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 
667 /// Deduce nocapture attributes for the SCC.
668 static bool addArgumentAttrs(const SCCNodeSet &SCCNodes) {
669  bool Changed = false;
670 
671  ArgumentGraph AG;
672 
673  // Check each function in turn, determining which pointer arguments are not
674  // captured.
675  for (Function *F : SCCNodes) {
676  // We can infer and propagate function attributes only when we know that the
677  // definition we'll get at link time is *exactly* the definition we see now.
678  // For more details, see GlobalValue::mayBeDerefined.
679  if (!F->hasExactDefinition())
680  continue;
681 
682  Changed |= addArgumentAttrsFromCallsites(*F);
683 
684  // Functions that are readonly (or readnone) and nounwind and don't return
685  // a value can't capture arguments. Don't analyze them.
686  if (F->onlyReadsMemory() && F->doesNotThrow() &&
687  F->getReturnType()->isVoidTy()) {
688  for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end(); A != E;
689  ++A) {
690  if (A->getType()->isPointerTy() && !A->hasNoCaptureAttr()) {
691  A->addAttr(Attribute::NoCapture);
692  ++NumNoCapture;
693  Changed = true;
694  }
695  }
696  continue;
697  }
698 
699  for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end(); A != E;
700  ++A) {
701  if (!A->getType()->isPointerTy())
702  continue;
703  bool HasNonLocalUses = false;
704  if (!A->hasNoCaptureAttr()) {
705  ArgumentUsesTracker Tracker(SCCNodes);
706  PointerMayBeCaptured(&*A, &Tracker);
707  if (!Tracker.Captured) {
708  if (Tracker.Uses.empty()) {
709  // If it's trivially not captured, mark it nocapture now.
710  A->addAttr(Attribute::NoCapture);
711  ++NumNoCapture;
712  Changed = true;
713  } else {
714  // If it's not trivially captured and not trivially not captured,
715  // then it must be calling into another function in our SCC. Save
716  // its particulars for Argument-SCC analysis later.
717  ArgumentGraphNode *Node = AG[&*A];
718  for (Argument *Use : Tracker.Uses) {
719  Node->Uses.push_back(AG[Use]);
720  if (Use != &*A)
721  HasNonLocalUses = true;
722  }
723  }
724  }
725  // Otherwise, it's captured. Don't bother doing SCC analysis on it.
726  }
727  if (!HasNonLocalUses && !A->onlyReadsMemory()) {
728  // Can we determine that it's readonly/readnone without doing an SCC?
729  // Note that we don't allow any calls at all here, or else our result
730  // will be dependent on the iteration order through the functions in the
731  // SCC.
733  Self.insert(&*A);
735  if (R != Attribute::None) {
736  A->addAttr(R);
737  Changed = true;
738  R == Attribute::ReadOnly ? ++NumReadOnlyArg : ++NumReadNoneArg;
739  }
740  }
741  }
742  }
743 
744  // The graph we've collected is partial because we stopped scanning for
745  // argument uses once we solved the argument trivially. These partial nodes
746  // show up as ArgumentGraphNode objects with an empty Uses list, and for
747  // these nodes the final decision about whether they capture has already been
748  // made. If the definition doesn't have a 'nocapture' attribute by now, it
749  // captures.
750 
751  for (scc_iterator<ArgumentGraph *> I = scc_begin(&AG); !I.isAtEnd(); ++I) {
752  const std::vector<ArgumentGraphNode *> &ArgumentSCC = *I;
753  if (ArgumentSCC.size() == 1) {
754  if (!ArgumentSCC[0]->Definition)
755  continue; // synthetic root node
756 
757  // eg. "void f(int* x) { if (...) f(x); }"
758  if (ArgumentSCC[0]->Uses.size() == 1 &&
759  ArgumentSCC[0]->Uses[0] == ArgumentSCC[0]) {
760  Argument *A = ArgumentSCC[0]->Definition;
761  A->addAttr(Attribute::NoCapture);
762  ++NumNoCapture;
763  Changed = true;
764  }
765  continue;
766  }
767 
768  bool SCCCaptured = false;
769  for (auto I = ArgumentSCC.begin(), E = ArgumentSCC.end();
770  I != E && !SCCCaptured; ++I) {
771  ArgumentGraphNode *Node = *I;
772  if (Node->Uses.empty()) {
773  if (!Node->Definition->hasNoCaptureAttr())
774  SCCCaptured = true;
775  }
776  }
777  if (SCCCaptured)
778  continue;
779 
780  SmallPtrSet<Argument *, 8> ArgumentSCCNodes;
781  // Fill ArgumentSCCNodes with the elements of the ArgumentSCC. Used for
782  // quickly looking up whether a given Argument is in this ArgumentSCC.
783  for (ArgumentGraphNode *I : ArgumentSCC) {
784  ArgumentSCCNodes.insert(I->Definition);
785  }
786 
787  for (auto I = ArgumentSCC.begin(), E = ArgumentSCC.end();
788  I != E && !SCCCaptured; ++I) {
789  ArgumentGraphNode *N = *I;
790  for (ArgumentGraphNode *Use : N->Uses) {
791  Argument *A = Use->Definition;
792  if (A->hasNoCaptureAttr() || ArgumentSCCNodes.count(A))
793  continue;
794  SCCCaptured = true;
795  break;
796  }
797  }
798  if (SCCCaptured)
799  continue;
800 
801  for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) {
802  Argument *A = ArgumentSCC[i]->Definition;
803  A->addAttr(Attribute::NoCapture);
804  ++NumNoCapture;
805  Changed = true;
806  }
807 
808  // We also want to compute readonly/readnone. With a small number of false
809  // negatives, we can assume that any pointer which is captured isn't going
810  // to be provably readonly or readnone, since by definition we can't
811  // analyze all uses of a captured pointer.
812  //
813  // The false negatives happen when the pointer is captured by a function
814  // that promises readonly/readnone behaviour on the pointer, then the
815  // pointer's lifetime ends before anything that writes to arbitrary memory.
816  // Also, a readonly/readnone pointer may be returned, but returning a
817  // pointer is capturing it.
818 
819  Attribute::AttrKind ReadAttr = Attribute::ReadNone;
820  for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) {
821  Argument *A = ArgumentSCC[i]->Definition;
822  Attribute::AttrKind K = determinePointerReadAttrs(A, ArgumentSCCNodes);
823  if (K == Attribute::ReadNone)
824  continue;
825  if (K == Attribute::ReadOnly) {
826  ReadAttr = Attribute::ReadOnly;
827  continue;
828  }
829  ReadAttr = K;
830  break;
831  }
832 
833  if (ReadAttr != Attribute::None) {
834  for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) {
835  Argument *A = ArgumentSCC[i]->Definition;
836  // Clear out existing readonly/readnone attributes
837  A->removeAttr(Attribute::ReadOnly);
838  A->removeAttr(Attribute::ReadNone);
839  A->addAttr(ReadAttr);
840  ReadAttr == Attribute::ReadOnly ? ++NumReadOnlyArg : ++NumReadNoneArg;
841  Changed = true;
842  }
843  }
844  }
845 
846  return Changed;
847 }
848 
849 /// Tests whether a function is "malloc-like".
850 ///
851 /// A function is "malloc-like" if it returns either null or a pointer that
852 /// doesn't alias any other pointer visible to the caller.
853 static bool isFunctionMallocLike(Function *F, const SCCNodeSet &SCCNodes) {
854  SmallSetVector<Value *, 8> FlowsToReturn;
855  for (BasicBlock &BB : *F)
856  if (ReturnInst *Ret = dyn_cast<ReturnInst>(BB.getTerminator()))
857  FlowsToReturn.insert(Ret->getReturnValue());
858 
859  for (unsigned i = 0; i != FlowsToReturn.size(); ++i) {
860  Value *RetVal = FlowsToReturn[i];
861 
862  if (Constant *C = dyn_cast<Constant>(RetVal)) {
863  if (!C->isNullValue() && !isa<UndefValue>(C))
864  return false;
865 
866  continue;
867  }
868 
869  if (isa<Argument>(RetVal))
870  return false;
871 
872  if (Instruction *RVI = dyn_cast<Instruction>(RetVal))
873  switch (RVI->getOpcode()) {
874  // Extend the analysis by looking upwards.
875  case Instruction::BitCast:
876  case Instruction::GetElementPtr:
877  case Instruction::AddrSpaceCast:
878  FlowsToReturn.insert(RVI->getOperand(0));
879  continue;
880  case Instruction::Select: {
881  SelectInst *SI = cast<SelectInst>(RVI);
882  FlowsToReturn.insert(SI->getTrueValue());
883  FlowsToReturn.insert(SI->getFalseValue());
884  continue;
885  }
886  case Instruction::PHI: {
887  PHINode *PN = cast<PHINode>(RVI);
888  for (Value *IncValue : PN->incoming_values())
889  FlowsToReturn.insert(IncValue);
890  continue;
891  }
892 
893  // Check whether the pointer came from an allocation.
894  case Instruction::Alloca:
895  break;
896  case Instruction::Call:
897  case Instruction::Invoke: {
898  CallSite CS(RVI);
900  break;
901  if (CS.getCalledFunction() && SCCNodes.count(CS.getCalledFunction()))
902  break;
904  }
905  default:
906  return false; // Did not come from an allocation.
907  }
908 
909  if (PointerMayBeCaptured(RetVal, false, /*StoreCaptures=*/false))
910  return false;
911  }
912 
913  return true;
914 }
915 
916 /// Deduce noalias attributes for the SCC.
917 static bool addNoAliasAttrs(const SCCNodeSet &SCCNodes) {
918  // Check each function in turn, determining which functions return noalias
919  // pointers.
920  for (Function *F : SCCNodes) {
921  // Already noalias.
922  if (F->returnDoesNotAlias())
923  continue;
924 
925  // We can infer and propagate function attributes only when we know that the
926  // definition we'll get at link time is *exactly* the definition we see now.
927  // For more details, see GlobalValue::mayBeDerefined.
928  if (!F->hasExactDefinition())
929  return false;
930 
931  // We annotate noalias return values, which are only applicable to
932  // pointer types.
933  if (!F->getReturnType()->isPointerTy())
934  continue;
935 
936  if (!isFunctionMallocLike(F, SCCNodes))
937  return false;
938  }
939 
940  bool MadeChange = false;
941  for (Function *F : SCCNodes) {
942  if (F->returnDoesNotAlias() ||
943  !F->getReturnType()->isPointerTy())
944  continue;
945 
946  F->setReturnDoesNotAlias();
947  ++NumNoAlias;
948  MadeChange = true;
949  }
950 
951  return MadeChange;
952 }
953 
954 /// Tests whether this function is known to not return null.
955 ///
956 /// Requires that the function returns a pointer.
957 ///
958 /// Returns true if it believes the function will not return a null, and sets
959 /// \p Speculative based on whether the returned conclusion is a speculative
960 /// conclusion due to SCC calls.
961 static bool isReturnNonNull(Function *F, const SCCNodeSet &SCCNodes,
962  bool &Speculative) {
963  assert(F->getReturnType()->isPointerTy() &&
964  "nonnull only meaningful on pointer types");
965  Speculative = false;
966 
967  SmallSetVector<Value *, 8> FlowsToReturn;
968  for (BasicBlock &BB : *F)
969  if (auto *Ret = dyn_cast<ReturnInst>(BB.getTerminator()))
970  FlowsToReturn.insert(Ret->getReturnValue());
971 
972  auto &DL = F->getParent()->getDataLayout();
973 
974  for (unsigned i = 0; i != FlowsToReturn.size(); ++i) {
975  Value *RetVal = FlowsToReturn[i];
976 
977  // If this value is locally known to be non-null, we're good
978  if (isKnownNonZero(RetVal, DL))
979  continue;
980 
981  // Otherwise, we need to look upwards since we can't make any local
982  // conclusions.
983  Instruction *RVI = dyn_cast<Instruction>(RetVal);
984  if (!RVI)
985  return false;
986  switch (RVI->getOpcode()) {
987  // Extend the analysis by looking upwards.
988  case Instruction::BitCast:
989  case Instruction::GetElementPtr:
990  case Instruction::AddrSpaceCast:
991  FlowsToReturn.insert(RVI->getOperand(0));
992  continue;
993  case Instruction::Select: {
994  SelectInst *SI = cast<SelectInst>(RVI);
995  FlowsToReturn.insert(SI->getTrueValue());
996  FlowsToReturn.insert(SI->getFalseValue());
997  continue;
998  }
999  case Instruction::PHI: {
1000  PHINode *PN = cast<PHINode>(RVI);
1001  for (int i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
1002  FlowsToReturn.insert(PN->getIncomingValue(i));
1003  continue;
1004  }
1005  case Instruction::Call:
1006  case Instruction::Invoke: {
1007  CallSite CS(RVI);
1009  // A call to a node within the SCC is assumed to return null until
1010  // proven otherwise
1011  if (Callee && SCCNodes.count(Callee)) {
1012  Speculative = true;
1013  continue;
1014  }
1015  return false;
1016  }
1017  default:
1018  return false; // Unknown source, may be null
1019  };
1020  llvm_unreachable("should have either continued or returned");
1021  }
1022 
1023  return true;
1024 }
1025 
1026 /// Deduce nonnull attributes for the SCC.
1027 static bool addNonNullAttrs(const SCCNodeSet &SCCNodes) {
1028  // Speculative that all functions in the SCC return only nonnull
1029  // pointers. We may refute this as we analyze functions.
1030  bool SCCReturnsNonNull = true;
1031 
1032  bool MadeChange = false;
1033 
1034  // Check each function in turn, determining which functions return nonnull
1035  // pointers.
1036  for (Function *F : SCCNodes) {
1037  // Already nonnull.
1038  if (F->getAttributes().hasAttribute(AttributeList::ReturnIndex,
1039  Attribute::NonNull))
1040  continue;
1041 
1042  // We can infer and propagate function attributes only when we know that the
1043  // definition we'll get at link time is *exactly* the definition we see now.
1044  // For more details, see GlobalValue::mayBeDerefined.
1045  if (!F->hasExactDefinition())
1046  return false;
1047 
1048  // We annotate nonnull return values, which are only applicable to
1049  // pointer types.
1050  if (!F->getReturnType()->isPointerTy())
1051  continue;
1052 
1053  bool Speculative = false;
1054  if (isReturnNonNull(F, SCCNodes, Speculative)) {
1055  if (!Speculative) {
1056  // Mark the function eagerly since we may discover a function
1057  // which prevents us from speculating about the entire SCC
1058  LLVM_DEBUG(dbgs() << "Eagerly marking " << F->getName()
1059  << " as nonnull\n");
1060  F->addAttribute(AttributeList::ReturnIndex, Attribute::NonNull);
1061  ++NumNonNullReturn;
1062  MadeChange = true;
1063  }
1064  continue;
1065  }
1066  // At least one function returns something which could be null, can't
1067  // speculate any more.
1068  SCCReturnsNonNull = false;
1069  }
1070 
1071  if (SCCReturnsNonNull) {
1072  for (Function *F : SCCNodes) {
1073  if (F->getAttributes().hasAttribute(AttributeList::ReturnIndex,
1074  Attribute::NonNull) ||
1075  !F->getReturnType()->isPointerTy())
1076  continue;
1077 
1078  LLVM_DEBUG(dbgs() << "SCC marking " << F->getName() << " as nonnull\n");
1079  F->addAttribute(AttributeList::ReturnIndex, Attribute::NonNull);
1080  ++NumNonNullReturn;
1081  MadeChange = true;
1082  }
1083  }
1084 
1085  return MadeChange;
1086 }
1087 
1088 namespace {
1089 
1090 /// Collects a set of attribute inference requests and performs them all in one
1091 /// go on a single SCC Node. Inference involves scanning function bodies
1092 /// looking for instructions that violate attribute assumptions.
1093 /// As soon as all the bodies are fine we are free to set the attribute.
1094 /// Customization of inference for individual attributes is performed by
1095 /// providing a handful of predicates for each attribute.
1096 class AttributeInferer {
1097 public:
1098  /// Describes a request for inference of a single attribute.
1099  struct InferenceDescriptor {
1100 
1101  /// Returns true if this function does not have to be handled.
1102  /// General intent for this predicate is to provide an optimization
1103  /// for functions that do not need this attribute inference at all
1104  /// (say, for functions that already have the attribute).
1105  std::function<bool(const Function &)> SkipFunction;
1106 
1107  /// Returns true if this instruction violates attribute assumptions.
1108  std::function<bool(Instruction &)> InstrBreaksAttribute;
1109 
1110  /// Sets the inferred attribute for this function.
1111  std::function<void(Function &)> SetAttribute;
1112 
1113  /// Attribute we derive.
1114  Attribute::AttrKind AKind;
1115 
1116  /// If true, only "exact" definitions can be used to infer this attribute.
1117  /// See GlobalValue::isDefinitionExact.
1118  bool RequiresExactDefinition;
1119 
1120  InferenceDescriptor(Attribute::AttrKind AK,
1121  std::function<bool(const Function &)> SkipFunc,
1122  std::function<bool(Instruction &)> InstrScan,
1123  std::function<void(Function &)> SetAttr,
1124  bool ReqExactDef)
1125  : SkipFunction(SkipFunc), InstrBreaksAttribute(InstrScan),
1126  SetAttribute(SetAttr), AKind(AK),
1127  RequiresExactDefinition(ReqExactDef) {}
1128  };
1129 
1130 private:
1131  SmallVector<InferenceDescriptor, 4> InferenceDescriptors;
1132 
1133 public:
1134  void registerAttrInference(InferenceDescriptor AttrInference) {
1135  InferenceDescriptors.push_back(AttrInference);
1136  }
1137 
1138  bool run(const SCCNodeSet &SCCNodes);
1139 };
1140 
1141 /// Perform all the requested attribute inference actions according to the
1142 /// attribute predicates stored before.
1143 bool AttributeInferer::run(const SCCNodeSet &SCCNodes) {
1144  SmallVector<InferenceDescriptor, 4> InferInSCC = InferenceDescriptors;
1145  // Go through all the functions in SCC and check corresponding attribute
1146  // assumptions for each of them. Attributes that are invalid for this SCC
1147  // will be removed from InferInSCC.
1148  for (Function *F : SCCNodes) {
1149 
1150  // No attributes whose assumptions are still valid - done.
1151  if (InferInSCC.empty())
1152  return false;
1153 
1154  // Check if our attributes ever need scanning/can be scanned.
1155  llvm::erase_if(InferInSCC, [F](const InferenceDescriptor &ID) {
1156  if (ID.SkipFunction(*F))
1157  return false;
1158 
1159  // Remove from further inference (invalidate) when visiting a function
1160  // that has no instructions to scan/has an unsuitable definition.
1161  return F->isDeclaration() ||
1162  (ID.RequiresExactDefinition && !F->hasExactDefinition());
1163  });
1164 
1165  // For each attribute still in InferInSCC that doesn't explicitly skip F,
1166  // set up the F instructions scan to verify assumptions of the attribute.
1167  SmallVector<InferenceDescriptor, 4> InferInThisFunc;
1168  llvm::copy_if(
1169  InferInSCC, std::back_inserter(InferInThisFunc),
1170  [F](const InferenceDescriptor &ID) { return !ID.SkipFunction(*F); });
1171 
1172  if (InferInThisFunc.empty())
1173  continue;
1174 
1175  // Start instruction scan.
1176  for (Instruction &I : instructions(*F)) {
1177  llvm::erase_if(InferInThisFunc, [&](const InferenceDescriptor &ID) {
1178  if (!ID.InstrBreaksAttribute(I))
1179  return false;
1180  // Remove attribute from further inference on any other functions
1181  // because attribute assumptions have just been violated.
1182  llvm::erase_if(InferInSCC, [&ID](const InferenceDescriptor &D) {
1183  return D.AKind == ID.AKind;
1184  });
1185  // Remove attribute from the rest of current instruction scan.
1186  return true;
1187  });
1188 
1189  if (InferInThisFunc.empty())
1190  break;
1191  }
1192  }
1193 
1194  if (InferInSCC.empty())
1195  return false;
1196 
1197  bool Changed = false;
1198  for (Function *F : SCCNodes)
1199  // At this point InferInSCC contains only functions that were either:
1200  // - explicitly skipped from scan/inference, or
1201  // - verified to have no instructions that break attribute assumptions.
1202  // Hence we just go and force the attribute for all non-skipped functions.
1203  for (auto &ID : InferInSCC) {
1204  if (ID.SkipFunction(*F))
1205  continue;
1206  Changed = true;
1207  ID.SetAttribute(*F);
1208  }
1209  return Changed;
1210 }
1211 
1212 } // end anonymous namespace
1213 
1214 /// Helper for non-Convergent inference predicate InstrBreaksAttribute.
1216  const SCCNodeSet &SCCNodes) {
1217  const CallSite CS(&I);
1218  // Breaks non-convergent assumption if CS is a convergent call to a function
1219  // not in the SCC.
1220  return CS && CS.isConvergent() && SCCNodes.count(CS.getCalledFunction()) == 0;
1221 }
1222 
1223 /// Helper for NoUnwind inference predicate InstrBreaksAttribute.
1224 static bool InstrBreaksNonThrowing(Instruction &I, const SCCNodeSet &SCCNodes) {
1225  if (!I.mayThrow())
1226  return false;
1227  if (const auto *CI = dyn_cast<CallInst>(&I)) {
1228  if (Function *Callee = CI->getCalledFunction()) {
1229  // I is a may-throw call to a function inside our SCC. This doesn't
1230  // invalidate our current working assumption that the SCC is no-throw; we
1231  // just have to scan that other function.
1232  if (SCCNodes.count(Callee) > 0)
1233  return false;
1234  }
1235  }
1236  return true;
1237 }
1238 
1239 /// Helper for NoFree inference predicate InstrBreaksAttribute.
1240 static bool InstrBreaksNoFree(Instruction &I, const SCCNodeSet &SCCNodes) {
1241  CallSite CS(&I);
1242  if (!CS)
1243  return false;
1244 
1246  if (!Callee)
1247  return true;
1248 
1249  if (Callee->doesNotFreeMemory())
1250  return false;
1251 
1252  if (SCCNodes.count(Callee) > 0)
1253  return false;
1254 
1255  return true;
1256 }
1257 
1258 /// Infer attributes from all functions in the SCC by scanning every
1259 /// instruction for compliance to the attribute assumptions. Currently it
1260 /// does:
1261 /// - removal of Convergent attribute
1262 /// - addition of NoUnwind attribute
1263 ///
1264 /// Returns true if any changes to function attributes were made.
1265 static bool inferAttrsFromFunctionBodies(const SCCNodeSet &SCCNodes) {
1266 
1267  AttributeInferer AI;
1268 
1269  // Request to remove the convergent attribute from all functions in the SCC
1270  // if every callsite within the SCC is not convergent (except for calls
1271  // to functions within the SCC).
1272  // Note: Removal of the attr from the callsites will happen in
1273  // InstCombineCalls separately.
1274  AI.registerAttrInference(AttributeInferer::InferenceDescriptor{
1276  // Skip non-convergent functions.
1277  [](const Function &F) { return !F.isConvergent(); },
1278  // Instructions that break non-convergent assumption.
1279  [SCCNodes](Instruction &I) {
1280  return InstrBreaksNonConvergent(I, SCCNodes);
1281  },
1282  [](Function &F) {
1283  LLVM_DEBUG(dbgs() << "Removing convergent attr from fn " << F.getName()
1284  << "\n");
1285  F.setNotConvergent();
1286  },
1287  /* RequiresExactDefinition= */ false});
1288 
1290  // Request to infer nounwind attribute for all the functions in the SCC if
1291  // every callsite within the SCC is not throwing (except for calls to
1292  // functions within the SCC). Note that nounwind attribute suffers from
1293  // derefinement - results may change depending on how functions are
1294  // optimized. Thus it can be inferred only from exact definitions.
1295  AI.registerAttrInference(AttributeInferer::InferenceDescriptor{
1296  Attribute::NoUnwind,
1297  // Skip non-throwing functions.
1298  [](const Function &F) { return F.doesNotThrow(); },
1299  // Instructions that break non-throwing assumption.
1300  [SCCNodes](Instruction &I) {
1301  return InstrBreaksNonThrowing(I, SCCNodes);
1302  },
1303  [](Function &F) {
1304  LLVM_DEBUG(dbgs()
1305  << "Adding nounwind attr to fn " << F.getName() << "\n");
1306  F.setDoesNotThrow();
1307  ++NumNoUnwind;
1308  },
1309  /* RequiresExactDefinition= */ true});
1310 
1312  // Request to infer nofree attribute for all the functions in the SCC if
1313  // every callsite within the SCC does not directly or indirectly free
1314  // memory (except for calls to functions within the SCC). Note that nofree
1315  // attribute suffers from derefinement - results may change depending on
1316  // how functions are optimized. Thus it can be inferred only from exact
1317  // definitions.
1318  AI.registerAttrInference(AttributeInferer::InferenceDescriptor{
1319  Attribute::NoFree,
1320  // Skip functions known not to free memory.
1321  [](const Function &F) { return F.doesNotFreeMemory(); },
1322  // Instructions that break non-deallocating assumption.
1323  [SCCNodes](Instruction &I) {
1324  return InstrBreaksNoFree(I, SCCNodes);
1325  },
1326  [](Function &F) {
1327  LLVM_DEBUG(dbgs()
1328  << "Adding nofree attr to fn " << F.getName() << "\n");
1329  F.setDoesNotFreeMemory();
1330  ++NumNoFree;
1331  },
1332  /* RequiresExactDefinition= */ true});
1333 
1334  // Perform all the requested attribute inference actions.
1335  return AI.run(SCCNodes);
1336 }
1337 
1339  if (F.doesNotRecurse())
1340  return false;
1341  F.setDoesNotRecurse();
1342  ++NumNoRecurse;
1343  return true;
1344 }
1345 
1346 static bool addNoRecurseAttrs(const SCCNodeSet &SCCNodes) {
1347  // Try and identify functions that do not recurse.
1348 
1349  // If the SCC contains multiple nodes we know for sure there is recursion.
1350  if (SCCNodes.size() != 1)
1351  return false;
1352 
1353  Function *F = *SCCNodes.begin();
1354  if (!F || !F->hasExactDefinition() || F->doesNotRecurse())
1355  return false;
1356 
1357  // If all of the calls in F are identifiable and are to norecurse functions, F
1358  // is norecurse. This check also detects self-recursion as F is not currently
1359  // marked norecurse, so any called from F to F will not be marked norecurse.
1360  for (auto &BB : *F)
1361  for (auto &I : BB.instructionsWithoutDebug())
1362  if (auto CS = CallSite(&I)) {
1363  Function *Callee = CS.getCalledFunction();
1364  if (!Callee || Callee == F || !Callee->doesNotRecurse())
1365  // Function calls a potentially recursive function.
1366  return false;
1367  }
1368 
1369  // Every call was to a non-recursive function other than this function, and
1370  // we have no indirect recursion as the SCC size is one. This function cannot
1371  // recurse.
1372  return setDoesNotRecurse(*F);
1373 }
1374 
1375 template <typename AARGetterT>
1376 static bool deriveAttrsInPostOrder(SCCNodeSet &SCCNodes,
1377  AARGetterT &&AARGetter,
1378  bool HasUnknownCall) {
1379  bool Changed = false;
1380 
1381  // Bail if the SCC only contains optnone functions.
1382  if (SCCNodes.empty())
1383  return Changed;
1384 
1385  Changed |= addArgumentReturnedAttrs(SCCNodes);
1386  Changed |= addReadAttrs(SCCNodes, AARGetter);
1387  Changed |= addArgumentAttrs(SCCNodes);
1388 
1389  // If we have no external nodes participating in the SCC, we can deduce some
1390  // more precise attributes as well.
1391  if (!HasUnknownCall) {
1392  Changed |= addNoAliasAttrs(SCCNodes);
1393  Changed |= addNonNullAttrs(SCCNodes);
1394  Changed |= inferAttrsFromFunctionBodies(SCCNodes);
1395  Changed |= addNoRecurseAttrs(SCCNodes);
1396  }
1397 
1398  return Changed;
1399 }
1400 
1403  LazyCallGraph &CG,
1404  CGSCCUpdateResult &) {
1406  AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C, CG).getManager();
1407 
1408  // We pass a lambda into functions to wire them up to the analysis manager
1409  // for getting function analyses.
1410  auto AARGetter = [&](Function &F) -> AAResults & {
1411  return FAM.getResult<AAManager>(F);
1412  };
1413 
1414  // Fill SCCNodes with the elements of the SCC. Also track whether there are
1415  // any external or opt-none nodes that will prevent us from optimizing any
1416  // part of the SCC.
1417  SCCNodeSet SCCNodes;
1418  bool HasUnknownCall = false;
1419  for (LazyCallGraph::Node &N : C) {
1420  Function &F = N.getFunction();
1421  if (F.hasOptNone() || F.hasFnAttribute(Attribute::Naked)) {
1422  // Treat any function we're trying not to optimize as if it were an
1423  // indirect call and omit it from the node set used below.
1424  HasUnknownCall = true;
1425  continue;
1426  }
1427  // Track whether any functions in this SCC have an unknown call edge.
1428  // Note: if this is ever a performance hit, we can common it with
1429  // subsequent routines which also do scans over the instructions of the
1430  // function.
1431  if (!HasUnknownCall)
1432  for (Instruction &I : instructions(F))
1433  if (auto CS = CallSite(&I))
1434  if (!CS.getCalledFunction()) {
1435  HasUnknownCall = true;
1436  break;
1437  }
1438 
1439  SCCNodes.insert(&F);
1440  }
1441 
1442  if (deriveAttrsInPostOrder(SCCNodes, AARGetter, HasUnknownCall))
1443  return PreservedAnalyses::none();
1444 
1445  return PreservedAnalyses::all();
1446 }
1447 
1448 namespace {
1449 
1450 struct PostOrderFunctionAttrsLegacyPass : public CallGraphSCCPass {
1451  // Pass identification, replacement for typeid
1452  static char ID;
1453 
1454  PostOrderFunctionAttrsLegacyPass() : CallGraphSCCPass(ID) {
1457  }
1458 
1459  bool runOnSCC(CallGraphSCC &SCC) override;
1460 
1461  void getAnalysisUsage(AnalysisUsage &AU) const override {
1462  AU.setPreservesCFG();
1466  }
1467 };
1468 
1469 } // end anonymous namespace
1470 
1472 INITIALIZE_PASS_BEGIN(PostOrderFunctionAttrsLegacyPass, "functionattrs",
1473  "Deduce function attributes", false, false)
1476 INITIALIZE_PASS_END(PostOrderFunctionAttrsLegacyPass, "functionattrs",
1477  "Deduce function attributes", false, false)
1478 
1480  return new PostOrderFunctionAttrsLegacyPass();
1481 }
1482 
1483 template <typename AARGetterT>
1484 static bool runImpl(CallGraphSCC &SCC, AARGetterT AARGetter) {
1485 
1486  // Fill SCCNodes with the elements of the SCC. Used for quickly looking up
1487  // whether a given CallGraphNode is in this SCC. Also track whether there are
1488  // any external or opt-none nodes that will prevent us from optimizing any
1489  // part of the SCC.
1490  SCCNodeSet SCCNodes;
1491  bool ExternalNode = false;
1492  for (CallGraphNode *I : SCC) {
1493  Function *F = I->getFunction();
1494  if (!F || F->hasOptNone() || F->hasFnAttribute(Attribute::Naked)) {
1495  // External node or function we're trying not to optimize - we both avoid
1496  // transform them and avoid leveraging information they provide.
1497  ExternalNode = true;
1498  continue;
1499  }
1500 
1501  SCCNodes.insert(F);
1502  }
1503 
1504  return deriveAttrsInPostOrder(SCCNodes, AARGetter, ExternalNode);
1505 }
1506 
1507 bool PostOrderFunctionAttrsLegacyPass::runOnSCC(CallGraphSCC &SCC) {
1508  if (skipSCC(SCC))
1509  return false;
1510  return runImpl(SCC, LegacyAARGetter(*this));
1511 }
1512 
1513 namespace {
1514 
1515 struct ReversePostOrderFunctionAttrsLegacyPass : public ModulePass {
1516  // Pass identification, replacement for typeid
1517  static char ID;
1518 
1519  ReversePostOrderFunctionAttrsLegacyPass() : ModulePass(ID) {
1522  }
1523 
1524  bool runOnModule(Module &M) override;
1525 
1526  void getAnalysisUsage(AnalysisUsage &AU) const override {
1527  AU.setPreservesCFG();
1530  }
1531 };
1532 
1533 } // end anonymous namespace
1534 
1536 
1537 INITIALIZE_PASS_BEGIN(ReversePostOrderFunctionAttrsLegacyPass, "rpo-functionattrs",
1538  "Deduce function attributes in RPO", false, false)
1540 INITIALIZE_PASS_END(ReversePostOrderFunctionAttrsLegacyPass, "rpo-functionattrs",
1541  "Deduce function attributes in RPO", false, false)
1542 
1544  return new ReversePostOrderFunctionAttrsLegacyPass();
1545 }
1546 
1548  // We check the preconditions for the function prior to calling this to avoid
1549  // the cost of building up a reversible post-order list. We assert them here
1550  // to make sure none of the invariants this relies on were violated.
1551  assert(!F.isDeclaration() && "Cannot deduce norecurse without a definition!");
1552  assert(!F.doesNotRecurse() &&
1553  "This function has already been deduced as norecurs!");
1554  assert(F.hasInternalLinkage() &&
1555  "Can only do top-down deduction for internal linkage functions!");
1556 
1557  // If F is internal and all of its uses are calls from a non-recursive
1558  // functions, then none of its calls could in fact recurse without going
1559  // through a function marked norecurse, and so we can mark this function too
1560  // as norecurse. Note that the uses must actually be calls -- otherwise
1561  // a pointer to this function could be returned from a norecurse function but
1562  // this function could be recursively (indirectly) called. Note that this
1563  // also detects if F is directly recursive as F is not yet marked as
1564  // a norecurse function.
1565  for (auto *U : F.users()) {
1566  auto *I = dyn_cast<Instruction>(U);
1567  if (!I)
1568  return false;
1569  CallSite CS(I);
1570  if (!CS || !CS.getParent()->getParent()->doesNotRecurse())
1571  return false;
1572  }
1573  return setDoesNotRecurse(F);
1574 }
1575 
1577  // We only have a post-order SCC traversal (because SCCs are inherently
1578  // discovered in post-order), so we accumulate them in a vector and then walk
1579  // it in reverse. This is simpler than using the RPO iterator infrastructure
1580  // because we need to combine SCC detection and the PO walk of the call
1581  // graph. We can also cheat egregiously because we're primarily interested in
1582  // synthesizing norecurse and so we can only save the singular SCCs as SCCs
1583  // with multiple functions in them will clearly be recursive.
1584  SmallVector<Function *, 16> Worklist;
1585  for (scc_iterator<CallGraph *> I = scc_begin(&CG); !I.isAtEnd(); ++I) {
1586  if (I->size() != 1)
1587  continue;
1588 
1589  Function *F = I->front()->getFunction();
1590  if (F && !F->isDeclaration() && !F->doesNotRecurse() &&
1591  F->hasInternalLinkage())
1592  Worklist.push_back(F);
1593  }
1594 
1595  bool Changed = false;
1596  for (auto *F : llvm::reverse(Worklist))
1597  Changed |= addNoRecurseAttrsTopDown(*F);
1598 
1599  return Changed;
1600 }
1601 
1602 bool ReversePostOrderFunctionAttrsLegacyPass::runOnModule(Module &M) {
1603  if (skipModule(M))
1604  return false;
1605 
1606  auto &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph();
1607 
1608  return deduceFunctionAttributeInRPO(M, CG);
1609 }
1610 
1613  auto &CG = AM.getResult<CallGraphAnalysis>(M);
1614 
1615  if (!deduceFunctionAttributeInRPO(M, CG))
1616  return PreservedAnalyses::all();
1617 
1618  PreservedAnalyses PA;
1620  return PA;
1621 }
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:354
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
This class represents an incoming formal argument to a Function.
Definition: Argument.h: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:1239
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...
No attributes have been set.
Definition: Attributes.h:71
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:273
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:244
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:1199
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:722
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:1359
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:399
LLVM_NODISCARD bool isNoModRef(const ModRefInfo MRI)
static bool addNoAliasAttrs(const SCCNodeSet &SCCNodes)
Deduce noalias attributes for the SCC.
const Value * getFalseValue() const
static bool addArgumentAttrs(const SCCNodeSet &SCCNodes)
Deduce nocapture attributes for the SCC.
static bool inferAttrsFromFunctionBodies(const SCCNodeSet &SCCNodes)
Infer attributes from all functions in the SCC by scanning every instruction for compliance to the at...
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:227
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
LLVM Value Representation.
Definition: Value.h:72
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:250
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:69
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