[CFLAA] Split CFL-AA into one unification-based pass and one inclusion-based pass

[grievejia]

Summary

This patch renames the existing CFLAliasAnalysis pass to CFLSteensAliasAnalysis, and introduces a new pass CFLAndersAliasAnalysis. The pass name "cfl-aa" gets replaced by "cfl-steens-aa" and "cfl-anders-aa". The "use-cfl-aa" and "use-cfl-aa-in-codegen" flags gets changed from a boolean flags to enum flags (none/steens/anders).

Precision enhancements are getting more and more difficult to add to the existing CFLAliasAnalysis pass due to its unification-based nature. Since extending CFL-AA with features like field sensitivity and inclusion-based semantics won't share too much of the existing codes anyway, it's much cleaner to start anew (and perhaps factor out certain parts of the original codes that can be shared by all CFL-based alias analysis) than to keep increasing the code complexity in CFLAliasAnalysis.cpp.

The newly added pass contains only a stub implementation of alias() currently. Its body will be gradually filled out in subsequent patches.

[• dberlin]

Given you basically want to reuse the graph, you should refactor that out
too.

The only difference between the steens and inclusion based ones should be
how they walk the graph and what preprocessing they do, if any.

(This also lets you layer them without having to rebuild the entire graph.

As we discussed offline, in a perfect world, you want to do something like
quickly ask the steens if they are no-alias. If it says "no-alias", you
return that, otherwise, you do inclusion based walking)

[grievejia]

In D21910#471778, @dberlin wrote:

Given you basically want to reuse the graph, you should refactor that out
too.

That's the plan. I've already changed a lot of things here so it may be safer to do that in another patch.

As we discussed offline, in a perfect world, you want to do something like
quickly ask the steens if they are no-alias. If it says "no-alias", you
return that, otherwise, you do inclusion based walking)

Agreed. But for now let's build cfl-anders first before we worry about how to combine it with cfl-steens?

Cfl-anders can be implemented in various ways. We could ahead-compute everything just like what we did in cfl-steens, or like you said we could keep the cfl graph and walk it in a memoized demand-driven fashion. If we did it on-demand, we could also either put the logic that combines cfl-anders and cfl-steens into cfl-anders, or we can offload that task to the aa pass manager. It seems that there are lots of design decision to be made here, and I'm still trying to figure out what the best choice would be...

[george.burgess.iv]

include/llvm/Analysis/CFLAndersAliasAnalysis.h

35 ↗

