Go to the documentation of this file.
14 #ifndef LLVM_ANALYSIS_VALUETRACKING_H
15 #define LLVM_ANALYSIS_VALUETRACKING_H
32 class AssumptionCache;
36 class WithOverflowInst;
41 class OptimizationRemarkEmitter;
43 class TargetLibraryInfo;
61 bool UseInstrInfo =
true);
77 bool UseInstrInfo =
true);
85 bool UseInstrInfo =
true);
94 bool UseInstrInfo =
true);
106 bool UseInstrInfo =
true);
114 bool OrZero =
false,
unsigned Depth = 0,
118 bool UseInstrInfo =
true);
132 bool UseInstrInfo =
true);
145 bool UseInstrInfo =
true);
153 bool UseInstrInfo =
true);
161 bool UseInstrInfo =
true);
169 bool UseInstrInfo =
true);
184 bool UseInstrInfo =
true);
197 bool UseInstrInfo =
true);
273 bool AllowNonInbounds =
true) {
274 APInt OffsetAPInt(
DL.getIndexTypeSizeInBits(
Ptr->getType()), 0);
276 Ptr->stripAndAccumulateConstantOffsets(
DL, OffsetAPInt, AllowNonInbounds);
284 bool AllowNonInbounds =
true) {
331 bool TrimAtNul =
true);
342 bool MustPreserveNullness);
344 bool MustPreserveNullness) {
346 const_cast<const CallBase *
>(Call), MustPreserveNullness));
356 const CallBase *Call,
bool MustPreserveNullness);
366 const Value *VConst = V;
399 SmallVectorImpl<const Value *> &Objects,
400 LoopInfo *LI =
nullptr,
unsigned MaxLookup = 6);
405 SmallVectorImpl<Value *> &Objects);
411 bool OffsetZero =
false) {
453 const Instruction *CtxI =
nullptr,
454 AssumptionCache *AC =
nullptr,
455 const DominatorTree *DT =
nullptr,
456 const TargetLibraryInfo *TLI =
nullptr);
476 unsigned Opcode,
const Instruction *Inst,
const Instruction *CtxI =
nullptr,
477 AssumptionCache *AC =
nullptr,
const DominatorTree *DT =
nullptr,
478 const TargetLibraryInfo *TLI =
nullptr);
498 const DominatorTree *DT =
nullptr);
512 const DataLayout &
DL,
514 const Instruction *CxtI,
515 const DominatorTree *DT,
516 bool UseInstrInfo =
true);
518 const DataLayout &
DL,
520 const Instruction *CxtI,
521 const DominatorTree *DT,
522 bool UseInstrInfo =
true);
524 const DataLayout &
DL,
526 const Instruction *CxtI,
527 const DominatorTree *DT,
528 bool UseInstrInfo =
true);
530 const DataLayout &
DL,
531 AssumptionCache *AC =
nullptr,
532 const Instruction *CxtI =
nullptr,
533 const DominatorTree *DT =
nullptr);
536 const DataLayout &
DL,
537 AssumptionCache *AC =
nullptr,
538 const Instruction *CxtI =
nullptr,
539 const DominatorTree *DT =
nullptr);
541 const DataLayout &
DL,
543 const Instruction *CxtI,
544 const DominatorTree *DT);
546 const DataLayout &
DL,
548 const Instruction *CxtI,
549 const DominatorTree *DT);
555 const DominatorTree &DT);
560 bool UseInstrInfo =
true,
561 AssumptionCache *AC =
nullptr,
562 const Instruction *CtxI =
nullptr,
563 const DominatorTree *DT =
nullptr,
593 unsigned ScanLimit = 32);
597 iterator_range<BasicBlock::const_iterator> Range,
unsigned ScanLimit = 32);
620 SmallVectorImpl<const Value *> &Ops);
626 SmallVectorImpl<const Value *> &Ops);
632 const SmallSet<const Value *, 16> &KnownPoison);
662 bool ConsiderFlagsAndMetadata =
true);
680 AssumptionCache *AC =
nullptr,
681 const Instruction *CtxI =
nullptr,
682 const DominatorTree *DT =
nullptr,
685 const Instruction *CtxI =
nullptr,
686 const DominatorTree *DT =
nullptr,
784 std::pair<Intrinsic::ID, bool>
829 const DataLayout &
DL,
830 bool LHSIsTrue =
true,
835 const DataLayout &
DL,
836 bool LHSIsTrue =
true,
842 const Instruction *ContextI,
843 const DataLayout &
DL);
846 const Instruction *ContextI,
847 const DataLayout &
DL);
853 const DataLayout &
DL);
856 #endif // LLVM_ANALYSIS_VALUETRACKING_H
bool mustSuppressSpeculation(const LoadInst &LI)
Return true if speculation of the given load must be suppressed to avoid ordering or interfering with...
@ SPF_SMAX
Unsigned minimum.
bool isKnownNegative(const Value *V, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Returns true if the given value is known be negative (i.e.
This is an optimization pass for GlobalISel generic memory operations.
bool haveNoCommonBitsSet(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Return true if LHS and RHS have no common bits set.
bool isKnownNonNegative(const Value *V, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Returns true if the give value is known to be non-negative.
@ NeverOverflows
Never overflows.
bool MaskedValueIsZero(const Value *V, const APInt &Mask, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Return true if 'V & Mask' is known to be zero.
A parsed version of the target data layout string in and methods for querying it.
bool mayHaveNonDefUseDependency(const Instruction &I)
Returns true if the result or effects of the given instructions I depend values not reachable through...
const ConstantDataArray * Array
ConstantDataArray pointer.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
OverflowResult computeOverflowForUnsignedMul(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT, bool UseInstrInfo=true)
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
SelectPatternFlavor Flavor
bool isGuaranteedNotToBeUndefOrPoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Return true if this function can prove that V does not have undef bits and is never poison.
int64_t getSExtValue() const
Get sign extended value.
bool matchSimpleRecurrence(const PHINode *P, BinaryOperator *&BO, Value *&Start, Value *&Step)
Attempt to match a simple first order recurrence cycle of the form: iv = phi Ty [Start,...
SelectPatternNaNBehavior NaNBehavior
uint64_t getElementAsInteger(unsigned i) const
If this is a sequential container of integers (of any size), return the specified element in the low ...
constexpr unsigned MaxAnalysisRecursionDepth
OverflowResult computeOverflowForUnsignedAdd(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT, bool UseInstrInfo=true)
bool SignBitMustBeZero(const Value *V, const TargetLibraryInfo *TLI)
Return true if we can prove that the specified FP value's sign bit is 0.
bool isKnownPositive(const Value *V, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Returns true if the given value is known be positive (i.e.
unsigned ComputeMaxSignificantBits(const Value *Op, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr)
Get the upper bound on bit size for this Value Op as a signed integer.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
uint64_t Offset
Slice starts at this Offset.
bool isKnownNonZero(const Value *V, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Return true if the given value is known to be non-zero when defined.
bool programUndefinedIfPoison(const Instruction *Inst)
@ AlwaysOverflowsLow
Always overflows in the direction of signed/unsigned min value.
Value * isBytewiseValue(Value *V, const DataLayout &DL)
If the specified value can be set by repeating the same byte in memory, return the i8 value that it i...
@ SPF_UMAX
Signed maximum.
unsigned ComputeNumSignBits(const Value *Op, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Return the number of times the sign bit of the register is replicated into the other bits.
uint64_t Length
Length of the slice.
SelectPatternNaNBehavior
Behavior when a floating point min/max is given one NaN and one non-NaN as input.
SelectPatternResult matchSelectPattern(Value *V, Value *&LHS, Value *&RHS, Instruction::CastOps *CastOp=nullptr, unsigned Depth=0)
Pattern match integer [SU]MIN, [SU]MAX and ABS idioms, returning the kind and providing the out param...
SelectPatternFlavor
Specific patterns of select instructions we can match.
APInt getMinMaxLimit(SelectPatternFlavor SPF, unsigned BitWidth)
Return the minimum or maximum constant value for the specified integer min/max flavor and type.
@ SPNB_RETURNS_NAN
NaN behavior not applicable.
void computeKnownBitsFromRangeMetadata(const MDNode &Ranges, KnownBits &Known)
Compute known bits from the range metadata.
bool mustTriggerUB(const Instruction *I, const SmallSet< const Value *, 16 > &KnownPoison)
Return true if the given instruction must trigger undefined behavior when I is executed with any oper...
constexpr std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
@ SPF_NABS
Absolute value.
OverflowResult computeOverflowForSignedSub(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT)
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,...
OverflowResult computeOverflowForSignedAdd(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr)
bool canCreatePoison(const Operator *Op, bool ConsiderFlagsAndMetadata=true)
@ MayOverflow
May or may not overflow.
std::optional< bool > isImpliedByDomCondition(const Value *Cond, const Instruction *ContextI, const DataLayout &DL)
Return the boolean condition value in the context of the given instruction if it is known based on do...
static bool isMinOrMax(SelectPatternFlavor SPF)
When implementing this min/max pattern as fcmp; select, does the fcmp have to be ordered?
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
SelectPatternFlavor getInverseMinMaxFlavor(SelectPatternFlavor SPF)
Return the inverse minimum/maximum flavor of the specified flavor.
const Value * getArgumentAliasingToReturnedPointer(const CallBase *Call, bool MustPreserveNullness)
This function returns call pointer argument that is considered the same by aliasing rules.
bool getConstantStringInfo(const Value *V, StringRef &Str, bool TrimAtNul=true)
This function computes the length of a null-terminated C string pointed to by V.
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 isGEPBasedOnPointerToString(const GEPOperator *GEP, unsigned CharSize=8)
Returns true if the GEP is based on a pointer to a string (array of.
bool impliesPoison(const Value *ValAssumedPoison, const Value *V)
Return true if V is poison given that ValAssumedPoison is already poison.
std::optional< int64_t > isPointerOffset(const Value *Ptr1, const Value *Ptr2, const DataLayout &DL)
If Ptr1 is provably equal to Ptr2 plus a constant offset, return that offset.
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
bool onlyUsedByLifetimeMarkersOrDroppableInsts(const Value *V)
Return true if the only users of this pointer are lifetime markers or droppable instructions.
bool isOnlyUsedInZeroEqualityComparison(const Instruction *CxtI)
void getGuaranteedWellDefinedOps(const Instruction *I, SmallVectorImpl< const Value * > &Ops)
Insert operands of I into Ops such that I will trigger undefined behavior if I is executed and that o...
void getUnderlyingObjects(const Value *V, SmallVectorImpl< const Value * > &Objects, LoopInfo *LI=nullptr, unsigned MaxLookup=6)
This method is similar to getUnderlyingObject except that it can look through phi and select instruct...
SelectPatternResult matchDecomposedSelectPattern(CmpInst *CmpI, Value *TrueVal, Value *FalseVal, Value *&LHS, Value *&RHS, Instruction::CastOps *CastOp=nullptr, unsigned Depth=0)
Determine the pattern that a select with the given compare as its predicate and given values as its t...
bool isGuaranteedToExecuteForEveryIteration(const Instruction *I, const Loop *L)
Return true if this function can prove that the instruction I is executed for every iteration of the ...
bool canCreateUndefOrPoison(const Operator *Op, bool ConsiderFlagsAndMetadata=true)
canCreateUndefOrPoison returns true if Op can create undef or poison from non-undef & non-poison oper...
OverflowResult computeOverflowForUnsignedSub(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT)
An array constant whose element type is a simple 1/2/4/8-byte integer or float/double,...
bool isKnownNonEqual(const Value *V1, const Value *V2, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Return true if the given values are known to be non-equal when defined.
void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, OptimizationRemarkEmitter *ORE=nullptr, bool UseInstrInfo=true)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
@ SPNB_RETURNS_ANY
Given one NaN input, returns the non-NaN.
@ SPF_ABS
Floating point maxnum.
bool isKnownNegation(const Value *X, const Value *Y, bool NeedNSW=false)
Return true if the two given values are negation.
bool getUnderlyingObjectsForCodeGen(const Value *V, SmallVectorImpl< Value * > &Objects)
This is a wrapper around getUnderlyingObjects and adds support for basic ptrtoint+arithmetic+inttoptr...
@ BasicBlock
Various leaf nodes.
Class for arbitrary precision integers.
SmallVector< MachineOperand, 4 > Cond
bool getConstantDataArrayInfo(const Value *V, ConstantDataArraySlice &Slice, unsigned ElementSize, uint64_t Offset=0)
Returns true if the value V is a pointer into a ConstantDataArray.
A cache of @llvm.assume calls within a function.
uint64_t operator[](unsigned I) const
Convenience accessor for elements in the slice.
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
ConstantRange computeConstantRange(const Value *V, bool ForSigned, bool UseInstrInfo=true, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Determine the possible constant range of an integer or vector of integer value.
@ SPF_FMINNUM
Unsigned maximum.
bool isKnownNeverInfinity(const Value *V, const TargetLibraryInfo *TLI, unsigned Depth=0)
Return true if the floating-point scalar value is not an infinity or if the floating-point vector val...
@ SPF_FMAXNUM
Floating point minnum.
bool isKnownNeverNaN(const Value *V, const TargetLibraryInfo *TLI, unsigned Depth=0)
Return true if the floating-point scalar value is not a NaN or if the floating-point vector value has...
bool isAssumeLikeIntrinsic(const Instruction *I)
Return true if it is an intrinsic that cannot be speculated but also cannot trap.
bool onlyUsedByLifetimeMarkers(const Value *V)
Return true if the only users of this pointer are lifetime markers.
uint64_t GetStringLength(const Value *V, unsigned CharSize=8)
If we can compute the length of the string pointed to by the specified pointer, return 'len+1'.
Value * FindInsertedValue(Value *V, ArrayRef< unsigned > idx_range, Instruction *InsertBefore=nullptr)
Given an aggregate and an sequence of indices, see if the scalar value indexed is already around as a...
bool Ordered
Only applicable if Flavor is SPF_FMINNUM or SPF_FMAXNUM.
bool isOverflowIntrinsicNoWrap(const WithOverflowInst *WO, const DominatorTree &DT)
Returns true if the arithmetic part of the WO 's result is used only along the paths control dependen...
bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)
Return true if this function can prove that the instruction I will always transfer execution to one o...
Intrinsic::ID getIntrinsicForCallSite(const CallBase &CB, const TargetLibraryInfo *TLI)
Map a call instruction to an intrinsic ID.
constexpr unsigned BitWidth
Provides information about what library functions are available for the current target.
bool CannotBeOrderedLessThanZero(const Value *V, const TargetLibraryInfo *TLI)
Return true if we can prove that the specified FP value is either NaN or never less than -0....
@ AlwaysOverflowsHigh
Always overflows in the direction of signed/unsigned max value.
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.
Intrinsic::ID getInverseMinMaxIntrinsic(Intrinsic::ID MinMaxID)
OverflowResult computeOverflowForSignedMul(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT, bool UseInstrInfo=true)
bool propagatesPoison(const Use &PoisonOp)
Return true if PoisonOp's user yields poison or raises UB if its operand PoisonOp is poison.
bool CannotBeNegativeZero(const Value *V, const TargetLibraryInfo *TLI, unsigned Depth=0)
Return true if we can prove that the specified FP value is never equal to -0.0.
std::optional< bool > isImpliedCondition(const Value *LHS, const Value *RHS, const DataLayout &DL, bool LHSIsTrue=true, unsigned Depth=0)
Return true if RHS is known to be implied true by LHS.
@ SPF_UMIN
Signed minimum.
CmpInst::Predicate getMinMaxPred(SelectPatternFlavor SPF, bool Ordered=false)
Return the canonical comparison predicate for the specified minimum/maximum flavor.
@ SPNB_RETURNS_OTHER
Given one NaN input, returns the NaN.
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
bool isGuaranteedNotToBePoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
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
Represents offset+length into a ConstantDataArray.
bool isKnownToBeAPowerOfTwo(const Value *V, const DataLayout &DL, bool OrZero=false, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Return true if the given value is known to have exactly one bit set when defined.
void move(uint64_t Delta)
Moves the Offset and adjusts Length accordingly.
an instruction to allocate memory on the stack
void getGuaranteedNonPoisonOps(const Instruction *I, SmallVectorImpl< const Value * > &Ops)
Insert operands of I into Ops such that I will trigger undefined behavior if I is executed and that o...
bool programUndefinedIfUndefOrPoison(const Instruction *Inst)
Return true if this function can prove that if Inst is executed and yields a poison value or undef bi...
std::pair< Intrinsic::ID, bool > canConvertToMinOrMaxIntrinsic(ArrayRef< Value * > VL)
Check if the values in VL are select instructions that can be converted to a min or max (vector) intr...
bool isSafeToSpeculativelyExecute(const Instruction *I, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr)
Return true if the instruction does not have any effects besides calculating the result and does not ...
LLVM Value Representation.
bool isIntrinsicReturningPointerAliasingArgumentWithoutCapturing(const CallBase *Call, bool MustPreserveNullness)
{launder,strip}.invariant.group returns pointer that aliases its argument, and it only captures point...
AllocaInst * findAllocaForValue(Value *V, bool OffsetZero=false)
Returns unique alloca where the value comes from, or nullptr.
InstListType::const_iterator const_iterator
bool isSafeToSpeculativelyExecuteWithOpcode(unsigned Opcode, const Instruction *Inst, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr)
This returns the same result as isSafeToSpeculativelyExecute if Opcode is the actual opcode of Inst.