• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 
StratifiedLinkStratifiedLink57   StratifiedLink() : Above(SetSentinel), Below(SetSentinel) {}
58 
hasBelowStratifiedLink59   bool hasBelow() const { return Below != SetSentinel; }
hasAboveStratifiedLink60   bool hasAbove() const { return Above != SetSentinel; }
61 
clearBelowStratifiedLink62   void clearBelow() { Below = SetSentinel; }
clearAboveStratifiedLink63   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
StratifiedSets(StratifiedSets && Other)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 
StratifiedSets(DenseMap<T,StratifiedInfo> Map,std::vector<StratifiedLink> Links)100   StratifiedSets(DenseMap<T, StratifiedInfo> Map,
101                  std::vector<StratifiedLink> Links)
102       : Values(std::move(Map)), Links(std::move(Links)) {}
103 
find(const T & Elem)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 
getLink(StratifiedIndex Index)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 
inbounds(StratifiedIndex Idx)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 
BuilderLinkBuilderLink190     BuilderLink(StratifiedIndex N) : Number(N) {
191       Remap = StratifiedLink::SetSentinel;
192     }
193 
hasAboveBuilderLink194     bool hasAbove() const {
195       assert(!isRemapped());
196       return Link.hasAbove();
197     }
198 
hasBelowBuilderLink199     bool hasBelow() const {
200       assert(!isRemapped());
201       return Link.hasBelow();
202     }
203 
setBelowBuilderLink204     void setBelow(StratifiedIndex I) {
205       assert(!isRemapped());
206       Link.Below = I;
207     }
208 
setAboveBuilderLink209     void setAbove(StratifiedIndex I) {
210       assert(!isRemapped());
211       Link.Above = I;
212     }
213 
clearBelowBuilderLink214     void clearBelow() {
215       assert(!isRemapped());
216       Link.clearBelow();
217     }
218 
clearAboveBuilderLink219     void clearAbove() {
220       assert(!isRemapped());
221       Link.clearAbove();
222     }
223 
getBelowBuilderLink224     StratifiedIndex getBelow() const {
225       assert(!isRemapped());
226       assert(hasBelow());
227       return Link.Below;
228     }
229 
getAboveBuilderLink230     StratifiedIndex getAbove() const {
231       assert(!isRemapped());
232       assert(hasAbove());
233       return Link.Above;
234     }
235 
getAttrsBuilderLink236     AliasAttrs getAttrs() {
237       assert(!isRemapped());
238       return Link.Attrs;
239     }
240 
setAttrsBuilderLink241     void setAttrs(AliasAttrs Other) {
242       assert(!isRemapped());
243       Link.Attrs |= Other;
244     }
245 
isRemappedBuilderLink246     bool isRemapped() const { return Remap != StratifiedLink::SetSentinel; }
247 
248     /// For initial remapping to another set
remapToBuilderLink249     void remapTo(StratifiedIndex Other) {
250       assert(!isRemapped());
251       Remap = Other;
252     }
253 
getRemapIndexBuilderLink254     StratifiedIndex getRemapIndex() const {
255       assert(isRemapped());
256       return Remap;
257     }
258 
259     /// Should only be called when we're already remapped.
updateRemapBuilderLink260     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.
getLinkBuilderLink268     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.
finalizeSets(std::vector<StratifiedLink> & StratLinks)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.
propagateAttrs(std::vector<StratifiedLink> & Links)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.
build()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 
has(const T & Elem)353   bool has(const T &Elem) const { return get(Elem).hasValue(); }
354 
add(const T & Main)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.
addAbove(const T & Main,const T & ToAdd)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.
addBelow(const T & Main,const T & ToAdd)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 
addWith(const T & Main,const T & ToAdd)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 
noteAttributes(const T & Main,AliasAttrs NewAttrs)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.
addAtMerging(const T & ToAdd,StratifiedIndex Index)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.
linksAt(StratifiedIndex Index)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.
merge(StratifiedIndex Idx1,StratifiedIndex Idx2)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`.
mergeDirect(StratifiedIndex Idx1,StratifiedIndex 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.
tryMergeUpwards(StratifiedIndex LowerIndex,StratifiedIndex UpperIndex)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 
get(const T & Val)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 
get(const T & Val)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 
indexOf(const T & Val)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 
addLinkBelow(StratifiedIndex Set)580   StratifiedIndex addLinkBelow(StratifiedIndex Set) {
581     auto At = addLinks();
582     Links[Set].setBelow(At);
583     Links[At].setAbove(Set);
584     return At;
585   }
586 
addLinkAbove(StratifiedIndex Set)587   StratifiedIndex addLinkAbove(StratifiedIndex Set) {
588     auto At = addLinks();
589     Links[At].setBelow(Set);
590     Links[Set].setAbove(At);
591     return At;
592   }
593 
getNewUnlinkedIndex()594   StratifiedIndex getNewUnlinkedIndex() { return addLinks(); }
595 
addLinks()596   StratifiedIndex addLinks() {
597     auto Link = Links.size();
598     Links.push_back(BuilderLink(Link));
599     return Link;
600   }
601 
inbounds(StratifiedIndex N)602   bool inbounds(StratifiedIndex N) const { return N < Links.size(); }
603 };
604 }
605 }
606 #endif // LLVM_ADT_STRATIFIEDSETS_H
607