[InstCombine] Fold series of instructions into mull

[Allen]

Summary

The following sequence should be folded into in0 * in1

In0Lo = in0 & 0xffffffff; In0Hi = in0 >> 32;
In1Lo = in1 & 0xffffffff; In1Hi = in1 >> 32;
m01 = In1Hi * In0Lo; m10 = In1Lo * In0Hi; m00 = In1Lo * In0Lo;
addc = m01 + m10;
ResLo = m00 + (addc >> 32);

[bcl5980]

What is the motivation of this change? I feel a little strange to do this in instcombine.
And if we really need to do this, we do need more negative tests.

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

856

This pattern can work for any types with even bit width I think, not only i64.

864

Need one-use here for addc.

[Allen]

Thanks for your attention, I do this as there is case https://godbolt.org/z/x5jMhqW8s is our benchmark,
and the source is equel to an mull operater for two 64bits integer vaules, so it should be fold to similar assemble.
This is the 1st step try to generate the mul. so now I only enable it with i64 as the instruction umulh.

mul   x8,x0,x1
umulh x9,x0,x1
str   x8,[x2]
str   x9,[x3]

[bcl5980]

In D136015#3860475, @Allen wrote:

Thanks for your attention, I do this as there is case https://godbolt.org/z/x5jMhqW8s is our benchmark,
and the source is equel to an mull operater for two 64bits integer vaules, so it should be fold to similar assemble.
This is the 1st step try to generate the mul. so now I only enable it with i64 as the instruction umulh.

mul   x8,x0,x1
umulh x9,x0,x1
str   x8,[x2]
str   x9,[x3]

Maybe you can do it in AArch64 SDAG if you are only interested in AArch64.
I think the detect pattern is too long in instcombine so I have a little worry about the change.
But I'm not senior enough to review the patch, so I will resign as reviewer.

[Allen]

Add conditon m_OneUse(Addc)

[Allen]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

856

The source https://godbolt.org/z/x5jMhqW8s is equel to an mull operater for two 64bits integer vaules, so it should be fold to similar assemble.
This is the 1st step try to generate the mul, so now I only enable it with i64 as the instruction umulh

[spatel]

We're not creating a new multiply that is wider than we started with, so I'm assuming codegen can't be worse.
As mentioned earlier, the code should be generalized to handle any even bitwidth; we don't want highly type-specific transforms in IR canonicalization.
https://alive2.llvm.org/ce/z/2BqKLt

The commutative pattern matching doesn't look correct at first glance, so we need tests that exercise all of those possible patterns. The instructions with constants will always have the constant as operand 1, so you don't need to worry about those. But the 3 muls and 2 adds can all be commuted, so that's 16 potential patterns?

Since we are only creating a single new instruction, there's no need to check for m_OneUse on any of the existing values (but we should include at least one test with extra uses to show that works as expected).

[Allen]

Delete condtion m_OneUse and I.getType()->getIntegerBitWidth() == 64, and Add relavant test cases

[Allen]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

856

delete the checking I.getType()->getIntegerBitWidth() == 64, thanks.

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineInternal.h

550

There's no need to make a class function for this transform. Just create a static function above InstCombinerImpl::visitAdd().

Use the raw BinaryOperator::CreateMul() to return an Instruction, so we don't need to pass the Builder or use replaceInstUsesWith().

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

856

The type check is insufficient in at least 2 ways and over-restrictive in other.

So we need at least 3 more tests like this:

define i9 @mul9_low(i9 %in0, i9 %in1) {
  %In0Lo = and i9 %in0, 15
  %In0Hi = lshr i9 %in0, 4
  %In1Lo = and i9 %in1, 15
  %In1Hi = lshr i9 %in1, 4
  %m10 = mul i9 %In1Hi, %In0Lo
  %m01 = mul i9 %In1Lo, %In0Hi
  %m00 = mul i9 %In1Lo, %In0Lo
  %addc = add i9 %m10, %m01
  %shl = shl i9 %addc, 4
  %addc9 = add i9 %shl, %m00
  ret i9 %addc9
}

