LLVM CFL Alias Analysis -- Supporting Data Structures

[george.burgess.iv]

Summary

For the motivation for this patch, please see the primary CFL Alias Analysis patch titled "LLVM CFL Alias Analysis -- Algorithm"

This was split off from the primary CFL AA patch because a ~1.5KLOC review is never fun, and this can be cleanly committed prior to committing the "main" CFL AA patch.

This contains the implementation of a weighted, bidirected graph and of a stratified sets algorithm. For more information, see here: http://www.cse.cuhk.edu.hk/lyu/_media/paper/pldi2013.pdf

[• dberlin]

Just some preliminary comments

lib/Analysis/StratifiedSets.h

95

For this implementation, it would be good to explain what the impact of having something above or below something else is. You later use the "below" property to ensure proper marking of externals aliasing, but without an explanation of what the impact of being below something is, it's not obvious to a reader that what you do is right.

409

An explanation of what exactly this worklist algorithm is doing, and why it is right, would be good :)

[• gbiv]

Addressed dberlin's comments, swapped std::map->DenseMap and std::set->DenseSet, and took out some unnecessary headers.

[hfinkel]

Hi George,

Thanks for working on this! I apologize ahead of time for not entering these comments on the web site (I was composing this review on the plane). As a general note, you'll need to fix a bunch of compliance issues with LLVM's coding conventions (variable naming, braces, etc.), and while I pointed out a couple of these, I quickly stopped.

+ \brief These are stratified sets, as described in the paper located at
+ www.cse.cuhk.edu.hk/lyu/_media/paper/pldi2013.pdf -- in short, this is meant

This looks like an unofficial link that could become stale. I recommend including the full reference (a search engine can find the PDF, if it is still available, at some future time).

