LLVM  6.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/SetVector.h"
19 #include "llvm/ADT/SmallSet.h"
20 #include "llvm/ADT/Statistic.h"
21 #include "llvm/ADT/StringSwitch.h"
30 #include "llvm/IR/GlobalVariable.h"
31 #include "llvm/IR/InstIterator.h"
32 #include "llvm/IR/IntrinsicInst.h"
33 #include "llvm/IR/LLVMContext.h"
34 #include "llvm/Support/Debug.h"
36 #include "llvm/Transforms/IPO.h"
37 using namespace llvm;
38 
39 #define DEBUG_TYPE "functionattrs"
40 
41 STATISTIC(NumReadNone, "Number of functions marked readnone");
42 STATISTIC(NumReadOnly, "Number of functions marked readonly");
43 STATISTIC(NumNoCapture, "Number of arguments marked nocapture");
44 STATISTIC(NumReturned, "Number of arguments marked returned");
45 STATISTIC(NumReadNoneArg, "Number of arguments marked readnone");
46 STATISTIC(NumReadOnlyArg, "Number of arguments marked readonly");
47 STATISTIC(NumNoAlias, "Number of function returns marked noalias");
48 STATISTIC(NumNonNullReturn, "Number of function returns marked nonnull");
49 STATISTIC(NumNoRecurse, "Number of functions marked as norecurse");
50 
51 // FIXME: This is disabled by default to avoid exposing security vulnerabilities
52 // in C/C++ code compiled by clang:
53 // http://lists.llvm.org/pipermail/cfe-dev/2017-January/052066.html
55  "enable-nonnull-arg-prop", cl::Hidden,
56  cl::desc("Try to propagate nonnull argument attributes from callsites to "
57  "caller functions."));
58 
59 namespace {
60 typedef SmallSetVector<Function *, 8> SCCNodeSet;
61 }
62 
63 /// Returns the memory access attribute for function F using AAR for AA results,
64 /// where SCCNodes is the current SCC.
65 ///
66 /// If ThisBody is true, this function may examine the function body and will
67 /// return a result pertaining to this copy of the function. If it is false, the
68 /// result will be based only on AA results for the function declaration; it
69 /// will be assumed that some other (perhaps less optimized) version of the
70 /// function may be selected at link time.
72  AAResults &AAR,
73  const SCCNodeSet &SCCNodes) {
75  if (MRB == FMRB_DoesNotAccessMemory)
76  // Already perfect!
77  return MAK_ReadNone;
78 
79  if (!ThisBody) {
81  return MAK_ReadOnly;
82 
83  // Conservatively assume it writes to memory.
84  return MAK_MayWrite;
85  }
86 
87  // Scan the function body for instructions that may read or write memory.
88  bool ReadsMemory = false;
89  for (inst_iterator II = inst_begin(F), E = inst_end(F); II != E; ++II) {
90  Instruction *I = &*II;
91 
92  // Some instructions can be ignored even if they read or write memory.
93  // Detect these now, skipping to the next instruction if one is found.
94  CallSite CS(cast<Value>(I));
95  if (CS) {
96  // Ignore calls to functions in the same SCC, as long as the call sites
97  // don't have operand bundles. Calls with operand bundles are allowed to
98  // have memory effects not described by the memory effects of the call
99  // target.
100  if (!CS.hasOperandBundles() && CS.getCalledFunction() &&
101  SCCNodes.count(CS.getCalledFunction()))
102  continue;
104 
105  // If the call doesn't access memory, we're done.
106  if (!(MRB & MRI_ModRef))
107  continue;
108 
110  // The call could access any memory. If that includes writes, give up.
111  if (MRB & MRI_Mod)
112  return MAK_MayWrite;
113  // If it reads, note it.
114  if (MRB & MRI_Ref)
115  ReadsMemory = true;
116  continue;
117  }
118 
119  // Check whether all pointer arguments point to local memory, and
120  // ignore calls that only access local memory.
121  for (CallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end();
122  CI != CE; ++CI) {
123  Value *Arg = *CI;
124  if (!Arg->getType()->isPtrOrPtrVectorTy())
125  continue;
126 
127  AAMDNodes AAInfo;
128  I->getAAMetadata(AAInfo);
130 
131  // Skip accesses to local or constant memory as they don't impact the
132  // externally visible mod/ref behavior.
133  if (AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true))
134  continue;
135 
136  if (MRB & MRI_Mod)
137  // Writes non-local memory. Give up.
138  return MAK_MayWrite;
139  if (MRB & MRI_Ref)
140  // Ok, it reads non-local memory.
141  ReadsMemory = true;
142  }
143  continue;
144  } else if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
145  // Ignore non-volatile loads from local memory. (Atomic is okay here.)
146  if (!LI->isVolatile()) {
148  if (AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true))
149  continue;
150  }
151  } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
152  // Ignore non-volatile stores to local memory. (Atomic is okay here.)
153  if (!SI->isVolatile()) {
155  if (AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true))
156  continue;
157  }
158  } else if (VAArgInst *VI = dyn_cast<VAArgInst>(I)) {
159  // Ignore vaargs on local memory.
161  if (AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true))
162  continue;
163  }
164 
165  // Any remaining instructions need to be taken seriously! Check if they
166  // read or write memory.
167  if (I->mayWriteToMemory())
168  // Writes memory. Just give up.
169  return MAK_MayWrite;
170 
171  // If this instruction may read memory, remember that.
172  ReadsMemory |= I->mayReadFromMemory();
173  }
174 
175  return ReadsMemory ? MAK_ReadOnly : MAK_ReadNone;
176 }
177 
179  AAResults &AAR) {
180  return checkFunctionMemoryAccess(F, /*ThisBody=*/true, AAR, {});
181 }
182 
183 /// Deduce readonly/readnone attributes for the SCC.
184 template <typename AARGetterT>
185 static bool addReadAttrs(const SCCNodeSet &SCCNodes, AARGetterT &&AARGetter) {
186  // Check if any of the functions in the SCC read or write memory. If they
187  // write memory then they can't be marked readnone or readonly.
188  bool ReadsMemory = false;
189  for (Function *F : SCCNodes) {
190  // Call the callable parameter to look up AA results for this function.
191  AAResults &AAR = AARGetter(*F);
192 
193  // Non-exact function definitions may not be selected at link time, and an
194  // alternative version that writes to memory may be selected. See the
195  // comment on GlobalValue::isDefinitionExact for more details.
196  switch (checkFunctionMemoryAccess(*F, F->hasExactDefinition(),
197  AAR, SCCNodes)) {
198  case MAK_MayWrite:
199  return false;
200  case MAK_ReadOnly:
201  ReadsMemory = true;
202  break;
203  case MAK_ReadNone:
204  // Nothing to do!
205  break;
206  }
207  }
208 
209  // Success! Functions in this SCC do not access memory, or only read memory.
210  // Give them the appropriate attribute.
211  bool MadeChange = false;
212  for (Function *F : SCCNodes) {
213  if (F->doesNotAccessMemory())
214  // Already perfect!
215  continue;
216 
217  if (F->onlyReadsMemory() && ReadsMemory)
218  // No change.
219  continue;
220 
221  MadeChange = true;
222 
223  // Clear out any existing attributes.
224  F->removeFnAttr(Attribute::ReadOnly);
225  F->removeFnAttr(Attribute::ReadNone);
226 
227  // Add in the new attribute.
228  F->addFnAttr(ReadsMemory ? Attribute::ReadOnly : Attribute::ReadNone);
229 
230  if (ReadsMemory)
231  ++NumReadOnly;
232  else
233  ++NumReadNone;
234  }
235 
236  return MadeChange;
237 }
238 
239 namespace {
240 /// For a given pointer Argument, this retains a list of Arguments of functions
241 /// in the same SCC that the pointer data flows into. We use this to build an
242 /// SCC of the arguments.
243 struct ArgumentGraphNode {
244  Argument *Definition;
246 };
247 
248 class ArgumentGraph {
249  // We store pointers to ArgumentGraphNode objects, so it's important that
250  // that they not move around upon insert.
251  typedef std::map<Argument *, ArgumentGraphNode> ArgumentMapTy;
252 
253  ArgumentMapTy ArgumentMap;
254 
255  // There is no root node for the argument graph, in fact:
256  // void f(int *x, int *y) { if (...) f(x, y); }
257  // is an example where the graph is disconnected. The SCCIterator requires a
258  // single entry point, so we maintain a fake ("synthetic") root node that
259  // uses every node. Because the graph is directed and nothing points into
260  // the root, it will not participate in any SCCs (except for its own).
261  ArgumentGraphNode SyntheticRoot;
262 
263 public:
264  ArgumentGraph() { SyntheticRoot.Definition = nullptr; }
265 
267 
268  iterator begin() { return SyntheticRoot.Uses.begin(); }
269  iterator end() { return SyntheticRoot.Uses.end(); }
270  ArgumentGraphNode *getEntryNode() { return &SyntheticRoot; }
271 
272  ArgumentGraphNode *operator[](Argument *A) {
273  ArgumentGraphNode &Node = ArgumentMap[A];
274  Node.Definition = A;
275  SyntheticRoot.Uses.push_back(&Node);
276  return &Node;
277  }
278 };
279 
280 /// This tracker checks whether callees are in the SCC, and if so it does not
281 /// consider that a capture, instead adding it to the "Uses" list and
282 /// continuing with the analysis.
283 struct ArgumentUsesTracker : public CaptureTracker {
284  ArgumentUsesTracker(const SCCNodeSet &SCCNodes)
285  : Captured(false), SCCNodes(SCCNodes) {}
286 
287  void tooManyUses() override { Captured = true; }
288 
289  bool captured(const Use *U) override {
290  CallSite CS(U->getUser());
291  if (!CS.getInstruction()) {
292  Captured = true;
293  return true;
294  }
295 
296  Function *F = CS.getCalledFunction();
297  if (!F || !F->hasExactDefinition() || !SCCNodes.count(F)) {
298  Captured = true;
299  return true;
300  }
301 
302  // Note: the callee and the two successor blocks *follow* the argument
303  // operands. This means there is no need to adjust UseIndex to account for
304  // these.
305 
306  unsigned UseIndex =
307  std::distance(const_cast<const Use *>(CS.arg_begin()), U);
308 
309  assert(UseIndex < CS.data_operands_size() &&
310  "Indirect function calls should have been filtered above!");
311 
312  if (UseIndex >= CS.getNumArgOperands()) {
313  // Data operand, but not a argument operand -- must be a bundle operand
314  assert(CS.hasOperandBundles() && "Must be!");
315 
316  // CaptureTracking told us that we're being captured by an operand bundle
317  // use. In this case it does not matter if the callee is within our SCC
318  // or not -- we've been captured in some unknown way, and we have to be
319  // conservative.
320  Captured = true;
321  return true;
322  }
323 
324  if (UseIndex >= F->arg_size()) {
325  assert(F->isVarArg() && "More params than args in non-varargs call");
326  Captured = true;
327  return true;
328  }
329 
330  Uses.push_back(&*std::next(F->arg_begin(), UseIndex));
331  return false;
332  }
333 
334  bool Captured; // True only if certainly captured (used outside our SCC).
335  SmallVector<Argument *, 4> Uses; // Uses within our SCC.
336 
337  const SCCNodeSet &SCCNodes;
338 };
339 }
340 
341 namespace llvm {
342 template <> struct GraphTraits<ArgumentGraphNode *> {
343  typedef ArgumentGraphNode *NodeRef;
345 
346  static NodeRef getEntryNode(NodeRef A) { return A; }
347  static ChildIteratorType child_begin(NodeRef N) { return N->Uses.begin(); }
348  static ChildIteratorType child_end(NodeRef N) { return N->Uses.end(); }
349 };
350 template <>
351 struct GraphTraits<ArgumentGraph *> : public GraphTraits<ArgumentGraphNode *> {
352  static NodeRef getEntryNode(ArgumentGraph *AG) { return AG->getEntryNode(); }
353  static ChildIteratorType nodes_begin(ArgumentGraph *AG) {
354  return AG->begin();
355  }
356  static ChildIteratorType nodes_end(ArgumentGraph *AG) { return AG->end(); }
357 };
358 }
359 
360 /// Returns Attribute::None, Attribute::ReadOnly or Attribute::ReadNone.
361 static Attribute::AttrKind
363  const SmallPtrSet<Argument *, 8> &SCCNodes) {
364 
365  SmallVector<Use *, 32> Worklist;
366  SmallSet<Use *, 32> Visited;
367 
368  // inalloca arguments are always clobbered by the call.
369  if (A->hasInAllocaAttr())
370  return Attribute::None;
371 
372  bool IsRead = false;
373  // We don't need to track IsWritten. If A is written to, return immediately.
374 
375  for (Use &U : A->uses()) {
376  Visited.insert(&U);
377  Worklist.push_back(&U);
378  }
379 
380  while (!Worklist.empty()) {
381  Use *U = Worklist.pop_back_val();
382  Instruction *I = cast<Instruction>(U->getUser());
383 
384  switch (I->getOpcode()) {
385  case Instruction::BitCast:
386  case Instruction::GetElementPtr:
387  case Instruction::PHI:
388  case Instruction::Select:
389  case Instruction::AddrSpaceCast:
390  // The original value is not read/written via this if the new value isn't.
391  for (Use &UU : I->uses())
392  if (Visited.insert(&UU).second)
393  Worklist.push_back(&UU);
394  break;
395 
396  case Instruction::Call:
397  case Instruction::Invoke: {
398  bool Captures = true;
399 
400  if (I->getType()->isVoidTy())
401  Captures = false;
402 
403  auto AddUsersToWorklistIfCapturing = [&] {
404  if (Captures)
405  for (Use &UU : I->uses())
406  if (Visited.insert(&UU).second)
407  Worklist.push_back(&UU);
408  };
409 
410  CallSite CS(I);
411  if (CS.doesNotAccessMemory()) {
412  AddUsersToWorklistIfCapturing();
413  continue;
414  }
415 
416  Function *F = CS.getCalledFunction();
417  if (!F) {
418  if (CS.onlyReadsMemory()) {
419  IsRead = true;
420  AddUsersToWorklistIfCapturing();
421  continue;
422  }
423  return Attribute::None;
424  }
425 
426  // Note: the callee and the two successor blocks *follow* the argument
427  // operands. This means there is no need to adjust UseIndex to account
428  // for these.
429 
430  unsigned UseIndex = std::distance(CS.arg_begin(), U);
431 
432  // U cannot be the callee operand use: since we're exploring the
433  // transitive uses of an Argument, having such a use be a callee would
434  // imply the CallSite is an indirect call or invoke; and we'd take the
435  // early exit above.
436  assert(UseIndex < CS.data_operands_size() &&
437  "Data operand use expected!");
438 
439  bool IsOperandBundleUse = UseIndex >= CS.getNumArgOperands();
440 
441  if (UseIndex >= F->arg_size() && !IsOperandBundleUse) {
442  assert(F->isVarArg() && "More params than args in non-varargs call");
443  return Attribute::None;
444  }
445 
446  Captures &= !CS.doesNotCapture(UseIndex);
447 
448  // Since the optimizer (by design) cannot see the data flow corresponding
449  // to a operand bundle use, these cannot participate in the optimistic SCC
450  // analysis. Instead, we model the operand bundle uses as arguments in
451  // call to a function external to the SCC.
452  if (IsOperandBundleUse ||
453  !SCCNodes.count(&*std::next(F->arg_begin(), UseIndex))) {
454 
455  // The accessors used on CallSite here do the right thing for calls and
456  // invokes with operand bundles.
457 
458  if (!CS.onlyReadsMemory() && !CS.onlyReadsMemory(UseIndex))
459  return Attribute::None;
460  if (!CS.doesNotAccessMemory(UseIndex))
461  IsRead = true;
462  }
463 
464  AddUsersToWorklistIfCapturing();
465  break;
466  }
467 
468  case Instruction::Load:
469  // A volatile load has side effects beyond what readonly can be relied
470  // upon.
471  if (cast<LoadInst>(I)->isVolatile())
472  return Attribute::None;
473 
474  IsRead = true;
475  break;
476 
477  case Instruction::ICmp:
478  case Instruction::Ret:
479  break;
480 
481  default:
482  return Attribute::None;
483  }
484  }
485 
486  return IsRead ? Attribute::ReadOnly : Attribute::ReadNone;
487 }
488 
489 /// Deduce returned attributes for the SCC.
490 static bool addArgumentReturnedAttrs(const SCCNodeSet &SCCNodes) {
491  bool Changed = false;
492 
493  // Check each function in turn, determining if an argument is always returned.
494  for (Function *F : SCCNodes) {
495  // We can infer and propagate function attributes only when we know that the
496  // definition we'll get at link time is *exactly* the definition we see now.
497  // For more details, see GlobalValue::mayBeDerefined.
498  if (!F->hasExactDefinition())
499  continue;
500 
501  if (F->getReturnType()->isVoidTy())
502  continue;
503 
504  // There is nothing to do if an argument is already marked as 'returned'.
505  if (any_of(F->args(),
506  [](const Argument &Arg) { return Arg.hasReturnedAttr(); }))
507  continue;
508 
509  auto FindRetArg = [&]() -> Value * {
510  Value *RetArg = nullptr;
511  for (BasicBlock &BB : *F)
512  if (auto *Ret = dyn_cast<ReturnInst>(BB.getTerminator())) {
513  // Note that stripPointerCasts should look through functions with
514  // returned arguments.
515  Value *RetVal = Ret->getReturnValue()->stripPointerCasts();
516  if (!isa<Argument>(RetVal) || RetVal->getType() != F->getReturnType())
517  return nullptr;
518 
519  if (!RetArg)
520  RetArg = RetVal;
521  else if (RetArg != RetVal)
522  return nullptr;
523  }
524 
525  return RetArg;
526  };
527 
528  if (Value *RetArg = FindRetArg()) {
529  auto *A = cast<Argument>(RetArg);
530  A->addAttr(Attribute::Returned);
531  ++NumReturned;
532  Changed = true;
533  }
534  }
535 
536  return Changed;
537 }
538 
539 /// If a callsite has arguments that are also arguments to the parent function,
540 /// try to propagate attributes from the callsite's arguments to the parent's
541 /// arguments. This may be important because inlining can cause information loss
542 /// when attribute knowledge disappears with the inlined call.
545  return false;
546 
547  bool Changed = false;
548 
549  // For an argument attribute to transfer from a callsite to the parent, the
550  // call must be guaranteed to execute every time the parent is called.
551  // Conservatively, just check for calls in the entry block that are guaranteed
552  // to execute.
553  // TODO: This could be enhanced by testing if the callsite post-dominates the
554  // entry block or by doing simple forward walks or backward walks to the
555  // callsite.
556  BasicBlock &Entry = F.getEntryBlock();
557  for (Instruction &I : Entry) {
558  if (auto CS = CallSite(&I)) {
559  if (auto *CalledFunc = CS.getCalledFunction()) {
560  for (auto &CSArg : CalledFunc->args()) {
561  if (!CSArg.hasNonNullAttr())
562  continue;
563 
564  // If the non-null callsite argument operand is an argument to 'F'
565  // (the caller) and the call is guaranteed to execute, then the value
566  // must be non-null throughout 'F'.
567  auto *FArg = dyn_cast<Argument>(CS.getArgOperand(CSArg.getArgNo()));
568  if (FArg && !FArg->hasNonNullAttr()) {
569  FArg->addAttr(Attribute::NonNull);
570  Changed = true;
571  }
572  }
573  }
574  }
576  break;
577  }
578 
579  return Changed;
580 }
581 
582 /// Deduce nocapture attributes for the SCC.
583 static bool addArgumentAttrs(const SCCNodeSet &SCCNodes) {
584  bool Changed = false;
585 
586  ArgumentGraph AG;
587 
588  // Check each function in turn, determining which pointer arguments are not
589  // captured.
590  for (Function *F : SCCNodes) {
591  // We can infer and propagate function attributes only when we know that the
592  // definition we'll get at link time is *exactly* the definition we see now.
593  // For more details, see GlobalValue::mayBeDerefined.
594  if (!F->hasExactDefinition())
595  continue;
596 
597  Changed |= addArgumentAttrsFromCallsites(*F);
598 
599  // Functions that are readonly (or readnone) and nounwind and don't return
600  // a value can't capture arguments. Don't analyze them.
601  if (F->onlyReadsMemory() && F->doesNotThrow() &&
602  F->getReturnType()->isVoidTy()) {
603  for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end(); A != E;
604  ++A) {
605  if (A->getType()->isPointerTy() && !A->hasNoCaptureAttr()) {
606  A->addAttr(Attribute::NoCapture);
607  ++NumNoCapture;
608  Changed = true;
609  }
610  }
611  continue;
612  }
613 
614  for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end(); A != E;
615  ++A) {
616  if (!A->getType()->isPointerTy())
617  continue;
618  bool HasNonLocalUses = false;
619  if (!A->hasNoCaptureAttr()) {
620  ArgumentUsesTracker Tracker(SCCNodes);
621  PointerMayBeCaptured(&*A, &Tracker);
622  if (!Tracker.Captured) {
623  if (Tracker.Uses.empty()) {
624  // If it's trivially not captured, mark it nocapture now.
625  A->addAttr(Attribute::NoCapture);
626  ++NumNoCapture;
627  Changed = true;
628  } else {
629  // If it's not trivially captured and not trivially not captured,
630  // then it must be calling into another function in our SCC. Save
631  // its particulars for Argument-SCC analysis later.
632  ArgumentGraphNode *Node = AG[&*A];
633  for (Argument *Use : Tracker.Uses) {
634  Node->Uses.push_back(AG[Use]);
635  if (Use != &*A)
636  HasNonLocalUses = true;
637  }
638  }
639  }
640  // Otherwise, it's captured. Don't bother doing SCC analysis on it.
641  }
642  if (!HasNonLocalUses && !A->onlyReadsMemory()) {
643  // Can we determine that it's readonly/readnone without doing an SCC?
644  // Note that we don't allow any calls at all here, or else our result
645  // will be dependent on the iteration order through the functions in the
646  // SCC.
648  Self.insert(&*A);
650  if (R != Attribute::None) {
651  A->addAttr(R);
652  Changed = true;
653  R == Attribute::ReadOnly ? ++NumReadOnlyArg : ++NumReadNoneArg;
654  }
655  }
656  }
657  }
658 
659  // The graph we've collected is partial because we stopped scanning for
660  // argument uses once we solved the argument trivially. These partial nodes
661  // show up as ArgumentGraphNode objects with an empty Uses list, and for
662  // these nodes the final decision about whether they capture has already been
663  // made. If the definition doesn't have a 'nocapture' attribute by now, it
664  // captures.
665 
666  for (scc_iterator<ArgumentGraph *> I = scc_begin(&AG); !I.isAtEnd(); ++I) {
667  const std::vector<ArgumentGraphNode *> &ArgumentSCC = *I;
668  if (ArgumentSCC.size() == 1) {
669  if (!ArgumentSCC[0]->Definition)
670  continue; // synthetic root node
671 
672  // eg. "void f(int* x) { if (...) f(x); }"
673  if (ArgumentSCC[0]->Uses.size() == 1 &&
674  ArgumentSCC[0]->Uses[0] == ArgumentSCC[0]) {
675  Argument *A = ArgumentSCC[0]->Definition;
676  A->addAttr(Attribute::NoCapture);
677  ++NumNoCapture;
678  Changed = true;
679  }
680  continue;
681  }
682 
683  bool SCCCaptured = false;
684  for (auto I = ArgumentSCC.begin(), E = ArgumentSCC.end();
685  I != E && !SCCCaptured; ++I) {
686  ArgumentGraphNode *Node = *I;
687  if (Node->Uses.empty()) {
688  if (!Node->Definition->hasNoCaptureAttr())
689  SCCCaptured = true;
690  }
691  }
692  if (SCCCaptured)
693  continue;
694 
695  SmallPtrSet<Argument *, 8> ArgumentSCCNodes;
696  // Fill ArgumentSCCNodes with the elements of the ArgumentSCC. Used for
697  // quickly looking up whether a given Argument is in this ArgumentSCC.
698  for (ArgumentGraphNode *I : ArgumentSCC) {
699  ArgumentSCCNodes.insert(I->Definition);
700  }
701 
702  for (auto I = ArgumentSCC.begin(), E = ArgumentSCC.end();
703  I != E && !SCCCaptured; ++I) {
704  ArgumentGraphNode *N = *I;
705  for (ArgumentGraphNode *Use : N->Uses) {
706  Argument *A = Use->Definition;
707  if (A->hasNoCaptureAttr() || ArgumentSCCNodes.count(A))
708  continue;
709  SCCCaptured = true;
710  break;
711  }
712  }
713  if (SCCCaptured)
714  continue;
715 
716  for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) {
717  Argument *A = ArgumentSCC[i]->Definition;
718  A->addAttr(Attribute::NoCapture);
719  ++NumNoCapture;
720  Changed = true;
721  }
722 
723  // We also want to compute readonly/readnone. With a small number of false
724  // negatives, we can assume that any pointer which is captured isn't going
725  // to be provably readonly or readnone, since by definition we can't
726  // analyze all uses of a captured pointer.
727  //
728  // The false negatives happen when the pointer is captured by a function
729  // that promises readonly/readnone behaviour on the pointer, then the
730  // pointer's lifetime ends before anything that writes to arbitrary memory.
731  // Also, a readonly/readnone pointer may be returned, but returning a
732  // pointer is capturing it.
733 
734  Attribute::AttrKind ReadAttr = Attribute::ReadNone;
735  for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) {
736  Argument *A = ArgumentSCC[i]->Definition;
737  Attribute::AttrKind K = determinePointerReadAttrs(A, ArgumentSCCNodes);
738  if (K == Attribute::ReadNone)
739  continue;
740  if (K == Attribute::ReadOnly) {
741  ReadAttr = Attribute::ReadOnly;
742  continue;
743  }
744  ReadAttr = K;
745  break;
746  }
747 
748  if (ReadAttr != Attribute::None) {
749  for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) {
750  Argument *A = ArgumentSCC[i]->Definition;
751  // Clear out existing readonly/readnone attributes
752  A->removeAttr(Attribute::ReadOnly);
753  A->removeAttr(Attribute::ReadNone);
754  A->addAttr(ReadAttr);
755  ReadAttr == Attribute::ReadOnly ? ++NumReadOnlyArg : ++NumReadNoneArg;
756  Changed = true;
757  }
758  }
759  }
760 
761  return Changed;
762 }
763 
764 /// Tests whether a function is "malloc-like".
765 ///
766 /// A function is "malloc-like" if it returns either null or a pointer that
767 /// doesn't alias any other pointer visible to the caller.
768 static bool isFunctionMallocLike(Function *F, const SCCNodeSet &SCCNodes) {
769  SmallSetVector<Value *, 8> FlowsToReturn;
770  for (BasicBlock &BB : *F)
771  if (ReturnInst *Ret = dyn_cast<ReturnInst>(BB.getTerminator()))
772  FlowsToReturn.insert(Ret->getReturnValue());
773 
774  for (unsigned i = 0; i != FlowsToReturn.size(); ++i) {
775  Value *RetVal = FlowsToReturn[i];
776 
777  if (Constant *C = dyn_cast<Constant>(RetVal)) {
778  if (!C->isNullValue() && !isa<UndefValue>(C))
779  return false;
780 
781  continue;
782  }
783 
784  if (isa<Argument>(RetVal))
785  return false;
786 
787  if (Instruction *RVI = dyn_cast<Instruction>(RetVal))
788  switch (RVI->getOpcode()) {
789  // Extend the analysis by looking upwards.
790  case Instruction::BitCast:
791  case Instruction::GetElementPtr:
792  case Instruction::AddrSpaceCast:
793  FlowsToReturn.insert(RVI->getOperand(0));
794  continue;
795  case Instruction::Select: {
796  SelectInst *SI = cast<SelectInst>(RVI);
797  FlowsToReturn.insert(SI->getTrueValue());
798  FlowsToReturn.insert(SI->getFalseValue());
799  continue;
800  }
801  case Instruction::PHI: {
802  PHINode *PN = cast<PHINode>(RVI);
803  for (Value *IncValue : PN->incoming_values())
804  FlowsToReturn.insert(IncValue);
805  continue;
806  }
807 
808  // Check whether the pointer came from an allocation.
809  case Instruction::Alloca:
810  break;
811  case Instruction::Call:
812  case Instruction::Invoke: {
813  CallSite CS(RVI);
815  break;
816  if (CS.getCalledFunction() && SCCNodes.count(CS.getCalledFunction()))
817  break;
819  }
820  default:
821  return false; // Did not come from an allocation.
822  }
823 
824  if (PointerMayBeCaptured(RetVal, false, /*StoreCaptures=*/false))
825  return false;
826  }
827 
828  return true;
829 }
830 
831 /// Deduce noalias attributes for the SCC.
832 static bool addNoAliasAttrs(const SCCNodeSet &SCCNodes) {
833  // Check each function in turn, determining which functions return noalias
834  // pointers.
835  for (Function *F : SCCNodes) {
836  // Already noalias.
837  if (F->returnDoesNotAlias())
838  continue;
839 
840  // We can infer and propagate function attributes only when we know that the
841  // definition we'll get at link time is *exactly* the definition we see now.
842  // For more details, see GlobalValue::mayBeDerefined.
843  if (!F->hasExactDefinition())
844  return false;
845 
846  // We annotate noalias return values, which are only applicable to
847  // pointer types.
848  if (!F->getReturnType()->isPointerTy())
849  continue;
850 
851  if (!isFunctionMallocLike(F, SCCNodes))
852  return false;
853  }
854 
855  bool MadeChange = false;
856  for (Function *F : SCCNodes) {
857  if (F->returnDoesNotAlias() ||
858  !F->getReturnType()->isPointerTy())
859  continue;
860 
861  F->setReturnDoesNotAlias();
862  ++NumNoAlias;
863  MadeChange = true;
864  }
865 
866  return MadeChange;
867 }
868 
869 /// Tests whether this function is known to not return null.
870 ///
871 /// Requires that the function returns a pointer.
872 ///
873 /// Returns true if it believes the function will not return a null, and sets
874 /// \p Speculative based on whether the returned conclusion is a speculative
875 /// conclusion due to SCC calls.
876 static bool isReturnNonNull(Function *F, const SCCNodeSet &SCCNodes,
877  bool &Speculative) {
878  assert(F->getReturnType()->isPointerTy() &&
879  "nonnull only meaningful on pointer types");
880  Speculative = false;
881 
882  SmallSetVector<Value *, 8> FlowsToReturn;
883  for (BasicBlock &BB : *F)
884  if (auto *Ret = dyn_cast<ReturnInst>(BB.getTerminator()))
885  FlowsToReturn.insert(Ret->getReturnValue());
886 
887  for (unsigned i = 0; i != FlowsToReturn.size(); ++i) {
888  Value *RetVal = FlowsToReturn[i];
889 
890  // If this value is locally known to be non-null, we're good
891  if (isKnownNonNull(RetVal))
892  continue;
893 
894  // Otherwise, we need to look upwards since we can't make any local
895  // conclusions.
896  Instruction *RVI = dyn_cast<Instruction>(RetVal);
897  if (!RVI)
898  return false;
899  switch (RVI->getOpcode()) {
900  // Extend the analysis by looking upwards.
901  case Instruction::BitCast:
902  case Instruction::GetElementPtr:
903  case Instruction::AddrSpaceCast:
904  FlowsToReturn.insert(RVI->getOperand(0));
905  continue;
906  case Instruction::Select: {
907  SelectInst *SI = cast<SelectInst>(RVI);
908  FlowsToReturn.insert(SI->getTrueValue());
909  FlowsToReturn.insert(SI->getFalseValue());
910  continue;
911  }
912  case Instruction::PHI: {
913  PHINode *PN = cast<PHINode>(RVI);
914  for (int i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
915  FlowsToReturn.insert(PN->getIncomingValue(i));
916  continue;
917  }
918  case Instruction::Call:
919  case Instruction::Invoke: {
920  CallSite CS(RVI);
921  Function *Callee = CS.getCalledFunction();
922  // A call to a node within the SCC is assumed to return null until
923  // proven otherwise
924  if (Callee && SCCNodes.count(Callee)) {
925  Speculative = true;
926  continue;
927  }
928  return false;
929  }
930  default:
931  return false; // Unknown source, may be null
932  };
933  llvm_unreachable("should have either continued or returned");
934  }
935 
936  return true;
937 }
938 
939 /// Deduce nonnull attributes for the SCC.
940 static bool addNonNullAttrs(const SCCNodeSet &SCCNodes) {
941  // Speculative that all functions in the SCC return only nonnull
942  // pointers. We may refute this as we analyze functions.
943  bool SCCReturnsNonNull = true;
944 
945  bool MadeChange = false;
946 
947  // Check each function in turn, determining which functions return nonnull
948  // pointers.
949  for (Function *F : SCCNodes) {
950  // Already nonnull.
951  if (F->getAttributes().hasAttribute(AttributeList::ReturnIndex,
952  Attribute::NonNull))
953  continue;
954 
955  // We can infer and propagate function attributes only when we know that the
956  // definition we'll get at link time is *exactly* the definition we see now.
957  // For more details, see GlobalValue::mayBeDerefined.
958  if (!F->hasExactDefinition())
959  return false;
960 
961  // We annotate nonnull return values, which are only applicable to
962  // pointer types.
963  if (!F->getReturnType()->isPointerTy())
964  continue;
965 
966  bool Speculative = false;
967  if (isReturnNonNull(F, SCCNodes, Speculative)) {
968  if (!Speculative) {
969  // Mark the function eagerly since we may discover a function
970  // which prevents us from speculating about the entire SCC
971  DEBUG(dbgs() << "Eagerly marking " << F->getName() << " as nonnull\n");
972  F->addAttribute(AttributeList::ReturnIndex, Attribute::NonNull);
973  ++NumNonNullReturn;
974  MadeChange = true;
975  }
976  continue;
977  }
978  // At least one function returns something which could be null, can't
979  // speculate any more.
980  SCCReturnsNonNull = false;
981  }
982 
983  if (SCCReturnsNonNull) {
984  for (Function *F : SCCNodes) {
985  if (F->getAttributes().hasAttribute(AttributeList::ReturnIndex,
986  Attribute::NonNull) ||
987  !F->getReturnType()->isPointerTy())
988  continue;
989 
990  DEBUG(dbgs() << "SCC marking " << F->getName() << " as nonnull\n");
991  F->addAttribute(AttributeList::ReturnIndex, Attribute::NonNull);
992  ++NumNonNullReturn;
993  MadeChange = true;
994  }
995  }
996 
997  return MadeChange;
998 }
999 
1000 /// Remove the convergent attribute from all functions in the SCC if every
1001 /// callsite within the SCC is not convergent (except for calls to functions
1002 /// within the SCC). Returns true if changes were made.
1003 static bool removeConvergentAttrs(const SCCNodeSet &SCCNodes) {
1004  // For every function in SCC, ensure that either
1005  // * it is not convergent, or
1006  // * we can remove its convergent attribute.
1007  bool HasConvergentFn = false;
1008  for (Function *F : SCCNodes) {
1009  if (!F->isConvergent()) continue;
1010  HasConvergentFn = true;
1011 
1012  // Can't remove convergent from function declarations.
1013  if (F->isDeclaration()) return false;
1014 
1015  // Can't remove convergent if any of our functions has a convergent call to a
1016  // function not in the SCC.
1017  for (Instruction &I : instructions(*F)) {
1018  CallSite CS(&I);
1019  // Bail if CS is a convergent call to a function not in the SCC.
1020  if (CS && CS.isConvergent() &&
1021  SCCNodes.count(CS.getCalledFunction()) == 0)
1022  return false;
1023  }
1024  }
1025 
1026  // If the SCC doesn't have any convergent functions, we have nothing to do.
1027  if (!HasConvergentFn) return false;
1028 
1029  // If we got here, all of the calls the SCC makes to functions not in the SCC
1030  // are non-convergent. Therefore all of the SCC's functions can also be made
1031  // non-convergent. We'll remove the attr from the callsites in
1032  // InstCombineCalls.
1033  for (Function *F : SCCNodes) {
1034  if (!F->isConvergent()) continue;
1035 
1036  DEBUG(dbgs() << "Removing convergent attr from fn " << F->getName()
1037  << "\n");
1038  F->setNotConvergent();
1039  }
1040  return true;
1041 }
1042 
1044  if (F.doesNotRecurse())
1045  return false;
1046  F.setDoesNotRecurse();
1047  ++NumNoRecurse;
1048  return true;
1049 }
1050 
1051 static bool addNoRecurseAttrs(const SCCNodeSet &SCCNodes) {
1052  // Try and identify functions that do not recurse.
1053 
1054  // If the SCC contains multiple nodes we know for sure there is recursion.
1055  if (SCCNodes.size() != 1)
1056  return false;
1057 
1058  Function *F = *SCCNodes.begin();
1059  if (!F || F->isDeclaration() || F->doesNotRecurse())
1060  return false;
1061 
1062  // If all of the calls in F are identifiable and are to norecurse functions, F
1063  // is norecurse. This check also detects self-recursion as F is not currently
1064  // marked norecurse, so any called from F to F will not be marked norecurse.
1065  for (Instruction &I : instructions(*F))
1066  if (auto CS = CallSite(&I)) {
1067  Function *Callee = CS.getCalledFunction();
1068  if (!Callee || Callee == F || !Callee->doesNotRecurse())
1069  // Function calls a potentially recursive function.
1070  return false;
1071  }
1072 
1073  // Every call was to a non-recursive function other than this function, and
1074  // we have no indirect recursion as the SCC size is one. This function cannot
1075  // recurse.
1076  return setDoesNotRecurse(*F);
1077 }
1078 
1081  LazyCallGraph &CG,
1082  CGSCCUpdateResult &) {
1084  AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C, CG).getManager();
1085 
1086  // We pass a lambda into functions to wire them up to the analysis manager
1087  // for getting function analyses.
1088  auto AARGetter = [&](Function &F) -> AAResults & {
1089  return FAM.getResult<AAManager>(F);
1090  };
1091 
1092  // Fill SCCNodes with the elements of the SCC. Also track whether there are
1093  // any external or opt-none nodes that will prevent us from optimizing any
1094  // part of the SCC.
1095  SCCNodeSet SCCNodes;
1096  bool HasUnknownCall = false;
1097  for (LazyCallGraph::Node &N : C) {
1098  Function &F = N.getFunction();
1099  if (F.hasFnAttribute(Attribute::OptimizeNone)) {
1100  // Treat any function we're trying not to optimize as if it were an
1101  // indirect call and omit it from the node set used below.
1102  HasUnknownCall = true;
1103  continue;
1104  }
1105  // Track whether any functions in this SCC have an unknown call edge.
1106  // Note: if this is ever a performance hit, we can common it with
1107  // subsequent routines which also do scans over the instructions of the
1108  // function.
1109  if (!HasUnknownCall)
1110  for (Instruction &I : instructions(F))
1111  if (auto CS = CallSite(&I))
1112  if (!CS.getCalledFunction()) {
1113  HasUnknownCall = true;
1114  break;
1115  }
1116 
1117  SCCNodes.insert(&F);
1118  }
1119 
1120  bool Changed = false;
1121  Changed |= addArgumentReturnedAttrs(SCCNodes);
1122  Changed |= addReadAttrs(SCCNodes, AARGetter);
1123  Changed |= addArgumentAttrs(SCCNodes);
1124 
1125  // If we have no external nodes participating in the SCC, we can deduce some
1126  // more precise attributes as well.
1127  if (!HasUnknownCall) {
1128  Changed |= addNoAliasAttrs(SCCNodes);
1129  Changed |= addNonNullAttrs(SCCNodes);
1130  Changed |= removeConvergentAttrs(SCCNodes);
1131  Changed |= addNoRecurseAttrs(SCCNodes);
1132  }
1133 
1134  return Changed ? PreservedAnalyses::none() : PreservedAnalyses::all();
1135 }
1136 
1137 namespace {
1138 struct PostOrderFunctionAttrsLegacyPass : public CallGraphSCCPass {
1139  static char ID; // Pass identification, replacement for typeid
1140  PostOrderFunctionAttrsLegacyPass() : CallGraphSCCPass(ID) {
1143  }
1144 
1145  bool runOnSCC(CallGraphSCC &SCC) override;
1146 
1147  void getAnalysisUsage(AnalysisUsage &AU) const override {
1148  AU.setPreservesCFG();
1152  }
1153 };
1154 }
1155 
1157 INITIALIZE_PASS_BEGIN(PostOrderFunctionAttrsLegacyPass, "functionattrs",
1158  "Deduce function attributes", false, false)
1161 INITIALIZE_PASS_END(PostOrderFunctionAttrsLegacyPass, "functionattrs",
1162  "Deduce function attributes", false, false)
1163 
1165  return new PostOrderFunctionAttrsLegacyPass();
1166 }
1167 
1168 template <typename AARGetterT>
1169 static bool runImpl(CallGraphSCC &SCC, AARGetterT AARGetter) {
1170  bool Changed = false;
1171 
1172  // Fill SCCNodes with the elements of the SCC. Used for quickly looking up
1173  // whether a given CallGraphNode is in this SCC. Also track whether there are
1174  // any external or opt-none nodes that will prevent us from optimizing any
1175  // part of the SCC.
1176  SCCNodeSet SCCNodes;
1177  bool ExternalNode = false;
1178  for (CallGraphNode *I : SCC) {
1179  Function *F = I->getFunction();
1180  if (!F || F->hasFnAttribute(Attribute::OptimizeNone)) {
1181  // External node or function we're trying not to optimize - we both avoid
1182  // transform them and avoid leveraging information they provide.
1183  ExternalNode = true;
1184  continue;
1185  }
1186 
1187  SCCNodes.insert(F);
1188  }
1189 
1190  // Skip it if the SCC only contains optnone functions.
1191  if (SCCNodes.empty())
1192  return Changed;
1193 
1194  Changed |= addArgumentReturnedAttrs(SCCNodes);
1195  Changed |= addReadAttrs(SCCNodes, AARGetter);
1196  Changed |= addArgumentAttrs(SCCNodes);
1197 
1198  // If we have no external nodes participating in the SCC, we can deduce some
1199  // more precise attributes as well.
1200  if (!ExternalNode) {
1201  Changed |= addNoAliasAttrs(SCCNodes);
1202  Changed |= addNonNullAttrs(SCCNodes);
1203  Changed |= removeConvergentAttrs(SCCNodes);
1204  Changed |= addNoRecurseAttrs(SCCNodes);
1205  }
1206 
1207  return Changed;
1208 }
1209 
1210 bool PostOrderFunctionAttrsLegacyPass::runOnSCC(CallGraphSCC &SCC) {
1211  if (skipSCC(SCC))
1212  return false;
1213  return runImpl(SCC, LegacyAARGetter(*this));
1214 }
1215 
1216 namespace {
1217 struct ReversePostOrderFunctionAttrsLegacyPass : public ModulePass {
1218  static char ID; // Pass identification, replacement for typeid
1219  ReversePostOrderFunctionAttrsLegacyPass() : ModulePass(ID) {
1222  }
1223 
1224  bool runOnModule(Module &M) override;
1225 
1226  void getAnalysisUsage(AnalysisUsage &AU) const override {
1227  AU.setPreservesCFG();
1230  }
1231 };
1232 }
1233 
1235 INITIALIZE_PASS_BEGIN(ReversePostOrderFunctionAttrsLegacyPass, "rpo-functionattrs",
1236  "Deduce function attributes in RPO", false, false)
1238 INITIALIZE_PASS_END(ReversePostOrderFunctionAttrsLegacyPass, "rpo-functionattrs",
1239  "Deduce function attributes in RPO", false, false)
1240 
1242  return new ReversePostOrderFunctionAttrsLegacyPass();
1243 }
1244 
1246  // We check the preconditions for the function prior to calling this to avoid
1247  // the cost of building up a reversible post-order list. We assert them here
1248  // to make sure none of the invariants this relies on were violated.
1249  assert(!F.isDeclaration() && "Cannot deduce norecurse without a definition!");
1250  assert(!F.doesNotRecurse() &&
1251  "This function has already been deduced as norecurs!");
1252  assert(F.hasInternalLinkage() &&
1253  "Can only do top-down deduction for internal linkage functions!");
1254 
1255  // If F is internal and all of its uses are calls from a non-recursive
1256  // functions, then none of its calls could in fact recurse without going
1257  // through a function marked norecurse, and so we can mark this function too
1258  // as norecurse. Note that the uses must actually be calls -- otherwise
1259  // a pointer to this function could be returned from a norecurse function but
1260  // this function could be recursively (indirectly) called. Note that this
1261  // also detects if F is directly recursive as F is not yet marked as
1262  // a norecurse function.
1263  for (auto *U : F.users()) {
1264  auto *I = dyn_cast<Instruction>(U);
1265  if (!I)
1266  return false;
1267  CallSite CS(I);
1268  if (!CS || !CS.getParent()->getParent()->doesNotRecurse())
1269  return false;
1270  }
1271  return setDoesNotRecurse(F);
1272 }
1273 
1275  // We only have a post-order SCC traversal (because SCCs are inherently
1276  // discovered in post-order), so we accumulate them in a vector and then walk
1277  // it in reverse. This is simpler than using the RPO iterator infrastructure
1278  // because we need to combine SCC detection and the PO walk of the call
1279  // graph. We can also cheat egregiously because we're primarily interested in
1280  // synthesizing norecurse and so we can only save the singular SCCs as SCCs
1281  // with multiple functions in them will clearly be recursive.
1282  SmallVector<Function *, 16> Worklist;
1283  for (scc_iterator<CallGraph *> I = scc_begin(&CG); !I.isAtEnd(); ++I) {
1284  if (I->size() != 1)
1285  continue;
1286 
1287  Function *F = I->front()->getFunction();
1288  if (F && !F->isDeclaration() && !F->doesNotRecurse() &&
1289  F->hasInternalLinkage())
1290  Worklist.push_back(F);
1291  }
1292 
1293  bool Changed = false;
1294  for (auto *F : reverse(Worklist))
1295  Changed |= addNoRecurseAttrsTopDown(*F);
1296 
1297  return Changed;
1298 }
1299 
1300 bool ReversePostOrderFunctionAttrsLegacyPass::runOnModule(Module &M) {
1301  if (skipModule(M))
1302  return false;
1303 
1304  auto &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph();
1305 
1306  return deduceFunctionAttributeInRPO(M, CG);
1307 }
1308 
1311  auto &CG = AM.getResult<CallGraphAnalysis>(M);
1312 
1313  if (!deduceFunctionAttributeInRPO(M, CG))
1314  return PreservedAnalyses::all();
1315 
1316  PreservedAnalyses PA;
1318  return PA;
1319 }
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:150
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:210
MemoryAccessKind
The three kinds of memory access relevant to &#39;readonly&#39; and &#39;readnone&#39; attributes.
Definition: FunctionAttrs.h:27
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:243
iterator_range< use_iterator > uses()
Definition: Value.h:350
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:234
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
static bool addArgumentReturnedAttrs(const SCCNodeSet &SCCNodes)
Deduce returned attributes for the SCC.
static bool setDoesNotRecurse(Function &F)
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.
void setDoesNotRecurse()
Definition: Function.h:483
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:254
STATISTIC(NumFunctions, "Total number of functions")
The two locations do not alias at all.
Definition: AliasAnalysis.h:79
An instruction for reading from memory.
Definition: Instructions.h:164
SmallVectorImpl< ArgumentGraphNode * >::iterator ChildIteratorType
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...
The access modifies the value stored in memory.
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:446
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:256
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:549
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...
No attributes have been set.
Definition: Attributes.h:72
The access references the value stored in memory.
Definition: AliasAnalysis.h:98
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:250
This file provides interfaces used to build and manipulate a call graph, which is a very useful tool ...
#define F(x, y, z)
Definition: MD5.cpp:55
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:121
An instruction for storing to memory.
Definition: Instructions.h:306
Value * getOperand(unsigned i) const
Definition: User.h:154
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:564
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:142
typename ArgumentGraphNode *::UnknownGraphTypeError NodeRef
Definition: GraphTraits.h:59
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
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
This is an important base class in LLVM.
Definition: Constant.h:42
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:36
functionattrs
bool isPointerTy() const
True if this is an instance of PointerType.
Definition: Type.h:221
A manager for alias analyses.
#define A
Definition: LargeTest.cpp:12
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:372
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:509
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:825
bool hasInternalLinkage() const
Definition: GlobalValue.h:414
static bool addNoRecurseAttrsTopDown(Function &F)
size_t arg_size() const
Definition: Function.h:622
A node in the call graph.
arg_iterator arg_begin()
Definition: Function.h:595
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:383
std::pair< NoneType, bool > insert(const T &V)
insert - Insert an element into the set if it isn&#39;t already there.
Definition: SmallSet.h:81
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:567
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:290
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.
bool doesNotRecurse() const
Determine if the function is known not to recurse, directly or indirectly.
Definition: Function.h:480
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:423
#define E
Definition: LargeTest.cpp:27
IterTy arg_begin() const
Definition: CallSite.h:545
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:864
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
const size_t N
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:385
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:278
unsigned getNumIncomingValues() const
Return the number of incoming edges.
BBTy * getParent() const
Get the basic block containing the call site.
Definition: CallSite.h:94
PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, LazyCallGraph &CG, CGSCCUpdateResult &UR)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
static ChildIteratorType child_begin(NodeRef N)
typename SuperClass::iterator iterator
Definition: SmallVector.h:328
iterator_range< user_iterator > users()
Definition: Value.h:395
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 removeConvergentAttrs(const SCCNodeSet &SCCNodes)
Remove the convergent attribute from all functions in the SCC if every callsite within the SCC is not...
bool doesNotAccessMemory() const
Determine if the call does not access memory.
Definition: CallSite.h:438
An analysis pass to compute the CallGraph for a Module.
Definition: CallGraph.h:292
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
bool isKnownNonNull(const Value *V)
Return true if this pointer couldn&#39;t possibly be null by its definition.
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:61
void initializePostOrderFunctionAttrsLegacyPassPass(PassRegistry &)
bool hasExactDefinition() const
Return true if this global has an exact defintion.
Definition: GlobalValue.h:387
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:108
The access both references and modifies the value stored in memory.
#define I(x, y, z)
Definition: MD5.cpp:58
static NodeRef getEntryNode(NodeRef A)
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:235
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.
bool isDeclaration() const
Return true if the primary definition of this global value is outside of the current translation unit...
Definition: Globals.cpp:200
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:104
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:369
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
#define DEBUG(X)
Definition: Debug.h:118
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:495
static bool isVolatile(Instruction *Inst)
bool hasNoCaptureAttr() const
Return true if this argument has the nocapture attribute.
Definition: Function.cpp:140
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