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