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