[AA] Remove CFL AA passes

[nikic]

Summary

The CFL Steens/Anders alias analysis passes are not enabled by default, and to the best of my knowledge have no pathway towards ever being enabled by default. The last significant interest in these passes seems to date back to 2016. Given the little maintenance these have seen in recent times, I also have very little confidence in the correctness of these passes. I don't think we should keep these in-tree.

[jdoerfert]

I'm happy with this. It was effectively dead.

[reames]

LGTM, removing dead code is always worthwhile.

[george.burgess.iv]

+1 - thanks for the cleanup :)

[fhahn]

LGTM, thanks for the cleanup!

clang/docs/tools/clang-formatted-files.txt

 llvm/include/llvm/ADT/Sequence.h
 llvm/include/llvm/ADT/simple_ilist.h
 llvm/include/llvm/ADT/Statistic.h
 llvm/include/llvm/ADT/STLArrayExtras.h
 llvm/include/llvm/ADT/STLForwardCompat.h
 llvm/include/llvm/ADT/StringSet.h
 llvm/include/llvm/ADT/TypeSwitch.h
 llvm/include/llvm/Analysis/BlockFrequencyInfo.h
-llvm/include/llvm/Analysis/CFLAliasAnalysisUtils.h
-llvm/include/llvm/Analysis/CFLAndersAliasAnalysis.h
-llvm/include/llvm/Analysis/CFLSteensAliasAnalysis.h
 llvm/include/llvm/Analysis/ConstraintSystem.h
 llvm/include/llvm/Analysis/CostModel.h
 llvm/include/llvm/Analysis/CycleAnalysis.h
 llvm/include/llvm/Analysis/DDGPrinter.h
 llvm/include/llvm/Analysis/Delinearization.h
 llvm/include/llvm/Analysis/DependenceGraphBuilder.h
 llvm/include/llvm/Analysis/DivergenceAnalysis.h
 llvm/include/llvm/Analysis/DomTreeUpdater.h

 llvm/include/llvm-c/IRReader.h
 llvm/include/llvm-c/LLJIT.h
 llvm/include/llvm-c/OrcEE.h
 llvm/include/llvm-c/Remarks.h
 llvm/include/llvm-c/Types.h
 llvm/include/llvm-c/Transforms/PassBuilder.h
 llvm/include/llvm-c/Transforms/Scalar.h
 llvm/include/llvm-c/Transforms/Vectorize.h
-llvm/lib/Analysis/CFLAndersAliasAnalysis.cpp
-llvm/lib/Analysis/CFLGraph.h
-llvm/lib/Analysis/CFLSteensAliasAnalysis.cpp
 llvm/lib/Analysis/CodeMetrics.cpp
 llvm/lib/Analysis/CycleAnalysis.cpp
 llvm/lib/Analysis/DDGPrinter.cpp
 llvm/lib/Analysis/Delinearization.cpp
 llvm/lib/Analysis/DependenceGraphBuilder.cpp
 llvm/lib/Analysis/DevelopmentModeInlineAdvisor.cpp
 llvm/lib/Analysis/DivergenceAnalysis.cpp
 llvm/lib/Analysis/DomTreeUpdater.cpp

llvm/include/llvm/Analysis/CFLAliasAnalysisUtils.h

-//=- CFLAliasAnalysisUtils.h - Utilities for CFL Alias Analysis ----*- C++-*-=//
-//
-// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
-// See https://llvm.org/LICENSE.txt for license information.
-// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
-//
-//===----------------------------------------------------------------------===//
-// \file
-// These are the utilities/helpers used by the CFL Alias Analyses available in
-// tree, i.e. Steensgaard's and Andersens'.
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_ANALYSIS_CFLALIASANALYSISUTILS_H
-#define LLVM_ANALYSIS_CFLALIASANALYSISUTILS_H
-
-#include "llvm/IR/Argument.h"
-#include "llvm/IR/Function.h"
-#include "llvm/IR/ValueHandle.h"
-
-namespace llvm {
-
-namespace cflaa {
-
-template <typename AAResult> struct FunctionHandle final : public CallbackVH {
-  FunctionHandle(Function *Fn, AAResult *Result)
-      : CallbackVH(Fn), Result(Result) {
-    assert(Fn != nullptr);
-    assert(Result != nullptr);
-  }
-
-  void deleted() override { removeSelfFromCache(); }
-  void allUsesReplacedWith(Value *) override { removeSelfFromCache(); }
-
-private:
-  AAResult *Result;
-
-  void removeSelfFromCache() {
-    assert(Result != nullptr);
-    auto *Val = getValPtr();
-    Result->evict(cast<Function>(Val));
-    setValPtr(nullptr);
-  }
-};
-
-static inline const Function *parentFunctionOfValue(const Value *Val) {
-  if (auto *Inst = dyn_cast<Instruction>(Val)) {
-    auto *Bb = Inst->getParent();
-    return Bb->getParent();
-  }
-
-  if (auto *Arg = dyn_cast<Argument>(Val))
-    return Arg->getParent();
-  return nullptr;
-}
-} // namespace cflaa
-} // namespace llvm
-
-#endif // LLVM_ANALYSIS_CFLALIASANALYSISUTILS_H

llvm/include/llvm/Analysis/CFLAndersAliasAnalysis.h

-//==- CFLAndersAliasAnalysis.h - Unification-based Alias Analysis -*- C++-*-==//
-//
-// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
-// See https://llvm.org/LICENSE.txt for license information.
-// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
-//
-//===----------------------------------------------------------------------===//
-/// \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/ADT/DenseMap.h"
-#include "llvm/Analysis/AliasAnalysis.h"
-#include "llvm/Analysis/CFLAliasAnalysisUtils.h"
-#include "llvm/IR/PassManager.h"
-#include "llvm/Pass.h"
-#include <forward_list>
-#include <memory>
-
-namespace llvm {
-
-template <typename T> class Optional;
-class Function;
-class MemoryLocation;
-class TargetLibraryInfo;
-
-namespace cflaa {
-
-struct AliasSummary;
-
-} // end namespace cflaa
-
-class CFLAndersAAResult : public AAResultBase {
-  class FunctionInfo;
-
-public:
-  explicit CFLAndersAAResult(
-      std::function<const TargetLibraryInfo &(Function &F)> GetTLI);
-  CFLAndersAAResult(CFLAndersAAResult &&RHS);
-  ~CFLAndersAAResult();
-
-  /// Handle invalidation events from the new pass manager.
-  /// By definition, this result is stateless and so remains valid.
-  bool invalidate(Function &, const PreservedAnalyses &,
-                  FunctionAnalysisManager::Invalidator &) {
-    return false;
-  }
-
-  /// Evict the given function from cache
-  void evict(const Function *Fn);
-
-  /// Get the alias summary for the given function
-  /// Return nullptr if the summary is not found or not available
-  const cflaa::AliasSummary *getAliasSummary(const Function &);
-
-  AliasResult query(const MemoryLocation &, const MemoryLocation &);
-  AliasResult alias(const MemoryLocation &, const MemoryLocation &,
-                    AAQueryInfo &);
-
-private:
-  /// Ensures that the given function is available in the cache.
-  /// Returns the appropriate entry from the cache.
-  const Optional<FunctionInfo> &ensureCached(const Function &);
-
-  /// Inserts the given Function into the cache.
-  void scan(const Function &);
-
-  /// Build summary for a given function
-  FunctionInfo buildInfoFrom(const Function &);
-
-  std::function<const TargetLibraryInfo &(Function &F)> GetTLI;
-
-  /// Cached mapping of Functions to their StratifiedSets.
-  /// If a function's sets are currently being built, it is marked
-  /// in the cache as an Optional without a value. This way, if we
-  /// have any kind of recursion, it is discernable from a function
-  /// that simply has empty sets.
-  DenseMap<const Function *, Optional<FunctionInfo>> Cache;
-
-  std::forward_list<cflaa::FunctionHandle<CFLAndersAAResult>> Handles;
-};
-
-/// 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 AnalysisKey Key;
-
-public:
-  using Result = CFLAndersAAResult;
-
-  CFLAndersAAResult run(Function &F, FunctionAnalysisManager &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();
-
-} // end namespace llvm
-
-#endif // LLVM_ANALYSIS_CFLANDERSALIASANALYSIS_H

llvm/include/llvm/Analysis/CFLSteensAliasAnalysis.h

-//==- CFLSteensAliasAnalysis.h - Unification-based Alias Analysis -*- C++-*-==//
-//
-// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
-// See https://llvm.org/LICENSE.txt for license information.
-// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
-//
-//===----------------------------------------------------------------------===//
-/// \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/Analysis/AliasAnalysis.h"
-#include "llvm/Analysis/CFLAliasAnalysisUtils.h"
-#include "llvm/Analysis/MemoryLocation.h"
-#include "llvm/IR/PassManager.h"
-#include "llvm/Pass.h"
-#include <forward_list>
-#include <memory>
-
-namespace llvm {
-
-class Function;
-class TargetLibraryInfo;
-
-namespace cflaa {
-
-struct AliasSummary;
-
-} // end namespace cflaa
-
-class CFLSteensAAResult : public AAResultBase {
-  class FunctionInfo;
-
-public:
-  explicit CFLSteensAAResult(
-      std::function<const TargetLibraryInfo &(Function &)> GetTLI);
-  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 &,
-                  FunctionAnalysisManager::Invalidator &) {
-    return false;
-  }
-
-  /// Inserts the given Function into the cache.
-  void scan(Function *Fn);
-
-  void evict(Function *Fn);
-
-  /// Ensures that the given function is available in the cache.
-  /// Returns the appropriate entry from the cache.
-  const Optional<FunctionInfo> &ensureCached(Function *Fn);
-
-  /// Get the alias summary for the given function
-  /// Return nullptr if the summary is not found or not available
-  const cflaa::AliasSummary *getAliasSummary(Function &Fn);
-
-  AliasResult query(const MemoryLocation &LocA, const MemoryLocation &LocB);
-
-  AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB,
-                    AAQueryInfo &AAQI) {
-    if (LocA.Ptr == LocB.Ptr)
-      return AliasResult::MustAlias;
-
-    // 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, AAQI);
-
-    AliasResult QueryResult = query(LocA, LocB);
-    if (QueryResult == AliasResult::MayAlias)
-      return AAResultBase::alias(LocA, LocB, AAQI);
-
-    return QueryResult;
-  }
-
-private:
-  std::function<const TargetLibraryInfo &(Function &)> GetTLI;
-
-  /// 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<cflaa::FunctionHandle<CFLSteensAAResult>> 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 AnalysisKey Key;
-
-public:
-  using Result = CFLSteensAAResult;
-
-  CFLSteensAAResult run(Function &F, FunctionAnalysisManager &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();
-
-} // end namespace llvm
-
-#endif // LLVM_ANALYSIS_CFLSTEENSALIASANALYSIS_H

llvm/include/llvm/CodeGen/CodeGenPassBuilder.h

 
 #ifndef LLVM_CODEGEN_CODEGENPASSBUILDER_H
 #define LLVM_CODEGEN_CODEGENPASSBUILDER_H
 
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/BasicAliasAnalysis.h"
-#include "llvm/Analysis/CFLAndersAliasAnalysis.h"
-#include "llvm/Analysis/CFLSteensAliasAnalysis.h"
 #include "llvm/Analysis/ScopedNoAliasAA.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/Analysis/TypeBasedAliasAnalysis.h"
 #include "llvm/CodeGen/ExpandReductions.h"
 #include "llvm/CodeGen/MachinePassManager.h"
 #include "llvm/CodeGen/PreISelIntrinsicLowering.h"
 #include "llvm/CodeGen/ReplaceWithVeclib.h"
 #include "llvm/CodeGen/UnreachableBlockElim.h"
derived().addAsmPrinter(
       addPass, [this, &Out, DwoOut, FileType](MCContext &Ctx) {
         return this->TM.createMCStreamer(Out, DwoOut, FileType, Ctx);
       });
 
   addPass(FreeMachineFunctionPass());
   return Error::success();
 }
 
