X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=blobdiff_plain;f=lib%2FTransforms%2FIPO%2FFunctionAttrs.cpp;h=cfeedf6d1db999cfeefb66540f01a8f29523882e;hp=aabf623e0af5b5eab3c93d5bf7969dc7643c182f;hb=1f97273f8fb2e51080ef2c7a9cd867d0d0ccf8a0;hpb=0b8c9a80f20772c3793201ab5b251d3520b9cea3 diff --git a/lib/Transforms/IPO/FunctionAttrs.cpp b/lib/Transforms/IPO/FunctionAttrs.cpp index aabf623e0af..cfeedf6d1db 100644 --- a/lib/Transforms/IPO/FunctionAttrs.cpp +++ b/lib/Transforms/IPO/FunctionAttrs.cpp @@ -1,4 +1,4 @@ -//===- FunctionAttrs.cpp - Pass which marks functions readnone or readonly ===// +//===- FunctionAttrs.cpp - Pass which marks functions attributes ----------===// // // The LLVM Compiler Infrastructure // @@ -9,83 +9,90 @@ // // This file implements a simple interprocedural pass which walks the // call-graph, looking for functions which do not access or only read -// non-local memory, and marking them readnone/readonly. In addition, -// it marks function arguments (of pointer type) 'nocapture' if a call -// to the function does not create any copies of the pointer value that -// outlive the call. This more or less means that the pointer is only -// dereferenced, and not returned from the function or stored in a global. -// This pass is implemented as a bottom-up traversal of the call-graph. +// non-local memory, and marking them readnone/readonly. It does the +// same with function arguments independently, marking them readonly/ +// readnone/nocapture. Finally, well-known library call declarations +// are marked with all attributes that are consistent with the +// function's standard definition. This pass is implemented as a +// bottom-up traversal of the call-graph. // //===----------------------------------------------------------------------===// -#define DEBUG_TYPE "functionattrs" #include "llvm/Transforms/IPO.h" #include "llvm/ADT/SCCIterator.h" #include "llvm/ADT/SetVector.h" #include "llvm/ADT/SmallSet.h" #include "llvm/ADT/Statistic.h" #include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/Analysis/AssumptionCache.h" +#include "llvm/Analysis/BasicAliasAnalysis.h" #include "llvm/Analysis/CallGraph.h" +#include "llvm/Analysis/CallGraphSCCPass.h" #include "llvm/Analysis/CaptureTracking.h" -#include "llvm/CallGraphSCCPass.h" +#include "llvm/Analysis/TargetLibraryInfo.h" +#include "llvm/Analysis/ValueTracking.h" #include "llvm/IR/GlobalVariable.h" +#include "llvm/IR/InstIterator.h" #include "llvm/IR/IntrinsicInst.h" #include "llvm/IR/LLVMContext.h" -#include "llvm/Support/InstIterator.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/raw_ostream.h" +#include "llvm/Analysis/TargetLibraryInfo.h" using namespace llvm; +#define DEBUG_TYPE "functionattrs" + STATISTIC(NumReadNone, "Number of functions marked readnone"); STATISTIC(NumReadOnly, "Number of functions marked readonly"); STATISTIC(NumNoCapture, "Number of arguments marked nocapture"); +STATISTIC(NumReadNoneArg, "Number of arguments marked readnone"); +STATISTIC(NumReadOnlyArg, "Number of arguments marked readonly"); STATISTIC(NumNoAlias, "Number of function returns marked noalias"); +STATISTIC(NumNonNullReturn, "Number of function returns marked nonnull"); +STATISTIC(NumAnnotated, "Number of attributes added to library functions"); namespace { - struct FunctionAttrs : public CallGraphSCCPass { - static char ID; // Pass identification, replacement for typeid - FunctionAttrs() : CallGraphSCCPass(ID), AA(0) { - initializeFunctionAttrsPass(*PassRegistry::getPassRegistry()); - } - - // runOnSCC - Analyze the SCC, performing the transformation if possible. - bool runOnSCC(CallGraphSCC &SCC); - - // AddReadAttrs - Deduce readonly/readnone attributes for the SCC. - bool AddReadAttrs(const CallGraphSCC &SCC); - - // AddNoCaptureAttrs - Deduce nocapture attributes for the SCC. - bool AddNoCaptureAttrs(const CallGraphSCC &SCC); +struct FunctionAttrs : public CallGraphSCCPass { + static char ID; // Pass identification, replacement for typeid + FunctionAttrs() : CallGraphSCCPass(ID) { + initializeFunctionAttrsPass(*PassRegistry::getPassRegistry()); + } - // IsFunctionMallocLike - Does this function allocate new memory? - bool IsFunctionMallocLike(Function *F, - SmallPtrSet &) const; + bool runOnSCC(CallGraphSCC &SCC) override; - // AddNoAliasAttrs - Deduce noalias attributes for the SCC. - bool AddNoAliasAttrs(const CallGraphSCC &SCC); + void getAnalysisUsage(AnalysisUsage &AU) const override { + AU.setPreservesCFG(); + AU.addRequired(); + AU.addRequired(); + CallGraphSCCPass::getAnalysisUsage(AU); + } - virtual void getAnalysisUsage(AnalysisUsage &AU) const { - AU.setPreservesCFG(); - AU.addRequired(); - CallGraphSCCPass::getAnalysisUsage(AU); - } +private: + TargetLibraryInfo *TLI; - private: - AliasAnalysis *AA; - }; + bool AddReadAttrs(const CallGraphSCC &SCC); + bool AddArgumentAttrs(const CallGraphSCC &SCC); + bool IsFunctionMallocLike(Function *F, SmallPtrSet &) const; + bool AddNoAliasAttrs(const CallGraphSCC &SCC); + bool AddNonNullAttrs(const CallGraphSCC &SCC); + bool annotateLibraryCalls(const CallGraphSCC &SCC); +}; } char FunctionAttrs::ID = 0; INITIALIZE_PASS_BEGIN(FunctionAttrs, "functionattrs", - "Deduce function attributes", false, false) -INITIALIZE_AG_DEPENDENCY(CallGraph) + "Deduce function attributes", false, false) +INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) +INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass) +INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) INITIALIZE_PASS_END(FunctionAttrs, "functionattrs", - "Deduce function attributes", false, false) + "Deduce function attributes", false, false) Pass *llvm::createFunctionAttrsPass() { return new FunctionAttrs(); } - -/// AddReadAttrs - Deduce readonly/readnone attributes for the SCC. +/// Deduce readonly/readnone attributes for the SCC. bool FunctionAttrs::AddReadAttrs(const CallGraphSCC &SCC) { - SmallPtrSet SCCNodes; + SmallPtrSet SCCNodes; // Fill SCCNodes with the elements of the SCC. Used for quickly // looking up whether a given CallGraphNode is in this SCC. @@ -98,12 +105,21 @@ bool FunctionAttrs::AddReadAttrs(const CallGraphSCC &SCC) { for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) { Function *F = (*I)->getFunction(); - if (F == 0) - // External node - may write memory. Just give up. + if (!F || F->hasFnAttribute(Attribute::OptimizeNone)) + // External node or node we don't want to optimize - assume it may write + // memory and give up. return false; - AliasAnalysis::ModRefBehavior MRB = AA->getModRefBehavior(F); - if (MRB == AliasAnalysis::DoesNotAccessMemory) + // We need to manually construct BasicAA directly in order to disable its + // use of other function analyses. + BasicAAResult BAR(createLegacyPMBasicAAResult(*this, *F)); + + // Construct our own AA results for this function. We do this manually to + // work around the limitations of the legacy pass manager. + AAResults AAR(createLegacyPMAAResults(*this, *F, BAR)); + + FunctionModRefBehavior MRB = AAR.getModRefBehavior(F); + if (MRB == FMRB_DoesNotAccessMemory) // Already perfect! continue; @@ -129,7 +145,7 @@ bool FunctionAttrs::AddReadAttrs(const CallGraphSCC &SCC) { // Ignore calls to functions in the same SCC. if (CS.getCalledFunction() && SCCNodes.count(CS.getCalledFunction())) continue; - AliasAnalysis::ModRefBehavior MRB = AA->getModRefBehavior(CS); + FunctionModRefBehavior MRB = AAR.getModRefBehavior(CS); // If the call doesn't access arbitrary memory, we may be able to // figure out something. if (AliasAnalysis::onlyAccessesArgPointees(MRB)) { @@ -141,14 +157,15 @@ bool FunctionAttrs::AddReadAttrs(const CallGraphSCC &SCC) { CI != CE; ++CI) { Value *Arg = *CI; if (Arg->getType()->isPointerTy()) { - AliasAnalysis::Location Loc(Arg, - AliasAnalysis::UnknownSize, - I->getMetadata(LLVMContext::MD_tbaa)); - if (!AA->pointsToConstantMemory(Loc, /*OrLocal=*/true)) { - if (MRB & AliasAnalysis::Mod) + AAMDNodes AAInfo; + I->getAAMetadata(AAInfo); + + MemoryLocation Loc(Arg, MemoryLocation::UnknownSize, AAInfo); + if (!AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true)) { + if (MRB & MRI_Mod) // Writes non-local memory. Give up. return false; - if (MRB & AliasAnalysis::Ref) + if (MRB & MRI_Ref) // Ok, it reads non-local memory. ReadsMemory = true; } @@ -157,30 +174,30 @@ bool FunctionAttrs::AddReadAttrs(const CallGraphSCC &SCC) { continue; } // The call could access any memory. If that includes writes, give up. - if (MRB & AliasAnalysis::Mod) + if (MRB & MRI_Mod) return false; // If it reads, note it. - if (MRB & AliasAnalysis::Ref) + if (MRB & MRI_Ref) ReadsMemory = true; continue; } else if (LoadInst *LI = dyn_cast(I)) { // Ignore non-volatile loads from local memory. (Atomic is okay here.) if (!LI->isVolatile()) { - AliasAnalysis::Location Loc = AA->getLocation(LI); - if (AA->pointsToConstantMemory(Loc, /*OrLocal=*/true)) + MemoryLocation Loc = MemoryLocation::get(LI); + if (AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true)) continue; } } else if (StoreInst *SI = dyn_cast(I)) { // Ignore non-volatile stores to local memory. (Atomic is okay here.) if (!SI->isVolatile()) { - AliasAnalysis::Location Loc = AA->getLocation(SI); - if (AA->pointsToConstantMemory(Loc, /*OrLocal=*/true)) + MemoryLocation Loc = MemoryLocation::get(SI); + if (AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true)) continue; } } else if (VAArgInst *VI = dyn_cast(I)) { // Ignore vaargs on local memory. - AliasAnalysis::Location Loc = AA->getLocation(VI); - if (AA->pointsToConstantMemory(Loc, /*OrLocal=*/true)) + MemoryLocation Loc = MemoryLocation::get(VI); + if (AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true)) continue; } @@ -213,16 +230,14 @@ bool FunctionAttrs::AddReadAttrs(const CallGraphSCC &SCC) { // Clear out any existing attributes. AttrBuilder B; - B.addAttribute(Attribute::ReadOnly) - .addAttribute(Attribute::ReadNone); - F->removeAttribute(AttributeSet::FunctionIndex, - Attribute::get(F->getContext(), B)); + B.addAttribute(Attribute::ReadOnly).addAttribute(Attribute::ReadNone); + F->removeAttributes( + AttributeSet::FunctionIndex, + AttributeSet::get(F->getContext(), AttributeSet::FunctionIndex, B)); // Add in the new attribute. - B.clear(); - B.addAttribute(ReadsMemory ? Attribute::ReadOnly : Attribute::ReadNone); F->addAttribute(AttributeSet::FunctionIndex, - Attribute::get(F->getContext(), B)); + ReadsMemory ? Attribute::ReadOnly : Attribute::ReadNone); if (ReadsMemory) ++NumReadOnly; @@ -234,124 +249,237 @@ bool FunctionAttrs::AddReadAttrs(const CallGraphSCC &SCC) { } namespace { - // For a given pointer Argument, this retains a list of Arguments of functions - // in the same SCC that the pointer data flows into. We use this to build an - // SCC of the arguments. - struct ArgumentGraphNode { - Argument *Definition; - SmallVector Uses; - }; - - class ArgumentGraph { - // We store pointers to ArgumentGraphNode objects, so it's important that - // that they not move around upon insert. - typedef std::map ArgumentMapTy; - - ArgumentMapTy ArgumentMap; - - // There is no root node for the argument graph, in fact: - // void f(int *x, int *y) { if (...) f(x, y); } - // is an example where the graph is disconnected. The SCCIterator requires a - // single entry point, so we maintain a fake ("synthetic") root node that - // uses every node. Because the graph is directed and nothing points into - // the root, it will not participate in any SCCs (except for its own). - ArgumentGraphNode SyntheticRoot; - - public: - ArgumentGraph() { SyntheticRoot.Definition = 0; } - - typedef SmallVectorImpl::iterator iterator; - - iterator begin() { return SyntheticRoot.Uses.begin(); } - iterator end() { return SyntheticRoot.Uses.end(); } - ArgumentGraphNode *getEntryNode() { return &SyntheticRoot; } - - ArgumentGraphNode *operator[](Argument *A) { - ArgumentGraphNode &Node = ArgumentMap[A]; - Node.Definition = A; - SyntheticRoot.Uses.push_back(&Node); - return &Node; - } - }; +/// For a given pointer Argument, this retains a list of Arguments of functions +/// in the same SCC that the pointer data flows into. We use this to build an +/// SCC of the arguments. +struct ArgumentGraphNode { + Argument *Definition; + SmallVector Uses; +}; + +class ArgumentGraph { + // We store pointers to ArgumentGraphNode objects, so it's important that + // that they not move around upon insert. + typedef std::map ArgumentMapTy; + + ArgumentMapTy ArgumentMap; + + // There is no root node for the argument graph, in fact: + // void f(int *x, int *y) { if (...) f(x, y); } + // is an example where the graph is disconnected. The SCCIterator requires a + // single entry point, so we maintain a fake ("synthetic") root node that + // uses every node. Because the graph is directed and nothing points into + // the root, it will not participate in any SCCs (except for its own). + ArgumentGraphNode SyntheticRoot; + +public: + ArgumentGraph() { SyntheticRoot.Definition = nullptr; } + + typedef SmallVectorImpl::iterator iterator; + + iterator begin() { return SyntheticRoot.Uses.begin(); } + iterator end() { return SyntheticRoot.Uses.end(); } + ArgumentGraphNode *getEntryNode() { return &SyntheticRoot; } + + ArgumentGraphNode *operator[](Argument *A) { + ArgumentGraphNode &Node = ArgumentMap[A]; + Node.Definition = A; + SyntheticRoot.Uses.push_back(&Node); + return &Node; + } +}; - // This tracker checks whether callees are in the SCC, and if so it does not - // consider that a capture, instead adding it to the "Uses" list and - // continuing with the analysis. - struct ArgumentUsesTracker : public CaptureTracker { - ArgumentUsesTracker(const SmallPtrSet &SCCNodes) +/// This tracker checks whether callees are in the SCC, and if so it does not +/// consider that a capture, instead adding it to the "Uses" list and +/// continuing with the analysis. +struct ArgumentUsesTracker : public CaptureTracker { + ArgumentUsesTracker(const SmallPtrSet &SCCNodes) : Captured(false), SCCNodes(SCCNodes) {} - void tooManyUses() { Captured = true; } + void tooManyUses() override { Captured = true; } - bool captured(Use *U) { - CallSite CS(U->getUser()); - if (!CS.getInstruction()) { Captured = true; return true; } + bool captured(const Use *U) override { + CallSite CS(U->getUser()); + if (!CS.getInstruction()) { + Captured = true; + return true; + } - Function *F = CS.getCalledFunction(); - if (!F || !SCCNodes.count(F)) { Captured = true; return true; } + Function *F = CS.getCalledFunction(); + if (!F || !SCCNodes.count(F)) { + Captured = true; + return true; + } - Function::arg_iterator AI = F->arg_begin(), AE = F->arg_end(); - for (CallSite::arg_iterator PI = CS.arg_begin(), PE = CS.arg_end(); - PI != PE; ++PI, ++AI) { - if (AI == AE) { - assert(F->isVarArg() && "More params than args in non-varargs call"); - Captured = true; - return true; - } - if (PI == U) { - Uses.push_back(AI); - break; - } + bool Found = false; + Function::arg_iterator AI = F->arg_begin(), AE = F->arg_end(); + for (CallSite::arg_iterator PI = CS.arg_begin(), PE = CS.arg_end(); + PI != PE; ++PI, ++AI) { + if (AI == AE) { + assert(F->isVarArg() && "More params than args in non-varargs call"); + Captured = true; + return true; + } + if (PI == U) { + Uses.push_back(AI); + Found = true; + break; } - assert(!Uses.empty() && "Capturing call-site captured nothing?"); - return false; } + assert(Found && "Capturing call-site captured nothing?"); + (void)Found; + return false; + } - bool Captured; // True only if certainly captured (used outside our SCC). - SmallVector Uses; // Uses within our SCC. + bool Captured; // True only if certainly captured (used outside our SCC). + SmallVector Uses; // Uses within our SCC. - const SmallPtrSet &SCCNodes; - }; + const SmallPtrSet &SCCNodes; +}; } namespace llvm { - template<> struct GraphTraits { - typedef ArgumentGraphNode NodeType; - typedef SmallVectorImpl::iterator ChildIteratorType; +template <> struct GraphTraits { + typedef ArgumentGraphNode NodeType; + typedef SmallVectorImpl::iterator ChildIteratorType; - static inline NodeType *getEntryNode(NodeType *A) { return A; } - static inline ChildIteratorType child_begin(NodeType *N) { - return N->Uses.begin(); - } - static inline ChildIteratorType child_end(NodeType *N) { - return N->Uses.end(); - } - }; - template<> struct GraphTraits - : public GraphTraits { - static NodeType *getEntryNode(ArgumentGraph *AG) { - return AG->getEntryNode(); - } - static ChildIteratorType nodes_begin(ArgumentGraph *AG) { - return AG->begin(); + static inline NodeType *getEntryNode(NodeType *A) { return A; } + static inline ChildIteratorType child_begin(NodeType *N) { + return N->Uses.begin(); + } + static inline ChildIteratorType child_end(NodeType *N) { + return N->Uses.end(); + } +}; +template <> +struct GraphTraits : public GraphTraits { + static NodeType *getEntryNode(ArgumentGraph *AG) { + return AG->getEntryNode(); + } + static ChildIteratorType nodes_begin(ArgumentGraph *AG) { + return AG->begin(); + } + static ChildIteratorType nodes_end(ArgumentGraph *AG) { return AG->end(); } +}; +} + +/// Returns Attribute::None, Attribute::ReadOnly or Attribute::ReadNone. +static Attribute::AttrKind +determinePointerReadAttrs(Argument *A, + const SmallPtrSet &SCCNodes) { + + SmallVector Worklist; + SmallSet Visited; + + // inalloca arguments are always clobbered by the call. + if (A->hasInAllocaAttr()) + return Attribute::None; + + bool IsRead = false; + // We don't need to track IsWritten. If A is written to, return immediately. + + for (Use &U : A->uses()) { + Visited.insert(&U); + Worklist.push_back(&U); + } + + while (!Worklist.empty()) { + Use *U = Worklist.pop_back_val(); + Instruction *I = cast(U->getUser()); + Value *V = U->get(); + + switch (I->getOpcode()) { + case Instruction::BitCast: + case Instruction::GetElementPtr: + case Instruction::PHI: + case Instruction::Select: + case Instruction::AddrSpaceCast: + // The original value is not read/written via this if the new value isn't. + for (Use &UU : I->uses()) + if (Visited.insert(&UU).second) + Worklist.push_back(&UU); + break; + + case Instruction::Call: + case Instruction::Invoke: { + bool Captures = true; + + if (I->getType()->isVoidTy()) + Captures = false; + + auto AddUsersToWorklistIfCapturing = [&] { + if (Captures) + for (Use &UU : I->uses()) + if (Visited.insert(&UU).second) + Worklist.push_back(&UU); + }; + + CallSite CS(I); + if (CS.doesNotAccessMemory()) { + AddUsersToWorklistIfCapturing(); + continue; + } + + Function *F = CS.getCalledFunction(); + if (!F) { + if (CS.onlyReadsMemory()) { + IsRead = true; + AddUsersToWorklistIfCapturing(); + continue; + } + return Attribute::None; + } + + Function::arg_iterator AI = F->arg_begin(), AE = F->arg_end(); + CallSite::arg_iterator B = CS.arg_begin(), E = CS.arg_end(); + for (CallSite::arg_iterator A = B; A != E; ++A, ++AI) { + if (A->get() == V) { + if (AI == AE) { + assert(F->isVarArg() && + "More params than args in non-varargs call."); + return Attribute::None; + } + Captures &= !CS.doesNotCapture(A - B); + if (SCCNodes.count(AI)) + continue; + if (!CS.onlyReadsMemory() && !CS.onlyReadsMemory(A - B)) + return Attribute::None; + if (!CS.doesNotAccessMemory(A - B)) + IsRead = true; + } + } + AddUsersToWorklistIfCapturing(); + break; } - static ChildIteratorType nodes_end(ArgumentGraph *AG) { - return AG->end(); + + case Instruction::Load: + IsRead = true; + break; + + case Instruction::ICmp: + case Instruction::Ret: + break; + + default: + return Attribute::None; } - }; + } + + return IsRead ? Attribute::ReadOnly : Attribute::ReadNone; } -/// AddNoCaptureAttrs - Deduce nocapture attributes for the SCC. -bool FunctionAttrs::AddNoCaptureAttrs(const CallGraphSCC &SCC) { +/// Deduce nocapture attributes for the SCC. +bool FunctionAttrs::AddArgumentAttrs(const CallGraphSCC &SCC) { bool Changed = false; - SmallPtrSet SCCNodes; + SmallPtrSet SCCNodes; // Fill SCCNodes with the elements of the SCC. Used for quickly // looking up whether a given CallGraphNode is in this SCC. for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) { Function *F = (*I)->getFunction(); - if (F && !F->isDeclaration() && !F->mayBeOverridden()) + if (F && !F->isDeclaration() && !F->mayBeOverridden() && + !F->hasFnAttribute(Attribute::OptimizeNone)) SCCNodes.insert(F); } @@ -365,8 +493,9 @@ bool FunctionAttrs::AddNoCaptureAttrs(const CallGraphSCC &SCC) { for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) { Function *F = (*I)->getFunction(); - if (F == 0) - // External node - only a problem for arguments that we pass to it. + if (!F || F->hasFnAttribute(Attribute::OptimizeNone)) + // External node or function we're trying not to optimize - only a problem + // for arguments that we pass to it. continue; // Definitions with weak linkage may be overridden at linktime with @@ -378,10 +507,10 @@ bool FunctionAttrs::AddNoCaptureAttrs(const CallGraphSCC &SCC) { // a value can't capture arguments. Don't analyze them. if (F->onlyReadsMemory() && F->doesNotThrow() && F->getReturnType()->isVoidTy()) { - for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end(); - A != E; ++A) { + for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end(); A != E; + ++A) { if (A->getType()->isPointerTy() && !A->hasNoCaptureAttr()) { - A->addAttr(Attribute::get(F->getContext(), B)); + A->addAttr(AttributeSet::get(F->getContext(), A->getArgNo() + 1, B)); ++NumNoCapture; Changed = true; } @@ -389,14 +518,19 @@ bool FunctionAttrs::AddNoCaptureAttrs(const CallGraphSCC &SCC) { continue; } - for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end(); A!=E; ++A) - if (A->getType()->isPointerTy() && !A->hasNoCaptureAttr()) { + for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end(); A != E; + ++A) { + if (!A->getType()->isPointerTy()) + continue; + bool HasNonLocalUses = false; + if (!A->hasNoCaptureAttr()) { ArgumentUsesTracker Tracker(SCCNodes); PointerMayBeCaptured(A, &Tracker); if (!Tracker.Captured) { if (Tracker.Uses.empty()) { // If it's trivially not captured, mark it nocapture now. - A->addAttr(Attribute::get(F->getContext(), B)); + A->addAttr( + AttributeSet::get(F->getContext(), A->getArgNo() + 1, B)); ++NumNoCapture; Changed = true; } else { @@ -404,13 +538,35 @@ bool FunctionAttrs::AddNoCaptureAttrs(const CallGraphSCC &SCC) { // then it must be calling into another function in our SCC. Save // its particulars for Argument-SCC analysis later. ArgumentGraphNode *Node = AG[A]; - for (SmallVectorImpl::iterator UI = Tracker.Uses.begin(), - UE = Tracker.Uses.end(); UI != UE; ++UI) + for (SmallVectorImpl::iterator + UI = Tracker.Uses.begin(), + UE = Tracker.Uses.end(); + UI != UE; ++UI) { Node->Uses.push_back(AG[*UI]); + if (*UI != A) + HasNonLocalUses = true; + } } } // Otherwise, it's captured. Don't bother doing SCC analysis on it. } + if (!HasNonLocalUses && !A->onlyReadsMemory()) { + // Can we determine that it's readonly/readnone without doing an SCC? + // Note that we don't allow any calls at all here, or else our result + // will be dependent on the iteration order through the functions in the + // SCC. + SmallPtrSet Self; + Self.insert(A); + Attribute::AttrKind R = determinePointerReadAttrs(A, Self); + if (R != Attribute::None) { + AttrBuilder B; + B.addAttribute(R); + A->addAttr(AttributeSet::get(A->getContext(), A->getArgNo() + 1, B)); + Changed = true; + R == Attribute::ReadOnly ? ++NumReadOnlyArg : ++NumReadNoneArg; + } + } + } } // The graph we've collected is partial because we stopped scanning for @@ -420,18 +576,17 @@ bool FunctionAttrs::AddNoCaptureAttrs(const CallGraphSCC &SCC) { // made. If the definition doesn't have a 'nocapture' attribute by now, it // captures. - for (scc_iterator I = scc_begin(&AG), E = scc_end(&AG); - I != E; ++I) { - std::vector &ArgumentSCC = *I; + for (scc_iterator I = scc_begin(&AG); !I.isAtEnd(); ++I) { + const std::vector &ArgumentSCC = *I; if (ArgumentSCC.size() == 1) { - if (!ArgumentSCC[0]->Definition) continue; // synthetic root node + if (!ArgumentSCC[0]->Definition) + continue; // synthetic root node // eg. "void f(int* x) { if (...) f(x); }" if (ArgumentSCC[0]->Uses.size() == 1 && ArgumentSCC[0]->Uses[0] == ArgumentSCC[0]) { - ArgumentSCC[0]-> - Definition-> - addAttr(Attribute::get(ArgumentSCC[0]->Definition->getContext(), B)); + Argument *A = ArgumentSCC[0]->Definition; + A->addAttr(AttributeSet::get(A->getContext(), A->getArgNo() + 1, B)); ++NumNoCapture; Changed = true; } @@ -439,29 +594,30 @@ bool FunctionAttrs::AddNoCaptureAttrs(const CallGraphSCC &SCC) { } bool SCCCaptured = false; - for (std::vector::iterator I = ArgumentSCC.begin(), - E = ArgumentSCC.end(); I != E && !SCCCaptured; ++I) { + for (auto I = ArgumentSCC.begin(), E = ArgumentSCC.end(); + I != E && !SCCCaptured; ++I) { ArgumentGraphNode *Node = *I; if (Node->Uses.empty()) { if (!Node->Definition->hasNoCaptureAttr()) SCCCaptured = true; } } - if (SCCCaptured) continue; + if (SCCCaptured) + continue; - SmallPtrSet ArgumentSCCNodes; + SmallPtrSet ArgumentSCCNodes; // Fill ArgumentSCCNodes with the elements of the ArgumentSCC. Used for // quickly looking up whether a given Argument is in this ArgumentSCC. - for (std::vector::iterator I = ArgumentSCC.begin(), - E = ArgumentSCC.end(); I != E; ++I) { + for (auto I = ArgumentSCC.begin(), E = ArgumentSCC.end(); I != E; ++I) { ArgumentSCCNodes.insert((*I)->Definition); } - for (std::vector::iterator I = ArgumentSCC.begin(), - E = ArgumentSCC.end(); I != E && !SCCCaptured; ++I) { + for (auto I = ArgumentSCC.begin(), E = ArgumentSCC.end(); + I != E && !SCCCaptured; ++I) { ArgumentGraphNode *N = *I; - for (SmallVectorImpl::iterator UI = N->Uses.begin(), - UE = N->Uses.end(); UI != UE; ++UI) { + for (SmallVectorImpl::iterator UI = N->Uses.begin(), + UE = N->Uses.end(); + UI != UE; ++UI) { Argument *A = (*UI)->Definition; if (A->hasNoCaptureAttr() || ArgumentSCCNodes.count(A)) continue; @@ -469,23 +625,65 @@ bool FunctionAttrs::AddNoCaptureAttrs(const CallGraphSCC &SCC) { break; } } - if (SCCCaptured) continue; + if (SCCCaptured) + continue; for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) { Argument *A = ArgumentSCC[i]->Definition; - A->addAttr(Attribute::get(A->getContext(), B)); + A->addAttr(AttributeSet::get(A->getContext(), A->getArgNo() + 1, B)); ++NumNoCapture; Changed = true; } + + // We also want to compute readonly/readnone. With a small number of false + // negatives, we can assume that any pointer which is captured isn't going + // to be provably readonly or readnone, since by definition we can't + // analyze all uses of a captured pointer. + // + // The false negatives happen when the pointer is captured by a function + // that promises readonly/readnone behaviour on the pointer, then the + // pointer's lifetime ends before anything that writes to arbitrary memory. + // Also, a readonly/readnone pointer may be returned, but returning a + // pointer is capturing it. + + Attribute::AttrKind ReadAttr = Attribute::ReadNone; + for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) { + Argument *A = ArgumentSCC[i]->Definition; + Attribute::AttrKind K = determinePointerReadAttrs(A, ArgumentSCCNodes); + if (K == Attribute::ReadNone) + continue; + if (K == Attribute::ReadOnly) { + ReadAttr = Attribute::ReadOnly; + continue; + } + ReadAttr = K; + break; + } + + if (ReadAttr != Attribute::None) { + AttrBuilder B, R; + B.addAttribute(ReadAttr); + R.addAttribute(Attribute::ReadOnly).addAttribute(Attribute::ReadNone); + for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) { + Argument *A = ArgumentSCC[i]->Definition; + // Clear out existing readonly/readnone attributes + A->removeAttr(AttributeSet::get(A->getContext(), A->getArgNo() + 1, R)); + A->addAttr(AttributeSet::get(A->getContext(), A->getArgNo() + 1, B)); + ReadAttr == Attribute::ReadOnly ? ++NumReadOnlyArg : ++NumReadNoneArg; + Changed = true; + } + } } return Changed; } -/// 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 { +/// Tests whether a function is "malloc-like". +/// +/// 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 { SmallSetVector FlowsToReturn; for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) if (ReturnInst *Ret = dyn_cast(I->getTerminator())) @@ -506,38 +704,38 @@ bool FunctionAttrs::IsFunctionMallocLike(Function *F, 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; - } + // Extend the analysis by looking upwards. + case Instruction::BitCast: + case Instruction::GetElementPtr: + case Instruction::AddrSpaceCast: + 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 (Value *IncValue : PN->incoming_values()) + FlowsToReturn.insert(IncValue); + continue; + } - // Check whether the pointer came from an allocation. - case Instruction::Alloca: + // 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; - 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. + } // fall-through + default: + return false; // Did not come from an allocation. } if (PointerMayBeCaptured(RetVal, false, /*StoreCaptures=*/false)) @@ -547,9 +745,9 @@ bool FunctionAttrs::IsFunctionMallocLike(Function *F, return true; } -/// AddNoAliasAttrs - Deduce noalias attributes for the SCC. +/// Deduce noalias attributes for the SCC. bool FunctionAttrs::AddNoAliasAttrs(const CallGraphSCC &SCC) { - SmallPtrSet SCCNodes; + SmallPtrSet SCCNodes; // Fill SCCNodes with the elements of the SCC. Used for quickly // looking up whether a given CallGraphNode is in this SCC. @@ -561,8 +759,8 @@ bool FunctionAttrs::AddNoAliasAttrs(const CallGraphSCC &SCC) { for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) { Function *F = (*I)->getFunction(); - if (F == 0) - // External node - skip it; + if (!F || F->hasFnAttribute(Attribute::OptimizeNone)) + // External node or node we don't want to optimize - skip it; return false; // Already noalias. @@ -574,7 +772,7 @@ bool FunctionAttrs::AddNoAliasAttrs(const CallGraphSCC &SCC) { if (F->isDeclaration() || F->mayBeOverridden()) return false; - // We annotate noalias return values, which are only applicable to + // We annotate noalias return values, which are only applicable to // pointer types. if (!F->getReturnType()->isPointerTy()) continue; @@ -597,11 +795,1018 @@ bool FunctionAttrs::AddNoAliasAttrs(const CallGraphSCC &SCC) { return MadeChange; } +/// Tests whether this function is known to not return null. +/// +/// Requires that the function returns a pointer. +/// +/// Returns true if it believes the function will not return a null, and sets +/// \p Speculative based on whether the returned conclusion is a speculative +/// conclusion due to SCC calls. +static bool isReturnNonNull(Function *F, SmallPtrSet &SCCNodes, + const TargetLibraryInfo &TLI, bool &Speculative) { + assert(F->getReturnType()->isPointerTy() && + "nonnull only meaningful on pointer types"); + Speculative = false; + + SmallSetVector FlowsToReturn; + for (BasicBlock &BB : *F) + if (auto *Ret = dyn_cast(BB.getTerminator())) + FlowsToReturn.insert(Ret->getReturnValue()); + + for (unsigned i = 0; i != FlowsToReturn.size(); ++i) { + Value *RetVal = FlowsToReturn[i]; + + // If this value is locally known to be non-null, we're good + if (isKnownNonNull(RetVal, &TLI)) + continue; + + // Otherwise, we need to look upwards since we can't make any local + // conclusions. + Instruction *RVI = dyn_cast(RetVal); + if (!RVI) + return false; + switch (RVI->getOpcode()) { + // Extend the analysis by looking upwards. + case Instruction::BitCast: + case Instruction::GetElementPtr: + case Instruction::AddrSpaceCast: + 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; + } + case Instruction::Call: + case Instruction::Invoke: { + CallSite CS(RVI); + Function *Callee = CS.getCalledFunction(); + // A call to a node within the SCC is assumed to return null until + // proven otherwise + if (Callee && SCCNodes.count(Callee)) { + Speculative = true; + continue; + } + return false; + } + default: + return false; // Unknown source, may be null + }; + llvm_unreachable("should have either continued or returned"); + } + + return true; +} + +/// Deduce nonnull attributes for the SCC. +bool FunctionAttrs::AddNonNullAttrs(const CallGraphSCC &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 (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) + SCCNodes.insert((*I)->getFunction()); + + // Speculative that all functions in the SCC return only nonnull + // pointers. We may refute this as we analyze functions. + bool SCCReturnsNonNull = true; + + bool MadeChange = false; + + // Check each function in turn, determining which functions return nonnull + // pointers. + for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) { + Function *F = (*I)->getFunction(); + + if (!F || F->hasFnAttribute(Attribute::OptimizeNone)) + // External node or node we don't want to optimize - skip it; + return false; + + // Already nonnull. + if (F->getAttributes().hasAttribute(AttributeSet::ReturnIndex, + Attribute::NonNull)) + continue; + + // Definitions with weak linkage may be overridden at linktime, so + // treat them like declarations. + if (F->isDeclaration() || F->mayBeOverridden()) + return false; + + // We annotate nonnull return values, which are only applicable to + // pointer types. + if (!F->getReturnType()->isPointerTy()) + continue; + + bool Speculative = false; + if (isReturnNonNull(F, SCCNodes, *TLI, Speculative)) { + if (!Speculative) { + // Mark the function eagerly since we may discover a function + // which prevents us from speculating about the entire SCC + DEBUG(dbgs() << "Eagerly marking " << F->getName() << " as nonnull\n"); + F->addAttribute(AttributeSet::ReturnIndex, Attribute::NonNull); + ++NumNonNullReturn; + MadeChange = true; + } + continue; + } + // At least one function returns something which could be null, can't + // speculate any more. + SCCReturnsNonNull = false; + } + + if (SCCReturnsNonNull) { + for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) { + Function *F = (*I)->getFunction(); + if (F->getAttributes().hasAttribute(AttributeSet::ReturnIndex, + Attribute::NonNull) || + !F->getReturnType()->isPointerTy()) + continue; + + DEBUG(dbgs() << "SCC marking " << F->getName() << " as nonnull\n"); + F->addAttribute(AttributeSet::ReturnIndex, Attribute::NonNull); + ++NumNonNullReturn; + MadeChange = true; + } + } + + return MadeChange; +} + +static void setDoesNotAccessMemory(Function &F) { + if (!F.doesNotAccessMemory()) { + F.setDoesNotAccessMemory(); + ++NumAnnotated; + } +} + +static void setOnlyReadsMemory(Function &F) { + if (!F.onlyReadsMemory()) { + F.setOnlyReadsMemory(); + ++NumAnnotated; + } +} + +static void setDoesNotThrow(Function &F) { + if (!F.doesNotThrow()) { + F.setDoesNotThrow(); + ++NumAnnotated; + } +} + +static void setDoesNotCapture(Function &F, unsigned n) { + if (!F.doesNotCapture(n)) { + F.setDoesNotCapture(n); + ++NumAnnotated; + } +} + +static void setOnlyReadsMemory(Function &F, unsigned n) { + if (!F.onlyReadsMemory(n)) { + F.setOnlyReadsMemory(n); + ++NumAnnotated; + } +} + +static void setDoesNotAlias(Function &F, unsigned n) { + if (!F.doesNotAlias(n)) { + F.setDoesNotAlias(n); + ++NumAnnotated; + } +} + +/// Analyze the name and prototype of the given function and set any applicable +/// attributes. +/// +/// Returns true if any attributes were set and false otherwise. +static bool inferPrototypeAttributes(Function &F, const TargetLibraryInfo &TLI) { + if (F.hasFnAttribute(Attribute::OptimizeNone)) + return false; + + FunctionType *FTy = F.getFunctionType(); + LibFunc::Func TheLibFunc; + if (!(TLI.getLibFunc(F.getName(), TheLibFunc) && TLI.has(TheLibFunc))) + return false; + + switch (TheLibFunc) { + case LibFunc::strlen: + if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy()) + return false; + setOnlyReadsMemory(F); + setDoesNotThrow(F); + setDoesNotCapture(F, 1); + break; + case LibFunc::strchr: + case LibFunc::strrchr: + if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy() || + !FTy->getParamType(1)->isIntegerTy()) + return false; + setOnlyReadsMemory(F); + setDoesNotThrow(F); + break; + case LibFunc::strtol: + case LibFunc::strtod: + case LibFunc::strtof: + case LibFunc::strtoul: + case LibFunc::strtoll: + case LibFunc::strtold: + case LibFunc::strtoull: + if (FTy->getNumParams() < 2 || !FTy->getParamType(1)->isPointerTy()) + return false; + setDoesNotThrow(F); + setDoesNotCapture(F, 2); + setOnlyReadsMemory(F, 1); + break; + case LibFunc::strcpy: + case LibFunc::stpcpy: + case LibFunc::strcat: + case LibFunc::strncat: + case LibFunc::strncpy: + case LibFunc::stpncpy: + if (FTy->getNumParams() < 2 || !FTy->getParamType(1)->isPointerTy()) + return false; + setDoesNotThrow(F); + setDoesNotCapture(F, 2); + setOnlyReadsMemory(F, 2); + break; + case LibFunc::strxfrm: + if (FTy->getNumParams() != 3 || !FTy->getParamType(0)->isPointerTy() || + !FTy->getParamType(1)->isPointerTy()) + return false; + setDoesNotThrow(F); + setDoesNotCapture(F, 1); + setDoesNotCapture(F, 2); + setOnlyReadsMemory(F, 2); + break; + case LibFunc::strcmp: // 0,1 + case LibFunc::strspn: // 0,1 + case LibFunc::strncmp: // 0,1 + case LibFunc::strcspn: // 0,1 + case LibFunc::strcoll: // 0,1 + case LibFunc::strcasecmp: // 0,1 + case LibFunc::strncasecmp: // + if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy() || + !FTy->getParamType(1)->isPointerTy()) + return false; + setOnlyReadsMemory(F); + setDoesNotThrow(F); + setDoesNotCapture(F, 1); + setDoesNotCapture(F, 2); + break; + case LibFunc::strstr: + case LibFunc::strpbrk: + if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy()) + return false; + setOnlyReadsMemory(F); + setDoesNotThrow(F); + setDoesNotCapture(F, 2); + break; + case LibFunc::strtok: + case LibFunc::strtok_r: + if (FTy->getNumParams() < 2 || !FTy->getParamType(1)->isPointerTy()) + return false; + setDoesNotThrow(F); + setDoesNotCapture(F, 2); + setOnlyReadsMemory(F, 2); + break; + case LibFunc::scanf: + if (FTy->getNumParams() < 1 || !FTy->getParamType(0)->isPointerTy()) + return false; + setDoesNotThrow(F); + setDoesNotCapture(F, 1); + setOnlyReadsMemory(F, 1); + break; + case LibFunc::setbuf: + case LibFunc::setvbuf: + if (FTy->getNumParams() < 1 || !FTy->getParamType(0)->isPointerTy()) + return false; + setDoesNotThrow(F); + setDoesNotCapture(F, 1); + break; + case LibFunc::strdup: + case LibFunc::strndup: + if (FTy->getNumParams() < 1 || !FTy->getReturnType()->isPointerTy() || + !FTy->getParamType(0)->isPointerTy()) + return false; + setDoesNotThrow(F); + setDoesNotAlias(F, 0); + setDoesNotCapture(F, 1); + setOnlyReadsMemory(F, 1); + break; + case LibFunc::stat: + case LibFunc::statvfs: + if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy() || + !FTy->getParamType(1)->isPointerTy()) + return false; + setDoesNotThrow(F); + setDoesNotCapture(F, 1); + setDoesNotCapture(F, 2); + setOnlyReadsMemory(F, 1); + break; + case LibFunc::sscanf: + if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy() || + !FTy->getParamType(1)->isPointerTy()) + return false; + setDoesNotThrow(F); + setDoesNotCapture(F, 1); + setDoesNotCapture(F, 2); + setOnlyReadsMemory(F, 1); + setOnlyReadsMemory(F, 2); + break; + case LibFunc::sprintf: + if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy() || + !FTy->getParamType(1)->isPointerTy()) + return false; + setDoesNotThrow(F); + setDoesNotCapture(F, 1); + setDoesNotCapture(F, 2); + setOnlyReadsMemory(F, 2); + break; + case LibFunc::snprintf: + if (FTy->getNumParams() != 3 || !FTy->getParamType(0)->isPointerTy() || + !FTy->getParamType(2)->isPointerTy()) + return false; + setDoesNotThrow(F); + setDoesNotCapture(F, 1); + setDoesNotCapture(F, 3); + setOnlyReadsMemory(F, 3); + break; + case LibFunc::setitimer: + if (FTy->getNumParams() != 3 || !FTy->getParamType(1)->isPointerTy() || + !FTy->getParamType(2)->isPointerTy()) + return false; + setDoesNotThrow(F); + setDoesNotCapture(F, 2); + setDoesNotCapture(F, 3); + setOnlyReadsMemory(F, 2); + break; + case LibFunc::system: + if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy()) + return false; + // May throw; "system" is a valid pthread cancellation point. + setDoesNotCapture(F, 1); + setOnlyReadsMemory(F, 1); + break; + case LibFunc::malloc: + if (FTy->getNumParams() != 1 || !FTy->getReturnType()->isPointerTy()) + return false; + setDoesNotThrow(F); + setDoesNotAlias(F, 0); + break; + case LibFunc::memcmp: + if (FTy->getNumParams() != 3 || !FTy->getParamType(0)->isPointerTy() || + !FTy->getParamType(1)->isPointerTy()) + return false; + setOnlyReadsMemory(F); + setDoesNotThrow(F); + setDoesNotCapture(F, 1); + setDoesNotCapture(F, 2); + break; + case LibFunc::memchr: + case LibFunc::memrchr: + if (FTy->getNumParams() != 3) + return false; + setOnlyReadsMemory(F); + setDoesNotThrow(F); + break; + case LibFunc::modf: + case LibFunc::modff: + case LibFunc::modfl: + if (FTy->getNumParams() < 2 || !FTy->getParamType(1)->isPointerTy()) + return false; + setDoesNotThrow(F); + setDoesNotCapture(F, 2); + break; + case LibFunc::memcpy: + case LibFunc::memccpy: + case LibFunc::memmove: + if (FTy->getNumParams() < 2 || !FTy->getParamType(1)->isPointerTy()) + return false; + setDoesNotThrow(F); + setDoesNotCapture(F, 2); + setOnlyReadsMemory(F, 2); + break; + case LibFunc::memalign: + if (!FTy->getReturnType()->isPointerTy()) + return false; + setDoesNotAlias(F, 0); + break; + case LibFunc::mkdir: + if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy()) + return false; + setDoesNotThrow(F); + setDoesNotCapture(F, 1); + setOnlyReadsMemory(F, 1); + break; + case LibFunc::mktime: + if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy()) + return false; + setDoesNotThrow(F); + setDoesNotCapture(F, 1); + break; + case LibFunc::realloc: + if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy() || + !FTy->getReturnType()->isPointerTy()) + return false; + setDoesNotThrow(F); + setDoesNotAlias(F, 0); + setDoesNotCapture(F, 1); + break; + case LibFunc::read: + if (FTy->getNumParams() != 3 || !FTy->getParamType(1)->isPointerTy()) + return false; + // May throw; "read" is a valid pthread cancellation point. + setDoesNotCapture(F, 2); + break; + case LibFunc::rewind: + if (FTy->getNumParams() < 1 || !FTy->getParamType(0)->isPointerTy()) + return false; + setDoesNotThrow(F); + setDoesNotCapture(F, 1); + break; + case LibFunc::rmdir: + case LibFunc::remove: + case LibFunc::realpath: + if (FTy->getNumParams() < 1 || !FTy->getParamType(0)->isPointerTy()) + return false; + setDoesNotThrow(F); + setDoesNotCapture(F, 1); + setOnlyReadsMemory(F, 1); + break; + case LibFunc::rename: + if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy() || + !FTy->getParamType(1)->isPointerTy()) + return false; + setDoesNotThrow(F); + setDoesNotCapture(F, 1); + setDoesNotCapture(F, 2); + setOnlyReadsMemory(F, 1); + setOnlyReadsMemory(F, 2); + break; + case LibFunc::readlink: + if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy() || + !FTy->getParamType(1)->isPointerTy()) + return false; + setDoesNotThrow(F); + setDoesNotCapture(F, 1); + setDoesNotCapture(F, 2); + setOnlyReadsMemory(F, 1); + break; + case LibFunc::write: + if (FTy->getNumParams() != 3 || !FTy->getParamType(1)->isPointerTy()) + return false; + // May throw; "write" is a valid pthread cancellation point. + setDoesNotCapture(F, 2); + setOnlyReadsMemory(F, 2); + break; + case LibFunc::bcopy: + if (FTy->getNumParams() != 3 || !FTy->getParamType(0)->isPointerTy() || + !FTy->getParamType(1)->isPointerTy()) + return false; + setDoesNotThrow(F); + setDoesNotCapture(F, 1); + setDoesNotCapture(F, 2); + setOnlyReadsMemory(F, 1); + break; + case LibFunc::bcmp: + if (FTy->getNumParams() != 3 || !FTy->getParamType(0)->isPointerTy() || + !FTy->getParamType(1)->isPointerTy()) + return false; + setDoesNotThrow(F); + setOnlyReadsMemory(F); + setDoesNotCapture(F, 1); + setDoesNotCapture(F, 2); + break; + case LibFunc::bzero: + if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy()) + return false; + setDoesNotThrow(F); + setDoesNotCapture(F, 1); + break; + case LibFunc::calloc: + if (FTy->getNumParams() != 2 || !FTy->getReturnType()->isPointerTy()) + return false; + setDoesNotThrow(F); + setDoesNotAlias(F, 0); + break; + case LibFunc::chmod: + case LibFunc::chown: + if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy()) + return false; + setDoesNotThrow(F); + setDoesNotCapture(F, 1); + setOnlyReadsMemory(F, 1); + break; + case LibFunc::ctermid: + case LibFunc::clearerr: + case LibFunc::closedir: + if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy()) + return false; + setDoesNotThrow(F); + setDoesNotCapture(F, 1); + break; + case LibFunc::atoi: + case LibFunc::atol: + case LibFunc::atof: + case LibFunc::atoll: + if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy()) + return false; + setDoesNotThrow(F); + setOnlyReadsMemory(F); + setDoesNotCapture(F, 1); + break; + case LibFunc::access: + if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy()) + return false; + setDoesNotThrow(F); + setDoesNotCapture(F, 1); + setOnlyReadsMemory(F, 1); + break; + case LibFunc::fopen: + if (FTy->getNumParams() != 2 || !FTy->getReturnType()->isPointerTy() || + !FTy->getParamType(0)->isPointerTy() || + !FTy->getParamType(1)->isPointerTy()) + return false; + setDoesNotThrow(F); + setDoesNotAlias(F, 0); + setDoesNotCapture(F, 1); + setDoesNotCapture(F, 2); + setOnlyReadsMemory(F, 1); + setOnlyReadsMemory(F, 2); + break; + case LibFunc::fdopen: + if (FTy->getNumParams() != 2 || !FTy->getReturnType()->isPointerTy() || + !FTy->getParamType(1)->isPointerTy()) + return false; + setDoesNotThrow(F); + setDoesNotAlias(F, 0); + setDoesNotCapture(F, 2); + setOnlyReadsMemory(F, 2); + break; + case LibFunc::feof: + case LibFunc::free: + case LibFunc::fseek: + case LibFunc::ftell: + case LibFunc::fgetc: + case LibFunc::fseeko: + case LibFunc::ftello: + case LibFunc::fileno: + case LibFunc::fflush: + case LibFunc::fclose: + case LibFunc::fsetpos: + case LibFunc::flockfile: + case LibFunc::funlockfile: + case LibFunc::ftrylockfile: + if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy()) + return false; + setDoesNotThrow(F); + setDoesNotCapture(F, 1); + break; + case LibFunc::ferror: + if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy()) + return false; + setDoesNotThrow(F); + setDoesNotCapture(F, 1); + setOnlyReadsMemory(F); + break; + case LibFunc::fputc: + case LibFunc::fstat: + case LibFunc::frexp: + case LibFunc::frexpf: + case LibFunc::frexpl: + case LibFunc::fstatvfs: + if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy()) + return false; + setDoesNotThrow(F); + setDoesNotCapture(F, 2); + break; + case LibFunc::fgets: + if (FTy->getNumParams() != 3 || !FTy->getParamType(0)->isPointerTy() || + !FTy->getParamType(2)->isPointerTy()) + return false; + setDoesNotThrow(F); + setDoesNotCapture(F, 3); + break; + case LibFunc::fread: + if (FTy->getNumParams() != 4 || !FTy->getParamType(0)->isPointerTy() || + !FTy->getParamType(3)->isPointerTy()) + return false; + setDoesNotThrow(F); + setDoesNotCapture(F, 1); + setDoesNotCapture(F, 4); + break; + case LibFunc::fwrite: + if (FTy->getNumParams() != 4 || !FTy->getParamType(0)->isPointerTy() || + !FTy->getParamType(3)->isPointerTy()) + return false; + setDoesNotThrow(F); + setDoesNotCapture(F, 1); + setDoesNotCapture(F, 4); + break; + case LibFunc::fputs: + if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy() || + !FTy->getParamType(1)->isPointerTy()) + return false; + setDoesNotThrow(F); + setDoesNotCapture(F, 1); + setDoesNotCapture(F, 2); + setOnlyReadsMemory(F, 1); + break; + case LibFunc::fscanf: + case LibFunc::fprintf: + if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy() || + !FTy->getParamType(1)->isPointerTy()) + return false; + setDoesNotThrow(F); + setDoesNotCapture(F, 1); + setDoesNotCapture(F, 2); + setOnlyReadsMemory(F, 2); + break; + case LibFunc::fgetpos: + if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy() || + !FTy->getParamType(1)->isPointerTy()) + return false; + setDoesNotThrow(F); + setDoesNotCapture(F, 1); + setDoesNotCapture(F, 2); + break; + case LibFunc::getc: + case LibFunc::getlogin_r: + case LibFunc::getc_unlocked: + if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy()) + return false; + setDoesNotThrow(F); + setDoesNotCapture(F, 1); + break; + case LibFunc::getenv: + if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy()) + return false; + setDoesNotThrow(F); + setOnlyReadsMemory(F); + setDoesNotCapture(F, 1); + break; + case LibFunc::gets: + case LibFunc::getchar: + setDoesNotThrow(F); + break; + case LibFunc::getitimer: + if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy()) + return false; + setDoesNotThrow(F); + setDoesNotCapture(F, 2); + break; + case LibFunc::getpwnam: + if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy()) + return false; + setDoesNotThrow(F); + setDoesNotCapture(F, 1); + setOnlyReadsMemory(F, 1); + break; + case LibFunc::ungetc: + if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy()) + return false; + setDoesNotThrow(F); + setDoesNotCapture(F, 2); + break; + case LibFunc::uname: + if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy()) + return false; + setDoesNotThrow(F); + setDoesNotCapture(F, 1); + break; + case LibFunc::unlink: + if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy()) + return false; + setDoesNotThrow(F); + setDoesNotCapture(F, 1); + setOnlyReadsMemory(F, 1); + break; + case LibFunc::unsetenv: + if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy()) + return false; + setDoesNotThrow(F); + setDoesNotCapture(F, 1); + setOnlyReadsMemory(F, 1); + break; + case LibFunc::utime: + case LibFunc::utimes: + if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy() || + !FTy->getParamType(1)->isPointerTy()) + return false; + setDoesNotThrow(F); + setDoesNotCapture(F, 1); + setDoesNotCapture(F, 2); + setOnlyReadsMemory(F, 1); + setOnlyReadsMemory(F, 2); + break; + case LibFunc::putc: + if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy()) + return false; + setDoesNotThrow(F); + setDoesNotCapture(F, 2); + break; + case LibFunc::puts: + case LibFunc::printf: + case LibFunc::perror: + if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy()) + return false; + setDoesNotThrow(F); + setDoesNotCapture(F, 1); + setOnlyReadsMemory(F, 1); + break; + case LibFunc::pread: + if (FTy->getNumParams() != 4 || !FTy->getParamType(1)->isPointerTy()) + return false; + // May throw; "pread" is a valid pthread cancellation point. + setDoesNotCapture(F, 2); + break; + case LibFunc::pwrite: + if (FTy->getNumParams() != 4 || !FTy->getParamType(1)->isPointerTy()) + return false; + // May throw; "pwrite" is a valid pthread cancellation point. + setDoesNotCapture(F, 2); + setOnlyReadsMemory(F, 2); + break; + case LibFunc::putchar: + setDoesNotThrow(F); + break; + case LibFunc::popen: + if (FTy->getNumParams() != 2 || !FTy->getReturnType()->isPointerTy() || + !FTy->getParamType(0)->isPointerTy() || + !FTy->getParamType(1)->isPointerTy()) + return false; + setDoesNotThrow(F); + setDoesNotAlias(F, 0); + setDoesNotCapture(F, 1); + setDoesNotCapture(F, 2); + setOnlyReadsMemory(F, 1); + setOnlyReadsMemory(F, 2); + break; + case LibFunc::pclose: + if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy()) + return false; + setDoesNotThrow(F); + setDoesNotCapture(F, 1); + break; + case LibFunc::vscanf: + if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy()) + return false; + setDoesNotThrow(F); + setDoesNotCapture(F, 1); + setOnlyReadsMemory(F, 1); + break; + case LibFunc::vsscanf: + if (FTy->getNumParams() != 3 || !FTy->getParamType(1)->isPointerTy() || + !FTy->getParamType(2)->isPointerTy()) + return false; + setDoesNotThrow(F); + setDoesNotCapture(F, 1); + setDoesNotCapture(F, 2); + setOnlyReadsMemory(F, 1); + setOnlyReadsMemory(F, 2); + break; + case LibFunc::vfscanf: + if (FTy->getNumParams() != 3 || !FTy->getParamType(1)->isPointerTy() || + !FTy->getParamType(2)->isPointerTy()) + return false; + setDoesNotThrow(F); + setDoesNotCapture(F, 1); + setDoesNotCapture(F, 2); + setOnlyReadsMemory(F, 2); + break; + case LibFunc::valloc: + if (!FTy->getReturnType()->isPointerTy()) + return false; + setDoesNotThrow(F); + setDoesNotAlias(F, 0); + break; + case LibFunc::vprintf: + if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy()) + return false; + setDoesNotThrow(F); + setDoesNotCapture(F, 1); + setOnlyReadsMemory(F, 1); + break; + case LibFunc::vfprintf: + case LibFunc::vsprintf: + if (FTy->getNumParams() != 3 || !FTy->getParamType(0)->isPointerTy() || + !FTy->getParamType(1)->isPointerTy()) + return false; + setDoesNotThrow(F); + setDoesNotCapture(F, 1); + setDoesNotCapture(F, 2); + setOnlyReadsMemory(F, 2); + break; + case LibFunc::vsnprintf: + if (FTy->getNumParams() != 4 || !FTy->getParamType(0)->isPointerTy() || + !FTy->getParamType(2)->isPointerTy()) + return false; + setDoesNotThrow(F); + setDoesNotCapture(F, 1); + setDoesNotCapture(F, 3); + setOnlyReadsMemory(F, 3); + break; + case LibFunc::open: + if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy()) + return false; + // May throw; "open" is a valid pthread cancellation point. + setDoesNotCapture(F, 1); + setOnlyReadsMemory(F, 1); + break; + case LibFunc::opendir: + if (FTy->getNumParams() != 1 || !FTy->getReturnType()->isPointerTy() || + !FTy->getParamType(0)->isPointerTy()) + return false; + setDoesNotThrow(F); + setDoesNotAlias(F, 0); + setDoesNotCapture(F, 1); + setOnlyReadsMemory(F, 1); + break; + case LibFunc::tmpfile: + if (!FTy->getReturnType()->isPointerTy()) + return false; + setDoesNotThrow(F); + setDoesNotAlias(F, 0); + break; + case LibFunc::times: + if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy()) + return false; + setDoesNotThrow(F); + setDoesNotCapture(F, 1); + break; + case LibFunc::htonl: + case LibFunc::htons: + case LibFunc::ntohl: + case LibFunc::ntohs: + setDoesNotThrow(F); + setDoesNotAccessMemory(F); + break; + case LibFunc::lstat: + if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy() || + !FTy->getParamType(1)->isPointerTy()) + return false; + setDoesNotThrow(F); + setDoesNotCapture(F, 1); + setDoesNotCapture(F, 2); + setOnlyReadsMemory(F, 1); + break; + case LibFunc::lchown: + if (FTy->getNumParams() != 3 || !FTy->getParamType(0)->isPointerTy()) + return false; + setDoesNotThrow(F); + setDoesNotCapture(F, 1); + setOnlyReadsMemory(F, 1); + break; + case LibFunc::qsort: + if (FTy->getNumParams() != 4 || !FTy->getParamType(3)->isPointerTy()) + return false; + // May throw; places call through function pointer. + setDoesNotCapture(F, 4); + break; + case LibFunc::dunder_strdup: + case LibFunc::dunder_strndup: + if (FTy->getNumParams() < 1 || !FTy->getReturnType()->isPointerTy() || + !FTy->getParamType(0)->isPointerTy()) + return false; + setDoesNotThrow(F); + setDoesNotAlias(F, 0); + setDoesNotCapture(F, 1); + setOnlyReadsMemory(F, 1); + break; + case LibFunc::dunder_strtok_r: + if (FTy->getNumParams() != 3 || !FTy->getParamType(1)->isPointerTy()) + return false; + setDoesNotThrow(F); + setDoesNotCapture(F, 2); + setOnlyReadsMemory(F, 2); + break; + case LibFunc::under_IO_getc: + if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy()) + return false; + setDoesNotThrow(F); + setDoesNotCapture(F, 1); + break; + case LibFunc::under_IO_putc: + if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy()) + return false; + setDoesNotThrow(F); + setDoesNotCapture(F, 2); + break; + case LibFunc::dunder_isoc99_scanf: + if (FTy->getNumParams() < 1 || !FTy->getParamType(0)->isPointerTy()) + return false; + setDoesNotThrow(F); + setDoesNotCapture(F, 1); + setOnlyReadsMemory(F, 1); + break; + case LibFunc::stat64: + case LibFunc::lstat64: + case LibFunc::statvfs64: + if (FTy->getNumParams() < 1 || !FTy->getParamType(0)->isPointerTy() || + !FTy->getParamType(1)->isPointerTy()) + return false; + setDoesNotThrow(F); + setDoesNotCapture(F, 1); + setDoesNotCapture(F, 2); + setOnlyReadsMemory(F, 1); + break; + case LibFunc::dunder_isoc99_sscanf: + if (FTy->getNumParams() < 1 || !FTy->getParamType(0)->isPointerTy() || + !FTy->getParamType(1)->isPointerTy()) + return false; + setDoesNotThrow(F); + setDoesNotCapture(F, 1); + setDoesNotCapture(F, 2); + setOnlyReadsMemory(F, 1); + setOnlyReadsMemory(F, 2); + break; + case LibFunc::fopen64: + if (FTy->getNumParams() != 2 || !FTy->getReturnType()->isPointerTy() || + !FTy->getParamType(0)->isPointerTy() || + !FTy->getParamType(1)->isPointerTy()) + return false; + setDoesNotThrow(F); + setDoesNotAlias(F, 0); + setDoesNotCapture(F, 1); + setDoesNotCapture(F, 2); + setOnlyReadsMemory(F, 1); + setOnlyReadsMemory(F, 2); + break; + case LibFunc::fseeko64: + case LibFunc::ftello64: + if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy()) + return false; + setDoesNotThrow(F); + setDoesNotCapture(F, 1); + break; + case LibFunc::tmpfile64: + if (!FTy->getReturnType()->isPointerTy()) + return false; + setDoesNotThrow(F); + setDoesNotAlias(F, 0); + break; + case LibFunc::fstat64: + case LibFunc::fstatvfs64: + if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy()) + return false; + setDoesNotThrow(F); + setDoesNotCapture(F, 2); + break; + case LibFunc::open64: + if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy()) + return false; + // May throw; "open" is a valid pthread cancellation point. + setDoesNotCapture(F, 1); + setOnlyReadsMemory(F, 1); + break; + case LibFunc::gettimeofday: + if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy() || + !FTy->getParamType(1)->isPointerTy()) + return false; + // Currently some platforms have the restrict keyword on the arguments to + // gettimeofday. To be conservative, do not add noalias to gettimeofday's + // arguments. + setDoesNotThrow(F); + setDoesNotCapture(F, 1); + setDoesNotCapture(F, 2); + break; + default: + // Didn't mark any attributes. + return false; + } + + return true; +} + +/// Adds attributes to well-known standard library call declarations. +bool FunctionAttrs::annotateLibraryCalls(const CallGraphSCC &SCC) { + bool MadeChange = false; + + // Check each function in turn annotating well-known library function + // declarations with attributes. + for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) { + Function *F = (*I)->getFunction(); + + if (F && F->isDeclaration()) + MadeChange |= inferPrototypeAttributes(*F, *TLI); + } + + return MadeChange; +} + bool FunctionAttrs::runOnSCC(CallGraphSCC &SCC) { - AA = &getAnalysis(); + TLI = &getAnalysis().getTLI(); - bool Changed = AddReadAttrs(SCC); - Changed |= AddNoCaptureAttrs(SCC); + bool Changed = annotateLibraryCalls(SCC); + Changed |= AddReadAttrs(SCC); + Changed |= AddArgumentAttrs(SCC); Changed |= AddNoAliasAttrs(SCC); + Changed |= AddNonNullAttrs(SCC); return Changed; }