Index: include/llvm/Analysis/CFLAndersAliasAnalysis.h
===================================================================
--- include/llvm/Analysis/CFLAndersAliasAnalysis.h
+++ include/llvm/Analysis/CFLAndersAliasAnalysis.h
@@ -15,33 +15,86 @@
 #ifndef LLVM_ANALYSIS_CFLANDERSALIASANALYSIS_H
 #define LLVM_ANALYSIS_CFLANDERSALIASANALYSIS_H
 
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/Optional.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/IR/Function.h"
+#include "llvm/IR/ValueHandle.h"
 #include "llvm/Pass.h"
+#include <forward_list>
 
 namespace llvm {
 
+class TargetLibraryInfo;
+
 namespace cflaa {
 struct AliasSummary;
 }
 
 class CFLAndersAAResult : public AAResultBase<CFLAndersAAResult> {
   friend AAResultBase<CFLAndersAAResult>;
+  class FunctionInfo;
 
 public:
-  explicit CFLAndersAAResult();
+  explicit CFLAndersAAResult(const TargetLibraryInfo &);
+  CFLAndersAAResult(CFLAndersAAResult &&);
+  ~CFLAndersAAResult();
+
+  /// 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; }
+  /// Evict the given function from cache
+  void evict(const Function &Fn);
 
   /// \brief Get the alias summary for the given function
   /// Return nullptr if the summary is not found or not available
-  const cflaa::AliasSummary *getAliasSummary(Function &Fn) {
-    // Dummy implementation
-    return nullptr;
-  }
-
-  AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB) {
-    // Dummy implementation
-    return AAResultBase::alias(LocA, LocB);
-  }
+  const cflaa::AliasSummary *getAliasSummary(const Function &);
+
+  AliasResult query(const MemoryLocation &, const MemoryLocation &);
+  AliasResult alias(const MemoryLocation &, const MemoryLocation &);
+
+private:
+  struct FunctionHandle final : public CallbackVH {
+    FunctionHandle(Function *Fn, CFLAndersAAResult *Result)
+        : CallbackVH(Fn), Result(Result) {
+      assert(Fn != nullptr);
+      assert(Result != nullptr);
+    }
+
+    void deleted() override { removeSelfFromCache(); }
+    void allUsesReplacedWith(Value *) override { removeSelfFromCache(); }
+
+  private:
+    CFLAndersAAResult *Result;
+
+    void removeSelfFromCache() {
+      assert(Result != nullptr);
+      auto *Val = getValPtr();
+      Result->evict(*cast<Function>(Val));
+      setValPtr(nullptr);
+    }
+  };
+
+  /// \brief Ensures that the given function is available in the cache.
+  /// Returns the appropriate entry from the cache.
+  const Optional<FunctionInfo> &ensureCached(const Function &);
+
+  /// \brief Inserts the given Function into the cache.
+  void scan(const Function &);
+
+  /// \brief Build summary for a given function
+  FunctionInfo buildInfoFrom(const Function &);
+
+  const TargetLibraryInfo &TLI;
+
+  /// \brief Cached mapping of Functions to their StratifiedSets.
+  /// 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<const Function *, Optional<FunctionInfo>> Cache;
+
+  std::forward_list<FunctionHandle> Handles;
 };
 
 /// Analysis pass providing a never-invalidated alias analysis result.
Index: lib/Analysis/AliasAnalysisSummary.h
===================================================================
--- lib/Analysis/AliasAnalysisSummary.h
+++ lib/Analysis/AliasAnalysisSummary.h
@@ -114,11 +114,11 @@
   unsigned DerefLevel;
 };
 
