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