lib/Analysis/StratifiedSets.h

   1 //===- StratifiedSets.h - Abstract stratified sets implementation. --------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #ifndef LLVM_ADT_STRATIFIEDSETS_H
  11 #define LLVM_ADT_STRATIFIEDSETS_H
  12
  13 #include "llvm/ADT/DenseMap.h"
  14 #include "llvm/ADT/Optional.h"
  15 #include "llvm/ADT/SmallPtrSet.h"
  16 #include "llvm/ADT/SmallSet.h"
  17 #include "llvm/ADT/SmallVector.h"
  18 #include <bitset>
  19 #include <cassert>
  20 #include <cmath>
  21 #include <limits>
  22 #include <type_traits>
  23 #include <vector>
  24
  25 namespace llvm {
  26 // \brief An index into Stratified Sets.
  27 typedef unsigned StratifiedIndex;
  28 // NOTE: ^ This can't be a short -- bootstrapping clang has a case where
  29 // ~1M sets exist.
  30
  31 // \brief Container of information related to a value in a StratifiedSet.
  32 struct StratifiedInfo {
  33   StratifiedIndex Index;
  34   // For field sensitivity, etc. we can tack attributes on to this struct.
  35 };
  36
  37 // The number of attributes that StratifiedAttrs should contain. Attributes are
  38 // described below, and 32 was an arbitrary choice because it fits nicely in 32
  39 // bits (because we use a bitset for StratifiedAttrs).
  40 static constexpr unsigned NumStratifiedAttrs = 32;
  41
  42 // These are attributes that the users of StratifiedSets/StratifiedSetBuilders
  43 // may use for various purposes. These also have the special property of that
  44 // they are merged down. So, if set A is above set B, and one decides to set an
  45 // attribute in set A, then the attribute will automatically be set in set B.
  46 typedef std::bitset<NumStratifiedAttrs> StratifiedAttrs;
  47
  48 // \brief A "link" between two StratifiedSets.
  49 struct StratifiedLink {
  50   // \brief This is a value used to signify "does not exist" where
  51   // the StratifiedIndex type is used. This is used instead of
  52   // Optional<StratifiedIndex> because Optional<StratifiedIndex> would
  53   // eat up a considerable amount of extra memory, after struct
  54   // padding/alignment is taken into account.
  55   static constexpr auto SetSentinel =
  56       std::numeric_limits<StratifiedIndex>::max();
  57
  58   // \brief The index for the set "above" current
  59   StratifiedIndex Above;
  60
  61   // \brief The link for the set "below" current
  62   StratifiedIndex Below;
  63
  64   // \brief Attributes for these StratifiedSets.
  65   StratifiedAttrs Attrs;
  66
  67   StratifiedLink() : Above(SetSentinel), Below(SetSentinel) {}
  68
  69   bool hasBelow() const { return Below != SetSentinel; }
  70   bool hasAbove() const { return Above != SetSentinel; }
  71
  72   void clearBelow() { Below = SetSentinel; }
  73   void clearAbove() { Above = SetSentinel; }
  74 };
  75
  76 // \brief These are stratified sets, as described in "Fast algorithms for
  77 // Dyck-CFL-reachability with applications to Alias Analysis" by Zhang Q, Lyu M
  78 // R, Yuan H, and Su Z. -- in short, this is meant to represent different sets
  79 // of Value*s. If two Value*s are in the same set, or if both sets have
  80 // overlapping attributes, then the Value*s are said to alias.
  81 //
  82 // Sets may be related by position, meaning that one set may be considered as
  83 // above or below another. In CFL Alias Analysis, this gives us an indication
  84 // of how two variables are related; if the set of variable A is below a set
  85 // containing variable B, then at some point, a variable that has interacted
  86 // with B (or B itself) was either used in order to extract the variable A, or
  87 // was used as storage of variable A.
  88 //
  89 // Sets may also have attributes (as noted above). These attributes are
  90 // generally used for noting whether a variable in the set has interacted with
  91 // a variable whose origins we don't quite know (i.e. globals/arguments), or if
  92 // the variable may have had operations performed on it (modified in a function
  93 // call). All attributes that exist in a set A must exist in all sets marked as
  94 // below set A.
  95 template <typename T> class StratifiedSets {
  96 public:
  97   StratifiedSets() {}
  98
  99   StratifiedSets(DenseMap<T, StratifiedInfo> Map,
 100                  std::vector<StratifiedLink> Links)
 101       : Values(std::move(Map)), Links(std::move(Links)) {}
 102
 103   StratifiedSets(StratifiedSets<T> &&Other) { *this = std::move(Other); }
 104
 105   StratifiedSets &operator=(StratifiedSets<T> &&Other) {
 106     Values = std::move(Other.Values);
 107     Links = std::move(Other.Links);
 108     return *this;
 109   }
 110
 111   Optional<StratifiedInfo> find(const T &Elem) const {
 112     auto Iter = Values.find(Elem);
 113     if (Iter == Values.end()) {
 114       return NoneType();
 115     }
 116     return Iter->second;
 117   }
 118
 119   const StratifiedLink &getLink(StratifiedIndex Index) const {
 120     assert(inbounds(Index));
 121     return Links[Index];
 122   }
 123
 124 private:
 125   DenseMap<T, StratifiedInfo> Values;
 126   std::vector<StratifiedLink> Links;
 127
 128   bool inbounds(StratifiedIndex Idx) const { return Idx < Links.size(); }
 129 };
 130
 131 // \brief Generic Builder class that produces StratifiedSets instances.
 132 //
 133 // The goal of this builder is to efficiently produce correct StratifiedSets
 134 // instances. To this end, we use a few tricks:
 135 //   > Set chains (A method for linking sets together)
 136 //   > Set remaps (A method for marking a set as an alias [irony?] of another)
 137 //
 138 // ==== Set chains ====
 139 // This builder has a notion of some value A being above, below, or with some
 140 // other value B:
 141 //   > The `A above B` relationship implies that there is a reference edge going
 142 //   from A to B. Namely, it notes that A can store anything in B's set.
 143 //   > The `A below B` relationship is the opposite of `A above B`. It implies
 144 //   that there's a dereference edge going from A to B.
 145 //   > The `A with B` relationship states that there's an assignment edge going
 146 //   from A to B, and that A and B should be treated as equals.
 147 //
 148 // As an example, take the following code snippet:
 149 //
 150 // %a = alloca i32, align 4
 151 // %ap = alloca i32*, align 8
 152 // %app = alloca i32**, align 8
 153 // store %a, %ap
 154 // store %ap, %app
 155 // %aw = getelementptr %ap, 0
 156 //
 157 // Given this, the follow relations exist:
 158 //   - %a below %ap & %ap above %a
 159 //   - %ap below %app & %app above %ap
 160 //   - %aw with %ap & %ap with %aw
 161 //
 162 // These relations produce the following sets:
 163 //   [{%a}, {%ap, %aw}, {%app}]
 164 //
 165 // ...Which states that the only MayAlias relationship in the above program is
 166 // between %ap and %aw.
 167 //
 168 // Life gets more complicated when we actually have logic in our programs. So,
 169 // we either must remove this logic from our programs, or make consessions for
 170 // it in our AA algorithms. In this case, we have decided to select the latter
 171 // option.
 172 //
 173 // First complication: Conditionals
 174 // Motivation:
 175 //  %ad = alloca int, align 4
 176 //  %a = alloca int*, align 8
 177 //  %b = alloca int*, align 8
 178 //  %bp = alloca int**, align 8
 179 //  %c = call i1 @SomeFunc()
 180 //  %k = select %c, %ad, %bp
 181 //  store %ad, %a
 182 //  store %b, %bp
 183 //
 184 // %k has 'with' edges to both %a and %b, which ordinarily would not be linked
 185 // together. So, we merge the set that contains %a with the set that contains
 186 // %b. We then recursively merge the set above %a with the set above %b, and
 187 // the set below  %a with the set below %b, etc. Ultimately, the sets for this
 188 // program would end up like: {%ad}, {%a, %b, %k}, {%bp}, where {%ad} is below
 189 // {%a, %b, %c} is below {%ad}.
 190 //
 191 // Second complication: Arbitrary casts
 192 // Motivation:
 193 //  %ip = alloca int*, align 8
 194 //  %ipp = alloca int**, align 8
 195 //  %i = bitcast ipp to int
 196 //  store %ip, %ipp
 197 //  store %i, %ip
 198 //
 199 // This is impossible to construct with any of the rules above, because a set
 200 // containing both {%i, %ipp} is supposed to exist, the set with %i is supposed
 201 // to be below the set with %ip, and the set with %ip is supposed to be below
 202 // the set with %ipp. Because we don't allow circular relationships like this,
 203 // we merge all concerned sets into one. So, the above code would generate a
 204 // single StratifiedSet: {%ip, %ipp, %i}.
 205 //
 206 // ==== Set remaps ====
 207 // More of an implementation detail than anything -- when merging sets, we need
 208 // to update the numbers of all of the elements mapped to those sets. Rather
 209 // than doing this at each merge, we note in the BuilderLink structure that a
 210 // remap has occurred, and use this information so we can defer renumbering set
 211 // elements until build time.
 212 template <typename T> class StratifiedSetsBuilder {
 213   // \brief Represents a Stratified Set, with information about the Stratified
 214   // Set above it, the set below it, and whether the current set has been
 215   // remapped to another.
 216   struct BuilderLink {
 217     const StratifiedIndex Number;
 218
 219     BuilderLink(StratifiedIndex N) : Number(N) {
 220       Remap = StratifiedLink::SetSentinel;
 221     }
 222
 223     bool hasAbove() const {
 224       assert(!isRemapped());
 225       return Link.hasAbove();
 226     }
 227
 228     bool hasBelow() const {
 229       assert(!isRemapped());
 230       return Link.hasBelow();
 231     }
 232
 233     void setBelow(StratifiedIndex I) {
 234       assert(!isRemapped());
 235       Link.Below = I;
 236     }
 237
 238     void setAbove(StratifiedIndex I) {
 239       assert(!isRemapped());
 240       Link.Above = I;
 241     }
 242
 243     void clearBelow() {
 244       assert(!isRemapped());
 245       Link.clearBelow();
 246     }
 247
 248     void clearAbove() {
 249       assert(!isRemapped());
 250       Link.clearAbove();
 251     }
 252
 253     StratifiedIndex getBelow() const {
 254       assert(!isRemapped());
 255       assert(hasBelow());
 256       return Link.Below;
 257     }
 258
 259     StratifiedIndex getAbove() const {
 260       assert(!isRemapped());
 261       assert(hasAbove());
 262       return Link.Above;
 263     }
 264
 265     StratifiedAttrs &getAttrs() {
 266       assert(!isRemapped());
 267       return Link.Attrs;
 268     }
 269
 270     void setAttr(unsigned index) {
 271       assert(!isRemapped());
 272       assert(index < NumStratifiedAttrs);
 273       Link.Attrs.set(index);
 274     }
 275
 276     void setAttrs(const StratifiedAttrs &other) {
 277       assert(!isRemapped());
 278       Link.Attrs |= other;
 279     }
 280
 281     bool isRemapped() const { return Remap != StratifiedLink::SetSentinel; }
 282
 283     // \brief For initial remapping to another set
 284     void remapTo(StratifiedIndex Other) {
 285       assert(!isRemapped());
 286       Remap = Other;
 287     }
 288
 289     StratifiedIndex getRemapIndex() const {
 290       assert(isRemapped());
 291       return Remap;
 292     }
 293
 294     // \brief Should only be called when we're already remapped.
 295     void updateRemap(StratifiedIndex Other) {
 296       assert(isRemapped());
 297       Remap = Other;
 298     }
 299
 300     // \brief Prefer the above functions to calling things directly on what's
 301     // returned from this -- they guard against unexpected calls when the
 302     // current BuilderLink is remapped.
 303     const StratifiedLink &getLink() const { return Link; }
 304
 305   private:
 306     StratifiedLink Link;
 307     StratifiedIndex Remap;
 308   };
 309
 310   // \brief This function performs all of the set unioning/value renumbering
 311   // that we've been putting off, and generates a vector<StratifiedLink> that
 312   // may be placed in a StratifiedSets instance.
 313   void finalizeSets(std::vector<StratifiedLink> &StratLinks) {
 314     DenseMap<StratifiedIndex, StratifiedIndex> Remaps;
 315     for (auto &Link : Links) {
 316       if (Link.isRemapped()) {
 317         continue;
 318       }
 319
 320       StratifiedIndex Number = StratLinks.size();
 321       Remaps.insert({Link.Number, Number});
 322       StratLinks.push_back(Link.getLink());
 323     }
 324
 325     for (auto &Link : StratLinks) {
 326       if (Link.hasAbove()) {
 327         auto &Above = linksAt(Link.Above);
 328         auto Iter = Remaps.find(Above.Number);
 329         assert(Iter != Remaps.end());
 330         Link.Above = Iter->second;
 331       }
 332
 333       if (Link.hasBelow()) {
 334         auto &Below = linksAt(Link.Below);
 335         auto Iter = Remaps.find(Below.Number);
 336         assert(Iter != Remaps.end());
 337         Link.Below = Iter->second;
 338       }
 339     }
 340
 341     for (auto &Pair : Values) {
 342       auto &Info = Pair.second;
 343       auto &Link = linksAt(Info.Index);
 344       auto Iter = Remaps.find(Link.Number);
 345       assert(Iter != Remaps.end());
 346       Info.Index = Iter->second;
 347     }
 348   }
 349
 350   // \brief There's a guarantee in StratifiedLink where all bits set in a
 351   // Link.externals will be set in all Link.externals "below" it.
 352   static void propagateAttrs(std::vector<StratifiedLink> &Links) {
 353     const auto getHighestParentAbove = [&Links](StratifiedIndex Idx) {
 354       const auto *Link = &Links[Idx];
 355       while (Link->hasAbove()) {
 356         Idx = Link->Above;
 357         Link = &Links[Idx];
 358       }
 359       return Idx;
 360     };
 361
 362     SmallSet<StratifiedIndex, 16> Visited;
 363     for (unsigned I = 0, E = Links.size(); I < E; ++I) {
 364       auto CurrentIndex = getHighestParentAbove(I);
 365       if (!Visited.insert(CurrentIndex)) {
 366         continue;
 367       }
 368
 369       while (Links[CurrentIndex].hasBelow()) {
 370         auto &CurrentBits = Links[CurrentIndex].Attrs;
 371         auto NextIndex = Links[CurrentIndex].Below;
 372         auto &NextBits = Links[NextIndex].Attrs;
 373         NextBits |= CurrentBits;
 374         CurrentIndex = NextIndex;
 375       }
 376     }
 377   }
 378
 379 public:
 380   // \brief Builds a StratifiedSet from the information we've been given since
 381   // either construction or the prior build() call.
 382   StratifiedSets<T> build() {
 383     std::vector<StratifiedLink> StratLinks;
 384     finalizeSets(StratLinks);
 385     propagateAttrs(StratLinks);
 386     Links.clear();
 387     return StratifiedSets<T>(std::move(Values), std::move(StratLinks));
 388   }
 389
 390   std::size_t size() const { return Values.size(); }
 391   std::size_t numSets() const { return Links.size(); }
 392
 393   bool has(const T &Elem) const { return get(Elem).hasValue(); }
 394
 395   bool add(const T &Main) {
 396     if (get(Main).hasValue())
 397       return false;
 398
 399     auto NewIndex = getNewUnlinkedIndex();
 400     return addAtMerging(Main, NewIndex);
 401   }
 402
 403   // \brief Restructures the stratified sets as necessary to make "ToAdd" in a
 404   // set above "Main". There are some cases where this is not possible (see
 405   // above), so we merge them such that ToAdd and Main are in the same set.
 406   bool addAbove(const T &Main, const T &ToAdd) {
 407     assert(has(Main));
 408     auto Index = *indexOf(Main);
 409     if (!linksAt(Index).hasAbove())
 410       addLinkAbove(Index);
 411
 412     auto Above = linksAt(Index).getAbove();
 413     return addAtMerging(ToAdd, Above);
 414   }
 415
 416   // \brief Restructures the stratified sets as necessary to make "ToAdd" in a
 417   // set below "Main". There are some cases where this is not possible (see
 418   // above), so we merge them such that ToAdd and Main are in the same set.
 419   bool addBelow(const T &Main, const T &ToAdd) {
 420     assert(has(Main));
 421     auto Index = *indexOf(Main);
 422     if (!linksAt(Index).hasBelow())
 423       addLinkBelow(Index);
 424
 425     auto Below = linksAt(Index).getBelow();
 426     return addAtMerging(ToAdd, Below);
 427   }
 428
 429   bool addWith(const T &Main, const T &ToAdd) {
 430     assert(has(Main));
 431     auto MainIndex = *indexOf(Main);
 432     return addAtMerging(ToAdd, MainIndex);
 433   }
 434
 435   void noteAttribute(const T &Main, unsigned AttrNum) {
 436     assert(has(Main));
 437     assert(AttrNum < StratifiedLink::SetSentinel);
 438     auto *Info = *get(Main);
 439     auto &Link = linksAt(Info->Index);
 440     Link.setAttr(AttrNum);
 441   }
 442
 443   void noteAttributes(const T &Main, const StratifiedAttrs &NewAttrs) {
 444     assert(has(Main));
 445     auto *Info = *get(Main);
 446     auto &Link = linksAt(Info->Index);
 447     Link.setAttrs(NewAttrs);
 448   }
 449
 450   StratifiedAttrs getAttributes(const T &Main) {
 451     assert(has(Main));
 452     auto *Info = *get(Main);
 453     auto *Link = &linksAt(Info->Index);
 454     auto Attrs = Link->getAttrs();
 455     while (Link->hasAbove()) {
 456       Link = &linksAt(Link->getAbove());
 457       Attrs |= Link->getAttrs();
 458     }
 459
 460     return Attrs;
 461   }
 462
 463   bool getAttribute(const T &Main, unsigned AttrNum) {
 464     assert(AttrNum < StratifiedLink::SetSentinel);
 465     auto Attrs = getAttributes(Main);
 466     return Attrs[AttrNum];
 467   }
 468
 469   // \brief Gets the attributes that have been applied to the set that Main
 470   // belongs to. It ignores attributes in any sets above the one that Main
 471   // resides in.
 472   StratifiedAttrs getRawAttributes(const T &Main) {
 473     assert(has(Main));
 474     auto *Info = *get(Main);
 475     auto &Link = linksAt(Info->Index);
 476     return Link.getAttrs();
 477   }
 478
 479   // \brief Gets an attribute from the attributes that have been applied to the
 480   // set that Main belongs to. It ignores attributes in any sets above the one
 481   // that Main resides in.
 482   bool getRawAttribute(const T &Main, unsigned AttrNum) {
 483     assert(AttrNum < StratifiedLink::SetSentinel);
 484     auto Attrs = getRawAttributes(Main);
 485     return Attrs[AttrNum];
 486   }
 487
 488 private:
 489   DenseMap<T, StratifiedInfo> Values;
 490   std::vector<BuilderLink> Links;
 491
 492   // \brief Adds the given element at the given index, merging sets if
 493   // necessary.
 494   bool addAtMerging(const T &ToAdd, StratifiedIndex Index) {
 495     StratifiedInfo Info = {Index};
 496     auto Pair = Values.insert({ToAdd, Info});
 497     if (Pair.second)
 498       return true;
 499
 500     auto &Iter = Pair.first;
 501     auto &IterSet = linksAt(Iter->second.Index);
 502     auto &ReqSet = linksAt(Index);
 503
 504     // Failed to add where we wanted to. Merge the sets.
 505     if (&IterSet != &ReqSet)
 506       merge(IterSet.Number, ReqSet.Number);
 507
 508     return false;
 509   }
 510
 511   // \brief Gets the BuilderLink at the given index, taking set remapping into
 512   // account.
 513   BuilderLink &linksAt(StratifiedIndex Index) {
 514     auto *Start = &Links[Index];
 515     if (!Start->isRemapped())
 516       return *Start;
 517
 518     auto *Current = Start;
 519     while (Current->isRemapped())
 520       Current = &Links[Current->getRemapIndex()];
 521
 522     auto NewRemap = Current->Number;
 523
 524     // Run through everything that has yet to be updated, and update them to
 525     // remap to NewRemap
 526     Current = Start;
 527     while (Current->isRemapped()) {
 528       auto *Next = &Links[Current->getRemapIndex()];
 529       Current->updateRemap(NewRemap);
 530       Current = Next;
 531     }
 532
 533     return *Current;
 534   }
 535
 536   // \brief Merges two sets into one another. Assumes that these sets are not
 537   // already one in the same
 538   void merge(StratifiedIndex Idx1, StratifiedIndex Idx2) {
 539     assert(inbounds(Idx1) && inbounds(Idx2));
 540     assert(&linksAt(Idx1) != &linksAt(Idx2) &&
 541            "Merging a set into itself is not allowed");
 542
 543     // CASE 1: If the set at `Idx1` is above or below `Idx2`, we need to merge
 544     // both the
 545     // given sets, and all sets between them, into one.
 546     if (tryMergeUpwards(Idx1, Idx2))
 547       return;
 548
 549     if (tryMergeUpwards(Idx2, Idx1))
 550       return;
 551
 552     // CASE 2: The set at `Idx1` is not in the same chain as the set at `Idx2`.
 553     // We therefore need to merge the two chains together.
 554     mergeDirect(Idx1, Idx2);
 555   }
 556
 557   // \brief Merges two sets assuming that the set at `Idx1` is unreachable from
 558   // traversing above or below the set at `Idx2`.
 559   void mergeDirect(StratifiedIndex Idx1, StratifiedIndex Idx2) {
 560     assert(inbounds(Idx1) && inbounds(Idx2));
 561
 562     auto *LinksInto = &linksAt(Idx1);
 563     auto *LinksFrom = &linksAt(Idx2);
 564     // Merging everything above LinksInto then proceeding to merge everything
 565     // below LinksInto becomes problematic, so we go as far "up" as possible!
 566     while (LinksInto->hasAbove() && LinksFrom->hasAbove()) {
 567       LinksInto = &linksAt(LinksInto->getAbove());
 568       LinksFrom = &linksAt(LinksFrom->getAbove());
 569     }
 570
 571     if (LinksFrom->hasAbove()) {
 572       LinksInto->setAbove(LinksFrom->getAbove());
 573       auto &NewAbove = linksAt(LinksInto->getAbove());
 574       NewAbove.setBelow(LinksInto->Number);
 575     }
 576
 577     // Merging strategy:
 578     //  > If neither has links below, stop.
 579     //  > If only `LinksInto` has links below, stop.
 580     //  > If only `LinksFrom` has links below, reset `LinksInto.Below` to
 581     //  match `LinksFrom.Below`
 582     //  > If both have links above, deal with those next.
 583     while (LinksInto->hasBelow() && LinksFrom->hasBelow()) {
 584       auto &FromAttrs = LinksFrom->getAttrs();
 585       LinksInto->setAttrs(FromAttrs);
 586
 587       // Remap needs to happen after getBelow(), but before
 588       // assignment of LinksFrom
 589       auto *NewLinksFrom = &linksAt(LinksFrom->getBelow());
 590       LinksFrom->remapTo(LinksInto->Number);
 591       LinksFrom = NewLinksFrom;
 592       LinksInto = &linksAt(LinksInto->getBelow());
 593     }
 594
 595     if (LinksFrom->hasBelow()) {
 596       LinksInto->setBelow(LinksFrom->getBelow());
 597       auto &NewBelow = linksAt(LinksInto->getBelow());
 598       NewBelow.setAbove(LinksInto->Number);
 599     }
 600
 601     LinksFrom->remapTo(LinksInto->Number);
 602   }
 603
 604   // \brief Checks to see if lowerIndex is at a level lower than upperIndex.
 605   // If so, it will merge lowerIndex with upperIndex (and all of the sets
 606   // between) and return true. Otherwise, it will return false.
 607   bool tryMergeUpwards(StratifiedIndex LowerIndex, StratifiedIndex UpperIndex) {
 608     assert(inbounds(LowerIndex) && inbounds(UpperIndex));
 609     auto *Lower = &linksAt(LowerIndex);
 610     auto *Upper = &linksAt(UpperIndex);
 611     if (Lower == Upper)
 612       return true;
 613
 614     SmallVector<BuilderLink *, 8> Found;
 615     auto *Current = Lower;
 616     auto Attrs = Current->getAttrs();
 617     while (Current->hasAbove() && Current != Upper) {
 618       Found.push_back(Current);
 619       Attrs |= Current->getAttrs();
 620       Current = &linksAt(Current->getAbove());
 621     }
 622
 623     if (Current != Upper)
 624       return false;
 625
 626     Upper->setAttrs(Attrs);
 627
 628     if (Lower->hasBelow()) {
 629       auto NewBelowIndex = Lower->getBelow();
 630       Upper->setBelow(NewBelowIndex);
 631       auto &NewBelow = linksAt(NewBelowIndex);
 632       NewBelow.setAbove(UpperIndex);
 633     } else {
 634       Upper->clearBelow();
 635     }
 636
 637     for (const auto &Ptr : Found)
 638       Ptr->remapTo(Upper->Number);
 639
 640     return true;
 641   }
 642
 643   Optional<const StratifiedInfo *> get(const T &Val) const {
 644     auto Result = Values.find(Val);
 645     if (Result == Values.end())
 646       return NoneType();
 647     return &Result->second;
 648   }
 649
 650   Optional<StratifiedInfo *> get(const T &Val) {
 651     auto Result = Values.find(Val);
 652     if (Result == Values.end())
 653       return NoneType();
 654     return &Result->second;
 655   }
 656
 657   Optional<StratifiedIndex> indexOf(const T &Val) {
 658     auto MaybeVal = get(Val);
 659     if (!MaybeVal.hasValue())
 660       return NoneType();
 661     auto *Info = *MaybeVal;
 662     auto &Link = linksAt(Info->Index);
 663     return Link.Number;
 664   }
 665
 666   StratifiedIndex addLinkBelow(StratifiedIndex Set) {
 667     auto At = addLinks();
 668     Links[Set].setBelow(At);
 669     Links[At].setAbove(Set);
 670     return At;
 671   }
 672
 673   StratifiedIndex addLinkAbove(StratifiedIndex Set) {
 674     auto At = addLinks();
 675     Links[At].setBelow(Set);
 676     Links[Set].setAbove(At);
 677     return At;
 678   }
 679
 680   StratifiedIndex getNewUnlinkedIndex() { return addLinks(); }
 681
 682   StratifiedIndex addLinks() {
 683     auto Link = Links.size();
 684     Links.push_back(BuilderLink(Link));
 685     return Link;
 686   }
 687
 688   bool inbounds(StratifiedIndex N) const { return N >= 0 && N < Links.size(); }
 689 };
 690 }
 691 #endif // LLVM_ADT_STRATIFIEDSETS_H