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