Index: lib/Transforms/InstCombine/InstCombineAddSub.cpp
===================================================================
--- lib/Transforms/InstCombine/InstCombineAddSub.cpp
+++ lib/Transforms/InstCombine/InstCombineAddSub.cpp
@@ -1032,6 +1032,107 @@
   return nullptr;
 }
 
+
+// Simplifies X % C0 + (( X / C0 ) % C1) * C0 to X % (C0 * C1).
+Instruction *InstCombiner::SimplifyAddWithRemainder(BinaryOperator &I) {
+  if (I.getOpcode() != Instruction::Add) {
+    return nullptr;
+  }
+
+  // Matches multiplication expression Op * C where C is a constant. Returns
+  // the constant value in C and the other operand in Op. Returns true if such a
+  // match is found.
+  auto match_mul = [](Value *E, Value **Op, uint64_t& C) {
+    ConstantInt *CI;
+    if (match(E, m_Mul(m_Value(*Op), m_ConstantInt(CI))) ||
+        match(E, m_Mul(m_ConstantInt(CI), m_Value(*Op)))) {
+      C = CI->getZExtValue();
+      return true;
+    } else if (match(E, m_Shl(m_Value(*Op), m_ConstantInt(CI)))) {
+      C = 1 << CI->getZExtValue();
+      return true;
+    }
+    return false;
+  };
+
+  // Matches remainder expression Op % C where C is a constant. Returns the
+  // constant value in C and the other operand in Op. Returns the signess of
+  // the remainder operation in IsSigned. Returns true if such a match is
+  // found.
+  auto match_rem = [](Value *E, Value **Op, uint64_t& C, bool& IsSigned) {
+    ConstantInt *CI;
+    if (match(E, m_SRem(m_Value(*Op), m_ConstantInt(CI))) ||
+       match(E, m_URem(m_Value(*Op), m_ConstantInt(CI))) ||
+       (match(E, m_And(m_Value(*Op), m_ConstantInt(CI))) &&
+        isPowerOf2_32(CI->getZExtValue() + 1))) {
+      C = CI->getZExtValue();
+      unsigned Opcode = dyn_cast<Instruction>(E)->getOpcode();
+      if (Opcode == Instruction::And) {
+        C++;
+      }
+      IsSigned = (Opcode == Instruction::SRem);
+      return true;
+    }
+    return false;
+  };
+
+  // Matches division expression Op / C with the given signess as indicated by
+  // IsSigned, where C is a constant. Returns the constant value in C and the
+  // other operand in Op. Returns true if such a match is found.
+  auto match_div = [](Value *E, Value **Op, uint64_t& C, bool IsSigned) {
+    ConstantInt *CI;
+    if (IsSigned && match(E, m_SDiv(m_Value(*Op), m_ConstantInt(CI)))) {
+      C = CI->getZExtValue();
+      return true;
+    } else if (!IsSigned &&
+               (match(E, m_UDiv(m_Value(*Op), m_ConstantInt(CI))) ||
+                match(E, m_LShr(m_Value(*Op), m_ConstantInt(CI))))) {
+      C = CI->getZExtValue();
+      if (dyn_cast<Instruction>(E)->getOpcode() == Instruction::LShr) {
+        C = 1 << C;
+      }
+      return true;
+    }
+    return false;
+  };
+
+  Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
+  Value *X, *MulOpv;
+  uint64_t C0, MulOpc;
+  bool IsSigned;
+  if (((match_rem(LHS, &X, C0, IsSigned) && match_mul(RHS, &MulOpv, MulOpc))
+      || (match_rem(RHS, &X, C0, IsSigned) &&
+          match_mul(LHS, &MulOpv, MulOpc))) && C0 == MulOpc) {
+    Value *RemOpv;
+    uint64_t C1;
+    bool IsSigned_2;
+    if (match_rem(MulOpv, &RemOpv, C1, IsSigned_2) &&
+        IsSigned == IsSigned_2) {
+      Value *DivOpv;
+      uint64_t DivOpc;
+      if (match_div(RemOpv, &DivOpv, DivOpc, IsSigned) && X == DivOpv
+          && C0 == DivOpc) {
+        Value *C0_C1 = ConstantInt::get(X->getType(), C0*C1, IsSigned);
+        Value *NewVal;
+        if (IsSigned) {
+          NewVal = Builder.CreateSRem(X, C0_C1, "srem");
+        } else {
+          NewVal = Builder.CreateURem(X, C0_C1, "urem");
+        }
+        Instruction *NewInst = dyn_cast<Instruction>(NewVal);
+        if (NewInst->getParent()) {
+          // It is an existing instruction.
+          return replaceInstUsesWith(I, NewInst);
+        } else {
+          return NewInst;
+        }
+      }
+    }
+  }
+
+  return nullptr;
+}
+
 Instruction *InstCombiner::visitAdd(BinaryOperator &I) {
   bool Changed = SimplifyAssociativeOrCommutative(I);
   if (Value *V = SimplifyVectorOp(I))
@@ -1124,6 +1225,11 @@
   if (Value *V = checkForNegativeOperand(I, Builder))
     return replaceInstUsesWith(I, V);
 
+  // X % C0 + (( X / C0 ) % C1) * C0 => X % (C0 * C1)
+  if (Instruction *Inst = SimplifyAddWithRemainder(I)) {
+    return Inst;
+  }
+
   // A+B --> A|B iff A and B have no bits set in common.
   if (haveNoCommonBitsSet(LHS, RHS, DL, &AC, &I, &DT))
     return BinaryOperator::CreateOr(LHS, RHS);
Index: lib/Transforms/InstCombine/InstCombineInternal.h
===================================================================
--- lib/Transforms/InstCombine/InstCombineInternal.h
+++ lib/Transforms/InstCombine/InstCombineInternal.h
@@ -626,6 +626,13 @@
   /// value, or null if it didn't simplify.
   Value *SimplifyUsingDistributiveLaws(BinaryOperator &I);
 
+  /// \brief Tries to simplify add operations using the definition of remainder.
+  ///
+  /// The definition of remainder is X % C = X - (X / C ) * C. The add
+  /// expression X % C0 + (( X / C0 ) % C1) * C0 can be simplified to
+  /// X % (C0 * C1)
+  Instruction *SimplifyAddWithRemainder(BinaryOperator &I);
+
   // Binary Op helper for select operations where the expression can be
   // efficiently reorganized.
   Value *SimplifySelectsFeedingBinaryOp(BinaryOperator &I, Value *LHS,
Index: test/Transforms/InstCombine/add4.ll
===================================================================
--- /dev/null
+++ test/Transforms/InstCombine/add4.ll
@@ -0,0 +1,66 @@
+; RUN: opt < %s -instcombine -S | FileCheck %s
+; Test transformation: X % C0 + (( X / C0 ) % C1) * C0 => X % (C0 * C1)
+
+define i64 @match_unsigned(i64 %x) {
+  %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
+; CHECK-LABEL: @match_unsigned(
+; CHECK-NEXT: [[UREM:[%a-z0-9]+]] = urem i64 %x, 19136
+; CHECK-NEXT: ret i64 [[UREM]]
+}
+
+define i64 @match_andAsRem_lshrAsDiv_shlAsMul(i64 %x) {
+  %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
+; CHECK-LABEL: @match_andAsRem_lshrAsDiv_shlAsMul(
+; CHECK-NEXT: [[UREM:[%a-z0-9]+]] = urem i64 %x, 576
+; CHECK-NEXT: ret i64 [[UREM]]
+}
+
+define i64 @match_signed(i64 %x) {
+  %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
+; CHECK-LABEL: @match_signed(
+; CHECK-NEXT: [[SREM:[%a-z0-9]+]] = srem i64 %x, 172224
+; CHECK-NEXT: ret i64 [[SREM]]
+}
+
+define i64 @not_match_inconsistent_signs(i64 %x) {
+  %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
+; CHECK-LABEL: @not_match_inconsistent_signs(
+; CHECK: [[ADD:[%a-z0-9]+]] = add
+; CHECK-NEXT: ret i64 [[ADD]]
+}
+
+define i64 @not_match_inconsistent_values(i64 %x) {
+  %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
+; CHECK-LABEL: @not_match_inconsistent_values(
+; CHECK: [[ADD:[%a-z0-9]+]] = add
+; CHECK-NEXT: ret i64 [[ADD]]
+}