Index: lib/Transforms/InstCombine/InstCombineAddSub.cpp =================================================================== --- lib/Transforms/InstCombine/InstCombineAddSub.cpp +++ lib/Transforms/InstCombine/InstCombineAddSub.cpp @@ -1032,6 +1032,99 @@ 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 MatchMul = [](Value *E, Value *&Op, APInt &C) { + ConstantInt *CI; + if (match(E, m_Mul(m_Value(Op), m_ConstantInt(CI)))) { + C = CI->getValue(); + return true; + } else if (match(E, m_Shl(m_Value(Op), m_ConstantInt(CI)))) { + C = APInt(CI->getBitWidth(), 1); + C <<= CI->getValue(); + 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 signedness of + // the remainder operation in IsSigned. Returns true if such a match is + // found. + auto MatchRem = [](Value *E, Value *&Op, APInt &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))) && + (CI->getValue() + 1).isPowerOf2())) { + C = CI->getValue(); + unsigned Opcode = cast(E)->getOpcode(); + if (Opcode == Instruction::And) + C++; + IsSigned = (Opcode == Instruction::SRem); + return true; + } + return false; + }; + + // Matches division expression Op / C with the given signedness 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 MatchDiv = [](Value *E, Value *&Op, APInt &C, bool IsSigned) { + ConstantInt *CI; + if (IsSigned && match(E, m_SDiv(m_Value(Op), m_ConstantInt(CI)))) { + C = CI->getValue(); + 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->getValue(); + if (cast(E)->getOpcode() == Instruction::LShr) { + C = APInt(CI->getBitWidth(), 1); + C <<= CI->getValue(); + } + return true; + } + return false; + }; + + Value *LHS = I.getOperand(0), *RHS = I.getOperand(1); + Value *X, *MulOpv; + APInt C0, MulOpc; + bool IsSigned; + if (((MatchRem(LHS, X, C0, IsSigned) && MatchMul(RHS, MulOpv, MulOpc)) || + (MatchRem(RHS, X, C0, IsSigned) && MatchMul(LHS, MulOpv, MulOpc))) && + C0 == MulOpc) { + Value *RemOpv; + APInt C1; + bool Rem2_IsSigned; + if (MatchRem(MulOpv, RemOpv, C1, Rem2_IsSigned) && + IsSigned == Rem2_IsSigned) { + Value *DivOpv; + APInt DivOpc; + if (MatchDiv(RemOpv, DivOpv, DivOpc, IsSigned) && X == DivOpv && + C0 == DivOpc) { + Value *C0_C1 = ConstantInt::get(X->getType()->getContext(), C0 * C1); + Value *NewVal; + if (IsSigned) + NewVal = Builder.CreateSRem(X, C0_C1, "srem"); + else + NewVal = Builder.CreateURem(X, C0_C1, "urem"); + Instruction *NewInst = cast(NewVal); + return replaceInstUsesWith(I, NewInst); + } + } + } + + return nullptr; +} + Instruction *InstCombiner::visitAdd(BinaryOperator &I) { bool Changed = SimplifyAssociativeOrCommutative(I); if (Value *V = SimplifyVectorOp(I)) @@ -1124,6 +1217,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 =================================================================== --- test/Transforms/InstCombine/add4.ll +++ test/Transforms/InstCombine/add4.ll @@ -4,8 +4,9 @@ define i64 @match_unsigned(i64 %x) { ; CHECK-LABEL: @match_unsigned( -; CHECK: [[TMP:%.*]] = add -; CHECK-NEXT: ret i64 [[TMP]] +; CHECK-NEXT: bb: +; CHECK-NEXT: [[UREM:%.*]] = urem i64 [[X:%.*]], 19136 +; CHECK-NEXT: ret i64 [[UREM]] ; bb: %tmp = urem i64 %x, 299 @@ -18,8 +19,9 @@ define i64 @match_andAsRem_lshrAsDiv_shlAsMul(i64 %x) { ; CHECK-LABEL: @match_andAsRem_lshrAsDiv_shlAsMul( -; CHECK: [[TMP:%.*]] = or -; CHECK-NEXT: ret i64 [[TMP]] +; CHECK-NEXT: bb: +; CHECK-NEXT: [[UREM:%.*]] = urem i64 [[X:%.*]], 576 +; CHECK-NEXT: ret i64 [[UREM]] ; bb: %tmp = and i64 %x, 63 @@ -32,9 +34,9 @@ define i64 @match_signed(i64 %x) { ; CHECK-LABEL: @match_signed( -; CHECK: [[TMP1:%.*]] = add -; CHECK: [[TMP2:%.*]] = add -; CHECK-NEXT: ret i64 [[TMP2]] +; CHECK-NEXT: bb: +; CHECK-NEXT: [[SREM1:%.*]] = srem i64 [[X:%.*]], 172224 +; CHECK-NEXT: ret i64 [[SREM1]] ; bb: %tmp = srem i64 %x, 299 @@ -51,7 +53,7 @@ define i64 @not_match_inconsistent_signs(i64 %x) { ; CHECK-LABEL: @not_match_inconsistent_signs( -; CHECK: [[TMP:%.*]] = add +; CHECK: [[TMP:%.*]] = add ; CHECK-NEXT: ret i64 [[TMP]] ; bb: @@ -65,7 +67,7 @@ define i64 @not_match_inconsistent_values(i64 %x) { ; CHECK-LABEL: @not_match_inconsistent_values( -; CHECK: [[TMP:%.*]] = add +; CHECK: [[TMP:%.*]] = add ; CHECK-NEXT: ret i64 [[TMP]] ; bb: