[CFLAA] Move CFLGraphBuilder out of CFLSteensAliasAnalysis

[grievejia]

Summary

CFLGraphBuilder can be useful to both CFLSteensAliasAnalysis and CFLAndersAliasAnalysis, just like CFLGraph. Move it out to for future use by CFLAndersAliasAnalysis.

Since CFLGraphBuilder needs to use CFLSteens/CFLAnders for interprocedural analysis, I've made it template on the type of AA that uses it. This does impose an implicit API constraint on the AA: we expect it to a getAliasSummary() member function so that the summary of any functions can be retrieved. I didn't make any attempts to properly enforce this constraint (except mentioning it in the documentation), since doing that may require some SFINAE tricks that'll confuse the main point of the codes. Concept will help on that, but we are still not there :)

[george.burgess.iv]

LGTM; will commit later. Thanks for the patch!

llvm/trunk/include/llvm/Analysis/CFLAndersAliasAnalysis.h

 #define LLVM_ANALYSIS_CFLANDERSALIASANALYSIS_H
 
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/IR/Function.h"
 #include "llvm/Pass.h"
 
 namespace llvm {
 
+namespace cflaa {
+struct AliasSummary;
+}
+
 class CFLAndersAAResult : public AAResultBase<CFLAndersAAResult> {
   friend AAResultBase<CFLAndersAAResult>;
 
 public:
   explicit CFLAndersAAResult();
 
+  /// \brief Get the alias summary for the given function
+  /// Return nullptr if the summary is not found or not available
+  const cflaa::AliasSummary *getAliasSummary(Function &Fn) {
+    // Dummy implementation
+    return nullptr;
+  }
+
   AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB) {
     // Dummy implementation
     return AAResultBase::alias(LocA, LocB);
   }
 };
 
 /// Analysis pass providing a never-invalidated alias analysis result.
 ///

llvm/trunk/include/llvm/Analysis/CFLSteensAliasAnalysis.h

 #include "llvm/IR/ValueHandle.h"
 #include "llvm/Pass.h"
 #include <forward_list>
 
 namespace llvm {
 
 class TargetLibraryInfo;
 
+namespace cflaa {
+struct AliasSummary;
+}
+
 class CFLSteensAAResult : public AAResultBase<CFLSteensAAResult> {
   friend AAResultBase<CFLSteensAAResult>;
   class FunctionInfo;
 
 public:
   explicit CFLSteensAAResult(const TargetLibraryInfo &);
   CFLSteensAAResult(CFLSteensAAResult &&Arg);
   ~CFLSteensAAResult();
 
   /// Handle invalidation events from the new pass manager.
   ///
   /// By definition, this result is stateless and so remains valid.
   bool invalidate(Function &, const PreservedAnalyses &) { return false; }
 
   /// \brief Inserts the given Function into the cache.
   void scan(Function *Fn);
 
   void evict(Function *Fn);
 
   /// \brief Ensures that the given function is available in the cache.
   /// Returns the appropriate entry from the cache.
   const Optional<FunctionInfo> &ensureCached(Function *Fn);
 
+  /// \brief Get the alias summary for the given function
+  /// Return nullptr if the summary is not found or not available
+  const cflaa::AliasSummary *getAliasSummary(Function &Fn);
+
   AliasResult query(const MemoryLocation &LocA, const MemoryLocation &LocB);
 
   AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB) {
     if (LocA.Ptr == LocB.Ptr)
       return LocA.Size == LocB.Size ? MustAlias : PartialAlias;
 
     // Comparisons between global variables and other constants should be
     // handled by BasicAA.

llvm/trunk/lib/Analysis/AliasAnalysisSummary.h

 /// and therefore heavily rely on this header.
 ///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ANALYSIS_ALIASANALYSISSUMMARY_H
 #define LLVM_ANALYSIS_ALIASANALYSISSUMMARY_H
 
 #include "llvm/ADT/Optional.h"
+#include "llvm/ADT/SmallVector.h"
 #include "llvm/IR/CallSite.h"
 #include <bitset>
 
 namespace llvm {
 namespace cflaa {
 
 //===----------------------------------------------------------------------===//
 // AliasAttr related stuffs

 /// Currently, externally visible AliasAttrs include AttrUnknown, AttrGlobal,
 /// and AttrEscaped
 AliasAttrs getExternallyVisibleAttrs(AliasAttrs);
 
 //===----------------------------------------------------------------------===//
 // Function summary related stuffs
 //===----------------------------------------------------------------------===//
 
+/// The maximum number of arguments we can put into a summary.
+static unsigned MaxSupportedArgsInSummary = 50;
+
 /// We use InterfaceValue to describe parameters/return value, as well as
 /// potential memory locations that are pointed to by parameters/return value,
 /// of a function.
 /// Index is an integer which represents a single parameter or a return value.
 /// When the index is 0, it refers to the return value. Non-zero index i refers
 /// to the i-th parameter.
 /// DerefLevel indicates the number of dereferences one must perform on the
 /// parameter/return value to get this InterfaceValue.

 
 /// We use ExternalAttribute to describe an externally visible AliasAttrs
 /// for parameters/return value.
 struct ExternalAttribute {
   InterfaceValue IValue;
   AliasAttrs Attr;
 };
 
+/// AliasSummary is just a collection of ExternalRelation and ExternalAttribute
+struct AliasSummary {
+  // RetParamRelations is a collection of ExternalRelations.
+  SmallVector<ExternalRelation, 8> RetParamRelations;
+
+  // RetParamAttributes is a collection of ExternalAttributes.
+  SmallVector<ExternalAttribute, 8> RetParamAttributes;
+};
+
 /// This is the result of instantiating InterfaceValue at a particular callsite
 struct InstantiatedValue {
   Value *Val;
   unsigned DerefLevel;
 };
 Optional<InstantiatedValue> instantiateInterfaceValue(InterfaceValue, CallSite);
 
 /// This is the result of instantiating ExternalRelation at a particular

llvm/trunk/lib/Analysis/CFLGraph.h

 ///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ANALYSIS_CFLGRAPH_H
 #define LLVM_ANALYSIS_CFLGRAPH_H
 
 #include "AliasAnalysisSummary.h"
 #include "llvm/ADT/STLExtras.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
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)));
   }
 
   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;