-static inline AAManager registerAAAnalyses(CFLAAType UseCFLAA) {
+static inline AAManager registerAAAnalyses() {
   AAManager AA;
 
   // The order in which these are registered determines their priority when
   // being queried.
 
-  switch (UseCFLAA) {
-  case CFLAAType::Steensgaard:
-    AA.registerFunctionAnalysis<CFLSteensAA>();
-    break;
-  case CFLAAType::Andersen:
-    AA.registerFunctionAnalysis<CFLAndersAA>();
-    break;
-  case CFLAAType::Both:
-    AA.registerFunctionAnalysis<CFLAndersAA>();
-    AA.registerFunctionAnalysis<CFLSteensAA>();
-    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.
   AA.registerFunctionAnalysis<TypeBasedAA>();
   AA.registerFunctionAnalysis<ScopedNoAliasAA>();
   AA.registerFunctionAnalysis<BasicAA>();
 
   return AA;
 }
 
 template <typename Derived>
 void CodeGenPassBuilder<Derived>::registerModuleAnalyses(
     ModuleAnalysisManager &MAM) const {
 #define MODULE_ANALYSIS(NAME, PASS_NAME, CONSTRUCTOR)                          \
   MAM.registerPass([&] { return PASS_NAME CONSTRUCTOR; });
 #include "MachinePassRegistry.def"
   derived().registerTargetAnalysis(MAM);
 }
 
 template <typename Derived>
 void CodeGenPassBuilder<Derived>::registerFunctionAnalyses(
     FunctionAnalysisManager &FAM) const {
-  FAM.registerPass([this] { return registerAAAnalyses(this->Opt.UseCFLAA); });
+  FAM.registerPass([this] { return registerAAAnalyses(); });
 
 #define FUNCTION_ANALYSIS(NAME, PASS_NAME, CONSTRUCTOR)                        \
   FAM.registerPass([&] { return PASS_NAME CONSTRUCTOR; });
 #include "MachinePassRegistry.def"
   derived().registerTargetAnalysis(FAM);
 }
 
 template <typename Derived>

llvm/include/llvm/InitializePasses.h

 void initializeCFGOnlyViewerLegacyPassPass(PassRegistry&);
 void initializeCFGPrinterLegacyPassPass(PassRegistry&);
 void initializeCFGSimplifyPassPass(PassRegistry&);
 void initializeCFGuardPass(PassRegistry&);
 void initializeCFGuardLongjmpPass(PassRegistry&);
 void initializeCFGViewerLegacyPassPass(PassRegistry&);
 void initializeCFIFixupPass(PassRegistry&);
 void initializeCFIInstrInserterPass(PassRegistry&);
-void initializeCFLAndersAAWrapperPassPass(PassRegistry&);
-void initializeCFLSteensAAWrapperPassPass(PassRegistry&);
 void initializeCallGraphDOTPrinterPass(PassRegistry&);
 void initializeCallGraphPrinterLegacyPassPass(PassRegistry&);
 void initializeCallGraphViewerPass(PassRegistry&);
 void initializeCallGraphWrapperPassPass(PassRegistry&);
 void initializeCallSiteSplittingLegacyPassPass(PassRegistry&);
 void initializeCalledValuePropagationLegacyPassPass(PassRegistry &);
 void initializeCheckDebugMachineModulePass(PassRegistry &);
 void initializeCodeGenPreparePass(PassRegistry&);

llvm/include/llvm/LinkAllPasses.h

 
 #ifndef LLVM_LINKALLPASSES_H
 #define LLVM_LINKALLPASSES_H
 
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AliasAnalysisEvaluator.h"
 #include "llvm/Analysis/AliasSetTracker.h"
 #include "llvm/Analysis/BasicAliasAnalysis.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::createBasicAAWrapperPass();
       (void) llvm::createSCEVAAWrapperPass();
       (void) llvm::createTypeBasedAAWrapperPass();
       (void) llvm::createScopedNoAliasAAWrapperPass();
       (void) llvm::createBreakCriticalEdgesPass();
       (void) llvm::createCallGraphDOTPrinterPass();
       (void) llvm::createCallGraphViewerPass();
       (void) llvm::createCFGSimplificationPass();
-      (void) llvm::createCFLAndersAAWrapperPass();
-      (void) llvm::createCFLSteensAAWrapperPass();
       (void) llvm::createStructurizeCFGPass();
       (void) llvm::createLibCallsShrinkWrapPass();
       (void) llvm::createCalledValuePropagationPass();
       (void) llvm::createConstantMergePass();
       (void) llvm::createCostModelAnalysisPass();
       (void) llvm::createDeadArgEliminationPass();
       (void) llvm::createDeadCodeEliminationPass();
       (void) llvm::createDeadStoreEliminationPass();

llvm/include/llvm/Target/CGPassBuilderOption.h

 #include "llvm/ADT/StringRef.h"
 #include "llvm/Target/TargetOptions.h"
 #include <optional>
 
 namespace llvm {
 
 enum class RunOutliner { TargetDefault, AlwaysOutline, NeverOutline };
 enum class RegAllocType { Default, Basic, Fast, Greedy, PBQP };
-enum class CFLAAType { None, Steensgaard, Andersen, Both };
 
 // Not one-on-one but mostly corresponding to commandline options in
 // TargetPassConfig.cpp.
 struct CGPassBuilderOption {
   std::optional<bool> OptimizeRegAlloc;
   std::optional<bool> EnableIPRA;
   bool DebugPM = false;
   bool DisableVerify = false;
struct CGPassBuilderOption {
   bool DisableConstantHoisting = false;
   bool DisableSelectOptimize = true;
   bool PrintISelInput = false;
   bool PrintGCInfo = false;
   bool RequiresCodeGenSCCOrder = false;
 
   RunOutliner EnableMachineOutliner = RunOutliner::TargetDefault;
   RegAllocType RegAlloc = RegAllocType::Default;
-  CFLAAType UseCFLAA = CFLAAType::None;
   std::optional<GlobalISelAbortMode> EnableGlobalISelAbort;
 
   std::optional<bool> VerifyMachineCode;
   std::optional<bool> EnableFastISelOption;
   std::optional<bool> EnableGlobalISelOption;
 };
 
 CGPassBuilderOption getCGPassBuilderOption();
 
 } // namespace llvm
 
 #endif // LLVM_TARGET_CGPASSBUILDEROPTION_H

llvm/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/ADT/Statistic.h"
 #include "llvm/Analysis/BasicAliasAnalysis.h"
-#include "llvm/Analysis/CFLAndersAliasAnalysis.h"
-#include "llvm/Analysis/CFLSteensAliasAnalysis.h"
 #include "llvm/Analysis/CaptureTracking.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/MemoryLocation.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"
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(CFLAndersAAWrapperPass)
-INITIALIZE_PASS_DEPENDENCY(CFLSteensAAWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(ExternalAAWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(SCEVAAWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(ScopedNoAliasAAWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(TypeBasedAAWrapperPass)
 INITIALIZE_PASS_END(AAResultsWrapperPass, "aa",
                     "Function Alias Analysis Results", false, true)
 
bool AAResultsWrapperPass::runOnFunction(Function &F) {
   if (auto *WrapperPass = getAnalysisIfAvailable<ScopedNoAliasAAWrapperPass>())
     AAR->addAAResult(WrapperPass->getResult());
   if (auto *WrapperPass = getAnalysisIfAvailable<TypeBasedAAWrapperPass>())
     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<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);
 
   // Analyses don't mutate the IR, so return false.
   return false;
 }
 
 void AAResultsWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.setPreservesAll();
   AU.addRequiredTransitive<BasicAAWrapperPass>();
   AU.addRequiredTransitive<TargetLibraryInfoWrapperPass>();
 
   // We also need to mark all the alias analysis passes we will potentially
   // 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<GlobalsAAWrapperPass>();
   AU.addUsedIfAvailable<SCEVAAWrapperPass>();
-  AU.addUsedIfAvailable<CFLAndersAAWrapperPass>();
-  AU.addUsedIfAvailable<CFLSteensAAWrapperPass>();
   AU.addUsedIfAvailable<ExternalAAWrapperPass>();
 }
 
 AAManager::Result AAManager::run(Function &F, FunctionAnalysisManager &AM) {
   Result R(AM.getResult<TargetLibraryAnalysis>(F));
   for (auto &Getter : ResultGetters)
     (*Getter)(F, AM, R);
   return R;
AAResults llvm::createLegacyPMAAResults(Pass &P, Function &F,
   // 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<GlobalsAAWrapperPass>())
     AAR.addAAResult(WrapperPass->getResult());
-  if (auto *WrapperPass = P.getAnalysisIfAvailable<CFLAndersAAWrapperPass>())
-    AAR.addAAResult(WrapperPass->getResult());
-  if (auto *WrapperPass = P.getAnalysisIfAvailable<CFLSteensAAWrapperPass>())
-    AAR.addAAResult(WrapperPass->getResult());
   if (auto *WrapperPass = P.getAnalysisIfAvailable<ExternalAAWrapperPass>())
     if (WrapperPass->CB)
       WrapperPass->CB(P, F, AAR);
 
   return AAR;
 }
 
 bool llvm::isNoAliasCall(const Value *V) {

 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<GlobalsAAWrapperPass>();
-  AU.addUsedIfAvailable<CFLAndersAAWrapperPass>();
-  AU.addUsedIfAvailable<CFLSteensAAWrapperPass>();
   AU.addUsedIfAvailable<ExternalAAWrapperPass>();
 }

llvm/lib/Analysis/Analysis.cpp

void llvm::initializeAnalysis(PassRegistry &Registry) {
   initializeCallGraphDOTPrinterPass(Registry);
   initializeCallGraphPrinterLegacyPassPass(Registry);
   initializeCallGraphViewerPass(Registry);
   initializeCostModelAnalysisPass(Registry);
   initializeCFGViewerLegacyPassPass(Registry);
   initializeCFGPrinterLegacyPassPass(Registry);
   initializeCFGOnlyViewerLegacyPassPass(Registry);
   initializeCFGOnlyPrinterLegacyPassPass(Registry);
-  initializeCFLAndersAAWrapperPassPass(Registry);
-  initializeCFLSteensAAWrapperPassPass(Registry);
   initializeCycleInfoWrapperPassPass(Registry);
   initializeDependenceAnalysisWrapperPassPass(Registry);
   initializeDelinearizationPass(Registry);
   initializeDemandedBitsWrapperPassPass(Registry);
   initializeDominanceFrontierWrapperPassPass(Registry);
   initializeDomViewerWrapperPassPass(Registry);
   initializeDomPrinterWrapperPassPass(Registry);
   initializeDomOnlyViewerWrapperPassPass(Registry);

llvm/lib/Analysis/CFLAndersAliasAnalysis.cpp

-//===- CFLAndersAliasAnalysis.cpp - Unification-based Alias Analysis ------===//
-//
-// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
-// See https://llvm.org/LICENSE.txt for license information.
-// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
-//
-//===----------------------------------------------------------------------===//
-//
-// 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.
-//
-// The algorithm used here is based on recursive state machine matching scheme
-// proposed in "Demand-driven alias analysis for C" by Xin Zheng and Radu
-// Rugina. The general idea is to extend the traditional transitive closure
-// algorithm to perform CFL matching along the way: instead of recording
-// "whether X is reachable from Y", we keep track of "whether X is reachable
-// from Y at state Z", where the "state" field indicates where we are in the CFL
-// matching process. To understand the matching better, it is advisable to have
-// the state machine shown in Figure 3 of the paper available when reading the
-// codes: all we do here is to selectively expand the transitive closure by
-// discarding edges that are not recognized by the state machine.
-//
-// There are two differences between our current implementation and the one
-// described in the paper:
-// - Our algorithm eagerly computes all alias pairs after the CFLGraph is built,
-// while in the paper the authors did the computation in a demand-driven
-// fashion. We did not implement the demand-driven algorithm due to the
-// additional coding complexity and higher memory profile, but if we found it
-// necessary we may switch to it eventually.
-// - In the paper the authors use a state machine that does not distinguish
-// value reads from value writes. For example, if Y is reachable from X at state
-// S3, it may be the case that X is written into Y, or it may be the case that
-// there's a third value Z that writes into both X and Y. To make that
-// distinction (which is crucial in building function summary as well as
-// retrieving mod-ref info), we choose to duplicate some of the states in the
-// paper's proposed state machine. The duplication does not change the set the
-// machine accepts. Given a pair of reachable values, it only provides more
-// detailed information on which value is being written into and which is being
-// read from.
-//
-//===----------------------------------------------------------------------===//
-
-// 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 "AliasAnalysisSummary.h"
-#include "CFLGraph.h"
-#include "llvm/ADT/DenseMap.h"
-#include "llvm/ADT/DenseMapInfo.h"
-#include "llvm/ADT/DenseSet.h"
-#include "llvm/ADT/Optional.h"
-#include "llvm/ADT/STLExtras.h"
-#include "llvm/ADT/SmallVector.h"
-#include "llvm/ADT/iterator_range.h"
-#include "llvm/Analysis/AliasAnalysis.h"
-#include "llvm/Analysis/MemoryLocation.h"
-#include "llvm/IR/Argument.h"
-#include "llvm/IR/Function.h"
-#include "llvm/IR/PassManager.h"
-#include "llvm/IR/Type.h"
-#include "llvm/InitializePasses.h"
-#include "llvm/Pass.h"
-#include "llvm/Support/Casting.h"
-#include "llvm/Support/Compiler.h"
-#include "llvm/Support/Debug.h"
-#include "llvm/Support/raw_ostream.h"
-#include <algorithm>
-#include <bitset>
-#include <cassert>
-#include <cstddef>
-#include <cstdint>
-#include <functional>
-#include <optional>
-#include <utility>
-#include <vector>
-
-using namespace llvm;
-using namespace llvm::cflaa;
-
-#define DEBUG_TYPE "cfl-anders-aa"
-
-CFLAndersAAResult::CFLAndersAAResult(
-    std::function<const TargetLibraryInfo &(Function &F)> GetTLI)
-    : GetTLI(std::move(GetTLI)) {}
-CFLAndersAAResult::CFLAndersAAResult(CFLAndersAAResult &&RHS)
-    : AAResultBase(std::move(RHS)), GetTLI(std::move(RHS.GetTLI)) {}
-CFLAndersAAResult::~CFLAndersAAResult() = default;
-
-namespace {
-
-enum class MatchState : uint8_t {
-  // The following state represents S1 in the paper.
-  FlowFromReadOnly = 0,
-  // The following two states together represent S2 in the paper.
-  // The 'NoReadWrite' suffix indicates that there exists an alias path that
-  // does not contain assignment and reverse assignment edges.
-  // The 'ReadOnly' suffix indicates that there exists an alias path that
-  // contains reverse assignment edges only.
-  FlowFromMemAliasNoReadWrite,
-  FlowFromMemAliasReadOnly,
-  // The following two states together represent S3 in the paper.
-  // The 'WriteOnly' suffix indicates that there exists an alias path that
-  // contains assignment edges only.
-  // The 'ReadWrite' suffix indicates that there exists an alias path that
-  // contains both assignment and reverse assignment edges. Note that if X and Y
-  // are reachable at 'ReadWrite' state, it does NOT mean X is both read from
-  // and written to Y. Instead, it means that a third value Z is written to both
-  // X and Y.
-  FlowToWriteOnly,
-  FlowToReadWrite,
-  // The following two states together represent S4 in the paper.
-  FlowToMemAliasWriteOnly,
-  FlowToMemAliasReadWrite,
-};
-
-using StateSet = std::bitset<7>;
-
-const unsigned ReadOnlyStateMask =
-    (1U << static_cast<uint8_t>(MatchState::FlowFromReadOnly)) |
-    (1U << static_cast<uint8_t>(MatchState::FlowFromMemAliasReadOnly));
-const unsigned WriteOnlyStateMask =
-    (1U << static_cast<uint8_t>(MatchState::FlowToWriteOnly)) |
-    (1U << static_cast<uint8_t>(MatchState::FlowToMemAliasWriteOnly));
-
-// A pair that consists of a value and an offset
-struct OffsetValue {
-  const Value *Val;
-  int64_t Offset;
-};
-
-bool operator==(OffsetValue LHS, OffsetValue RHS) {
-  return LHS.Val == RHS.Val && LHS.Offset == RHS.Offset;
-}
-bool operator<(OffsetValue LHS, OffsetValue RHS) {
-  return std::less<const Value *>()(LHS.Val, RHS.Val) ||
-         (LHS.Val == RHS.Val && LHS.Offset < RHS.Offset);
-}
-
-// A pair that consists of an InstantiatedValue and an offset
-struct OffsetInstantiatedValue {
-  InstantiatedValue IVal;
-  int64_t Offset;
-};
-
-bool operator==(OffsetInstantiatedValue LHS, OffsetInstantiatedValue RHS) {
-  return LHS.IVal == RHS.IVal && LHS.Offset == RHS.Offset;
-}
-
-// We use ReachabilitySet to keep track of value aliases (The nonterminal "V" in
-// the paper) during the analysis.
-class ReachabilitySet {
-  using ValueStateMap = DenseMap<InstantiatedValue, StateSet>;
-  using ValueReachMap = DenseMap<InstantiatedValue, ValueStateMap>;
-
-  ValueReachMap ReachMap;
-
-public:
-  using const_valuestate_iterator = ValueStateMap::const_iterator;
-  using const_value_iterator = ValueReachMap::const_iterator;
-
-  // Insert edge 'From->To' at state 'State'
-  bool insert(InstantiatedValue From, InstantiatedValue To, MatchState State) {
-    assert(From != To);
-    auto &States = ReachMap[To][From];
-    auto Idx = static_cast<size_t>(State);
-    if (!States.test(Idx)) {
-      States.set(Idx);
-      return true;
-    }
-    return false;
-  }
-
-  // Return the set of all ('From', 'State') pair for a given node 'To'
-  iterator_range<const_valuestate_iterator>
-  reachableValueAliases(InstantiatedValue V) const {
-    auto Itr = ReachMap.find(V);
-    if (Itr == ReachMap.end())
-      return make_range<const_valuestate_iterator>(const_valuestate_iterator(),
-                                                   const_valuestate_iterator());
-    return make_range<const_valuestate_iterator>(Itr->second.begin(),
-                                                 Itr->second.end());
-  }
-
-  iterator_range<const_value_iterator> value_mappings() const {
-    return make_range<const_value_iterator>(ReachMap.begin(), ReachMap.end());
-  }
-};
-
-// We use AliasMemSet to keep track of all memory aliases (the nonterminal "M"
-// in the paper) during the analysis.
-class AliasMemSet {
-  using MemSet = DenseSet<InstantiatedValue>;
-  using MemMapType = DenseMap<InstantiatedValue, MemSet>;
-
-  MemMapType MemMap;
-
-public:
-  using const_mem_iterator = MemSet::const_iterator;
-
-  bool insert(InstantiatedValue LHS, InstantiatedValue RHS) {
-    // Top-level values can never be memory aliases because one cannot take the
-    // addresses of them
-    assert(LHS.DerefLevel > 0 && RHS.DerefLevel > 0);
-    return MemMap[LHS].insert(RHS).second;
-  }
-
-  const MemSet *getMemoryAliases(InstantiatedValue V) const {
-    auto Itr = MemMap.find(V);
-    if (Itr == MemMap.end())
-      return nullptr;
-    return &Itr->second;
-  }
-};
-
-// We use AliasAttrMap to keep track of the AliasAttr of each node.
-class AliasAttrMap {
-  using MapType = DenseMap<InstantiatedValue, AliasAttrs>;
-
-  MapType AttrMap;
-
-public:
-  using const_iterator = MapType::const_iterator;
-
-  bool add(InstantiatedValue V, AliasAttrs Attr) {
-    auto &OldAttr = AttrMap[V];
-    auto NewAttr = OldAttr | Attr;
-    if (OldAttr == NewAttr)
-      return false;
-    OldAttr = NewAttr;
-    return true;
-  }
-
-  AliasAttrs getAttrs(InstantiatedValue V) const {
-    AliasAttrs Attr;
-    auto Itr = AttrMap.find(V);
-    if (Itr != AttrMap.end())
-      Attr = Itr->second;
-    return Attr;
-  }
-
-  iterator_range<const_iterator> mappings() const {
-    return make_range<const_iterator>(AttrMap.begin(), AttrMap.end());
-  }
-};
-
-struct WorkListItem {
-  InstantiatedValue From;
-  InstantiatedValue To;
-  MatchState State;
-};
-
-struct ValueSummary {
-  struct Record {
-    InterfaceValue IValue;
-    unsigned DerefLevel;
-  };
-  SmallVector<Record, 4> FromRecords, ToRecords;
-};
-
-} // end anonymous namespace
-
-namespace llvm {
-
-// Specialize DenseMapInfo for OffsetValue.
-template <> struct DenseMapInfo<OffsetValue> {
-  static OffsetValue getEmptyKey() {
-    return OffsetValue{DenseMapInfo<const Value *>::getEmptyKey(),
-                       DenseMapInfo<int64_t>::getEmptyKey()};
-  }
-
-  static OffsetValue getTombstoneKey() {
-    return OffsetValue{DenseMapInfo<const Value *>::getTombstoneKey(),
-                       DenseMapInfo<int64_t>::getEmptyKey()};
-  }
-
-  static unsigned getHashValue(const OffsetValue &OVal) {
-    return DenseMapInfo<std::pair<const Value *, int64_t>>::getHashValue(
-        std::make_pair(OVal.Val, OVal.Offset));
-  }
-
-  static bool isEqual(const OffsetValue &LHS, const OffsetValue &RHS) {
-    return LHS == RHS;
-  }
-};
-
-// Specialize DenseMapInfo for OffsetInstantiatedValue.
-template <> struct DenseMapInfo<OffsetInstantiatedValue> {
-  static OffsetInstantiatedValue getEmptyKey() {
-    return OffsetInstantiatedValue{
-        DenseMapInfo<InstantiatedValue>::getEmptyKey(),
-        DenseMapInfo<int64_t>::getEmptyKey()};
-  }
-
-  static OffsetInstantiatedValue getTombstoneKey() {
-    return OffsetInstantiatedValue{
-        DenseMapInfo<InstantiatedValue>::getTombstoneKey(),
-        DenseMapInfo<int64_t>::getEmptyKey()};
-  }
-
-  static unsigned getHashValue(const OffsetInstantiatedValue &OVal) {
-    return DenseMapInfo<std::pair<InstantiatedValue, int64_t>>::getHashValue(
-        std::make_pair(OVal.IVal, OVal.Offset));
-  }
-
-  static bool isEqual(const OffsetInstantiatedValue &LHS,
-                      const OffsetInstantiatedValue &RHS) {
-    return LHS == RHS;
-  }
-};
-
-} // end namespace llvm
-
-class CFLAndersAAResult::FunctionInfo {
-  /// Map a value to other values that may alias it
-  /// Since the alias relation is symmetric, to save some space we assume values
-  /// are properly ordered: if a and b alias each other, and a < b, then b is in
-  /// AliasMap[a] but not vice versa.
-  DenseMap<const Value *, std::vector<OffsetValue>> AliasMap;
-
-  /// Map a value to its corresponding AliasAttrs
-  DenseMap<const Value *, AliasAttrs> AttrMap;
-
-  /// Summary of externally visible effects.
-  AliasSummary Summary;
-
-  Optional<AliasAttrs> getAttrs(const Value *) const;
-
-public:
-  FunctionInfo(const Function &, const SmallVectorImpl<Value *> &,
-               const ReachabilitySet &, const AliasAttrMap &);
-
-  bool mayAlias(const Value *, LocationSize, const Value *, LocationSize) const;
-  const AliasSummary &getAliasSummary() const { return Summary; }
-};
-
-static bool hasReadOnlyState(StateSet Set) {
-  return (Set & StateSet(ReadOnlyStateMask)).any();
-}
-
-static bool hasWriteOnlyState(StateSet Set) {
-  return (Set & StateSet(WriteOnlyStateMask)).any();
-}
-
-static std::optional<InterfaceValue>
-getInterfaceValue(InstantiatedValue IValue,
-                  const SmallVectorImpl<Value *> &RetVals) {
-  auto Val = IValue.Val;
-
-  std::optional<unsigned> Index;
-  if (auto Arg = dyn_cast<Argument>(Val))
-    Index = Arg->getArgNo() + 1;
-  else if (is_contained(RetVals, Val))
-    Index = 0;
-
-  if (Index)
-    return InterfaceValue{*Index, IValue.DerefLevel};
-  return std::nullopt;
-}
-
-static void populateAttrMap(DenseMap<const Value *, AliasAttrs> &AttrMap,
-                            const AliasAttrMap &AMap) {
-  for (const auto &Mapping : AMap.mappings()) {
-    auto IVal = Mapping.first;
-
-    // Insert IVal into the map
-    auto &Attr = AttrMap[IVal.Val];
-    // AttrMap only cares about top-level values
-    if (IVal.DerefLevel == 0)
-      Attr |= Mapping.second;
-  }
-}
-
-static void
-populateAliasMap(DenseMap<const Value *, std::vector<OffsetValue>> &AliasMap,
-                 const ReachabilitySet &ReachSet) {
-  for (const auto &OuterMapping : ReachSet.value_mappings()) {
-    // AliasMap only cares about top-level values
-    if (OuterMapping.first.DerefLevel > 0)
-      continue;
-
-    auto Val = OuterMapping.first.Val;
-    auto &AliasList = AliasMap[Val];
-    for (const auto &InnerMapping : OuterMapping.second) {
-      // Again, AliasMap only cares about top-level values
-      if (InnerMapping.first.DerefLevel == 0)
-        AliasList.push_back(OffsetValue{InnerMapping.first.Val, UnknownOffset});
-    }
-
-    // Sort AliasList for faster lookup
-    llvm::sort(AliasList);
-  }
-}
-
-static void populateExternalRelations(
-    SmallVectorImpl<ExternalRelation> &ExtRelations, const Function &Fn,
-    const SmallVectorImpl<Value *> &RetVals, const ReachabilitySet &ReachSet) {
-  // If a function only returns one of its argument X, then X will be both an
-  // argument and a return value at the same time. This is an edge case that
-  // needs special handling here.
-  for (const auto &Arg : Fn.args()) {
-    if (is_contained(RetVals, &Arg)) {
-      auto ArgVal = InterfaceValue{Arg.getArgNo() + 1, 0};
-      auto RetVal = InterfaceValue{0, 0};
-      ExtRelations.push_back(ExternalRelation{ArgVal, RetVal, 0});
-    }
-  }
-
-  // Below is the core summary construction logic.
-  // A naive solution of adding only the value aliases that are parameters or
-  // return values in ReachSet to the summary won't work: It is possible that a
-  // parameter P is written into an intermediate value I, and the function
-  // subsequently returns *I. In that case, *I is does not value alias anything
-  // in ReachSet, and the naive solution will miss a summary edge from (P, 1) to
-  // (I, 1).
-  // To account for the aforementioned case, we need to check each non-parameter
-  // and non-return value for the possibility of acting as an intermediate.
-  // 'ValueMap' here records, for each value, which InterfaceValues read from or
-  // write into it. If both the read list and the write list of a given value
-  // are non-empty, we know that a particular value is an intermidate and we
-  // need to add summary edges from the writes to the reads.
-  DenseMap<Value *, ValueSummary> ValueMap;
-  for (const auto &OuterMapping : ReachSet.value_mappings()) {
-    if (auto Dst = getInterfaceValue(OuterMapping.first, RetVals)) {
-      for (const auto &InnerMapping : OuterMapping.second) {
-        // If Src is a param/return value, we get a same-level assignment.
-        if (auto Src = getInterfaceValue(InnerMapping.first, RetVals)) {
-          // This may happen if both Dst and Src are return values
-          if (*Dst == *Src)
-            continue;
-
-          if (hasReadOnlyState(InnerMapping.second))
-            ExtRelations.push_back(ExternalRelation{*Dst, *Src, UnknownOffset});
-          // No need to check for WriteOnly state, since ReachSet is symmetric
-        } else {
-          // If Src is not a param/return, add it to ValueMap
-          auto SrcIVal = InnerMapping.first;
-          if (hasReadOnlyState(InnerMapping.second))
-            ValueMap[SrcIVal.Val].FromRecords.push_back(
-                ValueSummary::Record{*Dst, SrcIVal.DerefLevel});
-          if (hasWriteOnlyState(InnerMapping.second))
-            ValueMap[SrcIVal.Val].ToRecords.push_back(
-                ValueSummary::Record{*Dst, SrcIVal.DerefLevel});
-        }
-      }
-    }
-  }
-
-  for (const auto &Mapping : ValueMap) {
-    for (const auto &FromRecord : Mapping.second.FromRecords) {
-      for (const auto &ToRecord : Mapping.second.ToRecords) {
-        auto ToLevel = ToRecord.DerefLevel;
-        auto FromLevel = FromRecord.DerefLevel;
-        // Same-level assignments should have already been processed by now
-        if (ToLevel == FromLevel)
-          continue;
-
-        auto SrcIndex = FromRecord.IValue.Index;
-        auto SrcLevel = FromRecord.IValue.DerefLevel;
-        auto DstIndex = ToRecord.IValue.Index;
-        auto DstLevel = ToRecord.IValue.DerefLevel;
-        if (ToLevel > FromLevel)
-          SrcLevel += ToLevel - FromLevel;
-        else
-          DstLevel += FromLevel - ToLevel;
-
-        ExtRelations.push_back(ExternalRelation{
-            InterfaceValue{SrcIndex, SrcLevel},
-            InterfaceValue{DstIndex, DstLevel}, UnknownOffset});
-      }
-    }
-  }
-
-  // Remove duplicates in ExtRelations
-  llvm::sort(ExtRelations);
-  ExtRelations.erase(std::unique(ExtRelations.begin(), ExtRelations.end()),
-                     ExtRelations.end());
-}
-
-static void populateExternalAttributes(
-    SmallVectorImpl<ExternalAttribute> &ExtAttributes, const Function &Fn,
-    const SmallVectorImpl<Value *> &RetVals, const AliasAttrMap &AMap) {
-  for (const auto &Mapping : AMap.mappings()) {
-    if (auto IVal = getInterfaceValue(Mapping.first, RetVals)) {
-      auto Attr = getExternallyVisibleAttrs(Mapping.second);
-      if (Attr.any())
-        ExtAttributes.push_back(ExternalAttribute{*IVal, Attr});
-    }
-  }
-}
-
-CFLAndersAAResult::FunctionInfo::FunctionInfo(
-    const Function &Fn, const SmallVectorImpl<Value *> &RetVals,
-    const ReachabilitySet &ReachSet, const AliasAttrMap &AMap) {
-  populateAttrMap(AttrMap, AMap);
-  populateExternalAttributes(Summary.RetParamAttributes, Fn, RetVals, AMap);
-  populateAliasMap(AliasMap, ReachSet);
-  populateExternalRelations(Summary.RetParamRelations, Fn, RetVals, ReachSet);
-}
-
-Optional<AliasAttrs>
-CFLAndersAAResult::FunctionInfo::getAttrs(const Value *V) const {
-  assert(V != nullptr);
-
-  auto Itr = AttrMap.find(V);
-  if (Itr != AttrMap.end())
-    return Itr->second;
-  return std::nullopt;
-}
-
-bool CFLAndersAAResult::FunctionInfo::mayAlias(
-    const Value *LHS, LocationSize MaybeLHSSize, const Value *RHS,
-    LocationSize MaybeRHSSize) const {
-  assert(LHS && RHS);
-
-  // Check if we've seen LHS and RHS before. Sometimes LHS or RHS can be created
-  // after the analysis gets executed, and we want to be conservative in those
-  // cases.
-  auto MaybeAttrsA = getAttrs(LHS);
-  auto MaybeAttrsB = getAttrs(RHS);
-  if (!MaybeAttrsA || !MaybeAttrsB)
-    return true;
-
-  // Check AliasAttrs before AliasMap lookup since it's cheaper
-  auto AttrsA = *MaybeAttrsA;
-  auto AttrsB = *MaybeAttrsB;
-  if (hasUnknownOrCallerAttr(AttrsA))
-    return AttrsB.any();
-  if (hasUnknownOrCallerAttr(AttrsB))
-    return AttrsA.any();
-  if (isGlobalOrArgAttr(AttrsA))
-    return isGlobalOrArgAttr(AttrsB);
-  if (isGlobalOrArgAttr(AttrsB))
-    return isGlobalOrArgAttr(AttrsA);
-
-  // At this point both LHS and RHS should point to locally allocated objects
-
-  auto Itr = AliasMap.find(LHS);
-  if (Itr != AliasMap.end()) {
-
-    // Find out all (X, Offset) where X == RHS
-    auto Comparator = [](OffsetValue LHS, OffsetValue RHS) {
-      return std::less<const Value *>()(LHS.Val, RHS.Val);
-    };
-#ifdef EXPENSIVE_CHECKS
-    assert(llvm::is_sorted(Itr->second, Comparator));
-#endif
-    auto RangePair = std::equal_range(Itr->second.begin(), Itr->second.end(),
-                                      OffsetValue{RHS, 0}, Comparator);
-
-    if (RangePair.first != RangePair.second) {
-      // Be conservative about unknown sizes
-      if (!MaybeLHSSize.hasValue() || !MaybeRHSSize.hasValue())
-        return true;
-
-      const uint64_t LHSSize = MaybeLHSSize.getValue();
-      const uint64_t RHSSize = MaybeRHSSize.getValue();
-
-      for (const auto &OVal : make_range(RangePair)) {
-        // Be conservative about UnknownOffset
-        if (OVal.Offset == UnknownOffset)
-          return true;
-
-        // We know that LHS aliases (RHS + OVal.Offset) if the control flow
-        // reaches here. The may-alias query essentially becomes integer
-        // range-overlap queries over two ranges [OVal.Offset, OVal.Offset +
-        // LHSSize) and [0, RHSSize).
-
-        // Try to be conservative on super large offsets
-        if (LLVM_UNLIKELY(LHSSize > INT64_MAX || RHSSize > INT64_MAX))
-          return true;
-
-        auto LHSStart = OVal.Offset;
-        // FIXME: Do we need to guard against integer overflow?
-        auto LHSEnd = OVal.Offset + static_cast<int64_t>(LHSSize);
-        auto RHSStart = 0;
-        auto RHSEnd = static_cast<int64_t>(RHSSize);
-        if (LHSEnd > RHSStart && LHSStart < RHSEnd)
-          return true;
-      }
-    }
-  }
-
-  return false;
-}
-
-static void propagate(InstantiatedValue From, InstantiatedValue To,
-                      MatchState State, ReachabilitySet &ReachSet,
-                      std::vector<WorkListItem> &WorkList) {
-  if (From == To)
-    return;
-  if (ReachSet.insert(From, To, State))
-    WorkList.push_back(WorkListItem{From, To, State});
-}
-
-static void initializeWorkList(std::vector<WorkListItem> &WorkList,
-                               ReachabilitySet &ReachSet,
-                               const CFLGraph &Graph) {
-  for (const auto &Mapping : Graph.value_mappings()) {
-    auto Val = Mapping.first;
-    auto &ValueInfo = Mapping.second;
-    assert(ValueInfo.getNumLevels() > 0);
-
-    // Insert all immediate assignment neighbors to the worklist
-    for (unsigned I = 0, E = ValueInfo.getNumLevels(); I < E; ++I) {
-      auto Src = InstantiatedValue{Val, I};
-      // If there's an assignment edge from X to Y, it means Y is reachable from
-      // X at S3 and X is reachable from Y at S1
-      for (const auto &Edge : ValueInfo.getNodeInfoAtLevel(I).Edges) {
-        propagate(Edge.Other, Src, MatchState::FlowFromReadOnly, ReachSet,
-                  WorkList);
-        propagate(Src, Edge.Other, MatchState::FlowToWriteOnly, ReachSet,
-                  WorkList);
-      }
-    }
-  }
-}
-
-static std::optional<InstantiatedValue> getNodeBelow(const CFLGraph &Graph,
-                                                InstantiatedValue V) {
-  auto NodeBelow = InstantiatedValue{V.Val, V.DerefLevel + 1};
-  if (Graph.getNode(NodeBelow))
-    return NodeBelow;
-  return std::nullopt;
-}
-
-static void processWorkListItem(const WorkListItem &Item, const CFLGraph &Graph,
-                                ReachabilitySet &ReachSet, AliasMemSet &MemSet,
-                                std::vector<WorkListItem> &WorkList) {
-  auto FromNode = Item.From;
-  auto ToNode = Item.To;
-
-  auto NodeInfo = Graph.getNode(ToNode);
-  assert(NodeInfo != nullptr);
-
-  // TODO: propagate field offsets
-
-  // FIXME: Here is a neat trick we can do: since both ReachSet and MemSet holds
-  // relations that are symmetric, we could actually cut the storage by half by
-  // sorting FromNode and ToNode before insertion happens.
-
-  // The newly added value alias pair may potentially generate more memory
-  // alias pairs. Check for them here.
-  auto FromNodeBelow = getNodeBelow(Graph, FromNode);
-  auto ToNodeBelow = getNodeBelow(Graph, ToNode);
-  if (FromNodeBelow && ToNodeBelow &&
-      MemSet.insert(*FromNodeBelow, *ToNodeBelow)) {
-    propagate(*FromNodeBelow, *ToNodeBelow,
-              MatchState::FlowFromMemAliasNoReadWrite, ReachSet, WorkList);
-    for (const auto &Mapping : ReachSet.reachableValueAliases(*FromNodeBelow)) {
-      auto Src = Mapping.first;
-      auto MemAliasPropagate = [&](MatchState FromState, MatchState ToState) {
-        if (Mapping.second.test(static_cast<size_t>(FromState)))
-          propagate(Src, *ToNodeBelow, ToState, ReachSet, WorkList);
-      };
-
-      MemAliasPropagate(MatchState::FlowFromReadOnly,
-                        MatchState::FlowFromMemAliasReadOnly);
-      MemAliasPropagate(MatchState::FlowToWriteOnly,
-                        MatchState::FlowToMemAliasWriteOnly);
-      MemAliasPropagate(MatchState::FlowToReadWrite,
-                        MatchState::FlowToMemAliasReadWrite);
-    }
-  }
-
-  // This is the core of the state machine walking algorithm. We expand ReachSet
-  // based on which state we are at (which in turn dictates what edges we
-  // should examine)
-  // From a high-level point of view, the state machine here guarantees two
-  // properties:
-  // - If *X and *Y are memory aliases, then X and Y are value aliases
-  // - If Y is an alias of X, then reverse assignment edges (if there is any)
-  // should precede any assignment edges on the path from X to Y.
-  auto NextAssignState = [&](MatchState State) {
-    for (const auto &AssignEdge : NodeInfo->Edges)
-      propagate(FromNode, AssignEdge.Other, State, ReachSet, WorkList);
-  };
-  auto NextRevAssignState = [&](MatchState State) {
-    for (const auto &RevAssignEdge : NodeInfo->ReverseEdges)
-      propagate(FromNode, RevAssignEdge.Other, State, ReachSet, WorkList);
-  };
-  auto NextMemState = [&](MatchState State) {
-    if (auto AliasSet = MemSet.getMemoryAliases(ToNode)) {
-      for (const auto &MemAlias : *AliasSet)
-        propagate(FromNode, MemAlias, State, ReachSet, WorkList);
-    }
-  };
-
-  switch (Item.State) {
-  case MatchState::FlowFromReadOnly:
-    NextRevAssignState(MatchState::FlowFromReadOnly);
-    NextAssignState(MatchState::FlowToReadWrite);
-    NextMemState(MatchState::FlowFromMemAliasReadOnly);
-    break;
-
-  case MatchState::FlowFromMemAliasNoReadWrite:
-    NextRevAssignState(MatchState::FlowFromReadOnly);
-    NextAssignState(MatchState::FlowToWriteOnly);
-    break;
-
-  case MatchState::FlowFromMemAliasReadOnly:
-    NextRevAssignState(MatchState::FlowFromReadOnly);
-    NextAssignState(MatchState::FlowToReadWrite);
-    break;
-
-  case MatchState::FlowToWriteOnly:
-    NextAssignState(MatchState::FlowToWriteOnly);
-    NextMemState(MatchState::FlowToMemAliasWriteOnly);
-    break;
-
-  case MatchState::FlowToReadWrite:
-    NextAssignState(MatchState::FlowToReadWrite);
-    NextMemState(MatchState::FlowToMemAliasReadWrite);
-    break;
-
-  case MatchState::FlowToMemAliasWriteOnly:
-    NextAssignState(MatchState::FlowToWriteOnly);
-    break;
-
-  case MatchState::FlowToMemAliasReadWrite:
-    NextAssignState(MatchState::FlowToReadWrite);
-    break;
-  }
-}
-
-static AliasAttrMap buildAttrMap(const CFLGraph &Graph,
-                                 const ReachabilitySet &ReachSet) {
-  AliasAttrMap AttrMap;
-  std::vector<InstantiatedValue> WorkList, NextList;
-
-  // Initialize each node with its original AliasAttrs in CFLGraph
-  for (const auto &Mapping : Graph.value_mappings()) {
-    auto Val = Mapping.first;
-    auto &ValueInfo = Mapping.second;
-    for (unsigned I = 0, E = ValueInfo.getNumLevels(); I < E; ++I) {
-      auto Node = InstantiatedValue{Val, I};
-      AttrMap.add(Node, ValueInfo.getNodeInfoAtLevel(I).Attr);
-      WorkList.push_back(Node);
-    }
-  }
-
-  while (!WorkList.empty()) {
-    for (const auto &Dst : WorkList) {
-      auto DstAttr = AttrMap.getAttrs(Dst);
-      if (DstAttr.none())
-        continue;
-
-      // Propagate attr on the same level
-      for (const auto &Mapping : ReachSet.reachableValueAliases(Dst)) {
-        auto Src = Mapping.first;
-        if (AttrMap.add(Src, DstAttr))
-          NextList.push_back(Src);
-      }
-
-      // Propagate attr to the levels below
-      auto DstBelow = getNodeBelow(Graph, Dst);
-      while (DstBelow) {
-        if (AttrMap.add(*DstBelow, DstAttr)) {
-          NextList.push_back(*DstBelow);
-          break;
-        }
-        DstBelow = getNodeBelow(Graph, *DstBelow);
-      }
-    }
-    WorkList.swap(NextList);
-    NextList.clear();
-  }
-
-  return AttrMap;
-}
-
-CFLAndersAAResult::FunctionInfo
-CFLAndersAAResult::buildInfoFrom(const Function &Fn) {
-  CFLGraphBuilder<CFLAndersAAResult> GraphBuilder(
-      *this, GetTLI(const_cast<Function &>(Fn)),
-      // Cast away the constness here due to GraphBuilder's API requirement
-      const_cast<Function &>(Fn));
-  auto &Graph = GraphBuilder.getCFLGraph();
-
-  ReachabilitySet ReachSet;
-  AliasMemSet MemSet;
-
-  std::vector<WorkListItem> WorkList, NextList;
-  initializeWorkList(WorkList, ReachSet, Graph);
-  // TODO: make sure we don't stop before the fix point is reached
-  while (!WorkList.empty()) {
-    for (const auto &Item : WorkList)
-      processWorkListItem(Item, Graph, ReachSet, MemSet, NextList);
-
-    NextList.swap(WorkList);
-    NextList.clear();
-  }
-
-  // Now that we have all the reachability info, propagate AliasAttrs according
-  // to it
-  auto IValueAttrMap = buildAttrMap(Graph, ReachSet);
-
-  return FunctionInfo(Fn, GraphBuilder.getReturnValues(), ReachSet,
-                      std::move(IValueAttrMap));
-}
-
-void CFLAndersAAResult::scan(const Function &Fn) {
-  auto InsertPair = Cache.insert(std::make_pair(&Fn, Optional<FunctionInfo>()));
-  (void)InsertPair;
-  assert(InsertPair.second &&
-         "Trying to scan a function that has already been cached");
-
-  // Note that we can't do Cache[Fn] = buildSetsFrom(Fn) here: the function call
-  // may get evaluated after operator[], potentially triggering a DenseMap
-  // resize and invalidating the reference returned by operator[]
-  auto FunInfo = buildInfoFrom(Fn);
-  Cache[&Fn] = std::move(FunInfo);
-  Handles.emplace_front(const_cast<Function *>(&Fn), this);
-}
-
-void CFLAndersAAResult::evict(const Function *Fn) { Cache.erase(Fn); }
-
-const Optional<CFLAndersAAResult::FunctionInfo> &
-CFLAndersAAResult::ensureCached(const Function &Fn) {
-  auto Iter = Cache.find(&Fn);
-  if (Iter == Cache.end()) {
-    scan(Fn);
-    Iter = Cache.find(&Fn);
-    assert(Iter != Cache.end());
-    assert(Iter->second);
-  }
-  return Iter->second;
-}
-
-const AliasSummary *CFLAndersAAResult::getAliasSummary(const Function &Fn) {
-  auto &FunInfo = ensureCached(Fn);
-  if (FunInfo)
-    return &FunInfo->getAliasSummary();
-  else
-    return nullptr;
-}
-
-AliasResult CFLAndersAAResult::query(const MemoryLocation &LocA,
-                                     const MemoryLocation &LocB) {
-  auto *ValA = LocA.Ptr;
-  auto *ValB = LocB.Ptr;
-
-  if (!ValA->getType()->isPointerTy() || !ValB->getType()->isPointerTy())
-    return AliasResult::NoAlias;
-
-  auto *Fn = parentFunctionOfValue(ValA);
-  if (!Fn) {
-    Fn = parentFunctionOfValue(ValB);
-    if (!Fn) {
-      // The only times this is known to happen are when globals + InlineAsm are
-      // involved
-      LLVM_DEBUG(
-          dbgs()
-          << "CFLAndersAA: could not extract parent function information.\n");
-      return AliasResult::MayAlias;
-    }
-  } else {
-    assert(!parentFunctionOfValue(ValB) || parentFunctionOfValue(ValB) == Fn);
-  }
-
-  assert(Fn != nullptr);
-  auto &FunInfo = ensureCached(*Fn);
-
-  // AliasMap lookup
-  if (FunInfo->mayAlias(ValA, LocA.Size, ValB, LocB.Size))
-    return AliasResult::MayAlias;
-  return AliasResult::NoAlias;
-}
-
-AliasResult CFLAndersAAResult::alias(const MemoryLocation &LocA,
-                                     const MemoryLocation &LocB,
-                                     AAQueryInfo &AAQI) {
-  if (LocA.Ptr == LocB.Ptr)
-    return AliasResult::MustAlias;
-
-  // Comparisons between global variables and other constants should be
-  // handled by BasicAA.
-  // CFLAndersAA may report NoAlias when comparing a GlobalValue and
-  // ConstantExpr, but every query needs to have at least one Value tied to a
-  // Function, and neither GlobalValues nor ConstantExprs are.
-  if (isa<Constant>(LocA.Ptr) && isa<Constant>(LocB.Ptr))
-    return AAResultBase::alias(LocA, LocB, AAQI);
-
-  AliasResult QueryResult = query(LocA, LocB);
-  if (QueryResult == AliasResult::MayAlias)
-    return AAResultBase::alias(LocA, LocB, AAQI);
-
-  return QueryResult;
-}
-
-AnalysisKey CFLAndersAA::Key;
-
-CFLAndersAAResult CFLAndersAA::run(Function &F, FunctionAnalysisManager &AM) {
-  auto GetTLI = [&AM](Function &F) -> TargetLibraryInfo & {
-    return AM.getResult<TargetLibraryAnalysis>(F);
-  };
-  return CFLAndersAAResult(GetTLI);
-}
-
-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() {
-  auto GetTLI = [this](Function &F) -> TargetLibraryInfo & {
-    return this->getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
-  };
-  Result.reset(new CFLAndersAAResult(GetTLI));
-}
-
-void CFLAndersAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
-  AU.setPreservesAll();
-  AU.addRequired<TargetLibraryInfoWrapperPass>();
-}

llvm/lib/Analysis/CFLGraph.h

-//===- CFLGraph.h - Abstract stratified sets implementation. -----*- C++-*-===//
-//
-// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
-// See https://llvm.org/LICENSE.txt for license information.
-// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
-//
-//===----------------------------------------------------------------------===//
-//
-/// \file
-/// This file defines CFLGraph, an auxiliary data structure used by CFL-based
-/// alias analysis.
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_LIB_ANALYSIS_CFLGRAPH_H
-#define LLVM_LIB_ANALYSIS_CFLGRAPH_H
-
-#include "AliasAnalysisSummary.h"
-#include "llvm/ADT/APInt.h"
-#include "llvm/ADT/DenseMap.h"
-#include "llvm/ADT/SmallVector.h"
-#include "llvm/ADT/iterator_range.h"
-#include "llvm/Analysis/MemoryBuiltins.h"
-#include "llvm/Analysis/TargetLibraryInfo.h"
-#include "llvm/IR/Argument.h"
-#include "llvm/IR/BasicBlock.h"
-#include "llvm/IR/Constants.h"
-#include "llvm/IR/DataLayout.h"
-#include "llvm/IR/Function.h"
-#include "llvm/IR/GlobalValue.h"
-#include "llvm/IR/InstVisitor.h"
-#include "llvm/IR/InstrTypes.h"
-#include "llvm/IR/Instruction.h"
-#include "llvm/IR/Instructions.h"
-#include "llvm/IR/Operator.h"
-#include "llvm/IR/Type.h"
-#include "llvm/IR/Value.h"
-#include "llvm/Support/Casting.h"
-#include "llvm/Support/ErrorHandling.h"
-#include <cassert>
-#include <cstdint>
-#include <vector>
-
-namespace llvm {
-namespace cflaa {
-
-/// The Program Expression Graph (PEG) of CFL analysis
-/// CFLGraph is auxiliary data structure used by CFL-based alias analysis to
-/// describe flow-insensitive pointer-related behaviors. Given an LLVM function,
-/// the main purpose of this graph is to abstract away unrelated facts and
-/// translate the rest into a form that can be easily digested by CFL analyses.
-/// Each Node in the graph is an InstantiatedValue, and each edge represent a
-/// pointer assignment between InstantiatedValue. Pointer
-/// references/dereferences are not explicitly stored in the graph: we
-/// implicitly assume that for each node (X, I) it has a dereference edge to (X,
-/// I+1) and a reference edge to (X, I-1).
-class CFLGraph {
-public:
-  using Node = InstantiatedValue;
-
-  struct Edge {
-    Node Other;
-    int64_t Offset;
-  };
-
-  using EdgeList = std::vector<Edge>;
-
-  struct NodeInfo {
-    EdgeList Edges, ReverseEdges;
-    AliasAttrs Attr;
-  };
-
-  class ValueInfo {
-    std::vector<NodeInfo> Levels;
-
-  public:
-    bool addNodeToLevel(unsigned Level) {
-      auto NumLevels = Levels.size();
-      if (NumLevels > Level)
-        return false;
-      Levels.resize(Level + 1);
-      return true;
-    }
-
-    NodeInfo &getNodeInfoAtLevel(unsigned Level) {
-      assert(Level < Levels.size());
-      return Levels[Level];
-    }
-    const NodeInfo &getNodeInfoAtLevel(unsigned Level) const {
-      assert(Level < Levels.size());
-      return Levels[Level];
-    }
-
-    unsigned getNumLevels() const { return Levels.size(); }
-  };
-
-private:
-  using ValueMap = DenseMap<Value *, ValueInfo>;
-
-  ValueMap ValueImpls;
-
-  NodeInfo *getNode(Node N) {
-    auto Itr = ValueImpls.find(N.Val);
-    if (Itr == ValueImpls.end() || Itr->second.getNumLevels() <= N.DerefLevel)
-      return nullptr;
-    return &Itr->second.getNodeInfoAtLevel(N.DerefLevel);
-  }
-
-public:
-  using const_value_iterator = ValueMap::const_iterator;
-
-  bool addNode(Node N, AliasAttrs Attr = AliasAttrs()) {
-    assert(N.Val != nullptr);
-    auto &ValInfo = ValueImpls[N.Val];
-    auto Changed = ValInfo.addNodeToLevel(N.DerefLevel);
-    ValInfo.getNodeInfoAtLevel(N.DerefLevel).Attr |= Attr;
-    return Changed;
-  }
-
-  void addAttr(Node N, AliasAttrs Attr) {
-    auto *Info = getNode(N);
-    assert(Info != nullptr);
-    Info->Attr |= Attr;
-  }
-
-  void addEdge(Node From, Node To, int64_t Offset = 0) {
-    auto *FromInfo = getNode(From);
-    assert(FromInfo != nullptr);
-    auto *ToInfo = getNode(To);
-    assert(ToInfo != nullptr);
-
-    FromInfo->Edges.push_back(Edge{To, Offset});
-    ToInfo->ReverseEdges.push_back(Edge{From, Offset});
-  }
-
-  const NodeInfo *getNode(Node N) const {
-    auto Itr = ValueImpls.find(N.Val);
-    if (Itr == ValueImpls.end() || Itr->second.getNumLevels() <= N.DerefLevel)
-      return nullptr;
-    return &Itr->second.getNodeInfoAtLevel(N.DerefLevel);
-  }
-
-  AliasAttrs attrFor(Node N) const {
-    auto *Info = getNode(N);
-    assert(Info != nullptr);
-    return Info->Attr;
-  }
-
-  iterator_range<const_value_iterator> value_mappings() const {
-    return make_range<const_value_iterator>(ValueImpls.begin(),
-                                            ValueImpls.end());
-  }
-};
-
-/// A builder class used to create CFLGraph instance from a given function
-/// The CFL-AA that uses this builder must provide its own type as a template
-/// argument. This is necessary for interprocedural processing: CFLGraphBuilder
-/// needs a way of obtaining the summary of other functions when callinsts are
-/// encountered.
-/// As a result, we expect the said CFL-AA to expose a getAliasSummary() public
-/// member function that takes a Function& and returns the corresponding summary
-/// as a const AliasSummary*.
-template <typename CFLAA> class CFLGraphBuilder {
-  // Input of the builder
-  CFLAA &Analysis;
-  const TargetLibraryInfo &TLI;
-
-  // Output of the builder
-  CFLGraph Graph;
-  SmallVector<Value *, 4> ReturnedValues;
-
-  // Helper class
-  /// Gets the edges our graph should have, based on an Instruction*
-  class GetEdgesVisitor : public InstVisitor<GetEdgesVisitor, void> {
-    CFLAA &AA;
-    const DataLayout &DL;
-    const TargetLibraryInfo &TLI;
-
-    CFLGraph &Graph;
-    SmallVectorImpl<Value *> &ReturnValues;
-
-    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;
-    }
-
-    // Returns possible functions called by CS into the given SmallVectorImpl.
-    // Returns true if targets found, false otherwise.
-    static bool getPossibleTargets(CallBase &Call,
-                                   SmallVectorImpl<Function *> &Output) {
-      if (auto *Fn = Call.getCalledFunction()) {
-        Output.push_back(Fn);
-        return true;
-      }
-
-      // TODO: If the call is indirect, we might be able to enumerate all
-      // potential targets of the call and return them, rather than just
-      // failing.
-      return false;
-    }
-
-    void addNode(Value *Val, AliasAttrs Attr = AliasAttrs()) {
-      assert(Val != nullptr && Val->getType()->isPointerTy());
-      if (auto GVal = dyn_cast<GlobalValue>(Val)) {
-        if (Graph.addNode(InstantiatedValue{GVal, 0},
-                          getGlobalOrArgAttrFromValue(*GVal)))
-          Graph.addNode(InstantiatedValue{GVal, 1}, getAttrUnknown());
-      } else if (auto CExpr = dyn_cast<ConstantExpr>(Val)) {
-        if (hasUsefulEdges(CExpr)) {
-          if (Graph.addNode(InstantiatedValue{CExpr, 0}))
-            visitConstantExpr(CExpr);
-        }
-      } else
-        Graph.addNode(InstantiatedValue{Val, 0}, Attr);
-    }
-
-    void addAssignEdge(Value *From, Value *To, int64_t Offset = 0) {
-      assert(From != nullptr && To != nullptr);
-      if (!From->getType()->isPointerTy() || !To->getType()->isPointerTy())
-        return;
-      addNode(From);
-      if (To != From) {
-        addNode(To);
-        Graph.addEdge(InstantiatedValue{From, 0}, InstantiatedValue{To, 0},
-                      Offset);
-      }
-    }
-
-    void addDerefEdge(Value *From, Value *To, bool IsRead) {
-      assert(From != nullptr && To != nullptr);
-      // FIXME: This is subtly broken, due to how we model some instructions
-      // (e.g. extractvalue, extractelement) as loads. Since those take
-      // non-pointer operands, we'll entirely skip adding edges for those.
-      //
-      // addAssignEdge seems to have a similar issue with insertvalue, etc.
-      if (!From->getType()->isPointerTy() || !To->getType()->isPointerTy())
-        return;
-      addNode(From);
-      addNode(To);
-      if (IsRead) {
-        Graph.addNode(InstantiatedValue{From, 1});
-        Graph.addEdge(InstantiatedValue{From, 1}, InstantiatedValue{To, 0});
-      } else {
-        Graph.addNode(InstantiatedValue{To, 1});
-        Graph.addEdge(InstantiatedValue{From, 0}, InstantiatedValue{To, 1});
-      }
-    }
-
-    void addLoadEdge(Value *From, Value *To) { addDerefEdge(From, To, true); }
-    void addStoreEdge(Value *From, Value *To) { addDerefEdge(From, To, false); }
-
-  public:
-    GetEdgesVisitor(CFLGraphBuilder &Builder, const DataLayout &DL)
-        : AA(Builder.Analysis), DL(DL), TLI(Builder.TLI), Graph(Builder.Graph),
-          ReturnValues(Builder.ReturnedValues) {}
-
-    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);
-      addNode(Ptr, getAttrEscaped());
-    }
-
-    void visitIntToPtrInst(IntToPtrInst &Inst) {
-      auto *Ptr = &Inst;
-      addNode(Ptr, getAttrUnknown());
-    }
-
-    void visitCastInst(CastInst &Inst) {
-      auto *Src = Inst.getOperand(0);
-      addAssignEdge(Src, &Inst);
-    }
-
-    void visitFreezeInst(FreezeInst &Inst) {
-      // Accessing freeze(ptr) is equivalent to accessing ptr.
-      // The former raises UB iff latter raises UB.
-      auto *Src = Inst.getOperand(0);
-      addAssignEdge(Src, &Inst);
-    }
-
-    void visitBinaryOperator(BinaryOperator &Inst) {
-      auto *Op1 = Inst.getOperand(0);
-      auto *Op2 = Inst.getOperand(1);
-      addAssignEdge(Op1, &Inst);
-      addAssignEdge(Op2, &Inst);
-    }
-
-    void visitUnaryOperator(UnaryOperator &Inst) {
-      auto *Src = Inst.getOperand(0);
-      addAssignEdge(Src, &Inst);
-    }
-
-    void visitAtomicCmpXchgInst(AtomicCmpXchgInst &Inst) {
-      auto *Ptr = Inst.getPointerOperand();
-      auto *Val = Inst.getNewValOperand();
-      addStoreEdge(Val, Ptr);
-    }
-
-    void visitAtomicRMWInst(AtomicRMWInst &Inst) {
-      auto *Ptr = Inst.getPointerOperand();
-      auto *Val = Inst.getValOperand();
-      addStoreEdge(Val, Ptr);
-    }
-
-    void visitPHINode(PHINode &Inst) {
-      for (Value *Val : Inst.incoming_values())
-        addAssignEdge(Val, &Inst);
-    }
-
-    void visitGEP(GEPOperator &GEPOp) {
-      uint64_t Offset = UnknownOffset;
-      APInt APOffset(DL.getPointerSizeInBits(GEPOp.getPointerAddressSpace()),
-                     0);
-      if (GEPOp.accumulateConstantOffset(DL, APOffset))
-        Offset = APOffset.getSExtValue();
-
-      auto *Op = GEPOp.getPointerOperand();
-      addAssignEdge(Op, &GEPOp, Offset);
-    }
-
-    void visitGetElementPtrInst(GetElementPtrInst &Inst) {
-      auto *GEPOp = cast<GEPOperator>(&Inst);
-      visitGEP(*GEPOp);
-    }
-
-    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();
-      addAssignEdge(TrueVal, &Inst);
-      addAssignEdge(FalseVal, &Inst);
-    }
-
-    void visitAllocaInst(AllocaInst &Inst) { addNode(&Inst); }
-
-    void visitLoadInst(LoadInst &Inst) {
-      auto *Ptr = Inst.getPointerOperand();
-      auto *Val = &Inst;
-      addLoadEdge(Ptr, Val);
-    }
-
-    void visitStoreInst(StoreInst &Inst) {
-      auto *Ptr = Inst.getPointerOperand();
-      auto *Val = Inst.getValueOperand();
-      addStoreEdge(Val, Ptr);
-    }
-
-    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).
-      if (Inst.getType()->isPointerTy())
-        addNode(&Inst, getAttrUnknown());
-    }
-
-    static bool isFunctionExternal(Function *Fn) {
-      return !Fn->hasExactDefinition();
-    }
-
-    bool tryInterproceduralAnalysis(CallBase &Call,
-                                    const SmallVectorImpl<Function *> &Fns) {
-      assert(Fns.size() > 0);
-
-      if (Call.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() <= Call.arg_size());
-        if (!AA.getAliasSummary(*Fn))
-          return false;
-      }
-
-      for (auto *Fn : Fns) {
-        auto Summary = AA.getAliasSummary(*Fn);
-        assert(Summary != nullptr);
-
-        auto &RetParamRelations = Summary->RetParamRelations;
-        for (auto &Relation : RetParamRelations) {
-          auto IRelation = instantiateExternalRelation(Relation, Call);
-          if (IRelation) {
-            Graph.addNode(IRelation->From);
-            Graph.addNode(IRelation->To);
-            Graph.addEdge(IRelation->From, IRelation->To);
-          }
-        }
-
-        auto &RetParamAttributes = Summary->RetParamAttributes;
-        for (auto &Attribute : RetParamAttributes) {
-          auto IAttr = instantiateExternalAttribute(Attribute, Call);
-          if (IAttr)
-            Graph.addNode(IAttr->IValue, IAttr->Attr);
-        }
-      }
-
-      return true;
-    }
-
-    void visitCallBase(CallBase &Call) {
-      // Make sure all arguments and return value are added to the graph first
-      for (Value *V : Call.args())
-        if (V->getType()->isPointerTy())
-          addNode(V);
-      if (Call.getType()->isPointerTy())
-        addNode(&Call);
-
-      // 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 (isMallocOrCallocLikeFn(&Call, &TLI) ||
-          getFreedOperand(&Call, &TLI) != nullptr)
-        return;
-
-      // TODO: Add support for noalias args/all the other fun function
-      // attributes that we can tack on.
-      SmallVector<Function *, 4> Targets;
-      if (getPossibleTargets(Call, Targets))
-        if (tryInterproceduralAnalysis(Call, 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 (!Call.onlyReadsMemory())
-        for (Value *V : Call.args()) {
-          if (V->getType()->isPointerTy()) {
-            // The argument itself escapes.
-            Graph.addAttr(InstantiatedValue{V, 0}, getAttrEscaped());
-            // The fate of argument memory is unknown. Note that since
-            // AliasAttrs is transitive with respect to dereference, we only
-            // need to specify it for the first-level memory.
-            Graph.addNode(InstantiatedValue{V, 1}, getAttrUnknown());
-          }
-        }
-
-      if (Call.getType()->isPointerTy()) {
-        auto *Fn = Call.getCalledFunction();
-        if (Fn == nullptr || !Fn->returnDoesNotAlias())
-          // No need to call addNode() since we've added Inst at the
-          // beginning of this function and we know it is not a global.
-          Graph.addAttr(InstantiatedValue{&Call, 0}, getAttrUnknown());
-      }
-    }
-
-    /// 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;
-      addLoadEdge(Ptr, Val);
-    }
-
-    void visitInsertElementInst(InsertElementInst &Inst) {
-      auto *Vec = Inst.getOperand(0);
-      auto *Val = Inst.getOperand(1);
-      addAssignEdge(Vec, &Inst);
-      addStoreEdge(Val, &Inst);
-    }
-
-    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
-      if (Inst.getType()->isPointerTy())
-        addNode(&Inst, getAttrUnknown());
-    }
-
-    void visitInsertValueInst(InsertValueInst &Inst) {
-      auto *Agg = Inst.getOperand(0);
-      auto *Val = Inst.getOperand(1);
-      addAssignEdge(Agg, &Inst);
-      addStoreEdge(Val, &Inst);
-    }
-
-    void visitExtractValueInst(ExtractValueInst &Inst) {
-      auto *Ptr = Inst.getAggregateOperand();
-      addLoadEdge(Ptr, &Inst);
-    }
-
-    void visitShuffleVectorInst(ShuffleVectorInst &Inst) {
-      auto *From1 = Inst.getOperand(0);
-      auto *From2 = Inst.getOperand(1);
-      addAssignEdge(From1, &Inst);
-      addAssignEdge(From2, &Inst);
-    }
-
-    void visitConstantExpr(ConstantExpr *CE) {
-      switch (CE->getOpcode()) {
-      case Instruction::GetElementPtr: {
-        auto GEPOp = cast<GEPOperator>(CE);
-        visitGEP(*GEPOp);
-        break;
-      }
-
-      case Instruction::PtrToInt: {
-        addNode(CE->getOperand(0), getAttrEscaped());
-        break;
-      }
-
-      case Instruction::IntToPtr: {
-        addNode(CE, getAttrUnknown());
-        break;
-      }
-
-      case Instruction::BitCast:
-      case Instruction::AddrSpaceCast:
-      case Instruction::Trunc:
-      case Instruction::ZExt:
-      case Instruction::SExt:
-      case Instruction::FPExt:
-      case Instruction::FPTrunc:
-      case Instruction::UIToFP:
-      case Instruction::SIToFP:
-      case Instruction::FPToUI:
-      case Instruction::FPToSI: {
-        addAssignEdge(CE->getOperand(0), CE);
-        break;
-      }
-
-      case Instruction::Select: {
-        addAssignEdge(CE->getOperand(1), CE);
-        addAssignEdge(CE->getOperand(2), CE);
-        break;
-      }
-
-      case Instruction::InsertElement:
-      case Instruction::InsertValue: {
-        addAssignEdge(CE->getOperand(0), CE);
-        addStoreEdge(CE->getOperand(1), CE);
-        break;
-      }
-
-      case Instruction::ExtractElement:
-      case Instruction::ExtractValue: {
-        addLoadEdge(CE->getOperand(0), CE);
-        break;
-      }
-
-      case Instruction::Add:
-      case Instruction::FAdd:
-      case Instruction::Sub:
-      case Instruction::FSub:
-      case Instruction::Mul:
-      case Instruction::FMul:
-      case Instruction::UDiv:
-      case Instruction::SDiv:
-      case Instruction::FDiv:
-      case Instruction::URem:
-      case Instruction::SRem:
-      case Instruction::FRem:
-      case Instruction::And:
-      case Instruction::Or:
-      case Instruction::Xor:
-      case Instruction::Shl:
-      case Instruction::LShr:
-      case Instruction::AShr:
-      case Instruction::ICmp:
-      case Instruction::FCmp:
-      case Instruction::ShuffleVector: {
-        addAssignEdge(CE->getOperand(0), CE);
-        addAssignEdge(CE->getOperand(1), CE);
-        break;
-      }
-
-      case Instruction::FNeg: {
-        addAssignEdge(CE->getOperand(0), CE);
-        break;
-      }
-
-      default:
-        llvm_unreachable("Unknown instruction type encountered!");
-      }
-    }
-  };
-
-  // Helper functions
-
-  // Determines whether or not we an instruction is useless to us (e.g.
-  // FenceInst)
-  static bool hasUsefulEdges(Instruction *Inst) {
-    bool IsNonInvokeRetTerminator = Inst->isTerminator() &&
-                                    !isa<InvokeInst>(Inst) &&
-                                    !isa<ReturnInst>(Inst);
-    return !isa<CmpInst>(Inst) && !isa<FenceInst>(Inst) &&
-           !IsNonInvokeRetTerminator;
-  }
-
-  void addArgumentToGraph(Argument &Arg) {
-    if (Arg.getType()->isPointerTy()) {
-      Graph.addNode(InstantiatedValue{&Arg, 0},
-                    getGlobalOrArgAttrFromValue(Arg));
-      // Pointees of a formal parameter is known to the caller
-      Graph.addNode(InstantiatedValue{&Arg, 1}, getAttrCaller());
-    }
-  }
-
-  // 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(GetEdgesVisitor &Visitor, Instruction &Inst) {
-    if (!hasUsefulEdges(&Inst))
-      return;
-
-    Visitor.visit(Inst);
-  }
-
-  // Builds the graph needed for constructing the StratifiedSets for the given
-  // function
-  void buildGraphFrom(Function &Fn) {
-    GetEdgesVisitor Visitor(*this, Fn.getParent()->getDataLayout());
-
-    for (auto &Bb : Fn.getBasicBlockList())
-      for (auto &Inst : Bb)
-        addInstructionToGraph(Visitor, Inst);
-
-    for (auto &Arg : Fn.args())
-      addArgumentToGraph(Arg);
-  }
-
-public:
-  CFLGraphBuilder(CFLAA &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;
-  }
-};
-
-} // end namespace cflaa
-} // end namespace llvm
-
-#endif // LLVM_LIB_ANALYSIS_CFLGRAPH_H

