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/Transforms/IPO.h"
18 #include "llvm/ADT/SCCIterator.h"
19 #include "llvm/ADT/SetVector.h"
20 #include "llvm/ADT/SmallSet.h"
21 #include "llvm/ADT/Statistic.h"
22 #include "llvm/ADT/StringSwitch.h"
23 #include "llvm/Analysis/AliasAnalysis.h"
24 #include "llvm/Analysis/AssumptionCache.h"
25 #include "llvm/Analysis/BasicAliasAnalysis.h"
26 #include "llvm/Analysis/CallGraph.h"
27 #include "llvm/Analysis/CallGraphSCCPass.h"
28 #include "llvm/Analysis/CaptureTracking.h"
29 #include "llvm/Analysis/TargetLibraryInfo.h"
30 #include "llvm/Analysis/ValueTracking.h"
31 #include "llvm/IR/GlobalVariable.h"
32 #include "llvm/IR/InstIterator.h"
33 #include "llvm/IR/IntrinsicInst.h"
34 #include "llvm/IR/LLVMContext.h"
35 #include "llvm/Support/Debug.h"
36 #include "llvm/Support/raw_ostream.h"
37 #include "llvm/Analysis/TargetLibraryInfo.h"
40 #define DEBUG_TYPE "functionattrs"
42 STATISTIC(NumReadNone, "Number of functions marked readnone");
43 STATISTIC(NumReadOnly, "Number of functions marked readonly");
44 STATISTIC(NumNoCapture, "Number of arguments marked nocapture");
45 STATISTIC(NumReturned, "Number of arguments marked returned");
46 STATISTIC(NumReadNoneArg, "Number of arguments marked readnone");
47 STATISTIC(NumReadOnlyArg, "Number of arguments marked readonly");
48 STATISTIC(NumNoAlias, "Number of function returns marked noalias");
49 STATISTIC(NumNonNullReturn, "Number of function returns marked nonnull");
50 STATISTIC(NumNoRecurse, "Number of functions marked as norecurse");
53 typedef SmallSetVector<Function *, 8> SCCNodeSet;
57 /// The three kinds of memory access relevant to 'readonly' and
58 /// 'readnone' attributes.
59 enum MemoryAccessKind {
66 static MemoryAccessKind checkFunctionMemoryAccess(Function &F, AAResults &AAR,
67 const SCCNodeSet &SCCNodes) {
68 FunctionModRefBehavior MRB = AAR.getModRefBehavior(&F);
69 if (MRB == FMRB_DoesNotAccessMemory)
73 // Non-exact function definitions may not be selected at link time, and an
74 // alternative version that writes to memory may be selected. See the comment
75 // on GlobalValue::isDefinitionExact for more details.
76 if (!F.hasExactDefinition()) {
77 if (AliasAnalysis::onlyReadsMemory(MRB))
80 // Conservatively assume it writes to memory.
84 // Scan the function body for instructions that may read or write memory.
85 bool ReadsMemory = false;
86 for (inst_iterator II = inst_begin(F), E = inst_end(F); II != E; ++II) {
87 Instruction *I = &*II;
89 // Some instructions can be ignored even if they read or write memory.
90 // Detect these now, skipping to the next instruction if one is found.
91 CallSite CS(cast<Value>(I));
93 // Ignore calls to functions in the same SCC, as long as the call sites
94 // don't have operand bundles. Calls with operand bundles are allowed to
95 // have memory effects not described by the memory effects of the call
97 if (!CS.hasOperandBundles() && CS.getCalledFunction() &&
98 SCCNodes.count(CS.getCalledFunction()))
100 FunctionModRefBehavior MRB = AAR.getModRefBehavior(CS);
102 // If the call doesn't access memory, we're done.
103 if (!(MRB & MRI_ModRef))
106 if (!AliasAnalysis::onlyAccessesArgPointees(MRB)) {
107 // The call could access any memory. If that includes writes, give up.
110 // If it reads, note it.
116 // Check whether all pointer arguments point to local memory, and
117 // ignore calls that only access local memory.
118 for (CallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end();
121 if (!Arg->getType()->isPtrOrPtrVectorTy())
125 I->getAAMetadata(AAInfo);
126 MemoryLocation Loc(Arg, MemoryLocation::UnknownSize, AAInfo);
128 // Skip accesses to local or constant memory as they don't impact the
129 // externally visible mod/ref behavior.
130 if (AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true))
134 // Writes non-local memory. Give up.
137 // Ok, it reads non-local memory.
141 } else if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
142 // Ignore non-volatile loads from local memory. (Atomic is okay here.)
143 if (!LI->isVolatile()) {
144 MemoryLocation Loc = MemoryLocation::get(LI);
145 if (AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true))
148 } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
149 // Ignore non-volatile stores to local memory. (Atomic is okay here.)
150 if (!SI->isVolatile()) {
151 MemoryLocation Loc = MemoryLocation::get(SI);
152 if (AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true))
155 } else if (VAArgInst *VI = dyn_cast<VAArgInst>(I)) {
156 // Ignore vaargs on local memory.
157 MemoryLocation Loc = MemoryLocation::get(VI);
158 if (AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true))
162 // Any remaining instructions need to be taken seriously! Check if they
163 // read or write memory.
164 if (I->mayWriteToMemory())
165 // Writes memory. Just give up.
168 // If this instruction may read memory, remember that.
169 ReadsMemory |= I->mayReadFromMemory();
172 return ReadsMemory ? MAK_ReadOnly : MAK_ReadNone;
175 /// Deduce readonly/readnone attributes for the SCC.
176 template <typename AARGetterT>
177 static bool addReadAttrs(const SCCNodeSet &SCCNodes, AARGetterT AARGetter) {
178 // Check if any of the functions in the SCC read or write memory. If they
179 // write memory then they can't be marked readnone or readonly.
180 bool ReadsMemory = false;
181 for (Function *F : SCCNodes) {
182 // Call the callable parameter to look up AA results for this function.
183 AAResults &AAR = AARGetter(*F);
185 switch (checkFunctionMemoryAccess(*F, AAR, SCCNodes)) {
197 // Success! Functions in this SCC do not access memory, or only read memory.
198 // Give them the appropriate attribute.
199 bool MadeChange = false;
200 for (Function *F : SCCNodes) {
201 if (F->doesNotAccessMemory())
205 if (F->onlyReadsMemory() && ReadsMemory)
211 // Clear out any existing attributes.
213 B.addAttribute(Attribute::ReadOnly).addAttribute(Attribute::ReadNone);
215 AttributeSet::FunctionIndex,
216 AttributeSet::get(F->getContext(), AttributeSet::FunctionIndex, B));
218 // Add in the new attribute.
219 F->addAttribute(AttributeSet::FunctionIndex,
220 ReadsMemory ? Attribute::ReadOnly : Attribute::ReadNone);
232 /// For a given pointer Argument, this retains a list of Arguments of functions
233 /// in the same SCC that the pointer data flows into. We use this to build an
234 /// SCC of the arguments.
235 struct ArgumentGraphNode {
236 Argument *Definition;
237 SmallVector<ArgumentGraphNode *, 4> Uses;
240 class ArgumentGraph {
241 // We store pointers to ArgumentGraphNode objects, so it's important that
242 // that they not move around upon insert.
243 typedef std::map<Argument *, ArgumentGraphNode> ArgumentMapTy;
245 ArgumentMapTy ArgumentMap;
247 // There is no root node for the argument graph, in fact:
248 // void f(int *x, int *y) { if (...) f(x, y); }
249 // is an example where the graph is disconnected. The SCCIterator requires a
250 // single entry point, so we maintain a fake ("synthetic") root node that
251 // uses every node. Because the graph is directed and nothing points into
252 // the root, it will not participate in any SCCs (except for its own).
253 ArgumentGraphNode SyntheticRoot;
256 ArgumentGraph() { SyntheticRoot.Definition = nullptr; }
258 typedef SmallVectorImpl<ArgumentGraphNode *>::iterator iterator;
260 iterator begin() { return SyntheticRoot.Uses.begin(); }
261 iterator end() { return SyntheticRoot.Uses.end(); }
262 ArgumentGraphNode *getEntryNode() { return &SyntheticRoot; }
264 ArgumentGraphNode *operator[](Argument *A) {
265 ArgumentGraphNode &Node = ArgumentMap[A];
267 SyntheticRoot.Uses.push_back(&Node);
272 /// This tracker checks whether callees are in the SCC, and if so it does not
273 /// consider that a capture, instead adding it to the "Uses" list and
274 /// continuing with the analysis.
275 struct ArgumentUsesTracker : public CaptureTracker {
276 ArgumentUsesTracker(const SCCNodeSet &SCCNodes)
277 : Captured(false), SCCNodes(SCCNodes) {}
279 void tooManyUses() override { Captured = true; }
281 bool captured(const Use *U) override {
282 CallSite CS(U->getUser());
283 if (!CS.getInstruction()) {
288 Function *F = CS.getCalledFunction();
289 if (!F || !F->hasExactDefinition() || !SCCNodes.count(F)) {
294 // Note: the callee and the two successor blocks *follow* the argument
295 // operands. This means there is no need to adjust UseIndex to account for
299 std::distance(const_cast<const Use *>(CS.arg_begin()), U);
301 assert(UseIndex < CS.data_operands_size() &&
302 "Indirect function calls should have been filtered above!");
304 if (UseIndex >= CS.getNumArgOperands()) {
305 // Data operand, but not a argument operand -- must be a bundle operand
306 assert(CS.hasOperandBundles() && "Must be!");
308 // CaptureTracking told us that we're being captured by an operand bundle
309 // use. In this case it does not matter if the callee is within our SCC
310 // or not -- we've been captured in some unknown way, and we have to be
316 if (UseIndex >= F->arg_size()) {
317 assert(F->isVarArg() && "More params than args in non-varargs call");
322 Uses.push_back(&*std::next(F->arg_begin(), UseIndex));
326 bool Captured; // True only if certainly captured (used outside our SCC).
327 SmallVector<Argument *, 4> Uses; // Uses within our SCC.
329 const SCCNodeSet &SCCNodes;
334 template <> struct GraphTraits<ArgumentGraphNode *> {
335 typedef ArgumentGraphNode *NodeRef;
336 typedef SmallVectorImpl<ArgumentGraphNode *>::iterator ChildIteratorType;
338 static NodeRef getEntryNode(NodeRef A) { return A; }
339 static ChildIteratorType child_begin(NodeRef N) { return N->Uses.begin(); }
340 static ChildIteratorType child_end(NodeRef N) { return N->Uses.end(); }
343 struct GraphTraits<ArgumentGraph *> : public GraphTraits<ArgumentGraphNode *> {
344 static NodeRef getEntryNode(ArgumentGraph *AG) { return AG->getEntryNode(); }
345 static ChildIteratorType nodes_begin(ArgumentGraph *AG) {
348 static ChildIteratorType nodes_end(ArgumentGraph *AG) { return AG->end(); }
352 /// Returns Attribute::None, Attribute::ReadOnly or Attribute::ReadNone.
353 static Attribute::AttrKind
354 determinePointerReadAttrs(Argument *A,
355 const SmallPtrSet<Argument *, 8> &SCCNodes) {
357 SmallVector<Use *, 32> Worklist;
358 SmallSet<Use *, 32> Visited;
360 // inalloca arguments are always clobbered by the call.
361 if (A->hasInAllocaAttr())
362 return Attribute::None;
365 // We don't need to track IsWritten. If A is written to, return immediately.
367 for (Use &U : A->uses()) {
369 Worklist.push_back(&U);
372 while (!Worklist.empty()) {
373 Use *U = Worklist.pop_back_val();
374 Instruction *I = cast<Instruction>(U->getUser());
376 switch (I->getOpcode()) {
377 case Instruction::BitCast:
378 case Instruction::GetElementPtr:
379 case Instruction::PHI:
380 case Instruction::Select:
381 case Instruction::AddrSpaceCast:
382 // The original value is not read/written via this if the new value isn't.
383 for (Use &UU : I->uses())
384 if (Visited.insert(&UU).second)
385 Worklist.push_back(&UU);
388 case Instruction::Call:
389 case Instruction::Invoke: {
390 bool Captures = true;
392 if (I->getType()->isVoidTy())
395 auto AddUsersToWorklistIfCapturing = [&] {
397 for (Use &UU : I->uses())
398 if (Visited.insert(&UU).second)
399 Worklist.push_back(&UU);
403 if (CS.doesNotAccessMemory()) {
404 AddUsersToWorklistIfCapturing();
408 Function *F = CS.getCalledFunction();
410 if (CS.onlyReadsMemory()) {
412 AddUsersToWorklistIfCapturing();
415 return Attribute::None;
418 // Note: the callee and the two successor blocks *follow* the argument
419 // operands. This means there is no need to adjust UseIndex to account
422 unsigned UseIndex = std::distance(CS.arg_begin(), U);
424 // U cannot be the callee operand use: since we're exploring the
425 // transitive uses of an Argument, having such a use be a callee would
426 // imply the CallSite is an indirect call or invoke; and we'd take the
428 assert(UseIndex < CS.data_operands_size() &&
429 "Data operand use expected!");
431 bool IsOperandBundleUse = UseIndex >= CS.getNumArgOperands();
433 if (UseIndex >= F->arg_size() && !IsOperandBundleUse) {
434 assert(F->isVarArg() && "More params than args in non-varargs call");
435 return Attribute::None;
438 Captures &= !CS.doesNotCapture(UseIndex);
440 // Since the optimizer (by design) cannot see the data flow corresponding
441 // to a operand bundle use, these cannot participate in the optimistic SCC
442 // analysis. Instead, we model the operand bundle uses as arguments in
443 // call to a function external to the SCC.
444 if (IsOperandBundleUse ||
445 !SCCNodes.count(&*std::next(F->arg_begin(), UseIndex))) {
447 // The accessors used on CallSite here do the right thing for calls and
448 // invokes with operand bundles.
450 if (!CS.onlyReadsMemory() && !CS.onlyReadsMemory(UseIndex))
451 return Attribute::None;
452 if (!CS.doesNotAccessMemory(UseIndex))
456 AddUsersToWorklistIfCapturing();
460 case Instruction::Load:
461 // A volatile load has side effects beyond what readonly can be relied
463 if (cast<LoadInst>(I)->isVolatile())
464 return Attribute::None;
469 case Instruction::ICmp:
470 case Instruction::Ret:
474 return Attribute::None;
478 return IsRead ? Attribute::ReadOnly : Attribute::ReadNone;
481 /// Deduce returned attributes for the SCC.
482 static bool addArgumentReturnedAttrs(const SCCNodeSet &SCCNodes) {
483 bool Changed = false;
486 B.addAttribute(Attribute::Returned);
488 // Check each function in turn, determining if an argument is always returned.
489 for (Function *F : SCCNodes) {
490 // We can infer and propagate function attributes only when we know that the
491 // definition we'll get at link time is *exactly* the definition we see now.
492 // For more details, see GlobalValue::mayBeDerefined.
493 if (!F->hasExactDefinition())
496 if (F->getReturnType()->isVoidTy())
499 // There is nothing to do if an argument is already marked as 'returned'.
500 if (any_of(F->args(),
501 [](const Argument &Arg) { return Arg.hasReturnedAttr(); }))
504 auto FindRetArg = [&]() -> Value * {
505 Value *RetArg = nullptr;
506 for (BasicBlock &BB : *F)
507 if (auto *Ret = dyn_cast<ReturnInst>(BB.getTerminator())) {
508 // Note that stripPointerCasts should look through functions with
509 // returned arguments.
510 Value *RetVal = Ret->getReturnValue()->stripPointerCasts();
511 if (!isa<Argument>(RetVal) || RetVal->getType() != F->getReturnType())
516 else if (RetArg != RetVal)
523 if (Value *RetArg = FindRetArg()) {
524 auto *A = cast<Argument>(RetArg);
525 A->addAttr(AttributeSet::get(F->getContext(), A->getArgNo() + 1, B));
534 /// Deduce nocapture attributes for the SCC.
535 static bool addArgumentAttrs(const SCCNodeSet &SCCNodes) {
536 bool Changed = false;
541 B.addAttribute(Attribute::NoCapture);
543 // Check each function in turn, determining which pointer arguments are not
545 for (Function *F : SCCNodes) {
546 // We can infer and propagate function attributes only when we know that the
547 // definition we'll get at link time is *exactly* the definition we see now.
548 // For more details, see GlobalValue::mayBeDerefined.
549 if (!F->hasExactDefinition())
552 // Functions that are readonly (or readnone) and nounwind and don't return
553 // a value can't capture arguments. Don't analyze them.
554 if (F->onlyReadsMemory() && F->doesNotThrow() &&
555 F->getReturnType()->isVoidTy()) {
556 for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end(); A != E;
558 if (A->getType()->isPointerTy() && !A->hasNoCaptureAttr()) {
559 A->addAttr(AttributeSet::get(F->getContext(), A->getArgNo() + 1, B));
567 for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end(); A != E;
569 if (!A->getType()->isPointerTy())
571 bool HasNonLocalUses = false;
572 if (!A->hasNoCaptureAttr()) {
573 ArgumentUsesTracker Tracker(SCCNodes);
574 PointerMayBeCaptured(&*A, &Tracker);
575 if (!Tracker.Captured) {
576 if (Tracker.Uses.empty()) {
577 // If it's trivially not captured, mark it nocapture now.
579 AttributeSet::get(F->getContext(), A->getArgNo() + 1, B));
583 // If it's not trivially captured and not trivially not captured,
584 // then it must be calling into another function in our SCC. Save
585 // its particulars for Argument-SCC analysis later.
586 ArgumentGraphNode *Node = AG[&*A];
587 for (Argument *Use : Tracker.Uses) {
588 Node->Uses.push_back(AG[Use]);
590 HasNonLocalUses = true;
594 // Otherwise, it's captured. Don't bother doing SCC analysis on it.
596 if (!HasNonLocalUses && !A->onlyReadsMemory()) {
597 // Can we determine that it's readonly/readnone without doing an SCC?
598 // Note that we don't allow any calls at all here, or else our result
599 // will be dependent on the iteration order through the functions in the
601 SmallPtrSet<Argument *, 8> Self;
603 Attribute::AttrKind R = determinePointerReadAttrs(&*A, Self);
604 if (R != Attribute::None) {
607 A->addAttr(AttributeSet::get(A->getContext(), A->getArgNo() + 1, B));
609 R == Attribute::ReadOnly ? ++NumReadOnlyArg : ++NumReadNoneArg;
615 // The graph we've collected is partial because we stopped scanning for
616 // argument uses once we solved the argument trivially. These partial nodes
617 // show up as ArgumentGraphNode objects with an empty Uses list, and for
618 // these nodes the final decision about whether they capture has already been
619 // made. If the definition doesn't have a 'nocapture' attribute by now, it
622 for (scc_iterator<ArgumentGraph *> I = scc_begin(&AG); !I.isAtEnd(); ++I) {
623 const std::vector<ArgumentGraphNode *> &ArgumentSCC = *I;
624 if (ArgumentSCC.size() == 1) {
625 if (!ArgumentSCC[0]->Definition)
626 continue; // synthetic root node
628 // eg. "void f(int* x) { if (...) f(x); }"
629 if (ArgumentSCC[0]->Uses.size() == 1 &&
630 ArgumentSCC[0]->Uses[0] == ArgumentSCC[0]) {
631 Argument *A = ArgumentSCC[0]->Definition;
632 A->addAttr(AttributeSet::get(A->getContext(), A->getArgNo() + 1, B));
639 bool SCCCaptured = false;
640 for (auto I = ArgumentSCC.begin(), E = ArgumentSCC.end();
641 I != E && !SCCCaptured; ++I) {
642 ArgumentGraphNode *Node = *I;
643 if (Node->Uses.empty()) {
644 if (!Node->Definition->hasNoCaptureAttr())
651 SmallPtrSet<Argument *, 8> ArgumentSCCNodes;
652 // Fill ArgumentSCCNodes with the elements of the ArgumentSCC. Used for
653 // quickly looking up whether a given Argument is in this ArgumentSCC.
654 for (ArgumentGraphNode *I : ArgumentSCC) {
655 ArgumentSCCNodes.insert(I->Definition);
658 for (auto I = ArgumentSCC.begin(), E = ArgumentSCC.end();
659 I != E && !SCCCaptured; ++I) {
660 ArgumentGraphNode *N = *I;
661 for (ArgumentGraphNode *Use : N->Uses) {
662 Argument *A = Use->Definition;
663 if (A->hasNoCaptureAttr() || ArgumentSCCNodes.count(A))
672 for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) {
673 Argument *A = ArgumentSCC[i]->Definition;
674 A->addAttr(AttributeSet::get(A->getContext(), A->getArgNo() + 1, B));
679 // We also want to compute readonly/readnone. With a small number of false
680 // negatives, we can assume that any pointer which is captured isn't going
681 // to be provably readonly or readnone, since by definition we can't
682 // analyze all uses of a captured pointer.
684 // The false negatives happen when the pointer is captured by a function
685 // that promises readonly/readnone behaviour on the pointer, then the
686 // pointer's lifetime ends before anything that writes to arbitrary memory.
687 // Also, a readonly/readnone pointer may be returned, but returning a
688 // pointer is capturing it.
690 Attribute::AttrKind ReadAttr = Attribute::ReadNone;
691 for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) {
692 Argument *A = ArgumentSCC[i]->Definition;
693 Attribute::AttrKind K = determinePointerReadAttrs(A, ArgumentSCCNodes);
694 if (K == Attribute::ReadNone)
696 if (K == Attribute::ReadOnly) {
697 ReadAttr = Attribute::ReadOnly;
704 if (ReadAttr != Attribute::None) {
706 B.addAttribute(ReadAttr);
707 R.addAttribute(Attribute::ReadOnly).addAttribute(Attribute::ReadNone);
708 for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) {
709 Argument *A = ArgumentSCC[i]->Definition;
710 // Clear out existing readonly/readnone attributes
711 A->removeAttr(AttributeSet::get(A->getContext(), A->getArgNo() + 1, R));
712 A->addAttr(AttributeSet::get(A->getContext(), A->getArgNo() + 1, B));
713 ReadAttr == Attribute::ReadOnly ? ++NumReadOnlyArg : ++NumReadNoneArg;
722 /// Tests whether a function is "malloc-like".
724 /// A function is "malloc-like" if it returns either null or a pointer that
725 /// doesn't alias any other pointer visible to the caller.
726 static bool isFunctionMallocLike(Function *F, const SCCNodeSet &SCCNodes) {
727 SmallSetVector<Value *, 8> FlowsToReturn;
728 for (BasicBlock &BB : *F)
729 if (ReturnInst *Ret = dyn_cast<ReturnInst>(BB.getTerminator()))
730 FlowsToReturn.insert(Ret->getReturnValue());
732 for (unsigned i = 0; i != FlowsToReturn.size(); ++i) {
733 Value *RetVal = FlowsToReturn[i];
735 if (Constant *C = dyn_cast<Constant>(RetVal)) {
736 if (!C->isNullValue() && !isa<UndefValue>(C))
742 if (isa<Argument>(RetVal))
745 if (Instruction *RVI = dyn_cast<Instruction>(RetVal))
746 switch (RVI->getOpcode()) {
747 // Extend the analysis by looking upwards.
748 case Instruction::BitCast:
749 case Instruction::GetElementPtr:
750 case Instruction::AddrSpaceCast:
751 FlowsToReturn.insert(RVI->getOperand(0));
753 case Instruction::Select: {
754 SelectInst *SI = cast<SelectInst>(RVI);
755 FlowsToReturn.insert(SI->getTrueValue());
756 FlowsToReturn.insert(SI->getFalseValue());
759 case Instruction::PHI: {
760 PHINode *PN = cast<PHINode>(RVI);
761 for (Value *IncValue : PN->incoming_values())
762 FlowsToReturn.insert(IncValue);
766 // Check whether the pointer came from an allocation.
767 case Instruction::Alloca:
769 case Instruction::Call:
770 case Instruction::Invoke: {
772 if (CS.paramHasAttr(0, Attribute::NoAlias))
774 if (CS.getCalledFunction() && SCCNodes.count(CS.getCalledFunction()))
779 return false; // Did not come from an allocation.
782 if (PointerMayBeCaptured(RetVal, false, /*StoreCaptures=*/false))
789 /// Deduce noalias attributes for the SCC.
790 static bool addNoAliasAttrs(const SCCNodeSet &SCCNodes) {
791 // Check each function in turn, determining which functions return noalias
793 for (Function *F : SCCNodes) {
795 if (F->doesNotAlias(0))
798 // We can infer and propagate function attributes only when we know that the
799 // definition we'll get at link time is *exactly* the definition we see now.
800 // For more details, see GlobalValue::mayBeDerefined.
801 if (!F->hasExactDefinition())
804 // We annotate noalias return values, which are only applicable to
806 if (!F->getReturnType()->isPointerTy())
809 if (!isFunctionMallocLike(F, SCCNodes))
813 bool MadeChange = false;
814 for (Function *F : SCCNodes) {
815 if (F->doesNotAlias(0) || !F->getReturnType()->isPointerTy())
818 F->setDoesNotAlias(0);
826 /// Tests whether this function is known to not return null.
828 /// Requires that the function returns a pointer.
830 /// Returns true if it believes the function will not return a null, and sets
831 /// \p Speculative based on whether the returned conclusion is a speculative
832 /// conclusion due to SCC calls.
833 static bool isReturnNonNull(Function *F, const SCCNodeSet &SCCNodes,
835 assert(F->getReturnType()->isPointerTy() &&
836 "nonnull only meaningful on pointer types");
839 SmallSetVector<Value *, 8> FlowsToReturn;
840 for (BasicBlock &BB : *F)
841 if (auto *Ret = dyn_cast<ReturnInst>(BB.getTerminator()))
842 FlowsToReturn.insert(Ret->getReturnValue());
844 for (unsigned i = 0; i != FlowsToReturn.size(); ++i) {
845 Value *RetVal = FlowsToReturn[i];
847 // If this value is locally known to be non-null, we're good
848 if (isKnownNonNull(RetVal))
851 // Otherwise, we need to look upwards since we can't make any local
853 Instruction *RVI = dyn_cast<Instruction>(RetVal);
856 switch (RVI->getOpcode()) {
857 // Extend the analysis by looking upwards.
858 case Instruction::BitCast:
859 case Instruction::GetElementPtr:
860 case Instruction::AddrSpaceCast:
861 FlowsToReturn.insert(RVI->getOperand(0));
863 case Instruction::Select: {
864 SelectInst *SI = cast<SelectInst>(RVI);
865 FlowsToReturn.insert(SI->getTrueValue());
866 FlowsToReturn.insert(SI->getFalseValue());
869 case Instruction::PHI: {
870 PHINode *PN = cast<PHINode>(RVI);
871 for (int i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
872 FlowsToReturn.insert(PN->getIncomingValue(i));
875 case Instruction::Call:
876 case Instruction::Invoke: {
878 Function *Callee = CS.getCalledFunction();
879 // A call to a node within the SCC is assumed to return null until
881 if (Callee && SCCNodes.count(Callee)) {
888 return false; // Unknown source, may be null
890 llvm_unreachable("should have either continued or returned");
896 /// Deduce nonnull attributes for the SCC.
897 static bool addNonNullAttrs(const SCCNodeSet &SCCNodes) {
898 // Speculative that all functions in the SCC return only nonnull
899 // pointers. We may refute this as we analyze functions.
900 bool SCCReturnsNonNull = true;
902 bool MadeChange = false;
904 // Check each function in turn, determining which functions return nonnull
906 for (Function *F : SCCNodes) {
908 if (F->getAttributes().hasAttribute(AttributeSet::ReturnIndex,
912 // We can infer and propagate function attributes only when we know that the
913 // definition we'll get at link time is *exactly* the definition we see now.
914 // For more details, see GlobalValue::mayBeDerefined.
915 if (!F->hasExactDefinition())
918 // We annotate nonnull return values, which are only applicable to
920 if (!F->getReturnType()->isPointerTy())
923 bool Speculative = false;
924 if (isReturnNonNull(F, SCCNodes, Speculative)) {
926 // Mark the function eagerly since we may discover a function
927 // which prevents us from speculating about the entire SCC
928 DEBUG(dbgs() << "Eagerly marking " << F->getName() << " as nonnull\n");
929 F->addAttribute(AttributeSet::ReturnIndex, Attribute::NonNull);
935 // At least one function returns something which could be null, can't
936 // speculate any more.
937 SCCReturnsNonNull = false;
940 if (SCCReturnsNonNull) {
941 for (Function *F : SCCNodes) {
942 if (F->getAttributes().hasAttribute(AttributeSet::ReturnIndex,
943 Attribute::NonNull) ||
944 !F->getReturnType()->isPointerTy())
947 DEBUG(dbgs() << "SCC marking " << F->getName() << " as nonnull\n");
948 F->addAttribute(AttributeSet::ReturnIndex, Attribute::NonNull);
957 /// Remove the convergent attribute from all functions in the SCC if every
958 /// callsite within the SCC is not convergent (except for calls to functions
959 /// within the SCC). Returns true if changes were made.
960 static bool removeConvergentAttrs(const SCCNodeSet &SCCNodes) {
961 // For every function in SCC, ensure that either
962 // * it is not convergent, or
963 // * we can remove its convergent attribute.
964 bool HasConvergentFn = false;
965 for (Function *F : SCCNodes) {
966 if (!F->isConvergent()) continue;
967 HasConvergentFn = true;
969 // Can't remove convergent from function declarations.
970 if (F->isDeclaration()) return false;
972 // Can't remove convergent if any of our functions has a convergent call to a
973 // function not in the SCC.
974 for (Instruction &I : instructions(*F)) {
976 // Bail if CS is a convergent call to a function not in the SCC.
977 if (CS && CS.isConvergent() &&
978 SCCNodes.count(CS.getCalledFunction()) == 0)
983 // If the SCC doesn't have any convergent functions, we have nothing to do.
984 if (!HasConvergentFn) return false;
986 // If we got here, all of the calls the SCC makes to functions not in the SCC
987 // are non-convergent. Therefore all of the SCC's functions can also be made
988 // non-convergent. We'll remove the attr from the callsites in
990 for (Function *F : SCCNodes) {
991 if (!F->isConvergent()) continue;
993 DEBUG(dbgs() << "Removing convergent attr from fn " << F->getName()
995 F->setNotConvergent();
1000 static bool setDoesNotRecurse(Function &F) {
1001 if (F.doesNotRecurse())
1003 F.setDoesNotRecurse();
1008 static bool addNoRecurseAttrs(const SCCNodeSet &SCCNodes) {
1009 // Try and identify functions that do not recurse.
1011 // If the SCC contains multiple nodes we know for sure there is recursion.
1012 if (SCCNodes.size() != 1)
1015 Function *F = *SCCNodes.begin();
1016 if (!F || F->isDeclaration() || F->doesNotRecurse())
1019 // If all of the calls in F are identifiable and are to norecurse functions, F
1020 // is norecurse. This check also detects self-recursion as F is not currently
1021 // marked norecurse, so any called from F to F will not be marked norecurse.
1022 for (Instruction &I : instructions(*F))
1023 if (auto CS = CallSite(&I)) {
1024 Function *Callee = CS.getCalledFunction();
1025 if (!Callee || Callee == F || !Callee->doesNotRecurse())
1026 // Function calls a potentially recursive function.
1030 // Every call was to a non-recursive function other than this function, and
1031 // we have no indirect recursion as the SCC size is one. This function cannot
1033 return setDoesNotRecurse(*F);
1036 PreservedAnalyses PostOrderFunctionAttrsPass::run(LazyCallGraph::SCC &C,
1037 CGSCCAnalysisManager &AM,
1039 CGSCCUpdateResult &) {
1040 FunctionAnalysisManager &FAM =
1041 AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C, CG).getManager();
1043 // We pass a lambda into functions to wire them up to the analysis manager
1044 // for getting function analyses.
1045 auto AARGetter = [&](Function &F) -> AAResults & {
1046 return FAM.getResult<AAManager>(F);
1049 // Fill SCCNodes with the elements of the SCC. Also track whether there are
1050 // any external or opt-none nodes that will prevent us from optimizing any
1052 SCCNodeSet SCCNodes;
1053 bool HasUnknownCall = false;
1054 for (LazyCallGraph::Node &N : C) {
1055 Function &F = N.getFunction();
1056 if (F.hasFnAttribute(Attribute::OptimizeNone)) {
1057 // Treat any function we're trying not to optimize as if it were an
1058 // indirect call and omit it from the node set used below.
1059 HasUnknownCall = true;
1062 // Track whether any functions in this SCC have an unknown call edge.
1063 // Note: if this is ever a performance hit, we can common it with
1064 // subsequent routines which also do scans over the instructions of the
1066 if (!HasUnknownCall)
1067 for (Instruction &I : instructions(F))
1068 if (auto CS = CallSite(&I))
1069 if (!CS.getCalledFunction()) {
1070 HasUnknownCall = true;
1074 SCCNodes.insert(&F);
1077 bool Changed = false;
1078 Changed |= addArgumentReturnedAttrs(SCCNodes);
1079 Changed |= addReadAttrs(SCCNodes, AARGetter);
1080 Changed |= addArgumentAttrs(SCCNodes);
1082 // If we have no external nodes participating in the SCC, we can deduce some
1083 // more precise attributes as well.
1084 if (!HasUnknownCall) {
1085 Changed |= addNoAliasAttrs(SCCNodes);
1086 Changed |= addNonNullAttrs(SCCNodes);
1087 Changed |= removeConvergentAttrs(SCCNodes);
1088 Changed |= addNoRecurseAttrs(SCCNodes);
1091 return Changed ? PreservedAnalyses::none() : PreservedAnalyses::all();
1095 struct PostOrderFunctionAttrsLegacyPass : public CallGraphSCCPass {
1096 static char ID; // Pass identification, replacement for typeid
1097 PostOrderFunctionAttrsLegacyPass() : CallGraphSCCPass(ID) {
1098 initializePostOrderFunctionAttrsLegacyPassPass(
1099 *PassRegistry::getPassRegistry());
1102 bool runOnSCC(CallGraphSCC &SCC) override;
1104 void getAnalysisUsage(AnalysisUsage &AU) const override {
1105 AU.setPreservesCFG();
1106 AU.addRequired<AssumptionCacheTracker>();
1107 getAAResultsAnalysisUsage(AU);
1108 CallGraphSCCPass::getAnalysisUsage(AU);
1113 char PostOrderFunctionAttrsLegacyPass::ID = 0;
1114 INITIALIZE_PASS_BEGIN(PostOrderFunctionAttrsLegacyPass, "functionattrs",
1115 "Deduce function attributes", false, false)
1116 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
1117 INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass)
1118 INITIALIZE_PASS_END(PostOrderFunctionAttrsLegacyPass, "functionattrs",
1119 "Deduce function attributes", false, false)
1121 Pass *llvm::createPostOrderFunctionAttrsLegacyPass() {
1122 return new PostOrderFunctionAttrsLegacyPass();
1125 template <typename AARGetterT>
1126 static bool runImpl(CallGraphSCC &SCC, AARGetterT AARGetter) {
1127 bool Changed = false;
1129 // Fill SCCNodes with the elements of the SCC. Used for quickly looking up
1130 // whether a given CallGraphNode is in this SCC. Also track whether there are
1131 // any external or opt-none nodes that will prevent us from optimizing any
1133 SCCNodeSet SCCNodes;
1134 bool ExternalNode = false;
1135 for (CallGraphNode *I : SCC) {
1136 Function *F = I->getFunction();
1137 if (!F || F->hasFnAttribute(Attribute::OptimizeNone)) {
1138 // External node or function we're trying not to optimize - we both avoid
1139 // transform them and avoid leveraging information they provide.
1140 ExternalNode = true;
1147 Changed |= addArgumentReturnedAttrs(SCCNodes);
1148 Changed |= addReadAttrs(SCCNodes, AARGetter);
1149 Changed |= addArgumentAttrs(SCCNodes);
1151 // If we have no external nodes participating in the SCC, we can deduce some
1152 // more precise attributes as well.
1153 if (!ExternalNode) {
1154 Changed |= addNoAliasAttrs(SCCNodes);
1155 Changed |= addNonNullAttrs(SCCNodes);
1156 Changed |= removeConvergentAttrs(SCCNodes);
1157 Changed |= addNoRecurseAttrs(SCCNodes);
1163 bool PostOrderFunctionAttrsLegacyPass::runOnSCC(CallGraphSCC &SCC) {
1167 // We compute dedicated AA results for each function in the SCC as needed. We
1168 // use a lambda referencing external objects so that they live long enough to
1169 // be queried, but we re-use them each time.
1170 Optional<BasicAAResult> BAR;
1171 Optional<AAResults> AAR;
1172 auto AARGetter = [&](Function &F) -> AAResults & {
1173 BAR.emplace(createLegacyPMBasicAAResult(*this, F));
1174 AAR.emplace(createLegacyPMAAResults(*this, F, *BAR));
1178 return runImpl(SCC, AARGetter);
1182 struct ReversePostOrderFunctionAttrsLegacyPass : public ModulePass {
1183 static char ID; // Pass identification, replacement for typeid
1184 ReversePostOrderFunctionAttrsLegacyPass() : ModulePass(ID) {
1185 initializeReversePostOrderFunctionAttrsLegacyPassPass(
1186 *PassRegistry::getPassRegistry());
1189 bool runOnModule(Module &M) override;
1191 void getAnalysisUsage(AnalysisUsage &AU) const override {
1192 AU.setPreservesCFG();
1193 AU.addRequired<CallGraphWrapperPass>();
1194 AU.addPreserved<CallGraphWrapperPass>();
1199 char ReversePostOrderFunctionAttrsLegacyPass::ID = 0;
1200 INITIALIZE_PASS_BEGIN(ReversePostOrderFunctionAttrsLegacyPass, "rpo-functionattrs",
1201 "Deduce function attributes in RPO", false, false)
1202 INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass)
1203 INITIALIZE_PASS_END(ReversePostOrderFunctionAttrsLegacyPass, "rpo-functionattrs",
1204 "Deduce function attributes in RPO", false, false)
1206 Pass *llvm::createReversePostOrderFunctionAttrsPass() {
1207 return new ReversePostOrderFunctionAttrsLegacyPass();
1210 static bool addNoRecurseAttrsTopDown(Function &F) {
1211 // We check the preconditions for the function prior to calling this to avoid
1212 // the cost of building up a reversible post-order list. We assert them here
1213 // to make sure none of the invariants this relies on were violated.
1214 assert(!F.isDeclaration() && "Cannot deduce norecurse without a definition!");
1215 assert(!F.doesNotRecurse() &&
1216 "This function has already been deduced as norecurs!");
1217 assert(F.hasInternalLinkage() &&
1218 "Can only do top-down deduction for internal linkage functions!");
1220 // If F is internal and all of its uses are calls from a non-recursive
1221 // functions, then none of its calls could in fact recurse without going
1222 // through a function marked norecurse, and so we can mark this function too
1223 // as norecurse. Note that the uses must actually be calls -- otherwise
1224 // a pointer to this function could be returned from a norecurse function but
1225 // this function could be recursively (indirectly) called. Note that this
1226 // also detects if F is directly recursive as F is not yet marked as
1227 // a norecurse function.
1228 for (auto *U : F.users()) {
1229 auto *I = dyn_cast<Instruction>(U);
1233 if (!CS || !CS.getParent()->getParent()->doesNotRecurse())
1236 return setDoesNotRecurse(F);
1239 static bool deduceFunctionAttributeInRPO(Module &M, CallGraph &CG) {
1240 // We only have a post-order SCC traversal (because SCCs are inherently
1241 // discovered in post-order), so we accumulate them in a vector and then walk
1242 // it in reverse. This is simpler than using the RPO iterator infrastructure
1243 // because we need to combine SCC detection and the PO walk of the call
1244 // graph. We can also cheat egregiously because we're primarily interested in
1245 // synthesizing norecurse and so we can only save the singular SCCs as SCCs
1246 // with multiple functions in them will clearly be recursive.
1247 SmallVector<Function *, 16> Worklist;
1248 for (scc_iterator<CallGraph *> I = scc_begin(&CG); !I.isAtEnd(); ++I) {
1252 Function *F = I->front()->getFunction();
1253 if (F && !F->isDeclaration() && !F->doesNotRecurse() &&
1254 F->hasInternalLinkage())
1255 Worklist.push_back(F);
1258 bool Changed = false;
1259 for (auto *F : reverse(Worklist))
1260 Changed |= addNoRecurseAttrsTopDown(*F);
1265 bool ReversePostOrderFunctionAttrsLegacyPass::runOnModule(Module &M) {
1269 auto &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph();
1271 return deduceFunctionAttributeInRPO(M, CG);
1275 ReversePostOrderFunctionAttrsPass::run(Module &M, ModuleAnalysisManager &AM) {
1276 auto &CG = AM.getResult<CallGraphAnalysis>(M);
1278 bool Changed = deduceFunctionAttributeInRPO(M, CG);
1280 // CallGraphAnalysis holds AssertingVH and must be invalidated eagerly so
1281 // that other passes don't delete stuff from under it.
1282 // FIXME: We need to invalidate this to avoid PR28400. Is there a better
1284 AM.invalidate<CallGraphAnalysis>(M);
1287 return PreservedAnalyses::all();
1288 PreservedAnalyses PA;
1289 PA.preserve<CallGraphAnalysis>();