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