Restoring authorship annotation for <shadchin@yandex-team.ru>. Commit 2 of 2.

1 files changed, 397 insertions, 397 deletions

diff --git a/contrib/libs/llvm12/lib/Support/KnownBits.cpp b/contrib/libs/llvm12/lib/Support/KnownBits.cpp
index dcd51675e9..3623a54ae4 100644
--- a/contrib/libs/llvm12/lib/Support/KnownBits.cpp
+++ b/contrib/libs/llvm12/lib/Support/KnownBits.cpp
@@ -83,403 +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::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;