diff options
Diffstat (limited to 'contrib/llvm-project/llvm/lib/Support/KnownBits.cpp')
| -rw-r--r-- | contrib/llvm-project/llvm/lib/Support/KnownBits.cpp | 397 |
1 files changed, 397 insertions, 0 deletions
diff --git a/contrib/llvm-project/llvm/lib/Support/KnownBits.cpp b/contrib/llvm-project/llvm/lib/Support/KnownBits.cpp index 1ff66d504cbe..3623a54ae476 100644 --- a/contrib/llvm-project/llvm/lib/Support/KnownBits.cpp +++ b/contrib/llvm-project/llvm/lib/Support/KnownBits.cpp @@ -83,6 +83,403 @@ KnownBits KnownBits::computeForAddSub(bool Add, bool NSW, return KnownOut; } +KnownBits KnownBits::sextInReg(unsigned SrcBitWidth) const { + unsigned BitWidth = getBitWidth(); + assert(0 < SrcBitWidth && SrcBitWidth <= BitWidth && + "Illegal sext-in-register"); + + if (SrcBitWidth == BitWidth) + return *this; + + unsigned ExtBits = BitWidth - SrcBitWidth; + KnownBits Result; + Result.One = One << ExtBits; + Result.Zero = Zero << ExtBits; + Result.One.ashrInPlace(ExtBits); + Result.Zero.ashrInPlace(ExtBits); + return Result; +} + +KnownBits KnownBits::makeGE(const APInt &Val) const { + // Count the number of leading bit positions where our underlying value is + // known to be less than or equal to Val. + unsigned N = (Zero | Val).countLeadingOnes(); + + // For each of those bit positions, if Val has a 1 in that bit then our + // underlying value must also have a 1. + APInt MaskedVal(Val); + MaskedVal.clearLowBits(getBitWidth() - N); + return KnownBits(Zero, One | MaskedVal); +} + +KnownBits KnownBits::umax(const KnownBits &LHS, const KnownBits &RHS) { + // If we can prove that LHS >= RHS then use LHS as the result. Likewise for + // RHS. Ideally our caller would already have spotted these cases and + // optimized away the umax operation, but we handle them here for + // completeness. + if (LHS.getMinValue().uge(RHS.getMaxValue())) + return LHS; + if (RHS.getMinValue().uge(LHS.getMaxValue())) + return RHS; + + // If the result of the umax is LHS then it must be greater than or equal to + // the minimum possible value of RHS. Likewise for RHS. Any known bits that + // are common to these two values are also known in the result. + KnownBits L = LHS.makeGE(RHS.getMinValue()); + KnownBits R = RHS.makeGE(LHS.getMinValue()); + return KnownBits::commonBits(L, R); +} + +KnownBits KnownBits::umin(const KnownBits &LHS, const KnownBits &RHS) { + // Flip the range of values: [0, 0xFFFFFFFF] <-> [0xFFFFFFFF, 0] + auto Flip = [](const KnownBits &Val) { return KnownBits(Val.One, Val.Zero); }; + return Flip(umax(Flip(LHS), Flip(RHS))); +} + +KnownBits KnownBits::smax(const KnownBits &LHS, const KnownBits &RHS) { + // Flip the range of values: [-0x80000000, 0x7FFFFFFF] <-> [0, 0xFFFFFFFF] + auto Flip = [](const KnownBits &Val) { + unsigned SignBitPosition = Val.getBitWidth() - 1; + APInt Zero = Val.Zero; + APInt One = Val.One; + Zero.setBitVal(SignBitPosition, Val.One[SignBitPosition]); + One.setBitVal(SignBitPosition, Val.Zero[SignBitPosition]); + return KnownBits(Zero, One); + }; + return Flip(umax(Flip(LHS), Flip(RHS))); +} + +KnownBits KnownBits::smin(const KnownBits &LHS, const KnownBits &RHS) { + // Flip the range of values: [-0x80000000, 0x7FFFFFFF] <-> [0xFFFFFFFF, 0] + auto Flip = [](const KnownBits &Val) { + unsigned SignBitPosition = Val.getBitWidth() - 1; + APInt Zero = Val.One; + APInt One = Val.Zero; + Zero.setBitVal(SignBitPosition, Val.Zero[SignBitPosition]); + One.setBitVal(SignBitPosition, Val.One[SignBitPosition]); + return KnownBits(Zero, One); + }; + return Flip(umax(Flip(LHS), Flip(RHS))); +} + +KnownBits KnownBits::shl(const KnownBits &LHS, const KnownBits &RHS) { + unsigned BitWidth = LHS.getBitWidth(); + KnownBits Known(BitWidth); + + // If the shift amount is a valid constant then transform LHS directly. + if (RHS.isConstant() && RHS.getConstant().ult(BitWidth)) { + unsigned Shift = RHS.getConstant().getZExtValue(); + Known = LHS; + Known.Zero <<= Shift; + Known.One <<= Shift; + // Low bits are known zero. + Known.Zero.setLowBits(Shift); + return Known; + } + + // No matter the shift amount, the trailing zeros will stay zero. + unsigned MinTrailingZeros = LHS.countMinTrailingZeros(); + + // Minimum shift amount low bits are known zero. + if (RHS.getMinValue().ult(BitWidth)) { + MinTrailingZeros += RHS.getMinValue().getZExtValue(); + MinTrailingZeros = std::min(MinTrailingZeros, BitWidth); + } + + Known.Zero.setLowBits(MinTrailingZeros); + return Known; +} + +KnownBits KnownBits::lshr(const KnownBits &LHS, const KnownBits &RHS) { + unsigned BitWidth = LHS.getBitWidth(); + KnownBits Known(BitWidth); + + if (RHS.isConstant() && RHS.getConstant().ult(BitWidth)) { + unsigned Shift = RHS.getConstant().getZExtValue(); + Known = LHS; + Known.Zero.lshrInPlace(Shift); + Known.One.lshrInPlace(Shift); + // High bits are known zero. + Known.Zero.setHighBits(Shift); + return Known; + } + + // No matter the shift amount, the leading zeros will stay zero. + unsigned MinLeadingZeros = LHS.countMinLeadingZeros(); + + // Minimum shift amount high bits are known zero. + if (RHS.getMinValue().ult(BitWidth)) { + MinLeadingZeros += RHS.getMinValue().getZExtValue(); + MinLeadingZeros = std::min(MinLeadingZeros, BitWidth); + } + + Known.Zero.setHighBits(MinLeadingZeros); + return Known; +} + +KnownBits KnownBits::ashr(const KnownBits &LHS, const KnownBits &RHS) { + unsigned BitWidth = LHS.getBitWidth(); + KnownBits Known(BitWidth); + + if (RHS.isConstant() && RHS.getConstant().ult(BitWidth)) { + unsigned Shift = RHS.getConstant().getZExtValue(); + Known = LHS; + Known.Zero.ashrInPlace(Shift); + Known.One.ashrInPlace(Shift); + return Known; + } + + // No matter the shift amount, the leading sign bits will stay. + unsigned MinLeadingZeros = LHS.countMinLeadingZeros(); + unsigned MinLeadingOnes = LHS.countMinLeadingOnes(); + + // Minimum shift amount high bits are known sign bits. + if (RHS.getMinValue().ult(BitWidth)) { + if (MinLeadingZeros) { + MinLeadingZeros += RHS.getMinValue().getZExtValue(); + MinLeadingZeros = std::min(MinLeadingZeros, BitWidth); + } + if (MinLeadingOnes) { + MinLeadingOnes += RHS.getMinValue().getZExtValue(); + MinLeadingOnes = std::min(MinLeadingOnes, BitWidth); + } + } + + Known.Zero.setHighBits(MinLeadingZeros); + Known.One.setHighBits(MinLeadingOnes); + return Known; +} + +Optional<bool> KnownBits::eq(const KnownBits &LHS, const KnownBits &RHS) { + if (LHS.isConstant() && RHS.isConstant()) + return Optional<bool>(LHS.getConstant() == RHS.getConstant()); + if (LHS.One.intersects(RHS.Zero) || RHS.One.intersects(LHS.Zero)) + return Optional<bool>(false); + return None; +} + +Optional<bool> KnownBits::ne(const KnownBits &LHS, const KnownBits &RHS) { + if (Optional<bool> KnownEQ = eq(LHS, RHS)) + return Optional<bool>(!KnownEQ.getValue()); + return None; +} + +Optional<bool> KnownBits::ugt(const KnownBits &LHS, const KnownBits &RHS) { + // LHS >u RHS -> false if umax(LHS) <= umax(RHS) + if (LHS.getMaxValue().ule(RHS.getMinValue())) + return Optional<bool>(false); + // LHS >u RHS -> true if umin(LHS) > umax(RHS) + if (LHS.getMinValue().ugt(RHS.getMaxValue())) + return Optional<bool>(true); + return None; +} + +Optional<bool> KnownBits::uge(const KnownBits &LHS, const KnownBits &RHS) { + if (Optional<bool> IsUGT = ugt(RHS, LHS)) + return Optional<bool>(!IsUGT.getValue()); + return None; +} + +Optional<bool> KnownBits::ult(const KnownBits &LHS, const KnownBits &RHS) { + return ugt(RHS, LHS); +} + +Optional<bool> KnownBits::ule(const KnownBits &LHS, const KnownBits &RHS) { + return uge(RHS, LHS); +} + +Optional<bool> KnownBits::sgt(const KnownBits &LHS, const KnownBits &RHS) { + // LHS >s RHS -> false if smax(LHS) <= smax(RHS) + if (LHS.getSignedMaxValue().sle(RHS.getSignedMinValue())) + return Optional<bool>(false); + // LHS >s RHS -> true if smin(LHS) > smax(RHS) + if (LHS.getSignedMinValue().sgt(RHS.getSignedMaxValue())) + return Optional<bool>(true); + return None; +} + +Optional<bool> KnownBits::sge(const KnownBits &LHS, const KnownBits &RHS) { + if (Optional<bool> KnownSGT = sgt(RHS, LHS)) + return Optional<bool>(!KnownSGT.getValue()); + return None; +} + +Optional<bool> KnownBits::slt(const KnownBits &LHS, const KnownBits &RHS) { + return sgt(RHS, LHS); +} + +Optional<bool> KnownBits::sle(const KnownBits &LHS, const KnownBits &RHS) { + return sge(RHS, LHS); +} + +KnownBits KnownBits::abs(bool IntMinIsPoison) const { + // If the source's MSB is zero then we know the rest of the bits already. + if (isNonNegative()) + return *this; + + // Absolute value preserves trailing zero count. + KnownBits KnownAbs(getBitWidth()); + KnownAbs.Zero.setLowBits(countMinTrailingZeros()); + + // We only know that the absolute values's MSB will be zero if INT_MIN is + // poison, or there is a set bit that isn't the sign bit (otherwise it could + // be INT_MIN). + if (IntMinIsPoison || (!One.isNullValue() && !One.isMinSignedValue())) + KnownAbs.Zero.setSignBit(); + + // FIXME: Handle known negative input? + // FIXME: Calculate the negated Known bits and combine them? + return KnownAbs; +} + +KnownBits KnownBits::computeForMul(const KnownBits &LHS, const KnownBits &RHS) { + unsigned BitWidth = LHS.getBitWidth(); + + assert(!LHS.hasConflict() && !RHS.hasConflict()); + // Compute a conservative estimate for high known-0 bits. + unsigned LeadZ = + std::max(LHS.countMinLeadingZeros() + RHS.countMinLeadingZeros(), + BitWidth) - + BitWidth; + LeadZ = std::min(LeadZ, BitWidth); + + // The result of the bottom bits of an integer multiply can be + // inferred by looking at the bottom bits of both operands and + // multiplying them together. + // We can infer at least the minimum number of known trailing bits + // of both operands. Depending on number of trailing zeros, we can + // infer more bits, because (a*b) <=> ((a/m) * (b/n)) * (m*n) assuming + // a and b are divisible by m and n respectively. + // We then calculate how many of those bits are inferrable and set + // the output. For example, the i8 mul: + // a = XXXX1100 (12) + // b = XXXX1110 (14) + // We know the bottom 3 bits are zero since the first can be divided by + // 4 and the second by 2, thus having ((12/4) * (14/2)) * (2*4). + // Applying the multiplication to the trimmed arguments gets: + // XX11 (3) + // X111 (7) + // ------- + // XX11 + // XX11 + // XX11 + // XX11 + // ------- + // XXXXX01 + // Which allows us to infer the 2 LSBs. Since we're multiplying the result + // by 8, the bottom 3 bits will be 0, so we can infer a total of 5 bits. + // The proof for this can be described as: + // Pre: (C1 >= 0) && (C1 < (1 << C5)) && (C2 >= 0) && (C2 < (1 << C6)) && + // (C7 == (1 << (umin(countTrailingZeros(C1), C5) + + // umin(countTrailingZeros(C2), C6) + + // umin(C5 - umin(countTrailingZeros(C1), C5), + // C6 - umin(countTrailingZeros(C2), C6)))) - 1) + // %aa = shl i8 %a, C5 + // %bb = shl i8 %b, C6 + // %aaa = or i8 %aa, C1 + // %bbb = or i8 %bb, C2 + // %mul = mul i8 %aaa, %bbb + // %mask = and i8 %mul, C7 + // => + // %mask = i8 ((C1*C2)&C7) + // Where C5, C6 describe the known bits of %a, %b + // C1, C2 describe the known bottom bits of %a, %b. + // C7 describes the mask of the known bits of the result. + const APInt &Bottom0 = LHS.One; + const APInt &Bottom1 = RHS.One; + + // How many times we'd be able to divide each argument by 2 (shr by 1). + // This gives us the number of trailing zeros on the multiplication result. + unsigned TrailBitsKnown0 = (LHS.Zero | LHS.One).countTrailingOnes(); + unsigned TrailBitsKnown1 = (RHS.Zero | RHS.One).countTrailingOnes(); + unsigned TrailZero0 = LHS.countMinTrailingZeros(); + unsigned TrailZero1 = RHS.countMinTrailingZeros(); + unsigned TrailZ = TrailZero0 + TrailZero1; + + // Figure out the fewest known-bits operand. + unsigned SmallestOperand = + std::min(TrailBitsKnown0 - TrailZero0, TrailBitsKnown1 - TrailZero1); + unsigned ResultBitsKnown = std::min(SmallestOperand + TrailZ, BitWidth); + + APInt BottomKnown = + Bottom0.getLoBits(TrailBitsKnown0) * Bottom1.getLoBits(TrailBitsKnown1); + + KnownBits Res(BitWidth); + Res.Zero.setHighBits(LeadZ); + Res.Zero |= (~BottomKnown).getLoBits(ResultBitsKnown); + Res.One = BottomKnown.getLoBits(ResultBitsKnown); + return Res; +} + +KnownBits KnownBits::udiv(const KnownBits &LHS, const KnownBits &RHS) { + unsigned BitWidth = LHS.getBitWidth(); + assert(!LHS.hasConflict() && !RHS.hasConflict()); + KnownBits Known(BitWidth); + + // For the purposes of computing leading zeros we can conservatively + // treat a udiv as a logical right shift by the power of 2 known to + // be less than the denominator. + unsigned LeadZ = LHS.countMinLeadingZeros(); + unsigned RHSMaxLeadingZeros = RHS.countMaxLeadingZeros(); + + if (RHSMaxLeadingZeros != BitWidth) + LeadZ = std::min(BitWidth, LeadZ + BitWidth - RHSMaxLeadingZeros - 1); + + Known.Zero.setHighBits(LeadZ); + return Known; +} + +KnownBits KnownBits::urem(const KnownBits &LHS, const KnownBits &RHS) { + unsigned BitWidth = LHS.getBitWidth(); + assert(!LHS.hasConflict() && !RHS.hasConflict()); + KnownBits Known(BitWidth); + + if (RHS.isConstant() && RHS.getConstant().isPowerOf2()) { + // The upper bits are all zero, the lower ones are unchanged. + APInt LowBits = RHS.getConstant() - 1; + Known.Zero = LHS.Zero | ~LowBits; + Known.One = LHS.One & LowBits; + return Known; + } + + // Since the result is less than or equal to either operand, any leading + // zero bits in either operand must also exist in the result. + uint32_t Leaders = + std::max(LHS.countMinLeadingZeros(), RHS.countMinLeadingZeros()); + Known.Zero.setHighBits(Leaders); + return Known; +} + +KnownBits KnownBits::srem(const KnownBits &LHS, const KnownBits &RHS) { + unsigned BitWidth = LHS.getBitWidth(); + assert(!LHS.hasConflict() && !RHS.hasConflict()); + KnownBits Known(BitWidth); + + if (RHS.isConstant() && RHS.getConstant().isPowerOf2()) { + // The low bits of the first operand are unchanged by the srem. + APInt LowBits = RHS.getConstant() - 1; + Known.Zero = LHS.Zero & LowBits; + Known.One = LHS.One & LowBits; + + // If the first operand is non-negative or has all low bits zero, then + // the upper bits are all zero. + if (LHS.isNonNegative() || LowBits.isSubsetOf(LHS.Zero)) + Known.Zero |= ~LowBits; + + // If the first operand is negative and not all low bits are zero, then + // the upper bits are all one. + if (LHS.isNegative() && LowBits.intersects(LHS.One)) + Known.One |= ~LowBits; + return Known; + } + + // The sign bit is the LHS's sign bit, except when the result of the + // remainder is zero. If it's known zero, our sign bit is also zero. + if (LHS.isNonNegative()) + Known.makeNonNegative(); + return Known; +} + KnownBits &KnownBits::operator&=(const KnownBits &RHS) { // Result bit is 0 if either operand bit is 0. Zero |= RHS.Zero; |