contrib/llvm/lib/Analysis/StratifiedSets.h

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