llvm/lib/Analysis/CFLSteensAliasAnalysis.cpp

-//===- CFLSteensAliasAnalysis.cpp - Unification-based Alias Analysis ------===//
-//
-// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
-// See https://llvm.org/LICENSE.txt for license information.
-// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
-//
-//===----------------------------------------------------------------------===//
-//
-// 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 "AliasAnalysisSummary.h"
-#include "CFLGraph.h"
-#include "StratifiedSets.h"
-#include "llvm/ADT/DenseMap.h"
-#include "llvm/ADT/Optional.h"
-#include "llvm/ADT/SmallVector.h"
-#include "llvm/Analysis/TargetLibraryInfo.h"
-#include "llvm/IR/Constants.h"
-#include "llvm/IR/Function.h"
-#include "llvm/IR/Type.h"
-#include "llvm/IR/Value.h"
-#include "llvm/InitializePasses.h"
-#include "llvm/Pass.h"
-#include "llvm/Support/Debug.h"
-#include "llvm/Support/raw_ostream.h"
-#include <algorithm>
-#include <cassert>
-#include <limits>
-#include <memory>
-#include <utility>
-
-using namespace llvm;
-using namespace llvm::cflaa;
-
-#define DEBUG_TYPE "cfl-steens-aa"
-
-CFLSteensAAResult::CFLSteensAAResult(
-    std::function<const TargetLibraryInfo &(Function &F)> GetTLI)
-    : GetTLI(std::move(GetTLI)) {}
-CFLSteensAAResult::CFLSteensAAResult(CFLSteensAAResult &&Arg)
-    : AAResultBase(std::move(Arg)), GetTLI(std::move(Arg.GetTLI)) {}
-CFLSteensAAResult::~CFLSteensAAResult() = default;
-
-/// Information we have about a function and would like to keep around.
-class CFLSteensAAResult::FunctionInfo {
-  StratifiedSets<InstantiatedValue> Sets;
-  AliasSummary Summary;
-
-public:
-  FunctionInfo(Function &Fn, const SmallVectorImpl<Value *> &RetVals,
-               StratifiedSets<InstantiatedValue> S);
-
-  const StratifiedSets<InstantiatedValue> &getStratifiedSets() const {
-    return Sets;
-  }
-
-  const AliasSummary &getAliasSummary() const { return Summary; }
-};
-
-const StratifiedIndex StratifiedLink::SetSentinel =
-    std::numeric_limits<StratifiedIndex>::max();
-
-//===----------------------------------------------------------------------===//
-// Function declarations that require types defined in the namespace above
-//===----------------------------------------------------------------------===//
-
-/// Determines whether it would be pointless to add the given Value to our sets.
-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<InstantiatedValue> 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)
-          Summary.RetParamRelations.push_back(
-              ExternalRelation{CurrValue, Itr->second, UnknownOffset});
-        break;
-      }
-
-      auto &Link = Sets.getLink(SetIndex);
-      InterfaceMap.insert(std::make_pair(SetIndex, CurrValue));
-      auto ExternalAttrs = getExternallyVisibleAttrs(Link.Attrs);
-      if (ExternalAttrs.any())
-        Summary.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(InstantiatedValue{RetVal, 0});
-    if (RetInfo)
-      AddToRetParamRelations(0, RetInfo->Index);
-  }
-
-  // Populate RetParamRelations for parameters
-  unsigned I = 0;
-  for (auto &Param : Fn.args()) {
-    if (Param.getType()->isPointerTy()) {
-      auto ParamInfo = Sets.find(InstantiatedValue{&Param, 0});
-      if (ParamInfo)
-        AddToRetParamRelations(I + 1, ParamInfo->Index);
-    }
-    ++I;
-  }
-}
-
-// Builds the graph + StratifiedSets for a function.
-CFLSteensAAResult::FunctionInfo CFLSteensAAResult::buildSetsFrom(Function *Fn) {
-  CFLGraphBuilder<CFLSteensAAResult> GraphBuilder(*this, GetTLI(*Fn), *Fn);
-  StratifiedSetsBuilder<InstantiatedValue> SetBuilder;
-
-  // Add all CFLGraph nodes and all Dereference edges to StratifiedSets
-  auto &Graph = GraphBuilder.getCFLGraph();
-  for (const auto &Mapping : Graph.value_mappings()) {
-    auto Val = Mapping.first;
-    if (canSkipAddingToSets(Val))
-      continue;
-    auto &ValueInfo = Mapping.second;
-
-    assert(ValueInfo.getNumLevels() > 0);
-    SetBuilder.add(InstantiatedValue{Val, 0});
-    SetBuilder.noteAttributes(InstantiatedValue{Val, 0},
-                              ValueInfo.getNodeInfoAtLevel(0).Attr);
-    for (unsigned I = 0, E = ValueInfo.getNumLevels() - 1; I < E; ++I) {
-      SetBuilder.add(InstantiatedValue{Val, I + 1});
-      SetBuilder.noteAttributes(InstantiatedValue{Val, I + 1},
-                                ValueInfo.getNodeInfoAtLevel(I + 1).Attr);
-      SetBuilder.addBelow(InstantiatedValue{Val, I},
-                          InstantiatedValue{Val, I + 1});
-    }
-  }
-
-  // Add all assign edges to StratifiedSets
-  for (const auto &Mapping : Graph.value_mappings()) {
-    auto Val = Mapping.first;
-    if (canSkipAddingToSets(Val))
-      continue;
-    auto &ValueInfo = Mapping.second;
-
-    for (unsigned I = 0, E = ValueInfo.getNumLevels(); I < E; ++I) {
-      auto Src = InstantiatedValue{Val, I};
-      for (const auto &Edge : ValueInfo.getNodeInfoAtLevel(I).Edges)
-        SetBuilder.addWith(Src, Edge.Other);
-    }
-  }
-
-  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.emplace_front(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);
-  }
-  return Iter->second;
-}
-
-const AliasSummary *CFLSteensAAResult::getAliasSummary(Function &Fn) {
-  auto &FunInfo = ensureCached(&Fn);
-  if (FunInfo)
-    return &FunInfo->getAliasSummary();
-  else
-    return nullptr;
-}
-
-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 AliasResult::NoAlias;
-
-  Function *Fn = nullptr;
-  Function *MaybeFnA = const_cast<Function *>(parentFunctionOfValue(ValA));
-  Function *MaybeFnB = const_cast<Function *>(parentFunctionOfValue(ValB));
-  if (!MaybeFnA && !MaybeFnB) {
-    // The only times this is known to happen are when globals + InlineAsm are
-    // involved
-    LLVM_DEBUG(
-        dbgs()
-        << "CFLSteensAA: could not extract parent function information.\n");
-    return AliasResult::MayAlias;
-  }
-
-  if (MaybeFnA) {
-    Fn = MaybeFnA;
-    assert((!MaybeFnB || MaybeFnB == MaybeFnA) &&
-           "Interprocedural queries not supported");
-  } else {
-    Fn = MaybeFnB;
-  }
-
-  assert(Fn != nullptr);
-  auto &MaybeInfo = ensureCached(Fn);
-  assert(MaybeInfo);
-
-  auto &Sets = MaybeInfo->getStratifiedSets();
-  auto MaybeA = Sets.find(InstantiatedValue{ValA, 0});
-  if (!MaybeA)
-    return AliasResult::MayAlias;
-
-  auto MaybeB = Sets.find(InstantiatedValue{ValB, 0});
-  if (!MaybeB)
-    return AliasResult::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 AliasResult::MayAlias;
-  if (AttrsA.none() || AttrsB.none())
-    return AliasResult::NoAlias;
-  if (hasUnknownOrCallerAttr(AttrsA) || hasUnknownOrCallerAttr(AttrsB))
-    return AliasResult::MayAlias;
-  if (isGlobalOrArgAttr(AttrsA) && isGlobalOrArgAttr(AttrsB))
-    return AliasResult::MayAlias;
-  return AliasResult::NoAlias;
-}
-
-AnalysisKey CFLSteensAA::Key;
-
-CFLSteensAAResult CFLSteensAA::run(Function &F, FunctionAnalysisManager &AM) {
-  auto GetTLI = [&AM](Function &F) -> const TargetLibraryInfo & {
-    return AM.getResult<TargetLibraryAnalysis>(F);
-  };
-  return CFLSteensAAResult(GetTLI);
-}
-
-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 GetTLI = [this](Function &F) -> const TargetLibraryInfo & {
-    return this->getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
-  };
-  Result.reset(new CFLSteensAAResult(GetTLI));
-}
-
-void CFLSteensAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
-  AU.setPreservesAll();
-  AU.addRequired<TargetLibraryInfoWrapperPass>();
-}

