[CFLAA] On-Demand variant of Context Free Language Alias Analysis

[david2050]

Summary

This patch adds another flavor of Alias Analysis which
is a variant of the earlier CFLAliasAnalysis.

This analysis is still experimental and is contributed
as an alternative to the two existing similar passes.

Analysis is off by default but enabled by

-mllvm -use-cfl-aa=on-demand -mllvm -use-cfl-aa-in-codegen=on-demand

A summary of approach and experimentation is here:

https://www.facebook.com/notes/david-callahan/llvm-cfl-alias-analysis/10150648030284971

[george.burgess.iv]

+Hal

[david2050]

Cleanup comments and small refactorings

include/llvm/Analysis/CFLOnDemandAliasAnalysis.h

+//===- CFLAliasAnalysis.h - CFL-Based Alias Analysis Interface ---*- C++ -*-==//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+/// \file
+/// This is the interface for LLVM's primary stateless and local alias analysis.
+///
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_CFLONDEMANDALIASANALYSIS_H
+#define LLVM_ANALYSIS_CFLONDEMANDALIASANALYSIS_H
+
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/None.h"
+#include "llvm/ADT/Optional.h"
+#include "llvm/Analysis/AliasAnalysis.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/Module.h"
+#include "llvm/IR/ValueHandle.h"
+#include "llvm/Pass.h"
+#include <forward_list>
+
+namespace llvm {
+
+class CFLODAAResult : public AAResultBase<CFLODAAResult> {
+  friend AAResultBase<CFLODAAResult>;
+
+  struct FunctionInfo;
+
+public:
+  explicit CFLODAAResult();
+  CFLODAAResult(CFLODAAResult &&Arg);
+  ~CFLODAAResult();
+
+  /// 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 rescan(Function *Fn); /// Rebuild information after transformations
+
+  void evict(Function *Fn);
+
+  /// \brief Ensures that the given function is available in the cache.
+  /// Returns the appropriate entry from the cache.
+  FunctionInfo *ensureCached(Function *Fn);
+  Optional<FunctionInfo *> getCached(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;
+    AliasResult QueryResult = query(LocA, LocB);
+    return QueryResult;
+  }
+  void setActiveFunction(Function*);
+
+private:
+  AliasResult query(Function * Fn, Value * ValA, Value * ValB);
+  
+  /// \brief Cached mapping of Functions to their equivalence class.
+  /// If a function's sets are currently being built, it is marked
+  /// in the cache as an Optional without a value. This way, if we
+  /// have any kind of recursion, it is discernable from a function
+  /// that simply has empty sets
+  
+  DenseMap<Function *, std::unique_ptr<FunctionInfo>> Cache;
+  Function *ActiveFunction = nullptr;
+
+  /// Builds the graph + StratifiedSets for a function.
+  std::unique_ptr<FunctionInfo> buildSetsFrom(Function *F);
+};
+
+/// Analysis pass providing a never-invalidated alias analysis result.
+///
+/// FIXME: We really should refactor CFL to use the analysis more heavily, and
+/// in particular to leverage invalidation to trigger re-computation of sets.
+class CFLODAA : public AnalysisInfoMixin<CFLODAA> {
+  friend AnalysisInfoMixin<CFLODAA> ;
+  static char PassID;
+  
+public:
+  typedef CFLODAAResult Result;
+  CFLODAAResult run(Function &F, AnalysisManager<Function> *AM);
+};
+
+/// Legacy wrapper pass to provide the CFLODAAResult object.
+class CFLODAAWrapperPass : public ImmutablePass {
+  std::unique_ptr<CFLODAAResult> Result;
+
+public:
+  static char ID;
+
+  CFLODAAWrapperPass();
+
+  CFLODAAResult &getResult() { return *Result; }
+  const CFLODAAResult &getResult() const { return *Result; }
+
+  bool doInitialization(Module &M) override;
+  bool doFinalization(Module &M) override;
+  void getAnalysisUsage(AnalysisUsage &AU) const override;
+};
+
+//===--------------------------------------------------------------------===//
+//
+// createCFLOnDemandAAWrapperPass - This pass implements a set-based approach to
+// alias analysis.
+//
+ImmutablePass *createCFLOnDemandAAWrapperPass();
+FunctionPass *createCFLOnDemandAARebuildPass();
+}
+
+#endif

include/llvm/Analysis/LabeledBidirectionalGraph.h

+//===- LabeledBidirectionalGraph.h -----------------------------------------==//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines a simple labeled, bidirectional graph expressed with
+// adjacency lists.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LABELEDBIDRECTIONALGRAPH_H
+#define LABELEDBIDRECTIONALGRAPH_H 1
+
+#include <assert.h>
+#include <vector>
+
+namespace llvm {
+
+// Set building requires a Labeled bidirectional graph.
+template <typename EdgeTypeT> class LabeledBidirectionalGraph {
+public:
+  typedef std::size_t Node;
+
+  struct Edge {
+    EdgeTypeT Type;
+    Node Other;
+
+    Edge(EdgeTypeT Type, Node Other) : Type(Type), Other(Other) {}
+
+    bool operator==(Edge E) const {
+      return Type == E.Type && Other == E.Other;
+    }
+
+    bool operator!=(Edge E) const { return !operator==(E); }
+  };
+
+private:
+  typedef SmallVector<Edge,4> EdgesVectorType;
+  struct NodeImpl {
+    EdgesVectorType Edges;
+  };
+
+  std::vector<NodeImpl> NodeImpls;
+
+  const NodeImpl &getNode(Node N) const { return NodeImpls[N]; }
+  NodeImpl &getNode(Node N) { return NodeImpls[N]; }
+#ifndef NDEBUG
+  unsigned EdgeCount = 0;
+#endif
+
+public:
+  bool inbounds(Node NodeIndex) const { return NodeIndex < NodeImpls.size(); }
+
+  // ----- Actual graph-related things ----- //
+
+  LabeledBidirectionalGraph() {}
+
+  LabeledBidirectionalGraph(LabeledBidirectionalGraph<EdgeTypeT> &&Other)
+      : NodeImpls(std::move(Other.NodeImpls)) {}
+
+  LabeledBidirectionalGraph(const LabeledBidirectionalGraph &G) {
+    NodeImpls = G.NodeImpls;
+  }
+
+  LabeledBidirectionalGraph &operator=(const LabeledBidirectionalGraph &G) {
+    NodeImpls = G.NodeImpls;
+    return *this;
+  }
+
+  LabeledBidirectionalGraph<EdgeTypeT> &
+  operator=(LabeledBidirectionalGraph<EdgeTypeT> &&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, EdgeTypeT Label, EdgeTypeT ReverseLabel) {
+    assert(inbounds(From));
+    assert(inbounds(To));
+    getNode(From).Edges.emplace_back(Label, To);
+    getNode(To).Edges.emplace_back(ReverseLabel, From);
+  }
+  void addEdge(Node From, Node To, EdgeTypeT Label) {
+    assert(inbounds(From));
+    assert(inbounds(To));
+    auto &FromNode = getNode(From);
+    FromNode.Edges.emplace_back(Label, To);
+  }
+
+  bool empty() const { return NodeImpls.empty(); }
+  std::size_t size() const { return NodeImpls.size(); }
+
+  const EdgesVectorType &edges(Node N) const {
+    assert(inbounds(N));
+    return NodeImpls[N].Edges;
+  }
+
+  bool hasEdgeType(Node N, EdgeTypeT Type) const {
+    for (auto &E : edges(N))
+      if (E.Type == Type)
+        return true;
+    return false;
+  }
+  bool hasEdge(Node N, Node Other, EdgeTypeT Type) const {
+    assert(inbounds(N));
+    for (auto &E : edges(N))
+      if (E.Type == Type && E.Other == Other)
+        return true;
+    return false;
+  }
+  Optional<Node> firstSuccessorByType(Node N, EdgeTypeT Type) const {
+    for (auto &E : edges(N))
+      if (E.Type == Type)
+        return E.Other;
+    return None;
+  }
+
+  /// An adaptor to support range-based for iteration over nodes.
+  class NodeIterator {
+    Node Current;
+
+  public:
+    NodeIterator(size_t Current) : Current(static_cast<Node>(Current)) {}
+    void operator++() { ++Current; }
+    Node operator*() { return Current; }
+    bool operator==(NodeIterator E) { return Current == E.Current; }
+    bool operator!=(NodeIterator E) { return Current != E.Current; }
+  };
+  NodeIterator begin() const { return NodeIterator(0); }
+  NodeIterator end() const { return NodeIterator(size()); }
+};
+}
+#endif

include/llvm/InitializePasses.h

 void initializeBreakCriticalEdgesPass(PassRegistry&);
 void initializeCFGOnlyPrinterPass(PassRegistry&);
 void initializeCFGOnlyViewerPass(PassRegistry&);
 void initializeCFGPrinterPass(PassRegistry&);
 void initializeCFGSimplifyPassPass(PassRegistry&);
 void initializeCFGViewerPass(PassRegistry&);
 void initializeCFLAndersAAWrapperPassPass(PassRegistry&);
 void initializeCFLSteensAAWrapperPassPass(PassRegistry&);
+void initializeCFLODAAWrapperPassPass(PassRegistry&);
+void initializeCFLODAARebuildPassPass(PassRegistry&);
 void initializeCallGraphDOTPrinterPass(PassRegistry&);
 void initializeCallGraphPrinterLegacyPassPass(PassRegistry&);
 void initializeCallGraphViewerPass(PassRegistry&);
 void initializeCallGraphWrapperPassPass(PassRegistry &);
 void initializeCodeGenPreparePass(PassRegistry&);
 void initializeConstantHoistingLegacyPassPass(PassRegistry&);
 void initializeConstantMergeLegacyPassPass(PassRegistry &);
 void initializeConstantPropagationPass(PassRegistry&);

include/llvm/LinkAllPasses.h

 #define LLVM_LINKALLPASSES_H
 
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AliasSetTracker.h"
 #include "llvm/Analysis/AliasAnalysisEvaluator.h"
 #include "llvm/Analysis/BasicAliasAnalysis.h"
 #include "llvm/Analysis/CFLAndersAliasAnalysis.h"
 #include "llvm/Analysis/CFLSteensAliasAnalysis.h"
+#include "llvm/Analysis/CFLOnDemandAliasAnalysis.h"
 #include "llvm/Analysis/CallPrinter.h"
 #include "llvm/Analysis/DomPrinter.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/IntervalPartition.h"
 #include "llvm/Analysis/Lint.h"
 #include "llvm/Analysis/Passes.h"
 #include "llvm/Analysis/PostDominators.h"
 #include "llvm/Analysis/RegionPass.h"
