LLVM  13.0.0git
Attributor.cpp
Go to the documentation of this file.
1 //===- Attributor.cpp - Module-wide attribute deduction -------------------===//
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 // This file implements an interprocedural pass that deduces and/or propagates
10 // attributes. This is done in an abstract interpretation style fixpoint
11 // iteration. See the Attributor.h file comment and the class descriptions in
12 // that file for more information.
13 //
14 //===----------------------------------------------------------------------===//
15 
17 
18 #include "llvm/ADT/GraphTraits.h"
20 #include "llvm/ADT/Statistic.h"
21 #include "llvm/ADT/TinyPtrVector.h"
27 #include "llvm/IR/Attributes.h"
28 #include "llvm/IR/GlobalValue.h"
29 #include "llvm/IR/IRBuilder.h"
30 #include "llvm/IR/NoFolder.h"
31 #include "llvm/IR/Verifier.h"
32 #include "llvm/InitializePasses.h"
33 #include "llvm/Support/Casting.h"
35 #include "llvm/Support/Debug.h"
43 
44 #include <cassert>
45 #include <string>
46 
47 using namespace llvm;
48 
49 #define DEBUG_TYPE "attributor"
50 
51 DEBUG_COUNTER(ManifestDBGCounter, "attributor-manifest",
52  "Determine what attributes are manifested in the IR");
53 
54 STATISTIC(NumFnDeleted, "Number of function deleted");
55 STATISTIC(NumFnWithExactDefinition,
56  "Number of functions with exact definitions");
57 STATISTIC(NumFnWithoutExactDefinition,
58  "Number of functions without exact definitions");
59 STATISTIC(NumFnShallowWrappersCreated, "Number of shallow wrappers created");
60 STATISTIC(NumAttributesTimedOut,
61  "Number of abstract attributes timed out before fixpoint");
62 STATISTIC(NumAttributesValidFixpoint,
63  "Number of abstract attributes in a valid fixpoint state");
64 STATISTIC(NumAttributesManifested,
65  "Number of abstract attributes manifested in IR");
66 STATISTIC(NumAttributesFixedDueToRequiredDependences,
67  "Number of abstract attributes fixed due to required dependences");
68 
69 // TODO: Determine a good default value.
70 //
71 // In the LLVM-TS and SPEC2006, 32 seems to not induce compile time overheads
72 // (when run with the first 5 abstract attributes). The results also indicate
73 // that we never reach 32 iterations but always find a fixpoint sooner.
74 //
75 // This will become more evolved once we perform two interleaved fixpoint
76 // iterations: bottom-up and top-down.
77 static cl::opt<unsigned>
78  MaxFixpointIterations("attributor-max-iterations", cl::Hidden,
79  cl::desc("Maximal number of fixpoint iterations."),
80  cl::init(32));
81 
83  "attributor-max-initialization-chain-length", cl::Hidden,
84  cl::desc(
85  "Maximal number of chained initializations (to avoid stack overflows)"),
88 
90  "attributor-max-iterations-verify", cl::Hidden,
91  cl::desc("Verify that max-iterations is a tight bound for a fixpoint"),
92  cl::init(false));
93 
95  "attributor-annotate-decl-cs", cl::Hidden,
96  cl::desc("Annotate call sites of function declarations."), cl::init(false));
97 
98 static cl::opt<bool> EnableHeapToStack("enable-heap-to-stack-conversion",
99  cl::init(true), cl::Hidden);
100 
101 static cl::opt<bool>
102  AllowShallowWrappers("attributor-allow-shallow-wrappers", cl::Hidden,
103  cl::desc("Allow the Attributor to create shallow "
104  "wrappers for non-exact definitions."),
105  cl::init(false));
106 
107 static cl::opt<bool>
108  AllowDeepWrapper("attributor-allow-deep-wrappers", cl::Hidden,
109  cl::desc("Allow the Attributor to use IP information "
110  "derived from non-exact functions via cloning"),
111  cl::init(false));
112 
113 // These options can only used for debug builds.
114 #ifndef NDEBUG
116  SeedAllowList("attributor-seed-allow-list", cl::Hidden,
117  cl::desc("Comma seperated list of attribute names that are "
118  "allowed to be seeded."),
120 
122  "attributor-function-seed-allow-list", cl::Hidden,
123  cl::desc("Comma seperated list of function names that are "
124  "allowed to be seeded."),
126 #endif
127 
128 static cl::opt<bool>
129  DumpDepGraph("attributor-dump-dep-graph", cl::Hidden,
130  cl::desc("Dump the dependency graph to dot files."),
131  cl::init(false));
132 
134  "attributor-depgraph-dot-filename-prefix", cl::Hidden,
135  cl::desc("The prefix used for the CallGraph dot file names."));
136 
137 static cl::opt<bool> ViewDepGraph("attributor-view-dep-graph", cl::Hidden,
138  cl::desc("View the dependency graph."),
139  cl::init(false));
140 
141 static cl::opt<bool> PrintDependencies("attributor-print-dep", cl::Hidden,
142  cl::desc("Print attribute dependencies"),
143  cl::init(false));
144 
146  "attributor-enable-call-site-specific-deduction", cl::Hidden,
147  cl::desc("Allow the Attributor to do call site specific analysis"),
148  cl::init(false));
149 
150 /// Logic operators for the change status enum class.
151 ///
152 ///{
154  return L == ChangeStatus::CHANGED ? L : R;
155 }
157  return L == ChangeStatus::UNCHANGED ? L : R;
158 }
159 ///}
160 
161 /// Return true if \p New is equal or worse than \p Old.
162 static bool isEqualOrWorse(const Attribute &New, const Attribute &Old) {
163  if (!Old.isIntAttribute())
164  return true;
165 
166  return Old.getValueAsInt() >= New.getValueAsInt();
167 }
168 
169 /// Return true if the information provided by \p Attr was added to the
170 /// attribute list \p Attrs. This is only the case if it was not already present
171 /// in \p Attrs at the position describe by \p PK and \p AttrIdx.
172 static bool addIfNotExistent(LLVMContext &Ctx, const Attribute &Attr,
173  AttributeList &Attrs, int AttrIdx) {
174 
175  if (Attr.isEnumAttribute()) {
177  if (Attrs.hasAttribute(AttrIdx, Kind))
178  if (isEqualOrWorse(Attr, Attrs.getAttribute(AttrIdx, Kind)))
179  return false;
180  Attrs = Attrs.addAttribute(Ctx, AttrIdx, Attr);
181  return true;
182  }
183  if (Attr.isStringAttribute()) {
184  StringRef Kind = Attr.getKindAsString();
185  if (Attrs.hasAttribute(AttrIdx, Kind))
186  if (isEqualOrWorse(Attr, Attrs.getAttribute(AttrIdx, Kind)))
187  return false;
188  Attrs = Attrs.addAttribute(Ctx, AttrIdx, Attr);
189  return true;
190  }
191  if (Attr.isIntAttribute()) {
193  if (Attrs.hasAttribute(AttrIdx, Kind))
194  if (isEqualOrWorse(Attr, Attrs.getAttribute(AttrIdx, Kind)))
195  return false;
196  Attrs = Attrs.removeAttribute(Ctx, AttrIdx, Kind);
197  Attrs = Attrs.addAttribute(Ctx, AttrIdx, Attr);
198  return true;
199  }
200 
201  llvm_unreachable("Expected enum or string attribute!");
202 }
203 
205  if (getPositionKind() == IRP_ARGUMENT)
206  return cast<Argument>(&getAnchorValue());
207 
208  // Not an Argument and no argument number means this is not a call site
209  // argument, thus we cannot find a callback argument to return.
210  int ArgNo = getCallSiteArgNo();
211  if (ArgNo < 0)
212  return nullptr;
213 
214  // Use abstract call sites to make the connection between the call site
215  // values and the ones in callbacks. If a callback was found that makes use
216  // of the underlying call site operand, we want the corresponding callback
217  // callee argument and not the direct callee argument.
218  Optional<Argument *> CBCandidateArg;
219  SmallVector<const Use *, 4> CallbackUses;
220  const auto &CB = cast<CallBase>(getAnchorValue());
221  AbstractCallSite::getCallbackUses(CB, CallbackUses);
222  for (const Use *U : CallbackUses) {
223  AbstractCallSite ACS(U);
224  assert(ACS && ACS.isCallbackCall());
225  if (!ACS.getCalledFunction())
226  continue;
227 
228  for (unsigned u = 0, e = ACS.getNumArgOperands(); u < e; u++) {
229 
230  // Test if the underlying call site operand is argument number u of the
231  // callback callee.
232  if (ACS.getCallArgOperandNo(u) != ArgNo)
233  continue;
234 
235  assert(ACS.getCalledFunction()->arg_size() > u &&
236  "ACS mapped into var-args arguments!");
237  if (CBCandidateArg.hasValue()) {
238  CBCandidateArg = nullptr;
239  break;
240  }
241  CBCandidateArg = ACS.getCalledFunction()->getArg(u);
242  }
243  }
244 
245  // If we found a unique callback candidate argument, return it.
246  if (CBCandidateArg.hasValue() && CBCandidateArg.getValue())
247  return CBCandidateArg.getValue();
248 
249  // If no callbacks were found, or none used the underlying call site operand
250  // exclusively, use the direct callee argument if available.
251  const Function *Callee = CB.getCalledFunction();
252  if (Callee && Callee->arg_size() > unsigned(ArgNo))
253  return Callee->getArg(ArgNo);
254 
255  return nullptr;
256 }
257 
260  if (getState().isAtFixpoint())
261  return HasChanged;
262 
263  LLVM_DEBUG(dbgs() << "[Attributor] Update: " << *this << "\n");
264 
265  HasChanged = updateImpl(A);
266 
267  LLVM_DEBUG(dbgs() << "[Attributor] Update " << HasChanged << " " << *this
268  << "\n");
269 
270  return HasChanged;
271 }
272 
275  const ArrayRef<Attribute> &DeducedAttrs) {
276  Function *ScopeFn = IRP.getAnchorScope();
278 
279  // In the following some generic code that will manifest attributes in
280  // DeducedAttrs if they improve the current IR. Due to the different
281  // annotation positions we use the underlying AttributeList interface.
282 
284  switch (PK) {
291  Attrs = ScopeFn->getAttributes();
292  break;
296  Attrs = cast<CallBase>(IRP.getAnchorValue()).getAttributes();
297  break;
298  }
299 
301  LLVMContext &Ctx = IRP.getAnchorValue().getContext();
302  for (const Attribute &Attr : DeducedAttrs) {
303  if (!addIfNotExistent(Ctx, Attr, Attrs, IRP.getAttrIdx()))
304  continue;
305 
306  HasChanged = ChangeStatus::CHANGED;
307  }
308 
309  if (HasChanged == ChangeStatus::UNCHANGED)
310  return HasChanged;
311 
312  switch (PK) {
316  ScopeFn->setAttributes(Attrs);
317  break;
321  cast<CallBase>(IRP.getAnchorValue()).setAttributes(Attrs);
322  break;
325  break;
326  }
327 
328  return HasChanged;
329 }
330 
332 const IRPosition
334 
336  IRPositions.emplace_back(IRP);
337 
338  // Helper to determine if operand bundles on a call site are benin or
339  // potentially problematic. We handle only llvm.assume for now.
340  auto CanIgnoreOperandBundles = [](const CallBase &CB) {
341  return (isa<IntrinsicInst>(CB) &&
342  cast<IntrinsicInst>(CB).getIntrinsicID() == Intrinsic ::assume);
343  };
344 
345  const auto *CB = dyn_cast<CallBase>(&IRP.getAnchorValue());
346  switch (IRP.getPositionKind()) {
350  return;
353  IRPositions.emplace_back(IRPosition::function(*IRP.getAnchorScope()));
354  return;
356  assert(CB && "Expected call site!");
357  // TODO: We need to look at the operand bundles similar to the redirection
358  // in CallBase.
359  if (!CB->hasOperandBundles() || CanIgnoreOperandBundles(*CB))
360  if (const Function *Callee = CB->getCalledFunction())
361  IRPositions.emplace_back(IRPosition::function(*Callee));
362  return;
364  assert(CB && "Expected call site!");
365  // TODO: We need to look at the operand bundles similar to the redirection
366  // in CallBase.
367  if (!CB->hasOperandBundles() || CanIgnoreOperandBundles(*CB)) {
368  if (const Function *Callee = CB->getCalledFunction()) {
369  IRPositions.emplace_back(IRPosition::returned(*Callee));
370  IRPositions.emplace_back(IRPosition::function(*Callee));
371  for (const Argument &Arg : Callee->args())
372  if (Arg.hasReturnedAttr()) {
373  IRPositions.emplace_back(
374  IRPosition::callsite_argument(*CB, Arg.getArgNo()));
375  IRPositions.emplace_back(
376  IRPosition::value(*CB->getArgOperand(Arg.getArgNo())));
377  IRPositions.emplace_back(IRPosition::argument(Arg));
378  }
379  }
380  }
381  IRPositions.emplace_back(IRPosition::callsite_function(*CB));
382  return;
384  assert(CB && "Expected call site!");
385  // TODO: We need to look at the operand bundles similar to the redirection
386  // in CallBase.
387  if (!CB->hasOperandBundles() || CanIgnoreOperandBundles(*CB)) {
388  const Function *Callee = CB->getCalledFunction();
389  if (Callee) {
390  if (Argument *Arg = IRP.getAssociatedArgument())
391  IRPositions.emplace_back(IRPosition::argument(*Arg));
392  IRPositions.emplace_back(IRPosition::function(*Callee));
393  }
394  }
395  IRPositions.emplace_back(IRPosition::value(IRP.getAssociatedValue()));
396  return;
397  }
398  }
399 }
400 
402  bool IgnoreSubsumingPositions, Attributor *A) const {
404  for (const IRPosition &EquivIRP : SubsumingPositionIterator(*this)) {
405  for (Attribute::AttrKind AK : AKs)
406  if (EquivIRP.getAttrsFromIRAttr(AK, Attrs))
407  return true;
408  // The first position returned by the SubsumingPositionIterator is
409  // always the position itself. If we ignore subsuming positions we
410  // are done after the first iteration.
411  if (IgnoreSubsumingPositions)
412  break;
413  }
414  if (A)
415  for (Attribute::AttrKind AK : AKs)
416  if (getAttrsFromAssumes(AK, Attrs, *A))
417  return true;
418  return false;
419 }
420 
423  bool IgnoreSubsumingPositions, Attributor *A) const {
424  for (const IRPosition &EquivIRP : SubsumingPositionIterator(*this)) {
425  for (Attribute::AttrKind AK : AKs)
426  EquivIRP.getAttrsFromIRAttr(AK, Attrs);
427  // The first position returned by the SubsumingPositionIterator is
428  // always the position itself. If we ignore subsuming positions we
429  // are done after the first iteration.
430  if (IgnoreSubsumingPositions)
431  break;
432  }
433  if (A)
434  for (Attribute::AttrKind AK : AKs)
435  getAttrsFromAssumes(AK, Attrs, *A);
436 }
437 
438 bool IRPosition::getAttrsFromIRAttr(Attribute::AttrKind AK,
441  return false;
442 
443  AttributeList AttrList;
444  if (const auto *CB = dyn_cast<CallBase>(&getAnchorValue()))
445  AttrList = CB->getAttributes();
446  else
447  AttrList = getAssociatedFunction()->getAttributes();
448 
449  bool HasAttr = AttrList.hasAttribute(getAttrIdx(), AK);
450  if (HasAttr)
451  Attrs.push_back(AttrList.getAttribute(getAttrIdx(), AK));
452  return HasAttr;
453 }
454 
455 bool IRPosition::getAttrsFromAssumes(Attribute::AttrKind AK,
457  Attributor &A) const {
458  assert(getPositionKind() != IRP_INVALID && "Did expect a valid position!");
459  Value &AssociatedValue = getAssociatedValue();
460 
461  const Assume2KnowledgeMap &A2K =
462  A.getInfoCache().getKnowledgeMap().lookup({&AssociatedValue, AK});
463 
464  // Check if we found any potential assume use, if not we don't need to create
465  // explorer iterators.
466  if (A2K.empty())
467  return false;
468 
469  LLVMContext &Ctx = AssociatedValue.getContext();
470  unsigned AttrsSize = Attrs.size();
472  A.getInfoCache().getMustBeExecutedContextExplorer();
473  auto EIt = Explorer.begin(getCtxI()), EEnd = Explorer.end(getCtxI());
474  for (auto &It : A2K)
475  if (Explorer.findInContextOf(It.first, EIt, EEnd))
476  Attrs.push_back(Attribute::get(Ctx, AK, It.second.Max));
477  return AttrsSize != Attrs.size();
478 }
479 
480 void IRPosition::verify() {
481 #ifdef EXPENSIVE_CHECKS
482  switch (getPositionKind()) {
483  case IRP_INVALID:
484  assert((CBContext == nullptr) &&
485  "Invalid position must not have CallBaseContext!");
486  assert(!Enc.getOpaqueValue() &&
487  "Expected a nullptr for an invalid position!");
488  return;
489  case IRP_FLOAT:
490  assert((!isa<CallBase>(&getAssociatedValue()) &&
491  !isa<Argument>(&getAssociatedValue())) &&
492  "Expected specialized kind for call base and argument values!");
493  return;
494  case IRP_RETURNED:
495  assert(isa<Function>(getAsValuePtr()) &&
496  "Expected function for a 'returned' position!");
497  assert(getAsValuePtr() == &getAssociatedValue() &&
498  "Associated value mismatch!");
499  return;
501  assert((CBContext == nullptr) &&
502  "'call site returned' position must not have CallBaseContext!");
503  assert((isa<CallBase>(getAsValuePtr())) &&
504  "Expected call base for 'call site returned' position!");
505  assert(getAsValuePtr() == &getAssociatedValue() &&
506  "Associated value mismatch!");
507  return;
508  case IRP_CALL_SITE:
509  assert((CBContext == nullptr) &&
510  "'call site function' position must not have CallBaseContext!");
511  assert((isa<CallBase>(getAsValuePtr())) &&
512  "Expected call base for 'call site function' position!");
513  assert(getAsValuePtr() == &getAssociatedValue() &&
514  "Associated value mismatch!");
515  return;
516  case IRP_FUNCTION:
517  assert(isa<Function>(getAsValuePtr()) &&
518  "Expected function for a 'function' position!");
519  assert(getAsValuePtr() == &getAssociatedValue() &&
520  "Associated value mismatch!");
521  return;
522  case IRP_ARGUMENT:
523  assert(isa<Argument>(getAsValuePtr()) &&
524  "Expected argument for a 'argument' position!");
525  assert(getAsValuePtr() == &getAssociatedValue() &&
526  "Associated value mismatch!");
527  return;
528  case IRP_CALL_SITE_ARGUMENT: {
529  assert((CBContext == nullptr) &&
530  "'call site argument' position must not have CallBaseContext!");
531  Use *U = getAsUsePtr();
532  assert(U && "Expected use for a 'call site argument' position!");
533  assert(isa<CallBase>(U->getUser()) &&
534  "Expected call base user for a 'call site argument' position!");
535  assert(cast<CallBase>(U->getUser())->isArgOperand(U) &&
536  "Expected call base argument operand for a 'call site argument' "
537  "position");
538  assert(cast<CallBase>(U->getUser())->getArgOperandNo(U) ==
539  unsigned(getCallSiteArgNo()) &&
540  "Argument number mismatch!");
541  assert(U->get() == &getAssociatedValue() && "Associated value mismatch!");
542  return;
543  }
544  }
545 #endif
546 }
547 
550  bool &UsedAssumedInformation) {
551  const auto &ValueSimplifyAA =
552  getAAFor<AAValueSimplify>(AA, IRPosition::value(V), DepClassTy::NONE);
553  Optional<Value *> SimplifiedV =
554  ValueSimplifyAA.getAssumedSimplifiedValue(*this);
555  bool IsKnown = ValueSimplifyAA.isKnown();
556  UsedAssumedInformation |= !IsKnown;
557  if (!SimplifiedV.hasValue()) {
558  recordDependence(ValueSimplifyAA, AA, DepClassTy::OPTIONAL);
559  return llvm::None;
560  }
561  if (isa_and_nonnull<UndefValue>(SimplifiedV.getValue())) {
562  recordDependence(ValueSimplifyAA, AA, DepClassTy::OPTIONAL);
563  return llvm::None;
564  }
565  Constant *CI = dyn_cast_or_null<Constant>(SimplifiedV.getValue());
566  if (CI && CI->getType() != V.getType()) {
567  // TODO: Check for a save conversion.
568  return nullptr;
569  }
570  if (CI)
571  recordDependence(ValueSimplifyAA, AA, DepClassTy::OPTIONAL);
572  return CI;
573 }
574 
576  // The abstract attributes are allocated via the BumpPtrAllocator Allocator,
577  // thus we cannot delete them. We can, and want to, destruct them though.
578  for (auto &DepAA : DG.SyntheticRoot.Deps) {
579  AbstractAttribute *AA = cast<AbstractAttribute>(DepAA.getPointer());
580  AA->~AbstractAttribute();
581  }
582 }
583 
585  const AAIsDead *FnLivenessAA,
586  bool CheckBBLivenessOnly, DepClassTy DepClass) {
587  const IRPosition &IRP = AA.getIRPosition();
588  if (!Functions.count(IRP.getAnchorScope()))
589  return false;
590  return isAssumedDead(IRP, &AA, FnLivenessAA, CheckBBLivenessOnly, DepClass);
591 }
592 
594  const AbstractAttribute *QueryingAA,
595  const AAIsDead *FnLivenessAA,
596  bool CheckBBLivenessOnly, DepClassTy DepClass) {
597  Instruction *UserI = dyn_cast<Instruction>(U.getUser());
598  if (!UserI)
599  return isAssumedDead(IRPosition::value(*U.get()), QueryingAA, FnLivenessAA,
600  CheckBBLivenessOnly, DepClass);
601 
602  if (auto *CB = dyn_cast<CallBase>(UserI)) {
603  // For call site argument uses we can check if the argument is
604  // unused/dead.
605  if (CB->isArgOperand(&U)) {
606  const IRPosition &CSArgPos =
607  IRPosition::callsite_argument(*CB, CB->getArgOperandNo(&U));
608  return isAssumedDead(CSArgPos, QueryingAA, FnLivenessAA,
609  CheckBBLivenessOnly, DepClass);
610  }
611  } else if (ReturnInst *RI = dyn_cast<ReturnInst>(UserI)) {
612  const IRPosition &RetPos = IRPosition::returned(*RI->getFunction());
613  return isAssumedDead(RetPos, QueryingAA, FnLivenessAA, CheckBBLivenessOnly,
614  DepClass);
615  } else if (PHINode *PHI = dyn_cast<PHINode>(UserI)) {
616  BasicBlock *IncomingBB = PHI->getIncomingBlock(U);
617  return isAssumedDead(*IncomingBB->getTerminator(), QueryingAA, FnLivenessAA,
618  CheckBBLivenessOnly, DepClass);
619  }
620 
621  return isAssumedDead(IRPosition::value(*UserI), QueryingAA, FnLivenessAA,
622  CheckBBLivenessOnly, DepClass);
623 }
624 
626  const AbstractAttribute *QueryingAA,
627  const AAIsDead *FnLivenessAA,
628  bool CheckBBLivenessOnly, DepClassTy DepClass) {
629  if (!FnLivenessAA)
630  FnLivenessAA = lookupAAFor<AAIsDead>(IRPosition::function(*I.getFunction()),
631  QueryingAA, DepClassTy::NONE);
632 
633  // If we have a context instruction and a liveness AA we use it.
634  if (FnLivenessAA &&
635  FnLivenessAA->getIRPosition().getAnchorScope() == I.getFunction() &&
636  FnLivenessAA->isAssumedDead(&I)) {
637  if (QueryingAA)
638  recordDependence(*FnLivenessAA, *QueryingAA, DepClass);
639  return true;
640  }
641 
642  if (CheckBBLivenessOnly)
643  return false;
644 
645  const AAIsDead &IsDeadAA = getOrCreateAAFor<AAIsDead>(
646  IRPosition::value(I), QueryingAA, DepClassTy::NONE);
647  // Don't check liveness for AAIsDead.
648  if (QueryingAA == &IsDeadAA)
649  return false;
650 
651  if (IsDeadAA.isAssumedDead()) {
652  if (QueryingAA)
653  recordDependence(IsDeadAA, *QueryingAA, DepClass);
654  return true;
655  }
656 
657  return false;
658 }
659 
661  const AbstractAttribute *QueryingAA,
662  const AAIsDead *FnLivenessAA,
663  bool CheckBBLivenessOnly, DepClassTy DepClass) {
664  Instruction *CtxI = IRP.getCtxI();
665  if (CtxI &&
666  isAssumedDead(*CtxI, QueryingAA, FnLivenessAA,
667  /* CheckBBLivenessOnly */ true,
668  CheckBBLivenessOnly ? DepClass : DepClassTy::OPTIONAL))
669  return true;
670 
671  if (CheckBBLivenessOnly)
672  return false;
673 
674  // If we haven't succeeded we query the specific liveness info for the IRP.
675  const AAIsDead *IsDeadAA;
677  IsDeadAA = &getOrCreateAAFor<AAIsDead>(
678  IRPosition::callsite_returned(cast<CallBase>(IRP.getAssociatedValue())),
679  QueryingAA, DepClassTy::NONE);
680  else
681  IsDeadAA = &getOrCreateAAFor<AAIsDead>(IRP, QueryingAA, DepClassTy::NONE);
682  // Don't check liveness for AAIsDead.
683  if (QueryingAA == IsDeadAA)
684  return false;
685 
686  if (IsDeadAA->isAssumedDead()) {
687  if (QueryingAA)
688  recordDependence(*IsDeadAA, *QueryingAA, DepClass);
689  return true;
690  }
691 
692  return false;
693 }
694 
695 bool Attributor::checkForAllUses(function_ref<bool(const Use &, bool &)> Pred,
696  const AbstractAttribute &QueryingAA,
697  const Value &V, DepClassTy LivenessDepClass) {
698 
699  // Check the trivial case first as it catches void values.
700  if (V.use_empty())
701  return true;
702 
703  // If the value is replaced by another one, for now a constant, we do not have
704  // uses. Note that this requires users of `checkForAllUses` to not recurse but
705  // instead use the `follow` callback argument to look at transitive users,
706  // however, that should be clear from the presence of the argument.
707  bool UsedAssumedInformation = false;
709  getAssumedConstant(V, QueryingAA, UsedAssumedInformation);
710  if (C.hasValue() && C.getValue()) {
711  LLVM_DEBUG(dbgs() << "[Attributor] Value is simplified, uses skipped: " << V
712  << " -> " << *C.getValue() << "\n");
713  return true;
714  }
715 
716  const IRPosition &IRP = QueryingAA.getIRPosition();
719 
720  for (const Use &U : V.uses())
721  Worklist.push_back(&U);
722 
723  LLVM_DEBUG(dbgs() << "[Attributor] Got " << Worklist.size()
724  << " initial uses to check\n");
725 
726  const Function *ScopeFn = IRP.getAnchorScope();
727  const auto *LivenessAA =
728  ScopeFn ? &getAAFor<AAIsDead>(QueryingAA, IRPosition::function(*ScopeFn),
730  : nullptr;
731 
732  while (!Worklist.empty()) {
733  const Use *U = Worklist.pop_back_val();
734  if (!Visited.insert(U).second)
735  continue;
736  LLVM_DEBUG(dbgs() << "[Attributor] Check use: " << **U << " in "
737  << *U->getUser() << "\n");
738  if (isAssumedDead(*U, &QueryingAA, LivenessAA,
739  /* CheckBBLivenessOnly */ false, LivenessDepClass)) {
740  LLVM_DEBUG(dbgs() << "[Attributor] Dead use, skip!\n");
741  continue;
742  }
743  if (U->getUser()->isDroppable()) {
744  LLVM_DEBUG(dbgs() << "[Attributor] Droppable user, skip!\n");
745  continue;
746  }
747 
748  bool Follow = false;
749  if (!Pred(*U, Follow))
750  return false;
751  if (!Follow)
752  continue;
753  for (const Use &UU : U->getUser()->uses())
754  Worklist.push_back(&UU);
755  }
756 
757  return true;
758 }
759 
761  const AbstractAttribute &QueryingAA,
762  bool RequireAllCallSites,
763  bool &AllCallSitesKnown) {
764  // We can try to determine information from
765  // the call sites. However, this is only possible all call sites are known,
766  // hence the function has internal linkage.
767  const IRPosition &IRP = QueryingAA.getIRPosition();
768  const Function *AssociatedFunction = IRP.getAssociatedFunction();
769  if (!AssociatedFunction) {
770  LLVM_DEBUG(dbgs() << "[Attributor] No function associated with " << IRP
771  << "\n");
772  AllCallSitesKnown = false;
773  return false;
774  }
775 
776  return checkForAllCallSites(Pred, *AssociatedFunction, RequireAllCallSites,
777  &QueryingAA, AllCallSitesKnown);
778 }
779 
781  const Function &Fn,
782  bool RequireAllCallSites,
783  const AbstractAttribute *QueryingAA,
784  bool &AllCallSitesKnown) {
785  if (RequireAllCallSites && !Fn.hasLocalLinkage()) {
786  LLVM_DEBUG(
787  dbgs()
788  << "[Attributor] Function " << Fn.getName()
789  << " has no internal linkage, hence not all call sites are known\n");
790  AllCallSitesKnown = false;
791  return false;
792  }
793 
794  // If we do not require all call sites we might not see all.
795  AllCallSitesKnown = RequireAllCallSites;
796 
798  for (unsigned u = 0; u < Uses.size(); ++u) {
799  const Use &U = *Uses[u];
800  LLVM_DEBUG(dbgs() << "[Attributor] Check use: " << *U << " in "
801  << *U.getUser() << "\n");
802  if (isAssumedDead(U, QueryingAA, nullptr, /* CheckBBLivenessOnly */ true)) {
803  LLVM_DEBUG(dbgs() << "[Attributor] Dead use, skip!\n");
804  continue;
805  }
806  if (ConstantExpr *CE = dyn_cast<ConstantExpr>(U.getUser())) {
807  if (CE->isCast() && CE->getType()->isPointerTy() &&
808  CE->getType()->getPointerElementType()->isFunctionTy()) {
809  for (const Use &CEU : CE->uses())
810  Uses.push_back(&CEU);
811  continue;
812  }
813  }
814 
815  AbstractCallSite ACS(&U);
816  if (!ACS) {
817  LLVM_DEBUG(dbgs() << "[Attributor] Function " << Fn.getName()
818  << " has non call site use " << *U.get() << " in "
819  << *U.getUser() << "\n");
820  // BlockAddress users are allowed.
821  if (isa<BlockAddress>(U.getUser()))
822  continue;
823  return false;
824  }
825 
826  const Use *EffectiveUse =
827  ACS.isCallbackCall() ? &ACS.getCalleeUseForCallback() : &U;
828  if (!ACS.isCallee(EffectiveUse)) {
829  if (!RequireAllCallSites)
830  continue;
831  LLVM_DEBUG(dbgs() << "[Attributor] User " << EffectiveUse->getUser()
832  << " is an invalid use of " << Fn.getName() << "\n");
833  return false;
834  }
835 
836  // Make sure the arguments that can be matched between the call site and the
837  // callee argee on their type. It is unlikely they do not and it doesn't
838  // make sense for all attributes to know/care about this.
839  assert(&Fn == ACS.getCalledFunction() && "Expected known callee");
840  unsigned MinArgsParams =
841  std::min(size_t(ACS.getNumArgOperands()), Fn.arg_size());
842  for (unsigned u = 0; u < MinArgsParams; ++u) {
843  Value *CSArgOp = ACS.getCallArgOperand(u);
844  if (CSArgOp && Fn.getArg(u)->getType() != CSArgOp->getType()) {
845  LLVM_DEBUG(
846  dbgs() << "[Attributor] Call site / callee argument type mismatch ["
847  << u << "@" << Fn.getName() << ": "
848  << *Fn.getArg(u)->getType() << " vs. "
849  << *ACS.getCallArgOperand(u)->getType() << "\n");
850  return false;
851  }
852  }
853 
854  if (Pred(ACS))
855  continue;
856 
857  LLVM_DEBUG(dbgs() << "[Attributor] Call site callback failed for "
858  << *ACS.getInstruction() << "\n");
859  return false;
860  }
861 
862  return true;
863 }
864 
865 bool Attributor::shouldPropagateCallBaseContext(const IRPosition &IRP) {
866  // TODO: Maintain a cache of Values that are
867  // on the pathway from a Argument to a Instruction that would effect the
868  // liveness/return state etc.
869  return EnableCallSiteSpecific;
870 }
871 
873  function_ref<bool(Value &, const SmallSetVector<ReturnInst *, 4> &)> Pred,
874  const AbstractAttribute &QueryingAA) {
875 
876  const IRPosition &IRP = QueryingAA.getIRPosition();
877  // Since we need to provide return instructions we have to have an exact
878  // definition.
879  const Function *AssociatedFunction = IRP.getAssociatedFunction();
880  if (!AssociatedFunction)
881  return false;
882 
883  // If this is a call site query we use the call site specific return values
884  // and liveness information.
885  // TODO: use the function scope once we have call site AAReturnedValues.
886  const IRPosition &QueryIRP = IRPosition::function(*AssociatedFunction);
887  const auto &AARetVal =
888  getAAFor<AAReturnedValues>(QueryingAA, QueryIRP, DepClassTy::REQUIRED);
889  if (!AARetVal.getState().isValidState())
890  return false;
891 
892  return AARetVal.checkForAllReturnedValuesAndReturnInsts(Pred);
893 }
894 
896  function_ref<bool(Value &)> Pred, const AbstractAttribute &QueryingAA) {
897 
898  const IRPosition &IRP = QueryingAA.getIRPosition();
899  const Function *AssociatedFunction = IRP.getAssociatedFunction();
900  if (!AssociatedFunction)
901  return false;
902 
903  // TODO: use the function scope once we have call site AAReturnedValues.
904  const IRPosition &QueryIRP = IRPosition::function(*AssociatedFunction);
905  const auto &AARetVal =
906  getAAFor<AAReturnedValues>(QueryingAA, QueryIRP, DepClassTy::REQUIRED);
907  if (!AARetVal.getState().isValidState())
908  return false;
909 
910  return AARetVal.checkForAllReturnedValuesAndReturnInsts(
911  [&](Value &RV, const SmallSetVector<ReturnInst *, 4> &) {
912  return Pred(RV);
913  });
914 }
915 
918  function_ref<bool(Instruction &)> Pred, const AbstractAttribute *QueryingAA,
919  const AAIsDead *LivenessAA, const ArrayRef<unsigned> &Opcodes,
920  bool CheckBBLivenessOnly = false) {
921  for (unsigned Opcode : Opcodes) {
922  // Check if we have instructions with this opcode at all first.
923  auto *Insts = OpcodeInstMap.lookup(Opcode);
924  if (!Insts)
925  continue;
926 
927  for (Instruction *I : *Insts) {
928  // Skip dead instructions.
929  if (A && A->isAssumedDead(IRPosition::value(*I), QueryingAA, LivenessAA,
930  CheckBBLivenessOnly))
931  continue;
932 
933  if (!Pred(*I))
934  return false;
935  }
936  }
937  return true;
938 }
939 
941  const AbstractAttribute &QueryingAA,
942  const ArrayRef<unsigned> &Opcodes,
943  bool CheckBBLivenessOnly) {
944 
945  const IRPosition &IRP = QueryingAA.getIRPosition();
946  // Since we need to provide instructions we have to have an exact definition.
947  const Function *AssociatedFunction = IRP.getAssociatedFunction();
948  if (!AssociatedFunction)
949  return false;
950 
951  // TODO: use the function scope once we have call site AAReturnedValues.
952  const IRPosition &QueryIRP = IRPosition::function(*AssociatedFunction);
953  const auto *LivenessAA =
954  CheckBBLivenessOnly
955  ? nullptr
956  : &(getAAFor<AAIsDead>(QueryingAA, QueryIRP, DepClassTy::NONE));
957 
958  auto &OpcodeInstMap =
959  InfoCache.getOpcodeInstMapForFunction(*AssociatedFunction);
960  if (!checkForAllInstructionsImpl(this, OpcodeInstMap, Pred, &QueryingAA,
961  LivenessAA, Opcodes, CheckBBLivenessOnly))
962  return false;
963 
964  return true;
965 }
966 
968  function_ref<bool(Instruction &)> Pred, AbstractAttribute &QueryingAA) {
969 
970  const Function *AssociatedFunction =
971  QueryingAA.getIRPosition().getAssociatedFunction();
972  if (!AssociatedFunction)
973  return false;
974 
975  // TODO: use the function scope once we have call site AAReturnedValues.
976  const IRPosition &QueryIRP = IRPosition::function(*AssociatedFunction);
977  const auto &LivenessAA =
978  getAAFor<AAIsDead>(QueryingAA, QueryIRP, DepClassTy::NONE);
979 
980  for (Instruction *I :
981  InfoCache.getReadOrWriteInstsForFunction(*AssociatedFunction)) {
982  // Skip dead instructions.
983  if (isAssumedDead(IRPosition::value(*I), &QueryingAA, &LivenessAA))
984  continue;
985 
986  if (!Pred(*I))
987  return false;
988  }
989 
990  return true;
991 }
992 
993 void Attributor::runTillFixpoint() {
994  TimeTraceScope TimeScope("Attributor::runTillFixpoint");
995  LLVM_DEBUG(dbgs() << "[Attributor] Identified and initialized "
996  << DG.SyntheticRoot.Deps.size()
997  << " abstract attributes.\n");
998 
999  // Now that all abstract attributes are collected and initialized we start
1000  // the abstract analysis.
1001 
1002  unsigned IterationCounter = 1;
1003 
1005  SetVector<AbstractAttribute *> Worklist, InvalidAAs;
1006  Worklist.insert(DG.SyntheticRoot.begin(), DG.SyntheticRoot.end());
1007 
1008  do {
1009  // Remember the size to determine new attributes.
1010  size_t NumAAs = DG.SyntheticRoot.Deps.size();
1011  LLVM_DEBUG(dbgs() << "\n\n[Attributor] #Iteration: " << IterationCounter
1012  << ", Worklist size: " << Worklist.size() << "\n");
1013 
1014  // For invalid AAs we can fix dependent AAs that have a required dependence,
1015  // thereby folding long dependence chains in a single step without the need
1016  // to run updates.
1017  for (unsigned u = 0; u < InvalidAAs.size(); ++u) {
1018  AbstractAttribute *InvalidAA = InvalidAAs[u];
1019 
1020  // Check the dependences to fast track invalidation.
1021  LLVM_DEBUG(dbgs() << "[Attributor] InvalidAA: " << *InvalidAA << " has "
1022  << InvalidAA->Deps.size()
1023  << " required & optional dependences\n");
1024  while (!InvalidAA->Deps.empty()) {
1025  const auto &Dep = InvalidAA->Deps.back();
1026  InvalidAA->Deps.pop_back();
1027  AbstractAttribute *DepAA = cast<AbstractAttribute>(Dep.getPointer());
1028  if (Dep.getInt() == unsigned(DepClassTy::OPTIONAL)) {
1029  Worklist.insert(DepAA);
1030  continue;
1031  }
1033  assert(DepAA->getState().isAtFixpoint() && "Expected fixpoint state!");
1034  if (!DepAA->getState().isValidState())
1035  InvalidAAs.insert(DepAA);
1036  else
1037  ChangedAAs.push_back(DepAA);
1038  }
1039  }
1040 
1041  // Add all abstract attributes that are potentially dependent on one that
1042  // changed to the work list.
1043  for (AbstractAttribute *ChangedAA : ChangedAAs)
1044  while (!ChangedAA->Deps.empty()) {
1045  Worklist.insert(
1046  cast<AbstractAttribute>(ChangedAA->Deps.back().getPointer()));
1047  ChangedAA->Deps.pop_back();
1048  }
1049 
1050  LLVM_DEBUG(dbgs() << "[Attributor] #Iteration: " << IterationCounter
1051  << ", Worklist+Dependent size: " << Worklist.size()
1052  << "\n");
1053 
1054  // Reset the changed and invalid set.
1055  ChangedAAs.clear();
1056  InvalidAAs.clear();
1057 
1058  // Update all abstract attribute in the work list and record the ones that
1059  // changed.
1060  for (AbstractAttribute *AA : Worklist) {
1061  const auto &AAState = AA->getState();
1062  if (!AAState.isAtFixpoint())
1063  if (updateAA(*AA) == ChangeStatus::CHANGED)
1064  ChangedAAs.push_back(AA);
1065 
1066  // Use the InvalidAAs vector to propagate invalid states fast transitively
1067  // without requiring updates.
1068  if (!AAState.isValidState())
1069  InvalidAAs.insert(AA);
1070  }
1071 
1072  // Add attributes to the changed set if they have been created in the last
1073  // iteration.
1074  ChangedAAs.append(DG.SyntheticRoot.begin() + NumAAs,
1075  DG.SyntheticRoot.end());
1076 
1077  // Reset the work list and repopulate with the changed abstract attributes.
1078  // Note that dependent ones are added above.
1079  Worklist.clear();
1080  Worklist.insert(ChangedAAs.begin(), ChangedAAs.end());
1081 
1082  } while (!Worklist.empty() && (IterationCounter++ < MaxFixpointIterations ||
1084 
1085  LLVM_DEBUG(dbgs() << "\n[Attributor] Fixpoint iteration done after: "
1086  << IterationCounter << "/" << MaxFixpointIterations
1087  << " iterations\n");
1088 
1089  // Reset abstract arguments not settled in a sound fixpoint by now. This
1090  // happens when we stopped the fixpoint iteration early. Note that only the
1091  // ones marked as "changed" *and* the ones transitively depending on them
1092  // need to be reverted to a pessimistic state. Others might not be in a
1093  // fixpoint state but we can use the optimistic results for them anyway.
1095  for (unsigned u = 0; u < ChangedAAs.size(); u++) {
1096  AbstractAttribute *ChangedAA = ChangedAAs[u];
1097  if (!Visited.insert(ChangedAA).second)
1098  continue;
1099 
1100  AbstractState &State = ChangedAA->getState();
1101  if (!State.isAtFixpoint()) {
1103 
1104  NumAttributesTimedOut++;
1105  }
1106 
1107  while (!ChangedAA->Deps.empty()) {
1108  ChangedAAs.push_back(
1109  cast<AbstractAttribute>(ChangedAA->Deps.back().getPointer()));
1110  ChangedAA->Deps.pop_back();
1111  }
1112  }
1113 
1114  LLVM_DEBUG({
1115  if (!Visited.empty())
1116  dbgs() << "\n[Attributor] Finalized " << Visited.size()
1117  << " abstract attributes.\n";
1118  });
1119 
1121  IterationCounter != MaxFixpointIterations) {
1122  errs() << "\n[Attributor] Fixpoint iteration done after: "
1123  << IterationCounter << "/" << MaxFixpointIterations
1124  << " iterations\n";
1125  llvm_unreachable("The fixpoint was not reached with exactly the number of "
1126  "specified iterations!");
1127  }
1128 }
1129 
1130 ChangeStatus Attributor::manifestAttributes() {
1131  TimeTraceScope TimeScope("Attributor::manifestAttributes");
1132  size_t NumFinalAAs = DG.SyntheticRoot.Deps.size();
1133 
1134  unsigned NumManifested = 0;
1135  unsigned NumAtFixpoint = 0;
1136  ChangeStatus ManifestChange = ChangeStatus::UNCHANGED;
1137  for (auto &DepAA : DG.SyntheticRoot.Deps) {
1138  AbstractAttribute *AA = cast<AbstractAttribute>(DepAA.getPointer());
1139  AbstractState &State = AA->getState();
1140 
1141  // If there is not already a fixpoint reached, we can now take the
1142  // optimistic state. This is correct because we enforced a pessimistic one
1143  // on abstract attributes that were transitively dependent on a changed one
1144  // already above.
1145  if (!State.isAtFixpoint())
1147 
1148  // We must not manifest Attributes that use Callbase info.
1149  if (AA->hasCallBaseContext())
1150  continue;
1151  // If the state is invalid, we do not try to manifest it.
1152  if (!State.isValidState())
1153  continue;
1154 
1155  // Skip dead code.
1156  if (isAssumedDead(*AA, nullptr, /* CheckBBLivenessOnly */ true))
1157  continue;
1158  // Check if the manifest debug counter that allows skipping manifestation of
1159  // AAs
1160  if (!DebugCounter::shouldExecute(ManifestDBGCounter))
1161  continue;
1162  // Manifest the state and record if we changed the IR.
1163  ChangeStatus LocalChange = AA->manifest(*this);
1164  if (LocalChange == ChangeStatus::CHANGED && AreStatisticsEnabled())
1165  AA->trackStatistics();
1166  LLVM_DEBUG(dbgs() << "[Attributor] Manifest " << LocalChange << " : " << *AA
1167  << "\n");
1168 
1169  ManifestChange = ManifestChange | LocalChange;
1170 
1171  NumAtFixpoint++;
1172  NumManifested += (LocalChange == ChangeStatus::CHANGED);
1173  }
1174 
1175  (void)NumManifested;
1176  (void)NumAtFixpoint;
1177  LLVM_DEBUG(dbgs() << "\n[Attributor] Manifested " << NumManifested
1178  << " arguments while " << NumAtFixpoint
1179  << " were in a valid fixpoint state\n");
1180 
1181  NumAttributesManifested += NumManifested;
1182  NumAttributesValidFixpoint += NumAtFixpoint;
1183 
1184  (void)NumFinalAAs;
1185  if (NumFinalAAs != DG.SyntheticRoot.Deps.size()) {
1186  for (unsigned u = NumFinalAAs; u < DG.SyntheticRoot.Deps.size(); ++u)
1187  errs() << "Unexpected abstract attribute: "
1188  << cast<AbstractAttribute>(DG.SyntheticRoot.Deps[u].getPointer())
1189  << " :: "
1190  << cast<AbstractAttribute>(DG.SyntheticRoot.Deps[u].getPointer())
1191  ->getIRPosition()
1192  .getAssociatedValue()
1193  << "\n";
1194  llvm_unreachable("Expected the final number of abstract attributes to "
1195  "remain unchanged!");
1196  }
1197  return ManifestChange;
1198 }
1199 
1200 void Attributor::identifyDeadInternalFunctions() {
1201  // Early exit if we don't intend to delete functions.
1202  if (!DeleteFns)
1203  return;
1204 
1205  // Identify dead internal functions and delete them. This happens outside
1206  // the other fixpoint analysis as we might treat potentially dead functions
1207  // as live to lower the number of iterations. If they happen to be dead, the
1208  // below fixpoint loop will identify and eliminate them.
1209  SmallVector<Function *, 8> InternalFns;
1210  for (Function *F : Functions)
1211  if (F->hasLocalLinkage())
1212  InternalFns.push_back(F);
1213 
1214  SmallPtrSet<Function *, 8> LiveInternalFns;
1215  bool FoundLiveInternal = true;
1216  while (FoundLiveInternal) {
1217  FoundLiveInternal = false;
1218  for (unsigned u = 0, e = InternalFns.size(); u < e; ++u) {
1219  Function *F = InternalFns[u];
1220  if (!F)
1221  continue;
1222 
1223  bool AllCallSitesKnown;
1225  [&](AbstractCallSite ACS) {
1227  return ToBeDeletedFunctions.count(Callee) ||
1228  (Functions.count(Callee) && Callee->hasLocalLinkage() &&
1229  !LiveInternalFns.count(Callee));
1230  },
1231  *F, true, nullptr, AllCallSitesKnown)) {
1232  continue;
1233  }
1234 
1235  LiveInternalFns.insert(F);
1236  InternalFns[u] = nullptr;
1237  FoundLiveInternal = true;
1238  }
1239  }
1240 
1241  for (unsigned u = 0, e = InternalFns.size(); u < e; ++u)
1242  if (Function *F = InternalFns[u])
1243  ToBeDeletedFunctions.insert(F);
1244 }
1245 
1246 ChangeStatus Attributor::cleanupIR() {
1247  TimeTraceScope TimeScope("Attributor::cleanupIR");
1248  // Delete stuff at the end to avoid invalid references and a nice order.
1249  LLVM_DEBUG(dbgs() << "\n[Attributor] Delete at least "
1250  << ToBeDeletedFunctions.size() << " functions and "
1251  << ToBeDeletedBlocks.size() << " blocks and "
1252  << ToBeDeletedInsts.size() << " instructions and "
1253  << ToBeChangedUses.size() << " uses\n");
1254 
1256  SmallVector<Instruction *, 32> TerminatorsToFold;
1257 
1258  for (auto &It : ToBeChangedUses) {
1259  Use *U = It.first;
1260  Value *NewV = It.second;
1261  Value *OldV = U->get();
1262 
1263  // Do not replace uses in returns if the value is a must-tail call we will
1264  // not delete.
1265  if (isa<ReturnInst>(U->getUser()))
1266  if (auto *CI = dyn_cast<CallInst>(OldV->stripPointerCasts()))
1267  if (CI->isMustTailCall() && !ToBeDeletedInsts.count(CI))
1268  continue;
1269 
1270  LLVM_DEBUG(dbgs() << "Use " << *NewV << " in " << *U->getUser()
1271  << " instead of " << *OldV << "\n");
1272  U->set(NewV);
1273  // Do not modify call instructions outside the SCC.
1274  if (auto *CB = dyn_cast<CallBase>(OldV))
1275  if (!Functions.count(CB->getCaller()))
1276  continue;
1277  if (Instruction *I = dyn_cast<Instruction>(OldV)) {
1278  CGModifiedFunctions.insert(I->getFunction());
1279  if (!isa<PHINode>(I) && !ToBeDeletedInsts.count(I) &&
1281  DeadInsts.push_back(I);
1282  }
1283  if (isa<UndefValue>(NewV) && isa<CallBase>(U->getUser())) {
1284  auto *CB = cast<CallBase>(U->getUser());
1285  if (CB->isArgOperand(U)) {
1286  unsigned Idx = CB->getArgOperandNo(U);
1287  CB->removeParamAttr(Idx, Attribute::NoUndef);
1288  Function *Fn = CB->getCalledFunction();
1289  assert(Fn && "Expected callee when call argument is replaced!");
1290  if (Fn->arg_size() > Idx)
1291  Fn->removeParamAttr(Idx, Attribute::NoUndef);
1292  }
1293  }
1294  if (isa<Constant>(NewV) && isa<BranchInst>(U->getUser())) {
1295  Instruction *UserI = cast<Instruction>(U->getUser());
1296  if (isa<UndefValue>(NewV)) {
1297  ToBeChangedToUnreachableInsts.insert(UserI);
1298  } else {
1299  TerminatorsToFold.push_back(UserI);
1300  }
1301  }
1302  }
1303  for (auto &V : InvokeWithDeadSuccessor)
1304  if (InvokeInst *II = dyn_cast_or_null<InvokeInst>(V)) {
1305  bool UnwindBBIsDead = II->hasFnAttr(Attribute::NoUnwind);
1306  bool NormalBBIsDead = II->hasFnAttr(Attribute::NoReturn);
1307  bool Invoke2CallAllowed =
1308  !AAIsDead::mayCatchAsynchronousExceptions(*II->getFunction());
1309  assert((UnwindBBIsDead || NormalBBIsDead) &&
1310  "Invoke does not have dead successors!");
1311  BasicBlock *BB = II->getParent();
1312  BasicBlock *NormalDestBB = II->getNormalDest();
1313  if (UnwindBBIsDead) {
1314  Instruction *NormalNextIP = &NormalDestBB->front();
1315  if (Invoke2CallAllowed) {
1316  changeToCall(II);
1317  NormalNextIP = BB->getTerminator();
1318  }
1319  if (NormalBBIsDead)
1320  ToBeChangedToUnreachableInsts.insert(NormalNextIP);
1321  } else {
1322  assert(NormalBBIsDead && "Broken invariant!");
1323  if (!NormalDestBB->getUniquePredecessor())
1324  NormalDestBB = SplitBlockPredecessors(NormalDestBB, {BB}, ".dead");
1325  ToBeChangedToUnreachableInsts.insert(&NormalDestBB->front());
1326  }
1327  }
1328  for (Instruction *I : TerminatorsToFold) {
1329  CGModifiedFunctions.insert(I->getFunction());
1330  ConstantFoldTerminator(I->getParent());
1331  }
1332  for (auto &V : ToBeChangedToUnreachableInsts)
1333  if (Instruction *I = dyn_cast_or_null<Instruction>(V)) {
1334  CGModifiedFunctions.insert(I->getFunction());
1335  changeToUnreachable(I, /* UseLLVMTrap */ false);
1336  }
1337 
1338  for (auto &V : ToBeDeletedInsts) {
1339  if (Instruction *I = dyn_cast_or_null<Instruction>(V)) {
1340  I->dropDroppableUses();
1341  CGModifiedFunctions.insert(I->getFunction());
1342  if (!I->getType()->isVoidTy())
1343  I->replaceAllUsesWith(UndefValue::get(I->getType()));
1344  if (!isa<PHINode>(I) && isInstructionTriviallyDead(I))
1345  DeadInsts.push_back(I);
1346  else
1347  I->eraseFromParent();
1348  }
1349  }
1350 
1351  LLVM_DEBUG(dbgs() << "[Attributor] DeadInsts size: " << DeadInsts.size()
1352  << "\n");
1353 
1355 
1356  if (unsigned NumDeadBlocks = ToBeDeletedBlocks.size()) {
1357  SmallVector<BasicBlock *, 8> ToBeDeletedBBs;
1358  ToBeDeletedBBs.reserve(NumDeadBlocks);
1359  for (BasicBlock *BB : ToBeDeletedBlocks) {
1360  CGModifiedFunctions.insert(BB->getParent());
1361  ToBeDeletedBBs.push_back(BB);
1362  }
1363  // Actually we do not delete the blocks but squash them into a single
1364  // unreachable but untangling branches that jump here is something we need
1365  // to do in a more generic way.
1366  DetatchDeadBlocks(ToBeDeletedBBs, nullptr);
1367  }
1368 
1369  identifyDeadInternalFunctions();
1370 
1371  // Rewrite the functions as requested during manifest.
1372  ChangeStatus ManifestChange = rewriteFunctionSignatures(CGModifiedFunctions);
1373 
1374  for (Function *Fn : CGModifiedFunctions)
1375  if (!ToBeDeletedFunctions.count(Fn))
1376  CGUpdater.reanalyzeFunction(*Fn);
1377 
1378  for (Function *Fn : ToBeDeletedFunctions) {
1379  if (!Functions.count(Fn))
1380  continue;
1381  CGUpdater.removeFunction(*Fn);
1382  }
1383 
1384  if (!ToBeChangedUses.empty())
1385  ManifestChange = ChangeStatus::CHANGED;
1386 
1387  if (!ToBeChangedToUnreachableInsts.empty())
1388  ManifestChange = ChangeStatus::CHANGED;
1389 
1390  if (!ToBeDeletedFunctions.empty())
1391  ManifestChange = ChangeStatus::CHANGED;
1392 
1393  if (!ToBeDeletedBlocks.empty())
1394  ManifestChange = ChangeStatus::CHANGED;
1395 
1396  if (!ToBeDeletedInsts.empty())
1397  ManifestChange = ChangeStatus::CHANGED;
1398 
1399  if (!InvokeWithDeadSuccessor.empty())
1400  ManifestChange = ChangeStatus::CHANGED;
1401 
1402  if (!DeadInsts.empty())
1403  ManifestChange = ChangeStatus::CHANGED;
1404 
1405  NumFnDeleted += ToBeDeletedFunctions.size();
1406 
1407  LLVM_DEBUG(dbgs() << "[Attributor] Deleted " << ToBeDeletedFunctions.size()
1408  << " functions after manifest.\n");
1409 
1410 #ifdef EXPENSIVE_CHECKS
1411  for (Function *F : Functions) {
1412  if (ToBeDeletedFunctions.count(F))
1413  continue;
1414  assert(!verifyFunction(*F, &errs()) && "Module verification failed!");
1415  }
1416 #endif
1417 
1418  return ManifestChange;
1419 }
1420 
1422  TimeTraceScope TimeScope("Attributor::run");
1423 
1424  Phase = AttributorPhase::UPDATE;
1425  runTillFixpoint();
1426 
1427  // dump graphs on demand
1428  if (DumpDepGraph)
1429  DG.dumpGraph();
1430 
1431  if (ViewDepGraph)
1432  DG.viewGraph();
1433 
1434  if (PrintDependencies)
1435  DG.print();
1436 
1437  Phase = AttributorPhase::MANIFEST;
1438  ChangeStatus ManifestChange = manifestAttributes();
1439 
1440  Phase = AttributorPhase::CLEANUP;
1441  ChangeStatus CleanupChange = cleanupIR();
1442 
1443  return ManifestChange | CleanupChange;
1444 }
1445 
1446 ChangeStatus Attributor::updateAA(AbstractAttribute &AA) {
1447  TimeTraceScope TimeScope(
1449  "::updateAA");
1450  assert(Phase == AttributorPhase::UPDATE &&
1451  "We can update AA only in the update stage!");
1452 
1453  // Use a new dependence vector for this update.
1454  DependenceVector DV;
1455  DependenceStack.push_back(&DV);
1456 
1457  auto &AAState = AA.getState();
1459  if (!isAssumedDead(AA, nullptr, /* CheckBBLivenessOnly */ true))
1460  CS = AA.update(*this);
1461 
1462  if (DV.empty()) {
1463  // If the attribute did not query any non-fix information, the state
1464  // will not change and we can indicate that right away.
1465  AAState.indicateOptimisticFixpoint();
1466  }
1467 
1468  if (!AAState.isAtFixpoint())
1469  rememberDependences();
1470 
1471  // Verify the stack was used properly, that is we pop the dependence vector we
1472  // put there earlier.
1473  DependenceVector *PoppedDV = DependenceStack.pop_back_val();
1474  (void)PoppedDV;
1475  assert(PoppedDV == &DV && "Inconsistent usage of the dependence stack!");
1476 
1477  return CS;
1478 }
1479 
1481  assert(!F.isDeclaration() && "Cannot create a wrapper around a declaration!");
1482 
1483  Module &M = *F.getParent();
1484  LLVMContext &Ctx = M.getContext();
1485  FunctionType *FnTy = F.getFunctionType();
1486 
1487  Function *Wrapper =
1488  Function::Create(FnTy, F.getLinkage(), F.getAddressSpace(), F.getName());
1489  F.setName(""); // set the inside function anonymous
1490  M.getFunctionList().insert(F.getIterator(), Wrapper);
1491 
1492  F.setLinkage(GlobalValue::InternalLinkage);
1493 
1494  F.replaceAllUsesWith(Wrapper);
1495  assert(F.use_empty() && "Uses remained after wrapper was created!");
1496 
1497  // Move the COMDAT section to the wrapper.
1498  // TODO: Check if we need to keep it for F as well.
1499  Wrapper->setComdat(F.getComdat());
1500  F.setComdat(nullptr);
1501 
1502  // Copy all metadata and attributes but keep them on F as well.
1504  F.getAllMetadata(MDs);
1505  for (auto MDIt : MDs)
1506  Wrapper->addMetadata(MDIt.first, *MDIt.second);
1507  Wrapper->setAttributes(F.getAttributes());
1508 
1509  // Create the call in the wrapper.
1510  BasicBlock *EntryBB = BasicBlock::Create(Ctx, "entry", Wrapper);
1511 
1513  Argument *FArgIt = F.arg_begin();
1514  for (Argument &Arg : Wrapper->args()) {
1515  Args.push_back(&Arg);
1516  Arg.setName((FArgIt++)->getName());
1517  }
1518 
1519  CallInst *CI = CallInst::Create(&F, Args, "", EntryBB);
1520  CI->setTailCall(true);
1521  CI->addAttribute(AttributeList::FunctionIndex, Attribute::NoInline);
1522  ReturnInst::Create(Ctx, CI->getType()->isVoidTy() ? nullptr : CI, EntryBB);
1523 
1524  NumFnShallowWrappersCreated++;
1525 }
1526 
1527 /// Make another copy of the function \p F such that the copied version has
1528 /// internal linkage afterwards and can be analysed. Then we replace all uses
1529 /// of the original function to the copied one
1530 ///
1531 /// Only non-exactly defined functions that have `linkonce_odr` or `weak_odr`
1532 /// linkage can be internalized because these linkages guarantee that other
1533 /// definitions with the same name have the same semantics as this one
1534 ///
1536  assert(AllowDeepWrapper && "Cannot create a copy if not allowed.");
1537  assert(!F.isDeclaration() && !F.hasExactDefinition() &&
1538  !GlobalValue::isInterposableLinkage(F.getLinkage()) &&
1539  "Trying to internalize function which cannot be internalized.");
1540 
1541  Module &M = *F.getParent();
1542  FunctionType *FnTy = F.getFunctionType();
1543 
1544  // create a copy of the current function
1545  Function *Copied = Function::Create(FnTy, F.getLinkage(), F.getAddressSpace(),
1546  F.getName() + ".internalized");
1547  ValueToValueMapTy VMap;
1548  auto *NewFArgIt = Copied->arg_begin();
1549  for (auto &Arg : F.args()) {
1550  auto ArgName = Arg.getName();
1551  NewFArgIt->setName(ArgName);
1552  VMap[&Arg] = &(*NewFArgIt++);
1553  }
1555 
1556  // Copy the body of the original function to the new one
1558  Returns);
1559 
1560  // Set the linakage and visibility late as CloneFunctionInto has some implicit
1561  // requirements.
1564 
1565  // Copy metadata
1567  F.getAllMetadata(MDs);
1568  for (auto MDIt : MDs)
1569  Copied->addMetadata(MDIt.first, *MDIt.second);
1570 
1571  M.getFunctionList().insert(F.getIterator(), Copied);
1572  F.replaceAllUsesWith(Copied);
1573  Copied->setDSOLocal(true);
1574 
1575  return Copied;
1576 }
1577 
1579  Argument &Arg, ArrayRef<Type *> ReplacementTypes) {
1580 
1581  auto CallSiteCanBeChanged = [](AbstractCallSite ACS) {
1582  // Forbid the call site to cast the function return type. If we need to
1583  // rewrite these functions we need to re-create a cast for the new call site
1584  // (if the old had uses).
1585  if (!ACS.getCalledFunction() ||
1586  ACS.getInstruction()->getType() !=
1588  return false;
1589  // Forbid must-tail calls for now.
1590  return !ACS.isCallbackCall() && !ACS.getInstruction()->isMustTailCall();
1591  };
1592 
1593  Function *Fn = Arg.getParent();
1594  // Avoid var-arg functions for now.
1595  if (Fn->isVarArg()) {
1596  LLVM_DEBUG(dbgs() << "[Attributor] Cannot rewrite var-args functions\n");
1597  return false;
1598  }
1599 
1600  // Avoid functions with complicated argument passing semantics.
1601  AttributeList FnAttributeList = Fn->getAttributes();
1602  if (FnAttributeList.hasAttrSomewhere(Attribute::Nest) ||
1603  FnAttributeList.hasAttrSomewhere(Attribute::StructRet) ||
1604  FnAttributeList.hasAttrSomewhere(Attribute::InAlloca) ||
1605  FnAttributeList.hasAttrSomewhere(Attribute::Preallocated)) {
1606  LLVM_DEBUG(
1607  dbgs() << "[Attributor] Cannot rewrite due to complex attribute\n");
1608  return false;
1609  }
1610 
1611  // Avoid callbacks for now.
1612  bool AllCallSitesKnown;
1613  if (!checkForAllCallSites(CallSiteCanBeChanged, *Fn, true, nullptr,
1614  AllCallSitesKnown)) {
1615  LLVM_DEBUG(dbgs() << "[Attributor] Cannot rewrite all call sites\n");
1616  return false;
1617  }
1618 
1619  auto InstPred = [](Instruction &I) {
1620  if (auto *CI = dyn_cast<CallInst>(&I))
1621  return !CI->isMustTailCall();
1622  return true;
1623  };
1624 
1625  // Forbid must-tail calls for now.
1626  // TODO:
1627  auto &OpcodeInstMap = InfoCache.getOpcodeInstMapForFunction(*Fn);
1628  if (!checkForAllInstructionsImpl(nullptr, OpcodeInstMap, InstPred, nullptr,
1629  nullptr, {Instruction::Call})) {
1630  LLVM_DEBUG(dbgs() << "[Attributor] Cannot rewrite due to instructions\n");
1631  return false;
1632  }
1633 
1634  return true;
1635 }
1636 
1638  Argument &Arg, ArrayRef<Type *> ReplacementTypes,
1641  LLVM_DEBUG(dbgs() << "[Attributor] Register new rewrite of " << Arg << " in "
1642  << Arg.getParent()->getName() << " with "
1643  << ReplacementTypes.size() << " replacements\n");
1644  assert(isValidFunctionSignatureRewrite(Arg, ReplacementTypes) &&
1645  "Cannot register an invalid rewrite");
1646 
1647  Function *Fn = Arg.getParent();
1649  ArgumentReplacementMap[Fn];
1650  if (ARIs.empty())
1651  ARIs.resize(Fn->arg_size());
1652 
1653  // If we have a replacement already with less than or equal new arguments,
1654  // ignore this request.
1655  std::unique_ptr<ArgumentReplacementInfo> &ARI = ARIs[Arg.getArgNo()];
1656  if (ARI && ARI->getNumReplacementArgs() <= ReplacementTypes.size()) {
1657  LLVM_DEBUG(dbgs() << "[Attributor] Existing rewrite is preferred\n");
1658  return false;
1659  }
1660 
1661  // If we have a replacement already but we like the new one better, delete
1662  // the old.
1663  ARI.reset();
1664 
1665  LLVM_DEBUG(dbgs() << "[Attributor] Register new rewrite of " << Arg << " in "
1666  << Arg.getParent()->getName() << " with "
1667  << ReplacementTypes.size() << " replacements\n");
1668 
1669  // Remember the replacement.
1670  ARI.reset(new ArgumentReplacementInfo(*this, Arg, ReplacementTypes,
1671  std::move(CalleeRepairCB),
1672  std::move(ACSRepairCB)));
1673 
1674  return true;
1675 }
1676 
1677 bool Attributor::shouldSeedAttribute(AbstractAttribute &AA) {
1678  bool Result = true;
1679 #ifndef NDEBUG
1680  if (SeedAllowList.size() != 0)
1681  Result =
1682  std::count(SeedAllowList.begin(), SeedAllowList.end(), AA.getName());
1683  Function *Fn = AA.getAnchorScope();
1684  if (FunctionSeedAllowList.size() != 0 && Fn)
1685  Result &= std::count(FunctionSeedAllowList.begin(),
1686  FunctionSeedAllowList.end(), Fn->getName());
1687 #endif
1688  return Result;
1689 }
1690 
1691 ChangeStatus Attributor::rewriteFunctionSignatures(
1692  SmallPtrSetImpl<Function *> &ModifiedFns) {
1694 
1695  for (auto &It : ArgumentReplacementMap) {
1696  Function *OldFn = It.getFirst();
1697 
1698  // Deleted functions do not require rewrites.
1699  if (!Functions.count(OldFn) || ToBeDeletedFunctions.count(OldFn))
1700  continue;
1701 
1703  It.getSecond();
1704  assert(ARIs.size() == OldFn->arg_size() && "Inconsistent state!");
1705 
1706  SmallVector<Type *, 16> NewArgumentTypes;
1707  SmallVector<AttributeSet, 16> NewArgumentAttributes;
1708 
1709  // Collect replacement argument types and copy over existing attributes.
1710  AttributeList OldFnAttributeList = OldFn->getAttributes();
1711  for (Argument &Arg : OldFn->args()) {
1712  if (const std::unique_ptr<ArgumentReplacementInfo> &ARI =
1713  ARIs[Arg.getArgNo()]) {
1714  NewArgumentTypes.append(ARI->ReplacementTypes.begin(),
1715  ARI->ReplacementTypes.end());
1716  NewArgumentAttributes.append(ARI->getNumReplacementArgs(),
1717  AttributeSet());
1718  } else {
1719  NewArgumentTypes.push_back(Arg.getType());
1720  NewArgumentAttributes.push_back(
1721  OldFnAttributeList.getParamAttributes(Arg.getArgNo()));
1722  }
1723  }
1724 
1725  FunctionType *OldFnTy = OldFn->getFunctionType();
1726  Type *RetTy = OldFnTy->getReturnType();
1727 
1728  // Construct the new function type using the new arguments types.
1729  FunctionType *NewFnTy =
1730  FunctionType::get(RetTy, NewArgumentTypes, OldFnTy->isVarArg());
1731 
1732  LLVM_DEBUG(dbgs() << "[Attributor] Function rewrite '" << OldFn->getName()
1733  << "' from " << *OldFn->getFunctionType() << " to "
1734  << *NewFnTy << "\n");
1735 
1736  // Create the new function body and insert it into the module.
1737  Function *NewFn = Function::Create(NewFnTy, OldFn->getLinkage(),
1738  OldFn->getAddressSpace(), "");
1739  OldFn->getParent()->getFunctionList().insert(OldFn->getIterator(), NewFn);
1740  NewFn->takeName(OldFn);
1741  NewFn->copyAttributesFrom(OldFn);
1742 
1743  // Patch the pointer to LLVM function in debug info descriptor.
1744  NewFn->setSubprogram(OldFn->getSubprogram());
1745  OldFn->setSubprogram(nullptr);
1746 
1747  // Recompute the parameter attributes list based on the new arguments for
1748  // the function.
1749  LLVMContext &Ctx = OldFn->getContext();
1751  Ctx, OldFnAttributeList.getFnAttributes(),
1752  OldFnAttributeList.getRetAttributes(), NewArgumentAttributes));
1753 
1754  // Since we have now created the new function, splice the body of the old
1755  // function right into the new function, leaving the old rotting hulk of the
1756  // function empty.
1757  NewFn->getBasicBlockList().splice(NewFn->begin(),
1758  OldFn->getBasicBlockList());
1759 
1760  // Fixup block addresses to reference new function.
1761  SmallVector<BlockAddress *, 8u> BlockAddresses;
1762  for (User *U : OldFn->users())
1763  if (auto *BA = dyn_cast<BlockAddress>(U))
1764  BlockAddresses.push_back(BA);
1765  for (auto *BA : BlockAddresses)
1766  BA->replaceAllUsesWith(BlockAddress::get(NewFn, BA->getBasicBlock()));
1767 
1768  // Set of all "call-like" instructions that invoke the old function mapped
1769  // to their new replacements.
1771 
1772  // Callback to create a new "call-like" instruction for a given one.
1773  auto CallSiteReplacementCreator = [&](AbstractCallSite ACS) {
1774  CallBase *OldCB = cast<CallBase>(ACS.getInstruction());
1775  const AttributeList &OldCallAttributeList = OldCB->getAttributes();
1776 
1777  // Collect the new argument operands for the replacement call site.
1778  SmallVector<Value *, 16> NewArgOperands;
1779  SmallVector<AttributeSet, 16> NewArgOperandAttributes;
1780  for (unsigned OldArgNum = 0; OldArgNum < ARIs.size(); ++OldArgNum) {
1781  unsigned NewFirstArgNum = NewArgOperands.size();
1782  (void)NewFirstArgNum; // only used inside assert.
1783  if (const std::unique_ptr<ArgumentReplacementInfo> &ARI =
1784  ARIs[OldArgNum]) {
1785  if (ARI->ACSRepairCB)
1786  ARI->ACSRepairCB(*ARI, ACS, NewArgOperands);
1787  assert(ARI->getNumReplacementArgs() + NewFirstArgNum ==
1788  NewArgOperands.size() &&
1789  "ACS repair callback did not provide as many operand as new "
1790  "types were registered!");
1791  // TODO: Exose the attribute set to the ACS repair callback
1792  NewArgOperandAttributes.append(ARI->ReplacementTypes.size(),
1793  AttributeSet());
1794  } else {
1795  NewArgOperands.push_back(ACS.getCallArgOperand(OldArgNum));
1796  NewArgOperandAttributes.push_back(
1797  OldCallAttributeList.getParamAttributes(OldArgNum));
1798  }
1799  }
1800 
1801  assert(NewArgOperands.size() == NewArgOperandAttributes.size() &&
1802  "Mismatch # argument operands vs. # argument operand attributes!");
1803  assert(NewArgOperands.size() == NewFn->arg_size() &&
1804  "Mismatch # argument operands vs. # function arguments!");
1805 
1806  SmallVector<OperandBundleDef, 4> OperandBundleDefs;
1807  OldCB->getOperandBundlesAsDefs(OperandBundleDefs);
1808 
1809  // Create a new call or invoke instruction to replace the old one.
1810  CallBase *NewCB;
1811  if (InvokeInst *II = dyn_cast<InvokeInst>(OldCB)) {
1812  NewCB =
1813  InvokeInst::Create(NewFn, II->getNormalDest(), II->getUnwindDest(),
1814  NewArgOperands, OperandBundleDefs, "", OldCB);
1815  } else {
1816  auto *NewCI = CallInst::Create(NewFn, NewArgOperands, OperandBundleDefs,
1817  "", OldCB);
1818  NewCI->setTailCallKind(cast<CallInst>(OldCB)->getTailCallKind());
1819  NewCB = NewCI;
1820  }
1821 
1822  // Copy over various properties and the new attributes.
1823  NewCB->copyMetadata(*OldCB, {LLVMContext::MD_prof, LLVMContext::MD_dbg});
1824  NewCB->setCallingConv(OldCB->getCallingConv());
1825  NewCB->takeName(OldCB);
1827  Ctx, OldCallAttributeList.getFnAttributes(),
1828  OldCallAttributeList.getRetAttributes(), NewArgOperandAttributes));
1829 
1830  CallSitePairs.push_back({OldCB, NewCB});
1831  return true;
1832  };
1833 
1834  // Use the CallSiteReplacementCreator to create replacement call sites.
1835  bool AllCallSitesKnown;
1836  bool Success = checkForAllCallSites(CallSiteReplacementCreator, *OldFn,
1837  true, nullptr, AllCallSitesKnown);
1838  (void)Success;
1839  assert(Success && "Assumed call site replacement to succeed!");
1840 
1841  // Rewire the arguments.
1842  Argument *OldFnArgIt = OldFn->arg_begin();
1843  Argument *NewFnArgIt = NewFn->arg_begin();
1844  for (unsigned OldArgNum = 0; OldArgNum < ARIs.size();
1845  ++OldArgNum, ++OldFnArgIt) {
1846  if (const std::unique_ptr<ArgumentReplacementInfo> &ARI =
1847  ARIs[OldArgNum]) {
1848  if (ARI->CalleeRepairCB)
1849  ARI->CalleeRepairCB(*ARI, *NewFn, NewFnArgIt);
1850  NewFnArgIt += ARI->ReplacementTypes.size();
1851  } else {
1852  NewFnArgIt->takeName(&*OldFnArgIt);
1853  OldFnArgIt->replaceAllUsesWith(&*NewFnArgIt);
1854  ++NewFnArgIt;
1855  }
1856  }
1857 
1858  // Eliminate the instructions *after* we visited all of them.
1859  for (auto &CallSitePair : CallSitePairs) {
1860  CallBase &OldCB = *CallSitePair.first;
1861  CallBase &NewCB = *CallSitePair.second;
1862  assert(OldCB.getType() == NewCB.getType() &&
1863  "Cannot handle call sites with different types!");
1864  ModifiedFns.insert(OldCB.getFunction());
1865  CGUpdater.replaceCallSite(OldCB, NewCB);
1866  OldCB.replaceAllUsesWith(&NewCB);
1867  OldCB.eraseFromParent();
1868  }
1869 
1870  // Replace the function in the call graph (if any).
1871  CGUpdater.replaceFunctionWith(*OldFn, *NewFn);
1872 
1873  // If the old function was modified and needed to be reanalyzed, the new one
1874  // does now.
1875  if (ModifiedFns.erase(OldFn))
1876  ModifiedFns.insert(NewFn);
1877 
1878  Changed = ChangeStatus::CHANGED;
1879  }
1880 
1881  return Changed;
1882 }
1883 
1884 void InformationCache::initializeInformationCache(const Function &CF,
1885  FunctionInfo &FI) {
1886  // As we do not modify the function here we can remove the const
1887  // withouth breaking implicit assumptions. At the end of the day, we could
1888  // initialize the cache eagerly which would look the same to the users.
1889  Function &F = const_cast<Function &>(CF);
1890 
1891  // Walk all instructions to find interesting instructions that might be
1892  // queried by abstract attributes during their initialization or update.
1893  // This has to happen before we create attributes.
1894 
1895  for (Instruction &I : instructions(&F)) {
1896  bool IsInterestingOpcode = false;
1897 
1898  // To allow easy access to all instructions in a function with a given
1899  // opcode we store them in the InfoCache. As not all opcodes are interesting
1900  // to concrete attributes we only cache the ones that are as identified in
1901  // the following switch.
1902  // Note: There are no concrete attributes now so this is initially empty.
1903  switch (I.getOpcode()) {
1904  default:
1905  assert(!isa<CallBase>(&I) &&
1906  "New call base instruction type needs to be known in the "
1907  "Attributor.");
1908  break;
1909  case Instruction::Call:
1910  // Calls are interesting on their own, additionally:
1911  // For `llvm.assume` calls we also fill the KnowledgeMap as we find them.
1912  // For `must-tail` calls we remember the caller and callee.
1913  if (auto *Assume = dyn_cast<AssumeInst>(&I)) {
1914  fillMapFromAssume(*Assume, KnowledgeMap);
1915  } else if (cast<CallInst>(I).isMustTailCall()) {
1916  FI.ContainsMustTailCall = true;
1917  if (const Function *Callee = cast<CallInst>(I).getCalledFunction())
1918  getFunctionInfo(*Callee).CalledViaMustTail = true;
1919  }
1921  case Instruction::CallBr:
1922  case Instruction::Invoke:
1923  case Instruction::CleanupRet:
1924  case Instruction::CatchSwitch:
1925  case Instruction::AtomicRMW:
1926  case Instruction::AtomicCmpXchg:
1927  case Instruction::Br:
1928  case Instruction::Resume:
1929  case Instruction::Ret:
1930  case Instruction::Load:
1931  // The alignment of a pointer is interesting for loads.
1932  case Instruction::Store:
1933  // The alignment of a pointer is interesting for stores.
1934  IsInterestingOpcode = true;
1935  }
1936  if (IsInterestingOpcode) {
1937  auto *&Insts = FI.OpcodeInstMap[I.getOpcode()];
1938  if (!Insts)
1939  Insts = new (Allocator) InstructionVectorTy();
1940  Insts->push_back(&I);
1941  }
1942  if (I.mayReadOrWriteMemory())
1943  FI.RWInsts.push_back(&I);
1944  }
1945 
1946  if (F.hasFnAttribute(Attribute::AlwaysInline) &&
1948  InlineableFunctions.insert(&F);
1949 }
1950 
1952  return AG.getAnalysis<AAManager>(F);
1953 }
1954 
1955 InformationCache::FunctionInfo::~FunctionInfo() {
1956  // The instruction vectors are allocated using a BumpPtrAllocator, we need to
1957  // manually destroy them.
1958  for (auto &It : OpcodeInstMap)
1959  It.getSecond()->~InstructionVectorTy();
1960 }
1961 
1963  const AbstractAttribute &ToAA,
1964  DepClassTy DepClass) {
1965  if (DepClass == DepClassTy::NONE)
1966  return;
1967  // If we are outside of an update, thus before the actual fixpoint iteration
1968  // started (= when we create AAs), we do not track dependences because we will
1969  // put all AAs into the initial worklist anyway.
1970  if (DependenceStack.empty())
1971  return;
1972  if (FromAA.getState().isAtFixpoint())
1973  return;
1974  DependenceStack.back()->push_back({&FromAA, &ToAA, DepClass});
1975 }
1976 
1977 void Attributor::rememberDependences() {
1978  assert(!DependenceStack.empty() && "No dependences to remember!");
1979 
1980  for (DepInfo &DI : *DependenceStack.back()) {
1981  assert((DI.DepClass == DepClassTy::REQUIRED ||
1982  DI.DepClass == DepClassTy::OPTIONAL) &&
1983  "Expected required or optional dependence (1 bit)!");
1984  auto &DepAAs = const_cast<AbstractAttribute &>(*DI.FromAA).Deps;
1985  DepAAs.push_back(AbstractAttribute::DepTy(
1986  const_cast<AbstractAttribute *>(DI.ToAA), unsigned(DI.DepClass)));
1987  }
1988 }
1989 
1991  if (!VisitedFunctions.insert(&F).second)
1992  return;
1993  if (F.isDeclaration())
1994  return;
1995 
1996  // In non-module runs we need to look at the call sites of a function to
1997  // determine if it is part of a must-tail call edge. This will influence what
1998  // attributes we can derive.
1999  InformationCache::FunctionInfo &FI = InfoCache.getFunctionInfo(F);
2000  if (!isModulePass() && !FI.CalledViaMustTail) {
2001  for (const Use &U : F.uses())
2002  if (const auto *CB = dyn_cast<CallBase>(U.getUser()))
2003  if (CB->isCallee(&U) && CB->isMustTailCall())
2004  FI.CalledViaMustTail = true;
2005  }
2006 
2008 
2009  // Check for dead BasicBlocks in every function.
2010  // We need dead instruction detection because we do not want to deal with
2011  // broken IR in which SSA rules do not apply.
2012  getOrCreateAAFor<AAIsDead>(FPos);
2013 
2014  // Every function might be "will-return".
2015  getOrCreateAAFor<AAWillReturn>(FPos);
2016 
2017  // Every function might contain instructions that cause "undefined behavior".
2018  getOrCreateAAFor<AAUndefinedBehavior>(FPos);
2019 
2020  // Every function can be nounwind.
2021  getOrCreateAAFor<AANoUnwind>(FPos);
2022 
2023  // Every function might be marked "nosync"
2024  getOrCreateAAFor<AANoSync>(FPos);
2025 
2026  // Every function might be "no-free".
2027  getOrCreateAAFor<AANoFree>(FPos);
2028 
2029  // Every function might be "no-return".
2030  getOrCreateAAFor<AANoReturn>(FPos);
2031 
2032  // Every function might be "no-recurse".
2033  getOrCreateAAFor<AANoRecurse>(FPos);
2034 
2035  // Every function might be "readnone/readonly/writeonly/...".
2036  getOrCreateAAFor<AAMemoryBehavior>(FPos);
2037 
2038  // Every function can be "readnone/argmemonly/inaccessiblememonly/...".
2039  getOrCreateAAFor<AAMemoryLocation>(FPos);
2040 
2041  // Every function might be applicable for Heap-To-Stack conversion.
2042  if (EnableHeapToStack)
2043  getOrCreateAAFor<AAHeapToStack>(FPos);
2044 
2045  // Return attributes are only appropriate if the return type is non void.
2046  Type *ReturnType = F.getReturnType();
2047  if (!ReturnType->isVoidTy()) {
2048  // Argument attribute "returned" --- Create only one per function even
2049  // though it is an argument attribute.
2050  getOrCreateAAFor<AAReturnedValues>(FPos);
2051 
2052  IRPosition RetPos = IRPosition::returned(F);
2053 
2054  // Every returned value might be dead.
2055  getOrCreateAAFor<AAIsDead>(RetPos);
2056 
2057  // Every function might be simplified.
2058  getOrCreateAAFor<AAValueSimplify>(RetPos);
2059 
2060  // Every returned value might be marked noundef.
2061  getOrCreateAAFor<AANoUndef>(RetPos);
2062 
2063  if (ReturnType->isPointerTy()) {
2064 
2065  // Every function with pointer return type might be marked align.
2066  getOrCreateAAFor<AAAlign>(RetPos);
2067 
2068  // Every function with pointer return type might be marked nonnull.
2069  getOrCreateAAFor<AANonNull>(RetPos);
2070 
2071  // Every function with pointer return type might be marked noalias.
2072  getOrCreateAAFor<AANoAlias>(RetPos);
2073 
2074  // Every function with pointer return type might be marked
2075  // dereferenceable.
2076  getOrCreateAAFor<AADereferenceable>(RetPos);
2077  }
2078  }
2079 
2080  for (Argument &Arg : F.args()) {
2082 
2083  // Every argument might be simplified.
2084  getOrCreateAAFor<AAValueSimplify>(ArgPos);
2085 
2086  // Every argument might be dead.
2087  getOrCreateAAFor<AAIsDead>(ArgPos);
2088 
2089  // Every argument might be marked noundef.
2090  getOrCreateAAFor<AANoUndef>(ArgPos);
2091 
2092  if (Arg.getType()->isPointerTy()) {
2093  // Every argument with pointer type might be marked nonnull.
2094  getOrCreateAAFor<AANonNull>(ArgPos);
2095 
2096  // Every argument with pointer type might be marked noalias.
2097  getOrCreateAAFor<AANoAlias>(ArgPos);
2098 
2099  // Every argument with pointer type might be marked dereferenceable.
2100  getOrCreateAAFor<AADereferenceable>(ArgPos);
2101 
2102  // Every argument with pointer type might be marked align.
2103  getOrCreateAAFor<AAAlign>(ArgPos);
2104 
2105  // Every argument with pointer type might be marked nocapture.
2106  getOrCreateAAFor<AANoCapture>(ArgPos);
2107 
2108  // Every argument with pointer type might be marked
2109  // "readnone/readonly/writeonly/..."
2110  getOrCreateAAFor<AAMemoryBehavior>(ArgPos);
2111 
2112  // Every argument with pointer type might be marked nofree.
2113  getOrCreateAAFor<AANoFree>(ArgPos);
2114 
2115  // Every argument with pointer type might be privatizable (or promotable)
2116  getOrCreateAAFor<AAPrivatizablePtr>(ArgPos);
2117  }
2118  }
2119 
2120  auto CallSitePred = [&](Instruction &I) -> bool {
2121  auto &CB = cast<CallBase>(I);
2123 
2124  // Call sites might be dead if they do not have side effects and no live
2125  // users. The return value might be dead if there are no live users.
2126  getOrCreateAAFor<AAIsDead>(CBRetPos);
2127 
2128  Function *Callee = CB.getCalledFunction();
2129  // TODO: Even if the callee is not known now we might be able to simplify
2130  // the call/callee.
2131  if (!Callee)
2132  return true;
2133 
2134  // Skip declarations except if annotations on their call sites were
2135  // explicitly requested.
2136  if (!AnnotateDeclarationCallSites && Callee->isDeclaration() &&
2137  !Callee->hasMetadata(LLVMContext::MD_callback))
2138  return true;
2139 
2140  if (!Callee->getReturnType()->isVoidTy() && !CB.use_empty()) {
2141 
2143 
2144  // Call site return integer values might be limited by a constant range.
2145  if (Callee->getReturnType()->isIntegerTy())
2146  getOrCreateAAFor<AAValueConstantRange>(CBRetPos);
2147  }
2148 
2149  for (int I = 0, E = CB.getNumArgOperands(); I < E; ++I) {
2150 
2151  IRPosition CBArgPos = IRPosition::callsite_argument(CB, I);
2152 
2153  // Every call site argument might be dead.
2154  getOrCreateAAFor<AAIsDead>(CBArgPos);
2155 
2156  // Call site argument might be simplified.
2157  getOrCreateAAFor<AAValueSimplify>(CBArgPos);
2158 
2159  // Every call site argument might be marked "noundef".
2160  getOrCreateAAFor<AANoUndef>(CBArgPos);
2161 
2162  if (!CB.getArgOperand(I)->getType()->isPointerTy())
2163  continue;
2164 
2165  // Call site argument attribute "non-null".
2166  getOrCreateAAFor<AANonNull>(CBArgPos);
2167 
2168  // Call site argument attribute "nocapture".
2169  getOrCreateAAFor<AANoCapture>(CBArgPos);
2170 
2171  // Call site argument attribute "no-alias".
2172  getOrCreateAAFor<AANoAlias>(CBArgPos);
2173 
2174  // Call site argument attribute "dereferenceable".
2175  getOrCreateAAFor<AADereferenceable>(CBArgPos);
2176 
2177  // Call site argument attribute "align".
2178  getOrCreateAAFor<AAAlign>(CBArgPos);
2179 
2180  // Call site argument attribute
2181  // "readnone/readonly/writeonly/..."
2182  getOrCreateAAFor<AAMemoryBehavior>(CBArgPos);
2183 
2184  // Call site argument attribute "nofree".
2185  getOrCreateAAFor<AANoFree>(CBArgPos);
2186  }
2187  return true;
2188  };
2189 
2190  auto &OpcodeInstMap = InfoCache.getOpcodeInstMapForFunction(F);
2191  bool Success;
2193  nullptr, OpcodeInstMap, CallSitePred, nullptr, nullptr,
2194  {(unsigned)Instruction::Invoke, (unsigned)Instruction::CallBr,
2195  (unsigned)Instruction::Call});
2196  (void)Success;
2197  assert(Success && "Expected the check call to be successful!");
2198 
2199  auto LoadStorePred = [&](Instruction &I) -> bool {
2200  if (isa<LoadInst>(I))
2201  getOrCreateAAFor<AAAlign>(
2202  IRPosition::value(*cast<LoadInst>(I).getPointerOperand()));
2203  else
2204  getOrCreateAAFor<AAAlign>(
2205  IRPosition::value(*cast<StoreInst>(I).getPointerOperand()));
2206  return true;
2207  };
2209  nullptr, OpcodeInstMap, LoadStorePred, nullptr, nullptr,
2210  {(unsigned)Instruction::Load, (unsigned)Instruction::Store});
2211  (void)Success;
2212  assert(Success && "Expected the check call to be successful!");
2213 }
2214 
2215 /// Helpers to ease debugging through output streams and print calls.
2216 ///
2217 ///{
2219  return OS << (S == ChangeStatus::CHANGED ? "changed" : "unchanged");
2220 }
2221 
2223  switch (AP) {
2225  return OS << "inv";
2226  case IRPosition::IRP_FLOAT:
2227  return OS << "flt";
2229  return OS << "fn_ret";
2231  return OS << "cs_ret";
2233  return OS << "fn";
2235  return OS << "cs";
2237  return OS << "arg";
2239  return OS << "cs_arg";
2240  }
2241  llvm_unreachable("Unknown attribute position!");
2242 }
2243 
2245  const Value &AV = Pos.getAssociatedValue();
2246  OS << "{" << Pos.getPositionKind() << ":" << AV.getName() << " ["
2247  << Pos.getAnchorValue().getName() << "@" << Pos.getCallSiteArgNo() << "]";
2248 
2249  if (Pos.hasCallBaseContext())
2250  OS << "[cb_context:" << *Pos.getCallBaseContext() << "]";
2251  return OS << "}";
2252 }
2253 
2255  OS << "range-state(" << S.getBitWidth() << ")<";
2256  S.getKnown().print(OS);
2257  OS << " / ";
2258  S.getAssumed().print(OS);
2259  OS << ">";
2260 
2261  return OS << static_cast<const AbstractState &>(S);
2262 }
2263 
2265  return OS << (!S.isValidState() ? "top" : (S.isAtFixpoint() ? "fix" : ""));
2266 }
2267 
2269  AA.print(OS);
2270  return OS;
2271 }
2272 
2275  OS << "set-state(< {";
2276  if (!S.isValidState())
2277  OS << "full-set";
2278  else {
2279  for (auto &it : S.getAssumedSet())
2280  OS << it << ", ";
2281  if (S.undefIsContained())
2282  OS << "undef ";
2283  }
2284  OS << "} >)";
2285 
2286  return OS;
2287 }
2288 
2290  OS << "[";
2291  OS << getName();
2292  OS << "] for CtxI ";
2293 
2294  if (auto *I = getCtxI()) {
2295  OS << "'";
2296  I->print(OS);
2297  OS << "'";
2298  } else
2299  OS << "<<null inst>>";
2300 
2301  OS << " at position " << getIRPosition() << " with state " << getAsStr()
2302  << '\n';
2303 }
2304 
2306  print(OS);
2307 
2308  for (const auto &DepAA : Deps) {
2309  auto *AA = DepAA.getPointer();
2310  OS << " updates ";
2311  AA->print(OS);
2312  }
2313 
2314  OS << '\n';
2315 }
2316 ///}
2317 
2318 /// ----------------------------------------------------------------------------
2319 /// Pass (Manager) Boilerplate
2320 /// ----------------------------------------------------------------------------
2321 
2323  SetVector<Function *> &Functions,
2324  AnalysisGetter &AG,
2325  CallGraphUpdater &CGUpdater,
2326  bool DeleteFns) {
2327  if (Functions.empty())
2328  return false;
2329 
2330  LLVM_DEBUG(dbgs() << "[Attributor] Run on module with " << Functions.size()
2331  << " functions.\n");
2332 
2333  // Create an Attributor and initially empty information cache that is filled
2334  // while we identify default attribute opportunities.
2335  Attributor A(Functions, InfoCache, CGUpdater, /* Allowed */ nullptr,
2336  DeleteFns);
2337 
2338  // Create shallow wrappers for all functions that are not IPO amendable
2340  for (Function *F : Functions)
2341  if (!A.isFunctionIPOAmendable(*F))
2343 
2344  // Internalize non-exact functions
2345  // TODO: for now we eagerly internalize functions without calculating the
2346  // cost, we need a cost interface to determine whether internalizing
2347  // a function is "benefitial"
2348  if (AllowDeepWrapper) {
2349  unsigned FunSize = Functions.size();
2350  for (unsigned u = 0; u < FunSize; u++) {
2351  Function *F = Functions[u];
2352  if (!F->isDeclaration() && !F->isDefinitionExact() && F->getNumUses() &&
2353  !GlobalValue::isInterposableLinkage(F->getLinkage())) {
2354  Function *NewF = internalizeFunction(*F);
2355  Functions.insert(NewF);
2356 
2357  // Update call graph
2358  CGUpdater.replaceFunctionWith(*F, *NewF);
2359  for (const Use &U : NewF->uses())
2360  if (CallBase *CB = dyn_cast<CallBase>(U.getUser())) {
2361  auto *CallerF = CB->getCaller();
2362  CGUpdater.reanalyzeFunction(*CallerF);
2363  }
2364  }
2365  }
2366  }
2367 
2368  for (Function *F : Functions) {
2369  if (F->hasExactDefinition())
2370  NumFnWithExactDefinition++;
2371  else
2372  NumFnWithoutExactDefinition++;
2373 
2374  // We look at internal functions only on-demand but if any use is not a
2375  // direct call or outside the current set of analyzed functions, we have
2376  // to do it eagerly.
2377  if (F->hasLocalLinkage()) {
2378  if (llvm::all_of(F->uses(), [&Functions](const Use &U) {
2379  const auto *CB = dyn_cast<CallBase>(U.getUser());
2380  return CB && CB->isCallee(&U) &&
2381  Functions.count(const_cast<Function *>(CB->getCaller()));
2382  }))
2383  continue;
2384  }
2385 
2386  // Populate the Attributor with abstract attribute opportunities in the
2387  // function and the information cache with IR information.
2388  A.identifyDefaultAbstractAttributes(*F);
2389  }
2390 
2391  ChangeStatus Changed = A.run();
2392 
2393  LLVM_DEBUG(dbgs() << "[Attributor] Done with " << Functions.size()
2394  << " functions, result: " << Changed << ".\n");
2395  return Changed == ChangeStatus::CHANGED;
2396 }
2397 
2398 void AADepGraph::viewGraph() { llvm::ViewGraph(this, "Dependency Graph"); }
2399 
2401  static std::atomic<int> CallTimes;
2402  std::string Prefix;
2403 
2404  if (!DepGraphDotFileNamePrefix.empty())
2406  else
2407  Prefix = "dep_graph";
2408  std::string Filename =
2409  Prefix + "_" + std::to_string(CallTimes.load()) + ".dot";
2410 
2411  outs() << "Dependency graph dump to " << Filename << ".\n";
2412 
2413  std::error_code EC;
2414 
2416  if (!EC)
2417  llvm::WriteGraph(File, this);
2418 
2419  CallTimes++;
2420 }
2421 
2423  for (auto DepAA : SyntheticRoot.Deps)
2424  cast<AbstractAttribute>(DepAA.getPointer())->printWithDeps(outs());
2425 }
2426 
2430  AnalysisGetter AG(FAM);
2431 
2432  SetVector<Function *> Functions;
2433  for (Function &F : M)
2434  Functions.insert(&F);
2435 
2436  CallGraphUpdater CGUpdater;
2438  InformationCache InfoCache(M, AG, Allocator, /* CGSCC */ nullptr);
2439  if (runAttributorOnFunctions(InfoCache, Functions, AG, CGUpdater,
2440  /* DeleteFns */ true)) {
2441  // FIXME: Think about passes we will preserve and add them here.
2442  return PreservedAnalyses::none();
2443  }
2444  return PreservedAnalyses::all();
2445 }
2446 
2449  LazyCallGraph &CG,
2450  CGSCCUpdateResult &UR) {
2452  AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C, CG).getManager();
2453  AnalysisGetter AG(FAM);
2454 
2455  SetVector<Function *> Functions;
2456  for (LazyCallGraph::Node &N : C)
2457  Functions.insert(&N.getFunction());
2458 
2459  if (Functions.empty())
2460  return PreservedAnalyses::all();
2461 
2462  Module &M = *Functions.back()->getParent();
2463  CallGraphUpdater CGUpdater;
2464  CGUpdater.initialize(CG, C, AM, UR);
2466  InformationCache InfoCache(M, AG, Allocator, /* CGSCC */ &Functions);
2467  if (runAttributorOnFunctions(InfoCache, Functions, AG, CGUpdater,
2468  /* DeleteFns */ false)) {
2469  // FIXME: Think about passes we will preserve and add them here.
2470  PreservedAnalyses PA;
2472  return PA;
2473  }
2474  return PreservedAnalyses::all();
2475 }
2476 
2477 namespace llvm {
2478 
2479 template <> struct GraphTraits<AADepGraphNode *> {
2483 
2484  static NodeRef getEntryNode(AADepGraphNode *DGN) { return DGN; }
2485  static NodeRef DepGetVal(DepTy &DT) { return DT.getPointer(); }
2486 
2487  using ChildIteratorType =
2490 
2491  static ChildIteratorType child_begin(NodeRef N) { return N->child_begin(); }
2492 
2493  static ChildIteratorType child_end(NodeRef N) { return N->child_end(); }
2494 };
2495 
2496 template <>
2498  static NodeRef getEntryNode(AADepGraph *DG) { return DG->GetEntryNode(); }
2499 
2500  using nodes_iterator =
2502 
2503  static nodes_iterator nodes_begin(AADepGraph *DG) { return DG->begin(); }
2504 
2505  static nodes_iterator nodes_end(AADepGraph *DG) { return DG->end(); }
2506 };
2507 
2508 template <> struct DOTGraphTraits<AADepGraph *> : public DefaultDOTGraphTraits {
2510 
2511  static std::string getNodeLabel(const AADepGraphNode *Node,
2512  const AADepGraph *DG) {
2513  std::string AAString;
2514  raw_string_ostream O(AAString);
2515  Node->print(O);
2516  return AAString;
2517  }
2518 };
2519 
2520 } // end namespace llvm
2521 
2522 namespace {
2523 
2524 struct AttributorLegacyPass : public ModulePass {
2525  static char ID;
2526 
2527  AttributorLegacyPass() : ModulePass(ID) {
2529  }
2530 
2531  bool runOnModule(Module &M) override {
2532  if (skipModule(M))
2533  return false;
2534 
2535  AnalysisGetter AG;
2536  SetVector<Function *> Functions;
2537  for (Function &F : M)
2538  Functions.insert(&F);
2539 
2540  CallGraphUpdater CGUpdater;
2542  InformationCache InfoCache(M, AG, Allocator, /* CGSCC */ nullptr);
2543  return runAttributorOnFunctions(InfoCache, Functions, AG, CGUpdater,
2544  /* DeleteFns*/ true);
2545  }
2546 
2547  void getAnalysisUsage(AnalysisUsage &AU) const override {
2548  // FIXME: Think about passes we will preserve and add them here.
2550  }
2551 };
2552 
2553 struct AttributorCGSCCLegacyPass : public CallGraphSCCPass {
2554  static char ID;
2555 
2556  AttributorCGSCCLegacyPass() : CallGraphSCCPass(ID) {
2558  }
2559 
2560  bool runOnSCC(CallGraphSCC &SCC) override {
2561  if (skipSCC(SCC))
2562  return false;
2563 
2564  SetVector<Function *> Functions;
2565  for (CallGraphNode *CGN : SCC)
2566  if (Function *Fn = CGN->getFunction())
2567  if (!Fn->isDeclaration())
2568  Functions.insert(Fn);
2569 
2570  if (Functions.empty())
2571  return false;
2572 
2573  AnalysisGetter AG;
2574  CallGraph &CG = const_cast<CallGraph &>(SCC.getCallGraph());
2575  CallGraphUpdater CGUpdater;
2576  CGUpdater.initialize(CG, SCC);
2577  Module &M = *Functions.back()->getParent();
2579  InformationCache InfoCache(M, AG, Allocator, /* CGSCC */ &Functions);
2580  return runAttributorOnFunctions(InfoCache, Functions, AG, CGUpdater,
2581  /* DeleteFns */ false);
2582  }
2583 
2584  void getAnalysisUsage(AnalysisUsage &AU) const override {
2585  // FIXME: Think about passes we will preserve and add them here.
2588  }
2589 };
2590 
2591 } // end anonymous namespace
2592 
2593 Pass *llvm::createAttributorLegacyPass() { return new AttributorLegacyPass(); }
2595  return new AttributorCGSCCLegacyPass();
2596 }
2597 
2598 char AttributorLegacyPass::ID = 0;
2600 
2601 INITIALIZE_PASS_BEGIN(AttributorLegacyPass, "attributor",
2602  "Deduce and propagate attributes", false, false)
2604 INITIALIZE_PASS_END(AttributorLegacyPass, "attributor",
2606 INITIALIZE_PASS_BEGIN(AttributorCGSCCLegacyPass, "attributor-cgscc",
2607  "Deduce and propagate attributes (CGSCC pass)", false,
2608  false)
2611 INITIALIZE_PASS_END(AttributorCGSCCLegacyPass, "attributor-cgscc",
2612  "Deduce and propagate attributes (CGSCC pass)", false,
2613  false)
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm::CallGraphUpdater
Wrapper to unify "old style" CallGraph and "new style" LazyCallGraph.
Definition: CallGraphUpdater.h:28
llvm::EngineKind::Kind
Kind
Definition: ExecutionEngine.h:524
llvm::GraphTraits< AADepGraphNode * >::getEntryNode
static NodeRef getEntryNode(AADepGraphNode *DGN)
Definition: Attributor.cpp:2484
llvm::RecursivelyDeleteTriviallyDeadInstructions
bool RecursivelyDeleteTriviallyDeadInstructions(Value *V, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr, std::function< void(Value *)> AboutToDeleteCallback=std::function< void(Value *)>())
If the specified value is a trivially dead instruction, delete it.
Definition: Local.cpp:486
llvm::Argument
This class represents an incoming formal argument to a Function.
Definition: Argument.h:29
llvm::AAManager
A manager for alias analyses.
Definition: AliasAnalysis.h:1221
llvm::IRPosition::function
static const IRPosition function(const Function &F, const CallBaseContext *CBContext=nullptr)
Create a position describing the function scope of F.
Definition: Attributor.h:266
Attrs
Function Attrs
Definition: README_ALTIVEC.txt:215
getName
static StringRef getName(Value *V)
Definition: ProvenanceAnalysisEvaluator.cpp:42
llvm::initializeAttributorLegacyPassPass
void initializeAttributorLegacyPassPass(PassRegistry &)
llvm
Definition: AllocatorList.h:23
llvm::Attribute::isEnumAttribute
bool isEnumAttribute() const
Return true if the attribute is an Attribute::AttrKind type.
Definition: Attributes.cpp:260
llvm::GraphTraits< AADepGraphNode * >::child_end
static ChildIteratorType child_end(NodeRef N)
Definition: Attributor.cpp:2493
llvm::CallBase::getOperandBundlesAsDefs
void getOperandBundlesAsDefs(SmallVectorImpl< OperandBundleDef > &Defs) const
Return the list of operand bundles attached to this instruction as a vector of OperandBundleDefs.
Definition: Instructions.cpp:361
FunctionSeedAllowList
static cl::list< std::string > FunctionSeedAllowList("attributor-function-seed-allow-list", cl::Hidden, cl::desc("Comma seperated list of function names that are " "allowed to be seeded."), cl::ZeroOrMore, cl::CommaSeparated)
llvm::InvokeInst::Create
static InvokeInst * Create(FunctionType *Ty, Value *Func, BasicBlock *IfNormal, BasicBlock *IfException, ArrayRef< Value * > Args, const Twine &NameStr, Instruction *InsertBefore=nullptr)
Definition: Instructions.h:3730
llvm::Function::args
iterator_range< arg_iterator > args()
Definition: Function.h:807
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::TimeTraceScope
The TimeTraceScope is a helper class to call the begin and end functions of the time trace profiler.
Definition: TimeProfiler.h:65
llvm::CallInst::setTailCall
void setTailCall(bool IsTc=true)
Definition: Instructions.h:1657
llvm::ReturnInst
Return a value (possibly void), from a function.
Definition: Instructions.h:2923
llvm::SmallPtrSetImpl::erase
bool erase(PtrType Ptr)
erase - If the set contains the specified pointer, remove it and return true, otherwise return false.
Definition: SmallPtrSet.h:378
NoFolder.h
llvm::IRPosition::getCallBaseContext
const CallBaseContext * getCallBaseContext() const
Get the call base context from the position.
Definition: Attributor.h:560
FileSystem.h
llvm::IRPosition::getAssociatedFunction
Function * getAssociatedFunction() const
Return the associated function, if any.
Definition: Attributor.h:354
llvm::AbstractCallSite::getCallbackUses
static void getCallbackUses(const CallBase &CB, SmallVectorImpl< const Use * > &CallbackUses)
Add operand uses of CB that represent callback uses into CallbackUses.
Definition: AbstractCallSite.cpp:35
llvm::AttributeList::hasAttrSomewhere
bool hasAttrSomewhere(Attribute::AttrKind Kind, unsigned *Index=nullptr) const
Return true if the specified attribute is set for at least one parameter or for the return value.
Definition: Attributes.cpp:1592
llvm::GraphTraits< AADepGraph * >::nodes_begin
static nodes_iterator nodes_begin(AADepGraph *DG)
Definition: Attributor.cpp:2503
llvm::ModulePass
ModulePass class - This class is used to implement unstructured interprocedural optimizations and ana...
Definition: Pass.h:238
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:785
llvm::cl::Prefix
@ Prefix
Definition: CommandLine.h:161
llvm::Function::getBasicBlockList
const BasicBlockListType & getBasicBlockList() const
Get the underlying elements of the Function...
Definition: Function.h:745
llvm::Attributor::ArgumentReplacementInfo
Helper struct used in the communication between an abstract attribute (AA) that wants to change the s...
Definition: Attributor.h:1434
EnableHeapToStack
static cl::opt< bool > EnableHeapToStack("enable-heap-to-stack-conversion", cl::init(true), cl::Hidden)
llvm::GlobalValue::getLinkage
LinkageTypes getLinkage() const
Definition: GlobalValue.h:461
MemorySSAUpdater.h
llvm::Function
Definition: Function.h:61
getFunction
static Function * getFunction(Constant *C)
Definition: Evaluator.cpp:253
llvm::cl::location
LocationClass< Ty > location(Ty &L)
Definition: CommandLine.h:456
llvm::Attribute
Definition: Attributes.h:52
llvm::DenseMapBase::lookup
ValueT lookup(const_arg_type_t< KeyT > Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
Definition: DenseMap.h:197
llvm::CallGraphUpdater::replaceCallSite
bool replaceCallSite(CallBase &OldCS, CallBase &NewCS)
Replace OldCS with the new call site NewCS.
Definition: CallGraphUpdater.cpp:143
llvm::AbstractAttribute::update
ChangeStatus update(Attributor &A)
Hook for the Attributor to trigger an update of the internal state.
Definition: Attributor.cpp:258
llvm::raw_string_ostream
A raw_ostream that writes to an std::string.
Definition: raw_ostream.h:614
llvm::SetVector::size
size_type size() const
Determine the number of elements in the SetVector.
Definition: SetVector.h:77
it
Reference model for inliner Oz decision policy Note this model is also referenced by test Transforms Inline ML tests if replacing it
Definition: README.txt:3
llvm::Attribute::get
static Attribute get(LLVMContext &Context, AttrKind Kind, uint64_t Val=0)
Return a uniquified Attribute object.
Definition: Attributes.cpp:92
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
Statistic.h
Wrapper
amdgpu aa AMDGPU Address space based Alias Analysis Wrapper
Definition: AMDGPUAliasAnalysis.cpp:30
llvm::IRPosition::value
static const IRPosition value(const Value &V, const CallBaseContext *CBContext=nullptr)
Create a position describing the value of V.
Definition: Attributor.h:255
llvm::Function::getSubprogram
DISubprogram * getSubprogram() const
Get the attached subprogram.
Definition: Metadata.cpp:1526
llvm::GraphTraits< AADepGraph * >::getEntryNode
static NodeRef getEntryNode(AADepGraph *DG)
Definition: Attributor.cpp:2498
llvm::cl::CommaSeparated
@ CommaSeparated
Definition: CommandLine.h:166
llvm::SPII::Load
@ Load
Definition: SparcInstrInfo.h:32
llvm::Use::get
Value * get() const
Definition: Use.h:67
llvm::AbstractAttribute::getName
virtual const std::string getName() const =0
This function should return the name of the AbstractAttribute.
llvm::FunctionType::get
static FunctionType * get(Type *Result, ArrayRef< Type * > Params, bool isVarArg)
This static method is the primary way of constructing a FunctionType.
Definition: Type.cpp:321
llvm::SubsumingPositionIterator::SubsumingPositionIterator
SubsumingPositionIterator(const IRPosition &IRP)
Definition: Attributor.cpp:335
ValueTracking.h
Local.h
llvm::AttributeList::get
static AttributeList get(LLVMContext &C, ArrayRef< std::pair< unsigned, Attribute >> Attrs)
Create an AttributeList with the specified parameters in it.
Definition: Attributes.cpp:1203
llvm::CallGraph
The basic data container for the call graph of a Module of IR.
Definition: CallGraph.h:73
llvm::IRPosition::getAttrs
void getAttrs(ArrayRef< Attribute::AttrKind > AKs, SmallVectorImpl< Attribute > &Attrs, bool IgnoreSubsumingPositions=false, Attributor *A=nullptr) const
Return the attributes of any kind in AKs existing in the IR at a position that will affect this one.
Definition: Attributor.cpp:421
llvm::verifyFunction
bool verifyFunction(const Function &F, raw_ostream *OS=nullptr)
Check a function for errors, useful for use when debugging a pass.
Definition: Verifier.cpp:5741
llvm::AADepGraph::dumpGraph
void dumpGraph()
Dump graph to file.
Definition: Attributor.cpp:2400
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:140
llvm::Attributor::checkForAllUses
bool checkForAllUses(function_ref< bool(const Use &, bool &)> Pred, const AbstractAttribute &QueryingAA, const Value &V, DepClassTy LivenessDepClass=DepClassTy::OPTIONAL)
Check Pred on all (transitive) uses of V.
Definition: Attributor.cpp:695
llvm::PreservedAnalyses::none
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
Definition: PassManager.h:158
llvm::Function::getContext
LLVMContext & getContext() const
getContext - Return a reference to the LLVMContext associated with this function.
Definition: Function.cpp:316
llvm::Function::arg_size
size_t arg_size() const
Definition: Function.h:816
llvm::AbstractState::indicatePessimisticFixpoint
virtual ChangeStatus indicatePessimisticFixpoint()=0
Indicate that the abstract state should converge to the pessimistic state.
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:46
llvm::AttributeList
Definition: Attributes.h:385
llvm::CallBase::getAttributes
AttributeList getAttributes() const
Return the parameter attributes for this call.
Definition: InstrTypes.h:1472
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(AttributorLegacyPass, "attributor", "Deduce and propagate attributes", false, false) INITIALIZE_PASS_END(AttributorLegacyPass
llvm::InformationCache
Data structure to hold cached (LLVM-IR) information.
Definition: Attributor.h:792
llvm::CallBase::isMustTailCall
bool isMustTailCall() const
Tests if this call site must be tail call optimized.
Definition: Instructions.cpp:294
llvm::Optional
Definition: APInt.h:33
llvm::isInlineViable
InlineResult isInlineViable(Function &Callee)
Minimal filter to detect invalid constructs for inlining.
Definition: InlineCost.cpp:2647
llvm::InformationCache::getAAResultsForFunction
AAResults * getAAResultsForFunction(const Function &F)
Return AliasAnalysis Result for function F.
Definition: Attributor.cpp:1951
llvm::GlobalValue::DefaultVisibility
@ DefaultVisibility
The GV is visible.
Definition: GlobalValue.h:63
llvm::mapped_iterator
Definition: STLExtras.h:286
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:449
llvm::AADepGraph::SyntheticRoot
AADepGraphNode SyntheticRoot
There is no root node for the dependency graph.
Definition: Attributor.h:207
llvm::CloneFunctionChangeType::LocalChangesOnly
@ LocalChangesOnly
llvm::AbstractAttribute::manifest
virtual ChangeStatus manifest(Attributor &A)
Hook for the Attributor to trigger the manifestation of the information represented by the abstract a...
Definition: Attributor.h:2386
llvm::Attributor::recordDependence
void recordDependence(const AbstractAttribute &FromAA, const AbstractAttribute &ToAA, DepClassTy DepClass)
Explicitly record a dependence from FromAA to ToAA, that is if FromAA changes ToAA should be updated ...
Definition: Attributor.cpp:1962
isMustTailCall
static bool isMustTailCall(Value *V)
Definition: InstructionCombining.cpp:2841
llvm::Attributor::run
ChangeStatus run()
Run the analyses until a fixpoint is reached or enforced (timeout).
Definition: Attributor.cpp:1421
llvm::errs
raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
Definition: raw_ostream.cpp:892
llvm::IRPosition::IRP_ARGUMENT
@ IRP_ARGUMENT
An attribute for a function argument.
Definition: Attributor.h:245
llvm::AADepGraphNode::end
aaiterator end()
Definition: Attributor.h:179
llvm::Attributor::~Attributor
~Attributor()
Definition: Attributor.cpp:575
LazyValueInfo.h
llvm::IRPosition::IRP_RETURNED
@ IRP_RETURNED
An attribute for the function return value.
Definition: Attributor.h:241
llvm::Instruction::copyMetadata
void copyMetadata(const Instruction &SrcInst, ArrayRef< unsigned > WL=ArrayRef< unsigned >())
Copy metadata from SrcInst to this instruction.
Definition: Instruction.cpp:800
attributes
Deduce and propagate attributes
Definition: Attributor.cpp:2605
llvm::MipsISD::Ret
@ Ret
Definition: MipsISelLowering.h:116
llvm::ViewGraph
void ViewGraph(const GraphType &G, const Twine &Name, bool ShortNames=false, const Twine &Title="", GraphProgram::Name Program=GraphProgram::DOT)
ViewGraph - Emit a dot graph, run 'dot', run gv on the postscript file, then cleanup.
Definition: GraphWriter.h:375
llvm::createAttributorLegacyPass
Pass * createAttributorLegacyPass()
Definition: Attributor.cpp:2593
llvm::Attributor::checkForAllReturnedValues
bool checkForAllReturnedValues(function_ref< bool(Value &)> Pred, const AbstractAttribute &QueryingAA)
Check Pred on all values potentially returned by the function associated with QueryingAA.
Definition: Attributor.cpp:895
llvm::AbstractCallSite
AbstractCallSite.
Definition: AbstractCallSite.h:50
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:635
and
We currently generate a but we really shouldn eax ecx xorl edx divl ecx eax divl ecx movl eax ret A similar code sequence works for division We currently compile i32 v2 eax eax jo LBB1_2 and
Definition: README.txt:1271
llvm::IRPosition::hasCallBaseContext
bool hasCallBaseContext() const
Check if the position has any call base context.
Definition: Attributor.h:563
llvm::AbstractCallSite::getNumArgOperands
unsigned getNumArgOperands() const
Return the number of parameters of the callee.
Definition: AbstractCallSite.h:154
llvm::AAIsDead::mayCatchAsynchronousExceptions
static bool mayCatchAsynchronousExceptions(const Function &F)
Determine if F might catch asynchronous exceptions.
Definition: Attributor.h:2855
llvm::InformationCache::InstructionVectorTy
SmallVector< Instruction *, 8 > InstructionVectorTy
A vector type to hold instructions.
Definition: Attributor.h:884
llvm::IRPosition::IRP_FLOAT
@ IRP_FLOAT
A position that is not associated with a spot suitable for attributes.
Definition: Attributor.h:239
INITIALIZE_PASS_END
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
Definition: RegBankSelect.cpp:69
llvm::GlobalValue::setDSOLocal
void setDSOLocal(bool Local)
Definition: GlobalValue.h:280
MustExecute.h
llvm::MaxInitializationChainLength
unsigned MaxInitializationChainLength
The value passed to the line option that defines the maximal initialization chain length.
Definition: Attributor.cpp:87
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:122
AnnotateDeclarationCallSites
static cl::opt< bool > AnnotateDeclarationCallSites("attributor-annotate-decl-cs", cl::Hidden, cl::desc("Annotate call sites of function declarations."), cl::init(false))
llvm::IRAttributeManifest::manifestAttrs
static ChangeStatus manifestAttrs(Attributor &A, const IRPosition &IRP, const ArrayRef< Attribute > &DeducedAttrs)
Definition: Attributor.cpp:274
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::FunctionType::isVarArg
bool isVarArg() const
Definition: DerivedTypes.h:122
Uses
SmallPtrSet< MachineInstr *, 2 > Uses
Definition: ARMLowOverheadLoops.cpp:583
DumpDepGraph
static cl::opt< bool > DumpDepGraph("attributor-dump-dep-graph", cl::Hidden, cl::desc("Dump the dependency graph to dot files."), cl::init(false))
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::AttributeList::hasAttribute
bool hasAttribute(unsigned Index, Attribute::AttrKind Kind) const
Return true if the attribute exists at the given index.
Definition: Attributes.cpp:1566
llvm::Optional::hasValue
constexpr bool hasValue() const
Definition: Optional.h:286
PointerIntPair.h
llvm::createAttributorCGSCCLegacyPass
Pass * createAttributorCGSCCLegacyPass()
Definition: Attributor.cpp:2594
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
GraphTraits.h
llvm::AbstractAttribute::trackStatistics
virtual void trackStatistics() const =0
Hook to enable custom statistic tracking, called after manifest that resulted in a change if statisti...
Arg
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
Definition: AMDGPULibCalls.cpp:205
CommandLine.h
llvm::Attribute::getValueAsInt
uint64_t getValueAsInt() const
Return the attribute's value as an integer.
Definition: Attributes.cpp:283
llvm::DenseMapInfo
Definition: APInt.h:34
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:1505
addIfNotExistent
static bool addIfNotExistent(LLVMContext &Ctx, const Attribute &Attr, AttributeList &Attrs, int AttrIdx)
Return true if the information provided by Attr was added to the attribute list Attrs.
Definition: Attributor.cpp:172
llvm::AreStatisticsEnabled
bool AreStatisticsEnabled()
Check if statistics are enabled.
Definition: Statistic.cpp:131
llvm::GraphTraits< AADepGraphNode * >::child_begin
static ChildIteratorType child_begin(NodeRef N)
Definition: Attributor.cpp:2491
GlobalValue.h
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:421
llvm::Attributor::checkForAllCallSites
bool checkForAllCallSites(function_ref< bool(AbstractCallSite)> Pred, const AbstractAttribute &QueryingAA, bool RequireAllCallSites, bool &AllCallSitesKnown)
Check Pred on all function call sites.
Definition: Attributor.cpp:760
llvm::GlobalValue::isDeclaration
bool isDeclaration() const
Return true if the primary definition of this global value is outside of the current translation unit...
Definition: Globals.cpp:228
llvm::outs
raw_fd_ostream & outs()
This returns a reference to a raw_fd_ostream for standard output.
Definition: raw_ostream.cpp:884
llvm::AAResults
Definition: AliasAnalysis.h:456
llvm::ChangeStatus
ChangeStatus
{
Definition: Attributor.h:139
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::SmallVectorImpl::append
void append(in_iter in_start, in_iter in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:648
llvm::AbstractAttribute::getState
virtual StateType & getState()=0
Return the internal abstract state for inspection.
llvm::User
Definition: User.h:44
AllowShallowWrappers
static cl::opt< bool > AllowShallowWrappers("attributor-allow-shallow-wrappers", cl::Hidden, cl::desc("Allow the Attributor to create shallow " "wrappers for non-exact definitions."), cl::init(false))
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::ARM_PROC::A
@ A
Definition: ARMBaseInfo.h:34
llvm::AbstractAttribute::printWithDeps
virtual void printWithDeps(raw_ostream &OS) const
Definition: Attributor.cpp:2305
llvm::AttributeList::getFnAttributes
AttributeSet getFnAttributes() const
The function attributes are returned.
Definition: Attributes.cpp:1562
llvm::CallBase::setAttributes
void setAttributes(AttributeList A)
Set the parameter attributes for this call.
Definition: InstrTypes.h:1476
llvm::CallInst::Create
static CallInst * Create(FunctionType *Ty, Value *F, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Definition: Instructions.h:1493
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
AllowDeepWrapper
static cl::opt< bool > AllowDeepWrapper("attributor-allow-deep-wrappers", cl::Hidden, cl::desc("Allow the Attributor to use IP information " "derived from non-exact functions via cloning"), cl::init(false))
llvm::AADepGraph::GetEntryNode
AADepGraphNode * GetEntryNode()
Definition: Attributor.h:208
llvm::AADepGraph::print
void print()
Print dependency graph.
Definition: Attributor.cpp:2422
llvm::AttributeList::getParamAttributes
AttributeSet getParamAttributes(unsigned ArgNo) const
The attributes for the argument or parameter at the given index are returned.
Definition: Attributes.cpp:1554
llvm::Value::uses
iterator_range< use_iterator > uses()
Definition: Value.h:389
false
Definition: StackSlotColoring.cpp:142
llvm::AbstractAttribute::~AbstractAttribute
virtual ~AbstractAttribute()
Virtual destructor.
Definition: Attributor.h:2326
DepGraphDotFileNamePrefix
static cl::opt< std::string > DepGraphDotFileNamePrefix("attributor-depgraph-dot-filename-prefix", cl::Hidden, cl::desc("The prefix used for the CallGraph dot file names."))
pass
modulo schedule Modulo Schedule test pass
Definition: ModuloSchedule.cpp:2126
llvm::IRPosition::hasAttr
bool hasAttr(ArrayRef< Attribute::AttrKind > AKs, bool IgnoreSubsumingPositions=false, Attributor *A=nullptr) const
TODO: Figure out if the attribute related helper functions should live here or somewhere else.
Definition: Attributor.cpp:401
llvm::AbstractState::isValidState
virtual bool isValidState() const =0
Return if this abstract state is in a valid state.
llvm::Instruction
Definition: Instruction.h:45
llvm::DebugCounter::shouldExecute
static bool shouldExecute(unsigned CounterName)
Definition: DebugCounter.h:74
llvm::IRPosition::getPositionKind
Kind getPositionKind() const
Return the associated position kind.
Definition: Attributor.h:463
llvm::IRPosition::getCtxI
Instruction * getCtxI() const
Return the context instruction, if any.
Definition: Attributor.h:395
llvm::DepClassTy::OPTIONAL
@ OPTIONAL
The target may be valid if the source is not.
llvm::AttributeList::getAttributes
AttributeSet getAttributes(unsigned Index) const
The attributes for the specified index are returned.
Definition: Attributes.cpp:1664
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
llvm::Function::copyAttributesFrom
void copyAttributesFrom(const Function *Src)
copyAttributesFrom - copy all additional attributes (those not needed to create a Function) from the ...
Definition: Function.cpp:647
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:50
llvm::Function::removeParamAttr
void removeParamAttr(unsigned ArgNo, Attribute::AttrKind Kind)
removes the attribute from the list of attributes.
Definition: Function.cpp:558
llvm::GlobalObject::addMetadata
void addMetadata(unsigned KindID, MDNode &MD)
Add a metadata attachment.
Definition: Metadata.cpp:1262
llvm::InlineResult::isSuccess
bool isSuccess() const
Definition: InlineCost.h:143
llvm::IntegerRangeState
State for an integer range.
Definition: Attributor.h:2090
llvm::SmallVectorImpl::resize
void resize(size_type N)
Definition: SmallVector.h:606
runAttributorOnFunctions
static bool runAttributorOnFunctions(InformationCache &InfoCache, SetVector< Function * > &Functions, AnalysisGetter &AG, CallGraphUpdater &CGUpdater, bool DeleteFns)
}
Definition: Attributor.cpp:2322
llvm::operator<<
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Definition: APFixedPoint.h:230
llvm::UndefValue::get
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1770
llvm::PotentialValuesState
A class for a set state.
Definition: Attributor.h:3578
llvm::Use::getUser
User * getUser() const
Returns the User that contains this Use.
Definition: Use.h:73
llvm::Attribute::getKindAsString
StringRef getKindAsString() const
Return the attribute's kind as a string.
Definition: Attributes.cpp:297
llvm::CallGraphNode
A node in the call graph for a module.
Definition: CallGraph.h:167
llvm::Attribute::isStringAttribute
bool isStringAttribute() const
Return true if the attribute is a string (target-dependent) attribute.
Definition: Attributes.cpp:268
llvm::SplitBlockPredecessors
BasicBlock * SplitBlockPredecessors(BasicBlock *BB, ArrayRef< BasicBlock * > Preds, const char *Suffix, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, bool PreserveLCSSA=false)
This method introduces at least one new basic block into the function and moves some of the predecess...
Definition: BasicBlockUtils.cpp:1154
llvm::AbstractCallSite::getInstruction
CallBase * getInstruction() const
Return the underlying instruction.
Definition: AbstractCallSite.h:112
llvm::GraphTraits< AADepGraph * >::nodes_end
static nodes_iterator nodes_end(AADepGraph *DG)
Definition: Attributor.cpp:2505
llvm::GlobalValue::InternalLinkage
@ InternalLinkage
Rename collisions when linking (static functions).
Definition: GlobalValue.h:55
llvm::MCID::Call
@ Call
Definition: MCInstrDesc.h:154
llvm::CallBase::getCallingConv
CallingConv::ID getCallingConv() const
Definition: InstrTypes.h:1453
llvm::SetVector::empty
bool empty() const
Determine if the SetVector is empty or not.
Definition: SetVector.h:72
llvm::None
const NoneType None
Definition: None.h:23
llvm::IRPosition::EmptyKey
static const IRPosition EmptyKey
Special DenseMap key values.
Definition: Attributor.h:568
llvm::MustBeExecutedContextExplorer::findInContextOf
bool findInContextOf(const Instruction *I, const Instruction *PP)
Helper to look for I in the context of PP.
Definition: MustExecute.h:472
llvm::Value::use_empty
bool use_empty() const
Definition: Value.h:357
llvm::AbstractState::isAtFixpoint
virtual bool isAtFixpoint() const =0
Return if this abstract state is fixed, thus does not need to be updated if information changes as it...
llvm::AnalysisGetter::getAnalysis
Analysis::Result * getAnalysis(const Function &F)
Definition: Attributor.h:767
llvm::AADepGraphNode::Deps
TinyPtrVector< DepTy > Deps
Set of dependency graph nodes which should be updated if this one is updated.
Definition: Attributor.h:163
llvm::AbstractAttribute::getAsStr
virtual const std::string getAsStr() const =0
This function should return the "summarized" assumed state as string.
llvm::sys::fs::OF_TextWithCRLF
@ OF_TextWithCRLF
The file should be opened in text mode and use a carriage linefeed '\r '.
Definition: FileSystem.h:772
llvm::DOTGraphTraits
DOTGraphTraits - Template class that can be specialized to customize how graphs are converted to 'dot...
Definition: DOTGraphTraits.h:161
llvm::AttributorCGSCCPass::run
PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, LazyCallGraph &CG, CGSCCUpdateResult &UR)
Definition: Attributor.cpp:2447
llvm::Function::getAttributes
AttributeList getAttributes() const
Return the attribute list for this Function.
Definition: Function.h:239
llvm::ChangeStatus::UNCHANGED
@ UNCHANGED
llvm::InvokeInst
Invoke instruction.
Definition: Instructions.h:3686
getCalledFunction
static const Function * getCalledFunction(const Value *V, bool LookThroughBitCast, bool &IsNoBuiltin)
Definition: MemoryBuiltins.cpp:117
llvm::cl::ZeroOrMore
@ ZeroOrMore
Definition: CommandLine.h:117
llvm::function_ref
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLExtras.h:176
llvm::PointerIntPair::getPointer
PointerTy getPointer() const
Definition: PointerIntPair.h:59
llvm::Attributor::createShallowWrapper
static void createShallowWrapper(Function &F)
Create a shallow wrapper for F such that F has internal linkage afterwards.
Definition: Attributor.cpp:1480
llvm::AttributorPass::run
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)
Definition: Attributor.cpp:2427
PrintDependencies
static cl::opt< bool > PrintDependencies("attributor-print-dep", cl::Hidden, cl::desc("Print attribute dependencies"), cl::init(false))
llvm::cl::opt
Definition: CommandLine.h:1419
Attributor.h
llvm::Function::setSubprogram
void setSubprogram(DISubprogram *SP)
Set the attached subprogram.
Definition: Metadata.cpp:1522
llvm::RISCVFenceField::O
@ O
Definition: RISCVBaseInfo.h:128
llvm::IRPosition::callsite_argument
static const IRPosition callsite_argument(const CallBase &CB, unsigned ArgNo)
Create a position describing the argument of CB at position ArgNo.
Definition: Attributor.h:296
llvm::instructions
inst_range instructions(Function *F)
Definition: InstIterator.h:133
llvm::Attributor::ArgumentReplacementInfo::ACSRepairCBTy
std::function< void(const ArgumentReplacementInfo &, AbstractCallSite, SmallVectorImpl< Value * > &)> ACSRepairCBTy
Abstract call site (ACS) repair callback type.
Definition: Attributor.h:1457
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
llvm::Instruction::eraseFromParent
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:78
llvm::NONE
@ NONE
Do not track a dependence between source and target.
llvm::operator|
APInt operator|(APInt a, const APInt &b)
Definition: APInt.h:2069
llvm::Function::getReturnType
Type * getReturnType() const
Returns the type of the ret val.
Definition: Function.h:170
llvm::Function::removeAttribute
void removeAttribute(unsigned i, Attribute::AttrKind Kind)
removes the attribute from the list of attributes.
Definition: Function.cpp:540
llvm::AbstractAttribute
Base struct for all "concrete attribute" deductions.
Definition: Attributor.h:2320
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:657
llvm::count
auto count(R &&Range, const E &Element)
Wrapper function around std::count to count the number of times an element Element occurs in the give...
Definition: STLExtras.h:1588
llvm::getPointerOperand
const Value * getPointerOperand(const Value *V)
A helper function that returns the pointer operand of a load, store or GEP instruction.
Definition: Instructions.h:5251
llvm::InformationCache::getOpcodeInstMapForFunction
OpcodeInstMapTy & getOpcodeInstMapForFunction(const Function &F)
Return the map that relates "interesting" opcodes with all instructions with that opcode in F.
Definition: Attributor.h:891
llvm::TargetLibraryInfoWrapperPass
Definition: TargetLibraryInfo.h:446
llvm::DepClassTy::REQUIRED
@ REQUIRED
The target cannot be valid if the source is not.
llvm::GlobalValue::getParent
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:572
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::PreservedAnalyses::preserve
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:176
llvm::changeToUnreachable
unsigned changeToUnreachable(Instruction *I, bool UseLLVMTrap, bool PreserveLCSSA=false, DomTreeUpdater *DTU=nullptr, MemorySSAUpdater *MSSAU=nullptr)
Insert an unreachable instruction before the specified instruction, making it and the rest of the cod...
Definition: Local.cpp:2044
llvm::BumpPtrAllocatorImpl
Allocate memory in an ever growing pool, as if by bump-pointer.
Definition: Allocator.h:67
move
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
Definition: README.txt:546
llvm::LLVMContext
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:68
llvm::IRPosition::IRP_FUNCTION
@ IRP_FUNCTION
An attribute for a function (scope).
Definition: Attributor.h:243
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
llvm::IRPosition::getAnchorValue
Value & getAnchorValue() const
Return the value this abstract attribute is anchored with.
Definition: Attributor.h:340
DEBUG_COUNTER
DEBUG_COUNTER(ManifestDBGCounter, "attributor-manifest", "Determine what attributes are manifested in the IR")
llvm::DenseMap
Definition: DenseMap.h:714
llvm::Attributor::checkForAllInstructions
bool checkForAllInstructions(function_ref< bool(Instruction &)> Pred, const AbstractAttribute &QueryingAA, const ArrayRef< unsigned > &Opcodes, bool CheckBBLivenessOnly=false)
Check Pred on all instructions with an opcode present in Opcodes.
Definition: Attributor.cpp:940
llvm::Attributor::registerFunctionSignatureRewrite
bool registerFunctionSignatureRewrite(Argument &Arg, ArrayRef< Type * > ReplacementTypes, ArgumentReplacementInfo::CalleeRepairCBTy &&CalleeRepairCB, ArgumentReplacementInfo::ACSRepairCBTy &&ACSRepairCB)
Register a rewrite for a function signature.
Definition: Attributor.cpp:1637
llvm::CallGraphWrapperPass
The ModulePass which wraps up a CallGraph and the logic to build it.
Definition: CallGraph.h:337
llvm::fillMapFromAssume
void fillMapFromAssume(AssumeInst &Assume, RetainedKnowledgeMap &Result)
Insert into the map all the informations contained in the operand bundles of the llvm....
Definition: AssumeBundleQueries.cpp:70
llvm::Attribute::getKindAsEnum
Attribute::AttrKind getKindAsEnum() const
Return the attribute's kind as an enum (Attribute::AttrKind).
Definition: Attributes.cpp:276
I
#define I(x, y, z)
Definition: MD5.cpp:59
Cloning.h
llvm::IRPosition::getAssociatedValue
Value & getAssociatedValue() const
Return the value this abstract attribute is associated with.
Definition: Attributor.h:409
llvm::Attribute::AttrKind
AttrKind
This enumeration lists the attributes that can be associated with parameters, function results,...
Definition: Attributes.h:71
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:440
llvm::IRPosition::getAssociatedArgument
Argument * getAssociatedArgument() const
Return the associated argument, if any.
Definition: Attributor.cpp:204
propagate
static void propagate(InstantiatedValue From, InstantiatedValue To, MatchState State, ReachabilitySet &ReachSet, std::vector< WorkListItem > &WorkList)
Definition: CFLAndersAliasAnalysis.cpp:596
llvm::GlobalValue::setLinkage
void setLinkage(LinkageTypes LT)
Definition: GlobalValue.h:454
llvm::IRPosition::getAttrIdx
unsigned getAttrIdx() const
Return the index in the attribute list for this position.
Definition: Attributor.h:443
llvm::AAIsDead
An abstract interface for liveness abstract attribute.
Definition: Attributor.h:2810
llvm::MustBeExecutedContextExplorer::begin
iterator & begin(const Instruction *PP)
Return an iterator to explore the context around PP.
Definition: MustExecute.h:422
llvm::Function::Create
static Function * Create(FunctionType *Ty, LinkageTypes Linkage, unsigned AddrSpace, const Twine &N="", Module *M=nullptr)
Definition: Function.h:137
IRBuilder.h
llvm::AbstractState
An interface to query the internal state of an abstract attribute.
Definition: Attributor.h:1767
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::AADepGraph::end
iterator end()
Definition: Attributor.h:211
llvm::GlobalValue::hasLocalLinkage
bool hasLocalLinkage() const
Definition: GlobalValue.h:445
InlineCost.h
llvm::WriteGraph
raw_ostream & WriteGraph(raw_ostream &O, const GraphType &G, bool ShortNames=false, const Twine &Title="")
Definition: GraphWriter.h:307
llvm::IRPosition
Helper to describe and deal with positions in the LLVM-IR.
Definition: Attributor.h:231
llvm::Function::hasAttribute
bool hasAttribute(unsigned i, Attribute::AttrKind Kind) const
check if an attributes is in the list of attributes.
Definition: Function.h:434
llvm::Type::isVoidTy
bool isVoidTy() const
Return true if this is 'void'.
Definition: Type.h:139
llvm::WinEH::EncodingType::CE
@ CE
Windows NT (Windows on ARM)
llvm::DOTGraphTraits< AADepGraph * >::getNodeLabel
static std::string getNodeLabel(const AADepGraphNode *Node, const AADepGraph *DG)
Definition: Attributor.cpp:2511
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:67
TinyPtrVector.h
llvm::MustBeExecutedContextExplorer
A "must be executed context" for a given program point PP is the set of instructions,...
Definition: MustExecute.h:388
llvm::LazyCallGraph::Node
A node in the call graph.
Definition: LazyCallGraph.h:317
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:382
llvm::ARM::WinEH::ReturnType
ReturnType
Definition: ARMWinEH.h:25
llvm::Function::getFunction
const Function & getFunction() const
Definition: Function.h:135
llvm::AbstractCallSite::isCallbackCall
bool isCallbackCall() const
Return true if this ACS represents a callback call.
Definition: AbstractCallSite.h:125
llvm::SetVector::insert
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:141
llvm::AMDGPU::CPol::SCC
@ SCC
Definition: SIDefines.h:285
llvm::Attributor::identifyDefaultAbstractAttributes
void identifyDefaultAbstractAttributes(Function &F)
Determine opportunities to derive 'default' attributes in F and create abstract attribute objects for...
Definition: Attributor.cpp:1990
llvm::IRPosition::IRP_CALL_SITE_RETURNED
@ IRP_CALL_SITE_RETURNED
An attribute for a call site return value.
Definition: Attributor.h:242
llvm::make_pointer_range
iterator_range< pointer_iterator< WrappedIteratorT > > make_pointer_range(RangeT &&Range)
Definition: iterator.h:340
llvm::MustBeExecutedContextExplorer::end
iterator & end()
Return an universal end iterator.
Definition: MustExecute.h:436
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::isInstructionTriviallyDead
bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction is not used, and the instruction has no side ef...
Definition: Local.cpp:388
llvm::CGSCC
@ CGSCC
Definition: Attributor.h:3846
llvm::IRPosition::IRP_INVALID
@ IRP_INVALID
An invalid position.
Definition: Attributor.h:238
llvm::min
Expected< ExpressionValue > min(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:357
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:57
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:136
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:256
llvm::BasicBlock::getUniquePredecessor
const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
Definition: BasicBlock.cpp:272
llvm::Instruction::getFunction
const Function * getFunction() const
Return the function this instruction belongs to.
Definition: Instruction.cpp:70
llvm::Value::replaceAllUsesWith
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:527
llvm::BasicBlock::Create
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:100
MaxInitializationChainLengthX
static cl::opt< unsigned, true > MaxInitializationChainLengthX("attributor-max-initialization-chain-length", cl::Hidden, cl::desc("Maximal number of chained initializations (to avoid stack overflows)"), cl::location(MaxInitializationChainLength), cl::init(1024))
llvm::Value::getContext
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:952
llvm::ilist_node_impl::getIterator
self_iterator getIterator()
Definition: ilist_node.h:81
isEqualOrWorse
static bool isEqualOrWorse(const Attribute &New, const Attribute &Old)
}
Definition: Attributor.cpp:162
llvm::DetatchDeadBlocks
void DetatchDeadBlocks(ArrayRef< BasicBlock * > BBs, SmallVectorImpl< DominatorTree::UpdateType > *Updates, bool KeepOneInputPHIs=false)
Replace contents of every block in BBs with single unreachable instruction.
Definition: BasicBlockUtils.cpp:55
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
VerifyMaxFixpointIterations
static cl::opt< bool > VerifyMaxFixpointIterations("attributor-max-iterations-verify", cl::Hidden, cl::desc("Verify that max-iterations is a tight bound for a fixpoint"), cl::init(false))
attributor
attributor
Definition: Attributor.cpp:2604
llvm::ChangeStatus::CHANGED
@ CHANGED
llvm::Module::getFunctionList
const FunctionListType & getFunctionList() const
Get the Module's list of functions (constant).
Definition: Module.h:553
llvm::AbstractState::indicateOptimisticFixpoint
virtual ChangeStatus indicateOptimisticFixpoint()=0
Indicate that the abstract state should converge to the optimistic state.
LLVM_FALLTHROUGH
#define LLVM_FALLTHROUGH
LLVM_FALLTHROUGH - Mark fallthrough cases in switch statements.
Definition: Compiler.h:281
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:299
llvm::ValueMap< const Value *, WeakTrackingVH >
llvm::BasicBlock::getTerminator
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.cpp:148
llvm::raw_fd_ostream
A raw_ostream that writes to a file descriptor.
Definition: raw_ostream.h:432
llvm::SPII::Store
@ Store
Definition: SparcInstrInfo.h:33
llvm::IRPosition::IRP_CALL_SITE_ARGUMENT
@ IRP_CALL_SITE_ARGUMENT
An attribute for a call site argument.
Definition: Attributor.h:246
llvm::Function::begin
iterator begin()
Definition: Function.h:768
llvm::Value::stripPointerCasts
const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs and address space casts.
Definition: Value.cpp:649
llvm::SmallPtrSetImplBase::size
size_type size() const
Definition: SmallPtrSet.h:92
llvm::InformationCache::getReadOrWriteInstsForFunction
InstructionVectorTy & getReadOrWriteInstsForFunction(const Function &F)
Return the instructions in F that may read or write memory.
Definition: Attributor.h:896
llvm::BasicBlock::front
const Instruction & front() const
Definition: BasicBlock.h:308
llvm::DenseMapBase::empty
LLVM_NODISCARD bool empty() const
Definition: DenseMap.h:97
llvm::IRPosition::getAnchorScope
Function * getAnchorScope() const
Return the Function surrounding the anchor value.
Definition: Attributor.h:383
Callee
amdgpu Simplify well known AMD library false FunctionCallee Callee
Definition: AMDGPULibCalls.cpp:205
llvm::SetVector::clear
void clear()
Completely clear the SetVector.
Definition: SetVector.h:220
llvm::operator&
APInt operator&(APInt a, const APInt &b)
Definition: APInt.h:2049
Attributes.h
llvm::Attributor::isValidFunctionSignatureRewrite
bool isValidFunctionSignatureRewrite(Argument &Arg, ArrayRef< Type * > ReplacementTypes)
Check if we can rewrite a function signature.
Definition: Attributor.cpp:1578
llvm::CGSCCUpdateResult
Support structure for SCC passes to communicate updates the call graph back to the CGSCC pass manager...
Definition: CGSCCPassManager.h:232
llvm::ConstantFoldTerminator
bool ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions=false, const TargetLibraryInfo *TLI=nullptr, DomTreeUpdater *DTU=nullptr)
If a terminator instruction is predicated on a constant value, convert it into an unconditional branc...
Definition: Local.cpp:128
Verifier.h
llvm::ConstantExpr
A constant value that is initialized with an expression using other constant values.
Definition: Constants.h:931
SeedAllowList
static cl::list< std::string > SeedAllowList("attributor-seed-allow-list", cl::Hidden, cl::desc("Comma seperated list of attribute names that are " "allowed to be seeded."), cl::ZeroOrMore, cl::CommaSeparated)
llvm::IRPosition::IRP_CALL_SITE
@ IRP_CALL_SITE
An attribute for a call site (function scope).
Definition: Attributor.h:244
GraphWriter.h
llvm::IRPosition::getCallSiteArgNo
int getCallSiteArgNo() const
Return the call site argument number of the associated value if it is an argument or call site argume...
Definition: Attributor.h:438
EnableCallSiteSpecific
static cl::opt< bool > EnableCallSiteSpecific("attributor-enable-call-site-specific-deduction", cl::Hidden, cl::desc("Allow the Attributor to do call site specific analysis"), cl::init(false))
llvm::GlobalValue::isInterposableLinkage
static bool isInterposableLinkage(LinkageTypes Linkage)
Whether the definition of this global may be replaced by something non-equivalent at link time.
Definition: GlobalValue.h:345
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:161
llvm::Function::getArg
Argument * getArg(unsigned i) const
Definition: Function.h:801
llvm::GraphTraits< AADepGraphNode * >
Definition: Attributor.cpp:2479
llvm::CallGraphUpdater::replaceFunctionWith
void replaceFunctionWith(Function &OldFn, Function &NewFn)
Replace OldFn in the call graph (and SCC) with NewFn.
Definition: CallGraphUpdater.cpp:123
llvm::AttributeList::getAttribute
Attribute getAttribute(unsigned Index, Attribute::AttrKind Kind) const
Return the attribute object that exists at the given index.
Definition: Attributes.cpp:1597
Success
#define Success
Definition: AArch64Disassembler.cpp:248
Casting.h
llvm::TinyPtrVector::iterator
EltTy * iterator
Definition: TinyPtrVector.h:180
llvm::CallGraphSCCPass
Definition: CallGraphSCCPass.h:34
llvm::DepClassTy
DepClassTy
Definition: Attributor.h:147
DebugCounter.h
llvm::Function::addAttribute
void addAttribute(unsigned i, Attribute::AttrKind Kind)
adds the attribute to the list of attributes.
Definition: Function.cpp:504
llvm::Attributor
The fixpoint analysis framework that orchestrates the attribute deduction.
Definition: Attributor.h:1054
llvm::ReturnInst::Create
static ReturnInst * Create(LLVMContext &C, Value *retVal=nullptr, Instruction *InsertBefore=nullptr)
Definition: Instructions.h:2950
llvm::PointerIntPair::getOpaqueValue
void * getOpaqueValue() const
Definition: PointerIntPair.h:91
llvm::Function::getFunctionType
FunctionType * getFunctionType() const
Returns the FunctionType for me.
Definition: Function.h:165
llvm::IRPosition::argument
static const IRPosition argument(const Argument &Arg, const CallBaseContext *CBContext=nullptr)
Create a position describing the argument Arg.
Definition: Attributor.h:280
llvm::IRPosition::callsite_function
static const IRPosition callsite_function(const CallBase &CB)
Create a position describing the function scope of CB.
Definition: Attributor.h:286
llvm::AbstractAttribute::print
void print(raw_ostream &OS) const override
Helper functions, for debug purposes only.
Definition: Attributor.cpp:2289
isSimple
static bool isSimple(Instruction *I)
Definition: SLPVectorizer.cpp:524
llvm::Function::arg_begin
arg_iterator arg_begin()
Definition: Function.h:783
llvm::AADepGraphNode::begin
aaiterator begin()
Definition: Attributor.h:178
llvm::GraphTraits< AADepGraphNode * >::ChildEdgeIteratorType
TinyPtrVector< DepTy >::iterator ChildEdgeIteratorType
Definition: Attributor.cpp:2489
llvm::GlobalValue::getAddressSpace
unsigned getAddressSpace() const
Definition: Globals.cpp:112
llvm::AADepGraph
The data structure for the dependency graph.
Definition: Attributor.h:195
llvm::AADepGraphNode
}
Definition: Attributor.h:155
cgscc
Deduce and propagate false attributor cgscc
Definition: Attributor.cpp:2611
llvm::AttributeList::FunctionIndex
@ FunctionIndex
Definition: Attributes.h:389
llvm::Function::isVarArg
bool isVarArg() const
isVarArg - Return true if this function takes a variable number of arguments.
Definition: Function.h:178
llvm::AttributeList::getRetAttributes
AttributeSet getRetAttributes() const
The attributes for the ret value are returned.
Definition: Attributes.cpp:1558
llvm::Pass
Pass interface - Implemented by all 'passes'.
Definition: Pass.h:91
llvm::CallGraphUpdater::removeFunction
void removeFunction(Function &Fn)
Remove Fn from the call graph.
Definition: CallGraphUpdater.cpp:107
llvm::GlobalValue::PrivateLinkage
@ PrivateLinkage
Like Internal, but omit from symbol table.
Definition: GlobalValue.h:56
llvm::PointerIntPair
PointerIntPair - This class implements a pair of a pointer and small integer.
Definition: PointerIntPair.h:45
llvm::AttributeSet
Definition: Attributes.h:254
llvm::DOTGraphTraits< AADepGraph * >::DOTGraphTraits
DOTGraphTraits(bool isSimple=false)
Definition: Attributor.cpp:2509
llvm::AADepGraph::begin
iterator begin()
Definition: Attributor.h:210
llvm::IRPosition::TombstoneKey
static const IRPosition TombstoneKey
Definition: Attributor.h:569
llvm::AbstractAttribute::updateImpl
virtual ChangeStatus updateImpl(Attributor &A)=0
The actual update/transfer function which has to be implemented by the derived classes.
Allocator
Basic Register Allocator
Definition: RegAllocBasic.cpp:146
llvm::Attributor::checkForAllReadWriteInstructions
bool checkForAllReadWriteInstructions(function_ref< bool(Instruction &)> Pred, AbstractAttribute &QueryingAA)
Check Pred on all Read/Write instructions.
Definition: Attributor.cpp:967
llvm::SmallPtrSetImplBase::empty
LLVM_NODISCARD bool empty() const
Definition: SmallPtrSet.h:91
N
#define N
llvm::changeToCall
void changeToCall(InvokeInst *II, DomTreeUpdater *DTU=nullptr)
This function converts the specified invoek into a normall call.
Definition: Local.cpp:2117
llvm::to_string
std::string to_string(const T &Value)
Definition: ScopedPrinter.h:62
llvm::BlockAddress::get
static BlockAddress * get(Function *F, BasicBlock *BB)
Return a BlockAddress for the specified function and basic block.
Definition: Constants.cpp:1808
llvm::ArrayRef::size
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:163
llvm::AnalysisGetter
Wrapper for FunctoinAnalysisManager.
Definition: Attributor.h:765
llvm::GraphTraits< AADepGraphNode * >::DepGetVal
static NodeRef DepGetVal(DepTy &DT)
Definition: Attributor.cpp:2485
llvm::AAIsDead::isAssumedDead
virtual bool isAssumedDead() const =0
The query functions are protected such that other attributes need to go through the Attributor interf...
llvm::PHINode
Definition: Instructions.h:2572
llvm::Function::getAttribute
Attribute getAttribute(unsigned i, Attribute::AttrKind Kind) const
gets the attribute from the list of attributes.
Definition: Function.h:449
checkForAllInstructionsImpl
static bool checkForAllInstructionsImpl(Attributor *A, InformationCache::OpcodeInstMapTy &OpcodeInstMap, function_ref< bool(Instruction &)> Pred, const AbstractAttribute *QueryingAA, const AAIsDead *LivenessAA, const ArrayRef< unsigned > &Opcodes, bool CheckBBLivenessOnly=false)
Definition: Attributor.cpp:916
llvm::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:43
llvm::DefaultDOTGraphTraits
DefaultDOTGraphTraits - This class provides the default implementations of all of the DOTGraphTraits ...
Definition: DOTGraphTraits.h:28
llvm::CallBase::addAttribute
void addAttribute(unsigned i, Attribute::AttrKind Kind)
adds the attribute to the list of attributes.
Definition: InstrTypes.h:1493
llvm::Attribute::isIntAttribute
bool isIntAttribute() const
Return true if the attribute is an integer attribute.
Definition: Attributes.cpp:264
llvm::SubsumingPositionIterator
A visitor class for IR positions.
Definition: Attributor.h:754
llvm::CallBase
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1164
llvm::SmallPtrSetImpl
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:343
llvm::SmallSetVector
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:307
llvm::SetVector::back
const T & back() const
Return the last element of the SetVector.
Definition: SetVector.h:128
llvm::IRPosition::Kind
Kind
The positions we distinguish in the IR.
Definition: Attributor.h:237
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
llvm::Attributor::ArgumentReplacementInfo::CalleeRepairCBTy
std::function< void(const ArgumentReplacementInfo &, Function &, Function::arg_iterator)> CalleeRepairCBTy
Callee repair callback type.
Definition: Attributor.h:1443
llvm::InnerAnalysisManagerProxy
An analysis over an "outer" IR unit that provides access to an analysis manager over an "inner" IR un...
Definition: PassManager.h:945
llvm::Attributor::isAssumedDead
bool isAssumedDead(const AbstractAttribute &AA, const AAIsDead *LivenessAA, bool CheckBBLivenessOnly=false, DepClassTy DepClass=DepClassTy::OPTIONAL)
Return true if AA (or its context instruction) is assumed dead.
Definition: Attributor.cpp:584
llvm::CallInst
This class represents a function call, abstracting a target machine's calling convention.
Definition: Instructions.h:1450
llvm::initializeAttributorCGSCCLegacyPassPass
void initializeAttributorCGSCCLegacyPassPass(PassRegistry &)
llvm::CloneFunctionInto
void CloneFunctionInto(Function *NewFunc, const Function *OldFunc, ValueToValueMapTy &VMap, CloneFunctionChangeType Changes, SmallVectorImpl< ReturnInst * > &Returns, const char *NameSuffix="", ClonedCodeInfo *CodeInfo=nullptr, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr)
Clone OldFunc into NewFunc, transforming the old arguments into references to VMap values.
Definition: CloneFunction.cpp:84
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::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
llvm::GraphTraits
Definition: GraphTraits.h:35
ViewDepGraph
static cl::opt< bool > ViewDepGraph("attributor-view-dep-graph", cl::Hidden, cl::desc("View the dependency graph."), cl::init(false))
llvm::Value::takeName
void takeName(Value *V)
Transfer the name from V to this value.
Definition: Value.cpp:377
llvm::AMDGPU::HSAMD::Kernel::Key::Args
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
Definition: AMDGPUMetadata.h:389
llvm::cl::desc
Definition: CommandLine.h:411
llvm::Attributor::checkForAllReturnedValuesAndReturnInsts
bool checkForAllReturnedValuesAndReturnInsts(function_ref< bool(Value &, const SmallSetVector< ReturnInst *, 4 > &)> Pred, const AbstractAttribute &QueryingAA)
Check Pred on all values potentially returned by F.
Definition: Attributor.cpp:872
llvm::LazyCallGraph
A lazily constructed view of the call graph of a module.
Definition: LazyCallGraph.h:112
llvm::AbstractAttribute::getIRPosition
const IRPosition & getIRPosition() const
Return an IR position, see struct IRPosition.
Definition: Attributor.h:2351
raw_ostream.h
llvm::AbstractCallSite::getCalledFunction
Function * getCalledFunction() const
Return the function being called if this is a direct call, otherwise return null (if it's an indirect...
Definition: AbstractCallSite.h:218
llvm::CallGraphUpdater::initialize
void initialize(CallGraph &CG, CallGraphSCC &SCC)
Initializers for usage outside of a CGSCC pass, inside a CGSCC pass in the old and new pass manager (...
Definition: CallGraphUpdater.h:62
llvm::CallGraphUpdater::reanalyzeFunction
void reanalyzeFunction(Function &Fn)
After an CGSCC pass changes a function in ways that affect the call graph, this method can be called ...
Definition: CallGraphUpdater.cpp:87
llvm::SetVector
A vector that has set insertion semantics.
Definition: SetVector.h:40
internalizeFunction
static Function * internalizeFunction(Function &F)
Make another copy of the function F such that the copied version has internal linkage afterwards and ...
Definition: Attributor.cpp:1535
llvm::SmallVectorImpl::reserve
void reserve(size_type N)
Definition: SmallVector.h:624
llvm::IRPosition::callsite_returned
static const IRPosition callsite_returned(const CallBase &CB)
Create a position describing the returned value of CB.
Definition: Attributor.h:291
llvm::FunctionAnalysisManagerCGSCCProxy
A proxy from a FunctionAnalysisManager to an SCC.
Definition: CGSCCPassManager.h:392
BasicBlockUtils.h
llvm::AbstractCallSite::getCallArgOperand
Value * getCallArgOperand(Argument &Arg) const
Return the operand of the underlying instruction associated with Arg.
Definition: AbstractCallSite.h:177
llvm::Attributor::isModulePass
bool isModulePass() const
Return true if this is a module pass, false otherwise.
Definition: Attributor.h:1282
llvm::Function::setAttributes
void setAttributes(AttributeList Attrs)
Set the attribute list for this Function.
Definition: Function.h:242
llvm::GlobalValue::setVisibility
void setVisibility(VisibilityTypes V)
Definition: GlobalValue.h:235
InitializePasses.h
MaxFixpointIterations
static cl::opt< unsigned > MaxFixpointIterations("attributor-max-iterations", cl::Hidden, cl::desc("Maximal number of fixpoint iterations."), cl::init(32))
llvm::FunctionType::getReturnType
Type * getReturnType() const
Definition: DerivedTypes.h:123
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
Debug.h
llvm::Value::users
iterator_range< user_iterator > users()
Definition: Value.h:434
File
Instrumentation for Order File
Definition: InstrOrderFile.cpp:206
llvm::Attributor::getAssumedConstant
Optional< Constant * > getAssumedConstant(const Value &V, const AbstractAttribute &AA, bool &UsedAssumedInformation)
If V is assumed to be a constant, return it, if it is unclear yet, return None, otherwise return null...
Definition: Attributor.cpp:549
llvm::AADepGraph::viewGraph
void viewGraph()
Definition: Attributor.cpp:2398
llvm::Optional::getValue
constexpr const T & getValue() const LLVM_LVALUE_FUNCTION
Definition: Optional.h:280
llvm::AbstractCallSite::getCallArgOperandNo
int getCallArgOperandNo(Argument &Arg) const
Return the operand index of the underlying instruction associated with Arg.
Definition: AbstractCallSite.h:163
llvm::IRPosition::returned
static const IRPosition returned(const Function &F, const CallBaseContext *CBContext=nullptr)
Create a position describing the returned value of F.
Definition: Attributor.h:273
llvm::CallBase::setCallingConv
void setCallingConv(CallingConv::ID CC)
Definition: InstrTypes.h:1457
llvm::FunctionType
Class to represent function types.
Definition: DerivedTypes.h:102
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44
llvm::Function::size
size_t size() const
Definition: Function.h:773
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:364
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38
llvm::cl::list
Definition: CommandLine.h:1627