Index: include/llvm/Analysis/Passes.h
===================================================================
--- include/llvm/Analysis/Passes.h
+++ include/llvm/Analysis/Passes.h
@@ -66,6 +66,13 @@
 
   //===--------------------------------------------------------------------===//
   //
+  // createCFLAliasAnalysisPass - This pass implements a set-based approach to
+  // alias analysis.
+  //
+  ImmutablePass *createCFLAliasAnalysisPass();
+
+  //===--------------------------------------------------------------------===//
+  //
   /// createLibCallAliasAnalysisPass - Create an alias analysis pass that knows
   /// about the semantics of a set of libcalls specified by LCI.  The newly
   /// constructed pass takes ownership of the pointer that is provided.
Index: include/llvm/InitializePasses.h
===================================================================
--- include/llvm/InitializePasses.h
+++ include/llvm/InitializePasses.h
@@ -89,6 +89,7 @@
 void initializeCFGOnlyViewerPass(PassRegistry&);
 void initializeCFGPrinterPass(PassRegistry&);
 void initializeCFGSimplifyPassPass(PassRegistry&);
+void initializeCFLAliasAnalysisPass(PassRegistry&);
 void initializeFlattenCFGPassPass(PassRegistry&);
 void initializeStructurizeCFGPass(PassRegistry&);
 void initializeCFGViewerPass(PassRegistry&);
Index: include/llvm/LinkAllPasses.h
===================================================================
--- include/llvm/LinkAllPasses.h
+++ include/llvm/LinkAllPasses.h
@@ -62,6 +62,7 @@
       (void) llvm::createCallGraphPrinterPass();
       (void) llvm::createCallGraphViewerPass();
       (void) llvm::createCFGSimplificationPass();
+      (void) llvm::createCFLAliasAnalysisPass();
       (void) llvm::createStructurizeCFGPass();
       (void) llvm::createConstantMergePass();
       (void) llvm::createConstantPropagationPass();
