Index: llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp
===================================================================
--- llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp
+++ llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp
@@ -1306,15 +1306,15 @@
   // X % C0 + (( X / C0 ) % C1) * C0 => X % (C0 * C1)
   if (Value *V = SimplifyAddWithRemainder(I)) return replaceInstUsesWith(I, V);
 
-  // ((X / C1) << C2) + X => X % C1
-  // where C1 = 1 << C2
+  // ((X / C1) << C2) + X => X % -C1
+  // where -C1 = 1 << C2
   const APInt *C1, *C2;
   if (match(LHS, m_Shl(m_SDiv(m_Value(A), m_APInt(C1)), m_APInt(C2)))) {
     if ((RHS == A) && C1->abs().isPowerOf2() && C1->isNegative()) {
       APInt one(C2->getBitWidth(), 1);
       if ((C1->abs() == one.shl(*C2)) && C2->sgt(one)) {
         Constant *NewRHS = ConstantInt::get(RHS->getType(), C1->abs());
-        return replaceInstUsesWith(I, Builder.CreateSRem(RHS, NewRHS, "srem"));
+        return BinaryOperator::CreateSRem(RHS, NewRHS);
       }
     }
   }
Index: llvm/test/Transforms/InstCombine/add-shl-sdiv-to-srem.ll
===================================================================
--- /dev/null
+++ llvm/test/Transforms/InstCombine/add-shl-sdiv-to-srem.ll
@@ -0,0 +1,142 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -instcombine -S | FileCheck %s
+
+define i8 @add-shl-sdiv-i8-2(i8 %x) {
+; CHECK-LABEL: @add-shl-sdiv-i8-2(
+; CHECK-NEXT:    [[RZ:%.*]] = srem i8 [[X:%.*]], 4
+; CHECK-NEXT:    ret i8 [[RZ]]
+;
+  %sd = sdiv i8 %x, -4
+  %sl = shl i8 %sd, 2
+  %rz = add i8 %sl, %x
+  ret i8 %rz
+}
+
+define i8 @add-shl-sdiv-i8-6(i8 %x) {
+; CHECK-LABEL: @add-shl-sdiv-i8-6(
+; CHECK-NEXT:    [[RZ:%.*]] = srem i8 [[X:%.*]], 64
+; CHECK-NEXT:    ret i8 [[RZ]]
+;
+  %sd = sdiv i8 %x, -64
+  %sl = shl i8 %sd, 6
+  %rz = add i8 %sl, %x
+  ret i8 %rz
+}
+
+define i32 @add-shl-sdiv-i32-30(i32 %x) {
+; CHECK-LABEL: @add-shl-sdiv-i32-30(
+; CHECK-NEXT:    [[RZ:%.*]] = srem i32 [[X:%.*]], 1073741824
+; CHECK-NEXT:    ret i32 [[RZ]]
+;
+  %sd = sdiv i32 %x, -1073741824
+  %sl = shl i32 %sd, 30
+  %rz = add i32 %sl, %x
+  ret i32 %rz
+}
+
+; Splat vectors
+
+define <3 x i8> @add-shl-sdiv-3xi8-2(<3 x i8> %x) {
+; CHECK-LABEL: @add-shl-sdiv-3xi8-2(
+; CHECK-NEXT:    [[RZ:%.*]] = srem <3 x i8> [[X:%.*]], <i8 4, i8 4, i8 4>
+; CHECK-NEXT:    ret <3 x i8> [[RZ]]
+;
+  %sd = sdiv <3 x i8> %x, <i8 -4, i8 -4, i8 -4>
+  %sl = shl <3 x i8> %sd, <i8 2, i8 2, i8 2>
+  %rz = add <3 x i8> %sl, %x
+  ret <3 x i8> %rz
+}
+
+define <2 x i64> @add-shl-sdiv-2xi64-5(<2 x i64> %x) {
+; CHECK-LABEL: @add-shl-sdiv-2xi64-5(
+; CHECK-NEXT:    [[RZ:%.*]] = srem <2 x i64> [[X:%.*]], <i64 32, i64 32>
+; CHECK-NEXT:    ret <2 x i64> [[RZ]]
+;
+  %sd = sdiv <2 x i64> %x, <i64 -32, i64 -32>
+  %sl = shl <2 x i64> %sd, <i64 5, i64 5>
+  %rz = add <2 x i64> %sl, %x
+  ret <2 x i64> %rz
+}
+
+; One-use tests
+
+declare void @use32(i32)
+define i32 @add-shl-sdiv-i32-4-use-1(i32 %x) {
+; CHECK-LABEL: @add-shl-sdiv-i32-4-use-1(
+; CHECK-NEXT:    call void @use32(i32 [[X:%.*]])
+; CHECK-NEXT:    [[RZ:%.*]] = srem i32 [[X]], 16
+; CHECK-NEXT:    ret i32 [[RZ]]
+;
+  call void @use32(i32 %x)
+  %sd = sdiv i32 %x, -16
+  %sl = shl i32 %sd, 4
+  %rz = add i32 %sl, %x
+  ret i32 %rz
+}
+
+define i32 @add-shl-sdiv-i32-4-use-2(i32 %x) {
+; CHECK-LABEL: @add-shl-sdiv-i32-4-use-2(
+; CHECK-NEXT:    [[SD:%.*]] = sdiv i32 [[X:%.*]], -16
+; CHECK-NEXT:    call void @use32(i32 [[SD]])
+; CHECK-NEXT:    [[RZ:%.*]] = srem i32 [[X]], 16
+; CHECK-NEXT:    ret i32 [[RZ]]
+;
+  %sd = sdiv i32 %x, -16
+  call void @use32(i32 %sd)
+  %sl = shl i32 %sd, 4
+  %rz = add i32 %sl, %x
+  ret i32 %rz
+}
+
+define i32 @add-shl-sdiv-i32-4-use-3(i32 %x) {
+; CHECK-LABEL: @add-shl-sdiv-i32-4-use-3(
+; CHECK-NEXT:    [[SD:%.*]] = sdiv i32 [[X:%.*]], -16
+; CHECK-NEXT:    [[SL:%.*]] = shl i32 [[SD]], 4
+; CHECK-NEXT:    call void @use32(i32 [[SL]])
+; CHECK-NEXT:    [[RZ:%.*]] = srem i32 [[X]], 16
+; CHECK-NEXT:    ret i32 [[RZ]]
+;
+  %sd = sdiv i32 %x, -16
+  %sl = shl i32 %sd, 4
+  call void @use32(i32 %sl)
+  %rz = add i32 %sl, %x
+  ret i32 %rz
+}
+
+; Negative
+
+define i8 @add-shl-sdiv-negative-1(i8 %x) {
+; CHECK-LABEL: @add-shl-sdiv-negative-1(
+; CHECK-NEXT:    [[SD:%.*]] = sdiv i8 [[X:%.*]], 4
+; CHECK-NEXT:    [[SL:%.*]] = shl nsw i8 [[SD]], 2
+; CHECK-NEXT:    [[RZ:%.*]] = add i8 [[SL]], [[X]]
+; CHECK-NEXT:    ret i8 [[RZ]]
+;
+  %sd = sdiv i8 %x, 4
+  %sl = shl i8 %sd, 2
+  %rz = add i8 %sl, %x
+  ret i8 %rz
+}
+
+define <3 x i8> @add-shl-sdiv-negative-2(<3 x i8> %x) {
+; CHECK-LABEL: @add-shl-sdiv-negative-2(
+; CHECK-NEXT:    [[SD:%.*]] = sdiv <3 x i8> [[X:%.*]], <i8 -5, i8 -5, i8 -5>
+; CHECK-NEXT:    [[SL:%.*]] = shl <3 x i8> [[SD]], <i8 2, i8 2, i8 2>
+; CHECK-NEXT:    [[RZ:%.*]] = add <3 x i8> [[SL]], [[X]]
+; CHECK-NEXT:    ret <3 x i8> [[RZ]]
+;
+  %sd = sdiv <3 x i8> %x, <i8 -5, i8 -5, i8 -5>
+  %sl = shl <3 x i8> %sd, <i8 2, i8 2, i8 2>
+  %rz = add <3 x i8> %sl, %x
+  ret <3 x i8> %rz
+}
+
+define <2 x i64> @add-shl-sdiv-negative-3(<2 x i64> %x) {
+; CHECK-LABEL: @add-shl-sdiv-negative-3(
+; CHECK-NEXT:    ret <2 x i64> undef
+;
+  %sd = sdiv <2 x i64> %x, <i64 32, i64 32>
+  %sl = shl <2 x i64> %sd, <i64 -5, i64 -5>
+  %rz = add <2 x i64> %sl, %x
+  ret <2 x i64> %rz
+}
Index: llvm/test/Transforms/InstCombine/icmp-div-constant.ll
===================================================================
--- llvm/test/Transforms/InstCombine/icmp-div-constant.ll
+++ llvm/test/Transforms/InstCombine/icmp-div-constant.ll
@@ -38,19 +38,6 @@
   ret i1 %r
 }
 
-define i1 @is_rem32_pos_decomposed_i8(i8 %x) {
-; CHECK-LABEL: @is_rem32_pos_decomposed_i8(
-; CHECK-NEXT:    [[TMP1:%.*]] = and i8 [[X:%.*]], -97
-; CHECK-NEXT:    [[R:%.*]] = icmp sgt i8 [[TMP1]], 0
-; CHECK-NEXT:    ret i1 [[R]]
-;
-  %d = sdiv i8 %x, 32
-  %m = mul nsw i8 %d, 32
-  %s = sub nsw i8 %x, %m
-  %r = icmp eq i8 %s, 0
-  ret i1 %r
-}
-
 ; i16 -32765 == 32771 == 0b1000000000000011
 
 define i1 @is_rem4_neg_i16(i16 %x) {