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