+
+    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) {
+      assert(Val != nullptr);
+      if (!Graph.addNode(Val))
+        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 addNodeWithAttr(Value *Val, AliasAttrs Attr) {
+      addNode(Val);
+      Graph.addAttr(Val, Attr);
+    }
+
+    void addEdge(Value *From, Value *To, EdgeType Type) {
+      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);
+    }
+
+  public:
+    GetEdgesVisitor(CFLGraphBuilder &Builder)
+        : AA(Builder.Analysis), TLI(Builder.TLI), Graph(Builder.Graph),
+          ReturnValues(Builder.ReturnedValues),
+          InstantiatedRelations(Builder.InstantiatedRelations),
+          InstantiatedAttrs(Builder.InstantiatedAttrs) {}
+
+    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());
+    }
+
+    void visitIntToPtrInst(IntToPtrInst &Inst) {
+      auto *Ptr = &Inst;
+      addNodeWithAttr(Ptr, getAttrUnknown());
+    }
+
+    void visitCastInst(CastInst &Inst) {
+      auto *Src = Inst.getOperand(0);
+      addEdge(Src, &Inst, EdgeType::Assign);
+    }
+
+    void visitBinaryOperator(BinaryOperator &Inst) {
+      auto *Op1 = Inst.getOperand(0);
+      auto *Op2 = Inst.getOperand(1);
+      addEdge(Op1, &Inst, EdgeType::Assign);
+      addEdge(Op2, &Inst, EdgeType::Assign);
+    }
+
+    void visitAtomicCmpXchgInst(AtomicCmpXchgInst &Inst) {
+      auto *Ptr = Inst.getPointerOperand();
+      auto *Val = Inst.getNewValOperand();
+      addEdge(Ptr, Val, EdgeType::Dereference);
+    }
+
+    void visitAtomicRMWInst(AtomicRMWInst &Inst) {
+      auto *Ptr = Inst.getPointerOperand();
+      auto *Val = Inst.getValOperand();
+      addEdge(Ptr, Val, EdgeType::Dereference);
+    }
+
+    void visitPHINode(PHINode &Inst) {
+      for (Value *Val : Inst.incoming_values())
+        addEdge(Val, &Inst, EdgeType::Assign);
+    }
+
+    void visitGetElementPtrInst(GetElementPtrInst &Inst) {
+      auto *Op = Inst.getPointerOperand();
+      addEdge(Op, &Inst, EdgeType::Assign);
+    }
+
+    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);
+    }
+
+    void visitAllocaInst(AllocaInst &Inst) { Graph.addNode(&Inst); }
+
+    void visitLoadInst(LoadInst &Inst) {
+      auto *Ptr = Inst.getPointerOperand();
+      auto *Val = &Inst;
+      addEdge(Val, Ptr, EdgeType::Reference);
+    }
+
+    void visitStoreInst(StoreInst &Inst) {
+      auto *Ptr = Inst.getPointerOperand();
+      auto *Val = Inst.getValueOperand();
+      addEdge(Ptr, Val, EdgeType::Dereference);
+    }
+
+    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());
+    }
+
+    static bool isFunctionExternal(Function *Fn) {
+      return !Fn->hasExactDefinition();
+    }
+
+    bool tryInterproceduralAnalysis(CallSite CS,
+                                    const SmallVectorImpl<Function *> &Fns) {
+      assert(Fns.size() > 0);
+
+      if (CS.arg_size() > MaxSupportedArgsInSummary)
+        return false;
+
+      // Exit early if we'll fail anyway
+      for (auto *Fn : Fns) {
+        if (isFunctionExternal(Fn) || Fn->isVarArg())
+          return false;
+        // Fail if the caller does not provide enough arguments
+        assert(Fn->arg_size() <= CS.arg_size());
+        if (!AA.getAliasSummary(*Fn))
+          return false;
+      }
+
+      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);
+        }
+
+        auto &RetParamAttributes = Summary->RetParamAttributes;
+        for (auto &Attribute : RetParamAttributes) {
+          auto IAttr = instantiateExternalAttribute(Attribute, CS);
+          if (IAttr.hasValue())
+            InstantiatedAttrs.push_back(*IAttr);
+        }
+      }
+
+      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())
+        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(),
+      // etc.
+      if (isMallocLikeFn(Inst, &TLI) || isCallocLikeFn(Inst, &TLI) ||
+          isFreeCall(Inst, &TLI))
+        return;
+
+      // TODO: Add support for noalias args/all the other fun function
+      // attributes
+      // that we can tack on.
+      SmallVector<Function *, 4> Targets;
+      if (getPossibleTargets(CS, Targets))
+        if (tryInterproceduralAnalysis(CS, Targets))
+          return;
+
+      // 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());
+            // 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()});
+          }
+        }
+
+      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
+          // beginning of this function and we know it is not a global.
+          Graph.addAttr(Inst, 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);
+    }
+
+    void visitInsertElementInst(InsertElementInst &Inst) {
+      auto *Vec = Inst.getOperand(0);
+      auto *Val = Inst.getOperand(1);
+      addEdge(Vec, &Inst, EdgeType::Assign);
+      addEdge(&Inst, Val, EdgeType::Dereference);
+    }
+
+    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());
+    }
+
+    void visitInsertValueInst(InsertValueInst &Inst) {
+      auto *Agg = Inst.getOperand(0);
+      auto *Val = Inst.getOperand(1);
+      addEdge(Agg, &Inst, EdgeType::Assign);
+      addEdge(&Inst, Val, EdgeType::Dereference);
+    }
+
+    void visitExtractValueInst(ExtractValueInst &Inst) {
+      auto *Ptr = Inst.getAggregateOperand();
+      addEdge(&Inst, Ptr, EdgeType::Reference);
+    }
+
+    void visitShuffleVectorInst(ShuffleVectorInst &Inst) {
+      auto *From1 = Inst.getOperand(0);
+      auto *From2 = Inst.getOperand(1);
+      addEdge(From1, &Inst, EdgeType::Assign);
+      addEdge(From2, &Inst, EdgeType::Assign);
+    }
+
+    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)                                        \
+  case Instruction::OPCODE:                                                    \
+    this->visit##OPCODE(*(CLASS *)CE);                                         \
+    break;
+#include "llvm/IR/Instruction.def"
+      }
+    }
+  };
+
+  // Helper functions
+
+  // Determines whether or not we an instruction is useless to us (e.g.
+  // FenceInst)
+  static bool hasUsefulEdges(Instruction *Inst) {
+    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));
+      // Pointees of a formal parameter is known to the caller
+      InstantiatedAttrs.push_back(
+          InstantiatedAttr{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) {
+    if (!hasUsefulEdges(&Inst))
+      return;
+
+    GetEdgesVisitor(*this).visit(Inst);
+  }
+
+  // Builds the graph needed for constructing the StratifiedSets for the given
+  // function
+  void buildGraphFrom(Function &Fn) {
+    for (auto &Bb : Fn.getBasicBlockList())
+      for (auto &Inst : Bb.getInstList())
+        addInstructionToGraph(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

llvm/trunk/lib/Analysis/CFLSteensAliasAnalysis.cpp

 // FunctionPasses to run concurrently.
 
 #include "llvm/Analysis/CFLSteensAliasAnalysis.h"
 #include "CFLGraph.h"
 #include "StratifiedSets.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/None.h"
 #include "llvm/ADT/Optional.h"
-#include "llvm/Analysis/MemoryBuiltins.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/Function.h"
-#include "llvm/IR/InstVisitor.h"
-#include "llvm/IR/Instructions.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/raw_ostream.h"
 #include <algorithm>
 #include <cassert>
 #include <memory>
 #include <tuple>
 
 using namespace llvm;
 using namespace llvm::cflaa;
 
 #define DEBUG_TYPE "cfl-steens-aa"
 
 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;
-
-  // RetParamRelations is a collection of ExternalRelations.
-  SmallVector<ExternalRelation, 8> RetParamRelations;
-
-  // RetParamAttributes is a collection of ExternalAttributes.
-  SmallVector<ExternalAttribute, 8> RetParamAttributes;
+  AliasSummary Summary;
 
 public:
   FunctionInfo(Function &Fn, const SmallVectorImpl<Value *> &RetVals,
                StratifiedSets<Value *> S);
 
   const StratifiedSets<Value *> &getStratifiedSets() const { return Sets; }
-  const SmallVectorImpl<ExternalRelation> &getRetParamRelations() const {
-    return RetParamRelations;
-  }
-  const SmallVectorImpl<ExternalAttribute> &getRetParamAttributes() const {
-    return RetParamAttributes;
-  }
+  const AliasSummary &getAliasSummary() const { return Summary; }
 };
 
 /// Try to go from a Value* to a Function*. Never returns nullptr.
 static Optional<Function *> parentFunctionOfValue(Value *);
 
-/// Returns possible functions called by the Inst* into the given
-/// SmallVectorImpl. Returns true if targets found, false otherwise. This is
-/// templated so we can use it with CallInsts and InvokeInsts.
-static bool getPossibleTargets(CallSite, SmallVectorImpl<Function *> &);
-
 const StratifiedIndex StratifiedLink::SetSentinel =
     std::numeric_limits<StratifiedIndex>::max();
 
 namespace {
 
-/// The maximum number of arguments we can put into a summary.
-LLVM_CONSTEXPR unsigned MaxSupportedArgsInSummary = 50;
-
 /// StratifiedSets call for knowledge of "direction", so this is how we
 /// represent that locally.
 enum class Level { Same, Above, Below };
-
-/// Gets the edges our graph should have, based on an Instruction*
-class GetEdgesVisitor : public InstVisitor<GetEdgesVisitor, void> {
-  CFLSteensAAResult &AA;
-  const TargetLibraryInfo &TLI;
-
-  CFLGraph &Graph;
-  SmallVectorImpl<Value *> &ReturnValues;
-  SmallVectorImpl<InstantiatedRelation> &InstantiatedRelations;
-  SmallVectorImpl<InstantiatedAttr> &InstantiatedAttrs;
-
-  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;
-  }
-
-  void addNode(Value *Val) {
-    assert(Val != nullptr);
-    if (!Graph.addNode(Val))
-      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 addNodeWithAttr(Value *Val, AliasAttrs Attr) {
-    addNode(Val);
-    Graph.addAttr(Val, Attr);
-  }
-
-  void addEdge(Value *From, Value *To, EdgeType Type) {
-    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);
-  }
-
-public:
-  GetEdgesVisitor(CFLSteensAAResult &AA, const TargetLibraryInfo &TLI,
-                  CFLGraph &Graph, SmallVectorImpl<Value *> &ReturnValues,
-                  SmallVectorImpl<InstantiatedRelation> &InstantiatedRelations,
-                  SmallVectorImpl<InstantiatedAttr> &InstantiatedAttrs)
-      : AA(AA), TLI(TLI), Graph(Graph), ReturnValues(ReturnValues),
-        InstantiatedRelations(InstantiatedRelations),
-        InstantiatedAttrs(InstantiatedAttrs) {}
-
-  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());
-  }
-
-  void visitIntToPtrInst(IntToPtrInst &Inst) {
-    auto *Ptr = &Inst;
-    addNodeWithAttr(Ptr, getAttrUnknown());
-  }
-
-  void visitCastInst(CastInst &Inst) {
-    auto *Src = Inst.getOperand(0);
-    addEdge(Src, &Inst, EdgeType::Assign);
-  }
-
-  void visitBinaryOperator(BinaryOperator &Inst) {
-    auto *Op1 = Inst.getOperand(0);
-    auto *Op2 = Inst.getOperand(1);
-    addEdge(Op1, &Inst, EdgeType::Assign);
-    addEdge(Op2, &Inst, EdgeType::Assign);
-  }
-
-  void visitAtomicCmpXchgInst(AtomicCmpXchgInst &Inst) {
-    auto *Ptr = Inst.getPointerOperand();
-    auto *Val = Inst.getNewValOperand();
-    addEdge(Ptr, Val, EdgeType::Dereference);
-  }
-
-  void visitAtomicRMWInst(AtomicRMWInst &Inst) {
-    auto *Ptr = Inst.getPointerOperand();
-    auto *Val = Inst.getValOperand();
-    addEdge(Ptr, Val, EdgeType::Dereference);
-  }
-
-  void visitPHINode(PHINode &Inst) {
-    for (Value *Val : Inst.incoming_values())
-      addEdge(Val, &Inst, EdgeType::Assign);
-  }
-
-  void visitGetElementPtrInst(GetElementPtrInst &Inst) {
-    auto *Op = Inst.getPointerOperand();
-    addEdge(Op, &Inst, EdgeType::Assign);
-  }
-
-  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);
-  }
-
-  void visitAllocaInst(AllocaInst &Inst) { Graph.addNode(&Inst); }
-
-  void visitLoadInst(LoadInst &Inst) {
-    auto *Ptr = Inst.getPointerOperand();
-    auto *Val = &Inst;
-    addEdge(Val, Ptr, EdgeType::Reference);
-  }
-
-  void visitStoreInst(StoreInst &Inst) {
-    auto *Ptr = Inst.getPointerOperand();
-    auto *Val = Inst.getValueOperand();
-    addEdge(Ptr, Val, EdgeType::Dereference);
-  }
-
-  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());
-  }
-
-  static bool isFunctionExternal(Function *Fn) {
-    return !Fn->hasExactDefinition();
-  }
-
-  bool tryInterproceduralAnalysis(CallSite CS,
-                                  const SmallVectorImpl<Function *> &Fns) {
-    assert(Fns.size() > 0);
-
-    if (CS.arg_size() > MaxSupportedArgsInSummary)
-      return false;
-
-    // Exit early if we'll fail anyway
-    for (auto *Fn : Fns) {
-      if (isFunctionExternal(Fn) || Fn->isVarArg())
-        return false;
-      // Fail if the caller does not provide enough arguments
-      assert(Fn->arg_size() <= CS.arg_size());
-      auto &MaybeInfo = AA.ensureCached(Fn);
-      if (!MaybeInfo.hasValue())
-        return false;
-    }
-
-    for (auto *Fn : Fns) {
-      auto &FnInfo = AA.ensureCached(Fn);
-      assert(FnInfo.hasValue());
-
-      auto &RetParamRelations = FnInfo->getRetParamRelations();
-      for (auto &Relation : RetParamRelations) {
-        auto IRelation = instantiateExternalRelation(Relation, CS);
-        if (IRelation.hasValue())
-          InstantiatedRelations.push_back(*IRelation);
-      }
-
-      auto &RetParamAttributes = FnInfo->getRetParamAttributes();
-      for (auto &Attribute : RetParamAttributes) {
-        auto IAttr = instantiateExternalAttribute(Attribute, CS);
-        if (IAttr.hasValue())
-          InstantiatedAttrs.push_back(*IAttr);
-      }
-    }
-
-    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())
-      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(),
-    // etc.
-    if (isMallocLikeFn(Inst, &TLI) || isCallocLikeFn(Inst, &TLI) ||
-        isFreeCall(Inst, &TLI))
-      return;
-
-    // TODO: Add support for noalias args/all the other fun function attributes
-    // that we can tack on.
-    SmallVector<Function *, 4> Targets;
-    if (getPossibleTargets(CS, Targets))
-      if (tryInterproceduralAnalysis(CS, Targets))
-        return;
-
-    // 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());
-          // 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()});
-        }
-      }
-
-    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
-        // beginning of this function and we know it is not a global.
-        Graph.addAttr(Inst, 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);
-  }
-
-  void visitInsertElementInst(InsertElementInst &Inst) {
-    auto *Vec = Inst.getOperand(0);
-    auto *Val = Inst.getOperand(1);
-    addEdge(Vec, &Inst, EdgeType::Assign);
-    addEdge(&Inst, Val, EdgeType::Dereference);
-  }
-
-  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());
-  }
-
-  void visitInsertValueInst(InsertValueInst &Inst) {
-    auto *Agg = Inst.getOperand(0);
-    auto *Val = Inst.getOperand(1);
-    addEdge(Agg, &Inst, EdgeType::Assign);
-    addEdge(&Inst, Val, EdgeType::Dereference);
-  }
-
-  void visitExtractValueInst(ExtractValueInst &Inst) {
-    auto *Ptr = Inst.getAggregateOperand();
-    addEdge(&Inst, Ptr, EdgeType::Reference);
-  }
-
-  void visitShuffleVectorInst(ShuffleVectorInst &Inst) {
-    auto *From1 = Inst.getOperand(0);
-    auto *From2 = Inst.getOperand(1);
-    addEdge(From1, &Inst, EdgeType::Assign);
-    addEdge(From2, &Inst, EdgeType::Assign);
-  }
-
-  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)                                        \
-  case Instruction::OPCODE:                                                    \
-    visit##OPCODE(*(CLASS *)CE);                                               \
-    break;
-#include "llvm/IR/Instruction.def"
-    }
-  }
-};
-
-class CFLGraphBuilder {
-  // Input of the builder
-  CFLSteensAAResult &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 functions
-
-  // Determines whether or not we an instruction is useless to us (e.g.
-  // FenceInst)
-  static bool hasUsefulEdges(Instruction *Inst) {
-    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));
-      // Pointees of a formal parameter is known to the caller
-      InstantiatedAttrs.push_back(
-          InstantiatedAttr{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) {
-    if (!hasUsefulEdges(&Inst))
-      return;
-
-    GetEdgesVisitor(Analysis, TLI, Graph, ReturnedValues, InstantiatedRelations,
-                    InstantiatedAttrs)
-        .visit(Inst);
-  }
-
-  // Builds the graph needed for constructing the StratifiedSets for the given
-  // function
-  void buildGraphFrom(Function &Fn) {
-    for (auto &Bb : Fn.getBasicBlockList())
-      for (auto &Inst : Bb.getInstList())
-        addInstructionToGraph(Inst);
-
-    for (auto &Arg : Fn.args())
-      addArgumentToGraph(Arg);
-  }
-
-public:
-  CFLGraphBuilder(CFLSteensAAResult &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;
-  }
-};
 }
 
 //===----------------------------------------------------------------------===//
 // 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 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;
