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