LLVM 19.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"
25
26using namespace llvm;
27
28namespace 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,
37 "enable preservation of attributes throughout code transformation"));
38} // namespace llvm
39
40#define DEBUG_TYPE "assume-builder"
41
42STATISTIC(NumAssumeBuilt, "Number of assume built by the assume builder");
43STATISTIC(NumBundlesInAssumes, "Total number of Bundles in the assume built");
44STATISTIC(NumAssumesMerged,
45 "Number of assume merged by the assume simplify pass");
46STATISTIC(NumAssumesRemoved,
47 "Number of assume removed by the assume simplify pass");
48
49DEBUG_COUNTER(BuildAssumeCounter, "assume-builder-counter",
50 "Controls which assumes gets created");
51
52namespace {
53
54bool 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.
70RetainedKnowledge 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.
103struct 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));
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)
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 false;
296 bool Changed = false;
297 AssumeBuilderState Builder(I->getModule(), I, AC, DT);
298 Builder.addInstruction(I);
299 if (auto *Intr = Builder.build()) {
300 Intr->insertBefore(I);
301 Changed = true;
302 if (AC)
304 }
305 return Changed;
306}
307
310 Instruction *CtxI, AssumptionCache *AC,
311 DominatorTree *DT) {
312 AssumeBuilderState Builder(CtxI->getModule(), CtxI, AC, DT);
313 for (const RetainedKnowledge &RK : Knowledge)
314 Builder.addKnowledge(RK);
315 return Builder.build();
316}
317
320 AssumptionCache *AC,
321 DominatorTree *DT) {
322 AssumeBuilderState Builder(Assume->getModule(), Assume, AC, DT);
323 RK = canonicalizedKnowledge(RK, Assume->getModule()->getDataLayout());
324
325 if (!Builder.isKnowledgeWorthPreserving(RK))
327
328 if (Builder.tryToPreserveWithoutAddingAssume(RK))
330 return RK;
331}
332
333namespace {
334
335struct AssumeSimplify {
336 Function &F;
337 AssumptionCache &AC;
338 DominatorTree *DT;
339 LLVMContext &C;
341 StringMapEntry<uint32_t> *IgnoreTag;
343 bool MadeChange = false;
344
345 AssumeSimplify(Function &F, AssumptionCache &AC, DominatorTree *DT,
346 LLVMContext &C)
347 : F(F), AC(AC), DT(DT), C(C),
348 IgnoreTag(C.getOrInsertBundleTag(IgnoreBundleTag)) {}
349
350 void buildMapping(bool FilterBooleanArgument) {
351 BBToAssume.clear();
352 for (Value *V : AC.assumptions()) {
353 if (!V)
354 continue;
355 IntrinsicInst *Assume = cast<IntrinsicInst>(V);
356 if (FilterBooleanArgument) {
357 auto *Arg = dyn_cast<ConstantInt>(Assume->getOperand(0));
358 if (!Arg || Arg->isZero())
359 continue;
360 }
361 BBToAssume[Assume->getParent()].push_back(Assume);
362 }
363
364 for (auto &Elem : BBToAssume) {
365 llvm::sort(Elem.second,
366 [](const IntrinsicInst *LHS, const IntrinsicInst *RHS) {
367 return LHS->comesBefore(RHS);
368 });
369 }
370 }
371
372 /// Remove all asumes in CleanupToDo if there boolean argument is true and
373 /// ForceCleanup is set or the assume doesn't hold valuable knowledge.
374 void RunCleanup(bool ForceCleanup) {
375 for (IntrinsicInst *Assume : CleanupToDo) {
376 auto *Arg = dyn_cast<ConstantInt>(Assume->getOperand(0));
377 if (!Arg || Arg->isZero() ||
378 (!ForceCleanup &&
379 !isAssumeWithEmptyBundle(cast<AssumeInst>(*Assume))))
380 continue;
381 MadeChange = true;
382 if (ForceCleanup)
383 NumAssumesMerged++;
384 else
385 NumAssumesRemoved++;
386 Assume->eraseFromParent();
387 }
388 CleanupToDo.clear();
389 }
390
391 /// Remove knowledge stored in assume when it is already know by an attribute
392 /// or an other assume. This can when valid update an existing knowledge in an
393 /// attribute or an other assume.
394 void dropRedundantKnowledge() {
395 struct MapValue {
396 IntrinsicInst *Assume;
397 uint64_t ArgValue;
399 };
400 buildMapping(false);
403 Knowledge;
404 for (BasicBlock *BB : depth_first(&F))
405 for (Value *V : BBToAssume[BB]) {
406 if (!V)
407 continue;
408 IntrinsicInst *Assume = cast<IntrinsicInst>(V);
409 for (CallInst::BundleOpInfo &BOI : Assume->bundle_op_infos()) {
410 auto RemoveFromAssume = [&]() {
411 CleanupToDo.insert(Assume);
412 if (BOI.Begin != BOI.End) {
413 Use *U = &Assume->op_begin()[BOI.Begin + ABA_WasOn];
414 U->set(UndefValue::get(U->get()->getType()));
415 }
416 BOI.Tag = IgnoreTag;
417 };
418 if (BOI.Tag == IgnoreTag) {
419 CleanupToDo.insert(Assume);
420 continue;
421 }
423 getKnowledgeFromBundle(cast<AssumeInst>(*Assume), BOI);
424 if (auto *Arg = dyn_cast_or_null<Argument>(RK.WasOn)) {
425 bool HasSameKindAttr = Arg->hasAttribute(RK.AttrKind);
426 if (HasSameKindAttr)
428 Arg->getAttribute(RK.AttrKind).getValueAsInt() >=
429 RK.ArgValue) {
430 RemoveFromAssume();
431 continue;
432 }
434 Assume, &*F.getEntryBlock().getFirstInsertionPt()) ||
435 Assume == &*F.getEntryBlock().getFirstInsertionPt()) {
436 if (HasSameKindAttr)
437 Arg->removeAttr(RK.AttrKind);
438 Arg->addAttr(Attribute::get(C, RK.AttrKind, RK.ArgValue));
439 MadeChange = true;
440 RemoveFromAssume();
441 continue;
442 }
443 }
444 auto &Lookup = Knowledge[{RK.WasOn, RK.AttrKind}];
445 for (MapValue &Elem : Lookup) {
446 if (!isValidAssumeForContext(Elem.Assume, Assume, DT))
447 continue;
448 if (Elem.ArgValue >= RK.ArgValue) {
449 RemoveFromAssume();
450 continue;
451 } else if (isValidAssumeForContext(Assume, Elem.Assume, DT)) {
452 Elem.Assume->op_begin()[Elem.BOI->Begin + ABA_Argument].set(
453 ConstantInt::get(Type::getInt64Ty(C), RK.ArgValue));
454 MadeChange = true;
455 RemoveFromAssume();
456 continue;
457 }
458 }
459 Lookup.push_back({Assume, RK.ArgValue, &BOI});
460 }
461 }
462 }
463
464 using MergeIterator = SmallVectorImpl<IntrinsicInst *>::iterator;
465
466 /// Merge all Assumes from Begin to End in and insert the resulting assume as
467 /// high as possible in the basicblock.
468 void mergeRange(BasicBlock *BB, MergeIterator Begin, MergeIterator End) {
469 if (Begin == End || std::next(Begin) == End)
470 return;
471 /// Provide no additional information so that AssumeBuilderState doesn't
472 /// try to do any punning since it already has been done better.
473 AssumeBuilderState Builder(F.getParent());
474
475 /// For now it is initialized to the best value it could have
476 Instruction *InsertPt = BB->getFirstNonPHI();
477 if (isa<LandingPadInst>(InsertPt))
478 InsertPt = InsertPt->getNextNode();
479 for (IntrinsicInst *I : make_range(Begin, End)) {
480 CleanupToDo.insert(I);
481 for (CallInst::BundleOpInfo &BOI : I->bundle_op_infos()) {
483 getKnowledgeFromBundle(cast<AssumeInst>(*I), BOI);
484 if (!RK)
485 continue;
486 Builder.addKnowledge(RK);
487 if (auto *I = dyn_cast_or_null<Instruction>(RK.WasOn))
488 if (I->getParent() == InsertPt->getParent() &&
489 (InsertPt->comesBefore(I) || InsertPt == I))
490 InsertPt = I->getNextNode();
491 }
492 }
493
494 /// Adjust InsertPt if it is before Begin, since mergeAssumes only
495 /// guarantees we can place the resulting assume between Begin and End.
496 if (InsertPt->comesBefore(*Begin))
497 for (auto It = (*Begin)->getIterator(), E = InsertPt->getIterator();
498 It != E; --It)
500 InsertPt = It->getNextNode();
501 break;
502 }
503 auto *MergedAssume = Builder.build();
504 if (!MergedAssume)
505 return;
506 MadeChange = true;
507 MergedAssume->insertBefore(InsertPt);
508 AC.registerAssumption(MergedAssume);
509 }
510
511 /// Merge assume when they are in the same BasicBlock and for all instruction
512 /// between them isGuaranteedToTransferExecutionToSuccessor returns true.
513 void mergeAssumes() {
514 buildMapping(true);
515
517 for (auto &Elem : BBToAssume) {
518 SmallVectorImpl<IntrinsicInst *> &AssumesInBB = Elem.second;
519 if (AssumesInBB.size() < 2)
520 continue;
521 /// AssumesInBB is already sorted by order in the block.
522
523 BasicBlock::iterator It = AssumesInBB.front()->getIterator();
524 BasicBlock::iterator E = AssumesInBB.back()->getIterator();
525 SplitPoints.push_back(AssumesInBB.begin());
526 MergeIterator LastSplit = AssumesInBB.begin();
527 for (; It != E; ++It)
529 for (; (*LastSplit)->comesBefore(&*It); ++LastSplit)
530 ;
531 if (SplitPoints.back() != LastSplit)
532 SplitPoints.push_back(LastSplit);
533 }
534 SplitPoints.push_back(AssumesInBB.end());
535 for (auto SplitIt = SplitPoints.begin();
536 SplitIt != std::prev(SplitPoints.end()); SplitIt++) {
537 mergeRange(Elem.first, *SplitIt, *(SplitIt + 1));
538 }
539 SplitPoints.clear();
540 }
541 }
542};
543
544bool simplifyAssumes(Function &F, AssumptionCache *AC, DominatorTree *DT) {
545 AssumeSimplify AS(F, *AC, DT, F.getContext());
546
547 /// Remove knowledge that is already known by a dominating other assume or an
548 /// attribute.
549 AS.dropRedundantKnowledge();
550
551 /// Remove assume that are empty.
552 AS.RunCleanup(false);
553
554 /// Merge assume in the same basicblock when possible.
555 AS.mergeAssumes();
556
557 /// Remove assume that were merged.
558 AS.RunCleanup(true);
559 return AS.MadeChange;
560}
561
562} // namespace
563
567 return PreservedAnalyses::all();
568 if (!simplifyAssumes(F, &AM.getResult<AssumptionAnalysis>(F),
570 return PreservedAnalyses::all();
573 return PA;
574}
575
580 bool Changed = false;
581 for (Instruction &I : instructions(F))
582 Changed |= salvageKnowledge(&I, AC, DT);
583 if (!Changed)
587 return PA;
588}
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
unsigned Intr
Expand Atomic instructions
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:480
Hexagon Common GEP
#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)
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:348
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
Definition: PassManager.h:519
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:500
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.
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:308
bool isIntAttribute() const
Return true if the attribute is an integer attribute.
Definition: Attributes.cpp:304
uint64_t getValueAsInt() const
Return the attribute's value as an integer.
Definition: Attributes.cpp:328
static Attribute get(LLVMContext &Context, AttrKind Kind, uint64_t Val=0)
Return a uniquified Attribute object.
Definition: Attributes.cpp:93
Attribute::AttrKind getKindAsEnum() const
Return the attribute's kind as an enum (Attribute::AttrKind).
Definition: Attributes.cpp:320
static StringRef getNameFromAttrKind(Attribute::AttrKind AttrKind)
Definition: Attributes.cpp:274
AttrKind
This enumeration lists the attributes that can be associated with parameters, function results,...
Definition: Attributes.h:85
bool isTypeAttribute() const
Return true if the attribute is a type attribute.
Definition: Attributes.cpp:312
static bool isIntAttrKind(AttrKind Kind)
Definition: Attributes.h:101
bool hasAttribute(AttrKind Val) const
Return true if the attribute is present.
Definition: Attributes.cpp:369
LLVM Basic Block Representation.
Definition: BasicBlock.h:60
const Instruction * getFirstNonPHI() const
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
Definition: BasicBlock.cpp:347
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:164
Represents analyses that only rely on functions' control flow.
Definition: Analysis.h:70
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1455
iterator_range< bundle_op_iterator > bundle_op_infos()
Return the range [bundle_op_info_begin, bundle_op_info_end).
Definition: InstrTypes.h:2551
static CallInst * Create(FunctionType *Ty, Value *F, const Twine &NameStr, BasicBlock::iterator InsertBefore)
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:849
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
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:162
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
Definition: Instruction.cpp:80
const BasicBlock * getParent() const
Definition: Instruction.h:151
InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
const Function * getFunction() const
Return the function this instruction belongs to.
Definition: Instruction.cpp:84
bool comesBefore(const Instruction *Other) const
Given an instruction Other in the same basic block as this instruction, return true if this instructi...
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:167
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:287
A container for an operand bundle being viewed as a set of values rather than a set of uses.
Definition: InstrTypes.h:1408
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:109
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: Analysis.h:115
void preserveSet()
Mark an analysis set as preserved.
Definition: Analysis.h:144
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:586
typename SuperClass::iterator iterator
Definition: SmallVector.h:590
void push_back(const T &Elt)
Definition: SmallVector.h:426
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
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:1808
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:785
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:168
self_iterator getIterator()
Definition: ilist_node.h:109
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
Definition: ilist_node.h:316
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
Key
PAL metadata keys.
@ 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:1451
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:450
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
cl::opt< bool > EnableKnowledgeRetention
@ Offset
Definition: DWP.cpp:456
bool isValidAssumeForContext(const Instruction *I, const Instruction *CxtI, const DominatorTree *DT=nullptr, bool AllowEphemerals=false)
Return true if it is valid to use the assumptions provided by an assume intrinsic,...
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:1656
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:2014
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:418
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:218
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
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)
AssumeInst * buildAssumeFromInst(Instruction *I)
Build a call to llvm.assume to preserve informations that can be derived from the given instruction.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Used to keep track of an operand bundle.
Definition: InstrTypes.h:2442
uint32_t Begin
The index in the Use& vector where operands for this operand bundle starts.
Definition: InstrTypes.h:2449
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:254