This is an archive of the discontinued LLVM Phabricator instance.

Differential D136661

[InstCombine] Fold series of instructions into mull for more types
ClosedPublic

Authored by Allen on Oct 24 2022, 10:06 PM.

Details

Reviewers
spatel
chfast
Commits
rG620cff096aba: [InstCombine] Fold series of instructions into mull for more types
Summary

Relax the constraint of wide/vectors types.
Address the comment https://reviews.llvm.org/D136015?id=469189#inline-1314520

Diff Detail

Unit TestsFailed

TimeTest
60,030 msx64 debian > Clang-Unit.Format/_/FormatTests/6::61
60,050 msx64 debian > MLIR.Examples/standalone::test.toy

Event Timeline

Allen created this revision.Oct 24 2022, 10:06 PM
Herald added a project: Restricted Project. · View Herald TranscriptOct 24 2022, 10:06 PM
Herald added a subscriber: hiraditya. · View Herald Transcript
Allen requested review of this revision.Oct 24 2022, 10:06 PM
Herald added a project: Restricted Project. · View Herald TranscriptOct 24 2022, 10:06 PM
Herald added a subscriber: llvm-commits. · View Herald Transcript
Allen added a reviewer: chfast.Oct 24 2022, 10:07 PM
Harbormaster completed remote builds in B194095: Diff 470370.Oct 24 2022, 10:54 PM
chfast requested changes to this revision.Oct 25 2022, 12:05 AM
chfast added inline comments.
llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp
1275
llvm/test/Transforms/InstCombine/mul_full_64.ll
451

There is typo in the link: last instruction should be add not and. https://alive2.llvm.org/ce/z/y26zaW
Please update the comment to TODO if we don't plan to match the or pattern right now.

This revision now requires changes to proceed.Oct 25 2022, 12:05 AM
Allen updated this revision to Diff 470408.Oct 25 2022, 1:35 AM

update the comment with TODO

Allen marked an inline comment as done.Oct 25 2022, 1:45 AM
Allen added inline comments.
llvm/test/Transforms/InstCombine/mul_full_64.ll
451

Done, thanks for your rectifying

chfast accepted this revision.Oct 25 2022, 2:18 AM

LGTM, but I'd wait for one more review.

This revision is now accepted and ready to land.Oct 25 2022, 2:18 AM
Harbormaster completed remote builds in B194118: Diff 470408.Oct 25 2022, 4:24 AM
spatel accepted this revision.Oct 25 2022, 5:46 AM

LGTM

This revision was landed with ongoing or failed builds.Oct 25 2022, 8:05 AM
Closed by commit rG620cff096aba: [InstCombine] Fold series of instructions into mull for more types (authored by Allen). · Explain Why
This revision was automatically updated to reflect the committed changes.
Allen marked an inline comment as done.
Allen added a commit: rG620cff096aba: [InstCombine] Fold series of instructions into mull for more types.

Revision Contents

PathSize
llvm/
lib/
Transforms/
InstCombine/
8 lines
test/
Transforms/
InstCombine/
46 lines
2 lines

Diff 470408

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

