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 "IPOOptions.h"
17#include "llvm/ADT/ArrayRef.h"
18#include "llvm/ADT/DenseMap.h"
19#include "llvm/ADT/DepthFirstIterator.h"
20#include "llvm/ADT/PostOrderIterator.h"
21#include "llvm/ADT/SCCIterator.h"
22#include "llvm/ADT/STLExtras.h"
23#include "llvm/ADT/SetVector.h"
24#include "llvm/ADT/SmallPtrSet.h"
25#include "llvm/ADT/SmallVector.h"
26#include "llvm/ADT/Statistic.h"
27#include "llvm/Analysis/AssumptionCache.h"
28#include "llvm/Analysis/BasicAliasAnalysis.h"
29#include "llvm/Analysis/CFG.h"
30#include "llvm/Analysis/CGSCCPassManager.h"
31#include "llvm/Analysis/CallGraph.h"
32#include "llvm/Analysis/CaptureTracking.h"
33#include "llvm/Analysis/LazyCallGraph.h"
34#include "llvm/Analysis/MemoryLocation.h"
35#include "llvm/Analysis/ValueTracking.h"
36#include "llvm/IR/Argument.h"
37#include "llvm/IR/Attributes.h"
38#include "llvm/IR/BasicBlock.h"
39#include "llvm/IR/Constant.h"
40#include "llvm/IR/ConstantRangeList.h"
41#include "llvm/IR/Constants.h"
42#include "llvm/IR/Function.h"
43#include "llvm/IR/InstIterator.h"
44#include "llvm/IR/InstrTypes.h"
45#include "llvm/IR/Instruction.h"
46#include "llvm/IR/Instructions.h"
47#include "llvm/IR/IntrinsicInst.h"
48#include "llvm/IR/Metadata.h"
49#include "llvm/IR/ModuleSummaryIndex.h"
50#include "llvm/IR/PassManager.h"
51#include "llvm/IR/PatternMatch.h"
52#include "llvm/IR/Type.h"
53#include "llvm/IR/Use.h"
54#include "llvm/IR/User.h"
55#include "llvm/IR/Value.h"
56#include "llvm/Support/Casting.h"
57#include "llvm/Support/CommandLine.h"
58#include "llvm/Support/Compiler.h"
59#include "llvm/Support/Debug.h"
60#include "llvm/Support/ErrorHandling.h"
61#include "llvm/Support/KnownFPClass.h"
62#include "llvm/Support/raw_ostream.h"
63#include "llvm/Transforms/IPO.h"
64#include "llvm/Transforms/Utils/Local.h"
65#include <cassert>
66#include <iterator>
67#include <map>
68#include <optional>
69#include <vector>
70
71using namespace llvm;
72using namespace llvm::PatternMatch;
73
74#define DEBUG_TYPE "function-attrs"
75
76STATISTIC(NumMemoryAttr, "Number of functions with improved memory attribute");
77STATISTIC(NumCapturesNone, "Number of arguments marked captures(none)");
78STATISTIC(NumCapturesPartial, "Number of arguments marked with captures "
79 "attribute other than captures(none)");
80STATISTIC(NumReturned, "Number of arguments marked returned");
81STATISTIC(NumReadNoneArg, "Number of arguments marked readnone");
82STATISTIC(NumReadOnlyArg, "Number of arguments marked readonly");
83STATISTIC(NumWriteOnlyArg, "Number of arguments marked writeonly");
84STATISTIC(NumNoAlias, "Number of function returns marked noalias");
85STATISTIC(NumNonNullReturn, "Number of function returns marked nonnull");
86STATISTIC(NumNoUndefReturn, "Number of function returns marked noundef");
87STATISTIC(NumNoRecurse, "Number of functions marked as norecurse");
88STATISTIC(NumNoUnwind, "Number of functions marked as nounwind");
89STATISTIC(NumNoFree, "Number of functions marked as nofree");
90STATISTIC(NumNoFreeArg, "Number of arguments marked as nofree");
91STATISTIC(NumWillReturn, "Number of functions marked as willreturn");
92STATISTIC(NumNoSync, "Number of functions marked as nosync");
93STATISTIC(NumCold, "Number of functions marked as cold");
94
95STATISTIC(NumThinLinkNoRecurse,
96 "Number of functions marked as norecurse during thinlink");
97STATISTIC(NumThinLinkNoUnwind,
98 "Number of functions marked as nounwind during thinlink");
99
100static cl::opt<bool> DisableThinLTOPropagation(
101 "disable-thinlto-funcattrs", cl::init(Val: true), cl::Hidden,
102 cl::desc("Don't propagate function-attrs in thinLTO"));
103
104static void addCapturesStat(CaptureInfo CI) {
105 if (capturesNothing(CC: CI))
106 ++NumCapturesNone;
107 else
108 ++NumCapturesPartial;
109}
110
111namespace {
112
113using SCCNodeSet = SmallSetVector<Function *, 8>;
114
115} // end anonymous namespace
116
117static void addLocAccess(MemoryEffects &ME, const MemoryLocation &Loc,
118 ModRefInfo MR, AAResults &AAR) {
119 // Ignore accesses to known-invariant or local memory.
120 MR &= AAR.getModRefInfoMask(Loc, /*IgnoreLocal=*/IgnoreLocals: true);
121 if (isNoModRef(MRI: MR))
122 return;
123
124 const Value *UO = getUnderlyingObjectAggressive(V: Loc.Ptr);
125 if (isa<AllocaInst>(Val: UO))
126 return;
127 if (isa<Argument>(Val: UO)) {
128 ME |= MemoryEffects::argMemOnly(MR);
129 return;
130 }
131
132 // If it's not an identified object, it might be an argument.
133 if (!isIdentifiedObject(V: UO))
134 ME |= MemoryEffects::argMemOnly(MR);
135 ME |= MemoryEffects(IRMemLocation::ErrnoMem, MR);
136 ME |= MemoryEffects(IRMemLocation::Other, MR);
137}
138
139static void addArgLocs(MemoryEffects &ME, const CallBase *Call,
140 ModRefInfo ArgMR, AAResults &AAR) {
141 for (const Value *Arg : Call->args()) {
142 if (!Arg->getType()->isPtrOrPtrVectorTy())
143 continue;
144
145 addLocAccess(ME,
146 Loc: MemoryLocation::getBeforeOrAfter(Ptr: Arg, AATags: Call->getAAMetadata()),
147 MR: ArgMR, AAR);
148 }
149}
150
151/// Returns the memory access attribute for function F using AAR for AA results,
152/// where SCCNodes is the current SCC.
153///
154/// If ThisBody is true, this function may examine the function body and will
155/// return a result pertaining to this copy of the function. If it is false, the
156/// result will be based only on AA results for the function declaration; it
157/// will be assumed that some other (perhaps less optimized) version of the
158/// function may be selected at link time.
159///
160/// The return value is split into two parts: Memory effects that always apply,
161/// and additional memory effects that apply if any of the functions in the SCC
162/// can access argmem.
163static std::pair<MemoryEffects, MemoryEffects>
164checkFunctionMemoryAccess(Function &F, bool ThisBody, AAResults &AAR,
165 const SCCNodeSet &SCCNodes) {
166 MemoryEffects OrigME = AAR.getMemoryEffects(F: &F);
167 if (OrigME.doesNotAccessMemory())
168 // Already perfect!
169 return {OrigME, MemoryEffects::none()};
170
171 if (!ThisBody)
172 return {OrigME, MemoryEffects::none()};
173
174 MemoryEffects ME = MemoryEffects::none();
175 // Additional locations accessed if the SCC accesses argmem.
176 MemoryEffects RecursiveArgME = MemoryEffects::none();
177
178 auto AddNonArgMemoryEffects = [&ME](MemoryEffects InstME) {
179 // Merge instruction memory effects, including inaccessible and errno
180 // memory, but excluding argument memory, which is handled separately.
181 ME |= InstME.getWithoutLoc(Loc: IRMemLocation::ArgMem);
182
183 // If the instruction accesses captured memory (currently part of "other")
184 // and an argument is captured (currently not tracked), then it may also
185 // access argument memory.
186 ModRefInfo OtherMR = InstME.getModRef(Loc: IRMemLocation::Other);
187 ME |= MemoryEffects::argMemOnly(MR: OtherMR);
188 };
189
190 // Inalloca and preallocated arguments are always clobbered by the call.
191 if (F.getAttributes().hasAttrSomewhere(Kind: Attribute::InAlloca) ||
192 F.getAttributes().hasAttrSomewhere(Kind: Attribute::Preallocated))
193 ME |= MemoryEffects::argMemOnly(MR: ModRefInfo::ModRef);
194
195 // Scan the function body for instructions that may read or write memory.
196 for (Instruction &I : instructions(F)) {
197 // Some instructions can be ignored even if they read or write memory.
198 // Detect these now, skipping to the next instruction if one is found.
199 // We can optimistically ignore calls to functions in the same SCC, with
200 // two caveats:
201 // * Calls with operand bundles may have additional effects.
202 // * Argument memory accesses may imply additional effects depending on
203 // what the argument location is.
204 auto *Call = dyn_cast<CallBase>(Val: &I);
205 if (Call && !Call->hasOperandBundles() && Call->getCalledFunction() &&
206 SCCNodes.count(key: Call->getCalledFunction())) {
207 // Keep track of which additional locations are accessed if the SCC
208 // turns out to access argmem.
209 addArgLocs(ME&: RecursiveArgME, Call, ArgMR: ModRefInfo::ModRef, AAR);
210 continue;
211 }
212
213 // Once ME covers OrigME, the returned effects are final.
214 if ((ME & OrigME) == OrigME)
215 continue;
216
217 if (Call) {
218 MemoryEffects CallME = AAR.getMemoryEffects(Call);
219
220 // If the call doesn't access memory, we're done.
221 if (CallME.doesNotAccessMemory())
222 continue;
223
224 // A pseudo probe call shouldn't change any function attribute since it
225 // doesn't translate to a real instruction. It comes with a memory access
226 // tag to prevent itself being removed by optimizations and not block
227 // other instructions being optimized.
228 if (isa<PseudoProbeInst>(Val: I))
229 continue;
230
231 AddNonArgMemoryEffects(CallME);
232
233 // Check whether all pointer arguments point to local memory, and
234 // ignore calls that only access local memory.
235 ModRefInfo ArgMR = CallME.getModRef(Loc: IRMemLocation::ArgMem);
236 if (ArgMR != ModRefInfo::NoModRef)
237 addArgLocs(ME, Call, ArgMR, AAR);
238 continue;
239 }
240
241 MemoryEffects InstME = I.getMemoryEffects();
242 if (InstME.doesNotAccessMemory())
243 continue;
244
245 std::optional<MemoryLocation> Loc = MemoryLocation::getOrNone(Inst: &I);
246 if (!Loc) {
247 // If no location is known, conservatively assume anything can be
248 // accessed.
249 ME |= MemoryEffects(InstME.getModRef());
250 continue;
251 }
252
253 AddNonArgMemoryEffects(InstME);
254 addLocAccess(ME, Loc: *Loc, MR: InstME.getModRef(Loc: IRMemLocation::ArgMem), AAR);
255 }
256
257 return {OrigME & ME, RecursiveArgME};
258}
259
260MemoryEffects llvm::computeFunctionBodyMemoryAccess(Function &F,
261 AAResults &AAR) {
262 return checkFunctionMemoryAccess(F, /*ThisBody=*/true, AAR, SCCNodes: {}).first;
263}
264
265/// Deduce readonly/readnone/writeonly attributes for the SCC.
266template <typename AARGetterT>
267static void addMemoryAttrs(const SCCNodeSet &SCCNodes, AARGetterT &&AARGetter,
268 SmallPtrSet<Function *, 8> &Changed) {
269 MemoryEffects ME = MemoryEffects::none();
270 MemoryEffects RecursiveArgME = MemoryEffects::none();
271 for (Function *F : SCCNodes) {
272 // Call the callable parameter to look up AA results for this function.
273 AAResults &AAR = AARGetter(*F);
274 // Non-exact function definitions may not be selected at link time, and an
275 // alternative version that writes to memory may be selected. See the
276 // comment on GlobalValue::isDefinitionExact for more details.
277 auto [FnME, FnRecursiveArgME] =
278 checkFunctionMemoryAccess(F&: *F, ThisBody: F->hasExactDefinition(), AAR, SCCNodes);
279 ME |= FnME;
280 RecursiveArgME |= FnRecursiveArgME;
281 // Reached bottom of the lattice, we will not be able to improve the result.
282 if (ME == MemoryEffects::unknown())
283 return;
284 }
285
286 // If the SCC accesses argmem, add recursive accesses resulting from that.
287 ModRefInfo ArgMR = ME.getModRef(Loc: IRMemLocation::ArgMem);
288 if (ArgMR != ModRefInfo::NoModRef)
289 ME |= RecursiveArgME & MemoryEffects(ArgMR);
290
291 for (Function *F : SCCNodes) {
292 MemoryEffects OldME = F->getMemoryEffects();
293 MemoryEffects NewME = ME & OldME;
294 if (NewME != OldME) {
295 ++NumMemoryAttr;
296 F->setMemoryEffects(NewME);
297 // Remove conflicting writable attributes.
298 if (!isModSet(MRI: NewME.getModRef(Loc: IRMemLocation::ArgMem)))
299 for (Argument &A : F->args())
300 A.removeAttr(Kind: Attribute::Writable);
301 Changed.insert(Ptr: F);
302 }
303 }
304}
305
306// Compute definitive function attributes for a function taking into account
307// prevailing definitions and linkage types
308static FunctionSummary *calculatePrevailingSummary(
309 ValueInfo VI,
310 DenseMap<ValueInfo, FunctionSummary *> &CachedPrevailingSummary,
311 function_ref<bool(GlobalValue::GUID, const GlobalValueSummary *)>
312 IsPrevailing) {
313
314 auto [It, Inserted] = CachedPrevailingSummary.try_emplace(Key: VI);
315 if (!Inserted)
316 return It->second;
317
318 /// At this point, prevailing symbols have been resolved. The following leads
319 /// to returning a conservative result:
320 /// - Multiple instances with local linkage. Normally local linkage would be
321 /// unique per module
322 /// as the GUID includes the module path. We could have a guid alias if
323 /// there wasn't any distinguishing path when each file was compiled, but
324 /// that should be rare so we'll punt on those.
325
326 /// These next 2 cases should not happen and will assert:
327 /// - Multiple instances with external linkage. This should be caught in
328 /// symbol resolution
329 /// - Non-existent FunctionSummary for Aliasee. This presents a hole in our
330 /// knowledge meaning we have to go conservative.
331
332 /// Otherwise, we calculate attributes for a function as:
333 /// 1. If we have a local linkage, take its attributes. If there's somehow
334 /// multiple, bail and go conservative.
335 /// 2. If we have an external/WeakODR/LinkOnceODR linkage check that it is
336 /// prevailing, take its attributes.
337 /// 3. If we have a Weak/LinkOnce linkage the copies can have semantic
338 /// differences. However, if the prevailing copy is known it will be used
339 /// so take its attributes. If the prevailing copy is in a native file
340 /// all IR copies will be dead and propagation will go conservative.
341 /// 4. AvailableExternally summaries without a prevailing copy are known to
342 /// occur in a couple of circumstances:
343 /// a. An internal function gets imported due to its caller getting
344 /// imported, it becomes AvailableExternally but no prevailing
345 /// definition exists. Because it has to get imported along with its
346 /// caller the attributes will be captured by propagating on its
347 /// caller.
348 /// b. C++11 [temp.explicit]p10 can generate AvailableExternally
349 /// definitions of explicitly instanced template declarations
350 /// for inlining which are ultimately dropped from the TU. Since this
351 /// is localized to the TU the attributes will have already made it to
352 /// the callers.
353 /// These are edge cases and already captured by their callers so we
354 /// ignore these for now. If they become relevant to optimize in the
355 /// future this can be revisited.
356 /// 5. Otherwise, go conservative.
357
358 FunctionSummary *Local = nullptr;
359 FunctionSummary *Prevailing = nullptr;
360
361 for (const auto &GVS : VI.getSummaryList()) {
362 if (!GVS->isLive())
363 continue;
364
365 FunctionSummary *FS = dyn_cast<FunctionSummary>(Val: GVS->getBaseObject());
366 // Virtual and Unknown (e.g. indirect) calls require going conservative
367 if (!FS || FS->fflags().HasUnknownCall)
368 return nullptr;
369
370 const auto &Linkage = GVS->linkage();
371 if (GlobalValue::isLocalLinkage(Linkage)) {
372 if (Local) {
373 LLVM_DEBUG(
374 dbgs()
375 << "ThinLTO FunctionAttrs: Multiple Local Linkage, bailing on "
376 "function "
377 << VI.name() << " from " << FS->modulePath() << ". Previous module "
378 << Local->modulePath() << "\n");
379 return nullptr;
380 }
381 Local = FS;
382 } else if (GlobalValue::isExternalLinkage(Linkage)) {
383 assert(IsPrevailing(VI.getGUID(), GVS.get()) || GVS->wasPromoted());
384 Prevailing = FS;
385 break;
386 } else if (GlobalValue::isWeakODRLinkage(Linkage) ||
387 GlobalValue::isLinkOnceODRLinkage(Linkage) ||
388 GlobalValue::isWeakAnyLinkage(Linkage) ||
389 GlobalValue::isLinkOnceAnyLinkage(Linkage)) {
390 if (IsPrevailing(VI.getGUID(), GVS.get())) {
391 Prevailing = FS;
392 break;
393 }
394 } else if (GlobalValue::isAvailableExternallyLinkage(Linkage)) {
395 // TODO: Handle these cases if they become meaningful
396 continue;
397 }
398 }
399
400 auto &CPS = CachedPrevailingSummary[VI];
401 if (Local) {
402 assert(!Prevailing);
403 CPS = Local;
404 } else if (Prevailing) {
405 assert(!Local);
406 CPS = Prevailing;
407 }
408
409 return CPS;
410}
411
412bool llvm::thinLTOPropagateFunctionAttrs(
413 ModuleSummaryIndex &Index,
414 function_ref<bool(GlobalValue::GUID, const GlobalValueSummary *)>
415 IsPrevailing) {
416 // TODO: implement addNoAliasAttrs once
417 // there's more information about the return type in the summary
418 if (DisableThinLTOPropagation)
419 return false;
420
421 DenseMap<ValueInfo, FunctionSummary *> CachedPrevailingSummary;
422 bool Changed = false;
423
424 auto PropagateAttributes = [&](std::vector<ValueInfo> &SCCNodes) {
425 // Assume we can propagate unless we discover otherwise
426 FunctionSummary::FFlags InferredFlags;
427 InferredFlags.NoRecurse = (SCCNodes.size() == 1);
428 InferredFlags.NoUnwind = true;
429
430 for (auto &V : SCCNodes) {
431 FunctionSummary *CallerSummary =
432 calculatePrevailingSummary(VI: V, CachedPrevailingSummary, IsPrevailing);
433
434 // Function summaries can fail to contain information such as declarations
435 if (!CallerSummary)
436 return;
437
438 if (CallerSummary->fflags().MayThrow)
439 InferredFlags.NoUnwind = false;
440
441 for (const auto &Callee : CallerSummary->calls()) {
442 FunctionSummary *CalleeSummary = calculatePrevailingSummary(
443 VI: Callee.first, CachedPrevailingSummary, IsPrevailing);
444
445 if (!CalleeSummary)
446 return;
447
448 if (!CalleeSummary->fflags().NoRecurse)
449 InferredFlags.NoRecurse = false;
450
451 if (!CalleeSummary->fflags().NoUnwind)
452 InferredFlags.NoUnwind = false;
453
454 if (!InferredFlags.NoUnwind && !InferredFlags.NoRecurse)
455 break;
456 }
457 }
458
459 if (InferredFlags.NoUnwind || InferredFlags.NoRecurse) {
460 Changed = true;
461 for (auto &V : SCCNodes) {
462 if (InferredFlags.NoRecurse) {
463 LLVM_DEBUG(dbgs() << "ThinLTO FunctionAttrs: Propagated NoRecurse to "
464 << V.name() << "\n");
465 ++NumThinLinkNoRecurse;
466 }
467
468 if (InferredFlags.NoUnwind) {
469 LLVM_DEBUG(dbgs() << "ThinLTO FunctionAttrs: Propagated NoUnwind to "
470 << V.name() << "\n");
471 ++NumThinLinkNoUnwind;
472 }
473
474 for (const auto &S : V.getSummaryList()) {
475 if (auto *FS = dyn_cast<FunctionSummary>(Val: S.get())) {
476 if (InferredFlags.NoRecurse)
477 FS->setNoRecurse();
478
479 if (InferredFlags.NoUnwind)
480 FS->setNoUnwind();
481 }
482 }
483 }
484 }
485 };
486
487 // Call propagation functions on each SCC in the Index
488 for (scc_iterator<ModuleSummaryIndex *> I = scc_begin(G: &Index); !I.isAtEnd();
489 ++I) {
490 std::vector<ValueInfo> Nodes(*I);
491 PropagateAttributes(Nodes);
492 }
493 return Changed;
494}
495
496namespace {
497
498/// For a given pointer Argument, this retains a list of Arguments of functions
499/// in the same SCC that the pointer data flows into. We use this to build an
500/// SCC of the arguments.
501struct ArgumentGraphNode {
502 Argument *Definition;
503 /// CaptureComponents for this argument, excluding captures via Uses.
504 /// We don't distinguish between other/return captures here.
505 CaptureComponents CC = CaptureComponents::None;
506 SmallVector<ArgumentGraphNode *, 4> Uses;
507};
508
509class ArgumentGraph {
510 // We store pointers to ArgumentGraphNode objects, so it's important that
511 // that they not move around upon insert.
512 using ArgumentMapTy = std::map<Argument *, ArgumentGraphNode>;
513
514 ArgumentMapTy ArgumentMap;
515
516 // There is no root node for the argument graph, in fact:
517 // void f(int *x, int *y) { if (...) f(x, y); }
518 // is an example where the graph is disconnected. The SCCIterator requires a
519 // single entry point, so we maintain a fake ("synthetic") root node that
520 // uses every node. Because the graph is directed and nothing points into
521 // the root, it will not participate in any SCCs (except for its own).
522 ArgumentGraphNode SyntheticRoot;
523
524public:
525 ArgumentGraph() { SyntheticRoot.Definition = nullptr; }
526
527 using iterator = SmallVectorImpl<ArgumentGraphNode *>::iterator;
528
529 iterator begin() { return SyntheticRoot.Uses.begin(); }
530 iterator end() { return SyntheticRoot.Uses.end(); }
531 ArgumentGraphNode *getEntryNode() { return &SyntheticRoot; }
532
533 ArgumentGraphNode *operator[](Argument *A) {
534 ArgumentGraphNode &Node = ArgumentMap[A];
535 Node.Definition = A;
536 SyntheticRoot.Uses.push_back(Elt: &Node);
537 return &Node;
538 }
539};
540
541/// This tracker checks whether callees are in the SCC, and if so it does not
542/// consider that a capture, instead adding it to the "Uses" list and
543/// continuing with the analysis.
544struct ArgumentUsesTracker : public CaptureTracker {
545 ArgumentUsesTracker(const SCCNodeSet &SCCNodes) : SCCNodes(SCCNodes) {}
546
547 void tooManyUses() override { CI = CaptureInfo::all(); }
548
549 Action captured(const Use *U, UseCaptureInfo UseCI) override {
550 if (updateCaptureInfo(U, CC: UseCI.UseCC)) {
551 // Don't bother continuing if we already capture everything.
552 if (capturesAll(CC: CI.getOtherComponents()))
553 return Stop;
554 return Continue;
555 }
556
557 // For SCC argument tracking, we're not going to analyze other/ret
558 // components separately, so don't follow the return value.
559 return ContinueIgnoringReturn;
560 }
561
562 bool updateCaptureInfo(const Use *U, CaptureComponents CC) {
563 CallBase *CB = dyn_cast<CallBase>(Val: U->getUser());
564 if (!CB) {
565 if (isa<ReturnInst>(Val: U->getUser()))
566 CI |= CaptureInfo::retOnly(RetComponents: CC);
567 else
568 // Conservatively assume that the captured value might make its way
569 // into the return value as well. This could be made more precise.
570 CI |= CaptureInfo(CC);
571 return true;
572 }
573
574 Function *F = CB->getCalledFunction();
575 if (!F || !F->hasExactDefinition() || !SCCNodes.count(key: F)) {
576 CI |= CaptureInfo(CC);
577 return true;
578 }
579
580 assert(!CB->isCallee(U) && "callee operand reported captured?");
581 const unsigned UseIndex = CB->getDataOperandNo(U);
582 if (UseIndex >= CB->arg_size()) {
583 // Data operand, but not a argument operand -- must be a bundle operand
584 assert(CB->hasOperandBundles() && "Must be!");
585
586 // CaptureTracking told us that we're being captured by an operand bundle
587 // use. In this case it does not matter if the callee is within our SCC
588 // or not -- we've been captured in some unknown way, and we have to be
589 // conservative.
590 CI |= CaptureInfo(CC);
591 return true;
592 }
593
594 if (UseIndex >= F->arg_size()) {
595 assert(F->isVarArg() && "More params than args in non-varargs call");
596 CI |= CaptureInfo(CC);
597 return true;
598 }
599
600 // TODO(captures): Could improve precision by remembering maximum
601 // capture components for the argument.
602 Uses.push_back(Elt: &*std::next(x: F->arg_begin(), n: UseIndex));
603 return false;
604 }
605
606 // Does not include potential captures via Uses in the SCC.
607 CaptureInfo CI = CaptureInfo::none();
608
609 // Uses within our SCC.
610 SmallVector<Argument *, 4> Uses;
611
612 const SCCNodeSet &SCCNodes;
613};
614
615/// A struct of argument use: a Use and the offset it accesses. This struct
616/// is to track uses inside function via GEP. If GEP has a non-constant index,
617/// the Offset field is nullopt.
618struct ArgumentUse {
619 Use *U;
620 std::optional<int64_t> Offset;
621};
622
623/// A struct of argument access info. "Unknown" accesses are the cases like
624/// unrecognized instructions, instructions that have more than one use of
625/// the argument, or volatile memory accesses. "WriteWithSideEffect" are call
626/// instructions that not only write an argument but also capture it.
627struct ArgumentAccessInfo {
628 enum class AccessType : uint8_t { Write, WriteWithSideEffect, Read, Unknown };
629 AccessType ArgAccessType;
630 ConstantRangeList AccessRanges;
631};
632
633/// A struct to wrap the argument use info per block.
634struct UsesPerBlockInfo {
635 SmallDenseMap<Instruction *, ArgumentAccessInfo, 4> Insts;
636 bool HasWrites = false;
637 bool HasUnknownAccess = false;
638};
639
640/// A struct to summarize the argument use info in a function.
641struct ArgumentUsesSummary {
642 bool HasAnyWrite = false;
643 bool HasWriteOutsideEntryBB = false;
644 SmallDenseMap<const BasicBlock *, UsesPerBlockInfo, 16> UsesPerBlock;
645};
646
647ArgumentAccessInfo getArgumentAccessInfo(const Instruction *I,
648 const ArgumentUse &ArgUse,
649 const DataLayout &DL) {
650 auto GetTypeAccessRange =
651 [&DL](Type *Ty,
652 std::optional<int64_t> Offset) -> std::optional<ConstantRange> {
653 auto TypeSize = DL.getTypeStoreSize(Ty);
654 if (!TypeSize.isScalable() && Offset) {
655 int64_t Size = TypeSize.getFixedValue();
656 APInt Low(64, *Offset, true);
657 bool Overflow;
658 APInt High = Low.sadd_ov(RHS: APInt(64, Size, true), Overflow);
659 // Bail if the range overflows signed 64-bit int.
660 if (Overflow)
661 return std::nullopt;
662 return ConstantRange(Low, High);
663 }
664 return std::nullopt;
665 };
666 auto GetConstantIntRange =
667 [](Value *Length,
668 std::optional<int64_t> Offset) -> std::optional<ConstantRange> {
669 auto *ConstantLength = dyn_cast<ConstantInt>(Val: Length);
670 if (ConstantLength && Offset) {
671 int64_t Len = ConstantLength->getSExtValue();
672
673 // Reject zero or negative lengths
674 if (Len <= 0)
675 return std::nullopt;
676
677 APInt Low(64, *Offset, true);
678 bool Overflow;
679 APInt High = Low.sadd_ov(RHS: APInt(64, Len, true), Overflow);
680 if (Overflow)
681 return std::nullopt;
682
683 return ConstantRange(Low, High);
684 }
685 return std::nullopt;
686 };
687
688 if (auto *SI = dyn_cast<StoreInst>(Val: I)) {
689 if (SI->isSimple() && &SI->getOperandUse(i: 1) == ArgUse.U) {
690 // Get the fixed type size of "SI". Since the access range of a write
691 // will be unioned, if "SI" doesn't have a fixed type size, we just set
692 // the access range to empty.
693 ConstantRangeList AccessRanges;
694 if (auto TypeAccessRange =
695 GetTypeAccessRange(SI->getAccessType(), ArgUse.Offset))
696 AccessRanges.insert(NewRange: *TypeAccessRange);
697 return {.ArgAccessType: ArgumentAccessInfo::AccessType::Write, .AccessRanges: std::move(AccessRanges)};
698 }
699 } else if (auto *LI = dyn_cast<LoadInst>(Val: I)) {
700 if (LI->isSimple()) {
701 assert(&LI->getOperandUse(0) == ArgUse.U);
702 // Get the fixed type size of "LI". Different from Write, if "LI"
703 // doesn't have a fixed type size, we conservatively set as a clobber
704 // with an empty access range.
705 if (auto TypeAccessRange =
706 GetTypeAccessRange(LI->getAccessType(), ArgUse.Offset))
707 return {.ArgAccessType: ArgumentAccessInfo::AccessType::Read, .AccessRanges: {*TypeAccessRange}};
708 }
709 } else if (auto *MemSet = dyn_cast<MemSetInst>(Val: I)) {
710 if (!MemSet->isVolatile()) {
711 ConstantRangeList AccessRanges;
712 if (auto AccessRange =
713 GetConstantIntRange(MemSet->getLength(), ArgUse.Offset))
714 AccessRanges.insert(NewRange: *AccessRange);
715 return {.ArgAccessType: ArgumentAccessInfo::AccessType::Write, .AccessRanges: AccessRanges};
716 }
717 } else if (auto *MTI = dyn_cast<MemTransferInst>(Val: I)) {
718 if (!MTI->isVolatile()) {
719 if (&MTI->getOperandUse(i: 0) == ArgUse.U) {
720 ConstantRangeList AccessRanges;
721 if (auto AccessRange =
722 GetConstantIntRange(MTI->getLength(), ArgUse.Offset))
723 AccessRanges.insert(NewRange: *AccessRange);
724 return {.ArgAccessType: ArgumentAccessInfo::AccessType::Write, .AccessRanges: AccessRanges};
725 } else if (&MTI->getOperandUse(i: 1) == ArgUse.U) {
726 if (auto AccessRange =
727 GetConstantIntRange(MTI->getLength(), ArgUse.Offset))
728 return {.ArgAccessType: ArgumentAccessInfo::AccessType::Read, .AccessRanges: {*AccessRange}};
729 }
730 }
731 } else if (auto *CB = dyn_cast<CallBase>(Val: I)) {
732 if (CB->isArgOperand(U: ArgUse.U) &&
733 !CB->isByValArgument(ArgNo: CB->getArgOperandNo(U: ArgUse.U))) {
734 unsigned ArgNo = CB->getArgOperandNo(U: ArgUse.U);
735 bool IsInitialize = CB->paramHasAttr(ArgNo, Kind: Attribute::Initializes);
736 if (IsInitialize && ArgUse.Offset) {
737 // Argument is a Write when parameter is writeonly/readnone
738 // and nocapture. Otherwise, it's a WriteWithSideEffect.
739 auto Access = CB->onlyWritesMemory(OpNo: ArgNo) && CB->doesNotCapture(OpNo: ArgNo)
740 ? ArgumentAccessInfo::AccessType::Write
741 : ArgumentAccessInfo::AccessType::WriteWithSideEffect;
742 ConstantRangeList AccessRanges;
743 Attribute Attr = CB->getParamAttr(ArgNo, Kind: Attribute::Initializes);
744 ConstantRangeList CBCRL = Attr.getValueAsConstantRangeList();
745 for (ConstantRange &CR : CBCRL)
746 AccessRanges.insert(NewRange: ConstantRange(CR.getLower() + *ArgUse.Offset,
747 CR.getUpper() + *ArgUse.Offset));
748 return {.ArgAccessType: Access, .AccessRanges: AccessRanges};
749 }
750 }
751 }
752 // Other unrecognized instructions are considered as unknown.
753 return {.ArgAccessType: ArgumentAccessInfo::AccessType::Unknown, .AccessRanges: {}};
754}
755
756// Collect the uses of argument "A" in "F".
757ArgumentUsesSummary collectArgumentUsesPerBlock(Argument &A, Function &F) {
758 auto &DL = F.getDataLayout();
759 unsigned PointerSize =
760 DL.getIndexSizeInBits(AS: A.getType()->getPointerAddressSpace());
761 ArgumentUsesSummary Result;
762
763 BasicBlock &EntryBB = F.getEntryBlock();
764 SmallVector<ArgumentUse, 4> Worklist;
765 for (Use &U : A.uses())
766 Worklist.push_back(Elt: {.U: &U, .Offset: 0});
767
768 // Update "UsesPerBlock" with the block of "I" as key and "Info" as value.
769 // Return true if the block of "I" has write accesses after updating.
770 auto UpdateUseInfo = [&Result](Instruction *I, ArgumentAccessInfo Info) {
771 auto *BB = I->getParent();
772 auto &BBInfo = Result.UsesPerBlock[BB];
773 auto [It, Inserted] = BBInfo.Insts.try_emplace(Key: I);
774 auto &IInfo = It->second;
775
776 // Instructions that have more than one use of the argument are considered
777 // as clobbers.
778 if (!Inserted) {
779 IInfo = {.ArgAccessType: ArgumentAccessInfo::AccessType::Unknown, .AccessRanges: {}};
780 BBInfo.HasUnknownAccess = true;
781 return false;
782 }
783
784 IInfo = std::move(Info);
785 BBInfo.HasUnknownAccess |=
786 IInfo.ArgAccessType == ArgumentAccessInfo::AccessType::Unknown;
787 bool InfoHasWrites =
788 (IInfo.ArgAccessType == ArgumentAccessInfo::AccessType::Write ||
789 IInfo.ArgAccessType ==
790 ArgumentAccessInfo::AccessType::WriteWithSideEffect) &&
791 !IInfo.AccessRanges.empty();
792 BBInfo.HasWrites |= InfoHasWrites;
793 return InfoHasWrites;
794 };
795
796 // No need for a visited set because we don't look through phis, so there are
797 // no cycles.
798 while (!Worklist.empty()) {
799 ArgumentUse ArgUse = Worklist.pop_back_val();
800 User *U = ArgUse.U->getUser();
801 // Add GEP uses to worklist.
802 // If the GEP is not a constant GEP, set the ArgumentUse::Offset to nullopt.
803 if (auto *GEP = dyn_cast<GEPOperator>(Val: U)) {
804 std::optional<int64_t> NewOffset = std::nullopt;
805 if (ArgUse.Offset) {
806 APInt Offset(PointerSize, 0);
807 if (GEP->accumulateConstantOffset(DL, Offset))
808 NewOffset = *ArgUse.Offset + Offset.getSExtValue();
809 }
810 for (Use &U : GEP->uses())
811 Worklist.push_back(Elt: {.U: &U, .Offset: NewOffset});
812 continue;
813 }
814
815 auto *I = cast<Instruction>(Val: U);
816 bool HasWrite = UpdateUseInfo(I, getArgumentAccessInfo(I, ArgUse, DL));
817
818 Result.HasAnyWrite |= HasWrite;
819
820 if (HasWrite && I->getParent() != &EntryBB)
821 Result.HasWriteOutsideEntryBB = true;
822 }
823 return Result;
824}
825
826} // end anonymous namespace
827
828namespace llvm {
829
830template <> struct GraphTraits<ArgumentGraphNode *> {
831 using NodeRef = ArgumentGraphNode *;
832 using ChildIteratorType = SmallVectorImpl<ArgumentGraphNode *>::iterator;
833
834 static NodeRef getEntryNode(NodeRef A) { return A; }
835 static ChildIteratorType child_begin(NodeRef N) { return N->Uses.begin(); }
836 static ChildIteratorType child_end(NodeRef N) { return N->Uses.end(); }
837};
838
839template <>
840struct GraphTraits<ArgumentGraph *> : public GraphTraits<ArgumentGraphNode *> {
841 static NodeRef getEntryNode(ArgumentGraph *AG) { return AG->getEntryNode(); }
842
843 static ChildIteratorType nodes_begin(ArgumentGraph *AG) {
844 return AG->begin();
845 }
846
847 static ChildIteratorType nodes_end(ArgumentGraph *AG) { return AG->end(); }
848};
849
850struct ArgAccessProperties {
851 bool IsRead = false;
852 bool IsWrite = false;
853 bool IsFree = false;
854
855 static ArgAccessProperties all() { return {.IsRead: true, .IsWrite: true, .IsFree: true}; }
856
857 bool hasAll() const { return IsRead && IsWrite && IsFree; }
858
859 ArgAccessProperties &operator|=(const ArgAccessProperties &Other) {
860 IsRead |= Other.IsRead;
861 IsWrite |= Other.IsWrite;
862 IsFree |= Other.IsFree;
863 return *this;
864 }
865};
866
867} // end namespace llvm
868
869/// Returns Attribute::None, Attribute::ReadOnly or Attribute::ReadNone.
870static ArgAccessProperties
871determinePointerAccessAttrs(Argument *A,
872 const SmallPtrSet<Argument *, 8> &SCCNodes) {
873 SmallVector<Use *, 32> Worklist;
874 SmallPtrSet<Use *, 32> Visited;
875
876 // inalloca arguments are always clobbered by the call.
877 if (A->hasInAllocaAttr() || A->hasPreallocatedAttr())
878 return ArgAccessProperties::all();
879
880 ArgAccessProperties Props;
881
882 for (Use &U : A->uses()) {
883 Visited.insert(Ptr: &U);
884 Worklist.push_back(Elt: &U);
885 }
886
887 while (!Worklist.empty()) {
888 if (Props.hasAll())
889 // No point in searching further..
890 return Props;
891
892 Use *U = Worklist.pop_back_val();
893 Instruction *I = cast<Instruction>(Val: U->getUser());
894 if (isa<ReturnInst>(Val: I))
895 continue;
896
897 UseCaptureInfo Info = DetermineUseCaptureKind(U: *U, Base: A);
898
899 // FIXME: This should really be part of CaptureTracking, but keep it here
900 // for now due to interference with isEscapeSource().
901 if (auto *CB = dyn_cast<CallBase>(Val: I))
902 if (CB->onlyReadsMemory())
903 Info.UseCC &= CaptureComponents::Address;
904
905 if (capturesAnyProvenance(CC: Info.UseCC)) {
906 // Handle indirect access via captured provenance.
907 if (!capturesReadProvenanceOnly(CC: Info.UseCC))
908 return ArgAccessProperties::all();
909 Props.IsRead = true;
910 }
911
912 if (capturesAnyProvenance(CC: Info.ResultCC)) {
913 for (Use &UU : I->uses())
914 if (Visited.insert(Ptr: &UU).second)
915 Worklist.push_back(Elt: &UU);
916 }
917
918 if (auto *CB = dyn_cast<CallBase>(Val: I)) {
919 if (CB->isCallee(U)) {
920 Props.IsRead = true;
921 continue;
922 }
923
924 // Given we've explicitly handled the callee operand above, what's left
925 // must be a data operand (e.g. argument or operand bundle)
926 const unsigned UseIndex = CB->getDataOperandNo(U);
927
928 ModRefInfo ArgMR =
929 CB->getMemoryEffects().getModRef(Loc: IRMemLocation::ArgMem);
930 if (isNoModRef(MRI: ArgMR))
931 continue;
932
933 if (Function *F = CB->getCalledFunction())
934 if (CB->isArgOperand(U) && UseIndex < F->arg_size() &&
935 SCCNodes.count(Ptr: F->getArg(i: UseIndex)))
936 // This is an argument which is part of the speculative SCC. Note
937 // that only operands corresponding to formal arguments of the callee
938 // can participate in the speculation.
939 continue;
940
941 // The accessors used on call site here do the right thing for calls and
942 // invokes with operand bundles.
943 if (isRefSet(MRI: ArgMR) && !CB->onlyWritesMemory(OpNo: UseIndex))
944 Props.IsRead = true;
945 if (isModSet(MRI: ArgMR) && !CB->onlyReadsMemory(OpNo: UseIndex)) {
946 Props.IsWrite = true;
947 if (CB->isArgOperand(U) && !CB->hasFnAttr(Kind: Attribute::NoFree) &&
948 !CB->paramHasAttr(ArgNo: UseIndex, Kind: Attribute::NoFree) &&
949 !CB->paramHasAttr(ArgNo: UseIndex, Kind: Attribute::NoFreeObj))
950 Props.IsFree = true;
951 }
952 } else {
953 // Ignore value operand for stores.
954 if (isa<StoreInst>(Val: I) &&
955 StoreInst::getPointerOperandIndex() != U->getOperandNo())
956 continue;
957
958 Props.IsRead |= I->mayReadFromMemory();
959 Props.IsWrite |= I->mayWriteToMemory();
960 }
961 }
962
963 return Props;
964}
965
966/// Deduce returned attributes for the SCC.
967static void addArgumentReturnedAttrs(const SCCNodeSet &SCCNodes,
968 SmallPtrSet<Function *, 8> &Changed) {
969 // Check each function in turn, determining if an argument is always returned.
970 for (Function *F : SCCNodes) {
971 // We can infer and propagate function attributes only when we know that the
972 // definition we'll get at link time is *exactly* the definition we see now.
973 // For more details, see GlobalValue::mayBeDerefined.
974 if (!F->hasExactDefinition())
975 continue;
976
977 if (F->getReturnType()->isVoidTy())
978 continue;
979
980 // There is nothing to do if an argument is already marked as 'returned'.
981 if (F->getAttributes().hasAttrSomewhere(Kind: Attribute::Returned))
982 continue;
983
984 auto FindRetArg = [&]() -> Argument * {
985 Argument *RetArg = nullptr;
986 for (BasicBlock &BB : *F)
987 if (auto *Ret = dyn_cast<ReturnInst>(Val: BB.getTerminator())) {
988 // Note that stripPointerCasts should look through functions with
989 // returned arguments.
990 auto *RetVal =
991 dyn_cast<Argument>(Val: Ret->getReturnValue()->stripPointerCasts());
992 if (!RetVal || RetVal->getType() != F->getReturnType())
993 return nullptr;
994
995 if (!RetArg)
996 RetArg = RetVal;
997 else if (RetArg != RetVal)
998 return nullptr;
999 }
1000
1001 return RetArg;
1002 };
1003
1004 if (Argument *RetArg = FindRetArg()) {
1005 RetArg->addAttr(Kind: Attribute::Returned);
1006 ++NumReturned;
1007 Changed.insert(Ptr: F);
1008 }
1009 }
1010}
1011
1012/// If a callsite has arguments that are also arguments to the parent function,
1013/// try to propagate attributes from the callsite's arguments to the parent's
1014/// arguments. This may be important because inlining can cause information loss
1015/// when attribute knowledge disappears with the inlined call.
1016static bool addArgumentAttrsFromCallsites(const IPOOptions &Opts, Function &F) {
1017 if (!Opts.enable_poison_arg_attr_prop)
1018 return false;
1019
1020 bool Changed = false;
1021
1022 // For an argument attribute to transfer from a callsite to the parent, the
1023 // call must be guaranteed to execute every time the parent is called.
1024 // Conservatively, just check for calls in the entry block that are guaranteed
1025 // to execute.
1026 // TODO: This could be enhanced by testing if the callsite post-dominates the
1027 // entry block or by doing simple forward walks or backward walks to the
1028 // callsite.
1029 BasicBlock &Entry = F.getEntryBlock();
1030 for (Instruction &I : Entry) {
1031 if (auto *CB = dyn_cast<CallBase>(Val: &I)) {
1032 if (auto *CalledFunc = CB->getCalledFunction()) {
1033 for (auto &CSArg : CalledFunc->args()) {
1034 unsigned ArgNo = CSArg.getArgNo();
1035 auto *FArg = dyn_cast<Argument>(Val: CB->getArgOperand(i: ArgNo));
1036 if (!FArg)
1037 continue;
1038
1039 if (CSArg.hasNonNullAttr(/*AllowUndefOrPoison=*/false)) {
1040 // If the non-null callsite argument operand is an argument to 'F'
1041 // (the caller) and the call is guaranteed to execute, then the
1042 // value must be non-null throughout 'F'.
1043 if (!FArg->hasNonNullAttr()) {
1044 FArg->addAttr(Kind: Attribute::NonNull);
1045 Changed = true;
1046 }
1047 } else if (FPClassTest CSNoFPClass = CB->getParamNoFPClass(i: ArgNo);
1048 CSNoFPClass != fcNone &&
1049 CB->paramHasAttr(ArgNo, Kind: Attribute::NoUndef)) {
1050 FPClassTest ArgNoFPClass = FArg->getNoFPClass();
1051
1052 if ((CSNoFPClass | ArgNoFPClass) != ArgNoFPClass) {
1053 FArg->addAttr(Attr: Attribute::getWithNoFPClass(
1054 Context&: FArg->getContext(), Mask: CSNoFPClass | ArgNoFPClass));
1055 Changed = true;
1056 }
1057 }
1058 }
1059 }
1060 }
1061 if (!isGuaranteedToTransferExecutionToSuccessor(I: &I))
1062 break;
1063 }
1064
1065 return Changed;
1066}
1067
1068static bool addAccessAttrs(Argument *A, ArgAccessProperties Props) {
1069 assert(A && "Argument must not be null.");
1070
1071 bool Changed = false;
1072 if (!Props.IsFree && !A->hasAttribute(Kind: Attribute::NoFree) &&
1073 !A->hasAttribute(Kind: Attribute::NoFreeObj)) {
1074 ++NumNoFreeArg;
1075 A->addAttr(Kind: Attribute::NoFree);
1076 Changed = true;
1077 }
1078
1079 if (Props.IsRead && Props.IsWrite)
1080 return Changed;
1081
1082 Attribute::AttrKind Attr;
1083 if (Props.IsRead)
1084 Attr = Attribute::ReadOnly;
1085 else if (Props.IsWrite)
1086 Attr = Attribute::WriteOnly;
1087 else
1088 Attr = Attribute::ReadNone;
1089
1090 // If the argument already has the attribute, nothing needs to be done.
1091 if (A->hasAttribute(Kind: Attr))
1092 return false;
1093
1094 // Otherwise, remove potentially conflicting attribute, add the new one,
1095 // and update statistics.
1096 A->removeAttr(Kind: Attribute::WriteOnly);
1097 A->removeAttr(Kind: Attribute::ReadOnly);
1098 A->removeAttr(Kind: Attribute::ReadNone);
1099 // Remove conflicting writable attribute.
1100 if (Attr == Attribute::ReadNone || Attr == Attribute::ReadOnly)
1101 A->removeAttr(Kind: Attribute::Writable);
1102 A->addAttr(Kind: Attr);
1103 if (Attr == Attribute::ReadOnly)
1104 ++NumReadOnlyArg;
1105 else if (Attr == Attribute::WriteOnly)
1106 ++NumWriteOnlyArg;
1107 else
1108 ++NumReadNoneArg;
1109 return true;
1110}
1111
1112/// Return true if a block without successors is reachable from \p EntryBB
1113/// without passing through a block that writes the argument. Nothing is
1114/// initialized on such a path.
1115static bool canExitWithoutWrites(const BasicBlock &EntryBB,
1116 const ArgumentUsesSummary &ArgumentUses) {
1117 const auto &UsesPerBlock = ArgumentUses.UsesPerBlock;
1118 for (auto It = df_begin(G: &EntryBB), End = df_end(G: &EntryBB); It != End;) {
1119 auto UPB = UsesPerBlock.find(Val: *It);
1120 if (UPB != UsesPerBlock.end() && UPB->second.HasWrites) {
1121 It.skipChildren();
1122 continue;
1123 }
1124 if (succ_empty(BB: *It))
1125 return true;
1126 ++It;
1127 }
1128 return false;
1129}
1130
1131static bool inferInitializes(Argument &A, Function &F) {
1132 auto ArgumentUses = collectArgumentUsesPerBlock(A, F);
1133 // No write anywhere in the function, bail.
1134 if (!ArgumentUses.HasAnyWrite)
1135 return false;
1136
1137 auto &UsesPerBlock = ArgumentUses.UsesPerBlock;
1138 BasicBlock &EntryBB = F.getEntryBlock();
1139 // A map to store the argument ranges initialized by a BasicBlock (including
1140 // its successors).
1141 DenseMap<const BasicBlock *, ConstantRangeList> Initialized;
1142 // Visit the successors of "BB" block and the instructions in BB (post-order)
1143 // to get the argument ranges initialized by "BB" (including its successors).
1144 // The result will be cached in "Initialized".
1145 auto VisitBlock = [&](const BasicBlock *BB) -> ConstantRangeList {
1146 auto UPB = UsesPerBlock.find(Val: BB);
1147 ConstantRangeList CRL;
1148
1149 // Start with intersection of successors.
1150 // If this block has any clobbering use, we're going to clear out the
1151 // ranges at some point in this block anyway, so don't bother looking at
1152 // successors.
1153 if (UPB == UsesPerBlock.end() || !UPB->second.HasUnknownAccess) {
1154 bool HasAddedSuccessor = false;
1155 for (auto *Succ : successors(BB)) {
1156 if (auto SuccI = Initialized.find(Val: Succ); SuccI != Initialized.end()) {
1157 if (HasAddedSuccessor) {
1158 CRL = CRL.intersectWith(CRL: SuccI->second);
1159 } else {
1160 CRL = SuccI->second;
1161 HasAddedSuccessor = true;
1162 }
1163 } else {
1164 CRL = ConstantRangeList();
1165 break;
1166 }
1167 }
1168 }
1169
1170 if (UPB != UsesPerBlock.end()) {
1171 // Sort uses in this block by instruction order.
1172 SmallVector<std::pair<Instruction *, ArgumentAccessInfo>, 2> Insts;
1173 append_range(C&: Insts, R&: UPB->second.Insts);
1174 sort(C&: Insts, Comp: [](std::pair<Instruction *, ArgumentAccessInfo> &LHS,
1175 std::pair<Instruction *, ArgumentAccessInfo> &RHS) {
1176 return LHS.first->comesBefore(Other: RHS.first);
1177 });
1178
1179 // From the end of the block to the beginning of the block, set
1180 // initializes ranges.
1181 for (auto &[_, Info] : reverse(C&: Insts)) {
1182 if (Info.ArgAccessType == ArgumentAccessInfo::AccessType::Unknown ||
1183 Info.ArgAccessType ==
1184 ArgumentAccessInfo::AccessType::WriteWithSideEffect)
1185 CRL = ConstantRangeList();
1186 if (!Info.AccessRanges.empty()) {
1187 if (Info.ArgAccessType == ArgumentAccessInfo::AccessType::Write ||
1188 Info.ArgAccessType ==
1189 ArgumentAccessInfo::AccessType::WriteWithSideEffect) {
1190 CRL = CRL.unionWith(CRL: Info.AccessRanges);
1191 } else {
1192 assert(Info.ArgAccessType == ArgumentAccessInfo::AccessType::Read);
1193 for (const auto &ReadRange : Info.AccessRanges)
1194 CRL.subtract(SubRange: ReadRange);
1195 }
1196 }
1197 }
1198 }
1199 return CRL;
1200 };
1201
1202 ConstantRangeList EntryCRL;
1203 // If all write instructions are in the EntryBB, or if the EntryBB has
1204 // a clobbering use, we only need to look at EntryBB.
1205 bool OnlyScanEntryBlock = !ArgumentUses.HasWriteOutsideEntryBB;
1206 if (!OnlyScanEntryBlock)
1207 if (auto EntryUPB = UsesPerBlock.find(Val: &EntryBB);
1208 EntryUPB != UsesPerBlock.end())
1209 OnlyScanEntryBlock = EntryUPB->second.HasUnknownAccess;
1210 if (OnlyScanEntryBlock) {
1211 EntryCRL = VisitBlock(&EntryBB);
1212 if (EntryCRL.empty())
1213 return false;
1214 } else {
1215 // Computing the initialized ranges of every block is expensive, and they
1216 // are empty for the entry block if a path from it avoids all writes.
1217 if (canExitWithoutWrites(EntryBB, ArgumentUses))
1218 return false;
1219
1220 // Now we have to go through CFG to get the initialized argument ranges
1221 // across blocks. With dominance and post-dominance, the initialized ranges
1222 // by a block include both accesses inside this block and accesses in its
1223 // (transitive) successors. So visit successors before predecessors with a
1224 // post-order walk of the blocks and memorize the results in "Initialized".
1225 for (const BasicBlock *BB : post_order(G: &F)) {
1226 ConstantRangeList CRL = VisitBlock(BB);
1227 if (!CRL.empty())
1228 Initialized[BB] = CRL;
1229 }
1230
1231 auto EntryCRLI = Initialized.find(Val: &EntryBB);
1232 if (EntryCRLI == Initialized.end())
1233 return false;
1234
1235 EntryCRL = EntryCRLI->second;
1236 }
1237
1238 assert(!EntryCRL.empty() &&
1239 "should have bailed already if EntryCRL is empty");
1240
1241 if (A.hasAttribute(Kind: Attribute::Initializes)) {
1242 ConstantRangeList PreviousCRL =
1243 A.getAttribute(Kind: Attribute::Initializes).getValueAsConstantRangeList();
1244 if (PreviousCRL == EntryCRL)
1245 return false;
1246 EntryCRL = EntryCRL.unionWith(CRL: PreviousCRL);
1247 }
1248
1249 A.addAttr(Attr: Attribute::get(Context&: A.getContext(), Kind: Attribute::Initializes,
1250 Val: EntryCRL.rangesRef()));
1251
1252 return true;
1253}
1254
1255/// Deduce nocapture attributes for the SCC.
1256static void addArgumentAttrs(const IPOOptions &Opts, const SCCNodeSet &SCCNodes,
1257 SmallPtrSet<Function *, 8> &Changed,
1258 bool SkipInitializes) {
1259 ArgumentGraph AG;
1260
1261 auto DetermineAccessAttrsForSingleton = [](Argument *A) {
1262 SmallPtrSet<Argument *, 8> Self;
1263 Self.insert(Ptr: A);
1264 return addAccessAttrs(A, Props: determinePointerAccessAttrs(A, SCCNodes: Self));
1265 };
1266
1267 // Check each function in turn, determining which pointer arguments are not
1268 // captured.
1269 for (Function *F : SCCNodes) {
1270 // We can infer and propagate function attributes only when we know that the
1271 // definition we'll get at link time is *exactly* the definition we see now.
1272 // For more details, see GlobalValue::mayBeDerefined.
1273 if (!F->hasExactDefinition())
1274 continue;
1275
1276 if (addArgumentAttrsFromCallsites(Opts, F&: *F))
1277 Changed.insert(Ptr: F);
1278
1279 // Functions that are readonly (or readnone) and nounwind and don't return
1280 // a value can't capture arguments. Don't analyze them.
1281 if (F->onlyReadsMemory() && F->doesNotThrow() && F->willReturn() &&
1282 F->getReturnType()->isVoidTy()) {
1283 for (Argument &A : F->args()) {
1284 if (A.getType()->isPointerTy() && !A.hasNoCaptureAttr()) {
1285 A.addAttr(Attr: Attribute::getWithCaptureInfo(Context&: A.getContext(),
1286 CI: CaptureInfo::none()));
1287 ++NumCapturesNone;
1288 Changed.insert(Ptr: F);
1289 }
1290 }
1291 continue;
1292 }
1293
1294 for (Argument &A : F->args()) {
1295 if (!A.getType()->isPointerTy())
1296 continue;
1297 bool HasNonLocalUses = false;
1298 CaptureInfo OrigCI = A.getAttributes().getCaptureInfo();
1299 if (!capturesNothing(CC: OrigCI)) {
1300 ArgumentUsesTracker Tracker(SCCNodes);
1301 PointerMayBeCaptured(V: &A, Tracker: &Tracker);
1302 CaptureInfo NewCI = Tracker.CI & OrigCI;
1303 if (NewCI != OrigCI) {
1304 if (Tracker.Uses.empty()) {
1305 // If the information is complete, add the attribute now.
1306 A.addAttr(Attr: Attribute::getWithCaptureInfo(Context&: A.getContext(), CI: NewCI));
1307 addCapturesStat(CI: NewCI);
1308 Changed.insert(Ptr: F);
1309 } else {
1310 // If it's not trivially captured and not trivially not captured,
1311 // then it must be calling into another function in our SCC. Save
1312 // its particulars for Argument-SCC analysis later.
1313 ArgumentGraphNode *Node = AG[&A];
1314 Node->CC = CaptureComponents(NewCI);
1315 for (Argument *Use : Tracker.Uses) {
1316 Node->Uses.push_back(Elt: AG[Use]);
1317 if (Use != &A)
1318 HasNonLocalUses = true;
1319 }
1320 }
1321 }
1322 // Otherwise, it's captured. Don't bother doing SCC analysis on it.
1323 }
1324 if (!HasNonLocalUses && !A.onlyReadsMemory()) {
1325 // Can we determine that it's readonly/readnone/writeonly without doing
1326 // an SCC? Note that we don't allow any calls at all here, or else our
1327 // result will be dependent on the iteration order through the
1328 // functions in the SCC.
1329 if (DetermineAccessAttrsForSingleton(&A))
1330 Changed.insert(Ptr: F);
1331 }
1332 if (!SkipInitializes && !A.onlyReadsMemory()) {
1333 if (inferInitializes(A, F&: *F))
1334 Changed.insert(Ptr: F);
1335 }
1336 }
1337 }
1338
1339 // The graph we've collected is partial because we stopped scanning for
1340 // argument uses once we solved the argument trivially. These partial nodes
1341 // show up as ArgumentGraphNode objects with an empty Uses list, and for
1342 // these nodes the final decision about whether they capture has already been
1343 // made. If the definition doesn't have a 'nocapture' attribute by now, it
1344 // captures.
1345
1346 for (scc_iterator<ArgumentGraph *> I = scc_begin(G: &AG); !I.isAtEnd(); ++I) {
1347 const std::vector<ArgumentGraphNode *> &ArgumentSCC = *I;
1348 if (ArgumentSCC.size() == 1) {
1349 if (!ArgumentSCC[0]->Definition)
1350 continue; // synthetic root node
1351
1352 // eg. "void f(int* x) { if (...) f(x); }"
1353 if (ArgumentSCC[0]->Uses.size() == 1 &&
1354 ArgumentSCC[0]->Uses[0] == ArgumentSCC[0]) {
1355 Argument *A = ArgumentSCC[0]->Definition;
1356 CaptureInfo OrigCI = A->getAttributes().getCaptureInfo();
1357 CaptureInfo NewCI = CaptureInfo(ArgumentSCC[0]->CC) & OrigCI;
1358 if (NewCI != OrigCI) {
1359 A->addAttr(Attr: Attribute::getWithCaptureInfo(Context&: A->getContext(), CI: NewCI));
1360 addCapturesStat(CI: NewCI);
1361 Changed.insert(Ptr: A->getParent());
1362 }
1363
1364 // Infer the access attributes given the new captures one
1365 if (DetermineAccessAttrsForSingleton(A))
1366 Changed.insert(Ptr: A->getParent());
1367 }
1368 continue;
1369 }
1370
1371 SmallPtrSet<Argument *, 8> ArgumentSCCNodes;
1372 // Fill ArgumentSCCNodes with the elements of the ArgumentSCC. Used for
1373 // quickly looking up whether a given Argument is in this ArgumentSCC.
1374 for (ArgumentGraphNode *I : ArgumentSCC) {
1375 ArgumentSCCNodes.insert(Ptr: I->Definition);
1376 }
1377
1378 // At the SCC level, only track merged CaptureComponents. We're not
1379 // currently prepared to handle propagation of return-only captures across
1380 // the SCC.
1381 CaptureComponents CC = CaptureComponents::None;
1382 for (ArgumentGraphNode *N : ArgumentSCC) {
1383 for (ArgumentGraphNode *Use : N->Uses) {
1384 Argument *A = Use->Definition;
1385 if (ArgumentSCCNodes.count(Ptr: A))
1386 CC |= Use->CC;
1387 else
1388 CC |= CaptureComponents(A->getAttributes().getCaptureInfo());
1389 }
1390 if (capturesAll(CC))
1391 break;
1392 }
1393
1394 if (!capturesAll(CC)) {
1395 for (ArgumentGraphNode *N : ArgumentSCC) {
1396 Argument *A = N->Definition;
1397 CaptureInfo OrigCI = A->getAttributes().getCaptureInfo();
1398 CaptureInfo NewCI = CaptureInfo(N->CC | CC) & OrigCI;
1399 if (NewCI != OrigCI) {
1400 A->addAttr(Attr: Attribute::getWithCaptureInfo(Context&: A->getContext(), CI: NewCI));
1401 addCapturesStat(CI: NewCI);
1402 Changed.insert(Ptr: A->getParent());
1403 }
1404 }
1405 }
1406
1407 if (capturesAnyProvenance(CC)) {
1408 // As the pointer provenance may be captured, determine the pointer
1409 // attributes looking at each argument individually.
1410 for (ArgumentGraphNode *N : ArgumentSCC) {
1411 if (DetermineAccessAttrsForSingleton(N->Definition))
1412 Changed.insert(Ptr: N->Definition->getParent());
1413 }
1414 continue;
1415 }
1416
1417 // We also want to compute readonly/readnone/writeonly. With a small number
1418 // of false negatives, we can assume that any pointer which is captured
1419 // isn't going to be provably readonly or readnone, since by definition
1420 // we can't analyze all uses of a captured pointer.
1421 //
1422 // The false negatives happen when the pointer is captured by a function
1423 // that promises readonly/readnone behaviour on the pointer, then the
1424 // pointer's lifetime ends before anything that writes to arbitrary memory.
1425 // Also, a readonly/readnone pointer may be returned, but returning a
1426 // pointer is capturing it.
1427
1428 ArgAccessProperties Props;
1429 for (ArgumentGraphNode *N : ArgumentSCC) {
1430 Argument *A = N->Definition;
1431 Props |= determinePointerAccessAttrs(A, SCCNodes: ArgumentSCCNodes);
1432 if (Props.hasAll())
1433 break;
1434 }
1435
1436 if (!Props.hasAll()) {
1437 for (ArgumentGraphNode *N : ArgumentSCC) {
1438 Argument *A = N->Definition;
1439 if (addAccessAttrs(A, Props))
1440 Changed.insert(Ptr: A->getParent());
1441 }
1442 }
1443 }
1444}
1445
1446/// Tests whether a function is "malloc-like".
1447///
1448/// A function is "malloc-like" if it returns either null or a pointer that
1449/// doesn't alias any other pointer visible to the caller.
1450static bool isFunctionMallocLike(Function *F, const SCCNodeSet &SCCNodes) {
1451 SmallSetVector<Value *, 8> FlowsToReturn;
1452 for (BasicBlock &BB : *F)
1453 if (ReturnInst *Ret = dyn_cast<ReturnInst>(Val: BB.getTerminator()))
1454 FlowsToReturn.insert(X: Ret->getReturnValue());
1455
1456 for (unsigned i = 0; i != FlowsToReturn.size(); ++i) {
1457 Value *RetVal = FlowsToReturn[i];
1458
1459 if (Constant *C = dyn_cast<Constant>(Val: RetVal)) {
1460 if (!C->isNullValue() && !isa<UndefValue>(Val: C))
1461 return false;
1462
1463 continue;
1464 }
1465
1466 if (isa<Argument>(Val: RetVal))
1467 return false;
1468
1469 if (Instruction *RVI = dyn_cast<Instruction>(Val: RetVal))
1470 switch (RVI->getOpcode()) {
1471 // Extend the analysis by looking upwards.
1472 case Instruction::BitCast:
1473 case Instruction::GetElementPtr:
1474 case Instruction::AddrSpaceCast:
1475 FlowsToReturn.insert(X: RVI->getOperand(i: 0));
1476 continue;
1477 case Instruction::Select: {
1478 SelectInst *SI = cast<SelectInst>(Val: RVI);
1479 FlowsToReturn.insert(X: SI->getTrueValue());
1480 FlowsToReturn.insert(X: SI->getFalseValue());
1481 continue;
1482 }
1483 case Instruction::PHI: {
1484 PHINode *PN = cast<PHINode>(Val: RVI);
1485 FlowsToReturn.insert_range(R: PN->incoming_values());
1486 continue;
1487 }
1488
1489 // Check whether the pointer came from an allocation.
1490 case Instruction::Alloca:
1491 break;
1492 case Instruction::Call:
1493 case Instruction::Invoke: {
1494 CallBase &CB = cast<CallBase>(Val&: *RVI);
1495 if (CB.hasRetAttr(Kind: Attribute::NoAlias))
1496 break;
1497 if (CB.getCalledFunction() && SCCNodes.count(key: CB.getCalledFunction()))
1498 break;
1499 [[fallthrough]];
1500 }
1501 default:
1502 return false; // Did not come from an allocation.
1503 }
1504
1505 // Only capturing the provenance of the result prevents it from being
1506 // noalias.
1507 if (capturesAnything(
1508 CC: PointerMayBeCaptured(V: RetVal, Mask: CaptureComponents::Provenance)
1509 .WithoutRet))
1510 return false;
1511 }
1512
1513 return true;
1514}
1515
1516/// Deduce noalias attributes for the SCC.
1517static void addNoAliasAttrs(const SCCNodeSet &SCCNodes,
1518 SmallPtrSet<Function *, 8> &Changed) {
1519 // Check each function in turn, determining which functions return noalias
1520 // pointers.
1521 for (Function *F : SCCNodes) {
1522 // Already noalias.
1523 if (F->returnDoesNotAlias())
1524 continue;
1525
1526 // We can infer and propagate function attributes only when we know that the
1527 // definition we'll get at link time is *exactly* the definition we see now.
1528 // For more details, see GlobalValue::mayBeDerefined.
1529 if (!F->hasExactDefinition())
1530 return;
1531
1532 // We annotate noalias return values, which are only applicable to
1533 // pointer types.
1534 if (!F->getReturnType()->isPointerTy())
1535 continue;
1536
1537 if (!isFunctionMallocLike(F, SCCNodes))
1538 return;
1539 }
1540
1541 for (Function *F : SCCNodes) {
1542 if (F->returnDoesNotAlias() ||
1543 !F->getReturnType()->isPointerTy())
1544 continue;
1545
1546 F->setReturnDoesNotAlias();
1547 ++NumNoAlias;
1548 Changed.insert(Ptr: F);
1549 }
1550}
1551
1552/// Tests whether this function is known to not return null.
1553///
1554/// Requires that the function returns a pointer.
1555///
1556/// Returns true if it believes the function will not return a null, and sets
1557/// \p Speculative based on whether the returned conclusion is a speculative
1558/// conclusion due to SCC calls.
1559static bool isReturnNonNull(Function *F, const SCCNodeSet &SCCNodes,
1560 bool &Speculative) {
1561 assert(F->getReturnType()->isPointerTy() &&
1562 "nonnull only meaningful on pointer types");
1563 Speculative = false;
1564
1565 SmallSetVector<Value *, 8> FlowsToReturn;
1566 for (BasicBlock &BB : *F)
1567 if (auto *Ret = dyn_cast<ReturnInst>(Val: BB.getTerminator()))
1568 FlowsToReturn.insert(X: Ret->getReturnValue());
1569
1570 auto &DL = F->getDataLayout();
1571
1572 for (unsigned i = 0; i != FlowsToReturn.size(); ++i) {
1573 Value *RetVal = FlowsToReturn[i];
1574
1575 // If this value is locally known to be non-null, we're good
1576 if (isKnownNonZero(V: RetVal, Q: DL))
1577 continue;
1578
1579 // Otherwise, we need to look upwards since we can't make any local
1580 // conclusions.
1581 Instruction *RVI = dyn_cast<Instruction>(Val: RetVal);
1582 if (!RVI)
1583 return false;
1584 switch (RVI->getOpcode()) {
1585 // Extend the analysis by looking upwards.
1586 case Instruction::BitCast:
1587 case Instruction::AddrSpaceCast:
1588 FlowsToReturn.insert(X: RVI->getOperand(i: 0));
1589 continue;
1590 case Instruction::GetElementPtr:
1591 if (cast<GEPOperator>(Val: RVI)->isInBounds()) {
1592 FlowsToReturn.insert(X: RVI->getOperand(i: 0));
1593 continue;
1594 }
1595 return false;
1596 case Instruction::Select: {
1597 SelectInst *SI = cast<SelectInst>(Val: RVI);
1598 FlowsToReturn.insert(X: SI->getTrueValue());
1599 FlowsToReturn.insert(X: SI->getFalseValue());
1600 continue;
1601 }
1602 case Instruction::PHI: {
1603 PHINode *PN = cast<PHINode>(Val: RVI);
1604 for (int i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
1605 FlowsToReturn.insert(X: PN->getIncomingValue(i));
1606 continue;
1607 }
1608 case Instruction::Call:
1609 case Instruction::Invoke: {
1610 CallBase &CB = cast<CallBase>(Val&: *RVI);
1611 Function *Callee = CB.getCalledFunction();
1612 // A call to a node within the SCC is assumed to return null until
1613 // proven otherwise
1614 if (Callee && SCCNodes.count(key: Callee)) {
1615 Speculative = true;
1616 continue;
1617 }
1618 return false;
1619 }
1620 default:
1621 return false; // Unknown source, may be null
1622 };
1623 llvm_unreachable("should have either continued or returned");
1624 }
1625
1626 return true;
1627}
1628
1629/// Deduce nonnull attributes for the SCC.
1630static void addNonNullAttrs(const SCCNodeSet &SCCNodes,
1631 SmallPtrSet<Function *, 8> &Changed) {
1632 // Speculative that all functions in the SCC return only nonnull
1633 // pointers. We may refute this as we analyze functions.
1634 bool SCCReturnsNonNull = true;
1635
1636 // Check each function in turn, determining which functions return nonnull
1637 // pointers.
1638 for (Function *F : SCCNodes) {
1639 // Already nonnull.
1640 if (F->getAttributes().hasRetAttr(Kind: Attribute::NonNull))
1641 continue;
1642
1643 // We can infer and propagate function attributes only when we know that the
1644 // definition we'll get at link time is *exactly* the definition we see now.
1645 // For more details, see GlobalValue::mayBeDerefined.
1646 if (!F->hasExactDefinition())
1647 return;
1648
1649 // We annotate nonnull return values, which are only applicable to
1650 // pointer types.
1651 if (!F->getReturnType()->isPointerTy())
1652 continue;
1653
1654 bool Speculative = false;
1655 if (isReturnNonNull(F, SCCNodes, Speculative)) {
1656 if (!Speculative) {
1657 // Mark the function eagerly since we may discover a function
1658 // which prevents us from speculating about the entire SCC
1659 LLVM_DEBUG(dbgs() << "Eagerly marking " << F->getName()
1660 << " as nonnull\n");
1661 F->addRetAttr(Kind: Attribute::NonNull);
1662 ++NumNonNullReturn;
1663 Changed.insert(Ptr: F);
1664 }
1665 continue;
1666 }
1667 // At least one function returns something which could be null, can't
1668 // speculate any more.
1669 SCCReturnsNonNull = false;
1670 }
1671
1672 if (SCCReturnsNonNull) {
1673 for (Function *F : SCCNodes) {
1674 if (F->getAttributes().hasRetAttr(Kind: Attribute::NonNull) ||
1675 !F->getReturnType()->isPointerTy())
1676 continue;
1677
1678 LLVM_DEBUG(dbgs() << "SCC marking " << F->getName() << " as nonnull\n");
1679 F->addRetAttr(Kind: Attribute::NonNull);
1680 ++NumNonNullReturn;
1681 Changed.insert(Ptr: F);
1682 }
1683 }
1684}
1685
1686/// Deduce noundef attributes for the SCC.
1687static void addNoUndefAttrs(const SCCNodeSet &SCCNodes,
1688 SmallPtrSet<Function *, 8> &Changed) {
1689 // Check each function in turn, determining which functions return noundef
1690 // values.
1691 for (Function *F : SCCNodes) {
1692 // Already noundef.
1693 AttributeList Attrs = F->getAttributes();
1694 if (Attrs.hasRetAttr(Kind: Attribute::NoUndef))
1695 continue;
1696
1697 // We can infer and propagate function attributes only when we know that the
1698 // definition we'll get at link time is *exactly* the definition we see now.
1699 // For more details, see GlobalValue::mayBeDerefined.
1700 if (!F->hasExactDefinition())
1701 return;
1702
1703 // MemorySanitizer assumes that the definition and declaration of a
1704 // function will be consistent. A function with sanitize_memory attribute
1705 // should be skipped from inference.
1706 if (F->hasFnAttribute(Kind: Attribute::SanitizeMemory))
1707 continue;
1708
1709 if (F->getReturnType()->isVoidTy())
1710 continue;
1711
1712 const DataLayout &DL = F->getDataLayout();
1713 if (all_of(Range&: *F, P: [&](BasicBlock &BB) {
1714 if (auto *Ret = dyn_cast<ReturnInst>(Val: BB.getTerminator())) {
1715 // TODO: perform context-sensitive analysis?
1716 Value *RetVal = Ret->getReturnValue();
1717 if (!isGuaranteedNotToBeUndefOrPoison(V: RetVal))
1718 return false;
1719
1720 // We know the original return value is not poison now, but it
1721 // could still be converted to poison by another return attribute.
1722 // Try to explicitly re-prove the relevant attributes.
1723 if (Attrs.hasRetAttr(Kind: Attribute::NonNull) &&
1724 !isKnownNonZero(V: RetVal, Q: DL))
1725 return false;
1726
1727 if (MaybeAlign Align = Attrs.getRetAlignment())
1728 if (!RetVal->getType()->isPointerTy() ||
1729 RetVal->getPointerAlignment(DL) < *Align)
1730 return false;
1731
1732 Attribute Attr = Attrs.getRetAttr(Kind: Attribute::Range);
1733 if (Attr.isValid() &&
1734 !Attr.getRange().contains(
1735 CR: computeConstantRange(V: RetVal, /*ForSigned=*/false,
1736 SQ: SimplifyQuery(F->getDataLayout()))))
1737 return false;
1738
1739 FPClassTest AttrFPClass = Attrs.getRetNoFPClass();
1740 if (AttrFPClass != fcNone) {
1741 KnownFPClass ComputedFPClass = computeKnownFPClass(V: RetVal, DL);
1742 if (!ComputedFPClass.isKnownNever(Mask: AttrFPClass))
1743 return false;
1744 }
1745 }
1746 return true;
1747 })) {
1748 F->addRetAttr(Kind: Attribute::NoUndef);
1749 ++NumNoUndefReturn;
1750 Changed.insert(Ptr: F);
1751 }
1752 }
1753}
1754
1755namespace {
1756
1757/// Collects a set of attribute inference requests and performs them all in one
1758/// go on a single SCC Node. Inference involves scanning function bodies
1759/// looking for instructions that violate attribute assumptions.
1760/// As soon as all the bodies are fine we are free to set the attribute.
1761/// Customization of inference for individual attributes is performed by
1762/// providing a handful of predicates for each attribute.
1763class AttributeInferer {
1764public:
1765 /// Describes a request for inference of a single attribute.
1766 struct InferenceDescriptor {
1767
1768 /// Returns true if this function does not have to be handled.
1769 /// General intent for this predicate is to provide an optimization
1770 /// for functions that do not need this attribute inference at all
1771 /// (say, for functions that already have the attribute).
1772 std::function<bool(const Function &)> SkipFunction;
1773
1774 /// Returns true if this instruction violates attribute assumptions.
1775 std::function<bool(Instruction &)> InstrBreaksAttribute;
1776
1777 /// Sets the inferred attribute for this function.
1778 std::function<void(Function &)> SetAttribute;
1779
1780 /// Attribute we derive.
1781 Attribute::AttrKind AKind;
1782
1783 /// If true, only "exact" definitions can be used to infer this attribute.
1784 /// See GlobalValue::isDefinitionExact.
1785 bool RequiresExactDefinition;
1786
1787 InferenceDescriptor(Attribute::AttrKind AK,
1788 std::function<bool(const Function &)> SkipFunc,
1789 std::function<bool(Instruction &)> InstrScan,
1790 std::function<void(Function &)> SetAttr,
1791 bool ReqExactDef)
1792 : SkipFunction(SkipFunc), InstrBreaksAttribute(InstrScan),
1793 SetAttribute(SetAttr), AKind(AK),
1794 RequiresExactDefinition(ReqExactDef) {}
1795 };
1796
1797private:
1798 SmallVector<InferenceDescriptor, 4> InferenceDescriptors;
1799
1800public:
1801 void registerAttrInference(InferenceDescriptor AttrInference) {
1802 InferenceDescriptors.push_back(Elt: AttrInference);
1803 }
1804
1805 void run(const SCCNodeSet &SCCNodes, SmallPtrSet<Function *, 8> &Changed);
1806};
1807
1808/// Perform all the requested attribute inference actions according to the
1809/// attribute predicates stored before.
1810void AttributeInferer::run(const SCCNodeSet &SCCNodes,
1811 SmallPtrSet<Function *, 8> &Changed) {
1812 SmallVector<InferenceDescriptor, 4> InferInSCC = InferenceDescriptors;
1813 // Go through all the functions in SCC and check corresponding attribute
1814 // assumptions for each of them. Attributes that are invalid for this SCC
1815 // will be removed from InferInSCC.
1816 for (Function *F : SCCNodes) {
1817
1818 // No attributes whose assumptions are still valid - done.
1819 if (InferInSCC.empty())
1820 return;
1821
1822 // Check if our attributes ever need scanning/can be scanned.
1823 llvm::erase_if(C&: InferInSCC, P: [F](const InferenceDescriptor &ID) {
1824 if (ID.SkipFunction(*F))
1825 return false;
1826
1827 // Remove from further inference (invalidate) when visiting a function
1828 // that has no instructions to scan/has an unsuitable definition.
1829 return F->isDeclaration() ||
1830 (ID.RequiresExactDefinition && !F->hasExactDefinition());
1831 });
1832
1833 // For each attribute still in InferInSCC that doesn't explicitly skip F,
1834 // set up the F instructions scan to verify assumptions of the attribute.
1835 SmallVector<InferenceDescriptor, 4> InferInThisFunc;
1836 llvm::copy_if(
1837 Range&: InferInSCC, Out: std::back_inserter(x&: InferInThisFunc),
1838 P: [F](const InferenceDescriptor &ID) { return !ID.SkipFunction(*F); });
1839
1840 if (InferInThisFunc.empty())
1841 continue;
1842
1843 // Start instruction scan.
1844 for (Instruction &I : instructions(F&: *F)) {
1845 llvm::erase_if(C&: InferInThisFunc, P: [&](const InferenceDescriptor &ID) {
1846 if (!ID.InstrBreaksAttribute(I))
1847 return false;
1848 // Remove attribute from further inference on any other functions
1849 // because attribute assumptions have just been violated.
1850 llvm::erase_if(C&: InferInSCC, P: [&ID](const InferenceDescriptor &D) {
1851 return D.AKind == ID.AKind;
1852 });
1853 // Remove attribute from the rest of current instruction scan.
1854 return true;
1855 });
1856
1857 if (InferInThisFunc.empty())
1858 break;
1859 }
1860 }
1861
1862 if (InferInSCC.empty())
1863 return;
1864
1865 for (Function *F : SCCNodes)
1866 // At this point InferInSCC contains only functions that were either:
1867 // - explicitly skipped from scan/inference, or
1868 // - verified to have no instructions that break attribute assumptions.
1869 // Hence we just go and force the attribute for all non-skipped functions.
1870 for (auto &ID : InferInSCC) {
1871 if (ID.SkipFunction(*F))
1872 continue;
1873 Changed.insert(Ptr: F);
1874 ID.SetAttribute(*F);
1875 }
1876}
1877
1878struct SCCNodesResult {
1879 SCCNodeSet SCCNodes;
1880};
1881
1882} // end anonymous namespace
1883
1884/// Helper for non-Convergent inference predicate InstrBreaksAttribute.
1885static bool InstrBreaksNonConvergent(Instruction &I,
1886 const SCCNodeSet &SCCNodes) {
1887 const CallBase *CB = dyn_cast<CallBase>(Val: &I);
1888 // Breaks non-convergent assumption if CS is a convergent call to a function
1889 // not in the SCC.
1890 return CB && CB->isConvergent() &&
1891 !SCCNodes.contains(key: CB->getCalledFunction());
1892}
1893
1894/// Helper for NoUnwind inference predicate InstrBreaksAttribute.
1895static bool InstrBreaksNonThrowing(Instruction &I, const SCCNodeSet &SCCNodes) {
1896 if (!I.mayThrow(/* IncludePhaseOneUnwind */ true))
1897 return false;
1898 if (const auto *CI = dyn_cast<CallInst>(Val: &I)) {
1899 if (Function *Callee = CI->getCalledFunction()) {
1900 // I is a may-throw call to a function inside our SCC. This doesn't
1901 // invalidate our current working assumption that the SCC is no-throw; we
1902 // just have to scan that other function.
1903 if (SCCNodes.contains(key: Callee))
1904 return false;
1905 }
1906 }
1907 return true;
1908}
1909
1910/// Helper for NoFree inference predicate InstrBreaksAttribute.
1911static bool InstrBreaksNoFree(Instruction &I, const SCCNodeSet &SCCNodes) {
1912 CallBase *CB = dyn_cast<CallBase>(Val: &I);
1913 if (!CB) {
1914 // Synchronization may establish happens-before with a free on another
1915 // thread.
1916 return I.maySynchronize();
1917 }
1918
1919 if (CB->hasFnAttr(Kind: Attribute::NoFree))
1920 return false;
1921
1922 // Speculatively assume in SCC.
1923 if (Function *Callee = CB->getCalledFunction())
1924 if (SCCNodes.contains(key: Callee))
1925 return false;
1926
1927 return true;
1928}
1929
1930static bool InstrBreaksNoSync(Instruction &I, const SCCNodeSet &SCCNodes) {
1931 if (!I.maySynchronize())
1932 return false;
1933
1934 // Optimistically assume calls within the SCC are nosync: if nothing else in
1935 // the SCC synchronizes, the assumption holds.
1936 if (auto *CB = dyn_cast<CallBase>(Val: &I))
1937 if (Function *Callee = CB->getCalledFunction())
1938 if (SCCNodes.contains(key: Callee))
1939 return false;
1940
1941 return true;
1942}
1943
1944/// Attempt to remove convergent function attribute when possible.
1945///
1946/// Returns true if any changes to function attributes were made.
1947static void inferConvergent(const SCCNodeSet &SCCNodes,
1948 SmallPtrSet<Function *, 8> &Changed) {
1949 AttributeInferer AI;
1950
1951 // Request to remove the convergent attribute from all functions in the SCC
1952 // if every callsite within the SCC is not convergent (except for calls
1953 // to functions within the SCC).
1954 // Note: Removal of the attr from the callsites will happen in
1955 // InstCombineCalls separately.
1956 AI.registerAttrInference(AttrInference: AttributeInferer::InferenceDescriptor{
1957 Attribute::Convergent,
1958 // Skip non-convergent functions.
1959 [](const Function &F) { return !F.isConvergent(); },
1960 // Instructions that break non-convergent assumption.
1961 [SCCNodes](Instruction &I) {
1962 return InstrBreaksNonConvergent(I, SCCNodes);
1963 },
1964 [](Function &F) {
1965 LLVM_DEBUG(dbgs() << "Removing convergent attr from fn " << F.getName()
1966 << "\n");
1967 F.setNotConvergent();
1968 },
1969 /* RequiresExactDefinition= */ false});
1970 // Perform all the requested attribute inference actions.
1971 AI.run(SCCNodes, Changed);
1972}
1973
1974/// Infer attributes from all functions in the SCC by scanning every
1975/// instruction for compliance to the attribute assumptions.
1976///
1977/// Returns true if any changes to function attributes were made.
1978static void inferAttrsFromFunctionBodies(const IPOOptions &Opts,
1979 const SCCNodeSet &SCCNodes,
1980 SmallPtrSet<Function *, 8> &Changed) {
1981 AttributeInferer AI;
1982
1983 if (Opts.nounwind_inference)
1984 // Request to infer nounwind attribute for all the functions in the SCC if
1985 // every callsite within the SCC is not throwing (except for calls to
1986 // functions within the SCC). Note that nounwind attribute suffers from
1987 // derefinement - results may change depending on how functions are
1988 // optimized. Thus it can be inferred only from exact definitions.
1989 AI.registerAttrInference(AttrInference: AttributeInferer::InferenceDescriptor{
1990 Attribute::NoUnwind,
1991 // Skip non-throwing functions.
1992 [](const Function &F) { return F.doesNotThrow(); },
1993 // Instructions that break non-throwing assumption.
1994 [&SCCNodes](Instruction &I) {
1995 return InstrBreaksNonThrowing(I, SCCNodes);
1996 },
1997 [](Function &F) {
1998 LLVM_DEBUG(dbgs()
1999 << "Adding nounwind attr to fn " << F.getName() << "\n");
2000 F.setDoesNotThrow();
2001 ++NumNoUnwind;
2002 },
2003 /* RequiresExactDefinition= */ true});
2004
2005 if (Opts.nofree_inference)
2006 // Request to infer nofree attribute for all the functions in the SCC if
2007 // every callsite within the SCC does not directly or indirectly free
2008 // memory (except for calls to functions within the SCC). Note that nofree
2009 // attribute suffers from derefinement - results may change depending on
2010 // how functions are optimized. Thus it can be inferred only from exact
2011 // definitions.
2012 AI.registerAttrInference(AttrInference: AttributeInferer::InferenceDescriptor{
2013 Attribute::NoFree,
2014 // Skip functions known not to free memory.
2015 [](const Function &F) { return F.doesNotFreeMemory(); },
2016 // Instructions that break non-deallocating assumption.
2017 [&SCCNodes](Instruction &I) {
2018 return InstrBreaksNoFree(I, SCCNodes);
2019 },
2020 [](Function &F) {
2021 LLVM_DEBUG(dbgs()
2022 << "Adding nofree attr to fn " << F.getName() << "\n");
2023 F.setDoesNotFreeMemory();
2024 ++NumNoFree;
2025 },
2026 /* RequiresExactDefinition= */ true});
2027
2028 AI.registerAttrInference(AttrInference: AttributeInferer::InferenceDescriptor{
2029 Attribute::NoSync,
2030 // Skip already marked functions.
2031 [](const Function &F) { return F.hasNoSync(); },
2032 // Instructions that break nosync assumption.
2033 [&SCCNodes](Instruction &I) {
2034 return InstrBreaksNoSync(I, SCCNodes);
2035 },
2036 [](Function &F) {
2037 LLVM_DEBUG(dbgs()
2038 << "Adding nosync attr to fn " << F.getName() << "\n");
2039 F.setNoSync();
2040 ++NumNoSync;
2041 },
2042 /* RequiresExactDefinition= */ true});
2043
2044 // Perform all the requested attribute inference actions.
2045 AI.run(SCCNodes, Changed);
2046}
2047
2048// Determines if the function 'F' can be marked 'norecurse'.
2049// It returns true if any call within 'F' could lead to a recursive
2050// call back to 'F', and false otherwise.
2051// The 'AnyFunctionsAddressIsTaken' parameter is a module-wide flag
2052// that is true if any function's address is taken, or if any function
2053// has external linkage. This is used to determine the safety of
2054// external/library calls.
2055static bool mayHaveRecursiveCallee(Function &F,
2056 bool AnyFunctionsAddressIsTaken = true) {
2057 for (const auto &BB : F) {
2058 for (const auto &I : BB) {
2059 if (const auto *CB = dyn_cast<CallBase>(Val: &I)) {
2060 const Function *Callee = CB->getCalledFunction();
2061 if (!Callee || Callee == &F)
2062 return true;
2063
2064 if (Callee->doesNotRecurse())
2065 continue;
2066
2067 if (!AnyFunctionsAddressIsTaken ||
2068 (Callee->isDeclaration() &&
2069 Callee->hasFnAttribute(Kind: Attribute::NoCallback)))
2070 continue;
2071 return true;
2072 }
2073 }
2074 }
2075 return false;
2076}
2077
2078static void addNoRecurseAttrs(const SCCNodeSet &SCCNodes,
2079 SmallPtrSet<Function *, 8> &Changed) {
2080 // Try and identify functions that do not recurse.
2081
2082 // If the SCC contains multiple nodes we know for sure there is recursion.
2083 if (SCCNodes.size() != 1)
2084 return;
2085
2086 Function *F = *SCCNodes.begin();
2087 if (!F || !F->hasExactDefinition() || F->doesNotRecurse())
2088 return;
2089 if (!mayHaveRecursiveCallee(F&: *F)) {
2090 // Every call was to a non-recursive function other than this function, and
2091 // we have no indirect recursion as the SCC size is one. This function
2092 // cannot recurse.
2093 F->setDoesNotRecurse();
2094 ++NumNoRecurse;
2095 Changed.insert(Ptr: F);
2096 }
2097}
2098
2099// Set the noreturn function attribute if possible.
2100static void addNoReturnAttrs(const SCCNodeSet &SCCNodes,
2101 SmallPtrSet<Function *, 8> &Changed) {
2102 for (Function *F : SCCNodes) {
2103 if (!F || !F->hasExactDefinition() || F->hasFnAttribute(Kind: Attribute::Naked) ||
2104 F->doesNotReturn())
2105 continue;
2106
2107 if (!canReturn(F: *F)) {
2108 F->setDoesNotReturn();
2109 Changed.insert(Ptr: F);
2110 }
2111 }
2112}
2113
2114static bool allPathsGoThroughCold(Function &F) {
2115 SmallDenseMap<BasicBlock *, bool, 16> ColdPaths;
2116 ColdPaths[&F.front()] = false;
2117 SmallVector<BasicBlock *> Jobs;
2118 Jobs.push_back(Elt: &F.front());
2119
2120 while (!Jobs.empty()) {
2121 BasicBlock *BB = Jobs.pop_back_val();
2122
2123 // If block contains a cold callsite this path through the CG is cold.
2124 // Ignore whether the instructions actually are guaranteed to transfer
2125 // execution. Divergent behavior is considered unlikely.
2126 if (any_of(Range&: *BB, P: [](Instruction &I) {
2127 if (auto *CB = dyn_cast<CallBase>(Val: &I))
2128 return CB->hasFnAttr(Kind: Attribute::Cold);
2129 return false;
2130 })) {
2131 ColdPaths[BB] = true;
2132 continue;
2133 }
2134
2135 auto Succs = successors(BB);
2136 // We found a path that doesn't go through any cold callsite.
2137 if (Succs.empty())
2138 return false;
2139
2140 // We didn't find a cold callsite in this BB, so check that all successors
2141 // contain a cold callsite (or that their successors do).
2142 // Potential TODO: We could use static branch hints to assume certain
2143 // successor paths are inherently cold, irrespective of if they contain a
2144 // cold callsite.
2145 for (BasicBlock *Succ : Succs) {
2146 // Start with false, this is necessary to ensure we don't turn loops into
2147 // cold.
2148 auto [Iter, Inserted] = ColdPaths.try_emplace(Key: Succ, Args: false);
2149 if (!Inserted) {
2150 if (Iter->second)
2151 continue;
2152 return false;
2153 }
2154 Jobs.push_back(Elt: Succ);
2155 }
2156 }
2157 return true;
2158}
2159
2160// Set the cold function attribute if possible.
2161static void addColdAttrs(const SCCNodeSet &SCCNodes,
2162 SmallPtrSet<Function *, 8> &Changed) {
2163 for (Function *F : SCCNodes) {
2164 if (!F || !F->hasExactDefinition() || F->hasFnAttribute(Kind: Attribute::Naked) ||
2165 F->hasFnAttribute(Kind: Attribute::Cold) || F->hasFnAttribute(Kind: Attribute::Hot))
2166 continue;
2167
2168 // Potential TODO: We could add attribute `cold` on functions with `coldcc`.
2169 if (allPathsGoThroughCold(F&: *F)) {
2170 F->addFnAttr(Kind: Attribute::Cold);
2171 ++NumCold;
2172 Changed.insert(Ptr: F);
2173 continue;
2174 }
2175 }
2176}
2177
2178static bool functionWillReturn(const Function &F) {
2179 // We can infer and propagate function attributes only when we know that the
2180 // definition we'll get at link time is *exactly* the definition we see now.
2181 // For more details, see GlobalValue::mayBeDerefined.
2182 if (!F.hasExactDefinition())
2183 return false;
2184
2185 // Must-progress function without side-effects must return.
2186 if (F.mustProgress() && F.onlyReadsMemory())
2187 return true;
2188
2189 // Can only analyze functions with a definition.
2190 if (F.isDeclaration())
2191 return false;
2192
2193 // Functions with loops require more sophisticated analysis, as the loop
2194 // may be infinite. For now, don't try to handle them.
2195 SmallVector<std::pair<const BasicBlock *, const BasicBlock *>> Backedges;
2196 FindFunctionBackedges(F, Result&: Backedges);
2197 if (!Backedges.empty())
2198 return false;
2199
2200 // If there are no loops, then the function is willreturn if all calls in
2201 // it are willreturn.
2202 return all_of(Range: instructions(F), P: [](const Instruction &I) {
2203 return I.willReturn();
2204 });
2205}
2206
2207// Set the willreturn function attribute if possible.
2208static void addWillReturn(const SCCNodeSet &SCCNodes,
2209 SmallPtrSet<Function *, 8> &Changed) {
2210 for (Function *F : SCCNodes) {
2211 if (!F || F->willReturn() || !functionWillReturn(F: *F))
2212 continue;
2213
2214 F->setWillReturn();
2215 NumWillReturn++;
2216 Changed.insert(Ptr: F);
2217 }
2218}
2219
2220static SCCNodesResult createSCCNodeSet(ArrayRef<Function *> Functions) {
2221 SCCNodesResult Res;
2222 for (Function *F : Functions) {
2223 if (!F || F->hasOptNone() || F->hasFnAttribute(Kind: Attribute::Naked) ||
2224 F->isPresplitCoroutine()) {
2225 // Omit any functions we're trying not to optimize from the set.
2226 continue;
2227 }
2228
2229 Res.SCCNodes.insert(X: F);
2230 }
2231 return Res;
2232}
2233
2234template <typename AARGetterT>
2235static SmallPtrSet<Function *, 8>
2236deriveAttrsInPostOrder(ArrayRef<Function *> Functions, AARGetterT &&AARGetter,
2237 bool ArgAttrsOnly) {
2238 SCCNodesResult Nodes = createSCCNodeSet(Functions);
2239
2240 // Bail if the SCC only contains optnone functions.
2241 if (Nodes.SCCNodes.empty())
2242 return {};
2243
2244 const IPOOptions &Opts = getIPOOptions(F: *Nodes.SCCNodes.front());
2245 SmallPtrSet<Function *, 8> Changed;
2246 if (ArgAttrsOnly) {
2247 // ArgAttrsOnly means to only infer attributes that may aid optimizations
2248 // on the *current* function. "initializes" attribute is to aid
2249 // optimizations (like DSE) on the callers, so skip "initializes" here.
2250 addArgumentAttrs(Opts, SCCNodes: Nodes.SCCNodes, Changed, /*SkipInitializes=*/true);
2251 return Changed;
2252 }
2253
2254 addArgumentReturnedAttrs(SCCNodes: Nodes.SCCNodes, Changed);
2255 addMemoryAttrs(Nodes.SCCNodes, AARGetter, Changed);
2256 addArgumentAttrs(Opts, SCCNodes: Nodes.SCCNodes, Changed, /*SkipInitializes=*/false);
2257 inferConvergent(SCCNodes: Nodes.SCCNodes, Changed);
2258 addNoReturnAttrs(SCCNodes: Nodes.SCCNodes, Changed);
2259 addColdAttrs(SCCNodes: Nodes.SCCNodes, Changed);
2260 addWillReturn(SCCNodes: Nodes.SCCNodes, Changed);
2261 addNoUndefAttrs(SCCNodes: Nodes.SCCNodes, Changed);
2262 addNoAliasAttrs(SCCNodes: Nodes.SCCNodes, Changed);
2263 addNonNullAttrs(SCCNodes: Nodes.SCCNodes, Changed);
2264 inferAttrsFromFunctionBodies(Opts, SCCNodes: Nodes.SCCNodes, Changed);
2265 addNoRecurseAttrs(SCCNodes: Nodes.SCCNodes, Changed);
2266
2267 // Finally, infer the maximal set of attributes from the ones we've inferred
2268 // above. This is handling the cases where one attribute on a signature
2269 // implies another, but for implementation reasons the inference rule for
2270 // the later is missing (or simply less sophisticated).
2271 for (Function *F : Nodes.SCCNodes)
2272 if (F)
2273 if (inferAttributesFromOthers(F&: *F))
2274 Changed.insert(Ptr: F);
2275
2276 return Changed;
2277}
2278
2279PreservedAnalyses PostOrderFunctionAttrsPass::run(LazyCallGraph::SCC &C,
2280 CGSCCAnalysisManager &AM,
2281 LazyCallGraph &CG,
2282 CGSCCUpdateResult &) {
2283 // Skip non-recursive functions if requested.
2284 // Only infer argument attributes for non-recursive functions, because
2285 // it can affect optimization behavior in conjunction with noalias.
2286 bool ArgAttrsOnly = false;
2287 if (C.size() == 1 && SkipNonRecursive) {
2288 LazyCallGraph::Node &N = *C.begin();
2289 if (!N->lookup(N))
2290 ArgAttrsOnly = true;
2291 }
2292
2293 FunctionAnalysisManager &FAM =
2294 AM.getResult<FunctionAnalysisManagerCGSCCProxy>(IR&: C, ExtraArgs&: CG).getManager();
2295
2296 // We pass a lambda into functions to wire them up to the analysis manager
2297 // for getting function analyses.
2298 auto AARGetter = [&](Function &F) -> AAResults & {
2299 return FAM.getResult<AAManager>(IR&: F);
2300 };
2301
2302 SmallVector<Function *, 8> Functions;
2303 for (LazyCallGraph::Node &N : C) {
2304 Functions.push_back(Elt: &N.getFunction());
2305 }
2306
2307 auto ChangedFunctions =
2308 deriveAttrsInPostOrder(Functions, AARGetter, ArgAttrsOnly);
2309 if (ChangedFunctions.empty())
2310 return PreservedAnalyses::all();
2311
2312 // Invalidate analyses for modified functions so that we don't have to
2313 // invalidate all analyses for all functions in this SCC.
2314 PreservedAnalyses FuncPA;
2315 // We haven't changed the CFG for modified functions.
2316 FuncPA.preserveSet<CFGAnalyses>();
2317 for (Function *Changed : ChangedFunctions) {
2318 FAM.invalidate(IR&: *Changed, PA: FuncPA);
2319 // Also invalidate any direct callers of changed functions since analyses
2320 // may care about attributes of direct callees. For example, MemorySSA cares
2321 // about whether or not a call's callee modifies memory and queries that
2322 // through function attributes.
2323 for (auto *U : Changed->users()) {
2324 if (auto *Call = dyn_cast<CallBase>(Val: U)) {
2325 if (Call->getCalledOperand() == Changed)
2326 FAM.invalidate(IR&: *Call->getFunction(), PA: FuncPA);
2327 }
2328 }
2329 }
2330
2331 PreservedAnalyses PA;
2332 // We have not added or removed functions.
2333 PA.preserve<FunctionAnalysisManagerCGSCCProxy>();
2334 // We already invalidated all relevant function analyses above.
2335 PA.preserveSet<AllAnalysesOn<Function>>();
2336 return PA;
2337}
2338
2339void PostOrderFunctionAttrsPass::printPipeline(
2340 raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) {
2341 static_cast<PassInfoMixin<PostOrderFunctionAttrsPass> *>(this)->printPipeline(
2342 OS, MapClassName2PassName);
2343 if (SkipNonRecursive)
2344 OS << "<skip-non-recursive-function-attrs>";
2345}
2346
2347static bool addNoRecurseAttrsTopDown(Function &F) {
2348 if (F.doesNotRecurse())
2349 return false;
2350
2351 // We check the preconditions for the function prior to calling this to avoid
2352 // the cost of building up a reversible post-order list. We assert them here
2353 // to make sure none of the invariants this relies on were violated.
2354 assert(!F.isDeclaration() && "Cannot deduce norecurse without a definition!");
2355 assert(F.hasInternalLinkage() &&
2356 "Can only do top-down deduction for internal linkage functions!");
2357
2358 // If F is internal and all of its uses are calls from a non-recursive
2359 // functions, then none of its calls could in fact recurse without going
2360 // through a function marked norecurse, and so we can mark this function too
2361 // as norecurse. Note that the uses must actually be calls -- otherwise
2362 // a pointer to this function could be returned from a norecurse function but
2363 // this function could be recursively (indirectly) called. Note that this
2364 // also detects if F is directly recursive as F is not yet marked as
2365 // a norecurse function.
2366 for (auto &U : F.uses()) {
2367 const CallBase *CB = dyn_cast<CallBase>(Val: U.getUser());
2368 if (!CB || !CB->isCallee(U: &U) ||
2369 !CB->getParent()->getParent()->doesNotRecurse())
2370 return false;
2371 }
2372 F.setDoesNotRecurse();
2373 ++NumNoRecurse;
2374 return true;
2375}
2376
2377static bool addNoFPClassAttrsTopDown(Function &F) {
2378 assert(!F.isDeclaration() && "Cannot deduce nofpclass without a definition!");
2379 unsigned NumArgs = F.arg_size();
2380 SmallVector<FPClassTest, 8> ArgsNoFPClass(NumArgs, fcAllFlags);
2381 FPClassTest RetNoFPClass = fcAllFlags;
2382
2383 bool Changed = false;
2384 for (User *U : F.users()) {
2385 auto *CB = dyn_cast<CallBase>(Val: U);
2386 if (!CB || CB->getCalledFunction() != &F)
2387 return false;
2388
2389 RetNoFPClass &= CB->getRetNoFPClass();
2390 for (unsigned I = 0; I != NumArgs; ++I) {
2391 // TODO: Consider computeKnownFPClass, at least with a small search
2392 // depth. This will currently not catch non-splat vectors.
2393 const APFloat *Cst;
2394 if (match(V: CB->getArgOperand(i: I), P: m_APFloat(Res&: Cst)))
2395 ArgsNoFPClass[I] &= ~Cst->classify();
2396 else
2397 ArgsNoFPClass[I] &= CB->getParamNoFPClass(i: I);
2398 }
2399 }
2400
2401 LLVMContext &Ctx = F.getContext();
2402
2403 if (RetNoFPClass != fcNone) {
2404 FPClassTest OldAttr = F.getAttributes().getRetNoFPClass();
2405 if (OldAttr != RetNoFPClass) {
2406 F.addRetAttr(Attr: Attribute::getWithNoFPClass(Context&: Ctx, Mask: RetNoFPClass));
2407 Changed = true;
2408 }
2409 }
2410
2411 for (unsigned I = 0; I != NumArgs; ++I) {
2412 FPClassTest ArgNoFPClass = ArgsNoFPClass[I];
2413 if (ArgNoFPClass == fcNone)
2414 continue;
2415 FPClassTest OldAttr = F.getParamNoFPClass(ArgNo: I);
2416 if (OldAttr == ArgNoFPClass)
2417 continue;
2418
2419 F.addParamAttr(ArgNo: I, Attr: Attribute::getWithNoFPClass(Context&: Ctx, Mask: ArgNoFPClass));
2420 Changed = true;
2421 }
2422
2423 return Changed;
2424}
2425
2426static bool deduceFunctionAttributeInRPO(Module &M, LazyCallGraph &CG) {
2427 // We only have a post-order SCC traversal (because SCCs are inherently
2428 // discovered in post-order), so we accumulate them in a vector and then walk
2429 // it in reverse. This is simpler than using the RPO iterator infrastructure
2430 // because we need to combine SCC detection and the PO walk of the call
2431 // graph. We can also cheat egregiously because we're primarily interested in
2432 // synthesizing norecurse and so we can only save the singular SCCs as SCCs
2433 // with multiple functions in them will clearly be recursive.
2434
2435 SmallVector<Function *, 16> Worklist;
2436 CG.buildRefSCCs();
2437 for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs()) {
2438 for (LazyCallGraph::SCC &SCC : RC) {
2439 if (SCC.size() != 1)
2440 continue;
2441 Function &F = SCC.begin()->getFunction();
2442 if (!F.isDeclaration() && F.hasInternalLinkage() && !F.use_empty())
2443 Worklist.push_back(Elt: &F);
2444 }
2445 }
2446 bool Changed = false;
2447 for (auto *F : llvm::reverse(C&: Worklist)) {
2448 Changed |= addNoRecurseAttrsTopDown(F&: *F);
2449 Changed |= addNoFPClassAttrsTopDown(F&: *F);
2450 }
2451
2452 return Changed;
2453}
2454
2455PreservedAnalyses
2456ReversePostOrderFunctionAttrsPass::run(Module &M, ModuleAnalysisManager &AM) {
2457 auto &CG = AM.getResult<LazyCallGraphAnalysis>(IR&: M);
2458
2459 if (!deduceFunctionAttributeInRPO(M, CG))
2460 return PreservedAnalyses::all();
2461
2462 PreservedAnalyses PA;
2463 PA.preserve<LazyCallGraphAnalysis>();
2464 return PA;
2465}
2466
2467PreservedAnalyses NoRecurseLTOInferencePass::run(Module &M,
2468 ModuleAnalysisManager &MAM) {
2469
2470 // Check if any function in the whole program has its address taken or has
2471 // potentially external linkage.
2472 // We use this information when inferring norecurse attribute: If there is
2473 // no function whose address is taken and all functions have internal
2474 // linkage, there is no path for a callback to any user function.
2475 bool AnyFunctionsAddressIsTaken = false;
2476 for (Function &F : M) {
2477 if (F.isDeclaration() || F.doesNotRecurse())
2478 continue;
2479 if (!F.hasLocalLinkage() || F.hasAddressTaken()) {
2480 AnyFunctionsAddressIsTaken = true;
2481 break;
2482 }
2483 }
2484
2485 // Run norecurse inference on all RefSCCs in the LazyCallGraph for this
2486 // module.
2487 bool Changed = false;
2488 LazyCallGraph &CG = MAM.getResult<LazyCallGraphAnalysis>(IR&: M);
2489 CG.buildRefSCCs();
2490
2491 for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs()) {
2492 // Skip any RefSCC that is part of a call cycle. A RefSCC containing more
2493 // than one SCC indicates a recursive relationship involving indirect calls.
2494 if (RC.size() > 1)
2495 continue;
2496
2497 // RefSCC contains a single-SCC. SCC size > 1 indicates mutually recursive
2498 // functions. Ex: foo1 -> foo2 -> foo3 -> foo1.
2499 LazyCallGraph::SCC &S = *RC.begin();
2500 if (S.size() > 1)
2501 continue;
2502
2503 // Get the single function from this SCC.
2504 Function &F = S.begin()->getFunction();
2505 if (!F.hasExactDefinition() || F.doesNotRecurse())
2506 continue;
2507
2508 // If the analysis confirms that this function has no recursive calls
2509 // (either direct, indirect, or through external linkages),
2510 // we can safely apply the norecurse attribute.
2511 if (!mayHaveRecursiveCallee(F, AnyFunctionsAddressIsTaken)) {
2512 F.setDoesNotRecurse();
2513 ++NumNoRecurse;
2514 Changed = true;
2515 }
2516 }
2517
2518 PreservedAnalyses PA;
2519 if (Changed)
2520 PA.preserve<LazyCallGraphAnalysis>();
2521 else
2522 PA = PreservedAnalyses::all();
2523 return PA;
2524}
2525