X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FIPA%2FGlobalsModRef.cpp;h=18a7233075ea7f415100a254bb8d20e68e923c23;hb=89576cea3ff721821ce288d9c9aa338a6aed97e7;hp=01090f11cb27096c264757eb00ad586bff649dde;hpb=f5a86f45e75ec744c203270ffa03659eb0a220c1;p=oota-llvm.git diff --git a/lib/Analysis/IPA/GlobalsModRef.cpp b/lib/Analysis/IPA/GlobalsModRef.cpp index 01090f11cb2..18a7233075e 100644 --- a/lib/Analysis/IPA/GlobalsModRef.cpp +++ b/lib/Analysis/IPA/GlobalsModRef.cpp @@ -14,23 +14,27 @@ // //===----------------------------------------------------------------------===// -#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/SmallPtrSet.h" +#include "llvm/ADT/Statistic.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/CallGraph.h" -#include "llvm/Analysis/MallocHelper.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 +#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"); @@ -38,137 +42,331 @@ STATISTIC(NumNoMemFunctions, "Number of functions that do not access memory"); STATISTIC(NumReadMemFunctions, "Number of functions that only read memory"); STATISTIC(NumIndirectGlobalVars, "Number of indirect global objects"); +// An option to enable unsafe alias results from the GlobalsModRef analysis. +// When enabled, GlobalsModRef will provide no-alias results which in extremely +// rare cases may not be conservatively correct. In particular, in the face of +// transforms which cause assymetry between how effective GetUnderlyingObject +// is for two pointers, it may produce incorrect results. +// +// These unsafe results have been returned by GMR for many years without +// causing significant issues in the wild and so we provide a mechanism to +// re-enable them for users of LLVM that have a particular performance +// sensitivity and no known issues. The option also makes it easy to evaluate +// the performance impact of these results. +static cl::opt EnableUnsafeGlobalsModRefAliasResults( + "enable-unsafe-globalsmodref-alias-results", cl::init(false), cl::Hidden); + 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 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(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; +/// 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 { + typedef SmallDenseMap GlobalInfoMapType; + + /// Build a wrapper struct that has 8-byte alignment. All heap allocations + /// should provide this much alignment at least, but this makes it clear we + /// specifically rely on this amount of alignment. + struct LLVM_ALIGNAS(8) AlignedMap { + AlignedMap() {} + AlignedMap(const AlignedMap &Arg) : Map(Arg.Map) {} + GlobalInfoMapType Map; + }; + + /// Pointer traits for our aligned map. + struct AlignedMapPointerTraits { + static inline void *getAsVoidPointer(AlignedMap *P) { return P; } + static inline AlignedMap *getFromVoidPointer(void *P) { + return (AlignedMap *)P; } + enum { NumLowBitsAvailable = 3 }; + static_assert(AlignOf::Alignment >= (1 << NumLowBitsAvailable), + "AlignedMap insufficiently aligned to have enough low bits."); + }; - /// 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; + /// The bit that flags that this function may read any global. This is + /// chosen to mix together with ModRefInfo bits. + enum { MayReadAnyGlobal = 4 }; + + /// Checks to document the invariants of the bit packing here. + static_assert((MayReadAnyGlobal & MRI_ModRef) == 0, + "ModRef and the MayReadAnyGlobal flag bits overlap."); + static_assert(((MayReadAnyGlobal | MRI_ModRef) >> + AlignedMapPointerTraits::NumLowBitsAvailable) == 0, + "Insufficient low bits to store our flag and ModRef info."); + +public: + FunctionInfo() : Info() {} + ~FunctionInfo() { + delete Info.getPointer(); + } + // Spell out the copy ond move constructors and assignment operators to get + // deep copy semantics and correct move semantics in the face of the + // pointer-int pair. + FunctionInfo(const FunctionInfo &Arg) + : Info(nullptr, Arg.Info.getInt()) { + if (const auto *ArgPtr = Arg.Info.getPointer()) + Info.setPointer(new AlignedMap(*ArgPtr)); + } + FunctionInfo(FunctionInfo &&Arg) + : Info(Arg.Info.getPointer(), Arg.Info.getInt()) { + Arg.Info.setPointerAndInt(nullptr, 0); + } + FunctionInfo &operator=(const FunctionInfo &RHS) { + delete Info.getPointer(); + Info.setPointerAndInt(nullptr, RHS.Info.getInt()); + if (const auto *RHSPtr = RHS.Info.getPointer()) + Info.setPointer(new AlignedMap(*RHSPtr)); + return *this; + } + FunctionInfo &operator=(FunctionInfo &&RHS) { + delete Info.getPointer(); + Info.setPointerAndInt(RHS.Info.getPointer(), RHS.Info.getInt()); + RHS.Info.setPointerAndInt(nullptr, 0); + return *this; + } - FunctionRecord() : MayReadAnyGlobal (false), FunctionEffect(0) {} - }; + /// Returns the \c ModRefInfo info for this function. + ModRefInfo getModRefInfo() const { + return ModRefInfo(Info.getInt() & MRI_ModRef); + } - /// GlobalsModRef - The actual analysis pass. - class GlobalsModRef : public ModulePass, public AliasAnalysis { - /// NonAddressTakenGlobals - The globals that do not have their addresses - /// taken. - std::set NonAddressTakenGlobals; + /// Adds new \c ModRefInfo for this function to its state. + void addModRefInfo(ModRefInfo NewMRI) { + Info.setInt(Info.getInt() | NewMRI); + } - /// IndirectGlobals - The memory pointed to by this global is known to be - /// 'owned' by the global. - std::set IndirectGlobals; + /// Returns whether this function may read any global variable, and we don't + /// know which global. + bool mayReadAnyGlobal() const { return Info.getInt() & MayReadAnyGlobal; } + + /// Sets this function as potentially reading from any global. + void setMayReadAnyGlobal() { Info.setInt(Info.getInt() | MayReadAnyGlobal); } + + /// Returns the \c ModRefInfo info for this function w.r.t. a particular + /// global, which may be more precise than the general information above. + ModRefInfo getModRefInfoForGlobal(const GlobalValue &GV) const { + ModRefInfo GlobalMRI = mayReadAnyGlobal() ? MRI_Ref : MRI_NoModRef; + if (AlignedMap *P = Info.getPointer()) { + auto I = P->Map.find(&GV); + if (I != P->Map.end()) + GlobalMRI = ModRefInfo(GlobalMRI | I->second); + } + return GlobalMRI; + } - /// AllocsForIndirectGlobals - If an instruction allocates memory for an - /// indirect global, this map indicates which one. - std::map AllocsForIndirectGlobals; + /// Add mod/ref info from another function into ours, saturating towards + /// MRI_ModRef. + void addFunctionInfo(const FunctionInfo &FI) { + addModRefInfo(FI.getModRefInfo()); - /// FunctionInfo - For each function, keep track of what globals are - /// modified or read. - std::map FunctionInfo; + if (FI.mayReadAnyGlobal()) + setMayReadAnyGlobal(); - public: - static char ID; - GlobalsModRef() : ModulePass(&ID) {} + if (AlignedMap *P = FI.Info.getPointer()) + for (const auto &G : P->Map) + addModRefInfoForGlobal(*G.first, G.second); + } - 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; + void addModRefInfoForGlobal(const GlobalValue &GV, ModRefInfo NewMRI) { + AlignedMap *P = Info.getPointer(); + if (!P) { + P = new AlignedMap(); + Info.setPointer(P); } + auto &GlobalMRI = P->Map[&GV]; + GlobalMRI = ModRefInfo(GlobalMRI | NewMRI); + } - virtual void getAnalysisUsage(AnalysisUsage &AU) const { - AliasAnalysis::getAnalysisUsage(AU); - AU.addRequired(); - AU.setPreservesAll(); // Does not transform code - } + /// Clear a global's ModRef info. Should be used when a global is being + /// deleted. + void eraseModRefInfoForGlobal(const GlobalValue &GV) { + if (AlignedMap *P = Info.getPointer()) + P->Map.erase(&GV); + } - //------------------------------------------------ - // 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); - } - 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. - ModRefBehavior getModRefBehavior(Function *F, - std::vector *Info) { - if (FunctionRecord *FR = getFunctionInfo(F)) { - if (FR->FunctionEffect == 0) - return DoesNotAccessMemory; - else if ((FR->FunctionEffect & Mod) == 0) - return OnlyReadsMemory; - } - return AliasAnalysis::getModRefBehavior(F, Info); - } - - /// 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; +private: + /// All of the information is encoded into a single pointer, with a three bit + /// integer in the low three bits. The high bit provides a flag for when this + /// function may read any global. The low two bits are the ModRefInfo. And + /// the pointer, when non-null, points to a map from GlobalValue to + /// ModRefInfo specific to that GlobalValue. + 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); + } } - return AliasAnalysis::getModRefBehavior(CS, Info); + + // 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! } + }; + + /// 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; - virtual void deleteValue(Value *V); - virtual void copyValue(Value *From, Value *To); - - 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); - if (I != FunctionInfo.end()) - return &I->second; - return 0; +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; + } + + 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 { + FunctionModRefBehavior Min = FMRB_UnknownModRefBehavior; + + if (FunctionInfo *FI = getFunctionInfo(F)) { + if (FI->getModRefInfo() == MRI_NoModRef) + Min = FMRB_DoesNotAccessMemory; + else if ((FI->getModRefInfo() & MRI_Mod) == 0) + Min = FMRB_OnlyReadsMemory; } - void AnalyzeGlobals(Module &M); - void AnalyzeCallGraph(CallGraph &CG, Module &M); - bool AnalyzeUsesOfPointer(Value *V, std::vector &Readers, - std::vector &Writers, - GlobalValue *OkayStoreDest = 0); - bool AnalyzeIndirectGlobalMemory(GlobalValue *GV); - }; + 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); +}; } 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(); } @@ -177,38 +375,53 @@ Pass *llvm::createGlobalsModRefPass() { return new GlobalsModRef(); } /// (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->hasLocalLinkage()) { - if (!AnalyzeUsesOfPointer(I, Readers, Writers)) { + SmallPtrSet TrackedFunctions; + for (Function &F : M) + if (F.hasLocalLinkage()) + if (!AnalyzeUsesOfPointer(&F)) { // Remember that we are tracking this global. - NonAddressTakenGlobals.insert(I); + NonAddressTakenGlobals.insert(&F); + TrackedFunctions.insert(&F); + Handles.emplace_front(*this, &F); + Handles.front().I = Handles.begin(); ++NumNonAddrTakenFunctions; } - Readers.clear(); Writers.clear(); - } - for (Module::global_iterator I = M.global_begin(), E = M.global_end(); - I != E; ++I) - if (I->hasLocalLinkage()) { - if (!AnalyzeUsesOfPointer(I, Readers, Writers)) { + SmallPtrSet Readers, Writers; + for (GlobalVariable &GV : M.globals()) + if (GV.hasLocalLinkage()) { + if (!AnalyzeUsesOfPointer(&GV, &Readers, + GV.isConstant() ? nullptr : &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); + Handles.emplace_front(*this, &GV); + Handles.front().I = Handles.begin(); + + for (Function *Reader : Readers) { + if (TrackedFunctions.insert(Reader).second) { + Handles.emplace_front(*this, Reader); + Handles.front().I = Handles.begin(); + } + FunctionInfos[Reader].addModRefInfoForGlobal(GV, MRI_Ref); + } - 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; + if (!GV.isConstant()) // No need to keep track of writers to constants + for (Function *Writer : Writers) { + if (TrackedFunctions.insert(Writer).second) { + Handles.emplace_front(*this, Writer); + Handles.front().I = Handles.begin(); + } + FunctionInfos[Writer].addModRefInfoForGlobal(GV, MRI_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(); } } @@ -219,51 +432,50 @@ 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, + SmallPtrSetImpl *Readers, + SmallPtrSetImpl *Writers, GlobalValue *OkayStoreDest) { - if (!isa(V->getType())) return true; - - for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E; ++UI) - if (LoadInst *LI = dyn_cast(*UI)) { - Readers.push_back(LI->getParent()->getParent()); - } else if (StoreInst *SI = dyn_cast(*UI)) { + if (!V->getType()->isPointerTy()) + return true; + + for (Use &U : V->uses()) { + User *I = U.getUser(); + if (LoadInst *LI = dyn_cast(I)) { + if (Readers) + Readers->insert(LI->getParent()->getParent()); + } else if (StoreInst *SI = dyn_cast(I)) { if (V == SI->getOperand(1)) { - Writers.push_back(SI->getParent()->getParent()); + if (Writers) + Writers->insert(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 (BitCastInst *BCI = dyn_cast(*UI)) { - if (AnalyzeUsesOfPointer(BCI, Readers, Writers, OkayStoreDest)) + } else if (Operator::getOpcode(I) == Instruction::GetElementPtr) { + if (AnalyzeUsesOfPointer(I, Readers, Writers)) return true; - } else if (isa(*UI) || isFreeCall(*UI)) { - Writers.push_back(cast(*UI)->getParent()->getParent()); - } 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::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)) { + if (Writers) + Writers->insert(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. + return true; // Allow comparison against null. } else { return true; } + } + return false; } @@ -277,45 +489,39 @@ 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; - if (AnalyzeUsesOfPointer(LI, ReadersWriters, ReadersWriters)) - return false; // Loaded pointer escapes. + if (AnalyzeUsesOfPointer(LI)) + 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 = 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 { - 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; - if (AnalyzeUsesOfPointer(Ptr, ReadersWriters, ReadersWriters, GV)) - return false; // Loaded pointer escapes. + if (AnalyzeUsesOfPointer(Ptr, /*Readers*/ nullptr, /*Writers*/ nullptr, + GV)) + return false; // Loaded pointer escapes. // Remember that this allocation is related to the indirect global. AllocRelatedValues.push_back(Ptr); @@ -329,9 +535,13 @@ bool GlobalsModRef::AnalyzeIndirectGlobalMemory(GlobalValue *GV) { // this global in AllocsForIndirectGlobals. while (!AllocRelatedValues.empty()) { AllocsForIndirectGlobals[AllocRelatedValues.back()] = GV; + Handles.emplace_front(*this, AllocRelatedValues.back()); + Handles.front().I = Handles.begin(); AllocRelatedValues.pop_back(); } IndirectGlobals.insert(GV); + Handles.emplace_front(*this, GV); + Handles.front().I = Handles.begin(); return true; } @@ -342,23 +552,20 @@ 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()) { // Calls externally - can't say anything useful. Remove any existing // function records (may have been created when scanning globals). - for (unsigned i = 0, e = SCC.size(); i != e; ++i) - FunctionInfo.erase(SCC[i]->getFunction()); + for (auto *Node : SCC) + FunctionInfos.erase(Node->getFunction()); continue; } - FunctionRecord &FR = FunctionInfo[SCC[0]->getFunction()]; - + FunctionInfo &FI = FunctionInfos[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. @@ -374,13 +581,13 @@ void GlobalsModRef::AnalyzeCallGraph(CallGraph &CG, Module &M) { if (F->doesNotAccessMemory()) { // Can't do better than that! } else if (F->onlyReadsMemory()) { - FunctionEffect |= Ref; + FI.addModRefInfo(MRI_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; + FI.setMayReadAnyGlobal(); } else { - FunctionEffect |= ModRef; + FI.addModRefInfo(MRI_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(); @@ -391,16 +598,9 @@ void GlobalsModRef::AnalyzeCallGraph(CallGraph &CG, Module &M) { 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)) { + if (FunctionInfo *CalleeFI = 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; - FR.MayReadAnyGlobal |= CalleeFR->MayReadAnyGlobal; + FI.addFunctionInfo(*CalleeFI); } else { // Can't say anything about it. However, if it is inside our SCC, // then nothing needs to be done. @@ -414,74 +614,93 @@ void GlobalsModRef::AnalyzeCallGraph(CallGraph &CG, Module &M) { } // If we can't say anything useful about this SCC, remove all SCC functions - // from the FunctionInfo map. + // from the FunctionInfos map. if (KnowNothing) { - for (unsigned i = 0, e = SCC.size(); i != e; ++i) - FunctionInfo.erase(SCC[i]->getFunction()); + for (auto *Node : SCC) + FunctionInfos.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()); - II != E && FunctionEffect != ModRef; ++II) - if (isa(*II)) { - FunctionEffect |= Ref; - if (cast(*II).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)) { - FunctionEffect |= Mod; - if (cast(*II).isVolatile()) - // Treat volatile stores as reading memory somewhere. - FunctionEffect |= Ref; - } else if (isMalloc(&cast(*II)) || isa(*II) || - isFreeCall(&cast(*II))) { - FunctionEffect |= ModRef; + for (auto *Node : SCC) { + if (FI.getModRefInfo() == MRI_ModRef) + break; // The mod/ref lattice saturates here. + for (Instruction &I : inst_range(Node->getFunction())) { + if (FI.getModRefInfo() == MRI_ModRef) + break; // The mod/ref lattice saturates here. + + // We handle calls specially because the graph-relevant aspects are + // handled above. + if (auto CS = CallSite(&I)) { + if (isAllocationFn(&I, TLI) || isFreeCall(&I, TLI)) { + // FIXME: It is completely unclear why this is necessary and not + // handled by the above graph code. + FI.addModRefInfo(MRI_ModRef); + } else if (Function *Callee = CS.getCalledFunction()) { + // The callgraph doesn't include intrinsic calls. + if (Callee->isIntrinsic()) { + FunctionModRefBehavior Behaviour = + AliasAnalysis::getModRefBehavior(Callee); + FI.addModRefInfo(ModRefInfo(Behaviour & MRI_ModRef)); + } + } + continue; } - if ((FunctionEffect & Mod) == 0) + // All non-call instructions we use the primary predicates for whether + // thay read or write memory. + if (I.mayReadFromMemory()) + FI.addModRefInfo(MRI_Ref); + if (I.mayWriteToMemory()) + FI.addModRefInfo(MRI_Mod); + } + } + + if ((FI.getModRefInfo() & MRI_Mod) == 0) ++NumReadMemFunctions; - if (FunctionEffect == 0) + if (FI.getModRefInfo() == MRI_NoModRef) ++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; + FunctionInfos[SCC[i]->getFunction()] = FI; } } - - /// 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 = const_cast(V1->getUnderlyingObject()); - Value *UV2 = const_cast(V2->getUnderlyingObject()); + 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 the 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) + 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 we know these can't alias. + if (GV1 && GV2 && GV1 != GV2) return NoAlias; + // If one is and the other isn't, it isn't strictly safe but we can fake + // this result if necessary for performance. This does not appear to be + // a common problem in practice. + if (EnableUnsafeGlobalsModRefAliasResults) + if ((GV1 || GV2) && GV1 != GV2) + return NoAlias; + // Otherwise if they are both derived from the same addr-taken global, we // can't know the two accesses don't overlap. } @@ -489,82 +708,55 @@ 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; // 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]; + if (!GV1) + GV1 = AllocsForIndirectGlobals.lookup(UV1); + if (!GV2) + GV2 = AllocsForIndirectGlobals.lookup(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) + // use this to disambiguate the pointers. If the pointers are based on + // different indirect globals they cannot alias. + if (GV1 && GV2 && GV1 != GV2) return NoAlias; - return AliasAnalysis::alias(V1, V1Size, V2, V2Size); + // If one is based on an indirect global and the other isn't, it isn't + // strictly safe but we can fake this result if necessary for performance. + // This does not appear to be a common problem in practice. + if (EnableUnsafeGlobalsModRefAliasResults) + if ((GV1 || GV2) && GV1 != GV2) + return NoAlias; + + return AliasAnalysis::alias(LocA, LocB); } -AliasAnalysis::ModRefResult -GlobalsModRef::getModRefInfo(CallSite CS, Value *P, unsigned Size) { - unsigned Known = ModRef; +ModRefInfo GlobalsModRef::getModRefInfo(ImmutableCallSite CS, + const MemoryLocation &Loc) { + unsigned Known = MRI_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())) + const DataLayout &DL = CS.getCaller()->getParent()->getDataLayout(); + if (const GlobalValue *GV = + dyn_cast(GetUnderlyingObject(Loc.Ptr, DL))) if (GV->hasLocalLinkage()) - if (Function *F = CS.getCalledFunction()) + if (const Function *F = CS.getCalledFunction()) if (NonAddressTakenGlobals.count(GV)) - if (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)); -} - - -//===----------------------------------------------------------------------===// -// Methods to update the analysis as a result of the client transformation. -// -void GlobalsModRef::deleteValue(Value *V) { - if (GlobalValue *GV = dyn_cast(V)) { - if (NonAddressTakenGlobals.erase(GV)) { - // This global might be an indirect global. If so, remove it and remove - // 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; ) { - if (I->second == GV) { - AllocsForIndirectGlobals.erase(I++); - } else { - ++I; - } - } - } - } - } - - // Otherwise, if this is an allocation related to an indirect global, remove - // it. - AllocsForIndirectGlobals.erase(V); - - AliasAnalysis::deleteValue(V); -} + if (const FunctionInfo *FI = getFunctionInfo(F)) + Known = FI->getModRefInfoForGlobal(*GV); -void GlobalsModRef::copyValue(Value *From, Value *To) { - AliasAnalysis::copyValue(From, To); + if (Known == MRI_NoModRef) + return MRI_NoModRef; // No need to query other mod/ref analyses + return ModRefInfo(Known & AliasAnalysis::getModRefInfo(CS, Loc)); }