Show First 20 Lines • Show All 1,264 Lines • ▼ Show 20 Linesstatic Instruction *factorizeMathWithShlOps(BinaryOperator &I,
NewShl->setHasNoSignedWrap(HasNSW); NewShl->setHasNoSignedWrap(HasNSW);
NewShl->setHasNoUnsignedWrap(HasNUW); NewShl->setHasNoUnsignedWrap(HasNUW);
return NewShl; return NewShl;
} }
/// Reduce a sequence of masked half-width multiplies to a single multiply. /// Reduce a sequence of masked half-width multiplies to a single multiply.
/// ((XLow * YHigh) + (YLow * XHigh)) << HalfBits) + (XLow * YLow) --> X * Y /// ((XLow * YHigh) + (YLow * XHigh)) << HalfBits) + (XLow * YLow) --> X * Y
static Instruction *foldBoxMultiply(BinaryOperator &I) { static Instruction *foldBoxMultiply(BinaryOperator &I) {
if (!I.getType()->isIntegerTy())
return nullptr;
unsigned BitWidth = I.getType()->getScalarSizeInBits(); unsigned BitWidth = I.getType()->getScalarSizeInBits();
// Skip the odd bitwidth types and large bitwidth types // Skip the odd bitwidth types.
// TODO: Relax the constraint of wide/vectors types. if ((BitWidth & 0x1))
chfastUnsubmitted
Not Done
ReplyInline Actions
// Skip the odd bitwidth types.
- if ((BitWidth & 0x1))
+ if ((BitWidth & 1))
return nullptr;
chfast:
if ((BitWidth & 0x1) || (BitWidth > 128))
return nullptr; return nullptr;
unsigned HalfBits = BitWidth >> 1; unsigned HalfBits = BitWidth >> 1;
APInt HalfMask = APInt::getMaxValue(HalfBits); APInt HalfMask = APInt::getMaxValue(HalfBits);
// ResLo = (CrossSum << HalfBits) + (YLo * XLo) // ResLo = (CrossSum << HalfBits) + (YLo * XLo)
Value *XLo, *YLo; Value *XLo, *YLo;
Value *CrossSum; Value *CrossSum;
▲ Show 20 Lines • Show All 1,301 Lines • Show Last 20 Lines

llvm/test/Transforms/InstCombine/mul_fold.ll

Show First 20 Lines • Show All 515 Lines • ▼ Show 20 Lines;
%m01 = mul i128 %In1Lo, %In0Hi %m01 = mul i128 %In1Lo, %In0Hi
%m00 = mul i128 %In1Lo, %In0Lo %m00 = mul i128 %In1Lo, %In0Lo
%addc = add i128 %m10, %m01 %addc = add i128 %m10, %m01
%shl = shl i128 %addc, 64 %shl = shl i128 %addc, 64
%retLo = add i128 %shl, %m00 %retLo = add i128 %shl, %m00
ret i128 %retLo ret i128 %retLo
} }
; TODO: Skip vector type ; Support vector type
define <2 x i8> @mul_v2i8_low(<2 x i8> %in0, <2 x i8> %in1) { define <2 x i8> @mul_v2i8_low(<2 x i8> %in0, <2 x i8> %in1) {
; CHECK-LABEL: @mul_v2i8_low( ; CHECK-LABEL: @mul_v2i8_low(
; CHECK-NEXT: [[IN0LO:%.*]] = and <2 x i8> [[IN0:%.*]], <i8 15, i8 15> ; CHECK-NEXT: [[RETLO:%.*]] = mul <2 x i8> [[IN0:%.*]], [[IN1:%.*]]
; CHECK-NEXT: [[IN0HI:%.*]] = lshr <2 x i8> [[IN0]], <i8 4, i8 4>
; CHECK-NEXT: [[IN1LO:%.*]] = and <2 x i8> [[IN1:%.*]], <i8 15, i8 15>
; CHECK-NEXT: [[IN1HI:%.*]] = lshr <2 x i8> [[IN1]], <i8 4, i8 4>
; CHECK-NEXT: [[M10:%.*]] = mul <2 x i8> [[IN1HI]], [[IN0]]
; CHECK-NEXT: [[M01:%.*]] = mul <2 x i8> [[IN0HI]], [[IN1]]
; CHECK-NEXT: [[M00:%.*]] = mul nuw <2 x i8> [[IN1LO]], [[IN0LO]]
; CHECK-NEXT: [[ADDC:%.*]] = add <2 x i8> [[M10]], [[M01]]
; CHECK-NEXT: [[SHL:%.*]] = shl <2 x i8> [[ADDC]], <i8 4, i8 4>
; CHECK-NEXT: [[RETLO:%.*]] = add <2 x i8> [[SHL]], [[M00]]
; CHECK-NEXT: ret <2 x i8> [[RETLO]] ; CHECK-NEXT: ret <2 x i8> [[RETLO]]
; ;
%In0Lo = and <2 x i8> %in0, <i8 15, i8 15> %In0Lo = and <2 x i8> %in0, <i8 15, i8 15>
%In0Hi = lshr <2 x i8> %in0, <i8 4, i8 4> %In0Hi = lshr <2 x i8> %in0, <i8 4, i8 4>
%In1Lo = and <2 x i8> %in1, <i8 15, i8 15> %In1Lo = and <2 x i8> %in1, <i8 15, i8 15>
%In1Hi = lshr <2 x i8> %in1, <i8 4, i8 4> %In1Hi = lshr <2 x i8> %in1, <i8 4, i8 4>
%m10 = mul <2 x i8> %In1Hi, %In0Lo %m10 = mul <2 x i8> %In1Hi, %In0Lo
%m01 = mul <2 x i8> %In1Lo, %In0Hi %m01 = mul <2 x i8> %In1Lo, %In0Hi
%m00 = mul <2 x i8> %In1Lo, %In0Lo %m00 = mul <2 x i8> %In1Lo, %In0Lo
%addc = add <2 x i8> %m10, %m01 %addc = add <2 x i8> %m10, %m01
%shl = shl <2 x i8> %addc, <i8 4, i8 4> %shl = shl <2 x i8> %addc, <i8 4, i8 4>
%retLo = add <2 x i8> %shl, %m00 %retLo = add <2 x i8> %shl, %m00
ret <2 x i8> %retLo ret <2 x i8> %retLo
} }
define <2 x i8> @mul_v2i8_low_one_extra_user(<2 x i8> %in0, <2 x i8> %in1) { define <2 x i8> @mul_v2i8_low_one_extra_user(<2 x i8> %in0, <2 x i8> %in1) {
; CHECK-LABEL: @mul_v2i8_low_one_extra_user( ; CHECK-LABEL: @mul_v2i8_low_one_extra_user(
; CHECK-NEXT: [[IN0LO:%.*]] = and <2 x i8> [[IN0:%.*]], <i8 15, i8 15> ; CHECK-NEXT: [[IN0HI:%.*]] = lshr <2 x i8> [[IN0:%.*]], <i8 4, i8 4>
; CHECK-NEXT: [[IN0HI:%.*]] = lshr <2 x i8> [[IN0]], <i8 4, i8 4>
; CHECK-NEXT: [[IN1LO:%.*]] = and <2 x i8> [[IN1:%.*]], <i8 15, i8 15> ; CHECK-NEXT: [[IN1LO:%.*]] = and <2 x i8> [[IN1:%.*]], <i8 15, i8 15>
; CHECK-NEXT: [[IN1HI:%.*]] = lshr <2 x i8> [[IN1]], <i8 4, i8 4>
; CHECK-NEXT: [[M10:%.*]] = mul <2 x i8> [[IN1HI]], [[IN0]]
; CHECK-NEXT: [[M01:%.*]] = mul nuw <2 x i8> [[IN1LO]], [[IN0HI]] ; CHECK-NEXT: [[M01:%.*]] = mul nuw <2 x i8> [[IN1LO]], [[IN0HI]]
; CHECK-NEXT: call void @use_v2i8(<2 x i8> [[M01]]) ; CHECK-NEXT: call void @use_v2i8(<2 x i8> [[M01]])
; CHECK-NEXT: [[M00:%.*]] = mul nuw <2 x i8> [[IN1LO]], [[IN0LO]] ; CHECK-NEXT: [[RETLO:%.*]] = mul <2 x i8> [[IN0]], [[IN1]]
; CHECK-NEXT: [[ADDC:%.*]] = add <2 x i8> [[M10]], [[M01]]
; CHECK-NEXT: [[SHL:%.*]] = shl <2 x i8> [[ADDC]], <i8 4, i8 4>
; CHECK-NEXT: [[RETLO:%.*]] = add <2 x i8> [[SHL]], [[M00]]
; CHECK-NEXT: ret <2 x i8> [[RETLO]] ; CHECK-NEXT: ret <2 x i8> [[RETLO]]
; ;
%In0Lo = and <2 x i8> %in0, <i8 15, i8 15> %In0Lo = and <2 x i8> %in0, <i8 15, i8 15>
%In0Hi = lshr <2 x i8> %in0, <i8 4, i8 4> %In0Hi = lshr <2 x i8> %in0, <i8 4, i8 4>
%In1Lo = and <2 x i8> %in1, <i8 15, i8 15> %In1Lo = and <2 x i8> %in1, <i8 15, i8 15>
%In1Hi = lshr <2 x i8> %in1, <i8 4, i8 4> %In1Hi = lshr <2 x i8> %in1, <i8 4, i8 4>
%m10 = mul <2 x i8> %In1Hi, %In0Lo %m10 = mul <2 x i8> %In1Hi, %In0Lo
%m01 = mul <2 x i8> %In1Lo, %In0Hi %m01 = mul <2 x i8> %In1Lo, %In0Hi
call void @use_v2i8(<2 x i8> %m01) call void @use_v2i8(<2 x i8> %m01)
%m00 = mul <2 x i8> %In1Lo, %In0Lo %m00 = mul <2 x i8> %In1Lo, %In0Lo
%addc = add <2 x i8> %m10, %m01 %addc = add <2 x i8> %m10, %m01
%shl = shl <2 x i8> %addc, <i8 4, i8 4> %shl = shl <2 x i8> %addc, <i8 4, i8 4>
%retLo = add <2 x i8> %shl, %m00 %retLo = add <2 x i8> %shl, %m00
ret <2 x i8> %retLo ret <2 x i8> %retLo
} }
; TODO: Support wide width ; Support wide width
define i130 @mul130_low(i130 %in0, i130 %in1) { define i130 @mul130_low(i130 %in0, i130 %in1) {
; CHECK-LABEL: @mul130_low( ; CHECK-LABEL: @mul130_low(
; CHECK-NEXT: [[IN0LO:%.*]] = and i130 [[IN0:%.*]], 36893488147419103231 ; CHECK-NEXT: [[RETLO:%.*]] = mul i130 [[IN0:%.*]], [[IN1:%.*]]
; CHECK-NEXT: [[IN0HI:%.*]] = lshr i130 [[IN0]], 65
; CHECK-NEXT: [[IN1LO:%.*]] = and i130 [[IN1:%.*]], 36893488147419103231
; CHECK-NEXT: [[IN1HI:%.*]] = lshr i130 [[IN1]], 65
; CHECK-NEXT: [[M10:%.*]] = mul i130 [[IN1HI]], [[IN0]]
; CHECK-NEXT: [[M01:%.*]] = mul i130 [[IN0HI]], [[IN1]]
; CHECK-NEXT: [[M00:%.*]] = mul nuw i130 [[IN1LO]], [[IN0LO]]
; CHECK-NEXT: [[ADDC:%.*]] = add i130 [[M10]], [[M01]]
; CHECK-NEXT: [[SHL:%.*]] = shl i130 [[ADDC]], 65
; CHECK-NEXT: [[RETLO:%.*]] = add i130 [[SHL]], [[M00]]
; CHECK-NEXT: ret i130 [[RETLO]] ; CHECK-NEXT: ret i130 [[RETLO]]
; ;
%In0Lo = and i130 %in0, 36893488147419103231 %In0Lo = and i130 %in0, 36893488147419103231
%In0Hi = lshr i130 %in0, 65 %In0Hi = lshr i130 %in0, 65
%In1Lo = and i130 %in1, 36893488147419103231 %In1Lo = and i130 %in1, 36893488147419103231
%In1Hi = lshr i130 %in1, 65 %In1Hi = lshr i130 %in1, 65
%m10 = mul i130 %In1Hi, %In0Lo %m10 = mul i130 %In1Hi, %In0Lo
%m01 = mul i130 %In1Lo, %In0Hi %m01 = mul i130 %In1Lo, %In0Hi
%m00 = mul i130 %In1Lo, %In0Lo %m00 = mul i130 %In1Lo, %In0Lo
%addc = add i130 %m10, %m01 %addc = add i130 %m10, %m01
%shl = shl i130 %addc, 65 %shl = shl i130 %addc, 65
%retLo = add i130 %shl, %m00 %retLo = add i130 %shl, %m00
ret i130 %retLo ret i130 %retLo
} }
define i130 @mul130_low_one_extra_user(i130 %in0, i130 %in1) { define i130 @mul130_low_one_extra_user(i130 %in0, i130 %in1) {
; CHECK-LABEL: @mul130_low_one_extra_user( ; CHECK-LABEL: @mul130_low_one_extra_user(
; CHECK-NEXT: [[IN0LO:%.*]] = and i130 [[IN0:%.*]], 36893488147419103231 ; CHECK-NEXT: [[IN0LO:%.*]] = and i130 [[IN0:%.*]], 36893488147419103231
; CHECK-NEXT: [[IN0HI:%.*]] = lshr i130 [[IN0]], 65 ; CHECK-NEXT: [[IN1HI:%.*]] = lshr i130 [[IN1:%.*]], 65
; CHECK-NEXT: [[IN1LO:%.*]] = and i130 [[IN1:%.*]], 36893488147419103231
; CHECK-NEXT: [[IN1HI:%.*]] = lshr i130 [[IN1]], 65
; CHECK-NEXT: [[M10:%.*]] = mul nuw i130 [[IN1HI]], [[IN0LO]] ; CHECK-NEXT: [[M10:%.*]] = mul nuw i130 [[IN1HI]], [[IN0LO]]
; CHECK-NEXT: call void @use130(i130 [[M10]]) ; CHECK-NEXT: call void @use130(i130 [[M10]])
; CHECK-NEXT: [[M01:%.*]] = mul i130 [[IN0HI]], [[IN1]] ; CHECK-NEXT: [[RETLO:%.*]] = mul i130 [[IN0]], [[IN1]]
; CHECK-NEXT: [[M00:%.*]] = mul nuw i130 [[IN1LO]], [[IN0LO]]
; CHECK-NEXT: [[ADDC:%.*]] = add i130 [[M10]], [[M01]]
; CHECK-NEXT: [[SHL:%.*]] = shl i130 [[ADDC]], 65
; CHECK-NEXT: [[RETLO:%.*]] = add i130 [[SHL]], [[M00]]
; CHECK-NEXT: ret i130 [[RETLO]] ; CHECK-NEXT: ret i130 [[RETLO]]
; ;
%In0Lo = and i130 %in0, 36893488147419103231 %In0Lo = and i130 %in0, 36893488147419103231
%In0Hi = lshr i130 %in0, 65 %In0Hi = lshr i130 %in0, 65
%In1Lo = and i130 %in1, 36893488147419103231 %In1Lo = and i130 %in1, 36893488147419103231
%In1Hi = lshr i130 %in1, 65 %In1Hi = lshr i130 %in1, 65
%m10 = mul i130 %In1Hi, %In0Lo %m10 = mul i130 %In1Hi, %In0Lo
call void @use130(i130 %m10) call void @use130(i130 %m10)
▲ Show 20 Lines • Show All 115 Lines • Show Last 20 Lines

llvm/test/Transforms/InstCombine/mul_full_64.ll

Show First 20 Lines • Show All 442 Lines • ▼ Show 20 Lines;
%u1h = lshr i64 %u1, 32 %u1h = lshr i64 %u1, 32
%u2 = add i64 %u0h, %t3 %u2 = add i64 %u0h, %t3
%hi = add i64 %u2, %u1h %hi = add i64 %u2, %u1h
ret i64 %hi ret i64 %hi
} }
; TODO: https://alive2.llvm.org/ce/z/y26zaW
chfastUnsubmitted
Done
ReplyInline Actions

There is typo in the link: last instruction should be add not and. https://alive2.llvm.org/ce/z/y26zaW
Please update the comment to TODO if we don't plan to match the or pattern right now.

chfast: There is typo in the link: last instruction should be `add` not `and`. https://alive2.llvm.
AllenAuthorUnsubmitted
Done
ReplyInline Actions

Done, thanks for your rectifying

Allen: Done, thanks for your rectifying
define i64 @mullo(i64 %x, i64 %y) { define i64 @mullo(i64 %x, i64 %y) {
; CHECK-LABEL: @mullo( ; CHECK-LABEL: @mullo(
; CHECK-NEXT: [[XL:%.*]] = and i64 [[X:%.*]], 4294967295 ; CHECK-NEXT: [[XL:%.*]] = and i64 [[X:%.*]], 4294967295
; CHECK-NEXT: [[XH:%.*]] = lshr i64 [[X]], 32 ; CHECK-NEXT: [[XH:%.*]] = lshr i64 [[X]], 32
; CHECK-NEXT: [[YL:%.*]] = and i64 [[Y:%.*]], 4294967295 ; CHECK-NEXT: [[YL:%.*]] = and i64 [[Y:%.*]], 4294967295
; CHECK-NEXT: [[YH:%.*]] = lshr i64 [[Y]], 32 ; CHECK-NEXT: [[YH:%.*]] = lshr i64 [[Y]], 32
; CHECK-NEXT: [[T0:%.*]] = mul nuw i64 [[YL]], [[XL]] ; CHECK-NEXT: [[T0:%.*]] = mul nuw i64 [[YL]], [[XL]]
; CHECK-NEXT: [[T1:%.*]] = mul i64 [[XH]], [[Y]] ; CHECK-NEXT: [[T1:%.*]] = mul i64 [[XH]], [[Y]]
▲ Show 20 Lines • Show All 261 Lines • Show Last 20 Lines