[CFLAA] Simplify CFLGraphBuilder by removing InstantiatedRelations and InstantiatedAttrs

[grievejia]

Summary

This is a code cleanup patch. No functionality change is introduced. It concludes the efforts of moving all information from the auxiliary data structures in CFLGraphBuilder into the constructed CFLGraph.

To achieve the aforementioned goal, I changed the node type of CFLGraph from Value* to (Value*, DerefLevel) pair. With the change of node type, CFLGraph is now able to represent concepts like "derference value x 3 times", therefore it doesn't need InstantiatedRelations and InstantiatedAttrs any more to hold the information we get from interprocedural analysis.

Another change I made to the CFLGraph is that I tried to group together all nodes that share the same Value*. Also, there's no need to explicit store Reference/Dereference edges because we know that it is always going to be the case that there exists a reference edge from (X, I) to (X, I-1) and a dereference edge form (X, I) to (X, I+1). For the purpose of consistency we disallow any other forms of reference/dereference edges. As a result, walking through a dereference chain becomes a fairly easy job (which is useful for implementing CFLAnders). I'm not satisfied with the API to perform the walkthrough, but I can't come up with a better alternative without making things less efficient.

The patch deprecates our previous hacks on StratifiedSets: noteAttributeBelow() and addBelowWith() is no longer needed, as we can take care of it at CFLGraph level. It also reveals another problem hidden in StratifiedSets::mergeDirect(): when it tries to merge two sets and neither set has anything up/below it, the attributes of those two sets won't get merged. Not sure if this is intentional or not. I added a line there to make sure the attribute merge is guaranteed.

[grievejia]

Changed the offset type from Optional<int> to int

[grievejia]

Changed CFLGraph from bidirectional to unidirectional since the former doesn't seem to buy us that much.

[george.burgess.iv]

As always, thanks for the patch!

lib/Analysis/CFLGraph.h

42

Can you talk about the purpose of Offset, please? It looks like it's unused, and only ever has a value of 0. Will this change in the future, or am I missing something?

54

Redundant private

62

Can this just be Levels.resize(Level+1)?

89

Please merge this with the condition above

97

This, too

164

Is there a reason we have separate sets for globals vs constants?

192

Why can't we just say if (!Graph.addNode({Val, 0}) return; (here and for the CExpr case)?

194

It looks like addNode(Foo) + addAttr(Foo, A) is a common pattern. Maybe we could either add a WithAttrs param (or whatever) to addNode, or make an addNodeWithAttrs method, so we don't need to do redundant lookups?

209

If Val turns out to be a global or constant expression, it seems mildly redundant to add it (or see that we've already added it) in checkGlobalOrCExpr, then try to re-add it below.

Also, given its uses, I think addGlobalOrCExpr may be a better name. :)

218

And here

221

And here

392

Is there a case where we add non-pointer types to the graph? If not, can we either add assert(isPointerTy) to addNode, or add this logic into addNode?

It looks like it's really easy to miss a type check at the moment. :/

lib/Analysis/CFLSteensAliasAnalysis.cpp

203

s/mapping/Mapping

[grievejia]

lib/Analysis/CFLGraph.h

42

It is intended for future usage.

But I think you had a point that it's confusing to put an unused field here. Let me remove it for now and add it back in a separate patch.

[grievejia]

Style fixes.

[george.burgess.iv]

LGTM after a few more nits. Thanks again!

lib/Analysis/CFLGraph.h

111

