32 cl::desc(
"enable preservation of all attrbitues. even those that are "
33 "unlikely to be usefull"));
38 "enable preservation of attributes throughout code transformation"));
41#define DEBUG_TYPE "assume-builder"
43STATISTIC(NumAssumeBuilt,
"Number of assume built by the assume builder");
44STATISTIC(NumBundlesInAssumes,
"Total number of Bundles in the assume built");
46 "Number of assume merged by the assume simplify pass");
48 "Number of assume removed by the assume simplify pass");
51 "Controls which assumes gets created");
57 case Attribute::NonNull:
58 case Attribute::NoUndef:
59 case Attribute::Alignment:
60 case Attribute::Dereferenceable:
61 case Attribute::DereferenceableOrNull:
76 case Attribute::NonNull:
79 case Attribute::Alignment: {
81 if (
auto *
GEP = dyn_cast<GEPOperator>(Strip))
88 case Attribute::Dereferenceable:
89 case Attribute::DereferenceableOrNull: {
104struct AssumeBuilderState {
107 using MapKey = std::pair<Value *, Attribute::AttrKind>;
115 :
M(
M), InstBeingModified(
I), AC(AC), DT(DT) {}
118 if (!InstBeingModified || !RK.
WasOn)
120 bool HasBeenPreserved =
false;
121 Use* ToUpdate =
nullptr;
123 RK.
WasOn, {RK.AttrKind}, AC,
126 if (!isValidAssumeForContext(Assume, InstBeingModified, DT))
128 if (RKOther.ArgValue >= RK.ArgValue) {
129 HasBeenPreserved = true;
132 HasBeenPreserved =
true;
142 return HasBeenPreserved;
152 if (isa<AllocaInst>(UnderlyingPtr) || isa<GlobalValue>(UnderlyingPtr))
155 if (
auto *Arg = dyn_cast<Argument>(RK.
WasOn)) {
156 if (Arg->hasAttribute(RK.
AttrKind) &&
162 if (
auto *Inst = dyn_cast<Instruction>(RK.
WasOn))
167 if (SingleUse && SingleUse->getUser() == InstBeingModified)
174 RK = canonicalizedKnowledge(RK,
M->getDataLayout());
176 if (!isKnowledgeWorthPreserving(RK))
179 if (tryToPreserveWithoutAddingAssume(RK))
183 if (
Lookup == AssumedKnowledgeMap.
end()) {
189 "inconsistent argument value");
207 void addCall(
const CallBase *Call) {
208 auto addAttrList = [&](
AttributeList AttrList,
unsigned NumArgs) {
209 for (
unsigned Idx = 0;
Idx < NumArgs;
Idx++)
211 bool IsPoisonAttr = Attr.
hasAttribute(Attribute::NonNull) ||
213 if (!IsPoisonAttr ||
Call->isPassingUndefUB(
Idx))
214 addAttribute(Attr,
Call->getArgOperand(
Idx));
217 addAttribute(Attr,
nullptr);
219 addAttrList(
Call->getAttributes(),
Call->arg_size());
221 addAttrList(Fn->getAttributes(), Fn->arg_size());
225 if (AssumedKnowledgeMap.
empty())
232 for (
auto &MapElem : AssumedKnowledgeMap) {
234 if (MapElem.first.first)
235 Args.push_back(MapElem.first.first);
245 NumBundlesInAssumes++;
254 unsigned DerefSize = MemInst->
getModule()
258 if (DerefSize != 0) {
259 addKnowledge({Attribute::Dereferenceable, DerefSize,
Pointer});
261 Pointer->getType()->getPointerAddressSpace()))
262 addKnowledge({Attribute::NonNull, 0
u,
Pointer});
265 addKnowledge({Attribute::Alignment, MA.
valueOrOne().
value(), Pointer});
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(),
274 if (
auto *Store = dyn_cast<StoreInst>(
I))
275 return addAccessedPtr(
I,
Store->getPointerOperand(),
276 Store->getValueOperand()->getType(),
288 AssumeBuilderState
Builder(
I->getModule());
297 bool Changed =
false;
298 AssumeBuilderState
Builder(
I->getModule(),
I, AC, DT);
301 Intr->insertBefore(
I);
326 if (!
Builder.isKnowledgeWorthPreserving(RK))
329 if (
Builder.tryToPreserveWithoutAddingAssume(RK))
336struct AssumeSimplify {
344 bool MadeChange =
false;
348 :
F(
F), AC(AC), DT(DT), C(C),
351 void buildMapping(
bool FilterBooleanArgument) {
357 if (FilterBooleanArgument) {
358 auto *Arg = dyn_cast<ConstantInt>(Assume->
getOperand(0));
359 if (!Arg || Arg->isZero())
362 BBToAssume[Assume->
getParent()].push_back(Assume);
365 for (
auto &Elem : BBToAssume) {
368 return LHS->comesBefore(RHS);
375 void RunCleanup(
bool ForceCleanup) {
377 auto *Arg = dyn_cast<ConstantInt>(Assume->
getOperand(0));
378 if (!Arg || Arg->isZero() ||
395 void dropRedundantKnowledge() {
406 for (
Value *V : BBToAssume[BB]) {
411 auto RemoveFromAssume = [&]() {
412 CleanupToDo.insert(Assume);
413 if (BOI.Begin != BOI.End) {
419 if (BOI.Tag == IgnoreTag) {
420 CleanupToDo.insert(Assume);
425 if (
auto *Arg = dyn_cast_or_null<Argument>(RK.
WasOn)) {
426 bool HasSameKindAttr = Arg->hasAttribute(RK.
AttrKind);
429 Arg->getAttribute(RK.
AttrKind).getValueAsInt() >=
435 Assume, &*
F.getEntryBlock().getFirstInsertionPt()) ||
436 Assume == &*
F.getEntryBlock().getFirstInsertionPt()) {
453 Elem.Assume->op_begin()[Elem.BOI->Begin +
ABA_Argument].set(
469 void mergeRange(
BasicBlock *BB, MergeIterator Begin, MergeIterator
End) {
470 if (Begin ==
End || std::next(Begin) ==
End)
474 AssumeBuilderState
Builder(
F.getParent());
478 if (isa<LandingPadInst>(InsertPt))
481 CleanupToDo.insert(
I);
488 if (
auto *
I = dyn_cast_or_null<Instruction>(RK.
WasOn))
489 if (
I->getParent() == InsertPt->
getParent() &&
491 InsertPt =
I->getNextNode();
498 for (
auto It = (*Begin)->getIterator(),
E = InsertPt->
getIterator();
504 auto *MergedAssume =
Builder.build();
508 MergedAssume->insertBefore(InsertPt);
514 void mergeAssumes() {
518 for (
auto &Elem : BBToAssume) {
520 if (AssumesInBB.
size() < 2)
527 MergeIterator LastSplit = AssumesInBB.
begin();
528 for (; It !=
E; ++It)
530 for (; (*LastSplit)->comesBefore(&*It); ++LastSplit)
532 if (SplitPoints.
back() != LastSplit)
536 for (
auto SplitIt = SplitPoints.
begin();
537 SplitIt != std::prev(SplitPoints.
end()); SplitIt++) {
538 mergeRange(Elem.first, *SplitIt, *(SplitIt + 1));
546 AssumeSimplify AS(
F, *AC, DT,
F.getContext());
550 AS.dropRedundantKnowledge();
553 AS.RunCleanup(
false);
560 return AS.MadeChange;
581 bool Changed =
false;
592class AssumeBuilderPassLegacyPass :
public FunctionPass {
601 getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
F);
603 getAnalysisIfAvailable<DominatorTreeWrapperPass>();
617char AssumeBuilderPassLegacyPass::ID = 0;
620 "Assume Builder",
false,
false)
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
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)
This file builds on the ADT/GraphTraits.h file to build generic depth first graph iterator.
static bool runOnFunction(Function &F, bool PostInlining)
Select target instructions out of generic instructions
This file implements a map that provides insertion order iteration.
Module.h This file contains the declarations for the Module class.
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
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)
static int Lookup(ArrayRef< TableEntry > Table, unsigned Opcode)
A container for analyses that lazily runs them and caches their results.
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
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),...
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.
bool isIntAttribute() const
Return true if the attribute is an integer attribute.
uint64_t getValueAsInt() const
Return the attribute's value as an integer.
static Attribute get(LLVMContext &Context, AttrKind Kind, uint64_t Val=0)
Return a uniquified Attribute object.
Attribute::AttrKind getKindAsEnum() const
Return the attribute's kind as an enum (Attribute::AttrKind).
static StringRef getNameFromAttrKind(Attribute::AttrKind AttrKind)
AttrKind
This enumeration lists the attributes that can be associated with parameters, function results,...
bool isTypeAttribute() const
Return true if the attribute is a type attribute.
static bool isIntAttrKind(AttrKind Kind)
bool hasAttribute(AttrKind Val) const
Return true if the attribute is present.
LLVM Basic Block Representation.
const Instruction * getFirstNonPHI() const
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
InstListType::iterator iterator
Instruction iterators...
Represents analyses that only rely on functions' control flow.
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
iterator_range< bundle_op_iterator > bundle_op_infos()
Return the range [bundle_op_info_begin, bundle_op_info_end).
static CallInst * Create(FunctionType *Ty, Value *F, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
static ConstantInt * getTrue(LLVMContext &Context)
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.
A parsed version of the target data layout string in and methods for querying it.
TypeSize getTypeStoreSize(Type *Ty) const
Returns the maximum number of bytes that may be overwritten by storing the specified type.
static bool shouldExecute(unsigned CounterName)
Analysis pass which computes a DominatorTree.
Legacy analysis pass which computes a DominatorTree.
DominatorTree & getDomTree()
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
FunctionPass class - This class is used to implement most global optimizations.
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
const BasicBlock * getParent() const
const Function * getFunction() const
Return the function this instruction belongs to.
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.
A wrapper class for inspecting calls to intrinsic functions.
This is an important class for using LLVM in a threaded context.
iterator find(const KeyT &Key)
A Module instance is used to store all the information related to an LLVM module.
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
A container for an operand bundle being viewed as a set of values rather than a set of uses.
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.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
void preserveSet()
Mark an analysis set as preserved.
Implements a dense probed hash-table based set with some number of buckets stored inline.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
typename SuperClass::iterator iterator
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
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.
bool isPointerTy() const
True if this is an instance of PointerType.
static IntegerType * getInt64Ty(LLVMContext &C)
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
A Use represents the edge between a Value definition and its users.
Value * getOperand(unsigned i) const
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
const Value * stripInBoundsOffsets(function_ref< void(const Value *)> Func=[](const Value *) {}) const
Strip off pointer casts and inbounds GEPs.
Use * getSingleUndroppableUse()
Return true if there is exactly one use of this value that cannot be dropped.
constexpr ScalarTy getKnownMinValue() const
Returns the minimum value this quantity can represent.
self_iterator getIterator()
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
@ C
The default llvm calling convention, compatible with C.
Function * getDeclaration(Module *M, ID id, ArrayRef< Type * > Tys=std::nullopt)
Create or insert an LLVM Function declaration for an intrinsic, and return it.
initializer< Ty > init(const Ty &Val)
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.
This is an optimization pass for GlobalISel generic memory operations.
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)
bool NullPointerIsDefined(const Function *F, unsigned AS=0)
Check whether null pointer dereferencing is considered undefined behavior for a given function or an ...
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.
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.
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.
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.
uint32_t Begin
The index in the Use& vector where operands for this operand bundle starts.
This struct is a compact representation of a valid (power of two) or undefined (0) alignment.
Align valueOrOne() const
For convenience, returns a valid alignment or 1 if undefined.
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.