1 //===-- KnownBits.cpp - Stores known zeros/ones ---------------------------===//
9 // This file contains a class for representing known zeros and ones used by
27   // Compute known bits of the carry.  in computeForAddCarry()
31   // Compute set of known bits (where all three relevant bits are known).  in computeForAddCarry()
35   APInt Known = std::move(LHSKnownUnion) & RHSKnownUnion & CarryKnownUnion;  in computeForAddCarry()  local
37   // Compute known bits of the result.  in computeForAddCarry()
39   KnownOut.Zero = ~std::move(PossibleSumZero) & Known;  in computeForAddCarry()
40   KnownOut.One = std::move(PossibleSumOne) & Known;  in computeForAddCarry()
168   // known to be less than or equal to Val.  in makeGE()
189   // the minimum possible value of RHS. Likewise for RHS. Any known bits that  in umax()
190   // are common to these two values are also known in the result.  in umax()
289     KnownBits Known;  in shl()  local
291     Known.Zero = LHS.Zero.ushl_ov(ShiftAmt, ShiftedOutZero);  in shl()
292     Known.Zero.setLowBits(ShiftAmt);  in shl()
293     Known.One = LHS.One.ushl_ov(ShiftAmt, ShiftedOutOne);  in shl()
302         Known.makeNonNegative();  in shl()
304         Known.makeNegative();  in shl()
306     return Known;  in shl()
310   KnownBits Known(BitWidth);  in shl()  local
315     Known.Zero.setLowBits(MinShiftAmount);  in shl()
317       Known.makeNonNegative();  in shl()
318     return Known;  in shl()
336     Known.Zero.setLowBits(LHS.countMinTrailingZeros());  in shl()
338       Known.One.setSignBit();  in shl()
341         Known.makeNonNegative();  in shl()
343         Known.makeNegative();  in shl()
345     return Known;  in shl()
351   Known.Zero.setAllBits();  in shl()
352   Known.One.setAllBits();  in shl()
359     Known = Known.intersectWith(ShiftByConst(LHS, ShiftAmt));  in shl()
360     if (Known.isUnknown())  in shl()
365   if (Known.hasConflict())  in shl()
366     Known.setAllZero();  in shl()
367   return Known;  in shl()
374     KnownBits Known = LHS;  in lshr()  local
375     Known.Zero.lshrInPlace(ShiftAmt);  in lshr()
376     Known.One.lshrInPlace(ShiftAmt);  in lshr()
377     // High bits are known zero.  in lshr()
378     Known.Zero.setHighBits(ShiftAmt);  in lshr()
379     return Known;  in lshr()
383   KnownBits Known(BitWidth);  in lshr()  local
388     Known.Zero.setHighBits(MinShiftAmount);  in lshr()
389     return Known;  in lshr()
396   // If exact, bound MaxShiftAmount to first known 1 in LHS.  in lshr()
401       Known.setAllZero();  in lshr()
402       return Known;  in lshr()
409   Known.Zero.setAllBits();  in lshr()
410   Known.One.setAllBits();  in lshr()
417     Known = Known.intersectWith(ShiftByConst(LHS, ShiftAmt));  in lshr()
418     if (Known.isUnknown())  in lshr()
423   if (Known.hasConflict())  in lshr()
424     Known.setAllZero();  in lshr()
425   return Known;  in lshr()
432     KnownBits Known = LHS;  in ashr()  local
433     Known.Zero.ashrInPlace(ShiftAmt);  in ashr()
434     Known.One.ashrInPlace(ShiftAmt);  in ashr()
435     return Known;  in ashr()
439   KnownBits Known(BitWidth);  in ashr()  local
446       Known.setAllZero();  in ashr()
447       return Known;  in ashr()
449     return Known;  in ashr()
456   // If exact, bound MaxShiftAmount to first known 1 in LHS.  in ashr()
461       Known.setAllZero();  in ashr()
462       return Known;  in ashr()
469   Known.Zero.setAllBits();  in ashr()
470   Known.One.setAllBits();  in ashr()
477     Known = Known.intersectWith(ShiftByConst(LHS, ShiftAmt));  in ashr()
478     if (Known.isUnknown())  in ashr()
483   if (Known.hasConflict())  in ashr()
484     Known.setAllZero();  in ashr()
485   return Known;  in ashr()
577     // to the high bits. If we know a known INT_MIN input skip this. The result  in abs()
695     // respectively, so we can preserve known ones/zeros.  in computeForSatAddSub()
742     // We need to clear all the known zeros as we can only use the leading ones.  in computeForSatAddSub()
746     // We need to clear all the known ones as we can only use the leading zero.  in computeForSatAddSub()
804   // Compute the high known-0 bits by multiplying the unsigned max of each side.  in mul()
821   // We can infer at least the minimum number of known trailing bits  in mul()
857   // Where C5, C6 describe the known bits of %a, %b  in mul()
858   // C1, C2 describe the known bottom bits of %a, %b.  in mul()
859   // C7 describes the mask of the known bits of the result.  in mul()
871   // Figure out the fewest known-bits operand.  in mul()
910 static KnownBits divComputeLowBit(KnownBits Known, const KnownBits &LHS,  in divComputeLowBit()  argument
914     return Known;  in divComputeLowBit()
920     Known.One.setBit(0);  in divComputeLowBit()
928     Known.Zero.setLowBits(MinTZ);  in divComputeLowBit()
931       Known.One.setBit(MinTZ);  in divComputeLowBit()
935     Known.setAllZero();  in divComputeLowBit()
940   if (Known.hasConflict())  in divComputeLowBit()
941     Known.setAllZero();  in divComputeLowBit()
943   return Known;  in divComputeLowBit()
953   KnownBits Known(BitWidth);  in sdiv()  local
956     // Result is either known Zero or UB. Return Zero either way.  in sdiv()
958     Known.setAllZero();  in sdiv()
959     return Known;  in sdiv()
991       Known.Zero.setHighBits(LeadZ);  in sdiv()
994       Known.One.setHighBits(LeadO);  in sdiv()
998   Known = divComputeLowBit(Known, LHS, RHS, Exact);  in sdiv()
999   return Known;  in sdiv()
1005   KnownBits Known(BitWidth);  in udiv()  local
1008     // Result is either known Zero or UB. Return Zero either way.  in udiv()
1010     Known.setAllZero();  in udiv()
1011     return Known;  in udiv()
1023   Known.Zero.setHighBits(LeadZ);  in udiv()
1024   Known = divComputeLowBit(Known, LHS, RHS, Exact);  in udiv()
1026   return Known;  in udiv()
1043   KnownBits Known = remGetLowBits(LHS, RHS);  in urem()  local
1047     Known.Zero |= HighBits;  in urem()
1048     return Known;  in urem()
1055   Known.Zero.setHighBits(Leaders);  in urem()
1056   return Known;  in urem()
1060   KnownBits Known = remGetLowBits(LHS, RHS);  in srem()  local
1067       Known.Zero |= ~LowBits;  in srem()
1072       Known.One |= ~LowBits;  in srem()
1073     return Known;  in srem()
1080   Known.Zero.setHighBits(LHS.countMinLeadingZeros());  in srem()
1081   return Known;  in srem()
1111   KnownBits Known(Zero, APInt(BitWidth, 0));  in blsi()  local
1113   Known.Zero.setBitsFrom(std::min(Max + 1, BitWidth));  in blsi()
1116     Known.One.setBit(Max);  in blsi()
1117   return Known;  in blsi()
1122   KnownBits Known(BitWidth);  in blsmsk()  local
1124   Known.Zero.setBitsFrom(std::min(Max + 1, BitWidth));  in blsmsk()
1126   Known.One.setLowBits(std::min(Min + 1, BitWidth));  in blsmsk()
1127   return Known;  in blsmsk()