X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FIPA%2FGlobalsModRef.cpp;h=607c06810123ebeb1ebee7f811714a9ecd9edf64;hb=12af22e8cc217827cf4f118b0f5e4ebbda9925ae;hp=f13deea41d4ede8642dccdbd584bde689af98964;hpb=8be3291f5942e3ae4a5d66c480e7aabe2f771031;p=oota-llvm.git diff --git a/lib/Analysis/IPA/GlobalsModRef.cpp b/lib/Analysis/IPA/GlobalsModRef.cpp index f13deea41d4..607c0681012 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/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"); @@ -47,14 +50,15 @@ namespace { /// 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; + std::map GlobalInfo; /// MayReadAnyGlobal - May read global variables, but it is not known which. bool MayReadAnyGlobal; - unsigned getInfoForGlobal(GlobalValue *GV) const { + unsigned getInfoForGlobal(const GlobalValue *GV) const { unsigned Effect = MayReadAnyGlobal ? AliasAnalysis::Ref : 0; - std::map::const_iterator I = GlobalInfo.find(GV); + std::map::const_iterator I = + GlobalInfo.find(GV); if (I != GlobalInfo.end()) Effect |= I->second; return Effect; @@ -71,86 +75,97 @@ namespace { class GlobalsModRef : public ModulePass, public AliasAnalysis { /// NonAddressTakenGlobals - The globals that do not have their addresses /// taken. - std::set NonAddressTakenGlobals; + std::set NonAddressTakenGlobals; /// IndirectGlobals - The memory pointed to by this global is known to be /// 'owned' by the global. - std::set IndirectGlobals; + std::set IndirectGlobals; /// AllocsForIndirectGlobals - If an instruction allocates memory for an /// indirect global, this map indicates which one. - std::map AllocsForIndirectGlobals; + std::map AllocsForIndirectGlobals; /// FunctionInfo - For each function, keep track of what globals are /// modified or read. - std::map FunctionInfo; + std::map FunctionInfo; public: static char ID; - GlobalsModRef() : ModulePass(&ID) {} + GlobalsModRef() : ModulePass(ID) { + initializeGlobalsModRefPass(*PassRegistry::getPassRegistry()); + } + + bool runOnModule(Module &M) override { + InitializeAliasAnalysis(this); + + // Find non-addr taken globals. + AnalyzeGlobals(M); - bool runOnModule(Module &M) { - InitializeAliasAnalysis(this); // set up super class - AnalyzeGlobals(M); // find non-addr taken globals - AnalyzeCallGraph(getAnalysis(), M); // Propagate on CG + // Propagate on CG. + AnalyzeCallGraph(getAnalysis().getCallGraph(), M); return false; } - virtual void getAnalysisUsage(AnalysisUsage &AU) const { + void getAnalysisUsage(AnalysisUsage &AU) const override { AliasAnalysis::getAnalysisUsage(AU); - AU.addRequired(); + AU.addRequired(); AU.setPreservesAll(); // Does not transform code } //------------------------------------------------ // 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); + AliasResult alias(const Location &LocA, const Location &LocB) override; + ModRefResult getModRefInfo(ImmutableCallSite CS, + const Location &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(Function *F, - std::vector *Info) { + ModRefBehavior getModRefBehavior(const Function *F) override { + ModRefBehavior Min = UnknownModRefBehavior; + 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, 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(CallSite CS, - std::vector *Info) { - Function* F = CS.getCalledFunction(); - if (!F) return AliasAnalysis::getModRefBehavior(CS, Info); - if (FunctionRecord *FR = getFunctionInfo(F)) { - if (FR->FunctionEffect == 0) - return DoesNotAccessMemory; - else if ((FR->FunctionEffect & Mod) == 0) - return OnlyReadsMemory; - } - return AliasAnalysis::getModRefBehavior(CS, Info); + ModRefBehavior getModRefBehavior(ImmutableCallSite CS) override { + ModRefBehavior Min = UnknownModRefBehavior; + + if (const Function* F = CS.getCalledFunction()) + if (FunctionRecord *FR = getFunctionInfo(F)) { + if (FR->FunctionEffect == 0) + Min = DoesNotAccessMemory; + else if ((FR->FunctionEffect & Mod) == 0) + Min = OnlyReadsMemory; + } + + return ModRefBehavior(AliasAnalysis::getModRefBehavior(CS) & Min); } - virtual void deleteValue(Value *V); - virtual void copyValue(Value *From, Value *To); + void deleteValue(Value *V) override; + void copyValue(Value *From, Value *To) 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. - virtual void *getAdjustedAnalysisPointer(const PassInfo *PI) { - if (PI->isPassID(&AliasAnalysis::ID)) + void *getAdjustedAnalysisPointer(AnalysisID PI) override { + if (PI == &AliasAnalysis::ID) return (AliasAnalysis*)this; return this; } @@ -158,26 +173,31 @@ namespace { private: /// getFunctionInfo - Return the function info for the function, or null if /// we don't have anything useful to say about it. - FunctionRecord *getFunctionInfo(Function *F) { - std::map::iterator I = FunctionInfo.find(F); + FunctionRecord *getFunctionInfo(const Function *F) { + std::map::iterator I = + FunctionInfo.find(F); if (I != FunctionInfo.end()) return &I->second; - return 0; + return nullptr; } void AnalyzeGlobals(Module &M); void AnalyzeCallGraph(CallGraph &CG, Module &M); bool AnalyzeUsesOfPointer(Value *V, std::vector &Readers, std::vector &Writers, - GlobalValue *OkayStoreDest = 0); + GlobalValue *OkayStoreDest = nullptr); bool AnalyzeIndirectGlobalMemory(GlobalValue *GV); }; } char GlobalsModRef::ID = 0; -static RegisterPass -X("globalsmodref-aa", "Simple mod/ref analysis for globals", false, true); -static RegisterAnalysisGroup Y(X); +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(); } @@ -233,42 +253,33 @@ bool GlobalsModRef::AnalyzeUsesOfPointer(Value *V, GlobalValue *OkayStoreDest) { if (!V->getType()->isPointerTy()) return true; - for (Value::use_iterator UI = V->use_begin(), E=V->use_end(); UI != E; ++UI) { - User *U = *UI; - if (LoadInst *LI = dyn_cast(U)) { + 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(U)) { + } 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 } - } else if (GetElementPtrInst *GEP = dyn_cast(U)) { - if (AnalyzeUsesOfPointer(GEP, Readers, Writers)) return true; - } else if (BitCastInst *BCI = dyn_cast(U)) { - if (AnalyzeUsesOfPointer(BCI, Readers, Writers, OkayStoreDest)) + } else if (Operator::getOpcode(I) == Instruction::GetElementPtr) { + if (AnalyzeUsesOfPointer(I, Readers, Writers)) return true; - } else if (isFreeCall(U)) { - Writers.push_back(cast(U)->getParent()->getParent()); - } else if (CallInst *CI = dyn_cast(U)) { - // Make sure that this is just the function being called, not that it is - // passing into the function. - for (unsigned i = 0, e = CI->getNumArgOperands(); i != e; ++i) - if (CI->getArgOperand(i) == V) return true; - } else if (InvokeInst *II = dyn_cast(U)) { + } else if (Operator::getOpcode(I) == Instruction::BitCast) { + if (AnalyzeUsesOfPointer(I, Readers, Writers, OkayStoreDest)) + return true; + } else if (CallSite CS = I) { // Make sure that this is just the function being called, not that it is // passing into the function. - for (unsigned i = 0, e = II->getNumArgOperands(); i != e; ++i) - if (II->getArgOperand(i) == V) return true; - } else if (ConstantExpr *CE = dyn_cast(U)) { - 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(U)) { + } else if (ICmpInst *ICI = dyn_cast(I)) { if (!isa(ICI->getOperand(1))) return true; // Allow comparison against null. } else { @@ -293,8 +304,7 @@ bool GlobalsModRef::AnalyzeIndirectGlobalMemory(GlobalValue *GV) { // 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){ - User *U = *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 @@ -312,17 +322,10 @@ bool GlobalsModRef::AnalyzeIndirectGlobalMemory(GlobalValue *GV) { continue; // Check the value being stored. - Value *Ptr = SI->getOperand(0)->getUnderlyingObject(); - - if (isMalloc(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 { + Value *Ptr = GetUnderlyingObject(SI->getOperand(0)); + + 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. @@ -355,9 +358,8 @@ 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) { - std::vector &SCC = *I; + 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()) { @@ -409,10 +411,8 @@ void GlobalsModRef::AnalyzeCallGraph(CallGraph &CG, Module &M) { 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; + 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, @@ -439,20 +439,24 @@ void GlobalsModRef::AnalyzeCallGraph(CallGraph &CG, Module &M) { for (inst_iterator II = inst_begin(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; - if (cast(*II).isVolatile()) + 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 (isa(*II)) { + } else if (StoreInst *SI = dyn_cast(&*II)) { FunctionEffect |= Mod; - if (cast(*II).isVolatile()) + if (SI->isVolatile()) // Treat volatile stores as reading memory somewhere. FunctionEffect |= Ref; - } else if (isMalloc(&cast(*II)) || - isFreeCall(&cast(*II))) { + } 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) @@ -474,21 +478,21 @@ void GlobalsModRef::AnalyzeCallGraph(CallGraph &CG, Module &M) { /// 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) { +GlobalsModRef::alias(const Location &LocA, + const Location &LocB) { // Get the base object these pointers point to. - Value *UV1 = const_cast(V1->getUnderlyingObject()); - Value *UV2 = const_cast(V2->getUnderlyingObject()); + const Value *UV1 = GetUnderlyingObject(LocA.Ptr); + const Value *UV2 = GetUnderlyingObject(LocB.Ptr); // 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 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. @@ -502,13 +506,13 @@ GlobalsModRef::alias(const Value *V1, unsigned V1Size, // 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; @@ -526,25 +530,27 @@ GlobalsModRef::alias(const Value *V1, unsigned V1Size, 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 Location &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(P->getUnderlyingObject())) + if (const GlobalValue *GV = + dyn_cast(GetUnderlyingObject(Loc.Ptr))) if (GV->hasLocalLinkage()) - if (Function *F = CS.getCalledFunction()) + 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)); } @@ -558,7 +564,7 @@ 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 + for (std::map::iterator I = AllocsForIndirectGlobals.begin(), E = AllocsForIndirectGlobals.end(); I != E; ) { if (I->second == GV) { @@ -581,3 +587,13 @@ void GlobalsModRef::deleteValue(Value *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); +}