-inline bool operator==(InterfaceValue lhs, InterfaceValue rhs) {
-  return lhs.Index == rhs.Index && lhs.DerefLevel == rhs.DerefLevel;
+inline bool operator==(InterfaceValue LHS, InterfaceValue RHS) {
+  return LHS.Index == RHS.Index && LHS.DerefLevel == RHS.DerefLevel;
 }
-inline bool operator!=(InterfaceValue lhs, InterfaceValue rhs) {
-  return !(lhs == rhs);
+inline bool operator!=(InterfaceValue LHS, InterfaceValue RHS) {
+  return !(LHS == RHS);
 }
 
 /// We use ExternalRelation to describe an externally visible aliasing relations
@@ -150,6 +150,26 @@
 };
 Optional<InstantiatedValue> instantiateInterfaceValue(InterfaceValue, CallSite);
 
+inline bool operator==(InstantiatedValue LHS, InstantiatedValue RHS) {
+  return LHS.Val == RHS.Val && LHS.DerefLevel == RHS.DerefLevel;
+}
+inline bool operator!=(InstantiatedValue LHS, InstantiatedValue RHS) {
+  return !(LHS == RHS);
+}
+inline bool operator<(InstantiatedValue LHS, InstantiatedValue RHS) {
+  return std::less<Value *>()(LHS.Val, RHS.Val) ||
+         (LHS.Val == RHS.Val && LHS.DerefLevel < RHS.DerefLevel);
+}
+inline bool operator>(InstantiatedValue LHS, InstantiatedValue RHS) {
+  return RHS < LHS;
+}
+inline bool operator<=(InstantiatedValue LHS, InstantiatedValue RHS) {
+  return !(RHS < LHS);
+}
+inline bool operator>=(InstantiatedValue LHS, InstantiatedValue RHS) {
+  return !(LHS < RHS);
+}
+
 /// This is the result of instantiating ExternalRelation at a particular
 /// callsite
 struct InstantiatedRelation {
Index: lib/Analysis/CFLAndersAliasAnalysis.cpp
===================================================================
--- lib/Analysis/CFLAndersAliasAnalysis.cpp
+++ lib/Analysis/CFLAndersAliasAnalysis.cpp
@@ -16,6 +16,24 @@
 // precise analysis result. The precision of this analysis is roughly the same
 // as that of an one level context-sensitive Andersen's algorithm.
 //
+// The algorithm used here is based on recursive state machine matching scheme
+// proposed in "Demand-driven alias analysis for C" by Xin Zheng and Radu
+// Rugina. The general idea is to extend the tranditional transitive closure
+// algorithm to perform CFL matching along the way: instead of recording
+// "whether X is reachable from Y", we keep track of "whether X is reachable
+// from Y at state Z", where the "state" field indicates where we are in the CFL
+// matching process. To understand the matching better, it is advisable to have
+// the state machine shown in Figure 3 of the paper available when reading the
+// codes: all we do here is to selectively expand the transitive closure by
+// discarding edges that are not recognized by the state machine.
+//
+// There is one difference between our current implementation and the one
+// described in the paper: out algorithm eagerly computes all alias pairs after
+// the CFLGraph is built, while in the paper the authors did the computation in
+// a demand-driven fashion. We did not implement the demand-driven algorithm due
+// to the additional coding complexity and higher memory profile, but if we
+// found it necessary we may switch to it eventually.
+//
 //===----------------------------------------------------------------------===//
 
 // N.B. AliasAnalysis as a whole is phrased as a FunctionPass at the moment, and
@@ -26,6 +44,7 @@
 
 #include "llvm/Analysis/CFLAndersAliasAnalysis.h"
 #include "CFLGraph.h"
+#include "llvm/ADT/DenseSet.h"
 #include "llvm/Pass.h"
 
 using namespace llvm;
@@ -33,12 +52,409 @@
 
 #define DEBUG_TYPE "cfl-anders-aa"
 
-CFLAndersAAResult::CFLAndersAAResult() = default;
+CFLAndersAAResult::CFLAndersAAResult(const TargetLibraryInfo &TLI) : TLI(TLI) {}
+CFLAndersAAResult::CFLAndersAAResult(CFLAndersAAResult &&RHS)
+    : AAResultBase(std::move(RHS)), TLI(RHS.TLI) {}
+CFLAndersAAResult::~CFLAndersAAResult() {}
+
+static const Function *parentFunctionOfValue(const 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;
+}
+
+static void sortInstantiatedValue(InstantiatedValue &LHS,
+                                  InstantiatedValue &RHS) {
+  if (LHS < RHS)
+    std::swap(LHS, RHS);
+}
+
+namespace {
+
+enum class MatchState : uint8_t {
+  FlowFrom = 0,     // S1 in the paper
+  FlowFromMemAlias, // S2 in the paper
+  FlowTo,           // S3 in the paper
+  FlowToMemAlias    // S4 in the paper
+};
+
+// We use ReachabilitySet to keep track of value aliases (The nonterminal "V" in
+// the paper) during the analysis.
+class ReachabilitySet {
+  typedef std::bitset<4> StateSet;
+  typedef DenseMap<InstantiatedValue, StateSet> ValueStateMap;
+  typedef DenseMap<InstantiatedValue, ValueStateMap> ValueReachMap;
+  ValueReachMap ReachMap;
+
+public:
+  typedef ValueStateMap::const_iterator const_valuestate_iterator;
+  typedef ValueReachMap::const_iterator const_value_iterator;
+
+  // Insert edge 'From->To' at state 'State'
+  bool insert(InstantiatedValue From, InstantiatedValue To, MatchState State) {
+    // Since value alias is a symmetric relation, we can enforce an order here
+    // and reduce the required storage by half
+    sortInstantiatedValue(From, To);
+    auto &States = ReachMap[To][From];
+    auto Idx = static_cast<size_t>(State);
+    if (!States.test(Idx)) {
+      States.set(Idx);
+      return true;
+    }
+    return false;
+  }
+
+  // Return the set of all ('From', 'State') pair for a given node 'To'
+  iterator_range<const_valuestate_iterator>
+  reachableValueAliases(InstantiatedValue V) const {
+    auto Itr = ReachMap.find(V);
+    if (Itr == ReachMap.end())
+      return make_range<const_valuestate_iterator>(const_valuestate_iterator(),
+                                                   const_valuestate_iterator());
+    else
+      return make_range<const_valuestate_iterator>(Itr->second.begin(),
+                                                   Itr->second.end());
+  }
+
+  iterator_range<const_value_iterator> value_mappings() const {
+    return make_range<const_value_iterator>(ReachMap.begin(), ReachMap.end());
+  }
+};
+
+// We use AliasMemSet to keep track of all memory aliases (the nonterminal "M"
+// in the papter) during the analysis
+class AliasMemSet {
+  typedef DenseSet<InstantiatedValue> MemSet;
+  typedef DenseMap<InstantiatedValue, MemSet> MemMapType;
+  MemMapType MemMap;
+
+public:
+  typedef MemSet::const_iterator const_mem_iterator;
+
+  bool insert(InstantiatedValue LHS, InstantiatedValue RHS) {
+    // Top-level values can never be memory aliases because one cannot take the
+    // addresses of them
+    assert(LHS.DerefLevel > 0 && RHS.DerefLevel > 0);
+
+    // Since value alias is a symmetric relation, we can enforce an order here
+    // and reduce the required storage by half
+    sortInstantiatedValue(LHS, RHS);
+    return MemMap[LHS].insert(RHS).second;
+  }
+
+  const MemSet *getMemoryAliases(InstantiatedValue V) const {
+    auto Itr = MemMap.find(V);
+    if (Itr == MemMap.end())
+      return nullptr;
+    else
+      return &Itr->second;
+  }
+};
+
+struct WorkListItem {
+  InstantiatedValue From;
+  InstantiatedValue To;
+  MatchState State;
+};
+}
+
+class CFLAndersAAResult::FunctionInfo {
+  /// Map a value to other values that may alias it
+  /// Since the alias relation is symmetric, to save some space we assume values
+  /// are properly ordered: if a and b alias each other, and a < b, then b is in
+  /// AliasMap[a] but not vice versa.
+  DenseMap<const Value *, std::vector<const Value *>> AliasMap;
+
+  /// Summary of externally visible effects.
+  AliasSummary Summary;
+
+public:
+  FunctionInfo(const ReachabilitySet &);
+
+  bool mayAlias(const Value *LHS, const Value *RHS) const;
+  const AliasSummary &getAliasSummary() const { return Summary; }
+};
+
+CFLAndersAAResult::FunctionInfo::FunctionInfo(const ReachabilitySet &ReachSet) {
+  for (const auto &OuterMapping : ReachSet.value_mappings()) {
+    // AliasMap only cares about top-level values
+    if (OuterMapping.first.DerefLevel > 0)
+      continue;
+
+    auto Val = OuterMapping.first.Val;
+    auto &AliasList = AliasMap[Val];
+    for (const auto &InnerMapping : OuterMapping.second) {
+      // Again, AliasMap only cares about top-level values
+      if (InnerMapping.first.DerefLevel == 0)
+        AliasList.push_back(InnerMapping.first.Val);
+    }
+
+    // Sort AliasList for faster lookup
+    std::sort(AliasList.begin(), AliasList.end());
+  }
+
+  // TODO: Populate function summary here
+}
+
+bool CFLAndersAAResult::FunctionInfo::mayAlias(const Value *LHS,
+                                               const Value *RHS) const {
+  assert(LHS && RHS);
+  if (std::less<const Value *>()(RHS, LHS))
+    std::swap(LHS, RHS);
+
+  auto Itr = AliasMap.find(LHS);
+  if (Itr == AliasMap.end())
+    return false;
+
+  // TODO: Check AliasAttrs before drawing any conclusions
+
+  return std::binary_search(Itr->second.begin(), Itr->second.end(), RHS);
+}
+
+static void propagate(InstantiatedValue From, InstantiatedValue To,
+                      MatchState State, ReachabilitySet &ReachSet,
+                      std::vector<WorkListItem> &WorkList) {
+  if (From == To)
+    return;
+  if (ReachSet.insert(From, To, State))
+    WorkList.push_back(WorkListItem{From, To, State});
+}
+
+static void initializeWorkList(std::vector<WorkListItem> &WorkList,
+                               ReachabilitySet &ReachSet,
+                               const CFLGraph &Graph) {
+  for (const auto &Mapping : Graph.value_mappings()) {
+    auto Val = Mapping.first;
+    auto &ValueInfo = Mapping.second;
+    assert(ValueInfo.getNumLevels() > 0);
+
+    // Insert all immediate assignment neighbors to the worklist
+    for (unsigned I = 0, E = ValueInfo.getNumLevels(); I < E; ++I) {
+      auto Src = InstantiatedValue{Val, I};
+      // If there's an assignment edge from X to Y, it means Y is reachable from
+      // X at S2 and X is reachable from Y at S1
+      for (auto &Edge : ValueInfo.getNodeInfoAtLevel(I).Edges) {
+        propagate(Edge.Other, Src, MatchState::FlowFrom, ReachSet, WorkList);
+        propagate(Src, Edge.Other, MatchState::FlowTo, ReachSet, WorkList);
+      }
+    }
+  }
+}
+
+static Optional<InstantiatedValue> getNodeBelow(const CFLGraph &Graph,
+                                                InstantiatedValue V) {
+  Optional<InstantiatedValue> Ret;
+  auto NodeBelow = InstantiatedValue{V.Val, V.DerefLevel + 1};
+  if (Graph.getNode(NodeBelow))
+    Ret = NodeBelow;
+  return Ret;
+}
+
+static void processWorkListItem(const WorkListItem &Item, const CFLGraph &Graph,
+                                ReachabilitySet &ReachSet, AliasMemSet &MemSet,
+                                std::vector<WorkListItem> &WorkList) {
+  auto FromNode = Item.From;
+  auto ToNode = Item.To;
+
+  auto NodeInfo = Graph.getNode(ToNode);
+  assert(NodeInfo != nullptr);
+
+  // TODO: propagate AliasAttr as well
+  // TODO: propagate field offsets
+
+  // The newly added value alias pair may pontentially generate more memory
+  // alias pairs. Check for them here.
+  auto FromNodeBelow = getNodeBelow(Graph, FromNode);
+  auto ToNodeBelow = getNodeBelow(Graph, ToNode);
+  if (FromNodeBelow && ToNodeBelow &&
+      MemSet.insert(*FromNodeBelow, *ToNodeBelow)) {
+    propagate(*FromNodeBelow, *ToNodeBelow, MatchState::FlowFromMemAlias,
+              ReachSet, WorkList);
+    for (const auto &Mapping : ReachSet.reachableValueAliases(*FromNodeBelow)) {
+      auto Src = Mapping.first;
+      if (Mapping.second.test(static_cast<size_t>(MatchState::FlowFrom)))
+        propagate(Src, *ToNodeBelow, MatchState::FlowFromMemAlias, ReachSet,
+                  WorkList);
+      if (Mapping.second.test(static_cast<size_t>(MatchState::FlowTo)))
+        propagate(Src, *ToNodeBelow, MatchState::FlowToMemAlias, ReachSet,
+                  WorkList);
+    }
+  }
+
+  // This is the core of the state machine walking algorithm. We expand ReachSet
+  // based on which state we are at (which in turn dictates what edges we
+  // should examine)
+  // From a high-level point of view, the state machine here guarantees two
+  // properties:
+  // - If *X and *Y are memory aliases, then X and Y are value aliases
+  // - If Y is an alias of X, then reverse assignment edges (if there is any)
+  // should precede any assignment edges on the path from X to Y.
+  switch (Item.State) {
+  case MatchState::FlowFrom: {
+    for (const auto &RevAssignEdge : NodeInfo->ReverseEdges)
+      propagate(FromNode, RevAssignEdge.Other, MatchState::FlowFrom, ReachSet,
+                WorkList);
+    for (const auto &AssignEdge : NodeInfo->Edges)
+      propagate(FromNode, AssignEdge.Other, MatchState::FlowTo, ReachSet,
+                WorkList);
+    if (auto AliasSet = MemSet.getMemoryAliases(ToNode)) {
+      for (const auto &MemAlias : *AliasSet)
+        propagate(FromNode, MemAlias, MatchState::FlowFromMemAlias, ReachSet,
+                  WorkList);
+    }
+    break;
+  }
+  case MatchState::FlowFromMemAlias: {
+    for (const auto &RevAssignEdge : NodeInfo->ReverseEdges)
+      propagate(FromNode, RevAssignEdge.Other, MatchState::FlowFrom, ReachSet,
+                WorkList);
+    for (const auto &AssignEdge : NodeInfo->Edges)
+      propagate(FromNode, AssignEdge.Other, MatchState::FlowTo, ReachSet,
+                WorkList);
+    break;
+  }
+  case MatchState::FlowTo: {
+    for (const auto &AssignEdge : NodeInfo->Edges)
+      WorkList.push_back(
+          WorkListItem{FromNode, AssignEdge.Other, MatchState::FlowTo});
+    if (auto AliasSet = MemSet.getMemoryAliases(ToNode)) {
+      for (const auto &MemAlias : *AliasSet)
+        propagate(FromNode, MemAlias, MatchState::FlowToMemAlias, ReachSet,
+                  WorkList);
+    }
+    break;
+  }
+  case MatchState::FlowToMemAlias: {
+    for (const auto &AssignEdge : NodeInfo->Edges)
+      WorkList.push_back(
+          WorkListItem{FromNode, AssignEdge.Other, MatchState::FlowTo});
+    break;
+  }
+  }
+}
+
+CFLAndersAAResult::FunctionInfo
+CFLAndersAAResult::buildInfoFrom(const Function &Fn) {
+  CFLGraphBuilder<CFLAndersAAResult> GraphBuilder(
+      *this, TLI,
+      // Cast away the constness here due to GraphBuilder's API requirement
+      const_cast<Function &>(Fn));
+  auto &Graph = GraphBuilder.getCFLGraph();
+
+  ReachabilitySet ReachSet;
+  AliasMemSet MemSet;
+
+  std::vector<WorkListItem> WorkList, NextList;
+  initializeWorkList(WorkList, ReachSet, Graph);
+  // TODO: make sure we don't stop before the fix point is reached
+  while (!WorkList.empty()) {
+    for (const auto &Item : WorkList)
+      processWorkListItem(Item, Graph, ReachSet, MemSet, NextList);
+
+    NextList.swap(WorkList);
+    NextList.clear();
+  }
+
+  return FunctionInfo(ReachSet);
+}
+
+void CFLAndersAAResult::scan(const Function &Fn) {
+  auto InsertPair = Cache.insert(std::make_pair(&Fn, Optional<FunctionInfo>()));
+  (void)InsertPair;
+  assert(InsertPair.second &&
+         "Trying to scan a function that has already been cached");
+
+  // Note that we can't do Cache[Fn] = buildSetsFrom(Fn) here: the function call
+  // may get evaluated after operator[], potentially triggering a DenseMap
+  // resize and invalidating the reference returned by operator[]
+  auto FunInfo = buildInfoFrom(Fn);
+  Cache[&Fn] = std::move(FunInfo);
+  Handles.push_front(FunctionHandle(const_cast<Function *>(&Fn), this));
+}
+
+void CFLAndersAAResult::evict(const Function &Fn) { Cache.erase(&Fn); }
+
+const Optional<CFLAndersAAResult::FunctionInfo> &
+CFLAndersAAResult::ensureCached(const Function &Fn) {
+  auto Iter = Cache.find(&Fn);
+  if (Iter == Cache.end()) {
+    scan(Fn);
+    Iter = Cache.find(&Fn);
+    assert(Iter != Cache.end());
+    assert(Iter->second.hasValue());
+  }
+  return Iter->second;
+}
+
+const AliasSummary *CFLAndersAAResult::getAliasSummary(const Function &Fn) {
+  auto &FunInfo = ensureCached(Fn);
+  if (FunInfo.hasValue())
+    return &FunInfo->getAliasSummary();
+  else
+    return nullptr;
+}
+
+AliasResult CFLAndersAAResult::query(const MemoryLocation &LocA,
+                                     const MemoryLocation &LocB) {
+  auto *ValA = LocA.Ptr;
+  auto *ValB = LocB.Ptr;
+
+  if (!ValA->getType()->isPointerTy() || !ValB->getType()->isPointerTy())
+    return NoAlias;
+
+  auto *Fn = parentFunctionOfValue(ValA);
+  if (!Fn) {
+    Fn = parentFunctionOfValue(ValB);
+    if (!Fn) {
+      // The only times this is known to happen are when globals + InlineAsm are
+      // involved
+      DEBUG(dbgs()
+            << "CFLAndersAA: could not extract parent function information.\n");
+      return MayAlias;
+    }
+  } else {
+    assert(!parentFunctionOfValue(ValB) || parentFunctionOfValue(ValB) == Fn);
+  }
+
+  assert(Fn != nullptr);
+  auto &FunInfo = ensureCached(*Fn);
+  assert(FunInfo.hasValue());
+
+  // AliasMap lookup
+  if (FunInfo->mayAlias(ValA, ValB))
+    return MayAlias;
+  return NoAlias;
+}
+
+AliasResult CFLAndersAAResult::alias(const MemoryLocation &LocA,
+                                     const MemoryLocation &LocB) {
+  if (LocA.Ptr == LocB.Ptr)
+    return LocA.Size == LocB.Size ? MustAlias : PartialAlias;
+
+  // Comparisons between global variables and other constants should be
+  // handled by BasicAA.
+  // CFLAndersAA may report NoAlias when comparing a GlobalValue and
+  // ConstantExpr, but every query needs to have at least one Value tied to a
+  // Function, and neither GlobalValues nor ConstantExprs are.
+  if (isa<Constant>(LocA.Ptr) && isa<Constant>(LocB.Ptr))
+    return AAResultBase::alias(LocA, LocB);
+
+  AliasResult QueryResult = query(LocA, LocB);
+  if (QueryResult == MayAlias)
+    return AAResultBase::alias(LocA, LocB);
+
+  return QueryResult;
+}
 
 char CFLAndersAA::PassID;
 
 CFLAndersAAResult CFLAndersAA::run(Function &F, AnalysisManager<Function> &AM) {
-  return CFLAndersAAResult();
+  return CFLAndersAAResult(AM.getResult<TargetLibraryAnalysis>(F));
 }
 
 char CFLAndersAAWrapperPass::ID = 0;
@@ -53,8 +469,12 @@
   initializeCFLAndersAAWrapperPassPass(*PassRegistry::getPassRegistry());
 }
 
-void CFLAndersAAWrapperPass::initializePass() {}
+void CFLAndersAAWrapperPass::initializePass() {
+  auto &TLIWP = getAnalysis<TargetLibraryInfoWrapperPass>();
+  Result.reset(new CFLAndersAAResult(TLIWP.getTLI()));
+}
 
 void CFLAndersAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.setPreservesAll();
+  AU.addRequired<TargetLibraryInfoWrapperPass>();
 }
