X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FIPA%2FGlobalsModRef.cpp;h=ae4eafbc77d3feb236690bd69e362007dc047032;hb=f31b1ec106799f9461d8ed21a2e67da3d9ac798b;hp=17fce9d62adcb41689f6c5cc7972fa835e355768;hpb=c758209153ca0f6da6737f25ada269c573fba456;p=oota-llvm.git diff --git a/lib/Analysis/IPA/GlobalsModRef.cpp b/lib/Analysis/IPA/GlobalsModRef.cpp index 17fce9d62ad..ae4eafbc77d 100644 --- a/lib/Analysis/IPA/GlobalsModRef.cpp +++ b/lib/Analysis/IPA/GlobalsModRef.cpp @@ -14,23 +14,26 @@ // //===----------------------------------------------------------------------===// -#define DEBUG_TYPE "globalsmodref-aa" #include "llvm/Analysis/Passes.h" -#include "llvm/Module.h" -#include "llvm/Pass.h" -#include "llvm/Instructions.h" -#include "llvm/Constants.h" -#include "llvm/DerivedTypes.h" +#include "llvm/ADT/SCCIterator.h" +#include "llvm/ADT/Statistic.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/CallGraph.h" -#include "llvm/Support/Compiler.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" +#include "llvm/IR/IntrinsicInst.h" +#include "llvm/IR/Module.h" +#include "llvm/Pass.h" #include "llvm/Support/CommandLine.h" -#include "llvm/Support/InstIterator.h" -#include "llvm/ADT/Statistic.h" -#include "llvm/ADT/SCCIterator.h" #include using namespace llvm; +#define DEBUG_TYPE "globalsmodref-aa" + STATISTIC(NumNonAddrTakenGlobalVars, "Number of global vars without address taken"); STATISTIC(NumNonAddrTakenFunctions,"Number of functions without address taken"); @@ -39,182 +42,203 @@ STATISTIC(NumReadMemFunctions, "Number of functions that only read memory"); STATISTIC(NumIndirectGlobalVars, "Number of indirect global objects"); namespace { - /// FunctionRecord - One instance of this structure is stored for every - /// function in the program. Later, the entries for these functions are - /// removed if the function is found to call an external function (in which - /// case we know nothing about it. - struct VISIBILITY_HIDDEN FunctionRecord { - /// GlobalInfo - Maintain mod/ref info for all of the globals without - /// addresses taken that are read or written (transitively) by this - /// function. - std::map GlobalInfo; - - unsigned getInfoForGlobal(GlobalValue *GV) const { - std::map::const_iterator I = GlobalInfo.find(GV); - if (I != GlobalInfo.end()) - return I->second; - return 0; - } +/// FunctionRecord - One instance of this structure is stored for every +/// function in the program. Later, the entries for these functions are +/// removed if the function is found to call an external function (in which +/// case we know nothing about it. +struct FunctionRecord { + /// GlobalInfo - Maintain mod/ref info for all of the globals without + /// addresses taken that are read or written (transitively) by this + /// function. + std::map GlobalInfo; + + /// MayReadAnyGlobal - May read global variables, but it is not known which. + bool MayReadAnyGlobal; + + unsigned getInfoForGlobal(const GlobalValue *GV) const { + unsigned Effect = MayReadAnyGlobal ? AliasAnalysis::Ref : 0; + std::map::const_iterator I = + GlobalInfo.find(GV); + if (I != GlobalInfo.end()) + Effect |= I->second; + return Effect; + } - /// FunctionEffect - Capture whether or not this function reads or writes to - /// ANY memory. If not, we can do a lot of aggressive analysis on it. - unsigned FunctionEffect; - - FunctionRecord() : FunctionEffect(0) {} - }; - - /// GlobalsModRef - The actual analysis pass. - class VISIBILITY_HIDDEN GlobalsModRef - : public ModulePass, public AliasAnalysis { - /// NonAddressTakenGlobals - The globals that do not have their addresses - /// taken. - std::set NonAddressTakenGlobals; - - /// IndirectGlobals - The memory pointed to by this global is known to be - /// 'owned' by the global. - std::set IndirectGlobals; - - /// AllocsForIndirectGlobals - If an instruction allocates memory for an - /// indirect global, this map indicates which one. - std::map AllocsForIndirectGlobals; - - /// FunctionInfo - For each function, keep track of what globals are - /// modified or read. - std::map FunctionInfo; - - public: - static char ID; - GlobalsModRef() : ModulePass((intptr_t)&ID) {} - - bool runOnModule(Module &M) { - InitializeAliasAnalysis(this); // set up super class - AnalyzeGlobals(M); // find non-addr taken globals - AnalyzeCallGraph(getAnalysis(), M); // Propagate on CG - return false; - } + /// FunctionEffect - Capture whether or not this function reads or writes to + /// ANY memory. If not, we can do a lot of aggressive analysis on it. + unsigned FunctionEffect; - virtual void getAnalysisUsage(AnalysisUsage &AU) const { - AliasAnalysis::getAnalysisUsage(AU); - AU.addRequired(); - AU.setPreservesAll(); // Does not transform code - } + FunctionRecord() : MayReadAnyGlobal(false), FunctionEffect(0) {} +}; + +/// GlobalsModRef - The actual analysis pass. +class GlobalsModRef : public ModulePass, public AliasAnalysis { + /// NonAddressTakenGlobals - The globals that do not have their addresses + /// taken. + std::set NonAddressTakenGlobals; + + /// IndirectGlobals - The memory pointed to by this global is known to be + /// 'owned' by the global. + std::set IndirectGlobals; + + /// AllocsForIndirectGlobals - If an instruction allocates memory for an + /// indirect global, this map indicates which one. + std::map AllocsForIndirectGlobals; + + /// FunctionInfo - For each function, keep track of what globals are + /// modified or read. + std::map FunctionInfo; + +public: + static char ID; + GlobalsModRef() : ModulePass(ID) { + initializeGlobalsModRefPass(*PassRegistry::getPassRegistry()); + } + + 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; + } - //------------------------------------------------ - // Implement the AliasAnalysis API - // - AliasResult alias(const Value *V1, unsigned V1Size, - const Value *V2, unsigned V2Size); - ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size); - ModRefResult getModRefInfo(CallSite CS1, CallSite CS2) { - return AliasAnalysis::getModRefInfo(CS1,CS2); + void getAnalysisUsage(AnalysisUsage &AU) const override { + AliasAnalysis::getAnalysisUsage(AU); + AU.addRequired(); + AU.setPreservesAll(); // Does not transform code + } + + //------------------------------------------------ + // Implement the AliasAnalysis API + // + AliasResult alias(const MemoryLocation &LocA, + const MemoryLocation &LocB) override; + ModRefResult getModRefInfo(ImmutableCallSite CS, + const MemoryLocation &Loc) override; + ModRefResult 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. + ModRefBehavior getModRefBehavior(const Function *F) override { + ModRefBehavior Min = UnknownModRefBehavior; + + if (FunctionRecord *FR = getFunctionInfo(F)) { + if (FR->FunctionEffect == 0) + Min = DoesNotAccessMemory; + else if ((FR->FunctionEffect & Mod) == 0) + Min = OnlyReadsMemory; } - bool hasNoModRefInfoForCalls() const { return false; } - /// 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. - virtual ModRefBehavior getModRefBehavior(Function *F, CallSite CS, - std::vector *Info) { + return ModRefBehavior(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. + ModRefBehavior getModRefBehavior(ImmutableCallSite CS) override { + ModRefBehavior Min = UnknownModRefBehavior; + + if (const Function *F = CS.getCalledFunction()) if (FunctionRecord *FR = getFunctionInfo(F)) { if (FR->FunctionEffect == 0) - return DoesNotAccessMemory; + Min = DoesNotAccessMemory; else if ((FR->FunctionEffect & Mod) == 0) - return OnlyReadsMemory; + Min = OnlyReadsMemory; } - return AliasAnalysis::getModRefBehavior(F, CS, Info); - } - - virtual void deleteValue(Value *V); - virtual void copyValue(Value *From, Value *To); - - private: - /// getFunctionInfo - Return the function info for the function, or null if - /// the function calls an external function (in which case we don't have - /// anything useful to say about it). - FunctionRecord *getFunctionInfo(Function *F) { - std::map::iterator I = FunctionInfo.find(F); - if (I != FunctionInfo.end()) - return &I->second; - return 0; - } - void AnalyzeGlobals(Module &M); - void AnalyzeCallGraph(CallGraph &CG, Module &M); - void AnalyzeSCC(std::vector &SCC); - bool AnalyzeUsesOfPointer(Value *V, std::vector &Readers, - std::vector &Writers, - GlobalValue *OkayStoreDest = 0); - bool AnalyzeIndirectGlobalMemory(GlobalValue *GV); - }; - - char GlobalsModRef::ID = 0; - RegisterPass X("globalsmodref-aa", - "Simple mod/ref analysis for globals", true, - true); - RegisterAnalysisGroup Y(X); -} + return ModRefBehavior(AliasAnalysis::getModRefBehavior(CS) & Min); + } -Pass *llvm::createGlobalsModRefPass() { return new GlobalsModRef(); } + void deleteValue(Value *V) override; + void addEscapingUse(Use &U) override; + + /// 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; + } -/// getUnderlyingObject - This traverses the use chain to figure out what object -/// the specified value points to. If the value points to, or is derived from, -/// a global object, return it. -static Value *getUnderlyingObject(Value *V) { - if (!isa(V->getType())) return V; - - // If we are at some type of object... return it. - if (GlobalValue *GV = dyn_cast(V)) return GV; - - // Traverse through different addressing mechanisms. - if (Instruction *I = dyn_cast(V)) { - if (isa(I) || isa(I)) - return getUnderlyingObject(I->getOperand(0)); - } else if (ConstantExpr *CE = dyn_cast(V)) { - if (CE->getOpcode() == Instruction::BitCast || - CE->getOpcode() == Instruction::GetElementPtr) - return getUnderlyingObject(CE->getOperand(0)); +private: + /// getFunctionInfo - Return the function info for the function, or null if + /// we don't have anything useful to say about it. + FunctionRecord *getFunctionInfo(const Function *F) { + std::map::iterator I = + FunctionInfo.find(F); + if (I != FunctionInfo.end()) + return &I->second; + return nullptr; } - - // Othewise, we don't know what this is, return it as the base pointer. - return V; + + void AnalyzeGlobals(Module &M); + void AnalyzeCallGraph(CallGraph &CG, Module &M); + bool AnalyzeUsesOfPointer(Value *V, std::vector &Readers, + std::vector &Writers, + GlobalValue *OkayStoreDest = nullptr); + bool AnalyzeIndirectGlobalMemory(GlobalValue *GV); +}; } +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(); } + /// AnalyzeGlobals - Scan through the users of all of the internal -/// GlobalValue's in the program. If none of them have their "Address taken" +/// GlobalValue's in the program. If none of them have their "address taken" /// (really, their address passed to something nontrivial), record this fact, /// and record the functions that they are used directly in. void GlobalsModRef::AnalyzeGlobals(Module &M) { - std::vector Readers, Writers; - for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) - if (I->hasInternalLinkage()) { - if (!AnalyzeUsesOfPointer(I, Readers, Writers)) { + std::vector Readers, Writers; + for (Function &F : M) + if (F.hasLocalLinkage()) { + if (!AnalyzeUsesOfPointer(&F, Readers, Writers)) { // Remember that we are tracking this global. - NonAddressTakenGlobals.insert(I); + NonAddressTakenGlobals.insert(&F); ++NumNonAddrTakenFunctions; } - Readers.clear(); Writers.clear(); + Readers.clear(); + Writers.clear(); } - for (Module::global_iterator I = M.global_begin(), E = M.global_end(); - I != E; ++I) - if (I->hasInternalLinkage()) { - if (!AnalyzeUsesOfPointer(I, Readers, Writers)) { + for (GlobalVariable &GV : M.globals()) + if (GV.hasLocalLinkage()) { + if (!AnalyzeUsesOfPointer(&GV, Readers, Writers)) { // Remember that we are tracking this global, and the mod/ref fns - NonAddressTakenGlobals.insert(I); - for (unsigned i = 0, e = Readers.size(); i != e; ++i) - FunctionInfo[Readers[i]].GlobalInfo[I] |= Ref; + NonAddressTakenGlobals.insert(&GV); - if (!I->isConstant()) // No need to keep track of writers to constants - for (unsigned i = 0, e = Writers.size(); i != e; ++i) - FunctionInfo[Writers[i]].GlobalInfo[I] |= Mod; + for (Function *Reader : Readers) + FunctionInfo[Reader].GlobalInfo[&GV] |= Ref; + + if (!GV.isConstant()) // No need to keep track of writers to constants + for (Function *Writer : Writers) + FunctionInfo[Writer].GlobalInfo[&GV] |= Mod; ++NumNonAddrTakenGlobalVars; - + // If this global holds a pointer type, see if it is an indirect global. - if (isa(I->getType()->getElementType()) && - AnalyzeIndirectGlobalMemory(I)) + if (GV.getType()->getElementType()->isPointerTy() && + AnalyzeIndirectGlobalMemory(&GV)) ++NumIndirectGlobalVars; } - Readers.clear(); Writers.clear(); + Readers.clear(); + Writers.clear(); } } @@ -225,48 +249,46 @@ void GlobalsModRef::AnalyzeGlobals(Module &M) { /// /// If OkayStoreDest is non-null, stores into this global are allowed. bool GlobalsModRef::AnalyzeUsesOfPointer(Value *V, - std::vector &Readers, - std::vector &Writers, + std::vector &Readers, + std::vector &Writers, GlobalValue *OkayStoreDest) { - if (!isa(V->getType())) return true; + if (!V->getType()->isPointerTy()) + return true; - for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E; ++UI) - if (LoadInst *LI = dyn_cast(*UI)) { + for (Use &U : V->uses()) { + User *I = U.getUser(); + if (LoadInst *LI = dyn_cast(I)) { Readers.push_back(LI->getParent()->getParent()); - } else if (StoreInst *SI = dyn_cast(*UI)) { + } else if (StoreInst *SI = dyn_cast(I)) { if (V == SI->getOperand(1)) { Writers.push_back(SI->getParent()->getParent()); } else if (SI->getOperand(1) != OkayStoreDest) { - return true; // Storing the pointer + return true; // Storing the pointer } - } else if (GetElementPtrInst *GEP = dyn_cast(*UI)) { - if (AnalyzeUsesOfPointer(GEP, Readers, Writers)) return true; - } else if (CallInst *CI = dyn_cast(*UI)) { - // Make sure that this is just the function being called, not that it is - // passing into the function. - for (unsigned i = 1, e = CI->getNumOperands(); i != e; ++i) - if (CI->getOperand(i) == V) return true; - } else if (InvokeInst *II = dyn_cast(*UI)) { + } else if (Operator::getOpcode(I) == Instruction::GetElementPtr) { + if (AnalyzeUsesOfPointer(I, Readers, Writers)) + return true; + } else if (Operator::getOpcode(I) == Instruction::BitCast) { + if (AnalyzeUsesOfPointer(I, Readers, Writers, OkayStoreDest)) + return true; + } else if (auto CS = CallSite(I)) { // Make sure that this is just the function being called, not that it is // passing into the function. - for (unsigned i = 3, e = II->getNumOperands(); i != e; ++i) - if (II->getOperand(i) == V) return true; - } else if (ConstantExpr *CE = dyn_cast(*UI)) { - if (CE->getOpcode() == Instruction::GetElementPtr || - CE->getOpcode() == Instruction::BitCast) { - if (AnalyzeUsesOfPointer(CE, Readers, Writers)) - return true; - } else { - return true; + if (!CS.isCallee(&U)) { + // Detect calls to free. + if (isFreeCall(I, TLI)) + Writers.push_back(CS->getParent()->getParent()); + else + return true; // Argument of an unknown call. } - } else if (ICmpInst *ICI = dyn_cast(*UI)) { + } else if (ICmpInst *ICI = dyn_cast(I)) { if (!isa(ICI->getOperand(1))) - return true; // Allow comparison against null. - } else if (FreeInst *F = dyn_cast(*UI)) { - Writers.push_back(F->getParent()->getParent()); + return true; // Allow comparison against null. } else { return true; } + } + return false; } @@ -280,45 +302,40 @@ bool GlobalsModRef::AnalyzeUsesOfPointer(Value *V, bool GlobalsModRef::AnalyzeIndirectGlobalMemory(GlobalValue *GV) { // Keep track of values related to the allocation of the memory, f.e. the // value produced by the malloc call and any casts. - std::vector AllocRelatedValues; - + std::vector AllocRelatedValues; + // Walk the user list of the global. If we find anything other than a direct // load or store, bail out. - for (Value::use_iterator I = GV->use_begin(), E = GV->use_end(); I != E; ++I){ - if (LoadInst *LI = dyn_cast(*I)) { + for (User *U : GV->users()) { + if (LoadInst *LI = dyn_cast(U)) { // The pointer loaded from the global can only be used in simple ways: // we allow addressing of it and loading storing to it. We do *not* allow // storing the loaded pointer somewhere else or passing to a function. - std::vector ReadersWriters; + std::vector ReadersWriters; if (AnalyzeUsesOfPointer(LI, ReadersWriters, ReadersWriters)) - return false; // Loaded pointer escapes. + return false; // Loaded pointer escapes. // TODO: Could try some IP mod/ref of the loaded pointer. - } else if (StoreInst *SI = dyn_cast(*I)) { + } else if (StoreInst *SI = dyn_cast(U)) { // Storing the global itself. - if (SI->getOperand(0) == GV) return false; - + if (SI->getOperand(0) == GV) + return false; + // If storing the null pointer, ignore it. if (isa(SI->getOperand(0))) continue; - + // Check the value being stored. - Value *Ptr = getUnderlyingObject(SI->getOperand(0)); - - if (isa(Ptr)) { - // Okay, easy case. - } else if (CallInst *CI = dyn_cast(Ptr)) { - Function *F = CI->getCalledFunction(); - if (!F || !F->isDeclaration()) return false; // Too hard to analyze. - if (F->getName() != "calloc") return false; // Not calloc. - } else { - return false; // Too hard to analyze. - } - + Value *Ptr = GetUnderlyingObject(SI->getOperand(0), + GV->getParent()->getDataLayout()); + + if (!isAllocLikeFn(Ptr, TLI)) + return false; // Too hard to analyze. + // Analyze all uses of the allocation. If any of them are used in a // non-simple way (e.g. stored to another global) bail out. - std::vector ReadersWriters; + std::vector ReadersWriters; if (AnalyzeUsesOfPointer(Ptr, ReadersWriters, ReadersWriters, GV)) - return false; // Loaded pointer escapes. + return false; // Loaded pointer escapes. // Remember that this allocation is related to the indirect global. AllocRelatedValues.push_back(Ptr); @@ -327,7 +344,7 @@ bool GlobalsModRef::AnalyzeIndirectGlobalMemory(GlobalValue *GV) { return false; } } - + // Okay, this is an indirect global. Remember all of the allocations for // this global in AllocsForIndirectGlobals. while (!AllocRelatedValues.empty()) { @@ -345,128 +362,143 @@ bool GlobalsModRef::AnalyzeIndirectGlobalMemory(GlobalValue *GV) { void GlobalsModRef::AnalyzeCallGraph(CallGraph &CG, Module &M) { // We do a bottom-up SCC traversal of the call graph. In other words, we // visit all callees before callers (leaf-first). - for (scc_iterator I = scc_begin(&CG), E = scc_end(&CG); I!=E; ++I) - if ((*I).size() != 1) { - AnalyzeSCC(*I); - } else if (Function *F = (*I)[0]->getFunction()) { - if (!F->isDeclaration()) { - // Nonexternal function. - AnalyzeSCC(*I); - } else { - // Otherwise external function. Handle intrinsics and other special - // cases here. - if (getAnalysis().doesNotAccessMemory(F)) - // If it does not access memory, process the function, causing us to - // realize it doesn't do anything (the body is empty). - AnalyzeSCC(*I); - else { - // Otherwise, don't process it. This will cause us to conservatively - // assume the worst. - } - } - } else { - // Do not process the external node, assume the worst. + for (scc_iterator I = scc_begin(&CG); !I.isAtEnd(); ++I) { + const std::vector &SCC = *I; + assert(!SCC.empty() && "SCC with no functions?"); + + if (!SCC[0]->getFunction()) { + // Calls externally - can't say anything useful. Remove any existing + // function records (may have been created when scanning globals). + for (auto *Node : SCC) + FunctionInfo.erase(Node->getFunction()); + continue; } -} -void GlobalsModRef::AnalyzeSCC(std::vector &SCC) { - assert(!SCC.empty() && "SCC with no functions?"); - FunctionRecord &FR = FunctionInfo[SCC[0]->getFunction()]; - - bool CallsExternal = false; - unsigned FunctionEffect = 0; - - // Collect the mod/ref properties due to called functions. We only compute - // one mod-ref set - for (unsigned i = 0, e = SCC.size(); i != e && !CallsExternal; ++i) - for (CallGraphNode::iterator CI = SCC[i]->begin(), E = SCC[i]->end(); - CI != E; ++CI) - if (Function *Callee = CI->second->getFunction()) { - if (FunctionRecord *CalleeFR = getFunctionInfo(Callee)) { - // Propagate function effect up. - FunctionEffect |= CalleeFR->FunctionEffect; - - // Incorporate callee's effects on globals into our info. - for (std::map::iterator GI = - CalleeFR->GlobalInfo.begin(), E = CalleeFR->GlobalInfo.end(); - GI != E; ++GI) - FR.GlobalInfo[GI->first] |= GI->second; + FunctionRecord &FR = FunctionInfo[SCC[0]->getFunction()]; + + bool KnowNothing = false; + unsigned FunctionEffect = 0; + + // Collect the mod/ref properties due to called functions. We only compute + // one mod-ref set. + for (unsigned i = 0, e = SCC.size(); i != e && !KnowNothing; ++i) { + Function *F = SCC[i]->getFunction(); + if (!F) { + KnowNothing = true; + break; + } + if (F->isDeclaration()) { + // Try to get mod/ref behaviour from function attributes. + if (F->doesNotAccessMemory()) { + // Can't do better than that! + } else if (F->onlyReadsMemory()) { + FunctionEffect |= Ref; + if (!F->isIntrinsic()) + // This function might call back into the module and read a global - + // consider every global as possibly being read by this function. + FR.MayReadAnyGlobal = true; } else { - // Okay, if we can't say anything about it, maybe some other alias - // analysis can. - ModRefBehavior MRB = - AliasAnalysis::getModRefBehavior(Callee); - if (MRB != DoesNotAccessMemory) { - // FIXME: could make this more aggressive for functions that just - // read memory. We should just say they read all globals. - CallsExternal = true; - break; - } + FunctionEffect |= ModRef; + // Can't say anything useful unless it's an intrinsic - they don't + // read or write global variables of the kind considered here. + KnowNothing = !F->isIntrinsic(); } - } else { - CallsExternal = true; - break; + continue; } - // If this SCC calls an external function, we can't say anything about it, so - // remove all SCC functions from the FunctionInfo map. - if (CallsExternal) { - for (unsigned i = 0, e = SCC.size(); i != e; ++i) - FunctionInfo.erase(SCC[i]->getFunction()); - return; - } + for (CallGraphNode::iterator CI = SCC[i]->begin(), E = SCC[i]->end(); + CI != E && !KnowNothing; ++CI) + if (Function *Callee = CI->second->getFunction()) { + if (FunctionRecord *CalleeFR = getFunctionInfo(Callee)) { + // Propagate function effect up. + FunctionEffect |= CalleeFR->FunctionEffect; + + // Incorporate callee's effects on globals into our info. + for (const auto &G : CalleeFR->GlobalInfo) + FR.GlobalInfo[G.first] |= G.second; + FR.MayReadAnyGlobal |= CalleeFR->MayReadAnyGlobal; + } else { + // Can't say anything about it. However, if it is inside our SCC, + // then nothing needs to be done. + CallGraphNode *CalleeNode = CG[Callee]; + if (std::find(SCC.begin(), SCC.end(), CalleeNode) == SCC.end()) + KnowNothing = true; + } + } else { + KnowNothing = true; + } + } - // Otherwise, unless we already know that this function mod/refs memory, scan - // the function bodies to see if there are any explicit loads or stores. - if (FunctionEffect != ModRef) { - for (unsigned i = 0, e = SCC.size(); i != e && FunctionEffect != ModRef;++i) + // If we can't say anything useful about this SCC, remove all SCC functions + // from the FunctionInfo map. + if (KnowNothing) { + for (auto *Node : SCC) + FunctionInfo.erase(Node->getFunction()); + continue; + } + + // Scan the function bodies for explicit loads or stores. + for (unsigned i = 0, e = SCC.size(); i != e && FunctionEffect != ModRef; + ++i) for (inst_iterator II = inst_begin(SCC[i]->getFunction()), - E = inst_end(SCC[i]->getFunction()); + E = inst_end(SCC[i]->getFunction()); II != E && FunctionEffect != ModRef; ++II) - if (isa(*II)) + if (LoadInst *LI = dyn_cast(&*II)) { FunctionEffect |= Ref; - else if (isa(*II)) + if (LI->isVolatile()) + // Volatile loads may have side-effects, so mark them as writing + // memory (for example, a flag inside the processor). + FunctionEffect |= Mod; + } else if (StoreInst *SI = dyn_cast(&*II)) { FunctionEffect |= Mod; - else if (isa(*II) || isa(*II)) + if (SI->isVolatile()) + // Treat volatile stores as reading memory somewhere. + FunctionEffect |= Ref; + } else if (isAllocationFn(&*II, TLI) || isFreeCall(&*II, TLI)) { FunctionEffect |= ModRef; - } + } else if (IntrinsicInst *Intrinsic = dyn_cast(&*II)) { + // The callgraph doesn't include intrinsic calls. + Function *Callee = Intrinsic->getCalledFunction(); + ModRefBehavior Behaviour = AliasAnalysis::getModRefBehavior(Callee); + FunctionEffect |= (Behaviour & ModRef); + } - if ((FunctionEffect & Mod) == 0) - ++NumReadMemFunctions; - if (FunctionEffect == 0) - ++NumNoMemFunctions; - FR.FunctionEffect = FunctionEffect; + if ((FunctionEffect & Mod) == 0) + ++NumReadMemFunctions; + if (FunctionEffect == 0) + ++NumNoMemFunctions; + FR.FunctionEffect = FunctionEffect; - // Finally, now that we know the full effect on this SCC, clone the - // information to each function in the SCC. - for (unsigned i = 1, e = SCC.size(); i != e; ++i) - FunctionInfo[SCC[i]->getFunction()] = FR; + // Finally, now that we know the full effect on this SCC, clone the + // information to each function in the SCC. + for (unsigned i = 1, e = SCC.size(); i != e; ++i) + FunctionInfo[SCC[i]->getFunction()] = FR; + } } - - /// alias - If one of the pointers is to a global that we are tracking, and the /// other is some random pointer, we know there cannot be an alias, because the /// address of the global isn't taken. -AliasAnalysis::AliasResult -GlobalsModRef::alias(const Value *V1, unsigned V1Size, - const Value *V2, unsigned V2Size) { +AliasResult GlobalsModRef::alias(const MemoryLocation &LocA, + const MemoryLocation &LocB) { // Get the base object these pointers point to. - Value *UV1 = getUnderlyingObject(const_cast(V1)); - Value *UV2 = getUnderlyingObject(const_cast(V2)); - + const Value *UV1 = GetUnderlyingObject(LocA.Ptr, *DL); + const Value *UV2 = GetUnderlyingObject(LocB.Ptr, *DL); + // If either of the underlying values is a global, they may be non-addr-taken // globals, which we can answer queries about. - GlobalValue *GV1 = dyn_cast(UV1); - GlobalValue *GV2 = dyn_cast(UV2); + const GlobalValue *GV1 = dyn_cast(UV1); + const GlobalValue *GV2 = dyn_cast(UV2); if (GV1 || GV2) { // If the global's address is taken, pretend we don't know it's a pointer to // the global. - if (GV1 && !NonAddressTakenGlobals.count(GV1)) GV1 = 0; - if (GV2 && !NonAddressTakenGlobals.count(GV2)) GV2 = 0; + if (GV1 && !NonAddressTakenGlobals.count(GV1)) + GV1 = nullptr; + if (GV2 && !NonAddressTakenGlobals.count(GV2)) + GV2 = nullptr; - // If the the two pointers are derived from two different non-addr-taken + // If the two pointers are derived from two different non-addr-taken // globals, or if one is and the other isn't, we know these can't alias. if ((GV1 || GV2) && GV1 != GV2) return NoAlias; @@ -474,56 +506,57 @@ GlobalsModRef::alias(const Value *V1, unsigned V1Size, // Otherwise if they are both derived from the same addr-taken global, we // can't know the two accesses don't overlap. } - + // These pointers may be based on the memory owned by an indirect global. If // so, we may be able to handle this. First check to see if the base pointer // is a direct load from an indirect global. - GV1 = GV2 = 0; - if (LoadInst *LI = dyn_cast(UV1)) + GV1 = GV2 = nullptr; + if (const LoadInst *LI = dyn_cast(UV1)) if (GlobalVariable *GV = dyn_cast(LI->getOperand(0))) if (IndirectGlobals.count(GV)) GV1 = GV; - if (LoadInst *LI = dyn_cast(UV2)) - if (GlobalVariable *GV = dyn_cast(LI->getOperand(0))) + if (const LoadInst *LI = dyn_cast(UV2)) + if (const GlobalVariable *GV = dyn_cast(LI->getOperand(0))) if (IndirectGlobals.count(GV)) GV2 = GV; - + // These pointers may also be from an allocation for the indirect global. If // so, also handle them. if (AllocsForIndirectGlobals.count(UV1)) GV1 = AllocsForIndirectGlobals[UV1]; if (AllocsForIndirectGlobals.count(UV2)) GV2 = AllocsForIndirectGlobals[UV2]; - + // Now that we know whether the two pointers are related to indirect globals, // use this to disambiguate the pointers. If either pointer is based on an // indirect global and if they are not both based on the same indirect global, // they cannot alias. if ((GV1 || GV2) && GV1 != GV2) return NoAlias; - - return AliasAnalysis::alias(V1, V1Size, V2, V2Size); + + return AliasAnalysis::alias(LocA, LocB); } AliasAnalysis::ModRefResult -GlobalsModRef::getModRefInfo(CallSite CS, Value *P, unsigned Size) { +GlobalsModRef::getModRefInfo(ImmutableCallSite CS, const MemoryLocation &Loc) { unsigned Known = ModRef; // If we are asking for mod/ref info of a direct call with a pointer to a // global we are tracking, return information if we have it. - if (GlobalValue *GV = dyn_cast(getUnderlyingObject(P))) - if (GV->hasInternalLinkage()) - if (Function *F = CS.getCalledFunction()) + const DataLayout &DL = CS.getCaller()->getParent()->getDataLayout(); + if (const GlobalValue *GV = + dyn_cast(GetUnderlyingObject(Loc.Ptr, DL))) + if (GV->hasLocalLinkage()) + if (const Function *F = CS.getCalledFunction()) if (NonAddressTakenGlobals.count(GV)) - if (FunctionRecord *FR = getFunctionInfo(F)) + if (const FunctionRecord *FR = getFunctionInfo(F)) Known = FR->getInfoForGlobal(GV); if (Known == NoModRef) return NoModRef; // No need to query other mod/ref analyses - return ModRefResult(Known & AliasAnalysis::getModRefInfo(CS, P, Size)); + return ModRefResult(Known & AliasAnalysis::getModRefInfo(CS, Loc)); } - //===----------------------------------------------------------------------===// // Methods to update the analysis as a result of the client transformation. // @@ -534,9 +567,10 @@ void GlobalsModRef::deleteValue(Value *V) { // any AllocRelatedValues for it. if (IndirectGlobals.erase(GV)) { // Remove any entries in AllocsForIndirectGlobals for this global. - for (std::map::iterator - I = AllocsForIndirectGlobals.begin(), - E = AllocsForIndirectGlobals.end(); I != E; ) { + for (std::map::iterator + I = AllocsForIndirectGlobals.begin(), + E = AllocsForIndirectGlobals.end(); + I != E;) { if (I->second == GV) { AllocsForIndirectGlobals.erase(I++); } else { @@ -546,14 +580,20 @@ void GlobalsModRef::deleteValue(Value *V) { } } } - + // Otherwise, if this is an allocation related to an indirect global, remove // it. AllocsForIndirectGlobals.erase(V); - + AliasAnalysis::deleteValue(V); } -void GlobalsModRef::copyValue(Value *From, Value *To) { - AliasAnalysis::copyValue(From, To); +void GlobalsModRef::addEscapingUse(Use &U) { + // For the purposes of this analysis, it is conservatively correct to treat + // a newly escaping value equivalently to a deleted one. We could perhaps + // be more precise by processing the new use and attempting to update our + // saved analysis results to accommodate it. + deleteValue(U); + + AliasAnalysis::addEscapingUse(U); }