LLVM 17.0.0git
ValueTracking.h
Go to the documentation of this file.
1//===- llvm/Analysis/ValueTracking.h - Walk computations --------*- 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//
9// This file contains routines that help analyze properties that chains of
10// computations have.
11//
12//===----------------------------------------------------------------------===//
13
14#ifndef LLVM_ANALYSIS_VALUETRACKING_H
15#define LLVM_ANALYSIS_VALUETRACKING_H
16
17#include "llvm/ADT/ArrayRef.h"
18#include "llvm/ADT/SmallSet.h"
19#include "llvm/IR/Constants.h"
20#include "llvm/IR/DataLayout.h"
21#include "llvm/IR/InstrTypes.h"
22#include "llvm/IR/Intrinsics.h"
23#include <cassert>
24#include <cstdint>
25
26namespace llvm {
27
28class Operator;
29class AddOperator;
30class AllocaInst;
31class APInt;
32class AssumptionCache;
33class DominatorTree;
34class GEPOperator;
35class LoadInst;
36class WithOverflowInst;
37struct KnownBits;
38class Loop;
39class LoopInfo;
40class MDNode;
41struct SimplifyQuery;
42class StringRef;
43class TargetLibraryInfo;
44class Value;
45
46constexpr unsigned MaxAnalysisRecursionDepth = 6;
47
48/// Determine which bits of V are known to be either zero or one and return
49/// them in the KnownZero/KnownOne bit sets.
50///
51/// This function is defined on values with integer type, values with pointer
52/// type, and vectors of integers. In the case
53/// where V is a vector, the known zero and known one values are the
54/// same width as the vector element, and the bit is set only if it is true
55/// for all of the elements in the vector.
56void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL,
57 unsigned Depth = 0, AssumptionCache *AC = nullptr,
58 const Instruction *CxtI = nullptr,
59 const DominatorTree *DT = nullptr,
60 bool UseInstrInfo = true);
61
62/// Determine which bits of V are known to be either zero or one and return
63/// them in the KnownZero/KnownOne bit sets.
64///
65/// This function is defined on values with integer type, values with pointer
66/// type, and vectors of integers. In the case
67/// where V is a vector, the known zero and known one values are the
68/// same width as the vector element, and the bit is set only if it is true
69/// for all of the demanded elements in the vector.
70void computeKnownBits(const Value *V, const APInt &DemandedElts,
71 KnownBits &Known, const DataLayout &DL,
72 unsigned Depth = 0, AssumptionCache *AC = nullptr,
73 const Instruction *CxtI = nullptr,
74 const DominatorTree *DT = nullptr,
75 bool UseInstrInfo = true);
76
77/// Returns the known bits rather than passing by reference.
79 unsigned Depth = 0, AssumptionCache *AC = nullptr,
80 const Instruction *CxtI = nullptr,
81 const DominatorTree *DT = nullptr,
82 bool UseInstrInfo = true);
83
84/// Returns the known bits rather than passing by reference.
85KnownBits computeKnownBits(const Value *V, const APInt &DemandedElts,
86 const DataLayout &DL, unsigned Depth = 0,
87 AssumptionCache *AC = nullptr,
88 const Instruction *CxtI = nullptr,
89 const DominatorTree *DT = nullptr,
90 bool UseInstrInfo = true);
91
92/// Compute known bits from the range metadata.
93/// \p KnownZero the set of bits that are known to be zero
94/// \p KnownOne the set of bits that are known to be one
95void computeKnownBitsFromRangeMetadata(const MDNode &Ranges, KnownBits &Known);
96
97/// Merge bits known from assumes into Known.
98void computeKnownBitsFromAssume(const Value *V, KnownBits &Known,
99 unsigned Depth, const SimplifyQuery &Q);
100
101/// Using KnownBits LHS/RHS produce the known bits for logic op (and/xor/or).
103 const Operator *I, const KnownBits &KnownLHS, const KnownBits &KnownRHS,
104 unsigned Depth, const DataLayout &DL, AssumptionCache *AC = nullptr,
105 const Instruction *CxtI = nullptr, const DominatorTree *DT = nullptr,
106 bool UseInstrInfo = true);
107
108/// Return true if LHS and RHS have no common bits set.
109bool haveNoCommonBitsSet(const Value *LHS, const Value *RHS,
110 const DataLayout &DL, AssumptionCache *AC = nullptr,
111 const Instruction *CxtI = nullptr,
112 const DominatorTree *DT = nullptr,
113 bool UseInstrInfo = true);
114
115/// Return true if the given value is known to have exactly one bit set when
116/// defined. For vectors return true if every element is known to be a power
117/// of two when defined. Supports values with integer or pointer type and
118/// vectors of integers. If 'OrZero' is set, then return true if the given
119/// value is either a power of two or zero.
120bool isKnownToBeAPowerOfTwo(const Value *V, const DataLayout &DL,
121 bool OrZero = false, unsigned Depth = 0,
122 AssumptionCache *AC = nullptr,
123 const Instruction *CxtI = nullptr,
124 const DominatorTree *DT = nullptr,
125 bool UseInstrInfo = true);
126
128
129/// Return true if the given value is known to be non-zero when defined. For
130/// vectors, return true if every element is known to be non-zero when
131/// defined. For pointers, if the context instruction and dominator tree are
132/// specified, perform context-sensitive analysis and return true if the
133/// pointer couldn't possibly be null at the specified instruction.
134/// Supports values with integer or pointer type and vectors of integers.
135bool isKnownNonZero(const Value *V, const DataLayout &DL, unsigned Depth = 0,
136 AssumptionCache *AC = nullptr,
137 const Instruction *CxtI = nullptr,
138 const DominatorTree *DT = nullptr,
139 bool UseInstrInfo = true);
140
141/// Return true if the two given values are negation.
142/// Currently can recoginze Value pair:
143/// 1: <X, Y> if X = sub (0, Y) or Y = sub (0, X)
144/// 2: <X, Y> if X = sub (A, B) and Y = sub (B, A)
145bool isKnownNegation(const Value *X, const Value *Y, bool NeedNSW = false);
146
147/// Returns true if the give value is known to be non-negative.
148bool isKnownNonNegative(const Value *V, const DataLayout &DL,
149 unsigned Depth = 0, AssumptionCache *AC = nullptr,
150 const Instruction *CxtI = nullptr,
151 const DominatorTree *DT = nullptr,
152 bool UseInstrInfo = true);
153
154/// Returns true if the given value is known be positive (i.e. non-negative
155/// and non-zero).
156bool isKnownPositive(const Value *V, const DataLayout &DL, unsigned Depth = 0,
157 AssumptionCache *AC = nullptr,
158 const Instruction *CxtI = nullptr,
159 const DominatorTree *DT = nullptr,
160 bool UseInstrInfo = true);
161
162/// Returns true if the given value is known be negative (i.e. non-positive
163/// and non-zero).
164bool isKnownNegative(const Value *V, const DataLayout &DL, unsigned Depth = 0,
165 AssumptionCache *AC = nullptr,
166 const Instruction *CxtI = nullptr,
167 const DominatorTree *DT = nullptr,
168 bool UseInstrInfo = true);
169
170/// Return true if the given values are known to be non-equal when defined.
171/// Supports scalar integer types only.
172bool isKnownNonEqual(const Value *V1, const Value *V2, const DataLayout &DL,
173 AssumptionCache *AC = nullptr,
174 const Instruction *CxtI = nullptr,
175 const DominatorTree *DT = nullptr,
176 bool UseInstrInfo = true);
177
178/// Return true if 'V & Mask' is known to be zero. We use this predicate to
179/// simplify operations downstream. Mask is known to be zero for bits that V
180/// cannot have.
181///
182/// This function is defined on values with integer type, values with pointer
183/// type, and vectors of integers. In the case
184/// where V is a vector, the mask, known zero, and known one values are the
185/// same width as the vector element, and the bit is set only if it is true
186/// for all of the elements in the vector.
187bool MaskedValueIsZero(const Value *V, const APInt &Mask, const DataLayout &DL,
188 unsigned Depth = 0, AssumptionCache *AC = nullptr,
189 const Instruction *CxtI = nullptr,
190 const DominatorTree *DT = nullptr,
191 bool UseInstrInfo = true);
192
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
199/// bits.
200unsigned 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);
205
206/// Get the upper bound on bit size for this Value \p Op as a signed integer.
207/// i.e. x == sext(trunc(x to MaxSignificantBits) to bitwidth(x)).
208/// Similar to the APInt::getSignificantBits function.
209unsigned ComputeMaxSignificantBits(const Value *Op, const DataLayout &DL,
210 unsigned Depth = 0,
211 AssumptionCache *AC = nullptr,
212 const Instruction *CxtI = nullptr,
213 const DominatorTree *DT = nullptr);
214
215/// Map a call instruction to an intrinsic ID. Libcalls which have equivalent
216/// intrinsics are treated as-if they were intrinsics.
218 const TargetLibraryInfo *TLI);
219
220/// Returns a pair of values, which if passed to llvm.is.fpclass, returns the
221/// same result as an fcmp with the given operands.
222///
223/// If \p LookThroughSrc is true, consider the input value when computing the
224/// mask.
225///
226/// If \p LookThroughSrc is false, ignore the source value (i.e. the first pair
227/// element will always be LHS.
228std::pair<Value *, FPClassTest> fcmpToClassTest(CmpInst::Predicate Pred,
229 const Function &F, Value *LHS,
230 Value *RHS,
231 bool LookThroughSrc = true);
232
234 /// Floating-point classes the value could be one of.
236
237 /// std::nullopt if the sign bit is unknown, true if the sign bit is
238 /// definitely set or false if the sign bit is definitely unset.
239 std::optional<bool> SignBit;
240
241 /// Return true if it's known this can never be one of the mask entries.
242 bool isKnownNever(FPClassTest Mask) const {
243 return (KnownFPClasses & Mask) == fcNone;
244 }
245
246 bool isUnknown() const {
247 return KnownFPClasses == fcAllFlags && !SignBit;
248 }
249
250 /// Return true if it's known this can never be a nan.
251 bool isKnownNeverNaN() const {
252 return isKnownNever(fcNan);
253 }
254
255 /// Return true if it's known this can never be an infinity.
256 bool isKnownNeverInfinity() const {
257 return isKnownNever(fcInf);
258 }
259
260 /// Return true if it's known this can never be +infinity.
262 return isKnownNever(fcPosInf);
263 }
264
265 /// Return true if it's known this can never be -infinity.
267 return isKnownNever(fcNegInf);
268 }
269
270 /// Return true if it's known this can never be a subnormal
273 }
274
275 /// Return true if it's known this can never be a positive subnormal
278 }
279
280 /// Return true if it's known this can never be a negative subnormal
283 }
284
285 /// Return true if it's known this can never be a zero. This means a literal
286 /// [+-]0, and does not include denormal inputs implicitly treated as [+-]0.
287 bool isKnownNeverZero() const {
288 return isKnownNever(fcZero);
289 }
290
291 /// Return true if it's known this can never be a literal positive zero.
292 bool isKnownNeverPosZero() const {
293 return isKnownNever(fcPosZero);
294 }
295
296 /// Return true if it's known this can never be a literal negative zero.
297 bool isKnownNeverNegZero() const {
298 return isKnownNever(fcNegZero);
299 }
300
301 /// Return true if it's know this can never be interpreted as a zero. This
302 /// extends isKnownNeverZero to cover the case where the assumed
303 /// floating-point mode for the function interprets denormals as zero.
304 bool isKnownNeverLogicalZero(const Function &F, Type *Ty) const;
305
306 /// Return true if it's know this can never be interpreted as a negative zero.
307 bool isKnownNeverLogicalNegZero(const Function &F, Type *Ty) const;
308
309 /// Return true if it's know this can never be interpreted as a positive zero.
310 bool isKnownNeverLogicalPosZero(const Function &F, Type *Ty) const;
311
316
317 /// Return true if we can prove that the analyzed floating-point value is
318 /// either NaN or never less than -0.0.
319 ///
320 /// NaN --> true
321 /// +0 --> true
322 /// -0 --> true
323 /// x > +0 --> true
324 /// x < -0 --> false
327 }
328
329 /// Return true if we can prove that the analyzed floating-point value is
330 /// either NaN or never greater than -0.0.
331 /// NaN --> true
332 /// +0 --> true
333 /// -0 --> true
334 /// x > +0 --> false
335 /// x < -0 --> true
338 }
339
341 KnownFPClasses = KnownFPClasses | RHS.KnownFPClasses;
342
343 if (SignBit != RHS.SignBit)
344 SignBit = std::nullopt;
345 return *this;
346 }
347
348 void knownNot(FPClassTest RuleOut) {
349 KnownFPClasses = KnownFPClasses & ~RuleOut;
350 }
351
352 void fneg() {
354 if (SignBit)
355 SignBit = !*SignBit;
356 }
357
358 void fabs() {
361
364
367
370
372 }
373
374 /// Return true if the sign bit must be 0, ignoring the sign of nans.
375 bool signBitIsZeroOrNaN() const {
376 return isKnownNever(fcNegative);
377 }
378
379 /// Assume the sign bit is zero.
382 SignBit = false;
383 }
384
385 void copysign(const KnownFPClass &Sign) {
386 // Don't know anything about the sign of the source. Expand the possible set
387 // to its opposite sign pair.
394 if (KnownFPClasses & fcInf)
396
397 // Sign bit is exactly preserved even for nans.
398 SignBit = Sign.SignBit;
399
400 // Clear sign bits based on the input sign mask.
401 if (Sign.isKnownNever(fcPositive | fcNan) || (SignBit && *SignBit))
403 if (Sign.isKnownNever(fcNegative | fcNan) || (SignBit && !*SignBit))
405 }
406
407 // Propagate knowledge that a non-NaN source implies the result can also not
408 // be a NaN. For unconstrained operations, signaling nans are not guaranteed
409 // to be quieted but cannot be introduced.
410 void propagateNaN(const KnownFPClass &Src, bool PreserveSign = false) {
411 if (Src.isKnownNever(fcNan)) {
413 if (PreserveSign)
414 SignBit = Src.SignBit;
415 } else if (Src.isKnownNever(fcSNan))
417 }
418
419 void resetAll() { *this = KnownFPClass(); }
420};
421
423 LHS |= RHS;
424 return LHS;
425}
426
428 RHS |= LHS;
429 return std::move(RHS);
430}
431
432/// Determine which floating-point classes are valid for \p V, and return them
433/// in KnownFPClass bit sets.
434///
435/// This function is defined on values with floating-point type, values vectors
436/// of floating-point type, and arrays of floating-point type.
437
438/// \p InterestedClasses is a compile time optimization hint for which floating
439/// point classes should be queried. Queries not specified in \p
440/// InterestedClasses should be reliable if they are determined during the
441/// query.
442KnownFPClass computeKnownFPClass(
443 const Value *V, const APInt &DemandedElts, const DataLayout &DL,
444 FPClassTest InterestedClasses = fcAllFlags, unsigned Depth = 0,
445 const TargetLibraryInfo *TLI = nullptr, AssumptionCache *AC = nullptr,
446 const Instruction *CxtI = nullptr, const DominatorTree *DT = nullptr,
447 bool UseInstrInfo = true);
448
449KnownFPClass computeKnownFPClass(
450 const Value *V, const DataLayout &DL,
451 FPClassTest InterestedClasses = fcAllFlags, unsigned Depth = 0,
452 const TargetLibraryInfo *TLI = nullptr, AssumptionCache *AC = nullptr,
453 const Instruction *CxtI = nullptr, const DominatorTree *DT = nullptr,
454 bool UseInstrInfo = true);
455
456/// Return true if we can prove that the specified FP value is never equal to
457/// -0.0.
458bool CannotBeNegativeZero(const Value *V, const TargetLibraryInfo *TLI,
459 unsigned Depth = 0);
460
461/// Return true if we can prove that the specified FP value is either NaN or
462/// never less than -0.0.
463///
464/// NaN --> true
465/// +0 --> true
466/// -0 --> true
467/// x > +0 --> true
468/// x < -0 --> false
469bool CannotBeOrderedLessThanZero(const Value *V, const DataLayout &DL,
470 const TargetLibraryInfo *TLI);
471
472/// Return true if the floating-point scalar value is not an infinity or if
473/// the floating-point vector value has no infinities. Return false if a value
474/// could ever be infinity.
475inline bool isKnownNeverInfinity(const Value *V, const DataLayout &DL,
476 const TargetLibraryInfo *TLI = nullptr,
477 unsigned Depth = 0,
478 AssumptionCache *AC = nullptr,
479 const Instruction *CtxI = nullptr,
480 const DominatorTree *DT = nullptr,
481 bool UseInstrInfo = true) {
482 KnownFPClass Known = computeKnownFPClass(V, DL, fcInf, Depth, TLI, AC, CtxI,
483 DT, UseInstrInfo);
484 return Known.isKnownNeverInfinity();
485}
486
487/// Return true if the floating-point value can never contain a NaN or infinity.
489 const Value *V, const DataLayout &DL, const TargetLibraryInfo *TLI,
490 unsigned Depth = 0, AssumptionCache *AC = nullptr,
491 const Instruction *CtxI = nullptr, const DominatorTree *DT = nullptr,
492 bool UseInstrInfo = true) {
493 KnownFPClass Known = computeKnownFPClass(V, DL, fcInf | fcNan, Depth, TLI, AC,
494 CtxI, DT, UseInstrInfo);
495 return Known.isKnownNeverNaN() && Known.isKnownNeverInfinity();
496}
497
498/// Return true if the floating-point scalar value is not a NaN or if the
499/// floating-point vector value has no NaN elements. Return false if a value
500/// could ever be NaN.
501inline bool isKnownNeverNaN(const Value *V, const DataLayout &DL,
502 const TargetLibraryInfo *TLI, unsigned Depth = 0,
503 AssumptionCache *AC = nullptr,
504 const Instruction *CtxI = nullptr,
505 const DominatorTree *DT = nullptr,
506 bool UseInstrInfo = true) {
507 KnownFPClass Known = computeKnownFPClass(V, DL, fcNan, Depth, TLI, AC, CtxI,
508 DT, UseInstrInfo);
509 return Known.isKnownNeverNaN();
510}
511
512/// Return true if we can prove that the specified FP value's sign bit is 0.
513///
514/// NaN --> true/false (depending on the NaN's sign bit)
515/// +0 --> true
516/// -0 --> false
517/// x > +0 --> true
518/// x < -0 --> false
519bool SignBitMustBeZero(const Value *V, const DataLayout &DL,
520 const TargetLibraryInfo *TLI);
521
522/// If the specified value can be set by repeating the same byte in memory,
523/// return the i8 value that it is represented with. This is true for all i8
524/// values obviously, but is also true for i32 0, i32 -1, i16 0xF0F0, double
525/// 0.0 etc. If the value can't be handled with a repeated byte store (e.g.
526/// i16 0x1234), return null. If the value is entirely undef and padding,
527/// return undef.
528Value *isBytewiseValue(Value *V, const DataLayout &DL);
529
530/// Given an aggregate and an sequence of indices, see if the scalar value
531/// indexed is already around as a register, for example if it were inserted
532/// directly into the aggregate.
533///
534/// If InsertBefore is not null, this function will duplicate (modified)
535/// insertvalues when a part of a nested struct is extracted.
536Value *FindInsertedValue(Value *V, ArrayRef<unsigned> idx_range,
537 Instruction *InsertBefore = nullptr);
538
539/// Analyze the specified pointer to see if it can be expressed as a base
540/// pointer plus a constant offset. Return the base and offset to the caller.
541///
542/// This is a wrapper around Value::stripAndAccumulateConstantOffsets that
543/// creates and later unpacks the required APInt.
545 const DataLayout &DL,
546 bool AllowNonInbounds = true) {
547 APInt OffsetAPInt(DL.getIndexTypeSizeInBits(Ptr->getType()), 0);
548 Value *Base =
549 Ptr->stripAndAccumulateConstantOffsets(DL, OffsetAPInt, AllowNonInbounds);
550
551 Offset = OffsetAPInt.getSExtValue();
552 return Base;
553}
554inline const Value *
556 const DataLayout &DL,
557 bool AllowNonInbounds = true) {
558 return GetPointerBaseWithConstantOffset(const_cast<Value *>(Ptr), Offset, DL,
559 AllowNonInbounds);
560}
561
562/// Returns true if the GEP is based on a pointer to a string (array of
563// \p CharSize integers) and is indexing into this string.
564bool isGEPBasedOnPointerToString(const GEPOperator *GEP, unsigned CharSize = 8);
565
566/// Represents offset+length into a ConstantDataArray.
568 /// ConstantDataArray pointer. nullptr indicates a zeroinitializer (a valid
569 /// initializer, it just doesn't fit the ConstantDataArray interface).
571
572 /// Slice starts at this Offset.
574
575 /// Length of the slice.
577
578 /// Moves the Offset and adjusts Length accordingly.
579 void move(uint64_t Delta) {
580 assert(Delta < Length);
581 Offset += Delta;
582 Length -= Delta;
583 }
584
585 /// Convenience accessor for elements in the slice.
586 uint64_t operator[](unsigned I) const {
587 return Array == nullptr ? 0 : Array->getElementAsInteger(I + Offset);
588 }
589};
590
591/// Returns true if the value \p V is a pointer into a ConstantDataArray.
592/// If successful \p Slice will point to a ConstantDataArray info object
593/// with an appropriate offset.
594bool getConstantDataArrayInfo(const Value *V, ConstantDataArraySlice &Slice,
595 unsigned ElementSize, uint64_t Offset = 0);
596
597/// This function computes the length of a null-terminated C string pointed to
598/// by V. If successful, it returns true and returns the string in Str. If
599/// unsuccessful, it returns false. This does not include the trailing null
600/// character by default. If TrimAtNul is set to false, then this returns any
601/// trailing null characters as well as any other characters that come after
602/// it.
603bool getConstantStringInfo(const Value *V, StringRef &Str,
604 bool TrimAtNul = true);
605
606/// If we can compute the length of the string pointed to by the specified
607/// pointer, return 'len+1'. If we can't, return 0.
608uint64_t GetStringLength(const Value *V, unsigned CharSize = 8);
609
610/// This function returns call pointer argument that is considered the same by
611/// aliasing rules. You CAN'T use it to replace one value with another. If
612/// \p MustPreserveNullness is true, the call must preserve the nullness of
613/// the pointer.
614const Value *getArgumentAliasingToReturnedPointer(const CallBase *Call,
615 bool MustPreserveNullness);
617 bool MustPreserveNullness) {
618 return const_cast<Value *>(getArgumentAliasingToReturnedPointer(
619 const_cast<const CallBase *>(Call), MustPreserveNullness));
620}
621
622/// {launder,strip}.invariant.group returns pointer that aliases its argument,
623/// and it only captures pointer by returning it.
624/// These intrinsics are not marked as nocapture, because returning is
625/// considered as capture. The arguments are not marked as returned neither,
626/// because it would make it useless. If \p MustPreserveNullness is true,
627/// the intrinsic must preserve the nullness of the pointer.
629 const CallBase *Call, bool MustPreserveNullness);
630
631/// This method strips off any GEP address adjustments and pointer casts from
632/// the specified value, returning the original object being addressed. Note
633/// that the returned value has pointer type if the specified value does. If
634/// the MaxLookup value is non-zero, it limits the number of instructions to
635/// be stripped off.
636const Value *getUnderlyingObject(const Value *V, unsigned MaxLookup = 6);
637inline Value *getUnderlyingObject(Value *V, unsigned MaxLookup = 6) {
638 // Force const to avoid infinite recursion.
639 const Value *VConst = V;
640 return const_cast<Value *>(getUnderlyingObject(VConst, MaxLookup));
641}
642
643/// This method is similar to getUnderlyingObject except that it can
644/// look through phi and select instructions and return multiple objects.
645///
646/// If LoopInfo is passed, loop phis are further analyzed. If a pointer
647/// accesses different objects in each iteration, we don't look through the
648/// phi node. E.g. consider this loop nest:
649///
650/// int **A;
651/// for (i)
652/// for (j) {
653/// A[i][j] = A[i-1][j] * B[j]
654/// }
655///
656/// This is transformed by Load-PRE to stash away A[i] for the next iteration
657/// of the outer loop:
658///
659/// Curr = A[0]; // Prev_0
660/// for (i: 1..N) {
661/// Prev = Curr; // Prev = PHI (Prev_0, Curr)
662/// Curr = A[i];
663/// for (j: 0..N) {
664/// Curr[j] = Prev[j] * B[j]
665/// }
666/// }
667///
668/// Since A[i] and A[i-1] are independent pointers, getUnderlyingObjects
669/// should not assume that Curr and Prev share the same underlying object thus
670/// it shouldn't look through the phi above.
671void getUnderlyingObjects(const Value *V,
672 SmallVectorImpl<const Value *> &Objects,
673 LoopInfo *LI = nullptr, unsigned MaxLookup = 6);
674
675/// This is a wrapper around getUnderlyingObjects and adds support for basic
676/// ptrtoint+arithmetic+inttoptr sequences.
677bool getUnderlyingObjectsForCodeGen(const Value *V,
678 SmallVectorImpl<Value *> &Objects);
679
680/// Returns unique alloca where the value comes from, or nullptr.
681/// If OffsetZero is true check that V points to the begining of the alloca.
682AllocaInst *findAllocaForValue(Value *V, bool OffsetZero = false);
683inline const AllocaInst *findAllocaForValue(const Value *V,
684 bool OffsetZero = false) {
685 return findAllocaForValue(const_cast<Value *>(V), OffsetZero);
686}
687
688/// Return true if the only users of this pointer are lifetime markers.
689bool onlyUsedByLifetimeMarkers(const Value *V);
690
691/// Return true if the only users of this pointer are lifetime markers or
692/// droppable instructions.
694
695/// Return true if speculation of the given load must be suppressed to avoid
696/// ordering or interfering with an active sanitizer. If not suppressed,
697/// dereferenceability and alignment must be proven separately. Note: This
698/// is only needed for raw reasoning; if you use the interface below
699/// (isSafeToSpeculativelyExecute), this is handled internally.
700bool mustSuppressSpeculation(const LoadInst &LI);
701
702/// Return true if the instruction does not have any effects besides
703/// calculating the result and does not have undefined behavior.
704///
705/// This method never returns true for an instruction that returns true for
706/// mayHaveSideEffects; however, this method also does some other checks in
707/// addition. It checks for undefined behavior, like dividing by zero or
708/// loading from an invalid pointer (but not for undefined results, like a
709/// shift with a shift amount larger than the width of the result). It checks
710/// for malloc and alloca because speculatively executing them might cause a
711/// memory leak. It also returns false for instructions related to control
712/// flow, specifically terminators and PHI nodes.
713///
714/// If the CtxI is specified this method performs context-sensitive analysis
715/// and returns true if it is safe to execute the instruction immediately
716/// before the CtxI.
717///
718/// If the CtxI is NOT specified this method only looks at the instruction
719/// itself and its operands, so if this method returns true, it is safe to
720/// move the instruction as long as the correct dominance relationships for
721/// the operands and users hold.
722///
723/// This method can return true for instructions that read memory;
724/// for such instructions, moving them may change the resulting value.
725bool isSafeToSpeculativelyExecute(const Instruction *I,
726 const Instruction *CtxI = nullptr,
727 AssumptionCache *AC = nullptr,
728 const DominatorTree *DT = nullptr,
729 const TargetLibraryInfo *TLI = nullptr);
730
731/// This returns the same result as isSafeToSpeculativelyExecute if Opcode is
732/// the actual opcode of Inst. If the provided and actual opcode differ, the
733/// function (virtually) overrides the opcode of Inst with the provided
734/// Opcode. There are come constraints in this case:
735/// * If Opcode has a fixed number of operands (eg, as binary operators do),
736/// then Inst has to have at least as many leading operands. The function
737/// will ignore all trailing operands beyond that number.
738/// * If Opcode allows for an arbitrary number of operands (eg, as CallInsts
739/// do), then all operands are considered.
740/// * The virtual instruction has to satisfy all typing rules of the provided
741/// Opcode.
742/// * This function is pessimistic in the following sense: If one actually
743/// materialized the virtual instruction, then isSafeToSpeculativelyExecute
744/// may say that the materialized instruction is speculatable whereas this
745/// function may have said that the instruction wouldn't be speculatable.
746/// This behavior is a shortcoming in the current implementation and not
747/// intentional.
749 unsigned Opcode, const Instruction *Inst, const Instruction *CtxI = nullptr,
750 AssumptionCache *AC = nullptr, const DominatorTree *DT = nullptr,
751 const TargetLibraryInfo *TLI = nullptr);
752
753/// Returns true if the result or effects of the given instructions \p I
754/// depend values not reachable through the def use graph.
755/// * Memory dependence arises for example if the instruction reads from
756/// memory or may produce effects or undefined behaviour. Memory dependent
757/// instructions generally cannot be reorderd with respect to other memory
758/// dependent instructions.
759/// * Control dependence arises for example if the instruction may fault
760/// if lifted above a throwing call or infinite loop.
761bool mayHaveNonDefUseDependency(const Instruction &I);
762
763/// Return true if it is an intrinsic that cannot be speculated but also
764/// cannot trap.
765bool isAssumeLikeIntrinsic(const Instruction *I);
766
767/// Return true if it is valid to use the assumptions provided by an
768/// assume intrinsic, I, at the point in the control-flow identified by the
769/// context instruction, CxtI.
770bool isValidAssumeForContext(const Instruction *I, const Instruction *CxtI,
771 const DominatorTree *DT = nullptr);
772
773enum class OverflowResult {
774 /// Always overflows in the direction of signed/unsigned min value.
776 /// Always overflows in the direction of signed/unsigned max value.
778 /// May or may not overflow.
780 /// Never overflows.
782};
783
784OverflowResult computeOverflowForUnsignedMul(const Value *LHS, const Value *RHS,
785 const DataLayout &DL,
786 AssumptionCache *AC,
787 const Instruction *CxtI,
788 const DominatorTree *DT,
789 bool UseInstrInfo = true);
790OverflowResult computeOverflowForSignedMul(const Value *LHS, const Value *RHS,
791 const DataLayout &DL,
792 AssumptionCache *AC,
793 const Instruction *CxtI,
794 const DominatorTree *DT,
795 bool UseInstrInfo = true);
796OverflowResult computeOverflowForUnsignedAdd(const Value *LHS, const Value *RHS,
797 const DataLayout &DL,
798 AssumptionCache *AC,
799 const Instruction *CxtI,
800 const DominatorTree *DT,
801 bool UseInstrInfo = true);
802OverflowResult computeOverflowForSignedAdd(const Value *LHS, const Value *RHS,
803 const DataLayout &DL,
804 AssumptionCache *AC = nullptr,
805 const Instruction *CxtI = nullptr,
806 const DominatorTree *DT = nullptr);
807/// This version also leverages the sign bit of Add if known.
809 const DataLayout &DL,
810 AssumptionCache *AC = nullptr,
811 const Instruction *CxtI = nullptr,
812 const DominatorTree *DT = nullptr);
813OverflowResult computeOverflowForUnsignedSub(const Value *LHS, const Value *RHS,
814 const DataLayout &DL,
815 AssumptionCache *AC,
816 const Instruction *CxtI,
817 const DominatorTree *DT);
818OverflowResult computeOverflowForSignedSub(const Value *LHS, const Value *RHS,
819 const DataLayout &DL,
820 AssumptionCache *AC,
821 const Instruction *CxtI,
822 const DominatorTree *DT);
823
824/// Returns true if the arithmetic part of the \p WO 's result is
825/// used only along the paths control dependent on the computation
826/// not overflowing, \p WO being an <op>.with.overflow intrinsic.
827bool isOverflowIntrinsicNoWrap(const WithOverflowInst *WO,
828 const DominatorTree &DT);
829
830/// Determine the possible constant range of vscale with the given bit width,
831/// based on the vscale_range function attribute.
832ConstantRange getVScaleRange(const Function *F, unsigned BitWidth);
833
834/// Determine the possible constant range of an integer or vector of integer
835/// value. This is intended as a cheap, non-recursive check.
836ConstantRange computeConstantRange(const Value *V, bool ForSigned,
837 bool UseInstrInfo = true,
838 AssumptionCache *AC = nullptr,
839 const Instruction *CtxI = nullptr,
840 const DominatorTree *DT = nullptr,
841 unsigned Depth = 0);
842
843/// Return true if this function can prove that the instruction I will
844/// always transfer execution to one of its successors (including the next
845/// instruction that follows within a basic block). E.g. this is not
846/// guaranteed for function calls that could loop infinitely.
847///
848/// In other words, this function returns false for instructions that may
849/// transfer execution or fail to transfer execution in a way that is not
850/// captured in the CFG nor in the sequence of instructions within a basic
851/// block.
852///
853/// Undefined behavior is assumed not to happen, so e.g. division is
854/// guaranteed to transfer execution to the following instruction even
855/// though division by zero might cause undefined behavior.
856bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I);
857
858/// Returns true if this block does not contain a potential implicit exit.
859/// This is equivelent to saying that all instructions within the basic block
860/// are guaranteed to transfer execution to their successor within the basic
861/// block. This has the same assumptions w.r.t. undefined behavior as the
862/// instruction variant of this function.
863bool isGuaranteedToTransferExecutionToSuccessor(const BasicBlock *BB);
864
865/// Return true if every instruction in the range (Begin, End) is
866/// guaranteed to transfer execution to its static successor. \p ScanLimit
867/// bounds the search to avoid scanning huge blocks.
870 unsigned ScanLimit = 32);
871
872/// Same as previous, but with range expressed via iterator_range.
874 iterator_range<BasicBlock::const_iterator> Range, unsigned ScanLimit = 32);
875
876/// Return true if this function can prove that the instruction I
877/// is executed for every iteration of the loop L.
878///
879/// Note that this currently only considers the loop header.
880bool isGuaranteedToExecuteForEveryIteration(const Instruction *I,
881 const Loop *L);
882
883/// Return true if \p PoisonOp's user yields poison or raises UB if its
884/// operand \p PoisonOp is poison.
885///
886/// If \p PoisonOp is a vector or an aggregate and the operation's result is a
887/// single value, any poison element in /p PoisonOp should make the result
888/// poison or raise UB.
889///
890/// To filter out operands that raise UB on poison, you can use
891/// getGuaranteedNonPoisonOp.
892bool propagatesPoison(const Use &PoisonOp);
893
894/// Insert operands of I into Ops such that I will trigger undefined behavior
895/// if I is executed and that operand has a poison value.
896void getGuaranteedNonPoisonOps(const Instruction *I,
897 SmallVectorImpl<const Value *> &Ops);
898
899/// Insert operands of I into Ops such that I will trigger undefined behavior
900/// if I is executed and that operand is not a well-defined value
901/// (i.e. has undef bits or poison).
902void getGuaranteedWellDefinedOps(const Instruction *I,
903 SmallVectorImpl<const Value *> &Ops);
904
905/// Return true if the given instruction must trigger undefined behavior
906/// when I is executed with any operands which appear in KnownPoison holding
907/// a poison value at the point of execution.
908bool mustTriggerUB(const Instruction *I,
909 const SmallPtrSetImpl<const Value *> &KnownPoison);
910
911/// Return true if this function can prove that if Inst is executed
912/// and yields a poison value or undef bits, then that will trigger
913/// undefined behavior.
914///
915/// Note that this currently only considers the basic block that is
916/// the parent of Inst.
917bool programUndefinedIfUndefOrPoison(const Instruction *Inst);
918bool programUndefinedIfPoison(const Instruction *Inst);
919
920/// canCreateUndefOrPoison returns true if Op can create undef or poison from
921/// non-undef & non-poison operands.
922/// For vectors, canCreateUndefOrPoison returns true if there is potential
923/// poison or undef in any element of the result when vectors without
924/// undef/poison poison are given as operands.
925/// For example, given `Op = shl <2 x i32> %x, <0, 32>`, this function returns
926/// true. If Op raises immediate UB but never creates poison or undef
927/// (e.g. sdiv I, 0), canCreatePoison returns false.
928///
929/// \p ConsiderFlagsAndMetadata controls whether poison producing flags and
930/// metadata on the instruction are considered. This can be used to see if the
931/// instruction could still introduce undef or poison even without poison
932/// generating flags and metadata which might be on the instruction.
933/// (i.e. could the result of Op->dropPoisonGeneratingFlags() still create
934/// poison or undef)
935///
936/// canCreatePoison returns true if Op can create poison from non-poison
937/// operands.
938bool canCreateUndefOrPoison(const Operator *Op,
939 bool ConsiderFlagsAndMetadata = true);
940bool canCreatePoison(const Operator *Op, bool ConsiderFlagsAndMetadata = true);
941
942/// Return true if V is poison given that ValAssumedPoison is already poison.
943/// For example, if ValAssumedPoison is `icmp X, 10` and V is `icmp X, 5`,
944/// impliesPoison returns true.
945bool impliesPoison(const Value *ValAssumedPoison, const Value *V);
946
947/// Return true if this function can prove that V does not have undef bits
948/// and is never poison. If V is an aggregate value or vector, check whether
949/// all elements (except padding) are not undef or poison.
950/// Note that this is different from canCreateUndefOrPoison because the
951/// function assumes Op's operands are not poison/undef.
952///
953/// If CtxI and DT are specified this method performs flow-sensitive analysis
954/// and returns true if it is guaranteed to be never undef or poison
955/// immediately before the CtxI.
956bool isGuaranteedNotToBeUndefOrPoison(const Value *V,
957 AssumptionCache *AC = nullptr,
958 const Instruction *CtxI = nullptr,
959 const DominatorTree *DT = nullptr,
960 unsigned Depth = 0);
961bool isGuaranteedNotToBePoison(const Value *V, AssumptionCache *AC = nullptr,
962 const Instruction *CtxI = nullptr,
963 const DominatorTree *DT = nullptr,
964 unsigned Depth = 0);
965
966/// Return true if undefined behavior would provable be executed on the path to
967/// OnPathTo if Root produced a posion result. Note that this doesn't say
968/// anything about whether OnPathTo is actually executed or whether Root is
969/// actually poison. This can be used to assess whether a new use of Root can
970/// be added at a location which is control equivalent with OnPathTo (such as
971/// immediately before it) without introducing UB which didn't previously
972/// exist. Note that a false result conveys no information.
973bool mustExecuteUBIfPoisonOnPathTo(Instruction *Root,
974 Instruction *OnPathTo,
975 DominatorTree *DT);
976
977/// Specific patterns of select instructions we can match.
980 SPF_SMIN, /// Signed minimum
981 SPF_UMIN, /// Unsigned minimum
982 SPF_SMAX, /// Signed maximum
983 SPF_UMAX, /// Unsigned maximum
984 SPF_FMINNUM, /// Floating point minnum
985 SPF_FMAXNUM, /// Floating point maxnum
986 SPF_ABS, /// Absolute value
987 SPF_NABS /// Negated absolute value
989
990/// Behavior when a floating point min/max is given one NaN and one
991/// non-NaN as input.
993 SPNB_NA = 0, /// NaN behavior not applicable.
994 SPNB_RETURNS_NAN, /// Given one NaN input, returns the NaN.
995 SPNB_RETURNS_OTHER, /// Given one NaN input, returns the non-NaN.
996 SPNB_RETURNS_ANY /// Given one NaN input, can return either (or
997 /// it has been determined that no operands can
998 /// be NaN).
1000
1003 SelectPatternNaNBehavior NaNBehavior; /// Only applicable if Flavor is
1004 /// SPF_FMINNUM or SPF_FMAXNUM.
1005 bool Ordered; /// When implementing this min/max pattern as
1006 /// fcmp; select, does the fcmp have to be
1007 /// ordered?
1008
1009 /// Return true if \p SPF is a min or a max pattern.
1011 return SPF != SPF_UNKNOWN && SPF != SPF_ABS && SPF != SPF_NABS;
1012 }
1013};
1014
1015/// Pattern match integer [SU]MIN, [SU]MAX and ABS idioms, returning the kind
1016/// and providing the out parameter results if we successfully match.
1017///
1018/// For ABS/NABS, LHS will be set to the input to the abs idiom. RHS will be
1019/// the negation instruction from the idiom.
1020///
1021/// If CastOp is not nullptr, also match MIN/MAX idioms where the type does
1022/// not match that of the original select. If this is the case, the cast
1023/// operation (one of Trunc,SExt,Zext) that must be done to transform the
1024/// type of LHS and RHS into the type of V is returned in CastOp.
1025///
1026/// For example:
1027/// %1 = icmp slt i32 %a, i32 4
1028/// %2 = sext i32 %a to i64
1029/// %3 = select i1 %1, i64 %2, i64 4
1030///
1031/// -> LHS = %a, RHS = i32 4, *CastOp = Instruction::SExt
1032///
1033SelectPatternResult matchSelectPattern(Value *V, Value *&LHS, Value *&RHS,
1034 Instruction::CastOps *CastOp = nullptr,
1035 unsigned Depth = 0);
1036
1038 const Value *&RHS) {
1039 Value *L = const_cast<Value *>(LHS);
1040 Value *R = const_cast<Value *>(RHS);
1041 auto Result = matchSelectPattern(const_cast<Value *>(V), L, R);
1042 LHS = L;
1043 RHS = R;
1044 return Result;
1045}
1046
1047/// Determine the pattern that a select with the given compare as its
1048/// predicate and given values as its true/false operands would match.
1049SelectPatternResult matchDecomposedSelectPattern(
1050 CmpInst *CmpI, Value *TrueVal, Value *FalseVal, Value *&LHS, Value *&RHS,
1051 Instruction::CastOps *CastOp = nullptr, unsigned Depth = 0);
1052
1053/// Return the canonical comparison predicate for the specified
1054/// minimum/maximum flavor.
1055CmpInst::Predicate getMinMaxPred(SelectPatternFlavor SPF, bool Ordered = false);
1056
1057/// Return the inverse minimum/maximum flavor of the specified flavor.
1058/// For example, signed minimum is the inverse of signed maximum.
1060
1062
1063/// Return the minimum or maximum constant value for the specified integer
1064/// min/max flavor and type.
1065APInt getMinMaxLimit(SelectPatternFlavor SPF, unsigned BitWidth);
1066
1067/// Check if the values in \p VL are select instructions that can be converted
1068/// to a min or max (vector) intrinsic. Returns the intrinsic ID, if such a
1069/// conversion is possible, together with a bool indicating whether all select
1070/// conditions are only used by the selects. Otherwise return
1071/// Intrinsic::not_intrinsic.
1072std::pair<Intrinsic::ID, bool>
1073canConvertToMinOrMaxIntrinsic(ArrayRef<Value *> VL);
1074
1075/// Attempt to match a simple first order recurrence cycle of the form:
1076/// %iv = phi Ty [%Start, %Entry], [%Inc, %backedge]
1077/// %inc = binop %iv, %step
1078/// OR
1079/// %iv = phi Ty [%Start, %Entry], [%Inc, %backedge]
1080/// %inc = binop %step, %iv
1081///
1082/// A first order recurrence is a formula with the form: X_n = f(X_(n-1))
1083///
1084/// A couple of notes on subtleties in that definition:
1085/// * The Step does not have to be loop invariant. In math terms, it can
1086/// be a free variable. We allow recurrences with both constant and
1087/// variable coefficients. Callers may wish to filter cases where Step
1088/// does not dominate P.
1089/// * For non-commutative operators, we will match both forms. This
1090/// results in some odd recurrence structures. Callers may wish to filter
1091/// out recurrences where the phi is not the LHS of the returned operator.
1092/// * Because of the structure matched, the caller can assume as a post
1093/// condition of the match the presence of a Loop with P's parent as it's
1094/// header *except* in unreachable code. (Dominance decays in unreachable
1095/// code.)
1096///
1097/// NOTE: This is intentional simple. If you want the ability to analyze
1098/// non-trivial loop conditons, see ScalarEvolution instead.
1099bool matchSimpleRecurrence(const PHINode *P, BinaryOperator *&BO, Value *&Start,
1100 Value *&Step);
1101
1102/// Analogous to the above, but starting from the binary operator
1103bool matchSimpleRecurrence(const BinaryOperator *I, PHINode *&P, Value *&Start,
1104 Value *&Step);
1105
1106/// Return true if RHS is known to be implied true by LHS. Return false if
1107/// RHS is known to be implied false by LHS. Otherwise, return std::nullopt if
1108/// no implication can be made. A & B must be i1 (boolean) values or a vector of
1109/// such values. Note that the truth table for implication is the same as <=u on
1110/// i1 values (but not
1111/// <=s!). The truth table for both is:
1112/// | T | F (B)
1113/// T | T | F
1114/// F | T | T
1115/// (A)
1116std::optional<bool> isImpliedCondition(const Value *LHS, const Value *RHS,
1117 const DataLayout &DL,
1118 bool LHSIsTrue = true,
1119 unsigned Depth = 0);
1120std::optional<bool> isImpliedCondition(const Value *LHS,
1121 CmpInst::Predicate RHSPred,
1122 const Value *RHSOp0, const Value *RHSOp1,
1123 const DataLayout &DL,
1124 bool LHSIsTrue = true,
1125 unsigned Depth = 0);
1126
1127/// Return the boolean condition value in the context of the given instruction
1128/// if it is known based on dominating conditions.
1129std::optional<bool> isImpliedByDomCondition(const Value *Cond,
1130 const Instruction *ContextI,
1131 const DataLayout &DL);
1132std::optional<bool> isImpliedByDomCondition(CmpInst::Predicate Pred,
1133 const Value *LHS, const Value *RHS,
1134 const Instruction *ContextI,
1135 const DataLayout &DL);
1136} // end namespace llvm
1137
1138#endif // LLVM_ANALYSIS_VALUETRACKING_H
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
SmallVector< MachineOperand, 4 > Cond
This file contains the declarations for the subclasses of Constant, which represent the different fla...
bool End
Definition: ELF_riscv.cpp:464
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
Hexagon Common GEP
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
#define P(N)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallSet class.
Value * RHS
Value * LHS
Class for arbitrary precision integers.
Definition: APInt.h:75
int64_t getSExtValue() const
Get sign extended value.
Definition: APInt.h:1520
an instruction to allocate memory on the stack
Definition: Instructions.h:58
A cache of @llvm.assume calls within a function.
InstListType::const_iterator const_iterator
Definition: BasicBlock.h:88
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1190
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:711
An array constant whose element type is a simple 1/2/4/8-byte integer or float/double,...
Definition: Constants.h:677
uint64_t getElementAsInteger(unsigned i) const
If this is a sequential container of integers (of any size), return the specified element in the low ...
Definition: Constants.cpp:3049
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:110
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
Metadata node.
Definition: Metadata.h:950
This is a utility class that provides an abstraction for the common functionality between Instruction...
Definition: Operator.h:31
Provides information about what library functions are available for the current target.
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
LLVM Value Representation.
Definition: Value.h:74
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
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.
bool mustExecuteUBIfPoisonOnPathTo(Instruction *Root, Instruction *OnPathTo, DominatorTree *DT)
Return true if undefined behavior would provable be executed on the path to OnPathTo if Root produced...
Intrinsic::ID getInverseMinMaxIntrinsic(Intrinsic::ID MinMaxID)
@ Offset
Definition: DWP.cpp:440
OverflowResult
@ NeverOverflows
Never overflows.
@ AlwaysOverflowsHigh
Always overflows in the direction of signed/unsigned max value.
@ AlwaysOverflowsLow
Always overflows in the direction of signed/unsigned min value.
@ MayOverflow
May or may not overflow.
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.
OverflowResult computeOverflowForSignedMul(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT, bool UseInstrInfo=true)
OverflowResult computeOverflowForSignedSub(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT)
bool canCreatePoison(const Operator *Op, bool ConsiderFlagsAndMetadata=true)
bool mustTriggerUB(const Instruction *I, const SmallPtrSetImpl< const Value * > &KnownPoison)
Return true if the given instruction must trigger undefined behavior when I is executed with any oper...
bool isKnownNegation(const Value *X, const Value *Y, bool NeedNSW=false)
Return true if the two given values are negation.
bool isOnlyUsedInZeroEqualityComparison(const Instruction *CxtI)
const Value * getArgumentAliasingToReturnedPointer(const CallBase *Call, bool MustPreserveNullness)
This function returns call pointer argument that is considered the same by aliasing rules.
OverflowResult computeOverflowForSignedAdd(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr)
bool isAssumeLikeIntrinsic(const Instruction *I)
Return true if it is an intrinsic that cannot be speculated but also cannot trap.
AllocaInst * findAllocaForValue(Value *V, bool OffsetZero=false)
Returns unique alloca where the value comes from, or nullptr.
APInt getMinMaxLimit(SelectPatternFlavor SPF, unsigned BitWidth)
Return the minimum or maximum constant value for the specified integer min/max flavor and type.
OverflowResult computeOverflowForUnsignedMul(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT, bool UseInstrInfo=true)
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 getConstantStringInfo(const Value *V, StringRef &Str, bool TrimAtNul=true)
This function computes the length of a null-terminated C string pointed to by V.
void computeKnownBitsFromAssume(const Value *V, KnownBits &Known, unsigned Depth, const SimplifyQuery &Q)
Merge bits known from assumes into Known.
bool onlyUsedByLifetimeMarkersOrDroppableInsts(const Value *V)
Return true if the only users of this pointer are lifetime markers or droppable instructions.
bool getUnderlyingObjectsForCodeGen(const Value *V, SmallVectorImpl< Value * > &Objects)
This is a wrapper around getUnderlyingObjects and adds support for basic ptrtoint+arithmetic+inttoptr...
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 getConstantDataArrayInfo(const Value *V, ConstantDataArraySlice &Slice, unsigned ElementSize, uint64_t Offset=0)
Returns true if the value V is a pointer into a ConstantDataArray.
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 ...
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 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.
bool mustSuppressSpeculation(const LoadInst &LI)
Return true if speculation of the given load must be suppressed to avoid ordering or interfering with...
CmpInst::Predicate getMinMaxPred(SelectPatternFlavor SPF, bool Ordered=false)
Return the canonical comparison predicate for the specified minimum/maximum flavor.
bool isKnownNeverNaN(const Value *V, const DataLayout &DL, const TargetLibraryInfo *TLI, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Return true if the floating-point scalar value is not a NaN or if the floating-point vector value has...
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.
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 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.
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,...
bool isKnownNeverInfinity(const Value *V, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Return true if the floating-point scalar value is not an infinity or if the floating-point vector val...
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...
SelectPatternFlavor getInverseMinMaxFlavor(SelectPatternFlavor SPF)
Return the inverse minimum/maximum flavor of the specified flavor.
constexpr unsigned MaxAnalysisRecursionDepth
Definition: ValueTracking.h:46
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...
FPClassTest fneg(FPClassTest Mask)
Return the test mask which returns true if the value's sign bit is flipped.
SelectPatternFlavor
Specific patterns of select instructions we can match.
@ SPF_ABS
Floating point maxnum.
@ SPF_NABS
Absolute value.
@ SPF_FMAXNUM
Floating point minnum.
@ SPF_UMIN
Signed minimum.
@ SPF_UMAX
Signed maximum.
@ SPF_SMIN
@ SPF_SMAX
Unsigned minimum.
@ SPF_UNKNOWN
@ SPF_FMINNUM
Unsigned maximum.
bool isIntrinsicReturningPointerAliasingArgumentWithoutCapturing(const CallBase *Call, bool MustPreserveNullness)
{launder,strip}.invariant.group returns pointer that aliases its argument, and it only captures point...
bool impliesPoison(const Value *ValAssumedPoison, const Value *V)
Return true if V is poison given that ValAssumedPoison is already poison.
FPClassTest
Floating-point class tests, supported by 'is_fpclass' intrinsic.
bool programUndefinedIfPoison(const Instruction *Inst)
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...
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...
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'.
ConstantRange getVScaleRange(const Function *F, unsigned BitWidth)
Determine the possible constant range of vscale with the given bit width, based on the vscale_range f...
bool canCreateUndefOrPoison(const Operator *Op, bool ConsiderFlagsAndMetadata=true)
canCreateUndefOrPoison returns true if Op can create undef or poison from non-undef & non-poison oper...
KnownBits analyzeKnownBitsFromAndXorOr(const Operator *I, const KnownBits &KnownLHS, const KnownBits &KnownRHS, unsigned Depth, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Using KnownBits LHS/RHS produce the known bits for logic op (and/xor/or).
OverflowResult computeOverflowForUnsignedSub(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT)
bool onlyUsedByLifetimeMarkers(const Value *V)
Return true if the only users of this pointer are lifetime markers.
Intrinsic::ID getIntrinsicForCallSite(const CallBase &CB, const TargetLibraryInfo *TLI)
Map a call instruction to an intrinsic ID.
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.
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...
bool propagatesPoison(const Use &PoisonOp)
Return true if PoisonOp's user yields poison or raises UB if its operand PoisonOp is poison.
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.
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.
@ Add
Sum of integers.
bool isKnownNeverInfOrNaN(const Value *V, const DataLayout &DL, const TargetLibraryInfo *TLI, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Return true if the floating-point value can never contain a NaN or infinity.
SelectPatternNaNBehavior
Behavior when a floating point min/max is given one NaN and one non-NaN as input.
@ SPNB_RETURNS_NAN
NaN behavior not applicable.
@ SPNB_RETURNS_OTHER
Given one NaN input, returns the NaN.
@ SPNB_RETURNS_ANY
Given one NaN input, returns the non-NaN.
void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
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.
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 ...
constexpr unsigned BitWidth
Definition: BitmaskEnum.h:184
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 isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)
Return true if this function can prove that the instruction I will always transfer execution to one o...
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.
bool CannotBeOrderedLessThanZero(const Value *V, const DataLayout &DL, const TargetLibraryInfo *TLI)
Return true if we can prove that the specified FP value is either NaN or never less than -0....
std::pair< Value *, FPClassTest > fcmpToClassTest(CmpInst::Predicate Pred, const Function &F, Value *LHS, Value *RHS, bool LookThroughSrc=true)
Returns a pair of values, which if passed to llvm.is.fpclass, returns the same result as an fcmp with...
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...
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.
bool SignBitMustBeZero(const Value *V, const DataLayout &DL, const TargetLibraryInfo *TLI)
Return true if we can prove that the specified FP value's sign bit is 0.
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...
bool isGEPBasedOnPointerToString(const GEPOperator *GEP, unsigned CharSize=8)
Returns true if the GEP is based on a pointer to a string (array of.
APInt operator|(APInt a, const APInt &b)
Definition: APInt.h:2082
bool isGuaranteedNotToBePoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
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.
void computeKnownBitsFromRangeMetadata(const MDNode &Ranges, KnownBits &Known)
Compute known bits from the range metadata.
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.
bool mayHaveNonDefUseDependency(const Instruction &I)
Returns true if the result or effects of the given instructions I depend values not reachable through...
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.
KnownFPClass computeKnownFPClass(const Value *V, const APInt &DemandedElts, const DataLayout &DL, FPClassTest InterestedClasses=fcAllFlags, unsigned Depth=0, const TargetLibraryInfo *TLI=nullptr, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Determine which floating-point classes are valid for V, and return them in KnownFPClass bit sets.
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 computeOverflowForUnsignedAdd(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT, bool UseInstrInfo=true)
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.
Represents offset+length into a ConstantDataArray.
uint64_t Length
Length of the slice.
uint64_t Offset
Slice starts at this Offset.
uint64_t operator[](unsigned I) const
Convenience accessor for elements in the slice.
void move(uint64_t Delta)
Moves the Offset and adjusts Length accordingly.
const ConstantDataArray * Array
ConstantDataArray pointer.
FPClassTest KnownFPClasses
Floating-point classes the value could be one of.
bool isKnownNeverInfinity() const
Return true if it's known this can never be an infinity.
bool cannotBeOrderedGreaterThanZero() const
Return true if we can prove that the analyzed floating-point value is either NaN or never greater tha...
static constexpr FPClassTest OrderedGreaterThanZeroMask
static constexpr FPClassTest OrderedLessThanZeroMask
void knownNot(FPClassTest RuleOut)
bool isKnownNeverZero() const
Return true if it's known this can never be a zero.
void copysign(const KnownFPClass &Sign)
bool isKnownNeverSubnormal() const
Return true if it's known this can never be a subnormal.
bool isKnownNeverLogicalNegZero(const Function &F, Type *Ty) const
Return true if it's know this can never be interpreted as a negative zero.
bool isKnownNeverLogicalPosZero(const Function &F, Type *Ty) const
Return true if it's know this can never be interpreted as a positive zero.
KnownFPClass & operator|=(const KnownFPClass &RHS)
bool isUnknown() const
bool isKnownNeverNegInfinity() const
Return true if it's known this can never be -infinity.
bool isKnownNeverNegSubnormal() const
Return true if it's known this can never be a negative subnormal.
bool isKnownNeverPosZero() const
Return true if it's known this can never be a literal positive zero.
std::optional< bool > SignBit
std::nullopt if the sign bit is unknown, true if the sign bit is definitely set or false if the sign ...
bool isKnownNeverNaN() const
Return true if it's known this can never be a nan.
bool isKnownNever(FPClassTest Mask) const
Return true if it's known this can never be one of the mask entries.
bool isKnownNeverNegZero() const
Return true if it's known this can never be a literal negative zero.
bool isKnownNeverLogicalZero(const Function &F, Type *Ty) const
Return true if it's know this can never be interpreted as a zero.
void propagateNaN(const KnownFPClass &Src, bool PreserveSign=false)
bool cannotBeOrderedLessThanZero() const
Return true if we can prove that the analyzed floating-point value is either NaN or never less than -...
void signBitMustBeZero()
Assume the sign bit is zero.
bool isKnownNeverPosInfinity() const
Return true if it's known this can never be +infinity.
bool signBitIsZeroOrNaN() const
Return true if the sign bit must be 0, ignoring the sign of nans.
bool isKnownNeverPosSubnormal() const
Return true if it's known this can never be a positive subnormal.
SelectPatternFlavor Flavor
bool Ordered
Only applicable if Flavor is SPF_FMINNUM or SPF_FMAXNUM.
static bool isMinOrMax(SelectPatternFlavor SPF)
When implementing this min/max pattern as fcmp; select, does the fcmp have to be ordered?
SelectPatternNaNBehavior NaNBehavior