+ class StratifiedInfo;
+
+ class StratifiedInfo {
+ public:

You don't need to pre-declare this one line before defining it. Also, make it a struct.

+// This builder allows the user to add elements with, (at the same level as)

Remove the comma prior to the parenthesis.

+// In the paper above, StratifiedSets are described as a data structure wherein

"In the paper above, StratifiedSets are described as" -> "StratifiedSets are"

+ constexpr static auto SetSentinel =
+ std::numeric_limits<StratifiedIndex>::max();

Add a comment explaining how this is used.

+ and the set deemed as below it. This also keeps information on the notion
+ of "remapping",

What does it mean to "keep information on the notion of" somthing? Does this means it manages the state associated with state remapping?

+ elements that have parents in the union-find structure. This is super
+ difficult to debug, so we use accessors.

You don't need to justify the use of accessors.

+ void setBelow(StratifiedIndex i) {
+ assert(!isRemapped());
+ below = i;
+ }

Please assert that i != SetSentinel. Same applies to setAbove and remapTo.

+ // aliasedExternal without that check. So we have this.

Remove "So we have this."

+ bool hasAliasedExternalRaw() const { return aliasedExternal; }

It sounds like this should not be public. Make it private and make this a friend of whatever needs access.

+ // \brief For initial remapping to another set
+ void remapTo(StratifiedIndex other) {

What's the reason for using the term "remapping" to describe the set unioning operation? There seem to be better choices (union, join, group; maybe some term related to proxying would be more appropriate?).

+ Removing dead sets may not be worth it -- "saves" us 20 bits in the average
+ case (51 sets total) and 4KB in the worst case (out of 1.07M sets == ~133KB
+ // total) when bootstrapping LLVM.

I don't understand this comment in the context of the code. It saves us bits where?

+ while (current->hasAbove()) {
+ current = &linksAt(current->getAbove());
+ }

Remove the {}

+ DenseSet<SetLinks *> visited;

SmallPtrSet<SetLinks, 16> Visisted; (pick some number you feel is reasonable, 16 is just a guess on my part) -- unless you expect the set to be pretty large.

+ bool hasExternals = false;

HasExternals (please follow the LLVM coding conventions for naming variables)

+ if (!insertSuccess) {
+ continue;
+ }

Remove {} (please follow the LLVM coding conventions in this regard)

+ \brief We store external aliasing information as part of SetLinks, when
+ it's way more space efficient to store it as a bitset. This generates said
+ // bitset.

This comment implies that this function moves information into a bitset to save space, but it does not. It simply creates the bitset, leaving the original information in the links unchanged.

+ std::vector<bool> aliasingExternals;
+ aliasingExternals.resize(links.size());

Set the size using the constructor.

+ assert(&linksAt(idx1) != &linksAt(idx2));

This assert needs some text because it is not obvious what it is asserting. Make it something like:

assert(&linksAt(idx1) != &linksAt(idx2) && "Trying to merge two sets with the same <fill in here>");

+ // CASE 1: If into is above or below from, we need to merge both the

Which one is 'into'?

+ We want directional searches up/down, but for the initial case, we want
+ to search both up and down.

Please clarify what 'up/down' means (does this mean 'up or down' or 'up then down').

+ // Funny story: the current implementation of this function makes it

Yea, you know ;)

+ TODO: Maybe find a better way to do this than a forest of if
+ statements?

This will look somewhat better once you remove all of the unnecessary {}

+ // TODO: Maybe restructure? I don't like public->private->public

Either do it or remove the comment.

-Hal

• Original Message -----

From: "George Burgess IV" <[e-mail]>
To: [e-mail], [e-mail], [e-mail], [e-mail]
Cc: [e-mail]
Sent: Friday, July 18, 2014 2:26:40 PM
Subject: Re: [PATCH] LLVM CFL Alias Analysis -- Supporting Data Structures

Addressed dberlin's comments, swapped std::map->DenseMap and
std::set->DenseSet, and took out some unnecessary headers.

http://reviews.llvm.org/D4550

Files:

lib/Analysis/StratifiedSets.h
lib/Analysis/WeightedBidirectedGraph.h

---

llvm-commits mailing list
[e-mail]
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

[sanjoy]

Totally bike-shedding comment on terminology: StratifiedSets.h uses terms that both leak the fact that we're manipulating memory expressions and aliasing information (hasAliasingExternal) and terms that try to hide it (up, down). It may be clearer to rename either hasAliasingExternal to something more general (some property that is transitive in the "low" direction) or up / down to something more specific (addressof / dereference).

lib/Analysis/StratifiedSets.h

136

Should this be %k = select %c, %ad, %bp?

423

Why only update start here? Can't the whole sequence of SetLinks remapped to the final index? If it is beneficial to updateRemap only start, why not do it outside the loop, once we have the first SetLink that isn't remapped?

495

If I understood the logic correctly here, maybe this can be written not as worklist algorithm, but simply as two loops, each in one direction? So something structurally like this:

StratifiedIndex linksIntoIdx = idx1, linksFromIdx = idx2;
while (true) {
  auto &linksInto = linksAt(linksIntoIdx);
  auto &linksFrom = linksAt(linksFromIdx);
  linksInto.remapTo(linksFrom.number);

  if (linksInto.hasAbove() && linksFrom.hasAbove()) {
    linksIntoIdx = linksInto.getAbove();
    linksFromIdx = linksFrom.getAbove();
  } else {
    break;
  }
}

if (linksAt(linksIntoIdx).hasAbove() || linksAt(linksFromIdx).hasAbove()) {
  auto &topLink =
      linksAt(linksIntoIdx).hasAbove() ?
      linksAt(linksIntoIdx).getAbove() : linksAt(linksFromIdx).getAbove();
  topLink.setBelow(linksIntoIdx);
  linksAt(linksIntoIdx).setAbove(topLink);
}

// ... and a second loop in the below direction

If the logic cannot be expressed that way then a comment on why that is the case would help. :)

[• gbiv]

Updated code to better match LLVM style, addressed most/all of hfinkel's and sanjoy's concerns.

Responses to a few of the higher-level comments:
hfinkel:

What does it mean to "keep information on the notion of" somthing? Does this means it manages the state associated with state remapping?

Comment updated in an effort to better describe what I'm doing. :)

What's the reason for using the term "remapping" to describe the set unioning operation? There seem to be better choices (union, join, group; maybe some term related to proxying would be more appropriate?).

It seemed like it fit what was happening well enough, because our goal is to effectively treat the "remapped" set as deleted, and a proxy a different set. I do like the terms "ProxyFor" and "Proxies" more though, so I'll swap to one of the two in the next rev.

sanjoy:

{Terminology comment}

Agreed. The notion of an aliasingExternal will be removed in the next revision, because, in implementing interprocedural analysis (coming soon to a code review near you), a more generic approach was necessary. I haven't quite settled on a name for it yet, so if you have any suggestions for names of properties that are transitive in the "low" direction, I'd be happy to hear them. :)

Why only update start here? ...

It only updated start because doing so was correct and simple to code. I see your point though, so I swapped over to updating everything.

[• gbiv]

Modified data structures to support interprocedural analysis.

In more specific terms:

Added set relationship data (aboveness/belowness) into StratifiedSets
Expanded aliasExternals to a more generic "Attributes"/"Attrs" type, so we can more accurately express whether uncertainty is coming from arguments or globals
We now remove sets that have been remapped at build-time so we conserve as much space as possible, because now the space penalty of letting a "remapped" set slip passed build time has gone up from a single bit (field in aliasingExternals bitset) to ~12 bytes.

[• dberlin]

Looks good to me, modulo one issue, but you should wait for Nick or
Hal to give you a final okay.

I know both are busy, so it may be a bit.

As for my last comment on this one:

The attributes mechanism is not entirely well described.
If the data structure is meant to truly be independent of the Aliasing
related stuff, then your description should just be "these are
attributes that builders may use for various purposes. The semantics
are <x> on merging". or something similar.
If they aren't independent, it probably pays to give them a bit more
thought and structure, but i don't think that's worth the time quite
yet, until we know more about which end up useful/don't (IE whether
you want additional attributes"

[• gbiv]

+Personal account (internship ends on Friday)

Addressed dberlin's feedback + fixed a merging bug/renamed some attribute-related methods.

[nlewycky]

