LLVM  16.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"
18 #include "llvm/ADT/SCCIterator.h"
19 #include "llvm/ADT/STLExtras.h"
20 #include "llvm/ADT/SetVector.h"
21 #include "llvm/ADT/SmallPtrSet.h"
22 #include "llvm/ADT/SmallSet.h"
23 #include "llvm/ADT/SmallVector.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"
41 #include "llvm/IR/InstIterator.h"
42 #include "llvm/IR/InstrTypes.h"
43 #include "llvm/IR/Instruction.h"
44 #include "llvm/IR/Instructions.h"
45 #include "llvm/IR/IntrinsicInst.h"
46 #include "llvm/IR/Metadata.h"
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"
53 #include "llvm/InitializePasses.h"
54 #include "llvm/Pass.h"
55 #include "llvm/Support/Casting.h"
57 #include "llvm/Support/Compiler.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 
69 using namespace llvm;
70 
71 #define DEBUG_TYPE "function-attrs"
72 
73 STATISTIC(NumMemoryAttr, "Number of functions with improved memory attribute");
74 STATISTIC(NumNoCapture, "Number of arguments marked nocapture");
75 STATISTIC(NumReturned, "Number of arguments marked returned");
76 STATISTIC(NumReadNoneArg, "Number of arguments marked readnone");
77 STATISTIC(NumReadOnlyArg, "Number of arguments marked readonly");
78 STATISTIC(NumWriteOnlyArg, "Number of arguments marked writeonly");
79 STATISTIC(NumNoAlias, "Number of function returns marked noalias");
80 STATISTIC(NumNonNullReturn, "Number of function returns marked nonnull");
81 STATISTIC(NumNoRecurse, "Number of functions marked as norecurse");
82 STATISTIC(NumNoUnwind, "Number of functions marked as nounwind");
83 STATISTIC(NumNoFree, "Number of functions marked as nofree");
84 STATISTIC(NumWillReturn, "Number of functions marked as willreturn");
85 STATISTIC(NumNoSync, "Number of functions marked as nosync");
86 
87 STATISTIC(NumThinLinkNoRecurse,
88  "Number of functions marked as norecurse during thinlink");
89 STATISTIC(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 
109 namespace {
110 
111 using 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))
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)) {
150  ME |= MemoryEffects::argMemOnly(MR);
151  return;
152  }
153 
154  // If it's not an identified object, it might be an argument.
155  if (!isIdentifiedObject(UO))
156  ME |= MemoryEffects::argMemOnly(MR);
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 
184  ME |= CallME.getWithoutLoc(MemoryEffects::ArgMem);
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 
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.
239 template <typename AARGetterT>
240 static 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) {
333  LLVM_DEBUG(
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 
455 namespace {
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.
460 struct ArgumentGraphNode {
461  Argument *Definition;
463 };
464 
465 class 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 
480 public:
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.
500 struct 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 
512  Function *F = CB->getCalledFunction();
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 
553 namespace llvm {
554 
555 template <> 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 
564 template <>
565 struct 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.
578 static Attribute::AttrKind
580  const SmallPtrSet<Argument *, 8> &SCCNodes) {
581  SmallVector<Use *, 32> Worklist;
582  SmallPtrSet<Use *, 32> Visited;
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.
712 static 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 (llvm::any_of(F->args(),
727  [](const Argument &Arg) { return Arg.hasReturnedAttr(); }))
728  continue;
729 
730  auto FindRetArg = [&]() -> Value * {
731  Value *RetArg = nullptr;
732  for (BasicBlock &BB : *F)
733  if (auto *Ret = dyn_cast<ReturnInst>(BB.getTerminator())) {
734  // Note that stripPointerCasts should look through functions with
735  // returned arguments.
736  Value *RetVal = Ret->getReturnValue()->stripPointerCasts();
737  if (!isa<Argument>(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 (Value *RetArg = FindRetArg()) {
750  auto *A = cast<Argument>(RetArg);
751  A->addAttr(Attribute::Returned);
752  ++NumReturned;
753  Changed.insert(F);
754  }
755  }
756 }
757 
758 /// If a callsite has arguments that are also arguments to the parent function,
759 /// try to propagate attributes from the callsite's arguments to the parent's
760 /// arguments. This may be important because inlining can cause information loss
761 /// when attribute knowledge disappears with the inlined call.
764  return false;
765 
766  bool Changed = false;
767 
768  // For an argument attribute to transfer from a callsite to the parent, the
769  // call must be guaranteed to execute every time the parent is called.
770  // Conservatively, just check for calls in the entry block that are guaranteed
771  // to execute.
772  // TODO: This could be enhanced by testing if the callsite post-dominates the
773  // entry block or by doing simple forward walks or backward walks to the
774  // callsite.
775  BasicBlock &Entry = F.getEntryBlock();
776  for (Instruction &I : Entry) {
777  if (auto *CB = dyn_cast<CallBase>(&I)) {
778  if (auto *CalledFunc = CB->getCalledFunction()) {
779  for (auto &CSArg : CalledFunc->args()) {
780  if (!CSArg.hasNonNullAttr(/* AllowUndefOrPoison */ false))
781  continue;
782 
783  // If the non-null callsite argument operand is an argument to 'F'
784  // (the caller) and the call is guaranteed to execute, then the value
785  // must be non-null throughout 'F'.
786  auto *FArg = dyn_cast<Argument>(CB->getArgOperand(CSArg.getArgNo()));
787  if (FArg && !FArg->hasNonNullAttr()) {
788  FArg->addAttr(Attribute::NonNull);
789  Changed = true;
790  }
791  }
792  }
793  }
795  break;
796  }
797 
798  return Changed;
799 }
800 
802  assert((R == Attribute::ReadOnly || R == Attribute::ReadNone ||
803  R == Attribute::WriteOnly)
804  && "Must be an access attribute.");
805  assert(A && "Argument must not be null.");
806 
807  // If the argument already has the attribute, nothing needs to be done.
808  if (A->hasAttribute(R))
809  return false;
810 
811  // Otherwise, remove potentially conflicting attribute, add the new one,
812  // and update statistics.
813  A->removeAttr(Attribute::WriteOnly);
814  A->removeAttr(Attribute::ReadOnly);
815  A->removeAttr(Attribute::ReadNone);
816  A->addAttr(R);
817  if (R == Attribute::ReadOnly)
818  ++NumReadOnlyArg;
819  else if (R == Attribute::WriteOnly)
820  ++NumWriteOnlyArg;
821  else
822  ++NumReadNoneArg;
823  return true;
824 }
825 
826 /// Deduce nocapture attributes for the SCC.
827 static void addArgumentAttrs(const SCCNodeSet &SCCNodes,
828  SmallSet<Function *, 8> &Changed) {
829  ArgumentGraph AG;
830 
831  // Check each function in turn, determining which pointer arguments are not
832  // captured.
833  for (Function *F : SCCNodes) {
834  // We can infer and propagate function attributes only when we know that the
835  // definition we'll get at link time is *exactly* the definition we see now.
836  // For more details, see GlobalValue::mayBeDerefined.
837  if (!F->hasExactDefinition())
838  continue;
839 
841  Changed.insert(F);
842 
843  // Functions that are readonly (or readnone) and nounwind and don't return
844  // a value can't capture arguments. Don't analyze them.
845  if (F->onlyReadsMemory() && F->doesNotThrow() &&
846  F->getReturnType()->isVoidTy()) {
847  for (Argument &A : F->args()) {
848  if (A.getType()->isPointerTy() && !A.hasNoCaptureAttr()) {
849  A.addAttr(Attribute::NoCapture);
850  ++NumNoCapture;
851  Changed.insert(F);
852  }
853  }
854  continue;
855  }
856 
857  for (Argument &A : F->args()) {
858  if (!A.getType()->isPointerTy())
859  continue;
860  bool HasNonLocalUses = false;
861  if (!A.hasNoCaptureAttr()) {
862  ArgumentUsesTracker Tracker(SCCNodes);
863  PointerMayBeCaptured(&A, &Tracker);
864  if (!Tracker.Captured) {
865  if (Tracker.Uses.empty()) {
866  // If it's trivially not captured, mark it nocapture now.
867  A.addAttr(Attribute::NoCapture);
868  ++NumNoCapture;
869  Changed.insert(F);
870  } else {
871  // If it's not trivially captured and not trivially not captured,
872  // then it must be calling into another function in our SCC. Save
873  // its particulars for Argument-SCC analysis later.
874  ArgumentGraphNode *Node = AG[&A];
875  for (Argument *Use : Tracker.Uses) {
876  Node->Uses.push_back(AG[Use]);
877  if (Use != &A)
878  HasNonLocalUses = true;
879  }
880  }
881  }
882  // Otherwise, it's captured. Don't bother doing SCC analysis on it.
883  }
884  if (!HasNonLocalUses && !A.onlyReadsMemory()) {
885  // Can we determine that it's readonly/readnone/writeonly without doing
886  // an SCC? Note that we don't allow any calls at all here, or else our
887  // result will be dependent on the iteration order through the
888  // functions in the SCC.
890  Self.insert(&A);
892  if (R != Attribute::None)
893  if (addAccessAttr(&A, R))
894  Changed.insert(F);
895  }
896  }
897  }
898 
899  // The graph we've collected is partial because we stopped scanning for
900  // argument uses once we solved the argument trivially. These partial nodes
901  // show up as ArgumentGraphNode objects with an empty Uses list, and for
902  // these nodes the final decision about whether they capture has already been
903  // made. If the definition doesn't have a 'nocapture' attribute by now, it
904  // captures.
905 
906  for (scc_iterator<ArgumentGraph *> I = scc_begin(&AG); !I.isAtEnd(); ++I) {
907  const std::vector<ArgumentGraphNode *> &ArgumentSCC = *I;
908  if (ArgumentSCC.size() == 1) {
909  if (!ArgumentSCC[0]->Definition)
910  continue; // synthetic root node
911 
912  // eg. "void f(int* x) { if (...) f(x); }"
913  if (ArgumentSCC[0]->Uses.size() == 1 &&
914  ArgumentSCC[0]->Uses[0] == ArgumentSCC[0]) {
915  Argument *A = ArgumentSCC[0]->Definition;
916  A->addAttr(Attribute::NoCapture);
917  ++NumNoCapture;
918  Changed.insert(A->getParent());
919 
920  // Infer the access attributes given the new nocapture one
922  Self.insert(&*A);
924  if (R != Attribute::None)
925  addAccessAttr(A, R);
926  }
927  continue;
928  }
929 
930  bool SCCCaptured = false;
931  for (ArgumentGraphNode *Node : ArgumentSCC) {
932  if (Node->Uses.empty() && !Node->Definition->hasNoCaptureAttr()) {
933  SCCCaptured = true;
934  break;
935  }
936  }
937  if (SCCCaptured)
938  continue;
939 
940  SmallPtrSet<Argument *, 8> ArgumentSCCNodes;
941  // Fill ArgumentSCCNodes with the elements of the ArgumentSCC. Used for
942  // quickly looking up whether a given Argument is in this ArgumentSCC.
943  for (ArgumentGraphNode *I : ArgumentSCC) {
944  ArgumentSCCNodes.insert(I->Definition);
945  }
946 
947  for (ArgumentGraphNode *N : ArgumentSCC) {
948  for (ArgumentGraphNode *Use : N->Uses) {
949  Argument *A = Use->Definition;
950  if (A->hasNoCaptureAttr() || ArgumentSCCNodes.count(A))
951  continue;
952  SCCCaptured = true;
953  break;
954  }
955  if (SCCCaptured)
956  break;
957  }
958  if (SCCCaptured)
959  continue;
960 
961  for (ArgumentGraphNode *N : ArgumentSCC) {
962  Argument *A = N->Definition;
963  A->addAttr(Attribute::NoCapture);
964  ++NumNoCapture;
965  Changed.insert(A->getParent());
966  }
967 
968  // We also want to compute readonly/readnone/writeonly. With a small number
969  // of false negatives, we can assume that any pointer which is captured
970  // isn't going to be provably readonly or readnone, since by definition
971  // we can't analyze all uses of a captured pointer.
972  //
973  // The false negatives happen when the pointer is captured by a function
974  // that promises readonly/readnone behaviour on the pointer, then the
975  // pointer's lifetime ends before anything that writes to arbitrary memory.
976  // Also, a readonly/readnone pointer may be returned, but returning a
977  // pointer is capturing it.
978 
979  auto meetAccessAttr = [](Attribute::AttrKind A, Attribute::AttrKind B) {
980  if (A == B)
981  return A;
982  if (A == Attribute::ReadNone)
983  return B;
984  if (B == Attribute::ReadNone)
985  return A;
986  return Attribute::None;
987  };
988 
989  Attribute::AttrKind AccessAttr = Attribute::ReadNone;
990  for (ArgumentGraphNode *N : ArgumentSCC) {
991  Argument *A = N->Definition;
992  Attribute::AttrKind K = determinePointerAccessAttrs(A, ArgumentSCCNodes);
993  AccessAttr = meetAccessAttr(AccessAttr, K);
994  if (AccessAttr == Attribute::None)
995  break;
996  }
997 
998  if (AccessAttr != Attribute::None) {
999  for (ArgumentGraphNode *N : ArgumentSCC) {
1000  Argument *A = N->Definition;
1001  if (addAccessAttr(A, AccessAttr))
1002  Changed.insert(A->getParent());
1003  }
1004  }
1005  }
1006 }
1007 
1008 /// Tests whether a function is "malloc-like".
1009 ///
1010 /// A function is "malloc-like" if it returns either null or a pointer that
1011 /// doesn't alias any other pointer visible to the caller.
1012 static bool isFunctionMallocLike(Function *F, const SCCNodeSet &SCCNodes) {
1013  SmallSetVector<Value *, 8> FlowsToReturn;
1014  for (BasicBlock &BB : *F)
1015  if (ReturnInst *Ret = dyn_cast<ReturnInst>(BB.getTerminator()))
1016  FlowsToReturn.insert(Ret->getReturnValue());
1017 
1018  for (unsigned i = 0; i != FlowsToReturn.size(); ++i) {
1019  Value *RetVal = FlowsToReturn[i];
1020 
1021  if (Constant *C = dyn_cast<Constant>(RetVal)) {
1022  if (!C->isNullValue() && !isa<UndefValue>(C))
1023  return false;
1024 
1025  continue;
1026  }
1027 
1028  if (isa<Argument>(RetVal))
1029  return false;
1030 
1031  if (Instruction *RVI = dyn_cast<Instruction>(RetVal))
1032  switch (RVI->getOpcode()) {
1033  // Extend the analysis by looking upwards.
1034  case Instruction::BitCast:
1035  case Instruction::GetElementPtr:
1036  case Instruction::AddrSpaceCast:
1037  FlowsToReturn.insert(RVI->getOperand(0));
1038  continue;
1039  case Instruction::Select: {
1040  SelectInst *SI = cast<SelectInst>(RVI);
1041  FlowsToReturn.insert(SI->getTrueValue());
1042  FlowsToReturn.insert(SI->getFalseValue());
1043  continue;
1044  }
1045  case Instruction::PHI: {
1046  PHINode *PN = cast<PHINode>(RVI);
1047  for (Value *IncValue : PN->incoming_values())
1048  FlowsToReturn.insert(IncValue);
1049  continue;
1050  }
1051 
1052  // Check whether the pointer came from an allocation.
1053  case Instruction::Alloca:
1054  break;
1055  case Instruction::Call:
1056  case Instruction::Invoke: {
1057  CallBase &CB = cast<CallBase>(*RVI);
1058  if (CB.hasRetAttr(Attribute::NoAlias))
1059  break;
1060  if (CB.getCalledFunction() && SCCNodes.count(CB.getCalledFunction()))
1061  break;
1062  [[fallthrough]];
1063  }
1064  default:
1065  return false; // Did not come from an allocation.
1066  }
1067 
1068  if (PointerMayBeCaptured(RetVal, false, /*StoreCaptures=*/false))
1069  return false;
1070  }
1071 
1072  return true;
1073 }
1074 
1075 /// Deduce noalias attributes for the SCC.
1076 static void addNoAliasAttrs(const SCCNodeSet &SCCNodes,
1077  SmallSet<Function *, 8> &Changed) {
1078  // Check each function in turn, determining which functions return noalias
1079  // pointers.
1080  for (Function *F : SCCNodes) {
1081  // Already noalias.
1082  if (F->returnDoesNotAlias())
1083  continue;
1084 
1085  // We can infer and propagate function attributes only when we know that the
1086  // definition we'll get at link time is *exactly* the definition we see now.
1087  // For more details, see GlobalValue::mayBeDerefined.
1088  if (!F->hasExactDefinition())
1089  return;
1090 
1091  // We annotate noalias return values, which are only applicable to
1092  // pointer types.
1093  if (!F->getReturnType()->isPointerTy())
1094  continue;
1095 
1096  if (!isFunctionMallocLike(F, SCCNodes))
1097  return;
1098  }
1099 
1100  for (Function *F : SCCNodes) {
1101  if (F->returnDoesNotAlias() ||
1102  !F->getReturnType()->isPointerTy())
1103  continue;
1104 
1105  F->setReturnDoesNotAlias();
1106  ++NumNoAlias;
1107  Changed.insert(F);
1108  }
1109 }
1110 
1111 /// Tests whether this function is known to not return null.
1112 ///
1113 /// Requires that the function returns a pointer.
1114 ///
1115 /// Returns true if it believes the function will not return a null, and sets
1116 /// \p Speculative based on whether the returned conclusion is a speculative
1117 /// conclusion due to SCC calls.
1118 static bool isReturnNonNull(Function *F, const SCCNodeSet &SCCNodes,
1119  bool &Speculative) {
1120  assert(F->getReturnType()->isPointerTy() &&
1121  "nonnull only meaningful on pointer types");
1122  Speculative = false;
1123 
1124  SmallSetVector<Value *, 8> FlowsToReturn;
1125  for (BasicBlock &BB : *F)
1126  if (auto *Ret = dyn_cast<ReturnInst>(BB.getTerminator()))
1127  FlowsToReturn.insert(Ret->getReturnValue());
1128 
1129  auto &DL = F->getParent()->getDataLayout();
1130 
1131  for (unsigned i = 0; i != FlowsToReturn.size(); ++i) {
1132  Value *RetVal = FlowsToReturn[i];
1133 
1134  // If this value is locally known to be non-null, we're good
1135  if (isKnownNonZero(RetVal, DL))
1136  continue;
1137 
1138  // Otherwise, we need to look upwards since we can't make any local
1139  // conclusions.
1140  Instruction *RVI = dyn_cast<Instruction>(RetVal);
1141  if (!RVI)
1142  return false;
1143  switch (RVI->getOpcode()) {
1144  // Extend the analysis by looking upwards.
1145  case Instruction::BitCast:
1146  case Instruction::GetElementPtr:
1147  case Instruction::AddrSpaceCast:
1148  FlowsToReturn.insert(RVI->getOperand(0));
1149  continue;
1150  case Instruction::Select: {
1151  SelectInst *SI = cast<SelectInst>(RVI);
1152  FlowsToReturn.insert(SI->getTrueValue());
1153  FlowsToReturn.insert(SI->getFalseValue());
1154  continue;
1155  }
1156  case Instruction::PHI: {
1157  PHINode *PN = cast<PHINode>(RVI);
1158  for (int i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
1159  FlowsToReturn.insert(PN->getIncomingValue(i));
1160  continue;
1161  }
1162  case Instruction::Call:
1163  case Instruction::Invoke: {
1164  CallBase &CB = cast<CallBase>(*RVI);
1166  // A call to a node within the SCC is assumed to return null until
1167  // proven otherwise
1168  if (Callee && SCCNodes.count(Callee)) {
1169  Speculative = true;
1170  continue;
1171  }
1172  return false;
1173  }
1174  default:
1175  return false; // Unknown source, may be null
1176  };
1177  llvm_unreachable("should have either continued or returned");
1178  }
1179 
1180  return true;
1181 }
1182 
1183 /// Deduce nonnull attributes for the SCC.
1184 static void addNonNullAttrs(const SCCNodeSet &SCCNodes,
1185  SmallSet<Function *, 8> &Changed) {
1186  // Speculative that all functions in the SCC return only nonnull
1187  // pointers. We may refute this as we analyze functions.
1188  bool SCCReturnsNonNull = true;
1189 
1190  // Check each function in turn, determining which functions return nonnull
1191  // pointers.
1192  for (Function *F : SCCNodes) {
1193  // Already nonnull.
1194  if (F->getAttributes().hasRetAttr(Attribute::NonNull))
1195  continue;
1196 
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  return;
1202 
1203  // We annotate nonnull return values, which are only applicable to
1204  // pointer types.
1205  if (!F->getReturnType()->isPointerTy())
1206  continue;
1207 
1208  bool Speculative = false;
1209  if (isReturnNonNull(F, SCCNodes, Speculative)) {
1210  if (!Speculative) {
1211  // Mark the function eagerly since we may discover a function
1212  // which prevents us from speculating about the entire SCC
1213  LLVM_DEBUG(dbgs() << "Eagerly marking " << F->getName()
1214  << " as nonnull\n");
1215  F->addRetAttr(Attribute::NonNull);
1216  ++NumNonNullReturn;
1217  Changed.insert(F);
1218  }
1219  continue;
1220  }
1221  // At least one function returns something which could be null, can't
1222  // speculate any more.
1223  SCCReturnsNonNull = false;
1224  }
1225 
1226  if (SCCReturnsNonNull) {
1227  for (Function *F : SCCNodes) {
1228  if (F->getAttributes().hasRetAttr(Attribute::NonNull) ||
1229  !F->getReturnType()->isPointerTy())
1230  continue;
1231 
1232  LLVM_DEBUG(dbgs() << "SCC marking " << F->getName() << " as nonnull\n");
1233  F->addRetAttr(Attribute::NonNull);
1234  ++NumNonNullReturn;
1235  Changed.insert(F);
1236  }
1237  }
1238 }
1239 
1240 namespace {
1241 
1242 /// Collects a set of attribute inference requests and performs them all in one
1243 /// go on a single SCC Node. Inference involves scanning function bodies
1244 /// looking for instructions that violate attribute assumptions.
1245 /// As soon as all the bodies are fine we are free to set the attribute.
1246 /// Customization of inference for individual attributes is performed by
1247 /// providing a handful of predicates for each attribute.
1248 class AttributeInferer {
1249 public:
1250  /// Describes a request for inference of a single attribute.
1251  struct InferenceDescriptor {
1252 
1253  /// Returns true if this function does not have to be handled.
1254  /// General intent for this predicate is to provide an optimization
1255  /// for functions that do not need this attribute inference at all
1256  /// (say, for functions that already have the attribute).
1257  std::function<bool(const Function &)> SkipFunction;
1258 
1259  /// Returns true if this instruction violates attribute assumptions.
1260  std::function<bool(Instruction &)> InstrBreaksAttribute;
1261 
1262  /// Sets the inferred attribute for this function.
1263  std::function<void(Function &)> SetAttribute;
1264 
1265  /// Attribute we derive.
1266  Attribute::AttrKind AKind;
1267 
1268  /// If true, only "exact" definitions can be used to infer this attribute.
1269  /// See GlobalValue::isDefinitionExact.
1270  bool RequiresExactDefinition;
1271 
1272  InferenceDescriptor(Attribute::AttrKind AK,
1273  std::function<bool(const Function &)> SkipFunc,
1274  std::function<bool(Instruction &)> InstrScan,
1275  std::function<void(Function &)> SetAttr,
1276  bool ReqExactDef)
1277  : SkipFunction(SkipFunc), InstrBreaksAttribute(InstrScan),
1278  SetAttribute(SetAttr), AKind(AK),
1279  RequiresExactDefinition(ReqExactDef) {}
1280  };
1281 
1282 private:
1283  SmallVector<InferenceDescriptor, 4> InferenceDescriptors;
1284 
1285 public:
1286  void registerAttrInference(InferenceDescriptor AttrInference) {
1287  InferenceDescriptors.push_back(AttrInference);
1288  }
1289 
1290  void run(const SCCNodeSet &SCCNodes, SmallSet<Function *, 8> &Changed);
1291 };
1292 
1293 /// Perform all the requested attribute inference actions according to the
1294 /// attribute predicates stored before.
1295 void AttributeInferer::run(const SCCNodeSet &SCCNodes,
1296  SmallSet<Function *, 8> &Changed) {
1297  SmallVector<InferenceDescriptor, 4> InferInSCC = InferenceDescriptors;
1298  // Go through all the functions in SCC and check corresponding attribute
1299  // assumptions for each of them. Attributes that are invalid for this SCC
1300  // will be removed from InferInSCC.
1301  for (Function *F : SCCNodes) {
1302 
1303  // No attributes whose assumptions are still valid - done.
1304  if (InferInSCC.empty())
1305  return;
1306 
1307  // Check if our attributes ever need scanning/can be scanned.
1308  llvm::erase_if(InferInSCC, [F](const InferenceDescriptor &ID) {
1309  if (ID.SkipFunction(*F))
1310  return false;
1311 
1312  // Remove from further inference (invalidate) when visiting a function
1313  // that has no instructions to scan/has an unsuitable definition.
1314  return F->isDeclaration() ||
1315  (ID.RequiresExactDefinition && !F->hasExactDefinition());
1316  });
1317 
1318  // For each attribute still in InferInSCC that doesn't explicitly skip F,
1319  // set up the F instructions scan to verify assumptions of the attribute.
1320  SmallVector<InferenceDescriptor, 4> InferInThisFunc;
1321  llvm::copy_if(
1322  InferInSCC, std::back_inserter(InferInThisFunc),
1323  [F](const InferenceDescriptor &ID) { return !ID.SkipFunction(*F); });
1324 
1325  if (InferInThisFunc.empty())
1326  continue;
1327 
1328  // Start instruction scan.
1329  for (Instruction &I : instructions(*F)) {
1330  llvm::erase_if(InferInThisFunc, [&](const InferenceDescriptor &ID) {
1331  if (!ID.InstrBreaksAttribute(I))
1332  return false;
1333  // Remove attribute from further inference on any other functions
1334  // because attribute assumptions have just been violated.
1335  llvm::erase_if(InferInSCC, [&ID](const InferenceDescriptor &D) {
1336  return D.AKind == ID.AKind;
1337  });
1338  // Remove attribute from the rest of current instruction scan.
1339  return true;
1340  });
1341 
1342  if (InferInThisFunc.empty())
1343  break;
1344  }
1345  }
1346 
1347  if (InferInSCC.empty())
1348  return;
1349 
1350  for (Function *F : SCCNodes)
1351  // At this point InferInSCC contains only functions that were either:
1352  // - explicitly skipped from scan/inference, or
1353  // - verified to have no instructions that break attribute assumptions.
1354  // Hence we just go and force the attribute for all non-skipped functions.
1355  for (auto &ID : InferInSCC) {
1356  if (ID.SkipFunction(*F))
1357  continue;
1358  Changed.insert(F);
1359  ID.SetAttribute(*F);
1360  }
1361 }
1362 
1363 struct SCCNodesResult {
1364  SCCNodeSet SCCNodes;
1365  bool HasUnknownCall;
1366 };
1367 
1368 } // end anonymous namespace
1369 
1370 /// Helper for non-Convergent inference predicate InstrBreaksAttribute.
1372  const SCCNodeSet &SCCNodes) {
1373  const CallBase *CB = dyn_cast<CallBase>(&I);
1374  // Breaks non-convergent assumption if CS is a convergent call to a function
1375  // not in the SCC.
1376  return CB && CB->isConvergent() &&
1377  !SCCNodes.contains(CB->getCalledFunction());
1378 }
1379 
1380 /// Helper for NoUnwind inference predicate InstrBreaksAttribute.
1381 static bool InstrBreaksNonThrowing(Instruction &I, const SCCNodeSet &SCCNodes) {
1382  if (!I.mayThrow())
1383  return false;
1384  if (const auto *CI = dyn_cast<CallInst>(&I)) {
1385  if (Function *Callee = CI->getCalledFunction()) {
1386  // I is a may-throw call to a function inside our SCC. This doesn't
1387  // invalidate our current working assumption that the SCC is no-throw; we
1388  // just have to scan that other function.
1389  if (SCCNodes.contains(Callee))
1390  return false;
1391  }
1392  }
1393  return true;
1394 }
1395 
1396 /// Helper for NoFree inference predicate InstrBreaksAttribute.
1397 static bool InstrBreaksNoFree(Instruction &I, const SCCNodeSet &SCCNodes) {
1398  CallBase *CB = dyn_cast<CallBase>(&I);
1399  if (!CB)
1400  return false;
1401 
1402  if (CB->hasFnAttr(Attribute::NoFree))
1403  return false;
1404 
1405  // Speculatively assume in SCC.
1406  if (Function *Callee = CB->getCalledFunction())
1407  if (SCCNodes.contains(Callee))
1408  return false;
1409 
1410  return true;
1411 }
1412 
1413 /// Attempt to remove convergent function attribute when possible.
1414 ///
1415 /// Returns true if any changes to function attributes were made.
1416 static void inferConvergent(const SCCNodeSet &SCCNodes,
1417  SmallSet<Function *, 8> &Changed) {
1418  AttributeInferer AI;
1419 
1420  // Request to remove the convergent attribute from all functions in the SCC
1421  // if every callsite within the SCC is not convergent (except for calls
1422  // to functions within the SCC).
1423  // Note: Removal of the attr from the callsites will happen in
1424  // InstCombineCalls separately.
1425  AI.registerAttrInference(AttributeInferer::InferenceDescriptor{
1427  // Skip non-convergent functions.
1428  [](const Function &F) { return !F.isConvergent(); },
1429  // Instructions that break non-convergent assumption.
1430  [SCCNodes](Instruction &I) {
1431  return InstrBreaksNonConvergent(I, SCCNodes);
1432  },
1433  [](Function &F) {
1434  LLVM_DEBUG(dbgs() << "Removing convergent attr from fn " << F.getName()
1435  << "\n");
1436  F.setNotConvergent();
1437  },
1438  /* RequiresExactDefinition= */ false});
1439  // Perform all the requested attribute inference actions.
1440  AI.run(SCCNodes, Changed);
1441 }
1442 
1443 /// Infer attributes from all functions in the SCC by scanning every
1444 /// instruction for compliance to the attribute assumptions. Currently it
1445 /// does:
1446 /// - addition of NoUnwind attribute
1447 ///
1448 /// Returns true if any changes to function attributes were made.
1449 static void inferAttrsFromFunctionBodies(const SCCNodeSet &SCCNodes,
1450  SmallSet<Function *, 8> &Changed) {
1451  AttributeInferer AI;
1452 
1454  // Request to infer nounwind attribute for all the functions in the SCC if
1455  // every callsite within the SCC is not throwing (except for calls to
1456  // functions within the SCC). Note that nounwind attribute suffers from
1457  // derefinement - results may change depending on how functions are
1458  // optimized. Thus it can be inferred only from exact definitions.
1459  AI.registerAttrInference(AttributeInferer::InferenceDescriptor{
1460  Attribute::NoUnwind,
1461  // Skip non-throwing functions.
1462  [](const Function &F) { return F.doesNotThrow(); },
1463  // Instructions that break non-throwing assumption.
1464  [&SCCNodes](Instruction &I) {
1465  return InstrBreaksNonThrowing(I, SCCNodes);
1466  },
1467  [](Function &F) {
1468  LLVM_DEBUG(dbgs()
1469  << "Adding nounwind attr to fn " << F.getName() << "\n");
1470  F.setDoesNotThrow();
1471  ++NumNoUnwind;
1472  },
1473  /* RequiresExactDefinition= */ true});
1474 
1476  // Request to infer nofree attribute for all the functions in the SCC if
1477  // every callsite within the SCC does not directly or indirectly free
1478  // memory (except for calls to functions within the SCC). Note that nofree
1479  // attribute suffers from derefinement - results may change depending on
1480  // how functions are optimized. Thus it can be inferred only from exact
1481  // definitions.
1482  AI.registerAttrInference(AttributeInferer::InferenceDescriptor{
1483  Attribute::NoFree,
1484  // Skip functions known not to free memory.
1485  [](const Function &F) { return F.doesNotFreeMemory(); },
1486  // Instructions that break non-deallocating assumption.
1487  [&SCCNodes](Instruction &I) {
1488  return InstrBreaksNoFree(I, SCCNodes);
1489  },
1490  [](Function &F) {
1491  LLVM_DEBUG(dbgs()
1492  << "Adding nofree attr to fn " << F.getName() << "\n");
1493  F.setDoesNotFreeMemory();
1494  ++NumNoFree;
1495  },
1496  /* RequiresExactDefinition= */ true});
1497 
1498  // Perform all the requested attribute inference actions.
1499  AI.run(SCCNodes, Changed);
1500 }
1501 
1502 static void addNoRecurseAttrs(const SCCNodeSet &SCCNodes,
1503  SmallSet<Function *, 8> &Changed) {
1504  // Try and identify functions that do not recurse.
1505 
1506  // If the SCC contains multiple nodes we know for sure there is recursion.
1507  if (SCCNodes.size() != 1)
1508  return;
1509 
1510  Function *F = *SCCNodes.begin();
1511  if (!F || !F->hasExactDefinition() || F->doesNotRecurse())
1512  return;
1513 
1514  // If all of the calls in F are identifiable and are to norecurse functions, F
1515  // is norecurse. This check also detects self-recursion as F is not currently
1516  // marked norecurse, so any called from F to F will not be marked norecurse.
1517  for (auto &BB : *F)
1518  for (auto &I : BB.instructionsWithoutDebug())
1519  if (auto *CB = dyn_cast<CallBase>(&I)) {
1521  if (!Callee || Callee == F || !Callee->doesNotRecurse())
1522  // Function calls a potentially recursive function.
1523  return;
1524  }
1525 
1526  // Every call was to a non-recursive function other than this function, and
1527  // we have no indirect recursion as the SCC size is one. This function cannot
1528  // recurse.
1529  F->setDoesNotRecurse();
1530  ++NumNoRecurse;
1531  Changed.insert(F);
1532 }
1533 
1535  if (auto *CB = dyn_cast<CallBase>(&I))
1536  return CB->hasFnAttr(Attribute::NoReturn);
1537  return false;
1538 }
1539 
1540 // A basic block can only return if it terminates with a ReturnInst and does not
1541 // contain calls to noreturn functions.
1543  if (!isa<ReturnInst>(BB.getTerminator()))
1544  return false;
1546 }
1547 
1548 // FIXME: this doesn't handle recursion.
1549 static bool canReturn(Function &F) {
1552 
1553  Visited.insert(&F.front());
1554  Worklist.push_back(&F.front());
1555 
1556  do {
1557  BasicBlock *BB = Worklist.pop_back_val();
1558  if (basicBlockCanReturn(*BB))
1559  return true;
1560  for (BasicBlock *Succ : successors(BB))
1561  if (Visited.insert(Succ).second)
1562  Worklist.push_back(Succ);
1563  } while (!Worklist.empty());
1564 
1565  return false;
1566 }
1567 
1568 // Set the noreturn function attribute if possible.
1569 static void addNoReturnAttrs(const SCCNodeSet &SCCNodes,
1570  SmallSet<Function *, 8> &Changed) {
1571  for (Function *F : SCCNodes) {
1572  if (!F || !F->hasExactDefinition() || F->hasFnAttribute(Attribute::Naked) ||
1573  F->doesNotReturn())
1574  continue;
1575 
1576  if (!canReturn(*F)) {
1577  F->setDoesNotReturn();
1578  Changed.insert(F);
1579  }
1580  }
1581 }
1582 
1583 static bool functionWillReturn(const Function &F) {
1584  // We can infer and propagate function attributes only when we know that the
1585  // definition we'll get at link time is *exactly* the definition we see now.
1586  // For more details, see GlobalValue::mayBeDerefined.
1587  if (!F.hasExactDefinition())
1588  return false;
1589 
1590  // Must-progress function without side-effects must return.
1591  if (F.mustProgress() && F.onlyReadsMemory())
1592  return true;
1593 
1594  // Can only analyze functions with a definition.
1595  if (F.isDeclaration())
1596  return false;
1597 
1598  // Functions with loops require more sophisticated analysis, as the loop
1599  // may be infinite. For now, don't try to handle them.
1601  FindFunctionBackedges(F, Backedges);
1602  if (!Backedges.empty())
1603  return false;
1604 
1605  // If there are no loops, then the function is willreturn if all calls in
1606  // it are willreturn.
1607  return all_of(instructions(F), [](const Instruction &I) {
1608  return I.willReturn();
1609  });
1610 }
1611 
1612 // Set the willreturn function attribute if possible.
1613 static void addWillReturn(const SCCNodeSet &SCCNodes,
1614  SmallSet<Function *, 8> &Changed) {
1615  for (Function *F : SCCNodes) {
1616  if (!F || F->willReturn() || !functionWillReturn(*F))
1617  continue;
1618 
1619  F->setWillReturn();
1620  NumWillReturn++;
1621  Changed.insert(F);
1622  }
1623 }
1624 
1625 // Return true if this is an atomic which has an ordering stronger than
1626 // unordered. Note that this is different than the predicate we use in
1627 // Attributor. Here we chose to be conservative and consider monotonic
1628 // operations potentially synchronizing. We generally don't do much with
1629 // monotonic operations, so this is simply risk reduction.
1631  if (!I->isAtomic())
1632  return false;
1633 
1634  if (auto *FI = dyn_cast<FenceInst>(I))
1635  // All legal orderings for fence are stronger than monotonic.
1636  return FI->getSyncScopeID() != SyncScope::SingleThread;
1637  else if (isa<AtomicCmpXchgInst>(I) || isa<AtomicRMWInst>(I))
1638  return true;
1639  else if (auto *SI = dyn_cast<StoreInst>(I))
1640  return !SI->isUnordered();
1641  else if (auto *LI = dyn_cast<LoadInst>(I))
1642  return !LI->isUnordered();
1643  else {
1644  llvm_unreachable("unknown atomic instruction?");
1645  }
1646 }
1647 
1648 static bool InstrBreaksNoSync(Instruction &I, const SCCNodeSet &SCCNodes) {
1649  // Volatile may synchronize
1650  if (I.isVolatile())
1651  return true;
1652 
1653  // An ordered atomic may synchronize. (See comment about on monotonic.)
1654  if (isOrderedAtomic(&I))
1655  return true;
1656 
1657  auto *CB = dyn_cast<CallBase>(&I);
1658  if (!CB)
1659  // Non call site cases covered by the two checks above
1660  return false;
1661 
1662  if (CB->hasFnAttr(Attribute::NoSync))
1663  return false;
1664 
1665  // Non volatile memset/memcpy/memmoves are nosync
1666  // NOTE: Only intrinsics with volatile flags should be handled here. All
1667  // others should be marked in Intrinsics.td.
1668  if (auto *MI = dyn_cast<MemIntrinsic>(&I))
1669  if (!MI->isVolatile())
1670  return false;
1671 
1672  // Speculatively assume in SCC.
1673  if (Function *Callee = CB->getCalledFunction())
1674  if (SCCNodes.contains(Callee))
1675  return false;
1676 
1677  return true;
1678 }
1679 
1680 // Infer the nosync attribute.
1681 static void addNoSyncAttr(const SCCNodeSet &SCCNodes,
1682  SmallSet<Function *, 8> &Changed) {
1683  AttributeInferer AI;
1684  AI.registerAttrInference(AttributeInferer::InferenceDescriptor{
1685  Attribute::NoSync,
1686  // Skip already marked functions.
1687  [](const Function &F) { return F.hasNoSync(); },
1688  // Instructions that break nosync assumption.
1689  [&SCCNodes](Instruction &I) {
1690  return InstrBreaksNoSync(I, SCCNodes);
1691  },
1692  [](Function &F) {
1693  LLVM_DEBUG(dbgs()
1694  << "Adding nosync attr to fn " << F.getName() << "\n");
1695  F.setNoSync();
1696  ++NumNoSync;
1697  },
1698  /* RequiresExactDefinition= */ true});
1699  AI.run(SCCNodes, Changed);
1700 }
1701 
1702 static SCCNodesResult createSCCNodeSet(ArrayRef<Function *> Functions) {
1703  SCCNodesResult Res;
1704  Res.HasUnknownCall = false;
1705  for (Function *F : Functions) {
1706  if (!F || F->hasOptNone() || F->hasFnAttribute(Attribute::Naked) ||
1707  F->isPresplitCoroutine()) {
1708  // Treat any function we're trying not to optimize as if it were an
1709  // indirect call and omit it from the node set used below.
1710  Res.HasUnknownCall = true;
1711  continue;
1712  }
1713  // Track whether any functions in this SCC have an unknown call edge.
1714  // Note: if this is ever a performance hit, we can common it with
1715  // subsequent routines which also do scans over the instructions of the
1716  // function.
1717  if (!Res.HasUnknownCall) {
1718  for (Instruction &I : instructions(*F)) {
1719  if (auto *CB = dyn_cast<CallBase>(&I)) {
1720  if (!CB->getCalledFunction()) {
1721  Res.HasUnknownCall = true;
1722  break;
1723  }
1724  }
1725  }
1726  }
1727  Res.SCCNodes.insert(F);
1728  }
1729  return Res;
1730 }
1731 
1732 template <typename AARGetterT>
1734 deriveAttrsInPostOrder(ArrayRef<Function *> Functions, AARGetterT &&AARGetter) {
1735  SCCNodesResult Nodes = createSCCNodeSet(Functions);
1736 
1737  // Bail if the SCC only contains optnone functions.
1738  if (Nodes.SCCNodes.empty())
1739  return {};
1740 
1741  SmallSet<Function *, 8> Changed;
1742 
1743  addArgumentReturnedAttrs(Nodes.SCCNodes, Changed);
1744  addMemoryAttrs(Nodes.SCCNodes, AARGetter, Changed);
1745  addArgumentAttrs(Nodes.SCCNodes, Changed);
1746  inferConvergent(Nodes.SCCNodes, Changed);
1747  addNoReturnAttrs(Nodes.SCCNodes, Changed);
1748  addWillReturn(Nodes.SCCNodes, Changed);
1749 
1750  // If we have no external nodes participating in the SCC, we can deduce some
1751  // more precise attributes as well.
1752  if (!Nodes.HasUnknownCall) {
1753  addNoAliasAttrs(Nodes.SCCNodes, Changed);
1754  addNonNullAttrs(Nodes.SCCNodes, Changed);
1755  inferAttrsFromFunctionBodies(Nodes.SCCNodes, Changed);
1756  addNoRecurseAttrs(Nodes.SCCNodes, Changed);
1757  }
1758 
1759  addNoSyncAttr(Nodes.SCCNodes, Changed);
1760 
1761  // Finally, infer the maximal set of attributes from the ones we've inferred
1762  // above. This is handling the cases where one attribute on a signature
1763  // implies another, but for implementation reasons the inference rule for
1764  // the later is missing (or simply less sophisticated).
1765  for (Function *F : Nodes.SCCNodes)
1766  if (F)
1768  Changed.insert(F);
1769 
1770  return Changed;
1771 }
1772 
1775  LazyCallGraph &CG,
1776  CGSCCUpdateResult &) {
1778  AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C, CG).getManager();
1779 
1780  // We pass a lambda into functions to wire them up to the analysis manager
1781  // for getting function analyses.
1782  auto AARGetter = [&](Function &F) -> AAResults & {
1783  return FAM.getResult<AAManager>(F);
1784  };
1785 
1786  SmallVector<Function *, 8> Functions;
1787  for (LazyCallGraph::Node &N : C) {
1788  Functions.push_back(&N.getFunction());
1789  }
1790 
1791  auto ChangedFunctions = deriveAttrsInPostOrder(Functions, AARGetter);
1792  if (ChangedFunctions.empty())
1793  return PreservedAnalyses::all();
1794 
1795  // Invalidate analyses for modified functions so that we don't have to
1796  // invalidate all analyses for all functions in this SCC.
1797  PreservedAnalyses FuncPA;
1798  // We haven't changed the CFG for modified functions.
1799  FuncPA.preserveSet<CFGAnalyses>();
1800  for (Function *Changed : ChangedFunctions) {
1801  FAM.invalidate(*Changed, FuncPA);
1802  // Also invalidate any direct callers of changed functions since analyses
1803  // may care about attributes of direct callees. For example, MemorySSA cares
1804  // about whether or not a call's callee modifies memory and queries that
1805  // through function attributes.
1806  for (auto *U : Changed->users()) {
1807  if (auto *Call = dyn_cast<CallBase>(U)) {
1808  if (Call->getCalledFunction() == Changed)
1809  FAM.invalidate(*Call->getFunction(), FuncPA);
1810  }
1811  }
1812  }
1813 
1814  PreservedAnalyses PA;
1815  // We have not added or removed functions.
1817  // We already invalidated all relevant function analyses above.
1819  return PA;
1820 }
1821 
1822 namespace {
1823 
1824 struct PostOrderFunctionAttrsLegacyPass : public CallGraphSCCPass {
1825  // Pass identification, replacement for typeid
1826  static char ID;
1827 
1828  PostOrderFunctionAttrsLegacyPass() : CallGraphSCCPass(ID) {
1831  }
1832 
1833  bool runOnSCC(CallGraphSCC &SCC) override;
1834 
1835  void getAnalysisUsage(AnalysisUsage &AU) const override {
1836  AU.setPreservesCFG();
1840  }
1841 };
1842 
1843 } // end anonymous namespace
1844 
1846 INITIALIZE_PASS_BEGIN(PostOrderFunctionAttrsLegacyPass, "function-attrs",
1847  "Deduce function attributes", false, false)
1851 INITIALIZE_PASS_END(PostOrderFunctionAttrsLegacyPass, "function-attrs",
1853 
1855  return new PostOrderFunctionAttrsLegacyPass();
1856 }
1857 
1858 template <typename AARGetterT>
1859 static bool runImpl(CallGraphSCC &SCC, AARGetterT AARGetter) {
1860  SmallVector<Function *, 8> Functions;
1861  for (CallGraphNode *I : SCC) {
1862  Functions.push_back(I->getFunction());
1863  }
1864 
1865  return !deriveAttrsInPostOrder(Functions, AARGetter).empty();
1866 }
1867 
1868 bool PostOrderFunctionAttrsLegacyPass::runOnSCC(CallGraphSCC &SCC) {
1869  if (skipSCC(SCC))
1870  return false;
1871  return runImpl(SCC, LegacyAARGetter(*this));
1872 }
1873 
1874 namespace {
1875 
1876 struct ReversePostOrderFunctionAttrsLegacyPass : public ModulePass {
1877  // Pass identification, replacement for typeid
1878  static char ID;
1879 
1880  ReversePostOrderFunctionAttrsLegacyPass() : ModulePass(ID) {
1883  }
1884 
1885  bool runOnModule(Module &M) override;
1886 
1887  void getAnalysisUsage(AnalysisUsage &AU) const override {
1888  AU.setPreservesCFG();
1891  }
1892 };
1893 
1894 } // end anonymous namespace
1895 
1897 
1898 INITIALIZE_PASS_BEGIN(ReversePostOrderFunctionAttrsLegacyPass,
1899  "rpo-function-attrs", "Deduce function attributes in RPO",
1900  false, false)
1902 INITIALIZE_PASS_END(ReversePostOrderFunctionAttrsLegacyPass,
1904  false, false)
1905 
1907  return new ReversePostOrderFunctionAttrsLegacyPass();
1908 }
1909 
1911  // We check the preconditions for the function prior to calling this to avoid
1912  // the cost of building up a reversible post-order list. We assert them here
1913  // to make sure none of the invariants this relies on were violated.
1914  assert(!F.isDeclaration() && "Cannot deduce norecurse without a definition!");
1915  assert(!F.doesNotRecurse() &&
1916  "This function has already been deduced as norecurs!");
1917  assert(F.hasInternalLinkage() &&
1918  "Can only do top-down deduction for internal linkage functions!");
1919 
1920  // If F is internal and all of its uses are calls from a non-recursive
1921  // functions, then none of its calls could in fact recurse without going
1922  // through a function marked norecurse, and so we can mark this function too
1923  // as norecurse. Note that the uses must actually be calls -- otherwise
1924  // a pointer to this function could be returned from a norecurse function but
1925  // this function could be recursively (indirectly) called. Note that this
1926  // also detects if F is directly recursive as F is not yet marked as
1927  // a norecurse function.
1928  for (auto &U : F.uses()) {
1929  auto *I = dyn_cast<Instruction>(U.getUser());
1930  if (!I)
1931  return false;
1932  CallBase *CB = dyn_cast<CallBase>(I);
1933  if (!CB || !CB->isCallee(&U) ||
1934  !CB->getParent()->getParent()->doesNotRecurse())
1935  return false;
1936  }
1937  F.setDoesNotRecurse();
1938  ++NumNoRecurse;
1939  return true;
1940 }
1941 
1943  // We only have a post-order SCC traversal (because SCCs are inherently
1944  // discovered in post-order), so we accumulate them in a vector and then walk
1945  // it in reverse. This is simpler than using the RPO iterator infrastructure
1946  // because we need to combine SCC detection and the PO walk of the call
1947  // graph. We can also cheat egregiously because we're primarily interested in
1948  // synthesizing norecurse and so we can only save the singular SCCs as SCCs
1949  // with multiple functions in them will clearly be recursive.
1950  SmallVector<Function *, 16> Worklist;
1951  for (scc_iterator<CallGraph *> I = scc_begin(&CG); !I.isAtEnd(); ++I) {
1952  if (I->size() != 1)
1953  continue;
1954 
1955  Function *F = I->front()->getFunction();
1956  if (F && !F->isDeclaration() && !F->doesNotRecurse() &&
1957  F->hasInternalLinkage())
1958  Worklist.push_back(F);
1959  }
1960 
1961  bool Changed = false;
1962  for (auto *F : llvm::reverse(Worklist))
1963  Changed |= addNoRecurseAttrsTopDown(*F);
1964 
1965  return Changed;
1966 }
1967 
1968 bool ReversePostOrderFunctionAttrsLegacyPass::runOnModule(Module &M) {
1969  if (skipModule(M))
1970  return false;
1971 
1972  auto &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph();
1973 
1974  return deduceFunctionAttributeInRPO(M, CG);
1975 }
1976 
1979  auto &CG = AM.getResult<CallGraphAnalysis>(M);
1980 
1981  if (!deduceFunctionAttributeInRPO(M, CG))
1982  return PreservedAnalyses::all();
1983 
1984  PreservedAnalyses PA;
1986  return PA;
1987 }
i
i
Definition: README.txt:29
llvm::SPII::Load
@ Load
Definition: SparcInstrInfo.h:32
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
llvm::ModRefInfo::NoModRef
@ NoModRef
The access neither references nor modifies the value stored in memory.
llvm::Argument
This class represents an incoming formal argument to a Function.
Definition: Argument.h:28
AssumptionCache.h
llvm::AAManager
A manager for alias analyses.
Definition: AliasAnalysis.h:876
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:109
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
llvm::none_of
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:1748
llvm::ReturnInst
Return a value (possibly void), from a function.
Definition: Instructions.h:3050
llvm::PHINode::incoming_values
op_range incoming_values()
Definition: Instructions.h:2783
llvm::AArch64PACKey::ID
ID
Definition: AArch64BaseInfo.h:818
llvm::CallGraphAnalysis
An analysis pass to compute the CallGraph for a Module.
Definition: CallGraph.h:304
Metadata.h
llvm::FindFunctionBackedges
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
PHI
Rewrite undef for PHI
Definition: AMDGPURewriteUndefForPHI.cpp:101
llvm::ModulePass
ModulePass class - This class is used to implement unstructured interprocedural optimizations and ana...
Definition: Pass.h:248
llvm::BasicBlock::getParent
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:104
IntrinsicInst.h
SCCIterator.h
llvm::AnalysisManager::getResult
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:774
llvm::MemoryLocation::Ptr
const Value * Ptr
The address of the start of the location.
Definition: MemoryLocation.h:219
InstIterator.h
llvm::FunctionSummary::calls
ArrayRef< EdgeTy > calls() const
Return the list of <CalleeValueInfo, CalleeInfo> pairs.
Definition: ModuleSummaryIndex.h:858
llvm::FunctionSummary::fflags
FFlags fflags() const
Get function summary flags.
Definition: ModuleSummaryIndex.h:842
llvm::Function
Definition: Function.h:60
llvm::AnalysisManager::invalidate
void invalidate(IRUnitT &IR, const PreservedAnalyses &PA)
Invalidate cached analyses for an IR unit.
Definition: PassManagerImpl.h:89
Pass.h
llvm::MemoryLocation::getOrNone
static std::optional< MemoryLocation > getOrNone(const Instruction *Inst)
Definition: MemoryLocation.cpp:78
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(PostOrderFunctionAttrsLegacyPass, "function-attrs", "Deduce function attributes", false, false) INITIALIZE_PASS_END(PostOrderFunctionAttrsLegacyPass
llvm::CaptureTracker
This callback is used in conjunction with PointerMayBeCaptured.
Definition: CaptureTracking.h:92
llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::size
size_type size() const
Determine the number of elements in the SetVector.
Definition: SetVector.h:77
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1199
Statistic.h
CaptureTracking.h
llvm::GlobalValue::isLocalLinkage
static bool isLocalLinkage(LinkageTypes Linkage)
Definition: GlobalValue.h:404
ErrorHandling.h
addNoSyncAttr
static void addNoSyncAttr(const SCCNodeSet &SCCNodes, SmallSet< Function *, 8 > &Changed)
Definition: FunctionAttrs.cpp:1681
llvm::AllAnalysesOn
This templated class represents "all analyses that operate over <a particular IR unit>" (e....
Definition: PassManager.h:90
llvm::erase_if
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:1997
RPO
rpo function Deduce function attributes in RPO
Definition: FunctionAttrs.cpp:1903
ValueTracking.h
Local.h
canReturn
static bool canReturn(Function &F)
Definition: FunctionAttrs.cpp:1549
llvm::CallGraph
The basic data container for the call graph of a Module of IR.
Definition: CallGraph.h:72
FAM
FunctionAnalysisManager FAM
Definition: PassBuilderBindings.cpp:59
llvm::CallBase::hasFnAttr
bool hasFnAttr(Attribute::AttrKind Kind) const
Determine whether this call has the given attribute.
Definition: InstrTypes.h:1484
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:140
llvm::isKnownNonZero
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.
Definition: ValueTracking.cpp:315
DenseMap.h
llvm::sys::path::end
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:235
instructionDoesNotReturn
static bool instructionDoesNotReturn(Instruction &I)
Definition: FunctionAttrs.cpp:1534
llvm::sys::path::begin
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:226
llvm::CallBase::isCallee
bool isCallee(Value::const_user_iterator UI) const
Determine whether the passed iterator points to the callee operand's Use.
Definition: InstrTypes.h:1408
llvm::SmallSet
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:136
llvm::MemoryEffects::ArgMem
@ ArgMem
Access to memory via argument pointers.
Definition: ModRef.h:68
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::count
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:145
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
llvm::GraphTraits< ArgumentGraphNode * >::NodeRef
ArgumentGraphNode * NodeRef
Definition: FunctionAttrs.cpp:556
llvm::MCID::Convergent
@ Convergent
Definition: MCInstrDesc.h:184
llvm::successors
auto successors(MachineBasicBlock *BB)
Definition: MachineSSAContext.h:29
llvm::MipsISD::Ret
@ Ret
Definition: MipsISelLowering.h:119
STLExtras.h
isReturnNonNull
static bool isReturnNonNull(Function *F, const SCCNodeSet &SCCNodes, bool &Speculative)
Tests whether this function is known to not return null.
Definition: FunctionAttrs.cpp:1118
llvm::FunctionSummary::FFlags::NoRecurse
unsigned NoRecurse
Definition: ModuleSummaryIndex.h:642
DisableNoUnwindInference
static cl::opt< bool > DisableNoUnwindInference("disable-nounwind-inference", cl::Hidden, cl::desc("Stop inferring nounwind attribute during function-attrs pass"))
llvm::GlobalValue::isLinkOnceODRLinkage
static bool isLinkOnceODRLinkage(LinkageTypes Linkage)
Definition: GlobalValue.h:380
createSCCNodeSet
static SCCNodesResult createSCCNodeSet(ArrayRef< Function * > Functions)
Definition: FunctionAttrs.cpp:1702
llvm::GraphTraits< ArgumentGraphNode * >::child_end
static ChildIteratorType child_end(NodeRef N)
Definition: FunctionAttrs.cpp:561
BasicAliasAnalysis.h
addArgumentReturnedAttrs
static void addArgumentReturnedAttrs(const SCCNodeSet &SCCNodes, SmallSet< Function *, 8 > &Changed)
Deduce returned attributes for the SCC.
Definition: FunctionAttrs.cpp:712
Use.h
ModuleSummaryIndex.h
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
runImpl
static bool runImpl(CallGraphSCC &SCC, AARGetterT AARGetter)
Definition: FunctionAttrs.cpp:1859
llvm::getAAResultsAnalysisUsage
void getAAResultsAnalysisUsage(AnalysisUsage &AU)
A helper for the legacy pass manager to populate AU to add uses to make sure the analyses required by...
Definition: AliasAnalysis.cpp:952
addAccessAttr
static bool addAccessAttr(Argument *A, Attribute::AttrKind R)
Definition: FunctionAttrs.cpp:801
attrs
function attrs
Definition: FunctionAttrs.cpp:1851
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::RISCVFenceField::R
@ R
Definition: RISCVBaseInfo.h:265
Uses
SmallPtrSet< MachineInstr *, 2 > Uses
Definition: ARMLowOverheadLoops.cpp:590
isFunctionMallocLike
static bool isFunctionMallocLike(Function *F, const SCCNodeSet &SCCNodes)
Tests whether a function is "malloc-like".
Definition: FunctionAttrs.cpp:1012
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::MemoryEffects
Summary of how a function affects memory in the program.
Definition: ModRef.h:63
Arg
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
Definition: AMDGPULibCalls.cpp:187
Instruction.h
CommandLine.h
llvm::GlobalValueSummary
Function and variable summary information to aid decisions and implementation of importing.
Definition: ModuleSummaryIndex.h:364
llvm::Instruction::getOpcode
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:169
llvm::all_of
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:1734
functionWillReturn
static bool functionWillReturn(const Function &F)
Definition: FunctionAttrs.cpp:1583
llvm::CallGraphSCC
CallGraphSCC - This is a single SCC that a CallGraphSCCPass is run on.
Definition: CallGraphSCCPass.h:87
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:24
llvm::LazyCallGraph::SCC
An SCC of the call graph.
Definition: LazyCallGraph.h:420
llvm::ModRefInfo::Ref
@ Ref
The access may reference the value stored in memory.
Constants.h
llvm::GlobalValue::isLinkOnceAnyLinkage
static bool isLinkOnceAnyLinkage(LinkageTypes Linkage)
Definition: GlobalValue.h:377
llvm::PHINode::getIncomingValue
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
Definition: Instructions.h:2793
llvm::AAResults
Definition: AliasAnalysis.h:294
InstrBreaksNonThrowing
static bool InstrBreaksNonThrowing(Instruction &I, const SCCNodeSet &SCCNodes)
Helper for NoUnwind inference predicate InstrBreaksAttribute.
Definition: FunctionAttrs.cpp:1381
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::ARM_PROC::A
@ A
Definition: ARMBaseInfo.h:34
llvm::MemoryEffects::Other
@ Other
Any other memory.
Definition: ModRef.h:72
InstrTypes.h
llvm::CallBase::getCalledFunction
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation or the function signa...
Definition: InstrTypes.h:1397
deriveAttrsInPostOrder
static SmallSet< Function *, 8 > deriveAttrsInPostOrder(ArrayRef< Function * > Functions, AARGetterT &&AARGetter)
Definition: FunctionAttrs.cpp:1734
SI
@ SI
Definition: SIInstrInfo.cpp:7966
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
addNoRecurseAttrsTopDown
static bool addNoRecurseAttrsTopDown(Function &F)
Definition: FunctionAttrs.cpp:1910
DisableThinLTOPropagation
static cl::opt< bool > DisableThinLTOPropagation("disable-thinlto-funcattrs", cl::init(true), cl::Hidden, cl::desc("Don't propagate function-attrs in thinLTO"))
false
Definition: StackSlotColoring.cpp:141
llvm::CallBase::isConvergent
bool isConvergent() const
Determine if the invoke is convergent.
Definition: InstrTypes.h:1902
llvm::dwarf::Index
Index
Definition: Dwarf.h:472
llvm::MemoryEffects::doesNotAccessMemory
bool doesNotAccessMemory() const
Whether this function accesses no memory.
Definition: ModRef.h:191
EnableNonnullArgPropagation
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."))
llvm::inferAttributesFromOthers
bool inferAttributesFromOthers(Function &F)
If we can infer one attribute from another on the declaration of a function, explicitly materialize t...
Definition: Local.cpp:3472
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::GlobalValue::isWeakODRLinkage
static bool isWeakODRLinkage(LinkageTypes Linkage)
Definition: GlobalValue.h:389
llvm::AAResults::getMemoryEffects
MemoryEffects getMemoryEffects(const CallBase *Call)
Return the behavior of the given call site.
Definition: AliasAnalysis.cpp:388
in
The object format emitted by the WebAssembly backed is documented in
Definition: README.txt:11
llvm::Instruction
Definition: Instruction.h:42
addNoAliasAttrs
static void addNoAliasAttrs(const SCCNodeSet &SCCNodes, SmallSet< Function *, 8 > &Changed)
Deduce noalias attributes for the SCC.
Definition: FunctionAttrs.cpp:1076
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
addArgumentAttrsFromCallsites
static bool addArgumentAttrsFromCallsites(Function &F)
If a callsite has arguments that are also arguments to the parent function, try to propagate attribut...
Definition: FunctionAttrs.cpp:762
llvm::X86AS::FS
@ FS
Definition: X86.h:200
addArgumentAttrs
static void addArgumentAttrs(const SCCNodeSet &SCCNodes, SmallSet< Function *, 8 > &Changed)
Deduce nocapture attributes for the SCC.
Definition: FunctionAttrs.cpp:827
llvm::Use::getUser
User * getUser() const
Returns the User that contains this Use.
Definition: Use.h:72
llvm::getUnderlyingObject
const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=6)
This method strips off any GEP address adjustments and pointer casts from the specified value,...
Definition: ValueTracking.cpp:4499
SmallPtrSet.h
llvm::CallGraphNode
A node in the call graph for a module.
Definition: CallGraph.h:166
llvm::GraphTraits< ArgumentGraph * >::nodes_end
static ChildIteratorType nodes_end(ArgumentGraph *AG)
Definition: FunctionAttrs.cpp:572
LazyCallGraph.h
inferAttrsFromFunctionBodies
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...
Definition: FunctionAttrs.cpp:1449
DisableNoFreeInference
static cl::opt< bool > DisableNoFreeInference("disable-nofree-inference", cl::Hidden, cl::desc("Stop inferring nofree attribute during function-attrs pass"))
llvm::MCID::Call
@ Call
Definition: MCInstrDesc.h:155
llvm::PHINode::getNumIncomingValues
unsigned getNumIncomingValues() const
Return the number of incoming edges.
Definition: Instructions.h:2789
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
llvm::CallBase::onlyReadsMemory
bool onlyReadsMemory(unsigned OpNo) const
Definition: InstrTypes.h:1721
Type.h
llvm::computeFunctionBodyMemoryAccess
MemoryEffects computeFunctionBodyMemoryAccess(Function &F, AAResults &AAR)
Returns the memory access properties of this copy of the function.
Definition: FunctionAttrs.cpp:233
llvm::ValueInfo
Struct that holds a reference to a particular GUID in a global value summary.
Definition: ModuleSummaryIndex.h:169
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
llvm::dxil::PointerTypeAnalysis::run
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
Definition: PointerTypeAnalysis.cpp:189
llvm::scc_begin
scc_iterator< T > scc_begin(const T &G)
Construct the begin iterator for a deduced graph type T.
Definition: SCCIterator.h:232
llvm::function_ref
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLFunctionalExtras.h:36
addWillReturn
static void addWillReturn(const SCCNodeSet &SCCNodes, SmallSet< Function *, 8 > &Changed)
Definition: FunctionAttrs.cpp:1613
addNoReturnAttrs
static void addNoReturnAttrs(const SCCNodeSet &SCCNodes, SmallSet< Function *, 8 > &Changed)
Definition: FunctionAttrs.cpp:1569
BasicBlock.h
llvm::cl::opt< bool >
llvm::instructions
inst_range instructions(Function *F)
Definition: InstIterator.h:133
llvm::MemoryEffects::unknown
static MemoryEffects unknown()
Create MemoryEffects that can read and write any memory.
Definition: ModRef.h:113
VI
@ VI
Definition: SIInstrInfo.cpp:7967
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
llvm::CallBase::doesNotAccessMemory
bool doesNotAccessMemory(unsigned OpNo) const
Definition: InstrTypes.h:1715
llvm::CallGraphSCCPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &Info) const override
getAnalysisUsage - For this class, we declare that we require and preserve the call graph.
Definition: CallGraphSCCPass.cpp:658
uint64_t
D
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
llvm::Attribute::None
@ None
No attributes have been set.
Definition: Attributes.h:87
llvm::createReversePostOrderFunctionAttrsPass
Pass * createReversePostOrderFunctionAttrsPass()
createReversePostOrderFunctionAttrsPass - This pass walks SCCs of the call graph in RPO to deduce and...
Definition: FunctionAttrs.cpp:1906
llvm::scc_iterator
Enumerate the SCCs of a directed graph in reverse topological order of the SCC DAG.
Definition: SCCIterator.h:46
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::PreservedAnalyses::preserve
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:173
IPO.h
addNonNullAttrs
static void addNonNullAttrs(const SCCNodeSet &SCCNodes, SmallSet< Function *, 8 > &Changed)
Deduce nonnull attributes for the SCC.
Definition: FunctionAttrs.cpp:1184
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:53
llvm::MemoryEffects::getModRef
ModRefInfo getModRef(Location Loc) const
Get ModRefInfo for the given Location.
Definition: ModRef.h:164
MemoryLocation.h
llvm::DenseMap
Definition: DenseMap.h:714
CGSCCPassManager.h
llvm::CallGraphWrapperPass
The ModulePass which wraps up a CallGraph and the logic to build it.
Definition: CallGraph.h:347
llvm::ReversePostOrderFunctionAttrsPass::run
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)
Definition: FunctionAttrs.cpp:1978
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::Attribute::AttrKind
AttrKind
This enumeration lists the attributes that can be associated with parameters, function results,...
Definition: Attributes.h:85
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:447
checkFunctionMemoryAccess
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...
Definition: FunctionAttrs.cpp:123
ArrayRef.h
llvm::CallBase::doesNotCapture
bool doesNotCapture(unsigned OpNo) const
Determine whether this data operand is not captured.
Definition: InstrTypes.h:1674
llvm::createPostOrderFunctionAttrsLegacyPass
Pass * createPostOrderFunctionAttrsLegacyPass()
Create a legacy pass manager instance of a pass to compute function attrs in post-order.
Definition: FunctionAttrs.cpp:1854
llvm::SPII::Store
@ Store
Definition: SparcInstrInfo.h:33
llvm::ModRefInfo
ModRefInfo
Flags indicating whether a memory access modifies or references memory.
Definition: ModRef.h:27
llvm::MemoryEffects::none
static MemoryEffects none()
Create MemoryEffects that cannot read or write any memory.
Definition: ModRef.h:118
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::GlobalValue::isExternalLinkage
static bool isExternalLinkage(LinkageTypes Linkage)
Definition: GlobalValue.h:371
llvm::CallBase::hasOperandBundles
bool hasOperandBundles() const
Return true if this User has any operand bundles.
Definition: InstrTypes.h:1936
InstrBreaksNonConvergent
static bool InstrBreaksNonConvergent(Instruction &I, const SCCNodeSet &SCCNodes)
Helper for non-Convergent inference predicate InstrBreaksAttribute.
Definition: FunctionAttrs.cpp:1371
determinePointerAccessAttrs
static Attribute::AttrKind determinePointerAccessAttrs(Argument *A, const SmallPtrSet< Argument *, 8 > &SCCNodes)
Returns Attribute::None, Attribute::ReadOnly or Attribute::ReadNone.
Definition: FunctionAttrs.cpp:579
llvm::SelectInst
This class represents the LLVM 'select' instruction.
Definition: Instructions.h:1735
function
print Print MemDeps of function
Definition: MemDepPrinter.cpp:82
llvm::GlobalValue::isAvailableExternallyLinkage
static bool isAvailableExternallyLinkage(LinkageTypes Linkage)
Definition: GlobalValue.h:374
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:66
llvm::Function::doesNotRecurse
bool doesNotRecurse() const
Determine if the function is known not to recurse, directly or indirectly.
Definition: Function.h:588
llvm::FunctionSummary::FFlags
Flags specific to function summaries.
Definition: ModuleSummaryIndex.h:637
llvm::LazyCallGraph::Node
A node in the call graph.
Definition: LazyCallGraph.h:316
llvm::SmallPtrSetImpl::count
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:383
llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::insert
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:141
llvm::AMDGPU::CPol::SCC
@ SCC
Definition: SIDefines.h:307
CFG.h
llvm::initializeReversePostOrderFunctionAttrsLegacyPassPass
void initializeReversePostOrderFunctionAttrsLegacyPassPass(PassRegistry &)
calculatePrevailingSummary
static FunctionSummary * calculatePrevailingSummary(ValueInfo VI, DenseMap< ValueInfo, FunctionSummary * > &CachedPrevailingSummary, function_ref< bool(GlobalValue::GUID, const GlobalValueSummary *)> IsPrevailing)
Definition: FunctionAttrs.cpp:268
llvm::AssumptionCacheTracker
An immutable pass that tracks lazily created AssumptionCache objects.
Definition: AssumptionCache.h:202
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::PointerMayBeCaptured
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...
Definition: CaptureTracking.cpp:229
llvm::any_of
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:1741
llvm::GraphTraits< ArgumentGraph * >::getEntryNode
static NodeRef getEntryNode(ArgumentGraph *AG)
Definition: FunctionAttrs.cpp:566
llvm::initializePostOrderFunctionAttrsLegacyPassPass
void initializePostOrderFunctionAttrsLegacyPassPass(PassRegistry &)
llvm::AnalysisUsage::setPreservesCFG
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:265
basicBlockCanReturn
static bool basicBlockCanReturn(BasicBlock &BB)
Definition: FunctionAttrs.cpp:1542
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:143
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
llvm::CFGAnalyses
Represents analyses that only rely on functions' control flow.
Definition: PassManager.h:113
llvm::AnalysisUsage::addPreserved
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
Definition: PassAnalysisSupport.h:98
A
* A
Definition: README_ALTIVEC.txt:89
Compiler.h
llvm::ModRefInfo::Mod
@ Mod
The access may modify the value stored in memory.
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
llvm::GraphTraits< ArgumentGraphNode * >::ChildIteratorType
SmallVectorImpl< ArgumentGraphNode * >::iterator ChildIteratorType
Definition: FunctionAttrs.cpp:557
llvm::CallBase::hasRetAttr
bool hasRetAttr(Attribute::AttrKind Kind) const
Determine whether the return value has the given attribute.
Definition: InstrTypes.h:1596
CallGraphSCCPass.h
llvm::CallBase::dataOperandHasImpliedAttr
bool dataOperandHasImpliedAttr(unsigned i, Attribute::AttrKind Kind) const
Return true if the data operand at index i has the attribute A.
Definition: InstrTypes.h:1654
llvm::MemoryEffects::getWithoutLoc
MemoryEffects getWithoutLoc(Location Loc) const
Get new MemoryEffects with NoModRef on the given Loc.
Definition: ModRef.h:176
Argument.h
llvm::GraphTraits< ArgumentGraphNode * >
Definition: FunctionAttrs.cpp:555
Callee
amdgpu Simplify well known AMD library false FunctionCallee Callee
Definition: AMDGPULibCalls.cpp:187
llvm::MCID::Select
@ Select
Definition: MCInstrDesc.h:164
Attributes.h
Constant.h
llvm::CGSCCUpdateResult
Support structure for SCC passes to communicate updates the call graph back to the CGSCC pass manager...
Definition: CGSCCPassManager.h:232
llvm::FunctionSummary
Function summary information to aid decisions and implementation of importing.
Definition: ModuleSummaryIndex.h:587
llvm::CallBase::getDataOperandNo
unsigned getDataOperandNo(Value::const_user_iterator UI) const
Given a value use iterator, return the data operand corresponding to it.
Definition: InstrTypes.h:1305
llvm::isIdentifiedObject
bool isIdentifiedObject(const Value *V)
Return true if this pointer refers to a distinct and identifiable object.
Definition: AliasAnalysis.cpp:891
llvm::copy_if
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:1780
llvm::CallBase::isArgOperand
bool isArgOperand(const Use *U) const
Definition: InstrTypes.h:1362
llvm::PostOrderFunctionAttrsPass::run
PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, LazyCallGraph &CG, CGSCCUpdateResult &UR)
Definition: FunctionAttrs.cpp:1773
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
llvm::SyncScope::SingleThread
@ SingleThread
Synchronized with respect to signal handlers executing in the same thread.
Definition: LLVMContext.h:54
llvm::CallBase::arg_size
unsigned arg_size() const
Definition: InstrTypes.h:1340
llvm::thinLTOPropagateFunctionAttrs
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.
Definition: FunctionAttrs.cpp:371
llvm::isGuaranteedToTransferExecutionToSuccessor
bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)
Return true if this function can prove that the instruction I will always transfer execution to one o...
Definition: ValueTracking.cpp:5471
Casting.h
Function.h
llvm::CallGraphSCCPass
Definition: CallGraphSCCPass.h:34
addNoRecurseAttrs
static void addNoRecurseAttrs(const SCCNodeSet &SCCNodes, SmallSet< Function *, 8 > &Changed)
Definition: FunctionAttrs.cpp:1502
PassManager.h
inferConvergent
static void inferConvergent(const SCCNodeSet &SCCNodes, SmallSet< Function *, 8 > &Changed)
Attempt to remove convergent function attribute when possible.
Definition: FunctionAttrs.cpp:1416
llvm::FunctionSummary::FFlags::MayThrow
unsigned MayThrow
Definition: ModuleSummaryIndex.h:653
InstrBreaksNoSync
static bool InstrBreaksNoSync(Instruction &I, const SCCNodeSet &SCCNodes)
Definition: FunctionAttrs.cpp:1648
llvm::SmallSet::insert
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:178
addMemoryAttrs
static void addMemoryAttrs(const SCCNodeSet &SCCNodes, AARGetterT &&AARGetter, SmallSet< Function *, 8 > &Changed)
Deduce readonly/readnone/writeonly attributes for the SCC.
Definition: FunctionAttrs.cpp:240
InstrBreaksNoFree
static bool InstrBreaksNoFree(Instruction &I, const SCCNodeSet &SCCNodes)
Helper for NoFree inference predicate InstrBreaksAttribute.
Definition: FunctionAttrs.cpp:1397
CallGraph.h
llvm::GraphTraits< ArgumentGraphNode * >::getEntryNode
static NodeRef getEntryNode(NodeRef A)
Definition: FunctionAttrs.cpp:559
llvm::Pass
Pass interface - Implemented by all 'passes'.
Definition: Pass.h:91
llvm::AAResults::getModRefInfoMask
ModRefInfo getModRefInfoMask(const MemoryLocation &Loc, bool IgnoreLocals=false)
Returns a bitmask that should be unconditionally applied to the ModRef info of a memory location.
Definition: AliasAnalysis.cpp:150
Instructions.h
llvm::PreservedAnalyses::preserveSet
void preserveSet()
Mark an analysis set as preserved.
Definition: PassManager.h:188
llvm::GraphTraits< ArgumentGraph * >::nodes_begin
static ChildIteratorType nodes_begin(ArgumentGraph *AG)
Definition: FunctionAttrs.cpp:568
SmallVector.h
User.h
llvm::ModuleSummaryIndex
Class to hold module path string table and global value map, and encapsulate methods for operating on...
Definition: ModuleSummaryIndex.h:1199
llvm::MemoryEffects::argMemOnly
static MemoryEffects argMemOnly(ModRefInfo MR=ModRefInfo::ModRef)
Create MemoryEffects that can only access argument memory.
Definition: ModRef.h:133
llvm::SmallVectorImpl::iterator
typename SuperClass::iterator iterator
Definition: SmallVector.h:581
llvm::CallBase::getArgOperand
Value * getArgOperand(unsigned i) const
Definition: InstrTypes.h:1342
N
#define N
attributes
function Deduce function attributes
Definition: FunctionAttrs.cpp:1852
llvm::AAResultsWrapperPass
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
Definition: AliasAnalysis.h:924
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:91
llvm::SmallVectorImpl::pop_back_val
T pop_back_val()
Definition: SmallVector.h:677
llvm::PHINode
Definition: Instructions.h:2697
llvm::GlobalValue::isWeakAnyLinkage
static bool isWeakAnyLinkage(LinkageTypes Linkage)
Definition: GlobalValue.h:386
llvm::reverse
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:485
llvm::isNoModRef
bool isNoModRef(const ModRefInfo MRI)
Definition: ModRef.h:39
llvm::MemoryLocation::getBeforeOrAfter
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...
Definition: MemoryLocation.h:279
llvm::CallBase
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1175
llvm::SmallSetVector
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:307
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::FunctionSummary::FFlags::NoUnwind
unsigned NoUnwind
Definition: ModuleSummaryIndex.h:651
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
llvm::GraphTraits
Definition: GraphTraits.h:37
llvm::User::getOperand
Value * getOperand(unsigned i) const
Definition: User.h:169
llvm::cl::desc
Definition: CommandLine.h:413
llvm::LazyCallGraph
A lazily constructed view of the call graph of a module.
Definition: LazyCallGraph.h:111
isOrderedAtomic
static bool isOrderedAtomic(Instruction *I)
Definition: FunctionAttrs.cpp:1630
raw_ostream.h
llvm::FunctionAnalysisManagerCGSCCProxy
A proxy from a FunctionAnalysisManager to an SCC.
Definition: CGSCCPassManager.h:392
Value.h
deduceFunctionAttributeInRPO
static bool deduceFunctionAttributeInRPO(Module &M, CallGraph &CG)
Definition: FunctionAttrs.cpp:1942
llvm::LegacyAARGetter
This class is a functor to be used in legacy module or SCC passes for computing AA results for a func...
Definition: BasicAliasAnalysis.h:189
InitializePasses.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
FunctionAttrs.h
Debug.h
llvm::GraphTraits< ArgumentGraphNode * >::child_begin
static ChildIteratorType child_begin(NodeRef N)
Definition: FunctionAttrs.cpp:560
llvm::MemoryEffects::inaccessibleMemOnly
static MemoryEffects inaccessibleMemOnly(ModRefInfo MR=ModRefInfo::ModRef)
Create MemoryEffects that can only access inaccessible memory.
Definition: ModRef.h:138
llvm::ModRefInfo::ModRef
@ ModRef
The access may reference and may modify the value stored in memory.
llvm::MemoryLocation
Representation for a specific memory location.
Definition: MemoryLocation.h:211
SetVector.h
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
SmallSet.h
llvm::SmallPtrSetImpl::insert
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