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, DataLayout DL) {
71  switch (RK.AttrKind) {
72  default:
73  return RK;
74  case Attribute::NonNull:
76  return RK;
77  case Attribute::Alignment: {
78  Value *V = RK.WasOn->stripInBoundsOffsets([&](const Value *Strip) {
79  if (auto *GEP = dyn_cast<GEPOperator>(Strip))
80  RK.ArgValue =
81  MinAlign(RK.ArgValue, GEP->getMaxPreservedAlignment(DL).value());
82  });
83  RK.WasOn = V;
84  return RK;
85  }
86  case Attribute::Dereferenceable:
87  case Attribute::DereferenceableOrNull: {
88  int64_t Offset = 0;
90  /*AllowNonInBounds*/ false);
91  if (Offset < 0)
92  return RK;
93  RK.ArgValue = RK.ArgValue + Offset;
94  RK.WasOn = V;
95  }
96  }
97  return RK;
98 }
99 
100 /// This class contain all knowledge that have been gather while building an
101 /// llvm.assume and the function to manipulate it.
102 struct AssumeBuilderState {
103  Module *M;
104 
105  using MapKey = std::pair<Value *, Attribute::AttrKind>;
106  SmallMapVector<MapKey, unsigned, 8> AssumedKnowledgeMap;
107  Instruction *InstBeingModified = nullptr;
108  AssumptionCache* AC = nullptr;
109  DominatorTree* DT = nullptr;
110 
111  AssumeBuilderState(Module *M, Instruction *I = nullptr,
112  AssumptionCache *AC = nullptr, DominatorTree *DT = nullptr)
113  : M(M), InstBeingModified(I), AC(AC), DT(DT) {}
114 
115  bool tryToPreserveWithoutAddingAssume(RetainedKnowledge RK) {
116  if (!InstBeingModified || !RK.WasOn)
117  return false;
118  bool HasBeenPreserved = false;
119  Use* ToUpdate = nullptr;
121  RK.WasOn, {RK.AttrKind}, AC,
122  [&](RetainedKnowledge RKOther, Instruction *Assume,
123  const CallInst::BundleOpInfo *Bundle) {
124  if (!isValidAssumeForContext(Assume, InstBeingModified, DT))
125  return false;
126  if (RKOther.ArgValue >= RK.ArgValue) {
127  HasBeenPreserved = true;
128  return true;
129  } else if (isValidAssumeForContext(InstBeingModified, Assume, DT)) {
130  HasBeenPreserved = true;
131  IntrinsicInst *Intr = cast<IntrinsicInst>(Assume);
132  ToUpdate = &Intr->op_begin()[Bundle->Begin + ABA_Argument];
133  return true;
134  }
135  return false;
136  });
137  if (ToUpdate)
138  ToUpdate->set(
139  ConstantInt::get(Type::getInt64Ty(M->getContext()), RK.ArgValue));
140  return HasBeenPreserved;
141  }
142 
143  bool isKnowledgeWorthPreserving(RetainedKnowledge RK) {
144  if (!RK)
145  return false;
146  if (!RK.WasOn)
147  return true;
148  if (RK.WasOn->getType()->isPointerTy()) {
149  Value *UnderlyingPtr = getUnderlyingObject(RK.WasOn);
150  if (isa<AllocaInst>(UnderlyingPtr) || isa<GlobalValue>(UnderlyingPtr))
151  return false;
152  }
153  if (auto *Arg = dyn_cast<Argument>(RK.WasOn)) {
154  if (Arg->hasAttribute(RK.AttrKind) &&
156  Arg->getAttribute(RK.AttrKind).getValueAsInt() >= RK.ArgValue))
157  return false;
158  return true;
159  }
160  if (auto *Inst = dyn_cast<Instruction>(RK.WasOn))
162  if (RK.WasOn->use_empty())
163  return false;
164  Use *SingleUse = RK.WasOn->getSingleUndroppableUse();
165  if (SingleUse && SingleUse->getUser() == InstBeingModified)
166  return false;
167  }
168  return true;
169  }
170 
171  void addKnowledge(RetainedKnowledge RK) {
172  RK = canonicalizedKnowledge(RK, M->getDataLayout());
173 
174  if (!isKnowledgeWorthPreserving(RK))
175  return;
176 
177  if (tryToPreserveWithoutAddingAssume(RK))
178  return;
179  MapKey Key{RK.WasOn, RK.AttrKind};
180  auto Lookup = AssumedKnowledgeMap.find(Key);
181  if (Lookup == AssumedKnowledgeMap.end()) {
182  AssumedKnowledgeMap[Key] = RK.ArgValue;
183  return;
184  }
185  assert(((Lookup->second == 0 && RK.ArgValue == 0) ||
186  (Lookup->second != 0 && RK.ArgValue != 0)) &&
187  "inconsistent argument value");
188 
189  /// This is only desirable because for all attributes taking an argument
190  /// higher is better.
191  Lookup->second = std::max(Lookup->second, RK.ArgValue);
192  }
193 
194  void addAttribute(Attribute Attr, Value *WasOn) {
195  if (Attr.isTypeAttribute() || Attr.isStringAttribute() ||
197  !isUsefullToPreserve(Attr.getKindAsEnum())))
198  return;
199  unsigned AttrArg = 0;
200  if (Attr.isIntAttribute())
201  AttrArg = Attr.getValueAsInt();
202  addKnowledge({Attr.getKindAsEnum(), AttrArg, WasOn});
203  }
204 
205  void addCall(const CallBase *Call) {
206  auto addAttrList = [&](AttributeList AttrList) {
207  for (unsigned Idx = AttributeList::FirstArgIndex;
208  Idx < AttrList.getNumAttrSets(); Idx++)
209  for (Attribute Attr : AttrList.getAttributes(Idx)) {
210  bool IsPoisonAttr = Attr.hasAttribute(Attribute::NonNull) ||
211  Attr.hasAttribute(Attribute::Alignment);
212  if (!IsPoisonAttr || Call->isPassingUndefUB(Idx - 1))
213  addAttribute(Attr, Call->getArgOperand(Idx - 1));
214  }
215  for (Attribute Attr : AttrList.getFnAttributes())
216  addAttribute(Attr, nullptr);
217  };
218  addAttrList(Call->getAttributes());
219  if (Function *Fn = Call->getCalledFunction())
220  addAttrList(Fn->getAttributes());
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(
265  {Attribute::Alignment, unsigned(MA.valueOrOne().value()), Pointer});
266  }
267 
268  void addInstruction(Instruction *I) {
269  if (auto *Call = dyn_cast<CallBase>(I))
270  return addCall(Call);
271  if (auto *Load = dyn_cast<LoadInst>(I))
272  return addAccessedPtr(I, Load->getPointerOperand(), Load->getType(),
273  Load->getAlign());
274  if (auto *Store = dyn_cast<StoreInst>(I))
275  return addAccessedPtr(I, Store->getPointerOperand(),
276  Store->getValueOperand()->getType(),
277  Store->getAlign());
278  // TODO: Add support for the other Instructions.
279  // TODO: Maybe we should look around and merge with other llvm.assume.
280  }
281 };
282 
283 } // namespace
284 
287  return nullptr;
288  AssumeBuilderState Builder(I->getModule());
289  Builder.addInstruction(I);
290  return Builder.build();
291 }
292 
294  DominatorTree *DT) {
295  if (!EnableKnowledgeRetention || I->isTerminator())
296  return;
297  AssumeBuilderState Builder(I->getModule(), I, AC, DT);
298  Builder.addInstruction(I);
299  if (auto *Intr = Builder.build()) {
300  Intr->insertBefore(I);
301  if (AC)
303  }
304 }
305 
306 AssumeInst *
308  Instruction *CtxI, AssumptionCache *AC,
309  DominatorTree *DT) {
310  AssumeBuilderState Builder(CtxI->getModule(), CtxI, AC, DT);
311  for (const RetainedKnowledge &RK : Knowledge)
312  Builder.addKnowledge(RK);
313  return Builder.build();
314 }
315 
318  AssumptionCache *AC,
319  DominatorTree *DT) {
320  AssumeBuilderState Builder(Assume->getModule(), Assume, AC, DT);
321  RK = canonicalizedKnowledge(RK, Assume->getModule()->getDataLayout());
322 
323  if (!Builder.isKnowledgeWorthPreserving(RK))
324  return RetainedKnowledge::none();
325 
326  if (Builder.tryToPreserveWithoutAddingAssume(RK))
327  return RetainedKnowledge::none();
328  return RK;
329 }
330 
331 namespace {
332 
333 struct AssumeSimplify {
334  Function &F;
335  AssumptionCache &AC;
336  DominatorTree *DT;
337  LLVMContext &C;
338  SmallDenseSet<IntrinsicInst *> CleanupToDo;
339  StringMapEntry<uint32_t> *IgnoreTag;
341  bool MadeChange = false;
342 
343  AssumeSimplify(Function &F, AssumptionCache &AC, DominatorTree *DT,
344  LLVMContext &C)
345  : F(F), AC(AC), DT(DT), C(C),
346  IgnoreTag(C.getOrInsertBundleTag(IgnoreBundleTag)) {}
347 
348  void buildMapping(bool FilterBooleanArgument) {
349  BBToAssume.clear();
350  for (Value *V : AC.assumptions()) {
351  if (!V)
352  continue;
353  IntrinsicInst *Assume = cast<IntrinsicInst>(V);
354  if (FilterBooleanArgument) {
355  auto *Arg = dyn_cast<ConstantInt>(Assume->getOperand(0));
356  if (!Arg || Arg->isZero())
357  continue;
358  }
359  BBToAssume[Assume->getParent()].push_back(Assume);
360  }
361 
362  for (auto &Elem : BBToAssume) {
363  llvm::sort(Elem.second,
364  [](const IntrinsicInst *LHS, const IntrinsicInst *RHS) {
365  return LHS->comesBefore(RHS);
366  });
367  }
368  }
369 
370  /// Remove all asumes in CleanupToDo if there boolean argument is true and
371  /// ForceCleanup is set or the assume doesn't hold valuable knowledge.
372  void RunCleanup(bool ForceCleanup) {
373  for (IntrinsicInst *Assume : CleanupToDo) {
374  auto *Arg = dyn_cast<ConstantInt>(Assume->getOperand(0));
375  if (!Arg || Arg->isZero() ||
376  (!ForceCleanup &&
377  !isAssumeWithEmptyBundle(cast<AssumeInst>(*Assume))))
378  continue;
379  MadeChange = true;
380  if (ForceCleanup)
381  NumAssumesMerged++;
382  else
383  NumAssumesRemoved++;
384  Assume->eraseFromParent();
385  }
386  CleanupToDo.clear();
387  }
388 
389  /// Remove knowledge stored in assume when it is already know by an attribute
390  /// or an other assume. This can when valid update an existing knowledge in an
391  /// attribute or an other assume.
392  void dropRedundantKnowledge() {
393  struct MapValue {
394  IntrinsicInst *Assume;
395  unsigned ArgValue;
396  CallInst::BundleOpInfo *BOI;
397  };
398  buildMapping(false);
401  Knowledge;
402  for (BasicBlock *BB : depth_first(&F))
403  for (Value *V : BBToAssume[BB]) {
404  if (!V)
405  continue;
406  IntrinsicInst *Assume = cast<IntrinsicInst>(V);
407  for (CallInst::BundleOpInfo &BOI : Assume->bundle_op_infos()) {
408  auto RemoveFromAssume = [&]() {
409  CleanupToDo.insert(Assume);
410  if (BOI.Begin != BOI.End) {
411  Use *U = &Assume->op_begin()[BOI.Begin + ABA_WasOn];
412  U->set(UndefValue::get(U->get()->getType()));
413  }
414  BOI.Tag = IgnoreTag;
415  };
416  if (BOI.Tag == IgnoreTag) {
417  CleanupToDo.insert(Assume);
418  continue;
419  }
420  RetainedKnowledge RK =
421  getKnowledgeFromBundle(cast<AssumeInst>(*Assume), BOI);
422  if (auto *Arg = dyn_cast_or_null<Argument>(RK.WasOn)) {
423  bool HasSameKindAttr = Arg->hasAttribute(RK.AttrKind);
424  if (HasSameKindAttr)
425  if (!Attribute::isIntAttrKind(RK.AttrKind) ||
426  Arg->getAttribute(RK.AttrKind).getValueAsInt() >=
427  RK.ArgValue) {
428  RemoveFromAssume();
429  continue;
430  }
432  Assume, &*F.getEntryBlock().getFirstInsertionPt()) ||
433  Assume == &*F.getEntryBlock().getFirstInsertionPt()) {
434  if (HasSameKindAttr)
435  Arg->removeAttr(RK.AttrKind);
436  Arg->addAttr(Attribute::get(C, RK.AttrKind, RK.ArgValue));
437  MadeChange = true;
438  RemoveFromAssume();
439  continue;
440  }
441  }
442  auto &Lookup = Knowledge[{RK.WasOn, RK.AttrKind}];
443  for (MapValue &Elem : Lookup) {
444  if (!isValidAssumeForContext(Elem.Assume, Assume, DT))
445  continue;
446  if (Elem.ArgValue >= RK.ArgValue) {
447  RemoveFromAssume();
448  continue;
449  } else if (isValidAssumeForContext(Assume, Elem.Assume, DT)) {
450  Elem.Assume->op_begin()[Elem.BOI->Begin + ABA_Argument].set(
451  ConstantInt::get(Type::getInt64Ty(C), RK.ArgValue));
452  MadeChange = true;
453  RemoveFromAssume();
454  continue;
455  }
456  }
457  Lookup.push_back({Assume, RK.ArgValue, &BOI});
458  }
459  }
460  }
461 
462  using MergeIterator = SmallVectorImpl<IntrinsicInst *>::iterator;
463 
464  /// Merge all Assumes from Begin to End in and insert the resulting assume as
465  /// high as possible in the basicblock.
466  void mergeRange(BasicBlock *BB, MergeIterator Begin, MergeIterator End) {
467  if (Begin == End || std::next(Begin) == End)
468  return;
469  /// Provide no additional information so that AssumeBuilderState doesn't
470  /// try to do any punning since it already has been done better.
471  AssumeBuilderState Builder(F.getParent());
472 
473  /// For now it is initialized to the best value it could have
474  Instruction *InsertPt = BB->getFirstNonPHI();
475  if (isa<LandingPadInst>(InsertPt))
476  InsertPt = InsertPt->getNextNode();
477  for (IntrinsicInst *I : make_range(Begin, End)) {
478  CleanupToDo.insert(I);
479  for (CallInst::BundleOpInfo &BOI : I->bundle_op_infos()) {
480  RetainedKnowledge RK =
481  getKnowledgeFromBundle(cast<AssumeInst>(*I), BOI);
482  if (!RK)
483  continue;
484  Builder.addKnowledge(RK);
485  if (auto *I = dyn_cast_or_null<Instruction>(RK.WasOn))
486  if (I->getParent() == InsertPt->getParent() &&
487  (InsertPt->comesBefore(I) || InsertPt == I))
488  InsertPt = I->getNextNode();
489  }
490  }
491 
492  /// Adjust InsertPt if it is before Begin, since mergeAssumes only
493  /// guarantees we can place the resulting assume between Begin and End.
494  if (InsertPt->comesBefore(*Begin))
495  for (auto It = (*Begin)->getIterator(), E = InsertPt->getIterator();
496  It != E; --It)
498  InsertPt = It->getNextNode();
499  break;
500  }
501  auto *MergedAssume = Builder.build();
502  if (!MergedAssume)
503  return;
504  MadeChange = true;
505  MergedAssume->insertBefore(InsertPt);
506  AC.registerAssumption(MergedAssume);
507  }
508 
509  /// Merge assume when they are in the same BasicBlock and for all instruction
510  /// between them isGuaranteedToTransferExecutionToSuccessor returns true.
511  void mergeAssumes() {
512  buildMapping(true);
513 
514  SmallVector<MergeIterator, 4> SplitPoints;
515  for (auto &Elem : BBToAssume) {
516  SmallVectorImpl<IntrinsicInst *> &AssumesInBB = Elem.second;
517  if (AssumesInBB.size() < 2)
518  continue;
519  /// AssumesInBB is already sorted by order in the block.
520 
521  BasicBlock::iterator It = AssumesInBB.front()->getIterator();
522  BasicBlock::iterator E = AssumesInBB.back()->getIterator();
523  SplitPoints.push_back(AssumesInBB.begin());
524  MergeIterator LastSplit = AssumesInBB.begin();
525  for (; It != E; ++It)
527  for (; (*LastSplit)->comesBefore(&*It); ++LastSplit)
528  ;
529  if (SplitPoints.back() != LastSplit)
530  SplitPoints.push_back(LastSplit);
531  }
532  SplitPoints.push_back(AssumesInBB.end());
533  for (auto SplitIt = SplitPoints.begin();
534  SplitIt != std::prev(SplitPoints.end()); SplitIt++) {
535  mergeRange(Elem.first, *SplitIt, *(SplitIt + 1));
536  }
537  SplitPoints.clear();
538  }
539  }
540 };
541 
542 bool simplifyAssumes(Function &F, AssumptionCache *AC, DominatorTree *DT) {
543  AssumeSimplify AS(F, *AC, DT, F.getContext());
544 
545  /// Remove knowledge that is already known by a dominating other assume or an
546  /// attribute.
547  AS.dropRedundantKnowledge();
548 
549  /// Remove assume that are empty.
550  AS.RunCleanup(false);
551 
552  /// Merge assume in the same basicblock when possible.
553  AS.mergeAssumes();
554 
555  /// Remove assume that were merged.
556  AS.RunCleanup(true);
557  return AS.MadeChange;
558 }
559 
560 } // namespace
561 
562 PreservedAnalyses AssumeSimplifyPass::run(Function &F,
565  return PreservedAnalyses::all();
566  simplifyAssumes(F, &AM.getResult<AssumptionAnalysis>(F),
568  return PreservedAnalyses::all();
569 }
570 
571 namespace {
572 class AssumeSimplifyPassLegacyPass : public FunctionPass {
573 public:
574  static char ID;
575 
576  AssumeSimplifyPassLegacyPass() : FunctionPass(ID) {
579  }
580  bool runOnFunction(Function &F) override {
581  if (skipFunction(F) || !EnableKnowledgeRetention)
582  return false;
583  AssumptionCache &AC =
584  getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
586  getAnalysisIfAvailable<DominatorTreeWrapperPass>();
587  return simplifyAssumes(F, &AC, DTWP ? &DTWP->getDomTree() : nullptr);
588  }
589 
590  void getAnalysisUsage(AnalysisUsage &AU) const override {
592 
593  AU.setPreservesAll();
594  }
595 };
596 } // namespace
597 
599 
600 INITIALIZE_PASS_BEGIN(AssumeSimplifyPassLegacyPass, "assume-simplify",
601  "Assume Simplify", false, false)
603 INITIALIZE_PASS_END(AssumeSimplifyPassLegacyPass, "assume-simplify",
604  "Assume Simplify", false, false)
605 
607  return new AssumeSimplifyPassLegacyPass();
608 }
609 
614  for (Instruction &I : instructions(F))
615  salvageKnowledge(&I, AC, DT);
616  return PreservedAnalyses::all();
617 }
618 
619 namespace {
620 class AssumeBuilderPassLegacyPass : public FunctionPass {
621 public:
622  static char ID;
623 
624  AssumeBuilderPassLegacyPass() : FunctionPass(ID) {
626  }
627  bool runOnFunction(Function &F) override {
628  AssumptionCache &AC =
629  getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
631  getAnalysisIfAvailable<DominatorTreeWrapperPass>();
632  for (Instruction &I : instructions(F))
633  salvageKnowledge(&I, &AC, DTWP ? &DTWP->getDomTree() : nullptr);
634  return true;
635  }
636 
637  void getAnalysisUsage(AnalysisUsage &AU) const override {
639 
640  AU.setPreservesAll();
641  }
642 };
643 } // namespace
644 
646 
647 INITIALIZE_PASS_BEGIN(AssumeBuilderPassLegacyPass, "assume-builder",
648  "Assume Builder", false, false)
650 INITIALIZE_PASS_END(AssumeBuilderPassLegacyPass, "assume-builder",
651  "Assume Builder", false, false)
llvm::RetainedKnowledge::WasOn
Value * WasOn
Definition: AssumeBundleQueries.h:104
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:606
AssumptionCache.h
llvm
---------------------— PointerInfo ------------------------------------—
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:112
llvm::ABA_Argument
@ ABA_Argument
Definition: AssumeBundleQueries.h:32
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:1336
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: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
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:61
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:86
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:466
builder
assume builder
Definition: AssumeBundleBuilder.cpp:650
llvm::IgnoreBundleTag
constexpr StringRef IgnoreBundleTag
Tag in operand bundle indicating that this bundle should be ignored.
Definition: AssumeBundleQueries.h:136
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:1297
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:208
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:398
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:316
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:2216
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:521
llvm::initializeAssumeBuilderPassLegacyPassPass
void initializeAssumeBuilderPassLegacyPassPass(PassRegistry &)
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::ABA_WasOn
@ ABA_WasOn
Definition: AssumeBundleQueries.h:31
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
Intr
unsigned Intr
Definition: AMDGPUBaseInfo.cpp:1987
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::RetainedKnowledge::ArgValue
unsigned ArgValue
Definition: AssumeBundleQueries.h:103
llvm::DebugCounter::shouldExecute
static bool shouldExecute(unsigned CounterName)
Definition: DebugCounter.h:74
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:281
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:285
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:899
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:4356
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:610
llvm::lltok::Kind
Kind
Definition: LLToken.h:18
llvm::Value::use_empty
bool use_empty() const
Definition: Value.h:345
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:102
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
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:443
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::CallingConv::Cold
@ Cold
Definition: CallingConv.h:48
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:293
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:651
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:604
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
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:101
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:764
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:204
llvm::ConstantInt::getTrue
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:847
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::Align::value
uint64_t value() const
This is a hole in the type system and should not be abused.
Definition: Alignment.h:85
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:5266
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:788
Function.h
DebugCounter.h
llvm::sort
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1488
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:289
simplify
assume simplify
Definition: AssumeBundleBuilder.cpp:603
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:307
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:414
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
InitializePasses.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
llvm::AttributeList::FirstArgIndex
@ FirstArgIndex
Definition: Attributes.h:403
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:352
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38
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