LLVM 17.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"
19#include "llvm/ADT/STLExtras.h"
20#include "llvm/ADT/SetVector.h"
22#include "llvm/ADT/SmallSet.h"
24#include "llvm/ADT/Statistic.h"
27#include "llvm/Analysis/CFG.h"
35#include "llvm/IR/Argument.h"
36#include "llvm/IR/Attributes.h"
37#include "llvm/IR/BasicBlock.h"
38#include "llvm/IR/Constant.h"
39#include "llvm/IR/Constants.h"
40#include "llvm/IR/Function.h"
42#include "llvm/IR/InstrTypes.h"
43#include "llvm/IR/Instruction.h"
46#include "llvm/IR/Metadata.h"
48#include "llvm/IR/PassManager.h"
49#include "llvm/IR/Type.h"
50#include "llvm/IR/Use.h"
51#include "llvm/IR/User.h"
52#include "llvm/IR/Value.h"
54#include "llvm/Pass.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(NumNoRecurse, "Number of functions marked as norecurse");
82STATISTIC(NumNoUnwind, "Number of functions marked as nounwind");
83STATISTIC(NumNoFree, "Number of functions marked as nofree");
84STATISTIC(NumWillReturn, "Number of functions marked as willreturn");
85STATISTIC(NumNoSync, "Number of functions marked as nosync");
86
87STATISTIC(NumThinLinkNoRecurse,
88 "Number of functions marked as norecurse during thinlink");
89STATISTIC(NumThinLinkNoUnwind,
90 "Number of functions marked as nounwind during thinlink");
91
93 "enable-nonnull-arg-prop", cl::init(true), cl::Hidden,
94 cl::desc("Try to propagate nonnull argument attributes from callsites to "
95 "caller functions."));
96
98 "disable-nounwind-inference", cl::Hidden,
99 cl::desc("Stop inferring nounwind attribute during function-attrs pass"));
100
102 "disable-nofree-inference", cl::Hidden,
103 cl::desc("Stop inferring nofree attribute during function-attrs pass"));
104
106 "disable-thinlto-funcattrs", cl::init(true), cl::Hidden,
107 cl::desc("Don't propagate function-attrs in thinLTO"));
108
109namespace {
110
111using SCCNodeSet = SmallSetVector<Function *, 8>;
112
113} // end anonymous namespace
114
115/// Returns the memory access attribute for function F using AAR for AA results,
116/// where SCCNodes is the current SCC.
117///
118/// If ThisBody is true, this function may examine the function body and will
119/// return a result pertaining to this copy of the function. If it is false, the
120/// result will be based only on AA results for the function declaration; it
121/// will be assumed that some other (perhaps less optimized) version of the
122/// function may be selected at link time.
124 AAResults &AAR,
125 const SCCNodeSet &SCCNodes) {
126 MemoryEffects OrigME = AAR.getMemoryEffects(&F);
127 if (OrigME.doesNotAccessMemory())
128 // Already perfect!
129 return OrigME;
130
131 if (!ThisBody)
132 return OrigME;
133
135 // Inalloca and preallocated arguments are always clobbered by the call.
136 if (F.getAttributes().hasAttrSomewhere(Attribute::InAlloca) ||
137 F.getAttributes().hasAttrSomewhere(Attribute::Preallocated))
138 ME |= MemoryEffects::argMemOnly(ModRefInfo::ModRef);
139
140 auto AddLocAccess = [&](const MemoryLocation &Loc, ModRefInfo MR) {
141 // Ignore accesses to known-invariant or local memory.
142 MR &= AAR.getModRefInfoMask(Loc, /*IgnoreLocal=*/true);
143 if (isNoModRef(MR))
144 return;
145
146 const Value *UO = getUnderlyingObject(Loc.Ptr);
147 assert(!isa<AllocaInst>(UO) &&
148 "Should have been handled by getModRefInfoMask()");
149 if (isa<Argument>(UO)) {
151 return;
152 }
153
154 // If it's not an identified object, it might be an argument.
155 if (!isIdentifiedObject(UO))
158 };
159 // Scan the function body for instructions that may read or write memory.
160 for (Instruction &I : instructions(F)) {
161 // Some instructions can be ignored even if they read or write memory.
162 // Detect these now, skipping to the next instruction if one is found.
163 if (auto *Call = dyn_cast<CallBase>(&I)) {
164 // Ignore calls to functions in the same SCC, as long as the call sites
165 // don't have operand bundles. Calls with operand bundles are allowed to
166 // have memory effects not described by the memory effects of the call
167 // target.
168 if (!Call->hasOperandBundles() && Call->getCalledFunction() &&
169 SCCNodes.count(Call->getCalledFunction()))
170 continue;
171 MemoryEffects CallME = AAR.getMemoryEffects(Call);
172
173 // If the call doesn't access memory, we're done.
174 if (CallME.doesNotAccessMemory())
175 continue;
176
177 // A pseudo probe call shouldn't change any function attribute since it
178 // doesn't translate to a real instruction. It comes with a memory access
179 // tag to prevent itself being removed by optimizations and not block
180 // other instructions being optimized.
181 if (isa<PseudoProbeInst>(I))
182 continue;
183
185
186 // If the call accesses captured memory (currently part of "other") and
187 // an argument is captured (currently not tracked), then it may also
188 // access argument memory.
189 ModRefInfo OtherMR = CallME.getModRef(MemoryEffects::Other);
190 ME |= MemoryEffects::argMemOnly(OtherMR);
191
192 // Check whether all pointer arguments point to local memory, and
193 // ignore calls that only access local memory.
195 if (ArgMR != ModRefInfo::NoModRef) {
196 for (const Use &U : Call->args()) {
197 const Value *Arg = U;
198 if (!Arg->getType()->isPtrOrPtrVectorTy())
199 continue;
200
201 AddLocAccess(MemoryLocation::getBeforeOrAfter(Arg, I.getAAMetadata()), ArgMR);
202 }
203 }
204 continue;
205 }
206
207 ModRefInfo MR = ModRefInfo::NoModRef;
208 if (I.mayWriteToMemory())
209 MR |= ModRefInfo::Mod;
210 if (I.mayReadFromMemory())
211 MR |= ModRefInfo::Ref;
212 if (MR == ModRefInfo::NoModRef)
213 continue;
214
215 std::optional<MemoryLocation> Loc = MemoryLocation::getOrNone(&I);
216 if (!Loc) {
217 // If no location is known, conservatively assume anything can be
218 // accessed.
219 ME |= MemoryEffects(MR);
220 continue;
221 }
222
223 // Volatile operations may access inaccessible memory.
224 if (I.isVolatile())
226
227 AddLocAccess(*Loc, MR);
228 }
229
230 return OrigME & ME;
231}
232
234 AAResults &AAR) {
235 return checkFunctionMemoryAccess(F, /*ThisBody=*/true, AAR, {});
236}
237
238/// Deduce readonly/readnone/writeonly attributes for the SCC.
239template <typename AARGetterT>
240static void addMemoryAttrs(const SCCNodeSet &SCCNodes, AARGetterT &&AARGetter,
241 SmallSet<Function *, 8> &Changed) {
243 for (Function *F : SCCNodes) {
244 // Call the callable parameter to look up AA results for this function.
245 AAResults &AAR = AARGetter(*F);
246 // Non-exact function definitions may not be selected at link time, and an
247 // alternative version that writes to memory may be selected. See the
248 // comment on GlobalValue::isDefinitionExact for more details.
249 ME |= checkFunctionMemoryAccess(*F, F->hasExactDefinition(), AAR, SCCNodes);
250 // Reached bottom of the lattice, we will not be able to improve the result.
251 if (ME == MemoryEffects::unknown())
252 return;
253 }
254
255 for (Function *F : SCCNodes) {
256 MemoryEffects OldME = F->getMemoryEffects();
257 MemoryEffects NewME = ME & OldME;
258 if (NewME != OldME) {
259 ++NumMemoryAttr;
260 F->setMemoryEffects(NewME);
261 Changed.insert(F);
262 }
263 }
264}
265
266// Compute definitive function attributes for a function taking into account
267// prevailing definitions and linkage types
269 ValueInfo VI,
270 DenseMap<ValueInfo, FunctionSummary *> &CachedPrevailingSummary,
272 IsPrevailing) {
273
274 if (CachedPrevailingSummary.count(VI))
275 return CachedPrevailingSummary[VI];
276
277 /// At this point, prevailing symbols have been resolved. The following leads
278 /// to returning a conservative result:
279 /// - Multiple instances with local linkage. Normally local linkage would be
280 /// unique per module
281 /// as the GUID includes the module path. We could have a guid alias if
282 /// there wasn't any distinguishing path when each file was compiled, but
283 /// that should be rare so we'll punt on those.
284
285 /// These next 2 cases should not happen and will assert:
286 /// - Multiple instances with external linkage. This should be caught in
287 /// symbol resolution
288 /// - Non-existent FunctionSummary for Aliasee. This presents a hole in our
289 /// knowledge meaning we have to go conservative.
290
291 /// Otherwise, we calculate attributes for a function as:
292 /// 1. If we have a local linkage, take its attributes. If there's somehow
293 /// multiple, bail and go conservative.
294 /// 2. If we have an external/WeakODR/LinkOnceODR linkage check that it is
295 /// prevailing, take its attributes.
296 /// 3. If we have a Weak/LinkOnce linkage the copies can have semantic
297 /// differences. However, if the prevailing copy is known it will be used
298 /// so take its attributes. If the prevailing copy is in a native file
299 /// all IR copies will be dead and propagation will go conservative.
300 /// 4. AvailableExternally summaries without a prevailing copy are known to
301 /// occur in a couple of circumstances:
302 /// a. An internal function gets imported due to its caller getting
303 /// imported, it becomes AvailableExternally but no prevailing
304 /// definition exists. Because it has to get imported along with its
305 /// caller the attributes will be captured by propagating on its
306 /// caller.
307 /// b. C++11 [temp.explicit]p10 can generate AvailableExternally
308 /// definitions of explicitly instanced template declarations
309 /// for inlining which are ultimately dropped from the TU. Since this
310 /// is localized to the TU the attributes will have already made it to
311 /// the callers.
312 /// These are edge cases and already captured by their callers so we
313 /// ignore these for now. If they become relevant to optimize in the
314 /// future this can be revisited.
315 /// 5. Otherwise, go conservative.
316
317 CachedPrevailingSummary[VI] = nullptr;
318 FunctionSummary *Local = nullptr;
319 FunctionSummary *Prevailing = nullptr;
320
321 for (const auto &GVS : VI.getSummaryList()) {
322 if (!GVS->isLive())
323 continue;
324
325 FunctionSummary *FS = dyn_cast<FunctionSummary>(GVS->getBaseObject());
326 // Virtual and Unknown (e.g. indirect) calls require going conservative
327 if (!FS || FS->fflags().HasUnknownCall)
328 return nullptr;
329
330 const auto &Linkage = GVS->linkage();
331 if (GlobalValue::isLocalLinkage(Linkage)) {
332 if (Local) {
334 dbgs()
335 << "ThinLTO FunctionAttrs: Multiple Local Linkage, bailing on "
336 "function "
337 << VI.name() << " from " << FS->modulePath() << ". Previous module "
338 << Local->modulePath() << "\n");
339 return nullptr;
340 }
341 Local = FS;
342 } else if (GlobalValue::isExternalLinkage(Linkage)) {
343 assert(IsPrevailing(VI.getGUID(), GVS.get()));
344 Prevailing = FS;
345 break;
346 } else if (GlobalValue::isWeakODRLinkage(Linkage) ||
350 if (IsPrevailing(VI.getGUID(), GVS.get())) {
351 Prevailing = FS;
352 break;
353 }
354 } else if (GlobalValue::isAvailableExternallyLinkage(Linkage)) {
355 // TODO: Handle these cases if they become meaningful
356 continue;
357 }
358 }
359
360 if (Local) {
361 assert(!Prevailing);
362 CachedPrevailingSummary[VI] = Local;
363 } else if (Prevailing) {
364 assert(!Local);
365 CachedPrevailingSummary[VI] = Prevailing;
366 }
367
368 return CachedPrevailingSummary[VI];
369}
370
374 IsPrevailing) {
375 // TODO: implement addNoAliasAttrs once
376 // there's more information about the return type in the summary
378 return false;
379
380 DenseMap<ValueInfo, FunctionSummary *> CachedPrevailingSummary;
381 bool Changed = false;
382
383 auto PropagateAttributes = [&](std::vector<ValueInfo> &SCCNodes) {
384 // Assume we can propagate unless we discover otherwise
385 FunctionSummary::FFlags InferredFlags;
386 InferredFlags.NoRecurse = (SCCNodes.size() == 1);
387 InferredFlags.NoUnwind = true;
388
389 for (auto &V : SCCNodes) {
390 FunctionSummary *CallerSummary =
391 calculatePrevailingSummary(V, CachedPrevailingSummary, IsPrevailing);
392
393 // Function summaries can fail to contain information such as declarations
394 if (!CallerSummary)
395 return;
396
397 if (CallerSummary->fflags().MayThrow)
398 InferredFlags.NoUnwind = false;
399
400 for (const auto &Callee : CallerSummary->calls()) {
402 Callee.first, CachedPrevailingSummary, IsPrevailing);
403
404 if (!CalleeSummary)
405 return;
406
407 if (!CalleeSummary->fflags().NoRecurse)
408 InferredFlags.NoRecurse = false;
409
410 if (!CalleeSummary->fflags().NoUnwind)
411 InferredFlags.NoUnwind = false;
412
413 if (!InferredFlags.NoUnwind && !InferredFlags.NoRecurse)
414 break;
415 }
416 }
417
418 if (InferredFlags.NoUnwind || InferredFlags.NoRecurse) {
419 Changed = true;
420 for (auto &V : SCCNodes) {
421 if (InferredFlags.NoRecurse) {
422 LLVM_DEBUG(dbgs() << "ThinLTO FunctionAttrs: Propagated NoRecurse to "
423 << V.name() << "\n");
424 ++NumThinLinkNoRecurse;
425 }
426
427 if (InferredFlags.NoUnwind) {
428 LLVM_DEBUG(dbgs() << "ThinLTO FunctionAttrs: Propagated NoUnwind to "
429 << V.name() << "\n");
430 ++NumThinLinkNoUnwind;
431 }
432
433 for (const auto &S : V.getSummaryList()) {
434 if (auto *FS = dyn_cast<FunctionSummary>(S.get())) {
435 if (InferredFlags.NoRecurse)
436 FS->setNoRecurse();
437
438 if (InferredFlags.NoUnwind)
439 FS->setNoUnwind();
440 }
441 }
442 }
443 }
444 };
445
446 // Call propagation functions on each SCC in the Index
448 ++I) {
449 std::vector<ValueInfo> Nodes(*I);
450 PropagateAttributes(Nodes);
451 }
452 return Changed;
453}
454
455namespace {
456
457/// For a given pointer Argument, this retains a list of Arguments of functions
458/// in the same SCC that the pointer data flows into. We use this to build an
459/// SCC of the arguments.
460struct ArgumentGraphNode {
461 Argument *Definition;
463};
464
465class ArgumentGraph {
466 // We store pointers to ArgumentGraphNode objects, so it's important that
467 // that they not move around upon insert.
468 using ArgumentMapTy = std::map<Argument *, ArgumentGraphNode>;
469
470 ArgumentMapTy ArgumentMap;
471
472 // There is no root node for the argument graph, in fact:
473 // void f(int *x, int *y) { if (...) f(x, y); }
474 // is an example where the graph is disconnected. The SCCIterator requires a
475 // single entry point, so we maintain a fake ("synthetic") root node that
476 // uses every node. Because the graph is directed and nothing points into
477 // the root, it will not participate in any SCCs (except for its own).
478 ArgumentGraphNode SyntheticRoot;
479
480public:
481 ArgumentGraph() { SyntheticRoot.Definition = nullptr; }
482
484
485 iterator begin() { return SyntheticRoot.Uses.begin(); }
486 iterator end() { return SyntheticRoot.Uses.end(); }
487 ArgumentGraphNode *getEntryNode() { return &SyntheticRoot; }
488
489 ArgumentGraphNode *operator[](Argument *A) {
490 ArgumentGraphNode &Node = ArgumentMap[A];
491 Node.Definition = A;
492 SyntheticRoot.Uses.push_back(&Node);
493 return &Node;
494 }
495};
496
497/// This tracker checks whether callees are in the SCC, and if so it does not
498/// consider that a capture, instead adding it to the "Uses" list and
499/// continuing with the analysis.
500struct ArgumentUsesTracker : public CaptureTracker {
501 ArgumentUsesTracker(const SCCNodeSet &SCCNodes) : SCCNodes(SCCNodes) {}
502
503 void tooManyUses() override { Captured = true; }
504
505 bool captured(const Use *U) override {
506 CallBase *CB = dyn_cast<CallBase>(U->getUser());
507 if (!CB) {
508 Captured = true;
509 return true;
510 }
511
513 if (!F || !F->hasExactDefinition() || !SCCNodes.count(F)) {
514 Captured = true;
515 return true;
516 }
517
518 assert(!CB->isCallee(U) && "callee operand reported captured?");
519 const unsigned UseIndex = CB->getDataOperandNo(U);
520 if (UseIndex >= CB->arg_size()) {
521 // Data operand, but not a argument operand -- must be a bundle operand
522 assert(CB->hasOperandBundles() && "Must be!");
523
524 // CaptureTracking told us that we're being captured by an operand bundle
525 // use. In this case it does not matter if the callee is within our SCC
526 // or not -- we've been captured in some unknown way, and we have to be
527 // conservative.
528 Captured = true;
529 return true;
530 }
531
532 if (UseIndex >= F->arg_size()) {
533 assert(F->isVarArg() && "More params than args in non-varargs call");
534 Captured = true;
535 return true;
536 }
537
538 Uses.push_back(&*std::next(F->arg_begin(), UseIndex));
539 return false;
540 }
541
542 // True only if certainly captured (used outside our SCC).
543 bool Captured = false;
544
545 // Uses within our SCC.
547
548 const SCCNodeSet &SCCNodes;
549};
550
551} // end anonymous namespace
552
553namespace llvm {
554
555template <> struct GraphTraits<ArgumentGraphNode *> {
556 using NodeRef = ArgumentGraphNode *;
558
559 static NodeRef getEntryNode(NodeRef A) { return A; }
560 static ChildIteratorType child_begin(NodeRef N) { return N->Uses.begin(); }
561 static ChildIteratorType child_end(NodeRef N) { return N->Uses.end(); }
562};
563
564template <>
565struct GraphTraits<ArgumentGraph *> : public GraphTraits<ArgumentGraphNode *> {
566 static NodeRef getEntryNode(ArgumentGraph *AG) { return AG->getEntryNode(); }
567
568 static ChildIteratorType nodes_begin(ArgumentGraph *AG) {
569 return AG->begin();
570 }
571
572 static ChildIteratorType nodes_end(ArgumentGraph *AG) { return AG->end(); }
573};
574
575} // end namespace llvm
576
577/// Returns Attribute::None, Attribute::ReadOnly or Attribute::ReadNone.
580 const SmallPtrSet<Argument *, 8> &SCCNodes) {
581 SmallVector<Use *, 32> Worklist;
583
584 // inalloca arguments are always clobbered by the call.
585 if (A->hasInAllocaAttr() || A->hasPreallocatedAttr())
586 return Attribute::None;
587
588 bool IsRead = false;
589 bool IsWrite = false;
590
591 for (Use &U : A->uses()) {
592 Visited.insert(&U);
593 Worklist.push_back(&U);
594 }
595
596 while (!Worklist.empty()) {
597 if (IsWrite && IsRead)
598 // No point in searching further..
599 return Attribute::None;
600
601 Use *U = Worklist.pop_back_val();
602 Instruction *I = cast<Instruction>(U->getUser());
603
604 switch (I->getOpcode()) {
605 case Instruction::BitCast:
606 case Instruction::GetElementPtr:
607 case Instruction::PHI:
608 case Instruction::Select:
609 case Instruction::AddrSpaceCast:
610 // The original value is not read/written via this if the new value isn't.
611 for (Use &UU : I->uses())
612 if (Visited.insert(&UU).second)
613 Worklist.push_back(&UU);
614 break;
615
616 case Instruction::Call:
617 case Instruction::Invoke: {
618 CallBase &CB = cast<CallBase>(*I);
619 if (CB.isCallee(U)) {
620 IsRead = true;
621 // Note that indirect calls do not capture, see comment in
622 // CaptureTracking for context
623 continue;
624 }
625
626 // Given we've explictily handled the callee operand above, what's left
627 // must be a data operand (e.g. argument or operand bundle)
628 const unsigned UseIndex = CB.getDataOperandNo(U);
629
630 if (!CB.doesNotCapture(UseIndex)) {
631 if (!CB.onlyReadsMemory())
632 // If the callee can save a copy into other memory, then simply
633 // scanning uses of the call is insufficient. We have no way
634 // of tracking copies of the pointer through memory to see
635 // if a reloaded copy is written to, thus we must give up.
636 return Attribute::None;
637 // Push users for processing once we finish this one
638 if (!I->getType()->isVoidTy())
639 for (Use &UU : I->uses())
640 if (Visited.insert(&UU).second)
641 Worklist.push_back(&UU);
642 }
643
644 if (CB.doesNotAccessMemory())
645 continue;
646
647 if (Function *F = CB.getCalledFunction())
648 if (CB.isArgOperand(U) && UseIndex < F->arg_size() &&
649 SCCNodes.count(F->getArg(UseIndex)))
650 // This is an argument which is part of the speculative SCC. Note
651 // that only operands corresponding to formal arguments of the callee
652 // can participate in the speculation.
653 break;
654
655 // The accessors used on call site here do the right thing for calls and
656 // invokes with operand bundles.
657 if (CB.doesNotAccessMemory(UseIndex)) {
658 /* nop */
659 } else if (CB.onlyReadsMemory() || CB.onlyReadsMemory(UseIndex)) {
660 IsRead = true;
661 } else if (CB.hasFnAttr(Attribute::WriteOnly) ||
662 CB.dataOperandHasImpliedAttr(UseIndex, Attribute::WriteOnly)) {
663 IsWrite = true;
664 } else {
665 return Attribute::None;
666 }
667 break;
668 }
669
670 case Instruction::Load:
671 // A volatile load has side effects beyond what readonly can be relied
672 // upon.
673 if (cast<LoadInst>(I)->isVolatile())
674 return Attribute::None;
675
676 IsRead = true;
677 break;
678
679 case Instruction::Store:
680 if (cast<StoreInst>(I)->getValueOperand() == *U)
681 // untrackable capture
682 return Attribute::None;
683
684 // A volatile store has side effects beyond what writeonly can be relied
685 // upon.
686 if (cast<StoreInst>(I)->isVolatile())
687 return Attribute::None;
688
689 IsWrite = true;
690 break;
691
692 case Instruction::ICmp:
693 case Instruction::Ret:
694 break;
695
696 default:
697 return Attribute::None;
698 }
699 }
700
701 if (IsWrite && IsRead)
702 return Attribute::None;
703 else if (IsRead)
704 return Attribute::ReadOnly;
705 else if (IsWrite)
706 return Attribute::WriteOnly;
707 else
708 return Attribute::ReadNone;
709}
710
711/// Deduce returned attributes for the SCC.
712static void addArgumentReturnedAttrs(const SCCNodeSet &SCCNodes,
713 SmallSet<Function *, 8> &Changed) {
714 // Check each function in turn, determining if an argument is always returned.
715 for (Function *F : SCCNodes) {
716 // We can infer and propagate function attributes only when we know that the
717 // definition we'll get at link time is *exactly* the definition we see now.
718 // For more details, see GlobalValue::mayBeDerefined.
719 if (!F->hasExactDefinition())
720 continue;
721
722 if (F->getReturnType()->isVoidTy())
723 continue;
724
725 // There is nothing to do if an argument is already marked as 'returned'.
726 if (F->getAttributes().hasAttrSomewhere(Attribute::Returned))
727 continue;
728
729 auto FindRetArg = [&]() -> Argument * {
730 Argument *RetArg = nullptr;
731 for (BasicBlock &BB : *F)
732 if (auto *Ret = dyn_cast<ReturnInst>(BB.getTerminator())) {
733 // Note that stripPointerCasts should look through functions with
734 // returned arguments.
735 auto *RetVal =
736 dyn_cast<Argument>(Ret->getReturnValue()->stripPointerCasts());
737 if (!RetVal || RetVal->getType() != F->getReturnType())
738 return nullptr;
739
740 if (!RetArg)
741 RetArg = RetVal;
742 else if (RetArg != RetVal)
743 return nullptr;
744 }
745
746 return RetArg;
747 };
748
749 if (Argument *RetArg = FindRetArg()) {
750 RetArg->addAttr(Attribute::Returned);
751 ++NumReturned;
752 Changed.insert(F);
753 }
754 }
755}
756
757/// If a callsite has arguments that are also arguments to the parent function,
758/// try to propagate attributes from the callsite's arguments to the parent's
759/// arguments. This may be important because inlining can cause information loss
760/// when attribute knowledge disappears with the inlined call.
763 return false;
764
765 bool Changed = false;
766
767 // For an argument attribute to transfer from a callsite to the parent, the
768 // call must be guaranteed to execute every time the parent is called.
769 // Conservatively, just check for calls in the entry block that are guaranteed
770 // to execute.
771 // TODO: This could be enhanced by testing if the callsite post-dominates the
772 // entry block or by doing simple forward walks or backward walks to the
773 // callsite.
774 BasicBlock &Entry = F.getEntryBlock();
775 for (Instruction &I : Entry) {
776 if (auto *CB = dyn_cast<CallBase>(&I)) {
777 if (auto *CalledFunc = CB->getCalledFunction()) {
778 for (auto &CSArg : CalledFunc->args()) {
779 if (!CSArg.hasNonNullAttr(/* AllowUndefOrPoison */ false))
780 continue;
781
782 // If the non-null callsite argument operand is an argument to 'F'
783 // (the caller) and the call is guaranteed to execute, then the value
784 // must be non-null throughout 'F'.
785 auto *FArg = dyn_cast<Argument>(CB->getArgOperand(CSArg.getArgNo()));
786 if (FArg && !FArg->hasNonNullAttr()) {
787 FArg->addAttr(Attribute::NonNull);
788 Changed = true;
789 }
790 }
791 }
792 }
794 break;
795 }
796
797 return Changed;
798}
799
801 assert((R == Attribute::ReadOnly || R == Attribute::ReadNone ||
802 R == Attribute::WriteOnly)
803 && "Must be an access attribute.");
804 assert(A && "Argument must not be null.");
805
806 // If the argument already has the attribute, nothing needs to be done.
807 if (A->hasAttribute(R))
808 return false;
809
810 // Otherwise, remove potentially conflicting attribute, add the new one,
811 // and update statistics.
812 A->removeAttr(Attribute::WriteOnly);
813 A->removeAttr(Attribute::ReadOnly);
814 A->removeAttr(Attribute::ReadNone);
815 A->addAttr(R);
816 if (R == Attribute::ReadOnly)
817 ++NumReadOnlyArg;
818 else if (R == Attribute::WriteOnly)
819 ++NumWriteOnlyArg;
820 else
821 ++NumReadNoneArg;
822 return true;
823}
824
825/// Deduce nocapture attributes for the SCC.
826static void addArgumentAttrs(const SCCNodeSet &SCCNodes,
827 SmallSet<Function *, 8> &Changed) {
828 ArgumentGraph AG;
829
830 // Check each function in turn, determining which pointer arguments are not
831 // captured.
832 for (Function *F : SCCNodes) {
833 // We can infer and propagate function attributes only when we know that the
834 // definition we'll get at link time is *exactly* the definition we see now.
835 // For more details, see GlobalValue::mayBeDerefined.
836 if (!F->hasExactDefinition())
837 continue;
838
840 Changed.insert(F);
841
842 // Functions that are readonly (or readnone) and nounwind and don't return
843 // a value can't capture arguments. Don't analyze them.
844 if (F->onlyReadsMemory() && F->doesNotThrow() &&
845 F->getReturnType()->isVoidTy()) {
846 for (Argument &A : F->args()) {
847 if (A.getType()->isPointerTy() && !A.hasNoCaptureAttr()) {
848 A.addAttr(Attribute::NoCapture);
849 ++NumNoCapture;
850 Changed.insert(F);
851 }
852 }
853 continue;
854 }
855
856 for (Argument &A : F->args()) {
857 if (!A.getType()->isPointerTy())
858 continue;
859 bool HasNonLocalUses = false;
860 if (!A.hasNoCaptureAttr()) {
861 ArgumentUsesTracker Tracker(SCCNodes);
862 PointerMayBeCaptured(&A, &Tracker);
863 if (!Tracker.Captured) {
864 if (Tracker.Uses.empty()) {
865 // If it's trivially not captured, mark it nocapture now.
866 A.addAttr(Attribute::NoCapture);
867 ++NumNoCapture;
868 Changed.insert(F);
869 } else {
870 // If it's not trivially captured and not trivially not captured,
871 // then it must be calling into another function in our SCC. Save
872 // its particulars for Argument-SCC analysis later.
873 ArgumentGraphNode *Node = AG[&A];
874 for (Argument *Use : Tracker.Uses) {
875 Node->Uses.push_back(AG[Use]);
876 if (Use != &A)
877 HasNonLocalUses = true;
878 }
879 }
880 }
881 // Otherwise, it's captured. Don't bother doing SCC analysis on it.
882 }
883 if (!HasNonLocalUses && !A.onlyReadsMemory()) {
884 // Can we determine that it's readonly/readnone/writeonly without doing
885 // an SCC? Note that we don't allow any calls at all here, or else our
886 // result will be dependent on the iteration order through the
887 // functions in the SCC.
889 Self.insert(&A);
891 if (R != Attribute::None)
892 if (addAccessAttr(&A, R))
893 Changed.insert(F);
894 }
895 }
896 }
897
898 // The graph we've collected is partial because we stopped scanning for
899 // argument uses once we solved the argument trivially. These partial nodes
900 // show up as ArgumentGraphNode objects with an empty Uses list, and for
901 // these nodes the final decision about whether they capture has already been
902 // made. If the definition doesn't have a 'nocapture' attribute by now, it
903 // captures.
904
905 for (scc_iterator<ArgumentGraph *> I = scc_begin(&AG); !I.isAtEnd(); ++I) {
906 const std::vector<ArgumentGraphNode *> &ArgumentSCC = *I;
907 if (ArgumentSCC.size() == 1) {
908 if (!ArgumentSCC[0]->Definition)
909 continue; // synthetic root node
910
911 // eg. "void f(int* x) { if (...) f(x); }"
912 if (ArgumentSCC[0]->Uses.size() == 1 &&
913 ArgumentSCC[0]->Uses[0] == ArgumentSCC[0]) {
914 Argument *A = ArgumentSCC[0]->Definition;
915 A->addAttr(Attribute::NoCapture);
916 ++NumNoCapture;
917 Changed.insert(A->getParent());
918
919 // Infer the access attributes given the new nocapture one
921 Self.insert(&*A);
923 if (R != Attribute::None)
924 addAccessAttr(A, R);
925 }
926 continue;
927 }
928
929 bool SCCCaptured = false;
930 for (ArgumentGraphNode *Node : ArgumentSCC) {
931 if (Node->Uses.empty() && !Node->Definition->hasNoCaptureAttr()) {
932 SCCCaptured = true;
933 break;
934 }
935 }
936 if (SCCCaptured)
937 continue;
938
939 SmallPtrSet<Argument *, 8> ArgumentSCCNodes;
940 // Fill ArgumentSCCNodes with the elements of the ArgumentSCC. Used for
941 // quickly looking up whether a given Argument is in this ArgumentSCC.
942 for (ArgumentGraphNode *I : ArgumentSCC) {
943 ArgumentSCCNodes.insert(I->Definition);
944 }
945
946 for (ArgumentGraphNode *N : ArgumentSCC) {
947 for (ArgumentGraphNode *Use : N->Uses) {
948 Argument *A = Use->Definition;
949 if (A->hasNoCaptureAttr() || ArgumentSCCNodes.count(A))
950 continue;
951 SCCCaptured = true;
952 break;
953 }
954 if (SCCCaptured)
955 break;
956 }
957 if (SCCCaptured)
958 continue;
959
960 for (ArgumentGraphNode *N : ArgumentSCC) {
961 Argument *A = N->Definition;
962 A->addAttr(Attribute::NoCapture);
963 ++NumNoCapture;
964 Changed.insert(A->getParent());
965 }
966
967 // We also want to compute readonly/readnone/writeonly. With a small number
968 // of false negatives, we can assume that any pointer which is captured
969 // isn't going to be provably readonly or readnone, since by definition
970 // we can't analyze all uses of a captured pointer.
971 //
972 // The false negatives happen when the pointer is captured by a function
973 // that promises readonly/readnone behaviour on the pointer, then the
974 // pointer's lifetime ends before anything that writes to arbitrary memory.
975 // Also, a readonly/readnone pointer may be returned, but returning a
976 // pointer is capturing it.
977
978 auto meetAccessAttr = [](Attribute::AttrKind A, Attribute::AttrKind B) {
979 if (A == B)
980 return A;
981 if (A == Attribute::ReadNone)
982 return B;
983 if (B == Attribute::ReadNone)
984 return A;
985 return Attribute::None;
986 };
987
988 Attribute::AttrKind AccessAttr = Attribute::ReadNone;
989 for (ArgumentGraphNode *N : ArgumentSCC) {
990 Argument *A = N->Definition;
992 AccessAttr = meetAccessAttr(AccessAttr, K);
993 if (AccessAttr == Attribute::None)
994 break;
995 }
996
997 if (AccessAttr != Attribute::None) {
998 for (ArgumentGraphNode *N : ArgumentSCC) {
999 Argument *A = N->Definition;
1000 if (addAccessAttr(A, AccessAttr))
1001 Changed.insert(A->getParent());
1002 }
1003 }
1004 }
1005}
1006
1007/// Tests whether a function is "malloc-like".
1008///
1009/// A function is "malloc-like" if it returns either null or a pointer that
1010/// doesn't alias any other pointer visible to the caller.
1011static bool isFunctionMallocLike(Function *F, const SCCNodeSet &SCCNodes) {
1012 SmallSetVector<Value *, 8> FlowsToReturn;
1013 for (BasicBlock &BB : *F)
1014 if (ReturnInst *Ret = dyn_cast<ReturnInst>(BB.getTerminator()))
1015 FlowsToReturn.insert(Ret->getReturnValue());
1016
1017 for (unsigned i = 0; i != FlowsToReturn.size(); ++i) {
1018 Value *RetVal = FlowsToReturn[i];
1019
1020 if (Constant *C = dyn_cast<Constant>(RetVal)) {
1021 if (!C->isNullValue() && !isa<UndefValue>(C))
1022 return false;
1023
1024 continue;
1025 }
1026
1027 if (isa<Argument>(RetVal))
1028 return false;
1029
1030 if (Instruction *RVI = dyn_cast<Instruction>(RetVal))
1031 switch (RVI->getOpcode()) {
1032 // Extend the analysis by looking upwards.
1033 case Instruction::BitCast:
1034 case Instruction::GetElementPtr:
1035 case Instruction::AddrSpaceCast:
1036 FlowsToReturn.insert(RVI->getOperand(0));
1037 continue;
1038 case Instruction::Select: {
1039 SelectInst *SI = cast<SelectInst>(RVI);
1040 FlowsToReturn.insert(SI->getTrueValue());
1041 FlowsToReturn.insert(SI->getFalseValue());
1042 continue;
1043 }
1044 case Instruction::PHI: {
1045 PHINode *PN = cast<PHINode>(RVI);
1046 for (Value *IncValue : PN->incoming_values())
1047 FlowsToReturn.insert(IncValue);
1048 continue;
1049 }
1050
1051 // Check whether the pointer came from an allocation.
1052 case Instruction::Alloca:
1053 break;
1054 case Instruction::Call:
1055 case Instruction::Invoke: {
1056 CallBase &CB = cast<CallBase>(*RVI);
1057 if (CB.hasRetAttr(Attribute::NoAlias))
1058 break;
1059 if (CB.getCalledFunction() && SCCNodes.count(CB.getCalledFunction()))
1060 break;
1061 [[fallthrough]];
1062 }
1063 default:
1064 return false; // Did not come from an allocation.
1065 }
1066
1067 if (PointerMayBeCaptured(RetVal, false, /*StoreCaptures=*/false))
1068 return false;
1069 }
1070
1071 return true;
1072}
1073
1074/// Deduce noalias attributes for the SCC.
1075static void addNoAliasAttrs(const SCCNodeSet &SCCNodes,
1076 SmallSet<Function *, 8> &Changed) {
1077 // Check each function in turn, determining which functions return noalias
1078 // pointers.
1079 for (Function *F : SCCNodes) {
1080 // Already noalias.
1081 if (F->returnDoesNotAlias())
1082 continue;
1083
1084 // We can infer and propagate function attributes only when we know that the
1085 // definition we'll get at link time is *exactly* the definition we see now.
1086 // For more details, see GlobalValue::mayBeDerefined.
1087 if (!F->hasExactDefinition())
1088 return;
1089
1090 // We annotate noalias return values, which are only applicable to
1091 // pointer types.
1092 if (!F->getReturnType()->isPointerTy())
1093 continue;
1094
1095 if (!isFunctionMallocLike(F, SCCNodes))
1096 return;
1097 }
1098
1099 for (Function *F : SCCNodes) {
1100 if (F->returnDoesNotAlias() ||
1101 !F->getReturnType()->isPointerTy())
1102 continue;
1103
1104 F->setReturnDoesNotAlias();
1105 ++NumNoAlias;
1106 Changed.insert(F);
1107 }
1108}
1109
1110/// Tests whether this function is known to not return null.
1111///
1112/// Requires that the function returns a pointer.
1113///
1114/// Returns true if it believes the function will not return a null, and sets
1115/// \p Speculative based on whether the returned conclusion is a speculative
1116/// conclusion due to SCC calls.
1117static bool isReturnNonNull(Function *F, const SCCNodeSet &SCCNodes,
1118 bool &Speculative) {
1119 assert(F->getReturnType()->isPointerTy() &&
1120 "nonnull only meaningful on pointer types");
1121 Speculative = false;
1122
1123 SmallSetVector<Value *, 8> FlowsToReturn;
1124 for (BasicBlock &BB : *F)
1125 if (auto *Ret = dyn_cast<ReturnInst>(BB.getTerminator()))
1126 FlowsToReturn.insert(Ret->getReturnValue());
1127
1128 auto &DL = F->getParent()->getDataLayout();
1129
1130 for (unsigned i = 0; i != FlowsToReturn.size(); ++i) {
1131 Value *RetVal = FlowsToReturn[i];
1132
1133 // If this value is locally known to be non-null, we're good
1134 if (isKnownNonZero(RetVal, DL))
1135 continue;
1136
1137 // Otherwise, we need to look upwards since we can't make any local
1138 // conclusions.
1139 Instruction *RVI = dyn_cast<Instruction>(RetVal);
1140 if (!RVI)
1141 return false;
1142 switch (RVI->getOpcode()) {
1143 // Extend the analysis by looking upwards.
1144 case Instruction::BitCast:
1145 case Instruction::GetElementPtr:
1146 case Instruction::AddrSpaceCast:
1147 FlowsToReturn.insert(RVI->getOperand(0));
1148 continue;
1149 case Instruction::Select: {
1150 SelectInst *SI = cast<SelectInst>(RVI);
1151 FlowsToReturn.insert(SI->getTrueValue());
1152 FlowsToReturn.insert(SI->getFalseValue());
1153 continue;
1154 }
1155 case Instruction::PHI: {
1156 PHINode *PN = cast<PHINode>(RVI);
1157 for (int i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
1158 FlowsToReturn.insert(PN->getIncomingValue(i));
1159 continue;
1160 }
1161 case Instruction::Call:
1162 case Instruction::Invoke: {
1163 CallBase &CB = cast<CallBase>(*RVI);
1165 // A call to a node within the SCC is assumed to return null until
1166 // proven otherwise
1167 if (Callee && SCCNodes.count(Callee)) {
1168 Speculative = true;
1169 continue;
1170 }
1171 return false;
1172 }
1173 default:
1174 return false; // Unknown source, may be null
1175 };
1176 llvm_unreachable("should have either continued or returned");
1177 }
1178
1179 return true;
1180}
1181
1182/// Deduce nonnull attributes for the SCC.
1183static void addNonNullAttrs(const SCCNodeSet &SCCNodes,
1184 SmallSet<Function *, 8> &Changed) {
1185 // Speculative that all functions in the SCC return only nonnull
1186 // pointers. We may refute this as we analyze functions.
1187 bool SCCReturnsNonNull = true;
1188
1189 // Check each function in turn, determining which functions return nonnull
1190 // pointers.
1191 for (Function *F : SCCNodes) {
1192 // Already nonnull.
1193 if (F->getAttributes().hasRetAttr(Attribute::NonNull))
1194 continue;
1195
1196 // We can infer and propagate function attributes only when we know that the
1197 // definition we'll get at link time is *exactly* the definition we see now.
1198 // For more details, see GlobalValue::mayBeDerefined.
1199 if (!F->hasExactDefinition())
1200 return;
1201
1202 // We annotate nonnull return values, which are only applicable to
1203 // pointer types.
1204 if (!F->getReturnType()->isPointerTy())
1205 continue;
1206
1207 bool Speculative = false;
1208 if (isReturnNonNull(F, SCCNodes, Speculative)) {
1209 if (!Speculative) {
1210 // Mark the function eagerly since we may discover a function
1211 // which prevents us from speculating about the entire SCC
1212 LLVM_DEBUG(dbgs() << "Eagerly marking " << F->getName()
1213 << " as nonnull\n");
1214 F->addRetAttr(Attribute::NonNull);
1215 ++NumNonNullReturn;
1216 Changed.insert(F);
1217 }
1218 continue;
1219 }
1220 // At least one function returns something which could be null, can't
1221 // speculate any more.
1222 SCCReturnsNonNull = false;
1223 }
1224
1225 if (SCCReturnsNonNull) {
1226 for (Function *F : SCCNodes) {
1227 if (F->getAttributes().hasRetAttr(Attribute::NonNull) ||
1228 !F->getReturnType()->isPointerTy())
1229 continue;
1230
1231 LLVM_DEBUG(dbgs() << "SCC marking " << F->getName() << " as nonnull\n");
1232 F->addRetAttr(Attribute::NonNull);
1233 ++NumNonNullReturn;
1234 Changed.insert(F);
1235 }
1236 }
1237}
1238
1239namespace {
1240
1241/// Collects a set of attribute inference requests and performs them all in one
1242/// go on a single SCC Node. Inference involves scanning function bodies
1243/// looking for instructions that violate attribute assumptions.
1244/// As soon as all the bodies are fine we are free to set the attribute.
1245/// Customization of inference for individual attributes is performed by
1246/// providing a handful of predicates for each attribute.
1247class AttributeInferer {
1248public:
1249 /// Describes a request for inference of a single attribute.
1250 struct InferenceDescriptor {
1251
1252 /// Returns true if this function does not have to be handled.
1253 /// General intent for this predicate is to provide an optimization
1254 /// for functions that do not need this attribute inference at all
1255 /// (say, for functions that already have the attribute).
1256 std::function<bool(const Function &)> SkipFunction;
1257
1258 /// Returns true if this instruction violates attribute assumptions.
1259 std::function<bool(Instruction &)> InstrBreaksAttribute;
1260
1261 /// Sets the inferred attribute for this function.
1262 std::function<void(Function &)> SetAttribute;
1263
1264 /// Attribute we derive.
1265 Attribute::AttrKind AKind;
1266
1267 /// If true, only "exact" definitions can be used to infer this attribute.
1268 /// See GlobalValue::isDefinitionExact.
1269 bool RequiresExactDefinition;
1270
1271 InferenceDescriptor(Attribute::AttrKind AK,
1272 std::function<bool(const Function &)> SkipFunc,
1273 std::function<bool(Instruction &)> InstrScan,
1274 std::function<void(Function &)> SetAttr,
1275 bool ReqExactDef)
1276 : SkipFunction(SkipFunc), InstrBreaksAttribute(InstrScan),
1277 SetAttribute(SetAttr), AKind(AK),
1278 RequiresExactDefinition(ReqExactDef) {}
1279 };
1280
1281private:
1282 SmallVector<InferenceDescriptor, 4> InferenceDescriptors;
1283
1284public:
1285 void registerAttrInference(InferenceDescriptor AttrInference) {
1286 InferenceDescriptors.push_back(AttrInference);
1287 }
1288
1289 void run(const SCCNodeSet &SCCNodes, SmallSet<Function *, 8> &Changed);
1290};
1291
1292/// Perform all the requested attribute inference actions according to the
1293/// attribute predicates stored before.
1294void AttributeInferer::run(const SCCNodeSet &SCCNodes,
1295 SmallSet<Function *, 8> &Changed) {
1296 SmallVector<InferenceDescriptor, 4> InferInSCC = InferenceDescriptors;
1297 // Go through all the functions in SCC and check corresponding attribute
1298 // assumptions for each of them. Attributes that are invalid for this SCC
1299 // will be removed from InferInSCC.
1300 for (Function *F : SCCNodes) {
1301
1302 // No attributes whose assumptions are still valid - done.
1303 if (InferInSCC.empty())
1304 return;
1305
1306 // Check if our attributes ever need scanning/can be scanned.
1307 llvm::erase_if(InferInSCC, [F](const InferenceDescriptor &ID) {
1308 if (ID.SkipFunction(*F))
1309 return false;
1310
1311 // Remove from further inference (invalidate) when visiting a function
1312 // that has no instructions to scan/has an unsuitable definition.
1313 return F->isDeclaration() ||
1314 (ID.RequiresExactDefinition && !F->hasExactDefinition());
1315 });
1316
1317 // For each attribute still in InferInSCC that doesn't explicitly skip F,
1318 // set up the F instructions scan to verify assumptions of the attribute.
1321 InferInSCC, std::back_inserter(InferInThisFunc),
1322 [F](const InferenceDescriptor &ID) { return !ID.SkipFunction(*F); });
1323
1324 if (InferInThisFunc.empty())
1325 continue;
1326
1327 // Start instruction scan.
1328 for (Instruction &I : instructions(*F)) {
1329 llvm::erase_if(InferInThisFunc, [&](const InferenceDescriptor &ID) {
1330 if (!ID.InstrBreaksAttribute(I))
1331 return false;
1332 // Remove attribute from further inference on any other functions
1333 // because attribute assumptions have just been violated.
1334 llvm::erase_if(InferInSCC, [&ID](const InferenceDescriptor &D) {
1335 return D.AKind == ID.AKind;
1336 });
1337 // Remove attribute from the rest of current instruction scan.
1338 return true;
1339 });
1340
1341 if (InferInThisFunc.empty())
1342 break;
1343 }
1344 }
1345
1346 if (InferInSCC.empty())
1347 return;
1348
1349 for (Function *F : SCCNodes)
1350 // At this point InferInSCC contains only functions that were either:
1351 // - explicitly skipped from scan/inference, or
1352 // - verified to have no instructions that break attribute assumptions.
1353 // Hence we just go and force the attribute for all non-skipped functions.
1354 for (auto &ID : InferInSCC) {
1355 if (ID.SkipFunction(*F))
1356 continue;
1357 Changed.insert(F);
1358 ID.SetAttribute(*F);
1359 }
1360}
1361
1362struct SCCNodesResult {
1363 SCCNodeSet SCCNodes;
1364 bool HasUnknownCall;
1365};
1366
1367} // end anonymous namespace
1368
1369/// Helper for non-Convergent inference predicate InstrBreaksAttribute.
1371 const SCCNodeSet &SCCNodes) {
1372 const CallBase *CB = dyn_cast<CallBase>(&I);
1373 // Breaks non-convergent assumption if CS is a convergent call to a function
1374 // not in the SCC.
1375 return CB && CB->isConvergent() &&
1376 !SCCNodes.contains(CB->getCalledFunction());
1377}
1378
1379/// Helper for NoUnwind inference predicate InstrBreaksAttribute.
1380static bool InstrBreaksNonThrowing(Instruction &I, const SCCNodeSet &SCCNodes) {
1381 if (!I.mayThrow())
1382 return false;
1383 if (const auto *CI = dyn_cast<CallInst>(&I)) {
1384 if (Function *Callee = CI->getCalledFunction()) {
1385 // I is a may-throw call to a function inside our SCC. This doesn't
1386 // invalidate our current working assumption that the SCC is no-throw; we
1387 // just have to scan that other function.
1388 if (SCCNodes.contains(Callee))
1389 return false;
1390 }
1391 }
1392 return true;
1393}
1394
1395/// Helper for NoFree inference predicate InstrBreaksAttribute.
1396static bool InstrBreaksNoFree(Instruction &I, const SCCNodeSet &SCCNodes) {
1397 CallBase *CB = dyn_cast<CallBase>(&I);
1398 if (!CB)
1399 return false;
1400
1401 if (CB->hasFnAttr(Attribute::NoFree))
1402 return false;
1403
1404 // Speculatively assume in SCC.
1405 if (Function *Callee = CB->getCalledFunction())
1406 if (SCCNodes.contains(Callee))
1407 return false;
1408
1409 return true;
1410}
1411
1412// Return true if this is an atomic which has an ordering stronger than
1413// unordered. Note that this is different than the predicate we use in
1414// Attributor. Here we chose to be conservative and consider monotonic
1415// operations potentially synchronizing. We generally don't do much with
1416// monotonic operations, so this is simply risk reduction.
1418 if (!I->isAtomic())
1419 return false;
1420
1421 if (auto *FI = dyn_cast<FenceInst>(I))
1422 // All legal orderings for fence are stronger than monotonic.
1423 return FI->getSyncScopeID() != SyncScope::SingleThread;
1424 else if (isa<AtomicCmpXchgInst>(I) || isa<AtomicRMWInst>(I))
1425 return true;
1426 else if (auto *SI = dyn_cast<StoreInst>(I))
1427 return !SI->isUnordered();
1428 else if (auto *LI = dyn_cast<LoadInst>(I))
1429 return !LI->isUnordered();
1430 else {
1431 llvm_unreachable("unknown atomic instruction?");
1432 }
1433}
1434
1435static bool InstrBreaksNoSync(Instruction &I, const SCCNodeSet &SCCNodes) {
1436 // Volatile may synchronize
1437 if (I.isVolatile())
1438 return true;
1439
1440 // An ordered atomic may synchronize. (See comment about on monotonic.)
1441 if (isOrderedAtomic(&I))
1442 return true;
1443
1444 auto *CB = dyn_cast<CallBase>(&I);
1445 if (!CB)
1446 // Non call site cases covered by the two checks above
1447 return false;
1448
1449 if (CB->hasFnAttr(Attribute::NoSync))
1450 return false;
1451
1452 // Non volatile memset/memcpy/memmoves are nosync
1453 // NOTE: Only intrinsics with volatile flags should be handled here. All
1454 // others should be marked in Intrinsics.td.
1455 if (auto *MI = dyn_cast<MemIntrinsic>(&I))
1456 if (!MI->isVolatile())
1457 return false;
1458
1459 // Speculatively assume in SCC.
1460 if (Function *Callee = CB->getCalledFunction())
1461 if (SCCNodes.contains(Callee))
1462 return false;
1463
1464 return true;
1465}
1466
1467/// Attempt to remove convergent function attribute when possible.
1468///
1469/// Returns true if any changes to function attributes were made.
1470static void inferConvergent(const SCCNodeSet &SCCNodes,
1471 SmallSet<Function *, 8> &Changed) {
1472 AttributeInferer AI;
1473
1474 // Request to remove the convergent attribute from all functions in the SCC
1475 // if every callsite within the SCC is not convergent (except for calls
1476 // to functions within the SCC).
1477 // Note: Removal of the attr from the callsites will happen in
1478 // InstCombineCalls separately.
1479 AI.registerAttrInference(AttributeInferer::InferenceDescriptor{
1480 Attribute::Convergent,
1481 // Skip non-convergent functions.
1482 [](const Function &F) { return !F.isConvergent(); },
1483 // Instructions that break non-convergent assumption.
1484 [SCCNodes](Instruction &I) {
1485 return InstrBreaksNonConvergent(I, SCCNodes);
1486 },
1487 [](Function &F) {
1488 LLVM_DEBUG(dbgs() << "Removing convergent attr from fn " << F.getName()
1489 << "\n");
1490 F.setNotConvergent();
1491 },
1492 /* RequiresExactDefinition= */ false});
1493 // Perform all the requested attribute inference actions.
1494 AI.run(SCCNodes, Changed);
1495}
1496
1497/// Infer attributes from all functions in the SCC by scanning every
1498/// instruction for compliance to the attribute assumptions.
1499///
1500/// Returns true if any changes to function attributes were made.
1501static void inferAttrsFromFunctionBodies(const SCCNodeSet &SCCNodes,
1502 SmallSet<Function *, 8> &Changed) {
1503 AttributeInferer AI;
1504
1506 // Request to infer nounwind attribute for all the functions in the SCC if
1507 // every callsite within the SCC is not throwing (except for calls to
1508 // functions within the SCC). Note that nounwind attribute suffers from
1509 // derefinement - results may change depending on how functions are
1510 // optimized. Thus it can be inferred only from exact definitions.
1511 AI.registerAttrInference(AttributeInferer::InferenceDescriptor{
1512 Attribute::NoUnwind,
1513 // Skip non-throwing functions.
1514 [](const Function &F) { return F.doesNotThrow(); },
1515 // Instructions that break non-throwing assumption.
1516 [&SCCNodes](Instruction &I) {
1517 return InstrBreaksNonThrowing(I, SCCNodes);
1518 },
1519 [](Function &F) {
1521 << "Adding nounwind attr to fn " << F.getName() << "\n");
1522 F.setDoesNotThrow();
1523 ++NumNoUnwind;
1524 },
1525 /* RequiresExactDefinition= */ true});
1526
1528 // Request to infer nofree attribute for all the functions in the SCC if
1529 // every callsite within the SCC does not directly or indirectly free
1530 // memory (except for calls to functions within the SCC). Note that nofree
1531 // attribute suffers from derefinement - results may change depending on
1532 // how functions are optimized. Thus it can be inferred only from exact
1533 // definitions.
1534 AI.registerAttrInference(AttributeInferer::InferenceDescriptor{
1535 Attribute::NoFree,
1536 // Skip functions known not to free memory.
1537 [](const Function &F) { return F.doesNotFreeMemory(); },
1538 // Instructions that break non-deallocating assumption.
1539 [&SCCNodes](Instruction &I) {
1540 return InstrBreaksNoFree(I, SCCNodes);
1541 },
1542 [](Function &F) {
1544 << "Adding nofree attr to fn " << F.getName() << "\n");
1545 F.setDoesNotFreeMemory();
1546 ++NumNoFree;
1547 },
1548 /* RequiresExactDefinition= */ true});
1549
1550 AI.registerAttrInference(AttributeInferer::InferenceDescriptor{
1551 Attribute::NoSync,
1552 // Skip already marked functions.
1553 [](const Function &F) { return F.hasNoSync(); },
1554 // Instructions that break nosync assumption.
1555 [&SCCNodes](Instruction &I) {
1556 return InstrBreaksNoSync(I, SCCNodes);
1557 },
1558 [](Function &F) {
1560 << "Adding nosync attr to fn " << F.getName() << "\n");
1561 F.setNoSync();
1562 ++NumNoSync;
1563 },
1564 /* RequiresExactDefinition= */ true});
1565
1566 // Perform all the requested attribute inference actions.
1567 AI.run(SCCNodes, Changed);
1568}
1569
1570static void addNoRecurseAttrs(const SCCNodeSet &SCCNodes,
1571 SmallSet<Function *, 8> &Changed) {
1572 // Try and identify functions that do not recurse.
1573
1574 // If the SCC contains multiple nodes we know for sure there is recursion.
1575 if (SCCNodes.size() != 1)
1576 return;
1577
1578 Function *F = *SCCNodes.begin();
1579 if (!F || !F->hasExactDefinition() || F->doesNotRecurse())
1580 return;
1581
1582 // If all of the calls in F are identifiable and are to norecurse functions, F
1583 // is norecurse. This check also detects self-recursion as F is not currently
1584 // marked norecurse, so any called from F to F will not be marked norecurse.
1585 for (auto &BB : *F)
1586 for (auto &I : BB.instructionsWithoutDebug())
1587 if (auto *CB = dyn_cast<CallBase>(&I)) {
1589 if (!Callee || Callee == F || !Callee->doesNotRecurse())
1590 // Function calls a potentially recursive function.
1591 return;
1592 }
1593
1594 // Every call was to a non-recursive function other than this function, and
1595 // we have no indirect recursion as the SCC size is one. This function cannot
1596 // recurse.
1597 F->setDoesNotRecurse();
1598 ++NumNoRecurse;
1599 Changed.insert(F);
1600}
1601
1603 if (auto *CB = dyn_cast<CallBase>(&I))
1604 return CB->hasFnAttr(Attribute::NoReturn);
1605 return false;
1606}
1607
1608// A basic block can only return if it terminates with a ReturnInst and does not
1609// contain calls to noreturn functions.
1611 if (!isa<ReturnInst>(BB.getTerminator()))
1612 return false;
1614}
1615
1616// FIXME: this doesn't handle recursion.
1617static bool canReturn(Function &F) {
1620
1621 Visited.insert(&F.front());
1622 Worklist.push_back(&F.front());
1623
1624 do {
1625 BasicBlock *BB = Worklist.pop_back_val();
1626 if (basicBlockCanReturn(*BB))
1627 return true;
1628 for (BasicBlock *Succ : successors(BB))
1629 if (Visited.insert(Succ).second)
1630 Worklist.push_back(Succ);
1631 } while (!Worklist.empty());
1632
1633 return false;
1634}
1635
1636// Set the noreturn function attribute if possible.
1637static void addNoReturnAttrs(const SCCNodeSet &SCCNodes,
1638 SmallSet<Function *, 8> &Changed) {
1639 for (Function *F : SCCNodes) {
1640 if (!F || !F->hasExactDefinition() || F->hasFnAttribute(Attribute::Naked) ||
1641 F->doesNotReturn())
1642 continue;
1643
1644 if (!canReturn(*F)) {
1645 F->setDoesNotReturn();
1646 Changed.insert(F);
1647 }
1648 }
1649}
1650
1651static bool functionWillReturn(const Function &F) {
1652 // We can infer and propagate function attributes only when we know that the
1653 // definition we'll get at link time is *exactly* the definition we see now.
1654 // For more details, see GlobalValue::mayBeDerefined.
1655 if (!F.hasExactDefinition())
1656 return false;
1657
1658 // Must-progress function without side-effects must return.
1659 if (F.mustProgress() && F.onlyReadsMemory())
1660 return true;
1661
1662 // Can only analyze functions with a definition.
1663 if (F.isDeclaration())
1664 return false;
1665
1666 // Functions with loops require more sophisticated analysis, as the loop
1667 // may be infinite. For now, don't try to handle them.
1669 FindFunctionBackedges(F, Backedges);
1670 if (!Backedges.empty())
1671 return false;
1672
1673 // If there are no loops, then the function is willreturn if all calls in
1674 // it are willreturn.
1675 return all_of(instructions(F), [](const Instruction &I) {
1676 return I.willReturn();
1677 });
1678}
1679
1680// Set the willreturn function attribute if possible.
1681static void addWillReturn(const SCCNodeSet &SCCNodes,
1682 SmallSet<Function *, 8> &Changed) {
1683 for (Function *F : SCCNodes) {
1684 if (!F || F->willReturn() || !functionWillReturn(*F))
1685 continue;
1686
1687 F->setWillReturn();
1688 NumWillReturn++;
1689 Changed.insert(F);
1690 }
1691}
1692
1693static SCCNodesResult createSCCNodeSet(ArrayRef<Function *> Functions) {
1694 SCCNodesResult Res;
1695 Res.HasUnknownCall = false;
1696 for (Function *F : Functions) {
1697 if (!F || F->hasOptNone() || F->hasFnAttribute(Attribute::Naked) ||
1698 F->isPresplitCoroutine()) {
1699 // Treat any function we're trying not to optimize as if it were an
1700 // indirect call and omit it from the node set used below.
1701 Res.HasUnknownCall = true;
1702 continue;
1703 }
1704 // Track whether any functions in this SCC have an unknown call edge.
1705 // Note: if this is ever a performance hit, we can common it with
1706 // subsequent routines which also do scans over the instructions of the
1707 // function.
1708 if (!Res.HasUnknownCall) {
1709 for (Instruction &I : instructions(*F)) {
1710 if (auto *CB = dyn_cast<CallBase>(&I)) {
1711 if (!CB->getCalledFunction()) {
1712 Res.HasUnknownCall = true;
1713 break;
1714 }
1715 }
1716 }
1717 }
1718 Res.SCCNodes.insert(F);
1719 }
1720 return Res;
1721}
1722
1723template <typename AARGetterT>
1725deriveAttrsInPostOrder(ArrayRef<Function *> Functions, AARGetterT &&AARGetter) {
1726 SCCNodesResult Nodes = createSCCNodeSet(Functions);
1727
1728 // Bail if the SCC only contains optnone functions.
1729 if (Nodes.SCCNodes.empty())
1730 return {};
1731
1733
1734 addArgumentReturnedAttrs(Nodes.SCCNodes, Changed);
1735 addMemoryAttrs(Nodes.SCCNodes, AARGetter, Changed);
1736 addArgumentAttrs(Nodes.SCCNodes, Changed);
1737 inferConvergent(Nodes.SCCNodes, Changed);
1738 addNoReturnAttrs(Nodes.SCCNodes, Changed);
1739 addWillReturn(Nodes.SCCNodes, Changed);
1740
1741 // If we have no external nodes participating in the SCC, we can deduce some
1742 // more precise attributes as well.
1743 if (!Nodes.HasUnknownCall) {
1744 addNoAliasAttrs(Nodes.SCCNodes, Changed);
1745 addNonNullAttrs(Nodes.SCCNodes, Changed);
1746 inferAttrsFromFunctionBodies(Nodes.SCCNodes, Changed);
1747 addNoRecurseAttrs(Nodes.SCCNodes, Changed);
1748 }
1749
1750 // Finally, infer the maximal set of attributes from the ones we've inferred
1751 // above. This is handling the cases where one attribute on a signature
1752 // implies another, but for implementation reasons the inference rule for
1753 // the later is missing (or simply less sophisticated).
1754 for (Function *F : Nodes.SCCNodes)
1755 if (F)
1757 Changed.insert(F);
1758
1759 return Changed;
1760}
1761
1764 LazyCallGraph &CG,
1766 // Skip non-recursive functions if requested.
1767 if (C.size() == 1 && SkipNonRecursive) {
1768 LazyCallGraph::Node &N = *C.begin();
1769 if (!N->lookup(N))
1770 return PreservedAnalyses::all();
1771 }
1772
1774 AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C, CG).getManager();
1775
1776 // We pass a lambda into functions to wire them up to the analysis manager
1777 // for getting function analyses.
1778 auto AARGetter = [&](Function &F) -> AAResults & {
1779 return FAM.getResult<AAManager>(F);
1780 };
1781
1783 for (LazyCallGraph::Node &N : C) {
1784 Functions.push_back(&N.getFunction());
1785 }
1786
1787 auto ChangedFunctions = deriveAttrsInPostOrder(Functions, AARGetter);
1788 if (ChangedFunctions.empty())
1789 return PreservedAnalyses::all();
1790
1791 // Invalidate analyses for modified functions so that we don't have to
1792 // invalidate all analyses for all functions in this SCC.
1793 PreservedAnalyses FuncPA;
1794 // We haven't changed the CFG for modified functions.
1795 FuncPA.preserveSet<CFGAnalyses>();
1796 for (Function *Changed : ChangedFunctions) {
1797 FAM.invalidate(*Changed, FuncPA);
1798 // Also invalidate any direct callers of changed functions since analyses
1799 // may care about attributes of direct callees. For example, MemorySSA cares
1800 // about whether or not a call's callee modifies memory and queries that
1801 // through function attributes.
1802 for (auto *U : Changed->users()) {
1803 if (auto *Call = dyn_cast<CallBase>(U)) {
1804 if (Call->getCalledFunction() == Changed)
1805 FAM.invalidate(*Call->getFunction(), FuncPA);
1806 }
1807 }
1808 }
1809
1811 // We have not added or removed functions.
1813 // We already invalidated all relevant function analyses above.
1815 return PA;
1816}
1817
1819 raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) {
1821 OS, MapClassName2PassName);
1822 if (SkipNonRecursive)
1823 OS << "<skip-non-recursive>";
1824}
1825
1826template <typename AARGetterT>
1827static bool runImpl(CallGraphSCC &SCC, AARGetterT AARGetter) {
1829 for (CallGraphNode *I : SCC) {
1830 Functions.push_back(I->getFunction());
1831 }
1832
1833 return !deriveAttrsInPostOrder(Functions, AARGetter).empty();
1834}
1835
1837 // We check the preconditions for the function prior to calling this to avoid
1838 // the cost of building up a reversible post-order list. We assert them here
1839 // to make sure none of the invariants this relies on were violated.
1840 assert(!F.isDeclaration() && "Cannot deduce norecurse without a definition!");
1841 assert(!F.doesNotRecurse() &&
1842 "This function has already been deduced as norecurs!");
1843 assert(F.hasInternalLinkage() &&
1844 "Can only do top-down deduction for internal linkage functions!");
1845
1846 // If F is internal and all of its uses are calls from a non-recursive
1847 // functions, then none of its calls could in fact recurse without going
1848 // through a function marked norecurse, and so we can mark this function too
1849 // as norecurse. Note that the uses must actually be calls -- otherwise
1850 // a pointer to this function could be returned from a norecurse function but
1851 // this function could be recursively (indirectly) called. Note that this
1852 // also detects if F is directly recursive as F is not yet marked as
1853 // a norecurse function.
1854 for (auto &U : F.uses()) {
1855 auto *I = dyn_cast<Instruction>(U.getUser());
1856 if (!I)
1857 return false;
1858 CallBase *CB = dyn_cast<CallBase>(I);
1859 if (!CB || !CB->isCallee(&U) ||
1860 !CB->getParent()->getParent()->doesNotRecurse())
1861 return false;
1862 }
1863 F.setDoesNotRecurse();
1864 ++NumNoRecurse;
1865 return true;
1866}
1867
1869 // We only have a post-order SCC traversal (because SCCs are inherently
1870 // discovered in post-order), so we accumulate them in a vector and then walk
1871 // it in reverse. This is simpler than using the RPO iterator infrastructure
1872 // because we need to combine SCC detection and the PO walk of the call
1873 // graph. We can also cheat egregiously because we're primarily interested in
1874 // synthesizing norecurse and so we can only save the singular SCCs as SCCs
1875 // with multiple functions in them will clearly be recursive.
1876
1878 CG.buildRefSCCs();
1879 for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs()) {
1880 for (LazyCallGraph::SCC &SCC : RC) {
1881 if (SCC.size() != 1)
1882 continue;
1883 Function &F = SCC.begin()->getFunction();
1884 if (!F.isDeclaration() && !F.doesNotRecurse() && F.hasInternalLinkage())
1885 Worklist.push_back(&F);
1886 }
1887 }
1888 bool Changed = false;
1889 for (auto *F : llvm::reverse(Worklist))
1890 Changed |= addNoRecurseAttrsTopDown(*F);
1891
1892 return Changed;
1893}
1894
1897 auto &CG = AM.getResult<LazyCallGraphAnalysis>(M);
1898
1899 if (!deduceFunctionAttributeInRPO(M, CG))
1900 return PreservedAnalyses::all();
1901
1904 return PA;
1905}
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
amdgpu Simplify well known AMD library false FunctionCallee Callee
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
SmallPtrSet< MachineInstr *, 2 > Uses
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.
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...
#define LLVM_DEBUG(X)
Definition: Debug.h:101
This file defines the DenseMap class.
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 SmallSet< Function *, 8 > deriveAttrsInPostOrder(ArrayRef< Function * > Functions, AARGetterT &&AARGetter)
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 bool isOrderedAtomic(Instruction *I)
static bool isFunctionMallocLike(Function *F, const SCCNodeSet &SCCNodes)
Tests whether a function is "malloc-like".
static void addArgumentAttrs(const SCCNodeSet &SCCNodes, SmallSet< Function *, 8 > &Changed)
Deduce nocapture attributes for the SCC.
static bool canReturn(Function &F)
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 bool InstrBreaksNonThrowing(Instruction &I, const SCCNodeSet &SCCNodes)
Helper for NoUnwind inference predicate InstrBreaksAttribute.
static bool basicBlockCanReturn(BasicBlock &BB)
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 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 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 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.
IRTranslator LLVM IR MI
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...
print must be executed print the must be executed context for all instructions
FunctionAnalysisManager FAM
This header defines various interfaces for pass management in LLVM.
This builds on the llvm/ADT/GraphTraits.h file to find the strongly connected components (SCCs) of a ...
@ SI
@ VI
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:167
This defines the Use class.
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.
This templated class represents "all analyses that operate over <a particular IR unit>" (e....
Definition: PassManager.h:90
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:620
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:774
This class represents an incoming formal argument to a Function.
Definition: Argument.h:28
void addAttr(Attribute::AttrKind Kind)
Definition: Function.cpp:289
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
AttrKind
This enumeration lists the attributes that can be associated with parameters, function results,...
Definition: Attributes.h:87
@ None
No attributes have been set.
Definition: Attributes.h:89
LLVM Basic Block Representation.
Definition: BasicBlock.h:56
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:112
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:127
Represents analyses that only rely on functions' control flow.
Definition: PassManager.h:113
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1186
bool doesNotCapture(unsigned OpNo) const
Determine whether this data operand is not captured.
Definition: InstrTypes.h:1685
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation or the function signa...
Definition: InstrTypes.h:1408
bool doesNotAccessMemory(unsigned OpNo) const
Definition: InstrTypes.h:1726
bool hasFnAttr(Attribute::AttrKind Kind) const
Determine whether this call has the given attribute.
Definition: InstrTypes.h:1495
bool hasRetAttr(Attribute::AttrKind Kind) const
Determine whether the return value has the given attribute.
Definition: InstrTypes.h:1607
unsigned getDataOperandNo(Value::const_user_iterator UI) const
Given a value use iterator, return the data operand corresponding to it.
Definition: InstrTypes.h:1316
bool dataOperandHasImpliedAttr(unsigned i, Attribute::AttrKind Kind) const
Return true if the data operand at index i has the attribute A.
Definition: InstrTypes.h:1665
bool isCallee(Value::const_user_iterator UI) const
Determine whether the passed iterator points to the callee operand's Use.
Definition: InstrTypes.h:1419
bool onlyReadsMemory(unsigned OpNo) const
Definition: InstrTypes.h:1732
Value * getArgOperand(unsigned i) const
Definition: InstrTypes.h:1353
bool isConvergent() const
Determine if the invoke is convergent.
Definition: InstrTypes.h:1930
unsigned arg_size() const
Definition: InstrTypes.h:1351
bool isArgOperand(const Use *U) const
Definition: InstrTypes.h:1373
bool hasOperandBundles() const
Return true if this User has any operand bundles.
Definition: InstrTypes.h:1964
A node in the call graph for a module.
Definition: CallGraph.h:166
CallGraphSCC - This is a single SCC that a CallGraphSCCPass is run on.
This is an important base class in LLVM.
Definition: Constant.h:41
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:151
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.
bool doesNotRecurse() const
Determine if the function is known not to recurse, directly or indirectly.
Definition: Function.h:592
Function and variable summary information to aid decisions and implementation of importing.
static bool isWeakAnyLinkage(LinkageTypes Linkage)
Definition: GlobalValue.h:386
static bool isLinkOnceAnyLinkage(LinkageTypes Linkage)
Definition: GlobalValue.h:377
static bool isLocalLinkage(LinkageTypes Linkage)
Definition: GlobalValue.h:404
static bool isWeakODRLinkage(LinkageTypes Linkage)
Definition: GlobalValue.h:389
static bool isAvailableExternallyLinkage(LinkageTypes Linkage)
Definition: GlobalValue.h:374
static bool isExternalLinkage(LinkageTypes Linkage)
Definition: GlobalValue.h:371
static bool isLinkOnceODRLinkage(LinkageTypes Linkage)
Definition: GlobalValue.h:380
const BasicBlock * getParent() const
Definition: Instruction.h:90
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:168
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()
Summary of how a function affects memory in the program.
Definition: ModRef.h:63
static MemoryEffects inaccessibleMemOnly(ModRefInfo MR=ModRefInfo::ModRef)
Create MemoryEffects that can only access inaccessible memory.
Definition: ModRef.h:138
bool doesNotAccessMemory() const
Whether this function accesses no memory.
Definition: ModRef.h:191
@ ArgMem
Access to memory via argument pointers.
Definition: ModRef.h:68
@ Other
Any other memory.
Definition: ModRef.h:72
MemoryEffects getWithoutLoc(Location Loc) const
Get new MemoryEffects with NoModRef on the given Loc.
Definition: ModRef.h:176
ModRefInfo getModRef(Location Loc) const
Get ModRefInfo for the given Location.
Definition: ModRef.h:164
static MemoryEffects none()
Create MemoryEffects that cannot read or write any memory.
Definition: ModRef.h:118
static MemoryEffects argMemOnly(ModRefInfo MR=ModRefInfo::ModRef)
Create MemoryEffects that can only access argument memory.
Definition: ModRef.h:133
static MemoryEffects unknown()
Create MemoryEffects that can read and write any memory.
Definition: ModRef.h:113
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: PassManager.h:152
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
void preserveSet()
Mark an analysis set as preserved.
Definition: PassManager.h:188
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:173
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:77
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:141
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:383
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:365
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:301
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:135
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:177
bool empty() const
Definition: SmallVector.h:94
typename SuperClass::iterator iterator
Definition: SmallVector.h:581
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
Value * getOperand(unsigned i) const
Definition: User.h:169
LLVM Value Representation.
Definition: Value.h:74
An efficient, type-erasing, non-owning reference to a callable.
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:48
#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:445
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:226
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:235
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
bool isKnownNonZero(const Value *V, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Return true if the given value is known to be non-zero when defined.
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:1782
MemoryEffects computeFunctionBodyMemoryAccess(Function &F, AAResults &AAR)
Returns the memory access properties of this copy of the function.
auto successors(const MachineBasicBlock *BB)
const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=6)
This method strips off any GEP address adjustments and pointer casts from the specified value,...
scc_iterator< T > scc_begin(const T &G)
Construct the begin iterator for a deduced graph type T.
Definition: SCCIterator.h:232
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:1828
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:495
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:1796
ModRefInfo
Flags indicating whether a memory access modifies or references memory.
Definition: ModRef.h:27
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:2076
bool inferAttributesFromOthers(Function &F)
If we can infer one attribute from another on the declaration of a function, explicitly materialize t...
Definition: Local.cpp:3515
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.
#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:371
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.