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 //===----------------------------------------------------------------------===//
11 /// This file implements interprocedural passes which walk the
12 /// call-graph deducing and/or propagating function attributes.
14 //===----------------------------------------------------------------------===//
16 #include "llvm/Transforms/IPO/FunctionAttrs.h"
17 #include "llvm/ADT/SCCIterator.h"
18 #include "llvm/ADT/STLExtras.h"
19 #include "llvm/ADT/SetVector.h"
20 #include "llvm/ADT/SmallPtrSet.h"
21 #include "llvm/ADT/SmallSet.h"
22 #include "llvm/ADT/SmallVector.h"
23 #include "llvm/ADT/Statistic.h"
24 #include "llvm/Analysis/AliasAnalysis.h"
25 #include "llvm/Analysis/AssumptionCache.h"
26 #include "llvm/Analysis/BasicAliasAnalysis.h"
27 #include "llvm/Analysis/CGSCCPassManager.h"
28 #include "llvm/Analysis/CallGraph.h"
29 #include "llvm/Analysis/CallGraphSCCPass.h"
30 #include "llvm/Analysis/CaptureTracking.h"
31 #include "llvm/Analysis/LazyCallGraph.h"
32 #include "llvm/Analysis/MemoryLocation.h"
33 #include "llvm/Analysis/ValueTracking.h"
34 #include "llvm/IR/Argument.h"
35 #include "llvm/IR/Attributes.h"
36 #include "llvm/IR/BasicBlock.h"
37 #include "llvm/IR/CallSite.h"
38 #include "llvm/IR/Constant.h"
39 #include "llvm/IR/Constants.h"
40 #include "llvm/IR/Function.h"
41 #include "llvm/IR/InstIterator.h"
42 #include "llvm/IR/InstrTypes.h"
43 #include "llvm/IR/Instruction.h"
44 #include "llvm/IR/Instructions.h"
45 #include "llvm/IR/Metadata.h"
46 #include "llvm/IR/PassManager.h"
47 #include "llvm/IR/Type.h"
48 #include "llvm/IR/Use.h"
49 #include "llvm/IR/User.h"
50 #include "llvm/IR/Value.h"
51 #include "llvm/Pass.h"
52 #include "llvm/Support/Casting.h"
53 #include "llvm/Support/CommandLine.h"
54 #include "llvm/Support/Compiler.h"
55 #include "llvm/Support/Debug.h"
56 #include "llvm/Support/ErrorHandling.h"
57 #include "llvm/Support/raw_ostream.h"
58 #include "llvm/Transforms/IPO.h"
66 #define DEBUG_TYPE "functionattrs"
68 STATISTIC(NumReadNone, "Number of functions marked readnone");
69 STATISTIC(NumReadOnly, "Number of functions marked readonly");
70 STATISTIC(NumNoCapture, "Number of arguments marked nocapture");
71 STATISTIC(NumReturned, "Number of arguments marked returned");
72 STATISTIC(NumReadNoneArg, "Number of arguments marked readnone");
73 STATISTIC(NumReadOnlyArg, "Number of arguments marked readonly");
74 STATISTIC(NumNoAlias, "Number of function returns marked noalias");
75 STATISTIC(NumNonNullReturn, "Number of function returns marked nonnull");
76 STATISTIC(NumNoRecurse, "Number of functions marked as norecurse");
78 // FIXME: This is disabled by default to avoid exposing security vulnerabilities
79 // in C/C++ code compiled by clang:
80 // http://lists.llvm.org/pipermail/cfe-dev/2017-January/052066.html
81 static cl::opt<bool> EnableNonnullArgPropagation(
82 "enable-nonnull-arg-prop", cl::Hidden,
83 cl::desc("Try to propagate nonnull argument attributes from callsites to "
84 "caller functions."));
88 using SCCNodeSet = SmallSetVector<Function *, 8>;
90 } // end anonymous namespace
92 /// Returns the memory access attribute for function F using AAR for AA results,
93 /// where SCCNodes is the current SCC.
95 /// If ThisBody is true, this function may examine the function body and will
96 /// return a result pertaining to this copy of the function. If it is false, the
97 /// result will be based only on AA results for the function declaration; it
98 /// will be assumed that some other (perhaps less optimized) version of the
99 /// function may be selected at link time.
100 static MemoryAccessKind checkFunctionMemoryAccess(Function &F, bool ThisBody,
102 const SCCNodeSet &SCCNodes) {
103 FunctionModRefBehavior MRB = AAR.getModRefBehavior(&F);
104 if (MRB == FMRB_DoesNotAccessMemory)
109 if (AliasAnalysis::onlyReadsMemory(MRB))
112 // Conservatively assume it writes to memory.
116 // Scan the function body for instructions that may read or write memory.
117 bool ReadsMemory = false;
118 for (inst_iterator II = inst_begin(F), E = inst_end(F); II != E; ++II) {
119 Instruction *I = &*II;
121 // Some instructions can be ignored even if they read or write memory.
122 // Detect these now, skipping to the next instruction if one is found.
123 CallSite CS(cast<Value>(I));
125 // Ignore calls to functions in the same SCC, as long as the call sites
126 // don't have operand bundles. Calls with operand bundles are allowed to
127 // have memory effects not described by the memory effects of the call
129 if (!CS.hasOperandBundles() && CS.getCalledFunction() &&
130 SCCNodes.count(CS.getCalledFunction()))
132 FunctionModRefBehavior MRB = AAR.getModRefBehavior(CS);
133 ModRefInfo MRI = createModRefInfo(MRB);
135 // If the call doesn't access memory, we're done.
139 if (!AliasAnalysis::onlyAccessesArgPointees(MRB)) {
140 // The call could access any memory. If that includes writes, give up.
143 // If it reads, note it.
149 // Check whether all pointer arguments point to local memory, and
150 // ignore calls that only access local memory.
151 for (CallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end();
154 if (!Arg->getType()->isPtrOrPtrVectorTy())
158 I->getAAMetadata(AAInfo);
159 MemoryLocation Loc(Arg, MemoryLocation::UnknownSize, AAInfo);
161 // Skip accesses to local or constant memory as they don't impact the
162 // externally visible mod/ref behavior.
163 if (AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true))
167 // Writes non-local memory. Give up.
170 // Ok, it reads non-local memory.
174 } else if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
175 // Ignore non-volatile loads from local memory. (Atomic is okay here.)
176 if (!LI->isVolatile()) {
177 MemoryLocation Loc = MemoryLocation::get(LI);
178 if (AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true))
181 } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
182 // Ignore non-volatile stores to local memory. (Atomic is okay here.)
183 if (!SI->isVolatile()) {
184 MemoryLocation Loc = MemoryLocation::get(SI);
185 if (AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true))
188 } else if (VAArgInst *VI = dyn_cast<VAArgInst>(I)) {
189 // Ignore vaargs on local memory.
190 MemoryLocation Loc = MemoryLocation::get(VI);
191 if (AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true))
195 // Any remaining instructions need to be taken seriously! Check if they
196 // read or write memory.
197 if (I->mayWriteToMemory())
198 // Writes memory. Just give up.
201 // If this instruction may read memory, remember that.
202 ReadsMemory |= I->mayReadFromMemory();
205 return ReadsMemory ? MAK_ReadOnly : MAK_ReadNone;
208 MemoryAccessKind llvm::computeFunctionBodyMemoryAccess(Function &F,
210 return checkFunctionMemoryAccess(F, /*ThisBody=*/true, AAR, {});
213 /// Deduce readonly/readnone attributes for the SCC.
214 template <typename AARGetterT>
215 static bool addReadAttrs(const SCCNodeSet &SCCNodes, AARGetterT &&AARGetter) {
216 // Check if any of the functions in the SCC read or write memory. If they
217 // write memory then they can't be marked readnone or readonly.
218 bool ReadsMemory = false;
219 for (Function *F : SCCNodes) {
220 // Call the callable parameter to look up AA results for this function.
221 AAResults &AAR = AARGetter(*F);
223 // Non-exact function definitions may not be selected at link time, and an
224 // alternative version that writes to memory may be selected. See the
225 // comment on GlobalValue::isDefinitionExact for more details.
226 switch (checkFunctionMemoryAccess(*F, F->hasExactDefinition(),
239 // Success! Functions in this SCC do not access memory, or only read memory.
240 // Give them the appropriate attribute.
241 bool MadeChange = false;
242 for (Function *F : SCCNodes) {
243 if (F->doesNotAccessMemory())
247 if (F->onlyReadsMemory() && ReadsMemory)
253 // Clear out any existing attributes.
254 F->removeFnAttr(Attribute::ReadOnly);
255 F->removeFnAttr(Attribute::ReadNone);
257 // Add in the new attribute.
258 F->addFnAttr(ReadsMemory ? Attribute::ReadOnly : Attribute::ReadNone);
271 /// For a given pointer Argument, this retains a list of Arguments of functions
272 /// in the same SCC that the pointer data flows into. We use this to build an
273 /// SCC of the arguments.
274 struct ArgumentGraphNode {
275 Argument *Definition;
276 SmallVector<ArgumentGraphNode *, 4> Uses;
279 class ArgumentGraph {
280 // We store pointers to ArgumentGraphNode objects, so it's important that
281 // that they not move around upon insert.
282 using ArgumentMapTy = std::map<Argument *, ArgumentGraphNode>;
284 ArgumentMapTy ArgumentMap;
286 // There is no root node for the argument graph, in fact:
287 // void f(int *x, int *y) { if (...) f(x, y); }
288 // is an example where the graph is disconnected. The SCCIterator requires a
289 // single entry point, so we maintain a fake ("synthetic") root node that
290 // uses every node. Because the graph is directed and nothing points into
291 // the root, it will not participate in any SCCs (except for its own).
292 ArgumentGraphNode SyntheticRoot;
295 ArgumentGraph() { SyntheticRoot.Definition = nullptr; }
297 using iterator = SmallVectorImpl<ArgumentGraphNode *>::iterator;
299 iterator begin() { return SyntheticRoot.Uses.begin(); }
300 iterator end() { return SyntheticRoot.Uses.end(); }
301 ArgumentGraphNode *getEntryNode() { return &SyntheticRoot; }
303 ArgumentGraphNode *operator[](Argument *A) {
304 ArgumentGraphNode &Node = ArgumentMap[A];
306 SyntheticRoot.Uses.push_back(&Node);
311 /// This tracker checks whether callees are in the SCC, and if so it does not
312 /// consider that a capture, instead adding it to the "Uses" list and
313 /// continuing with the analysis.
314 struct ArgumentUsesTracker : public CaptureTracker {
315 ArgumentUsesTracker(const SCCNodeSet &SCCNodes) : SCCNodes(SCCNodes) {}
317 void tooManyUses() override { Captured = true; }
319 bool captured(const Use *U) override {
320 CallSite CS(U->getUser());
321 if (!CS.getInstruction()) {
326 Function *F = CS.getCalledFunction();
327 if (!F || !F->hasExactDefinition() || !SCCNodes.count(F)) {
332 // Note: the callee and the two successor blocks *follow* the argument
333 // operands. This means there is no need to adjust UseIndex to account for
337 std::distance(const_cast<const Use *>(CS.arg_begin()), U);
339 assert(UseIndex < CS.data_operands_size() &&
340 "Indirect function calls should have been filtered above!");
342 if (UseIndex >= CS.getNumArgOperands()) {
343 // Data operand, but not a argument operand -- must be a bundle operand
344 assert(CS.hasOperandBundles() && "Must be!");
346 // CaptureTracking told us that we're being captured by an operand bundle
347 // use. In this case it does not matter if the callee is within our SCC
348 // or not -- we've been captured in some unknown way, and we have to be
354 if (UseIndex >= F->arg_size()) {
355 assert(F->isVarArg() && "More params than args in non-varargs call");
360 Uses.push_back(&*std::next(F->arg_begin(), UseIndex));
364 // True only if certainly captured (used outside our SCC).
365 bool Captured = false;
367 // Uses within our SCC.
368 SmallVector<Argument *, 4> Uses;
370 const SCCNodeSet &SCCNodes;
373 } // end anonymous namespace
377 template <> struct GraphTraits<ArgumentGraphNode *> {
378 using NodeRef = ArgumentGraphNode *;
379 using ChildIteratorType = SmallVectorImpl<ArgumentGraphNode *>::iterator;
381 static NodeRef getEntryNode(NodeRef A) { return A; }
382 static ChildIteratorType child_begin(NodeRef N) { return N->Uses.begin(); }
383 static ChildIteratorType child_end(NodeRef N) { return N->Uses.end(); }
387 struct GraphTraits<ArgumentGraph *> : public GraphTraits<ArgumentGraphNode *> {
388 static NodeRef getEntryNode(ArgumentGraph *AG) { return AG->getEntryNode(); }
390 static ChildIteratorType nodes_begin(ArgumentGraph *AG) {
394 static ChildIteratorType nodes_end(ArgumentGraph *AG) { return AG->end(); }
397 } // end namespace llvm
399 /// Returns Attribute::None, Attribute::ReadOnly or Attribute::ReadNone.
400 static Attribute::AttrKind
401 determinePointerReadAttrs(Argument *A,
402 const SmallPtrSet<Argument *, 8> &SCCNodes) {
403 SmallVector<Use *, 32> Worklist;
404 SmallSet<Use *, 32> Visited;
406 // inalloca arguments are always clobbered by the call.
407 if (A->hasInAllocaAttr())
408 return Attribute::None;
411 // We don't need to track IsWritten. If A is written to, return immediately.
413 for (Use &U : A->uses()) {
415 Worklist.push_back(&U);
418 while (!Worklist.empty()) {
419 Use *U = Worklist.pop_back_val();
420 Instruction *I = cast<Instruction>(U->getUser());
422 switch (I->getOpcode()) {
423 case Instruction::BitCast:
424 case Instruction::GetElementPtr:
425 case Instruction::PHI:
426 case Instruction::Select:
427 case Instruction::AddrSpaceCast:
428 // The original value is not read/written via this if the new value isn't.
429 for (Use &UU : I->uses())
430 if (Visited.insert(&UU).second)
431 Worklist.push_back(&UU);
434 case Instruction::Call:
435 case Instruction::Invoke: {
436 bool Captures = true;
438 if (I->getType()->isVoidTy())
441 auto AddUsersToWorklistIfCapturing = [&] {
443 for (Use &UU : I->uses())
444 if (Visited.insert(&UU).second)
445 Worklist.push_back(&UU);
449 if (CS.doesNotAccessMemory()) {
450 AddUsersToWorklistIfCapturing();
454 Function *F = CS.getCalledFunction();
456 if (CS.onlyReadsMemory()) {
458 AddUsersToWorklistIfCapturing();
461 return Attribute::None;
464 // Note: the callee and the two successor blocks *follow* the argument
465 // operands. This means there is no need to adjust UseIndex to account
468 unsigned UseIndex = std::distance(CS.arg_begin(), U);
470 // U cannot be the callee operand use: since we're exploring the
471 // transitive uses of an Argument, having such a use be a callee would
472 // imply the CallSite is an indirect call or invoke; and we'd take the
474 assert(UseIndex < CS.data_operands_size() &&
475 "Data operand use expected!");
477 bool IsOperandBundleUse = UseIndex >= CS.getNumArgOperands();
479 if (UseIndex >= F->arg_size() && !IsOperandBundleUse) {
480 assert(F->isVarArg() && "More params than args in non-varargs call");
481 return Attribute::None;
484 Captures &= !CS.doesNotCapture(UseIndex);
486 // Since the optimizer (by design) cannot see the data flow corresponding
487 // to a operand bundle use, these cannot participate in the optimistic SCC
488 // analysis. Instead, we model the operand bundle uses as arguments in
489 // call to a function external to the SCC.
490 if (IsOperandBundleUse ||
491 !SCCNodes.count(&*std::next(F->arg_begin(), UseIndex))) {
493 // The accessors used on CallSite here do the right thing for calls and
494 // invokes with operand bundles.
496 if (!CS.onlyReadsMemory() && !CS.onlyReadsMemory(UseIndex))
497 return Attribute::None;
498 if (!CS.doesNotAccessMemory(UseIndex))
502 AddUsersToWorklistIfCapturing();
506 case Instruction::Load:
507 // A volatile load has side effects beyond what readonly can be relied
509 if (cast<LoadInst>(I)->isVolatile())
510 return Attribute::None;
515 case Instruction::ICmp:
516 case Instruction::Ret:
520 return Attribute::None;
524 return IsRead ? Attribute::ReadOnly : Attribute::ReadNone;
527 /// Deduce returned attributes for the SCC.
528 static bool addArgumentReturnedAttrs(const SCCNodeSet &SCCNodes) {
529 bool Changed = false;
531 // Check each function in turn, determining if an argument is always returned.
532 for (Function *F : SCCNodes) {
533 // We can infer and propagate function attributes only when we know that the
534 // definition we'll get at link time is *exactly* the definition we see now.
535 // For more details, see GlobalValue::mayBeDerefined.
536 if (!F->hasExactDefinition())
539 if (F->getReturnType()->isVoidTy())
542 // There is nothing to do if an argument is already marked as 'returned'.
543 if (llvm::any_of(F->args(),
544 [](const Argument &Arg) { return Arg.hasReturnedAttr(); }))
547 auto FindRetArg = [&]() -> Value * {
548 Value *RetArg = nullptr;
549 for (BasicBlock &BB : *F)
550 if (auto *Ret = dyn_cast<ReturnInst>(BB.getTerminator())) {
551 // Note that stripPointerCasts should look through functions with
552 // returned arguments.
553 Value *RetVal = Ret->getReturnValue()->stripPointerCasts();
554 if (!isa<Argument>(RetVal) || RetVal->getType() != F->getReturnType())
559 else if (RetArg != RetVal)
566 if (Value *RetArg = FindRetArg()) {
567 auto *A = cast<Argument>(RetArg);
568 A->addAttr(Attribute::Returned);
577 /// If a callsite has arguments that are also arguments to the parent function,
578 /// try to propagate attributes from the callsite's arguments to the parent's
579 /// arguments. This may be important because inlining can cause information loss
580 /// when attribute knowledge disappears with the inlined call.
581 static bool addArgumentAttrsFromCallsites(Function &F) {
582 if (!EnableNonnullArgPropagation)
585 bool Changed = false;
587 // For an argument attribute to transfer from a callsite to the parent, the
588 // call must be guaranteed to execute every time the parent is called.
589 // Conservatively, just check for calls in the entry block that are guaranteed
591 // TODO: This could be enhanced by testing if the callsite post-dominates the
592 // entry block or by doing simple forward walks or backward walks to the
594 BasicBlock &Entry = F.getEntryBlock();
595 for (Instruction &I : Entry) {
596 if (auto CS = CallSite(&I)) {
597 if (auto *CalledFunc = CS.getCalledFunction()) {
598 for (auto &CSArg : CalledFunc->args()) {
599 if (!CSArg.hasNonNullAttr())
602 // If the non-null callsite argument operand is an argument to 'F'
603 // (the caller) and the call is guaranteed to execute, then the value
604 // must be non-null throughout 'F'.
605 auto *FArg = dyn_cast<Argument>(CS.getArgOperand(CSArg.getArgNo()));
606 if (FArg && !FArg->hasNonNullAttr()) {
607 FArg->addAttr(Attribute::NonNull);
613 if (!isGuaranteedToTransferExecutionToSuccessor(&I))
620 /// Deduce nocapture attributes for the SCC.
621 static bool addArgumentAttrs(const SCCNodeSet &SCCNodes) {
622 bool Changed = false;
626 // Check each function in turn, determining which pointer arguments are not
628 for (Function *F : SCCNodes) {
629 // We can infer and propagate function attributes only when we know that the
630 // definition we'll get at link time is *exactly* the definition we see now.
631 // For more details, see GlobalValue::mayBeDerefined.
632 if (!F->hasExactDefinition())
635 Changed |= addArgumentAttrsFromCallsites(*F);
637 // Functions that are readonly (or readnone) and nounwind and don't return
638 // a value can't capture arguments. Don't analyze them.
639 if (F->onlyReadsMemory() && F->doesNotThrow() &&
640 F->getReturnType()->isVoidTy()) {
641 for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end(); A != E;
643 if (A->getType()->isPointerTy() && !A->hasNoCaptureAttr()) {
644 A->addAttr(Attribute::NoCapture);
652 for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end(); A != E;
654 if (!A->getType()->isPointerTy())
656 bool HasNonLocalUses = false;
657 if (!A->hasNoCaptureAttr()) {
658 ArgumentUsesTracker Tracker(SCCNodes);
659 PointerMayBeCaptured(&*A, &Tracker);
660 if (!Tracker.Captured) {
661 if (Tracker.Uses.empty()) {
662 // If it's trivially not captured, mark it nocapture now.
663 A->addAttr(Attribute::NoCapture);
667 // If it's not trivially captured and not trivially not captured,
668 // then it must be calling into another function in our SCC. Save
669 // its particulars for Argument-SCC analysis later.
670 ArgumentGraphNode *Node = AG[&*A];
671 for (Argument *Use : Tracker.Uses) {
672 Node->Uses.push_back(AG[Use]);
674 HasNonLocalUses = true;
678 // Otherwise, it's captured. Don't bother doing SCC analysis on it.
680 if (!HasNonLocalUses && !A->onlyReadsMemory()) {
681 // Can we determine that it's readonly/readnone without doing an SCC?
682 // Note that we don't allow any calls at all here, or else our result
683 // will be dependent on the iteration order through the functions in the
685 SmallPtrSet<Argument *, 8> Self;
687 Attribute::AttrKind R = determinePointerReadAttrs(&*A, Self);
688 if (R != Attribute::None) {
691 R == Attribute::ReadOnly ? ++NumReadOnlyArg : ++NumReadNoneArg;
697 // The graph we've collected is partial because we stopped scanning for
698 // argument uses once we solved the argument trivially. These partial nodes
699 // show up as ArgumentGraphNode objects with an empty Uses list, and for
700 // these nodes the final decision about whether they capture has already been
701 // made. If the definition doesn't have a 'nocapture' attribute by now, it
704 for (scc_iterator<ArgumentGraph *> I = scc_begin(&AG); !I.isAtEnd(); ++I) {
705 const std::vector<ArgumentGraphNode *> &ArgumentSCC = *I;
706 if (ArgumentSCC.size() == 1) {
707 if (!ArgumentSCC[0]->Definition)
708 continue; // synthetic root node
710 // eg. "void f(int* x) { if (...) f(x); }"
711 if (ArgumentSCC[0]->Uses.size() == 1 &&
712 ArgumentSCC[0]->Uses[0] == ArgumentSCC[0]) {
713 Argument *A = ArgumentSCC[0]->Definition;
714 A->addAttr(Attribute::NoCapture);
721 bool SCCCaptured = false;
722 for (auto I = ArgumentSCC.begin(), E = ArgumentSCC.end();
723 I != E && !SCCCaptured; ++I) {
724 ArgumentGraphNode *Node = *I;
725 if (Node->Uses.empty()) {
726 if (!Node->Definition->hasNoCaptureAttr())
733 SmallPtrSet<Argument *, 8> ArgumentSCCNodes;
734 // Fill ArgumentSCCNodes with the elements of the ArgumentSCC. Used for
735 // quickly looking up whether a given Argument is in this ArgumentSCC.
736 for (ArgumentGraphNode *I : ArgumentSCC) {
737 ArgumentSCCNodes.insert(I->Definition);
740 for (auto I = ArgumentSCC.begin(), E = ArgumentSCC.end();
741 I != E && !SCCCaptured; ++I) {
742 ArgumentGraphNode *N = *I;
743 for (ArgumentGraphNode *Use : N->Uses) {
744 Argument *A = Use->Definition;
745 if (A->hasNoCaptureAttr() || ArgumentSCCNodes.count(A))
754 for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) {
755 Argument *A = ArgumentSCC[i]->Definition;
756 A->addAttr(Attribute::NoCapture);
761 // We also want to compute readonly/readnone. With a small number of false
762 // negatives, we can assume that any pointer which is captured isn't going
763 // to be provably readonly or readnone, since by definition we can't
764 // analyze all uses of a captured pointer.
766 // The false negatives happen when the pointer is captured by a function
767 // that promises readonly/readnone behaviour on the pointer, then the
768 // pointer's lifetime ends before anything that writes to arbitrary memory.
769 // Also, a readonly/readnone pointer may be returned, but returning a
770 // pointer is capturing it.
772 Attribute::AttrKind ReadAttr = Attribute::ReadNone;
773 for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) {
774 Argument *A = ArgumentSCC[i]->Definition;
775 Attribute::AttrKind K = determinePointerReadAttrs(A, ArgumentSCCNodes);
776 if (K == Attribute::ReadNone)
778 if (K == Attribute::ReadOnly) {
779 ReadAttr = Attribute::ReadOnly;
786 if (ReadAttr != Attribute::None) {
787 for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) {
788 Argument *A = ArgumentSCC[i]->Definition;
789 // Clear out existing readonly/readnone attributes
790 A->removeAttr(Attribute::ReadOnly);
791 A->removeAttr(Attribute::ReadNone);
792 A->addAttr(ReadAttr);
793 ReadAttr == Attribute::ReadOnly ? ++NumReadOnlyArg : ++NumReadNoneArg;
802 /// Tests whether a function is "malloc-like".
804 /// A function is "malloc-like" if it returns either null or a pointer that
805 /// doesn't alias any other pointer visible to the caller.
806 static bool isFunctionMallocLike(Function *F, const SCCNodeSet &SCCNodes) {
807 SmallSetVector<Value *, 8> FlowsToReturn;
808 for (BasicBlock &BB : *F)
809 if (ReturnInst *Ret = dyn_cast<ReturnInst>(BB.getTerminator()))
810 FlowsToReturn.insert(Ret->getReturnValue());
812 for (unsigned i = 0; i != FlowsToReturn.size(); ++i) {
813 Value *RetVal = FlowsToReturn[i];
815 if (Constant *C = dyn_cast<Constant>(RetVal)) {
816 if (!C->isNullValue() && !isa<UndefValue>(C))
822 if (isa<Argument>(RetVal))
825 if (Instruction *RVI = dyn_cast<Instruction>(RetVal))
826 switch (RVI->getOpcode()) {
827 // Extend the analysis by looking upwards.
828 case Instruction::BitCast:
829 case Instruction::GetElementPtr:
830 case Instruction::AddrSpaceCast:
831 FlowsToReturn.insert(RVI->getOperand(0));
833 case Instruction::Select: {
834 SelectInst *SI = cast<SelectInst>(RVI);
835 FlowsToReturn.insert(SI->getTrueValue());
836 FlowsToReturn.insert(SI->getFalseValue());
839 case Instruction::PHI: {
840 PHINode *PN = cast<PHINode>(RVI);
841 for (Value *IncValue : PN->incoming_values())
842 FlowsToReturn.insert(IncValue);
846 // Check whether the pointer came from an allocation.
847 case Instruction::Alloca:
849 case Instruction::Call:
850 case Instruction::Invoke: {
852 if (CS.hasRetAttr(Attribute::NoAlias))
854 if (CS.getCalledFunction() && SCCNodes.count(CS.getCalledFunction()))
859 return false; // Did not come from an allocation.
862 if (PointerMayBeCaptured(RetVal, false, /*StoreCaptures=*/false))
869 /// Deduce noalias attributes for the SCC.
870 static bool addNoAliasAttrs(const SCCNodeSet &SCCNodes) {
871 // Check each function in turn, determining which functions return noalias
873 for (Function *F : SCCNodes) {
875 if (F->returnDoesNotAlias())
878 // We can infer and propagate function attributes only when we know that the
879 // definition we'll get at link time is *exactly* the definition we see now.
880 // For more details, see GlobalValue::mayBeDerefined.
881 if (!F->hasExactDefinition())
884 // We annotate noalias return values, which are only applicable to
886 if (!F->getReturnType()->isPointerTy())
889 if (!isFunctionMallocLike(F, SCCNodes))
893 bool MadeChange = false;
894 for (Function *F : SCCNodes) {
895 if (F->returnDoesNotAlias() ||
896 !F->getReturnType()->isPointerTy())
899 F->setReturnDoesNotAlias();
907 /// Tests whether this function is known to not return null.
909 /// Requires that the function returns a pointer.
911 /// Returns true if it believes the function will not return a null, and sets
912 /// \p Speculative based on whether the returned conclusion is a speculative
913 /// conclusion due to SCC calls.
914 static bool isReturnNonNull(Function *F, const SCCNodeSet &SCCNodes,
916 assert(F->getReturnType()->isPointerTy() &&
917 "nonnull only meaningful on pointer types");
920 SmallSetVector<Value *, 8> FlowsToReturn;
921 for (BasicBlock &BB : *F)
922 if (auto *Ret = dyn_cast<ReturnInst>(BB.getTerminator()))
923 FlowsToReturn.insert(Ret->getReturnValue());
925 auto &DL = F->getParent()->getDataLayout();
927 for (unsigned i = 0; i != FlowsToReturn.size(); ++i) {
928 Value *RetVal = FlowsToReturn[i];
930 // If this value is locally known to be non-null, we're good
931 if (isKnownNonZero(RetVal, DL))
934 // Otherwise, we need to look upwards since we can't make any local
936 Instruction *RVI = dyn_cast<Instruction>(RetVal);
939 switch (RVI->getOpcode()) {
940 // Extend the analysis by looking upwards.
941 case Instruction::BitCast:
942 case Instruction::GetElementPtr:
943 case Instruction::AddrSpaceCast:
944 FlowsToReturn.insert(RVI->getOperand(0));
946 case Instruction::Select: {
947 SelectInst *SI = cast<SelectInst>(RVI);
948 FlowsToReturn.insert(SI->getTrueValue());
949 FlowsToReturn.insert(SI->getFalseValue());
952 case Instruction::PHI: {
953 PHINode *PN = cast<PHINode>(RVI);
954 for (int i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
955 FlowsToReturn.insert(PN->getIncomingValue(i));
958 case Instruction::Call:
959 case Instruction::Invoke: {
961 Function *Callee = CS.getCalledFunction();
962 // A call to a node within the SCC is assumed to return null until
964 if (Callee && SCCNodes.count(Callee)) {
971 return false; // Unknown source, may be null
973 llvm_unreachable("should have either continued or returned");
979 /// Deduce nonnull attributes for the SCC.
980 static bool addNonNullAttrs(const SCCNodeSet &SCCNodes) {
981 // Speculative that all functions in the SCC return only nonnull
982 // pointers. We may refute this as we analyze functions.
983 bool SCCReturnsNonNull = true;
985 bool MadeChange = false;
987 // Check each function in turn, determining which functions return nonnull
989 for (Function *F : SCCNodes) {
991 if (F->getAttributes().hasAttribute(AttributeList::ReturnIndex,
995 // We can infer and propagate function attributes only when we know that the
996 // definition we'll get at link time is *exactly* the definition we see now.
997 // For more details, see GlobalValue::mayBeDerefined.
998 if (!F->hasExactDefinition())
1001 // We annotate nonnull return values, which are only applicable to
1003 if (!F->getReturnType()->isPointerTy())
1006 bool Speculative = false;
1007 if (isReturnNonNull(F, SCCNodes, Speculative)) {
1009 // Mark the function eagerly since we may discover a function
1010 // which prevents us from speculating about the entire SCC
1011 DEBUG(dbgs() << "Eagerly marking " << F->getName() << " as nonnull\n");
1012 F->addAttribute(AttributeList::ReturnIndex, Attribute::NonNull);
1018 // At least one function returns something which could be null, can't
1019 // speculate any more.
1020 SCCReturnsNonNull = false;
1023 if (SCCReturnsNonNull) {
1024 for (Function *F : SCCNodes) {
1025 if (F->getAttributes().hasAttribute(AttributeList::ReturnIndex,
1026 Attribute::NonNull) ||
1027 !F->getReturnType()->isPointerTy())
1030 DEBUG(dbgs() << "SCC marking " << F->getName() << " as nonnull\n");
1031 F->addAttribute(AttributeList::ReturnIndex, Attribute::NonNull);
1040 /// Remove the convergent attribute from all functions in the SCC if every
1041 /// callsite within the SCC is not convergent (except for calls to functions
1042 /// within the SCC). Returns true if changes were made.
1043 static bool removeConvergentAttrs(const SCCNodeSet &SCCNodes) {
1044 // For every function in SCC, ensure that either
1045 // * it is not convergent, or
1046 // * we can remove its convergent attribute.
1047 bool HasConvergentFn = false;
1048 for (Function *F : SCCNodes) {
1049 if (!F->isConvergent()) continue;
1050 HasConvergentFn = true;
1052 // Can't remove convergent from function declarations.
1053 if (F->isDeclaration()) return false;
1055 // Can't remove convergent if any of our functions has a convergent call to a
1056 // function not in the SCC.
1057 for (Instruction &I : instructions(*F)) {
1059 // Bail if CS is a convergent call to a function not in the SCC.
1060 if (CS && CS.isConvergent() &&
1061 SCCNodes.count(CS.getCalledFunction()) == 0)
1066 // If the SCC doesn't have any convergent functions, we have nothing to do.
1067 if (!HasConvergentFn) return false;
1069 // If we got here, all of the calls the SCC makes to functions not in the SCC
1070 // are non-convergent. Therefore all of the SCC's functions can also be made
1071 // non-convergent. We'll remove the attr from the callsites in
1072 // InstCombineCalls.
1073 for (Function *F : SCCNodes) {
1074 if (!F->isConvergent()) continue;
1076 DEBUG(dbgs() << "Removing convergent attr from fn " << F->getName()
1078 F->setNotConvergent();
1083 static bool setDoesNotRecurse(Function &F) {
1084 if (F.doesNotRecurse())
1086 F.setDoesNotRecurse();
1091 static bool addNoRecurseAttrs(const SCCNodeSet &SCCNodes) {
1092 // Try and identify functions that do not recurse.
1094 // If the SCC contains multiple nodes we know for sure there is recursion.
1095 if (SCCNodes.size() != 1)
1098 Function *F = *SCCNodes.begin();
1099 if (!F || F->isDeclaration() || F->doesNotRecurse())
1102 // If all of the calls in F are identifiable and are to norecurse functions, F
1103 // is norecurse. This check also detects self-recursion as F is not currently
1104 // marked norecurse, so any called from F to F will not be marked norecurse.
1105 for (Instruction &I : instructions(*F))
1106 if (auto CS = CallSite(&I)) {
1107 Function *Callee = CS.getCalledFunction();
1108 if (!Callee || Callee == F || !Callee->doesNotRecurse())
1109 // Function calls a potentially recursive function.
1113 // Every call was to a non-recursive function other than this function, and
1114 // we have no indirect recursion as the SCC size is one. This function cannot
1116 return setDoesNotRecurse(*F);
1119 PreservedAnalyses PostOrderFunctionAttrsPass::run(LazyCallGraph::SCC &C,
1120 CGSCCAnalysisManager &AM,
1122 CGSCCUpdateResult &) {
1123 FunctionAnalysisManager &FAM =
1124 AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C, CG).getManager();
1126 // We pass a lambda into functions to wire them up to the analysis manager
1127 // for getting function analyses.
1128 auto AARGetter = [&](Function &F) -> AAResults & {
1129 return FAM.getResult<AAManager>(F);
1132 // Fill SCCNodes with the elements of the SCC. Also track whether there are
1133 // any external or opt-none nodes that will prevent us from optimizing any
1135 SCCNodeSet SCCNodes;
1136 bool HasUnknownCall = false;
1137 for (LazyCallGraph::Node &N : C) {
1138 Function &F = N.getFunction();
1139 if (F.hasFnAttribute(Attribute::OptimizeNone)) {
1140 // Treat any function we're trying not to optimize as if it were an
1141 // indirect call and omit it from the node set used below.
1142 HasUnknownCall = true;
1145 // Track whether any functions in this SCC have an unknown call edge.
1146 // Note: if this is ever a performance hit, we can common it with
1147 // subsequent routines which also do scans over the instructions of the
1149 if (!HasUnknownCall)
1150 for (Instruction &I : instructions(F))
1151 if (auto CS = CallSite(&I))
1152 if (!CS.getCalledFunction()) {
1153 HasUnknownCall = true;
1157 SCCNodes.insert(&F);
1160 bool Changed = false;
1161 Changed |= addArgumentReturnedAttrs(SCCNodes);
1162 Changed |= addReadAttrs(SCCNodes, AARGetter);
1163 Changed |= addArgumentAttrs(SCCNodes);
1165 // If we have no external nodes participating in the SCC, we can deduce some
1166 // more precise attributes as well.
1167 if (!HasUnknownCall) {
1168 Changed |= addNoAliasAttrs(SCCNodes);
1169 Changed |= addNonNullAttrs(SCCNodes);
1170 Changed |= removeConvergentAttrs(SCCNodes);
1171 Changed |= addNoRecurseAttrs(SCCNodes);
1174 return Changed ? PreservedAnalyses::none() : PreservedAnalyses::all();
1179 struct PostOrderFunctionAttrsLegacyPass : public CallGraphSCCPass {
1180 // Pass identification, replacement for typeid
1183 PostOrderFunctionAttrsLegacyPass() : CallGraphSCCPass(ID) {
1184 initializePostOrderFunctionAttrsLegacyPassPass(
1185 *PassRegistry::getPassRegistry());
1188 bool runOnSCC(CallGraphSCC &SCC) override;
1190 void getAnalysisUsage(AnalysisUsage &AU) const override {
1191 AU.setPreservesCFG();
1192 AU.addRequired<AssumptionCacheTracker>();
1193 getAAResultsAnalysisUsage(AU);
1194 CallGraphSCCPass::getAnalysisUsage(AU);
1198 } // end anonymous namespace
1200 char PostOrderFunctionAttrsLegacyPass::ID = 0;
1201 INITIALIZE_PASS_BEGIN(PostOrderFunctionAttrsLegacyPass, "functionattrs",
1202 "Deduce function attributes", false, false)
1203 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
1204 INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass)
1205 INITIALIZE_PASS_END(PostOrderFunctionAttrsLegacyPass, "functionattrs",
1206 "Deduce function attributes", false, false)
1208 Pass *llvm::createPostOrderFunctionAttrsLegacyPass() {
1209 return new PostOrderFunctionAttrsLegacyPass();
1212 template <typename AARGetterT>
1213 static bool runImpl(CallGraphSCC &SCC, AARGetterT AARGetter) {
1214 bool Changed = false;
1216 // Fill SCCNodes with the elements of the SCC. Used for quickly looking up
1217 // whether a given CallGraphNode is in this SCC. Also track whether there are
1218 // any external or opt-none nodes that will prevent us from optimizing any
1220 SCCNodeSet SCCNodes;
1221 bool ExternalNode = false;
1222 for (CallGraphNode *I : SCC) {
1223 Function *F = I->getFunction();
1224 if (!F || F->hasFnAttribute(Attribute::OptimizeNone)) {
1225 // External node or function we're trying not to optimize - we both avoid
1226 // transform them and avoid leveraging information they provide.
1227 ExternalNode = true;
1234 // Skip it if the SCC only contains optnone functions.
1235 if (SCCNodes.empty())
1238 Changed |= addArgumentReturnedAttrs(SCCNodes);
1239 Changed |= addReadAttrs(SCCNodes, AARGetter);
1240 Changed |= addArgumentAttrs(SCCNodes);
1242 // If we have no external nodes participating in the SCC, we can deduce some
1243 // more precise attributes as well.
1244 if (!ExternalNode) {
1245 Changed |= addNoAliasAttrs(SCCNodes);
1246 Changed |= addNonNullAttrs(SCCNodes);
1247 Changed |= removeConvergentAttrs(SCCNodes);
1248 Changed |= addNoRecurseAttrs(SCCNodes);
1254 bool PostOrderFunctionAttrsLegacyPass::runOnSCC(CallGraphSCC &SCC) {
1257 return runImpl(SCC, LegacyAARGetter(*this));
1262 struct ReversePostOrderFunctionAttrsLegacyPass : public ModulePass {
1263 // Pass identification, replacement for typeid
1266 ReversePostOrderFunctionAttrsLegacyPass() : ModulePass(ID) {
1267 initializeReversePostOrderFunctionAttrsLegacyPassPass(
1268 *PassRegistry::getPassRegistry());
1271 bool runOnModule(Module &M) override;
1273 void getAnalysisUsage(AnalysisUsage &AU) const override {
1274 AU.setPreservesCFG();
1275 AU.addRequired<CallGraphWrapperPass>();
1276 AU.addPreserved<CallGraphWrapperPass>();
1280 } // end anonymous namespace
1282 char ReversePostOrderFunctionAttrsLegacyPass::ID = 0;
1284 INITIALIZE_PASS_BEGIN(ReversePostOrderFunctionAttrsLegacyPass, "rpo-functionattrs",
1285 "Deduce function attributes in RPO", false, false)
1286 INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass)
1287 INITIALIZE_PASS_END(ReversePostOrderFunctionAttrsLegacyPass, "rpo-functionattrs",
1288 "Deduce function attributes in RPO", false, false)
1290 Pass *llvm::createReversePostOrderFunctionAttrsPass() {
1291 return new ReversePostOrderFunctionAttrsLegacyPass();
1294 static bool addNoRecurseAttrsTopDown(Function &F) {
1295 // We check the preconditions for the function prior to calling this to avoid
1296 // the cost of building up a reversible post-order list. We assert them here
1297 // to make sure none of the invariants this relies on were violated.
1298 assert(!F.isDeclaration() && "Cannot deduce norecurse without a definition!");
1299 assert(!F.doesNotRecurse() &&
1300 "This function has already been deduced as norecurs!");
1301 assert(F.hasInternalLinkage() &&
1302 "Can only do top-down deduction for internal linkage functions!");
1304 // If F is internal and all of its uses are calls from a non-recursive
1305 // functions, then none of its calls could in fact recurse without going
1306 // through a function marked norecurse, and so we can mark this function too
1307 // as norecurse. Note that the uses must actually be calls -- otherwise
1308 // a pointer to this function could be returned from a norecurse function but
1309 // this function could be recursively (indirectly) called. Note that this
1310 // also detects if F is directly recursive as F is not yet marked as
1311 // a norecurse function.
1312 for (auto *U : F.users()) {
1313 auto *I = dyn_cast<Instruction>(U);
1317 if (!CS || !CS.getParent()->getParent()->doesNotRecurse())
1320 return setDoesNotRecurse(F);
1323 static bool deduceFunctionAttributeInRPO(Module &M, CallGraph &CG) {
1324 // We only have a post-order SCC traversal (because SCCs are inherently
1325 // discovered in post-order), so we accumulate them in a vector and then walk
1326 // it in reverse. This is simpler than using the RPO iterator infrastructure
1327 // because we need to combine SCC detection and the PO walk of the call
1328 // graph. We can also cheat egregiously because we're primarily interested in
1329 // synthesizing norecurse and so we can only save the singular SCCs as SCCs
1330 // with multiple functions in them will clearly be recursive.
1331 SmallVector<Function *, 16> Worklist;
1332 for (scc_iterator<CallGraph *> I = scc_begin(&CG); !I.isAtEnd(); ++I) {
1336 Function *F = I->front()->getFunction();
1337 if (F && !F->isDeclaration() && !F->doesNotRecurse() &&
1338 F->hasInternalLinkage())
1339 Worklist.push_back(F);
1342 bool Changed = false;
1343 for (auto *F : llvm::reverse(Worklist))
1344 Changed |= addNoRecurseAttrsTopDown(*F);
1349 bool ReversePostOrderFunctionAttrsLegacyPass::runOnModule(Module &M) {
1353 auto &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph();
1355 return deduceFunctionAttributeInRPO(M, CG);
1359 ReversePostOrderFunctionAttrsPass::run(Module &M, ModuleAnalysisManager &AM) {
1360 auto &CG = AM.getResult<CallGraphAnalysis>(M);
1362 if (!deduceFunctionAttributeInRPO(M, CG))
1363 return PreservedAnalyses::all();
1365 PreservedAnalyses PA;
1366 PA.preserve<CallGraphAnalysis>();