llvm/lib/Analysis/CMakeLists.txt

add_llvm_component_library(LLVMAnalysis
   AssumptionCache.cpp
   BasicAliasAnalysis.cpp
   BlockFrequencyInfo.cpp
   BlockFrequencyInfoImpl.cpp
   BranchProbabilityInfo.cpp
   CFG.cpp
   CFGPrinter.cpp
   CFGSCCPrinter.cpp
-  CFLAndersAliasAnalysis.cpp
-  CFLSteensAliasAnalysis.cpp
   CGSCCPassManager.cpp
   CallGraph.cpp
   CallGraphSCCPass.cpp
   CallPrinter.cpp
   CaptureTracking.cpp
   CmpInstAnalysis.cpp
   CostModel.cpp
   CodeMetrics.cpp

llvm/lib/CodeGen/TargetPassConfig.cpp

 //
 //===---------------------------------------------------------------------===//
 
 #include "llvm/CodeGen/TargetPassConfig.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Analysis/BasicAliasAnalysis.h"
-#include "llvm/Analysis/CFLAndersAliasAnalysis.h"
-#include "llvm/Analysis/CFLSteensAliasAnalysis.h"
 #include "llvm/Analysis/CallGraphSCCPass.h"
 #include "llvm/Analysis/ScopedNoAliasAA.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/Analysis/TypeBasedAliasAnalysis.h"
 #include "llvm/CodeGen/BasicBlockSectionsProfileReader.h"
 #include "llvm/CodeGen/CSEConfigBase.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachinePassRegistry.h"
static cl::opt<bool> MISchedPostRA(
     "misched-postra", cl::Hidden,
     cl::desc(
         "Run MachineScheduler post regalloc (independent of preRA sched)"));
 
 // Experimental option to run live interval analysis early.
 static cl::opt<bool> EarlyLiveIntervals("early-live-intervals", cl::Hidden,
     cl::desc("Run live interval analysis earlier in the pipeline"));
 
-// Experimental option to use CFL-AA in codegen
-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")));
-
 /// Option names for limiting the codegen pipeline.
 /// Those are used in error reporting and we didn't want
 /// to duplicate their names all over the place.
 static const char StartAfterOptName[] = "start-after";
 static const char StartBeforeOptName[] = "start-before";
 static const char StopAfterOptName[] = "stop-after";
 static const char StopBeforeOptName[] = "stop-before";
 

 
 #define SET_BOOLEAN_OPTION(Option) Opt.Option = Option;
 
   SET_BOOLEAN_OPTION(EarlyLiveIntervals)
   SET_BOOLEAN_OPTION(EnableBlockPlacementStats)
   SET_BOOLEAN_OPTION(EnableImplicitNullChecks)
   SET_BOOLEAN_OPTION(EnableMachineOutliner)
   SET_BOOLEAN_OPTION(MISchedPostRA)
-  SET_BOOLEAN_OPTION(UseCFLAA)
   SET_BOOLEAN_OPTION(DisableMergeICmps)
   SET_BOOLEAN_OPTION(DisableLSR)
   SET_BOOLEAN_OPTION(DisableConstantHoisting)
   SET_BOOLEAN_OPTION(DisableCGP)
   SET_BOOLEAN_OPTION(DisablePartialLibcallInlining)
   SET_BOOLEAN_OPTION(DisableSelectOptimize)
   SET_BOOLEAN_OPTION(PrintLSR)
   SET_BOOLEAN_OPTION(PrintISelInput)

 /// following machine independent optimization.
 void TargetPassConfig::addIRPasses() {
   // 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());
 
   if (getOptLevel() != CodeGenOpt::None) {
-    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.
     addPass(createTypeBasedAAWrapperPass());
     addPass(createScopedNoAliasAAWrapperPass());
     addPass(createBasicAAWrapperPass());
 

llvm/lib/Passes/PassBuilder.cpp

 #include "llvm/Analysis/AliasAnalysisEvaluator.h"
 #include "llvm/Analysis/AliasSetTracker.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/BasicAliasAnalysis.h"
 #include "llvm/Analysis/BlockFrequencyInfo.h"
 #include "llvm/Analysis/BranchProbabilityInfo.h"
 #include "llvm/Analysis/CFGPrinter.h"
 #include "llvm/Analysis/CFGSCCPrinter.h"
-#include "llvm/Analysis/CFLAndersAliasAnalysis.h"
-#include "llvm/Analysis/CFLSteensAliasAnalysis.h"
 #include "llvm/Analysis/CGSCCPassManager.h"
 #include "llvm/Analysis/CallGraph.h"
 #include "llvm/Analysis/CallPrinter.h"
 #include "llvm/Analysis/CostModel.h"
 #include "llvm/Analysis/CycleAnalysis.h"
 #include "llvm/Analysis/DDG.h"
 #include "llvm/Analysis/DDGPrinter.h"
 #include "llvm/Analysis/Delinearization.h"

llvm/lib/Passes/PassRegistry.def

 FUNCTION_ANALYSIS("pass-instrumentation", PassInstrumentationAnalysis(PIC))
 FUNCTION_ANALYSIS("divergence", DivergenceAnalysis())
 
 #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-anders-aa", CFLAndersAA())
-FUNCTION_ALIAS_ANALYSIS("cfl-steens-aa", CFLSteensAA())
 FUNCTION_ALIAS_ANALYSIS("objc-arc-aa", objcarc::ObjCARCAA())
 FUNCTION_ALIAS_ANALYSIS("scev-aa", SCEVAA())
 FUNCTION_ALIAS_ANALYSIS("scoped-noalias-aa", ScopedNoAliasAA())
 FUNCTION_ALIAS_ANALYSIS("tbaa", TypeBasedAA())
 #undef FUNCTION_ALIAS_ANALYSIS
 #undef FUNCTION_ANALYSIS
 
 #ifndef FUNCTION_PASS

llvm/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/STLExtras.h"
 #include "llvm/ADT/SmallVector.h"
-#include "llvm/Analysis/CFLAndersAliasAnalysis.h"
-#include "llvm/Analysis/CFLSteensAliasAnalysis.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/ScopedNoAliasAA.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/TypeBasedAliasAnalysis.h"
 #include "llvm/IR/LegacyPassManager.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/ManagedStatic.h"
 #include "llvm/Target/CGPassBuilderOption.h"

llvm/test/Analysis/CFLAliasAnalysis/Andersen/assign.ll

-; This testcase ensures that CFL AA handles assignment in an inclusion-based 
-; manner
-
-; RUN: opt < %s -aa-pipeline=cfl-anders-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
-
-; CHECK-LABEL: Function: test_assign
-; CHECK: NoAlias: i64* %a, i64* %b
-; CHECK: NoAlias: i64* %b, i32* %c
-; CHECK: NoAlias: i64* %a, i32* %d
-; CHECK: NoAlias: i32* %c, i32* %d
-; CHECK: MayAlias: i64* %a, i32* %e
-; CHECK: MayAlias: i64* %b, i32* %e
-; CHECK: MayAlias: i32* %c, i32* %e
-; CHECK: MayAlias: i32* %d, i32* %e
-define void @test_assign(i1 %cond) {
-  %a = alloca i64, align 8
-  %b = alloca i64, align 8
-
-  %c = bitcast i64* %a to i32*
-  %d = bitcast i64* %b to i32*
-  %e = select i1 %cond, i32* %c, i32* %d
-  load i64, i64* %a
-  load i64, i64* %b
-  load i32, i32* %c
-  load i32, i32* %d
-  load i32, i32* %e
-  ret void
-}

llvm/test/Analysis/CFLAliasAnalysis/Andersen/assign2.ll

-; This testcase ensures that CFL AA handles assignment in an inclusion-based 
-; manner
-
-; RUN: opt < %s -aa-pipeline=cfl-anders-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
-
-; CHECK-LABEL: Function: test_assign2
-; CHECK: NoAlias: i64* %a, i32* %b
-; CHECK: NoAlias: i32* %b, i32* %c
-; CHECK: NoAlias: i32* %b, i32* %d
-; CHECK: MayAlias: i64* %a, i32* %e
-; CHECK: MayAlias: i32* %b, i32* %e
-; CHECK: MayAlias: i32* %c, i32* %e
-; CHECK: MayAlias: i32* %d, i32* %e
-define void @test_assign2(i1 %cond) {
-  %a = alloca i64, align 8
-  %b = alloca i32, align 4
-
-  %c = bitcast i64* %a to i32*
-  %d = bitcast i64* %a to i32*
-  %e = select i1 %cond, i32* %c, i32* %b
-  load i64, i64* %a
-  load i32, i32* %b
-  load i32, i32* %c
-  load i32, i32* %d
-  load i32, i32* %e
-  ret void
-}

llvm/test/Analysis/CFLAliasAnalysis/Andersen/attrs-below.ll

-; This testcase ensures that AliasAttrs are propagated not only on the same 
-; level but also downward.
-
-; RUN: opt < %s -aa-pipeline=cfl-anders-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
-
-; CHECK-LABEL: Function: test_attr_below
-; CHECK-DAG: MayAlias: i64*** %p, i64* %q
-; CHECK-DAG: NoAlias: i64* %esc, i64*** %p
-; CHECK-DAG: NoAlias: i64* %esc, i64* %q
-
-; CHECK-DAG: MayAlias: i64*** %p, i64* %unknown
-; CHECK-DAG: MayAlias: i64* %q, i64* %unknown
-; CHECK-DAG: MayAlias: i64* %esc, i64* %unknown
-; CHECK-DAG: MayAlias: i64** %pdrf, i64* %q
-; CHECK-DAG: MayAlias: i64* %esc, i64** %pdrf
-; CHECK-DAG: MayAlias: i64** %pdrf, i64* %unknown
-; CHECK-DAG: MayAlias: i64* %pdrf2, i64* %q
-; CHECK-DAG: MayAlias: i64* %esc, i64* %pdrf2
-; CHECK-DAG: MayAlias: i64* %pdrf2, i64* %unknown
-define void @test_attr_below(i64*** %p, i64* %q) {
-  %esc = alloca i64, align 8
-  %escint = ptrtoint i64* %esc to i64
-  %unknown = inttoptr i64 %escint to i64*
-
-  %pdrf = load i64**, i64*** %p
-  %pdrf2 = load i64*, i64** %pdrf
-
-  load i64, i64* %q
-  load i64, i64* %esc
-  load i64, i64* %unknown
-  load i64, i64* %pdrf2
-
-  ret void
-}
-
-; CHECK-LABEL: Function: test_attr_assign_below
-; CHECK-DAG: MayAlias: i64*** %p, i64** %sel
-; CHECK-DAG: MayAlias: i64* %q, i64** %sel
-; CHECK-DAG: MayAlias: i64** %a, i64** %sel
-; CHECK-DAG: MayAlias: i64** %pdrf, i64** %sel
-
-; CHECK-DAG: MayAlias: i64** %c, i64*** %p
-; CHECK-DAG: MayAlias: i64** %c, i64* %q
-; CHECK-DAG: MayAlias: i64** %a, i64** %c
-; CHECK-DAG: MayAlias: i64** %c, i64** %pdrf
-; CHECK-DAG: MayAlias: i64** %c, i64** %sel
-
-; CHECK-DAG: MayAlias: i64* %d, i64*** %p
-; CHECK-DAG: MayAlias: i64* %d, i64* %q
-; CHECK-DAG: MayAlias: i64* %d, i64** %pdrf
-; CHECK-DAG: MayAlias: i64* %d, i64** %sel
-define void @test_attr_assign_below(i64*** %p, i64* %q, i1 %cond) {
-  %a = alloca i64*, align 8
-  %pdrf = load i64**, i64*** %p
-  %sel = select i1 %cond, i64** %a, i64** %pdrf
-
-  %b = alloca i64**, align 8
-  store i64** %sel, i64*** %b
-
-  %c = load i64**, i64*** %b
-  %d = load i64*, i64** %c
-
-  load i64, i64* %q
-  load i64*, i64** %a
-  load i64*, i64** %pdrf
-  load i64*, i64** %sel
-  load i64*, i64** %c
-  load i64, i64* %d
-
-  ret void
-}
-

llvm/test/Analysis/CFLAliasAnalysis/Andersen/attrs.ll

-; This testcase ensures that CFL AA handles escaped values no more conservative than it should
-
-; RUN: opt < %s -aa-pipeline=cfl-anders-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
-
-; CHECK-LABEL: Function: test_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*
-  load i32, i32* %a
-  load i32, i32* %b
-  load i32, i32* %aAlias
-  ret void
-}
-
-; CHECK-LABEL: Function: test_global_param
-; CHECK-DAG: NoAlias: i32* %a, i32** %x
-; CHECK-DAG: MayAlias: i32* %a, i32* %xload
-; CHECK-DAG: MayAlias: i32* %a, i32* %gload
-; CHECK-DAG: MayAlias: i32* %gload, i32* %xload
-; CHECK-DAG: MayAlias: i32** %x, i32** @ext_global
-; CHECK-DAG: 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
-  load i32, i32* %a
-  load i32, i32* %xload
-  load i32, i32* %gload
-  ret void
-}
-
-declare void @external_func(i32**)
-; CHECK-LABEL: Function: test_external_call
-; CHECK-DAG: NoAlias: i32* %b, i32* %x
-; CHECK-DAG: NoAlias: i32** %a, i32* %b
-; CHECK-DAG: MayAlias: i32* %c, i32* %x
-; CHECK-DAG: MayAlias: i32** %a, i32* %c
-; CHECK-DAG: 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
-  load i32, i32* %x
-  load i32, i32* %b
-  load i32, i32* %c
-  ret void
-}
-
-declare void @external_func_readonly(i32**) readonly
-; CHECK-LABEL: Function: test_external_call_func_readonly
-; CHECK-DAG: MayAlias: i32* %c, i32* %x
-; CHECK-DAG: NoAlias: i32** %a, i32* %c
-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
-  load i32, i32* %x
-  load i32, i32* %c
-  ret void
-}
-
-; CHECK-LABEL: Function: test_external_call_callsite_readonly
-; CHECK-DAG: MayAlias: i32* %c, i32* %x
-; CHECK-DAG: NoAlias: i32** %a, i32* %c
-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
-  load i32, i32* %x
-  load i32, i32* %c
-  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)
-  load i32, i32* %x
-  load i32, i32* %a
-  load i32, i32* %c
-  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)
-  load i32, i32* %x
-  load i32, i32* %a
-  load i32, i32* %c
-  ret void
-}

