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