LLVM  14.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/Constant.h"
30 #include "llvm/IR/Constants.h"
31 #include "llvm/IR/GlobalValue.h"
32 #include "llvm/IR/GlobalVariable.h"
33 #include "llvm/IR/IRBuilder.h"
34 #include "llvm/IR/Instruction.h"
35 #include "llvm/IR/IntrinsicInst.h"
36 #include "llvm/IR/NoFolder.h"
37 #include "llvm/IR/ValueHandle.h"
38 #include "llvm/IR/Verifier.h"
39 #include "llvm/InitializePasses.h"
40 #include "llvm/Support/Casting.h"
42 #include "llvm/Support/Debug.h"
50 
51 #include <cassert>
52 #include <string>
53 
54 using namespace llvm;
55 
56 #define DEBUG_TYPE "attributor"
57 
58 DEBUG_COUNTER(ManifestDBGCounter, "attributor-manifest",
59  "Determine what attributes are manifested in the IR");
60 
61 STATISTIC(NumFnDeleted, "Number of function deleted");
62 STATISTIC(NumFnWithExactDefinition,
63  "Number of functions with exact definitions");
64 STATISTIC(NumFnWithoutExactDefinition,
65  "Number of functions without exact definitions");
66 STATISTIC(NumFnShallowWrappersCreated, "Number of shallow wrappers created");
67 STATISTIC(NumAttributesTimedOut,
68  "Number of abstract attributes timed out before fixpoint");
69 STATISTIC(NumAttributesValidFixpoint,
70  "Number of abstract attributes in a valid fixpoint state");
71 STATISTIC(NumAttributesManifested,
72  "Number of abstract attributes manifested in IR");
73 
74 // TODO: Determine a good default value.
75 //
76 // In the LLVM-TS and SPEC2006, 32 seems to not induce compile time overheads
77 // (when run with the first 5 abstract attributes). The results also indicate
78 // that we never reach 32 iterations but always find a fixpoint sooner.
79 //
80 // This will become more evolved once we perform two interleaved fixpoint
81 // iterations: bottom-up and top-down.
82 static cl::opt<unsigned>
83  SetFixpointIterations("attributor-max-iterations", cl::Hidden,
84  cl::desc("Maximal number of fixpoint iterations."),
85  cl::init(32));
86 
88  "attributor-max-initialization-chain-length", cl::Hidden,
89  cl::desc(
90  "Maximal number of chained initializations (to avoid stack overflows)"),
93 
95  "attributor-max-iterations-verify", cl::Hidden,
96  cl::desc("Verify that max-iterations is a tight bound for a fixpoint"),
97  cl::init(false));
98 
100  "attributor-annotate-decl-cs", cl::Hidden,
101  cl::desc("Annotate call sites of function declarations."), cl::init(false));
102 
103 static cl::opt<bool> EnableHeapToStack("enable-heap-to-stack-conversion",
104  cl::init(true), cl::Hidden);
105 
106 static cl::opt<bool>
107  AllowShallowWrappers("attributor-allow-shallow-wrappers", cl::Hidden,
108  cl::desc("Allow the Attributor to create shallow "
109  "wrappers for non-exact definitions."),
110  cl::init(false));
111 
112 static cl::opt<bool>
113  AllowDeepWrapper("attributor-allow-deep-wrappers", cl::Hidden,
114  cl::desc("Allow the Attributor to use IP information "
115  "derived from non-exact functions via cloning"),
116  cl::init(false));
117 
118 // These options can only used for debug builds.
119 #ifndef NDEBUG
121  SeedAllowList("attributor-seed-allow-list", cl::Hidden,
122  cl::desc("Comma seperated list of attribute names that are "
123  "allowed to be seeded."),
125 
127  "attributor-function-seed-allow-list", cl::Hidden,
128  cl::desc("Comma seperated list of function names that are "
129  "allowed to be seeded."),
131 #endif
132 
133 static cl::opt<bool>
134  DumpDepGraph("attributor-dump-dep-graph", cl::Hidden,
135  cl::desc("Dump the dependency graph to dot files."),
136  cl::init(false));
137 
139  "attributor-depgraph-dot-filename-prefix", cl::Hidden,
140  cl::desc("The prefix used for the CallGraph dot file names."));
141 
142 static cl::opt<bool> ViewDepGraph("attributor-view-dep-graph", cl::Hidden,
143  cl::desc("View the dependency graph."),
144  cl::init(false));
145 
146 static cl::opt<bool> PrintDependencies("attributor-print-dep", cl::Hidden,
147  cl::desc("Print attribute dependencies"),
148  cl::init(false));
149 
151  "attributor-enable-call-site-specific-deduction", cl::Hidden,
152  cl::desc("Allow the Attributor to do call site specific analysis"),
153  cl::init(false));
154 
155 static cl::opt<bool>
156  PrintCallGraph("attributor-print-call-graph", cl::Hidden,
157  cl::desc("Print Attributor's internal call graph"),
158  cl::init(false));
159 
160 static cl::opt<bool> SimplifyAllLoads("attributor-simplify-all-loads",
161  cl::Hidden,
162  cl::desc("Try to simplify all loads."),
163  cl::init(true));
164 
165 /// Logic operators for the change status enum class.
166 ///
167 ///{
169  return L == ChangeStatus::CHANGED ? L : R;
170 }
172  L = L | R;
173  return L;
174 }
176  return L == ChangeStatus::UNCHANGED ? L : R;
177 }
179  L = L & R;
180  return L;
181 }
182 ///}
183 
185  const Value &V) {
186  if (auto *C = dyn_cast<Constant>(&V))
187  return !C->isThreadDependent();
188  // TODO: Inspect and cache more complex instructions.
189  if (auto *CB = dyn_cast<CallBase>(&V))
190  return CB->getNumOperands() == 0 && !CB->mayHaveSideEffects() &&
191  !CB->mayReadFromMemory();
192  const Function *Scope = nullptr;
193  if (auto *I = dyn_cast<Instruction>(&V))
194  Scope = I->getFunction();
195  if (auto *A = dyn_cast<Argument>(&V))
196  Scope = A->getParent();
197  if (!Scope)
198  return false;
199  auto &NoRecurseAA = A.getAAFor<AANoRecurse>(
201  return NoRecurseAA.isAssumedNoRecurse();
202 }
203 
205  if (isa<AllocaInst>(Obj))
206  return UndefValue::get(&Ty);
207  auto *GV = dyn_cast<GlobalVariable>(&Obj);
208  if (!GV || !GV->hasLocalLinkage())
209  return nullptr;
210  if (!GV->hasInitializer())
211  return UndefValue::get(&Ty);
212  return dyn_cast_or_null<Constant>(getWithType(*GV->getInitializer(), Ty));
213 }
214 
215 bool AA::isValidInScope(const Value &V, const Function *Scope) {
216  if (isa<Constant>(V))
217  return true;
218  if (auto *I = dyn_cast<Instruction>(&V))
219  return I->getFunction() == Scope;
220  if (auto *A = dyn_cast<Argument>(&V))
221  return A->getParent() == Scope;
222  return false;
223 }
224 
225 bool AA::isValidAtPosition(const Value &V, const Instruction &CtxI,
226  InformationCache &InfoCache) {
227  if (isa<Constant>(V))
228  return true;
229  const Function *Scope = CtxI.getFunction();
230  if (auto *A = dyn_cast<Argument>(&V))
231  return A->getParent() == Scope;
232  if (auto *I = dyn_cast<Instruction>(&V))
233  if (I->getFunction() == Scope) {
234  const DominatorTree *DT =
236  return DT && DT->dominates(I, &CtxI);
237  }
238  return false;
239 }
240 
242  if (V.getType() == &Ty)
243  return &V;
244  if (isa<PoisonValue>(V))
245  return PoisonValue::get(&Ty);
246  if (isa<UndefValue>(V))
247  return UndefValue::get(&Ty);
248  if (auto *C = dyn_cast<Constant>(&V)) {
249  if (C->isNullValue())
250  return Constant::getNullValue(&Ty);
251  if (C->getType()->isPointerTy() && Ty.isPointerTy())
252  return ConstantExpr::getPointerCast(C, &Ty);
253  if (C->getType()->isIntegerTy() && Ty.isIntegerTy())
254  return ConstantExpr::getTrunc(C, &Ty, /* OnlyIfReduced */ true);
255  if (C->getType()->isFloatingPointTy() && Ty.isFloatingPointTy())
256  return ConstantExpr::getFPTrunc(C, &Ty, /* OnlyIfReduced */ true);
257  }
258  return nullptr;
259 }
260 
263  const Optional<Value *> &B, Type *Ty) {
264  if (A == B)
265  return A;
266  if (!B.hasValue())
267  return A;
268  if (*B == nullptr)
269  return nullptr;
270  if (!A.hasValue())
271  return Ty ? getWithType(**B, *Ty) : nullptr;
272  if (*A == nullptr)
273  return nullptr;
274  if (!Ty)
275  Ty = (*A)->getType();
276  if (isa_and_nonnull<UndefValue>(*A))
277  return getWithType(**B, *Ty);
278  if (isa<UndefValue>(*B))
279  return A;
280  if (*A && *B && *A == getWithType(**B, *Ty))
281  return A;
282  return nullptr;
283 }
284 
286  Attributor &A, StoreInst &SI, SmallSetVector<Value *, 4> &PotentialCopies,
287  const AbstractAttribute &QueryingAA, bool &UsedAssumedInformation) {
288 
289  Value &Ptr = *SI.getPointerOperand();
290  SmallVector<Value *, 8> Objects;
291  if (!AA::getAssumedUnderlyingObjects(A, Ptr, Objects, QueryingAA, &SI)) {
292  LLVM_DEBUG(
293  dbgs() << "Underlying objects stored into could not be determined\n";);
294  return false;
295  }
296 
298  SmallVector<Value *> NewCopies;
299 
300  for (Value *Obj : Objects) {
301  LLVM_DEBUG(dbgs() << "Visit underlying object " << *Obj << "\n");
302  if (isa<UndefValue>(Obj))
303  continue;
304  if (isa<ConstantPointerNull>(Obj)) {
305  // A null pointer access can be undefined but any offset from null may
306  // be OK. We do not try to optimize the latter.
307  if (!NullPointerIsDefined(SI.getFunction(),
308  Ptr.getType()->getPointerAddressSpace()) &&
309  A.getAssumedSimplified(Ptr, QueryingAA, UsedAssumedInformation) ==
310  Obj)
311  continue;
312  LLVM_DEBUG(
313  dbgs() << "Underlying object is a valid nullptr, giving up.\n";);
314  return false;
315  }
316  if (!isa<AllocaInst>(Obj) && !isa<GlobalVariable>(Obj)) {
317  LLVM_DEBUG(dbgs() << "Underlying object is not supported yet: " << *Obj
318  << "\n";);
319  return false;
320  }
321  if (auto *GV = dyn_cast<GlobalVariable>(Obj))
322  if (!GV->hasLocalLinkage()) {
323  LLVM_DEBUG(dbgs() << "Underlying object is global with external "
324  "linkage, not supported yet: "
325  << *Obj << "\n";);
326  return false;
327  }
328 
329  auto CheckAccess = [&](const AAPointerInfo::Access &Acc, bool IsExact) {
330  if (!Acc.isRead())
331  return true;
332  auto *LI = dyn_cast<LoadInst>(Acc.getRemoteInst());
333  if (!LI) {
334  LLVM_DEBUG(dbgs() << "Underlying object read through a non-load "
335  "instruction not supported yet: "
336  << *Acc.getRemoteInst() << "\n";);
337  return false;
338  }
339  NewCopies.push_back(LI);
340  return true;
341  };
342 
343  auto &PI = A.getAAFor<AAPointerInfo>(QueryingAA, IRPosition::value(*Obj),
345  if (!PI.forallInterferingAccesses(SI, CheckAccess)) {
346  LLVM_DEBUG(
347  dbgs()
348  << "Failed to verify all interfering accesses for underlying object: "
349  << *Obj << "\n");
350  return false;
351  }
352  PIs.push_back(&PI);
353  }
354 
355  for (auto *PI : PIs) {
356  if (!PI->getState().isAtFixpoint())
357  UsedAssumedInformation = true;
358  A.recordDependence(*PI, QueryingAA, DepClassTy::OPTIONAL);
359  }
360  PotentialCopies.insert(NewCopies.begin(), NewCopies.end());
361 
362  return true;
363 }
364 
365 /// Return true if \p New is equal or worse than \p Old.
366 static bool isEqualOrWorse(const Attribute &New, const Attribute &Old) {
367  if (!Old.isIntAttribute())
368  return true;
369 
370  return Old.getValueAsInt() >= New.getValueAsInt();
371 }
372 
373 /// Return true if the information provided by \p Attr was added to the
374 /// attribute list \p Attrs. This is only the case if it was not already present
375 /// in \p Attrs at the position describe by \p PK and \p AttrIdx.
376 static bool addIfNotExistent(LLVMContext &Ctx, const Attribute &Attr,
377  AttributeList &Attrs, int AttrIdx,
378  bool ForceReplace = false) {
379 
380  if (Attr.isEnumAttribute()) {
382  if (Attrs.hasAttribute(AttrIdx, Kind))
383  if (!ForceReplace &&
384  isEqualOrWorse(Attr, Attrs.getAttribute(AttrIdx, Kind)))
385  return false;
386  Attrs = Attrs.addAttribute(Ctx, AttrIdx, Attr);
387  return true;
388  }
389  if (Attr.isStringAttribute()) {
390  StringRef Kind = Attr.getKindAsString();
391  if (Attrs.hasAttribute(AttrIdx, Kind))
392  if (!ForceReplace &&
393  isEqualOrWorse(Attr, Attrs.getAttribute(AttrIdx, Kind)))
394  return false;
395  Attrs = Attrs.addAttribute(Ctx, AttrIdx, Attr);
396  return true;
397  }
398  if (Attr.isIntAttribute()) {
400  if (Attrs.hasAttribute(AttrIdx, Kind))
401  if (!ForceReplace &&
402  isEqualOrWorse(Attr, Attrs.getAttribute(AttrIdx, Kind)))
403  return false;
404  Attrs = Attrs.removeAttribute(Ctx, AttrIdx, Kind);
405  Attrs = Attrs.addAttribute(Ctx, AttrIdx, Attr);
406  return true;
407  }
408 
409  llvm_unreachable("Expected enum or string attribute!");
410 }
411 
413  if (getPositionKind() == IRP_ARGUMENT)
414  return cast<Argument>(&getAnchorValue());
415 
416  // Not an Argument and no argument number means this is not a call site
417  // argument, thus we cannot find a callback argument to return.
418  int ArgNo = getCallSiteArgNo();
419  if (ArgNo < 0)
420  return nullptr;
421 
422  // Use abstract call sites to make the connection between the call site
423  // values and the ones in callbacks. If a callback was found that makes use
424  // of the underlying call site operand, we want the corresponding callback
425  // callee argument and not the direct callee argument.
426  Optional<Argument *> CBCandidateArg;
427  SmallVector<const Use *, 4> CallbackUses;
428  const auto &CB = cast<CallBase>(getAnchorValue());
429  AbstractCallSite::getCallbackUses(CB, CallbackUses);
430  for (const Use *U : CallbackUses) {
431  AbstractCallSite ACS(U);
432  assert(ACS && ACS.isCallbackCall());
433  if (!ACS.getCalledFunction())
434  continue;
435 
436  for (unsigned u = 0, e = ACS.getNumArgOperands(); u < e; u++) {
437 
438  // Test if the underlying call site operand is argument number u of the
439  // callback callee.
440  if (ACS.getCallArgOperandNo(u) != ArgNo)
441  continue;
442 
443  assert(ACS.getCalledFunction()->arg_size() > u &&
444  "ACS mapped into var-args arguments!");
445  if (CBCandidateArg.hasValue()) {
446  CBCandidateArg = nullptr;
447  break;
448  }
449  CBCandidateArg = ACS.getCalledFunction()->getArg(u);
450  }
451  }
452 
453  // If we found a unique callback candidate argument, return it.
454  if (CBCandidateArg.hasValue() && CBCandidateArg.getValue())
455  return CBCandidateArg.getValue();
456 
457  // If no callbacks were found, or none used the underlying call site operand
458  // exclusively, use the direct callee argument if available.
459  const Function *Callee = CB.getCalledFunction();
460  if (Callee && Callee->arg_size() > unsigned(ArgNo))
461  return Callee->getArg(ArgNo);
462 
463  return nullptr;
464 }
465 
468  if (getState().isAtFixpoint())
469  return HasChanged;
470 
471  LLVM_DEBUG(dbgs() << "[Attributor] Update: " << *this << "\n");
472 
473  HasChanged = updateImpl(A);
474 
475  LLVM_DEBUG(dbgs() << "[Attributor] Update " << HasChanged << " " << *this
476  << "\n");
477 
478  return HasChanged;
479 }
480 
483  const ArrayRef<Attribute> &DeducedAttrs,
484  bool ForceReplace) {
485  Function *ScopeFn = IRP.getAnchorScope();
487 
488  // In the following some generic code that will manifest attributes in
489  // DeducedAttrs if they improve the current IR. Due to the different
490  // annotation positions we use the underlying AttributeList interface.
491 
493  switch (PK) {
500  Attrs = ScopeFn->getAttributes();
501  break;
505  Attrs = cast<CallBase>(IRP.getAnchorValue()).getAttributes();
506  break;
507  }
508 
510  LLVMContext &Ctx = IRP.getAnchorValue().getContext();
511  for (const Attribute &Attr : DeducedAttrs) {
512  if (!addIfNotExistent(Ctx, Attr, Attrs, IRP.getAttrIdx(), ForceReplace))
513  continue;
514 
515  HasChanged = ChangeStatus::CHANGED;
516  }
517 
518  if (HasChanged == ChangeStatus::UNCHANGED)
519  return HasChanged;
520 
521  switch (PK) {
525  ScopeFn->setAttributes(Attrs);
526  break;
530  cast<CallBase>(IRP.getAnchorValue()).setAttributes(Attrs);
531  break;
534  break;
535  }
536 
537  return HasChanged;
538 }
539 
541 const IRPosition
543 
545  IRPositions.emplace_back(IRP);
546 
547  // Helper to determine if operand bundles on a call site are benin or
548  // potentially problematic. We handle only llvm.assume for now.
549  auto CanIgnoreOperandBundles = [](const CallBase &CB) {
550  return (isa<IntrinsicInst>(CB) &&
551  cast<IntrinsicInst>(CB).getIntrinsicID() == Intrinsic ::assume);
552  };
553 
554  const auto *CB = dyn_cast<CallBase>(&IRP.getAnchorValue());
555  switch (IRP.getPositionKind()) {
559  return;
562  IRPositions.emplace_back(IRPosition::function(*IRP.getAnchorScope()));
563  return;
565  assert(CB && "Expected call site!");
566  // TODO: We need to look at the operand bundles similar to the redirection
567  // in CallBase.
568  if (!CB->hasOperandBundles() || CanIgnoreOperandBundles(*CB))
569  if (const Function *Callee = CB->getCalledFunction())
570  IRPositions.emplace_back(IRPosition::function(*Callee));
571  return;
573  assert(CB && "Expected call site!");
574  // TODO: We need to look at the operand bundles similar to the redirection
575  // in CallBase.
576  if (!CB->hasOperandBundles() || CanIgnoreOperandBundles(*CB)) {
577  if (const Function *Callee = CB->getCalledFunction()) {
578  IRPositions.emplace_back(IRPosition::returned(*Callee));
579  IRPositions.emplace_back(IRPosition::function(*Callee));
580  for (const Argument &Arg : Callee->args())
581  if (Arg.hasReturnedAttr()) {
582  IRPositions.emplace_back(
583  IRPosition::callsite_argument(*CB, Arg.getArgNo()));
584  IRPositions.emplace_back(
585  IRPosition::value(*CB->getArgOperand(Arg.getArgNo())));
586  IRPositions.emplace_back(IRPosition::argument(Arg));
587  }
588  }
589  }
590  IRPositions.emplace_back(IRPosition::callsite_function(*CB));
591  return;
593  assert(CB && "Expected call site!");
594  // TODO: We need to look at the operand bundles similar to the redirection
595  // in CallBase.
596  if (!CB->hasOperandBundles() || CanIgnoreOperandBundles(*CB)) {
597  const Function *Callee = CB->getCalledFunction();
598  if (Callee) {
599  if (Argument *Arg = IRP.getAssociatedArgument())
600  IRPositions.emplace_back(IRPosition::argument(*Arg));
601  IRPositions.emplace_back(IRPosition::function(*Callee));
602  }
603  }
604  IRPositions.emplace_back(IRPosition::value(IRP.getAssociatedValue()));
605  return;
606  }
607  }
608 }
609 
611  bool IgnoreSubsumingPositions, Attributor *A) const {
613  for (const IRPosition &EquivIRP : SubsumingPositionIterator(*this)) {
614  for (Attribute::AttrKind AK : AKs)
615  if (EquivIRP.getAttrsFromIRAttr(AK, Attrs))
616  return true;
617  // The first position returned by the SubsumingPositionIterator is
618  // always the position itself. If we ignore subsuming positions we
619  // are done after the first iteration.
620  if (IgnoreSubsumingPositions)
621  break;
622  }
623  if (A)
624  for (Attribute::AttrKind AK : AKs)
625  if (getAttrsFromAssumes(AK, Attrs, *A))
626  return true;
627  return false;
628 }
629 
632  bool IgnoreSubsumingPositions, Attributor *A) const {
633  for (const IRPosition &EquivIRP : SubsumingPositionIterator(*this)) {
634  for (Attribute::AttrKind AK : AKs)
635  EquivIRP.getAttrsFromIRAttr(AK, Attrs);
636  // The first position returned by the SubsumingPositionIterator is
637  // always the position itself. If we ignore subsuming positions we
638  // are done after the first iteration.
639  if (IgnoreSubsumingPositions)
640  break;
641  }
642  if (A)
643  for (Attribute::AttrKind AK : AKs)
644  getAttrsFromAssumes(AK, Attrs, *A);
645 }
646 
647 bool IRPosition::getAttrsFromIRAttr(Attribute::AttrKind AK,
650  return false;
651 
652  AttributeList AttrList;
653  if (const auto *CB = dyn_cast<CallBase>(&getAnchorValue()))
654  AttrList = CB->getAttributes();
655  else
656  AttrList = getAssociatedFunction()->getAttributes();
657 
658  bool HasAttr = AttrList.hasAttribute(getAttrIdx(), AK);
659  if (HasAttr)
660  Attrs.push_back(AttrList.getAttribute(getAttrIdx(), AK));
661  return HasAttr;
662 }
663 
664 bool IRPosition::getAttrsFromAssumes(Attribute::AttrKind AK,
666  Attributor &A) const {
667  assert(getPositionKind() != IRP_INVALID && "Did expect a valid position!");
668  Value &AssociatedValue = getAssociatedValue();
669 
670  const Assume2KnowledgeMap &A2K =
671  A.getInfoCache().getKnowledgeMap().lookup({&AssociatedValue, AK});
672 
673  // Check if we found any potential assume use, if not we don't need to create
674  // explorer iterators.
675  if (A2K.empty())
676  return false;
677 
678  LLVMContext &Ctx = AssociatedValue.getContext();
679  unsigned AttrsSize = Attrs.size();
681  A.getInfoCache().getMustBeExecutedContextExplorer();
682  auto EIt = Explorer.begin(getCtxI()), EEnd = Explorer.end(getCtxI());
683  for (auto &It : A2K)
684  if (Explorer.findInContextOf(It.first, EIt, EEnd))
685  Attrs.push_back(Attribute::get(Ctx, AK, It.second.Max));
686  return AttrsSize != Attrs.size();
687 }
688 
689 void IRPosition::verify() {
690 #ifdef EXPENSIVE_CHECKS
691  switch (getPositionKind()) {
692  case IRP_INVALID:
693  assert((CBContext == nullptr) &&
694  "Invalid position must not have CallBaseContext!");
695  assert(!Enc.getOpaqueValue() &&
696  "Expected a nullptr for an invalid position!");
697  return;
698  case IRP_FLOAT:
699  assert((!isa<CallBase>(&getAssociatedValue()) &&
700  !isa<Argument>(&getAssociatedValue())) &&
701  "Expected specialized kind for call base and argument values!");
702  return;
703  case IRP_RETURNED:
704  assert(isa<Function>(getAsValuePtr()) &&
705  "Expected function for a 'returned' position!");
706  assert(getAsValuePtr() == &getAssociatedValue() &&
707  "Associated value mismatch!");
708  return;
710  assert((CBContext == nullptr) &&
711  "'call site returned' position must not have CallBaseContext!");
712  assert((isa<CallBase>(getAsValuePtr())) &&
713  "Expected call base for 'call site returned' position!");
714  assert(getAsValuePtr() == &getAssociatedValue() &&
715  "Associated value mismatch!");
716  return;
717  case IRP_CALL_SITE:
718  assert((CBContext == nullptr) &&
719  "'call site function' position must not have CallBaseContext!");
720  assert((isa<CallBase>(getAsValuePtr())) &&
721  "Expected call base for 'call site function' position!");
722  assert(getAsValuePtr() == &getAssociatedValue() &&
723  "Associated value mismatch!");
724  return;
725  case IRP_FUNCTION:
726  assert(isa<Function>(getAsValuePtr()) &&
727  "Expected function for a 'function' position!");
728  assert(getAsValuePtr() == &getAssociatedValue() &&
729  "Associated value mismatch!");
730  return;
731  case IRP_ARGUMENT:
732  assert(isa<Argument>(getAsValuePtr()) &&
733  "Expected argument for a 'argument' position!");
734  assert(getAsValuePtr() == &getAssociatedValue() &&
735  "Associated value mismatch!");
736  return;
737  case IRP_CALL_SITE_ARGUMENT: {
738  assert((CBContext == nullptr) &&
739  "'call site argument' position must not have CallBaseContext!");
740  Use *U = getAsUsePtr();
741  assert(U && "Expected use for a 'call site argument' position!");
742  assert(isa<CallBase>(U->getUser()) &&
743  "Expected call base user for a 'call site argument' position!");
744  assert(cast<CallBase>(U->getUser())->isArgOperand(U) &&
745  "Expected call base argument operand for a 'call site argument' "
746  "position");
747  assert(cast<CallBase>(U->getUser())->getArgOperandNo(U) ==
748  unsigned(getCallSiteArgNo()) &&
749  "Argument number mismatch!");
750  assert(U->get() == &getAssociatedValue() && "Associated value mismatch!");
751  return;
752  }
753  }
754 #endif
755 }
756 
759  const AbstractAttribute &AA,
760  bool &UsedAssumedInformation) {
761  // First check all callbacks provided by outside AAs. If any of them returns
762  // a non-null value that is different from the associated value, or None, we
763  // assume it's simpliied.
764  for (auto &CB : SimplificationCallbacks.lookup(IRP)) {
765  Optional<Value *> SimplifiedV = CB(IRP, &AA, UsedAssumedInformation);
766  if (!SimplifiedV.hasValue())
767  return llvm::None;
768  if (isa_and_nonnull<Constant>(*SimplifiedV))
769  return cast<Constant>(*SimplifiedV);
770  return nullptr;
771  }
772  const auto &ValueSimplifyAA =
773  getAAFor<AAValueSimplify>(AA, IRP, DepClassTy::NONE);
774  Optional<Value *> SimplifiedV =
775  ValueSimplifyAA.getAssumedSimplifiedValue(*this);
776  bool IsKnown = ValueSimplifyAA.isAtFixpoint();
777  UsedAssumedInformation |= !IsKnown;
778  if (!SimplifiedV.hasValue()) {
779  recordDependence(ValueSimplifyAA, AA, DepClassTy::OPTIONAL);
780  return llvm::None;
781  }
782  if (isa_and_nonnull<UndefValue>(SimplifiedV.getValue())) {
783  recordDependence(ValueSimplifyAA, AA, DepClassTy::OPTIONAL);
784  return UndefValue::get(IRP.getAssociatedType());
785  }
786  Constant *CI = dyn_cast_or_null<Constant>(SimplifiedV.getValue());
787  if (CI)
788  CI = dyn_cast_or_null<Constant>(
789  AA::getWithType(*CI, *IRP.getAssociatedType()));
790  if (CI)
791  recordDependence(ValueSimplifyAA, AA, DepClassTy::OPTIONAL);
792  return CI;
793 }
794 
797  const AbstractAttribute *AA,
798  bool &UsedAssumedInformation) {
799  // First check all callbacks provided by outside AAs. If any of them returns
800  // a non-null value that is different from the associated value, or None, we
801  // assume it's simpliied.
802  for (auto &CB : SimplificationCallbacks.lookup(IRP))
803  return CB(IRP, AA, UsedAssumedInformation);
804 
805  // If no high-level/outside simplification occured, use AAValueSimplify.
806  const auto &ValueSimplifyAA =
807  getOrCreateAAFor<AAValueSimplify>(IRP, AA, DepClassTy::NONE);
808  Optional<Value *> SimplifiedV =
809  ValueSimplifyAA.getAssumedSimplifiedValue(*this);
810  bool IsKnown = ValueSimplifyAA.isAtFixpoint();
811  UsedAssumedInformation |= !IsKnown;
812  if (!SimplifiedV.hasValue()) {
813  if (AA)
814  recordDependence(ValueSimplifyAA, *AA, DepClassTy::OPTIONAL);
815  return llvm::None;
816  }
817  if (*SimplifiedV == nullptr)
818  return const_cast<Value *>(&IRP.getAssociatedValue());
819  if (Value *SimpleV =
820  AA::getWithType(**SimplifiedV, *IRP.getAssociatedType())) {
821  if (AA)
822  recordDependence(ValueSimplifyAA, *AA, DepClassTy::OPTIONAL);
823  return SimpleV;
824  }
825  return const_cast<Value *>(&IRP.getAssociatedValue());
826 }
827 
829  Optional<Value *> V, CallBase &CB, const AbstractAttribute &AA,
830  bool &UsedAssumedInformation) {
831  if (!V.hasValue())
832  return V;
833  if (*V == nullptr || isa<Constant>(*V))
834  return V;
835  if (auto *Arg = dyn_cast<Argument>(*V))
836  if (CB.getCalledFunction() == Arg->getParent())
837  if (!Arg->hasPointeeInMemoryValueAttr())
838  return getAssumedSimplified(
839  IRPosition::callsite_argument(CB, Arg->getArgNo()), AA,
840  UsedAssumedInformation);
841  return nullptr;
842 }
843 
845  // The abstract attributes are allocated via the BumpPtrAllocator Allocator,
846  // thus we cannot delete them. We can, and want to, destruct them though.
847  for (auto &DepAA : DG.SyntheticRoot.Deps) {
848  AbstractAttribute *AA = cast<AbstractAttribute>(DepAA.getPointer());
849  AA->~AbstractAttribute();
850  }
851 }
852 
854  const AAIsDead *FnLivenessAA,
855  bool &UsedAssumedInformation,
856  bool CheckBBLivenessOnly, DepClassTy DepClass) {
857  const IRPosition &IRP = AA.getIRPosition();
858  if (!Functions.count(IRP.getAnchorScope()))
859  return false;
860  return isAssumedDead(IRP, &AA, FnLivenessAA, UsedAssumedInformation,
861  CheckBBLivenessOnly, DepClass);
862 }
863 
865  const AbstractAttribute *QueryingAA,
866  const AAIsDead *FnLivenessAA,
867  bool &UsedAssumedInformation,
868  bool CheckBBLivenessOnly, DepClassTy DepClass) {
869  Instruction *UserI = dyn_cast<Instruction>(U.getUser());
870  if (!UserI)
871  return isAssumedDead(IRPosition::value(*U.get()), QueryingAA, FnLivenessAA,
872  UsedAssumedInformation, CheckBBLivenessOnly, DepClass);
873 
874  if (auto *CB = dyn_cast<CallBase>(UserI)) {
875  // For call site argument uses we can check if the argument is
876  // unused/dead.
877  if (CB->isArgOperand(&U)) {
878  const IRPosition &CSArgPos =
879  IRPosition::callsite_argument(*CB, CB->getArgOperandNo(&U));
880  return isAssumedDead(CSArgPos, QueryingAA, FnLivenessAA,
881  UsedAssumedInformation, CheckBBLivenessOnly,
882  DepClass);
883  }
884  } else if (ReturnInst *RI = dyn_cast<ReturnInst>(UserI)) {
885  const IRPosition &RetPos = IRPosition::returned(*RI->getFunction());
886  return isAssumedDead(RetPos, QueryingAA, FnLivenessAA,
887  UsedAssumedInformation, CheckBBLivenessOnly, DepClass);
888  } else if (PHINode *PHI = dyn_cast<PHINode>(UserI)) {
889  BasicBlock *IncomingBB = PHI->getIncomingBlock(U);
890  return isAssumedDead(*IncomingBB->getTerminator(), QueryingAA, FnLivenessAA,
891  UsedAssumedInformation, CheckBBLivenessOnly, DepClass);
892  }
893 
894  return isAssumedDead(IRPosition::value(*UserI), QueryingAA, FnLivenessAA,
895  UsedAssumedInformation, CheckBBLivenessOnly, DepClass);
896 }
897 
899  const AbstractAttribute *QueryingAA,
900  const AAIsDead *FnLivenessAA,
901  bool &UsedAssumedInformation,
902  bool CheckBBLivenessOnly, DepClassTy DepClass) {
903  const IRPosition::CallBaseContext *CBCtx =
904  QueryingAA ? QueryingAA->getCallBaseContext() : nullptr;
905 
906  if (ManifestAddedBlocks.contains(I.getParent()))
907  return false;
908 
909  if (!FnLivenessAA)
910  FnLivenessAA =
911  lookupAAFor<AAIsDead>(IRPosition::function(*I.getFunction(), CBCtx),
912  QueryingAA, DepClassTy::NONE);
913 
914  // If we have a context instruction and a liveness AA we use it.
915  if (FnLivenessAA &&
916  FnLivenessAA->getIRPosition().getAnchorScope() == I.getFunction() &&
917  FnLivenessAA->isAssumedDead(&I)) {
918  if (QueryingAA)
919  recordDependence(*FnLivenessAA, *QueryingAA, DepClass);
920  if (!FnLivenessAA->isKnownDead(&I))
921  UsedAssumedInformation = true;
922  return true;
923  }
924 
925  if (CheckBBLivenessOnly)
926  return false;
927 
928  const AAIsDead &IsDeadAA = getOrCreateAAFor<AAIsDead>(
929  IRPosition::value(I, CBCtx), QueryingAA, DepClassTy::NONE);
930  // Don't check liveness for AAIsDead.
931  if (QueryingAA == &IsDeadAA)
932  return false;
933 
934  if (IsDeadAA.isAssumedDead()) {
935  if (QueryingAA)
936  recordDependence(IsDeadAA, *QueryingAA, DepClass);
937  if (!IsDeadAA.isKnownDead())
938  UsedAssumedInformation = true;
939  return true;
940  }
941 
942  return false;
943 }
944 
946  const AbstractAttribute *QueryingAA,
947  const AAIsDead *FnLivenessAA,
948  bool &UsedAssumedInformation,
949  bool CheckBBLivenessOnly, DepClassTy DepClass) {
950  Instruction *CtxI = IRP.getCtxI();
951  if (CtxI &&
952  isAssumedDead(*CtxI, QueryingAA, FnLivenessAA, UsedAssumedInformation,
953  /* CheckBBLivenessOnly */ true,
954  CheckBBLivenessOnly ? DepClass : DepClassTy::OPTIONAL))
955  return true;
956 
957  if (CheckBBLivenessOnly)
958  return false;
959 
960  // If we haven't succeeded we query the specific liveness info for the IRP.
961  const AAIsDead *IsDeadAA;
963  IsDeadAA = &getOrCreateAAFor<AAIsDead>(
964  IRPosition::callsite_returned(cast<CallBase>(IRP.getAssociatedValue())),
965  QueryingAA, DepClassTy::NONE);
966  else
967  IsDeadAA = &getOrCreateAAFor<AAIsDead>(IRP, QueryingAA, DepClassTy::NONE);
968  // Don't check liveness for AAIsDead.
969  if (QueryingAA == IsDeadAA)
970  return false;
971 
972  if (IsDeadAA->isAssumedDead()) {
973  if (QueryingAA)
974  recordDependence(*IsDeadAA, *QueryingAA, DepClass);
975  if (!IsDeadAA->isKnownDead())
976  UsedAssumedInformation = true;
977  return true;
978  }
979 
980  return false;
981 }
982 
984  const AbstractAttribute *QueryingAA,
985  const AAIsDead *FnLivenessAA,
986  DepClassTy DepClass) {
987  if (!FnLivenessAA)
988  FnLivenessAA = lookupAAFor<AAIsDead>(IRPosition::function(*BB.getParent()),
989  QueryingAA, DepClassTy::NONE);
990  if (FnLivenessAA->isAssumedDead(&BB)) {
991  if (QueryingAA)
992  recordDependence(*FnLivenessAA, *QueryingAA, DepClass);
993  return true;
994  }
995 
996  return false;
997 }
998 
999 bool Attributor::checkForAllUses(function_ref<bool(const Use &, bool &)> Pred,
1000  const AbstractAttribute &QueryingAA,
1001  const Value &V, bool CheckBBLivenessOnly,
1002  DepClassTy LivenessDepClass) {
1003 
1004  // Check the trivial case first as it catches void values.
1005  if (V.use_empty())
1006  return true;
1007 
1008  const IRPosition &IRP = QueryingAA.getIRPosition();
1011 
1012  for (const Use &U : V.uses())
1013  Worklist.push_back(&U);
1014 
1015  LLVM_DEBUG(dbgs() << "[Attributor] Got " << Worklist.size()
1016  << " initial uses to check\n");
1017 
1018  const Function *ScopeFn = IRP.getAnchorScope();
1019  const auto *LivenessAA =
1020  ScopeFn ? &getAAFor<AAIsDead>(QueryingAA, IRPosition::function(*ScopeFn),
1022  : nullptr;
1023 
1024  while (!Worklist.empty()) {
1025  const Use *U = Worklist.pop_back_val();
1026  if (!Visited.insert(U).second)
1027  continue;
1028  LLVM_DEBUG(dbgs() << "[Attributor] Check use: " << **U << " in "
1029  << *U->getUser() << "\n");
1030  bool UsedAssumedInformation = false;
1031  if (isAssumedDead(*U, &QueryingAA, LivenessAA, UsedAssumedInformation,
1032  CheckBBLivenessOnly, LivenessDepClass)) {
1033  LLVM_DEBUG(dbgs() << "[Attributor] Dead use, skip!\n");
1034  continue;
1035  }
1036  if (U->getUser()->isDroppable()) {
1037  LLVM_DEBUG(dbgs() << "[Attributor] Droppable user, skip!\n");
1038  continue;
1039  }
1040 
1041  if (auto *SI = dyn_cast<StoreInst>(U->getUser())) {
1042  if (&SI->getOperandUse(0) == U) {
1043  SmallSetVector<Value *, 4> PotentialCopies;
1044  if (AA::getPotentialCopiesOfStoredValue(*this, *SI, PotentialCopies,
1045  QueryingAA,
1046  UsedAssumedInformation)) {
1047  LLVM_DEBUG(dbgs() << "[Attributor] Value is stored, continue with "
1048  << PotentialCopies.size()
1049  << " potential copies instead!\n");
1050  for (Value *PotentialCopy : PotentialCopies)
1051  for (const Use &U : PotentialCopy->uses())
1052  Worklist.push_back(&U);
1053  continue;
1054  }
1055  }
1056  }
1057 
1058  bool Follow = false;
1059  if (!Pred(*U, Follow))
1060  return false;
1061  if (!Follow)
1062  continue;
1063  for (const Use &UU : U->getUser()->uses())
1064  Worklist.push_back(&UU);
1065  }
1066 
1067  return true;
1068 }
1069 
1071  const AbstractAttribute &QueryingAA,
1072  bool RequireAllCallSites,
1073  bool &AllCallSitesKnown) {
1074  // We can try to determine information from
1075  // the call sites. However, this is only possible all call sites are known,
1076  // hence the function has internal linkage.
1077  const IRPosition &IRP = QueryingAA.getIRPosition();
1078  const Function *AssociatedFunction = IRP.getAssociatedFunction();
1079  if (!AssociatedFunction) {
1080  LLVM_DEBUG(dbgs() << "[Attributor] No function associated with " << IRP
1081  << "\n");
1082  AllCallSitesKnown = false;
1083  return false;
1084  }
1085 
1086  return checkForAllCallSites(Pred, *AssociatedFunction, RequireAllCallSites,
1087  &QueryingAA, AllCallSitesKnown);
1088 }
1089 
1091  const Function &Fn,
1092  bool RequireAllCallSites,
1093  const AbstractAttribute *QueryingAA,
1094  bool &AllCallSitesKnown) {
1095  if (RequireAllCallSites && !Fn.hasLocalLinkage()) {
1096  LLVM_DEBUG(
1097  dbgs()
1098  << "[Attributor] Function " << Fn.getName()
1099  << " has no internal linkage, hence not all call sites are known\n");
1100  AllCallSitesKnown = false;
1101  return false;
1102  }
1103 
1104  // If we do not require all call sites we might not see all.
1105  AllCallSitesKnown = RequireAllCallSites;
1106 
1108  for (unsigned u = 0; u < Uses.size(); ++u) {
1109  const Use &U = *Uses[u];
1110  LLVM_DEBUG(dbgs() << "[Attributor] Check use: " << *U << " in "
1111  << *U.getUser() << "\n");
1112  bool UsedAssumedInformation = false;
1113  if (isAssumedDead(U, QueryingAA, nullptr, UsedAssumedInformation,
1114  /* CheckBBLivenessOnly */ true)) {
1115  LLVM_DEBUG(dbgs() << "[Attributor] Dead use, skip!\n");
1116  continue;
1117  }
1118  if (ConstantExpr *CE = dyn_cast<ConstantExpr>(U.getUser())) {
1119  if (CE->isCast() && CE->getType()->isPointerTy() &&
1120  CE->getType()->getPointerElementType()->isFunctionTy()) {
1121  for (const Use &CEU : CE->uses())
1122  Uses.push_back(&CEU);
1123  continue;
1124  }
1125  }
1126 
1127  AbstractCallSite ACS(&U);
1128  if (!ACS) {
1129  LLVM_DEBUG(dbgs() << "[Attributor] Function " << Fn.getName()
1130  << " has non call site use " << *U.get() << " in "
1131  << *U.getUser() << "\n");
1132  // BlockAddress users are allowed.
1133  if (isa<BlockAddress>(U.getUser()))
1134  continue;
1135  return false;
1136  }
1137 
1138  const Use *EffectiveUse =
1139  ACS.isCallbackCall() ? &ACS.getCalleeUseForCallback() : &U;
1140  if (!ACS.isCallee(EffectiveUse)) {
1141  if (!RequireAllCallSites)
1142  continue;
1143  LLVM_DEBUG(dbgs() << "[Attributor] User " << EffectiveUse->getUser()
1144  << " is an invalid use of " << Fn.getName() << "\n");
1145  return false;
1146  }
1147 
1148  // Make sure the arguments that can be matched between the call site and the
1149  // callee argee on their type. It is unlikely they do not and it doesn't
1150  // make sense for all attributes to know/care about this.
1151  assert(&Fn == ACS.getCalledFunction() && "Expected known callee");
1152  unsigned MinArgsParams =
1153  std::min(size_t(ACS.getNumArgOperands()), Fn.arg_size());
1154  for (unsigned u = 0; u < MinArgsParams; ++u) {
1155  Value *CSArgOp = ACS.getCallArgOperand(u);
1156  if (CSArgOp && Fn.getArg(u)->getType() != CSArgOp->getType()) {
1157  LLVM_DEBUG(
1158  dbgs() << "[Attributor] Call site / callee argument type mismatch ["
1159  << u << "@" << Fn.getName() << ": "
1160  << *Fn.getArg(u)->getType() << " vs. "
1161  << *ACS.getCallArgOperand(u)->getType() << "\n");
1162  return false;
1163  }
1164  }
1165 
1166  if (Pred(ACS))
1167  continue;
1168 
1169  LLVM_DEBUG(dbgs() << "[Attributor] Call site callback failed for "
1170  << *ACS.getInstruction() << "\n");
1171  return false;
1172  }
1173 
1174  return true;
1175 }
1176 
1177 bool Attributor::shouldPropagateCallBaseContext(const IRPosition &IRP) {
1178  // TODO: Maintain a cache of Values that are
1179  // on the pathway from a Argument to a Instruction that would effect the
1180  // liveness/return state etc.
1181  return EnableCallSiteSpecific;
1182 }
1183 
1185  function_ref<bool(Value &, const SmallSetVector<ReturnInst *, 4> &)> Pred,
1186  const AbstractAttribute &QueryingAA) {
1187 
1188  const IRPosition &IRP = QueryingAA.getIRPosition();
1189  // Since we need to provide return instructions we have to have an exact
1190  // definition.
1191  const Function *AssociatedFunction = IRP.getAssociatedFunction();
1192  if (!AssociatedFunction)
1193  return false;
1194 
1195  // If this is a call site query we use the call site specific return values
1196  // and liveness information.
1197  // TODO: use the function scope once we have call site AAReturnedValues.
1198  const IRPosition &QueryIRP = IRPosition::function(*AssociatedFunction);
1199  const auto &AARetVal =
1200  getAAFor<AAReturnedValues>(QueryingAA, QueryIRP, DepClassTy::REQUIRED);
1201  if (!AARetVal.getState().isValidState())
1202  return false;
1203 
1204  return AARetVal.checkForAllReturnedValuesAndReturnInsts(Pred);
1205 }
1206 
1208  function_ref<bool(Value &)> Pred, const AbstractAttribute &QueryingAA) {
1209 
1210  const IRPosition &IRP = QueryingAA.getIRPosition();
1211  const Function *AssociatedFunction = IRP.getAssociatedFunction();
1212  if (!AssociatedFunction)
1213  return false;
1214 
1215  // TODO: use the function scope once we have call site AAReturnedValues.
1216  const IRPosition &QueryIRP = IRPosition::function(
1217  *AssociatedFunction, QueryingAA.getCallBaseContext());
1218  const auto &AARetVal =
1219  getAAFor<AAReturnedValues>(QueryingAA, QueryIRP, DepClassTy::REQUIRED);
1220  if (!AARetVal.getState().isValidState())
1221  return false;
1222 
1223  return AARetVal.checkForAllReturnedValuesAndReturnInsts(
1224  [&](Value &RV, const SmallSetVector<ReturnInst *, 4> &) {
1225  return Pred(RV);
1226  });
1227 }
1228 
1230  Attributor *A, InformationCache::OpcodeInstMapTy &OpcodeInstMap,
1231  function_ref<bool(Instruction &)> Pred, const AbstractAttribute *QueryingAA,
1232  const AAIsDead *LivenessAA, const ArrayRef<unsigned> &Opcodes,
1233  bool &UsedAssumedInformation, bool CheckBBLivenessOnly = false,
1234  bool CheckPotentiallyDead = false) {
1235  for (unsigned Opcode : Opcodes) {
1236  // Check if we have instructions with this opcode at all first.
1237  auto *Insts = OpcodeInstMap.lookup(Opcode);
1238  if (!Insts)
1239  continue;
1240 
1241  for (Instruction *I : *Insts) {
1242  // Skip dead instructions.
1243  if (A && !CheckPotentiallyDead &&
1244  A->isAssumedDead(IRPosition::value(*I), QueryingAA, LivenessAA,
1245  UsedAssumedInformation, CheckBBLivenessOnly))
1246  continue;
1247 
1248  if (!Pred(*I))
1249  return false;
1250  }
1251  }
1252  return true;
1253 }
1254 
1256  const AbstractAttribute &QueryingAA,
1257  const ArrayRef<unsigned> &Opcodes,
1258  bool &UsedAssumedInformation,
1259  bool CheckBBLivenessOnly,
1260  bool CheckPotentiallyDead) {
1261 
1262  const IRPosition &IRP = QueryingAA.getIRPosition();
1263  // Since we need to provide instructions we have to have an exact definition.
1264  const Function *AssociatedFunction = IRP.getAssociatedFunction();
1265  if (!AssociatedFunction)
1266  return false;
1267 
1268  if (AssociatedFunction->isDeclaration())
1269  return false;
1270 
1271  // TODO: use the function scope once we have call site AAReturnedValues.
1272  const IRPosition &QueryIRP = IRPosition::function(*AssociatedFunction);
1273  const auto *LivenessAA =
1274  (CheckBBLivenessOnly || CheckPotentiallyDead)
1275  ? nullptr
1276  : &(getAAFor<AAIsDead>(QueryingAA, QueryIRP, DepClassTy::NONE));
1277 
1278  auto &OpcodeInstMap =
1279  InfoCache.getOpcodeInstMapForFunction(*AssociatedFunction);
1280  if (!checkForAllInstructionsImpl(this, OpcodeInstMap, Pred, &QueryingAA,
1281  LivenessAA, Opcodes, UsedAssumedInformation,
1282  CheckBBLivenessOnly, CheckPotentiallyDead))
1283  return false;
1284 
1285  return true;
1286 }
1287 
1289  function_ref<bool(Instruction &)> Pred, AbstractAttribute &QueryingAA,
1290  bool &UsedAssumedInformation) {
1291 
1292  const Function *AssociatedFunction =
1293  QueryingAA.getIRPosition().getAssociatedFunction();
1294  if (!AssociatedFunction)
1295  return false;
1296 
1297  // TODO: use the function scope once we have call site AAReturnedValues.
1298  const IRPosition &QueryIRP = IRPosition::function(*AssociatedFunction);
1299  const auto &LivenessAA =
1300  getAAFor<AAIsDead>(QueryingAA, QueryIRP, DepClassTy::NONE);
1301 
1302  for (Instruction *I :
1303  InfoCache.getReadOrWriteInstsForFunction(*AssociatedFunction)) {
1304  // Skip dead instructions.
1305  if (isAssumedDead(IRPosition::value(*I), &QueryingAA, &LivenessAA,
1306  UsedAssumedInformation))
1307  continue;
1308 
1309  if (!Pred(*I))
1310  return false;
1311  }
1312 
1313  return true;
1314 }
1315 
1316 void Attributor::runTillFixpoint() {
1317  TimeTraceScope TimeScope("Attributor::runTillFixpoint");
1318  LLVM_DEBUG(dbgs() << "[Attributor] Identified and initialized "
1319  << DG.SyntheticRoot.Deps.size()
1320  << " abstract attributes.\n");
1321 
1322  // Now that all abstract attributes are collected and initialized we start
1323  // the abstract analysis.
1324 
1325  unsigned IterationCounter = 1;
1326  unsigned MaxFixedPointIterations;
1327  if (MaxFixpointIterations)
1328  MaxFixedPointIterations = MaxFixpointIterations.getValue();
1329  else
1330  MaxFixedPointIterations = SetFixpointIterations;
1331 
1333  SetVector<AbstractAttribute *> Worklist, InvalidAAs;
1334  Worklist.insert(DG.SyntheticRoot.begin(), DG.SyntheticRoot.end());
1335 
1336  do {
1337  // Remember the size to determine new attributes.
1338  size_t NumAAs = DG.SyntheticRoot.Deps.size();
1339  LLVM_DEBUG(dbgs() << "\n\n[Attributor] #Iteration: " << IterationCounter
1340  << ", Worklist size: " << Worklist.size() << "\n");
1341 
1342  // For invalid AAs we can fix dependent AAs that have a required dependence,
1343  // thereby folding long dependence chains in a single step without the need
1344  // to run updates.
1345  for (unsigned u = 0; u < InvalidAAs.size(); ++u) {
1346  AbstractAttribute *InvalidAA = InvalidAAs[u];
1347 
1348  // Check the dependences to fast track invalidation.
1349  LLVM_DEBUG(dbgs() << "[Attributor] InvalidAA: " << *InvalidAA << " has "
1350  << InvalidAA->Deps.size()
1351  << " required & optional dependences\n");
1352  while (!InvalidAA->Deps.empty()) {
1353  const auto &Dep = InvalidAA->Deps.back();
1354  InvalidAA->Deps.pop_back();
1355  AbstractAttribute *DepAA = cast<AbstractAttribute>(Dep.getPointer());
1356  if (Dep.getInt() == unsigned(DepClassTy::OPTIONAL)) {
1357  Worklist.insert(DepAA);
1358  continue;
1359  }
1361  assert(DepAA->getState().isAtFixpoint() && "Expected fixpoint state!");
1362  if (!DepAA->getState().isValidState())
1363  InvalidAAs.insert(DepAA);
1364  else
1365  ChangedAAs.push_back(DepAA);
1366  }
1367  }
1368 
1369  // Add all abstract attributes that are potentially dependent on one that
1370  // changed to the work list.
1371  for (AbstractAttribute *ChangedAA : ChangedAAs)
1372  while (!ChangedAA->Deps.empty()) {
1373  Worklist.insert(
1374  cast<AbstractAttribute>(ChangedAA->Deps.back().getPointer()));
1375  ChangedAA->Deps.pop_back();
1376  }
1377 
1378  LLVM_DEBUG(dbgs() << "[Attributor] #Iteration: " << IterationCounter
1379  << ", Worklist+Dependent size: " << Worklist.size()
1380  << "\n");
1381 
1382  // Reset the changed and invalid set.
1383  ChangedAAs.clear();
1384  InvalidAAs.clear();
1385 
1386  // Update all abstract attribute in the work list and record the ones that
1387  // changed.
1388  for (AbstractAttribute *AA : Worklist) {
1389  const auto &AAState = AA->getState();
1390  if (!AAState.isAtFixpoint())
1391  if (updateAA(*AA) == ChangeStatus::CHANGED)
1392  ChangedAAs.push_back(AA);
1393 
1394  // Use the InvalidAAs vector to propagate invalid states fast transitively
1395  // without requiring updates.
1396  if (!AAState.isValidState())
1397  InvalidAAs.insert(AA);
1398  }
1399 
1400  // Add attributes to the changed set if they have been created in the last
1401  // iteration.
1402  ChangedAAs.append(DG.SyntheticRoot.begin() + NumAAs,
1403  DG.SyntheticRoot.end());
1404 
1405  // Reset the work list and repopulate with the changed abstract attributes.
1406  // Note that dependent ones are added above.
1407  Worklist.clear();
1408  Worklist.insert(ChangedAAs.begin(), ChangedAAs.end());
1409 
1410  } while (!Worklist.empty() && (IterationCounter++ < MaxFixedPointIterations ||
1412 
1413  LLVM_DEBUG(dbgs() << "\n[Attributor] Fixpoint iteration done after: "
1414  << IterationCounter << "/" << MaxFixpointIterations
1415  << " iterations\n");
1416 
1417  // Reset abstract arguments not settled in a sound fixpoint by now. This
1418  // happens when we stopped the fixpoint iteration early. Note that only the
1419  // ones marked as "changed" *and* the ones transitively depending on them
1420  // need to be reverted to a pessimistic state. Others might not be in a
1421  // fixpoint state but we can use the optimistic results for them anyway.
1423  for (unsigned u = 0; u < ChangedAAs.size(); u++) {
1424  AbstractAttribute *ChangedAA = ChangedAAs[u];
1425  if (!Visited.insert(ChangedAA).second)
1426  continue;
1427 
1428  AbstractState &State = ChangedAA->getState();
1429  if (!State.isAtFixpoint()) {
1431 
1432  NumAttributesTimedOut++;
1433  }
1434 
1435  while (!ChangedAA->Deps.empty()) {
1436  ChangedAAs.push_back(
1437  cast<AbstractAttribute>(ChangedAA->Deps.back().getPointer()));
1438  ChangedAA->Deps.pop_back();
1439  }
1440  }
1441 
1442  LLVM_DEBUG({
1443  if (!Visited.empty())
1444  dbgs() << "\n[Attributor] Finalized " << Visited.size()
1445  << " abstract attributes.\n";
1446  });
1447 
1449  IterationCounter != MaxFixedPointIterations) {
1450  errs() << "\n[Attributor] Fixpoint iteration done after: "
1451  << IterationCounter << "/" << MaxFixedPointIterations
1452  << " iterations\n";
1453  llvm_unreachable("The fixpoint was not reached with exactly the number of "
1454  "specified iterations!");
1455  }
1456 }
1457 
1458 ChangeStatus Attributor::manifestAttributes() {
1459  TimeTraceScope TimeScope("Attributor::manifestAttributes");
1460  size_t NumFinalAAs = DG.SyntheticRoot.Deps.size();
1461 
1462  unsigned NumManifested = 0;
1463  unsigned NumAtFixpoint = 0;
1464  ChangeStatus ManifestChange = ChangeStatus::UNCHANGED;
1465  for (auto &DepAA : DG.SyntheticRoot.Deps) {
1466  AbstractAttribute *AA = cast<AbstractAttribute>(DepAA.getPointer());
1467  AbstractState &State = AA->getState();
1468 
1469  // If there is not already a fixpoint reached, we can now take the
1470  // optimistic state. This is correct because we enforced a pessimistic one
1471  // on abstract attributes that were transitively dependent on a changed one
1472  // already above.
1473  if (!State.isAtFixpoint())
1475 
1476  // We must not manifest Attributes that use Callbase info.
1477  if (AA->hasCallBaseContext())
1478  continue;
1479  // If the state is invalid, we do not try to manifest it.
1480  if (!State.isValidState())
1481  continue;
1482 
1483  // Skip dead code.
1484  bool UsedAssumedInformation = false;
1485  if (isAssumedDead(*AA, nullptr, UsedAssumedInformation,
1486  /* CheckBBLivenessOnly */ true))
1487  continue;
1488  // Check if the manifest debug counter that allows skipping manifestation of
1489  // AAs
1490  if (!DebugCounter::shouldExecute(ManifestDBGCounter))
1491  continue;
1492  // Manifest the state and record if we changed the IR.
1493  ChangeStatus LocalChange = AA->manifest(*this);
1494  if (LocalChange == ChangeStatus::CHANGED && AreStatisticsEnabled())
1495  AA->trackStatistics();
1496  LLVM_DEBUG(dbgs() << "[Attributor] Manifest " << LocalChange << " : " << *AA
1497  << "\n");
1498 
1499  ManifestChange = ManifestChange | LocalChange;
1500 
1501  NumAtFixpoint++;
1502  NumManifested += (LocalChange == ChangeStatus::CHANGED);
1503  }
1504 
1505  (void)NumManifested;
1506  (void)NumAtFixpoint;
1507  LLVM_DEBUG(dbgs() << "\n[Attributor] Manifested " << NumManifested
1508  << " arguments while " << NumAtFixpoint
1509  << " were in a valid fixpoint state\n");
1510 
1511  NumAttributesManifested += NumManifested;
1512  NumAttributesValidFixpoint += NumAtFixpoint;
1513 
1514  (void)NumFinalAAs;
1515  if (NumFinalAAs != DG.SyntheticRoot.Deps.size()) {
1516  for (unsigned u = NumFinalAAs; u < DG.SyntheticRoot.Deps.size(); ++u)
1517  errs() << "Unexpected abstract attribute: "
1518  << cast<AbstractAttribute>(DG.SyntheticRoot.Deps[u].getPointer())
1519  << " :: "
1520  << cast<AbstractAttribute>(DG.SyntheticRoot.Deps[u].getPointer())
1521  ->getIRPosition()
1522  .getAssociatedValue()
1523  << "\n";
1524  llvm_unreachable("Expected the final number of abstract attributes to "
1525  "remain unchanged!");
1526  }
1527  return ManifestChange;
1528 }
1529 
1530 void Attributor::identifyDeadInternalFunctions() {
1531  // Early exit if we don't intend to delete functions.
1532  if (!DeleteFns)
1533  return;
1534 
1535  // Identify dead internal functions and delete them. This happens outside
1536  // the other fixpoint analysis as we might treat potentially dead functions
1537  // as live to lower the number of iterations. If they happen to be dead, the
1538  // below fixpoint loop will identify and eliminate them.
1539  SmallVector<Function *, 8> InternalFns;
1540  for (Function *F : Functions)
1541  if (F->hasLocalLinkage())
1542  InternalFns.push_back(F);
1543 
1544  SmallPtrSet<Function *, 8> LiveInternalFns;
1545  bool FoundLiveInternal = true;
1546  while (FoundLiveInternal) {
1547  FoundLiveInternal = false;
1548  for (unsigned u = 0, e = InternalFns.size(); u < e; ++u) {
1549  Function *F = InternalFns[u];
1550  if (!F)
1551  continue;
1552 
1553  bool AllCallSitesKnown;
1555  [&](AbstractCallSite ACS) {
1557  return ToBeDeletedFunctions.count(Callee) ||
1558  (Functions.count(Callee) && Callee->hasLocalLinkage() &&
1559  !LiveInternalFns.count(Callee));
1560  },
1561  *F, true, nullptr, AllCallSitesKnown)) {
1562  continue;
1563  }
1564 
1565  LiveInternalFns.insert(F);
1566  InternalFns[u] = nullptr;
1567  FoundLiveInternal = true;
1568  }
1569  }
1570 
1571  for (unsigned u = 0, e = InternalFns.size(); u < e; ++u)
1572  if (Function *F = InternalFns[u])
1573  ToBeDeletedFunctions.insert(F);
1574 }
1575 
1576 ChangeStatus Attributor::cleanupIR() {
1577  TimeTraceScope TimeScope("Attributor::cleanupIR");
1578  // Delete stuff at the end to avoid invalid references and a nice order.
1579  LLVM_DEBUG(dbgs() << "\n[Attributor] Delete/replace at least "
1580  << ToBeDeletedFunctions.size() << " functions and "
1581  << ToBeDeletedBlocks.size() << " blocks and "
1582  << ToBeDeletedInsts.size() << " instructions and "
1583  << ToBeChangedValues.size() << " values and "
1584  << ToBeChangedUses.size() << " uses. "
1585  << "Preserve manifest added " << ManifestAddedBlocks.size()
1586  << " blocks\n");
1587 
1589  SmallVector<Instruction *, 32> TerminatorsToFold;
1590 
1591  auto ReplaceUse = [&](Use *U, Value *NewV) {
1592  Value *OldV = U->get();
1593 
1594  // If we plan to replace NewV we need to update it at this point.
1595  do {
1596  const auto &Entry = ToBeChangedValues.lookup(NewV);
1597  if (!Entry.first)
1598  break;
1599  NewV = Entry.first;
1600  } while (true);
1601 
1602  // Do not replace uses in returns if the value is a must-tail call we will
1603  // not delete.
1604  if (auto *RI = dyn_cast<ReturnInst>(U->getUser())) {
1605  if (auto *CI = dyn_cast<CallInst>(OldV->stripPointerCasts()))
1606  if (CI->isMustTailCall() &&
1607  (!ToBeDeletedInsts.count(CI) || !isRunOn(*CI->getCaller())))
1608  return;
1609  // If we rewrite a return and the new value is not an argument, strip the
1610  // `returned` attribute as it is wrong now.
1611  if (!isa<Argument>(NewV))
1612  for (auto &Arg : RI->getFunction()->args())
1613  Arg.removeAttr(Attribute::Returned);
1614  }
1615 
1616  // Do not perform call graph altering changes outside the SCC.
1617  if (auto *CB = dyn_cast<CallBase>(U->getUser()))
1618  if (CB->isCallee(U) && !isRunOn(*CB->getCaller()))
1619  return;
1620 
1621  LLVM_DEBUG(dbgs() << "Use " << *NewV << " in " << *U->getUser()
1622  << " instead of " << *OldV << "\n");
1623  U->set(NewV);
1624 
1625  if (Instruction *I = dyn_cast<Instruction>(OldV)) {
1626  CGModifiedFunctions.insert(I->getFunction());
1627  if (!isa<PHINode>(I) && !ToBeDeletedInsts.count(I) &&
1629  DeadInsts.push_back(I);
1630  }
1631  if (isa<UndefValue>(NewV) && isa<CallBase>(U->getUser())) {
1632  auto *CB = cast<CallBase>(U->getUser());
1633  if (CB->isArgOperand(U)) {
1634  unsigned Idx = CB->getArgOperandNo(U);
1635  CB->removeParamAttr(Idx, Attribute::NoUndef);
1636  Function *Fn = CB->getCalledFunction();
1637  if (Fn && Fn->arg_size() > Idx)
1638  Fn->removeParamAttr(Idx, Attribute::NoUndef);
1639  }
1640  }
1641  if (isa<Constant>(NewV) && isa<BranchInst>(U->getUser())) {
1642  Instruction *UserI = cast<Instruction>(U->getUser());
1643  if (isa<UndefValue>(NewV)) {
1644  ToBeChangedToUnreachableInsts.insert(UserI);
1645  } else {
1646  TerminatorsToFold.push_back(UserI);
1647  }
1648  }
1649  };
1650 
1651  for (auto &It : ToBeChangedUses) {
1652  Use *U = It.first;
1653  Value *NewV = It.second;
1654  ReplaceUse(U, NewV);
1655  }
1656 
1658  for (auto &It : ToBeChangedValues) {
1659  Value *OldV = It.first;
1660  auto &Entry = It.second;
1661  Value *NewV = Entry.first;
1662  Uses.clear();
1663  for (auto &U : OldV->uses())
1664  if (Entry.second || !U.getUser()->isDroppable())
1665  Uses.push_back(&U);
1666  for (Use *U : Uses)
1667  ReplaceUse(U, NewV);
1668  }
1669 
1670  for (auto &V : InvokeWithDeadSuccessor)
1671  if (InvokeInst *II = dyn_cast_or_null<InvokeInst>(V)) {
1672  assert(isRunOn(*II->getFunction()) &&
1673  "Cannot replace an invoke outside the current SCC!");
1674  bool UnwindBBIsDead = II->hasFnAttr(Attribute::NoUnwind);
1675  bool NormalBBIsDead = II->hasFnAttr(Attribute::NoReturn);
1676  bool Invoke2CallAllowed =
1677  !AAIsDead::mayCatchAsynchronousExceptions(*II->getFunction());
1678  assert((UnwindBBIsDead || NormalBBIsDead) &&
1679  "Invoke does not have dead successors!");
1680  BasicBlock *BB = II->getParent();
1681  BasicBlock *NormalDestBB = II->getNormalDest();
1682  if (UnwindBBIsDead) {
1683  Instruction *NormalNextIP = &NormalDestBB->front();
1684  if (Invoke2CallAllowed) {
1685  changeToCall(II);
1686  NormalNextIP = BB->getTerminator();
1687  }
1688  if (NormalBBIsDead)
1689  ToBeChangedToUnreachableInsts.insert(NormalNextIP);
1690  } else {
1691  assert(NormalBBIsDead && "Broken invariant!");
1692  if (!NormalDestBB->getUniquePredecessor())
1693  NormalDestBB = SplitBlockPredecessors(NormalDestBB, {BB}, ".dead");
1694  ToBeChangedToUnreachableInsts.insert(&NormalDestBB->front());
1695  }
1696  }
1697  for (Instruction *I : TerminatorsToFold) {
1698  if (!isRunOn(*I->getFunction()))
1699  continue;
1700  CGModifiedFunctions.insert(I->getFunction());
1701  ConstantFoldTerminator(I->getParent());
1702  }
1703  for (auto &V : ToBeChangedToUnreachableInsts)
1704  if (Instruction *I = dyn_cast_or_null<Instruction>(V)) {
1705  if (!isRunOn(*I->getFunction()))
1706  continue;
1707  CGModifiedFunctions.insert(I->getFunction());
1709  }
1710 
1711  for (auto &V : ToBeDeletedInsts) {
1712  if (Instruction *I = dyn_cast_or_null<Instruction>(V)) {
1713  if (auto *CB = dyn_cast<CallBase>(I)) {
1714  if (!isRunOn(*I->getFunction()))
1715  continue;
1716  if (!isa<IntrinsicInst>(CB))
1717  CGUpdater.removeCallSite(*CB);
1718  }
1719  I->dropDroppableUses();
1720  CGModifiedFunctions.insert(I->getFunction());
1721  if (!I->getType()->isVoidTy())
1722  I->replaceAllUsesWith(UndefValue::get(I->getType()));
1723  if (!isa<PHINode>(I) && isInstructionTriviallyDead(I))
1724  DeadInsts.push_back(I);
1725  else
1726  I->eraseFromParent();
1727  }
1728  }
1729 
1730  llvm::erase_if(DeadInsts, [&](WeakTrackingVH I) {
1731  return !I || !isRunOn(*cast<Instruction>(I)->getFunction());
1732  });
1733 
1734  LLVM_DEBUG({
1735  dbgs() << "[Attributor] DeadInsts size: " << DeadInsts.size() << "\n";
1736  for (auto &I : DeadInsts)
1737  if (I)
1738  dbgs() << " - " << *I << "\n";
1739  });
1740 
1742 
1743  if (unsigned NumDeadBlocks = ToBeDeletedBlocks.size()) {
1744  SmallVector<BasicBlock *, 8> ToBeDeletedBBs;
1745  ToBeDeletedBBs.reserve(NumDeadBlocks);
1746  for (BasicBlock *BB : ToBeDeletedBlocks) {
1747  assert(isRunOn(*BB->getParent()) &&
1748  "Cannot delete a block outside the current SCC!");
1749  CGModifiedFunctions.insert(BB->getParent());
1750  // Do not delete BBs added during manifests of AAs.
1751  if (ManifestAddedBlocks.contains(BB))
1752  continue;
1753  ToBeDeletedBBs.push_back(BB);
1754  }
1755  // Actually we do not delete the blocks but squash them into a single
1756  // unreachable but untangling branches that jump here is something we need
1757  // to do in a more generic way.
1758  DetatchDeadBlocks(ToBeDeletedBBs, nullptr);
1759  }
1760 
1761  identifyDeadInternalFunctions();
1762 
1763  // Rewrite the functions as requested during manifest.
1764  ChangeStatus ManifestChange = rewriteFunctionSignatures(CGModifiedFunctions);
1765 
1766  for (Function *Fn : CGModifiedFunctions)
1767  if (!ToBeDeletedFunctions.count(Fn) && Functions.count(Fn))
1768  CGUpdater.reanalyzeFunction(*Fn);
1769 
1770  for (Function *Fn : ToBeDeletedFunctions) {
1771  if (!Functions.count(Fn))
1772  continue;
1773  CGUpdater.removeFunction(*Fn);
1774  }
1775 
1776  if (!ToBeChangedUses.empty())
1777  ManifestChange = ChangeStatus::CHANGED;
1778 
1779  if (!ToBeChangedToUnreachableInsts.empty())
1780  ManifestChange = ChangeStatus::CHANGED;
1781 
1782  if (!ToBeDeletedFunctions.empty())
1783  ManifestChange = ChangeStatus::CHANGED;
1784 
1785  if (!ToBeDeletedBlocks.empty())
1786  ManifestChange = ChangeStatus::CHANGED;
1787 
1788  if (!ToBeDeletedInsts.empty())
1789  ManifestChange = ChangeStatus::CHANGED;
1790 
1791  if (!InvokeWithDeadSuccessor.empty())
1792  ManifestChange = ChangeStatus::CHANGED;
1793 
1794  if (!DeadInsts.empty())
1795  ManifestChange = ChangeStatus::CHANGED;
1796 
1797  NumFnDeleted += ToBeDeletedFunctions.size();
1798 
1799  LLVM_DEBUG(dbgs() << "[Attributor] Deleted " << ToBeDeletedFunctions.size()
1800  << " functions after manifest.\n");
1801 
1802 #ifdef EXPENSIVE_CHECKS
1803  for (Function *F : Functions) {
1804  if (ToBeDeletedFunctions.count(F))
1805  continue;
1806  assert(!verifyFunction(*F, &errs()) && "Module verification failed!");
1807  }
1808 #endif
1809 
1810  return ManifestChange;
1811 }
1812 
1814  TimeTraceScope TimeScope("Attributor::run");
1815  AttributorCallGraph ACallGraph(*this);
1816 
1817  if (PrintCallGraph)
1818  ACallGraph.populateAll();
1819 
1820  Phase = AttributorPhase::UPDATE;
1821  runTillFixpoint();
1822 
1823  // dump graphs on demand
1824  if (DumpDepGraph)
1825  DG.dumpGraph();
1826 
1827  if (ViewDepGraph)
1828  DG.viewGraph();
1829 
1830  if (PrintDependencies)
1831  DG.print();
1832 
1833  Phase = AttributorPhase::MANIFEST;
1834  ChangeStatus ManifestChange = manifestAttributes();
1835 
1836  Phase = AttributorPhase::CLEANUP;
1837  ChangeStatus CleanupChange = cleanupIR();
1838 
1839  if (PrintCallGraph)
1840  ACallGraph.print();
1841 
1842  return ManifestChange | CleanupChange;
1843 }
1844 
1845 ChangeStatus Attributor::updateAA(AbstractAttribute &AA) {
1846  TimeTraceScope TimeScope(
1848  "::updateAA");
1849  assert(Phase == AttributorPhase::UPDATE &&
1850  "We can update AA only in the update stage!");
1851 
1852  // Use a new dependence vector for this update.
1853  DependenceVector DV;
1854  DependenceStack.push_back(&DV);
1855 
1856  auto &AAState = AA.getState();
1858  bool UsedAssumedInformation = false;
1859  if (!isAssumedDead(AA, nullptr, UsedAssumedInformation,
1860  /* CheckBBLivenessOnly */ true))
1861  CS = AA.update(*this);
1862 
1863  if (DV.empty()) {
1864  // If the attribute did not query any non-fix information, the state
1865  // will not change and we can indicate that right away.
1866  AAState.indicateOptimisticFixpoint();
1867  }
1868 
1869  if (!AAState.isAtFixpoint())
1870  rememberDependences();
1871 
1872  // Verify the stack was used properly, that is we pop the dependence vector we
1873  // put there earlier.
1874  DependenceVector *PoppedDV = DependenceStack.pop_back_val();
1875  (void)PoppedDV;
1876  assert(PoppedDV == &DV && "Inconsistent usage of the dependence stack!");
1877 
1878  return CS;
1879 }
1880 
1882  assert(!F.isDeclaration() && "Cannot create a wrapper around a declaration!");
1883 
1884  Module &M = *F.getParent();
1885  LLVMContext &Ctx = M.getContext();
1886  FunctionType *FnTy = F.getFunctionType();
1887 
1888  Function *Wrapper =
1889  Function::Create(FnTy, F.getLinkage(), F.getAddressSpace(), F.getName());
1890  F.setName(""); // set the inside function anonymous
1891  M.getFunctionList().insert(F.getIterator(), Wrapper);
1892 
1893  F.setLinkage(GlobalValue::InternalLinkage);
1894 
1895  F.replaceAllUsesWith(Wrapper);
1896  assert(F.use_empty() && "Uses remained after wrapper was created!");
1897 
1898  // Move the COMDAT section to the wrapper.
1899  // TODO: Check if we need to keep it for F as well.
1900  Wrapper->setComdat(F.getComdat());
1901  F.setComdat(nullptr);
1902 
1903  // Copy all metadata and attributes but keep them on F as well.
1905  F.getAllMetadata(MDs);
1906  for (auto MDIt : MDs)
1907  Wrapper->addMetadata(MDIt.first, *MDIt.second);
1908  Wrapper->setAttributes(F.getAttributes());
1909 
1910  // Create the call in the wrapper.
1911  BasicBlock *EntryBB = BasicBlock::Create(Ctx, "entry", Wrapper);
1912 
1914  Argument *FArgIt = F.arg_begin();
1915  for (Argument &Arg : Wrapper->args()) {
1916  Args.push_back(&Arg);
1917  Arg.setName((FArgIt++)->getName());
1918  }
1919 
1920  CallInst *CI = CallInst::Create(&F, Args, "", EntryBB);
1921  CI->setTailCall(true);
1922  CI->addAttribute(AttributeList::FunctionIndex, Attribute::NoInline);
1923  ReturnInst::Create(Ctx, CI->getType()->isVoidTy() ? nullptr : CI, EntryBB);
1924 
1925  NumFnShallowWrappersCreated++;
1926 }
1927 
1929  if (F.isDeclaration() || F.hasLocalLinkage() ||
1930  GlobalValue::isInterposableLinkage(F.getLinkage()))
1931  return false;
1932  return true;
1933 }
1934 
1936  if (!AllowDeepWrapper && !Force)
1937  return nullptr;
1938  if (!isInternalizable(F))
1939  return nullptr;
1940 
1941  SmallPtrSet<Function *, 2> FnSet = {&F};
1942  DenseMap<Function *, Function *> InternalizedFns;
1943  internalizeFunctions(FnSet, InternalizedFns);
1944 
1945  return InternalizedFns[&F];
1946 }
1947 
1950  for (Function *F : FnSet)
1952  return false;
1953 
1954  FnMap.clear();
1955  // Generate the internalized version of each function.
1956  for (Function *F : FnSet) {
1957  Module &M = *F->getParent();
1958  FunctionType *FnTy = F->getFunctionType();
1959 
1960  // Create a copy of the current function
1961  Function *Copied =
1962  Function::Create(FnTy, F->getLinkage(), F->getAddressSpace(),
1963  F->getName() + ".internalized");
1964  ValueToValueMapTy VMap;
1965  auto *NewFArgIt = Copied->arg_begin();
1966  for (auto &Arg : F->args()) {
1967  auto ArgName = Arg.getName();
1968  NewFArgIt->setName(ArgName);
1969  VMap[&Arg] = &(*NewFArgIt++);
1970  }
1972 
1973  // Copy the body of the original function to the new one
1974  CloneFunctionInto(Copied, F, VMap,
1976 
1977  // Set the linakage and visibility late as CloneFunctionInto has some
1978  // implicit requirements.
1981 
1982  // Copy metadata
1984  F->getAllMetadata(MDs);
1985  for (auto MDIt : MDs)
1986  if (!Copied->hasMetadata())
1987  Copied->addMetadata(MDIt.first, *MDIt.second);
1988 
1989  M.getFunctionList().insert(F->getIterator(), Copied);
1990  Copied->setDSOLocal(true);
1991  FnMap[F] = Copied;
1992  }
1993 
1994  // Replace all uses of the old function with the new internalized function
1995  // unless the caller is a function that was just internalized.
1996  for (Function *F : FnSet) {
1997  auto &InternalizedFn = FnMap[F];
1998  auto IsNotInternalized = [&](Use &U) -> bool {
1999  if (auto *CB = dyn_cast<CallBase>(U.getUser()))
2000  return !FnMap.lookup(CB->getCaller());
2001  return false;
2002  };
2003  F->replaceUsesWithIf(InternalizedFn, IsNotInternalized);
2004  }
2005 
2006  return true;
2007 }
2008 
2010  Argument &Arg, ArrayRef<Type *> ReplacementTypes) {
2011 
2012  if (!RewriteSignatures)
2013  return false;
2014 
2015  auto CallSiteCanBeChanged = [](AbstractCallSite ACS) {
2016  // Forbid the call site to cast the function return type. If we need to
2017  // rewrite these functions we need to re-create a cast for the new call site
2018  // (if the old had uses).
2019  if (!ACS.getCalledFunction() ||
2020  ACS.getInstruction()->getType() !=
2022  return false;
2023  // Forbid must-tail calls for now.
2024  return !ACS.isCallbackCall() && !ACS.getInstruction()->isMustTailCall();
2025  };
2026 
2027  Function *Fn = Arg.getParent();
2028  // Avoid var-arg functions for now.
2029  if (Fn->isVarArg()) {
2030  LLVM_DEBUG(dbgs() << "[Attributor] Cannot rewrite var-args functions\n");
2031  return false;
2032  }
2033 
2034  // Avoid functions with complicated argument passing semantics.
2035  AttributeList FnAttributeList = Fn->getAttributes();
2036  if (FnAttributeList.hasAttrSomewhere(Attribute::Nest) ||
2037  FnAttributeList.hasAttrSomewhere(Attribute::StructRet) ||
2038  FnAttributeList.hasAttrSomewhere(Attribute::InAlloca) ||
2039  FnAttributeList.hasAttrSomewhere(Attribute::Preallocated)) {
2040  LLVM_DEBUG(
2041  dbgs() << "[Attributor] Cannot rewrite due to complex attribute\n");
2042  return false;
2043  }
2044 
2045  // Avoid callbacks for now.
2046  bool AllCallSitesKnown;
2047  if (!checkForAllCallSites(CallSiteCanBeChanged, *Fn, true, nullptr,
2048  AllCallSitesKnown)) {
2049  LLVM_DEBUG(dbgs() << "[Attributor] Cannot rewrite all call sites\n");
2050  return false;
2051  }
2052 
2053  auto InstPred = [](Instruction &I) {
2054  if (auto *CI = dyn_cast<CallInst>(&I))
2055  return !CI->isMustTailCall();
2056  return true;
2057  };
2058 
2059  // Forbid must-tail calls for now.
2060  // TODO:
2061  bool UsedAssumedInformation = false;
2062  auto &OpcodeInstMap = InfoCache.getOpcodeInstMapForFunction(*Fn);
2063  if (!checkForAllInstructionsImpl(nullptr, OpcodeInstMap, InstPred, nullptr,
2064  nullptr, {Instruction::Call},
2065  UsedAssumedInformation)) {
2066  LLVM_DEBUG(dbgs() << "[Attributor] Cannot rewrite due to instructions\n");
2067  return false;
2068  }
2069 
2070  return true;
2071 }
2072 
2074  Argument &Arg, ArrayRef<Type *> ReplacementTypes,
2077  LLVM_DEBUG(dbgs() << "[Attributor] Register new rewrite of " << Arg << " in "
2078  << Arg.getParent()->getName() << " with "
2079  << ReplacementTypes.size() << " replacements\n");
2080  assert(isValidFunctionSignatureRewrite(Arg, ReplacementTypes) &&
2081  "Cannot register an invalid rewrite");
2082 
2083  Function *Fn = Arg.getParent();
2085  ArgumentReplacementMap[Fn];
2086  if (ARIs.empty())
2087  ARIs.resize(Fn->arg_size());
2088 
2089  // If we have a replacement already with less than or equal new arguments,
2090  // ignore this request.
2091  std::unique_ptr<ArgumentReplacementInfo> &ARI = ARIs[Arg.getArgNo()];
2092  if (ARI && ARI->getNumReplacementArgs() <= ReplacementTypes.size()) {
2093  LLVM_DEBUG(dbgs() << "[Attributor] Existing rewrite is preferred\n");
2094  return false;
2095  }
2096 
2097  // If we have a replacement already but we like the new one better, delete
2098  // the old.
2099  ARI.reset();
2100 
2101  LLVM_DEBUG(dbgs() << "[Attributor] Register new rewrite of " << Arg << " in "
2102  << Arg.getParent()->getName() << " with "
2103  << ReplacementTypes.size() << " replacements\n");
2104 
2105  // Remember the replacement.
2106  ARI.reset(new ArgumentReplacementInfo(*this, Arg, ReplacementTypes,
2107  std::move(CalleeRepairCB),
2108  std::move(ACSRepairCB)));
2109 
2110  return true;
2111 }
2112 
2113 bool Attributor::shouldSeedAttribute(AbstractAttribute &AA) {
2114  bool Result = true;
2115 #ifndef NDEBUG
2116  if (SeedAllowList.size() != 0)
2117  Result =
2118  std::count(SeedAllowList.begin(), SeedAllowList.end(), AA.getName());
2119  Function *Fn = AA.getAnchorScope();
2120  if (FunctionSeedAllowList.size() != 0 && Fn)
2121  Result &= std::count(FunctionSeedAllowList.begin(),
2122  FunctionSeedAllowList.end(), Fn->getName());
2123 #endif
2124  return Result;
2125 }
2126 
2127 ChangeStatus Attributor::rewriteFunctionSignatures(
2128  SmallPtrSetImpl<Function *> &ModifiedFns) {
2130 
2131  for (auto &It : ArgumentReplacementMap) {
2132  Function *OldFn = It.getFirst();
2133 
2134  // Deleted functions do not require rewrites.
2135  if (!Functions.count(OldFn) || ToBeDeletedFunctions.count(OldFn))
2136  continue;
2137 
2139  It.getSecond();
2140  assert(ARIs.size() == OldFn->arg_size() && "Inconsistent state!");
2141 
2142  SmallVector<Type *, 16> NewArgumentTypes;
2143  SmallVector<AttributeSet, 16> NewArgumentAttributes;
2144 
2145  // Collect replacement argument types and copy over existing attributes.
2146  AttributeList OldFnAttributeList = OldFn->getAttributes();
2147  for (Argument &Arg : OldFn->args()) {
2148  if (const std::unique_ptr<ArgumentReplacementInfo> &ARI =
2149  ARIs[Arg.getArgNo()]) {
2150  NewArgumentTypes.append(ARI->ReplacementTypes.begin(),
2151  ARI->ReplacementTypes.end());
2152  NewArgumentAttributes.append(ARI->getNumReplacementArgs(),
2153  AttributeSet());
2154  } else {
2155  NewArgumentTypes.push_back(Arg.getType());
2156  NewArgumentAttributes.push_back(
2157  OldFnAttributeList.getParamAttributes(Arg.getArgNo()));
2158  }
2159  }
2160 
2161  FunctionType *OldFnTy = OldFn->getFunctionType();
2162  Type *RetTy = OldFnTy->getReturnType();
2163 
2164  // Construct the new function type using the new arguments types.
2165  FunctionType *NewFnTy =
2166  FunctionType::get(RetTy, NewArgumentTypes, OldFnTy->isVarArg());
2167 
2168  LLVM_DEBUG(dbgs() << "[Attributor] Function rewrite '" << OldFn->getName()
2169  << "' from " << *OldFn->getFunctionType() << " to "
2170  << *NewFnTy << "\n");
2171 
2172  // Create the new function body and insert it into the module.
2173  Function *NewFn = Function::Create(NewFnTy, OldFn->getLinkage(),
2174  OldFn->getAddressSpace(), "");
2175  Functions.insert(NewFn);
2176  OldFn->getParent()->getFunctionList().insert(OldFn->getIterator(), NewFn);
2177  NewFn->takeName(OldFn);
2178  NewFn->copyAttributesFrom(OldFn);
2179 
2180  // Patch the pointer to LLVM function in debug info descriptor.
2181  NewFn->setSubprogram(OldFn->getSubprogram());
2182  OldFn->setSubprogram(nullptr);
2183 
2184  // Recompute the parameter attributes list based on the new arguments for
2185  // the function.
2186  LLVMContext &Ctx = OldFn->getContext();
2188  Ctx, OldFnAttributeList.getFnAttributes(),
2189  OldFnAttributeList.getRetAttributes(), NewArgumentAttributes));
2190 
2191  // Since we have now created the new function, splice the body of the old
2192  // function right into the new function, leaving the old rotting hulk of the
2193  // function empty.
2194  NewFn->getBasicBlockList().splice(NewFn->begin(),
2195  OldFn->getBasicBlockList());
2196 
2197  // Fixup block addresses to reference new function.
2198  SmallVector<BlockAddress *, 8u> BlockAddresses;
2199  for (User *U : OldFn->users())
2200  if (auto *BA = dyn_cast<BlockAddress>(U))
2201  BlockAddresses.push_back(BA);
2202  for (auto *BA : BlockAddresses)
2203  BA->replaceAllUsesWith(BlockAddress::get(NewFn, BA->getBasicBlock()));
2204 
2205  // Set of all "call-like" instructions that invoke the old function mapped
2206  // to their new replacements.
2208 
2209  // Callback to create a new "call-like" instruction for a given one.
2210  auto CallSiteReplacementCreator = [&](AbstractCallSite ACS) {
2211  CallBase *OldCB = cast<CallBase>(ACS.getInstruction());
2212  const AttributeList &OldCallAttributeList = OldCB->getAttributes();
2213 
2214  // Collect the new argument operands for the replacement call site.
2215  SmallVector<Value *, 16> NewArgOperands;
2216  SmallVector<AttributeSet, 16> NewArgOperandAttributes;
2217  for (unsigned OldArgNum = 0; OldArgNum < ARIs.size(); ++OldArgNum) {
2218  unsigned NewFirstArgNum = NewArgOperands.size();
2219  (void)NewFirstArgNum; // only used inside assert.
2220  if (const std::unique_ptr<ArgumentReplacementInfo> &ARI =
2221  ARIs[OldArgNum]) {
2222  if (ARI->ACSRepairCB)
2223  ARI->ACSRepairCB(*ARI, ACS, NewArgOperands);
2224  assert(ARI->getNumReplacementArgs() + NewFirstArgNum ==
2225  NewArgOperands.size() &&
2226  "ACS repair callback did not provide as many operand as new "
2227  "types were registered!");
2228  // TODO: Exose the attribute set to the ACS repair callback
2229  NewArgOperandAttributes.append(ARI->ReplacementTypes.size(),
2230  AttributeSet());
2231  } else {
2232  NewArgOperands.push_back(ACS.getCallArgOperand(OldArgNum));
2233  NewArgOperandAttributes.push_back(
2234  OldCallAttributeList.getParamAttributes(OldArgNum));
2235  }
2236  }
2237 
2238  assert(NewArgOperands.size() == NewArgOperandAttributes.size() &&
2239  "Mismatch # argument operands vs. # argument operand attributes!");
2240  assert(NewArgOperands.size() == NewFn->arg_size() &&
2241  "Mismatch # argument operands vs. # function arguments!");
2242 
2243  SmallVector<OperandBundleDef, 4> OperandBundleDefs;
2244  OldCB->getOperandBundlesAsDefs(OperandBundleDefs);
2245 
2246  // Create a new call or invoke instruction to replace the old one.
2247  CallBase *NewCB;
2248  if (InvokeInst *II = dyn_cast<InvokeInst>(OldCB)) {
2249  NewCB =
2250  InvokeInst::Create(NewFn, II->getNormalDest(), II->getUnwindDest(),
2251  NewArgOperands, OperandBundleDefs, "", OldCB);
2252  } else {
2253  auto *NewCI = CallInst::Create(NewFn, NewArgOperands, OperandBundleDefs,
2254  "", OldCB);
2255  NewCI->setTailCallKind(cast<CallInst>(OldCB)->getTailCallKind());
2256  NewCB = NewCI;
2257  }
2258 
2259  // Copy over various properties and the new attributes.
2260  NewCB->copyMetadata(*OldCB, {LLVMContext::MD_prof, LLVMContext::MD_dbg});
2261  NewCB->setCallingConv(OldCB->getCallingConv());
2262  NewCB->takeName(OldCB);
2264  Ctx, OldCallAttributeList.getFnAttributes(),
2265  OldCallAttributeList.getRetAttributes(), NewArgOperandAttributes));
2266 
2267  CallSitePairs.push_back({OldCB, NewCB});
2268  return true;
2269  };
2270 
2271  // Use the CallSiteReplacementCreator to create replacement call sites.
2272  bool AllCallSitesKnown;
2273  bool Success = checkForAllCallSites(CallSiteReplacementCreator, *OldFn,
2274  true, nullptr, AllCallSitesKnown);
2275  (void)Success;
2276  assert(Success && "Assumed call site replacement to succeed!");
2277 
2278  // Rewire the arguments.
2279  Argument *OldFnArgIt = OldFn->arg_begin();
2280  Argument *NewFnArgIt = NewFn->arg_begin();
2281  for (unsigned OldArgNum = 0; OldArgNum < ARIs.size();
2282  ++OldArgNum, ++OldFnArgIt) {
2283  if (const std::unique_ptr<ArgumentReplacementInfo> &ARI =
2284  ARIs[OldArgNum]) {
2285  if (ARI->CalleeRepairCB)
2286  ARI->CalleeRepairCB(*ARI, *NewFn, NewFnArgIt);
2287  NewFnArgIt += ARI->ReplacementTypes.size();
2288  } else {
2289  NewFnArgIt->takeName(&*OldFnArgIt);
2290  OldFnArgIt->replaceAllUsesWith(&*NewFnArgIt);
2291  ++NewFnArgIt;
2292  }
2293  }
2294 
2295  // Eliminate the instructions *after* we visited all of them.
2296  for (auto &CallSitePair : CallSitePairs) {
2297  CallBase &OldCB = *CallSitePair.first;
2298  CallBase &NewCB = *CallSitePair.second;
2299  assert(OldCB.getType() == NewCB.getType() &&
2300  "Cannot handle call sites with different types!");
2301  ModifiedFns.insert(OldCB.getFunction());
2302  CGUpdater.replaceCallSite(OldCB, NewCB);
2303  OldCB.replaceAllUsesWith(&NewCB);
2304  OldCB.eraseFromParent();
2305  }
2306 
2307  // Replace the function in the call graph (if any).
2308  CGUpdater.replaceFunctionWith(*OldFn, *NewFn);
2309 
2310  // If the old function was modified and needed to be reanalyzed, the new one
2311  // does now.
2312  if (ModifiedFns.erase(OldFn))
2313  ModifiedFns.insert(NewFn);
2314 
2315  Changed = ChangeStatus::CHANGED;
2316  }
2317 
2318  return Changed;
2319 }
2320 
2321 void InformationCache::initializeInformationCache(const Function &CF,
2322  FunctionInfo &FI) {
2323  // As we do not modify the function here we can remove the const
2324  // withouth breaking implicit assumptions. At the end of the day, we could
2325  // initialize the cache eagerly which would look the same to the users.
2326  Function &F = const_cast<Function &>(CF);
2327 
2328  // Walk all instructions to find interesting instructions that might be
2329  // queried by abstract attributes during their initialization or update.
2330  // This has to happen before we create attributes.
2331 
2332  for (Instruction &I : instructions(&F)) {
2333  bool IsInterestingOpcode = false;
2334 
2335  // To allow easy access to all instructions in a function with a given
2336  // opcode we store them in the InfoCache. As not all opcodes are interesting
2337  // to concrete attributes we only cache the ones that are as identified in
2338  // the following switch.
2339  // Note: There are no concrete attributes now so this is initially empty.
2340  switch (I.getOpcode()) {
2341  default:
2342  assert(!isa<CallBase>(&I) &&
2343  "New call base instruction type needs to be known in the "
2344  "Attributor.");
2345  break;
2346  case Instruction::Call:
2347  // Calls are interesting on their own, additionally:
2348  // For `llvm.assume` calls we also fill the KnowledgeMap as we find them.
2349  // For `must-tail` calls we remember the caller and callee.
2350  if (auto *Assume = dyn_cast<AssumeInst>(&I)) {
2351  fillMapFromAssume(*Assume, KnowledgeMap);
2352  } else if (cast<CallInst>(I).isMustTailCall()) {
2353  FI.ContainsMustTailCall = true;
2354  if (const Function *Callee = cast<CallInst>(I).getCalledFunction())
2355  getFunctionInfo(*Callee).CalledViaMustTail = true;
2356  }
2358  case Instruction::CallBr:
2359  case Instruction::Invoke:
2360  case Instruction::CleanupRet:
2361  case Instruction::CatchSwitch:
2362  case Instruction::AtomicRMW:
2363  case Instruction::AtomicCmpXchg:
2364  case Instruction::Br:
2365  case Instruction::Resume:
2366  case Instruction::Ret:
2367  case Instruction::Load:
2368  // The alignment of a pointer is interesting for loads.
2369  case Instruction::Store:
2370  // The alignment of a pointer is interesting for stores.
2371  case Instruction::Alloca:
2372  case Instruction::AddrSpaceCast:
2373  IsInterestingOpcode = true;
2374  }
2375  if (IsInterestingOpcode) {
2376  auto *&Insts = FI.OpcodeInstMap[I.getOpcode()];
2377  if (!Insts)
2378  Insts = new (Allocator) InstructionVectorTy();
2379  Insts->push_back(&I);
2380  }
2381  if (I.mayReadOrWriteMemory())
2382  FI.RWInsts.push_back(&I);
2383  }
2384 
2385  if (F.hasFnAttribute(Attribute::AlwaysInline) &&
2387  InlineableFunctions.insert(&F);
2388 }
2389 
2391  return AG.getAnalysis<AAManager>(F);
2392 }
2393 
2394 InformationCache::FunctionInfo::~FunctionInfo() {
2395  // The instruction vectors are allocated using a BumpPtrAllocator, we need to
2396  // manually destroy them.
2397  for (auto &It : OpcodeInstMap)
2398  It.getSecond()->~InstructionVectorTy();
2399 }
2400 
2402  const AbstractAttribute &ToAA,
2403  DepClassTy DepClass) {
2404  if (DepClass == DepClassTy::NONE)
2405  return;
2406  // If we are outside of an update, thus before the actual fixpoint iteration
2407  // started (= when we create AAs), we do not track dependences because we will
2408  // put all AAs into the initial worklist anyway.
2409  if (DependenceStack.empty())
2410  return;
2411  if (FromAA.getState().isAtFixpoint())
2412  return;
2413  DependenceStack.back()->push_back({&FromAA, &ToAA, DepClass});
2414 }
2415 
2416 void Attributor::rememberDependences() {
2417  assert(!DependenceStack.empty() && "No dependences to remember!");
2418 
2419  for (DepInfo &DI : *DependenceStack.back()) {
2420  assert((DI.DepClass == DepClassTy::REQUIRED ||
2421  DI.DepClass == DepClassTy::OPTIONAL) &&
2422  "Expected required or optional dependence (1 bit)!");
2423  auto &DepAAs = const_cast<AbstractAttribute &>(*DI.FromAA).Deps;
2424  DepAAs.push_back(AbstractAttribute::DepTy(
2425  const_cast<AbstractAttribute *>(DI.ToAA), unsigned(DI.DepClass)));
2426  }
2427 }
2428 
2430  if (!VisitedFunctions.insert(&F).second)
2431  return;
2432  if (F.isDeclaration())
2433  return;
2434 
2435  // In non-module runs we need to look at the call sites of a function to
2436  // determine if it is part of a must-tail call edge. This will influence what
2437  // attributes we can derive.
2438  InformationCache::FunctionInfo &FI = InfoCache.getFunctionInfo(F);
2439  if (!isModulePass() && !FI.CalledViaMustTail) {
2440  for (const Use &U : F.uses())
2441  if (const auto *CB = dyn_cast<CallBase>(U.getUser()))
2442  if (CB->isCallee(&U) && CB->isMustTailCall())
2443  FI.CalledViaMustTail = true;
2444  }
2445 
2447 
2448  // Check for dead BasicBlocks in every function.
2449  // We need dead instruction detection because we do not want to deal with
2450  // broken IR in which SSA rules do not apply.
2451  getOrCreateAAFor<AAIsDead>(FPos);
2452 
2453  // Every function might be "will-return".
2454  getOrCreateAAFor<AAWillReturn>(FPos);
2455 
2456  // Every function might contain instructions that cause "undefined behavior".
2457  getOrCreateAAFor<AAUndefinedBehavior>(FPos);
2458 
2459  // Every function can be nounwind.
2460  getOrCreateAAFor<AANoUnwind>(FPos);
2461 
2462  // Every function might be marked "nosync"
2463  getOrCreateAAFor<AANoSync>(FPos);
2464 
2465  // Every function might be "no-free".
2466  getOrCreateAAFor<AANoFree>(FPos);
2467 
2468  // Every function might be "no-return".
2469  getOrCreateAAFor<AANoReturn>(FPos);
2470 
2471  // Every function might be "no-recurse".
2472  getOrCreateAAFor<AANoRecurse>(FPos);
2473 
2474  // Every function might be "readnone/readonly/writeonly/...".
2475  getOrCreateAAFor<AAMemoryBehavior>(FPos);
2476 
2477  // Every function can be "readnone/argmemonly/inaccessiblememonly/...".
2478  getOrCreateAAFor<AAMemoryLocation>(FPos);
2479 
2480  // Every function might be applicable for Heap-To-Stack conversion.
2481  if (EnableHeapToStack)
2482  getOrCreateAAFor<AAHeapToStack>(FPos);
2483 
2484  // Return attributes are only appropriate if the return type is non void.
2485  Type *ReturnType = F.getReturnType();
2486  if (!ReturnType->isVoidTy()) {
2487  // Argument attribute "returned" --- Create only one per function even
2488  // though it is an argument attribute.
2489  getOrCreateAAFor<AAReturnedValues>(FPos);
2490 
2491  IRPosition RetPos = IRPosition::returned(F);
2492 
2493  // Every returned value might be dead.
2494  getOrCreateAAFor<AAIsDead>(RetPos);
2495 
2496  // Every function might be simplified.
2497  getOrCreateAAFor<AAValueSimplify>(RetPos);
2498 
2499  // Every returned value might be marked noundef.
2500  getOrCreateAAFor<AANoUndef>(RetPos);
2501 
2502  if (ReturnType->isPointerTy()) {
2503 
2504  // Every function with pointer return type might be marked align.
2505  getOrCreateAAFor<AAAlign>(RetPos);
2506 
2507  // Every function with pointer return type might be marked nonnull.
2508  getOrCreateAAFor<AANonNull>(RetPos);
2509 
2510  // Every function with pointer return type might be marked noalias.
2511  getOrCreateAAFor<AANoAlias>(RetPos);
2512 
2513  // Every function with pointer return type might be marked
2514  // dereferenceable.
2515  getOrCreateAAFor<AADereferenceable>(RetPos);
2516  }
2517  }
2518 
2519  for (Argument &Arg : F.args()) {
2521 
2522  // Every argument might be simplified. We have to go through the Attributor
2523  // interface though as outside AAs can register custom simplification
2524  // callbacks.
2525  bool UsedAssumedInformation = false;
2526  getAssumedSimplified(ArgPos, /* AA */ nullptr, UsedAssumedInformation);
2527 
2528  // Every argument might be dead.
2529  getOrCreateAAFor<AAIsDead>(ArgPos);
2530 
2531  // Every argument might be marked noundef.
2532  getOrCreateAAFor<AANoUndef>(ArgPos);
2533 
2534  if (Arg.getType()->isPointerTy()) {
2535  // Every argument with pointer type might be marked nonnull.
2536  getOrCreateAAFor<AANonNull>(ArgPos);
2537 
2538  // Every argument with pointer type might be marked noalias.
2539  getOrCreateAAFor<AANoAlias>(ArgPos);
2540 
2541  // Every argument with pointer type might be marked dereferenceable.
2542  getOrCreateAAFor<AADereferenceable>(ArgPos);
2543 
2544  // Every argument with pointer type might be marked align.
2545  getOrCreateAAFor<AAAlign>(ArgPos);
2546 
2547  // Every argument with pointer type might be marked nocapture.
2548  getOrCreateAAFor<AANoCapture>(ArgPos);
2549 
2550  // Every argument with pointer type might be marked
2551  // "readnone/readonly/writeonly/..."
2552  getOrCreateAAFor<AAMemoryBehavior>(ArgPos);
2553 
2554  // Every argument with pointer type might be marked nofree.
2555  getOrCreateAAFor<AANoFree>(ArgPos);
2556 
2557  // Every argument with pointer type might be privatizable (or promotable)
2558  getOrCreateAAFor<AAPrivatizablePtr>(ArgPos);
2559  }
2560  }
2561 
2562  auto CallSitePred = [&](Instruction &I) -> bool {
2563  auto &CB = cast<CallBase>(I);
2565 
2566  // Call sites might be dead if they do not have side effects and no live
2567  // users. The return value might be dead if there are no live users.
2568  getOrCreateAAFor<AAIsDead>(CBRetPos);
2569 
2570  Function *Callee = CB.getCalledFunction();
2571  // TODO: Even if the callee is not known now we might be able to simplify
2572  // the call/callee.
2573  if (!Callee)
2574  return true;
2575 
2576  // Skip declarations except if annotations on their call sites were
2577  // explicitly requested.
2578  if (!AnnotateDeclarationCallSites && Callee->isDeclaration() &&
2579  !Callee->hasMetadata(LLVMContext::MD_callback))
2580  return true;
2581 
2582  if (!Callee->getReturnType()->isVoidTy() && !CB.use_empty()) {
2583 
2585  getOrCreateAAFor<AAValueSimplify>(CBRetPos);
2586  }
2587 
2588  for (int I = 0, E = CB.getNumArgOperands(); I < E; ++I) {
2589 
2590  IRPosition CBArgPos = IRPosition::callsite_argument(CB, I);
2591 
2592  // Every call site argument might be dead.
2593  getOrCreateAAFor<AAIsDead>(CBArgPos);
2594 
2595  // Call site argument might be simplified. We have to go through the
2596  // Attributor interface though as outside AAs can register custom
2597  // simplification callbacks.
2598  bool UsedAssumedInformation = false;
2599  getAssumedSimplified(CBArgPos, /* AA */ nullptr, UsedAssumedInformation);
2600 
2601  // Every call site argument might be marked "noundef".
2602  getOrCreateAAFor<AANoUndef>(CBArgPos);
2603 
2604  if (!CB.getArgOperand(I)->getType()->isPointerTy())
2605  continue;
2606 
2607  // Call site argument attribute "non-null".
2608  getOrCreateAAFor<AANonNull>(CBArgPos);
2609 
2610  // Call site argument attribute "nocapture".
2611  getOrCreateAAFor<AANoCapture>(CBArgPos);
2612 
2613  // Call site argument attribute "no-alias".
2614  getOrCreateAAFor<AANoAlias>(CBArgPos);
2615 
2616  // Call site argument attribute "dereferenceable".
2617  getOrCreateAAFor<AADereferenceable>(CBArgPos);
2618 
2619  // Call site argument attribute "align".
2620  getOrCreateAAFor<AAAlign>(CBArgPos);
2621 
2622  // Call site argument attribute
2623  // "readnone/readonly/writeonly/..."
2624  getOrCreateAAFor<AAMemoryBehavior>(CBArgPos);
2625 
2626  // Call site argument attribute "nofree".
2627  getOrCreateAAFor<AANoFree>(CBArgPos);
2628  }
2629  return true;
2630  };
2631 
2632  auto &OpcodeInstMap = InfoCache.getOpcodeInstMapForFunction(F);
2633  bool Success;
2634  bool UsedAssumedInformation = false;
2636  nullptr, OpcodeInstMap, CallSitePred, nullptr, nullptr,
2637  {(unsigned)Instruction::Invoke, (unsigned)Instruction::CallBr,
2638  (unsigned)Instruction::Call},
2639  UsedAssumedInformation);
2640  (void)Success;
2641  assert(Success && "Expected the check call to be successful!");
2642 
2643  auto LoadStorePred = [&](Instruction &I) -> bool {
2644  if (isa<LoadInst>(I)) {
2645  getOrCreateAAFor<AAAlign>(
2646  IRPosition::value(*cast<LoadInst>(I).getPointerOperand()));
2647  if (SimplifyAllLoads)
2648  getOrCreateAAFor<AAValueSimplify>(IRPosition::value(I));
2649  } else
2650  getOrCreateAAFor<AAAlign>(
2651  IRPosition::value(*cast<StoreInst>(I).getPointerOperand()));
2652  return true;
2653  };
2655  nullptr, OpcodeInstMap, LoadStorePred, nullptr, nullptr,
2656  {(unsigned)Instruction::Load, (unsigned)Instruction::Store},
2657  UsedAssumedInformation);
2658  (void)Success;
2659  assert(Success && "Expected the check call to be successful!");
2660 }
2661 
2662 /// Helpers to ease debugging through output streams and print calls.
2663 ///
2664 ///{
2666  return OS << (S == ChangeStatus::CHANGED ? "changed" : "unchanged");
2667 }
2668 
2670  switch (AP) {
2672  return OS << "inv";
2673  case IRPosition::IRP_FLOAT:
2674  return OS << "flt";
2676  return OS << "fn_ret";
2678  return OS << "cs_ret";
2680  return OS << "fn";
2682  return OS << "cs";
2684  return OS << "arg";
2686  return OS << "cs_arg";
2687  }
2688  llvm_unreachable("Unknown attribute position!");
2689 }
2690 
2692  const Value &AV = Pos.getAssociatedValue();
2693  OS << "{" << Pos.getPositionKind() << ":" << AV.getName() << " ["
2694  << Pos.getAnchorValue().getName() << "@" << Pos.getCallSiteArgNo() << "]";
2695 
2696  if (Pos.hasCallBaseContext())
2697  OS << "[cb_context:" << *Pos.getCallBaseContext() << "]";
2698  return OS << "}";
2699 }
2700 
2702  OS << "range-state(" << S.getBitWidth() << ")<";
2703  S.getKnown().print(OS);
2704  OS << " / ";
2705  S.getAssumed().print(OS);
2706  OS << ">";
2707 
2708  return OS << static_cast<const AbstractState &>(S);
2709 }
2710 
2712  return OS << (!S.isValidState() ? "top" : (S.isAtFixpoint() ? "fix" : ""));
2713 }
2714 
2716  AA.print(OS);
2717  return OS;
2718 }
2719 
2722  OS << "set-state(< {";
2723  if (!S.isValidState())
2724  OS << "full-set";
2725  else {
2726  for (auto &it : S.getAssumedSet())
2727  OS << it << ", ";
2728  if (S.undefIsContained())
2729  OS << "undef ";
2730  }
2731  OS << "} >)";
2732 
2733  return OS;
2734 }
2735 
2737  OS << "[";
2738  OS << getName();
2739  OS << "] for CtxI ";
2740 
2741  if (auto *I = getCtxI()) {
2742  OS << "'";
2743  I->print(OS);
2744  OS << "'";
2745  } else
2746  OS << "<<null inst>>";
2747 
2748  OS << " at position " << getIRPosition() << " with state " << getAsStr()
2749  << '\n';
2750 }
2751 
2753  print(OS);
2754 
2755  for (const auto &DepAA : Deps) {
2756  auto *AA = DepAA.getPointer();
2757  OS << " updates ";
2758  AA->print(OS);
2759  }
2760 
2761  OS << '\n';
2762 }
2763 
2765  const AAPointerInfo::Access &Acc) {
2766  OS << " [" << Acc.getKind() << "] " << *Acc.getRemoteInst();
2767  if (Acc.getLocalInst() != Acc.getRemoteInst())
2768  OS << " via " << *Acc.getLocalInst();
2769  if (Acc.getContent().hasValue())
2770  OS << " [" << *Acc.getContent() << "]";
2771  return OS;
2772 }
2773 ///}
2774 
2775 /// ----------------------------------------------------------------------------
2776 /// Pass (Manager) Boilerplate
2777 /// ----------------------------------------------------------------------------
2778 
2780  SetVector<Function *> &Functions,
2781  AnalysisGetter &AG,
2782  CallGraphUpdater &CGUpdater,
2783  bool DeleteFns) {
2784  if (Functions.empty())
2785  return false;
2786 
2787  LLVM_DEBUG({
2788  dbgs() << "[Attributor] Run on module with " << Functions.size()
2789  << " functions:\n";
2790  for (Function *Fn : Functions)
2791  dbgs() << " - " << Fn->getName() << "\n";
2792  });
2793 
2794  // Create an Attributor and initially empty information cache that is filled
2795  // while we identify default attribute opportunities.
2796  Attributor A(Functions, InfoCache, CGUpdater, /* Allowed */ nullptr,
2797  DeleteFns);
2798 
2799  // Create shallow wrappers for all functions that are not IPO amendable
2801  for (Function *F : Functions)
2802  if (!A.isFunctionIPOAmendable(*F))
2804 
2805  // Internalize non-exact functions
2806  // TODO: for now we eagerly internalize functions without calculating the
2807  // cost, we need a cost interface to determine whether internalizing
2808  // a function is "benefitial"
2809  if (AllowDeepWrapper) {
2810  unsigned FunSize = Functions.size();
2811  for (unsigned u = 0; u < FunSize; u++) {
2812  Function *F = Functions[u];
2813  if (!F->isDeclaration() && !F->isDefinitionExact() && F->getNumUses() &&
2814  !GlobalValue::isInterposableLinkage(F->getLinkage())) {
2816  assert(NewF && "Could not internalize function.");
2817  Functions.insert(NewF);
2818 
2819  // Update call graph
2820  CGUpdater.replaceFunctionWith(*F, *NewF);
2821  for (const Use &U : NewF->uses())
2822  if (CallBase *CB = dyn_cast<CallBase>(U.getUser())) {
2823  auto *CallerF = CB->getCaller();
2824  CGUpdater.reanalyzeFunction(*CallerF);
2825  }
2826  }
2827  }
2828  }
2829 
2830  for (Function *F : Functions) {
2831  if (F->hasExactDefinition())
2832  NumFnWithExactDefinition++;
2833  else
2834  NumFnWithoutExactDefinition++;
2835 
2836  // We look at internal functions only on-demand but if any use is not a
2837  // direct call or outside the current set of analyzed functions, we have
2838  // to do it eagerly.
2839  if (F->hasLocalLinkage()) {
2840  if (llvm::all_of(F->uses(), [&Functions](const Use &U) {
2841  const auto *CB = dyn_cast<CallBase>(U.getUser());
2842  return CB && CB->isCallee(&U) &&
2843  Functions.count(const_cast<Function *>(CB->getCaller()));
2844  }))
2845  continue;
2846  }
2847 
2848  // Populate the Attributor with abstract attribute opportunities in the
2849  // function and the information cache with IR information.
2850  A.identifyDefaultAbstractAttributes(*F);
2851  }
2852 
2853  ChangeStatus Changed = A.run();
2854 
2855  LLVM_DEBUG(dbgs() << "[Attributor] Done with " << Functions.size()
2856  << " functions, result: " << Changed << ".\n");
2857  return Changed == ChangeStatus::CHANGED;
2858 }
2859 
2860 void AADepGraph::viewGraph() { llvm::ViewGraph(this, "Dependency Graph"); }
2861 
2863  static std::atomic<int> CallTimes;
2864  std::string Prefix;
2865 
2866  if (!DepGraphDotFileNamePrefix.empty())
2868  else
2869  Prefix = "dep_graph";
2870  std::string Filename =
2871  Prefix + "_" + std::to_string(CallTimes.load()) + ".dot";
2872 
2873  outs() << "Dependency graph dump to " << Filename << ".\n";
2874 
2875  std::error_code EC;
2876 
2878  if (!EC)
2879  llvm::WriteGraph(File, this);
2880 
2881  CallTimes++;
2882 }
2883 
2885  for (auto DepAA : SyntheticRoot.Deps)
2886  cast<AbstractAttribute>(DepAA.getPointer())->printWithDeps(outs());
2887 }
2888 
2892  AnalysisGetter AG(FAM);
2893 
2894  SetVector<Function *> Functions;
2895  for (Function &F : M)
2896  Functions.insert(&F);
2897 
2898  CallGraphUpdater CGUpdater;
2900  InformationCache InfoCache(M, AG, Allocator, /* CGSCC */ nullptr);
2901  if (runAttributorOnFunctions(InfoCache, Functions, AG, CGUpdater,
2902  /* DeleteFns */ true)) {
2903  // FIXME: Think about passes we will preserve and add them here.
2904  return PreservedAnalyses::none();
2905  }
2906  return PreservedAnalyses::all();
2907 }
2908 
2911  LazyCallGraph &CG,
2912  CGSCCUpdateResult &UR) {
2914  AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C, CG).getManager();
2915  AnalysisGetter AG(FAM);
2916 
2917  SetVector<Function *> Functions;
2918  for (LazyCallGraph::Node &N : C)
2919  Functions.insert(&N.getFunction());
2920 
2921  if (Functions.empty())
2922  return PreservedAnalyses::all();
2923 
2924  Module &M = *Functions.back()->getParent();
2925  CallGraphUpdater CGUpdater;
2926  CGUpdater.initialize(CG, C, AM, UR);
2928  InformationCache InfoCache(M, AG, Allocator, /* CGSCC */ &Functions);
2929  if (runAttributorOnFunctions(InfoCache, Functions, AG, CGUpdater,
2930  /* DeleteFns */ false)) {
2931  // FIXME: Think about passes we will preserve and add them here.
2932  PreservedAnalyses PA;
2934  return PA;
2935  }
2936  return PreservedAnalyses::all();
2937 }
2938 
2939 namespace llvm {
2940 
2941 template <> struct GraphTraits<AADepGraphNode *> {
2945 
2946  static NodeRef getEntryNode(AADepGraphNode *DGN) { return DGN; }
2947  static NodeRef DepGetVal(DepTy &DT) { return DT.getPointer(); }
2948 
2949  using ChildIteratorType =
2952 
2953  static ChildIteratorType child_begin(NodeRef N) { return N->child_begin(); }
2954 
2955  static ChildIteratorType child_end(NodeRef N) { return N->child_end(); }
2956 };
2957 
2958 template <>
2960  static NodeRef getEntryNode(AADepGraph *DG) { return DG->GetEntryNode(); }
2961 
2962  using nodes_iterator =
2964 
2965  static nodes_iterator nodes_begin(AADepGraph *DG) { return DG->begin(); }
2966 
2967  static nodes_iterator nodes_end(AADepGraph *DG) { return DG->end(); }
2968 };
2969 
2970 template <> struct DOTGraphTraits<AADepGraph *> : public DefaultDOTGraphTraits {
2972 
2973  static std::string getNodeLabel(const AADepGraphNode *Node,
2974  const AADepGraph *DG) {
2975  std::string AAString;
2976  raw_string_ostream O(AAString);
2977  Node->print(O);
2978  return AAString;
2979  }
2980 };
2981 
2982 } // end namespace llvm
2983 
2984 namespace {
2985 
2986 struct AttributorLegacyPass : public ModulePass {
2987  static char ID;
2988 
2989  AttributorLegacyPass() : ModulePass(ID) {
2991  }
2992 
2993  bool runOnModule(Module &M) override {
2994  if (skipModule(M))
2995  return false;
2996 
2997  AnalysisGetter AG;
2998  SetVector<Function *> Functions;
2999  for (Function &F : M)
3000  Functions.insert(&F);
3001 
3002  CallGraphUpdater CGUpdater;
3004  InformationCache InfoCache(M, AG, Allocator, /* CGSCC */ nullptr);
3005  return runAttributorOnFunctions(InfoCache, Functions, AG, CGUpdater,
3006  /* DeleteFns*/ true);
3007  }
3008 
3009  void getAnalysisUsage(AnalysisUsage &AU) const override {
3010  // FIXME: Think about passes we will preserve and add them here.
3012  }
3013 };
3014 
3015 struct AttributorCGSCCLegacyPass : public CallGraphSCCPass {
3016  static char ID;
3017 
3018  AttributorCGSCCLegacyPass() : CallGraphSCCPass(ID) {
3020  }
3021 
3022  bool runOnSCC(CallGraphSCC &SCC) override {
3023  if (skipSCC(SCC))
3024  return false;
3025 
3026  SetVector<Function *> Functions;
3027  for (CallGraphNode *CGN : SCC)
3028  if (Function *Fn = CGN->getFunction())
3029  if (!Fn->isDeclaration())
3030  Functions.insert(Fn);
3031 
3032  if (Functions.empty())
3033  return false;
3034 
3035  AnalysisGetter AG;
3036  CallGraph &CG = const_cast<CallGraph &>(SCC.getCallGraph());
3037  CallGraphUpdater CGUpdater;
3038  CGUpdater.initialize(CG, SCC);
3039  Module &M = *Functions.back()->getParent();
3041  InformationCache InfoCache(M, AG, Allocator, /* CGSCC */ &Functions);
3042  return runAttributorOnFunctions(InfoCache, Functions, AG, CGUpdater,
3043  /* DeleteFns */ false);
3044  }
3045 
3046  void getAnalysisUsage(AnalysisUsage &AU) const override {
3047  // FIXME: Think about passes we will preserve and add them here.
3050  }
3051 };
3052 
3053 } // end anonymous namespace
3054 
3055 Pass *llvm::createAttributorLegacyPass() { return new AttributorLegacyPass(); }
3057  return new AttributorCGSCCLegacyPass();
3058 }
3059 
3060 char AttributorLegacyPass::ID = 0;
3062 
3063 INITIALIZE_PASS_BEGIN(AttributorLegacyPass, "attributor",
3064  "Deduce and propagate attributes", false, false)
3066 INITIALIZE_PASS_END(AttributorLegacyPass, "attributor",
3068 INITIALIZE_PASS_BEGIN(AttributorCGSCCLegacyPass, "attributor-cgscc",
3069  "Deduce and propagate attributes (CGSCC pass)", false,
3070  false)
3073 INITIALIZE_PASS_END(AttributorCGSCCLegacyPass, "attributor-cgscc",
3074  "Deduce and propagate attributes (CGSCC pass)", false,
3075  false)
llvm::AAIsDead::isKnownDead
virtual bool isKnownDead() const =0
Returns true if the underlying value is known dead.
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:2946
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:511
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:338
llvm::AA::getPotentialCopiesOfStoredValue
bool getPotentialCopiesOfStoredValue(Attributor &A, StoreInst &SI, SmallSetVector< Value *, 4 > &PotentialCopies, const AbstractAttribute &QueryingAA, bool &UsedAssumedInformation)
Collect all potential values of the one stored by SI into PotentialCopies.
Definition: Attributor.cpp:285
Attrs
Function Attrs
Definition: README_ALTIVEC.txt:215
getName
static StringRef getName(Value *V)
Definition: ProvenanceAnalysisEvaluator.cpp:42
llvm::initializeAttributorLegacyPassPass
void initializeAttributorLegacyPassPass(PassRegistry &)
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::Attribute::isEnumAttribute
bool isEnumAttribute() const
Return true if the attribute is an Attribute::AttrKind type.
Definition: Attributes.cpp:257
llvm::GraphTraits< AADepGraphNode * >::child_end
static ChildIteratorType child_end(NodeRef N)
Definition: Attributor.cpp:2955
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:365
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:3757
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
it
into xmm2 addss xmm2 xmm1 xmm3 addss xmm3 movaps xmm0 unpcklps xmm0 ret seems silly when it could just be one addps Expand libm rounding functions main should enable SSE DAZ mode and other fast SSE modes Think about doing i64 math in SSE regs on x86 This testcase should have no SSE instructions in it
Definition: README-SSE.txt:81
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:1682
llvm::ReturnInst
Return a value (possibly void), from a function.
Definition: Instructions.h:2950
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:632
FileSystem.h
llvm::IRPosition::getAssociatedFunction
Function * getAssociatedFunction() const
Return the associated function, if any.
Definition: Attributor.h:426
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:1413
llvm::GraphTraits< AADepGraph * >::nodes_begin
static nodes_iterator nodes_begin(AADepGraph *DG)
Definition: Attributor.cpp:2965
llvm::ModulePass
ModulePass class - This class is used to implement unstructured interprocedural optimizations and ana...
Definition: Pass.h:238
IntrinsicInst.h
llvm::Type::isPointerTy
bool isPointerTy() const
True if this is an instance of PointerType.
Definition: Type.h:228
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:1683
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:255
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:466
llvm::AA::getInitialValueForObj
Constant * getInitialValueForObj(Value &Obj, Type &Ty)
Return the initial value of Obj with type Ty if that is a constant.
Definition: Attributor.cpp:204
llvm::raw_string_ostream
A raw_ostream that writes to an std::string.
Definition: raw_ostream.h:623
llvm::SetVector::size
size_type size() const
Determine the number of elements in the SetVector.
Definition: SetVector.h:77
llvm::Attribute::get
static Attribute get(LLVMContext &Context, AttrKind Kind, uint64_t Val=0)
Return a uniquified Attribute object.
Definition: Attributes.cpp:92
llvm::AANoRecurse
An abstract attribute for norecurse.
Definition: Attributor.h:2901
llvm::AAPointerInfo::Access
An access description.
Definition: Attributor.h:4492
llvm::SmallVector< Value *, 8 >
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:327
llvm::Function::getSubprogram
DISubprogram * getSubprogram() const
Get the attached subprogram.
Definition: Metadata.cpp:1532
llvm::GraphTraits< AADepGraph * >::getEntryNode
static NodeRef getEntryNode(AADepGraph *DG)
Definition: Attributor.cpp:2960
llvm::cl::CommaSeparated
@ CommaSeparated
Definition: CommandLine.h:169
llvm::Type::getPointerAddressSpace
unsigned getPointerAddressSpace() const
Get the address space of this pointer or pointer vector type.
Definition: DerivedTypes.h:733
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:1728
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:327
llvm::SubsumingPositionIterator::SubsumingPositionIterator
SubsumingPositionIterator(const IRPosition &IRP)
Definition: Attributor.cpp:544
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:1040
llvm::CallGraph
The basic data container for the call graph of a Module of IR.
Definition: CallGraph.h:73
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
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:630
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:5727
llvm::AADepGraph::dumpGraph
void dumpGraph()
Dump graph to file.
Definition: Attributor.cpp:2862
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:143
llvm::Attributor::isRunOn
bool isRunOn(Function &Fn) const
Return true if we derive attributes for Fn.
Definition: Attributor.h:1416
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:321
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::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
llvm::AttributeList
Definition: Attributes.h:398
llvm::CallBase::getAttributes
AttributeList getAttributes() const
Return the parameter attributes for this call.
Definition: InstrTypes.h:1468
llvm::IRPosition::getAssociatedType
Type * getAssociatedType() const
Return the type this abstract attribute is associated with.
Definition: Attributor.h:490
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 &UsedAssumedInformation, bool CheckBBLivenessOnly=false, bool CheckPotentiallyDead=false)
Definition: Attributor.cpp:1229
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:864
llvm::CallBase::isMustTailCall
bool isMustTailCall() const
Tests if this call site must be tail call optimized.
Definition: Instructions.cpp:298
llvm::Optional
Definition: APInt.h:33
llvm::isInlineViable
InlineResult isInlineViable(Function &Callee)
Minimal filter to detect invalid constructs for inlining.
Definition: InlineCost.cpp:2861
llvm::InformationCache::getAAResultsForFunction
AAResults * getAAResultsForFunction(const Function &F)
Return AliasAnalysis Result for function F.
Definition: Attributor.cpp:2390
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:279
llvm::AAPointerInfo::Access::getRemoteInst
Instruction * getRemoteInst() const
Return the actual instruction that causes the access.
Definition: Attributor.h:4542
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:2696
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:2401
isMustTailCall
static bool isMustTailCall(Value *V)
Definition: InstructionCombining.cpp:2884
llvm::Attributor::run
ChangeStatus run()
Run the analyses until a fixpoint is reached or enforced (timeout).
Definition: Attributor.cpp:1813
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:317
llvm::AADepGraphNode::end
aaiterator end()
Definition: Attributor.h:251
llvm::Attributor::~Attributor
~Attributor()
Definition: Attributor.cpp:844
LazyValueInfo.h
llvm::IRPosition::IRP_RETURNED
@ IRP_RETURNED
An attribute for the function return value.
Definition: Attributor.h:313
llvm::Instruction::copyMetadata
void copyMetadata(const Instruction &SrcInst, ArrayRef< unsigned > WL=ArrayRef< unsigned >())
Copy metadata from SrcInst to this instruction.
Definition: Instruction.cpp:829
attributes
Deduce and propagate attributes
Definition: Attributor.cpp:3067
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:3055
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:1207
STLExtras.h
llvm::AbstractCallSite
AbstractCallSite.
Definition: AbstractCallSite.h:50
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:635
llvm::Type::isFloatingPointTy
bool isFloatingPointTy() const
Return true if this is one of the six floating-point types.
Definition: Type.h:162
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:635
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:3189
llvm::InformationCache::InstructionVectorTy
SmallVector< Instruction *, 8 > InstructionVectorTy
A vector type to hold instructions.
Definition: Attributor.h:956
llvm::IRPosition::IRP_FLOAT
@ IRP_FLOAT
A position that is not associated with a spot suitable for attributes.
Definition: Attributor.h:311
llvm::GlobalValue::setDSOLocal
void setDSOLocal(bool Local)
Definition: GlobalValue.h:280
MustExecute.h
llvm::AA::isValidAtPosition
bool isValidAtPosition(const Value &V, const Instruction &CtxI, InformationCache &InfoCache)
Return true if V is a valid value at position CtxI, that is a constant, an argument of the same funct...
Definition: Attributor.cpp:225
llvm::MaxInitializationChainLength
unsigned MaxInitializationChainLength
The value passed to the line option that defines the maximal initialization chain length.
Definition: Attributor.cpp:92
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))
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:2033
Uses
SmallPtrSet< MachineInstr *, 2 > Uses
Definition: ARMLowOverheadLoops.cpp:579
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:1387
llvm::Optional::hasValue
constexpr bool hasValue() const
Definition: Optional.h:288
PointerIntPair.h
llvm::createAttributorCGSCCLegacyPass
Pass * createAttributorCGSCCLegacyPass()
Definition: Attributor.cpp:3056
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
GraphTraits.h
llvm::DominatorTree::dominates
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
Definition: Dominators.cpp:115
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:280
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:1547
llvm::operator&=
bool operator&=(SparseBitVector< ElementSize > *LHS, const SparseBitVector< ElementSize > &RHS)
Definition: SparseBitVector.h:834
llvm::AreStatisticsEnabled
bool AreStatisticsEnabled()
Check if statistics are enabled.
Definition: Statistic.cpp:138
llvm::GraphTraits< AADepGraphNode * >::child_begin
static ChildIteratorType child_begin(NodeRef N)
Definition: Attributor.cpp:2953
GlobalValue.h
llvm::CallGraphSCC
CallGraphSCC - This is a single SCC that a CallGraphSCCPass is run on.
Definition: CallGraphSCCPass.h:87
llvm::SPII::Load
@ Load
Definition: SparcInstrInfo.h:32
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:422
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:1070
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
Constants.h
llvm::AAResults
Definition: AliasAnalysis.h:456
llvm::ChangeStatus
ChangeStatus
{
Definition: Attributor.h:209
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::CallGraphUpdater::removeCallSite
void removeCallSite(CallBase &CS)
Remove the call site CS from the call graph.
Definition: CallGraphUpdater.cpp:160
llvm::SmallVectorImpl::append
void append(in_iter in_start, in_iter in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:648
llvm::AbstractAttribute::getState
virtual StateType & getState()=0
Return the internal abstract state for inspection.
llvm::User
Definition: User.h:44
AllowShallowWrappers
static cl::opt< bool > AllowShallowWrappers("attributor-allow-shallow-wrappers", cl::Hidden, cl::desc("Allow the Attributor to create shallow " "wrappers for non-exact definitions."), cl::init(false))
PrintCallGraph
static cl::opt< bool > PrintCallGraph("attributor-print-call-graph", cl::Hidden, cl::desc("Print Attributor's internal call graph"), 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:2752
llvm::AttributeList::getFnAttributes
AttributeSet getFnAttributes() const
The function attributes are returned.
Definition: Attributes.cpp:1383
llvm::CallBase::getCalledFunction
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation.
Definition: InstrTypes.h:1393
llvm::AttributorCallGraph
Definition: Attributor.h:4346
llvm::CallBase::setAttributes
void setAttributes(AttributeList A)
Set the parameter attributes for this call.
Definition: InstrTypes.h:1472
llvm::CallInst::Create
static CallInst * Create(FunctionType *Ty, Value *F, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Definition: Instructions.h:1518
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:280
llvm::AADepGraph::print
void print()
Print dependency graph.
Definition: Attributor.cpp:2884
llvm::AttributeList::getParamAttributes
AttributeSet getParamAttributes(unsigned ArgNo) const
The attributes for the argument or parameter at the given index are returned.
Definition: Attributes.cpp:1375
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:2636
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
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:610
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:535
llvm::IRPosition::getCtxI
Instruction * getCtxI() const
Return the context instruction, if any.
Definition: Attributor.h:467
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:1489
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:669
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:53
llvm::Function::removeParamAttr
void removeParamAttr(unsigned ArgNo, Attribute::AttrKind Kind)
removes the attribute from the list of attributes.
Definition: Function.cpp:586
llvm::GlobalObject::addMetadata
void addMetadata(unsigned KindID, MDNode &MD)
Add a metadata attachment.
Definition: Metadata.cpp:1268
llvm::InlineResult::isSuccess
bool isSuccess() const
Definition: InlineCost.h:168
llvm::IntegerRangeState
State for an integer range.
Definition: Attributor.h:2399
llvm::SmallVectorImpl::resize
void resize(size_type N)
Definition: SmallVector.h:606
runAttributorOnFunctions
static bool runAttributorOnFunctions(InformationCache &InfoCache, SetVector< Function * > &Functions, AnalysisGetter &AG, CallGraphUpdater &CGUpdater, bool DeleteFns)
}
Definition: Attributor.cpp:2779
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:1784
llvm::PotentialValuesState
A class for a set state.
Definition: Attributor.h:3994
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:294
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:265
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:2967
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:1449
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:640
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:839
llvm::AADepGraphNode::Deps
TinyPtrVector< DepTy > Deps
Set of dependency graph nodes which should be updated if this one is updated.
Definition: Attributor.h:235
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:770
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:2909
llvm::AttributorCallGraph::print
void print()
Definition: AttributorAttributes.cpp:9534
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:3713
llvm::AA::isValidInScope
bool isValidInScope(const Value &V, const Function *Scope)
Return true if V is a valid value in Scope, that is a constant or an instruction/argument of Scope.
Definition: Attributor.cpp:215
getCalledFunction
static const Function * getCalledFunction(const Value *V, bool LookThroughBitCast, bool &IsNoBuiltin)
Definition: MemoryBuiltins.cpp:118
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:201
llvm::function_ref
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLExtras.h:168
llvm::AAPointerInfo::Access::getKind
AccessKind getKind() const
Return the access kind.
Definition: Attributor.h:4529
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:1881
llvm::AA::getAssumedUnderlyingObjects
bool getAssumedUnderlyingObjects(Attributor &A, const Value &Ptr, SmallVectorImpl< Value * > &Objects, const AbstractAttribute &QueryingAA, const Instruction *CtxI)
Collect all potential underlying objects of Ptr at position CtxI in Objects.
Definition: AttributorAttributes.cpp:393
llvm::AttributorPass::run
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)
Definition: Attributor.cpp:2889
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:2083
llvm::cl::opt
Definition: CommandLine.h:1422
Attributor.h
llvm::Function::setSubprogram
void setSubprogram(DISubprogram *SP)
Set the attached subprogram.
Definition: Metadata.cpp:1528
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:368
llvm::instructions
inst_range instructions(Function *F)
Definition: InstIterator.h:133
llvm::StoreInst
An instruction for storing to memory.
Definition: Instructions.h:304
llvm::Attributor::ArgumentReplacementInfo::ACSRepairCBTy
std::function< void(const ArgumentReplacementInfo &, AbstractCallSite, SmallVectorImpl< Value * > &)> ACSRepairCBTy
Abstract call site (ACS) repair callback type.
Definition: Attributor.h:1706
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:2062
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:568
llvm::AbstractAttribute
Base struct for all "concrete attribute" deductions.
Definition: Attributor.h:2630
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::clear
void clear()
Definition: DenseMap.h:111
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:1630
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:5279
llvm::Attributor::getAssumedConstant
Optional< Constant * > getAssumedConstant(const IRPosition &IRP, const AbstractAttribute &AA, bool &UsedAssumedInformation)
If IRP is assumed to be a constant, return it, if it is unclear yet, return None, otherwise return nu...
Definition: Attributor.cpp:758
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:963
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::AAPointerInfo::Access::getContent
Optional< Value * > getContent() const
Return the written value which can be llvm::null if it is not yet determined.
Definition: Attributor.h:4562
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:315
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:412
DEBUG_COUNTER
DEBUG_COUNTER(ManifestDBGCounter, "attributor-manifest", "Determine what attributes are manifested in the IR")
llvm::DenseMap
Definition: DenseMap.h:714
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:2073
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:273
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:481
llvm::AA::getWithType
Value * getWithType(Value &V, Type &Ty)
Try to convert V to type Ty without introducing new instructions.
Definition: Attributor.cpp:241
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:412
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:515
llvm::AAIsDead
An abstract interface for liveness abstract attribute.
Definition: Attributor.h:3134
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:2076
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::AADepGraph::end
iterator end()
Definition: Attributor.h:283
SI
StandardInstrumentations SI(Debug, VerifyEach)
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:303
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:138
llvm::Attributor::checkForAllInstructions
bool checkForAllInstructions(function_ref< bool(Instruction &)> Pred, const AbstractAttribute &QueryingAA, const ArrayRef< unsigned > &Opcodes, bool &UsedAssumedInformation, bool CheckBBLivenessOnly=false, bool CheckPotentiallyDead=false)
Check Pred on all instructions with an opcode present in Opcodes.
Definition: Attributor.cpp:1255
llvm::WinEH::EncodingType::CE
@ CE
Windows NT (Windows on ARM)
addIfNotExistent
static bool addIfNotExistent(LLVMContext &Ctx, const Attribute &Attr, AttributeList &Attrs, int AttrIdx, bool ForceReplace=false)
Return true if the information provided by Attr was added to the attribute list Attrs.
Definition: Attributor.cpp:376
llvm::DOTGraphTraits< AADepGraph * >::getNodeLabel
static std::string getNodeLabel(const AADepGraphNode *Node, const AADepGraph *DG)
Definition: Attributor.cpp:2973
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:67
TinyPtrVector.h
llvm::Attributor::checkForAllReadWriteInstructions
bool checkForAllReadWriteInstructions(function_ref< bool(Instruction &)> Pred, AbstractAttribute &QueryingAA, bool &UsedAssumedInformation)
Check Pred on all Read/Write instructions.
Definition: Attributor.cpp:1288
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:318
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::User::isDroppable
bool isDroppable() const
A droppable user is a user for which uses can be dropped without affecting correctness and should be ...
Definition: User.cpp:109
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:2429
llvm::IRPosition::IRP_CALL_SITE_RETURNED
@ IRP_CALL_SITE_RETURNED
An attribute for a call site return value.
Definition: Attributor.h:314
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:4616
llvm::IRPosition::IRP_INVALID
@ IRP_INVALID
An invalid position.
Definition: Attributor.h:310
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::AttributorCallGraph::populateAll
void populateAll() const
Force populate the entire call graph.
Definition: Attributor.h:4359
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:136
llvm::operator|=
bool operator|=(SparseBitVector< ElementSize > &LHS, const SparseBitVector< ElementSize > *RHS)
Definition: SparseBitVector.h:822
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:256
llvm::SPII::Store
@ Store
Definition: SparcInstrInfo.h:33
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::AAPointerInfo
An abstract interface for struct information.
Definition: Attributor.h:4482
llvm::Instruction::getFunction
const Function * getFunction() const
Return the function this instruction belongs to.
Definition: Instruction.cpp:70
llvm::IRAttributeManifest::manifestAttrs
static ChangeStatus manifestAttrs(Attributor &A, const IRPosition &IRP, const ArrayRef< Attribute > &DeducedAttrs, bool ForceReplace=false)
Definition: Attributor.cpp:482
llvm::Value::replaceAllUsesWith
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:520
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:979
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:366
llvm::GlobalObject::hasMetadata
bool hasMetadata() const
Return true if this value has any metadata attached to it.
Definition: Value.h:585
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:3066
llvm::ChangeStatus::CHANGED
@ CHANGED
llvm::Module::getFunctionList
const FunctionListType & getFunctionList() const
Get the Module's list of functions (constant).
Definition: Module.h:556
llvm::Attributor::isInternalizable
static bool isInternalizable(Function &F)
Returns true if the function F can be internalized.
Definition: Attributor.cpp:1928
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:273
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:297
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:441
llvm::Attributor::internalizeFunction
static Function * internalizeFunction(Function &F, bool Force=false)
Make another copy of the function F such that the copied version has internal linkage afterwards and ...
Definition: Attributor.cpp:1935
llvm::IRPosition::IRP_CALL_SITE_ARGUMENT
@ IRP_CALL_SITE_ARGUMENT
An attribute for a call site argument.
Definition: Attributor.h:318
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:675
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:968
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:455
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:2042
Attributes.h
llvm::Attributor::isValidFunctionSignatureRewrite
bool isValidFunctionSignatureRewrite(Argument &Arg, ArrayRef< Type * > ReplacementTypes)
Check if we can rewrite a function signature.
Definition: Attributor.cpp:2009
Constant.h
llvm::CGSCCUpdateResult
Support structure for SCC passes to communicate updates the call graph back to the CGSCC pass manager...
Definition: CGSCCPassManager.h:232
llvm::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:936
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:316
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:510
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
GlobalVariable.h
llvm::GraphTraits< AADepGraphNode * >
Definition: Attributor.cpp:2941
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:1418
Success
#define Success
Definition: AArch64Disassembler.cpp:261
Casting.h
llvm::TinyPtrVector::iterator
EltTy * iterator
Definition: TinyPtrVector.h:180
llvm::CallGraphSCCPass
Definition: CallGraphSCCPass.h:34
llvm::DepClassTy
DepClassTy
Definition: Attributor.h:219
DebugCounter.h
llvm::SetVector::count
size_type count(const key_type &key) const
Count the number of elements of a given key in the SetVector.
Definition: SetVector.h:215
llvm::Function::addAttribute
void addAttribute(unsigned i, Attribute::AttrKind Kind)
adds the attribute to the list of attributes.
Definition: Function.cpp:532
llvm::Attributor
The fixpoint analysis framework that orchestrates the attribute deduction.
Definition: Attributor.h:1139
llvm::ReturnInst::Create
static ReturnInst * Create(LLVMContext &C, Value *retVal=nullptr, Instruction *InsertBefore=nullptr)
Definition: Instructions.h:2977
llvm::AAPointerInfo::Access::getLocalInst
Instruction * getLocalInst() const
Return the instruction that causes the access with respect to the local scope of the associated attri...
Definition: Attributor.h:4539
llvm::PointerIntPair::getOpaqueValue
void * getOpaqueValue() const
Definition: PointerIntPair.h:91
llvm::Attributor::checkForAllUses
bool checkForAllUses(function_ref< bool(const Use &, bool &)> Pred, const AbstractAttribute &QueryingAA, const Value &V, bool CheckBBLivenessOnly=false, DepClassTy LivenessDepClass=DepClassTy::OPTIONAL)
Check Pred on all (transitive) uses of V.
Definition: Attributor.cpp:999
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:352
llvm::IRPosition::callsite_function
static const IRPosition callsite_function(const CallBase &CB)
Create a position describing the function scope of CB.
Definition: Attributor.h:358
llvm::AbstractAttribute::print
void print(raw_ostream &OS) const override
Helper functions, for debug purposes only.
Definition: Attributor.cpp:2736
llvm::ConstantExpr::getFPTrunc
static Constant * getFPTrunc(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2125
isSimple
static bool isSimple(Instruction *I)
Definition: SLPVectorizer.cpp:528
llvm::Function::arg_begin
arg_iterator arg_begin()
Definition: Function.h:793
llvm::AADepGraphNode::begin
aaiterator begin()
Definition: Attributor.h:250
llvm::AA::combineOptionalValuesInAAValueLatice
Optional< Value * > combineOptionalValuesInAAValueLatice(const Optional< Value * > &A, const Optional< Value * > &B, Type *Ty)
Return the combination of A and B such that the result is a possible value of both.
Definition: Attributor.cpp:262
llvm::AANoRecurse::isAssumedNoRecurse
bool isAssumedNoRecurse() const
Return true if "norecurse" is assumed.
Definition: Attributor.h:2907
llvm::GraphTraits< AADepGraphNode * >::ChildEdgeIteratorType
TinyPtrVector< DepTy >::iterator ChildEdgeIteratorType
Definition: Attributor.cpp:2951
llvm::GlobalValue::getAddressSpace
unsigned getAddressSpace() const
Definition: Globals.cpp:112
llvm::AADepGraph
The data structure for the dependency graph.
Definition: Attributor.h:267
llvm::AADepGraphNode
}
Definition: Attributor.h:227
cgscc
Deduce and propagate false attributor cgscc
Definition: Attributor.cpp:3073
llvm::AttributeList::FunctionIndex
@ FunctionIndex
Definition: Attributes.h:402
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:252
llvm::Function::isVarArg
bool isVarArg() const
isVarArg - Return true if this function takes a variable number of arguments.
Definition: Function.h:188
llvm::changeToUnreachable
unsigned changeToUnreachable(Instruction *I, 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:2113
llvm::AttributeList::getRetAttributes
AttributeSet getRetAttributes() const
The attributes for the ret value are returned.
Definition: Attributes.cpp:1379
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::InformationCache::getAnalysisResultForFunction
AP::Result * getAnalysisResultForFunction(const Function &F)
Return the analysis result from a pass AP for function F.
Definition: Attributor.h:994
llvm::PointerIntPair
PointerIntPair - This class implements a pair of a pointer and small integer.
Definition: PointerIntPair.h:45
llvm::AttributeSet
Definition: Attributes.h:266
llvm::DOTGraphTraits< AADepGraph * >::DOTGraphTraits
DOTGraphTraits(bool isSimple=false)
Definition: Attributor.cpp:2971
llvm::AADepGraph::begin
iterator begin()
Definition: Attributor.h:282
llvm::IRPosition::TombstoneKey
static const IRPosition TombstoneKey
Definition: Attributor.h:641
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::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:2178
llvm::to_string
std::string to_string(const T &Value)
Definition: ScopedPrinter.h:63
llvm::BlockAddress::get
static BlockAddress * get(Function *F, BasicBlock *BB)
Return a BlockAddress for the specified function and basic block.
Definition: Constants.cpp:1822
llvm::ArrayRef::size
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:165
llvm::AnalysisGetter
Wrapper for FunctoinAnalysisManager.
Definition: Attributor.h:837
llvm::GraphTraits< AADepGraphNode * >::DepGetVal
static NodeRef DepGetVal(DepTy &DT)
Definition: Attributor.cpp:2947
llvm::Attributor::isAssumedDead
bool isAssumedDead(const AbstractAttribute &AA, const AAIsDead *LivenessAA, bool &UsedAssumedInformation, bool CheckBBLivenessOnly=false, DepClassTy DepClass=DepClassTy::OPTIONAL)
Return true if AA (or its context instruction) is assumed dead.
Definition: Attributor.cpp:853
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:2597
llvm::Function::getAttribute
Attribute getAttribute(unsigned i, Attribute::AttrKind Kind) const
gets the attribute from the list of attributes.
Definition: Function.h:459
llvm::Attributor::translateArgumentToCallSiteContent
Optional< Value * > translateArgumentToCallSiteContent(Optional< Value * > V, CallBase &CB, const AbstractAttribute &AA, bool &UsedAssumedInformation)
Translate V from the callee context into the call site context.
Definition: Attributor.cpp:828
llvm::Attributor::getAssumedSimplified
Optional< Value * > getAssumedSimplified(const IRPosition &IRP, const AbstractAttribute &AA, bool &UsedAssumedInformation)
If V is assumed simplified, return it, if it is unclear yet, return None, otherwise return nullptr.
Definition: Attributor.h:1535
llvm::AA::isDynamicallyUnique
bool isDynamicallyUnique(Attributor &A, const AbstractAttribute &QueryingAA, const Value &V)
Return true if V is dynamically unique, that is, there are no two "instances" of V at runtime with di...
Definition: Attributor.cpp:184
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:1489
llvm::Attribute::isIntAttribute
bool isIntAttribute() const
Return true if the attribute is an integer attribute.
Definition: Attributes.cpp:261
llvm::SubsumingPositionIterator
A visitor class for IR positions.
Definition: Attributor.h:826
llvm::CallBase
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1161
llvm::SmallPtrSetImpl< Function * >
llvm::SmallSetVector< Value *, 4 >
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:309
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:1692
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::CallInst
This class represents a function call, abstracting a target machine's calling convention.
Definition: Instructions.h:1475
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:370
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:1184
llvm::LazyCallGraph
A lazily constructed view of the call graph of a module.
Definition: LazyCallGraph.h:113
llvm::AbstractAttribute::getIRPosition
const IRPosition & getIRPosition() const
Return an IR position, see struct IRPosition.
Definition: Attributor.h:2661
raw_ostream.h
llvm::NullPointerIsDefined
bool NullPointerIsDefined(const Function *F, unsigned AS=0)
Check whether null pointer dereferencing is considered undefined behavior for a given function or an ...
Definition: Function.cpp:1925
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
llvm::SmallVectorImpl::reserve
void reserve(size_type N)
Definition: SmallVector.h:624
llvm::IRPosition::callsite_returned
static const IRPosition callsite_returned(const CallBase &CB)
Create a position describing the returned value of CB.
Definition: Attributor.h:363
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:1410
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
llvm::AAPointerInfo::Access::isRead
bool isRead() const
Return true if this is a read access.
Definition: Attributor.h:4532
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::AADepGraph::viewGraph
void viewGraph()
Definition: Attributor.cpp:2860
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:345
SimplifyAllLoads
static cl::opt< bool > SimplifyAllLoads("attributor-simplify-all-loads", cl::Hidden, cl::desc("Try to simplify all loads."), cl::init(true))
llvm::CallBase::setCallingConv
void setCallingConv(CallingConv::ID CC)
Definition: InstrTypes.h:1453
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::Attributor::internalizeFunctions
static bool internalizeFunctions(SmallPtrSetImpl< Function * > &FnSet, DenseMap< Function *, Function * > &FnMap)
Make copies of each function in the set FnSet such that the copied version has internal linkage after...
Definition: Attributor.cpp:1948
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
SetFixpointIterations
static cl::opt< unsigned > SetFixpointIterations("attributor-max-iterations", cl::Hidden, cl::desc("Maximal number of fixpoint iterations."), cl::init(32))
llvm::PoisonValue::get
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
Definition: Constants.cpp:1803
llvm::cl::list
Definition: CommandLine.h:1630