LLVM 18.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"
20#include "llvm/IR/Module.h"
21#include "llvm/IR/Operator.h"
26
27using namespace llvm;
28
29namespace llvm {
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,
38 "enable preservation of attributes throughout code transformation"));
39} // namespace llvm
40
41#define DEBUG_TYPE "assume-builder"
42
43STATISTIC(NumAssumeBuilt, "Number of assume built by the assume builder");
44STATISTIC(NumBundlesInAssumes, "Total number of Bundles in the assume built");
45STATISTIC(NumAssumesMerged,
46 "Number of assume merged by the assume simplify pass");
47STATISTIC(NumAssumesRemoved,
48 "Number of assume removed by the assume simplify pass");
49
50DEBUG_COUNTER(BuildAssumeCounter, "assume-builder-counter",
51 "Controls which assumes gets created");
52
53namespace {
54
55bool isUsefullToPreserve(Attribute::AttrKind Kind) {
56 switch (Kind) {
57 case Attribute::NonNull:
58 case Attribute::NoUndef:
59 case Attribute::Alignment:
60 case Attribute::Dereferenceable:
61 case Attribute::DereferenceableOrNull:
62 case Attribute::Cold:
63 return true;
64 default:
65 return false;
66 }
67}
68
69/// This function will try to transform the given knowledge into a more
70/// canonical one. the canonical knowledge maybe the given one.
71RetainedKnowledge canonicalizedKnowledge(RetainedKnowledge RK,
72 const DataLayout &DL) {
73 switch (RK.AttrKind) {
74 default:
75 return RK;
76 case Attribute::NonNull:
78 return RK;
79 case Attribute::Alignment: {
80 Value *V = RK.WasOn->stripInBoundsOffsets([&](const Value *Strip) {
81 if (auto *GEP = dyn_cast<GEPOperator>(Strip))
82 RK.ArgValue =
83 MinAlign(RK.ArgValue, GEP->getMaxPreservedAlignment(DL).value());
84 });
85 RK.WasOn = V;
86 return RK;
87 }
88 case Attribute::Dereferenceable:
89 case Attribute::DereferenceableOrNull: {
90 int64_t Offset = 0;
92 /*AllowNonInBounds*/ false);
93 if (Offset < 0)
94 return RK;
95 RK.ArgValue = RK.ArgValue + Offset;
96 RK.WasOn = V;
97 }
98 }
99 return RK;
100}
101
102/// This class contain all knowledge that have been gather while building an
103/// llvm.assume and the function to manipulate it.
104struct AssumeBuilderState {
105 Module *M;
106
107 using MapKey = std::pair<Value *, Attribute::AttrKind>;
108 SmallMapVector<MapKey, uint64_t, 8> AssumedKnowledgeMap;
109 Instruction *InstBeingModified = nullptr;
110 AssumptionCache* AC = nullptr;
111 DominatorTree* DT = nullptr;
112
113 AssumeBuilderState(Module *M, Instruction *I = nullptr,
114 AssumptionCache *AC = nullptr, DominatorTree *DT = nullptr)
115 : M(M), InstBeingModified(I), AC(AC), DT(DT) {}
116
117 bool tryToPreserveWithoutAddingAssume(RetainedKnowledge RK) {
118 if (!InstBeingModified || !RK.WasOn)
119 return false;
120 bool HasBeenPreserved = false;
121 Use* ToUpdate = nullptr;
123 RK.WasOn, {RK.AttrKind}, AC,
124 [&](RetainedKnowledge RKOther, Instruction *Assume,
125 const CallInst::BundleOpInfo *Bundle) {
126 if (!isValidAssumeForContext(Assume, InstBeingModified, DT))
127 return false;
128 if (RKOther.ArgValue >= RK.ArgValue) {
129 HasBeenPreserved = true;
130 return true;
131 } else if (isValidAssumeForContext(InstBeingModified, Assume, DT)) {
132 HasBeenPreserved = true;
133 IntrinsicInst *Intr = cast<IntrinsicInst>(Assume);
134 ToUpdate = &Intr->op_begin()[Bundle->Begin + ABA_Argument];
135 return true;
136 }
137 return false;
138 });
139 if (ToUpdate)
140 ToUpdate->set(
141 ConstantInt::get(Type::getInt64Ty(M->getContext()), RK.ArgValue));
142 return HasBeenPreserved;
143 }
144
145 bool isKnowledgeWorthPreserving(RetainedKnowledge RK) {
146 if (!RK)
147 return false;
148 if (!RK.WasOn)
149 return true;
150 if (RK.WasOn->getType()->isPointerTy()) {
151 Value *UnderlyingPtr = getUnderlyingObject(RK.WasOn);
152 if (isa<AllocaInst>(UnderlyingPtr) || isa<GlobalValue>(UnderlyingPtr))
153 return false;
154 }
155 if (auto *Arg = dyn_cast<Argument>(RK.WasOn)) {
156 if (Arg->hasAttribute(RK.AttrKind) &&
158 Arg->getAttribute(RK.AttrKind).getValueAsInt() >= RK.ArgValue))
159 return false;
160 return true;
161 }
162 if (auto *Inst = dyn_cast<Instruction>(RK.WasOn))
164 if (RK.WasOn->use_empty())
165 return false;
166 Use *SingleUse = RK.WasOn->getSingleUndroppableUse();
167 if (SingleUse && SingleUse->getUser() == InstBeingModified)
168 return false;
169 }
170 return true;
171 }
172
173 void addKnowledge(RetainedKnowledge RK) {
174 RK = canonicalizedKnowledge(RK, M->getDataLayout());
175
176 if (!isKnowledgeWorthPreserving(RK))
177 return;
178
179 if (tryToPreserveWithoutAddingAssume(RK))
180 return;
181 MapKey Key{RK.WasOn, RK.AttrKind};
182 auto Lookup = AssumedKnowledgeMap.find(Key);
183 if (Lookup == AssumedKnowledgeMap.end()) {
184 AssumedKnowledgeMap[Key] = RK.ArgValue;
185 return;
186 }
187 assert(((Lookup->second == 0 && RK.ArgValue == 0) ||
188 (Lookup->second != 0 && RK.ArgValue != 0)) &&
189 "inconsistent argument value");
190
191 /// This is only desirable because for all attributes taking an argument
192 /// higher is better.
193 Lookup->second = std::max(Lookup->second, RK.ArgValue);
194 }
195
196 void addAttribute(Attribute Attr, Value *WasOn) {
197 if (Attr.isTypeAttribute() || Attr.isStringAttribute() ||
199 !isUsefullToPreserve(Attr.getKindAsEnum())))
200 return;
201 uint64_t AttrArg = 0;
202 if (Attr.isIntAttribute())
203 AttrArg = Attr.getValueAsInt();
204 addKnowledge({Attr.getKindAsEnum(), AttrArg, WasOn});
205 }
206
207 void addCall(const CallBase *Call) {
208 auto addAttrList = [&](AttributeList AttrList, unsigned NumArgs) {
209 for (unsigned Idx = 0; Idx < NumArgs; Idx++)
210 for (Attribute Attr : AttrList.getParamAttrs(Idx)) {
211 bool IsPoisonAttr = Attr.hasAttribute(Attribute::NonNull) ||
212 Attr.hasAttribute(Attribute::Alignment);
213 if (!IsPoisonAttr || Call->isPassingUndefUB(Idx))
214 addAttribute(Attr, Call->getArgOperand(Idx));
215 }
216 for (Attribute Attr : AttrList.getFnAttrs())
217 addAttribute(Attr, nullptr);
218 };
219 addAttrList(Call->getAttributes(), Call->arg_size());
220 if (Function *Fn = Call->getCalledFunction())
221 addAttrList(Fn->getAttributes(), Fn->arg_size());
222 }
223
224 AssumeInst *build() {
225 if (AssumedKnowledgeMap.empty())
226 return nullptr;
227 if (!DebugCounter::shouldExecute(BuildAssumeCounter))
228 return nullptr;
229 Function *FnAssume = Intrinsic::getDeclaration(M, Intrinsic::assume);
230 LLVMContext &C = M->getContext();
232 for (auto &MapElem : AssumedKnowledgeMap) {
234 if (MapElem.first.first)
235 Args.push_back(MapElem.first.first);
236
237 /// This is only valid because for all attribute that currently exist a
238 /// value of 0 is useless. and should not be preserved.
239 if (MapElem.second)
240 Args.push_back(ConstantInt::get(Type::getInt64Ty(M->getContext()),
241 MapElem.second));
243 std::string(Attribute::getNameFromAttrKind(MapElem.first.second)),
244 Args));
245 NumBundlesInAssumes++;
246 }
247 NumAssumeBuilt++;
248 return cast<AssumeInst>(CallInst::Create(
249 FnAssume, ArrayRef<Value *>({ConstantInt::getTrue(C)}), OpBundle));
250 }
251
252 void addAccessedPtr(Instruction *MemInst, Value *Pointer, Type *AccType,
253 MaybeAlign MA) {
254 unsigned DerefSize = MemInst->getModule()
255 ->getDataLayout()
256 .getTypeStoreSize(AccType)
258 if (DerefSize != 0) {
259 addKnowledge({Attribute::Dereferenceable, DerefSize, Pointer});
260 if (!NullPointerIsDefined(MemInst->getFunction(),
261 Pointer->getType()->getPointerAddressSpace()))
262 addKnowledge({Attribute::NonNull, 0u, Pointer});
263 }
264 if (MA.valueOrOne() > 1)
265 addKnowledge({Attribute::Alignment, 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 false;
297 bool Changed = false;
298 AssumeBuilderState Builder(I->getModule(), I, AC, DT);
299 Builder.addInstruction(I);
300 if (auto *Intr = Builder.build()) {
301 Intr->insertBefore(I);
302 Changed = true;
303 if (AC)
305 }
306 return Changed;
307}
308
311 Instruction *CtxI, AssumptionCache *AC,
312 DominatorTree *DT) {
313 AssumeBuilderState Builder(CtxI->getModule(), CtxI, AC, DT);
314 for (const RetainedKnowledge &RK : Knowledge)
315 Builder.addKnowledge(RK);
316 return Builder.build();
317}
318
321 AssumptionCache *AC,
322 DominatorTree *DT) {
323 AssumeBuilderState Builder(Assume->getModule(), Assume, AC, DT);
324 RK = canonicalizedKnowledge(RK, Assume->getModule()->getDataLayout());
325
326 if (!Builder.isKnowledgeWorthPreserving(RK))
328
329 if (Builder.tryToPreserveWithoutAddingAssume(RK))
331 return RK;
332}
333
334namespace {
335
336struct AssumeSimplify {
337 Function &F;
338 AssumptionCache &AC;
339 DominatorTree *DT;
340 LLVMContext &C;
342 StringMapEntry<uint32_t> *IgnoreTag;
344 bool MadeChange = false;
345
346 AssumeSimplify(Function &F, AssumptionCache &AC, DominatorTree *DT,
347 LLVMContext &C)
348 : F(F), AC(AC), DT(DT), C(C),
349 IgnoreTag(C.getOrInsertBundleTag(IgnoreBundleTag)) {}
350
351 void buildMapping(bool FilterBooleanArgument) {
352 BBToAssume.clear();
353 for (Value *V : AC.assumptions()) {
354 if (!V)
355 continue;
356 IntrinsicInst *Assume = cast<IntrinsicInst>(V);
357 if (FilterBooleanArgument) {
358 auto *Arg = dyn_cast<ConstantInt>(Assume->getOperand(0));
359 if (!Arg || Arg->isZero())
360 continue;
361 }
362 BBToAssume[Assume->getParent()].push_back(Assume);
363 }
364
365 for (auto &Elem : BBToAssume) {
366 llvm::sort(Elem.second,
367 [](const IntrinsicInst *LHS, const IntrinsicInst *RHS) {
368 return LHS->comesBefore(RHS);
369 });
370 }
371 }
372
373 /// Remove all asumes in CleanupToDo if there boolean argument is true and
374 /// ForceCleanup is set or the assume doesn't hold valuable knowledge.
375 void RunCleanup(bool ForceCleanup) {
376 for (IntrinsicInst *Assume : CleanupToDo) {
377 auto *Arg = dyn_cast<ConstantInt>(Assume->getOperand(0));
378 if (!Arg || Arg->isZero() ||
379 (!ForceCleanup &&
380 !isAssumeWithEmptyBundle(cast<AssumeInst>(*Assume))))
381 continue;
382 MadeChange = true;
383 if (ForceCleanup)
384 NumAssumesMerged++;
385 else
386 NumAssumesRemoved++;
387 Assume->eraseFromParent();
388 }
389 CleanupToDo.clear();
390 }
391
392 /// Remove knowledge stored in assume when it is already know by an attribute
393 /// or an other assume. This can when valid update an existing knowledge in an
394 /// attribute or an other assume.
395 void dropRedundantKnowledge() {
396 struct MapValue {
397 IntrinsicInst *Assume;
398 uint64_t ArgValue;
400 };
401 buildMapping(false);
404 Knowledge;
405 for (BasicBlock *BB : depth_first(&F))
406 for (Value *V : BBToAssume[BB]) {
407 if (!V)
408 continue;
409 IntrinsicInst *Assume = cast<IntrinsicInst>(V);
410 for (CallInst::BundleOpInfo &BOI : Assume->bundle_op_infos()) {
411 auto RemoveFromAssume = [&]() {
412 CleanupToDo.insert(Assume);
413 if (BOI.Begin != BOI.End) {
414 Use *U = &Assume->op_begin()[BOI.Begin + ABA_WasOn];
415 U->set(UndefValue::get(U->get()->getType()));
416 }
417 BOI.Tag = IgnoreTag;
418 };
419 if (BOI.Tag == IgnoreTag) {
420 CleanupToDo.insert(Assume);
421 continue;
422 }
424 getKnowledgeFromBundle(cast<AssumeInst>(*Assume), BOI);
425 if (auto *Arg = dyn_cast_or_null<Argument>(RK.WasOn)) {
426 bool HasSameKindAttr = Arg->hasAttribute(RK.AttrKind);
427 if (HasSameKindAttr)
429 Arg->getAttribute(RK.AttrKind).getValueAsInt() >=
430 RK.ArgValue) {
431 RemoveFromAssume();
432 continue;
433 }
435 Assume, &*F.getEntryBlock().getFirstInsertionPt()) ||
436 Assume == &*F.getEntryBlock().getFirstInsertionPt()) {
437 if (HasSameKindAttr)
438 Arg->removeAttr(RK.AttrKind);
439 Arg->addAttr(Attribute::get(C, RK.AttrKind, RK.ArgValue));
440 MadeChange = true;
441 RemoveFromAssume();
442 continue;
443 }
444 }
445 auto &Lookup = Knowledge[{RK.WasOn, RK.AttrKind}];
446 for (MapValue &Elem : Lookup) {
447 if (!isValidAssumeForContext(Elem.Assume, Assume, DT))
448 continue;
449 if (Elem.ArgValue >= RK.ArgValue) {
450 RemoveFromAssume();
451 continue;
452 } else if (isValidAssumeForContext(Assume, Elem.Assume, DT)) {
453 Elem.Assume->op_begin()[Elem.BOI->Begin + ABA_Argument].set(
455 MadeChange = true;
456 RemoveFromAssume();
457 continue;
458 }
459 }
460 Lookup.push_back({Assume, RK.ArgValue, &BOI});
461 }
462 }
463 }
464
465 using MergeIterator = SmallVectorImpl<IntrinsicInst *>::iterator;
466
467 /// Merge all Assumes from Begin to End in and insert the resulting assume as
468 /// high as possible in the basicblock.
469 void mergeRange(BasicBlock *BB, MergeIterator Begin, MergeIterator End) {
470 if (Begin == End || std::next(Begin) == End)
471 return;
472 /// Provide no additional information so that AssumeBuilderState doesn't
473 /// try to do any punning since it already has been done better.
474 AssumeBuilderState Builder(F.getParent());
475
476 /// For now it is initialized to the best value it could have
477 Instruction *InsertPt = BB->getFirstNonPHI();
478 if (isa<LandingPadInst>(InsertPt))
479 InsertPt = InsertPt->getNextNode();
480 for (IntrinsicInst *I : make_range(Begin, End)) {
481 CleanupToDo.insert(I);
482 for (CallInst::BundleOpInfo &BOI : I->bundle_op_infos()) {
484 getKnowledgeFromBundle(cast<AssumeInst>(*I), BOI);
485 if (!RK)
486 continue;
487 Builder.addKnowledge(RK);
488 if (auto *I = dyn_cast_or_null<Instruction>(RK.WasOn))
489 if (I->getParent() == InsertPt->getParent() &&
490 (InsertPt->comesBefore(I) || InsertPt == I))
491 InsertPt = I->getNextNode();
492 }
493 }
494
495 /// Adjust InsertPt if it is before Begin, since mergeAssumes only
496 /// guarantees we can place the resulting assume between Begin and End.
497 if (InsertPt->comesBefore(*Begin))
498 for (auto It = (*Begin)->getIterator(), E = InsertPt->getIterator();
499 It != E; --It)
501 InsertPt = It->getNextNode();
502 break;
503 }
504 auto *MergedAssume = Builder.build();
505 if (!MergedAssume)
506 return;
507 MadeChange = true;
508 MergedAssume->insertBefore(InsertPt);
509 AC.registerAssumption(MergedAssume);
510 }
511
512 /// Merge assume when they are in the same BasicBlock and for all instruction
513 /// between them isGuaranteedToTransferExecutionToSuccessor returns true.
514 void mergeAssumes() {
515 buildMapping(true);
516
518 for (auto &Elem : BBToAssume) {
519 SmallVectorImpl<IntrinsicInst *> &AssumesInBB = Elem.second;
520 if (AssumesInBB.size() < 2)
521 continue;
522 /// AssumesInBB is already sorted by order in the block.
523
524 BasicBlock::iterator It = AssumesInBB.front()->getIterator();
525 BasicBlock::iterator E = AssumesInBB.back()->getIterator();
526 SplitPoints.push_back(AssumesInBB.begin());
527 MergeIterator LastSplit = AssumesInBB.begin();
528 for (; It != E; ++It)
530 for (; (*LastSplit)->comesBefore(&*It); ++LastSplit)
531 ;
532 if (SplitPoints.back() != LastSplit)
533 SplitPoints.push_back(LastSplit);
534 }
535 SplitPoints.push_back(AssumesInBB.end());
536 for (auto SplitIt = SplitPoints.begin();
537 SplitIt != std::prev(SplitPoints.end()); SplitIt++) {
538 mergeRange(Elem.first, *SplitIt, *(SplitIt + 1));
539 }
540 SplitPoints.clear();
541 }
542 }
543};
544
545bool simplifyAssumes(Function &F, AssumptionCache *AC, DominatorTree *DT) {
546 AssumeSimplify AS(F, *AC, DT, F.getContext());
547
548 /// Remove knowledge that is already known by a dominating other assume or an
549 /// attribute.
550 AS.dropRedundantKnowledge();
551
552 /// Remove assume that are empty.
553 AS.RunCleanup(false);
554
555 /// Merge assume in the same basicblock when possible.
556 AS.mergeAssumes();
557
558 /// Remove assume that were merged.
559 AS.RunCleanup(true);
560 return AS.MadeChange;
561}
562
563} // namespace
564
568 return PreservedAnalyses::all();
569 if (!simplifyAssumes(F, &AM.getResult<AssumptionAnalysis>(F),
571 return PreservedAnalyses::all();
574 return PA;
575}
576
581 bool Changed = false;
582 for (Instruction &I : instructions(F))
583 Changed |= salvageKnowledge(&I, AC, DT);
584 if (!Changed)
588 return PA;
589}
590
591namespace {
592class AssumeBuilderPassLegacyPass : public FunctionPass {
593public:
594 static char ID;
595
596 AssumeBuilderPassLegacyPass() : FunctionPass(ID) {
598 }
599 bool runOnFunction(Function &F) override {
600 AssumptionCache &AC =
601 getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
603 getAnalysisIfAvailable<DominatorTreeWrapperPass>();
604 for (Instruction &I : instructions(F))
605 salvageKnowledge(&I, &AC, DTWP ? &DTWP->getDomTree() : nullptr);
606 return true;
607 }
608
609 void getAnalysisUsage(AnalysisUsage &AU) const override {
611
612 AU.setPreservesAll();
613 }
614};
615} // namespace
616
617char AssumeBuilderPassLegacyPass::ID = 0;
618
619INITIALIZE_PASS_BEGIN(AssumeBuilderPassLegacyPass, "assume-builder",
620 "Assume Builder", false, false)
622INITIALIZE_PASS_END(AssumeBuilderPassLegacyPass, "assume-builder",
623 "Assume Builder", false, false)
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
unsigned Intr
assume builder
assume Assume Builder
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
Given that RA is a live value
This file provides an implementation of debug counters.
#define DEBUG_COUNTER(VARNAME, COUNTERNAME, DESC)
Definition: DebugCounter.h:182
This file builds on the ADT/GraphTraits.h file to build generic depth first graph iterator.
bool End
Definition: ELF_riscv.cpp:469
static bool runOnFunction(Function &F, bool PostInlining)
Hexagon Common GEP
Select target instructions out of generic instructions
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
This file implements a map that provides insertion order iteration.
Module.h This file contains the declarations for the Module class.
if(VerifyEach)
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:55
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:59
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:52
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition: Statistic.h:167
static int Lookup(ArrayRef< TableEntry > Table, unsigned Opcode)
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:620
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
Definition: PassManager.h:793
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:774
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
void setPreservesAll()
Set by analyses that do not transform their input at all.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
This represents the llvm.assume intrinsic.
A function analysis which provides an AssumptionCache.
An immutable pass that tracks lazily created AssumptionCache objects.
A cache of @llvm.assume calls within a function.
void registerAssumption(AssumeInst *CI)
Add an @llvm.assume intrinsic to this function's cache.
MutableArrayRef< ResultElem > assumptions()
Access the list of assumption handles currently tracked for this function.
AttributeSet getFnAttrs() const
The function attributes are returned.
AttributeSet getParamAttrs(unsigned ArgNo) const
The attributes for the argument or parameter at the given index are returned.
bool isStringAttribute() const
Return true if the attribute is a string (target-dependent) attribute.
Definition: Attributes.cpp:282
bool isIntAttribute() const
Return true if the attribute is an integer attribute.
Definition: Attributes.cpp:278
uint64_t getValueAsInt() const
Return the attribute's value as an integer.
Definition: Attributes.cpp:297
static Attribute get(LLVMContext &Context, AttrKind Kind, uint64_t Val=0)
Return a uniquified Attribute object.
Definition: Attributes.cpp:92
Attribute::AttrKind getKindAsEnum() const
Return the attribute's kind as an enum (Attribute::AttrKind).
Definition: Attributes.cpp:290
static StringRef getNameFromAttrKind(Attribute::AttrKind AttrKind)
Definition: Attributes.cpp:248
AttrKind
This enumeration lists the attributes that can be associated with parameters, function results,...
Definition: Attributes.h:84
bool isTypeAttribute() const
Return true if the attribute is a type attribute.
Definition: Attributes.cpp:286
static bool isIntAttrKind(AttrKind Kind)
Definition: Attributes.h:100
bool hasAttribute(AttrKind Val) const
Return true if the attribute is present.
Definition: Attributes.cpp:333
LLVM Basic Block Representation.
Definition: BasicBlock.h:56
const Instruction * getFirstNonPHI() const
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
Definition: BasicBlock.cpp:216
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:87
Represents analyses that only rely on functions' control flow.
Definition: PassManager.h:113
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1190
iterator_range< bundle_op_iterator > bundle_op_infos()
Return the range [bundle_op_info_begin, bundle_op_info_end).
Definition: InstrTypes.h:2248
static CallInst * Create(FunctionType *Ty, Value *F, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:833
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:888
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:110
TypeSize getTypeStoreSize(Type *Ty) const
Returns the maximum number of bytes that may be overwritten by storing the specified type.
Definition: DataLayout.h:472
static bool shouldExecute(unsigned CounterName)
Definition: DebugCounter.h:72
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:279
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:314
DominatorTree & getDomTree()
Definition: Dominators.h:322
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:311
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
Definition: Instruction.cpp:71
const BasicBlock * getParent() const
Definition: Instruction.h:90
const Function * getFunction() const
Return the function this instruction belongs to.
Definition: Instruction.cpp:75
bool comesBefore(const Instruction *Other) const
Given an instruction Other in the same basic block as this instruction, return true if this instructi...
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:83
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:47
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:67
iterator end()
Definition: MapVector.h:71
iterator find(const KeyT &Key)
Definition: MapVector.h:146
bool empty() const
Definition: MapVector.h:79
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
Definition: Module.h:254
A container for an operand bundle being viewed as a set of values rather than a set of uses.
Definition: InstrTypes.h:1143
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
void preserveSet()
Mark an analysis set as preserved.
Definition: PassManager.h:188
Implements a dense probed hash-table based set with some number of buckets stored inline.
Definition: DenseSet.h:290
size_t size() const
Definition: SmallVector.h:91
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:577
typename SuperClass::iterator iterator
Definition: SmallVector.h:581
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
StringMapEntry - This is used to represent one value that is inserted into a StringMap.
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
bool isPointerTy() const
True if this is an instance of PointerType.
Definition: Type.h:255
static IntegerType * getInt64Ty(LLVMContext &C)
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1724
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
op_iterator op_begin()
Definition: User.h:234
Value * getOperand(unsigned i) const
Definition: User.h:169
LLVM Value Representation.
Definition: Value.h:74
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
const Value * stripInBoundsOffsets(function_ref< void(const Value *)> Func=[](const Value *) {}) const
Strip off pointer casts and inbounds GEPs.
Definition: Value.cpp:780
Use * getSingleUndroppableUse()
Return true if there is exactly one use of this value that cannot be dropped.
Definition: Value.cpp:167
bool use_empty() const
Definition: Value.h:344
constexpr ScalarTy getKnownMinValue() const
Returns the minimum value this quantity can represent.
Definition: TypeSize.h:163
self_iterator getIterator()
Definition: ilist_node.h:82
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
Definition: ilist_node.h:289
void clear()
Definition: ilist.h:246
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
Key
PAL metadata keys.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
Function * getDeclaration(Module *M, ID id, ArrayRef< Type * > Tys=std::nullopt)
Create or insert an LLVM Function declaration for an intrinsic, and return it.
Definition: Function.cpp:1422
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:445
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:372
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
@ Offset
Definition: DWP.cpp:440
RetainedKnowledge simplifyRetainedKnowledge(AssumeInst *Assume, RetainedKnowledge RK, AssumptionCache *AC, DominatorTree *DT)
canonicalize the RetainedKnowledge RK.
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
constexpr StringRef IgnoreBundleTag
Tag in operand bundle indicating that this bundle should be ignored.
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"))
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.
const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=6)
This method strips off any GEP address adjustments and pointer casts from the specified value,...
bool isAssumeWithEmptyBundle(const AssumeInst &Assume)
Return true iff the operand bundles of the provided llvm.assume doesn't contain any valuable informat...
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...
RetainedKnowledge getKnowledgeFromBundle(AssumeInst &Assume, const CallBase::BundleOpInfo &BOI)
This extracts the Knowledge from an element of an operand bundle.
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1652
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:1985
bool wouldInstructionBeTriviallyDead(const 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:417
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...
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:211
bool salvageKnowledge(Instruction *I, AssumptionCache *AC=nullptr, DominatorTree *DT=nullptr)
Calls BuildAssumeFromInst and if the resulting llvm.assume is valid insert if before I.
constexpr uint64_t MinAlign(uint64_t A, uint64_t B)
A and B are either alignments or offsets.
Definition: MathExtras.h:338
void initializeAssumeBuilderPassLegacyPassPass(PassRegistry &)
bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)
Return true if this function can prove that the instruction I will always transfer execution to one o...
iterator_range< df_iterator< T > > depth_first(const T &G)
cl::opt< bool > EnableKnowledgeRetention
enable preservation of attributes in assume like: call void @llvm.assume(i1 true) [ "nonnull"(i32* PT...
AssumeInst * buildAssumeFromInst(Instruction *I)
Build a call to llvm.assume to preserve informations that can be derived from the given instruction.
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,...
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Used to keep track of an operand bundle.
Definition: InstrTypes.h:2139
uint32_t Begin
The index in the Use& vector where operands for this operand bundle starts.
Definition: InstrTypes.h:2146
This struct is a compact representation of a valid (power of two) or undefined (0) alignment.
Definition: Alignment.h:117
Align valueOrOne() const
For convenience, returns a valid alignment or 1 if undefined.
Definition: Alignment.h:141
Represent one information held inside an operand bundle of an llvm.assume.
Attribute::AttrKind AttrKind
static RetainedKnowledge none()
A MapVector that performs no allocations if smaller than a certain size.
Definition: MapVector.h:233