define <2 x i8> @mul_v2i8_low(<2 x i8> %in0, <2 x i8> %in1) {
  %In0Lo = and <2 x i8> %in0, <i8 15, i8 15>
  %In0Hi = lshr <2 x i8> %in0, <i8 4, i8 4>
  %In1Lo = and <2 x i8> %in1, <i8 15, i8 15>
  %In1Hi = lshr <2 x i8> %in1, <i8 4, i8 4>
  %m10 = mul <2 x i8> %In1Hi, %In0Lo
  %m01 = mul <2 x i8> %In1Lo, %In0Hi
  %m00 = mul <2 x i8> %In1Lo, %In0Lo
  %addc = add <2 x i8> %m10, %m01
  %shl = shl <2 x i8> %addc, <i8 4, i8 4>
  %addc9 = add <2 x i8> %shl, %m00
  ret <2 x i8> %addc9
}

define i128 @mul128_low(i128 %in0, i128 %in1) {
  %In0Lo = and i128 %in0, 18446744073709551615
  %In0Hi = lshr i128 %in0, 64
  %In1Lo = and i128 %in1, 18446744073709551615
  %In1Hi = lshr i128 %in1, 64
  %m10 = mul i128 %In1Hi, %In0Lo
  %m01 = mul i128 %In1Lo, %In0Hi
  %m00 = mul i128 %In1Lo, %In0Lo
  %addc = add i128 %m10, %m01
  %shl = shl i128 %addc, 64
  %addc9 = add i128 %shl, %m00
  ret i128 %addc9
}

866

The structure of these matches is confusing. I'd prefer to organize it more like this:

  // R = (CrossSum << HalfBits) + (XLo * YLo)
  Value *XLo, *YLo;
  Value *CrossSum;
  if (!match(&I, m_c_Add(m_Shl(m_Value(CrossSum), m_SpecificInt(HalfBits)),
                         m_Mul(m_Value(XLo), m_Value(YLo)))))
    return nullptr;

  // XLo = X & HalfMask
  // YLo = Y & HalfMask
  Value *X, *Y;
  if (!match(XLo, m_And(m_Value(X), m_SpecificInt(HalfMask))) ||
      !match(YLo, m_And(m_Value(Y), m_SpecificInt(HalfMask))))
    return nullptr;

  // CrossSum = (X' * (Y >> Halfbits)) + (Y' * (X >> HalfBits))
...

IIUC, X' can be either X or XLo in the pattern (and the same for Y'). You can probably use m_CombineOr(m_Specific(), m_Specific()) to match that with minimal code.

llvm/test/Transforms/InstCombine/mul.ll

1578

The tests are incomplete for commutative patterns. As I said earlier, I think we need at least 16 tests to verify that the matching is working as expected.

Once we have the right tests in place, please pre-commit the baseline tests (CHECK lines without the code change), so we will only show diffs in this patch.

[Allen]

1、 use BinaryOperator::CreateMul() to avoid the use of replaceInstUsesWith()
2、 Add 3 more cases according comment
3、 Use m_CombineOr to match that with minimal code
4、create a static function above InstCombinerImpl::visitAdd()

[Allen]

update after precommit the testcases

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

1270

Add a better description for the full transform. Something like:

/// Reduce a sequence of masked half-width multiplies to a single multiply.
/// ((XLow * YHigh) + (YLow * XHigh)) << HalfBits) + (XLow * YLow) --> X * Y

1271

Function names should start with lower-case letter. "Simplify" has a distinct meaning in LLVM combining - it suggests that we are not creating a new instruction. Even though it is misused in other places including in this file, we shouldn't do that again.