(On Diff #62426)

Please remove

41 ↗

(On Diff #62426)

Maybe take out "of sets" here, if this won't be using StratifiedSets?

include/llvm/Analysis/CFLSteensAliasAnalysis.h

64 ↗

(On Diff #62426)

Looks like this comment got broken.

lib/Analysis/CFLAndersAliasAnalysis.cpp

1 ↗

(On Diff #62426)

.cpp :)

12 ↗

(On Diff #62426)

I think a number of CFLAndersAliasAnalysis in here should be CFLSteensAliasAnalysis

18 ↗

(On Diff #62426)

please delete, or add //

lib/Analysis/CFLSteensAliasAnalysis.cpp

1 ↗

(On Diff #62426)

.cpp :)

lib/CodeGen/TargetPassConfig.cpp

116 ↗

(On Diff #62426)

So... Is the goal to ultimately only allow one or the other to be run per compilation? Or will we be able to e.g. throw CFLsteens before CFLanders at a later point?

[grievejia]

include/llvm/Analysis/CFLAndersAliasAnalysis.h

41 ↗

(On Diff #62426)

I would imagine that we still need some kinds of set. It won't be StratifiedSets, but it will be other set :)

lib/Analysis/CFLAndersAliasAnalysis.cpp

12 ↗

(On Diff #62426)

Oops, a typical problem caused by blind search-replace...

lib/CodeGen/TargetPassConfig.cpp

116 ↗

(On Diff #62426)

Yeah I agree it would be useful to be able to run cfl-anders and cfl-steens on the same pipeline.

Let me address your concern by adding another enum option "Both".

[grievejia]

Fixed broken comments and added a new option to use both variants of cfl-aa

[george.burgess.iv]

LGTM -- will commit later today. Thanks for the patch!

llvm/trunk/include/llvm/Analysis/CFLAliasAnalysis.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_CFLALIASANALYSIS_H
-#define LLVM_ANALYSIS_CFLALIASANALYSIS_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 TargetLibraryInfo;
-
-class CFLAAResult : public AAResultBase<CFLAAResult> {
-  friend AAResultBase<CFLAAResult>;
-  class FunctionInfo;
-
-public:
-  explicit CFLAAResult(const TargetLibraryInfo &);
-  CFLAAResult(CFLAAResult &&Arg);
-  ~CFLAAResult();
-
-  /// Handle invalidation events from the new pass manager.
-  ///
-  /// By definition, this result is stateless and so remains valid.
-  bool invalidate(Function &, const PreservedAnalyses &) { return false; }
-
-  /// \brief Inserts the given Function into the cache.
-  void scan(Function *Fn);
-
-  void evict(Function *Fn);
-
-  /// \brief Ensures that the given function is available in the cache.
-  /// Returns the appropriate entry from the cache.
-  const Optional<FunctionInfo> &ensureCached(Function *Fn);
-
-  AliasResult query(const MemoryLocation &LocA, const MemoryLocation &LocB);
-
-  AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB) {
-    if (LocA.Ptr == LocB.Ptr)
-      return LocA.Size == LocB.Size ? MustAlias : PartialAlias;
-
-    // Comparisons between global variables and other constants should be
-    // handled by BasicAA.
-    // TODO: ConstantExpr handling -- CFLAA 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;
-  }
-
-  /// Get the location associated with a pointer argument of a callsite.
-  ModRefInfo getArgModRefInfo(ImmutableCallSite CS, unsigned ArgIdx);
-
-  /// Returns the behavior when calling the given call site.
-  FunctionModRefBehavior getModRefBehavior(ImmutableCallSite CS);
-
-  /// Returns the behavior when calling the given function. For use when the
-  /// call site is not known.
-  FunctionModRefBehavior getModRefBehavior(const Function *F);
-
-private:
-  struct FunctionHandle final : public CallbackVH {
-    FunctionHandle(Function *Fn, CFLAAResult *Result)
-        : CallbackVH(Fn), Result(Result) {
-      assert(Fn != nullptr);
-      assert(Result != nullptr);
-    }
-
-    void deleted() override { removeSelfFromCache(); }
-    void allUsesReplacedWith(Value *) override { removeSelfFromCache(); }
-
-  private:
-    CFLAAResult *Result;
-
-    void removeSelfFromCache() {
-      assert(Result != nullptr);
-      auto *Val = getValPtr();
-      Result->evict(cast<Function>(Val));
-      setValPtr(nullptr);
-    }
-  };
-
-  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<Function *, Optional<FunctionInfo>> Cache;
-  std::forward_list<FunctionHandle> Handles;
-
-  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 CFLAA : public AnalysisInfoMixin<CFLAA> {
-  friend AnalysisInfoMixin<CFLAA>;
-  static char PassID;
-
-public:
-  typedef CFLAAResult Result;
-
-  CFLAAResult run(Function &F, AnalysisManager<Function> &AM);
-};
-
-/// Legacy wrapper pass to provide the CFLAAResult object.
-class CFLAAWrapperPass : public ImmutablePass {
-  std::unique_ptr<CFLAAResult> Result;
-
-public:
-  static char ID;
-
-  CFLAAWrapperPass();
-
-  CFLAAResult &getResult() { return *Result; }
-  const CFLAAResult &getResult() const { return *Result; }
-
-  void initializePass() override;
-  void getAnalysisUsage(AnalysisUsage &AU) const override;
-};
-
-//===--------------------------------------------------------------------===//
-//
-// createCFLAAWrapperPass - This pass implements a set-based approach to
-// alias analysis.
-//
-ImmutablePass *createCFLAAWrapperPass();
-}
-
-#endif

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

+//=- CFLAndersAliasAnalysis.h - 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.
+//
+//===----------------------------------------------------------------------===//
+/// \file
+/// This is the interface for LLVM's inclusion-based alias analysis
+/// implemented with CFL graph reachability.
+///
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_CFLANDERSALIASANALYSIS_H
+#define LLVM_ANALYSIS_CFLANDERSALIASANALYSIS_H
+
+#include "llvm/Analysis/AliasAnalysis.h"
+#include "llvm/IR/Function.h"
+#include "llvm/Pass.h"
+
+namespace llvm {
+
+class CFLAndersAAResult : public AAResultBase<CFLAndersAAResult> {
+  friend AAResultBase<CFLAndersAAResult>;
+
+public:
+  explicit CFLAndersAAResult();
+
+  AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB) {
+    // Dummy implementation
+    return AAResultBase::alias(LocA, LocB);
+  }
+};
+
+/// 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.
+class CFLAndersAA : public AnalysisInfoMixin<CFLAndersAA> {
+  friend AnalysisInfoMixin<CFLAndersAA>;
+  static char PassID;
+
+public:
+  typedef CFLAndersAAResult Result;
+
+  CFLAndersAAResult run(Function &F, AnalysisManager<Function> &AM);
+};
+
+/// Legacy wrapper pass to provide the CFLAndersAAResult object.
+class CFLAndersAAWrapperPass : public ImmutablePass {
+  std::unique_ptr<CFLAndersAAResult> Result;
+
+public:
+  static char ID;
+
+  CFLAndersAAWrapperPass();
+
+  CFLAndersAAResult &getResult() { return *Result; }
+  const CFLAndersAAResult &getResult() const { return *Result; }
+
+  void initializePass() override;
+  void getAnalysisUsage(AnalysisUsage &AU) const override;
+};
+
+//===--------------------------------------------------------------------===//
+//
+// createCFLAndersAAWrapperPass - This pass implements a set-based approach to
+// alias analysis.
+//
+ImmutablePass *createCFLAndersAAWrapperPass();
+}
+
+#endif

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

+//=- CFLSteensAliasAnalysis.h - 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.
+//
+//===----------------------------------------------------------------------===//
+/// \file
+/// This is the interface for LLVM's unification-based alias analysis
+/// implemented with CFL graph reachability.
+///
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_CFLSTEENSALIASANALYSIS_H
+#define LLVM_ANALYSIS_CFLSTEENSALIASANALYSIS_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 TargetLibraryInfo;
+
+class CFLSteensAAResult : public AAResultBase<CFLSteensAAResult> {
+  friend AAResultBase<CFLSteensAAResult>;
+  class FunctionInfo;
+
+public:
+  explicit CFLSteensAAResult(const TargetLibraryInfo &);
+  CFLSteensAAResult(CFLSteensAAResult &&Arg);
+  ~CFLSteensAAResult();
+
+  /// Handle invalidation events from the new pass manager.
+  ///
+  /// By definition, this result is stateless and so remains valid.
+  bool invalidate(Function &, const PreservedAnalyses &) { return false; }
+
+  /// \brief Inserts the given Function into the cache.
+  void scan(Function *Fn);
+
+  void evict(Function *Fn);
+
+  /// \brief Ensures that the given function is available in the cache.
+  /// Returns the appropriate entry from the cache.
+  const Optional<FunctionInfo> &ensureCached(Function *Fn);
+
+  AliasResult query(const MemoryLocation &LocA, const MemoryLocation &LocB);
+
+  AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB) {
+    if (LocA.Ptr == LocB.Ptr)
+      return LocA.Size == LocB.Size ? MustAlias : PartialAlias;
+
+    // Comparisons between global variables and other constants should be
+    // handled by BasicAA.
+    // CFLSteensAA 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;
+  }
+
+  /// Get the location associated with a pointer argument of a callsite.
+  ModRefInfo getArgModRefInfo(ImmutableCallSite CS, unsigned ArgIdx);
+
+  /// Returns the behavior when calling the given call site.
+  FunctionModRefBehavior getModRefBehavior(ImmutableCallSite CS);
+
+  /// Returns the behavior when calling the given function. For use when the
+  /// call site is not known.
+  FunctionModRefBehavior getModRefBehavior(const Function *F);
+
+private:
+  struct FunctionHandle final : public CallbackVH {
+    FunctionHandle(Function *Fn, CFLSteensAAResult *Result)
+        : CallbackVH(Fn), Result(Result) {
+      assert(Fn != nullptr);
+      assert(Result != nullptr);
+    }
+
+    void deleted() override { removeSelfFromCache(); }
+    void allUsesReplacedWith(Value *) override { removeSelfFromCache(); }
+
+  private:
+    CFLSteensAAResult *Result;
+
+    void removeSelfFromCache() {
+      assert(Result != nullptr);
+      auto *Val = getValPtr();
+      Result->evict(cast<Function>(Val));
+      setValPtr(nullptr);
+    }
+  };
+
+  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<Function *, Optional<FunctionInfo>> Cache;
+  std::forward_list<FunctionHandle> Handles;
+
+  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 CFLSteensAA : public AnalysisInfoMixin<CFLSteensAA> {
+  friend AnalysisInfoMixin<CFLSteensAA>;
+  static char PassID;
+
+public:
+  typedef CFLSteensAAResult Result;
+
+  CFLSteensAAResult run(Function &F, AnalysisManager<Function> &AM);
+};
+
+/// Legacy wrapper pass to provide the CFLSteensAAResult object.
+class CFLSteensAAWrapperPass : public ImmutablePass {
+  std::unique_ptr<CFLSteensAAResult> Result;
+
+public:
+  static char ID;
+
+  CFLSteensAAWrapperPass();
+
+  CFLSteensAAResult &getResult() { return *Result; }
+  const CFLSteensAAResult &getResult() const { return *Result; }
+
+  void initializePass() override;
+  void getAnalysisUsage(AnalysisUsage &AU) const override;
+};
+
+//===--------------------------------------------------------------------===//
+//
+// createCFLSteensAAWrapperPass - This pass implements a set-based approach to
+// alias analysis.
+//
+ImmutablePass *createCFLSteensAAWrapperPass();
+}
+
+#endif

llvm/trunk/include/llvm/InitializePasses.h

 void initializeBranchFolderPassPass(PassRegistry&);
 void initializeBranchProbabilityInfoWrapperPassPass(PassRegistry&);
 void initializeBreakCriticalEdgesPass(PassRegistry&);
 void initializeCFGOnlyPrinterPass(PassRegistry&);
 void initializeCFGOnlyViewerPass(PassRegistry&);
 void initializeCFGPrinterPass(PassRegistry&);
 void initializeCFGSimplifyPassPass(PassRegistry&);
 void initializeCFGViewerPass(PassRegistry&);
-void initializeCFLAAWrapperPassPass(PassRegistry&);
+void initializeCFLAndersAAWrapperPassPass(PassRegistry&);
+void initializeCFLSteensAAWrapperPassPass(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&);

llvm/trunk/include/llvm/LinkAllPasses.h

 
 #ifndef 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/CFLAliasAnalysis.h"
+#include "llvm/Analysis/CFLAndersAliasAnalysis.h"
+#include "llvm/Analysis/CFLSteensAliasAnalysis.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::createSCEVAAWrapperPass();
       (void) llvm::createTypeBasedAAWrapperPass();
       (void) llvm::createScopedNoAliasAAWrapperPass();
       (void) llvm::createBoundsCheckingPass();
       (void) llvm::createBreakCriticalEdgesPass();
       (void) llvm::createCallGraphDOTPrinterPass();
       (void) llvm::createCallGraphViewerPass();
       (void) llvm::createCFGSimplificationPass();
-      (void) llvm::createCFLAAWrapperPass();
+      (void) llvm::createCFLAndersAAWrapperPass();
+      (void) llvm::createCFLSteensAAWrapperPass();
       (void) llvm::createStructurizeCFGPass();
       (void) llvm::createConstantMergePass();
       (void) llvm::createConstantPropagationPass();
       (void) llvm::createCostModelAnalysisPass();
       (void) llvm::createDeadArgEliminationPass();
       (void) llvm::createDeadCodeEliminationPass();
       (void) llvm::createDeadInstEliminationPass();
       (void) llvm::createDeadStoreEliminationPass();

llvm/trunk/lib/Analysis/AliasAnalysis.cpp

 // implementations may choose to rely on this pass to resolve these simple and
 // easy cases.
 //
 //===----------------------------------------------------------------------===//
 
 #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"
 #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"
AAResultsWrapperPass::AAResultsWrapperPass() : FunctionPass(ID) {
   initializeAAResultsWrapperPassPass(*PassRegistry::getPassRegistry());
 }
 
 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)
 INITIALIZE_PASS_DEPENDENCY(SCEVAAWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(ScopedNoAliasAAWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(TypeBasedAAWrapperPass)
 INITIALIZE_PASS_END(AAResultsWrapperPass, "aa",
                     "Function Alias Analysis Results", false, true)
if (auto *WrapperPass = getAnalysisIfAvailable<TypeBasedAAWrapperPass>())
     AAR->addAAResult(WrapperPass->getResult());
   if (auto *WrapperPass =
           getAnalysisIfAvailable<objcarc::ObjCARCAAWrapperPass>())
     AAR->addAAResult(WrapperPass->getResult());
   if (auto *WrapperPass = getAnalysisIfAvailable<GlobalsAAWrapperPass>())
     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
   // well.
   if (auto *WrapperPass = getAnalysisIfAvailable<ExternalAAWrapperPass>())
     if (WrapperPass->CB)
       WrapperPass->CB(*this, F, *AAR);
 
void AAResultsWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
   // probe in runOnFunction as used here to ensure the legacy pass manager
   // 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<CFLAAWrapperPass>();
+  AU.addUsedIfAvailable<CFLAndersAAWrapperPass>();
+  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 (!DisableBasicAA)
     AAR.addAAResult(BAR);
 
   // Populate the results with the other currently available AAs.
   if (auto *WrapperPass =
           P.getAnalysisIfAvailable<ScopedNoAliasAAWrapperPass>())
     AAR.addAAResult(WrapperPass->getResult());
   if (auto *WrapperPass = P.getAnalysisIfAvailable<TypeBasedAAWrapperPass>())
     AAR.addAAResult(WrapperPass->getResult());
   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<CFLAAWrapperPass>())
+  if (auto *WrapperPass = P.getAnalysisIfAvailable<CFLAndersAAWrapperPass>())
+    AAR.addAAResult(WrapperPass->getResult());
+  if (auto *WrapperPass = P.getAnalysisIfAvailable<CFLSteensAAWrapperPass>())
     AAR.addAAResult(WrapperPass->getResult());
 
   return AAR;
 }
 
 bool llvm::isNoAliasCall(const Value *V) {
   if (auto CS = ImmutableCallSite(V))
     return CS.paramHasAttr(0, Attribute::NoAlias);
void llvm::getAAResultsAnalysisUsage(AnalysisUsage &AU) {
   // This function needs to be in sync with llvm::createLegacyPMAAResults -- if
   // more alias analyses are added to llvm::createLegacyPMAAResults, they need
   // to be added here also.
   AU.addRequired<TargetLibraryInfoWrapperPass>();
   AU.addUsedIfAvailable<ScopedNoAliasAAWrapperPass>();
   AU.addUsedIfAvailable<TypeBasedAAWrapperPass>();
   AU.addUsedIfAvailable<objcarc::ObjCARCAAWrapperPass>();
   AU.addUsedIfAvailable<GlobalsAAWrapperPass>();
-  AU.addUsedIfAvailable<CFLAAWrapperPass>();
+  AU.addUsedIfAvailable<CFLAndersAAWrapperPass>();
+  AU.addUsedIfAvailable<CFLSteensAAWrapperPass>();
 }

llvm/trunk/lib/Analysis/Analysis.cpp

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

llvm/trunk/lib/Analysis/CFLAliasAnalysis.cpp

-//===- 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 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.
-//
-// 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 "Fast algorithms..." (mentioned above)
-// in order to transform the graph into sets of variables that may alias in
-// ~nlogn time (n = number of variables), which makes queries take constant
-// time.
-//===----------------------------------------------------------------------===//
-
-// 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
-// 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 "StratifiedSets.h"
-#include "llvm/ADT/DenseMap.h"
-#include "llvm/ADT/None.h"
-#include "llvm/ADT/Optional.h"
-#include "llvm/Analysis/MemoryBuiltins.h"
-#include "llvm/Analysis/TargetLibraryInfo.h"
-#include "llvm/IR/Constants.h"
-#include "llvm/IR/Function.h"
-#include "llvm/IR/InstVisitor.h"
-#include "llvm/IR/Instructions.h"
-#include "llvm/Pass.h"
-#include "llvm/Support/Compiler.h"
-#include "llvm/Support/Debug.h"
-#include "llvm/Support/ErrorHandling.h"
-#include "llvm/Support/raw_ostream.h"
-#include <algorithm>
-#include <cassert>
-#include <memory>
-#include <tuple>
-
-using namespace llvm;
-
-#define DEBUG_TYPE "cfl-aa"
-
-CFLAAResult::CFLAAResult(const TargetLibraryInfo &TLI)
-    : AAResultBase(), TLI(TLI) {}
-CFLAAResult::CFLAAResult(CFLAAResult &&Arg)
-    : AAResultBase(std::move(Arg)), TLI(Arg.TLI) {}
-CFLAAResult::~CFLAAResult() {}
-
-/// We use InterfaceValue to describe parameters/return value, as well as
-/// potential memory locations that are pointed to by parameters/return value,
-/// of a function.
-/// Index is an integer which represents a single parameter or a return value.
-/// When the index is 0, it refers to the return value. Non-zero index i refers
-/// to the i-th parameter.
-/// DerefLevel indicates the number of dereferences one must perform on the
-/// parameter/return value to get this InterfaceValue.
-struct InterfaceValue {
-  unsigned Index;
-  unsigned DerefLevel;
-};
-
-bool operator==(InterfaceValue lhs, InterfaceValue rhs) {
-  return lhs.Index == rhs.Index && lhs.DerefLevel == rhs.DerefLevel;
-}
-bool operator!=(InterfaceValue lhs, InterfaceValue rhs) {
-  return !(lhs == rhs);
-}
-
-/// We use ExternalRelation to describe an externally visible aliasing relations
-/// between parameters/return value of a function.
-struct ExternalRelation {
-  InterfaceValue From, To;
-};
-
-/// We use ExternalAttribute to describe an externally visible StratifiedAttrs
-/// for parameters/return value.
-struct ExternalAttribute {
-  InterfaceValue IValue;
-  StratifiedAttrs Attr;
-};
-
-/// Information we have about a function and would like to keep around.
-class CFLAAResult::FunctionInfo {
-  StratifiedSets<Value *> Sets;
-
-  // RetParamRelations is a collection of ExternalRelations.
-  SmallVector<ExternalRelation, 8> RetParamRelations;
-
-  // RetParamAttributes is a collection of ExternalAttributes.
-  SmallVector<ExternalAttribute, 8> RetParamAttributes;
-
-public:
-  FunctionInfo(Function &Fn, const SmallVectorImpl<Value *> &RetVals,
-               StratifiedSets<Value *> S);
-
-  const StratifiedSets<Value *> &getStratifiedSets() const { return Sets; }
-  const SmallVectorImpl<ExternalRelation> &getRetParamRelations() const {
-    return RetParamRelations;
-  }
-  const SmallVectorImpl<ExternalAttribute> &getRetParamAttributes() const {
-    return RetParamAttributes;
-  }
-};
-
-/// Try to go from a Value* to a Function*. Never returns nullptr.
-static Optional<Function *> parentFunctionOfValue(Value *);
-
-/// Returns possible functions called by the Inst* into the given
-/// SmallVectorImpl. Returns true if targets found, false otherwise. This is
-/// templated so we can use it with CallInsts and InvokeInsts.
-static bool getPossibleTargets(CallSite, SmallVectorImpl<Function *> &);
-
-const StratifiedIndex StratifiedLink::SetSentinel =
-    std::numeric_limits<StratifiedIndex>::max();
-
-namespace {
-/// StratifiedInfo Attribute things.
-LLVM_CONSTEXPR unsigned MaxStratifiedAttrIndex = NumStratifiedAttrs;
-LLVM_CONSTEXPR unsigned AttrEscapedIndex = 0;
-LLVM_CONSTEXPR unsigned AttrUnknownIndex = 1;
-LLVM_CONSTEXPR unsigned AttrGlobalIndex = 2;
-LLVM_CONSTEXPR unsigned AttrCallerIndex = 3;
-LLVM_CONSTEXPR unsigned AttrFirstArgIndex = 4;
-LLVM_CONSTEXPR unsigned AttrLastArgIndex = MaxStratifiedAttrIndex;
-LLVM_CONSTEXPR unsigned AttrMaxNumArgs = AttrLastArgIndex - AttrFirstArgIndex;
-
-// NOTE: These aren't StratifiedAttrs because bitsets don't have a constexpr
-// ctor for some versions of MSVC that we support. We could maybe refactor,
-// but...
-using StratifiedAttr = unsigned;
-LLVM_CONSTEXPR StratifiedAttr AttrNone = 0;
-LLVM_CONSTEXPR StratifiedAttr AttrEscaped = 1 << AttrEscapedIndex;
-LLVM_CONSTEXPR StratifiedAttr AttrUnknown = 1 << AttrUnknownIndex;
-LLVM_CONSTEXPR StratifiedAttr AttrGlobal = 1 << AttrGlobalIndex;
-LLVM_CONSTEXPR StratifiedAttr AttrCaller = 1 << AttrCallerIndex;
-LLVM_CONSTEXPR StratifiedAttr ExternalAttrMask =
-    AttrEscaped | AttrUnknown | AttrGlobal;
-
-/// The maximum number of arguments we can put into a summary.
-LLVM_CONSTEXPR unsigned MaxSupportedArgsInSummary = 50;
-
-/// StratifiedSets call for knowledge of "direction", so this is how we
-/// represent that locally.
-enum class Level { Same, Above, Below };
-
-/// Edges can be one of four "weights" -- each weight must have an inverse
-/// weight (Assign has Assign; Reference has Dereference).
-enum class EdgeType {
-  /// The weight assigned when assigning from or to a value. For example, in:
-  /// %b = getelementptr %a, 0
-  /// ...The relationships are %b assign %a, and %a assign %b. This used to be
-  /// two edges, but having a distinction bought us nothing.
-  Assign,
-
-  /// 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 (%a Dereference %b)
-  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 (%b Reference %a)
-  Reference
-};
-
-/// The Program Expression Graph (PEG) of CFL analysis
-class CFLGraph {
-  typedef Value *Node;
-
-  struct Edge {
-    EdgeType Type;
-    Node Other;
-  };
-
-  typedef std::vector<Edge> EdgeList;
-
-  struct NodeInfo {
-    EdgeList Edges;
-    StratifiedAttrs Attr;
-  };
-
-  typedef DenseMap<Node, NodeInfo> NodeMap;
-  NodeMap NodeImpls;
-
-  // Gets the inverse of a given EdgeType.
-  static EdgeType flipWeight(EdgeType Initial) {
-    switch (Initial) {
-    case EdgeType::Assign:
-      return EdgeType::Assign;
-    case EdgeType::Dereference:
-      return EdgeType::Reference;
-    case EdgeType::Reference:
-      return EdgeType::Dereference;
-    }
-    llvm_unreachable("Incomplete coverage of EdgeType enum");
-  }
-
-  const NodeInfo *getNode(Node N) const {
-    auto Itr = NodeImpls.find(N);
-    if (Itr == NodeImpls.end())
-      return nullptr;
-    return &Itr->second;
-  }
-  NodeInfo *getNode(Node N) {
-    auto Itr = NodeImpls.find(N);
-    if (Itr == NodeImpls.end())
-      return nullptr;
-    return &Itr->second;
-  }
-
-  static Node nodeDeref(const NodeMap::value_type &P) { return P.first; }
-  typedef std::pointer_to_unary_function<const NodeMap::value_type &, Node>
-      NodeDerefFun;
-
-public:
-  typedef EdgeList::const_iterator const_edge_iterator;
-  typedef mapped_iterator<NodeMap::const_iterator, NodeDerefFun>
-      const_node_iterator;
-
-  bool addNode(Node N) {
-    return NodeImpls.insert(std::make_pair(N, NodeInfo{EdgeList(), AttrNone}))
-        .second;
-  }
-
-  void addAttr(Node N, StratifiedAttrs Attr) {
-    auto *Info = getNode(N);
-    assert(Info != nullptr);
-    Info->Attr |= Attr;
-  }
-
-  void addEdge(Node From, Node To, EdgeType Type) {
-    auto *FromInfo = getNode(From);
-    assert(FromInfo != nullptr);
-    auto *ToInfo = getNode(To);
-    assert(ToInfo != nullptr);
-
-    FromInfo->Edges.push_back(Edge{Type, To});
-    ToInfo->Edges.push_back(Edge{flipWeight(Type), From});
-  }
-
-  StratifiedAttrs attrFor(Node N) const {
-    auto *Info = getNode(N);
-    assert(Info != nullptr);
-    return Info->Attr;
-  }
-
-  iterator_range<const_edge_iterator> edgesFor(Node N) const {
-    auto *Info = getNode(N);
-    assert(Info != nullptr);
-    auto &Edges = Info->Edges;
-    return make_range(Edges.begin(), Edges.end());
-  }
-
-  iterator_range<const_node_iterator> nodes() const {
-    return make_range<const_node_iterator>(
-        map_iterator(NodeImpls.begin(), NodeDerefFun(nodeDeref)),
-        map_iterator(NodeImpls.end(), NodeDerefFun(nodeDeref)));
-  }
-
-  bool empty() const { return NodeImpls.empty(); }
-  std::size_t size() const { return NodeImpls.size(); }
-};
-
-// This is the result of instantiating InterfaceValue at a particular callsite
-struct InterprocNode {
-  Value *Val;
-  unsigned DerefLevel;
-};
-
-// Interprocedural assignment edges that CFLGraph may not easily model
-struct InterprocEdge {
-  InterprocNode From, To;
-};
-
-// Interprocedural attribute tagging that CFLGraph may not easily model
-struct InterprocAttr {
-  InterprocNode Node;
-  StratifiedAttrs Attr;
-};
-
-/// Gets the edges our graph should have, based on an Instruction*
-class GetEdgesVisitor : public InstVisitor<GetEdgesVisitor, void> {
-  CFLAAResult &AA;
-  const TargetLibraryInfo &TLI;
-
-  CFLGraph &Graph;
-  SmallVectorImpl<Value *> &ReturnValues;
-  SmallPtrSetImpl<Value *> &Externals;
-  SmallPtrSetImpl<Value *> &Escapes;
-  SmallVectorImpl<InterprocEdge> &InterprocEdges;
-  SmallVectorImpl<InterprocAttr> &InterprocAttrs;
-
-  static bool hasUsefulEdges(ConstantExpr *CE) {
-    // ConstantExpr doesn't have terminators, invokes, or fences, so only needs
-    // to check for compares.
-    return CE->getOpcode() != Instruction::ICmp &&
-           CE->getOpcode() != Instruction::FCmp;
-  }
-
-  void addNode(Value *Val) {
-    if (!Graph.addNode(Val))
-      return;
-
-    if (isa<GlobalValue>(Val))
-      Externals.insert(Val);
-    else if (auto CExpr = dyn_cast<ConstantExpr>(Val))
-      if (hasUsefulEdges(CExpr))
-        visitConstantExpr(CExpr);
-  }
-
-  void addNodeWithAttr(Value *Val, StratifiedAttrs Attr) {
-    addNode(Val);
-    Graph.addAttr(Val, Attr);
-  }
-
-  void addEdge(Value *From, Value *To, EdgeType Type) {
-    if (!From->getType()->isPointerTy() || !To->getType()->isPointerTy())
-      return;
-    addNode(From);
-    if (To != From)
-      addNode(To);
-    Graph.addEdge(From, To, Type);
-  }
-
-public:
-  GetEdgesVisitor(CFLAAResult &AA, const TargetLibraryInfo &TLI,
-                  CFLGraph &Graph, SmallVectorImpl<Value *> &ReturnValues,
-                  SmallPtrSetImpl<Value *> &Externals,
-                  SmallPtrSetImpl<Value *> &Escapes,
-                  SmallVectorImpl<InterprocEdge> &InterprocEdges,
-                  SmallVectorImpl<InterprocAttr> &InterprocAttrs)
-      : AA(AA), TLI(TLI), Graph(Graph), ReturnValues(ReturnValues),
-        Externals(Externals), Escapes(Escapes), InterprocEdges(InterprocEdges),
-        InterprocAttrs(InterprocAttrs) {}
-
-  void visitInstruction(Instruction &) {
-    llvm_unreachable("Unsupported instruction encountered");
-  }
-
-  void visitReturnInst(ReturnInst &Inst) {
-    if (auto RetVal = Inst.getReturnValue()) {
-      if (RetVal->getType()->isPointerTy()) {
-        addNode(RetVal);
-        ReturnValues.push_back(RetVal);
-      }
-    }
-  }
-
-  void visitPtrToIntInst(PtrToIntInst &Inst) {
-    auto *Ptr = Inst.getOperand(0);
-    addNodeWithAttr(Ptr, AttrEscaped);
-  }
-
-  void visitIntToPtrInst(IntToPtrInst &Inst) {
-    auto *Ptr = &Inst;
-    addNodeWithAttr(Ptr, AttrUnknown);
-  }
-
-  void visitCastInst(CastInst &Inst) {
-    auto *Src = Inst.getOperand(0);
-    addEdge(Src, &Inst, EdgeType::Assign);
-  }
-
-  void visitBinaryOperator(BinaryOperator &Inst) {
-    auto *Op1 = Inst.getOperand(0);
-    auto *Op2 = Inst.getOperand(1);
-    addEdge(Op1, &Inst, EdgeType::Assign);
-    addEdge(Op2, &Inst, EdgeType::Assign);
-  }
-
-  void visitAtomicCmpXchgInst(AtomicCmpXchgInst &Inst) {
-    auto *Ptr = Inst.getPointerOperand();
-    auto *Val = Inst.getNewValOperand();
-    addEdge(Ptr, Val, EdgeType::Dereference);
-  }
-
-  void visitAtomicRMWInst(AtomicRMWInst &Inst) {
-    auto *Ptr = Inst.getPointerOperand();
-    auto *Val = Inst.getValOperand();
-    addEdge(Ptr, Val, EdgeType::Dereference);
-  }
-
-  void visitPHINode(PHINode &Inst) {
-    for (Value *Val : Inst.incoming_values())
-      addEdge(Val, &Inst, EdgeType::Assign);
-  }
-
-  void visitGetElementPtrInst(GetElementPtrInst &Inst) {
-    auto *Op = Inst.getPointerOperand();
-    addEdge(Op, &Inst, EdgeType::Assign);
-  }
-
-  void visitSelectInst(SelectInst &Inst) {
-    // Condition is not processed here (The actual statement producing
-    // the condition result is processed elsewhere). For select, the
-    // condition is evaluated, but not loaded, stored, or assigned
-    // simply as a result of being the condition of a select.
-
-    auto *TrueVal = Inst.getTrueValue();
-    auto *FalseVal = Inst.getFalseValue();
-    addEdge(TrueVal, &Inst, EdgeType::Assign);
-    addEdge(FalseVal, &Inst, EdgeType::Assign);
-  }
-
-  void visitAllocaInst(AllocaInst &Inst) { Graph.addNode(&Inst); }
-
-  void visitLoadInst(LoadInst &Inst) {
-    auto *Ptr = Inst.getPointerOperand();
-    auto *Val = &Inst;
-    addEdge(Val, Ptr, EdgeType::Reference);
-  }
-
-  void visitStoreInst(StoreInst &Inst) {
-    auto *Ptr = Inst.getPointerOperand();
-    auto *Val = Inst.getValueOperand();
-    addEdge(Ptr, Val, EdgeType::Dereference);
-  }
-
-  void visitVAArgInst(VAArgInst &Inst) {
-    // We can't fully model va_arg here. For *Ptr = Inst.getOperand(0), it does
-    // two things:
-    //  1. Loads a value from *((T*)*Ptr).
-    //  2. Increments (stores to) *Ptr by some target-specific amount.
-    // For now, we'll handle this like a landingpad instruction (by placing the
-    // result in its own group, and having that group alias externals).
-    addNodeWithAttr(&Inst, AttrUnknown);
-  }
-
-  static bool isFunctionExternal(Function *Fn) {
-    return !Fn->hasExactDefinition();
-  }
-
-  bool tryInterproceduralAnalysis(CallSite CS,
-                                  const SmallVectorImpl<Function *> &Fns) {
-    assert(Fns.size() > 0);
-
-    if (CS.arg_size() > MaxSupportedArgsInSummary)
-      return false;
-
-    // Exit early if we'll fail anyway
-    for (auto *Fn : Fns) {
-      if (isFunctionExternal(Fn) || Fn->isVarArg())
-        return false;
-      // Fail if the caller does not provide enough arguments
-      assert(Fn->arg_size() <= CS.arg_size());
-      auto &MaybeInfo = AA.ensureCached(Fn);
-      if (!MaybeInfo.hasValue())
-        return false;
-    }
-
-    auto InstantiateInterfaceIndex = [&CS](unsigned Index) {
-      auto Value =
-          (Index == 0) ? CS.getInstruction() : CS.getArgument(Index - 1);
-      return Value->getType()->isPointerTy() ? Value : nullptr;
-    };
-
-    for (auto *Fn : Fns) {
-      auto &FnInfo = AA.ensureCached(Fn);
-      assert(FnInfo.hasValue());
-
-      auto &RetParamRelations = FnInfo->getRetParamRelations();
-      for (auto &Relation : RetParamRelations) {
-        auto FromVal = InstantiateInterfaceIndex(Relation.From.Index);
-        auto ToVal = InstantiateInterfaceIndex(Relation.To.Index);
-        if (FromVal && ToVal) {
-          auto FromLevel = Relation.From.DerefLevel;
-          auto ToLevel = Relation.To.DerefLevel;
-          InterprocEdges.push_back(
-              InterprocEdge{InterprocNode{FromVal, FromLevel},
-                            InterprocNode{ToVal, ToLevel}});
-        }
-      }
-
-      auto &RetParamAttributes = FnInfo->getRetParamAttributes();
-      for (auto &Attribute : RetParamAttributes) {
-        if (auto Val = InstantiateInterfaceIndex(Attribute.IValue.Index)) {
-          InterprocAttrs.push_back(InterprocAttr{
-              InterprocNode{Val, Attribute.IValue.DerefLevel}, Attribute.Attr});
-        }
-      }
-    }
-
-    return true;
-  }
-
-  void visitCallSite(CallSite CS) {
-    auto Inst = CS.getInstruction();
-
-    // Make sure all arguments and return value are added to the graph first
-    for (Value *V : CS.args())
-      addNode(V);
-    if (Inst->getType()->isPointerTy())
-      addNode(Inst);
-
-    // Check if Inst is a call to a library function that allocates/deallocates
-    // on the heap. Those kinds of functions do not introduce any aliases.
-    // TODO: address other common library functions such as realloc(), strdup(),
-    // etc.
-    if (isMallocLikeFn(Inst, &TLI) || isCallocLikeFn(Inst, &TLI) ||
-        isFreeCall(Inst, &TLI))
-      return;
-
-    // TODO: Add support for noalias args/all the other fun function attributes
-    // that we can tack on.
-    SmallVector<Function *, 4> Targets;
-    if (getPossibleTargets(CS, Targets))
-      if (tryInterproceduralAnalysis(CS, Targets))
-        return;
-
-    // Because the function is opaque, we need to note that anything
-    // could have happened to the arguments (unless the function is marked
-    // readonly or readnone), and that the result could alias just about
-    // anything, too (unless the result is marked noalias).
-    if (!CS.onlyReadsMemory())
-      for (Value *V : CS.args()) {
-        if (V->getType()->isPointerTy())
-          Escapes.insert(V);
-      }
-
-    if (Inst->getType()->isPointerTy()) {
-      auto *Fn = CS.getCalledFunction();
-      if (Fn == nullptr || !Fn->doesNotAlias(0))
-        Graph.addAttr(Inst, AttrUnknown);
-    }
-  }
-
-  /// Because vectors/aggregates are immutable and unaddressable, there's
-  /// nothing we can do to coax a value out of them, other than calling
-  /// Extract{Element,Value}. We can effectively treat them as pointers to
-  /// arbitrary memory locations we can store in and load from.
-  void visitExtractElementInst(ExtractElementInst &Inst) {
-    auto *Ptr = Inst.getVectorOperand();
-    auto *Val = &Inst;
-    addEdge(Val, Ptr, EdgeType::Reference);
-  }
-
-  void visitInsertElementInst(InsertElementInst &Inst) {
-    auto *Vec = Inst.getOperand(0);
-    auto *Val = Inst.getOperand(1);
-    addEdge(Vec, &Inst, EdgeType::Assign);
-    addEdge(&Inst, Val, EdgeType::Dereference);
-  }
-
-  void visitLandingPadInst(LandingPadInst &Inst) {
-    // Exceptions come from "nowhere", from our analysis' perspective.
-    // So we place the instruction its own group, noting that said group may
-    // alias externals
-    addNodeWithAttr(&Inst, AttrUnknown);
-  }
-
-  void visitInsertValueInst(InsertValueInst &Inst) {
-    auto *Agg = Inst.getOperand(0);
-    auto *Val = Inst.getOperand(1);
-    addEdge(Agg, &Inst, EdgeType::Assign);
-    addEdge(&Inst, Val, EdgeType::Dereference);
-  }
-
-  void visitExtractValueInst(ExtractValueInst &Inst) {
-    auto *Ptr = Inst.getAggregateOperand();
-    addEdge(&Inst, Ptr, EdgeType::Reference);
-  }
-
-  void visitShuffleVectorInst(ShuffleVectorInst &Inst) {
-    auto *From1 = Inst.getOperand(0);
-    auto *From2 = Inst.getOperand(1);
-    addEdge(From1, &Inst, EdgeType::Assign);
-    addEdge(From2, &Inst, EdgeType::Assign);
-  }
-
-  void visitConstantExpr(ConstantExpr *CE) {
-    switch (CE->getOpcode()) {
-    default:
-      llvm_unreachable("Unknown instruction type encountered!");
-// Build the switch statement using the Instruction.def file.
-#define HANDLE_INST(NUM, OPCODE, CLASS)                                        \
-  case Instruction::OPCODE:                                                    \
-    visit##OPCODE(*(CLASS *)CE);                                               \
-    break;
-#include "llvm/IR/Instruction.def"
-    }
-  }
-};
-
-class CFLGraphBuilder {
-  // Input of the builder
-  CFLAAResult &Analysis;
-  const TargetLibraryInfo &TLI;
-
-  // Output of the builder
-  CFLGraph Graph;
-  SmallVector<Value *, 4> ReturnedValues;
-
-  // Auxiliary structures used by the builder
-  SmallPtrSet<Value *, 8> ExternalValues;
-  SmallPtrSet<Value *, 8> EscapedValues;
-  SmallVector<InterprocEdge, 8> InterprocEdges;
-  SmallVector<InterprocAttr, 8> InterprocAttrs;
-
-  // Helper functions
-
-  // Determines whether or not we an instruction is useless to us (e.g.
-  // FenceInst)
-  static bool hasUsefulEdges(Instruction *Inst) {
-    bool IsNonInvokeRetTerminator = isa<TerminatorInst>(Inst) &&
-                                    !isa<InvokeInst>(Inst) &&
-                                    !isa<ReturnInst>(Inst);
-    return !isa<CmpInst>(Inst) && !isa<FenceInst>(Inst) &&
-           !IsNonInvokeRetTerminator;
-  }
-
-  void addArgumentToGraph(Argument &Arg) {
-    if (Arg.getType()->isPointerTy()) {
-      Graph.addNode(&Arg);
-      ExternalValues.insert(&Arg);
-    }
-  }
-
-  // Given an Instruction, this will add it to the graph, along with any
-  // Instructions that are potentially only available from said Instruction
-  // For example, given the following line:
-  //   %0 = load i16* getelementptr ([1 x i16]* @a, 0, 0), align 2
-  // addInstructionToGraph would add both the `load` and `getelementptr`
-  // instructions to the graph appropriately.
-  void addInstructionToGraph(Instruction &Inst) {
-    if (!hasUsefulEdges(&Inst))
-      return;
-
-    GetEdgesVisitor(Analysis, TLI, Graph, ReturnedValues, ExternalValues,
-                    EscapedValues, InterprocEdges, InterprocAttrs)
-        .visit(Inst);
-  }
-
-  // Builds the graph needed for constructing the StratifiedSets for the given
-  // function
-  void buildGraphFrom(Function &Fn) {
-    for (auto &Bb : Fn.getBasicBlockList())
-      for (auto &Inst : Bb.getInstList())
-        addInstructionToGraph(Inst);
-
-    for (auto &Arg : Fn.args())
-      addArgumentToGraph(Arg);
-  }
-
-public:
-  CFLGraphBuilder(CFLAAResult &Analysis, const TargetLibraryInfo &TLI,
-                  Function &Fn)
-      : Analysis(Analysis), TLI(TLI) {
-    buildGraphFrom(Fn);
-  }
-
-  const CFLGraph &getCFLGraph() const { return Graph; }
-  const SmallVector<Value *, 4> &getReturnValues() const {
-    return ReturnedValues;
-  }
-  const SmallPtrSet<Value *, 8> &getExternalValues() const {
-    return ExternalValues;
-  }
-  const SmallPtrSet<Value *, 8> &getEscapedValues() const {
-    return EscapedValues;
-  }
-  const SmallVector<InterprocEdge, 8> &getInterprocEdges() const {
-    return InterprocEdges;
-  }
-  const SmallVector<InterprocAttr, 8> &getInterprocAttrs() const {
-    return InterprocAttrs;
-  }
-};
-}
-
-//===----------------------------------------------------------------------===//
-// Function declarations that require types defined in the namespace above
-//===----------------------------------------------------------------------===//
-
-/// Given a StratifiedAttrs, returns true if it marks the corresponding values
-/// as globals or arguments
-static bool isGlobalOrArgAttr(StratifiedAttrs Attr);
-
-/// Given a StratifiedAttrs, returns true if the corresponding values come from
-/// an unknown source (such as opaque memory or an integer cast)
-static bool isUnknownAttr(StratifiedAttrs Attr);
-
-/// Given an argument number, returns the appropriate StratifiedAttr to set.
-static StratifiedAttrs argNumberToAttr(unsigned ArgNum);
-
-/// Given a Value, potentially return which StratifiedAttr it maps to.
-static Optional<StratifiedAttrs> valueToAttr(Value *Val);
-
-/// Gets the "Level" that one should travel in StratifiedSets
-/// given an EdgeType.
-static Level directionOfEdgeType(EdgeType);
-
-/// Determines whether it would be pointless to add the given Value to our sets.
-static bool canSkipAddingToSets(Value *Val);
-
-static Optional<Function *> parentFunctionOfValue(Value *Val) {
-  if (auto *Inst = dyn_cast<Instruction>(Val)) {
-    auto *Bb = Inst->getParent();
-    return Bb->getParent();
-  }
-
-  if (auto *Arg = dyn_cast<Argument>(Val))
-    return Arg->getParent();
-  return None;
-}
-
-static bool getPossibleTargets(CallSite CS,
-                               SmallVectorImpl<Function *> &Output) {
-  if (auto *Fn = CS.getCalledFunction()) {
-    Output.push_back(Fn);
-    return true;
-  }
-
-  // TODO: If the call is indirect, we might be able to enumerate all potential
-  // targets of the call and return them, rather than just failing.
-  return false;
-}
-
-static bool isGlobalOrArgAttr(StratifiedAttrs Attr) {
-  return Attr.reset(AttrEscapedIndex)
-      .reset(AttrUnknownIndex)
-      .reset(AttrCallerIndex)
-      .any();
-}
-
-static bool isUnknownAttr(StratifiedAttrs Attr) {
-  return Attr.test(AttrUnknownIndex) || Attr.test(AttrCallerIndex);
-}
-
-static Optional<StratifiedAttrs> valueToAttr(Value *Val) {
-  if (isa<GlobalValue>(Val))
-    return StratifiedAttrs(AttrGlobal);
-
-  if (auto *Arg = dyn_cast<Argument>(Val))
-    // Only pointer arguments should have the argument attribute,
-    // because things can't escape through scalars without us seeing a
-    // cast, and thus, interaction with them doesn't matter.
-    if (!Arg->hasNoAliasAttr() && Arg->getType()->isPointerTy())
-      return argNumberToAttr(Arg->getArgNo());
-  return None;
-}
-
-static StratifiedAttrs argNumberToAttr(unsigned ArgNum) {
-  if (ArgNum >= AttrMaxNumArgs)
-    return AttrUnknown;
-  // N.B. MSVC complains if we use `1U` here, since StratifiedAttrs' ctor takes
-  // an unsigned long long.
-  return StratifiedAttrs(1ULL << (ArgNum + AttrFirstArgIndex));
-}
-
-static Level directionOfEdgeType(EdgeType Weight) {
-  switch (Weight) {
-  case EdgeType::Reference:
-    return Level::Above;
-  case EdgeType::Dereference:
-    return Level::Below;
-  case EdgeType::Assign:
-    return Level::Same;
-  }
-  llvm_unreachable("Incomplete switch coverage");
-}
-
-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)) {
-    // 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) ||
-                               isa<ConstantAggregate>(Val);
-    return !CanStoreMutableData;
-  }
-
-  return false;
-}
-
-CFLAAResult::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.
-  if (Fn.arg_size() > MaxSupportedArgsInSummary)
-    return;
-
-  DenseMap<StratifiedIndex, InterfaceValue> InterfaceMap;
-
-  // Our intention here is to record all InterfaceValues that share the same
-  // StratifiedIndex in RetParamRelations. For each valid InterfaceValue, we
-  // have its StratifiedIndex scanned here and check if the index is presented
-  // in InterfaceMap: if it is not, we add the correspondence to the map;
-  // otherwise, an aliasing relation is found and we add it to
-  // RetParamRelations.
-
-  auto AddToRetParamRelations = [&](unsigned InterfaceIndex,
-                                    StratifiedIndex SetIndex) {
-    unsigned Level = 0;
-    while (true) {
-      InterfaceValue CurrValue{InterfaceIndex, Level};
-
-      auto Itr = InterfaceMap.find(SetIndex);
-      if (Itr != InterfaceMap.end()) {
-        if (CurrValue != Itr->second)
-          RetParamRelations.push_back(ExternalRelation{CurrValue, Itr->second});
-        break;
-      }
-
-      auto &Link = Sets.getLink(SetIndex);
-      InterfaceMap.insert(std::make_pair(SetIndex, CurrValue));
-      auto ExternalAttrs = Link.Attrs & StratifiedAttrs(ExternalAttrMask);
-      if (ExternalAttrs.any())
-        RetParamAttributes.push_back(
-            ExternalAttribute{CurrValue, ExternalAttrs});
-
-      if (!Link.hasBelow())
-        break;
-
-      ++Level;
-      SetIndex = Link.Below;
-    }
-  };
-
-  // Populate RetParamRelations for return values
-  for (auto *RetVal : RetVals) {
-    assert(RetVal != nullptr);
-    assert(RetVal->getType()->isPointerTy());
-    auto RetInfo = Sets.find(RetVal);
-    if (RetInfo.hasValue())
-      AddToRetParamRelations(0, RetInfo->Index);
-  }
-
-  // Populate RetParamRelations for parameters
-  unsigned I = 0;
-  for (auto &Param : Fn.args()) {
-    if (Param.getType()->isPointerTy()) {
-      auto ParamInfo = Sets.find(&Param);
-      if (ParamInfo.hasValue())
-        AddToRetParamRelations(I + 1, ParamInfo->Index);
-    }
-    ++I;
-  }
-}
-
-// Builds the graph + StratifiedSets for a function.
-CFLAAResult::FunctionInfo CFLAAResult::buildSetsFrom(Function *Fn) {
-  CFLGraphBuilder GraphBuilder(*this, TLI, *Fn);
-  StratifiedSetsBuilder<Value *> SetBuilder;
-
-  auto &Graph = GraphBuilder.getCFLGraph();
-  SmallVector<Value *, 16> Worklist;
-  for (auto Node : Graph.nodes())
-    Worklist.push_back(Node);
-
-  while (!Worklist.empty()) {
-    auto *CurValue = Worklist.pop_back_val();
-    SetBuilder.add(CurValue);
-    if (canSkipAddingToSets(CurValue))
-      continue;
-
-    auto Attr = Graph.attrFor(CurValue);
-    SetBuilder.noteAttributes(CurValue, Attr);
-
-    for (const auto &Edge : Graph.edgesFor(CurValue)) {
-      auto Label = Edge.Type;
-      auto *OtherValue = Edge.Other;
-
-      if (canSkipAddingToSets(OtherValue))
-        continue;
-
-      bool Added;
-      switch (directionOfEdgeType(Label)) {
-      case Level::Above:
-        Added = SetBuilder.addAbove(CurValue, OtherValue);
-        break;
-      case Level::Below:
-        Added = SetBuilder.addBelow(CurValue, OtherValue);
-        break;
-      case Level::Same:
-        Added = SetBuilder.addWith(CurValue, OtherValue);
-        break;
-      }
-
-      if (Added)
-        Worklist.push_back(OtherValue);
-    }
-  }
-
-  // Special handling for globals and arguments
-  for (auto *External : GraphBuilder.getExternalValues()) {
-    SetBuilder.add(External);
-    auto Attr = valueToAttr(External);
-    if (Attr.hasValue()) {
-      SetBuilder.noteAttributes(External, *Attr);
-      if (*Attr == AttrGlobal)
-        SetBuilder.addAttributesBelow(External, 1, AttrUnknown);
-      else
-        SetBuilder.addAttributesBelow(External, 1, AttrCaller);
-    }
-  }
-
-  // Special handling for interprocedural aliases
-  for (auto &Edge : GraphBuilder.getInterprocEdges()) {
-    auto FromVal = Edge.From.Val;
-    auto ToVal = Edge.To.Val;
-    SetBuilder.add(FromVal);
-    SetBuilder.add(ToVal);
-    SetBuilder.addBelowWith(FromVal, Edge.From.DerefLevel, ToVal,
-                            Edge.To.DerefLevel);
-  }
-
-  // Special handling for interprocedural attributes
-  for (auto &IPAttr : GraphBuilder.getInterprocAttrs()) {
-    auto Val = IPAttr.Node.Val;
-    SetBuilder.add(Val);
-    SetBuilder.addAttributesBelow(Val, IPAttr.Node.DerefLevel, IPAttr.Attr);
-  }
-
-  // Special handling for opaque external functions
-  for (auto *Escape : GraphBuilder.getEscapedValues()) {
-    SetBuilder.add(Escape);
-    SetBuilder.noteAttributes(Escape, AttrEscaped);
-    SetBuilder.addAttributesBelow(Escape, 1, AttrUnknown);
-  }
-
-  return FunctionInfo(*Fn, GraphBuilder.getReturnValues(), SetBuilder.build());
-}
-
-void CFLAAResult::scan(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 = buildSetsFrom(Fn);
-  Cache[Fn] = std::move(FunInfo);
-
-  Handles.push_front(FunctionHandle(Fn, this));
-}
-
-void CFLAAResult::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) {
-  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;
-}
-
-AliasResult CFLAAResult::query(const MemoryLocation &LocA,
-                               const MemoryLocation &LocB) {
-  auto *ValA = const_cast<Value *>(LocA.Ptr);
-  auto *ValB = const_cast<Value *>(LocB.Ptr);
-
-  if (!ValA->getType()->isPointerTy() || !ValB->getType()->isPointerTy())
-    return NoAlias;
-
-  Function *Fn = nullptr;
-  auto MaybeFnA = parentFunctionOfValue(ValA);
-  auto MaybeFnB = parentFunctionOfValue(ValB);
-  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");
-    return MayAlias;
-  }
-
-  if (MaybeFnA.hasValue()) {
-    Fn = *MaybeFnA;
-    assert((!MaybeFnB.hasValue() || *MaybeFnB == *MaybeFnA) &&
-           "Interprocedural queries not supported");
-  } else {
-    Fn = *MaybeFnB;
-  }
-
-  assert(Fn != nullptr);
-  auto &MaybeInfo = ensureCached(Fn);
-  assert(MaybeInfo.hasValue());
-
-  auto &Sets = MaybeInfo->getStratifiedSets();
-  auto MaybeA = Sets.find(ValA);
-  if (!MaybeA.hasValue())
-    return MayAlias;
-
-  auto MaybeB = Sets.find(ValB);
-  if (!MaybeB.hasValue())
-    return MayAlias;
-
-  auto SetA = *MaybeA;
-  auto SetB = *MaybeB;
-  auto AttrsA = Sets.getLink(SetA.Index).Attrs;
-  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
-  // 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:
-  // - Non-local values may alias each other
-  // - AttrNone values do not alias any non-local values
-  // - AttrEscaped do not alias globals/arguments, but they may alias
-  // AttrUnknown values
-  if (SetA.Index == SetB.Index)
-    return MayAlias;
-  if (AttrsA.none() || AttrsB.none())
-    return NoAlias;
-  if (isUnknownAttr(AttrsA) || isUnknownAttr(AttrsB))
-    return MayAlias;
-  if (isGlobalOrArgAttr(AttrsA) && isGlobalOrArgAttr(AttrsB))
-    return MayAlias;
-  return NoAlias;
-}
-
-ModRefInfo CFLAAResult::getArgModRefInfo(ImmutableCallSite CS,
-                                         unsigned ArgIdx) {
-  if (auto CalledFunc = CS.getCalledFunction()) {
-    auto &MaybeInfo = ensureCached(const_cast<Function *>(CalledFunc));
-    if (!MaybeInfo.hasValue())
-      return MRI_ModRef;
-    auto &RetParamAttributes = MaybeInfo->getRetParamAttributes();
-    auto &RetParamRelations = MaybeInfo->getRetParamRelations();
-
-    bool ArgAttributeIsWritten =
-        std::any_of(RetParamAttributes.begin(), RetParamAttributes.end(),
-                    [ArgIdx](const ExternalAttribute &ExtAttr) {
-                      return ExtAttr.IValue.Index == ArgIdx + 1;
-                    });
-    bool ArgIsAccessed =
-        std::any_of(RetParamRelations.begin(), RetParamRelations.end(),
-                    [ArgIdx](const ExternalRelation &ExtRelation) {
-                      return ExtRelation.To.Index == ArgIdx + 1 ||
-                             ExtRelation.From.Index == ArgIdx + 1;
-                    });
-
-    return (!ArgIsAccessed && !ArgAttributeIsWritten) ? MRI_NoModRef
-                                                      : MRI_ModRef;
-  }
-
-  return MRI_ModRef;
-}
-
-FunctionModRefBehavior CFLAAResult::getModRefBehavior(ImmutableCallSite CS) {
-  // If we know the callee, try analyzing it
-  if (auto CalledFunc = CS.getCalledFunction())
-    return getModRefBehavior(CalledFunc);
-
-  // Otherwise, be conservative
-  return FMRB_UnknownModRefBehavior;
-}
-
-FunctionModRefBehavior CFLAAResult::getModRefBehavior(const Function *F) {
-  assert(F != nullptr);
-
-  // TODO: Remove the const_cast
-  auto &MaybeInfo = ensureCached(const_cast<Function *>(F));
-  if (!MaybeInfo.hasValue())
-    return FMRB_UnknownModRefBehavior;
-  auto &RetParamAttributes = MaybeInfo->getRetParamAttributes();
-  auto &RetParamRelations = MaybeInfo->getRetParamRelations();
-
-  // First, if any argument is marked Escpaed, Unknown or Global, anything may
-  // happen to them and thus we can't draw any conclusion.
-  if (!RetParamAttributes.empty())
-    return FMRB_UnknownModRefBehavior;
-
-  // Currently we don't (and can't) distinguish reads from writes in
-  // RetParamRelations. All we can say is whether there may be memory access or
-  // not.
-  if (RetParamRelations.empty())
-    return FMRB_DoesNotAccessMemory;
-
-  // Check if something beyond argmem gets touched.
-  bool AccessArgMemoryOnly =
-      std::all_of(RetParamRelations.begin(), RetParamRelations.end(),
-                  [](const ExternalRelation &ExtRelation) {
-                    // Both DerefLevels has to be 0, since we don't know which
-                    // one is a read and which is a write.
-                    return ExtRelation.From.DerefLevel == 0 &&
-                           ExtRelation.To.DerefLevel == 0;
-                  });
-  return AccessArgMemoryOnly ? FMRB_OnlyAccessesArgumentPointees
-                             : FMRB_UnknownModRefBehavior;
-}
-
-char CFLAA::PassID;
-
-CFLAAResult CFLAA::run(Function &F, AnalysisManager<Function> &AM) {
-  return CFLAAResult(AM.getResult<TargetLibraryAnalysis>(F));
-}
-
-char CFLAAWrapperPass::ID = 0;
-INITIALIZE_PASS(CFLAAWrapperPass, "cfl-aa", "CFL-Based Alias Analysis", false,
-                true)
-
-ImmutablePass *llvm::createCFLAAWrapperPass() { return new CFLAAWrapperPass(); }
-
-CFLAAWrapperPass::CFLAAWrapperPass() : ImmutablePass(ID) {
-  initializeCFLAAWrapperPassPass(*PassRegistry::getPassRegistry());
-}
-
-void CFLAAWrapperPass::initializePass() {
-  auto &TLIWP = getAnalysis<TargetLibraryInfoWrapperPass>();
-  Result.reset(new CFLAAResult(TLIWP.getTLI()));
-}
-
-void CFLAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
-  AU.setPreservesAll();
-  AU.addRequired<TargetLibraryInfoWrapperPass>();
-}

