[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

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

1065

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

1103

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

1234

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

test/Transforms/InstCombine/add4.ll

1

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

signess->signedness

1062

Can you pass Op as Value *&Op?

1069

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

1085

What guarantees the ConstantInt only uses 64 bits or less?

1114

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

1122

Unchecked dyn_cast

1123

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

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

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

LLVM naming style is CamelCase so this should be MatchMul.

1066

Use m_Power2.

1069

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

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

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

1085

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

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

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

1045

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

1049

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

1064

Use m_APInt here too.

1070

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

1087

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

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

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

1101

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

Same here:

// Match MulOpv = RemOpv % C1

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

1120

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

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

1037

Removed.

1049

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

1120

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

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

1041

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

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

Same comment applies below.

1062

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

1081

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

Let's call this MulWillOverflow.

1108

Since you're checking this anyway, how about:

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

1114

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

1115

Should be MulOpV in the comment.

1120

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

1123

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

1130

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

1234

LLVM style avoids braces around single line statements like this.

1235

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

lib/Transforms/InstCombine/InstCombineInternal.h

629

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

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

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

the two are not equivalent.

1081

Remove the use of the cast.

1087

Will consider doing this in another change.

[sanjoy]

lgtm with minor nits.

lib/Transforms/InstCombine/InstCombineAddSub.cpp

1043

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

LLVM style discourages underscores in variable names.

1128

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

1234

LLVM style says no braces for single line statements.

[bixia]

• Removed nuw nsw from the tests.

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)) {

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 *,

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