diff --git a/clang/docs/tools/clang-formatted-files.txt b/clang/docs/tools/clang-formatted-files.txt --- a/clang/docs/tools/clang-formatted-files.txt +++ b/clang/docs/tools/clang-formatted-files.txt @@ -4986,9 +4986,6 @@ llvm/include/llvm/ADT/StringSet.h llvm/include/llvm/ADT/TypeSwitch.h llvm/include/llvm/Analysis/BlockFrequencyInfo.h -llvm/include/llvm/Analysis/CFLAliasAnalysisUtils.h -llvm/include/llvm/Analysis/CFLAndersAliasAnalysis.h -llvm/include/llvm/Analysis/CFLSteensAliasAnalysis.h llvm/include/llvm/Analysis/ConstraintSystem.h llvm/include/llvm/Analysis/CostModel.h llvm/include/llvm/Analysis/CycleAnalysis.h @@ -5720,9 +5717,6 @@ llvm/include/llvm-c/Transforms/PassBuilder.h llvm/include/llvm-c/Transforms/Scalar.h llvm/include/llvm-c/Transforms/Vectorize.h -llvm/lib/Analysis/CFLAndersAliasAnalysis.cpp -llvm/lib/Analysis/CFLGraph.h -llvm/lib/Analysis/CFLSteensAliasAnalysis.cpp llvm/lib/Analysis/CodeMetrics.cpp llvm/lib/Analysis/CycleAnalysis.cpp llvm/lib/Analysis/DDGPrinter.cpp diff --git a/llvm/include/llvm/Analysis/CFLAliasAnalysisUtils.h b/llvm/include/llvm/Analysis/CFLAliasAnalysisUtils.h deleted file mode 100644 --- a/llvm/include/llvm/Analysis/CFLAliasAnalysisUtils.h +++ /dev/null @@ -1,59 +0,0 @@ -//=- CFLAliasAnalysisUtils.h - Utilities for CFL Alias Analysis ----*- C++-*-=// -// -// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. -// See https://llvm.org/LICENSE.txt for license information. -// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception -// -//===----------------------------------------------------------------------===// -// \file -// These are the utilities/helpers used by the CFL Alias Analyses available in -// tree, i.e. Steensgaard's and Andersens'. -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_ANALYSIS_CFLALIASANALYSISUTILS_H -#define LLVM_ANALYSIS_CFLALIASANALYSISUTILS_H - -#include "llvm/IR/Argument.h" -#include "llvm/IR/Function.h" -#include "llvm/IR/ValueHandle.h" - -namespace llvm { - -namespace cflaa { - -template struct FunctionHandle final : public CallbackVH { - FunctionHandle(Function *Fn, AAResult *Result) - : CallbackVH(Fn), Result(Result) { - assert(Fn != nullptr); - assert(Result != nullptr); - } - - void deleted() override { removeSelfFromCache(); } - void allUsesReplacedWith(Value *) override { removeSelfFromCache(); } - -private: - AAResult *Result; - - void removeSelfFromCache() { - assert(Result != nullptr); - auto *Val = getValPtr(); - Result->evict(cast(Val)); - setValPtr(nullptr); - } -}; - -static inline const Function *parentFunctionOfValue(const 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 nullptr; -} -} // namespace cflaa -} // namespace llvm - -#endif // LLVM_ANALYSIS_CFLALIASANALYSISUTILS_H diff --git a/llvm/include/llvm/Analysis/CFLAndersAliasAnalysis.h b/llvm/include/llvm/Analysis/CFLAndersAliasAnalysis.h deleted file mode 100644 --- a/llvm/include/llvm/Analysis/CFLAndersAliasAnalysis.h +++ /dev/null @@ -1,125 +0,0 @@ -//==- CFLAndersAliasAnalysis.h - Unification-based Alias Analysis -*- C++-*-==// -// -// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. -// See https://llvm.org/LICENSE.txt for license information. -// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception -// -//===----------------------------------------------------------------------===// -/// \file -/// This is the interface for LLVM's inclusion-based alias analysis -/// implemented with CFL graph reachability. -/// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_ANALYSIS_CFLANDERSALIASANALYSIS_H -#define LLVM_ANALYSIS_CFLANDERSALIASANALYSIS_H - -#include "llvm/ADT/DenseMap.h" -#include "llvm/Analysis/AliasAnalysis.h" -#include "llvm/Analysis/CFLAliasAnalysisUtils.h" -#include "llvm/IR/PassManager.h" -#include "llvm/Pass.h" -#include -#include - -namespace llvm { - -template class Optional; -class Function; -class MemoryLocation; -class TargetLibraryInfo; - -namespace cflaa { - -struct AliasSummary; - -} // end namespace cflaa - -class CFLAndersAAResult : public AAResultBase { - class FunctionInfo; - -public: - explicit CFLAndersAAResult( - std::function GetTLI); - CFLAndersAAResult(CFLAndersAAResult &&RHS); - ~CFLAndersAAResult(); - - /// Handle invalidation events from the new pass manager. - /// By definition, this result is stateless and so remains valid. - bool invalidate(Function &, const PreservedAnalyses &, - FunctionAnalysisManager::Invalidator &) { - return false; - } - - /// Evict the given function from cache - void evict(const Function *Fn); - - /// Get the alias summary for the given function - /// Return nullptr if the summary is not found or not available - const cflaa::AliasSummary *getAliasSummary(const Function &); - - AliasResult query(const MemoryLocation &, const MemoryLocation &); - AliasResult alias(const MemoryLocation &, const MemoryLocation &, - AAQueryInfo &); - -private: - /// Ensures that the given function is available in the cache. - /// Returns the appropriate entry from the cache. - const Optional &ensureCached(const Function &); - - /// Inserts the given Function into the cache. - void scan(const Function &); - - /// Build summary for a given function - FunctionInfo buildInfoFrom(const Function &); - - std::function GetTLI; - - /// Cached mapping of Functions to their StratifiedSets. - /// If a function's sets are currently being built, it is marked - /// in the cache as an Optional without a value. This way, if we - /// have any kind of recursion, it is discernable from a function - /// that simply has empty sets. - DenseMap> Cache; - - std::forward_list> Handles; -}; - -/// Analysis pass providing a never-invalidated alias analysis result. -/// -/// FIXME: We really should refactor CFL to use the analysis more heavily, and -/// in particular to leverage invalidation to trigger re-computation. -class CFLAndersAA : public AnalysisInfoMixin { - friend AnalysisInfoMixin; - - static AnalysisKey Key; - -public: - using Result = CFLAndersAAResult; - - CFLAndersAAResult run(Function &F, FunctionAnalysisManager &AM); -}; - -/// Legacy wrapper pass to provide the CFLAndersAAResult object. -class CFLAndersAAWrapperPass : public ImmutablePass { - std::unique_ptr Result; - -public: - static char ID; - - CFLAndersAAWrapperPass(); - - CFLAndersAAResult &getResult() { return *Result; } - const CFLAndersAAResult &getResult() const { return *Result; } - - void initializePass() override; - void getAnalysisUsage(AnalysisUsage &AU) const override; -}; - -// createCFLAndersAAWrapperPass - This pass implements a set-based approach to -// alias analysis. -ImmutablePass *createCFLAndersAAWrapperPass(); - -} // end namespace llvm - -#endif // LLVM_ANALYSIS_CFLANDERSALIASANALYSIS_H diff --git a/llvm/include/llvm/Analysis/CFLSteensAliasAnalysis.h b/llvm/include/llvm/Analysis/CFLSteensAliasAnalysis.h deleted file mode 100644 --- a/llvm/include/llvm/Analysis/CFLSteensAliasAnalysis.h +++ /dev/null @@ -1,140 +0,0 @@ -//==- CFLSteensAliasAnalysis.h - Unification-based Alias Analysis -*- C++-*-==// -// -// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. -// See https://llvm.org/LICENSE.txt for license information. -// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception -// -//===----------------------------------------------------------------------===// -/// \file -/// This is the interface for LLVM's unification-based alias analysis -/// implemented with CFL graph reachability. -/// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_ANALYSIS_CFLSTEENSALIASANALYSIS_H -#define LLVM_ANALYSIS_CFLSTEENSALIASANALYSIS_H - -#include "llvm/ADT/DenseMap.h" -#include "llvm/Analysis/AliasAnalysis.h" -#include "llvm/Analysis/CFLAliasAnalysisUtils.h" -#include "llvm/Analysis/MemoryLocation.h" -#include "llvm/IR/PassManager.h" -#include "llvm/Pass.h" -#include -#include - -namespace llvm { - -class Function; -class TargetLibraryInfo; - -namespace cflaa { - -struct AliasSummary; - -} // end namespace cflaa - -class CFLSteensAAResult : public AAResultBase { - class FunctionInfo; - -public: - explicit CFLSteensAAResult( - std::function GetTLI); - CFLSteensAAResult(CFLSteensAAResult &&Arg); - ~CFLSteensAAResult(); - - /// Handle invalidation events from the new pass manager. - /// - /// By definition, this result is stateless and so remains valid. - bool invalidate(Function &, const PreservedAnalyses &, - FunctionAnalysisManager::Invalidator &) { - return false; - } - - /// Inserts the given Function into the cache. - void scan(Function *Fn); - - void evict(Function *Fn); - - /// Ensures that the given function is available in the cache. - /// Returns the appropriate entry from the cache. - const Optional &ensureCached(Function *Fn); - - /// Get the alias summary for the given function - /// Return nullptr if the summary is not found or not available - const cflaa::AliasSummary *getAliasSummary(Function &Fn); - - AliasResult query(const MemoryLocation &LocA, const MemoryLocation &LocB); - - AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB, - AAQueryInfo &AAQI) { - if (LocA.Ptr == LocB.Ptr) - return AliasResult::MustAlias; - - // Comparisons between global variables and other constants should be - // handled by BasicAA. - // CFLSteensAA may report NoAlias when comparing a GlobalValue and - // ConstantExpr, but every query needs to have at least one Value tied to a - // Function, and neither GlobalValues nor ConstantExprs are. - if (isa(LocA.Ptr) && isa(LocB.Ptr)) - return AAResultBase::alias(LocA, LocB, AAQI); - - AliasResult QueryResult = query(LocA, LocB); - if (QueryResult == AliasResult::MayAlias) - return AAResultBase::alias(LocA, LocB, AAQI); - - return QueryResult; - } - -private: - std::function GetTLI; - - /// Cached mapping of Functions to their StratifiedSets. - /// If a function's sets are currently being built, it is marked - /// in the cache as an Optional without a value. This way, if we - /// have any kind of recursion, it is discernable from a function - /// that simply has empty sets. - DenseMap> 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 AnalysisKey Key; - -public: - using Result = CFLSteensAAResult; - - CFLSteensAAResult run(Function &F, FunctionAnalysisManager &AM); -}; - -/// Legacy wrapper pass to provide the CFLSteensAAResult object. -class CFLSteensAAWrapperPass : public ImmutablePass { - std::unique_ptr Result; - -public: - static char ID; - - CFLSteensAAWrapperPass(); - - CFLSteensAAResult &getResult() { return *Result; } - const CFLSteensAAResult &getResult() const { return *Result; } - - void initializePass() override; - void getAnalysisUsage(AnalysisUsage &AU) const override; -}; - -// createCFLSteensAAWrapperPass - This pass implements a set-based approach to -// alias analysis. -ImmutablePass *createCFLSteensAAWrapperPass(); - -} // end namespace llvm - -#endif // LLVM_ANALYSIS_CFLSTEENSALIASANALYSIS_H diff --git a/llvm/include/llvm/CodeGen/CodeGenPassBuilder.h b/llvm/include/llvm/CodeGen/CodeGenPassBuilder.h --- a/llvm/include/llvm/CodeGen/CodeGenPassBuilder.h +++ b/llvm/include/llvm/CodeGen/CodeGenPassBuilder.h @@ -19,8 +19,6 @@ #include "llvm/ADT/StringRef.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/BasicAliasAnalysis.h" -#include "llvm/Analysis/CFLAndersAliasAnalysis.h" -#include "llvm/Analysis/CFLSteensAliasAnalysis.h" #include "llvm/Analysis/ScopedNoAliasAA.h" #include "llvm/Analysis/TargetTransformInfo.h" #include "llvm/Analysis/TypeBasedAliasAnalysis.h" @@ -483,27 +481,12 @@ return Error::success(); } -static inline AAManager registerAAAnalyses(CFLAAType UseCFLAA) { +static inline AAManager registerAAAnalyses() { AAManager AA; // The order in which these are registered determines their priority when // being queried. - switch (UseCFLAA) { - case CFLAAType::Steensgaard: - AA.registerFunctionAnalysis(); - break; - case CFLAAType::Andersen: - AA.registerFunctionAnalysis(); - break; - case CFLAAType::Both: - AA.registerFunctionAnalysis(); - AA.registerFunctionAnalysis(); - break; - default: - break; - } - // Basic AliasAnalysis support. // Add TypeBasedAliasAnalysis before BasicAliasAnalysis so that // BasicAliasAnalysis wins if they disagree. This is intended to help @@ -527,7 +510,7 @@ template void CodeGenPassBuilder::registerFunctionAnalyses( FunctionAnalysisManager &FAM) const { - FAM.registerPass([this] { return registerAAAnalyses(this->Opt.UseCFLAA); }); + FAM.registerPass([this] { return registerAAAnalyses(); }); #define FUNCTION_ANALYSIS(NAME, PASS_NAME, CONSTRUCTOR) \ FAM.registerPass([&] { return PASS_NAME CONSTRUCTOR; }); diff --git a/llvm/include/llvm/InitializePasses.h b/llvm/include/llvm/InitializePasses.h --- a/llvm/include/llvm/InitializePasses.h +++ b/llvm/include/llvm/InitializePasses.h @@ -84,8 +84,6 @@ void initializeCFGViewerLegacyPassPass(PassRegistry&); void initializeCFIFixupPass(PassRegistry&); void initializeCFIInstrInserterPass(PassRegistry&); -void initializeCFLAndersAAWrapperPassPass(PassRegistry&); -void initializeCFLSteensAAWrapperPassPass(PassRegistry&); void initializeCallGraphDOTPrinterPass(PassRegistry&); void initializeCallGraphPrinterLegacyPassPass(PassRegistry&); void initializeCallGraphViewerPass(PassRegistry&); diff --git a/llvm/include/llvm/LinkAllPasses.h b/llvm/include/llvm/LinkAllPasses.h --- a/llvm/include/llvm/LinkAllPasses.h +++ b/llvm/include/llvm/LinkAllPasses.h @@ -18,8 +18,6 @@ #include "llvm/Analysis/AliasAnalysisEvaluator.h" #include "llvm/Analysis/AliasSetTracker.h" #include "llvm/Analysis/BasicAliasAnalysis.h" -#include "llvm/Analysis/CFLAndersAliasAnalysis.h" -#include "llvm/Analysis/CFLSteensAliasAnalysis.h" #include "llvm/Analysis/CallPrinter.h" #include "llvm/Analysis/DomPrinter.h" #include "llvm/Analysis/GlobalsModRef.h" @@ -82,8 +80,6 @@ (void) llvm::createCallGraphDOTPrinterPass(); (void) llvm::createCallGraphViewerPass(); (void) llvm::createCFGSimplificationPass(); - (void) llvm::createCFLAndersAAWrapperPass(); - (void) llvm::createCFLSteensAAWrapperPass(); (void) llvm::createStructurizeCFGPass(); (void) llvm::createLibCallsShrinkWrapPass(); (void) llvm::createCalledValuePropagationPass(); diff --git a/llvm/include/llvm/Target/CGPassBuilderOption.h b/llvm/include/llvm/Target/CGPassBuilderOption.h --- a/llvm/include/llvm/Target/CGPassBuilderOption.h +++ b/llvm/include/llvm/Target/CGPassBuilderOption.h @@ -22,7 +22,6 @@ enum class RunOutliner { TargetDefault, AlwaysOutline, NeverOutline }; enum class RegAllocType { Default, Basic, Fast, Greedy, PBQP }; -enum class CFLAAType { None, Steensgaard, Andersen, Both }; // Not one-on-one but mostly corresponding to commandline options in // TargetPassConfig.cpp. @@ -49,7 +48,6 @@ RunOutliner EnableMachineOutliner = RunOutliner::TargetDefault; RegAllocType RegAlloc = RegAllocType::Default; - CFLAAType UseCFLAA = CFLAAType::None; std::optional EnableGlobalISelAbort; std::optional VerifyMachineCode; diff --git a/llvm/lib/Analysis/AliasAnalysis.cpp b/llvm/lib/Analysis/AliasAnalysis.cpp --- a/llvm/lib/Analysis/AliasAnalysis.cpp +++ b/llvm/lib/Analysis/AliasAnalysis.cpp @@ -26,8 +26,6 @@ #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/ADT/Statistic.h" #include "llvm/Analysis/BasicAliasAnalysis.h" -#include "llvm/Analysis/CFLAndersAliasAnalysis.h" -#include "llvm/Analysis/CFLSteensAliasAnalysis.h" #include "llvm/Analysis/CaptureTracking.h" #include "llvm/Analysis/GlobalsModRef.h" #include "llvm/Analysis/MemoryLocation.h" @@ -761,8 +759,6 @@ INITIALIZE_PASS_BEGIN(AAResultsWrapperPass, "aa", "Function Alias Analysis Results", false, true) INITIALIZE_PASS_DEPENDENCY(BasicAAWrapperPass) -INITIALIZE_PASS_DEPENDENCY(CFLAndersAAWrapperPass) -INITIALIZE_PASS_DEPENDENCY(CFLSteensAAWrapperPass) INITIALIZE_PASS_DEPENDENCY(ExternalAAWrapperPass) INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass) INITIALIZE_PASS_DEPENDENCY(SCEVAAWrapperPass) @@ -809,10 +805,6 @@ AAR->addAAResult(WrapperPass->getResult()); if (auto *WrapperPass = getAnalysisIfAvailable()) AAR->addAAResult(WrapperPass->getResult()); - 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 // well. @@ -837,8 +829,6 @@ AU.addUsedIfAvailable(); AU.addUsedIfAvailable(); AU.addUsedIfAvailable(); - AU.addUsedIfAvailable(); - AU.addUsedIfAvailable(); AU.addUsedIfAvailable(); } @@ -865,10 +855,6 @@ AAR.addAAResult(WrapperPass->getResult()); if (auto *WrapperPass = P.getAnalysisIfAvailable()) AAR.addAAResult(WrapperPass->getResult()); - if (auto *WrapperPass = P.getAnalysisIfAvailable()) - AAR.addAAResult(WrapperPass->getResult()); - if (auto *WrapperPass = P.getAnalysisIfAvailable()) - AAR.addAAResult(WrapperPass->getResult()); if (auto *WrapperPass = P.getAnalysisIfAvailable()) if (WrapperPass->CB) WrapperPass->CB(P, F, AAR); @@ -957,7 +943,5 @@ AU.addUsedIfAvailable(); AU.addUsedIfAvailable(); AU.addUsedIfAvailable(); - AU.addUsedIfAvailable(); - AU.addUsedIfAvailable(); AU.addUsedIfAvailable(); } diff --git a/llvm/lib/Analysis/Analysis.cpp b/llvm/lib/Analysis/Analysis.cpp --- a/llvm/lib/Analysis/Analysis.cpp +++ b/llvm/lib/Analysis/Analysis.cpp @@ -32,8 +32,6 @@ initializeCFGPrinterLegacyPassPass(Registry); initializeCFGOnlyViewerLegacyPassPass(Registry); initializeCFGOnlyPrinterLegacyPassPass(Registry); - initializeCFLAndersAAWrapperPassPass(Registry); - initializeCFLSteensAAWrapperPassPass(Registry); initializeCycleInfoWrapperPassPass(Registry); initializeDependenceAnalysisWrapperPassPass(Registry); initializeDelinearizationPass(Registry); diff --git a/llvm/lib/Analysis/CFLAndersAliasAnalysis.cpp b/llvm/lib/Analysis/CFLAndersAliasAnalysis.cpp deleted file mode 100644 --- a/llvm/lib/Analysis/CFLAndersAliasAnalysis.cpp +++ /dev/null @@ -1,931 +0,0 @@ -//===- CFLAndersAliasAnalysis.cpp - Unification-based Alias Analysis ------===// -// -// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. -// See https://llvm.org/LICENSE.txt for license information. -// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception -// -//===----------------------------------------------------------------------===// -// -// This file implements a CFL-based, summary-based alias analysis algorithm. It -// differs from CFLSteensAliasAnalysis in its inclusion-based nature while -// CFLSteensAliasAnalysis is unification-based. This pass has worse performance -// than CFLSteensAliasAnalysis (the worst case complexity of -// CFLAndersAliasAnalysis is cubic, while the worst case complexity of -// CFLSteensAliasAnalysis is almost linear), but it is able to yield more -// precise analysis result. The precision of this analysis is roughly the same -// as that of an one level context-sensitive Andersen's algorithm. -// -// The algorithm used here is based on recursive state machine matching scheme -// proposed in "Demand-driven alias analysis for C" by Xin Zheng and Radu -// Rugina. The general idea is to extend the traditional transitive closure -// algorithm to perform CFL matching along the way: instead of recording -// "whether X is reachable from Y", we keep track of "whether X is reachable -// from Y at state Z", where the "state" field indicates where we are in the CFL -// matching process. To understand the matching better, it is advisable to have -// the state machine shown in Figure 3 of the paper available when reading the -// codes: all we do here is to selectively expand the transitive closure by -// discarding edges that are not recognized by the state machine. -// -// There are two differences between our current implementation and the one -// described in the paper: -// - Our algorithm eagerly computes all alias pairs after the CFLGraph is built, -// while in the paper the authors did the computation in a demand-driven -// fashion. We did not implement the demand-driven algorithm due to the -// additional coding complexity and higher memory profile, but if we found it -// necessary we may switch to it eventually. -// - In the paper the authors use a state machine that does not distinguish -// value reads from value writes. For example, if Y is reachable from X at state -// S3, it may be the case that X is written into Y, or it may be the case that -// there's a third value Z that writes into both X and Y. To make that -// distinction (which is crucial in building function summary as well as -// retrieving mod-ref info), we choose to duplicate some of the states in the -// paper's proposed state machine. The duplication does not change the set the -// machine accepts. Given a pair of reachable values, it only provides more -// detailed information on which value is being written into and which is being -// read from. -// -//===----------------------------------------------------------------------===// - -// N.B. AliasAnalysis as a whole is phrased as a FunctionPass at the moment, and -// CFLAndersAA is interprocedural. This is *technically* A Bad Thing, because -// FunctionPasses are only allowed to inspect the Function that they're being -// run on. Realistically, this likely isn't a problem until we allow -// FunctionPasses to run concurrently. - -#include "llvm/Analysis/CFLAndersAliasAnalysis.h" -#include "AliasAnalysisSummary.h" -#include "CFLGraph.h" -#include "llvm/ADT/DenseMap.h" -#include "llvm/ADT/DenseMapInfo.h" -#include "llvm/ADT/DenseSet.h" -#include "llvm/ADT/Optional.h" -#include "llvm/ADT/STLExtras.h" -#include "llvm/ADT/SmallVector.h" -#include "llvm/ADT/iterator_range.h" -#include "llvm/Analysis/AliasAnalysis.h" -#include "llvm/Analysis/MemoryLocation.h" -#include "llvm/IR/Argument.h" -#include "llvm/IR/Function.h" -#include "llvm/IR/PassManager.h" -#include "llvm/IR/Type.h" -#include "llvm/InitializePasses.h" -#include "llvm/Pass.h" -#include "llvm/Support/Casting.h" -#include "llvm/Support/Compiler.h" -#include "llvm/Support/Debug.h" -#include "llvm/Support/raw_ostream.h" -#include -#include -#include -#include -#include -#include -#include -#include -#include - -using namespace llvm; -using namespace llvm::cflaa; - -#define DEBUG_TYPE "cfl-anders-aa" - -CFLAndersAAResult::CFLAndersAAResult( - std::function GetTLI) - : GetTLI(std::move(GetTLI)) {} -CFLAndersAAResult::CFLAndersAAResult(CFLAndersAAResult &&RHS) - : AAResultBase(std::move(RHS)), GetTLI(std::move(RHS.GetTLI)) {} -CFLAndersAAResult::~CFLAndersAAResult() = default; - -namespace { - -enum class MatchState : uint8_t { - // The following state represents S1 in the paper. - FlowFromReadOnly = 0, - // The following two states together represent S2 in the paper. - // The 'NoReadWrite' suffix indicates that there exists an alias path that - // does not contain assignment and reverse assignment edges. - // The 'ReadOnly' suffix indicates that there exists an alias path that - // contains reverse assignment edges only. - FlowFromMemAliasNoReadWrite, - FlowFromMemAliasReadOnly, - // The following two states together represent S3 in the paper. - // The 'WriteOnly' suffix indicates that there exists an alias path that - // contains assignment edges only. - // The 'ReadWrite' suffix indicates that there exists an alias path that - // contains both assignment and reverse assignment edges. Note that if X and Y - // are reachable at 'ReadWrite' state, it does NOT mean X is both read from - // and written to Y. Instead, it means that a third value Z is written to both - // X and Y. - FlowToWriteOnly, - FlowToReadWrite, - // The following two states together represent S4 in the paper. - FlowToMemAliasWriteOnly, - FlowToMemAliasReadWrite, -}; - -using StateSet = std::bitset<7>; - -const unsigned ReadOnlyStateMask = - (1U << static_cast(MatchState::FlowFromReadOnly)) | - (1U << static_cast(MatchState::FlowFromMemAliasReadOnly)); -const unsigned WriteOnlyStateMask = - (1U << static_cast(MatchState::FlowToWriteOnly)) | - (1U << static_cast(MatchState::FlowToMemAliasWriteOnly)); - -// A pair that consists of a value and an offset -struct OffsetValue { - const Value *Val; - int64_t Offset; -}; - -bool operator==(OffsetValue LHS, OffsetValue RHS) { - return LHS.Val == RHS.Val && LHS.Offset == RHS.Offset; -} -bool operator<(OffsetValue LHS, OffsetValue RHS) { - return std::less()(LHS.Val, RHS.Val) || - (LHS.Val == RHS.Val && LHS.Offset < RHS.Offset); -} - -// A pair that consists of an InstantiatedValue and an offset -struct OffsetInstantiatedValue { - InstantiatedValue IVal; - int64_t Offset; -}; - -bool operator==(OffsetInstantiatedValue LHS, OffsetInstantiatedValue RHS) { - return LHS.IVal == RHS.IVal && LHS.Offset == RHS.Offset; -} - -// We use ReachabilitySet to keep track of value aliases (The nonterminal "V" in -// the paper) during the analysis. -class ReachabilitySet { - using ValueStateMap = DenseMap; - using ValueReachMap = DenseMap; - - ValueReachMap ReachMap; - -public: - using const_valuestate_iterator = ValueStateMap::const_iterator; - using const_value_iterator = ValueReachMap::const_iterator; - - // Insert edge 'From->To' at state 'State' - bool insert(InstantiatedValue From, InstantiatedValue To, MatchState State) { - assert(From != To); - auto &States = ReachMap[To][From]; - auto Idx = static_cast(State); - if (!States.test(Idx)) { - States.set(Idx); - return true; - } - return false; - } - - // Return the set of all ('From', 'State') pair for a given node 'To' - iterator_range - reachableValueAliases(InstantiatedValue V) const { - auto Itr = ReachMap.find(V); - if (Itr == ReachMap.end()) - return make_range(const_valuestate_iterator(), - const_valuestate_iterator()); - return make_range(Itr->second.begin(), - Itr->second.end()); - } - - iterator_range value_mappings() const { - return make_range(ReachMap.begin(), ReachMap.end()); - } -}; - -// We use AliasMemSet to keep track of all memory aliases (the nonterminal "M" -// in the paper) during the analysis. -class AliasMemSet { - using MemSet = DenseSet; - using MemMapType = DenseMap; - - MemMapType MemMap; - -public: - using const_mem_iterator = MemSet::const_iterator; - - bool insert(InstantiatedValue LHS, InstantiatedValue RHS) { - // Top-level values can never be memory aliases because one cannot take the - // addresses of them - assert(LHS.DerefLevel > 0 && RHS.DerefLevel > 0); - return MemMap[LHS].insert(RHS).second; - } - - const MemSet *getMemoryAliases(InstantiatedValue V) const { - auto Itr = MemMap.find(V); - if (Itr == MemMap.end()) - return nullptr; - return &Itr->second; - } -}; - -// We use AliasAttrMap to keep track of the AliasAttr of each node. -class AliasAttrMap { - using MapType = DenseMap; - - MapType AttrMap; - -public: - using const_iterator = MapType::const_iterator; - - bool add(InstantiatedValue V, AliasAttrs Attr) { - auto &OldAttr = AttrMap[V]; - auto NewAttr = OldAttr | Attr; - if (OldAttr == NewAttr) - return false; - OldAttr = NewAttr; - return true; - } - - AliasAttrs getAttrs(InstantiatedValue V) const { - AliasAttrs Attr; - auto Itr = AttrMap.find(V); - if (Itr != AttrMap.end()) - Attr = Itr->second; - return Attr; - } - - iterator_range mappings() const { - return make_range(AttrMap.begin(), AttrMap.end()); - } -}; - -struct WorkListItem { - InstantiatedValue From; - InstantiatedValue To; - MatchState State; -}; - -struct ValueSummary { - struct Record { - InterfaceValue IValue; - unsigned DerefLevel; - }; - SmallVector FromRecords, ToRecords; -}; - -} // end anonymous namespace - -namespace llvm { - -// Specialize DenseMapInfo for OffsetValue. -template <> struct DenseMapInfo { - static OffsetValue getEmptyKey() { - return OffsetValue{DenseMapInfo::getEmptyKey(), - DenseMapInfo::getEmptyKey()}; - } - - static OffsetValue getTombstoneKey() { - return OffsetValue{DenseMapInfo::getTombstoneKey(), - DenseMapInfo::getEmptyKey()}; - } - - static unsigned getHashValue(const OffsetValue &OVal) { - return DenseMapInfo>::getHashValue( - std::make_pair(OVal.Val, OVal.Offset)); - } - - static bool isEqual(const OffsetValue &LHS, const OffsetValue &RHS) { - return LHS == RHS; - } -}; - -// Specialize DenseMapInfo for OffsetInstantiatedValue. -template <> struct DenseMapInfo { - static OffsetInstantiatedValue getEmptyKey() { - return OffsetInstantiatedValue{ - DenseMapInfo::getEmptyKey(), - DenseMapInfo::getEmptyKey()}; - } - - static OffsetInstantiatedValue getTombstoneKey() { - return OffsetInstantiatedValue{ - DenseMapInfo::getTombstoneKey(), - DenseMapInfo::getEmptyKey()}; - } - - static unsigned getHashValue(const OffsetInstantiatedValue &OVal) { - return DenseMapInfo>::getHashValue( - std::make_pair(OVal.IVal, OVal.Offset)); - } - - static bool isEqual(const OffsetInstantiatedValue &LHS, - const OffsetInstantiatedValue &RHS) { - return LHS == RHS; - } -}; - -} // end namespace llvm - -class CFLAndersAAResult::FunctionInfo { - /// Map a value to other values that may alias it - /// Since the alias relation is symmetric, to save some space we assume values - /// are properly ordered: if a and b alias each other, and a < b, then b is in - /// AliasMap[a] but not vice versa. - DenseMap> AliasMap; - - /// Map a value to its corresponding AliasAttrs - DenseMap AttrMap; - - /// Summary of externally visible effects. - AliasSummary Summary; - - Optional getAttrs(const Value *) const; - -public: - FunctionInfo(const Function &, const SmallVectorImpl &, - const ReachabilitySet &, const AliasAttrMap &); - - bool mayAlias(const Value *, LocationSize, const Value *, LocationSize) const; - const AliasSummary &getAliasSummary() const { return Summary; } -}; - -static bool hasReadOnlyState(StateSet Set) { - return (Set & StateSet(ReadOnlyStateMask)).any(); -} - -static bool hasWriteOnlyState(StateSet Set) { - return (Set & StateSet(WriteOnlyStateMask)).any(); -} - -static std::optional -getInterfaceValue(InstantiatedValue IValue, - const SmallVectorImpl &RetVals) { - auto Val = IValue.Val; - - std::optional Index; - if (auto Arg = dyn_cast(Val)) - Index = Arg->getArgNo() + 1; - else if (is_contained(RetVals, Val)) - Index = 0; - - if (Index) - return InterfaceValue{*Index, IValue.DerefLevel}; - return std::nullopt; -} - -static void populateAttrMap(DenseMap &AttrMap, - const AliasAttrMap &AMap) { - for (const auto &Mapping : AMap.mappings()) { - auto IVal = Mapping.first; - - // Insert IVal into the map - auto &Attr = AttrMap[IVal.Val]; - // AttrMap only cares about top-level values - if (IVal.DerefLevel == 0) - Attr |= Mapping.second; - } -} - -static void -populateAliasMap(DenseMap> &AliasMap, - const ReachabilitySet &ReachSet) { - for (const auto &OuterMapping : ReachSet.value_mappings()) { - // AliasMap only cares about top-level values - if (OuterMapping.first.DerefLevel > 0) - continue; - - auto Val = OuterMapping.first.Val; - auto &AliasList = AliasMap[Val]; - for (const auto &InnerMapping : OuterMapping.second) { - // Again, AliasMap only cares about top-level values - if (InnerMapping.first.DerefLevel == 0) - AliasList.push_back(OffsetValue{InnerMapping.first.Val, UnknownOffset}); - } - - // Sort AliasList for faster lookup - llvm::sort(AliasList); - } -} - -static void populateExternalRelations( - SmallVectorImpl &ExtRelations, const Function &Fn, - const SmallVectorImpl &RetVals, const ReachabilitySet &ReachSet) { - // If a function only returns one of its argument X, then X will be both an - // argument and a return value at the same time. This is an edge case that - // needs special handling here. - for (const auto &Arg : Fn.args()) { - if (is_contained(RetVals, &Arg)) { - auto ArgVal = InterfaceValue{Arg.getArgNo() + 1, 0}; - auto RetVal = InterfaceValue{0, 0}; - ExtRelations.push_back(ExternalRelation{ArgVal, RetVal, 0}); - } - } - - // Below is the core summary construction logic. - // A naive solution of adding only the value aliases that are parameters or - // return values in ReachSet to the summary won't work: It is possible that a - // parameter P is written into an intermediate value I, and the function - // subsequently returns *I. In that case, *I is does not value alias anything - // in ReachSet, and the naive solution will miss a summary edge from (P, 1) to - // (I, 1). - // To account for the aforementioned case, we need to check each non-parameter - // and non-return value for the possibility of acting as an intermediate. - // 'ValueMap' here records, for each value, which InterfaceValues read from or - // write into it. If both the read list and the write list of a given value - // are non-empty, we know that a particular value is an intermidate and we - // need to add summary edges from the writes to the reads. - DenseMap ValueMap; - for (const auto &OuterMapping : ReachSet.value_mappings()) { - if (auto Dst = getInterfaceValue(OuterMapping.first, RetVals)) { - for (const auto &InnerMapping : OuterMapping.second) { - // If Src is a param/return value, we get a same-level assignment. - if (auto Src = getInterfaceValue(InnerMapping.first, RetVals)) { - // This may happen if both Dst and Src are return values - if (*Dst == *Src) - continue; - - if (hasReadOnlyState(InnerMapping.second)) - ExtRelations.push_back(ExternalRelation{*Dst, *Src, UnknownOffset}); - // No need to check for WriteOnly state, since ReachSet is symmetric - } else { - // If Src is not a param/return, add it to ValueMap - auto SrcIVal = InnerMapping.first; - if (hasReadOnlyState(InnerMapping.second)) - ValueMap[SrcIVal.Val].FromRecords.push_back( - ValueSummary::Record{*Dst, SrcIVal.DerefLevel}); - if (hasWriteOnlyState(InnerMapping.second)) - ValueMap[SrcIVal.Val].ToRecords.push_back( - ValueSummary::Record{*Dst, SrcIVal.DerefLevel}); - } - } - } - } - - for (const auto &Mapping : ValueMap) { - for (const auto &FromRecord : Mapping.second.FromRecords) { - for (const auto &ToRecord : Mapping.second.ToRecords) { - auto ToLevel = ToRecord.DerefLevel; - auto FromLevel = FromRecord.DerefLevel; - // Same-level assignments should have already been processed by now - if (ToLevel == FromLevel) - continue; - - auto SrcIndex = FromRecord.IValue.Index; - auto SrcLevel = FromRecord.IValue.DerefLevel; - auto DstIndex = ToRecord.IValue.Index; - auto DstLevel = ToRecord.IValue.DerefLevel; - if (ToLevel > FromLevel) - SrcLevel += ToLevel - FromLevel; - else - DstLevel += FromLevel - ToLevel; - - ExtRelations.push_back(ExternalRelation{ - InterfaceValue{SrcIndex, SrcLevel}, - InterfaceValue{DstIndex, DstLevel}, UnknownOffset}); - } - } - } - - // Remove duplicates in ExtRelations - llvm::sort(ExtRelations); - ExtRelations.erase(std::unique(ExtRelations.begin(), ExtRelations.end()), - ExtRelations.end()); -} - -static void populateExternalAttributes( - SmallVectorImpl &ExtAttributes, const Function &Fn, - const SmallVectorImpl &RetVals, const AliasAttrMap &AMap) { - for (const auto &Mapping : AMap.mappings()) { - if (auto IVal = getInterfaceValue(Mapping.first, RetVals)) { - auto Attr = getExternallyVisibleAttrs(Mapping.second); - if (Attr.any()) - ExtAttributes.push_back(ExternalAttribute{*IVal, Attr}); - } - } -} - -CFLAndersAAResult::FunctionInfo::FunctionInfo( - const Function &Fn, const SmallVectorImpl &RetVals, - const ReachabilitySet &ReachSet, const AliasAttrMap &AMap) { - populateAttrMap(AttrMap, AMap); - populateExternalAttributes(Summary.RetParamAttributes, Fn, RetVals, AMap); - populateAliasMap(AliasMap, ReachSet); - populateExternalRelations(Summary.RetParamRelations, Fn, RetVals, ReachSet); -} - -Optional -CFLAndersAAResult::FunctionInfo::getAttrs(const Value *V) const { - assert(V != nullptr); - - auto Itr = AttrMap.find(V); - if (Itr != AttrMap.end()) - return Itr->second; - return std::nullopt; -} - -bool CFLAndersAAResult::FunctionInfo::mayAlias( - const Value *LHS, LocationSize MaybeLHSSize, const Value *RHS, - LocationSize MaybeRHSSize) const { - assert(LHS && RHS); - - // Check if we've seen LHS and RHS before. Sometimes LHS or RHS can be created - // after the analysis gets executed, and we want to be conservative in those - // cases. - auto MaybeAttrsA = getAttrs(LHS); - auto MaybeAttrsB = getAttrs(RHS); - if (!MaybeAttrsA || !MaybeAttrsB) - return true; - - // Check AliasAttrs before AliasMap lookup since it's cheaper - auto AttrsA = *MaybeAttrsA; - auto AttrsB = *MaybeAttrsB; - if (hasUnknownOrCallerAttr(AttrsA)) - return AttrsB.any(); - if (hasUnknownOrCallerAttr(AttrsB)) - return AttrsA.any(); - if (isGlobalOrArgAttr(AttrsA)) - return isGlobalOrArgAttr(AttrsB); - if (isGlobalOrArgAttr(AttrsB)) - return isGlobalOrArgAttr(AttrsA); - - // At this point both LHS and RHS should point to locally allocated objects - - auto Itr = AliasMap.find(LHS); - if (Itr != AliasMap.end()) { - - // Find out all (X, Offset) where X == RHS - auto Comparator = [](OffsetValue LHS, OffsetValue RHS) { - return std::less()(LHS.Val, RHS.Val); - }; -#ifdef EXPENSIVE_CHECKS - assert(llvm::is_sorted(Itr->second, Comparator)); -#endif - auto RangePair = std::equal_range(Itr->second.begin(), Itr->second.end(), - OffsetValue{RHS, 0}, Comparator); - - if (RangePair.first != RangePair.second) { - // Be conservative about unknown sizes - if (!MaybeLHSSize.hasValue() || !MaybeRHSSize.hasValue()) - return true; - - const uint64_t LHSSize = MaybeLHSSize.getValue(); - const uint64_t RHSSize = MaybeRHSSize.getValue(); - - for (const auto &OVal : make_range(RangePair)) { - // Be conservative about UnknownOffset - if (OVal.Offset == UnknownOffset) - return true; - - // We know that LHS aliases (RHS + OVal.Offset) if the control flow - // reaches here. The may-alias query essentially becomes integer - // range-overlap queries over two ranges [OVal.Offset, OVal.Offset + - // LHSSize) and [0, RHSSize). - - // Try to be conservative on super large offsets - if (LLVM_UNLIKELY(LHSSize > INT64_MAX || RHSSize > INT64_MAX)) - return true; - - auto LHSStart = OVal.Offset; - // FIXME: Do we need to guard against integer overflow? - auto LHSEnd = OVal.Offset + static_cast(LHSSize); - auto RHSStart = 0; - auto RHSEnd = static_cast(RHSSize); - if (LHSEnd > RHSStart && LHSStart < RHSEnd) - return true; - } - } - } - - return false; -} - -static void propagate(InstantiatedValue From, InstantiatedValue To, - MatchState State, ReachabilitySet &ReachSet, - std::vector &WorkList) { - if (From == To) - return; - if (ReachSet.insert(From, To, State)) - WorkList.push_back(WorkListItem{From, To, State}); -} - -static void initializeWorkList(std::vector &WorkList, - ReachabilitySet &ReachSet, - const CFLGraph &Graph) { - for (const auto &Mapping : Graph.value_mappings()) { - auto Val = Mapping.first; - auto &ValueInfo = Mapping.second; - assert(ValueInfo.getNumLevels() > 0); - - // Insert all immediate assignment neighbors to the worklist - for (unsigned I = 0, E = ValueInfo.getNumLevels(); I < E; ++I) { - auto Src = InstantiatedValue{Val, I}; - // If there's an assignment edge from X to Y, it means Y is reachable from - // X at S3 and X is reachable from Y at S1 - for (const auto &Edge : ValueInfo.getNodeInfoAtLevel(I).Edges) { - propagate(Edge.Other, Src, MatchState::FlowFromReadOnly, ReachSet, - WorkList); - propagate(Src, Edge.Other, MatchState::FlowToWriteOnly, ReachSet, - WorkList); - } - } - } -} - -static std::optional getNodeBelow(const CFLGraph &Graph, - InstantiatedValue V) { - auto NodeBelow = InstantiatedValue{V.Val, V.DerefLevel + 1}; - if (Graph.getNode(NodeBelow)) - return NodeBelow; - return std::nullopt; -} - -static void processWorkListItem(const WorkListItem &Item, const CFLGraph &Graph, - ReachabilitySet &ReachSet, AliasMemSet &MemSet, - std::vector &WorkList) { - auto FromNode = Item.From; - auto ToNode = Item.To; - - auto NodeInfo = Graph.getNode(ToNode); - assert(NodeInfo != nullptr); - - // TODO: propagate field offsets - - // FIXME: Here is a neat trick we can do: since both ReachSet and MemSet holds - // relations that are symmetric, we could actually cut the storage by half by - // sorting FromNode and ToNode before insertion happens. - - // The newly added value alias pair may potentially generate more memory - // alias pairs. Check for them here. - auto FromNodeBelow = getNodeBelow(Graph, FromNode); - auto ToNodeBelow = getNodeBelow(Graph, ToNode); - if (FromNodeBelow && ToNodeBelow && - MemSet.insert(*FromNodeBelow, *ToNodeBelow)) { - propagate(*FromNodeBelow, *ToNodeBelow, - MatchState::FlowFromMemAliasNoReadWrite, ReachSet, WorkList); - for (const auto &Mapping : ReachSet.reachableValueAliases(*FromNodeBelow)) { - auto Src = Mapping.first; - auto MemAliasPropagate = [&](MatchState FromState, MatchState ToState) { - if (Mapping.second.test(static_cast(FromState))) - propagate(Src, *ToNodeBelow, ToState, ReachSet, WorkList); - }; - - MemAliasPropagate(MatchState::FlowFromReadOnly, - MatchState::FlowFromMemAliasReadOnly); - MemAliasPropagate(MatchState::FlowToWriteOnly, - MatchState::FlowToMemAliasWriteOnly); - MemAliasPropagate(MatchState::FlowToReadWrite, - MatchState::FlowToMemAliasReadWrite); - } - } - - // This is the core of the state machine walking algorithm. We expand ReachSet - // based on which state we are at (which in turn dictates what edges we - // should examine) - // From a high-level point of view, the state machine here guarantees two - // properties: - // - If *X and *Y are memory aliases, then X and Y are value aliases - // - If Y is an alias of X, then reverse assignment edges (if there is any) - // should precede any assignment edges on the path from X to Y. - auto NextAssignState = [&](MatchState State) { - for (const auto &AssignEdge : NodeInfo->Edges) - propagate(FromNode, AssignEdge.Other, State, ReachSet, WorkList); - }; - auto NextRevAssignState = [&](MatchState State) { - for (const auto &RevAssignEdge : NodeInfo->ReverseEdges) - propagate(FromNode, RevAssignEdge.Other, State, ReachSet, WorkList); - }; - auto NextMemState = [&](MatchState State) { - if (auto AliasSet = MemSet.getMemoryAliases(ToNode)) { - for (const auto &MemAlias : *AliasSet) - propagate(FromNode, MemAlias, State, ReachSet, WorkList); - } - }; - - switch (Item.State) { - case MatchState::FlowFromReadOnly: - NextRevAssignState(MatchState::FlowFromReadOnly); - NextAssignState(MatchState::FlowToReadWrite); - NextMemState(MatchState::FlowFromMemAliasReadOnly); - break; - - case MatchState::FlowFromMemAliasNoReadWrite: - NextRevAssignState(MatchState::FlowFromReadOnly); - NextAssignState(MatchState::FlowToWriteOnly); - break; - - case MatchState::FlowFromMemAliasReadOnly: - NextRevAssignState(MatchState::FlowFromReadOnly); - NextAssignState(MatchState::FlowToReadWrite); - break; - - case MatchState::FlowToWriteOnly: - NextAssignState(MatchState::FlowToWriteOnly); - NextMemState(MatchState::FlowToMemAliasWriteOnly); - break; - - case MatchState::FlowToReadWrite: - NextAssignState(MatchState::FlowToReadWrite); - NextMemState(MatchState::FlowToMemAliasReadWrite); - break; - - case MatchState::FlowToMemAliasWriteOnly: - NextAssignState(MatchState::FlowToWriteOnly); - break; - - case MatchState::FlowToMemAliasReadWrite: - NextAssignState(MatchState::FlowToReadWrite); - break; - } -} - -static AliasAttrMap buildAttrMap(const CFLGraph &Graph, - const ReachabilitySet &ReachSet) { - AliasAttrMap AttrMap; - std::vector WorkList, NextList; - - // Initialize each node with its original AliasAttrs in CFLGraph - for (const auto &Mapping : Graph.value_mappings()) { - auto Val = Mapping.first; - auto &ValueInfo = Mapping.second; - for (unsigned I = 0, E = ValueInfo.getNumLevels(); I < E; ++I) { - auto Node = InstantiatedValue{Val, I}; - AttrMap.add(Node, ValueInfo.getNodeInfoAtLevel(I).Attr); - WorkList.push_back(Node); - } - } - - while (!WorkList.empty()) { - for (const auto &Dst : WorkList) { - auto DstAttr = AttrMap.getAttrs(Dst); - if (DstAttr.none()) - continue; - - // Propagate attr on the same level - for (const auto &Mapping : ReachSet.reachableValueAliases(Dst)) { - auto Src = Mapping.first; - if (AttrMap.add(Src, DstAttr)) - NextList.push_back(Src); - } - - // Propagate attr to the levels below - auto DstBelow = getNodeBelow(Graph, Dst); - while (DstBelow) { - if (AttrMap.add(*DstBelow, DstAttr)) { - NextList.push_back(*DstBelow); - break; - } - DstBelow = getNodeBelow(Graph, *DstBelow); - } - } - WorkList.swap(NextList); - NextList.clear(); - } - - return AttrMap; -} - -CFLAndersAAResult::FunctionInfo -CFLAndersAAResult::buildInfoFrom(const Function &Fn) { - CFLGraphBuilder GraphBuilder( - *this, GetTLI(const_cast(Fn)), - // Cast away the constness here due to GraphBuilder's API requirement - const_cast(Fn)); - auto &Graph = GraphBuilder.getCFLGraph(); - - ReachabilitySet ReachSet; - AliasMemSet MemSet; - - std::vector WorkList, NextList; - initializeWorkList(WorkList, ReachSet, Graph); - // TODO: make sure we don't stop before the fix point is reached - while (!WorkList.empty()) { - for (const auto &Item : WorkList) - processWorkListItem(Item, Graph, ReachSet, MemSet, NextList); - - NextList.swap(WorkList); - NextList.clear(); - } - - // Now that we have all the reachability info, propagate AliasAttrs according - // to it - auto IValueAttrMap = buildAttrMap(Graph, ReachSet); - - return FunctionInfo(Fn, GraphBuilder.getReturnValues(), ReachSet, - std::move(IValueAttrMap)); -} - -void CFLAndersAAResult::scan(const Function &Fn) { - auto InsertPair = Cache.insert(std::make_pair(&Fn, Optional())); - (void)InsertPair; - assert(InsertPair.second && - "Trying to scan a function that has already been cached"); - - // Note that we can't do Cache[Fn] = buildSetsFrom(Fn) here: the function call - // may get evaluated after operator[], potentially triggering a DenseMap - // resize and invalidating the reference returned by operator[] - auto FunInfo = buildInfoFrom(Fn); - Cache[&Fn] = std::move(FunInfo); - Handles.emplace_front(const_cast(&Fn), this); -} - -void CFLAndersAAResult::evict(const Function *Fn) { Cache.erase(Fn); } - -const Optional & -CFLAndersAAResult::ensureCached(const Function &Fn) { - auto Iter = Cache.find(&Fn); - if (Iter == Cache.end()) { - scan(Fn); - Iter = Cache.find(&Fn); - assert(Iter != Cache.end()); - assert(Iter->second); - } - return Iter->second; -} - -const AliasSummary *CFLAndersAAResult::getAliasSummary(const Function &Fn) { - auto &FunInfo = ensureCached(Fn); - if (FunInfo) - return &FunInfo->getAliasSummary(); - else - return nullptr; -} - -AliasResult CFLAndersAAResult::query(const MemoryLocation &LocA, - const MemoryLocation &LocB) { - auto *ValA = LocA.Ptr; - auto *ValB = LocB.Ptr; - - if (!ValA->getType()->isPointerTy() || !ValB->getType()->isPointerTy()) - return AliasResult::NoAlias; - - auto *Fn = parentFunctionOfValue(ValA); - if (!Fn) { - Fn = parentFunctionOfValue(ValB); - if (!Fn) { - // The only times this is known to happen are when globals + InlineAsm are - // involved - LLVM_DEBUG( - dbgs() - << "CFLAndersAA: could not extract parent function information.\n"); - return AliasResult::MayAlias; - } - } else { - assert(!parentFunctionOfValue(ValB) || parentFunctionOfValue(ValB) == Fn); - } - - assert(Fn != nullptr); - auto &FunInfo = ensureCached(*Fn); - - // AliasMap lookup - if (FunInfo->mayAlias(ValA, LocA.Size, ValB, LocB.Size)) - return AliasResult::MayAlias; - return AliasResult::NoAlias; -} - -AliasResult CFLAndersAAResult::alias(const MemoryLocation &LocA, - const MemoryLocation &LocB, - AAQueryInfo &AAQI) { - if (LocA.Ptr == LocB.Ptr) - return AliasResult::MustAlias; - - // Comparisons between global variables and other constants should be - // handled by BasicAA. - // CFLAndersAA may report NoAlias when comparing a GlobalValue and - // ConstantExpr, but every query needs to have at least one Value tied to a - // Function, and neither GlobalValues nor ConstantExprs are. - if (isa(LocA.Ptr) && isa(LocB.Ptr)) - return AAResultBase::alias(LocA, LocB, AAQI); - - AliasResult QueryResult = query(LocA, LocB); - if (QueryResult == AliasResult::MayAlias) - return AAResultBase::alias(LocA, LocB, AAQI); - - return QueryResult; -} - -AnalysisKey CFLAndersAA::Key; - -CFLAndersAAResult CFLAndersAA::run(Function &F, FunctionAnalysisManager &AM) { - auto GetTLI = [&AM](Function &F) -> TargetLibraryInfo & { - return AM.getResult(F); - }; - return CFLAndersAAResult(GetTLI); -} - -char CFLAndersAAWrapperPass::ID = 0; -INITIALIZE_PASS(CFLAndersAAWrapperPass, "cfl-anders-aa", - "Inclusion-Based CFL Alias Analysis", false, true) - -ImmutablePass *llvm::createCFLAndersAAWrapperPass() { - return new CFLAndersAAWrapperPass(); -} - -CFLAndersAAWrapperPass::CFLAndersAAWrapperPass() : ImmutablePass(ID) { - initializeCFLAndersAAWrapperPassPass(*PassRegistry::getPassRegistry()); -} - -void CFLAndersAAWrapperPass::initializePass() { - auto GetTLI = [this](Function &F) -> TargetLibraryInfo & { - return this->getAnalysis().getTLI(F); - }; - Result.reset(new CFLAndersAAResult(GetTLI)); -} - -void CFLAndersAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { - AU.setPreservesAll(); - AU.addRequired(); -} diff --git a/llvm/lib/Analysis/CFLGraph.h b/llvm/lib/Analysis/CFLGraph.h deleted file mode 100644 --- a/llvm/lib/Analysis/CFLGraph.h +++ /dev/null @@ -1,668 +0,0 @@ -//===- CFLGraph.h - Abstract stratified sets implementation. -----*- C++-*-===// -// -// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. -// See https://llvm.org/LICENSE.txt for license information. -// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception -// -//===----------------------------------------------------------------------===// -// -/// \file -/// This file defines CFLGraph, an auxiliary data structure used by CFL-based -/// alias analysis. -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_LIB_ANALYSIS_CFLGRAPH_H -#define LLVM_LIB_ANALYSIS_CFLGRAPH_H - -#include "AliasAnalysisSummary.h" -#include "llvm/ADT/APInt.h" -#include "llvm/ADT/DenseMap.h" -#include "llvm/ADT/SmallVector.h" -#include "llvm/ADT/iterator_range.h" -#include "llvm/Analysis/MemoryBuiltins.h" -#include "llvm/Analysis/TargetLibraryInfo.h" -#include "llvm/IR/Argument.h" -#include "llvm/IR/BasicBlock.h" -#include "llvm/IR/Constants.h" -#include "llvm/IR/DataLayout.h" -#include "llvm/IR/Function.h" -#include "llvm/IR/GlobalValue.h" -#include "llvm/IR/InstVisitor.h" -#include "llvm/IR/InstrTypes.h" -#include "llvm/IR/Instruction.h" -#include "llvm/IR/Instructions.h" -#include "llvm/IR/Operator.h" -#include "llvm/IR/Type.h" -#include "llvm/IR/Value.h" -#include "llvm/Support/Casting.h" -#include "llvm/Support/ErrorHandling.h" -#include -#include -#include - -namespace llvm { -namespace cflaa { - -/// The Program Expression Graph (PEG) of CFL analysis -/// CFLGraph is auxiliary data structure used by CFL-based alias analysis to -/// describe flow-insensitive pointer-related behaviors. Given an LLVM function, -/// the main purpose of this graph is to abstract away unrelated facts and -/// translate the rest into a form that can be easily digested by CFL analyses. -/// Each Node in the graph is an InstantiatedValue, and each edge represent a -/// pointer assignment between InstantiatedValue. Pointer -/// references/dereferences are not explicitly stored in the graph: we -/// implicitly assume that for each node (X, I) it has a dereference edge to (X, -/// I+1) and a reference edge to (X, I-1). -class CFLGraph { -public: - using Node = InstantiatedValue; - - struct Edge { - Node Other; - int64_t Offset; - }; - - using EdgeList = std::vector; - - struct NodeInfo { - EdgeList Edges, ReverseEdges; - AliasAttrs Attr; - }; - - class ValueInfo { - std::vector Levels; - - public: - bool addNodeToLevel(unsigned Level) { - auto NumLevels = Levels.size(); - if (NumLevels > Level) - return false; - Levels.resize(Level + 1); - return true; - } - - NodeInfo &getNodeInfoAtLevel(unsigned Level) { - assert(Level < Levels.size()); - return Levels[Level]; - } - const NodeInfo &getNodeInfoAtLevel(unsigned Level) const { - assert(Level < Levels.size()); - return Levels[Level]; - } - - unsigned getNumLevels() const { return Levels.size(); } - }; - -private: - using ValueMap = DenseMap; - - ValueMap ValueImpls; - - NodeInfo *getNode(Node N) { - auto Itr = ValueImpls.find(N.Val); - if (Itr == ValueImpls.end() || Itr->second.getNumLevels() <= N.DerefLevel) - return nullptr; - return &Itr->second.getNodeInfoAtLevel(N.DerefLevel); - } - -public: - using const_value_iterator = ValueMap::const_iterator; - - bool addNode(Node N, AliasAttrs Attr = AliasAttrs()) { - assert(N.Val != nullptr); - auto &ValInfo = ValueImpls[N.Val]; - auto Changed = ValInfo.addNodeToLevel(N.DerefLevel); - ValInfo.getNodeInfoAtLevel(N.DerefLevel).Attr |= Attr; - return Changed; - } - - void addAttr(Node N, AliasAttrs Attr) { - auto *Info = getNode(N); - assert(Info != nullptr); - Info->Attr |= Attr; - } - - void addEdge(Node From, Node To, int64_t Offset = 0) { - auto *FromInfo = getNode(From); - assert(FromInfo != nullptr); - auto *ToInfo = getNode(To); - assert(ToInfo != nullptr); - - FromInfo->Edges.push_back(Edge{To, Offset}); - ToInfo->ReverseEdges.push_back(Edge{From, Offset}); - } - - const NodeInfo *getNode(Node N) const { - auto Itr = ValueImpls.find(N.Val); - if (Itr == ValueImpls.end() || Itr->second.getNumLevels() <= N.DerefLevel) - return nullptr; - return &Itr->second.getNodeInfoAtLevel(N.DerefLevel); - } - - AliasAttrs attrFor(Node N) const { - auto *Info = getNode(N); - assert(Info != nullptr); - return Info->Attr; - } - - iterator_range value_mappings() const { - return make_range(ValueImpls.begin(), - ValueImpls.end()); - } -}; - -/// A builder class used to create CFLGraph instance from a given function -/// The CFL-AA that uses this builder must provide its own type as a template -/// argument. This is necessary for interprocedural processing: CFLGraphBuilder -/// needs a way of obtaining the summary of other functions when callinsts are -/// encountered. -/// As a result, we expect the said CFL-AA to expose a getAliasSummary() public -/// member function that takes a Function& and returns the corresponding summary -/// as a const AliasSummary*. -template class CFLGraphBuilder { - // Input of the builder - CFLAA &Analysis; - const TargetLibraryInfo &TLI; - - // Output of the builder - CFLGraph Graph; - SmallVector ReturnedValues; - - // Helper class - /// Gets the edges our graph should have, based on an Instruction* - class GetEdgesVisitor : public InstVisitor { - CFLAA &AA; - const DataLayout &DL; - const TargetLibraryInfo &TLI; - - CFLGraph &Graph; - SmallVectorImpl &ReturnValues; - - static bool hasUsefulEdges(ConstantExpr *CE) { - // ConstantExpr doesn't have terminators, invokes, or fences, so only - // needs to check for compares. - return CE->getOpcode() != Instruction::ICmp && - CE->getOpcode() != Instruction::FCmp; - } - - // Returns possible functions called by CS into the given SmallVectorImpl. - // Returns true if targets found, false otherwise. - static bool getPossibleTargets(CallBase &Call, - SmallVectorImpl &Output) { - if (auto *Fn = Call.getCalledFunction()) { - Output.push_back(Fn); - return true; - } - - // TODO: If the call is indirect, we might be able to enumerate all - // potential targets of the call and return them, rather than just - // failing. - return false; - } - - void addNode(Value *Val, AliasAttrs Attr = AliasAttrs()) { - assert(Val != nullptr && Val->getType()->isPointerTy()); - if (auto GVal = dyn_cast(Val)) { - if (Graph.addNode(InstantiatedValue{GVal, 0}, - getGlobalOrArgAttrFromValue(*GVal))) - Graph.addNode(InstantiatedValue{GVal, 1}, getAttrUnknown()); - } else if (auto CExpr = dyn_cast(Val)) { - if (hasUsefulEdges(CExpr)) { - if (Graph.addNode(InstantiatedValue{CExpr, 0})) - visitConstantExpr(CExpr); - } - } else - Graph.addNode(InstantiatedValue{Val, 0}, Attr); - } - - void addAssignEdge(Value *From, Value *To, int64_t Offset = 0) { - assert(From != nullptr && To != nullptr); - if (!From->getType()->isPointerTy() || !To->getType()->isPointerTy()) - return; - addNode(From); - if (To != From) { - addNode(To); - Graph.addEdge(InstantiatedValue{From, 0}, InstantiatedValue{To, 0}, - Offset); - } - } - - void addDerefEdge(Value *From, Value *To, bool IsRead) { - assert(From != nullptr && To != nullptr); - // FIXME: This is subtly broken, due to how we model some instructions - // (e.g. extractvalue, extractelement) as loads. Since those take - // non-pointer operands, we'll entirely skip adding edges for those. - // - // addAssignEdge seems to have a similar issue with insertvalue, etc. - if (!From->getType()->isPointerTy() || !To->getType()->isPointerTy()) - return; - addNode(From); - addNode(To); - if (IsRead) { - Graph.addNode(InstantiatedValue{From, 1}); - Graph.addEdge(InstantiatedValue{From, 1}, InstantiatedValue{To, 0}); - } else { - Graph.addNode(InstantiatedValue{To, 1}); - Graph.addEdge(InstantiatedValue{From, 0}, InstantiatedValue{To, 1}); - } - } - - void addLoadEdge(Value *From, Value *To) { addDerefEdge(From, To, true); } - void addStoreEdge(Value *From, Value *To) { addDerefEdge(From, To, false); } - - public: - GetEdgesVisitor(CFLGraphBuilder &Builder, const DataLayout &DL) - : AA(Builder.Analysis), DL(DL), TLI(Builder.TLI), Graph(Builder.Graph), - ReturnValues(Builder.ReturnedValues) {} - - void visitInstruction(Instruction &) { - llvm_unreachable("Unsupported instruction encountered"); - } - - void visitReturnInst(ReturnInst &Inst) { - if (auto RetVal = Inst.getReturnValue()) { - if (RetVal->getType()->isPointerTy()) { - addNode(RetVal); - ReturnValues.push_back(RetVal); - } - } - } - - void visitPtrToIntInst(PtrToIntInst &Inst) { - auto *Ptr = Inst.getOperand(0); - addNode(Ptr, getAttrEscaped()); - } - - void visitIntToPtrInst(IntToPtrInst &Inst) { - auto *Ptr = &Inst; - addNode(Ptr, getAttrUnknown()); - } - - void visitCastInst(CastInst &Inst) { - auto *Src = Inst.getOperand(0); - addAssignEdge(Src, &Inst); - } - - void visitFreezeInst(FreezeInst &Inst) { - // Accessing freeze(ptr) is equivalent to accessing ptr. - // The former raises UB iff latter raises UB. - auto *Src = Inst.getOperand(0); - addAssignEdge(Src, &Inst); - } - - void visitBinaryOperator(BinaryOperator &Inst) { - auto *Op1 = Inst.getOperand(0); - auto *Op2 = Inst.getOperand(1); - addAssignEdge(Op1, &Inst); - addAssignEdge(Op2, &Inst); - } - - void visitUnaryOperator(UnaryOperator &Inst) { - auto *Src = Inst.getOperand(0); - addAssignEdge(Src, &Inst); - } - - void visitAtomicCmpXchgInst(AtomicCmpXchgInst &Inst) { - auto *Ptr = Inst.getPointerOperand(); - auto *Val = Inst.getNewValOperand(); - addStoreEdge(Val, Ptr); - } - - void visitAtomicRMWInst(AtomicRMWInst &Inst) { - auto *Ptr = Inst.getPointerOperand(); - auto *Val = Inst.getValOperand(); - addStoreEdge(Val, Ptr); - } - - void visitPHINode(PHINode &Inst) { - for (Value *Val : Inst.incoming_values()) - addAssignEdge(Val, &Inst); - } - - void visitGEP(GEPOperator &GEPOp) { - uint64_t Offset = UnknownOffset; - APInt APOffset(DL.getPointerSizeInBits(GEPOp.getPointerAddressSpace()), - 0); - if (GEPOp.accumulateConstantOffset(DL, APOffset)) - Offset = APOffset.getSExtValue(); - - auto *Op = GEPOp.getPointerOperand(); - addAssignEdge(Op, &GEPOp, Offset); - } - - void visitGetElementPtrInst(GetElementPtrInst &Inst) { - auto *GEPOp = cast(&Inst); - visitGEP(*GEPOp); - } - - void visitSelectInst(SelectInst &Inst) { - // Condition is not processed here (The actual statement producing - // the condition result is processed elsewhere). For select, the - // condition is evaluated, but not loaded, stored, or assigned - // simply as a result of being the condition of a select. - - auto *TrueVal = Inst.getTrueValue(); - auto *FalseVal = Inst.getFalseValue(); - addAssignEdge(TrueVal, &Inst); - addAssignEdge(FalseVal, &Inst); - } - - void visitAllocaInst(AllocaInst &Inst) { addNode(&Inst); } - - void visitLoadInst(LoadInst &Inst) { - auto *Ptr = Inst.getPointerOperand(); - auto *Val = &Inst; - addLoadEdge(Ptr, Val); - } - - void visitStoreInst(StoreInst &Inst) { - auto *Ptr = Inst.getPointerOperand(); - auto *Val = Inst.getValueOperand(); - addStoreEdge(Val, Ptr); - } - - void visitVAArgInst(VAArgInst &Inst) { - // We can't fully model va_arg here. For *Ptr = Inst.getOperand(0), it - // does - // two things: - // 1. Loads a value from *((T*)*Ptr). - // 2. Increments (stores to) *Ptr by some target-specific amount. - // For now, we'll handle this like a landingpad instruction (by placing - // the - // result in its own group, and having that group alias externals). - if (Inst.getType()->isPointerTy()) - addNode(&Inst, getAttrUnknown()); - } - - static bool isFunctionExternal(Function *Fn) { - return !Fn->hasExactDefinition(); - } - - bool tryInterproceduralAnalysis(CallBase &Call, - const SmallVectorImpl &Fns) { - assert(Fns.size() > 0); - - if (Call.arg_size() > MaxSupportedArgsInSummary) - return false; - - // Exit early if we'll fail anyway - for (auto *Fn : Fns) { - if (isFunctionExternal(Fn) || Fn->isVarArg()) - return false; - // Fail if the caller does not provide enough arguments - assert(Fn->arg_size() <= Call.arg_size()); - if (!AA.getAliasSummary(*Fn)) - return false; - } - - for (auto *Fn : Fns) { - auto Summary = AA.getAliasSummary(*Fn); - assert(Summary != nullptr); - - auto &RetParamRelations = Summary->RetParamRelations; - for (auto &Relation : RetParamRelations) { - auto IRelation = instantiateExternalRelation(Relation, Call); - if (IRelation) { - Graph.addNode(IRelation->From); - Graph.addNode(IRelation->To); - Graph.addEdge(IRelation->From, IRelation->To); - } - } - - auto &RetParamAttributes = Summary->RetParamAttributes; - for (auto &Attribute : RetParamAttributes) { - auto IAttr = instantiateExternalAttribute(Attribute, Call); - if (IAttr) - Graph.addNode(IAttr->IValue, IAttr->Attr); - } - } - - return true; - } - - void visitCallBase(CallBase &Call) { - // Make sure all arguments and return value are added to the graph first - for (Value *V : Call.args()) - if (V->getType()->isPointerTy()) - addNode(V); - if (Call.getType()->isPointerTy()) - addNode(&Call); - - // Check if Inst is a call to a library function that - // allocates/deallocates on the heap. Those kinds of functions do not - // introduce any aliases. - // TODO: address other common library functions such as realloc(), - // strdup(), etc. - if (isMallocOrCallocLikeFn(&Call, &TLI) || - getFreedOperand(&Call, &TLI) != nullptr) - return; - - // TODO: Add support for noalias args/all the other fun function - // attributes that we can tack on. - SmallVector Targets; - if (getPossibleTargets(Call, Targets)) - if (tryInterproceduralAnalysis(Call, Targets)) - return; - - // Because the function is opaque, we need to note that anything - // could have happened to the arguments (unless the function is marked - // readonly or readnone), and that the result could alias just about - // anything, too (unless the result is marked noalias). - if (!Call.onlyReadsMemory()) - for (Value *V : Call.args()) { - if (V->getType()->isPointerTy()) { - // The argument itself escapes. - Graph.addAttr(InstantiatedValue{V, 0}, getAttrEscaped()); - // The fate of argument memory is unknown. Note that since - // AliasAttrs is transitive with respect to dereference, we only - // need to specify it for the first-level memory. - Graph.addNode(InstantiatedValue{V, 1}, getAttrUnknown()); - } - } - - if (Call.getType()->isPointerTy()) { - auto *Fn = Call.getCalledFunction(); - if (Fn == nullptr || !Fn->returnDoesNotAlias()) - // No need to call addNode() since we've added Inst at the - // beginning of this function and we know it is not a global. - Graph.addAttr(InstantiatedValue{&Call, 0}, getAttrUnknown()); - } - } - - /// Because vectors/aggregates are immutable and unaddressable, there's - /// nothing we can do to coax a value out of them, other than calling - /// Extract{Element,Value}. We can effectively treat them as pointers to - /// arbitrary memory locations we can store in and load from. - void visitExtractElementInst(ExtractElementInst &Inst) { - auto *Ptr = Inst.getVectorOperand(); - auto *Val = &Inst; - addLoadEdge(Ptr, Val); - } - - void visitInsertElementInst(InsertElementInst &Inst) { - auto *Vec = Inst.getOperand(0); - auto *Val = Inst.getOperand(1); - addAssignEdge(Vec, &Inst); - addStoreEdge(Val, &Inst); - } - - void visitLandingPadInst(LandingPadInst &Inst) { - // Exceptions come from "nowhere", from our analysis' perspective. - // So we place the instruction its own group, noting that said group may - // alias externals - if (Inst.getType()->isPointerTy()) - addNode(&Inst, getAttrUnknown()); - } - - void visitInsertValueInst(InsertValueInst &Inst) { - auto *Agg = Inst.getOperand(0); - auto *Val = Inst.getOperand(1); - addAssignEdge(Agg, &Inst); - addStoreEdge(Val, &Inst); - } - - void visitExtractValueInst(ExtractValueInst &Inst) { - auto *Ptr = Inst.getAggregateOperand(); - addLoadEdge(Ptr, &Inst); - } - - void visitShuffleVectorInst(ShuffleVectorInst &Inst) { - auto *From1 = Inst.getOperand(0); - auto *From2 = Inst.getOperand(1); - addAssignEdge(From1, &Inst); - addAssignEdge(From2, &Inst); - } - - void visitConstantExpr(ConstantExpr *CE) { - switch (CE->getOpcode()) { - case Instruction::GetElementPtr: { - auto GEPOp = cast(CE); - visitGEP(*GEPOp); - break; - } - - case Instruction::PtrToInt: { - addNode(CE->getOperand(0), getAttrEscaped()); - break; - } - - case Instruction::IntToPtr: { - addNode(CE, getAttrUnknown()); - break; - } - - case Instruction::BitCast: - case Instruction::AddrSpaceCast: - case Instruction::Trunc: - case Instruction::ZExt: - case Instruction::SExt: - case Instruction::FPExt: - case Instruction::FPTrunc: - case Instruction::UIToFP: - case Instruction::SIToFP: - case Instruction::FPToUI: - case Instruction::FPToSI: { - addAssignEdge(CE->getOperand(0), CE); - break; - } - - case Instruction::Select: { - addAssignEdge(CE->getOperand(1), CE); - addAssignEdge(CE->getOperand(2), CE); - break; - } - - case Instruction::InsertElement: - case Instruction::InsertValue: { - addAssignEdge(CE->getOperand(0), CE); - addStoreEdge(CE->getOperand(1), CE); - break; - } - - case Instruction::ExtractElement: - case Instruction::ExtractValue: { - addLoadEdge(CE->getOperand(0), CE); - break; - } - - case Instruction::Add: - case Instruction::FAdd: - case Instruction::Sub: - case Instruction::FSub: - case Instruction::Mul: - case Instruction::FMul: - case Instruction::UDiv: - case Instruction::SDiv: - case Instruction::FDiv: - case Instruction::URem: - case Instruction::SRem: - case Instruction::FRem: - case Instruction::And: - case Instruction::Or: - case Instruction::Xor: - case Instruction::Shl: - case Instruction::LShr: - case Instruction::AShr: - case Instruction::ICmp: - case Instruction::FCmp: - case Instruction::ShuffleVector: { - addAssignEdge(CE->getOperand(0), CE); - addAssignEdge(CE->getOperand(1), CE); - break; - } - - case Instruction::FNeg: { - addAssignEdge(CE->getOperand(0), CE); - break; - } - - default: - llvm_unreachable("Unknown instruction type encountered!"); - } - } - }; - - // Helper functions - - // Determines whether or not we an instruction is useless to us (e.g. - // FenceInst) - static bool hasUsefulEdges(Instruction *Inst) { - bool IsNonInvokeRetTerminator = Inst->isTerminator() && - !isa(Inst) && - !isa(Inst); - return !isa(Inst) && !isa(Inst) && - !IsNonInvokeRetTerminator; - } - - void addArgumentToGraph(Argument &Arg) { - if (Arg.getType()->isPointerTy()) { - Graph.addNode(InstantiatedValue{&Arg, 0}, - getGlobalOrArgAttrFromValue(Arg)); - // Pointees of a formal parameter is known to the caller - Graph.addNode(InstantiatedValue{&Arg, 1}, getAttrCaller()); - } - } - - // Given an Instruction, this will add it to the graph, along with any - // Instructions that are potentially only available from said Instruction - // For example, given the following line: - // %0 = load i16* getelementptr ([1 x i16]* @a, 0, 0), align 2 - // addInstructionToGraph would add both the `load` and `getelementptr` - // instructions to the graph appropriately. - void addInstructionToGraph(GetEdgesVisitor &Visitor, Instruction &Inst) { - if (!hasUsefulEdges(&Inst)) - return; - - Visitor.visit(Inst); - } - - // Builds the graph needed for constructing the StratifiedSets for the given - // function - void buildGraphFrom(Function &Fn) { - GetEdgesVisitor Visitor(*this, Fn.getParent()->getDataLayout()); - - for (auto &Bb : Fn.getBasicBlockList()) - for (auto &Inst : Bb) - addInstructionToGraph(Visitor, Inst); - - for (auto &Arg : Fn.args()) - addArgumentToGraph(Arg); - } - -public: - CFLGraphBuilder(CFLAA &Analysis, const TargetLibraryInfo &TLI, Function &Fn) - : Analysis(Analysis), TLI(TLI) { - buildGraphFrom(Fn); - } - - const CFLGraph &getCFLGraph() const { return Graph; } - const SmallVector &getReturnValues() const { - return ReturnedValues; - } -}; - -} // end namespace cflaa -} // end namespace llvm - -#endif // LLVM_LIB_ANALYSIS_CFLGRAPH_H diff --git a/llvm/lib/Analysis/CFLSteensAliasAnalysis.cpp b/llvm/lib/Analysis/CFLSteensAliasAnalysis.cpp deleted file mode 100644 --- a/llvm/lib/Analysis/CFLSteensAliasAnalysis.cpp +++ /dev/null @@ -1,364 +0,0 @@ -//===- CFLSteensAliasAnalysis.cpp - Unification-based Alias Analysis ------===// -// -// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. -// See https://llvm.org/LICENSE.txt for license information. -// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception -// -//===----------------------------------------------------------------------===// -// -// This file implements a CFL-base, summary-based alias analysis algorithm. It -// does not depend on types. The algorithm is a mixture of the one described in -// "Demand-driven alias analysis for C" by Xin Zheng and Radu Rugina, and "Fast -// algorithms for Dyck-CFL-reachability with applications to Alias Analysis" by -// Zhang Q, Lyu M R, Yuan H, and Su Z. -- to summarize the papers, we build a -// graph of the uses of a variable, where each node is a memory location, and -// each edge is an action that happened on that memory location. The "actions" -// can be one of Dereference, Reference, or Assign. The precision of this -// analysis is roughly the same as that of an one level context-sensitive -// Steensgaard's algorithm. -// -// Two variables are considered as aliasing iff you can reach one value's node -// from the other value's node and the language formed by concatenating all of -// the edge labels (actions) conforms to a context-free grammar. -// -// Because this algorithm requires a graph search on each query, we execute the -// algorithm outlined in "Fast algorithms..." (mentioned above) -// in order to transform the graph into sets of variables that may alias in -// ~nlogn time (n = number of variables), which makes queries take constant -// time. -//===----------------------------------------------------------------------===// - -// N.B. AliasAnalysis as a whole is phrased as a FunctionPass at the moment, and -// CFLSteensAA is interprocedural. This is *technically* A Bad Thing, because -// FunctionPasses are only allowed to inspect the Function that they're being -// run on. Realistically, this likely isn't a problem until we allow -// FunctionPasses to run concurrently. - -#include "llvm/Analysis/CFLSteensAliasAnalysis.h" -#include "AliasAnalysisSummary.h" -#include "CFLGraph.h" -#include "StratifiedSets.h" -#include "llvm/ADT/DenseMap.h" -#include "llvm/ADT/Optional.h" -#include "llvm/ADT/SmallVector.h" -#include "llvm/Analysis/TargetLibraryInfo.h" -#include "llvm/IR/Constants.h" -#include "llvm/IR/Function.h" -#include "llvm/IR/Type.h" -#include "llvm/IR/Value.h" -#include "llvm/InitializePasses.h" -#include "llvm/Pass.h" -#include "llvm/Support/Debug.h" -#include "llvm/Support/raw_ostream.h" -#include -#include -#include -#include -#include - -using namespace llvm; -using namespace llvm::cflaa; - -#define DEBUG_TYPE "cfl-steens-aa" - -CFLSteensAAResult::CFLSteensAAResult( - std::function GetTLI) - : GetTLI(std::move(GetTLI)) {} -CFLSteensAAResult::CFLSteensAAResult(CFLSteensAAResult &&Arg) - : AAResultBase(std::move(Arg)), GetTLI(std::move(Arg.GetTLI)) {} -CFLSteensAAResult::~CFLSteensAAResult() = default; - -/// Information we have about a function and would like to keep around. -class CFLSteensAAResult::FunctionInfo { - StratifiedSets Sets; - AliasSummary Summary; - -public: - FunctionInfo(Function &Fn, const SmallVectorImpl &RetVals, - StratifiedSets S); - - const StratifiedSets &getStratifiedSets() const { - return Sets; - } - - const AliasSummary &getAliasSummary() const { return Summary; } -}; - -const StratifiedIndex StratifiedLink::SetSentinel = - std::numeric_limits::max(); - -//===----------------------------------------------------------------------===// -// Function declarations that require types defined in the namespace above -//===----------------------------------------------------------------------===// - -/// Determines whether it would be pointless to add the given Value to our sets. -static bool canSkipAddingToSets(Value *Val) { - // Constants can share instances, which may falsely unify multiple - // sets, e.g. in - // store i32* null, i32** %ptr1 - // store i32* null, i32** %ptr2 - // clearly ptr1 and ptr2 should not be unified into the same set, so - // we should filter out the (potentially shared) instance to - // i32* null. - if (isa(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) - Summary.RetParamRelations.push_back( - ExternalRelation{CurrValue, Itr->second, UnknownOffset}); - break; - } - - auto &Link = Sets.getLink(SetIndex); - InterfaceMap.insert(std::make_pair(SetIndex, CurrValue)); - auto ExternalAttrs = getExternallyVisibleAttrs(Link.Attrs); - if (ExternalAttrs.any()) - Summary.RetParamAttributes.push_back( - ExternalAttribute{CurrValue, ExternalAttrs}); - - if (!Link.hasBelow()) - break; - - ++Level; - SetIndex = Link.Below; - } - }; - - // Populate RetParamRelations for return values - for (auto *RetVal : RetVals) { - assert(RetVal != nullptr); - assert(RetVal->getType()->isPointerTy()); - auto RetInfo = Sets.find(InstantiatedValue{RetVal, 0}); - if (RetInfo) - AddToRetParamRelations(0, RetInfo->Index); - } - - // Populate RetParamRelations for parameters - unsigned I = 0; - for (auto &Param : Fn.args()) { - if (Param.getType()->isPointerTy()) { - auto ParamInfo = Sets.find(InstantiatedValue{&Param, 0}); - if (ParamInfo) - AddToRetParamRelations(I + 1, ParamInfo->Index); - } - ++I; - } -} - -// Builds the graph + StratifiedSets for a function. -CFLSteensAAResult::FunctionInfo CFLSteensAAResult::buildSetsFrom(Function *Fn) { - CFLGraphBuilder GraphBuilder(*this, GetTLI(*Fn), *Fn); - StratifiedSetsBuilder SetBuilder; - - // Add all CFLGraph nodes and all Dereference edges to StratifiedSets - auto &Graph = GraphBuilder.getCFLGraph(); - for (const auto &Mapping : Graph.value_mappings()) { - auto Val = Mapping.first; - if (canSkipAddingToSets(Val)) - continue; - auto &ValueInfo = Mapping.second; - - assert(ValueInfo.getNumLevels() > 0); - SetBuilder.add(InstantiatedValue{Val, 0}); - SetBuilder.noteAttributes(InstantiatedValue{Val, 0}, - ValueInfo.getNodeInfoAtLevel(0).Attr); - for (unsigned I = 0, E = ValueInfo.getNumLevels() - 1; I < E; ++I) { - SetBuilder.add(InstantiatedValue{Val, I + 1}); - SetBuilder.noteAttributes(InstantiatedValue{Val, I + 1}, - ValueInfo.getNodeInfoAtLevel(I + 1).Attr); - SetBuilder.addBelow(InstantiatedValue{Val, I}, - InstantiatedValue{Val, I + 1}); - } - } - - // Add all assign edges to StratifiedSets - for (const auto &Mapping : Graph.value_mappings()) { - auto Val = Mapping.first; - if (canSkipAddingToSets(Val)) - continue; - auto &ValueInfo = Mapping.second; - - for (unsigned I = 0, E = ValueInfo.getNumLevels(); I < E; ++I) { - auto Src = InstantiatedValue{Val, I}; - for (const auto &Edge : ValueInfo.getNodeInfoAtLevel(I).Edges) - SetBuilder.addWith(Src, Edge.Other); - } - } - - return FunctionInfo(*Fn, GraphBuilder.getReturnValues(), SetBuilder.build()); -} - -void CFLSteensAAResult::scan(Function *Fn) { - auto InsertPair = Cache.insert(std::make_pair(Fn, Optional())); - (void)InsertPair; - assert(InsertPair.second && - "Trying to scan a function that has already been cached"); - - // Note that we can't do Cache[Fn] = buildSetsFrom(Fn) here: the function call - // may get evaluated after operator[], potentially triggering a DenseMap - // resize and invalidating the reference returned by operator[] - auto FunInfo = buildSetsFrom(Fn); - Cache[Fn] = std::move(FunInfo); - - Handles.emplace_front(Fn, this); -} - -void CFLSteensAAResult::evict(Function *Fn) { Cache.erase(Fn); } - -/// Ensures that the given function is available in the cache, and returns the -/// entry. -const Optional & -CFLSteensAAResult::ensureCached(Function *Fn) { - auto Iter = Cache.find(Fn); - if (Iter == Cache.end()) { - scan(Fn); - Iter = Cache.find(Fn); - assert(Iter != Cache.end()); - assert(Iter->second); - } - return Iter->second; -} - -const AliasSummary *CFLSteensAAResult::getAliasSummary(Function &Fn) { - auto &FunInfo = ensureCached(&Fn); - if (FunInfo) - return &FunInfo->getAliasSummary(); - else - return nullptr; -} - -AliasResult CFLSteensAAResult::query(const MemoryLocation &LocA, - const MemoryLocation &LocB) { - auto *ValA = const_cast(LocA.Ptr); - auto *ValB = const_cast(LocB.Ptr); - - if (!ValA->getType()->isPointerTy() || !ValB->getType()->isPointerTy()) - return AliasResult::NoAlias; - - Function *Fn = nullptr; - Function *MaybeFnA = const_cast(parentFunctionOfValue(ValA)); - Function *MaybeFnB = const_cast(parentFunctionOfValue(ValB)); - if (!MaybeFnA && !MaybeFnB) { - // The only times this is known to happen are when globals + InlineAsm are - // involved - LLVM_DEBUG( - dbgs() - << "CFLSteensAA: could not extract parent function information.\n"); - return AliasResult::MayAlias; - } - - if (MaybeFnA) { - Fn = MaybeFnA; - assert((!MaybeFnB || MaybeFnB == MaybeFnA) && - "Interprocedural queries not supported"); - } else { - Fn = MaybeFnB; - } - - assert(Fn != nullptr); - auto &MaybeInfo = ensureCached(Fn); - assert(MaybeInfo); - - auto &Sets = MaybeInfo->getStratifiedSets(); - auto MaybeA = Sets.find(InstantiatedValue{ValA, 0}); - if (!MaybeA) - return AliasResult::MayAlias; - - auto MaybeB = Sets.find(InstantiatedValue{ValB, 0}); - if (!MaybeB) - return AliasResult::MayAlias; - - auto SetA = *MaybeA; - auto SetB = *MaybeB; - auto AttrsA = Sets.getLink(SetA.Index).Attrs; - auto AttrsB = Sets.getLink(SetB.Index).Attrs; - - // If both values are local (meaning the corresponding set has attribute - // AttrNone or AttrEscaped), then we know that CFLSteensAA fully models them: - // they may-alias each other if and only if they are in the same set. - // If at least one value is non-local (meaning it either is global/argument or - // it comes from unknown sources like integer cast), the situation becomes a - // bit more interesting. We follow three general rules described below: - // - Non-local values may alias each other - // - AttrNone values do not alias any non-local values - // - AttrEscaped do not alias globals/arguments, but they may alias - // AttrUnknown values - if (SetA.Index == SetB.Index) - return AliasResult::MayAlias; - if (AttrsA.none() || AttrsB.none()) - return AliasResult::NoAlias; - if (hasUnknownOrCallerAttr(AttrsA) || hasUnknownOrCallerAttr(AttrsB)) - return AliasResult::MayAlias; - if (isGlobalOrArgAttr(AttrsA) && isGlobalOrArgAttr(AttrsB)) - return AliasResult::MayAlias; - return AliasResult::NoAlias; -} - -AnalysisKey CFLSteensAA::Key; - -CFLSteensAAResult CFLSteensAA::run(Function &F, FunctionAnalysisManager &AM) { - auto GetTLI = [&AM](Function &F) -> const TargetLibraryInfo & { - return AM.getResult(F); - }; - return CFLSteensAAResult(GetTLI); -} - -char CFLSteensAAWrapperPass::ID = 0; -INITIALIZE_PASS(CFLSteensAAWrapperPass, "cfl-steens-aa", - "Unification-Based CFL Alias Analysis", false, true) - -ImmutablePass *llvm::createCFLSteensAAWrapperPass() { - return new CFLSteensAAWrapperPass(); -} - -CFLSteensAAWrapperPass::CFLSteensAAWrapperPass() : ImmutablePass(ID) { - initializeCFLSteensAAWrapperPassPass(*PassRegistry::getPassRegistry()); -} - -void CFLSteensAAWrapperPass::initializePass() { - auto GetTLI = [this](Function &F) -> const TargetLibraryInfo & { - return this->getAnalysis().getTLI(F); - }; - Result.reset(new CFLSteensAAResult(GetTLI)); -} - -void CFLSteensAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { - AU.setPreservesAll(); - AU.addRequired(); -} diff --git a/llvm/lib/Analysis/CMakeLists.txt b/llvm/lib/Analysis/CMakeLists.txt --- a/llvm/lib/Analysis/CMakeLists.txt +++ b/llvm/lib/Analysis/CMakeLists.txt @@ -47,8 +47,6 @@ CFG.cpp CFGPrinter.cpp CFGSCCPrinter.cpp - CFLAndersAliasAnalysis.cpp - CFLSteensAliasAnalysis.cpp CGSCCPassManager.cpp CallGraph.cpp CallGraphSCCPass.cpp diff --git a/llvm/lib/CodeGen/TargetPassConfig.cpp b/llvm/lib/CodeGen/TargetPassConfig.cpp --- a/llvm/lib/CodeGen/TargetPassConfig.cpp +++ b/llvm/lib/CodeGen/TargetPassConfig.cpp @@ -16,8 +16,6 @@ #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/StringRef.h" #include "llvm/Analysis/BasicAliasAnalysis.h" -#include "llvm/Analysis/CFLAndersAliasAnalysis.h" -#include "llvm/Analysis/CFLSteensAliasAnalysis.h" #include "llvm/Analysis/CallGraphSCCPass.h" #include "llvm/Analysis/ScopedNoAliasAA.h" #include "llvm/Analysis/TargetTransformInfo.h" @@ -209,18 +207,6 @@ static cl::opt EarlyLiveIntervals("early-live-intervals", cl::Hidden, cl::desc("Run live interval analysis earlier in the pipeline")); -// Experimental option to use CFL-AA in codegen -static cl::opt UseCFLAA( - "use-cfl-aa-in-codegen", cl::init(CFLAAType::None), cl::Hidden, - cl::desc("Enable the new, experimental CFL alias analysis in CodeGen"), - cl::values(clEnumValN(CFLAAType::None, "none", "Disable CFL-AA"), - clEnumValN(CFLAAType::Steensgaard, "steens", - "Enable unification-based CFL-AA"), - clEnumValN(CFLAAType::Andersen, "anders", - "Enable inclusion-based CFL-AA"), - clEnumValN(CFLAAType::Both, "both", - "Enable both variants of CFL-AA"))); - /// Option names for limiting the codegen pipeline. /// Those are used in error reporting and we didn't want /// to duplicate their names all over the place. @@ -493,7 +479,6 @@ SET_BOOLEAN_OPTION(EnableImplicitNullChecks) SET_BOOLEAN_OPTION(EnableMachineOutliner) SET_BOOLEAN_OPTION(MISchedPostRA) - SET_BOOLEAN_OPTION(UseCFLAA) SET_BOOLEAN_OPTION(DisableMergeICmps) SET_BOOLEAN_OPTION(DisableLSR) SET_BOOLEAN_OPTION(DisableConstantHoisting) @@ -858,21 +843,6 @@ addPass(createVerifierPass()); if (getOptLevel() != CodeGenOpt::None) { - switch (UseCFLAA) { - case CFLAAType::Steensgaard: - addPass(createCFLSteensAAWrapperPass()); - break; - case CFLAAType::Andersen: - addPass(createCFLAndersAAWrapperPass()); - break; - case CFLAAType::Both: - addPass(createCFLAndersAAWrapperPass()); - addPass(createCFLSteensAAWrapperPass()); - break; - default: - break; - } - // Basic AliasAnalysis support. // Add TypeBasedAliasAnalysis before BasicAliasAnalysis so that // BasicAliasAnalysis wins if they disagree. This is intended to help diff --git a/llvm/lib/Passes/PassBuilder.cpp b/llvm/lib/Passes/PassBuilder.cpp --- a/llvm/lib/Passes/PassBuilder.cpp +++ b/llvm/lib/Passes/PassBuilder.cpp @@ -24,8 +24,6 @@ #include "llvm/Analysis/BranchProbabilityInfo.h" #include "llvm/Analysis/CFGPrinter.h" #include "llvm/Analysis/CFGSCCPrinter.h" -#include "llvm/Analysis/CFLAndersAliasAnalysis.h" -#include "llvm/Analysis/CFLSteensAliasAnalysis.h" #include "llvm/Analysis/CGSCCPassManager.h" #include "llvm/Analysis/CallGraph.h" #include "llvm/Analysis/CallPrinter.h" diff --git a/llvm/lib/Passes/PassRegistry.def b/llvm/lib/Passes/PassRegistry.def --- a/llvm/lib/Passes/PassRegistry.def +++ b/llvm/lib/Passes/PassRegistry.def @@ -241,8 +241,6 @@ FUNCTION_ANALYSIS(NAME, CREATE_PASS) #endif FUNCTION_ALIAS_ANALYSIS("basic-aa", BasicAA()) -FUNCTION_ALIAS_ANALYSIS("cfl-anders-aa", CFLAndersAA()) -FUNCTION_ALIAS_ANALYSIS("cfl-steens-aa", CFLSteensAA()) FUNCTION_ALIAS_ANALYSIS("objc-arc-aa", objcarc::ObjCARCAA()) FUNCTION_ALIAS_ANALYSIS("scev-aa", SCEVAA()) FUNCTION_ALIAS_ANALYSIS("scoped-noalias-aa", ScopedNoAliasAA()) diff --git a/llvm/lib/Transforms/IPO/PassManagerBuilder.cpp b/llvm/lib/Transforms/IPO/PassManagerBuilder.cpp --- a/llvm/lib/Transforms/IPO/PassManagerBuilder.cpp +++ b/llvm/lib/Transforms/IPO/PassManagerBuilder.cpp @@ -15,8 +15,6 @@ #include "llvm-c/Transforms/PassManagerBuilder.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SmallVector.h" -#include "llvm/Analysis/CFLAndersAliasAnalysis.h" -#include "llvm/Analysis/CFLSteensAliasAnalysis.h" #include "llvm/Analysis/GlobalsModRef.h" #include "llvm/Analysis/ScopedNoAliasAA.h" #include "llvm/Analysis/TargetLibraryInfo.h" diff --git a/llvm/test/Analysis/CFLAliasAnalysis/Andersen/assign.ll b/llvm/test/Analysis/CFLAliasAnalysis/Andersen/assign.ll deleted file mode 100644 --- a/llvm/test/Analysis/CFLAliasAnalysis/Andersen/assign.ll +++ /dev/null @@ -1,28 +0,0 @@ -; This testcase ensures that CFL AA handles assignment in an inclusion-based -; manner - -; RUN: opt < %s -aa-pipeline=cfl-anders-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s - -; CHECK-LABEL: Function: test_assign -; CHECK: NoAlias: i64* %a, i64* %b -; CHECK: NoAlias: i64* %b, i32* %c -; CHECK: NoAlias: i64* %a, i32* %d -; CHECK: NoAlias: i32* %c, i32* %d -; CHECK: MayAlias: i64* %a, i32* %e -; CHECK: MayAlias: i64* %b, i32* %e -; CHECK: MayAlias: i32* %c, i32* %e -; CHECK: MayAlias: i32* %d, i32* %e -define void @test_assign(i1 %cond) { - %a = alloca i64, align 8 - %b = alloca i64, align 8 - - %c = bitcast i64* %a to i32* - %d = bitcast i64* %b to i32* - %e = select i1 %cond, i32* %c, i32* %d - load i64, i64* %a - load i64, i64* %b - load i32, i32* %c - load i32, i32* %d - load i32, i32* %e - ret void -} diff --git a/llvm/test/Analysis/CFLAliasAnalysis/Andersen/assign2.ll b/llvm/test/Analysis/CFLAliasAnalysis/Andersen/assign2.ll deleted file mode 100644 --- a/llvm/test/Analysis/CFLAliasAnalysis/Andersen/assign2.ll +++ /dev/null @@ -1,27 +0,0 @@ -; This testcase ensures that CFL AA handles assignment in an inclusion-based -; manner - -; RUN: opt < %s -aa-pipeline=cfl-anders-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s - -; CHECK-LABEL: Function: test_assign2 -; CHECK: NoAlias: i64* %a, i32* %b -; CHECK: NoAlias: i32* %b, i32* %c -; CHECK: NoAlias: i32* %b, i32* %d -; CHECK: MayAlias: i64* %a, i32* %e -; CHECK: MayAlias: i32* %b, i32* %e -; CHECK: MayAlias: i32* %c, i32* %e -; CHECK: MayAlias: i32* %d, i32* %e -define void @test_assign2(i1 %cond) { - %a = alloca i64, align 8 - %b = alloca i32, align 4 - - %c = bitcast i64* %a to i32* - %d = bitcast i64* %a to i32* - %e = select i1 %cond, i32* %c, i32* %b - load i64, i64* %a - load i32, i32* %b - load i32, i32* %c - load i32, i32* %d - load i32, i32* %e - ret void -} diff --git a/llvm/test/Analysis/CFLAliasAnalysis/Andersen/attrs-below.ll b/llvm/test/Analysis/CFLAliasAnalysis/Andersen/attrs-below.ll deleted file mode 100644 --- a/llvm/test/Analysis/CFLAliasAnalysis/Andersen/attrs-below.ll +++ /dev/null @@ -1,72 +0,0 @@ -; This testcase ensures that AliasAttrs are propagated not only on the same -; level but also downward. - -; RUN: opt < %s -aa-pipeline=cfl-anders-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s - -; CHECK-LABEL: Function: test_attr_below -; CHECK-DAG: MayAlias: i64*** %p, i64* %q -; CHECK-DAG: NoAlias: i64* %esc, i64*** %p -; CHECK-DAG: NoAlias: i64* %esc, i64* %q - -; CHECK-DAG: MayAlias: i64*** %p, i64* %unknown -; CHECK-DAG: MayAlias: i64* %q, i64* %unknown -; CHECK-DAG: MayAlias: i64* %esc, i64* %unknown -; CHECK-DAG: MayAlias: i64** %pdrf, i64* %q -; CHECK-DAG: MayAlias: i64* %esc, i64** %pdrf -; CHECK-DAG: MayAlias: i64** %pdrf, i64* %unknown -; CHECK-DAG: MayAlias: i64* %pdrf2, i64* %q -; CHECK-DAG: MayAlias: i64* %esc, i64* %pdrf2 -; CHECK-DAG: MayAlias: i64* %pdrf2, i64* %unknown -define void @test_attr_below(i64*** %p, i64* %q) { - %esc = alloca i64, align 8 - %escint = ptrtoint i64* %esc to i64 - %unknown = inttoptr i64 %escint to i64* - - %pdrf = load i64**, i64*** %p - %pdrf2 = load i64*, i64** %pdrf - - load i64, i64* %q - load i64, i64* %esc - load i64, i64* %unknown - load i64, i64* %pdrf2 - - ret void -} - -; CHECK-LABEL: Function: test_attr_assign_below -; CHECK-DAG: MayAlias: i64*** %p, i64** %sel -; CHECK-DAG: MayAlias: i64* %q, i64** %sel -; CHECK-DAG: MayAlias: i64** %a, i64** %sel -; CHECK-DAG: MayAlias: i64** %pdrf, i64** %sel - -; CHECK-DAG: MayAlias: i64** %c, i64*** %p -; CHECK-DAG: MayAlias: i64** %c, i64* %q -; CHECK-DAG: MayAlias: i64** %a, i64** %c -; CHECK-DAG: MayAlias: i64** %c, i64** %pdrf -; CHECK-DAG: MayAlias: i64** %c, i64** %sel - -; CHECK-DAG: MayAlias: i64* %d, i64*** %p -; CHECK-DAG: MayAlias: i64* %d, i64* %q -; CHECK-DAG: MayAlias: i64* %d, i64** %pdrf -; CHECK-DAG: MayAlias: i64* %d, i64** %sel -define void @test_attr_assign_below(i64*** %p, i64* %q, i1 %cond) { - %a = alloca i64*, align 8 - %pdrf = load i64**, i64*** %p - %sel = select i1 %cond, i64** %a, i64** %pdrf - - %b = alloca i64**, align 8 - store i64** %sel, i64*** %b - - %c = load i64**, i64*** %b - %d = load i64*, i64** %c - - load i64, i64* %q - load i64*, i64** %a - load i64*, i64** %pdrf - load i64*, i64** %sel - load i64*, i64** %c - load i64, i64* %d - - ret void -} - diff --git a/llvm/test/Analysis/CFLAliasAnalysis/Andersen/attrs.ll b/llvm/test/Analysis/CFLAliasAnalysis/Andersen/attrs.ll deleted file mode 100644 --- a/llvm/test/Analysis/CFLAliasAnalysis/Andersen/attrs.ll +++ /dev/null @@ -1,112 +0,0 @@ -; This testcase ensures that CFL AA handles escaped values no more conservative than it should - -; RUN: opt < %s -aa-pipeline=cfl-anders-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s - -; CHECK-LABEL: Function: test_local -; CHECK: NoAlias: i32* %a, i32* %b -; CHECK: MayAlias: i32* %a, i32* %aAlias -; CHECK: NoAlias: i32* %aAlias, i32* %b -define void @test_local() { - %a = alloca i32, align 4 - %b = alloca i32, align 4 - %aint = ptrtoint i32* %a to i64 - %aAlias = inttoptr i64 %aint to i32* - load i32, i32* %a - load i32, i32* %b - load i32, i32* %aAlias - ret void -} - -; CHECK-LABEL: Function: test_global_param -; CHECK-DAG: NoAlias: i32* %a, i32** %x -; CHECK-DAG: MayAlias: i32* %a, i32* %xload -; CHECK-DAG: MayAlias: i32* %a, i32* %gload -; CHECK-DAG: MayAlias: i32* %gload, i32* %xload -; CHECK-DAG: MayAlias: i32** %x, i32** @ext_global -; CHECK-DAG: NoAlias: i32* %a, i32** @ext_global -@ext_global = external global i32* -define void @test_global_param(i32** %x) { - %a = alloca i32, align 4 - %aint = ptrtoint i32* %a to i64 - %xload = load i32*, i32** %x - %gload = load i32*, i32** @ext_global - load i32, i32* %a - load i32, i32* %xload - load i32, i32* %gload - ret void -} - -declare void @external_func(i32**) -; CHECK-LABEL: Function: test_external_call -; CHECK-DAG: NoAlias: i32* %b, i32* %x -; CHECK-DAG: NoAlias: i32** %a, i32* %b -; CHECK-DAG: MayAlias: i32* %c, i32* %x -; CHECK-DAG: MayAlias: i32** %a, i32* %c -; CHECK-DAG: NoAlias: i32* %b, i32* %c -define void @test_external_call(i32* %x) { - %a = alloca i32*, align 8 - %b = alloca i32, align 4 - call void @external_func(i32** %a) - %c = load i32*, i32** %a - load i32, i32* %x - load i32, i32* %b - load i32, i32* %c - ret void -} - -declare void @external_func_readonly(i32**) readonly -; CHECK-LABEL: Function: test_external_call_func_readonly -; CHECK-DAG: MayAlias: i32* %c, i32* %x -; CHECK-DAG: NoAlias: i32** %a, i32* %c -define void @test_external_call_func_readonly(i32* %x) { - %a = alloca i32*, align 8 - %b = alloca i32, align 4 - store i32* %x, i32** %a, align 4 - call void @external_func_readonly(i32** %a) - %c = load i32*, i32** %a - load i32, i32* %x - load i32, i32* %c - ret void -} - -; CHECK-LABEL: Function: test_external_call_callsite_readonly -; CHECK-DAG: MayAlias: i32* %c, i32* %x -; CHECK-DAG: NoAlias: i32** %a, i32* %c -define void @test_external_call_callsite_readonly(i32* %x) { - %a = alloca i32*, align 8 - %b = alloca i32, align 4 - store i32* %x, i32** %a, align 4 - call void @external_func(i32** %a) readonly - %c = load i32*, i32** %a - load i32, i32* %x - load i32, i32* %c - ret void -} - -declare i32* @external_func_normal_return(i32*) -; CHECK-LABEL: Function: test_external_call_normal_return -; CHECK: MayAlias: i32* %c, i32* %x -; CHECK: MayAlias: i32* %a, i32* %c -define void @test_external_call_normal_return(i32* %x) { - %a = alloca i32, align 8 - %b = alloca i32, align 4 - %c = call i32* @external_func_normal_return(i32* %a) - load i32, i32* %x - load i32, i32* %a - load i32, i32* %c - ret void -} - -declare noalias i32* @external_func_noalias_return(i32*) -; CHECK-LABEL: Function: test_external_call_noalias_return -; CHECK: NoAlias: i32* %c, i32* %x -; CHECK: NoAlias: i32* %a, i32* %c -define void @test_external_call_noalias_return(i32* %x) { - %a = alloca i32, align 8 - %b = alloca i32, align 4 - %c = call i32* @external_func_noalias_return(i32* %a) - load i32, i32* %x - load i32, i32* %a - load i32, i32* %c - ret void -} diff --git a/llvm/test/Analysis/CFLAliasAnalysis/Andersen/basic-interproc.ll b/llvm/test/Analysis/CFLAliasAnalysis/Andersen/basic-interproc.ll deleted file mode 100644 --- a/llvm/test/Analysis/CFLAliasAnalysis/Andersen/basic-interproc.ll +++ /dev/null @@ -1,23 +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 -aa-pipeline=cfl-anders-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s - -; CHECK-LABEL: Function: noop_callee -; CHECK: MayAlias: i32* %arg1, i32* %arg2 -define void @noop_callee(i32* %arg1, i32* %arg2) { - store i32 0, i32* %arg1 - store i32 0, i32* %arg2 - ret void -} -; CHECK-LABEL: Function: test_noop -; CHECK: NoAlias: i32* %a, i32* %b -define void @test_noop() { - %a = alloca i32, align 4 - %b = alloca i32, align 4 - load i32, i32* %a - load i32, i32* %b - call void @noop_callee(i32* %a, i32* %b) - - ret void -} diff --git a/llvm/test/Analysis/CFLAliasAnalysis/Andersen/cycle.ll b/llvm/test/Analysis/CFLAliasAnalysis/Andersen/cycle.ll deleted file mode 100644 --- a/llvm/test/Analysis/CFLAliasAnalysis/Andersen/cycle.ll +++ /dev/null @@ -1,36 +0,0 @@ -; This testcase ensures that CFL AA handles assignment cycles correctly - -; RUN: opt < %s -aa-pipeline=cfl-anders-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s - -; CHECK-LABEL: Function: test_cycle -; CHECK: NoAlias: i64* %a, i64** %b -; CHECK: NoAlias: i64* %a, i64*** %c -; CHECK: NoAlias: i64** %b, i64*** %c -; CHECK: NoAlias: i64* %a, i64**** %d -; CHECK: NoAlias: i64** %b, i64**** %d -; CHECK: NoAlias: i64*** %c, i64**** %d -; CHECK: NoAlias: i64* %a, i64* %e -; CHECK: NoAlias: i64** %b, i64* %e -; CHECK: NoAlias: i64*** %c, i64* %e -; CHECK: MayAlias: i64* %a, i64* %f -; CHECK: NoAlias: i64** %b, i64* %f -; CHECK: NoAlias: i64*** %c, i64* %f -; CHECK: MayAlias: i64**** %d, i64* %f -; CHECK: MayAlias: i64* %e, i64* %f -define void @test_cycle() { - %a = alloca i64, align 8 - %b = alloca i64*, align 8 - %c = alloca i64**, align 8 - %d = alloca i64***, align 8 - load i64, i64* %a - store i64* %a, i64** %b - store i64** %b, i64*** %c - store i64*** %c, i64**** %d - - %e = bitcast i64**** %d to i64* - load i64, i64* %e - store i64* %e, i64** %b - %f = load i64*, i64** %b - load i64, i64* %f - ret void -} diff --git a/llvm/test/Analysis/CFLAliasAnalysis/Andersen/interproc-arg-deref-escape.ll b/llvm/test/Analysis/CFLAliasAnalysis/Andersen/interproc-arg-deref-escape.ll deleted file mode 100644 --- a/llvm/test/Analysis/CFLAliasAnalysis/Andersen/interproc-arg-deref-escape.ll +++ /dev/null @@ -1,35 +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 -aa-pipeline=cfl-anders-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s - -declare void @opaque(i32*) -define void @escape_arg_deref(i32** %arg) { - %arg_deref = load i32*, i32** %arg - call void @opaque(i32* %arg_deref) - ret void -} -; CHECK-LABEL: Function: test_arg_deref_escape -; CHECK-DAG: NoAlias: i32* %a, i32** %x -; CHECK-DAG: NoAlias: i32* %b, i32** %x -; CHECK-DAG: NoAlias: i32* %a, i32* %b -; CHECK-DAG: NoAlias: i32** %p, i32** %x -; CHECK-DAG: NoAlias: i32* %a, i32** %p -; CHECK-DAG: NoAlias: i32* %b, i32** %p -; CHECK-DAG: MayAlias: i32* %a, i32* %c -; CHECK-DAG: NoAlias: i32* %b, i32* %c -; CHECK-DAG: NoAlias: i32* %c, i32** %p -define void @test_arg_deref_escape(i32** %x) { - %a = alloca i32, align 4 - %b = alloca i32, align 4 - %p = alloca i32*, align 4 - - load i32, i32* %a - load i32, i32* %b - store i32* %a, i32** %p - call void @escape_arg_deref(i32** %p) - %c = load i32*, i32** %x - load i32, i32* %c - - ret void -} diff --git a/llvm/test/Analysis/CFLAliasAnalysis/Andersen/interproc-arg-escape.ll b/llvm/test/Analysis/CFLAliasAnalysis/Andersen/interproc-arg-escape.ll deleted file mode 100644 --- a/llvm/test/Analysis/CFLAliasAnalysis/Andersen/interproc-arg-escape.ll +++ /dev/null @@ -1,34 +0,0 @@ -; This testcase ensures that CFL AA answers queries soundly when callee tries -; to escape its parameters - -; RUN: opt < %s -aa-pipeline=cfl-anders-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s - -declare void @opaque(i32*) -define void @escape_arg(i32* %arg) { - call void @opaque(i32* %arg) - ret void -} -; CHECK-LABEL: Function: test_arg_escape -; CHECK-DAG: NoAlias: i32* %a, i32** %x -; CHECK-DAG: NoAlias: i32* %b, i32** %x -; CHECK-DAG: NoAlias: i32* %a, i32* %b -; CHECK-DAG: NoAlias: i32* %c, i32** %x -; CHECK-DAG: NoAlias: i32* %a, i32* %c -; CHECK-DAG: NoAlias: i32* %b, i32* %c -; CHECK-DAG: MayAlias: i32* %a, i32* %d -; CHECK-DAG: MayAlias: i32* %b, i32* %d -; CHECK-DAG: NoAlias: i32* %c, i32* %d -define void @test_arg_escape(i32** %x) { - %a = alloca i32, align 4 - %b = alloca i32, align 4 - %c = alloca i32, align 4 - load i32, i32* %a - load i32, i32* %b - load i32, i32* %c - call void @escape_arg(i32* %a) - call void @escape_arg(i32* %b) - %d = load i32*, i32** %x - load i32, i32* %d - - ret void -} diff --git a/llvm/test/Analysis/CFLAliasAnalysis/Andersen/interproc-ret-arg.ll b/llvm/test/Analysis/CFLAliasAnalysis/Andersen/interproc-ret-arg.ll deleted file mode 100644 --- a/llvm/test/Analysis/CFLAliasAnalysis/Andersen/interproc-ret-arg.ll +++ /dev/null @@ -1,28 +0,0 @@ -; This testcase ensures that CFL AA answers queries soundly when callee tries -; to return one of its parameters - -; RUN: opt < %s -aa-pipeline=cfl-anders-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s - -define i32* @return_arg_callee(i32* %arg1, i32* %arg2) { - ret i32* %arg1 -} -; CHECK-LABEL: Function: test_return_arg -; CHECK: NoAlias: i32* %a, i32* %b -; CHECK: MayAlias: i32* %a, i32* %c -; CHECK: NoAlias: i32* %b, i32* %c - -; Temporarily disable modref checks -; NoModRef: Ptr: i32* %a <-> %c = call i32* @return_arg_callee(i32* %a, i32* %b) -; NoModRef: Ptr: i32* %b <-> %c = call i32* @return_arg_callee(i32* %a, i32* %b) -; NoModRef: Ptr: i32* %c <-> %c = call i32* @return_arg_callee(i32* %a, i32* %b) -define void @test_return_arg() { - %a = alloca i32, align 4 - %b = alloca i32, align 4 - - %c = call i32* @return_arg_callee(i32* %a, i32* %b) - load i32, i32* %a - load i32, i32* %b - load i32, i32* %c - - ret void -} diff --git a/llvm/test/Analysis/CFLAliasAnalysis/Andersen/interproc-ret-deref-arg-multilevel.ll b/llvm/test/Analysis/CFLAliasAnalysis/Andersen/interproc-ret-deref-arg-multilevel.ll deleted file mode 100644 --- a/llvm/test/Analysis/CFLAliasAnalysis/Andersen/interproc-ret-deref-arg-multilevel.ll +++ /dev/null @@ -1,56 +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 -aa-pipeline=cfl-anders-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s - -define i32* @return_deref_arg_multilevel_callee(i32*** %arg1) { - %deref = load i32**, i32*** %arg1 - %deref2 = load i32*, i32** %deref - ret i32* %deref2 -} -; CHECK-LABEL: Function: test_return_deref_arg_multilevel -; CHECK: NoAlias: i32* %a, i32* %b -; CHECK: MayAlias: i32* %a, i32* %c -; CHECK: NoAlias: i32* %b, i32* %c -; CHECK: NoAlias: i32* %c, i32** %p -; CHECK: NoAlias: i32* %c, i32*** %pp -; CHECK: MayAlias: i32** %lpp, i32** %p -; CHECK: NoAlias: i32** %lpp, i32*** %pp -; CHECK: NoAlias: i32* %c, i32** %lpp -; CHECK: MayAlias: i32* %a, i32* %lpp_deref -; CHECK: NoAlias: i32* %b, i32* %lpp_deref -; CHECK: NoAlias: i32* %lpp_deref, i32*** %pp -; CHECK: MayAlias: i32* %a, i32* %lp -; CHECK: NoAlias: i32* %b, i32* %lp -; CHECK: NoAlias: i32* %lp, i32** %p -; CHECK: NoAlias: i32* %lp, i32*** %pp -; CHECK: MayAlias: i32* %c, i32* %lp -; CHECK: NoAlias: i32* %lp, i32** %lpp -; CHECK: MayAlias: i32* %lp, i32* %lpp_deref - -; Temporarily disable modref checks -; Just Ref: Ptr: i32** %p <-> %c = call i32* @return_deref_arg_multilevel_callee(i32*** %pp) -; Just Ref: Ptr: i32*** %pp <-> %c = call i32* @return_deref_arg_multilevel_callee(i32*** %pp) -; Just Ref: Ptr: i32** %lpp <-> %c = call i32* @return_deref_arg_multilevel_callee(i32*** %pp) - -define void @test_return_deref_arg_multilevel() { - %a = alloca i32, align 4 - %b = alloca i32, align 4 - %p = alloca i32*, align 8 - %pp = alloca i32**, align 8 - - load i32, i32* %a - load i32, i32* %b - store i32* %a, i32** %p - store i32** %p, i32*** %pp - %c = call i32* @return_deref_arg_multilevel_callee(i32*** %pp) - load i32, i32* %c - - %lpp = load i32**, i32*** %pp - %lpp_deref = load i32*, i32** %lpp - %lp = load i32*, i32** %p - load i32, i32* %lpp_deref - load i32, i32* %lp - - ret void -} diff --git a/llvm/test/Analysis/CFLAliasAnalysis/Andersen/interproc-ret-deref-arg.ll b/llvm/test/Analysis/CFLAliasAnalysis/Andersen/interproc-ret-deref-arg.ll deleted file mode 100644 --- a/llvm/test/Analysis/CFLAliasAnalysis/Andersen/interproc-ret-deref-arg.ll +++ /dev/null @@ -1,40 +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 -aa-pipeline=cfl-anders-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s - -define i32* @return_deref_arg_callee(i32** %arg1) { - %deref = load i32*, i32** %arg1 - ret i32* %deref -} -; CHECK-LABEL: Function: test_return_deref_arg -; CHECK: NoAlias: i32* %a, i32* %b -; CHECK: MayAlias: i32* %a, i32* %c -; CHECK: NoAlias: i32* %b, i32* %c -; CHECK: MayAlias: i32* %a, i32* %lp -; CHECK: NoAlias: i32* %b, i32* %lp -; CHECK: NoAlias: i32* %lp, i32** %p -; CHECK: MayAlias: i32* %c, i32* %lp - -; Temporarily disable modref checks -; NoModRef: Ptr: i32* %a <-> %c = call i32* @return_deref_arg_callee(i32** %p) -; NoModRef: Ptr: i32* %b <-> %c = call i32* @return_deref_arg_callee(i32** %p) -; Just Ref: Ptr: i32** %p <-> %c = call i32* @return_deref_arg_callee(i32** %p) -; NoModRef: Ptr: i32* %c <-> %c = call i32* @return_deref_arg_callee(i32** %p) -; NoModRef: Ptr: i32* %lp <-> %c = call i32* @return_deref_arg_callee(i32** %p) -define void @test_return_deref_arg() { - %a = alloca i32, align 4 - %b = alloca i32, align 4 - %p = alloca i32*, align 8 - - load i32, i32* %a - load i32, i32* %b - store i32* %a, i32** %p - %c = call i32* @return_deref_arg_callee(i32** %p) - load i32, i32* %c - - %lp = load i32*, i32** %p - load i32, i32* %lp - - ret void -} diff --git a/llvm/test/Analysis/CFLAliasAnalysis/Andersen/interproc-ret-escape.ll b/llvm/test/Analysis/CFLAliasAnalysis/Andersen/interproc-ret-escape.ll deleted file mode 100644 --- a/llvm/test/Analysis/CFLAliasAnalysis/Andersen/interproc-ret-escape.ll +++ /dev/null @@ -1,36 +0,0 @@ -; This testcase ensures that CFL AA answers queries soundly when callee tries -; to return an escaped pointer - -; RUN: opt < %s -aa-pipeline=cfl-anders-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s - -declare noalias i8* @malloc(i64) -declare void @opaque(i32*) - -define i32* @return_escaped_callee() { - %ptr = call noalias i8* @malloc(i64 8) - %ptr_cast = bitcast i8* %ptr to i32* - call void @opaque(i32* %ptr_cast) - ret i32* %ptr_cast -} -; CHECK-LABEL: Function: test_return_escape -; CHECK: NoAlias: i32* %a, i32** %x -; CHECK: NoAlias: i32* %b, i32** %x -; CHECK: NoAlias: i32* %a, i32* %b -; CHECK: NoAlias: i32* %c, i32** %x -; CHECK: NoAlias: i32* %a, i32* %c -; CHECK: NoAlias: i32* %b, i32* %c -; CHECK: NoAlias: i32* %a, i32* %d -; CHECK: MayAlias: i32* %b, i32* %d -; CHECK: MayAlias: i32* %c, i32* %d -define void @test_return_escape(i32** %x) { - %a = alloca i32, align 4 - %b = call i32* @return_escaped_callee() - %c = call i32* @return_escaped_callee() - %d = load i32*, i32** %x - load i32, i32* %a - load i32, i32* %b - load i32, i32* %c - load i32, i32* %d - - ret void -} diff --git a/llvm/test/Analysis/CFLAliasAnalysis/Andersen/interproc-ret-ref-arg-multilevel.ll b/llvm/test/Analysis/CFLAliasAnalysis/Andersen/interproc-ret-ref-arg-multilevel.ll deleted file mode 100644 --- a/llvm/test/Analysis/CFLAliasAnalysis/Andersen/interproc-ret-ref-arg-multilevel.ll +++ /dev/null @@ -1,56 +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 -aa-pipeline=cfl-anders-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s - -declare noalias i8* @malloc(i64) - -define i32*** @return_ref_arg_multilevel_callee(i32* %arg1) { - %ptr = call noalias i8* @malloc(i64 8) - %ptr_cast = bitcast i8* %ptr to i32*** - %ptr2 = call noalias i8* @malloc(i64 8) - %ptr_cast2 = bitcast i8* %ptr2 to i32** - store i32* %arg1, i32** %ptr_cast2 - store i32** %ptr_cast2, i32*** %ptr_cast - ret i32*** %ptr_cast -} -; CHECK-LABEL: Function: test_return_ref_arg_multilevel -; CHECK-DAG: NoAlias: i32* %a, i32*** %b -; CHECK-DAG: NoAlias: i32*** %b, i32** %p -; CHECK-DAG: NoAlias: i32*** %b, i32*** %pp -; CHECK-DAG: NoAlias: i32* %a, i32** %lb -; CHECK-DAG: NoAlias: i32** %lb, i32** %p -; CHECK-DAG: NoAlias: i32** %lb, i32*** %pp -; CHECK-DAG: NoAlias: i32*** %b, i32** %lb -; CHECK-DAG: MayAlias: i32* %a, i32* %lb_deref -; CHECK-DAG: NoAlias: i32* %lb_deref, i32** %lpp -; CHECK-DAG: MayAlias: i32* %lb_deref, i32* %lpp_deref -; CHECK-DAG: NoAlias: i32** %lpp, i32* %lpp_deref -; CHECK-DAG: MayAlias: i32* %lb_deref, i32* %lp -; CHECK-DAG: NoAlias: i32* %lp, i32** %lpp -; CHECK-DAG: MayAlias: i32* %lp, i32* %lpp_deref - -; Temporarily disable modref checks -; Just Mod: Ptr: i32*** %b <-> %b = call i32*** @return_ref_arg_multilevel_callee(i32* %a) -; Just Mod: Ptr: i32** %lb <-> %b = call i32*** @return_ref_arg_multilevel_callee(i32* %a) -define void @test_return_ref_arg_multilevel() { - %a = alloca i32, align 4 - %p = alloca i32*, align 8 - %pp = alloca i32**, align 8 - - load i32, i32* %a - store i32* %a, i32** %p - store i32** %p, i32*** %pp - %b = call i32*** @return_ref_arg_multilevel_callee(i32* %a) - - %lb = load i32**, i32*** %b - %lb_deref = load i32*, i32** %lb - %lpp = load i32**, i32*** %pp - %lpp_deref = load i32*, i32** %lpp - %lp = load i32*, i32** %p - load i32, i32* %lb_deref - load i32, i32* %lpp_deref - load i32, i32* %lp - - ret void -} diff --git a/llvm/test/Analysis/CFLAliasAnalysis/Andersen/interproc-ret-ref-arg.ll b/llvm/test/Analysis/CFLAliasAnalysis/Andersen/interproc-ret-ref-arg.ll deleted file mode 100644 --- a/llvm/test/Analysis/CFLAliasAnalysis/Andersen/interproc-ret-ref-arg.ll +++ /dev/null @@ -1,39 +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 -aa-pipeline=cfl-anders-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s - -declare noalias i8* @malloc(i64) - -define i32** @return_ref_arg_callee(i32* %arg1) { - %ptr = call noalias i8* @malloc(i64 8) - %ptr_cast = bitcast i8* %ptr to i32** - store i32* %arg1, i32** %ptr_cast - ret i32** %ptr_cast -} -; CHECK-LABEL: Function: test_return_ref_arg -; CHECK: NoAlias: i32** %b, i32** %p -; CHECK: MayAlias: i32* %a, i32* %lb -; CHECK: NoAlias: i32* %lb, i32** %p -; CHECK: NoAlias: i32** %b, i32* %lb -; CHECK: NoAlias: i32* %lp, i32** %p -; CHECK: NoAlias: i32** %b, i32* %lp -; CHECK: MayAlias: i32* %lb, i32* %lp - -; Temporarily disable modref checks -; Just Mod: Ptr: i32** %b <-> %b = call i32** @return_ref_arg_callee(i32* %a) -define void @test_return_ref_arg() { - %a = alloca i32, align 4 - %p = alloca i32*, align 8 - - load i32, i32* %a - store i32* %a, i32** %p - %b = call i32** @return_ref_arg_callee(i32* %a) - - %lb = load i32*, i32** %b - %lp = load i32*, i32** %p - load i32, i32* %lb - load i32, i32* %lp - - ret void -} diff --git a/llvm/test/Analysis/CFLAliasAnalysis/Andersen/interproc-ret-unknown.ll b/llvm/test/Analysis/CFLAliasAnalysis/Andersen/interproc-ret-unknown.ll deleted file mode 100644 --- a/llvm/test/Analysis/CFLAliasAnalysis/Andersen/interproc-ret-unknown.ll +++ /dev/null @@ -1,43 +0,0 @@ -; This testcase ensures that CFL AA answers queries soundly when callee tries -; to return an unknown pointer - -; RUN: opt < %s -aa-pipeline=cfl-anders-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s - -@g = external global i32 -define i32* @return_unknown_callee(i32* %arg1, i32* %arg2) { - ret i32* @g -} -; CHECK-LABEL: Function: test_return_unknown -; CHECK-DAG: NoAlias: i32* %a, i32* %b -; CHECK-DAG: MayAlias: i32* %c, i32* %x -; CHECK-DAG: NoAlias: i32* %a, i32* %c -; CHECK-DAG: NoAlias: i32* %b, i32* %c -define void @test_return_unknown(i32* %x) { - %a = alloca i32, align 4 - %b = alloca i32, align 4 - - %c = call i32* @return_unknown_callee(i32* %a, i32* %b) - load i32, i32* %a - load i32, i32* %b - load i32, i32* %c - load i32, i32* %x - - ret void -} - -@g2 = external global i32* -define i32** @return_unknown_callee2() { - ret i32** @g2 -} -; CHECK-LABEL: Function: test_return_unknown2 -; CHECK-DAG: MayAlias: i32** %a, i32* %x -; CHECK-DAG: MayAlias: i32* %b, i32* %x -; CHECK-DAG: MayAlias: i32** %a, i32* %b -define void @test_return_unknown2(i32* %x) { - %a = call i32** @return_unknown_callee2() - %b = load i32*, i32** %a - load i32, i32* %b - load i32, i32* %x - - ret void -} diff --git a/llvm/test/Analysis/CFLAliasAnalysis/Andersen/interproc-store-arg-multilevel.ll b/llvm/test/Analysis/CFLAliasAnalysis/Andersen/interproc-store-arg-multilevel.ll deleted file mode 100644 --- a/llvm/test/Analysis/CFLAliasAnalysis/Andersen/interproc-store-arg-multilevel.ll +++ /dev/null @@ -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 -aa-pipeline=cfl-anders-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s - -declare noalias i8* @malloc(i64) - -define void @store_arg_multilevel_callee(i32*** %arg1, i32* %arg2) { - %ptr = call noalias i8* @malloc(i64 8) - %ptr_cast = bitcast i8* %ptr to i32** - store i32* %arg2, i32** %ptr_cast - store i32** %ptr_cast, i32*** %arg1 - ret void -} -; CHECK-LABEL: Function: test_store_arg_multilevel -; CHECK: NoAlias: i32* %a, i32* %b -; CHECK: NoAlias: i32* %a, i32** %lpp -; CHECK: NoAlias: i32* %b, i32** %lpp -; CHECK: MayAlias: i32** %lpp, i32** %p -; CHECK: MayAlias: i32* %a, i32* %lpp_deref -; CHECK: MayAlias: i32* %b, i32* %lpp_deref -; CHECK: NoAlias: i32* %lpp_deref, i32** %p -; CHECK: NoAlias: i32* %lpp_deref, i32*** %pp -; CHECK: NoAlias: i32** %lpp, i32* %lpp_deref -; CHECK: MayAlias: i32* %a, i32* %lp -; CHECK: NoAlias: i32* %lp, i32*** %pp -; CHECK: NoAlias: i32* %lp, i32** %lpp -; CHECK: MayAlias: i32* %lp, i32* %lpp_deref -define void @test_store_arg_multilevel() { - %a = alloca i32, align 4 - %b = alloca i32, align 4 - %p = alloca i32*, align 8 - %pp = alloca i32**, align 8 - - load i32, i32* %a - load i32, i32* %b - store i32* %a, i32** %p - store i32** %p, i32*** %pp - call void @store_arg_multilevel_callee(i32*** %pp, i32* %b) - - %lpp = load i32**, i32*** %pp - %lpp_deref = load i32*, i32** %lpp - %lp = load i32*, i32** %p - load i32, i32* %lpp_deref - load i32, i32* %lp - - ret void -} diff --git a/llvm/test/Analysis/CFLAliasAnalysis/Andersen/interproc-store-arg-unknown.ll b/llvm/test/Analysis/CFLAliasAnalysis/Andersen/interproc-store-arg-unknown.ll deleted file mode 100644 --- a/llvm/test/Analysis/CFLAliasAnalysis/Andersen/interproc-store-arg-unknown.ll +++ /dev/null @@ -1,35 +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 -aa-pipeline=cfl-anders-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s - -@g = external global i32 - -define void @store_arg_unknown_callee(i32** %arg1) { - store i32* @g, i32** %arg1 - ret void -} -; CHECK-LABEL: Function: test_store_arg_unknown -; CHECK: NoAlias: i32** %p, i32* %x -; CHECK: NoAlias: i32* %a, i32** %p -; CHECK: NoAlias: i32* %b, i32** %p -; CHECK: MayAlias: i32* %lp, i32* %x -; CHECK: MayAlias: i32* %a, i32* %lp -; CHECK: NoAlias: i32* %b, i32* %lp -; CHECK: NoAlias: i32* %lp, i32** %p -define void @test_store_arg_unknown(i32* %x) { - %a = alloca i32, align 4 - %b = alloca i32, align 4 - %p = alloca i32*, align 8 - - load i32, i32* %x - load i32, i32* %a - load i32, i32* %b - store i32* %a, i32** %p - call void @store_arg_unknown_callee(i32** %p) - - %lp = load i32*, i32** %p - load i32, i32* %lp - - ret void -} diff --git a/llvm/test/Analysis/CFLAliasAnalysis/Andersen/interproc-store-arg.ll b/llvm/test/Analysis/CFLAliasAnalysis/Andersen/interproc-store-arg.ll deleted file mode 100644 --- a/llvm/test/Analysis/CFLAliasAnalysis/Andersen/interproc-store-arg.ll +++ /dev/null @@ -1,43 +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 -aa-pipeline=cfl-anders-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s - -define void @store_arg_callee(i32** %arg1, i32* %arg2) { - store i32* %arg2, i32** %arg1 - ret void -} -; CHECK-LABEL: Function: test_store_arg -; CHECK: NoAlias: i32* %a, i32* %b -; CHECK: NoAlias: i32* %a, i32** %p -; CHECK: NoAlias: i32* %b, i32** %p -; CHECK: MayAlias: i32* %a, i32* %lp -; CHECK: MayAlias: i32* %b, i32* %lp -; CHECK: NoAlias: i32* %a, i32* %lq -; CHECK: MayAlias: i32* %b, i32* %lq -; CHECK: MayAlias: i32* %lp, i32* %lq - -; Temporarily disable modref checks -; NoModRef: Ptr: i32* %a <-> call void @store_arg_callee(i32** %p, i32* %b) -; Just Ref: Ptr: i32* %b <-> call void @store_arg_callee(i32** %p, i32* %b) -; Just Mod: Ptr: i32** %p <-> call void @store_arg_callee(i32** %p, i32* %b) -; NoModRef: Ptr: i32** %q <-> call void @store_arg_callee(i32** %p, i32* %b) -define void @test_store_arg() { - %a = alloca i32, align 4 - %b = alloca i32, align 4 - %p = alloca i32*, align 8 - %q = alloca i32*, align 8 - - load i32, i32* %a - load i32, i32* %b - store i32* %a, i32** %p - store i32* %b, i32** %q - call void @store_arg_callee(i32** %p, i32* %b) - - %lp = load i32*, i32** %p - %lq = load i32*, i32** %q - load i32, i32* %lp - load i32, i32* %lq - - ret void -} diff --git a/llvm/test/Analysis/CFLAliasAnalysis/Andersen/memalias.ll b/llvm/test/Analysis/CFLAliasAnalysis/Andersen/memalias.ll deleted file mode 100644 --- a/llvm/test/Analysis/CFLAliasAnalysis/Andersen/memalias.ll +++ /dev/null @@ -1,22 +0,0 @@ -; This testcase ensures that CFL AA correctly handles simple memory alias -; pattern - -; RUN: opt < %s -aa-pipeline=cfl-anders-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s - -; CHECK-LABEL: Function: test_memalias -; CHECK: NoAlias: i64* %a, i64** %b -; CHECK: NoAlias: i64* %a, i32** %c -; CHECK: MayAlias: i64* %a, i32* %d -; CHECK: NoAlias: i64** %b, i32* %d -; CHECK: NoAlias: i32** %c, i32* %d -define void @test_memalias() { - %a = alloca i64, align 8 - %b = alloca i64*, align 8 - load i64, i64* %a - store i64* %a, i64** %b - - %c = bitcast i64** %b to i32** - %d = load i32*, i32** %c - load i32, i32* %d - ret void -} diff --git a/llvm/test/Analysis/CFLAliasAnalysis/Andersen/struct.ll b/llvm/test/Analysis/CFLAliasAnalysis/Andersen/struct.ll deleted file mode 100644 --- a/llvm/test/Analysis/CFLAliasAnalysis/Andersen/struct.ll +++ /dev/null @@ -1,17 +0,0 @@ -; Ensures that our struct ops are sane. - -; RUN: opt < %s -aa-pipeline=cfl-anders-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s - -; Since we ignore non-pointer values, we effectively ignore extractvalue -; instructions. This means that %c "doesn't exist" in test_structure's graph, -; so we currently get MayAlias. -; XFAIL: * - -; CHECK-LABEL: Function: test_structure -; CHECK: NoAlias: i64** %c, { i64**, i64** }* %a -define void @test_structure() { - %a = alloca {i64**, i64**}, align 8 - %b = load {i64**, i64**}, {i64**, i64**}* %a - %c = extractvalue {i64**, i64**} %b, 0 - ret void -} diff --git a/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/arguments-globals.ll b/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/arguments-globals.ll deleted file mode 100644 --- a/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/arguments-globals.ll +++ /dev/null @@ -1,26 +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 -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s - -; CHECK: Function: test - -@g = external global i32 - -; CHECK: MayAlias: i32* %arg1, i32* %arg2 -; CHECK: NoAlias: i32* %A, i32* %arg1 -; CHECK: NoAlias: i32* %A, i32* %arg2 -; CHECK: MayAlias: i32* %arg1, i32* @g -; CHECK: MayAlias: i32* %arg2, i32* @g -; CHECK: MayAlias: i32* %A, i32* @g -define void @test(i1 %c, i32* %arg1, i32* %arg2) { - %A = alloca i32 - load i32, i32* %arg1 - load i32, i32* %arg2 - load i32, i32* %A - load i32, i32* @g - - ret void -} diff --git a/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/arguments.ll b/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/arguments.ll deleted file mode 100644 --- a/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/arguments.ll +++ /dev/null @@ -1,19 +0,0 @@ -; This testcase ensures that CFL AA gives conservative answers on variables -; that involve arguments. - -; RUN: opt < %s -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s - -; CHECK: Function: test - -define void @test(i1 %c, i32* %arg1, i32* %arg2) { - ; CHECK: 6 Total Alias Queries Performed - ; CHECK: 3 no alias responses - %a = alloca i32, align 4 - %b = select i1 %c, i32* %arg1, i32* %arg2 - load i32, i32* %a - load i32, i32* %b - load i32, i32* %arg1 - load i32, i32* %arg2 - - ret void -} diff --git a/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/asm-global-bugfix.ll b/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/asm-global-bugfix.ll deleted file mode 100644 --- a/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/asm-global-bugfix.ll +++ /dev/null @@ -1,18 +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 -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s - -@G = private unnamed_addr constant [1 x i8] c"\00", align 1 - -; CHECK: Function: test_no_crash -; CHECK: 0 no alias responses -define void @test_no_crash() #0 { -entry: - call i8* asm "nop", "=r,r"( - i8* getelementptr inbounds ([1 x i8], [1 x i8]* @G, i64 0, i64 0)) - load [1 x i8], [1 x i8]* @G - load i8, i8* getelementptr inbounds ([1 x i8], [1 x i8]* @G, i64 0, i64 0) - ret void -} diff --git a/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/attr-escape.ll b/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/attr-escape.ll deleted file mode 100644 --- a/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/attr-escape.ll +++ /dev/null @@ -1,112 +0,0 @@ -; This testcase ensures that CFL AA handles escaped values no more conservative than it should - -; RUN: opt < %s -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s - -; CHECK-LABEL: Function: test_local -; CHECK: NoAlias: i32* %a, i32* %b -; CHECK: MayAlias: i32* %a, i32* %aAlias -; CHECK: NoAlias: i32* %aAlias, i32* %b -define void @test_local() { - %a = alloca i32, align 4 - %b = alloca i32, align 4 - %aint = ptrtoint i32* %a to i64 - %aAlias = inttoptr i64 %aint to i32* - load i32, i32* %a - load i32, i32* %b - load i32, i32* %aAlias - ret void -} - -; CHECK-LABEL: Function: test_global_param -; CHECK-DAG: NoAlias: i32* %a, i32** %x -; CHECK-DAG: MayAlias: i32* %a, i32* %xload -; CHECK-DAG: MayAlias: i32* %a, i32* %gload -; CHECK-DAG: MayAlias: i32* %gload, i32* %xload -; CHECK-DAG: MayAlias: i32** %x, i32** @ext_global -; CHECK-DAG: NoAlias: i32* %a, i32** @ext_global -@ext_global = external global i32* -define void @test_global_param(i32** %x) { - %a = alloca i32, align 4 - %aint = ptrtoint i32* %a to i64 - %xload = load i32*, i32** %x - %gload = load i32*, i32** @ext_global - load i32, i32* %a - load i32, i32* %xload - load i32, i32* %gload - ret void -} - -declare void @external_func(i32**) -; CHECK-LABEL: Function: test_external_call -; CHECK-DAG: NoAlias: i32* %b, i32* %x -; CHECK-DAG: NoAlias: i32** %a, i32* %b -; CHECK-DAG: MayAlias: i32* %c, i32* %x -; CHECK-DAG: MayAlias: i32** %a, i32* %c -; CHECK-DAG: NoAlias: i32* %b, i32* %c -define void @test_external_call(i32* %x) { - %a = alloca i32*, align 8 - %b = alloca i32, align 4 - call void @external_func(i32** %a) - %c = load i32*, i32** %a - load i32, i32* %x - load i32, i32* %b - load i32, i32* %c - ret void -} - -declare void @external_func_readonly(i32**) readonly -; CHECK-LABEL: Function: test_external_call_func_readonly -; CHECK-DAG: MayAlias: i32* %c, i32* %x -; CHECK-DAG: NoAlias: i32** %a, i32* %c -define void @test_external_call_func_readonly(i32* %x) { - %a = alloca i32*, align 8 - %b = alloca i32, align 4 - store i32* %x, i32** %a, align 4 - call void @external_func_readonly(i32** %a) - %c = load i32*, i32** %a - load i32, i32* %x - load i32, i32* %c - ret void -} - -; CHECK-LABEL: Function: test_external_call_callsite_readonly -; CHECK-DAG: MayAlias: i32* %c, i32* %x -; CHECK-DAG: NoAlias: i32** %a, i32* %c -define void @test_external_call_callsite_readonly(i32* %x) { - %a = alloca i32*, align 8 - %b = alloca i32, align 4 - store i32* %x, i32** %a, align 4 - call void @external_func(i32** %a) readonly - %c = load i32*, i32** %a - load i32, i32* %x - load i32, i32* %c - ret void -} - -declare i32* @external_func_normal_return(i32*) -; CHECK-LABEL: Function: test_external_call_normal_return -; CHECK-DAG: MayAlias: i32* %c, i32* %x -; CHECK-DAG: MayAlias: i32* %a, i32* %c -define void @test_external_call_normal_return(i32* %x) { - %a = alloca i32, align 8 - %b = alloca i32, align 4 - %c = call i32* @external_func_normal_return(i32* %a) - load i32, i32* %a - load i32, i32* %x - load i32, i32* %c - ret void -} - -declare noalias i32* @external_func_noalias_return(i32*) -; CHECK-LABEL: Function: test_external_call_noalias_return -; CHECK-DAG: NoAlias: i32* %c, i32* %x -; CHECK-DAG: NoAlias: i32* %a, i32* %c -define void @test_external_call_noalias_return(i32* %x) { - %a = alloca i32, align 8 - %b = alloca i32, align 4 - %c = call i32* @external_func_noalias_return(i32* %a) - load i32, i32* %a - load i32, i32* %x - load i32, i32* %c - ret void -} diff --git a/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/basic-interproc.ll b/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/basic-interproc.ll deleted file mode 100644 --- a/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/basic-interproc.ll +++ /dev/null @@ -1,23 +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 -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s - -; CHECK-LABEL: Function: noop_callee -; CHECK: MayAlias: i32* %arg1, i32* %arg2 -define void @noop_callee(i32* %arg1, i32* %arg2) { - store i32 0, i32* %arg1 - store i32 0, i32* %arg2 - ret void -} -; CHECK-LABEL: Function: test_noop -; CHECK: NoAlias: i32* %a, i32* %b -define void @test_noop() { - %a = alloca i32, align 4 - %b = alloca i32, align 4 - load i32, i32* %a - load i32, i32* %b - call void @noop_callee(i32* %a, i32* %b) - - ret void -} diff --git a/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/branch-alias.ll b/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/branch-alias.ll deleted file mode 100644 --- a/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/branch-alias.ll +++ /dev/null @@ -1,74 +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 -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s - -; CHECK: Function: ptr_test -define void @ptr_test() #0 { - ; CHECK: MayAlias: i32** %A, i32** %ShouldAliasA - ; CHECK-NOT: %AliasA1 -entry: - %A = alloca i32*, align 8 - %RefCopy = alloca i64, align 8 - %i = alloca i32, align 4 - %AliasA1 = alloca i32**, align 8 - %ShouldAliasA = alloca i32*, align 8 - %ignore1 = load i32*, i32** %A - store i64 0, i64* %RefCopy, align 8 - store i32 0, i32* %i, align 4 - br label %for.cond - -for.cond: ; preds = %for.inc, %entry - %0 = load i32, i32* %i, align 4 - %conv = sext i32 %0 to i64 - %cmp = icmp ult i64 %conv, 64 - br i1 %cmp, label %for.body, label %for.end - -for.body: ; preds = %for.cond - %1 = ptrtoint i32** %A to i64 - %2 = load i32, i32* %i, align 4 - %sh_prom = zext i32 %2 to i64 - %shl = shl i64 1, %sh_prom - %and = and i64 %1, %shl - %tobool = icmp ne i64 %and, 0 - br i1 %tobool, label %if.then, label %if.end - -if.then: ; preds = %for.body - %3 = load i32, i32* %i, align 4 - %sh_prom2 = zext i32 %3 to i64 - %shl3 = shl i64 1, %sh_prom2 - %4 = load i64, i64* %RefCopy, align 8 - %or = or i64 %4, %shl3 - store i64 %or, i64* %RefCopy, align 8 - br label %if.end - -if.end: ; preds = %if.then, %for.body - br label %for.inc - -for.inc: ; preds = %if.end - %5 = load i32, i32* %i, align 4 - %inc = add nsw i32 %5, 1 - store i32 %inc, i32* %i, align 4 - br label %for.cond - -for.end: ; preds = %for.cond - %6 = load i64, i64* %RefCopy, align 8 - %7 = inttoptr i64 %6 to i32** - store i32** %7, i32*** %AliasA1, align 8 - %8 = load i32**, i32*** %AliasA1, align 8 - %9 = load i32*, i32** %8, align 8 - store i32* %9, i32** %ShouldAliasA, align 8 - ret void -} diff --git a/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/const-expr-gep.ll b/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/const-expr-gep.ll deleted file mode 100644 --- a/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/const-expr-gep.ll +++ /dev/null @@ -1,65 +0,0 @@ -; This testcase consists of alias relations which should be completely -; resolvable by cfl-steens-aa, but require analysis of getelementptr constant exprs. -; Derived from BasicAA/2003-12-11-ConstExprGEP.ll - -; RUN: opt < %s -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s - -%T = type { i32, [10 x i8] } - -@G = external global %T -@G2 = external global %T - -; TODO: Quite a few of these are MayAlias because we don't yet consider -; constant offsets in CFLSteensAA. If we start doing so, then we'll need to -; change these test cases - -; CHECK: Function: test -; CHECK: MayAlias: i32* %D, i32* %F -; CHECK: MayAlias: i32* %D, i8* %X -; CHECK: MayAlias: i32* %F, i8* %X -define void @test() { - %D = getelementptr %T, %T* @G, i64 0, i32 0 - %F = getelementptr i32, i32* getelementptr (%T, %T* @G, i64 0, i32 0), i64 0 - %X = getelementptr [10 x i8], [10 x i8]* getelementptr (%T, %T* @G, i64 0, i32 1), i64 0, i64 5 - load i32, i32* %D - load i32, i32* %F - load i8, i8* %X - - ret void -} - -; CHECK: Function: simplecheck -; CHECK: MayAlias: i32* %F, i32* %arg0 -; CHECK: MayAlias: i32* %H, i32* %arg0 -; CHECK: MayAlias: i32* %F, i32* %H -define void @simplecheck(i32* %arg0) { - %F = getelementptr i32, i32* getelementptr (%T, %T* @G, i64 0, i32 0), i64 0 - %H = getelementptr %T, %T* @G2, i64 0, i32 0 - load i32, i32* %arg0 - load i32, i32* %F - load i32, i32* %H - - ret void -} - -; Ensure that CFLSteensAA properly identifies and handles escaping variables (i.e. -; globals) in nested ConstantExprs - -; CHECK: Function: checkNesting -; CHECK: MayAlias: i32* %A, i32* %arg0 - -%NestedT = type { [1 x [1 x i32]] } -@NT = external global %NestedT - -define void @checkNesting(i32* %arg0) { - %A = getelementptr [1 x i32], - [1 x i32]* getelementptr - ([1 x [1 x i32]], [1 x [1 x i32]]* getelementptr (%NestedT, %NestedT* @NT, i64 0, i32 0), - i64 0, - i32 0), - i64 0, - i32 0 - load i32, i32* %arg0 - load i32, i32* %A - ret void -} diff --git a/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/const-exprs.ll b/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/const-exprs.ll deleted file mode 100644 --- a/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/const-exprs.ll +++ /dev/null @@ -1,31 +0,0 @@ -; RUN: opt %s -S -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-all-alias-modref-info 2>&1 | FileCheck %s -; -; Regression: we weren't properly checking constexpr selects. - -@g = extern_weak dso_local global i32, align 4 -@g2 = extern_weak dso_local global i32, align 4 -@g3 = extern_weak dso_local global i32, align 4 - -; CHECK-LABEL: Function: foo -; CHECK-DAG: NoAlias: i32** %a, i32* select (i1 icmp ne (i32* @g, i32* null), i32* @g2, i32* @g3) -; CHECK-DAG: NoAlias: i32** %a, i32* %b -; CHECK-DAG: MayAlias: i32* %b, i32* select (i1 icmp ne (i32* @g, i32* null), i32* @g2, i32* @g3) -; CHECK-DAG: NoAlias: i32** %a, i32* @g2 -; CHECK-DAG: MayAlias: i32* @g2, i32* select (i1 icmp ne (i32* @g, i32* null), i32* @g2, i32* @g3) -; CHECK-DAG: MayAlias: i32* %b, i32* @g2 -; CHECK-DAG: NoAlias: i32** %a, i32* @g3 -; CHECK-DAG: MayAlias: i32* @g3, i32* select (i1 icmp ne (i32* @g, i32* null), i32* @g2, i32* @g3) -; CHECK-DAG: MayAlias: i32* %b, i32* @g3 -; CHECK-DAG: MayAlias: i32* @g2, i32* @g3 - -define void @foo() { -entry: - %a = alloca i32*, align 8 - load i32, i32* select (i1 icmp ne (i32* @g, i32* null), i32* @g2, i32* @g3) - store i32* select (i1 icmp ne (i32* @g, i32* null), i32* @g2, i32* @g3), i32** %a - %b = load i32*, i32** %a - %c = load i32, i32* %b - %d = load i32, i32* @g2 - %e = load i32, i32* @g3 - ret void -} diff --git a/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/constant-over-index.ll b/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/constant-over-index.ll deleted file mode 100644 --- a/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/constant-over-index.ll +++ /dev/null @@ -1,30 +0,0 @@ -; RUN: opt < %s -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-all-alias-modref-info 2>&1 | FileCheck %s - -; CFL AA currently returns PartialAlias, BasicAA returns MayAlias, both seem -; acceptable (although we might decide that we don't want PartialAlias, and if -; so, we should update this test case accordingly). -; CHECK: {{PartialAlias|MayAlias}}: double* %p.0.i.0, double* %p3 - -; %p3 is equal to %p.0.i.0 on the second iteration of the loop, -; so MayAlias is needed. - -define void @foo([3 x [3 x double]]* noalias %p) { -entry: - %p3 = getelementptr [3 x [3 x double]], [3 x [3 x double]]* %p, i64 0, i64 0, i64 3 - br label %loop - -loop: - %i = phi i64 [ 0, %entry ], [ %i.next, %loop ] - - %p.0.i.0 = getelementptr [3 x [3 x double]], [3 x [3 x double]]* %p, i64 0, i64 %i, i64 0 - - store volatile double 0.0, double* %p3 - store volatile double 0.1, double* %p.0.i.0 - - %i.next = add i64 %i, 1 - %cmp = icmp slt i64 %i.next, 3 - br i1 %cmp, label %loop, label %exit - -exit: - ret void -} diff --git a/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/empty.ll b/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/empty.ll deleted file mode 100644 --- a/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/empty.ll +++ /dev/null @@ -1,12 +0,0 @@ -; RUN: opt < %s -aa-pipeline=basic-aa,cfl-steens-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s - -target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64" - -; CHECK: Function: foo: -; CHECK-NEXT: NoAlias: {}* %p, {}* %q - -define void @foo({}* %p, {}* %q) { - store {} {}, {}* %p - store {} {}, {}* %q - ret void -} diff --git a/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/full-store-partial-alias.ll b/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/full-store-partial-alias.ll deleted file mode 100644 --- a/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/full-store-partial-alias.ll +++ /dev/null @@ -1,39 +0,0 @@ -; RUN: opt -S -aa-pipeline=tbaa,cfl-steens-aa -passes=gvn < %s | FileCheck -check-prefix=CFLSteensAA %s -; RUN: opt -S -aa-pipeline=tbaa -passes=gvn < %s | FileCheck %s -; Adapted from the BasicAA full-store-partial-alias.ll test. - -; CFL AA could notice that the store stores to the entire %u object, -; so the %tmp5 load is PartialAlias with the store and suppress TBAA. -; FIXME: However, right now, CFLSteensAA cannot prove PartialAlias here -; Without CFL AA, TBAA should say that %tmp5 is NoAlias with the store. - -target datalayout = "e-p:64:64:64" - -%union.anon = type { double } - -@u = global %union.anon { double -2.500000e-01 }, align 8 -@endianness_test = global i64 1, align 8 - -define i32 @signbit(double %x) nounwind { -; FIXME: This would be ret i32 %tmp5.lobit if CFLSteensAA could prove PartialAlias -; CFLSteensAA: ret i32 0 -; CHECK: ret i32 0 -entry: - %u = alloca %union.anon, align 8 - %tmp9 = getelementptr inbounds %union.anon, %union.anon* %u, i64 0, i32 0 - store double %x, double* %tmp9, align 8, !tbaa !0 - %tmp2 = load i32, i32* bitcast (i64* @endianness_test to i32*), align 8, !tbaa !3 - %idxprom = sext i32 %tmp2 to i64 - %tmp4 = bitcast %union.anon* %u to [2 x i32]* - %arrayidx = getelementptr inbounds [2 x i32], [2 x i32]* %tmp4, i64 0, i64 %idxprom - %tmp5 = load i32, i32* %arrayidx, align 4, !tbaa !3 - %tmp5.lobit = lshr i32 %tmp5, 31 - ret i32 %tmp5.lobit -} - -!0 = !{!4, !4, i64 0} -!1 = !{!"omnipotent char", !2} -!2 = !{!"Simple C/C++ TBAA"} -!3 = !{!5, !5, i64 0} -!4 = !{!"double", !1} -!5 = !{!"int", !1} diff --git a/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/gep-index-no-alias.ll b/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/gep-index-no-alias.ll deleted file mode 100644 --- a/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/gep-index-no-alias.ll +++ /dev/null @@ -1,17 +0,0 @@ -; This testcase ensures that gep result does not alias gep indices - -; RUN: opt < %s -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-no-aliases -disable-output 2>&1 | FileCheck %s - -; CHECK: Function: foo -; CHECK: [2 x i32]* %a, [2 x i32]* %b -define void @foo(i32 %n) { - %a = alloca [2 x i32], align 4 - %b = alloca [2 x i32], align 4 - %c = getelementptr inbounds [2 x i32], [2 x i32]* %a, i32 0, i32 %n - %d = getelementptr inbounds [2 x i32], [2 x i32]* %b, i32 0, i32 %n - load [2 x i32], [2 x i32]* %a - load [2 x i32], [2 x i32]* %b - load i32, i32* %c - load i32, i32* %d - ret void -} diff --git a/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/gep-signed-arithmetic.ll b/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/gep-signed-arithmetic.ll deleted file mode 100644 --- a/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/gep-signed-arithmetic.ll +++ /dev/null @@ -1,19 +0,0 @@ -; RUN: opt < %s -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s -; Derived from BasicAA/2010-09-15-GEP-SignedArithmetic.ll - -target datalayout = "e-p:32:32:32" - -; FIXME: This could be PartialAlias but CFLSteensAA can't currently prove it -; CHECK: 1 may alias response - -define i32 @test(i32 %indvar) nounwind { - %tab = alloca i32, align 4 - %tmp31 = mul i32 %indvar, -2 - %tmp32 = add i32 %tmp31, 30 - %t.5 = getelementptr i32, i32* %tab, i32 %tmp32 - %loada = load i32, i32* %tab - store i32 0, i32* %t.5 - %loadb = load i32, i32* %tab - %rval = add i32 %loada, %loadb - ret i32 %rval -} diff --git a/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-arg-deref-escape.ll b/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-arg-deref-escape.ll deleted file mode 100644 --- a/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-arg-deref-escape.ll +++ /dev/null @@ -1,35 +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 -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s - -declare void @opaque(i32*) -define void @escape_arg_deref(i32** %arg) { - %arg_deref = load i32*, i32** %arg - call void @opaque(i32* %arg_deref) - ret void -} -; CHECK-LABEL: Function: test_arg_deref_escape -; CHECK-DAG: NoAlias: i32* %a, i32** %x -; CHECK-DAG: NoAlias: i32* %b, i32** %x -; CHECK-DAG: NoAlias: i32* %a, i32* %b -; CHECK-DAG: NoAlias: i32** %p, i32** %x -; CHECK-DAG: NoAlias: i32* %a, i32** %p -; CHECK-DAG: NoAlias: i32* %b, i32** %p -; CHECK-DAG: MayAlias: i32* %a, i32* %c -; CHECK-DAG: NoAlias: i32* %b, i32* %c -; CHECK-DAG: NoAlias: i32* %c, i32** %p -define void @test_arg_deref_escape(i32** %x) { - %a = alloca i32, align 4 - %b = alloca i32, align 4 - %p = alloca i32*, align 4 - - load i32, i32* %a - load i32, i32* %b - store i32* %a, i32** %p - call void @escape_arg_deref(i32** %p) - %c = load i32*, i32** %x - load i32, i32* %c - - ret void -} diff --git a/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-arg-escape.ll b/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-arg-escape.ll deleted file mode 100644 --- a/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-arg-escape.ll +++ /dev/null @@ -1,34 +0,0 @@ -; This testcase ensures that CFL AA answers queries soundly when callee tries -; to escape its parameters - -; RUN: opt < %s -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s - -declare void @opaque(i32*) -define void @escape_arg(i32* %arg) { - call void @opaque(i32* %arg) - ret void -} -; CHECK-LABEL: Function: test_arg_escape -; CHECK-DAG: NoAlias: i32* %a, i32** %x -; CHECK-DAG: NoAlias: i32* %b, i32** %x -; CHECK-DAG: NoAlias: i32* %a, i32* %b -; CHECK-DAG: NoAlias: i32* %c, i32** %x -; CHECK-DAG: NoAlias: i32* %a, i32* %c -; CHECK-DAG: NoAlias: i32* %b, i32* %c -; CHECK-DAG: MayAlias: i32* %a, i32* %d -; CHECK-DAG: MayAlias: i32* %b, i32* %d -; CHECK-DAG: NoAlias: i32* %c, i32* %d -define void @test_arg_escape(i32** %x) { - %a = alloca i32, align 4 - %b = alloca i32, align 4 - %c = alloca i32, align 4 - load i32, i32* %a - load i32, i32* %b - load i32, i32* %c - call void @escape_arg(i32* %a) - call void @escape_arg(i32* %b) - %d = load i32*, i32** %x - load i32, i32* %d - - ret void -} diff --git a/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-ret-arg.ll b/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-ret-arg.ll deleted file mode 100644 --- a/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-ret-arg.ll +++ /dev/null @@ -1,26 +0,0 @@ -; This testcase ensures that CFL AA answers queries soundly when callee tries -; to return one of its parameters - -; RUN: opt < %s -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s - -define i32* @return_arg_callee(i32* %arg1, i32* %arg2) { - ret i32* %arg1 -} -; CHECK-LABEL: Function: test_return_arg -; CHECK: NoAlias: i32* %a, i32* %b -; CHECK: MayAlias: i32* %a, i32* %c -; CHECK: NoAlias: i32* %b, i32* %c - -; Temporarily disable modref checks -; NoModRef: Ptr: i32* %b <-> %c = call i32* @return_arg_callee(i32* %a, i32* %b) -define void @test_return_arg() { - %a = alloca i32, align 4 - %b = alloca i32, align 4 - - load i32, i32* %a - load i32, i32* %b - %c = call i32* @return_arg_callee(i32* %a, i32* %b) - load i32, i32* %c - - ret void -} diff --git a/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-ret-deref-arg-multilevel.ll b/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-ret-deref-arg-multilevel.ll deleted file mode 100644 --- a/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-ret-deref-arg-multilevel.ll +++ /dev/null @@ -1,50 +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 -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s - -define i32* @return_deref_arg_multilevel_callee(i32*** %arg1) { - %deref = load i32**, i32*** %arg1 - %deref2 = load i32*, i32** %deref - ret i32* %deref2 -} -; CHECK-LABEL: Function: test_return_deref_arg_multilevel -; CHECK: NoAlias: i32* %a, i32* %b -; CHECK: MayAlias: i32* %a, i32* %c -; CHECK: NoAlias: i32* %b, i32* %c -; CHECK: NoAlias: i32* %c, i32** %p -; CHECK: NoAlias: i32* %c, i32*** %pp -; CHECK: MayAlias: i32** %lpp, i32** %p -; CHECK: NoAlias: i32** %lpp, i32*** %pp -; CHECK: NoAlias: i32* %c, i32** %lpp -; CHECK: MayAlias: i32* %a, i32* %lpp_deref -; CHECK: NoAlias: i32* %b, i32* %lpp_deref -; CHECK: NoAlias: i32* %lpp_deref, i32*** %pp -; CHECK: MayAlias: i32* %a, i32* %lp -; CHECK: NoAlias: i32* %b, i32* %lp -; CHECK: NoAlias: i32* %lp, i32** %p -; CHECK: NoAlias: i32* %lp, i32*** %pp -; CHECK: MayAlias: i32* %c, i32* %lp -; CHECK: NoAlias: i32* %lp, i32** %lpp -; CHECK: MayAlias: i32* %lp, i32* %lpp_deref -define void @test_return_deref_arg_multilevel() { - %a = alloca i32, align 4 - %b = alloca i32, align 4 - %p = alloca i32*, align 8 - %pp = alloca i32**, align 8 - - load i32, i32* %a - load i32, i32* %b - store i32* %a, i32** %p - store i32** %p, i32*** %pp - %c = call i32* @return_deref_arg_multilevel_callee(i32*** %pp) - load i32, i32* %c - - %lpp = load i32**, i32*** %pp - %lpp_deref = load i32*, i32** %lpp - %lp = load i32*, i32** %p - load i32, i32* %lpp_deref - load i32, i32* %lp - - ret void -} diff --git a/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-ret-deref-arg.ll b/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-ret-deref-arg.ll deleted file mode 100644 --- a/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-ret-deref-arg.ll +++ /dev/null @@ -1,33 +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 -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s - -define i32* @return_deref_arg_callee(i32** %arg1) { - %deref = load i32*, i32** %arg1 - ret i32* %deref -} -; CHECK-LABEL: Function: test_return_deref_arg -; CHECK: NoAlias: i32* %a, i32* %b -; CHECK: MayAlias: i32* %a, i32* %c -; CHECK: NoAlias: i32* %b, i32* %c -; CHECK: MayAlias: i32* %a, i32* %lp -; CHECK: NoAlias: i32* %b, i32* %lp -; CHECK: NoAlias: i32* %lp, i32** %p -; CHECK: MayAlias: i32* %c, i32* %lp -define void @test_return_deref_arg() { - %a = alloca i32, align 4 - %b = alloca i32, align 4 - %p = alloca i32*, align 8 - - load i32, i32* %a - load i32, i32* %b - store i32* %a, i32** %p - %c = call i32* @return_deref_arg_callee(i32** %p) - - %lp = load i32*, i32** %p - load i32, i32* %c - load i32, i32* %lp - - ret void -} diff --git a/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-ret-escape.ll b/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-ret-escape.ll deleted file mode 100644 --- a/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-ret-escape.ll +++ /dev/null @@ -1,36 +0,0 @@ -; This testcase ensures that CFL AA answers queries soundly when callee tries -; to return an escaped pointer - -; RUN: opt < %s -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s - -declare noalias i8* @malloc(i64) -declare void @opaque(i32*) - -define i32* @return_escaped_callee() { - %ptr = call noalias i8* @malloc(i64 8) - %ptr_cast = bitcast i8* %ptr to i32* - call void @opaque(i32* %ptr_cast) - ret i32* %ptr_cast -} -; CHECK-LABEL: Function: test_return_escape -; CHECK-DAG: NoAlias: i32* %a, i32** %x -; CHECK-DAG: NoAlias: i32* %b, i32** %x -; CHECK-DAG: NoAlias: i32* %a, i32* %b -; CHECK-DAG: NoAlias: i32* %c, i32** %x -; CHECK-DAG: NoAlias: i32* %a, i32* %c -; CHECK-DAG: NoAlias: i32* %b, i32* %c -; CHECK-DAG: NoAlias: i32* %a, i32* %d -; CHECK-DAG: MayAlias: i32* %b, i32* %d -; CHECK-DAG: MayAlias: i32* %c, i32* %d -define void @test_return_escape(i32** %x) { - %a = alloca i32, align 4 - %b = call i32* @return_escaped_callee() - %c = call i32* @return_escaped_callee() - load i32, i32* %a - load i32, i32* %b - load i32, i32* %c - %d = load i32*, i32** %x - load i32, i32* %d - - ret void -} diff --git a/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-ret-ref-arg-multilevel.ll b/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-ret-ref-arg-multilevel.ll deleted file mode 100644 --- a/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-ret-ref-arg-multilevel.ll +++ /dev/null @@ -1,54 +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 -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s - -declare noalias i8* @malloc(i64) - -define i32*** @return_ref_arg_multilevel_callee(i32* %arg1) { - %ptr = call noalias i8* @malloc(i64 8) - %ptr_cast = bitcast i8* %ptr to i32*** - %ptr2 = call noalias i8* @malloc(i64 8) - %ptr_cast2 = bitcast i8* %ptr2 to i32** - store i32* %arg1, i32** %ptr_cast2 - store i32** %ptr_cast2, i32*** %ptr_cast - ret i32*** %ptr_cast -} -; CHECK-LABEL: Function: test_return_ref_arg_multilevel -; CHECK-DAG: NoAlias: i32* %a, i32*** %b -; CHECK-DAG: NoAlias: i32*** %b, i32** %p -; CHECK-DAG: NoAlias: i32* %a, i32** %lb -; CHECK-DAG: NoAlias: i32** %lb, i32*** %pp -; CHECK-DAG: NoAlias: i32*** %b, i32** %lb -; CHECK-DAG: MayAlias: i32* %a, i32* %lb_deref -; CHECK-DAG: NoAlias: i32* %lb_deref, i32** %lpp -; CHECK-DAG: MayAlias: i32* %lb_deref, i32* %lpp_deref -; CHECK-DAG: NoAlias: i32** %lpp, i32* %lpp_deref -; CHECK-DAG: MayAlias: i32* %lb_deref, i32* %lp -; CHECK-DAG: NoAlias: i32* %lp, i32** %lpp -; CHECK-DAG: MayAlias: i32* %lp, i32* %lpp_deref - -; We could've proven the following facts if the analysis were inclusion-based: -; NoAlias: i32*** %b, i32*** %pp -; NoAlias: i32** %lb, i32** %p -define void @test_return_ref_arg_multilevel() { - %a = alloca i32, align 4 - %p = alloca i32*, align 8 - %pp = alloca i32**, align 8 - - load i32, i32* %a - store i32* %a, i32** %p - store i32** %p, i32*** %pp - %b = call i32*** @return_ref_arg_multilevel_callee(i32* %a) - - %lb = load i32**, i32*** %b - %lb_deref = load i32*, i32** %lb - %lpp = load i32**, i32*** %pp - %lpp_deref = load i32*, i32** %lpp - %lp = load i32*, i32** %p - load i32, i32* %lb_deref - load i32, i32* %lpp_deref - load i32, i32* %lp - - ret void -} diff --git a/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-ret-ref-arg.ll b/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-ret-ref-arg.ll deleted file mode 100644 --- a/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-ret-ref-arg.ll +++ /dev/null @@ -1,38 +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 -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s - -declare noalias i8* @malloc(i64) - -define i32** @return_ref_arg_callee(i32* %arg1) { - %ptr = call noalias i8* @malloc(i64 8) - %ptr_cast = bitcast i8* %ptr to i32** - store i32* %arg1, i32** %ptr_cast - ret i32** %ptr_cast -} -; CHECK-LABEL: Function: test_return_ref_arg -; CHECK: MayAlias: i32* %a, i32* %lb -; CHECK: NoAlias: i32* %lb, i32** %p -; CHECK: NoAlias: i32** %b, i32* %lb -; CHECK: NoAlias: i32* %lp, i32** %p -; CHECK: NoAlias: i32** %b, i32* %lp -; CHECK: MayAlias: i32* %lb, i32* %lp - -; We could've proven the following facts if the analysis were inclusion-based: -; NoAlias: i32** %b, i32** %p -define void @test_return_ref_arg() { - %a = alloca i32, align 4 - %p = alloca i32*, align 8 - - load i32, i32* %a - store i32* %a, i32** %p - %b = call i32** @return_ref_arg_callee(i32* %a) - - %lb = load i32*, i32** %b - %lp = load i32*, i32** %p - load i32, i32* %lb - load i32, i32* %lp - - ret void -} diff --git a/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-ret-unknown.ll b/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-ret-unknown.ll deleted file mode 100644 --- a/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-ret-unknown.ll +++ /dev/null @@ -1,43 +0,0 @@ -; This testcase ensures that CFL AA answers queries soundly when callee tries -; to return an unknown pointer - -; RUN: opt < %s -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s - -@g = external global i32 -define i32* @return_unknown_callee(i32* %arg1, i32* %arg2) { - ret i32* @g -} -; CHECK-LABEL: Function: test_return_unknown -; CHECK: NoAlias: i32* %a, i32* %b -; CHECK: MayAlias: i32* %c, i32* %x -; CHECK: NoAlias: i32* %a, i32* %c -; CHECK: NoAlias: i32* %b, i32* %c -define void @test_return_unknown(i32* %x) { - %a = alloca i32, align 4 - %b = alloca i32, align 4 - - load i32, i32* %x - load i32, i32* %a - load i32, i32* %b - %c = call i32* @return_unknown_callee(i32* %a, i32* %b) - load i32, i32* %c - - ret void -} - -@g2 = external global i32* -define i32** @return_unknown_callee2() { - ret i32** @g2 -} -; CHECK-LABEL: Function: test_return_unknown2 -; CHECK: MayAlias: i32** %a, i32* %x -; CHECK: MayAlias: i32* %b, i32* %x -; CHECK: MayAlias: i32** %a, i32* %b -define void @test_return_unknown2(i32* %x) { - load i32, i32* %x - %a = call i32** @return_unknown_callee2() - %b = load i32*, i32** %a - load i32, i32* %b - - ret void -} diff --git a/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-store-arg-multilevel.ll b/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-store-arg-multilevel.ll deleted file mode 100644 --- a/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-store-arg-multilevel.ll +++ /dev/null @@ -1,51 +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 -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s - -declare noalias i8* @malloc(i64) - -define void @store_arg_multilevel_callee(i32*** %arg1, i32* %arg2) { - %ptr = call noalias i8* @malloc(i64 8) - %ptr_cast = bitcast i8* %ptr to i32** - store i32* %arg2, i32** %ptr_cast - store i32** %ptr_cast, i32*** %arg1 - ret void -} -; CHECK-LABEL: Function: test_store_arg_multilevel -; CHECK: NoAlias: i32* %a, i32** %lpp -; CHECK: NoAlias: i32* %b, i32** %lpp -; CHECK: MayAlias: i32** %lpp, i32** %p -; CHECK: MayAlias: i32* %a, i32* %lpp_deref -; CHECK: MayAlias: i32* %b, i32* %lpp_deref -; CHECK: NoAlias: i32* %lpp_deref, i32** %p -; CHECK: NoAlias: i32* %lpp_deref, i32*** %pp -; CHECK: NoAlias: i32** %lpp, i32* %lpp_deref -; CHECK: MayAlias: i32* %a, i32* %lp -; CHECK: NoAlias: i32* %lp, i32*** %pp -; CHECK: NoAlias: i32* %lp, i32** %lpp -; CHECK: MayAlias: i32* %lp, i32* %lpp_deref - -; We could've proven the following facts if the analysis were inclusion-based: -; NoAlias: i32* %a, i32* %b -define void @test_store_arg_multilevel() { - %a = alloca i32, align 4 - %b = alloca i32, align 4 - %p = alloca i32*, align 8 - %pp = alloca i32**, align 8 - - load i32, i32* %a - load i32, i32* %b - store i32* %a, i32** %p - store i32** %p, i32*** %pp - call void @store_arg_multilevel_callee(i32*** %pp, i32* %b) - - %lpp = load i32**, i32*** %pp - %lpp_deref = load i32*, i32** %lpp - %lp = load i32*, i32** %p - load i32, i32* %lpp_deref - load i32, i32* %lp - - ret void -} - diff --git a/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-store-arg-unknown.ll b/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-store-arg-unknown.ll deleted file mode 100644 --- a/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-store-arg-unknown.ll +++ /dev/null @@ -1,35 +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 -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s - -@g = external global i32 - -define void @store_arg_unknown_callee(i32** %arg1) { - store i32* @g, i32** %arg1 - ret void -} -; CHECK-LABEL: Function: test_store_arg_unknown -; CHECK: NoAlias: i32** %p, i32* %x -; CHECK: NoAlias: i32* %a, i32** %p -; CHECK: NoAlias: i32* %b, i32** %p -; CHECK: MayAlias: i32* %lp, i32* %x -; CHECK: MayAlias: i32* %a, i32* %lp -; CHECK: NoAlias: i32* %b, i32* %lp -; CHECK: NoAlias: i32* %lp, i32** %p -define void @test_store_arg_unknown(i32* %x) { - %a = alloca i32, align 4 - %b = alloca i32, align 4 - %p = alloca i32*, align 8 - - load i32, i32* %x - load i32, i32* %a - load i32, i32* %b - store i32* %a, i32** %p - call void @store_arg_unknown_callee(i32** %p) - - %lp = load i32*, i32** %p - load i32, i32* %lp - - ret void -} diff --git a/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-store-arg.ll b/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-store-arg.ll deleted file mode 100644 --- a/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/interproc-store-arg.ll +++ /dev/null @@ -1,39 +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 -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s - -define void @store_arg_callee(i32** %arg1, i32* %arg2) { - store i32* %arg2, i32** %arg1 - ret void -} -; CHECK-LABEL: Function: test_store_arg -; CHECK: NoAlias: i32* %a, i32** %p -; CHECK: NoAlias: i32* %b, i32** %p -; CHECK: MayAlias: i32* %a, i32* %lp -; CHECK: MayAlias: i32* %b, i32* %lp -; CHECK: MayAlias: i32* %b, i32* %lq -; CHECK: MayAlias: i32* %lp, i32* %lq - -; We could've proven the following facts if the analysis were inclusion-based: -; NoAlias: i32* %a, i32* %b -; NoAlias: i32* %a, i32* %lq -define void @test_store_arg() { - %a = alloca i32, align 4 - %b = alloca i32, align 4 - %p = alloca i32*, align 8 - %q = alloca i32*, align 8 - - load i32, i32* %a - load i32, i32* %b - store i32* %a, i32** %p - store i32* %b, i32** %q - call void @store_arg_callee(i32** %p, i32* %b) - - %lp = load i32*, i32** %p - %lq = load i32*, i32** %q - load i32, i32* %lp - load i32, i32* %lq - - ret void -} diff --git a/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/malloc-and-free.ll b/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/malloc-and-free.ll deleted file mode 100644 --- a/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/malloc-and-free.ll +++ /dev/null @@ -1,35 +0,0 @@ -; This testcase ensures that CFL AA handles malloc and free in a sound and precise manner - -; RUN: opt < %s -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-no-aliases -disable-output 2>&1 | FileCheck %s - -declare noalias i8* @malloc(i64) -declare noalias i8* @calloc(i64, i64) -declare void @free(i8* nocapture) - -; CHECK: Function: test_malloc -; CHECK: NoAlias: i8* %p, i8* %q -define void @test_malloc(i8* %p) { - %q = call i8* @malloc(i64 4) - load i8, i8* %p - load i8, i8* %q - ret void -} - -; CHECK: Function: test_calloc -; CHECK: NoAlias: i8* %p, i8* %q -define void @test_calloc(i8* %p) { - %q = call i8* @calloc(i64 2, i64 4) - load i8, i8* %p - load i8, i8* %q - ret void -} - -; CHECK: Function: test_free -; CHECK: NoAlias: i8* %p, i8* %q -define void @test_free(i8* %p) { - %q = alloca i8, align 4 - call void @free(i8* %q) - load i8, i8* %p - load i8, i8* %q - ret void -} diff --git a/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/multilevel-combine.ll b/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/multilevel-combine.ll deleted file mode 100644 --- a/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/multilevel-combine.ll +++ /dev/null @@ -1,35 +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 -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s - -%T = type { i32, [10 x i8] } - -; CHECK: Function: test - -define void @test(i1 %C) { -; CHECK: 10 Total Alias Queries Performed -; CHECK: 4 no alias responses - %M = alloca %T*, align 8 ; NoAlias with %A, %B, %MS, %AP - %A = alloca %T, align 8 - %B = alloca %T, align 8 - - %MS = select i1 %C, %T* %B, %T* %A - - store %T* %MS, %T** %M - - %AP = load %T*, %T** %M ; PartialAlias with %A, %B - load %T, %T* %A - load %T, %T* %B - load %T, %T* %MS - load %T, %T* %AP - - ret void -} diff --git a/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/multilevel.ll b/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/multilevel.ll deleted file mode 100644 --- a/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/multilevel.ll +++ /dev/null @@ -1,34 +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 -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s - -%T = type { i32, [10 x i8] } - -; CHECK: Function: test - -define void @test() { -; CHECK: 15 Total Alias Queries Performed -; CHECK: 13 no alias responses - %M = alloca %T*, align 8 - %N = alloca %T*, align 8 - %A = alloca %T, align 8 - %B = alloca %T, align 8 - - store %T* %A, %T** %M - store %T* %B, %T** %N - - %AP = load %T*, %T** %M ; PartialAlias with %A - %BP = load %T*, %T** %N ; PartialAlias with %B - load %T, %T* %A - load %T, %T* %B - load %T, %T* %AP - load %T, %T* %BP - - ret void -} diff --git a/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/must-and-partial.ll b/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/must-and-partial.ll deleted file mode 100644 --- a/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/must-and-partial.ll +++ /dev/null @@ -1,57 +0,0 @@ -; RUN: opt < %s -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-all-alias-modref-info 2>&1 | FileCheck %s -; When merging MustAlias and PartialAlias, merge to PartialAlias -; instead of MayAlias. - - -target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64" - -; FIXME: This could be PartialAlias but CFLSteensAA can't currently prove it -; CHECK: MayAlias: i16* %bigbase0, i8* %phi -define i8 @test0(i1 %x) { -entry: - %base = alloca i8, align 4 - %baseplusone = getelementptr i8, i8* %base, i64 1 - br i1 %x, label %red, label %green -red: - br label %green -green: - %phi = phi i8* [ %baseplusone, %red ], [ %base, %entry ] - store i8 0, i8* %phi - - %bigbase0 = bitcast i8* %base to i16* - store i16 -1, i16* %bigbase0 - - %loaded = load i8, i8* %phi - ret i8 %loaded -} - -; FIXME: This could be PartialAlias but CFLSteensAA can't currently prove it -; CHECK: MayAlias: i16* %bigbase1, i8* %sel -define i8 @test1(i1 %x) { -entry: - %base = alloca i8, align 4 - %baseplusone = getelementptr i8, i8* %base, i64 1 - %sel = select i1 %x, i8* %baseplusone, i8* %base - store i8 0, i8* %sel - - %bigbase1 = bitcast i8* %base to i16* - store i16 -1, i16* %bigbase1 - - %loaded = load i8, i8* %sel - ret i8 %loaded -} - -; Incoming pointer arguments should not be MayAlias because we do not know their initial state -; even if they are nocapture -; CHECK: MayAlias: double* %A, double* %Index -define void @testr2(double* nocapture readonly %A, double* nocapture readonly %Index) { - %arrayidx22 = getelementptr inbounds double, double* %Index, i64 2 - %1 = load double, double* %arrayidx22 - %arrayidx25 = getelementptr inbounds double, double* %A, i64 2 - %2 = load double, double* %arrayidx25 - %3 = fneg double %1 - %mul26 = fmul double %3, %2 - load double, double* %A - load double, double* %Index - ret void -} diff --git a/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/opaque-call-alias.ll b/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/opaque-call-alias.ll deleted file mode 100644 --- a/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/opaque-call-alias.ll +++ /dev/null @@ -1,23 +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 -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s - -; CHECK: Function: test -; CHECK: NoAlias: i8* %Arg, i8* %Escapes -; CHECK: MayAlias: i8* %Arg, i8* %Retrieved -; CHECK: MayAlias: i8* %Escapes, i8* %Retrieved -define void @test(i8* %Arg) { - %Noalias = alloca i8 - %Escapes = alloca i8 - load i8, i8* %Arg - load i8, i8* %Escapes - call void @set_thepointer(i8* %Escapes) - %Retrieved = call i8* @get_thepointer() - load i8, i8* %Retrieved - ret void -} - -declare void @set_thepointer(i8* %P) -declare i8* @get_thepointer() diff --git a/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/phi-and-select.ll b/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/phi-and-select.ll deleted file mode 100644 --- a/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/phi-and-select.ll +++ /dev/null @@ -1,36 +0,0 @@ -; RUN: opt < %s -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s -; Derived from (a subset of) BasicAA/phi-and-select.ll - -; CHECK: Function: qux -; CHECK: NoAlias: double* %a, double* %b -; CHECK: ===== Alias Analysis Evaluator Report ===== - -; Two PHIs with disjoint sets of inputs. -define void @qux(i1 %m, double* noalias %x, double* noalias %y, - i1 %n, double* noalias %v, double* noalias %w) { -entry: - br i1 %m, label %true, label %false - -true: - br label %exit - -false: - br label %exit - -exit: - %a = phi double* [ %x, %true ], [ %y, %false ] - br i1 %n, label %ntrue, label %nfalse - -ntrue: - br label %nexit - -nfalse: - br label %nexit - -nexit: - %b = phi double* [ %v, %ntrue ], [ %w, %nfalse ] - store volatile double 0.0, double* %a - store volatile double 1.0, double* %b - ret void -} - diff --git a/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/pr27213.ll b/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/pr27213.ll deleted file mode 100644 --- a/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/pr27213.ll +++ /dev/null @@ -1,39 +0,0 @@ -; RUN: opt < %s -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s - -; CHECK-LABEL: Function: foo -; CHECK: MayAlias: i32* %A, i32* %B -define void @foo(i32* %A, i32* %B) { -entry: - store i32 0, i32* %A, align 4 - store i32 0, i32* %B, align 4 - ret void -} - -; CHECK-LABEL: Function: bar -; CHECK: MayAlias: i32* %A, i32* %B -; CHECK: MayAlias: i32* %A, i32* %arrayidx -; CHECK: MayAlias: i32* %B, i32* %arrayidx -define void @bar(i32* %A, i32* %B) { -entry: - store i32 0, i32* %A, align 4 - load i32, i32* %B - %arrayidx = getelementptr inbounds i32, i32* %B, i64 1 - store i32 0, i32* %arrayidx, align 4 - ret void -} - -@G = global i32 0 - -; CHECK-LABEL: Function: baz -; CHECK: MayAlias: i32* %A, i32* @G -define void @baz(i32* %A) { -entry: - store i32 0, i32* %A, align 4 - store i32 0, i32* @G, align 4 - ret void -} - -; CHECK-LABEL: Alias Analysis Evaluator Report -; CHECK: 5 Total Alias Queries Performed -; CHECK: 0 no alias responses -; CHECK: 5 may alias responses diff --git a/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/simple.ll b/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/simple.ll deleted file mode 100644 --- a/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/simple.ll +++ /dev/null @@ -1,18 +0,0 @@ -; This testcase consists of alias relations which should be completely -; resolvable by cfl-steens-aa (derived from BasicAA/2003-11-04-SimpleCases.ll). - -; RUN: opt < %s -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s - -%T = type { i32, [10 x i8] } - -; CHECK: Function: test -; CHECK-NOT: May: - -define void @test(%T* %P) { - %A = getelementptr %T, %T* %P, i64 0 - %B = getelementptr %T, %T* %P, i64 0, i32 0 - %C = getelementptr %T, %T* %P, i64 0, i32 1 - %D = getelementptr %T, %T* %P, i64 0, i32 1, i64 0 - %E = getelementptr %T, %T* %P, i64 0, i32 1, i64 5 - ret void -} diff --git a/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/stratified-attrs-indexing.ll b/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/stratified-attrs-indexing.ll deleted file mode 100644 --- a/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/stratified-attrs-indexing.ll +++ /dev/null @@ -1,35 +0,0 @@ -; This testcase ensures that CFLSteensAA doesn't try to access out of bounds indices -; when given functions with large amounts of arguments (specifically, more -; arguments than the StratifiedAttrs bitset can handle) -; -; Because the result on failure is effectively crashing the compiler, output -; checking is minimal. - -; RUN: opt < %s -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s - -; CHECK: Function: test -define void @test(i1 %cond, - i32* %arg1, i32* %arg2, i32* %arg3, i32* %arg4, i32* %arg5, - i32* %arg6, i32* %arg7, i32* %arg8, i32* %arg9, i32* %arg10, - i32* %arg11, i32* %arg12, i32* %arg13, i32* %arg14, i32* %arg15, - i32* %arg16, i32* %arg17, i32* %arg18, i32* %arg19, i32* %arg20, - i32* %arg21, i32* %arg22, i32* %arg23, i32* %arg24, i32* %arg25, - i32* %arg26, i32* %arg27, i32* %arg28, i32* %arg29, i32* %arg30, - i32* %arg31, i32* %arg32, i32* %arg33, i32* %arg34, i32* %arg35) { - - ; CHECK: 45 Total Alias Queries Performed - ; CHECK: 9 no alias responses (20.0%) - %a = alloca i32, align 4 - load i32, i32* %a - load i32, i32* %arg27 - load i32, i32* %arg28 - load i32, i32* %arg29 - load i32, i32* %arg30 - load i32, i32* %arg31 - load i32, i32* %arg32 - load i32, i32* %arg33 - load i32, i32* %arg34 - load i32, i32* %arg35 - - ret void -} diff --git a/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/va.ll b/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/va.ll deleted file mode 100644 --- a/llvm/test/Analysis/CFLAliasAnalysis/Steensgaard/va.ll +++ /dev/null @@ -1,37 +0,0 @@ -; RUN: opt < %s -aa-pipeline=cfl-steens-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s - -; CHECK-LABEL: Function: test1 -; CHECK-DAG: MayAlias: i32* %X, i32* %tmp -; CHECK-DAG: MayAlias: i8** %ap, i32* %tmp -; CHECK-DAG: NoAlias: i8** %ap, i8** %aq -; CHECK-DAG: MayAlias: i8** %aq, i32* %tmp - -define i32* @test1(i32* %X, ...) { - ; Initialize variable argument processing - %ap = alloca i8* - %ap2 = bitcast i8** %ap to i8* - call void @llvm.va_start(i8* %ap2) - - ; Read a single pointer argument - %tmp = va_arg i8** %ap, i32* - - ; Demonstrate usage of llvm.va_copy and llvm.va_end - %aq = alloca i8* - %aq2 = bitcast i8** %aq to i8* - call void @llvm.va_copy(i8* %aq2, i8* %ap2) - call void @llvm.va_end(i8* %aq2) - - ; Stop processing of arguments. - call void @llvm.va_end(i8* %ap2) - - load i32, i32* %X - load i8*, i8** %ap - load i8*, i8** %aq - load i32, i32* %tmp - ret i32* %tmp -} - -declare void @llvm.va_start(i8*) -declare void @llvm.va_copy(i8*, i8*) -declare void @llvm.va_end(i8*) -