LLVM  12.0.0git
AssumeBundleBuilder.cpp
Go to the documentation of this file.
1 //===- AssumeBundleBuilder.cpp - tools to preserve informations -*- C++ -*-===//
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 #define DEBUG_TYPE "assume-builder"
10 
13 #include "llvm/ADT/MapVector.h"
14 #include "llvm/ADT/Statistic.h"
18 #include "llvm/IR/Dominators.h"
19 #include "llvm/IR/Function.h"
20 #include "llvm/IR/InstIterator.h"
21 #include "llvm/IR/IntrinsicInst.h"
22 #include "llvm/IR/Module.h"
23 #include "llvm/InitializePasses.h"
27 
28 using namespace llvm;
29 
31  "assume-preserve-all", cl::init(false), cl::Hidden,
32  cl::desc("enable preservation of all attrbitues. even those that are "
33  "unlikely to be usefull"));
34 
36  "enable-knowledge-retention", cl::init(false), cl::Hidden,
37  cl::desc(
38  "enable preservation of attributes throughout code transformation"));
39 
40 STATISTIC(NumAssumeBuilt, "Number of assume built by the assume builder");
41 STATISTIC(NumBundlesInAssumes, "Total number of Bundles in the assume built");
42 STATISTIC(NumAssumesMerged,
43  "Number of assume merged by the assume simplify pass");
44 STATISTIC(NumAssumesRemoved,
45  "Number of assume removed by the assume simplify pass");
46 
47 DEBUG_COUNTER(BuildAssumeCounter, "assume-builder-counter",
48  "Controls which assumes gets created");
49 
50 namespace {
51 
52 bool isUsefullToPreserve(Attribute::AttrKind Kind) {
53  switch (Kind) {
54  case Attribute::NonNull:
55  case Attribute::Alignment:
56  case Attribute::Dereferenceable:
57  case Attribute::DereferenceableOrNull:
58  case Attribute::Cold:
59  return true;
60  default:
61  return false;
62  }
63 }
64 
65 /// This function will try to transform the given knowledge into a more
66 /// canonical one. the canonical knowledge maybe the given one.
67 RetainedKnowledge canonicalizedKnowledge(RetainedKnowledge RK, Module *M) {
68  switch (RK.AttrKind) {
69  default:
70  return RK;
71  case Attribute::NonNull:
73  return RK;
74  case Attribute::Alignment: {
75  Value *V = RK.WasOn->stripInBoundsOffsets([&](const Value *Strip) {
76  if (auto *GEP = dyn_cast<GEPOperator>(Strip))
77  RK.ArgValue =
78  MinAlign(RK.ArgValue,
79  GEP->getMaxPreservedAlignment(M->getDataLayout()).value());
80  });
81  RK.WasOn = V;
82  return RK;
83  }
84  case Attribute::Dereferenceable:
85  case Attribute::DereferenceableOrNull: {
86  int64_t Offset = 0;
88  RK.WasOn, Offset, M->getDataLayout(), /*AllowNonInBounds*/ false);
89  if (Offset < 0)
90  return RK;
91  RK.ArgValue = RK.ArgValue + Offset;
92  RK.WasOn = V;
93  }
94  }
95  return RK;
96 }
97 
98 /// This class contain all knowledge that have been gather while building an
99 /// llvm.assume and the function to manipulate it.
100 struct AssumeBuilderState {
101  Module *M;
102 
103  using MapKey = std::pair<Value *, Attribute::AttrKind>;
104  SmallMapVector<MapKey, unsigned, 8> AssumedKnowledgeMap;
105  Instruction *InstBeingRemoved = nullptr;
106  AssumptionCache* AC = nullptr;
107  DominatorTree* DT = nullptr;
108 
109  AssumeBuilderState(Module *M, Instruction *I = nullptr,
110  AssumptionCache *AC = nullptr, DominatorTree *DT = nullptr)
111  : M(M), InstBeingRemoved(I), AC(AC), DT(DT) {}
112 
113  bool tryToPreserveWithoutAddingAssume(RetainedKnowledge RK) {
114  if (!InstBeingRemoved || !RK.WasOn)
115  return false;
116  bool HasBeenPreserved = false;
117  Use* ToUpdate = nullptr;
119  RK.WasOn, {RK.AttrKind}, AC,
120  [&](RetainedKnowledge RKOther, Instruction *Assume,
121  const CallInst::BundleOpInfo *Bundle) {
122  if (!isValidAssumeForContext(Assume, InstBeingRemoved, DT))
123  return false;
124  if (RKOther.ArgValue >= RK.ArgValue) {
125  HasBeenPreserved = true;
126  return true;
127  } else if (isValidAssumeForContext(InstBeingRemoved, Assume,
128  DT)) {
129  HasBeenPreserved = true;
130  IntrinsicInst *Intr = cast<IntrinsicInst>(Assume);
131  ToUpdate = &Intr->op_begin()[Bundle->Begin + ABA_Argument];
132  return true;
133  }
134  return false;
135  });
136  if (ToUpdate)
137  ToUpdate->set(
139  return HasBeenPreserved;
140  }
141 
142  bool isKnowledgeWorthPreserving(RetainedKnowledge RK) {
143  if (!RK)
144  return false;
145  if (!RK.WasOn)
146  return true;
147  if (RK.WasOn->getType()->isPointerTy()) {
148  Value *UnderlyingPtr = GetUnderlyingObject(RK.WasOn, M->getDataLayout());
149  if (isa<AllocaInst>(UnderlyingPtr) || isa<GlobalValue>(UnderlyingPtr))
150  return false;
151  }
152  if (auto *Arg = dyn_cast<Argument>(RK.WasOn)) {
153  if (Arg->hasAttribute(RK.AttrKind) &&
155  Arg->getAttribute(RK.AttrKind).getValueAsInt() >= RK.ArgValue))
156  return false;
157  return true;
158  }
159  if (auto *Inst = dyn_cast<Instruction>(RK.WasOn))
161  if (RK.WasOn->use_empty())
162  return false;
163  Use *SingleUse = RK.WasOn->getSingleUndroppableUse();
164  if (SingleUse && SingleUse->getUser() == InstBeingRemoved)
165  return false;
166  }
167  return true;
168  }
169 
170  void addKnowledge(RetainedKnowledge RK) {
171  RK = canonicalizedKnowledge(RK, M);
172 
173  if (!isKnowledgeWorthPreserving(RK))
174  return;
175 
176  if (tryToPreserveWithoutAddingAssume(RK))
177  return;
178  MapKey Key{RK.WasOn, RK.AttrKind};
179  auto Lookup = AssumedKnowledgeMap.find(Key);
180  if (Lookup == AssumedKnowledgeMap.end()) {
181  AssumedKnowledgeMap[Key] = RK.ArgValue;
182  return;
183  }
184  assert(((Lookup->second == 0 && RK.ArgValue == 0) ||
185  (Lookup->second != 0 && RK.ArgValue != 0)) &&
186  "inconsistent argument value");
187 
188  /// This is only desirable because for all attributes taking an argument
189  /// higher is better.
190  Lookup->second = std::max(Lookup->second, RK.ArgValue);
191  }
192 
193  void addAttribute(Attribute Attr, Value *WasOn) {
194  if (Attr.isTypeAttribute() || Attr.isStringAttribute() ||
196  !isUsefullToPreserve(Attr.getKindAsEnum())))
197  return;
198  unsigned AttrArg = 0;
199  if (Attr.isIntAttribute())
200  AttrArg = Attr.getValueAsInt();
201  addKnowledge({Attr.getKindAsEnum(), AttrArg, WasOn});
202  }
203 
204  void addCall(const CallBase *Call) {
205  auto addAttrList = [&](AttributeList AttrList) {
206  for (unsigned Idx = AttributeList::FirstArgIndex;
207  Idx < AttrList.getNumAttrSets(); Idx++)
208  for (Attribute Attr : AttrList.getAttributes(Idx))
209  addAttribute(Attr, Call->getArgOperand(Idx - 1));
210  for (Attribute Attr : AttrList.getFnAttributes())
211  addAttribute(Attr, nullptr);
212  };
213  addAttrList(Call->getAttributes());
214  if (Function *Fn = Call->getCalledFunction())
215  addAttrList(Fn->getAttributes());
216  }
217 
218  IntrinsicInst *build() {
219  if (AssumedKnowledgeMap.empty())
220  return nullptr;
221  if (!DebugCounter::shouldExecute(BuildAssumeCounter))
222  return nullptr;
223  Function *FnAssume = Intrinsic::getDeclaration(M, Intrinsic::assume);
224  LLVMContext &C = M->getContext();
226  for (auto &MapElem : AssumedKnowledgeMap) {
228  if (MapElem.first.first)
229  Args.push_back(MapElem.first.first);
230 
231  /// This is only valid because for all attribute that currently exist a
232  /// value of 0 is useless. and should not be preserved.
233  if (MapElem.second)
235  MapElem.second));
237  std::string(Attribute::getNameFromAttrKind(MapElem.first.second)),
238  Args));
239  NumBundlesInAssumes++;
240  }
241  NumAssumeBuilt++;
242  return cast<IntrinsicInst>(CallInst::Create(
243  FnAssume, ArrayRef<Value *>({ConstantInt::getTrue(C)}), OpBundle));
244  }
245 
246  void addAccessedPtr(Instruction *MemInst, Value *Pointer, Type *AccType,
247  MaybeAlign MA) {
248  unsigned DerefSize = MemInst->getModule()
249  ->getDataLayout()
250  .getTypeStoreSize(AccType)
251  .getKnownMinSize();
252  if (DerefSize != 0) {
253  addKnowledge({Attribute::Dereferenceable, DerefSize, Pointer});
254  if (!NullPointerIsDefined(MemInst->getFunction(),
255  Pointer->getType()->getPointerAddressSpace()))
256  addKnowledge({Attribute::NonNull, 0u, Pointer});
257  }
258  if (MA.valueOrOne() > 1)
259  addKnowledge(
260  {Attribute::Alignment, unsigned(MA.valueOrOne().value()), Pointer});
261  }
262 
263  void addInstruction(Instruction *I) {
264  if (auto *Call = dyn_cast<CallBase>(I))
265  return addCall(Call);
266  if (auto *Load = dyn_cast<LoadInst>(I))
267  return addAccessedPtr(I, Load->getPointerOperand(), Load->getType(),
268  Load->getAlign());
269  if (auto *Store = dyn_cast<StoreInst>(I))
270  return addAccessedPtr(I, Store->getPointerOperand(),
271  Store->getValueOperand()->getType(),
272  Store->getAlign());
273  // TODO: Add support for the other Instructions.
274  // TODO: Maybe we should look around and merge with other llvm.assume.
275  }
276 };
277 
278 } // namespace
279 
282  return nullptr;
283  AssumeBuilderState Builder(I->getModule());
284  Builder.addInstruction(I);
285  return Builder.build();
286 }
287 
289  DominatorTree *DT) {
291  return;
292  AssumeBuilderState Builder(I->getModule(), I, AC, DT);
293  Builder.addInstruction(I);
294  if (IntrinsicInst *Intr = Builder.build()) {
295  Intr->insertBefore(I);
296  if (AC)
297  AC->registerAssumption(Intr);
298  }
299 }
300 
301 namespace {
302 
303 struct AssumeSimplify {
304  Function &F;
305  AssumptionCache &AC;
306  DominatorTree *DT;
307  LLVMContext &C;
308  SmallDenseSet<IntrinsicInst *> CleanupToDo;
309  StringMapEntry<uint32_t> *IgnoreTag;
311  bool MadeChange = false;
312 
313  AssumeSimplify(Function &F, AssumptionCache &AC, DominatorTree *DT,
314  LLVMContext &C)
315  : F(F), AC(AC), DT(DT), C(C),
316  IgnoreTag(C.getOrInsertBundleTag(IgnoreBundleTag)) {}
317 
318  void buildMapping(bool FilterBooleanArgument) {
319  BBToAssume.clear();
320  for (Value *V : AC.assumptions()) {
321  if (!V)
322  continue;
323  IntrinsicInst *Assume = cast<IntrinsicInst>(V);
324  if (FilterBooleanArgument) {
325  auto *Arg = dyn_cast<ConstantInt>(Assume->getOperand(0));
326  if (!Arg || Arg->isZero())
327  continue;
328  }
329  BBToAssume[Assume->getParent()].push_back(Assume);
330  }
331 
332  for (auto &Elem : BBToAssume) {
333  llvm::sort(Elem.second,
334  [](const IntrinsicInst *LHS, const IntrinsicInst *RHS) {
335  return LHS->comesBefore(RHS);
336  });
337  }
338  }
339 
340  /// Remove all asumes in CleanupToDo if there boolean argument is true and
341  /// ForceCleanup is set or the assume doesn't hold valuable knowledge.
342  void RunCleanup(bool ForceCleanup) {
343  for (IntrinsicInst *Assume : CleanupToDo) {
344  auto *Arg = dyn_cast<ConstantInt>(Assume->getOperand(0));
345  if (!Arg || Arg->isZero() ||
346  (!ForceCleanup && !isAssumeWithEmptyBundle(*Assume)))
347  continue;
348  MadeChange = true;
349  if (ForceCleanup)
350  NumAssumesMerged++;
351  else
352  NumAssumesRemoved++;
353  Assume->eraseFromParent();
354  }
355  CleanupToDo.clear();
356  }
357 
358  /// Remove knowledge stored in assume when it is already know by an attribute
359  /// or an other assume. This can when valid update an existing knowledge in an
360  /// attribute or an other assume.
361  void dropRedundantKnowledge() {
362  struct MapValue {
363  IntrinsicInst *Assume;
364  unsigned ArgValue;
366  };
367  buildMapping(false);
370  Knowledge;
371  for (BasicBlock *BB : depth_first(&F))
372  for (Value *V : BBToAssume[BB]) {
373  if (!V)
374  continue;
375  IntrinsicInst *Assume = cast<IntrinsicInst>(V);
376  for (CallInst::BundleOpInfo &BOI : Assume->bundle_op_infos()) {
377  auto RemoveFromAssume = [&]() {
378  CleanupToDo.insert(Assume);
379  if (BOI.Begin != BOI.End) {
380  Use *U = &Assume->op_begin()[BOI.Begin + ABA_WasOn];
381  U->set(UndefValue::get(U->get()->getType()));
382  }
383  BOI.Tag = IgnoreTag;
384  };
385  if (BOI.Tag == IgnoreTag) {
386  CleanupToDo.insert(Assume);
387  continue;
388  }
389  RetainedKnowledge RK = getKnowledgeFromBundle(*Assume, BOI);
390  if (auto *Arg = dyn_cast_or_null<Argument>(RK.WasOn)) {
391  bool HasSameKindAttr = Arg->hasAttribute(RK.AttrKind);
392  if (HasSameKindAttr)
394  Arg->getAttribute(RK.AttrKind).getValueAsInt() >=
395  RK.ArgValue) {
396  RemoveFromAssume();
397  continue;
398  }
400  Assume, &*F.getEntryBlock().getFirstInsertionPt()) ||
401  Assume == &*F.getEntryBlock().getFirstInsertionPt()) {
402  if (HasSameKindAttr)
403  Arg->removeAttr(RK.AttrKind);
404  Arg->addAttr(Attribute::get(C, RK.AttrKind, RK.ArgValue));
405  MadeChange = true;
406  RemoveFromAssume();
407  continue;
408  }
409  }
410  auto &Lookup = Knowledge[{RK.WasOn, RK.AttrKind}];
411  for (MapValue &Elem : Lookup) {
412  if (!isValidAssumeForContext(Elem.Assume, Assume, DT))
413  continue;
414  if (Elem.ArgValue >= RK.ArgValue) {
415  RemoveFromAssume();
416  continue;
417  } else if (isValidAssumeForContext(Assume, Elem.Assume, DT)) {
418  Elem.Assume->op_begin()[Elem.BOI->Begin + ABA_Argument].set(
420  MadeChange = true;
421  RemoveFromAssume();
422  continue;
423  }
424  }
425  Lookup.push_back({Assume, RK.ArgValue, &BOI});
426  }
427  }
428  }
429 
430  using MergeIterator = SmallVectorImpl<IntrinsicInst *>::iterator;
431 
432  /// Merge all Assumes from Begin to End in and insert the resulting assume as
433  /// high as possible in the basicblock.
434  void mergeRange(BasicBlock *BB, MergeIterator Begin, MergeIterator End) {
435  if (Begin == End || std::next(Begin) == End)
436  return;
437  /// Provide no additional information so that AssumeBuilderState doesn't
438  /// try to do any punning since it already has been done better.
439  AssumeBuilderState Builder(F.getParent());
440 
441  /// For now it is initialized to the best value it could have
442  Instruction *InsertPt = BB->getFirstNonPHI();
443  if (isa<LandingPadInst>(InsertPt))
444  InsertPt = InsertPt->getNextNode();
445  for (IntrinsicInst *I : make_range(Begin, End)) {
446  CleanupToDo.insert(I);
447  for (CallInst::BundleOpInfo &BOI : I->bundle_op_infos()) {
449  if (!RK)
450  continue;
451  Builder.addKnowledge(RK);
452  if (auto *I = dyn_cast_or_null<Instruction>(RK.WasOn))
453  if (I->getParent() == InsertPt->getParent() &&
454  (InsertPt->comesBefore(I) || InsertPt == I))
455  InsertPt = I->getNextNode();
456  }
457  }
458 
459  /// Adjust InsertPt if it is before Begin, since mergeAssumes only
460  /// guarantees we can place the resulting assume between Begin and End.
461  if (InsertPt->comesBefore(*Begin))
462  for (auto It = (*Begin)->getIterator(), E = InsertPt->getIterator();
463  It != E; --It)
465  InsertPt = It->getNextNode();
466  break;
467  }
468  IntrinsicInst *MergedAssume = Builder.build();
469  if (!MergedAssume)
470  return;
471  MadeChange = true;
472  MergedAssume->insertBefore(InsertPt);
473  AC.registerAssumption(MergedAssume);
474  }
475 
476  /// Merge assume when they are in the same BasicBlock and for all instruction
477  /// between them isGuaranteedToTransferExecutionToSuccessor returns true.
478  void mergeAssumes() {
479  buildMapping(true);
480 
481  SmallVector<MergeIterator, 4> SplitPoints;
482  for (auto &Elem : BBToAssume) {
483  SmallVectorImpl<IntrinsicInst *> &AssumesInBB = Elem.second;
484  if (AssumesInBB.size() < 2)
485  continue;
486  /// AssumesInBB is already sorted by order in the block.
487 
488  BasicBlock::iterator It = AssumesInBB.front()->getIterator();
489  BasicBlock::iterator E = AssumesInBB.back()->getIterator();
490  SplitPoints.push_back(AssumesInBB.begin());
491  MergeIterator LastSplit = AssumesInBB.begin();
492  for (; It != E; ++It)
494  for (; (*LastSplit)->comesBefore(&*It); ++LastSplit)
495  ;
496  if (SplitPoints.back() != LastSplit)
497  SplitPoints.push_back(LastSplit);
498  }
499  SplitPoints.push_back(AssumesInBB.end());
500  for (auto SplitIt = SplitPoints.begin();
501  SplitIt != std::prev(SplitPoints.end()); SplitIt++) {
502  mergeRange(Elem.first, *SplitIt, *(SplitIt + 1));
503  }
504  SplitPoints.clear();
505  }
506  }
507 };
508 
509 bool simplifyAssumes(Function &F, AssumptionCache *AC, DominatorTree *DT) {
510  AssumeSimplify AS(F, *AC, DT, F.getContext());
511 
512  /// Remove knowledge that is already known by a dominating other assume or an
513  /// attribute.
514  AS.dropRedundantKnowledge();
515 
516  /// Remove assume that are empty.
517  AS.RunCleanup(false);
518 
519  /// Merge assume in the same basicblock when possible.
520  AS.mergeAssumes();
521 
522  /// Remove assume that were merged.
523  AS.RunCleanup(true);
524  return AS.MadeChange;
525 }
526 
527 } // namespace
528 
532  return PreservedAnalyses::all();
533  simplifyAssumes(F, &AM.getResult<AssumptionAnalysis>(F),
535  return PreservedAnalyses::all();
536 }
537 
538 namespace {
539 class AssumeSimplifyPassLegacyPass : public FunctionPass {
540 public:
541  static char ID;
542 
543  AssumeSimplifyPassLegacyPass() : FunctionPass(ID) {
546  }
547  bool runOnFunction(Function &F) override {
548  if (skipFunction(F) || !EnableKnowledgeRetention)
549  return false;
550  AssumptionCache &AC =
551  getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
553  getAnalysisIfAvailable<DominatorTreeWrapperPass>();
554  return simplifyAssumes(F, &AC, DTWP ? &DTWP->getDomTree() : nullptr);
555  }
556 
557  void getAnalysisUsage(AnalysisUsage &AU) const override {
559 
560  AU.setPreservesAll();
561  }
562 };
563 } // namespace
564 
566 
567 INITIALIZE_PASS_BEGIN(AssumeSimplifyPassLegacyPass, "assume-simplify",
568  "Assume Simplify", false, false)
570 INITIALIZE_PASS_END(AssumeSimplifyPassLegacyPass, "assume-simplify",
571  "Assume Simplify", false, false)
572 
574  return new AssumeSimplifyPassLegacyPass();
575 }
576 
581  for (Instruction &I : instructions(F))
582  salvageKnowledge(&I, AC, DT);
583  return PreservedAnalyses::all();
584 }
585 
586 namespace {
587 class AssumeBuilderPassLegacyPass : public FunctionPass {
588 public:
589  static char ID;
590 
591  AssumeBuilderPassLegacyPass() : FunctionPass(ID) {
593  }
594  bool runOnFunction(Function &F) override {
595  AssumptionCache &AC =
596  getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
598  getAnalysisIfAvailable<DominatorTreeWrapperPass>();
599  for (Instruction &I : instructions(F))
600  salvageKnowledge(&I, &AC, DTWP ? &DTWP->getDomTree() : nullptr);
601  return true;
602  }
603 
604  void getAnalysisUsage(AnalysisUsage &AU) const override {
606 
607  AU.setPreservesAll();
608  }
609 };
610 } // namespace
611 
613 
614 INITIALIZE_PASS_BEGIN(AssumeBuilderPassLegacyPass, "assume-builder",
615  "Assume Builder", false, false)
617 INITIALIZE_PASS_END(AssumeBuilderPassLegacyPass, "assume-builder",
618  "Assume Builder", false, false)
uint64_t CallInst * C
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks &#39;this&#39; from the containing basic block and deletes it.
Definition: Instruction.cpp:80
Align valueOrOne() const
For convenience, returns a valid alignment or 1 if undefined.
Definition: Alignment.h:144
LLVM_NODISCARD std::enable_if_t< !is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type > dyn_cast(const Y &Val)
Definition: Casting.h:334
Value * GetPointerBaseWithConstantOffset(Value *Ptr, int64_t &Offset, const DataLayout &DL, bool AllowNonInbounds=true)
Analyze the specified pointer to see if it can be expressed as a base pointer plus a constant offset...
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Use * getSingleUndroppableUse()
Return true if there is exactly one user of this value that cannot be dropped.
Definition: Value.cpp:152
DEBUG_COUNTER(BuildAssumeCounter, "assume-builder-counter", "Controls which assumes gets created")
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
Definition: ilist_node.h:288
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:769
This class represents lattice values for constants.
Definition: AllocatorList.h:23
void initializeAssumeBuilderPassLegacyPassPass(PassRegistry &)
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:67
StringMapEntry< uint32_t > * getOrInsertBundleTag(StringRef TagName) const
getOrInsertBundleTag - Returns the Tag to use for an operand bundle of name TagName.
static CallInst * Create(FunctionType *Ty, Value *F, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
cl::opt< bool > ShouldPreserveAllAttributes("assume-preserve-all", cl::init(false), cl::Hidden, cl::desc("enable preservation of all attrbitues. even those that are " "unlikely to be usefull"))
An immutable pass that tracks lazily created AssumptionCache objects.
A cache of @llvm.assume calls within a function.
void initializeAssumeSimplifyPassLegacyPassPass(PassRegistry &)
FunctionPass * createAssumeSimplifyPass()
bool isTerminator() const
Definition: Instruction.h:163
cl::opt< bool > EnableKnowledgeRetention("enable-knowledge-retention", cl::init(false), cl::Hidden, cl::desc("enable preservation of attributes throughout code transformation"))
bool isValidAssumeForContext(const Instruction *I, const Instruction *CxtI, const DominatorTree *DT=nullptr)
Return true if it is valid to use the assumptions provided by an assume intrinsic, I, at the point in the control-flow identified by the context instruction, CxtI.
STATISTIC(NumFunctions, "Total number of functions")
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1100
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:233
F(f)
unsigned getPointerAddressSpace() const
Get the address space of this pointer or pointer vector type.
Definition: DerivedTypes.h:718
IntrinsicInst * buildAssumeFromInst(Instruction *I)
Build a call to llvm.assume to preserve informations that can be derived from the given instruction...
static IntegerType * getInt64Ty(LLVMContext &C)
Definition: Type.cpp:187
Hexagon Common GEP
op_iterator op_begin()
Definition: User.h:234
Value * getArgOperand(unsigned i) const
Definition: InstrTypes.h:1259
RetainedKnowledge getKnowledgeForValue(const Value *V, ArrayRef< Attribute::AttrKind > AttrKinds, AssumptionCache *AC=nullptr, function_ref< bool(RetainedKnowledge, Instruction *, const CallBase::BundleOpInfo *)> Filter=[](auto...) { return true;})
Return a valid Knowledge associated to the Value V if its Attribute kind is in AttrKinds and it match...
AnalysisUsage & addRequired()
Used to keep track of an operand bundle.
Definition: InstrTypes.h:1997
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:397
uint64_t getValueAsInt() const
Return the attribute&#39;s value as an integer.
Definition: Attributes.cpp:253
bool isStringAttribute() const
Return true if the attribute is a string (target-dependent) attribute.
Definition: Attributes.cpp:238
LLVMContext & getContext() const
Get the global data context.
Definition: Module.h:253
static int Lookup(ArrayRef< TableEntry > Table, unsigned Opcode)
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:43
A MapVector that performs no allocations if smaller than a certain size.
Definition: MapVector.h:232
unsigned Intr
DominatorTree & getDomTree()
Definition: Dominators.h:270
This file provides an implementation of debug counters.
Key
PAL metadata keys.
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:244
static StringRef getNameFromAttrKind(Attribute::AttrKind AttrKind)
Definition: Attributes.cpp:196
TypeSize getTypeStoreSize(Type *Ty) const
Returns the maximum number of bytes that may be overwritten by storing the specified type...
Definition: DataLayout.h:458
assume Assume Simplify
constexpr StringRef IgnoreBundleTag
Tag in operand bundle indicating that this bundle should be ignored.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:32
uint64_t value() const
This is a hole in the type system and should not be abused.
Definition: Alignment.h:85
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
Function * getDeclaration(Module *M, ID id, ArrayRef< Type *> Tys=None)
Create or insert an LLVM Function declaration for an intrinsic, and return it.
Definition: Function.cpp:1161
Value * getOperand(unsigned i) const
Definition: User.h:169
const BasicBlock & getEntryBlock() const
Definition: Function.h:689
constexpr uint64_t MinAlign(uint64_t A, uint64_t B)
A and B are either alignments or offsets.
Definition: MathExtras.h:673
Attribute::AttrKind AttrKind
Error build(ArrayRef< Module *> Mods, SmallVector< char, 0 > &Symtab, StringTableBuilder &StrtabBuilder, BumpPtrAllocator &Alloc)
Fills in Symtab and StrtabBuilder with a valid symbol and string table for Mods.
Definition: IRSymtab.cpp:342
assume builder
static bool runOnFunction(Function &F, bool PostInlining)
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:434
bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)
Return true if this function can prove that the instruction I will always transfer execution to one o...
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
const Instruction * getFirstNonPHI() const
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
Definition: BasicBlock.cpp:214
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:154
* if(!EatIfPresent(lltok::kw_thread_local)) return false
ParseOptionalThreadLocal := /*empty.
const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
Definition: BasicBlock.cpp:241
void insertBefore(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified instruction...
Definition: Instruction.cpp:86
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:46
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:68
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
bool isPointerTy() const
True if this is an instance of PointerType.
Definition: Type.h:225
Represent the analysis usage information of a pass.
Attribute::AttrKind getKindAsEnum() const
Return the attribute&#39;s kind as an enum (Attribute::AttrKind).
Definition: Attributes.cpp:246
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:284
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
static bool shouldExecute(unsigned CounterName)
Definition: DebugCounter.h:74
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1433
const Function * getFunction() const
Return the function this instruction belongs to.
Definition: Instruction.cpp:72
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
LLVMContext & getContext() const
getContext - Return a reference to the LLVMContext associated with this function. ...
Definition: Function.cpp:252
assume Assume Builder
static UndefValue * get(Type *T)
Static factory methods - Return an &#39;undef&#39; object of the specified type.
Definition: Constants.cpp:1665
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:160
Value * GetUnderlyingObject(Value *V, const DataLayout &DL, unsigned MaxLookup=6)
This method strips off any GEP address adjustments and pointer casts from the specified value...
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
Value * MapValue(const Value *V, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr)
Look up or compute a value in the value map.
Definition: ValueMapper.h:206
static bool doesAttrKindHaveArgument(Attribute::AttrKind AttrKind)
Return true if and only if the attribute has an Argument.
Definition: Attributes.cpp:210
A function analysis which provides an AssumptionCache.
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
const Value * stripInBoundsOffsets(function_ref< void(const Value *)> Func=[](const Value *) {}) const
Strip off pointer casts and inbounds GEPs.
Definition: Value.cpp:682
Iterator for intrusive lists based on ilist_node.
This is the shared class of boolean and integer constants.
Definition: Constants.h:77
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:350
This struct is a compact representation of a valid (power of two) or undefined (0) alignment...
Definition: Alignment.h:119
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:883
Module.h This file contains the declarations for the Module class.
bool isTypeAttribute() const
Return true if the attribute is a type attribute.
Definition: Attributes.cpp:242
static Constant * get(Type *Ty, uint64_t V, bool isSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:786
AttributeList getAttributes() const
Return the parameter attributes for this call.
Definition: InstrTypes.h:1390
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:1685
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:742
Implements a dense probed hash-table based set with some number of buckets stored inline...
Definition: DenseSet.h:273
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
Definition: Instruction.cpp:68
void setPreservesAll()
Set by analyses that do not transform their input at all.
typename SuperClass::iterator iterator
Definition: SmallVector.h:365
void salvageKnowledge(Instruction *I, AssumptionCache *AC=nullptr, DominatorTree *DT=nullptr)
Calls BuildAssumeFromInst and if the resulting llvm.assume is valid insert if before I...
bool isIntAttribute() const
Return true if the attribute is an integer attribute.
Definition: Attributes.cpp:234
void registerAssumption(CallInst *CI)
Add an @llvm.assume intrinsic to this function&#39;s cache.
void clear()
Definition: ilist.h:309
uint64_t getKnownMinSize() const
Definition: TypeSize.h:145
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation.
Definition: InstrTypes.h:1314
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:107
#define I(x, y, z)
Definition: MD5.cpp:59
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
Definition: PassManager.h:788
bool isAssumeWithEmptyBundle(CallInst &Assume)
Return true iff the operand bundles of the provided llvm.assume doesn&#39;t contain any valuable informat...
static Attribute get(LLVMContext &Context, AttrKind Kind, uint64_t Val=0)
Return a uniquified Attribute object.
Definition: Attributes.cpp:81
iterator_range< df_iterator< T > > depth_first(const T &G)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:572
LLVM Value Representation.
Definition: Value.h:74
A container for an operand bundle being viewed as a set of values rather than a set of uses...
Definition: InstrTypes.h:1053
RetainedKnowledge getKnowledgeFromBundle(CallInst &Assume, const CallBase::BundleOpInfo &BOI)
This extracts the Knowledge from an element of an operand bundle.
bool wouldInstructionBeTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction would have no side effects if it was not used...
Definition: Local.cpp:367
INITIALIZE_PASS_BEGIN(AssumeSimplifyPassLegacyPass, "assume-simplify", "Assume Simplify", false, false) INITIALIZE_PASS_END(AssumeSimplifyPassLegacyPass
inst_range instructions(Function *F)
Definition: InstIterator.h:133
iterator_range< bundle_op_iterator > bundle_op_infos()
Return the range [bundle_op_info_begin, bundle_op_info_end).
Definition: InstrTypes.h:2106
A container for analyses that lazily runs them and caches their results.
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:262
assume simplify
Represent one information held inside an operand bundle of an llvm.assume.
bool use_empty() const
Definition: Value.h:341
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
MutableArrayRef< ResultElem > assumptions()
Access the list of assumption handles currently tracked for this function.
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:44
const BasicBlock * getParent() const
Definition: Instruction.h:94
AttrKind
This enumeration lists the attributes that can be associated with parameters, function results...
Definition: Attributes.h:70
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)