[InstSimplify] fold sdiv/srem based on compare of dividend and divisor

[spatel]

Summary

This should bring signed div/rem analysis up to the same level as unsigned. We use icmp simplification to determine when the divisor is known greater than the dividend.

It's possible I've been staring at this too long and made it more complicated than necessary.

Here are attempts to prove correctness in Alive:
http://rise4fun.com/Alive/TRQp
http://rise4fun.com/Alive/DMs

Each positive test is followed by a negative test to show that we're not overstepping the boundaries of the known bits.

[majnemer]

lib/Analysis/InstructionSimplify.cpp

1022–1023 ↗

(On Diff #114686)

You could make this a little simpler by getting rid of the IsDiv flag.
The remainder side could do something like:

if (Constant *C = dyn_cast_or_null<Constant>(simplifySignedDiv(Op0, Op1, Q, MaxRecurse)))
  if (C->isNullValue())
    return Op0;

[spatel]

lib/Analysis/InstructionSimplify.cpp

1022–1023 ↗

(On Diff #114686)

Ah, ok. If we go that route, we could just have this return a bool, then the caller can return the proper value. Let me write that up.

[spatel]

Patch updated:
Let the callers (sdiv or srem) choose the appropriate answer based on a bool return from the common helper.

[nlopes]

I was trying to prove this in Alive, but the proof doesn't go through.
Some corner cases are not correct: http://rise4fun.com/Alive/iVs
For example: 'INT_MIN / something' would be replaced with 0, but shouldn't.

[spatel]

In D37713#868735, @nlopes wrote:

I was trying to prove this in Alive, but the proof doesn't go through.
Some corner cases are not correct: http://rise4fun.com/Alive/iVs
For example: 'INT_MIN / something' would be replaced with 0, but shouldn't.

Yes, you're correct. We can't take abs(signed_min) because that's undefined. But I think you have the wrong formula for the constant divisor cases in your proofs - it should be && rather than ||?
Please have a look:
http://rise4fun.com/Alive/WI5

So I think there are 2 bugs:

1. If the dividend constant isMinSignedValue(), bail out - nothing will prove that division is zero. This case miscompiles with this version of the patch.
2. If the divisor constant isMinSignedValue(), just show that the dividend is *not* the divisor. We miss this optimization with this version of the patch.

[spatel]

Patch updated:
Handle the signed-min-value cases correctly. I've added 2 tests for those possibilities. We also managed to simplify an existing test with the extra check for the signed-min-value divisor.

[nlopes]

LGTM, thanks.
You're right: the Boolean connector for the second transformation was flipped. All good now :)

llvm/trunk/lib/Analysis/InstructionSimplify.cpp

static bool isICmpTrue(ICmpInst::Predicate Pred, Value *LHS, Value *RHS,
                        const SimplifyQuery &Q, unsigned MaxRecurse) {
   Value *V = SimplifyICmpInst(Pred, LHS, RHS, Q, MaxRecurse);
   Constant *C = dyn_cast_or_null<Constant>(V);
   return (C && C->isAllOnesValue());
 }
 
 /// Return true if we can simplify X / Y to 0. Remainder can adapt that answer
 /// to simplify X % Y to X.
-static bool isDivZero(Value *Op0, Value *Op1, const SimplifyQuery &Q,
+static bool isDivZero(Value *X, Value *Y, const SimplifyQuery &Q,
                       unsigned MaxRecurse, bool IsSigned) {
   // Recursion is always used, so bail out at once if we already hit the limit.
   if (!MaxRecurse--)
     return false;
 
   if (IsSigned) {
-    // TODO: Handle signed.
+    // |X| / |Y| --> 0
+    //
+    // We require that 1 operand is a simple constant. That could be extended to
+    // 2 variables if we computed the sign bit for each.
+    //
+    // Make sure that a constant is not the minimum signed value because taking
+    // the abs() of that is undefined.
+    Type *Ty = X->getType();
+    const APInt *C;
+    if (match(X, m_APInt(C)) && !C->isMinSignedValue()) {
+      // Is the variable divisor magnitude always greater than the constant
+      // dividend magnitude?
+      // |Y| > |C| --> Y < -abs(C) or Y > abs(C)
+      Constant *PosDividendC = ConstantInt::get(Ty, C->abs());
+      Constant *NegDividendC = ConstantInt::get(Ty, -C->abs());
+      if (isICmpTrue(CmpInst::ICMP_SLT, Y, NegDividendC, Q, MaxRecurse) ||
+          isICmpTrue(CmpInst::ICMP_SGT, Y, PosDividendC, Q, MaxRecurse))
+        return true;
+    }
+    if (match(Y, m_APInt(C))) {
+      // Special-case: we can't take the abs() of a minimum signed value. If
+      // that's the divisor, then all we have to do is prove that the dividend
+      // is also not the minimum signed value.
+      if (C->isMinSignedValue())
+        return isICmpTrue(CmpInst::ICMP_NE, X, Y, Q, MaxRecurse);
+
+      // Is the variable dividend magnitude always less than the constant
+      // divisor magnitude?
+      // |X| < |C| --> X > -abs(C) and X < abs(C)
+      Constant *PosDivisorC = ConstantInt::get(Ty, C->abs());
+      Constant *NegDivisorC = ConstantInt::get(Ty, -C->abs());
+      if (isICmpTrue(CmpInst::ICMP_SGT, X, NegDivisorC, Q, MaxRecurse) &&
+          isICmpTrue(CmpInst::ICMP_SLT, X, PosDivisorC, Q, MaxRecurse))
+        return true;
+    }
     return false;
   }
 
   // IsSigned == false.
-  // Is the quotient unsigned less than the divisor?
-  return isICmpTrue(ICmpInst::ICMP_ULT, Op0, Op1, Q, MaxRecurse);
+  // Is the dividend unsigned less than the divisor?
+  return isICmpTrue(ICmpInst::ICMP_ULT, X, Y, Q, MaxRecurse);
 }
 
 /// These are simplifications common to SDiv and UDiv.
 static Value *simplifyDiv(Instruction::BinaryOps Opcode, Value *Op0, Value *Op1,
                           const SimplifyQuery &Q, unsigned MaxRecurse) {
   if (Constant *C = foldOrCommuteConstant(Opcode, Op0, Op1, Q))
     return C;
 

llvm/trunk/test/Transforms/InstCombine/div.ll

 ; CHECK-NEXT:    [[DIV:%.*]] = sdiv i32 [[CONV]], 128
 ; CHECK-NEXT:    ret i32 [[DIV]]
 ;
   %conv = sext i8 %x to i32
   %div = sdiv i32 %conv, 128
   ret i32 %div
 }
 
+; When the divisor is known larger than the quotient,
+; InstSimplify should kill it before InstCombine sees it.
+
 define i32 @shrink_no2(i8 %x) {
 ; CHECK-LABEL: @shrink_no2(
-; CHECK-NEXT:    [[CONV:%.*]] = sext i8 %x to i32
-; CHECK-NEXT:    [[DIV:%.*]] = sdiv i32 [[CONV]], -129
-; CHECK-NEXT:    ret i32 [[DIV]]
+; CHECK-NEXT:    ret i32 0
 ;
   %conv = sext i8 %x to i32
   %div = sdiv i32 %conv, -129
   ret i32 %div
 }
 
-; 17 bits are needed to represent 65535 as a signed value, so this shouldn't fold.
-
 define i32 @shrink_no3(i16 %x) {
 ; CHECK-LABEL: @shrink_no3(
-; CHECK-NEXT:    [[CONV:%.*]] = sext i16 %x to i32
-; CHECK-NEXT:    [[DIV:%.*]] = sdiv i32 [[CONV]], 65535
-; CHECK-NEXT:    ret i32 [[DIV]]
+; CHECK-NEXT:    ret i32 0
 ;
   %conv = sext i16 %x to i32
   %div = sdiv i32 %conv, 65535
   ret i32 %div
 }
 

llvm/trunk/test/Transforms/InstSimplify/exact-nsw-nuw.ll

 ;
   %A = udiv i32 %V, -2147483648
   %B = udiv i32 %A, -2147483648
   ret i32 %B
 }
 
 define i32 @div2(i32 %V) {
 ; CHECK-LABEL: @div2(
-; CHECK-NEXT:    [[A:%.*]] = sdiv i32 %V, -1
-; CHECK-NEXT:    [[B:%.*]] = sdiv i32 [[A]], -2147483648
-; CHECK-NEXT:    ret i32 [[B]]
+; CHECK-NEXT:    ret i32 0
 ;
   %A = sdiv i32 %V, -1
   %B = sdiv i32 %A, -2147483648
   ret i32 %B
 }
 

llvm/trunk/test/Transforms/InstSimplify/signed-div-rem.ll

 ; RUN: opt < %s -instsimplify -S | FileCheck %s
 
 define i32 @sdiv_sext_big_divisor(i8 %x) {
 ; CHECK-LABEL: @sdiv_sext_big_divisor(
-; CHECK-NEXT:    [[CONV:%.*]] = sext i8 %x to i32
-; CHECK-NEXT:    [[DIV:%.*]] = sdiv i32 [[CONV]], 129
-; CHECK-NEXT:    ret i32 [[DIV]]
+; CHECK-NEXT:    ret i32 0
 ;
   %conv = sext i8 %x to i32
   %div = sdiv i32 %conv, 129
   ret i32 %div
 }
 
 define i32 @not_sdiv_sext_big_divisor(i8 %x) {
 ; CHECK-LABEL: @not_sdiv_sext_big_divisor(
 ; CHECK-NEXT:    [[CONV:%.*]] = sext i8 %x to i32
 ; CHECK-NEXT:    [[DIV:%.*]] = sdiv i32 [[CONV]], 128
 ; CHECK-NEXT:    ret i32 [[DIV]]
 ;
   %conv = sext i8 %x to i32
   %div = sdiv i32 %conv, 128
   ret i32 %div
 }
 
 define i32 @sdiv_sext_small_divisor(i8 %x) {
 ; CHECK-LABEL: @sdiv_sext_small_divisor(
-; CHECK-NEXT:    [[CONV:%.*]] = sext i8 %x to i32
-; CHECK-NEXT:    [[DIV:%.*]] = sdiv i32 [[CONV]], -129
-; CHECK-NEXT:    ret i32 [[DIV]]
+; CHECK-NEXT:    ret i32 0
 ;
   %conv = sext i8 %x to i32
   %div = sdiv i32 %conv, -129
   ret i32 %div
 }
 
 define i32 @not_sdiv_sext_small_divisor(i8 %x) {
 ; CHECK-LABEL: @not_sdiv_sext_small_divisor(
 ; CHECK-NEXT:    [[CONV:%.*]] = sext i8 %x to i32
 ; CHECK-NEXT:    [[DIV:%.*]] = sdiv i32 [[CONV]], -128
 ; CHECK-NEXT:    ret i32 [[DIV]]
 ;
   %conv = sext i8 %x to i32
   %div = sdiv i32 %conv, -128
   ret i32 %div
 }
 
 define i32 @sdiv_zext_big_divisor(i8 %x) {
 ; CHECK-LABEL: @sdiv_zext_big_divisor(
-; CHECK-NEXT:    [[CONV:%.*]] = zext i8 %x to i32
-; CHECK-NEXT:    [[DIV:%.*]] = sdiv i32 [[CONV]], 256
-; CHECK-NEXT:    ret i32 [[DIV]]
+; CHECK-NEXT:    ret i32 0
 ;
   %conv = zext i8 %x to i32
   %div = sdiv i32 %conv, 256
   ret i32 %div
 }
 
 define i32 @not_sdiv_zext_big_divisor(i8 %x) {
 ; CHECK-LABEL: @not_sdiv_zext_big_divisor(
 ; CHECK-NEXT:    [[CONV:%.*]] = zext i8 %x to i32
 ; CHECK-NEXT:    [[DIV:%.*]] = sdiv i32 [[CONV]], 255
 ; CHECK-NEXT:    ret i32 [[DIV]]
 ;
   %conv = zext i8 %x to i32
   %div = sdiv i32 %conv, 255
   ret i32 %div
 }
 
 define i32 @sdiv_zext_small_divisor(i8 %x) {
 ; CHECK-LABEL: @sdiv_zext_small_divisor(
-; CHECK-NEXT:    [[CONV:%.*]] = zext i8 %x to i32
-; CHECK-NEXT:    [[DIV:%.*]] = sdiv i32 [[CONV]], -256
-; CHECK-NEXT:    ret i32 [[DIV]]
+; CHECK-NEXT:    ret i32 0
 ;
   %conv = zext i8 %x to i32
   %div = sdiv i32 %conv, -256
   ret i32 %div
 }
 
 define i32 @not_sdiv_zext_small_divisor(i8 %x) {
 ; CHECK-LABEL: @not_sdiv_zext_small_divisor(
 ; CHECK-NEXT:    [[CONV:%.*]] = zext i8 %x to i32
 ; CHECK-NEXT:    [[DIV:%.*]] = sdiv i32 [[CONV]], -255
 ; CHECK-NEXT:    ret i32 [[DIV]]
 ;
   %conv = zext i8 %x to i32
   %div = sdiv i32 %conv, -255
   ret i32 %div
 }
 
 define i32 @sdiv_dividend_known_smaller_than_pos_divisor_clear_bits(i32 %x) {
 ; CHECK-LABEL: @sdiv_dividend_known_smaller_than_pos_divisor_clear_bits(
-; CHECK-NEXT:    [[AND:%.*]] = and i32 %x, 253
-; CHECK-NEXT:    [[DIV:%.*]] = sdiv i32 [[AND]], 254
-; CHECK-NEXT:    ret i32 [[DIV]]
+; CHECK-NEXT:    ret i32 0
 ;
   %and = and i32 %x, 253
   %div = sdiv i32 %and, 254
   ret i32 %div
 }
 
 define i32 @not_sdiv_dividend_known_smaller_than_pos_divisor_clear_bits(i32 %x) {
 ; CHECK-LABEL: @not_sdiv_dividend_known_smaller_than_pos_divisor_clear_bits(
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 %x, 253
 ; CHECK-NEXT:    [[DIV:%.*]] = sdiv i32 [[AND]], 253
 ; CHECK-NEXT:    ret i32 [[DIV]]
 ;
   %and = and i32 %x, 253
   %div = sdiv i32 %and, 253
   ret i32 %div
 }
 
 define i32 @sdiv_dividend_known_smaller_than_neg_divisor_clear_bits(i32 %x) {
 ; CHECK-LABEL: @sdiv_dividend_known_smaller_than_neg_divisor_clear_bits(
-; CHECK-NEXT:    [[AND:%.*]] = and i32 %x, 253
-; CHECK-NEXT:    [[DIV:%.*]] = sdiv i32 [[AND]], -254
-; CHECK-NEXT:    ret i32 [[DIV]]
+; CHECK-NEXT:    ret i32 0
 ;
   %and = and i32 %x, 253
   %div = sdiv i32 %and, -254
   ret i32 %div
 }
 
 define i32 @not_sdiv_dividend_known_smaller_than_neg_divisor_clear_bits(i32 %x) {
 ; CHECK-LABEL: @not_sdiv_dividend_known_smaller_than_neg_divisor_clear_bits(
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 %x, 253
 ; CHECK-NEXT:    [[DIV:%.*]] = sdiv i32 [[AND]], -253
 ; CHECK-NEXT:    ret i32 [[DIV]]
 ;
   %and = and i32 %x, 253
   %div = sdiv i32 %and, -253
   ret i32 %div
 }
 
 define i32 @sdiv_dividend_known_smaller_than_pos_divisor_set_bits(i32 %x) {
 ; CHECK-LABEL: @sdiv_dividend_known_smaller_than_pos_divisor_set_bits(
-; CHECK-NEXT:    [[OR:%.*]] = or i32 %x, -253
-; CHECK-NEXT:    [[DIV:%.*]] = sdiv i32 [[OR]], 254
-; CHECK-NEXT:    ret i32 [[DIV]]
+; CHECK-NEXT:    ret i32 0
 ;
   %or = or i32 %x, -253
   %div = sdiv i32 %or, 254
   ret i32 %div
 }
 
 define i32 @not_sdiv_dividend_known_smaller_than_pos_divisor_set_bits(i32 %x) {
 ; CHECK-LABEL: @not_sdiv_dividend_known_smaller_than_pos_divisor_set_bits(
 ; CHECK-NEXT:    [[OR:%.*]] = or i32 %x, -253
 ; CHECK-NEXT:    [[DIV:%.*]] = sdiv i32 [[OR]], 253
 ; CHECK-NEXT:    ret i32 [[DIV]]
 ;
   %or = or i32 %x, -253
   %div = sdiv i32 %or, 253
   ret i32 %div
 }
 
 define i32 @sdiv_dividend_known_smaller_than_neg_divisor_set_bits(i32 %x) {
 ; CHECK-LABEL: @sdiv_dividend_known_smaller_than_neg_divisor_set_bits(
-; CHECK-NEXT:    [[OR:%.*]] = or i32 %x, -253
-; CHECK-NEXT:    [[DIV:%.*]] = sdiv i32 [[OR]], -254
-; CHECK-NEXT:    ret i32 [[DIV]]
+; CHECK-NEXT:    ret i32 0
 ;
   %or = or i32 %x, -253
   %div = sdiv i32 %or, -254
   ret i32 %div
 }
 
 define i32 @not_sdiv_dividend_known_smaller_than_neg_divisor_set_bits(i32 %x) {
 ; CHECK-LABEL: @not_sdiv_dividend_known_smaller_than_neg_divisor_set_bits(
 ; CHECK-NEXT:    [[OR:%.*]] = or i32 %x, -253
 ; CHECK-NEXT:    [[DIV:%.*]] = sdiv i32 [[OR]], -253
 ; CHECK-NEXT:    ret i32 [[DIV]]
 ;
   %or = or i32 %x, -253
   %div = sdiv i32 %or, -253
   ret i32 %div
 }
 
 define i32 @srem_sext_big_divisor(i8 %x) {
 ; CHECK-LABEL: @srem_sext_big_divisor(
 ; CHECK-NEXT:    [[CONV:%.*]] = sext i8 %x to i32
-; CHECK-NEXT:    [[REM:%.*]] = srem i32 [[CONV]], 129
-; CHECK-NEXT:    ret i32 [[REM]]
+; CHECK-NEXT:    ret i32 [[CONV]]
 ;
   %conv = sext i8 %x to i32
   %rem = srem i32 %conv, 129
   ret i32 %rem
 }
 
 define i32 @not_srem_sext_big_divisor(i8 %x) {
 ; CHECK-LABEL: @not_srem_sext_big_divisor(
 ; CHECK-NEXT:    [[CONV:%.*]] = sext i8 %x to i32
 ; CHECK-NEXT:    [[REM:%.*]] = srem i32 [[CONV]], 128
 ; CHECK-NEXT:    ret i32 [[REM]]
 ;
   %conv = sext i8 %x to i32
   %rem = srem i32 %conv, 128
   ret i32 %rem
 }
 
 define i32 @srem_sext_small_divisor(i8 %x) {
 ; CHECK-LABEL: @srem_sext_small_divisor(
 ; CHECK-NEXT:    [[CONV:%.*]] = sext i8 %x to i32
-; CHECK-NEXT:    [[REM:%.*]] = srem i32 [[CONV]], -129
-; CHECK-NEXT:    ret i32 [[REM]]
+; CHECK-NEXT:    ret i32 [[CONV]]
 ;
   %conv = sext i8 %x to i32
   %rem = srem i32 %conv, -129
   ret i32 %rem
 }
 
 define i32 @not_srem_sext_small_divisor(i8 %x) {
 ; CHECK-LABEL: @not_srem_sext_small_divisor(
 ; CHECK-NEXT:    [[CONV:%.*]] = sext i8 %x to i32
 ; CHECK-NEXT:    [[REM:%.*]] = srem i32 [[CONV]], -128
 ; CHECK-NEXT:    ret i32 [[REM]]
 ;
   %conv = sext i8 %x to i32
   %rem = srem i32 %conv, -128
   ret i32 %rem
 }
 
 define i32 @srem_zext_big_divisor(i8 %x) {
 ; CHECK-LABEL: @srem_zext_big_divisor(
 ; CHECK-NEXT:    [[CONV:%.*]] = zext i8 %x to i32
-; CHECK-NEXT:    [[REM:%.*]] = srem i32 [[CONV]], 256
-; CHECK-NEXT:    ret i32 [[REM]]
+; CHECK-NEXT:    ret i32 [[CONV]]
 ;
   %conv = zext i8 %x to i32
   %rem = srem i32 %conv, 256
   ret i32 %rem
 }
 
 define i32 @not_srem_zext_big_divisor(i8 %x) {
 ; CHECK-LABEL: @not_srem_zext_big_divisor(
 ; CHECK-NEXT:    [[CONV:%.*]] = zext i8 %x to i32
 ; CHECK-NEXT:    [[REM:%.*]] = srem i32 [[CONV]], 255
 ; CHECK-NEXT:    ret i32 [[REM]]
 ;
   %conv = zext i8 %x to i32
   %rem = srem i32 %conv, 255
   ret i32 %rem
 }
 
 define i32 @srem_zext_small_divisor(i8 %x) {
 ; CHECK-LABEL: @srem_zext_small_divisor(
 ; CHECK-NEXT:    [[CONV:%.*]] = zext i8 %x to i32
-; CHECK-NEXT:    [[REM:%.*]] = srem i32 [[CONV]], -256
-; CHECK-NEXT:    ret i32 [[REM]]
+; CHECK-NEXT:    ret i32 [[CONV]]
 ;
   %conv = zext i8 %x to i32
   %rem = srem i32 %conv, -256
   ret i32 %rem
 }
 
 define i32 @not_srem_zext_small_divisor(i8 %x) {
 ; CHECK-LABEL: @not_srem_zext_small_divisor(
 ; CHECK-NEXT:    [[CONV:%.*]] = zext i8 %x to i32
 ; CHECK-NEXT:    [[REM:%.*]] = srem i32 [[CONV]], -255
 ; CHECK-NEXT:    ret i32 [[REM]]
 ;
   %conv = zext i8 %x to i32
   %rem = srem i32 %conv, -255
   ret i32 %rem
 }
 
 define i32 @srem_dividend_known_smaller_than_pos_divisor_clear_bits(i32 %x) {
 ; CHECK-LABEL: @srem_dividend_known_smaller_than_pos_divisor_clear_bits(
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 %x, 253
-; CHECK-NEXT:    [[REM:%.*]] = srem i32 [[AND]], 254
-; CHECK-NEXT:    ret i32 [[REM]]
+; CHECK-NEXT:    ret i32 [[AND]]
 ;
   %and = and i32 %x, 253
   %rem = srem i32 %and, 254
   ret i32 %rem
 }
 
 define i32 @not_srem_dividend_known_smaller_than_pos_divisor_clear_bits(i32 %x) {
 ; CHECK-LABEL: @not_srem_dividend_known_smaller_than_pos_divisor_clear_bits(
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 %x, 253
 ; CHECK-NEXT:    [[REM:%.*]] = srem i32 [[AND]], 253
 ; CHECK-NEXT:    ret i32 [[REM]]
 ;
   %and = and i32 %x, 253
   %rem = srem i32 %and, 253
   ret i32 %rem
 }
 
 define i32 @srem_dividend_known_smaller_than_neg_divisor_clear_bits(i32 %x) {
 ; CHECK-LABEL: @srem_dividend_known_smaller_than_neg_divisor_clear_bits(
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 %x, 253
-; CHECK-NEXT:    [[REM:%.*]] = srem i32 [[AND]], -254
-; CHECK-NEXT:    ret i32 [[REM]]
+; CHECK-NEXT:    ret i32 [[AND]]
 ;
   %and = and i32 %x, 253
   %rem = srem i32 %and, -254
   ret i32 %rem
 }
 
 define i32 @not_srem_dividend_known_smaller_than_neg_divisor_clear_bits(i32 %x) {
 ; CHECK-LABEL: @not_srem_dividend_known_smaller_than_neg_divisor_clear_bits(
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 %x, 253
 ; CHECK-NEXT:    [[REM:%.*]] = srem i32 [[AND]], -253
 ; CHECK-NEXT:    ret i32 [[REM]]
 ;
   %and = and i32 %x, 253
   %rem = srem i32 %and, -253
   ret i32 %rem
 }
 
 define i32 @srem_dividend_known_smaller_than_pos_divisor_set_bits(i32 %x) {
 ; CHECK-LABEL: @srem_dividend_known_smaller_than_pos_divisor_set_bits(
 ; CHECK-NEXT:    [[OR:%.*]] = or i32 %x, -253
-; CHECK-NEXT:    [[REM:%.*]] = srem i32 [[OR]], 254
-; CHECK-NEXT:    ret i32 [[REM]]
+; CHECK-NEXT:    ret i32 [[OR]]
 ;
   %or = or i32 %x, -253
   %rem = srem i32 %or, 254
   ret i32 %rem
 }
 
 define i32 @not_srem_dividend_known_smaller_than_pos_divisor_set_bits(i32 %x) {
 ; CHECK-LABEL: @not_srem_dividend_known_smaller_than_pos_divisor_set_bits(
 ; CHECK-NEXT:    [[OR:%.*]] = or i32 %x, -253
 ; CHECK-NEXT:    [[REM:%.*]] = srem i32 [[OR]], 253
 ; CHECK-NEXT:    ret i32 [[REM]]
 ;
   %or = or i32 %x, -253
   %rem = srem i32 %or, 253
   ret i32 %rem
 }
 
 define i32 @srem_dividend_known_smaller_than_neg_divisor_set_bits(i32 %x) {
 ; CHECK-LABEL: @srem_dividend_known_smaller_than_neg_divisor_set_bits(
 ; CHECK-NEXT:    [[OR:%.*]] = or i32 %x, -253
-; CHECK-NEXT:    [[REM:%.*]] = srem i32 [[OR]], -254
-; CHECK-NEXT:    ret i32 [[REM]]
+; CHECK-NEXT:    ret i32 [[OR]]
 ;
   %or = or i32 %x, -253
   %rem = srem i32 %or, -254
   ret i32 %rem
 }
 
 define i32 @not_srem_dividend_known_smaller_than_neg_divisor_set_bits(i32 %x) {
 ; CHECK-LABEL: @not_srem_dividend_known_smaller_than_neg_divisor_set_bits(
 ; CHECK-NEXT:    [[OR:%.*]] = or i32 %x, -253
 ; CHECK-NEXT:    [[REM:%.*]] = srem i32 [[OR]], -253
 ; CHECK-NEXT:    ret i32 [[REM]]
 ;
   %or = or i32 %x, -253
   %rem = srem i32 %or, -253
   ret i32 %rem
 }
 
+; Make sure that we're handling the minimum signed constant correctly - can't fold this.
+
+define i16 @sdiv_min_dividend(i8 %x) {
+; CHECK-LABEL: @sdiv_min_dividend(
+; CHECK-NEXT:    [[Z:%.*]] = zext i8 %x to i16
+; CHECK-NEXT:    [[D:%.*]] = sdiv i16 -32768, [[Z]]
+; CHECK-NEXT:    ret i16 [[D]]
+;
+  %z = zext i8 %x to i16
+  %d = sdiv i16 -32768, %z
+  ret i16 %d
+}
+
+; If the quotient is known to not be -32768, then this can fold.
+
+define i16 @sdiv_min_divisor(i8 %x) {
+; CHECK-LABEL: @sdiv_min_divisor(
+; CHECK-NEXT:    ret i16 0
+;
+  %z = zext i8 %x to i16
+  %d = sdiv i16 %z, -32768
+  ret i16 %d
+}
+