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