I suggest naming this "foldLongMultiply" or "foldBoxMultiply" ( https://www.ixl.com/math/grade-4/box-multiplication ) or something like that, so it's more obvious that we are reducing a sequence of mul and add to something else.

1275

I don't see a reason to exclude vectors from this transform. Just change this line?

unsigned BitWidth = I.getType()->getScalarSizeInBits();

1277

Similarly, why exclude wide widths? We're already using APInt::getMaxValue(), so just use that APInt in the m_SpecificInt() calls?

[RKSimon]

any chance we could get vector support/tests please?

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

1296

What about if the AND has been removed by SimplifyDemandedBits? Maybe also test for KnownBits known leading zeros?

[Allen]

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

1277

exclude the wide/vectors widths as hey are unusual get the IR from C/C++ code, and can be expand when needed later? or a seperate patch, now we already need too many cases to cover the pattern?

llvm/lib/Transforms/InstCombine/InstCombineInternal.h

550

Done, thanks for detail suggestions

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

856

Thanks for detail examples.

866

Apply your comment, thanks

llvm/test/Transforms/InstCombine/mul.ll

1578

Addressed in D136340

[Allen]

a) rename function name to foldBoxMultiply and it's description
b) use APInt in m_SpecificInt directly
c) update getIntegerBitWidth with getScalarSizeInBits

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

1296

Thanks for your suggestion, I'll record this issue, and I'll try out your suggestions later with a separate patch ?

[RKSimon]

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

1296

A TODO comment is fine for now - cheers

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

1277

There's really no difference in the testing - just change one test to i130 or something like that?
And the code difference is just to remove that clause in the if on line 1278 - nothing else changes?
But if you think there's some risk from handling that, then please add a TODO comment, so we can relax the constraint in a follow-up patch.

[RKSimon]

CC @chfast who was looking at something similar in D56214

[chfast]

In https://reviews.llvm.org/D56214 similar pattern match was applied in AggressiveInstCombine.

Do you want me to submit test cases from there?

[Allen]

rebase as the precommit tests update

[RKSimon]

In D136015#3875187, @chfast wrote:

In https://reviews.llvm.org/D56214 similar pattern match was applied in AggressiveInstCombine.

Do you want me to submit test cases from there?

Yes please @chfast, if you think we can just use this patch then maybe just move them (and tweak for -instcombine).

[chfast]

In D136015#3876878, @RKSimon wrote:

In D136015#3875187, @chfast wrote:

In https://reviews.llvm.org/D56214 similar pattern match was applied in AggressiveInstCombine.

Do you want me to submit test cases from there?

Yes please @chfast, if you think we can just use this patch then maybe just move them (and tweak for -instcombine).

Added in https://reviews.llvm.org/rG119c34e7f9c66dbdb77f69d67bb50507c91dc2ef.

[RKSimon]

@Allen please can you rebase?

[Allen]

rebase top as the precommit test

[Allen]

In D136015#3877593, @RKSimon wrote:

@Allen please can you rebase?

Done, thanks @RKSimon/@chfast for your precommit tests.

[spatel]

Please rebase again after 41c42f5b1825 / 56c6b612aed1.
If I did that correctly, we won't see any changes for the final value in each test from this revision, but we'll test this patch directly and get a better coverage for commuted patterns.
After that, I think this patch will be complete.

[Allen]

rebase after 41c42f5b1825 / 56c6b612aed1

[chfast]

llvm/test/Transforms/InstCombine/mul_full_64.ll

452 ↗