ForcePassLinking() {
       (void) llvm::createTypeBasedAAWrapperPass();
       (void) llvm::createScopedNoAliasAAWrapperPass();
       (void) llvm::createBoundsCheckingPass();
       (void) llvm::createBreakCriticalEdgesPass();
       (void) llvm::createCallGraphDOTPrinterPass();
       (void) llvm::createCallGraphViewerPass();
       (void) llvm::createCFGSimplificationPass();
       (void) llvm::createCFLAndersAAWrapperPass();
+      (void) llvm::createCFLOnDemandAAWrapperPass();
       (void) llvm::createCFLSteensAAWrapperPass();
       (void) llvm::createStructurizeCFGPass();
       (void) llvm::createConstantMergePass();
       (void) llvm::createConstantPropagationPass();
       (void) llvm::createCostModelAnalysisPass();
       (void) llvm::createDeadArgEliminationPass();
       (void) llvm::createDeadCodeEliminationPass();
       (void) llvm::createDeadInstEliminationPass();

lib/Analysis/AliasAnalysis.cpp

 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/BasicAliasAnalysis.h"
 #include "llvm/Analysis/CFG.h"
 #include "llvm/Analysis/CFLAndersAliasAnalysis.h"
 #include "llvm/Analysis/CFLSteensAliasAnalysis.h"
+#include "llvm/Analysis/CFLOnDemandAliasAnalysis.h"
 #include "llvm/Analysis/CaptureTracking.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/ObjCARCAliasAnalysis.h"
 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
 #include "llvm/Analysis/ScopedNoAliasAA.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/TypeBasedAliasAnalysis.h"
 #include "llvm/Analysis/ValueTracking.h"

 
 char AAResultsWrapperPass::ID = 0;
 
 INITIALIZE_PASS_BEGIN(AAResultsWrapperPass, "aa",
                       "Function Alias Analysis Results", false, true)
 INITIALIZE_PASS_DEPENDENCY(BasicAAWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(CFLAndersAAWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(CFLSteensAAWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(CFLODAAWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(ExternalAAWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(ObjCARCAAWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(SCEVAAWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(ScopedNoAliasAAWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(TypeBasedAAWrapperPass)
 INITIALIZE_PASS_END(AAResultsWrapperPass, "aa",
                     "Function Alias Analysis Results", false, true)
bool AAResultsWrapperPass::runOnFunction(Function &F) {
   if (auto *WrapperPass = getAnalysisIfAvailable<GlobalsAAWrapperPass>())
     AAR->addAAResult(WrapperPass->getResult());
   if (auto *WrapperPass = getAnalysisIfAvailable<SCEVAAWrapperPass>())
     AAR->addAAResult(WrapperPass->getResult());
   if (auto *WrapperPass = getAnalysisIfAvailable<CFLAndersAAWrapperPass>())
     AAR->addAAResult(WrapperPass->getResult());
   if (auto *WrapperPass = getAnalysisIfAvailable<CFLSteensAAWrapperPass>())
     AAR->addAAResult(WrapperPass->getResult());
+  if (auto *WrapperPass = getAnalysisIfAvailable<CFLODAAWrapperPass>())
+    AAR->addAAResult(WrapperPass->getResult());
 
   // If available, run an external AA providing callback over the results as
   // well.
   if (auto *WrapperPass = getAnalysisIfAvailable<ExternalAAWrapperPass>())
     if (WrapperPass->CB)
       WrapperPass->CB(*this, F, *AAR);
 
   // Analyses don't mutate the IR, so return false.
void AAResultsWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
   // preserves them. This hard coding of lists of alias analyses is specific to
   // the legacy pass manager.
   AU.addUsedIfAvailable<ScopedNoAliasAAWrapperPass>();
   AU.addUsedIfAvailable<TypeBasedAAWrapperPass>();
   AU.addUsedIfAvailable<objcarc::ObjCARCAAWrapperPass>();
   AU.addUsedIfAvailable<GlobalsAAWrapperPass>();
   AU.addUsedIfAvailable<SCEVAAWrapperPass>();
   AU.addUsedIfAvailable<CFLAndersAAWrapperPass>();
+  AU.addUsedIfAvailable<CFLODAAWrapperPass>();
   AU.addUsedIfAvailable<CFLSteensAAWrapperPass>();
 }
 
 AAResults llvm::createLegacyPMAAResults(Pass &P, Function &F,
                                         BasicAAResult &BAR) {
   AAResults AAR(P.getAnalysis<TargetLibraryInfoWrapperPass>().getTLI());
 
   // Add in our explicitly constructed BasicAA results.
if (auto *WrapperPass =
           P.getAnalysisIfAvailable<objcarc::ObjCARCAAWrapperPass>())
     AAR.addAAResult(WrapperPass->getResult());
   if (auto *WrapperPass = P.getAnalysisIfAvailable<GlobalsAAWrapperPass>())
     AAR.addAAResult(WrapperPass->getResult());
   if (auto *WrapperPass = P.getAnalysisIfAvailable<CFLAndersAAWrapperPass>())
     AAR.addAAResult(WrapperPass->getResult());
   if (auto *WrapperPass = P.getAnalysisIfAvailable<CFLSteensAAWrapperPass>())
     AAR.addAAResult(WrapperPass->getResult());
+  if (auto *WrapperPass = P.getAnalysisIfAvailable<CFLODAAWrapperPass>())
+    AAR.addAAResult(WrapperPass->getResult());
 
   return AAR;
 }
 
 bool llvm::isNoAliasCall(const Value *V) {
   if (auto CS = ImmutableCallSite(V))
     return CS.paramHasAttr(0, Attribute::NoAlias);
   return false;
void llvm::getAAResultsAnalysisUsage(AnalysisUsage &AU) {
   // to be added here also.
   AU.addRequired<TargetLibraryInfoWrapperPass>();
   AU.addUsedIfAvailable<ScopedNoAliasAAWrapperPass>();
   AU.addUsedIfAvailable<TypeBasedAAWrapperPass>();
   AU.addUsedIfAvailable<objcarc::ObjCARCAAWrapperPass>();
   AU.addUsedIfAvailable<GlobalsAAWrapperPass>();
   AU.addUsedIfAvailable<CFLAndersAAWrapperPass>();
   AU.addUsedIfAvailable<CFLSteensAAWrapperPass>();
+  AU.addUsedIfAvailable<CFLODAAWrapperPass>();
 }

lib/Analysis/Analysis.cpp

void llvm::initializeAnalysis(PassRegistry &Registry) {
   initializeCallGraphViewerPass(Registry);
   initializeCostModelAnalysisPass(Registry);
   initializeCFGViewerPass(Registry);
   initializeCFGPrinterPass(Registry);
   initializeCFGOnlyViewerPass(Registry);
   initializeCFGOnlyPrinterPass(Registry);
   initializeCFLAndersAAWrapperPassPass(Registry);
   initializeCFLSteensAAWrapperPassPass(Registry);
+  initializeCFLODAAWrapperPassPass(Registry);
   initializeDependenceAnalysisWrapperPassPass(Registry);
   initializeDelinearizationPass(Registry);
   initializeDemandedBitsWrapperPassPass(Registry);
   initializeDivergenceAnalysisPass(Registry);
   initializeDominanceFrontierWrapperPassPass(Registry);
   initializeDomViewerPass(Registry);
   initializeDomPrinterPass(Registry);
   initializeDomOnlyViewerPass(Registry);

lib/Analysis/CFLOnDemandAliasAnalysis.cpp

+//===- CFLOnDemandAliasAnalysis.cpp - CFL-Based Alias-Analysis Implementation=//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This analysis is a variation of that implemented in CFLAliasAnalysis.cpp but
+// differs in how globals and unknown functions are handled, how
+// cross-procedural information is handled, and retains the "on-demand" search
+// aspect to improve precision.
+//
+// This file implements a CFL-based context-insensitive alias analysis
+// algorithm. It does not depend on types. The algorithm is a mixture of the one
+// described in "Demand-driven alias analysis for C" by Xin Zheng and Radu
+// Rugina, and "Fast algorithms for Dyck-CFL-reachability with applications to
+// Alias Analysis" by Zhang Q, Lyu M R, Yuan H, and Su Z. -- to summarize the
+// papers, we build a graph of the uses of a variable, where each node is a
+// memory location, and each edge is an action that happened on that memory
+// location.  The "actions" can be one of Dereference, Reference, AssignTo, or
+// AssignFrom.
+//
+// An alias exists if there are certain paths in this graph whose labels are
+// described be a context free language. The details are described below.
+//
+// We perform a compression on this graph which reduces the number of nodes
+// without sacrificing precision. This compression reduces the cost of searching
+// for paths in the graph. In compressed form, graphs frequently reduce to a
+// "simple" form where path searches can be done in unit time.
+//
+// We then force nodes of the graph into an equivalence relation. This relation
+// allows for unit-time tests for no-alias avoiding the need to search the graph
+// for paths at all.
+//
+// We exnted to a cross-procedural analysis by maintaining two graphs which make
+// different assumptions about formal arguments. We can copy the optimistic
+// graoh of a called into the caller when it is below some size limit. Otherwise
+// we make pessimestic assumptions about the effects of a function call on
+// pointer parameters and return values.
+//
+// As an aide in debugging, we retain an uncompressed graph and support an
+// option
+// to do path analysis on that graph to confirm the same result.
+//
+// There are four distinct parts of this implementation
+//    -- code that builds the pointer abstraction graph from the input IR
+//    -- code which compresses these graphs and computes equivalence class
+//       approximations
+//    -- code which does on-demand exploration of the graph.
+//    -- code to integrate with alias analysis framework and pass manager
+//
+// The key top-level classes defined here:
+//     PointerGraph -- the graph which abstracts operatons on pointers
+//     GraphBuilder -- the functions to build the PointerGraph from the base IR
+//     GraphInfo -- the information retained from GraphBuilder that is used
+//             later during alias analysis and cross-procedural use in other
+//             functions
+//     Combiner -- functions used to compress the "full" graph to reduce the
+//             cost of later queries
+//     Searcher -- state and functions used to directly search a PointerGraph
+//             for paths which imply aliases
+//     CFLODAAResult::FunctionInfo -- all the information retained for a
+//             function
+//
+//===----------------------------------------------------------------------===//
+
+// N.B. AliasAnalysis as a whole is phrased as a FunctionPass at the moment, and
+// CFLODAA is interprocedural. This is *technically* A Bad Thing, because
+// FunctionPasses are only allowed to inspect the Function that they're being
+// run on. Realistically, this likely isn't a problem until we allow
+// FunctionPasses to run concurrently.
+
+#ifdef NDEBUG
+#define ENABLE_EXPERIMENTS 0
+#define DEBUG_SEARCH 0
+#else
+// Enable the extra features needed to experiment with on-demand searching
+// if the uncompress pointer graph.
+#define ENABLE_EXPERIMENTS 1
+// Enable debugging messages for searching the graph.
+#define DEBUG_SEARCH 0
+// When compressing, combine all aliases of the heap node into the node.
+// This will loose precision.
+#define COMPRESS_HEAP_ALIASES 1
+// Retain the uncompress graph so we can compare searches on that graph
+// to searches on the compressed graph. This provides both validation
+// of the correctness of the compression and measurement of loss of precision.
+#define SEARCH_FULL_GRAPH 1
+#endif
+
+#include "llvm/Analysis/CFLOnDemandAliasAnalysis.h"
+
+#include "llvm/ADT/BitVector.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/None.h"
+#include "llvm/ADT/Optional.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/Analysis/LabeledBidirectionalGraph.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/Allocator.h"
+#include "llvm/Support/Compiler.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/ErrorHandling.h"
+#ifndef NDEBUG
+#include "llvm/Support/FileSystem.h"
+#endif
+#include "llvm/Support/Format.h"
+#ifndef NDEBUG
+#include "llvm/Support/GraphWriter.h"
+#endif
+#include "llvm/Support/raw_ostream.h"
+#include <algorithm>
+#include <cassert>
+#include <memory>
+#include <queue>
+#include <set>
+#include <sstream>
+#include <tuple>
+#include <unordered_set>
+
+using namespace llvm;
+
+static cl::opt<bool> FunctionReporting("cfl-stats", cl::Hidden,
+                                       cl::init(false));
+
+/// This option sets a thrshold on the size of compressed graphs associated
+/// with called functions which are willing to inline into the caller.
+static cl::opt<unsigned> InlineLimit("cfl-inline-limit", cl::Hidden,
+                                     cl::init(50));
+/// Disable searching of the compressed graph to find more precision.
+static cl::opt<bool> DisableSearch("cfl-no-search", cl::Hidden,
+                                   cl::init(false));
+
+/// Given "p+i" where "i" is an integer, we by default
+/// assume that "i" does not index outside of the object referenced by "p"
+/// unless this option is specified.
+static cl::opt<bool> UnsafeAddressing("cfl-unsafe-addressing", cl::Hidden,
+                                      cl::init(false));
+
+/// A debugging a option which prints very lightweight status about phase entry
+static cl::opt<bool> ShowStatus("cfl-status", cl::Hidden, cl::init(false));
+/// Print diagnostic note when untested IR features when first encountered.
+static cl::opt<bool> ShowUntested("clf-untested", cl::Hidden, cl::init(false));
+/// As a validation aid, do graph search on the full graph when it is available.
+static cl::opt<bool> FullGraphSearch("cfl-full-graph", cl::Hidden,
+                                     cl::init(false));
+/// Disable the use of "address bases" to refine equivalence classes for
+/// fast path alias analysis
+static cl::opt<bool> DontUseAddressBases("cfl-no-address-bases", cl::Hidden,
+                                         cl::init(false));
+#ifndef NDEBUG
+static cl::opt<bool> DebugDump("cfl-dump", cl::Hidden, cl::init(false));
+/// Dump "non-simple" graphs for debugging.
+static cl::opt<bool> DebugDumpNonSimple("cfl-dump-non-simple", cl::Hidden,
+                                        cl::init(false));
+/// Don't try to print instructions as labels for graph dumps. At some points
+/// in compilation instructions won't print propertly and the compilation
+/// will fault.
+static cl::opt<bool> NoLabels("cfl-no-labels", cl::Hidden, cl::init(false));
+
+/// Limit debug output to a specific analysis pass based on internal numbering.
+static cl::opt<unsigned>
+    DebugOnly("cfl-debug", cl::Hidden,
+              cl::init(std::numeric_limits<unsigned>::max()));
+#endif
+
+#define DEBUG_TYPE "cfl-od-aa"
+
+#ifdef LLVM_ENABLE_STATS
+STATISTIC(MaxGraphSize, "Maximum compressed graph");
+STATISTIC(TotalGraphSize, "Total size of compressed graphs (edges)");
+#endif
+STATISTIC(QueryCalls, "Number of calls to query()");
+STATISTIC(FastkNoAlias, "Number of NoAlias results on fast path");
+#if ENABLE_EXPERIMENTS
+STATISTIC(SearchOps, "Number Search Steps");
+STATISTIC(FullSearchOps, "Number Full Graph Search Steps");
+STATISTIC(SimpleNoAlias, "Number of NoAlias results for Simple Graphs");
+STATISTIC(SlowNoAlias, "Number of NoAlias results on compressed search path");
+#ifdef LLVM_ENABLE_STAS
+STATISTIC(FastViaAddressRoots,
+          "Number of NoAlias results absed on address roots");
+#endif
+STATISTIC(FullNoAlias, "Number of NoALias Results on full path");
+STATISTIC(NoNodeForValue,
+          "Number of times there was no graph node for a value");
+#endif
+STATISTIC(NumInstructions, "Number of instructions analyzed");
+
+#ifndef NDEBUG
+namespace {
+/// This provieds a numbering scheme for calls to the analysis to
+/// allow debug information to be limited to a specific pass.
+int FunctionNumber = 0;
+/// Map a function to a number for debugging use
+DenseMap<Function *, int> DebugNumber;
+int NextFunctionNumber = 0;
+void setDebugFlag() {
+  if (DebugOnly.getNumOccurrences())
+    llvm::DebugFlag = (DebugOnly.getValue() == (unsigned)FunctionNumber);
+}
+void setDebugFlag(Function *Fn) {
+  FunctionNumber = DebugNumber[Fn];
+  setDebugFlag();
+}
+void dumpCFG(const Function &F) {
+
+  std::string Filename = ("aa/cfg." + F.getName() + ".txt").str();
+  errs() << "Writing '" << Filename << "'...\n";
+
+  std::error_code EC;
+  raw_fd_ostream File(Filename, EC, sys::fs::F_Text);
+  if (EC) {
+    errs() << "Unable top open " << Filename << "\n";
+    return;
+  }
+  F.print(File);
+}
+}
+#endif
+
+// A few macros for repeateed debugging/diagnostic actions.
+#define DEBUG_MSG(x) DEBUG(dbgs() << x << '\n')
+#define DEBUG_INST(x, y) DEBUG(dbgs() << x; y.dump())
+#define DEBUG_ONCE(x)                                                          \
+  DEBUG({                                                                      \
+    bool once = false;                                                         \
+    if (!once) {                                                               \
+      once = true;                                                             \
+      dbgs() << x;                                                             \
+    }                                                                          \
+  })
+
+#define STATUS_MSG(x)                                                          \
+  if (ShowStatus)                                                              \
+  dbgs() << x << '\n'
+
+#define UNTESTED(x)                                                            \
+  do {                                                                         \
+    static bool once = true;                                                   \
+    if (once && ShowUntested) {                                                \
+      once = false;                                                            \
+      dbgs() << x << '\n';                                                     \
+    }                                                                          \
+  } while (0)
+
+namespace {
+/// Edges can be one of these "Labels" -- each Label must have an inverse
+/// Label (Assign has Assign; Reference has Dereference) unless it use
+/// in an transient manner.
+enum class EdgeType {
+  /// The Label assigned when assigning from or to a value. For example, in:
+  ///    %b = getelementptr %a, 0
+  /// The relationships are %b assignFrom %a, and %a assignTo %b.
+  AssignTo,
+  AssignFrom,
+
+  /// The edge used when we have an edge going from some "address" to a Value.
+  /// We create a single "dereference" for a pointer value. We then assign
+  /// from that to uses.
+  ///
+  /// Examples of this include:
+  /// %b = load %a              (%a Derefer X ,  X assignTo %b)
+  /// %b = extractelement %a, 0 ... same
+  Dereference,
+
+  /// The inverse of a Dereference
+  /// %b = load %a              (%a Dereference X) (X refernce %a)
+  /// %b = extractelement %a, 0 ... same
+  Reference,
+
+  /// Transient used during construction
+  /// store p, v       (assign v to the unique dereference of p
+  ///         will generate (p Dereference X) (v AssignTo X)
+  Store,
+};
+
+/// Edges come in pairs, return the label of the inverse edge given a label
+EdgeType flipLabel(EdgeType Initial) {
+  switch (Initial) {
+  case EdgeType::AssignTo:
+    return EdgeType::AssignFrom;
+  case EdgeType::AssignFrom:
+    return EdgeType::AssignTo;
+  case EdgeType::Dereference:
+    return EdgeType::Reference;
+  case EdgeType::Reference:
+    return EdgeType::Dereference;
+  case EdgeType::Store:
+    assert(0 && "Unexpected edge type in flipLabel");
+    return Initial;
+  }
+  llvm_unreachable("Incomplete coverage of EdgeType enum");
+}
+
+#ifndef NDEBUG
+inline raw_ostream &operator<<(raw_ostream &Out, EdgeType Label) {
+  const char *str;
+  switch (Label) {
+  case EdgeType::AssignTo:
+    str = "assign";
+    break;
+  case EdgeType::AssignFrom:
+    str = "assign from";
+    break;
+  case EdgeType::Dereference:
+    str = "deref";
+    break;
+  case EdgeType::Reference:
+    str = "ref";
+    break;
+  case EdgeType::Store:
+    str = "store";
+    break;
+  }
+  return Out << str;
+}
+#endif
+
+typedef LabeledBidirectionalGraph<EdgeType> GraphT;
+typedef GraphT::Node Node;
+typedef DenseMap<Value *, Node> NodeMapT;
+
+/// This is the information we store about a node in the program IR. Two nodes
+/// are not aliased if they have difference Class values or if the Address
+/// fields are different and neither is NOT_ADDRESS_ROOT
+struct AliasEquivInfo {
+  static const unsigned NOT_ADDRESS_ROOT = 0;
+  unsigned Class;
+  unsigned Address;
+  AliasEquivInfo(unsigned Class, unsigned Address = NOT_ADDRESS_ROOT)
+      : Class(Class), Address(Address) {}
+};
+typedef DenseMap<Value *, AliasEquivInfo> AliasEquivClassMap;
+
+/// A specialization of a labeled bidirectional graph
+/// used to represent pointer operations in a function.
+class PointerGraph : public GraphT {
+public:
+  /// A sentinel used when no valid Node value is available.
+  static const Node NOT_A_NODE = std::numeric_limits<Node>::max();
+
+  /// The special node denoted "unknown" memory. This node has a particular
+  /// pessimestic structure.
+  Node Heap = NOT_A_NODE;
+  /// For var-args functions, denotes the block holding the parameters
+  Node VarArgs = NOT_A_NODE;
+  /// Partial map of Value* to Nodes
+  NodeMapT Map;
+  /// Nodes corresponding to formal arguments. Will be NOT_A_NODE
+  /// for non-pointer arguments
+  SmallVector<Node, 8> FormalArguments;
+  /// Collection of GlobalValues used in a function or in a called
+  /// function whose graph is inlined.
+  SmallVector<Value *, 8> GlobalsValues;
+  /// Nodes whose values may be returned from this function
+  SmallVector<Node, 4> ReturnedNodes;
+
+  void addEdgeAndInverse(Node From, Node To, EdgeType Type) {
+    addEdge(From, To, Type, flipLabel(Type));
+  }
+
+  Node findOrCreateNode(Value *Val) {
+
+    // Non-pointer values are assumed to refer to anywhere
+    // and this is modeled by mapping them to that unqiue Heap nodes
+    if (!Val->getType()->isPointerTy()) {
+      return Heap;
+    }
+    auto Pair = Map.insert(std::make_pair(Val, Node()));
+    auto &Iter = Pair.first;
+    if (Pair.second) {
+      auto NewNode = addNode();
+      if (isa<GlobalValue>(Val)) {
+        // Addresses of globals values may be assigned into heap memory by
+        // other other functions so we model that directly.
+        addEdge(NewNode, Heap, EdgeType::AssignTo, EdgeType::AssignFrom);
+        GlobalsValues.push_back(Val);
+      }
+      Iter->second = NewNode;
+    }
+    return Iter->second;
+  }
+
+  /// Initialize the unique heap nodes which is it's own dereference
+  /// and which is assigned to itself. We model unknown effects of called
+  /// functions and the calling context by assigning values to and from the heap
+  Node createHeap() {
+    if (Heap == NOT_A_NODE) {
+      Heap = addNode();
+      assert(Heap == 0 &&
+             "Heap node expected to be first node in PointerGraph");
+      addEdge(Heap, Heap, EdgeType::AssignTo, EdgeType::AssignFrom);
+      addEdge(Heap, Heap, EdgeType::Dereference, EdgeType::Reference);
+    }
+    return Heap;
+  }
+
+  /// Return the node corresponding to a value if it exists
+  Optional<Node> getNode(Value *V) const {
+    auto Iter = Map.find(V);
+    if (Iter == Map.end())
+      return None;
+    return Iter->second;
+  }
+
+  /// Return the "dereference" of a node, if it exists
+  /// There will be at most one such node.
+  Optional<Node> getDeref(Node N) const {
+    return firstSuccessorByType(N, EdgeType::Dereference);
+  }
+
+  /// Return the unique dereference successor of a node,
+  /// creating it if it does not already exist
+  Node findOrCreateDeref(Node N) {
+    if (auto Deref = getDeref(N))
+      return *Deref;
+    auto Deref = addNode();
+    addEdge(N, Deref, EdgeType::Dereference, EdgeType::Reference);
+    return Deref;
+  }
+
+#if ENABLE_EXPERIMENTS
+  /// A pointer graph is "simple" when every non-heap node has every
+  /// AssignTo edge and every Dereference pointing to the unique Heap node.
+  /// In a simple graph, we can simplify the search to just the two nodes
+  /// involved
+  bool isSimple() {
+    assert(Heap == 0);
+    for (auto N : nonHeapNodes()) {
+      for (auto E : edges(N)) {
+        if (E.Other != Heap)
+          return false;
+        if (E.Type != EdgeType::Dereference && E.Type != EdgeType::AssignTo)
+          return false;
+      }
+    }
+    return true;
+  }
+  /// In a "simple" graph, every node that is not the heap
+  /// has only AssignTo and Dereference edges which point to the heap
+  /// and no other edges. In this case, we can simplify the search:
+  /// two non-heap nodes are not aliased
+  /// a non-heap node aliases the heap if there is an assign edge to the heap
+  bool simpleMayAlias(Node A, Node B);
+#endif
+
+  /// A node N is an AddressRoot if it is not assigned from some other
+  /// node and is not the dereference of some other node.
+  bool isAddressRoot(Node N) {
+    for (auto E : edges(N))
+      if (E.Type == EdgeType::AssignFrom || E.Type == EdgeType::Reference)
+        return false;
+    return true;
+  }
+
+  /// Simple wrapper that iterates over all nodes except the Heap node.
+  class NonHeapNodes {
+    size_t N;
+
+  public:
+    NonHeapNodes(const PointerGraph &G) : N(G.size()) {}
+    NodeIterator begin() { return NodeIterator(1); }
+    NodeIterator end() { return NodeIterator(N); }
+  };
+  NonHeapNodes nonHeapNodes() const { return NonHeapNodes(*this); }
+
+  /// Perform compression on a graph to yield a new graph.
+  /// When \p ForInlining is true, then separate heuristics are used
+  /// for that scenario
+  PointerGraph compress(bool ForInlining);
+
+#ifndef NDEBUG
+  void dump(const Function &F, const AliasEquivClassMap *AliasEquivClass,
+            const class Combiner *DoCombining, const char *label,
+            bool PrintValues = true, Node ONLY_A = NOT_A_NODE,
+            Node ONLY_B = NOT_A_NODE) const;
+  /// Debugging aide: validate structure of the graph
+  void check(const char *label, const Function &Fn) const;
+#endif
+};
+
+/// Information computed from the base IR and retained for alias analysis
+/// and subsequence cross-procedure use.
+class GraphInfo {
+public:
+  /// The summary of pointer operations for a function.
+  PointerGraph Graph;
+  /// An equivalence relation on Values which conservatively approximates the
+  /// alias relation. If two values map to different classes, they are not
+  /// aliased
+  AliasEquivClassMap AliasEquivClass;
+
+  /// Return true if we A and B are known to be in distinct alias
+  /// equivalence classes.
+  bool distinctAliasEquivalenceClassses(Value *A, Value *B) {
+    auto AIter = AliasEquivClass.find(A);
+    if (AIter == AliasEquivClass.end())
+      return false;
+    auto BIter = AliasEquivClass.find(B);
+    if (BIter == AliasEquivClass.end())
+      return false;
+    if (AIter->second.Class != BIter->second.Class)
+      return true;
+    if (!DontUseAddressBases) {
+      // same class and same address root?
+      if (AIter->second.Address == BIter->second.Address)
+        return false;
+      // both are actually address roots?
+      if (AIter->second.Address != AliasEquivInfo::NOT_ADDRESS_ROOT &&
+          BIter->second.Address != AliasEquivInfo::NOT_ADDRESS_ROOT) {
+#ifndef ENABLE_EXPERIMENTS
+        FastViaAddressRoots += 1;
+#endif
+        return true;
+      }
+    }
+    return false;
+  }
+};
+
+struct BuilderEdge;
+
+/// This class does combining of nodes into equivalence classes supporting
+/// an precise reduction aimed at just reducing graph size and an imprecise
+/// scenario used to reduce query cost.
+class Combiner {
+  const PointerGraph &G;
+  static const Node MULTIPLE_SOURCES = (PointerGraph::NOT_A_NODE - 1);
+
+  struct Info {
+    /// State used to implement a disjoint-set union-find algorithm
+    Node Parent = PointerGraph::NOT_A_NODE;
+    bool isRoot() { return Parent == PointerGraph::NOT_A_NODE; }
+
+    /// We maintain an invariant that all Dereference edges from one
+    /// node class refer to the same node class, combining as needed.
+    Node Deref = PointerGraph::NOT_A_NODE;
+
+    /// We mark nodes "live" if they are needed in an output graph.
+    /// The exact semantics depend on whether we are compressiong for inlining
+    /// or alias testing.
+    bool IsLive = false;
+
+    /// Used to find the unique class which is the source of
+    /// AssignTo edges into the current class
+    Node Src;
+
+    /// Final alias class number
+    unsigned AliasClassNumber;
+    Info() {}
+    Info(Node Deref) : Deref(Deref) {}
+  };
+  std::vector<Info> NodeInfo;
+
+  /// Initialize NodeInfo and record dereference nodes
+  void initialize() {
+    NodeInfo.clear();
+    NodeInfo.reserve(G.size());
+    for (Node I : G) {
+      Node Deref = PointerGraph::NOT_A_NODE;
+      if (auto D = G.getDeref(I))
+        Deref = *D;
+      NodeInfo.emplace_back(Deref);
+    }
+  }
+
+  /// Return the root node for set containing A and perform
+  /// path compression on the tree.
+  Node getComponent(Node A) {
+    Node Root = A;
+    SmallVector<int, 16> Path;
+    for (;;) {
+      auto &Info = NodeInfo[Root];
+      if (Info.isRoot())
+        break;
+      Path.push_back(Root);
+      Root = Info.Parent;
+    }
+
+    // Path compression to reduce future query costs.
+    for (auto Cur : Path)
+      NodeInfo[Cur].Parent = Root;
+
+    return Root;
+  }
+  /// Return true if these nodes are in the same equivalence class.
+  bool sameClass(Node C1, Node C2) {
+    return getComponent(C1) == getComponent(C2);
+  }
+  /// Combine the components containing the single node and return
+  /// true a change is made.
+  bool combine(Node C1, Node C2) {
+    C1 = getComponent(C1);
+    C2 = getComponent(C2);
+    if (C1 == C2)
+      return false;
+
+    // This guarantees that the heap node 0 is a root
+    if (C1 > C2)
+      std::swap(C1, C2);
+    DEBUG_MSG("combine N" << C2 << " -> N" << C1);
+    assert(NodeInfo[C1].isRoot());
+    assert(NodeInfo[C2].isRoot());
+    auto D2 = NodeInfo[C2].Deref;
+    NodeInfo[C2].Parent = C1;
+    if (D2 != PointerGraph::NOT_A_NODE) {
+      auto D1 = NodeInfo[C1].Deref;
+      if (D1 == PointerGraph::NOT_A_NODE)
+        NodeInfo[C1].Deref = D2;
+      else
+        combine(D1, D2);
+    }
+    return true;
+  }
+
+  /// The number of classes after all combining.
+  unsigned NumClasses = 0;
+
+  /// Assign unique numbers to each final class which holds a live node.
+  void numberRoots() {
+    for (Node I : G)
+      if (NodeInfo[I].IsLive)
+        NodeInfo[getComponent(I)].IsLive = true;
+
+    for (Node I : G)
+      if (NodeInfo[I].isRoot() && NodeInfo[I].IsLive)
+        NodeInfo[I].AliasClassNumber = NumClasses++;
+  }
+
+  /// Mark as IsLive those nodes which are needed either for inlining
+  /// or for query support depending on the parameter.
+  void trimDead(bool TrimToFormals);
+
+  /// Walk the "heap" and nodes connected to it by assignment to find nodes
+  /// which are indistinguishable from the heap from an alias perspective.
+  void walkHeap();
+
+  /// Find unique assignment values into a equivalence class of nodes to allow
+  /// combining of assignment chains.
+  void walkAssignTrees();
+
+  /// Look at AssignFrom edges that target N and return the unique
+  /// source of those edges if there is one. MULTIPLE_SOURCES if there
+  /// are more than one source and NOT_A_NODE if there are none.
+  Node uniqueSource(Node N);
+
+public:
+  Combiner(const PointerGraph &G) : G(G){};
+  /// Combine nodes connected via assignment and
+  /// Dereferences from the common class
+  void doCombiningForEquivClasses();
+
+  /// Combine nodes to reduce size but without loss of CFL precision
+  void doCombiningForSize(bool TrimForInlining);
+
+  /// Return the final number of classes.
+  unsigned getNumClasses() const { return NumClasses; }
+
+  /// Get the equivalence class number for a graph node.
+  Node getIndex(Node Node) const {
+    while (NodeInfo[Node].Parent != PointerGraph::NOT_A_NODE)
+      Node = NodeInfo[Node].Parent;
+    auto &Info = NodeInfo[Node];
+    if (Info.IsLive)
+      return NodeInfo[Node].AliasClassNumber;
+    return PointerGraph::NOT_A_NODE;
+  };
+};
+
+/// This class translate the IR of a function into the GraphInfo
+class GraphBuilder : public GraphInfo {
+  Function *Fn;
+  CFLODAAResult &Analysis;
+  /// This graph will be used for callers who want to model the effects of call.
+  PointerGraph GraphToInline;
+#if ENABLE_EXPERIMENTS
+  /// This is the uncompressed graph used to verify optimizations.
+  PointerGraph FullGraph;
+#endif
+
+  /// Build the full graph from the input Function.
+  void buildGraph();
+
+  /// Process one instruction and add its effects to the graph.
+  void addInstructionToGraph(Instruction &Inst);
+
+  /// Get the edges of a ConstantExpr as if it was an Instruction. This
+  /// function also acts on any nested ConstantExprs, adding the edges
+  /// of those to the given SmallVector as well.
+  void constexprToEdges(ConstantExpr &CExprToCollapse,
+                        SmallVectorImpl<BuilderEdge> &Results);
+
+  void addEdgeToGraph(BuilderEdge E);
+  // Gets edges of the given Instruction*, writing them to the SmallVector*.
+  void argsToEdges(CFLODAAResult &, Instruction *,
+                   SmallVectorImpl<BuilderEdge> &);
+
+  // Gets edges of the given ConstantExpr*, writing them to the SmallVector*.
+  void argsToEdges(CFLODAAResult &, ConstantExpr *,
+                   SmallVectorImpl<BuilderEdge> &);
+
+  // Convert to pessimestic assumptions for pointer parameters that they
+  // are initialized from the heap.
+  void convertFormalArgumentsToHeap();
+
+  // Support for compressing the graph by combining nodes and for
+  // determing equivalance classes
+  Combiner DoCombining;
+
+  static bool hasUsefulEdges(Instruction *Inst);
+  static bool hasUsefulEdges(ConstantExpr *CE);
+
+  // Some instructions need to have their users tracked. Instructions like
+  // `add` require you to get the users of the Instruction* itself, other
+  // instructions like `store` require you to get the users of the first
+  // operand. This function gets the "proper" value to track for each
+  // type of instruction we support.
+  static Optional<Value *> getTargetValue(Instruction *Inst);
+
+public:
+  GraphBuilder(Function *Fn, CFLODAAResult &Analysis)
+      : Fn(Fn), Analysis(Analysis), DoCombining(Graph) {}
+
+  /// Build the abstract pointer operation graph and reduce it to an
+  /// approximate equivalence relation expressed as a mapping of Value* to
+  /// numbers.
+  void buildGraphAndEquivalences();
+#ifndef NDEBUG
+  const Combiner &getCombiner() { return DoCombining; }
+#endif
+  PointerGraph &getGraphToInline() { return GraphToInline; }
+#if ENABLE_EXPERIMENTS
+  PointerGraph &getFullGraph() { return FullGraph; }
+#endif
+  GraphInfo &getGraph() { return *this; }
+};
+}
+
+/// Information needed during alias analysis.
+struct AliasInfo : public GraphInfo {
+  const char *DebugLabel;
+#if ENABLE_EXPERIMENTS
+  /// True when the graph is "simple" accoring to the definition above.
+  bool SimpleGraph;
+  /// As we discover aliases between nodes, we can reuse them
+  /// in subsequent queries.
+  DenseMap<Node, std::set<Node>> AliasMem;
+
+  /// True if we have fully resolved the aliases of some node.
+  std::vector<bool> AliasesKnown;
+#endif
+
+#if !ENABLE_EXPERIMENTS
+  /// Constructor for compressed graph.
+  AliasInfo(GraphInfo *Graph) {
+    AliasEquivClass = std::move(Graph->AliasEquivClass);
+  }
+#else
+  AliasInfo(GraphInfo *Graph)
+      : GraphInfo(std::move(*Graph)), DebugLabel(""),
+        AliasesKnown(GraphInfo::Graph.size(), false) {
+    SimpleGraph = this->Graph.isSimple();
+  }
+  /// Constructor for the "full graph".
+  AliasInfo(PointerGraph *Graph)
+      : DebugLabel("full"), AliasesKnown(Graph->size(), false) {
+    GraphInfo::Graph = std::move(*Graph);
+    SimpleGraph = false;
+  }
+#endif
+  // True if the two values may refer to the same memory location and
+  // false otherwise.
+  bool mayAlias(Value *p1, Value *p2);
+#if ENABLE_EXPERIMENTS
+  // Diagnostic only, count number of search steps.
+  unsigned SearchCount = 0;
+#endif
+};
+
+/// Information we have about a function and keep around to enable
+/// alias testing.
+struct CFLODAAResult::FunctionInfo : public AliasInfo {
+
+  /// This graph will be used for callers who want
+  /// to model the effects of call.
+  PointerGraph GraphToInline;
+#if SEARCH_FULL_GRAPH
+  /// The uncompressed graph, used to validate the compression and to
+  /// measure loss of procession.
+  AliasInfo FullInfo;
+#endif
+
+#ifndef NDEBUG
+  /// Name of the function, for diagnostic output only.
+  std::string FunctionName;
+#endif
+  FunctionInfo(GraphBuilder *Info)
+      : AliasInfo(&Info->getGraph()),
+        GraphToInline(std::move(Info->getGraphToInline()))
+#if SEARCH_FULL_GRAPH
+        ,
+        FullInfo(&Info->getFullGraph())
+#endif
+  {
+  }
+
+#ifndef NDEBUG
+  /// Per function count of number of queries
+  unsigned QueryCount = 0;
+  /// Per function number of MayAlias calls
+  unsigned MayAliasCount = 0;
+  /// Report per-function diagnostics.
+  void report(Function *F);
+#endif
+};
+
+//===----------------------------------------------------------------------===//
+//
+//
+//  Code related to building an abstract pointer operation graph
+//
+//
+//===----------------------------------------------------------------------===//
+
+void GraphBuilder::buildGraphAndEquivalences() {
+
+  DEBUG(DebugDump = true);
+#ifndef NDEBUG
+  if (DebugDump)
+    dumpCFG(*Fn);
+#endif
+
+  // Build the "full" operation graph.
+  buildGraph();
+
+  // Compress down to equivalence classes
+  DoCombining.doCombiningForEquivClasses();
+#ifndef NDEBUG
+  if (DebugDumpNonSimple && !Graph.isSimple())
+    Graph.dump(*Fn, &AliasEquivClass, &DoCombining, "");
+#endif
+
+  // Save map of Values to equivance class information.
+  for (const auto &P : Graph.Map) {
+    auto V = P.first;
+    auto N = P.second;
+    auto C = DoCombining.getIndex(N);
+    unsigned Address = AliasEquivInfo::NOT_ADDRESS_ROOT;
+    if (Graph.isAddressRoot(N))
+      Address = N;
+    AliasEquivClass.insert(std::make_pair(V, AliasEquivInfo(C, Address)));
+  }
+
+#ifdef LLVM_ENABLE_STATS
+  // Compute graph size for statistics.
+  unsigned S = Graph.size();
+  for (size_t N = 0; N < Graph.size(); ++N)
+    S += Graph.edges(N).size();
+
+  TotalGraphSize += S;
+  MaxGraphSize = std::max<unsigned>(MaxGraphSize, S);
+#endif
+}
+
+void GraphBuilder::buildGraph() {
+
+  Graph.createHeap();
+
+  // Create nodes for formal arguments.
+  for (auto &Arg : Fn->args()) {
+    Node ArgNode = (Arg.getType()->isPointerTy() ? Graph.findOrCreateNode(&Arg)
+                                                 : PointerGraph::NOT_A_NODE);
+    Graph.FormalArguments.push_back(ArgNode);
+  }
+
+  // Create nodes and edges for each instruction and called function.
+  for (auto &Bb : Fn->getBasicBlockList())
+    for (auto &Inst : Bb.getInstList())
+      addInstructionToGraph(Inst);
+
+#ifndef NDEBUG
+  Graph.check("full", *Fn);
+#endif
+
+  // Save a compressed version of this graph for later inlining.
+  GraphToInline = Graph.compress(/*TrimForInlining*/ true);
+#ifndef NDEBUG
+  GraphToInline.check("inline", *Fn);
+  if (DebugDump)
+    GraphToInline.dump(*Fn, nullptr, nullptr, "-inline");
+#endif
+
+  // Make pessimestic assumptions about formal parameters.
+  convertFormalArgumentsToHeap();
+#ifndef NDEBUG
+  if (DebugDump)
+    Graph.dump(*Fn, nullptr, nullptr, "-full");
+#endif
+#if SEARCH_FULL_GRAPH
+  if (FullGraphSearch) {
+    FullGraph = std::move(Graph);
+    Graph = FullGraph.compress(/*TrimForInlining*/ false);
+  } else
+#endif
+    Graph = Graph.compress(/*TrimForInlining*/ false);
+#ifndef NDEBUG
+  Graph.check("final", *Fn);
+#endif
+}
+
+namespace {
+/// Encodes the notion of a "use" while we are building
+/// the pointer abstraction graph.
+struct BuilderEdge {
+
+  /// Storing HEAP_VALUE to either From or To refers to an "unknown" value and
+  /// it will be translated into the Heap node.
+  constexpr static Value *const HEAP_VALUE = nullptr;
+  Value *From;
+  Value *To;
+  EdgeType Type;
+
+  BuilderEdge(Value *From, Value *To, EdgeType Type)
+      : From(From), To(To), Type(Type) {}
+};
+}
+
+// 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 GraphBuilder::addInstructionToGraph(Instruction &Inst) {
+  NumInstructions += 1;
+#ifndef NDEBUG
+  if (!NoLabels)
+    DEBUG_INST("add: " << (void *)&Inst << ' ', Inst);
+#endif
+  if (!hasUsefulEdges(&Inst))
+    return;
+
+  SmallVector<BuilderEdge, 8> Edges;
+
+  // Based on isntruction type, get a list of edges that should be
+  // part of the graph. This list is a little more general in form than
+  // the final graph.
+  argsToEdges(Analysis, &Inst, Edges);
+
+  // In the case of an unused alloca (or similar), edges may be empty. Remember
+  // that it exists so we can potentially answer NoAlias.
+  if (Edges.empty()) {
+    auto MaybeVal = getTargetValue(&Inst);
+    assert(MaybeVal.hasValue());
+    auto *Target = *MaybeVal;
+    DEBUG_MSG("\tedges empty, target");
+    Graph.findOrCreateNode(Target);
+    return;
+  }
+
+  if (isa<ReturnInst>(&Inst)) {
+    assert(Edges.size() == 1);
+    auto *From = Edges[0].From;
+    if (From->getType()->isPointerTy())
+      Graph.ReturnedNodes.push_back(Graph.findOrCreateNode(From));
+    // TODO: assign to heap?
+    return;
+  }
+
+  // Find ConstantExpr's referneced by this Instruction.
+  SmallVector<ConstantExpr *, 4> ConstantExprs;
+  for (const BuilderEdge &E : Edges) {
+    if (E.To != BuilderEdge::HEAP_VALUE)
+      if (auto *Constexpr = dyn_cast<ConstantExpr>(E.To))
+        ConstantExprs.push_back(Constexpr);
+    if (E.From != BuilderEdge::HEAP_VALUE)
+      if (auto *Constexpr = dyn_cast<ConstantExpr>(E.From))
+        ConstantExprs.push_back(Constexpr);
+  }
+
+  // Avoid creating nodes which are single-source assignments by mapping
+  // this value to the same as the source.
+  if (Edges.size() == 1 && ConstantExprs.empty()) {
+    auto E = Edges[0];
+    if (E.From == &Inst && E.To != BuilderEdge::HEAP_VALUE &&
+        E.Type == EdgeType::AssignFrom &&
+        Graph.Map.find(E.From) == Graph.Map.end()) {
+      Graph.Map[E.From] = Graph.findOrCreateNode(Edges[0].To);
+      return;
+    }
+  }
+
+  for (const BuilderEdge &E : Edges)
+    addEdgeToGraph(E);
+
+  // Walk the ConstantExpr looking for
+  for (ConstantExpr *CE : ConstantExprs) {
+    Edges.clear();
+    constexprToEdges(*CE, Edges);
+    for (auto &Edge : Edges)
+      addEdgeToGraph(Edge);
+  }
+}
+
+namespace {
+
+/// Get the edges the graph should have, based on an Instruction.
+class GetEdgesVisitor : public InstVisitor<GetEdgesVisitor, void> {
+
+  /// We give access to this result for cross-procedural cases
+  /// where we inline the graph for corresponding to the called function
+  CFLODAAResult &AA;
+  /// The graph we are currently building to handle cases where it
+  /// is expedient to directly add edges.
+  PointerGraph &Graph;
+  /// We capture the effecits of an instruciton as a set of
+  /// edges which will be added to Graph.
+  SmallVectorImpl<BuilderEdge> &Output;
+
+public:
+  GetEdgesVisitor(CFLODAAResult &AA, PointerGraph &Graph,
+                  SmallVectorImpl<BuilderEdge> &Output)
+      : AA(AA), Graph(Graph), Output(Output) {}
+
+  void visitInstruction(Instruction &) {
+    llvm_unreachable("Unsupported instruction encountered");
+  }
+
+  void visitReturnInst(ReturnInst &Inst) {
+    if (Inst.getNumOperands()) {
+      auto *Ptr = Inst.getOperand(0);
+      Output.emplace_back(Ptr, &Inst, EdgeType::AssignTo);
+    }
+  }
+
+  void visitPtrToIntInst(PtrToIntInst &Inst) {
+    auto *Ptr = BuilderEdge::HEAP_VALUE;
+    Output.emplace_back(Inst.getOperand(0), Ptr, EdgeType::AssignTo);
+  }
+
+  void visitIntToPtrInst(IntToPtrInst &Inst) {
+    auto *Ptr = BuilderEdge::HEAP_VALUE;
+    Output.emplace_back(Ptr, &Inst, EdgeType::AssignTo);
+  }
+
+  void visitCastInst(CastInst &Inst) {
+    Output.emplace_back(&Inst, Inst.getOperand(0), EdgeType::AssignFrom);
+  }
+
+  void visitBinaryOperator(BinaryOperator &Inst) {
+    Output.emplace_back(&Inst, Inst.getOperand(0), EdgeType::AssignFrom);
+    Output.emplace_back(&Inst, Inst.getOperand(1), EdgeType::AssignFrom);
+  }
+
+  void visitAtomicCmpXchgInst(AtomicCmpXchgInst &Inst) {
+    auto *Ptr = Inst.getPointerOperand();
+    auto *Val = Inst.getNewValOperand();
+    Output.emplace_back(Val, Ptr, EdgeType::Store);
+  }
+
+  void visitAtomicRMWInst(AtomicRMWInst &Inst) {
+    auto *Ptr = Inst.getPointerOperand();
+    auto *Val = Inst.getValOperand();
+    Output.emplace_back(Val, Ptr, EdgeType::Store);
+  }
+
+  void visitPHINode(PHINode &Inst) {
+    for (Value *Val : Inst.incoming_values())
+      Output.emplace_back(&Inst, Val, EdgeType::AssignFrom);
+  }
+
+  void visitGetElementPtrInst(GetElementPtrInst &Inst) {
+    auto *Op = Inst.getPointerOperand();
+    Output.emplace_back(&Inst, Op, EdgeType::AssignFrom);
+    if (isa<ConstantExpr>(&Inst))
+      return;
+
+    // We assume here that the other inputs to the operations are
+    // values which do not change the object that is referenced. We can
+    // ignore them be cause we don't attempt to differentiate locations
+    // within an object.
+    if (Inst.isInBounds() || !UnsafeAddressing)
+      return;
+
+    for (auto I = Inst.idx_begin(), E = Inst.idx_end(); I != E; ++I)
+      Output.emplace_back(&Inst, *I, EdgeType::AssignFrom);
+  }
+
+  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();
+    Output.emplace_back(&Inst, TrueVal, EdgeType::AssignFrom);
+    auto *FalseVal = Inst.getFalseValue();
+    Output.emplace_back(&Inst, FalseVal, EdgeType::AssignFrom);
+
+    // we don't have to worry about the condition (or any control dependence)
+    // since a pointer value would be cast to int and hence escaped.
+  }
+
+  void visitAllocaInst(AllocaInst &) {}
+
+  void visitLoadInst(LoadInst &Inst) {
+    auto *Ptr = Inst.getPointerOperand();
+    auto *Val = &Inst;
+    Output.emplace_back(Val, Ptr, EdgeType::Reference);
+  }
+
+  void visitStoreInst(StoreInst &Inst) {
+    auto *Ptr = Inst.getPointerOperand();
+    auto *Val = Inst.getValueOperand();
+    Output.emplace_back(Val, Ptr, EdgeType::Store);
+  }
+
+  void visitVAArgInst(VAArgInst &Inst) {
+    // cdc: todo
+    // 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).
+    assert(0 && "unexpected VAArgInst");
+    auto *Val = &Inst;
+    auto *Ptr = BuilderEdge::HEAP_VALUE;
+    Output.emplace_back(Ptr, Val, EdgeType::AssignTo);
+  }
+
+  static bool isFunctionExternal(Function *Fn) {
+    return !Fn->hasExactDefinition();
+  }
+
+  // Returns possible functions called by the Inst* into the given
+  // SmallVectorImpl. Returns true if targets found, false otherwise.
+  // This is templated because InvokeInst/CallInst give us the same
+  // set of functions that we care about, and I don't like repeating
+  // myself.
+  template <typename Inst>
+  static bool getPossibleTargets(Inst *Call,
+                                 SmallVectorImpl<Function *> &Output) {
+    if (auto *Fn = Call->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;
+  }
+
+  bool
+  tryInterproceduralAnalysis(Function *Fn, Value *FuncValue,
+                             const iterator_range<User::op_iterator> &Args);
+  bool handleIntrinsic(Intrinsic::ID ID, Value *FuncValue,
+                       const iterator_range<User::op_iterator> &Args);
+  template <typename InstT> void visitCallLikeInst(InstT &Inst);
+
+  void visitCallInst(CallInst &Inst);
+  void visitInvokeInst(InvokeInst &Inst) { visitCallLikeInst(Inst); }
+
+  // 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) {
+    UNTESTED("CFL -- ExtractElementInst");
+    auto *Ptr = Inst.getVectorOperand();
+    auto *Val = &Inst;
+    Output.emplace_back(Val, Ptr, EdgeType::Reference);
+  }
+
+  void visitInsertElementInst(InsertElementInst &Inst) {
+    UNTESTED("CFL -- InsertElementInst");
+    auto *Vec = Inst.getOperand(0);
+    auto *Val = Inst.getOperand(1);
+    Output.emplace_back(&Inst, Vec, EdgeType::AssignFrom);
+    Output.emplace_back(&Inst, Val, EdgeType::Dereference);
+  }
+
+  void visitLandingPadInst(LandingPadInst &Inst) {
+    UNTESTED("CFL -- LandingPadInst");
+    // Exceptions come from "nowhere", from our analysis' perspective.
+    // So we place the instruction its own group, noting that said group may
+    // alias externals
+    Output.emplace_back(&Inst, &Inst, EdgeType::AssignFrom);
+  }
+
+  void visitInsertValueInst(InsertValueInst &Inst) {
+    UNTESTED("CFL -- InsertValueInst");
+    auto *Agg = Inst.getOperand(0);
+    auto *Val = Inst.getOperand(1);
+    Output.emplace_back(&Inst, Agg, EdgeType::Store);
+    Output.emplace_back(&Inst, Val, EdgeType::Dereference);
+  }
+
+  void visitExtractValueInst(ExtractValueInst &Inst) {
+    UNTESTED("CFL -- ExtractValueInst");
+    auto *Ptr = Inst.getAggregateOperand();
+    Output.emplace_back(&Inst, Ptr, EdgeType::Reference);
+  }
+
+  void visitShuffleVectorInst(ShuffleVectorInst &Inst) {
+    UNTESTED("CFL -- ShuffleVectorInst");
+    auto *From1 = Inst.getOperand(0);
+    auto *From2 = Inst.getOperand(1);
+    Output.emplace_back(&Inst, From1, EdgeType::AssignFrom);
+    Output.emplace_back(&Inst, From2, EdgeType::AssignFrom);
+  }
+
+  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"
+    }
+  }
+};
+
+void GraphBuilder::argsToEdges(CFLODAAResult &Analysis, Instruction *Inst,
+                               SmallVectorImpl<BuilderEdge> &Output) {
+  assert(hasUsefulEdges(Inst) &&
+         "Expected instructions to have 'useful' edges");
+  GetEdgesVisitor v(Analysis, Graph, Output);
+  v.visit(Inst);
+}
+
+void GraphBuilder::argsToEdges(CFLODAAResult &Analysis, ConstantExpr *CE,
+                               SmallVectorImpl<BuilderEdge> &Output) {
+  assert(hasUsefulEdges(CE) && "Expected constant expr to have 'useful' edges");
+  GetEdgesVisitor v(Analysis, Graph, Output);
+  v.visitConstantExpr(CE);
+}
+
+void GetEdgesVisitor::visitCallInst(CallInst &Inst) {
+  if (auto *F = Inst.getCalledFunction()) {
+    if (F->getIntrinsicID() == Intrinsic::vastart) {
+      if (auto *Op = Inst.getArgOperand(0)) {
+        // This operation initalize the result to hold a pointer
+        // into the block of memory on the stack holding parameteters.
+        if (Graph.VarArgs == PointerGraph::NOT_A_NODE) {
+          Graph.VarArgs = Graph.addNode();
+          Graph.addEdge(Graph.Heap, Graph.findOrCreateDeref(Graph.VarArgs),
+                        EdgeType::AssignTo, EdgeType::AssignFrom);
+        }
+        auto From = Graph.VarArgs;
+        auto To = Graph.findOrCreateDeref(Graph.findOrCreateNode(Op));
+        Graph.addEdge(From, To, EdgeType::AssignTo, EdgeType::AssignFrom);
+        return;
+      }
+    }
+  }
+  visitCallLikeInst(Inst);
+}
+
+template <typename InstT> void GetEdgesVisitor::visitCallLikeInst(InstT &Inst) {
+
+  if (isNoAliasCall(&Inst))
+    return;
+
+  SmallVector<Function *, 4> Targets;
+  if (getPossibleTargets(&Inst, Targets) && Targets.size() == 1) {
+
+    // If we can resolve the target, or a set of possible targets
+    // we can handle them as intrinstics or via inlining.
+    auto TryInterprocedural = [this, &Inst](Function *Fn) {
+      if (Intrinsic::ID ID = Fn->getIntrinsicID()) {
+        if (handleIntrinsic(ID, &Inst, Inst.arg_operands()))
+          return true;
+      } else if (!Fn->isDeclaration()) {
+        if (tryInterproceduralAnalysis(Fn, &Inst, Inst.arg_operands()))
+          return true;
+      }
+      return false;
+    };
+
+    // If we handle all targets, we are done, otherwise fall through
+    // to the pessimestic case
+    if (std::all_of(Targets.begin(), Targets.end(), TryInterprocedural))
+      return;
+  }
+
+  // Because the function is opaque, we need to note that anything
+  // could have happened to the arguments, and that the result could alias
+  // just about anything, too.
+  auto *HeapPtr = BuilderEdge::HEAP_VALUE;
+  for (Value *V : Inst.arg_operands())
+    if (V->getType()->isPointerTy())
+      Output.emplace_back(V, HeapPtr, EdgeType::AssignTo);
+  if (Inst.getType()->isPointerTy())
+    Output.emplace_back(HeapPtr, &Inst, EdgeType::AssignTo);
+}
+
+bool GetEdgesVisitor::handleIntrinsic(
+    Intrinsic::ID ID, llvm::Value *FuncValue,
+    const iterator_range<User::op_iterator> &Args) {
+
+  bool HasPointerArg = false;
+  for (auto &Arg : Args) {
+    if (Arg->getType()->isPointerTy())
+      HasPointerArg = true;
+  }
+
+  switch (ID) {
+  case Intrinsic::memmove:
+  case Intrinsic::memcpy: {
+    auto Iter = Args.begin();
+    auto &Dest = *(*Iter++);
+    auto &Source = *(*Iter);
+    // *Dest = *Source
+    Graph.addEdge(Graph.findOrCreateDeref(Graph.findOrCreateNode(&Source)),
+                  Graph.findOrCreateDeref(Graph.findOrCreateNode(&Dest)),
+                  EdgeType::AssignTo, EdgeType::AssignFrom);
+    return true;
+  }
+  case Intrinsic::vacopy: {
+    auto Iter = Args.begin();
+    auto &Dest = *(*Iter++);
+    auto &Source = *(*Iter);
+    Graph.addEdge(Graph.findOrCreateNode(&Source),
+                  Graph.findOrCreateNode(&Dest), EdgeType::AssignTo,
+                  EdgeType::AssignFrom);
+    return true;
+  }
+  case Intrinsic::dbg_value:
+  case Intrinsic::dbg_declare:
+  case Intrinsic::memset:
+  case Intrinsic::lifetime_start:
+  case Intrinsic::lifetime_end:
+  case Intrinsic::invariant_start:
+  case Intrinsic::invariant_end:
+  case Intrinsic::eh_typeid_for:
+  case Intrinsic::vaend:
+  case Intrinsic::vastart:
+  case Intrinsic::objectsize:
+  case Intrinsic::stackrestore:
+  case Intrinsic::prefetch:
+  case Intrinsic::x86_sse_stmxcsr:
+    return true;
+  case Intrinsic::fabs:
+  default:
+    if (HasPointerArg) {
+      dbgs() << "unhandled intrinsic ";
+      FuncValue->dump();
+    }
+    return false;
+  }
+}
+
+bool GetEdgesVisitor::tryInterproceduralAnalysis(
+    Function *Fn, Value *FuncValue,
+    const iterator_range<User::op_iterator> &Args) {
+
+  auto InfoPtr = AA.ensureCached(Fn);
+  if (InfoPtr == nullptr) {
+    DEBUG_MSG("no inline, recursive: " << Fn->getName());
+    // TODO -- handle direct recursion
+    return false;
+  }
+
+  if (Fn->isVarArg()) {
+    // TODO -- handle var args
+    DEBUG_MSG("no inline, var args: " << Fn->getName());
+    return false;
+  }
+
+  // Copy the "GraphToInline" from the called function
+  // to the caller and then assign actuals to formals
+  // and returned values to the return node.
+
+  auto &CalledGraph = InfoPtr->GraphToInline;
+  assert(CalledGraph.VarArgs == PointerGraph::NOT_A_NODE);
+  if (CalledGraph.size() > InlineLimit) {
+    DEBUG_MSG("no inline, size: " << CalledGraph.size() << " "
+                                  << Fn->getName());
+    return false;
+  }
+
+  std::vector<Node> InlineNodeMap(CalledGraph.size(),
+                                  Node(PointerGraph::NOT_A_NODE));
+  InlineNodeMap[CalledGraph.Heap] = Graph.Heap;
+
+  // Map common global references to their existing nodes, if any.
+  for (auto Global : CalledGraph.GlobalsValues) {
+    auto New = Graph.findOrCreateNode(Global);
+    auto Old = CalledGraph.getNode(Global);
+    assert(Old.hasValue());
+    InlineNodeMap[*Old] = New;
+    if (auto NewDeref = Graph.getDeref(New))
+      if (auto OldDeref = CalledGraph.getDeref(*Old))
+        InlineNodeMap[*OldDeref] = *NewDeref;
+  }
+
+  // Create new nodes for non-globals in the inline graph.
+  auto InlineNodeMapIter = InlineNodeMap.begin();
+  for (Node N : CalledGraph) {
+    auto &Image = *InlineNodeMapIter;
+    ++InlineNodeMapIter;
+    if (Image != PointerGraph::NOT_A_NODE)
+      continue;
+    const auto &Edges = CalledGraph.edges(N);
+    if (Edges.size() == 1 && Edges[0].Type == EdgeType::Dereference)
+      continue;
+    Image = Graph.addNode();
+  }
+  // Create new nodes for the return nodes in the called graph.
+  for (Node R : CalledGraph.ReturnedNodes) {
+    auto &Image = InlineNodeMap[R];
+    if (Image != PointerGraph::NOT_A_NODE)
+      continue;
+    Image = Graph.addNode();
+  }
+
+  // Build edges for the copy of the graph.
+  for (Node N : CalledGraph) {
+    auto NewN = InlineNodeMap[N];
+    if (NewN == PointerGraph::NOT_A_NODE)
+      continue;
+
+    DEBUG_MSG("inline N" << N << " -> N" << NewN);
+    for (auto E : CalledGraph.edges(N)) {
+      auto NewOther = InlineNodeMap[E.Other];
+      if (NewOther == PointerGraph::NOT_A_NODE)
+        continue;
+      if (NewN == NewOther && NewN == Graph.Heap)
+        continue;
+      if (E.Type == EdgeType::Dereference)
+        if (auto Deref = Graph.getDeref(NewN)) {
+          assert(*Deref == NewOther);
+          continue;
+        }
+      Graph.addEdge(NewN, NewOther, E.Type);
+    }
+  }
+
+  // Simulate assignment of actuals to formals.
+  auto FormalsIter = CalledGraph.FormalArguments.begin();
+  for (auto &Arg : Args) {
+    if (FormalsIter == CalledGraph.FormalArguments.end())
+      break;
+
+    Value *ArgVal = &*Arg;
+    auto Formal = *FormalsIter++;
+    bool ActualIsPointer = ArgVal->getType()->isPointerTy();
+    Node ActualNode = Graph.Heap;
+    if (Formal == PointerGraph::NOT_A_NODE) {
+      if (!ActualIsPointer)
+        continue;
+      Formal = Graph.Heap;
+    } else {
+      Formal = InlineNodeMap[Formal];
+      if (Formal == PointerGraph::NOT_A_NODE) {
+        // A formal which is simply dereferenced but
+        // never assigned to any other value is ignored.
+        continue;
+      }
+    }
+    if (!ActualIsPointer)
+      ActualNode = Graph.Heap;
+    else
+      ActualNode = Graph.findOrCreateNode(ArgVal);
+    Graph.addEdge(ActualNode, Formal, EdgeType::AssignTo, EdgeType::AssignFrom);
+  }
+
+  /// Simulate assignment of the return value.
+  Node Result =
+      (FuncValue->getType()->isPointerTy() ? Graph.findOrCreateNode(FuncValue)
+                                           : Graph.Heap);
+  for (auto R : CalledGraph.ReturnedNodes)
+    Graph.addEdge(InlineNodeMap[R], Result, EdgeType::AssignTo,
+                  EdgeType::AssignFrom);
+  return true;
+}
+
+/// For a given instruction, we need to know which Value* to get the
+/// users of in order to build our graph. In some cases (i.e. add),
+/// we simply need the Instruction*. In other cases (i.e. store),
+/// finding the users of the Instruction* is useless; we need to find
+/// the users of the first operand. This handles determining which
+/// value to follow for us.
+///
+/// Note: we *need* to keep this in sync with GetEdgesVisitor. Add
+/// something to GetEdgesVisitor, add it here -- remove something from
+/// GetEdgesVisitor, remove it here.
+class GetTargetValueVisitor
+    : public InstVisitor<GetTargetValueVisitor, Value *> {
+public:
+  Value *visitInstruction(Instruction &Inst) { return &Inst; }
+
+  Value *visitStoreInst(StoreInst &Inst) { return Inst.getPointerOperand(); }
+
+  Value *visitAtomicCmpXchgInst(AtomicCmpXchgInst &Inst) {
+    return Inst.getPointerOperand();
+  }
+
+  Value *visitAtomicRMWInst(AtomicRMWInst &Inst) {
+    return Inst.getPointerOperand();
+  }
+
+  Value *visitInsertElementInst(InsertElementInst &Inst) {
+    return Inst.getOperand(0);
+  }
+
+  Value *visitInsertValueInst(InsertValueInst &Inst) {
+    return Inst.getAggregateOperand();
+  }
+};
+
+} // anonymous namespace
+
+Optional<Value *> GraphBuilder::getTargetValue(Instruction *Inst) {
+  GetTargetValueVisitor V;
+  return V.visit(Inst);
+}
+
+bool GraphBuilder::hasUsefulEdges(Instruction *Inst) {
+  // There are certain instructions (i.e. FenceInst, etc.) that we ignore.
+  bool IsNonInvokeTerminator = isa<TerminatorInst>(Inst) &&
+                               !isa<InvokeInst>(Inst) && !isa<ReturnInst>(Inst);
+  return !isa<CmpInst>(Inst) && !isa<FenceInst>(Inst) && !IsNonInvokeTerminator;
+}
+
+bool GraphBuilder::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;
+}
+
+// TODO: should this simply test the type of the value? We perhaps simply ignore
+//   non-pointer constatns.
+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)) {
+    bool Container = isa<ConstantVector>(Val) || isa<ConstantArray>(Val) ||
+                     isa<ConstantStruct>(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) || Container;
+    return !CanStoreMutableData;
+  }
+
+  return false;
+}
+
+void GraphBuilder::addEdgeToGraph(BuilderEdge E) {
+  if (E.Type == EdgeType::Reference || E.Type == EdgeType::AssignFrom) {
+    std::swap(E.From, E.To);
+    E.Type = flipLabel(E.Type);
+  }
+  // Generally we ignore assignments from constants
+  // to avoid tangling parts of the graph with
+  // values which are not pointers.
+  if (E.From != BuilderEdge::HEAP_VALUE && canSkipAddingToSets(E.From)) {
+    // Build the derference incase the source address is a global variable
+    // that we want to inlcude in the analysis.
+    if (E.Type == EdgeType::Store)
+      Graph.findOrCreateDeref(Graph.findOrCreateNode(E.To));
+    return;
+  }
+  // There should be only one "*p" node for a given 'p'
+  // so rewrite   p ->deref q to be  p -> deref *p -> assign q.
+  auto From =
+      (E.From != BuilderEdge::HEAP_VALUE ? Graph.findOrCreateNode(E.From)
+                                         : Graph.Heap);
+  auto To = (E.To != BuilderEdge::HEAP_VALUE ? Graph.findOrCreateNode(E.To)
+                                             : Graph.Heap);
+
+  if (E.Type == EdgeType::Dereference) {
+    // x = *p, we create the '*p' node and the assign it to the node for 'x'.
+    From = Graph.findOrCreateDeref(From);
+    E.Type = EdgeType::AssignTo;
+  } else if (E.Type == EdgeType::Store) {
+    // *p = x,  we create the '*p' node and assign the value 'x' to it.
+    To = Graph.findOrCreateDeref(To);
+    E.Type = EdgeType::AssignTo;
+  }
+
+  if (To != Graph.Heap || From != Graph.Heap) {
+    auto FlippedLabel = flipLabel(E.Type);
+    DEBUG_MSG("edge (" << From << "," << To << ") " << E.Type);
+    Graph.addEdge(From, To, E.Type, FlippedLabel);
+  }
+}
+
+void GraphBuilder::constexprToEdges(ConstantExpr &CExprToCollapse,
+                                    SmallVectorImpl<BuilderEdge> &Results) {
+  SmallVector<ConstantExpr *, 4> Worklist;
+  Worklist.push_back(&CExprToCollapse);
+
+  SmallVector<BuilderEdge, 8> ConstexprEdges;
+  SmallPtrSet<ConstantExpr *, 4> Visited;
+  while (!Worklist.empty()) {
+    auto *CExpr = Worklist.pop_back_val();
+
+    if (!hasUsefulEdges(CExpr))
+      continue;
+
+    ConstexprEdges.clear();
+    argsToEdges(Analysis, CExpr, ConstexprEdges);
+    for (auto &Edge : ConstexprEdges) {
+      if (Edge.From != BuilderEdge::HEAP_VALUE)
+        if (auto *Nested = dyn_cast<ConstantExpr>(Edge.From))
+          if (Visited.insert(Nested).second)
+            Worklist.push_back(Nested);
+
+      if (Edge.To != BuilderEdge::HEAP_VALUE)
+        if (auto *Nested = dyn_cast<ConstantExpr>(Edge.To))
+          if (Visited.insert(Nested).second)
+            Worklist.push_back(Nested);
+    }
+
+    Results.append(ConstexprEdges.begin(), ConstexprEdges.end());
+  }
+}
+
+void GraphBuilder::convertFormalArgumentsToHeap() {
+
+  // To model an arbitrary call, we assume formal paramters are
+  // initialized from heap with special handling of var-args.
+
+  auto FormalP = Graph.FormalArguments.begin();
+  for (auto &Arg : Fn->args()) {
+    auto ArgNode = *FormalP++;
+    if (ArgNode == PointerGraph::NOT_A_NODE)
+      continue;
+    if (!Arg.hasNoAliasAttr()) {
+      Graph.addEdgeAndInverse(Graph.Heap, ArgNode, EdgeType::AssignTo);
+      continue;
+    }
+    // Here we model no-alias as pointing to a unique
+    // abstract location which is then tangled with the heap
+    // this allows the pointer value to be stored in a local
+    // temporary and read out of that temporary without losing
+    // the no-alias property. On the other hand, it allows the value
+    // to be stored in a local variable and then reused and it is not
+    // clear of the value retains the no-alias property once it has
+    // been filtered through another programmer-visible name.
+    auto Deref = Graph.findOrCreateDeref(ArgNode);
+    Graph.addEdgeAndInverse(Deref, Graph.Heap, EdgeType::AssignTo);
+    Graph.addEdgeAndInverse(Graph.Heap, Deref, EdgeType::AssignTo);
+  }
+}
+
+//===----------------------------------------------------------------------===//
+//
+//
+//  Code related to compressing an abstract pointer operation graph
+//
+//
+//===----------------------------------------------------------------------===//
+namespace {
+template <typename T1, typename T2, typename UnaryOp>
+void transform_vector(const T1 &Input, T2 &Output, UnaryOp Op) {
+  std::transform(Input.begin(), Input.end(), std::back_inserter(Output), Op);
+}
+}
+
+PointerGraph PointerGraph::compress(bool TrimForInlining) {
+  Combiner Combiner(*this);
+  // Determine the equivalence classes.
+  Combiner.doCombiningForSize(TrimForInlining);
+
+  PointerGraph Compressed;
+  Compressed.createHeap();
+  assert(Combiner.getIndex(Heap) == Compressed.Heap);
+  // Add a node for each non-heap equivalence class.
+  for (unsigned i = 1; i < Combiner.getNumClasses(); i++)
+    Compressed.addNode();
+
+  DEBUG_MSG("compressed size = " << Compressed.size());
+  // Build edges between compressed nodes.
+  for (auto I : *this) {
+    auto NewI = Combiner.getIndex(I);
+    if (NewI == PointerGraph::NOT_A_NODE)
+      continue;
+
+    DEBUG_MSG("compress N" << I << " -> N" << NewI);
+    for (auto E : edges(I)) {
+      auto NewOther = Combiner.getIndex(E.Other);
+      if (NewI == NewOther || NewOther == PointerGraph::NOT_A_NODE)
+        continue;
+      if (!Compressed.hasEdge(NewI, NewOther, E.Type))
+        Compressed.addEdge(NewI, NewOther, E.Type);
+    }
+  }
+
+  // Map an existing node to its image.
+  auto NewNode = [&Combiner](Node N) {
+    if (N == PointerGraph::NOT_A_NODE)
+      return N;
+    return static_cast<Node>(Combiner.getIndex(N));
+  };
+  // Build the list of node references in the compressed graph.
+  transform_vector(FormalArguments, Compressed.FormalArguments, NewNode);
+  transform_vector(ReturnedNodes, Compressed.ReturnedNodes, NewNode);
+
+  // Bbuild the output Map of IR nodes to graph nodes.
+  for (auto Pair : Map) {
+    assert(inbounds(Pair.second));
+    Pair.second = static_cast<Node>(Combiner.getIndex(Pair.second));
+    if (Pair.second != NOT_A_NODE) {
+      assert(Compressed.inbounds(Pair.second));
+      Compressed.Map.insert(Pair);
+    }
+  }
+  return Compressed;
+}
+
+std::unique_ptr<CFLODAAResult::FunctionInfo>
+CFLODAAResult::buildSetsFrom(Function *Fn) {
+  GraphBuilder Builder(Fn, *this);
+  Builder.buildGraphAndEquivalences();
+#ifndef NDEBUG
+  if (DebugDump) {
+    Builder.Graph.dump(*Fn, &Builder.AliasEquivClass, &Builder.getCombiner(),
+                       "-cmp");
+    Builder.getGraphToInline().dump(*Fn, nullptr, nullptr, "-inline");
+  }
+#endif
+  auto Ptr = make_unique<FunctionInfo>(&Builder);
+#ifndef NDEBUG
+  Ptr->FunctionName = Fn->getName();
+#endif
+  return Ptr;
+}
+
+void Combiner::doCombiningForEquivClasses() {
+  initialize();
+
+  // Treat all nodes as live.
+  for (auto &I : NodeInfo)
+    I.IsLive = true;
+
+  // Exhaustively combine along AssignTo edges.
+  for (Node I : G) {
+    Node Deref = NodeInfo[I].Deref;
+    for (auto E : G.edges(I)) {
+      if (E.Type == EdgeType::AssignTo) {
+        combine(I, E.Other);
+      } else if (E.Type == EdgeType::Dereference) {
+        // Each class has a unique dereference and we combine nodes
+        // to preserve this.
+        if (E.Other != Deref)
+          combine(E.Other, Deref);
+      }
+    }
+  }
+  numberRoots();
+}
+
+void Combiner::doCombiningForSize(bool TrimForInlining) {
+  DEBUG_MSG("do combining " << TrimForInlining);
+  initialize();
+  trimDead(TrimForInlining);
+
+  // Find nodes which are statically known to be aliases to the Heap node
+  // and combine them with the heap.
+  DEBUG_MSG("walk heap");
+  walkHeap();
+
+  // Look for nodes which are simply copies of some other node and combine
+  // them with that node.
+  DEBUG_MSG("walk assign trees");
+  walkAssignTrees();
+
+  numberRoots();
+}
+
+void Combiner::walkHeap() {
+
+  // Find all nodes which are memory aliases of the heap
+  // and all nodes which are reachable from those nodes
+  // Any node reachable along a path
+  //     DA = (AssignTo* Deref)
+  // Starting at a node already in the heap, or, if COMPRESS_HEAP_ALIASES,
+  // along a path:
+  //     DF = (AssignFrom+ AssigntTo* Deref)
+
+  // We build the maximal set H which is initialized
+  // to the heap node and is closed in that
+  //     Y \in H if there is X \in H such that DA(X,Y)
+  // and
+  //     Y \in H if there exists X \in H and DF(X,Y)
+
+  // We have the following sets associated with
+  // a node which are incrementally explore by associating state bits
+  // with a node:
+  //    DA_To(X)   ==> Y in H,  (AssignTo*)(Y,X)
+  // when we find Z such that there is Y \in  DA_To and Deref(Y,Z)
+  // then we add Z to H.
+
+  // Similarly, when COMPRESS_HEAP_ALIASES
+  //    DF_From(X) ==> Y \in H, (AssignFrom*)(Y,X)
+  //    DF_To(X)   ==> Y \in DF_From,  (AssignTo*)(Y,X)
+  // when we find Z such that there is Y \in  DF_To and Deref(Y,Z)
+  // then we add Z to H
+
+  // We also look for nodes X which are part of assignment
+  // cycles: DA_To(x) & DF_From(X) and force those nodes into the heap.
+
+  // Note: the combining done by DF is imprecise because
+  // it combines nodes which are not aliases making the
+  // relation more transitive, however perhaps we can
+  // precompue AliasMem for heap nodes ?
+
+  enum HeapStates {
+    DF_From = 1,
+    DF_To = 2,
+    DA_To = 4,
+    D_Heap = 16,
+    D_OnQueue = 32,
+  };
+
+  std::vector<unsigned> State(G.size(), 0);
+  std::vector<Node> WorkList;
+  WorkList.reserve(G.size());
+
+#ifndef NDEBUG
+  auto dump = [&State](Node N) {
+    dbgs() << "N" << N;
+    auto S = State[N];
+    if (S & D_Heap)
+      dbgs() << " Heap";
+    if (S & DF_From)
+      dbgs() << " from";
+    if (S & DA_To)
+      dbgs() << " a_to";
+    if (S & D_OnQueue)
+      dbgs() << " onqueue ";
+    if (S & ~(D_Heap | DF_From | DF_To | DA_To | D_OnQueue))
+      dbgs() << " invalid";
+    dbgs() << "\n";
+  };
+#endif
+
+  // If Src is any of WhenState, add ToState to Dest
+  // also add Dest to queue if it changes.
+  auto Push = [&State, &WorkList](unsigned WhenState, Node Src,
+                                  unsigned ToState, Node Dest) {
+    if (State[Src] & WhenState) {
+      auto &DestState = State[Dest];
+      if ((DestState & ToState) != ToState) {
+        DestState |= ToState;
+        if (!(DestState & D_OnQueue)) {
+          DestState |= D_OnQueue;
+          WorkList.push_back(Dest);
+        }
+      }
+    }
+  };
+
+  State[G.Heap] = D_Heap | D_OnQueue;
+  WorkList.push_back(G.Heap);
+
+  while (!WorkList.empty()) {
+    auto Current = WorkList.back();
+    DEBUG(dump(Current));
+    WorkList.pop_back();
+    auto &CurrentState = State[Current];
+    CurrentState &= ~D_OnQueue;
+
+    // Cycles of assignments involving the heap are collapsed
+    unsigned Cycle = DA_To | DF_From;
+    if ((CurrentState & Cycle) == Cycle)
+      CurrentState |= D_Heap;
+
+    if (CurrentState & D_Heap)
+      combine(G.Heap, Current);
+
+    for (auto E : G.edges(Current)) {
+      if (!NodeInfo[E.Other].IsLive)
+        continue;
+
+      switch (E.Type) {
+      case EdgeType::Dereference:
+        Push(DF_From | DA_To | D_Heap, Current, D_Heap, E.Other);
+#if COMPRESS_HEAP_ALIASES
+        Push(DF_To, Current, D_Heap, E.Other);
+#endif
+        break;
+      case EdgeType::AssignTo:
+        Push(DA_To | D_Heap, Current, DA_To, E.Other);
+        if (E.Other == G.Heap)
+          Push(DA_To, Current, D_Heap, Current);
+#if COMPRESS_HEAP_ALIASES
+        Push(DF_From | DF_To, Current, DF_To, E.Other);
+#endif
+        break;
+      case EdgeType::AssignFrom:
+        Push(DF_From | D_Heap, Current, DF_From, E.Other);
+        break;
+      default:
+        break;
+      }
+    }
+  }
+
+  DEBUG({
+    State[G.Heap] &= ~D_OnQueue;
+    for (size_t N = 0; N < G.size(); N++) {
+      auto S = State[N];
+      if (S == 0)
+        continue;
+      dump(N);
+      assert(!(S & D_OnQueue) && "Unexpected elemnt should have been on queue");
+    }
+  });
+}
+
+void Combiner::trimDead(bool TrimForInlining) {
+
+  // We treat a node as "dead" if it is not reachable from a formal parameter
+  // or a return point except on paths which pass through the heap. If not
+  // inlining, then nodes reachable from the IR are also live. If inlining,
+  // globals are kept live.
+
+  NodeInfo[G.Heap].IsLive = true;
+  std::vector<Node> WorkList;
+  WorkList.reserve(G.size());
+  auto MarkLive = [this, &WorkList](Node N) {
+    assert(N < G.size());
+    auto &IsLive = NodeInfo[N].IsLive;
+    if (!IsLive) {
+      IsLive = true;
+      WorkList.push_back(N);
+    }
+  };
+
+  for (auto N : G.FormalArguments)
+    if (N != PointerGraph::NOT_A_NODE)
+      MarkLive(N);
+  for (auto N : G.ReturnedNodes)
+    MarkLive(N);
+
+  if (!TrimForInlining) {
+    // Mark Live anything reachable from a Value*
+    for (const auto &Pair : G.Map)
+      MarkLive(Pair.second);
+  } else {
+    // Retuan global variables even when reducing to just formals
+    for (auto GV : G.GlobalsValues)
+      MarkLive(G.Map.lookup(GV));
+  }
+
+  // Every node connected to a live node is also live.
+  while (!WorkList.empty()) {
+    auto Current = WorkList.back();
+    WorkList.pop_back();
+    for (auto E : G.edges(Current))
+      MarkLive(E.Other);
+  }
+  DEBUG({
+    dbgs() << "Dead nodes:";
+    for (size_t N = 0; N < G.size(); ++N)
+      if (!NodeInfo[N].IsLive)
+        dbgs() << " " << N;
+    dbgs() << '\n';
+  });
+}
+
+Node Combiner::uniqueSource(Node N) {
+  Node C = getComponent(N);
+  if (C == 0)
+    // Don't pull an assignment into the heap
+    return PointerGraph::NOT_A_NODE;
+
+  // Verify input edges are just assignments from a
+  // singe equivalence class source.
+  Node Src = PointerGraph::NOT_A_NODE;
+  for (auto E : G.edges(N)) {
+    Node ESrc = getComponent(E.Other);
+    if (ESrc == C)
+      continue;
+
+    switch (E.Type) {
+    case EdgeType::AssignFrom:
+      if (Src == PointerGraph::NOT_A_NODE)
+        Src = ESrc;
+      else if (Src != ESrc)
+        return MULTIPLE_SOURCES;
+      break;
+    case EdgeType::AssignTo:
+    case EdgeType::Dereference:
+      break;
+    case EdgeType::Reference:
+      return MULTIPLE_SOURCES;
+    default:
+      llvm_unreachable_internal();
+    }
+  }
+  return Src;
+}
+
+void Combiner::walkAssignTrees() {
+
+  // Find nodes which have a unique assignment source and combine them with
+  // that node, repeat until convergence.
+  bool Changed;
+  do {
+    for (auto &Info : NodeInfo)
+      Info.Src = PointerGraph::NOT_A_NODE;
+    for (Node N = 1; N < G.size(); ++N) {
+      auto C = getComponent(N);
+      if (C == 0) // Heap
+        continue;
+      auto Src = uniqueSource(N);
+      if (Src == PointerGraph::NOT_A_NODE)
+        continue;
+      DEBUG_MSG("assign N" << N << " =C" << C << " Src=C" << Src);
+      auto &CSrc = NodeInfo[C].Src;
+      if (CSrc == PointerGraph::NOT_A_NODE)
+        CSrc = Src;
+      else if (CSrc != Src)
+        CSrc = MULTIPLE_SOURCES;
+    }
+    Changed = false;
+    for (Node N1 = 1; N1 < G.size(); ++N1) {
+      auto &Info = NodeInfo[N1];
+      if (Info.isRoot() && Info.Src != PointerGraph::NOT_A_NODE &&
+          Info.Src != MULTIPLE_SOURCES) {
+        auto C = getComponent(N1);
+        DEBUG_MSG("assign final N" << N1 << " =C" << C << " Src=C" << Info.Src);
+        if (combine(C, Info.Src))
+          Changed = true;
+      }
+    }
+  } while (Changed);
+}
+
+#ifndef NDEBUG
+// Verify certain structural properties hold for the specified graph.
+void PointerGraph::check(const char *label, const Function &Fn) const {
+  bool failed = false;
+  for (Node N : *this) {
+    // At most one Derference edge.
+    unsigned DerefCount = 0;
+    for (auto E : edges(N)) {
+      if (E.Type == EdgeType::Dereference)
+        DerefCount += 1;
+      if (!inbounds(E.Other)) {
+        dbgs() << "bad edge reference from " << N << " to " << E.Other << '\n';
+        assert(0 && "Bad graph");
+      }
+      // Verify that the graph is bi-directional.
+      auto Flipped = flipLabel(E.Type);
+      auto &OtherEdges = edges(E.Other);
+      auto Count =
+          std::count_if(OtherEdges.begin(), OtherEdges.end(),
+                        [Flipped, N](GraphT::Edge Edge) {
+                          return Edge.Other == N && Edge.Type == Flipped;
+                        });
+      if (!Count) {
+        dbgs() << label << ": Missing from node N" << E.Other << " to N" << N
+               << " kind " << Flipped << '\n';
+        failed = true;
+      }
+    }
+    if (DerefCount > 1) {
+      dbgs() << label << ": Multiple derefence edges leaving N" << N << '\n';
+      failed = true;
+    }
+  }
+  if (failed) {
+    dump(Fn, nullptr, nullptr, "-failed");
+    assert(0 && "Failed checkgraph");
+  }
+}
+#endif
+
+void CFLODAAResult::scan(Function *Fn) {
+  DEBUG(ShowStatus = true);
+  STATUS_MSG("scanning " << Fn->getName());
+  auto InsertPair = Cache.insert(std::make_pair(Fn, nullptr));
+  (void)InsertPair;
+  assert(InsertPair.second &&
+         "Trying to scan a function that has already been cached");
+
+#ifndef NDEBUG
+  auto Save = FunctionNumber;
+  FunctionNumber = NextFunctionNumber++;
+  DebugNumber[Fn] = FunctionNumber;
+  auto SaveFlag = llvm::DebugFlag;
+  setDebugFlag();
+#endif
+  auto Info = buildSetsFrom(Fn);
+#ifndef NDEBUG
+  FunctionNumber = Save;
+  llvm::DebugFlag = SaveFlag;
+#endif
+  Cache[Fn] = std::move(Info);
+}
+
+void CFLODAAResult::rescan(Function *Fn) {
+  if (ShowStatus)
+    dbgs() << "Rescanning " << Fn->getName() << '\n';
+}
+
+void CFLODAAResult::evict(Function *Fn) { Cache.erase(Fn); }
+
+// Ensures that the given function is available in the cache.
+// Returns the appropriate entry from the cache.
+CFLODAAResult::FunctionInfo *CFLODAAResult::ensureCached(Function *Fn) {
+  auto Iter = Cache.find(Fn);
+  if (Iter == Cache.end()) {
+    scan(Fn);
+    Iter = Cache.find(Fn);
+    assert(Iter != Cache.end());
+    assert(Iter->second);
+  }
+  return Iter->second.get();
+}
+
+void CFLODAAResult::setActiveFunction(Function *Fn) {
+  if (ActiveFunction && ActiveFunction != Fn) {
+    STATUS_MSG("Analyzing " << Fn->getName());
+  }
+  ActiveFunction = Fn;
+}
+
+Optional<CFLODAAResult::FunctionInfo *> CFLODAAResult::getCached(Function *Fn) {
+  auto Iter = Cache.find(Fn);
+  if (Iter == Cache.end())
+    return None;
+  return Iter->second.get();
+}
+
+// Try to go from a Value* to a containing Function*.
+static 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 nullptr;
+}
+
+AliasResult CFLODAAResult::query(const MemoryLocation &LocA,
+                                 const MemoryLocation &LocB) {
+  QueryCalls += 1;
+
+  auto *ValA = const_cast<Value *>(LocA.Ptr);
+  auto *ValB = const_cast<Value *>(LocB.Ptr);
+
+  auto MaybeFnA = parentFunctionOfValue(ValA);
+  auto MaybeFnB = parentFunctionOfValue(ValB);
+  if (!MaybeFnA && !MaybeFnB) {
+    // The only times this is known to happen are when globals + InlineAsm
+    // are involved
+    DEBUG(
+        dbgs() << "CFLODAA: could not extract parent function information.\n");
+    return MayAlias;
+  }
+
+  Function *Fn = nullptr;
+  if (MaybeFnA) {
+    Fn = MaybeFnA;
+    assert((!MaybeFnB || MaybeFnB == MaybeFnA) &&
+           "Interprocedural queries not supported");
+  } else {
+    Fn = MaybeFnB;
+  }
+
+  setActiveFunction(Fn); // Diagnostic only
+
+  AliasResult Result = query(Fn, ValA, ValB);
+#if SEARCH_FULL_GRAPH
+  // Search on the full graph if it is available but limited total work...
+  if (FullGraphSearch && FullSearchOps < 10000000) {
+    auto &Info = *ensureCached(Fn);
+    bool FullResult = Info.FullInfo.mayAlias(ValA, ValB);
+    if (Result == MayAlias) {
+      if (!FullResult)
+        FullNoAlias += 1;
+    } else if (FullResult) {
+      FunctionNumber = DebugNumber[Fn];
+      errs() << "Failed CFL Verification of Compressed Info\n";
+      errs() << "        Full=" << (FullResult ? "May Alias" : "No Alias")
+             << '\n';
+      errs() << "  Compressed="
+             << (Result == MayAlias ? "May Alias" : "No Alias") << '\n';
+      auto List = [Info](Value *V) {
+        if (auto NumA = Info.Graph.getNode(V))
+          errs() << " C" << *NumA;
+        if (auto NumAF = Info.FullInfo.Graph.getNode(V))
+          errs() << " F" << *NumAF;
+        errs() << ": ";
+        V->print(errs());
+        errs() << '\n';
+      };
+      List(ValA);
+      List(ValB);
+      bool PrintValues = false;
+      Info.Graph.dump(*Fn, &Info.AliasEquivClass, nullptr, "-v", PrintValues,
+                      *Info.Graph.getNode(ValA), *Info.Graph.getNode(ValB));
+      Info.FullInfo.Graph.dump(*Fn, nullptr, nullptr, "-v-full", PrintValues,
+                               *Info.FullInfo.Graph.getNode(ValA),
+                               *Info.FullInfo.Graph.getNode(ValB));
+      dumpCFG(*Fn);
+      assert(Result == FullResult &&
+             "Failed CFL verification of compressed info");
+    }
+  }
+#endif
+  return Result;
+}
+
+AliasResult CFLODAAResult::query(Function *Fn, Value *ValA, Value *ValB) {
+  assert(Fn != nullptr);
+  auto &Info = *ensureCached(Fn);
+
+#ifndef NDEBUG
+  setDebugFlag(Fn);
+  Info.QueryCount += 1;
+#endif
+
+  // The fast path ... we can prove without searching that the
+  // pointers refere to distinct memory.
+  if (Info.distinctAliasEquivalenceClassses(ValA, ValB)) {
+    FastkNoAlias += 1;
+    return NoAlias;
+  }
+
+#if ENABLE_EXPERIMENTS
+  auto NodeA = Info.Graph.getNode(ValA);
+  if (!NodeA.hasValue()) {
+    NoNodeForValue += 1;
+    return MayAlias;
+  }
+  auto NodeB = Info.Graph.getNode(ValB);
+  if (!NodeB.hasValue()) {
+    NoNodeForValue += 1;
+    return MayAlias;
+  }
+  if (*NodeA == *NodeB)
+    return MayAlias;
+
+  // Check for the simple graph heuristic
+  if (Info.SimpleGraph) {
+    if (Info.Graph.simpleMayAlias(*NodeA, *NodeB))
+      return MayAlias;
+    SimpleNoAlias += 1;
+    return NoAlias;
+  }
+
+  // Do the path-search on the graph looking for a path which
+  // establishes an may-alias
+  if (Info.mayAlias(ValA, ValB)) {
+    Info.MayAliasCount += 1;
+    return MayAlias;
+  }
+
+  // No such path, no alias.
+  SlowNoAlias += 1;
+  return NoAlias;
+#else
+  return MayAlias;
+#endif
+}
+
+#if ENABLE_EXPERIMENTS
+bool PointerGraph::simpleMayAlias(Node A, Node B) {
+  Node NonHeap;
+  if (A != Heap) {
+    if (B != Heap) {
+      return false;
+    }
+    NonHeap = A;
+  } else
+    NonHeap = B;
+  return hasEdge(NonHeap, Heap, EdgeType::AssignTo);
+}
+#endif
+
+//===----------------------------------------------------------------------===//
+//
+//
+//  Code related to searching a PointerGraph for an alias inducing path.
+//
+//
+//===----------------------------------------------------------------------===//
+#if ENABLE_EXPERIMENTS
+namespace {
+/// States which summarize path to a given node.
+enum class State {
+  /// Path via only AssignFrom.
+  AssignFromOnlyPath = 1,
+  /// Path via only AssignFrom, after one memory alias.
+  AssignFromOnlyPathAfterMemAlias = 2,
+  /// A path which ends with AssignTo edges.
+  AssignToPath = 3,
+  /// A path which ends with AssignTo edges, after one memory alias
+  AssignToPathAfterMemAlias = 4
+};
+
+#if DEBUG_SEARCH
+const char *name(State s) {
+  switch (s) {
+  case State::AssignToPath:
+    return "AssignToPath";
+  case State::AssignFromOnlyPath:
+    return "AssignFromOnly";
+  case State::AssignToPathAfterMemAlias:
+    return "AssignTo,After";
+  case State::AssignFromOnlyPathAfterMemAlias:
+    return "AssignFrom,After";
+  }
+  llvm_unreachable("unkown State");
+}
+#endif
+
+/// This class manages the queue of to-be-explored-states which is basically
+/// the collection of states augmented with a set which notes which states
+/// have already been seen.
+class StateQueue {
+  typedef GraphT::Node Node;
+
+  /// The to-be-explored elements.
+  struct StateQueueElement {
+    /// The current node.
+    Node N;
+    /// The target 'end' node of the path
+    Node S;
+    /// A characterization of the path so far to 'N'
+    State C;
+    /// A level which relates to the number of Reference/Dereference
+    /// nodes traversed as we explore the exists of memory aliases. This is
+    /// used as a priority to search paths without aliases before looking for
+    /// more aliases.
+    int Level;
+    bool operator==(const StateQueueElement &E) const {
+      return E.N == N && E.S == S && E.C == C;
+    }
+    bool operator<(const StateQueueElement &E) const { return Level < E.Level; }
+  };
+  struct Hash {
+    size_t operator()(const StateQueueElement &E) const {
+      size_t Key = E.N << 17 | E.S << 2 | unsigned(E.C);
+      return std::hash<size_t>()(Key);
+    }
+  };
+
+  std::priority_queue<StateQueueElement> WorkList;
+  std::unordered_set<StateQueueElement, Hash> Seen;
+
+public:
+  bool push(Node N, Node S, State C, int Level) {
+    StateQueueElement E{N, S, C, Level};
+    if (!Seen.insert(E).second)
+      return false;
+#if DEBUG_SEARCH
+    DEBUG_MSG("   push " << N << ' ' << S << ' ' << name(C));
+#endif
+    WorkList.push(E);
+    return true;
+  }
+  void pop(Node *N, Node *S, State *C, int *Level) {
+    StateQueueElement E = WorkList.top();
+    *N = E.N;
+    *S = E.S;
+    *C = E.C;
+    *Level = E.Level;
+#if DEBUG_SEARCH
+    DEBUG_MSG("pop " << E.N << ' ' << E.S << ' ' << name(E.C));
+#endif
+    WorkList.pop();
+  }
+  bool empty() const { return WorkList.empty(); }
+};
+
+/// This class encapsulate the logic of exploring the pointer graph
+/// for the existence of paths whose labels satisfy the CFL given by
+/// the following rules
+///    V = (AssignFrom M?)* M? (AssignTo M?)*
+///    M = Reference V Derefernce
+/// Note that we remember nodes X,Y connected by a path M in the
+/// the set AliasMem and this set can be reused across different
+/// invocations.
+///
+/// For the relations above we denote V(x,y) to indicate that there is a path
+/// from x to y whose labels are language defined by V. Similarly for M.
+///
+/// Intuitively, two pointers p1 and p2 are aliased they refer
+/// to the same memorhy location. This is observed as path from some
+/// address (global variable or malloc call) which reaches the nodes
+/// corresponding to p1 and p2 through assignment paths. The path
+/// V then walks backwards from p1 to this source address and forward
+/// to node p2.
+///
+/// This basic idea is then extend bu finding abstract "memory" locations
+/// which might be the same because there addresses have a common value.
+/// Since the analysis is flow insensitive, a path of assignments may enter
+/// one memory node and then continue from any aliased location. This is the
+/// role of the M relation above.
+///
+/// Given two values p1, p2 with corresponding nodes n1, n2, we attempt to
+/// prove that V(n1,n2) exists by exhaustively search for such a path. We record
+/// triples of the form (n1,s1,c) which capture the existence of a path
+/// starting at "s1" which reaches "n1" where "c" indicates where in the
+/// expansion of V this path corresponds to. To illustrate:
+///
+///    V = (AssignFrom M? )* M? (AssignTo M? )*
+///                   1  2               3  4
+/// Which are explained as
+///     1 -- AssignFromOnlyPath --- we have only seeen AssignFrom operations
+///            and maybe some M transitions, and an M transition may be next
+///     2 -- AssignFromOnlyPathAfterMemAlias -- we have only seen AssignFrom
+///            operations and have just made an M transition
+///     3 -- AssignToPath -- we have seen at least one AssignTo operations
+///            and may have a M transition
+///     4 -- AssignToPathAfterMemAlias -- we have seen at least one AssignTo
+///            operation and just had an M transition.
+/// We process every such triple to create new triples based on the edges
+/// incident to the node. If we process a tuple of the form  (n2,n1,*) then
+/// we have establish the basic question and can report p1 and p2 are aliased.
+/// If we exhaust the search, we have determined they are not aliased.
+///
+/// To accomplish the M transition, whenever we process a node n1 in
+/// states AssignFromOnlyPath (1) or AssignToPath (2), and the node n1 has
+/// a reference source, n2  (i.e., there is an edge (n1,n2, Reference) and
+/// by construction also an edge (n2,n1,Dereference)). Then we include the sate
+/// (n2,n2, AssignFromOnlyPath) which will identify nodes "m2" where V(n2,m2)
+/// When ever we process a state (n2,m2,*), we look for nodes  n3 and m3 which
+/// are dereferences of n2 and m2 respectively. We can add (n3,m3) to M.
+/// When we add a pair to M, we can examine the states which are known n3, and
+/// use that to add new states for m3.
+///
+/// When an alias does exist, the order in which we visit nodes effects the
+/// number of noes visited. This initial implementation makes no attempt to
+/// exploit this fact.
+///
+/// TODO -- is the definition of V actually correct? If so, how is
+///    the middle M? transition handled?
+class Searcher {
+
+  /// The alias graph we are searching.
+  AliasInfo &Info;
+
+  /// These nodes are the original question is (N0,S0) \in V
+  /// We will start teh search form N0 looking for S0.
+  Node N0, S0;
+
+  /// The queue of (n,s,c) triples still to be processed.
+  StateQueue W;
+
+  /// This map implements the projection from all visited triples
+  /// to those with a particular first node.
+  typedef std::pair<Node, State> ReachElt;
+  DenseMap<Node, SmallVector<ReachElt, 4>> Reach;
+
+  /// Add (N,S,C) to the set of triples to be explored.
+  void propagate(Node N, Node S, State C, int Level) {
+    assert(Info.Graph.inbounds(N));
+    if (W.push(N, S, C, Level))
+      // First time it has been seen
+      Reach[N].emplace_back(S, C);
+  };
+
+  /// This tracks Derefence nodes we have explored. If we fail to find
+  /// a path, then the aliases for these nodes are fully known and in future
+  /// search calls we don't need to look for more memory aliases.
+  SmallVector<Node, 16> DerefencesChecked;
+
+public:
+  Searcher(AliasInfo &Info) : Info(Info) {}
+  void init(Node N, Node S) {
+    N0 = N;
+    S0 = S;
+
+    // There is a bug in the paper where they fail to
+    // initialize the Reach[] set with the starting
+    // information. This is fixed by calling propagate instead
+    // of push here to initialize.  This bug manifests on a path
+    // which begins with transition to a memory alias.
+    propagate(N, N, State::AssignFromOnlyPath, 0);
+  }
+
+  /// Process one node on the queue and indicate whether
+  /// we have learned anything. This interface allows the client
+  /// to control/limit/interleave the search. This structure is intended
+  /// to at some point allow searches to be interleaved but that is not
+  /// currently done.
+  enum class SearchStatus { CONTINUE, NO_ALIAS, MAY_ALIAS };
+  SearchStatus advance();
+};
+}
+
+Searcher::SearchStatus Searcher::advance() {
+  if (W.empty())
+    return SearchStatus::NO_ALIAS;
+
+  SearchOps += 1;
+  Node N, S;
+  State C;
+  int Level;
+  W.pop(&N, &S, &C, &Level);
+
+  // Have we reached a path to the
+  // original end node?
+  if (N == S0 && S == N0) {
+    // We are not done processing here so clear the status flag since
+    // we don't know all of the aliases for these Derference nodes.
+    for (auto D : DerefencesChecked)
+      Info.AliasesKnown[D] = false;
+    return SearchStatus::MAY_ALIAS;
+  }
+
+  // See if we have discovered a new element in the M releation
+  if (auto N1 = Info.Graph.getDeref(N))
+    if (auto S1 = Info.Graph.getDeref(S))
+      if (*N1 != *S1 && Info.AliasMem[*S1].insert(*N1).second) {
+// Discovered a memory alias
+#if DEBUG_SEARCH
+        DEBUG_MSG("   alias " << *N1 << " and " << *S1);
+#endif
+        // Continue value search associated with S1 from new alias N1
+        SmallVector<ReachElt, 16> ToPropagate;
+        for (const auto &R : Reach[*S1]) {
+          if (R.second == State::AssignFromOnlyPath)
+            ToPropagate.emplace_back(R.first,
+                                     State::AssignFromOnlyPathAfterMemAlias);
+          else if (R.second == State::AssignToPath)
+            ToPropagate.emplace_back(R.first, State::AssignToPathAfterMemAlias);
+        }
+        for (const auto &R : ToPropagate)
+          propagate(*N1, R.first, R.second, Level + 1);
+      }
+
+  // Propagate state to adjacent nodes
+  switch (C) {
+  case State::AssignFromOnlyPath:
+  case State::AssignFromOnlyPathAfterMemAlias: {
+    for (const auto &E : Info.Graph.edges(N)) {
+      if (E.Type == EdgeType::AssignFrom)
+        propagate(E.Other, S, State::AssignFromOnlyPath, Level);
+      else if (E.Type == EdgeType::AssignTo)
+        propagate(E.Other, S, State::AssignToPath, Level);
+    }
+    if (C == State::AssignFromOnlyPath) {
+      auto Iter = Info.AliasMem.find(N);
+      if (Iter != Info.AliasMem.end())
+        for (auto M : Iter->second)
+          propagate(M, S, State::AssignFromOnlyPathAfterMemAlias, Level);
+    }
+    break;
+  }
+  case State::AssignToPath:
+  case State::AssignToPathAfterMemAlias: {
+    for (const auto &E : Info.Graph.edges(N))
+      if (E.Type == EdgeType::AssignTo)
+        propagate(E.Other, S, State::AssignToPath, Level);
+    if (C == State::AssignToPath) {
+      auto Iter = Info.AliasMem.find(N);
+      if (Iter != Info.AliasMem.end())
+        for (auto M : Iter->second)
+          propagate(M, S, State::AssignToPathAfterMemAlias, Level);
+    }
+    break;
+  }
+  }
+
+  // Jump to an alias of N if its aliases are not known and it
+  // has an Reference edge (which identifies an "address").
+  if (C == State::AssignFromOnlyPath || C == State::AssignToPath)
+    for (auto E : Info.Graph.edges(N))
+      if (E.Type == EdgeType::Reference && !Info.AliasesKnown[E.Other]) {
+        // Remember that we have explored alias for this node.
+        Info.AliasesKnown[E.Other] = true;
+        DerefencesChecked.push_back(E.Other);
+        // Exploring aliases is a lower priorty than continunie to search
+        // for value paths at this level
+        int Priority = Level - 1;
+        propagate(E.Other, E.Other, State::AssignFromOnlyPath, Priority);
+      }
+
+  return SearchStatus::CONTINUE;
+}
+
+// p1 and p2 are two address associated with memory locations
+// we try to prove they may not be the same location
+bool AliasInfo::mayAlias(Value *p1, Value *p2) {
+  if (DisableSearch)
+    return true;
+  if (p1 == p2)
+    return true;
+  
+  // The alias information degrades as transformations are performed
+  // on the underly IR and so here we may conservative assumptions.
+  auto N0 = Graph.getNode(p1);
+  if (!N0.hasValue())
+    return true;
+  auto S0 = Graph.getNode(p2);
+  if (!S0.hasValue())
+    return true;
+  if (*N0 == *S0)
+    return true;
+  assert(Graph.inbounds(*N0));
+  assert(Graph.inbounds(*S0));
+
+#if DEBUG_SEARCH
+  DEBUG_INST(DebugLabel << "p1 = " << *N0 << ": ", (*p1));
+  DEBUG_INST(DebugLabel << "p2 = " << *S0 << ": ", (*p2));
+#endif
+
+#ifdef LLVM_ENABLE_STATS
+  auto CountInit = SearchOps.getValue();
+#endif
+  Searcher Search(*this);
+  Search.init(*N0, *S0);
+
+  Searcher::SearchStatus Status;
+  do {
+    Status = Search.advance();
+  } while (Status == Searcher::SearchStatus::CONTINUE);
+
+#ifdef LLVM_ENABLE_STATS
+  auto NumSteps = SearchOps - CountInit;
+  SearchCount += NumSteps;
+  if (*DebugLabel) {
+    SearchOps -= NumSteps;
+    FullSearchOps += NumSteps;
+  }
+#endif
+
+  if (Status == Searcher::SearchStatus::NO_ALIAS) {
+#if DEBUG_SEARCH
+    DEBUG_MSG("CFL no alias");
+#endif
+    return false;
+  }
+  return true;
+}
+#endif
+
+CFLODAAResult CFLODAA::run(Function &F, AnalysisManager<Function> *AM) {
+  return CFLODAAResult();
+}
+
+CFLODAAResult::CFLODAAResult() : AAResultBase() {}
+CFLODAAResult::CFLODAAResult(CFLODAAResult &&Arg)
+    : AAResultBase(std::move(Arg)) {}
+CFLODAAResult::~CFLODAAResult() {
+  if (!FunctionReporting) {
+    return;
+  }
+#ifndef NDEBUG
+  for (auto &P : Cache)
+    if (P.second)
+      P.second->report(P.first);
+#endif
+}
+
+#ifndef NDEBUG
+void CFLODAAResult::FunctionInfo::report(Function *F) {
+#if ENABLE_EXPERIMENTS
+  dbgs() << format("%5d", QueryCount)
+         << format(" %5.1f%% ", 100 * MayAliasCount / double(QueryCount))
+         << (SimpleGraph ? "simple" : "      ") << " steps "
+         << format(" %6d ", SearchCount);
+  dbgs() << " CFL ";
+  dbgs() << DebugNumber[F];
+  dbgs() << ' ' << FunctionName << '\n';
+#endif
+}
+#endif
+
+char CFLODAA::PassID;
+char CFLODAAWrapperPass::ID = 0;
+
+INITIALIZE_PASS(CFLODAAWrapperPass, "cfl-od-aa",
+                "CFL-Based On Demand Alias Analysis", false, true)
+
+ImmutablePass *llvm::createCFLOnDemandAAWrapperPass() {
+  return new CFLODAAWrapperPass();
+}
+
+CFLODAAWrapperPass::CFLODAAWrapperPass() : ImmutablePass(ID) {
+  initializeCFLODAAWrapperPassPass(*PassRegistry::getPassRegistry());
+}
+
+bool CFLODAAWrapperPass::doInitialization(Module &M) {
+  Result.reset(new CFLODAAResult());
+  return false;
+}
+
+bool CFLODAAWrapperPass::doFinalization(Module &M) {
+  Result.reset();
+  return false;
+}
+
+void CFLODAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
+  AU.setPreservesAll();
+}
+
+namespace {
+struct CFLODAARebuildPass : public FunctionPass {
+  static char ID;
+  CFLODAARebuildPass() : FunctionPass(ID) {
+    llvm::initializeCFLODAARebuildPassPass(*PassRegistry::getPassRegistry());
+  }
+  bool runOnFunction(Function &F) override {
+    if (skipFunction(F))
+      return false;
+    auto R = &getAnalysis<CFLODAAWrapperPass>().getResult();
+    R->rescan(&F);
+    return true;
+  }
+
+  void getAnalysisUsage(AnalysisUsage &AU) const override {
+    AU.addRequired<CFLODAAWrapperPass>();
+    AU.setPreservesAll();
+  }
+};
+}
+char CFLODAARebuildPass::ID = 0;
+INITIALIZE_PASS_BEGIN(CFLODAARebuildPass, "cfl-rebuild",
+                      "Rebuild CFL AA information", false, false)
+INITIALIZE_PASS_DEPENDENCY(CFLODAAWrapperPass)
+INITIALIZE_PASS_END(CFLODAARebuildPass, "cfl-rebuild",
+                    "Rebuild CFL AA information", false, false)
+FunctionPass *llvm::createCFLOnDemandAARebuildPass() {
+  return new CFLODAARebuildPass();
+}
+#ifndef NDEBUG
+namespace {
+
+/// This class finds connected components of the graph with
+/// the heap node logically removed.
+class SplitHeapComponents {
+  const PointerGraph &G;
+  /// All nodes in a connected component have
+  /// the same non-zero value under this map. This
+  /// is also used as "visited" flag for graph traversal.
+  std::vector<unsigned> Component;
+  SmallVector<Node,32> Worklist;
+
+  void collectComponent(Node N, unsigned Number) {
+    Worklist.push_back(N);
+    while(!Worklist.empty()) {
+      N = Worklist.pop_back_val();
+      Component[N] = Number;
+      for (auto E : G.edges(N))
+        if (!Component[E.Other])
+          Worklist.push_back(E.Other);
+    }
+  }
+
+public:
+  SplitHeapComponents(const PointerGraph &G) : G(G) {}
+
+  unsigned doLabeling() {
+    Component.resize(G.size(), 0);
+
+    // Force the heap to be in its own compmonent
+    unsigned NumComponent = 1;
+    Component[G.Heap] = NumComponent;
+    for (Node N = 1; N < G.size(); N++) {
+      if (Component[N] == 0) {
+        ++NumComponent;
+        collectComponent(N, NumComponent);
+      }
+    }
+    return NumComponent;
+  }
+  unsigned getComponent(Node N) const { return Component[N]; }
+};
+
+// Generate a ".dot" file for the graph for visualization.
+// Node labels will include equivalence class information when its available.
+void PointerGraph::dump(const Function &F,
+                        const AliasEquivClassMap *AliasEquivClass,
+                        const Combiner *DoCombining, const char *label,
+                        bool PrintValues, Node ONLY_A, Node ONLY_B) const {
+
+  std::vector<Value *> NodeToValue(size());
+  for (const auto &P : Map) {
+    assert(inbounds(P.second));
+    NodeToValue[P.second] = P.first;
+  }
+
+  std::stringstream Buffer;
+  Buffer << "aa/" << FunctionNumber << '_' << F.getName().str() << label
+         << ".dot";
+  std::string Filename = Buffer.str();
+  errs() << "Writing '" << Filename << "'...\n";
+
+  std::error_code EC;
+  raw_fd_ostream File(Filename, EC, sys::fs::F_Text);
+  if (EC) {
+    errs() << "Unable top open " << Filename << "\n";
+    return;
+  }
+  File << "digraph " << DOT::EscapeString(F.getName()) << " {\n";
+
+  // Split the graph into components by removing the heap node
+  // and treating its connected component with its own copy of the
+  // heap as a separate graph to aide readability.
+  SplitHeapComponents Splitter(*this);
+  auto NumComponents = Splitter.doLabeling();
+  std::vector<char> Active(NumComponents, (ONLY_A == NOT_A_NODE ? 1 : 0));
+  if (ONLY_A != NOT_A_NODE) {
+    Active[Splitter.getComponent(ONLY_A)] = 1;
+    Active[Splitter.getComponent(ONLY_B)] = 1;
+  }
+  auto IsActive = [&](Node N) { return Active[Splitter.getComponent(N)]; };
+
+  for (unsigned H = 1; H <= NumComponents; ++H)
+    if (Active[H])
+      File << "H" << H << " [label=\"heap\"];\n";
+
+  for (auto I : nonHeapNodes()) {
+    if (!IsActive(I))
+      continue;
+
+    File << "N" << I;
+    File << " [label=\"" << I << " ";
+
+    auto V = NodeToValue[I];
+    if (AliasEquivClass) {
+      auto AliasIter = AliasEquivClass->find(V);
+      if (AliasIter != AliasEquivClass->end()) {
+        File << ", " << AliasIter->second.Class << ": ";
+      } else if (DoCombining) {
+        auto C = DoCombining->getIndex(I);
+        if (C != PointerGraph::NOT_A_NODE)
+          File << ", " << C << ": ";
+      }
+    }
+    if (I == 0) {
+      File << " heap";
+    } else if (V && !NoLabels && PrintValues) {
+      std::string Result;
+      raw_string_ostream TempStream(Result);
+      if (isa<Function>(V))
+        TempStream << "function " << V->getName();
+      else
+        V->print(TempStream);
+      for (auto C : Result) {
+        if (C == '"') {
+          File << '\\';
+        }
+        File << C;
+      }
+    } else {
+      File << " N" << I;
+    }
+    File << "\"]";
+    File << ";\n";
+  }
+
+  if (!ReturnedNodes.empty()) {
+    // Build implicit edges to a "return" node from
+    // nodes which are returned from the function
+    File << "R [Label=\"ret\"];\n";
+    for (auto R : ReturnedNodes)
+      if (IsActive(R))
+        File << " N" << R << " -> R;\n";
+  }
+
+  for (auto Edge : edges(Heap)) {
+    if (Edge.Other == Heap)
+      continue;
+    auto Label = Edge.Type;
+    if (Label == EdgeType::Reference || Label == EdgeType::AssignFrom)
+      continue;
+    if (!IsActive(Edge.Other))
+      continue;
+    unsigned C = Splitter.getComponent(Edge.Other);
+    File << "H" << C << " -> N" << Edge.Other << " [label=\"" << Label
+         << "\"];\n";
+  }
+
+  for (auto I : nonHeapNodes()) {
+    if (!IsActive(I))
+      continue;
+
+    for (auto Edge : edges(I)) {
+      auto Label = Edge.Type;
+      if (Label == EdgeType::Reference || Label == EdgeType::AssignFrom)
+        continue;
+
+      File << " N" << I;
+      if (Edge.Other == Heap) {
+        // Connect to this commponents heap
+        unsigned C = Splitter.getComponent(I);
+        File << " -> H" << C;
+      } else {
+        File << " -> N" << Edge.Other;
+      }
+      File << " [label=\"" << Label << "\"];\n";
+    }
+  }
+  File << "}\n";
+}
+}
+#endif
+
+#ifndef NDEBUG
+void CFL_On_Demand_report() {
+  static unsigned LastQueryCalls = 0;
+  static unsigned LastNoNode = 0;
+  if (QueryCalls > LastQueryCalls) {
+    dbgs() << "CFL Report" << QueryCalls.getValue() - LastQueryCalls
+           << " queries " << NoNodeForValue.getValue() - LastNoNode
+           << " no node\n";
+    LastNoNode = NoNodeForValue;
+    LastQueryCalls = QueryCalls;
+  }
+}
+#endif

lib/Analysis/CMakeLists.txt

 add_llvm_library(LLVMAnalysis
   AliasAnalysis.cpp
   AliasAnalysisEvaluator.cpp
   AliasAnalysisSummary.cpp
   AliasSetTracker.cpp
   Analysis.cpp
   AssumptionCache.cpp
   BasicAliasAnalysis.cpp
   BlockFrequencyInfo.cpp
   BlockFrequencyInfoImpl.cpp
   BranchProbabilityInfo.cpp
   CFG.cpp
   CFGPrinter.cpp
   CFLAndersAliasAnalysis.cpp
   CFLSteensAliasAnalysis.cpp
+  CFLOnDemandAliasAnalysis.cpp
   CGSCCPassManager.cpp
   CallGraph.cpp
   CallGraphSCCPass.cpp
   CallPrinter.cpp
   CaptureTracking.cpp
   CostModel.cpp
   CodeMetrics.cpp
   ConstantFolding.cpp

lib/CodeGen/TargetPassConfig.cpp

 // generation passes provided by the LLVM backend.
 //
 //===---------------------------------------------------------------------===//
 
 #include "llvm/CodeGen/TargetPassConfig.h"
 
 #include "llvm/Analysis/BasicAliasAnalysis.h"
 #include "llvm/Analysis/CFLAndersAliasAnalysis.h"
+#include "llvm/Analysis/CFLOnDemandAliasAnalysis.h"
 #include "llvm/Analysis/CFLSteensAliasAnalysis.h"
 #include "llvm/Analysis/CallGraphSCCPass.h"
 #include "llvm/Analysis/Passes.h"
 #include "llvm/Analysis/ScopedNoAliasAA.h"
 #include "llvm/Analysis/TypeBasedAliasAnalysis.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/RegAllocRegistry.h"
 #include "llvm/CodeGen/RegisterUsageInfo.h"

 cl::opt<bool> MISchedPostRA("misched-postra", cl::Hidden,
   cl::desc("Run MachineScheduler post regalloc (independent of preRA sched)"));
 
 // Experimental option to run live interval analysis early.
 static cl::opt<bool> EarlyLiveIntervals("early-live-intervals", cl::Hidden,
     cl::desc("Run live interval analysis earlier in the pipeline"));
 
 // Experimental option to use CFL-AA in codegen
-enum class CFLAAType { None, Steensgaard, Andersen, Both };
+enum class CFLAAType { None, Steensgaard, Andersen, Both, OnDemand };
 static cl::opt<CFLAAType> UseCFLAA(
     "use-cfl-aa-in-codegen", cl::init(CFLAAType::None), cl::Hidden,
     cl::desc("Enable the new, experimental CFL alias analysis in CodeGen"),
     cl::values(clEnumValN(CFLAAType::None, "none", "Disable CFL-AA"),
                clEnumValN(CFLAAType::Steensgaard, "steens",
                           "Enable unification-based CFL-AA"),
                clEnumValN(CFLAAType::Andersen, "anders",
                           "Enable inclusion-based CFL-AA"),
                clEnumValN(CFLAAType::Both, "both", 
                           "Enable both variants of CFL-AA"),
+               clEnumValN(CFLAAType::OnDemand, "on-demand", 
+                          "Enable On-Demand variant of CFL-AA"),
                clEnumValEnd));
 
 /// Allow standard passes to be disabled by command line options. This supports
 /// simple binary flags that either suppress the pass or do nothing.
 /// i.e. -disable-mypass=false has no effect.
 /// These should be converted to boolOrDefault in order to use applyOverride.
 static IdentifyingPassPtr applyDisable(IdentifyingPassPtr PassID,
                                        bool Override) {
case CFLAAType::Steensgaard:
     break;
   case CFLAAType::Andersen:
     addPass(createCFLAndersAAWrapperPass());
     break;
   case CFLAAType::Both:
     addPass(createCFLAndersAAWrapperPass());
     addPass(createCFLSteensAAWrapperPass());
     break;
+  case CFLAAType::OnDemand:
+    addPass(createCFLOnDemandAAWrapperPass());
+    break;
   default:
     break;
   }
 
   // Basic AliasAnalysis support.
   // Add TypeBasedAliasAnalysis before BasicAliasAnalysis so that
   // BasicAliasAnalysis wins if they disagree. This is intended to help
   // support "obvious" type-punning idioms.

lib/Passes/PassBuilder.cpp

 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/AliasAnalysisEvaluator.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/BasicAliasAnalysis.h"
 #include "llvm/Analysis/BlockFrequencyInfo.h"
 #include "llvm/Analysis/BlockFrequencyInfoImpl.h"
 #include "llvm/Analysis/BranchProbabilityInfo.h"
 #include "llvm/Analysis/CFLAndersAliasAnalysis.h"
+#include "llvm/Analysis/CFLOnDemandAliasAnalysis.h"
 #include "llvm/Analysis/CFLSteensAliasAnalysis.h"
 #include "llvm/Analysis/CGSCCPassManager.h"
 #include "llvm/Analysis/CallGraph.h"
 #include "llvm/Analysis/DemandedBits.h"
 #include "llvm/Analysis/DependenceAnalysis.h"
 #include "llvm/Analysis/DominanceFrontier.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/IVUsers.h"

lib/Transforms/IPO/PassManagerBuilder.cpp

 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/IPO/PassManagerBuilder.h"
 #include "llvm-c/Transforms/PassManagerBuilder.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/Analysis/BasicAliasAnalysis.h"
 #include "llvm/Analysis/CFLAndersAliasAnalysis.h"
+#include "llvm/Analysis/CFLOnDemandAliasAnalysis.h"
 #include "llvm/Analysis/CFLSteensAliasAnalysis.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/InlineCost.h"
 #include "llvm/Analysis/Passes.h"
 #include "llvm/Analysis/ScopedNoAliasAA.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/TypeBasedAliasAnalysis.h"
 #include "llvm/IR/DataLayout.h"

 
 static cl::opt<bool>
 RunSLPAfterLoopVectorization("run-slp-after-loop-vectorization",
   cl::init(true), cl::Hidden,
   cl::desc("Run the SLP vectorizer (and BB vectorizer) after the Loop "
            "vectorizer instead of before"));
 
 // Experimental option to use CFL-AA
-enum class CFLAAType { None, Steensgaard, Andersen, Both };
+enum class CFLAAType { None, Steensgaard, Andersen, Both, OnDemand };
 static cl::opt<CFLAAType>
     UseCFLAA("use-cfl-aa", cl::init(CFLAAType::None), cl::Hidden,
              cl::desc("Enable the new, experimental CFL alias analysis"),
              cl::values(clEnumValN(CFLAAType::None, "none", "Disable CFL-AA"),
                         clEnumValN(CFLAAType::Steensgaard, "steens",
                                    "Enable unification-based CFL-AA"),
                         clEnumValN(CFLAAType::Andersen, "anders",
                                    "Enable inclusion-based CFL-AA"),
                         clEnumValN(CFLAAType::Both, "both",
                                    "Enable both variants of CFL-AA"),
+                        clEnumValN(CFLAAType::OnDemand, "on-demand",
+                                   "Enable on-demand variant of CFL-aa"),
                         clEnumValEnd));
 
 static cl::opt<bool>
 EnableMLSM("mlsm", cl::init(true), cl::Hidden,
            cl::desc("Enable motion of merged load and store"));
 
 static cl::opt<bool> EnableLoopInterchange(
     "enable-loopinterchange", cl::init(false), cl::Hidden,
case CFLAAType::Steensgaard:
     break;
   case CFLAAType::Andersen:
     PM.add(createCFLAndersAAWrapperPass());
     break;
   case CFLAAType::Both:
     PM.add(createCFLSteensAAWrapperPass());
     PM.add(createCFLAndersAAWrapperPass());
     break;
+  case CFLAAType::OnDemand:
+    PM.add(createCFLOnDemandAAWrapperPass());
+    break;
   default:
     break;
   }
 
   // Add TypeBasedAliasAnalysis before BasicAliasAnalysis so that
   // BasicAliasAnalysis wins if they disagree. This is intended to help
   // support "obvious" type-punning idioms.
   PM.add(createTypeBasedAAWrapperPass());