1 //===- llvm/Analysis/ValueTracking.h - Walk computations --------*- C++ -*-===//
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
7 //===----------------------------------------------------------------------===//
9 // This file contains routines that help analyze properties that chains of
12 //===----------------------------------------------------------------------===//
14 #ifndef LLVM_ANALYSIS_VALUETRACKING_H
15 #define LLVM_ANALYSIS_VALUETRACKING_H
17 #include "llvm/ADT/ArrayRef.h"
18 #include "llvm/ADT/Optional.h"
19 #include "llvm/ADT/SmallSet.h"
20 #include "llvm/IR/Constants.h"
21 #include "llvm/IR/DataLayout.h"
22 #include "llvm/IR/InstrTypes.h"
23 #include "llvm/IR/Intrinsics.h"
24 #include "llvm/IR/Operator.h"
33 class AssumptionCache;
38 class WithOverflowInst;
43 class OptimizationRemarkEmitter;
45 class TargetLibraryInfo;
48 constexpr unsigned MaxAnalysisRecursionDepth = 6;
50 /// Determine which bits of V are known to be either zero or one and return
51 /// them in the KnownZero/KnownOne bit sets.
53 /// This function is defined on values with integer type, values with pointer
54 /// type, and vectors of integers. In the case
55 /// where V is a vector, the known zero and known one values are the
56 /// same width as the vector element, and the bit is set only if it is true
57 /// for all of the elements in the vector.
58 void computeKnownBits(const Value *V, KnownBits &Known,
59 const DataLayout &DL, unsigned Depth = 0,
60 AssumptionCache *AC = nullptr,
61 const Instruction *CxtI = nullptr,
62 const DominatorTree *DT = nullptr,
63 OptimizationRemarkEmitter *ORE = nullptr,
64 bool UseInstrInfo = true);
66 /// Determine which bits of V are known to be either zero or one and return
67 /// them in the KnownZero/KnownOne bit sets.
69 /// This function is defined on values with integer type, values with pointer
70 /// type, and vectors of integers. In the case
71 /// where V is a vector, the known zero and known one values are the
72 /// same width as the vector element, and the bit is set only if it is true
73 /// for all of the demanded elements in the vector.
74 void computeKnownBits(const Value *V, const APInt &DemandedElts,
75 KnownBits &Known, const DataLayout &DL,
76 unsigned Depth = 0, AssumptionCache *AC = nullptr,
77 const Instruction *CxtI = nullptr,
78 const DominatorTree *DT = nullptr,
79 OptimizationRemarkEmitter *ORE = nullptr,
80 bool UseInstrInfo = true);
82 /// Returns the known bits rather than passing by reference.
83 KnownBits computeKnownBits(const Value *V, const DataLayout &DL,
84 unsigned Depth = 0, AssumptionCache *AC = nullptr,
85 const Instruction *CxtI = nullptr,
86 const DominatorTree *DT = nullptr,
87 OptimizationRemarkEmitter *ORE = nullptr,
88 bool UseInstrInfo = true);
90 /// Returns the known bits rather than passing by reference.
91 KnownBits computeKnownBits(const Value *V, const APInt &DemandedElts,
92 const DataLayout &DL, unsigned Depth = 0,
93 AssumptionCache *AC = nullptr,
94 const Instruction *CxtI = nullptr,
95 const DominatorTree *DT = nullptr,
96 OptimizationRemarkEmitter *ORE = nullptr,
97 bool UseInstrInfo = true);
99 /// Compute known bits from the range metadata.
100 /// \p KnownZero the set of bits that are known to be zero
101 /// \p KnownOne the set of bits that are known to be one
102 void computeKnownBitsFromRangeMetadata(const MDNode &Ranges,
105 /// Return true if LHS and RHS have no common bits set.
106 bool haveNoCommonBitsSet(const Value *LHS, const Value *RHS,
107 const DataLayout &DL,
108 AssumptionCache *AC = nullptr,
109 const Instruction *CxtI = nullptr,
110 const DominatorTree *DT = nullptr,
111 bool UseInstrInfo = true);
113 /// Return true if the given value is known to have exactly one bit set when
114 /// defined. For vectors return true if every element is known to be a power
115 /// of two when defined. Supports values with integer or pointer type and
116 /// vectors of integers. If 'OrZero' is set, then return true if the given
117 /// value is either a power of two or zero.
118 bool isKnownToBeAPowerOfTwo(const Value *V, const DataLayout &DL,
119 bool OrZero = false, unsigned Depth = 0,
120 AssumptionCache *AC = nullptr,
121 const Instruction *CxtI = nullptr,
122 const DominatorTree *DT = nullptr,
123 bool UseInstrInfo = true);
125 bool isOnlyUsedInZeroEqualityComparison(const Instruction *CxtI);
127 /// Return true if the given value is known to be non-zero when defined. For
128 /// vectors, return true if every element is known to be non-zero when
129 /// defined. For pointers, if the context instruction and dominator tree are
130 /// specified, perform context-sensitive analysis and return true if the
131 /// pointer couldn't possibly be null at the specified instruction.
132 /// Supports values with integer or pointer type and vectors of integers.
133 bool isKnownNonZero(const Value *V, const DataLayout &DL, unsigned Depth = 0,
134 AssumptionCache *AC = nullptr,
135 const Instruction *CxtI = nullptr,
136 const DominatorTree *DT = nullptr,
137 bool UseInstrInfo = true);
139 /// Return true if the two given values are negation.
140 /// Currently can recoginze Value pair:
141 /// 1: <X, Y> if X = sub (0, Y) or Y = sub (0, X)
142 /// 2: <X, Y> if X = sub (A, B) and Y = sub (B, A)
143 bool isKnownNegation(const Value *X, const Value *Y, bool NeedNSW = false);
145 /// Returns true if the give value is known to be non-negative.
146 bool isKnownNonNegative(const Value *V, const DataLayout &DL,
148 AssumptionCache *AC = nullptr,
149 const Instruction *CxtI = nullptr,
150 const DominatorTree *DT = nullptr,
151 bool UseInstrInfo = true);
153 /// Returns true if the given value is known be positive (i.e. non-negative
155 bool isKnownPositive(const Value *V, const DataLayout &DL, unsigned Depth = 0,
156 AssumptionCache *AC = nullptr,
157 const Instruction *CxtI = nullptr,
158 const DominatorTree *DT = nullptr,
159 bool UseInstrInfo = true);
161 /// Returns true if the given value is known be negative (i.e. non-positive
163 bool isKnownNegative(const Value *V, const DataLayout &DL, unsigned Depth = 0,
164 AssumptionCache *AC = nullptr,
165 const Instruction *CxtI = nullptr,
166 const DominatorTree *DT = nullptr,
167 bool UseInstrInfo = true);
169 /// Return true if the given values are known to be non-equal when defined.
170 /// Supports scalar integer types only.
171 bool isKnownNonEqual(const Value *V1, const Value *V2, const DataLayout &DL,
172 AssumptionCache *AC = nullptr,
173 const Instruction *CxtI = nullptr,
174 const DominatorTree *DT = nullptr,
175 bool UseInstrInfo = true);
177 /// Return true if 'V & Mask' is known to be zero. We use this predicate to
178 /// simplify operations downstream. Mask is known to be zero for bits that V
181 /// This function is defined on values with integer type, values with pointer
182 /// type, and vectors of integers. In the case
183 /// where V is a vector, the mask, known zero, and known one values are the
184 /// same width as the vector element, and the bit is set only if it is true
185 /// for all of the elements in the vector.
186 bool MaskedValueIsZero(const Value *V, const APInt &Mask,
187 const DataLayout &DL,
188 unsigned Depth = 0, AssumptionCache *AC = nullptr,
189 const Instruction *CxtI = nullptr,
190 const DominatorTree *DT = nullptr,
191 bool UseInstrInfo = true);
193 /// Return the number of times the sign bit of the register is replicated into
194 /// the other bits. We know that at least 1 bit is always equal to the sign
195 /// bit (itself), but other cases can give us information. For example,
196 /// immediately after an "ashr X, 2", we know that the top 3 bits are all
197 /// equal to each other, so we return 3. For vectors, return the number of
198 /// sign bits for the vector element with the mininum number of known sign
200 unsigned ComputeNumSignBits(const Value *Op, const DataLayout &DL,
201 unsigned Depth = 0, AssumptionCache *AC = nullptr,
202 const Instruction *CxtI = nullptr,
203 const DominatorTree *DT = nullptr,
204 bool UseInstrInfo = true);
206 /// Get the minimum bit size for this Value \p Op as a signed integer.
207 /// i.e. x == sext(trunc(x to MinSignedBits) to bitwidth(x)).
208 /// Similar to the APInt::getMinSignedBits function.
209 unsigned ComputeMinSignedBits(const Value *Op, const DataLayout &DL,
211 AssumptionCache *AC = nullptr,
212 const Instruction *CxtI = nullptr,
213 const DominatorTree *DT = nullptr);
215 /// This function computes the integer multiple of Base that equals V. If
216 /// successful, it returns true and returns the multiple in Multiple. If
217 /// unsuccessful, it returns false. Also, if V can be simplified to an
218 /// integer, then the simplified V is returned in Val. Look through sext only
219 /// if LookThroughSExt=true.
220 bool ComputeMultiple(Value *V, unsigned Base, Value *&Multiple,
221 bool LookThroughSExt = false,
224 /// Map a call instruction to an intrinsic ID. Libcalls which have equivalent
225 /// intrinsics are treated as-if they were intrinsics.
226 Intrinsic::ID getIntrinsicForCallSite(const CallBase &CB,
227 const TargetLibraryInfo *TLI);
229 /// Return true if we can prove that the specified FP value is never equal to
231 bool CannotBeNegativeZero(const Value *V, const TargetLibraryInfo *TLI,
234 /// Return true if we can prove that the specified FP value is either NaN or
235 /// never less than -0.0.
242 bool CannotBeOrderedLessThanZero(const Value *V, const TargetLibraryInfo *TLI);
244 /// Return true if the floating-point scalar value is not an infinity or if
245 /// the floating-point vector value has no infinities. Return false if a value
246 /// could ever be infinity.
247 bool isKnownNeverInfinity(const Value *V, const TargetLibraryInfo *TLI,
250 /// Return true if the floating-point scalar value is not a NaN or if the
251 /// floating-point vector value has no NaN elements. Return false if a value
252 /// could ever be NaN.
253 bool isKnownNeverNaN(const Value *V, const TargetLibraryInfo *TLI,
256 /// Return true if we can prove that the specified FP value's sign bit is 0.
258 /// NaN --> true/false (depending on the NaN's sign bit)
263 bool SignBitMustBeZero(const Value *V, const TargetLibraryInfo *TLI);
265 /// If the specified value can be set by repeating the same byte in memory,
266 /// return the i8 value that it is represented with. This is true for all i8
267 /// values obviously, but is also true for i32 0, i32 -1, i16 0xF0F0, double
268 /// 0.0 etc. If the value can't be handled with a repeated byte store (e.g.
269 /// i16 0x1234), return null. If the value is entirely undef and padding,
271 Value *isBytewiseValue(Value *V, const DataLayout &DL);
273 /// Given an aggregate and an sequence of indices, see if the scalar value
274 /// indexed is already around as a register, for example if it were inserted
275 /// directly into the aggregate.
277 /// If InsertBefore is not null, this function will duplicate (modified)
278 /// insertvalues when a part of a nested struct is extracted.
279 Value *FindInsertedValue(Value *V,
280 ArrayRef<unsigned> idx_range,
281 Instruction *InsertBefore = nullptr);
283 /// Analyze the specified pointer to see if it can be expressed as a base
284 /// pointer plus a constant offset. Return the base and offset to the caller.
286 /// This is a wrapper around Value::stripAndAccumulateConstantOffsets that
287 /// creates and later unpacks the required APInt.
288 inline Value *GetPointerBaseWithConstantOffset(Value *Ptr, int64_t &Offset,
289 const DataLayout &DL,
290 bool AllowNonInbounds = true) {
291 APInt OffsetAPInt(DL.getIndexTypeSizeInBits(Ptr->getType()), 0);
293 Ptr->stripAndAccumulateConstantOffsets(DL, OffsetAPInt, AllowNonInbounds);
295 Offset = OffsetAPInt.getSExtValue();
299 GetPointerBaseWithConstantOffset(const Value *Ptr, int64_t &Offset,
300 const DataLayout &DL,
301 bool AllowNonInbounds = true) {
302 return GetPointerBaseWithConstantOffset(const_cast<Value *>(Ptr), Offset, DL,
306 /// Returns true if the GEP is based on a pointer to a string (array of
307 // \p CharSize integers) and is indexing into this string.
308 bool isGEPBasedOnPointerToString(const GEPOperator *GEP,
309 unsigned CharSize = 8);
311 /// Represents offset+length into a ConstantDataArray.
312 struct ConstantDataArraySlice {
313 /// ConstantDataArray pointer. nullptr indicates a zeroinitializer (a valid
314 /// initializer, it just doesn't fit the ConstantDataArray interface).
315 const ConstantDataArray *Array;
317 /// Slice starts at this Offset.
320 /// Length of the slice.
323 /// Moves the Offset and adjusts Length accordingly.
324 void move(uint64_t Delta) {
325 assert(Delta < Length);
330 /// Convenience accessor for elements in the slice.
331 uint64_t operator[](unsigned I) const {
332 return Array==nullptr ? 0 : Array->getElementAsInteger(I + Offset);
336 /// Returns true if the value \p V is a pointer into a ConstantDataArray.
337 /// If successful \p Slice will point to a ConstantDataArray info object
338 /// with an appropriate offset.
339 bool getConstantDataArrayInfo(const Value *V, ConstantDataArraySlice &Slice,
340 unsigned ElementSize, uint64_t Offset = 0);
342 /// This function computes the length of a null-terminated C string pointed to
343 /// by V. If successful, it returns true and returns the string in Str. If
344 /// unsuccessful, it returns false. This does not include the trailing null
345 /// character by default. If TrimAtNul is set to false, then this returns any
346 /// trailing null characters as well as any other characters that come after
348 bool getConstantStringInfo(const Value *V, StringRef &Str,
349 uint64_t Offset = 0, bool TrimAtNul = true);
351 /// If we can compute the length of the string pointed to by the specified
352 /// pointer, return 'len+1'. If we can't, return 0.
353 uint64_t GetStringLength(const Value *V, unsigned CharSize = 8);
355 /// This function returns call pointer argument that is considered the same by
356 /// aliasing rules. You CAN'T use it to replace one value with another. If
357 /// \p MustPreserveNullness is true, the call must preserve the nullness of
359 const Value *getArgumentAliasingToReturnedPointer(const CallBase *Call,
360 bool MustPreserveNullness);
362 getArgumentAliasingToReturnedPointer(CallBase *Call,
363 bool MustPreserveNullness) {
364 return const_cast<Value *>(getArgumentAliasingToReturnedPointer(
365 const_cast<const CallBase *>(Call), MustPreserveNullness));
368 /// {launder,strip}.invariant.group returns pointer that aliases its argument,
369 /// and it only captures pointer by returning it.
370 /// These intrinsics are not marked as nocapture, because returning is
371 /// considered as capture. The arguments are not marked as returned neither,
372 /// because it would make it useless. If \p MustPreserveNullness is true,
373 /// the intrinsic must preserve the nullness of the pointer.
374 bool isIntrinsicReturningPointerAliasingArgumentWithoutCapturing(
375 const CallBase *Call, bool MustPreserveNullness);
377 /// This method strips off any GEP address adjustments and pointer casts from
378 /// the specified value, returning the original object being addressed. Note
379 /// that the returned value has pointer type if the specified value does. If
380 /// the MaxLookup value is non-zero, it limits the number of instructions to
382 const Value *getUnderlyingObject(const Value *V, unsigned MaxLookup = 6);
383 inline Value *getUnderlyingObject(Value *V, unsigned MaxLookup = 6) {
384 // Force const to avoid infinite recursion.
385 const Value *VConst = V;
386 return const_cast<Value *>(getUnderlyingObject(VConst, MaxLookup));
389 /// This method is similar to getUnderlyingObject except that it can
390 /// look through phi and select instructions and return multiple objects.
392 /// If LoopInfo is passed, loop phis are further analyzed. If a pointer
393 /// accesses different objects in each iteration, we don't look through the
394 /// phi node. E.g. consider this loop nest:
399 /// A[i][j] = A[i-1][j] * B[j]
402 /// This is transformed by Load-PRE to stash away A[i] for the next iteration
403 /// of the outer loop:
405 /// Curr = A[0]; // Prev_0
407 /// Prev = Curr; // Prev = PHI (Prev_0, Curr)
410 /// Curr[j] = Prev[j] * B[j]
414 /// Since A[i] and A[i-1] are independent pointers, getUnderlyingObjects
415 /// should not assume that Curr and Prev share the same underlying object thus
416 /// it shouldn't look through the phi above.
417 void getUnderlyingObjects(const Value *V,
418 SmallVectorImpl<const Value *> &Objects,
419 LoopInfo *LI = nullptr, unsigned MaxLookup = 6);
421 /// This is a wrapper around getUnderlyingObjects and adds support for basic
422 /// ptrtoint+arithmetic+inttoptr sequences.
423 bool getUnderlyingObjectsForCodeGen(const Value *V,
424 SmallVectorImpl<Value *> &Objects);
426 /// Returns unique alloca where the value comes from, or nullptr.
427 /// If OffsetZero is true check that V points to the begining of the alloca.
428 AllocaInst *findAllocaForValue(Value *V, bool OffsetZero = false);
429 inline const AllocaInst *findAllocaForValue(const Value *V,
430 bool OffsetZero = false) {
431 return findAllocaForValue(const_cast<Value *>(V), OffsetZero);
434 /// Return true if the only users of this pointer are lifetime markers.
435 bool onlyUsedByLifetimeMarkers(const Value *V);
437 /// Return true if the only users of this pointer are lifetime markers or
438 /// droppable instructions.
439 bool onlyUsedByLifetimeMarkersOrDroppableInsts(const Value *V);
441 /// Return true if speculation of the given load must be suppressed to avoid
442 /// ordering or interfering with an active sanitizer. If not suppressed,
443 /// dereferenceability and alignment must be proven separately. Note: This
444 /// is only needed for raw reasoning; if you use the interface below
445 /// (isSafeToSpeculativelyExecute), this is handled internally.
446 bool mustSuppressSpeculation(const LoadInst &LI);
448 /// Return true if the instruction does not have any effects besides
449 /// calculating the result and does not have undefined behavior.
451 /// This method never returns true for an instruction that returns true for
452 /// mayHaveSideEffects; however, this method also does some other checks in
453 /// addition. It checks for undefined behavior, like dividing by zero or
454 /// loading from an invalid pointer (but not for undefined results, like a
455 /// shift with a shift amount larger than the width of the result). It checks
456 /// for malloc and alloca because speculatively executing them might cause a
457 /// memory leak. It also returns false for instructions related to control
458 /// flow, specifically terminators and PHI nodes.
460 /// If the CtxI is specified this method performs context-sensitive analysis
461 /// and returns true if it is safe to execute the instruction immediately
464 /// If the CtxI is NOT specified this method only looks at the instruction
465 /// itself and its operands, so if this method returns true, it is safe to
466 /// move the instruction as long as the correct dominance relationships for
467 /// the operands and users hold.
469 /// This method can return true for instructions that read memory;
470 /// for such instructions, moving them may change the resulting value.
471 bool isSafeToSpeculativelyExecute(const Value *V,
472 const Instruction *CtxI = nullptr,
473 const DominatorTree *DT = nullptr,
474 const TargetLibraryInfo *TLI = nullptr);
476 /// Returns true if the result or effects of the given instructions \p I
477 /// depend on or influence global memory.
478 /// Memory dependence arises for example if the instruction reads from
479 /// memory or may produce effects or undefined behaviour. Memory dependent
480 /// instructions generally cannot be reorderd with respect to other memory
481 /// dependent instructions or moved into non-dominated basic blocks.
482 /// Instructions which just compute a value based on the values of their
483 /// operands are not memory dependent.
484 bool mayBeMemoryDependent(const Instruction &I);
486 /// Return true if it is an intrinsic that cannot be speculated but also
488 bool isAssumeLikeIntrinsic(const Instruction *I);
490 /// Return true if it is valid to use the assumptions provided by an
491 /// assume intrinsic, I, at the point in the control-flow identified by the
492 /// context instruction, CxtI.
493 bool isValidAssumeForContext(const Instruction *I, const Instruction *CxtI,
494 const DominatorTree *DT = nullptr);
496 enum class OverflowResult {
497 /// Always overflows in the direction of signed/unsigned min value.
499 /// Always overflows in the direction of signed/unsigned max value.
501 /// May or may not overflow.
507 OverflowResult computeOverflowForUnsignedMul(const Value *LHS,
509 const DataLayout &DL,
511 const Instruction *CxtI,
512 const DominatorTree *DT,
513 bool UseInstrInfo = true);
514 OverflowResult computeOverflowForSignedMul(const Value *LHS, const Value *RHS,
515 const DataLayout &DL,
517 const Instruction *CxtI,
518 const DominatorTree *DT,
519 bool UseInstrInfo = true);
520 OverflowResult computeOverflowForUnsignedAdd(const Value *LHS,
522 const DataLayout &DL,
524 const Instruction *CxtI,
525 const DominatorTree *DT,
526 bool UseInstrInfo = true);
527 OverflowResult computeOverflowForSignedAdd(const Value *LHS, const Value *RHS,
528 const DataLayout &DL,
529 AssumptionCache *AC = nullptr,
530 const Instruction *CxtI = nullptr,
531 const DominatorTree *DT = nullptr);
532 /// This version also leverages the sign bit of Add if known.
533 OverflowResult computeOverflowForSignedAdd(const AddOperator *Add,
534 const DataLayout &DL,
535 AssumptionCache *AC = nullptr,
536 const Instruction *CxtI = nullptr,
537 const DominatorTree *DT = nullptr);
538 OverflowResult computeOverflowForUnsignedSub(const Value *LHS, const Value *RHS,
539 const DataLayout &DL,
541 const Instruction *CxtI,
542 const DominatorTree *DT);
543 OverflowResult computeOverflowForSignedSub(const Value *LHS, const Value *RHS,
544 const DataLayout &DL,
546 const Instruction *CxtI,
547 const DominatorTree *DT);
549 /// Returns true if the arithmetic part of the \p WO 's result is
550 /// used only along the paths control dependent on the computation
551 /// not overflowing, \p WO being an <op>.with.overflow intrinsic.
552 bool isOverflowIntrinsicNoWrap(const WithOverflowInst *WO,
553 const DominatorTree &DT);
556 /// Determine the possible constant range of an integer or vector of integer
557 /// value. This is intended as a cheap, non-recursive check.
558 ConstantRange computeConstantRange(const Value *V, bool UseInstrInfo = true,
559 AssumptionCache *AC = nullptr,
560 const Instruction *CtxI = nullptr,
561 const DominatorTree *DT = nullptr,
564 /// Return true if this function can prove that the instruction I will
565 /// always transfer execution to one of its successors (including the next
566 /// instruction that follows within a basic block). E.g. this is not
567 /// guaranteed for function calls that could loop infinitely.
569 /// In other words, this function returns false for instructions that may
570 /// transfer execution or fail to transfer execution in a way that is not
571 /// captured in the CFG nor in the sequence of instructions within a basic
574 /// Undefined behavior is assumed not to happen, so e.g. division is
575 /// guaranteed to transfer execution to the following instruction even
576 /// though division by zero might cause undefined behavior.
577 bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I);
579 /// Returns true if this block does not contain a potential implicit exit.
580 /// This is equivelent to saying that all instructions within the basic block
581 /// are guaranteed to transfer execution to their successor within the basic
582 /// block. This has the same assumptions w.r.t. undefined behavior as the
583 /// instruction variant of this function.
584 bool isGuaranteedToTransferExecutionToSuccessor(const BasicBlock *BB);
586 /// Return true if every instruction in the range (Begin, End) is
587 /// guaranteed to transfer execution to its static successor. \p ScanLimit
588 /// bounds the search to avoid scanning huge blocks.
589 bool isGuaranteedToTransferExecutionToSuccessor(
590 BasicBlock::const_iterator Begin, BasicBlock::const_iterator End,
591 unsigned ScanLimit = 32);
593 /// Same as previous, but with range expressed via iterator_range.
594 bool isGuaranteedToTransferExecutionToSuccessor(
595 iterator_range<BasicBlock::const_iterator> Range,
596 unsigned ScanLimit = 32);
598 /// Return true if this function can prove that the instruction I
599 /// is executed for every iteration of the loop L.
601 /// Note that this currently only considers the loop header.
602 bool isGuaranteedToExecuteForEveryIteration(const Instruction *I,
605 /// Return true if I yields poison or raises UB if any of its operands is
607 /// Formally, given I = `r = op v1 v2 .. vN`, propagatesPoison returns true
608 /// if, for all i, r is evaluated to poison or op raises UB if vi = poison.
609 /// If vi is a vector or an aggregate and r is a single value, any poison
610 /// element in vi should make r poison or raise UB.
611 /// To filter out operands that raise UB on poison, you can use
612 /// getGuaranteedNonPoisonOp.
613 bool propagatesPoison(const Operator *I);
615 /// Insert operands of I into Ops such that I will trigger undefined behavior
616 /// if I is executed and that operand has a poison value.
617 void getGuaranteedNonPoisonOps(const Instruction *I,
618 SmallPtrSetImpl<const Value *> &Ops);
619 /// Insert operands of I into Ops such that I will trigger undefined behavior
620 /// if I is executed and that operand is not a well-defined value
621 /// (i.e. has undef bits or poison).
622 void getGuaranteedWellDefinedOps(const Instruction *I,
623 SmallPtrSetImpl<const Value *> &Ops);
625 /// Return true if the given instruction must trigger undefined behavior
626 /// when I is executed with any operands which appear in KnownPoison holding
627 /// a poison value at the point of execution.
628 bool mustTriggerUB(const Instruction *I,
629 const SmallSet<const Value *, 16>& KnownPoison);
631 /// Return true if this function can prove that if Inst is executed
632 /// and yields a poison value or undef bits, then that will trigger
633 /// undefined behavior.
635 /// Note that this currently only considers the basic block that is
636 /// the parent of Inst.
637 bool programUndefinedIfUndefOrPoison(const Instruction *Inst);
638 bool programUndefinedIfPoison(const Instruction *Inst);
640 /// canCreateUndefOrPoison returns true if Op can create undef or poison from
641 /// non-undef & non-poison operands.
642 /// For vectors, canCreateUndefOrPoison returns true if there is potential
643 /// poison or undef in any element of the result when vectors without
644 /// undef/poison poison are given as operands.
645 /// For example, given `Op = shl <2 x i32> %x, <0, 32>`, this function returns
646 /// true. If Op raises immediate UB but never creates poison or undef
647 /// (e.g. sdiv I, 0), canCreatePoison returns false.
649 /// \p ConsiderFlags controls whether poison producing flags on the
650 /// instruction are considered. This can be used to see if the instruction
651 /// could still introduce undef or poison even without poison generating flags
652 /// which might be on the instruction. (i.e. could the result of
653 /// Op->dropPoisonGeneratingFlags() still create poison or undef)
655 /// canCreatePoison returns true if Op can create poison from non-poison
657 bool canCreateUndefOrPoison(const Operator *Op, bool ConsiderFlags = true);
658 bool canCreatePoison(const Operator *Op, bool ConsiderFlags = true);
660 /// Return true if V is poison given that ValAssumedPoison is already poison.
661 /// For example, if ValAssumedPoison is `icmp X, 10` and V is `icmp X, 5`,
662 /// impliesPoison returns true.
663 bool impliesPoison(const Value *ValAssumedPoison, const Value *V);
665 /// Return true if this function can prove that V does not have undef bits
666 /// and is never poison. If V is an aggregate value or vector, check whether
667 /// all elements (except padding) are not undef or poison.
668 /// Note that this is different from canCreateUndefOrPoison because the
669 /// function assumes Op's operands are not poison/undef.
671 /// If CtxI and DT are specified this method performs flow-sensitive analysis
672 /// and returns true if it is guaranteed to be never undef or poison
673 /// immediately before the CtxI.
674 bool isGuaranteedNotToBeUndefOrPoison(const Value *V,
675 AssumptionCache *AC = nullptr,
676 const Instruction *CtxI = nullptr,
677 const DominatorTree *DT = nullptr,
679 bool isGuaranteedNotToBePoison(const Value *V, AssumptionCache *AC = nullptr,
680 const Instruction *CtxI = nullptr,
681 const DominatorTree *DT = nullptr,
684 /// Specific patterns of select instructions we can match.
685 enum SelectPatternFlavor {
687 SPF_SMIN, /// Signed minimum
688 SPF_UMIN, /// Unsigned minimum
689 SPF_SMAX, /// Signed maximum
690 SPF_UMAX, /// Unsigned maximum
691 SPF_FMINNUM, /// Floating point minnum
692 SPF_FMAXNUM, /// Floating point maxnum
693 SPF_ABS, /// Absolute value
694 SPF_NABS /// Negated absolute value
697 /// Behavior when a floating point min/max is given one NaN and one
698 /// non-NaN as input.
699 enum SelectPatternNaNBehavior {
700 SPNB_NA = 0, /// NaN behavior not applicable.
701 SPNB_RETURNS_NAN, /// Given one NaN input, returns the NaN.
702 SPNB_RETURNS_OTHER, /// Given one NaN input, returns the non-NaN.
703 SPNB_RETURNS_ANY /// Given one NaN input, can return either (or
704 /// it has been determined that no operands can
708 struct SelectPatternResult {
709 SelectPatternFlavor Flavor;
710 SelectPatternNaNBehavior NaNBehavior; /// Only applicable if Flavor is
711 /// SPF_FMINNUM or SPF_FMAXNUM.
712 bool Ordered; /// When implementing this min/max pattern as
713 /// fcmp; select, does the fcmp have to be
716 /// Return true if \p SPF is a min or a max pattern.
717 static bool isMinOrMax(SelectPatternFlavor SPF) {
718 return SPF != SPF_UNKNOWN && SPF != SPF_ABS && SPF != SPF_NABS;
722 /// Pattern match integer [SU]MIN, [SU]MAX and ABS idioms, returning the kind
723 /// and providing the out parameter results if we successfully match.
725 /// For ABS/NABS, LHS will be set to the input to the abs idiom. RHS will be
726 /// the negation instruction from the idiom.
728 /// If CastOp is not nullptr, also match MIN/MAX idioms where the type does
729 /// not match that of the original select. If this is the case, the cast
730 /// operation (one of Trunc,SExt,Zext) that must be done to transform the
731 /// type of LHS and RHS into the type of V is returned in CastOp.
734 /// %1 = icmp slt i32 %a, i32 4
735 /// %2 = sext i32 %a to i64
736 /// %3 = select i1 %1, i64 %2, i64 4
738 /// -> LHS = %a, RHS = i32 4, *CastOp = Instruction::SExt
740 SelectPatternResult matchSelectPattern(Value *V, Value *&LHS, Value *&RHS,
741 Instruction::CastOps *CastOp = nullptr,
744 inline SelectPatternResult
745 matchSelectPattern(const Value *V, const Value *&LHS, const Value *&RHS) {
746 Value *L = const_cast<Value *>(LHS);
747 Value *R = const_cast<Value *>(RHS);
748 auto Result = matchSelectPattern(const_cast<Value *>(V), L, R);
754 /// Determine the pattern that a select with the given compare as its
755 /// predicate and given values as its true/false operands would match.
756 SelectPatternResult matchDecomposedSelectPattern(
757 CmpInst *CmpI, Value *TrueVal, Value *FalseVal, Value *&LHS, Value *&RHS,
758 Instruction::CastOps *CastOp = nullptr, unsigned Depth = 0);
760 /// Return the canonical comparison predicate for the specified
761 /// minimum/maximum flavor.
762 CmpInst::Predicate getMinMaxPred(SelectPatternFlavor SPF,
763 bool Ordered = false);
765 /// Return the inverse minimum/maximum flavor of the specified flavor.
766 /// For example, signed minimum is the inverse of signed maximum.
767 SelectPatternFlavor getInverseMinMaxFlavor(SelectPatternFlavor SPF);
769 Intrinsic::ID getInverseMinMaxIntrinsic(Intrinsic::ID MinMaxID);
771 /// Return the canonical inverse comparison predicate for the specified
772 /// minimum/maximum flavor.
773 CmpInst::Predicate getInverseMinMaxPred(SelectPatternFlavor SPF);
775 /// Return the minimum or maximum constant value for the specified integer
776 /// min/max flavor and type.
777 APInt getMinMaxLimit(SelectPatternFlavor SPF, unsigned BitWidth);
779 /// Check if the values in \p VL are select instructions that can be converted
780 /// to a min or max (vector) intrinsic. Returns the intrinsic ID, if such a
781 /// conversion is possible, together with a bool indicating whether all select
782 /// conditions are only used by the selects. Otherwise return
783 /// Intrinsic::not_intrinsic.
784 std::pair<Intrinsic::ID, bool>
785 canConvertToMinOrMaxIntrinsic(ArrayRef<Value *> VL);
787 /// Attempt to match a simple first order recurrence cycle of the form:
788 /// %iv = phi Ty [%Start, %Entry], [%Inc, %backedge]
789 /// %inc = binop %iv, %step
791 /// %iv = phi Ty [%Start, %Entry], [%Inc, %backedge]
792 /// %inc = binop %step, %iv
794 /// A first order recurrence is a formula with the form: X_n = f(X_(n-1))
796 /// A couple of notes on subtleties in that definition:
797 /// * The Step does not have to be loop invariant. In math terms, it can
798 /// be a free variable. We allow recurrences with both constant and
799 /// variable coefficients. Callers may wish to filter cases where Step
800 /// does not dominate P.
801 /// * For non-commutative operators, we will match both forms. This
802 /// results in some odd recurrence structures. Callers may wish to filter
803 /// out recurrences where the phi is not the LHS of the returned operator.
804 /// * Because of the structure matched, the caller can assume as a post
805 /// condition of the match the presence of a Loop with P's parent as it's
806 /// header *except* in unreachable code. (Dominance decays in unreachable
809 /// NOTE: This is intentional simple. If you want the ability to analyze
810 /// non-trivial loop conditons, see ScalarEvolution instead.
811 bool matchSimpleRecurrence(const PHINode *P, BinaryOperator *&BO,
812 Value *&Start, Value *&Step);
814 /// Analogous to the above, but starting from the binary operator
815 bool matchSimpleRecurrence(const BinaryOperator *I, PHINode *&P,
816 Value *&Start, Value *&Step);
818 /// Return true if RHS is known to be implied true by LHS. Return false if
819 /// RHS is known to be implied false by LHS. Otherwise, return None if no
820 /// implication can be made.
821 /// A & B must be i1 (boolean) values or a vector of such values. Note that
822 /// the truth table for implication is the same as <=u on i1 values (but not
823 /// <=s!). The truth table for both is:
828 Optional<bool> isImpliedCondition(const Value *LHS, const Value *RHS,
829 const DataLayout &DL, bool LHSIsTrue = true,
831 Optional<bool> isImpliedCondition(const Value *LHS,
832 CmpInst::Predicate RHSPred,
833 const Value *RHSOp0, const Value *RHSOp1,
834 const DataLayout &DL, bool LHSIsTrue = true,
837 /// Return the boolean condition value in the context of the given instruction
838 /// if it is known based on dominating conditions.
839 Optional<bool> isImpliedByDomCondition(const Value *Cond,
840 const Instruction *ContextI,
841 const DataLayout &DL);
842 Optional<bool> isImpliedByDomCondition(CmpInst::Predicate Pred,
843 const Value *LHS, const Value *RHS,
844 const Instruction *ContextI,
845 const DataLayout &DL);
847 /// If Ptr1 is provably equal to Ptr2 plus a constant offset, return that
848 /// offset. For example, Ptr1 might be &A[42], and Ptr2 might be &A[40]. In
849 /// this case offset would be -8.
850 Optional<int64_t> isPointerOffset(const Value *Ptr1, const Value *Ptr2,
851 const DataLayout &DL);
852 } // end namespace llvm
854 #endif // LLVM_ANALYSIS_VALUETRACKING_H