(On Diff #470137)

Interestingly, it hasn't folded this one.

[Allen]

In D136015#3879133, @spatel wrote:

Please rebase again after 41c42f5b1825 / 56c6b612aed1.
If I did that correctly, we won't see any changes for the final value in each test from this revision, but we'll test this patch directly and get a better coverage for commuted patterns.
After that, I think this patch will be complete.

Done, thanks very much for your changes. And I don't completely understand why need the use at the beginning of a function? eg:

define i8 @mul8_low_A0_B2(i8 %in0, i8 %p) {
  %in1 = call i8 @use8(i8 %p) ; thwart complexity-based canonicalization
  %In0Lo = and i8 %in0, 15
  %In0Hi = lshr i8 %in0, 4
  %In1Lo = and i8 %in1, 15
  %In1Hi = lshr i8 %in1, 4
  %m10 = mul i8 %In1Hi, %in0
  %m01 = mul i8 %in1, %In0Hi
  %m00 = mul i8 %In1Lo, %In0Lo
  %addc = add i8 %m01, %m10
  %shl = shl i8 %addc, 4
  %retLo = add i8 %shl, %m00
  ret i8 %retLo
}

[spatel]

LGTM

In D136015#3879280, @Allen wrote:

Done, thanks very much for your changes. And I don't completely understand why need the use at the beginning of a function? eg:

define i8 @mul8_low_A0_B2(i8 %in0, i8 %p) {
  %in1 = call i8 @use8(i8 %p) ; thwart complexity-based canonicalization

If you remove that line, notice that the values in the later multiply get commuted. That happens before we reach this transform, so the test is trying to ensure that the exact placement of the values at runtime is the same as specified in the test.

llvm/test/Transforms/InstCombine/mul_full_64.ll

452 ↗

(On Diff #470137)

This patch assumes we are ending with an "add", but this test changes to an "or". We'd need to add another check for hasNoCommonBitsSet() to catch it?

Here's another potential fold:
https://alive2.llvm.org/ce/z/hUm56R
...but it needs to freeze the inputs to be poison-safe because they have multiple uses.

[Allen]

If you remove that line, notice that the values in the later multiply get commuted. That happens before we reach this transform, so the test is trying to ensure that the exact placement of the values at runtime is the same as specified in the test.

Thanks very much for your guidance.

[Allen]

llvm/test/Transforms/InstCombine/mul_full_64.ll

452 ↗

(On Diff #470137)

hi @chfast

I think the case **@mullo** should not be matched? https://alive2.llvm.org/ce/z/jH4kU7

hi, @spatel

 As the case in link https://alive2.llvm.org/ce/z/hUm56R, it's result not equal to **mul i8 %y, %x**, so it need some other logic to match ? maybe defined with a new helper function. see detail https://alive2.llvm.org/ce/z/FEgEU7
```

define i8 @tgt(i8 %x, i8 %y) {

%m = mul i8 %y, %x
ret i8 %m

}

[chfast]

llvm/test/Transforms/InstCombine/mul_full_64.ll

452 ↗

(On Diff #470137)

I think the case **@mullo** should not be matched? https://alive2.llvm.org/ce/z/jH4kU7

There is a typo in the example. You changed or to and but the original pattern starts at add. I.e. all patterns starting at add, or and xor should work, the one starting at and should not. https://alive2.llvm.org/ce/z/y26zaW

I'm not sure it is worth to expand the matching to or and `xor.

[Allen]

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

1296

hi @RKSimon

As this revision is accept, so it is time to consider your refactor suggestion, do you have some idea about the extra tests ? thanks.

llvm/test/Transforms/InstCombine/mul_full_64.ll

452 ↗

(On Diff #470137)

Thanks @chfast for your case. I take a look at your case more, except the above add VS or, there is some other diffirence with my initail case. https://alive2.llvm.org/ce/z/ZKmrJB

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

if (auto *NewI = dyn_cast<BinaryOperator>(NewMath)) {
     NewI->setHasNoUnsignedWrap(HasNUW);
   }
   auto *NewShl = BinaryOperator::CreateShl(NewMath, ShAmt);
   NewShl->setHasNoSignedWrap(HasNSW);
   NewShl->setHasNoUnsignedWrap(HasNUW);
   return NewShl;
 }
 
 Instruction *InstCombinerImpl::visitAdd(BinaryOperator &I) {
   if (Value *V = simplifyAddInst(I.getOperand(0), I.getOperand(1),
                                  I.hasNoSignedWrap(), I.hasNoUnsignedWrap(),
                                  SQ.getWithInstruction(&I)))
     return replaceInstUsesWith(I, V);
 
   if (SimplifyAssociativeOrCommutative(I))
     return &I;
 
   if (Instruction *X = foldVectorBinop(I))
     return X;
 
   if (Instruction *Phi = foldBinopWithPhiOperands(I))
     return Phi;
 
   // (A*B)+(A*C) -> A*(B+C) etc
   if (Value *V = SimplifyUsingDistributiveLaws(I))
     return replaceInstUsesWith(I, V);
 
+  if (Value *V = SimplifyMull(I))
+    return replaceInstUsesWith(I, V);
+
   if (Instruction *R = factorizeMathWithShlOps(I, Builder))
     return R;
 
   if (Instruction *X = foldAddWithConstant(I))
     return X;
 
   if (Instruction *X = foldNoWrapAdd(I, Builder))
     return X;
 
   Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
   Type *Ty = I.getType();
   if (Ty->isIntOrIntVectorTy(1))
     return BinaryOperator::CreateXor(LHS, RHS);

llvm/lib/Transforms/InstCombine/InstCombineInternal.h

public:
   /// 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 a few sequence operations into MULL
+  Value *SimplifyMull(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

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

if (R && R == ConstantExpr::getBinOpIdentity(InnerOpcode, R->getType())) {
       A->takeName(&I);
       return A;
     }
   }
 
   return SimplifySelectsFeedingBinaryOp(I, LHS, RHS);
 }
 
+Value *InstCombinerImpl::SimplifyMull(BinaryOperator &I) {
+  if (!(I.getType()->isIntegerTy() && I.getType()->getIntegerBitWidth() == 64))
+    return nullptr;
+
+  Value *In0, *In1;
+  Value *M01, *M10, *M00, *Addc;
+
+  // addc = m01 + m10;
+  // ResLo = m00 + (addc >> 32);
+  bool IsMulLow = match(&I, m_c_Add(m_Value(M00),
+                                    m_Shl(m_Value(Addc), m_SpecificInt(32)))) &&
+                  match(Addc, m_c_Add(m_Value(M01), m_Value(M10)));
+
+  // In0Lo = in0 & 0xffffffff; In0Hi = in0 >> 32;
+  // In1Lo = in1 & 0xffffffff; In1Hi = in1 >> 32;
+  // m01 = In1Hi * In0Lo; m10 = In1Lo * In0Hi; m00 = In1Lo * In0Lo;
+  if (IsMulLow &&
+      match(M00, m_c_Mul(m_c_And(m_Value(In1), m_SpecificInt(4294967295)),
+                         m_c_And(m_Value(In0), m_SpecificInt(4294967295)))) &&
+      match(M01, m_c_Mul(m_LShr(m_Specific(In1), m_SpecificInt(32)),
+                         m_Specific(In0))) &&
+      match(M10, m_c_Mul(m_LShr(m_Specific(In0), m_SpecificInt(32)),
+                         m_Specific(In1)))) {
+    return Builder.CreateMul(In0, In1);
+  }
+
+  return nullptr;
+}
+
 Value *InstCombinerImpl::SimplifySelectsFeedingBinaryOp(BinaryOperator &I,
                                                         Value *LHS,
                                                         Value *RHS) {
   Value *A, *B, *C, *D, *E, *F;
   bool LHSIsSelect = match(LHS, m_Select(m_Value(A), m_Value(B), m_Value(C)));
   bool RHSIsSelect = match(RHS, m_Select(m_Value(D), m_Value(E), m_Value(F)));
   if (!LHSIsSelect && !RHSIsSelect)
     return nullptr;

llvm/test/Transforms/InstCombine/mul.ll

 ; CHECK-NEXT:    [[R:%.*]] = mul i32 [[ZX]], -16777216
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %zx = zext i8 %x to i32
   call void @use32(i32 %zx)
   %r = mul i32 %zx, -16777216 ; -1 << 24
   ret i32 %r
 }
+
+define i64 @mul64_low(i64 noundef %in0, i64 noundef %in1) {
+; CHECK-LABEL: @mul64_low(
+; CHECK-NEXT:    [[TMP1:%.*]] = mul i64 [[IN0:%.*]], [[IN1:%.*]]
+; CHECK-NEXT:    ret i64 [[TMP1]]
+;
+  %In0Lo = and i64 %in0, 4294967295
+  %In0Hi = lshr i64 %in0, 32
+  %In1Lo = and i64 %in1, 4294967295
+  %In1Hi = lshr i64 %in1, 32
+  %m10 = mul i64 %In1Hi, %In0Lo
+  %m01 = mul i64 %In1Lo, %In0Hi
+  %m00 = mul i64 %In1Lo, %In0Lo
+  %addc = add i64 %m10, %m01
+  %shl = shl i64 %addc, 32
+  %addc9 = add i64 %shl, %m00
+  ret i64 %addc9
+}