Index: lib/Analysis/CFLGraph.h
===================================================================
--- lib/Analysis/CFLGraph.h
+++ lib/Analysis/CFLGraph.h
@@ -45,7 +45,7 @@
   typedef std::vector<Edge> EdgeList;
 
   struct NodeInfo {
-    EdgeList Edges;
+    EdgeList Edges, ReverseEdges;
     AliasAttrs Attr;
   };
 
@@ -77,12 +77,6 @@
   typedef DenseMap<Value *, ValueInfo> ValueMap;
   ValueMap ValueImpls;
 
-  const NodeInfo *getNode(Node N) const {
-    auto Itr = ValueImpls.find(N.Val);
-    if (Itr == ValueImpls.end() || Itr->second.getNumLevels() <= N.DerefLevel)
-      return nullptr;
-    return &Itr->second.getNodeInfoAtLevel(N.DerefLevel);
-  }
   NodeInfo *getNode(Node N) {
     auto Itr = ValueImpls.find(N.Val);
     if (Itr == ValueImpls.end() || Itr->second.getNumLevels() <= N.DerefLevel)
@@ -114,6 +108,14 @@
     assert(ToInfo != nullptr);
 
     FromInfo->Edges.push_back(Edge{To});
+    ToInfo->ReverseEdges.push_back(Edge{From});
+  }
+
+  const NodeInfo *getNode(Node N) const {
+    auto Itr = ValueImpls.find(N.Val);
+    if (Itr == ValueImpls.end() || Itr->second.getNumLevels() <= N.DerefLevel)
+      return nullptr;
+    return &Itr->second.getNodeInfoAtLevel(N.DerefLevel);
   }
 
   AliasAttrs attrFor(Node N) const {
@@ -204,7 +206,7 @@
       }
     }
 
