Index: include/llvm/Analysis/CFLAndersAliasAnalysis.h =================================================================== --- /dev/null +++ include/llvm/Analysis/CFLAndersAliasAnalysis.h @@ -0,0 +1,74 @@ +//=- CFLAndersAliasAnalysis.h - Unification-based Alias Analysis ---*- C++-*-=// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +/// \file +/// This is the interface for LLVM's inclusion-based alias analysis +/// implemented with CFL graph reachability. +/// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_CFLANDERSALIASANALYSIS_H +#define LLVM_ANALYSIS_CFLANDERSALIASANALYSIS_H + +#include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/IR/Function.h" +#include "llvm/Pass.h" + +namespace llvm { + +class CFLAndersAAResult : public AAResultBase { + friend AAResultBase; + +public: + explicit CFLAndersAAResult(); + + AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB) { + // Dummy implementation + return AAResultBase::alias(LocA, LocB); + } +}; + +/// Analysis pass providing a never-invalidated alias analysis result. +/// +/// FIXME: We really should refactor CFL to use the analysis more heavily, and +/// in particular to leverage invalidation to trigger re-computation. +class CFLAndersAA : public AnalysisInfoMixin { + friend AnalysisInfoMixin; + static char PassID; + +public: + typedef CFLAndersAAResult Result; + + CFLAndersAAResult run(Function &F, AnalysisManager &AM); +}; + +/// Legacy wrapper pass to provide the CFLAndersAAResult object. +class CFLAndersAAWrapperPass : public ImmutablePass { + std::unique_ptr Result; + +public: + static char ID; + + CFLAndersAAWrapperPass(); + + CFLAndersAAResult &getResult() { return *Result; } + const CFLAndersAAResult &getResult() const { return *Result; } + + void initializePass() override; + void getAnalysisUsage(AnalysisUsage &AU) const override; +}; + +//===--------------------------------------------------------------------===// +// +// createCFLAndersAAWrapperPass - This pass implements a set-based approach to +// alias analysis. +// +ImmutablePass *createCFLAndersAAWrapperPass(); +} + +#endif Index: include/llvm/Analysis/CFLSteensAliasAnalysis.h =================================================================== --- include/llvm/Analysis/CFLSteensAliasAnalysis.h +++ include/llvm/Analysis/CFLSteensAliasAnalysis.h @@ -1,4 +1,4 @@ -//===- CFLAliasAnalysis.h - CFL-Based Alias Analysis Interface ---*- C++ -*-==// +//=- CFLSteensAliasAnalysis.h - Unification-based Alias Analysis ---*- C++-*-=// // // The LLVM Compiler Infrastructure // @@ -7,12 +7,13 @@ // //===----------------------------------------------------------------------===// /// \file -/// This is the interface for LLVM's primary stateless and local alias analysis. +/// This is the interface for LLVM's unification-based alias analysis +/// implemented with CFL graph reachability. /// //===----------------------------------------------------------------------===// -#ifndef LLVM_ANALYSIS_CFLALIASANALYSIS_H -#define LLVM_ANALYSIS_CFLALIASANALYSIS_H +#ifndef LLVM_ANALYSIS_CFLSTEENSALIASANALYSIS_H +#define LLVM_ANALYSIS_CFLSTEENSALIASANALYSIS_H #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/None.h" @@ -28,14 +29,14 @@ class TargetLibraryInfo; -class CFLAAResult : public AAResultBase { - friend AAResultBase; +class CFLSteensAAResult : public AAResultBase { + friend AAResultBase; class FunctionInfo; public: - explicit CFLAAResult(const TargetLibraryInfo &); - CFLAAResult(CFLAAResult &&Arg); - ~CFLAAResult(); + explicit CFLSteensAAResult(const TargetLibraryInfo &); + CFLSteensAAResult(CFLSteensAAResult &&Arg); + ~CFLSteensAAResult(); /// Handle invalidation events from the new pass manager. /// @@ -59,10 +60,9 @@ // Comparisons between global variables and other constants should be // handled by BasicAA. - // TODO: ConstantExpr handling -- CFLAA may report NoAlias when comparing - // a GlobalValue and ConstantExpr, but every query needs to have at least - // one Value tied to a Function, and neither GlobalValues nor ConstantExprs - // are. + // 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(LocA.Ptr) && isa(LocB.Ptr)) return AAResultBase::alias(LocA, LocB); @@ -85,7 +85,7 @@ private: struct FunctionHandle final : public CallbackVH { - FunctionHandle(Function *Fn, CFLAAResult *Result) + FunctionHandle(Function *Fn, CFLSteensAAResult *Result) : CallbackVH(Fn), Result(Result) { assert(Fn != nullptr); assert(Result != nullptr); @@ -95,7 +95,7 @@ void allUsesReplacedWith(Value *) override { removeSelfFromCache(); } private: - CFLAAResult *Result; + CFLSteensAAResult *Result; void removeSelfFromCache() { assert(Result != nullptr); @@ -122,27 +122,27 @@ /// /// FIXME: We really should refactor CFL to use the analysis more heavily, and /// in particular to leverage invalidation to trigger re-computation of sets. -class CFLAA : public AnalysisInfoMixin { - friend AnalysisInfoMixin; +class CFLSteensAA : public AnalysisInfoMixin { + friend AnalysisInfoMixin; static char PassID; public: - typedef CFLAAResult Result; + typedef CFLSteensAAResult Result; - CFLAAResult run(Function &F, AnalysisManager &AM); + CFLSteensAAResult run(Function &F, AnalysisManager &AM); }; -/// Legacy wrapper pass to provide the CFLAAResult object. -class CFLAAWrapperPass : public ImmutablePass { - std::unique_ptr Result; +/// Legacy wrapper pass to provide the CFLSteensAAResult object. +class CFLSteensAAWrapperPass : public ImmutablePass { + std::unique_ptr Result; public: static char ID; - CFLAAWrapperPass(); + CFLSteensAAWrapperPass(); - CFLAAResult &getResult() { return *Result; } - const CFLAAResult &getResult() const { return *Result; } + CFLSteensAAResult &getResult() { return *Result; } + const CFLSteensAAResult &getResult() const { return *Result; } void initializePass() override; void getAnalysisUsage(AnalysisUsage &AU) const override; @@ -150,10 +150,10 @@ //===--------------------------------------------------------------------===// // -// createCFLAAWrapperPass - This pass implements a set-based approach to +// createCFLSteensAAWrapperPass - This pass implements a set-based approach to // alias analysis. // -ImmutablePass *createCFLAAWrapperPass(); +ImmutablePass *createCFLSteensAAWrapperPass(); } #endif Index: include/llvm/InitializePasses.h =================================================================== --- include/llvm/InitializePasses.h +++ include/llvm/InitializePasses.h @@ -82,7 +82,8 @@ void initializeCFGPrinterPass(PassRegistry&); void initializeCFGSimplifyPassPass(PassRegistry&); void initializeCFGViewerPass(PassRegistry&); -void initializeCFLAAWrapperPassPass(PassRegistry&); +void initializeCFLAndersAAWrapperPassPass(PassRegistry&); +void initializeCFLSteensAAWrapperPassPass(PassRegistry&); void initializeCallGraphDOTPrinterPass(PassRegistry&); void initializeCallGraphPrinterLegacyPassPass(PassRegistry&); void initializeCallGraphViewerPass(PassRegistry&); Index: include/llvm/LinkAllPasses.h =================================================================== --- include/llvm/LinkAllPasses.h +++ include/llvm/LinkAllPasses.h @@ -19,7 +19,8 @@ #include "llvm/Analysis/AliasSetTracker.h" #include "llvm/Analysis/AliasAnalysisEvaluator.h" #include "llvm/Analysis/BasicAliasAnalysis.h" -#include "llvm/Analysis/CFLAliasAnalysis.h" +#include "llvm/Analysis/CFLAndersAliasAnalysis.h" +#include "llvm/Analysis/CFLSteensAliasAnalysis.h" #include "llvm/Analysis/CallPrinter.h" #include "llvm/Analysis/DomPrinter.h" #include "llvm/Analysis/GlobalsModRef.h" @@ -73,7 +74,8 @@ (void) llvm::createCallGraphDOTPrinterPass(); (void) llvm::createCallGraphViewerPass(); (void) llvm::createCFGSimplificationPass(); - (void) llvm::createCFLAAWrapperPass(); + (void) llvm::createCFLAndersAAWrapperPass(); + (void) llvm::createCFLSteensAAWrapperPass(); (void) llvm::createStructurizeCFGPass(); (void) llvm::createConstantMergePass(); (void) llvm::createConstantPropagationPass(); Index: lib/Analysis/AliasAnalysis.cpp =================================================================== --- lib/Analysis/AliasAnalysis.cpp +++ lib/Analysis/AliasAnalysis.cpp @@ -27,7 +27,8 @@ #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/BasicAliasAnalysis.h" #include "llvm/Analysis/CFG.h" -#include "llvm/Analysis/CFLAliasAnalysis.h" +#include "llvm/Analysis/CFLAndersAliasAnalysis.h" +#include "llvm/Analysis/CFLSteensAliasAnalysis.h" #include "llvm/Analysis/CaptureTracking.h" #include "llvm/Analysis/GlobalsModRef.h" #include "llvm/Analysis/ObjCARCAliasAnalysis.h" @@ -548,7 +549,8 @@ INITIALIZE_PASS_BEGIN(AAResultsWrapperPass, "aa", "Function Alias Analysis Results", false, true) INITIALIZE_PASS_DEPENDENCY(BasicAAWrapperPass) -INITIALIZE_PASS_DEPENDENCY(CFLAAWrapperPass) +INITIALIZE_PASS_DEPENDENCY(CFLAndersAAWrapperPass) +INITIALIZE_PASS_DEPENDENCY(CFLSteensAAWrapperPass) INITIALIZE_PASS_DEPENDENCY(ExternalAAWrapperPass) INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass) INITIALIZE_PASS_DEPENDENCY(ObjCARCAAWrapperPass) @@ -599,7 +601,9 @@ AAR->addAAResult(WrapperPass->getResult()); if (auto *WrapperPass = getAnalysisIfAvailable()) AAR->addAAResult(WrapperPass->getResult()); - if (auto *WrapperPass = getAnalysisIfAvailable()) + if (auto *WrapperPass = getAnalysisIfAvailable()) + AAR->addAAResult(WrapperPass->getResult()); + if (auto *WrapperPass = getAnalysisIfAvailable()) AAR->addAAResult(WrapperPass->getResult()); // If available, run an external AA providing callback over the results as @@ -626,7 +630,8 @@ AU.addUsedIfAvailable(); AU.addUsedIfAvailable(); AU.addUsedIfAvailable(); - AU.addUsedIfAvailable(); + AU.addUsedIfAvailable(); + AU.addUsedIfAvailable(); } AAResults llvm::createLegacyPMAAResults(Pass &P, Function &F, @@ -648,7 +653,9 @@ AAR.addAAResult(WrapperPass->getResult()); if (auto *WrapperPass = P.getAnalysisIfAvailable()) AAR.addAAResult(WrapperPass->getResult()); - if (auto *WrapperPass = P.getAnalysisIfAvailable()) + if (auto *WrapperPass = P.getAnalysisIfAvailable()) + AAR.addAAResult(WrapperPass->getResult()); + if (auto *WrapperPass = P.getAnalysisIfAvailable()) AAR.addAAResult(WrapperPass->getResult()); return AAR; @@ -691,5 +698,6 @@ AU.addUsedIfAvailable(); AU.addUsedIfAvailable(); AU.addUsedIfAvailable(); - AU.addUsedIfAvailable(); + AU.addUsedIfAvailable(); + AU.addUsedIfAvailable(); } Index: lib/Analysis/Analysis.cpp =================================================================== --- lib/Analysis/Analysis.cpp +++ lib/Analysis/Analysis.cpp @@ -34,7 +34,8 @@ initializeCFGPrinterPass(Registry); initializeCFGOnlyViewerPass(Registry); initializeCFGOnlyPrinterPass(Registry); - initializeCFLAAWrapperPassPass(Registry); + initializeCFLAndersAAWrapperPassPass(Registry); + initializeCFLSteensAAWrapperPassPass(Registry); initializeDependenceAnalysisWrapperPassPass(Registry); initializeDelinearizationPass(Registry); initializeDemandedBitsWrapperPassPass(Registry); Index: lib/Analysis/CFLAndersAliasAnalysis.cpp =================================================================== --- /dev/null +++ lib/Analysis/CFLAndersAliasAnalysis.cpp @@ -0,0 +1,58 @@ +//- CFLAndersAliasAnalysis.cpp - Unification-based Alias Analysis ---*- C++-*-// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file implements a CFL-based, summary-based alias analysis algorithm. It +// differs from CFLSteensAliasAnalysis in its inclusion-based nature while +// CFLSteensAliasAnalysis is unification-based. This pass has worse performance +// than CFLSteensAliasAnalysis (the worst case complexity of +// CFLAndersAliasAnalysis is cubic, while the worst case complexity of +// CFLSteensAliasAnalysis is almost linear), but it is able to yield more +// precise analysis result. The precision of this analysis is roughly the same +// as that of an one level context-sensitive Andersen's algorithm. +// +//===----------------------------------------------------------------------===// + +// N.B. AliasAnalysis as a whole is phrased as a FunctionPass at the moment, and +// CFLAndersAA is interprocedural. This is *technically* A Bad Thing, because +// FunctionPasses are only allowed to inspect the Function that they're being +// run on. Realistically, this likely isn't a problem until we allow +// FunctionPasses to run concurrently. + +#include "llvm/Analysis/CFLAndersAliasAnalysis.h" +#include "llvm/Pass.h" + +using namespace llvm; + +#define DEBUG_TYPE "cfl-anders-aa" + +CFLAndersAAResult::CFLAndersAAResult() = default; + +char CFLAndersAA::PassID; + +CFLAndersAAResult CFLAndersAA::run(Function &F, AnalysisManager &AM) { + return CFLAndersAAResult(); +} + +char CFLAndersAAWrapperPass::ID = 0; +INITIALIZE_PASS(CFLAndersAAWrapperPass, "cfl-anders-aa", + "Inclusion-Based CFL Alias Analysis", false, true) + +ImmutablePass *llvm::createCFLAndersAAWrapperPass() { + return new CFLAndersAAWrapperPass(); +} + +CFLAndersAAWrapperPass::CFLAndersAAWrapperPass() : ImmutablePass(ID) { + initializeCFLAndersAAWrapperPassPass(*PassRegistry::getPassRegistry()); +} + +void CFLAndersAAWrapperPass::initializePass() {} + +void CFLAndersAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { + AU.setPreservesAll(); +} Index: lib/Analysis/CFLSteensAliasAnalysis.cpp =================================================================== --- lib/Analysis/CFLSteensAliasAnalysis.cpp +++ lib/Analysis/CFLSteensAliasAnalysis.cpp @@ -1,4 +1,4 @@ -//===- CFLAliasAnalysis.cpp - CFL-Based Alias Analysis Implementation ------==// +//- CFLSteensAliasAnalysis.cpp - Unification-based Alias Analysis ---*- C++-*-// // // The LLVM Compiler Infrastructure // @@ -7,14 +7,16 @@ // //===----------------------------------------------------------------------===// // -// This file implements a CFL-based context-insensitive alias analysis -// algorithm. It does not depend on types. The algorithm is a mixture of the one -// described in "Demand-driven alias analysis for C" by Xin Zheng and Radu -// Rugina, and "Fast algorithms for Dyck-CFL-reachability with applications to -// Alias Analysis" by Zhang Q, Lyu M R, Yuan H, and Su Z. -- to summarize the -// papers, we build a graph of the uses of a variable, where each node is a -// memory location, and each edge is an action that happened on that memory -// location. The "actions" can be one of Dereference, Reference, or Assign. +// This file implements a CFL-base, summary-based alias analysis algorithm. It +// does not depend on types. The algorithm is a mixture of the one described in +// "Demand-driven alias analysis for C" by Xin Zheng and Radu Rugina, and "Fast +// algorithms for Dyck-CFL-reachability with applications to Alias Analysis" by +// Zhang Q, Lyu M R, Yuan H, and Su Z. -- to summarize the papers, we build a +// graph of the uses of a variable, where each node is a memory location, and +// each edge is an action that happened on that memory location. The "actions" +// can be one of Dereference, Reference, or Assign. The precision of this +// analysis is roughly the same as that of an one level context-sensitive +// Steensgaard's algorithm. // // Two variables are considered as aliasing iff you can reach one value's node // from the other value's node and the language formed by concatenating all of @@ -28,12 +30,12 @@ //===----------------------------------------------------------------------===// // N.B. AliasAnalysis as a whole is phrased as a FunctionPass at the moment, and -// CFLAA is interprocedural. This is *technically* A Bad Thing, because +// CFLSteensAA is interprocedural. This is *technically* A Bad Thing, because // FunctionPasses are only allowed to inspect the Function that they're being // run on. Realistically, this likely isn't a problem until we allow // FunctionPasses to run concurrently. -#include "llvm/Analysis/CFLAliasAnalysis.h" +#include "llvm/Analysis/CFLSteensAliasAnalysis.h" #include "StratifiedSets.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/None.h" @@ -56,13 +58,13 @@ using namespace llvm; -#define DEBUG_TYPE "cfl-aa" +#define DEBUG_TYPE "cfl-steens-aa" -CFLAAResult::CFLAAResult(const TargetLibraryInfo &TLI) +CFLSteensAAResult::CFLSteensAAResult(const TargetLibraryInfo &TLI) : AAResultBase(), TLI(TLI) {} -CFLAAResult::CFLAAResult(CFLAAResult &&Arg) +CFLSteensAAResult::CFLSteensAAResult(CFLSteensAAResult &&Arg) : AAResultBase(std::move(Arg)), TLI(Arg.TLI) {} -CFLAAResult::~CFLAAResult() {} +CFLSteensAAResult::~CFLSteensAAResult() {} /// We use InterfaceValue to describe parameters/return value, as well as /// potential memory locations that are pointed to by parameters/return value, @@ -98,7 +100,7 @@ }; /// Information we have about a function and would like to keep around. -class CFLAAResult::FunctionInfo { +class CFLSteensAAResult::FunctionInfo { StratifiedSets Sets; // RetParamRelations is a collection of ExternalRelations. @@ -300,7 +302,7 @@ /// Gets the edges our graph should have, based on an Instruction* class GetEdgesVisitor : public InstVisitor { - CFLAAResult &AA; + CFLSteensAAResult &AA; const TargetLibraryInfo &TLI; CFLGraph &Graph; @@ -343,7 +345,7 @@ } public: - GetEdgesVisitor(CFLAAResult &AA, const TargetLibraryInfo &TLI, + GetEdgesVisitor(CFLSteensAAResult &AA, const TargetLibraryInfo &TLI, CFLGraph &Graph, SmallVectorImpl &ReturnValues, SmallPtrSetImpl &Externals, SmallPtrSetImpl &Escapes, @@ -603,7 +605,7 @@ class CFLGraphBuilder { // Input of the builder - CFLAAResult &Analysis; + CFLSteensAAResult &Analysis; const TargetLibraryInfo &TLI; // Output of the builder @@ -662,7 +664,7 @@ } public: - CFLGraphBuilder(CFLAAResult &Analysis, const TargetLibraryInfo &TLI, + CFLGraphBuilder(CFLSteensAAResult &Analysis, const TargetLibraryInfo &TLI, Function &Fn) : Analysis(Analysis), TLI(TLI) { buildGraphFrom(Fn); @@ -800,9 +802,9 @@ return false; } -CFLAAResult::FunctionInfo::FunctionInfo(Function &Fn, - const SmallVectorImpl &RetVals, - StratifiedSets S) +CFLSteensAAResult::FunctionInfo::FunctionInfo( + Function &Fn, const SmallVectorImpl &RetVals, + StratifiedSets S) : Sets(std::move(S)) { // Historically, an arbitrary upper-bound of 50 args was selected. We may want // to remove this if it doesn't really matter in practice. @@ -868,7 +870,7 @@ } // Builds the graph + StratifiedSets for a function. -CFLAAResult::FunctionInfo CFLAAResult::buildSetsFrom(Function *Fn) { +CFLSteensAAResult::FunctionInfo CFLSteensAAResult::buildSetsFrom(Function *Fn) { CFLGraphBuilder GraphBuilder(*this, TLI, *Fn); StratifiedSetsBuilder SetBuilder; @@ -951,7 +953,7 @@ return FunctionInfo(*Fn, GraphBuilder.getReturnValues(), SetBuilder.build()); } -void CFLAAResult::scan(Function *Fn) { +void CFLSteensAAResult::scan(Function *Fn) { auto InsertPair = Cache.insert(std::make_pair(Fn, Optional())); (void)InsertPair; assert(InsertPair.second && @@ -966,12 +968,12 @@ Handles.push_front(FunctionHandle(Fn, this)); } -void CFLAAResult::evict(Function *Fn) { Cache.erase(Fn); } +void CFLSteensAAResult::evict(Function *Fn) { Cache.erase(Fn); } /// Ensures that the given function is available in the cache, and returns the /// entry. -const Optional & -CFLAAResult::ensureCached(Function *Fn) { +const Optional & +CFLSteensAAResult::ensureCached(Function *Fn) { auto Iter = Cache.find(Fn); if (Iter == Cache.end()) { scan(Fn); @@ -982,8 +984,8 @@ return Iter->second; } -AliasResult CFLAAResult::query(const MemoryLocation &LocA, - const MemoryLocation &LocB) { +AliasResult CFLSteensAAResult::query(const MemoryLocation &LocA, + const MemoryLocation &LocB) { auto *ValA = const_cast(LocA.Ptr); auto *ValB = const_cast(LocB.Ptr); @@ -996,7 +998,8 @@ if (!MaybeFnA.hasValue() && !MaybeFnB.hasValue()) { // The only times this is known to happen are when globals + InlineAsm are // involved - DEBUG(dbgs() << "CFLAA: could not extract parent function information.\n"); + DEBUG(dbgs() + << "CFLSteensAA: could not extract parent function information.\n"); return MayAlias; } @@ -1027,8 +1030,8 @@ auto AttrsB = Sets.getLink(SetB.Index).Attrs; // If both values are local (meaning the corresponding set has attribute - // AttrNone or AttrEscaped), then we know that CFLAA fully models them: they - // may-alias each other if and only if they are in the same set + // AttrNone or AttrEscaped), then we know that CFLSteensAA fully models them: + // they may-alias each other if and only if they are in the same set. // If at least one value is non-local (meaning it either is global/argument or // it comes from unknown sources like integer cast), the situation becomes a // bit more interesting. We follow three general rules described below: @@ -1047,8 +1050,8 @@ return NoAlias; } -ModRefInfo CFLAAResult::getArgModRefInfo(ImmutableCallSite CS, - unsigned ArgIdx) { +ModRefInfo CFLSteensAAResult::getArgModRefInfo(ImmutableCallSite CS, + unsigned ArgIdx) { if (auto CalledFunc = CS.getCalledFunction()) { auto &MaybeInfo = ensureCached(const_cast(CalledFunc)); if (!MaybeInfo.hasValue()) @@ -1075,7 +1078,8 @@ return MRI_ModRef; } -FunctionModRefBehavior CFLAAResult::getModRefBehavior(ImmutableCallSite CS) { +FunctionModRefBehavior +CFLSteensAAResult::getModRefBehavior(ImmutableCallSite CS) { // If we know the callee, try analyzing it if (auto CalledFunc = CS.getCalledFunction()) return getModRefBehavior(CalledFunc); @@ -1084,7 +1088,7 @@ return FMRB_UnknownModRefBehavior; } -FunctionModRefBehavior CFLAAResult::getModRefBehavior(const Function *F) { +FunctionModRefBehavior CFLSteensAAResult::getModRefBehavior(const Function *F) { assert(F != nullptr); // TODO: Remove the const_cast @@ -1118,28 +1122,30 @@ : FMRB_UnknownModRefBehavior; } -char CFLAA::PassID; +char CFLSteensAA::PassID; -CFLAAResult CFLAA::run(Function &F, AnalysisManager &AM) { - return CFLAAResult(AM.getResult(F)); +CFLSteensAAResult CFLSteensAA::run(Function &F, AnalysisManager &AM) { + return CFLSteensAAResult(AM.getResult(F)); } -char CFLAAWrapperPass::ID = 0; -INITIALIZE_PASS(CFLAAWrapperPass, "cfl-aa", "CFL-Based Alias Analysis", false, - true) +char CFLSteensAAWrapperPass::ID = 0; +INITIALIZE_PASS(CFLSteensAAWrapperPass, "cfl-steens-aa", + "Unification-Based CFL Alias Analysis", false, true) -ImmutablePass *llvm::createCFLAAWrapperPass() { return new CFLAAWrapperPass(); } +ImmutablePass *llvm::createCFLSteensAAWrapperPass() { + return new CFLSteensAAWrapperPass(); +} -CFLAAWrapperPass::CFLAAWrapperPass() : ImmutablePass(ID) { - initializeCFLAAWrapperPassPass(*PassRegistry::getPassRegistry()); +CFLSteensAAWrapperPass::CFLSteensAAWrapperPass() : ImmutablePass(ID) { + initializeCFLSteensAAWrapperPassPass(*PassRegistry::getPassRegistry()); } -void CFLAAWrapperPass::initializePass() { +void CFLSteensAAWrapperPass::initializePass() { auto &TLIWP = getAnalysis(); - Result.reset(new CFLAAResult(TLIWP.getTLI())); + Result.reset(new CFLSteensAAResult(TLIWP.getTLI())); } -void CFLAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { +void CFLSteensAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesAll(); AU.addRequired(); } Index: lib/Analysis/CMakeLists.txt =================================================================== --- lib/Analysis/CMakeLists.txt +++ lib/Analysis/CMakeLists.txt @@ -10,7 +10,8 @@ BranchProbabilityInfo.cpp CFG.cpp CFGPrinter.cpp - CFLAliasAnalysis.cpp + CFLAndersAliasAnalysis.cpp + CFLSteensAliasAnalysis.cpp CGSCCPassManager.cpp CallGraph.cpp CallGraphSCCPass.cpp Index: lib/CodeGen/TargetPassConfig.cpp =================================================================== --- lib/CodeGen/TargetPassConfig.cpp +++ lib/CodeGen/TargetPassConfig.cpp @@ -15,7 +15,8 @@ #include "llvm/CodeGen/TargetPassConfig.h" #include "llvm/Analysis/BasicAliasAnalysis.h" -#include "llvm/Analysis/CFLAliasAnalysis.h" +#include "llvm/Analysis/CFLAndersAliasAnalysis.h" +#include "llvm/Analysis/CFLSteensAliasAnalysis.h" #include "llvm/Analysis/CallGraphSCCPass.h" #include "llvm/Analysis/Passes.h" #include "llvm/Analysis/ScopedNoAliasAA.h" @@ -110,9 +111,19 @@ static cl::opt EarlyLiveIntervals("early-live-intervals", cl::Hidden, cl::desc("Run live interval analysis earlier in the pipeline")); -static cl::opt UseCFLAA("use-cfl-aa-in-codegen", - cl::init(false), cl::Hidden, - cl::desc("Enable the new, experimental CFL alias analysis in CodeGen")); +// Experimental option to use CFL-AA in codegen +enum class CFLAAType { None, Steensgaard, Andersen, Both }; +static cl::opt UseCFLAA( + "use-cfl-aa-in-codegen", cl::init(CFLAAType::None), cl::Hidden, + cl::desc("Enable the new, experimental CFL alias analysis in CodeGen"), + cl::values(clEnumValN(CFLAAType::None, "none", "Disable CFL-AA"), + clEnumValN(CFLAAType::Steensgaard, "steens", + "Enable unification-based CFL-AA"), + clEnumValN(CFLAAType::Andersen, "anders", + "Enable inclusion-based CFL-AA"), + clEnumValN(CFLAAType::Both, "both", + "Enable both variants of CFL-AA"), + clEnumValEnd)); cl::opt UseIPRA("enable-ipra", cl::init(false), cl::Hidden, cl::desc("Enable interprocedural register allocation " @@ -414,12 +425,25 @@ /// Add common target configurable passes that perform LLVM IR to IR transforms /// following machine independent optimization. void TargetPassConfig::addIRPasses() { + switch (UseCFLAA) { + case CFLAAType::Steensgaard: + addPass(createCFLSteensAAWrapperPass()); + break; + case CFLAAType::Andersen: + addPass(createCFLAndersAAWrapperPass()); + break; + case CFLAAType::Both: + addPass(createCFLAndersAAWrapperPass()); + addPass(createCFLSteensAAWrapperPass()); + break; + default: + break; + } + // Basic AliasAnalysis support. // Add TypeBasedAliasAnalysis before BasicAliasAnalysis so that // BasicAliasAnalysis wins if they disagree. This is intended to help // support "obvious" type-punning idioms. - if (UseCFLAA) - addPass(createCFLAAWrapperPass()); addPass(createTypeBasedAAWrapperPass()); addPass(createScopedNoAliasAAWrapperPass()); addPass(createBasicAAWrapperPass()); Index: lib/Passes/PassBuilder.cpp =================================================================== --- lib/Passes/PassBuilder.cpp +++ lib/Passes/PassBuilder.cpp @@ -24,7 +24,8 @@ #include "llvm/Analysis/BlockFrequencyInfo.h" #include "llvm/Analysis/BlockFrequencyInfoImpl.h" #include "llvm/Analysis/BranchProbabilityInfo.h" -#include "llvm/Analysis/CFLAliasAnalysis.h" +#include "llvm/Analysis/CFLAndersAliasAnalysis.h" +#include "llvm/Analysis/CFLSteensAliasAnalysis.h" #include "llvm/Analysis/CGSCCPassManager.h" #include "llvm/Analysis/CallGraph.h" #include "llvm/Analysis/DemandedBits.h" @@ -690,7 +691,8 @@ DebugLogging) || !PipelineText.empty()) return false; - MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM), DebugLogging)); + MPM.addPass( + createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM), DebugLogging)); return true; } Index: lib/Passes/PassRegistry.def =================================================================== --- lib/Passes/PassRegistry.def +++ lib/Passes/PassRegistry.def @@ -27,7 +27,7 @@ MODULE_ANALYSIS("verify", VerifierAnalysis()) #ifndef MODULE_ALIAS_ANALYSIS -#define MODULE_ALIAS_ANALYSIS(NAME, CREATE_PASS) \ +#define MODULE_ALIAS_ANALYSIS(NAME, CREATE_PASS) \ MODULE_ANALYSIS(NAME, CREATE_PASS) #endif MODULE_ALIAS_ANALYSIS("globals-aa", GlobalsAA()) @@ -110,7 +110,8 @@ FUNCTION_ANALYSIS(NAME, CREATE_PASS) #endif FUNCTION_ALIAS_ANALYSIS("basic-aa", BasicAA()) -FUNCTION_ALIAS_ANALYSIS("cfl-aa", CFLAA()) +FUNCTION_ALIAS_ANALYSIS("cfl-anders-aa", CFLAndersAA()) +FUNCTION_ALIAS_ANALYSIS("cfl-steens-aa", CFLSteensAA()) FUNCTION_ALIAS_ANALYSIS("scev-aa", SCEVAA()) FUNCTION_ALIAS_ANALYSIS("scoped-noalias-aa", ScopedNoAliasAA()) FUNCTION_ALIAS_ANALYSIS("type-based-aa", TypeBasedAA()) Index: lib/Transforms/IPO/PassManagerBuilder.cpp =================================================================== --- lib/Transforms/IPO/PassManagerBuilder.cpp +++ lib/Transforms/IPO/PassManagerBuilder.cpp @@ -16,7 +16,8 @@ #include "llvm-c/Transforms/PassManagerBuilder.h" #include "llvm/ADT/SmallVector.h" #include "llvm/Analysis/BasicAliasAnalysis.h" -#include "llvm/Analysis/CFLAliasAnalysis.h" +#include "llvm/Analysis/CFLAndersAliasAnalysis.h" +#include "llvm/Analysis/CFLSteensAliasAnalysis.h" #include "llvm/Analysis/GlobalsModRef.h" #include "llvm/Analysis/Passes.h" #include "llvm/Analysis/ScopedNoAliasAA.h" @@ -79,9 +80,19 @@ cl::desc("Run the SLP vectorizer (and BB vectorizer) after the Loop " "vectorizer instead of before")); -static cl::opt UseCFLAA("use-cfl-aa", - cl::init(false), cl::Hidden, - cl::desc("Enable the new, experimental CFL alias analysis")); +// Experimental option to use CFL-AA +enum class CFLAAType { None, Steensgaard, Andersen, Both }; +static cl::opt + UseCFLAA("use-cfl-aa", cl::init(CFLAAType::None), cl::Hidden, + cl::desc("Enable the new, experimental CFL alias analysis"), + cl::values(clEnumValN(CFLAAType::None, "none", "Disable CFL-AA"), + clEnumValN(CFLAAType::Steensgaard, "steens", + "Enable unification-based CFL-AA"), + clEnumValN(CFLAAType::Andersen, "anders", + "Enable inclusion-based CFL-AA"), + clEnumValN(CFLAAType::Both, "both", + "Enable both variants of CFL-aa"), + clEnumValEnd)); static cl::opt EnableMLSM("mlsm", cl::init(true), cl::Hidden, @@ -169,11 +180,24 @@ void PassManagerBuilder::addInitialAliasAnalysisPasses( legacy::PassManagerBase &PM) const { + switch (UseCFLAA) { + case CFLAAType::Steensgaard: + PM.add(createCFLSteensAAWrapperPass()); + break; + case CFLAAType::Andersen: + PM.add(createCFLAndersAAWrapperPass()); + break; + case CFLAAType::Both: + PM.add(createCFLSteensAAWrapperPass()); + PM.add(createCFLAndersAAWrapperPass()); + break; + default: + break; + } + // Add TypeBasedAliasAnalysis before BasicAliasAnalysis so that // BasicAliasAnalysis wins if they disagree. This is intended to help // support "obvious" type-punning idioms. - if (UseCFLAA) - PM.add(createCFLAAWrapperPass()); PM.add(createTypeBasedAAWrapperPass()); PM.add(createScopedNoAliasAAWrapperPass()); } Index: test/Analysis/CFLAliasAnalysis/Steensgaard/arguments-globals.ll =================================================================== --- test/Analysis/CFLAliasAnalysis/Steensgaard/arguments-globals.ll +++ test/Analysis/CFLAliasAnalysis/Steensgaard/arguments-globals.ll @@ -3,7 +3,7 @@ ; (Everything should alias everything, because args can alias globals, so the ; aliasing sets should of args+alloca+global should be combined) -; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -disable-basicaa -cfl-steens-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s ; CHECK: Function: test Index: test/Analysis/CFLAliasAnalysis/Steensgaard/arguments.ll =================================================================== --- test/Analysis/CFLAliasAnalysis/Steensgaard/arguments.ll +++ test/Analysis/CFLAliasAnalysis/Steensgaard/arguments.ll @@ -1,7 +1,7 @@ ; This testcase ensures that CFL AA gives conservative answers on variables ; that involve arguments. -; RUN: opt < %s -cfl-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -cfl-steens-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s ; CHECK: Function: test Index: test/Analysis/CFLAliasAnalysis/Steensgaard/asm-global-bugfix.ll =================================================================== --- test/Analysis/CFLAliasAnalysis/Steensgaard/asm-global-bugfix.ll +++ test/Analysis/CFLAliasAnalysis/Steensgaard/asm-global-bugfix.ll @@ -2,7 +2,7 @@ ; whether two values that didn't belong to a function (i.e. two globals, etc) ; aliased. -; RUN: opt < %s -cfl-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -cfl-steens-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s @G = private unnamed_addr constant [1 x i8] c"\00", align 1 Index: test/Analysis/CFLAliasAnalysis/Steensgaard/attr-escape.ll =================================================================== --- test/Analysis/CFLAliasAnalysis/Steensgaard/attr-escape.ll +++ test/Analysis/CFLAliasAnalysis/Steensgaard/attr-escape.ll @@ -1,7 +1,7 @@ ; This testcase ensures that CFL AA handles escaped values no more conservative than it should -; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s -; RUN: opt < %s -aa-pipeline=cfl-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -disable-basicaa -cfl-steens-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s ; CHECK-LABEL: Function: test_local ; CHECK: NoAlias: i32* %a, i32* %b Index: test/Analysis/CFLAliasAnalysis/Steensgaard/basic-interproc.ll =================================================================== --- test/Analysis/CFLAliasAnalysis/Steensgaard/basic-interproc.ll +++ test/Analysis/CFLAliasAnalysis/Steensgaard/basic-interproc.ll @@ -1,8 +1,8 @@ ; This testcase ensures that CFL AA won't be too conservative when trying to do ; interprocedural analysis on simple callee -; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s -; RUN: opt < %s -aa-pipeline=cfl-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -disable-basicaa -cfl-steens-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s ; CHECK-LABEL: Function: noop_callee ; CHECK: MayAlias: i32* %arg1, i32* %arg2 Index: test/Analysis/CFLAliasAnalysis/Steensgaard/branch-alias.ll =================================================================== --- test/Analysis/CFLAliasAnalysis/Steensgaard/branch-alias.ll +++ test/Analysis/CFLAliasAnalysis/Steensgaard/branch-alias.ll @@ -13,7 +13,7 @@ ; int* ShouldAliasA = *AliasA1; ; } -; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -disable-basicaa -cfl-steens-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s ; CHECK: Function: ptr_test define void @ptr_test() #0 { Index: test/Analysis/CFLAliasAnalysis/Steensgaard/const-expr-gep.ll =================================================================== --- test/Analysis/CFLAliasAnalysis/Steensgaard/const-expr-gep.ll +++ test/Analysis/CFLAliasAnalysis/Steensgaard/const-expr-gep.ll @@ -1,8 +1,8 @@ ; This testcase consists of alias relations which should be completely -; resolvable by cfl-aa, but require analysis of getelementptr constant exprs. +; resolvable by cfl-steens-aa, but require analysis of getelementptr constant exprs. ; Derived from BasicAA/2003-12-11-ConstExprGEP.ll -; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -disable-basicaa -cfl-steens-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s %T = type { i32, [10 x i8] } @@ -10,7 +10,7 @@ @G2 = external global %T ; TODO: Quite a few of these are MayAlias because we don't yet consider -; constant offsets in CFLAA. If we start doing so, then we'll need to +; constant offsets in CFLSteensAA. If we start doing so, then we'll need to ; change these test cases ; CHECK: Function: test @@ -36,7 +36,7 @@ ret void } -; Ensure that CFLAA properly identifies and handles escaping variables (i.e. +; Ensure that CFLSteensAA properly identifies and handles escaping variables (i.e. ; globals) in nested ConstantExprs ; CHECK: Function: checkNesting Index: test/Analysis/CFLAliasAnalysis/Steensgaard/constant-over-index.ll =================================================================== --- test/Analysis/CFLAliasAnalysis/Steensgaard/constant-over-index.ll +++ test/Analysis/CFLAliasAnalysis/Steensgaard/constant-over-index.ll @@ -1,4 +1,4 @@ -; RUN: opt < %s -cfl-aa -aa-eval -print-all-alias-modref-info 2>&1 | FileCheck %s +; RUN: opt < %s -cfl-steens-aa -aa-eval -print-all-alias-modref-info 2>&1 | FileCheck %s ; CFL AA currently returns PartialAlias, BasicAA returns MayAlias, both seem ; acceptable (although we might decide that we don't want PartialAlias, and if Index: test/Analysis/CFLAliasAnalysis/Steensgaard/empty.ll =================================================================== --- test/Analysis/CFLAliasAnalysis/Steensgaard/empty.ll +++ test/Analysis/CFLAliasAnalysis/Steensgaard/empty.ll @@ -1,4 +1,4 @@ -; RUN: opt < %s -cfl-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -cfl-steens-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64" Index: test/Analysis/CFLAliasAnalysis/Steensgaard/full-store-partial-alias.ll =================================================================== --- test/Analysis/CFLAliasAnalysis/Steensgaard/full-store-partial-alias.ll +++ test/Analysis/CFLAliasAnalysis/Steensgaard/full-store-partial-alias.ll @@ -1,10 +1,10 @@ -; RUN: opt -S -disable-basicaa -tbaa -cfl-aa -gvn < %s | FileCheck -check-prefix=CFLAA %s +; RUN: opt -S -disable-basicaa -tbaa -cfl-steens-aa -gvn < %s | FileCheck -check-prefix=CFLSteensAA %s ; RUN: opt -S -disable-basicaa -tbaa -gvn < %s | FileCheck %s ; Adapted from the BasicAA full-store-partial-alias.ll test. ; CFL AA could notice that the store stores to the entire %u object, ; so the %tmp5 load is PartialAlias with the store and suppress TBAA. -; FIXME: However, right now, CFLAA cannot prove PartialAlias here +; 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" @@ -15,8 +15,8 @@ @endianness_test = global i64 1, align 8 define i32 @signbit(double %x) nounwind { -; FIXME: This would be ret i32 %tmp5.lobit if CFLAA could prove PartialAlias -; CFLAA: ret i32 0 +; 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 Index: test/Analysis/CFLAliasAnalysis/Steensgaard/gep-index-no-alias.ll =================================================================== --- test/Analysis/CFLAliasAnalysis/Steensgaard/gep-index-no-alias.ll +++ test/Analysis/CFLAliasAnalysis/Steensgaard/gep-index-no-alias.ll @@ -1,7 +1,7 @@ ; This testcase ensures that gep result does not alias gep indices -; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-no-aliases -disable-output 2>&1 | FileCheck %s -; RUN: opt < %s -aa-pipeline=cfl-aa -passes=aa-eval -print-no-aliases -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -disable-basicaa -cfl-steens-aa -aa-eval -print-no-aliases -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-no-aliases -disable-output 2>&1 | FileCheck %s ; CHECK: Function: foo ; CHECK: [2 x i32]* %a, [2 x i32]* %b Index: test/Analysis/CFLAliasAnalysis/Steensgaard/gep-signed-arithmetic.ll =================================================================== --- test/Analysis/CFLAliasAnalysis/Steensgaard/gep-signed-arithmetic.ll +++ test/Analysis/CFLAliasAnalysis/Steensgaard/gep-signed-arithmetic.ll @@ -1,9 +1,9 @@ -; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -disable-basicaa -cfl-steens-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s ; Derived from BasicAA/2010-09-15-GEP-SignedArithmetic.ll target datalayout = "e-p:32:32:32" -; FIXME: This could be PartialAlias but CFLAA can't currently prove it +; FIXME: This could be PartialAlias but CFLSteensAA can't currently prove it ; CHECK: 1 may alias response define i32 @test(i32 %indvar) nounwind { Index: test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-arg-deref-escape.ll =================================================================== --- test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-arg-deref-escape.ll +++ test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-arg-deref-escape.ll @@ -1,8 +1,8 @@ ; This testcase ensures that CFL AA answers queries soundly when callee tries ; to escape the memory pointed to by its parameters -; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s -; RUN: opt < %s -aa-pipeline=cfl-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -disable-basicaa -cfl-steens-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s declare void @opaque(i32*) define void @escape_arg_deref(i32** %arg) { Index: test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-arg-escape.ll =================================================================== --- test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-arg-escape.ll +++ test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-arg-escape.ll @@ -1,8 +1,8 @@ ; This testcase ensures that CFL AA answers queries soundly when callee tries ; to escape its parameters -; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s -; RUN: opt < %s -aa-pipeline=cfl-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -disable-basicaa -cfl-steens-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s declare void @opaque(i32*) define void @escape_arg(i32* %arg) { Index: test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-ret-arg.ll =================================================================== --- test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-ret-arg.ll +++ test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-ret-arg.ll @@ -1,8 +1,8 @@ ; This testcase ensures that CFL AA answers queries soundly when callee tries ; to return one of its parameters -; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s -; RUN: opt < %s -aa-pipeline=cfl-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -disable-basicaa -cfl-steens-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s define i32* @return_arg_callee(i32* %arg1, i32* %arg2) { ret i32* %arg1 Index: test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-ret-deref-arg-multilevel.ll =================================================================== --- test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-ret-deref-arg-multilevel.ll +++ test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-ret-deref-arg-multilevel.ll @@ -1,8 +1,8 @@ ; This testcase ensures that CFL AA answers queries soundly when callee tries ; to return the multi-level dereference of one of its parameters -; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s -; RUN: opt < %s -aa-pipeline=cfl-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -disable-basicaa -cfl-steens-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s define i32* @return_deref_arg_multilevel_callee(i32*** %arg1) { %deref = load i32**, i32*** %arg1 Index: test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-ret-deref-arg.ll =================================================================== --- test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-ret-deref-arg.ll +++ test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-ret-deref-arg.ll @@ -1,8 +1,8 @@ ; This testcase ensures that CFL AA answers queries soundly when callee tries ; to return the dereference of one of its parameters -; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s -; RUN: opt < %s -aa-pipeline=cfl-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -disable-basicaa -cfl-steens-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s define i32* @return_deref_arg_callee(i32** %arg1) { %deref = load i32*, i32** %arg1 Index: test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-ret-escape.ll =================================================================== --- test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-ret-escape.ll +++ test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-ret-escape.ll @@ -1,8 +1,8 @@ ; This testcase ensures that CFL AA answers queries soundly when callee tries ; to return an escaped pointer -; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s -; RUN: opt < %s -aa-pipeline=cfl-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -disable-basicaa -cfl-steens-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s declare noalias i8* @malloc(i64) declare void @opaque(i32*) Index: test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-ret-ref-arg-multilevel.ll =================================================================== --- test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-ret-ref-arg-multilevel.ll +++ test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-ret-ref-arg-multilevel.ll @@ -1,8 +1,8 @@ ; This testcase ensures that CFL AA answers queries soundly when callee tries ; to return the multi-level reference of one of its parameters -; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s -; RUN: opt < %s -aa-pipeline=cfl-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -disable-basicaa -cfl-steens-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s declare noalias i8* @malloc(i64) Index: test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-ret-ref-arg.ll =================================================================== --- test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-ret-ref-arg.ll +++ test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-ret-ref-arg.ll @@ -1,8 +1,8 @@ ; This testcase ensures that CFL AA answers queries soundly when callee tries ; to return the reference of one of its parameters -; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s -; RUN: opt < %s -aa-pipeline=cfl-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -disable-basicaa -cfl-steens-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s declare noalias i8* @malloc(i64) Index: test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-ret-unknown.ll =================================================================== --- test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-ret-unknown.ll +++ test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-ret-unknown.ll @@ -1,8 +1,8 @@ ; This testcase ensures that CFL AA answers queries soundly when callee tries ; to return an unknown pointer -; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s -; RUN: opt < %s -aa-pipeline=cfl-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -disable-basicaa -cfl-steens-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s @g = external global i32 define i32* @return_unknown_callee(i32* %arg1, i32* %arg2) { Index: test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-store-arg-multilevel.ll =================================================================== --- test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-store-arg-multilevel.ll +++ test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-store-arg-multilevel.ll @@ -1,8 +1,8 @@ ; This testcase ensures that CFL AA answers queries soundly when callee tries ; to mutate the memory pointed to by its parameters -; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s -; RUN: opt < %s -aa-pipeline=cfl-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -disable-basicaa -cfl-steens-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s declare noalias i8* @malloc(i64) Index: test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-store-arg-unknown.ll =================================================================== --- test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-store-arg-unknown.ll +++ test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-store-arg-unknown.ll @@ -1,8 +1,8 @@ ; This testcase ensures that CFL AA answers queries soundly when callee tries ; to mutate the memory pointed to by its parameters -; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s -; RUN: opt < %s -aa-pipeline=cfl-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -disable-basicaa -cfl-steens-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s @g = external global i32 Index: test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-store-arg.ll =================================================================== --- test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-store-arg.ll +++ test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-store-arg.ll @@ -1,8 +1,8 @@ ; This testcase ensures that CFL AA answers queries soundly when callee tries ; to mutate the memory pointed to by its parameters -; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s -; RUN: opt < %s -aa-pipeline=cfl-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -disable-basicaa -cfl-steens-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s define void @store_arg_callee(i32** %arg1, i32* %arg2) { store i32* %arg2, i32** %arg1 Index: test/Analysis/CFLAliasAnalysis/Steensgaard/malloc-and-free.ll =================================================================== --- test/Analysis/CFLAliasAnalysis/Steensgaard/malloc-and-free.ll +++ test/Analysis/CFLAliasAnalysis/Steensgaard/malloc-and-free.ll @@ -1,7 +1,7 @@ ; This testcase ensures that CFL AA handles malloc and free in a sound and precise manner -; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-no-aliases -disable-output 2>&1 | FileCheck %s -; RUN: opt < %s -aa-pipeline=cfl-aa -passes=aa-eval -print-no-aliases -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -disable-basicaa -cfl-steens-aa -aa-eval -print-no-aliases -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-no-aliases -disable-output 2>&1 | FileCheck %s declare noalias i8* @malloc(i64) declare noalias i8* @calloc(i64, i64) Index: test/Analysis/CFLAliasAnalysis/Steensgaard/multilevel-combine.ll =================================================================== --- test/Analysis/CFLAliasAnalysis/Steensgaard/multilevel-combine.ll +++ test/Analysis/CFLAliasAnalysis/Steensgaard/multilevel-combine.ll @@ -8,7 +8,7 @@ ; } ; -; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -disable-basicaa -cfl-steens-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s %T = type { i32, [10 x i8] } Index: test/Analysis/CFLAliasAnalysis/Steensgaard/multilevel.ll =================================================================== --- test/Analysis/CFLAliasAnalysis/Steensgaard/multilevel.ll +++ test/Analysis/CFLAliasAnalysis/Steensgaard/multilevel.ll @@ -6,7 +6,7 @@ ; *m; ; *n; -; RUN: opt < %s -cfl-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -cfl-steens-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s %T = type { i32, [10 x i8] } Index: test/Analysis/CFLAliasAnalysis/Steensgaard/must-and-partial.ll =================================================================== --- test/Analysis/CFLAliasAnalysis/Steensgaard/must-and-partial.ll +++ test/Analysis/CFLAliasAnalysis/Steensgaard/must-and-partial.ll @@ -1,11 +1,11 @@ -; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-all-alias-modref-info 2>&1 | FileCheck %s +; RUN: opt < %s -disable-basicaa -cfl-steens-aa -aa-eval -print-all-alias-modref-info 2>&1 | FileCheck %s ; When merging MustAlias and PartialAlias, merge to PartialAlias ; instead of MayAlias. target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64" -; FIXME: This could be PartialAlias but CFLAA can't currently prove it +; FIXME: This could be PartialAlias but CFLSteensAA can't currently prove it ; CHECK: MayAlias: i16* %bigbase0, i8* %phi define i8 @test0(i1 %x) { entry: @@ -25,7 +25,7 @@ ret i8 %loaded } -; FIXME: This could be PartialAlias but CFLAA can't currently prove it +; FIXME: This could be PartialAlias but CFLSteensAA can't currently prove it ; CHECK: MayAlias: i16* %bigbase1, i8* %sel define i8 @test1(i1 %x) { entry: Index: test/Analysis/CFLAliasAnalysis/Steensgaard/opaque-call-alias.ll =================================================================== --- test/Analysis/CFLAliasAnalysis/Steensgaard/opaque-call-alias.ll +++ test/Analysis/CFLAliasAnalysis/Steensgaard/opaque-call-alias.ll @@ -2,7 +2,7 @@ ; its own stratified set. This would make cases like the one in @test say that ; nothing (except %Escapes and %Arg) can alias -; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -disable-basicaa -cfl-steens-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s ; CHECK: Function: test ; CHECK: NoAlias: i8* %Arg, i8* %Escapes Index: test/Analysis/CFLAliasAnalysis/Steensgaard/phi-and-select.ll =================================================================== --- test/Analysis/CFLAliasAnalysis/Steensgaard/phi-and-select.ll +++ test/Analysis/CFLAliasAnalysis/Steensgaard/phi-and-select.ll @@ -1,4 +1,4 @@ -; RUN: opt < %s -cfl-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -cfl-steens-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s ; Derived from (a subset of) BasicAA/phi-and-select.ll ; CHECK: Function: qux Index: test/Analysis/CFLAliasAnalysis/Steensgaard/pr27213.ll =================================================================== --- test/Analysis/CFLAliasAnalysis/Steensgaard/pr27213.ll +++ test/Analysis/CFLAliasAnalysis/Steensgaard/pr27213.ll @@ -1,5 +1,5 @@ -; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s -; RUN: opt < %s -aa-pipeline=cfl-aa -passes=aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -disable-basicaa -cfl-steens-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s ; CHECK-LABEL: Function: foo ; CHECK: MayAlias: i32* %A, i32* %B Index: test/Analysis/CFLAliasAnalysis/Steensgaard/simple.ll =================================================================== --- test/Analysis/CFLAliasAnalysis/Steensgaard/simple.ll +++ test/Analysis/CFLAliasAnalysis/Steensgaard/simple.ll @@ -1,7 +1,7 @@ ; This testcase consists of alias relations which should be completely -; resolvable by cfl-aa (derived from BasicAA/2003-11-04-SimpleCases.ll). +; resolvable by cfl-steens-aa (derived from BasicAA/2003-11-04-SimpleCases.ll). -; RUN: opt < %s -cfl-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -cfl-steens-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s %T = type { i32, [10 x i8] } Index: test/Analysis/CFLAliasAnalysis/Steensgaard/stratified-attrs-indexing.ll =================================================================== --- test/Analysis/CFLAliasAnalysis/Steensgaard/stratified-attrs-indexing.ll +++ test/Analysis/CFLAliasAnalysis/Steensgaard/stratified-attrs-indexing.ll @@ -1,11 +1,11 @@ -; This testcase ensures that CFLAA doesn't try to access out of bounds indices +; This testcase ensures that CFLSteensAA doesn't try to access out of bounds indices ; when given functions with large amounts of arguments (specifically, more ; arguments than the StratifiedAttrs bitset can handle) ; ; Because the result on failure is effectively crashing the compiler, output ; checking is minimal. -; RUN: opt < %s -cfl-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -cfl-steens-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s ; CHECK: Function: test define void @test(i1 %cond, Index: test/Analysis/CFLAliasAnalysis/Steensgaard/va.ll =================================================================== --- test/Analysis/CFLAliasAnalysis/Steensgaard/va.ll +++ test/Analysis/CFLAliasAnalysis/Steensgaard/va.ll @@ -1,4 +1,4 @@ -; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -disable-basicaa -cfl-steens-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s ; CHECK-LABEL: Function: test1 ; CHECK: MayAlias: i32* %X, i32* %tmp