For StratifiedSets, I need more documentation (*cough* or to read the paper) in order to continue reviewing it.

WeightedBidirectedGraph.h looks good to me, though I'd prefer "Bidirectional" (optional).

lib/Analysis/StratifiedSets.h

10

Missing high-level conceptual description of stratified sets.

38

Period to end complete sentence.

Also, the reader is left wondering what attributes are and why it should contain 32?

172–174

Extra space between then and recursively.
Extra space between below and %a.
Extra space between would and end.

339

propogateAttrs -> propagateAttrs

390

These methods need docstrings.

397

To check my understanding, this is what causes a cycle (attempting to insert A above B given that B is already above A) to be flattened into a single, uh, "stratus"?

lib/Analysis/WeightedBidirectedGraph.h

2

"Bidirected"? Bidirectional?

2

I'm not convinced this should be pulled out of CFL Alias Analysis.

LLVM's graph infrastructure has:
a) generic algorithms that operate over child_begin/child_end iterators
b) wrappers that are constructed from other objects and provide child_begin/end.
Sometimes the wrappers in (b) are null wrappers the implementation of the graph APIs are intrusive upon the underlying classes.

This doesn't fit that model at all, this is a graph data type. If this needs to exist at all (ie., we can't lazily construct it from other objects we have handy like the IR) then it should be local to CFLAliasAnalysis. That could mean creating a new CFGAlias directory to put this file in.

[hfinkel]

This is looks pretty good. Once the comments from the others reviewers are addressed, I think this can go in.

lib/Analysis/StratifiedSets.h

196

Don't break the line here.

lib/Analysis/WeightedBidirectedGraph.h

2

I agree. It is also not that big and could probably just go into the main source file too.

[george.burgess.iv]

Commandeering to abandon; this went in a long time ago as part of D5106.

lib/Analysis/StratifiedSets.h

