[InstCombine] Simplify Add with remainder expressions as operands.

[bixia]

Summary

Simplify integer add expression X % C0 + (( X / C0 ) % C1) * C0 to
X % (C0 * C1). This is a common pattern seen in code generated by the XLA
GPU backend.

Add test cases for this new optimization.

[lebedev.ri]

lib/Transforms/InstCombine/InstCombineAddSub.cpp

1047 ↗

(On Diff #143604)

m_c_Mul()
And please make sure that there is a test for both combinations.

1065 ↗

(On Diff #143604)

The formatting looks off, maybe use clang-format on the diff (you could use a git post-commit hook)

1103 ↗

(On Diff #143604)

You take address of MulOpv, and then immediately deference it in match_rem().
Maybe pass it by reference (Value *&Op)

1229 ↗

(On Diff #143604)

Here and everywhere - no need for {} in such one-line cases.

test/Transforms/InstCombine/add4.ll

1 ↗

(On Diff #143604)

Please use llvm/utils/update_test_checks.py, and ideally split the initial tests (with the output as of trunk) into parent differential, rebase this differential ontop of that one, so the changes are more clear.

[craig.topper]

lib/Transforms/InstCombine/InstCombineAddSub.cpp

1059 ↗

(On Diff #143604)

signess->signedness

1062 ↗

(On Diff #143604)

Can you pass Op as Value *&Op?

1069 ↗

(On Diff #143604)

If you use dyn_cast, you need to check the result isn't null. If it can never fail use 'cast'

1085 ↗

(On Diff #143604)

What guarantees the ConstantInt only uses 64 bits or less?

1114 ↗

(On Diff #143604)

&& should be at the end of the previous line. If they won't fit, bring "X == DivOpv" down. Or just clang-format thsi.

1122 ↗

(On Diff #143604)

Unchecked dyn_cast

1123 ↗

(On Diff #143604)

The IR builder will never give you back an existing instruction. The only optimization it can do is to constant fold, but that wouldn't castable to an Instruction.

[sanjoy]

Some style nits -- will review the content of the patch once these are fixed. You might want to skim through these: https://llvm.org/docs/CodingStandards.html http://llvm.org/docs/ProgrammersManual.html

lib/Transforms/InstCombine/InstCombineAddSub.cpp

1047 ↗

(On Diff #143604)

I'm not sure if m_c_Mul is necessary here -- we should be canonicalizing multiplications such that the constant operand, if there is any, is always the RHS.

1052 ↗

(On Diff #143604)

getZExtValue will crash if the constant does not fit in 64 bits. It is probably better to keep constants as APInt throughout.

[sanjoy]

lib/Transforms/InstCombine/InstCombineAddSub.cpp

1045 ↗

(On Diff #143604)

LLVM naming style is CamelCase so this should be MatchMul.

1066 ↗

(On Diff #143604)

Use m_Power2.

1069 ↗

(On Diff #143604)

dyn_cast<T>(V)->foo() is never necessary. If V is always of type T then use cast<> not dyn_cast<>. If V may not be of type T then dyn_cast<> may return nullptr and cause UB (so you need to check the value returned by dyn_cast<>).

More details at http://llvm.org/docs/ProgrammersManual.html#the-isa-cast-and-dyn-cast-templates

1108 ↗

(On Diff #143604)

IsSigned_2 needs a more descriptive name.

[craig.topper]

I'm not sure I see anything that ensures C1*C2 doesn't overflow. And in particular if C1*C2 overflows and produces 0, the resulting remainder instruction is UB.

[bixia]

• Use instnamer to fix names.

[bixia]

lib/Transforms/InstCombine/InstCombineAddSub.cpp

1047 ↗

(On Diff #143604)

I removed one of the two m_Mul assuming that the operation is canonicalized.

1085 ↗

(On Diff #143604)

Changed to use APInt instead.

[bixia]

• Use instnamer to fix names.

[bixia]

• Use prefix ++ instead of postfix ++.

[sanjoy]

Mostly nits except for the comment with the Alive proofs (didn't get to the meat of the patch yet).

lib/Transforms/InstCombine/InstCombineAddSub.cpp

1035 ↗

(On Diff #143773)

Are these correct interpretations of this transform:

https://rise4fun.com/Alive/j4G (signed)
https://rise4fun.com/Alive/RQB (unsigned)

? If so, Alive seems to think they're incorrect.

1037 ↗

(On Diff #143773)

Can this condition ever be false? You're calling this only from visitAdd right?

1045 ↗

(On Diff #143773)

Use m_APInt instead of manually calling CI->getValue().

1049 ↗

(On Diff #143773)

Is this lifetime of this APInt correct? Won't it go out of scope once MatchMul returns?

1064 ↗

(On Diff #143773)

Use m_APInt here too.

1070 ↗

(On Diff #143773)

Braces around Opcode == Instruction::SRem are not necessary.

1087 ↗

(On Diff #143773)

Probably better to do this as a separate change, but it might be nice to push all of this logic (division as udiv or as an lshr) into a matcher.

1098 ↗

(On Diff #143773)

LLVM style would be MulOpV and MulOpC, but you can also say MulLHS and MulRHS -- you can tell which is constant and which isn't by the C++ type.

1101 ↗

(On Diff #143773)

I don't think you need the ( around the call to MatchRem.

1101 ↗

(On Diff #143773)

I think this sort of thing will be more readable if you give examples of what you're matching using the C++ names right before the if:

// Match I = (X  % C0) + (MulOpv * MulOpc)

etc.

1107 ↗

(On Diff #143773)

Same here:

// Match MulOpv = RemOpv % C1

though here the benefit is less because the code is simpler.

1120 ↗

(On Diff #143773)

Can just be replaceInstUsesWith(I, cast<Instruction>(NewVal)). However, please state why NewVal can not be a constant.

[efriedma]

Fixed Alive proof for the signed case: https://rise4fun.com/Alive/zJr

Granted, I'm pretty sure this patch doesn't check the precondition correctly.

[bixia]

• Use prefix ++ instead of postfix ++.

[bixia]

lib/Transforms/InstCombine/InstCombineAddSub.cpp

1035 ↗

(On Diff #143773)

Added check to make sure C0*C1 does not overflow.

1037 ↗

(On Diff #143773)

Removed.

1049 ↗

(On Diff #143773)

The temp constructed by APInt(...) is copied to C.

1120 ↗

(On Diff #143773)

I put a comment that says NewVal can't be a constant because I is not a constant.

[bixia]

• Applied git clang-format.

[sanjoy]

lib/Transforms/InstCombine/InstCombineAddSub.cpp

1035 ↗

(On Diff #143833)

s/(C0) * C1)/(C0 * C1)/

1041 ↗

(On Diff #143833)

We're not getting much leverage from making these lambdas -- how about making them static helper functions? That'll reduce the indentation and make SimplifyAddWithRemainder a bit smaller.

1042 ↗

(On Diff #143833)

Let's call this something other than CI since CI usually means ConstantInt.

Same comment applies below.

1062 ↗

(On Diff #143833)

Instead of (*CI + 1).isPowerOf2() you can do CI->isAllOnesValue() to avoid the addition and also read a bit cleaner.

1081 ↗

(On Diff #143833)

Can this match a ConstantExpr (which isn't an Instruction and will fail the cast<> below)? Or have we checked before that E is an Instruction?

1095 ↗

(On Diff #143833)

Let's call this MulWillOverflow.

1108 ↗

(On Diff #143833)

Since you're checking this anyway, how about:

// Match I = X % C0 + MulOpV * C0

1114 ↗

(On Diff #143833)

LLVM style will be Rem2IsSigned or InnerRemIsSigned (since 2 isn't very discriminating).

1115 ↗

(On Diff #143833)

Should be MulOpV in the comment.

1120 ↗

(On Diff #143833)

Instead of commenting RemOpV = DivOpV / DivOpC how about commenting RemOpV = X / C0?

1123 ↗

(On Diff #143833)

How about s/C0_C1/NewDivisor ? Generally LLVM coding style does not allow underscores in variable names.

1130 ↗

(On Diff #143833)

The cast<> to Instruction is probably not necessary -- replaceInstUsesWith takes a Value as its second argument.

1231 ↗

(On Diff #143833)

LLVM style avoids braces around single line statements like this.

1232 ↗

(On Diff #143833)

Might be worth being consistent with the previous clause where replaceInstUsesWith is called here, not in the callee.

lib/Transforms/InstCombine/InstCombineInternal.h

629 ↗

(On Diff #143833)

No need for \brief in new doxygen comments -- we now build the docs with autobrief which means the first sentence is automatically considered \brief.

test/Transforms/InstCombine/add4.ll

92 ↗

(On Diff #143833)

You should probably add a test case with where the add does not have nuw or nsw, just to show that these flags are not necessary.

[bixia]

• Remove nuw nsw from the tests.

[bixia]

test/Transforms/InstCombine/add4.ll

92 ↗

(On Diff #143833)

Removed nuw nsw from the tests.

[bixia]

• Removed nuw nsw from the tests.
• Removed \brief from the comment.

[bixia]

• Removed nuw nsw from the tests.

[bixia]

• Removed nuw nsw from the tests.

[bixia]

• Removed nuw nsw from the tests.

[bixia]

lib/Transforms/InstCombine/InstCombineAddSub.cpp

1062 ↗

(On Diff #143833)

the two are not equivalent.

1081 ↗

(On Diff #143833)

Remove the use of the cast.

1087 ↗

(On Diff #143773)

Will consider doing this in another change.

[sanjoy]

lgtm with minor nits.

lib/Transforms/InstCombine/InstCombineAddSub.cpp

1043 ↗

(On Diff #144013)

This is optional, but in these cases I find it easier to avoid the else and write it as:

if (match(E, m_Mul(m_Value(Op), m_APInt(AI)))) {
  C = *AI;
  return true;
}

if (match(E, m_Shl(m_Value(Op), m_APInt(AI)))) {
  C = APInt(AI->getBitWidth(), 1);
  C <<= *AI;
  return true;
}

Same below.

1126 ↗

(On Diff #144013)

LLVM style discourages underscores in variable names.

1128 ↗

(On Diff #144013)

Minor, but a ternary operation may be more readable here.

1233 ↗

(On Diff #144013)

LLVM style says no braces for single line statements.

[bixia]

• Removed nuw nsw from the tests.

llvm/trunk/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;
 }
 
+// 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.
+static bool MatchMul(Value *E, Value *&Op, APInt &C) {
+  const APInt *AI;
+  if (match(E, m_Mul(m_Value(Op), m_APInt(AI)))) {
+    C = *AI;
+    return true;
+  }
+  if (match(E, m_Shl(m_Value(Op), m_APInt(AI)))) {
+    C = APInt(AI->getBitWidth(), 1);
+    C <<= *AI;
+    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.
+static bool MatchRem(Value *E, Value *&Op, APInt &C, bool &IsSigned) {
+  const APInt *AI;
+  IsSigned = false;
+  if (match(E, m_SRem(m_Value(Op), m_APInt(AI)))) {
+    IsSigned = true;
+    C = *AI;
+    return true;
+  }
+  if (match(E, m_URem(m_Value(Op), m_APInt(AI)))) {
+    C = *AI;
+    return true;
+  }
+  if (match(E, m_And(m_Value(Op), m_APInt(AI))) && (*AI + 1).isPowerOf2()) {
+    C = *AI + 1;
+    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.
+static bool MatchDiv(Value *E, Value *&Op, APInt &C, bool IsSigned) {
+  const APInt *AI;
+  if (IsSigned && match(E, m_SDiv(m_Value(Op), m_APInt(AI)))) {
+    C = *AI;
+    return true;
+  }
+  if (!IsSigned) {
+    if (match(E, m_UDiv(m_Value(Op), m_APInt(AI)))) {
+      C = *AI;
+      return true;
+    }
+    if (match(E, m_LShr(m_Value(Op), m_APInt(AI)))) {
+      C = APInt(AI->getBitWidth(), 1);
+      C <<= *AI;
+      return true;
+    }
+  }
+  return false;
+}
+
+// Returns whether C0 * C1 with the given signedness overflows.
+static bool MulWillOverflow(APInt &C0, APInt &C1, bool IsSigned) {
+  bool overflow;
+  if (IsSigned)
+    (void)C0.smul_ov(C1, overflow);
+  else
+    (void)C0.umul_ov(C1, overflow);
+  return overflow;
+}
+
+// Simplifies X % C0 + (( X / C0 ) % C1) * C0 to X % (C0 * C1), where (C0 * C1)
+// does not overflow.
+Value *InstCombiner::SimplifyAddWithRemainder(BinaryOperator &I) {
+  Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
+  Value *X, *MulOpV;
+  APInt C0, MulOpC;
+  bool IsSigned;
+  // Match I = X % C0 + MulOpV * C0
+  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 Rem2IsSigned;
+    // Match MulOpC = RemOpV % C1
+    if (MatchRem(MulOpV, RemOpV, C1, Rem2IsSigned) &&
+        IsSigned == Rem2IsSigned) {
+      Value *DivOpV;
+      APInt DivOpC;
+      // Match RemOpV = X / C0
+      if (MatchDiv(RemOpV, DivOpV, DivOpC, IsSigned) && X == DivOpV &&
+          C0 == DivOpC && !MulWillOverflow(C0, C1, IsSigned)) {
+        Value *NewDivisor =
+            ConstantInt::get(X->getType()->getContext(), C0 * C1);
+        return IsSigned ? Builder.CreateSRem(X, NewDivisor, "srem")
+                        : Builder.CreateURem(X, NewDivisor, "urem");
+      }
+    }
+  }
+
+  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 (Value *V = SimplifyAddWithRemainder(I)) return replaceInstUsesWith(I, V);
+
   // 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)) {

llvm/trunk/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);
 
+  /// 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)
+  Value *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 *,

llvm/trunk/test/Transforms/InstCombine/add4.ll

 ; RUN: opt < %s -instcombine -S | FileCheck %s
 ; ModuleID = 'test/Transforms/InstCombine/add4.ll'
 source_filename = "test/Transforms/InstCombine/add4.ll"
 
 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
   %tmp1 = udiv i64 %x, 299
   %tmp2 = urem i64 %tmp1, 64
   %tmp3 = mul i64 %tmp2, 299
-  %tmp4 = add nuw nsw i64 %tmp, %tmp3
+  %tmp4 = add i64 %tmp, %tmp3
   ret i64 %tmp4
 }
 
 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
   %tmp1 = lshr i64 %x, 6
   %tmp2 = urem i64 %tmp1, 9
-  %tmp3 = shl nuw nsw i64 %tmp2, 6
-  %tmp4 = add nuw nsw i64 %tmp, %tmp3
+  %tmp3 = shl i64 %tmp2, 6
+  %tmp4 = add i64 %tmp, %tmp3
   ret i64 %tmp4
 }
 
 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
   %tmp1 = sdiv i64 %x, 299
   %tmp2 = srem i64 %tmp1, 64
   %tmp3 = sdiv i64 %x, 19136
   %tmp4 = srem i64 %tmp3, 9
-  %tmp5 = mul nuw nsw i64 %tmp2, 299
-  %tmp6 = add nuw nsw i64 %tmp, %tmp5
-  %tmp7 = mul nuw nsw i64 %tmp4, 19136
-  %tmp8 = add nuw nsw i64 %tmp6, %tmp7
+  %tmp5 = mul i64 %tmp2, 299
+  %tmp6 = add i64 %tmp, %tmp5
+  %tmp7 = mul i64 %tmp4, 19136
+  %tmp8 = add i64 %tmp6, %tmp7
   ret i64 %tmp8
 }
 
 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:
   %tmp = urem i64 %x, 299
   %tmp1 = sdiv i64 %x, 299
   %tmp2 = urem i64 %tmp1, 64
   %tmp3 = mul i64 %tmp2, 299
-  %tmp4 = add nuw nsw i64 %tmp, %tmp3
+  %tmp4 = add i64 %tmp, %tmp3
   ret i64 %tmp4
 }
 
 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:
   %tmp = urem i64 %x, 299
   %tmp1 = udiv i64 %x, 29
   %tmp2 = urem i64 %tmp1, 64
   %tmp3 = mul i64 %tmp2, 299
-  %tmp4 = add nuw nsw i64 %tmp, %tmp3
+  %tmp4 = add i64 %tmp, %tmp3
   ret i64 %tmp4
 }
+
+define i32 @not_match_overflow(i32 %x) {
+; CHECK-LABEL: @not_match_overflow(
+; CHECK:         [[TMP:%.*]] = add
+; CHECK-NEXT:    ret i32 [[TMP]]
+;
+bb:
+  %tmp = urem i32 %x, 299
+  %tmp1 = udiv i32 %x,299
+  %tmp2 = urem i32 %tmp1, 147483647
+  %tmp3 = mul i32 %tmp2, 299
+  %tmp4 = add i32 %tmp, %tmp3
+  ret i32 %tmp4
+}