llvm/test/Analysis/CFLAliasAnalysis/Andersen/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 -aa-pipeline=cfl-anders-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
-  load i32, i32* %a
-  load i32, i32* %b
-  call void @noop_callee(i32* %a, i32* %b)
-
-  ret void
-}

llvm/test/Analysis/CFLAliasAnalysis/Andersen/cycle.ll

-; This testcase ensures that CFL AA handles assignment cycles correctly
-
-; RUN: opt < %s -aa-pipeline=cfl-anders-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
-
-; CHECK-LABEL: Function: test_cycle
-; CHECK: NoAlias: i64* %a, i64** %b
-; CHECK: NoAlias: i64* %a, i64*** %c
-; CHECK: NoAlias: i64** %b, i64*** %c
-; CHECK: NoAlias: i64* %a, i64**** %d
-; CHECK: NoAlias: i64** %b, i64**** %d
-; CHECK: NoAlias: i64*** %c, i64**** %d
-; CHECK: NoAlias: i64* %a, i64* %e
-; CHECK: NoAlias: i64** %b, i64* %e
-; CHECK: NoAlias: i64*** %c, i64* %e
-; CHECK: MayAlias: i64* %a, i64* %f
-; CHECK: NoAlias: i64** %b, i64* %f
-; CHECK: NoAlias: i64*** %c, i64* %f
-; CHECK: MayAlias: i64**** %d, i64* %f
-; CHECK: MayAlias: i64* %e, i64* %f
-define void @test_cycle() {
-  %a = alloca i64, align 8
-  %b = alloca i64*, align 8
-  %c = alloca i64**, align 8
-  %d = alloca i64***, align 8
-  load i64, i64* %a
-  store i64* %a, i64** %b
-  store i64** %b, i64*** %c
-  store i64*** %c, i64**** %d
-
-  %e = bitcast i64**** %d to i64*
-  load i64, i64* %e
-  store i64* %e, i64** %b
-  %f = load i64*, i64** %b
-  load i64, i64* %f
-  ret void
-}

