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