X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FIPO%2FFunctionAttrs.cpp;h=298d5cf39162f788c5eb4b89649dc8d33f68ee42;hb=9fcd72b71afda971915ff17614431a725811be4b;hp=97f82ad85121ddc9865f7ff32ee53b215401f011;hpb=00e7ea98c0fd4a568fe974e79fb44913f173fa77;p=oota-llvm.git diff --git a/lib/Transforms/IPO/FunctionAttrs.cpp b/lib/Transforms/IPO/FunctionAttrs.cpp index 97f82ad8512..298d5cf3916 100644 --- a/lib/Transforms/IPO/FunctionAttrs.cpp +++ b/lib/Transforms/IPO/FunctionAttrs.cpp @@ -22,26 +22,29 @@ #include "llvm/Transforms/IPO.h" #include "llvm/CallGraphSCCPass.h" #include "llvm/GlobalVariable.h" -#include "llvm/Instructions.h" +#include "llvm/IntrinsicInst.h" +#include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/CallGraph.h" -#include "llvm/ADT/PointerIntPair.h" +#include "llvm/Analysis/CaptureTracking.h" +#include "llvm/Analysis/MemoryBuiltins.h" #include "llvm/ADT/SmallSet.h" #include "llvm/ADT/Statistic.h" -#include "llvm/Support/Compiler.h" +#include "llvm/ADT/UniqueVector.h" #include "llvm/Support/InstIterator.h" using namespace llvm; STATISTIC(NumReadNone, "Number of functions marked readnone"); STATISTIC(NumReadOnly, "Number of functions marked readonly"); STATISTIC(NumNoCapture, "Number of arguments marked nocapture"); +STATISTIC(NumNoAlias, "Number of function returns marked noalias"); namespace { - struct VISIBILITY_HIDDEN FunctionAttrs : public CallGraphSCCPass { + struct FunctionAttrs : public CallGraphSCCPass { static char ID; // Pass identification, replacement for typeid FunctionAttrs() : CallGraphSCCPass(&ID) {} // runOnSCC - Analyze the SCC, performing the transformation if possible. - bool runOnSCC(const std::vector &SCC); + bool runOnSCC(std::vector &SCC); // AddReadAttrs - Deduce readonly/readnone attributes for the SCC. bool AddReadAttrs(const std::vector &SCC); @@ -49,8 +52,12 @@ namespace { // AddNoCaptureAttrs - Deduce nocapture attributes for the SCC. bool AddNoCaptureAttrs(const std::vector &SCC); - // isCaptured - Return true if this pointer value may be captured. - bool isCaptured(Function &F, Value *V); + // IsFunctionMallocLike - Does this function allocate new memory? + bool IsFunctionMallocLike(Function *F, + SmallPtrSet &) const; + + // AddNoAliasAttrs - Deduce noalias attributes for the SCC. + bool AddNoAliasAttrs(const std::vector &SCC); virtual void getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesCFG(); @@ -72,27 +79,57 @@ Pass *llvm::createFunctionAttrsPass() { return new FunctionAttrs(); } /// memory that is local to the function. Global constants are considered /// local to all functions. bool FunctionAttrs::PointsToLocalMemory(Value *V) { - V = V->getUnderlyingObject(); - // An alloca instruction defines local memory. - if (isa(V)) - return true; - // A global constant counts as local memory for our purposes. - if (GlobalVariable *GV = dyn_cast(V)) - return GV->isConstant(); - // Could look through phi nodes and selects here, but it doesn't seem - // to be useful in practice. - return false; + SmallVector Worklist; + unsigned MaxLookup = 8; + + Worklist.push_back(V); + + do { + V = Worklist.pop_back_val()->getUnderlyingObject(); + + // An alloca instruction defines local memory. + if (isa(V)) + continue; + + // A global constant counts as local memory for our purposes. + if (GlobalVariable *GV = dyn_cast(V)) { + if (!GV->isConstant()) + return false; + continue; + } + + // If both select values point to local memory, then so does the select. + if (SelectInst *SI = dyn_cast(V)) { + Worklist.push_back(SI->getTrueValue()); + Worklist.push_back(SI->getFalseValue()); + continue; + } + + // If all values incoming to a phi node point to local memory, then so does + // the phi. + if (PHINode *PN = dyn_cast(V)) { + // Don't bother inspecting phi nodes with many operands. + if (PN->getNumIncomingValues() > MaxLookup) + return false; + for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) + Worklist.push_back(PN->getIncomingValue(i)); + continue; + } + + return false; + } while (!Worklist.empty() && --MaxLookup); + + return Worklist.empty(); } /// AddReadAttrs - Deduce readonly/readnone attributes for the SCC. bool FunctionAttrs::AddReadAttrs(const std::vector &SCC) { - SmallPtrSet SCCNodes; - CallGraph &CG = getAnalysis(); + SmallPtrSet SCCNodes; // Fill SCCNodes with the elements of the SCC. Used for quickly // looking up whether a given CallGraphNode is in this SCC. for (unsigned i = 0, e = SCC.size(); i != e; ++i) - SCCNodes.insert(SCC[i]); + SCCNodes.insert(SCC[i]->getFunction()); // Check if any of the functions in the SCC read or write memory. If they // write memory then they can't be marked readnone or readonly. @@ -126,10 +163,25 @@ bool FunctionAttrs::AddReadAttrs(const std::vector &SCC) { // Some instructions can be ignored even if they read or write memory. // Detect these now, skipping to the next instruction if one is found. CallSite CS = CallSite::get(I); - if (CS.getInstruction()) { + if (CS.getInstruction() && CS.getCalledFunction()) { // Ignore calls to functions in the same SCC. - if (SCCNodes.count(CG[CS.getCalledFunction()])) + if (SCCNodes.count(CS.getCalledFunction())) continue; + // Ignore intrinsics that only access local memory. + if (unsigned id = CS.getCalledFunction()->getIntrinsicID()) + if (AliasAnalysis::getModRefBehavior(id) == + AliasAnalysis::AccessesArguments) { + // Check that all pointer arguments point to local memory. + for (CallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end(); + CI != CE; ++CI) { + Value *Arg = *CI; + if (Arg->getType()->isPointerTy() && !PointsToLocalMemory(Arg)) + // Writes memory. Just give up. + return false; + } + // Only reads and writes local memory. + continue; + } } else if (LoadInst *LI = dyn_cast(I)) { // Ignore loads from local memory. if (PointsToLocalMemory(LI->getPointerOperand())) @@ -145,6 +197,11 @@ bool FunctionAttrs::AddReadAttrs(const std::vector &SCC) { if (I->mayWriteToMemory()) // Writes memory. Just give up. return false; + + if (isMalloc(I)) + // malloc claims not to write memory! PR3754. + return false; + // If this instruction may read memory, remember that. ReadsMemory |= I->mayReadFromMemory(); } @@ -181,135 +238,6 @@ bool FunctionAttrs::AddReadAttrs(const std::vector &SCC) { return MadeChange; } -/// isCaptured - Return true if this pointer value may be captured. -bool FunctionAttrs::isCaptured(Function &F, Value *V) { - typedef PointerIntPair UseWithDepth; - SmallVector Worklist; - SmallSet Visited; - - for (Value::use_iterator UI = V->use_begin(), UE = V->use_end(); UI != UE; - ++UI) { - UseWithDepth UD(&UI.getUse(), 0); - Visited.insert(UD); - Worklist.push_back(UD); - } - - while (!Worklist.empty()) { - UseWithDepth UD = Worklist.pop_back_val(); - Use *U = UD.getPointer(); - Instruction *I = cast(U->getUser()); - // The value V may have any type if it comes from tracking a load. - V = U->get(); - // The depth represents the number of loads that need to be performed to - // get back the original pointer (or a bitcast etc of it). For example, - // if the pointer is stored to an alloca, then all uses of the alloca get - // depth 1: if the alloca is loaded then you get the original pointer back. - // If a load of the alloca is returned then the pointer has been captured. - // The depth is needed in order to know which loads dereference the original - // pointer (these do not capture), and which return a value which needs to - // be tracked because if it is captured then so is the original pointer. - unsigned Depth = UD.getInt(); - - switch (I->getOpcode()) { - case Instruction::Store: - if (V == I->getOperand(0)) { - // Stored the pointer - it may be captured. If it is stored to a local - // object (alloca) then track that object. Otherwise give up. - Value *Target = I->getOperand(1)->getUnderlyingObject(); - if (!isa(Target)) - // Didn't store to an obviously local object - captured. - return true; - if (Depth >= 3) - // Alloca recursion too deep - give up. - return true; - // Analyze all uses of the alloca. - for (Value::use_iterator UI = Target->use_begin(), - UE = Target->use_end(); UI != UE; ++UI) { - UseWithDepth NUD(&UI.getUse(), Depth + 1); - if (Visited.insert(NUD)) - Worklist.push_back(NUD); - } - } - // Storing to the pointee does not cause the pointer to be captured. - break; - case Instruction::Free: - // Freeing a pointer does not cause it to be captured. - break; - case Instruction::Call: - case Instruction::Invoke: { - CallSite CS = CallSite::get(I); - // Not captured if the callee is readonly and doesn't return a copy - // through its return value. - if (CS.onlyReadsMemory() && I->getType() == Type::VoidTy) - break; - - // Not captured if only passed via 'nocapture' arguments. Note that - // calling a function pointer does not in itself cause the pointer to - // be captured. This is a subtle point considering that (for example) - // the callee might return its own address. It is analogous to saying - // that loading a value from a pointer does not cause the pointer to be - // captured, even though the loaded value might be the pointer itself - // (think of self-referential objects). - CallSite::arg_iterator B = CS.arg_begin(), E = CS.arg_end(); - for (CallSite::arg_iterator A = B; A != E; ++A) - if (A->get() == V && !CS.paramHasAttr(A - B + 1, Attribute::NoCapture)) - // The parameter is not marked 'nocapture' - captured. - return true; - // Only passed via 'nocapture' arguments, or is the called function - not - // captured. - break; - } - case Instruction::BitCast: - case Instruction::GetElementPtr: - case Instruction::Load: - case Instruction::PHI: - case Instruction::Select: - // Track any uses of this instruction to see if they are captured. - // First handle any special cases. - if (isa(I)) { - // Play safe and do not accept being used as an index. - if (V != I->getOperand(0)) - return true; - } else if (isa(I)) { - // Play safe and do not accept being used as the condition. - if (V == I->getOperand(0)) - return true; - } else if (isa(I)) { - // Usually loads can be ignored because they dereference the original - // pointer. However the loaded value needs to be tracked if loading - // from an object that the original pointer was stored to. - if (Depth == 0) - // Loading the original pointer or a variation of it. This does not - // cause the pointer to be captured. Note that the loaded value might - // be the pointer itself (think of self-referential objects), but that - // is fine as long as it's not this function that stored it there. - break; - // Loading a pointer to (a pointer to...) the original pointer or a - // variation of it. Track uses of the loaded value, noting that one - // dereference was performed. Note that the loaded value need not be - // of pointer type. For example, an alloca may have been bitcast to - // a pointer to another type, which was then loaded. - --Depth; - } - - // The original value is not captured via this if the instruction isn't. - for (Instruction::use_iterator UI = I->use_begin(), UE = I->use_end(); - UI != UE; ++UI) { - UseWithDepth UD(&UI.getUse(), Depth); - if (Visited.insert(UD)) - Worklist.push_back(UD); - } - break; - default: - // Something else - be conservative and say it is captured. - return true; - } - } - - // All uses examined - not captured. - return false; -} - /// AddNoCaptureAttrs - Deduce nocapture attributes for the SCC. bool FunctionAttrs::AddNoCaptureAttrs(const std::vector &SCC) { bool Changed = false; @@ -329,8 +257,8 @@ bool FunctionAttrs::AddNoCaptureAttrs(const std::vector &SCC) { continue; for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end(); A!=E; ++A) - if (isa(A->getType()) && !A->hasNoCaptureAttr() && - !isCaptured(*F, A)) { + if (A->getType()->isPointerTy() && !A->hasNoCaptureAttr() && + !PointerMayBeCaptured(A, true, /*StoreCaptures=*/false)) { A->addAttr(Attribute::NoCapture); ++NumNoCapture; Changed = true; @@ -340,8 +268,124 @@ bool FunctionAttrs::AddNoCaptureAttrs(const std::vector &SCC) { return Changed; } -bool FunctionAttrs::runOnSCC(const std::vector &SCC) { +/// IsFunctionMallocLike - A function is malloc-like if it returns either null +/// or a pointer that doesn't alias any other pointer visible to the caller. +bool FunctionAttrs::IsFunctionMallocLike(Function *F, + SmallPtrSet &SCCNodes) const { + UniqueVector FlowsToReturn; + for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) + if (ReturnInst *Ret = dyn_cast(I->getTerminator())) + FlowsToReturn.insert(Ret->getReturnValue()); + + for (unsigned i = 0; i != FlowsToReturn.size(); ++i) { + Value *RetVal = FlowsToReturn[i+1]; // UniqueVector[0] is reserved. + + if (Constant *C = dyn_cast(RetVal)) { + if (!C->isNullValue() && !isa(C)) + return false; + + continue; + } + + if (isa(RetVal)) + return false; + + if (Instruction *RVI = dyn_cast(RetVal)) + switch (RVI->getOpcode()) { + // Extend the analysis by looking upwards. + case Instruction::BitCast: + case Instruction::GetElementPtr: + FlowsToReturn.insert(RVI->getOperand(0)); + continue; + case Instruction::Select: { + SelectInst *SI = cast(RVI); + FlowsToReturn.insert(SI->getTrueValue()); + FlowsToReturn.insert(SI->getFalseValue()); + continue; + } + case Instruction::PHI: { + PHINode *PN = cast(RVI); + for (int i = 0, e = PN->getNumIncomingValues(); i != e; ++i) + FlowsToReturn.insert(PN->getIncomingValue(i)); + continue; + } + + // Check whether the pointer came from an allocation. + case Instruction::Alloca: + break; + case Instruction::Call: + case Instruction::Invoke: { + CallSite CS(RVI); + if (CS.paramHasAttr(0, Attribute::NoAlias)) + break; + if (CS.getCalledFunction() && + SCCNodes.count(CS.getCalledFunction())) + break; + } // fall-through + default: + return false; // Did not come from an allocation. + } + + if (PointerMayBeCaptured(RetVal, false, /*StoreCaptures=*/false)) + return false; + } + + return true; +} + +/// AddNoAliasAttrs - Deduce noalias attributes for the SCC. +bool FunctionAttrs::AddNoAliasAttrs(const std::vector &SCC) { + SmallPtrSet SCCNodes; + + // Fill SCCNodes with the elements of the SCC. Used for quickly + // looking up whether a given CallGraphNode is in this SCC. + for (unsigned i = 0, e = SCC.size(); i != e; ++i) + SCCNodes.insert(SCC[i]->getFunction()); + + // Check each function in turn, determining which functions return noalias + // pointers. + for (unsigned i = 0, e = SCC.size(); i != e; ++i) { + Function *F = SCC[i]->getFunction(); + + if (F == 0) + // External node - skip it; + return false; + + // Already noalias. + if (F->doesNotAlias(0)) + continue; + + // Definitions with weak linkage may be overridden at linktime, so + // treat them like declarations. + if (F->isDeclaration() || F->mayBeOverridden()) + return false; + + // We annotate noalias return values, which are only applicable to + // pointer types. + if (!F->getReturnType()->isPointerTy()) + continue; + + if (!IsFunctionMallocLike(F, SCCNodes)) + return false; + } + + bool MadeChange = false; + for (unsigned i = 0, e = SCC.size(); i != e; ++i) { + Function *F = SCC[i]->getFunction(); + if (F->doesNotAlias(0) || !F->getReturnType()->isPointerTy()) + continue; + + F->setDoesNotAlias(0); + ++NumNoAlias; + MadeChange = true; + } + + return MadeChange; +} + +bool FunctionAttrs::runOnSCC(std::vector &SCC) { bool Changed = AddReadAttrs(SCC); Changed |= AddNoCaptureAttrs(SCC); + Changed |= AddNoAliasAttrs(SCC); return Changed; }