Index: test/Transforms/InstCombine/add4.ll
===================================================================
--- /dev/null
+++ test/Transforms/InstCombine/add4.ll
@@ -0,0 +1,73 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -instcombine -S | FileCheck %s
+; Test transformation: X % C0 + (( X / C0 ) % C1) * C0 => X % (C0 * C1)
+
+define i64 @match_unsigned(i64 %x) {
+; CHECK-LABEL: @match_unsigned(
+; CHECK:    [[TMP:%.*]] = add
+; CHECK-NEXT:    ret i64 [[TMP]]
+;
+  %1 = urem i64 %x, 299
+  %2 = udiv i64 %x, 299
+  %3 = urem i64 %2, 64
+  %4 = mul i64 %3, 299
+  %5 = add nuw nsw i64 %1, %4
+  ret i64 %5
+}
+
+define i64 @match_andAsRem_lshrAsDiv_shlAsMul(i64 %x) {
+; CHECK-LABEL: @match_andAsRem_lshrAsDiv_shlAsMul(
+; CHECK:    [[TMP:%.*]] = or
+; CHECK-NEXT:    ret i64 [[TMP]]
+;
+  %1 = and i64 %x, 63
+  %2 = lshr i64 %x, 6
+  %3 = urem i64 %2, 9
+  %4 = shl nuw nsw i64 %3, 6
+  %5 = add nuw nsw i64 %1, %4
+  ret i64 %5
+}
+
+define i64 @match_signed(i64 %x) {
+; CHECK-LABEL: @match_signed(
+; CHECK:    [[TMP1:%.*]] = add
+; CHECK:    [[TMP2:%.*]] = add
+; CHECK-NEXT:    ret i64 [[TMP2]]
+;
+  %1 = srem i64 %x, 299
+  %2 = sdiv i64 %x, 299
+  %3 = srem i64 %2, 64
+  %4 = sdiv i64 %x, 19136
+  %5 = srem i64 %4, 9
+  %6 = mul nuw nsw i64 %3, 299
+  %7 = add nuw nsw i64 %1, %6
+  %8 = mul nuw nsw i64 %5, 19136
+  %9 = add nuw nsw i64 %7, %8
+  ret i64 %9
+}
+
+define i64 @not_match_inconsistent_signs(i64 %x) {
+; CHECK-LABEL: @not_match_inconsistent_signs(
+; CHECK:    [[TMP:%.*]] = add
+; CHECK-NEXT:    ret i64 [[TMP]]
+;
+  %1 = urem i64 %x, 299
+  %2 = sdiv i64 %x, 299
+  %3 = urem i64 %2, 64
+  %4 = mul i64 %3, 299
+  %5 = add nuw nsw i64 %1, %4
+  ret i64 %5
+}
+
+define i64 @not_match_inconsistent_values(i64 %x) {
+; CHECK-LABEL: @not_match_inconsistent_values(
+; CHECK:    [[TMP:%.*]] = add
+; CHECK-NEXT:    ret i64 [[TMP]]
+;
+  %1 = urem i64 %x, 299
+  %2 = udiv i64 %x, 29
+  %3 = urem i64 %2, 64
+  %4 = mul i64 %3, 299
+  %5 = add nuw nsw i64 %1, %4
+  ret i64 %5
+}