Index: lib/Analysis/InstructionSimplify.cpp
===================================================================
--- lib/Analysis/InstructionSimplify.cpp
+++ lib/Analysis/InstructionSimplify.cpp
@@ -1009,7 +1009,7 @@
   if (!MaxRecurse--)
     return nullptr;
 
-  // If we can prove that the quotient is unsigned less than the divisor, then
+  // If we can prove that the dividend is unsigned less than the divisor, then
   // we know the answer:
   // X / Y --> 0
   // X % Y --> X
@@ -1019,6 +1019,55 @@
   return nullptr;
 }
 
+/// Return true if we can simplify X / Y to 0. Signed remainder can adapt that
+/// answer to simplify X % Y to X.
+static bool signedDivIsZero(Value *X, Value *Y, const SimplifyQuery &Q,
+                            unsigned MaxRecurse) {
+  // Recursion is always used, so bail out at once if we already hit the limit.
+  if (!MaxRecurse--)
+    return false;
+
+  // If we can prove that the dividend magnitude is less than the divisor
+  // magnitude, then we know the answer:
+  // |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;
+}
+
 /// Given operands for an SDiv, see if we can fold the result.
 /// If not, this returns null.
 static Value *SimplifySDivInst(Value *Op0, Value *Op1, const SimplifyQuery &Q,
@@ -1026,6 +1075,9 @@
   if (Value *V = simplifyDiv(Instruction::SDiv, Op0, Op1, Q, MaxRecurse))
     return V;
 
+  if (signedDivIsZero(Op0, Op1, Q, MaxRecurse))
+    return Constant::getNullValue(Op0->getType());
+
   return nullptr;
 }
 
@@ -1057,6 +1109,9 @@
   if (Value *V = simplifyRem(Instruction::SRem, Op0, Op1, Q, MaxRecurse))
     return V;
 
+  if (signedDivIsZero(Op0, Op1, Q, MaxRecurse))
+    return Op0;
+
   return nullptr;
 }
 
Index: test/Transforms/InstCombine/div.ll
===================================================================
--- test/Transforms/InstCombine/div.ll
+++ test/Transforms/InstCombine/div.ll
@@ -532,24 +532,21 @@
   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
Index: test/Transforms/InstSimplify/exact-nsw-nuw.ll
===================================================================
--- test/Transforms/InstSimplify/exact-nsw-nuw.ll
+++ test/Transforms/InstSimplify/exact-nsw-nuw.ll
@@ -60,9 +60,7 @@
 
 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
Index: test/Transforms/InstSimplify/signed-div-rem.ll
===================================================================
--- test/Transforms/InstSimplify/signed-div-rem.ll
+++ test/Transforms/InstSimplify/signed-div-rem.ll
@@ -2,9 +2,7 @@
 
 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
@@ -24,9 +22,7 @@
 
 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
@@ -46,9 +42,7 @@
 
 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
@@ -68,9 +62,7 @@
 
 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
@@ -90,9 +82,7 @@
 
 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
@@ -112,9 +102,7 @@
 
 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
@@ -134,9 +122,7 @@
 
 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
@@ -156,9 +142,7 @@
 
 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
@@ -179,8 +163,7 @@
 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
@@ -201,8 +184,7 @@
 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
@@ -223,8 +205,7 @@
 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
@@ -245,8 +226,7 @@
 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
@@ -267,8 +247,7 @@
 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
@@ -289,8 +268,7 @@
 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
@@ -311,8 +289,7 @@
 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
@@ -333,8 +310,7 @@
 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
@@ -352,3 +328,27 @@
   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
+}
+