10b57cec5SDimitry Andric //===- llvm/Analysis/ValueTracking.h - Walk computations --------*- C++ -*-===//
20b57cec5SDimitry Andric //
30b57cec5SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
40b57cec5SDimitry Andric // See https://llvm.org/LICENSE.txt for license information.
50b57cec5SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
60b57cec5SDimitry Andric //
70b57cec5SDimitry Andric //===----------------------------------------------------------------------===//
80b57cec5SDimitry Andric //
90b57cec5SDimitry Andric // This file contains routines that help analyze properties that chains of
100b57cec5SDimitry Andric // computations have.
110b57cec5SDimitry Andric //
120b57cec5SDimitry Andric //===----------------------------------------------------------------------===//
130b57cec5SDimitry Andric
140b57cec5SDimitry Andric #ifndef LLVM_ANALYSIS_VALUETRACKING_H
150b57cec5SDimitry Andric #define LLVM_ANALYSIS_VALUETRACKING_H
160b57cec5SDimitry Andric
170b57cec5SDimitry Andric #include "llvm/ADT/ArrayRef.h"
185f757f3fSDimitry Andric #include "llvm/Analysis/SimplifyQuery.h"
195f757f3fSDimitry Andric #include "llvm/Analysis/WithCache.h"
200b57cec5SDimitry Andric #include "llvm/IR/Constants.h"
210b57cec5SDimitry Andric #include "llvm/IR/DataLayout.h"
225f757f3fSDimitry Andric #include "llvm/IR/FMF.h"
235ffd83dbSDimitry Andric #include "llvm/IR/InstrTypes.h"
240b57cec5SDimitry Andric #include "llvm/IR/Intrinsics.h"
250b57cec5SDimitry Andric #include <cassert>
260b57cec5SDimitry Andric #include <cstdint>
270b57cec5SDimitry Andric
280b57cec5SDimitry Andric namespace llvm {
290b57cec5SDimitry Andric
3081ad6265SDimitry Andric class Operator;
310b57cec5SDimitry Andric class AddOperator;
32e8d8bef9SDimitry Andric class AllocaInst;
330b57cec5SDimitry Andric class APInt;
340b57cec5SDimitry Andric class AssumptionCache;
350b57cec5SDimitry Andric class DominatorTree;
360b57cec5SDimitry Andric class GEPOperator;
375ffd83dbSDimitry Andric class LoadInst;
380b57cec5SDimitry Andric class WithOverflowInst;
390b57cec5SDimitry Andric struct KnownBits;
400b57cec5SDimitry Andric class Loop;
410b57cec5SDimitry Andric class LoopInfo;
420b57cec5SDimitry Andric class MDNode;
430b57cec5SDimitry Andric class StringRef;
440b57cec5SDimitry Andric class TargetLibraryInfo;
450b57cec5SDimitry Andric class Value;
460b57cec5SDimitry Andric
47e8d8bef9SDimitry Andric constexpr unsigned MaxAnalysisRecursionDepth = 6;
48e8d8bef9SDimitry Andric
490b57cec5SDimitry Andric /// Determine which bits of V are known to be either zero or one and return
500b57cec5SDimitry Andric /// them in the KnownZero/KnownOne bit sets.
510b57cec5SDimitry Andric ///
520b57cec5SDimitry Andric /// This function is defined on values with integer type, values with pointer
530b57cec5SDimitry Andric /// type, and vectors of integers. In the case
540b57cec5SDimitry Andric /// where V is a vector, the known zero and known one values are the
550b57cec5SDimitry Andric /// same width as the vector element, and the bit is set only if it is true
560b57cec5SDimitry Andric /// for all of the elements in the vector.
57bdd1243dSDimitry Andric void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL,
58bdd1243dSDimitry Andric unsigned Depth = 0, AssumptionCache *AC = nullptr,
590b57cec5SDimitry Andric const Instruction *CxtI = nullptr,
600b57cec5SDimitry Andric const DominatorTree *DT = nullptr,
610b57cec5SDimitry Andric bool UseInstrInfo = true);
620b57cec5SDimitry Andric
630b57cec5SDimitry Andric /// Returns the known bits rather than passing by reference.
640b57cec5SDimitry Andric KnownBits computeKnownBits(const Value *V, const DataLayout &DL,
650b57cec5SDimitry Andric unsigned Depth = 0, AssumptionCache *AC = nullptr,
660b57cec5SDimitry Andric const Instruction *CxtI = nullptr,
670b57cec5SDimitry Andric const DominatorTree *DT = nullptr,
680b57cec5SDimitry Andric bool UseInstrInfo = true);
690b57cec5SDimitry Andric
705ffd83dbSDimitry Andric /// Returns the known bits rather than passing by reference.
715ffd83dbSDimitry Andric KnownBits computeKnownBits(const Value *V, const APInt &DemandedElts,
725ffd83dbSDimitry Andric const DataLayout &DL, unsigned Depth = 0,
735ffd83dbSDimitry Andric AssumptionCache *AC = nullptr,
745ffd83dbSDimitry Andric const Instruction *CxtI = nullptr,
755ffd83dbSDimitry Andric const DominatorTree *DT = nullptr,
765ffd83dbSDimitry Andric bool UseInstrInfo = true);
775ffd83dbSDimitry Andric
785f757f3fSDimitry Andric KnownBits computeKnownBits(const Value *V, const APInt &DemandedElts,
795f757f3fSDimitry Andric unsigned Depth, const SimplifyQuery &Q);
805f757f3fSDimitry Andric
815f757f3fSDimitry Andric KnownBits computeKnownBits(const Value *V, unsigned Depth,
825f757f3fSDimitry Andric const SimplifyQuery &Q);
835f757f3fSDimitry Andric
845f757f3fSDimitry Andric void computeKnownBits(const Value *V, KnownBits &Known, unsigned Depth,
855f757f3fSDimitry Andric const SimplifyQuery &Q);
865f757f3fSDimitry Andric
870b57cec5SDimitry Andric /// Compute known bits from the range metadata.
880b57cec5SDimitry Andric /// \p KnownZero the set of bits that are known to be zero
890b57cec5SDimitry Andric /// \p KnownOne the set of bits that are known to be one
90bdd1243dSDimitry Andric void computeKnownBitsFromRangeMetadata(const MDNode &Ranges, KnownBits &Known);
910b57cec5SDimitry Andric
925f757f3fSDimitry Andric /// Merge bits known from context-dependent facts into Known.
935f757f3fSDimitry Andric void computeKnownBitsFromContext(const Value *V, KnownBits &Known,
9406c3fb27SDimitry Andric unsigned Depth, const SimplifyQuery &Q);
9506c3fb27SDimitry Andric
9606c3fb27SDimitry Andric /// Using KnownBits LHS/RHS produce the known bits for logic op (and/xor/or).
975f757f3fSDimitry Andric KnownBits analyzeKnownBitsFromAndXorOr(const Operator *I,
985f757f3fSDimitry Andric const KnownBits &KnownLHS,
995f757f3fSDimitry Andric const KnownBits &KnownRHS,
1005f757f3fSDimitry Andric unsigned Depth, const SimplifyQuery &SQ);
10106c3fb27SDimitry Andric
1020b57cec5SDimitry Andric /// Return true if LHS and RHS have no common bits set.
1035f757f3fSDimitry Andric bool haveNoCommonBitsSet(const WithCache<const Value *> &LHSCache,
1045f757f3fSDimitry Andric const WithCache<const Value *> &RHSCache,
1055f757f3fSDimitry Andric const SimplifyQuery &SQ);
1060b57cec5SDimitry Andric
1070b57cec5SDimitry Andric /// Return true if the given value is known to have exactly one bit set when
1080b57cec5SDimitry Andric /// defined. For vectors return true if every element is known to be a power
1090b57cec5SDimitry Andric /// of two when defined. Supports values with integer or pointer type and
1100b57cec5SDimitry Andric /// vectors of integers. If 'OrZero' is set, then return true if the given
1110b57cec5SDimitry Andric /// value is either a power of two or zero.
1120b57cec5SDimitry Andric bool isKnownToBeAPowerOfTwo(const Value *V, const DataLayout &DL,
1130b57cec5SDimitry Andric bool OrZero = false, unsigned Depth = 0,
1140b57cec5SDimitry Andric AssumptionCache *AC = nullptr,
1150b57cec5SDimitry Andric const Instruction *CxtI = nullptr,
1160b57cec5SDimitry Andric const DominatorTree *DT = nullptr,
1170b57cec5SDimitry Andric bool UseInstrInfo = true);
1180b57cec5SDimitry Andric
1190b57cec5SDimitry Andric bool isOnlyUsedInZeroEqualityComparison(const Instruction *CxtI);
1200b57cec5SDimitry Andric
1210b57cec5SDimitry Andric /// Return true if the given value is known to be non-zero when defined. For
1220b57cec5SDimitry Andric /// vectors, return true if every element is known to be non-zero when
1230b57cec5SDimitry Andric /// defined. For pointers, if the context instruction and dominator tree are
1240b57cec5SDimitry Andric /// specified, perform context-sensitive analysis and return true if the
1250b57cec5SDimitry Andric /// pointer couldn't possibly be null at the specified instruction.
1260b57cec5SDimitry Andric /// Supports values with integer or pointer type and vectors of integers.
1270b57cec5SDimitry Andric bool isKnownNonZero(const Value *V, const DataLayout &DL, unsigned Depth = 0,
1280b57cec5SDimitry Andric AssumptionCache *AC = nullptr,
1290b57cec5SDimitry Andric const Instruction *CxtI = nullptr,
1300b57cec5SDimitry Andric const DominatorTree *DT = nullptr,
1310b57cec5SDimitry Andric bool UseInstrInfo = true);
1320b57cec5SDimitry Andric
1330b57cec5SDimitry Andric /// Return true if the two given values are negation.
1340b57cec5SDimitry Andric /// Currently can recoginze Value pair:
1350b57cec5SDimitry Andric /// 1: <X, Y> if X = sub (0, Y) or Y = sub (0, X)
1360b57cec5SDimitry Andric /// 2: <X, Y> if X = sub (A, B) and Y = sub (B, A)
1370b57cec5SDimitry Andric bool isKnownNegation(const Value *X, const Value *Y, bool NeedNSW = false);
1380b57cec5SDimitry Andric
1390b57cec5SDimitry Andric /// Returns true if the give value is known to be non-negative.
1405f757f3fSDimitry Andric bool isKnownNonNegative(const Value *V, const SimplifyQuery &SQ,
1415f757f3fSDimitry Andric unsigned Depth = 0);
1420b57cec5SDimitry Andric
1430b57cec5SDimitry Andric /// Returns true if the given value is known be positive (i.e. non-negative
1440b57cec5SDimitry Andric /// and non-zero).
1455f757f3fSDimitry Andric bool isKnownPositive(const Value *V, const SimplifyQuery &SQ,
1465f757f3fSDimitry Andric unsigned Depth = 0);
1470b57cec5SDimitry Andric
1480b57cec5SDimitry Andric /// Returns true if the given value is known be negative (i.e. non-positive
1490b57cec5SDimitry Andric /// and non-zero).
1505f757f3fSDimitry Andric bool isKnownNegative(const Value *V, const SimplifyQuery &DL,
1515f757f3fSDimitry Andric unsigned Depth = 0);
1520b57cec5SDimitry Andric
1530b57cec5SDimitry Andric /// Return true if the given values are known to be non-equal when defined.
1540b57cec5SDimitry Andric /// Supports scalar integer types only.
1550b57cec5SDimitry Andric bool isKnownNonEqual(const Value *V1, const Value *V2, const DataLayout &DL,
1560b57cec5SDimitry Andric AssumptionCache *AC = nullptr,
1570b57cec5SDimitry Andric const Instruction *CxtI = nullptr,
1580b57cec5SDimitry Andric const DominatorTree *DT = nullptr,
1590b57cec5SDimitry Andric bool UseInstrInfo = true);
1600b57cec5SDimitry Andric
1610b57cec5SDimitry Andric /// Return true if 'V & Mask' is known to be zero. We use this predicate to
1620b57cec5SDimitry Andric /// simplify operations downstream. Mask is known to be zero for bits that V
1630b57cec5SDimitry Andric /// cannot have.
1640b57cec5SDimitry Andric ///
1650b57cec5SDimitry Andric /// This function is defined on values with integer type, values with pointer
1660b57cec5SDimitry Andric /// type, and vectors of integers. In the case
1670b57cec5SDimitry Andric /// where V is a vector, the mask, known zero, and known one values are the
1680b57cec5SDimitry Andric /// same width as the vector element, and the bit is set only if it is true
1690b57cec5SDimitry Andric /// for all of the elements in the vector.
1705f757f3fSDimitry Andric bool MaskedValueIsZero(const Value *V, const APInt &Mask,
1715f757f3fSDimitry Andric const SimplifyQuery &DL, unsigned Depth = 0);
1720b57cec5SDimitry Andric
1730b57cec5SDimitry Andric /// Return the number of times the sign bit of the register is replicated into
1740b57cec5SDimitry Andric /// the other bits. We know that at least 1 bit is always equal to the sign
1750b57cec5SDimitry Andric /// bit (itself), but other cases can give us information. For example,
1760b57cec5SDimitry Andric /// immediately after an "ashr X, 2", we know that the top 3 bits are all
1770b57cec5SDimitry Andric /// equal to each other, so we return 3. For vectors, return the number of
1780b57cec5SDimitry Andric /// sign bits for the vector element with the mininum number of known sign
1790b57cec5SDimitry Andric /// bits.
1800b57cec5SDimitry Andric unsigned ComputeNumSignBits(const Value *Op, const DataLayout &DL,
1810b57cec5SDimitry Andric unsigned Depth = 0, AssumptionCache *AC = nullptr,
1820b57cec5SDimitry Andric const Instruction *CxtI = nullptr,
1830b57cec5SDimitry Andric const DominatorTree *DT = nullptr,
1840b57cec5SDimitry Andric bool UseInstrInfo = true);
1850b57cec5SDimitry Andric
18604eeddc0SDimitry Andric /// Get the upper bound on bit size for this Value \p Op as a signed integer.
18704eeddc0SDimitry Andric /// i.e. x == sext(trunc(x to MaxSignificantBits) to bitwidth(x)).
18804eeddc0SDimitry Andric /// Similar to the APInt::getSignificantBits function.
18904eeddc0SDimitry Andric unsigned ComputeMaxSignificantBits(const Value *Op, const DataLayout &DL,
190349cc55cSDimitry Andric unsigned Depth = 0,
191349cc55cSDimitry Andric AssumptionCache *AC = nullptr,
192349cc55cSDimitry Andric const Instruction *CxtI = nullptr,
193349cc55cSDimitry Andric const DominatorTree *DT = nullptr);
194349cc55cSDimitry Andric
1950b57cec5SDimitry Andric /// Map a call instruction to an intrinsic ID. Libcalls which have equivalent
1960b57cec5SDimitry Andric /// intrinsics are treated as-if they were intrinsics.
1975ffd83dbSDimitry Andric Intrinsic::ID getIntrinsicForCallSite(const CallBase &CB,
1980b57cec5SDimitry Andric const TargetLibraryInfo *TLI);
1990b57cec5SDimitry Andric
20006c3fb27SDimitry Andric /// Returns a pair of values, which if passed to llvm.is.fpclass, returns the
20106c3fb27SDimitry Andric /// same result as an fcmp with the given operands.
20206c3fb27SDimitry Andric ///
20306c3fb27SDimitry Andric /// If \p LookThroughSrc is true, consider the input value when computing the
20406c3fb27SDimitry Andric /// mask.
20506c3fb27SDimitry Andric ///
20606c3fb27SDimitry Andric /// If \p LookThroughSrc is false, ignore the source value (i.e. the first pair
20706c3fb27SDimitry Andric /// element will always be LHS.
20806c3fb27SDimitry Andric std::pair<Value *, FPClassTest> fcmpToClassTest(CmpInst::Predicate Pred,
20906c3fb27SDimitry Andric const Function &F, Value *LHS,
21006c3fb27SDimitry Andric Value *RHS,
21106c3fb27SDimitry Andric bool LookThroughSrc = true);
2125f757f3fSDimitry Andric std::pair<Value *, FPClassTest> fcmpToClassTest(CmpInst::Predicate Pred,
2135f757f3fSDimitry Andric const Function &F, Value *LHS,
2145f757f3fSDimitry Andric const APFloat *ConstRHS,
2155f757f3fSDimitry Andric bool LookThroughSrc = true);
21606c3fb27SDimitry Andric
21706c3fb27SDimitry Andric struct KnownFPClass {
21806c3fb27SDimitry Andric /// Floating-point classes the value could be one of.
21906c3fb27SDimitry Andric FPClassTest KnownFPClasses = fcAllFlags;
22006c3fb27SDimitry Andric
22106c3fb27SDimitry Andric /// std::nullopt if the sign bit is unknown, true if the sign bit is
22206c3fb27SDimitry Andric /// definitely set or false if the sign bit is definitely unset.
22306c3fb27SDimitry Andric std::optional<bool> SignBit;
22406c3fb27SDimitry Andric
22506c3fb27SDimitry Andric /// Return true if it's known this can never be one of the mask entries.
isKnownNeverKnownFPClass22606c3fb27SDimitry Andric bool isKnownNever(FPClassTest Mask) const {
22706c3fb27SDimitry Andric return (KnownFPClasses & Mask) == fcNone;
22806c3fb27SDimitry Andric }
22906c3fb27SDimitry Andric
isUnknownKnownFPClass23006c3fb27SDimitry Andric bool isUnknown() const {
23106c3fb27SDimitry Andric return KnownFPClasses == fcAllFlags && !SignBit;
23206c3fb27SDimitry Andric }
23306c3fb27SDimitry Andric
23406c3fb27SDimitry Andric /// Return true if it's known this can never be a nan.
isKnownNeverNaNKnownFPClass23506c3fb27SDimitry Andric bool isKnownNeverNaN() const {
23606c3fb27SDimitry Andric return isKnownNever(fcNan);
23706c3fb27SDimitry Andric }
23806c3fb27SDimitry Andric
23906c3fb27SDimitry Andric /// Return true if it's known this can never be an infinity.
isKnownNeverInfinityKnownFPClass24006c3fb27SDimitry Andric bool isKnownNeverInfinity() const {
24106c3fb27SDimitry Andric return isKnownNever(fcInf);
24206c3fb27SDimitry Andric }
24306c3fb27SDimitry Andric
24406c3fb27SDimitry Andric /// Return true if it's known this can never be +infinity.
isKnownNeverPosInfinityKnownFPClass24506c3fb27SDimitry Andric bool isKnownNeverPosInfinity() const {
24606c3fb27SDimitry Andric return isKnownNever(fcPosInf);
24706c3fb27SDimitry Andric }
24806c3fb27SDimitry Andric
24906c3fb27SDimitry Andric /// Return true if it's known this can never be -infinity.
isKnownNeverNegInfinityKnownFPClass25006c3fb27SDimitry Andric bool isKnownNeverNegInfinity() const {
25106c3fb27SDimitry Andric return isKnownNever(fcNegInf);
25206c3fb27SDimitry Andric }
25306c3fb27SDimitry Andric
25406c3fb27SDimitry Andric /// Return true if it's known this can never be a subnormal
isKnownNeverSubnormalKnownFPClass25506c3fb27SDimitry Andric bool isKnownNeverSubnormal() const {
25606c3fb27SDimitry Andric return isKnownNever(fcSubnormal);
25706c3fb27SDimitry Andric }
25806c3fb27SDimitry Andric
25906c3fb27SDimitry Andric /// Return true if it's known this can never be a positive subnormal
isKnownNeverPosSubnormalKnownFPClass26006c3fb27SDimitry Andric bool isKnownNeverPosSubnormal() const {
26106c3fb27SDimitry Andric return isKnownNever(fcPosSubnormal);
26206c3fb27SDimitry Andric }
26306c3fb27SDimitry Andric
26406c3fb27SDimitry Andric /// Return true if it's known this can never be a negative subnormal
isKnownNeverNegSubnormalKnownFPClass26506c3fb27SDimitry Andric bool isKnownNeverNegSubnormal() const {
26606c3fb27SDimitry Andric return isKnownNever(fcNegSubnormal);
26706c3fb27SDimitry Andric }
26806c3fb27SDimitry Andric
26906c3fb27SDimitry Andric /// Return true if it's known this can never be a zero. This means a literal
27006c3fb27SDimitry Andric /// [+-]0, and does not include denormal inputs implicitly treated as [+-]0.
isKnownNeverZeroKnownFPClass27106c3fb27SDimitry Andric bool isKnownNeverZero() const {
27206c3fb27SDimitry Andric return isKnownNever(fcZero);
27306c3fb27SDimitry Andric }
27406c3fb27SDimitry Andric
27506c3fb27SDimitry Andric /// Return true if it's known this can never be a literal positive zero.
isKnownNeverPosZeroKnownFPClass27606c3fb27SDimitry Andric bool isKnownNeverPosZero() const {
27706c3fb27SDimitry Andric return isKnownNever(fcPosZero);
27806c3fb27SDimitry Andric }
27906c3fb27SDimitry Andric
28006c3fb27SDimitry Andric /// Return true if it's known this can never be a negative zero. This means a
28106c3fb27SDimitry Andric /// literal -0 and does not include denormal inputs implicitly treated as -0.
isKnownNeverNegZeroKnownFPClass28206c3fb27SDimitry Andric bool isKnownNeverNegZero() const {
28306c3fb27SDimitry Andric return isKnownNever(fcNegZero);
28406c3fb27SDimitry Andric }
28506c3fb27SDimitry Andric
28606c3fb27SDimitry Andric /// Return true if it's know this can never be interpreted as a zero. This
28706c3fb27SDimitry Andric /// extends isKnownNeverZero to cover the case where the assumed
28806c3fb27SDimitry Andric /// floating-point mode for the function interprets denormals as zero.
28906c3fb27SDimitry Andric bool isKnownNeverLogicalZero(const Function &F, Type *Ty) const;
29006c3fb27SDimitry Andric
29106c3fb27SDimitry Andric /// Return true if it's know this can never be interpreted as a negative zero.
29206c3fb27SDimitry Andric bool isKnownNeverLogicalNegZero(const Function &F, Type *Ty) const;
29306c3fb27SDimitry Andric
29406c3fb27SDimitry Andric /// Return true if it's know this can never be interpreted as a positive zero.
29506c3fb27SDimitry Andric bool isKnownNeverLogicalPosZero(const Function &F, Type *Ty) const;
29606c3fb27SDimitry Andric
29706c3fb27SDimitry Andric static constexpr FPClassTest OrderedLessThanZeroMask =
29806c3fb27SDimitry Andric fcNegSubnormal | fcNegNormal | fcNegInf;
29906c3fb27SDimitry Andric static constexpr FPClassTest OrderedGreaterThanZeroMask =
30006c3fb27SDimitry Andric fcPosSubnormal | fcPosNormal | fcPosInf;
30106c3fb27SDimitry Andric
30206c3fb27SDimitry Andric /// Return true if we can prove that the analyzed floating-point value is
30306c3fb27SDimitry Andric /// either NaN or never less than -0.0.
30406c3fb27SDimitry Andric ///
30506c3fb27SDimitry Andric /// NaN --> true
30606c3fb27SDimitry Andric /// +0 --> true
30706c3fb27SDimitry Andric /// -0 --> true
30806c3fb27SDimitry Andric /// x > +0 --> true
30906c3fb27SDimitry Andric /// x < -0 --> false
cannotBeOrderedLessThanZeroKnownFPClass31006c3fb27SDimitry Andric bool cannotBeOrderedLessThanZero() const {
31106c3fb27SDimitry Andric return isKnownNever(OrderedLessThanZeroMask);
31206c3fb27SDimitry Andric }
31306c3fb27SDimitry Andric
31406c3fb27SDimitry Andric /// Return true if we can prove that the analyzed floating-point value is
31506c3fb27SDimitry Andric /// either NaN or never greater than -0.0.
31606c3fb27SDimitry Andric /// NaN --> true
31706c3fb27SDimitry Andric /// +0 --> true
31806c3fb27SDimitry Andric /// -0 --> true
31906c3fb27SDimitry Andric /// x > +0 --> false
32006c3fb27SDimitry Andric /// x < -0 --> true
cannotBeOrderedGreaterThanZeroKnownFPClass32106c3fb27SDimitry Andric bool cannotBeOrderedGreaterThanZero() const {
32206c3fb27SDimitry Andric return isKnownNever(OrderedGreaterThanZeroMask);
32306c3fb27SDimitry Andric }
32406c3fb27SDimitry Andric
32506c3fb27SDimitry Andric KnownFPClass &operator|=(const KnownFPClass &RHS) {
32606c3fb27SDimitry Andric KnownFPClasses = KnownFPClasses | RHS.KnownFPClasses;
32706c3fb27SDimitry Andric
32806c3fb27SDimitry Andric if (SignBit != RHS.SignBit)
32906c3fb27SDimitry Andric SignBit = std::nullopt;
33006c3fb27SDimitry Andric return *this;
33106c3fb27SDimitry Andric }
33206c3fb27SDimitry Andric
knownNotKnownFPClass33306c3fb27SDimitry Andric void knownNot(FPClassTest RuleOut) {
33406c3fb27SDimitry Andric KnownFPClasses = KnownFPClasses & ~RuleOut;
33506c3fb27SDimitry Andric }
33606c3fb27SDimitry Andric
fnegKnownFPClass33706c3fb27SDimitry Andric void fneg() {
33806c3fb27SDimitry Andric KnownFPClasses = llvm::fneg(KnownFPClasses);
33906c3fb27SDimitry Andric if (SignBit)
34006c3fb27SDimitry Andric SignBit = !*SignBit;
34106c3fb27SDimitry Andric }
34206c3fb27SDimitry Andric
fabsKnownFPClass34306c3fb27SDimitry Andric void fabs() {
34406c3fb27SDimitry Andric if (KnownFPClasses & fcNegZero)
34506c3fb27SDimitry Andric KnownFPClasses |= fcPosZero;
34606c3fb27SDimitry Andric
34706c3fb27SDimitry Andric if (KnownFPClasses & fcNegInf)
34806c3fb27SDimitry Andric KnownFPClasses |= fcPosInf;
34906c3fb27SDimitry Andric
35006c3fb27SDimitry Andric if (KnownFPClasses & fcNegSubnormal)
35106c3fb27SDimitry Andric KnownFPClasses |= fcPosSubnormal;
35206c3fb27SDimitry Andric
35306c3fb27SDimitry Andric if (KnownFPClasses & fcNegNormal)
35406c3fb27SDimitry Andric KnownFPClasses |= fcPosNormal;
35506c3fb27SDimitry Andric
35606c3fb27SDimitry Andric signBitMustBeZero();
35706c3fb27SDimitry Andric }
35806c3fb27SDimitry Andric
35906c3fb27SDimitry Andric /// Return true if the sign bit must be 0, ignoring the sign of nans.
signBitIsZeroOrNaNKnownFPClass36006c3fb27SDimitry Andric bool signBitIsZeroOrNaN() const {
36106c3fb27SDimitry Andric return isKnownNever(fcNegative);
36206c3fb27SDimitry Andric }
36306c3fb27SDimitry Andric
36406c3fb27SDimitry Andric /// Assume the sign bit is zero.
signBitMustBeZeroKnownFPClass36506c3fb27SDimitry Andric void signBitMustBeZero() {
36606c3fb27SDimitry Andric KnownFPClasses &= (fcPositive | fcNan);
36706c3fb27SDimitry Andric SignBit = false;
36806c3fb27SDimitry Andric }
36906c3fb27SDimitry Andric
copysignKnownFPClass37006c3fb27SDimitry Andric void copysign(const KnownFPClass &Sign) {
37106c3fb27SDimitry Andric // Don't know anything about the sign of the source. Expand the possible set
37206c3fb27SDimitry Andric // to its opposite sign pair.
37306c3fb27SDimitry Andric if (KnownFPClasses & fcZero)
37406c3fb27SDimitry Andric KnownFPClasses |= fcZero;
37506c3fb27SDimitry Andric if (KnownFPClasses & fcSubnormal)
37606c3fb27SDimitry Andric KnownFPClasses |= fcSubnormal;
37706c3fb27SDimitry Andric if (KnownFPClasses & fcNormal)
37806c3fb27SDimitry Andric KnownFPClasses |= fcNormal;
37906c3fb27SDimitry Andric if (KnownFPClasses & fcInf)
38006c3fb27SDimitry Andric KnownFPClasses |= fcInf;
38106c3fb27SDimitry Andric
38206c3fb27SDimitry Andric // Sign bit is exactly preserved even for nans.
38306c3fb27SDimitry Andric SignBit = Sign.SignBit;
38406c3fb27SDimitry Andric
38506c3fb27SDimitry Andric // Clear sign bits based on the input sign mask.
38606c3fb27SDimitry Andric if (Sign.isKnownNever(fcPositive | fcNan) || (SignBit && *SignBit))
38706c3fb27SDimitry Andric KnownFPClasses &= (fcNegative | fcNan);
38806c3fb27SDimitry Andric if (Sign.isKnownNever(fcNegative | fcNan) || (SignBit && !*SignBit))
38906c3fb27SDimitry Andric KnownFPClasses &= (fcPositive | fcNan);
39006c3fb27SDimitry Andric }
39106c3fb27SDimitry Andric
39206c3fb27SDimitry Andric // Propagate knowledge that a non-NaN source implies the result can also not
39306c3fb27SDimitry Andric // be a NaN. For unconstrained operations, signaling nans are not guaranteed
39406c3fb27SDimitry Andric // to be quieted but cannot be introduced.
39506c3fb27SDimitry Andric void propagateNaN(const KnownFPClass &Src, bool PreserveSign = false) {
39606c3fb27SDimitry Andric if (Src.isKnownNever(fcNan)) {
39706c3fb27SDimitry Andric knownNot(fcNan);
39806c3fb27SDimitry Andric if (PreserveSign)
39906c3fb27SDimitry Andric SignBit = Src.SignBit;
40006c3fb27SDimitry Andric } else if (Src.isKnownNever(fcSNan))
40106c3fb27SDimitry Andric knownNot(fcSNan);
40206c3fb27SDimitry Andric }
40306c3fb27SDimitry Andric
40406c3fb27SDimitry Andric /// Propagate knowledge from a source value that could be a denormal or
40506c3fb27SDimitry Andric /// zero. We have to be conservative since output flushing is not guaranteed,
40606c3fb27SDimitry Andric /// so known-never-zero may not hold.
40706c3fb27SDimitry Andric ///
40806c3fb27SDimitry Andric /// This assumes a copy-like operation and will replace any currently known
40906c3fb27SDimitry Andric /// information.
41006c3fb27SDimitry Andric void propagateDenormal(const KnownFPClass &Src, const Function &F, Type *Ty);
41106c3fb27SDimitry Andric
41206c3fb27SDimitry Andric /// Report known classes if \p Src is evaluated through a potentially
41306c3fb27SDimitry Andric /// canonicalizing operation. We can assume signaling nans will not be
41406c3fb27SDimitry Andric /// introduced, but cannot assume a denormal will be flushed under FTZ/DAZ.
41506c3fb27SDimitry Andric ///
41606c3fb27SDimitry Andric /// This assumes a copy-like operation and will replace any currently known
41706c3fb27SDimitry Andric /// information.
41806c3fb27SDimitry Andric void propagateCanonicalizingSrc(const KnownFPClass &Src, const Function &F,
41906c3fb27SDimitry Andric Type *Ty);
42006c3fb27SDimitry Andric
resetAllKnownFPClass42106c3fb27SDimitry Andric void resetAll() { *this = KnownFPClass(); }
42206c3fb27SDimitry Andric };
42306c3fb27SDimitry Andric
42406c3fb27SDimitry Andric inline KnownFPClass operator|(KnownFPClass LHS, const KnownFPClass &RHS) {
42506c3fb27SDimitry Andric LHS |= RHS;
42606c3fb27SDimitry Andric return LHS;
42706c3fb27SDimitry Andric }
42806c3fb27SDimitry Andric
42906c3fb27SDimitry Andric inline KnownFPClass operator|(const KnownFPClass &LHS, KnownFPClass &&RHS) {
43006c3fb27SDimitry Andric RHS |= LHS;
43106c3fb27SDimitry Andric return std::move(RHS);
43206c3fb27SDimitry Andric }
43306c3fb27SDimitry Andric
43406c3fb27SDimitry Andric /// Determine which floating-point classes are valid for \p V, and return them
43506c3fb27SDimitry Andric /// in KnownFPClass bit sets.
43606c3fb27SDimitry Andric ///
43706c3fb27SDimitry Andric /// This function is defined on values with floating-point type, values vectors
43806c3fb27SDimitry Andric /// of floating-point type, and arrays of floating-point type.
43906c3fb27SDimitry Andric
44006c3fb27SDimitry Andric /// \p InterestedClasses is a compile time optimization hint for which floating
44106c3fb27SDimitry Andric /// point classes should be queried. Queries not specified in \p
44206c3fb27SDimitry Andric /// InterestedClasses should be reliable if they are determined during the
44306c3fb27SDimitry Andric /// query.
44406c3fb27SDimitry Andric KnownFPClass computeKnownFPClass(
44506c3fb27SDimitry Andric const Value *V, const APInt &DemandedElts, const DataLayout &DL,
44606c3fb27SDimitry Andric FPClassTest InterestedClasses = fcAllFlags, unsigned Depth = 0,
44706c3fb27SDimitry Andric const TargetLibraryInfo *TLI = nullptr, AssumptionCache *AC = nullptr,
44806c3fb27SDimitry Andric const Instruction *CxtI = nullptr, const DominatorTree *DT = nullptr,
44906c3fb27SDimitry Andric bool UseInstrInfo = true);
45006c3fb27SDimitry Andric
45106c3fb27SDimitry Andric KnownFPClass computeKnownFPClass(
45206c3fb27SDimitry Andric const Value *V, const DataLayout &DL,
45306c3fb27SDimitry Andric FPClassTest InterestedClasses = fcAllFlags, unsigned Depth = 0,
45406c3fb27SDimitry Andric const TargetLibraryInfo *TLI = nullptr, AssumptionCache *AC = nullptr,
45506c3fb27SDimitry Andric const Instruction *CxtI = nullptr, const DominatorTree *DT = nullptr,
45606c3fb27SDimitry Andric bool UseInstrInfo = true);
45706c3fb27SDimitry Andric
4585f757f3fSDimitry Andric /// Wrapper to account for known fast math flags at the use instruction.
4595f757f3fSDimitry Andric inline KnownFPClass computeKnownFPClass(
4605f757f3fSDimitry Andric const Value *V, FastMathFlags FMF, const DataLayout &DL,
4615f757f3fSDimitry Andric FPClassTest InterestedClasses = fcAllFlags, unsigned Depth = 0,
4625f757f3fSDimitry Andric const TargetLibraryInfo *TLI = nullptr, AssumptionCache *AC = nullptr,
4635f757f3fSDimitry Andric const Instruction *CxtI = nullptr, const DominatorTree *DT = nullptr,
4645f757f3fSDimitry Andric bool UseInstrInfo = true) {
4655f757f3fSDimitry Andric if (FMF.noNaNs())
4665f757f3fSDimitry Andric InterestedClasses &= ~fcNan;
4675f757f3fSDimitry Andric if (FMF.noInfs())
4685f757f3fSDimitry Andric InterestedClasses &= ~fcInf;
4695f757f3fSDimitry Andric
4705f757f3fSDimitry Andric KnownFPClass Result = computeKnownFPClass(V, DL, InterestedClasses, Depth,
4715f757f3fSDimitry Andric TLI, AC, CxtI, DT, UseInstrInfo);
4725f757f3fSDimitry Andric
4735f757f3fSDimitry Andric if (FMF.noNaNs())
4745f757f3fSDimitry Andric Result.KnownFPClasses &= ~fcNan;
4755f757f3fSDimitry Andric if (FMF.noInfs())
4765f757f3fSDimitry Andric Result.KnownFPClasses &= ~fcInf;
4775f757f3fSDimitry Andric return Result;
4785f757f3fSDimitry Andric }
4795f757f3fSDimitry Andric
4800b57cec5SDimitry Andric /// Return true if we can prove that the specified FP value is never equal to
48106c3fb27SDimitry Andric /// -0.0. Users should use caution when considering PreserveSign
48206c3fb27SDimitry Andric /// denormal-fp-math.
48306c3fb27SDimitry Andric inline bool cannotBeNegativeZero(const Value *V, const DataLayout &DL,
48406c3fb27SDimitry Andric const TargetLibraryInfo *TLI = nullptr,
48506c3fb27SDimitry Andric unsigned Depth = 0,
48606c3fb27SDimitry Andric AssumptionCache *AC = nullptr,
48706c3fb27SDimitry Andric const Instruction *CtxI = nullptr,
48806c3fb27SDimitry Andric const DominatorTree *DT = nullptr,
48906c3fb27SDimitry Andric bool UseInstrInfo = true) {
49006c3fb27SDimitry Andric KnownFPClass Known = computeKnownFPClass(V, DL, fcNegZero, Depth, TLI, AC,
49106c3fb27SDimitry Andric CtxI, DT, UseInstrInfo);
49206c3fb27SDimitry Andric return Known.isKnownNeverNegZero();
49306c3fb27SDimitry Andric }
49406c3fb27SDimitry Andric
4950b57cec5SDimitry Andric /// Return true if we can prove that the specified FP value is either NaN or
4960b57cec5SDimitry Andric /// never less than -0.0.
4970b57cec5SDimitry Andric ///
4980b57cec5SDimitry Andric /// NaN --> true
4990b57cec5SDimitry Andric /// +0 --> true
5000b57cec5SDimitry Andric /// -0 --> true
5010b57cec5SDimitry Andric /// x > +0 --> true
5020b57cec5SDimitry Andric /// x < -0 --> false
50306c3fb27SDimitry Andric inline bool cannotBeOrderedLessThanZero(const Value *V, const DataLayout &DL,
50406c3fb27SDimitry Andric const TargetLibraryInfo *TLI = nullptr,
50506c3fb27SDimitry Andric unsigned Depth = 0,
50606c3fb27SDimitry Andric AssumptionCache *AC = nullptr,
50706c3fb27SDimitry Andric const Instruction *CtxI = nullptr,
50806c3fb27SDimitry Andric const DominatorTree *DT = nullptr,
50906c3fb27SDimitry Andric bool UseInstrInfo = true) {
51006c3fb27SDimitry Andric KnownFPClass Known =
51106c3fb27SDimitry Andric computeKnownFPClass(V, DL, KnownFPClass::OrderedLessThanZeroMask, Depth,
51206c3fb27SDimitry Andric TLI, AC, CtxI, DT, UseInstrInfo);
51306c3fb27SDimitry Andric return Known.cannotBeOrderedLessThanZero();
51406c3fb27SDimitry Andric }
5150b57cec5SDimitry Andric
516480093f4SDimitry Andric /// Return true if the floating-point scalar value is not an infinity or if
517480093f4SDimitry Andric /// the floating-point vector value has no infinities. Return false if a value
518480093f4SDimitry Andric /// could ever be infinity.
51906c3fb27SDimitry Andric inline bool isKnownNeverInfinity(const Value *V, const DataLayout &DL,
52006c3fb27SDimitry Andric const TargetLibraryInfo *TLI = nullptr,
52106c3fb27SDimitry Andric unsigned Depth = 0,
52206c3fb27SDimitry Andric AssumptionCache *AC = nullptr,
52306c3fb27SDimitry Andric const Instruction *CtxI = nullptr,
52406c3fb27SDimitry Andric const DominatorTree *DT = nullptr,
52506c3fb27SDimitry Andric bool UseInstrInfo = true) {
52606c3fb27SDimitry Andric KnownFPClass Known = computeKnownFPClass(V, DL, fcInf, Depth, TLI, AC, CtxI,
52706c3fb27SDimitry Andric DT, UseInstrInfo);
52806c3fb27SDimitry Andric return Known.isKnownNeverInfinity();
52906c3fb27SDimitry Andric }
53006c3fb27SDimitry Andric
53106c3fb27SDimitry Andric /// Return true if the floating-point value can never contain a NaN or infinity.
53206c3fb27SDimitry Andric inline bool isKnownNeverInfOrNaN(
53306c3fb27SDimitry Andric const Value *V, const DataLayout &DL, const TargetLibraryInfo *TLI,
53406c3fb27SDimitry Andric unsigned Depth = 0, AssumptionCache *AC = nullptr,
53506c3fb27SDimitry Andric const Instruction *CtxI = nullptr, const DominatorTree *DT = nullptr,
53606c3fb27SDimitry Andric bool UseInstrInfo = true) {
53706c3fb27SDimitry Andric KnownFPClass Known = computeKnownFPClass(V, DL, fcInf | fcNan, Depth, TLI, AC,
53806c3fb27SDimitry Andric CtxI, DT, UseInstrInfo);
53906c3fb27SDimitry Andric return Known.isKnownNeverNaN() && Known.isKnownNeverInfinity();
54006c3fb27SDimitry Andric }
541480093f4SDimitry Andric
5420b57cec5SDimitry Andric /// Return true if the floating-point scalar value is not a NaN or if the
5430b57cec5SDimitry Andric /// floating-point vector value has no NaN elements. Return false if a value
5440b57cec5SDimitry Andric /// could ever be NaN.
54506c3fb27SDimitry Andric inline bool isKnownNeverNaN(const Value *V, const DataLayout &DL,
54606c3fb27SDimitry Andric const TargetLibraryInfo *TLI, unsigned Depth = 0,
54706c3fb27SDimitry Andric AssumptionCache *AC = nullptr,
54806c3fb27SDimitry Andric const Instruction *CtxI = nullptr,
54906c3fb27SDimitry Andric const DominatorTree *DT = nullptr,
55006c3fb27SDimitry Andric bool UseInstrInfo = true) {
55106c3fb27SDimitry Andric KnownFPClass Known = computeKnownFPClass(V, DL, fcNan, Depth, TLI, AC, CtxI,
55206c3fb27SDimitry Andric DT, UseInstrInfo);
55306c3fb27SDimitry Andric return Known.isKnownNeverNaN();
55406c3fb27SDimitry Andric }
5550b57cec5SDimitry Andric
5560b57cec5SDimitry Andric /// Return true if we can prove that the specified FP value's sign bit is 0.
5570b57cec5SDimitry Andric ///
5580b57cec5SDimitry Andric /// NaN --> true/false (depending on the NaN's sign bit)
5590b57cec5SDimitry Andric /// +0 --> true
5600b57cec5SDimitry Andric /// -0 --> false
5610b57cec5SDimitry Andric /// x > +0 --> true
5620b57cec5SDimitry Andric /// x < -0 --> false
56306c3fb27SDimitry Andric bool SignBitMustBeZero(const Value *V, const DataLayout &DL,
56406c3fb27SDimitry Andric const TargetLibraryInfo *TLI);
5650b57cec5SDimitry Andric
5660b57cec5SDimitry Andric /// If the specified value can be set by repeating the same byte in memory,
5670b57cec5SDimitry Andric /// return the i8 value that it is represented with. This is true for all i8
5680b57cec5SDimitry Andric /// values obviously, but is also true for i32 0, i32 -1, i16 0xF0F0, double
5690b57cec5SDimitry Andric /// 0.0 etc. If the value can't be handled with a repeated byte store (e.g.
5700b57cec5SDimitry Andric /// i16 0x1234), return null. If the value is entirely undef and padding,
5710b57cec5SDimitry Andric /// return undef.
5720b57cec5SDimitry Andric Value *isBytewiseValue(Value *V, const DataLayout &DL);
5730b57cec5SDimitry Andric
574480093f4SDimitry Andric /// Given an aggregate and an sequence of indices, see if the scalar value
5750b57cec5SDimitry Andric /// indexed is already around as a register, for example if it were inserted
576480093f4SDimitry Andric /// directly into the aggregate.
5770b57cec5SDimitry Andric ///
5780b57cec5SDimitry Andric /// If InsertBefore is not null, this function will duplicate (modified)
5790b57cec5SDimitry Andric /// insertvalues when a part of a nested struct is extracted.
580bdd1243dSDimitry Andric Value *FindInsertedValue(Value *V, ArrayRef<unsigned> idx_range,
5810b57cec5SDimitry Andric Instruction *InsertBefore = nullptr);
5820b57cec5SDimitry Andric
5830b57cec5SDimitry Andric /// Analyze the specified pointer to see if it can be expressed as a base
5840b57cec5SDimitry Andric /// pointer plus a constant offset. Return the base and offset to the caller.
5850b57cec5SDimitry Andric ///
5860b57cec5SDimitry Andric /// This is a wrapper around Value::stripAndAccumulateConstantOffsets that
5870b57cec5SDimitry Andric /// creates and later unpacks the required APInt.
5880b57cec5SDimitry Andric inline Value *GetPointerBaseWithConstantOffset(Value *Ptr, int64_t &Offset,
5898bcb0991SDimitry Andric const DataLayout &DL,
5908bcb0991SDimitry Andric bool AllowNonInbounds = true) {
5910b57cec5SDimitry Andric APInt OffsetAPInt(DL.getIndexTypeSizeInBits(Ptr->getType()), 0);
5920b57cec5SDimitry Andric Value *Base =
5938bcb0991SDimitry Andric Ptr->stripAndAccumulateConstantOffsets(DL, OffsetAPInt, AllowNonInbounds);
5948bcb0991SDimitry Andric
5950b57cec5SDimitry Andric Offset = OffsetAPInt.getSExtValue();
5960b57cec5SDimitry Andric return Base;
5970b57cec5SDimitry Andric }
5988bcb0991SDimitry Andric inline const Value *
5998bcb0991SDimitry Andric GetPointerBaseWithConstantOffset(const Value *Ptr, int64_t &Offset,
6008bcb0991SDimitry Andric const DataLayout &DL,
6018bcb0991SDimitry Andric bool AllowNonInbounds = true) {
6028bcb0991SDimitry Andric return GetPointerBaseWithConstantOffset(const_cast<Value *>(Ptr), Offset, DL,
6038bcb0991SDimitry Andric AllowNonInbounds);
6040b57cec5SDimitry Andric }
6050b57cec5SDimitry Andric
6060b57cec5SDimitry Andric /// Returns true if the GEP is based on a pointer to a string (array of
6070b57cec5SDimitry Andric // \p CharSize integers) and is indexing into this string.
608bdd1243dSDimitry Andric bool isGEPBasedOnPointerToString(const GEPOperator *GEP, unsigned CharSize = 8);
6090b57cec5SDimitry Andric
6100b57cec5SDimitry Andric /// Represents offset+length into a ConstantDataArray.
6110b57cec5SDimitry Andric struct ConstantDataArraySlice {
6120b57cec5SDimitry Andric /// ConstantDataArray pointer. nullptr indicates a zeroinitializer (a valid
6130b57cec5SDimitry Andric /// initializer, it just doesn't fit the ConstantDataArray interface).
6140b57cec5SDimitry Andric const ConstantDataArray *Array;
6150b57cec5SDimitry Andric
6160b57cec5SDimitry Andric /// Slice starts at this Offset.
6170b57cec5SDimitry Andric uint64_t Offset;
6180b57cec5SDimitry Andric
6190b57cec5SDimitry Andric /// Length of the slice.
6200b57cec5SDimitry Andric uint64_t Length;
6210b57cec5SDimitry Andric
6220b57cec5SDimitry Andric /// Moves the Offset and adjusts Length accordingly.
moveConstantDataArraySlice6230b57cec5SDimitry Andric void move(uint64_t Delta) {
6240b57cec5SDimitry Andric assert(Delta < Length);
6250b57cec5SDimitry Andric Offset += Delta;
6260b57cec5SDimitry Andric Length -= Delta;
6270b57cec5SDimitry Andric }
6280b57cec5SDimitry Andric
6290b57cec5SDimitry Andric /// Convenience accessor for elements in the slice.
6300b57cec5SDimitry Andric uint64_t operator[](unsigned I) const {
6310b57cec5SDimitry Andric return Array == nullptr ? 0 : Array->getElementAsInteger(I + Offset);
6320b57cec5SDimitry Andric }
6330b57cec5SDimitry Andric };
6340b57cec5SDimitry Andric
6350b57cec5SDimitry Andric /// Returns true if the value \p V is a pointer into a ConstantDataArray.
6360b57cec5SDimitry Andric /// If successful \p Slice will point to a ConstantDataArray info object
6370b57cec5SDimitry Andric /// with an appropriate offset.
6380b57cec5SDimitry Andric bool getConstantDataArrayInfo(const Value *V, ConstantDataArraySlice &Slice,
6390b57cec5SDimitry Andric unsigned ElementSize, uint64_t Offset = 0);
6400b57cec5SDimitry Andric
6410b57cec5SDimitry Andric /// This function computes the length of a null-terminated C string pointed to
6420b57cec5SDimitry Andric /// by V. If successful, it returns true and returns the string in Str. If
6430b57cec5SDimitry Andric /// unsuccessful, it returns false. This does not include the trailing null
6440b57cec5SDimitry Andric /// character by default. If TrimAtNul is set to false, then this returns any
6450b57cec5SDimitry Andric /// trailing null characters as well as any other characters that come after
6460b57cec5SDimitry Andric /// it.
6470b57cec5SDimitry Andric bool getConstantStringInfo(const Value *V, StringRef &Str,
648bdd1243dSDimitry Andric bool TrimAtNul = true);
6490b57cec5SDimitry Andric
6500b57cec5SDimitry Andric /// If we can compute the length of the string pointed to by the specified
6510b57cec5SDimitry Andric /// pointer, return 'len+1'. If we can't, return 0.
6520b57cec5SDimitry Andric uint64_t GetStringLength(const Value *V, unsigned CharSize = 8);
6530b57cec5SDimitry Andric
6540b57cec5SDimitry Andric /// This function returns call pointer argument that is considered the same by
6558bcb0991SDimitry Andric /// aliasing rules. You CAN'T use it to replace one value with another. If
6568bcb0991SDimitry Andric /// \p MustPreserveNullness is true, the call must preserve the nullness of
6578bcb0991SDimitry Andric /// the pointer.
6588bcb0991SDimitry Andric const Value *getArgumentAliasingToReturnedPointer(const CallBase *Call,
6598bcb0991SDimitry Andric bool MustPreserveNullness);
getArgumentAliasingToReturnedPointer(CallBase * Call,bool MustPreserveNullness)660bdd1243dSDimitry Andric inline Value *getArgumentAliasingToReturnedPointer(CallBase *Call,
6618bcb0991SDimitry Andric bool MustPreserveNullness) {
6620b57cec5SDimitry Andric return const_cast<Value *>(getArgumentAliasingToReturnedPointer(
6638bcb0991SDimitry Andric const_cast<const CallBase *>(Call), MustPreserveNullness));
6640b57cec5SDimitry Andric }
6650b57cec5SDimitry Andric
6668bcb0991SDimitry Andric /// {launder,strip}.invariant.group returns pointer that aliases its argument,
6678bcb0991SDimitry Andric /// and it only captures pointer by returning it.
6688bcb0991SDimitry Andric /// These intrinsics are not marked as nocapture, because returning is
6698bcb0991SDimitry Andric /// considered as capture. The arguments are not marked as returned neither,
6708bcb0991SDimitry Andric /// because it would make it useless. If \p MustPreserveNullness is true,
6718bcb0991SDimitry Andric /// the intrinsic must preserve the nullness of the pointer.
6720b57cec5SDimitry Andric bool isIntrinsicReturningPointerAliasingArgumentWithoutCapturing(
6738bcb0991SDimitry Andric const CallBase *Call, bool MustPreserveNullness);
6740b57cec5SDimitry Andric
6750b57cec5SDimitry Andric /// This method strips off any GEP address adjustments and pointer casts from
6760b57cec5SDimitry Andric /// the specified value, returning the original object being addressed. Note
6770b57cec5SDimitry Andric /// that the returned value has pointer type if the specified value does. If
6780b57cec5SDimitry Andric /// the MaxLookup value is non-zero, it limits the number of instructions to
6790b57cec5SDimitry Andric /// be stripped off.
680fe6060f1SDimitry Andric const Value *getUnderlyingObject(const Value *V, unsigned MaxLookup = 6);
681fe6060f1SDimitry Andric inline Value *getUnderlyingObject(Value *V, unsigned MaxLookup = 6) {
682fe6060f1SDimitry Andric // Force const to avoid infinite recursion.
683fe6060f1SDimitry Andric const Value *VConst = V;
684fe6060f1SDimitry Andric return const_cast<Value *>(getUnderlyingObject(VConst, MaxLookup));
6850b57cec5SDimitry Andric }
6860b57cec5SDimitry Andric
687e8d8bef9SDimitry Andric /// This method is similar to getUnderlyingObject except that it can
6880b57cec5SDimitry Andric /// look through phi and select instructions and return multiple objects.
6890b57cec5SDimitry Andric ///
6900b57cec5SDimitry Andric /// If LoopInfo is passed, loop phis are further analyzed. If a pointer
6910b57cec5SDimitry Andric /// accesses different objects in each iteration, we don't look through the
6920b57cec5SDimitry Andric /// phi node. E.g. consider this loop nest:
6930b57cec5SDimitry Andric ///
6940b57cec5SDimitry Andric /// int **A;
6950b57cec5SDimitry Andric /// for (i)
6960b57cec5SDimitry Andric /// for (j) {
6970b57cec5SDimitry Andric /// A[i][j] = A[i-1][j] * B[j]
6980b57cec5SDimitry Andric /// }
6990b57cec5SDimitry Andric ///
7000b57cec5SDimitry Andric /// This is transformed by Load-PRE to stash away A[i] for the next iteration
7010b57cec5SDimitry Andric /// of the outer loop:
7020b57cec5SDimitry Andric ///
7030b57cec5SDimitry Andric /// Curr = A[0]; // Prev_0
7040b57cec5SDimitry Andric /// for (i: 1..N) {
7050b57cec5SDimitry Andric /// Prev = Curr; // Prev = PHI (Prev_0, Curr)
7060b57cec5SDimitry Andric /// Curr = A[i];
7070b57cec5SDimitry Andric /// for (j: 0..N) {
7080b57cec5SDimitry Andric /// Curr[j] = Prev[j] * B[j]
7090b57cec5SDimitry Andric /// }
7100b57cec5SDimitry Andric /// }
7110b57cec5SDimitry Andric ///
7120b57cec5SDimitry Andric /// Since A[i] and A[i-1] are independent pointers, getUnderlyingObjects
7130b57cec5SDimitry Andric /// should not assume that Curr and Prev share the same underlying object thus
7140b57cec5SDimitry Andric /// it shouldn't look through the phi above.
715e8d8bef9SDimitry Andric void getUnderlyingObjects(const Value *V,
7160b57cec5SDimitry Andric SmallVectorImpl<const Value *> &Objects,
717e8d8bef9SDimitry Andric LoopInfo *LI = nullptr, unsigned MaxLookup = 6);
7180b57cec5SDimitry Andric
719e8d8bef9SDimitry Andric /// This is a wrapper around getUnderlyingObjects and adds support for basic
7200b57cec5SDimitry Andric /// ptrtoint+arithmetic+inttoptr sequences.
7210b57cec5SDimitry Andric bool getUnderlyingObjectsForCodeGen(const Value *V,
722e8d8bef9SDimitry Andric SmallVectorImpl<Value *> &Objects);
723e8d8bef9SDimitry Andric
724e8d8bef9SDimitry Andric /// Returns unique alloca where the value comes from, or nullptr.
725e8d8bef9SDimitry Andric /// If OffsetZero is true check that V points to the begining of the alloca.
726e8d8bef9SDimitry Andric AllocaInst *findAllocaForValue(Value *V, bool OffsetZero = false);
727e8d8bef9SDimitry Andric inline const AllocaInst *findAllocaForValue(const Value *V,
728e8d8bef9SDimitry Andric bool OffsetZero = false) {
729e8d8bef9SDimitry Andric return findAllocaForValue(const_cast<Value *>(V), OffsetZero);
730e8d8bef9SDimitry Andric }
7310b57cec5SDimitry Andric
7320b57cec5SDimitry Andric /// Return true if the only users of this pointer are lifetime markers.
7330b57cec5SDimitry Andric bool onlyUsedByLifetimeMarkers(const Value *V);
7340b57cec5SDimitry Andric
735e8d8bef9SDimitry Andric /// Return true if the only users of this pointer are lifetime markers or
736e8d8bef9SDimitry Andric /// droppable instructions.
737e8d8bef9SDimitry Andric bool onlyUsedByLifetimeMarkersOrDroppableInsts(const Value *V);
738e8d8bef9SDimitry Andric
7398bcb0991SDimitry Andric /// Return true if speculation of the given load must be suppressed to avoid
7408bcb0991SDimitry Andric /// ordering or interfering with an active sanitizer. If not suppressed,
7418bcb0991SDimitry Andric /// dereferenceability and alignment must be proven separately. Note: This
7428bcb0991SDimitry Andric /// is only needed for raw reasoning; if you use the interface below
7438bcb0991SDimitry Andric /// (isSafeToSpeculativelyExecute), this is handled internally.
7448bcb0991SDimitry Andric bool mustSuppressSpeculation(const LoadInst &LI);
7458bcb0991SDimitry Andric
7460b57cec5SDimitry Andric /// Return true if the instruction does not have any effects besides
7470b57cec5SDimitry Andric /// calculating the result and does not have undefined behavior.
7480b57cec5SDimitry Andric ///
7490b57cec5SDimitry Andric /// This method never returns true for an instruction that returns true for
7500b57cec5SDimitry Andric /// mayHaveSideEffects; however, this method also does some other checks in
7510b57cec5SDimitry Andric /// addition. It checks for undefined behavior, like dividing by zero or
7520b57cec5SDimitry Andric /// loading from an invalid pointer (but not for undefined results, like a
7530b57cec5SDimitry Andric /// shift with a shift amount larger than the width of the result). It checks
7540b57cec5SDimitry Andric /// for malloc and alloca because speculatively executing them might cause a
7550b57cec5SDimitry Andric /// memory leak. It also returns false for instructions related to control
7560b57cec5SDimitry Andric /// flow, specifically terminators and PHI nodes.
7570b57cec5SDimitry Andric ///
7580b57cec5SDimitry Andric /// If the CtxI is specified this method performs context-sensitive analysis
7590b57cec5SDimitry Andric /// and returns true if it is safe to execute the instruction immediately
7600b57cec5SDimitry Andric /// before the CtxI.
7610b57cec5SDimitry Andric ///
7620b57cec5SDimitry Andric /// If the CtxI is NOT specified this method only looks at the instruction
7630b57cec5SDimitry Andric /// itself and its operands, so if this method returns true, it is safe to
7640b57cec5SDimitry Andric /// move the instruction as long as the correct dominance relationships for
7650b57cec5SDimitry Andric /// the operands and users hold.
7660b57cec5SDimitry Andric ///
7670b57cec5SDimitry Andric /// This method can return true for instructions that read memory;
7680b57cec5SDimitry Andric /// for such instructions, moving them may change the resulting value.
769753f127fSDimitry Andric bool isSafeToSpeculativelyExecute(const Instruction *I,
7700b57cec5SDimitry Andric const Instruction *CtxI = nullptr,
771bdd1243dSDimitry Andric AssumptionCache *AC = nullptr,
772fe6060f1SDimitry Andric const DominatorTree *DT = nullptr,
773fe6060f1SDimitry Andric const TargetLibraryInfo *TLI = nullptr);
7740b57cec5SDimitry Andric
77581ad6265SDimitry Andric /// This returns the same result as isSafeToSpeculativelyExecute if Opcode is
77681ad6265SDimitry Andric /// the actual opcode of Inst. If the provided and actual opcode differ, the
77781ad6265SDimitry Andric /// function (virtually) overrides the opcode of Inst with the provided
77881ad6265SDimitry Andric /// Opcode. There are come constraints in this case:
77981ad6265SDimitry Andric /// * If Opcode has a fixed number of operands (eg, as binary operators do),
78081ad6265SDimitry Andric /// then Inst has to have at least as many leading operands. The function
78181ad6265SDimitry Andric /// will ignore all trailing operands beyond that number.
78281ad6265SDimitry Andric /// * If Opcode allows for an arbitrary number of operands (eg, as CallInsts
78381ad6265SDimitry Andric /// do), then all operands are considered.
78481ad6265SDimitry Andric /// * The virtual instruction has to satisfy all typing rules of the provided
78581ad6265SDimitry Andric /// Opcode.
78681ad6265SDimitry Andric /// * This function is pessimistic in the following sense: If one actually
78781ad6265SDimitry Andric /// materialized the virtual instruction, then isSafeToSpeculativelyExecute
78881ad6265SDimitry Andric /// may say that the materialized instruction is speculatable whereas this
78981ad6265SDimitry Andric /// function may have said that the instruction wouldn't be speculatable.
79081ad6265SDimitry Andric /// This behavior is a shortcoming in the current implementation and not
79181ad6265SDimitry Andric /// intentional.
79281ad6265SDimitry Andric bool isSafeToSpeculativelyExecuteWithOpcode(
793bdd1243dSDimitry Andric unsigned Opcode, const Instruction *Inst, const Instruction *CtxI = nullptr,
794bdd1243dSDimitry Andric AssumptionCache *AC = nullptr, const DominatorTree *DT = nullptr,
79581ad6265SDimitry Andric const TargetLibraryInfo *TLI = nullptr);
79681ad6265SDimitry Andric
7970b57cec5SDimitry Andric /// Returns true if the result or effects of the given instructions \p I
79881ad6265SDimitry Andric /// depend values not reachable through the def use graph.
79981ad6265SDimitry Andric /// * Memory dependence arises for example if the instruction reads from
8000b57cec5SDimitry Andric /// memory or may produce effects or undefined behaviour. Memory dependent
8010b57cec5SDimitry Andric /// instructions generally cannot be reorderd with respect to other memory
80281ad6265SDimitry Andric /// dependent instructions.
80381ad6265SDimitry Andric /// * Control dependence arises for example if the instruction may fault
80481ad6265SDimitry Andric /// if lifted above a throwing call or infinite loop.
80581ad6265SDimitry Andric bool mayHaveNonDefUseDependency(const Instruction &I);
8060b57cec5SDimitry Andric
8070b57cec5SDimitry Andric /// Return true if it is an intrinsic that cannot be speculated but also
8080b57cec5SDimitry Andric /// cannot trap.
8090b57cec5SDimitry Andric bool isAssumeLikeIntrinsic(const Instruction *I);
8100b57cec5SDimitry Andric
8110b57cec5SDimitry Andric /// Return true if it is valid to use the assumptions provided by an
8120b57cec5SDimitry Andric /// assume intrinsic, I, at the point in the control-flow identified by the
8131db9f3b2SDimitry Andric /// context instruction, CxtI. By default, ephemeral values of the assumption
8141db9f3b2SDimitry Andric /// are treated as an invalid context, to prevent the assumption from being used
8151db9f3b2SDimitry Andric /// to optimize away its argument. If the caller can ensure that this won't
8161db9f3b2SDimitry Andric /// happen, it can call with AllowEphemerals set to true to get more valid
8171db9f3b2SDimitry Andric /// assumptions.
8180b57cec5SDimitry Andric bool isValidAssumeForContext(const Instruction *I, const Instruction *CxtI,
8191db9f3b2SDimitry Andric const DominatorTree *DT = nullptr,
8201db9f3b2SDimitry Andric bool AllowEphemerals = false);
8210b57cec5SDimitry Andric
8220b57cec5SDimitry Andric enum class OverflowResult {
8230b57cec5SDimitry Andric /// Always overflows in the direction of signed/unsigned min value.
8240b57cec5SDimitry Andric AlwaysOverflowsLow,
8250b57cec5SDimitry Andric /// Always overflows in the direction of signed/unsigned max value.
8260b57cec5SDimitry Andric AlwaysOverflowsHigh,
8270b57cec5SDimitry Andric /// May or may not overflow.
8280b57cec5SDimitry Andric MayOverflow,
8290b57cec5SDimitry Andric /// Never overflows.
8300b57cec5SDimitry Andric NeverOverflows,
8310b57cec5SDimitry Andric };
8320b57cec5SDimitry Andric
833bdd1243dSDimitry Andric OverflowResult computeOverflowForUnsignedMul(const Value *LHS, const Value *RHS,
8345f757f3fSDimitry Andric const SimplifyQuery &SQ);
8350b57cec5SDimitry Andric OverflowResult computeOverflowForSignedMul(const Value *LHS, const Value *RHS,
8365f757f3fSDimitry Andric const SimplifyQuery &SQ);
8375f757f3fSDimitry Andric OverflowResult
8385f757f3fSDimitry Andric computeOverflowForUnsignedAdd(const WithCache<const Value *> &LHS,
8395f757f3fSDimitry Andric const WithCache<const Value *> &RHS,
8405f757f3fSDimitry Andric const SimplifyQuery &SQ);
8415f757f3fSDimitry Andric OverflowResult computeOverflowForSignedAdd(const WithCache<const Value *> &LHS,
8425f757f3fSDimitry Andric const WithCache<const Value *> &RHS,
8435f757f3fSDimitry Andric const SimplifyQuery &SQ);
8440b57cec5SDimitry Andric /// This version also leverages the sign bit of Add if known.
8450b57cec5SDimitry Andric OverflowResult computeOverflowForSignedAdd(const AddOperator *Add,
8465f757f3fSDimitry Andric const SimplifyQuery &SQ);
8470b57cec5SDimitry Andric OverflowResult computeOverflowForUnsignedSub(const Value *LHS, const Value *RHS,
8485f757f3fSDimitry Andric const SimplifyQuery &SQ);
8490b57cec5SDimitry Andric OverflowResult computeOverflowForSignedSub(const Value *LHS, const Value *RHS,
8505f757f3fSDimitry Andric const SimplifyQuery &SQ);
8510b57cec5SDimitry Andric
8520b57cec5SDimitry Andric /// Returns true if the arithmetic part of the \p WO 's result is
8530b57cec5SDimitry Andric /// used only along the paths control dependent on the computation
8540b57cec5SDimitry Andric /// not overflowing, \p WO being an <op>.with.overflow intrinsic.
8550b57cec5SDimitry Andric bool isOverflowIntrinsicNoWrap(const WithOverflowInst *WO,
8560b57cec5SDimitry Andric const DominatorTree &DT);
8570b57cec5SDimitry Andric
85806c3fb27SDimitry Andric /// Determine the possible constant range of vscale with the given bit width,
85906c3fb27SDimitry Andric /// based on the vscale_range function attribute.
86006c3fb27SDimitry Andric ConstantRange getVScaleRange(const Function *F, unsigned BitWidth);
86106c3fb27SDimitry Andric
8620b57cec5SDimitry Andric /// Determine the possible constant range of an integer or vector of integer
8630b57cec5SDimitry Andric /// value. This is intended as a cheap, non-recursive check.
86404eeddc0SDimitry Andric ConstantRange computeConstantRange(const Value *V, bool ForSigned,
86504eeddc0SDimitry Andric bool UseInstrInfo = true,
8665ffd83dbSDimitry Andric AssumptionCache *AC = nullptr,
8675ffd83dbSDimitry Andric const Instruction *CtxI = nullptr,
868349cc55cSDimitry Andric const DominatorTree *DT = nullptr,
8695ffd83dbSDimitry Andric unsigned Depth = 0);
8700b57cec5SDimitry Andric
871cb14a3feSDimitry Andric /// Combine constant ranges from computeConstantRange() and computeKnownBits().
872cb14a3feSDimitry Andric ConstantRange
873cb14a3feSDimitry Andric computeConstantRangeIncludingKnownBits(const WithCache<const Value *> &V,
874cb14a3feSDimitry Andric bool ForSigned, const SimplifyQuery &SQ);
875cb14a3feSDimitry Andric
8760b57cec5SDimitry Andric /// Return true if this function can prove that the instruction I will
8770b57cec5SDimitry Andric /// always transfer execution to one of its successors (including the next
8780b57cec5SDimitry Andric /// instruction that follows within a basic block). E.g. this is not
8790b57cec5SDimitry Andric /// guaranteed for function calls that could loop infinitely.
8800b57cec5SDimitry Andric ///
8810b57cec5SDimitry Andric /// In other words, this function returns false for instructions that may
8820b57cec5SDimitry Andric /// transfer execution or fail to transfer execution in a way that is not
8830b57cec5SDimitry Andric /// captured in the CFG nor in the sequence of instructions within a basic
8840b57cec5SDimitry Andric /// block.
8850b57cec5SDimitry Andric ///
8860b57cec5SDimitry Andric /// Undefined behavior is assumed not to happen, so e.g. division is
8870b57cec5SDimitry Andric /// guaranteed to transfer execution to the following instruction even
8880b57cec5SDimitry Andric /// though division by zero might cause undefined behavior.
8890b57cec5SDimitry Andric bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I);
8900b57cec5SDimitry Andric
8910b57cec5SDimitry Andric /// Returns true if this block does not contain a potential implicit exit.
8920b57cec5SDimitry Andric /// This is equivelent to saying that all instructions within the basic block
8930b57cec5SDimitry Andric /// are guaranteed to transfer execution to their successor within the basic
8940b57cec5SDimitry Andric /// block. This has the same assumptions w.r.t. undefined behavior as the
8950b57cec5SDimitry Andric /// instruction variant of this function.
8960b57cec5SDimitry Andric bool isGuaranteedToTransferExecutionToSuccessor(const BasicBlock *BB);
8970b57cec5SDimitry Andric
898349cc55cSDimitry Andric /// Return true if every instruction in the range (Begin, End) is
899349cc55cSDimitry Andric /// guaranteed to transfer execution to its static successor. \p ScanLimit
900349cc55cSDimitry Andric /// bounds the search to avoid scanning huge blocks.
901349cc55cSDimitry Andric bool isGuaranteedToTransferExecutionToSuccessor(
902349cc55cSDimitry Andric BasicBlock::const_iterator Begin, BasicBlock::const_iterator End,
903349cc55cSDimitry Andric unsigned ScanLimit = 32);
904349cc55cSDimitry Andric
905349cc55cSDimitry Andric /// Same as previous, but with range expressed via iterator_range.
906349cc55cSDimitry Andric bool isGuaranteedToTransferExecutionToSuccessor(
907bdd1243dSDimitry Andric iterator_range<BasicBlock::const_iterator> Range, unsigned ScanLimit = 32);
908349cc55cSDimitry Andric
9090b57cec5SDimitry Andric /// Return true if this function can prove that the instruction I
9100b57cec5SDimitry Andric /// is executed for every iteration of the loop L.
9110b57cec5SDimitry Andric ///
9120b57cec5SDimitry Andric /// Note that this currently only considers the loop header.
9130b57cec5SDimitry Andric bool isGuaranteedToExecuteForEveryIteration(const Instruction *I,
9140b57cec5SDimitry Andric const Loop *L);
9150b57cec5SDimitry Andric
916bdd1243dSDimitry Andric /// Return true if \p PoisonOp's user yields poison or raises UB if its
917bdd1243dSDimitry Andric /// operand \p PoisonOp is poison.
918bdd1243dSDimitry Andric ///
919bdd1243dSDimitry Andric /// If \p PoisonOp is a vector or an aggregate and the operation's result is a
920bdd1243dSDimitry Andric /// single value, any poison element in /p PoisonOp should make the result
921bdd1243dSDimitry Andric /// poison or raise UB.
922bdd1243dSDimitry Andric ///
9235ffd83dbSDimitry Andric /// To filter out operands that raise UB on poison, you can use
9245ffd83dbSDimitry Andric /// getGuaranteedNonPoisonOp.
925bdd1243dSDimitry Andric bool propagatesPoison(const Use &PoisonOp);
9260b57cec5SDimitry Andric
927e8d8bef9SDimitry Andric /// Insert operands of I into Ops such that I will trigger undefined behavior
928e8d8bef9SDimitry Andric /// if I is executed and that operand has a poison value.
929e8d8bef9SDimitry Andric void getGuaranteedNonPoisonOps(const Instruction *I,
930bdd1243dSDimitry Andric SmallVectorImpl<const Value *> &Ops);
931bdd1243dSDimitry Andric
932fe6060f1SDimitry Andric /// Insert operands of I into Ops such that I will trigger undefined behavior
933fe6060f1SDimitry Andric /// if I is executed and that operand is not a well-defined value
934fe6060f1SDimitry Andric /// (i.e. has undef bits or poison).
935fe6060f1SDimitry Andric void getGuaranteedWellDefinedOps(const Instruction *I,
936bdd1243dSDimitry Andric SmallVectorImpl<const Value *> &Ops);
9370b57cec5SDimitry Andric
938e8d8bef9SDimitry Andric /// Return true if the given instruction must trigger undefined behavior
9390b57cec5SDimitry Andric /// when I is executed with any operands which appear in KnownPoison holding
9405ffd83dbSDimitry Andric /// a poison value at the point of execution.
9410b57cec5SDimitry Andric bool mustTriggerUB(const Instruction *I,
94206c3fb27SDimitry Andric const SmallPtrSetImpl<const Value *> &KnownPoison);
9430b57cec5SDimitry Andric
944e8d8bef9SDimitry Andric /// Return true if this function can prove that if Inst is executed
945e8d8bef9SDimitry Andric /// and yields a poison value or undef bits, then that will trigger
946e8d8bef9SDimitry Andric /// undefined behavior.
9470b57cec5SDimitry Andric ///
9480b57cec5SDimitry Andric /// Note that this currently only considers the basic block that is
949e8d8bef9SDimitry Andric /// the parent of Inst.
950e8d8bef9SDimitry Andric bool programUndefinedIfUndefOrPoison(const Instruction *Inst);
951e8d8bef9SDimitry Andric bool programUndefinedIfPoison(const Instruction *Inst);
9525ffd83dbSDimitry Andric
953e8d8bef9SDimitry Andric /// canCreateUndefOrPoison returns true if Op can create undef or poison from
954e8d8bef9SDimitry Andric /// non-undef & non-poison operands.
955e8d8bef9SDimitry Andric /// For vectors, canCreateUndefOrPoison returns true if there is potential
956e8d8bef9SDimitry Andric /// poison or undef in any element of the result when vectors without
957e8d8bef9SDimitry Andric /// undef/poison poison are given as operands.
958e8d8bef9SDimitry Andric /// For example, given `Op = shl <2 x i32> %x, <0, 32>`, this function returns
959e8d8bef9SDimitry Andric /// true. If Op raises immediate UB but never creates poison or undef
960e8d8bef9SDimitry Andric /// (e.g. sdiv I, 0), canCreatePoison returns false.
961e8d8bef9SDimitry Andric ///
962bdd1243dSDimitry Andric /// \p ConsiderFlagsAndMetadata controls whether poison producing flags and
963bdd1243dSDimitry Andric /// metadata on the instruction are considered. This can be used to see if the
964bdd1243dSDimitry Andric /// instruction could still introduce undef or poison even without poison
965bdd1243dSDimitry Andric /// generating flags and metadata which might be on the instruction.
966bdd1243dSDimitry Andric /// (i.e. could the result of Op->dropPoisonGeneratingFlags() still create
967bdd1243dSDimitry Andric /// poison or undef)
968349cc55cSDimitry Andric ///
969e8d8bef9SDimitry Andric /// canCreatePoison returns true if Op can create poison from non-poison
9705ffd83dbSDimitry Andric /// operands.
971bdd1243dSDimitry Andric bool canCreateUndefOrPoison(const Operator *Op,
972bdd1243dSDimitry Andric bool ConsiderFlagsAndMetadata = true);
973bdd1243dSDimitry Andric bool canCreatePoison(const Operator *Op, bool ConsiderFlagsAndMetadata = true);
9740b57cec5SDimitry Andric
975e8d8bef9SDimitry Andric /// Return true if V is poison given that ValAssumedPoison is already poison.
976e8d8bef9SDimitry Andric /// For example, if ValAssumedPoison is `icmp X, 10` and V is `icmp X, 5`,
977e8d8bef9SDimitry Andric /// impliesPoison returns true.
978e8d8bef9SDimitry Andric bool impliesPoison(const Value *ValAssumedPoison, const Value *V);
979e8d8bef9SDimitry Andric
980e8d8bef9SDimitry Andric /// Return true if this function can prove that V does not have undef bits
981e8d8bef9SDimitry Andric /// and is never poison. If V is an aggregate value or vector, check whether
982e8d8bef9SDimitry Andric /// all elements (except padding) are not undef or poison.
983e8d8bef9SDimitry Andric /// Note that this is different from canCreateUndefOrPoison because the
984e8d8bef9SDimitry Andric /// function assumes Op's operands are not poison/undef.
985e8d8bef9SDimitry Andric ///
9865ffd83dbSDimitry Andric /// If CtxI and DT are specified this method performs flow-sensitive analysis
9875ffd83dbSDimitry Andric /// and returns true if it is guaranteed to be never undef or poison
9885ffd83dbSDimitry Andric /// immediately before the CtxI.
9895ffd83dbSDimitry Andric bool isGuaranteedNotToBeUndefOrPoison(const Value *V,
990e8d8bef9SDimitry Andric AssumptionCache *AC = nullptr,
991e8d8bef9SDimitry Andric const Instruction *CtxI = nullptr,
992e8d8bef9SDimitry Andric const DominatorTree *DT = nullptr,
993e8d8bef9SDimitry Andric unsigned Depth = 0);
9945f757f3fSDimitry Andric
9955f757f3fSDimitry Andric /// Returns true if V cannot be poison, but may be undef.
996e8d8bef9SDimitry Andric bool isGuaranteedNotToBePoison(const Value *V, AssumptionCache *AC = nullptr,
9975ffd83dbSDimitry Andric const Instruction *CtxI = nullptr,
9985ffd83dbSDimitry Andric const DominatorTree *DT = nullptr,
9995ffd83dbSDimitry Andric unsigned Depth = 0);
1000480093f4SDimitry Andric
10015f757f3fSDimitry Andric /// Returns true if V cannot be undef, but may be poison.
10025f757f3fSDimitry Andric bool isGuaranteedNotToBeUndef(const Value *V, AssumptionCache *AC = nullptr,
10035f757f3fSDimitry Andric const Instruction *CtxI = nullptr,
10045f757f3fSDimitry Andric const DominatorTree *DT = nullptr,
10055f757f3fSDimitry Andric unsigned Depth = 0);
10065f757f3fSDimitry Andric
100706c3fb27SDimitry Andric /// Return true if undefined behavior would provable be executed on the path to
100806c3fb27SDimitry Andric /// OnPathTo if Root produced a posion result. Note that this doesn't say
100906c3fb27SDimitry Andric /// anything about whether OnPathTo is actually executed or whether Root is
101006c3fb27SDimitry Andric /// actually poison. This can be used to assess whether a new use of Root can
101106c3fb27SDimitry Andric /// be added at a location which is control equivalent with OnPathTo (such as
101206c3fb27SDimitry Andric /// immediately before it) without introducing UB which didn't previously
101306c3fb27SDimitry Andric /// exist. Note that a false result conveys no information.
101406c3fb27SDimitry Andric bool mustExecuteUBIfPoisonOnPathTo(Instruction *Root,
101506c3fb27SDimitry Andric Instruction *OnPathTo,
101606c3fb27SDimitry Andric DominatorTree *DT);
101706c3fb27SDimitry Andric
10180b57cec5SDimitry Andric /// Specific patterns of select instructions we can match.
10190b57cec5SDimitry Andric enum SelectPatternFlavor {
10200b57cec5SDimitry Andric SPF_UNKNOWN = 0,
10210b57cec5SDimitry Andric SPF_SMIN, /// Signed minimum
10220b57cec5SDimitry Andric SPF_UMIN, /// Unsigned minimum
10230b57cec5SDimitry Andric SPF_SMAX, /// Signed maximum
10240b57cec5SDimitry Andric SPF_UMAX, /// Unsigned maximum
10250b57cec5SDimitry Andric SPF_FMINNUM, /// Floating point minnum
10260b57cec5SDimitry Andric SPF_FMAXNUM, /// Floating point maxnum
10270b57cec5SDimitry Andric SPF_ABS, /// Absolute value
10280b57cec5SDimitry Andric SPF_NABS /// Negated absolute value
10290b57cec5SDimitry Andric };
10300b57cec5SDimitry Andric
10310b57cec5SDimitry Andric /// Behavior when a floating point min/max is given one NaN and one
10320b57cec5SDimitry Andric /// non-NaN as input.
10330b57cec5SDimitry Andric enum SelectPatternNaNBehavior {
10340b57cec5SDimitry Andric SPNB_NA = 0, /// NaN behavior not applicable.
10350b57cec5SDimitry Andric SPNB_RETURNS_NAN, /// Given one NaN input, returns the NaN.
10360b57cec5SDimitry Andric SPNB_RETURNS_OTHER, /// Given one NaN input, returns the non-NaN.
10370b57cec5SDimitry Andric SPNB_RETURNS_ANY /// Given one NaN input, can return either (or
10380b57cec5SDimitry Andric /// it has been determined that no operands can
10390b57cec5SDimitry Andric /// be NaN).
10400b57cec5SDimitry Andric };
10410b57cec5SDimitry Andric
10420b57cec5SDimitry Andric struct SelectPatternResult {
10430b57cec5SDimitry Andric SelectPatternFlavor Flavor;
10440b57cec5SDimitry Andric SelectPatternNaNBehavior NaNBehavior; /// Only applicable if Flavor is
10450b57cec5SDimitry Andric /// SPF_FMINNUM or SPF_FMAXNUM.
10460b57cec5SDimitry Andric bool Ordered; /// When implementing this min/max pattern as
10470b57cec5SDimitry Andric /// fcmp; select, does the fcmp have to be
10480b57cec5SDimitry Andric /// ordered?
10490b57cec5SDimitry Andric
10500b57cec5SDimitry Andric /// Return true if \p SPF is a min or a max pattern.
isMinOrMaxSelectPatternResult10510b57cec5SDimitry Andric static bool isMinOrMax(SelectPatternFlavor SPF) {
10520b57cec5SDimitry Andric return SPF != SPF_UNKNOWN && SPF != SPF_ABS && SPF != SPF_NABS;
10530b57cec5SDimitry Andric }
10540b57cec5SDimitry Andric };
10550b57cec5SDimitry Andric
10560b57cec5SDimitry Andric /// Pattern match integer [SU]MIN, [SU]MAX and ABS idioms, returning the kind
10570b57cec5SDimitry Andric /// and providing the out parameter results if we successfully match.
10580b57cec5SDimitry Andric ///
10590b57cec5SDimitry Andric /// For ABS/NABS, LHS will be set to the input to the abs idiom. RHS will be
10600b57cec5SDimitry Andric /// the negation instruction from the idiom.
10610b57cec5SDimitry Andric ///
10620b57cec5SDimitry Andric /// If CastOp is not nullptr, also match MIN/MAX idioms where the type does
10630b57cec5SDimitry Andric /// not match that of the original select. If this is the case, the cast
10640b57cec5SDimitry Andric /// operation (one of Trunc,SExt,Zext) that must be done to transform the
10650b57cec5SDimitry Andric /// type of LHS and RHS into the type of V is returned in CastOp.
10660b57cec5SDimitry Andric ///
10670b57cec5SDimitry Andric /// For example:
10680b57cec5SDimitry Andric /// %1 = icmp slt i32 %a, i32 4
10690b57cec5SDimitry Andric /// %2 = sext i32 %a to i64
10700b57cec5SDimitry Andric /// %3 = select i1 %1, i64 %2, i64 4
10710b57cec5SDimitry Andric ///
10720b57cec5SDimitry Andric /// -> LHS = %a, RHS = i32 4, *CastOp = Instruction::SExt
10730b57cec5SDimitry Andric ///
10740b57cec5SDimitry Andric SelectPatternResult matchSelectPattern(Value *V, Value *&LHS, Value *&RHS,
10750b57cec5SDimitry Andric Instruction::CastOps *CastOp = nullptr,
10760b57cec5SDimitry Andric unsigned Depth = 0);
10778bcb0991SDimitry Andric
matchSelectPattern(const Value * V,const Value * & LHS,const Value * & RHS)1078bdd1243dSDimitry Andric inline SelectPatternResult matchSelectPattern(const Value *V, const Value *&LHS,
1079bdd1243dSDimitry Andric const Value *&RHS) {
10800b57cec5SDimitry Andric Value *L = const_cast<Value *>(LHS);
10810b57cec5SDimitry Andric Value *R = const_cast<Value *>(RHS);
10820b57cec5SDimitry Andric auto Result = matchSelectPattern(const_cast<Value *>(V), L, R);
10830b57cec5SDimitry Andric LHS = L;
10840b57cec5SDimitry Andric RHS = R;
10850b57cec5SDimitry Andric return Result;
10860b57cec5SDimitry Andric }
10870b57cec5SDimitry Andric
10880b57cec5SDimitry Andric /// Determine the pattern that a select with the given compare as its
10890b57cec5SDimitry Andric /// predicate and given values as its true/false operands would match.
10900b57cec5SDimitry Andric SelectPatternResult matchDecomposedSelectPattern(
10910b57cec5SDimitry Andric CmpInst *CmpI, Value *TrueVal, Value *FalseVal, Value *&LHS, Value *&RHS,
10920b57cec5SDimitry Andric Instruction::CastOps *CastOp = nullptr, unsigned Depth = 0);
10930b57cec5SDimitry Andric
10940b57cec5SDimitry Andric /// Return the canonical comparison predicate for the specified
10950b57cec5SDimitry Andric /// minimum/maximum flavor.
1096bdd1243dSDimitry Andric CmpInst::Predicate getMinMaxPred(SelectPatternFlavor SPF, bool Ordered = false);
10970b57cec5SDimitry Andric
10980b57cec5SDimitry Andric /// Return the inverse minimum/maximum flavor of the specified flavor.
10990b57cec5SDimitry Andric /// For example, signed minimum is the inverse of signed maximum.
11000b57cec5SDimitry Andric SelectPatternFlavor getInverseMinMaxFlavor(SelectPatternFlavor SPF);
11010b57cec5SDimitry Andric
1102fe6060f1SDimitry Andric Intrinsic::ID getInverseMinMaxIntrinsic(Intrinsic::ID MinMaxID);
1103fe6060f1SDimitry Andric
11046e75b2fbSDimitry Andric /// Return the minimum or maximum constant value for the specified integer
11056e75b2fbSDimitry Andric /// min/max flavor and type.
11066e75b2fbSDimitry Andric APInt getMinMaxLimit(SelectPatternFlavor SPF, unsigned BitWidth);
11076e75b2fbSDimitry Andric
1108e8d8bef9SDimitry Andric /// Check if the values in \p VL are select instructions that can be converted
1109e8d8bef9SDimitry Andric /// to a min or max (vector) intrinsic. Returns the intrinsic ID, if such a
1110e8d8bef9SDimitry Andric /// conversion is possible, together with a bool indicating whether all select
1111e8d8bef9SDimitry Andric /// conditions are only used by the selects. Otherwise return
1112e8d8bef9SDimitry Andric /// Intrinsic::not_intrinsic.
1113e8d8bef9SDimitry Andric std::pair<Intrinsic::ID, bool>
1114e8d8bef9SDimitry Andric canConvertToMinOrMaxIntrinsic(ArrayRef<Value *> VL);
1115e8d8bef9SDimitry Andric
1116fe6060f1SDimitry Andric /// Attempt to match a simple first order recurrence cycle of the form:
1117fe6060f1SDimitry Andric /// %iv = phi Ty [%Start, %Entry], [%Inc, %backedge]
1118fe6060f1SDimitry Andric /// %inc = binop %iv, %step
1119fe6060f1SDimitry Andric /// OR
1120fe6060f1SDimitry Andric /// %iv = phi Ty [%Start, %Entry], [%Inc, %backedge]
1121fe6060f1SDimitry Andric /// %inc = binop %step, %iv
1122fe6060f1SDimitry Andric ///
1123fe6060f1SDimitry Andric /// A first order recurrence is a formula with the form: X_n = f(X_(n-1))
1124fe6060f1SDimitry Andric ///
1125fe6060f1SDimitry Andric /// A couple of notes on subtleties in that definition:
1126fe6060f1SDimitry Andric /// * The Step does not have to be loop invariant. In math terms, it can
1127fe6060f1SDimitry Andric /// be a free variable. We allow recurrences with both constant and
1128fe6060f1SDimitry Andric /// variable coefficients. Callers may wish to filter cases where Step
1129fe6060f1SDimitry Andric /// does not dominate P.
1130fe6060f1SDimitry Andric /// * For non-commutative operators, we will match both forms. This
1131fe6060f1SDimitry Andric /// results in some odd recurrence structures. Callers may wish to filter
1132fe6060f1SDimitry Andric /// out recurrences where the phi is not the LHS of the returned operator.
1133fe6060f1SDimitry Andric /// * Because of the structure matched, the caller can assume as a post
1134fe6060f1SDimitry Andric /// condition of the match the presence of a Loop with P's parent as it's
1135fe6060f1SDimitry Andric /// header *except* in unreachable code. (Dominance decays in unreachable
1136fe6060f1SDimitry Andric /// code.)
1137fe6060f1SDimitry Andric ///
1138fe6060f1SDimitry Andric /// NOTE: This is intentional simple. If you want the ability to analyze
1139fe6060f1SDimitry Andric /// non-trivial loop conditons, see ScalarEvolution instead.
1140bdd1243dSDimitry Andric bool matchSimpleRecurrence(const PHINode *P, BinaryOperator *&BO, Value *&Start,
1141bdd1243dSDimitry Andric Value *&Step);
1142fe6060f1SDimitry Andric
1143fe6060f1SDimitry Andric /// Analogous to the above, but starting from the binary operator
1144bdd1243dSDimitry Andric bool matchSimpleRecurrence(const BinaryOperator *I, PHINode *&P, Value *&Start,
1145bdd1243dSDimitry Andric Value *&Step);
1146fe6060f1SDimitry Andric
11470b57cec5SDimitry Andric /// Return true if RHS is known to be implied true by LHS. Return false if
1148bdd1243dSDimitry Andric /// RHS is known to be implied false by LHS. Otherwise, return std::nullopt if
1149bdd1243dSDimitry Andric /// no implication can be made. A & B must be i1 (boolean) values or a vector of
1150bdd1243dSDimitry Andric /// such values. Note that the truth table for implication is the same as <=u on
1151bdd1243dSDimitry Andric /// i1 values (but not
11520b57cec5SDimitry Andric /// <=s!). The truth table for both is:
11530b57cec5SDimitry Andric /// | T | F (B)
11540b57cec5SDimitry Andric /// T | T | F
11550b57cec5SDimitry Andric /// F | T | T
11560b57cec5SDimitry Andric /// (A)
1157bdd1243dSDimitry Andric std::optional<bool> isImpliedCondition(const Value *LHS, const Value *RHS,
1158bdd1243dSDimitry Andric const DataLayout &DL,
1159bdd1243dSDimitry Andric bool LHSIsTrue = true,
11600b57cec5SDimitry Andric unsigned Depth = 0);
1161bdd1243dSDimitry Andric std::optional<bool> isImpliedCondition(const Value *LHS,
11625ffd83dbSDimitry Andric CmpInst::Predicate RHSPred,
11635ffd83dbSDimitry Andric const Value *RHSOp0, const Value *RHSOp1,
1164bdd1243dSDimitry Andric const DataLayout &DL,
1165bdd1243dSDimitry Andric bool LHSIsTrue = true,
11665ffd83dbSDimitry Andric unsigned Depth = 0);
11670b57cec5SDimitry Andric
11680b57cec5SDimitry Andric /// Return the boolean condition value in the context of the given instruction
11690b57cec5SDimitry Andric /// if it is known based on dominating conditions.
1170bdd1243dSDimitry Andric std::optional<bool> isImpliedByDomCondition(const Value *Cond,
11710b57cec5SDimitry Andric const Instruction *ContextI,
11720b57cec5SDimitry Andric const DataLayout &DL);
1173bdd1243dSDimitry Andric std::optional<bool> isImpliedByDomCondition(CmpInst::Predicate Pred,
11745ffd83dbSDimitry Andric const Value *LHS, const Value *RHS,
11755ffd83dbSDimitry Andric const Instruction *ContextI,
11765ffd83dbSDimitry Andric const DataLayout &DL);
11770b57cec5SDimitry Andric } // end namespace llvm
11780b57cec5SDimitry Andric
11790b57cec5SDimitry Andric #endif // LLVM_ANALYSIS_VALUETRACKING_H
1180