LLVM  15.0.0git
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/ArrayRef.h"
17 #include "llvm/ADT/DenseMap.h"
18 #include "llvm/ADT/SCCIterator.h"
19 #include "llvm/ADT/STLExtras.h"
20 #include "llvm/ADT/SetVector.h"
21 #include "llvm/ADT/SmallPtrSet.h"
22 #include "llvm/ADT/SmallSet.h"
23 #include "llvm/ADT/SmallVector.h"
24 #include "llvm/ADT/Statistic.h"
27 #include "llvm/Analysis/CFG.h"
35 #include "llvm/IR/Argument.h"
36 #include "llvm/IR/Attributes.h"
37 #include "llvm/IR/BasicBlock.h"
38 #include "llvm/IR/Constant.h"
39 #include "llvm/IR/Constants.h"
40 #include "llvm/IR/Function.h"
41 #include "llvm/IR/InstIterator.h"
42 #include "llvm/IR/InstrTypes.h"
43 #include "llvm/IR/Instruction.h"
44 #include "llvm/IR/Instructions.h"
45 #include "llvm/IR/IntrinsicInst.h"
46 #include "llvm/IR/Metadata.h"
48 #include "llvm/IR/PassManager.h"
49 #include "llvm/IR/Type.h"
50 #include "llvm/IR/Use.h"
51 #include "llvm/IR/User.h"
52 #include "llvm/IR/Value.h"
53 #include "llvm/InitializePasses.h"
54 #include "llvm/Pass.h"
55 #include "llvm/Support/Casting.h"
57 #include "llvm/Support/Compiler.h"
58 #include "llvm/Support/Debug.h"
61 #include "llvm/Transforms/IPO.h"
63 #include <cassert>
64 #include <iterator>
65 #include <map>
66 #include <vector>
67 
68 using namespace llvm;
69 
70 #define DEBUG_TYPE "function-attrs"
71 
72 STATISTIC(NumArgMemOnly, "Number of functions marked argmemonly");
73 STATISTIC(NumReadNone, "Number of functions marked readnone");
74 STATISTIC(NumReadOnly, "Number of functions marked readonly");
75 STATISTIC(NumWriteOnly, "Number of functions marked writeonly");
76 STATISTIC(NumNoCapture, "Number of arguments marked nocapture");
77 STATISTIC(NumReturned, "Number of arguments marked returned");
78 STATISTIC(NumReadNoneArg, "Number of arguments marked readnone");
79 STATISTIC(NumReadOnlyArg, "Number of arguments marked readonly");
80 STATISTIC(NumWriteOnlyArg, "Number of arguments marked writeonly");
81 STATISTIC(NumNoAlias, "Number of function returns marked noalias");
82 STATISTIC(NumNonNullReturn, "Number of function returns marked nonnull");
83 STATISTIC(NumNoRecurse, "Number of functions marked as norecurse");
84 STATISTIC(NumNoUnwind, "Number of functions marked as nounwind");
85 STATISTIC(NumNoFree, "Number of functions marked as nofree");
86 STATISTIC(NumWillReturn, "Number of functions marked as willreturn");
87 STATISTIC(NumNoSync, "Number of functions marked as nosync");
88 
89 STATISTIC(NumThinLinkNoRecurse,
90  "Number of functions marked as norecurse during thinlink");
91 STATISTIC(NumThinLinkNoUnwind,
92  "Number of functions marked as nounwind during thinlink");
93 
95  "enable-nonnull-arg-prop", cl::init(true), cl::Hidden,
96  cl::desc("Try to propagate nonnull argument attributes from callsites to "
97  "caller functions."));
98 
100  "disable-nounwind-inference", cl::Hidden,
101  cl::desc("Stop inferring nounwind attribute during function-attrs pass"));
102 
104  "disable-nofree-inference", cl::Hidden,
105  cl::desc("Stop inferring nofree attribute during function-attrs pass"));
106 
108  "disable-thinlto-funcattrs", cl::init(true), cl::Hidden,
109  cl::desc("Don't propagate function-attrs in thinLTO"));
110 
111 namespace {
112 
113 using SCCNodeSet = SmallSetVector<Function *, 8>;
114 
115 } // end anonymous namespace
116 
117 /// Returns the memory access attribute for function F using AAR for AA results,
118 /// where SCCNodes is the current SCC.
119 ///
120 /// If ThisBody is true, this function may examine the function body and will
121 /// return a result pertaining to this copy of the function. If it is false, the
122 /// result will be based only on AA results for the function declaration; it
123 /// will be assumed that some other (perhaps less optimized) version of the
124 /// function may be selected at link time.
127  const SCCNodeSet &SCCNodes) {
129  if (MRB == FMRB_DoesNotAccessMemory)
130  // Already perfect!
131  return MRB;
132 
133  if (!ThisBody)
134  return MRB;
135 
136  // Scan the function body for instructions that may read or write memory.
137  bool ReadsMemory = false;
138  bool WritesMemory = false;
139  // Track if the function accesses memory not based on pointer arguments or
140  // allocas.
141  bool AccessesNonArgsOrAlloca = false;
142  // Returns true if Ptr is not based on a function argument.
143  auto IsArgumentOrAlloca = [](const Value *Ptr) {
144  const Value *UO = getUnderlyingObject(Ptr);
145  return isa<Argument>(UO) || isa<AllocaInst>(UO);
146  };
147  for (Instruction &I : instructions(F)) {
148  // Some instructions can be ignored even if they read or write memory.
149  // Detect these now, skipping to the next instruction if one is found.
150  if (auto *Call = dyn_cast<CallBase>(&I)) {
151  // Ignore calls to functions in the same SCC, as long as the call sites
152  // don't have operand bundles. Calls with operand bundles are allowed to
153  // have memory effects not described by the memory effects of the call
154  // target.
155  if (!Call->hasOperandBundles() && Call->getCalledFunction() &&
156  SCCNodes.count(Call->getCalledFunction()))
157  continue;
160 
161  // If the call doesn't access memory, we're done.
162  if (isNoModRef(MRI))
163  continue;
164 
165  // A pseudo probe call shouldn't change any function attribute since it
166  // doesn't translate to a real instruction. It comes with a memory access
167  // tag to prevent itself being removed by optimizations and not block
168  // other instructions being optimized.
169  if (isa<PseudoProbeInst>(I))
170  continue;
171 
173  // The call could access any memory. If that includes writes, note it.
174  if (isModSet(MRI))
175  WritesMemory = true;
176  // If it reads, note it.
177  if (isRefSet(MRI))
178  ReadsMemory = true;
179  AccessesNonArgsOrAlloca = true;
180  continue;
181  }
182 
183  // Check whether all pointer arguments point to local memory, and
184  // ignore calls that only access local memory.
185  for (const Use &U : Call->args()) {
186  const Value *Arg = U;
187  if (!Arg->getType()->isPtrOrPtrVectorTy())
188  continue;
189 
190  MemoryLocation Loc =
191  MemoryLocation::getBeforeOrAfter(Arg, I.getAAMetadata());
192  // Skip accesses to local or constant memory as they don't impact the
193  // externally visible mod/ref behavior.
194  if (AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true))
195  continue;
196 
197  AccessesNonArgsOrAlloca |= !IsArgumentOrAlloca(Loc.Ptr);
198 
199  if (isModSet(MRI))
200  // Writes non-local memory.
201  WritesMemory = true;
202  if (isRefSet(MRI))
203  // Ok, it reads non-local memory.
204  ReadsMemory = true;
205  }
206  continue;
207  } else if (LoadInst *LI = dyn_cast<LoadInst>(&I)) {
209  // Ignore non-volatile loads from local memory. (Atomic is okay here.)
210  if (!LI->isVolatile() &&
211  AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true))
212  continue;
213  AccessesNonArgsOrAlloca |= !IsArgumentOrAlloca(Loc.Ptr);
214  } else if (StoreInst *SI = dyn_cast<StoreInst>(&I)) {
216  // Ignore non-volatile stores to local memory. (Atomic is okay here.)
217  if (!SI->isVolatile() &&
218  AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true))
219  continue;
220  AccessesNonArgsOrAlloca |= !IsArgumentOrAlloca(Loc.Ptr);
221  } else if (VAArgInst *VI = dyn_cast<VAArgInst>(&I)) {
222  // Ignore vaargs on local memory.
224  if (AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true))
225  continue;
226  AccessesNonArgsOrAlloca |= !IsArgumentOrAlloca(Loc.Ptr);
227  } else {
228  // If AccessesNonArgsOrAlloca has not been updated above, set it
229  // conservatively.
230  AccessesNonArgsOrAlloca |= I.mayReadOrWriteMemory();
231  }
232 
233  // Any remaining instructions need to be taken seriously! Check if they
234  // read or write memory.
235  //
236  // Writes memory, remember that.
237  WritesMemory |= I.mayWriteToMemory();
238 
239  // If this instruction may read memory, remember that.
240  ReadsMemory |= I.mayReadFromMemory();
241  }
242 
243  if (!WritesMemory && !ReadsMemory)
245 
247  if (!AccessesNonArgsOrAlloca)
249  if (WritesMemory)
250  Result = FunctionModRefBehavior(Result | static_cast<int>(ModRefInfo::Mod));
251  if (ReadsMemory)
252  Result = FunctionModRefBehavior(Result | static_cast<int>(ModRefInfo::Ref));
253  return Result;
254 }
255 
257  AAResults &AAR) {
258  return checkFunctionMemoryAccess(F, /*ThisBody=*/true, AAR, {});
259 }
260 
261 /// Deduce readonly/readnone/writeonly attributes for the SCC.
262 template <typename AARGetterT>
263 static void addMemoryAttrs(const SCCNodeSet &SCCNodes, AARGetterT &&AARGetter,
264  SmallSet<Function *, 8> &Changed) {
265  // Check if any of the functions in the SCC read or write memory. If they
266  // write memory then they can't be marked readnone or readonly.
267  bool ReadsMemory = false;
268  bool WritesMemory = false;
269  // Check if all functions only access memory through their arguments.
270  bool ArgMemOnly = true;
271  for (Function *F : SCCNodes) {
272  // Call the callable parameter to look up AA results for this function.
273  AAResults &AAR = AARGetter(*F);
274  // Non-exact function definitions may not be selected at link time, and an
275  // alternative version that writes to memory may be selected. See the
276  // comment on GlobalValue::isDefinitionExact for more details.
278  checkFunctionMemoryAccess(*F, F->hasExactDefinition(), AAR, SCCNodes);
279  if (FMRB == FMRB_DoesNotAccessMemory)
280  continue;
281  ModRefInfo MR = createModRefInfo(FMRB);
282  ReadsMemory |= isRefSet(MR);
283  WritesMemory |= isModSet(MR);
284  ArgMemOnly &= AliasAnalysis::onlyAccessesArgPointees(FMRB);
285  // Reached neither readnone, readonly, writeonly nor argmemonly can be
286  // inferred. Exit.
287  if (ReadsMemory && WritesMemory && !ArgMemOnly)
288  return;
289  }
290 
291  assert((!ReadsMemory || !WritesMemory || ArgMemOnly) &&
292  "no memory attributes can be added for this SCC, should have exited "
293  "earlier");
294  // Success! Functions in this SCC do not access memory, only read memory,
295  // only write memory, or only access memory through its arguments. Give them
296  // the appropriate attribute.
297 
298  for (Function *F : SCCNodes) {
299  // If possible add argmemonly attribute to F, if it accesses memory.
300  if (ArgMemOnly && !F->onlyAccessesArgMemory() &&
301  (ReadsMemory || WritesMemory)) {
302  NumArgMemOnly++;
303  F->addFnAttr(Attribute::ArgMemOnly);
304  Changed.insert(F);
305  }
306 
307  // The SCC contains functions both writing and reading from memory. We
308  // cannot add readonly or writeonline attributes.
309  if (ReadsMemory && WritesMemory)
310  continue;
311  if (F->doesNotAccessMemory())
312  // Already perfect!
313  continue;
314 
315  if (F->onlyReadsMemory() && ReadsMemory)
316  // No change.
317  continue;
318 
319  if (F->onlyWritesMemory() && WritesMemory)
320  continue;
321 
322  Changed.insert(F);
323 
324  // Clear out any existing attributes.
325  AttributeMask AttrsToRemove;
326  AttrsToRemove.addAttribute(Attribute::ReadOnly);
327  AttrsToRemove.addAttribute(Attribute::ReadNone);
328  AttrsToRemove.addAttribute(Attribute::WriteOnly);
329 
330  if (!WritesMemory && !ReadsMemory) {
331  // Clear out any "access range attributes" if readnone was deduced.
332  AttrsToRemove.addAttribute(Attribute::ArgMemOnly);
333  AttrsToRemove.addAttribute(Attribute::InaccessibleMemOnly);
334  AttrsToRemove.addAttribute(Attribute::InaccessibleMemOrArgMemOnly);
335  }
336  F->removeFnAttrs(AttrsToRemove);
337 
338  // Add in the new attribute.
339  if (WritesMemory && !ReadsMemory)
340  F->addFnAttr(Attribute::WriteOnly);
341  else
342  F->addFnAttr(ReadsMemory ? Attribute::ReadOnly : Attribute::ReadNone);
343 
344  if (WritesMemory && !ReadsMemory)
345  ++NumWriteOnly;
346  else if (ReadsMemory)
347  ++NumReadOnly;
348  else
349  ++NumReadNone;
350  }
351 }
352 
353 // Compute definitive function attributes for a function taking into account
354 // prevailing definitions and linkage types
356  ValueInfo VI,
357  DenseMap<ValueInfo, FunctionSummary *> &CachedPrevailingSummary,
359  IsPrevailing) {
360 
361  if (CachedPrevailingSummary.count(VI))
362  return CachedPrevailingSummary[VI];
363 
364  /// At this point, prevailing symbols have been resolved. The following leads
365  /// to returning a conservative result:
366  /// - Multiple instances with local linkage. Normally local linkage would be
367  /// unique per module
368  /// as the GUID includes the module path. We could have a guid alias if
369  /// there wasn't any distinguishing path when each file was compiled, but
370  /// that should be rare so we'll punt on those.
371 
372  /// These next 2 cases should not happen and will assert:
373  /// - Multiple instances with external linkage. This should be caught in
374  /// symbol resolution
375  /// - Non-existent FunctionSummary for Aliasee. This presents a hole in our
376  /// knowledge meaning we have to go conservative.
377 
378  /// Otherwise, we calculate attributes for a function as:
379  /// 1. If we have a local linkage, take its attributes. If there's somehow
380  /// multiple, bail and go conservative.
381  /// 2. If we have an external/WeakODR/LinkOnceODR linkage check that it is
382  /// prevailing, take its attributes.
383  /// 3. If we have a Weak/LinkOnce linkage the copies can have semantic
384  /// differences. However, if the prevailing copy is known it will be used
385  /// so take its attributes. If the prevailing copy is in a native file
386  /// all IR copies will be dead and propagation will go conservative.
387  /// 4. AvailableExternally summaries without a prevailing copy are known to
388  /// occur in a couple of circumstances:
389  /// a. An internal function gets imported due to its caller getting
390  /// imported, it becomes AvailableExternally but no prevailing
391  /// definition exists. Because it has to get imported along with its
392  /// caller the attributes will be captured by propagating on its
393  /// caller.
394  /// b. C++11 [temp.explicit]p10 can generate AvailableExternally
395  /// definitions of explicitly instanced template declarations
396  /// for inlining which are ultimately dropped from the TU. Since this
397  /// is localized to the TU the attributes will have already made it to
398  /// the callers.
399  /// These are edge cases and already captured by their callers so we
400  /// ignore these for now. If they become relevant to optimize in the
401  /// future this can be revisited.
402  /// 5. Otherwise, go conservative.
403 
404  CachedPrevailingSummary[VI] = nullptr;
405  FunctionSummary *Local = nullptr;
406  FunctionSummary *Prevailing = nullptr;
407 
408  for (const auto &GVS : VI.getSummaryList()) {
409  if (!GVS->isLive())
410  continue;
411 
412  FunctionSummary *FS = dyn_cast<FunctionSummary>(GVS->getBaseObject());
413  // Virtual and Unknown (e.g. indirect) calls require going conservative
414  if (!FS || FS->fflags().HasUnknownCall)
415  return nullptr;
416 
417  const auto &Linkage = GVS->linkage();
418  if (GlobalValue::isLocalLinkage(Linkage)) {
419  if (Local) {
420  LLVM_DEBUG(
421  dbgs()
422  << "ThinLTO FunctionAttrs: Multiple Local Linkage, bailing on "
423  "function "
424  << VI.name() << " from " << FS->modulePath() << ". Previous module "
425  << Local->modulePath() << "\n");
426  return nullptr;
427  }
428  Local = FS;
429  } else if (GlobalValue::isExternalLinkage(Linkage)) {
430  assert(IsPrevailing(VI.getGUID(), GVS.get()));
431  Prevailing = FS;
432  break;
433  } else if (GlobalValue::isWeakODRLinkage(Linkage) ||
437  if (IsPrevailing(VI.getGUID(), GVS.get())) {
438  Prevailing = FS;
439  break;
440  }
441  } else if (GlobalValue::isAvailableExternallyLinkage(Linkage)) {
442  // TODO: Handle these cases if they become meaningful
443  continue;
444  }
445  }
446 
447  if (Local) {
448  assert(!Prevailing);
449  CachedPrevailingSummary[VI] = Local;
450  } else if (Prevailing) {
451  assert(!Local);
452  CachedPrevailingSummary[VI] = Prevailing;
453  }
454 
455  return CachedPrevailingSummary[VI];
456 }
457 
461  IsPrevailing) {
462  // TODO: implement addNoAliasAttrs once
463  // there's more information about the return type in the summary
465  return false;
466 
467  DenseMap<ValueInfo, FunctionSummary *> CachedPrevailingSummary;
468  bool Changed = false;
469 
470  auto PropagateAttributes = [&](std::vector<ValueInfo> &SCCNodes) {
471  // Assume we can propagate unless we discover otherwise
472  FunctionSummary::FFlags InferredFlags;
473  InferredFlags.NoRecurse = (SCCNodes.size() == 1);
474  InferredFlags.NoUnwind = true;
475 
476  for (auto &V : SCCNodes) {
477  FunctionSummary *CallerSummary =
478  calculatePrevailingSummary(V, CachedPrevailingSummary, IsPrevailing);
479 
480  // Function summaries can fail to contain information such as declarations
481  if (!CallerSummary)
482  return;
483 
484  if (CallerSummary->fflags().MayThrow)
485  InferredFlags.NoUnwind = false;
486 
487  for (const auto &Callee : CallerSummary->calls()) {
489  Callee.first, CachedPrevailingSummary, IsPrevailing);
490 
491  if (!CalleeSummary)
492  return;
493 
494  if (!CalleeSummary->fflags().NoRecurse)
495  InferredFlags.NoRecurse = false;
496 
497  if (!CalleeSummary->fflags().NoUnwind)
498  InferredFlags.NoUnwind = false;
499 
500  if (!InferredFlags.NoUnwind && !InferredFlags.NoRecurse)
501  break;
502  }
503  }
504 
505  if (InferredFlags.NoUnwind || InferredFlags.NoRecurse) {
506  Changed = true;
507  for (auto &V : SCCNodes) {
508  if (InferredFlags.NoRecurse) {
509  LLVM_DEBUG(dbgs() << "ThinLTO FunctionAttrs: Propagated NoRecurse to "
510  << V.name() << "\n");
511  ++NumThinLinkNoRecurse;
512  }
513 
514  if (InferredFlags.NoUnwind) {
515  LLVM_DEBUG(dbgs() << "ThinLTO FunctionAttrs: Propagated NoUnwind to "
516  << V.name() << "\n");
517  ++NumThinLinkNoUnwind;
518  }
519 
520  for (auto &S : V.getSummaryList()) {
521  if (auto *FS = dyn_cast<FunctionSummary>(S.get())) {
522  if (InferredFlags.NoRecurse)
523  FS->setNoRecurse();
524 
525  if (InferredFlags.NoUnwind)
526  FS->setNoUnwind();
527  }
528  }
529  }
530  }
531  };
532 
533  // Call propagation functions on each SCC in the Index
535  ++I) {
536  std::vector<ValueInfo> Nodes(*I);
537  PropagateAttributes(Nodes);
538  }
539  return Changed;
540 }
541 
542 namespace {
543 
544 /// For a given pointer Argument, this retains a list of Arguments of functions
545 /// in the same SCC that the pointer data flows into. We use this to build an
546 /// SCC of the arguments.
547 struct ArgumentGraphNode {
548  Argument *Definition;
550 };
551 
552 class ArgumentGraph {
553  // We store pointers to ArgumentGraphNode objects, so it's important that
554  // that they not move around upon insert.
555  using ArgumentMapTy = std::map<Argument *, ArgumentGraphNode>;
556 
557  ArgumentMapTy ArgumentMap;
558 
559  // There is no root node for the argument graph, in fact:
560  // void f(int *x, int *y) { if (...) f(x, y); }
561  // is an example where the graph is disconnected. The SCCIterator requires a
562  // single entry point, so we maintain a fake ("synthetic") root node that
563  // uses every node. Because the graph is directed and nothing points into
564  // the root, it will not participate in any SCCs (except for its own).
565  ArgumentGraphNode SyntheticRoot;
566 
567 public:
568  ArgumentGraph() { SyntheticRoot.Definition = nullptr; }
569 
571 
572  iterator begin() { return SyntheticRoot.Uses.begin(); }
573  iterator end() { return SyntheticRoot.Uses.end(); }
574  ArgumentGraphNode *getEntryNode() { return &SyntheticRoot; }
575 
576  ArgumentGraphNode *operator[](Argument *A) {
577  ArgumentGraphNode &Node = ArgumentMap[A];
578  Node.Definition = A;
579  SyntheticRoot.Uses.push_back(&Node);
580  return &Node;
581  }
582 };
583 
584 /// This tracker checks whether callees are in the SCC, and if so it does not
585 /// consider that a capture, instead adding it to the "Uses" list and
586 /// continuing with the analysis.
587 struct ArgumentUsesTracker : public CaptureTracker {
588  ArgumentUsesTracker(const SCCNodeSet &SCCNodes) : SCCNodes(SCCNodes) {}
589 
590  void tooManyUses() override { Captured = true; }
591 
592  bool captured(const Use *U) override {
593  CallBase *CB = dyn_cast<CallBase>(U->getUser());
594  if (!CB) {
595  Captured = true;
596  return true;
597  }
598 
599  Function *F = CB->getCalledFunction();
600  if (!F || !F->hasExactDefinition() || !SCCNodes.count(F)) {
601  Captured = true;
602  return true;
603  }
604 
605  assert(!CB->isCallee(U) && "callee operand reported captured?");
606  const unsigned UseIndex = CB->getDataOperandNo(U);
607  if (UseIndex >= CB->arg_size()) {
608  // Data operand, but not a argument operand -- must be a bundle operand
609  assert(CB->hasOperandBundles() && "Must be!");
610 
611  // CaptureTracking told us that we're being captured by an operand bundle
612  // use. In this case it does not matter if the callee is within our SCC
613  // or not -- we've been captured in some unknown way, and we have to be
614  // conservative.
615  Captured = true;
616  return true;
617  }
618 
619  if (UseIndex >= F->arg_size()) {
620  assert(F->isVarArg() && "More params than args in non-varargs call");
621  Captured = true;
622  return true;
623  }
624 
625  Uses.push_back(&*std::next(F->arg_begin(), UseIndex));
626  return false;
627  }
628 
629  // True only if certainly captured (used outside our SCC).
630  bool Captured = false;
631 
632  // Uses within our SCC.
634 
635  const SCCNodeSet &SCCNodes;
636 };
637 
638 } // end anonymous namespace
639 
640 namespace llvm {
641 
642 template <> struct GraphTraits<ArgumentGraphNode *> {
643  using NodeRef = ArgumentGraphNode *;
645 
646  static NodeRef getEntryNode(NodeRef A) { return A; }
647  static ChildIteratorType child_begin(NodeRef N) { return N->Uses.begin(); }
648  static ChildIteratorType child_end(NodeRef N) { return N->Uses.end(); }
649 };
650 
651 template <>
652 struct GraphTraits<ArgumentGraph *> : public GraphTraits<ArgumentGraphNode *> {
653  static NodeRef getEntryNode(ArgumentGraph *AG) { return AG->getEntryNode(); }
654 
655  static ChildIteratorType nodes_begin(ArgumentGraph *AG) {
656  return AG->begin();
657  }
658 
659  static ChildIteratorType nodes_end(ArgumentGraph *AG) { return AG->end(); }
660 };
661 
662 } // end namespace llvm
663 
664 /// Returns Attribute::None, Attribute::ReadOnly or Attribute::ReadNone.
665 static Attribute::AttrKind
667  const SmallPtrSet<Argument *, 8> &SCCNodes) {
668  SmallVector<Use *, 32> Worklist;
669  SmallPtrSet<Use *, 32> Visited;
670 
671  // inalloca arguments are always clobbered by the call.
672  if (A->hasInAllocaAttr() || A->hasPreallocatedAttr())
673  return Attribute::None;
674 
675  bool IsRead = false;
676  bool IsWrite = false;
677 
678  for (Use &U : A->uses()) {
679  Visited.insert(&U);
680  Worklist.push_back(&U);
681  }
682 
683  while (!Worklist.empty()) {
684  if (IsWrite && IsRead)
685  // No point in searching further..
686  return Attribute::None;
687 
688  Use *U = Worklist.pop_back_val();
689  Instruction *I = cast<Instruction>(U->getUser());
690 
691  switch (I->getOpcode()) {
692  case Instruction::BitCast:
693  case Instruction::GetElementPtr:
694  case Instruction::PHI:
695  case Instruction::Select:
696  case Instruction::AddrSpaceCast:
697  // The original value is not read/written via this if the new value isn't.
698  for (Use &UU : I->uses())
699  if (Visited.insert(&UU).second)
700  Worklist.push_back(&UU);
701  break;
702 
703  case Instruction::Call:
704  case Instruction::Invoke: {
705  CallBase &CB = cast<CallBase>(*I);
706  if (CB.isCallee(U)) {
707  IsRead = true;
708  // Note that indirect calls do not capture, see comment in
709  // CaptureTracking for context
710  continue;
711  }
712 
713  // Given we've explictily handled the callee operand above, what's left
714  // must be a data operand (e.g. argument or operand bundle)
715  const unsigned UseIndex = CB.getDataOperandNo(U);
716 
717  if (!CB.doesNotCapture(UseIndex)) {
718  if (!CB.onlyReadsMemory())
719  // If the callee can save a copy into other memory, then simply
720  // scanning uses of the call is insufficient. We have no way
721  // of tracking copies of the pointer through memory to see
722  // if a reloaded copy is written to, thus we must give up.
723  return Attribute::None;
724  // Push users for processing once we finish this one
725  if (!I->getType()->isVoidTy())
726  for (Use &UU : I->uses())
727  if (Visited.insert(&UU).second)
728  Worklist.push_back(&UU);
729  }
730 
731  if (CB.doesNotAccessMemory())
732  continue;
733 
734  if (Function *F = CB.getCalledFunction())
735  if (CB.isArgOperand(U) && UseIndex < F->arg_size() &&
736  SCCNodes.count(F->getArg(UseIndex)))
737  // This is an argument which is part of the speculative SCC. Note
738  // that only operands corresponding to formal arguments of the callee
739  // can participate in the speculation.
740  break;
741 
742  // The accessors used on call site here do the right thing for calls and
743  // invokes with operand bundles.
744  if (CB.doesNotAccessMemory(UseIndex)) {
745  /* nop */
746  } else if (CB.onlyReadsMemory() || CB.onlyReadsMemory(UseIndex)) {
747  IsRead = true;
748  } else if (CB.hasFnAttr(Attribute::WriteOnly) ||
749  CB.dataOperandHasImpliedAttr(UseIndex, Attribute::WriteOnly)) {
750  IsWrite = true;
751  } else {
752  return Attribute::None;
753  }
754  break;
755  }
756 
757  case Instruction::Load:
758  // A volatile load has side effects beyond what readonly can be relied
759  // upon.
760  if (cast<LoadInst>(I)->isVolatile())
761  return Attribute::None;
762 
763  IsRead = true;
764  break;
765 
766  case Instruction::Store:
767  if (cast<StoreInst>(I)->getValueOperand() == *U)
768  // untrackable capture
769  return Attribute::None;
770 
771  // A volatile store has side effects beyond what writeonly can be relied
772  // upon.
773  if (cast<StoreInst>(I)->isVolatile())
774  return Attribute::None;
775 
776  IsWrite = true;
777  break;
778 
779  case Instruction::ICmp:
780  case Instruction::Ret:
781  break;
782 
783  default:
784  return Attribute::None;
785  }
786  }
787 
788  if (IsWrite && IsRead)
789  return Attribute::None;
790  else if (IsRead)
791  return Attribute::ReadOnly;
792  else if (IsWrite)
793  return Attribute::WriteOnly;
794  else
795  return Attribute::ReadNone;
796 }
797 
798 /// Deduce returned attributes for the SCC.
799 static void addArgumentReturnedAttrs(const SCCNodeSet &SCCNodes,
800  SmallSet<Function *, 8> &Changed) {
801  // Check each function in turn, determining if an argument is always returned.
802  for (Function *F : SCCNodes) {
803  // We can infer and propagate function attributes only when we know that the
804  // definition we'll get at link time is *exactly* the definition we see now.
805  // For more details, see GlobalValue::mayBeDerefined.
806  if (!F->hasExactDefinition())
807  continue;
808 
809  if (F->getReturnType()->isVoidTy())
810  continue;
811 
812  // There is nothing to do if an argument is already marked as 'returned'.
813  if (llvm::any_of(F->args(),
814  [](const Argument &Arg) { return Arg.hasReturnedAttr(); }))
815  continue;
816 
817  auto FindRetArg = [&]() -> Value * {
818  Value *RetArg = nullptr;
819  for (BasicBlock &BB : *F)
820  if (auto *Ret = dyn_cast<ReturnInst>(BB.getTerminator())) {
821  // Note that stripPointerCasts should look through functions with
822  // returned arguments.
823  Value *RetVal = Ret->getReturnValue()->stripPointerCasts();
824  if (!isa<Argument>(RetVal) || RetVal->getType() != F->getReturnType())
825  return nullptr;
826 
827  if (!RetArg)
828  RetArg = RetVal;
829  else if (RetArg != RetVal)
830  return nullptr;
831  }
832 
833  return RetArg;
834  };
835 
836  if (Value *RetArg = FindRetArg()) {
837  auto *A = cast<Argument>(RetArg);
838  A->addAttr(Attribute::Returned);
839  ++NumReturned;
840  Changed.insert(F);
841  }
842  }
843 }
844 
845 /// If a callsite has arguments that are also arguments to the parent function,
846 /// try to propagate attributes from the callsite's arguments to the parent's
847 /// arguments. This may be important because inlining can cause information loss
848 /// when attribute knowledge disappears with the inlined call.
851  return false;
852 
853  bool Changed = false;
854 
855  // For an argument attribute to transfer from a callsite to the parent, the
856  // call must be guaranteed to execute every time the parent is called.
857  // Conservatively, just check for calls in the entry block that are guaranteed
858  // to execute.
859  // TODO: This could be enhanced by testing if the callsite post-dominates the
860  // entry block or by doing simple forward walks or backward walks to the
861  // callsite.
862  BasicBlock &Entry = F.getEntryBlock();
863  for (Instruction &I : Entry) {
864  if (auto *CB = dyn_cast<CallBase>(&I)) {
865  if (auto *CalledFunc = CB->getCalledFunction()) {
866  for (auto &CSArg : CalledFunc->args()) {
867  if (!CSArg.hasNonNullAttr(/* AllowUndefOrPoison */ false))
868  continue;
869 
870  // If the non-null callsite argument operand is an argument to 'F'
871  // (the caller) and the call is guaranteed to execute, then the value
872  // must be non-null throughout 'F'.
873  auto *FArg = dyn_cast<Argument>(CB->getArgOperand(CSArg.getArgNo()));
874  if (FArg && !FArg->hasNonNullAttr()) {
875  FArg->addAttr(Attribute::NonNull);
876  Changed = true;
877  }
878  }
879  }
880  }
882  break;
883  }
884 
885  return Changed;
886 }
887 
889  assert((R == Attribute::ReadOnly || R == Attribute::ReadNone ||
890  R == Attribute::WriteOnly)
891  && "Must be an access attribute.");
892  assert(A && "Argument must not be null.");
893 
894  // If the argument already has the attribute, nothing needs to be done.
895  if (A->hasAttribute(R))
896  return false;
897 
898  // Otherwise, remove potentially conflicting attribute, add the new one,
899  // and update statistics.
900  A->removeAttr(Attribute::WriteOnly);
901  A->removeAttr(Attribute::ReadOnly);
902  A->removeAttr(Attribute::ReadNone);
903  A->addAttr(R);
904  if (R == Attribute::ReadOnly)
905  ++NumReadOnlyArg;
906  else if (R == Attribute::WriteOnly)
907  ++NumWriteOnlyArg;
908  else
909  ++NumReadNoneArg;
910  return true;
911 }
912 
913 /// Deduce nocapture attributes for the SCC.
914 static void addArgumentAttrs(const SCCNodeSet &SCCNodes,
915  SmallSet<Function *, 8> &Changed) {
916  ArgumentGraph AG;
917 
918  // Check each function in turn, determining which pointer arguments are not
919  // captured.
920  for (Function *F : SCCNodes) {
921  // We can infer and propagate function attributes only when we know that the
922  // definition we'll get at link time is *exactly* the definition we see now.
923  // For more details, see GlobalValue::mayBeDerefined.
924  if (!F->hasExactDefinition())
925  continue;
926 
928  Changed.insert(F);
929 
930  // Functions that are readonly (or readnone) and nounwind and don't return
931  // a value can't capture arguments. Don't analyze them.
932  if (F->onlyReadsMemory() && F->doesNotThrow() &&
933  F->getReturnType()->isVoidTy()) {
934  for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end(); A != E;
935  ++A) {
936  if (A->getType()->isPointerTy() && !A->hasNoCaptureAttr()) {
937  A->addAttr(Attribute::NoCapture);
938  ++NumNoCapture;
939  Changed.insert(F);
940  }
941  }
942  continue;
943  }
944 
945  for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end(); A != E;
946  ++A) {
947  if (!A->getType()->isPointerTy())
948  continue;
949  bool HasNonLocalUses = false;
950  if (!A->hasNoCaptureAttr()) {
951  ArgumentUsesTracker Tracker(SCCNodes);
952  PointerMayBeCaptured(&*A, &Tracker);
953  if (!Tracker.Captured) {
954  if (Tracker.Uses.empty()) {
955  // If it's trivially not captured, mark it nocapture now.
956  A->addAttr(Attribute::NoCapture);
957  ++NumNoCapture;
958  Changed.insert(F);
959  } else {
960  // If it's not trivially captured and not trivially not captured,
961  // then it must be calling into another function in our SCC. Save
962  // its particulars for Argument-SCC analysis later.
963  ArgumentGraphNode *Node = AG[&*A];
964  for (Argument *Use : Tracker.Uses) {
965  Node->Uses.push_back(AG[Use]);
966  if (Use != &*A)
967  HasNonLocalUses = true;
968  }
969  }
970  }
971  // Otherwise, it's captured. Don't bother doing SCC analysis on it.
972  }
973  if (!HasNonLocalUses && !A->onlyReadsMemory()) {
974  // Can we determine that it's readonly/readnone/writeonly without doing
975  // an SCC? Note that we don't allow any calls at all here, or else our
976  // result will be dependent on the iteration order through the
977  // functions in the SCC.
979  Self.insert(&*A);
981  if (R != Attribute::None)
982  if (addAccessAttr(A, R))
983  Changed.insert(F);
984  }
985  }
986  }
987 
988  // The graph we've collected is partial because we stopped scanning for
989  // argument uses once we solved the argument trivially. These partial nodes
990  // show up as ArgumentGraphNode objects with an empty Uses list, and for
991  // these nodes the final decision about whether they capture has already been
992  // made. If the definition doesn't have a 'nocapture' attribute by now, it
993  // captures.
994 
995  for (scc_iterator<ArgumentGraph *> I = scc_begin(&AG); !I.isAtEnd(); ++I) {
996  const std::vector<ArgumentGraphNode *> &ArgumentSCC = *I;
997  if (ArgumentSCC.size() == 1) {
998  if (!ArgumentSCC[0]->Definition)
999  continue; // synthetic root node
1000 
1001  // eg. "void f(int* x) { if (...) f(x); }"
1002  if (ArgumentSCC[0]->Uses.size() == 1 &&
1003  ArgumentSCC[0]->Uses[0] == ArgumentSCC[0]) {
1004  Argument *A = ArgumentSCC[0]->Definition;
1005  A->addAttr(Attribute::NoCapture);
1006  ++NumNoCapture;
1007  Changed.insert(A->getParent());
1008 
1009  // Infer the access attributes given the new nocapture one
1011  Self.insert(&*A);
1013  if (R != Attribute::None)
1014  addAccessAttr(A, R);
1015  }
1016  continue;
1017  }
1018 
1019  bool SCCCaptured = false;
1020  for (auto I = ArgumentSCC.begin(), E = ArgumentSCC.end();
1021  I != E && !SCCCaptured; ++I) {
1022  ArgumentGraphNode *Node = *I;
1023  if (Node->Uses.empty()) {
1024  if (!Node->Definition->hasNoCaptureAttr())
1025  SCCCaptured = true;
1026  }
1027  }
1028  if (SCCCaptured)
1029  continue;
1030 
1031  SmallPtrSet<Argument *, 8> ArgumentSCCNodes;
1032  // Fill ArgumentSCCNodes with the elements of the ArgumentSCC. Used for
1033  // quickly looking up whether a given Argument is in this ArgumentSCC.
1034  for (ArgumentGraphNode *I : ArgumentSCC) {
1035  ArgumentSCCNodes.insert(I->Definition);
1036  }
1037 
1038  for (auto I = ArgumentSCC.begin(), E = ArgumentSCC.end();
1039  I != E && !SCCCaptured; ++I) {
1040  ArgumentGraphNode *N = *I;
1041  for (ArgumentGraphNode *Use : N->Uses) {
1042  Argument *A = Use->Definition;
1043  if (A->hasNoCaptureAttr() || ArgumentSCCNodes.count(A))
1044  continue;
1045  SCCCaptured = true;
1046  break;
1047  }
1048  }
1049  if (SCCCaptured)
1050  continue;
1051 
1052  for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) {
1053  Argument *A = ArgumentSCC[i]->Definition;
1054  A->addAttr(Attribute::NoCapture);
1055  ++NumNoCapture;
1056  Changed.insert(A->getParent());
1057  }
1058 
1059  // We also want to compute readonly/readnone/writeonly. With a small number
1060  // of false negatives, we can assume that any pointer which is captured
1061  // isn't going to be provably readonly or readnone, since by definition
1062  // we can't analyze all uses of a captured pointer.
1063  //
1064  // The false negatives happen when the pointer is captured by a function
1065  // that promises readonly/readnone behaviour on the pointer, then the
1066  // pointer's lifetime ends before anything that writes to arbitrary memory.
1067  // Also, a readonly/readnone pointer may be returned, but returning a
1068  // pointer is capturing it.
1069 
1070  auto meetAccessAttr = [](Attribute::AttrKind A, Attribute::AttrKind B) {
1071  if (A == B)
1072  return A;
1073  if (A == Attribute::ReadNone)
1074  return B;
1075  if (B == Attribute::ReadNone)
1076  return A;
1077  return Attribute::None;
1078  };
1079 
1080  Attribute::AttrKind AccessAttr = Attribute::ReadNone;
1081  for (unsigned i = 0, e = ArgumentSCC.size();
1082  i != e && AccessAttr != Attribute::None; ++i) {
1083  Argument *A = ArgumentSCC[i]->Definition;
1084  Attribute::AttrKind K = determinePointerAccessAttrs(A, ArgumentSCCNodes);
1085  AccessAttr = meetAccessAttr(AccessAttr, K);
1086  }
1087 
1088  if (AccessAttr != Attribute::None) {
1089  for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) {
1090  Argument *A = ArgumentSCC[i]->Definition;
1091  if (addAccessAttr(A, AccessAttr))
1092  Changed.insert(A->getParent());
1093  }
1094  }
1095  }
1096 }
1097 
1098 /// Tests whether a function is "malloc-like".
1099 ///
1100 /// A function is "malloc-like" if it returns either null or a pointer that
1101 /// doesn't alias any other pointer visible to the caller.
1102 static bool isFunctionMallocLike(Function *F, const SCCNodeSet &SCCNodes) {
1103  SmallSetVector<Value *, 8> FlowsToReturn;
1104  for (BasicBlock &BB : *F)
1105  if (ReturnInst *Ret = dyn_cast<ReturnInst>(BB.getTerminator()))
1106  FlowsToReturn.insert(Ret->getReturnValue());
1107 
1108  for (unsigned i = 0; i != FlowsToReturn.size(); ++i) {
1109  Value *RetVal = FlowsToReturn[i];
1110 
1111  if (Constant *C = dyn_cast<Constant>(RetVal)) {
1112  if (!C->isNullValue() && !isa<UndefValue>(C))
1113  return false;
1114 
1115  continue;
1116  }
1117 
1118  if (isa<Argument>(RetVal))
1119  return false;
1120 
1121  if (Instruction *RVI = dyn_cast<Instruction>(RetVal))
1122  switch (RVI->getOpcode()) {
1123  // Extend the analysis by looking upwards.
1124  case Instruction::BitCast:
1125  case Instruction::GetElementPtr:
1126  case Instruction::AddrSpaceCast:
1127  FlowsToReturn.insert(RVI->getOperand(0));
1128  continue;
1129  case Instruction::Select: {
1130  SelectInst *SI = cast<SelectInst>(RVI);
1131  FlowsToReturn.insert(SI->getTrueValue());
1132  FlowsToReturn.insert(SI->getFalseValue());
1133  continue;
1134  }
1135  case Instruction::PHI: {
1136  PHINode *PN = cast<PHINode>(RVI);
1137  for (Value *IncValue : PN->incoming_values())
1138  FlowsToReturn.insert(IncValue);
1139  continue;
1140  }
1141 
1142  // Check whether the pointer came from an allocation.
1143  case Instruction::Alloca:
1144  break;
1145  case Instruction::Call:
1146  case Instruction::Invoke: {
1147  CallBase &CB = cast<CallBase>(*RVI);
1148  if (CB.hasRetAttr(Attribute::NoAlias))
1149  break;
1150  if (CB.getCalledFunction() && SCCNodes.count(CB.getCalledFunction()))
1151  break;
1153  }
1154  default:
1155  return false; // Did not come from an allocation.
1156  }
1157 
1158  if (PointerMayBeCaptured(RetVal, false, /*StoreCaptures=*/false))
1159  return false;
1160  }
1161 
1162  return true;
1163 }
1164 
1165 /// Deduce noalias attributes for the SCC.
1166 static void addNoAliasAttrs(const SCCNodeSet &SCCNodes,
1167  SmallSet<Function *, 8> &Changed) {
1168  // Check each function in turn, determining which functions return noalias
1169  // pointers.
1170  for (Function *F : SCCNodes) {
1171  // Already noalias.
1172  if (F->returnDoesNotAlias())
1173  continue;
1174 
1175  // We can infer and propagate function attributes only when we know that the
1176  // definition we'll get at link time is *exactly* the definition we see now.
1177  // For more details, see GlobalValue::mayBeDerefined.
1178  if (!F->hasExactDefinition())
1179  return;
1180 
1181  // We annotate noalias return values, which are only applicable to
1182  // pointer types.
1183  if (!F->getReturnType()->isPointerTy())
1184  continue;
1185 
1186  if (!isFunctionMallocLike(F, SCCNodes))
1187  return;
1188  }
1189 
1190  for (Function *F : SCCNodes) {
1191  if (F->returnDoesNotAlias() ||
1192  !F->getReturnType()->isPointerTy())
1193  continue;
1194 
1195  F->setReturnDoesNotAlias();
1196  ++NumNoAlias;
1197  Changed.insert(F);
1198  }
1199 }
1200 
1201 /// Tests whether this function is known to not return null.
1202 ///
1203 /// Requires that the function returns a pointer.
1204 ///
1205 /// Returns true if it believes the function will not return a null, and sets
1206 /// \p Speculative based on whether the returned conclusion is a speculative
1207 /// conclusion due to SCC calls.
1208 static bool isReturnNonNull(Function *F, const SCCNodeSet &SCCNodes,
1209  bool &Speculative) {
1210  assert(F->getReturnType()->isPointerTy() &&
1211  "nonnull only meaningful on pointer types");
1212  Speculative = false;
1213 
1214  SmallSetVector<Value *, 8> FlowsToReturn;
1215  for (BasicBlock &BB : *F)
1216  if (auto *Ret = dyn_cast<ReturnInst>(BB.getTerminator()))
1217  FlowsToReturn.insert(Ret->getReturnValue());
1218 
1219  auto &DL = F->getParent()->getDataLayout();
1220 
1221  for (unsigned i = 0; i != FlowsToReturn.size(); ++i) {
1222  Value *RetVal = FlowsToReturn[i];
1223 
1224  // If this value is locally known to be non-null, we're good
1225  if (isKnownNonZero(RetVal, DL))
1226  continue;
1227 
1228  // Otherwise, we need to look upwards since we can't make any local
1229  // conclusions.
1230  Instruction *RVI = dyn_cast<Instruction>(RetVal);
1231  if (!RVI)
1232  return false;
1233  switch (RVI->getOpcode()) {
1234  // Extend the analysis by looking upwards.
1235  case Instruction::BitCast:
1236  case Instruction::GetElementPtr:
1237  case Instruction::AddrSpaceCast:
1238  FlowsToReturn.insert(RVI->getOperand(0));
1239  continue;
1240  case Instruction::Select: {
1241  SelectInst *SI = cast<SelectInst>(RVI);
1242  FlowsToReturn.insert(SI->getTrueValue());
1243  FlowsToReturn.insert(SI->getFalseValue());
1244  continue;
1245  }
1246  case Instruction::PHI: {
1247  PHINode *PN = cast<PHINode>(RVI);
1248  for (int i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
1249  FlowsToReturn.insert(PN->getIncomingValue(i));
1250  continue;
1251  }
1252  case Instruction::Call:
1253  case Instruction::Invoke: {
1254  CallBase &CB = cast<CallBase>(*RVI);
1256  // A call to a node within the SCC is assumed to return null until
1257  // proven otherwise
1258  if (Callee && SCCNodes.count(Callee)) {
1259  Speculative = true;
1260  continue;
1261  }
1262  return false;
1263  }
1264  default:
1265  return false; // Unknown source, may be null
1266  };
1267  llvm_unreachable("should have either continued or returned");
1268  }
1269 
1270  return true;
1271 }
1272 
1273 /// Deduce nonnull attributes for the SCC.
1274 static void addNonNullAttrs(const SCCNodeSet &SCCNodes,
1275  SmallSet<Function *, 8> &Changed) {
1276  // Speculative that all functions in the SCC return only nonnull
1277  // pointers. We may refute this as we analyze functions.
1278  bool SCCReturnsNonNull = true;
1279 
1280  // Check each function in turn, determining which functions return nonnull
1281  // pointers.
1282  for (Function *F : SCCNodes) {
1283  // Already nonnull.
1284  if (F->getAttributes().hasRetAttr(Attribute::NonNull))
1285  continue;
1286 
1287  // We can infer and propagate function attributes only when we know that the
1288  // definition we'll get at link time is *exactly* the definition we see now.
1289  // For more details, see GlobalValue::mayBeDerefined.
1290  if (!F->hasExactDefinition())
1291  return;
1292 
1293  // We annotate nonnull return values, which are only applicable to
1294  // pointer types.
1295  if (!F->getReturnType()->isPointerTy())
1296  continue;
1297 
1298  bool Speculative = false;
1299  if (isReturnNonNull(F, SCCNodes, Speculative)) {
1300  if (!Speculative) {
1301  // Mark the function eagerly since we may discover a function
1302  // which prevents us from speculating about the entire SCC
1303  LLVM_DEBUG(dbgs() << "Eagerly marking " << F->getName()
1304  << " as nonnull\n");
1305  F->addRetAttr(Attribute::NonNull);
1306  ++NumNonNullReturn;
1307  Changed.insert(F);
1308  }
1309  continue;
1310  }
1311  // At least one function returns something which could be null, can't
1312  // speculate any more.
1313  SCCReturnsNonNull = false;
1314  }
1315 
1316  if (SCCReturnsNonNull) {
1317  for (Function *F : SCCNodes) {
1318  if (F->getAttributes().hasRetAttr(Attribute::NonNull) ||
1319  !F->getReturnType()->isPointerTy())
1320  continue;
1321 
1322  LLVM_DEBUG(dbgs() << "SCC marking " << F->getName() << " as nonnull\n");
1323  F->addRetAttr(Attribute::NonNull);
1324  ++NumNonNullReturn;
1325  Changed.insert(F);
1326  }
1327  }
1328 }
1329 
1330 namespace {
1331 
1332 /// Collects a set of attribute inference requests and performs them all in one
1333 /// go on a single SCC Node. Inference involves scanning function bodies
1334 /// looking for instructions that violate attribute assumptions.
1335 /// As soon as all the bodies are fine we are free to set the attribute.
1336 /// Customization of inference for individual attributes is performed by
1337 /// providing a handful of predicates for each attribute.
1338 class AttributeInferer {
1339 public:
1340  /// Describes a request for inference of a single attribute.
1341  struct InferenceDescriptor {
1342 
1343  /// Returns true if this function does not have to be handled.
1344  /// General intent for this predicate is to provide an optimization
1345  /// for functions that do not need this attribute inference at all
1346  /// (say, for functions that already have the attribute).
1347  std::function<bool(const Function &)> SkipFunction;
1348 
1349  /// Returns true if this instruction violates attribute assumptions.
1350  std::function<bool(Instruction &)> InstrBreaksAttribute;
1351 
1352  /// Sets the inferred attribute for this function.
1353  std::function<void(Function &)> SetAttribute;
1354 
1355  /// Attribute we derive.
1356  Attribute::AttrKind AKind;
1357 
1358  /// If true, only "exact" definitions can be used to infer this attribute.
1359  /// See GlobalValue::isDefinitionExact.
1360  bool RequiresExactDefinition;
1361 
1362  InferenceDescriptor(Attribute::AttrKind AK,
1363  std::function<bool(const Function &)> SkipFunc,
1364  std::function<bool(Instruction &)> InstrScan,
1365  std::function<void(Function &)> SetAttr,
1366  bool ReqExactDef)
1367  : SkipFunction(SkipFunc), InstrBreaksAttribute(InstrScan),
1368  SetAttribute(SetAttr), AKind(AK),
1369  RequiresExactDefinition(ReqExactDef) {}
1370  };
1371 
1372 private:
1373  SmallVector<InferenceDescriptor, 4> InferenceDescriptors;
1374 
1375 public:
1376  void registerAttrInference(InferenceDescriptor AttrInference) {
1377  InferenceDescriptors.push_back(AttrInference);
1378  }
1379 
1380  void run(const SCCNodeSet &SCCNodes, SmallSet<Function *, 8> &Changed);
1381 };
1382 
1383 /// Perform all the requested attribute inference actions according to the
1384 /// attribute predicates stored before.
1385 void AttributeInferer::run(const SCCNodeSet &SCCNodes,
1386  SmallSet<Function *, 8> &Changed) {
1387  SmallVector<InferenceDescriptor, 4> InferInSCC = InferenceDescriptors;
1388  // Go through all the functions in SCC and check corresponding attribute
1389  // assumptions for each of them. Attributes that are invalid for this SCC
1390  // will be removed from InferInSCC.
1391  for (Function *F : SCCNodes) {
1392 
1393  // No attributes whose assumptions are still valid - done.
1394  if (InferInSCC.empty())
1395  return;
1396 
1397  // Check if our attributes ever need scanning/can be scanned.
1398  llvm::erase_if(InferInSCC, [F](const InferenceDescriptor &ID) {
1399  if (ID.SkipFunction(*F))
1400  return false;
1401 
1402  // Remove from further inference (invalidate) when visiting a function
1403  // that has no instructions to scan/has an unsuitable definition.
1404  return F->isDeclaration() ||
1405  (ID.RequiresExactDefinition && !F->hasExactDefinition());
1406  });
1407 
1408  // For each attribute still in InferInSCC that doesn't explicitly skip F,
1409  // set up the F instructions scan to verify assumptions of the attribute.
1410  SmallVector<InferenceDescriptor, 4> InferInThisFunc;
1411  llvm::copy_if(
1412  InferInSCC, std::back_inserter(InferInThisFunc),
1413  [F](const InferenceDescriptor &ID) { return !ID.SkipFunction(*F); });
1414 
1415  if (InferInThisFunc.empty())
1416  continue;
1417 
1418  // Start instruction scan.
1419  for (Instruction &I : instructions(*F)) {
1420  llvm::erase_if(InferInThisFunc, [&](const InferenceDescriptor &ID) {
1421  if (!ID.InstrBreaksAttribute(I))
1422  return false;
1423  // Remove attribute from further inference on any other functions
1424  // because attribute assumptions have just been violated.
1425  llvm::erase_if(InferInSCC, [&ID](const InferenceDescriptor &D) {
1426  return D.AKind == ID.AKind;
1427  });
1428  // Remove attribute from the rest of current instruction scan.
1429  return true;
1430  });
1431 
1432  if (InferInThisFunc.empty())
1433  break;
1434  }
1435  }
1436 
1437  if (InferInSCC.empty())
1438  return;
1439 
1440  for (Function *F : SCCNodes)
1441  // At this point InferInSCC contains only functions that were either:
1442  // - explicitly skipped from scan/inference, or
1443  // - verified to have no instructions that break attribute assumptions.
1444  // Hence we just go and force the attribute for all non-skipped functions.
1445  for (auto &ID : InferInSCC) {
1446  if (ID.SkipFunction(*F))
1447  continue;
1448  Changed.insert(F);
1449  ID.SetAttribute(*F);
1450  }
1451 }
1452 
1453 struct SCCNodesResult {
1454  SCCNodeSet SCCNodes;
1455  bool HasUnknownCall;
1456 };
1457 
1458 } // end anonymous namespace
1459 
1460 /// Helper for non-Convergent inference predicate InstrBreaksAttribute.
1462  const SCCNodeSet &SCCNodes) {
1463  const CallBase *CB = dyn_cast<CallBase>(&I);
1464  // Breaks non-convergent assumption if CS is a convergent call to a function
1465  // not in the SCC.
1466  return CB && CB->isConvergent() &&
1467  !SCCNodes.contains(CB->getCalledFunction());
1468 }
1469 
1470 /// Helper for NoUnwind inference predicate InstrBreaksAttribute.
1471 static bool InstrBreaksNonThrowing(Instruction &I, const SCCNodeSet &SCCNodes) {
1472  if (!I.mayThrow())
1473  return false;
1474  if (const auto *CI = dyn_cast<CallInst>(&I)) {
1475  if (Function *Callee = CI->getCalledFunction()) {
1476  // I is a may-throw call to a function inside our SCC. This doesn't
1477  // invalidate our current working assumption that the SCC is no-throw; we
1478  // just have to scan that other function.
1479  if (SCCNodes.contains(Callee))
1480  return false;
1481  }
1482  }
1483  return true;
1484 }
1485 
1486 /// Helper for NoFree inference predicate InstrBreaksAttribute.
1487 static bool InstrBreaksNoFree(Instruction &I, const SCCNodeSet &SCCNodes) {
1488  CallBase *CB = dyn_cast<CallBase>(&I);
1489  if (!CB)
1490  return false;
1491 
1492  if (CB->hasFnAttr(Attribute::NoFree))
1493  return false;
1494 
1495  // Speculatively assume in SCC.
1496  if (Function *Callee = CB->getCalledFunction())
1497  if (SCCNodes.contains(Callee))
1498  return false;
1499 
1500  return true;
1501 }
1502 
1503 /// Attempt to remove convergent function attribute when possible.
1504 ///
1505 /// Returns true if any changes to function attributes were made.
1506 static void inferConvergent(const SCCNodeSet &SCCNodes,
1507  SmallSet<Function *, 8> &Changed) {
1508  AttributeInferer AI;
1509 
1510  // Request to remove the convergent attribute from all functions in the SCC
1511  // if every callsite within the SCC is not convergent (except for calls
1512  // to functions within the SCC).
1513  // Note: Removal of the attr from the callsites will happen in
1514  // InstCombineCalls separately.
1515  AI.registerAttrInference(AttributeInferer::InferenceDescriptor{
1517  // Skip non-convergent functions.
1518  [](const Function &F) { return !F.isConvergent(); },
1519  // Instructions that break non-convergent assumption.
1520  [SCCNodes](Instruction &I) {
1521  return InstrBreaksNonConvergent(I, SCCNodes);
1522  },
1523  [](Function &F) {
1524  LLVM_DEBUG(dbgs() << "Removing convergent attr from fn " << F.getName()
1525  << "\n");
1526  F.setNotConvergent();
1527  },
1528  /* RequiresExactDefinition= */ false});
1529  // Perform all the requested attribute inference actions.
1530  AI.run(SCCNodes, Changed);
1531 }
1532 
1533 /// Infer attributes from all functions in the SCC by scanning every
1534 /// instruction for compliance to the attribute assumptions. Currently it
1535 /// does:
1536 /// - addition of NoUnwind attribute
1537 ///
1538 /// Returns true if any changes to function attributes were made.
1539 static void inferAttrsFromFunctionBodies(const SCCNodeSet &SCCNodes,
1540  SmallSet<Function *, 8> &Changed) {
1541  AttributeInferer AI;
1542 
1544  // Request to infer nounwind attribute for all the functions in the SCC if
1545  // every callsite within the SCC is not throwing (except for calls to
1546  // functions within the SCC). Note that nounwind attribute suffers from
1547  // derefinement - results may change depending on how functions are
1548  // optimized. Thus it can be inferred only from exact definitions.
1549  AI.registerAttrInference(AttributeInferer::InferenceDescriptor{
1550  Attribute::NoUnwind,
1551  // Skip non-throwing functions.
1552  [](const Function &F) { return F.doesNotThrow(); },
1553  // Instructions that break non-throwing assumption.
1554  [&SCCNodes](Instruction &I) {
1555  return InstrBreaksNonThrowing(I, SCCNodes);
1556  },
1557  [](Function &F) {
1558  LLVM_DEBUG(dbgs()
1559  << "Adding nounwind attr to fn " << F.getName() << "\n");
1560  F.setDoesNotThrow();
1561  ++NumNoUnwind;
1562  },
1563  /* RequiresExactDefinition= */ true});
1564 
1566  // Request to infer nofree attribute for all the functions in the SCC if
1567  // every callsite within the SCC does not directly or indirectly free
1568  // memory (except for calls to functions within the SCC). Note that nofree
1569  // attribute suffers from derefinement - results may change depending on
1570  // how functions are optimized. Thus it can be inferred only from exact
1571  // definitions.
1572  AI.registerAttrInference(AttributeInferer::InferenceDescriptor{
1573  Attribute::NoFree,
1574  // Skip functions known not to free memory.
1575  [](const Function &F) { return F.doesNotFreeMemory(); },
1576  // Instructions that break non-deallocating assumption.
1577  [&SCCNodes](Instruction &I) {
1578  return InstrBreaksNoFree(I, SCCNodes);
1579  },
1580  [](Function &F) {
1581  LLVM_DEBUG(dbgs()
1582  << "Adding nofree attr to fn " << F.getName() << "\n");
1583  F.setDoesNotFreeMemory();
1584  ++NumNoFree;
1585  },
1586  /* RequiresExactDefinition= */ true});
1587 
1588  // Perform all the requested attribute inference actions.
1589  AI.run(SCCNodes, Changed);
1590 }
1591 
1592 static void addNoRecurseAttrs(const SCCNodeSet &SCCNodes,
1593  SmallSet<Function *, 8> &Changed) {
1594  // Try and identify functions that do not recurse.
1595 
1596  // If the SCC contains multiple nodes we know for sure there is recursion.
1597  if (SCCNodes.size() != 1)
1598  return;
1599 
1600  Function *F = *SCCNodes.begin();
1601  if (!F || !F->hasExactDefinition() || F->doesNotRecurse())
1602  return;
1603 
1604  // If all of the calls in F are identifiable and are to norecurse functions, F
1605  // is norecurse. This check also detects self-recursion as F is not currently
1606  // marked norecurse, so any called from F to F will not be marked norecurse.
1607  for (auto &BB : *F)
1608  for (auto &I : BB.instructionsWithoutDebug())
1609  if (auto *CB = dyn_cast<CallBase>(&I)) {
1611  if (!Callee || Callee == F || !Callee->doesNotRecurse())
1612  // Function calls a potentially recursive function.
1613  return;
1614  }
1615 
1616  // Every call was to a non-recursive function other than this function, and
1617  // we have no indirect recursion as the SCC size is one. This function cannot
1618  // recurse.
1619  F->setDoesNotRecurse();
1620  ++NumNoRecurse;
1621  Changed.insert(F);
1622 }
1623 
1625  if (auto *CB = dyn_cast<CallBase>(&I))
1626  return CB->hasFnAttr(Attribute::NoReturn);
1627  return false;
1628 }
1629 
1630 // A basic block can only return if it terminates with a ReturnInst and does not
1631 // contain calls to noreturn functions.
1633  if (!isa<ReturnInst>(BB.getTerminator()))
1634  return false;
1636 }
1637 
1638 // FIXME: this doesn't handle recursion.
1639 static bool canReturn(Function &F) {
1642 
1643  Visited.insert(&F.front());
1644  Worklist.push_back(&F.front());
1645 
1646  do {
1647  BasicBlock *BB = Worklist.pop_back_val();
1648  if (basicBlockCanReturn(*BB))
1649  return true;
1650  for (BasicBlock *Succ : successors(BB))
1651  if (Visited.insert(Succ).second)
1652  Worklist.push_back(Succ);
1653  } while (!Worklist.empty());
1654 
1655  return false;
1656 }
1657 
1658 // Set the noreturn function attribute if possible.
1659 static void addNoReturnAttrs(const SCCNodeSet &SCCNodes,
1660  SmallSet<Function *, 8> &Changed) {
1661  for (Function *F : SCCNodes) {
1662  if (!F || !F->hasExactDefinition() || F->hasFnAttribute(Attribute::Naked) ||
1663  F->doesNotReturn())
1664  continue;
1665 
1666  if (!canReturn(*F)) {
1667  F->setDoesNotReturn();
1668  Changed.insert(F);
1669  }
1670  }
1671 }
1672 
1673 static bool functionWillReturn(const Function &F) {
1674  // We can infer and propagate function attributes only when we know that the
1675  // definition we'll get at link time is *exactly* the definition we see now.
1676  // For more details, see GlobalValue::mayBeDerefined.
1677  if (!F.hasExactDefinition())
1678  return false;
1679 
1680  // Must-progress function without side-effects must return.
1681  if (F.mustProgress() && F.onlyReadsMemory())
1682  return true;
1683 
1684  // Can only analyze functions with a definition.
1685  if (F.isDeclaration())
1686  return false;
1687 
1688  // Functions with loops require more sophisticated analysis, as the loop
1689  // may be infinite. For now, don't try to handle them.
1691  FindFunctionBackedges(F, Backedges);
1692  if (!Backedges.empty())
1693  return false;
1694 
1695  // If there are no loops, then the function is willreturn if all calls in
1696  // it are willreturn.
1697  return all_of(instructions(F), [](const Instruction &I) {
1698  return I.willReturn();
1699  });
1700 }
1701 
1702 // Set the willreturn function attribute if possible.
1703 static void addWillReturn(const SCCNodeSet &SCCNodes,
1704  SmallSet<Function *, 8> &Changed) {
1705  for (Function *F : SCCNodes) {
1706  if (!F || F->willReturn() || !functionWillReturn(*F))
1707  continue;
1708 
1709  F->setWillReturn();
1710  NumWillReturn++;
1711  Changed.insert(F);
1712  }
1713 }
1714 
1715 // Return true if this is an atomic which has an ordering stronger than
1716 // unordered. Note that this is different than the predicate we use in
1717 // Attributor. Here we chose to be conservative and consider monotonic
1718 // operations potentially synchronizing. We generally don't do much with
1719 // monotonic operations, so this is simply risk reduction.
1721  if (!I->isAtomic())
1722  return false;
1723 
1724  if (auto *FI = dyn_cast<FenceInst>(I))
1725  // All legal orderings for fence are stronger than monotonic.
1726  return FI->getSyncScopeID() != SyncScope::SingleThread;
1727  else if (isa<AtomicCmpXchgInst>(I) || isa<AtomicRMWInst>(I))
1728  return true;
1729  else if (auto *SI = dyn_cast<StoreInst>(I))
1730  return !SI->isUnordered();
1731  else if (auto *LI = dyn_cast<LoadInst>(I))
1732  return !LI->isUnordered();
1733  else {
1734  llvm_unreachable("unknown atomic instruction?");
1735  }
1736 }
1737 
1738 static bool InstrBreaksNoSync(Instruction &I, const SCCNodeSet &SCCNodes) {
1739  // Volatile may synchronize
1740  if (I.isVolatile())
1741  return true;
1742 
1743  // An ordered atomic may synchronize. (See comment about on monotonic.)
1744  if (isOrderedAtomic(&I))
1745  return true;
1746 
1747  auto *CB = dyn_cast<CallBase>(&I);
1748  if (!CB)
1749  // Non call site cases covered by the two checks above
1750  return false;
1751 
1752  if (CB->hasFnAttr(Attribute::NoSync))
1753  return false;
1754 
1755  // Non volatile memset/memcpy/memmoves are nosync
1756  // NOTE: Only intrinsics with volatile flags should be handled here. All
1757  // others should be marked in Intrinsics.td.
1758  if (auto *MI = dyn_cast<MemIntrinsic>(&I))
1759  if (!MI->isVolatile())
1760  return false;
1761 
1762  // Speculatively assume in SCC.
1763  if (Function *Callee = CB->getCalledFunction())
1764  if (SCCNodes.contains(Callee))
1765  return false;
1766 
1767  return true;
1768 }
1769 
1770 // Infer the nosync attribute.
1771 static void addNoSyncAttr(const SCCNodeSet &SCCNodes,
1772  SmallSet<Function *, 8> &Changed) {
1773  AttributeInferer AI;
1774  AI.registerAttrInference(AttributeInferer::InferenceDescriptor{
1775  Attribute::NoSync,
1776  // Skip already marked functions.
1777  [](const Function &F) { return F.hasNoSync(); },
1778  // Instructions that break nosync assumption.
1779  [&SCCNodes](Instruction &I) {
1780  return InstrBreaksNoSync(I, SCCNodes);
1781  },
1782  [](Function &F) {
1783  LLVM_DEBUG(dbgs()
1784  << "Adding nosync attr to fn " << F.getName() << "\n");
1785  F.setNoSync();
1786  ++NumNoSync;
1787  },
1788  /* RequiresExactDefinition= */ true});
1789  AI.run(SCCNodes, Changed);
1790 }
1791 
1792 static SCCNodesResult createSCCNodeSet(ArrayRef<Function *> Functions) {
1793  SCCNodesResult Res;
1794  Res.HasUnknownCall = false;
1795  for (Function *F : Functions) {
1796  if (!F || F->hasOptNone() || F->hasFnAttribute(Attribute::Naked) ||
1797  F->isPresplitCoroutine()) {
1798  // Treat any function we're trying not to optimize as if it were an
1799  // indirect call and omit it from the node set used below.
1800  Res.HasUnknownCall = true;
1801  continue;
1802  }
1803  // Track whether any functions in this SCC have an unknown call edge.
1804  // Note: if this is ever a performance hit, we can common it with
1805  // subsequent routines which also do scans over the instructions of the
1806  // function.
1807  if (!Res.HasUnknownCall) {
1808  for (Instruction &I : instructions(*F)) {
1809  if (auto *CB = dyn_cast<CallBase>(&I)) {
1810  if (!CB->getCalledFunction()) {
1811  Res.HasUnknownCall = true;
1812  break;
1813  }
1814  }
1815  }
1816  }
1817  Res.SCCNodes.insert(F);
1818  }
1819  return Res;
1820 }
1821 
1822 template <typename AARGetterT>
1824 deriveAttrsInPostOrder(ArrayRef<Function *> Functions, AARGetterT &&AARGetter) {
1825  SCCNodesResult Nodes = createSCCNodeSet(Functions);
1826 
1827  // Bail if the SCC only contains optnone functions.
1828  if (Nodes.SCCNodes.empty())
1829  return {};
1830 
1831  SmallSet<Function *, 8> Changed;
1832 
1833  addArgumentReturnedAttrs(Nodes.SCCNodes, Changed);
1834  addMemoryAttrs(Nodes.SCCNodes, AARGetter, Changed);
1835  addArgumentAttrs(Nodes.SCCNodes, Changed);
1836  inferConvergent(Nodes.SCCNodes, Changed);
1837  addNoReturnAttrs(Nodes.SCCNodes, Changed);
1838  addWillReturn(Nodes.SCCNodes, Changed);
1839 
1840  // If we have no external nodes participating in the SCC, we can deduce some
1841  // more precise attributes as well.
1842  if (!Nodes.HasUnknownCall) {
1843  addNoAliasAttrs(Nodes.SCCNodes, Changed);
1844  addNonNullAttrs(Nodes.SCCNodes, Changed);
1845  inferAttrsFromFunctionBodies(Nodes.SCCNodes, Changed);
1846  addNoRecurseAttrs(Nodes.SCCNodes, Changed);
1847  }
1848 
1849  addNoSyncAttr(Nodes.SCCNodes, Changed);
1850 
1851  // Finally, infer the maximal set of attributes from the ones we've inferred
1852  // above. This is handling the cases where one attribute on a signature
1853  // implies another, but for implementation reasons the inference rule for
1854  // the later is missing (or simply less sophisticated).
1855  for (Function *F : Nodes.SCCNodes)
1856  if (F)
1858  Changed.insert(F);
1859 
1860  return Changed;
1861 }
1862 
1865  LazyCallGraph &CG,
1866  CGSCCUpdateResult &) {
1868  AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C, CG).getManager();
1869 
1870  // We pass a lambda into functions to wire them up to the analysis manager
1871  // for getting function analyses.
1872  auto AARGetter = [&](Function &F) -> AAResults & {
1873  return FAM.getResult<AAManager>(F);
1874  };
1875 
1876  SmallVector<Function *, 8> Functions;
1877  for (LazyCallGraph::Node &N : C) {
1878  Functions.push_back(&N.getFunction());
1879  }
1880 
1881  auto ChangedFunctions = deriveAttrsInPostOrder(Functions, AARGetter);
1882  if (ChangedFunctions.empty())
1883  return PreservedAnalyses::all();
1884 
1885  // Invalidate analyses for modified functions so that we don't have to
1886  // invalidate all analyses for all functions in this SCC.
1887  PreservedAnalyses FuncPA;
1888  // We haven't changed the CFG for modified functions.
1889  FuncPA.preserveSet<CFGAnalyses>();
1890  for (Function *Changed : ChangedFunctions) {
1891  FAM.invalidate(*Changed, FuncPA);
1892  // Also invalidate any direct callers of changed functions since analyses
1893  // may care about attributes of direct callees. For example, MemorySSA cares
1894  // about whether or not a call's callee modifies memory and queries that
1895  // through function attributes.
1896  for (auto *U : Changed->users()) {
1897  if (auto *Call = dyn_cast<CallBase>(U)) {
1898  if (Call->getCalledFunction() == Changed)
1899  FAM.invalidate(*Call->getFunction(), FuncPA);
1900  }
1901  }
1902  }
1903 
1904  PreservedAnalyses PA;
1905  // We have not added or removed functions.
1907  // We already invalidated all relevant function analyses above.
1909  return PA;
1910 }
1911 
1912 namespace {
1913 
1914 struct PostOrderFunctionAttrsLegacyPass : public CallGraphSCCPass {
1915  // Pass identification, replacement for typeid
1916  static char ID;
1917 
1918  PostOrderFunctionAttrsLegacyPass() : CallGraphSCCPass(ID) {
1921  }
1922 
1923  bool runOnSCC(CallGraphSCC &SCC) override;
1924 
1925  void getAnalysisUsage(AnalysisUsage &AU) const override {
1926  AU.setPreservesCFG();
1930  }
1931 };
1932 
1933 } // end anonymous namespace
1934 
1936 INITIALIZE_PASS_BEGIN(PostOrderFunctionAttrsLegacyPass, "function-attrs",
1937  "Deduce function attributes", false, false)
1941 INITIALIZE_PASS_END(PostOrderFunctionAttrsLegacyPass, "function-attrs",
1943 
1945  return new PostOrderFunctionAttrsLegacyPass();
1946 }
1947 
1948 template <typename AARGetterT>
1949 static bool runImpl(CallGraphSCC &SCC, AARGetterT AARGetter) {
1950  SmallVector<Function *, 8> Functions;
1951  for (CallGraphNode *I : SCC) {
1952  Functions.push_back(I->getFunction());
1953  }
1954 
1955  return !deriveAttrsInPostOrder(Functions, AARGetter).empty();
1956 }
1957 
1958 bool PostOrderFunctionAttrsLegacyPass::runOnSCC(CallGraphSCC &SCC) {
1959  if (skipSCC(SCC))
1960  return false;
1961  return runImpl(SCC, LegacyAARGetter(*this));
1962 }
1963 
1964 namespace {
1965 
1966 struct ReversePostOrderFunctionAttrsLegacyPass : public ModulePass {
1967  // Pass identification, replacement for typeid
1968  static char ID;
1969 
1970  ReversePostOrderFunctionAttrsLegacyPass() : ModulePass(ID) {
1973  }
1974 
1975  bool runOnModule(Module &M) override;
1976 
1977  void getAnalysisUsage(AnalysisUsage &AU) const override {
1978  AU.setPreservesCFG();
1981  }
1982 };
1983 
1984 } // end anonymous namespace
1985 
1987 
1988 INITIALIZE_PASS_BEGIN(ReversePostOrderFunctionAttrsLegacyPass,
1989  "rpo-function-attrs", "Deduce function attributes in RPO",
1990  false, false)
1992 INITIALIZE_PASS_END(ReversePostOrderFunctionAttrsLegacyPass,
1994  false, false)
1995 
1997  return new ReversePostOrderFunctionAttrsLegacyPass();
1998 }
1999 
2001  // We check the preconditions for the function prior to calling this to avoid
2002  // the cost of building up a reversible post-order list. We assert them here
2003  // to make sure none of the invariants this relies on were violated.
2004  assert(!F.isDeclaration() && "Cannot deduce norecurse without a definition!");
2005  assert(!F.doesNotRecurse() &&
2006  "This function has already been deduced as norecurs!");
2007  assert(F.hasInternalLinkage() &&
2008  "Can only do top-down deduction for internal linkage functions!");
2009 
2010  // If F is internal and all of its uses are calls from a non-recursive
2011  // functions, then none of its calls could in fact recurse without going
2012  // through a function marked norecurse, and so we can mark this function too
2013  // as norecurse. Note that the uses must actually be calls -- otherwise
2014  // a pointer to this function could be returned from a norecurse function but
2015  // this function could be recursively (indirectly) called. Note that this
2016  // also detects if F is directly recursive as F is not yet marked as
2017  // a norecurse function.
2018  for (auto &U : F.uses()) {
2019  auto *I = dyn_cast<Instruction>(U.getUser());
2020  if (!I)
2021  return false;
2022  CallBase *CB = dyn_cast<CallBase>(I);
2023  if (!CB || !CB->isCallee(&U) ||
2024  !CB->getParent()->getParent()->doesNotRecurse())
2025  return false;
2026  }
2027  F.setDoesNotRecurse();
2028  ++NumNoRecurse;
2029  return true;
2030 }
2031 
2033  // We only have a post-order SCC traversal (because SCCs are inherently
2034  // discovered in post-order), so we accumulate them in a vector and then walk
2035  // it in reverse. This is simpler than using the RPO iterator infrastructure
2036  // because we need to combine SCC detection and the PO walk of the call
2037  // graph. We can also cheat egregiously because we're primarily interested in
2038  // synthesizing norecurse and so we can only save the singular SCCs as SCCs
2039  // with multiple functions in them will clearly be recursive.
2040  SmallVector<Function *, 16> Worklist;
2041  for (scc_iterator<CallGraph *> I = scc_begin(&CG); !I.isAtEnd(); ++I) {
2042  if (I->size() != 1)
2043  continue;
2044 
2045  Function *F = I->front()->getFunction();
2046  if (F && !F->isDeclaration() && !F->doesNotRecurse() &&
2047  F->hasInternalLinkage())
2048  Worklist.push_back(F);
2049  }
2050 
2051  bool Changed = false;
2052  for (auto *F : llvm::reverse(Worklist))
2053  Changed |= addNoRecurseAttrsTopDown(*F);
2054 
2055  return Changed;
2056 }
2057 
2058 bool ReversePostOrderFunctionAttrsLegacyPass::runOnModule(Module &M) {
2059  if (skipModule(M))
2060  return false;
2061 
2062  auto &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph();
2063 
2064  return deduceFunctionAttributeInRPO(M, CG);
2065 }
2066 
2069  auto &CG = AM.getResult<CallGraphAnalysis>(M);
2070 
2071  if (!deduceFunctionAttributeInRPO(M, CG))
2072  return PreservedAnalyses::all();
2073 
2074  PreservedAnalyses PA;
2076  return PA;
2077 }
i
i
Definition: README.txt:29
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
llvm::Argument
This class represents an incoming formal argument to a Function.
Definition: Argument.h:28
AssumptionCache.h
llvm::AAManager
A manager for alias analyses.
Definition: AliasAnalysis.h:1303
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:104
llvm::MemoryLocation::get
static MemoryLocation get(const LoadInst *LI)
Return a location with information about the memory reference by the given instruction.
Definition: MemoryLocation.cpp:35
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
llvm::none_of
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1631
llvm::ReturnInst
Return a value (possibly void), from a function.
Definition: Instructions.h:3004
llvm::VAArgInst
This class represents the va_arg llvm instruction, which returns an argument of the specified type gi...
Definition: Instructions.h:1819
llvm::PHINode::incoming_values
op_range incoming_values()
Definition: Instructions.h:2737
llvm::CallGraphAnalysis
An analysis pass to compute the CallGraph for a Module.
Definition: CallGraph.h:304
Metadata.h
llvm::FindFunctionBackedges
void FindFunctionBackedges(const Function &F, SmallVectorImpl< std::pair< const BasicBlock *, const BasicBlock * > > &Result)
Analyze the specified function to find all of the loop backedges in the function and return them.
Definition: CFG.cpp:34
llvm::ModulePass
ModulePass class - This class is used to implement unstructured interprocedural optimizations and ana...
Definition: Pass.h:248
llvm::BasicBlock::getParent
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:104
IntrinsicInst.h
SCCIterator.h
llvm::AnalysisManager::getResult
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:780
llvm::MemoryLocation::Ptr
const Value * Ptr
The address of the start of the location.
Definition: MemoryLocation.h:218
InstIterator.h
llvm::FunctionSummary::calls
ArrayRef< EdgeTy > calls() const
Return the list of <CalleeValueInfo, CalleeInfo> pairs.
Definition: ModuleSummaryIndex.h:758
llvm::FunctionSummary::fflags
FFlags fflags() const
Get function summary flags.
Definition: ModuleSummaryIndex.h:742
llvm::Function
Definition: Function.h:60
llvm::AnalysisManager::invalidate
void invalidate(IRUnitT &IR, const PreservedAnalyses &PA)
Invalidate cached analyses for an IR unit.
Definition: PassManagerImpl.h:89
Pass.h
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(PostOrderFunctionAttrsLegacyPass, "function-attrs", "Deduce function attributes", false, false) INITIALIZE_PASS_END(PostOrderFunctionAttrsLegacyPass
llvm::CaptureTracker
This callback is used in conjunction with PointerMayBeCaptured.
Definition: CaptureTracking.h:92
llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::size
size_type size() const
Determine the number of elements in the SetVector.
Definition: SetVector.h:77
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1185
Statistic.h
CaptureTracking.h
llvm::GlobalValue::isLocalLinkage
static bool isLocalLinkage(LinkageTypes Linkage)
Definition: GlobalValue.h:374
ErrorHandling.h
addNoSyncAttr
static void addNoSyncAttr(const SCCNodeSet &SCCNodes, SmallSet< Function *, 8 > &Changed)
Definition: FunctionAttrs.cpp:1771
llvm::AllAnalysesOn
This templated class represents "all analyses that operate over <a particular IR unit>" (e....
Definition: PassManager.h:90
llvm::erase_if
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
Definition: STLExtras.h:1807
llvm::createModRefInfo
LLVM_NODISCARD ModRefInfo createModRefInfo(const FunctionModRefBehavior FMRB)
Definition: AliasAnalysis.h:377
RPO
rpo function Deduce function attributes in RPO
Definition: FunctionAttrs.cpp:1993
ValueTracking.h
Local.h
canReturn
static bool canReturn(Function &F)
Definition: FunctionAttrs.cpp:1639
llvm::CallGraph
The basic data container for the call graph of a Module of IR.
Definition: CallGraph.h:72
FAM
FunctionAnalysisManager FAM
Definition: PassBuilderBindings.cpp:59
llvm::CallBase::hasFnAttr
bool hasFnAttr(Attribute::AttrKind Kind) const
Determine whether this call has the given attribute.
Definition: InstrTypes.h:1483
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:139
llvm::AAResults::onlyAccessesArgPointees
static bool onlyAccessesArgPointees(FunctionModRefBehavior MRB)
Checks if functions with the specified behavior are known to read and write at most from objects poin...
Definition: AliasAnalysis.h:692
llvm::isKnownNonZero
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.
Definition: ValueTracking.cpp:340
DenseMap.h
llvm::reverse
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
Definition: STLExtras.h:380
llvm::AttributeMask
Definition: Attributes.h:963
llvm::sys::path::end
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:235
instructionDoesNotReturn
static bool instructionDoesNotReturn(Instruction &I)
Definition: FunctionAttrs.cpp:1624
llvm::sys::path::begin
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:226
llvm::CallBase::isCallee
bool isCallee(Value::const_user_iterator UI) const
Determine whether the passed iterator points to the callee operand's Use.
Definition: InstrTypes.h:1407
llvm::SmallSet
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:136
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::count
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
Definition: DenseMap.h:147
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
llvm::GraphTraits< ArgumentGraphNode * >::NodeRef
ArgumentGraphNode * NodeRef
Definition: FunctionAttrs.cpp:643
llvm::MCID::Convergent
@ Convergent
Definition: MCInstrDesc.h:184
llvm::successors
auto successors(MachineBasicBlock *BB)
Definition: MachineSSAContext.h:29
llvm::MipsISD::Ret
@ Ret
Definition: MipsISelLowering.h:119
STLExtras.h
isReturnNonNull
static bool isReturnNonNull(Function *F, const SCCNodeSet &SCCNodes, bool &Speculative)
Tests whether this function is known to not return null.
Definition: FunctionAttrs.cpp:1208
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:654
llvm::FunctionSummary::FFlags::NoRecurse
unsigned NoRecurse
Definition: ModuleSummaryIndex.h:567
DisableNoUnwindInference
static cl::opt< bool > DisableNoUnwindInference("disable-nounwind-inference", cl::Hidden, cl::desc("Stop inferring nounwind attribute during function-attrs pass"))
llvm::GlobalValue::isLinkOnceODRLinkage
static bool isLinkOnceODRLinkage(LinkageTypes Linkage)
Definition: GlobalValue.h:350
createSCCNodeSet
static SCCNodesResult createSCCNodeSet(ArrayRef< Function * > Functions)
Definition: FunctionAttrs.cpp:1792
llvm::GraphTraits< ArgumentGraphNode * >::child_end
static ChildIteratorType child_end(NodeRef N)
Definition: FunctionAttrs.cpp:648
BasicAliasAnalysis.h
llvm::FMRL_Anywhere
@ FMRL_Anywhere
Access to any memory.
Definition: AliasAnalysis.h:254
addArgumentReturnedAttrs
static void addArgumentReturnedAttrs(const SCCNodeSet &SCCNodes, SmallSet< Function *, 8 > &Changed)
Deduce returned attributes for the SCC.
Definition: FunctionAttrs.cpp:799
Use.h
ModuleSummaryIndex.h
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
runImpl
static bool runImpl(CallGraphSCC &SCC, AARGetterT AARGetter)
Definition: FunctionAttrs.cpp:1949
llvm::getAAResultsAnalysisUsage
void getAAResultsAnalysisUsage(AnalysisUsage &AU)
A helper for the legacy pass manager to populate AU to add uses to make sure the analyses required by...
Definition: AliasAnalysis.cpp:1035
addAccessAttr
static bool addAccessAttr(Argument *A, Attribute::AttrKind R)
Definition: FunctionAttrs.cpp:888
attrs
function attrs
Definition: FunctionAttrs.cpp:1941
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::RISCVFenceField::R
@ R
Definition: RISCVBaseInfo.h:241
Uses
SmallPtrSet< MachineInstr *, 2 > Uses
Definition: ARMLowOverheadLoops.cpp:585
isFunctionMallocLike
static bool isFunctionMallocLike(Function *F, const SCCNodeSet &SCCNodes)
Tests whether a function is "malloc-like".
Definition: FunctionAttrs.cpp:1102
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
Arg
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
Definition: AMDGPULibCalls.cpp:186
Instruction.h
CommandLine.h
llvm::SPII::Load
@ Load
Definition: SparcInstrInfo.h:32
llvm::GlobalValueSummary
Function and variable summary information to aid decisions and implementation of importing.
Definition: ModuleSummaryIndex.h:289
llvm::Instruction::getOpcode
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:157
llvm::all_of
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1617
functionWillReturn
static bool functionWillReturn(const Function &F)
Definition: FunctionAttrs.cpp:1673
llvm::CallGraphSCC
CallGraphSCC - This is a single SCC that a CallGraphSCCPass is run on.
Definition: CallGraphSCCPass.h:87
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
llvm::LazyCallGraph::SCC
An SCC of the call graph.
Definition: LazyCallGraph.h:419
llvm::ModRefInfo::Ref
@ Ref
The access may reference the value stored in memory.
Constants.h
llvm::GlobalValue::isLinkOnceAnyLinkage
static bool isLinkOnceAnyLinkage(LinkageTypes Linkage)
Definition: GlobalValue.h:347
llvm::PHINode::getIncomingValue
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
Definition: Instructions.h:2747
llvm::AAResults
Definition: AliasAnalysis.h:511
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
InstrBreaksNonThrowing
static bool InstrBreaksNonThrowing(Instruction &I, const SCCNodeSet &SCCNodes)
Helper for NoUnwind inference predicate InstrBreaksAttribute.
Definition: FunctionAttrs.cpp:1471
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::ARM_PROC::A
@ A
Definition: ARMBaseInfo.h:34
InstrTypes.h
llvm::CallBase::getCalledFunction
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation or the function signa...
Definition: InstrTypes.h:1396
deriveAttrsInPostOrder
static SmallSet< Function *, 8 > deriveAttrsInPostOrder(ArrayRef< Function * > Functions, AARGetterT &&AARGetter)
Definition: FunctionAttrs.cpp:1824
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
addNoRecurseAttrsTopDown
static bool addNoRecurseAttrsTopDown(Function &F)
Definition: FunctionAttrs.cpp:2000
DisableThinLTOPropagation
static cl::opt< bool > DisableThinLTOPropagation("disable-thinlto-funcattrs", cl::init(true), cl::Hidden, cl::desc("Don't propagate function-attrs in thinLTO"))
false
Definition: StackSlotColoring.cpp:141
llvm::CallBase::isConvergent
bool isConvergent() const
Determine if the invoke is convergent.
Definition: InstrTypes.h:1911
llvm::dwarf::Index
Index
Definition: Dwarf.h:472
EnableNonnullArgPropagation
static cl::opt< bool > EnableNonnullArgPropagation("enable-nonnull-arg-prop", cl::init(true), cl::Hidden, cl::desc("Try to propagate nonnull argument attributes from callsites to " "caller functions."))
llvm::inferAttributesFromOthers
bool inferAttributesFromOthers(Function &F)
If we can infer one attribute from another on the declaration of a function, explicitly materialize t...
Definition: Local.cpp:3374
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::GlobalValue::isWeakODRLinkage
static bool isWeakODRLinkage(LinkageTypes Linkage)
Definition: GlobalValue.h:359
llvm::FMRL_ArgumentPointees
@ FMRL_ArgumentPointees
Access to memory via argument pointers.
Definition: AliasAnalysis.h:250
in
The object format emitted by the WebAssembly backed is documented in
Definition: README.txt:11
llvm::Instruction
Definition: Instruction.h:42
addNoAliasAttrs
static void addNoAliasAttrs(const SCCNodeSet &SCCNodes, SmallSet< Function *, 8 > &Changed)
Deduce noalias attributes for the SCC.
Definition: FunctionAttrs.cpp:1166
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
addArgumentAttrsFromCallsites
static bool addArgumentAttrsFromCallsites(Function &F)
If a callsite has arguments that are also arguments to the parent function, try to propagate attribut...
Definition: FunctionAttrs.cpp:849
addArgumentAttrs
static void addArgumentAttrs(const SCCNodeSet &SCCNodes, SmallSet< Function *, 8 > &Changed)
Deduce nocapture attributes for the SCC.
Definition: FunctionAttrs.cpp:914
llvm::Use::getUser
User * getUser() const
Returns the User that contains this Use.
Definition: Use.h:72
llvm::getUnderlyingObject
const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=6)
This method strips off any GEP address adjustments and pointer casts from the specified value,...
Definition: ValueTracking.cpp:4450
SmallPtrSet.h
llvm::CallGraphNode
A node in the call graph for a module.
Definition: CallGraph.h:166
llvm::GraphTraits< ArgumentGraph * >::nodes_end
static ChildIteratorType nodes_end(ArgumentGraph *AG)
Definition: FunctionAttrs.cpp:659
LazyCallGraph.h
inferAttrsFromFunctionBodies
static void inferAttrsFromFunctionBodies(const SCCNodeSet &SCCNodes, SmallSet< Function *, 8 > &Changed)
Infer attributes from all functions in the SCC by scanning every instruction for compliance to the at...
Definition: FunctionAttrs.cpp:1539
DisableNoFreeInference
static cl::opt< bool > DisableNoFreeInference("disable-nofree-inference", cl::Hidden, cl::desc("Stop inferring nofree attribute during function-attrs pass"))
llvm::MCID::Call
@ Call
Definition: MCInstrDesc.h:155
llvm::isModSet
LLVM_NODISCARD bool isModSet(const ModRefInfo MRI)
Definition: AliasAnalysis.h:196
llvm::SPII::Store
@ Store
Definition: SparcInstrInfo.h:33
llvm::PHINode::getNumIncomingValues
unsigned getNumIncomingValues() const
Return the number of incoming edges.
Definition: Instructions.h:2743
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
llvm::CallBase::onlyReadsMemory
bool onlyReadsMemory(unsigned OpNo) const
Definition: InstrTypes.h:1720
Type.h
llvm::ValueInfo
Struct that holds a reference to a particular GUID in a global value summary.
Definition: ModuleSummaryIndex.h:167
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
llvm::dxil::PointerTypeAnalysis::run
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
Definition: PointerTypeAnalysis.cpp:101
llvm::scc_begin
scc_iterator< T > scc_begin(const T &G)
Construct the begin iterator for a deduced graph type T.
Definition: SCCIterator.h:232
llvm::function_ref
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLFunctionalExtras.h:36
addWillReturn
static void addWillReturn(const SCCNodeSet &SCCNodes, SmallSet< Function *, 8 > &Changed)
Definition: FunctionAttrs.cpp:1703
addNoReturnAttrs
static void addNoReturnAttrs(const SCCNodeSet &SCCNodes, SmallSet< Function *, 8 > &Changed)
Definition: FunctionAttrs.cpp:1659
BasicBlock.h
llvm::cl::opt< bool >
llvm::instructions
inst_range instructions(Function *F)
Definition: InstIterator.h:133
llvm::StoreInst
An instruction for storing to memory.
Definition: Instructions.h:297
llvm::isNoModRef
LLVM_NODISCARD bool isNoModRef(const ModRefInfo MRI)
Definition: AliasAnalysis.h:185
VI
@ VI
Definition: SIInstrInfo.cpp:7845
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
llvm::CallBase::doesNotAccessMemory
bool doesNotAccessMemory(unsigned OpNo) const
Definition: InstrTypes.h:1714
llvm::CallGraphSCCPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &Info) const override
getAnalysisUsage - For this class, we declare that we require and preserve the call graph.
Definition: CallGraphSCCPass.cpp:658
uint64_t
D
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
llvm::Attribute::None
@ None
No attributes have been set.
Definition: Attributes.h:86
llvm::createReversePostOrderFunctionAttrsPass
Pass * createReversePostOrderFunctionAttrsPass()
createReversePostOrderFunctionAttrsPass - This pass walks SCCs of the call graph in RPO to deduce and...
Definition: FunctionAttrs.cpp:1996
llvm::scc_iterator
Enumerate the SCCs of a directed graph in reverse topological order of the SCC DAG.
Definition: SCCIterator.h:46
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::PreservedAnalyses::preserve
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:173
IPO.h
addNonNullAttrs
static void addNonNullAttrs(const SCCNodeSet &SCCNodes, SmallSet< Function *, 8 > &Changed)
Deduce nonnull attributes for the SCC.
Definition: FunctionAttrs.cpp:1274
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
MemoryLocation.h
llvm::DenseMap
Definition: DenseMap.h:716
CGSCCPassManager.h
llvm::CallGraphWrapperPass
The ModulePass which wraps up a CallGraph and the logic to build it.
Definition: CallGraph.h:336
llvm::ReversePostOrderFunctionAttrsPass::run
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)
Definition: FunctionAttrs.cpp:2068
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::Attribute::AttrKind
AttrKind
This enumeration lists the attributes that can be associated with parameters, function results,...
Definition: Attributes.h:84
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
ArrayRef.h
llvm::CallBase::doesNotCapture
bool doesNotCapture(unsigned OpNo) const
Determine whether this data operand is not captured.
Definition: InstrTypes.h:1673
llvm::createPostOrderFunctionAttrsLegacyPass
Pass * createPostOrderFunctionAttrsLegacyPass()
Create a legacy pass manager instance of a pass to compute function attrs in post-order.
Definition: FunctionAttrs.cpp:1944
llvm::ModRefInfo
ModRefInfo
Flags indicating whether a memory access modifies or references memory.
Definition: AliasAnalysis.h:148
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::X86AS::FS
@ FS
Definition: X86.h:192
llvm::GlobalValue::isExternalLinkage
static bool isExternalLinkage(LinkageTypes Linkage)
Definition: GlobalValue.h:341
llvm::CallBase::hasOperandBundles
bool hasOperandBundles() const
Return true if this User has any operand bundles.
Definition: InstrTypes.h:1945
InstrBreaksNonConvergent
static bool InstrBreaksNonConvergent(Instruction &I, const SCCNodeSet &SCCNodes)
Helper for non-Convergent inference predicate InstrBreaksAttribute.
Definition: FunctionAttrs.cpp:1461
SI
StandardInstrumentations SI(Debug, VerifyEach)
determinePointerAccessAttrs
static Attribute::AttrKind determinePointerAccessAttrs(Argument *A, const SmallPtrSet< Argument *, 8 > &SCCNodes)
Returns Attribute::None, Attribute::ReadOnly or Attribute::ReadNone.
Definition: FunctionAttrs.cpp:666
llvm::SelectInst
This class represents the LLVM 'select' instruction.
Definition: Instructions.h:1724
function
print Print MemDeps of function
Definition: MemDepPrinter.cpp:82
llvm::GlobalValue::isAvailableExternallyLinkage
static bool isAvailableExternallyLinkage(LinkageTypes Linkage)
Definition: GlobalValue.h:344
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
llvm::Function::doesNotRecurse
bool doesNotRecurse() const
Determine if the function is known not to recurse, directly or indirectly.
Definition: Function.h:607
llvm::FMRB_DoesNotAccessMemory
@ FMRB_DoesNotAccessMemory
This function does not perform any non-local loads or stores to memory.
Definition: AliasAnalysis.h:268
llvm::FunctionSummary::FFlags
Flags specific to function summaries.
Definition: ModuleSummaryIndex.h:562
llvm::LazyCallGraph::Node
A node in the call graph.
Definition: LazyCallGraph.h:315
llvm::SmallPtrSetImpl::count
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:383
llvm::computeFunctionBodyMemoryAccess
FunctionModRefBehavior computeFunctionBodyMemoryAccess(Function &F, AAResults &AAR)
Returns the memory access properties of this copy of the function.
Definition: FunctionAttrs.cpp:256
llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::insert
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:141
checkFunctionMemoryAccess
static FunctionModRefBehavior 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...
Definition: FunctionAttrs.cpp:126
llvm::AMDGPU::CPol::SCC
@ SCC
Definition: SIDefines.h:307
CFG.h
llvm::initializeReversePostOrderFunctionAttrsLegacyPassPass
void initializeReversePostOrderFunctionAttrsLegacyPassPass(PassRegistry &)
calculatePrevailingSummary
static FunctionSummary * calculatePrevailingSummary(ValueInfo VI, DenseMap< ValueInfo, FunctionSummary * > &CachedPrevailingSummary, function_ref< bool(GlobalValue::GUID, const GlobalValueSummary *)> IsPrevailing)
Definition: FunctionAttrs.cpp:355
llvm::AssumptionCacheTracker
An immutable pass that tracks lazily created AssumptionCache objects.
Definition: AssumptionCache.h:202
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::PointerMayBeCaptured
bool PointerMayBeCaptured(const Value *V, bool ReturnCaptures, bool StoreCaptures, unsigned MaxUsesToExplore=0)
PointerMayBeCaptured - Return true if this pointer value may be captured by the enclosing function (w...
Definition: CaptureTracking.cpp:229
llvm::any_of
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:1624
llvm::GraphTraits< ArgumentGraph * >::getEntryNode
static NodeRef getEntryNode(ArgumentGraph *AG)
Definition: FunctionAttrs.cpp:653
llvm::initializePostOrderFunctionAttrsLegacyPassPass
void initializePostOrderFunctionAttrsLegacyPassPass(PassRegistry &)
llvm::AnalysisUsage::setPreservesCFG
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:263
basicBlockCanReturn
static bool basicBlockCanReturn(BasicBlock &BB)
Definition: FunctionAttrs.cpp:1632
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:143
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
llvm::CFGAnalyses
Represents analyses that only rely on functions' control flow.
Definition: PassManager.h:113
llvm::AnalysisUsage::addPreserved
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
Definition: PassAnalysisSupport.h:98
A
* A
Definition: README_ALTIVEC.txt:89
Compiler.h
llvm::ModRefInfo::Mod
@ Mod
The access may modify the value stored in memory.
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
llvm::FunctionModRefBehavior
FunctionModRefBehavior
Summary of how a function affects memory in the program.
Definition: AliasAnalysis.h:262
llvm::GraphTraits< ArgumentGraphNode * >::ChildIteratorType
SmallVectorImpl< ArgumentGraphNode * >::iterator ChildIteratorType
Definition: FunctionAttrs.cpp:644
llvm::SmallSet::insert
std::pair< NoneType, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
Definition: SmallSet.h:182
llvm::CallBase::hasRetAttr
bool hasRetAttr(Attribute::AttrKind Kind) const
Determine whether the return value has the given attribute.
Definition: InstrTypes.h:1595
CallGraphSCCPass.h
llvm::CallBase::dataOperandHasImpliedAttr
bool dataOperandHasImpliedAttr(unsigned i, Attribute::AttrKind Kind) const
Return true if the data operand at index i has the attribute A.
Definition: InstrTypes.h:1653
LLVM_FALLTHROUGH
#define LLVM_FALLTHROUGH
LLVM_FALLTHROUGH - Mark fallthrough cases in switch statements.
Definition: Compiler.h:280
llvm::LoadInst
An instruction for reading from memory.
Definition: Instructions.h:173
llvm::AAResults::getModRefBehavior
FunctionModRefBehavior getModRefBehavior(const CallBase *Call)
Return the behavior of the given call site.
Definition: AliasAnalysis.cpp:422
MRI
unsigned const MachineRegisterInfo * MRI
Definition: AArch64AdvSIMDScalarPass.cpp:105
Argument.h
llvm::GraphTraits< ArgumentGraphNode * >
Definition: FunctionAttrs.cpp:642
Callee
amdgpu Simplify well known AMD library false FunctionCallee Callee
Definition: AMDGPULibCalls.cpp:186
llvm::MCID::Select
@ Select
Definition: MCInstrDesc.h:164
Attributes.h
Constant.h
llvm::CGSCCUpdateResult
Support structure for SCC passes to communicate updates the call graph back to the CGSCC pass manager...
Definition: CGSCCPassManager.h:232
llvm::FunctionSummary
Function summary information to aid decisions and implementation of importing.
Definition: ModuleSummaryIndex.h:512
llvm::CallBase::getDataOperandNo
unsigned getDataOperandNo(Value::const_user_iterator UI) const
Given a value use iterator, return the data operand corresponding to it.
Definition: InstrTypes.h:1304
llvm::copy_if
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:1663
llvm::CallBase::isArgOperand
bool isArgOperand(const Use *U) const
Definition: InstrTypes.h:1361
llvm::PostOrderFunctionAttrsPass::run
PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, LazyCallGraph &CG, CGSCCUpdateResult &UR)
Definition: FunctionAttrs.cpp:1863
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
llvm::CallBase::arg_size
unsigned arg_size() const
Definition: InstrTypes.h:1339
llvm::thinLTOPropagateFunctionAttrs
bool thinLTOPropagateFunctionAttrs(ModuleSummaryIndex &Index, function_ref< bool(GlobalValue::GUID, const GlobalValueSummary *)> isPrevailing)
Propagate function attributes for function summaries along the index's callgraph during thinlink.
Definition: FunctionAttrs.cpp:458
llvm::isGuaranteedToTransferExecutionToSuccessor
bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)
Return true if this function can prove that the instruction I will always transfer execution to one o...
Definition: ValueTracking.cpp:5430
Casting.h
Function.h
llvm::CallGraphSCCPass
Definition: CallGraphSCCPass.h:34
addNoRecurseAttrs
static void addNoRecurseAttrs(const SCCNodeSet &SCCNodes, SmallSet< Function *, 8 > &Changed)
Definition: FunctionAttrs.cpp:1592
PassManager.h
inferConvergent
static void inferConvergent(const SCCNodeSet &SCCNodes, SmallSet< Function *, 8 > &Changed)
Attempt to remove convergent function attribute when possible.
Definition: FunctionAttrs.cpp:1506
llvm::FunctionSummary::FFlags::MayThrow
unsigned MayThrow
Definition: ModuleSummaryIndex.h:578
InstrBreaksNoSync
static bool InstrBreaksNoSync(Instruction &I, const SCCNodeSet &SCCNodes)
Definition: FunctionAttrs.cpp:1738
llvm::AAResults::pointsToConstantMemory
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 ...
Definition: AliasAnalysis.cpp:162
addMemoryAttrs
static void addMemoryAttrs(const SCCNodeSet &SCCNodes, AARGetterT &&AARGetter, SmallSet< Function *, 8 > &Changed)
Deduce readonly/readnone/writeonly attributes for the SCC.
Definition: FunctionAttrs.cpp:263
InstrBreaksNoFree
static bool InstrBreaksNoFree(Instruction &I, const SCCNodeSet &SCCNodes)
Helper for NoFree inference predicate InstrBreaksAttribute.
Definition: FunctionAttrs.cpp:1487
CallGraph.h
llvm::GraphTraits< ArgumentGraphNode * >::getEntryNode
static NodeRef getEntryNode(NodeRef A)
Definition: FunctionAttrs.cpp:646
llvm::Pass
Pass interface - Implemented by all 'passes'.
Definition: Pass.h:91
Instructions.h
llvm::PreservedAnalyses::preserveSet
void preserveSet()
Mark an analysis set as preserved.
Definition: PassManager.h:188
llvm::GraphTraits< ArgumentGraph * >::nodes_begin
static ChildIteratorType nodes_begin(ArgumentGraph *AG)
Definition: FunctionAttrs.cpp:655
SmallVector.h
User.h
llvm::ModuleSummaryIndex
Class to hold module path string table and global value map, and encapsulate methods for operating on...
Definition: ModuleSummaryIndex.h:1087
llvm::isRefSet
LLVM_NODISCARD bool isRefSet(const ModRefInfo MRI)
Definition: AliasAnalysis.h:199
llvm::SmallVectorImpl::iterator
typename SuperClass::iterator iterator
Definition: SmallVector.h:558
llvm::CallBase::getArgOperand
Value * getArgOperand(unsigned i) const
Definition: InstrTypes.h:1341
N
#define N
attributes
function Deduce function attributes
Definition: FunctionAttrs.cpp:1942
llvm::AAResultsWrapperPass
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
Definition: AliasAnalysis.h:1351
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:91
llvm::PHINode
Definition: Instructions.h:2651
llvm::GlobalValue::isWeakAnyLinkage
static bool isWeakAnyLinkage(LinkageTypes Linkage)
Definition: GlobalValue.h:356
llvm::MemoryLocation::getBeforeOrAfter
static MemoryLocation getBeforeOrAfter(const Value *Ptr, const AAMDNodes &AATags=AAMDNodes())
Return a location that may access any location before or after Ptr, while remaining within the underl...
Definition: MemoryLocation.h:278
llvm::CallBase
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1174
llvm::SmallSetVector
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:307
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::FunctionSummary::FFlags::NoUnwind
unsigned NoUnwind
Definition: ModuleSummaryIndex.h:576
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
llvm::GraphTraits
Definition: GraphTraits.h:37
llvm::User::getOperand
Value * getOperand(unsigned i) const
Definition: User.h:169
llvm::cl::desc
Definition: CommandLine.h:405
llvm::AttributeMask::addAttribute
AttributeMask & addAttribute(Attribute::AttrKind Val)
Add an attribute to the mask.
Definition: Attributes.h:978
llvm::LazyCallGraph
A lazily constructed view of the call graph of a module.
Definition: LazyCallGraph.h:110
isOrderedAtomic
static bool isOrderedAtomic(Instruction *I)
Definition: FunctionAttrs.cpp:1720
raw_ostream.h
llvm::FunctionAnalysisManagerCGSCCProxy
A proxy from a FunctionAnalysisManager to an SCC.
Definition: CGSCCPassManager.h:392
Value.h
deduceFunctionAttributeInRPO
static bool deduceFunctionAttributeInRPO(Module &M, CallGraph &CG)
Definition: FunctionAttrs.cpp:2032
llvm::LegacyAARGetter
This class is a functor to be used in legacy module or SCC passes for computing AA results for a func...
Definition: BasicAliasAnalysis.h:200
InitializePasses.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
FunctionAttrs.h
Debug.h
llvm::GraphTraits< ArgumentGraphNode * >::child_begin
static ChildIteratorType child_begin(NodeRef N)
Definition: FunctionAttrs.cpp:647
llvm::MemoryLocation
Representation for a specific memory location.
Definition: MemoryLocation.h:210
SetVector.h
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
llvm::SyncScope::SingleThread
@ SingleThread
Synchronized with respect to signal handlers executing in the same thread.
Definition: LLVMContext.h:55
SmallSet.h
llvm::SmallPtrSetImpl::insert
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:365
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38