[CFLAA] Split into Anders+Steens analysis.

StratifiedSets (as implemented) is very fast, but its accuracy is also
limited. If we take a more aggressive andersens-like approach, we can be
way more accurate, but we'll also end up being slower.

So, we've decided to split CFLAA into CFLSteensAA and CFLAndersAA.

Long-term, we want to end up in a place where CFLSteens is queried
first; if it can provide an answer, great (since queries are basically
map lookups). Otherwise, we'll fall back to CFLAnders, BasicAA, etc.

This patch splits everything out so we can try to do something like
that when we get a reasonable CFLAnders implementation.

Patch by Jia Chen.

Differential Revision: http://reviews.llvm.org/D21910

llvm-svn: 274589

9 files changed, 198 insertions, 73 deletions

diff --git a/llvm/lib/Analysis/AliasAnalysis.cpp b/llvm/lib/Analysis/AliasAnalysis.cpp
index a9d4610ed67..643e9da1db1 100644
--- a/llvm/lib/Analysis/AliasAnalysis.cpp
+++ b/llvm/lib/Analysis/AliasAnalysis.cpp
@@ -27,7 +27,8 @@
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/BasicAliasAnalysis.h"
 #include "llvm/Analysis/CFG.h"
-#include "llvm/Analysis/CFLAliasAnalysis.h"
+#include "llvm/Analysis/CFLAndersAliasAnalysis.h"
+#include "llvm/Analysis/CFLSteensAliasAnalysis.h"
 #include "llvm/Analysis/CaptureTracking.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/ObjCARCAliasAnalysis.h"
@@ -552,7 +553,8 @@ char AAResultsWrapperPass::ID = 0;
 INITIALIZE_PASS_BEGIN(AAResultsWrapperPass, "aa",
                       "Function Alias Analysis Results", false, true)
 INITIALIZE_PASS_DEPENDENCY(BasicAAWrapperPass)