llvm/test/Analysis/CFLAliasAnalysis/Andersen/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 -aa-pipeline=cfl-anders-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-DAG: NoAlias: i32* %a, i32** %x
-; CHECK-DAG: NoAlias: i32* %b, i32** %x
-; CHECK-DAG: NoAlias: i32* %a, i32* %b
-; CHECK-DAG: NoAlias: i32** %p, i32** %x
-; CHECK-DAG: NoAlias: i32* %a, i32** %p
-; CHECK-DAG: NoAlias: i32* %b, i32** %p
-; CHECK-DAG: MayAlias: i32* %a, i32* %c
-; CHECK-DAG: NoAlias: i32* %b, i32* %c
-; CHECK-DAG: 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
-  
-  load i32, i32* %a
-  load i32, i32* %b
-  store i32* %a, i32** %p
-  call void @escape_arg_deref(i32** %p)
-  %c = load i32*, i32** %x
-  load i32, i32* %c
-
-  ret void
-}

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

-; This testcase ensures that CFL AA answers queries soundly when callee tries 
-; to escape its parameters
-
-; RUN: opt < %s -aa-pipeline=cfl-anders-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-DAG: NoAlias: i32* %a, i32** %x
-; CHECK-DAG: NoAlias: i32* %b, i32** %x
-; CHECK-DAG: NoAlias: i32* %a, i32* %b
-; CHECK-DAG: NoAlias: i32* %c, i32** %x
-; CHECK-DAG: NoAlias: i32* %a, i32* %c
-; CHECK-DAG: NoAlias: i32* %b, i32* %c
-; CHECK-DAG: MayAlias: i32* %a, i32* %d
-; CHECK-DAG: MayAlias: i32* %b, i32* %d
-; CHECK-DAG: 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
-  load i32, i32* %a
-  load i32, i32* %b
-  load i32, i32* %c
-  call void @escape_arg(i32* %a)
-  call void @escape_arg(i32* %b)
-  %d = load i32*, i32** %x
-  load i32, i32* %d
-
-  ret void
-}

