1166 lines · cpp
1//===-- KnownBits.cpp - Stores known zeros/ones ---------------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// This file contains a class for representing known zeros and ones used by10// computeKnownBits.11//12//===----------------------------------------------------------------------===//13 14#include "llvm/Support/KnownBits.h"15#include "llvm/Support/Debug.h"16#include "llvm/Support/raw_ostream.h"17#include <cassert>18 19using namespace llvm;20 21KnownBits KnownBits::flipSignBit(const KnownBits &Val) {22 unsigned SignBitPosition = Val.getBitWidth() - 1;23 APInt Zero = Val.Zero;24 APInt One = Val.One;25 Zero.setBitVal(SignBitPosition, Val.One[SignBitPosition]);26 One.setBitVal(SignBitPosition, Val.Zero[SignBitPosition]);27 return KnownBits(Zero, One);28}29 30static KnownBits computeForAddCarry(const KnownBits &LHS, const KnownBits &RHS,31 bool CarryZero, bool CarryOne) {32 33 APInt PossibleSumZero = LHS.getMaxValue() + RHS.getMaxValue() + !CarryZero;34 APInt PossibleSumOne = LHS.getMinValue() + RHS.getMinValue() + CarryOne;35 36 // Compute known bits of the carry.37 APInt CarryKnownZero = ~(PossibleSumZero ^ LHS.Zero ^ RHS.Zero);38 APInt CarryKnownOne = PossibleSumOne ^ LHS.One ^ RHS.One;39 40 // Compute set of known bits (where all three relevant bits are known).41 APInt LHSKnownUnion = LHS.Zero | LHS.One;42 APInt RHSKnownUnion = RHS.Zero | RHS.One;43 APInt CarryKnownUnion = std::move(CarryKnownZero) | CarryKnownOne;44 APInt Known = std::move(LHSKnownUnion) & RHSKnownUnion & CarryKnownUnion;45 46 // Compute known bits of the result.47 KnownBits KnownOut;48 KnownOut.Zero = ~std::move(PossibleSumZero) & Known;49 KnownOut.One = std::move(PossibleSumOne) & Known;50 return KnownOut;51}52 53KnownBits KnownBits::computeForAddCarry(54 const KnownBits &LHS, const KnownBits &RHS, const KnownBits &Carry) {55 assert(Carry.getBitWidth() == 1 && "Carry must be 1-bit");56 return ::computeForAddCarry(57 LHS, RHS, Carry.Zero.getBoolValue(), Carry.One.getBoolValue());58}59 60KnownBits KnownBits::computeForAddSub(bool Add, bool NSW, bool NUW,61 const KnownBits &LHS,62 const KnownBits &RHS) {63 unsigned BitWidth = LHS.getBitWidth();64 KnownBits KnownOut(BitWidth);65 // This can be a relatively expensive helper, so optimistically save some66 // work.67 if (LHS.isUnknown() && RHS.isUnknown())68 return KnownOut;69 70 if (!LHS.isUnknown() && !RHS.isUnknown()) {71 if (Add) {72 // Sum = LHS + RHS + 073 KnownOut = ::computeForAddCarry(LHS, RHS, /*CarryZero=*/true,74 /*CarryOne=*/false);75 } else {76 // Sum = LHS + ~RHS + 177 KnownBits NotRHS = RHS;78 std::swap(NotRHS.Zero, NotRHS.One);79 KnownOut = ::computeForAddCarry(LHS, NotRHS, /*CarryZero=*/false,80 /*CarryOne=*/true);81 }82 }83 84 // Handle add/sub given nsw and/or nuw.85 if (NUW) {86 if (Add) {87 // (add nuw X, Y)88 APInt MinVal = LHS.getMinValue().uadd_sat(RHS.getMinValue());89 // None of the adds can end up overflowing, so min consecutive highbits90 // in minimum possible of X + Y must all remain set.91 if (NSW) {92 unsigned NumBits = MinVal.trunc(BitWidth - 1).countl_one();93 // If we have NSW as well, we also know we can't overflow the signbit so94 // can start counting from 1 bit back.95 KnownOut.One.setBits(BitWidth - 1 - NumBits, BitWidth - 1);96 }97 KnownOut.One.setHighBits(MinVal.countl_one());98 } else {99 // (sub nuw X, Y)100 APInt MaxVal = LHS.getMaxValue().usub_sat(RHS.getMinValue());101 // None of the subs can overflow at any point, so any common high bits102 // will subtract away and result in zeros.103 if (NSW) {104 // If we have NSW as well, we also know we can't overflow the signbit so105 // can start counting from 1 bit back.106 unsigned NumBits = MaxVal.trunc(BitWidth - 1).countl_zero();107 KnownOut.Zero.setBits(BitWidth - 1 - NumBits, BitWidth - 1);108 }109 KnownOut.Zero.setHighBits(MaxVal.countl_zero());110 }111 }112 113 if (NSW) {114 APInt MinVal;115 APInt MaxVal;116 if (Add) {117 // (add nsw X, Y)118 MinVal = LHS.getSignedMinValue().sadd_sat(RHS.getSignedMinValue());119 MaxVal = LHS.getSignedMaxValue().sadd_sat(RHS.getSignedMaxValue());120 } else {121 // (sub nsw X, Y)122 MinVal = LHS.getSignedMinValue().ssub_sat(RHS.getSignedMaxValue());123 MaxVal = LHS.getSignedMaxValue().ssub_sat(RHS.getSignedMinValue());124 }125 if (MinVal.isNonNegative()) {126 // If min is non-negative, result will always be non-neg (can't overflow127 // around).128 unsigned NumBits = MinVal.trunc(BitWidth - 1).countl_one();129 KnownOut.One.setBits(BitWidth - 1 - NumBits, BitWidth - 1);130 KnownOut.Zero.setSignBit();131 }132 if (MaxVal.isNegative()) {133 // If max is negative, result will always be neg (can't overflow around).134 unsigned NumBits = MaxVal.trunc(BitWidth - 1).countl_zero();135 KnownOut.Zero.setBits(BitWidth - 1 - NumBits, BitWidth - 1);136 KnownOut.One.setSignBit();137 }138 }139 140 // Just return 0 if the nsw/nuw is violated and we have poison.141 if (KnownOut.hasConflict())142 KnownOut.setAllZero();143 return KnownOut;144}145 146KnownBits KnownBits::computeForSubBorrow(const KnownBits &LHS, KnownBits RHS,147 const KnownBits &Borrow) {148 assert(Borrow.getBitWidth() == 1 && "Borrow must be 1-bit");149 150 // LHS - RHS = LHS + ~RHS + 1151 // Carry 1 - Borrow in ::computeForAddCarry152 std::swap(RHS.Zero, RHS.One);153 return ::computeForAddCarry(LHS, RHS,154 /*CarryZero=*/Borrow.One.getBoolValue(),155 /*CarryOne=*/Borrow.Zero.getBoolValue());156}157 158KnownBits KnownBits::sextInReg(unsigned SrcBitWidth) const {159 unsigned BitWidth = getBitWidth();160 assert(0 < SrcBitWidth && SrcBitWidth <= BitWidth &&161 "Illegal sext-in-register");162 163 if (SrcBitWidth == BitWidth)164 return *this;165 166 unsigned ExtBits = BitWidth - SrcBitWidth;167 KnownBits Result;168 Result.One = One << ExtBits;169 Result.Zero = Zero << ExtBits;170 Result.One.ashrInPlace(ExtBits);171 Result.Zero.ashrInPlace(ExtBits);172 return Result;173}174 175KnownBits KnownBits::makeGE(const APInt &Val) const {176 // Count the number of leading bit positions where our underlying value is177 // known to be less than or equal to Val.178 unsigned N = (Zero | Val).countl_one();179 180 // For each of those bit positions, if Val has a 1 in that bit then our181 // underlying value must also have a 1.182 APInt MaskedVal(Val);183 MaskedVal.clearLowBits(getBitWidth() - N);184 return KnownBits(Zero, One | MaskedVal);185}186 187KnownBits KnownBits::umax(const KnownBits &LHS, const KnownBits &RHS) {188 // If we can prove that LHS >= RHS then use LHS as the result. Likewise for189 // RHS. Ideally our caller would already have spotted these cases and190 // optimized away the umax operation, but we handle them here for191 // completeness.192 if (LHS.getMinValue().uge(RHS.getMaxValue()))193 return LHS;194 if (RHS.getMinValue().uge(LHS.getMaxValue()))195 return RHS;196 197 // If the result of the umax is LHS then it must be greater than or equal to198 // the minimum possible value of RHS. Likewise for RHS. Any known bits that199 // are common to these two values are also known in the result.200 KnownBits L = LHS.makeGE(RHS.getMinValue());201 KnownBits R = RHS.makeGE(LHS.getMinValue());202 return L.intersectWith(R);203}204 205KnownBits KnownBits::umin(const KnownBits &LHS, const KnownBits &RHS) {206 // Flip the range of values: [0, 0xFFFFFFFF] <-> [0xFFFFFFFF, 0]207 auto Flip = [](const KnownBits &Val) { return KnownBits(Val.One, Val.Zero); };208 return Flip(umax(Flip(LHS), Flip(RHS)));209}210 211KnownBits KnownBits::smax(const KnownBits &LHS, const KnownBits &RHS) {212 return flipSignBit(umax(flipSignBit(LHS), flipSignBit(RHS)));213}214 215KnownBits KnownBits::smin(const KnownBits &LHS, const KnownBits &RHS) {216 // Flip the range of values: [-0x80000000, 0x7FFFFFFF] <-> [0xFFFFFFFF, 0]217 auto Flip = [](const KnownBits &Val) {218 unsigned SignBitPosition = Val.getBitWidth() - 1;219 APInt Zero = Val.One;220 APInt One = Val.Zero;221 Zero.setBitVal(SignBitPosition, Val.Zero[SignBitPosition]);222 One.setBitVal(SignBitPosition, Val.One[SignBitPosition]);223 return KnownBits(Zero, One);224 };225 return Flip(umax(Flip(LHS), Flip(RHS)));226}227 228KnownBits KnownBits::abdu(const KnownBits &LHS, const KnownBits &RHS) {229 // If we know which argument is larger, return (sub LHS, RHS) or230 // (sub RHS, LHS) directly.231 if (LHS.getMinValue().uge(RHS.getMaxValue()))232 return computeForAddSub(/*Add=*/false, /*NSW=*/false, /*NUW=*/false, LHS,233 RHS);234 if (RHS.getMinValue().uge(LHS.getMaxValue()))235 return computeForAddSub(/*Add=*/false, /*NSW=*/false, /*NUW=*/false, RHS,236 LHS);237 238 // By construction, the subtraction in abdu never has unsigned overflow.239 // Find the common bits between (sub nuw LHS, RHS) and (sub nuw RHS, LHS).240 KnownBits Diff0 =241 computeForAddSub(/*Add=*/false, /*NSW=*/false, /*NUW=*/true, LHS, RHS);242 KnownBits Diff1 =243 computeForAddSub(/*Add=*/false, /*NSW=*/false, /*NUW=*/true, RHS, LHS);244 return Diff0.intersectWith(Diff1);245}246 247KnownBits KnownBits::abds(KnownBits LHS, KnownBits RHS) {248 // If we know which argument is larger, return (sub LHS, RHS) or249 // (sub RHS, LHS) directly.250 if (LHS.getSignedMinValue().sge(RHS.getSignedMaxValue()))251 return computeForAddSub(/*Add=*/false, /*NSW=*/false, /*NUW=*/false, LHS,252 RHS);253 if (RHS.getSignedMinValue().sge(LHS.getSignedMaxValue()))254 return computeForAddSub(/*Add=*/false, /*NSW=*/false, /*NUW=*/false, RHS,255 LHS);256 257 // Shift both arguments from the signed range to the unsigned range, e.g. from258 // [-0x80, 0x7F] to [0, 0xFF]. This allows us to use "sub nuw" below just like259 // abdu does.260 // Note that we can't just use "sub nsw" instead because abds has signed261 // inputs but an unsigned result, which makes the overflow conditions262 // different.263 unsigned SignBitPosition = LHS.getBitWidth() - 1;264 for (auto Arg : {&LHS, &RHS}) {265 bool Tmp = Arg->Zero[SignBitPosition];266 Arg->Zero.setBitVal(SignBitPosition, Arg->One[SignBitPosition]);267 Arg->One.setBitVal(SignBitPosition, Tmp);268 }269 270 // Find the common bits between (sub nuw LHS, RHS) and (sub nuw RHS, LHS).271 KnownBits Diff0 =272 computeForAddSub(/*Add=*/false, /*NSW=*/false, /*NUW=*/true, LHS, RHS);273 KnownBits Diff1 =274 computeForAddSub(/*Add=*/false, /*NSW=*/false, /*NUW=*/true, RHS, LHS);275 return Diff0.intersectWith(Diff1);276}277 278static unsigned getMaxShiftAmount(const APInt &MaxValue, unsigned BitWidth) {279 if (isPowerOf2_32(BitWidth))280 return MaxValue.extractBitsAsZExtValue(Log2_32(BitWidth), 0);281 // This is only an approximate upper bound.282 return MaxValue.getLimitedValue(BitWidth - 1);283}284 285KnownBits KnownBits::shl(const KnownBits &LHS, const KnownBits &RHS, bool NUW,286 bool NSW, bool ShAmtNonZero) {287 unsigned BitWidth = LHS.getBitWidth();288 auto ShiftByConst = [&](const KnownBits &LHS, unsigned ShiftAmt) {289 KnownBits Known;290 bool ShiftedOutZero, ShiftedOutOne;291 Known.Zero = LHS.Zero.ushl_ov(ShiftAmt, ShiftedOutZero);292 Known.Zero.setLowBits(ShiftAmt);293 Known.One = LHS.One.ushl_ov(ShiftAmt, ShiftedOutOne);294 295 // All cases returning poison have been handled by MaxShiftAmount already.296 if (NSW) {297 if (NUW && ShiftAmt != 0)298 // NUW means we can assume anything shifted out was a zero.299 ShiftedOutZero = true;300 301 if (ShiftedOutZero)302 Known.makeNonNegative();303 else if (ShiftedOutOne)304 Known.makeNegative();305 }306 return Known;307 };308 309 // Fast path for a common case when LHS is completely unknown.310 KnownBits Known(BitWidth);311 unsigned MinShiftAmount = RHS.getMinValue().getLimitedValue(BitWidth);312 if (MinShiftAmount == 0 && ShAmtNonZero)313 MinShiftAmount = 1;314 if (LHS.isUnknown()) {315 Known.Zero.setLowBits(MinShiftAmount);316 if (NUW && NSW && MinShiftAmount != 0)317 Known.makeNonNegative();318 return Known;319 }320 321 // Determine maximum shift amount, taking NUW/NSW flags into account.322 APInt MaxValue = RHS.getMaxValue();323 unsigned MaxShiftAmount = getMaxShiftAmount(MaxValue, BitWidth);324 if (NUW && NSW)325 MaxShiftAmount = std::min(MaxShiftAmount, LHS.countMaxLeadingZeros() - 1);326 if (NUW)327 MaxShiftAmount = std::min(MaxShiftAmount, LHS.countMaxLeadingZeros());328 if (NSW)329 MaxShiftAmount = std::min(330 MaxShiftAmount,331 std::max(LHS.countMaxLeadingZeros(), LHS.countMaxLeadingOnes()) - 1);332 333 // Fast path for common case where the shift amount is unknown.334 if (MinShiftAmount == 0 && MaxShiftAmount == BitWidth - 1 &&335 isPowerOf2_32(BitWidth)) {336 Known.Zero.setLowBits(LHS.countMinTrailingZeros());337 if (LHS.isAllOnes())338 Known.One.setSignBit();339 if (NSW) {340 if (LHS.isNonNegative())341 Known.makeNonNegative();342 if (LHS.isNegative())343 Known.makeNegative();344 }345 return Known;346 }347 348 // Find the common bits from all possible shifts.349 unsigned ShiftAmtZeroMask = RHS.Zero.zextOrTrunc(32).getZExtValue();350 unsigned ShiftAmtOneMask = RHS.One.zextOrTrunc(32).getZExtValue();351 Known.setAllConflict();352 for (unsigned ShiftAmt = MinShiftAmount; ShiftAmt <= MaxShiftAmount;353 ++ShiftAmt) {354 // Skip if the shift amount is impossible.355 if ((ShiftAmtZeroMask & ShiftAmt) != 0 ||356 (ShiftAmtOneMask | ShiftAmt) != ShiftAmt)357 continue;358 Known = Known.intersectWith(ShiftByConst(LHS, ShiftAmt));359 if (Known.isUnknown())360 break;361 }362 363 // All shift amounts may result in poison.364 if (Known.hasConflict())365 Known.setAllZero();366 return Known;367}368 369KnownBits KnownBits::lshr(const KnownBits &LHS, const KnownBits &RHS,370 bool ShAmtNonZero, bool Exact) {371 unsigned BitWidth = LHS.getBitWidth();372 auto ShiftByConst = [&](const KnownBits &LHS, unsigned ShiftAmt) {373 KnownBits Known = LHS;374 Known >>= ShiftAmt;375 // High bits are known zero.376 Known.Zero.setHighBits(ShiftAmt);377 return Known;378 };379 380 // Fast path for a common case when LHS is completely unknown.381 KnownBits Known(BitWidth);382 unsigned MinShiftAmount = RHS.getMinValue().getLimitedValue(BitWidth);383 if (MinShiftAmount == 0 && ShAmtNonZero)384 MinShiftAmount = 1;385 if (LHS.isUnknown()) {386 Known.Zero.setHighBits(MinShiftAmount);387 return Known;388 }389 390 // Find the common bits from all possible shifts.391 APInt MaxValue = RHS.getMaxValue();392 unsigned MaxShiftAmount = getMaxShiftAmount(MaxValue, BitWidth);393 394 // If exact, bound MaxShiftAmount to first known 1 in LHS.395 if (Exact) {396 unsigned FirstOne = LHS.countMaxTrailingZeros();397 if (FirstOne < MinShiftAmount) {398 // Always poison. Return zero because we don't like returning conflict.399 Known.setAllZero();400 return Known;401 }402 MaxShiftAmount = std::min(MaxShiftAmount, FirstOne);403 }404 405 unsigned ShiftAmtZeroMask = RHS.Zero.zextOrTrunc(32).getZExtValue();406 unsigned ShiftAmtOneMask = RHS.One.zextOrTrunc(32).getZExtValue();407 Known.setAllConflict();408 for (unsigned ShiftAmt = MinShiftAmount; ShiftAmt <= MaxShiftAmount;409 ++ShiftAmt) {410 // Skip if the shift amount is impossible.411 if ((ShiftAmtZeroMask & ShiftAmt) != 0 ||412 (ShiftAmtOneMask | ShiftAmt) != ShiftAmt)413 continue;414 Known = Known.intersectWith(ShiftByConst(LHS, ShiftAmt));415 if (Known.isUnknown())416 break;417 }418 419 // All shift amounts may result in poison.420 if (Known.hasConflict())421 Known.setAllZero();422 return Known;423}424 425KnownBits KnownBits::ashr(const KnownBits &LHS, const KnownBits &RHS,426 bool ShAmtNonZero, bool Exact) {427 unsigned BitWidth = LHS.getBitWidth();428 auto ShiftByConst = [&](const KnownBits &LHS, unsigned ShiftAmt) {429 KnownBits Known = LHS;430 Known.Zero.ashrInPlace(ShiftAmt);431 Known.One.ashrInPlace(ShiftAmt);432 return Known;433 };434 435 // Fast path for a common case when LHS is completely unknown.436 KnownBits Known(BitWidth);437 unsigned MinShiftAmount = RHS.getMinValue().getLimitedValue(BitWidth);438 if (MinShiftAmount == 0 && ShAmtNonZero)439 MinShiftAmount = 1;440 if (LHS.isUnknown()) {441 if (MinShiftAmount == BitWidth) {442 // Always poison. Return zero because we don't like returning conflict.443 Known.setAllZero();444 return Known;445 }446 return Known;447 }448 449 // Find the common bits from all possible shifts.450 APInt MaxValue = RHS.getMaxValue();451 unsigned MaxShiftAmount = getMaxShiftAmount(MaxValue, BitWidth);452 453 // If exact, bound MaxShiftAmount to first known 1 in LHS.454 if (Exact) {455 unsigned FirstOne = LHS.countMaxTrailingZeros();456 if (FirstOne < MinShiftAmount) {457 // Always poison. Return zero because we don't like returning conflict.458 Known.setAllZero();459 return Known;460 }461 MaxShiftAmount = std::min(MaxShiftAmount, FirstOne);462 }463 464 unsigned ShiftAmtZeroMask = RHS.Zero.zextOrTrunc(32).getZExtValue();465 unsigned ShiftAmtOneMask = RHS.One.zextOrTrunc(32).getZExtValue();466 Known.setAllConflict();467 for (unsigned ShiftAmt = MinShiftAmount; ShiftAmt <= MaxShiftAmount;468 ++ShiftAmt) {469 // Skip if the shift amount is impossible.470 if ((ShiftAmtZeroMask & ShiftAmt) != 0 ||471 (ShiftAmtOneMask | ShiftAmt) != ShiftAmt)472 continue;473 Known = Known.intersectWith(ShiftByConst(LHS, ShiftAmt));474 if (Known.isUnknown())475 break;476 }477 478 // All shift amounts may result in poison.479 if (Known.hasConflict())480 Known.setAllZero();481 return Known;482}483 484std::optional<bool> KnownBits::eq(const KnownBits &LHS, const KnownBits &RHS) {485 if (LHS.isConstant() && RHS.isConstant())486 return std::optional<bool>(LHS.getConstant() == RHS.getConstant());487 if (LHS.One.intersects(RHS.Zero) || RHS.One.intersects(LHS.Zero))488 return std::optional<bool>(false);489 return std::nullopt;490}491 492std::optional<bool> KnownBits::ne(const KnownBits &LHS, const KnownBits &RHS) {493 if (std::optional<bool> KnownEQ = eq(LHS, RHS))494 return std::optional<bool>(!*KnownEQ);495 return std::nullopt;496}497 498std::optional<bool> KnownBits::ugt(const KnownBits &LHS, const KnownBits &RHS) {499 // LHS >u RHS -> false if umax(LHS) <= umax(RHS)500 if (LHS.getMaxValue().ule(RHS.getMinValue()))501 return std::optional<bool>(false);502 // LHS >u RHS -> true if umin(LHS) > umax(RHS)503 if (LHS.getMinValue().ugt(RHS.getMaxValue()))504 return std::optional<bool>(true);505 return std::nullopt;506}507 508std::optional<bool> KnownBits::uge(const KnownBits &LHS, const KnownBits &RHS) {509 if (std::optional<bool> IsUGT = ugt(RHS, LHS))510 return std::optional<bool>(!*IsUGT);511 return std::nullopt;512}513 514std::optional<bool> KnownBits::ult(const KnownBits &LHS, const KnownBits &RHS) {515 return ugt(RHS, LHS);516}517 518std::optional<bool> KnownBits::ule(const KnownBits &LHS, const KnownBits &RHS) {519 return uge(RHS, LHS);520}521 522std::optional<bool> KnownBits::sgt(const KnownBits &LHS, const KnownBits &RHS) {523 // LHS >s RHS -> false if smax(LHS) <= smax(RHS)524 if (LHS.getSignedMaxValue().sle(RHS.getSignedMinValue()))525 return std::optional<bool>(false);526 // LHS >s RHS -> true if smin(LHS) > smax(RHS)527 if (LHS.getSignedMinValue().sgt(RHS.getSignedMaxValue()))528 return std::optional<bool>(true);529 return std::nullopt;530}531 532std::optional<bool> KnownBits::sge(const KnownBits &LHS, const KnownBits &RHS) {533 if (std::optional<bool> KnownSGT = sgt(RHS, LHS))534 return std::optional<bool>(!*KnownSGT);535 return std::nullopt;536}537 538std::optional<bool> KnownBits::slt(const KnownBits &LHS, const KnownBits &RHS) {539 return sgt(RHS, LHS);540}541 542std::optional<bool> KnownBits::sle(const KnownBits &LHS, const KnownBits &RHS) {543 return sge(RHS, LHS);544}545 546KnownBits KnownBits::abs(bool IntMinIsPoison) const {547 // If the source's MSB is zero then we know the rest of the bits already.548 if (isNonNegative())549 return *this;550 551 // Absolute value preserves trailing zero count.552 KnownBits KnownAbs(getBitWidth());553 554 // If the input is negative, then abs(x) == -x.555 if (isNegative()) {556 KnownBits Tmp = *this;557 // Special case for IntMinIsPoison. We know the sign bit is set and we know558 // all the rest of the bits except one to be zero. Since we have559 // IntMinIsPoison, that final bit MUST be a one, as otherwise the input is560 // INT_MIN.561 if (IntMinIsPoison && (Zero.popcount() + 2) == getBitWidth())562 Tmp.One.setBit(countMinTrailingZeros());563 564 KnownAbs = computeForAddSub(565 /*Add*/ false, IntMinIsPoison, /*NUW=*/false,566 KnownBits::makeConstant(APInt(getBitWidth(), 0)), Tmp);567 568 // One more special case for IntMinIsPoison. If we don't know any ones other569 // than the signbit, we know for certain that all the unknowns can't be570 // zero. So if we know high zero bits, but have unknown low bits, we know571 // for certain those high-zero bits will end up as one. This is because,572 // the low bits can't be all zeros, so the +1 in (~x + 1) cannot carry up573 // to the high bits. If we know a known INT_MIN input skip this. The result574 // is poison anyways.575 if (IntMinIsPoison && Tmp.countMinPopulation() == 1 &&576 Tmp.countMaxPopulation() != 1) {577 Tmp.One.clearSignBit();578 Tmp.Zero.setSignBit();579 KnownAbs.One.setBits(getBitWidth() - Tmp.countMinLeadingZeros(),580 getBitWidth() - 1);581 }582 583 } else {584 unsigned MaxTZ = countMaxTrailingZeros();585 unsigned MinTZ = countMinTrailingZeros();586 587 KnownAbs.Zero.setLowBits(MinTZ);588 // If we know the lowest set 1, then preserve it.589 if (MaxTZ == MinTZ && MaxTZ < getBitWidth())590 KnownAbs.One.setBit(MaxTZ);591 592 // We only know that the absolute values's MSB will be zero if INT_MIN is593 // poison, or there is a set bit that isn't the sign bit (otherwise it could594 // be INT_MIN).595 if (IntMinIsPoison || (!One.isZero() && !One.isMinSignedValue())) {596 KnownAbs.One.clearSignBit();597 KnownAbs.Zero.setSignBit();598 }599 }600 601 return KnownAbs;602}603 604static KnownBits computeForSatAddSub(bool Add, bool Signed,605 const KnownBits &LHS,606 const KnownBits &RHS) {607 // We don't see NSW even for sadd/ssub as we want to check if the result has608 // signed overflow.609 unsigned BitWidth = LHS.getBitWidth();610 611 std::optional<bool> Overflow;612 // Even if we can't entirely rule out overflow, we may be able to rule out613 // overflow in one direction. This allows us to potentially keep some of the614 // add/sub bits. I.e if we can't overflow in the positive direction we won't615 // clamp to INT_MAX so we can keep low 0s from the add/sub result.616 bool MayNegClamp = true;617 bool MayPosClamp = true;618 if (Signed) {619 // Easy cases we can rule out any overflow.620 if (Add && ((LHS.isNegative() && RHS.isNonNegative()) ||621 (LHS.isNonNegative() && RHS.isNegative())))622 Overflow = false;623 else if (!Add && (((LHS.isNegative() && RHS.isNegative()) ||624 (LHS.isNonNegative() && RHS.isNonNegative()))))625 Overflow = false;626 else {627 // Check if we may overflow. If we can't rule out overflow then check if628 // we can rule out a direction at least.629 KnownBits UnsignedLHS = LHS;630 KnownBits UnsignedRHS = RHS;631 // Get version of LHS/RHS with clearer signbit. This allows us to detect632 // how the addition/subtraction might overflow into the signbit. Then633 // using the actual known signbits of LHS/RHS, we can figure out which634 // overflows are/aren't possible.635 UnsignedLHS.One.clearSignBit();636 UnsignedLHS.Zero.setSignBit();637 UnsignedRHS.One.clearSignBit();638 UnsignedRHS.Zero.setSignBit();639 KnownBits Res =640 KnownBits::computeForAddSub(Add, /*NSW=*/false,641 /*NUW=*/false, UnsignedLHS, UnsignedRHS);642 if (Add) {643 if (Res.isNegative()) {644 // Only overflow scenario is Pos + Pos.645 MayNegClamp = false;646 // Pos + Pos will overflow with extra signbit.647 if (LHS.isNonNegative() && RHS.isNonNegative())648 Overflow = true;649 } else if (Res.isNonNegative()) {650 // Only overflow scenario is Neg + Neg651 MayPosClamp = false;652 // Neg + Neg will overflow without extra signbit.653 if (LHS.isNegative() && RHS.isNegative())654 Overflow = true;655 }656 // We will never clamp to the opposite sign of N-bit result.657 if (LHS.isNegative() || RHS.isNegative())658 MayPosClamp = false;659 if (LHS.isNonNegative() || RHS.isNonNegative())660 MayNegClamp = false;661 } else {662 if (Res.isNegative()) {663 // Only overflow scenario is Neg - Pos.664 MayPosClamp = false;665 // Neg - Pos will overflow with extra signbit.666 if (LHS.isNegative() && RHS.isNonNegative())667 Overflow = true;668 } else if (Res.isNonNegative()) {669 // Only overflow scenario is Pos - Neg.670 MayNegClamp = false;671 // Pos - Neg will overflow without extra signbit.672 if (LHS.isNonNegative() && RHS.isNegative())673 Overflow = true;674 }675 // We will never clamp to the opposite sign of N-bit result.676 if (LHS.isNegative() || RHS.isNonNegative())677 MayPosClamp = false;678 if (LHS.isNonNegative() || RHS.isNegative())679 MayNegClamp = false;680 }681 }682 // If we have ruled out all clamping, we will never overflow.683 if (!MayNegClamp && !MayPosClamp)684 Overflow = false;685 } else if (Add) {686 // uadd.sat687 bool Of;688 (void)LHS.getMaxValue().uadd_ov(RHS.getMaxValue(), Of);689 if (!Of) {690 Overflow = false;691 } else {692 (void)LHS.getMinValue().uadd_ov(RHS.getMinValue(), Of);693 if (Of)694 Overflow = true;695 }696 } else {697 // usub.sat698 bool Of;699 (void)LHS.getMinValue().usub_ov(RHS.getMaxValue(), Of);700 if (!Of) {701 Overflow = false;702 } else {703 (void)LHS.getMaxValue().usub_ov(RHS.getMinValue(), Of);704 if (Of)705 Overflow = true;706 }707 }708 709 KnownBits Res = KnownBits::computeForAddSub(Add, /*NSW=*/Signed,710 /*NUW=*/!Signed, LHS, RHS);711 712 if (Overflow) {713 // We know whether or not we overflowed.714 if (!(*Overflow)) {715 // No overflow.716 return Res;717 }718 719 // We overflowed720 APInt C;721 if (Signed) {722 // sadd.sat / ssub.sat723 assert(!LHS.isSignUnknown() &&724 "We somehow know overflow without knowing input sign");725 C = LHS.isNegative() ? APInt::getSignedMinValue(BitWidth)726 : APInt::getSignedMaxValue(BitWidth);727 } else if (Add) {728 // uadd.sat729 C = APInt::getMaxValue(BitWidth);730 } else {731 // uadd.sat732 C = APInt::getMinValue(BitWidth);733 }734 735 Res.One = C;736 Res.Zero = ~C;737 return Res;738 }739 740 // We don't know if we overflowed.741 if (Signed) {742 // sadd.sat/ssub.sat743 // We can keep our information about the sign bits.744 if (MayPosClamp)745 Res.Zero.clearLowBits(BitWidth - 1);746 if (MayNegClamp)747 Res.One.clearLowBits(BitWidth - 1);748 } else if (Add) {749 // uadd.sat750 // We need to clear all the known zeros as we can only use the leading ones.751 Res.Zero.clearAllBits();752 } else {753 // usub.sat754 // We need to clear all the known ones as we can only use the leading zero.755 Res.One.clearAllBits();756 }757 758 return Res;759}760 761KnownBits KnownBits::sadd_sat(const KnownBits &LHS, const KnownBits &RHS) {762 return computeForSatAddSub(/*Add*/ true, /*Signed*/ true, LHS, RHS);763}764KnownBits KnownBits::ssub_sat(const KnownBits &LHS, const KnownBits &RHS) {765 return computeForSatAddSub(/*Add*/ false, /*Signed*/ true, LHS, RHS);766}767KnownBits KnownBits::uadd_sat(const KnownBits &LHS, const KnownBits &RHS) {768 return computeForSatAddSub(/*Add*/ true, /*Signed*/ false, LHS, RHS);769}770KnownBits KnownBits::usub_sat(const KnownBits &LHS, const KnownBits &RHS) {771 return computeForSatAddSub(/*Add*/ false, /*Signed*/ false, LHS, RHS);772}773 774static KnownBits avgComputeU(KnownBits LHS, KnownBits RHS, bool IsCeil) {775 unsigned BitWidth = LHS.getBitWidth();776 LHS = LHS.zext(BitWidth + 1);777 RHS = RHS.zext(BitWidth + 1);778 LHS =779 computeForAddCarry(LHS, RHS, /*CarryZero*/ !IsCeil, /*CarryOne*/ IsCeil);780 LHS = LHS.extractBits(BitWidth, 1);781 return LHS;782}783 784KnownBits KnownBits::avgFloorS(const KnownBits &LHS, const KnownBits &RHS) {785 return flipSignBit(avgFloorU(flipSignBit(LHS), flipSignBit(RHS)));786}787 788KnownBits KnownBits::avgFloorU(const KnownBits &LHS, const KnownBits &RHS) {789 return avgComputeU(LHS, RHS, /*IsCeil=*/false);790}791 792KnownBits KnownBits::avgCeilS(const KnownBits &LHS, const KnownBits &RHS) {793 return flipSignBit(avgCeilU(flipSignBit(LHS), flipSignBit(RHS)));794}795 796KnownBits KnownBits::avgCeilU(const KnownBits &LHS, const KnownBits &RHS) {797 return avgComputeU(LHS, RHS, /*IsCeil=*/true);798}799 800KnownBits KnownBits::mul(const KnownBits &LHS, const KnownBits &RHS,801 bool NoUndefSelfMultiply) {802 unsigned BitWidth = LHS.getBitWidth();803 assert(BitWidth == RHS.getBitWidth() && "Operand mismatch");804 assert((!NoUndefSelfMultiply || LHS == RHS) &&805 "Self multiplication knownbits mismatch");806 807 // Compute the high known-0 bits by multiplying the unsigned max of each side.808 // Conservatively, M active bits * N active bits results in M + N bits in the809 // result. But if we know a value is a power-of-2 for example, then this810 // computes one more leading zero.811 // TODO: This could be generalized to number of sign bits (negative numbers).812 APInt UMaxLHS = LHS.getMaxValue();813 APInt UMaxRHS = RHS.getMaxValue();814 815 // For leading zeros in the result to be valid, the unsigned max product must816 // fit in the bitwidth (it must not overflow).817 bool HasOverflow;818 APInt UMaxResult = UMaxLHS.umul_ov(UMaxRHS, HasOverflow);819 unsigned LeadZ = HasOverflow ? 0 : UMaxResult.countl_zero();820 821 // The result of the bottom bits of an integer multiply can be822 // inferred by looking at the bottom bits of both operands and823 // multiplying them together.824 // We can infer at least the minimum number of known trailing bits825 // of both operands. Depending on number of trailing zeros, we can826 // infer more bits, because (a*b) <=> ((a/m) * (b/n)) * (m*n) assuming827 // a and b are divisible by m and n respectively.828 // We then calculate how many of those bits are inferrable and set829 // the output. For example, the i8 mul:830 // a = XXXX1100 (12)831 // b = XXXX1110 (14)832 // We know the bottom 3 bits are zero since the first can be divided by833 // 4 and the second by 2, thus having ((12/4) * (14/2)) * (2*4).834 // Applying the multiplication to the trimmed arguments gets:835 // XX11 (3)836 // X111 (7)837 // -------838 // XX11839 // XX11840 // XX11841 // XX11842 // -------843 // XXXXX01844 // Which allows us to infer the 2 LSBs. Since we're multiplying the result845 // by 8, the bottom 3 bits will be 0, so we can infer a total of 5 bits.846 // The proof for this can be described as:847 // Pre: (C1 >= 0) && (C1 < (1 << C5)) && (C2 >= 0) && (C2 < (1 << C6)) &&848 // (C7 == (1 << (umin(countTrailingZeros(C1), C5) +849 // umin(countTrailingZeros(C2), C6) +850 // umin(C5 - umin(countTrailingZeros(C1), C5),851 // C6 - umin(countTrailingZeros(C2), C6)))) - 1)852 // %aa = shl i8 %a, C5853 // %bb = shl i8 %b, C6854 // %aaa = or i8 %aa, C1855 // %bbb = or i8 %bb, C2856 // %mul = mul i8 %aaa, %bbb857 // %mask = and i8 %mul, C7858 // =>859 // %mask = i8 ((C1*C2)&C7)860 // Where C5, C6 describe the known bits of %a, %b861 // C1, C2 describe the known bottom bits of %a, %b.862 // C7 describes the mask of the known bits of the result.863 const APInt &Bottom0 = LHS.One;864 const APInt &Bottom1 = RHS.One;865 866 // How many times we'd be able to divide each argument by 2 (shr by 1).867 // This gives us the number of trailing zeros on the multiplication result.868 unsigned TrailBitsKnown0 = (LHS.Zero | LHS.One).countr_one();869 unsigned TrailBitsKnown1 = (RHS.Zero | RHS.One).countr_one();870 unsigned TrailZero0 = LHS.countMinTrailingZeros();871 unsigned TrailZero1 = RHS.countMinTrailingZeros();872 unsigned TrailZ = TrailZero0 + TrailZero1;873 874 // Figure out the fewest known-bits operand.875 unsigned SmallestOperand =876 std::min(TrailBitsKnown0 - TrailZero0, TrailBitsKnown1 - TrailZero1);877 unsigned ResultBitsKnown = std::min(SmallestOperand + TrailZ, BitWidth);878 879 APInt BottomKnown =880 Bottom0.getLoBits(TrailBitsKnown0) * Bottom1.getLoBits(TrailBitsKnown1);881 882 KnownBits Res(BitWidth);883 Res.Zero.setHighBits(LeadZ);884 Res.Zero |= (~BottomKnown).getLoBits(ResultBitsKnown);885 Res.One = BottomKnown.getLoBits(ResultBitsKnown);886 887 if (NoUndefSelfMultiply) {888 // If X has at least TZ trailing zeroes, then bit (2 * TZ + 1) must be zero.889 unsigned TwoTZP1 = 2 * TrailZero0 + 1;890 if (TwoTZP1 < BitWidth)891 Res.Zero.setBit(TwoTZP1);892 893 // If X has exactly TZ trailing zeros, then bit (2 * TZ + 2) must also be894 // zero.895 if (TrailZero0 < BitWidth && LHS.One[TrailZero0]) {896 unsigned TwoTZP2 = TwoTZP1 + 1;897 if (TwoTZP2 < BitWidth)898 Res.Zero.setBit(TwoTZP2);899 }900 }901 902 return Res;903}904 905KnownBits KnownBits::mulhs(const KnownBits &LHS, const KnownBits &RHS) {906 unsigned BitWidth = LHS.getBitWidth();907 assert(BitWidth == RHS.getBitWidth() && "Operand mismatch");908 KnownBits WideLHS = LHS.sext(2 * BitWidth);909 KnownBits WideRHS = RHS.sext(2 * BitWidth);910 return mul(WideLHS, WideRHS).extractBits(BitWidth, BitWidth);911}912 913KnownBits KnownBits::mulhu(const KnownBits &LHS, const KnownBits &RHS) {914 unsigned BitWidth = LHS.getBitWidth();915 assert(BitWidth == RHS.getBitWidth() && "Operand mismatch");916 KnownBits WideLHS = LHS.zext(2 * BitWidth);917 KnownBits WideRHS = RHS.zext(2 * BitWidth);918 return mul(WideLHS, WideRHS).extractBits(BitWidth, BitWidth);919}920 921static KnownBits divComputeLowBit(KnownBits Known, const KnownBits &LHS,922 const KnownBits &RHS, bool Exact) {923 924 if (!Exact)925 return Known;926 927 // If LHS is Odd, the result is Odd no matter what.928 // Odd / Odd -> Odd929 // Odd / Even -> Impossible (because its exact division)930 if (LHS.One[0])931 Known.One.setBit(0);932 933 int MinTZ =934 (int)LHS.countMinTrailingZeros() - (int)RHS.countMaxTrailingZeros();935 int MaxTZ =936 (int)LHS.countMaxTrailingZeros() - (int)RHS.countMinTrailingZeros();937 if (MinTZ >= 0) {938 // Result has at least MinTZ trailing zeros.939 Known.Zero.setLowBits(MinTZ);940 if (MinTZ == MaxTZ) {941 // Result has exactly MinTZ trailing zeros.942 Known.One.setBit(MinTZ);943 }944 } else if (MaxTZ < 0) {945 // Poison Result946 Known.setAllZero();947 }948 949 // In the KnownBits exhaustive tests, we have poison inputs for exact values950 // a LOT. If we have a conflict, just return all zeros.951 if (Known.hasConflict())952 Known.setAllZero();953 954 return Known;955}956 957KnownBits KnownBits::sdiv(const KnownBits &LHS, const KnownBits &RHS,958 bool Exact) {959 // Equivalent of `udiv`. We must have caught this before it was folded.960 if (LHS.isNonNegative() && RHS.isNonNegative())961 return udiv(LHS, RHS, Exact);962 963 unsigned BitWidth = LHS.getBitWidth();964 KnownBits Known(BitWidth);965 966 if (LHS.isZero() || RHS.isZero()) {967 // Result is either known Zero or UB. Return Zero either way.968 // Checking this earlier saves us a lot of special cases later on.969 Known.setAllZero();970 return Known;971 }972 973 std::optional<APInt> Res;974 if (LHS.isNegative() && RHS.isNegative()) {975 // Result non-negative.976 APInt Denom = RHS.getSignedMaxValue();977 APInt Num = LHS.getSignedMinValue();978 // INT_MIN/-1 would be a poison result (impossible). Estimate the division979 // as signed max (we will only set sign bit in the result).980 Res = (Num.isMinSignedValue() && Denom.isAllOnes())981 ? APInt::getSignedMaxValue(BitWidth)982 : Num.sdiv(Denom);983 } else if (LHS.isNegative() && RHS.isNonNegative()) {984 // Result is negative if Exact OR -LHS u>= RHS.985 if (Exact || (-LHS.getSignedMaxValue()).uge(RHS.getSignedMaxValue())) {986 APInt Denom = RHS.getSignedMinValue();987 APInt Num = LHS.getSignedMinValue();988 Res = Denom.isZero() ? Num : Num.sdiv(Denom);989 }990 } else if (LHS.isStrictlyPositive() && RHS.isNegative()) {991 // Result is negative if Exact OR LHS u>= -RHS.992 if (Exact || LHS.getSignedMinValue().uge(-RHS.getSignedMinValue())) {993 APInt Denom = RHS.getSignedMaxValue();994 APInt Num = LHS.getSignedMaxValue();995 Res = Num.sdiv(Denom);996 }997 }998 999 if (Res) {1000 if (Res->isNonNegative()) {1001 unsigned LeadZ = Res->countLeadingZeros();1002 Known.Zero.setHighBits(LeadZ);1003 } else {1004 unsigned LeadO = Res->countLeadingOnes();1005 Known.One.setHighBits(LeadO);1006 }1007 }1008 1009 Known = divComputeLowBit(Known, LHS, RHS, Exact);1010 return Known;1011}1012 1013KnownBits KnownBits::udiv(const KnownBits &LHS, const KnownBits &RHS,1014 bool Exact) {1015 unsigned BitWidth = LHS.getBitWidth();1016 KnownBits Known(BitWidth);1017 1018 if (LHS.isZero() || RHS.isZero()) {1019 // Result is either known Zero or UB. Return Zero either way.1020 // Checking this earlier saves us a lot of special cases later on.1021 Known.setAllZero();1022 return Known;1023 }1024 1025 // We can figure out the minimum number of upper zero bits by doing1026 // MaxNumerator / MinDenominator. If the Numerator gets smaller or Denominator1027 // gets larger, the number of upper zero bits increases.1028 APInt MinDenom = RHS.getMinValue();1029 APInt MaxNum = LHS.getMaxValue();1030 APInt MaxRes = MinDenom.isZero() ? MaxNum : MaxNum.udiv(MinDenom);1031 1032 unsigned LeadZ = MaxRes.countLeadingZeros();1033 1034 Known.Zero.setHighBits(LeadZ);1035 Known = divComputeLowBit(Known, LHS, RHS, Exact);1036 1037 return Known;1038}1039 1040KnownBits KnownBits::remGetLowBits(const KnownBits &LHS, const KnownBits &RHS) {1041 unsigned BitWidth = LHS.getBitWidth();1042 if (!RHS.isZero() && RHS.Zero[0]) {1043 // rem X, Y where Y[0:N] is zero will preserve X[0:N] in the result.1044 unsigned RHSZeros = RHS.countMinTrailingZeros();1045 APInt Mask = APInt::getLowBitsSet(BitWidth, RHSZeros);1046 APInt OnesMask = LHS.One & Mask;1047 APInt ZerosMask = LHS.Zero & Mask;1048 return KnownBits(ZerosMask, OnesMask);1049 }1050 return KnownBits(BitWidth);1051}1052 1053KnownBits KnownBits::urem(const KnownBits &LHS, const KnownBits &RHS) {1054 KnownBits Known = remGetLowBits(LHS, RHS);1055 if (RHS.isConstant() && RHS.getConstant().isPowerOf2()) {1056 // NB: Low bits set in `remGetLowBits`.1057 APInt HighBits = ~(RHS.getConstant() - 1);1058 Known.Zero |= HighBits;1059 return Known;1060 }1061 1062 // Since the result is less than or equal to either operand, any leading1063 // zero bits in either operand must also exist in the result.1064 uint32_t Leaders =1065 std::max(LHS.countMinLeadingZeros(), RHS.countMinLeadingZeros());1066 Known.Zero.setHighBits(Leaders);1067 return Known;1068}1069 1070KnownBits KnownBits::srem(const KnownBits &LHS, const KnownBits &RHS) {1071 KnownBits Known = remGetLowBits(LHS, RHS);1072 if (RHS.isConstant() && RHS.getConstant().isPowerOf2()) {1073 // NB: Low bits are set in `remGetLowBits`.1074 APInt LowBits = RHS.getConstant() - 1;1075 // If the first operand is non-negative or has all low bits zero, then1076 // the upper bits are all zero.1077 if (LHS.isNonNegative() || LowBits.isSubsetOf(LHS.Zero))1078 Known.Zero |= ~LowBits;1079 1080 // If the first operand is negative and not all low bits are zero, then1081 // the upper bits are all one.1082 if (LHS.isNegative() && LowBits.intersects(LHS.One))1083 Known.One |= ~LowBits;1084 return Known;1085 }1086 1087 // The sign bit is the LHS's sign bit, except when the result of the1088 // remainder is zero. The magnitude of the result should be less than or1089 // equal to the magnitude of either operand.1090 if (LHS.isNegative() && Known.isNonZero())1091 Known.One.setHighBits(1092 std::max(LHS.countMinLeadingOnes(), RHS.countMinSignBits()));1093 else if (LHS.isNonNegative())1094 Known.Zero.setHighBits(1095 std::max(LHS.countMinLeadingZeros(), RHS.countMinSignBits()));1096 return Known;1097}1098 1099KnownBits &KnownBits::operator&=(const KnownBits &RHS) {1100 // Result bit is 0 if either operand bit is 0.1101 Zero |= RHS.Zero;1102 // Result bit is 1 if both operand bits are 1.1103 One &= RHS.One;1104 return *this;1105}1106 1107KnownBits &KnownBits::operator|=(const KnownBits &RHS) {1108 // Result bit is 0 if both operand bits are 0.1109 Zero &= RHS.Zero;1110 // Result bit is 1 if either operand bit is 1.1111 One |= RHS.One;1112 return *this;1113}1114 1115KnownBits &KnownBits::operator^=(const KnownBits &RHS) {1116 // Result bit is 0 if both operand bits are 0 or both are 1.1117 APInt Z = (Zero & RHS.Zero) | (One & RHS.One);1118 // Result bit is 1 if one operand bit is 0 and the other is 1.1119 One = (Zero & RHS.One) | (One & RHS.Zero);1120 Zero = std::move(Z);1121 return *this;1122}1123 1124KnownBits KnownBits::blsi() const {1125 unsigned BitWidth = getBitWidth();1126 KnownBits Known(Zero, APInt(BitWidth, 0));1127 unsigned Max = countMaxTrailingZeros();1128 Known.Zero.setBitsFrom(std::min(Max + 1, BitWidth));1129 unsigned Min = countMinTrailingZeros();1130 if (Max == Min && Max < BitWidth)1131 Known.One.setBit(Max);1132 return Known;1133}1134 1135KnownBits KnownBits::blsmsk() const {1136 unsigned BitWidth = getBitWidth();1137 KnownBits Known(BitWidth);1138 unsigned Max = countMaxTrailingZeros();1139 Known.Zero.setBitsFrom(std::min(Max + 1, BitWidth));1140 unsigned Min = countMinTrailingZeros();1141 Known.One.setLowBits(std::min(Min + 1, BitWidth));1142 return Known;1143}1144 1145void KnownBits::print(raw_ostream &OS) const {1146 unsigned BitWidth = getBitWidth();1147 for (unsigned I = 0; I < BitWidth; ++I) {1148 unsigned N = BitWidth - I - 1;1149 if (Zero[N] && One[N])1150 OS << "!";1151 else if (Zero[N])1152 OS << "0";1153 else if (One[N])1154 OS << "1";1155 else1156 OS << "?";1157 }1158}1159 1160#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)1161LLVM_DUMP_METHOD void KnownBits::dump() const {1162 print(dbgs());1163 dbgs() << "\n";1164}1165#endif1166