+//===- StratifiedSets.h - Abstract stratified sets implementation. --------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ADT_STRATIFIEDSETS_H
+#define LLVM_ADT_STRATIFIEDSETS_H
+
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/Optional.h"
+#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/SmallSet.h"
+#include "llvm/ADT/SmallVector.h"
+#include <bitset>
+#include <cassert>
+#include <cmath>
+#include <limits>
+#include <type_traits>
+#include <vector>
+
+namespace llvm {
+// \brief An index into Stratified Sets.
+typedef unsigned StratifiedIndex;
+// NOTE: ^ This can't be a short -- bootstrapping clang has a case where
+// ~1M sets exist.
+
+// \brief Container of information related to a value in a StratifiedSet.
+struct StratifiedInfo {
+  StratifiedIndex Index;
+  // For field sensitivity, etc. we can tack attributes on to this struct.
+};
+
+// The number of attributes that StratifiedAttrs should contain
+static constexpr unsigned NumStratifiedAttrs = 32;
+// StratifiedLinks need to carry attributes with them. Because they're used so
+// often, this was lifted from StratifiedLink and given a name.
+typedef std::bitset<NumStratifiedAttrs> StratifiedAttrs;
+
+// \brief A "link" between two StratifiedSets.
+struct StratifiedLink {
+  // \brief This is a value used to signify "does not exist" where
+  // the StratifiedIndex type is used. This is used instead of
+  // Optional<StratifiedIndex> because Optional<StratifiedIndex> would
+  // eat up a considerable amount of extra memory, after struct
+  // padding/alignment is taken into account.
+  static constexpr auto SetSentinel =
+      std::numeric_limits<StratifiedIndex>::max();
+
+  // \brief The index for the set "above" current
+  StratifiedIndex Above;
+  // \brief The link for the set "below" current
+  StratifiedIndex Below;
+  // \brief Attributes that have to do with values external to the current
+  // function. Please note that each bit set in the `externals` above one set
+  // *will* be set in all `externals` in sets below the current one.
+  StratifiedAttrs Attrs;
+
+  StratifiedLink() : Above(SetSentinel), Below(SetSentinel) {}
+
+  bool hasBelow() const { return Below != SetSentinel; }
+  bool hasAbove() const { return Above != SetSentinel; }
+
+  void clearBelow() { Below = SetSentinel; }
+  void clearAbove() { Above = SetSentinel; }
+};
+
+// \brief These are stratified sets, as described in "Fast algorithms for
+// Dyck-CFL-reachability with applications to Alias Analysis" by Zhang Q, Lyu M
+// R, Yuan H, and Su Z. -- in short, this is meant to represent different sets
+// of Value*s. If two Value*s are in the same set, or if both sets have the
+// aliasingAttrs attribute, then the Value*s are considered to potentially
+// alias. Otherwise, they are not.
+template <typename T> class StratifiedSets {
+public:
+  StratifiedSets() {}
+
+  StratifiedSets(DenseMap<T, StratifiedInfo> Map,
+                 std::vector<StratifiedLink> Links)
+      : Values(std::move(Map)), Links(std::move(Links)) {}
+
+  StratifiedSets(StratifiedSets<T> &&Other) { *this = std::move(Other); }
+
+  StratifiedSets &operator=(StratifiedSets<T> &&Other) {
+    Values = std::move(Other.Values);
+    Links = std::move(Other.Links);
+    return *this;
+  }
+
+  Optional<StratifiedInfo> find(const T &Elem) const {
+    auto Iter = Values.find(Elem);
+    if (Iter == Values.end()) {
+      return NoneType();
+    }
+    return Iter->second;
+  }
+
+  const StratifiedLink &getLink(StratifiedIndex Index) const {
+    assert(inbounds(Index));
+    return Links[Index];
+  }
+
+private:
+  DenseMap<T, StratifiedInfo> Values;
+  std::vector<StratifiedLink> Links;
+
+  bool inbounds(StratifiedIndex Idx) const { return Idx < Links.size(); }
+};
+
+// \brief Generic Builder class that produces StratifiedSets instances.
+//
+// The goal of this builder is to efficiently produce correct StratifiedSets
+// instances. To this end, we use a few tricks:
+//   > Set chains (A method for linking sets together)
+//   > Set remaps (A method for marking a set as an alias [irony?] of another)
+//
+// ==== Set chains ====
+// This builder has a notion of some value A being above, below, or with some
+// other value B:
+//   > The `A above B` relationship implies that there is a reference edge going
+//   from A to B. Namely, it notes that A can store anything in B's set.
+//   > The `A below B` relationship is the opposite of `A above B`. It implies
+//   that there's a dereference edge going from A to B.
+//   > The `A with B` relationship states that there's an assignment edge going
+//   from A to B, and that A and B should be treated as equals.
+//
+// As an example, take the following code snippet:
+//
+// %a = alloca i32, align 4
+// %ap = alloca i32*, align 8
+// %app = alloca i32**, align 8
+// store %a, %ap
+// store %ap, %app
+// %aw = getelementptr %ap, 0
+//
+// Given this, the follow relations exist:
+//   - %a below %ap & %ap above %a
+//   - %ap below %app & %app above %ap
+//   - %aw with %ap & %ap with %aw
+//
+// These relations produce the following sets:
+//   [{%a}, {%ap, %aw}, {%app}]
+//
+// ...Which states that the only MayAlias relationship in the above program is
+// between %ap and %aw.
+//
+// Life gets more complicated when we actually have logic in our programs. So,
+// we either must remove this logic from our programs, or make consessions for
+// it in our AA algorithms. In this case, we have decided to select the latter
+// option.
+//
+// First complication: Conditionals
+// Motivation:
+//  %ad = alloca int, align 4
+//  %a = alloca int*, align 8
+//  %b = alloca int*, align 8
+//  %bp = alloca int**, align 8
+//  %c = call i1 @SomeFunc()
+//  %k = select %c, %ad, %bp
+//  store %ad, %a
+//  store %b, %bp
+//
+// %k has 'with' edges to both %a and %b, which ordinarily would not be linked
+// together. So, we merge the set that contains %a with the set that contains
+// %b. We then  recursively merge the set above %a with the set above %b, and
+// the set below  %a with the set below %b, etc. Ultimately, the sets for this
+// program would  end up like:  {%ad}, {%a, %b, %k}, {%bp}, where {%ad} is below
+// {%a, %b, %c} is below {%ad}.
+//
+// Second complication: Arbitrary casts
+// Motivation:
+//  %ip = alloca int*, align 8
+//  %ipp = alloca int**, align 8
+//  %i = bitcast ipp to int
+//  store %ip, %ipp
+//  store %i, %ip
+//
+// This is impossible to construct with any of the rules above, because a set
+// containing both {%i, %ipp} is supposed to exist, the set with %i is supposed
+// to be below the set with %ip, and the set with %ip is supposed to be below
+// the set with %ipp. Because we don't allow circular relationships like this,
+// we merge all concerned sets into one. So, the above code would generate a
+// single StratifiedSet: {%ip, %ipp, %i}.
+//
+// ==== Set remaps ====
+// More of an implementation detail than anything -- when merging sets, we need
+// to update the numbers of all of the elements mapped to those sets. Rather
+// than doing this at each merge, we note in the BuilderLink structure that a
+// remap
+// has occurred, and use this information so we can defer renumbering set
+// elements until build time.
+template <typename T> class StratifiedSetsBuilder {
+  // \brief Represents a Stratified Set, with information about the Stratified
+  // Set above it, the set below it, and whether the current set has been
+  // remapped to another.
+  struct BuilderLink {
+    const StratifiedIndex Number;
+
+    BuilderLink(StratifiedIndex N) : Number(N) {
+      Remap = StratifiedLink::SetSentinel;
+    }
+
+    bool hasAbove() const {
+      assert(!isRemapped());
+      return Link.hasAbove();
+    }
+
+    bool hasBelow() const {
+      assert(!isRemapped());
+      return Link.hasBelow();
+    }
+
+    void setBelow(StratifiedIndex I) {
+      assert(!isRemapped());
+      Link.Below = I;
+    }
+
+    void setAbove(StratifiedIndex I) {
+      assert(!isRemapped());
+      Link.Above = I;
+    }
+
+    void clearBelow() {
+      assert(!isRemapped());
+      Link.clearBelow();
+    }
+
+    void clearAbove() {
+      assert(!isRemapped());
+      Link.clearAbove();
+    }
+
+    StratifiedIndex getBelow() const {
+      assert(!isRemapped());
+      assert(hasBelow());
+      return Link.Below;
+    }
+
+    StratifiedIndex getAbove() const {
+      assert(!isRemapped());
+      assert(hasAbove());
+      return Link.Above;
+    }
+
+    StratifiedAttrs &getAttrs() {
+      assert(!isRemapped());
+      return Link.Attrs;
+    }
+
+    void setAttr(unsigned index) {
+      assert(!isRemapped());
+      assert(index < NumStratifiedAttrs);
+      Link.Attrs.set(index);
+    }
+
+    void addAttrs(const StratifiedAttrs &other) {
+      assert(!isRemapped());
+      Link.Attrs |= other;
+    }
+
+    bool isRemapped() const { return Remap != StratifiedLink::SetSentinel; }
+
+    // \brief For initial remapping to another set
+    void remapTo(StratifiedIndex Other) {
+      assert(!isRemapped());
+      Remap = Other;
+    }
+
+    StratifiedIndex getRemapIndex() const {
+      assert(isRemapped());
+      return Remap;
+    }
+
+    // \brief Should only be called when we're already remapped.
+    void updateRemap(StratifiedIndex Other) {
+      assert(isRemapped());
+      Remap = Other;
+    }
+
+    // \brief Prefer the above functions to calling things directly on what's
+    // returned from this -- they guard against unexpected calls when the
+    // current BuilderLink is remapped.
+    const StratifiedLink &getLink() const { return Link; }
+
+  private:
+    StratifiedLink Link;
+    StratifiedIndex Remap;
+  };
+
+  // \brief This function performs all of the set unioning/value renumbering
+  // that we've been putting off, and generates a vector<StratifiedLink> that
+  // may be placed in a StratifiedSets instance.
+  void finalizeSets(std::vector<StratifiedLink> &StratLinks) {
+    DenseMap<StratifiedIndex, StratifiedIndex> Remaps;
+    for (auto &Link : Links) {
+      if (Link.isRemapped()) {
+        continue;
+      }
+
+      StratifiedIndex Number = StratLinks.size();
+      Remaps.insert({Link.Number, Number});
+      StratLinks.push_back(Link.getLink());
+    }
+
+    for (auto &Link : StratLinks) {
+      if (Link.hasAbove()) {
+        auto &Above = linksAt(Link.Above);
+        auto Iter = Remaps.find(Above.Number);
+        assert(Iter != Remaps.end());
+        Link.Above = Iter->second;
+      }
+
+      if (Link.hasBelow()) {
+        auto &Below = linksAt(Link.Below);
+        auto Iter = Remaps.find(Below.Number);
+        assert(Iter != Remaps.end());
+        Link.Below = Iter->second;
+      }
+    }
+
+    for (auto &Pair : Values) {
+      auto &Info = Pair.second;
+      auto &Link = linksAt(Info.Index);
+      auto Iter = Remaps.find(Link.Number);
+      assert(Iter != Remaps.end());
+      Info.Index = Iter->second;
+    }
+  }
+
+  // \brief There's a guarantee in StratifiedLink where all bits set in a
+  // Link.externals will be set in all Link.externals "below" it.
+  static void propogateAttrs(std::vector<StratifiedLink> &Links) {
+    const auto getHighestParentAbove = [&Links](StratifiedIndex Idx) {
+      const auto *Link = &Links[Idx];
+      while (Link->hasAbove()) {
+        Idx = Link->Above;
+        Link = &Links[Idx];
+      }
+      return Idx;
+    };
+
+    SmallSet<StratifiedIndex, 16> Visited;
+    for (unsigned I = 0, E = Links.size(); I < E; ++I) {
+      auto CurrentIndex = getHighestParentAbove(I);
+      if (!Visited.insert(CurrentIndex)) {
+        continue;
+      }
+
+      while (Links[CurrentIndex].hasBelow()) {
+        auto &CurrentBits = Links[CurrentIndex].Attrs;
+        auto NextIndex = Links[CurrentIndex].Below;
+        auto &NextBits = Links[NextIndex].Attrs;
+        NextBits |= CurrentBits;
+        CurrentIndex = NextIndex;
+      }
+    }
+  }
+
+public:
+  // \brief Builds a StratifiedSet from the information we've been given since
+  // either construction or the prior build() call.
+  StratifiedSets<T> build() {
+    std::vector<StratifiedLink> StratLinks;
+    finalizeSets(StratLinks);
+    propogateAttrs(StratLinks);
+    Links.clear();
+    return StratifiedSets<T>(std::move(Values), std::move(StratLinks));
+  }
+
+  std::size_t size() const { return Values.size(); }
+  std::size_t numSets() const { return Links.size(); }
+
+  bool has(const T &Elem) const { return get(Elem).hasValue(); }
+
+  bool add(const T &Main) {
+    if (get(Main).hasValue())
+      return false;
+
+    auto NewIndex = getNewUnlinkedIndex();
+    return addAtMerging(Main, NewIndex);
+  }
+
+  bool addAbove(const T &Main, const T &ToAdd) {
+    assert(has(Main));
+    auto Index = *indexOf(Main);
+    if (!linksAt(Index).hasAbove())
+      addLinkAbove(Index);
+
+    auto Above = linksAt(Index).getAbove();
+    return addAtMerging(ToAdd, Above);
+  }
+
+  bool addBelow(const T &Main, const T &ToAdd) {
+    assert(has(Main));
+    auto Index = *indexOf(Main);
+    if (!linksAt(Index).hasBelow())
+      addLinkBelow(Index);
+
+    auto Below = linksAt(Index).getBelow();
+    return addAtMerging(ToAdd, Below);
+  }
+
+  bool addWith(const T &Main, const T &ToAdd) {
+    assert(has(Main));
+    auto MainIndex = *indexOf(Main);
+    return addAtMerging(ToAdd, MainIndex);
+  }
+
+  void noteAttribute(const T &Main, unsigned AttrNum) {
+    assert(has(Main));
+    assert(AttrNum < StratifiedLink::SetSentinel);
+    auto *Info = *get(Main);
+    auto &Link = linksAt(Info->Index);
+    Link.setAttr(AttrNum);
+  }
+
+  void noteAttributes(const T &Main, const StratifiedAttrs &NewAttrs) {
+    assert(has(Main));
+    auto *Info = *get(Main);
+    auto &Link = linksAt(Info->Index);
+    Link.addAttrs(NewAttrs);
+  }
+
+  bool getAttribute(const T &Main, unsigned AttrNum) const {
+    assert(has(Main));
+    assert(AttrNum < StratifiedLink::SetSentinel);
+    auto *Info = *get(Main);
+    auto &Link = linksAt(Info->Index);
+    auto &Attrs = Link.getAttrs();
+    return Attrs[AttrNum];
+  }
+
+  StratifiedAttrs getAttributes(const T &Main) const {
+    assert(has(Main));
+    auto *Info = *get(Main);
+    auto &Link = linksAt(Info->Index);
+    return Link.getAttrs();
+  }
+
+private:
+  DenseMap<T, StratifiedInfo> Values;
+  std::vector<BuilderLink> Links;
+
+  // \brief Adds the given element at the given index, merging sets if
+  // necessary.
+  bool addAtMerging(const T &ToAdd, StratifiedIndex Index) {
+    StratifiedInfo Info = {Index};
+    auto Pair = Values.insert({ToAdd, Info});
+    if (Pair.second)
+      return true;
+
+    auto &Iter = Pair.first;
+    auto &IterSet = linksAt(Iter->second.Index);
+    auto &ReqSet = linksAt(Index);
+
+    // Failed to add where we wanted to. Merge the sets.
+    if (&IterSet != &ReqSet)
+      merge(IterSet.Number, ReqSet.Number);
+
+    return false;
+  }
+
+  // \brief Gets the BuilderLink at the given index, taking set remapping into
+  // account.
+  BuilderLink &linksAt(StratifiedIndex Index) {
+    auto *Start = &Links[Index];
+    if (!Start->isRemapped())
+      return *Start;
+
+    auto *Current = Start;
+    while (Current->isRemapped())
+      Current = &Links[Current->getRemapIndex()];
+
+    auto NewRemap = Current->Number;
+
+    // Run through everything that has yet to be updated, and update them to
+    // remap to NewRemap
+    Current = Start;
+    while (Current->isRemapped()) {
+      auto *Next = &Links[Current->getRemapIndex()];
+      Current->updateRemap(NewRemap);
+      Current = Next;
+    }
+
+    return *Current;
+  }
+
+  // \brief Merges two sets into one another. Assumes that these sets are not
+  // already one in the same
+  void merge(StratifiedIndex Idx1, StratifiedIndex Idx2) {
+    assert(inbounds(Idx1) && inbounds(Idx2));
+    assert(&linksAt(Idx1) != &linksAt(Idx2) &&
+           "Merging a set into itself is not allowed");
+
+    // CASE 1: If the set at `Idx1` is above or below `Idx2`, we need to merge
+    // both the
+    // given sets, and all sets between them, into one.
+    if (tryMergeUpwards(Idx1, Idx2))
+      return;
+
+    if (tryMergeUpwards(Idx2, Idx1))
+      return;
+
+    // CASE 2: The set at `Idx1` is not in the same chain as the set at `Idx2`.
+    // We therefore need to merge the two chains together.
+    mergeDirect(Idx1, Idx2);
+  }
+
+  // \brief Merges two sets assuming that the set at `Idx1` is unreachable from
+  // traversing above or below the set at `Idx2`.
+  void mergeDirect(StratifiedIndex Idx1, StratifiedIndex Idx2) {
+    assert(inbounds(Idx1) && inbounds(Idx2));
+    assert(!Links[Idx1].isRemapped() && !Links[Idx2].isRemapped());
+
+    // Merging strategy:
+    //  > If neither has links above, stop.
+    //  > If only `LinksInto` has links above, stop.
+    //  > If only `LinksFrom` has links above, reset `LinksInto.Above` to
+    //  match `LinksFrom.Above`
+    //  > If both have links in some direction, deal with those next.
+    auto *LinksInto = &linksAt(Idx1);
+    auto *LinksFrom = &linksAt(Idx2);
+    while (true) {
+      auto &IntoAttrs = LinksInto->getAttrs();
+      IntoAttrs |= LinksFrom->getAttrs();
+
+      if (!LinksFrom->hasAbove())
+        break;
+
+      if (!LinksInto->hasAbove()) {
+        LinksInto->setAbove(LinksFrom->getAbove());
+        auto &NewAbove = linksAt(LinksInto->getAbove());
+        NewAbove.setBelow(LinksInto->Number);
+        break;
+      }
+
+      LinksFrom->remapTo(LinksInto->Number);
+    }
+
+    LinksInto = &linksAt(Idx1);
+    LinksFrom = &linksAt(Idx2);
+    while (true) {
+      auto &IntoAttrs = LinksInto->getAttrs();
+      IntoAttrs |= LinksFrom->getAttrs();
+
+      if (!LinksFrom->hasBelow())
+        break;
+
+      if (!LinksInto->hasBelow()) {
+        LinksInto->setBelow(LinksFrom->getBelow());
+        auto &NewBelow = linksAt(LinksInto->getBelow());
+        NewBelow.setBelow(LinksInto->Number);
+        break;
+      }
+
+      LinksFrom->remapTo(LinksInto->Number);
+    }
+  }
+
+  // \brief Checks to see if lowerIndex is at a level lower than upperIndex.
+  // If so, it will merge lowerIndex with upperIndex (and all of the sets
+  // between) and return true. Otherwise, it will return false.
+  bool tryMergeUpwards(StratifiedIndex LowerIndex, StratifiedIndex UpperIndex) {
+    assert(inbounds(LowerIndex) && inbounds(UpperIndex));
+    auto *Lower = &linksAt(LowerIndex);
+    auto *Upper = &linksAt(UpperIndex);
+    if (Lower == Upper)
+      return true;
+
+    SmallVector<BuilderLink *, 8> Found;
+    auto *Current = Lower;
+    auto Attrs = Current->getAttrs();
+    while (Current->hasAbove() && Current != Upper) {
+      Found.push_back(Current);
+      auto &CurrentAttrs = Current->getAttrs();
+      Attrs |= CurrentAttrs;
+      auto AboveIndex = Current->getAbove();
+      Current = &linksAt(AboveIndex);
+    }
+
+    if (Current != Upper)
+      return false;
+
+    auto &UpperAttrs = Upper->getAttrs();
+    UpperAttrs |= Attrs;
+
+    if (Lower->hasBelow()) {
+      auto NewBelowIndex = Lower->getBelow();
+      Upper->setBelow(NewBelowIndex);
+      auto &NewBelow = linksAt(NewBelowIndex);
+      NewBelow.setAbove(UpperIndex);
+    } else {
+      Upper->clearBelow();
+    }
+
+    for (const auto &Ptr : Found)
+      Ptr->remapTo(Upper->Number);
+
+    return true;
+  }
+
+  Optional<const StratifiedInfo *> get(const T &Val) const {
+    auto Result = Values.find(Val);
+    if (Result == Values.end())
+      return NoneType();
+    return &Result->second;
+  }
+
+  Optional<StratifiedInfo *> get(const T &Val) {
+    auto Result = Values.find(Val);
+    if (Result == Values.end())
+      return NoneType();
+    return &Result->second;
+  }
+
+  Optional<StratifiedIndex> indexOf(const T &Val) {
+    auto MaybeVal = get(Val);
+    if (!MaybeVal.hasValue())
+      return NoneType();
+    auto *Info = *MaybeVal;
+    auto &Link = linksAt(Info->Index);
+    return Link.Number;
+  }
+
+  StratifiedIndex addLinkBelow(StratifiedIndex Set) {
+    auto At = addLinks();
+    Links[Set].setBelow(At);
+    Links[At].setAbove(Set);
+    return At;
+  }
+
+  StratifiedIndex addLinkAbove(StratifiedIndex Set) {
+    auto At = addLinks();
+    Links[At].setBelow(Set);
+    Links[Set].setAbove(At);
+    return At;
+  }
+
+  StratifiedIndex getNewUnlinkedIndex() { return addLinks(); }
+
+  StratifiedIndex addLinks() {
+    auto Link = Links.size();
+    Links.push_back(BuilderLink(Link));
+    return Link;
+  }
+
+  bool inbounds(StratifiedIndex N) const { return N >= 0 && N < Links.size(); }
+};
+}
+#endif // LLVM_ADT_STRATIFIEDSETS_H

