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