Index: lib/Analysis/CFLAliasAnalysis.cpp
===================================================================
--- /dev/null
+++ lib/Analysis/CFLAliasAnalysis.cpp
@@ -0,0 +1,770 @@
+//===- CFLAliasAnalysis.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 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 here: www.cs.cornell.edu/~rugina/papers/popl08.pdf and here:
+// www.cse.cuhk.edu.hk/lyu/_media/paper/pldi2013.pdf -- 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.
+//
+// Two variables are considered as aliasing iff you can reach one value's node
+// from the other value's node and the language formed by concatenating all of
+// the edge labels (actions) conforms to a context-free grammar.
+//
+// Because this algorithm requires a graph search on each query, we execute the
+// algorithm outlined in pldi2013.pdf (above) in order to transform the graph
+// into sets of variables that may alias in ~nlogn time (n = number of
+// variables.). This makes queries take constant time.
+//===----------------------------------------------------------------------===//
+
+#include "StratifiedSets.h"
+#include "WeightedBidirectedGraph.h"
+#include "llvm/Analysis/Passes.h"
+#include "llvm/ADT/BitVector.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/Optional.h"
+#include "llvm/ADT/None.h"
+#include "llvm/Analysis/AliasAnalysis.h"
+#include "llvm/IR/Constants.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/InstVisitor.h"
+#include "llvm/Pass.h"
+#include "llvm/Support/ErrorHandling.h"
+#include <algorithm>
+#include <cassert>
+#include <tuple>
+using namespace llvm;
+
+// Try to go from a Value* to a Function*. Never returns nullptr.
+static Optional<Function *> valueToFunction(Value *);
+
+// 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 *, SmallVectorImpl<Function *> *);
+
+// 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 *);
+
+// There are certain instructions (i.e. FenceInst, etc.) that we ignore.
+// This detects those.
+static bool hasUsefulEdges(Instruction *inst);
+
+// Is this value a global or not-noalias argument?
+static bool isAliasingExternal(Value *val);
+
+namespace {
+// \brief StratifiedSets call for knowledge of "direction", so this is how we
+// represent that locally.
+enum class Direction { None, Above, Below };
+
+// \brief Edges can be one of four "weights" -- each weight must have an inverse
+// weight (AssignFrom has AssignTo; Reference has Dereference).
+enum class EdgeWeight {
+  // The weight assigned when assigning from a value. For example, in:
+  // %b = getelementptr %a, 0
+  // ...The relationship is %b assignFrom %a
+  AssignFrom,
+  // The inverse of AssignFrom -- used when we assign to a value. As can be
+  // expected, given
+  // %b = getelementptr %a, 0
+  // ...The relationship is %a assignTo %b
+  // TODO: Maybe merge this with AssignFrom if it carries no benefit.
+  AssignTo,
+  // The edge used when we have an edge going from some handle to a Value.
+  // Examples of this include:
+  // %b = load %a              (%b Dereference %a)
+  // %b = extractelement %a, 0 (%b Dereference %a)
+  // TODO: Rename this + Reference
+  Dereference,
+
+  // The edge used when our edge goes from a value to a handle that may have
+  // contained it at some point. Examples:
+  // %b = load %a              (%a Reference %b)
+  // %b = extractelement %a, 0 (%a Reference %b)
+  Reference
+};
+
+// \brief Encodes the notion of a "use"
+struct Edge {
+  // \brief Which value the edge is coming from
+  Value *from;
+  // \brief Which value the edge is pointing to
+  Value *to;
+  // \brief Edge weight
+  EdgeWeight weight;
+  // \brief Whether we aliased any external values along the way that may be
+  // invisible to the analysis (i.e. landingpad for exceptions, calls for
+  // interprocedural analysis, etc.)
+  bool aliasedExternal;
+
+  Edge(Value *from, Value *to, EdgeWeight w, bool a)
+      : from(from), to(to), weight(w), aliasedExternal(a) {}
+};
+
+struct CFLAliasAnalysis : public ImmutablePass, public AliasAnalysis {
+private:
+  /// \brief Cached mapping of Functions to their StratifiedSets.
+  /// If a function's sets arecurrently 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 *, Optional<StratifiedSets<Value *>>> cache;
+
+public:
+  static char ID;
+
+  CFLAliasAnalysis() : ImmutablePass(ID) {
+    initializeCFLAliasAnalysisPass(*PassRegistry::getPassRegistry());
+  }
+
+  void getAnalysisUsage(AnalysisUsage &AU) const {
+    AliasAnalysis::getAnalysisUsage(AU);
+  }
+
+  void *getAdjustedAnalysisPointer(const void *ID) override {
+    if (ID == &AliasAnalysis::ID)
+      return (AliasAnalysis *)this;
+    return this;
+  }
+
+  /// \brief Inserts the given Function into the cache.
+  void scan(Function *fn);
+
+  /// \brief Ensures that the given function is available in the cache.
+  /// Returns the appropriate entry from the cache.
+  const Optional<StratifiedSets<Value *>> &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.hasValue());
+    }
+    return iter->second;
+  }
+
+  Optional<AliasResult> query(const Location &locA, const Location &locB);
+
+  AliasResult alias(const Location &locA, const Location &locB) override {
+    // This should be covered by BasicAA, but it's super cheap to check.
+    if (locA.Ptr == locB.Ptr) {
+      if (locA.Size == locB.Size) {
+        return MustAlias;
+      } else {
+        return PartialAlias;
+      }
+    }
+
+    if (isa<Constant>(locA.Ptr) && isa<Constant>(locB.Ptr)) {
+      return MayAlias;
+    }
+
+    auto maybeResult = query(locA, locB);
+    if (!maybeResult.hasValue()) {
+      return MayAlias;
+    }
+
+    return *maybeResult;
+  }
+
+  void initializePass() override { InitializeAliasAnalysis(this); }
+};
+
+// \brief Gets the edges our graph should have, based on an Instruction*
+//
+// Currently everything returns an Optional<bool> because it makes life easier
+// to be able to selectively disable support for instructions and troubleshoot
+// our coverage of the instructions we'll get. I plan to remove this as this AA
+// gets tested more/nearer finalization.
+//
+// Return values:
+//    Nothing     - Unknown instruction. Program should die.
+//    Just(false) - Known instruction, but not supported (probably disabled
+//      while trying to find a bug). Discard results from GetEdgesVisitor.
+//    Just(true)  - Known instruction, results are valid. Continue as normal.
+class GetEdgesVisitor : public InstVisitor<GetEdgesVisitor, Optional<bool>> {
+  CFLAliasAnalysis *aa;
+  SmallVectorImpl<Edge> *output;
+
+public:
+  GetEdgesVisitor(CFLAliasAnalysis *aa, SmallVectorImpl<Edge> *output)
+      : aa(aa), output(output) {}
+
+  Optional<bool> visitInstruction(Instruction &) { return NoneType(); }
+
+  Optional<bool> visitCastInst(CastInst &inst) {
+    assert(isa<CastInst>(inst));
+    output->push_back(
+        {&inst, inst.getOperand(0), EdgeWeight::AssignFrom, false});
+    // Casting does nothing -- it's the operations on the casted value that we
+    // get restrictive about.
+    return true;
+  }
+
+  Optional<bool> visitBinaryOperator(BinaryOperator &inst) {
+    auto *op1 = inst.getOperand(0);
+    auto *op2 = inst.getOperand(1);
+    output->push_back({&inst, op1, EdgeWeight::AssignFrom, false});
+    output->push_back({&inst, op2, EdgeWeight::AssignFrom, false});
+    return true;
+  }
+
+  Optional<bool> visitAtomicCmpXchgInst(AtomicCmpXchgInst &inst) {
+    auto *ptr = inst.getPointerOperand();
+    auto *val = inst.getNewValOperand();
+    output->push_back({ptr, val, EdgeWeight::Dereference, false});
+    return true;
+  }
+
+  Optional<bool> visitAtomicRMWInst(AtomicRMWInst &inst) {
+    auto *ptr = inst.getPointerOperand();
+    auto *val = inst.getValOperand();
+    output->push_back({ptr, val, EdgeWeight::Dereference, false});
+    return true;
+  }
+
+  Optional<bool> visitPHINode(PHINode &inst) {
+    for (unsigned i = 0, e = inst.getNumIncomingValues(); i < e; ++i) {
+      Value *val = inst.getIncomingValue(i);
+      output->push_back({&inst, val, EdgeWeight::AssignFrom, false});
+    }
+    return true;
+  }
+
+  Optional<bool> visitGetElementPtrInst(GetElementPtrInst &inst) {
+    Value *op = inst.getPointerOperand();
+    output->push_back({&inst, op, EdgeWeight::AssignFrom, false});
+    return true;
+  }
+
+  Optional<bool> visitSelectInst(SelectInst &inst) {
+    auto *trueVal = inst.getTrueValue();
+    auto *falseVal = inst.getFalseValue();
+    output->push_back({&inst, trueVal, EdgeWeight::AssignFrom, false});
+    output->push_back({&inst, falseVal, EdgeWeight::AssignFrom, false});
+    return true;
+  }
+
+  Optional<bool> visitAllocaInst(AllocaInst &inst) { return true; }
+
+  Optional<bool> visitLoadInst(LoadInst &inst) {
+    auto *ptr = inst.getPointerOperand();
+    auto *val = &inst;
+    output->push_back({val, ptr, EdgeWeight::Reference, false});
+    return true;
+  }
+
+  Optional<bool> visitStoreInst(StoreInst &inst) {
+    auto *ptr = inst.getPointerOperand();
+    auto *val = inst.getValueOperand();
+    output->push_back({ptr, val, EdgeWeight::Dereference, false});
+    return true;
+  }
+
+  static bool isFunctionExternal(Function *fn) {
+    return fn->getBasicBlockList().empty();
+  }
+
+  bool tryInterproceduralAnalysis(const SmallVectorImpl<Function *> &fns) {
+    bool externalFns = std::any_of(fns.begin(), fns.end(), isFunctionExternal);
+    if (externalFns) {
+      return false;
+    }
+
+    assert(fns.size() > 0);
+    bool onlyReadMemory =
+        std::all_of(fns.begin(), fns.end(),
+                    [](const Function *fn) { return fn->onlyReadsMemory(); });
+
+    if (onlyReadMemory) {
+      return true;
+    }
+    return false;
+  }
+
+  // TODO: Maybe just split the same code into two methods.
+  template <typename Inst> Optional<bool> visitCallLikeInst(Inst &inst) {
+    SmallVector<Function *, 4> targets;
+    // TODO: Interprocedural
+    if (getPossibleTargets(&inst, &targets)) {
+      bool success = tryInterproceduralAnalysis(targets);
+      if (success) {
+        return true;
+      }
+      // tryInterproceduralAnalysis doesn't clean up after itself if it fails,
+      // so we take care of that for it. This isn't a necessary step -- we're
+      // just adding edges that are laxer than anything that interprocedural
+      // will put in output, so there's no point in wasting cycles on what's
+      // currently there.
+      output->clear();
+    }
+
+    for (Value *v : inst.arg_operands()) {
+      output->push_back({&inst, v, EdgeWeight::AssignFrom, true});
+    }
+
+    return true;
+  }
+
+  Optional<bool> visitCallInst(CallInst &inst) {
+    return visitCallLikeInst(inst);
+  }
+
+  Optional<bool> visitInvokeInst(InvokeInst &inst) {
+    return 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.
+  Optional<bool> visitExtractElementInst(ExtractElementInst &inst) {
+    auto *ptr = inst.getVectorOperand();
+    auto *val = &inst;
+    output->push_back({val, ptr, EdgeWeight::Reference, false});
+    return true;
+  }
+
+  Optional<bool> visitInsertElementInst(InsertElementInst &inst) {
+    auto *vec = inst.getOperand(0);
+    auto *val = inst.getOperand(1);
+    output->push_back({&inst, vec, EdgeWeight::AssignFrom, false});
+    output->push_back({&inst, val, EdgeWeight::Dereference, false});
+    return true;
+  }
+
+  Optional<bool> visitLandingPadInst(LandingPadInst &inst) {
+    // Exceptions come from "nowhere", from our analysis' perspective.
+    // So we place the instruction its own group, noting that said group may
+    // alias externals
+    output->push_back({&inst, &inst, EdgeWeight::AssignTo, true});
+    return true;
+  }
+
+  Optional<bool> visitInsertValueInst(InsertValueInst &inst) {
+    auto *agg = inst.getOperand(0);
+    auto *val = inst.getOperand(1);
+    output->push_back({&inst, agg, EdgeWeight::AssignFrom, false});
+    output->push_back({&inst, val, EdgeWeight::Dereference, false});
+    return true;
+  }
+
+  Optional<bool> visitExtractValueInst(ExtractValueInst &inst) {
+    auto *ptr = inst.getAggregateOperand();
+    output->push_back({&inst, ptr, EdgeWeight::Reference, false});
+    return true;
+  }
+
+  Optional<bool> visitShuffleVectorInst(ShuffleVectorInst &inst) {
+    auto *from1 = inst.getOperand(0);
+    auto *from2 = inst.getOperand(1);
+    output->push_back({&inst, from1, EdgeWeight::AssignFrom, false});
+    output->push_back({&inst, from2, EdgeWeight::AssignFrom, false});
+    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, Optional<Value *>> {
+public:
+  Optional<Value *> visitInstruction(Instruction &) { return NoneType(); }
+  Optional<Value *> visitCastInst(CastInst &inst) { return &inst; }
+  Optional<Value *> visitBinaryOperator(BinaryOperator &inst) { return &inst; }
+  Optional<Value *> visitLoadInst(LoadInst &inst) { return &inst; }
+  Optional<Value *> visitSelectInst(SelectInst &inst) { return &inst; }
+  Optional<Value *> visitAllocaInst(AllocaInst &inst) { return &inst; }
+  Optional<Value *> visitPHINode(PHINode &inst) { return &inst; }
+  Optional<Value *> visitCallInst(CallInst &inst) { return &inst; }
+  Optional<Value *> visitInvokeInst(InvokeInst &inst) { return &inst; }
+  Optional<Value *> visitShuffleVectorInst(ShuffleVectorInst &inst) {
+    return &inst;
+  }
+
+  Optional<Value *> visitExtractValueInst(ExtractValueInst &inst) {
+    return &inst;
+  }
+
+  Optional<Value *> visitAtomicCmpXchgInst(AtomicCmpXchgInst &inst) {
+    return inst.getPointerOperand();
+  }
+
+  Optional<Value *> visitAtomicRMWInst(AtomicRMWInst &inst) {
+    return inst.getPointerOperand();
+  }
+
+  Optional<Value *> visitGetElementPtrInst(GetElementPtrInst &inst) {
+    return &inst;
+  }
+
+  Optional<Value *> visitStoreInst(StoreInst &inst) {
+    return inst.getPointerOperand();
+  }
+
+  Optional<Value *> visitExtractElementInst(ExtractElementInst &inst) {
+    return &inst;
+  }
+
+  Optional<Value *> visitInsertElementInst(InsertElementInst &inst) {
+    return inst.getOperand(0);
+  }
+
+  Optional<Value *> visitInsertValueInst(InsertValueInst &inst) {
+    return inst.getAggregateOperand();
+  }
+};
+
+typedef WeightedBidirectedGraph<std::pair<EdgeWeight, bool>> Graph;
+typedef DenseMap<Value *, Graph::Node> NodeMap;
+}
+
+// -- Setting up/registering CFLAA pass -- //
+char CFLAliasAnalysis::ID = 0;
+
+INITIALIZE_AG_PASS(CFLAliasAnalysis, AliasAnalysis, "cfl-aa",
+                   "CFL-Based AA implementation", false, true, false)
+
+ImmutablePass *llvm::createCFLAliasAnalysisPass() {
+  return new CFLAliasAnalysis();
+}
+
+//===----------------------------------------------------------------------===//
+// Function declarations that require types defined in the namespace above
+//===----------------------------------------------------------------------===//
+
+// Gets the inverse of a given EdgeWeight.
+static EdgeWeight flipWeight(EdgeWeight initial);
+
+// Gets edges of the given Instruction*, writing them to the SmallVector*.
+// The return value is whether or not we were able to convert the arguments to
+// edges. True if we could, false if we couldn't. If you hand this function an
+// instruction it didn't expect, we break. Yay. (For more information on what it
+// expects/how to add instruction support, see GetEdgesVisitor)
+static bool argsToEdges(CFLAliasAnalysis *, Instruction *,
+                        SmallVectorImpl<Edge> *);
+
+// Gets the "Direction" that one should travel in StratifiedSets
+// given an EdgeWeight.
+static Direction directionOfEdgeWeight(EdgeWeight);
+
+// Builds the graph needed for constructing the StratifiedSets for the
+// given function
+static bool buildGraphFrom(CFLAliasAnalysis *, Function *, NodeMap *, Graph *);
+
+// Builds the graph + StratifiedSets for a function.
+static Optional<StratifiedSets<Value *>> buildSetsFrom(CFLAliasAnalysis *,
+                                                       Function *);
+
+//===----------------------------------------------------------------------===//
+// Definitions of static functions declared at the top/middle of the file
+//===----------------------------------------------------------------------===//
+static Optional<Function *> valueToFunction(Value *val) {
+  if (auto *inst = dyn_cast<Instruction>(val)) {
+    auto *bb = inst->getParent();
+    return bb->getParent();
+  } else if (auto *arg = dyn_cast<Argument>(val)) {
+    return arg->getParent();
+  }
+  return NoneType();
+}
+
+// TODO: Make this look at virtual calls, etc.
+template <typename Inst>
+static bool getPossibleTargets(Inst *call,
+                               SmallVectorImpl<Function *> *output) {
+  if (auto *fn = call->getCalledFunction()) {
+    output->push_back(fn);
+    return true;
+  }
+  return false;
+}
+
+static Optional<Value *> getTargetValue(Instruction *inst) {
+  GetTargetValueVisitor v;
+  return v.visit(inst);
+}
+
+static bool hasUsefulEdges(Instruction *inst) {
+  bool isExcitingTerminator =
+      isa<InvokeInst>(inst) || isa<LandingPadInst>(inst);
+  return !isa<TerminatorInst>(inst) || isExcitingTerminator;
+}
+
+static bool isAliasingExternal(Value *val) {
+  bool isGlobal = isa<GlobalValue>(val);
+  auto *arg = dyn_cast<Argument>(val);
+  bool isAliasArg = arg != nullptr && !arg->hasNoAliasAttr();
+  return isGlobal || isAliasArg;
+}
+
+static EdgeWeight flipWeight(EdgeWeight initial) {
+  switch (initial) {
+  case EdgeWeight::AssignFrom:
+    return EdgeWeight::AssignTo;
+  case EdgeWeight::AssignTo:
+    return EdgeWeight::AssignFrom;
+  case EdgeWeight::Dereference:
+    return EdgeWeight::Reference;
+  case EdgeWeight::Reference:
+    return EdgeWeight::Dereference;
+  }
+  llvm_unreachable("Incomplete coverage of EdgeWeight enum");
+}
+
+static bool argsToEdges(CFLAliasAnalysis *analysis, Instruction *inst,
+                        SmallVectorImpl<Edge> *output) {
+  GetEdgesVisitor v(analysis, output);
+  auto maybeResult = v.visit(inst);
+  if (maybeResult.hasValue()) {
+    return *maybeResult;
+  }
+
+  llvm_unreachable("Got unrecognized instruction.");
+}
+
+static Direction directionOfEdgeWeight(EdgeWeight weight) {
+  switch (weight) {
+  case EdgeWeight::Reference:
+    return Direction::Above;
+  case EdgeWeight::Dereference:
+    return Direction::Below;
+  case EdgeWeight::AssignFrom:
+  case EdgeWeight::AssignTo:
+    return Direction::None;
+  }
+  llvm_unreachable("Incomplete switch coverage");
+}
+
+// Aside: We may remove graph construction entirely, because it doesn't really
+// buy us much that we don't already have. I'd like to add interprocedural
+// analysis prior to this however, in case that somehow requires the graph
+// produced by this for efficient execution
+static bool buildGraphFrom(CFLAliasAnalysis *analysis, Function *fn,
+                           NodeMap *map, Graph *graph) {
+  const auto findOrInsertNode = [map, graph](Value *val) {
+    auto pair = map->insert({val, Graph::Node()});
+    auto &iter = pair.first;
+    if (pair.second) {
+      auto newNode = graph->addNode();
+      iter->second = newNode;
+    }
+    return iter->second;
+  };
+
+  SmallVector<Edge, 8> edges;
+  for (auto &bb : fn->getBasicBlockList()) {
+    for (auto &inst : bb.getInstList()) {
+      // We don't want the edges of most "return" instructions, but we *do* want
+      // to know what all can be returned.
+      if (!hasUsefulEdges(&inst)) {
+        continue;
+      }
+
+      edges.clear();
+      bool ok = argsToEdges(analysis, &inst, &edges);
+      if (!ok) {
+        map->clear();
+        *graph = Graph();
+        return false;
+      }
+
+      // In the case of an unused alloca (or similar), edges may be empty. Note
+      // that it exists so we can potentially answer NoAlias.
+      if (edges.empty()) {
+        auto maybeVal = getTargetValue(&inst);
+        assert(maybeVal.hasValue());
+        auto *target = *maybeVal;
+        findOrInsertNode(target);
+        continue;
+      }
+
+      for (const Edge &e : edges) {
+        auto to = findOrInsertNode(e.to);
+        auto from = findOrInsertNode(e.from);
+        auto flippedWeight = flipWeight(e.weight);
+        graph->addEdge(from, to, {e.weight, e.aliasedExternal},
+                       {flippedWeight, e.aliasedExternal});
+      }
+    }
+  }
+
+  return true;
+}
+
+static Optional<StratifiedSets<Value *>>
+buildSetsFrom(CFLAliasAnalysis *analysis, Function *fn) {
+  NodeMap map;
+  Graph graph;
+
+  bool ok = buildGraphFrom(analysis, fn, &map, &graph);
+  if (!ok) {
+    return NoneType();
+  }
+
+  DenseMap<Graph::Node, Value *> nodeValueMap;
+  // nodeValueMap.resize(map.size());
+  for (const auto &pair : map) {
+    nodeValueMap.insert({pair.second, pair.first});
+  }
+
+  const auto findValueOrDie = [&nodeValueMap](Graph::Node node) {
+    auto valIter = nodeValueMap.find(node);
+    assert(valIter != nodeValueMap.end());
+    return valIter->second;
+  };
+
+  StratifiedSetsBuilder<Value *> builder;
+
+  std::vector<Graph::Node> worklist;
+  for (auto &pair : map) {
+    worklist.clear();
+
+    auto *value = pair.first;
+    builder.add(value);
+    auto initialNode = pair.second;
+    worklist.push_back(initialNode);
+
+    while (!worklist.empty()) {
+      auto node = worklist.back();
+      worklist.pop_back();
+
+      auto *curValue = findValueOrDie(node);
+      if (isa<Constant>(curValue) && !isAliasingExternal(curValue)) {
+        continue;
+      }
+      for (const auto &edgeTuple : graph.edgesFor(node)) {
+        auto weight = std::get<0>(edgeTuple);
+        auto edgeWeight = weight.first;
+        auto &otherNode = std::get<1>(edgeTuple);
+        auto *otherValue = findValueOrDie(otherNode);
+
+        if (isa<Constant>(otherValue) && !isAliasingExternal(otherValue)) {
+          continue;
+        }
+
+        bool added;
+        switch (directionOfEdgeWeight(edgeWeight)) {
+        case Direction::Above:
+          added = builder.addAbove(curValue, otherValue);
+          break;
+        case Direction::Below:
+          added = builder.addBelow(curValue, otherValue);
+          break;
+        case Direction::None:
+          added = builder.addWith(curValue, otherValue);
+          break;
+        }
+
+        if (added) {
+          auto aliasing = weight.second;
+          if (aliasing || isAliasingExternal(otherValue)) {
+            builder.noteHasAliasingExternal(curValue);
+            builder.noteHasAliasingExternal(otherValue);
+          }
+          worklist.push_back(otherNode);
+        }
+      }
+    }
+  }
+
+  return builder.build();
+}
+
+//===----------------------------------------------------------------------===//
+// Lengthy CFL AA methods
+//===----------------------------------------------------------------------===//
+void CFLAliasAnalysis::scan(Function *fn) {
+  auto dummyPair = cache.insert({fn, Optional<StratifiedSets<Value *>>()});
+  (void)dummyPair;
+  assert(dummyPair.second);
+
+  Optional<StratifiedSets<Value *>> maybeInfo(buildSetsFrom(this, fn));
+  // Give it a value to distinguish between "finished building -- nothing was
+  // there" and "in the process of building"
+  if (!maybeInfo.hasValue()) {
+    maybeInfo = StratifiedSets<Value *>();
+  }
+  assert(maybeInfo.hasValue());
+
+  // Note: buildSetsFrom *can* cause a resize on cache, invalidating all
+  // iterators. So we can't use the iterator given above.
+  cache[fn] = std::move(*maybeInfo);
+}
+
+Optional<AliasAnalysis::AliasResult>
+CFLAliasAnalysis::query(const AliasAnalysis::Location &locA,
+                        const AliasAnalysis::Location &locB) {
+  auto *valA = const_cast<Value *>(locA.Ptr);
+  auto *valB = const_cast<Value *>(locB.Ptr);
+
+  Function *fn = nullptr;
+  auto maybeFnA = valueToFunction(valA);
+  auto maybeFnB = valueToFunction(valB);
+  if (!maybeFnA.hasValue() && !maybeFnB.hasValue()) {
+    llvm_unreachable("Can't find Funcation A or Function B");
+  }
+
+  if (maybeFnA.hasValue()) {
+    fn = *maybeFnA;
+    // Ensure we're looking at the same function for both variables.
+    assert(!maybeFnB.hasValue() || *maybeFnB == *maybeFnA);
+  } else {
+    fn = *maybeFnB;
+  }
+
+  assert(fn != nullptr);
+  auto &maybeInfo = ensureCached(fn);
+  assert(maybeInfo.hasValue());
+
+  auto &sets = *maybeInfo;
+  auto maybeA = sets.find(valA);
+  if (!maybeA.hasValue()) {
+    return NoneType();
+  }
+
+  auto maybeB = sets.find(valB);
+  if (!maybeB.hasValue()) {
+    return NoneType();
+  }
+
+  auto setA = *maybeA;
+  auto setB = *maybeB;
+
+  bool sameIndex = setA.index == setB.index;
+  bool bothExternals = sets.hasAliasingExternal(setA.index) &&
+                       sets.hasAliasingExternal(setB.index);
+
+  if (sameIndex || bothExternals) {
+    return PartialAlias;
+  }
+
+  return NoAlias;
+}
+
Index: lib/Analysis/CMakeLists.txt
===================================================================
--- lib/Analysis/CMakeLists.txt
+++ lib/Analysis/CMakeLists.txt
@@ -12,6 +12,7 @@
   CFG.cpp
   CFGPrinter.cpp
   CGSCCPassManager.cpp
+  CFLAliasAnalysis.cpp
   CaptureTracking.cpp
   CostModel.cpp
   CodeMetrics.cpp