lib/Analysis/WeightedBidirectedGraph.h

+//===- WeightedBidirectedGraph.h - Abstract weighted, bidirected graph. ---===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ADT_WEIGHTEDBIDIRECTEDGRPAH_H
+#define LLVM_ADT_WEIGHTEDBIDIRECTEDGRPAH_H
+
+#include "llvm/ADT/Optional.h"
+#include <limits>
+#include <tuple>
+#include <vector>
+
+namespace llvm {
+// \brief A weighted bidirected graph made for use with the CFL Alias Analysis
+// implementation.
+template <typename EdgeWeightT> class WeightedBidirectedGraph {
+public:
+  typedef std::size_t Node;
+
+private:
+  constexpr static Node StartNode = Node(0);
+
+  struct Edge {
+    EdgeWeightT Weight;
+    Node Other;
+
+    bool operator==(const Edge &E) const {
+      return Weight == E.Weight && Other == E.Other;
+    }
+
+    bool operator!=(const Edge &E) const { return !operator==(E); }
+  };
+
+  struct NodeImpl {
+    std::vector<Edge> Edges;
+  };
+
+  std::vector<NodeImpl> NodeImpls;
+
+  bool inbounds(Node NodeIndex) const { return NodeIndex < NodeImpls.size(); }
+
+  const NodeImpl &getNode(Node N) const { return NodeImpls[N]; }
+  NodeImpl &getNode(Node N) { return NodeImpls[N]; }
+
+public:
+  // ----- Various Edge iterators for the graph ----- //
+
+  // \brief Iterator for edges. Because this graph is bidirected, we don't
+  // allow modificaiton of the edges using this iterator. Additionally, the
+  // iterator becomes invalid if you add edges to or from the node you're
+  // getting the edges of.
+  struct EdgeIterator : public std::iterator<std::forward_iterator_tag,
+                                             std::tuple<EdgeWeightT, Node *>> {
+    EdgeIterator(const typename std::vector<Edge>::const_iterator &Iter)
+        : Current(Iter) {}
+
+    EdgeIterator(NodeImpl &Impl) : Current(Impl.begin()) {}
+
+    EdgeIterator &operator++() {
+      ++Current;
+      return *this;
+    }
+
+    EdgeIterator operator++(int) {
+      EdgeIterator Copy(Current);
+      operator++();
+      return Copy;
+    }
+
+    std::tuple<EdgeWeightT, Node> &operator*() {
+      Store = std::make_tuple(Current->Weight, Current->Other);
+      return Store;
+    }
+
+    bool operator==(const EdgeIterator &Other) const {
+      return Current == Other.Current;
+    }
+
+    bool operator!=(const EdgeIterator &Other) const {
+      return !operator==(Other);
+    }
+
+  private:
+    typename std::vector<Edge>::const_iterator Current;
+    std::tuple<EdgeWeightT, Node> Store;
+  };
+
+  // Wrapper for EdgeIterator with begin()/end() calls.
+  struct EdgeIterable {
+    EdgeIterable(const std::vector<Edge> &Edges)
+        : BeginIter(Edges.begin()), EndIter(Edges.end()) {}
+
+    EdgeIterator begin() { return EdgeIterator(BeginIter); }
+
+    EdgeIterator end() { return EdgeIterator(EndIter); }
+
+  private:
+    typename std::vector<Edge>::const_iterator BeginIter;
+    typename std::vector<Edge>::const_iterator EndIter;
+  };
+
+  // ----- Actual graph-related things ----- //
+
+  WeightedBidirectedGraph() = default;
+
+  WeightedBidirectedGraph(WeightedBidirectedGraph<EdgeWeightT> &&Other)
+      : NodeImpls(std::move(Other.NodeImpls)) {}
+
+  WeightedBidirectedGraph<EdgeWeightT> &
+  operator=(WeightedBidirectedGraph<EdgeWeightT> &&Other) {
+    NodeImpls = std::move(Other.NodeImpls);
+    return *this;
+  }
+
+  Node addNode() {
+    auto Index = NodeImpls.size();
+    auto NewNode = Node(Index);
+    NodeImpls.push_back(NodeImpl());
+    return NewNode;
+  }
+
+  void addEdge(Node From, Node To, const EdgeWeightT &Weight,
+               const EdgeWeightT &ReverseWeight) {
+    assert(inbounds(From));
+    assert(inbounds(To));
+    auto &FromNode = getNode(From);
+    auto &ToNode = getNode(To);
+    FromNode.Edges.push_back(Edge{Weight, To});
+    ToNode.Edges.push_back(Edge{ReverseWeight, From});
+  }
+
+  EdgeIterable edgesFor(const Node &N) const {
+    const auto &Node = getNode(N);
+    return EdgeIterable(Node.Edges);
+  }
+
+  bool empty() const { return NodeImpls.empty(); }
+  std::size_t size() const { return NodeImpls.size(); }
+
+  // \brief Gets an arbitrary node in the graph as a starting point for
+  // traversal.
+  Node getEntryNode() {
+    assert(inbounds(StartNode));
+    return StartNode;
+  }
+};
+}
+
+#endif // LLVM_ADT_WEIGHTEDBIDIRECTEDGRPAH_H