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