Index: llvm/trunk/include/llvm/Analysis/CFLAliasAnalysis.h =================================================================== --- llvm/trunk/include/llvm/Analysis/CFLAliasAnalysis.h +++ llvm/trunk/include/llvm/Analysis/CFLAliasAnalysis.h @@ -1,159 +0,0 @@ -//===- CFLAliasAnalysis.h - CFL-Based Alias Analysis Interface ---*- C++ -*-==// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -/// \file -/// This is the interface for LLVM's primary stateless and local alias analysis. -/// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_ANALYSIS_CFLALIASANALYSIS_H -#define LLVM_ANALYSIS_CFLALIASANALYSIS_H - -#include "llvm/ADT/DenseMap.h" -#include "llvm/ADT/None.h" -#include "llvm/ADT/Optional.h" -#include "llvm/Analysis/AliasAnalysis.h" -#include "llvm/IR/Function.h" -#include "llvm/IR/Module.h" -#include "llvm/IR/ValueHandle.h" -#include "llvm/Pass.h" -#include - -namespace llvm { - -class TargetLibraryInfo; - -class CFLAAResult : public AAResultBase { - friend AAResultBase; - class FunctionInfo; - -public: - explicit CFLAAResult(const TargetLibraryInfo &); - CFLAAResult(CFLAAResult &&Arg); - ~CFLAAResult(); - - /// Handle invalidation events from the new pass manager. - /// - /// By definition, this result is stateless and so remains valid. - bool invalidate(Function &, const PreservedAnalyses &) { return false; } - - /// \brief Inserts the given Function into the cache. - void scan(Function *Fn); - - void evict(Function *Fn); - - /// \brief Ensures that the given function is available in the cache. - /// Returns the appropriate entry from the cache. - const Optional &ensureCached(Function *Fn); - - AliasResult query(const MemoryLocation &LocA, const MemoryLocation &LocB); - - AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB) { - if (LocA.Ptr == LocB.Ptr) - return LocA.Size == LocB.Size ? MustAlias : PartialAlias; - - // Comparisons between global variables and other constants should be - // handled by BasicAA. - // TODO: ConstantExpr handling -- CFLAA may report NoAlias when comparing - // a GlobalValue and ConstantExpr, but every query needs to have at least - // one Value tied to a Function, and neither GlobalValues nor ConstantExprs - // are. - if (isa(LocA.Ptr) && isa(LocB.Ptr)) - return AAResultBase::alias(LocA, LocB); - - AliasResult QueryResult = query(LocA, LocB); - if (QueryResult == MayAlias) - return AAResultBase::alias(LocA, LocB); - - return QueryResult; - } - - /// Get the location associated with a pointer argument of a callsite. - ModRefInfo getArgModRefInfo(ImmutableCallSite CS, unsigned ArgIdx); - - /// Returns the behavior when calling the given call site. - FunctionModRefBehavior getModRefBehavior(ImmutableCallSite CS); - - /// Returns the behavior when calling the given function. For use when the - /// call site is not known. - FunctionModRefBehavior getModRefBehavior(const Function *F); - -private: - struct FunctionHandle final : public CallbackVH { - FunctionHandle(Function *Fn, CFLAAResult *Result) - : CallbackVH(Fn), Result(Result) { - assert(Fn != nullptr); - assert(Result != nullptr); - } - - void deleted() override { removeSelfFromCache(); } - void allUsesReplacedWith(Value *) override { removeSelfFromCache(); } - - private: - CFLAAResult *Result; - - void removeSelfFromCache() { - assert(Result != nullptr); - auto *Val = getValPtr(); - Result->evict(cast(Val)); - setValPtr(nullptr); - } - }; - - const TargetLibraryInfo &TLI; - - /// \brief Cached mapping of Functions to their StratifiedSets. - /// If a function's sets are currently being built, it is marked - /// in the cache as an Optional without a value. This way, if we - /// have any kind of recursion, it is discernable from a function - /// that simply has empty sets. - DenseMap> Cache; - std::forward_list Handles; - - FunctionInfo buildSetsFrom(Function *F); -}; - -/// Analysis pass providing a never-invalidated alias analysis result. -/// -/// FIXME: We really should refactor CFL to use the analysis more heavily, and -/// in particular to leverage invalidation to trigger re-computation of sets. -class CFLAA : public AnalysisInfoMixin { - friend AnalysisInfoMixin; - static char PassID; - -public: - typedef CFLAAResult Result; - - CFLAAResult run(Function &F, AnalysisManager &AM); -}; - -/// Legacy wrapper pass to provide the CFLAAResult object. -class CFLAAWrapperPass : public ImmutablePass { - std::unique_ptr Result; - -public: - static char ID; - - CFLAAWrapperPass(); - - CFLAAResult &getResult() { return *Result; } - const CFLAAResult &getResult() const { return *Result; } - - void initializePass() override; - void getAnalysisUsage(AnalysisUsage &AU) const override; -}; - -//===--------------------------------------------------------------------===// -// -// createCFLAAWrapperPass - This pass implements a set-based approach to -// alias analysis. -// -ImmutablePass *createCFLAAWrapperPass(); -} - -#endif Index: llvm/trunk/include/llvm/Analysis/CFLAndersAliasAnalysis.h =================================================================== --- llvm/trunk/include/llvm/Analysis/CFLAndersAliasAnalysis.h +++ llvm/trunk/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: llvm/trunk/include/llvm/Analysis/CFLSteensAliasAnalysis.h =================================================================== --- llvm/trunk/include/llvm/Analysis/CFLSteensAliasAnalysis.h +++ llvm/trunk/include/llvm/Analysis/CFLSteensAliasAnalysis.h @@ -0,0 +1,159 @@ +//=- CFLSteensAliasAnalysis.h - Unification-based Alias Analysis ---*- C++-*-=// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +/// \file +/// This is the interface for LLVM's unification-based alias analysis +/// implemented with CFL graph reachability. +/// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_CFLSTEENSALIASANALYSIS_H +#define LLVM_ANALYSIS_CFLSTEENSALIASANALYSIS_H + +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/None.h" +#include "llvm/ADT/Optional.h" +#include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/IR/Function.h" +#include "llvm/IR/Module.h" +#include "llvm/IR/ValueHandle.h" +#include "llvm/Pass.h" +#include + +namespace llvm { + +class TargetLibraryInfo; + +class CFLSteensAAResult : public AAResultBase { + friend AAResultBase; + class FunctionInfo; + +public: + explicit CFLSteensAAResult(const TargetLibraryInfo &); + CFLSteensAAResult(CFLSteensAAResult &&Arg); + ~CFLSteensAAResult(); + + /// Handle invalidation events from the new pass manager. + /// + /// By definition, this result is stateless and so remains valid. + bool invalidate(Function &, const PreservedAnalyses &) { return false; } + + /// \brief Inserts the given Function into the cache. + void scan(Function *Fn); + + void evict(Function *Fn); + + /// \brief Ensures that the given function is available in the cache. + /// Returns the appropriate entry from the cache. + const Optional &ensureCached(Function *Fn); + + AliasResult query(const MemoryLocation &LocA, const MemoryLocation &LocB); + + AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB) { + if (LocA.Ptr == LocB.Ptr) + return LocA.Size == LocB.Size ? MustAlias : PartialAlias; + + // Comparisons between global variables and other constants should be + // handled by BasicAA. + // CFLSteensAA may report NoAlias when comparing a GlobalValue and + // ConstantExpr, but every query needs to have at least one Value tied to a + // Function, and neither GlobalValues nor ConstantExprs are. + if (isa(LocA.Ptr) && isa(LocB.Ptr)) + return AAResultBase::alias(LocA, LocB); + + AliasResult QueryResult = query(LocA, LocB); + if (QueryResult == MayAlias) + return AAResultBase::alias(LocA, LocB); + + return QueryResult; + } + + /// Get the location associated with a pointer argument of a callsite. + ModRefInfo getArgModRefInfo(ImmutableCallSite CS, unsigned ArgIdx); + + /// Returns the behavior when calling the given call site. + FunctionModRefBehavior getModRefBehavior(ImmutableCallSite CS); + + /// Returns the behavior when calling the given function. For use when the + /// call site is not known. + FunctionModRefBehavior getModRefBehavior(const Function *F); + +private: + struct FunctionHandle final : public CallbackVH { + FunctionHandle(Function *Fn, CFLSteensAAResult *Result) + : CallbackVH(Fn), Result(Result) { + assert(Fn != nullptr); + assert(Result != nullptr); + } + + void deleted() override { removeSelfFromCache(); } + void allUsesReplacedWith(Value *) override { removeSelfFromCache(); } + + private: + CFLSteensAAResult *Result; + + void removeSelfFromCache() { + assert(Result != nullptr); + auto *Val = getValPtr(); + Result->evict(cast(Val)); + setValPtr(nullptr); + } + }; + + const TargetLibraryInfo &TLI; + + /// \brief Cached mapping of Functions to their StratifiedSets. + /// If a function's sets are currently being built, it is marked + /// in the cache as an Optional without a value. This way, if we + /// have any kind of recursion, it is discernable from a function + /// that simply has empty sets. + DenseMap> Cache; + std::forward_list 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 { + friend AnalysisInfoMixin; + static char PassID; + +public: + typedef CFLSteensAAResult Result; + + CFLSteensAAResult run(Function &F, AnalysisManager &AM); +}; + +/// Legacy wrapper pass to provide the CFLSteensAAResult object. +class CFLSteensAAWrapperPass : public ImmutablePass { + std::unique_ptr Result; + +public: + static char ID; + + CFLSteensAAWrapperPass(); + + CFLSteensAAResult &getResult() { return *Result; } + const CFLSteensAAResult &getResult() const { return *Result; } + + void initializePass() override; + void getAnalysisUsage(AnalysisUsage &AU) const override; +}; + +//===--------------------------------------------------------------------===// +// +// createCFLSteensAAWrapperPass - This pass implements a set-based approach to +// alias analysis. +// +ImmutablePass *createCFLSteensAAWrapperPass(); +} + +#endif Index: llvm/trunk/include/llvm/InitializePasses.h =================================================================== --- llvm/trunk/include/llvm/InitializePasses.h +++ llvm/trunk/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: llvm/trunk/include/llvm/LinkAllPasses.h =================================================================== --- llvm/trunk/include/llvm/LinkAllPasses.h +++ llvm/trunk/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: llvm/trunk/lib/Analysis/AliasAnalysis.cpp =================================================================== --- llvm/trunk/lib/Analysis/AliasAnalysis.cpp +++ llvm/trunk/lib/Analysis/AliasAnalysis.cpp @@ -27,7 +27,8 @@ #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/BasicAliasAnalysis.h" #include "llvm/Analysis/CFG.h" -#include "llvm/Analysis/CFLAliasAnalysis.h" +#include "llvm/Analysis/CFLAndersAliasAnalysis.h" +#include "llvm/Analysis/CFLSteensAliasAnalysis.h" #include "llvm/Analysis/CaptureTracking.h" #include "llvm/Analysis/GlobalsModRef.h" #include "llvm/Analysis/ObjCARCAliasAnalysis.h" @@ -552,7 +553,8 @@ INITIALIZE_PASS_BEGIN(AAResultsWrapperPass, "aa", "Function Alias Analysis Results", false, true) INITIALIZE_PASS_DEPENDENCY(BasicAAWrapperPass) -INITIALIZE_PASS_DEPENDENCY(CFLAAWrapperPass) +INITIALIZE_PASS_DEPENDENCY(CFLAndersAAWrapperPass) +INITIALIZE_PASS_DEPENDENCY(CFLSteensAAWrapperPass) INITIALIZE_PASS_DEPENDENCY(ExternalAAWrapperPass) INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass) INITIALIZE_PASS_DEPENDENCY(ObjCARCAAWrapperPass) @@ -603,7 +605,9 @@ 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 @@ -630,7 +634,8 @@ AU.addUsedIfAvailable(); AU.addUsedIfAvailable(); AU.addUsedIfAvailable(); - AU.addUsedIfAvailable(); + AU.addUsedIfAvailable(); + AU.addUsedIfAvailable(); } AAResults llvm::createLegacyPMAAResults(Pass &P, Function &F, @@ -652,7 +657,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; @@ -695,5 +702,6 @@ AU.addUsedIfAvailable(); AU.addUsedIfAvailable(); AU.addUsedIfAvailable(); - AU.addUsedIfAvailable(); + AU.addUsedIfAvailable(); + AU.addUsedIfAvailable(); } Index: llvm/trunk/lib/Analysis/Analysis.cpp =================================================================== --- llvm/trunk/lib/Analysis/Analysis.cpp +++ llvm/trunk/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: llvm/trunk/lib/Analysis/CFLAliasAnalysis.cpp =================================================================== --- llvm/trunk/lib/Analysis/CFLAliasAnalysis.cpp +++ llvm/trunk/lib/Analysis/CFLAliasAnalysis.cpp @@ -1,1145 +0,0 @@ -//===- CFLAliasAnalysis.cpp - CFL-Based Alias Analysis Implementation ------==// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This file implements a CFL-based context-insensitive alias analysis -// algorithm. It does not depend on types. The algorithm is a mixture of the one -// described in "Demand-driven alias analysis for C" by Xin Zheng and Radu -// Rugina, and "Fast algorithms for Dyck-CFL-reachability with applications to -// Alias Analysis" by Zhang Q, Lyu M R, Yuan H, and Su Z. -- to summarize the -// papers, we build a graph of the uses of a variable, where each node is a -// memory location, and each edge is an action that happened on that memory -// location. The "actions" can be one of Dereference, Reference, or Assign. -// -// Two variables are considered as aliasing iff you can reach one value's node -// from the other value's node and the language formed by concatenating all of -// the edge labels (actions) conforms to a context-free grammar. -// -// Because this algorithm requires a graph search on each query, we execute the -// algorithm outlined in "Fast algorithms..." (mentioned above) -// in order to transform the graph into sets of variables that may alias in -// ~nlogn time (n = number of variables), which makes queries take constant -// time. -//===----------------------------------------------------------------------===// - -// N.B. AliasAnalysis as a whole is phrased as a FunctionPass at the moment, and -// CFLAA is interprocedural. This is *technically* A Bad Thing, because -// FunctionPasses are only allowed to inspect the Function that they're being -// run on. Realistically, this likely isn't a problem until we allow -// FunctionPasses to run concurrently. - -#include "llvm/Analysis/CFLAliasAnalysis.h" -#include "StratifiedSets.h" -#include "llvm/ADT/DenseMap.h" -#include "llvm/ADT/None.h" -#include "llvm/ADT/Optional.h" -#include "llvm/Analysis/MemoryBuiltins.h" -#include "llvm/Analysis/TargetLibraryInfo.h" -#include "llvm/IR/Constants.h" -#include "llvm/IR/Function.h" -#include "llvm/IR/InstVisitor.h" -#include "llvm/IR/Instructions.h" -#include "llvm/Pass.h" -#include "llvm/Support/Compiler.h" -#include "llvm/Support/Debug.h" -#include "llvm/Support/ErrorHandling.h" -#include "llvm/Support/raw_ostream.h" -#include -#include -#include -#include - -using namespace llvm; - -#define DEBUG_TYPE "cfl-aa" - -CFLAAResult::CFLAAResult(const TargetLibraryInfo &TLI) - : AAResultBase(), TLI(TLI) {} -CFLAAResult::CFLAAResult(CFLAAResult &&Arg) - : AAResultBase(std::move(Arg)), TLI(Arg.TLI) {} -CFLAAResult::~CFLAAResult() {} - -/// We use InterfaceValue to describe parameters/return value, as well as -/// potential memory locations that are pointed to by parameters/return value, -/// of a function. -/// Index is an integer which represents a single parameter or a return value. -/// When the index is 0, it refers to the return value. Non-zero index i refers -/// to the i-th parameter. -/// DerefLevel indicates the number of dereferences one must perform on the -/// parameter/return value to get this InterfaceValue. -struct InterfaceValue { - unsigned Index; - unsigned DerefLevel; -}; - -bool operator==(InterfaceValue lhs, InterfaceValue rhs) { - return lhs.Index == rhs.Index && lhs.DerefLevel == rhs.DerefLevel; -} -bool operator!=(InterfaceValue lhs, InterfaceValue rhs) { - return !(lhs == rhs); -} - -/// We use ExternalRelation to describe an externally visible aliasing relations -/// between parameters/return value of a function. -struct ExternalRelation { - InterfaceValue From, To; -}; - -/// We use ExternalAttribute to describe an externally visible StratifiedAttrs -/// for parameters/return value. -struct ExternalAttribute { - InterfaceValue IValue; - StratifiedAttrs Attr; -}; - -/// Information we have about a function and would like to keep around. -class CFLAAResult::FunctionInfo { - StratifiedSets Sets; - - // RetParamRelations is a collection of ExternalRelations. - SmallVector RetParamRelations; - - // RetParamAttributes is a collection of ExternalAttributes. - SmallVector RetParamAttributes; - -public: - FunctionInfo(Function &Fn, const SmallVectorImpl &RetVals, - StratifiedSets S); - - const StratifiedSets &getStratifiedSets() const { return Sets; } - const SmallVectorImpl &getRetParamRelations() const { - return RetParamRelations; - } - const SmallVectorImpl &getRetParamAttributes() const { - return RetParamAttributes; - } -}; - -/// Try to go from a Value* to a Function*. Never returns nullptr. -static Optional parentFunctionOfValue(Value *); - -/// Returns possible functions called by the Inst* into the given -/// SmallVectorImpl. Returns true if targets found, false otherwise. This is -/// templated so we can use it with CallInsts and InvokeInsts. -static bool getPossibleTargets(CallSite, SmallVectorImpl &); - -const StratifiedIndex StratifiedLink::SetSentinel = - std::numeric_limits::max(); - -namespace { -/// StratifiedInfo Attribute things. -LLVM_CONSTEXPR unsigned MaxStratifiedAttrIndex = NumStratifiedAttrs; -LLVM_CONSTEXPR unsigned AttrEscapedIndex = 0; -LLVM_CONSTEXPR unsigned AttrUnknownIndex = 1; -LLVM_CONSTEXPR unsigned AttrGlobalIndex = 2; -LLVM_CONSTEXPR unsigned AttrCallerIndex = 3; -LLVM_CONSTEXPR unsigned AttrFirstArgIndex = 4; -LLVM_CONSTEXPR unsigned AttrLastArgIndex = MaxStratifiedAttrIndex; -LLVM_CONSTEXPR unsigned AttrMaxNumArgs = AttrLastArgIndex - AttrFirstArgIndex; - -// NOTE: These aren't StratifiedAttrs because bitsets don't have a constexpr -// ctor for some versions of MSVC that we support. We could maybe refactor, -// but... -using StratifiedAttr = unsigned; -LLVM_CONSTEXPR StratifiedAttr AttrNone = 0; -LLVM_CONSTEXPR StratifiedAttr AttrEscaped = 1 << AttrEscapedIndex; -LLVM_CONSTEXPR StratifiedAttr AttrUnknown = 1 << AttrUnknownIndex; -LLVM_CONSTEXPR StratifiedAttr AttrGlobal = 1 << AttrGlobalIndex; -LLVM_CONSTEXPR StratifiedAttr AttrCaller = 1 << AttrCallerIndex; -LLVM_CONSTEXPR StratifiedAttr ExternalAttrMask = - AttrEscaped | AttrUnknown | AttrGlobal; - -/// The maximum number of arguments we can put into a summary. -LLVM_CONSTEXPR unsigned MaxSupportedArgsInSummary = 50; - -/// StratifiedSets call for knowledge of "direction", so this is how we -/// represent that locally. -enum class Level { Same, Above, Below }; - -/// Edges can be one of four "weights" -- each weight must have an inverse -/// weight (Assign has Assign; Reference has Dereference). -enum class EdgeType { - /// The weight assigned when assigning from or to a value. For example, in: - /// %b = getelementptr %a, 0 - /// ...The relationships are %b assign %a, and %a assign %b. This used to be - /// two edges, but having a distinction bought us nothing. - Assign, - - /// The edge used when we have an edge going from some handle to a Value. - /// Examples of this include: - /// %b = load %a (%b Dereference %a) - /// %b = extractelement %a, 0 (%a Dereference %b) - Dereference, - - /// The edge used when our edge goes from a value to a handle that may have - /// contained it at some point. Examples: - /// %b = load %a (%a Reference %b) - /// %b = extractelement %a, 0 (%b Reference %a) - Reference -}; - -/// The Program Expression Graph (PEG) of CFL analysis -class CFLGraph { - typedef Value *Node; - - struct Edge { - EdgeType Type; - Node Other; - }; - - typedef std::vector EdgeList; - - struct NodeInfo { - EdgeList Edges; - StratifiedAttrs Attr; - }; - - typedef DenseMap NodeMap; - NodeMap NodeImpls; - - // Gets the inverse of a given EdgeType. - static EdgeType flipWeight(EdgeType Initial) { - switch (Initial) { - case EdgeType::Assign: - return EdgeType::Assign; - case EdgeType::Dereference: - return EdgeType::Reference; - case EdgeType::Reference: - return EdgeType::Dereference; - } - llvm_unreachable("Incomplete coverage of EdgeType enum"); - } - - const NodeInfo *getNode(Node N) const { - auto Itr = NodeImpls.find(N); - if (Itr == NodeImpls.end()) - return nullptr; - return &Itr->second; - } - NodeInfo *getNode(Node N) { - auto Itr = NodeImpls.find(N); - if (Itr == NodeImpls.end()) - return nullptr; - return &Itr->second; - } - - static Node nodeDeref(const NodeMap::value_type &P) { return P.first; } - typedef std::pointer_to_unary_function - NodeDerefFun; - -public: - typedef EdgeList::const_iterator const_edge_iterator; - typedef mapped_iterator - const_node_iterator; - - bool addNode(Node N) { - return NodeImpls.insert(std::make_pair(N, NodeInfo{EdgeList(), AttrNone})) - .second; - } - - void addAttr(Node N, StratifiedAttrs Attr) { - auto *Info = getNode(N); - assert(Info != nullptr); - Info->Attr |= Attr; - } - - void addEdge(Node From, Node To, EdgeType Type) { - auto *FromInfo = getNode(From); - assert(FromInfo != nullptr); - auto *ToInfo = getNode(To); - assert(ToInfo != nullptr); - - FromInfo->Edges.push_back(Edge{Type, To}); - ToInfo->Edges.push_back(Edge{flipWeight(Type), From}); - } - - StratifiedAttrs attrFor(Node N) const { - auto *Info = getNode(N); - assert(Info != nullptr); - return Info->Attr; - } - - iterator_range edgesFor(Node N) const { - auto *Info = getNode(N); - assert(Info != nullptr); - auto &Edges = Info->Edges; - return make_range(Edges.begin(), Edges.end()); - } - - iterator_range nodes() const { - return make_range( - map_iterator(NodeImpls.begin(), NodeDerefFun(nodeDeref)), - map_iterator(NodeImpls.end(), NodeDerefFun(nodeDeref))); - } - - bool empty() const { return NodeImpls.empty(); } - std::size_t size() const { return NodeImpls.size(); } -}; - -// This is the result of instantiating InterfaceValue at a particular callsite -struct InterprocNode { - Value *Val; - unsigned DerefLevel; -}; - -// Interprocedural assignment edges that CFLGraph may not easily model -struct InterprocEdge { - InterprocNode From, To; -}; - -// Interprocedural attribute tagging that CFLGraph may not easily model -struct InterprocAttr { - InterprocNode Node; - StratifiedAttrs Attr; -}; - -/// Gets the edges our graph should have, based on an Instruction* -class GetEdgesVisitor : public InstVisitor { - CFLAAResult &AA; - const TargetLibraryInfo &TLI; - - CFLGraph &Graph; - SmallVectorImpl &ReturnValues; - SmallPtrSetImpl &Externals; - SmallPtrSetImpl &Escapes; - SmallVectorImpl &InterprocEdges; - SmallVectorImpl &InterprocAttrs; - - static bool hasUsefulEdges(ConstantExpr *CE) { - // ConstantExpr doesn't have terminators, invokes, or fences, so only needs - // to check for compares. - return CE->getOpcode() != Instruction::ICmp && - CE->getOpcode() != Instruction::FCmp; - } - - void addNode(Value *Val) { - if (!Graph.addNode(Val)) - return; - - if (isa(Val)) - Externals.insert(Val); - else if (auto CExpr = dyn_cast(Val)) - if (hasUsefulEdges(CExpr)) - visitConstantExpr(CExpr); - } - - void addNodeWithAttr(Value *Val, StratifiedAttrs Attr) { - addNode(Val); - Graph.addAttr(Val, Attr); - } - - void addEdge(Value *From, Value *To, EdgeType Type) { - if (!From->getType()->isPointerTy() || !To->getType()->isPointerTy()) - return; - addNode(From); - if (To != From) - addNode(To); - Graph.addEdge(From, To, Type); - } - -public: - GetEdgesVisitor(CFLAAResult &AA, const TargetLibraryInfo &TLI, - CFLGraph &Graph, SmallVectorImpl &ReturnValues, - SmallPtrSetImpl &Externals, - SmallPtrSetImpl &Escapes, - SmallVectorImpl &InterprocEdges, - SmallVectorImpl &InterprocAttrs) - : AA(AA), TLI(TLI), Graph(Graph), ReturnValues(ReturnValues), - Externals(Externals), Escapes(Escapes), InterprocEdges(InterprocEdges), - InterprocAttrs(InterprocAttrs) {} - - void visitInstruction(Instruction &) { - llvm_unreachable("Unsupported instruction encountered"); - } - - void visitReturnInst(ReturnInst &Inst) { - if (auto RetVal = Inst.getReturnValue()) { - if (RetVal->getType()->isPointerTy()) { - addNode(RetVal); - ReturnValues.push_back(RetVal); - } - } - } - - void visitPtrToIntInst(PtrToIntInst &Inst) { - auto *Ptr = Inst.getOperand(0); - addNodeWithAttr(Ptr, AttrEscaped); - } - - void visitIntToPtrInst(IntToPtrInst &Inst) { - auto *Ptr = &Inst; - addNodeWithAttr(Ptr, AttrUnknown); - } - - void visitCastInst(CastInst &Inst) { - auto *Src = Inst.getOperand(0); - addEdge(Src, &Inst, EdgeType::Assign); - } - - void visitBinaryOperator(BinaryOperator &Inst) { - auto *Op1 = Inst.getOperand(0); - auto *Op2 = Inst.getOperand(1); - addEdge(Op1, &Inst, EdgeType::Assign); - addEdge(Op2, &Inst, EdgeType::Assign); - } - - void visitAtomicCmpXchgInst(AtomicCmpXchgInst &Inst) { - auto *Ptr = Inst.getPointerOperand(); - auto *Val = Inst.getNewValOperand(); - addEdge(Ptr, Val, EdgeType::Dereference); - } - - void visitAtomicRMWInst(AtomicRMWInst &Inst) { - auto *Ptr = Inst.getPointerOperand(); - auto *Val = Inst.getValOperand(); - addEdge(Ptr, Val, EdgeType::Dereference); - } - - void visitPHINode(PHINode &Inst) { - for (Value *Val : Inst.incoming_values()) - addEdge(Val, &Inst, EdgeType::Assign); - } - - void visitGetElementPtrInst(GetElementPtrInst &Inst) { - auto *Op = Inst.getPointerOperand(); - addEdge(Op, &Inst, EdgeType::Assign); - } - - void visitSelectInst(SelectInst &Inst) { - // Condition is not processed here (The actual statement producing - // the condition result is processed elsewhere). For select, the - // condition is evaluated, but not loaded, stored, or assigned - // simply as a result of being the condition of a select. - - auto *TrueVal = Inst.getTrueValue(); - auto *FalseVal = Inst.getFalseValue(); - addEdge(TrueVal, &Inst, EdgeType::Assign); - addEdge(FalseVal, &Inst, EdgeType::Assign); - } - - void visitAllocaInst(AllocaInst &Inst) { Graph.addNode(&Inst); } - - void visitLoadInst(LoadInst &Inst) { - auto *Ptr = Inst.getPointerOperand(); - auto *Val = &Inst; - addEdge(Val, Ptr, EdgeType::Reference); - } - - void visitStoreInst(StoreInst &Inst) { - auto *Ptr = Inst.getPointerOperand(); - auto *Val = Inst.getValueOperand(); - addEdge(Ptr, Val, EdgeType::Dereference); - } - - void visitVAArgInst(VAArgInst &Inst) { - // We can't fully model va_arg here. For *Ptr = Inst.getOperand(0), it does - // two things: - // 1. Loads a value from *((T*)*Ptr). - // 2. Increments (stores to) *Ptr by some target-specific amount. - // For now, we'll handle this like a landingpad instruction (by placing the - // result in its own group, and having that group alias externals). - addNodeWithAttr(&Inst, AttrUnknown); - } - - static bool isFunctionExternal(Function *Fn) { - return !Fn->hasExactDefinition(); - } - - bool tryInterproceduralAnalysis(CallSite CS, - const SmallVectorImpl &Fns) { - assert(Fns.size() > 0); - - if (CS.arg_size() > MaxSupportedArgsInSummary) - return false; - - // Exit early if we'll fail anyway - for (auto *Fn : Fns) { - if (isFunctionExternal(Fn) || Fn->isVarArg()) - return false; - // Fail if the caller does not provide enough arguments - assert(Fn->arg_size() <= CS.arg_size()); - auto &MaybeInfo = AA.ensureCached(Fn); - if (!MaybeInfo.hasValue()) - return false; - } - - auto InstantiateInterfaceIndex = [&CS](unsigned Index) { - auto Value = - (Index == 0) ? CS.getInstruction() : CS.getArgument(Index - 1); - return Value->getType()->isPointerTy() ? Value : nullptr; - }; - - for (auto *Fn : Fns) { - auto &FnInfo = AA.ensureCached(Fn); - assert(FnInfo.hasValue()); - - auto &RetParamRelations = FnInfo->getRetParamRelations(); - for (auto &Relation : RetParamRelations) { - auto FromVal = InstantiateInterfaceIndex(Relation.From.Index); - auto ToVal = InstantiateInterfaceIndex(Relation.To.Index); - if (FromVal && ToVal) { - auto FromLevel = Relation.From.DerefLevel; - auto ToLevel = Relation.To.DerefLevel; - InterprocEdges.push_back( - InterprocEdge{InterprocNode{FromVal, FromLevel}, - InterprocNode{ToVal, ToLevel}}); - } - } - - auto &RetParamAttributes = FnInfo->getRetParamAttributes(); - for (auto &Attribute : RetParamAttributes) { - if (auto Val = InstantiateInterfaceIndex(Attribute.IValue.Index)) { - InterprocAttrs.push_back(InterprocAttr{ - InterprocNode{Val, Attribute.IValue.DerefLevel}, Attribute.Attr}); - } - } - } - - return true; - } - - void visitCallSite(CallSite CS) { - auto Inst = CS.getInstruction(); - - // Make sure all arguments and return value are added to the graph first - for (Value *V : CS.args()) - addNode(V); - if (Inst->getType()->isPointerTy()) - addNode(Inst); - - // Check if Inst is a call to a library function that allocates/deallocates - // on the heap. Those kinds of functions do not introduce any aliases. - // TODO: address other common library functions such as realloc(), strdup(), - // etc. - if (isMallocLikeFn(Inst, &TLI) || isCallocLikeFn(Inst, &TLI) || - isFreeCall(Inst, &TLI)) - return; - - // TODO: Add support for noalias args/all the other fun function attributes - // that we can tack on. - SmallVector Targets; - if (getPossibleTargets(CS, Targets)) - if (tryInterproceduralAnalysis(CS, Targets)) - return; - - // Because the function is opaque, we need to note that anything - // could have happened to the arguments (unless the function is marked - // readonly or readnone), and that the result could alias just about - // anything, too (unless the result is marked noalias). - if (!CS.onlyReadsMemory()) - for (Value *V : CS.args()) { - if (V->getType()->isPointerTy()) - Escapes.insert(V); - } - - if (Inst->getType()->isPointerTy()) { - auto *Fn = CS.getCalledFunction(); - if (Fn == nullptr || !Fn->doesNotAlias(0)) - Graph.addAttr(Inst, AttrUnknown); - } - } - - /// Because vectors/aggregates are immutable and unaddressable, there's - /// nothing we can do to coax a value out of them, other than calling - /// Extract{Element,Value}. We can effectively treat them as pointers to - /// arbitrary memory locations we can store in and load from. - void visitExtractElementInst(ExtractElementInst &Inst) { - auto *Ptr = Inst.getVectorOperand(); - auto *Val = &Inst; - addEdge(Val, Ptr, EdgeType::Reference); - } - - void visitInsertElementInst(InsertElementInst &Inst) { - auto *Vec = Inst.getOperand(0); - auto *Val = Inst.getOperand(1); - addEdge(Vec, &Inst, EdgeType::Assign); - addEdge(&Inst, Val, EdgeType::Dereference); - } - - void visitLandingPadInst(LandingPadInst &Inst) { - // Exceptions come from "nowhere", from our analysis' perspective. - // So we place the instruction its own group, noting that said group may - // alias externals - addNodeWithAttr(&Inst, AttrUnknown); - } - - void visitInsertValueInst(InsertValueInst &Inst) { - auto *Agg = Inst.getOperand(0); - auto *Val = Inst.getOperand(1); - addEdge(Agg, &Inst, EdgeType::Assign); - addEdge(&Inst, Val, EdgeType::Dereference); - } - - void visitExtractValueInst(ExtractValueInst &Inst) { - auto *Ptr = Inst.getAggregateOperand(); - addEdge(&Inst, Ptr, EdgeType::Reference); - } - - void visitShuffleVectorInst(ShuffleVectorInst &Inst) { - auto *From1 = Inst.getOperand(0); - auto *From2 = Inst.getOperand(1); - addEdge(From1, &Inst, EdgeType::Assign); - addEdge(From2, &Inst, EdgeType::Assign); - } - - void visitConstantExpr(ConstantExpr *CE) { - switch (CE->getOpcode()) { - default: - llvm_unreachable("Unknown instruction type encountered!"); -// Build the switch statement using the Instruction.def file. -#define HANDLE_INST(NUM, OPCODE, CLASS) \ - case Instruction::OPCODE: \ - visit##OPCODE(*(CLASS *)CE); \ - break; -#include "llvm/IR/Instruction.def" - } - } -}; - -class CFLGraphBuilder { - // Input of the builder - CFLAAResult &Analysis; - const TargetLibraryInfo &TLI; - - // Output of the builder - CFLGraph Graph; - SmallVector ReturnedValues; - - // Auxiliary structures used by the builder - SmallPtrSet ExternalValues; - SmallPtrSet EscapedValues; - SmallVector InterprocEdges; - SmallVector InterprocAttrs; - - // Helper functions - - // Determines whether or not we an instruction is useless to us (e.g. - // FenceInst) - static bool hasUsefulEdges(Instruction *Inst) { - bool IsNonInvokeRetTerminator = isa(Inst) && - !isa(Inst) && - !isa(Inst); - return !isa(Inst) && !isa(Inst) && - !IsNonInvokeRetTerminator; - } - - void addArgumentToGraph(Argument &Arg) { - if (Arg.getType()->isPointerTy()) { - Graph.addNode(&Arg); - ExternalValues.insert(&Arg); - } - } - - // Given an Instruction, this will add it to the graph, along with any - // Instructions that are potentially only available from said Instruction - // For example, given the following line: - // %0 = load i16* getelementptr ([1 x i16]* @a, 0, 0), align 2 - // addInstructionToGraph would add both the `load` and `getelementptr` - // instructions to the graph appropriately. - void addInstructionToGraph(Instruction &Inst) { - if (!hasUsefulEdges(&Inst)) - return; - - GetEdgesVisitor(Analysis, TLI, Graph, ReturnedValues, ExternalValues, - EscapedValues, InterprocEdges, InterprocAttrs) - .visit(Inst); - } - - // Builds the graph needed for constructing the StratifiedSets for the given - // function - void buildGraphFrom(Function &Fn) { - for (auto &Bb : Fn.getBasicBlockList()) - for (auto &Inst : Bb.getInstList()) - addInstructionToGraph(Inst); - - for (auto &Arg : Fn.args()) - addArgumentToGraph(Arg); - } - -public: - CFLGraphBuilder(CFLAAResult &Analysis, const TargetLibraryInfo &TLI, - Function &Fn) - : Analysis(Analysis), TLI(TLI) { - buildGraphFrom(Fn); - } - - const CFLGraph &getCFLGraph() const { return Graph; } - const SmallVector &getReturnValues() const { - return ReturnedValues; - } - const SmallPtrSet &getExternalValues() const { - return ExternalValues; - } - const SmallPtrSet &getEscapedValues() const { - return EscapedValues; - } - const SmallVector &getInterprocEdges() const { - return InterprocEdges; - } - const SmallVector &getInterprocAttrs() const { - return InterprocAttrs; - } -}; -} - -//===----------------------------------------------------------------------===// -// Function declarations that require types defined in the namespace above -//===----------------------------------------------------------------------===// - -/// Given a StratifiedAttrs, returns true if it marks the corresponding values -/// as globals or arguments -static bool isGlobalOrArgAttr(StratifiedAttrs Attr); - -/// Given a StratifiedAttrs, returns true if the corresponding values come from -/// an unknown source (such as opaque memory or an integer cast) -static bool isUnknownAttr(StratifiedAttrs Attr); - -/// Given an argument number, returns the appropriate StratifiedAttr to set. -static StratifiedAttrs argNumberToAttr(unsigned ArgNum); - -/// Given a Value, potentially return which StratifiedAttr it maps to. -static Optional valueToAttr(Value *Val); - -/// Gets the "Level" that one should travel in StratifiedSets -/// given an EdgeType. -static Level directionOfEdgeType(EdgeType); - -/// Determines whether it would be pointless to add the given Value to our sets. -static bool canSkipAddingToSets(Value *Val); - -static Optional parentFunctionOfValue(Value *Val) { - if (auto *Inst = dyn_cast(Val)) { - auto *Bb = Inst->getParent(); - return Bb->getParent(); - } - - if (auto *Arg = dyn_cast(Val)) - return Arg->getParent(); - return None; -} - -static bool getPossibleTargets(CallSite CS, - SmallVectorImpl &Output) { - if (auto *Fn = CS.getCalledFunction()) { - Output.push_back(Fn); - return true; - } - - // TODO: If the call is indirect, we might be able to enumerate all potential - // targets of the call and return them, rather than just failing. - return false; -} - -static bool isGlobalOrArgAttr(StratifiedAttrs Attr) { - return Attr.reset(AttrEscapedIndex) - .reset(AttrUnknownIndex) - .reset(AttrCallerIndex) - .any(); -} - -static bool isUnknownAttr(StratifiedAttrs Attr) { - return Attr.test(AttrUnknownIndex) || Attr.test(AttrCallerIndex); -} - -static Optional valueToAttr(Value *Val) { - if (isa(Val)) - return StratifiedAttrs(AttrGlobal); - - if (auto *Arg = dyn_cast(Val)) - // Only pointer arguments should have the argument attribute, - // because things can't escape through scalars without us seeing a - // cast, and thus, interaction with them doesn't matter. - if (!Arg->hasNoAliasAttr() && Arg->getType()->isPointerTy()) - return argNumberToAttr(Arg->getArgNo()); - return None; -} - -static StratifiedAttrs argNumberToAttr(unsigned ArgNum) { - if (ArgNum >= AttrMaxNumArgs) - return AttrUnknown; - // N.B. MSVC complains if we use `1U` here, since StratifiedAttrs' ctor takes - // an unsigned long long. - return StratifiedAttrs(1ULL << (ArgNum + AttrFirstArgIndex)); -} - -static Level directionOfEdgeType(EdgeType Weight) { - switch (Weight) { - case EdgeType::Reference: - return Level::Above; - case EdgeType::Dereference: - return Level::Below; - case EdgeType::Assign: - return Level::Same; - } - llvm_unreachable("Incomplete switch coverage"); -} - -static bool canSkipAddingToSets(Value *Val) { - // Constants can share instances, which may falsely unify multiple - // sets, e.g. in - // store i32* null, i32** %ptr1 - // store i32* null, i32** %ptr2 - // clearly ptr1 and ptr2 should not be unified into the same set, so - // we should filter out the (potentially shared) instance to - // i32* null. - if (isa(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(Val) || - isa(Val) || - isa(Val); - return !CanStoreMutableData; - } - - return false; -} - -CFLAAResult::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. - if (Fn.arg_size() > MaxSupportedArgsInSummary) - return; - - DenseMap InterfaceMap; - - // Our intention here is to record all InterfaceValues that share the same - // StratifiedIndex in RetParamRelations. For each valid InterfaceValue, we - // have its StratifiedIndex scanned here and check if the index is presented - // in InterfaceMap: if it is not, we add the correspondence to the map; - // otherwise, an aliasing relation is found and we add it to - // RetParamRelations. - - auto AddToRetParamRelations = [&](unsigned InterfaceIndex, - StratifiedIndex SetIndex) { - unsigned Level = 0; - while (true) { - InterfaceValue CurrValue{InterfaceIndex, Level}; - - auto Itr = InterfaceMap.find(SetIndex); - if (Itr != InterfaceMap.end()) { - if (CurrValue != Itr->second) - RetParamRelations.push_back(ExternalRelation{CurrValue, Itr->second}); - break; - } - - auto &Link = Sets.getLink(SetIndex); - InterfaceMap.insert(std::make_pair(SetIndex, CurrValue)); - auto ExternalAttrs = Link.Attrs & StratifiedAttrs(ExternalAttrMask); - if (ExternalAttrs.any()) - RetParamAttributes.push_back( - ExternalAttribute{CurrValue, ExternalAttrs}); - - if (!Link.hasBelow()) - break; - - ++Level; - SetIndex = Link.Below; - } - }; - - // Populate RetParamRelations for return values - for (auto *RetVal : RetVals) { - assert(RetVal != nullptr); - assert(RetVal->getType()->isPointerTy()); - auto RetInfo = Sets.find(RetVal); - if (RetInfo.hasValue()) - AddToRetParamRelations(0, RetInfo->Index); - } - - // Populate RetParamRelations for parameters - unsigned I = 0; - for (auto &Param : Fn.args()) { - if (Param.getType()->isPointerTy()) { - auto ParamInfo = Sets.find(&Param); - if (ParamInfo.hasValue()) - AddToRetParamRelations(I + 1, ParamInfo->Index); - } - ++I; - } -} - -// Builds the graph + StratifiedSets for a function. -CFLAAResult::FunctionInfo CFLAAResult::buildSetsFrom(Function *Fn) { - CFLGraphBuilder GraphBuilder(*this, TLI, *Fn); - StratifiedSetsBuilder SetBuilder; - - auto &Graph = GraphBuilder.getCFLGraph(); - SmallVector Worklist; - for (auto Node : Graph.nodes()) - Worklist.push_back(Node); - - while (!Worklist.empty()) { - auto *CurValue = Worklist.pop_back_val(); - SetBuilder.add(CurValue); - if (canSkipAddingToSets(CurValue)) - continue; - - auto Attr = Graph.attrFor(CurValue); - SetBuilder.noteAttributes(CurValue, Attr); - - for (const auto &Edge : Graph.edgesFor(CurValue)) { - auto Label = Edge.Type; - auto *OtherValue = Edge.Other; - - if (canSkipAddingToSets(OtherValue)) - continue; - - bool Added; - switch (directionOfEdgeType(Label)) { - case Level::Above: - Added = SetBuilder.addAbove(CurValue, OtherValue); - break; - case Level::Below: - Added = SetBuilder.addBelow(CurValue, OtherValue); - break; - case Level::Same: - Added = SetBuilder.addWith(CurValue, OtherValue); - break; - } - - if (Added) - Worklist.push_back(OtherValue); - } - } - - // Special handling for globals and arguments - for (auto *External : GraphBuilder.getExternalValues()) { - SetBuilder.add(External); - auto Attr = valueToAttr(External); - if (Attr.hasValue()) { - SetBuilder.noteAttributes(External, *Attr); - if (*Attr == AttrGlobal) - SetBuilder.addAttributesBelow(External, 1, AttrUnknown); - else - SetBuilder.addAttributesBelow(External, 1, AttrCaller); - } - } - - // Special handling for interprocedural aliases - for (auto &Edge : GraphBuilder.getInterprocEdges()) { - auto FromVal = Edge.From.Val; - auto ToVal = Edge.To.Val; - SetBuilder.add(FromVal); - SetBuilder.add(ToVal); - SetBuilder.addBelowWith(FromVal, Edge.From.DerefLevel, ToVal, - Edge.To.DerefLevel); - } - - // Special handling for interprocedural attributes - for (auto &IPAttr : GraphBuilder.getInterprocAttrs()) { - auto Val = IPAttr.Node.Val; - SetBuilder.add(Val); - SetBuilder.addAttributesBelow(Val, IPAttr.Node.DerefLevel, IPAttr.Attr); - } - - // Special handling for opaque external functions - for (auto *Escape : GraphBuilder.getEscapedValues()) { - SetBuilder.add(Escape); - SetBuilder.noteAttributes(Escape, AttrEscaped); - SetBuilder.addAttributesBelow(Escape, 1, AttrUnknown); - } - - return FunctionInfo(*Fn, GraphBuilder.getReturnValues(), SetBuilder.build()); -} - -void CFLAAResult::scan(Function *Fn) { - auto InsertPair = Cache.insert(std::make_pair(Fn, Optional())); - (void)InsertPair; - assert(InsertPair.second && - "Trying to scan a function that has already been cached"); - - // Note that we can't do Cache[Fn] = buildSetsFrom(Fn) here: the function call - // may get evaluated after operator[], potentially triggering a DenseMap - // resize and invalidating the reference returned by operator[] - auto FunInfo = buildSetsFrom(Fn); - Cache[Fn] = std::move(FunInfo); - - Handles.push_front(FunctionHandle(Fn, this)); -} - -void CFLAAResult::evict(Function *Fn) { Cache.erase(Fn); } - -/// Ensures that the given function is available in the cache, and returns the -/// entry. -const Optional & -CFLAAResult::ensureCached(Function *Fn) { - auto Iter = Cache.find(Fn); - if (Iter == Cache.end()) { - scan(Fn); - Iter = Cache.find(Fn); - assert(Iter != Cache.end()); - assert(Iter->second.hasValue()); - } - return Iter->second; -} - -AliasResult CFLAAResult::query(const MemoryLocation &LocA, - const MemoryLocation &LocB) { - auto *ValA = const_cast(LocA.Ptr); - auto *ValB = const_cast(LocB.Ptr); - - if (!ValA->getType()->isPointerTy() || !ValB->getType()->isPointerTy()) - return NoAlias; - - Function *Fn = nullptr; - auto MaybeFnA = parentFunctionOfValue(ValA); - auto MaybeFnB = parentFunctionOfValue(ValB); - if (!MaybeFnA.hasValue() && !MaybeFnB.hasValue()) { - // The only times this is known to happen are when globals + InlineAsm are - // involved - DEBUG(dbgs() << "CFLAA: could not extract parent function information.\n"); - return MayAlias; - } - - if (MaybeFnA.hasValue()) { - Fn = *MaybeFnA; - assert((!MaybeFnB.hasValue() || *MaybeFnB == *MaybeFnA) && - "Interprocedural queries not supported"); - } else { - Fn = *MaybeFnB; - } - - assert(Fn != nullptr); - auto &MaybeInfo = ensureCached(Fn); - assert(MaybeInfo.hasValue()); - - auto &Sets = MaybeInfo->getStratifiedSets(); - auto MaybeA = Sets.find(ValA); - if (!MaybeA.hasValue()) - return MayAlias; - - auto MaybeB = Sets.find(ValB); - if (!MaybeB.hasValue()) - return MayAlias; - - auto SetA = *MaybeA; - auto SetB = *MaybeB; - auto AttrsA = Sets.getLink(SetA.Index).Attrs; - auto AttrsB = Sets.getLink(SetB.Index).Attrs; - - // If both values are local (meaning the corresponding set has attribute - // AttrNone or AttrEscaped), then we know that CFLAA fully models them: they - // may-alias each other if and only if they are in the same set - // If at least one value is non-local (meaning it either is global/argument or - // it comes from unknown sources like integer cast), the situation becomes a - // bit more interesting. We follow three general rules described below: - // - Non-local values may alias each other - // - AttrNone values do not alias any non-local values - // - AttrEscaped do not alias globals/arguments, but they may alias - // AttrUnknown values - if (SetA.Index == SetB.Index) - return MayAlias; - if (AttrsA.none() || AttrsB.none()) - return NoAlias; - if (isUnknownAttr(AttrsA) || isUnknownAttr(AttrsB)) - return MayAlias; - if (isGlobalOrArgAttr(AttrsA) && isGlobalOrArgAttr(AttrsB)) - return MayAlias; - return NoAlias; -} - -ModRefInfo CFLAAResult::getArgModRefInfo(ImmutableCallSite CS, - unsigned ArgIdx) { - if (auto CalledFunc = CS.getCalledFunction()) { - auto &MaybeInfo = ensureCached(const_cast(CalledFunc)); - if (!MaybeInfo.hasValue()) - return MRI_ModRef; - auto &RetParamAttributes = MaybeInfo->getRetParamAttributes(); - auto &RetParamRelations = MaybeInfo->getRetParamRelations(); - - bool ArgAttributeIsWritten = - std::any_of(RetParamAttributes.begin(), RetParamAttributes.end(), - [ArgIdx](const ExternalAttribute &ExtAttr) { - return ExtAttr.IValue.Index == ArgIdx + 1; - }); - bool ArgIsAccessed = - std::any_of(RetParamRelations.begin(), RetParamRelations.end(), - [ArgIdx](const ExternalRelation &ExtRelation) { - return ExtRelation.To.Index == ArgIdx + 1 || - ExtRelation.From.Index == ArgIdx + 1; - }); - - return (!ArgIsAccessed && !ArgAttributeIsWritten) ? MRI_NoModRef - : MRI_ModRef; - } - - return MRI_ModRef; -} - -FunctionModRefBehavior CFLAAResult::getModRefBehavior(ImmutableCallSite CS) { - // If we know the callee, try analyzing it - if (auto CalledFunc = CS.getCalledFunction()) - return getModRefBehavior(CalledFunc); - - // Otherwise, be conservative - return FMRB_UnknownModRefBehavior; -} - -FunctionModRefBehavior CFLAAResult::getModRefBehavior(const Function *F) { - assert(F != nullptr); - - // TODO: Remove the const_cast - auto &MaybeInfo = ensureCached(const_cast(F)); - if (!MaybeInfo.hasValue()) - return FMRB_UnknownModRefBehavior; - auto &RetParamAttributes = MaybeInfo->getRetParamAttributes(); - auto &RetParamRelations = MaybeInfo->getRetParamRelations(); - - // First, if any argument is marked Escpaed, Unknown or Global, anything may - // happen to them and thus we can't draw any conclusion. - if (!RetParamAttributes.empty()) - return FMRB_UnknownModRefBehavior; - - // Currently we don't (and can't) distinguish reads from writes in - // RetParamRelations. All we can say is whether there may be memory access or - // not. - if (RetParamRelations.empty()) - return FMRB_DoesNotAccessMemory; - - // Check if something beyond argmem gets touched. - bool AccessArgMemoryOnly = - std::all_of(RetParamRelations.begin(), RetParamRelations.end(), - [](const ExternalRelation &ExtRelation) { - // Both DerefLevels has to be 0, since we don't know which - // one is a read and which is a write. - return ExtRelation.From.DerefLevel == 0 && - ExtRelation.To.DerefLevel == 0; - }); - return AccessArgMemoryOnly ? FMRB_OnlyAccessesArgumentPointees - : FMRB_UnknownModRefBehavior; -} - -char CFLAA::PassID; - -CFLAAResult CFLAA::run(Function &F, AnalysisManager &AM) { - return CFLAAResult(AM.getResult(F)); -} - -char CFLAAWrapperPass::ID = 0; -INITIALIZE_PASS(CFLAAWrapperPass, "cfl-aa", "CFL-Based Alias Analysis", false, - true) - -ImmutablePass *llvm::createCFLAAWrapperPass() { return new CFLAAWrapperPass(); } - -CFLAAWrapperPass::CFLAAWrapperPass() : ImmutablePass(ID) { - initializeCFLAAWrapperPassPass(*PassRegistry::getPassRegistry()); -} - -void CFLAAWrapperPass::initializePass() { - auto &TLIWP = getAnalysis(); - Result.reset(new CFLAAResult(TLIWP.getTLI())); -} - -void CFLAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { - AU.setPreservesAll(); - AU.addRequired(); -} Index: llvm/trunk/lib/Analysis/CFLAndersAliasAnalysis.cpp =================================================================== --- llvm/trunk/lib/Analysis/CFLAndersAliasAnalysis.cpp +++ llvm/trunk/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: llvm/trunk/lib/Analysis/CFLSteensAliasAnalysis.cpp =================================================================== --- llvm/trunk/lib/Analysis/CFLSteensAliasAnalysis.cpp +++ llvm/trunk/lib/Analysis/CFLSteensAliasAnalysis.cpp @@ -0,0 +1,1151 @@ +//- CFLSteensAliasAnalysis.cpp - Unification-based Alias Analysis ---*- C++-*-// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file implements a CFL-base, summary-based alias analysis algorithm. It +// does not depend on types. The algorithm is a mixture of the one described in +// "Demand-driven alias analysis for C" by Xin Zheng and Radu Rugina, and "Fast +// algorithms for Dyck-CFL-reachability with applications to Alias Analysis" by +// Zhang Q, Lyu M R, Yuan H, and Su Z. -- to summarize the papers, we build a +// graph of the uses of a variable, where each node is a memory location, and +// each edge is an action that happened on that memory location. The "actions" +// can be one of Dereference, Reference, or Assign. The precision of this +// analysis is roughly the same as that of an one level context-sensitive +// Steensgaard's algorithm. +// +// Two variables are considered as aliasing iff you can reach one value's node +// from the other value's node and the language formed by concatenating all of +// the edge labels (actions) conforms to a context-free grammar. +// +// Because this algorithm requires a graph search on each query, we execute the +// algorithm outlined in "Fast algorithms..." (mentioned above) +// in order to transform the graph into sets of variables that may alias in +// ~nlogn time (n = number of variables), which makes queries take constant +// time. +//===----------------------------------------------------------------------===// + +// N.B. AliasAnalysis as a whole is phrased as a FunctionPass at the moment, and +// CFLSteensAA is interprocedural. This is *technically* A Bad Thing, because +// FunctionPasses are only allowed to inspect the Function that they're being +// run on. Realistically, this likely isn't a problem until we allow +// FunctionPasses to run concurrently. + +#include "llvm/Analysis/CFLSteensAliasAnalysis.h" +#include "StratifiedSets.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/None.h" +#include "llvm/ADT/Optional.h" +#include "llvm/Analysis/MemoryBuiltins.h" +#include "llvm/Analysis/TargetLibraryInfo.h" +#include "llvm/IR/Constants.h" +#include "llvm/IR/Function.h" +#include "llvm/IR/InstVisitor.h" +#include "llvm/IR/Instructions.h" +#include "llvm/Pass.h" +#include "llvm/Support/Compiler.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/ErrorHandling.h" +#include "llvm/Support/raw_ostream.h" +#include +#include +#include +#include + +using namespace llvm; + +#define DEBUG_TYPE "cfl-steens-aa" + +CFLSteensAAResult::CFLSteensAAResult(const TargetLibraryInfo &TLI) + : AAResultBase(), TLI(TLI) {} +CFLSteensAAResult::CFLSteensAAResult(CFLSteensAAResult &&Arg) + : AAResultBase(std::move(Arg)), TLI(Arg.TLI) {} +CFLSteensAAResult::~CFLSteensAAResult() {} + +/// We use InterfaceValue to describe parameters/return value, as well as +/// potential memory locations that are pointed to by parameters/return value, +/// of a function. +/// Index is an integer which represents a single parameter or a return value. +/// When the index is 0, it refers to the return value. Non-zero index i refers +/// to the i-th parameter. +/// DerefLevel indicates the number of dereferences one must perform on the +/// parameter/return value to get this InterfaceValue. +struct InterfaceValue { + unsigned Index; + unsigned DerefLevel; +}; + +bool operator==(InterfaceValue lhs, InterfaceValue rhs) { + return lhs.Index == rhs.Index && lhs.DerefLevel == rhs.DerefLevel; +} +bool operator!=(InterfaceValue lhs, InterfaceValue rhs) { + return !(lhs == rhs); +} + +/// We use ExternalRelation to describe an externally visible aliasing relations +/// between parameters/return value of a function. +struct ExternalRelation { + InterfaceValue From, To; +}; + +/// We use ExternalAttribute to describe an externally visible StratifiedAttrs +/// for parameters/return value. +struct ExternalAttribute { + InterfaceValue IValue; + StratifiedAttrs Attr; +}; + +/// Information we have about a function and would like to keep around. +class CFLSteensAAResult::FunctionInfo { + StratifiedSets Sets; + + // RetParamRelations is a collection of ExternalRelations. + SmallVector RetParamRelations; + + // RetParamAttributes is a collection of ExternalAttributes. + SmallVector RetParamAttributes; + +public: + FunctionInfo(Function &Fn, const SmallVectorImpl &RetVals, + StratifiedSets S); + + const StratifiedSets &getStratifiedSets() const { return Sets; } + const SmallVectorImpl &getRetParamRelations() const { + return RetParamRelations; + } + const SmallVectorImpl &getRetParamAttributes() const { + return RetParamAttributes; + } +}; + +/// Try to go from a Value* to a Function*. Never returns nullptr. +static Optional parentFunctionOfValue(Value *); + +/// Returns possible functions called by the Inst* into the given +/// SmallVectorImpl. Returns true if targets found, false otherwise. This is +/// templated so we can use it with CallInsts and InvokeInsts. +static bool getPossibleTargets(CallSite, SmallVectorImpl &); + +const StratifiedIndex StratifiedLink::SetSentinel = + std::numeric_limits::max(); + +namespace { +/// StratifiedInfo Attribute things. +LLVM_CONSTEXPR unsigned MaxStratifiedAttrIndex = NumStratifiedAttrs; +LLVM_CONSTEXPR unsigned AttrEscapedIndex = 0; +LLVM_CONSTEXPR unsigned AttrUnknownIndex = 1; +LLVM_CONSTEXPR unsigned AttrGlobalIndex = 2; +LLVM_CONSTEXPR unsigned AttrCallerIndex = 3; +LLVM_CONSTEXPR unsigned AttrFirstArgIndex = 4; +LLVM_CONSTEXPR unsigned AttrLastArgIndex = MaxStratifiedAttrIndex; +LLVM_CONSTEXPR unsigned AttrMaxNumArgs = AttrLastArgIndex - AttrFirstArgIndex; + +// NOTE: These aren't StratifiedAttrs because bitsets don't have a constexpr +// ctor for some versions of MSVC that we support. We could maybe refactor, +// but... +using StratifiedAttr = unsigned; +LLVM_CONSTEXPR StratifiedAttr AttrNone = 0; +LLVM_CONSTEXPR StratifiedAttr AttrEscaped = 1 << AttrEscapedIndex; +LLVM_CONSTEXPR StratifiedAttr AttrUnknown = 1 << AttrUnknownIndex; +LLVM_CONSTEXPR StratifiedAttr AttrGlobal = 1 << AttrGlobalIndex; +LLVM_CONSTEXPR StratifiedAttr AttrCaller = 1 << AttrCallerIndex; +LLVM_CONSTEXPR StratifiedAttr ExternalAttrMask = + AttrEscaped | AttrUnknown | AttrGlobal; + +/// The maximum number of arguments we can put into a summary. +LLVM_CONSTEXPR unsigned MaxSupportedArgsInSummary = 50; + +/// StratifiedSets call for knowledge of "direction", so this is how we +/// represent that locally. +enum class Level { Same, Above, Below }; + +/// Edges can be one of four "weights" -- each weight must have an inverse +/// weight (Assign has Assign; Reference has Dereference). +enum class EdgeType { + /// The weight assigned when assigning from or to a value. For example, in: + /// %b = getelementptr %a, 0 + /// ...The relationships are %b assign %a, and %a assign %b. This used to be + /// two edges, but having a distinction bought us nothing. + Assign, + + /// The edge used when we have an edge going from some handle to a Value. + /// Examples of this include: + /// %b = load %a (%b Dereference %a) + /// %b = extractelement %a, 0 (%a Dereference %b) + Dereference, + + /// The edge used when our edge goes from a value to a handle that may have + /// contained it at some point. Examples: + /// %b = load %a (%a Reference %b) + /// %b = extractelement %a, 0 (%b Reference %a) + Reference +}; + +/// The Program Expression Graph (PEG) of CFL analysis +class CFLGraph { + typedef Value *Node; + + struct Edge { + EdgeType Type; + Node Other; + }; + + typedef std::vector EdgeList; + + struct NodeInfo { + EdgeList Edges; + StratifiedAttrs Attr; + }; + + typedef DenseMap NodeMap; + NodeMap NodeImpls; + + // Gets the inverse of a given EdgeType. + static EdgeType flipWeight(EdgeType Initial) { + switch (Initial) { + case EdgeType::Assign: + return EdgeType::Assign; + case EdgeType::Dereference: + return EdgeType::Reference; + case EdgeType::Reference: + return EdgeType::Dereference; + } + llvm_unreachable("Incomplete coverage of EdgeType enum"); + } + + const NodeInfo *getNode(Node N) const { + auto Itr = NodeImpls.find(N); + if (Itr == NodeImpls.end()) + return nullptr; + return &Itr->second; + } + NodeInfo *getNode(Node N) { + auto Itr = NodeImpls.find(N); + if (Itr == NodeImpls.end()) + return nullptr; + return &Itr->second; + } + + static Node nodeDeref(const NodeMap::value_type &P) { return P.first; } + typedef std::pointer_to_unary_function + NodeDerefFun; + +public: + typedef EdgeList::const_iterator const_edge_iterator; + typedef mapped_iterator + const_node_iterator; + + bool addNode(Node N) { + return NodeImpls.insert(std::make_pair(N, NodeInfo{EdgeList(), AttrNone})) + .second; + } + + void addAttr(Node N, StratifiedAttrs Attr) { + auto *Info = getNode(N); + assert(Info != nullptr); + Info->Attr |= Attr; + } + + void addEdge(Node From, Node To, EdgeType Type) { + auto *FromInfo = getNode(From); + assert(FromInfo != nullptr); + auto *ToInfo = getNode(To); + assert(ToInfo != nullptr); + + FromInfo->Edges.push_back(Edge{Type, To}); + ToInfo->Edges.push_back(Edge{flipWeight(Type), From}); + } + + StratifiedAttrs attrFor(Node N) const { + auto *Info = getNode(N); + assert(Info != nullptr); + return Info->Attr; + } + + iterator_range edgesFor(Node N) const { + auto *Info = getNode(N); + assert(Info != nullptr); + auto &Edges = Info->Edges; + return make_range(Edges.begin(), Edges.end()); + } + + iterator_range nodes() const { + return make_range( + map_iterator(NodeImpls.begin(), NodeDerefFun(nodeDeref)), + map_iterator(NodeImpls.end(), NodeDerefFun(nodeDeref))); + } + + bool empty() const { return NodeImpls.empty(); } + std::size_t size() const { return NodeImpls.size(); } +}; + +// This is the result of instantiating InterfaceValue at a particular callsite +struct InterprocNode { + Value *Val; + unsigned DerefLevel; +}; + +// Interprocedural assignment edges that CFLGraph may not easily model +struct InterprocEdge { + InterprocNode From, To; +}; + +// Interprocedural attribute tagging that CFLGraph may not easily model +struct InterprocAttr { + InterprocNode Node; + StratifiedAttrs Attr; +}; + +/// Gets the edges our graph should have, based on an Instruction* +class GetEdgesVisitor : public InstVisitor { + CFLSteensAAResult &AA; + const TargetLibraryInfo &TLI; + + CFLGraph &Graph; + SmallVectorImpl &ReturnValues; + SmallPtrSetImpl &Externals; + SmallPtrSetImpl &Escapes; + SmallVectorImpl &InterprocEdges; + SmallVectorImpl &InterprocAttrs; + + static bool hasUsefulEdges(ConstantExpr *CE) { + // ConstantExpr doesn't have terminators, invokes, or fences, so only needs + // to check for compares. + return CE->getOpcode() != Instruction::ICmp && + CE->getOpcode() != Instruction::FCmp; + } + + void addNode(Value *Val) { + if (!Graph.addNode(Val)) + return; + + if (isa(Val)) + Externals.insert(Val); + else if (auto CExpr = dyn_cast(Val)) + if (hasUsefulEdges(CExpr)) + visitConstantExpr(CExpr); + } + + void addNodeWithAttr(Value *Val, StratifiedAttrs Attr) { + addNode(Val); + Graph.addAttr(Val, Attr); + } + + void addEdge(Value *From, Value *To, EdgeType Type) { + if (!From->getType()->isPointerTy() || !To->getType()->isPointerTy()) + return; + addNode(From); + if (To != From) + addNode(To); + Graph.addEdge(From, To, Type); + } + +public: + GetEdgesVisitor(CFLSteensAAResult &AA, const TargetLibraryInfo &TLI, + CFLGraph &Graph, SmallVectorImpl &ReturnValues, + SmallPtrSetImpl &Externals, + SmallPtrSetImpl &Escapes, + SmallVectorImpl &InterprocEdges, + SmallVectorImpl &InterprocAttrs) + : AA(AA), TLI(TLI), Graph(Graph), ReturnValues(ReturnValues), + Externals(Externals), Escapes(Escapes), InterprocEdges(InterprocEdges), + InterprocAttrs(InterprocAttrs) {} + + void visitInstruction(Instruction &) { + llvm_unreachable("Unsupported instruction encountered"); + } + + void visitReturnInst(ReturnInst &Inst) { + if (auto RetVal = Inst.getReturnValue()) { + if (RetVal->getType()->isPointerTy()) { + addNode(RetVal); + ReturnValues.push_back(RetVal); + } + } + } + + void visitPtrToIntInst(PtrToIntInst &Inst) { + auto *Ptr = Inst.getOperand(0); + addNodeWithAttr(Ptr, AttrEscaped); + } + + void visitIntToPtrInst(IntToPtrInst &Inst) { + auto *Ptr = &Inst; + addNodeWithAttr(Ptr, AttrUnknown); + } + + void visitCastInst(CastInst &Inst) { + auto *Src = Inst.getOperand(0); + addEdge(Src, &Inst, EdgeType::Assign); + } + + void visitBinaryOperator(BinaryOperator &Inst) { + auto *Op1 = Inst.getOperand(0); + auto *Op2 = Inst.getOperand(1); + addEdge(Op1, &Inst, EdgeType::Assign); + addEdge(Op2, &Inst, EdgeType::Assign); + } + + void visitAtomicCmpXchgInst(AtomicCmpXchgInst &Inst) { + auto *Ptr = Inst.getPointerOperand(); + auto *Val = Inst.getNewValOperand(); + addEdge(Ptr, Val, EdgeType::Dereference); + } + + void visitAtomicRMWInst(AtomicRMWInst &Inst) { + auto *Ptr = Inst.getPointerOperand(); + auto *Val = Inst.getValOperand(); + addEdge(Ptr, Val, EdgeType::Dereference); + } + + void visitPHINode(PHINode &Inst) { + for (Value *Val : Inst.incoming_values()) + addEdge(Val, &Inst, EdgeType::Assign); + } + + void visitGetElementPtrInst(GetElementPtrInst &Inst) { + auto *Op = Inst.getPointerOperand(); + addEdge(Op, &Inst, EdgeType::Assign); + } + + void visitSelectInst(SelectInst &Inst) { + // Condition is not processed here (The actual statement producing + // the condition result is processed elsewhere). For select, the + // condition is evaluated, but not loaded, stored, or assigned + // simply as a result of being the condition of a select. + + auto *TrueVal = Inst.getTrueValue(); + auto *FalseVal = Inst.getFalseValue(); + addEdge(TrueVal, &Inst, EdgeType::Assign); + addEdge(FalseVal, &Inst, EdgeType::Assign); + } + + void visitAllocaInst(AllocaInst &Inst) { Graph.addNode(&Inst); } + + void visitLoadInst(LoadInst &Inst) { + auto *Ptr = Inst.getPointerOperand(); + auto *Val = &Inst; + addEdge(Val, Ptr, EdgeType::Reference); + } + + void visitStoreInst(StoreInst &Inst) { + auto *Ptr = Inst.getPointerOperand(); + auto *Val = Inst.getValueOperand(); + addEdge(Ptr, Val, EdgeType::Dereference); + } + + void visitVAArgInst(VAArgInst &Inst) { + // We can't fully model va_arg here. For *Ptr = Inst.getOperand(0), it does + // two things: + // 1. Loads a value from *((T*)*Ptr). + // 2. Increments (stores to) *Ptr by some target-specific amount. + // For now, we'll handle this like a landingpad instruction (by placing the + // result in its own group, and having that group alias externals). + addNodeWithAttr(&Inst, AttrUnknown); + } + + static bool isFunctionExternal(Function *Fn) { + return !Fn->hasExactDefinition(); + } + + bool tryInterproceduralAnalysis(CallSite CS, + const SmallVectorImpl &Fns) { + assert(Fns.size() > 0); + + if (CS.arg_size() > MaxSupportedArgsInSummary) + return false; + + // Exit early if we'll fail anyway + for (auto *Fn : Fns) { + if (isFunctionExternal(Fn) || Fn->isVarArg()) + return false; + // Fail if the caller does not provide enough arguments + assert(Fn->arg_size() <= CS.arg_size()); + auto &MaybeInfo = AA.ensureCached(Fn); + if (!MaybeInfo.hasValue()) + return false; + } + + auto InstantiateInterfaceIndex = [&CS](unsigned Index) { + auto Value = + (Index == 0) ? CS.getInstruction() : CS.getArgument(Index - 1); + return Value->getType()->isPointerTy() ? Value : nullptr; + }; + + for (auto *Fn : Fns) { + auto &FnInfo = AA.ensureCached(Fn); + assert(FnInfo.hasValue()); + + auto &RetParamRelations = FnInfo->getRetParamRelations(); + for (auto &Relation : RetParamRelations) { + auto FromVal = InstantiateInterfaceIndex(Relation.From.Index); + auto ToVal = InstantiateInterfaceIndex(Relation.To.Index); + if (FromVal && ToVal) { + auto FromLevel = Relation.From.DerefLevel; + auto ToLevel = Relation.To.DerefLevel; + InterprocEdges.push_back( + InterprocEdge{InterprocNode{FromVal, FromLevel}, + InterprocNode{ToVal, ToLevel}}); + } + } + + auto &RetParamAttributes = FnInfo->getRetParamAttributes(); + for (auto &Attribute : RetParamAttributes) { + if (auto Val = InstantiateInterfaceIndex(Attribute.IValue.Index)) { + InterprocAttrs.push_back(InterprocAttr{ + InterprocNode{Val, Attribute.IValue.DerefLevel}, Attribute.Attr}); + } + } + } + + return true; + } + + void visitCallSite(CallSite CS) { + auto Inst = CS.getInstruction(); + + // Make sure all arguments and return value are added to the graph first + for (Value *V : CS.args()) + addNode(V); + if (Inst->getType()->isPointerTy()) + addNode(Inst); + + // Check if Inst is a call to a library function that allocates/deallocates + // on the heap. Those kinds of functions do not introduce any aliases. + // TODO: address other common library functions such as realloc(), strdup(), + // etc. + if (isMallocLikeFn(Inst, &TLI) || isCallocLikeFn(Inst, &TLI) || + isFreeCall(Inst, &TLI)) + return; + + // TODO: Add support for noalias args/all the other fun function attributes + // that we can tack on. + SmallVector Targets; + if (getPossibleTargets(CS, Targets)) + if (tryInterproceduralAnalysis(CS, Targets)) + return; + + // Because the function is opaque, we need to note that anything + // could have happened to the arguments (unless the function is marked + // readonly or readnone), and that the result could alias just about + // anything, too (unless the result is marked noalias). + if (!CS.onlyReadsMemory()) + for (Value *V : CS.args()) { + if (V->getType()->isPointerTy()) + Escapes.insert(V); + } + + if (Inst->getType()->isPointerTy()) { + auto *Fn = CS.getCalledFunction(); + if (Fn == nullptr || !Fn->doesNotAlias(0)) + Graph.addAttr(Inst, AttrUnknown); + } + } + + /// Because vectors/aggregates are immutable and unaddressable, there's + /// nothing we can do to coax a value out of them, other than calling + /// Extract{Element,Value}. We can effectively treat them as pointers to + /// arbitrary memory locations we can store in and load from. + void visitExtractElementInst(ExtractElementInst &Inst) { + auto *Ptr = Inst.getVectorOperand(); + auto *Val = &Inst; + addEdge(Val, Ptr, EdgeType::Reference); + } + + void visitInsertElementInst(InsertElementInst &Inst) { + auto *Vec = Inst.getOperand(0); + auto *Val = Inst.getOperand(1); + addEdge(Vec, &Inst, EdgeType::Assign); + addEdge(&Inst, Val, EdgeType::Dereference); + } + + void visitLandingPadInst(LandingPadInst &Inst) { + // Exceptions come from "nowhere", from our analysis' perspective. + // So we place the instruction its own group, noting that said group may + // alias externals + addNodeWithAttr(&Inst, AttrUnknown); + } + + void visitInsertValueInst(InsertValueInst &Inst) { + auto *Agg = Inst.getOperand(0); + auto *Val = Inst.getOperand(1); + addEdge(Agg, &Inst, EdgeType::Assign); + addEdge(&Inst, Val, EdgeType::Dereference); + } + + void visitExtractValueInst(ExtractValueInst &Inst) { + auto *Ptr = Inst.getAggregateOperand(); + addEdge(&Inst, Ptr, EdgeType::Reference); + } + + void visitShuffleVectorInst(ShuffleVectorInst &Inst) { + auto *From1 = Inst.getOperand(0); + auto *From2 = Inst.getOperand(1); + addEdge(From1, &Inst, EdgeType::Assign); + addEdge(From2, &Inst, EdgeType::Assign); + } + + void visitConstantExpr(ConstantExpr *CE) { + switch (CE->getOpcode()) { + default: + llvm_unreachable("Unknown instruction type encountered!"); +// Build the switch statement using the Instruction.def file. +#define HANDLE_INST(NUM, OPCODE, CLASS) \ + case Instruction::OPCODE: \ + visit##OPCODE(*(CLASS *)CE); \ + break; +#include "llvm/IR/Instruction.def" + } + } +}; + +class CFLGraphBuilder { + // Input of the builder + CFLSteensAAResult &Analysis; + const TargetLibraryInfo &TLI; + + // Output of the builder + CFLGraph Graph; + SmallVector ReturnedValues; + + // Auxiliary structures used by the builder + SmallPtrSet ExternalValues; + SmallPtrSet EscapedValues; + SmallVector InterprocEdges; + SmallVector InterprocAttrs; + + // Helper functions + + // Determines whether or not we an instruction is useless to us (e.g. + // FenceInst) + static bool hasUsefulEdges(Instruction *Inst) { + bool IsNonInvokeRetTerminator = isa(Inst) && + !isa(Inst) && + !isa(Inst); + return !isa(Inst) && !isa(Inst) && + !IsNonInvokeRetTerminator; + } + + void addArgumentToGraph(Argument &Arg) { + if (Arg.getType()->isPointerTy()) { + Graph.addNode(&Arg); + ExternalValues.insert(&Arg); + } + } + + // Given an Instruction, this will add it to the graph, along with any + // Instructions that are potentially only available from said Instruction + // For example, given the following line: + // %0 = load i16* getelementptr ([1 x i16]* @a, 0, 0), align 2 + // addInstructionToGraph would add both the `load` and `getelementptr` + // instructions to the graph appropriately. + void addInstructionToGraph(Instruction &Inst) { + if (!hasUsefulEdges(&Inst)) + return; + + GetEdgesVisitor(Analysis, TLI, Graph, ReturnedValues, ExternalValues, + EscapedValues, InterprocEdges, InterprocAttrs) + .visit(Inst); + } + + // Builds the graph needed for constructing the StratifiedSets for the given + // function + void buildGraphFrom(Function &Fn) { + for (auto &Bb : Fn.getBasicBlockList()) + for (auto &Inst : Bb.getInstList()) + addInstructionToGraph(Inst); + + for (auto &Arg : Fn.args()) + addArgumentToGraph(Arg); + } + +public: + CFLGraphBuilder(CFLSteensAAResult &Analysis, const TargetLibraryInfo &TLI, + Function &Fn) + : Analysis(Analysis), TLI(TLI) { + buildGraphFrom(Fn); + } + + const CFLGraph &getCFLGraph() const { return Graph; } + const SmallVector &getReturnValues() const { + return ReturnedValues; + } + const SmallPtrSet &getExternalValues() const { + return ExternalValues; + } + const SmallPtrSet &getEscapedValues() const { + return EscapedValues; + } + const SmallVector &getInterprocEdges() const { + return InterprocEdges; + } + const SmallVector &getInterprocAttrs() const { + return InterprocAttrs; + } +}; +} + +//===----------------------------------------------------------------------===// +// Function declarations that require types defined in the namespace above +//===----------------------------------------------------------------------===// + +/// Given a StratifiedAttrs, returns true if it marks the corresponding values +/// as globals or arguments +static bool isGlobalOrArgAttr(StratifiedAttrs Attr); + +/// Given a StratifiedAttrs, returns true if the corresponding values come from +/// an unknown source (such as opaque memory or an integer cast) +static bool isUnknownAttr(StratifiedAttrs Attr); + +/// Given an argument number, returns the appropriate StratifiedAttr to set. +static StratifiedAttrs argNumberToAttr(unsigned ArgNum); + +/// Given a Value, potentially return which StratifiedAttr it maps to. +static Optional valueToAttr(Value *Val); + +/// Gets the "Level" that one should travel in StratifiedSets +/// given an EdgeType. +static Level directionOfEdgeType(EdgeType); + +/// Determines whether it would be pointless to add the given Value to our sets. +static bool canSkipAddingToSets(Value *Val); + +static Optional parentFunctionOfValue(Value *Val) { + if (auto *Inst = dyn_cast(Val)) { + auto *Bb = Inst->getParent(); + return Bb->getParent(); + } + + if (auto *Arg = dyn_cast(Val)) + return Arg->getParent(); + return None; +} + +static bool getPossibleTargets(CallSite CS, + SmallVectorImpl &Output) { + if (auto *Fn = CS.getCalledFunction()) { + Output.push_back(Fn); + return true; + } + + // TODO: If the call is indirect, we might be able to enumerate all potential + // targets of the call and return them, rather than just failing. + return false; +} + +static bool isGlobalOrArgAttr(StratifiedAttrs Attr) { + return Attr.reset(AttrEscapedIndex) + .reset(AttrUnknownIndex) + .reset(AttrCallerIndex) + .any(); +} + +static bool isUnknownAttr(StratifiedAttrs Attr) { + return Attr.test(AttrUnknownIndex) || Attr.test(AttrCallerIndex); +} + +static Optional valueToAttr(Value *Val) { + if (isa(Val)) + return StratifiedAttrs(AttrGlobal); + + if (auto *Arg = dyn_cast(Val)) + // Only pointer arguments should have the argument attribute, + // because things can't escape through scalars without us seeing a + // cast, and thus, interaction with them doesn't matter. + if (!Arg->hasNoAliasAttr() && Arg->getType()->isPointerTy()) + return argNumberToAttr(Arg->getArgNo()); + return None; +} + +static StratifiedAttrs argNumberToAttr(unsigned ArgNum) { + if (ArgNum >= AttrMaxNumArgs) + return AttrUnknown; + // N.B. MSVC complains if we use `1U` here, since StratifiedAttrs' ctor takes + // an unsigned long long. + return StratifiedAttrs(1ULL << (ArgNum + AttrFirstArgIndex)); +} + +static Level directionOfEdgeType(EdgeType Weight) { + switch (Weight) { + case EdgeType::Reference: + return Level::Above; + case EdgeType::Dereference: + return Level::Below; + case EdgeType::Assign: + return Level::Same; + } + llvm_unreachable("Incomplete switch coverage"); +} + +static bool canSkipAddingToSets(Value *Val) { + // Constants can share instances, which may falsely unify multiple + // sets, e.g. in + // store i32* null, i32** %ptr1 + // store i32* null, i32** %ptr2 + // clearly ptr1 and ptr2 should not be unified into the same set, so + // we should filter out the (potentially shared) instance to + // i32* null. + if (isa(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(Val) || + isa(Val) || + isa(Val); + return !CanStoreMutableData; + } + + return false; +} + +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. + if (Fn.arg_size() > MaxSupportedArgsInSummary) + return; + + DenseMap InterfaceMap; + + // Our intention here is to record all InterfaceValues that share the same + // StratifiedIndex in RetParamRelations. For each valid InterfaceValue, we + // have its StratifiedIndex scanned here and check if the index is presented + // in InterfaceMap: if it is not, we add the correspondence to the map; + // otherwise, an aliasing relation is found and we add it to + // RetParamRelations. + + auto AddToRetParamRelations = [&](unsigned InterfaceIndex, + StratifiedIndex SetIndex) { + unsigned Level = 0; + while (true) { + InterfaceValue CurrValue{InterfaceIndex, Level}; + + auto Itr = InterfaceMap.find(SetIndex); + if (Itr != InterfaceMap.end()) { + if (CurrValue != Itr->second) + RetParamRelations.push_back(ExternalRelation{CurrValue, Itr->second}); + break; + } + + auto &Link = Sets.getLink(SetIndex); + InterfaceMap.insert(std::make_pair(SetIndex, CurrValue)); + auto ExternalAttrs = Link.Attrs & StratifiedAttrs(ExternalAttrMask); + if (ExternalAttrs.any()) + RetParamAttributes.push_back( + ExternalAttribute{CurrValue, ExternalAttrs}); + + if (!Link.hasBelow()) + break; + + ++Level; + SetIndex = Link.Below; + } + }; + + // Populate RetParamRelations for return values + for (auto *RetVal : RetVals) { + assert(RetVal != nullptr); + assert(RetVal->getType()->isPointerTy()); + auto RetInfo = Sets.find(RetVal); + if (RetInfo.hasValue()) + AddToRetParamRelations(0, RetInfo->Index); + } + + // Populate RetParamRelations for parameters + unsigned I = 0; + for (auto &Param : Fn.args()) { + if (Param.getType()->isPointerTy()) { + auto ParamInfo = Sets.find(&Param); + if (ParamInfo.hasValue()) + AddToRetParamRelations(I + 1, ParamInfo->Index); + } + ++I; + } +} + +// Builds the graph + StratifiedSets for a function. +CFLSteensAAResult::FunctionInfo CFLSteensAAResult::buildSetsFrom(Function *Fn) { + CFLGraphBuilder GraphBuilder(*this, TLI, *Fn); + StratifiedSetsBuilder SetBuilder; + + auto &Graph = GraphBuilder.getCFLGraph(); + SmallVector Worklist; + for (auto Node : Graph.nodes()) + Worklist.push_back(Node); + + while (!Worklist.empty()) { + auto *CurValue = Worklist.pop_back_val(); + SetBuilder.add(CurValue); + if (canSkipAddingToSets(CurValue)) + continue; + + auto Attr = Graph.attrFor(CurValue); + SetBuilder.noteAttributes(CurValue, Attr); + + for (const auto &Edge : Graph.edgesFor(CurValue)) { + auto Label = Edge.Type; + auto *OtherValue = Edge.Other; + + if (canSkipAddingToSets(OtherValue)) + continue; + + bool Added; + switch (directionOfEdgeType(Label)) { + case Level::Above: + Added = SetBuilder.addAbove(CurValue, OtherValue); + break; + case Level::Below: + Added = SetBuilder.addBelow(CurValue, OtherValue); + break; + case Level::Same: + Added = SetBuilder.addWith(CurValue, OtherValue); + break; + } + + if (Added) + Worklist.push_back(OtherValue); + } + } + + // Special handling for globals and arguments + for (auto *External : GraphBuilder.getExternalValues()) { + SetBuilder.add(External); + auto Attr = valueToAttr(External); + if (Attr.hasValue()) { + SetBuilder.noteAttributes(External, *Attr); + if (*Attr == AttrGlobal) + SetBuilder.addAttributesBelow(External, 1, AttrUnknown); + else + SetBuilder.addAttributesBelow(External, 1, AttrCaller); + } + } + + // Special handling for interprocedural aliases + for (auto &Edge : GraphBuilder.getInterprocEdges()) { + auto FromVal = Edge.From.Val; + auto ToVal = Edge.To.Val; + SetBuilder.add(FromVal); + SetBuilder.add(ToVal); + SetBuilder.addBelowWith(FromVal, Edge.From.DerefLevel, ToVal, + Edge.To.DerefLevel); + } + + // Special handling for interprocedural attributes + for (auto &IPAttr : GraphBuilder.getInterprocAttrs()) { + auto Val = IPAttr.Node.Val; + SetBuilder.add(Val); + SetBuilder.addAttributesBelow(Val, IPAttr.Node.DerefLevel, IPAttr.Attr); + } + + // Special handling for opaque external functions + for (auto *Escape : GraphBuilder.getEscapedValues()) { + SetBuilder.add(Escape); + SetBuilder.noteAttributes(Escape, AttrEscaped); + SetBuilder.addAttributesBelow(Escape, 1, AttrUnknown); + } + + return FunctionInfo(*Fn, GraphBuilder.getReturnValues(), SetBuilder.build()); +} + +void CFLSteensAAResult::scan(Function *Fn) { + auto InsertPair = Cache.insert(std::make_pair(Fn, Optional())); + (void)InsertPair; + assert(InsertPair.second && + "Trying to scan a function that has already been cached"); + + // Note that we can't do Cache[Fn] = buildSetsFrom(Fn) here: the function call + // may get evaluated after operator[], potentially triggering a DenseMap + // resize and invalidating the reference returned by operator[] + auto FunInfo = buildSetsFrom(Fn); + Cache[Fn] = std::move(FunInfo); + + Handles.push_front(FunctionHandle(Fn, this)); +} + +void CFLSteensAAResult::evict(Function *Fn) { Cache.erase(Fn); } + +/// Ensures that the given function is available in the cache, and returns the +/// entry. +const Optional & +CFLSteensAAResult::ensureCached(Function *Fn) { + auto Iter = Cache.find(Fn); + if (Iter == Cache.end()) { + scan(Fn); + Iter = Cache.find(Fn); + assert(Iter != Cache.end()); + assert(Iter->second.hasValue()); + } + return Iter->second; +} + +AliasResult CFLSteensAAResult::query(const MemoryLocation &LocA, + const MemoryLocation &LocB) { + auto *ValA = const_cast(LocA.Ptr); + auto *ValB = const_cast(LocB.Ptr); + + if (!ValA->getType()->isPointerTy() || !ValB->getType()->isPointerTy()) + return NoAlias; + + Function *Fn = nullptr; + auto MaybeFnA = parentFunctionOfValue(ValA); + auto MaybeFnB = parentFunctionOfValue(ValB); + if (!MaybeFnA.hasValue() && !MaybeFnB.hasValue()) { + // The only times this is known to happen are when globals + InlineAsm are + // involved + DEBUG(dbgs() + << "CFLSteensAA: could not extract parent function information.\n"); + return MayAlias; + } + + if (MaybeFnA.hasValue()) { + Fn = *MaybeFnA; + assert((!MaybeFnB.hasValue() || *MaybeFnB == *MaybeFnA) && + "Interprocedural queries not supported"); + } else { + Fn = *MaybeFnB; + } + + assert(Fn != nullptr); + auto &MaybeInfo = ensureCached(Fn); + assert(MaybeInfo.hasValue()); + + auto &Sets = MaybeInfo->getStratifiedSets(); + auto MaybeA = Sets.find(ValA); + if (!MaybeA.hasValue()) + return MayAlias; + + auto MaybeB = Sets.find(ValB); + if (!MaybeB.hasValue()) + return MayAlias; + + auto SetA = *MaybeA; + auto SetB = *MaybeB; + auto AttrsA = Sets.getLink(SetA.Index).Attrs; + auto AttrsB = Sets.getLink(SetB.Index).Attrs; + + // If both values are local (meaning the corresponding set has attribute + // AttrNone or AttrEscaped), then we know that CFLSteensAA fully models them: + // they may-alias each other if and only if they are in the same set. + // If at least one value is non-local (meaning it either is global/argument or + // it comes from unknown sources like integer cast), the situation becomes a + // bit more interesting. We follow three general rules described below: + // - Non-local values may alias each other + // - AttrNone values do not alias any non-local values + // - AttrEscaped do not alias globals/arguments, but they may alias + // AttrUnknown values + if (SetA.Index == SetB.Index) + return MayAlias; + if (AttrsA.none() || AttrsB.none()) + return NoAlias; + if (isUnknownAttr(AttrsA) || isUnknownAttr(AttrsB)) + return MayAlias; + if (isGlobalOrArgAttr(AttrsA) && isGlobalOrArgAttr(AttrsB)) + return MayAlias; + return NoAlias; +} + +ModRefInfo CFLSteensAAResult::getArgModRefInfo(ImmutableCallSite CS, + unsigned ArgIdx) { + if (auto CalledFunc = CS.getCalledFunction()) { + auto &MaybeInfo = ensureCached(const_cast(CalledFunc)); + if (!MaybeInfo.hasValue()) + return MRI_ModRef; + auto &RetParamAttributes = MaybeInfo->getRetParamAttributes(); + auto &RetParamRelations = MaybeInfo->getRetParamRelations(); + + bool ArgAttributeIsWritten = + std::any_of(RetParamAttributes.begin(), RetParamAttributes.end(), + [ArgIdx](const ExternalAttribute &ExtAttr) { + return ExtAttr.IValue.Index == ArgIdx + 1; + }); + bool ArgIsAccessed = + std::any_of(RetParamRelations.begin(), RetParamRelations.end(), + [ArgIdx](const ExternalRelation &ExtRelation) { + return ExtRelation.To.Index == ArgIdx + 1 || + ExtRelation.From.Index == ArgIdx + 1; + }); + + return (!ArgIsAccessed && !ArgAttributeIsWritten) ? MRI_NoModRef + : MRI_ModRef; + } + + return MRI_ModRef; +} + +FunctionModRefBehavior +CFLSteensAAResult::getModRefBehavior(ImmutableCallSite CS) { + // If we know the callee, try analyzing it + if (auto CalledFunc = CS.getCalledFunction()) + return getModRefBehavior(CalledFunc); + + // Otherwise, be conservative + return FMRB_UnknownModRefBehavior; +} + +FunctionModRefBehavior CFLSteensAAResult::getModRefBehavior(const Function *F) { + assert(F != nullptr); + + // TODO: Remove the const_cast + auto &MaybeInfo = ensureCached(const_cast(F)); + if (!MaybeInfo.hasValue()) + return FMRB_UnknownModRefBehavior; + auto &RetParamAttributes = MaybeInfo->getRetParamAttributes(); + auto &RetParamRelations = MaybeInfo->getRetParamRelations(); + + // First, if any argument is marked Escpaed, Unknown or Global, anything may + // happen to them and thus we can't draw any conclusion. + if (!RetParamAttributes.empty()) + return FMRB_UnknownModRefBehavior; + + // Currently we don't (and can't) distinguish reads from writes in + // RetParamRelations. All we can say is whether there may be memory access or + // not. + if (RetParamRelations.empty()) + return FMRB_DoesNotAccessMemory; + + // Check if something beyond argmem gets touched. + bool AccessArgMemoryOnly = + std::all_of(RetParamRelations.begin(), RetParamRelations.end(), + [](const ExternalRelation &ExtRelation) { + // Both DerefLevels has to be 0, since we don't know which + // one is a read and which is a write. + return ExtRelation.From.DerefLevel == 0 && + ExtRelation.To.DerefLevel == 0; + }); + return AccessArgMemoryOnly ? FMRB_OnlyAccessesArgumentPointees + : FMRB_UnknownModRefBehavior; +} + +char CFLSteensAA::PassID; + +CFLSteensAAResult CFLSteensAA::run(Function &F, AnalysisManager &AM) { + return CFLSteensAAResult(AM.getResult(F)); +} + +char CFLSteensAAWrapperPass::ID = 0; +INITIALIZE_PASS(CFLSteensAAWrapperPass, "cfl-steens-aa", + "Unification-Based CFL Alias Analysis", false, true) + +ImmutablePass *llvm::createCFLSteensAAWrapperPass() { + return new CFLSteensAAWrapperPass(); +} + +CFLSteensAAWrapperPass::CFLSteensAAWrapperPass() : ImmutablePass(ID) { + initializeCFLSteensAAWrapperPassPass(*PassRegistry::getPassRegistry()); +} + +void CFLSteensAAWrapperPass::initializePass() { + auto &TLIWP = getAnalysis(); + Result.reset(new CFLSteensAAResult(TLIWP.getTLI())); +} + +void CFLSteensAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { + AU.setPreservesAll(); + AU.addRequired(); +} Index: llvm/trunk/lib/Analysis/CMakeLists.txt =================================================================== --- llvm/trunk/lib/Analysis/CMakeLists.txt +++ llvm/trunk/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: llvm/trunk/lib/CodeGen/TargetPassConfig.cpp =================================================================== --- llvm/trunk/lib/CodeGen/TargetPassConfig.cpp +++ llvm/trunk/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: llvm/trunk/lib/Passes/PassBuilder.cpp =================================================================== --- llvm/trunk/lib/Passes/PassBuilder.cpp +++ llvm/trunk/lib/Passes/PassBuilder.cpp @@ -24,7 +24,8 @@ #include "llvm/Analysis/BlockFrequencyInfo.h" #include "llvm/Analysis/BlockFrequencyInfoImpl.h" #include "llvm/Analysis/BranchProbabilityInfo.h" -#include "llvm/Analysis/CFLAliasAnalysis.h" +#include "llvm/Analysis/CFLAndersAliasAnalysis.h" +#include "llvm/Analysis/CFLSteensAliasAnalysis.h" #include "llvm/Analysis/CGSCCPassManager.h" #include "llvm/Analysis/CallGraph.h" #include "llvm/Analysis/DemandedBits.h" @@ -692,7 +693,8 @@ DebugLogging) || !PipelineText.empty()) return false; - MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM), DebugLogging)); + MPM.addPass( + createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM), DebugLogging)); return true; } Index: llvm/trunk/lib/Passes/PassRegistry.def =================================================================== --- llvm/trunk/lib/Passes/PassRegistry.def +++ llvm/trunk/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: llvm/trunk/lib/Transforms/IPO/PassManagerBuilder.cpp =================================================================== --- llvm/trunk/lib/Transforms/IPO/PassManagerBuilder.cpp +++ llvm/trunk/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: llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/arguments-globals.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/arguments-globals.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/arguments-globals.ll @@ -0,0 +1,20 @@ +; This testcase ensures that CFL AA gives conservative answers on variables +; that involve arguments. +; (Everything should alias everything, because args can alias globals, so the +; aliasing sets should of args+alloca+global should be combined) + +; RUN: opt < %s -disable-basicaa -cfl-steens-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s + +; CHECK: Function: test + +@g = external global i32 + +define void @test(i1 %c, i32* %arg1, i32* %arg2) { + ; CHECK: 15 Total Alias Queries Performed + ; CHECK: 0 no alias responses + %A = alloca i32, align 4 + %B = select i1 %c, i32* %arg1, i32* %arg2 + %C = select i1 %c, i32* @g, i32* %A + + ret void +} Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/arguments.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/arguments.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/arguments.ll @@ -0,0 +1,15 @@ +; This testcase ensures that CFL AA gives conservative answers on variables +; that involve arguments. + +; RUN: opt < %s -cfl-steens-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s + +; CHECK: Function: test + +define void @test(i1 %c, i32* %arg1, i32* %arg2) { + ; CHECK: 6 Total Alias Queries Performed + ; CHECK: 3 no alias responses + %a = alloca i32, align 4 + %b = select i1 %c, i32* %arg1, i32* %arg2 + + ret void +} Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/asm-global-bugfix.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/asm-global-bugfix.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/asm-global-bugfix.ll @@ -0,0 +1,16 @@ +; Test case for a bug where we would crash when we were requested to report +; whether two values that didn't belong to a function (i.e. two globals, etc) +; aliased. + +; RUN: opt < %s -cfl-steens-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s + +@G = private unnamed_addr constant [1 x i8] c"\00", align 1 + +; CHECK: Function: test_no_crash +; CHECK: 0 no alias responses +define void @test_no_crash() #0 { +entry: + call i8* asm "nop", "=r,r"( + i8* getelementptr inbounds ([1 x i8], [1 x i8]* @G, i64 0, i64 0)) + ret void +} Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/attr-escape.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/attr-escape.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/attr-escape.ll @@ -0,0 +1,94 @@ +; This testcase ensures that CFL AA handles escaped values no more conservative than it should + +; RUN: opt < %s -disable-basicaa -cfl-steens-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s + +; CHECK-LABEL: Function: test_local +; CHECK: NoAlias: i32* %a, i32* %b +; CHECK: MayAlias: i32* %a, i32* %aAlias +; CHECK: NoAlias: i32* %aAlias, i32* %b +define void @test_local() { + %a = alloca i32, align 4 + %b = alloca i32, align 4 + %aint = ptrtoint i32* %a to i64 + %aAlias = inttoptr i64 %aint to i32* + ret void +} + +; CHECK-LABEL: Function: test_global_param +; CHECK: NoAlias: i32* %a, i32** %x +; CHECK: MayAlias: i32* %a, i32* %xload +; CHECK: MayAlias: i32* %a, i32* %gload +; CHECK: MayAlias: i32* %gload, i32* %xload +; CHECK: MayAlias: i32** %x, i32** @ext_global +; CHECK: NoAlias: i32* %a, i32** @ext_global +@ext_global = external global i32* +define void @test_global_param(i32** %x) { + %a = alloca i32, align 4 + %aint = ptrtoint i32* %a to i64 + %xload = load i32*, i32** %x + %gload = load i32*, i32** @ext_global + ret void +} + +declare void @external_func(i32**) +; CHECK-LABEL: Function: test_external_call +; CHECK: NoAlias: i32* %b, i32* %x +; CHECK: NoAlias: i32* %b, i32** %a +; CHECK: MayAlias: i32* %c, i32* %x +; CHECK: MayAlias: i32* %c, i32** %a +; CHECK: NoAlias: i32* %b, i32* %c +define void @test_external_call(i32* %x) { + %a = alloca i32*, align 8 + %b = alloca i32, align 4 + call void @external_func(i32** %a) + %c = load i32*, i32** %a + ret void +} + +declare void @external_func_readonly(i32**) readonly +; CHECK-LABEL: Function: test_external_call_func_readonly +; CHECK: MayAlias: i32* %c, i32* %x +; CHECK: NoAlias: i32* %c, i32** %a +define void @test_external_call_func_readonly(i32* %x) { + %a = alloca i32*, align 8 + %b = alloca i32, align 4 + store i32* %x, i32** %a, align 4 + call void @external_func_readonly(i32** %a) + %c = load i32*, i32** %a + ret void +} + +; CHECK-LABEL: Function: test_external_call_callsite_readonly +; CHECK: MayAlias: i32* %c, i32* %x +; CHECK: NoAlias: i32* %c, i32** %a +define void @test_external_call_callsite_readonly(i32* %x) { + %a = alloca i32*, align 8 + %b = alloca i32, align 4 + store i32* %x, i32** %a, align 4 + call void @external_func(i32** %a) readonly + %c = load i32*, i32** %a + ret void +} + +declare i32* @external_func_normal_return(i32*) +; CHECK-LABEL: Function: test_external_call_normal_return +; CHECK: MayAlias: i32* %c, i32* %x +; CHECK: MayAlias: i32* %a, i32* %c +define void @test_external_call_normal_return(i32* %x) { + %a = alloca i32, align 8 + %b = alloca i32, align 4 + %c = call i32* @external_func_normal_return(i32* %a) + ret void +} + +declare noalias i32* @external_func_noalias_return(i32*) +; CHECK-LABEL: Function: test_external_call_noalias_return +; CHECK: NoAlias: i32* %c, i32* %x +; CHECK: NoAlias: i32* %a, i32* %c +define void @test_external_call_noalias_return(i32* %x) { + %a = alloca i32, align 8 + %b = alloca i32, align 4 + %c = call i32* @external_func_noalias_return(i32* %a) + ret void +} Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/basic-interproc.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/basic-interproc.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/basic-interproc.ll @@ -0,0 +1,22 @@ +; This testcase ensures that CFL AA won't be too conservative when trying to do +; interprocedural analysis on simple callee + +; RUN: opt < %s -disable-basicaa -cfl-steens-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s + +; CHECK-LABEL: Function: noop_callee +; CHECK: MayAlias: i32* %arg1, i32* %arg2 +define void @noop_callee(i32* %arg1, i32* %arg2) { + store i32 0, i32* %arg1 + store i32 0, i32* %arg2 + ret void +} +; CHECK-LABEL: Function: test_noop +; CHECK: NoAlias: i32* %a, i32* %b +define void @test_noop() { + %a = alloca i32, align 4 + %b = alloca i32, align 4 + call void @noop_callee(i32* %a, i32* %b) + + ret void +} Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/branch-alias.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/branch-alias.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/branch-alias.ll @@ -0,0 +1,73 @@ +; Makes sure that we give up on some pathological cases with inttoptr/ptrtoint +; +; @ptr_test was generated from the following C code: +; void ptr_test() { +; int* A; +; unsigned long RefCopy = 0; +; for (int i = 0; i < 8*sizeof(&A); ++i) { +; if ((unsigned long)&A & (1UL << i)) +; RefCopy |= 1UL << i; +; } +; +; int** AliasA1 = (int**)RefCopy; +; int* ShouldAliasA = *AliasA1; +; } + +; RUN: opt < %s -disable-basicaa -cfl-steens-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s + +; CHECK: Function: ptr_test +define void @ptr_test() #0 { + ; CHECK: MayAlias: i32** %A, i32** %ShouldAliasA + ; CHECK-NOT: %AliasA1 +entry: + %A = alloca i32*, align 8 + %RefCopy = alloca i64, align 8 + %i = alloca i32, align 4 + %AliasA1 = alloca i32**, align 8 + %ShouldAliasA = alloca i32*, align 8 + store i64 0, i64* %RefCopy, align 8 + store i32 0, i32* %i, align 4 + br label %for.cond + +for.cond: ; preds = %for.inc, %entry + %0 = load i32, i32* %i, align 4 + %conv = sext i32 %0 to i64 + %cmp = icmp ult i64 %conv, 64 + br i1 %cmp, label %for.body, label %for.end + +for.body: ; preds = %for.cond + %1 = ptrtoint i32** %A to i64 + %2 = load i32, i32* %i, align 4 + %sh_prom = zext i32 %2 to i64 + %shl = shl i64 1, %sh_prom + %and = and i64 %1, %shl + %tobool = icmp ne i64 %and, 0 + br i1 %tobool, label %if.then, label %if.end + +if.then: ; preds = %for.body + %3 = load i32, i32* %i, align 4 + %sh_prom2 = zext i32 %3 to i64 + %shl3 = shl i64 1, %sh_prom2 + %4 = load i64, i64* %RefCopy, align 8 + %or = or i64 %4, %shl3 + store i64 %or, i64* %RefCopy, align 8 + br label %if.end + +if.end: ; preds = %if.then, %for.body + br label %for.inc + +for.inc: ; preds = %if.end + %5 = load i32, i32* %i, align 4 + %inc = add nsw i32 %5, 1 + store i32 %inc, i32* %i, align 4 + br label %for.cond + +for.end: ; preds = %for.cond + %6 = load i64, i64* %RefCopy, align 8 + %7 = inttoptr i64 %6 to i32** + store i32** %7, i32*** %AliasA1, align 8 + %8 = load i32**, i32*** %AliasA1, align 8 + %9 = load i32*, i32** %8, align 8 + store i32* %9, i32** %ShouldAliasA, align 8 + ret void +} Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/const-expr-gep.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/const-expr-gep.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/const-expr-gep.ll @@ -0,0 +1,57 @@ +; This testcase consists of alias relations which should be completely +; resolvable by cfl-steens-aa, but require analysis of getelementptr constant exprs. +; Derived from BasicAA/2003-12-11-ConstExprGEP.ll + +; RUN: opt < %s -disable-basicaa -cfl-steens-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s + +%T = type { i32, [10 x i8] } + +@G = external global %T +@G2 = external global %T + +; TODO: Quite a few of these are MayAlias because we don't yet consider +; constant offsets in CFLSteensAA. If we start doing so, then we'll need to +; change these test cases + +; CHECK: Function: test +; CHECK: MayAlias: i32* %D, i32* %F +; CHECK: MayAlias: i32* %D, i8* %X +; CHECK: MayAlias: i32* %F, i8* %X +define void @test() { + %D = getelementptr %T, %T* @G, i64 0, i32 0 + %F = getelementptr i32, i32* getelementptr (%T, %T* @G, i64 0, i32 0), i64 0 + %X = getelementptr [10 x i8], [10 x i8]* getelementptr (%T, %T* @G, i64 0, i32 1), i64 0, i64 5 + + ret void +} + +; CHECK: Function: simplecheck +; CHECK: MayAlias: i32* %F, i32* %arg0 +; CHECK: MayAlias: i32* %H, i32* %arg0 +; CHECK: MayAlias: i32* %F, i32* %H +define void @simplecheck(i32* %arg0) { + %F = getelementptr i32, i32* getelementptr (%T, %T* @G, i64 0, i32 0), i64 0 + %H = getelementptr %T, %T* @G2, i64 0, i32 0 + + ret void +} + +; Ensure that CFLSteensAA properly identifies and handles escaping variables (i.e. +; globals) in nested ConstantExprs + +; CHECK: Function: checkNesting +; CHECK: MayAlias: i32* %A, i32* %arg0 + +%NestedT = type { [1 x [1 x i32]] } +@NT = external global %NestedT + +define void @checkNesting(i32* %arg0) { + %A = getelementptr [1 x i32], + [1 x i32]* getelementptr + ([1 x [1 x i32]], [1 x [1 x i32]]* getelementptr (%NestedT, %NestedT* @NT, i64 0, i32 0), + i64 0, + i32 0), + i64 0, + i32 0 + ret void +} Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/constant-over-index.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/constant-over-index.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/constant-over-index.ll @@ -0,0 +1,30 @@ +; RUN: opt < %s -cfl-steens-aa -aa-eval -print-all-alias-modref-info 2>&1 | FileCheck %s + +; CFL AA currently returns PartialAlias, BasicAA returns MayAlias, both seem +; acceptable (although we might decide that we don't want PartialAlias, and if +; so, we should update this test case accordingly). +; CHECK: {{PartialAlias|MayAlias}}: double* %p.0.i.0, double* %p3 + +; %p3 is equal to %p.0.i.0 on the second iteration of the loop, +; so MayAlias is needed. + +define void @foo([3 x [3 x double]]* noalias %p) { +entry: + %p3 = getelementptr [3 x [3 x double]], [3 x [3 x double]]* %p, i64 0, i64 0, i64 3 + br label %loop + +loop: + %i = phi i64 [ 0, %entry ], [ %i.next, %loop ] + + %p.0.i.0 = getelementptr [3 x [3 x double]], [3 x [3 x double]]* %p, i64 0, i64 %i, i64 0 + + store volatile double 0.0, double* %p3 + store volatile double 0.1, double* %p.0.i.0 + + %i.next = add i64 %i, 1 + %cmp = icmp slt i64 %i.next, 3 + br i1 %cmp, label %loop, label %exit + +exit: + ret void +} Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/empty.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/empty.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/empty.ll @@ -0,0 +1,12 @@ +; RUN: opt < %s -cfl-steens-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s + +target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64" + +; CHECK: Function: foo: +; CHECK-NEXT: NoAlias: {}* %p, {}* %q + +define void @foo({}* %p, {}* %q) { + store {} {}, {}* %p + store {} {}, {}* %q + ret void +} Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/full-store-partial-alias.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/full-store-partial-alias.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/full-store-partial-alias.ll @@ -0,0 +1,39 @@ +; RUN: opt -S -disable-basicaa -tbaa -cfl-steens-aa -gvn < %s | FileCheck -check-prefix=CFLSteensAA %s +; RUN: opt -S -disable-basicaa -tbaa -gvn < %s | FileCheck %s +; Adapted from the BasicAA full-store-partial-alias.ll test. + +; CFL AA could notice that the store stores to the entire %u object, +; so the %tmp5 load is PartialAlias with the store and suppress TBAA. +; FIXME: However, right now, CFLSteensAA cannot prove PartialAlias here +; Without CFL AA, TBAA should say that %tmp5 is NoAlias with the store. + +target datalayout = "e-p:64:64:64" + +%union.anon = type { double } + +@u = global %union.anon { double -2.500000e-01 }, align 8 +@endianness_test = global i64 1, align 8 + +define i32 @signbit(double %x) nounwind { +; FIXME: This would be ret i32 %tmp5.lobit if CFLSteensAA could prove PartialAlias +; CFLSteensAA: ret i32 0 +; CHECK: ret i32 0 +entry: + %u = alloca %union.anon, align 8 + %tmp9 = getelementptr inbounds %union.anon, %union.anon* %u, i64 0, i32 0 + store double %x, double* %tmp9, align 8, !tbaa !0 + %tmp2 = load i32, i32* bitcast (i64* @endianness_test to i32*), align 8, !tbaa !3 + %idxprom = sext i32 %tmp2 to i64 + %tmp4 = bitcast %union.anon* %u to [2 x i32]* + %arrayidx = getelementptr inbounds [2 x i32], [2 x i32]* %tmp4, i64 0, i64 %idxprom + %tmp5 = load i32, i32* %arrayidx, align 4, !tbaa !3 + %tmp5.lobit = lshr i32 %tmp5, 31 + ret i32 %tmp5.lobit +} + +!0 = !{!4, !4, i64 0} +!1 = !{!"omnipotent char", !2} +!2 = !{!"Simple C/C++ TBAA", null} +!3 = !{!5, !5, i64 0} +!4 = !{!"double", !1} +!5 = !{!"int", !1} Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/gep-index-no-alias.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/gep-index-no-alias.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/gep-index-no-alias.ll @@ -0,0 +1,14 @@ +; This testcase ensures that gep result does not alias gep indices + +; RUN: opt < %s -disable-basicaa -cfl-steens-aa -aa-eval -print-no-aliases -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-no-aliases -disable-output 2>&1 | FileCheck %s + +; CHECK: Function: foo +; CHECK: [2 x i32]* %a, [2 x i32]* %b +define void @foo(i32 %n) { + %a = alloca [2 x i32], align 4 + %b = alloca [2 x i32], align 4 + %c = getelementptr inbounds [2 x i32], [2 x i32]* %a, i32 0, i32 %n + %d = getelementptr inbounds [2 x i32], [2 x i32]* %b, i32 0, i32 %n + ret void +} Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/gep-signed-arithmetic.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/gep-signed-arithmetic.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/gep-signed-arithmetic.ll @@ -0,0 +1,19 @@ +; RUN: opt < %s -disable-basicaa -cfl-steens-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +; Derived from BasicAA/2010-09-15-GEP-SignedArithmetic.ll + +target datalayout = "e-p:32:32:32" + +; FIXME: This could be PartialAlias but CFLSteensAA can't currently prove it +; CHECK: 1 may alias response + +define i32 @test(i32 %indvar) nounwind { + %tab = alloca i32, align 4 + %tmp31 = mul i32 %indvar, -2 + %tmp32 = add i32 %tmp31, 30 + %t.5 = getelementptr i32, i32* %tab, i32 %tmp32 + %loada = load i32, i32* %tab + store i32 0, i32* %t.5 + %loadb = load i32, i32* %tab + %rval = add i32 %loada, %loadb + ret i32 %rval +} Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-arg-deref-escape.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-arg-deref-escape.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-arg-deref-escape.ll @@ -0,0 +1,33 @@ +; This testcase ensures that CFL AA answers queries soundly when callee tries +; to escape the memory pointed to by its parameters + +; RUN: opt < %s -disable-basicaa -cfl-steens-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s + +declare void @opaque(i32*) +define void @escape_arg_deref(i32** %arg) { + %arg_deref = load i32*, i32** %arg + call void @opaque(i32* %arg_deref) + ret void +} +; CHECK-LABEL: Function: test_arg_deref_escape +; CHECK: NoAlias: i32* %a, i32** %x +; CHECK: NoAlias: i32* %b, i32** %x +; CHECK: NoAlias: i32* %a, i32* %b +; CHECK: NoAlias: i32** %p, i32** %x +; CHECK: NoAlias: i32* %a, i32** %p +; CHECK: NoAlias: i32* %b, i32** %p +; CHECK: MayAlias: i32* %a, i32* %c +; CHECK: NoAlias: i32* %b, i32* %c +; CHECK: NoAlias: i32* %c, i32** %p +define void @test_arg_deref_escape(i32** %x) { + %a = alloca i32, align 4 + %b = alloca i32, align 4 + %p = alloca i32*, align 4 + + store i32* %a, i32** %p + call void @escape_arg_deref(i32** %p) + %c = load i32*, i32** %x + + ret void +} \ No newline at end of file Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-arg-escape.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-arg-escape.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-arg-escape.ll @@ -0,0 +1,31 @@ +; This testcase ensures that CFL AA answers queries soundly when callee tries +; to escape its parameters + +; RUN: opt < %s -disable-basicaa -cfl-steens-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s + +declare void @opaque(i32*) +define void @escape_arg(i32* %arg) { + call void @opaque(i32* %arg) + ret void +} +; CHECK-LABEL: Function: test_arg_escape +; CHECK: NoAlias: i32* %a, i32** %x +; CHECK: NoAlias: i32* %b, i32** %x +; CHECK: NoAlias: i32* %a, i32* %b +; CHECK: NoAlias: i32* %c, i32** %x +; CHECK: NoAlias: i32* %a, i32* %c +; CHECK: NoAlias: i32* %b, i32* %c +; CHECK: MayAlias: i32* %a, i32* %d +; CHECK: MayAlias: i32* %b, i32* %d +; CHECK: NoAlias: i32* %c, i32* %d +define void @test_arg_escape(i32** %x) { + %a = alloca i32, align 4 + %b = alloca i32, align 4 + %c = alloca i32, align 4 + call void @escape_arg(i32* %a) + call void @escape_arg(i32* %b) + %d = load i32*, i32** %x + + ret void +} \ No newline at end of file Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-ret-arg.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-ret-arg.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-ret-arg.ll @@ -0,0 +1,23 @@ +; This testcase ensures that CFL AA answers queries soundly when callee tries +; to return one of its parameters + +; RUN: opt < %s -disable-basicaa -cfl-steens-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s + +define i32* @return_arg_callee(i32* %arg1, i32* %arg2) { + ret i32* %arg1 +} +; CHECK-LABEL: Function: test_return_arg +; CHECK: NoAlias: i32* %a, i32* %b +; CHECK: MayAlias: i32* %a, i32* %c +; CHECK: NoAlias: i32* %b, i32* %c + +; CHECK: NoModRef: Ptr: i32* %b <-> %c = call i32* @return_arg_callee(i32* %a, i32* %b) +define void @test_return_arg() { + %a = alloca i32, align 4 + %b = alloca i32, align 4 + + %c = call i32* @return_arg_callee(i32* %a, i32* %b) + + ret void +} \ No newline at end of file Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-ret-deref-arg-multilevel.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-ret-deref-arg-multilevel.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-ret-deref-arg-multilevel.ll @@ -0,0 +1,46 @@ +; This testcase ensures that CFL AA answers queries soundly when callee tries +; to return the multi-level dereference of one of its parameters + +; RUN: opt < %s -disable-basicaa -cfl-steens-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s + +define i32* @return_deref_arg_multilevel_callee(i32*** %arg1) { + %deref = load i32**, i32*** %arg1 + %deref2 = load i32*, i32** %deref + ret i32* %deref2 +} +; CHECK-LABEL: Function: test_return_deref_arg_multilevel +; CHECK: NoAlias: i32* %a, i32* %b +; CHECK: MayAlias: i32* %a, i32* %c +; CHECK: NoAlias: i32* %b, i32* %c +; CHECK: NoAlias: i32* %c, i32** %p +; CHECK: NoAlias: i32* %c, i32*** %pp +; CHECK: MayAlias: i32** %lpp, i32** %p +; CHECK: NoAlias: i32** %lpp, i32*** %pp +; CHECK: NoAlias: i32* %c, i32** %lpp +; CHECK: MayAlias: i32* %a, i32* %lpp_deref +; CHECK: NoAlias: i32* %b, i32* %lpp_deref +; CHECK: NoAlias: i32* %lpp_deref, i32*** %pp +; CHECK: MayAlias: i32* %a, i32* %lp +; CHECK: NoAlias: i32* %b, i32* %lp +; CHECK: NoAlias: i32* %lp, i32** %p +; CHECK: NoAlias: i32* %lp, i32*** %pp +; CHECK: MayAlias: i32* %c, i32* %lp +; CHECK: NoAlias: i32* %lp, i32** %lpp +; CHECK: MayAlias: i32* %lp, i32* %lpp_deref +define void @test_return_deref_arg_multilevel() { + %a = alloca i32, align 4 + %b = alloca i32, align 4 + %p = alloca i32*, align 8 + %pp = alloca i32**, align 8 + + store i32* %a, i32** %p + store i32** %p, i32*** %pp + %c = call i32* @return_deref_arg_multilevel_callee(i32*** %pp) + + %lpp = load i32**, i32*** %pp + %lpp_deref = load i32*, i32** %lpp + %lp = load i32*, i32** %p + + ret void +} \ No newline at end of file Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-ret-deref-arg.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-ret-deref-arg.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-ret-deref-arg.ll @@ -0,0 +1,30 @@ +; This testcase ensures that CFL AA answers queries soundly when callee tries +; to return the dereference of one of its parameters + +; RUN: opt < %s -disable-basicaa -cfl-steens-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s + +define i32* @return_deref_arg_callee(i32** %arg1) { + %deref = load i32*, i32** %arg1 + ret i32* %deref +} +; CHECK-LABEL: Function: test_return_deref_arg +; CHECK: NoAlias: i32* %a, i32* %b +; CHECK: MayAlias: i32* %a, i32* %c +; CHECK: NoAlias: i32* %b, i32* %c +; CHECK: MayAlias: i32* %a, i32* %lp +; CHECK: NoAlias: i32* %b, i32* %lp +; CHECK: NoAlias: i32* %lp, i32** %p +; CHECK: MayAlias: i32* %c, i32* %lp +define void @test_return_deref_arg() { + %a = alloca i32, align 4 + %b = alloca i32, align 4 + %p = alloca i32*, align 8 + + store i32* %a, i32** %p + %c = call i32* @return_deref_arg_callee(i32** %p) + + %lp = load i32*, i32** %p + + ret void +} \ No newline at end of file Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-ret-escape.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-ret-escape.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-ret-escape.ll @@ -0,0 +1,33 @@ +; This testcase ensures that CFL AA answers queries soundly when callee tries +; to return an escaped pointer + +; RUN: opt < %s -disable-basicaa -cfl-steens-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s + +declare noalias i8* @malloc(i64) +declare void @opaque(i32*) + +define i32* @return_escaped_callee() { + %ptr = call noalias i8* @malloc(i64 8) + %ptr_cast = bitcast i8* %ptr to i32* + call void @opaque(i32* %ptr_cast) + ret i32* %ptr_cast +} +; CHECK-LABEL: Function: test_return_escape +; CHECK: NoAlias: i32* %a, i32** %x +; CHECK: NoAlias: i32* %b, i32** %x +; CHECK: NoAlias: i32* %a, i32* %b +; CHECK: NoAlias: i32* %c, i32** %x +; CHECK: NoAlias: i32* %a, i32* %c +; CHECK: NoAlias: i32* %b, i32* %c +; CHECK: NoAlias: i32* %a, i32* %d +; CHECK: MayAlias: i32* %b, i32* %d +; CHECK: MayAlias: i32* %c, i32* %d +define void @test_return_escape(i32** %x) { + %a = alloca i32, align 4 + %b = call i32* @return_escaped_callee() + %c = call i32* @return_escaped_callee() + %d = load i32*, i32** %x + + ret void +} \ No newline at end of file Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-ret-ref-arg-multilevel.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-ret-ref-arg-multilevel.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-ret-ref-arg-multilevel.ll @@ -0,0 +1,51 @@ +; This testcase ensures that CFL AA answers queries soundly when callee tries +; to return the multi-level reference of one of its parameters + +; RUN: opt < %s -disable-basicaa -cfl-steens-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s + +declare noalias i8* @malloc(i64) + +define i32*** @return_ref_arg_multilevel_callee(i32* %arg1) { + %ptr = call noalias i8* @malloc(i64 8) + %ptr_cast = bitcast i8* %ptr to i32*** + %ptr2 = call noalias i8* @malloc(i64 8) + %ptr_cast2 = bitcast i8* %ptr2 to i32** + store i32* %arg1, i32** %ptr_cast2 + store i32** %ptr_cast2, i32*** %ptr_cast + ret i32*** %ptr_cast +} +; CHECK-LABEL: Function: test_return_ref_arg_multilevel +; CHECK: NoAlias: i32* %a, i32*** %b +; CHECK: NoAlias: i32** %p, i32*** %b +; CHECK: NoAlias: i32* %a, i32** %lb +; CHECK: NoAlias: i32** %lb, i32*** %pp +; CHECK: NoAlias: i32** %lb, i32*** %b +; CHECK: MayAlias: i32* %a, i32* %lb_deref +; CHECK: NoAlias: i32* %lb_deref, i32** %lpp +; CHECK: MayAlias: i32* %lb_deref, i32* %lpp_deref +; CHECK: NoAlias: i32* %lpp_deref, i32** %lpp +; CHECK: MayAlias: i32* %lb_deref, i32* %lp +; CHECK: NoAlias: i32* %lp, i32** %lpp +; CHECK: MayAlias: i32* %lp, i32* %lpp_deref + +; We could've proven the following facts if the analysis were inclusion-based: +; NoAlias: i32*** %b, i32*** %pp +; NoAlias: i32** %lb, i32** %p +define void @test_return_ref_arg_multilevel() { + %a = alloca i32, align 4 + %p = alloca i32*, align 8 + %pp = alloca i32**, align 8 + + store i32* %a, i32** %p + store i32** %p, i32*** %pp + %b = call i32*** @return_ref_arg_multilevel_callee(i32* %a) + + %lb = load i32**, i32*** %b + %lb_deref = load i32*, i32** %lb + %lpp = load i32**, i32*** %pp + %lpp_deref = load i32*, i32** %lpp + %lp = load i32*, i32** %p + + ret void +} \ No newline at end of file Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-ret-ref-arg.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-ret-ref-arg.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-ret-ref-arg.ll @@ -0,0 +1,36 @@ +; This testcase ensures that CFL AA answers queries soundly when callee tries +; to return the reference of one of its parameters + +; RUN: opt < %s -disable-basicaa -cfl-steens-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s + +declare noalias i8* @malloc(i64) + +define i32** @return_ref_arg_callee(i32* %arg1) { + %ptr = call noalias i8* @malloc(i64 8) + %ptr_cast = bitcast i8* %ptr to i32** + store i32* %arg1, i32** %ptr_cast + ret i32** %ptr_cast +} +; CHECK-LABEL: Function: test_return_ref_arg +; CHECK: MayAlias: i32* %a, i32* %lb +; CHECK: NoAlias: i32* %lb, i32** %p +; CHECK: NoAlias: i32* %lb, i32** %b +; CHECK: NoAlias: i32* %lp, i32** %p +; CHECK: NoAlias: i32* %lp, i32** %b +; CHECK: MayAlias: i32* %lb, i32* %lp + +; We could've proven the following facts if the analysis were inclusion-based: +; NoAlias: i32** %b, i32** %p +define void @test_return_ref_arg() { + %a = alloca i32, align 4 + %p = alloca i32*, align 8 + + store i32* %a, i32** %p + %b = call i32** @return_ref_arg_callee(i32* %a) + + %lb = load i32*, i32** %b + %lp = load i32*, i32** %p + + ret void +} \ No newline at end of file Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-ret-unknown.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-ret-unknown.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-ret-unknown.ll @@ -0,0 +1,38 @@ +; This testcase ensures that CFL AA answers queries soundly when callee tries +; to return an unknown pointer + +; RUN: opt < %s -disable-basicaa -cfl-steens-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s + +@g = external global i32 +define i32* @return_unknown_callee(i32* %arg1, i32* %arg2) { + ret i32* @g +} +; CHECK-LABEL: Function: test_return_unknown +; CHECK: NoAlias: i32* %a, i32* %b +; CHECK: MayAlias: i32* %c, i32* %x +; CHECK: NoAlias: i32* %a, i32* %c +; CHECK: NoAlias: i32* %b, i32* %c +define void @test_return_unknown(i32* %x) { + %a = alloca i32, align 4 + %b = alloca i32, align 4 + + %c = call i32* @return_unknown_callee(i32* %a, i32* %b) + + ret void +} + +@g2 = external global i32* +define i32** @return_unknown_callee2() { + ret i32** @g2 +} +; CHECK-LABEL: Function: test_return_unknown2 +; CHECK: MayAlias: i32* %x, i32** %a +; CHECK: MayAlias: i32* %b, i32* %x +; CHECK: MayAlias: i32* %b, i32** %a +define void @test_return_unknown2(i32* %x) { + %a = call i32** @return_unknown_callee2() + %b = load i32*, i32** %a + + ret void +} \ No newline at end of file Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-store-arg-multilevel.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-store-arg-multilevel.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-store-arg-multilevel.ll @@ -0,0 +1,48 @@ +; This testcase ensures that CFL AA answers queries soundly when callee tries +; to mutate the memory pointed to by its parameters + +; RUN: opt < %s -disable-basicaa -cfl-steens-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s + +declare noalias i8* @malloc(i64) + +define void @store_arg_multilevel_callee(i32*** %arg1, i32* %arg2) { + %ptr = call noalias i8* @malloc(i64 8) + %ptr_cast = bitcast i8* %ptr to i32** + store i32* %arg2, i32** %ptr_cast + store i32** %ptr_cast, i32*** %arg1 + ret void +} +; CHECK-LABEL: Function: test_store_arg_multilevel +; CHECK: NoAlias: i32* %a, i32** %lpp +; CHECK: NoAlias: i32* %b, i32** %lpp +; CHECK: MayAlias: i32** %lpp, i32** %p +; CHECK: MayAlias: i32* %a, i32* %lpp_deref +; CHECK: MayAlias: i32* %b, i32* %lpp_deref +; CHECK: NoAlias: i32* %lpp_deref, i32** %p +; CHECK: NoAlias: i32* %lpp_deref, i32*** %pp +; CHECK: NoAlias: i32* %lpp_deref, i32** %lpp +; CHECK: MayAlias: i32* %a, i32* %lp +; CHECK: NoAlias: i32* %lp, i32*** %pp +; CHECK: NoAlias: i32* %lp, i32** %lpp +; CHECK: MayAlias: i32* %lp, i32* %lpp_deref + +; We could've proven the following facts if the analysis were inclusion-based: +; NoAlias: i32* %a, i32* %b +; NoAlias: i32* %b, i32* %lp +define void @test_store_arg_multilevel() { + %a = alloca i32, align 4 + %b = alloca i32, align 4 + %p = alloca i32*, align 8 + %pp = alloca i32**, align 8 + + store i32* %a, i32** %p + store i32** %p, i32*** %pp + call void @store_arg_multilevel_callee(i32*** %pp, i32* %b) + + %lpp = load i32**, i32*** %pp + %lpp_deref = load i32*, i32** %lpp + %lp = load i32*, i32** %p + + ret void +} \ No newline at end of file Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-store-arg-unknown.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-store-arg-unknown.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-store-arg-unknown.ll @@ -0,0 +1,32 @@ +; This testcase ensures that CFL AA answers queries soundly when callee tries +; to mutate the memory pointed to by its parameters + +; RUN: opt < %s -disable-basicaa -cfl-steens-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s + +@g = external global i32 + +define void @store_arg_unknown_callee(i32** %arg1) { + store i32* @g, i32** %arg1 + ret void +} +; CHECK-LABEL: Function: test_store_arg_unknown +; CHECK: NoAlias: i32* %x, i32** %p +; CHECK: NoAlias: i32* %a, i32** %p +; CHECK: NoAlias: i32* %b, i32** %p +; CHECK: MayAlias: i32* %lp, i32* %x +; CHECK: MayAlias: i32* %a, i32* %lp +; CHECK: NoAlias: i32* %b, i32* %lp +; CHECK: NoAlias: i32* %lp, i32** %p +define void @test_store_arg_unknown(i32* %x) { + %a = alloca i32, align 4 + %b = alloca i32, align 4 + %p = alloca i32*, align 8 + + store i32* %a, i32** %p + call void @store_arg_unknown_callee(i32** %p) + + %lp = load i32*, i32** %p + + ret void +} \ No newline at end of file Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-store-arg.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-store-arg.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-store-arg.ll @@ -0,0 +1,36 @@ +; This testcase ensures that CFL AA answers queries soundly when callee tries +; to mutate the memory pointed to by its parameters + +; RUN: opt < %s -disable-basicaa -cfl-steens-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s + +define void @store_arg_callee(i32** %arg1, i32* %arg2) { + store i32* %arg2, i32** %arg1 + ret void +} +; CHECK-LABEL: Function: test_store_arg +; CHECK: NoAlias: i32* %a, i32** %p +; CHECK: NoAlias: i32* %b, i32** %p +; CHECK: MayAlias: i32* %a, i32* %lp +; CHECK: MayAlias: i32* %b, i32* %lp +; CHECK: MayAlias: i32* %b, i32* %lq +; CHECK: MayAlias: i32* %lp, i32* %lq + +; We could've proven the following facts if the analysis were inclusion-based: +; NoAlias: i32* %a, i32* %b +; NoAlias: i32* %a, i32* %lq +define void @test_store_arg() { + %a = alloca i32, align 4 + %b = alloca i32, align 4 + %p = alloca i32*, align 8 + %q = alloca i32*, align 8 + + store i32* %a, i32** %p + store i32* %b, i32** %q + call void @store_arg_callee(i32** %p, i32* %b) + + %lp = load i32*, i32** %p + %lq = load i32*, i32** %q + + ret void +} \ No newline at end of file Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/malloc-and-free.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/malloc-and-free.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/malloc-and-free.ll @@ -0,0 +1,30 @@ +; This testcase ensures that CFL AA handles malloc and free in a sound and precise manner + +; RUN: opt < %s -disable-basicaa -cfl-steens-aa -aa-eval -print-no-aliases -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-no-aliases -disable-output 2>&1 | FileCheck %s + +declare noalias i8* @malloc(i64) +declare noalias i8* @calloc(i64, i64) +declare void @free(i8* nocapture) + +; CHECK: Function: test_malloc +; CHECK: NoAlias: i8* %p, i8* %q +define void @test_malloc(i8* %p) { + %q = call i8* @malloc(i64 4) + ret void +} + +; CHECK: Function: test_calloc +; CHECK: NoAlias: i8* %p, i8* %q +define void @test_calloc(i8* %p) { + %q = call i8* @calloc(i64 2, i64 4) + ret void +} + +; CHECK: Function: test_free +; CHECK: NoAlias: i8* %p, i8* %q +define void @test_free(i8* %p) { + %q = alloca i8, align 4 + call void @free(i8* %q) + ret void +} Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/multilevel-combine.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/multilevel-combine.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/multilevel-combine.ll @@ -0,0 +1,31 @@ +; This testcase ensures that CFL AA responds conservatively when we union +; groups of pointers together through ternary/conditional operations +; Derived from: +; void foo(bool c) { +; char a, b; +; char *m = c ? &a : &b; +; *m; +; } +; + +; RUN: opt < %s -disable-basicaa -cfl-steens-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s + +%T = type { i32, [10 x i8] } + +; CHECK: Function: test + +define void @test(i1 %C) { +; CHECK: 10 Total Alias Queries Performed +; CHECK: 4 no alias responses + %M = alloca %T*, align 8 ; NoAlias with %A, %B, %MS, %AP + %A = alloca %T, align 8 + %B = alloca %T, align 8 + + %MS = select i1 %C, %T* %B, %T* %A + + store %T* %MS, %T** %M + + %AP = load %T*, %T** %M ; PartialAlias with %A, %B + + ret void +} Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/multilevel.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/multilevel.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/multilevel.ll @@ -0,0 +1,30 @@ +; This testcase ensures that CFL AA handles trivial cases with storing +; pointers in pointers appropriately. +; Derived from: +; char a, b; +; char *m = &a, *n = &b; +; *m; +; *n; + +; RUN: opt < %s -cfl-steens-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s + +%T = type { i32, [10 x i8] } + +; CHECK: Function: test + +define void @test() { +; CHECK: 15 Total Alias Queries Performed +; CHECK: 13 no alias responses + %M = alloca %T*, align 8 + %N = alloca %T*, align 8 + %A = alloca %T, align 8 + %B = alloca %T, align 8 + + store %T* %A, %T** %M + store %T* %B, %T** %N + + %AP = load %T*, %T** %M ; PartialAlias with %A + %BP = load %T*, %T** %N ; PartialAlias with %B + + ret void +} Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/must-and-partial.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/must-and-partial.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/must-and-partial.ll @@ -0,0 +1,54 @@ +; RUN: opt < %s -disable-basicaa -cfl-steens-aa -aa-eval -print-all-alias-modref-info 2>&1 | FileCheck %s +; When merging MustAlias and PartialAlias, merge to PartialAlias +; instead of MayAlias. + + +target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64" + +; FIXME: This could be PartialAlias but CFLSteensAA can't currently prove it +; CHECK: MayAlias: i16* %bigbase0, i8* %phi +define i8 @test0(i1 %x) { +entry: + %base = alloca i8, align 4 + %baseplusone = getelementptr i8, i8* %base, i64 1 + br i1 %x, label %red, label %green +red: + br label %green +green: + %phi = phi i8* [ %baseplusone, %red ], [ %base, %entry ] + store i8 0, i8* %phi + + %bigbase0 = bitcast i8* %base to i16* + store i16 -1, i16* %bigbase0 + + %loaded = load i8, i8* %phi + ret i8 %loaded +} + +; FIXME: This could be PartialAlias but CFLSteensAA can't currently prove it +; CHECK: MayAlias: i16* %bigbase1, i8* %sel +define i8 @test1(i1 %x) { +entry: + %base = alloca i8, align 4 + %baseplusone = getelementptr i8, i8* %base, i64 1 + %sel = select i1 %x, i8* %baseplusone, i8* %base + store i8 0, i8* %sel + + %bigbase1 = bitcast i8* %base to i16* + store i16 -1, i16* %bigbase1 + + %loaded = load i8, i8* %sel + ret i8 %loaded +} + +; Incoming pointer arguments should not be PartialAlias because we do not know their initial state +; even if they are nocapture +; CHECK: MayAlias: double* %A, double* %Index +define void @testr2(double* nocapture readonly %A, double* nocapture readonly %Index) { + %arrayidx22 = getelementptr inbounds double, double* %Index, i64 2 + %1 = load double, double* %arrayidx22 + %arrayidx25 = getelementptr inbounds double, double* %A, i64 2 + %2 = load double, double* %arrayidx25 + %mul26 = fmul double %1, %2 + ret void +} Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/opaque-call-alias.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/opaque-call-alias.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/opaque-call-alias.ll @@ -0,0 +1,20 @@ +; We previously had a case where we would put results from a no-args call in +; its own stratified set. This would make cases like the one in @test say that +; nothing (except %Escapes and %Arg) can alias + +; RUN: opt < %s -disable-basicaa -cfl-steens-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s + +; CHECK: Function: test +; CHECK: NoAlias: i8* %Arg, i8* %Escapes +; CHECK: MayAlias: i8* %Arg, i8* %Retrieved +; CHECK: MayAlias: i8* %Escapes, i8* %Retrieved +define void @test(i8* %Arg) { + %Noalias = alloca i8 + %Escapes = alloca i8 + call void @set_thepointer(i8* %Escapes) + %Retrieved = call i8* @get_thepointer() + ret void +} + +declare void @set_thepointer(i8* %P) +declare i8* @get_thepointer() Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/phi-and-select.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/phi-and-select.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/phi-and-select.ll @@ -0,0 +1,36 @@ +; RUN: opt < %s -cfl-steens-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +; Derived from (a subset of) BasicAA/phi-and-select.ll + +; CHECK: Function: qux +; CHECK: NoAlias: double* %a, double* %b +; CHECK: ===== Alias Analysis Evaluator Report ===== + +; Two PHIs with disjoint sets of inputs. +define void @qux(i1 %m, double* noalias %x, double* noalias %y, + i1 %n, double* noalias %v, double* noalias %w) { +entry: + br i1 %m, label %true, label %false + +true: + br label %exit + +false: + br label %exit + +exit: + %a = phi double* [ %x, %true ], [ %y, %false ] + br i1 %n, label %ntrue, label %nfalse + +ntrue: + br label %nexit + +nfalse: + br label %nexit + +nexit: + %b = phi double* [ %v, %ntrue ], [ %w, %nfalse ] + store volatile double 0.0, double* %a + store volatile double 1.0, double* %b + ret void +} + Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/pr27213.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/pr27213.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/pr27213.ll @@ -0,0 +1,39 @@ +; RUN: opt < %s -disable-basicaa -cfl-steens-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s + +; CHECK-LABEL: Function: foo +; CHECK: MayAlias: i32* %A, i32* %B +define void @foo(i32* %A, i32* %B) { +entry: + store i32 0, i32* %A, align 4 + store i32 0, i32* %B, align 4 + ret void +} + +; CHECK-LABEL: Function: bar +; CHECK: MayAlias: i32* %A, i32* %B +; CHECK: MayAlias: i32* %A, i32* %arrayidx +; CHECK: MayAlias: i32* %B, i32* %arrayidx +define void @bar(i32* %A, i32* %B) { +entry: + store i32 0, i32* %A, align 4 + %arrayidx = getelementptr inbounds i32, i32* %B, i64 1 + store i32 0, i32* %arrayidx, align 4 + ret void +} + +@G = global i32 0 + +; CHECK-LABEL: Function: baz +; CHECK: MayAlias: i32* %A, i32* @G +define void @baz(i32* %A) { +entry: + store i32 0, i32* %A, align 4 + store i32 0, i32* @G, align 4 + ret void +} + +; CHECK-LABEL: Alias Analysis Evaluator Report +; CHECK: 5 Total Alias Queries Performed +; CHECK: 0 no alias responses +; CHECK: 5 may alias responses Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/simple.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/simple.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/simple.ll @@ -0,0 +1,18 @@ +; This testcase consists of alias relations which should be completely +; resolvable by cfl-steens-aa (derived from BasicAA/2003-11-04-SimpleCases.ll). + +; RUN: opt < %s -cfl-steens-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s + +%T = type { i32, [10 x i8] } + +; CHECK: Function: test +; CHECK-NOT: May: + +define void @test(%T* %P) { + %A = getelementptr %T, %T* %P, i64 0 + %B = getelementptr %T, %T* %P, i64 0, i32 0 + %C = getelementptr %T, %T* %P, i64 0, i32 1 + %D = getelementptr %T, %T* %P, i64 0, i32 1, i64 0 + %E = getelementptr %T, %T* %P, i64 0, i32 1, i64 5 + ret void +} Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/stratified-attrs-indexing.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/stratified-attrs-indexing.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/stratified-attrs-indexing.ll @@ -0,0 +1,33 @@ +; This testcase ensures that CFLSteensAA doesn't try to access out of bounds indices +; when given functions with large amounts of arguments (specifically, more +; arguments than the StratifiedAttrs bitset can handle) +; +; Because the result on failure is effectively crashing the compiler, output +; checking is minimal. + +; RUN: opt < %s -cfl-steens-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s + +; CHECK: Function: test +define void @test(i1 %cond, + i32* %arg1, i32* %arg2, i32* %arg3, i32* %arg4, i32* %arg5, + i32* %arg6, i32* %arg7, i32* %arg8, i32* %arg9, i32* %arg10, + i32* %arg11, i32* %arg12, i32* %arg13, i32* %arg14, i32* %arg15, + i32* %arg16, i32* %arg17, i32* %arg18, i32* %arg19, i32* %arg20, + i32* %arg21, i32* %arg22, i32* %arg23, i32* %arg24, i32* %arg25, + i32* %arg26, i32* %arg27, i32* %arg28, i32* %arg29, i32* %arg30, + i32* %arg31, i32* %arg32, i32* %arg33, i32* %arg34, i32* %arg35) { + + ; CHECK: 946 Total Alias Queries Performed + ; CHECK: 43 no alias responses (4.5%) + %a = alloca i32, align 4 + %b = select i1 %cond, i32* %arg35, i32* %arg34 + %c = select i1 %cond, i32* %arg34, i32* %arg33 + %d = select i1 %cond, i32* %arg33, i32* %arg32 + %e = select i1 %cond, i32* %arg32, i32* %arg31 + %f = select i1 %cond, i32* %arg31, i32* %arg30 + %g = select i1 %cond, i32* %arg30, i32* %arg29 + %h = select i1 %cond, i32* %arg29, i32* %arg28 + %i = select i1 %cond, i32* %arg28, i32* %arg27 + + ret void +} Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/va.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/va.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/Steensgaard/va.ll @@ -0,0 +1,32 @@ +; RUN: opt < %s -disable-basicaa -cfl-steens-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s + +; CHECK-LABEL: Function: test1 +; CHECK: MayAlias: i32* %X, i32* %tmp +; CHECK: MayAlias: i32* %tmp, i8** %ap +; CHECK: NoAlias: i8** %ap, i8** %aq +; CHECK: MayAlias: i32* %tmp, i8** %aq + +define i32* @test1(i32* %X, ...) { + ; Initialize variable argument processing + %ap = alloca i8* + %ap2 = bitcast i8** %ap to i8* + call void @llvm.va_start(i8* %ap2) + + ; Read a single pointer argument + %tmp = va_arg i8** %ap, i32* + + ; Demonstrate usage of llvm.va_copy and llvm.va_end + %aq = alloca i8* + %aq2 = bitcast i8** %aq to i8* + call void @llvm.va_copy(i8* %aq2, i8* %ap2) + call void @llvm.va_end(i8* %aq2) + + ; Stop processing of arguments. + call void @llvm.va_end(i8* %ap2) + ret i32* %tmp +} + +declare void @llvm.va_start(i8*) +declare void @llvm.va_copy(i8*, i8*) +declare void @llvm.va_end(i8*) + Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/arguments-globals.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/arguments-globals.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/arguments-globals.ll @@ -1,20 +0,0 @@ -; This testcase ensures that CFL AA gives conservative answers on variables -; that involve arguments. -; (Everything should alias everything, because args can alias globals, so the -; aliasing sets should of args+alloca+global should be combined) - -; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s - -; CHECK: Function: test - -@g = external global i32 - -define void @test(i1 %c, i32* %arg1, i32* %arg2) { - ; CHECK: 15 Total Alias Queries Performed - ; CHECK: 0 no alias responses - %A = alloca i32, align 4 - %B = select i1 %c, i32* %arg1, i32* %arg2 - %C = select i1 %c, i32* @g, i32* %A - - ret void -} Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/arguments.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/arguments.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/arguments.ll @@ -1,15 +0,0 @@ -; This testcase ensures that CFL AA gives conservative answers on variables -; that involve arguments. - -; RUN: opt < %s -cfl-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s - -; CHECK: Function: test - -define void @test(i1 %c, i32* %arg1, i32* %arg2) { - ; CHECK: 6 Total Alias Queries Performed - ; CHECK: 3 no alias responses - %a = alloca i32, align 4 - %b = select i1 %c, i32* %arg1, i32* %arg2 - - ret void -} Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/asm-global-bugfix.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/asm-global-bugfix.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/asm-global-bugfix.ll @@ -1,16 +0,0 @@ -; Test case for a bug where we would crash when we were requested to report -; whether two values that didn't belong to a function (i.e. two globals, etc) -; aliased. - -; RUN: opt < %s -cfl-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s - -@G = private unnamed_addr constant [1 x i8] c"\00", align 1 - -; CHECK: Function: test_no_crash -; CHECK: 0 no alias responses -define void @test_no_crash() #0 { -entry: - call i8* asm "nop", "=r,r"( - i8* getelementptr inbounds ([1 x i8], [1 x i8]* @G, i64 0, i64 0)) - ret void -} Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/attr-escape.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/attr-escape.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/attr-escape.ll @@ -1,94 +0,0 @@ -; This testcase ensures that CFL AA handles escaped values no more conservative than it should - -; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s -; RUN: opt < %s -aa-pipeline=cfl-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s - -; CHECK-LABEL: Function: test_local -; CHECK: NoAlias: i32* %a, i32* %b -; CHECK: MayAlias: i32* %a, i32* %aAlias -; CHECK: NoAlias: i32* %aAlias, i32* %b -define void @test_local() { - %a = alloca i32, align 4 - %b = alloca i32, align 4 - %aint = ptrtoint i32* %a to i64 - %aAlias = inttoptr i64 %aint to i32* - ret void -} - -; CHECK-LABEL: Function: test_global_param -; CHECK: NoAlias: i32* %a, i32** %x -; CHECK: MayAlias: i32* %a, i32* %xload -; CHECK: MayAlias: i32* %a, i32* %gload -; CHECK: MayAlias: i32* %gload, i32* %xload -; CHECK: MayAlias: i32** %x, i32** @ext_global -; CHECK: NoAlias: i32* %a, i32** @ext_global -@ext_global = external global i32* -define void @test_global_param(i32** %x) { - %a = alloca i32, align 4 - %aint = ptrtoint i32* %a to i64 - %xload = load i32*, i32** %x - %gload = load i32*, i32** @ext_global - ret void -} - -declare void @external_func(i32**) -; CHECK-LABEL: Function: test_external_call -; CHECK: NoAlias: i32* %b, i32* %x -; CHECK: NoAlias: i32* %b, i32** %a -; CHECK: MayAlias: i32* %c, i32* %x -; CHECK: MayAlias: i32* %c, i32** %a -; CHECK: NoAlias: i32* %b, i32* %c -define void @test_external_call(i32* %x) { - %a = alloca i32*, align 8 - %b = alloca i32, align 4 - call void @external_func(i32** %a) - %c = load i32*, i32** %a - ret void -} - -declare void @external_func_readonly(i32**) readonly -; CHECK-LABEL: Function: test_external_call_func_readonly -; CHECK: MayAlias: i32* %c, i32* %x -; CHECK: NoAlias: i32* %c, i32** %a -define void @test_external_call_func_readonly(i32* %x) { - %a = alloca i32*, align 8 - %b = alloca i32, align 4 - store i32* %x, i32** %a, align 4 - call void @external_func_readonly(i32** %a) - %c = load i32*, i32** %a - ret void -} - -; CHECK-LABEL: Function: test_external_call_callsite_readonly -; CHECK: MayAlias: i32* %c, i32* %x -; CHECK: NoAlias: i32* %c, i32** %a -define void @test_external_call_callsite_readonly(i32* %x) { - %a = alloca i32*, align 8 - %b = alloca i32, align 4 - store i32* %x, i32** %a, align 4 - call void @external_func(i32** %a) readonly - %c = load i32*, i32** %a - ret void -} - -declare i32* @external_func_normal_return(i32*) -; CHECK-LABEL: Function: test_external_call_normal_return -; CHECK: MayAlias: i32* %c, i32* %x -; CHECK: MayAlias: i32* %a, i32* %c -define void @test_external_call_normal_return(i32* %x) { - %a = alloca i32, align 8 - %b = alloca i32, align 4 - %c = call i32* @external_func_normal_return(i32* %a) - ret void -} - -declare noalias i32* @external_func_noalias_return(i32*) -; CHECK-LABEL: Function: test_external_call_noalias_return -; CHECK: NoAlias: i32* %c, i32* %x -; CHECK: NoAlias: i32* %a, i32* %c -define void @test_external_call_noalias_return(i32* %x) { - %a = alloca i32, align 8 - %b = alloca i32, align 4 - %c = call i32* @external_func_noalias_return(i32* %a) - ret void -} Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/basic-interproc.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/basic-interproc.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/basic-interproc.ll @@ -1,22 +0,0 @@ -; This testcase ensures that CFL AA won't be too conservative when trying to do -; interprocedural analysis on simple callee - -; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s -; RUN: opt < %s -aa-pipeline=cfl-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s - -; CHECK-LABEL: Function: noop_callee -; CHECK: MayAlias: i32* %arg1, i32* %arg2 -define void @noop_callee(i32* %arg1, i32* %arg2) { - store i32 0, i32* %arg1 - store i32 0, i32* %arg2 - ret void -} -; CHECK-LABEL: Function: test_noop -; CHECK: NoAlias: i32* %a, i32* %b -define void @test_noop() { - %a = alloca i32, align 4 - %b = alloca i32, align 4 - call void @noop_callee(i32* %a, i32* %b) - - ret void -} Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/branch-alias.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/branch-alias.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/branch-alias.ll @@ -1,73 +0,0 @@ -; Makes sure that we give up on some pathological cases with inttoptr/ptrtoint -; -; @ptr_test was generated from the following C code: -; void ptr_test() { -; int* A; -; unsigned long RefCopy = 0; -; for (int i = 0; i < 8*sizeof(&A); ++i) { -; if ((unsigned long)&A & (1UL << i)) -; RefCopy |= 1UL << i; -; } -; -; int** AliasA1 = (int**)RefCopy; -; int* ShouldAliasA = *AliasA1; -; } - -; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s - -; CHECK: Function: ptr_test -define void @ptr_test() #0 { - ; CHECK: MayAlias: i32** %A, i32** %ShouldAliasA - ; CHECK-NOT: %AliasA1 -entry: - %A = alloca i32*, align 8 - %RefCopy = alloca i64, align 8 - %i = alloca i32, align 4 - %AliasA1 = alloca i32**, align 8 - %ShouldAliasA = alloca i32*, align 8 - store i64 0, i64* %RefCopy, align 8 - store i32 0, i32* %i, align 4 - br label %for.cond - -for.cond: ; preds = %for.inc, %entry - %0 = load i32, i32* %i, align 4 - %conv = sext i32 %0 to i64 - %cmp = icmp ult i64 %conv, 64 - br i1 %cmp, label %for.body, label %for.end - -for.body: ; preds = %for.cond - %1 = ptrtoint i32** %A to i64 - %2 = load i32, i32* %i, align 4 - %sh_prom = zext i32 %2 to i64 - %shl = shl i64 1, %sh_prom - %and = and i64 %1, %shl - %tobool = icmp ne i64 %and, 0 - br i1 %tobool, label %if.then, label %if.end - -if.then: ; preds = %for.body - %3 = load i32, i32* %i, align 4 - %sh_prom2 = zext i32 %3 to i64 - %shl3 = shl i64 1, %sh_prom2 - %4 = load i64, i64* %RefCopy, align 8 - %or = or i64 %4, %shl3 - store i64 %or, i64* %RefCopy, align 8 - br label %if.end - -if.end: ; preds = %if.then, %for.body - br label %for.inc - -for.inc: ; preds = %if.end - %5 = load i32, i32* %i, align 4 - %inc = add nsw i32 %5, 1 - store i32 %inc, i32* %i, align 4 - br label %for.cond - -for.end: ; preds = %for.cond - %6 = load i64, i64* %RefCopy, align 8 - %7 = inttoptr i64 %6 to i32** - store i32** %7, i32*** %AliasA1, align 8 - %8 = load i32**, i32*** %AliasA1, align 8 - %9 = load i32*, i32** %8, align 8 - store i32* %9, i32** %ShouldAliasA, align 8 - ret void -} Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/const-expr-gep.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/const-expr-gep.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/const-expr-gep.ll @@ -1,57 +0,0 @@ -; This testcase consists of alias relations which should be completely -; resolvable by cfl-aa, but require analysis of getelementptr constant exprs. -; Derived from BasicAA/2003-12-11-ConstExprGEP.ll - -; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s - -%T = type { i32, [10 x i8] } - -@G = external global %T -@G2 = external global %T - -; TODO: Quite a few of these are MayAlias because we don't yet consider -; constant offsets in CFLAA. If we start doing so, then we'll need to -; change these test cases - -; CHECK: Function: test -; CHECK: MayAlias: i32* %D, i32* %F -; CHECK: MayAlias: i32* %D, i8* %X -; CHECK: MayAlias: i32* %F, i8* %X -define void @test() { - %D = getelementptr %T, %T* @G, i64 0, i32 0 - %F = getelementptr i32, i32* getelementptr (%T, %T* @G, i64 0, i32 0), i64 0 - %X = getelementptr [10 x i8], [10 x i8]* getelementptr (%T, %T* @G, i64 0, i32 1), i64 0, i64 5 - - ret void -} - -; CHECK: Function: simplecheck -; CHECK: MayAlias: i32* %F, i32* %arg0 -; CHECK: MayAlias: i32* %H, i32* %arg0 -; CHECK: MayAlias: i32* %F, i32* %H -define void @simplecheck(i32* %arg0) { - %F = getelementptr i32, i32* getelementptr (%T, %T* @G, i64 0, i32 0), i64 0 - %H = getelementptr %T, %T* @G2, i64 0, i32 0 - - ret void -} - -; Ensure that CFLAA properly identifies and handles escaping variables (i.e. -; globals) in nested ConstantExprs - -; CHECK: Function: checkNesting -; CHECK: MayAlias: i32* %A, i32* %arg0 - -%NestedT = type { [1 x [1 x i32]] } -@NT = external global %NestedT - -define void @checkNesting(i32* %arg0) { - %A = getelementptr [1 x i32], - [1 x i32]* getelementptr - ([1 x [1 x i32]], [1 x [1 x i32]]* getelementptr (%NestedT, %NestedT* @NT, i64 0, i32 0), - i64 0, - i32 0), - i64 0, - i32 0 - ret void -} Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/constant-over-index.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/constant-over-index.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/constant-over-index.ll @@ -1,30 +0,0 @@ -; RUN: opt < %s -cfl-aa -aa-eval -print-all-alias-modref-info 2>&1 | FileCheck %s - -; CFL AA currently returns PartialAlias, BasicAA returns MayAlias, both seem -; acceptable (although we might decide that we don't want PartialAlias, and if -; so, we should update this test case accordingly). -; CHECK: {{PartialAlias|MayAlias}}: double* %p.0.i.0, double* %p3 - -; %p3 is equal to %p.0.i.0 on the second iteration of the loop, -; so MayAlias is needed. - -define void @foo([3 x [3 x double]]* noalias %p) { -entry: - %p3 = getelementptr [3 x [3 x double]], [3 x [3 x double]]* %p, i64 0, i64 0, i64 3 - br label %loop - -loop: - %i = phi i64 [ 0, %entry ], [ %i.next, %loop ] - - %p.0.i.0 = getelementptr [3 x [3 x double]], [3 x [3 x double]]* %p, i64 0, i64 %i, i64 0 - - store volatile double 0.0, double* %p3 - store volatile double 0.1, double* %p.0.i.0 - - %i.next = add i64 %i, 1 - %cmp = icmp slt i64 %i.next, 3 - br i1 %cmp, label %loop, label %exit - -exit: - ret void -} Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/empty.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/empty.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/empty.ll @@ -1,12 +0,0 @@ -; RUN: opt < %s -cfl-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s - -target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64" - -; CHECK: Function: foo: -; CHECK-NEXT: NoAlias: {}* %p, {}* %q - -define void @foo({}* %p, {}* %q) { - store {} {}, {}* %p - store {} {}, {}* %q - ret void -} Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/full-store-partial-alias.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/full-store-partial-alias.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/full-store-partial-alias.ll @@ -1,39 +0,0 @@ -; RUN: opt -S -disable-basicaa -tbaa -cfl-aa -gvn < %s | FileCheck -check-prefix=CFLAA %s -; RUN: opt -S -disable-basicaa -tbaa -gvn < %s | FileCheck %s -; Adapted from the BasicAA full-store-partial-alias.ll test. - -; CFL AA could notice that the store stores to the entire %u object, -; so the %tmp5 load is PartialAlias with the store and suppress TBAA. -; FIXME: However, right now, CFLAA cannot prove PartialAlias here -; Without CFL AA, TBAA should say that %tmp5 is NoAlias with the store. - -target datalayout = "e-p:64:64:64" - -%union.anon = type { double } - -@u = global %union.anon { double -2.500000e-01 }, align 8 -@endianness_test = global i64 1, align 8 - -define i32 @signbit(double %x) nounwind { -; FIXME: This would be ret i32 %tmp5.lobit if CFLAA could prove PartialAlias -; CFLAA: ret i32 0 -; CHECK: ret i32 0 -entry: - %u = alloca %union.anon, align 8 - %tmp9 = getelementptr inbounds %union.anon, %union.anon* %u, i64 0, i32 0 - store double %x, double* %tmp9, align 8, !tbaa !0 - %tmp2 = load i32, i32* bitcast (i64* @endianness_test to i32*), align 8, !tbaa !3 - %idxprom = sext i32 %tmp2 to i64 - %tmp4 = bitcast %union.anon* %u to [2 x i32]* - %arrayidx = getelementptr inbounds [2 x i32], [2 x i32]* %tmp4, i64 0, i64 %idxprom - %tmp5 = load i32, i32* %arrayidx, align 4, !tbaa !3 - %tmp5.lobit = lshr i32 %tmp5, 31 - ret i32 %tmp5.lobit -} - -!0 = !{!4, !4, i64 0} -!1 = !{!"omnipotent char", !2} -!2 = !{!"Simple C/C++ TBAA", null} -!3 = !{!5, !5, i64 0} -!4 = !{!"double", !1} -!5 = !{!"int", !1} Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/gep-index-no-alias.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/gep-index-no-alias.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/gep-index-no-alias.ll @@ -1,14 +0,0 @@ -; This testcase ensures that gep result does not alias gep indices - -; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-no-aliases -disable-output 2>&1 | FileCheck %s -; RUN: opt < %s -aa-pipeline=cfl-aa -passes=aa-eval -print-no-aliases -disable-output 2>&1 | FileCheck %s - -; CHECK: Function: foo -; CHECK: [2 x i32]* %a, [2 x i32]* %b -define void @foo(i32 %n) { - %a = alloca [2 x i32], align 4 - %b = alloca [2 x i32], align 4 - %c = getelementptr inbounds [2 x i32], [2 x i32]* %a, i32 0, i32 %n - %d = getelementptr inbounds [2 x i32], [2 x i32]* %b, i32 0, i32 %n - ret void -} Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/gep-signed-arithmetic.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/gep-signed-arithmetic.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/gep-signed-arithmetic.ll @@ -1,19 +0,0 @@ -; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s -; Derived from BasicAA/2010-09-15-GEP-SignedArithmetic.ll - -target datalayout = "e-p:32:32:32" - -; FIXME: This could be PartialAlias but CFLAA can't currently prove it -; CHECK: 1 may alias response - -define i32 @test(i32 %indvar) nounwind { - %tab = alloca i32, align 4 - %tmp31 = mul i32 %indvar, -2 - %tmp32 = add i32 %tmp31, 30 - %t.5 = getelementptr i32, i32* %tab, i32 %tmp32 - %loada = load i32, i32* %tab - store i32 0, i32* %t.5 - %loadb = load i32, i32* %tab - %rval = add i32 %loada, %loadb - ret i32 %rval -} Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/interproc-arg-deref-escape.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/interproc-arg-deref-escape.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/interproc-arg-deref-escape.ll @@ -1,33 +0,0 @@ -; This testcase ensures that CFL AA answers queries soundly when callee tries -; to escape the memory pointed to by its parameters - -; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s -; RUN: opt < %s -aa-pipeline=cfl-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s - -declare void @opaque(i32*) -define void @escape_arg_deref(i32** %arg) { - %arg_deref = load i32*, i32** %arg - call void @opaque(i32* %arg_deref) - ret void -} -; CHECK-LABEL: Function: test_arg_deref_escape -; CHECK: NoAlias: i32* %a, i32** %x -; CHECK: NoAlias: i32* %b, i32** %x -; CHECK: NoAlias: i32* %a, i32* %b -; CHECK: NoAlias: i32** %p, i32** %x -; CHECK: NoAlias: i32* %a, i32** %p -; CHECK: NoAlias: i32* %b, i32** %p -; CHECK: MayAlias: i32* %a, i32* %c -; CHECK: NoAlias: i32* %b, i32* %c -; CHECK: NoAlias: i32* %c, i32** %p -define void @test_arg_deref_escape(i32** %x) { - %a = alloca i32, align 4 - %b = alloca i32, align 4 - %p = alloca i32*, align 4 - - store i32* %a, i32** %p - call void @escape_arg_deref(i32** %p) - %c = load i32*, i32** %x - - ret void -} \ No newline at end of file Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/interproc-arg-escape.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/interproc-arg-escape.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/interproc-arg-escape.ll @@ -1,31 +0,0 @@ -; This testcase ensures that CFL AA answers queries soundly when callee tries -; to escape its parameters - -; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s -; RUN: opt < %s -aa-pipeline=cfl-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s - -declare void @opaque(i32*) -define void @escape_arg(i32* %arg) { - call void @opaque(i32* %arg) - ret void -} -; CHECK-LABEL: Function: test_arg_escape -; CHECK: NoAlias: i32* %a, i32** %x -; CHECK: NoAlias: i32* %b, i32** %x -; CHECK: NoAlias: i32* %a, i32* %b -; CHECK: NoAlias: i32* %c, i32** %x -; CHECK: NoAlias: i32* %a, i32* %c -; CHECK: NoAlias: i32* %b, i32* %c -; CHECK: MayAlias: i32* %a, i32* %d -; CHECK: MayAlias: i32* %b, i32* %d -; CHECK: NoAlias: i32* %c, i32* %d -define void @test_arg_escape(i32** %x) { - %a = alloca i32, align 4 - %b = alloca i32, align 4 - %c = alloca i32, align 4 - call void @escape_arg(i32* %a) - call void @escape_arg(i32* %b) - %d = load i32*, i32** %x - - ret void -} \ No newline at end of file Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/interproc-ret-arg.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/interproc-ret-arg.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/interproc-ret-arg.ll @@ -1,23 +0,0 @@ -; This testcase ensures that CFL AA answers queries soundly when callee tries -; to return one of its parameters - -; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s -; RUN: opt < %s -aa-pipeline=cfl-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s - -define i32* @return_arg_callee(i32* %arg1, i32* %arg2) { - ret i32* %arg1 -} -; CHECK-LABEL: Function: test_return_arg -; CHECK: NoAlias: i32* %a, i32* %b -; CHECK: MayAlias: i32* %a, i32* %c -; CHECK: NoAlias: i32* %b, i32* %c - -; CHECK: NoModRef: Ptr: i32* %b <-> %c = call i32* @return_arg_callee(i32* %a, i32* %b) -define void @test_return_arg() { - %a = alloca i32, align 4 - %b = alloca i32, align 4 - - %c = call i32* @return_arg_callee(i32* %a, i32* %b) - - ret void -} \ No newline at end of file Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/interproc-ret-deref-arg-multilevel.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/interproc-ret-deref-arg-multilevel.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/interproc-ret-deref-arg-multilevel.ll @@ -1,46 +0,0 @@ -; This testcase ensures that CFL AA answers queries soundly when callee tries -; to return the multi-level dereference of one of its parameters - -; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s -; RUN: opt < %s -aa-pipeline=cfl-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s - -define i32* @return_deref_arg_multilevel_callee(i32*** %arg1) { - %deref = load i32**, i32*** %arg1 - %deref2 = load i32*, i32** %deref - ret i32* %deref2 -} -; CHECK-LABEL: Function: test_return_deref_arg_multilevel -; CHECK: NoAlias: i32* %a, i32* %b -; CHECK: MayAlias: i32* %a, i32* %c -; CHECK: NoAlias: i32* %b, i32* %c -; CHECK: NoAlias: i32* %c, i32** %p -; CHECK: NoAlias: i32* %c, i32*** %pp -; CHECK: MayAlias: i32** %lpp, i32** %p -; CHECK: NoAlias: i32** %lpp, i32*** %pp -; CHECK: NoAlias: i32* %c, i32** %lpp -; CHECK: MayAlias: i32* %a, i32* %lpp_deref -; CHECK: NoAlias: i32* %b, i32* %lpp_deref -; CHECK: NoAlias: i32* %lpp_deref, i32*** %pp -; CHECK: MayAlias: i32* %a, i32* %lp -; CHECK: NoAlias: i32* %b, i32* %lp -; CHECK: NoAlias: i32* %lp, i32** %p -; CHECK: NoAlias: i32* %lp, i32*** %pp -; CHECK: MayAlias: i32* %c, i32* %lp -; CHECK: NoAlias: i32* %lp, i32** %lpp -; CHECK: MayAlias: i32* %lp, i32* %lpp_deref -define void @test_return_deref_arg_multilevel() { - %a = alloca i32, align 4 - %b = alloca i32, align 4 - %p = alloca i32*, align 8 - %pp = alloca i32**, align 8 - - store i32* %a, i32** %p - store i32** %p, i32*** %pp - %c = call i32* @return_deref_arg_multilevel_callee(i32*** %pp) - - %lpp = load i32**, i32*** %pp - %lpp_deref = load i32*, i32** %lpp - %lp = load i32*, i32** %p - - ret void -} \ No newline at end of file Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/interproc-ret-deref-arg.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/interproc-ret-deref-arg.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/interproc-ret-deref-arg.ll @@ -1,30 +0,0 @@ -; This testcase ensures that CFL AA answers queries soundly when callee tries -; to return the dereference of one of its parameters - -; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s -; RUN: opt < %s -aa-pipeline=cfl-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s - -define i32* @return_deref_arg_callee(i32** %arg1) { - %deref = load i32*, i32** %arg1 - ret i32* %deref -} -; CHECK-LABEL: Function: test_return_deref_arg -; CHECK: NoAlias: i32* %a, i32* %b -; CHECK: MayAlias: i32* %a, i32* %c -; CHECK: NoAlias: i32* %b, i32* %c -; CHECK: MayAlias: i32* %a, i32* %lp -; CHECK: NoAlias: i32* %b, i32* %lp -; CHECK: NoAlias: i32* %lp, i32** %p -; CHECK: MayAlias: i32* %c, i32* %lp -define void @test_return_deref_arg() { - %a = alloca i32, align 4 - %b = alloca i32, align 4 - %p = alloca i32*, align 8 - - store i32* %a, i32** %p - %c = call i32* @return_deref_arg_callee(i32** %p) - - %lp = load i32*, i32** %p - - ret void -} \ No newline at end of file Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/interproc-ret-escape.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/interproc-ret-escape.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/interproc-ret-escape.ll @@ -1,33 +0,0 @@ -; This testcase ensures that CFL AA answers queries soundly when callee tries -; to return an escaped pointer - -; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s -; RUN: opt < %s -aa-pipeline=cfl-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s - -declare noalias i8* @malloc(i64) -declare void @opaque(i32*) - -define i32* @return_escaped_callee() { - %ptr = call noalias i8* @malloc(i64 8) - %ptr_cast = bitcast i8* %ptr to i32* - call void @opaque(i32* %ptr_cast) - ret i32* %ptr_cast -} -; CHECK-LABEL: Function: test_return_escape -; CHECK: NoAlias: i32* %a, i32** %x -; CHECK: NoAlias: i32* %b, i32** %x -; CHECK: NoAlias: i32* %a, i32* %b -; CHECK: NoAlias: i32* %c, i32** %x -; CHECK: NoAlias: i32* %a, i32* %c -; CHECK: NoAlias: i32* %b, i32* %c -; CHECK: NoAlias: i32* %a, i32* %d -; CHECK: MayAlias: i32* %b, i32* %d -; CHECK: MayAlias: i32* %c, i32* %d -define void @test_return_escape(i32** %x) { - %a = alloca i32, align 4 - %b = call i32* @return_escaped_callee() - %c = call i32* @return_escaped_callee() - %d = load i32*, i32** %x - - ret void -} \ No newline at end of file Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/interproc-ret-ref-arg-multilevel.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/interproc-ret-ref-arg-multilevel.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/interproc-ret-ref-arg-multilevel.ll @@ -1,51 +0,0 @@ -; This testcase ensures that CFL AA answers queries soundly when callee tries -; to return the multi-level reference of one of its parameters - -; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s -; RUN: opt < %s -aa-pipeline=cfl-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s - -declare noalias i8* @malloc(i64) - -define i32*** @return_ref_arg_multilevel_callee(i32* %arg1) { - %ptr = call noalias i8* @malloc(i64 8) - %ptr_cast = bitcast i8* %ptr to i32*** - %ptr2 = call noalias i8* @malloc(i64 8) - %ptr_cast2 = bitcast i8* %ptr2 to i32** - store i32* %arg1, i32** %ptr_cast2 - store i32** %ptr_cast2, i32*** %ptr_cast - ret i32*** %ptr_cast -} -; CHECK-LABEL: Function: test_return_ref_arg_multilevel -; CHECK: NoAlias: i32* %a, i32*** %b -; CHECK: NoAlias: i32** %p, i32*** %b -; CHECK: NoAlias: i32* %a, i32** %lb -; CHECK: NoAlias: i32** %lb, i32*** %pp -; CHECK: NoAlias: i32** %lb, i32*** %b -; CHECK: MayAlias: i32* %a, i32* %lb_deref -; CHECK: NoAlias: i32* %lb_deref, i32** %lpp -; CHECK: MayAlias: i32* %lb_deref, i32* %lpp_deref -; CHECK: NoAlias: i32* %lpp_deref, i32** %lpp -; CHECK: MayAlias: i32* %lb_deref, i32* %lp -; CHECK: NoAlias: i32* %lp, i32** %lpp -; CHECK: MayAlias: i32* %lp, i32* %lpp_deref - -; We could've proven the following facts if the analysis were inclusion-based: -; NoAlias: i32*** %b, i32*** %pp -; NoAlias: i32** %lb, i32** %p -define void @test_return_ref_arg_multilevel() { - %a = alloca i32, align 4 - %p = alloca i32*, align 8 - %pp = alloca i32**, align 8 - - store i32* %a, i32** %p - store i32** %p, i32*** %pp - %b = call i32*** @return_ref_arg_multilevel_callee(i32* %a) - - %lb = load i32**, i32*** %b - %lb_deref = load i32*, i32** %lb - %lpp = load i32**, i32*** %pp - %lpp_deref = load i32*, i32** %lpp - %lp = load i32*, i32** %p - - ret void -} \ No newline at end of file Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/interproc-ret-ref-arg.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/interproc-ret-ref-arg.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/interproc-ret-ref-arg.ll @@ -1,36 +0,0 @@ -; This testcase ensures that CFL AA answers queries soundly when callee tries -; to return the reference of one of its parameters - -; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s -; RUN: opt < %s -aa-pipeline=cfl-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s - -declare noalias i8* @malloc(i64) - -define i32** @return_ref_arg_callee(i32* %arg1) { - %ptr = call noalias i8* @malloc(i64 8) - %ptr_cast = bitcast i8* %ptr to i32** - store i32* %arg1, i32** %ptr_cast - ret i32** %ptr_cast -} -; CHECK-LABEL: Function: test_return_ref_arg -; CHECK: MayAlias: i32* %a, i32* %lb -; CHECK: NoAlias: i32* %lb, i32** %p -; CHECK: NoAlias: i32* %lb, i32** %b -; CHECK: NoAlias: i32* %lp, i32** %p -; CHECK: NoAlias: i32* %lp, i32** %b -; CHECK: MayAlias: i32* %lb, i32* %lp - -; We could've proven the following facts if the analysis were inclusion-based: -; NoAlias: i32** %b, i32** %p -define void @test_return_ref_arg() { - %a = alloca i32, align 4 - %p = alloca i32*, align 8 - - store i32* %a, i32** %p - %b = call i32** @return_ref_arg_callee(i32* %a) - - %lb = load i32*, i32** %b - %lp = load i32*, i32** %p - - ret void -} \ No newline at end of file Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/interproc-ret-unknown.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/interproc-ret-unknown.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/interproc-ret-unknown.ll @@ -1,38 +0,0 @@ -; This testcase ensures that CFL AA answers queries soundly when callee tries -; to return an unknown pointer - -; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s -; RUN: opt < %s -aa-pipeline=cfl-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s - -@g = external global i32 -define i32* @return_unknown_callee(i32* %arg1, i32* %arg2) { - ret i32* @g -} -; CHECK-LABEL: Function: test_return_unknown -; CHECK: NoAlias: i32* %a, i32* %b -; CHECK: MayAlias: i32* %c, i32* %x -; CHECK: NoAlias: i32* %a, i32* %c -; CHECK: NoAlias: i32* %b, i32* %c -define void @test_return_unknown(i32* %x) { - %a = alloca i32, align 4 - %b = alloca i32, align 4 - - %c = call i32* @return_unknown_callee(i32* %a, i32* %b) - - ret void -} - -@g2 = external global i32* -define i32** @return_unknown_callee2() { - ret i32** @g2 -} -; CHECK-LABEL: Function: test_return_unknown2 -; CHECK: MayAlias: i32* %x, i32** %a -; CHECK: MayAlias: i32* %b, i32* %x -; CHECK: MayAlias: i32* %b, i32** %a -define void @test_return_unknown2(i32* %x) { - %a = call i32** @return_unknown_callee2() - %b = load i32*, i32** %a - - ret void -} \ No newline at end of file Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/interproc-store-arg-multilevel.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/interproc-store-arg-multilevel.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/interproc-store-arg-multilevel.ll @@ -1,48 +0,0 @@ -; This testcase ensures that CFL AA answers queries soundly when callee tries -; to mutate the memory pointed to by its parameters - -; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s -; RUN: opt < %s -aa-pipeline=cfl-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s - -declare noalias i8* @malloc(i64) - -define void @store_arg_multilevel_callee(i32*** %arg1, i32* %arg2) { - %ptr = call noalias i8* @malloc(i64 8) - %ptr_cast = bitcast i8* %ptr to i32** - store i32* %arg2, i32** %ptr_cast - store i32** %ptr_cast, i32*** %arg1 - ret void -} -; CHECK-LABEL: Function: test_store_arg_multilevel -; CHECK: NoAlias: i32* %a, i32** %lpp -; CHECK: NoAlias: i32* %b, i32** %lpp -; CHECK: MayAlias: i32** %lpp, i32** %p -; CHECK: MayAlias: i32* %a, i32* %lpp_deref -; CHECK: MayAlias: i32* %b, i32* %lpp_deref -; CHECK: NoAlias: i32* %lpp_deref, i32** %p -; CHECK: NoAlias: i32* %lpp_deref, i32*** %pp -; CHECK: NoAlias: i32* %lpp_deref, i32** %lpp -; CHECK: MayAlias: i32* %a, i32* %lp -; CHECK: NoAlias: i32* %lp, i32*** %pp -; CHECK: NoAlias: i32* %lp, i32** %lpp -; CHECK: MayAlias: i32* %lp, i32* %lpp_deref - -; We could've proven the following facts if the analysis were inclusion-based: -; NoAlias: i32* %a, i32* %b -; NoAlias: i32* %b, i32* %lp -define void @test_store_arg_multilevel() { - %a = alloca i32, align 4 - %b = alloca i32, align 4 - %p = alloca i32*, align 8 - %pp = alloca i32**, align 8 - - store i32* %a, i32** %p - store i32** %p, i32*** %pp - call void @store_arg_multilevel_callee(i32*** %pp, i32* %b) - - %lpp = load i32**, i32*** %pp - %lpp_deref = load i32*, i32** %lpp - %lp = load i32*, i32** %p - - ret void -} \ No newline at end of file Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/interproc-store-arg-unknown.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/interproc-store-arg-unknown.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/interproc-store-arg-unknown.ll @@ -1,32 +0,0 @@ -; This testcase ensures that CFL AA answers queries soundly when callee tries -; to mutate the memory pointed to by its parameters - -; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s -; RUN: opt < %s -aa-pipeline=cfl-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s - -@g = external global i32 - -define void @store_arg_unknown_callee(i32** %arg1) { - store i32* @g, i32** %arg1 - ret void -} -; CHECK-LABEL: Function: test_store_arg_unknown -; CHECK: NoAlias: i32* %x, i32** %p -; CHECK: NoAlias: i32* %a, i32** %p -; CHECK: NoAlias: i32* %b, i32** %p -; CHECK: MayAlias: i32* %lp, i32* %x -; CHECK: MayAlias: i32* %a, i32* %lp -; CHECK: NoAlias: i32* %b, i32* %lp -; CHECK: NoAlias: i32* %lp, i32** %p -define void @test_store_arg_unknown(i32* %x) { - %a = alloca i32, align 4 - %b = alloca i32, align 4 - %p = alloca i32*, align 8 - - store i32* %a, i32** %p - call void @store_arg_unknown_callee(i32** %p) - - %lp = load i32*, i32** %p - - ret void -} \ No newline at end of file Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/interproc-store-arg.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/interproc-store-arg.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/interproc-store-arg.ll @@ -1,36 +0,0 @@ -; This testcase ensures that CFL AA answers queries soundly when callee tries -; to mutate the memory pointed to by its parameters - -; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s -; RUN: opt < %s -aa-pipeline=cfl-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s - -define void @store_arg_callee(i32** %arg1, i32* %arg2) { - store i32* %arg2, i32** %arg1 - ret void -} -; CHECK-LABEL: Function: test_store_arg -; CHECK: NoAlias: i32* %a, i32** %p -; CHECK: NoAlias: i32* %b, i32** %p -; CHECK: MayAlias: i32* %a, i32* %lp -; CHECK: MayAlias: i32* %b, i32* %lp -; CHECK: MayAlias: i32* %b, i32* %lq -; CHECK: MayAlias: i32* %lp, i32* %lq - -; We could've proven the following facts if the analysis were inclusion-based: -; NoAlias: i32* %a, i32* %b -; NoAlias: i32* %a, i32* %lq -define void @test_store_arg() { - %a = alloca i32, align 4 - %b = alloca i32, align 4 - %p = alloca i32*, align 8 - %q = alloca i32*, align 8 - - store i32* %a, i32** %p - store i32* %b, i32** %q - call void @store_arg_callee(i32** %p, i32* %b) - - %lp = load i32*, i32** %p - %lq = load i32*, i32** %q - - ret void -} \ No newline at end of file Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/malloc-and-free.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/malloc-and-free.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/malloc-and-free.ll @@ -1,30 +0,0 @@ -; This testcase ensures that CFL AA handles malloc and free in a sound and precise manner - -; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-no-aliases -disable-output 2>&1 | FileCheck %s -; RUN: opt < %s -aa-pipeline=cfl-aa -passes=aa-eval -print-no-aliases -disable-output 2>&1 | FileCheck %s - -declare noalias i8* @malloc(i64) -declare noalias i8* @calloc(i64, i64) -declare void @free(i8* nocapture) - -; CHECK: Function: test_malloc -; CHECK: NoAlias: i8* %p, i8* %q -define void @test_malloc(i8* %p) { - %q = call i8* @malloc(i64 4) - ret void -} - -; CHECK: Function: test_calloc -; CHECK: NoAlias: i8* %p, i8* %q -define void @test_calloc(i8* %p) { - %q = call i8* @calloc(i64 2, i64 4) - ret void -} - -; CHECK: Function: test_free -; CHECK: NoAlias: i8* %p, i8* %q -define void @test_free(i8* %p) { - %q = alloca i8, align 4 - call void @free(i8* %q) - ret void -} Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/multilevel-combine.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/multilevel-combine.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/multilevel-combine.ll @@ -1,31 +0,0 @@ -; This testcase ensures that CFL AA responds conservatively when we union -; groups of pointers together through ternary/conditional operations -; Derived from: -; void foo(bool c) { -; char a, b; -; char *m = c ? &a : &b; -; *m; -; } -; - -; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s - -%T = type { i32, [10 x i8] } - -; CHECK: Function: test - -define void @test(i1 %C) { -; CHECK: 10 Total Alias Queries Performed -; CHECK: 4 no alias responses - %M = alloca %T*, align 8 ; NoAlias with %A, %B, %MS, %AP - %A = alloca %T, align 8 - %B = alloca %T, align 8 - - %MS = select i1 %C, %T* %B, %T* %A - - store %T* %MS, %T** %M - - %AP = load %T*, %T** %M ; PartialAlias with %A, %B - - ret void -} Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/multilevel.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/multilevel.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/multilevel.ll @@ -1,30 +0,0 @@ -; This testcase ensures that CFL AA handles trivial cases with storing -; pointers in pointers appropriately. -; Derived from: -; char a, b; -; char *m = &a, *n = &b; -; *m; -; *n; - -; RUN: opt < %s -cfl-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s - -%T = type { i32, [10 x i8] } - -; CHECK: Function: test - -define void @test() { -; CHECK: 15 Total Alias Queries Performed -; CHECK: 13 no alias responses - %M = alloca %T*, align 8 - %N = alloca %T*, align 8 - %A = alloca %T, align 8 - %B = alloca %T, align 8 - - store %T* %A, %T** %M - store %T* %B, %T** %N - - %AP = load %T*, %T** %M ; PartialAlias with %A - %BP = load %T*, %T** %N ; PartialAlias with %B - - ret void -} Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/must-and-partial.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/must-and-partial.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/must-and-partial.ll @@ -1,54 +0,0 @@ -; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-all-alias-modref-info 2>&1 | FileCheck %s -; When merging MustAlias and PartialAlias, merge to PartialAlias -; instead of MayAlias. - - -target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64" - -; FIXME: This could be PartialAlias but CFLAA can't currently prove it -; CHECK: MayAlias: i16* %bigbase0, i8* %phi -define i8 @test0(i1 %x) { -entry: - %base = alloca i8, align 4 - %baseplusone = getelementptr i8, i8* %base, i64 1 - br i1 %x, label %red, label %green -red: - br label %green -green: - %phi = phi i8* [ %baseplusone, %red ], [ %base, %entry ] - store i8 0, i8* %phi - - %bigbase0 = bitcast i8* %base to i16* - store i16 -1, i16* %bigbase0 - - %loaded = load i8, i8* %phi - ret i8 %loaded -} - -; FIXME: This could be PartialAlias but CFLAA can't currently prove it -; CHECK: MayAlias: i16* %bigbase1, i8* %sel -define i8 @test1(i1 %x) { -entry: - %base = alloca i8, align 4 - %baseplusone = getelementptr i8, i8* %base, i64 1 - %sel = select i1 %x, i8* %baseplusone, i8* %base - store i8 0, i8* %sel - - %bigbase1 = bitcast i8* %base to i16* - store i16 -1, i16* %bigbase1 - - %loaded = load i8, i8* %sel - ret i8 %loaded -} - -; Incoming pointer arguments should not be PartialAlias because we do not know their initial state -; even if they are nocapture -; CHECK: MayAlias: double* %A, double* %Index -define void @testr2(double* nocapture readonly %A, double* nocapture readonly %Index) { - %arrayidx22 = getelementptr inbounds double, double* %Index, i64 2 - %1 = load double, double* %arrayidx22 - %arrayidx25 = getelementptr inbounds double, double* %A, i64 2 - %2 = load double, double* %arrayidx25 - %mul26 = fmul double %1, %2 - ret void -} Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/opaque-call-alias.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/opaque-call-alias.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/opaque-call-alias.ll @@ -1,20 +0,0 @@ -; We previously had a case where we would put results from a no-args call in -; its own stratified set. This would make cases like the one in @test say that -; nothing (except %Escapes and %Arg) can alias - -; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s - -; CHECK: Function: test -; CHECK: NoAlias: i8* %Arg, i8* %Escapes -; CHECK: MayAlias: i8* %Arg, i8* %Retrieved -; CHECK: MayAlias: i8* %Escapes, i8* %Retrieved -define void @test(i8* %Arg) { - %Noalias = alloca i8 - %Escapes = alloca i8 - call void @set_thepointer(i8* %Escapes) - %Retrieved = call i8* @get_thepointer() - ret void -} - -declare void @set_thepointer(i8* %P) -declare i8* @get_thepointer() Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/phi-and-select.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/phi-and-select.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/phi-and-select.ll @@ -1,36 +0,0 @@ -; RUN: opt < %s -cfl-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s -; Derived from (a subset of) BasicAA/phi-and-select.ll - -; CHECK: Function: qux -; CHECK: NoAlias: double* %a, double* %b -; CHECK: ===== Alias Analysis Evaluator Report ===== - -; Two PHIs with disjoint sets of inputs. -define void @qux(i1 %m, double* noalias %x, double* noalias %y, - i1 %n, double* noalias %v, double* noalias %w) { -entry: - br i1 %m, label %true, label %false - -true: - br label %exit - -false: - br label %exit - -exit: - %a = phi double* [ %x, %true ], [ %y, %false ] - br i1 %n, label %ntrue, label %nfalse - -ntrue: - br label %nexit - -nfalse: - br label %nexit - -nexit: - %b = phi double* [ %v, %ntrue ], [ %w, %nfalse ] - store volatile double 0.0, double* %a - store volatile double 1.0, double* %b - ret void -} - Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/pr27213.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/pr27213.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/pr27213.ll @@ -1,39 +0,0 @@ -; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s -; RUN: opt < %s -aa-pipeline=cfl-aa -passes=aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s - -; CHECK-LABEL: Function: foo -; CHECK: MayAlias: i32* %A, i32* %B -define void @foo(i32* %A, i32* %B) { -entry: - store i32 0, i32* %A, align 4 - store i32 0, i32* %B, align 4 - ret void -} - -; CHECK-LABEL: Function: bar -; CHECK: MayAlias: i32* %A, i32* %B -; CHECK: MayAlias: i32* %A, i32* %arrayidx -; CHECK: MayAlias: i32* %B, i32* %arrayidx -define void @bar(i32* %A, i32* %B) { -entry: - store i32 0, i32* %A, align 4 - %arrayidx = getelementptr inbounds i32, i32* %B, i64 1 - store i32 0, i32* %arrayidx, align 4 - ret void -} - -@G = global i32 0 - -; CHECK-LABEL: Function: baz -; CHECK: MayAlias: i32* %A, i32* @G -define void @baz(i32* %A) { -entry: - store i32 0, i32* %A, align 4 - store i32 0, i32* @G, align 4 - ret void -} - -; CHECK-LABEL: Alias Analysis Evaluator Report -; CHECK: 5 Total Alias Queries Performed -; CHECK: 0 no alias responses -; CHECK: 5 may alias responses Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/simple.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/simple.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/simple.ll @@ -1,18 +0,0 @@ -; This testcase consists of alias relations which should be completely -; resolvable by cfl-aa (derived from BasicAA/2003-11-04-SimpleCases.ll). - -; RUN: opt < %s -cfl-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s - -%T = type { i32, [10 x i8] } - -; CHECK: Function: test -; CHECK-NOT: May: - -define void @test(%T* %P) { - %A = getelementptr %T, %T* %P, i64 0 - %B = getelementptr %T, %T* %P, i64 0, i32 0 - %C = getelementptr %T, %T* %P, i64 0, i32 1 - %D = getelementptr %T, %T* %P, i64 0, i32 1, i64 0 - %E = getelementptr %T, %T* %P, i64 0, i32 1, i64 5 - ret void -} Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/stratified-attrs-indexing.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/stratified-attrs-indexing.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/stratified-attrs-indexing.ll @@ -1,33 +0,0 @@ -; This testcase ensures that CFLAA doesn't try to access out of bounds indices -; when given functions with large amounts of arguments (specifically, more -; arguments than the StratifiedAttrs bitset can handle) -; -; Because the result on failure is effectively crashing the compiler, output -; checking is minimal. - -; RUN: opt < %s -cfl-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s - -; CHECK: Function: test -define void @test(i1 %cond, - i32* %arg1, i32* %arg2, i32* %arg3, i32* %arg4, i32* %arg5, - i32* %arg6, i32* %arg7, i32* %arg8, i32* %arg9, i32* %arg10, - i32* %arg11, i32* %arg12, i32* %arg13, i32* %arg14, i32* %arg15, - i32* %arg16, i32* %arg17, i32* %arg18, i32* %arg19, i32* %arg20, - i32* %arg21, i32* %arg22, i32* %arg23, i32* %arg24, i32* %arg25, - i32* %arg26, i32* %arg27, i32* %arg28, i32* %arg29, i32* %arg30, - i32* %arg31, i32* %arg32, i32* %arg33, i32* %arg34, i32* %arg35) { - - ; CHECK: 946 Total Alias Queries Performed - ; CHECK: 43 no alias responses (4.5%) - %a = alloca i32, align 4 - %b = select i1 %cond, i32* %arg35, i32* %arg34 - %c = select i1 %cond, i32* %arg34, i32* %arg33 - %d = select i1 %cond, i32* %arg33, i32* %arg32 - %e = select i1 %cond, i32* %arg32, i32* %arg31 - %f = select i1 %cond, i32* %arg31, i32* %arg30 - %g = select i1 %cond, i32* %arg30, i32* %arg29 - %h = select i1 %cond, i32* %arg29, i32* %arg28 - %i = select i1 %cond, i32* %arg28, i32* %arg27 - - ret void -} Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/va.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/va.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/va.ll @@ -1,32 +0,0 @@ -; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s - -; CHECK-LABEL: Function: test1 -; CHECK: MayAlias: i32* %X, i32* %tmp -; CHECK: MayAlias: i32* %tmp, i8** %ap -; CHECK: NoAlias: i8** %ap, i8** %aq -; CHECK: MayAlias: i32* %tmp, i8** %aq - -define i32* @test1(i32* %X, ...) { - ; Initialize variable argument processing - %ap = alloca i8* - %ap2 = bitcast i8** %ap to i8* - call void @llvm.va_start(i8* %ap2) - - ; Read a single pointer argument - %tmp = va_arg i8** %ap, i32* - - ; Demonstrate usage of llvm.va_copy and llvm.va_end - %aq = alloca i8* - %aq2 = bitcast i8** %aq to i8* - call void @llvm.va_copy(i8* %aq2, i8* %ap2) - call void @llvm.va_end(i8* %aq2) - - ; Stop processing of arguments. - call void @llvm.va_end(i8* %ap2) - ret i32* %tmp -} - -declare void @llvm.va_start(i8*) -declare void @llvm.va_copy(i8*, i8*) -declare void @llvm.va_end(i8*) -