s/changed/Changed/ (aren't naming conventions fun?)

203–205

Please remove this function

513

Please swap this to addNode(value, attr)

517

This, too

[grievejia]

More style fixes

[grievejia]

As always, thanks for the comments!

lib/Analysis/AliasAnalysisSummary.h

 /// Currently, all CFL-based alias analyses adopt the summary-based approach
 /// and therefore heavily rely on this header.
 ///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ANALYSIS_ALIASANALYSISSUMMARY_H
 #define LLVM_ANALYSIS_ALIASANALYSISSUMMARY_H
 
+#include "llvm/ADT/DenseMapInfo.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/IR/CallSite.h"
 #include <bitset>
 
 namespace llvm {
 namespace cflaa {
 

 /// callsite
 struct InstantiatedAttr {
   InstantiatedValue IValue;
   AliasAttrs Attr;
 };
 Optional<InstantiatedAttr> instantiateExternalAttribute(ExternalAttribute,
                                                         CallSite);
 }
+
+template <> struct DenseMapInfo<cflaa::InstantiatedValue> {
+  static inline cflaa::InstantiatedValue getEmptyKey() {
+    return cflaa::InstantiatedValue{DenseMapInfo<Value *>::getEmptyKey(),
+                                    DenseMapInfo<unsigned>::getEmptyKey()};
+  }
+  static inline cflaa::InstantiatedValue getTombstoneKey() {
+    return cflaa::InstantiatedValue{DenseMapInfo<Value *>::getTombstoneKey(),
+                                    DenseMapInfo<unsigned>::getTombstoneKey()};
+  }
+  static unsigned getHashValue(const cflaa::InstantiatedValue &IV) {
+    return DenseMapInfo<std::pair<Value *, unsigned>>::getHashValue(
+        std::make_pair(IV.Val, IV.DerefLevel));
+  }
+  static bool isEqual(const cflaa::InstantiatedValue &LHS,
+                      const cflaa::InstantiatedValue &RHS) {
+    return LHS.Val == RHS.Val && LHS.DerefLevel == RHS.DerefLevel;
+  }
+};
 }
 
 #endif

lib/Analysis/CFLGraph.h

 /// alias analysis.
 ///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ANALYSIS_CFLGRAPH_H
 #define LLVM_ANALYSIS_CFLGRAPH_H
 
 #include "AliasAnalysisSummary.h"
-#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/Analysis/MemoryBuiltins.h"
 #include "llvm/IR/InstVisitor.h"
 #include "llvm/IR/Instructions.h"
 
 namespace llvm {
 namespace cflaa {
-/// Edges can be one of four "weights" -- each weight must have an inverse
-/// weight (Assign has Assign; Reference has Dereference).
-enum class EdgeType {
-  /// The weight assigned when assigning from or to a value. For example, in:
-  /// %b = getelementptr %a, 0
-  /// ...The relationships are %b assign %a, and %a assign %b. This used to be
-  /// two edges, but having a distinction bought us nothing.
-  Assign,
-
-  /// The edge used when we have an edge going from some handle to a Value.
-  /// Examples of this include:
-  /// %b = load %a              (%b Dereference %a)
-  /// %b = extractelement %a, 0 (%a Dereference %b)
-  Dereference,
-
-  /// The edge used when our edge goes from a value to a handle that may have
-  /// contained it at some point. Examples:
-  /// %b = load %a              (%a Reference %b)
-  /// %b = extractelement %a, 0 (%b Reference %a)
-  Reference
-};
 
 /// \brief The Program Expression Graph (PEG) of CFL analysis
 /// CFLGraph is auxiliary data structure used by CFL-based alias analysis to
 /// describe flow-insensitive pointer-related behaviors. Given an LLVM function,
 /// the main purpose of this graph is to abstract away unrelated facts and
 /// translate the rest into a form that can be easily digested by CFL analyses.
+/// Each Node in the graph is an InstantiatedValue, and each edge represent a
+/// pointer assignment between InstantiatedValue. Pointer
+/// references/dereferences are not explicitly stored in the graph: we
+/// implicitly assume that for each node (X, I) it has a dereference edge to (X,
+/// I+1) and a reference edge to (X, I-1).
 class CFLGraph {
-  typedef Value *Node;
+public:
+  typedef InstantiatedValue Node;
 
   struct Edge {
-    EdgeType Type;
+    int64_t Offset;
     Node Other;
   };
 
   typedef std::vector<Edge> EdgeList;
 
   struct NodeInfo {
     EdgeList Edges;
     AliasAttrs Attr;
   };
 
-  typedef DenseMap<Node, NodeInfo> NodeMap;
-  NodeMap NodeImpls;
+  class ValueInfo {
+  private:
+    std::vector<NodeInfo> Levels;
 
-  // Gets the inverse of a given EdgeType.
-  static EdgeType flipWeight(EdgeType Initial) {
-    switch (Initial) {
-    case EdgeType::Assign:
-      return EdgeType::Assign;
-    case EdgeType::Dereference:
-      return EdgeType::Reference;
-    case EdgeType::Reference:
-      return EdgeType::Dereference;
+  public:
+    bool addNodeToLevel(unsigned Level) {
+      auto NumLevels = Levels.size();
+      if (NumLevels > Level)
+        return false;
+      while (NumLevels <= Level) {
+        Levels.push_back(NodeInfo{EdgeList(), AliasAttrs()});
+        ++NumLevels;
       }
-    llvm_unreachable("Incomplete coverage of EdgeType enum");
+      return true;
     }
 
+    NodeInfo &getNodeInfoAtLevel(unsigned Level) {
+      assert(Level < Levels.size());
+      return Levels[Level];
+    }
+    const NodeInfo &getNodeInfoAtLevel(unsigned Level) const {
+      assert(Level < Levels.size());
+      return Levels[Level];
+    }
+
+    unsigned getNumLevels() const { return Levels.size(); }
+  };
+
+private:
+  typedef DenseMap<Value *, ValueInfo> ValueMap;
+  ValueMap ValueImpls;
+
   const NodeInfo *getNode(Node N) const {
-    auto Itr = NodeImpls.find(N);
-    if (Itr == NodeImpls.end())
+    auto Itr = ValueImpls.find(N.Val);
+    if (Itr == ValueImpls.end())
+      return nullptr;
+    else if (Itr->second.getNumLevels() <= N.DerefLevel)
       return nullptr;
-    return &Itr->second;
+    return &Itr->second.getNodeInfoAtLevel(N.DerefLevel);
   }
   NodeInfo *getNode(Node N) {
-    auto Itr = NodeImpls.find(N);
-    if (Itr == NodeImpls.end())
+    auto Itr = ValueImpls.find(N.Val);
+    if (Itr == ValueImpls.end())
       return nullptr;
-    return &Itr->second;
+    else if (Itr->second.getNumLevels() <= N.DerefLevel)
+      return nullptr;
+    return &Itr->second.getNodeInfoAtLevel(N.DerefLevel);
   }
 
-  static Node nodeDeref(const NodeMap::value_type &P) { return P.first; }
-  typedef std::pointer_to_unary_function<const NodeMap::value_type &, Node>
-      NodeDerefFun;
-
 public:
-  typedef EdgeList::const_iterator const_edge_iterator;
-  typedef mapped_iterator<NodeMap::const_iterator, NodeDerefFun>
-      const_node_iterator;
+  typedef ValueMap::const_iterator const_value_iterator;
 
   bool addNode(Node N) {
-    return NodeImpls
-        .insert(std::make_pair(N, NodeInfo{EdgeList(), getAttrNone()}))
-        .second;
+    assert(N.Val != nullptr);
+    return ValueImpls[N.Val].addNodeToLevel(N.DerefLevel);
   }
 
   void addAttr(Node N, AliasAttrs Attr) {
     auto *Info = getNode(N);
     assert(Info != nullptr);
     Info->Attr |= Attr;
   }
 
-  void addEdge(Node From, Node To, EdgeType Type) {
+  void addEdge(Node From, Node To, int64_t Offset = 0) {
     auto *FromInfo = getNode(From);
     assert(FromInfo != nullptr);
     auto *ToInfo = getNode(To);
     assert(ToInfo != nullptr);
 
-    FromInfo->Edges.push_back(Edge{Type, To});
-    ToInfo->Edges.push_back(Edge{flipWeight(Type), From});
+    FromInfo->Edges.push_back(Edge{Offset, To});
   }
 
   AliasAttrs attrFor(Node N) const {
     auto *Info = getNode(N);
     assert(Info != nullptr);
     return Info->Attr;
   }
 
-  iterator_range<const_edge_iterator> edgesFor(Node N) const {
-    auto *Info = getNode(N);
-    assert(Info != nullptr);
-    auto &Edges = Info->Edges;
-    return make_range(Edges.begin(), Edges.end());
-  }
-
-  iterator_range<const_node_iterator> nodes() const {
-    return make_range<const_node_iterator>(
-        map_iterator(NodeImpls.begin(), NodeDerefFun(nodeDeref)),
-        map_iterator(NodeImpls.end(), NodeDerefFun(nodeDeref)));
+  iterator_range<const_value_iterator> value_mappings() const {
+    return make_range<const_value_iterator>(ValueImpls.begin(),
+                                            ValueImpls.end());
   }
-
-  bool empty() const { return NodeImpls.empty(); }
-  std::size_t size() const { return NodeImpls.size(); }
 };
 
 ///\brief A builder class used to create CFLGraph instance from a given function
 /// The CFL-AA that uses this builder must provide its own type as a template
 /// argument. This is necessary for interprocedural processing: CFLGraphBuilder
 /// needs a way of obtaining the summary of other functions when callinsts are
 /// encountered.
 /// As a result, we expect the said CFL-AA to expose a getAliasSummary() public
 /// member function that takes a Function& and returns the corresponding summary
 /// as a const AliasSummary*.
 template <typename CFLAA> class CFLGraphBuilder {
   // Input of the builder
   CFLAA &Analysis;
   const TargetLibraryInfo &TLI;
 
   // Output of the builder
   CFLGraph Graph;
   SmallVector<Value *, 4> ReturnedValues;
 
-  // Auxiliary structures used by the builder
-  SmallVector<InstantiatedRelation, 8> InstantiatedRelations;
-  SmallVector<InstantiatedAttr, 8> InstantiatedAttrs;
-
   // Helper class
   /// Gets the edges our graph should have, based on an Instruction*
   class GetEdgesVisitor : public InstVisitor<GetEdgesVisitor, void> {
     CFLAA &AA;
     const TargetLibraryInfo &TLI;
 
     CFLGraph &Graph;
     SmallVectorImpl<Value *> &ReturnValues;
-    SmallVectorImpl<InstantiatedRelation> &InstantiatedRelations;
-    SmallVectorImpl<InstantiatedAttr> &InstantiatedAttrs;
+
+    SmallPtrSet<const GlobalValue *, 8> GlobalValues;
+    SmallPtrSet<const ConstantExpr *, 8> ConstantExprs;
 
     static bool hasUsefulEdges(ConstantExpr *CE) {
       // ConstantExpr doesn't have terminators, invokes, or fences, so only
       // needs
       // to check for compares.
       return CE->getOpcode() != Instruction::ICmp &&
              CE->getOpcode() != Instruction::FCmp;
     }
 
     // Returns possible functions called by CS into the given SmallVectorImpl.
     // Returns true if targets found, false otherwise.
     static bool getPossibleTargets(CallSite CS,
                                    SmallVectorImpl<Function *> &Output) {
       if (auto *Fn = CS.getCalledFunction()) {
         Output.push_back(Fn);
         return true;
       }
 
       // TODO: If the call is indirect, we might be able to enumerate all
       // potential
       // targets of the call and return them, rather than just failing.
       return false;
     }
 
-    void addNode(Value *Val) {
+    void checkGlobalOrCExpr(Value *Val) {
       assert(Val != nullptr);
-      if (!Graph.addNode(Val))
+      if (auto GVal = dyn_cast<GlobalValue>(Val)) {
+        if (!GlobalValues.insert(GVal).second)
+          return;
+        Graph.addNode(InstantiatedValue{GVal, 0});
+        Graph.addAttr(InstantiatedValue{GVal, 0},
+                      getGlobalOrArgAttrFromValue(*GVal));
+        Graph.addNode(InstantiatedValue{GVal, 1});
+        Graph.addAttr(InstantiatedValue{GVal, 1}, getAttrUnknown());
+      } else if (auto CExpr = dyn_cast<ConstantExpr>(Val)) {
+        if (hasUsefulEdges(CExpr)) {
+          if (!ConstantExprs.insert(CExpr).second)
             return;
-
-      if (isa<GlobalValue>(Val)) {
-        Graph.addAttr(Val, getGlobalOrArgAttrFromValue(*Val));
-        // Currently we do not attempt to be smart on globals
-        InstantiatedAttrs.push_back(
-            InstantiatedAttr{InstantiatedValue{Val, 1}, getAttrUnknown()});
-      } else if (auto CExpr = dyn_cast<ConstantExpr>(Val))
-        if (hasUsefulEdges(CExpr))
           visitConstantExpr(CExpr);
         }
+      }
+    }
+
+    void addNode(Value *Val, AliasAttrs Attr = AliasAttrs()) {
+      checkGlobalOrCExpr(Val);
+      Graph.addNode(InstantiatedValue{Val, 0});
+      Graph.addAttr(InstantiatedValue{Val, 0}, Attr);
+    }
 
-    void addNodeWithAttr(Value *Val, AliasAttrs Attr) {
-      addNode(Val);
-      Graph.addAttr(Val, Attr);
+    void addAssignEdge(Value *From, Value *To, int64_t Offset = 0) {
+      assert(From != nullptr && To != nullptr);
+      if (!From->getType()->isPointerTy() || !To->getType()->isPointerTy())
+        return;
+      checkGlobalOrCExpr(From);
+      Graph.addNode(InstantiatedValue{From, 0});
+      if (To != From) {
+        checkGlobalOrCExpr(To);
+        Graph.addNode(InstantiatedValue{To, 0});
+        Graph.addEdge(InstantiatedValue{From, 0}, InstantiatedValue{To, 0},
+                      Offset);
+      }
     }
 
-    void addEdge(Value *From, Value *To, EdgeType Type) {
+    void addDerefEdge(Value *From, Value *To) {
       assert(From != nullptr && To != nullptr);
       if (!From->getType()->isPointerTy() || !To->getType()->isPointerTy())
         return;
-      addNode(From);
-      if (To != From)
-        addNode(To);
-      Graph.addEdge(From, To, Type);
+      checkGlobalOrCExpr(From);
+      checkGlobalOrCExpr(To);
+      Graph.addNode(InstantiatedValue{From, 1});
+      Graph.addNode(InstantiatedValue{To, 0});
+      Graph.addEdge(InstantiatedValue{From, 1}, InstantiatedValue{To, 0});
     }
 
   public:
     GetEdgesVisitor(CFLGraphBuilder &Builder)
         : AA(Builder.Analysis), TLI(Builder.TLI), Graph(Builder.Graph),
-          ReturnValues(Builder.ReturnedValues),
-          InstantiatedRelations(Builder.InstantiatedRelations),
-          InstantiatedAttrs(Builder.InstantiatedAttrs) {}
+          ReturnValues(Builder.ReturnedValues) {}
 
     void visitInstruction(Instruction &) {
       llvm_unreachable("Unsupported instruction encountered");
     }
 
     void visitReturnInst(ReturnInst &Inst) {
       if (auto RetVal = Inst.getReturnValue()) {
         if (RetVal->getType()->isPointerTy()) {
           addNode(RetVal);
           ReturnValues.push_back(RetVal);
         }
       }
     }
 
     void visitPtrToIntInst(PtrToIntInst &Inst) {
       auto *Ptr = Inst.getOperand(0);
-      addNodeWithAttr(Ptr, getAttrEscaped());
+      addNode(Ptr, getAttrEscaped());
     }
 
     void visitIntToPtrInst(IntToPtrInst &Inst) {
       auto *Ptr = &Inst;
-      addNodeWithAttr(Ptr, getAttrUnknown());
+      addNode(Ptr, getAttrUnknown());
     }
 
     void visitCastInst(CastInst &Inst) {
       auto *Src = Inst.getOperand(0);
-      addEdge(Src, &Inst, EdgeType::Assign);
+      addAssignEdge(Src, &Inst);
     }
 
     void visitBinaryOperator(BinaryOperator &Inst) {
       auto *Op1 = Inst.getOperand(0);
       auto *Op2 = Inst.getOperand(1);
-      addEdge(Op1, &Inst, EdgeType::Assign);
-      addEdge(Op2, &Inst, EdgeType::Assign);
+      addAssignEdge(Op1, &Inst);
+      addAssignEdge(Op2, &Inst);
     }
 
     void visitAtomicCmpXchgInst(AtomicCmpXchgInst &Inst) {
       auto *Ptr = Inst.getPointerOperand();
       auto *Val = Inst.getNewValOperand();
-      addEdge(Ptr, Val, EdgeType::Dereference);
+      addDerefEdge(Ptr, Val);
     }
 
     void visitAtomicRMWInst(AtomicRMWInst &Inst) {
       auto *Ptr = Inst.getPointerOperand();
       auto *Val = Inst.getValOperand();
-      addEdge(Ptr, Val, EdgeType::Dereference);
+      addDerefEdge(Ptr, Val);
     }
 
     void visitPHINode(PHINode &Inst) {
       for (Value *Val : Inst.incoming_values())
-        addEdge(Val, &Inst, EdgeType::Assign);
+        addAssignEdge(Val, &Inst);
     }
 
     void visitGetElementPtrInst(GetElementPtrInst &Inst) {
       auto *Op = Inst.getPointerOperand();
-      addEdge(Op, &Inst, EdgeType::Assign);
+      addAssignEdge(Op, &Inst);
     }
 
     void visitSelectInst(SelectInst &Inst) {
       // Condition is not processed here (The actual statement producing
       // the condition result is processed elsewhere). For select, the
       // condition is evaluated, but not loaded, stored, or assigned
       // simply as a result of being the condition of a select.
 
       auto *TrueVal = Inst.getTrueValue();
       auto *FalseVal = Inst.getFalseValue();
-      addEdge(TrueVal, &Inst, EdgeType::Assign);
-      addEdge(FalseVal, &Inst, EdgeType::Assign);
+      addAssignEdge(TrueVal, &Inst);
+      addAssignEdge(FalseVal, &Inst);
     }
 
-    void visitAllocaInst(AllocaInst &Inst) { Graph.addNode(&Inst); }
+    void visitAllocaInst(AllocaInst &Inst) { addNode(&Inst); }
 
     void visitLoadInst(LoadInst &Inst) {
       auto *Ptr = Inst.getPointerOperand();
       auto *Val = &Inst;
-      addEdge(Val, Ptr, EdgeType::Reference);
+      addDerefEdge(Ptr, Val);
     }
 
     void visitStoreInst(StoreInst &Inst) {
       auto *Ptr = Inst.getPointerOperand();
       auto *Val = Inst.getValueOperand();
-      addEdge(Ptr, Val, EdgeType::Dereference);
+      addDerefEdge(Ptr, Val);
     }
 
     void visitVAArgInst(VAArgInst &Inst) {
       // We can't fully model va_arg here. For *Ptr = Inst.getOperand(0), it
       // does
       // two things:
       //  1. Loads a value from *((T*)*Ptr).
       //  2. Increments (stores to) *Ptr by some target-specific amount.
       // For now, we'll handle this like a landingpad instruction (by placing
       // the
       // result in its own group, and having that group alias externals).
-      addNodeWithAttr(&Inst, getAttrUnknown());
+      addNode(&Inst, getAttrUnknown());
     }
 
     static bool isFunctionExternal(Function *Fn) {
       return !Fn->hasExactDefinition();
     }
 
     bool tryInterproceduralAnalysis(CallSite CS,
                                     const SmallVectorImpl<Function *> &Fns) {
bool tryInterproceduralAnalysis(CallSite CS,
 
       for (auto *Fn : Fns) {
         auto Summary = AA.getAliasSummary(*Fn);
         assert(Summary != nullptr);
 
         auto &RetParamRelations = Summary->RetParamRelations;
         for (auto &Relation : RetParamRelations) {
           auto IRelation = instantiateExternalRelation(Relation, CS);
-          if (IRelation.hasValue())
-            InstantiatedRelations.push_back(*IRelation);
+          if (IRelation.hasValue()) {
+            Graph.addNode(IRelation->From);
+            Graph.addNode(IRelation->To);
+            Graph.addEdge(IRelation->From, IRelation->To);
+          }
         }
 
         auto &RetParamAttributes = Summary->RetParamAttributes;
         for (auto &Attribute : RetParamAttributes) {
           auto IAttr = instantiateExternalAttribute(Attribute, CS);
-          if (IAttr.hasValue())
-            InstantiatedAttrs.push_back(*IAttr);
+          if (IAttr.hasValue()) {
+            Graph.addNode(IAttr->IValue);
+            Graph.addAttr(IAttr->IValue, IAttr->Attr);
+          }
         }
       }
 
       return true;
     }
 
     void visitCallSite(CallSite CS) {
       auto Inst = CS.getInstruction();
 
       // Make sure all arguments and return value are added to the graph first
       for (Value *V : CS.args())
+        if (V->getType()->isPointerTy())
           addNode(V);
       if (Inst->getType()->isPointerTy())
         addNode(Inst);
 
       // Check if Inst is a call to a library function that
       // allocates/deallocates
       // on the heap. Those kinds of functions do not introduce any aliases.
       // TODO: address other common library functions such as realloc(),
       // strdup(),
void visitCallSite(CallSite CS) {
       // Because the function is opaque, we need to note that anything
       // could have happened to the arguments (unless the function is marked
       // readonly or readnone), and that the result could alias just about
       // anything, too (unless the result is marked noalias).
       if (!CS.onlyReadsMemory())
         for (Value *V : CS.args()) {
           if (V->getType()->isPointerTy()) {
             // The argument itself escapes.
-            addNodeWithAttr(V, getAttrEscaped());
+            Graph.addAttr(InstantiatedValue{V, 0}, getAttrEscaped());
             // The fate of argument memory is unknown. Note that since
-            // AliasAttrs
-            // is transitive with respect to dereference, we only need to
-            // specify
-            // it for the first-level memory.
-            InstantiatedAttrs.push_back(
-                InstantiatedAttr{InstantiatedValue{V, 1}, getAttrUnknown()});
+            // AliasAttrs is transitive with respect to dereference, we only
+            // need to specify it for the first-level memory.
+            Graph.addNode(InstantiatedValue{V, 1});
+            Graph.addAttr(InstantiatedValue{V, 1}, getAttrUnknown());
           }
         }
 
       if (Inst->getType()->isPointerTy()) {
         auto *Fn = CS.getCalledFunction();
         if (Fn == nullptr || !Fn->doesNotAlias(0))
-          // No need to call addNodeWithAttr() since we've added Inst at the
+          // No need to call addNode() since we've added Inst at the
           // beginning of this function and we know it is not a global.
-          Graph.addAttr(Inst, getAttrUnknown());
+          Graph.addAttr(InstantiatedValue{Inst, 0}, getAttrUnknown());
       }
     }
 
     /// Because vectors/aggregates are immutable and unaddressable, there's
     /// nothing we can do to coax a value out of them, other than calling
     /// Extract{Element,Value}. We can effectively treat them as pointers to
     /// arbitrary memory locations we can store in and load from.
     void visitExtractElementInst(ExtractElementInst &Inst) {
       auto *Ptr = Inst.getVectorOperand();
       auto *Val = &Inst;
-      addEdge(Val, Ptr, EdgeType::Reference);
+      addDerefEdge(Ptr, Val);
     }
 
     void visitInsertElementInst(InsertElementInst &Inst) {
       auto *Vec = Inst.getOperand(0);
       auto *Val = Inst.getOperand(1);
-      addEdge(Vec, &Inst, EdgeType::Assign);
-      addEdge(&Inst, Val, EdgeType::Dereference);
+      addAssignEdge(Vec, &Inst);
+      addDerefEdge(&Inst, Val);
     }
 
     void visitLandingPadInst(LandingPadInst &Inst) {
       // Exceptions come from "nowhere", from our analysis' perspective.
       // So we place the instruction its own group, noting that said group may
       // alias externals
-      addNodeWithAttr(&Inst, getAttrUnknown());
+      addNode(&Inst, getAttrUnknown());
     }
 
     void visitInsertValueInst(InsertValueInst &Inst) {
       auto *Agg = Inst.getOperand(0);
       auto *Val = Inst.getOperand(1);
-      addEdge(Agg, &Inst, EdgeType::Assign);
-      addEdge(&Inst, Val, EdgeType::Dereference);
+      addAssignEdge(Agg, &Inst);
+      addDerefEdge(&Inst, Val);
     }
 
     void visitExtractValueInst(ExtractValueInst &Inst) {
       auto *Ptr = Inst.getAggregateOperand();
-      addEdge(&Inst, Ptr, EdgeType::Reference);
+      addDerefEdge(Ptr, &Inst);
     }
 
     void visitShuffleVectorInst(ShuffleVectorInst &Inst) {
       auto *From1 = Inst.getOperand(0);
       auto *From2 = Inst.getOperand(1);
-      addEdge(From1, &Inst, EdgeType::Assign);
-      addEdge(From2, &Inst, EdgeType::Assign);
+      addAssignEdge(From1, &Inst);
+      addAssignEdge(From2, &Inst);
     }
 
     void visitConstantExpr(ConstantExpr *CE) {
       switch (CE->getOpcode()) {
       default:
         llvm_unreachable("Unknown instruction type encountered!");
 // Build the switch statement using the Instruction.def file.
 #define HANDLE_INST(NUM, OPCODE, CLASS)                                        \
bool IsNonInvokeRetTerminator = isa<TerminatorInst>(Inst) &&
                                     !isa<InvokeInst>(Inst) &&
                                     !isa<ReturnInst>(Inst);
     return !isa<CmpInst>(Inst) && !isa<FenceInst>(Inst) &&
            !IsNonInvokeRetTerminator;
   }
 
   void addArgumentToGraph(Argument &Arg) {
     if (Arg.getType()->isPointerTy()) {
-      Graph.addNode(&Arg);
-      Graph.addAttr(&Arg, getGlobalOrArgAttrFromValue(Arg));
+      Graph.addNode(InstantiatedValue{&Arg, 0});
+      Graph.addAttr(InstantiatedValue{&Arg, 0},
+                    getGlobalOrArgAttrFromValue(Arg));
       // Pointees of a formal parameter is known to the caller
-      InstantiatedAttrs.push_back(
-          InstantiatedAttr{InstantiatedValue{&Arg, 1}, getAttrCaller()});
+      Graph.addNode(InstantiatedValue{&Arg, 1});
+      Graph.addAttr(InstantiatedValue{&Arg, 1}, getAttrCaller());
     }
   }
 
   // Given an Instruction, this will add it to the graph, along with any
   // Instructions that are potentially only available from said Instruction
   // For example, given the following line:
   //   %0 = load i16* getelementptr ([1 x i16]* @a, 0, 0), align 2
   // addInstructionToGraph would add both the `load` and `getelementptr`
   // instructions to the graph appropriately.
-  void addInstructionToGraph(Instruction &Inst) {
+  void addInstructionToGraph(GetEdgesVisitor &Visitor, Instruction &Inst) {
     if (!hasUsefulEdges(&Inst))
       return;
 
-    GetEdgesVisitor(*this).visit(Inst);
+    Visitor.visit(Inst);
   }
 
   // Builds the graph needed for constructing the StratifiedSets for the given
   // function
   void buildGraphFrom(Function &Fn) {
+    GetEdgesVisitor Visitor(*this);
+
     for (auto &Bb : Fn.getBasicBlockList())
       for (auto &Inst : Bb.getInstList())
-        addInstructionToGraph(Inst);
+        addInstructionToGraph(Visitor, Inst);
 
     for (auto &Arg : Fn.args())
       addArgumentToGraph(Arg);
   }
 
 public:
   CFLGraphBuilder(CFLAA &Analysis, const TargetLibraryInfo &TLI, Function &Fn)
       : Analysis(Analysis), TLI(TLI) {
     buildGraphFrom(Fn);
   }
 
   const CFLGraph &getCFLGraph() const { return Graph; }
   const SmallVector<Value *, 4> &getReturnValues() const {
     return ReturnedValues;
   }
-  const SmallVector<InstantiatedRelation, 8> &getInstantiatedRelations() const {
-    return InstantiatedRelations;
-  }
-  const SmallVector<InstantiatedAttr, 8> &getInstantiatedAttrs() const {
-    return InstantiatedAttrs;
-  }
 };
 }
 }
 
 #endif

lib/Analysis/CFLSteensAliasAnalysis.cpp

 CFLSteensAAResult::CFLSteensAAResult(const TargetLibraryInfo &TLI)
     : AAResultBase(), TLI(TLI) {}
 CFLSteensAAResult::CFLSteensAAResult(CFLSteensAAResult &&Arg)
     : AAResultBase(std::move(Arg)), TLI(Arg.TLI) {}
 CFLSteensAAResult::~CFLSteensAAResult() {}
 
 /// Information we have about a function and would like to keep around.
 class CFLSteensAAResult::FunctionInfo {
-  StratifiedSets<Value *> Sets;
+  StratifiedSets<InstantiatedValue> Sets;
   AliasSummary Summary;
 
 public:
   FunctionInfo(Function &Fn, const SmallVectorImpl<Value *> &RetVals,
-               StratifiedSets<Value *> S);
+               StratifiedSets<InstantiatedValue> S);
 
-  const StratifiedSets<Value *> &getStratifiedSets() const { return Sets; }
+  const StratifiedSets<InstantiatedValue> &getStratifiedSets() const {
+    return Sets;
+  }
   const AliasSummary &getAliasSummary() const { return Summary; }
 };
 
 /// Try to go from a Value* to a Function*. Never returns nullptr.
 static Optional<Function *> parentFunctionOfValue(Value *);
 
 const StratifiedIndex StratifiedLink::SetSentinel =
     std::numeric_limits<StratifiedIndex>::max();
 
-namespace {
-
-/// StratifiedSets call for knowledge of "direction", so this is how we
-/// represent that locally.
-enum class Level { Same, Above, Below };
-}
-
 //===----------------------------------------------------------------------===//
 // Function declarations that require types defined in the namespace above
 //===----------------------------------------------------------------------===//
 
-/// Gets the "Level" that one should travel in StratifiedSets
-/// given an EdgeType.
-static Level directionOfEdgeType(EdgeType);
-
 /// Determines whether it would be pointless to add the given Value to our sets.
 static bool canSkipAddingToSets(Value *Val);
 
 static Optional<Function *> parentFunctionOfValue(Value *Val) {
   if (auto *Inst = dyn_cast<Instruction>(Val)) {
     auto *Bb = Inst->getParent();
     return Bb->getParent();
   }
 
   if (auto *Arg = dyn_cast<Argument>(Val))
     return Arg->getParent();
   return None;
 }
 
-static Level directionOfEdgeType(EdgeType Weight) {
-  switch (Weight) {
-  case EdgeType::Reference:
-    return Level::Above;
-  case EdgeType::Dereference:
-    return Level::Below;
-  case EdgeType::Assign:
-    return Level::Same;
-  }
-  llvm_unreachable("Incomplete switch coverage");
-}
-
 static bool canSkipAddingToSets(Value *Val) {
   // Constants can share instances, which may falsely unify multiple
   // sets, e.g. in
   // store i32* null, i32** %ptr1
   // store i32* null, i32** %ptr2
   // clearly ptr1 and ptr2 should not be unified into the same set, so
   // we should filter out the (potentially shared) instance to
   // i32* null.
   if (isa<Constant>(Val)) {
     // TODO: Because all of these things are constant, we can determine whether
     // the data is *actually* mutable at graph building time. This will probably
     // come for free/cheap with offset awareness.
     bool CanStoreMutableData = isa<GlobalValue>(Val) ||
                                isa<ConstantExpr>(Val) ||
                                isa<ConstantAggregate>(Val);
     return !CanStoreMutableData;
   }
 
   return false;
 }
 
 CFLSteensAAResult::FunctionInfo::FunctionInfo(
     Function &Fn, const SmallVectorImpl<Value *> &RetVals,
-    StratifiedSets<Value *> S)
+    StratifiedSets<InstantiatedValue> S)
     : Sets(std::move(S)) {
   // Historically, an arbitrary upper-bound of 50 args was selected. We may want
   // to remove this if it doesn't really matter in practice.
   if (Fn.arg_size() > MaxSupportedArgsInSummary)
     return;
 
   DenseMap<StratifiedIndex, InterfaceValue> InterfaceMap;
 
while (true) {
       SetIndex = Link.Below;
     }
   };
 
   // Populate RetParamRelations for return values
   for (auto *RetVal : RetVals) {
     assert(RetVal != nullptr);
     assert(RetVal->getType()->isPointerTy());
-    auto RetInfo = Sets.find(RetVal);
+    auto RetInfo = Sets.find(InstantiatedValue{RetVal, 0});
     if (RetInfo.hasValue())
       AddToRetParamRelations(0, RetInfo->Index);
   }
 
   // Populate RetParamRelations for parameters
   unsigned I = 0;
   for (auto &Param : Fn.args()) {
     if (Param.getType()->isPointerTy()) {
-      auto ParamInfo = Sets.find(&Param);
+      auto ParamInfo = Sets.find(InstantiatedValue{&Param, 0});
       if (ParamInfo.hasValue())
         AddToRetParamRelations(I + 1, ParamInfo->Index);
     }
     ++I;
   }
 }
 
 // Builds the graph + StratifiedSets for a function.
 CFLSteensAAResult::FunctionInfo CFLSteensAAResult::buildSetsFrom(Function *Fn) {
   CFLGraphBuilder<CFLSteensAAResult> GraphBuilder(*this, TLI, *Fn);
-  StratifiedSetsBuilder<Value *> SetBuilder;
+  StratifiedSetsBuilder<InstantiatedValue> SetBuilder;
 
+  // Add all CFLGraph nodes and all Dereference edges to StratifiedSets
   auto &Graph = GraphBuilder.getCFLGraph();
-  SmallVector<Value *, 16> Worklist;
-  for (auto Node : Graph.nodes())
-    Worklist.push_back(Node);
-
-  while (!Worklist.empty()) {
-    auto *CurValue = Worklist.pop_back_val();
-    SetBuilder.add(CurValue);
-    if (canSkipAddingToSets(CurValue))
+  for (const auto &mapping : Graph.value_mappings()) {
+    auto Val = mapping.first;
+    if (canSkipAddingToSets(Val))
       continue;
+    auto &ValueInfo = mapping.second;
 
-    auto Attr = Graph.attrFor(CurValue);
-    SetBuilder.noteAttributes(CurValue, Attr);
-
-    for (const auto &Edge : Graph.edgesFor(CurValue)) {
-      auto Label = Edge.Type;
-      auto *OtherValue = Edge.Other;
+    assert(ValueInfo.getNumLevels() > 0);
+    SetBuilder.add(InstantiatedValue{Val, 0});
+    SetBuilder.noteAttributes(InstantiatedValue{Val, 0},
+                              ValueInfo.getNodeInfoAtLevel(0).Attr);
+    for (unsigned I = 0, E = ValueInfo.getNumLevels() - 1; I < E; ++I) {
+      SetBuilder.add(InstantiatedValue{Val, I + 1});
+      SetBuilder.noteAttributes(InstantiatedValue{Val, I + 1},
+                                ValueInfo.getNodeInfoAtLevel(I + 1).Attr);
+      SetBuilder.addBelow(InstantiatedValue{Val, I},
+                          InstantiatedValue{Val, I + 1});
+    }
+  }
 
-      if (canSkipAddingToSets(OtherValue))
-        continue;
+  // Add all assign edges to StratifiedSets
+  for (const auto &mapping : Graph.value_mappings()) {
+    auto Val = mapping.first;
+    if (canSkipAddingToSets(Val))
+    auto &ValueInfo = mapping.second;
 
-      bool Added;
-      switch (directionOfEdgeType(Label)) {
-      case Level::Above:
-        Added = SetBuilder.addAbove(CurValue, OtherValue);
-        break;
-      case Level::Below:
-        Added = SetBuilder.addBelow(CurValue, OtherValue);
-        break;
-      case Level::Same:
-        Added = SetBuilder.addWith(CurValue, OtherValue);
-        break;
-      }
-
-      if (Added)
-        Worklist.push_back(OtherValue);
-    }
-  }
-
-  // Special handling for interprocedural aliases
-  for (auto &Edge : GraphBuilder.getInstantiatedRelations()) {
-    auto FromVal = Edge.From.Val;
-    auto ToVal = Edge.To.Val;
-    SetBuilder.add(FromVal);
-    SetBuilder.add(ToVal);
-    SetBuilder.addBelowWith(FromVal, Edge.From.DerefLevel, ToVal,
-                            Edge.To.DerefLevel);
-  }
-
-  // Special handling for interprocedural attributes
-  for (auto &IPAttr : GraphBuilder.getInstantiatedAttrs()) {
-    auto Val = IPAttr.IValue.Val;
-    SetBuilder.add(Val);
-    SetBuilder.addAttributesBelow(Val, IPAttr.IValue.DerefLevel, IPAttr.Attr);
+    for (unsigned I = 0, E = ValueInfo.getNumLevels(); I < E; ++I) {
+      auto Src = InstantiatedValue{Val, I};
+      for (auto &Edge : ValueInfo.getNodeInfoAtLevel(I).Edges)
+        SetBuilder.addWith(Src, Edge.Other);
   }
 
   return FunctionInfo(*Fn, GraphBuilder.getReturnValues(), SetBuilder.build());
 }
 
 void CFLSteensAAResult::scan(Function *Fn) {
   auto InsertPair = Cache.insert(std::make_pair(Fn, Optional<FunctionInfo>()));
   (void)InsertPair;
if (MaybeFnA.hasValue()) {
     Fn = *MaybeFnB;
   }
 
   assert(Fn != nullptr);
   auto &MaybeInfo = ensureCached(Fn);
   assert(MaybeInfo.hasValue());
 
   auto &Sets = MaybeInfo->getStratifiedSets();
-  auto MaybeA = Sets.find(ValA);
+  auto MaybeA = Sets.find(InstantiatedValue{ValA, 0});
   if (!MaybeA.hasValue())
     return MayAlias;
 
-  auto MaybeB = Sets.find(ValB);
+  auto MaybeB = Sets.find(InstantiatedValue{ValB, 0});
   if (!MaybeB.hasValue())
     return MayAlias;
 
   auto SetA = *MaybeA;
   auto SetB = *MaybeB;
   auto AttrsA = Sets.getLink(SetA.Index).Attrs;
   auto AttrsB = Sets.getLink(SetB.Index).Attrs;
 

lib/Analysis/StratifiedSets.h

bool addBelow(const T &Main, const T &ToAdd) {
     auto Index = *indexOf(Main);
     if (!linksAt(Index).hasBelow())
       addLinkBelow(Index);
 
     auto Below = linksAt(Index).getBelow();
     return addAtMerging(ToAdd, Below);
   }
 
-  /// \brief Set the AliasAttrs of the set "Level"-levels below "Main". If
-  /// there is no set below "Main", create one for it.
-  void addAttributesBelow(const T &Main, unsigned Level, AliasAttrs Attr) {
-    assert(has(Main));
-    auto Index = *indexOf(Main);
-    auto *Link = &linksAt(Index);
-
-    for (unsigned I = 0; I < Level; ++I) {
-      Index = Link->hasBelow() ? Link->getBelow() : addLinkBelow(Index);
-      Link = &linksAt(Index);
-    }
-    Link->setAttrs(Attr);
-  }
-
   bool addWith(const T &Main, const T &ToAdd) {
     assert(has(Main));
     auto MainIndex = *indexOf(Main);
     return addAtMerging(ToAdd, MainIndex);
   }
 
-  /// \brief Merge the set "MainBelow"-levels below "Main" and the set
-  /// "ToAddBelow"-levels below "ToAdd".
-  void addBelowWith(const T &Main, unsigned MainBelow, const T &ToAdd,
-                    unsigned ToAddBelow) {
-    assert(has(Main));
-    assert(has(ToAdd));
-
-    auto GetIndexBelow = [&](StratifiedIndex Index, unsigned NumLevel) {
-      for (unsigned I = 0; I < NumLevel; ++I) {
-        auto Link = linksAt(Index);
-        Index = Link.hasBelow() ? Link.getBelow() : addLinkBelow(Index);
-      }
-      return Index;
-    };
-    auto MainIndex = GetIndexBelow(*indexOf(Main), MainBelow);
-    auto ToAddIndex = GetIndexBelow(*indexOf(ToAdd), ToAddBelow);
-    if (&linksAt(MainIndex) != &linksAt(ToAddIndex))
-      merge(MainIndex, ToAddIndex);
-  }
-
   void noteAttributes(const T &Main, AliasAttrs NewAttrs) {
     assert(has(Main));
     auto *Info = *get(Main);
     auto &Link = linksAt(Info->Index);
     Link.setAttrs(NewAttrs);
   }
 
 private:
void mergeDirect(StratifiedIndex Idx1, StratifiedIndex Idx2) {
     }
 
     if (LinksFrom->hasBelow()) {
       LinksInto->setBelow(LinksFrom->getBelow());
       auto &NewBelow = linksAt(LinksInto->getBelow());
       NewBelow.setAbove(LinksInto->Number);
     }
 
+    LinksInto->setAttrs(LinksFrom->getAttrs());
     LinksFrom->remapTo(LinksInto->Number);
   }
 
   /// 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));