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