llvm/test/Analysis/CFLAliasAnalysis/Andersen/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 -aa-pipeline=cfl-anders-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
-
-; Temporarily disable modref checks
-; NoModRef: Ptr: i32* %a <-> %c = call i32* @return_arg_callee(i32* %a, i32* %b)
-; NoModRef: Ptr: i32* %b <-> %c = call i32* @return_arg_callee(i32* %a, i32* %b)
-; NoModRef: Ptr: i32* %c <-> %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)
-  load i32, i32* %a
-  load i32, i32* %b
-  load i32, i32* %c
-
-  ret void
-}

llvm/test/Analysis/CFLAliasAnalysis/Andersen/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 -aa-pipeline=cfl-anders-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
-
-; Temporarily disable modref checks
-; Just Ref: Ptr: i32** %p <-> %c = call i32* @return_deref_arg_multilevel_callee(i32*** %pp)
-; Just Ref: Ptr: i32*** %pp <-> %c = call i32* @return_deref_arg_multilevel_callee(i32*** %pp)
-; Just Ref: Ptr: i32** %lpp <-> %c = call i32* @return_deref_arg_multilevel_callee(i32*** %pp)
-
-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
-
-  load i32, i32* %a
-  load i32, i32* %b
-  store i32* %a, i32** %p
-  store i32** %p, i32*** %pp
-  %c = call i32* @return_deref_arg_multilevel_callee(i32*** %pp)
-  load i32, i32* %c
-
-  %lpp = load i32**, i32*** %pp
-  %lpp_deref = load i32*, i32** %lpp
-  %lp = load i32*, i32** %p
-  load i32, i32* %lpp_deref
-  load i32, i32* %lp
-
-  ret void
-}

llvm/test/Analysis/CFLAliasAnalysis/Andersen/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 -aa-pipeline=cfl-anders-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
-
-; Temporarily disable modref checks
-; NoModRef: Ptr: i32* %a <-> %c = call i32* @return_deref_arg_callee(i32** %p)
-; NoModRef: Ptr: i32* %b <-> %c = call i32* @return_deref_arg_callee(i32** %p)
-; Just Ref: Ptr: i32** %p <-> %c = call i32* @return_deref_arg_callee(i32** %p)
-; NoModRef: Ptr: i32* %c <-> %c = call i32* @return_deref_arg_callee(i32** %p)
-; NoModRef: Ptr: i32* %lp <-> %c = call i32* @return_deref_arg_callee(i32** %p)
-define void @test_return_deref_arg() {
-  %a = alloca i32, align 4
-  %b = alloca i32, align 4
-  %p = alloca i32*, align 8
-
-  load i32, i32* %a
-  load i32, i32* %b
-  store i32* %a, i32** %p
-  %c = call i32* @return_deref_arg_callee(i32** %p)
-  load i32, i32* %c
-
-  %lp = load i32*, i32** %p
-  load i32, i32* %lp
-
-  ret void
-}

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

-; This testcase ensures that CFL AA answers queries soundly when callee tries 
-; to return an escaped pointer
-
-; RUN: opt < %s -aa-pipeline=cfl-anders-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
-  load i32, i32* %a
-  load i32, i32* %b
-  load i32, i32* %c
-  load i32, i32* %d
-
-  ret void
-}

llvm/test/Analysis/CFLAliasAnalysis/Andersen/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 -aa-pipeline=cfl-anders-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-DAG: NoAlias: i32* %a, i32*** %b
-; CHECK-DAG: NoAlias: i32*** %b, i32** %p
-; CHECK-DAG: NoAlias: i32*** %b, i32*** %pp
-; CHECK-DAG: NoAlias: i32* %a, i32** %lb
-; CHECK-DAG: NoAlias: i32** %lb, i32** %p
-; CHECK-DAG: NoAlias: i32** %lb, i32*** %pp
-; CHECK-DAG: NoAlias: i32*** %b, i32** %lb
-; CHECK-DAG: MayAlias: i32* %a, i32* %lb_deref
-; CHECK-DAG: NoAlias: i32* %lb_deref, i32** %lpp
-; CHECK-DAG: MayAlias: i32* %lb_deref, i32* %lpp_deref
-; CHECK-DAG: NoAlias: i32** %lpp, i32* %lpp_deref
-; CHECK-DAG: MayAlias: i32* %lb_deref, i32* %lp
-; CHECK-DAG: NoAlias: i32* %lp, i32** %lpp
-; CHECK-DAG: MayAlias: i32* %lp, i32* %lpp_deref
-
-; Temporarily disable modref checks
-; Just Mod: Ptr: i32*** %b <-> %b = call i32*** @return_ref_arg_multilevel_callee(i32* %a)
-; Just Mod: Ptr: i32** %lb <-> %b = call i32*** @return_ref_arg_multilevel_callee(i32* %a)
-define void @test_return_ref_arg_multilevel() {
-  %a = alloca i32, align 4
-  %p = alloca i32*, align 8
-  %pp = alloca i32**, align 8
-
-  load i32, i32* %a
-  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
-  load i32, i32* %lb_deref
-  load i32, i32* %lpp_deref
-  load i32, i32* %lp
-
-  ret void
-}

llvm/test/Analysis/CFLAliasAnalysis/Andersen/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 -aa-pipeline=cfl-anders-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: NoAlias: i32** %b, i32** %p
-; CHECK: MayAlias: i32* %a, i32* %lb
-; CHECK: NoAlias: i32* %lb, i32** %p
-; CHECK: NoAlias: i32** %b, i32* %lb
-; CHECK: NoAlias: i32* %lp, i32** %p
-; CHECK: NoAlias: i32** %b, i32* %lp
-; CHECK: MayAlias: i32* %lb, i32* %lp
-
-; Temporarily disable modref checks
-; Just Mod: Ptr: i32** %b <-> %b = call i32** @return_ref_arg_callee(i32* %a)
-define void @test_return_ref_arg() {
-  %a = alloca i32, align 4
-  %p = alloca i32*, align 8
-
-  load i32, i32* %a
-  store i32* %a, i32** %p
-  %b = call i32** @return_ref_arg_callee(i32* %a)
-
-  %lb = load i32*, i32** %b
-  %lp = load i32*, i32** %p
-  load i32, i32* %lb
-  load i32, i32* %lp
-
-  ret void
-}

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

-; This testcase ensures that CFL AA answers queries soundly when callee tries 
-; to return an unknown pointer
-
-; RUN: opt < %s -aa-pipeline=cfl-anders-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-DAG: NoAlias: i32* %a, i32* %b
-; CHECK-DAG: MayAlias: i32* %c, i32* %x
-; CHECK-DAG: NoAlias: i32* %a, i32* %c
-; CHECK-DAG: 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)
-  load i32, i32* %a
-  load i32, i32* %b
-  load i32, i32* %c
-  load i32, i32* %x
-
-  ret void
-}
-
-@g2 = external global i32*
-define i32** @return_unknown_callee2() {
-  ret i32** @g2
-}
-; CHECK-LABEL: Function: test_return_unknown2
-; CHECK-DAG: MayAlias: i32** %a, i32* %x
-; CHECK-DAG: MayAlias: i32* %b, i32* %x
-; CHECK-DAG: MayAlias: i32** %a, i32* %b
-define void @test_return_unknown2(i32* %x) {
-  %a = call i32** @return_unknown_callee2()
-  %b = load i32*, i32** %a
-  load i32, i32* %b
-  load i32, i32* %x
-
-  ret void
-}

llvm/test/Analysis/CFLAliasAnalysis/Andersen/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 -aa-pipeline=cfl-anders-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* %b
-; 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, i32* %lpp_deref
-; 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
-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
-
-  load i32, i32* %a
-  load i32, i32* %b
-  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
-  load i32, i32* %lpp_deref
-  load i32, i32* %lp
-
-  ret void
-}

llvm/test/Analysis/CFLAliasAnalysis/Andersen/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 -aa-pipeline=cfl-anders-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** %p, i32* %x
-; 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
-
-  load i32, i32* %x
-  load i32, i32* %a
-  load i32, i32* %b
-  store i32* %a, i32** %p
-  call void @store_arg_unknown_callee(i32** %p)
-
-  %lp = load i32*, i32** %p
-  load i32, i32* %lp
-
-  ret void
-}

llvm/test/Analysis/CFLAliasAnalysis/Andersen/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 -aa-pipeline=cfl-anders-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* %b
-; 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: NoAlias: i32* %a, i32* %lq
-; CHECK: MayAlias: i32* %b, i32* %lq
-; CHECK: MayAlias: i32* %lp, i32* %lq
-
-; Temporarily disable modref checks
-; NoModRef: Ptr: i32* %a <-> call void @store_arg_callee(i32** %p, i32* %b)
-; Just Ref: Ptr: i32* %b <-> call void @store_arg_callee(i32** %p, i32* %b)
-; Just Mod: Ptr: i32** %p  <-> call void @store_arg_callee(i32** %p, i32* %b)
-; NoModRef: Ptr: i32** %q  <-> call void @store_arg_callee(i32** %p, i32* %b)
-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
-
-  load i32, i32* %a
-  load i32, i32* %b
-  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
-  load i32, i32* %lp
-  load i32, i32* %lq
-
-  ret void
-}

llvm/test/Analysis/CFLAliasAnalysis/Andersen/memalias.ll

-; This testcase ensures that CFL AA correctly handles simple memory alias 
-; pattern
-
-; RUN: opt < %s -aa-pipeline=cfl-anders-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
-
-; CHECK-LABEL: Function: test_memalias
-; CHECK: NoAlias: i64* %a, i64** %b
-; CHECK: NoAlias: i64* %a, i32** %c
-; CHECK: MayAlias: i64* %a, i32* %d
-; CHECK: NoAlias: i64** %b, i32* %d
-; CHECK: NoAlias: i32** %c, i32* %d
-define void @test_memalias() {
-  %a = alloca i64, align 8
-  %b = alloca i64*, align 8
-  load i64, i64* %a
-  store i64* %a, i64** %b
-
-  %c = bitcast i64** %b to i32**
-  %d = load i32*, i32** %c
-  load i32, i32* %d
-  ret void
-}

llvm/test/Analysis/CFLAliasAnalysis/Andersen/struct.ll

-; Ensures that our struct ops are sane.
-
-; RUN: opt < %s -aa-pipeline=cfl-anders-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
-
-; Since we ignore non-pointer values, we effectively ignore extractvalue
-; instructions. This means that %c "doesn't exist" in test_structure's graph,
-; so we currently get MayAlias.
-; XFAIL: *
-
-; CHECK-LABEL: Function: test_structure
-; CHECK: NoAlias: i64** %c, { i64**, i64** }* %a
-define void @test_structure() {
-  %a = alloca {i64**, i64**}, align 8
-  %b = load {i64**, i64**}, {i64**, i64**}* %a
-  %c = extractvalue {i64**, i64**} %b, 0
-  ret void
-}

