Here is the summary.

[bixia]

Summary

Here are the changes.

Some other thigs

[bixia]

• Add a blank line.

lib/Transforms/InstCombine/InstCombineAddSub.cpp

if (match(Op0, m_AShr(m_Shl(m_Value(X), m_APInt(C2)), m_APInt(C3))) &&
       Value *NotX = Builder.CreateNot(X);
       return BinaryOperator::CreateAnd(NotX, ConstantInt::get(Ty, 1));
     }
   }
 
   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 a constant multiplication expression and returns the constant
+  // value in C. Returns true is 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 a constant remainder expression, returns the constant value in
+  // C and the signess of the opcode 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 a constant division expression with the given signess and
+  // returns the constant value in C. 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);
+  DEBUG(llvm::dbgs() << "LHS " << *LHS << "RHS " << *RHS << "\n");
+  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) {
+    DEBUG(llvm::dbgs() << "X " << *X
+          << "C0 " << C0 << "MulOpv " << *MulOpv << "\n");
+    Value *RemOpv;
+    uint64_t C1;
+    bool IsSigned_2;
+    if (match_rem(MulOpv, &RemOpv, C1, IsSigned_2) &&
+        IsSigned == IsSigned_2) {
+      DEBUG(llvm::dbgs() << "RemOpv " << *RemOpv << "C1 " << C1 << "\n");
+      Value *DivOpv;
+      uint64_t DivOpc;
+      if (match_div(RemOpv, &DivOpv, DivOpc, IsSigned) && X == DivOpv
+          && C0 == DivOpc) {
+        DEBUG(llvm::dbgs() << "match \n");
+        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");
+        }
+        DEBUG(llvm::dbgs() << "NewVal " << *NewVal << "/n");
+        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))
     return replaceInstUsesWith(I, V);
 
   Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
   if (Value *V =
           SimplifyAddInst(LHS, RHS, I.hasNoSignedWrap(), I.hasNoUnsignedWrap(),
Instruction *InstCombiner::visitAdd(BinaryOperator &I) {
 
   // A + -B  -->  A - B
   if (match(RHS, m_Neg(m_Value(B))))
     return BinaryOperator::CreateSub(LHS, B);
 
   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);
 
   // FIXME: We already did a check for ConstantInt RHS above this.
   // FIXME: Is this pattern covered by another fold? No regression tests fail on
   // removal.
   if (ConstantInt *CRHS = dyn_cast<ConstantInt>(RHS)) {
if (!I.hasNoSignedWrap() && willNotOverflowSignedAdd(LHS, RHS, I)) {
     Changed = true;
     I.setHasNoSignedWrap(true);
   }
   if (!I.hasNoUnsignedWrap() && willNotOverflowUnsignedAdd(LHS, RHS, I)) {
     Changed = true;
     I.setHasNoUnsignedWrap(true);
   }
 
+
   return Changed ? &I : nullptr;
 }
 
 Instruction *InstCombiner::visitFAdd(BinaryOperator &I) {
   bool Changed = SimplifyAssociativeOrCommutative(I);
   Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
 
   if (Value *V = SimplifyVectorOp(I))

lib/Transforms/InstCombine/InstCombineInternal.h

private:
   /// operation distributes over.
   ///
   /// It does this by either by factorizing out common terms (eg "(A*B)+(A*C)"
   /// -> "A*(B+C)") or expanding out if this results in simplifications (eg: "A
   /// & (B | C) -> (A&B) | (A&C)" if this is a win).  Returns the simplified
   /// 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,
                                         Value *RHS);
 
   /// This tries to simplify binary operations by factorizing out common terms
   /// (e. g. "(A*B)+(A*C)" -> "A*(B+C)").
   Value *tryFactorization(BinaryOperator &, Instruction::BinaryOps, Value *,

test/Transforms/InstCombine/add4.ll

+; 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]]
+}