-    void addDerefEdge(Value *From, Value *To) {
+    void addLoadEdge(Value *From, Value *To) {
       assert(From != nullptr && To != nullptr);
       if (!From->getType()->isPointerTy() || !To->getType()->isPointerTy())
         return;
@@ -214,6 +216,16 @@
       Graph.addEdge(InstantiatedValue{From, 1}, InstantiatedValue{To, 0});
     }
 
+    void addStoreEdge(Value *From, Value *To) {
+      assert(From != nullptr && To != nullptr);
+      if (!From->getType()->isPointerTy() || !To->getType()->isPointerTy())
+        return;
+      addNode(From);
+      addNode(To);
+      Graph.addNode(InstantiatedValue{To, 1});
+      Graph.addEdge(InstantiatedValue{From, 0}, InstantiatedValue{To, 1});
+    }
+
   public:
     GetEdgesVisitor(CFLGraphBuilder &Builder)
         : AA(Builder.Analysis), TLI(Builder.TLI), Graph(Builder.Graph),
@@ -257,13 +269,13 @@
     void visitAtomicCmpXchgInst(AtomicCmpXchgInst &Inst) {
       auto *Ptr = Inst.getPointerOperand();
       auto *Val = Inst.getNewValOperand();
-      addDerefEdge(Ptr, Val);
+      addStoreEdge(Val, Ptr);
     }
 
     void visitAtomicRMWInst(AtomicRMWInst &Inst) {
       auto *Ptr = Inst.getPointerOperand();
       auto *Val = Inst.getValOperand();
-      addDerefEdge(Ptr, Val);
+      addStoreEdge(Val, Ptr);
     }
 
     void visitPHINode(PHINode &Inst) {
@@ -293,13 +305,13 @@
     void visitLoadInst(LoadInst &Inst) {
       auto *Ptr = Inst.getPointerOperand();
       auto *Val = &Inst;
-      addDerefEdge(Ptr, Val);
+      addLoadEdge(Ptr, Val);
     }
 
     void visitStoreInst(StoreInst &Inst) {
       auto *Ptr = Inst.getPointerOperand();
       auto *Val = Inst.getValueOperand();
-      addDerefEdge(Ptr, Val);
+      addStoreEdge(Val, Ptr);
     }
 
     void visitVAArgInst(VAArgInst &Inst) {
@@ -420,14 +432,14 @@
     void visitExtractElementInst(ExtractElementInst &Inst) {
       auto *Ptr = Inst.getVectorOperand();
       auto *Val = &Inst;
-      addDerefEdge(Ptr, Val);
+      addLoadEdge(Ptr, Val);
     }
 
     void visitInsertElementInst(InsertElementInst &Inst) {
       auto *Vec = Inst.getOperand(0);
       auto *Val = Inst.getOperand(1);
       addAssignEdge(Vec, &Inst);
-      addDerefEdge(&Inst, Val);
+      addStoreEdge(Val, &Inst);
     }
 
     void visitLandingPadInst(LandingPadInst &Inst) {
@@ -441,12 +453,12 @@
       auto *Agg = Inst.getOperand(0);
       auto *Val = Inst.getOperand(1);
       addAssignEdge(Agg, &Inst);
-      addDerefEdge(&Inst, Val);
+      addStoreEdge(Val, &Inst);
     }
 
     void visitExtractValueInst(ExtractValueInst &Inst) {
       auto *Ptr = Inst.getAggregateOperand();
-      addDerefEdge(Ptr, &Inst);
+      addLoadEdge(Ptr, &Inst);
     }
 
     void visitShuffleVectorInst(ShuffleVectorInst &Inst) {
Index: test/Analysis/CFLAliasAnalysis/Andersen/assign.ll
===================================================================
--- /dev/null
+++ test/Analysis/CFLAliasAnalysis/Andersen/assign.ll
@@ -0,0 +1,24 @@
+; This testcase ensures that CFL AA handles assignment in an inclusion-based 
+; manner
+
+; RUN: opt < %s -disable-basicaa -cfl-anders-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+; RUN: opt < %s -aa-pipeline=cfl-anders-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+
+; CHECK-LABEL: Function: test_assign
+; CHECK: NoAlias: i64* %a, i64* %b
+; CHECK: NoAlias: i32* %c, i64* %b
+; CHECK: NoAlias: i32* %d, i64* %a
+; CHECK: NoAlias: i32* %c, i32* %d
+; CHECK: MayAlias: i32* %e, i64* %a
+; CHECK: MayAlias: i32* %e, i64* %b
+; CHECK: MayAlias: i32* %c, i32* %e
+; CHECK: MayAlias: i32* %d, i32* %e
+define void @test_assign(i1 %cond) {
+  %a = alloca i64, align 8
+  %b = alloca i64, align 8
+
+  %c = bitcast i64* %a to i32*
+  %d = bitcast i64* %b to i32*
+  %e = select i1 %cond, i32* %c, i32* %d
+  ret void
+}
\ No newline at end of file
Index: test/Analysis/CFLAliasAnalysis/Andersen/assign2.ll
===================================================================
--- /dev/null
+++ test/Analysis/CFLAliasAnalysis/Andersen/assign2.ll
@@ -0,0 +1,23 @@
+; This testcase ensures that CFL AA handles assignment in an inclusion-based 
+; manner
+
+; RUN: opt < %s -disable-basicaa -cfl-anders-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+; RUN: opt < %s -aa-pipeline=cfl-anders-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+
+; CHECK-LABEL: Function: test_assign2
+; CHECK: NoAlias: i32* %b, i64* %a
+; CHECK: NoAlias: i32* %b, i32* %c
+; CHECK: NoAlias: i32* %b, i32* %d
+; CHECK: MayAlias: i32* %e, i64* %a
+; CHECK: MayAlias: i32* %b, i32* %e
+; CHECK: MayAlias: i32* %c, i32* %e
+; CHECK: MayAlias: i32* %d, i32* %e
+define void @test_assign2(i1 %cond) {
+	%a = alloca i64, align 8
+	%b = alloca i32, align 4
+
+	%c = bitcast i64* %a to i32*
+	%d = bitcast i64* %a to i32*
+	%e = select i1 %cond, i32* %c, i32* %b
+	ret void
+}
\ No newline at end of file
Index: test/Analysis/CFLAliasAnalysis/Andersen/cycle.ll
===================================================================
--- /dev/null
+++ test/Analysis/CFLAliasAnalysis/Andersen/cycle.ll
@@ -0,0 +1,34 @@
+; This testcase ensures that CFL AA handles assignment cycles correctly
+
+; RUN: opt < %s -disable-basicaa -cfl-anders-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+; RUN: opt < %s -aa-pipeline=cfl-anders-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+
+; CHECK-LABEL: Function: test_cycle
+; CHECK: NoAlias: i64* %a, i64** %b
+; CHECK: NoAlias: i64* %a, i64*** %c
+; CHECK: NoAlias: i64** %b, i64*** %c
+; CHECK: NoAlias: i64* %a, i64**** %d
+; CHECK: NoAlias: i64** %b, i64**** %d
+; CHECK: NoAlias: i64*** %c, i64**** %d
+; CHECK: NoAlias: i64* %a, i64* %e
+; CHECK: NoAlias: i64* %e, i64** %b
+; CHECK: NoAlias: i64* %e, i64*** %c
+; CHECK: MayAlias: i64* %a, i64* %f
+; CHECK: NoAlias: i64* %f, i64** %b
+; CHECK: NoAlias: i64* %f, i64*** %c
+; CHECK: MayAlias: i64* %f, i64**** %d
+; CHECK: MayAlias: i64* %e, i64* %f
+define void @test_cycle() {
+  %a = alloca i64, align 8
+  %b = alloca i64*, align 8
+  %c = alloca i64**, align 8
+  %d = alloca i64***, align 8
+  store i64* %a, i64** %b
+  store i64** %b, i64*** %c
+  store i64*** %c, i64**** %d
+
+  %e = bitcast i64**** %d to i64*
+  store i64* %e, i64** %b
+  %f = load i64*, i64** %b
+  ret void
+}
Index: test/Analysis/CFLAliasAnalysis/Andersen/memalias.ll
===================================================================
--- /dev/null
+++ test/Analysis/CFLAliasAnalysis/Andersen/memalias.ll
@@ -0,0 +1,21 @@
+; This testcase ensures that CFL AA correctly handles simple memory alias 
+; pattern
+
+; RUN: opt < %s -disable-basicaa -cfl-anders-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+; RUN: opt < %s -aa-pipeline=cfl-anders-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+
+; CHECK-LABEL: Function: test_memalias
+; CHECK: NoAlias: i64* %a, i64** %b
+; CHECK: NoAlias: i32** %c, i64* %a
+; CHECK: MayAlias: i32* %d, i64* %a
+; CHECK: NoAlias: i32* %d, i64** %b
+; CHECK: NoAlias: i32* %d, i32** %c
+define void @test_memalias() {
+  %a = alloca i64, align 8
+  %b = alloca i64*, align 8
+  store i64* %a, i64** %b
+
+  %c = bitcast i64** %b to i32**
+  %d = load i32*, i32** %c
+  ret void
+}
\ No newline at end of file