-INITIALIZE_PASS_DEPENDENCY(CFLAAWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(CFLAndersAAWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(CFLSteensAAWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(ExternalAAWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(ObjCARCAAWrapperPass)
@@ -603,7 +605,9 @@ bool AAResultsWrapperPass::runOnFunction(Function &F) {
     AAR->addAAResult(WrapperPass->getResult());
   if (auto *WrapperPass = getAnalysisIfAvailable<SCEVAAWrapperPass>())
     AAR->addAAResult(WrapperPass->getResult());
-  if (auto *WrapperPass = getAnalysisIfAvailable<CFLAAWrapperPass>())
+  if (auto *WrapperPass = getAnalysisIfAvailable<CFLAndersAAWrapperPass>())
+    AAR->addAAResult(WrapperPass->getResult());
+  if (auto *WrapperPass = getAnalysisIfAvailable<CFLSteensAAWrapperPass>())
     AAR->addAAResult(WrapperPass->getResult());
 
   // If available, run an external AA providing callback over the results as
@@ -630,7 +634,8 @@ void AAResultsWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.addUsedIfAvailable<objcarc::ObjCARCAAWrapperPass>();
   AU.addUsedIfAvailable<GlobalsAAWrapperPass>();
   AU.addUsedIfAvailable<SCEVAAWrapperPass>();
-  AU.addUsedIfAvailable<CFLAAWrapperPass>();
+  AU.addUsedIfAvailable<CFLAndersAAWrapperPass>();
+  AU.addUsedIfAvailable<CFLSteensAAWrapperPass>();
 }
 
 AAResults llvm::createLegacyPMAAResults(Pass &P, Function &F,
@@ -652,7 +657,9 @@ AAResults llvm::createLegacyPMAAResults(Pass &P, Function &F,
     AAR.addAAResult(WrapperPass->getResult());
   if (auto *WrapperPass = P.getAnalysisIfAvailable<GlobalsAAWrapperPass>())
     AAR.addAAResult(WrapperPass->getResult());
-  if (auto *WrapperPass = P.getAnalysisIfAvailable<CFLAAWrapperPass>())
+  if (auto *WrapperPass = P.getAnalysisIfAvailable<CFLAndersAAWrapperPass>())
+    AAR.addAAResult(WrapperPass->getResult());
+  if (auto *WrapperPass = P.getAnalysisIfAvailable<CFLSteensAAWrapperPass>())
     AAR.addAAResult(WrapperPass->getResult());
 
   return AAR;
@@ -695,5 +702,6 @@ void llvm::getAAResultsAnalysisUsage(AnalysisUsage &AU) {
   AU.addUsedIfAvailable<TypeBasedAAWrapperPass>();
   AU.addUsedIfAvailable<objcarc::ObjCARCAAWrapperPass>();
   AU.addUsedIfAvailable<GlobalsAAWrapperPass>();
-  AU.addUsedIfAvailable<CFLAAWrapperPass>();
+  AU.addUsedIfAvailable<CFLAndersAAWrapperPass>();
+  AU.addUsedIfAvailable<CFLSteensAAWrapperPass>();
 }
diff --git a/llvm/lib/Analysis/Analysis.cpp b/llvm/lib/Analysis/Analysis.cpp
index aba3c7dbde2..099ac15245c 100644
--- a/llvm/lib/Analysis/Analysis.cpp
+++ b/llvm/lib/Analysis/Analysis.cpp
@@ -34,7 +34,8 @@ void llvm::initializeAnalysis(PassRegistry &Registry) {
   initializeCFGPrinterPass(Registry);
   initializeCFGOnlyViewerPass(Registry);
   initializeCFGOnlyPrinterPass(Registry);
-  initializeCFLAAWrapperPassPass(Registry);
+  initializeCFLAndersAAWrapperPassPass(Registry);
+  initializeCFLSteensAAWrapperPassPass(Registry);
   initializeDependenceAnalysisWrapperPassPass(Registry);
   initializeDelinearizationPass(Registry);
   initializeDemandedBitsWrapperPassPass(Registry);
diff --git a/llvm/lib/Analysis/CFLAndersAliasAnalysis.cpp b/llvm/lib/Analysis/CFLAndersAliasAnalysis.cpp
new file mode 100644
index 00000000000..8db2051d673
--- /dev/null
+++ b/llvm/lib/Analysis/CFLAndersAliasAnalysis.cpp
@@ -0,0 +1,58 @@
+//- CFLAndersAliasAnalysis.cpp - Unification-based Alias Analysis ---*- C++-*-//
+//
+//                     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, summary-based alias analysis algorithm. It
+// differs from CFLSteensAliasAnalysis in its inclusion-based nature while
+// CFLSteensAliasAnalysis is unification-based. This pass has worse performance
+// than CFLSteensAliasAnalysis (the worst case complexity of
+// CFLAndersAliasAnalysis is cubic, while the worst case complexity of
+// CFLSteensAliasAnalysis is almost linear), but it is able to yield more
+// precise analysis result. The precision of this analysis is roughly the same
+// as that of an one level context-sensitive Andersen's algorithm.
+//
+//===----------------------------------------------------------------------===//
+
+// N.B. AliasAnalysis as a whole is phrased as a FunctionPass at the moment, and
+// CFLAndersAA 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.
+
+#include "llvm/Analysis/CFLAndersAliasAnalysis.h"
+#include "llvm/Pass.h"
+
+using namespace llvm;
+
+#define DEBUG_TYPE "cfl-anders-aa"
+
+CFLAndersAAResult::CFLAndersAAResult() = default;
+
+char CFLAndersAA::PassID;
+
+CFLAndersAAResult CFLAndersAA::run(Function &F, AnalysisManager<Function> &AM) {
+  return CFLAndersAAResult();
+}
+
+char CFLAndersAAWrapperPass::ID = 0;
+INITIALIZE_PASS(CFLAndersAAWrapperPass, "cfl-anders-aa",
+                "Inclusion-Based CFL Alias Analysis", false, true)
+
+ImmutablePass *llvm::createCFLAndersAAWrapperPass() {
+  return new CFLAndersAAWrapperPass();
+}
+
+CFLAndersAAWrapperPass::CFLAndersAAWrapperPass() : ImmutablePass(ID) {
+  initializeCFLAndersAAWrapperPassPass(*PassRegistry::getPassRegistry());
+}
+
+void CFLAndersAAWrapperPass::initializePass() {}
+
+void CFLAndersAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
+  AU.setPreservesAll();
+}
diff --git a/llvm/lib/Analysis/CFLAliasAnalysis.cpp b/llvm/lib/Analysis/CFLSteensAliasAnalysis.cpp
index b480fc01340..7da2cf22f40 100644
--- a/llvm/lib/Analysis/CFLAliasAnalysis.cpp
+++ b/llvm/lib/Analysis/CFLSteensAliasAnalysis.cpp
@@ -1,4 +1,4 @@
-//===- CFLAliasAnalysis.cpp - CFL-Based Alias Analysis Implementation ------==//
+//- CFLSteensAliasAnalysis.cpp - Unification-based Alias Analysis ---*- C++-*-//
 //
 //                     The LLVM Compiler Infrastructure
 //
@@ -7,14 +7,16 @@
 //
 //===----------------------------------------------------------------------===//
 //
-// 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, or Assign.
+// This file implements a CFL-base, summary-based 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, or Assign. The precision of this
+// analysis is roughly the same as that of an one level context-sensitive
+// Steensgaard's algorithm.
 //
 // 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
@@ -28,12 +30,12 @@
 //===----------------------------------------------------------------------===//
 
 // N.B. AliasAnalysis as a whole is phrased as a FunctionPass at the moment, and
-// CFLAA is interprocedural. This is *technically* A Bad Thing, because
+// CFLSteensAA 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.
 
-#include "llvm/Analysis/CFLAliasAnalysis.h"
+#include "llvm/Analysis/CFLSteensAliasAnalysis.h"
 #include "StratifiedSets.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/None.h"
@@ -56,13 +58,13 @@
 
 using namespace llvm;
 
-#define DEBUG_TYPE "cfl-aa"
+#define DEBUG_TYPE "cfl-steens-aa"
 
-CFLAAResult::CFLAAResult(const TargetLibraryInfo &TLI)
+CFLSteensAAResult::CFLSteensAAResult(const TargetLibraryInfo &TLI)
     : AAResultBase(), TLI(TLI) {}
-CFLAAResult::CFLAAResult(CFLAAResult &&Arg)
+CFLSteensAAResult::CFLSteensAAResult(CFLSteensAAResult &&Arg)
     : AAResultBase(std::move(Arg)), TLI(Arg.TLI) {}
-CFLAAResult::~CFLAAResult() {}
+CFLSteensAAResult::~CFLSteensAAResult() {}
 
 /// We use InterfaceValue to describe parameters/return value, as well as
 /// potential memory locations that are pointed to by parameters/return value,
@@ -98,7 +100,7 @@ struct ExternalAttribute {
 };
 
 /// Information we have about a function and would like to keep around.
-class CFLAAResult::FunctionInfo {
+class CFLSteensAAResult::FunctionInfo {
   StratifiedSets<Value *> Sets;
 
   // RetParamRelations is a collection of ExternalRelations.
@@ -300,7 +302,7 @@ struct InterprocAttr {
 
 /// Gets the edges our graph should have, based on an Instruction*
 class GetEdgesVisitor : public InstVisitor<GetEdgesVisitor, void> {
-  CFLAAResult &AA;
+  CFLSteensAAResult &AA;
   const TargetLibraryInfo &TLI;
 
   CFLGraph &Graph;
@@ -343,7 +345,7 @@ class GetEdgesVisitor : public InstVisitor<GetEdgesVisitor, void> {
   }
 
 public:
-  GetEdgesVisitor(CFLAAResult &AA, const TargetLibraryInfo &TLI,
+  GetEdgesVisitor(CFLSteensAAResult &AA, const TargetLibraryInfo &TLI,
                   CFLGraph &Graph, SmallVectorImpl<Value *> &ReturnValues,
                   SmallPtrSetImpl<Value *> &Externals,
                   SmallPtrSetImpl<Value *> &Escapes,
@@ -603,7 +605,7 @@ public:
 
 class CFLGraphBuilder {
   // Input of the builder
-  CFLAAResult &Analysis;
+  CFLSteensAAResult &Analysis;
   const TargetLibraryInfo &TLI;
 
   // Output of the builder
@@ -662,7 +664,7 @@ class CFLGraphBuilder {
   }
 
 public:
-  CFLGraphBuilder(CFLAAResult &Analysis, const TargetLibraryInfo &TLI,
+  CFLGraphBuilder(CFLSteensAAResult &Analysis, const TargetLibraryInfo &TLI,
                   Function &Fn)
       : Analysis(Analysis), TLI(TLI) {
     buildGraphFrom(Fn);
@@ -800,9 +802,9 @@ static bool canSkipAddingToSets(Value *Val) {
   return false;
 }
 
-CFLAAResult::FunctionInfo::FunctionInfo(Function &Fn,
-                                        const SmallVectorImpl<Value *> &RetVals,
-                                        StratifiedSets<Value *> S)
+CFLSteensAAResult::FunctionInfo::FunctionInfo(
+    Function &Fn, const SmallVectorImpl<Value *> &RetVals,
+    StratifiedSets<Value *> S)
     : Sets(std::move(S)) {
   // Historically, an arbitrary upper-bound of 50 args was selected. We may want
   // to remove this if it doesn't really matter in practice.
@@ -868,7 +870,7 @@ CFLAAResult::FunctionInfo::FunctionInfo(Function &Fn,
 }
 
 // Builds the graph + StratifiedSets for a function.
-CFLAAResult::FunctionInfo CFLAAResult::buildSetsFrom(Function *Fn) {
+CFLSteensAAResult::FunctionInfo CFLSteensAAResult::buildSetsFrom(Function *Fn) {
   CFLGraphBuilder GraphBuilder(*this, TLI, *Fn);
   StratifiedSetsBuilder<Value *> SetBuilder;
 
@@ -951,7 +953,7 @@ CFLAAResult::FunctionInfo CFLAAResult::buildSetsFrom(Function *Fn) {
   return FunctionInfo(*Fn, GraphBuilder.getReturnValues(), SetBuilder.build());
 }
 
-void CFLAAResult::scan(Function *Fn) {
+void CFLSteensAAResult::scan(Function *Fn) {
   auto InsertPair = Cache.insert(std::make_pair(Fn, Optional<FunctionInfo>()));
   (void)InsertPair;
   assert(InsertPair.second &&
@@ -966,12 +968,12 @@ void CFLAAResult::scan(Function *Fn) {
   Handles.push_front(FunctionHandle(Fn, this));
 }
 
-void CFLAAResult::evict(Function *Fn) { Cache.erase(Fn); }
+void CFLSteensAAResult::evict(Function *Fn) { Cache.erase(Fn); }
 
 /// Ensures that the given function is available in the cache, and returns the
 /// entry.
-const Optional<CFLAAResult::FunctionInfo> &
-CFLAAResult::ensureCached(Function *Fn) {
+const Optional<CFLSteensAAResult::FunctionInfo> &
+CFLSteensAAResult::ensureCached(Function *Fn) {
   auto Iter = Cache.find(Fn);
   if (Iter == Cache.end()) {
     scan(Fn);
@@ -982,8 +984,8 @@ CFLAAResult::ensureCached(Function *Fn) {
   return Iter->second;
 }
 
-AliasResult CFLAAResult::query(const MemoryLocation &LocA,
-                               const MemoryLocation &LocB) {
+AliasResult CFLSteensAAResult::query(const MemoryLocation &LocA,
+                                     const MemoryLocation &LocB) {
   auto *ValA = const_cast<Value *>(LocA.Ptr);
   auto *ValB = const_cast<Value *>(LocB.Ptr);
 
@@ -996,7 +998,8 @@ AliasResult CFLAAResult::query(const MemoryLocation &LocA,
   if (!MaybeFnA.hasValue() && !MaybeFnB.hasValue()) {
     // The only times this is known to happen are when globals + InlineAsm are
     // involved
-    DEBUG(dbgs() << "CFLAA: could not extract parent function information.\n");
+    DEBUG(dbgs()
+          << "CFLSteensAA: could not extract parent function information.\n");
     return MayAlias;
   }
 
@@ -1027,8 +1030,8 @@ AliasResult CFLAAResult::query(const MemoryLocation &LocA,
   auto AttrsB = Sets.getLink(SetB.Index).Attrs;
 
   // If both values are local (meaning the corresponding set has attribute
-  // AttrNone or AttrEscaped), then we know that CFLAA fully models them: they
-  // may-alias each other if and only if they are in the same set
+  // AttrNone or AttrEscaped), then we know that CFLSteensAA fully models them:
+  // they may-alias each other if and only if they are in the same set.
   // If at least one value is non-local (meaning it either is global/argument or
   // it comes from unknown sources like integer cast), the situation becomes a
   // bit more interesting. We follow three general rules described below:
@@ -1047,8 +1050,8 @@ AliasResult CFLAAResult::query(const MemoryLocation &LocA,
   return NoAlias;
 }
 
-ModRefInfo CFLAAResult::getArgModRefInfo(ImmutableCallSite CS,
-                                         unsigned ArgIdx) {
+ModRefInfo CFLSteensAAResult::getArgModRefInfo(ImmutableCallSite CS,
+                                               unsigned ArgIdx) {
   if (auto CalledFunc = CS.getCalledFunction()) {
     auto &MaybeInfo = ensureCached(const_cast<Function *>(CalledFunc));
     if (!MaybeInfo.hasValue())
@@ -1075,7 +1078,8 @@ ModRefInfo CFLAAResult::getArgModRefInfo(ImmutableCallSite CS,
   return MRI_ModRef;
 }
 
-FunctionModRefBehavior CFLAAResult::getModRefBehavior(ImmutableCallSite CS) {
+FunctionModRefBehavior
+CFLSteensAAResult::getModRefBehavior(ImmutableCallSite CS) {
   // If we know the callee, try analyzing it
   if (auto CalledFunc = CS.getCalledFunction())
     return getModRefBehavior(CalledFunc);
@@ -1084,7 +1088,7 @@ FunctionModRefBehavior CFLAAResult::getModRefBehavior(ImmutableCallSite CS) {
   return FMRB_UnknownModRefBehavior;
 }
 
-FunctionModRefBehavior CFLAAResult::getModRefBehavior(const Function *F) {
+FunctionModRefBehavior CFLSteensAAResult::getModRefBehavior(const Function *F) {
   assert(F != nullptr);
 
   // TODO: Remove the const_cast
@@ -1118,28 +1122,30 @@ FunctionModRefBehavior CFLAAResult::getModRefBehavior(const Function *F) {
                              : FMRB_UnknownModRefBehavior;
 }
 
-char CFLAA::PassID;
+char CFLSteensAA::PassID;
 
-CFLAAResult CFLAA::run(Function &F, AnalysisManager<Function> &AM) {
-  return CFLAAResult(AM.getResult<TargetLibraryAnalysis>(F));
+CFLSteensAAResult CFLSteensAA::run(Function &F, AnalysisManager<Function> &AM) {
+  return CFLSteensAAResult(AM.getResult<TargetLibraryAnalysis>(F));
 }
 
-char CFLAAWrapperPass::ID = 0;
-INITIALIZE_PASS(CFLAAWrapperPass, "cfl-aa", "CFL-Based Alias Analysis", false,
-                true)
+char CFLSteensAAWrapperPass::ID = 0;
+INITIALIZE_PASS(CFLSteensAAWrapperPass, "cfl-steens-aa",
+                "Unification-Based CFL Alias Analysis", false, true)
 
-ImmutablePass *llvm::createCFLAAWrapperPass() { return new CFLAAWrapperPass(); }
+ImmutablePass *llvm::createCFLSteensAAWrapperPass() {
+  return new CFLSteensAAWrapperPass();
+}
 
-CFLAAWrapperPass::CFLAAWrapperPass() : ImmutablePass(ID) {
-  initializeCFLAAWrapperPassPass(*PassRegistry::getPassRegistry());
+CFLSteensAAWrapperPass::CFLSteensAAWrapperPass() : ImmutablePass(ID) {
+  initializeCFLSteensAAWrapperPassPass(*PassRegistry::getPassRegistry());
 }
 
-void CFLAAWrapperPass::initializePass() {
+void CFLSteensAAWrapperPass::initializePass() {
   auto &TLIWP = getAnalysis<TargetLibraryInfoWrapperPass>();
-  Result.reset(new CFLAAResult(TLIWP.getTLI()));
+  Result.reset(new CFLSteensAAResult(TLIWP.getTLI()));
 }
 
-void CFLAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
+void CFLSteensAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.setPreservesAll();
   AU.addRequired<TargetLibraryInfoWrapperPass>();
 }
diff --git a/llvm/lib/Analysis/CMakeLists.txt b/llvm/lib/Analysis/CMakeLists.txt
index 56ab9a0b384..79b164cf646 100644
--- a/llvm/lib/Analysis/CMakeLists.txt
+++ b/llvm/lib/Analysis/CMakeLists.txt
@@ -10,7 +10,8 @@ add_llvm_library(LLVMAnalysis
   BranchProbabilityInfo.cpp
   CFG.cpp
   CFGPrinter.cpp
-  CFLAliasAnalysis.cpp
+  CFLAndersAliasAnalysis.cpp
+  CFLSteensAliasAnalysis.cpp
   CGSCCPassManager.cpp
   CallGraph.cpp
   CallGraphSCCPass.cpp
diff --git a/llvm/lib/CodeGen/TargetPassConfig.cpp b/llvm/lib/CodeGen/TargetPassConfig.cpp
index 1b30cc8ee54..332a8b7e323 100644
--- a/llvm/lib/CodeGen/TargetPassConfig.cpp
+++ b/llvm/lib/CodeGen/TargetPassConfig.cpp
@@ -15,7 +15,8 @@
 #include "llvm/CodeGen/TargetPassConfig.h"
 
 #include "llvm/Analysis/BasicAliasAnalysis.h"
-#include "llvm/Analysis/CFLAliasAnalysis.h"
+#include "llvm/Analysis/CFLAndersAliasAnalysis.h"
+#include "llvm/Analysis/CFLSteensAliasAnalysis.h"
 #include "llvm/Analysis/CallGraphSCCPass.h"
 #include "llvm/Analysis/Passes.h"
 #include "llvm/Analysis/ScopedNoAliasAA.h"
@@ -110,9 +111,19 @@ cl::opt<bool> MISchedPostRA("misched-postra", cl::Hidden,
 static cl::opt<bool> EarlyLiveIntervals("early-live-intervals", cl::Hidden,
     cl::desc("Run live interval analysis earlier in the pipeline"));
 
-static cl::opt<bool> UseCFLAA("use-cfl-aa-in-codegen",
-  cl::init(false), cl::Hidden,
-  cl::desc("Enable the new, experimental CFL alias analysis in CodeGen"));
+// Experimental option to use CFL-AA in codegen
+enum class CFLAAType { None, Steensgaard, Andersen, Both };
+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"),
+               clEnumValEnd));
 
 cl::opt<bool> UseIPRA("enable-ipra", cl::init(false), cl::Hidden,
                       cl::desc("Enable interprocedural register allocation "
@@ -414,12 +425,25 @@ void TargetPassConfig::addVerifyPass(const std::string &Banner) {
 /// Add common target configurable passes that perform LLVM IR to IR transforms
 /// following machine independent optimization.
 void TargetPassConfig::addIRPasses() {
+  switch (UseCFLAA) {
+  case CFLAAType::Steensgaard:
+    addPass(createCFLSteensAAWrapperPass());
+    break;
+  case CFLAAType::Andersen:
+    addPass(createCFLAndersAAWrapperPass());
+    break;
+  case CFLAAType::Both:
+    addPass(createCFLAndersAAWrapperPass());
+    addPass(createCFLSteensAAWrapperPass());
+    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.
-  if (UseCFLAA)
-    addPass(createCFLAAWrapperPass());
   addPass(createTypeBasedAAWrapperPass());
   addPass(createScopedNoAliasAAWrapperPass());
   addPass(createBasicAAWrapperPass());
diff --git a/llvm/lib/Passes/PassBuilder.cpp b/llvm/lib/Passes/PassBuilder.cpp
index fe9e4cffcbd..5ebe98361d0 100644
--- a/llvm/lib/Passes/PassBuilder.cpp
+++ b/llvm/lib/Passes/PassBuilder.cpp
@@ -24,7 +24,8 @@
 #include "llvm/Analysis/BlockFrequencyInfo.h"
 #include "llvm/Analysis/BlockFrequencyInfoImpl.h"
 #include "llvm/Analysis/BranchProbabilityInfo.h"
-#include "llvm/Analysis/CFLAliasAnalysis.h"
+#include "llvm/Analysis/CFLAndersAliasAnalysis.h"
+#include "llvm/Analysis/CFLSteensAliasAnalysis.h"
 #include "llvm/Analysis/CGSCCPassManager.h"
 #include "llvm/Analysis/CallGraph.h"
 #include "llvm/Analysis/DemandedBits.h"
@@ -692,7 +693,8 @@ bool PassBuilder::parsePassPipeline(ModulePassManager &MPM,
                                 DebugLogging) ||
         !PipelineText.empty())
       return false;
-    MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM), DebugLogging));
+    MPM.addPass(
+        createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM), DebugLogging));
     return true;
   }
 
diff --git a/llvm/lib/Passes/PassRegistry.def b/llvm/lib/Passes/PassRegistry.def
index b1c9d6d815e..9190844951b 100644
--- a/llvm/lib/Passes/PassRegistry.def
+++ b/llvm/lib/Passes/PassRegistry.def
@@ -27,7 +27,7 @@ MODULE_ANALYSIS("targetlibinfo", TargetLibraryAnalysis())
 MODULE_ANALYSIS("verify", VerifierAnalysis())
 
 #ifndef MODULE_ALIAS_ANALYSIS
-#define MODULE_ALIAS_ANALYSIS(NAME, CREATE_PASS)                             \
+#define MODULE_ALIAS_ANALYSIS(NAME, CREATE_PASS)                               \
   MODULE_ANALYSIS(NAME, CREATE_PASS)
 #endif
 MODULE_ALIAS_ANALYSIS("globals-aa", GlobalsAA())
@@ -110,7 +110,8 @@ FUNCTION_ANALYSIS("verify", VerifierAnalysis())
   FUNCTION_ANALYSIS(NAME, CREATE_PASS)
 #endif
 FUNCTION_ALIAS_ANALYSIS("basic-aa", BasicAA())
-FUNCTION_ALIAS_ANALYSIS("cfl-aa", CFLAA())
+FUNCTION_ALIAS_ANALYSIS("cfl-anders-aa", CFLAndersAA())
+FUNCTION_ALIAS_ANALYSIS("cfl-steens-aa", CFLSteensAA())
 FUNCTION_ALIAS_ANALYSIS("scev-aa", SCEVAA())
 FUNCTION_ALIAS_ANALYSIS("scoped-noalias-aa", ScopedNoAliasAA())
 FUNCTION_ALIAS_ANALYSIS("type-based-aa", TypeBasedAA())
diff --git a/llvm/lib/Transforms/IPO/PassManagerBuilder.cpp b/llvm/lib/Transforms/IPO/PassManagerBuilder.cpp
index 2a209b34ccf..e283d26f5c1 100644
--- a/llvm/lib/Transforms/IPO/PassManagerBuilder.cpp
+++ b/llvm/lib/Transforms/IPO/PassManagerBuilder.cpp
@@ -16,7 +16,8 @@
 #include "llvm-c/Transforms/PassManagerBuilder.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/Analysis/BasicAliasAnalysis.h"
-#include "llvm/Analysis/CFLAliasAnalysis.h"
+#include "llvm/Analysis/CFLAndersAliasAnalysis.h"
+#include "llvm/Analysis/CFLSteensAliasAnalysis.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/Passes.h"
 #include "llvm/Analysis/ScopedNoAliasAA.h"
@@ -79,9 +80,19 @@ RunSLPAfterLoopVectorization("run-slp-after-loop-vectorization",
   cl::desc("Run the SLP vectorizer (and BB vectorizer) after the Loop "
            "vectorizer instead of before"));
 
-static cl::opt<bool> UseCFLAA("use-cfl-aa",
-  cl::init(false), cl::Hidden,
-  cl::desc("Enable the new, experimental CFL alias analysis"));
+// Experimental option to use CFL-AA
+enum class CFLAAType { None, Steensgaard, Andersen, Both };
+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"),
+                        clEnumValEnd));
 
 static cl::opt<bool>
 EnableMLSM("mlsm", cl::init(true), cl::Hidden,
@@ -169,11 +180,24 @@ void PassManagerBuilder::addExtensionsToPM(ExtensionPointTy ETy,
 
 void PassManagerBuilder::addInitialAliasAnalysisPasses(
     legacy::PassManagerBase &PM) const {
+  switch (UseCFLAA) {
+  case CFLAAType::Steensgaard:
+    PM.add(createCFLSteensAAWrapperPass());
+    break;
+  case CFLAAType::Andersen:
+    PM.add(createCFLAndersAAWrapperPass());
+    break;
+  case CFLAAType::Both:
+    PM.add(createCFLSteensAAWrapperPass());
+    PM.add(createCFLAndersAAWrapperPass());
+    break;
+  default:
+    break;
+  }
+
   // Add TypeBasedAliasAnalysis before BasicAliasAnalysis so that
   // BasicAliasAnalysis wins if they disagree. This is intended to help
   // support "obvious" type-punning idioms.
-  if (UseCFLAA)
-    PM.add(createCFLAAWrapperPass());
   PM.add(createTypeBasedAAWrapperPass());
   PM.add(createScopedNoAliasAAWrapperPass());
 }