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