LLVM  14.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 
11 #include "llvm/ADT/MapVector.h"
12 #include "llvm/ADT/Statistic.h"
16 #include "llvm/IR/Dominators.h"
17 #include "llvm/IR/Function.h"
18 #include "llvm/IR/InstIterator.h"
19 #include "llvm/IR/IntrinsicInst.h"
20 #include "llvm/IR/Module.h"
21 #include "llvm/InitializePasses.h"
25 
26 using namespace llvm;
27 
28 namespace llvm {
30  "assume-preserve-all", cl::init(false), cl::Hidden,
31  cl::desc("enable preservation of all attrbitues. even those that are "
32  "unlikely to be usefull"));
33 
35  "enable-knowledge-retention", cl::init(false), cl::Hidden,
36  cl::desc(
37  "enable preservation of attributes throughout code transformation"));
38 } // namespace llvm
39 
40 #define DEBUG_TYPE "assume-builder"
41 
42 STATISTIC(NumAssumeBuilt, "Number of assume built by the assume builder");
43 STATISTIC(NumBundlesInAssumes, "Total number of Bundles in the assume built");
44 STATISTIC(NumAssumesMerged,
45  "Number of assume merged by the assume simplify pass");
46 STATISTIC(NumAssumesRemoved,
47  "Number of assume removed by the assume simplify pass");
48 
49 DEBUG_COUNTER(BuildAssumeCounter, "assume-builder-counter",
50  "Controls which assumes gets created");
51 
52 namespace {
53 
54 bool isUsefullToPreserve(Attribute::AttrKind Kind) {
55  switch (Kind) {
56  case Attribute::NonNull:
57  case Attribute::NoUndef:
58  case Attribute::Alignment:
59  case Attribute::Dereferenceable:
60  case Attribute::DereferenceableOrNull:
61  case Attribute::Cold:
62  return true;
63  default:
64  return false;
65  }
66 }
67 
68 /// This function will try to transform the given knowledge into a more
69 /// canonical one. the canonical knowledge maybe the given one.
70 RetainedKnowledge canonicalizedKnowledge(RetainedKnowledge RK,
71  const DataLayout &DL) {
72  switch (RK.AttrKind) {
73  default:
74  return RK;
75  case Attribute::NonNull:
77  return RK;
78  case Attribute::Alignment: {
79  Value *V = RK.WasOn->stripInBoundsOffsets([&](const Value *Strip) {
80  if (auto *GEP = dyn_cast<GEPOperator>(Strip))
81  RK.ArgValue =
82  MinAlign(RK.ArgValue, GEP->getMaxPreservedAlignment(DL).value());
83  });
84  RK.WasOn = V;
85  return RK;
86  }
87  case Attribute::Dereferenceable:
88  case Attribute::DereferenceableOrNull: {
89  int64_t Offset = 0;
91  /*AllowNonInBounds*/ false);
92  if (Offset < 0)
93  return RK;
94  RK.ArgValue = RK.ArgValue + Offset;
95  RK.WasOn = V;
96  }
97  }
98  return RK;
99 }
100 
101 /// This class contain all knowledge that have been gather while building an
102 /// llvm.assume and the function to manipulate it.
103 struct AssumeBuilderState {
104  Module *M;
105 
106  using MapKey = std::pair<Value *, Attribute::AttrKind>;
107  SmallMapVector<MapKey, uint64_t, 8> AssumedKnowledgeMap;
108  Instruction *InstBeingModified = nullptr;
109  AssumptionCache* AC = nullptr;
110  DominatorTree* DT = nullptr;
111 
112  AssumeBuilderState(Module *M, Instruction *I = nullptr,
113  AssumptionCache *AC = nullptr, DominatorTree *DT = nullptr)
114  : M(M), InstBeingModified(I), AC(AC), DT(DT) {}
115 
116  bool tryToPreserveWithoutAddingAssume(RetainedKnowledge RK) {
117  if (!InstBeingModified || !RK.WasOn)
118  return false;
119  bool HasBeenPreserved = false;
120  Use* ToUpdate = nullptr;
122  RK.WasOn, {RK.AttrKind}, AC,
123  [&](RetainedKnowledge RKOther, Instruction *Assume,
124  const CallInst::BundleOpInfo *Bundle) {
125  if (!isValidAssumeForContext(Assume, InstBeingModified, DT))
126  return false;
127  if (RKOther.ArgValue >= RK.ArgValue) {
128  HasBeenPreserved = true;
129  return true;
130  } else if (isValidAssumeForContext(InstBeingModified, Assume, DT)) {
131  HasBeenPreserved = true;
132  IntrinsicInst *Intr = cast<IntrinsicInst>(Assume);
133  ToUpdate = &Intr->op_begin()[Bundle->Begin + ABA_Argument];
134  return true;
135  }
136  return false;
137  });
138  if (ToUpdate)
139  ToUpdate->set(
140  ConstantInt::get(Type::getInt64Ty(M->getContext()), RK.ArgValue));
141  return HasBeenPreserved;
142  }
143 
144  bool isKnowledgeWorthPreserving(RetainedKnowledge RK) {
145  if (!RK)
146  return false;
147  if (!RK.WasOn)
148  return true;
149  if (RK.WasOn->getType()->isPointerTy()) {
150  Value *UnderlyingPtr = getUnderlyingObject(RK.WasOn);
151  if (isa<AllocaInst>(UnderlyingPtr) || isa<GlobalValue>(UnderlyingPtr))
152  return false;
153  }
154  if (auto *Arg = dyn_cast<Argument>(RK.WasOn)) {
155  if (Arg->hasAttribute(RK.AttrKind) &&
157  Arg->getAttribute(RK.AttrKind).getValueAsInt() >= RK.ArgValue))
158  return false;
159  return true;
160  }
161  if (auto *Inst = dyn_cast<Instruction>(RK.WasOn))
163  if (RK.WasOn->use_empty())
164  return false;
165  Use *SingleUse = RK.WasOn->getSingleUndroppableUse();
166  if (SingleUse && SingleUse->getUser() == InstBeingModified)
167  return false;
168  }
169  return true;
170  }
171 
172  void addKnowledge(RetainedKnowledge RK) {
173  RK = canonicalizedKnowledge(RK, M->getDataLayout());
174 
175  if (!isKnowledgeWorthPreserving(RK))
176  return;
177 
178  if (tryToPreserveWithoutAddingAssume(RK))
179  return;
180  MapKey Key{RK.WasOn, RK.AttrKind};
181  auto Lookup = AssumedKnowledgeMap.find(Key);
182  if (Lookup == AssumedKnowledgeMap.end()) {
183  AssumedKnowledgeMap[Key] = RK.ArgValue;
184  return;
185  }
186  assert(((Lookup->second == 0 && RK.ArgValue == 0) ||
187  (Lookup->second != 0 && RK.ArgValue != 0)) &&
188  "inconsistent argument value");
189 
190  /// This is only desirable because for all attributes taking an argument
191  /// higher is better.
192  Lookup->second = std::max(Lookup->second, RK.ArgValue);
193  }
194 
195  void addAttribute(Attribute Attr, Value *WasOn) {
196  if (Attr.isTypeAttribute() || Attr.isStringAttribute() ||
198  !isUsefullToPreserve(Attr.getKindAsEnum())))
199  return;
200  uint64_t AttrArg = 0;
201  if (Attr.isIntAttribute())
202  AttrArg = Attr.getValueAsInt();
203  addKnowledge({Attr.getKindAsEnum(), AttrArg, WasOn});
204  }
205 
206  void addCall(const CallBase *Call) {
207  auto addAttrList = [&](AttributeList AttrList, unsigned NumArgs) {
208  for (unsigned Idx = 0; Idx < NumArgs; Idx++)
209  for (Attribute Attr : AttrList.getParamAttrs(Idx)) {
210  bool IsPoisonAttr = Attr.hasAttribute(Attribute::NonNull) ||
211  Attr.hasAttribute(Attribute::Alignment);
212  if (!IsPoisonAttr || Call->isPassingUndefUB(Idx))
213  addAttribute(Attr, Call->getArgOperand(Idx));
214  }
215  for (Attribute Attr : AttrList.getFnAttrs())
216  addAttribute(Attr, nullptr);
217  };
218  addAttrList(Call->getAttributes(), Call->arg_size());
219  if (Function *Fn = Call->getCalledFunction())
220  addAttrList(Fn->getAttributes(), Fn->arg_size());
221  }
222 
223  AssumeInst *build() {
224  if (AssumedKnowledgeMap.empty())
225  return nullptr;
226  if (!DebugCounter::shouldExecute(BuildAssumeCounter))
227  return nullptr;
228  Function *FnAssume = Intrinsic::getDeclaration(M, Intrinsic::assume);
229  LLVMContext &C = M->getContext();
231  for (auto &MapElem : AssumedKnowledgeMap) {
233  if (MapElem.first.first)
234  Args.push_back(MapElem.first.first);
235 
236  /// This is only valid because for all attribute that currently exist a
237  /// value of 0 is useless. and should not be preserved.
238  if (MapElem.second)
239  Args.push_back(ConstantInt::get(Type::getInt64Ty(M->getContext()),
240  MapElem.second));
241  OpBundle.push_back(OperandBundleDefT<Value *>(
242  std::string(Attribute::getNameFromAttrKind(MapElem.first.second)),
243  Args));
244  NumBundlesInAssumes++;
245  }
246  NumAssumeBuilt++;
247  return cast<AssumeInst>(CallInst::Create(
248  FnAssume, ArrayRef<Value *>({ConstantInt::getTrue(C)}), OpBundle));
249  }
250 
251  void addAccessedPtr(Instruction *MemInst, Value *Pointer, Type *AccType,
252  MaybeAlign MA) {
253  unsigned DerefSize = MemInst->getModule()
254  ->getDataLayout()
255  .getTypeStoreSize(AccType)
256  .getKnownMinSize();
257  if (DerefSize != 0) {
258  addKnowledge({Attribute::Dereferenceable, DerefSize, Pointer});
259  if (!NullPointerIsDefined(MemInst->getFunction(),
260  Pointer->getType()->getPointerAddressSpace()))
261  addKnowledge({Attribute::NonNull, 0u, Pointer});
262  }
263  if (MA.valueOrOne() > 1)
264  addKnowledge({Attribute::Alignment, MA.valueOrOne().value(), Pointer});
265  }
266 
267  void addInstruction(Instruction *I) {
268  if (auto *Call = dyn_cast<CallBase>(I))
269  return addCall(Call);
270  if (auto *Load = dyn_cast<LoadInst>(I))
271  return addAccessedPtr(I, Load->getPointerOperand(), Load->getType(),
272  Load->getAlign());
273  if (auto *Store = dyn_cast<StoreInst>(I))
274  return addAccessedPtr(I, Store->getPointerOperand(),
275  Store->getValueOperand()->getType(),
276  Store->getAlign());
277  // TODO: Add support for the other Instructions.
278  // TODO: Maybe we should look around and merge with other llvm.assume.
279  }
280 };
281 
282 } // namespace
283 
286  return nullptr;
287  AssumeBuilderState Builder(I->getModule());
288  Builder.addInstruction(I);
289  return Builder.build();
290 }
291 
293  DominatorTree *DT) {
294  if (!EnableKnowledgeRetention || I->isTerminator())
295  return;
296  AssumeBuilderState Builder(I->getModule(), I, AC, DT);
297  Builder.addInstruction(I);
298  if (auto *Intr = Builder.build()) {
299  Intr->insertBefore(I);
300  if (AC)
302  }
303 }
304 
305 AssumeInst *
307  Instruction *CtxI, AssumptionCache *AC,
308  DominatorTree *DT) {
309  AssumeBuilderState Builder(CtxI->getModule(), CtxI, AC, DT);
310  for (const RetainedKnowledge &RK : Knowledge)
311  Builder.addKnowledge(RK);
312  return Builder.build();
313 }
314 
317  AssumptionCache *AC,
318  DominatorTree *DT) {
319  AssumeBuilderState Builder(Assume->getModule(), Assume, AC, DT);
320  RK = canonicalizedKnowledge(RK, Assume->getModule()->getDataLayout());
321 
322  if (!Builder.isKnowledgeWorthPreserving(RK))
323  return RetainedKnowledge::none();
324 
325  if (Builder.tryToPreserveWithoutAddingAssume(RK))
326  return RetainedKnowledge::none();
327  return RK;
328 }
329 
330 namespace {
331 
332 struct AssumeSimplify {
333  Function &F;
334  AssumptionCache &AC;
335  DominatorTree *DT;
336  LLVMContext &C;
337  SmallDenseSet<IntrinsicInst *> CleanupToDo;
338  StringMapEntry<uint32_t> *IgnoreTag;
340  bool MadeChange = false;
341 
342  AssumeSimplify(Function &F, AssumptionCache &AC, DominatorTree *DT,
343  LLVMContext &C)
344  : F(F), AC(AC), DT(DT), C(C),
345  IgnoreTag(C.getOrInsertBundleTag(IgnoreBundleTag)) {}
346 
347  void buildMapping(bool FilterBooleanArgument) {
348  BBToAssume.clear();
349  for (Value *V : AC.assumptions()) {
350  if (!V)
351  continue;
352  IntrinsicInst *Assume = cast<IntrinsicInst>(V);
353  if (FilterBooleanArgument) {
354  auto *Arg = dyn_cast<ConstantInt>(Assume->getOperand(0));
355  if (!Arg || Arg->isZero())
356  continue;
357  }
358  BBToAssume[Assume->getParent()].push_back(Assume);
359  }
360 
361  for (auto &Elem : BBToAssume) {
362  llvm::sort(Elem.second,
363  [](const IntrinsicInst *LHS, const IntrinsicInst *RHS) {
364  return LHS->comesBefore(RHS);
365  });
366  }
367  }
368 
369  /// Remove all asumes in CleanupToDo if there boolean argument is true and
370  /// ForceCleanup is set or the assume doesn't hold valuable knowledge.
371  void RunCleanup(bool ForceCleanup) {
372  for (IntrinsicInst *Assume : CleanupToDo) {
373  auto *Arg = dyn_cast<ConstantInt>(Assume->getOperand(0));
374  if (!Arg || Arg->isZero() ||
375  (!ForceCleanup &&
376  !isAssumeWithEmptyBundle(cast<AssumeInst>(*Assume))))
377  continue;
378  MadeChange = true;
379  if (ForceCleanup)
380  NumAssumesMerged++;
381  else
382  NumAssumesRemoved++;
383  Assume->eraseFromParent();
384  }
385  CleanupToDo.clear();
386  }
387 
388  /// Remove knowledge stored in assume when it is already know by an attribute
389  /// or an other assume. This can when valid update an existing knowledge in an
390  /// attribute or an other assume.
391  void dropRedundantKnowledge() {
392  struct MapValue {
393  IntrinsicInst *Assume;
394  uint64_t ArgValue;
395  CallInst::BundleOpInfo *BOI;
396  };
397  buildMapping(false);
400  Knowledge;
401  for (BasicBlock *BB : depth_first(&F))
402  for (Value *V : BBToAssume[BB]) {
403  if (!V)
404  continue;
405  IntrinsicInst *Assume = cast<IntrinsicInst>(V);
406  for (CallInst::BundleOpInfo &BOI : Assume->bundle_op_infos()) {
407  auto RemoveFromAssume = [&]() {
408  CleanupToDo.insert(Assume);
409  if (BOI.Begin != BOI.End) {
410  Use *U = &Assume->op_begin()[BOI.Begin + ABA_WasOn];
411  U->set(UndefValue::get(U->get()->getType()));
412  }
413  BOI.Tag = IgnoreTag;
414  };
415  if (BOI.Tag == IgnoreTag) {
416  CleanupToDo.insert(Assume);
417  continue;
418  }
419  RetainedKnowledge RK =
420  getKnowledgeFromBundle(cast<AssumeInst>(*Assume), BOI);
421  if (auto *Arg = dyn_cast_or_null<Argument>(RK.WasOn)) {
422  bool HasSameKindAttr = Arg->hasAttribute(RK.AttrKind);
423  if (HasSameKindAttr)
424  if (!Attribute::isIntAttrKind(RK.AttrKind) ||
425  Arg->getAttribute(RK.AttrKind).getValueAsInt() >=
426  RK.ArgValue) {
427  RemoveFromAssume();
428  continue;
429  }
431  Assume, &*F.getEntryBlock().getFirstInsertionPt()) ||
432  Assume == &*F.getEntryBlock().getFirstInsertionPt()) {
433  if (HasSameKindAttr)
434  Arg->removeAttr(RK.AttrKind);
435  Arg->addAttr(Attribute::get(C, RK.AttrKind, RK.ArgValue));
436  MadeChange = true;
437  RemoveFromAssume();
438  continue;
439  }
440  }
441  auto &Lookup = Knowledge[{RK.WasOn, RK.AttrKind}];
442  for (MapValue &Elem : Lookup) {
443  if (!isValidAssumeForContext(Elem.Assume, Assume, DT))
444  continue;
445  if (Elem.ArgValue >= RK.ArgValue) {
446  RemoveFromAssume();
447  continue;
448  } else if (isValidAssumeForContext(Assume, Elem.Assume, DT)) {
449  Elem.Assume->op_begin()[Elem.BOI->Begin + ABA_Argument].set(
450  ConstantInt::get(Type::getInt64Ty(C), RK.ArgValue));
451  MadeChange = true;
452  RemoveFromAssume();
453  continue;
454  }
455  }
456  Lookup.push_back({Assume, RK.ArgValue, &BOI});
457  }
458  }
459  }
460 
461  using MergeIterator = SmallVectorImpl<IntrinsicInst *>::iterator;
462 
463  /// Merge all Assumes from Begin to End in and insert the resulting assume as
464  /// high as possible in the basicblock.
465  void mergeRange(BasicBlock *BB, MergeIterator Begin, MergeIterator End) {
466  if (Begin == End || std::next(Begin) == End)
467  return;
468  /// Provide no additional information so that AssumeBuilderState doesn't
469  /// try to do any punning since it already has been done better.
470  AssumeBuilderState Builder(F.getParent());
471 
472  /// For now it is initialized to the best value it could have
473  Instruction *InsertPt = BB->getFirstNonPHI();
474  if (isa<LandingPadInst>(InsertPt))
475  InsertPt = InsertPt->getNextNode();
476  for (IntrinsicInst *I : make_range(Begin, End)) {
477  CleanupToDo.insert(I);
478  for (CallInst::BundleOpInfo &BOI : I->bundle_op_infos()) {
479  RetainedKnowledge RK =
480  getKnowledgeFromBundle(cast<AssumeInst>(*I), BOI);
481  if (!RK)
482  continue;
483  Builder.addKnowledge(RK);
484  if (auto *I = dyn_cast_or_null<Instruction>(RK.WasOn))
485  if (I->getParent() == InsertPt->getParent() &&
486  (InsertPt->comesBefore(I) || InsertPt == I))
487  InsertPt = I->getNextNode();
488  }
489  }
490 
491  /// Adjust InsertPt if it is before Begin, since mergeAssumes only
492  /// guarantees we can place the resulting assume between Begin and End.
493  if (InsertPt->comesBefore(*Begin))
494  for (auto It = (*Begin)->getIterator(), E = InsertPt->getIterator();
495  It != E; --It)
497  InsertPt = It->getNextNode();
498  break;
499  }
500  auto *MergedAssume = Builder.build();
501  if (!MergedAssume)
502  return;
503  MadeChange = true;
504  MergedAssume->insertBefore(InsertPt);
505  AC.registerAssumption(MergedAssume);
506  }
507 
508  /// Merge assume when they are in the same BasicBlock and for all instruction
509  /// between them isGuaranteedToTransferExecutionToSuccessor returns true.
510  void mergeAssumes() {
511  buildMapping(true);
512 
513  SmallVector<MergeIterator, 4> SplitPoints;
514  for (auto &Elem : BBToAssume) {
515  SmallVectorImpl<IntrinsicInst *> &AssumesInBB = Elem.second;
516  if (AssumesInBB.size() < 2)
517  continue;
518  /// AssumesInBB is already sorted by order in the block.
519 
520  BasicBlock::iterator It = AssumesInBB.front()->getIterator();
521  BasicBlock::iterator E = AssumesInBB.back()->getIterator();
522  SplitPoints.push_back(AssumesInBB.begin());
523  MergeIterator LastSplit = AssumesInBB.begin();
524  for (; It != E; ++It)
526  for (; (*LastSplit)->comesBefore(&*It); ++LastSplit)
527  ;
528  if (SplitPoints.back() != LastSplit)
529  SplitPoints.push_back(LastSplit);
530  }
531  SplitPoints.push_back(AssumesInBB.end());
532  for (auto SplitIt = SplitPoints.begin();
533  SplitIt != std::prev(SplitPoints.end()); SplitIt++) {
534  mergeRange(Elem.first, *SplitIt, *(SplitIt + 1));
535  }
536  SplitPoints.clear();
537  }
538  }
539 };
540 
541 bool simplifyAssumes(Function &F, AssumptionCache *AC, DominatorTree *DT) {
542  AssumeSimplify AS(F, *AC, DT, F.getContext());
543 
544  /// Remove knowledge that is already known by a dominating other assume or an
545  /// attribute.
546  AS.dropRedundantKnowledge();
547 
548  /// Remove assume that are empty.
549  AS.RunCleanup(false);
550 
551  /// Merge assume in the same basicblock when possible.
552  AS.mergeAssumes();
553 
554  /// Remove assume that were merged.
555  AS.RunCleanup(true);
556  return AS.MadeChange;
557 }
558 
559 } // namespace
560 
561 PreservedAnalyses AssumeSimplifyPass::run(Function &F,
564  return PreservedAnalyses::all();
565  simplifyAssumes(F, &AM.getResult<AssumptionAnalysis>(F),
567  return PreservedAnalyses::all();
568 }
569 
570 namespace {
571 class AssumeSimplifyPassLegacyPass : public FunctionPass {
572 public:
573  static char ID;
574 
575  AssumeSimplifyPassLegacyPass() : FunctionPass(ID) {
578  }
579  bool runOnFunction(Function &F) override {
580  if (skipFunction(F) || !EnableKnowledgeRetention)
581  return false;
582  AssumptionCache &AC =
583  getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
585  getAnalysisIfAvailable<DominatorTreeWrapperPass>();
586  return simplifyAssumes(F, &AC, DTWP ? &DTWP->getDomTree() : nullptr);
587  }
588 
589  void getAnalysisUsage(AnalysisUsage &AU) const override {
591 
592  AU.setPreservesAll();
593  }
594 };
595 } // namespace
596 
598 
599 INITIALIZE_PASS_BEGIN(AssumeSimplifyPassLegacyPass, "assume-simplify",
600  "Assume Simplify", false, false)
602 INITIALIZE_PASS_END(AssumeSimplifyPassLegacyPass, "assume-simplify",
603  "Assume Simplify", false, false)
604 
606  return new AssumeSimplifyPassLegacyPass();
607 }
608 
613  for (Instruction &I : instructions(F))
614  salvageKnowledge(&I, AC, DT);
615  return PreservedAnalyses::all();
616 }
617 
618 namespace {
619 class AssumeBuilderPassLegacyPass : public FunctionPass {
620 public:
621  static char ID;
622 
623  AssumeBuilderPassLegacyPass() : FunctionPass(ID) {
625  }
626  bool runOnFunction(Function &F) override {
627  AssumptionCache &AC =
628  getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
630  getAnalysisIfAvailable<DominatorTreeWrapperPass>();
631  for (Instruction &I : instructions(F))
632  salvageKnowledge(&I, &AC, DTWP ? &DTWP->getDomTree() : nullptr);
633  return true;
634  }
635 
636  void getAnalysisUsage(AnalysisUsage &AU) const override {
638 
639  AU.setPreservesAll();
640  }
641 };
642 } // namespace
643 
645 
646 INITIALIZE_PASS_BEGIN(AssumeBuilderPassLegacyPass, "assume-builder",
647  "Assume Builder", false, false)
649 INITIALIZE_PASS_END(AssumeBuilderPassLegacyPass, "assume-builder",
650  "Assume Builder", false, false)
llvm::RetainedKnowledge::WasOn
Value * WasOn
Definition: AssumeBundleQueries.h:103
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm::createAssumeSimplifyPass
FunctionPass * createAssumeSimplifyPass()
Definition: AssumeBundleBuilder.cpp:605
AssumptionCache.h
llvm
This file implements support for optimizing divisions by a constant.
Definition: AllocatorList.h:23
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
llvm::Instruction::getModule
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
Definition: Instruction.cpp:66
llvm::make_range
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
Definition: iterator_range.h:53
llvm::AssumptionCache::registerAssumption
void registerAssumption(AssumeInst *CI)
Add an @llvm.assume intrinsic to this function's cache.
Definition: AssumptionCache.cpp:217
llvm::StringMapEntry< uint32_t >
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:113
llvm::ABA_Argument
@ ABA_Argument
Definition: AssumeBundleQueries.h:31
llvm::Intrinsic::getDeclaration
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:1379
llvm::BasicBlock::iterator
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:90
IntrinsicInst.h
llvm::Type::isPointerTy
bool isPointerTy() const
True if this is an instance of PointerType.
Definition: Type.h:217
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:783
InstIterator.h
llvm::Attribute::hasAttribute
bool hasAttribute(AttrKind Val) const
Return true if the attribute is present.
Definition: Attributes.cpp:316
llvm::Function
Definition: Function.h:62
llvm::Attribute
Definition: Attributes.h:52
llvm::Attribute::isTypeAttribute
bool isTypeAttribute() const
Return true if the attribute is a type attribute.
Definition: Attributes.cpp:269
llvm::Attribute::isIntAttrKind
static bool isIntAttrKind(AttrKind Kind)
Definition: Attributes.h:87
llvm::ilist_node_with_parent::getNextNode
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
Definition: ilist_node.h:288
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
Statistic.h
llvm::DataLayout::getTypeStoreSize
TypeSize getTypeStoreSize(Type *Ty) const
Returns the maximum number of bytes that may be overwritten by storing the specified type.
Definition: DataLayout.h:471
builder
assume builder
Definition: AssumeBundleBuilder.cpp:649
llvm::IgnoreBundleTag
constexpr StringRef IgnoreBundleTag
Tag in operand bundle indicating that this bundle should be ignored.
Definition: AssumeBundleQueries.h:135
llvm::SmallDenseSet
Implements a dense probed hash-table based set with some number of buckets stored inline.
Definition: DenseSet.h:286
MapVector.h
llvm::SmallDenseMap
Definition: DenseMap.h:880
ValueTracking.h
llvm::isAssumeWithEmptyBundle
bool isAssumeWithEmptyBundle(AssumeInst &Assume)
Return true iff the operand bundles of the provided llvm.assume doesn't contain any valuable informat...
Definition: AssumeBundleQueries.cpp:125
Local.h
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:143
llvm::AssumeInst
This represents the llvm.assume intrinsic.
Definition: IntrinsicInst.h:1319
llvm::MapValue
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:209
llvm::SPII::Load
@ Load
Definition: SparcInstrInfo.h:32
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
Module.h
llvm::AttributeList
Definition: Attributes.h:399
llvm::MaybeAlign::valueOrOne
Align valueOrOne() const
For convenience, returns a valid alignment or 1 if undefined.
Definition: Alignment.h:134
llvm::OperandBundleDefT
A container for an operand bundle being viewed as a set of values rather than a set of uses.
Definition: InstrTypes.h:1114
llvm::simplifyRetainedKnowledge
RetainedKnowledge simplifyRetainedKnowledge(AssumeInst *Assume, RetainedKnowledge RK, AssumptionCache *AC, DominatorTree *DT)
canonicalize the RetainedKnowledge RK.
Definition: AssumeBundleBuilder.cpp:315
llvm::Instruction::comesBefore
bool comesBefore(const Instruction *Other) const
Given an instruction Other in the same basic block as this instruction, return true if this instructi...
Definition: Instruction.cpp:111
llvm::CallBase::bundle_op_infos
iterator_range< bundle_op_iterator > bundle_op_infos()
Return the range [bundle_op_info_begin, bundle_op_info_end).
Definition: InstrTypes.h:2217
llvm::AttributeList::getFnAttrs
AttributeSet getFnAttrs() const
The function attributes are returned.
Definition: Attributes.cpp:1362
llvm::EnableKnowledgeRetention
cl::opt< bool > EnableKnowledgeRetention
enable preservation of attributes in assume like: call void @llvm.assume(i1 true) [ "nonnull"(i32* PT...
Definition: InstCombineCalls.cpp:98
DEBUG_COUNTER
DEBUG_COUNTER(BuildAssumeCounter, "assume-builder-counter", "Controls which assumes gets created")
Offset
uint64_t Offset
Definition: ELFObjHandler.cpp:81
llvm::codeview::PointerMode::Pointer
@ Pointer
DepthFirstIterator.h
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
Arg
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
Definition: AMDGPULibCalls.cpp:206
CommandLine.h
llvm::Attribute::getValueAsInt
uint64_t getValueAsInt() const
Return the attribute's value as an integer.
Definition: Attributes.cpp:280
llvm::MinAlign
constexpr uint64_t MinAlign(uint64_t A, uint64_t B)
A and B are either alignments or offsets.
Definition: MathExtras.h:672
llvm::isValidAssumeForContext
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,...
Definition: ValueTracking.cpp:516
llvm::initializeAssumeBuilderPassLegacyPassPass
void initializeAssumeBuilderPassLegacyPassPass(PassRegistry &)
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
llvm::ABA_WasOn
@ ABA_WasOn
Definition: AssumeBundleQueries.h:30
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
Intr
unsigned Intr
Definition: AMDGPUBaseInfo.cpp:1991
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::Value::getSingleUndroppableUse
Use * getSingleUndroppableUse()
Return true if there is exactly one use of this value that cannot be dropped.
Definition: Value.cpp:167
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(AssumeSimplifyPassLegacyPass, "assume-simplify", "Assume Simplify", false, false) INITIALIZE_PASS_END(AssumeSimplifyPassLegacyPass
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
AssumeBundleQueries.h
llvm::AMDGPU::PALMD::Key
Key
PAL metadata keys.
Definition: AMDGPUMetadata.h:481
AssumeBundleBuilder.h
false
Definition: StackSlotColoring.cpp:142
llvm::EnableKnowledgeRetention
cl::opt< bool > EnableKnowledgeRetention("enable-knowledge-retention", cl::init(false), cl::Hidden, cl::desc("enable preservation of attributes throughout code transformation"))
llvm::MaybeAlign
This struct is a compact representation of a valid (power of two) or undefined (0) alignment.
Definition: Alignment.h:109
llvm::Instruction
Definition: Instruction.h:45
llvm::DebugCounter::shouldExecute
static bool shouldExecute(unsigned CounterName)
Definition: DebugCounter.h:74
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:287
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
llvm::buildAssumeFromInst
AssumeInst * buildAssumeFromInst(Instruction *I)
Build a call to llvm.assume to preserve informations that can be derived from the given instruction.
Definition: AssumeBundleBuilder.cpp:284
llvm::ConstantInt::get
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:925
llvm::getUnderlyingObject
const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=6)
This method strips off any GEP address adjustments and pointer casts from the specified value,...
Definition: ValueTracking.cpp:4376
llvm::Attribute::isStringAttribute
bool isStringAttribute() const
Return true if the attribute is a string (target-dependent) attribute.
Definition: Attributes.cpp:265
llvm::getKnowledgeFromBundle
RetainedKnowledge getKnowledgeFromBundle(AssumeInst &Assume, const CallBase::BundleOpInfo &BOI)
This extracts the Knowledge from an element of an operand bundle.
Definition: AssumeBundleQueries.cpp:99
llvm::MCID::Call
@ Call
Definition: MCInstrDesc.h:153
llvm::AssumeBuilderPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: AssumeBundleBuilder.cpp:609
llvm::lltok::Kind
Kind
Definition: LLToken.h:18
llvm::Value::use_empty
bool use_empty() const
Definition: Value.h:344
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
llvm::initializeAssumeSimplifyPassLegacyPassPass
void initializeAssumeSimplifyPassLegacyPassPass(PassRegistry &)
llvm::SmallMapVector
A MapVector that performs no allocations if smaller than a certain size.
Definition: MapVector.h:232
llvm::wouldInstructionBeTriviallyDead
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:405
llvm::cl::opt< bool >
llvm::instructions
inst_range instructions(Function *F)
Definition: InstIterator.h:133
llvm::RetainedKnowledge::AttrKind
Attribute::AttrKind AttrKind
Definition: AssumeBundleQueries.h:101
llvm::Instruction::eraseFromParent
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:78
llvm::MapVector< KeyT, ValueT, SmallDenseMap< KeyT, unsigned, N >, SmallVector< std::pair< KeyT, ValueT >, N > >::find
iterator find(const KeyT &Key)
Definition: MapVector.h:147
llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, 4, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::clear
void clear()
Definition: DenseMap.h:111
uint64_t
llvm::RetainedKnowledge::ArgValue
uint64_t ArgValue
Definition: AssumeBundleQueries.h:102
llvm::AssumptionAnalysis
A function analysis which provides an AssumptionCache.
Definition: AssumptionCache.h:169
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::LLVMContext
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:68
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
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:441
llvm::SPII::Store
@ Store
Definition: SparcInstrInfo.h:33
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::salvageKnowledge
void salvageKnowledge(Instruction *I, AssumptionCache *AC=nullptr, DominatorTree *DT=nullptr)
Calls BuildAssumeFromInst and if the resulting llvm.assume is valid insert if before I.
Definition: AssumeBundleBuilder.cpp:292
llvm::CallingConv::Cold
@ Cold
Definition: CallingConv.h:48
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:67
Builder
assume Assume Builder
Definition: AssumeBundleBuilder.cpp:650
llvm::AssumptionCacheTracker
An immutable pass that tracks lazily created AssumptionCache objects.
Definition: AssumptionCache.h:200
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::AssumptionCache
A cache of @llvm.assume calls within a function.
Definition: AssumptionCache.h:41
Simplify
assume Assume Simplify
Definition: AssumeBundleBuilder.cpp:603
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
if
if(llvm_vc STREQUAL "") set(fake_version_inc "$
Definition: CMakeLists.txt:14
llvm::Instruction::getFunction
const Function * getFunction() const
Return the function this instruction belongs to.
Definition: Instruction.cpp:70
llvm::ilist_node_impl::getIterator
self_iterator getIterator()
Definition: ilist_node.h:81
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
llvm::RetainedKnowledge
Represent one information held inside an operand bundle of an llvm.assume.
Definition: AssumeBundleQueries.h:100
llvm::MapVector< KeyT, ValueT, SmallDenseMap< KeyT, unsigned, N >, SmallVector< std::pair< KeyT, ValueT >, N > >::end
iterator end()
Definition: MapVector.h:71
llvm::Value::stripInBoundsOffsets
const Value * stripInBoundsOffsets(function_ref< void(const Value *)> Func=[](const Value *) {}) const
Strip off pointer casts and inbounds GEPs.
Definition: Value.cpp:776
llvm::depth_first
iterator_range< df_iterator< T > > depth_first(const T &G)
Definition: DepthFirstIterator.h:229
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:69
llvm::MapVector< KeyT, ValueT, SmallDenseMap< KeyT, unsigned, N >, SmallVector< std::pair< KeyT, ValueT >, N > >::empty
bool empty() const
Definition: MapVector.h:79
llvm::Type::getInt64Ty
static IntegerType * getInt64Ty(LLVMContext &C)
Definition: Type.cpp:242
llvm::ConstantInt::getTrue
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:873
llvm::AnalysisUsage::setPreservesAll
void setPreservesAll()
Set by analyses that do not transform their input at all.
Definition: PassAnalysisSupport.h:130
get
Should compile to something r4 addze r3 instead we get
Definition: README.txt:24
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:161
llvm::isGuaranteedToTransferExecutionToSuccessor
bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)
Return true if this function can prove that the instruction I will always transfer execution to one o...
Definition: ValueTracking.cpp:5300
llvm::AnalysisManager::getCachedResult
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
Definition: PassManager.h:802
Function.h
DebugCounter.h
llvm::sort
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1492
llvm::GetPointerBaseWithConstantOffset
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.
Definition: ValueTracking.h:279
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:585
llvm::DominatorTreeWrapperPass::getDomTree
DominatorTree & getDomTree()
Definition: Dominators.h:295
simplify
assume simplify
Definition: AssumeBundleBuilder.cpp:602
Lookup
static int Lookup(ArrayRef< TableEntry > Table, unsigned Opcode)
Definition: X86FloatingPoint.cpp:599
llvm::IntrinsicInst
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:45
llvm::Attribute::getNameFromAttrKind
static StringRef getNameFromAttrKind(Attribute::AttrKind AttrKind)
Definition: Attributes.cpp:231
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:252
llvm::AssumptionCache::assumptions
MutableArrayRef< ResultElem > assumptions()
Access the list of assumption handles currently tracked for this function.
Definition: AssumptionCache.h:146
llvm::User::op_begin
op_iterator op_begin()
Definition: User.h:234
Dominators.h
llvm::SmallVectorImpl::iterator
typename SuperClass::iterator iterator
Definition: SmallVector.h:562
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:94
llvm::max
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:340
llvm::TypeSize::getKnownMinSize
ScalarTy getKnownMinSize() const
Definition: TypeSize.h:427
llvm::buildAssumeFromKnowledge
AssumeInst * buildAssumeFromKnowledge(ArrayRef< RetainedKnowledge > Knowledge, Instruction *CtxI, AssumptionCache *AC=nullptr, DominatorTree *DT=nullptr)
Build and return a new assume created from the provided knowledge if the knowledge in the assume is f...
Definition: AssumeBundleBuilder.cpp:306
llvm::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:43
llvm::Attribute::isIntAttribute
bool isIntAttribute() const
Return true if the attribute is an integer attribute.
Definition: Attributes.cpp:261
llvm::CallBase
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1161
llvm::Module::getDataLayout
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
Definition: Module.cpp:401
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
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
GEP
Hexagon Common GEP
Definition: HexagonCommonGEP.cpp:172
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
llvm::AMDGPU::HSAMD::Kernel::Key::Args
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
Definition: AMDGPUMetadata.h:389
llvm::User::getOperand
Value * getOperand(unsigned i) const
Definition: User.h:169
llvm::cl::desc
Definition: CommandLine.h:412
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:1965
llvm::AttributeList::getParamAttrs
AttributeSet getParamAttrs(unsigned ArgNo) const
The attributes for the argument or parameter at the given index are returned.
Definition: Attributes.cpp:1354
InitializePasses.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44
llvm::ShouldPreserveAllAttributes
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"))
llvm::irsymtab::build
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:356
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37
llvm::getKnowledgeForValue
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...
Definition: AssumeBundleQueries.cpp:154