1 //===- FunctionAttrs.cpp - Pass which marks functions attributes ----------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 /// \file
10 /// This file implements interprocedural passes which walk the
11 /// call-graph deducing and/or propagating function attributes.
12 //
13 //===----------------------------------------------------------------------===//
14
15 #include "llvm/Transforms/IPO/FunctionAttrs.h"
16 #include "llvm/ADT/ArrayRef.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/SmallVector.h"
22 #include "llvm/ADT/Statistic.h"
23 #include "llvm/Analysis/AssumptionCache.h"
24 #include "llvm/Analysis/BasicAliasAnalysis.h"
25 #include "llvm/Analysis/CFG.h"
26 #include "llvm/Analysis/CGSCCPassManager.h"
27 #include "llvm/Analysis/CallGraph.h"
28 #include "llvm/Analysis/CallGraphSCCPass.h"
29 #include "llvm/Analysis/CaptureTracking.h"
30 #include "llvm/Analysis/LazyCallGraph.h"
31 #include "llvm/Analysis/MemoryBuiltins.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/Constant.h"
38 #include "llvm/IR/Constants.h"
39 #include "llvm/IR/Function.h"
40 #include "llvm/IR/InstIterator.h"
41 #include "llvm/IR/InstrTypes.h"
42 #include "llvm/IR/Instruction.h"
43 #include "llvm/IR/Instructions.h"
44 #include "llvm/IR/IntrinsicInst.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/InitializePasses.h"
52 #include "llvm/Pass.h"
53 #include "llvm/Support/Casting.h"
54 #include "llvm/Support/CommandLine.h"
55 #include "llvm/Support/Compiler.h"
56 #include "llvm/Support/Debug.h"
57 #include "llvm/Support/ErrorHandling.h"
58 #include "llvm/Support/raw_ostream.h"
59 #include "llvm/Transforms/IPO.h"
60 #include <cassert>
61 #include <iterator>
62 #include <map>
63 #include <vector>
64
65 using namespace llvm;
66
67 #define DEBUG_TYPE "function-attrs"
68
69 STATISTIC(NumReadNone, "Number of functions marked readnone");
70 STATISTIC(NumReadOnly, "Number of functions marked readonly");
71 STATISTIC(NumWriteOnly, "Number of functions marked writeonly");
72 STATISTIC(NumNoCapture, "Number of arguments marked nocapture");
73 STATISTIC(NumReturned, "Number of arguments marked returned");
74 STATISTIC(NumReadNoneArg, "Number of arguments marked readnone");
75 STATISTIC(NumReadOnlyArg, "Number of arguments marked readonly");
76 STATISTIC(NumNoAlias, "Number of function returns marked noalias");
77 STATISTIC(NumNonNullReturn, "Number of function returns marked nonnull");
78 STATISTIC(NumNoRecurse, "Number of functions marked as norecurse");
79 STATISTIC(NumNoUnwind, "Number of functions marked as nounwind");
80 STATISTIC(NumNoFree, "Number of functions marked as nofree");
81 STATISTIC(NumWillReturn, "Number of functions marked as willreturn");
82
83 static cl::opt<bool> EnableNonnullArgPropagation(
84 "enable-nonnull-arg-prop", cl::init(true), cl::Hidden,
85 cl::desc("Try to propagate nonnull argument attributes from callsites to "
86 "caller functions."));
87
88 static cl::opt<bool> DisableNoUnwindInference(
89 "disable-nounwind-inference", cl::Hidden,
90 cl::desc("Stop inferring nounwind attribute during function-attrs pass"));
91
92 static cl::opt<bool> DisableNoFreeInference(
93 "disable-nofree-inference", cl::Hidden,
94 cl::desc("Stop inferring nofree attribute during function-attrs pass"));
95
96 namespace {
97
98 using SCCNodeSet = SmallSetVector<Function *, 8>;
99
100 } // end anonymous namespace
101
102 /// Returns the memory access attribute for function F using AAR for AA results,
103 /// where SCCNodes is the current SCC.
104 ///
105 /// If ThisBody is true, this function may examine the function body and will
106 /// return a result pertaining to this copy of the function. If it is false, the
107 /// result will be based only on AA results for the function declaration; it
108 /// will be assumed that some other (perhaps less optimized) version of the
109 /// function may be selected at link time.
checkFunctionMemoryAccess(Function & F,bool ThisBody,AAResults & AAR,const SCCNodeSet & SCCNodes)110 static MemoryAccessKind checkFunctionMemoryAccess(Function &F, bool ThisBody,
111 AAResults &AAR,
112 const SCCNodeSet &SCCNodes) {
113 FunctionModRefBehavior MRB = AAR.getModRefBehavior(&F);
114 if (MRB == FMRB_DoesNotAccessMemory)
115 // Already perfect!
116 return MAK_ReadNone;
117
118 if (!ThisBody) {
119 if (AliasAnalysis::onlyReadsMemory(MRB))
120 return MAK_ReadOnly;
121
122 if (AliasAnalysis::doesNotReadMemory(MRB))
123 return MAK_WriteOnly;
124
125 // Conservatively assume it reads and writes to memory.
126 return MAK_MayWrite;
127 }
128
129 // Scan the function body for instructions that may read or write memory.
130 bool ReadsMemory = false;
131 bool WritesMemory = false;
132 for (inst_iterator II = inst_begin(F), E = inst_end(F); II != E; ++II) {
133 Instruction *I = &*II;
134
135 // Some instructions can be ignored even if they read or write memory.
136 // Detect these now, skipping to the next instruction if one is found.
137 if (auto *Call = dyn_cast<CallBase>(I)) {
138 // Ignore calls to functions in the same SCC, as long as the call sites
139 // don't have operand bundles. Calls with operand bundles are allowed to
140 // have memory effects not described by the memory effects of the call
141 // target.
142 if (!Call->hasOperandBundles() && Call->getCalledFunction() &&
143 SCCNodes.count(Call->getCalledFunction()))
144 continue;
145 FunctionModRefBehavior MRB = AAR.getModRefBehavior(Call);
146 ModRefInfo MRI = createModRefInfo(MRB);
147
148 // If the call doesn't access memory, we're done.
149 if (isNoModRef(MRI))
150 continue;
151
152 // A pseudo probe call shouldn't change any function attribute since it
153 // doesn't translate to a real instruction. It comes with a memory access
154 // tag to prevent itself being removed by optimizations and not block
155 // other instructions being optimized.
156 if (isa<PseudoProbeInst>(I))
157 continue;
158
159 if (!AliasAnalysis::onlyAccessesArgPointees(MRB)) {
160 // The call could access any memory. If that includes writes, note it.
161 if (isModSet(MRI))
162 WritesMemory = true;
163 // If it reads, note it.
164 if (isRefSet(MRI))
165 ReadsMemory = true;
166 continue;
167 }
168
169 // Check whether all pointer arguments point to local memory, and
170 // ignore calls that only access local memory.
171 for (auto CI = Call->arg_begin(), CE = Call->arg_end(); CI != CE; ++CI) {
172 Value *Arg = *CI;
173 if (!Arg->getType()->isPtrOrPtrVectorTy())
174 continue;
175
176 AAMDNodes AAInfo;
177 I->getAAMetadata(AAInfo);
178 MemoryLocation Loc = MemoryLocation::getBeforeOrAfter(Arg, AAInfo);
179
180 // Skip accesses to local or constant memory as they don't impact the
181 // externally visible mod/ref behavior.
182 if (AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true))
183 continue;
184
185 if (isModSet(MRI))
186 // Writes non-local memory.
187 WritesMemory = true;
188 if (isRefSet(MRI))
189 // Ok, it reads non-local memory.
190 ReadsMemory = true;
191 }
192 continue;
193 } else if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
194 // Ignore non-volatile loads from local memory. (Atomic is okay here.)
195 if (!LI->isVolatile()) {
196 MemoryLocation Loc = MemoryLocation::get(LI);
197 if (AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true))
198 continue;
199 }
200 } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
201 // Ignore non-volatile stores to local memory. (Atomic is okay here.)
202 if (!SI->isVolatile()) {
203 MemoryLocation Loc = MemoryLocation::get(SI);
204 if (AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true))
205 continue;
206 }
207 } else if (VAArgInst *VI = dyn_cast<VAArgInst>(I)) {
208 // Ignore vaargs on local memory.
209 MemoryLocation Loc = MemoryLocation::get(VI);
210 if (AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true))
211 continue;
212 }
213
214 // Any remaining instructions need to be taken seriously! Check if they
215 // read or write memory.
216 //
217 // Writes memory, remember that.
218 WritesMemory |= I->mayWriteToMemory();
219
220 // If this instruction may read memory, remember that.
221 ReadsMemory |= I->mayReadFromMemory();
222 }
223
224 if (WritesMemory) {
225 if (!ReadsMemory)
226 return MAK_WriteOnly;
227 else
228 return MAK_MayWrite;
229 }
230
231 return ReadsMemory ? MAK_ReadOnly : MAK_ReadNone;
232 }
233
computeFunctionBodyMemoryAccess(Function & F,AAResults & AAR)234 MemoryAccessKind llvm::computeFunctionBodyMemoryAccess(Function &F,
235 AAResults &AAR) {
236 return checkFunctionMemoryAccess(F, /*ThisBody=*/true, AAR, {});
237 }
238
239 /// Deduce readonly/readnone attributes for the SCC.
240 template <typename AARGetterT>
addReadAttrs(const SCCNodeSet & SCCNodes,AARGetterT && AARGetter)241 static bool addReadAttrs(const SCCNodeSet &SCCNodes, AARGetterT &&AARGetter) {
242 // Check if any of the functions in the SCC read or write memory. If they
243 // write memory then they can't be marked readnone or readonly.
244 bool ReadsMemory = false;
245 bool WritesMemory = false;
246 for (Function *F : SCCNodes) {
247 // Call the callable parameter to look up AA results for this function.
248 AAResults &AAR = AARGetter(*F);
249
250 // Non-exact function definitions may not be selected at link time, and an
251 // alternative version that writes to memory may be selected. See the
252 // comment on GlobalValue::isDefinitionExact for more details.
253 switch (checkFunctionMemoryAccess(*F, F->hasExactDefinition(),
254 AAR, SCCNodes)) {
255 case MAK_MayWrite:
256 return false;
257 case MAK_ReadOnly:
258 ReadsMemory = true;
259 break;
260 case MAK_WriteOnly:
261 WritesMemory = true;
262 break;
263 case MAK_ReadNone:
264 // Nothing to do!
265 break;
266 }
267 }
268
269 // If the SCC contains both functions that read and functions that write, then
270 // we cannot add readonly attributes.
271 if (ReadsMemory && WritesMemory)
272 return false;
273
274 // Success! Functions in this SCC do not access memory, or only read memory.
275 // Give them the appropriate attribute.
276 bool MadeChange = false;
277
278 for (Function *F : SCCNodes) {
279 if (F->doesNotAccessMemory())
280 // Already perfect!
281 continue;
282
283 if (F->onlyReadsMemory() && ReadsMemory)
284 // No change.
285 continue;
286
287 if (F->doesNotReadMemory() && WritesMemory)
288 continue;
289
290 MadeChange = true;
291
292 // Clear out any existing attributes.
293 AttrBuilder AttrsToRemove;
294 AttrsToRemove.addAttribute(Attribute::ReadOnly);
295 AttrsToRemove.addAttribute(Attribute::ReadNone);
296 AttrsToRemove.addAttribute(Attribute::WriteOnly);
297
298 if (!WritesMemory && !ReadsMemory) {
299 // Clear out any "access range attributes" if readnone was deduced.
300 AttrsToRemove.addAttribute(Attribute::ArgMemOnly);
301 AttrsToRemove.addAttribute(Attribute::InaccessibleMemOnly);
302 AttrsToRemove.addAttribute(Attribute::InaccessibleMemOrArgMemOnly);
303 }
304 F->removeAttributes(AttributeList::FunctionIndex, AttrsToRemove);
305
306 // Add in the new attribute.
307 if (WritesMemory && !ReadsMemory)
308 F->addFnAttr(Attribute::WriteOnly);
309 else
310 F->addFnAttr(ReadsMemory ? Attribute::ReadOnly : Attribute::ReadNone);
311
312 if (WritesMemory && !ReadsMemory)
313 ++NumWriteOnly;
314 else if (ReadsMemory)
315 ++NumReadOnly;
316 else
317 ++NumReadNone;
318 }
319
320 return MadeChange;
321 }
322
323 namespace {
324
325 /// For a given pointer Argument, this retains a list of Arguments of functions
326 /// in the same SCC that the pointer data flows into. We use this to build an
327 /// SCC of the arguments.
328 struct ArgumentGraphNode {
329 Argument *Definition;
330 SmallVector<ArgumentGraphNode *, 4> Uses;
331 };
332
333 class ArgumentGraph {
334 // We store pointers to ArgumentGraphNode objects, so it's important that
335 // that they not move around upon insert.
336 using ArgumentMapTy = std::map<Argument *, ArgumentGraphNode>;
337
338 ArgumentMapTy ArgumentMap;
339
340 // There is no root node for the argument graph, in fact:
341 // void f(int *x, int *y) { if (...) f(x, y); }
342 // is an example where the graph is disconnected. The SCCIterator requires a
343 // single entry point, so we maintain a fake ("synthetic") root node that
344 // uses every node. Because the graph is directed and nothing points into
345 // the root, it will not participate in any SCCs (except for its own).
346 ArgumentGraphNode SyntheticRoot;
347
348 public:
ArgumentGraph()349 ArgumentGraph() { SyntheticRoot.Definition = nullptr; }
350
351 using iterator = SmallVectorImpl<ArgumentGraphNode *>::iterator;
352
begin()353 iterator begin() { return SyntheticRoot.Uses.begin(); }
end()354 iterator end() { return SyntheticRoot.Uses.end(); }
getEntryNode()355 ArgumentGraphNode *getEntryNode() { return &SyntheticRoot; }
356
operator [](Argument * A)357 ArgumentGraphNode *operator[](Argument *A) {
358 ArgumentGraphNode &Node = ArgumentMap[A];
359 Node.Definition = A;
360 SyntheticRoot.Uses.push_back(&Node);
361 return &Node;
362 }
363 };
364
365 /// This tracker checks whether callees are in the SCC, and if so it does not
366 /// consider that a capture, instead adding it to the "Uses" list and
367 /// continuing with the analysis.
368 struct ArgumentUsesTracker : public CaptureTracker {
ArgumentUsesTracker__anonec1461e50211::ArgumentUsesTracker369 ArgumentUsesTracker(const SCCNodeSet &SCCNodes) : SCCNodes(SCCNodes) {}
370
tooManyUses__anonec1461e50211::ArgumentUsesTracker371 void tooManyUses() override { Captured = true; }
372
captured__anonec1461e50211::ArgumentUsesTracker373 bool captured(const Use *U) override {
374 CallBase *CB = dyn_cast<CallBase>(U->getUser());
375 if (!CB) {
376 Captured = true;
377 return true;
378 }
379
380 Function *F = CB->getCalledFunction();
381 if (!F || !F->hasExactDefinition() || !SCCNodes.count(F)) {
382 Captured = true;
383 return true;
384 }
385
386 // Note: the callee and the two successor blocks *follow* the argument
387 // operands. This means there is no need to adjust UseIndex to account for
388 // these.
389
390 unsigned UseIndex =
391 std::distance(const_cast<const Use *>(CB->arg_begin()), U);
392
393 assert(UseIndex < CB->data_operands_size() &&
394 "Indirect function calls should have been filtered above!");
395
396 if (UseIndex >= CB->getNumArgOperands()) {
397 // Data operand, but not a argument operand -- must be a bundle operand
398 assert(CB->hasOperandBundles() && "Must be!");
399
400 // CaptureTracking told us that we're being captured by an operand bundle
401 // use. In this case it does not matter if the callee is within our SCC
402 // or not -- we've been captured in some unknown way, and we have to be
403 // conservative.
404 Captured = true;
405 return true;
406 }
407
408 if (UseIndex >= F->arg_size()) {
409 assert(F->isVarArg() && "More params than args in non-varargs call");
410 Captured = true;
411 return true;
412 }
413
414 Uses.push_back(&*std::next(F->arg_begin(), UseIndex));
415 return false;
416 }
417
418 // True only if certainly captured (used outside our SCC).
419 bool Captured = false;
420
421 // Uses within our SCC.
422 SmallVector<Argument *, 4> Uses;
423
424 const SCCNodeSet &SCCNodes;
425 };
426
427 } // end anonymous namespace
428
429 namespace llvm {
430
431 template <> struct GraphTraits<ArgumentGraphNode *> {
432 using NodeRef = ArgumentGraphNode *;
433 using ChildIteratorType = SmallVectorImpl<ArgumentGraphNode *>::iterator;
434
getEntryNodellvm::GraphTraits435 static NodeRef getEntryNode(NodeRef A) { return A; }
child_beginllvm::GraphTraits436 static ChildIteratorType child_begin(NodeRef N) { return N->Uses.begin(); }
child_endllvm::GraphTraits437 static ChildIteratorType child_end(NodeRef N) { return N->Uses.end(); }
438 };
439
440 template <>
441 struct GraphTraits<ArgumentGraph *> : public GraphTraits<ArgumentGraphNode *> {
getEntryNodellvm::GraphTraits442 static NodeRef getEntryNode(ArgumentGraph *AG) { return AG->getEntryNode(); }
443
nodes_beginllvm::GraphTraits444 static ChildIteratorType nodes_begin(ArgumentGraph *AG) {
445 return AG->begin();
446 }
447
nodes_endllvm::GraphTraits448 static ChildIteratorType nodes_end(ArgumentGraph *AG) { return AG->end(); }
449 };
450
451 } // end namespace llvm
452
453 /// Returns Attribute::None, Attribute::ReadOnly or Attribute::ReadNone.
454 static Attribute::AttrKind
determinePointerReadAttrs(Argument * A,const SmallPtrSet<Argument *,8> & SCCNodes)455 determinePointerReadAttrs(Argument *A,
456 const SmallPtrSet<Argument *, 8> &SCCNodes) {
457 SmallVector<Use *, 32> Worklist;
458 SmallPtrSet<Use *, 32> Visited;
459
460 // inalloca arguments are always clobbered by the call.
461 if (A->hasInAllocaAttr() || A->hasPreallocatedAttr())
462 return Attribute::None;
463
464 bool IsRead = false;
465 // We don't need to track IsWritten. If A is written to, return immediately.
466
467 for (Use &U : A->uses()) {
468 Visited.insert(&U);
469 Worklist.push_back(&U);
470 }
471
472 while (!Worklist.empty()) {
473 Use *U = Worklist.pop_back_val();
474 Instruction *I = cast<Instruction>(U->getUser());
475
476 switch (I->getOpcode()) {
477 case Instruction::BitCast:
478 case Instruction::GetElementPtr:
479 case Instruction::PHI:
480 case Instruction::Select:
481 case Instruction::AddrSpaceCast:
482 // The original value is not read/written via this if the new value isn't.
483 for (Use &UU : I->uses())
484 if (Visited.insert(&UU).second)
485 Worklist.push_back(&UU);
486 break;
487
488 case Instruction::Call:
489 case Instruction::Invoke: {
490 bool Captures = true;
491
492 if (I->getType()->isVoidTy())
493 Captures = false;
494
495 auto AddUsersToWorklistIfCapturing = [&] {
496 if (Captures)
497 for (Use &UU : I->uses())
498 if (Visited.insert(&UU).second)
499 Worklist.push_back(&UU);
500 };
501
502 CallBase &CB = cast<CallBase>(*I);
503 if (CB.doesNotAccessMemory()) {
504 AddUsersToWorklistIfCapturing();
505 continue;
506 }
507
508 Function *F = CB.getCalledFunction();
509 if (!F) {
510 if (CB.onlyReadsMemory()) {
511 IsRead = true;
512 AddUsersToWorklistIfCapturing();
513 continue;
514 }
515 return Attribute::None;
516 }
517
518 // Note: the callee and the two successor blocks *follow* the argument
519 // operands. This means there is no need to adjust UseIndex to account
520 // for these.
521
522 unsigned UseIndex = std::distance(CB.arg_begin(), U);
523
524 // U cannot be the callee operand use: since we're exploring the
525 // transitive uses of an Argument, having such a use be a callee would
526 // imply the call site is an indirect call or invoke; and we'd take the
527 // early exit above.
528 assert(UseIndex < CB.data_operands_size() &&
529 "Data operand use expected!");
530
531 bool IsOperandBundleUse = UseIndex >= CB.getNumArgOperands();
532
533 if (UseIndex >= F->arg_size() && !IsOperandBundleUse) {
534 assert(F->isVarArg() && "More params than args in non-varargs call");
535 return Attribute::None;
536 }
537
538 Captures &= !CB.doesNotCapture(UseIndex);
539
540 // Since the optimizer (by design) cannot see the data flow corresponding
541 // to a operand bundle use, these cannot participate in the optimistic SCC
542 // analysis. Instead, we model the operand bundle uses as arguments in
543 // call to a function external to the SCC.
544 if (IsOperandBundleUse ||
545 !SCCNodes.count(&*std::next(F->arg_begin(), UseIndex))) {
546
547 // The accessors used on call site here do the right thing for calls and
548 // invokes with operand bundles.
549
550 if (!CB.onlyReadsMemory() && !CB.onlyReadsMemory(UseIndex))
551 return Attribute::None;
552 if (!CB.doesNotAccessMemory(UseIndex))
553 IsRead = true;
554 }
555
556 AddUsersToWorklistIfCapturing();
557 break;
558 }
559
560 case Instruction::Load:
561 // A volatile load has side effects beyond what readonly can be relied
562 // upon.
563 if (cast<LoadInst>(I)->isVolatile())
564 return Attribute::None;
565
566 IsRead = true;
567 break;
568
569 case Instruction::ICmp:
570 case Instruction::Ret:
571 break;
572
573 default:
574 return Attribute::None;
575 }
576 }
577
578 return IsRead ? Attribute::ReadOnly : Attribute::ReadNone;
579 }
580
581 /// Deduce returned attributes for the SCC.
addArgumentReturnedAttrs(const SCCNodeSet & SCCNodes)582 static bool addArgumentReturnedAttrs(const SCCNodeSet &SCCNodes) {
583 bool Changed = false;
584
585 // Check each function in turn, determining if an argument is always returned.
586 for (Function *F : SCCNodes) {
587 // We can infer and propagate function attributes only when we know that the
588 // definition we'll get at link time is *exactly* the definition we see now.
589 // For more details, see GlobalValue::mayBeDerefined.
590 if (!F->hasExactDefinition())
591 continue;
592
593 if (F->getReturnType()->isVoidTy())
594 continue;
595
596 // There is nothing to do if an argument is already marked as 'returned'.
597 if (llvm::any_of(F->args(),
598 [](const Argument &Arg) { return Arg.hasReturnedAttr(); }))
599 continue;
600
601 auto FindRetArg = [&]() -> Value * {
602 Value *RetArg = nullptr;
603 for (BasicBlock &BB : *F)
604 if (auto *Ret = dyn_cast<ReturnInst>(BB.getTerminator())) {
605 // Note that stripPointerCasts should look through functions with
606 // returned arguments.
607 Value *RetVal = Ret->getReturnValue()->stripPointerCasts();
608 if (!isa<Argument>(RetVal) || RetVal->getType() != F->getReturnType())
609 return nullptr;
610
611 if (!RetArg)
612 RetArg = RetVal;
613 else if (RetArg != RetVal)
614 return nullptr;
615 }
616
617 return RetArg;
618 };
619
620 if (Value *RetArg = FindRetArg()) {
621 auto *A = cast<Argument>(RetArg);
622 A->addAttr(Attribute::Returned);
623 ++NumReturned;
624 Changed = true;
625 }
626 }
627
628 return Changed;
629 }
630
631 /// If a callsite has arguments that are also arguments to the parent function,
632 /// try to propagate attributes from the callsite's arguments to the parent's
633 /// arguments. This may be important because inlining can cause information loss
634 /// when attribute knowledge disappears with the inlined call.
addArgumentAttrsFromCallsites(Function & F)635 static bool addArgumentAttrsFromCallsites(Function &F) {
636 if (!EnableNonnullArgPropagation)
637 return false;
638
639 bool Changed = false;
640
641 // For an argument attribute to transfer from a callsite to the parent, the
642 // call must be guaranteed to execute every time the parent is called.
643 // Conservatively, just check for calls in the entry block that are guaranteed
644 // to execute.
645 // TODO: This could be enhanced by testing if the callsite post-dominates the
646 // entry block or by doing simple forward walks or backward walks to the
647 // callsite.
648 BasicBlock &Entry = F.getEntryBlock();
649 for (Instruction &I : Entry) {
650 if (auto *CB = dyn_cast<CallBase>(&I)) {
651 if (auto *CalledFunc = CB->getCalledFunction()) {
652 for (auto &CSArg : CalledFunc->args()) {
653 if (!CSArg.hasNonNullAttr(/* AllowUndefOrPoison */ false))
654 continue;
655
656 // If the non-null callsite argument operand is an argument to 'F'
657 // (the caller) and the call is guaranteed to execute, then the value
658 // must be non-null throughout 'F'.
659 auto *FArg = dyn_cast<Argument>(CB->getArgOperand(CSArg.getArgNo()));
660 if (FArg && !FArg->hasNonNullAttr()) {
661 FArg->addAttr(Attribute::NonNull);
662 Changed = true;
663 }
664 }
665 }
666 }
667 if (!isGuaranteedToTransferExecutionToSuccessor(&I))
668 break;
669 }
670
671 return Changed;
672 }
673
addReadAttr(Argument * A,Attribute::AttrKind R)674 static bool addReadAttr(Argument *A, Attribute::AttrKind R) {
675 assert((R == Attribute::ReadOnly || R == Attribute::ReadNone)
676 && "Must be a Read attribute.");
677 assert(A && "Argument must not be null.");
678
679 // If the argument already has the attribute, nothing needs to be done.
680 if (A->hasAttribute(R))
681 return false;
682
683 // Otherwise, remove potentially conflicting attribute, add the new one,
684 // and update statistics.
685 A->removeAttr(Attribute::WriteOnly);
686 A->removeAttr(Attribute::ReadOnly);
687 A->removeAttr(Attribute::ReadNone);
688 A->addAttr(R);
689 R == Attribute::ReadOnly ? ++NumReadOnlyArg : ++NumReadNoneArg;
690 return true;
691 }
692
693 /// Deduce nocapture attributes for the SCC.
addArgumentAttrs(const SCCNodeSet & SCCNodes)694 static bool addArgumentAttrs(const SCCNodeSet &SCCNodes) {
695 bool Changed = false;
696
697 ArgumentGraph AG;
698
699 // Check each function in turn, determining which pointer arguments are not
700 // captured.
701 for (Function *F : SCCNodes) {
702 // We can infer and propagate function attributes only when we know that the
703 // definition we'll get at link time is *exactly* the definition we see now.
704 // For more details, see GlobalValue::mayBeDerefined.
705 if (!F->hasExactDefinition())
706 continue;
707
708 Changed |= addArgumentAttrsFromCallsites(*F);
709
710 // Functions that are readonly (or readnone) and nounwind and don't return
711 // a value can't capture arguments. Don't analyze them.
712 if (F->onlyReadsMemory() && F->doesNotThrow() &&
713 F->getReturnType()->isVoidTy()) {
714 for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end(); A != E;
715 ++A) {
716 if (A->getType()->isPointerTy() && !A->hasNoCaptureAttr()) {
717 A->addAttr(Attribute::NoCapture);
718 ++NumNoCapture;
719 Changed = true;
720 }
721 }
722 continue;
723 }
724
725 for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end(); A != E;
726 ++A) {
727 if (!A->getType()->isPointerTy())
728 continue;
729 bool HasNonLocalUses = false;
730 if (!A->hasNoCaptureAttr()) {
731 ArgumentUsesTracker Tracker(SCCNodes);
732 PointerMayBeCaptured(&*A, &Tracker);
733 if (!Tracker.Captured) {
734 if (Tracker.Uses.empty()) {
735 // If it's trivially not captured, mark it nocapture now.
736 A->addAttr(Attribute::NoCapture);
737 ++NumNoCapture;
738 Changed = true;
739 } else {
740 // If it's not trivially captured and not trivially not captured,
741 // then it must be calling into another function in our SCC. Save
742 // its particulars for Argument-SCC analysis later.
743 ArgumentGraphNode *Node = AG[&*A];
744 for (Argument *Use : Tracker.Uses) {
745 Node->Uses.push_back(AG[Use]);
746 if (Use != &*A)
747 HasNonLocalUses = true;
748 }
749 }
750 }
751 // Otherwise, it's captured. Don't bother doing SCC analysis on it.
752 }
753 if (!HasNonLocalUses && !A->onlyReadsMemory()) {
754 // Can we determine that it's readonly/readnone without doing an SCC?
755 // Note that we don't allow any calls at all here, or else our result
756 // will be dependent on the iteration order through the functions in the
757 // SCC.
758 SmallPtrSet<Argument *, 8> Self;
759 Self.insert(&*A);
760 Attribute::AttrKind R = determinePointerReadAttrs(&*A, Self);
761 if (R != Attribute::None)
762 Changed = addReadAttr(A, R);
763 }
764 }
765 }
766
767 // The graph we've collected is partial because we stopped scanning for
768 // argument uses once we solved the argument trivially. These partial nodes
769 // show up as ArgumentGraphNode objects with an empty Uses list, and for
770 // these nodes the final decision about whether they capture has already been
771 // made. If the definition doesn't have a 'nocapture' attribute by now, it
772 // captures.
773
774 for (scc_iterator<ArgumentGraph *> I = scc_begin(&AG); !I.isAtEnd(); ++I) {
775 const std::vector<ArgumentGraphNode *> &ArgumentSCC = *I;
776 if (ArgumentSCC.size() == 1) {
777 if (!ArgumentSCC[0]->Definition)
778 continue; // synthetic root node
779
780 // eg. "void f(int* x) { if (...) f(x); }"
781 if (ArgumentSCC[0]->Uses.size() == 1 &&
782 ArgumentSCC[0]->Uses[0] == ArgumentSCC[0]) {
783 Argument *A = ArgumentSCC[0]->Definition;
784 A->addAttr(Attribute::NoCapture);
785 ++NumNoCapture;
786 Changed = true;
787 }
788 continue;
789 }
790
791 bool SCCCaptured = false;
792 for (auto I = ArgumentSCC.begin(), E = ArgumentSCC.end();
793 I != E && !SCCCaptured; ++I) {
794 ArgumentGraphNode *Node = *I;
795 if (Node->Uses.empty()) {
796 if (!Node->Definition->hasNoCaptureAttr())
797 SCCCaptured = true;
798 }
799 }
800 if (SCCCaptured)
801 continue;
802
803 SmallPtrSet<Argument *, 8> ArgumentSCCNodes;
804 // Fill ArgumentSCCNodes with the elements of the ArgumentSCC. Used for
805 // quickly looking up whether a given Argument is in this ArgumentSCC.
806 for (ArgumentGraphNode *I : ArgumentSCC) {
807 ArgumentSCCNodes.insert(I->Definition);
808 }
809
810 for (auto I = ArgumentSCC.begin(), E = ArgumentSCC.end();
811 I != E && !SCCCaptured; ++I) {
812 ArgumentGraphNode *N = *I;
813 for (ArgumentGraphNode *Use : N->Uses) {
814 Argument *A = Use->Definition;
815 if (A->hasNoCaptureAttr() || ArgumentSCCNodes.count(A))
816 continue;
817 SCCCaptured = true;
818 break;
819 }
820 }
821 if (SCCCaptured)
822 continue;
823
824 for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) {
825 Argument *A = ArgumentSCC[i]->Definition;
826 A->addAttr(Attribute::NoCapture);
827 ++NumNoCapture;
828 Changed = true;
829 }
830
831 // We also want to compute readonly/readnone. With a small number of false
832 // negatives, we can assume that any pointer which is captured isn't going
833 // to be provably readonly or readnone, since by definition we can't
834 // analyze all uses of a captured pointer.
835 //
836 // The false negatives happen when the pointer is captured by a function
837 // that promises readonly/readnone behaviour on the pointer, then the
838 // pointer's lifetime ends before anything that writes to arbitrary memory.
839 // Also, a readonly/readnone pointer may be returned, but returning a
840 // pointer is capturing it.
841
842 Attribute::AttrKind ReadAttr = Attribute::ReadNone;
843 for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) {
844 Argument *A = ArgumentSCC[i]->Definition;
845 Attribute::AttrKind K = determinePointerReadAttrs(A, ArgumentSCCNodes);
846 if (K == Attribute::ReadNone)
847 continue;
848 if (K == Attribute::ReadOnly) {
849 ReadAttr = Attribute::ReadOnly;
850 continue;
851 }
852 ReadAttr = K;
853 break;
854 }
855
856 if (ReadAttr != Attribute::None) {
857 for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) {
858 Argument *A = ArgumentSCC[i]->Definition;
859 Changed = addReadAttr(A, ReadAttr);
860 }
861 }
862 }
863
864 return Changed;
865 }
866
867 /// Tests whether a function is "malloc-like".
868 ///
869 /// A function is "malloc-like" if it returns either null or a pointer that
870 /// doesn't alias any other pointer visible to the caller.
isFunctionMallocLike(Function * F,const SCCNodeSet & SCCNodes)871 static bool isFunctionMallocLike(Function *F, const SCCNodeSet &SCCNodes) {
872 SmallSetVector<Value *, 8> FlowsToReturn;
873 for (BasicBlock &BB : *F)
874 if (ReturnInst *Ret = dyn_cast<ReturnInst>(BB.getTerminator()))
875 FlowsToReturn.insert(Ret->getReturnValue());
876
877 for (unsigned i = 0; i != FlowsToReturn.size(); ++i) {
878 Value *RetVal = FlowsToReturn[i];
879
880 if (Constant *C = dyn_cast<Constant>(RetVal)) {
881 if (!C->isNullValue() && !isa<UndefValue>(C))
882 return false;
883
884 continue;
885 }
886
887 if (isa<Argument>(RetVal))
888 return false;
889
890 if (Instruction *RVI = dyn_cast<Instruction>(RetVal))
891 switch (RVI->getOpcode()) {
892 // Extend the analysis by looking upwards.
893 case Instruction::BitCast:
894 case Instruction::GetElementPtr:
895 case Instruction::AddrSpaceCast:
896 FlowsToReturn.insert(RVI->getOperand(0));
897 continue;
898 case Instruction::Select: {
899 SelectInst *SI = cast<SelectInst>(RVI);
900 FlowsToReturn.insert(SI->getTrueValue());
901 FlowsToReturn.insert(SI->getFalseValue());
902 continue;
903 }
904 case Instruction::PHI: {
905 PHINode *PN = cast<PHINode>(RVI);
906 for (Value *IncValue : PN->incoming_values())
907 FlowsToReturn.insert(IncValue);
908 continue;
909 }
910
911 // Check whether the pointer came from an allocation.
912 case Instruction::Alloca:
913 break;
914 case Instruction::Call:
915 case Instruction::Invoke: {
916 CallBase &CB = cast<CallBase>(*RVI);
917 if (CB.hasRetAttr(Attribute::NoAlias))
918 break;
919 if (CB.getCalledFunction() && SCCNodes.count(CB.getCalledFunction()))
920 break;
921 LLVM_FALLTHROUGH;
922 }
923 default:
924 return false; // Did not come from an allocation.
925 }
926
927 if (PointerMayBeCaptured(RetVal, false, /*StoreCaptures=*/false))
928 return false;
929 }
930
931 return true;
932 }
933
934 /// Deduce noalias attributes for the SCC.
addNoAliasAttrs(const SCCNodeSet & SCCNodes)935 static bool addNoAliasAttrs(const SCCNodeSet &SCCNodes) {
936 // Check each function in turn, determining which functions return noalias
937 // pointers.
938 for (Function *F : SCCNodes) {
939 // Already noalias.
940 if (F->returnDoesNotAlias())
941 continue;
942
943 // We can infer and propagate function attributes only when we know that the
944 // definition we'll get at link time is *exactly* the definition we see now.
945 // For more details, see GlobalValue::mayBeDerefined.
946 if (!F->hasExactDefinition())
947 return false;
948
949 // We annotate noalias return values, which are only applicable to
950 // pointer types.
951 if (!F->getReturnType()->isPointerTy())
952 continue;
953
954 if (!isFunctionMallocLike(F, SCCNodes))
955 return false;
956 }
957
958 bool MadeChange = false;
959 for (Function *F : SCCNodes) {
960 if (F->returnDoesNotAlias() ||
961 !F->getReturnType()->isPointerTy())
962 continue;
963
964 F->setReturnDoesNotAlias();
965 ++NumNoAlias;
966 MadeChange = true;
967 }
968
969 return MadeChange;
970 }
971
972 /// Tests whether this function is known to not return null.
973 ///
974 /// Requires that the function returns a pointer.
975 ///
976 /// Returns true if it believes the function will not return a null, and sets
977 /// \p Speculative based on whether the returned conclusion is a speculative
978 /// conclusion due to SCC calls.
isReturnNonNull(Function * F,const SCCNodeSet & SCCNodes,bool & Speculative)979 static bool isReturnNonNull(Function *F, const SCCNodeSet &SCCNodes,
980 bool &Speculative) {
981 assert(F->getReturnType()->isPointerTy() &&
982 "nonnull only meaningful on pointer types");
983 Speculative = false;
984
985 SmallSetVector<Value *, 8> FlowsToReturn;
986 for (BasicBlock &BB : *F)
987 if (auto *Ret = dyn_cast<ReturnInst>(BB.getTerminator()))
988 FlowsToReturn.insert(Ret->getReturnValue());
989
990 auto &DL = F->getParent()->getDataLayout();
991
992 for (unsigned i = 0; i != FlowsToReturn.size(); ++i) {
993 Value *RetVal = FlowsToReturn[i];
994
995 // If this value is locally known to be non-null, we're good
996 if (isKnownNonZero(RetVal, DL))
997 continue;
998
999 // Otherwise, we need to look upwards since we can't make any local
1000 // conclusions.
1001 Instruction *RVI = dyn_cast<Instruction>(RetVal);
1002 if (!RVI)
1003 return false;
1004 switch (RVI->getOpcode()) {
1005 // Extend the analysis by looking upwards.
1006 case Instruction::BitCast:
1007 case Instruction::GetElementPtr:
1008 case Instruction::AddrSpaceCast:
1009 FlowsToReturn.insert(RVI->getOperand(0));
1010 continue;
1011 case Instruction::Select: {
1012 SelectInst *SI = cast<SelectInst>(RVI);
1013 FlowsToReturn.insert(SI->getTrueValue());
1014 FlowsToReturn.insert(SI->getFalseValue());
1015 continue;
1016 }
1017 case Instruction::PHI: {
1018 PHINode *PN = cast<PHINode>(RVI);
1019 for (int i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
1020 FlowsToReturn.insert(PN->getIncomingValue(i));
1021 continue;
1022 }
1023 case Instruction::Call:
1024 case Instruction::Invoke: {
1025 CallBase &CB = cast<CallBase>(*RVI);
1026 Function *Callee = CB.getCalledFunction();
1027 // A call to a node within the SCC is assumed to return null until
1028 // proven otherwise
1029 if (Callee && SCCNodes.count(Callee)) {
1030 Speculative = true;
1031 continue;
1032 }
1033 return false;
1034 }
1035 default:
1036 return false; // Unknown source, may be null
1037 };
1038 llvm_unreachable("should have either continued or returned");
1039 }
1040
1041 return true;
1042 }
1043
1044 /// Deduce nonnull attributes for the SCC.
addNonNullAttrs(const SCCNodeSet & SCCNodes)1045 static bool addNonNullAttrs(const SCCNodeSet &SCCNodes) {
1046 // Speculative that all functions in the SCC return only nonnull
1047 // pointers. We may refute this as we analyze functions.
1048 bool SCCReturnsNonNull = true;
1049
1050 bool MadeChange = false;
1051
1052 // Check each function in turn, determining which functions return nonnull
1053 // pointers.
1054 for (Function *F : SCCNodes) {
1055 // Already nonnull.
1056 if (F->getAttributes().hasAttribute(AttributeList::ReturnIndex,
1057 Attribute::NonNull))
1058 continue;
1059
1060 // We can infer and propagate function attributes only when we know that the
1061 // definition we'll get at link time is *exactly* the definition we see now.
1062 // For more details, see GlobalValue::mayBeDerefined.
1063 if (!F->hasExactDefinition())
1064 return false;
1065
1066 // We annotate nonnull return values, which are only applicable to
1067 // pointer types.
1068 if (!F->getReturnType()->isPointerTy())
1069 continue;
1070
1071 bool Speculative = false;
1072 if (isReturnNonNull(F, SCCNodes, Speculative)) {
1073 if (!Speculative) {
1074 // Mark the function eagerly since we may discover a function
1075 // which prevents us from speculating about the entire SCC
1076 LLVM_DEBUG(dbgs() << "Eagerly marking " << F->getName()
1077 << " as nonnull\n");
1078 F->addAttribute(AttributeList::ReturnIndex, Attribute::NonNull);
1079 ++NumNonNullReturn;
1080 MadeChange = true;
1081 }
1082 continue;
1083 }
1084 // At least one function returns something which could be null, can't
1085 // speculate any more.
1086 SCCReturnsNonNull = false;
1087 }
1088
1089 if (SCCReturnsNonNull) {
1090 for (Function *F : SCCNodes) {
1091 if (F->getAttributes().hasAttribute(AttributeList::ReturnIndex,
1092 Attribute::NonNull) ||
1093 !F->getReturnType()->isPointerTy())
1094 continue;
1095
1096 LLVM_DEBUG(dbgs() << "SCC marking " << F->getName() << " as nonnull\n");
1097 F->addAttribute(AttributeList::ReturnIndex, Attribute::NonNull);
1098 ++NumNonNullReturn;
1099 MadeChange = true;
1100 }
1101 }
1102
1103 return MadeChange;
1104 }
1105
1106 namespace {
1107
1108 /// Collects a set of attribute inference requests and performs them all in one
1109 /// go on a single SCC Node. Inference involves scanning function bodies
1110 /// looking for instructions that violate attribute assumptions.
1111 /// As soon as all the bodies are fine we are free to set the attribute.
1112 /// Customization of inference for individual attributes is performed by
1113 /// providing a handful of predicates for each attribute.
1114 class AttributeInferer {
1115 public:
1116 /// Describes a request for inference of a single attribute.
1117 struct InferenceDescriptor {
1118
1119 /// Returns true if this function does not have to be handled.
1120 /// General intent for this predicate is to provide an optimization
1121 /// for functions that do not need this attribute inference at all
1122 /// (say, for functions that already have the attribute).
1123 std::function<bool(const Function &)> SkipFunction;
1124
1125 /// Returns true if this instruction violates attribute assumptions.
1126 std::function<bool(Instruction &)> InstrBreaksAttribute;
1127
1128 /// Sets the inferred attribute for this function.
1129 std::function<void(Function &)> SetAttribute;
1130
1131 /// Attribute we derive.
1132 Attribute::AttrKind AKind;
1133
1134 /// If true, only "exact" definitions can be used to infer this attribute.
1135 /// See GlobalValue::isDefinitionExact.
1136 bool RequiresExactDefinition;
1137
InferenceDescriptor__anonec1461e50611::AttributeInferer::InferenceDescriptor1138 InferenceDescriptor(Attribute::AttrKind AK,
1139 std::function<bool(const Function &)> SkipFunc,
1140 std::function<bool(Instruction &)> InstrScan,
1141 std::function<void(Function &)> SetAttr,
1142 bool ReqExactDef)
1143 : SkipFunction(SkipFunc), InstrBreaksAttribute(InstrScan),
1144 SetAttribute(SetAttr), AKind(AK),
1145 RequiresExactDefinition(ReqExactDef) {}
1146 };
1147
1148 private:
1149 SmallVector<InferenceDescriptor, 4> InferenceDescriptors;
1150
1151 public:
registerAttrInference(InferenceDescriptor AttrInference)1152 void registerAttrInference(InferenceDescriptor AttrInference) {
1153 InferenceDescriptors.push_back(AttrInference);
1154 }
1155
1156 bool run(const SCCNodeSet &SCCNodes);
1157 };
1158
1159 /// Perform all the requested attribute inference actions according to the
1160 /// attribute predicates stored before.
run(const SCCNodeSet & SCCNodes)1161 bool AttributeInferer::run(const SCCNodeSet &SCCNodes) {
1162 SmallVector<InferenceDescriptor, 4> InferInSCC = InferenceDescriptors;
1163 // Go through all the functions in SCC and check corresponding attribute
1164 // assumptions for each of them. Attributes that are invalid for this SCC
1165 // will be removed from InferInSCC.
1166 for (Function *F : SCCNodes) {
1167
1168 // No attributes whose assumptions are still valid - done.
1169 if (InferInSCC.empty())
1170 return false;
1171
1172 // Check if our attributes ever need scanning/can be scanned.
1173 llvm::erase_if(InferInSCC, [F](const InferenceDescriptor &ID) {
1174 if (ID.SkipFunction(*F))
1175 return false;
1176
1177 // Remove from further inference (invalidate) when visiting a function
1178 // that has no instructions to scan/has an unsuitable definition.
1179 return F->isDeclaration() ||
1180 (ID.RequiresExactDefinition && !F->hasExactDefinition());
1181 });
1182
1183 // For each attribute still in InferInSCC that doesn't explicitly skip F,
1184 // set up the F instructions scan to verify assumptions of the attribute.
1185 SmallVector<InferenceDescriptor, 4> InferInThisFunc;
1186 llvm::copy_if(
1187 InferInSCC, std::back_inserter(InferInThisFunc),
1188 [F](const InferenceDescriptor &ID) { return !ID.SkipFunction(*F); });
1189
1190 if (InferInThisFunc.empty())
1191 continue;
1192
1193 // Start instruction scan.
1194 for (Instruction &I : instructions(*F)) {
1195 llvm::erase_if(InferInThisFunc, [&](const InferenceDescriptor &ID) {
1196 if (!ID.InstrBreaksAttribute(I))
1197 return false;
1198 // Remove attribute from further inference on any other functions
1199 // because attribute assumptions have just been violated.
1200 llvm::erase_if(InferInSCC, [&ID](const InferenceDescriptor &D) {
1201 return D.AKind == ID.AKind;
1202 });
1203 // Remove attribute from the rest of current instruction scan.
1204 return true;
1205 });
1206
1207 if (InferInThisFunc.empty())
1208 break;
1209 }
1210 }
1211
1212 if (InferInSCC.empty())
1213 return false;
1214
1215 bool Changed = false;
1216 for (Function *F : SCCNodes)
1217 // At this point InferInSCC contains only functions that were either:
1218 // - explicitly skipped from scan/inference, or
1219 // - verified to have no instructions that break attribute assumptions.
1220 // Hence we just go and force the attribute for all non-skipped functions.
1221 for (auto &ID : InferInSCC) {
1222 if (ID.SkipFunction(*F))
1223 continue;
1224 Changed = true;
1225 ID.SetAttribute(*F);
1226 }
1227 return Changed;
1228 }
1229
1230 struct SCCNodesResult {
1231 SCCNodeSet SCCNodes;
1232 bool HasUnknownCall;
1233 };
1234
1235 } // end anonymous namespace
1236
1237 /// Helper for non-Convergent inference predicate InstrBreaksAttribute.
InstrBreaksNonConvergent(Instruction & I,const SCCNodeSet & SCCNodes)1238 static bool InstrBreaksNonConvergent(Instruction &I,
1239 const SCCNodeSet &SCCNodes) {
1240 const CallBase *CB = dyn_cast<CallBase>(&I);
1241 // Breaks non-convergent assumption if CS is a convergent call to a function
1242 // not in the SCC.
1243 return CB && CB->isConvergent() &&
1244 SCCNodes.count(CB->getCalledFunction()) == 0;
1245 }
1246
1247 /// Helper for NoUnwind inference predicate InstrBreaksAttribute.
InstrBreaksNonThrowing(Instruction & I,const SCCNodeSet & SCCNodes)1248 static bool InstrBreaksNonThrowing(Instruction &I, const SCCNodeSet &SCCNodes) {
1249 if (!I.mayThrow())
1250 return false;
1251 if (const auto *CI = dyn_cast<CallInst>(&I)) {
1252 if (Function *Callee = CI->getCalledFunction()) {
1253 // I is a may-throw call to a function inside our SCC. This doesn't
1254 // invalidate our current working assumption that the SCC is no-throw; we
1255 // just have to scan that other function.
1256 if (SCCNodes.contains(Callee))
1257 return false;
1258 }
1259 }
1260 return true;
1261 }
1262
1263 /// Helper for NoFree inference predicate InstrBreaksAttribute.
InstrBreaksNoFree(Instruction & I,const SCCNodeSet & SCCNodes)1264 static bool InstrBreaksNoFree(Instruction &I, const SCCNodeSet &SCCNodes) {
1265 CallBase *CB = dyn_cast<CallBase>(&I);
1266 if (!CB)
1267 return false;
1268
1269 Function *Callee = CB->getCalledFunction();
1270 if (!Callee)
1271 return true;
1272
1273 if (Callee->doesNotFreeMemory())
1274 return false;
1275
1276 if (SCCNodes.contains(Callee))
1277 return false;
1278
1279 return true;
1280 }
1281
1282 /// Attempt to remove convergent function attribute when possible.
1283 ///
1284 /// Returns true if any changes to function attributes were made.
inferConvergent(const SCCNodeSet & SCCNodes)1285 static bool inferConvergent(const SCCNodeSet &SCCNodes) {
1286 AttributeInferer AI;
1287
1288 // Request to remove the convergent attribute from all functions in the SCC
1289 // if every callsite within the SCC is not convergent (except for calls
1290 // to functions within the SCC).
1291 // Note: Removal of the attr from the callsites will happen in
1292 // InstCombineCalls separately.
1293 AI.registerAttrInference(AttributeInferer::InferenceDescriptor{
1294 Attribute::Convergent,
1295 // Skip non-convergent functions.
1296 [](const Function &F) { return !F.isConvergent(); },
1297 // Instructions that break non-convergent assumption.
1298 [SCCNodes](Instruction &I) {
1299 return InstrBreaksNonConvergent(I, SCCNodes);
1300 },
1301 [](Function &F) {
1302 LLVM_DEBUG(dbgs() << "Removing convergent attr from fn " << F.getName()
1303 << "\n");
1304 F.setNotConvergent();
1305 },
1306 /* RequiresExactDefinition= */ false});
1307 // Perform all the requested attribute inference actions.
1308 return AI.run(SCCNodes);
1309 }
1310
1311 /// Infer attributes from all functions in the SCC by scanning every
1312 /// instruction for compliance to the attribute assumptions. Currently it
1313 /// does:
1314 /// - addition of NoUnwind attribute
1315 ///
1316 /// Returns true if any changes to function attributes were made.
inferAttrsFromFunctionBodies(const SCCNodeSet & SCCNodes)1317 static bool inferAttrsFromFunctionBodies(const SCCNodeSet &SCCNodes) {
1318 AttributeInferer AI;
1319
1320 if (!DisableNoUnwindInference)
1321 // Request to infer nounwind attribute for all the functions in the SCC if
1322 // every callsite within the SCC is not throwing (except for calls to
1323 // functions within the SCC). Note that nounwind attribute suffers from
1324 // derefinement - results may change depending on how functions are
1325 // optimized. Thus it can be inferred only from exact definitions.
1326 AI.registerAttrInference(AttributeInferer::InferenceDescriptor{
1327 Attribute::NoUnwind,
1328 // Skip non-throwing functions.
1329 [](const Function &F) { return F.doesNotThrow(); },
1330 // Instructions that break non-throwing assumption.
1331 [&SCCNodes](Instruction &I) {
1332 return InstrBreaksNonThrowing(I, SCCNodes);
1333 },
1334 [](Function &F) {
1335 LLVM_DEBUG(dbgs()
1336 << "Adding nounwind attr to fn " << F.getName() << "\n");
1337 F.setDoesNotThrow();
1338 ++NumNoUnwind;
1339 },
1340 /* RequiresExactDefinition= */ true});
1341
1342 if (!DisableNoFreeInference)
1343 // Request to infer nofree attribute for all the functions in the SCC if
1344 // every callsite within the SCC does not directly or indirectly free
1345 // memory (except for calls to functions within the SCC). Note that nofree
1346 // attribute suffers from derefinement - results may change depending on
1347 // how functions are optimized. Thus it can be inferred only from exact
1348 // definitions.
1349 AI.registerAttrInference(AttributeInferer::InferenceDescriptor{
1350 Attribute::NoFree,
1351 // Skip functions known not to free memory.
1352 [](const Function &F) { return F.doesNotFreeMemory(); },
1353 // Instructions that break non-deallocating assumption.
1354 [&SCCNodes](Instruction &I) {
1355 return InstrBreaksNoFree(I, SCCNodes);
1356 },
1357 [](Function &F) {
1358 LLVM_DEBUG(dbgs()
1359 << "Adding nofree attr to fn " << F.getName() << "\n");
1360 F.setDoesNotFreeMemory();
1361 ++NumNoFree;
1362 },
1363 /* RequiresExactDefinition= */ true});
1364
1365 // Perform all the requested attribute inference actions.
1366 return AI.run(SCCNodes);
1367 }
1368
addNoRecurseAttrs(const SCCNodeSet & SCCNodes)1369 static bool addNoRecurseAttrs(const SCCNodeSet &SCCNodes) {
1370 // Try and identify functions that do not recurse.
1371
1372 // If the SCC contains multiple nodes we know for sure there is recursion.
1373 if (SCCNodes.size() != 1)
1374 return false;
1375
1376 Function *F = *SCCNodes.begin();
1377 if (!F || !F->hasExactDefinition() || F->doesNotRecurse())
1378 return false;
1379
1380 // If all of the calls in F are identifiable and are to norecurse functions, F
1381 // is norecurse. This check also detects self-recursion as F is not currently
1382 // marked norecurse, so any called from F to F will not be marked norecurse.
1383 for (auto &BB : *F)
1384 for (auto &I : BB.instructionsWithoutDebug())
1385 if (auto *CB = dyn_cast<CallBase>(&I)) {
1386 Function *Callee = CB->getCalledFunction();
1387 if (!Callee || Callee == F || !Callee->doesNotRecurse())
1388 // Function calls a potentially recursive function.
1389 return false;
1390 }
1391
1392 // Every call was to a non-recursive function other than this function, and
1393 // we have no indirect recursion as the SCC size is one. This function cannot
1394 // recurse.
1395 F->setDoesNotRecurse();
1396 ++NumNoRecurse;
1397 return true;
1398 }
1399
instructionDoesNotReturn(Instruction & I)1400 static bool instructionDoesNotReturn(Instruction &I) {
1401 if (auto *CB = dyn_cast<CallBase>(&I)) {
1402 Function *Callee = CB->getCalledFunction();
1403 return Callee && Callee->doesNotReturn();
1404 }
1405 return false;
1406 }
1407
1408 // A basic block can only return if it terminates with a ReturnInst and does not
1409 // contain calls to noreturn functions.
basicBlockCanReturn(BasicBlock & BB)1410 static bool basicBlockCanReturn(BasicBlock &BB) {
1411 if (!isa<ReturnInst>(BB.getTerminator()))
1412 return false;
1413 return none_of(BB, instructionDoesNotReturn);
1414 }
1415
1416 // Set the noreturn function attribute if possible.
addNoReturnAttrs(const SCCNodeSet & SCCNodes)1417 static bool addNoReturnAttrs(const SCCNodeSet &SCCNodes) {
1418 bool Changed = false;
1419
1420 for (Function *F : SCCNodes) {
1421 if (!F || !F->hasExactDefinition() || F->hasFnAttribute(Attribute::Naked) ||
1422 F->doesNotReturn())
1423 continue;
1424
1425 // The function can return if any basic blocks can return.
1426 // FIXME: this doesn't handle recursion or unreachable blocks.
1427 if (none_of(*F, basicBlockCanReturn)) {
1428 F->setDoesNotReturn();
1429 Changed = true;
1430 }
1431 }
1432
1433 return Changed;
1434 }
1435
functionWillReturn(const Function & F)1436 static bool functionWillReturn(const Function &F) {
1437 // Must-progress function without side-effects must return.
1438 if (F.mustProgress() && F.onlyReadsMemory())
1439 return true;
1440
1441 // Can only analyze functions with a definition.
1442 if (F.isDeclaration())
1443 return false;
1444
1445 // Functions with loops require more sophisticated analysis, as the loop
1446 // may be infinite. For now, don't try to handle them.
1447 SmallVector<std::pair<const BasicBlock *, const BasicBlock *>> Backedges;
1448 FindFunctionBackedges(F, Backedges);
1449 if (!Backedges.empty())
1450 return false;
1451
1452 // If there are no loops, then the function is willreturn if all calls in
1453 // it are willreturn.
1454 return all_of(instructions(F), [](const Instruction &I) {
1455 return I.willReturn();
1456 });
1457 }
1458
1459 // Set the willreturn function attribute if possible.
addWillReturn(const SCCNodeSet & SCCNodes)1460 static bool addWillReturn(const SCCNodeSet &SCCNodes) {
1461 bool Changed = false;
1462
1463 for (Function *F : SCCNodes) {
1464 if (!F || F->willReturn() || !functionWillReturn(*F))
1465 continue;
1466
1467 F->setWillReturn();
1468 NumWillReturn++;
1469 Changed = true;
1470 }
1471
1472 return Changed;
1473 }
1474
createSCCNodeSet(ArrayRef<Function * > Functions)1475 static SCCNodesResult createSCCNodeSet(ArrayRef<Function *> Functions) {
1476 SCCNodesResult Res;
1477 Res.HasUnknownCall = false;
1478 for (Function *F : Functions) {
1479 if (!F || F->hasOptNone() || F->hasFnAttribute(Attribute::Naked)) {
1480 // Treat any function we're trying not to optimize as if it were an
1481 // indirect call and omit it from the node set used below.
1482 Res.HasUnknownCall = true;
1483 continue;
1484 }
1485 // Track whether any functions in this SCC have an unknown call edge.
1486 // Note: if this is ever a performance hit, we can common it with
1487 // subsequent routines which also do scans over the instructions of the
1488 // function.
1489 if (!Res.HasUnknownCall) {
1490 for (Instruction &I : instructions(*F)) {
1491 if (auto *CB = dyn_cast<CallBase>(&I)) {
1492 if (!CB->getCalledFunction()) {
1493 Res.HasUnknownCall = true;
1494 break;
1495 }
1496 }
1497 }
1498 }
1499 Res.SCCNodes.insert(F);
1500 }
1501 return Res;
1502 }
1503
1504 template <typename AARGetterT>
deriveAttrsInPostOrder(ArrayRef<Function * > Functions,AARGetterT && AARGetter)1505 static bool deriveAttrsInPostOrder(ArrayRef<Function *> Functions,
1506 AARGetterT &&AARGetter) {
1507 SCCNodesResult Nodes = createSCCNodeSet(Functions);
1508 bool Changed = false;
1509
1510 // Bail if the SCC only contains optnone functions.
1511 if (Nodes.SCCNodes.empty())
1512 return Changed;
1513
1514 Changed |= addArgumentReturnedAttrs(Nodes.SCCNodes);
1515 Changed |= addReadAttrs(Nodes.SCCNodes, AARGetter);
1516 Changed |= addArgumentAttrs(Nodes.SCCNodes);
1517 Changed |= inferConvergent(Nodes.SCCNodes);
1518 Changed |= addNoReturnAttrs(Nodes.SCCNodes);
1519 Changed |= addWillReturn(Nodes.SCCNodes);
1520
1521 // If we have no external nodes participating in the SCC, we can deduce some
1522 // more precise attributes as well.
1523 if (!Nodes.HasUnknownCall) {
1524 Changed |= addNoAliasAttrs(Nodes.SCCNodes);
1525 Changed |= addNonNullAttrs(Nodes.SCCNodes);
1526 Changed |= inferAttrsFromFunctionBodies(Nodes.SCCNodes);
1527 Changed |= addNoRecurseAttrs(Nodes.SCCNodes);
1528 }
1529
1530 return Changed;
1531 }
1532
run(LazyCallGraph::SCC & C,CGSCCAnalysisManager & AM,LazyCallGraph & CG,CGSCCUpdateResult &)1533 PreservedAnalyses PostOrderFunctionAttrsPass::run(LazyCallGraph::SCC &C,
1534 CGSCCAnalysisManager &AM,
1535 LazyCallGraph &CG,
1536 CGSCCUpdateResult &) {
1537 FunctionAnalysisManager &FAM =
1538 AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C, CG).getManager();
1539
1540 // We pass a lambda into functions to wire them up to the analysis manager
1541 // for getting function analyses.
1542 auto AARGetter = [&](Function &F) -> AAResults & {
1543 return FAM.getResult<AAManager>(F);
1544 };
1545
1546 SmallVector<Function *, 8> Functions;
1547 for (LazyCallGraph::Node &N : C) {
1548 Functions.push_back(&N.getFunction());
1549 }
1550
1551 if (deriveAttrsInPostOrder(Functions, AARGetter))
1552 return PreservedAnalyses::none();
1553
1554 return PreservedAnalyses::all();
1555 }
1556
1557 namespace {
1558
1559 struct PostOrderFunctionAttrsLegacyPass : public CallGraphSCCPass {
1560 // Pass identification, replacement for typeid
1561 static char ID;
1562
PostOrderFunctionAttrsLegacyPass__anonec1461e51611::PostOrderFunctionAttrsLegacyPass1563 PostOrderFunctionAttrsLegacyPass() : CallGraphSCCPass(ID) {
1564 initializePostOrderFunctionAttrsLegacyPassPass(
1565 *PassRegistry::getPassRegistry());
1566 }
1567
1568 bool runOnSCC(CallGraphSCC &SCC) override;
1569
getAnalysisUsage__anonec1461e51611::PostOrderFunctionAttrsLegacyPass1570 void getAnalysisUsage(AnalysisUsage &AU) const override {
1571 AU.setPreservesCFG();
1572 AU.addRequired<AssumptionCacheTracker>();
1573 getAAResultsAnalysisUsage(AU);
1574 CallGraphSCCPass::getAnalysisUsage(AU);
1575 }
1576 };
1577
1578 } // end anonymous namespace
1579
1580 char PostOrderFunctionAttrsLegacyPass::ID = 0;
1581 INITIALIZE_PASS_BEGIN(PostOrderFunctionAttrsLegacyPass, "function-attrs",
1582 "Deduce function attributes", false, false)
INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)1583 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
1584 INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass)
1585 INITIALIZE_PASS_END(PostOrderFunctionAttrsLegacyPass, "function-attrs",
1586 "Deduce function attributes", false, false)
1587
1588 Pass *llvm::createPostOrderFunctionAttrsLegacyPass() {
1589 return new PostOrderFunctionAttrsLegacyPass();
1590 }
1591
1592 template <typename AARGetterT>
runImpl(CallGraphSCC & SCC,AARGetterT AARGetter)1593 static bool runImpl(CallGraphSCC &SCC, AARGetterT AARGetter) {
1594 SmallVector<Function *, 8> Functions;
1595 for (CallGraphNode *I : SCC) {
1596 Functions.push_back(I->getFunction());
1597 }
1598
1599 return deriveAttrsInPostOrder(Functions, AARGetter);
1600 }
1601
runOnSCC(CallGraphSCC & SCC)1602 bool PostOrderFunctionAttrsLegacyPass::runOnSCC(CallGraphSCC &SCC) {
1603 if (skipSCC(SCC))
1604 return false;
1605 return runImpl(SCC, LegacyAARGetter(*this));
1606 }
1607
1608 namespace {
1609
1610 struct ReversePostOrderFunctionAttrsLegacyPass : public ModulePass {
1611 // Pass identification, replacement for typeid
1612 static char ID;
1613
ReversePostOrderFunctionAttrsLegacyPass__anonec1461e51711::ReversePostOrderFunctionAttrsLegacyPass1614 ReversePostOrderFunctionAttrsLegacyPass() : ModulePass(ID) {
1615 initializeReversePostOrderFunctionAttrsLegacyPassPass(
1616 *PassRegistry::getPassRegistry());
1617 }
1618
1619 bool runOnModule(Module &M) override;
1620
getAnalysisUsage__anonec1461e51711::ReversePostOrderFunctionAttrsLegacyPass1621 void getAnalysisUsage(AnalysisUsage &AU) const override {
1622 AU.setPreservesCFG();
1623 AU.addRequired<CallGraphWrapperPass>();
1624 AU.addPreserved<CallGraphWrapperPass>();
1625 }
1626 };
1627
1628 } // end anonymous namespace
1629
1630 char ReversePostOrderFunctionAttrsLegacyPass::ID = 0;
1631
1632 INITIALIZE_PASS_BEGIN(ReversePostOrderFunctionAttrsLegacyPass,
1633 "rpo-function-attrs", "Deduce function attributes in RPO",
1634 false, false)
INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass)1635 INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass)
1636 INITIALIZE_PASS_END(ReversePostOrderFunctionAttrsLegacyPass,
1637 "rpo-function-attrs", "Deduce function attributes in RPO",
1638 false, false)
1639
1640 Pass *llvm::createReversePostOrderFunctionAttrsPass() {
1641 return new ReversePostOrderFunctionAttrsLegacyPass();
1642 }
1643
addNoRecurseAttrsTopDown(Function & F)1644 static bool addNoRecurseAttrsTopDown(Function &F) {
1645 // We check the preconditions for the function prior to calling this to avoid
1646 // the cost of building up a reversible post-order list. We assert them here
1647 // to make sure none of the invariants this relies on were violated.
1648 assert(!F.isDeclaration() && "Cannot deduce norecurse without a definition!");
1649 assert(!F.doesNotRecurse() &&
1650 "This function has already been deduced as norecurs!");
1651 assert(F.hasInternalLinkage() &&
1652 "Can only do top-down deduction for internal linkage functions!");
1653
1654 // If F is internal and all of its uses are calls from a non-recursive
1655 // functions, then none of its calls could in fact recurse without going
1656 // through a function marked norecurse, and so we can mark this function too
1657 // as norecurse. Note that the uses must actually be calls -- otherwise
1658 // a pointer to this function could be returned from a norecurse function but
1659 // this function could be recursively (indirectly) called. Note that this
1660 // also detects if F is directly recursive as F is not yet marked as
1661 // a norecurse function.
1662 for (auto *U : F.users()) {
1663 auto *I = dyn_cast<Instruction>(U);
1664 if (!I)
1665 return false;
1666 CallBase *CB = dyn_cast<CallBase>(I);
1667 if (!CB || !CB->getParent()->getParent()->doesNotRecurse())
1668 return false;
1669 }
1670 F.setDoesNotRecurse();
1671 ++NumNoRecurse;
1672 return true;
1673 }
1674
deduceFunctionAttributeInRPO(Module & M,CallGraph & CG)1675 static bool deduceFunctionAttributeInRPO(Module &M, CallGraph &CG) {
1676 // We only have a post-order SCC traversal (because SCCs are inherently
1677 // discovered in post-order), so we accumulate them in a vector and then walk
1678 // it in reverse. This is simpler than using the RPO iterator infrastructure
1679 // because we need to combine SCC detection and the PO walk of the call
1680 // graph. We can also cheat egregiously because we're primarily interested in
1681 // synthesizing norecurse and so we can only save the singular SCCs as SCCs
1682 // with multiple functions in them will clearly be recursive.
1683 SmallVector<Function *, 16> Worklist;
1684 for (scc_iterator<CallGraph *> I = scc_begin(&CG); !I.isAtEnd(); ++I) {
1685 if (I->size() != 1)
1686 continue;
1687
1688 Function *F = I->front()->getFunction();
1689 if (F && !F->isDeclaration() && !F->doesNotRecurse() &&
1690 F->hasInternalLinkage())
1691 Worklist.push_back(F);
1692 }
1693
1694 bool Changed = false;
1695 for (auto *F : llvm::reverse(Worklist))
1696 Changed |= addNoRecurseAttrsTopDown(*F);
1697
1698 return Changed;
1699 }
1700
runOnModule(Module & M)1701 bool ReversePostOrderFunctionAttrsLegacyPass::runOnModule(Module &M) {
1702 if (skipModule(M))
1703 return false;
1704
1705 auto &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph();
1706
1707 return deduceFunctionAttributeInRPO(M, CG);
1708 }
1709
1710 PreservedAnalyses
run(Module & M,ModuleAnalysisManager & AM)1711 ReversePostOrderFunctionAttrsPass::run(Module &M, ModuleAnalysisManager &AM) {
1712 auto &CG = AM.getResult<CallGraphAnalysis>(M);
1713
1714 if (!deduceFunctionAttributeInRPO(M, CG))
1715 return PreservedAnalyses::all();
1716
1717 PreservedAnalyses PA;
1718 PA.preserve<CallGraphAnalysis>();
1719 return PA;
1720 }
1721