1 //===- StratifiedSets.h - Abstract stratified sets implementation. --------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 #ifndef LLVM_ADT_STRATIFIEDSETS_H
11 #define LLVM_ADT_STRATIFIEDSETS_H
13 #include "llvm/ADT/DenseMap.h"
14 #include "llvm/ADT/Optional.h"
15 #include "llvm/ADT/SmallPtrSet.h"
16 #include "llvm/ADT/SmallSet.h"
17 #include "llvm/ADT/SmallVector.h"
18 #include "llvm/Support/Compiler.h"
23 #include <type_traits>
28 // \brief An index into Stratified Sets.
29 typedef unsigned StratifiedIndex;
30 // NOTE: ^ This can't be a short -- bootstrapping clang has a case where
33 // \brief Container of information related to a value in a StratifiedSet.
34 struct StratifiedInfo {
35 StratifiedIndex Index;
36 // For field sensitivity, etc. we can tack attributes on to this struct.
39 // The number of attributes that StratifiedAttrs should contain. Attributes are
40 // described below, and 32 was an arbitrary choice because it fits nicely in 32
41 // bits (because we use a bitset for StratifiedAttrs).
42 static const unsigned NumStratifiedAttrs = 32;
44 // These are attributes that the users of StratifiedSets/StratifiedSetBuilders
45 // may use for various purposes. These also have the special property of that
46 // they are merged down. So, if set A is above set B, and one decides to set an
47 // attribute in set A, then the attribute will automatically be set in set B.
48 typedef std::bitset<NumStratifiedAttrs> StratifiedAttrs;
50 // \brief A "link" between two StratifiedSets.
51 struct StratifiedLink {
52 // \brief This is a value used to signify "does not exist" where
53 // the StratifiedIndex type is used. This is used instead of
54 // Optional<StratifiedIndex> because Optional<StratifiedIndex> would
55 // eat up a considerable amount of extra memory, after struct
56 // padding/alignment is taken into account.
57 static const auto SetSentinel =
58 std::numeric_limits<StratifiedIndex>::max();
60 // \brief The index for the set "above" current
61 StratifiedIndex Above;
63 // \brief The link for the set "below" current
64 StratifiedIndex Below;
66 // \brief Attributes for these StratifiedSets.
67 StratifiedAttrs Attrs;
69 StratifiedLink() : Above(SetSentinel), Below(SetSentinel) {}
71 bool hasBelow() const { return Below != SetSentinel; }
72 bool hasAbove() const { return Above != SetSentinel; }
74 void clearBelow() { Below = SetSentinel; }
75 void clearAbove() { Above = SetSentinel; }
78 // \brief These are stratified sets, as described in "Fast algorithms for
79 // Dyck-CFL-reachability with applications to Alias Analysis" by Zhang Q, Lyu M
80 // R, Yuan H, and Su Z. -- in short, this is meant to represent different sets
81 // of Value*s. If two Value*s are in the same set, or if both sets have
82 // overlapping attributes, then the Value*s are said to alias.
84 // Sets may be related by position, meaning that one set may be considered as
85 // above or below another. In CFL Alias Analysis, this gives us an indication
86 // of how two variables are related; if the set of variable A is below a set
87 // containing variable B, then at some point, a variable that has interacted
88 // with B (or B itself) was either used in order to extract the variable A, or
89 // was used as storage of variable A.
91 // Sets may also have attributes (as noted above). These attributes are
92 // generally used for noting whether a variable in the set has interacted with
93 // a variable whose origins we don't quite know (i.e. globals/arguments), or if
94 // the variable may have had operations performed on it (modified in a function
95 // call). All attributes that exist in a set A must exist in all sets marked as
97 template <typename T> class StratifiedSets {
101 StratifiedSets(DenseMap<T, StratifiedInfo> Map,
102 std::vector<StratifiedLink> Links)
103 : Values(std::move(Map)), Links(std::move(Links)) {}
105 StratifiedSets(StratifiedSets<T> &&Other) { *this = std::move(Other); }
107 StratifiedSets &operator=(StratifiedSets<T> &&Other) {
108 Values = std::move(Other.Values);
109 Links = std::move(Other.Links);
113 Optional<StratifiedInfo> find(const T &Elem) const {
114 auto Iter = Values.find(Elem);
115 if (Iter == Values.end()) {
121 const StratifiedLink &getLink(StratifiedIndex Index) const {
122 assert(inbounds(Index));
127 DenseMap<T, StratifiedInfo> Values;
128 std::vector<StratifiedLink> Links;
130 bool inbounds(StratifiedIndex Idx) const { return Idx < Links.size(); }
133 // \brief Generic Builder class that produces StratifiedSets instances.
135 // The goal of this builder is to efficiently produce correct StratifiedSets
136 // instances. To this end, we use a few tricks:
137 // > Set chains (A method for linking sets together)
138 // > Set remaps (A method for marking a set as an alias [irony?] of another)
140 // ==== Set chains ====
141 // This builder has a notion of some value A being above, below, or with some
143 // > The `A above B` relationship implies that there is a reference edge going
144 // from A to B. Namely, it notes that A can store anything in B's set.
145 // > The `A below B` relationship is the opposite of `A above B`. It implies
146 // that there's a dereference edge going from A to B.
147 // > The `A with B` relationship states that there's an assignment edge going
148 // from A to B, and that A and B should be treated as equals.
150 // As an example, take the following code snippet:
152 // %a = alloca i32, align 4
153 // %ap = alloca i32*, align 8
154 // %app = alloca i32**, align 8
157 // %aw = getelementptr %ap, 0
159 // Given this, the follow relations exist:
160 // - %a below %ap & %ap above %a
161 // - %ap below %app & %app above %ap
162 // - %aw with %ap & %ap with %aw
164 // These relations produce the following sets:
165 // [{%a}, {%ap, %aw}, {%app}]
167 // ...Which states that the only MayAlias relationship in the above program is
168 // between %ap and %aw.
170 // Life gets more complicated when we actually have logic in our programs. So,
171 // we either must remove this logic from our programs, or make consessions for
172 // it in our AA algorithms. In this case, we have decided to select the latter
175 // First complication: Conditionals
177 // %ad = alloca int, align 4
178 // %a = alloca int*, align 8
179 // %b = alloca int*, align 8
180 // %bp = alloca int**, align 8
181 // %c = call i1 @SomeFunc()
182 // %k = select %c, %ad, %bp
186 // %k has 'with' edges to both %a and %b, which ordinarily would not be linked
187 // together. So, we merge the set that contains %a with the set that contains
188 // %b. We then recursively merge the set above %a with the set above %b, and
189 // the set below %a with the set below %b, etc. Ultimately, the sets for this
190 // program would end up like: {%ad}, {%a, %b, %k}, {%bp}, where {%ad} is below
191 // {%a, %b, %c} is below {%ad}.
193 // Second complication: Arbitrary casts
195 // %ip = alloca int*, align 8
196 // %ipp = alloca int**, align 8
197 // %i = bitcast ipp to int
201 // This is impossible to construct with any of the rules above, because a set
202 // containing both {%i, %ipp} is supposed to exist, the set with %i is supposed
203 // to be below the set with %ip, and the set with %ip is supposed to be below
204 // the set with %ipp. Because we don't allow circular relationships like this,
205 // we merge all concerned sets into one. So, the above code would generate a
206 // single StratifiedSet: {%ip, %ipp, %i}.
208 // ==== Set remaps ====
209 // More of an implementation detail than anything -- when merging sets, we need
210 // to update the numbers of all of the elements mapped to those sets. Rather
211 // than doing this at each merge, we note in the BuilderLink structure that a
212 // remap has occurred, and use this information so we can defer renumbering set
213 // elements until build time.
214 template <typename T> class StratifiedSetsBuilder {
215 // \brief Represents a Stratified Set, with information about the Stratified
216 // Set above it, the set below it, and whether the current set has been
217 // remapped to another.
219 const StratifiedIndex Number;
221 BuilderLink(StratifiedIndex N) : Number(N) {
222 Remap = StratifiedLink::SetSentinel;
225 bool hasAbove() const {
226 assert(!isRemapped());
227 return Link.hasAbove();
230 bool hasBelow() const {
231 assert(!isRemapped());
232 return Link.hasBelow();
235 void setBelow(StratifiedIndex I) {
236 assert(!isRemapped());
240 void setAbove(StratifiedIndex I) {
241 assert(!isRemapped());
246 assert(!isRemapped());
251 assert(!isRemapped());
255 StratifiedIndex getBelow() const {
256 assert(!isRemapped());
261 StratifiedIndex getAbove() const {
262 assert(!isRemapped());
267 StratifiedAttrs &getAttrs() {
268 assert(!isRemapped());
272 void setAttr(unsigned index) {
273 assert(!isRemapped());
274 assert(index < NumStratifiedAttrs);
275 Link.Attrs.set(index);
278 void setAttrs(const StratifiedAttrs &other) {
279 assert(!isRemapped());
283 bool isRemapped() const { return Remap != StratifiedLink::SetSentinel; }
285 // \brief For initial remapping to another set
286 void remapTo(StratifiedIndex Other) {
287 assert(!isRemapped());
291 StratifiedIndex getRemapIndex() const {
292 assert(isRemapped());
296 // \brief Should only be called when we're already remapped.
297 void updateRemap(StratifiedIndex Other) {
298 assert(isRemapped());
302 // \brief Prefer the above functions to calling things directly on what's
303 // returned from this -- they guard against unexpected calls when the
304 // current BuilderLink is remapped.
305 const StratifiedLink &getLink() const { return Link; }
309 StratifiedIndex Remap;
312 // \brief This function performs all of the set unioning/value renumbering
313 // that we've been putting off, and generates a vector<StratifiedLink> that
314 // may be placed in a StratifiedSets instance.
315 void finalizeSets(std::vector<StratifiedLink> &StratLinks) {
316 DenseMap<StratifiedIndex, StratifiedIndex> Remaps;
317 for (auto &Link : Links) {
318 if (Link.isRemapped()) {
322 StratifiedIndex Number = StratLinks.size();
323 Remaps.insert(std::make_pair(Link.Number, Number));
324 StratLinks.push_back(Link.getLink());
327 for (auto &Link : StratLinks) {
328 if (Link.hasAbove()) {
329 auto &Above = linksAt(Link.Above);
330 auto Iter = Remaps.find(Above.Number);
331 assert(Iter != Remaps.end());
332 Link.Above = Iter->second;
335 if (Link.hasBelow()) {
336 auto &Below = linksAt(Link.Below);
337 auto Iter = Remaps.find(Below.Number);
338 assert(Iter != Remaps.end());
339 Link.Below = Iter->second;
343 for (auto &Pair : Values) {
344 auto &Info = Pair.second;
345 auto &Link = linksAt(Info.Index);
346 auto Iter = Remaps.find(Link.Number);
347 assert(Iter != Remaps.end());
348 Info.Index = Iter->second;
352 // \brief There's a guarantee in StratifiedLink where all bits set in a
353 // Link.externals will be set in all Link.externals "below" it.
354 static void propagateAttrs(std::vector<StratifiedLink> &Links) {
355 const auto getHighestParentAbove = [&Links](StratifiedIndex Idx) {
356 const auto *Link = &Links[Idx];
357 while (Link->hasAbove()) {
364 SmallSet<StratifiedIndex, 16> Visited;
365 for (unsigned I = 0, E = Links.size(); I < E; ++I) {
366 auto CurrentIndex = getHighestParentAbove(I);
367 if (!Visited.insert(CurrentIndex)) {
371 while (Links[CurrentIndex].hasBelow()) {
372 auto &CurrentBits = Links[CurrentIndex].Attrs;
373 auto NextIndex = Links[CurrentIndex].Below;
374 auto &NextBits = Links[NextIndex].Attrs;
375 NextBits |= CurrentBits;
376 CurrentIndex = NextIndex;
382 // \brief Builds a StratifiedSet from the information we've been given since
383 // either construction or the prior build() call.
384 StratifiedSets<T> build() {
385 std::vector<StratifiedLink> StratLinks;
386 finalizeSets(StratLinks);
387 propagateAttrs(StratLinks);
389 return StratifiedSets<T>(std::move(Values), std::move(StratLinks));
392 std::size_t size() const { return Values.size(); }
393 std::size_t numSets() const { return Links.size(); }
395 bool has(const T &Elem) const { return get(Elem).hasValue(); }
397 bool add(const T &Main) {
398 if (get(Main).hasValue())
401 auto NewIndex = getNewUnlinkedIndex();
402 return addAtMerging(Main, NewIndex);
405 // \brief Restructures the stratified sets as necessary to make "ToAdd" in a
406 // set above "Main". There are some cases where this is not possible (see
407 // above), so we merge them such that ToAdd and Main are in the same set.
408 bool addAbove(const T &Main, const T &ToAdd) {
410 auto Index = *indexOf(Main);
411 if (!linksAt(Index).hasAbove())
414 auto Above = linksAt(Index).getAbove();
415 return addAtMerging(ToAdd, Above);
418 // \brief Restructures the stratified sets as necessary to make "ToAdd" in a
419 // set below "Main". There are some cases where this is not possible (see
420 // above), so we merge them such that ToAdd and Main are in the same set.
421 bool addBelow(const T &Main, const T &ToAdd) {
423 auto Index = *indexOf(Main);
424 if (!linksAt(Index).hasBelow())
427 auto Below = linksAt(Index).getBelow();
428 return addAtMerging(ToAdd, Below);
431 bool addWith(const T &Main, const T &ToAdd) {
433 auto MainIndex = *indexOf(Main);
434 return addAtMerging(ToAdd, MainIndex);
437 void noteAttribute(const T &Main, unsigned AttrNum) {
439 assert(AttrNum < StratifiedLink::SetSentinel);
440 auto *Info = *get(Main);
441 auto &Link = linksAt(Info->Index);
442 Link.setAttr(AttrNum);
445 void noteAttributes(const T &Main, const StratifiedAttrs &NewAttrs) {
447 auto *Info = *get(Main);
448 auto &Link = linksAt(Info->Index);
449 Link.setAttrs(NewAttrs);
452 StratifiedAttrs getAttributes(const T &Main) {
454 auto *Info = *get(Main);
455 auto *Link = &linksAt(Info->Index);
456 auto Attrs = Link->getAttrs();
457 while (Link->hasAbove()) {
458 Link = &linksAt(Link->getAbove());
459 Attrs |= Link->getAttrs();
465 bool getAttribute(const T &Main, unsigned AttrNum) {
466 assert(AttrNum < StratifiedLink::SetSentinel);
467 auto Attrs = getAttributes(Main);
468 return Attrs[AttrNum];
471 // \brief Gets the attributes that have been applied to the set that Main
472 // belongs to. It ignores attributes in any sets above the one that Main
474 StratifiedAttrs getRawAttributes(const T &Main) {
476 auto *Info = *get(Main);
477 auto &Link = linksAt(Info->Index);
478 return Link.getAttrs();
481 // \brief Gets an attribute from the attributes that have been applied to the
482 // set that Main belongs to. It ignores attributes in any sets above the one
483 // that Main resides in.
484 bool getRawAttribute(const T &Main, unsigned AttrNum) {
485 assert(AttrNum < StratifiedLink::SetSentinel);
486 auto Attrs = getRawAttributes(Main);
487 return Attrs[AttrNum];
491 DenseMap<T, StratifiedInfo> Values;
492 std::vector<BuilderLink> Links;
494 // \brief Adds the given element at the given index, merging sets if
496 bool addAtMerging(const T &ToAdd, StratifiedIndex Index) {
497 StratifiedInfo Info = {Index};
498 auto Pair = Values.insert(std::make_pair(ToAdd, Info));
502 auto &Iter = Pair.first;
503 auto &IterSet = linksAt(Iter->second.Index);
504 auto &ReqSet = linksAt(Index);
506 // Failed to add where we wanted to. Merge the sets.
507 if (&IterSet != &ReqSet)
508 merge(IterSet.Number, ReqSet.Number);
513 // \brief Gets the BuilderLink at the given index, taking set remapping into
515 BuilderLink &linksAt(StratifiedIndex Index) {
516 auto *Start = &Links[Index];
517 if (!Start->isRemapped())
520 auto *Current = Start;
521 while (Current->isRemapped())
522 Current = &Links[Current->getRemapIndex()];
524 auto NewRemap = Current->Number;
526 // Run through everything that has yet to be updated, and update them to
529 while (Current->isRemapped()) {
530 auto *Next = &Links[Current->getRemapIndex()];
531 Current->updateRemap(NewRemap);
538 // \brief Merges two sets into one another. Assumes that these sets are not
539 // already one in the same
540 void merge(StratifiedIndex Idx1, StratifiedIndex Idx2) {
541 assert(inbounds(Idx1) && inbounds(Idx2));
542 assert(&linksAt(Idx1) != &linksAt(Idx2) &&
543 "Merging a set into itself is not allowed");
545 // CASE 1: If the set at `Idx1` is above or below `Idx2`, we need to merge
547 // given sets, and all sets between them, into one.
548 if (tryMergeUpwards(Idx1, Idx2))
551 if (tryMergeUpwards(Idx2, Idx1))
554 // CASE 2: The set at `Idx1` is not in the same chain as the set at `Idx2`.
555 // We therefore need to merge the two chains together.
556 mergeDirect(Idx1, Idx2);
559 // \brief Merges two sets assuming that the set at `Idx1` is unreachable from
560 // traversing above or below the set at `Idx2`.
561 void mergeDirect(StratifiedIndex Idx1, StratifiedIndex Idx2) {
562 assert(inbounds(Idx1) && inbounds(Idx2));
564 auto *LinksInto = &linksAt(Idx1);
565 auto *LinksFrom = &linksAt(Idx2);
566 // Merging everything above LinksInto then proceeding to merge everything
567 // below LinksInto becomes problematic, so we go as far "up" as possible!
568 while (LinksInto->hasAbove() && LinksFrom->hasAbove()) {
569 LinksInto = &linksAt(LinksInto->getAbove());
570 LinksFrom = &linksAt(LinksFrom->getAbove());
573 if (LinksFrom->hasAbove()) {
574 LinksInto->setAbove(LinksFrom->getAbove());
575 auto &NewAbove = linksAt(LinksInto->getAbove());
576 NewAbove.setBelow(LinksInto->Number);
580 // > If neither has links below, stop.
581 // > If only `LinksInto` has links below, stop.
582 // > If only `LinksFrom` has links below, reset `LinksInto.Below` to
583 // match `LinksFrom.Below`
584 // > If both have links above, deal with those next.
585 while (LinksInto->hasBelow() && LinksFrom->hasBelow()) {
586 auto &FromAttrs = LinksFrom->getAttrs();
587 LinksInto->setAttrs(FromAttrs);
589 // Remap needs to happen after getBelow(), but before
590 // assignment of LinksFrom
591 auto *NewLinksFrom = &linksAt(LinksFrom->getBelow());
592 LinksFrom->remapTo(LinksInto->Number);
593 LinksFrom = NewLinksFrom;
594 LinksInto = &linksAt(LinksInto->getBelow());
597 if (LinksFrom->hasBelow()) {
598 LinksInto->setBelow(LinksFrom->getBelow());
599 auto &NewBelow = linksAt(LinksInto->getBelow());
600 NewBelow.setAbove(LinksInto->Number);
603 LinksFrom->remapTo(LinksInto->Number);
606 // \brief Checks to see if lowerIndex is at a level lower than upperIndex.
607 // If so, it will merge lowerIndex with upperIndex (and all of the sets
608 // between) and return true. Otherwise, it will return false.
609 bool tryMergeUpwards(StratifiedIndex LowerIndex, StratifiedIndex UpperIndex) {
610 assert(inbounds(LowerIndex) && inbounds(UpperIndex));
611 auto *Lower = &linksAt(LowerIndex);
612 auto *Upper = &linksAt(UpperIndex);
616 SmallVector<BuilderLink *, 8> Found;
617 auto *Current = Lower;
618 auto Attrs = Current->getAttrs();
619 while (Current->hasAbove() && Current != Upper) {
620 Found.push_back(Current);
621 Attrs |= Current->getAttrs();
622 Current = &linksAt(Current->getAbove());
625 if (Current != Upper)
628 Upper->setAttrs(Attrs);
630 if (Lower->hasBelow()) {
631 auto NewBelowIndex = Lower->getBelow();
632 Upper->setBelow(NewBelowIndex);
633 auto &NewBelow = linksAt(NewBelowIndex);
634 NewBelow.setAbove(UpperIndex);
639 for (const auto &Ptr : Found)
640 Ptr->remapTo(Upper->Number);
645 Optional<const StratifiedInfo *> get(const T &Val) const {
646 auto Result = Values.find(Val);
647 if (Result == Values.end())
649 return &Result->second;
652 Optional<StratifiedInfo *> get(const T &Val) {
653 auto Result = Values.find(Val);
654 if (Result == Values.end())
656 return &Result->second;
659 Optional<StratifiedIndex> indexOf(const T &Val) {
660 auto MaybeVal = get(Val);
661 if (!MaybeVal.hasValue())
663 auto *Info = *MaybeVal;
664 auto &Link = linksAt(Info->Index);
668 StratifiedIndex addLinkBelow(StratifiedIndex Set) {
669 auto At = addLinks();
670 Links[Set].setBelow(At);
671 Links[At].setAbove(Set);
675 StratifiedIndex addLinkAbove(StratifiedIndex Set) {
676 auto At = addLinks();
677 Links[At].setBelow(Set);
678 Links[Set].setAbove(At);
682 StratifiedIndex getNewUnlinkedIndex() { return addLinks(); }
684 StratifiedIndex addLinks() {
685 auto Link = Links.size();
686 Links.push_back(BuilderLink(Link));
690 bool inbounds(StratifiedIndex N) const { return N < Links.size(); }
693 #endif // LLVM_ADT_STRATIFIEDSETS_H