llvm/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 -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
-
-; CHECK:     Function: test
-
-@g = external global i32
-
-; CHECK: MayAlias:  i32* %arg1, i32* %arg2
-; CHECK: NoAlias: i32* %A, i32* %arg1
-; CHECK: NoAlias: i32* %A, i32* %arg2
-; CHECK: MayAlias:  i32* %arg1, i32* @g
-; CHECK: MayAlias:  i32* %arg2, i32* @g
-; CHECK: MayAlias:  i32* %A, i32* @g
-define void @test(i1 %c, i32* %arg1, i32* %arg2) {
-  %A = alloca i32
-  load i32, i32* %arg1
-  load i32, i32* %arg2
-  load i32, i32* %A
-  load i32, i32* @g
-
-  ret void
-}

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

-; This testcase ensures that CFL AA gives conservative answers on variables
-; that involve arguments.
-
-; RUN: opt < %s -aa-pipeline=cfl-steens-aa -passes=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
-  load i32, i32* %a
-  load i32, i32* %b
-  load i32, i32* %arg1
-  load i32, i32* %arg2
-
-  ret void
-}

llvm/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 -aa-pipeline=cfl-steens-aa -passes=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))
-  load [1 x i8], [1 x i8]* @G
-  load i8, i8* getelementptr inbounds ([1 x i8], [1 x i8]* @G, i64 0, i64 0)
-  ret void
-}

llvm/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 -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*
-  load i32, i32* %a
-  load i32, i32* %b
-  load i32, i32* %aAlias
-  ret void
-}
-
-; CHECK-LABEL: Function: test_global_param
-; CHECK-DAG: NoAlias: i32* %a, i32** %x
-; CHECK-DAG: MayAlias: i32* %a, i32* %xload
-; CHECK-DAG: MayAlias: i32* %a, i32* %gload
-; CHECK-DAG: MayAlias: i32* %gload, i32* %xload
-; CHECK-DAG: MayAlias: i32** %x, i32** @ext_global
-; CHECK-DAG: 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
-  load i32, i32* %a
-  load i32, i32* %xload
-  load i32, i32* %gload
-  ret void
-}
-
-declare void @external_func(i32**)
-; CHECK-LABEL: Function: test_external_call
-; CHECK-DAG: NoAlias: i32* %b, i32* %x
-; CHECK-DAG: NoAlias: i32** %a, i32* %b
-; CHECK-DAG: MayAlias: i32* %c, i32* %x
-; CHECK-DAG: MayAlias: i32** %a, i32* %c
-; CHECK-DAG: 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
-  load i32, i32* %x
-  load i32, i32* %b
-  load i32, i32* %c
-  ret void
-}
-
-declare void @external_func_readonly(i32**) readonly
-; CHECK-LABEL: Function: test_external_call_func_readonly
-; CHECK-DAG: MayAlias: i32* %c, i32* %x
-; CHECK-DAG: NoAlias: i32** %a, i32* %c
-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
-  load i32, i32* %x
-  load i32, i32* %c
-  ret void
-}
-
-; CHECK-LABEL: Function: test_external_call_callsite_readonly
-; CHECK-DAG: MayAlias: i32* %c, i32* %x
-; CHECK-DAG: NoAlias: i32** %a, i32* %c
-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
-  load i32, i32* %x
-  load i32, i32* %c
-  ret void
-}
-
-declare i32* @external_func_normal_return(i32*)
-; CHECK-LABEL: Function: test_external_call_normal_return
-; CHECK-DAG: MayAlias: i32* %c, i32* %x
-; CHECK-DAG: 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)
-  load i32, i32* %a
-  load i32, i32* %x
-  load i32, i32* %c
-  ret void
-}
-
-declare noalias i32* @external_func_noalias_return(i32*)
-; CHECK-LABEL: Function: test_external_call_noalias_return
-; CHECK-DAG: NoAlias: i32* %c, i32* %x
-; CHECK-DAG: 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)
-  load i32, i32* %a
-  load i32, i32* %x
-  load i32, i32* %c
-  ret void
-}

llvm/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 -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
-  load i32, i32* %a
-  load i32, i32* %b
-  call void @noop_callee(i32* %a, i32* %b)
-
-  ret void
-}

llvm/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 -aa-pipeline=cfl-steens-aa -passes=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
-  %ignore1 = load i32*, i32** %A
-  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/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 -aa-pipeline=cfl-steens-aa -passes=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
-  load i32, i32* %D
-  load i32, i32* %F
-  load i8, i8* %X
-
-  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
-  load i32, i32* %arg0
-  load i32, i32* %F
-  load i32, i32* %H
-
-  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
-  load i32, i32* %arg0
-  load i32, i32* %A
-  ret void
-}

llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/const-exprs.ll

-; RUN: opt %s -S -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-all-alias-modref-info 2>&1 | FileCheck %s
-;
-; Regression: we weren't properly checking constexpr selects.
-
-@g = extern_weak dso_local global i32, align 4
-@g2 = extern_weak dso_local global i32, align 4
-@g3 = extern_weak dso_local global i32, align 4
-
-; CHECK-LABEL: Function: foo
-; CHECK-DAG: NoAlias: i32** %a, i32* select (i1 icmp ne (i32* @g, i32* null), i32* @g2, i32* @g3)
-; CHECK-DAG: NoAlias: i32** %a, i32* %b
-; CHECK-DAG: MayAlias: i32* %b, i32* select (i1 icmp ne (i32* @g, i32* null), i32* @g2, i32* @g3)
-; CHECK-DAG: NoAlias: i32** %a, i32* @g2
-; CHECK-DAG: MayAlias: i32* @g2, i32* select (i1 icmp ne (i32* @g, i32* null), i32* @g2, i32* @g3)
-; CHECK-DAG: MayAlias: i32* %b, i32* @g2
-; CHECK-DAG: NoAlias: i32** %a, i32* @g3
-; CHECK-DAG: MayAlias: i32* @g3, i32* select (i1 icmp ne (i32* @g, i32* null), i32* @g2, i32* @g3)
-; CHECK-DAG: MayAlias: i32* %b, i32* @g3
-; CHECK-DAG: MayAlias: i32* @g2, i32* @g3
-
-define void @foo() {
-entry:
-  %a = alloca i32*, align 8
-  load i32, i32* select (i1 icmp ne (i32* @g, i32* null), i32* @g2, i32* @g3)
-  store i32* select (i1 icmp ne (i32* @g, i32* null), i32* @g2, i32* @g3), i32** %a
-  %b = load i32*, i32** %a
-  %c = load i32, i32* %b
-  %d = load i32, i32* @g2
-  %e = load i32, i32* @g3
-  ret void
-}

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

-; RUN: opt < %s -aa-pipeline=cfl-steens-aa -passes=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/test/Analysis/CFLAliasAnalysis/Steensgaard/empty.ll

-; RUN: opt < %s -aa-pipeline=basic-aa,cfl-steens-aa -passes=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/test/Analysis/CFLAliasAnalysis/Steensgaard/full-store-partial-alias.ll

-; RUN: opt -S -aa-pipeline=tbaa,cfl-steens-aa -passes=gvn < %s | FileCheck -check-prefix=CFLSteensAA %s
-; RUN: opt -S -aa-pipeline=tbaa -passes=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"}
-!3 = !{!5, !5, i64 0}
-!4 = !{!"double", !1}
-!5 = !{!"int", !1}

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

-; This testcase ensures that gep result does not alias gep indices
-
-; 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
-  load [2 x i32], [2 x i32]* %a
-  load [2 x i32], [2 x i32]* %b
-  load i32, i32* %c
-  load i32, i32* %d
-  ret void
-}

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

-; RUN: opt < %s -aa-pipeline=cfl-steens-aa -passes=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/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 -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-DAG: NoAlias: i32* %a, i32** %x
-; CHECK-DAG: NoAlias: i32* %b, i32** %x
-; CHECK-DAG: NoAlias: i32* %a, i32* %b
-; CHECK-DAG: NoAlias: i32** %p, i32** %x
-; CHECK-DAG: NoAlias: i32* %a, i32** %p
-; CHECK-DAG: NoAlias: i32* %b, i32** %p
-; CHECK-DAG: MayAlias: i32* %a, i32* %c
-; CHECK-DAG: NoAlias: i32* %b, i32* %c
-; CHECK-DAG: 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
-  
-  load i32, i32* %a
-  load i32, i32* %b
-  store i32* %a, i32** %p
-  call void @escape_arg_deref(i32** %p)
-  %c = load i32*, i32** %x
-  load i32, i32* %c
-
-  ret void
-}

llvm/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 -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-DAG: NoAlias: i32* %a, i32** %x
-; CHECK-DAG: NoAlias: i32* %b, i32** %x
-; CHECK-DAG: NoAlias: i32* %a, i32* %b
-; CHECK-DAG: NoAlias: i32* %c, i32** %x
-; CHECK-DAG: NoAlias: i32* %a, i32* %c
-; CHECK-DAG: NoAlias: i32* %b, i32* %c
-; CHECK-DAG: MayAlias: i32* %a, i32* %d
-; CHECK-DAG: MayAlias: i32* %b, i32* %d
-; CHECK-DAG: 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
-  load i32, i32* %a
-  load i32, i32* %b
-  load i32, i32* %c
-  call void @escape_arg(i32* %a)
-  call void @escape_arg(i32* %b)
-  %d = load i32*, i32** %x
-  load i32, i32* %d
-
-  ret void
-}

llvm/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 -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
-
-; Temporarily disable modref checks
-; 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
-
-  load i32, i32* %a
-  load i32, i32* %b
-  %c = call i32* @return_arg_callee(i32* %a, i32* %b)
-  load i32, i32* %c
-
-  ret void
-}

llvm/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 -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
-
-  load i32, i32* %a
-  load i32, i32* %b
-  store i32* %a, i32** %p
-  store i32** %p, i32*** %pp
-  %c = call i32* @return_deref_arg_multilevel_callee(i32*** %pp)
-  load i32, i32* %c
-
-  %lpp = load i32**, i32*** %pp
-  %lpp_deref = load i32*, i32** %lpp
-  %lp = load i32*, i32** %p
-  load i32, i32* %lpp_deref
-  load i32, i32* %lp
-
-  ret void
-}

llvm/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 -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
-
-  load i32, i32* %a
-  load i32, i32* %b
-  store i32* %a, i32** %p
-  %c = call i32* @return_deref_arg_callee(i32** %p)
-
-  %lp = load i32*, i32** %p
-  load i32, i32* %c
-  load i32, i32* %lp
-
-  ret void
-}

llvm/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 -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-DAG: NoAlias: i32* %a, i32** %x
-; CHECK-DAG: NoAlias: i32* %b, i32** %x
-; CHECK-DAG: NoAlias: i32* %a, i32* %b
-; CHECK-DAG: NoAlias: i32* %c, i32** %x
-; CHECK-DAG: NoAlias: i32* %a, i32* %c
-; CHECK-DAG: NoAlias: i32* %b, i32* %c
-; CHECK-DAG: NoAlias: i32* %a, i32* %d
-; CHECK-DAG: MayAlias: i32* %b, i32* %d
-; CHECK-DAG: 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()
-  load i32, i32* %a
-  load i32, i32* %b
-  load i32, i32* %c
-  %d = load i32*, i32** %x
-  load i32, i32* %d
-
-  ret void
-}

llvm/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 -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-DAG: NoAlias: i32* %a, i32*** %b
-; CHECK-DAG: NoAlias: i32*** %b, i32** %p
-; CHECK-DAG: NoAlias: i32* %a, i32** %lb
-; CHECK-DAG: NoAlias: i32** %lb, i32*** %pp
-; CHECK-DAG: NoAlias: i32*** %b, i32** %lb
-; CHECK-DAG: MayAlias: i32* %a, i32* %lb_deref
-; CHECK-DAG: NoAlias: i32* %lb_deref, i32** %lpp
-; CHECK-DAG: MayAlias: i32* %lb_deref, i32* %lpp_deref
-; CHECK-DAG: NoAlias: i32** %lpp, i32* %lpp_deref
-; CHECK-DAG: MayAlias: i32* %lb_deref, i32* %lp
-; CHECK-DAG: NoAlias: i32* %lp, i32** %lpp
-; CHECK-DAG: 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
-
-  load i32, i32* %a
-  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
-  load i32, i32* %lb_deref
-  load i32, i32* %lpp_deref
-  load i32, i32* %lp
-
-  ret void
-}

llvm/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 -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** %b, i32* %lb
-; CHECK: NoAlias: i32* %lp, i32** %p
-; CHECK: NoAlias: i32** %b, i32* %lp
-; 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
-
-  load i32, i32* %a
-  store i32* %a, i32** %p
-  %b = call i32** @return_ref_arg_callee(i32* %a)
-
-  %lb = load i32*, i32** %b
-  %lp = load i32*, i32** %p
-  load i32, i32* %lb
-  load i32, i32* %lp
-
-  ret void
-}

llvm/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 -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
-
-  load i32, i32* %x
-  load i32, i32* %a
-  load i32, i32* %b
-  %c = call i32* @return_unknown_callee(i32* %a, i32* %b)
-  load i32, i32* %c
-
-  ret void
-}
-
-@g2 = external global i32*
-define i32** @return_unknown_callee2() {
-  ret i32** @g2
-}
-; CHECK-LABEL: Function: test_return_unknown2
-; CHECK: MayAlias: i32** %a, i32* %x
-; CHECK: MayAlias: i32* %b, i32* %x
-; CHECK: MayAlias: i32** %a, i32* %b
-define void @test_return_unknown2(i32* %x) {
-  load i32, i32* %x
-  %a = call i32** @return_unknown_callee2()
-  %b = load i32*, i32** %a
-  load i32, i32* %b
-
-  ret void
-}

llvm/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 -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, i32* %lpp_deref
-; 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
-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
-
-  load i32, i32* %a
-  load i32, i32* %b
-  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
-  load i32, i32* %lpp_deref
-  load i32, i32* %lp
-
-  ret void
-}
-

llvm/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 -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** %p, i32* %x
-; 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
-
-  load i32, i32* %x
-  load i32, i32* %a
-  load i32, i32* %b
-  store i32* %a, i32** %p
-  call void @store_arg_unknown_callee(i32** %p)
-
-  %lp = load i32*, i32** %p
-  load i32, i32* %lp
-
-  ret void
-}

llvm/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 -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
-
-  load i32, i32* %a
-  load i32, i32* %b
-  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
-  load i32, i32* %lp
-  load i32, i32* %lq
-
-  ret void
-}

llvm/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 -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)
-  load i8, i8* %p
-  load i8, i8* %q
-  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)
-  load i8, i8* %p
-  load i8, i8* %q
-  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)
-  load i8, i8* %p
-  load i8, i8* %q
-  ret void
-}

llvm/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 -aa-pipeline=cfl-steens-aa -passes=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
-  load %T, %T* %A
-  load %T, %T* %B
-  load %T, %T* %MS
-  load %T, %T* %AP
-
-  ret void
-}

llvm/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 -aa-pipeline=cfl-steens-aa -passes=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
-  load %T, %T* %A
-  load %T, %T* %B
-  load %T, %T* %AP
-  load %T, %T* %BP
-
-  ret void
-}

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

-; RUN: opt < %s -aa-pipeline=cfl-steens-aa -passes=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 MayAlias 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
-  %3 = fneg double %1
-  %mul26 = fmul double %3, %2
-  load double, double* %A
-  load double, double* %Index
-  ret void
-}

llvm/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 -aa-pipeline=cfl-steens-aa -passes=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
-  load i8, i8* %Arg
-  load i8, i8* %Escapes
-  call void @set_thepointer(i8* %Escapes)
-  %Retrieved = call i8* @get_thepointer()
-  load i8, i8* %Retrieved
-  ret void
-}
-
-declare void @set_thepointer(i8* %P)
-declare i8* @get_thepointer()

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

-; RUN: opt < %s -aa-pipeline=cfl-steens-aa -passes=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/test/Analysis/CFLAliasAnalysis/Steensgaard/pr27213.ll

-; 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
-  load i32, i32* %B
-  %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/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 -aa-pipeline=cfl-steens-aa -passes=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/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 -aa-pipeline=cfl-steens-aa -passes=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: 45 Total Alias Queries Performed
-  ; CHECK: 9 no alias responses (20.0%)
-  %a = alloca i32, align 4
-  load i32, i32* %a
-  load i32, i32* %arg27
-  load i32, i32* %arg28
-  load i32, i32* %arg29
-  load i32, i32* %arg30
-  load i32, i32* %arg31
-  load i32, i32* %arg32
-  load i32, i32* %arg33
-  load i32, i32* %arg34
-  load i32, i32* %arg35
-
-  ret void
-}

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

-; 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: test1
-; CHECK-DAG: MayAlias: i32* %X, i32* %tmp
-; CHECK-DAG: MayAlias: i8** %ap, i32* %tmp
-; CHECK-DAG: NoAlias: i8** %ap, i8** %aq
-; CHECK-DAG: MayAlias: i8** %aq, i32* %tmp
-
-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)
-
-  load i32, i32* %X
-  load i8*, i8** %ap
-  load i8*, i8** %aq
-  load i32, i32* %tmp
-  ret i32* %tmp
-}
-
-declare void @llvm.va_start(i8*)
-declare void @llvm.va_copy(i8*, i8*)
-declare void @llvm.va_end(i8*)
-