X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=blobdiff_plain;f=lib%2FTransforms%2FIPO%2FFunctionAttrs.cpp;h=80050220c8bf1bffc47bb8460c2db03e9463e536;hp=13668838c789e94ceb31eed85e12179664166dfc;hb=f73144bb0330cc615083dd20a550fecdfd0fa4c4;hpb=60ceb6ec151eb3cad0de6559de247be972cd94d6 diff --git a/lib/Transforms/IPO/FunctionAttrs.cpp b/lib/Transforms/IPO/FunctionAttrs.cpp index 13668838c78..80050220c8b 100644 --- a/lib/Transforms/IPO/FunctionAttrs.cpp +++ b/lib/Transforms/IPO/FunctionAttrs.cpp @@ -18,250 +18,215 @@ // //===----------------------------------------------------------------------===// -#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/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/Target/TargetLibraryInfo.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()); - } +typedef SmallSetVector SCCNodeSet; +} - // runOnSCC - Analyze the SCC, performing the transformation if possible. - bool runOnSCC(CallGraphSCC &SCC); +namespace { +struct FunctionAttrs : public CallGraphSCCPass { + static char ID; // Pass identification, replacement for typeid + FunctionAttrs() : CallGraphSCCPass(ID) { + initializeFunctionAttrsPass(*PassRegistry::getPassRegistry()); + } - // AddReadAttrs - Deduce readonly/readnone attributes for the SCC. - bool AddReadAttrs(const CallGraphSCC &SCC); + bool runOnSCC(CallGraphSCC &SCC) override; - // AddArgumentAttrs - Deduce nocapture attributes for the SCC. - bool AddArgumentAttrs(const CallGraphSCC &SCC); + void getAnalysisUsage(AnalysisUsage &AU) const override { + AU.setPreservesCFG(); + AU.addRequired(); + AU.addRequired(); + CallGraphSCCPass::getAnalysisUsage(AU); + } - // IsFunctionMallocLike - Does this function allocate new memory? - bool IsFunctionMallocLike(Function *F, - SmallPtrSet &) const; +private: + TargetLibraryInfo *TLI; +}; +} - // AddNoAliasAttrs - Deduce noalias attributes for the SCC. - bool AddNoAliasAttrs(const CallGraphSCC &SCC); +char FunctionAttrs::ID = 0; +INITIALIZE_PASS_BEGIN(FunctionAttrs, "functionattrs", + "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) - // Utility methods used by inferPrototypeAttributes to add attributes - // and maintain annotation statistics. +Pass *llvm::createFunctionAttrsPass() { return new FunctionAttrs(); } - void setDoesNotAccessMemory(Function &F) { - if (!F.doesNotAccessMemory()) { - F.setDoesNotAccessMemory(); - ++NumAnnotated; - } - } +namespace { +/// The three kinds of memory access relevant to 'readonly' and +/// 'readnone' attributes. +enum MemoryAccessKind { + MAK_ReadNone = 0, + MAK_ReadOnly = 1, + MAK_MayWrite = 2 +}; +} - void setOnlyReadsMemory(Function &F) { - if (!F.onlyReadsMemory()) { - F.setOnlyReadsMemory(); - ++NumAnnotated; - } - } +static MemoryAccessKind checkFunctionMemoryAccess(Function &F, AAResults &AAR, + const SCCNodeSet &SCCNodes) { + FunctionModRefBehavior MRB = AAR.getModRefBehavior(&F); + if (MRB == FMRB_DoesNotAccessMemory) + // Already perfect! + return MAK_ReadNone; + + // Definitions with weak linkage may be overridden at linktime with + // something that writes memory, so treat them like declarations. + if (F.isDeclaration() || F.mayBeOverridden()) { + if (AliasAnalysis::onlyReadsMemory(MRB)) + return MAK_ReadOnly; + + // Conservatively assume it writes to memory. + return MAK_MayWrite; + } - void setDoesNotThrow(Function &F) { - if (!F.doesNotThrow()) { - F.setDoesNotThrow(); - ++NumAnnotated; - } - } + // Scan the function body for instructions that may read or write memory. + bool ReadsMemory = false; + for (inst_iterator II = inst_begin(F), E = inst_end(F); II != E; ++II) { + Instruction *I = &*II; + + // 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(cast(I)); + if (CS) { + // Ignore calls to functions in the same SCC. + if (CS.getCalledFunction() && SCCNodes.count(CS.getCalledFunction())) + continue; + FunctionModRefBehavior MRB = AAR.getModRefBehavior(CS); - void setDoesNotCapture(Function &F, unsigned n) { - if (!F.doesNotCapture(n)) { - F.setDoesNotCapture(n); - ++NumAnnotated; - } - } + // If the call doesn't access memory, we're done. + if (!(MRB & MRI_ModRef)) + continue; - void setOnlyReadsMemory(Function &F, unsigned n) { - if (!F.onlyReadsMemory(n)) { - F.setOnlyReadsMemory(n); - ++NumAnnotated; + if (!AliasAnalysis::onlyAccessesArgPointees(MRB)) { + // The call could access any memory. If that includes writes, give up. + if (MRB & MRI_Mod) + return MAK_MayWrite; + // If it reads, note it. + if (MRB & MRI_Ref) + ReadsMemory = true; + continue; } - } - void setDoesNotAlias(Function &F, unsigned n) { - if (!F.doesNotAlias(n)) { - F.setDoesNotAlias(n); - ++NumAnnotated; - } - } + // Check whether all pointer arguments point to local memory, and + // ignore calls that only access local memory. + for (CallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end(); + CI != CE; ++CI) { + Value *Arg = *CI; + if (!Arg->getType()->isPointerTy()) + continue; - // inferPrototypeAttributes - Analyze the name and prototype of the - // given function and set any applicable attributes. Returns true - // if any attributes were set and false otherwise. - bool inferPrototypeAttributes(Function &F); + AAMDNodes AAInfo; + I->getAAMetadata(AAInfo); + MemoryLocation Loc(Arg, MemoryLocation::UnknownSize, AAInfo); - // annotateLibraryCalls - Adds attributes to well-known standard library - // call declarations. - bool annotateLibraryCalls(const CallGraphSCC &SCC); + // Skip accesses to local or constant memory as they don't impact the + // externally visible mod/ref behavior. + if (AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true)) + continue; - virtual void getAnalysisUsage(AnalysisUsage &AU) const { - AU.setPreservesCFG(); - AU.addRequired(); - AU.addRequired(); - CallGraphSCCPass::getAnalysisUsage(AU); + if (MRB & MRI_Mod) + // Writes non-local memory. Give up. + return MAK_MayWrite; + if (MRB & MRI_Ref) + // Ok, it reads non-local memory. + ReadsMemory = true; + } + continue; + } else if (LoadInst *LI = dyn_cast(I)) { + // Ignore non-volatile loads from local memory. (Atomic is okay here.) + if (!LI->isVolatile()) { + 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()) { + MemoryLocation Loc = MemoryLocation::get(SI); + if (AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true)) + continue; + } + } else if (VAArgInst *VI = dyn_cast(I)) { + // Ignore vaargs on local memory. + MemoryLocation Loc = MemoryLocation::get(VI); + if (AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true)) + continue; } - private: - AliasAnalysis *AA; - TargetLibraryInfo *TLI; - }; -} - -char FunctionAttrs::ID = 0; -INITIALIZE_PASS_BEGIN(FunctionAttrs, "functionattrs", - "Deduce function attributes", false, false) -INITIALIZE_AG_DEPENDENCY(CallGraph) -INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo) -INITIALIZE_PASS_END(FunctionAttrs, "functionattrs", - "Deduce function attributes", false, false) - -Pass *llvm::createFunctionAttrsPass() { return new FunctionAttrs(); } - + // Any remaining instructions need to be taken seriously! Check if they + // read or write memory. + if (I->mayWriteToMemory()) + // Writes memory. Just give up. + return MAK_MayWrite; -/// AddReadAttrs - Deduce readonly/readnone attributes for the SCC. -bool FunctionAttrs::AddReadAttrs(const CallGraphSCC &SCC) { - SmallPtrSet SCCNodes; + // If this instruction may read memory, remember that. + ReadsMemory |= I->mayReadFromMemory(); + } - // 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()); + return ReadsMemory ? MAK_ReadOnly : MAK_ReadNone; +} +/// Deduce readonly/readnone attributes for the SCC. +template +static bool addReadAttrs(const SCCNodeSet &SCCNodes, AARGetterT AARGetter) { // 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. bool ReadsMemory = false; - for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) { - Function *F = (*I)->getFunction(); + for (Function *F : SCCNodes) { + // Call the callable parameter to look up AA results for this function. + AAResults &AAR = AARGetter(*F); - if (F == 0) - // External node - may write memory. Just give up. + switch (checkFunctionMemoryAccess(*F, AAR, SCCNodes)) { + case MAK_MayWrite: return false; - - AliasAnalysis::ModRefBehavior MRB = AA->getModRefBehavior(F); - if (MRB == AliasAnalysis::DoesNotAccessMemory) - // Already perfect! - continue; - - // Definitions with weak linkage may be overridden at linktime with - // something that writes memory, so treat them like declarations. - if (F->isDeclaration() || F->mayBeOverridden()) { - if (!AliasAnalysis::onlyReadsMemory(MRB)) - // May write memory. Just give up. - return false; - + case MAK_ReadOnly: ReadsMemory = true; - continue; - } - - // Scan the function body for instructions that may read or write memory. - for (inst_iterator II = inst_begin(F), E = inst_end(F); II != E; ++II) { - Instruction *I = &*II; - - // 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(cast(I)); - if (CS) { - // Ignore calls to functions in the same SCC. - if (CS.getCalledFunction() && SCCNodes.count(CS.getCalledFunction())) - continue; - AliasAnalysis::ModRefBehavior MRB = AA->getModRefBehavior(CS); - // If the call doesn't access arbitrary memory, we may be able to - // figure out something. - if (AliasAnalysis::onlyAccessesArgPointees(MRB)) { - // If the call does access argument pointees, check each argument. - if (AliasAnalysis::doesAccessArgPointees(MRB)) - // Check whether all pointer arguments point to local memory, and - // ignore calls that only access local memory. - for (CallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end(); - 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) - // Writes non-local memory. Give up. - return false; - if (MRB & AliasAnalysis::Ref) - // Ok, it reads non-local memory. - ReadsMemory = true; - } - } - } - continue; - } - // The call could access any memory. If that includes writes, give up. - if (MRB & AliasAnalysis::Mod) - return false; - // If it reads, note it. - if (MRB & AliasAnalysis::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)) - 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)) - 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)) - continue; - } - - // Any remaining instructions need to be taken seriously! Check if they - // read or write memory. - if (I->mayWriteToMemory()) - // Writes memory. Just give up. - return false; - - // If this instruction may read memory, remember that. - ReadsMemory |= I->mayReadFromMemory(); + break; + case MAK_ReadNone: + // Nothing to do! + break; } } // Success! Functions in this SCC do not access memory, or only read memory. // Give them the appropriate attribute. bool MadeChange = false; - for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) { - Function *F = (*I)->getFunction(); - + for (Function *F : SCCNodes) { if (F->doesNotAccessMemory()) // Already perfect! continue; @@ -274,11 +239,10 @@ bool FunctionAttrs::AddReadAttrs(const CallGraphSCC &SCC) { // Clear out any existing attributes. AttrBuilder B; - B.addAttribute(Attribute::ReadOnly) - .addAttribute(Attribute::ReadNone); - F->removeAttributes(AttributeSet::FunctionIndex, - AttributeSet::get(F->getContext(), - AttributeSet::FunctionIndex, B)); + B.addAttribute(Attribute::ReadOnly).addAttribute(Attribute::ReadNone); + F->removeAttributes( + AttributeSet::FunctionIndex, + AttributeSet::get(F->getContext(), AttributeSet::FunctionIndex, B)); // Add in the new attribute. F->addAttribute(AttributeSet::FunctionIndex, @@ -294,135 +258,139 @@ 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 SCCNodeSet &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 || F->isDeclaration() || F->mayBeOverridden() || + !SCCNodes.count(F)) { + Captured = true; + return true; + } - 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; - } + 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(Found && "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 SCCNodeSet &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 ChildIteratorType nodes_end(ArgumentGraph *AG) { - return AG->end(); - } - }; + 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. +/// Returns Attribute::None, Attribute::ReadOnly or Attribute::ReadNone. static Attribute::AttrKind determinePointerReadAttrs(Argument *A, - const SmallPtrSet &SCCNodes) { - - SmallVector Worklist; - SmallSet Visited; - int Count = 0; + 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 (Value::use_iterator UI = A->use_begin(), UE = A->use_end(); - UI != UE; ++UI) { - if (Count++ >= 20) - return Attribute::None; - - Use *U = &UI.getUse(); - Visited.insert(U); - Worklist.push_back(U); + for (Use &U : A->uses()) { + Visited.insert(&U); + Worklist.push_back(&U); } while (!Worklist.empty()) { @@ -435,25 +403,38 @@ determinePointerReadAttrs(Argument *A, 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 (Instruction::use_iterator UI = I->use_begin(), UE = I->use_end(); - UI != UE; ++UI) { - Use *U = &UI.getUse(); - if (Visited.insert(U)) - Worklist.push_back(U); - } + 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()) + if (CS.doesNotAccessMemory()) { + AddUsersToWorklistIfCapturing(); continue; + } Function *F = CS.getCalledFunction(); if (!F) { if (CS.onlyReadsMemory()) { IsRead = true; + AddUsersToWorklistIfCapturing(); continue; } return Attribute::None; @@ -468,7 +449,8 @@ determinePointerReadAttrs(Argument *A, "More params than args in non-varargs call."); return Attribute::None; } - if (SCCNodes.count(AI)) + Captures &= !CS.doesNotCapture(A - B); + if (SCCNodes.count(&*AI)) continue; if (!CS.onlyReadsMemory() && !CS.onlyReadsMemory(A - B)) return Attribute::None; @@ -476,6 +458,7 @@ determinePointerReadAttrs(Argument *A, IsRead = true; } } + AddUsersToWorklistIfCapturing(); break; } @@ -495,20 +478,10 @@ determinePointerReadAttrs(Argument *A, return IsRead ? Attribute::ReadOnly : Attribute::ReadNone; } -/// AddArgumentAttrs - Deduce nocapture attributes for the SCC. -bool FunctionAttrs::AddArgumentAttrs(const CallGraphSCC &SCC) { +/// Deduce nocapture attributes for the SCC. +static bool addArgumentAttrs(const SCCNodeSet &SCCNodes) { bool Changed = false; - 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()) - SCCNodes.insert(F); - } - ArgumentGraph AG; AttrBuilder B; @@ -516,13 +489,7 @@ bool FunctionAttrs::AddArgumentAttrs(const CallGraphSCC &SCC) { // Check each function in turn, determining which pointer arguments are not // captured. - 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. - continue; - + for (Function *F : SCCNodes) { // Definitions with weak linkage may be overridden at linktime with // something that captures pointers, so treat them like declarations. if (F->isDeclaration() || F->mayBeOverridden()) @@ -532,8 +499,8 @@ bool FunctionAttrs::AddArgumentAttrs(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(AttributeSet::get(F->getContext(), A->getArgNo() + 1, B)); ++NumNoCapture; @@ -543,26 +510,30 @@ bool FunctionAttrs::AddArgumentAttrs(const CallGraphSCC &SCC) { continue; } - for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end(); - A != E; ++A) { - if (!A->getType()->isPointerTy()) continue; + 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); + PointerMayBeCaptured(&*A, &Tracker); if (!Tracker.Captured) { if (Tracker.Uses.empty()) { // If it's trivially not captured, mark it nocapture now. - A->addAttr(AttributeSet::get(F->getContext(), A->getArgNo()+1, B)); + A->addAttr( + AttributeSet::get(F->getContext(), A->getArgNo() + 1, B)); ++NumNoCapture; Changed = true; } else { // If it's not trivially captured and not trivially not captured, // 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) { + ArgumentGraphNode *Node = AG[&*A]; + 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; @@ -576,9 +547,9 @@ bool FunctionAttrs::AddArgumentAttrs(const CallGraphSCC &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); + SmallPtrSet Self; + Self.insert(&*A); + Attribute::AttrKind R = determinePointerReadAttrs(&*A, Self); if (R != Attribute::None) { AttrBuilder B; B.addAttribute(R); @@ -597,11 +568,11 @@ bool FunctionAttrs::AddArgumentAttrs(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 && @@ -615,29 +586,30 @@ bool FunctionAttrs::AddArgumentAttrs(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; @@ -645,7 +617,8 @@ bool FunctionAttrs::AddArgumentAttrs(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; @@ -680,10 +653,13 @@ bool FunctionAttrs::AddArgumentAttrs(const CallGraphSCC &SCC) { } if (ReadAttr != Attribute::None) { - AttrBuilder B; + 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; @@ -694,10 +670,11 @@ bool FunctionAttrs::AddArgumentAttrs(const CallGraphSCC &SCC) { 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. +static bool isFunctionMallocLike(Function *F, const SCCNodeSet &SCCNodes) { SmallSetVector FlowsToReturn; for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) if (ReturnInst *Ret = dyn_cast(I->getTerminator())) @@ -718,38 +695,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; - 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 (CS.getCalledFunction() && SCCNodes.count(CS.getCalledFunction())) + break; + } // fall-through + default: + return false; // Did not come from an allocation. } if (PointerMayBeCaptured(RetVal, false, /*StoreCaptures=*/false)) @@ -759,24 +736,11 @@ bool FunctionAttrs::IsFunctionMallocLike(Function *F, return true; } -/// AddNoAliasAttrs - Deduce noalias attributes for the SCC. -bool FunctionAttrs::AddNoAliasAttrs(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()); - +/// Deduce noalias attributes for the SCC. +static bool addNoAliasAttrs(const SCCNodeSet &SCCNodes) { // Check each function in turn, determining which functions return noalias // pointers. - for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) { - Function *F = (*I)->getFunction(); - - if (F == 0) - // External node - skip it; - return false; - + for (Function *F : SCCNodes) { // Already noalias. if (F->doesNotAlias(0)) continue; @@ -786,18 +750,17 @@ 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; - if (!IsFunctionMallocLike(F, SCCNodes)) + if (!isFunctionMallocLike(F, SCCNodes)) return false; } bool MadeChange = false; - for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) { - Function *F = (*I)->getFunction(); + for (Function *F : SCCNodes) { if (F->doesNotAlias(0) || !F->getReturnType()->isPointerTy()) continue; @@ -809,13 +772,190 @@ bool FunctionAttrs::AddNoAliasAttrs(const CallGraphSCC &SCC) { return MadeChange; } -/// inferPrototypeAttributes - Analyze the name and prototype of the -/// given function and set any applicable attributes. Returns true -/// if any attributes were set and false otherwise. -bool FunctionAttrs::inferPrototypeAttributes(Function &F) { +/// 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, const SCCNodeSet &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. +static bool addNonNullAttrs(const SCCNodeSet &SCCNodes, + const TargetLibraryInfo &TLI) { + // 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 (Function *F : SCCNodes) { + // 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 (Function *F : SCCNodes) { + 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))) + if (!(TLI.getLibFunc(F.getName(), TheLibFunc) && TLI.has(TheLibFunc))) return false; switch (TheLibFunc) { @@ -828,8 +968,7 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) { break; case LibFunc::strchr: case LibFunc::strrchr: - if (FTy->getNumParams() != 2 || - !FTy->getParamType(0)->isPointerTy() || + if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy() || !FTy->getParamType(1)->isIntegerTy()) return false; setOnlyReadsMemory(F); @@ -842,8 +981,7 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) { case LibFunc::strtoll: case LibFunc::strtold: case LibFunc::strtoull: - if (FTy->getNumParams() < 2 || - !FTy->getParamType(1)->isPointerTy()) + if (FTy->getNumParams() < 2 || !FTy->getParamType(1)->isPointerTy()) return false; setDoesNotThrow(F); setDoesNotCapture(F, 2); @@ -855,16 +993,14 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) { case LibFunc::strncat: case LibFunc::strncpy: case LibFunc::stpncpy: - if (FTy->getNumParams() < 2 || - !FTy->getParamType(1)->isPointerTy()) + 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() || + if (FTy->getNumParams() != 3 || !FTy->getParamType(0)->isPointerTy() || !FTy->getParamType(1)->isPointerTy()) return false; setDoesNotThrow(F); @@ -872,15 +1008,14 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) { 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() || + 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); @@ -930,8 +1065,7 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) { break; case LibFunc::stat: case LibFunc::statvfs: - if (FTy->getNumParams() < 2 || - !FTy->getParamType(0)->isPointerTy() || + if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy() || !FTy->getParamType(1)->isPointerTy()) return false; setDoesNotThrow(F); @@ -940,8 +1074,7 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) { setOnlyReadsMemory(F, 1); break; case LibFunc::sscanf: - if (FTy->getNumParams() < 2 || - !FTy->getParamType(0)->isPointerTy() || + if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy() || !FTy->getParamType(1)->isPointerTy()) return false; setDoesNotThrow(F); @@ -951,8 +1084,7 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) { setOnlyReadsMemory(F, 2); break; case LibFunc::sprintf: - if (FTy->getNumParams() < 2 || - !FTy->getParamType(0)->isPointerTy() || + if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy() || !FTy->getParamType(1)->isPointerTy()) return false; setDoesNotThrow(F); @@ -961,8 +1093,7 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) { setOnlyReadsMemory(F, 2); break; case LibFunc::snprintf: - if (FTy->getNumParams() != 3 || - !FTy->getParamType(0)->isPointerTy() || + if (FTy->getNumParams() != 3 || !FTy->getParamType(0)->isPointerTy() || !FTy->getParamType(2)->isPointerTy()) return false; setDoesNotThrow(F); @@ -971,8 +1102,7 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) { setOnlyReadsMemory(F, 3); break; case LibFunc::setitimer: - if (FTy->getNumParams() != 3 || - !FTy->getParamType(1)->isPointerTy() || + if (FTy->getNumParams() != 3 || !FTy->getParamType(1)->isPointerTy() || !FTy->getParamType(2)->isPointerTy()) return false; setDoesNotThrow(F); @@ -981,23 +1111,20 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) { setOnlyReadsMemory(F, 2); break; case LibFunc::system: - if (FTy->getNumParams() != 1 || - !FTy->getParamType(0)->isPointerTy()) + 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()) + 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() || + if (FTy->getNumParams() != 3 || !FTy->getParamType(0)->isPointerTy() || !FTy->getParamType(1)->isPointerTy()) return false; setOnlyReadsMemory(F); @@ -1015,8 +1142,7 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) { case LibFunc::modf: case LibFunc::modff: case LibFunc::modfl: - if (FTy->getNumParams() < 2 || - !FTy->getParamType(1)->isPointerTy()) + if (FTy->getNumParams() < 2 || !FTy->getParamType(1)->isPointerTy()) return false; setDoesNotThrow(F); setDoesNotCapture(F, 2); @@ -1024,8 +1150,7 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) { case LibFunc::memcpy: case LibFunc::memccpy: case LibFunc::memmove: - if (FTy->getNumParams() < 2 || - !FTy->getParamType(1)->isPointerTy()) + if (FTy->getNumParams() < 2 || !FTy->getParamType(1)->isPointerTy()) return false; setDoesNotThrow(F); setDoesNotCapture(F, 2); @@ -1037,23 +1162,20 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) { setDoesNotAlias(F, 0); break; case LibFunc::mkdir: - if (FTy->getNumParams() == 0 || - !FTy->getParamType(0)->isPointerTy()) + 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()) + 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() || + if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy() || !FTy->getReturnType()->isPointerTy()) return false; setDoesNotThrow(F); @@ -1061,15 +1183,13 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) { setDoesNotCapture(F, 1); break; case LibFunc::read: - if (FTy->getNumParams() != 3 || - !FTy->getParamType(1)->isPointerTy()) + 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()) + if (FTy->getNumParams() < 1 || !FTy->getParamType(0)->isPointerTy()) return false; setDoesNotThrow(F); setDoesNotCapture(F, 1); @@ -1077,16 +1197,14 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) { case LibFunc::rmdir: case LibFunc::remove: case LibFunc::realpath: - if (FTy->getNumParams() < 1 || - !FTy->getParamType(0)->isPointerTy()) + 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() || + if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy() || !FTy->getParamType(1)->isPointerTy()) return false; setDoesNotThrow(F); @@ -1096,8 +1214,7 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) { setOnlyReadsMemory(F, 2); break; case LibFunc::readlink: - if (FTy->getNumParams() < 2 || - !FTy->getParamType(0)->isPointerTy() || + if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy() || !FTy->getParamType(1)->isPointerTy()) return false; setDoesNotThrow(F); @@ -1113,8 +1230,7 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) { setOnlyReadsMemory(F, 2); break; case LibFunc::bcopy: - if (FTy->getNumParams() != 3 || - !FTy->getParamType(0)->isPointerTy() || + if (FTy->getNumParams() != 3 || !FTy->getParamType(0)->isPointerTy() || !FTy->getParamType(1)->isPointerTy()) return false; setDoesNotThrow(F); @@ -1123,8 +1239,7 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) { setOnlyReadsMemory(F, 1); break; case LibFunc::bcmp: - if (FTy->getNumParams() != 3 || - !FTy->getParamType(0)->isPointerTy() || + if (FTy->getNumParams() != 3 || !FTy->getParamType(0)->isPointerTy() || !FTy->getParamType(1)->isPointerTy()) return false; setDoesNotThrow(F); @@ -1139,8 +1254,7 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) { setDoesNotCapture(F, 1); break; case LibFunc::calloc: - if (FTy->getNumParams() != 2 || - !FTy->getReturnType()->isPointerTy()) + if (FTy->getNumParams() != 2 || !FTy->getReturnType()->isPointerTy()) return false; setDoesNotThrow(F); setDoesNotAlias(F, 0); @@ -1179,8 +1293,7 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) { setOnlyReadsMemory(F, 1); break; case LibFunc::fopen: - if (FTy->getNumParams() != 2 || - !FTy->getReturnType()->isPointerTy() || + if (FTy->getNumParams() != 2 || !FTy->getReturnType()->isPointerTy() || !FTy->getParamType(0)->isPointerTy() || !FTy->getParamType(1)->isPointerTy()) return false; @@ -1192,8 +1305,7 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) { setOnlyReadsMemory(F, 2); break; case LibFunc::fdopen: - if (FTy->getNumParams() != 2 || - !FTy->getReturnType()->isPointerTy() || + if (FTy->getNumParams() != 2 || !FTy->getReturnType()->isPointerTy() || !FTy->getParamType(1)->isPointerTy()) return false; setDoesNotThrow(F); @@ -1239,16 +1351,14 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) { setDoesNotCapture(F, 2); break; case LibFunc::fgets: - if (FTy->getNumParams() != 3 || - !FTy->getParamType(0)->isPointerTy() || + 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() || + if (FTy->getNumParams() != 4 || !FTy->getParamType(0)->isPointerTy() || !FTy->getParamType(3)->isPointerTy()) return false; setDoesNotThrow(F); @@ -1256,8 +1366,7 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) { setDoesNotCapture(F, 4); break; case LibFunc::fwrite: - if (FTy->getNumParams() != 4 || - !FTy->getParamType(0)->isPointerTy() || + if (FTy->getNumParams() != 4 || !FTy->getParamType(0)->isPointerTy() || !FTy->getParamType(3)->isPointerTy()) return false; setDoesNotThrow(F); @@ -1265,8 +1374,7 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) { setDoesNotCapture(F, 4); break; case LibFunc::fputs: - if (FTy->getNumParams() < 2 || - !FTy->getParamType(0)->isPointerTy() || + if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy() || !FTy->getParamType(1)->isPointerTy()) return false; setDoesNotThrow(F); @@ -1276,8 +1384,7 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) { break; case LibFunc::fscanf: case LibFunc::fprintf: - if (FTy->getNumParams() < 2 || - !FTy->getParamType(0)->isPointerTy() || + if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy() || !FTy->getParamType(1)->isPointerTy()) return false; setDoesNotThrow(F); @@ -1286,8 +1393,7 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) { setOnlyReadsMemory(F, 2); break; case LibFunc::fgetpos: - if (FTy->getNumParams() < 2 || - !FTy->getParamType(0)->isPointerTy() || + if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy() || !FTy->getParamType(1)->isPointerTy()) return false; setDoesNotThrow(F); @@ -1354,8 +1460,7 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) { break; case LibFunc::utime: case LibFunc::utimes: - if (FTy->getNumParams() != 2 || - !FTy->getParamType(0)->isPointerTy() || + if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy() || !FTy->getParamType(1)->isPointerTy()) return false; setDoesNotThrow(F); @@ -1396,8 +1501,7 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) { setDoesNotThrow(F); break; case LibFunc::popen: - if (FTy->getNumParams() != 2 || - !FTy->getReturnType()->isPointerTy() || + if (FTy->getNumParams() != 2 || !FTy->getReturnType()->isPointerTy() || !FTy->getParamType(0)->isPointerTy() || !FTy->getParamType(1)->isPointerTy()) return false; @@ -1422,8 +1526,7 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) { setOnlyReadsMemory(F, 1); break; case LibFunc::vsscanf: - if (FTy->getNumParams() != 3 || - !FTy->getParamType(1)->isPointerTy() || + if (FTy->getNumParams() != 3 || !FTy->getParamType(1)->isPointerTy() || !FTy->getParamType(2)->isPointerTy()) return false; setDoesNotThrow(F); @@ -1433,8 +1536,7 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) { setOnlyReadsMemory(F, 2); break; case LibFunc::vfscanf: - if (FTy->getNumParams() != 3 || - !FTy->getParamType(1)->isPointerTy() || + if (FTy->getNumParams() != 3 || !FTy->getParamType(1)->isPointerTy() || !FTy->getParamType(2)->isPointerTy()) return false; setDoesNotThrow(F); @@ -1457,8 +1559,7 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) { break; case LibFunc::vfprintf: case LibFunc::vsprintf: - if (FTy->getNumParams() != 3 || - !FTy->getParamType(0)->isPointerTy() || + if (FTy->getNumParams() != 3 || !FTy->getParamType(0)->isPointerTy() || !FTy->getParamType(1)->isPointerTy()) return false; setDoesNotThrow(F); @@ -1467,8 +1568,7 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) { setOnlyReadsMemory(F, 2); break; case LibFunc::vsnprintf: - if (FTy->getNumParams() != 4 || - !FTy->getParamType(0)->isPointerTy() || + if (FTy->getNumParams() != 4 || !FTy->getParamType(0)->isPointerTy() || !FTy->getParamType(2)->isPointerTy()) return false; setDoesNotThrow(F); @@ -1484,8 +1584,7 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) { setOnlyReadsMemory(F, 1); break; case LibFunc::opendir: - if (FTy->getNumParams() != 1 || - !FTy->getReturnType()->isPointerTy() || + if (FTy->getNumParams() != 1 || !FTy->getReturnType()->isPointerTy() || !FTy->getParamType(0)->isPointerTy()) return false; setDoesNotThrow(F); @@ -1513,8 +1612,7 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) { setDoesNotAccessMemory(F); break; case LibFunc::lstat: - if (FTy->getNumParams() != 2 || - !FTy->getParamType(0)->isPointerTy() || + if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy() || !FTy->getParamType(1)->isPointerTy()) return false; setDoesNotThrow(F); @@ -1537,8 +1635,7 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) { break; case LibFunc::dunder_strdup: case LibFunc::dunder_strndup: - if (FTy->getNumParams() < 1 || - !FTy->getReturnType()->isPointerTy() || + if (FTy->getNumParams() < 1 || !FTy->getReturnType()->isPointerTy() || !FTy->getParamType(0)->isPointerTy()) return false; setDoesNotThrow(F); @@ -1547,8 +1644,7 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) { setOnlyReadsMemory(F, 1); break; case LibFunc::dunder_strtok_r: - if (FTy->getNumParams() != 3 || - !FTy->getParamType(1)->isPointerTy()) + if (FTy->getNumParams() != 3 || !FTy->getParamType(1)->isPointerTy()) return false; setDoesNotThrow(F); setDoesNotCapture(F, 2); @@ -1567,8 +1663,7 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) { setDoesNotCapture(F, 2); break; case LibFunc::dunder_isoc99_scanf: - if (FTy->getNumParams() < 1 || - !FTy->getParamType(0)->isPointerTy()) + if (FTy->getNumParams() < 1 || !FTy->getParamType(0)->isPointerTy()) return false; setDoesNotThrow(F); setDoesNotCapture(F, 1); @@ -1577,8 +1672,7 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) { case LibFunc::stat64: case LibFunc::lstat64: case LibFunc::statvfs64: - if (FTy->getNumParams() < 1 || - !FTy->getParamType(0)->isPointerTy() || + if (FTy->getNumParams() < 1 || !FTy->getParamType(0)->isPointerTy() || !FTy->getParamType(1)->isPointerTy()) return false; setDoesNotThrow(F); @@ -1587,8 +1681,7 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) { setOnlyReadsMemory(F, 1); break; case LibFunc::dunder_isoc99_sscanf: - if (FTy->getNumParams() < 1 || - !FTy->getParamType(0)->isPointerTy() || + if (FTy->getNumParams() < 1 || !FTy->getParamType(0)->isPointerTy() || !FTy->getParamType(1)->isPointerTy()) return false; setDoesNotThrow(F); @@ -1598,8 +1691,7 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) { setOnlyReadsMemory(F, 2); break; case LibFunc::fopen64: - if (FTy->getNumParams() != 2 || - !FTy->getReturnType()->isPointerTy() || + if (FTy->getNumParams() != 2 || !FTy->getReturnType()->isPointerTy() || !FTy->getParamType(0)->isPointerTy() || !FTy->getParamType(1)->isPointerTy()) return false; @@ -1647,6 +1739,7 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) { setDoesNotThrow(F); setDoesNotCapture(F, 1); setDoesNotCapture(F, 2); + break; default: // Didn't mark any attributes. return false; @@ -1655,30 +1748,53 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) { return true; } -/// annotateLibraryCalls - Adds attributes to well-known standard library -/// call declarations. -bool FunctionAttrs::annotateLibraryCalls(const CallGraphSCC &SCC) { - bool MadeChange = false; +bool FunctionAttrs::runOnSCC(CallGraphSCC &SCC) { + TLI = &getAnalysis().getTLI(); + bool Changed = false; - // Check each function in turn annotating well-known library function - // declarations with attributes. + // We compute dedicated AA results for each function in the SCC as needed. We + // use a lambda referencing external objects so that they live long enough to + // be queried, but we re-use them each time. + Optional BAR; + Optional AAR; + auto AARGetter = [&](Function &F) -> AAResults & { + BAR.emplace(createLegacyPMBasicAAResult(*this, F)); + AAR.emplace(createLegacyPMAAResults(*this, F, *BAR)); + return *AAR; + }; + + // Fill SCCNodes with the elements of the SCC. Used for quickly looking up + // whether a given CallGraphNode is in this SCC. Also track whether there are + // any external or opt-none nodes that will prevent us from optimizing any + // part of the SCC. + SCCNodeSet SCCNodes; + bool ExternalNode = false; 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 function we're trying not to optimize - we both avoid + // transform them and avoid leveraging information they provide. + ExternalNode = true; + continue; + } + + // When initially processing functions, also infer their prototype + // attributes if they are declarations. + if (F->isDeclaration()) + Changed |= inferPrototypeAttributes(*F, *TLI); - if (F != 0 && F->isDeclaration()) - MadeChange |= inferPrototypeAttributes(*F); + SCCNodes.insert(F); } - return MadeChange; -} + Changed |= addReadAttrs(SCCNodes, AARGetter); + Changed |= addArgumentAttrs(SCCNodes); -bool FunctionAttrs::runOnSCC(CallGraphSCC &SCC) { - AA = &getAnalysis(); - TLI = &getAnalysis(); + // If we have no external nodes participating in the SCC, we can infer some + // more precise attributes as well. + if (!ExternalNode) { + Changed |= addNoAliasAttrs(SCCNodes); + Changed |= addNonNullAttrs(SCCNodes, *TLI); + } - bool Changed = annotateLibraryCalls(SCC); - Changed |= AddReadAttrs(SCC); - Changed |= AddArgumentAttrs(SCC); - Changed |= AddNoAliasAttrs(SCC); return Changed; }