llvm/trunk/lib/Analysis/CFLAndersAliasAnalysis.cpp

+//- 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();
+}

llvm/trunk/lib/Analysis/CFLSteensAliasAnalysis.cpp

+//- CFLSteensAliasAnalysis.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-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
+// 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 "Fast algorithms..." (mentioned above)
+// in order to transform the graph into sets of variables that may alias in
+// ~nlogn time (n = number of variables), which makes queries take constant
+// time.
+//===----------------------------------------------------------------------===//
+
+// N.B. AliasAnalysis as a whole is phrased as a FunctionPass at the moment, and
+// 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/CFLSteensAliasAnalysis.h"
+#include "StratifiedSets.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/None.h"
+#include "llvm/ADT/Optional.h"
+#include "llvm/Analysis/MemoryBuiltins.h"
+#include "llvm/Analysis/TargetLibraryInfo.h"
+#include "llvm/IR/Constants.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/InstVisitor.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/Pass.h"
+#include "llvm/Support/Compiler.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/ErrorHandling.h"
+#include "llvm/Support/raw_ostream.h"
+#include <algorithm>
+#include <cassert>
+#include <memory>
+#include <tuple>
+
+using namespace llvm;
+
+#define DEBUG_TYPE "cfl-steens-aa"
+
+CFLSteensAAResult::CFLSteensAAResult(const TargetLibraryInfo &TLI)
+    : AAResultBase(), TLI(TLI) {}
+CFLSteensAAResult::CFLSteensAAResult(CFLSteensAAResult &&Arg)
+    : AAResultBase(std::move(Arg)), TLI(Arg.TLI) {}
+CFLSteensAAResult::~CFLSteensAAResult() {}
+
+/// We use InterfaceValue to describe parameters/return value, as well as
+/// potential memory locations that are pointed to by parameters/return value,
+/// of a function.
+/// Index is an integer which represents a single parameter or a return value.
+/// When the index is 0, it refers to the return value. Non-zero index i refers
+/// to the i-th parameter.
+/// DerefLevel indicates the number of dereferences one must perform on the
+/// parameter/return value to get this InterfaceValue.
+struct InterfaceValue {
+  unsigned Index;
+  unsigned DerefLevel;
+};
+
+bool operator==(InterfaceValue lhs, InterfaceValue rhs) {
+  return lhs.Index == rhs.Index && lhs.DerefLevel == rhs.DerefLevel;
+}
+bool operator!=(InterfaceValue lhs, InterfaceValue rhs) {
+  return !(lhs == rhs);
+}
+
+/// We use ExternalRelation to describe an externally visible aliasing relations
+/// between parameters/return value of a function.
+struct ExternalRelation {
+  InterfaceValue From, To;
+};
+
+/// We use ExternalAttribute to describe an externally visible StratifiedAttrs
+/// for parameters/return value.
+struct ExternalAttribute {
+  InterfaceValue IValue;
+  StratifiedAttrs Attr;
+};
+
+/// Information we have about a function and would like to keep around.
+class CFLSteensAAResult::FunctionInfo {
+  StratifiedSets<Value *> Sets;
+
+  // RetParamRelations is a collection of ExternalRelations.
+  SmallVector<ExternalRelation, 8> RetParamRelations;
+
+  // RetParamAttributes is a collection of ExternalAttributes.
+  SmallVector<ExternalAttribute, 8> RetParamAttributes;
+
+public:
+  FunctionInfo(Function &Fn, const SmallVectorImpl<Value *> &RetVals,
+               StratifiedSets<Value *> S);
+
+  const StratifiedSets<Value *> &getStratifiedSets() const { return Sets; }
+  const SmallVectorImpl<ExternalRelation> &getRetParamRelations() const {
+    return RetParamRelations;
+  }
+  const SmallVectorImpl<ExternalAttribute> &getRetParamAttributes() const {
+    return RetParamAttributes;
+  }
+};
+
+/// Try to go from a Value* to a Function*. Never returns nullptr.
+static Optional<Function *> parentFunctionOfValue(Value *);
+
+/// Returns possible functions called by the Inst* into the given
+/// SmallVectorImpl. Returns true if targets found, false otherwise. This is
+/// templated so we can use it with CallInsts and InvokeInsts.
+static bool getPossibleTargets(CallSite, SmallVectorImpl<Function *> &);
+
+const StratifiedIndex StratifiedLink::SetSentinel =
+    std::numeric_limits<StratifiedIndex>::max();
+
+namespace {
+/// StratifiedInfo Attribute things.
+LLVM_CONSTEXPR unsigned MaxStratifiedAttrIndex = NumStratifiedAttrs;
+LLVM_CONSTEXPR unsigned AttrEscapedIndex = 0;
+LLVM_CONSTEXPR unsigned AttrUnknownIndex = 1;
+LLVM_CONSTEXPR unsigned AttrGlobalIndex = 2;
+LLVM_CONSTEXPR unsigned AttrCallerIndex = 3;
+LLVM_CONSTEXPR unsigned AttrFirstArgIndex = 4;
+LLVM_CONSTEXPR unsigned AttrLastArgIndex = MaxStratifiedAttrIndex;
+LLVM_CONSTEXPR unsigned AttrMaxNumArgs = AttrLastArgIndex - AttrFirstArgIndex;
+
+// NOTE: These aren't StratifiedAttrs because bitsets don't have a constexpr
+// ctor for some versions of MSVC that we support. We could maybe refactor,
+// but...
+using StratifiedAttr = unsigned;
+LLVM_CONSTEXPR StratifiedAttr AttrNone = 0;
+LLVM_CONSTEXPR StratifiedAttr AttrEscaped = 1 << AttrEscapedIndex;
+LLVM_CONSTEXPR StratifiedAttr AttrUnknown = 1 << AttrUnknownIndex;
+LLVM_CONSTEXPR StratifiedAttr AttrGlobal = 1 << AttrGlobalIndex;
+LLVM_CONSTEXPR StratifiedAttr AttrCaller = 1 << AttrCallerIndex;
+LLVM_CONSTEXPR StratifiedAttr ExternalAttrMask =
+    AttrEscaped | AttrUnknown | AttrGlobal;
+
+/// The maximum number of arguments we can put into a summary.
+LLVM_CONSTEXPR unsigned MaxSupportedArgsInSummary = 50;
+
+/// StratifiedSets call for knowledge of "direction", so this is how we
+/// represent that locally.
+enum class Level { Same, Above, Below };
+
+/// Edges can be one of four "weights" -- each weight must have an inverse
+/// weight (Assign has Assign; Reference has Dereference).
+enum class EdgeType {
+  /// The weight assigned when assigning from or to a value. For example, in:
+  /// %b = getelementptr %a, 0
+  /// ...The relationships are %b assign %a, and %a assign %b. This used to be
+  /// two edges, but having a distinction bought us nothing.
+  Assign,
+
+  /// 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 (%a Dereference %b)
+  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 (%b Reference %a)
+  Reference
+};
+
+/// The Program Expression Graph (PEG) of CFL analysis
+class CFLGraph {
+  typedef Value *Node;
+
+  struct Edge {
+    EdgeType Type;
+    Node Other;
+  };
+
+  typedef std::vector<Edge> EdgeList;
+
+  struct NodeInfo {
+    EdgeList Edges;
+    StratifiedAttrs Attr;
+  };
+
+  typedef DenseMap<Node, NodeInfo> NodeMap;
+  NodeMap NodeImpls;
+
+  // Gets the inverse of a given EdgeType.
+  static EdgeType flipWeight(EdgeType Initial) {
+    switch (Initial) {
+    case EdgeType::Assign:
+      return EdgeType::Assign;
+    case EdgeType::Dereference:
+      return EdgeType::Reference;
+    case EdgeType::Reference:
+      return EdgeType::Dereference;
+    }
+    llvm_unreachable("Incomplete coverage of EdgeType enum");
+  }
+
+  const NodeInfo *getNode(Node N) const {
+    auto Itr = NodeImpls.find(N);
+    if (Itr == NodeImpls.end())
+      return nullptr;
+    return &Itr->second;
+  }
+  NodeInfo *getNode(Node N) {
+    auto Itr = NodeImpls.find(N);
+    if (Itr == NodeImpls.end())
+      return nullptr;
+    return &Itr->second;
+  }
+
+  static Node nodeDeref(const NodeMap::value_type &P) { return P.first; }
+  typedef std::pointer_to_unary_function<const NodeMap::value_type &, Node>
+      NodeDerefFun;
+
+public:
+  typedef EdgeList::const_iterator const_edge_iterator;
+  typedef mapped_iterator<NodeMap::const_iterator, NodeDerefFun>
+      const_node_iterator;
+
+  bool addNode(Node N) {
+    return NodeImpls.insert(std::make_pair(N, NodeInfo{EdgeList(), AttrNone}))
+        .second;
+  }
+
+  void addAttr(Node N, StratifiedAttrs Attr) {
+    auto *Info = getNode(N);
+    assert(Info != nullptr);
+    Info->Attr |= Attr;
+  }
+
+  void addEdge(Node From, Node To, EdgeType Type) {
+    auto *FromInfo = getNode(From);
+    assert(FromInfo != nullptr);
+    auto *ToInfo = getNode(To);
+    assert(ToInfo != nullptr);
+
+    FromInfo->Edges.push_back(Edge{Type, To});
+    ToInfo->Edges.push_back(Edge{flipWeight(Type), From});
+  }
+
+  StratifiedAttrs attrFor(Node N) const {
+    auto *Info = getNode(N);
+    assert(Info != nullptr);
+    return Info->Attr;
+  }
+
+  iterator_range<const_edge_iterator> edgesFor(Node N) const {
+    auto *Info = getNode(N);
+    assert(Info != nullptr);
+    auto &Edges = Info->Edges;
+    return make_range(Edges.begin(), Edges.end());
+  }
+
+  iterator_range<const_node_iterator> nodes() const {
+    return make_range<const_node_iterator>(
+        map_iterator(NodeImpls.begin(), NodeDerefFun(nodeDeref)),
+        map_iterator(NodeImpls.end(), NodeDerefFun(nodeDeref)));
+  }
+
+  bool empty() const { return NodeImpls.empty(); }
+  std::size_t size() const { return NodeImpls.size(); }
+};
+
+// This is the result of instantiating InterfaceValue at a particular callsite
+struct InterprocNode {
+  Value *Val;
+  unsigned DerefLevel;
+};
+
+// Interprocedural assignment edges that CFLGraph may not easily model
+struct InterprocEdge {
+  InterprocNode From, To;
+};
+
+// Interprocedural attribute tagging that CFLGraph may not easily model
+struct InterprocAttr {
+  InterprocNode Node;
+  StratifiedAttrs Attr;
+};
+
+/// Gets the edges our graph should have, based on an Instruction*
+class GetEdgesVisitor : public InstVisitor<GetEdgesVisitor, void> {
+  CFLSteensAAResult &AA;
+  const TargetLibraryInfo &TLI;
+
+  CFLGraph &Graph;
+  SmallVectorImpl<Value *> &ReturnValues;
+  SmallPtrSetImpl<Value *> &Externals;
+  SmallPtrSetImpl<Value *> &Escapes;
+  SmallVectorImpl<InterprocEdge> &InterprocEdges;
+  SmallVectorImpl<InterprocAttr> &InterprocAttrs;
+
+  static bool hasUsefulEdges(ConstantExpr *CE) {
+    // ConstantExpr doesn't have terminators, invokes, or fences, so only needs
+    // to check for compares.
+    return CE->getOpcode() != Instruction::ICmp &&
+           CE->getOpcode() != Instruction::FCmp;
+  }
+
+  void addNode(Value *Val) {
+    if (!Graph.addNode(Val))
+      return;
+
+    if (isa<GlobalValue>(Val))
+      Externals.insert(Val);
+    else if (auto CExpr = dyn_cast<ConstantExpr>(Val))
+      if (hasUsefulEdges(CExpr))
+        visitConstantExpr(CExpr);
+  }
+
+  void addNodeWithAttr(Value *Val, StratifiedAttrs Attr) {
+    addNode(Val);
+    Graph.addAttr(Val, Attr);
+  }
+
+  void addEdge(Value *From, Value *To, EdgeType Type) {
+    if (!From->getType()->isPointerTy() || !To->getType()->isPointerTy())
+      return;
+    addNode(From);
+    if (To != From)
+      addNode(To);
+    Graph.addEdge(From, To, Type);
+  }
+
+public:
+  GetEdgesVisitor(CFLSteensAAResult &AA, const TargetLibraryInfo &TLI,
+                  CFLGraph &Graph, SmallVectorImpl<Value *> &ReturnValues,
+                  SmallPtrSetImpl<Value *> &Externals,
+                  SmallPtrSetImpl<Value *> &Escapes,
+                  SmallVectorImpl<InterprocEdge> &InterprocEdges,
+                  SmallVectorImpl<InterprocAttr> &InterprocAttrs)
+      : AA(AA), TLI(TLI), Graph(Graph), ReturnValues(ReturnValues),
+        Externals(Externals), Escapes(Escapes), InterprocEdges(InterprocEdges),
+        InterprocAttrs(InterprocAttrs) {}
+
+  void visitInstruction(Instruction &) {
+    llvm_unreachable("Unsupported instruction encountered");
+  }
+
+  void visitReturnInst(ReturnInst &Inst) {
+    if (auto RetVal = Inst.getReturnValue()) {
+      if (RetVal->getType()->isPointerTy()) {
+        addNode(RetVal);
+        ReturnValues.push_back(RetVal);
+      }
+    }
+  }
+
+  void visitPtrToIntInst(PtrToIntInst &Inst) {
+    auto *Ptr = Inst.getOperand(0);
+    addNodeWithAttr(Ptr, AttrEscaped);
+  }
+
+  void visitIntToPtrInst(IntToPtrInst &Inst) {
+    auto *Ptr = &Inst;
+    addNodeWithAttr(Ptr, AttrUnknown);
+  }
+
+  void visitCastInst(CastInst &Inst) {
+    auto *Src = Inst.getOperand(0);
+    addEdge(Src, &Inst, EdgeType::Assign);
+  }
+
+  void visitBinaryOperator(BinaryOperator &Inst) {
+    auto *Op1 = Inst.getOperand(0);
+    auto *Op2 = Inst.getOperand(1);
+    addEdge(Op1, &Inst, EdgeType::Assign);
+    addEdge(Op2, &Inst, EdgeType::Assign);
+  }
+
+  void visitAtomicCmpXchgInst(AtomicCmpXchgInst &Inst) {
+    auto *Ptr = Inst.getPointerOperand();
+    auto *Val = Inst.getNewValOperand();
+    addEdge(Ptr, Val, EdgeType::Dereference);
+  }
+
+  void visitAtomicRMWInst(AtomicRMWInst &Inst) {
+    auto *Ptr = Inst.getPointerOperand();
+    auto *Val = Inst.getValOperand();
+    addEdge(Ptr, Val, EdgeType::Dereference);
+  }
+
+  void visitPHINode(PHINode &Inst) {
+    for (Value *Val : Inst.incoming_values())
+      addEdge(Val, &Inst, EdgeType::Assign);
+  }
+
+  void visitGetElementPtrInst(GetElementPtrInst &Inst) {
+    auto *Op = Inst.getPointerOperand();
+    addEdge(Op, &Inst, EdgeType::Assign);
+  }
+
+  void visitSelectInst(SelectInst &Inst) {
+    // Condition is not processed here (The actual statement producing
+    // the condition result is processed elsewhere). For select, the
+    // condition is evaluated, but not loaded, stored, or assigned
+    // simply as a result of being the condition of a select.
+
+    auto *TrueVal = Inst.getTrueValue();
+    auto *FalseVal = Inst.getFalseValue();
+    addEdge(TrueVal, &Inst, EdgeType::Assign);
+    addEdge(FalseVal, &Inst, EdgeType::Assign);
+  }
+
+  void visitAllocaInst(AllocaInst &Inst) { Graph.addNode(&Inst); }
+
+  void visitLoadInst(LoadInst &Inst) {
+    auto *Ptr = Inst.getPointerOperand();
+    auto *Val = &Inst;
+    addEdge(Val, Ptr, EdgeType::Reference);
+  }
+
+  void visitStoreInst(StoreInst &Inst) {
+    auto *Ptr = Inst.getPointerOperand();
+    auto *Val = Inst.getValueOperand();
+    addEdge(Ptr, Val, EdgeType::Dereference);
+  }
+
+  void visitVAArgInst(VAArgInst &Inst) {
+    // We can't fully model va_arg here. For *Ptr = Inst.getOperand(0), it does
+    // two things:
+    //  1. Loads a value from *((T*)*Ptr).
+    //  2. Increments (stores to) *Ptr by some target-specific amount.
+    // For now, we'll handle this like a landingpad instruction (by placing the
+    // result in its own group, and having that group alias externals).
+    addNodeWithAttr(&Inst, AttrUnknown);
+  }
+
+  static bool isFunctionExternal(Function *Fn) {
+    return !Fn->hasExactDefinition();
+  }
+
+  bool tryInterproceduralAnalysis(CallSite CS,
+                                  const SmallVectorImpl<Function *> &Fns) {
+    assert(Fns.size() > 0);
+
+    if (CS.arg_size() > MaxSupportedArgsInSummary)
+      return false;
+
+    // Exit early if we'll fail anyway
+    for (auto *Fn : Fns) {
+      if (isFunctionExternal(Fn) || Fn->isVarArg())
+        return false;
+      // Fail if the caller does not provide enough arguments
+      assert(Fn->arg_size() <= CS.arg_size());
+      auto &MaybeInfo = AA.ensureCached(Fn);
+      if (!MaybeInfo.hasValue())
+        return false;
+    }
+
+    auto InstantiateInterfaceIndex = [&CS](unsigned Index) {
+      auto Value =
+          (Index == 0) ? CS.getInstruction() : CS.getArgument(Index - 1);
+      return Value->getType()->isPointerTy() ? Value : nullptr;
+    };
+
+    for (auto *Fn : Fns) {
+      auto &FnInfo = AA.ensureCached(Fn);
+      assert(FnInfo.hasValue());
+
+      auto &RetParamRelations = FnInfo->getRetParamRelations();
+      for (auto &Relation : RetParamRelations) {
+        auto FromVal = InstantiateInterfaceIndex(Relation.From.Index);
+        auto ToVal = InstantiateInterfaceIndex(Relation.To.Index);
+        if (FromVal && ToVal) {
+          auto FromLevel = Relation.From.DerefLevel;
+          auto ToLevel = Relation.To.DerefLevel;
+          InterprocEdges.push_back(
+              InterprocEdge{InterprocNode{FromVal, FromLevel},
+                            InterprocNode{ToVal, ToLevel}});
+        }
+      }
+
+      auto &RetParamAttributes = FnInfo->getRetParamAttributes();
+      for (auto &Attribute : RetParamAttributes) {
+        if (auto Val = InstantiateInterfaceIndex(Attribute.IValue.Index)) {
+          InterprocAttrs.push_back(InterprocAttr{
+              InterprocNode{Val, Attribute.IValue.DerefLevel}, Attribute.Attr});
+        }
+      }
+    }
+
+    return true;
+  }
+
+  void visitCallSite(CallSite CS) {
+    auto Inst = CS.getInstruction();
+
+    // Make sure all arguments and return value are added to the graph first
+    for (Value *V : CS.args())
+      addNode(V);
+    if (Inst->getType()->isPointerTy())
+      addNode(Inst);
+
+    // Check if Inst is a call to a library function that allocates/deallocates
+    // on the heap. Those kinds of functions do not introduce any aliases.
+    // TODO: address other common library functions such as realloc(), strdup(),
+    // etc.
+    if (isMallocLikeFn(Inst, &TLI) || isCallocLikeFn(Inst, &TLI) ||
+        isFreeCall(Inst, &TLI))
+      return;
+
+    // TODO: Add support for noalias args/all the other fun function attributes
+    // that we can tack on.
+    SmallVector<Function *, 4> Targets;
+    if (getPossibleTargets(CS, Targets))
+      if (tryInterproceduralAnalysis(CS, Targets))
+        return;
+
+    // Because the function is opaque, we need to note that anything
+    // could have happened to the arguments (unless the function is marked
+    // readonly or readnone), and that the result could alias just about
+    // anything, too (unless the result is marked noalias).
+    if (!CS.onlyReadsMemory())
+      for (Value *V : CS.args()) {
+        if (V->getType()->isPointerTy())
+          Escapes.insert(V);
+      }
+
+    if (Inst->getType()->isPointerTy()) {
+      auto *Fn = CS.getCalledFunction();
+      if (Fn == nullptr || !Fn->doesNotAlias(0))
+        Graph.addAttr(Inst, AttrUnknown);
+    }
+  }
+
+  /// Because vectors/aggregates are immutable and unaddressable, there's
+  /// nothing we can do to coax a value out of them, other than calling
+  /// Extract{Element,Value}. We can effectively treat them as pointers to
+  /// arbitrary memory locations we can store in and load from.
+  void visitExtractElementInst(ExtractElementInst &Inst) {
+    auto *Ptr = Inst.getVectorOperand();
+    auto *Val = &Inst;
+    addEdge(Val, Ptr, EdgeType::Reference);
+  }
+
+  void visitInsertElementInst(InsertElementInst &Inst) {
+    auto *Vec = Inst.getOperand(0);
+    auto *Val = Inst.getOperand(1);
+    addEdge(Vec, &Inst, EdgeType::Assign);
+    addEdge(&Inst, Val, EdgeType::Dereference);
+  }
+
+  void visitLandingPadInst(LandingPadInst &Inst) {
+    // Exceptions come from "nowhere", from our analysis' perspective.
+    // So we place the instruction its own group, noting that said group may
+    // alias externals
+    addNodeWithAttr(&Inst, AttrUnknown);
+  }
+
+  void visitInsertValueInst(InsertValueInst &Inst) {
+    auto *Agg = Inst.getOperand(0);
+    auto *Val = Inst.getOperand(1);
+    addEdge(Agg, &Inst, EdgeType::Assign);
+    addEdge(&Inst, Val, EdgeType::Dereference);
+  }
+
+  void visitExtractValueInst(ExtractValueInst &Inst) {
+    auto *Ptr = Inst.getAggregateOperand();
+    addEdge(&Inst, Ptr, EdgeType::Reference);
+  }
+
+  void visitShuffleVectorInst(ShuffleVectorInst &Inst) {
+    auto *From1 = Inst.getOperand(0);
+    auto *From2 = Inst.getOperand(1);
+    addEdge(From1, &Inst, EdgeType::Assign);
+    addEdge(From2, &Inst, EdgeType::Assign);
+  }
+
+  void visitConstantExpr(ConstantExpr *CE) {
+    switch (CE->getOpcode()) {
+    default:
+      llvm_unreachable("Unknown instruction type encountered!");
+// Build the switch statement using the Instruction.def file.
+#define HANDLE_INST(NUM, OPCODE, CLASS)                                        \
+  case Instruction::OPCODE:                                                    \
+    visit##OPCODE(*(CLASS *)CE);                                               \
+    break;
+#include "llvm/IR/Instruction.def"
+    }
+  }
+};
+
+class CFLGraphBuilder {
+  // Input of the builder
+  CFLSteensAAResult &Analysis;
+  const TargetLibraryInfo &TLI;
+
+  // Output of the builder
+  CFLGraph Graph;
+  SmallVector<Value *, 4> ReturnedValues;
+
+  // Auxiliary structures used by the builder
+  SmallPtrSet<Value *, 8> ExternalValues;
+  SmallPtrSet<Value *, 8> EscapedValues;
+  SmallVector<InterprocEdge, 8> InterprocEdges;
+  SmallVector<InterprocAttr, 8> InterprocAttrs;
+
+  // Helper functions
+
+  // Determines whether or not we an instruction is useless to us (e.g.
+  // FenceInst)
+  static bool hasUsefulEdges(Instruction *Inst) {
+    bool IsNonInvokeRetTerminator = isa<TerminatorInst>(Inst) &&
+                                    !isa<InvokeInst>(Inst) &&
+                                    !isa<ReturnInst>(Inst);
+    return !isa<CmpInst>(Inst) && !isa<FenceInst>(Inst) &&
+           !IsNonInvokeRetTerminator;
+  }
+
+  void addArgumentToGraph(Argument &Arg) {
+    if (Arg.getType()->isPointerTy()) {
+      Graph.addNode(&Arg);
+      ExternalValues.insert(&Arg);
+    }
+  }
+
+  // Given an Instruction, this will add it to the graph, along with any
+  // Instructions that are potentially only available from said Instruction
+  // For example, given the following line:
+  //   %0 = load i16* getelementptr ([1 x i16]* @a, 0, 0), align 2
+  // addInstructionToGraph would add both the `load` and `getelementptr`
+  // instructions to the graph appropriately.
+  void addInstructionToGraph(Instruction &Inst) {
+    if (!hasUsefulEdges(&Inst))
+      return;
+
+    GetEdgesVisitor(Analysis, TLI, Graph, ReturnedValues, ExternalValues,
+                    EscapedValues, InterprocEdges, InterprocAttrs)
+        .visit(Inst);
+  }
+
+  // Builds the graph needed for constructing the StratifiedSets for the given
+  // function
+  void buildGraphFrom(Function &Fn) {
+    for (auto &Bb : Fn.getBasicBlockList())
+      for (auto &Inst : Bb.getInstList())
+        addInstructionToGraph(Inst);
+
+    for (auto &Arg : Fn.args())
+      addArgumentToGraph(Arg);
+  }
+
+public:
+  CFLGraphBuilder(CFLSteensAAResult &Analysis, const TargetLibraryInfo &TLI,
+                  Function &Fn)
+      : Analysis(Analysis), TLI(TLI) {
+    buildGraphFrom(Fn);
+  }
+
+  const CFLGraph &getCFLGraph() const { return Graph; }
+  const SmallVector<Value *, 4> &getReturnValues() const {
+    return ReturnedValues;
+  }
+  const SmallPtrSet<Value *, 8> &getExternalValues() const {
+    return ExternalValues;
+  }
+  const SmallPtrSet<Value *, 8> &getEscapedValues() const {
+    return EscapedValues;
+  }
+  const SmallVector<InterprocEdge, 8> &getInterprocEdges() const {
+    return InterprocEdges;
+  }
+  const SmallVector<InterprocAttr, 8> &getInterprocAttrs() const {
+    return InterprocAttrs;
+  }
+};
+}
+
+//===----------------------------------------------------------------------===//
+// Function declarations that require types defined in the namespace above
+//===----------------------------------------------------------------------===//
+
+/// Given a StratifiedAttrs, returns true if it marks the corresponding values
+/// as globals or arguments
+static bool isGlobalOrArgAttr(StratifiedAttrs Attr);
+
+/// Given a StratifiedAttrs, returns true if the corresponding values come from
+/// an unknown source (such as opaque memory or an integer cast)
+static bool isUnknownAttr(StratifiedAttrs Attr);
+
+/// Given an argument number, returns the appropriate StratifiedAttr to set.
+static StratifiedAttrs argNumberToAttr(unsigned ArgNum);
+
+/// Given a Value, potentially return which StratifiedAttr it maps to.
+static Optional<StratifiedAttrs> valueToAttr(Value *Val);
+
+/// Gets the "Level" that one should travel in StratifiedSets
+/// given an EdgeType.
+static Level directionOfEdgeType(EdgeType);
+
+/// Determines whether it would be pointless to add the given Value to our sets.
+static bool canSkipAddingToSets(Value *Val);
+
+static Optional<Function *> parentFunctionOfValue(Value *Val) {
+  if (auto *Inst = dyn_cast<Instruction>(Val)) {
+    auto *Bb = Inst->getParent();
+    return Bb->getParent();
+  }
+
+  if (auto *Arg = dyn_cast<Argument>(Val))
+    return Arg->getParent();
+  return None;
+}
+
+static bool getPossibleTargets(CallSite CS,
+                               SmallVectorImpl<Function *> &Output) {
+  if (auto *Fn = CS.getCalledFunction()) {
+    Output.push_back(Fn);
+    return true;
+  }
+
+  // TODO: If the call is indirect, we might be able to enumerate all potential
+  // targets of the call and return them, rather than just failing.
+  return false;
+}
+
+static bool isGlobalOrArgAttr(StratifiedAttrs Attr) {
+  return Attr.reset(AttrEscapedIndex)
+      .reset(AttrUnknownIndex)
+      .reset(AttrCallerIndex)
+      .any();
+}
+
+static bool isUnknownAttr(StratifiedAttrs Attr) {
+  return Attr.test(AttrUnknownIndex) || Attr.test(AttrCallerIndex);
+}
+
+static Optional<StratifiedAttrs> valueToAttr(Value *Val) {
+  if (isa<GlobalValue>(Val))
+    return StratifiedAttrs(AttrGlobal);
+
+  if (auto *Arg = dyn_cast<Argument>(Val))
+    // Only pointer arguments should have the argument attribute,
+    // because things can't escape through scalars without us seeing a
+    // cast, and thus, interaction with them doesn't matter.
+    if (!Arg->hasNoAliasAttr() && Arg->getType()->isPointerTy())
+      return argNumberToAttr(Arg->getArgNo());
+  return None;
+}
+
+static StratifiedAttrs argNumberToAttr(unsigned ArgNum) {
+  if (ArgNum >= AttrMaxNumArgs)
+    return AttrUnknown;
+  // N.B. MSVC complains if we use `1U` here, since StratifiedAttrs' ctor takes
+  // an unsigned long long.
+  return StratifiedAttrs(1ULL << (ArgNum + AttrFirstArgIndex));
+}
+
+static Level directionOfEdgeType(EdgeType Weight) {
+  switch (Weight) {
+  case EdgeType::Reference:
+    return Level::Above;
+  case EdgeType::Dereference:
+    return Level::Below;
+  case EdgeType::Assign:
+    return Level::Same;
+  }
+  llvm_unreachable("Incomplete switch coverage");
+}
+
+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)) {
+    // 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) ||
+                               isa<ConstantAggregate>(Val);
+    return !CanStoreMutableData;
+  }
+
+  return false;
+}
+
+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.
+  if (Fn.arg_size() > MaxSupportedArgsInSummary)
+    return;
+
+  DenseMap<StratifiedIndex, InterfaceValue> InterfaceMap;
+
+  // Our intention here is to record all InterfaceValues that share the same
+  // StratifiedIndex in RetParamRelations. For each valid InterfaceValue, we
+  // have its StratifiedIndex scanned here and check if the index is presented
+  // in InterfaceMap: if it is not, we add the correspondence to the map;
+  // otherwise, an aliasing relation is found and we add it to
+  // RetParamRelations.
+
+  auto AddToRetParamRelations = [&](unsigned InterfaceIndex,
+                                    StratifiedIndex SetIndex) {
+    unsigned Level = 0;
+    while (true) {
+      InterfaceValue CurrValue{InterfaceIndex, Level};
+
+      auto Itr = InterfaceMap.find(SetIndex);
+      if (Itr != InterfaceMap.end()) {
+        if (CurrValue != Itr->second)
+          RetParamRelations.push_back(ExternalRelation{CurrValue, Itr->second});
+        break;
+      }
+
+      auto &Link = Sets.getLink(SetIndex);
+      InterfaceMap.insert(std::make_pair(SetIndex, CurrValue));
+      auto ExternalAttrs = Link.Attrs & StratifiedAttrs(ExternalAttrMask);
+      if (ExternalAttrs.any())
+        RetParamAttributes.push_back(
+            ExternalAttribute{CurrValue, ExternalAttrs});
+
+      if (!Link.hasBelow())
+        break;
+
+      ++Level;
+      SetIndex = Link.Below;
+    }
+  };
+
+  // Populate RetParamRelations for return values
+  for (auto *RetVal : RetVals) {
+    assert(RetVal != nullptr);
+    assert(RetVal->getType()->isPointerTy());
+    auto RetInfo = Sets.find(RetVal);
+    if (RetInfo.hasValue())
+      AddToRetParamRelations(0, RetInfo->Index);
+  }
+
+  // Populate RetParamRelations for parameters
+  unsigned I = 0;
+  for (auto &Param : Fn.args()) {
+    if (Param.getType()->isPointerTy()) {
+      auto ParamInfo = Sets.find(&Param);
+      if (ParamInfo.hasValue())
+        AddToRetParamRelations(I + 1, ParamInfo->Index);
+    }
+    ++I;
+  }
+}
+
+// Builds the graph + StratifiedSets for a function.
+CFLSteensAAResult::FunctionInfo CFLSteensAAResult::buildSetsFrom(Function *Fn) {
+  CFLGraphBuilder GraphBuilder(*this, TLI, *Fn);
+  StratifiedSetsBuilder<Value *> SetBuilder;
+
+  auto &Graph = GraphBuilder.getCFLGraph();
+  SmallVector<Value *, 16> Worklist;
+  for (auto Node : Graph.nodes())
+    Worklist.push_back(Node);
+
+  while (!Worklist.empty()) {
+    auto *CurValue = Worklist.pop_back_val();
+    SetBuilder.add(CurValue);
+    if (canSkipAddingToSets(CurValue))
+      continue;
+
+    auto Attr = Graph.attrFor(CurValue);
+    SetBuilder.noteAttributes(CurValue, Attr);
+
+    for (const auto &Edge : Graph.edgesFor(CurValue)) {
+      auto Label = Edge.Type;
+      auto *OtherValue = Edge.Other;
+
+      if (canSkipAddingToSets(OtherValue))
+        continue;
+
+      bool Added;
+      switch (directionOfEdgeType(Label)) {
+      case Level::Above:
+        Added = SetBuilder.addAbove(CurValue, OtherValue);
+        break;
+      case Level::Below:
+        Added = SetBuilder.addBelow(CurValue, OtherValue);
+        break;
+      case Level::Same:
+        Added = SetBuilder.addWith(CurValue, OtherValue);
+        break;
+      }
+
+      if (Added)
+        Worklist.push_back(OtherValue);
+    }
+  }
+
+  // Special handling for globals and arguments
+  for (auto *External : GraphBuilder.getExternalValues()) {
+    SetBuilder.add(External);
+    auto Attr = valueToAttr(External);
+    if (Attr.hasValue()) {
+      SetBuilder.noteAttributes(External, *Attr);
+      if (*Attr == AttrGlobal)
+        SetBuilder.addAttributesBelow(External, 1, AttrUnknown);
+      else
+        SetBuilder.addAttributesBelow(External, 1, AttrCaller);
+    }
+  }
+
+  // Special handling for interprocedural aliases
+  for (auto &Edge : GraphBuilder.getInterprocEdges()) {
+    auto FromVal = Edge.From.Val;
+    auto ToVal = Edge.To.Val;
+    SetBuilder.add(FromVal);
+    SetBuilder.add(ToVal);
+    SetBuilder.addBelowWith(FromVal, Edge.From.DerefLevel, ToVal,
+                            Edge.To.DerefLevel);
+  }
+
+  // Special handling for interprocedural attributes
+  for (auto &IPAttr : GraphBuilder.getInterprocAttrs()) {
+    auto Val = IPAttr.Node.Val;
+    SetBuilder.add(Val);
+    SetBuilder.addAttributesBelow(Val, IPAttr.Node.DerefLevel, IPAttr.Attr);
+  }
+
+  // Special handling for opaque external functions
+  for (auto *Escape : GraphBuilder.getEscapedValues()) {
+    SetBuilder.add(Escape);
+    SetBuilder.noteAttributes(Escape, AttrEscaped);
+    SetBuilder.addAttributesBelow(Escape, 1, AttrUnknown);
+  }
+
+  return FunctionInfo(*Fn, GraphBuilder.getReturnValues(), SetBuilder.build());
+}
+
+void CFLSteensAAResult::scan(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 = buildSetsFrom(Fn);
+  Cache[Fn] = std::move(FunInfo);
+
+  Handles.push_front(FunctionHandle(Fn, this));
+}
+
+void CFLSteensAAResult::evict(Function *Fn) { Cache.erase(Fn); }
+
+/// Ensures that the given function is available in the cache, and returns the
+/// entry.
+const Optional<CFLSteensAAResult::FunctionInfo> &
+CFLSteensAAResult::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;
+}
+
+AliasResult CFLSteensAAResult::query(const MemoryLocation &LocA,
+                                     const MemoryLocation &LocB) {
+  auto *ValA = const_cast<Value *>(LocA.Ptr);
+  auto *ValB = const_cast<Value *>(LocB.Ptr);
+
+  if (!ValA->getType()->isPointerTy() || !ValB->getType()->isPointerTy())
+    return NoAlias;
+
+  Function *Fn = nullptr;
+  auto MaybeFnA = parentFunctionOfValue(ValA);
+  auto MaybeFnB = parentFunctionOfValue(ValB);
+  if (!MaybeFnA.hasValue() && !MaybeFnB.hasValue()) {
+    // The only times this is known to happen are when globals + InlineAsm are
+    // involved
+    DEBUG(dbgs()
+          << "CFLSteensAA: could not extract parent function information.\n");
+    return MayAlias;
+  }
+
+  if (MaybeFnA.hasValue()) {
+    Fn = *MaybeFnA;
+    assert((!MaybeFnB.hasValue() || *MaybeFnB == *MaybeFnA) &&
+           "Interprocedural queries not supported");
+  } else {
+    Fn = *MaybeFnB;
+  }
+
+  assert(Fn != nullptr);
+  auto &MaybeInfo = ensureCached(Fn);
+  assert(MaybeInfo.hasValue());
+
+  auto &Sets = MaybeInfo->getStratifiedSets();
+  auto MaybeA = Sets.find(ValA);
+  if (!MaybeA.hasValue())
+    return MayAlias;
+
+  auto MaybeB = Sets.find(ValB);
+  if (!MaybeB.hasValue())
+    return MayAlias;
+
+  auto SetA = *MaybeA;
+  auto SetB = *MaybeB;
+  auto AttrsA = Sets.getLink(SetA.Index).Attrs;
+  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 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:
+  // - Non-local values may alias each other
+  // - AttrNone values do not alias any non-local values
+  // - AttrEscaped do not alias globals/arguments, but they may alias
+  // AttrUnknown values
+  if (SetA.Index == SetB.Index)
+    return MayAlias;
+  if (AttrsA.none() || AttrsB.none())
+    return NoAlias;
+  if (isUnknownAttr(AttrsA) || isUnknownAttr(AttrsB))
+    return MayAlias;
+  if (isGlobalOrArgAttr(AttrsA) && isGlobalOrArgAttr(AttrsB))
+    return MayAlias;
+  return NoAlias;
+}
+
+ModRefInfo CFLSteensAAResult::getArgModRefInfo(ImmutableCallSite CS,
+                                               unsigned ArgIdx) {
+  if (auto CalledFunc = CS.getCalledFunction()) {
+    auto &MaybeInfo = ensureCached(const_cast<Function *>(CalledFunc));
+    if (!MaybeInfo.hasValue())
+      return MRI_ModRef;
+    auto &RetParamAttributes = MaybeInfo->getRetParamAttributes();
+    auto &RetParamRelations = MaybeInfo->getRetParamRelations();
+
+    bool ArgAttributeIsWritten =
+        std::any_of(RetParamAttributes.begin(), RetParamAttributes.end(),
+                    [ArgIdx](const ExternalAttribute &ExtAttr) {
+                      return ExtAttr.IValue.Index == ArgIdx + 1;
+                    });
+    bool ArgIsAccessed =
+        std::any_of(RetParamRelations.begin(), RetParamRelations.end(),
+                    [ArgIdx](const ExternalRelation &ExtRelation) {
+                      return ExtRelation.To.Index == ArgIdx + 1 ||
+                             ExtRelation.From.Index == ArgIdx + 1;
+                    });
+
+    return (!ArgIsAccessed && !ArgAttributeIsWritten) ? MRI_NoModRef
+                                                      : MRI_ModRef;
+  }
+
+  return MRI_ModRef;
+}
+
+FunctionModRefBehavior
+CFLSteensAAResult::getModRefBehavior(ImmutableCallSite CS) {
+  // If we know the callee, try analyzing it
+  if (auto CalledFunc = CS.getCalledFunction())
+    return getModRefBehavior(CalledFunc);
+
+  // Otherwise, be conservative
+  return FMRB_UnknownModRefBehavior;
+}
+
+FunctionModRefBehavior CFLSteensAAResult::getModRefBehavior(const Function *F) {
+  assert(F != nullptr);
+
+  // TODO: Remove the const_cast
+  auto &MaybeInfo = ensureCached(const_cast<Function *>(F));
+  if (!MaybeInfo.hasValue())
+    return FMRB_UnknownModRefBehavior;
+  auto &RetParamAttributes = MaybeInfo->getRetParamAttributes();
+  auto &RetParamRelations = MaybeInfo->getRetParamRelations();
+
+  // First, if any argument is marked Escpaed, Unknown or Global, anything may
+  // happen to them and thus we can't draw any conclusion.
+  if (!RetParamAttributes.empty())
+    return FMRB_UnknownModRefBehavior;
+
+  // Currently we don't (and can't) distinguish reads from writes in
+  // RetParamRelations. All we can say is whether there may be memory access or
+  // not.
+  if (RetParamRelations.empty())
+    return FMRB_DoesNotAccessMemory;
+
+  // Check if something beyond argmem gets touched.
+  bool AccessArgMemoryOnly =
+      std::all_of(RetParamRelations.begin(), RetParamRelations.end(),
+                  [](const ExternalRelation &ExtRelation) {
+                    // Both DerefLevels has to be 0, since we don't know which
+                    // one is a read and which is a write.
+                    return ExtRelation.From.DerefLevel == 0 &&
+                           ExtRelation.To.DerefLevel == 0;
+                  });
+  return AccessArgMemoryOnly ? FMRB_OnlyAccessesArgumentPointees
+                             : FMRB_UnknownModRefBehavior;
+}
+
+char CFLSteensAA::PassID;
+
+CFLSteensAAResult CFLSteensAA::run(Function &F, AnalysisManager<Function> &AM) {
+  return CFLSteensAAResult(AM.getResult<TargetLibraryAnalysis>(F));
+}
+
+char CFLSteensAAWrapperPass::ID = 0;
+INITIALIZE_PASS(CFLSteensAAWrapperPass, "cfl-steens-aa",
+                "Unification-Based CFL Alias Analysis", false, true)
+
+ImmutablePass *llvm::createCFLSteensAAWrapperPass() {
+  return new CFLSteensAAWrapperPass();
+}
+
+CFLSteensAAWrapperPass::CFLSteensAAWrapperPass() : ImmutablePass(ID) {
+  initializeCFLSteensAAWrapperPassPass(*PassRegistry::getPassRegistry());
+}
+
+void CFLSteensAAWrapperPass::initializePass() {
+  auto &TLIWP = getAnalysis<TargetLibraryInfoWrapperPass>();
+  Result.reset(new CFLSteensAAResult(TLIWP.getTLI()));
+}
+
+void CFLSteensAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
+  AU.setPreservesAll();
+  AU.addRequired<TargetLibraryInfoWrapperPass>();
+}

