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