From 0d68ddf6cecc75309dd6a9ee704acadec0b9e51e Mon Sep 17 00:00:00 2001 From: Chandler Carruth Date: Fri, 14 Aug 2015 03:48:20 +0000 Subject: [PATCH] [PM/AA] Extract the interface for GlobalsModRef into a header along with its creation function. This required shifting a bunch of method definitions to be out-of-line so that we could leave most of the implementation guts in the .cpp file. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@245021 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Analysis/GlobalsModRef.h | 139 ++++++++++++++ include/llvm/Analysis/Passes.h | 7 - include/llvm/LinkAllPasses.h | 1 + lib/Analysis/IPA/GlobalsModRef.cpp | 222 ++++++---------------- lib/Transforms/IPO/PassManagerBuilder.cpp | 1 + 5 files changed, 204 insertions(+), 166 deletions(-) create mode 100644 include/llvm/Analysis/GlobalsModRef.h diff --git a/include/llvm/Analysis/GlobalsModRef.h b/include/llvm/Analysis/GlobalsModRef.h new file mode 100644 index 00000000000..abd6309a7c3 --- /dev/null +++ b/include/llvm/Analysis/GlobalsModRef.h @@ -0,0 +1,139 @@ +//===- GlobalsModRef.h - Simple Mod/Ref AA for Globals ----------*- 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 a simple mod/ref and alias analysis over globlas. +/// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_GLOBALSMODREF_H +#define LLVM_ANALYSIS_GLOBALSMODREF_H + +#include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/Analysis/CallGraph.h" +#include "llvm/IR/Constants.h" +#include "llvm/IR/Function.h" +#include "llvm/IR/Module.h" +#include "llvm/IR/ValueHandle.h" +#include "llvm/Pass.h" +#include + +namespace llvm { + +/// GlobalsModRef - The actual analysis pass. +class GlobalsModRef : public ModulePass, public AliasAnalysis { + class FunctionInfo; + + /// The globals that do not have their addresses taken. + SmallPtrSet NonAddressTakenGlobals; + + /// IndirectGlobals - The memory pointed to by this global is known to be + /// 'owned' by the global. + SmallPtrSet IndirectGlobals; + + /// AllocsForIndirectGlobals - If an instruction allocates memory for an + /// indirect global, this map indicates which one. + DenseMap AllocsForIndirectGlobals; + + /// For each function, keep track of what globals are modified or read. + DenseMap FunctionInfos; + + /// Handle to clear this analysis on deletion of values. + struct DeletionCallbackHandle final : CallbackVH { + GlobalsModRef &GMR; + std::list::iterator I; + + DeletionCallbackHandle(GlobalsModRef &GMR, Value *V) + : CallbackVH(V), GMR(GMR) {} + + void deleted() override; + }; + + /// List of callbacks for globals being tracked by this analysis. Note that + /// these objects are quite large, but we only anticipate having one per + /// global tracked by this analysis. There are numerous optimizations we + /// could perform to the memory utilization here if this becomes a problem. + std::list Handles; + +public: + static char ID; + GlobalsModRef(); + + bool runOnModule(Module &M) override { + InitializeAliasAnalysis(this, &M.getDataLayout()); + + // Find non-addr taken globals. + AnalyzeGlobals(M); + + // Propagate on CG. + AnalyzeCallGraph(getAnalysis().getCallGraph(), M); + return false; + } + + void getAnalysisUsage(AnalysisUsage &AU) const override { + AliasAnalysis::getAnalysisUsage(AU); + AU.addRequired(); + AU.setPreservesAll(); // Does not transform code + } + + /// getAdjustedAnalysisPointer - This method is used when a pass implements + /// an analysis interface through multiple inheritance. If needed, it + /// should override this to adjust the this pointer as needed for the + /// specified pass info. + void *getAdjustedAnalysisPointer(AnalysisID PI) override { + if (PI == &AliasAnalysis::ID) + return (AliasAnalysis *)this; + return this; + } + + //------------------------------------------------ + // Implement the AliasAnalysis API + // + AliasResult alias(const MemoryLocation &LocA, + const MemoryLocation &LocB) override; + ModRefInfo getModRefInfo(ImmutableCallSite CS, + const MemoryLocation &Loc) override; + ModRefInfo getModRefInfo(ImmutableCallSite CS1, + ImmutableCallSite CS2) override { + return AliasAnalysis::getModRefInfo(CS1, CS2); + } + + /// getModRefBehavior - Return the behavior of the specified function if + /// called from the specified call site. The call site may be null in which + /// case the most generic behavior of this function should be returned. + FunctionModRefBehavior getModRefBehavior(const Function *F) override; + + /// getModRefBehavior - Return the behavior of the specified function if + /// called from the specified call site. The call site may be null in which + /// case the most generic behavior of this function should be returned. + FunctionModRefBehavior getModRefBehavior(ImmutableCallSite CS) override; + +private: + FunctionInfo *getFunctionInfo(const Function *F); + + void AnalyzeGlobals(Module &M); + void AnalyzeCallGraph(CallGraph &CG, Module &M); + bool AnalyzeUsesOfPointer(Value *V, + SmallPtrSetImpl *Readers = nullptr, + SmallPtrSetImpl *Writers = nullptr, + GlobalValue *OkayStoreDest = nullptr); + bool AnalyzeIndirectGlobalMemory(GlobalValue *GV); + + bool isNonEscapingGlobalNoAlias(const GlobalValue *GV, const Value *V); +}; + +//===--------------------------------------------------------------------===// +// +// createGlobalsModRefPass - This pass provides alias and mod/ref info for +// global values that do not have their addresses taken. +// +Pass *createGlobalsModRefPass(); + +} + +#endif diff --git a/include/llvm/Analysis/Passes.h b/include/llvm/Analysis/Passes.h index 672780f340b..ef757238b40 100644 --- a/include/llvm/Analysis/Passes.h +++ b/include/llvm/Analysis/Passes.h @@ -24,13 +24,6 @@ namespace llvm { class PassInfo; class LibCallInfo; - //===--------------------------------------------------------------------===// - // - // createGlobalsModRefPass - This pass provides alias and mod/ref info for - // global values that do not have their addresses taken. - // - Pass *createGlobalsModRefPass(); - //===--------------------------------------------------------------------===// // // createAAEvalPass - This pass implements a simple N^2 alias analysis diff --git a/include/llvm/LinkAllPasses.h b/include/llvm/LinkAllPasses.h index d37fd4c8fb4..fc9b63dd872 100644 --- a/include/llvm/LinkAllPasses.h +++ b/include/llvm/LinkAllPasses.h @@ -22,6 +22,7 @@ #include "llvm/Analysis/CFLAliasAnalysis.h" #include "llvm/Analysis/CallPrinter.h" #include "llvm/Analysis/DomPrinter.h" +#include "llvm/Analysis/GlobalsModRef.h" #include "llvm/Analysis/IntervalPartition.h" #include "llvm/Analysis/LibCallAliasAnalysis.h" #include "llvm/Analysis/Lint.h" diff --git a/lib/Analysis/IPA/GlobalsModRef.cpp b/lib/Analysis/IPA/GlobalsModRef.cpp index f429603da0b..2798888ce7d 100644 --- a/lib/Analysis/IPA/GlobalsModRef.cpp +++ b/lib/Analysis/IPA/GlobalsModRef.cpp @@ -14,15 +14,12 @@ // //===----------------------------------------------------------------------===// -#include "llvm/Analysis/Passes.h" +#include "llvm/Analysis/GlobalsModRef.h" #include "llvm/ADT/SCCIterator.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/Statistic.h" -#include "llvm/Analysis/AliasAnalysis.h" -#include "llvm/Analysis/CallGraph.h" #include "llvm/Analysis/MemoryBuiltins.h" #include "llvm/Analysis/ValueTracking.h" -#include "llvm/IR/Constants.h" #include "llvm/IR/DerivedTypes.h" #include "llvm/IR/InstIterator.h" #include "llvm/IR/Instructions.h" @@ -30,7 +27,6 @@ #include "llvm/IR/Module.h" #include "llvm/Pass.h" #include "llvm/Support/CommandLine.h" -#include using namespace llvm; #define DEBUG_TYPE "globalsmodref-aa" @@ -56,14 +52,13 @@ STATISTIC(NumIndirectGlobalVars, "Number of indirect global objects"); static cl::opt EnableUnsafeGlobalsModRefAliasResults( "enable-unsafe-globalsmodref-alias-results", cl::init(false), cl::Hidden); -namespace { /// The mod/ref information collected for a particular function. /// /// We collect information about mod/ref behavior of a function here, both in /// general and as pertains to specific globals. We only have this detailed /// information when we know *something* useful about the behavior. If we /// saturate to fully general mod/ref, we remove the info for the function. -class FunctionInfo { +class GlobalsModRef::FunctionInfo { typedef SmallDenseMap GlobalInfoMapType; /// Build a wrapper struct that has 8-byte alignment. All heap allocations @@ -196,122 +191,72 @@ private: PointerIntPair Info; }; -/// GlobalsModRef - The actual analysis pass. -class GlobalsModRef : public ModulePass, public AliasAnalysis { - /// The globals that do not have their addresses taken. - SmallPtrSet NonAddressTakenGlobals; - - /// IndirectGlobals - The memory pointed to by this global is known to be - /// 'owned' by the global. - SmallPtrSet IndirectGlobals; - - /// AllocsForIndirectGlobals - If an instruction allocates memory for an - /// indirect global, this map indicates which one. - DenseMap AllocsForIndirectGlobals; - - /// For each function, keep track of what globals are modified or read. - DenseMap FunctionInfos; - - /// Handle to clear this analysis on deletion of values. - struct DeletionCallbackHandle final : CallbackVH { - GlobalsModRef &GMR; - std::list::iterator I; - - DeletionCallbackHandle(GlobalsModRef &GMR, Value *V) - : CallbackVH(V), GMR(GMR) {} - - void deleted() override { - Value *V = getValPtr(); - if (auto *F = dyn_cast(V)) - GMR.FunctionInfos.erase(F); - - if (GlobalValue *GV = dyn_cast(V)) { - if (GMR.NonAddressTakenGlobals.erase(GV)) { - // This global might be an indirect global. If so, remove it and - // remove any AllocRelatedValues for it. - if (GMR.IndirectGlobals.erase(GV)) { - // Remove any entries in AllocsForIndirectGlobals for this global. - for (auto I = GMR.AllocsForIndirectGlobals.begin(), - E = GMR.AllocsForIndirectGlobals.end(); - I != E; ++I) - if (I->second == GV) - GMR.AllocsForIndirectGlobals.erase(I); - } - - // Scan the function info we have collected and remove this global - // from all of them. - for (auto &FIPair : GMR.FunctionInfos) - FIPair.second.eraseModRefInfoForGlobal(*GV); - } +void GlobalsModRef::DeletionCallbackHandle::deleted() { + Value *V = getValPtr(); + if (auto *F = dyn_cast(V)) + GMR.FunctionInfos.erase(F); + + if (GlobalValue *GV = dyn_cast(V)) { + if (GMR.NonAddressTakenGlobals.erase(GV)) { + // This global might be an indirect global. If so, remove it and + // remove any AllocRelatedValues for it. + if (GMR.IndirectGlobals.erase(GV)) { + // Remove any entries in AllocsForIndirectGlobals for this global. + for (auto I = GMR.AllocsForIndirectGlobals.begin(), + E = GMR.AllocsForIndirectGlobals.end(); + I != E; ++I) + if (I->second == GV) + GMR.AllocsForIndirectGlobals.erase(I); } - // If this is an allocation related to an indirect global, remove it. - GMR.AllocsForIndirectGlobals.erase(V); - - // And clear out the handle. - setValPtr(nullptr); - GMR.Handles.erase(I); - // This object is now destroyed! + // Scan the function info we have collected and remove this global + // from all of them. + for (auto &FIPair : GMR.FunctionInfos) + FIPair.second.eraseModRefInfoForGlobal(*GV); } - }; + } - /// List of callbacks for globals being tracked by this analysis. Note that - /// these objects are quite large, but we only anticipate having one per - /// global tracked by this analysis. There are numerous optimizations we - /// could perform to the memory utilization here if this becomes a problem. - std::list Handles; + // If this is an allocation related to an indirect global, remove it. + GMR.AllocsForIndirectGlobals.erase(V); -public: - static char ID; - GlobalsModRef() : ModulePass(ID) { - initializeGlobalsModRefPass(*PassRegistry::getPassRegistry()); - } + // And clear out the handle. + setValPtr(nullptr); + GMR.Handles.erase(I); + // This object is now destroyed! +} - bool runOnModule(Module &M) override { - InitializeAliasAnalysis(this, &M.getDataLayout()); +char GlobalsModRef::ID = 0; +INITIALIZE_AG_PASS_BEGIN(GlobalsModRef, AliasAnalysis, "globalsmodref-aa", + "Simple mod/ref analysis for globals", false, true, + false) +INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass) +INITIALIZE_AG_PASS_END(GlobalsModRef, AliasAnalysis, "globalsmodref-aa", + "Simple mod/ref analysis for globals", false, true, + false) - // Find non-addr taken globals. - AnalyzeGlobals(M); +Pass *llvm::createGlobalsModRefPass() { return new GlobalsModRef(); } - // Propagate on CG. - AnalyzeCallGraph(getAnalysis().getCallGraph(), M); - return false; - } +GlobalsModRef::GlobalsModRef() : ModulePass(ID) { + initializeGlobalsModRefPass(*PassRegistry::getPassRegistry()); +} - void getAnalysisUsage(AnalysisUsage &AU) const override { - AliasAnalysis::getAnalysisUsage(AU); - AU.addRequired(); - AU.setPreservesAll(); // Does not transform code - } +FunctionModRefBehavior GlobalsModRef::getModRefBehavior(const Function *F) { + FunctionModRefBehavior Min = FMRB_UnknownModRefBehavior; - /// getAdjustedAnalysisPointer - This method is used when a pass implements - /// an analysis interface through multiple inheritance. If needed, it - /// should override this to adjust the this pointer as needed for the - /// specified pass info. - void *getAdjustedAnalysisPointer(AnalysisID PI) override { - if (PI == &AliasAnalysis::ID) - return (AliasAnalysis *)this; - return this; + if (FunctionInfo *FI = getFunctionInfo(F)) { + if (FI->getModRefInfo() == MRI_NoModRef) + Min = FMRB_DoesNotAccessMemory; + else if ((FI->getModRefInfo() & MRI_Mod) == 0) + Min = FMRB_OnlyReadsMemory; } - //------------------------------------------------ - // Implement the AliasAnalysis API - // - AliasResult alias(const MemoryLocation &LocA, - const MemoryLocation &LocB) override; - ModRefInfo getModRefInfo(ImmutableCallSite CS, - const MemoryLocation &Loc) override; - ModRefInfo getModRefInfo(ImmutableCallSite CS1, - ImmutableCallSite CS2) override { - return AliasAnalysis::getModRefInfo(CS1, CS2); - } + return FunctionModRefBehavior(AliasAnalysis::getModRefBehavior(F) & Min); +} - /// getModRefBehavior - Return the behavior of the specified function if - /// called from the specified call site. The call site may be null in which - /// case the most generic behavior of this function should be returned. - FunctionModRefBehavior getModRefBehavior(const Function *F) override { - FunctionModRefBehavior Min = FMRB_UnknownModRefBehavior; +FunctionModRefBehavior GlobalsModRef::getModRefBehavior(ImmutableCallSite CS) { + FunctionModRefBehavior Min = FMRB_UnknownModRefBehavior; + if (const Function *F = CS.getCalledFunction()) if (FunctionInfo *FI = getFunctionInfo(F)) { if (FI->getModRefInfo() == MRI_NoModRef) Min = FMRB_DoesNotAccessMemory; @@ -319,58 +264,17 @@ public: Min = FMRB_OnlyReadsMemory; } - return FunctionModRefBehavior(AliasAnalysis::getModRefBehavior(F) & Min); - } - - /// getModRefBehavior - Return the behavior of the specified function if - /// called from the specified call site. The call site may be null in which - /// case the most generic behavior of this function should be returned. - FunctionModRefBehavior getModRefBehavior(ImmutableCallSite CS) override { - FunctionModRefBehavior Min = FMRB_UnknownModRefBehavior; - - if (const Function *F = CS.getCalledFunction()) - if (FunctionInfo *FI = getFunctionInfo(F)) { - if (FI->getModRefInfo() == MRI_NoModRef) - Min = FMRB_DoesNotAccessMemory; - else if ((FI->getModRefInfo() & MRI_Mod) == 0) - Min = FMRB_OnlyReadsMemory; - } - - return FunctionModRefBehavior(AliasAnalysis::getModRefBehavior(CS) & Min); - } - -private: - /// Returns the function info for the function, or null if we don't have - /// anything useful to say about it. - FunctionInfo *getFunctionInfo(const Function *F) { - auto I = FunctionInfos.find(F); - if (I != FunctionInfos.end()) - return &I->second; - return nullptr; - } - - void AnalyzeGlobals(Module &M); - void AnalyzeCallGraph(CallGraph &CG, Module &M); - bool AnalyzeUsesOfPointer(Value *V, - SmallPtrSetImpl *Readers = nullptr, - SmallPtrSetImpl *Writers = nullptr, - GlobalValue *OkayStoreDest = nullptr); - bool AnalyzeIndirectGlobalMemory(GlobalValue *GV); - - bool isNonEscapingGlobalNoAlias(const GlobalValue *GV, const Value *V); -}; + return FunctionModRefBehavior(AliasAnalysis::getModRefBehavior(CS) & Min); } -char GlobalsModRef::ID = 0; -INITIALIZE_AG_PASS_BEGIN(GlobalsModRef, AliasAnalysis, "globalsmodref-aa", - "Simple mod/ref analysis for globals", false, true, - false) -INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass) -INITIALIZE_AG_PASS_END(GlobalsModRef, AliasAnalysis, "globalsmodref-aa", - "Simple mod/ref analysis for globals", false, true, - false) - -Pass *llvm::createGlobalsModRefPass() { return new GlobalsModRef(); } +/// Returns the function info for the function, or null if we don't have +/// anything useful to say about it. +GlobalsModRef::FunctionInfo *GlobalsModRef::getFunctionInfo(const Function *F) { + auto I = FunctionInfos.find(F); + if (I != FunctionInfos.end()) + return &I->second; + return nullptr; +} /// AnalyzeGlobals - Scan through the users of all of the internal /// GlobalValue's in the program. If none of them have their "address taken" diff --git a/lib/Transforms/IPO/PassManagerBuilder.cpp b/lib/Transforms/IPO/PassManagerBuilder.cpp index 4ef55915aa3..edf3baf73a8 100644 --- a/lib/Transforms/IPO/PassManagerBuilder.cpp +++ b/lib/Transforms/IPO/PassManagerBuilder.cpp @@ -24,6 +24,7 @@ #include "llvm/Support/ManagedStatic.h" #include "llvm/Analysis/BasicAliasAnalysis.h" #include "llvm/Analysis/CFLAliasAnalysis.h" +#include "llvm/Analysis/GlobalsModRef.h" #include "llvm/Analysis/ScopedNoAliasAA.h" #include "llvm/Analysis/TargetLibraryInfo.h" #include "llvm/Analysis/TypeBasedAliasAnalysis.h" -- 2.34.1