llvm/trunk/lib/Analysis/CMakeLists.txt

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

llvm/trunk/lib/CodeGen/TargetPassConfig.cpp

 // This file defines interfaces to access the target independent code
 // generation passes provided by the LLVM backend.
 //
 //===---------------------------------------------------------------------===//
 
 #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"
 #include "llvm/Analysis/TypeBasedAliasAnalysis.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/RegAllocRegistry.h"
 #include "llvm/CodeGen/RegisterUsageInfo.h"
 #include "llvm/IR/IRPrintingPasses.h"

 // insert a PostRA scheduling pass wherever it wants.
 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"));
 
-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 "
                                "to reduce load/store at procedure calls."));
 
 /// 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.

 void TargetPassConfig::addVerifyPass(const std::string &Banner) {
   if (VerifyMachineCode)
     PM->add(createMachineVerifierPass(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());
 
   // Before running any passes, run the verifier to determine if the input
   // coming from the front-end and/or optimizer is valid.
   if (!DisableVerify)
     addPass(createVerifierPass());

llvm/trunk/lib/Passes/PassBuilder.cpp

 #include "llvm/ADT/StringSwitch.h"
 #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/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"
 #include "llvm/Analysis/DependenceAnalysis.h"
 #include "llvm/Analysis/DominanceFrontier.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/LazyCallGraph.h"
 #include "llvm/Analysis/LazyValueInfo.h"
bool PassBuilder::parsePassPipeline(ModulePassManager &MPM,
   // If this looks like a CGSCC pass, parse the whole thing as a CGSCC
   // pipeline.
   if (PipelineText.startswith("cgscc(") || isCGSCCPassName(FirstName)) {
     CGSCCPassManager CGPM(DebugLogging);
     if (!parseCGSCCPassPipeline(CGPM, PipelineText, VerifyEachPass,
                                 DebugLogging) ||
         !PipelineText.empty())
       return false;
-    MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM), DebugLogging));
+    MPM.addPass(
+        createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM), DebugLogging));
     return true;
   }
 
   // Similarly, if this looks like a Function pass, parse the whole thing as
   // a Function pipelien.
   if (PipelineText.startswith("function(") || isFunctionPassName(FirstName)) {
     FunctionPassManager FPM(DebugLogging);
     if (!parseFunctionPassPipeline(FPM, PipelineText, VerifyEachPass,

llvm/trunk/lib/Passes/PassRegistry.def

 MODULE_ANALYSIS("callgraph", CallGraphAnalysis())
 MODULE_ANALYSIS("lcg", LazyCallGraphAnalysis())
 MODULE_ANALYSIS("no-op-module", NoOpModuleAnalysis())
 MODULE_ANALYSIS("profile-summary", ProfileSummaryAnalysis())
 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())
 #undef MODULE_ALIAS_ANALYSIS
 #undef MODULE_ANALYSIS
 
 #ifndef MODULE_PASS
 #define MODULE_PASS(NAME, CREATE_PASS)
FUNCTION_ANALYSIS("targetir",
                   TM ? TM->getTargetIRAnalysis() : TargetIRAnalysis())
 FUNCTION_ANALYSIS("verify", VerifierAnalysis())
 
 #ifndef FUNCTION_ALIAS_ANALYSIS
 #define FUNCTION_ALIAS_ANALYSIS(NAME, CREATE_PASS)                             \
   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())
 #undef FUNCTION_ALIAS_ANALYSIS
 #undef FUNCTION_ANALYSIS
 
 #ifndef FUNCTION_PASS
 #define FUNCTION_PASS(NAME, CREATE_PASS)

llvm/trunk/lib/Transforms/IPO/PassManagerBuilder.cpp

 // "standard" optimization sequence suitable for languages like C and C++.
 //
 //===----------------------------------------------------------------------===//
 
 #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/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"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/TypeBasedAliasAnalysis.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/LegacyPassManager.h"
 #include "llvm/IR/ModuleSummaryIndex.h"
static cl::opt<bool> RunLoadCombine("combine-loads", cl::init(false),
                                     cl::desc("Run the load combining pass"));
 
 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"));
 
-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,
            cl::desc("Enable motion of merged load and store"));
 
 static cl::opt<bool> EnableLoopInterchange(
     "enable-loopinterchange", cl::init(false), cl::Hidden,
     cl::desc("Enable the new, experimental LoopInterchange Pass"));
