1 //===- FunctionAttrs.cpp - Pass which marks functions attributes ----------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements a simple interprocedural pass which walks the
11 // call-graph, looking for functions which do not access or only read
12 // non-local memory, and marking them readnone/readonly. It does the
13 // same with function arguments independently, marking them readonly/
14 // readnone/nocapture. Finally, well-known library call declarations
15 // are marked with all attributes that are consistent with the
16 // function's standard definition. This pass is implemented as a
17 // bottom-up traversal of the call-graph.
19 //===----------------------------------------------------------------------===//
21 #include "llvm/Transforms/IPO.h"
22 #include "llvm/ADT/SCCIterator.h"
23 #include "llvm/ADT/SetVector.h"
24 #include "llvm/ADT/SmallSet.h"
25 #include "llvm/ADT/Statistic.h"
26 #include "llvm/ADT/StringSwitch.h"
27 #include "llvm/Analysis/AliasAnalysis.h"
28 #include "llvm/Analysis/AssumptionCache.h"
29 #include "llvm/Analysis/BasicAliasAnalysis.h"
30 #include "llvm/Analysis/CallGraph.h"
31 #include "llvm/Analysis/CallGraphSCCPass.h"
32 #include "llvm/Analysis/CaptureTracking.h"
33 #include "llvm/Analysis/TargetLibraryInfo.h"
34 #include "llvm/Analysis/ValueTracking.h"
35 #include "llvm/IR/GlobalVariable.h"
36 #include "llvm/IR/InstIterator.h"
37 #include "llvm/IR/IntrinsicInst.h"
38 #include "llvm/IR/LLVMContext.h"
39 #include "llvm/Support/Debug.h"
40 #include "llvm/Support/raw_ostream.h"
41 #include "llvm/Analysis/TargetLibraryInfo.h"
44 #define DEBUG_TYPE "functionattrs"
46 STATISTIC(NumReadNone, "Number of functions marked readnone");
47 STATISTIC(NumReadOnly, "Number of functions marked readonly");
48 STATISTIC(NumNoCapture, "Number of arguments marked nocapture");
49 STATISTIC(NumReadNoneArg, "Number of arguments marked readnone");
50 STATISTIC(NumReadOnlyArg, "Number of arguments marked readonly");
51 STATISTIC(NumNoAlias, "Number of function returns marked noalias");
52 STATISTIC(NumNonNullReturn, "Number of function returns marked nonnull");
53 STATISTIC(NumAnnotated, "Number of attributes added to library functions");
54 STATISTIC(NumNoRecurse, "Number of functions marked as norecurse");
56 static cl::list<std::string>
57 ForceAttributes("force-attribute", cl::Hidden,
58 cl::desc("Add an attribute to a function. This should be a "
59 "pair of 'function-name:attribute-name', for "
60 "example -force-add-attribute=foo:noinline. This "
61 "option can be specified multiple times."));
64 typedef SmallSetVector<Function *, 8> SCCNodeSet;
68 struct FunctionAttrs : public CallGraphSCCPass {
69 static char ID; // Pass identification, replacement for typeid
70 FunctionAttrs() : CallGraphSCCPass(ID) {
71 initializeFunctionAttrsPass(*PassRegistry::getPassRegistry());
74 bool runOnSCC(CallGraphSCC &SCC) override;
75 bool doInitialization(CallGraph &CG) override {
79 bool doFinalization(CallGraph &CG) override;
81 void getAnalysisUsage(AnalysisUsage &AU) const override {
83 AU.addRequired<AssumptionCacheTracker>();
84 AU.addRequired<TargetLibraryInfoWrapperPass>();
85 CallGraphSCCPass::getAnalysisUsage(AU);
89 TargetLibraryInfo *TLI;
90 SmallVector<WeakVH,16> Revisit;
94 char FunctionAttrs::ID = 0;
95 INITIALIZE_PASS_BEGIN(FunctionAttrs, "functionattrs",
96 "Deduce function attributes", false, false)
97 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
98 INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass)
99 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
100 INITIALIZE_PASS_END(FunctionAttrs, "functionattrs",
101 "Deduce function attributes", false, false)
103 Pass *llvm::createFunctionAttrsPass() { return new FunctionAttrs(); }
106 /// The three kinds of memory access relevant to 'readonly' and
107 /// 'readnone' attributes.
108 enum MemoryAccessKind {
115 static MemoryAccessKind checkFunctionMemoryAccess(Function &F, AAResults &AAR,
116 const SCCNodeSet &SCCNodes) {
117 FunctionModRefBehavior MRB = AAR.getModRefBehavior(&F);
118 if (MRB == FMRB_DoesNotAccessMemory)
122 // Definitions with weak linkage may be overridden at linktime with
123 // something that writes memory, so treat them like declarations.
124 if (F.isDeclaration() || F.mayBeOverridden()) {
125 if (AliasAnalysis::onlyReadsMemory(MRB))
128 // Conservatively assume it writes to memory.
132 // Scan the function body for instructions that may read or write memory.
133 bool ReadsMemory = false;
134 for (inst_iterator II = inst_begin(F), E = inst_end(F); II != E; ++II) {
135 Instruction *I = &*II;
137 // Some instructions can be ignored even if they read or write memory.
138 // Detect these now, skipping to the next instruction if one is found.
139 CallSite CS(cast<Value>(I));
141 // Ignore calls to functions in the same SCC.
142 if (CS.getCalledFunction() && SCCNodes.count(CS.getCalledFunction()))
144 FunctionModRefBehavior MRB = AAR.getModRefBehavior(CS);
146 // If the call doesn't access memory, we're done.
147 if (!(MRB & MRI_ModRef))
150 if (!AliasAnalysis::onlyAccessesArgPointees(MRB)) {
151 // The call could access any memory. If that includes writes, give up.
154 // If it reads, note it.
160 // Check whether all pointer arguments point to local memory, and
161 // ignore calls that only access local memory.
162 for (CallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end();
165 if (!Arg->getType()->isPtrOrPtrVectorTy())
169 I->getAAMetadata(AAInfo);
170 MemoryLocation Loc(Arg, MemoryLocation::UnknownSize, AAInfo);
172 // Skip accesses to local or constant memory as they don't impact the
173 // externally visible mod/ref behavior.
174 if (AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true))
178 // Writes non-local memory. Give up.
181 // Ok, it reads non-local memory.
185 } else if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
186 // Ignore non-volatile loads from local memory. (Atomic is okay here.)
187 if (!LI->isVolatile()) {
188 MemoryLocation Loc = MemoryLocation::get(LI);
189 if (AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true))
192 } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
193 // Ignore non-volatile stores to local memory. (Atomic is okay here.)
194 if (!SI->isVolatile()) {
195 MemoryLocation Loc = MemoryLocation::get(SI);
196 if (AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true))
199 } else if (VAArgInst *VI = dyn_cast<VAArgInst>(I)) {
200 // Ignore vaargs on local memory.
201 MemoryLocation Loc = MemoryLocation::get(VI);
202 if (AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true))
206 // Any remaining instructions need to be taken seriously! Check if they
207 // read or write memory.
208 if (I->mayWriteToMemory())
209 // Writes memory. Just give up.
212 // If this instruction may read memory, remember that.
213 ReadsMemory |= I->mayReadFromMemory();
216 return ReadsMemory ? MAK_ReadOnly : MAK_ReadNone;
219 /// Deduce readonly/readnone attributes for the SCC.
220 template <typename AARGetterT>
221 static bool addReadAttrs(const SCCNodeSet &SCCNodes, AARGetterT AARGetter) {
222 // Check if any of the functions in the SCC read or write memory. If they
223 // write memory then they can't be marked readnone or readonly.
224 bool ReadsMemory = false;
225 for (Function *F : SCCNodes) {
226 // Call the callable parameter to look up AA results for this function.
227 AAResults &AAR = AARGetter(*F);
229 switch (checkFunctionMemoryAccess(*F, AAR, SCCNodes)) {
241 // Success! Functions in this SCC do not access memory, or only read memory.
242 // Give them the appropriate attribute.
243 bool MadeChange = false;
244 for (Function *F : SCCNodes) {
245 if (F->doesNotAccessMemory())
249 if (F->onlyReadsMemory() && ReadsMemory)
255 // Clear out any existing attributes.
257 B.addAttribute(Attribute::ReadOnly).addAttribute(Attribute::ReadNone);
259 AttributeSet::FunctionIndex,
260 AttributeSet::get(F->getContext(), AttributeSet::FunctionIndex, B));
262 // Add in the new attribute.
263 F->addAttribute(AttributeSet::FunctionIndex,
264 ReadsMemory ? Attribute::ReadOnly : Attribute::ReadNone);
276 /// For a given pointer Argument, this retains a list of Arguments of functions
277 /// in the same SCC that the pointer data flows into. We use this to build an
278 /// SCC of the arguments.
279 struct ArgumentGraphNode {
280 Argument *Definition;
281 SmallVector<ArgumentGraphNode *, 4> Uses;
284 class ArgumentGraph {
285 // We store pointers to ArgumentGraphNode objects, so it's important that
286 // that they not move around upon insert.
287 typedef std::map<Argument *, ArgumentGraphNode> ArgumentMapTy;
289 ArgumentMapTy ArgumentMap;
291 // There is no root node for the argument graph, in fact:
292 // void f(int *x, int *y) { if (...) f(x, y); }
293 // is an example where the graph is disconnected. The SCCIterator requires a
294 // single entry point, so we maintain a fake ("synthetic") root node that
295 // uses every node. Because the graph is directed and nothing points into
296 // the root, it will not participate in any SCCs (except for its own).
297 ArgumentGraphNode SyntheticRoot;
300 ArgumentGraph() { SyntheticRoot.Definition = nullptr; }
302 typedef SmallVectorImpl<ArgumentGraphNode *>::iterator iterator;
304 iterator begin() { return SyntheticRoot.Uses.begin(); }
305 iterator end() { return SyntheticRoot.Uses.end(); }
306 ArgumentGraphNode *getEntryNode() { return &SyntheticRoot; }
308 ArgumentGraphNode *operator[](Argument *A) {
309 ArgumentGraphNode &Node = ArgumentMap[A];
311 SyntheticRoot.Uses.push_back(&Node);
316 /// This tracker checks whether callees are in the SCC, and if so it does not
317 /// consider that a capture, instead adding it to the "Uses" list and
318 /// continuing with the analysis.
319 struct ArgumentUsesTracker : public CaptureTracker {
320 ArgumentUsesTracker(const SCCNodeSet &SCCNodes)
321 : Captured(false), SCCNodes(SCCNodes) {}
323 void tooManyUses() override { Captured = true; }
325 bool captured(const Use *U) override {
326 CallSite CS(U->getUser());
327 if (!CS.getInstruction()) {
332 Function *F = CS.getCalledFunction();
333 if (!F || F->isDeclaration() || F->mayBeOverridden() ||
334 !SCCNodes.count(F)) {
339 // Note: the callee and the two successor blocks *follow* the argument
340 // operands. This means there is no need to adjust UseIndex to account for
344 std::distance(const_cast<const Use *>(CS.arg_begin()), U);
346 assert(UseIndex < CS.data_operands_size() &&
347 "Indirect function calls should have been filtered above!");
349 if (UseIndex >= CS.getNumArgOperands()) {
350 // Data operand, but not a argument operand -- must be a bundle operand
351 assert(CS.hasOperandBundles() && "Must be!");
353 // CaptureTracking told us that we're being captured by an operand bundle
354 // use. In this case it does not matter if the callee is within our SCC
355 // or not -- we've been captured in some unknown way, and we have to be
361 if (UseIndex >= F->arg_size()) {
362 assert(F->isVarArg() && "More params than args in non-varargs call");
367 Uses.push_back(&*std::next(F->arg_begin(), UseIndex));
371 bool Captured; // True only if certainly captured (used outside our SCC).
372 SmallVector<Argument *, 4> Uses; // Uses within our SCC.
374 const SCCNodeSet &SCCNodes;
379 template <> struct GraphTraits<ArgumentGraphNode *> {
380 typedef ArgumentGraphNode NodeType;
381 typedef SmallVectorImpl<ArgumentGraphNode *>::iterator ChildIteratorType;
383 static inline NodeType *getEntryNode(NodeType *A) { return A; }
384 static inline ChildIteratorType child_begin(NodeType *N) {
385 return N->Uses.begin();
387 static inline ChildIteratorType child_end(NodeType *N) {
388 return N->Uses.end();
392 struct GraphTraits<ArgumentGraph *> : public GraphTraits<ArgumentGraphNode *> {
393 static NodeType *getEntryNode(ArgumentGraph *AG) {
394 return AG->getEntryNode();
396 static ChildIteratorType nodes_begin(ArgumentGraph *AG) {
399 static ChildIteratorType nodes_end(ArgumentGraph *AG) { return AG->end(); }
403 /// Returns Attribute::None, Attribute::ReadOnly or Attribute::ReadNone.
404 static Attribute::AttrKind
405 determinePointerReadAttrs(Argument *A,
406 const SmallPtrSet<Argument *, 8> &SCCNodes) {
408 SmallVector<Use *, 32> Worklist;
409 SmallSet<Use *, 32> Visited;
411 // inalloca arguments are always clobbered by the call.
412 if (A->hasInAllocaAttr())
413 return Attribute::None;
416 // We don't need to track IsWritten. If A is written to, return immediately.
418 for (Use &U : A->uses()) {
420 Worklist.push_back(&U);
423 while (!Worklist.empty()) {
424 Use *U = Worklist.pop_back_val();
425 Instruction *I = cast<Instruction>(U->getUser());
427 switch (I->getOpcode()) {
428 case Instruction::BitCast:
429 case Instruction::GetElementPtr:
430 case Instruction::PHI:
431 case Instruction::Select:
432 case Instruction::AddrSpaceCast:
433 // The original value is not read/written via this if the new value isn't.
434 for (Use &UU : I->uses())
435 if (Visited.insert(&UU).second)
436 Worklist.push_back(&UU);
439 case Instruction::Call:
440 case Instruction::Invoke: {
441 bool Captures = true;
443 if (I->getType()->isVoidTy())
446 auto AddUsersToWorklistIfCapturing = [&] {
448 for (Use &UU : I->uses())
449 if (Visited.insert(&UU).second)
450 Worklist.push_back(&UU);
454 if (CS.doesNotAccessMemory()) {
455 AddUsersToWorklistIfCapturing();
459 Function *F = CS.getCalledFunction();
461 if (CS.onlyReadsMemory()) {
463 AddUsersToWorklistIfCapturing();
466 return Attribute::None;
469 // Note: the callee and the two successor blocks *follow* the argument
470 // operands. This means there is no need to adjust UseIndex to account
473 unsigned UseIndex = std::distance(CS.arg_begin(), U);
475 // U cannot be the callee operand use: since we're exploring the
476 // transitive uses of an Argument, having such a use be a callee would
477 // imply the CallSite is an indirect call or invoke; and we'd take the
479 assert(UseIndex < CS.data_operands_size() &&
480 "Data operand use expected!");
482 bool IsOperandBundleUse = UseIndex >= CS.getNumArgOperands();
484 if (UseIndex >= F->arg_size() && !IsOperandBundleUse) {
485 assert(F->isVarArg() && "More params than args in non-varargs call");
486 return Attribute::None;
489 Captures &= !CS.doesNotCapture(UseIndex);
491 // Since the optimizer (by design) cannot see the data flow corresponding
492 // to a operand bundle use, these cannot participate in the optimistic SCC
493 // analysis. Instead, we model the operand bundle uses as arguments in
494 // call to a function external to the SCC.
495 if (!SCCNodes.count(&*std::next(F->arg_begin(), UseIndex)) ||
496 IsOperandBundleUse) {
498 // The accessors used on CallSite here do the right thing for calls and
499 // invokes with operand bundles.
501 if (!CS.onlyReadsMemory() && !CS.onlyReadsMemory(UseIndex))
502 return Attribute::None;
503 if (!CS.doesNotAccessMemory(UseIndex))
507 AddUsersToWorklistIfCapturing();
511 case Instruction::Load:
515 case Instruction::ICmp:
516 case Instruction::Ret:
520 return Attribute::None;
524 return IsRead ? Attribute::ReadOnly : Attribute::ReadNone;
527 /// Deduce nocapture attributes for the SCC.
528 static bool addArgumentAttrs(const SCCNodeSet &SCCNodes) {
529 bool Changed = false;
534 B.addAttribute(Attribute::NoCapture);
536 // Check each function in turn, determining which pointer arguments are not
538 for (Function *F : SCCNodes) {
539 // Definitions with weak linkage may be overridden at linktime with
540 // something that captures pointers, so treat them like declarations.
541 if (F->isDeclaration() || F->mayBeOverridden())
544 // Functions that are readonly (or readnone) and nounwind and don't return
545 // a value can't capture arguments. Don't analyze them.
546 if (F->onlyReadsMemory() && F->doesNotThrow() &&
547 F->getReturnType()->isVoidTy()) {
548 for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end(); A != E;
550 if (A->getType()->isPointerTy() && !A->hasNoCaptureAttr()) {
551 A->addAttr(AttributeSet::get(F->getContext(), A->getArgNo() + 1, B));
559 for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end(); A != E;
561 if (!A->getType()->isPointerTy())
563 bool HasNonLocalUses = false;
564 if (!A->hasNoCaptureAttr()) {
565 ArgumentUsesTracker Tracker(SCCNodes);
566 PointerMayBeCaptured(&*A, &Tracker);
567 if (!Tracker.Captured) {
568 if (Tracker.Uses.empty()) {
569 // If it's trivially not captured, mark it nocapture now.
571 AttributeSet::get(F->getContext(), A->getArgNo() + 1, B));
575 // If it's not trivially captured and not trivially not captured,
576 // then it must be calling into another function in our SCC. Save
577 // its particulars for Argument-SCC analysis later.
578 ArgumentGraphNode *Node = AG[&*A];
579 for (SmallVectorImpl<Argument *>::iterator
580 UI = Tracker.Uses.begin(),
581 UE = Tracker.Uses.end();
583 Node->Uses.push_back(AG[*UI]);
585 HasNonLocalUses = true;
589 // Otherwise, it's captured. Don't bother doing SCC analysis on it.
591 if (!HasNonLocalUses && !A->onlyReadsMemory()) {
592 // Can we determine that it's readonly/readnone without doing an SCC?
593 // Note that we don't allow any calls at all here, or else our result
594 // will be dependent on the iteration order through the functions in the
596 SmallPtrSet<Argument *, 8> Self;
598 Attribute::AttrKind R = determinePointerReadAttrs(&*A, Self);
599 if (R != Attribute::None) {
602 A->addAttr(AttributeSet::get(A->getContext(), A->getArgNo() + 1, B));
604 R == Attribute::ReadOnly ? ++NumReadOnlyArg : ++NumReadNoneArg;
610 // The graph we've collected is partial because we stopped scanning for
611 // argument uses once we solved the argument trivially. These partial nodes
612 // show up as ArgumentGraphNode objects with an empty Uses list, and for
613 // these nodes the final decision about whether they capture has already been
614 // made. If the definition doesn't have a 'nocapture' attribute by now, it
617 for (scc_iterator<ArgumentGraph *> I = scc_begin(&AG); !I.isAtEnd(); ++I) {
618 const std::vector<ArgumentGraphNode *> &ArgumentSCC = *I;
619 if (ArgumentSCC.size() == 1) {
620 if (!ArgumentSCC[0]->Definition)
621 continue; // synthetic root node
623 // eg. "void f(int* x) { if (...) f(x); }"
624 if (ArgumentSCC[0]->Uses.size() == 1 &&
625 ArgumentSCC[0]->Uses[0] == ArgumentSCC[0]) {
626 Argument *A = ArgumentSCC[0]->Definition;
627 A->addAttr(AttributeSet::get(A->getContext(), A->getArgNo() + 1, B));
634 bool SCCCaptured = false;
635 for (auto I = ArgumentSCC.begin(), E = ArgumentSCC.end();
636 I != E && !SCCCaptured; ++I) {
637 ArgumentGraphNode *Node = *I;
638 if (Node->Uses.empty()) {
639 if (!Node->Definition->hasNoCaptureAttr())
646 SmallPtrSet<Argument *, 8> ArgumentSCCNodes;
647 // Fill ArgumentSCCNodes with the elements of the ArgumentSCC. Used for
648 // quickly looking up whether a given Argument is in this ArgumentSCC.
649 for (auto I = ArgumentSCC.begin(), E = ArgumentSCC.end(); I != E; ++I) {
650 ArgumentSCCNodes.insert((*I)->Definition);
653 for (auto I = ArgumentSCC.begin(), E = ArgumentSCC.end();
654 I != E && !SCCCaptured; ++I) {
655 ArgumentGraphNode *N = *I;
656 for (SmallVectorImpl<ArgumentGraphNode *>::iterator UI = N->Uses.begin(),
659 Argument *A = (*UI)->Definition;
660 if (A->hasNoCaptureAttr() || ArgumentSCCNodes.count(A))
669 for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) {
670 Argument *A = ArgumentSCC[i]->Definition;
671 A->addAttr(AttributeSet::get(A->getContext(), A->getArgNo() + 1, B));
676 // We also want to compute readonly/readnone. With a small number of false
677 // negatives, we can assume that any pointer which is captured isn't going
678 // to be provably readonly or readnone, since by definition we can't
679 // analyze all uses of a captured pointer.
681 // The false negatives happen when the pointer is captured by a function
682 // that promises readonly/readnone behaviour on the pointer, then the
683 // pointer's lifetime ends before anything that writes to arbitrary memory.
684 // Also, a readonly/readnone pointer may be returned, but returning a
685 // pointer is capturing it.
687 Attribute::AttrKind ReadAttr = Attribute::ReadNone;
688 for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) {
689 Argument *A = ArgumentSCC[i]->Definition;
690 Attribute::AttrKind K = determinePointerReadAttrs(A, ArgumentSCCNodes);
691 if (K == Attribute::ReadNone)
693 if (K == Attribute::ReadOnly) {
694 ReadAttr = Attribute::ReadOnly;
701 if (ReadAttr != Attribute::None) {
703 B.addAttribute(ReadAttr);
704 R.addAttribute(Attribute::ReadOnly).addAttribute(Attribute::ReadNone);
705 for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) {
706 Argument *A = ArgumentSCC[i]->Definition;
707 // Clear out existing readonly/readnone attributes
708 A->removeAttr(AttributeSet::get(A->getContext(), A->getArgNo() + 1, R));
709 A->addAttr(AttributeSet::get(A->getContext(), A->getArgNo() + 1, B));
710 ReadAttr == Attribute::ReadOnly ? ++NumReadOnlyArg : ++NumReadNoneArg;
719 /// Tests whether a function is "malloc-like".
721 /// A function is "malloc-like" if it returns either null or a pointer that
722 /// doesn't alias any other pointer visible to the caller.
723 static bool isFunctionMallocLike(Function *F, const SCCNodeSet &SCCNodes) {
724 SmallSetVector<Value *, 8> FlowsToReturn;
725 for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I)
726 if (ReturnInst *Ret = dyn_cast<ReturnInst>(I->getTerminator()))
727 FlowsToReturn.insert(Ret->getReturnValue());
729 for (unsigned i = 0; i != FlowsToReturn.size(); ++i) {
730 Value *RetVal = FlowsToReturn[i];
732 if (Constant *C = dyn_cast<Constant>(RetVal)) {
733 if (!C->isNullValue() && !isa<UndefValue>(C))
739 if (isa<Argument>(RetVal))
742 if (Instruction *RVI = dyn_cast<Instruction>(RetVal))
743 switch (RVI->getOpcode()) {
744 // Extend the analysis by looking upwards.
745 case Instruction::BitCast:
746 case Instruction::GetElementPtr:
747 case Instruction::AddrSpaceCast:
748 FlowsToReturn.insert(RVI->getOperand(0));
750 case Instruction::Select: {
751 SelectInst *SI = cast<SelectInst>(RVI);
752 FlowsToReturn.insert(SI->getTrueValue());
753 FlowsToReturn.insert(SI->getFalseValue());
756 case Instruction::PHI: {
757 PHINode *PN = cast<PHINode>(RVI);
758 for (Value *IncValue : PN->incoming_values())
759 FlowsToReturn.insert(IncValue);
763 // Check whether the pointer came from an allocation.
764 case Instruction::Alloca:
766 case Instruction::Call:
767 case Instruction::Invoke: {
769 if (CS.paramHasAttr(0, Attribute::NoAlias))
771 if (CS.getCalledFunction() && SCCNodes.count(CS.getCalledFunction()))
775 return false; // Did not come from an allocation.
778 if (PointerMayBeCaptured(RetVal, false, /*StoreCaptures=*/false))
785 /// Deduce noalias attributes for the SCC.
786 static bool addNoAliasAttrs(const SCCNodeSet &SCCNodes) {
787 // Check each function in turn, determining which functions return noalias
789 for (Function *F : SCCNodes) {
791 if (F->doesNotAlias(0))
794 // Definitions with weak linkage may be overridden at linktime, so
795 // treat them like declarations.
796 if (F->isDeclaration() || F->mayBeOverridden())
799 // We annotate noalias return values, which are only applicable to
801 if (!F->getReturnType()->isPointerTy())
804 if (!isFunctionMallocLike(F, SCCNodes))
808 bool MadeChange = false;
809 for (Function *F : SCCNodes) {
810 if (F->doesNotAlias(0) || !F->getReturnType()->isPointerTy())
813 F->setDoesNotAlias(0);
821 /// Tests whether this function is known to not return null.
823 /// Requires that the function returns a pointer.
825 /// Returns true if it believes the function will not return a null, and sets
826 /// \p Speculative based on whether the returned conclusion is a speculative
827 /// conclusion due to SCC calls.
828 static bool isReturnNonNull(Function *F, const SCCNodeSet &SCCNodes,
829 const TargetLibraryInfo &TLI, bool &Speculative) {
830 assert(F->getReturnType()->isPointerTy() &&
831 "nonnull only meaningful on pointer types");
834 SmallSetVector<Value *, 8> FlowsToReturn;
835 for (BasicBlock &BB : *F)
836 if (auto *Ret = dyn_cast<ReturnInst>(BB.getTerminator()))
837 FlowsToReturn.insert(Ret->getReturnValue());
839 for (unsigned i = 0; i != FlowsToReturn.size(); ++i) {
840 Value *RetVal = FlowsToReturn[i];
842 // If this value is locally known to be non-null, we're good
843 if (isKnownNonNull(RetVal, &TLI))
846 // Otherwise, we need to look upwards since we can't make any local
848 Instruction *RVI = dyn_cast<Instruction>(RetVal);
851 switch (RVI->getOpcode()) {
852 // Extend the analysis by looking upwards.
853 case Instruction::BitCast:
854 case Instruction::GetElementPtr:
855 case Instruction::AddrSpaceCast:
856 FlowsToReturn.insert(RVI->getOperand(0));
858 case Instruction::Select: {
859 SelectInst *SI = cast<SelectInst>(RVI);
860 FlowsToReturn.insert(SI->getTrueValue());
861 FlowsToReturn.insert(SI->getFalseValue());
864 case Instruction::PHI: {
865 PHINode *PN = cast<PHINode>(RVI);
866 for (int i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
867 FlowsToReturn.insert(PN->getIncomingValue(i));
870 case Instruction::Call:
871 case Instruction::Invoke: {
873 Function *Callee = CS.getCalledFunction();
874 // A call to a node within the SCC is assumed to return null until
876 if (Callee && SCCNodes.count(Callee)) {
883 return false; // Unknown source, may be null
885 llvm_unreachable("should have either continued or returned");
891 /// Deduce nonnull attributes for the SCC.
892 static bool addNonNullAttrs(const SCCNodeSet &SCCNodes,
893 const TargetLibraryInfo &TLI) {
894 // Speculative that all functions in the SCC return only nonnull
895 // pointers. We may refute this as we analyze functions.
896 bool SCCReturnsNonNull = true;
898 bool MadeChange = false;
900 // Check each function in turn, determining which functions return nonnull
902 for (Function *F : SCCNodes) {
904 if (F->getAttributes().hasAttribute(AttributeSet::ReturnIndex,
908 // Definitions with weak linkage may be overridden at linktime, so
909 // treat them like declarations.
910 if (F->isDeclaration() || F->mayBeOverridden())
913 // We annotate nonnull return values, which are only applicable to
915 if (!F->getReturnType()->isPointerTy())
918 bool Speculative = false;
919 if (isReturnNonNull(F, SCCNodes, TLI, Speculative)) {
921 // Mark the function eagerly since we may discover a function
922 // which prevents us from speculating about the entire SCC
923 DEBUG(dbgs() << "Eagerly marking " << F->getName() << " as nonnull\n");
924 F->addAttribute(AttributeSet::ReturnIndex, Attribute::NonNull);
930 // At least one function returns something which could be null, can't
931 // speculate any more.
932 SCCReturnsNonNull = false;
935 if (SCCReturnsNonNull) {
936 for (Function *F : SCCNodes) {
937 if (F->getAttributes().hasAttribute(AttributeSet::ReturnIndex,
938 Attribute::NonNull) ||
939 !F->getReturnType()->isPointerTy())
942 DEBUG(dbgs() << "SCC marking " << F->getName() << " as nonnull\n");
943 F->addAttribute(AttributeSet::ReturnIndex, Attribute::NonNull);
952 static void setDoesNotAccessMemory(Function &F) {
953 if (!F.doesNotAccessMemory()) {
954 F.setDoesNotAccessMemory();
959 static void setOnlyReadsMemory(Function &F) {
960 if (!F.onlyReadsMemory()) {
961 F.setOnlyReadsMemory();
966 static void setDoesNotThrow(Function &F) {
967 if (!F.doesNotThrow()) {
973 static void setDoesNotCapture(Function &F, unsigned n) {
974 if (!F.doesNotCapture(n)) {
975 F.setDoesNotCapture(n);
980 static void setOnlyReadsMemory(Function &F, unsigned n) {
981 if (!F.onlyReadsMemory(n)) {
982 F.setOnlyReadsMemory(n);
987 static void setDoesNotAlias(Function &F, unsigned n) {
988 if (!F.doesNotAlias(n)) {
989 F.setDoesNotAlias(n);
994 static bool setDoesNotRecurse(Function &F) {
995 if (F.doesNotRecurse())
997 F.setDoesNotRecurse();
1002 /// Analyze the name and prototype of the given function and set any applicable
1005 /// Returns true if any attributes were set and false otherwise.
1006 static bool inferPrototypeAttributes(Function &F, const TargetLibraryInfo &TLI) {
1007 if (F.hasFnAttribute(Attribute::OptimizeNone))
1010 FunctionType *FTy = F.getFunctionType();
1011 LibFunc::Func TheLibFunc;
1012 if (!(TLI.getLibFunc(F.getName(), TheLibFunc) && TLI.has(TheLibFunc)))
1015 switch (TheLibFunc) {
1016 case LibFunc::strlen:
1017 if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1019 setOnlyReadsMemory(F);
1021 setDoesNotCapture(F, 1);
1023 case LibFunc::strchr:
1024 case LibFunc::strrchr:
1025 if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy() ||
1026 !FTy->getParamType(1)->isIntegerTy())
1028 setOnlyReadsMemory(F);
1031 case LibFunc::strtol:
1032 case LibFunc::strtod:
1033 case LibFunc::strtof:
1034 case LibFunc::strtoul:
1035 case LibFunc::strtoll:
1036 case LibFunc::strtold:
1037 case LibFunc::strtoull:
1038 if (FTy->getNumParams() < 2 || !FTy->getParamType(1)->isPointerTy())
1041 setDoesNotCapture(F, 2);
1042 setOnlyReadsMemory(F, 1);
1044 case LibFunc::strcpy:
1045 case LibFunc::stpcpy:
1046 case LibFunc::strcat:
1047 case LibFunc::strncat:
1048 case LibFunc::strncpy:
1049 case LibFunc::stpncpy:
1050 if (FTy->getNumParams() < 2 || !FTy->getParamType(1)->isPointerTy())
1053 setDoesNotCapture(F, 2);
1054 setOnlyReadsMemory(F, 2);
1056 case LibFunc::strxfrm:
1057 if (FTy->getNumParams() != 3 || !FTy->getParamType(0)->isPointerTy() ||
1058 !FTy->getParamType(1)->isPointerTy())
1061 setDoesNotCapture(F, 1);
1062 setDoesNotCapture(F, 2);
1063 setOnlyReadsMemory(F, 2);
1065 case LibFunc::strcmp: // 0,1
1066 case LibFunc::strspn: // 0,1
1067 case LibFunc::strncmp: // 0,1
1068 case LibFunc::strcspn: // 0,1
1069 case LibFunc::strcoll: // 0,1
1070 case LibFunc::strcasecmp: // 0,1
1071 case LibFunc::strncasecmp: //
1072 if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy() ||
1073 !FTy->getParamType(1)->isPointerTy())
1075 setOnlyReadsMemory(F);
1077 setDoesNotCapture(F, 1);
1078 setDoesNotCapture(F, 2);
1080 case LibFunc::strstr:
1081 case LibFunc::strpbrk:
1082 if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
1084 setOnlyReadsMemory(F);
1086 setDoesNotCapture(F, 2);
1088 case LibFunc::strtok:
1089 case LibFunc::strtok_r:
1090 if (FTy->getNumParams() < 2 || !FTy->getParamType(1)->isPointerTy())
1093 setDoesNotCapture(F, 2);
1094 setOnlyReadsMemory(F, 2);
1096 case LibFunc::scanf:
1097 if (FTy->getNumParams() < 1 || !FTy->getParamType(0)->isPointerTy())
1100 setDoesNotCapture(F, 1);
1101 setOnlyReadsMemory(F, 1);
1103 case LibFunc::setbuf:
1104 case LibFunc::setvbuf:
1105 if (FTy->getNumParams() < 1 || !FTy->getParamType(0)->isPointerTy())
1108 setDoesNotCapture(F, 1);
1110 case LibFunc::strdup:
1111 case LibFunc::strndup:
1112 if (FTy->getNumParams() < 1 || !FTy->getReturnType()->isPointerTy() ||
1113 !FTy->getParamType(0)->isPointerTy())
1116 setDoesNotAlias(F, 0);
1117 setDoesNotCapture(F, 1);
1118 setOnlyReadsMemory(F, 1);
1121 case LibFunc::statvfs:
1122 if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy() ||
1123 !FTy->getParamType(1)->isPointerTy())
1126 setDoesNotCapture(F, 1);
1127 setDoesNotCapture(F, 2);
1128 setOnlyReadsMemory(F, 1);
1130 case LibFunc::sscanf:
1131 if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy() ||
1132 !FTy->getParamType(1)->isPointerTy())
1135 setDoesNotCapture(F, 1);
1136 setDoesNotCapture(F, 2);
1137 setOnlyReadsMemory(F, 1);
1138 setOnlyReadsMemory(F, 2);
1140 case LibFunc::sprintf:
1141 if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy() ||
1142 !FTy->getParamType(1)->isPointerTy())
1145 setDoesNotCapture(F, 1);
1146 setDoesNotCapture(F, 2);
1147 setOnlyReadsMemory(F, 2);
1149 case LibFunc::snprintf:
1150 if (FTy->getNumParams() != 3 || !FTy->getParamType(0)->isPointerTy() ||
1151 !FTy->getParamType(2)->isPointerTy())
1154 setDoesNotCapture(F, 1);
1155 setDoesNotCapture(F, 3);
1156 setOnlyReadsMemory(F, 3);
1158 case LibFunc::setitimer:
1159 if (FTy->getNumParams() != 3 || !FTy->getParamType(1)->isPointerTy() ||
1160 !FTy->getParamType(2)->isPointerTy())
1163 setDoesNotCapture(F, 2);
1164 setDoesNotCapture(F, 3);
1165 setOnlyReadsMemory(F, 2);
1167 case LibFunc::system:
1168 if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1170 // May throw; "system" is a valid pthread cancellation point.
1171 setDoesNotCapture(F, 1);
1172 setOnlyReadsMemory(F, 1);
1174 case LibFunc::malloc:
1175 if (FTy->getNumParams() != 1 || !FTy->getReturnType()->isPointerTy())
1178 setDoesNotAlias(F, 0);
1180 case LibFunc::memcmp:
1181 if (FTy->getNumParams() != 3 || !FTy->getParamType(0)->isPointerTy() ||
1182 !FTy->getParamType(1)->isPointerTy())
1184 setOnlyReadsMemory(F);
1186 setDoesNotCapture(F, 1);
1187 setDoesNotCapture(F, 2);
1189 case LibFunc::memchr:
1190 case LibFunc::memrchr:
1191 if (FTy->getNumParams() != 3)
1193 setOnlyReadsMemory(F);
1197 case LibFunc::modff:
1198 case LibFunc::modfl:
1199 if (FTy->getNumParams() < 2 || !FTy->getParamType(1)->isPointerTy())
1202 setDoesNotCapture(F, 2);
1204 case LibFunc::memcpy:
1205 case LibFunc::memccpy:
1206 case LibFunc::memmove:
1207 if (FTy->getNumParams() < 2 || !FTy->getParamType(1)->isPointerTy())
1210 setDoesNotCapture(F, 2);
1211 setOnlyReadsMemory(F, 2);
1213 case LibFunc::memalign:
1214 if (!FTy->getReturnType()->isPointerTy())
1216 setDoesNotAlias(F, 0);
1218 case LibFunc::mkdir:
1219 if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy())
1222 setDoesNotCapture(F, 1);
1223 setOnlyReadsMemory(F, 1);
1225 case LibFunc::mktime:
1226 if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy())
1229 setDoesNotCapture(F, 1);
1231 case LibFunc::realloc:
1232 if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy() ||
1233 !FTy->getReturnType()->isPointerTy())
1236 setDoesNotAlias(F, 0);
1237 setDoesNotCapture(F, 1);
1240 if (FTy->getNumParams() != 3 || !FTy->getParamType(1)->isPointerTy())
1242 // May throw; "read" is a valid pthread cancellation point.
1243 setDoesNotCapture(F, 2);
1245 case LibFunc::rewind:
1246 if (FTy->getNumParams() < 1 || !FTy->getParamType(0)->isPointerTy())
1249 setDoesNotCapture(F, 1);
1251 case LibFunc::rmdir:
1252 case LibFunc::remove:
1253 case LibFunc::realpath:
1254 if (FTy->getNumParams() < 1 || !FTy->getParamType(0)->isPointerTy())
1257 setDoesNotCapture(F, 1);
1258 setOnlyReadsMemory(F, 1);
1260 case LibFunc::rename:
1261 if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy() ||
1262 !FTy->getParamType(1)->isPointerTy())
1265 setDoesNotCapture(F, 1);
1266 setDoesNotCapture(F, 2);
1267 setOnlyReadsMemory(F, 1);
1268 setOnlyReadsMemory(F, 2);
1270 case LibFunc::readlink:
1271 if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy() ||
1272 !FTy->getParamType(1)->isPointerTy())
1275 setDoesNotCapture(F, 1);
1276 setDoesNotCapture(F, 2);
1277 setOnlyReadsMemory(F, 1);
1279 case LibFunc::write:
1280 if (FTy->getNumParams() != 3 || !FTy->getParamType(1)->isPointerTy())
1282 // May throw; "write" is a valid pthread cancellation point.
1283 setDoesNotCapture(F, 2);
1284 setOnlyReadsMemory(F, 2);
1286 case LibFunc::bcopy:
1287 if (FTy->getNumParams() != 3 || !FTy->getParamType(0)->isPointerTy() ||
1288 !FTy->getParamType(1)->isPointerTy())
1291 setDoesNotCapture(F, 1);
1292 setDoesNotCapture(F, 2);
1293 setOnlyReadsMemory(F, 1);
1296 if (FTy->getNumParams() != 3 || !FTy->getParamType(0)->isPointerTy() ||
1297 !FTy->getParamType(1)->isPointerTy())
1300 setOnlyReadsMemory(F);
1301 setDoesNotCapture(F, 1);
1302 setDoesNotCapture(F, 2);
1304 case LibFunc::bzero:
1305 if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy())
1308 setDoesNotCapture(F, 1);
1310 case LibFunc::calloc:
1311 if (FTy->getNumParams() != 2 || !FTy->getReturnType()->isPointerTy())
1314 setDoesNotAlias(F, 0);
1316 case LibFunc::chmod:
1317 case LibFunc::chown:
1318 if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy())
1321 setDoesNotCapture(F, 1);
1322 setOnlyReadsMemory(F, 1);
1324 case LibFunc::ctermid:
1325 case LibFunc::clearerr:
1326 case LibFunc::closedir:
1327 if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy())
1330 setDoesNotCapture(F, 1);
1335 case LibFunc::atoll:
1336 if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1339 setOnlyReadsMemory(F);
1340 setDoesNotCapture(F, 1);
1342 case LibFunc::access:
1343 if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy())
1346 setDoesNotCapture(F, 1);
1347 setOnlyReadsMemory(F, 1);
1349 case LibFunc::fopen:
1350 if (FTy->getNumParams() != 2 || !FTy->getReturnType()->isPointerTy() ||
1351 !FTy->getParamType(0)->isPointerTy() ||
1352 !FTy->getParamType(1)->isPointerTy())
1355 setDoesNotAlias(F, 0);
1356 setDoesNotCapture(F, 1);
1357 setDoesNotCapture(F, 2);
1358 setOnlyReadsMemory(F, 1);
1359 setOnlyReadsMemory(F, 2);
1361 case LibFunc::fdopen:
1362 if (FTy->getNumParams() != 2 || !FTy->getReturnType()->isPointerTy() ||
1363 !FTy->getParamType(1)->isPointerTy())
1366 setDoesNotAlias(F, 0);
1367 setDoesNotCapture(F, 2);
1368 setOnlyReadsMemory(F, 2);
1372 case LibFunc::fseek:
1373 case LibFunc::ftell:
1374 case LibFunc::fgetc:
1375 case LibFunc::fseeko:
1376 case LibFunc::ftello:
1377 case LibFunc::fileno:
1378 case LibFunc::fflush:
1379 case LibFunc::fclose:
1380 case LibFunc::fsetpos:
1381 case LibFunc::flockfile:
1382 case LibFunc::funlockfile:
1383 case LibFunc::ftrylockfile:
1384 if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy())
1387 setDoesNotCapture(F, 1);
1389 case LibFunc::ferror:
1390 if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1393 setDoesNotCapture(F, 1);
1394 setOnlyReadsMemory(F);
1396 case LibFunc::fputc:
1397 case LibFunc::fstat:
1398 case LibFunc::frexp:
1399 case LibFunc::frexpf:
1400 case LibFunc::frexpl:
1401 case LibFunc::fstatvfs:
1402 if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
1405 setDoesNotCapture(F, 2);
1407 case LibFunc::fgets:
1408 if (FTy->getNumParams() != 3 || !FTy->getParamType(0)->isPointerTy() ||
1409 !FTy->getParamType(2)->isPointerTy())
1412 setDoesNotCapture(F, 3);
1414 case LibFunc::fread:
1415 if (FTy->getNumParams() != 4 || !FTy->getParamType(0)->isPointerTy() ||
1416 !FTy->getParamType(3)->isPointerTy())
1419 setDoesNotCapture(F, 1);
1420 setDoesNotCapture(F, 4);
1422 case LibFunc::fwrite:
1423 if (FTy->getNumParams() != 4 || !FTy->getParamType(0)->isPointerTy() ||
1424 !FTy->getParamType(3)->isPointerTy())
1427 setDoesNotCapture(F, 1);
1428 setDoesNotCapture(F, 4);
1430 case LibFunc::fputs:
1431 if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy() ||
1432 !FTy->getParamType(1)->isPointerTy())
1435 setDoesNotCapture(F, 1);
1436 setDoesNotCapture(F, 2);
1437 setOnlyReadsMemory(F, 1);
1439 case LibFunc::fscanf:
1440 case LibFunc::fprintf:
1441 if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy() ||
1442 !FTy->getParamType(1)->isPointerTy())
1445 setDoesNotCapture(F, 1);
1446 setDoesNotCapture(F, 2);
1447 setOnlyReadsMemory(F, 2);
1449 case LibFunc::fgetpos:
1450 if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy() ||
1451 !FTy->getParamType(1)->isPointerTy())
1454 setDoesNotCapture(F, 1);
1455 setDoesNotCapture(F, 2);
1458 case LibFunc::getlogin_r:
1459 case LibFunc::getc_unlocked:
1460 if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy())
1463 setDoesNotCapture(F, 1);
1465 case LibFunc::getenv:
1466 if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1469 setOnlyReadsMemory(F);
1470 setDoesNotCapture(F, 1);
1473 case LibFunc::getchar:
1476 case LibFunc::getitimer:
1477 if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
1480 setDoesNotCapture(F, 2);
1482 case LibFunc::getpwnam:
1483 if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1486 setDoesNotCapture(F, 1);
1487 setOnlyReadsMemory(F, 1);
1489 case LibFunc::ungetc:
1490 if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
1493 setDoesNotCapture(F, 2);
1495 case LibFunc::uname:
1496 if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1499 setDoesNotCapture(F, 1);
1501 case LibFunc::unlink:
1502 if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1505 setDoesNotCapture(F, 1);
1506 setOnlyReadsMemory(F, 1);
1508 case LibFunc::unsetenv:
1509 if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1512 setDoesNotCapture(F, 1);
1513 setOnlyReadsMemory(F, 1);
1515 case LibFunc::utime:
1516 case LibFunc::utimes:
1517 if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy() ||
1518 !FTy->getParamType(1)->isPointerTy())
1521 setDoesNotCapture(F, 1);
1522 setDoesNotCapture(F, 2);
1523 setOnlyReadsMemory(F, 1);
1524 setOnlyReadsMemory(F, 2);
1527 if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
1530 setDoesNotCapture(F, 2);
1533 case LibFunc::printf:
1534 case LibFunc::perror:
1535 if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1538 setDoesNotCapture(F, 1);
1539 setOnlyReadsMemory(F, 1);
1541 case LibFunc::pread:
1542 if (FTy->getNumParams() != 4 || !FTy->getParamType(1)->isPointerTy())
1544 // May throw; "pread" is a valid pthread cancellation point.
1545 setDoesNotCapture(F, 2);
1547 case LibFunc::pwrite:
1548 if (FTy->getNumParams() != 4 || !FTy->getParamType(1)->isPointerTy())
1550 // May throw; "pwrite" is a valid pthread cancellation point.
1551 setDoesNotCapture(F, 2);
1552 setOnlyReadsMemory(F, 2);
1554 case LibFunc::putchar:
1557 case LibFunc::popen:
1558 if (FTy->getNumParams() != 2 || !FTy->getReturnType()->isPointerTy() ||
1559 !FTy->getParamType(0)->isPointerTy() ||
1560 !FTy->getParamType(1)->isPointerTy())
1563 setDoesNotAlias(F, 0);
1564 setDoesNotCapture(F, 1);
1565 setDoesNotCapture(F, 2);
1566 setOnlyReadsMemory(F, 1);
1567 setOnlyReadsMemory(F, 2);
1569 case LibFunc::pclose:
1570 if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1573 setDoesNotCapture(F, 1);
1575 case LibFunc::vscanf:
1576 if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
1579 setDoesNotCapture(F, 1);
1580 setOnlyReadsMemory(F, 1);
1582 case LibFunc::vsscanf:
1583 if (FTy->getNumParams() != 3 || !FTy->getParamType(1)->isPointerTy() ||
1584 !FTy->getParamType(2)->isPointerTy())
1587 setDoesNotCapture(F, 1);
1588 setDoesNotCapture(F, 2);
1589 setOnlyReadsMemory(F, 1);
1590 setOnlyReadsMemory(F, 2);
1592 case LibFunc::vfscanf:
1593 if (FTy->getNumParams() != 3 || !FTy->getParamType(1)->isPointerTy() ||
1594 !FTy->getParamType(2)->isPointerTy())
1597 setDoesNotCapture(F, 1);
1598 setDoesNotCapture(F, 2);
1599 setOnlyReadsMemory(F, 2);
1601 case LibFunc::valloc:
1602 if (!FTy->getReturnType()->isPointerTy())
1605 setDoesNotAlias(F, 0);
1607 case LibFunc::vprintf:
1608 if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy())
1611 setDoesNotCapture(F, 1);
1612 setOnlyReadsMemory(F, 1);
1614 case LibFunc::vfprintf:
1615 case LibFunc::vsprintf:
1616 if (FTy->getNumParams() != 3 || !FTy->getParamType(0)->isPointerTy() ||
1617 !FTy->getParamType(1)->isPointerTy())
1620 setDoesNotCapture(F, 1);
1621 setDoesNotCapture(F, 2);
1622 setOnlyReadsMemory(F, 2);
1624 case LibFunc::vsnprintf:
1625 if (FTy->getNumParams() != 4 || !FTy->getParamType(0)->isPointerTy() ||
1626 !FTy->getParamType(2)->isPointerTy())
1629 setDoesNotCapture(F, 1);
1630 setDoesNotCapture(F, 3);
1631 setOnlyReadsMemory(F, 3);
1634 if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy())
1636 // May throw; "open" is a valid pthread cancellation point.
1637 setDoesNotCapture(F, 1);
1638 setOnlyReadsMemory(F, 1);
1640 case LibFunc::opendir:
1641 if (FTy->getNumParams() != 1 || !FTy->getReturnType()->isPointerTy() ||
1642 !FTy->getParamType(0)->isPointerTy())
1645 setDoesNotAlias(F, 0);
1646 setDoesNotCapture(F, 1);
1647 setOnlyReadsMemory(F, 1);
1649 case LibFunc::tmpfile:
1650 if (!FTy->getReturnType()->isPointerTy())
1653 setDoesNotAlias(F, 0);
1655 case LibFunc::times:
1656 if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1659 setDoesNotCapture(F, 1);
1661 case LibFunc::htonl:
1662 case LibFunc::htons:
1663 case LibFunc::ntohl:
1664 case LibFunc::ntohs:
1666 setDoesNotAccessMemory(F);
1668 case LibFunc::lstat:
1669 if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy() ||
1670 !FTy->getParamType(1)->isPointerTy())
1673 setDoesNotCapture(F, 1);
1674 setDoesNotCapture(F, 2);
1675 setOnlyReadsMemory(F, 1);
1677 case LibFunc::lchown:
1678 if (FTy->getNumParams() != 3 || !FTy->getParamType(0)->isPointerTy())
1681 setDoesNotCapture(F, 1);
1682 setOnlyReadsMemory(F, 1);
1684 case LibFunc::qsort:
1685 if (FTy->getNumParams() != 4 || !FTy->getParamType(3)->isPointerTy())
1687 // May throw; places call through function pointer.
1688 setDoesNotCapture(F, 4);
1690 case LibFunc::dunder_strdup:
1691 case LibFunc::dunder_strndup:
1692 if (FTy->getNumParams() < 1 || !FTy->getReturnType()->isPointerTy() ||
1693 !FTy->getParamType(0)->isPointerTy())
1696 setDoesNotAlias(F, 0);
1697 setDoesNotCapture(F, 1);
1698 setOnlyReadsMemory(F, 1);
1700 case LibFunc::dunder_strtok_r:
1701 if (FTy->getNumParams() != 3 || !FTy->getParamType(1)->isPointerTy())
1704 setDoesNotCapture(F, 2);
1705 setOnlyReadsMemory(F, 2);
1707 case LibFunc::under_IO_getc:
1708 if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1711 setDoesNotCapture(F, 1);
1713 case LibFunc::under_IO_putc:
1714 if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
1717 setDoesNotCapture(F, 2);
1719 case LibFunc::dunder_isoc99_scanf:
1720 if (FTy->getNumParams() < 1 || !FTy->getParamType(0)->isPointerTy())
1723 setDoesNotCapture(F, 1);
1724 setOnlyReadsMemory(F, 1);
1726 case LibFunc::stat64:
1727 case LibFunc::lstat64:
1728 case LibFunc::statvfs64:
1729 if (FTy->getNumParams() < 1 || !FTy->getParamType(0)->isPointerTy() ||
1730 !FTy->getParamType(1)->isPointerTy())
1733 setDoesNotCapture(F, 1);
1734 setDoesNotCapture(F, 2);
1735 setOnlyReadsMemory(F, 1);
1737 case LibFunc::dunder_isoc99_sscanf:
1738 if (FTy->getNumParams() < 1 || !FTy->getParamType(0)->isPointerTy() ||
1739 !FTy->getParamType(1)->isPointerTy())
1742 setDoesNotCapture(F, 1);
1743 setDoesNotCapture(F, 2);
1744 setOnlyReadsMemory(F, 1);
1745 setOnlyReadsMemory(F, 2);
1747 case LibFunc::fopen64:
1748 if (FTy->getNumParams() != 2 || !FTy->getReturnType()->isPointerTy() ||
1749 !FTy->getParamType(0)->isPointerTy() ||
1750 !FTy->getParamType(1)->isPointerTy())
1753 setDoesNotAlias(F, 0);
1754 setDoesNotCapture(F, 1);
1755 setDoesNotCapture(F, 2);
1756 setOnlyReadsMemory(F, 1);
1757 setOnlyReadsMemory(F, 2);
1759 case LibFunc::fseeko64:
1760 case LibFunc::ftello64:
1761 if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy())
1764 setDoesNotCapture(F, 1);
1766 case LibFunc::tmpfile64:
1767 if (!FTy->getReturnType()->isPointerTy())
1770 setDoesNotAlias(F, 0);
1772 case LibFunc::fstat64:
1773 case LibFunc::fstatvfs64:
1774 if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
1777 setDoesNotCapture(F, 2);
1779 case LibFunc::open64:
1780 if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy())
1782 // May throw; "open" is a valid pthread cancellation point.
1783 setDoesNotCapture(F, 1);
1784 setOnlyReadsMemory(F, 1);
1786 case LibFunc::gettimeofday:
1787 if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy() ||
1788 !FTy->getParamType(1)->isPointerTy())
1790 // Currently some platforms have the restrict keyword on the arguments to
1791 // gettimeofday. To be conservative, do not add noalias to gettimeofday's
1794 setDoesNotCapture(F, 1);
1795 setDoesNotCapture(F, 2);
1798 // Didn't mark any attributes.
1805 static bool addNoRecurseAttrs(const CallGraphSCC &SCC,
1806 SmallVectorImpl<WeakVH> &Revisit) {
1807 // Try and identify functions that do not recurse.
1809 // If the SCC contains multiple nodes we know for sure there is recursion.
1810 if (!SCC.isSingular())
1813 const CallGraphNode *CGN = *SCC.begin();
1814 Function *F = CGN->getFunction();
1815 if (!F || F->isDeclaration() || F->doesNotRecurse())
1818 // If all of the calls in F are identifiable and are to norecurse functions, F
1819 // is norecurse. This check also detects self-recursion as F is not currently
1820 // marked norecurse, so any called from F to F will not be marked norecurse.
1821 if (std::all_of(CGN->begin(), CGN->end(),
1822 [](const CallGraphNode::CallRecord &CR) {
1823 Function *F = CR.second->getFunction();
1824 return F && F->doesNotRecurse();
1826 // Function calls a potentially recursive function.
1827 return setDoesNotRecurse(*F);
1829 // We know that F is not obviously recursive, but we haven't been able to
1830 // prove that it doesn't actually recurse. Add it to the Revisit list to try
1831 // again top-down later.
1832 Revisit.push_back(F);
1836 static bool addNoRecurseAttrsTopDownOnly(Function *F) {
1837 // If F is internal and all uses are in norecurse functions, then F is also
1839 if (F->doesNotRecurse())
1841 if (F->hasInternalLinkage()) {
1842 for (auto *U : F->users())
1843 if (auto *I = dyn_cast<Instruction>(U)) {
1844 if (!I->getParent()->getParent()->doesNotRecurse())
1849 return setDoesNotRecurse(*F);
1854 static Attribute::AttrKind parseAttrKind(StringRef Kind) {
1855 return StringSwitch<Attribute::AttrKind>(Kind)
1856 .Case("alwaysinline", Attribute::AlwaysInline)
1857 .Case("builtin", Attribute::Builtin)
1858 .Case("cold", Attribute::Cold)
1859 .Case("convergent", Attribute::Convergent)
1860 .Case("inlinehint", Attribute::InlineHint)
1861 .Case("jumptable", Attribute::JumpTable)
1862 .Case("minsize", Attribute::MinSize)
1863 .Case("naked", Attribute::Naked)
1864 .Case("nobuiltin", Attribute::NoBuiltin)
1865 .Case("noduplicate", Attribute::NoDuplicate)
1866 .Case("noimplicitfloat", Attribute::NoImplicitFloat)
1867 .Case("noinline", Attribute::NoInline)
1868 .Case("nonlazybind", Attribute::NonLazyBind)
1869 .Case("noredzone", Attribute::NoRedZone)
1870 .Case("noreturn", Attribute::NoReturn)
1871 .Case("norecurse", Attribute::NoRecurse)
1872 .Case("nounwind", Attribute::NoUnwind)
1873 .Case("optnone", Attribute::OptimizeNone)
1874 .Case("optsize", Attribute::OptimizeForSize)
1875 .Case("readnone", Attribute::ReadNone)
1876 .Case("readonly", Attribute::ReadOnly)
1877 .Case("argmemonly", Attribute::ArgMemOnly)
1878 .Case("returns_twice", Attribute::ReturnsTwice)
1879 .Case("safestack", Attribute::SafeStack)
1880 .Case("sanitize_address", Attribute::SanitizeAddress)
1881 .Case("sanitize_memory", Attribute::SanitizeMemory)
1882 .Case("sanitize_thread", Attribute::SanitizeThread)
1883 .Case("ssp", Attribute::StackProtect)
1884 .Case("sspreq", Attribute::StackProtectReq)
1885 .Case("sspstrong", Attribute::StackProtectStrong)
1886 .Case("uwtable", Attribute::UWTable)
1887 .Default(Attribute::None);
1890 /// If F has any forced attributes given on the command line, add them.
1891 static bool addForcedAttributes(Function *F) {
1892 bool Changed = false;
1893 for (auto &S : ForceAttributes) {
1894 auto KV = StringRef(S).split(':');
1895 if (KV.first != F->getName())
1898 auto Kind = parseAttrKind(KV.second);
1899 if (Kind == Attribute::None) {
1900 DEBUG(dbgs() << "ForcedAttribute: " << KV.second
1901 << " unknown or not handled!\n");
1904 if (F->hasFnAttribute(Kind))
1912 bool FunctionAttrs::runOnSCC(CallGraphSCC &SCC) {
1913 TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
1914 bool Changed = false;
1916 // We compute dedicated AA results for each function in the SCC as needed. We
1917 // use a lambda referencing external objects so that they live long enough to
1918 // be queried, but we re-use them each time.
1919 Optional<BasicAAResult> BAR;
1920 Optional<AAResults> AAR;
1921 auto AARGetter = [&](Function &F) -> AAResults & {
1922 BAR.emplace(createLegacyPMBasicAAResult(*this, F));
1923 AAR.emplace(createLegacyPMAAResults(*this, F, *BAR));
1927 // Fill SCCNodes with the elements of the SCC. Used for quickly looking up
1928 // whether a given CallGraphNode is in this SCC. Also track whether there are
1929 // any external or opt-none nodes that will prevent us from optimizing any
1931 SCCNodeSet SCCNodes;
1932 bool ExternalNode = false;
1933 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) {
1934 Function *F = (*I)->getFunction();
1935 if (!F || F->hasFnAttribute(Attribute::OptimizeNone)) {
1936 // External node or function we're trying not to optimize - we both avoid
1937 // transform them and avoid leveraging information they provide.
1938 ExternalNode = true;
1942 // When initially processing functions, also infer their prototype
1943 // attributes if they are declarations.
1944 if (F->isDeclaration())
1945 Changed |= inferPrototypeAttributes(*F, *TLI);
1947 Changed |= addForcedAttributes(F);
1951 Changed |= addReadAttrs(SCCNodes, AARGetter);
1952 Changed |= addArgumentAttrs(SCCNodes);
1954 // If we have no external nodes participating in the SCC, we can infer some
1955 // more precise attributes as well.
1956 if (!ExternalNode) {
1957 Changed |= addNoAliasAttrs(SCCNodes);
1958 Changed |= addNonNullAttrs(SCCNodes, *TLI);
1961 Changed |= addNoRecurseAttrs(SCC, Revisit);
1965 bool FunctionAttrs::doFinalization(CallGraph &CG) {
1966 bool Changed = false;
1967 // When iterating over SCCs we visit functions in a bottom-up fashion. Some of
1968 // the rules we have for identifying norecurse functions work best with a
1969 // top-down walk, so look again at all the functions we previously marked as
1970 // worth revisiting, in top-down order.
1971 for (auto &F : reverse(Revisit))
1973 Changed |= addNoRecurseAttrsTopDownOnly(cast<Function>((Value*)F));