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.getParent()->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 break;
1372 }
1373 if (capturesAll(CC))
1374 break;
1375 }
1376
1377 if (!capturesAll(CC)) {
1378 for (ArgumentGraphNode *N : ArgumentSCC) {
1379 Argument *A = N->Definition;
1380 CaptureInfo OrigCI = A->getAttributes().getCaptureInfo();
1381 CaptureInfo NewCI = CaptureInfo(N->CC | CC) & OrigCI;
1382 if (NewCI != OrigCI) {
1383 A->addAttr(Attr: Attribute::getWithCaptureInfo(Context&: A->getContext(), CI: NewCI));
1384 addCapturesStat(CI: NewCI);
1385 Changed.insert(Ptr: A->getParent());
1386 }
1387 }
1388 }
1389
1390 if (capturesAnyProvenance(CC)) {
1391 // As the pointer provenance may be captured, determine the pointer
1392 // attributes looking at each argument individually.
1393 for (ArgumentGraphNode *N : ArgumentSCC) {
1394 if (DetermineAccessAttrsForSingleton(N->Definition))
1395 Changed.insert(Ptr: N->Definition->getParent());
1396 }
1397 continue;
1398 }
1399
1400 // We also want to compute readonly/readnone/writeonly. With a small number
1401 // of false negatives, we can assume that any pointer which is captured
1402 // isn't going to be provably readonly or readnone, since by definition
1403 // we can't analyze all uses of a captured pointer.
1404 //
1405 // The false negatives happen when the pointer is captured by a function
1406 // that promises readonly/readnone behaviour on the pointer, then the
1407 // pointer's lifetime ends before anything that writes to arbitrary memory.
1408 // Also, a readonly/readnone pointer may be returned, but returning a
1409 // pointer is capturing it.
1410
1411 ArgAccessProperties Props;
1412 for (ArgumentGraphNode *N : ArgumentSCC) {
1413 Argument *A = N->Definition;
1414 Props |= determinePointerAccessAttrs(A, SCCNodes: ArgumentSCCNodes);
1415 if (Props.hasAll())
1416 break;
1417 }
1418
1419 if (!Props.hasAll()) {
1420 for (ArgumentGraphNode *N : ArgumentSCC) {
1421 Argument *A = N->Definition;
1422 if (addAccessAttrs(A, Props))
1423 Changed.insert(Ptr: A->getParent());
1424 }
1425 }
1426 }
1427}
1428
1429/// Tests whether a function is "malloc-like".
1430///
1431/// A function is "malloc-like" if it returns either null or a pointer that
1432/// doesn't alias any other pointer visible to the caller.
1433static bool isFunctionMallocLike(Function *F, const SCCNodeSet &SCCNodes) {
1434 SmallSetVector<Value *, 8> FlowsToReturn;
1435 for (BasicBlock &BB : *F)
1436 if (ReturnInst *Ret = dyn_cast<ReturnInst>(Val: BB.getTerminator()))
1437 FlowsToReturn.insert(X: Ret->getReturnValue());
1438
1439 for (unsigned i = 0; i != FlowsToReturn.size(); ++i) {
1440 Value *RetVal = FlowsToReturn[i];
1441
1442 if (Constant *C = dyn_cast<Constant>(Val: RetVal)) {
1443 if (!C->isNullValue() && !isa<UndefValue>(Val: C))
1444 return false;
1445
1446 continue;
1447 }
1448
1449 if (isa<Argument>(Val: RetVal))
1450 return false;
1451
1452 if (Instruction *RVI = dyn_cast<Instruction>(Val: RetVal))
1453 switch (RVI->getOpcode()) {
1454 // Extend the analysis by looking upwards.
1455 case Instruction::BitCast:
1456 case Instruction::GetElementPtr:
1457 case Instruction::AddrSpaceCast:
1458 FlowsToReturn.insert(X: RVI->getOperand(i: 0));
1459 continue;
1460 case Instruction::Select: {
1461 SelectInst *SI = cast<SelectInst>(Val: RVI);
1462 FlowsToReturn.insert(X: SI->getTrueValue());
1463 FlowsToReturn.insert(X: SI->getFalseValue());
1464 continue;
1465 }
1466 case Instruction::PHI: {
1467 PHINode *PN = cast<PHINode>(Val: RVI);
1468 FlowsToReturn.insert_range(R: PN->incoming_values());
1469 continue;
1470 }
1471
1472 // Check whether the pointer came from an allocation.
1473 case Instruction::Alloca:
1474 break;
1475 case Instruction::Call:
1476 case Instruction::Invoke: {
1477 CallBase &CB = cast<CallBase>(Val&: *RVI);
1478 if (CB.hasRetAttr(Kind: Attribute::NoAlias))
1479 break;
1480 if (CB.getCalledFunction() && SCCNodes.count(key: CB.getCalledFunction()))
1481 break;
1482 [[fallthrough]];
1483 }
1484 default:
1485 return false; // Did not come from an allocation.
1486 }
1487
1488 if (PointerMayBeCaptured(V: RetVal, /*ReturnCaptures=*/false))
1489 return false;
1490 }
1491
1492 return true;
1493}
1494
1495/// Deduce noalias attributes for the SCC.
1496static void addNoAliasAttrs(const SCCNodeSet &SCCNodes,
1497 SmallPtrSet<Function *, 8> &Changed) {
1498 // Check each function in turn, determining which functions return noalias
1499 // pointers.
1500 for (Function *F : SCCNodes) {
1501 // Already noalias.
1502 if (F->returnDoesNotAlias())
1503 continue;
1504
1505 // We can infer and propagate function attributes only when we know that the
1506 // definition we'll get at link time is *exactly* the definition we see now.
1507 // For more details, see GlobalValue::mayBeDerefined.
1508 if (!F->hasExactDefinition())
1509 return;
1510
1511 // We annotate noalias return values, which are only applicable to
1512 // pointer types.
1513 if (!F->getReturnType()->isPointerTy())
1514 continue;
1515
1516 if (!isFunctionMallocLike(F, SCCNodes))
1517 return;
1518 }
1519
1520 for (Function *F : SCCNodes) {
1521 if (F->returnDoesNotAlias() ||
1522 !F->getReturnType()->isPointerTy())
1523 continue;
1524
1525 F->setReturnDoesNotAlias();
1526 ++NumNoAlias;
1527 Changed.insert(Ptr: F);
1528 }
1529}
1530
1531/// Tests whether this function is known to not return null.
1532///
1533/// Requires that the function returns a pointer.
1534///
1535/// Returns true if it believes the function will not return a null, and sets
1536/// \p Speculative based on whether the returned conclusion is a speculative
1537/// conclusion due to SCC calls.
1538static bool isReturnNonNull(Function *F, const SCCNodeSet &SCCNodes,
1539 bool &Speculative) {
1540 assert(F->getReturnType()->isPointerTy() &&
1541 "nonnull only meaningful on pointer types");
1542 Speculative = false;
1543
1544 SmallSetVector<Value *, 8> FlowsToReturn;
1545 for (BasicBlock &BB : *F)
1546 if (auto *Ret = dyn_cast<ReturnInst>(Val: BB.getTerminator()))
1547 FlowsToReturn.insert(X: Ret->getReturnValue());
1548
1549 auto &DL = F->getDataLayout();
1550
1551 for (unsigned i = 0; i != FlowsToReturn.size(); ++i) {
1552 Value *RetVal = FlowsToReturn[i];
1553
1554 // If this value is locally known to be non-null, we're good
1555 if (isKnownNonZero(V: RetVal, Q: DL))
1556 continue;
1557
1558 // Otherwise, we need to look upwards since we can't make any local
1559 // conclusions.
1560 Instruction *RVI = dyn_cast<Instruction>(Val: RetVal);
1561 if (!RVI)
1562 return false;
1563 switch (RVI->getOpcode()) {
1564 // Extend the analysis by looking upwards.
1565 case Instruction::BitCast:
1566 case Instruction::AddrSpaceCast:
1567 FlowsToReturn.insert(X: RVI->getOperand(i: 0));
1568 continue;
1569 case Instruction::GetElementPtr:
1570 if (cast<GEPOperator>(Val: RVI)->isInBounds()) {
1571 FlowsToReturn.insert(X: RVI->getOperand(i: 0));
1572 continue;
1573 }
1574 return false;
1575 case Instruction::Select: {
1576 SelectInst *SI = cast<SelectInst>(Val: RVI);
1577 FlowsToReturn.insert(X: SI->getTrueValue());
1578 FlowsToReturn.insert(X: SI->getFalseValue());
1579 continue;
1580 }
1581 case Instruction::PHI: {
1582 PHINode *PN = cast<PHINode>(Val: RVI);
1583 for (int i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
1584 FlowsToReturn.insert(X: PN->getIncomingValue(i));
1585 continue;
1586 }
1587 case Instruction::Call:
1588 case Instruction::Invoke: {
1589 CallBase &CB = cast<CallBase>(Val&: *RVI);
1590 Function *Callee = CB.getCalledFunction();
1591 // A call to a node within the SCC is assumed to return null until
1592 // proven otherwise
1593 if (Callee && SCCNodes.count(key: Callee)) {
1594 Speculative = true;
1595 continue;
1596 }
1597 return false;
1598 }
1599 default:
1600 return false; // Unknown source, may be null
1601 };
1602 llvm_unreachable("should have either continued or returned");
1603 }
1604
1605 return true;
1606}
1607
1608/// Deduce nonnull attributes for the SCC.
1609static void addNonNullAttrs(const SCCNodeSet &SCCNodes,
1610 SmallPtrSet<Function *, 8> &Changed) {
1611 // Speculative that all functions in the SCC return only nonnull
1612 // pointers. We may refute this as we analyze functions.
1613 bool SCCReturnsNonNull = true;
1614
1615 // Check each function in turn, determining which functions return nonnull
1616 // pointers.
1617 for (Function *F : SCCNodes) {
1618 // Already nonnull.
1619 if (F->getAttributes().hasRetAttr(Kind: Attribute::NonNull))
1620 continue;
1621
1622 // We can infer and propagate function attributes only when we know that the
1623 // definition we'll get at link time is *exactly* the definition we see now.
1624 // For more details, see GlobalValue::mayBeDerefined.
1625 if (!F->hasExactDefinition())
1626 return;
1627
1628 // We annotate nonnull return values, which are only applicable to
1629 // pointer types.
1630 if (!F->getReturnType()->isPointerTy())
1631 continue;
1632
1633 bool Speculative = false;
1634 if (isReturnNonNull(F, SCCNodes, Speculative)) {
1635 if (!Speculative) {
1636 // Mark the function eagerly since we may discover a function
1637 // which prevents us from speculating about the entire SCC
1638 LLVM_DEBUG(dbgs() << "Eagerly marking " << F->getName()
1639 << " as nonnull\n");
1640 F->addRetAttr(Kind: Attribute::NonNull);
1641 ++NumNonNullReturn;
1642 Changed.insert(Ptr: F);
1643 }
1644 continue;
1645 }
1646 // At least one function returns something which could be null, can't
1647 // speculate any more.
1648 SCCReturnsNonNull = false;
1649 }
1650
1651 if (SCCReturnsNonNull) {
1652 for (Function *F : SCCNodes) {
1653 if (F->getAttributes().hasRetAttr(Kind: Attribute::NonNull) ||
1654 !F->getReturnType()->isPointerTy())
1655 continue;
1656
1657 LLVM_DEBUG(dbgs() << "SCC marking " << F->getName() << " as nonnull\n");
1658 F->addRetAttr(Kind: Attribute::NonNull);
1659 ++NumNonNullReturn;
1660 Changed.insert(Ptr: F);
1661 }
1662 }
1663}
1664
1665/// Deduce noundef attributes for the SCC.
1666static void addNoUndefAttrs(const SCCNodeSet &SCCNodes,
1667 SmallPtrSet<Function *, 8> &Changed) {
1668 // Check each function in turn, determining which functions return noundef
1669 // values.
1670 for (Function *F : SCCNodes) {
1671 // Already noundef.
1672 AttributeList Attrs = F->getAttributes();
1673 if (Attrs.hasRetAttr(Kind: Attribute::NoUndef))
1674 continue;
1675
1676 // We can infer and propagate function attributes only when we know that the
1677 // definition we'll get at link time is *exactly* the definition we see now.
1678 // For more details, see GlobalValue::mayBeDerefined.
1679 if (!F->hasExactDefinition())
1680 return;
1681
1682 // MemorySanitizer assumes that the definition and declaration of a
1683 // function will be consistent. A function with sanitize_memory attribute
1684 // should be skipped from inference.
1685 if (F->hasFnAttribute(Kind: Attribute::SanitizeMemory))
1686 continue;
1687
1688 if (F->getReturnType()->isVoidTy())
1689 continue;
1690
1691 const DataLayout &DL = F->getDataLayout();
1692 if (all_of(Range&: *F, P: [&](BasicBlock &BB) {
1693 if (auto *Ret = dyn_cast<ReturnInst>(Val: BB.getTerminator())) {
1694 // TODO: perform context-sensitive analysis?
1695 Value *RetVal = Ret->getReturnValue();
1696 if (!isGuaranteedNotToBeUndefOrPoison(V: RetVal))
1697 return false;
1698
1699 // We know the original return value is not poison now, but it
1700 // could still be converted to poison by another return attribute.
1701 // Try to explicitly re-prove the relevant attributes.
1702 if (Attrs.hasRetAttr(Kind: Attribute::NonNull) &&
1703 !isKnownNonZero(V: RetVal, Q: DL))
1704 return false;
1705
1706 if (MaybeAlign Align = Attrs.getRetAlignment())
1707 if (RetVal->getPointerAlignment(DL) < *Align)
1708 return false;
1709
1710 Attribute Attr = Attrs.getRetAttr(Kind: Attribute::Range);
1711 if (Attr.isValid() &&
1712 !Attr.getRange().contains(
1713 CR: computeConstantRange(V: RetVal, /*ForSigned=*/false,
1714 SQ: SimplifyQuery(F->getDataLayout()))))
1715 return false;
1716
1717 FPClassTest AttrFPClass = Attrs.getRetNoFPClass();
1718 if (AttrFPClass != fcNone) {
1719 KnownFPClass ComputedFPClass = computeKnownFPClass(V: RetVal, DL);
1720 if (!ComputedFPClass.isKnownNever(Mask: AttrFPClass))
1721 return false;
1722 }
1723 }
1724 return true;
1725 })) {
1726 F->addRetAttr(Kind: Attribute::NoUndef);
1727 ++NumNoUndefReturn;
1728 Changed.insert(Ptr: F);
1729 }
1730 }
1731}
1732
1733namespace {
1734
1735/// Collects a set of attribute inference requests and performs them all in one
1736/// go on a single SCC Node. Inference involves scanning function bodies
1737/// looking for instructions that violate attribute assumptions.
1738/// As soon as all the bodies are fine we are free to set the attribute.
1739/// Customization of inference for individual attributes is performed by
1740/// providing a handful of predicates for each attribute.
1741class AttributeInferer {
1742public:
1743 /// Describes a request for inference of a single attribute.
1744 struct InferenceDescriptor {
1745
1746 /// Returns true if this function does not have to be handled.
1747 /// General intent for this predicate is to provide an optimization
1748 /// for functions that do not need this attribute inference at all
1749 /// (say, for functions that already have the attribute).
1750 std::function<bool(const Function &)> SkipFunction;
1751
1752 /// Returns true if this instruction violates attribute assumptions.
1753 std::function<bool(Instruction &)> InstrBreaksAttribute;
1754
1755 /// Sets the inferred attribute for this function.
1756 std::function<void(Function &)> SetAttribute;
1757
1758 /// Attribute we derive.
1759 Attribute::AttrKind AKind;
1760
1761 /// If true, only "exact" definitions can be used to infer this attribute.
1762 /// See GlobalValue::isDefinitionExact.
1763 bool RequiresExactDefinition;
1764
1765 InferenceDescriptor(Attribute::AttrKind AK,
1766 std::function<bool(const Function &)> SkipFunc,
1767 std::function<bool(Instruction &)> InstrScan,
1768 std::function<void(Function &)> SetAttr,
1769 bool ReqExactDef)
1770 : SkipFunction(SkipFunc), InstrBreaksAttribute(InstrScan),
1771 SetAttribute(SetAttr), AKind(AK),
1772 RequiresExactDefinition(ReqExactDef) {}
1773 };
1774
1775private:
1776 SmallVector<InferenceDescriptor, 4> InferenceDescriptors;
1777
1778public:
1779 void registerAttrInference(InferenceDescriptor AttrInference) {
1780 InferenceDescriptors.push_back(Elt: AttrInference);
1781 }
1782
1783 void run(const SCCNodeSet &SCCNodes, SmallPtrSet<Function *, 8> &Changed);
1784};
1785
1786/// Perform all the requested attribute inference actions according to the
1787/// attribute predicates stored before.
1788void AttributeInferer::run(const SCCNodeSet &SCCNodes,
1789 SmallPtrSet<Function *, 8> &Changed) {
1790 SmallVector<InferenceDescriptor, 4> InferInSCC = InferenceDescriptors;
1791 // Go through all the functions in SCC and check corresponding attribute
1792 // assumptions for each of them. Attributes that are invalid for this SCC
1793 // will be removed from InferInSCC.
1794 for (Function *F : SCCNodes) {
1795
1796 // No attributes whose assumptions are still valid - done.
1797 if (InferInSCC.empty())
1798 return;
1799
1800 // Check if our attributes ever need scanning/can be scanned.
1801 llvm::erase_if(C&: InferInSCC, P: [F](const InferenceDescriptor &ID) {
1802 if (ID.SkipFunction(*F))
1803 return false;
1804
1805 // Remove from further inference (invalidate) when visiting a function
1806 // that has no instructions to scan/has an unsuitable definition.
1807 return F->isDeclaration() ||
1808 (ID.RequiresExactDefinition && !F->hasExactDefinition());
1809 });
1810
1811 // For each attribute still in InferInSCC that doesn't explicitly skip F,
1812 // set up the F instructions scan to verify assumptions of the attribute.
1813 SmallVector<InferenceDescriptor, 4> InferInThisFunc;
1814 llvm::copy_if(
1815 Range&: InferInSCC, Out: std::back_inserter(x&: InferInThisFunc),
1816 P: [F](const InferenceDescriptor &ID) { return !ID.SkipFunction(*F); });
1817
1818 if (InferInThisFunc.empty())
1819 continue;
1820
1821 // Start instruction scan.
1822 for (Instruction &I : instructions(F&: *F)) {
1823 llvm::erase_if(C&: InferInThisFunc, P: [&](const InferenceDescriptor &ID) {
1824 if (!ID.InstrBreaksAttribute(I))
1825 return false;
1826 // Remove attribute from further inference on any other functions
1827 // because attribute assumptions have just been violated.
1828 llvm::erase_if(C&: InferInSCC, P: [&ID](const InferenceDescriptor &D) {
1829 return D.AKind == ID.AKind;
1830 });
1831 // Remove attribute from the rest of current instruction scan.
1832 return true;
1833 });
1834
1835 if (InferInThisFunc.empty())
1836 break;
1837 }
1838 }
1839
1840 if (InferInSCC.empty())
1841 return;
1842
1843 for (Function *F : SCCNodes)
1844 // At this point InferInSCC contains only functions that were either:
1845 // - explicitly skipped from scan/inference, or
1846 // - verified to have no instructions that break attribute assumptions.
1847 // Hence we just go and force the attribute for all non-skipped functions.
1848 for (auto &ID : InferInSCC) {
1849 if (ID.SkipFunction(*F))
1850 continue;
1851 Changed.insert(Ptr: F);
1852 ID.SetAttribute(*F);
1853 }
1854}
1855
1856struct SCCNodesResult {
1857 SCCNodeSet SCCNodes;
1858};
1859
1860} // end anonymous namespace
1861
1862/// Helper for non-Convergent inference predicate InstrBreaksAttribute.
1863static bool InstrBreaksNonConvergent(Instruction &I,
1864 const SCCNodeSet &SCCNodes) {
1865 const CallBase *CB = dyn_cast<CallBase>(Val: &I);
1866 // Breaks non-convergent assumption if CS is a convergent call to a function
1867 // not in the SCC.
1868 return CB && CB->isConvergent() &&
1869 !SCCNodes.contains(key: CB->getCalledFunction());
1870}
1871
1872/// Helper for NoUnwind inference predicate InstrBreaksAttribute.
1873static bool InstrBreaksNonThrowing(Instruction &I, const SCCNodeSet &SCCNodes) {
1874 if (!I.mayThrow(/* IncludePhaseOneUnwind */ true))
1875 return false;
1876 if (const auto *CI = dyn_cast<CallInst>(Val: &I)) {
1877 if (Function *Callee = CI->getCalledFunction()) {
1878 // I is a may-throw call to a function inside our SCC. This doesn't
1879 // invalidate our current working assumption that the SCC is no-throw; we
1880 // just have to scan that other function.
1881 if (SCCNodes.contains(key: Callee))
1882 return false;
1883 }
1884 }
1885 return true;
1886}
1887
1888/// Helper for NoFree inference predicate InstrBreaksAttribute.
1889static bool InstrBreaksNoFree(Instruction &I, const SCCNodeSet &SCCNodes) {
1890 CallBase *CB = dyn_cast<CallBase>(Val: &I);
1891 if (!CB) {
1892 // Synchronization may establish happens-before with a free on another
1893 // thread.
1894 return I.maySynchronize();
1895 }
1896
1897 if (CB->hasFnAttr(Kind: Attribute::NoFree))
1898 return false;
1899
1900 // Speculatively assume in SCC.
1901 if (Function *Callee = CB->getCalledFunction())
1902 if (SCCNodes.contains(key: Callee))
1903 return false;
1904
1905 return true;
1906}
1907
1908static bool InstrBreaksNoSync(Instruction &I, const SCCNodeSet &SCCNodes) {
1909 if (!I.maySynchronize())
1910 return false;
1911
1912 // Optimistically assume calls within the SCC are nosync: if nothing else in
1913 // the SCC synchronizes, the assumption holds.
1914 if (auto *CB = dyn_cast<CallBase>(Val: &I))
1915 if (Function *Callee = CB->getCalledFunction())
1916 if (SCCNodes.contains(key: Callee))
1917 return false;
1918
1919 return true;
1920}
1921
1922/// Attempt to remove convergent function attribute when possible.
1923///
1924/// Returns true if any changes to function attributes were made.
1925static void inferConvergent(const SCCNodeSet &SCCNodes,
1926 SmallPtrSet<Function *, 8> &Changed) {
1927 AttributeInferer AI;
1928
1929 // Request to remove the convergent attribute from all functions in the SCC
1930 // if every callsite within the SCC is not convergent (except for calls
1931 // to functions within the SCC).
1932 // Note: Removal of the attr from the callsites will happen in
1933 // InstCombineCalls separately.
1934 AI.registerAttrInference(AttrInference: AttributeInferer::InferenceDescriptor{
1935 Attribute::Convergent,
1936 // Skip non-convergent functions.
1937 [](const Function &F) { return !F.isConvergent(); },
1938 // Instructions that break non-convergent assumption.
1939 [SCCNodes](Instruction &I) {
1940 return InstrBreaksNonConvergent(I, SCCNodes);
1941 },
1942 [](Function &F) {
1943 LLVM_DEBUG(dbgs() << "Removing convergent attr from fn " << F.getName()
1944 << "\n");
1945 F.setNotConvergent();
1946 },
1947 /* RequiresExactDefinition= */ false});
1948 // Perform all the requested attribute inference actions.
1949 AI.run(SCCNodes, Changed);
1950}
1951
1952/// Infer attributes from all functions in the SCC by scanning every
1953/// instruction for compliance to the attribute assumptions.
1954///
1955/// Returns true if any changes to function attributes were made.
1956static void inferAttrsFromFunctionBodies(const SCCNodeSet &SCCNodes,
1957 SmallPtrSet<Function *, 8> &Changed) {
1958 AttributeInferer AI;
1959
1960 if (!DisableNoUnwindInference)
1961 // Request to infer nounwind attribute for all the functions in the SCC if
1962 // every callsite within the SCC is not throwing (except for calls to
1963 // functions within the SCC). Note that nounwind attribute suffers from
1964 // derefinement - results may change depending on how functions are
1965 // optimized. Thus it can be inferred only from exact definitions.
1966 AI.registerAttrInference(AttrInference: AttributeInferer::InferenceDescriptor{
1967 Attribute::NoUnwind,
1968 // Skip non-throwing functions.
1969 [](const Function &F) { return F.doesNotThrow(); },
1970 // Instructions that break non-throwing assumption.
1971 [&SCCNodes](Instruction &I) {
1972 return InstrBreaksNonThrowing(I, SCCNodes);
1973 },
1974 [](Function &F) {
1975 LLVM_DEBUG(dbgs()
1976 << "Adding nounwind attr to fn " << F.getName() << "\n");
1977 F.setDoesNotThrow();
1978 ++NumNoUnwind;
1979 },
1980 /* RequiresExactDefinition= */ true});
1981
1982 if (!DisableNoFreeInference)
1983 // Request to infer nofree attribute for all the functions in the SCC if
1984 // every callsite within the SCC does not directly or indirectly free
1985 // memory (except for calls to functions within the SCC). Note that nofree
1986 // attribute suffers from derefinement - results may change depending on
1987 // how functions are optimized. Thus it can be inferred only from exact
1988 // definitions.
1989 AI.registerAttrInference(AttrInference: AttributeInferer::InferenceDescriptor{
1990 Attribute::NoFree,
1991 // Skip functions known not to free memory.
1992 [](const Function &F) { return F.doesNotFreeMemory(); },
1993 // Instructions that break non-deallocating assumption.
1994 [&SCCNodes](Instruction &I) {
1995 return InstrBreaksNoFree(I, SCCNodes);
1996 },
1997 [](Function &F) {
1998 LLVM_DEBUG(dbgs()
1999 << "Adding nofree attr to fn " << F.getName() << "\n");
2000 F.setDoesNotFreeMemory();
2001 ++NumNoFree;
2002 },
2003 /* RequiresExactDefinition= */ true});
2004
2005 AI.registerAttrInference(AttrInference: AttributeInferer::InferenceDescriptor{
2006 Attribute::NoSync,
2007 // Skip already marked functions.
2008 [](const Function &F) { return F.hasNoSync(); },
2009 // Instructions that break nosync assumption.
2010 [&SCCNodes](Instruction &I) {
2011 return InstrBreaksNoSync(I, SCCNodes);
2012 },
2013 [](Function &F) {
2014 LLVM_DEBUG(dbgs()
2015 << "Adding nosync attr to fn " << F.getName() << "\n");
2016 F.setNoSync();
2017 ++NumNoSync;
2018 },
2019 /* RequiresExactDefinition= */ true});
2020
2021 // Perform all the requested attribute inference actions.
2022 AI.run(SCCNodes, Changed);
2023}
2024
2025// Determines if the function 'F' can be marked 'norecurse'.
2026// It returns true if any call within 'F' could lead to a recursive
2027// call back to 'F', and false otherwise.
2028// The 'AnyFunctionsAddressIsTaken' parameter is a module-wide flag
2029// that is true if any function's address is taken, or if any function
2030// has external linkage. This is used to determine the safety of
2031// external/library calls.
2032static bool mayHaveRecursiveCallee(Function &F,
2033 bool AnyFunctionsAddressIsTaken = true) {
2034 for (const auto &BB : F) {
2035 for (const auto &I : BB) {
2036 if (const auto *CB = dyn_cast<CallBase>(Val: &I)) {
2037 const Function *Callee = CB->getCalledFunction();
2038 if (!Callee || Callee == &F)
2039 return true;
2040
2041 if (Callee->doesNotRecurse())
2042 continue;
2043
2044 if (!AnyFunctionsAddressIsTaken ||
2045 (Callee->isDeclaration() &&
2046 Callee->hasFnAttribute(Kind: Attribute::NoCallback)))
2047 continue;
2048 return true;
2049 }
2050 }
2051 }
2052 return false;
2053}
2054
2055static void addNoRecurseAttrs(const SCCNodeSet &SCCNodes,
2056 SmallPtrSet<Function *, 8> &Changed) {
2057 // Try and identify functions that do not recurse.
2058
2059 // If the SCC contains multiple nodes we know for sure there is recursion.
2060 if (SCCNodes.size() != 1)
2061 return;
2062
2063 Function *F = *SCCNodes.begin();
2064 if (!F || !F->hasExactDefinition() || F->doesNotRecurse())
2065 return;
2066 if (!mayHaveRecursiveCallee(F&: *F)) {
2067 // Every call was to a non-recursive function other than this function, and
2068 // we have no indirect recursion as the SCC size is one. This function
2069 // cannot recurse.
2070 F->setDoesNotRecurse();
2071 ++NumNoRecurse;
2072 Changed.insert(Ptr: F);
2073 }
2074}
2075
2076// Set the noreturn function attribute if possible.
2077static void addNoReturnAttrs(const SCCNodeSet &SCCNodes,
2078 SmallPtrSet<Function *, 8> &Changed) {
2079 for (Function *F : SCCNodes) {
2080 if (!F || !F->hasExactDefinition() || F->hasFnAttribute(Kind: Attribute::Naked) ||
2081 F->doesNotReturn())
2082 continue;
2083
2084 if (!canReturn(F: *F)) {
2085 F->setDoesNotReturn();
2086 Changed.insert(Ptr: F);
2087 }
2088 }
2089}
2090
2091static bool allPathsGoThroughCold(Function &F) {
2092 SmallDenseMap<BasicBlock *, bool, 16> ColdPaths;
2093 ColdPaths[&F.front()] = false;
2094 SmallVector<BasicBlock *> Jobs;
2095 Jobs.push_back(Elt: &F.front());
2096
2097 while (!Jobs.empty()) {
2098 BasicBlock *BB = Jobs.pop_back_val();
2099
2100 // If block contains a cold callsite this path through the CG is cold.
2101 // Ignore whether the instructions actually are guaranteed to transfer
2102 // execution. Divergent behavior is considered unlikely.
2103 if (any_of(Range&: *BB, P: [](Instruction &I) {
2104 if (auto *CB = dyn_cast<CallBase>(Val: &I))
2105 return CB->hasFnAttr(Kind: Attribute::Cold);
2106 return false;
2107 })) {
2108 ColdPaths[BB] = true;
2109 continue;
2110 }
2111
2112 auto Succs = successors(BB);
2113 // We found a path that doesn't go through any cold callsite.
2114 if (Succs.empty())
2115 return false;
2116
2117 // We didn't find a cold callsite in this BB, so check that all successors
2118 // contain a cold callsite (or that their successors do).
2119 // Potential TODO: We could use static branch hints to assume certain
2120 // successor paths are inherently cold, irrespective of if they contain a
2121 // cold callsite.
2122 for (BasicBlock *Succ : Succs) {
2123 // Start with false, this is necessary to ensure we don't turn loops into
2124 // cold.
2125 auto [Iter, Inserted] = ColdPaths.try_emplace(Key: Succ, Args: false);
2126 if (!Inserted) {
2127 if (Iter->second)
2128 continue;
2129 return false;
2130 }
2131 Jobs.push_back(Elt: Succ);
2132 }
2133 }
2134 return true;
2135}
2136
2137// Set the cold function attribute if possible.
2138static void addColdAttrs(const SCCNodeSet &SCCNodes,
2139 SmallPtrSet<Function *, 8> &Changed) {
2140 for (Function *F : SCCNodes) {
2141 if (!F || !F->hasExactDefinition() || F->hasFnAttribute(Kind: Attribute::Naked) ||
2142 F->hasFnAttribute(Kind: Attribute::Cold) || F->hasFnAttribute(Kind: Attribute::Hot))
2143 continue;
2144
2145 // Potential TODO: We could add attribute `cold` on functions with `coldcc`.
2146 if (allPathsGoThroughCold(F&: *F)) {
2147 F->addFnAttr(Kind: Attribute::Cold);
2148 ++NumCold;
2149 Changed.insert(Ptr: F);
2150 continue;
2151 }
2152 }
2153}
2154
2155static bool functionWillReturn(const Function &F) {
2156 // We can infer and propagate function attributes only when we know that the
2157 // definition we'll get at link time is *exactly* the definition we see now.
2158 // For more details, see GlobalValue::mayBeDerefined.
2159 if (!F.hasExactDefinition())
2160 return false;
2161
2162 // Must-progress function without side-effects must return.
2163 if (F.mustProgress() && F.onlyReadsMemory())
2164 return true;
2165
2166 // Can only analyze functions with a definition.
2167 if (F.isDeclaration())
2168 return false;
2169
2170 // Functions with loops require more sophisticated analysis, as the loop
2171 // may be infinite. For now, don't try to handle them.
2172 SmallVector<std::pair<const BasicBlock *, const BasicBlock *>> Backedges;
2173 FindFunctionBackedges(F, Result&: Backedges);
2174 if (!Backedges.empty())
2175 return false;
2176
2177 // If there are no loops, then the function is willreturn if all calls in
2178 // it are willreturn.
2179 return all_of(Range: instructions(F), P: [](const Instruction &I) {
2180 return I.willReturn();
2181 });
2182}
2183
2184// Set the willreturn function attribute if possible.
2185static void addWillReturn(const SCCNodeSet &SCCNodes,
2186 SmallPtrSet<Function *, 8> &Changed) {
2187 for (Function *F : SCCNodes) {
2188 if (!F || F->willReturn() || !functionWillReturn(F: *F))
2189 continue;
2190
2191 F->setWillReturn();
2192 NumWillReturn++;
2193 Changed.insert(Ptr: F);
2194 }
2195}
2196
2197static SCCNodesResult createSCCNodeSet(ArrayRef<Function *> Functions) {
2198 SCCNodesResult Res;
2199 for (Function *F : Functions) {
2200 if (!F || F->hasOptNone() || F->hasFnAttribute(Kind: Attribute::Naked) ||
2201 F->isPresplitCoroutine()) {
2202 // Omit any functions we're trying not to optimize from the set.
2203 continue;
2204 }
2205
2206 Res.SCCNodes.insert(X: F);
2207 }
2208 return Res;
2209}
2210
2211template <typename AARGetterT>
2212static SmallPtrSet<Function *, 8>
2213deriveAttrsInPostOrder(ArrayRef<Function *> Functions, AARGetterT &&AARGetter,
2214 bool ArgAttrsOnly) {
2215 SCCNodesResult Nodes = createSCCNodeSet(Functions);
2216
2217 // Bail if the SCC only contains optnone functions.
2218 if (Nodes.SCCNodes.empty())
2219 return {};
2220
2221 SmallPtrSet<Function *, 8> Changed;
2222 if (ArgAttrsOnly) {
2223 // ArgAttrsOnly means to only infer attributes that may aid optimizations
2224 // on the *current* function. "initializes" attribute is to aid
2225 // optimizations (like DSE) on the callers, so skip "initializes" here.
2226 addArgumentAttrs(SCCNodes: Nodes.SCCNodes, Changed, /*SkipInitializes=*/true);
2227 return Changed;
2228 }
2229
2230 addArgumentReturnedAttrs(SCCNodes: Nodes.SCCNodes, Changed);
2231 addMemoryAttrs(Nodes.SCCNodes, AARGetter, Changed);
2232 addArgumentAttrs(SCCNodes: Nodes.SCCNodes, Changed, /*SkipInitializes=*/false);
2233 inferConvergent(SCCNodes: Nodes.SCCNodes, Changed);
2234 addNoReturnAttrs(SCCNodes: Nodes.SCCNodes, Changed);
2235 addColdAttrs(SCCNodes: Nodes.SCCNodes, Changed);
2236 addWillReturn(SCCNodes: Nodes.SCCNodes, Changed);
2237 addNoUndefAttrs(SCCNodes: Nodes.SCCNodes, Changed);
2238 addNoAliasAttrs(SCCNodes: Nodes.SCCNodes, Changed);
2239 addNonNullAttrs(SCCNodes: Nodes.SCCNodes, Changed);
2240 inferAttrsFromFunctionBodies(SCCNodes: Nodes.SCCNodes, Changed);
2241 addNoRecurseAttrs(SCCNodes: Nodes.SCCNodes, Changed);
2242
2243 // Finally, infer the maximal set of attributes from the ones we've inferred
2244 // above. This is handling the cases where one attribute on a signature
2245 // implies another, but for implementation reasons the inference rule for
2246 // the later is missing (or simply less sophisticated).
2247 for (Function *F : Nodes.SCCNodes)
2248 if (F)
2249 if (inferAttributesFromOthers(F&: *F))
2250 Changed.insert(Ptr: F);
2251
2252 return Changed;
2253}
2254
2255PreservedAnalyses PostOrderFunctionAttrsPass::run(LazyCallGraph::SCC &C,
2256 CGSCCAnalysisManager &AM,
2257 LazyCallGraph &CG,
2258 CGSCCUpdateResult &) {
2259 // Skip non-recursive functions if requested.
2260 // Only infer argument attributes for non-recursive functions, because
2261 // it can affect optimization behavior in conjunction with noalias.
2262 bool ArgAttrsOnly = false;
2263 if (C.size() == 1 && SkipNonRecursive) {
2264 LazyCallGraph::Node &N = *C.begin();
2265 if (!N->lookup(N))
2266 ArgAttrsOnly = true;
2267 }
2268
2269 FunctionAnalysisManager &FAM =
2270 AM.getResult<FunctionAnalysisManagerCGSCCProxy>(IR&: C, ExtraArgs&: CG).getManager();
2271
2272 // We pass a lambda into functions to wire them up to the analysis manager
2273 // for getting function analyses.
2274 auto AARGetter = [&](Function &F) -> AAResults & {
2275 return FAM.getResult<AAManager>(IR&: F);
2276 };
2277
2278 SmallVector<Function *, 8> Functions;
2279 for (LazyCallGraph::Node &N : C) {
2280 Functions.push_back(Elt: &N.getFunction());
2281 }
2282
2283 auto ChangedFunctions =
2284 deriveAttrsInPostOrder(Functions, AARGetter, ArgAttrsOnly);
2285 if (ChangedFunctions.empty())
2286 return PreservedAnalyses::all();
2287
2288 // Invalidate analyses for modified functions so that we don't have to
2289 // invalidate all analyses for all functions in this SCC.
2290 PreservedAnalyses FuncPA;
2291 // We haven't changed the CFG for modified functions.
2292 FuncPA.preserveSet<CFGAnalyses>();
2293 for (Function *Changed : ChangedFunctions) {
2294 FAM.invalidate(IR&: *Changed, PA: FuncPA);
2295 // Also invalidate any direct callers of changed functions since analyses
2296 // may care about attributes of direct callees. For example, MemorySSA cares
2297 // about whether or not a call's callee modifies memory and queries that
2298 // through function attributes.
2299 for (auto *U : Changed->users()) {
2300 if (auto *Call = dyn_cast<CallBase>(Val: U)) {
2301 if (Call->getCalledOperand() == Changed)
2302 FAM.invalidate(IR&: *Call->getFunction(), PA: FuncPA);
2303 }
2304 }
2305 }
2306
2307 PreservedAnalyses PA;
2308 // We have not added or removed functions.
2309 PA.preserve<FunctionAnalysisManagerCGSCCProxy>();
2310 // We already invalidated all relevant function analyses above.
2311 PA.preserveSet<AllAnalysesOn<Function>>();
2312 return PA;
2313}
2314
2315void PostOrderFunctionAttrsPass::printPipeline(
2316 raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) {
2317 static_cast<PassInfoMixin<PostOrderFunctionAttrsPass> *>(this)->printPipeline(
2318 OS, MapClassName2PassName);
2319 if (SkipNonRecursive)
2320 OS << "<skip-non-recursive-function-attrs>";
2321}
2322
2323static bool addNoRecurseAttrsTopDown(Function &F) {
2324 if (F.doesNotRecurse())
2325 return false;
2326
2327 // We check the preconditions for the function prior to calling this to avoid
2328 // the cost of building up a reversible post-order list. We assert them here
2329 // to make sure none of the invariants this relies on were violated.
2330 assert(!F.isDeclaration() && "Cannot deduce norecurse without a definition!");
2331 assert(F.hasInternalLinkage() &&
2332 "Can only do top-down deduction for internal linkage functions!");
2333
2334 // If F is internal and all of its uses are calls from a non-recursive
2335 // functions, then none of its calls could in fact recurse without going
2336 // through a function marked norecurse, and so we can mark this function too
2337 // as norecurse. Note that the uses must actually be calls -- otherwise
2338 // a pointer to this function could be returned from a norecurse function but
2339 // this function could be recursively (indirectly) called. Note that this
2340 // also detects if F is directly recursive as F is not yet marked as
2341 // a norecurse function.
2342 for (auto &U : F.uses()) {
2343 const CallBase *CB = dyn_cast<CallBase>(Val: U.getUser());
2344 if (!CB || !CB->isCallee(U: &U) ||
2345 !CB->getParent()->getParent()->doesNotRecurse())
2346 return false;
2347 }
2348 F.setDoesNotRecurse();
2349 ++NumNoRecurse;
2350 return true;
2351}
2352
2353static bool addNoFPClassAttrsTopDown(Function &F) {
2354 assert(!F.isDeclaration() && "Cannot deduce nofpclass without a definition!");
2355 unsigned NumArgs = F.arg_size();
2356 SmallVector<FPClassTest, 8> ArgsNoFPClass(NumArgs, fcAllFlags);
2357 FPClassTest RetNoFPClass = fcAllFlags;
2358
2359 bool Changed = false;
2360 for (User *U : F.users()) {
2361 auto *CB = dyn_cast<CallBase>(Val: U);
2362 if (!CB || CB->getCalledFunction() != &F)
2363 return false;
2364
2365 RetNoFPClass &= CB->getRetNoFPClass();
2366 for (unsigned I = 0; I != NumArgs; ++I) {
2367 // TODO: Consider computeKnownFPClass, at least with a small search
2368 // depth. This will currently not catch non-splat vectors.
2369 const APFloat *Cst;
2370 if (match(V: CB->getArgOperand(i: I), P: m_APFloat(Res&: Cst)))
2371 ArgsNoFPClass[I] &= ~Cst->classify();
2372 else
2373 ArgsNoFPClass[I] &= CB->getParamNoFPClass(i: I);
2374 }
2375 }
2376
2377 LLVMContext &Ctx = F.getContext();
2378
2379 if (RetNoFPClass != fcNone) {
2380 FPClassTest OldAttr = F.getAttributes().getRetNoFPClass();
2381 if (OldAttr != RetNoFPClass) {
2382 F.addRetAttr(Attr: Attribute::getWithNoFPClass(Context&: Ctx, Mask: RetNoFPClass));
2383 Changed = true;
2384 }
2385 }
2386
2387 for (unsigned I = 0; I != NumArgs; ++I) {
2388 FPClassTest ArgNoFPClass = ArgsNoFPClass[I];
2389 if (ArgNoFPClass == fcNone)
2390 continue;
2391 FPClassTest OldAttr = F.getParamNoFPClass(ArgNo: I);
2392 if (OldAttr == ArgNoFPClass)
2393 continue;
2394
2395 F.addParamAttr(ArgNo: I, Attr: Attribute::getWithNoFPClass(Context&: Ctx, Mask: ArgNoFPClass));
2396 Changed = true;
2397 }
2398
2399 return Changed;
2400}
2401
2402static bool deduceFunctionAttributeInRPO(Module &M, LazyCallGraph &CG) {
2403 // We only have a post-order SCC traversal (because SCCs are inherently
2404 // discovered in post-order), so we accumulate them in a vector and then walk
2405 // it in reverse. This is simpler than using the RPO iterator infrastructure
2406 // because we need to combine SCC detection and the PO walk of the call
2407 // graph. We can also cheat egregiously because we're primarily interested in
2408 // synthesizing norecurse and so we can only save the singular SCCs as SCCs
2409 // with multiple functions in them will clearly be recursive.
2410
2411 SmallVector<Function *, 16> Worklist;
2412 CG.buildRefSCCs();
2413 for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs()) {
2414 for (LazyCallGraph::SCC &SCC : RC) {
2415 if (SCC.size() != 1)
2416 continue;
2417 Function &F = SCC.begin()->getFunction();
2418 if (!F.isDeclaration() && F.hasInternalLinkage() && !F.use_empty())
2419 Worklist.push_back(Elt: &F);
2420 }
2421 }
2422 bool Changed = false;
2423 for (auto *F : llvm::reverse(C&: Worklist)) {
2424 Changed |= addNoRecurseAttrsTopDown(F&: *F);
2425 Changed |= addNoFPClassAttrsTopDown(F&: *F);
2426 }
2427
2428 return Changed;
2429}
2430
2431PreservedAnalyses
2432ReversePostOrderFunctionAttrsPass::run(Module &M, ModuleAnalysisManager &AM) {
2433 auto &CG = AM.getResult<LazyCallGraphAnalysis>(IR&: M);
2434
2435 if (!deduceFunctionAttributeInRPO(M, CG))
2436 return PreservedAnalyses::all();
2437
2438 PreservedAnalyses PA;
2439 PA.preserve<LazyCallGraphAnalysis>();
2440 return PA;
2441}
2442
2443PreservedAnalyses NoRecurseLTOInferencePass::run(Module &M,
2444 ModuleAnalysisManager &MAM) {
2445
2446 // Check if any function in the whole program has its address taken or has
2447 // potentially external linkage.
2448 // We use this information when inferring norecurse attribute: If there is
2449 // no function whose address is taken and all functions have internal
2450 // linkage, there is no path for a callback to any user function.
2451 bool AnyFunctionsAddressIsTaken = false;
2452 for (Function &F : M) {
2453 if (F.isDeclaration() || F.doesNotRecurse())
2454 continue;
2455 if (!F.hasLocalLinkage() || F.hasAddressTaken()) {
2456 AnyFunctionsAddressIsTaken = true;
2457 break;
2458 }
2459 }
2460
2461 // Run norecurse inference on all RefSCCs in the LazyCallGraph for this
2462 // module.
2463 bool Changed = false;
2464 LazyCallGraph &CG = MAM.getResult<LazyCallGraphAnalysis>(IR&: M);
2465 CG.buildRefSCCs();
2466
2467 for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs()) {
2468 // Skip any RefSCC that is part of a call cycle. A RefSCC containing more
2469 // than one SCC indicates a recursive relationship involving indirect calls.
2470 if (RC.size() > 1)
2471 continue;
2472
2473 // RefSCC contains a single-SCC. SCC size > 1 indicates mutually recursive
2474 // functions. Ex: foo1 -> foo2 -> foo3 -> foo1.
2475 LazyCallGraph::SCC &S = *RC.begin();
2476 if (S.size() > 1)
2477 continue;
2478
2479 // Get the single function from this SCC.
2480 Function &F = S.begin()->getFunction();
2481 if (!F.hasExactDefinition() || F.doesNotRecurse())
2482 continue;
2483
2484 // If the analysis confirms that this function has no recursive calls
2485 // (either direct, indirect, or through external linkages),
2486 // we can safely apply the norecurse attribute.
2487 if (!mayHaveRecursiveCallee(F, AnyFunctionsAddressIsTaken)) {
2488 F.setDoesNotRecurse();
2489 ++NumNoRecurse;
2490 Changed = true;
2491 }
2492 }
2493
2494 PreservedAnalyses PA;
2495 if (Changed)
2496 PA.preserve<LazyCallGraphAnalysis>();
2497 else
2498 PA = PreservedAnalyses::all();
2499 return PA;
2500}
2501