-}
-
 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;
auto AddToRetParamRelations = [&](unsigned InterfaceIndex,
                                     StratifiedIndex SetIndex) {
     unsigned Level = 0;
     while (true) {
       InterfaceValue CurrValue{InterfaceIndex, Level};
 
       auto Itr = InterfaceMap.find(SetIndex);
       if (Itr != InterfaceMap.end()) {
         if (CurrValue != Itr->second)
-          RetParamRelations.push_back(ExternalRelation{CurrValue, Itr->second});
+          Summary.RetParamRelations.push_back(
+              ExternalRelation{CurrValue, Itr->second});
         break;
       }
 
       auto &Link = Sets.getLink(SetIndex);
       InterfaceMap.insert(std::make_pair(SetIndex, CurrValue));
       auto ExternalAttrs = getExternallyVisibleAttrs(Link.Attrs);
       if (ExternalAttrs.any())
-        RetParamAttributes.push_back(
+        Summary.RetParamAttributes.push_back(
             ExternalAttribute{CurrValue, ExternalAttrs});
 
       if (!Link.hasBelow())
         break;
 
       ++Level;
       SetIndex = Link.Below;
     }
if (Param.getType()->isPointerTy()) {
         AddToRetParamRelations(I + 1, ParamInfo->Index);
     }
     ++I;
   }
 }
 
 // Builds the graph + StratifiedSets for a function.
 CFLSteensAAResult::FunctionInfo CFLSteensAAResult::buildSetsFrom(Function *Fn) {
-  CFLGraphBuilder GraphBuilder(*this, TLI, *Fn);
+  CFLGraphBuilder<CFLSteensAAResult> GraphBuilder(*this, TLI, *Fn);
   StratifiedSetsBuilder<Value *> SetBuilder;
 
   auto &Graph = GraphBuilder.getCFLGraph();
   SmallVector<Value *, 16> Worklist;
   for (auto Node : Graph.nodes())
     Worklist.push_back(Node);
 
   while (!Worklist.empty()) {
if (Iter == Cache.end()) {
     scan(Fn);
     Iter = Cache.find(Fn);
     assert(Iter != Cache.end());
     assert(Iter->second.hasValue());
   }
   return Iter->second;
 }
 
+const AliasSummary *CFLSteensAAResult::getAliasSummary(Function &Fn) {
+  auto &FunInfo = ensureCached(&Fn);
+  if (FunInfo.hasValue())
+    return &FunInfo->getAliasSummary();
+  else
+    return nullptr;
+}
+
 AliasResult CFLSteensAAResult::query(const MemoryLocation &LocA,
                                      const MemoryLocation &LocB) {
   auto *ValA = const_cast<Value *>(LocA.Ptr);
   auto *ValB = const_cast<Value *>(LocB.Ptr);
 
   if (!ValA->getType()->isPointerTy() || !ValB->getType()->isPointerTy())
     return NoAlias;
 

 }
 
 ModRefInfo CFLSteensAAResult::getArgModRefInfo(ImmutableCallSite CS,
                                                unsigned ArgIdx) {
   if (auto CalledFunc = CS.getCalledFunction()) {
     auto &MaybeInfo = ensureCached(const_cast<Function *>(CalledFunc));
     if (!MaybeInfo.hasValue())
       return MRI_ModRef;
-    auto &RetParamAttributes = MaybeInfo->getRetParamAttributes();
-    auto &RetParamRelations = MaybeInfo->getRetParamRelations();
+    auto &RetParamAttributes = MaybeInfo->getAliasSummary().RetParamAttributes;
+    auto &RetParamRelations = MaybeInfo->getAliasSummary().RetParamRelations;
 
     bool ArgAttributeIsWritten =
         std::any_of(RetParamAttributes.begin(), RetParamAttributes.end(),
                     [ArgIdx](const ExternalAttribute &ExtAttr) {
                       return ExtAttr.IValue.Index == ArgIdx + 1;
                     });
     bool ArgIsAccessed =
         std::any_of(RetParamRelations.begin(), RetParamRelations.end(),

 
 FunctionModRefBehavior CFLSteensAAResult::getModRefBehavior(const Function *F) {
   assert(F != nullptr);
 
   // TODO: Remove the const_cast
   auto &MaybeInfo = ensureCached(const_cast<Function *>(F));
   if (!MaybeInfo.hasValue())
     return FMRB_UnknownModRefBehavior;
-  auto &RetParamAttributes = MaybeInfo->getRetParamAttributes();
-  auto &RetParamRelations = MaybeInfo->getRetParamRelations();
+  auto &RetParamAttributes = MaybeInfo->getAliasSummary().RetParamAttributes;
+  auto &RetParamRelations = MaybeInfo->getAliasSummary().RetParamRelations;
 
   // First, if any argument is marked Escpaed, Unknown or Global, anything may
   // happen to them and thus we can't draw any conclusion.
   if (!RetParamAttributes.empty())
     return FMRB_UnknownModRefBehavior;
 
   // Currently we don't (and can't) distinguish reads from writes in
   // RetParamRelations. All we can say is whether there may be memory access or