1277323Sdim//===- StratifiedSets.h - Abstract stratified sets implementation. --------===// 2277323Sdim// 3277323Sdim// The LLVM Compiler Infrastructure 4277323Sdim// 5277323Sdim// This file is distributed under the University of Illinois Open Source 6277323Sdim// License. See LICENSE.TXT for details. 7277323Sdim// 8277323Sdim//===----------------------------------------------------------------------===// 9277323Sdim 10277323Sdim#ifndef LLVM_ADT_STRATIFIEDSETS_H 11277323Sdim#define LLVM_ADT_STRATIFIEDSETS_H 12277323Sdim 13277323Sdim#include "llvm/ADT/DenseMap.h" 14277323Sdim#include "llvm/ADT/Optional.h" 15277323Sdim#include "llvm/ADT/SmallPtrSet.h" 16277323Sdim#include "llvm/ADT/SmallSet.h" 17277323Sdim#include "llvm/ADT/SmallVector.h" 18277323Sdim#include "llvm/Support/Compiler.h" 19277323Sdim#include <bitset> 20277323Sdim#include <cassert> 21277323Sdim#include <cmath> 22277323Sdim#include <limits> 23277323Sdim#include <type_traits> 24277323Sdim#include <utility> 25277323Sdim#include <vector> 26277323Sdim 27277323Sdimnamespace llvm { 28277323Sdim// \brief An index into Stratified Sets. 29277323Sdimtypedef unsigned StratifiedIndex; 30277323Sdim// NOTE: ^ This can't be a short -- bootstrapping clang has a case where 31277323Sdim// ~1M sets exist. 32277323Sdim 33277323Sdim// \brief Container of information related to a value in a StratifiedSet. 34277323Sdimstruct StratifiedInfo { 35277323Sdim StratifiedIndex Index; 36277323Sdim // For field sensitivity, etc. we can tack attributes on to this struct. 37277323Sdim}; 38277323Sdim 39277323Sdim// The number of attributes that StratifiedAttrs should contain. Attributes are 40277323Sdim// described below, and 32 was an arbitrary choice because it fits nicely in 32 41277323Sdim// bits (because we use a bitset for StratifiedAttrs). 42277323Sdimstatic const unsigned NumStratifiedAttrs = 32; 43277323Sdim 44277323Sdim// These are attributes that the users of StratifiedSets/StratifiedSetBuilders 45277323Sdim// may use for various purposes. These also have the special property of that 46277323Sdim// they are merged down. So, if set A is above set B, and one decides to set an 47277323Sdim// attribute in set A, then the attribute will automatically be set in set B. 48277323Sdimtypedef std::bitset<NumStratifiedAttrs> StratifiedAttrs; 49277323Sdim 50277323Sdim// \brief A "link" between two StratifiedSets. 51277323Sdimstruct StratifiedLink { 52277323Sdim // \brief This is a value used to signify "does not exist" where 53277323Sdim // the StratifiedIndex type is used. This is used instead of 54277323Sdim // Optional<StratifiedIndex> because Optional<StratifiedIndex> would 55277323Sdim // eat up a considerable amount of extra memory, after struct 56277323Sdim // padding/alignment is taken into account. 57277323Sdim static const StratifiedIndex SetSentinel; 58277323Sdim 59277323Sdim // \brief The index for the set "above" current 60277323Sdim StratifiedIndex Above; 61277323Sdim 62277323Sdim // \brief The link for the set "below" current 63277323Sdim StratifiedIndex Below; 64277323Sdim 65277323Sdim // \brief Attributes for these StratifiedSets. 66277323Sdim StratifiedAttrs Attrs; 67277323Sdim 68277323Sdim StratifiedLink() : Above(SetSentinel), Below(SetSentinel) {} 69277323Sdim 70277323Sdim bool hasBelow() const { return Below != SetSentinel; } 71277323Sdim bool hasAbove() const { return Above != SetSentinel; } 72277323Sdim 73277323Sdim void clearBelow() { Below = SetSentinel; } 74277323Sdim void clearAbove() { Above = SetSentinel; } 75277323Sdim}; 76277323Sdim 77277323Sdim// \brief These are stratified sets, as described in "Fast algorithms for 78277323Sdim// Dyck-CFL-reachability with applications to Alias Analysis" by Zhang Q, Lyu M 79277323Sdim// R, Yuan H, and Su Z. -- in short, this is meant to represent different sets 80277323Sdim// of Value*s. If two Value*s are in the same set, or if both sets have 81277323Sdim// overlapping attributes, then the Value*s are said to alias. 82277323Sdim// 83277323Sdim// Sets may be related by position, meaning that one set may be considered as 84277323Sdim// above or below another. In CFL Alias Analysis, this gives us an indication 85277323Sdim// of how two variables are related; if the set of variable A is below a set 86277323Sdim// containing variable B, then at some point, a variable that has interacted 87277323Sdim// with B (or B itself) was either used in order to extract the variable A, or 88277323Sdim// was used as storage of variable A. 89277323Sdim// 90277323Sdim// Sets may also have attributes (as noted above). These attributes are 91277323Sdim// generally used for noting whether a variable in the set has interacted with 92277323Sdim// a variable whose origins we don't quite know (i.e. globals/arguments), or if 93277323Sdim// the variable may have had operations performed on it (modified in a function 94277323Sdim// call). All attributes that exist in a set A must exist in all sets marked as 95277323Sdim// below set A. 96277323Sdimtemplate <typename T> class StratifiedSets { 97277323Sdimpublic: 98277323Sdim StratifiedSets() {} 99277323Sdim 100277323Sdim StratifiedSets(DenseMap<T, StratifiedInfo> Map, 101277323Sdim std::vector<StratifiedLink> Links) 102277323Sdim : Values(std::move(Map)), Links(std::move(Links)) {} 103277323Sdim 104277323Sdim StratifiedSets(StratifiedSets<T> &&Other) { *this = std::move(Other); } 105277323Sdim 106277323Sdim StratifiedSets &operator=(StratifiedSets<T> &&Other) { 107277323Sdim Values = std::move(Other.Values); 108277323Sdim Links = std::move(Other.Links); 109277323Sdim return *this; 110277323Sdim } 111277323Sdim 112277323Sdim Optional<StratifiedInfo> find(const T &Elem) const { 113277323Sdim auto Iter = Values.find(Elem); 114277323Sdim if (Iter == Values.end()) { 115277323Sdim return NoneType(); 116277323Sdim } 117277323Sdim return Iter->second; 118277323Sdim } 119277323Sdim 120277323Sdim const StratifiedLink &getLink(StratifiedIndex Index) const { 121277323Sdim assert(inbounds(Index)); 122277323Sdim return Links[Index]; 123277323Sdim } 124277323Sdim 125277323Sdimprivate: 126277323Sdim DenseMap<T, StratifiedInfo> Values; 127277323Sdim std::vector<StratifiedLink> Links; 128277323Sdim 129277323Sdim bool inbounds(StratifiedIndex Idx) const { return Idx < Links.size(); } 130277323Sdim}; 131277323Sdim 132277323Sdim// \brief Generic Builder class that produces StratifiedSets instances. 133277323Sdim// 134277323Sdim// The goal of this builder is to efficiently produce correct StratifiedSets 135277323Sdim// instances. To this end, we use a few tricks: 136277323Sdim// > Set chains (A method for linking sets together) 137277323Sdim// > Set remaps (A method for marking a set as an alias [irony?] of another) 138277323Sdim// 139277323Sdim// ==== Set chains ==== 140277323Sdim// This builder has a notion of some value A being above, below, or with some 141277323Sdim// other value B: 142277323Sdim// > The `A above B` relationship implies that there is a reference edge going 143277323Sdim// from A to B. Namely, it notes that A can store anything in B's set. 144277323Sdim// > The `A below B` relationship is the opposite of `A above B`. It implies 145277323Sdim// that there's a dereference edge going from A to B. 146277323Sdim// > The `A with B` relationship states that there's an assignment edge going 147277323Sdim// from A to B, and that A and B should be treated as equals. 148277323Sdim// 149277323Sdim// As an example, take the following code snippet: 150277323Sdim// 151277323Sdim// %a = alloca i32, align 4 152277323Sdim// %ap = alloca i32*, align 8 153277323Sdim// %app = alloca i32**, align 8 154277323Sdim// store %a, %ap 155277323Sdim// store %ap, %app 156277323Sdim// %aw = getelementptr %ap, 0 157277323Sdim// 158277323Sdim// Given this, the follow relations exist: 159277323Sdim// - %a below %ap & %ap above %a 160277323Sdim// - %ap below %app & %app above %ap 161277323Sdim// - %aw with %ap & %ap with %aw 162277323Sdim// 163277323Sdim// These relations produce the following sets: 164277323Sdim// [{%a}, {%ap, %aw}, {%app}] 165277323Sdim// 166277323Sdim// ...Which states that the only MayAlias relationship in the above program is 167277323Sdim// between %ap and %aw. 168277323Sdim// 169277323Sdim// Life gets more complicated when we actually have logic in our programs. So, 170277323Sdim// we either must remove this logic from our programs, or make consessions for 171277323Sdim// it in our AA algorithms. In this case, we have decided to select the latter 172277323Sdim// option. 173277323Sdim// 174277323Sdim// First complication: Conditionals 175277323Sdim// Motivation: 176277323Sdim// %ad = alloca int, align 4 177277323Sdim// %a = alloca int*, align 8 178277323Sdim// %b = alloca int*, align 8 179277323Sdim// %bp = alloca int**, align 8 180277323Sdim// %c = call i1 @SomeFunc() 181277323Sdim// %k = select %c, %ad, %bp 182277323Sdim// store %ad, %a 183277323Sdim// store %b, %bp 184277323Sdim// 185277323Sdim// %k has 'with' edges to both %a and %b, which ordinarily would not be linked 186277323Sdim// together. So, we merge the set that contains %a with the set that contains 187277323Sdim// %b. We then recursively merge the set above %a with the set above %b, and 188277323Sdim// the set below %a with the set below %b, etc. Ultimately, the sets for this 189277323Sdim// program would end up like: {%ad}, {%a, %b, %k}, {%bp}, where {%ad} is below 190277323Sdim// {%a, %b, %c} is below {%ad}. 191277323Sdim// 192277323Sdim// Second complication: Arbitrary casts 193277323Sdim// Motivation: 194277323Sdim// %ip = alloca int*, align 8 195277323Sdim// %ipp = alloca int**, align 8 196277323Sdim// %i = bitcast ipp to int 197277323Sdim// store %ip, %ipp 198277323Sdim// store %i, %ip 199277323Sdim// 200277323Sdim// This is impossible to construct with any of the rules above, because a set 201277323Sdim// containing both {%i, %ipp} is supposed to exist, the set with %i is supposed 202277323Sdim// to be below the set with %ip, and the set with %ip is supposed to be below 203277323Sdim// the set with %ipp. Because we don't allow circular relationships like this, 204277323Sdim// we merge all concerned sets into one. So, the above code would generate a 205277323Sdim// single StratifiedSet: {%ip, %ipp, %i}. 206277323Sdim// 207277323Sdim// ==== Set remaps ==== 208277323Sdim// More of an implementation detail than anything -- when merging sets, we need 209277323Sdim// to update the numbers of all of the elements mapped to those sets. Rather 210277323Sdim// than doing this at each merge, we note in the BuilderLink structure that a 211277323Sdim// remap has occurred, and use this information so we can defer renumbering set 212277323Sdim// elements until build time. 213277323Sdimtemplate <typename T> class StratifiedSetsBuilder { 214277323Sdim // \brief Represents a Stratified Set, with information about the Stratified 215277323Sdim // Set above it, the set below it, and whether the current set has been 216277323Sdim // remapped to another. 217277323Sdim struct BuilderLink { 218277323Sdim const StratifiedIndex Number; 219277323Sdim 220277323Sdim BuilderLink(StratifiedIndex N) : Number(N) { 221277323Sdim Remap = StratifiedLink::SetSentinel; 222277323Sdim } 223277323Sdim 224277323Sdim bool hasAbove() const { 225277323Sdim assert(!isRemapped()); 226277323Sdim return Link.hasAbove(); 227277323Sdim } 228277323Sdim 229277323Sdim bool hasBelow() const { 230277323Sdim assert(!isRemapped()); 231277323Sdim return Link.hasBelow(); 232277323Sdim } 233277323Sdim 234277323Sdim void setBelow(StratifiedIndex I) { 235277323Sdim assert(!isRemapped()); 236277323Sdim Link.Below = I; 237277323Sdim } 238277323Sdim 239277323Sdim void setAbove(StratifiedIndex I) { 240277323Sdim assert(!isRemapped()); 241277323Sdim Link.Above = I; 242277323Sdim } 243277323Sdim 244277323Sdim void clearBelow() { 245277323Sdim assert(!isRemapped()); 246277323Sdim Link.clearBelow(); 247277323Sdim } 248277323Sdim 249277323Sdim void clearAbove() { 250277323Sdim assert(!isRemapped()); 251277323Sdim Link.clearAbove(); 252277323Sdim } 253277323Sdim 254277323Sdim StratifiedIndex getBelow() const { 255277323Sdim assert(!isRemapped()); 256277323Sdim assert(hasBelow()); 257277323Sdim return Link.Below; 258277323Sdim } 259277323Sdim 260277323Sdim StratifiedIndex getAbove() const { 261277323Sdim assert(!isRemapped()); 262277323Sdim assert(hasAbove()); 263277323Sdim return Link.Above; 264277323Sdim } 265277323Sdim 266277323Sdim StratifiedAttrs &getAttrs() { 267277323Sdim assert(!isRemapped()); 268277323Sdim return Link.Attrs; 269277323Sdim } 270277323Sdim 271277323Sdim void setAttr(unsigned index) { 272277323Sdim assert(!isRemapped()); 273277323Sdim assert(index < NumStratifiedAttrs); 274277323Sdim Link.Attrs.set(index); 275277323Sdim } 276277323Sdim 277277323Sdim void setAttrs(const StratifiedAttrs &other) { 278277323Sdim assert(!isRemapped()); 279277323Sdim Link.Attrs |= other; 280277323Sdim } 281277323Sdim 282277323Sdim bool isRemapped() const { return Remap != StratifiedLink::SetSentinel; } 283277323Sdim 284277323Sdim // \brief For initial remapping to another set 285277323Sdim void remapTo(StratifiedIndex Other) { 286277323Sdim assert(!isRemapped()); 287277323Sdim Remap = Other; 288277323Sdim } 289277323Sdim 290277323Sdim StratifiedIndex getRemapIndex() const { 291277323Sdim assert(isRemapped()); 292277323Sdim return Remap; 293277323Sdim } 294277323Sdim 295277323Sdim // \brief Should only be called when we're already remapped. 296277323Sdim void updateRemap(StratifiedIndex Other) { 297277323Sdim assert(isRemapped()); 298277323Sdim Remap = Other; 299277323Sdim } 300277323Sdim 301277323Sdim // \brief Prefer the above functions to calling things directly on what's 302277323Sdim // returned from this -- they guard against unexpected calls when the 303277323Sdim // current BuilderLink is remapped. 304277323Sdim const StratifiedLink &getLink() const { return Link; } 305277323Sdim 306277323Sdim private: 307277323Sdim StratifiedLink Link; 308277323Sdim StratifiedIndex Remap; 309277323Sdim }; 310277323Sdim 311277323Sdim // \brief This function performs all of the set unioning/value renumbering 312277323Sdim // that we've been putting off, and generates a vector<StratifiedLink> that 313277323Sdim // may be placed in a StratifiedSets instance. 314277323Sdim void finalizeSets(std::vector<StratifiedLink> &StratLinks) { 315277323Sdim DenseMap<StratifiedIndex, StratifiedIndex> Remaps; 316277323Sdim for (auto &Link : Links) { 317277323Sdim if (Link.isRemapped()) { 318277323Sdim continue; 319277323Sdim } 320277323Sdim 321277323Sdim StratifiedIndex Number = StratLinks.size(); 322277323Sdim Remaps.insert(std::make_pair(Link.Number, Number)); 323277323Sdim StratLinks.push_back(Link.getLink()); 324277323Sdim } 325277323Sdim 326277323Sdim for (auto &Link : StratLinks) { 327277323Sdim if (Link.hasAbove()) { 328277323Sdim auto &Above = linksAt(Link.Above); 329277323Sdim auto Iter = Remaps.find(Above.Number); 330277323Sdim assert(Iter != Remaps.end()); 331277323Sdim Link.Above = Iter->second; 332277323Sdim } 333277323Sdim 334277323Sdim if (Link.hasBelow()) { 335277323Sdim auto &Below = linksAt(Link.Below); 336277323Sdim auto Iter = Remaps.find(Below.Number); 337277323Sdim assert(Iter != Remaps.end()); 338277323Sdim Link.Below = Iter->second; 339277323Sdim } 340277323Sdim } 341277323Sdim 342277323Sdim for (auto &Pair : Values) { 343277323Sdim auto &Info = Pair.second; 344277323Sdim auto &Link = linksAt(Info.Index); 345277323Sdim auto Iter = Remaps.find(Link.Number); 346277323Sdim assert(Iter != Remaps.end()); 347277323Sdim Info.Index = Iter->second; 348277323Sdim } 349277323Sdim } 350277323Sdim 351277323Sdim // \brief There's a guarantee in StratifiedLink where all bits set in a 352277323Sdim // Link.externals will be set in all Link.externals "below" it. 353277323Sdim static void propagateAttrs(std::vector<StratifiedLink> &Links) { 354277323Sdim const auto getHighestParentAbove = [&Links](StratifiedIndex Idx) { 355277323Sdim const auto *Link = &Links[Idx]; 356277323Sdim while (Link->hasAbove()) { 357277323Sdim Idx = Link->Above; 358277323Sdim Link = &Links[Idx]; 359277323Sdim } 360277323Sdim return Idx; 361277323Sdim }; 362277323Sdim 363277323Sdim SmallSet<StratifiedIndex, 16> Visited; 364277323Sdim for (unsigned I = 0, E = Links.size(); I < E; ++I) { 365277323Sdim auto CurrentIndex = getHighestParentAbove(I); 366277323Sdim if (!Visited.insert(CurrentIndex).second) { 367277323Sdim continue; 368277323Sdim } 369277323Sdim 370277323Sdim while (Links[CurrentIndex].hasBelow()) { 371277323Sdim auto &CurrentBits = Links[CurrentIndex].Attrs; 372277323Sdim auto NextIndex = Links[CurrentIndex].Below; 373277323Sdim auto &NextBits = Links[NextIndex].Attrs; 374277323Sdim NextBits |= CurrentBits; 375277323Sdim CurrentIndex = NextIndex; 376277323Sdim } 377277323Sdim } 378277323Sdim } 379277323Sdim 380277323Sdimpublic: 381277323Sdim // \brief Builds a StratifiedSet from the information we've been given since 382277323Sdim // either construction or the prior build() call. 383277323Sdim StratifiedSets<T> build() { 384277323Sdim std::vector<StratifiedLink> StratLinks; 385277323Sdim finalizeSets(StratLinks); 386277323Sdim propagateAttrs(StratLinks); 387277323Sdim Links.clear(); 388277323Sdim return StratifiedSets<T>(std::move(Values), std::move(StratLinks)); 389277323Sdim } 390277323Sdim 391277323Sdim std::size_t size() const { return Values.size(); } 392277323Sdim std::size_t numSets() const { return Links.size(); } 393277323Sdim 394277323Sdim bool has(const T &Elem) const { return get(Elem).hasValue(); } 395277323Sdim 396277323Sdim bool add(const T &Main) { 397277323Sdim if (get(Main).hasValue()) 398277323Sdim return false; 399277323Sdim 400277323Sdim auto NewIndex = getNewUnlinkedIndex(); 401277323Sdim return addAtMerging(Main, NewIndex); 402277323Sdim } 403277323Sdim 404277323Sdim // \brief Restructures the stratified sets as necessary to make "ToAdd" in a 405277323Sdim // set above "Main". There are some cases where this is not possible (see 406277323Sdim // above), so we merge them such that ToAdd and Main are in the same set. 407277323Sdim bool addAbove(const T &Main, const T &ToAdd) { 408277323Sdim assert(has(Main)); 409277323Sdim auto Index = *indexOf(Main); 410277323Sdim if (!linksAt(Index).hasAbove()) 411277323Sdim addLinkAbove(Index); 412277323Sdim 413277323Sdim auto Above = linksAt(Index).getAbove(); 414277323Sdim return addAtMerging(ToAdd, Above); 415277323Sdim } 416277323Sdim 417277323Sdim // \brief Restructures the stratified sets as necessary to make "ToAdd" in a 418277323Sdim // set below "Main". There are some cases where this is not possible (see 419277323Sdim // above), so we merge them such that ToAdd and Main are in the same set. 420277323Sdim bool addBelow(const T &Main, const T &ToAdd) { 421277323Sdim assert(has(Main)); 422277323Sdim auto Index = *indexOf(Main); 423277323Sdim if (!linksAt(Index).hasBelow()) 424277323Sdim addLinkBelow(Index); 425277323Sdim 426277323Sdim auto Below = linksAt(Index).getBelow(); 427277323Sdim return addAtMerging(ToAdd, Below); 428277323Sdim } 429277323Sdim 430277323Sdim bool addWith(const T &Main, const T &ToAdd) { 431277323Sdim assert(has(Main)); 432277323Sdim auto MainIndex = *indexOf(Main); 433277323Sdim return addAtMerging(ToAdd, MainIndex); 434277323Sdim } 435277323Sdim 436277323Sdim void noteAttribute(const T &Main, unsigned AttrNum) { 437277323Sdim assert(has(Main)); 438277323Sdim assert(AttrNum < StratifiedLink::SetSentinel); 439277323Sdim auto *Info = *get(Main); 440277323Sdim auto &Link = linksAt(Info->Index); 441277323Sdim Link.setAttr(AttrNum); 442277323Sdim } 443277323Sdim 444277323Sdim void noteAttributes(const T &Main, const StratifiedAttrs &NewAttrs) { 445277323Sdim assert(has(Main)); 446277323Sdim auto *Info = *get(Main); 447277323Sdim auto &Link = linksAt(Info->Index); 448277323Sdim Link.setAttrs(NewAttrs); 449277323Sdim } 450277323Sdim 451277323Sdim StratifiedAttrs getAttributes(const T &Main) { 452277323Sdim assert(has(Main)); 453277323Sdim auto *Info = *get(Main); 454277323Sdim auto *Link = &linksAt(Info->Index); 455277323Sdim auto Attrs = Link->getAttrs(); 456277323Sdim while (Link->hasAbove()) { 457277323Sdim Link = &linksAt(Link->getAbove()); 458277323Sdim Attrs |= Link->getAttrs(); 459277323Sdim } 460277323Sdim 461277323Sdim return Attrs; 462277323Sdim } 463277323Sdim 464277323Sdim bool getAttribute(const T &Main, unsigned AttrNum) { 465277323Sdim assert(AttrNum < StratifiedLink::SetSentinel); 466277323Sdim auto Attrs = getAttributes(Main); 467277323Sdim return Attrs[AttrNum]; 468277323Sdim } 469277323Sdim 470277323Sdim // \brief Gets the attributes that have been applied to the set that Main 471277323Sdim // belongs to. It ignores attributes in any sets above the one that Main 472277323Sdim // resides in. 473277323Sdim StratifiedAttrs getRawAttributes(const T &Main) { 474277323Sdim assert(has(Main)); 475277323Sdim auto *Info = *get(Main); 476277323Sdim auto &Link = linksAt(Info->Index); 477277323Sdim return Link.getAttrs(); 478277323Sdim } 479277323Sdim 480277323Sdim // \brief Gets an attribute from the attributes that have been applied to the 481277323Sdim // set that Main belongs to. It ignores attributes in any sets above the one 482277323Sdim // that Main resides in. 483277323Sdim bool getRawAttribute(const T &Main, unsigned AttrNum) { 484277323Sdim assert(AttrNum < StratifiedLink::SetSentinel); 485277323Sdim auto Attrs = getRawAttributes(Main); 486277323Sdim return Attrs[AttrNum]; 487277323Sdim } 488277323Sdim 489277323Sdimprivate: 490277323Sdim DenseMap<T, StratifiedInfo> Values; 491277323Sdim std::vector<BuilderLink> Links; 492277323Sdim 493277323Sdim // \brief Adds the given element at the given index, merging sets if 494277323Sdim // necessary. 495277323Sdim bool addAtMerging(const T &ToAdd, StratifiedIndex Index) { 496277323Sdim StratifiedInfo Info = {Index}; 497277323Sdim auto Pair = Values.insert(std::make_pair(ToAdd, Info)); 498277323Sdim if (Pair.second) 499277323Sdim return true; 500277323Sdim 501277323Sdim auto &Iter = Pair.first; 502277323Sdim auto &IterSet = linksAt(Iter->second.Index); 503277323Sdim auto &ReqSet = linksAt(Index); 504277323Sdim 505277323Sdim // Failed to add where we wanted to. Merge the sets. 506277323Sdim if (&IterSet != &ReqSet) 507277323Sdim merge(IterSet.Number, ReqSet.Number); 508277323Sdim 509277323Sdim return false; 510277323Sdim } 511277323Sdim 512277323Sdim // \brief Gets the BuilderLink at the given index, taking set remapping into 513277323Sdim // account. 514277323Sdim BuilderLink &linksAt(StratifiedIndex Index) { 515277323Sdim auto *Start = &Links[Index]; 516277323Sdim if (!Start->isRemapped()) 517277323Sdim return *Start; 518277323Sdim 519277323Sdim auto *Current = Start; 520277323Sdim while (Current->isRemapped()) 521277323Sdim Current = &Links[Current->getRemapIndex()]; 522277323Sdim 523277323Sdim auto NewRemap = Current->Number; 524277323Sdim 525277323Sdim // Run through everything that has yet to be updated, and update them to 526277323Sdim // remap to NewRemap 527277323Sdim Current = Start; 528277323Sdim while (Current->isRemapped()) { 529277323Sdim auto *Next = &Links[Current->getRemapIndex()]; 530277323Sdim Current->updateRemap(NewRemap); 531277323Sdim Current = Next; 532277323Sdim } 533277323Sdim 534277323Sdim return *Current; 535277323Sdim } 536277323Sdim 537277323Sdim // \brief Merges two sets into one another. Assumes that these sets are not 538277323Sdim // already one in the same 539277323Sdim void merge(StratifiedIndex Idx1, StratifiedIndex Idx2) { 540277323Sdim assert(inbounds(Idx1) && inbounds(Idx2)); 541277323Sdim assert(&linksAt(Idx1) != &linksAt(Idx2) && 542277323Sdim "Merging a set into itself is not allowed"); 543277323Sdim 544277323Sdim // CASE 1: If the set at `Idx1` is above or below `Idx2`, we need to merge 545277323Sdim // both the 546277323Sdim // given sets, and all sets between them, into one. 547277323Sdim if (tryMergeUpwards(Idx1, Idx2)) 548277323Sdim return; 549277323Sdim 550277323Sdim if (tryMergeUpwards(Idx2, Idx1)) 551277323Sdim return; 552277323Sdim 553277323Sdim // CASE 2: The set at `Idx1` is not in the same chain as the set at `Idx2`. 554277323Sdim // We therefore need to merge the two chains together. 555277323Sdim mergeDirect(Idx1, Idx2); 556277323Sdim } 557277323Sdim 558277323Sdim // \brief Merges two sets assuming that the set at `Idx1` is unreachable from 559277323Sdim // traversing above or below the set at `Idx2`. 560277323Sdim void mergeDirect(StratifiedIndex Idx1, StratifiedIndex Idx2) { 561277323Sdim assert(inbounds(Idx1) && inbounds(Idx2)); 562277323Sdim 563277323Sdim auto *LinksInto = &linksAt(Idx1); 564277323Sdim auto *LinksFrom = &linksAt(Idx2); 565277323Sdim // Merging everything above LinksInto then proceeding to merge everything 566277323Sdim // below LinksInto becomes problematic, so we go as far "up" as possible! 567277323Sdim while (LinksInto->hasAbove() && LinksFrom->hasAbove()) { 568277323Sdim LinksInto = &linksAt(LinksInto->getAbove()); 569277323Sdim LinksFrom = &linksAt(LinksFrom->getAbove()); 570277323Sdim } 571277323Sdim 572277323Sdim if (LinksFrom->hasAbove()) { 573277323Sdim LinksInto->setAbove(LinksFrom->getAbove()); 574277323Sdim auto &NewAbove = linksAt(LinksInto->getAbove()); 575277323Sdim NewAbove.setBelow(LinksInto->Number); 576277323Sdim } 577277323Sdim 578277323Sdim // Merging strategy: 579277323Sdim // > If neither has links below, stop. 580277323Sdim // > If only `LinksInto` has links below, stop. 581277323Sdim // > If only `LinksFrom` has links below, reset `LinksInto.Below` to 582277323Sdim // match `LinksFrom.Below` 583277323Sdim // > If both have links above, deal with those next. 584277323Sdim while (LinksInto->hasBelow() && LinksFrom->hasBelow()) { 585277323Sdim auto &FromAttrs = LinksFrom->getAttrs(); 586277323Sdim LinksInto->setAttrs(FromAttrs); 587277323Sdim 588277323Sdim // Remap needs to happen after getBelow(), but before 589277323Sdim // assignment of LinksFrom 590277323Sdim auto *NewLinksFrom = &linksAt(LinksFrom->getBelow()); 591277323Sdim LinksFrom->remapTo(LinksInto->Number); 592277323Sdim LinksFrom = NewLinksFrom; 593277323Sdim LinksInto = &linksAt(LinksInto->getBelow()); 594277323Sdim } 595277323Sdim 596277323Sdim if (LinksFrom->hasBelow()) { 597277323Sdim LinksInto->setBelow(LinksFrom->getBelow()); 598277323Sdim auto &NewBelow = linksAt(LinksInto->getBelow()); 599277323Sdim NewBelow.setAbove(LinksInto->Number); 600277323Sdim } 601277323Sdim 602277323Sdim LinksFrom->remapTo(LinksInto->Number); 603277323Sdim } 604277323Sdim 605277323Sdim // \brief Checks to see if lowerIndex is at a level lower than upperIndex. 606277323Sdim // If so, it will merge lowerIndex with upperIndex (and all of the sets 607277323Sdim // between) and return true. Otherwise, it will return false. 608277323Sdim bool tryMergeUpwards(StratifiedIndex LowerIndex, StratifiedIndex UpperIndex) { 609277323Sdim assert(inbounds(LowerIndex) && inbounds(UpperIndex)); 610277323Sdim auto *Lower = &linksAt(LowerIndex); 611277323Sdim auto *Upper = &linksAt(UpperIndex); 612277323Sdim if (Lower == Upper) 613277323Sdim return true; 614277323Sdim 615277323Sdim SmallVector<BuilderLink *, 8> Found; 616277323Sdim auto *Current = Lower; 617277323Sdim auto Attrs = Current->getAttrs(); 618277323Sdim while (Current->hasAbove() && Current != Upper) { 619277323Sdim Found.push_back(Current); 620277323Sdim Attrs |= Current->getAttrs(); 621277323Sdim Current = &linksAt(Current->getAbove()); 622277323Sdim } 623277323Sdim 624277323Sdim if (Current != Upper) 625277323Sdim return false; 626277323Sdim 627277323Sdim Upper->setAttrs(Attrs); 628277323Sdim 629277323Sdim if (Lower->hasBelow()) { 630277323Sdim auto NewBelowIndex = Lower->getBelow(); 631277323Sdim Upper->setBelow(NewBelowIndex); 632277323Sdim auto &NewBelow = linksAt(NewBelowIndex); 633277323Sdim NewBelow.setAbove(UpperIndex); 634277323Sdim } else { 635277323Sdim Upper->clearBelow(); 636277323Sdim } 637277323Sdim 638277323Sdim for (const auto &Ptr : Found) 639277323Sdim Ptr->remapTo(Upper->Number); 640277323Sdim 641277323Sdim return true; 642277323Sdim } 643277323Sdim 644277323Sdim Optional<const StratifiedInfo *> get(const T &Val) const { 645277323Sdim auto Result = Values.find(Val); 646277323Sdim if (Result == Values.end()) 647277323Sdim return NoneType(); 648277323Sdim return &Result->second; 649277323Sdim } 650277323Sdim 651277323Sdim Optional<StratifiedInfo *> get(const T &Val) { 652277323Sdim auto Result = Values.find(Val); 653277323Sdim if (Result == Values.end()) 654277323Sdim return NoneType(); 655277323Sdim return &Result->second; 656277323Sdim } 657277323Sdim 658277323Sdim Optional<StratifiedIndex> indexOf(const T &Val) { 659277323Sdim auto MaybeVal = get(Val); 660277323Sdim if (!MaybeVal.hasValue()) 661277323Sdim return NoneType(); 662277323Sdim auto *Info = *MaybeVal; 663277323Sdim auto &Link = linksAt(Info->Index); 664277323Sdim return Link.Number; 665277323Sdim } 666277323Sdim 667277323Sdim StratifiedIndex addLinkBelow(StratifiedIndex Set) { 668277323Sdim auto At = addLinks(); 669277323Sdim Links[Set].setBelow(At); 670277323Sdim Links[At].setAbove(Set); 671277323Sdim return At; 672277323Sdim } 673277323Sdim 674277323Sdim StratifiedIndex addLinkAbove(StratifiedIndex Set) { 675277323Sdim auto At = addLinks(); 676277323Sdim Links[At].setBelow(Set); 677277323Sdim Links[Set].setAbove(At); 678277323Sdim return At; 679277323Sdim } 680277323Sdim 681277323Sdim StratifiedIndex getNewUnlinkedIndex() { return addLinks(); } 682277323Sdim 683277323Sdim StratifiedIndex addLinks() { 684277323Sdim auto Link = Links.size(); 685277323Sdim Links.push_back(BuilderLink(Link)); 686277323Sdim return Link; 687277323Sdim } 688277323Sdim 689277323Sdim bool inbounds(StratifiedIndex N) const { return N < Links.size(); } 690277323Sdim}; 691277323Sdim} 692277323Sdim#endif // LLVM_ADT_STRATIFIEDSETS_H 693