diff options
| -rw-r--r-- | llvm/include/llvm/Analysis/CFLAliasAnalysis.h | 103 | ||||
| -rw-r--r-- | llvm/include/llvm/Analysis/Passes.h | 7 | ||||
| -rw-r--r-- | llvm/include/llvm/LinkAllPasses.h | 1 | ||||
| -rw-r--r-- | llvm/lib/Analysis/CFLAliasAnalysis.cpp | 210 | ||||
| -rw-r--r-- | llvm/lib/CodeGen/Passes.cpp | 1 | ||||
| -rw-r--r-- | llvm/lib/Transforms/IPO/PassManagerBuilder.cpp | 1 |
6 files changed, 184 insertions, 139 deletions
diff --git a/llvm/include/llvm/Analysis/CFLAliasAnalysis.h b/llvm/include/llvm/Analysis/CFLAliasAnalysis.h new file mode 100644 index 00000000000..4a151d5a965 --- /dev/null +++ b/llvm/include/llvm/Analysis/CFLAliasAnalysis.h @@ -0,0 +1,103 @@ +//===- CFLAliasAnalysis.h - CFL-Based Alias Analysis Interface ---*- C++ -*-==// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +/// \file +/// This is the interface for LLVM's primary stateless and local alias analysis. +/// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_CFLALIASANALYSIS_H +#define LLVM_ANALYSIS_CFLALIASANALYSIS_H + +#include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/None.h" +#include "llvm/ADT/Optional.h" +#include "llvm/IR/Function.h" +#include "llvm/IR/Module.h" +#include "llvm/Pass.h" +#include <forward_list> + +namespace llvm { + +class CFLAliasAnalysis : public ImmutablePass, public AliasAnalysis { + struct FunctionInfo; + struct FunctionHandle; + + /// \brief Cached mapping of Functions to their StratifiedSets. + /// If a function's sets are currently being built, it is marked + /// in the cache as an Optional without a value. This way, if we + /// have any kind of recursion, it is discernable from a function + /// that simply has empty sets. + DenseMap<Function *, Optional<FunctionInfo>> Cache; + std::forward_list<FunctionHandle> Handles; + +public: + static char ID; + + CFLAliasAnalysis(); + ~CFLAliasAnalysis() override; + + void getAnalysisUsage(AnalysisUsage &AU) const override; + + void *getAdjustedAnalysisPointer(const void *ID) override; + + /// \brief Inserts the given Function into the cache. + void scan(Function *Fn); + + void evict(Function *Fn); + + /// \brief Ensures that the given function is available in the cache. + /// Returns the appropriate entry from the cache. + const Optional<FunctionInfo> &ensureCached(Function *Fn); + + AliasResult query(const MemoryLocation &LocA, const MemoryLocation &LocB); + + AliasResult alias(const MemoryLocation &LocA, + const MemoryLocation &LocB) override { + if (LocA.Ptr == LocB.Ptr) { + if (LocA.Size == LocB.Size) { + return MustAlias; + } else { + return PartialAlias; + } + } + + // Comparisons between global variables and other constants should be + // handled by BasicAA. + // TODO: ConstantExpr handling -- CFLAA may report NoAlias when comparing + // a GlobalValue and ConstantExpr, but every query needs to have at least + // one Value tied to a Function, and neither GlobalValues nor ConstantExprs + // are. + if (isa<Constant>(LocA.Ptr) && isa<Constant>(LocB.Ptr)) { + return AliasAnalysis::alias(LocA, LocB); + } + + AliasResult QueryResult = query(LocA, LocB); + if (QueryResult == MayAlias) + return AliasAnalysis::alias(LocA, LocB); + + return QueryResult; + } + + bool doInitialization(Module &M) override; + +private: + FunctionInfo buildSetsFrom(Function *F); +}; + +//===--------------------------------------------------------------------===// +// +// createCFLAliasAnalysisPass - This pass implements a set-based approach to +// alias analysis. +// +ImmutablePass *createCFLAliasAnalysisPass(); + +} + +#endif diff --git a/llvm/include/llvm/Analysis/Passes.h b/llvm/include/llvm/Analysis/Passes.h index c85d751a810..c5d0290eaa8 100644 --- a/llvm/include/llvm/Analysis/Passes.h +++ b/llvm/include/llvm/Analysis/Passes.h @@ -46,13 +46,6 @@ namespace llvm { //===--------------------------------------------------------------------===// // - // createCFLAliasAnalysisPass - This pass implements a set-based approach to - // alias analysis. - // - ImmutablePass *createCFLAliasAnalysisPass(); - - //===--------------------------------------------------------------------===// - // // createScalarEvolutionAliasAnalysisPass - This pass implements a simple // alias analysis using ScalarEvolution queries. // diff --git a/llvm/include/llvm/LinkAllPasses.h b/llvm/include/llvm/LinkAllPasses.h index 4b58ee3ab28..ad173885f78 100644 --- a/llvm/include/llvm/LinkAllPasses.h +++ b/llvm/include/llvm/LinkAllPasses.h @@ -19,6 +19,7 @@ #include "llvm/Analysis/AliasSetTracker.h" #include "llvm/Analysis/AliasAnalysisCounter.h" #include "llvm/Analysis/BasicAliasAnalysis.h" +#include "llvm/Analysis/CFLAliasAnalysis.h" #include "llvm/Analysis/CallPrinter.h" #include "llvm/Analysis/DomPrinter.h" #include "llvm/Analysis/IntervalPartition.h" diff --git a/llvm/lib/Analysis/CFLAliasAnalysis.cpp b/llvm/lib/Analysis/CFLAliasAnalysis.cpp index e87adf14285..958ba95b3e6 100644 --- a/llvm/lib/Analysis/CFLAliasAnalysis.cpp +++ b/llvm/lib/Analysis/CFLAliasAnalysis.cpp @@ -27,13 +27,13 @@ // time. //===----------------------------------------------------------------------===// +#include "llvm/Analysis/CFLAliasAnalysis.h" #include "StratifiedSets.h" #include "llvm/ADT/BitVector.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/None.h" #include "llvm/ADT/Optional.h" #include "llvm/Analysis/AliasAnalysis.h" -#include "llvm/Analysis/Passes.h" #include "llvm/IR/Constants.h" #include "llvm/IR/Function.h" #include "llvm/IR/InstVisitor.h" @@ -47,7 +47,6 @@ #include "llvm/Support/raw_ostream.h" #include <algorithm> #include <cassert> -#include <forward_list> #include <memory> #include <tuple> @@ -55,6 +54,63 @@ using namespace llvm; #define DEBUG_TYPE "cfl-aa" +// -- Setting up/registering CFLAA pass -- // +char CFLAliasAnalysis::ID = 0; + +INITIALIZE_AG_PASS(CFLAliasAnalysis, AliasAnalysis, "cfl-aa", + "CFL-Based AA implementation", false, true, false) + +ImmutablePass *llvm::createCFLAliasAnalysisPass() { + return new CFLAliasAnalysis(); +} + +// \brief Information we have about a function and would like to keep around +struct CFLAliasAnalysis::FunctionInfo { + StratifiedSets<Value *> Sets; + // Lots of functions have < 4 returns. Adjust as necessary. + SmallVector<Value *, 4> ReturnedValues; + + FunctionInfo(StratifiedSets<Value *> &&S, SmallVector<Value *, 4> &&RV) + : Sets(std::move(S)), ReturnedValues(std::move(RV)) {} +}; + +struct CFLAliasAnalysis::FunctionHandle final : public CallbackVH { + FunctionHandle(Function *Fn, CFLAliasAnalysis *CFLAA) + : CallbackVH(Fn), CFLAA(CFLAA) { + assert(Fn != nullptr); + assert(CFLAA != nullptr); + } + + void deleted() override { removeSelfFromCache(); } + void allUsesReplacedWith(Value *) override { removeSelfFromCache(); } + +private: + CFLAliasAnalysis *CFLAA; + + void removeSelfFromCache() { + assert(CFLAA != nullptr); + auto *Val = getValPtr(); + CFLAA->evict(cast<Function>(Val)); + setValPtr(nullptr); + } +}; + +CFLAliasAnalysis::CFLAliasAnalysis() : ImmutablePass(ID) { + initializeCFLAliasAnalysisPass(*PassRegistry::getPassRegistry()); +} + +CFLAliasAnalysis::~CFLAliasAnalysis() {} + +void CFLAliasAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { + AliasAnalysis::getAnalysisUsage(AU); +} + +void *CFLAliasAnalysis::getAdjustedAnalysisPointer(const void *ID) { + if (ID == &AliasAnalysis::ID) + return (AliasAnalysis *)this; + return this; +} + // Try to go from a Value* to a Function*. Never returns nullptr. static Optional<Function *> parentFunctionOfValue(Value *); @@ -141,120 +197,6 @@ struct Edge { : From(From), To(To), Weight(W), AdditionalAttrs(A) {} }; -// \brief Information we have about a function and would like to keep around -struct FunctionInfo { - StratifiedSets<Value *> Sets; - // Lots of functions have < 4 returns. Adjust as necessary. - SmallVector<Value *, 4> ReturnedValues; - - FunctionInfo(StratifiedSets<Value *> &&S, SmallVector<Value *, 4> &&RV) - : Sets(std::move(S)), ReturnedValues(std::move(RV)) {} -}; - -struct CFLAliasAnalysis; - -struct FunctionHandle final : public CallbackVH { - FunctionHandle(Function *Fn, CFLAliasAnalysis *CFLAA) - : CallbackVH(Fn), CFLAA(CFLAA) { - assert(Fn != nullptr); - assert(CFLAA != nullptr); - } - - void deleted() override { removeSelfFromCache(); } - void allUsesReplacedWith(Value *) override { removeSelfFromCache(); } - -private: - CFLAliasAnalysis *CFLAA; - - void removeSelfFromCache(); -}; - -struct CFLAliasAnalysis : public ImmutablePass, public AliasAnalysis { -private: - /// \brief Cached mapping of Functions to their StratifiedSets. - /// If a function's sets are currently being built, it is marked - /// in the cache as an Optional without a value. This way, if we - /// have any kind of recursion, it is discernable from a function - /// that simply has empty sets. - DenseMap<Function *, Optional<FunctionInfo>> Cache; - std::forward_list<FunctionHandle> Handles; - -public: - static char ID; - - CFLAliasAnalysis() : ImmutablePass(ID) { - initializeCFLAliasAnalysisPass(*PassRegistry::getPassRegistry()); - } - - ~CFLAliasAnalysis() override {} - - void getAnalysisUsage(AnalysisUsage &AU) const override { - AliasAnalysis::getAnalysisUsage(AU); - } - - void *getAdjustedAnalysisPointer(const void *ID) override { - if (ID == &AliasAnalysis::ID) - return (AliasAnalysis *)this; - return this; - } - - /// \brief Inserts the given Function into the cache. - void scan(Function *Fn); - - void evict(Function *Fn) { Cache.erase(Fn); } - - /// \brief Ensures that the given function is available in the cache. - /// Returns the appropriate entry from the cache. - const Optional<FunctionInfo> &ensureCached(Function *Fn) { - auto Iter = Cache.find(Fn); - if (Iter == Cache.end()) { - scan(Fn); - Iter = Cache.find(Fn); - assert(Iter != Cache.end()); - assert(Iter->second.hasValue()); - } - return Iter->second; - } - - AliasResult query(const MemoryLocation &LocA, const MemoryLocation &LocB); - - AliasResult alias(const MemoryLocation &LocA, - const MemoryLocation &LocB) override { - if (LocA.Ptr == LocB.Ptr) { - if (LocA.Size == LocB.Size) { - return MustAlias; - } else { - return PartialAlias; - } - } - - // Comparisons between global variables and other constants should be - // handled by BasicAA. - // TODO: ConstantExpr handling -- CFLAA may report NoAlias when comparing - // a GlobalValue and ConstantExpr, but every query needs to have at least - // one Value tied to a Function, and neither GlobalValues nor ConstantExprs - // are. - if (isa<Constant>(LocA.Ptr) && isa<Constant>(LocB.Ptr)) { - return AliasAnalysis::alias(LocA, LocB); - } - - AliasResult QueryResult = query(LocA, LocB); - if (QueryResult == MayAlias) - return AliasAnalysis::alias(LocA, LocB); - - return QueryResult; - } - - bool doInitialization(Module &M) override; -}; - -void FunctionHandle::removeSelfFromCache() { - assert(CFLAA != nullptr); - auto *Val = getValPtr(); - CFLAA->evict(cast<Function>(Val)); - setValPtr(nullptr); -} - // \brief Gets the edges our graph should have, based on an Instruction* class GetEdgesVisitor : public InstVisitor<GetEdgesVisitor, void> { CFLAliasAnalysis &AA; @@ -725,16 +667,6 @@ typedef WeightedBidirectionalGraph<std::pair<EdgeType, StratifiedAttrs>> GraphT; typedef DenseMap<Value *, GraphT::Node> NodeMapT; } -// -- Setting up/registering CFLAA pass -- // -char CFLAliasAnalysis::ID = 0; - -INITIALIZE_AG_PASS(CFLAliasAnalysis, AliasAnalysis, "cfl-aa", - "CFL-Based AA implementation", false, true, false) - -ImmutablePass *llvm::createCFLAliasAnalysisPass() { - return new CFLAliasAnalysis(); -} - //===----------------------------------------------------------------------===// // Function declarations that require types defined in the namespace above //===----------------------------------------------------------------------===// @@ -784,9 +716,6 @@ static void addInstructionToGraph(CFLAliasAnalysis &, Instruction &, // Notes whether it would be pointless to add the given Value to our sets. static bool canSkipAddingToSets(Value *Val); -// Builds the graph + StratifiedSets for a function. -static FunctionInfo buildSetsFrom(CFLAliasAnalysis &, Function *); - static Optional<Function *> parentFunctionOfValue(Value *Val) { if (auto *Inst = dyn_cast<Instruction>(Val)) { auto *Bb = Inst->getParent(); @@ -1010,12 +939,13 @@ static bool canSkipAddingToSets(Value *Val) { return false; } -static FunctionInfo buildSetsFrom(CFLAliasAnalysis &Analysis, Function *Fn) { +// Builds the graph + StratifiedSets for a function. +CFLAliasAnalysis::FunctionInfo CFLAliasAnalysis::buildSetsFrom(Function *Fn) { NodeMapT Map; GraphT Graph; SmallVector<Value *, 4> ReturnedValues; - buildGraphFrom(Analysis, Fn, ReturnedValues, Map, Graph); + buildGraphFrom(*this, Fn, ReturnedValues, Map, Graph); DenseMap<GraphT::Node, Value *> NodeValueMap; NodeValueMap.resize(Map.size()); @@ -1102,11 +1032,27 @@ void CFLAliasAnalysis::scan(Function *Fn) { assert(InsertPair.second && "Trying to scan a function that has already been cached"); - FunctionInfo Info(buildSetsFrom(*this, Fn)); + FunctionInfo Info(buildSetsFrom(Fn)); Cache[Fn] = std::move(Info); Handles.push_front(FunctionHandle(Fn, this)); } +void CFLAliasAnalysis::evict(Function *Fn) { Cache.erase(Fn); } + +/// \brief Ensures that the given function is available in the cache. +/// Returns the appropriate entry from the cache. +const Optional<CFLAliasAnalysis::FunctionInfo> & +CFLAliasAnalysis::ensureCached(Function *Fn) { + auto Iter = Cache.find(Fn); + if (Iter == Cache.end()) { + scan(Fn); + Iter = Cache.find(Fn); + assert(Iter != Cache.end()); + assert(Iter->second.hasValue()); + } + return Iter->second; +} + AliasResult CFLAliasAnalysis::query(const MemoryLocation &LocA, const MemoryLocation &LocB) { auto *ValA = const_cast<Value *>(LocA.Ptr); diff --git a/llvm/lib/CodeGen/Passes.cpp b/llvm/lib/CodeGen/Passes.cpp index f36e5134b5a..0a705980729 100644 --- a/llvm/lib/CodeGen/Passes.cpp +++ b/llvm/lib/CodeGen/Passes.cpp @@ -14,6 +14,7 @@ #include "llvm/CodeGen/Passes.h" #include "llvm/Analysis/BasicAliasAnalysis.h" +#include "llvm/Analysis/CFLAliasAnalysis.h" #include "llvm/Analysis/Passes.h" #include "llvm/CodeGen/MachineFunctionPass.h" #include "llvm/CodeGen/RegAllocRegistry.h" diff --git a/llvm/lib/Transforms/IPO/PassManagerBuilder.cpp b/llvm/lib/Transforms/IPO/PassManagerBuilder.cpp index 9f58b49288a..0a1a56cc99c 100644 --- a/llvm/lib/Transforms/IPO/PassManagerBuilder.cpp +++ b/llvm/lib/Transforms/IPO/PassManagerBuilder.cpp @@ -23,6 +23,7 @@ #include "llvm/Support/CommandLine.h" #include "llvm/Support/ManagedStatic.h" #include "llvm/Analysis/BasicAliasAnalysis.h" +#include "llvm/Analysis/CFLAliasAnalysis.h" #include "llvm/Analysis/TargetLibraryInfo.h" #include "llvm/Target/TargetMachine.h" #include "llvm/Transforms/IPO.h" |
