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