if ((*GlobalExtensions)[i].first == ETy)
       (*GlobalExtensions)[i].second(*this, PM);
   for (unsigned i = 0, e = Extensions.size(); i != e; ++i)
     if (Extensions[i].first == ETy)
       Extensions[i].second(*this, PM);
 }
 
 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());
 }
 
 void PassManagerBuilder::addInstructionCombiningPass(
     legacy::PassManagerBase &PM) const {
   bool ExpensiveCombines = OptLevel > 2;
   PM.add(createInstructionCombiningPass(ExpensiveCombines));

llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/arguments-globals.ll

+; This testcase ensures that CFL AA gives conservative answers on variables
+; that involve arguments.
+; (Everything should alias everything, because args can alias globals, so the
+; aliasing sets should of args+alloca+global should be combined)
+
+; RUN: opt < %s -disable-basicaa -cfl-steens-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s
+
+; CHECK:     Function: test
+
+@g = external global i32
+
+define void @test(i1 %c, i32* %arg1, i32* %arg2) {
+  ; CHECK: 15 Total Alias Queries Performed
+  ; CHECK: 0 no alias responses
+  %A = alloca i32, align 4
+  %B = select i1 %c, i32* %arg1, i32* %arg2
+  %C = select i1 %c, i32* @g, i32* %A
+
+  ret void
+}

llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/arguments.ll

+; This testcase ensures that CFL AA gives conservative answers on variables
+; that involve arguments.
+
+; RUN: opt < %s -cfl-steens-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s
+
+; CHECK:     Function: test
+
+define void @test(i1 %c, i32* %arg1, i32* %arg2) {
+  ; CHECK: 6 Total Alias Queries Performed
+  ; CHECK: 3 no alias responses
+  %a = alloca i32, align 4
+  %b = select i1 %c, i32* %arg1, i32* %arg2
+
+  ret void
+}

llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/asm-global-bugfix.ll

+; Test case for a bug where we would crash when we were requested to report
+; whether two values that didn't belong to a function (i.e. two globals, etc)
+; aliased.
+
+; RUN: opt < %s -cfl-steens-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s
+
+@G = private unnamed_addr constant [1 x i8] c"\00", align 1
+
+; CHECK: Function: test_no_crash
+; CHECK: 0 no alias responses
+define void @test_no_crash() #0 {
+entry:
+  call i8* asm "nop", "=r,r"(
+       i8* getelementptr inbounds ([1 x i8], [1 x i8]* @G, i64 0, i64 0))
+  ret void
+}

llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/attr-escape.ll

+; This testcase ensures that CFL AA handles escaped values no more conservative than it should
+
+; RUN: opt < %s -disable-basicaa -cfl-steens-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+; RUN: opt < %s -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+
+; CHECK-LABEL: Function: test_local
+; CHECK: NoAlias: i32* %a, i32* %b
+; CHECK: MayAlias: i32* %a, i32* %aAlias
+; CHECK: NoAlias: i32* %aAlias, i32* %b
+define void @test_local() {
+  %a = alloca i32, align 4
+  %b = alloca i32, align 4
+  %aint = ptrtoint i32* %a to i64
+  %aAlias = inttoptr i64 %aint to i32*
+  ret void
+}
+
+; CHECK-LABEL: Function: test_global_param
+; CHECK: NoAlias: i32* %a, i32** %x
+; CHECK: MayAlias: i32* %a, i32* %xload
+; CHECK: MayAlias: i32* %a, i32* %gload
+; CHECK: MayAlias: i32* %gload, i32* %xload
+; CHECK: MayAlias: i32** %x, i32** @ext_global
+; CHECK: NoAlias: i32* %a, i32** @ext_global
+@ext_global = external global i32*
+define void @test_global_param(i32** %x) {
+  %a = alloca i32, align 4
+  %aint = ptrtoint i32* %a to i64
+  %xload = load i32*, i32** %x
+  %gload = load i32*, i32** @ext_global
+  ret void
+}
+
+declare void @external_func(i32**)
+; CHECK-LABEL: Function: test_external_call
+; CHECK: NoAlias: i32* %b, i32* %x
+; CHECK: NoAlias: i32* %b, i32** %a
+; CHECK: MayAlias: i32* %c, i32* %x
+; CHECK: MayAlias: i32* %c, i32** %a
+; CHECK: NoAlias: i32* %b, i32* %c
+define void @test_external_call(i32* %x) {
+  %a = alloca i32*, align 8
+  %b = alloca i32, align 4
+  call void @external_func(i32** %a)
+  %c = load i32*, i32** %a
+  ret void
+}
+
+declare void @external_func_readonly(i32**) readonly
+; CHECK-LABEL: Function: test_external_call_func_readonly
+; CHECK: MayAlias: i32* %c, i32* %x
+; CHECK: NoAlias: i32* %c, i32** %a
+define void @test_external_call_func_readonly(i32* %x) {
+  %a = alloca i32*, align 8
+  %b = alloca i32, align 4
+  store i32* %x, i32** %a, align 4
+  call void @external_func_readonly(i32** %a)
+  %c = load i32*, i32** %a
+  ret void
+}
+
+; CHECK-LABEL: Function: test_external_call_callsite_readonly
+; CHECK: MayAlias: i32* %c, i32* %x
+; CHECK: NoAlias: i32* %c, i32** %a
+define void @test_external_call_callsite_readonly(i32* %x) {
+  %a = alloca i32*, align 8
+  %b = alloca i32, align 4
+  store i32* %x, i32** %a, align 4
+  call void @external_func(i32** %a) readonly
+  %c = load i32*, i32** %a
+  ret void
+}
+
+declare i32* @external_func_normal_return(i32*)
+; CHECK-LABEL: Function: test_external_call_normal_return
+; CHECK: MayAlias: i32* %c, i32* %x
+; CHECK: MayAlias: i32* %a, i32* %c
+define void @test_external_call_normal_return(i32* %x) {
+  %a = alloca i32, align 8
+  %b = alloca i32, align 4
+  %c = call i32* @external_func_normal_return(i32* %a)
+  ret void
+}
+
+declare noalias i32* @external_func_noalias_return(i32*)
+; CHECK-LABEL: Function: test_external_call_noalias_return
+; CHECK: NoAlias: i32* %c, i32* %x
+; CHECK: NoAlias: i32* %a, i32* %c
+define void @test_external_call_noalias_return(i32* %x) {
+  %a = alloca i32, align 8
+  %b = alloca i32, align 4
+  %c = call i32* @external_func_noalias_return(i32* %a)
+  ret void
+}

llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/basic-interproc.ll

+; This testcase ensures that CFL AA won't be too conservative when trying to do
+; interprocedural analysis on simple callee
+
+; RUN: opt < %s -disable-basicaa -cfl-steens-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+; RUN: opt < %s -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+
+; CHECK-LABEL: Function: noop_callee
+; CHECK: MayAlias: i32* %arg1, i32* %arg2
+define void @noop_callee(i32* %arg1, i32* %arg2) {
+  store i32 0, i32* %arg1
+  store i32 0, i32* %arg2
+  ret void
+}
+; CHECK-LABEL: Function: test_noop
+; CHECK: NoAlias: i32* %a, i32* %b
+define void @test_noop() {
+  %a = alloca i32, align 4
+  %b = alloca i32, align 4
+  call void @noop_callee(i32* %a, i32* %b)
+
+  ret void
+}

llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/branch-alias.ll

+; Makes sure that we give up on some pathological cases with inttoptr/ptrtoint
+;
+; @ptr_test was generated from the following C code:
+;  void ptr_test() {
+;    int* A;
+;    unsigned long RefCopy = 0;
+;    for (int i = 0; i < 8*sizeof(&A); ++i) {
+;      if ((unsigned long)&A & (1UL << i))
+;        RefCopy |= 1UL << i;
+;    }
+;
+;    int** AliasA1 = (int**)RefCopy;
+;    int* ShouldAliasA = *AliasA1;
+;  }
+
+; RUN: opt < %s -disable-basicaa -cfl-steens-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s
+
+; CHECK: Function: ptr_test
+define void @ptr_test() #0 {
+  ; CHECK: MayAlias: i32** %A, i32** %ShouldAliasA
+  ; CHECK-NOT: %AliasA1
+entry:
+  %A = alloca i32*, align 8
+  %RefCopy = alloca i64, align 8
+  %i = alloca i32, align 4
+  %AliasA1 = alloca i32**, align 8
+  %ShouldAliasA = alloca i32*, align 8
+  store i64 0, i64* %RefCopy, align 8
+  store i32 0, i32* %i, align 4
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %0 = load i32, i32* %i, align 4
+  %conv = sext i32 %0 to i64
+  %cmp = icmp ult i64 %conv, 64
+  br i1 %cmp, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %1 = ptrtoint i32** %A to i64
+  %2 = load i32, i32* %i, align 4
+  %sh_prom = zext i32 %2 to i64
+  %shl = shl i64 1, %sh_prom
+  %and = and i64 %1, %shl
+  %tobool = icmp ne i64 %and, 0
+  br i1 %tobool, label %if.then, label %if.end
+
+if.then:                                          ; preds = %for.body
+  %3 = load i32, i32* %i, align 4
+  %sh_prom2 = zext i32 %3 to i64
+  %shl3 = shl i64 1, %sh_prom2
+  %4 = load i64, i64* %RefCopy, align 8
+  %or = or i64 %4, %shl3
+  store i64 %or, i64* %RefCopy, align 8
+  br label %if.end
+
+if.end:                                           ; preds = %if.then, %for.body
+  br label %for.inc
+
+for.inc:                                          ; preds = %if.end
+  %5 = load i32, i32* %i, align 4
+  %inc = add nsw i32 %5, 1
+  store i32 %inc, i32* %i, align 4
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  %6 = load i64, i64* %RefCopy, align 8
+  %7 = inttoptr i64 %6 to i32**
+  store i32** %7, i32*** %AliasA1, align 8
+  %8 = load i32**, i32*** %AliasA1, align 8
+  %9 = load i32*, i32** %8, align 8
+  store i32* %9, i32** %ShouldAliasA, align 8
+  ret void
+}

llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/const-expr-gep.ll

+; This testcase consists of alias relations which should be completely
+; resolvable by cfl-steens-aa, but require analysis of getelementptr constant exprs.
+; Derived from BasicAA/2003-12-11-ConstExprGEP.ll
+
+; RUN: opt < %s -disable-basicaa -cfl-steens-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s
+
+%T = type { i32, [10 x i8] }
+
+@G = external global %T
+@G2 = external global %T
+
+; TODO: Quite a few of these are MayAlias because we don't yet consider
+; constant offsets in CFLSteensAA. If we start doing so, then we'll need to
+; change these test cases
+
+; CHECK:     Function: test
+; CHECK:     MayAlias: i32* %D, i32* %F
+; CHECK:     MayAlias: i32* %D, i8* %X
+; CHECK:     MayAlias: i32* %F, i8* %X
+define void @test() {
+  %D = getelementptr %T, %T* @G, i64 0, i32 0
+  %F = getelementptr i32, i32* getelementptr (%T, %T* @G, i64 0, i32 0), i64 0
+  %X = getelementptr [10 x i8], [10 x i8]* getelementptr (%T, %T* @G, i64 0, i32 1), i64 0, i64 5
+
+  ret void
+}
+
+; CHECK:     Function: simplecheck
+; CHECK:     MayAlias: i32* %F, i32* %arg0
+; CHECK:     MayAlias: i32* %H, i32* %arg0
+; CHECK:     MayAlias: i32* %F, i32* %H
+define void @simplecheck(i32* %arg0) {
+  %F = getelementptr i32, i32* getelementptr (%T, %T* @G, i64 0, i32 0), i64 0
+  %H = getelementptr %T, %T* @G2, i64 0, i32 0
+
+  ret void
+}
+
+; Ensure that CFLSteensAA properly identifies and handles escaping variables (i.e.
+; globals) in nested ConstantExprs
+
+; CHECK:      Function: checkNesting
+; CHECK:      MayAlias: i32* %A, i32* %arg0
+
+%NestedT = type { [1 x [1 x i32]] }
+@NT = external global %NestedT
+
+define void @checkNesting(i32* %arg0) {
+  %A = getelementptr [1 x i32],
+         [1 x i32]* getelementptr
+           ([1 x [1 x i32]], [1 x [1 x i32]]* getelementptr (%NestedT, %NestedT* @NT, i64 0, i32 0),
+           i64 0,
+           i32 0),
+         i64 0,
+         i32 0
+  ret void
+}

llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/constant-over-index.ll

+; RUN: opt < %s -cfl-steens-aa -aa-eval -print-all-alias-modref-info 2>&1 | FileCheck %s
+
+; CFL AA currently returns PartialAlias, BasicAA returns MayAlias, both seem
+; acceptable (although we might decide that we don't want PartialAlias, and if
+; so, we should update this test case accordingly).
+; CHECK: {{PartialAlias|MayAlias}}: double* %p.0.i.0, double* %p3
+
+; %p3 is equal to %p.0.i.0 on the second iteration of the loop,
+; so MayAlias is needed.
+
+define void @foo([3 x [3 x double]]* noalias %p) {
+entry:
+  %p3 = getelementptr [3 x [3 x double]], [3 x [3 x double]]* %p, i64 0, i64 0, i64 3
+  br label %loop
+
+loop:
+  %i = phi i64 [ 0, %entry ], [ %i.next, %loop ]
+
+  %p.0.i.0 = getelementptr [3 x [3 x double]], [3 x [3 x double]]* %p, i64 0, i64 %i, i64 0
+
+  store volatile double 0.0, double* %p3
+  store volatile double 0.1, double* %p.0.i.0
+
+  %i.next = add i64 %i, 1
+  %cmp = icmp slt i64 %i.next, 3
+  br i1 %cmp, label %loop, label %exit
+
+exit:
+  ret void
+}

llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/empty.ll

+; RUN: opt < %s -cfl-steens-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+
+target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"
+
+; CHECK:      Function: foo:
+; CHECK-NEXT:   NoAlias: {}* %p, {}* %q
+
+define void @foo({}* %p, {}* %q) {
+  store {} {}, {}* %p
+  store {} {}, {}* %q
+  ret void
+}

llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/full-store-partial-alias.ll

+; RUN: opt -S -disable-basicaa -tbaa -cfl-steens-aa -gvn < %s | FileCheck -check-prefix=CFLSteensAA %s
+; RUN: opt -S -disable-basicaa -tbaa -gvn < %s | FileCheck %s
+; Adapted from the BasicAA full-store-partial-alias.ll test.
+
+; CFL AA could notice that the store stores to the entire %u object,
+; so the %tmp5 load is PartialAlias with the store and suppress TBAA.
+; FIXME: However, right now, CFLSteensAA cannot prove PartialAlias here
+; Without CFL AA, TBAA should say that %tmp5 is NoAlias with the store.
+
+target datalayout = "e-p:64:64:64"
+
+%union.anon = type { double }
+
+@u = global %union.anon { double -2.500000e-01 }, align 8
+@endianness_test = global i64 1, align 8
+
+define i32 @signbit(double %x) nounwind {
+; FIXME: This would be ret i32 %tmp5.lobit if CFLSteensAA could prove PartialAlias
+; CFLSteensAA: ret i32 0
+; CHECK: ret i32 0
+entry:
+  %u = alloca %union.anon, align 8
+  %tmp9 = getelementptr inbounds %union.anon, %union.anon* %u, i64 0, i32 0
+  store double %x, double* %tmp9, align 8, !tbaa !0
+  %tmp2 = load i32, i32* bitcast (i64* @endianness_test to i32*), align 8, !tbaa !3
+  %idxprom = sext i32 %tmp2 to i64
+  %tmp4 = bitcast %union.anon* %u to [2 x i32]*
+  %arrayidx = getelementptr inbounds [2 x i32], [2 x i32]* %tmp4, i64 0, i64 %idxprom
+  %tmp5 = load i32, i32* %arrayidx, align 4, !tbaa !3
+  %tmp5.lobit = lshr i32 %tmp5, 31
+  ret i32 %tmp5.lobit
+}
+
+!0 = !{!4, !4, i64 0}
+!1 = !{!"omnipotent char", !2}
+!2 = !{!"Simple C/C++ TBAA", null}
+!3 = !{!5, !5, i64 0}
+!4 = !{!"double", !1}
+!5 = !{!"int", !1}

llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/gep-index-no-alias.ll

+; This testcase ensures that gep result does not alias gep indices
+
+; RUN: opt < %s -disable-basicaa -cfl-steens-aa -aa-eval -print-no-aliases -disable-output 2>&1 | FileCheck %s
+; RUN: opt < %s -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-no-aliases -disable-output 2>&1 | FileCheck %s
+
+; CHECK: Function: foo
+; CHECK: [2 x i32]* %a, [2 x i32]* %b
+define void @foo(i32 %n) {
+  %a = alloca [2 x i32], align 4
+  %b = alloca [2 x i32], align 4
+  %c = getelementptr inbounds [2 x i32], [2 x i32]* %a, i32 0, i32 %n
+  %d = getelementptr inbounds [2 x i32], [2 x i32]* %b, i32 0, i32 %n
+  ret void
+}

llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/gep-signed-arithmetic.ll

+; RUN: opt < %s -disable-basicaa -cfl-steens-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+; Derived from BasicAA/2010-09-15-GEP-SignedArithmetic.ll
+
+target datalayout = "e-p:32:32:32"
+
+; FIXME: This could be PartialAlias but CFLSteensAA can't currently prove it
+; CHECK: 1 may alias response
+
+define i32 @test(i32 %indvar) nounwind {
+  %tab = alloca i32, align 4
+  %tmp31 = mul i32 %indvar, -2
+  %tmp32 = add i32 %tmp31, 30
+  %t.5 = getelementptr i32, i32* %tab, i32 %tmp32
+  %loada = load i32, i32* %tab
+  store i32 0, i32* %t.5
+  %loadb = load i32, i32* %tab
+  %rval = add i32 %loada, %loadb
+  ret i32 %rval
+}

llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-arg-deref-escape.ll

+; This testcase ensures that CFL AA answers queries soundly when callee tries 
+; to escape the memory pointed to by its parameters
+
+; RUN: opt < %s -disable-basicaa -cfl-steens-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+; RUN: opt < %s -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+
+declare void @opaque(i32*)
+define void @escape_arg_deref(i32** %arg) {
+  %arg_deref = load i32*, i32** %arg
+  call void @opaque(i32* %arg_deref)
+  ret void
+}
+; CHECK-LABEL: Function: test_arg_deref_escape
+; CHECK: NoAlias: i32* %a, i32** %x
+; CHECK: NoAlias: i32* %b, i32** %x
+; CHECK: NoAlias: i32* %a, i32* %b
+; CHECK: NoAlias: i32** %p, i32** %x
+; CHECK: NoAlias: i32* %a, i32** %p
+; CHECK: NoAlias: i32* %b, i32** %p
+; CHECK: MayAlias: i32* %a, i32* %c
+; CHECK: NoAlias: i32* %b, i32* %c
+; CHECK: NoAlias: i32* %c, i32** %p
+define void @test_arg_deref_escape(i32** %x) {
+  %a = alloca i32, align 4
+  %b = alloca i32, align 4
+  %p = alloca i32*, align 4
+  
+  store i32* %a, i32** %p
+  call void @escape_arg_deref(i32** %p)
+  %c = load i32*, i32** %x
+
+  ret void
+}
 No newline at end of file

llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-arg-escape.ll

+; This testcase ensures that CFL AA answers queries soundly when callee tries 
+; to escape its parameters
+
+; RUN: opt < %s -disable-basicaa -cfl-steens-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+; RUN: opt < %s -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+
+declare void @opaque(i32*)
+define void @escape_arg(i32* %arg) {
+  call void @opaque(i32* %arg)
+  ret void
+}
+; CHECK-LABEL: Function: test_arg_escape
+; CHECK: NoAlias: i32* %a, i32** %x
+; CHECK: NoAlias: i32* %b, i32** %x
+; CHECK: NoAlias: i32* %a, i32* %b
+; CHECK: NoAlias: i32* %c, i32** %x
+; CHECK: NoAlias: i32* %a, i32* %c
+; CHECK: NoAlias: i32* %b, i32* %c
+; CHECK: MayAlias: i32* %a, i32* %d
+; CHECK: MayAlias: i32* %b, i32* %d
+; CHECK: NoAlias: i32* %c, i32* %d
+define void @test_arg_escape(i32** %x) {
+  %a = alloca i32, align 4
+  %b = alloca i32, align 4
+  %c = alloca i32, align 4
+  call void @escape_arg(i32* %a)
+  call void @escape_arg(i32* %b)
+  %d = load i32*, i32** %x
+
+  ret void
+}
 No newline at end of file

llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-ret-arg.ll

+; This testcase ensures that CFL AA answers queries soundly when callee tries 
+; to return one of its parameters
+
+; RUN: opt < %s -disable-basicaa -cfl-steens-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+; RUN: opt < %s -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+
+define i32* @return_arg_callee(i32* %arg1, i32* %arg2) {
+  ret i32* %arg1
+}
+; CHECK-LABEL: Function: test_return_arg
+; CHECK: NoAlias: i32* %a, i32* %b
+; CHECK: MayAlias: i32* %a, i32* %c
+; CHECK: NoAlias: i32* %b, i32* %c
+
+; CHECK: NoModRef: Ptr: i32* %b <-> %c = call i32* @return_arg_callee(i32* %a, i32* %b)
+define void @test_return_arg() {
+  %a = alloca i32, align 4
+  %b = alloca i32, align 4
+
+  %c = call i32* @return_arg_callee(i32* %a, i32* %b)
+
+  ret void
+}
 No newline at end of file

llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-ret-deref-arg-multilevel.ll

+; This testcase ensures that CFL AA answers queries soundly when callee tries 
+; to return the multi-level dereference of one of its parameters
+
+; RUN: opt < %s -disable-basicaa -cfl-steens-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+; RUN: opt < %s -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+
+define i32* @return_deref_arg_multilevel_callee(i32*** %arg1) {
+  %deref = load i32**, i32*** %arg1
+  %deref2 = load i32*, i32** %deref
+  ret i32* %deref2
+}
+; CHECK-LABEL: Function: test_return_deref_arg_multilevel
+; CHECK: NoAlias: i32* %a, i32* %b
+; CHECK: MayAlias: i32* %a, i32* %c
+; CHECK: NoAlias: i32* %b, i32* %c
+; CHECK: NoAlias: i32* %c, i32** %p
+; CHECK: NoAlias: i32* %c, i32*** %pp
+; CHECK: MayAlias: i32** %lpp, i32** %p
+; CHECK: NoAlias: i32** %lpp, i32*** %pp
+; CHECK: NoAlias: i32* %c, i32** %lpp
+; CHECK: MayAlias: i32* %a, i32* %lpp_deref
+; CHECK: NoAlias: i32* %b, i32* %lpp_deref
+; CHECK: NoAlias: i32* %lpp_deref, i32*** %pp
+; CHECK: MayAlias: i32* %a, i32* %lp
+; CHECK: NoAlias: i32* %b, i32* %lp
+; CHECK: NoAlias: i32* %lp, i32** %p
+; CHECK: NoAlias: i32* %lp, i32*** %pp
+; CHECK: MayAlias: i32* %c, i32* %lp
+; CHECK: NoAlias: i32* %lp, i32** %lpp
+; CHECK: MayAlias: i32* %lp, i32* %lpp_deref
+define void @test_return_deref_arg_multilevel() {
+  %a = alloca i32, align 4
+  %b = alloca i32, align 4
+  %p = alloca i32*, align 8
+  %pp = alloca i32**, align 8
+
+  store i32* %a, i32** %p
+  store i32** %p, i32*** %pp
+  %c = call i32* @return_deref_arg_multilevel_callee(i32*** %pp)
+
+  %lpp = load i32**, i32*** %pp
+  %lpp_deref = load i32*, i32** %lpp
+  %lp = load i32*, i32** %p
+
+  ret void
+}
 No newline at end of file

llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-ret-deref-arg.ll

+; This testcase ensures that CFL AA answers queries soundly when callee tries 
+; to return the dereference of one of its parameters
+
+; RUN: opt < %s -disable-basicaa -cfl-steens-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+; RUN: opt < %s -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+
+define i32* @return_deref_arg_callee(i32** %arg1) {
+  %deref = load i32*, i32** %arg1
+  ret i32* %deref
+}
+; CHECK-LABEL: Function: test_return_deref_arg
+; CHECK: NoAlias: i32* %a, i32* %b
+; CHECK: MayAlias: i32* %a, i32* %c
+; CHECK: NoAlias: i32* %b, i32* %c
+; CHECK: MayAlias: i32* %a, i32* %lp
+; CHECK: NoAlias: i32* %b, i32* %lp
+; CHECK: NoAlias: i32* %lp, i32** %p
+; CHECK: MayAlias: i32* %c, i32* %lp
+define void @test_return_deref_arg() {
+  %a = alloca i32, align 4
+  %b = alloca i32, align 4
+  %p = alloca i32*, align 8
+
+  store i32* %a, i32** %p
+  %c = call i32* @return_deref_arg_callee(i32** %p)
+
+  %lp = load i32*, i32** %p
+
+  ret void
+}
 No newline at end of file

llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-ret-escape.ll

+; This testcase ensures that CFL AA answers queries soundly when callee tries 
+; to return an escaped pointer
+
+; RUN: opt < %s -disable-basicaa -cfl-steens-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+; RUN: opt < %s -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+
+declare noalias i8* @malloc(i64)
+declare void @opaque(i32*)
+
+define i32* @return_escaped_callee() {
+  %ptr = call noalias i8* @malloc(i64 8)
+  %ptr_cast = bitcast i8* %ptr to i32*
+  call void @opaque(i32* %ptr_cast)
+  ret i32* %ptr_cast
+}
+; CHECK-LABEL: Function: test_return_escape
+; CHECK: NoAlias: i32* %a, i32** %x
+; CHECK: NoAlias: i32* %b, i32** %x
+; CHECK: NoAlias: i32* %a, i32* %b
+; CHECK: NoAlias: i32* %c, i32** %x
+; CHECK: NoAlias: i32* %a, i32* %c
+; CHECK: NoAlias: i32* %b, i32* %c
+; CHECK: NoAlias: i32* %a, i32* %d
+; CHECK: MayAlias: i32* %b, i32* %d
+; CHECK: MayAlias: i32* %c, i32* %d
+define void @test_return_escape(i32** %x) {
+  %a = alloca i32, align 4
+  %b = call i32* @return_escaped_callee()
+  %c = call i32* @return_escaped_callee()
+  %d = load i32*, i32** %x
+
+  ret void
+}
 No newline at end of file

llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-ret-ref-arg-multilevel.ll

+; This testcase ensures that CFL AA answers queries soundly when callee tries 
+; to return the multi-level reference of one of its parameters
+
+; RUN: opt < %s -disable-basicaa -cfl-steens-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+; RUN: opt < %s -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+
+declare noalias i8* @malloc(i64)
+
+define i32*** @return_ref_arg_multilevel_callee(i32* %arg1) {
+  %ptr = call noalias i8* @malloc(i64 8)
+  %ptr_cast = bitcast i8* %ptr to i32***
+  %ptr2 = call noalias i8* @malloc(i64 8)
+  %ptr_cast2 = bitcast i8* %ptr2 to i32**
+  store i32* %arg1, i32** %ptr_cast2
+  store i32** %ptr_cast2, i32*** %ptr_cast
+  ret i32*** %ptr_cast
+}
+; CHECK-LABEL: Function: test_return_ref_arg_multilevel
+; CHECK: NoAlias: i32* %a, i32*** %b
+; CHECK: NoAlias: i32** %p, i32*** %b
+; CHECK: NoAlias: i32* %a, i32** %lb
+; CHECK: NoAlias: i32** %lb, i32*** %pp
+; CHECK: NoAlias: i32** %lb, i32*** %b
+; CHECK: MayAlias: i32* %a, i32* %lb_deref
+; CHECK: NoAlias: i32* %lb_deref, i32** %lpp
+; CHECK: MayAlias: i32* %lb_deref, i32* %lpp_deref
+; CHECK: NoAlias: i32* %lpp_deref, i32** %lpp
+; CHECK: MayAlias: i32* %lb_deref, i32* %lp
+; CHECK: NoAlias: i32* %lp, i32** %lpp
+; CHECK: MayAlias: i32* %lp, i32* %lpp_deref
+
+; We could've proven the following facts if the analysis were inclusion-based:
+; NoAlias: i32*** %b, i32*** %pp
+; NoAlias: i32** %lb, i32** %p
+define void @test_return_ref_arg_multilevel() {
+  %a = alloca i32, align 4
+  %p = alloca i32*, align 8
+  %pp = alloca i32**, align 8
+
+  store i32* %a, i32** %p
+  store i32** %p, i32*** %pp
+  %b = call i32*** @return_ref_arg_multilevel_callee(i32* %a)
+
+  %lb = load i32**, i32*** %b
+  %lb_deref = load i32*, i32** %lb
+  %lpp = load i32**, i32*** %pp
+  %lpp_deref = load i32*, i32** %lpp
+  %lp = load i32*, i32** %p
+
+  ret void
+}
 No newline at end of file

llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-ret-ref-arg.ll

+; This testcase ensures that CFL AA answers queries soundly when callee tries 
+; to return the reference of one of its parameters
+
+; RUN: opt < %s -disable-basicaa -cfl-steens-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+; RUN: opt < %s -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+
+declare noalias i8* @malloc(i64)
+
+define i32** @return_ref_arg_callee(i32* %arg1) {
+  %ptr = call noalias i8* @malloc(i64 8)
+  %ptr_cast = bitcast i8* %ptr to i32**
+  store i32* %arg1, i32** %ptr_cast
+  ret i32** %ptr_cast
+}
+; CHECK-LABEL: Function: test_return_ref_arg
+; CHECK: MayAlias: i32* %a, i32* %lb
+; CHECK: NoAlias: i32* %lb, i32** %p
+; CHECK: NoAlias: i32* %lb, i32** %b
+; CHECK: NoAlias: i32* %lp, i32** %p
+; CHECK: NoAlias: i32* %lp, i32** %b
+; CHECK: MayAlias: i32* %lb, i32* %lp
+
+; We could've proven the following facts if the analysis were inclusion-based:
+; NoAlias: i32** %b, i32** %p
+define void @test_return_ref_arg() {
+  %a = alloca i32, align 4
+  %p = alloca i32*, align 8
+
+  store i32* %a, i32** %p
+  %b = call i32** @return_ref_arg_callee(i32* %a)
+
+  %lb = load i32*, i32** %b
+  %lp = load i32*, i32** %p
+
+  ret void
+}
 No newline at end of file

llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-ret-unknown.ll

+; This testcase ensures that CFL AA answers queries soundly when callee tries 
+; to return an unknown pointer
+
+; RUN: opt < %s -disable-basicaa -cfl-steens-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+; RUN: opt < %s -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+
+@g = external global i32
+define i32* @return_unknown_callee(i32* %arg1, i32* %arg2) {
+  ret i32* @g
+}
+; CHECK-LABEL: Function: test_return_unknown
+; CHECK: NoAlias: i32* %a, i32* %b
+; CHECK: MayAlias: i32* %c, i32* %x
+; CHECK: NoAlias: i32* %a, i32* %c
+; CHECK: NoAlias: i32* %b, i32* %c
+define void @test_return_unknown(i32* %x) {
+  %a = alloca i32, align 4
+  %b = alloca i32, align 4
+
+  %c = call i32* @return_unknown_callee(i32* %a, i32* %b)
+
+  ret void
+}
+
+@g2 = external global i32*
+define i32** @return_unknown_callee2() {
+  ret i32** @g2
+}
+; CHECK-LABEL: Function: test_return_unknown2
+; CHECK: MayAlias: i32* %x, i32** %a
+; CHECK: MayAlias: i32* %b, i32* %x
+; CHECK: MayAlias: i32* %b, i32** %a
+define void @test_return_unknown2(i32* %x) {
+  %a = call i32** @return_unknown_callee2()
+  %b = load i32*, i32** %a
+
+  ret void
+}
 No newline at end of file

llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-store-arg-multilevel.ll

+; This testcase ensures that CFL AA answers queries soundly when callee tries 
+; to mutate the memory pointed to by its parameters
+
+; RUN: opt < %s -disable-basicaa -cfl-steens-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+; RUN: opt < %s -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+
+declare noalias i8* @malloc(i64)
+
+define void @store_arg_multilevel_callee(i32*** %arg1, i32* %arg2) {
+  %ptr = call noalias i8* @malloc(i64 8)
+  %ptr_cast = bitcast i8* %ptr to i32**
+  store i32* %arg2, i32** %ptr_cast
+  store i32** %ptr_cast, i32*** %arg1
+  ret void
+}
+; CHECK-LABEL: Function: test_store_arg_multilevel
+; CHECK: NoAlias: i32* %a, i32** %lpp
+; CHECK: NoAlias: i32* %b, i32** %lpp
+; CHECK: MayAlias: i32** %lpp, i32** %p
+; CHECK: MayAlias: i32* %a, i32* %lpp_deref
+; CHECK: MayAlias: i32* %b, i32* %lpp_deref
+; CHECK: NoAlias: i32* %lpp_deref, i32** %p
+; CHECK: NoAlias: i32* %lpp_deref, i32*** %pp
+; CHECK: NoAlias: i32* %lpp_deref, i32** %lpp
+; CHECK: MayAlias: i32* %a, i32* %lp
+; CHECK: NoAlias: i32* %lp, i32*** %pp
+; CHECK: NoAlias: i32* %lp, i32** %lpp
+; CHECK: MayAlias: i32* %lp, i32* %lpp_deref
+
+; We could've proven the following facts if the analysis were inclusion-based:
+; NoAlias: i32* %a, i32* %b
+; NoAlias: i32* %b, i32* %lp
+define void @test_store_arg_multilevel() {
+  %a = alloca i32, align 4
+  %b = alloca i32, align 4
+  %p = alloca i32*, align 8
+  %pp = alloca i32**, align 8
+
+  store i32* %a, i32** %p
+  store i32** %p, i32*** %pp
+  call void @store_arg_multilevel_callee(i32*** %pp, i32* %b)
+
+  %lpp = load i32**, i32*** %pp
+  %lpp_deref = load i32*, i32** %lpp
+  %lp = load i32*, i32** %p
+
+  ret void
+}
 No newline at end of file

llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-store-arg-unknown.ll

+; This testcase ensures that CFL AA answers queries soundly when callee tries 
+; to mutate the memory pointed to by its parameters
+
+; RUN: opt < %s -disable-basicaa -cfl-steens-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+; RUN: opt < %s -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+
+@g = external global i32
+
+define void @store_arg_unknown_callee(i32** %arg1) {
+  store i32* @g, i32** %arg1
+  ret void
+}
+; CHECK-LABEL: Function: test_store_arg_unknown
+; CHECK: NoAlias: i32* %x, i32** %p
+; CHECK: NoAlias: i32* %a, i32** %p
+; CHECK: NoAlias: i32* %b, i32** %p
+; CHECK: MayAlias: i32* %lp, i32* %x
+; CHECK: MayAlias: i32* %a, i32* %lp
+; CHECK: NoAlias: i32* %b, i32* %lp
+; CHECK: NoAlias: i32* %lp, i32** %p
+define void @test_store_arg_unknown(i32* %x) {
+  %a = alloca i32, align 4
+  %b = alloca i32, align 4
+  %p = alloca i32*, align 8
+
+  store i32* %a, i32** %p
+  call void @store_arg_unknown_callee(i32** %p)
+
+  %lp = load i32*, i32** %p
+
+  ret void
+}
 No newline at end of file

llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-store-arg.ll

+; This testcase ensures that CFL AA answers queries soundly when callee tries 
+; to mutate the memory pointed to by its parameters
+
+; RUN: opt < %s -disable-basicaa -cfl-steens-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+; RUN: opt < %s -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+
+define void @store_arg_callee(i32** %arg1, i32* %arg2) {
+  store i32* %arg2, i32** %arg1
+  ret void
+}
+; CHECK-LABEL: Function: test_store_arg
+; CHECK: NoAlias: i32* %a, i32** %p
+; CHECK: NoAlias: i32* %b, i32** %p
+; CHECK: MayAlias: i32* %a, i32* %lp
+; CHECK: MayAlias: i32* %b, i32* %lp
+; CHECK: MayAlias: i32* %b, i32* %lq
+; CHECK: MayAlias: i32* %lp, i32* %lq
+
+; We could've proven the following facts if the analysis were inclusion-based:
+; NoAlias: i32* %a, i32* %b
+; NoAlias: i32* %a, i32* %lq
+define void @test_store_arg() {
+  %a = alloca i32, align 4
+  %b = alloca i32, align 4
+  %p = alloca i32*, align 8
+  %q = alloca i32*, align 8
+
+  store i32* %a, i32** %p
+  store i32* %b, i32** %q
+  call void @store_arg_callee(i32** %p, i32* %b)
+
+  %lp = load i32*, i32** %p
+  %lq = load i32*, i32** %q
+
+  ret void
+}
 No newline at end of file

llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/malloc-and-free.ll

+; This testcase ensures that CFL AA handles malloc and free in a sound and precise manner
+
+; RUN: opt < %s -disable-basicaa -cfl-steens-aa -aa-eval -print-no-aliases -disable-output 2>&1 | FileCheck %s
+; RUN: opt < %s -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-no-aliases -disable-output 2>&1 | FileCheck %s
+
+declare noalias i8* @malloc(i64)
+declare noalias i8* @calloc(i64, i64)
+declare void @free(i8* nocapture)
+
+; CHECK: Function: test_malloc
+; CHECK: NoAlias: i8* %p, i8* %q
+define void @test_malloc(i8* %p) {
+  %q = call i8* @malloc(i64 4)
+  ret void
+}
+
+; CHECK: Function: test_calloc
+; CHECK: NoAlias: i8* %p, i8* %q
+define void @test_calloc(i8* %p) {
+  %q = call i8* @calloc(i64 2, i64 4)
+  ret void
+}
+
+; CHECK: Function: test_free
+; CHECK: NoAlias: i8* %p, i8* %q
+define void @test_free(i8* %p) {
+  %q = alloca i8, align 4
+  call void @free(i8* %q)
+  ret void
+}

llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/multilevel-combine.ll

+; This testcase ensures that CFL AA responds conservatively when we union 
+; groups of pointers together through ternary/conditional operations
+; Derived from:
+; void foo(bool c) {
+;   char a, b;
+;   char *m = c ? &a : &b;
+;   *m;
+; }
+;
+
+; RUN: opt < %s -disable-basicaa -cfl-steens-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s
+
+%T = type { i32, [10 x i8] }
+
+; CHECK:     Function: test
+
+define void @test(i1 %C) {
+; CHECK: 10 Total Alias Queries Performed
+; CHECK: 4 no alias responses
+  %M = alloca %T*, align 8 ; NoAlias with %A, %B, %MS, %AP
+  %A = alloca %T, align 8
+  %B = alloca %T, align 8
+
+  %MS = select i1 %C, %T* %B, %T* %A
+
+  store %T* %MS, %T** %M
+
+  %AP = load %T*, %T** %M ; PartialAlias with %A, %B
+
+  ret void
+}

llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/multilevel.ll

+; This testcase ensures that CFL AA handles trivial cases with storing 
+; pointers in pointers appropriately.
+; Derived from:
+; char a, b;
+; char *m = &a, *n = &b;
+; *m;
+; *n;
+
+; RUN: opt < %s -cfl-steens-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s
+
+%T = type { i32, [10 x i8] }
+
+; CHECK:     Function: test
+
+define void @test() {
+; CHECK: 15 Total Alias Queries Performed
+; CHECK: 13 no alias responses
+  %M = alloca %T*, align 8
+  %N = alloca %T*, align 8
+  %A = alloca %T, align 8
+  %B = alloca %T, align 8
+
+  store %T* %A, %T** %M
+  store %T* %B, %T** %N
+
+  %AP = load %T*, %T** %M ; PartialAlias with %A
+  %BP = load %T*, %T** %N ; PartialAlias with %B
+
+  ret void
+}

llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/must-and-partial.ll

+; RUN: opt < %s -disable-basicaa -cfl-steens-aa -aa-eval -print-all-alias-modref-info 2>&1 | FileCheck %s
+; When merging MustAlias and PartialAlias, merge to PartialAlias
+; instead of MayAlias.
+
+
+target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"
+
+; FIXME: This could be PartialAlias but CFLSteensAA can't currently prove it
+; CHECK: MayAlias:  i16* %bigbase0, i8* %phi
+define i8 @test0(i1 %x) {
+entry:
+  %base = alloca i8, align 4
+  %baseplusone = getelementptr i8, i8* %base, i64 1
+  br i1 %x, label %red, label %green
+red:
+  br label %green
+green:
+  %phi = phi i8* [ %baseplusone, %red ], [ %base, %entry ]
+  store i8 0, i8* %phi
+
+  %bigbase0 = bitcast i8* %base to i16*
+  store i16 -1, i16* %bigbase0
+
+  %loaded = load i8, i8* %phi
+  ret i8 %loaded
+}
+
+; FIXME: This could be PartialAlias but CFLSteensAA can't currently prove it
+; CHECK: MayAlias:  i16* %bigbase1, i8* %sel
+define i8 @test1(i1 %x) {
+entry:
+  %base = alloca i8, align 4
+  %baseplusone = getelementptr i8, i8* %base, i64 1
+  %sel = select i1 %x, i8* %baseplusone, i8* %base
+  store i8 0, i8* %sel
+
+  %bigbase1 = bitcast i8* %base to i16*
+  store i16 -1, i16* %bigbase1
+
+  %loaded = load i8, i8* %sel
+  ret i8 %loaded
+}
+
+; Incoming pointer arguments should not be PartialAlias because we do not know their initial state
+; even if they are nocapture
+; CHECK: MayAlias:  double* %A, double* %Index
+define void @testr2(double* nocapture readonly %A, double* nocapture readonly %Index) {
+  %arrayidx22 = getelementptr inbounds double, double* %Index, i64 2
+  %1 = load double, double* %arrayidx22
+  %arrayidx25 = getelementptr inbounds double, double* %A, i64 2
+  %2 = load double, double* %arrayidx25
+  %mul26 = fmul double %1, %2
+  ret void
+}

llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/opaque-call-alias.ll

+; We previously had a case where we would put results from a no-args call in
+; its own stratified set. This would make cases like the one in @test say that
+; nothing (except %Escapes and %Arg) can alias
+
+; RUN: opt < %s -disable-basicaa -cfl-steens-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+
+; CHECK:     Function: test
+; CHECK:     NoAlias: i8* %Arg, i8* %Escapes
+; CHECK:     MayAlias: i8* %Arg, i8* %Retrieved
+; CHECK:     MayAlias: i8* %Escapes, i8* %Retrieved
+define void @test(i8* %Arg) {
+  %Noalias = alloca i8
+  %Escapes = alloca i8
+  call void @set_thepointer(i8* %Escapes)
+  %Retrieved = call i8* @get_thepointer()
+  ret void
+}
+
+declare void @set_thepointer(i8* %P)
+declare i8* @get_thepointer()

llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/phi-and-select.ll

+; RUN: opt < %s -cfl-steens-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+; Derived from (a subset of) BasicAA/phi-and-select.ll 
+
+; CHECK: Function: qux
+; CHECK:  NoAlias: double* %a, double* %b
+; CHECK: ===== Alias Analysis Evaluator Report =====
+
+; Two PHIs with disjoint sets of inputs.
+define void @qux(i1 %m, double* noalias %x, double* noalias %y,
+                 i1 %n, double* noalias %v, double* noalias %w) {
+entry:
+  br i1 %m, label %true, label %false
+
+true:
+  br label %exit
+
+false:
+  br label %exit
+
+exit:
+  %a = phi double* [ %x, %true ], [ %y, %false ]
+  br i1 %n, label %ntrue, label %nfalse
+
+ntrue:
+  br label %nexit
+
+nfalse:
+  br label %nexit
+
+nexit:
+  %b = phi double* [ %v, %ntrue ], [ %w, %nfalse ]
+  store volatile double 0.0, double* %a
+  store volatile double 1.0, double* %b
+  ret void
+}
+

llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/pr27213.ll

+; RUN: opt < %s -disable-basicaa -cfl-steens-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s
+; RUN: opt < %s -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s
+
+; CHECK-LABEL:     Function: foo
+; CHECK: MayAlias: i32* %A, i32* %B
+define void @foo(i32* %A, i32* %B) {
+entry:
+  store i32 0, i32* %A, align 4
+  store i32 0, i32* %B, align 4
+  ret void
+}
+
+; CHECK-LABEL:     Function: bar
+; CHECK: MayAlias: i32* %A, i32* %B
+; CHECK: MayAlias: i32* %A, i32* %arrayidx
+; CHECK: MayAlias: i32* %B, i32* %arrayidx
+define void @bar(i32* %A, i32* %B) {
+entry:
+  store i32 0, i32* %A, align 4
+  %arrayidx = getelementptr inbounds i32, i32* %B, i64 1
+  store i32 0, i32* %arrayidx, align 4
+  ret void
+}
+
+@G = global i32 0
+
+; CHECK-LABEL:     Function: baz
+; CHECK: MayAlias: i32* %A, i32* @G
+define void @baz(i32* %A) {
+entry:
+  store i32 0, i32* %A, align 4
+  store i32 0, i32* @G, align 4
+  ret void
+}
+
+; CHECK-LABEL: Alias Analysis Evaluator Report
+; CHECK: 5 Total Alias Queries Performed
+; CHECK: 0 no alias responses
+; CHECK: 5 may alias responses

llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/simple.ll

+; This testcase consists of alias relations which should be completely
+; resolvable by cfl-steens-aa (derived from BasicAA/2003-11-04-SimpleCases.ll).
+
+; RUN: opt < %s -cfl-steens-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s
+
+%T = type { i32, [10 x i8] }
+
+; CHECK:     Function: test
+; CHECK-NOT:   May:
+
+define void @test(%T* %P) {
+  %A = getelementptr %T, %T* %P, i64 0
+  %B = getelementptr %T, %T* %P, i64 0, i32 0
+  %C = getelementptr %T, %T* %P, i64 0, i32 1
+  %D = getelementptr %T, %T* %P, i64 0, i32 1, i64 0
+  %E = getelementptr %T, %T* %P, i64 0, i32 1, i64 5
+  ret void
+}

llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/stratified-attrs-indexing.ll

+; This testcase ensures that CFLSteensAA doesn't try to access out of bounds indices
+; when given functions with large amounts of arguments (specifically, more
+; arguments than the StratifiedAttrs bitset can handle)
+;
+; Because the result on failure is effectively crashing the compiler, output
+; checking is minimal.
+
+; RUN: opt < %s -cfl-steens-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s
+
+; CHECK: Function: test
+define void @test(i1 %cond,
+                  i32* %arg1, i32* %arg2, i32* %arg3, i32* %arg4, i32* %arg5,
+                  i32* %arg6, i32* %arg7, i32* %arg8, i32* %arg9, i32* %arg10,
+                  i32* %arg11, i32* %arg12, i32* %arg13, i32* %arg14, i32* %arg15,
+                  i32* %arg16, i32* %arg17, i32* %arg18, i32* %arg19, i32* %arg20,
+                  i32* %arg21, i32* %arg22, i32* %arg23, i32* %arg24, i32* %arg25,
+                  i32* %arg26, i32* %arg27, i32* %arg28, i32* %arg29, i32* %arg30,
+                  i32* %arg31, i32* %arg32, i32* %arg33, i32* %arg34, i32* %arg35) {
+
+  ; CHECK: 946 Total Alias Queries Performed
+  ; CHECK: 43 no alias responses (4.5%)
+  %a = alloca i32, align 4
+  %b = select i1 %cond, i32* %arg35, i32* %arg34
+  %c = select i1 %cond, i32* %arg34, i32* %arg33
+  %d = select i1 %cond, i32* %arg33, i32* %arg32
+  %e = select i1 %cond, i32* %arg32, i32* %arg31
+  %f = select i1 %cond, i32* %arg31, i32* %arg30
+  %g = select i1 %cond, i32* %arg30, i32* %arg29
+  %h = select i1 %cond, i32* %arg29, i32* %arg28
+  %i = select i1 %cond, i32* %arg28, i32* %arg27
+
+  ret void
+}

llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/va.ll

+; RUN: opt < %s -disable-basicaa -cfl-steens-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+
+; CHECK-LABEL: Function: test1
+; CHECK: MayAlias: i32* %X, i32* %tmp
+; CHECK: MayAlias: i32* %tmp, i8** %ap
+; CHECK: NoAlias: i8** %ap, i8** %aq
+; CHECK: MayAlias: i32* %tmp, i8** %aq
+
+define i32* @test1(i32* %X, ...) {
+  ; Initialize variable argument processing
+  %ap = alloca i8*
+  %ap2 = bitcast i8** %ap to i8*
+  call void @llvm.va_start(i8* %ap2)
+
+  ; Read a single pointer argument
+  %tmp = va_arg i8** %ap, i32*
+
+  ; Demonstrate usage of llvm.va_copy and llvm.va_end
+  %aq = alloca i8*
+  %aq2 = bitcast i8** %aq to i8*
+  call void @llvm.va_copy(i8* %aq2, i8* %ap2)
+  call void @llvm.va_end(i8* %aq2)
+
+  ; Stop processing of arguments.
+  call void @llvm.va_end(i8* %ap2)
+  ret i32* %tmp
+}
+
+declare void @llvm.va_start(i8*)
+declare void @llvm.va_copy(i8*, i8*)
+declare void @llvm.va_end(i8*)
+

llvm/trunk/test/Analysis/CFLAliasAnalysis/arguments-globals.ll

-; This testcase ensures that CFL AA gives conservative answers on variables
-; that involve arguments.
-; (Everything should alias everything, because args can alias globals, so the
-; aliasing sets should of args+alloca+global should be combined)
-
-; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s
-
-; CHECK:     Function: test
-
-@g = external global i32
-
-define void @test(i1 %c, i32* %arg1, i32* %arg2) {
-  ; CHECK: 15 Total Alias Queries Performed
-  ; CHECK: 0 no alias responses
-  %A = alloca i32, align 4
-  %B = select i1 %c, i32* %arg1, i32* %arg2
-  %C = select i1 %c, i32* @g, i32* %A
-
-  ret void
-}

llvm/trunk/test/Analysis/CFLAliasAnalysis/arguments.ll

-; This testcase ensures that CFL AA gives conservative answers on variables
-; that involve arguments.
-
-; RUN: opt < %s -cfl-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s
-
-; CHECK:     Function: test
-
-define void @test(i1 %c, i32* %arg1, i32* %arg2) {
-  ; CHECK: 6 Total Alias Queries Performed
-  ; CHECK: 3 no alias responses
-  %a = alloca i32, align 4
-  %b = select i1 %c, i32* %arg1, i32* %arg2
-
-  ret void
-}

llvm/trunk/test/Analysis/CFLAliasAnalysis/asm-global-bugfix.ll

-; Test case for a bug where we would crash when we were requested to report
-; whether two values that didn't belong to a function (i.e. two globals, etc)
-; aliased.
-
-; RUN: opt < %s -cfl-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s
-
-@G = private unnamed_addr constant [1 x i8] c"\00", align 1
-
-; CHECK: Function: test_no_crash
-; CHECK: 0 no alias responses
-define void @test_no_crash() #0 {
-entry:
-  call i8* asm "nop", "=r,r"(
-       i8* getelementptr inbounds ([1 x i8], [1 x i8]* @G, i64 0, i64 0))
-  ret void
-}

llvm/trunk/test/Analysis/CFLAliasAnalysis/attr-escape.ll

-; This testcase ensures that CFL AA handles escaped values no more conservative than it should
-
-; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
-; RUN: opt < %s -aa-pipeline=cfl-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
-
-; CHECK-LABEL: Function: test_local
-; CHECK: NoAlias: i32* %a, i32* %b
-; CHECK: MayAlias: i32* %a, i32* %aAlias
-; CHECK: NoAlias: i32* %aAlias, i32* %b
-define void @test_local() {
-  %a = alloca i32, align 4
-  %b = alloca i32, align 4
-  %aint = ptrtoint i32* %a to i64
-  %aAlias = inttoptr i64 %aint to i32*
-  ret void
-}
-
-; CHECK-LABEL: Function: test_global_param
-; CHECK: NoAlias: i32* %a, i32** %x
-; CHECK: MayAlias: i32* %a, i32* %xload
-; CHECK: MayAlias: i32* %a, i32* %gload
-; CHECK: MayAlias: i32* %gload, i32* %xload
-; CHECK: MayAlias: i32** %x, i32** @ext_global
-; CHECK: NoAlias: i32* %a, i32** @ext_global
-@ext_global = external global i32*
-define void @test_global_param(i32** %x) {
-  %a = alloca i32, align 4
-  %aint = ptrtoint i32* %a to i64
-  %xload = load i32*, i32** %x
-  %gload = load i32*, i32** @ext_global
-  ret void
-}
-
-declare void @external_func(i32**)
-; CHECK-LABEL: Function: test_external_call
-; CHECK: NoAlias: i32* %b, i32* %x
-; CHECK: NoAlias: i32* %b, i32** %a
-; CHECK: MayAlias: i32* %c, i32* %x
-; CHECK: MayAlias: i32* %c, i32** %a
-; CHECK: NoAlias: i32* %b, i32* %c
-define void @test_external_call(i32* %x) {
-  %a = alloca i32*, align 8
-  %b = alloca i32, align 4
-  call void @external_func(i32** %a)
-  %c = load i32*, i32** %a
-  ret void
-}
-
-declare void @external_func_readonly(i32**) readonly
-; CHECK-LABEL: Function: test_external_call_func_readonly
-; CHECK: MayAlias: i32* %c, i32* %x
-; CHECK: NoAlias: i32* %c, i32** %a
-define void @test_external_call_func_readonly(i32* %x) {
-  %a = alloca i32*, align 8
-  %b = alloca i32, align 4
-  store i32* %x, i32** %a, align 4
-  call void @external_func_readonly(i32** %a)
-  %c = load i32*, i32** %a
-  ret void
-}
-
-; CHECK-LABEL: Function: test_external_call_callsite_readonly
-; CHECK: MayAlias: i32* %c, i32* %x
-; CHECK: NoAlias: i32* %c, i32** %a
-define void @test_external_call_callsite_readonly(i32* %x) {
-  %a = alloca i32*, align 8
-  %b = alloca i32, align 4
-  store i32* %x, i32** %a, align 4
-  call void @external_func(i32** %a) readonly
-  %c = load i32*, i32** %a
-  ret void
-}
-
-declare i32* @external_func_normal_return(i32*)
-; CHECK-LABEL: Function: test_external_call_normal_return
-; CHECK: MayAlias: i32* %c, i32* %x
-; CHECK: MayAlias: i32* %a, i32* %c
-define void @test_external_call_normal_return(i32* %x) {
-  %a = alloca i32, align 8
-  %b = alloca i32, align 4
-  %c = call i32* @external_func_normal_return(i32* %a)
-  ret void
-}
-
-declare noalias i32* @external_func_noalias_return(i32*)
-; CHECK-LABEL: Function: test_external_call_noalias_return
-; CHECK: NoAlias: i32* %c, i32* %x
-; CHECK: NoAlias: i32* %a, i32* %c
-define void @test_external_call_noalias_return(i32* %x) {
-  %a = alloca i32, align 8
-  %b = alloca i32, align 4
-  %c = call i32* @external_func_noalias_return(i32* %a)
-  ret void
-}

llvm/trunk/test/Analysis/CFLAliasAnalysis/basic-interproc.ll

-; This testcase ensures that CFL AA won't be too conservative when trying to do
-; interprocedural analysis on simple callee
-
-; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
-; RUN: opt < %s -aa-pipeline=cfl-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
-
-; CHECK-LABEL: Function: noop_callee
-; CHECK: MayAlias: i32* %arg1, i32* %arg2
-define void @noop_callee(i32* %arg1, i32* %arg2) {
-  store i32 0, i32* %arg1
-  store i32 0, i32* %arg2
-  ret void
-}
-; CHECK-LABEL: Function: test_noop
-; CHECK: NoAlias: i32* %a, i32* %b
-define void @test_noop() {
-  %a = alloca i32, align 4
-  %b = alloca i32, align 4
-  call void @noop_callee(i32* %a, i32* %b)
-
-  ret void
-}

llvm/trunk/test/Analysis/CFLAliasAnalysis/branch-alias.ll

-; Makes sure that we give up on some pathological cases with inttoptr/ptrtoint
-;
-; @ptr_test was generated from the following C code:
-;  void ptr_test() {
-;    int* A;
-;    unsigned long RefCopy = 0;
-;    for (int i = 0; i < 8*sizeof(&A); ++i) {
-;      if ((unsigned long)&A & (1UL << i))
-;        RefCopy |= 1UL << i;
-;    }
-;
-;    int** AliasA1 = (int**)RefCopy;
-;    int* ShouldAliasA = *AliasA1;
-;  }
-
-; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s
-
-; CHECK: Function: ptr_test
-define void @ptr_test() #0 {
-  ; CHECK: MayAlias: i32** %A, i32** %ShouldAliasA
-  ; CHECK-NOT: %AliasA1
-entry:
-  %A = alloca i32*, align 8
-  %RefCopy = alloca i64, align 8
-  %i = alloca i32, align 4
-  %AliasA1 = alloca i32**, align 8
-  %ShouldAliasA = alloca i32*, align 8
-  store i64 0, i64* %RefCopy, align 8
-  store i32 0, i32* %i, align 4
-  br label %for.cond
-
-for.cond:                                         ; preds = %for.inc, %entry
-  %0 = load i32, i32* %i, align 4
-  %conv = sext i32 %0 to i64
-  %cmp = icmp ult i64 %conv, 64
-  br i1 %cmp, label %for.body, label %for.end
-
-for.body:                                         ; preds = %for.cond
-  %1 = ptrtoint i32** %A to i64
-  %2 = load i32, i32* %i, align 4
-  %sh_prom = zext i32 %2 to i64
-  %shl = shl i64 1, %sh_prom
-  %and = and i64 %1, %shl
-  %tobool = icmp ne i64 %and, 0
-  br i1 %tobool, label %if.then, label %if.end
-
-if.then:                                          ; preds = %for.body
-  %3 = load i32, i32* %i, align 4
-  %sh_prom2 = zext i32 %3 to i64
-  %shl3 = shl i64 1, %sh_prom2
-  %4 = load i64, i64* %RefCopy, align 8
-  %or = or i64 %4, %shl3
-  store i64 %or, i64* %RefCopy, align 8
-  br label %if.end
-
-if.end:                                           ; preds = %if.then, %for.body
-  br label %for.inc
-
-for.inc:                                          ; preds = %if.end
-  %5 = load i32, i32* %i, align 4
-  %inc = add nsw i32 %5, 1
-  store i32 %inc, i32* %i, align 4
-  br label %for.cond
-
-for.end:                                          ; preds = %for.cond
-  %6 = load i64, i64* %RefCopy, align 8
-  %7 = inttoptr i64 %6 to i32**
-  store i32** %7, i32*** %AliasA1, align 8
-  %8 = load i32**, i32*** %AliasA1, align 8
-  %9 = load i32*, i32** %8, align 8
-  store i32* %9, i32** %ShouldAliasA, align 8
-  ret void
-}

llvm/trunk/test/Analysis/CFLAliasAnalysis/const-expr-gep.ll

-; This testcase consists of alias relations which should be completely
-; resolvable by cfl-aa, but require analysis of getelementptr constant exprs.
-; Derived from BasicAA/2003-12-11-ConstExprGEP.ll
-
-; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s
-
-%T = type { i32, [10 x i8] }
-
-@G = external global %T
-@G2 = external global %T
-
-; TODO: Quite a few of these are MayAlias because we don't yet consider
-; constant offsets in CFLAA. If we start doing so, then we'll need to
-; change these test cases
-
-; CHECK:     Function: test
-; CHECK:     MayAlias: i32* %D, i32* %F
-; CHECK:     MayAlias: i32* %D, i8* %X
-; CHECK:     MayAlias: i32* %F, i8* %X
-define void @test() {
-  %D = getelementptr %T, %T* @G, i64 0, i32 0
-  %F = getelementptr i32, i32* getelementptr (%T, %T* @G, i64 0, i32 0), i64 0
-  %X = getelementptr [10 x i8], [10 x i8]* getelementptr (%T, %T* @G, i64 0, i32 1), i64 0, i64 5
-
-  ret void
-}
-
-; CHECK:     Function: simplecheck
-; CHECK:     MayAlias: i32* %F, i32* %arg0
-; CHECK:     MayAlias: i32* %H, i32* %arg0
-; CHECK:     MayAlias: i32* %F, i32* %H
-define void @simplecheck(i32* %arg0) {
-  %F = getelementptr i32, i32* getelementptr (%T, %T* @G, i64 0, i32 0), i64 0
-  %H = getelementptr %T, %T* @G2, i64 0, i32 0
-
-  ret void
-}
-
-; Ensure that CFLAA properly identifies and handles escaping variables (i.e.
-; globals) in nested ConstantExprs
-
-; CHECK:      Function: checkNesting
-; CHECK:      MayAlias: i32* %A, i32* %arg0
-
-%NestedT = type { [1 x [1 x i32]] }
-@NT = external global %NestedT
-
-define void @checkNesting(i32* %arg0) {
-  %A = getelementptr [1 x i32],
-         [1 x i32]* getelementptr
-           ([1 x [1 x i32]], [1 x [1 x i32]]* getelementptr (%NestedT, %NestedT* @NT, i64 0, i32 0),
-           i64 0,
-           i32 0),
-         i64 0,
-         i32 0
-  ret void
-}

llvm/trunk/test/Analysis/CFLAliasAnalysis/constant-over-index.ll

-; RUN: opt < %s -cfl-aa -aa-eval -print-all-alias-modref-info 2>&1 | FileCheck %s
-
-; CFL AA currently returns PartialAlias, BasicAA returns MayAlias, both seem
-; acceptable (although we might decide that we don't want PartialAlias, and if
-; so, we should update this test case accordingly).
-; CHECK: {{PartialAlias|MayAlias}}: double* %p.0.i.0, double* %p3
-
-; %p3 is equal to %p.0.i.0 on the second iteration of the loop,
-; so MayAlias is needed.
-
-define void @foo([3 x [3 x double]]* noalias %p) {
-entry:
-  %p3 = getelementptr [3 x [3 x double]], [3 x [3 x double]]* %p, i64 0, i64 0, i64 3
-  br label %loop
-
-loop:
-  %i = phi i64 [ 0, %entry ], [ %i.next, %loop ]
-
-  %p.0.i.0 = getelementptr [3 x [3 x double]], [3 x [3 x double]]* %p, i64 0, i64 %i, i64 0
-
-  store volatile double 0.0, double* %p3
-  store volatile double 0.1, double* %p.0.i.0
-
-  %i.next = add i64 %i, 1
-  %cmp = icmp slt i64 %i.next, 3
-  br i1 %cmp, label %loop, label %exit
-
-exit:
-  ret void
-}

llvm/trunk/test/Analysis/CFLAliasAnalysis/empty.ll

-; RUN: opt < %s -cfl-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
-
-target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"
-
-; CHECK:      Function: foo:
-; CHECK-NEXT:   NoAlias: {}* %p, {}* %q
-
-define void @foo({}* %p, {}* %q) {
-  store {} {}, {}* %p
-  store {} {}, {}* %q
-  ret void
-}

llvm/trunk/test/Analysis/CFLAliasAnalysis/full-store-partial-alias.ll

-; RUN: opt -S -disable-basicaa -tbaa -cfl-aa -gvn < %s | FileCheck -check-prefix=CFLAA %s
-; RUN: opt -S -disable-basicaa -tbaa -gvn < %s | FileCheck %s
-; Adapted from the BasicAA full-store-partial-alias.ll test.
-
-; CFL AA could notice that the store stores to the entire %u object,
-; so the %tmp5 load is PartialAlias with the store and suppress TBAA.
-; FIXME: However, right now, CFLAA cannot prove PartialAlias here
-; Without CFL AA, TBAA should say that %tmp5 is NoAlias with the store.
-
-target datalayout = "e-p:64:64:64"
-
-%union.anon = type { double }
-
-@u = global %union.anon { double -2.500000e-01 }, align 8
-@endianness_test = global i64 1, align 8
-
-define i32 @signbit(double %x) nounwind {
-; FIXME: This would be ret i32 %tmp5.lobit if CFLAA could prove PartialAlias
-; CFLAA: ret i32 0
-; CHECK: ret i32 0
-entry:
-  %u = alloca %union.anon, align 8
-  %tmp9 = getelementptr inbounds %union.anon, %union.anon* %u, i64 0, i32 0
-  store double %x, double* %tmp9, align 8, !tbaa !0
-  %tmp2 = load i32, i32* bitcast (i64* @endianness_test to i32*), align 8, !tbaa !3
-  %idxprom = sext i32 %tmp2 to i64
-  %tmp4 = bitcast %union.anon* %u to [2 x i32]*
-  %arrayidx = getelementptr inbounds [2 x i32], [2 x i32]* %tmp4, i64 0, i64 %idxprom
-  %tmp5 = load i32, i32* %arrayidx, align 4, !tbaa !3
-  %tmp5.lobit = lshr i32 %tmp5, 31
-  ret i32 %tmp5.lobit
-}
-
-!0 = !{!4, !4, i64 0}
-!1 = !{!"omnipotent char", !2}
-!2 = !{!"Simple C/C++ TBAA", null}
-!3 = !{!5, !5, i64 0}
-!4 = !{!"double", !1}
-!5 = !{!"int", !1}

llvm/trunk/test/Analysis/CFLAliasAnalysis/gep-index-no-alias.ll

-; This testcase ensures that gep result does not alias gep indices
-
-; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-no-aliases -disable-output 2>&1 | FileCheck %s
-; RUN: opt < %s -aa-pipeline=cfl-aa -passes=aa-eval -print-no-aliases -disable-output 2>&1 | FileCheck %s
-
-; CHECK: Function: foo
-; CHECK: [2 x i32]* %a, [2 x i32]* %b
-define void @foo(i32 %n) {
-  %a = alloca [2 x i32], align 4
-  %b = alloca [2 x i32], align 4
-  %c = getelementptr inbounds [2 x i32], [2 x i32]* %a, i32 0, i32 %n
-  %d = getelementptr inbounds [2 x i32], [2 x i32]* %b, i32 0, i32 %n
-  ret void
-}

llvm/trunk/test/Analysis/CFLAliasAnalysis/gep-signed-arithmetic.ll

-; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
-; Derived from BasicAA/2010-09-15-GEP-SignedArithmetic.ll
-
-target datalayout = "e-p:32:32:32"
-
-; FIXME: This could be PartialAlias but CFLAA can't currently prove it
-; CHECK: 1 may alias response
-
-define i32 @test(i32 %indvar) nounwind {
-  %tab = alloca i32, align 4
-  %tmp31 = mul i32 %indvar, -2
-  %tmp32 = add i32 %tmp31, 30
-  %t.5 = getelementptr i32, i32* %tab, i32 %tmp32
-  %loada = load i32, i32* %tab
-  store i32 0, i32* %t.5
-  %loadb = load i32, i32* %tab
-  %rval = add i32 %loada, %loadb
-  ret i32 %rval
-}

llvm/trunk/test/Analysis/CFLAliasAnalysis/interproc-arg-deref-escape.ll

-; This testcase ensures that CFL AA answers queries soundly when callee tries 
-; to escape the memory pointed to by its parameters
-
-; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
-; RUN: opt < %s -aa-pipeline=cfl-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
-
-declare void @opaque(i32*)
-define void @escape_arg_deref(i32** %arg) {
-  %arg_deref = load i32*, i32** %arg
-  call void @opaque(i32* %arg_deref)
-  ret void
-}
-; CHECK-LABEL: Function: test_arg_deref_escape
-; CHECK: NoAlias: i32* %a, i32** %x
-; CHECK: NoAlias: i32* %b, i32** %x
-; CHECK: NoAlias: i32* %a, i32* %b
-; CHECK: NoAlias: i32** %p, i32** %x
-; CHECK: NoAlias: i32* %a, i32** %p
-; CHECK: NoAlias: i32* %b, i32** %p
-; CHECK: MayAlias: i32* %a, i32* %c
-; CHECK: NoAlias: i32* %b, i32* %c
-; CHECK: NoAlias: i32* %c, i32** %p
-define void @test_arg_deref_escape(i32** %x) {
-  %a = alloca i32, align 4
-  %b = alloca i32, align 4
-  %p = alloca i32*, align 4
-  
-  store i32* %a, i32** %p
-  call void @escape_arg_deref(i32** %p)
-  %c = load i32*, i32** %x
-
-  ret void
-}
 

llvm/trunk/test/Analysis/CFLAliasAnalysis/interproc-arg-escape.ll

-; This testcase ensures that CFL AA answers queries soundly when callee tries 
-; to escape its parameters
-
-; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
-; RUN: opt < %s -aa-pipeline=cfl-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
-
-declare void @opaque(i32*)
-define void @escape_arg(i32* %arg) {
-  call void @opaque(i32* %arg)
-  ret void
-}
-; CHECK-LABEL: Function: test_arg_escape
-; CHECK: NoAlias: i32* %a, i32** %x
-; CHECK: NoAlias: i32* %b, i32** %x
-; CHECK: NoAlias: i32* %a, i32* %b
-; CHECK: NoAlias: i32* %c, i32** %x
-; CHECK: NoAlias: i32* %a, i32* %c
-; CHECK: NoAlias: i32* %b, i32* %c
-; CHECK: MayAlias: i32* %a, i32* %d
-; CHECK: MayAlias: i32* %b, i32* %d
-; CHECK: NoAlias: i32* %c, i32* %d
-define void @test_arg_escape(i32** %x) {
-  %a = alloca i32, align 4
-  %b = alloca i32, align 4
-  %c = alloca i32, align 4
-  call void @escape_arg(i32* %a)
-  call void @escape_arg(i32* %b)
-  %d = load i32*, i32** %x
-
-  ret void
-}
 

llvm/trunk/test/Analysis/CFLAliasAnalysis/interproc-ret-arg.ll

-; This testcase ensures that CFL AA answers queries soundly when callee tries 
-; to return one of its parameters
-
-; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
-; RUN: opt < %s -aa-pipeline=cfl-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
-
-define i32* @return_arg_callee(i32* %arg1, i32* %arg2) {
-  ret i32* %arg1
-}
-; CHECK-LABEL: Function: test_return_arg
-; CHECK: NoAlias: i32* %a, i32* %b
-; CHECK: MayAlias: i32* %a, i32* %c
-; CHECK: NoAlias: i32* %b, i32* %c
-
-; CHECK: NoModRef: Ptr: i32* %b <-> %c = call i32* @return_arg_callee(i32* %a, i32* %b)
-define void @test_return_arg() {
-  %a = alloca i32, align 4
-  %b = alloca i32, align 4
-
-  %c = call i32* @return_arg_callee(i32* %a, i32* %b)
-
-  ret void
-}
 

llvm/trunk/test/Analysis/CFLAliasAnalysis/interproc-ret-deref-arg-multilevel.ll

-; This testcase ensures that CFL AA answers queries soundly when callee tries 
-; to return the multi-level dereference of one of its parameters
-
-; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
-; RUN: opt < %s -aa-pipeline=cfl-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
-
-define i32* @return_deref_arg_multilevel_callee(i32*** %arg1) {
-  %deref = load i32**, i32*** %arg1
-  %deref2 = load i32*, i32** %deref
-  ret i32* %deref2
-}
-; CHECK-LABEL: Function: test_return_deref_arg_multilevel
-; CHECK: NoAlias: i32* %a, i32* %b
-; CHECK: MayAlias: i32* %a, i32* %c
-; CHECK: NoAlias: i32* %b, i32* %c
-; CHECK: NoAlias: i32* %c, i32** %p
-; CHECK: NoAlias: i32* %c, i32*** %pp
-; CHECK: MayAlias: i32** %lpp, i32** %p
-; CHECK: NoAlias: i32** %lpp, i32*** %pp
-; CHECK: NoAlias: i32* %c, i32** %lpp
-; CHECK: MayAlias: i32* %a, i32* %lpp_deref
-; CHECK: NoAlias: i32* %b, i32* %lpp_deref
-; CHECK: NoAlias: i32* %lpp_deref, i32*** %pp
-; CHECK: MayAlias: i32* %a, i32* %lp
-; CHECK: NoAlias: i32* %b, i32* %lp
-; CHECK: NoAlias: i32* %lp, i32** %p
-; CHECK: NoAlias: i32* %lp, i32*** %pp
-; CHECK: MayAlias: i32* %c, i32* %lp
-; CHECK: NoAlias: i32* %lp, i32** %lpp
-; CHECK: MayAlias: i32* %lp, i32* %lpp_deref
-define void @test_return_deref_arg_multilevel() {
-  %a = alloca i32, align 4
-  %b = alloca i32, align 4
-  %p = alloca i32*, align 8
-  %pp = alloca i32**, align 8
-
-  store i32* %a, i32** %p
-  store i32** %p, i32*** %pp
-  %c = call i32* @return_deref_arg_multilevel_callee(i32*** %pp)
-
-  %lpp = load i32**, i32*** %pp
-  %lpp_deref = load i32*, i32** %lpp
-  %lp = load i32*, i32** %p
-
-  ret void
-}
 

llvm/trunk/test/Analysis/CFLAliasAnalysis/interproc-ret-deref-arg.ll

