LLVM  8.0.0svn
FunctionAttrs.cpp
Go to the documentation of this file.
1 //===- FunctionAttrs.cpp - Pass which marks functions attributes ----------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 /// \file
11 /// This file implements interprocedural passes which walk the
12 /// call-graph deducing and/or propagating function attributes.
13 //
14 //===----------------------------------------------------------------------===//
15 
17 #include "llvm/ADT/SCCIterator.h"
18 #include "llvm/ADT/STLExtras.h"
19 #include "llvm/ADT/SetVector.h"
20 #include "llvm/ADT/SmallPtrSet.h"
21 #include "llvm/ADT/SmallVector.h"
22 #include "llvm/ADT/Statistic.h"
33 #include "llvm/IR/Argument.h"
34 #include "llvm/IR/Attributes.h"
35 #include "llvm/IR/BasicBlock.h"
36 #include "llvm/IR/CallSite.h"
37 #include "llvm/IR/Constant.h"
38 #include "llvm/IR/Constants.h"
39 #include "llvm/IR/Function.h"
40 #include "llvm/IR/InstIterator.h"
41 #include "llvm/IR/InstrTypes.h"
42 #include "llvm/IR/Instruction.h"
43 #include "llvm/IR/Instructions.h"
44 #include "llvm/IR/Metadata.h"
45 #include "llvm/IR/PassManager.h"
46 #include "llvm/IR/Type.h"
47 #include "llvm/IR/Use.h"
48 #include "llvm/IR/User.h"
49 #include "llvm/IR/Value.h"
50 #include "llvm/Pass.h"
51 #include "llvm/Support/Casting.h"
53 #include "llvm/Support/Compiler.h"
54 #include "llvm/Support/Debug.h"
57 #include "llvm/Transforms/IPO.h"
58 #include <cassert>
59 #include <iterator>
60 #include <map>
61 #include <vector>
62 
63 using namespace llvm;
64 
65 #define DEBUG_TYPE "functionattrs"
66 
67 STATISTIC(NumReadNone, "Number of functions marked readnone");
68 STATISTIC(NumReadOnly, "Number of functions marked readonly");
69 STATISTIC(NumWriteOnly, "Number of functions marked writeonly");
70 STATISTIC(NumNoCapture, "Number of arguments marked nocapture");
71 STATISTIC(NumReturned, "Number of arguments marked returned");
72 STATISTIC(NumReadNoneArg, "Number of arguments marked readnone");
73 STATISTIC(NumReadOnlyArg, "Number of arguments marked readonly");
74 STATISTIC(NumNoAlias, "Number of function returns marked noalias");
75 STATISTIC(NumNonNullReturn, "Number of function returns marked nonnull");
76 STATISTIC(NumNoRecurse, "Number of functions marked as norecurse");
77 STATISTIC(NumNoUnwind, "Number of functions marked as nounwind");
78 
79 // FIXME: This is disabled by default to avoid exposing security vulnerabilities
80 // in C/C++ code compiled by clang:
81 // http://lists.llvm.org/pipermail/cfe-dev/2017-January/052066.html
83  "enable-nonnull-arg-prop", cl::Hidden,
84  cl::desc("Try to propagate nonnull argument attributes from callsites to "
85  "caller functions."));
86 
88  "disable-nounwind-inference", cl::Hidden,
89  cl::desc("Stop inferring nounwind attribute during function-attrs pass"));
90 
91 namespace {
92 
93 using SCCNodeSet = SmallSetVector<Function *, 8>;
94 
95 } // end anonymous namespace
96 
97 /// Returns the memory access attribute for function F using AAR for AA results,
98 /// where SCCNodes is the current SCC.
99 ///
100 /// If ThisBody is true, this function may examine the function body and will
101 /// return a result pertaining to this copy of the function. If it is false, the
102 /// result will be based only on AA results for the function declaration; it
103 /// will be assumed that some other (perhaps less optimized) version of the
104 /// function may be selected at link time.
106  AAResults &AAR,
107  const SCCNodeSet &SCCNodes) {
109  if (MRB == FMRB_DoesNotAccessMemory)
110  // Already perfect!
111  return MAK_ReadNone;
112 
113  if (!ThisBody) {
115  return MAK_ReadOnly;
116 
118  return MAK_WriteOnly;
119 
120  // Conservatively assume it reads and writes to memory.
121  return MAK_MayWrite;
122  }
123 
124  // Scan the function body for instructions that may read or write memory.
125  bool ReadsMemory = false;
126  bool WritesMemory = false;
127  for (inst_iterator II = inst_begin(F), E = inst_end(F); II != E; ++II) {
128  Instruction *I = &*II;
129 
130  // Some instructions can be ignored even if they read or write memory.
131  // Detect these now, skipping to the next instruction if one is found.
132  CallSite CS(cast<Value>(I));
133  if (CS) {
134  // Ignore calls to functions in the same SCC, as long as the call sites
135  // don't have operand bundles. Calls with operand bundles are allowed to
136  // have memory effects not described by the memory effects of the call
137  // target.
138  if (!CS.hasOperandBundles() && CS.getCalledFunction() &&
139  SCCNodes.count(CS.getCalledFunction()))
140  continue;
143 
144  // If the call doesn't access memory, we're done.
145  if (isNoModRef(MRI))
146  continue;
147 
149  // The call could access any memory. If that includes writes, note it.
150  if (isModSet(MRI))
151  WritesMemory = true;
152  // If it reads, note it.
153  if (isRefSet(MRI))
154  ReadsMemory = true;
155  continue;
156  }
157 
158  // Check whether all pointer arguments point to local memory, and
159  // ignore calls that only access local memory.
160  for (CallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end();
161  CI != CE; ++CI) {
162  Value *Arg = *CI;
163  if (!Arg->getType()->isPtrOrPtrVectorTy())
164  continue;
165 
166  AAMDNodes AAInfo;
167  I->getAAMetadata(AAInfo);
169 
170  // Skip accesses to local or constant memory as they don't impact the
171  // externally visible mod/ref behavior.
172  if (AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true))
173  continue;
174 
175  if (isModSet(MRI))
176  // Writes non-local memory.
177  WritesMemory = true;
178  if (isRefSet(MRI))
179  // Ok, it reads non-local memory.
180  ReadsMemory = true;
181  }
182  continue;
183  } else if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
184  // Ignore non-volatile loads from local memory. (Atomic is okay here.)
185  if (!LI->isVolatile()) {
187  if (AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true))
188  continue;
189  }
190  } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
191  // Ignore non-volatile stores to local memory. (Atomic is okay here.)
192  if (!SI->isVolatile()) {
194  if (AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true))
195  continue;
196  }
197  } else if (VAArgInst *VI = dyn_cast<VAArgInst>(I)) {
198  // Ignore vaargs on local memory.
200  if (AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true))
201  continue;
202  }
203 
204  // Any remaining instructions need to be taken seriously! Check if they
205  // read or write memory.
206  //
207  // Writes memory, remember that.
208  WritesMemory |= I->mayWriteToMemory();
209 
210  // If this instruction may read memory, remember that.
211  ReadsMemory |= I->mayReadFromMemory();
212  }
213 
214  if (WritesMemory) {
215  if (!ReadsMemory)
216  return MAK_WriteOnly;
217  else
218  return MAK_MayWrite;
219  }
220 
221  return ReadsMemory ? MAK_ReadOnly : MAK_ReadNone;
222 }
223 
225  AAResults &AAR) {
226  return checkFunctionMemoryAccess(F, /*ThisBody=*/true, AAR, {});
227 }
228 
229 /// Deduce readonly/readnone attributes for the SCC.
230 template <typename AARGetterT>
231 static bool addReadAttrs(const SCCNodeSet &SCCNodes, AARGetterT &&AARGetter) {
232  // Check if any of the functions in the SCC read or write memory. If they
233  // write memory then they can't be marked readnone or readonly.
234  bool ReadsMemory = false;
235  bool WritesMemory = false;
236  for (Function *F : SCCNodes) {
237  // Call the callable parameter to look up AA results for this function.
238  AAResults &AAR = AARGetter(*F);
239 
240  // Non-exact function definitions may not be selected at link time, and an
241  // alternative version that writes to memory may be selected. See the
242  // comment on GlobalValue::isDefinitionExact for more details.
243  switch (checkFunctionMemoryAccess(*F, F->hasExactDefinition(),
244  AAR, SCCNodes)) {
245  case MAK_MayWrite:
246  return false;
247  case MAK_ReadOnly:
248  ReadsMemory = true;
249  break;
250  case MAK_WriteOnly:
251  WritesMemory = true;
252  break;
253  case MAK_ReadNone:
254  // Nothing to do!
255  break;
256  }
257  }
258 
259  // Success! Functions in this SCC do not access memory, or only read memory.
260  // Give them the appropriate attribute.
261  bool MadeChange = false;
262 
263  assert(!(ReadsMemory && WritesMemory) &&
264  "Function marked read-only and write-only");
265  for (Function *F : SCCNodes) {
266  if (F->doesNotAccessMemory())
267  // Already perfect!
268  continue;
269 
270  if (F->onlyReadsMemory() && ReadsMemory)
271  // No change.
272  continue;
273 
274  if (F->doesNotReadMemory() && WritesMemory)
275  continue;
276 
277  MadeChange = true;
278 
279  // Clear out any existing attributes.
280  F->removeFnAttr(Attribute::ReadOnly);
281  F->removeFnAttr(Attribute::ReadNone);
282  F->removeFnAttr(Attribute::WriteOnly);
283 
284  if (!WritesMemory && !ReadsMemory) {
285  // Clear out any "access range attributes" if readnone was deduced.
286  F->removeFnAttr(Attribute::ArgMemOnly);
287  F->removeFnAttr(Attribute::InaccessibleMemOnly);
288  F->removeFnAttr(Attribute::InaccessibleMemOrArgMemOnly);
289  }
290 
291  // Add in the new attribute.
292  if (WritesMemory && !ReadsMemory)
293  F->addFnAttr(Attribute::WriteOnly);
294  else
295  F->addFnAttr(ReadsMemory ? Attribute::ReadOnly : Attribute::ReadNone);
296 
297  if (WritesMemory && !ReadsMemory)
298  ++NumWriteOnly;
299  else if (ReadsMemory)
300  ++NumReadOnly;
301  else
302  ++NumReadNone;
303  }
304 
305  return MadeChange;
306 }
307 
308 namespace {
309 
310 /// For a given pointer Argument, this retains a list of Arguments of functions
311 /// in the same SCC that the pointer data flows into. We use this to build an
312 /// SCC of the arguments.
313 struct ArgumentGraphNode {
314  Argument *Definition;
316 };
317 
318 class ArgumentGraph {
319  // We store pointers to ArgumentGraphNode objects, so it's important that
320  // that they not move around upon insert.
321  using ArgumentMapTy = std::map<Argument *, ArgumentGraphNode>;
322 
323  ArgumentMapTy ArgumentMap;
324 
325  // There is no root node for the argument graph, in fact:
326  // void f(int *x, int *y) { if (...) f(x, y); }
327  // is an example where the graph is disconnected. The SCCIterator requires a
328  // single entry point, so we maintain a fake ("synthetic") root node that
329  // uses every node. Because the graph is directed and nothing points into
330  // the root, it will not participate in any SCCs (except for its own).
331  ArgumentGraphNode SyntheticRoot;
332 
333 public:
334  ArgumentGraph() { SyntheticRoot.Definition = nullptr; }
335 
337 
338  iterator begin() { return SyntheticRoot.Uses.begin(); }
339  iterator end() { return SyntheticRoot.Uses.end(); }
340  ArgumentGraphNode *getEntryNode() { return &SyntheticRoot; }
341 
342  ArgumentGraphNode *operator[](Argument *A) {
343  ArgumentGraphNode &Node = ArgumentMap[A];
344  Node.Definition = A;
345  SyntheticRoot.Uses.push_back(&Node);
346  return &Node;
347  }
348 };
349 
350 /// This tracker checks whether callees are in the SCC, and if so it does not
351 /// consider that a capture, instead adding it to the "Uses" list and
352 /// continuing with the analysis.
353 struct ArgumentUsesTracker : public CaptureTracker {
354  ArgumentUsesTracker(const SCCNodeSet &SCCNodes) : SCCNodes(SCCNodes) {}
355 
356  void tooManyUses() override { Captured = true; }
357 
358  bool captured(const Use *U) override {
359  CallSite CS(U->getUser());
360  if (!CS.getInstruction()) {
361  Captured = true;
362  return true;
363  }
364 
365  Function *F = CS.getCalledFunction();
366  if (!F || !F->hasExactDefinition() || !SCCNodes.count(F)) {
367  Captured = true;
368  return true;
369  }
370 
371  // Note: the callee and the two successor blocks *follow* the argument
372  // operands. This means there is no need to adjust UseIndex to account for
373  // these.
374 
375  unsigned UseIndex =
376  std::distance(const_cast<const Use *>(CS.arg_begin()), U);
377 
378  assert(UseIndex < CS.data_operands_size() &&
379  "Indirect function calls should have been filtered above!");
380 
381  if (UseIndex >= CS.getNumArgOperands()) {
382  // Data operand, but not a argument operand -- must be a bundle operand
383  assert(CS.hasOperandBundles() && "Must be!");
384 
385  // CaptureTracking told us that we're being captured by an operand bundle
386  // use. In this case it does not matter if the callee is within our SCC
387  // or not -- we've been captured in some unknown way, and we have to be
388  // conservative.
389  Captured = true;
390  return true;
391  }
392 
393  if (UseIndex >= F->arg_size()) {
394  assert(F->isVarArg() && "More params than args in non-varargs call");
395  Captured = true;
396  return true;
397  }
398 
399  Uses.push_back(&*std::next(F->arg_begin(), UseIndex));
400  return false;
401  }
402 
403  // True only if certainly captured (used outside our SCC).
404  bool Captured = false;
405 
406  // Uses within our SCC.
408 
409  const SCCNodeSet &SCCNodes;
410 };
411 
412 } // end anonymous namespace
413 
414 namespace llvm {
415 
416 template <> struct GraphTraits<ArgumentGraphNode *> {
417  using NodeRef = ArgumentGraphNode *;
419 
420  static NodeRef getEntryNode(NodeRef A) { return A; }
421  static ChildIteratorType child_begin(NodeRef N) { return N->Uses.begin(); }
422  static ChildIteratorType child_end(NodeRef N) { return N->Uses.end(); }
423 };
424 
425 template <>
426 struct GraphTraits<ArgumentGraph *> : public GraphTraits<ArgumentGraphNode *> {
427  static NodeRef getEntryNode(ArgumentGraph *AG) { return AG->getEntryNode(); }
428 
429  static ChildIteratorType nodes_begin(ArgumentGraph *AG) {
430  return AG->begin();
431  }
432 
433  static ChildIteratorType nodes_end(ArgumentGraph *AG) { return AG->end(); }
434 };
435 
436 } // end namespace llvm
437 
438 /// Returns Attribute::None, Attribute::ReadOnly or Attribute::ReadNone.
439 static Attribute::AttrKind
441  const SmallPtrSet<Argument *, 8> &SCCNodes) {
442  SmallVector<Use *, 32> Worklist;
443  SmallPtrSet<Use *, 32> Visited;
444 
445  // inalloca arguments are always clobbered by the call.
446  if (A->hasInAllocaAttr())
447  return Attribute::None;
448 
449  bool IsRead = false;
450  // We don't need to track IsWritten. If A is written to, return immediately.
451 
452  for (Use &U : A->uses()) {
453  Visited.insert(&U);
454  Worklist.push_back(&U);
455  }
456 
457  while (!Worklist.empty()) {
458  Use *U = Worklist.pop_back_val();
459  Instruction *I = cast<Instruction>(U->getUser());
460 
461  switch (I->getOpcode()) {
462  case Instruction::BitCast:
463  case Instruction::GetElementPtr:
464  case Instruction::PHI:
465  case Instruction::Select:
466  case Instruction::AddrSpaceCast:
467  // The original value is not read/written via this if the new value isn't.
468  for (Use &UU : I->uses())
469  if (Visited.insert(&UU).second)
470  Worklist.push_back(&UU);
471  break;
472 
473  case Instruction::Call:
474  case Instruction::Invoke: {
475  bool Captures = true;
476 
477  if (I->getType()->isVoidTy())
478  Captures = false;
479 
480  auto AddUsersToWorklistIfCapturing = [&] {
481  if (Captures)
482  for (Use &UU : I->uses())
483  if (Visited.insert(&UU).second)
484  Worklist.push_back(&UU);
485  };
486 
487  CallSite CS(I);
488  if (CS.doesNotAccessMemory()) {
489  AddUsersToWorklistIfCapturing();
490  continue;
491  }
492 
493  Function *F = CS.getCalledFunction();
494  if (!F) {
495  if (CS.onlyReadsMemory()) {
496  IsRead = true;
497  AddUsersToWorklistIfCapturing();
498  continue;
499  }
500  return Attribute::None;
501  }
502 
503  // Note: the callee and the two successor blocks *follow* the argument
504  // operands. This means there is no need to adjust UseIndex to account
505  // for these.
506 
507  unsigned UseIndex = std::distance(CS.arg_begin(), U);
508 
509  // U cannot be the callee operand use: since we're exploring the
510  // transitive uses of an Argument, having such a use be a callee would
511  // imply the CallSite is an indirect call or invoke; and we'd take the
512  // early exit above.
513  assert(UseIndex < CS.data_operands_size() &&
514  "Data operand use expected!");
515 
516  bool IsOperandBundleUse = UseIndex >= CS.getNumArgOperands();
517 
518  if (UseIndex >= F->arg_size() && !IsOperandBundleUse) {
519  assert(F->isVarArg() && "More params than args in non-varargs call");
520  return Attribute::None;
521  }
522 
523  Captures &= !CS.doesNotCapture(UseIndex);
524 
525  // Since the optimizer (by design) cannot see the data flow corresponding
526  // to a operand bundle use, these cannot participate in the optimistic SCC
527  // analysis. Instead, we model the operand bundle uses as arguments in
528  // call to a function external to the SCC.
529  if (IsOperandBundleUse ||
530  !SCCNodes.count(&*std::next(F->arg_begin(), UseIndex))) {
531 
532  // The accessors used on CallSite here do the right thing for calls and
533  // invokes with operand bundles.
534 
535  if (!CS.onlyReadsMemory() && !CS.onlyReadsMemory(UseIndex))
536  return Attribute::None;
537  if (!CS.doesNotAccessMemory(UseIndex))
538  IsRead = true;
539  }
540 
541  AddUsersToWorklistIfCapturing();
542  break;
543  }
544 
545  case Instruction::Load:
546  // A volatile load has side effects beyond what readonly can be relied
547  // upon.
548  if (cast<LoadInst>(I)->isVolatile())
549  return Attribute::None;
550 
551  IsRead = true;
552  break;
553 
554  case Instruction::ICmp:
555  case Instruction::Ret:
556  break;
557 
558  default:
559  return Attribute::None;
560  }
561  }
562 
563  return IsRead ? Attribute::ReadOnly : Attribute::ReadNone;
564 }
565 
566 /// Deduce returned attributes for the SCC.
567 static bool addArgumentReturnedAttrs(const SCCNodeSet &SCCNodes) {
568  bool Changed = false;
569 
570  // Check each function in turn, determining if an argument is always returned.
571  for (Function *F : SCCNodes) {
572  // We can infer and propagate function attributes only when we know that the
573  // definition we'll get at link time is *exactly* the definition we see now.
574  // For more details, see GlobalValue::mayBeDerefined.
575  if (!F->hasExactDefinition())
576  continue;
577 
578  if (F->getReturnType()->isVoidTy())
579  continue;
580 
581  // There is nothing to do if an argument is already marked as 'returned'.
582  if (llvm::any_of(F->args(),
583  [](const Argument &Arg) { return Arg.hasReturnedAttr(); }))
584  continue;
585 
586  auto FindRetArg = [&]() -> Value * {
587  Value *RetArg = nullptr;
588  for (BasicBlock &BB : *F)
589  if (auto *Ret = dyn_cast<ReturnInst>(BB.getTerminator())) {
590  // Note that stripPointerCasts should look through functions with
591  // returned arguments.
592  Value *RetVal = Ret->getReturnValue()->stripPointerCasts();
593  if (!isa<Argument>(RetVal) || RetVal->getType() != F->getReturnType())
594  return nullptr;
595 
596  if (!RetArg)
597  RetArg = RetVal;
598  else if (RetArg != RetVal)
599  return nullptr;
600  }
601 
602  return RetArg;
603  };
604 
605  if (Value *RetArg = FindRetArg()) {
606  auto *A = cast<Argument>(RetArg);
607  A->addAttr(Attribute::Returned);
608  ++NumReturned;
609  Changed = true;
610  }
611  }
612 
613  return Changed;
614 }
615 
616 /// If a callsite has arguments that are also arguments to the parent function,
617 /// try to propagate attributes from the callsite's arguments to the parent's
618 /// arguments. This may be important because inlining can cause information loss
619 /// when attribute knowledge disappears with the inlined call.
622  return false;
623 
624  bool Changed = false;
625 
626  // For an argument attribute to transfer from a callsite to the parent, the
627  // call must be guaranteed to execute every time the parent is called.
628  // Conservatively, just check for calls in the entry block that are guaranteed
629  // to execute.
630  // TODO: This could be enhanced by testing if the callsite post-dominates the
631  // entry block or by doing simple forward walks or backward walks to the
632  // callsite.
633  BasicBlock &Entry = F.getEntryBlock();
634  for (Instruction &I : Entry) {
635  if (auto CS = CallSite(&I)) {
636  if (auto *CalledFunc = CS.getCalledFunction()) {
637  for (auto &CSArg : CalledFunc->args()) {
638  if (!CSArg.hasNonNullAttr())
639  continue;
640 
641  // If the non-null callsite argument operand is an argument to 'F'
642  // (the caller) and the call is guaranteed to execute, then the value
643  // must be non-null throughout 'F'.
644  auto *FArg = dyn_cast<Argument>(CS.getArgOperand(CSArg.getArgNo()));
645  if (FArg && !FArg->hasNonNullAttr()) {
646  FArg->addAttr(Attribute::NonNull);
647  Changed = true;
648  }
649  }
650  }
651  }
653  break;
654  }
655 
656  return Changed;
657 }
658 
659 /// Deduce nocapture attributes for the SCC.
660 static bool addArgumentAttrs(const SCCNodeSet &SCCNodes) {
661  bool Changed = false;
662 
663  ArgumentGraph AG;
664 
665  // Check each function in turn, determining which pointer arguments are not
666  // captured.
667  for (Function *F : SCCNodes) {
668  // We can infer and propagate function attributes only when we know that the
669  // definition we'll get at link time is *exactly* the definition we see now.
670  // For more details, see GlobalValue::mayBeDerefined.
671  if (!F->hasExactDefinition())
672  continue;
673 
674  Changed |= addArgumentAttrsFromCallsites(*F);
675 
676  // Functions that are readonly (or readnone) and nounwind and don't return
677  // a value can't capture arguments. Don't analyze them.
678  if (F->onlyReadsMemory() && F->doesNotThrow() &&
679  F->getReturnType()->isVoidTy()) {
680  for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end(); A != E;
681  ++A) {
682  if (A->getType()->isPointerTy() && !A->hasNoCaptureAttr()) {
683  A->addAttr(Attribute::NoCapture);
684  ++NumNoCapture;
685  Changed = true;
686  }
687  }
688  continue;
689  }
690 
691  for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end(); A != E;
692  ++A) {
693  if (!A->getType()->isPointerTy())
694  continue;
695  bool HasNonLocalUses = false;
696  if (!A->hasNoCaptureAttr()) {
697  ArgumentUsesTracker Tracker(SCCNodes);
698  PointerMayBeCaptured(&*A, &Tracker);
699  if (!Tracker.Captured) {
700  if (Tracker.Uses.empty()) {
701  // If it's trivially not captured, mark it nocapture now.
702  A->addAttr(Attribute::NoCapture);
703  ++NumNoCapture;
704  Changed = true;
705  } else {
706  // If it's not trivially captured and not trivially not captured,
707  // then it must be calling into another function in our SCC. Save
708  // its particulars for Argument-SCC analysis later.
709  ArgumentGraphNode *Node = AG[&*A];
710  for (Argument *Use : Tracker.Uses) {
711  Node->Uses.push_back(AG[Use]);
712  if (Use != &*A)
713  HasNonLocalUses = true;
714  }
715  }
716  }
717  // Otherwise, it's captured. Don't bother doing SCC analysis on it.
718  }
719  if (!HasNonLocalUses && !A->onlyReadsMemory()) {
720  // Can we determine that it's readonly/readnone without doing an SCC?
721  // Note that we don't allow any calls at all here, or else our result
722  // will be dependent on the iteration order through the functions in the
723  // SCC.
725  Self.insert(&*A);
727  if (R != Attribute::None) {
728  A->addAttr(R);
729  Changed = true;
730  R == Attribute::ReadOnly ? ++NumReadOnlyArg : ++NumReadNoneArg;
731  }
732  }
733  }
734  }
735 
736  // The graph we've collected is partial because we stopped scanning for
737  // argument uses once we solved the argument trivially. These partial nodes
738  // show up as ArgumentGraphNode objects with an empty Uses list, and for
739  // these nodes the final decision about whether they capture has already been
740  // made. If the definition doesn't have a 'nocapture' attribute by now, it
741  // captures.
742 
743  for (scc_iterator<ArgumentGraph *> I = scc_begin(&AG); !I.isAtEnd(); ++I) {
744  const std::vector<ArgumentGraphNode *> &ArgumentSCC = *I;
745  if (ArgumentSCC.size() == 1) {
746  if (!ArgumentSCC[0]->Definition)
747  continue; // synthetic root node
748 
749  // eg. "void f(int* x) { if (...) f(x); }"
750  if (ArgumentSCC[0]->Uses.size() == 1 &&
751  ArgumentSCC[0]->Uses[0] == ArgumentSCC[0]) {
752  Argument *A = ArgumentSCC[0]->Definition;
753  A->addAttr(Attribute::NoCapture);
754  ++NumNoCapture;
755  Changed = true;
756  }
757  continue;
758  }
759 
760  bool SCCCaptured = false;
761  for (auto I = ArgumentSCC.begin(), E = ArgumentSCC.end();
762  I != E && !SCCCaptured; ++I) {
763  ArgumentGraphNode *Node = *I;
764  if (Node->Uses.empty()) {
765  if (!Node->Definition->hasNoCaptureAttr())
766  SCCCaptured = true;
767  }
768  }
769  if (SCCCaptured)
770  continue;
771 
772  SmallPtrSet<Argument *, 8> ArgumentSCCNodes;
773  // Fill ArgumentSCCNodes with the elements of the ArgumentSCC. Used for
774  // quickly looking up whether a given Argument is in this ArgumentSCC.
775  for (ArgumentGraphNode *I : ArgumentSCC) {
776  ArgumentSCCNodes.insert(I->Definition);
777  }
778 
779  for (auto I = ArgumentSCC.begin(), E = ArgumentSCC.end();
780  I != E && !SCCCaptured; ++I) {
781  ArgumentGraphNode *N = *I;
782  for (ArgumentGraphNode *Use : N->Uses) {
783  Argument *A = Use->Definition;
784  if (A->hasNoCaptureAttr() || ArgumentSCCNodes.count(A))
785  continue;
786  SCCCaptured = true;
787  break;
788  }
789  }
790  if (SCCCaptured)
791  continue;
792 
793  for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) {
794  Argument *A = ArgumentSCC[i]->Definition;
795  A->addAttr(Attribute::NoCapture);
796  ++NumNoCapture;
797  Changed = true;
798  }
799 
800  // We also want to compute readonly/readnone. With a small number of false
801  // negatives, we can assume that any pointer which is captured isn't going
802  // to be provably readonly or readnone, since by definition we can't
803  // analyze all uses of a captured pointer.
804  //
805  // The false negatives happen when the pointer is captured by a function
806  // that promises readonly/readnone behaviour on the pointer, then the
807  // pointer's lifetime ends before anything that writes to arbitrary memory.
808  // Also, a readonly/readnone pointer may be returned, but returning a
809  // pointer is capturing it.
810 
811  Attribute::AttrKind ReadAttr = Attribute::ReadNone;
812  for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) {
813  Argument *A = ArgumentSCC[i]->Definition;
814  Attribute::AttrKind K = determinePointerReadAttrs(A, ArgumentSCCNodes);
815  if (K == Attribute::ReadNone)
816  continue;
817  if (K == Attribute::ReadOnly) {
818  ReadAttr = Attribute::ReadOnly;
819  continue;
820  }
821  ReadAttr = K;
822  break;
823  }
824 
825  if (ReadAttr != Attribute::None) {
826  for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) {
827  Argument *A = ArgumentSCC[i]->Definition;
828  // Clear out existing readonly/readnone attributes
829  A->removeAttr(Attribute::ReadOnly);
830  A->removeAttr(Attribute::ReadNone);
831  A->addAttr(ReadAttr);
832  ReadAttr == Attribute::ReadOnly ? ++NumReadOnlyArg : ++NumReadNoneArg;
833  Changed = true;
834  }
835  }
836  }
837 
838  return Changed;
839 }
840 
841 /// Tests whether a function is "malloc-like".
842 ///
843 /// A function is "malloc-like" if it returns either null or a pointer that
844 /// doesn't alias any other pointer visible to the caller.
845 static bool isFunctionMallocLike(Function *F, const SCCNodeSet &SCCNodes) {
846  SmallSetVector<Value *, 8> FlowsToReturn;
847  for (BasicBlock &BB : *F)
848  if (ReturnInst *Ret = dyn_cast<ReturnInst>(BB.getTerminator()))
849  FlowsToReturn.insert(Ret->getReturnValue());
850 
851  for (unsigned i = 0; i != FlowsToReturn.size(); ++i) {
852  Value *RetVal = FlowsToReturn[i];
853 
854  if (Constant *C = dyn_cast<Constant>(RetVal)) {
855  if (!C->isNullValue() && !isa<UndefValue>(C))
856  return false;
857 
858  continue;
859  }
860 
861  if (isa<Argument>(RetVal))
862  return false;
863 
864  if (Instruction *RVI = dyn_cast<Instruction>(RetVal))
865  switch (RVI->getOpcode()) {
866  // Extend the analysis by looking upwards.
867  case Instruction::BitCast:
868  case Instruction::GetElementPtr:
869  case Instruction::AddrSpaceCast:
870  FlowsToReturn.insert(RVI->getOperand(0));
871  continue;
872  case Instruction::Select: {
873  SelectInst *SI = cast<SelectInst>(RVI);
874  FlowsToReturn.insert(SI->getTrueValue());
875  FlowsToReturn.insert(SI->getFalseValue());
876  continue;
877  }
878  case Instruction::PHI: {
879  PHINode *PN = cast<PHINode>(RVI);
880  for (Value *IncValue : PN->incoming_values())
881  FlowsToReturn.insert(IncValue);
882  continue;
883  }
884 
885  // Check whether the pointer came from an allocation.
886  case Instruction::Alloca:
887  break;
888  case Instruction::Call:
889  case Instruction::Invoke: {
890  CallSite CS(RVI);
892  break;
893  if (CS.getCalledFunction() && SCCNodes.count(CS.getCalledFunction()))
894  break;
896  }
897  default:
898  return false; // Did not come from an allocation.
899  }
900 
901  if (PointerMayBeCaptured(RetVal, false, /*StoreCaptures=*/false))
902  return false;
903  }
904 
905  return true;
906 }
907 
908 /// Deduce noalias attributes for the SCC.
909 static bool addNoAliasAttrs(const SCCNodeSet &SCCNodes) {
910  // Check each function in turn, determining which functions return noalias
911  // pointers.
912  for (Function *F : SCCNodes) {
913  // Already noalias.
914  if (F->returnDoesNotAlias())
915  continue;
916 
917  // We can infer and propagate function attributes only when we know that the
918  // definition we'll get at link time is *exactly* the definition we see now.
919  // For more details, see GlobalValue::mayBeDerefined.
920  if (!F->hasExactDefinition())
921  return false;
922 
923  // We annotate noalias return values, which are only applicable to
924  // pointer types.
925  if (!F->getReturnType()->isPointerTy())
926  continue;
927 
928  if (!isFunctionMallocLike(F, SCCNodes))
929  return false;
930  }
931 
932  bool MadeChange = false;
933  for (Function *F : SCCNodes) {
934  if (F->returnDoesNotAlias() ||
935  !F->getReturnType()->isPointerTy())
936  continue;
937 
938  F->setReturnDoesNotAlias();
939  ++NumNoAlias;
940  MadeChange = true;
941  }
942 
943  return MadeChange;
944 }
945 
946 /// Tests whether this function is known to not return null.
947 ///
948 /// Requires that the function returns a pointer.
949 ///
950 /// Returns true if it believes the function will not return a null, and sets
951 /// \p Speculative based on whether the returned conclusion is a speculative
952 /// conclusion due to SCC calls.
953 static bool isReturnNonNull(Function *F, const SCCNodeSet &SCCNodes,
954  bool &Speculative) {
955  assert(F->getReturnType()->isPointerTy() &&
956  "nonnull only meaningful on pointer types");
957  Speculative = false;
958 
959  SmallSetVector<Value *, 8> FlowsToReturn;
960  for (BasicBlock &BB : *F)
961  if (auto *Ret = dyn_cast<ReturnInst>(BB.getTerminator()))
962  FlowsToReturn.insert(Ret->getReturnValue());
963 
964  auto &DL = F->getParent()->getDataLayout();
965 
966  for (unsigned i = 0; i != FlowsToReturn.size(); ++i) {
967  Value *RetVal = FlowsToReturn[i];
968 
969  // If this value is locally known to be non-null, we're good
970  if (isKnownNonZero(RetVal, DL))
971  continue;
972 
973  // Otherwise, we need to look upwards since we can't make any local
974  // conclusions.
975  Instruction *RVI = dyn_cast<Instruction>(RetVal);
976  if (!RVI)
977  return false;
978  switch (RVI->getOpcode()) {
979  // Extend the analysis by looking upwards.
980  case Instruction::BitCast:
981  case Instruction::GetElementPtr:
982  case Instruction::AddrSpaceCast:
983  FlowsToReturn.insert(RVI->getOperand(0));
984  continue;
985  case Instruction::Select: {
986  SelectInst *SI = cast<SelectInst>(RVI);
987  FlowsToReturn.insert(SI->getTrueValue());
988  FlowsToReturn.insert(SI->getFalseValue());
989  continue;
990  }
991  case Instruction::PHI: {
992  PHINode *PN = cast<PHINode>(RVI);
993  for (int i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
994  FlowsToReturn.insert(PN->getIncomingValue(i));
995  continue;
996  }
997  case Instruction::Call:
998  case Instruction::Invoke: {
999  CallSite CS(RVI);
1001  // A call to a node within the SCC is assumed to return null until
1002  // proven otherwise
1003  if (Callee && SCCNodes.count(Callee)) {
1004  Speculative = true;
1005  continue;
1006  }
1007  return false;
1008  }
1009  default:
1010  return false; // Unknown source, may be null
1011  };
1012  llvm_unreachable("should have either continued or returned");
1013  }
1014 
1015  return true;
1016 }
1017 
1018 /// Deduce nonnull attributes for the SCC.
1019 static bool addNonNullAttrs(const SCCNodeSet &SCCNodes) {
1020  // Speculative that all functions in the SCC return only nonnull
1021  // pointers. We may refute this as we analyze functions.
1022  bool SCCReturnsNonNull = true;
1023 
1024  bool MadeChange = false;
1025 
1026  // Check each function in turn, determining which functions return nonnull
1027  // pointers.
1028  for (Function *F : SCCNodes) {
1029  // Already nonnull.
1030  if (F->getAttributes().hasAttribute(AttributeList::ReturnIndex,
1031  Attribute::NonNull))
1032  continue;
1033 
1034  // We can infer and propagate function attributes only when we know that the
1035  // definition we'll get at link time is *exactly* the definition we see now.
1036  // For more details, see GlobalValue::mayBeDerefined.
1037  if (!F->hasExactDefinition())
1038  return false;
1039 
1040  // We annotate nonnull return values, which are only applicable to
1041  // pointer types.
1042  if (!F->getReturnType()->isPointerTy())
1043  continue;
1044 
1045  bool Speculative = false;
1046  if (isReturnNonNull(F, SCCNodes, Speculative)) {
1047  if (!Speculative) {
1048  // Mark the function eagerly since we may discover a function
1049  // which prevents us from speculating about the entire SCC
1050  LLVM_DEBUG(dbgs() << "Eagerly marking " << F->getName()
1051  << " as nonnull\n");
1052  F->addAttribute(AttributeList::ReturnIndex, Attribute::NonNull);
1053  ++NumNonNullReturn;
1054  MadeChange = true;
1055  }
1056  continue;
1057  }
1058  // At least one function returns something which could be null, can't
1059  // speculate any more.
1060  SCCReturnsNonNull = false;
1061  }
1062 
1063  if (SCCReturnsNonNull) {
1064  for (Function *F : SCCNodes) {
1065  if (F->getAttributes().hasAttribute(AttributeList::ReturnIndex,
1066  Attribute::NonNull) ||
1067  !F->getReturnType()->isPointerTy())
1068  continue;
1069 
1070  LLVM_DEBUG(dbgs() << "SCC marking " << F->getName() << " as nonnull\n");
1071  F->addAttribute(AttributeList::ReturnIndex, Attribute::NonNull);
1072  ++NumNonNullReturn;
1073  MadeChange = true;
1074  }
1075  }
1076 
1077  return MadeChange;
1078 }
1079 
1080 namespace {
1081 
1082 /// Collects a set of attribute inference requests and performs them all in one
1083 /// go on a single SCC Node. Inference involves scanning function bodies
1084 /// looking for instructions that violate attribute assumptions.
1085 /// As soon as all the bodies are fine we are free to set the attribute.
1086 /// Customization of inference for individual attributes is performed by
1087 /// providing a handful of predicates for each attribute.
1088 class AttributeInferer {
1089 public:
1090  /// Describes a request for inference of a single attribute.
1091  struct InferenceDescriptor {
1092 
1093  /// Returns true if this function does not have to be handled.
1094  /// General intent for this predicate is to provide an optimization
1095  /// for functions that do not need this attribute inference at all
1096  /// (say, for functions that already have the attribute).
1097  std::function<bool(const Function &)> SkipFunction;
1098 
1099  /// Returns true if this instruction violates attribute assumptions.
1100  std::function<bool(Instruction &)> InstrBreaksAttribute;
1101 
1102  /// Sets the inferred attribute for this function.
1103  std::function<void(Function &)> SetAttribute;
1104 
1105  /// Attribute we derive.
1106  Attribute::AttrKind AKind;
1107 
1108  /// If true, only "exact" definitions can be used to infer this attribute.
1109  /// See GlobalValue::isDefinitionExact.
1110  bool RequiresExactDefinition;
1111 
1112  InferenceDescriptor(Attribute::AttrKind AK,
1113  std::function<bool(const Function &)> SkipFunc,
1114  std::function<bool(Instruction &)> InstrScan,
1115  std::function<void(Function &)> SetAttr,
1116  bool ReqExactDef)
1117  : SkipFunction(SkipFunc), InstrBreaksAttribute(InstrScan),
1118  SetAttribute(SetAttr), AKind(AK),
1119  RequiresExactDefinition(ReqExactDef) {}
1120  };
1121 
1122 private:
1123  SmallVector<InferenceDescriptor, 4> InferenceDescriptors;
1124 
1125 public:
1126  void registerAttrInference(InferenceDescriptor AttrInference) {
1127  InferenceDescriptors.push_back(AttrInference);
1128  }
1129 
1130  bool run(const SCCNodeSet &SCCNodes);
1131 };
1132 
1133 /// Perform all the requested attribute inference actions according to the
1134 /// attribute predicates stored before.
1135 bool AttributeInferer::run(const SCCNodeSet &SCCNodes) {
1136  SmallVector<InferenceDescriptor, 4> InferInSCC = InferenceDescriptors;
1137  // Go through all the functions in SCC and check corresponding attribute
1138  // assumptions for each of them. Attributes that are invalid for this SCC
1139  // will be removed from InferInSCC.
1140  for (Function *F : SCCNodes) {
1141 
1142  // No attributes whose assumptions are still valid - done.
1143  if (InferInSCC.empty())
1144  return false;
1145 
1146  // Check if our attributes ever need scanning/can be scanned.
1147  llvm::erase_if(InferInSCC, [F](const InferenceDescriptor &ID) {
1148  if (ID.SkipFunction(*F))
1149  return false;
1150 
1151  // Remove from further inference (invalidate) when visiting a function
1152  // that has no instructions to scan/has an unsuitable definition.
1153  return F->isDeclaration() ||
1154  (ID.RequiresExactDefinition && !F->hasExactDefinition());
1155  });
1156 
1157  // For each attribute still in InferInSCC that doesn't explicitly skip F,
1158  // set up the F instructions scan to verify assumptions of the attribute.
1159  SmallVector<InferenceDescriptor, 4> InferInThisFunc;
1160  llvm::copy_if(
1161  InferInSCC, std::back_inserter(InferInThisFunc),
1162  [F](const InferenceDescriptor &ID) { return !ID.SkipFunction(*F); });
1163 
1164  if (InferInThisFunc.empty())
1165  continue;
1166 
1167  // Start instruction scan.
1168  for (Instruction &I : instructions(*F)) {
1169  llvm::erase_if(InferInThisFunc, [&](const InferenceDescriptor &ID) {
1170  if (!ID.InstrBreaksAttribute(I))
1171  return false;
1172  // Remove attribute from further inference on any other functions
1173  // because attribute assumptions have just been violated.
1174  llvm::erase_if(InferInSCC, [&ID](const InferenceDescriptor &D) {
1175  return D.AKind == ID.AKind;
1176  });
1177  // Remove attribute from the rest of current instruction scan.
1178  return true;
1179  });
1180 
1181  if (InferInThisFunc.empty())
1182  break;
1183  }
1184  }
1185 
1186  if (InferInSCC.empty())
1187  return false;
1188 
1189  bool Changed = false;
1190  for (Function *F : SCCNodes)
1191  // At this point InferInSCC contains only functions that were either:
1192  // - explicitly skipped from scan/inference, or
1193  // - verified to have no instructions that break attribute assumptions.
1194  // Hence we just go and force the attribute for all non-skipped functions.
1195  for (auto &ID : InferInSCC) {
1196  if (ID.SkipFunction(*F))
1197  continue;
1198  Changed = true;
1199  ID.SetAttribute(*F);
1200  }
1201  return Changed;
1202 }
1203 
1204 } // end anonymous namespace
1205 
1206 /// Helper for non-Convergent inference predicate InstrBreaksAttribute.
1208  const SCCNodeSet &SCCNodes) {
1209  const CallSite CS(&I);
1210  // Breaks non-convergent assumption if CS is a convergent call to a function
1211  // not in the SCC.
1212  return CS && CS.isConvergent() && SCCNodes.count(CS.getCalledFunction()) == 0;
1213 }
1214 
1215 /// Helper for NoUnwind inference predicate InstrBreaksAttribute.
1216 static bool InstrBreaksNonThrowing(Instruction &I, const SCCNodeSet &SCCNodes) {
1217  if (!I.mayThrow())
1218  return false;
1219  if (const auto *CI = dyn_cast<CallInst>(&I)) {
1220  if (Function *Callee = CI->getCalledFunction()) {
1221  // I is a may-throw call to a function inside our SCC. This doesn't
1222  // invalidate our current working assumption that the SCC is no-throw; we
1223  // just have to scan that other function.
1224  if (SCCNodes.count(Callee) > 0)
1225  return false;
1226  }
1227  }
1228  return true;
1229 }
1230 
1231 /// Infer attributes from all functions in the SCC by scanning every
1232 /// instruction for compliance to the attribute assumptions. Currently it
1233 /// does:
1234 /// - removal of Convergent attribute
1235 /// - addition of NoUnwind attribute
1236 ///
1237 /// Returns true if any changes to function attributes were made.
1238 static bool inferAttrsFromFunctionBodies(const SCCNodeSet &SCCNodes) {
1239 
1240  AttributeInferer AI;
1241 
1242  // Request to remove the convergent attribute from all functions in the SCC
1243  // if every callsite within the SCC is not convergent (except for calls
1244  // to functions within the SCC).
1245  // Note: Removal of the attr from the callsites will happen in
1246  // InstCombineCalls separately.
1247  AI.registerAttrInference(AttributeInferer::InferenceDescriptor{
1249  // Skip non-convergent functions.
1250  [](const Function &F) { return !F.isConvergent(); },
1251  // Instructions that break non-convergent assumption.
1252  [SCCNodes](Instruction &I) {
1253  return InstrBreaksNonConvergent(I, SCCNodes);
1254  },
1255  [](Function &F) {
1256  LLVM_DEBUG(dbgs() << "Removing convergent attr from fn " << F.getName()
1257  << "\n");
1258  F.setNotConvergent();
1259  },
1260  /* RequiresExactDefinition= */ false});
1261 
1263  // Request to infer nounwind attribute for all the functions in the SCC if
1264  // every callsite within the SCC is not throwing (except for calls to
1265  // functions within the SCC). Note that nounwind attribute suffers from
1266  // derefinement - results may change depending on how functions are
1267  // optimized. Thus it can be inferred only from exact definitions.
1268  AI.registerAttrInference(AttributeInferer::InferenceDescriptor{
1269  Attribute::NoUnwind,
1270  // Skip non-throwing functions.
1271  [](const Function &F) { return F.doesNotThrow(); },
1272  // Instructions that break non-throwing assumption.
1273  [SCCNodes](Instruction &I) {
1274  return InstrBreaksNonThrowing(I, SCCNodes);
1275  },
1276  [](Function &F) {
1277  LLVM_DEBUG(dbgs()
1278  << "Adding nounwind attr to fn " << F.getName() << "\n");
1279  F.setDoesNotThrow();
1280  ++NumNoUnwind;
1281  },
1282  /* RequiresExactDefinition= */ true});
1283 
1284  // Perform all the requested attribute inference actions.
1285  return AI.run(SCCNodes);
1286 }
1287 
1289  if (F.doesNotRecurse())
1290  return false;
1291  F.setDoesNotRecurse();
1292  ++NumNoRecurse;
1293  return true;
1294 }
1295 
1296 static bool addNoRecurseAttrs(const SCCNodeSet &SCCNodes) {
1297  // Try and identify functions that do not recurse.
1298 
1299  // If the SCC contains multiple nodes we know for sure there is recursion.
1300  if (SCCNodes.size() != 1)
1301  return false;
1302 
1303  Function *F = *SCCNodes.begin();
1304  if (!F || F->isDeclaration() || F->doesNotRecurse())
1305  return false;
1306 
1307  // If all of the calls in F are identifiable and are to norecurse functions, F
1308  // is norecurse. This check also detects self-recursion as F is not currently
1309  // marked norecurse, so any called from F to F will not be marked norecurse.
1310  for (Instruction &I : instructions(*F))
1311  if (auto CS = CallSite(&I)) {
1312  Function *Callee = CS.getCalledFunction();
1313  if (!Callee || Callee == F || !Callee->doesNotRecurse())
1314  // Function calls a potentially recursive function.
1315  return false;
1316  }
1317 
1318  // Every call was to a non-recursive function other than this function, and
1319  // we have no indirect recursion as the SCC size is one. This function cannot
1320  // recurse.
1321  return setDoesNotRecurse(*F);
1322 }
1323 
1324 template <typename AARGetterT>
1325 static bool deriveAttrsInPostOrder(SCCNodeSet &SCCNodes, AARGetterT &&AARGetter,
1326  bool HasUnknownCall) {
1327  bool Changed = false;
1328 
1329  // Bail if the SCC only contains optnone functions.
1330  if (SCCNodes.empty())
1331  return Changed;
1332 
1333  Changed |= addArgumentReturnedAttrs(SCCNodes);
1334  Changed |= addReadAttrs(SCCNodes, AARGetter);
1335  Changed |= addArgumentAttrs(SCCNodes);
1336 
1337  // If we have no external nodes participating in the SCC, we can deduce some
1338  // more precise attributes as well.
1339  if (!HasUnknownCall) {
1340  Changed |= addNoAliasAttrs(SCCNodes);
1341  Changed |= addNonNullAttrs(SCCNodes);
1342  Changed |= inferAttrsFromFunctionBodies(SCCNodes);
1343  Changed |= addNoRecurseAttrs(SCCNodes);
1344  }
1345 
1346  return Changed;
1347 }
1348 
1351  LazyCallGraph &CG,
1352  CGSCCUpdateResult &) {
1354  AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C, CG).getManager();
1355 
1356  // We pass a lambda into functions to wire them up to the analysis manager
1357  // for getting function analyses.
1358  auto AARGetter = [&](Function &F) -> AAResults & {
1359  return FAM.getResult<AAManager>(F);
1360  };
1361 
1362  // Fill SCCNodes with the elements of the SCC. Also track whether there are
1363  // any external or opt-none nodes that will prevent us from optimizing any
1364  // part of the SCC.
1365  SCCNodeSet SCCNodes;
1366  bool HasUnknownCall = false;
1367  for (LazyCallGraph::Node &N : C) {
1368  Function &F = N.getFunction();
1369  if (F.hasFnAttribute(Attribute::OptimizeNone) ||
1370  F.hasFnAttribute(Attribute::Naked)) {
1371  // Treat any function we're trying not to optimize as if it were an
1372  // indirect call and omit it from the node set used below.
1373  HasUnknownCall = true;
1374  continue;
1375  }
1376  // Track whether any functions in this SCC have an unknown call edge.
1377  // Note: if this is ever a performance hit, we can common it with
1378  // subsequent routines which also do scans over the instructions of the
1379  // function.
1380  if (!HasUnknownCall)
1381  for (Instruction &I : instructions(F))
1382  if (auto CS = CallSite(&I))
1383  if (!CS.getCalledFunction()) {
1384  HasUnknownCall = true;
1385  break;
1386  }
1387 
1388  SCCNodes.insert(&F);
1389  }
1390 
1391  if (deriveAttrsInPostOrder(SCCNodes, AARGetter, HasUnknownCall))
1392  return PreservedAnalyses::none();
1393 
1394  return PreservedAnalyses::all();
1395 }
1396 
1397 namespace {
1398 
1399 struct PostOrderFunctionAttrsLegacyPass : public CallGraphSCCPass {
1400  // Pass identification, replacement for typeid
1401  static char ID;
1402 
1403  PostOrderFunctionAttrsLegacyPass() : CallGraphSCCPass(ID) {
1406  }
1407 
1408  bool runOnSCC(CallGraphSCC &SCC) override;
1409 
1410  void getAnalysisUsage(AnalysisUsage &AU) const override {
1411  AU.setPreservesCFG();
1415  }
1416 };
1417 
1418 } // end anonymous namespace
1419 
1421 INITIALIZE_PASS_BEGIN(PostOrderFunctionAttrsLegacyPass, "functionattrs",
1422  "Deduce function attributes", false, false)
1425 INITIALIZE_PASS_END(PostOrderFunctionAttrsLegacyPass, "functionattrs",
1426  "Deduce function attributes", false, false)
1427 
1429  return new PostOrderFunctionAttrsLegacyPass();
1430 }
1431 
1432 template <typename AARGetterT>
1433 static bool runImpl(CallGraphSCC &SCC, AARGetterT AARGetter) {
1434 
1435  // Fill SCCNodes with the elements of the SCC. Used for quickly looking up
1436  // whether a given CallGraphNode is in this SCC. Also track whether there are
1437  // any external or opt-none nodes that will prevent us from optimizing any
1438  // part of the SCC.
1439  SCCNodeSet SCCNodes;
1440  bool ExternalNode = false;
1441  for (CallGraphNode *I : SCC) {
1442  Function *F = I->getFunction();
1443  if (!F || F->hasFnAttribute(Attribute::OptimizeNone) ||
1444  F->hasFnAttribute(Attribute::Naked)) {
1445  // External node or function we're trying not to optimize - we both avoid
1446  // transform them and avoid leveraging information they provide.
1447  ExternalNode = true;
1448  continue;
1449  }
1450 
1451  SCCNodes.insert(F);
1452  }
1453 
1454  return deriveAttrsInPostOrder(SCCNodes, AARGetter, ExternalNode);
1455 }
1456 
1457 bool PostOrderFunctionAttrsLegacyPass::runOnSCC(CallGraphSCC &SCC) {
1458  if (skipSCC(SCC))
1459  return false;
1460  return runImpl(SCC, LegacyAARGetter(*this));
1461 }
1462 
1463 namespace {
1464 
1465 struct ReversePostOrderFunctionAttrsLegacyPass : public ModulePass {
1466  // Pass identification, replacement for typeid
1467  static char ID;
1468 
1469  ReversePostOrderFunctionAttrsLegacyPass() : ModulePass(ID) {
1472  }
1473 
1474  bool runOnModule(Module &M) override;
1475 
1476  void getAnalysisUsage(AnalysisUsage &AU) const override {
1477  AU.setPreservesCFG();
1480  }
1481 };
1482 
1483 } // end anonymous namespace
1484 
1486 
1487 INITIALIZE_PASS_BEGIN(ReversePostOrderFunctionAttrsLegacyPass, "rpo-functionattrs",
1488  "Deduce function attributes in RPO", false, false)
1490 INITIALIZE_PASS_END(ReversePostOrderFunctionAttrsLegacyPass, "rpo-functionattrs",
1491  "Deduce function attributes in RPO", false, false)
1492 
1494  return new ReversePostOrderFunctionAttrsLegacyPass();
1495 }
1496 
1498  // We check the preconditions for the function prior to calling this to avoid
1499  // the cost of building up a reversible post-order list. We assert them here
1500  // to make sure none of the invariants this relies on were violated.
1501  assert(!F.isDeclaration() && "Cannot deduce norecurse without a definition!");
1502  assert(!F.doesNotRecurse() &&
1503  "This function has already been deduced as norecurs!");
1504  assert(F.hasInternalLinkage() &&
1505  "Can only do top-down deduction for internal linkage functions!");
1506 
1507  // If F is internal and all of its uses are calls from a non-recursive
1508  // functions, then none of its calls could in fact recurse without going
1509  // through a function marked norecurse, and so we can mark this function too
1510  // as norecurse. Note that the uses must actually be calls -- otherwise
1511  // a pointer to this function could be returned from a norecurse function but
1512  // this function could be recursively (indirectly) called. Note that this
1513  // also detects if F is directly recursive as F is not yet marked as
1514  // a norecurse function.
1515  for (auto *U : F.users()) {
1516  auto *I = dyn_cast<Instruction>(U);
1517  if (!I)
1518  return false;
1519  CallSite CS(I);
1520  if (!CS || !CS.getParent()->getParent()->doesNotRecurse())
1521  return false;
1522  }
1523  return setDoesNotRecurse(F);
1524 }
1525 
1527  // We only have a post-order SCC traversal (because SCCs are inherently
1528  // discovered in post-order), so we accumulate them in a vector and then walk
1529  // it in reverse. This is simpler than using the RPO iterator infrastructure
1530  // because we need to combine SCC detection and the PO walk of the call
1531  // graph. We can also cheat egregiously because we're primarily interested in
1532  // synthesizing norecurse and so we can only save the singular SCCs as SCCs
1533  // with multiple functions in them will clearly be recursive.
1534  SmallVector<Function *, 16> Worklist;
1535  for (scc_iterator<CallGraph *> I = scc_begin(&CG); !I.isAtEnd(); ++I) {
1536  if (I->size() != 1)
1537  continue;
1538 
1539  Function *F = I->front()->getFunction();
1540  if (F && !F->isDeclaration() && !F->doesNotRecurse() &&
1541  F->hasInternalLinkage())
1542  Worklist.push_back(F);
1543  }
1544 
1545  bool Changed = false;
1546  for (auto *F : llvm::reverse(Worklist))
1547  Changed |= addNoRecurseAttrsTopDown(*F);
1548 
1549  return Changed;
1550 }
1551 
1552 bool ReversePostOrderFunctionAttrsLegacyPass::runOnModule(Module &M) {
1553  if (skipModule(M))
1554  return false;
1555 
1556  auto &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph();
1557 
1558  return deduceFunctionAttributeInRPO(M, CG);
1559 }
1560 
1563  auto &CG = AM.getResult<CallGraphAnalysis>(M);
1564 
1565  if (!deduceFunctionAttributeInRPO(M, CG))
1566  return PreservedAnalyses::all();
1567 
1568  PreservedAnalyses PA;
1570  return PA;
1571 }
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:81
bool isVarArg() const
isVarArg - Return true if this function takes a variable number of arguments.
Definition: Function.h:177
static cl::opt< bool > EnableNonnullArgPropagation("enable-nonnull-arg-prop", cl::Hidden, cl::desc("Try to propagate nonnull argument attributes from callsites to " "caller functions."))
uint64_t CallInst * C
static ChildIteratorType nodes_end(ArgumentGraph *AG)
Return a value (possibly void), from a function.
User::op_iterator arg_iterator
The type of iterator to use when looping over actual arguments at this call site. ...
Definition: CallSite.h:213
MemoryAccessKind
The three kinds of memory access relevant to &#39;readonly&#39; and &#39;readnone&#39; attributes.
Definition: FunctionAttrs.h:32
This builds on the llvm/ADT/GraphTraits.h file to find the strongly connected components (SCCs) of a ...
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:259
iterator_range< use_iterator > uses()
Definition: Value.h:355
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
This class represents an incoming formal argument to a Function.
Definition: Argument.h:30
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:250
This callback is used in conjunction with PointerMayBeCaptured.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:687
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
size_type size() const
Determine the number of elements in the SetVector.
Definition: SetVector.h:78
void removeAttr(Attribute::AttrKind Kind)
Remove attributes from an argument.
Definition: Function.cpp:182
static bool isFunctionMallocLike(Function *F, const SCCNodeSet &SCCNodes)
Tests whether a function is "malloc-like".
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:63
#define LLVM_FALLTHROUGH
Definition: Compiler.h:86
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:1089
static bool addArgumentReturnedAttrs(const SCCNodeSet &SCCNodes)
Deduce returned attributes for the SCC.
static bool setDoesNotRecurse(Function &F)
Implements a lazy call graph analysis and related passes for the new pass manager.
This file contains the declarations for metadata subclasses.
An immutable pass that tracks lazily created AssumptionCache objects.
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)
const Value * getTrueValue() const
bool mayWriteToMemory() const
Return true if this instruction may modify memory.
The two locations do not alias at all.
Definition: AliasAnalysis.h:85
void setDoesNotRecurse()
Definition: Function.h:559
bool onlyReadsMemory(ImmutableCallSite CS)
Checks if the specified call is known to only read from non-volatile memory (or not access memory at ...
bool hasFnAttribute(Attribute::AttrKind Kind) const
Return true if the function has the attribute.
Definition: Function.h:321
STATISTIC(NumFunctions, "Total number of functions")
F(f)
An instruction for reading from memory.
Definition: Instructions.h:168
This defines the Use class.
MemoryAccessKind computeFunctionBodyMemoryAccess(Function &F, AAResults &AAR)
Returns the memory access properties of this copy of the function.
A proxy from a FunctionAnalysisManager to an SCC.
A node in the call graph for a module.
Definition: CallGraph.h:165
void getAnalysisUsage(AnalysisUsage &Info) const override
getAnalysisUsage - For this class, we declare that we require and preserve the call graph...
Support structure for SCC passes to communicate updates the call graph back to the CGSCC pass manager...
void initializeReversePostOrderFunctionAttrsLegacyPassPass(PassRegistry &)
bool onlyReadsMemory() const
Determine if the call does not access or only reads memory.
Definition: CallSite.h:454
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:51
static bool addNonNullAttrs(const SCCNodeSet &SCCNodes)
Deduce nonnull attributes for the SCC.
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...
unsigned data_operands_size() const
Definition: CallSite.h:259
inst_iterator inst_begin(Function *F)
Definition: InstIterator.h:132
This class represents the LLVM &#39;select&#39; instruction.
static bool doesNotReadMemory(FunctionModRefBehavior MRB)
Checks if functions with the specified behavior are known to only write memory (or not access memory ...
A Use represents the edge between a Value definition and its users.
Definition: Use.h:56
static ChildIteratorType child_end(NodeRef N)
IterTy arg_end() const
Definition: CallSite.h:575
static bool runImpl(CallGraphSCC &SCC, AARGetterT AARGetter)
This class is a functor to be used in legacy module or SCC passes for computing AA results for a func...
This file contains the simple types necessary to represent the attributes associated with functions a...
No attributes have been set.
Definition: Attributes.h:72
scc_iterator< T > scc_begin(const T &G)
Construct the begin iterator for a deduced graph type T.
Definition: SCCIterator.h:226
auto reverse(ContainerTy &&C, typename std::enable_if< has_rbegin< ContainerTy >::value >::type *=nullptr) -> decltype(make_range(C.rbegin(), C.rend()))
Definition: STLExtras.h:251
This file provides interfaces used to build and manipulate a call graph, which is a very useful tool ...
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:245
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:142
FunctionModRefBehavior
Summary of how a function affects memory in the program.
A lazily constructed view of the call graph of a module.
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:126
An instruction for storing to memory.
Definition: Instructions.h:310
amdgpu Simplify well known AMD library false Value * Callee
Value * getOperand(unsigned i) const
Definition: User.h:170
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
Definition: PassManager.h:156
static bool addReadAttrs(const SCCNodeSet &SCCNodes, AARGetterT &&AARGetter)
Deduce readonly/readnone attributes for the SCC.
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 ...
bool isVoidTy() const
Return true if this is &#39;void&#39;.
Definition: Type.h:141
const BasicBlock & getEntryBlock() const
Definition: Function.h:640
void getAAMetadata(AAMDNodes &N, bool Merge=false) const
Fills the AAMDNodes structure with AA metadata from this instruction.
static MemoryLocation get(const LoadInst *LI)
Return a location with information about the memory reference by the given instruction.
bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)
Return true if this function can prove that the instruction I will always transfer execution to one o...
Type * getReturnType() const
Returns the type of the ret val.
Definition: Function.h:169
typename ArgumentGraphNode *::UnknownGraphTypeError NodeRef
Definition: GraphTraits.h:79
void addAttr(Attribute::AttrKind Kind)
Definition: Function.cpp:174
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
unsigned const MachineRegisterInfo * MRI
The ModulePass which wraps up a CallGraph and the logic to build it.
Definition: CallGraph.h:324
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
INITIALIZE_PASS_BEGIN(PostOrderFunctionAttrsLegacyPass, "functionattrs", "Deduce function attributes", false, false) INITIALIZE_PASS_END(PostOrderFunctionAttrsLegacyPass
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This is an important base class in LLVM.
Definition: Constant.h:42
This file contains the declarations for the subclasses of Constant, which represent the different fla...
functionattrs
bool isPointerTy() const
True if this is an instance of PointerType.
Definition: Type.h:224
static bool InstrBreaksNonThrowing(Instruction &I, const SCCNodeSet &SCCNodes)
Helper for NoUnwind inference predicate InstrBreaksAttribute.
A manager for alias analyses.
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:371
bool mayThrow() const
Return true if this instruction may throw an exception.
FunctionModRefBehavior getModRefBehavior(ImmutableCallSite CS)
Return the behavior of the given call site.
Represent the analysis usage information of a pass.
bool hasOperandBundles() const
Definition: CallSite.h:535
static bool addNoRecurseAttrs(const SCCNodeSet &SCCNodes)
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:1049
bool hasInternalLinkage() const
Definition: GlobalValue.h:434
static bool addNoRecurseAttrsTopDown(Function &F)
size_t arg_size() const
Definition: Function.h:698
A node in the call graph.
arg_iterator arg_begin()
Definition: Function.h:671
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:382
Pass * createReversePostOrderFunctionAttrsPass()
createReversePostOrderFunctionAttrsPass - This pass walks SCCs of the call graph in RPO to deduce and...
bool doesNotCapture(unsigned OpNo) const
Determine whether this data operand is not captured.
Definition: CallSite.h:593
bool hasInAllocaAttr() const
Return true if this argument has the inalloca attribute.
Definition: Function.cpp:101
This class represents the va_arg llvm instruction, which returns an argument of the specified type gi...
Pass * createPostOrderFunctionAttrsLegacyPass()
Create a legacy pass manager instance of a pass to compute function attrs in post-order.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:159
unsigned getNumArgOperands() const
Definition: CallSite.h:293
bool PointerMayBeCaptured(const Value *V, bool ReturnCaptures, bool StoreCaptures)
PointerMayBeCaptured - Return true if this pointer value may be captured by the enclosing function (w...
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
void getAAResultsAnalysisUsage(AnalysisUsage &AU)
A helper for the legacy pass manager to populate AU to add uses to make sure the analyses required by...
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
This function does not perform any non-local loads or stores to memory.
static cl::opt< bool > DisableNoUnwindInference("disable-nounwind-inference", cl::Hidden, cl::desc("Stop inferring nounwind attribute during function-attrs pass"))
bool doesNotRecurse() const
Determine if the function is known not to recurse, directly or indirectly.
Definition: Function.h:556
Representation for a specific memory location.
bool isPtrOrPtrVectorTy() const
Return true if this is a pointer type or a vector of pointer types.
Definition: Type.h:227
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:298
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:418
SmallVectorImpl< ArgumentGraphNode * >::iterator ChildIteratorType
IterTy arg_begin() const
Definition: CallSite.h:571
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:847
static NodeRef getEntryNode(ArgumentGraph *AG)
A collection of metadata nodes that might be associated with a memory access used by the alias-analys...
Definition: Metadata.h:642
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:381
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:286
unsigned getNumIncomingValues() const
Return the number of incoming edges.
BBTy * getParent() const
Get the basic block containing the call site.
Definition: CallSite.h:97
PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, LazyCallGraph &CG, CGSCCUpdateResult &UR)
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2&#39;s erase_if which is equivalent t...
Definition: STLExtras.h:1180
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:133
static ChildIteratorType child_begin(NodeRef N)
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.
typename SuperClass::iterator iterator
Definition: SmallVector.h:327
iterator_range< user_iterator > users()
Definition: Value.h:400
LLVM_NODISCARD bool isNoModRef(const ModRefInfo MRI)
static bool addNoAliasAttrs(const SCCNodeSet &SCCNodes)
Deduce noalias attributes for the SCC.
const Value * getFalseValue() const
static bool addArgumentAttrs(const SCCNodeSet &SCCNodes)
Deduce nocapture attributes for the SCC.
static bool inferAttrsFromFunctionBodies(const SCCNodeSet &SCCNodes)
Infer attributes from all functions in the SCC by scanning every instruction for compliance to the at...
bool doesNotAccessMemory() const
Determine if the call does not access memory.
Definition: CallSite.h:446
amdgpu Simplify well known AMD library false Value Value * Arg
An analysis pass to compute the CallGraph for a Module.
Definition: CallGraph.h:292
LLVM_NODISCARD bool isModSet(const ModRefInfo MRI)
static bool onlyAccessesArgPointees(FunctionModRefBehavior MRB)
Checks if functions with the specified behavior are known to read and write at most from objects poin...
The basic data container for the call graph of a Module of IR.
Definition: CallGraph.h:74
static bool addArgumentAttrsFromCallsites(Function &F)
If a callsite has arguments that are also arguments to the parent function, try to propagate attribut...
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:56
This file provides utility analysis objects describing memory locations.
void initializePostOrderFunctionAttrsLegacyPassPass(PassRegistry &)
bool hasExactDefinition() const
Return true if this global has an exact defintion.
Definition: GlobalValue.h:407
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:108
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
static NodeRef getEntryNode(NodeRef A)
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
bool mayReadFromMemory() const
Return true if this instruction may read memory.
ModulePass class - This class is used to implement unstructured interprocedural optimizations and ana...
Definition: Pass.h:225
Deduce function attributes
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:323
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:174
Provides passes for computing function attributes based on interprocedural analyses.
static bool isReturnNonNull(Function *F, const SCCNodeSet &SCCNodes, bool &Speculative)
Tests whether this function is known to not return null.
static bool deriveAttrsInPostOrder(SCCNodeSet &SCCNodes, AARGetterT &&AARGetter, bool HasUnknownCall)
This header provides classes for managing passes over SCCs of the call graph.
bool isDeclaration() const
Return true if the primary definition of this global value is outside of the current translation unit...
Definition: Globals.cpp:206
FunTy * getCalledFunction() const
Return the function being called if this is a direct call, otherwise return null (if it&#39;s an indirect...
Definition: CallSite.h:107
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
bool hasRetAttr(Attribute::AttrKind Kind) const
Return true if this return value has the given attribute.
Definition: CallSite.h:372
LLVM Value Representation.
Definition: Value.h:73
An SCC of the call graph.
CallGraphSCC - This is a single SCC that a CallGraphSCCPass is run on.
rpo Deduce function attributes in RPO
static ChildIteratorType nodes_begin(ArgumentGraph *AG)
LLVM_NODISCARD ModRefInfo createModRefInfo(const FunctionModRefBehavior FMRB)
ModRefInfo
Flags indicating whether a memory access modifies or references memory.
print Print MemDeps of function
This is the interface for LLVM&#39;s primary stateless and local alias analysis.
inst_range instructions(Function *F)
Definition: InstIterator.h:134
inst_iterator inst_end(Function *F)
Definition: InstIterator.h:133
A container for analyses that lazily runs them and caches their results.
bool isConvergent() const
Determine if the call is convergent.
Definition: CallSite.h:521
static bool isVolatile(Instruction *Inst)
This header defines various interfaces for pass management in LLVM.
bool hasNoCaptureAttr() const
Return true if this argument has the nocapture attribute.
Definition: Function.cpp:140
#define LLVM_DEBUG(X)
Definition: Debug.h:123
static bool InstrBreaksNonConvergent(Instruction &I, const SCCNodeSet &SCCNodes)
Helper for non-Convergent inference predicate InstrBreaksAttribute.
op_range incoming_values()
static Attribute::AttrKind determinePointerReadAttrs(Argument *A, const SmallPtrSet< Argument *, 8 > &SCCNodes)
Returns Attribute::None, Attribute::ReadOnly or Attribute::ReadNone.
static bool deduceFunctionAttributeInRPO(Module &M, CallGraph &CG)
Enumerate the SCCs of a directed graph in reverse topological order of the SCC DAG.
Definition: SCCIterator.h:43
AttrKind
This enumeration lists the attributes that can be associated with parameters, function results...
Definition: Attributes.h:70
LLVM_NODISCARD bool isRefSet(const ModRefInfo MRI)