LCOV - code coverage report
Current view: top level - lib/Analysis - StratifiedSets.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 119 142 83.8 %
Date: 2018-10-20 13:21:21 Functions: 15 27 55.6 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.13