-; This testcase ensures that CFL AA answers queries soundly when callee tries 
-; to return the dereference of one of its parameters
-
-; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
-; RUN: opt < %s -aa-pipeline=cfl-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
-
-define i32* @return_deref_arg_callee(i32** %arg1) {
-  %deref = load i32*, i32** %arg1
-  ret i32* %deref
-}
-; CHECK-LABEL: Function: test_return_deref_arg
-; CHECK: NoAlias: i32* %a, i32* %b
-; CHECK: MayAlias: i32* %a, i32* %c
-; CHECK: NoAlias: i32* %b, i32* %c
-; CHECK: MayAlias: i32* %a, i32* %lp
-; CHECK: NoAlias: i32* %b, i32* %lp
-; CHECK: NoAlias: i32* %lp, i32** %p
-; CHECK: MayAlias: i32* %c, i32* %lp
-define void @test_return_deref_arg() {
-  %a = alloca i32, align 4
-  %b = alloca i32, align 4
-  %p = alloca i32*, align 8
-
-  store i32* %a, i32** %p
-  %c = call i32* @return_deref_arg_callee(i32** %p)
-
-  %lp = load i32*, i32** %p
-
-  ret void
-}
 

llvm/trunk/test/Analysis/CFLAliasAnalysis/interproc-ret-escape.ll

-; This testcase ensures that CFL AA answers queries soundly when callee tries 
-; to return an escaped pointer
-
-; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
-; RUN: opt < %s -aa-pipeline=cfl-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
-
-declare noalias i8* @malloc(i64)
-declare void @opaque(i32*)
-
-define i32* @return_escaped_callee() {
-  %ptr = call noalias i8* @malloc(i64 8)
-  %ptr_cast = bitcast i8* %ptr to i32*
-  call void @opaque(i32* %ptr_cast)
-  ret i32* %ptr_cast
-}
-; CHECK-LABEL: Function: test_return_escape
-; CHECK: NoAlias: i32* %a, i32** %x
-; CHECK: NoAlias: i32* %b, i32** %x
-; CHECK: NoAlias: i32* %a, i32* %b
-; CHECK: NoAlias: i32* %c, i32** %x
-; CHECK: NoAlias: i32* %a, i32* %c
-; CHECK: NoAlias: i32* %b, i32* %c
-; CHECK: NoAlias: i32* %a, i32* %d
-; CHECK: MayAlias: i32* %b, i32* %d
-; CHECK: MayAlias: i32* %c, i32* %d
-define void @test_return_escape(i32** %x) {
-  %a = alloca i32, align 4
-  %b = call i32* @return_escaped_callee()
-  %c = call i32* @return_escaped_callee()
-  %d = load i32*, i32** %x
-
-  ret void
-}
 

llvm/trunk/test/Analysis/CFLAliasAnalysis/interproc-ret-ref-arg-multilevel.ll

-; This testcase ensures that CFL AA answers queries soundly when callee tries 
-; to return the multi-level reference of one of its parameters
-
-; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
-; RUN: opt < %s -aa-pipeline=cfl-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
-
-declare noalias i8* @malloc(i64)
-
-define i32*** @return_ref_arg_multilevel_callee(i32* %arg1) {
-  %ptr = call noalias i8* @malloc(i64 8)
-  %ptr_cast = bitcast i8* %ptr to i32***
-  %ptr2 = call noalias i8* @malloc(i64 8)
-  %ptr_cast2 = bitcast i8* %ptr2 to i32**
-  store i32* %arg1, i32** %ptr_cast2
-  store i32** %ptr_cast2, i32*** %ptr_cast
-  ret i32*** %ptr_cast
-}
-; CHECK-LABEL: Function: test_return_ref_arg_multilevel
-; CHECK: NoAlias: i32* %a, i32*** %b
-; CHECK: NoAlias: i32** %p, i32*** %b
-; CHECK: NoAlias: i32* %a, i32** %lb
-; CHECK: NoAlias: i32** %lb, i32*** %pp
-; CHECK: NoAlias: i32** %lb, i32*** %b
-; CHECK: MayAlias: i32* %a, i32* %lb_deref
-; CHECK: NoAlias: i32* %lb_deref, i32** %lpp
-; CHECK: MayAlias: i32* %lb_deref, i32* %lpp_deref
-; CHECK: NoAlias: i32* %lpp_deref, i32** %lpp
-; CHECK: MayAlias: i32* %lb_deref, i32* %lp
-; CHECK: NoAlias: i32* %lp, i32** %lpp
-; CHECK: MayAlias: i32* %lp, i32* %lpp_deref
-
-; We could've proven the following facts if the analysis were inclusion-based:
-; NoAlias: i32*** %b, i32*** %pp
-; NoAlias: i32** %lb, i32** %p
-define void @test_return_ref_arg_multilevel() {
-  %a = alloca i32, align 4
-  %p = alloca i32*, align 8
-  %pp = alloca i32**, align 8
-
-  store i32* %a, i32** %p
-  store i32** %p, i32*** %pp
-  %b = call i32*** @return_ref_arg_multilevel_callee(i32* %a)
-
-  %lb = load i32**, i32*** %b
-  %lb_deref = load i32*, i32** %lb
-  %lpp = load i32**, i32*** %pp
-  %lpp_deref = load i32*, i32** %lpp
-  %lp = load i32*, i32** %p
-
-  ret void
-}
 

llvm/trunk/test/Analysis/CFLAliasAnalysis/interproc-ret-ref-arg.ll

-; This testcase ensures that CFL AA answers queries soundly when callee tries 
-; to return the reference of one of its parameters
-
-; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
-; RUN: opt < %s -aa-pipeline=cfl-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
-
-declare noalias i8* @malloc(i64)
-
-define i32** @return_ref_arg_callee(i32* %arg1) {
-  %ptr = call noalias i8* @malloc(i64 8)
-  %ptr_cast = bitcast i8* %ptr to i32**
-  store i32* %arg1, i32** %ptr_cast
-  ret i32** %ptr_cast
-}
-; CHECK-LABEL: Function: test_return_ref_arg
-; CHECK: MayAlias: i32* %a, i32* %lb
-; CHECK: NoAlias: i32* %lb, i32** %p
-; CHECK: NoAlias: i32* %lb, i32** %b
-; CHECK: NoAlias: i32* %lp, i32** %p
-; CHECK: NoAlias: i32* %lp, i32** %b
-; CHECK: MayAlias: i32* %lb, i32* %lp
-
-; We could've proven the following facts if the analysis were inclusion-based:
-; NoAlias: i32** %b, i32** %p
-define void @test_return_ref_arg() {
-  %a = alloca i32, align 4
-  %p = alloca i32*, align 8
-
-  store i32* %a, i32** %p
-  %b = call i32** @return_ref_arg_callee(i32* %a)
-
-  %lb = load i32*, i32** %b
-  %lp = load i32*, i32** %p
-
-  ret void
-}
 

llvm/trunk/test/Analysis/CFLAliasAnalysis/interproc-ret-unknown.ll

-; This testcase ensures that CFL AA answers queries soundly when callee tries 
-; to return an unknown pointer
-
-; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
-; RUN: opt < %s -aa-pipeline=cfl-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
-
-@g = external global i32
-define i32* @return_unknown_callee(i32* %arg1, i32* %arg2) {
-  ret i32* @g
-}
-; CHECK-LABEL: Function: test_return_unknown
-; CHECK: NoAlias: i32* %a, i32* %b
-; CHECK: MayAlias: i32* %c, i32* %x
-; CHECK: NoAlias: i32* %a, i32* %c
-; CHECK: NoAlias: i32* %b, i32* %c
-define void @test_return_unknown(i32* %x) {
-  %a = alloca i32, align 4
-  %b = alloca i32, align 4
-
-  %c = call i32* @return_unknown_callee(i32* %a, i32* %b)
-
-  ret void
-}
-
-@g2 = external global i32*
-define i32** @return_unknown_callee2() {
-  ret i32** @g2
-}
-; CHECK-LABEL: Function: test_return_unknown2
-; CHECK: MayAlias: i32* %x, i32** %a
-; CHECK: MayAlias: i32* %b, i32* %x
-; CHECK: MayAlias: i32* %b, i32** %a
-define void @test_return_unknown2(i32* %x) {
-  %a = call i32** @return_unknown_callee2()
-  %b = load i32*, i32** %a
-
-  ret void
-}
 

llvm/trunk/test/Analysis/CFLAliasAnalysis/interproc-store-arg-multilevel.ll

-; This testcase ensures that CFL AA answers queries soundly when callee tries 
-; to mutate the memory pointed to by its parameters
-
-; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
-; RUN: opt < %s -aa-pipeline=cfl-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
-
-declare noalias i8* @malloc(i64)
-
-define void @store_arg_multilevel_callee(i32*** %arg1, i32* %arg2) {
-  %ptr = call noalias i8* @malloc(i64 8)
-  %ptr_cast = bitcast i8* %ptr to i32**
-  store i32* %arg2, i32** %ptr_cast
-  store i32** %ptr_cast, i32*** %arg1
-  ret void
-}
-; CHECK-LABEL: Function: test_store_arg_multilevel
-; CHECK: NoAlias: i32* %a, i32** %lpp
-; CHECK: NoAlias: i32* %b, i32** %lpp
-; CHECK: MayAlias: i32** %lpp, i32** %p
-; CHECK: MayAlias: i32* %a, i32* %lpp_deref
-; CHECK: MayAlias: i32* %b, i32* %lpp_deref
-; CHECK: NoAlias: i32* %lpp_deref, i32** %p
-; CHECK: NoAlias: i32* %lpp_deref, i32*** %pp
-; CHECK: NoAlias: i32* %lpp_deref, i32** %lpp
-; CHECK: MayAlias: i32* %a, i32* %lp
-; CHECK: NoAlias: i32* %lp, i32*** %pp
-; CHECK: NoAlias: i32* %lp, i32** %lpp
-; CHECK: MayAlias: i32* %lp, i32* %lpp_deref
-
-; We could've proven the following facts if the analysis were inclusion-based:
-; NoAlias: i32* %a, i32* %b
-; NoAlias: i32* %b, i32* %lp
-define void @test_store_arg_multilevel() {
-  %a = alloca i32, align 4
-  %b = alloca i32, align 4
-  %p = alloca i32*, align 8
-  %pp = alloca i32**, align 8
-
-  store i32* %a, i32** %p
-  store i32** %p, i32*** %pp
-  call void @store_arg_multilevel_callee(i32*** %pp, i32* %b)
-
-  %lpp = load i32**, i32*** %pp
-  %lpp_deref = load i32*, i32** %lpp
-  %lp = load i32*, i32** %p
-
-  ret void
-}
 

llvm/trunk/test/Analysis/CFLAliasAnalysis/interproc-store-arg-unknown.ll

-; This testcase ensures that CFL AA answers queries soundly when callee tries 
-; to mutate the memory pointed to by its parameters
-
-; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
-; RUN: opt < %s -aa-pipeline=cfl-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
-
-@g = external global i32
-
-define void @store_arg_unknown_callee(i32** %arg1) {
-  store i32* @g, i32** %arg1
-  ret void
-}
-; CHECK-LABEL: Function: test_store_arg_unknown
-; CHECK: NoAlias: i32* %x, i32** %p
-; CHECK: NoAlias: i32* %a, i32** %p
-; CHECK: NoAlias: i32* %b, i32** %p
-; CHECK: MayAlias: i32* %lp, i32* %x
-; CHECK: MayAlias: i32* %a, i32* %lp
-; CHECK: NoAlias: i32* %b, i32* %lp
-; CHECK: NoAlias: i32* %lp, i32** %p
-define void @test_store_arg_unknown(i32* %x) {
-  %a = alloca i32, align 4
-  %b = alloca i32, align 4
-  %p = alloca i32*, align 8
-
-  store i32* %a, i32** %p
-  call void @store_arg_unknown_callee(i32** %p)
-
-  %lp = load i32*, i32** %p
-
-  ret void
-}
 

llvm/trunk/test/Analysis/CFLAliasAnalysis/interproc-store-arg.ll

-; This testcase ensures that CFL AA answers queries soundly when callee tries 
-; to mutate the memory pointed to by its parameters
-
-; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
-; RUN: opt < %s -aa-pipeline=cfl-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
-
-define void @store_arg_callee(i32** %arg1, i32* %arg2) {
-  store i32* %arg2, i32** %arg1
-  ret void
-}
-; CHECK-LABEL: Function: test_store_arg
-; CHECK: NoAlias: i32* %a, i32** %p
-; CHECK: NoAlias: i32* %b, i32** %p
-; CHECK: MayAlias: i32* %a, i32* %lp
-; CHECK: MayAlias: i32* %b, i32* %lp
-; CHECK: MayAlias: i32* %b, i32* %lq
-; CHECK: MayAlias: i32* %lp, i32* %lq
-
-; We could've proven the following facts if the analysis were inclusion-based:
-; NoAlias: i32* %a, i32* %b
-; NoAlias: i32* %a, i32* %lq
-define void @test_store_arg() {
-  %a = alloca i32, align 4
-  %b = alloca i32, align 4
-  %p = alloca i32*, align 8
-  %q = alloca i32*, align 8
-
-  store i32* %a, i32** %p
-  store i32* %b, i32** %q
-  call void @store_arg_callee(i32** %p, i32* %b)
-
-  %lp = load i32*, i32** %p
-  %lq = load i32*, i32** %q
-
-  ret void
-}
 

llvm/trunk/test/Analysis/CFLAliasAnalysis/malloc-and-free.ll

-; This testcase ensures that CFL AA handles malloc and free in a sound and precise manner
-
-; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-no-aliases -disable-output 2>&1 | FileCheck %s
-; RUN: opt < %s -aa-pipeline=cfl-aa -passes=aa-eval -print-no-aliases -disable-output 2>&1 | FileCheck %s
-
-declare noalias i8* @malloc(i64)
-declare noalias i8* @calloc(i64, i64)
-declare void @free(i8* nocapture)
-
-; CHECK: Function: test_malloc
-; CHECK: NoAlias: i8* %p, i8* %q
-define void @test_malloc(i8* %p) {
-  %q = call i8* @malloc(i64 4)
-  ret void
-}
-
-; CHECK: Function: test_calloc
-; CHECK: NoAlias: i8* %p, i8* %q
-define void @test_calloc(i8* %p) {
-  %q = call i8* @calloc(i64 2, i64 4)
-  ret void
-}
-
-; CHECK: Function: test_free
-; CHECK: NoAlias: i8* %p, i8* %q
-define void @test_free(i8* %p) {
-  %q = alloca i8, align 4
-  call void @free(i8* %q)
-  ret void
-}

llvm/trunk/test/Analysis/CFLAliasAnalysis/multilevel-combine.ll

-; This testcase ensures that CFL AA responds conservatively when we union 
-; groups of pointers together through ternary/conditional operations
-; Derived from:
-; void foo(bool c) {
-;   char a, b;
-;   char *m = c ? &a : &b;
-;   *m;
-; }
-;
-
-; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s
-
-%T = type { i32, [10 x i8] }
-
-; CHECK:     Function: test
-
-define void @test(i1 %C) {
-; CHECK: 10 Total Alias Queries Performed
-; CHECK: 4 no alias responses
-  %M = alloca %T*, align 8 ; NoAlias with %A, %B, %MS, %AP
-  %A = alloca %T, align 8
-  %B = alloca %T, align 8
-
-  %MS = select i1 %C, %T* %B, %T* %A
-
-  store %T* %MS, %T** %M
-
-  %AP = load %T*, %T** %M ; PartialAlias with %A, %B
-
-  ret void
-}

llvm/trunk/test/Analysis/CFLAliasAnalysis/multilevel.ll

-; This testcase ensures that CFL AA handles trivial cases with storing 
-; pointers in pointers appropriately.
-; Derived from:
-; char a, b;
-; char *m = &a, *n = &b;
-; *m;
-; *n;
-
-; RUN: opt < %s -cfl-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s
-
-%T = type { i32, [10 x i8] }
-
-; CHECK:     Function: test
-
-define void @test() {
-; CHECK: 15 Total Alias Queries Performed
-; CHECK: 13 no alias responses
-  %M = alloca %T*, align 8
-  %N = alloca %T*, align 8
-  %A = alloca %T, align 8
-  %B = alloca %T, align 8
-
-  store %T* %A, %T** %M
-  store %T* %B, %T** %N
-
-  %AP = load %T*, %T** %M ; PartialAlias with %A
-  %BP = load %T*, %T** %N ; PartialAlias with %B
-
-  ret void
-}

llvm/trunk/test/Analysis/CFLAliasAnalysis/must-and-partial.ll

-; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-all-alias-modref-info 2>&1 | FileCheck %s
-; When merging MustAlias and PartialAlias, merge to PartialAlias
-; instead of MayAlias.
-
-
-target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"
-
-; FIXME: This could be PartialAlias but CFLAA can't currently prove it
-; CHECK: MayAlias:  i16* %bigbase0, i8* %phi
-define i8 @test0(i1 %x) {
-entry:
-  %base = alloca i8, align 4
-  %baseplusone = getelementptr i8, i8* %base, i64 1
-  br i1 %x, label %red, label %green
-red:
-  br label %green
-green:
-  %phi = phi i8* [ %baseplusone, %red ], [ %base, %entry ]
-  store i8 0, i8* %phi
-
-  %bigbase0 = bitcast i8* %base to i16*
-  store i16 -1, i16* %bigbase0
-
-  %loaded = load i8, i8* %phi
-  ret i8 %loaded
-}
-
-; FIXME: This could be PartialAlias but CFLAA can't currently prove it
-; CHECK: MayAlias:  i16* %bigbase1, i8* %sel
-define i8 @test1(i1 %x) {
-entry:
-  %base = alloca i8, align 4
-  %baseplusone = getelementptr i8, i8* %base, i64 1
-  %sel = select i1 %x, i8* %baseplusone, i8* %base
-  store i8 0, i8* %sel
-
-  %bigbase1 = bitcast i8* %base to i16*
-  store i16 -1, i16* %bigbase1
-
-  %loaded = load i8, i8* %sel
-  ret i8 %loaded
-}
-
-; Incoming pointer arguments should not be PartialAlias because we do not know their initial state
-; even if they are nocapture
-; CHECK: MayAlias:  double* %A, double* %Index
-define void @testr2(double* nocapture readonly %A, double* nocapture readonly %Index) {
-  %arrayidx22 = getelementptr inbounds double, double* %Index, i64 2
-  %1 = load double, double* %arrayidx22
-  %arrayidx25 = getelementptr inbounds double, double* %A, i64 2
-  %2 = load double, double* %arrayidx25
-  %mul26 = fmul double %1, %2
-  ret void
-}

llvm/trunk/test/Analysis/CFLAliasAnalysis/opaque-call-alias.ll

-; We previously had a case where we would put results from a no-args call in
-; its own stratified set. This would make cases like the one in @test say that
-; nothing (except %Escapes and %Arg) can alias
-
-; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
-
-; CHECK:     Function: test
-; CHECK:     NoAlias: i8* %Arg, i8* %Escapes
-; CHECK:     MayAlias: i8* %Arg, i8* %Retrieved
-; CHECK:     MayAlias: i8* %Escapes, i8* %Retrieved
-define void @test(i8* %Arg) {
-  %Noalias = alloca i8
-  %Escapes = alloca i8
-  call void @set_thepointer(i8* %Escapes)
-  %Retrieved = call i8* @get_thepointer()
-  ret void
-}
-
-declare void @set_thepointer(i8* %P)
-declare i8* @get_thepointer()

llvm/trunk/test/Analysis/CFLAliasAnalysis/phi-and-select.ll

-; RUN: opt < %s -cfl-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
-; Derived from (a subset of) BasicAA/phi-and-select.ll 
-
-; CHECK: Function: qux
-; CHECK:  NoAlias: double* %a, double* %b
-; CHECK: ===== Alias Analysis Evaluator Report =====
-
-; Two PHIs with disjoint sets of inputs.
-define void @qux(i1 %m, double* noalias %x, double* noalias %y,
-                 i1 %n, double* noalias %v, double* noalias %w) {
-entry:
-  br i1 %m, label %true, label %false
-
-true:
-  br label %exit
-
-false:
-  br label %exit
-
-exit:
-  %a = phi double* [ %x, %true ], [ %y, %false ]
-  br i1 %n, label %ntrue, label %nfalse
-
-ntrue:
-  br label %nexit
-
-nfalse:
-  br label %nexit
-
-nexit:
-  %b = phi double* [ %v, %ntrue ], [ %w, %nfalse ]
-  store volatile double 0.0, double* %a
-  store volatile double 1.0, double* %b
-  ret void
-}
-

llvm/trunk/test/Analysis/CFLAliasAnalysis/pr27213.ll

-; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s
-; RUN: opt < %s -aa-pipeline=cfl-aa -passes=aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s
-
-; CHECK-LABEL:     Function: foo
-; CHECK: MayAlias: i32* %A, i32* %B
-define void @foo(i32* %A, i32* %B) {
-entry:
-  store i32 0, i32* %A, align 4
-  store i32 0, i32* %B, align 4
-  ret void
-}
-
-; CHECK-LABEL:     Function: bar
-; CHECK: MayAlias: i32* %A, i32* %B
-; CHECK: MayAlias: i32* %A, i32* %arrayidx
-; CHECK: MayAlias: i32* %B, i32* %arrayidx
-define void @bar(i32* %A, i32* %B) {
-entry:
-  store i32 0, i32* %A, align 4
-  %arrayidx = getelementptr inbounds i32, i32* %B, i64 1
-  store i32 0, i32* %arrayidx, align 4
-  ret void
-}
-
-@G = global i32 0
-
-; CHECK-LABEL:     Function: baz
-; CHECK: MayAlias: i32* %A, i32* @G
-define void @baz(i32* %A) {
-entry:
-  store i32 0, i32* %A, align 4
-  store i32 0, i32* @G, align 4
-  ret void
-}
-
-; CHECK-LABEL: Alias Analysis Evaluator Report
-; CHECK: 5 Total Alias Queries Performed
-; CHECK: 0 no alias responses
-; CHECK: 5 may alias responses

llvm/trunk/test/Analysis/CFLAliasAnalysis/simple.ll

-; This testcase consists of alias relations which should be completely
-; resolvable by cfl-aa (derived from BasicAA/2003-11-04-SimpleCases.ll).
-
-; RUN: opt < %s -cfl-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s
-
-%T = type { i32, [10 x i8] }
-
-; CHECK:     Function: test
-; CHECK-NOT:   May:
-
-define void @test(%T* %P) {
-  %A = getelementptr %T, %T* %P, i64 0
-  %B = getelementptr %T, %T* %P, i64 0, i32 0
-  %C = getelementptr %T, %T* %P, i64 0, i32 1
-  %D = getelementptr %T, %T* %P, i64 0, i32 1, i64 0
-  %E = getelementptr %T, %T* %P, i64 0, i32 1, i64 5
-  ret void
-}

llvm/trunk/test/Analysis/CFLAliasAnalysis/stratified-attrs-indexing.ll

-; This testcase ensures that CFLAA doesn't try to access out of bounds indices
-; when given functions with large amounts of arguments (specifically, more
-; arguments than the StratifiedAttrs bitset can handle)
-;
-; Because the result on failure is effectively crashing the compiler, output
-; checking is minimal.
-
-; RUN: opt < %s -cfl-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s
-
-; CHECK: Function: test
-define void @test(i1 %cond,
-                  i32* %arg1, i32* %arg2, i32* %arg3, i32* %arg4, i32* %arg5,
-                  i32* %arg6, i32* %arg7, i32* %arg8, i32* %arg9, i32* %arg10,
-                  i32* %arg11, i32* %arg12, i32* %arg13, i32* %arg14, i32* %arg15,
-                  i32* %arg16, i32* %arg17, i32* %arg18, i32* %arg19, i32* %arg20,
-                  i32* %arg21, i32* %arg22, i32* %arg23, i32* %arg24, i32* %arg25,
-                  i32* %arg26, i32* %arg27, i32* %arg28, i32* %arg29, i32* %arg30,
-                  i32* %arg31, i32* %arg32, i32* %arg33, i32* %arg34, i32* %arg35) {
-
-  ; CHECK: 946 Total Alias Queries Performed
-  ; CHECK: 43 no alias responses (4.5%)
-  %a = alloca i32, align 4
-  %b = select i1 %cond, i32* %arg35, i32* %arg34
-  %c = select i1 %cond, i32* %arg34, i32* %arg33
-  %d = select i1 %cond, i32* %arg33, i32* %arg32
-  %e = select i1 %cond, i32* %arg32, i32* %arg31
-  %f = select i1 %cond, i32* %arg31, i32* %arg30
-  %g = select i1 %cond, i32* %arg30, i32* %arg29
-  %h = select i1 %cond, i32* %arg29, i32* %arg28
-  %i = select i1 %cond, i32* %arg28, i32* %arg27
-
-  ret void
-}

llvm/trunk/test/Analysis/CFLAliasAnalysis/va.ll

-; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
-
-; CHECK-LABEL: Function: test1
-; CHECK: MayAlias: i32* %X, i32* %tmp
-; CHECK: MayAlias: i32* %tmp, i8** %ap
-; CHECK: NoAlias: i8** %ap, i8** %aq
-; CHECK: MayAlias: i32* %tmp, i8** %aq
-
-define i32* @test1(i32* %X, ...) {
-  ; Initialize variable argument processing
-  %ap = alloca i8*
-  %ap2 = bitcast i8** %ap to i8*
-  call void @llvm.va_start(i8* %ap2)
-
-  ; Read a single pointer argument
-  %tmp = va_arg i8** %ap, i32*
-
-  ; Demonstrate usage of llvm.va_copy and llvm.va_end
-  %aq = alloca i8*
-  %aq2 = bitcast i8** %aq to i8*
-  call void @llvm.va_copy(i8* %aq2, i8* %ap2)
-  call void @llvm.va_end(i8* %aq2)
-
-  ; Stop processing of arguments.
-  call void @llvm.va_end(i8* %ap2)
-  ret i32* %tmp
-}
-
-declare void @llvm.va_start(i8*)
-declare void @llvm.va_copy(i8*, i8*)
-declare void @llvm.va_end(i8*)
-