This is an archive of the discontinued LLVM Phabricator instance.

Differential D55961

[InstCombine] canonicalize MUL with NEG operand
ClosedPublic

Authored by shchenz on Dec 20 2018, 3:15 PM.

Details

Reviewers
hfinkel
spatel
lebedev.ri
jsji
nemanjai
steven.zhang
Commits
rG4952e668f8e5: [InstCombine] canonicalize MUL with NEG operand
rL350185: [InstCombine] canonicalize MUL with NEG operand
Summary

There is an opportunity in instCombine for following instruction pattern:

%mul = mul nsw i32 %b, %a
%cmp = icmp sgt i32 %mul, -1
%sub = sub i32 0, %a
%mul2 = mul nsw i32 %sub, %b
%cond = select i1 %cmp, i32 %mul, i32 %mul2

Source code for above pattern:

return (a*b) >=0 ? (a*b) : -a*b;

Currently, llvm(-O3) can not recognize this as abs(a*b).

Got help from @spatel in llvm-dev:
"
it looks like we are missing an IR canonicalization for 'mul' like this:
https://rise4fun.com/Alive/ARs

%neg = sub i8 0, %x
%r = mul i8 %neg, %y

-->

%mul2 = mul i8 %x, %y
%r = sub i8 0, %mul2

"

Testcases are already add in https://reviews.llvm.org/rL349847.
Thanks @jsji, i have updated the testcases according to his comment to the above nfc patch.

Diff Detail

Event Timeline

shchenz created this revision.Dec 20 2018, 3:15 PM
Herald added a subscriber: hiraditya. · View Herald TranscriptDec 20 2018, 3:16 PM
spatel added a comment.Dec 20 2018, 3:35 PM

Thank you for making the patch.

  1. Please always upload your patch with full context:

https://llvm.org/docs/Phabricator.html#requesting-a-review-via-the-web-interface

  1. I don't think propagation of 'nsw' is safe in this transform:

https://rise4fun.com/Alive/wQc

  1. We need to check "m_OneUse" on the negated operand, or this transform will create an extra instruction. We should have 2 more tests with that pattern (and they should show that the transform does not occur). You might want to look at the code and tests for the similar transforms that we do for "fmul" later in this file.
dmgreen added a subscriber: dmgreen.Dec 23 2018, 12:59 AM
shchenz updated this revision to Diff 179632.Dec 28 2018, 6:10 AM

fix according to Sanjay's comments

shchenz added a comment.Dec 28 2018, 6:12 AM

@spatel Hi Sanjay, thanks very much for your comments. I have updated accordingly. Could you please help to have another review? Thanks again.

lebedev.ri added a comment.Dec 28 2018, 6:44 AM

Looks better.

llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
247–253

This seems correct now, but i wonder if it would be better to fold this into a single branch:

// -X * Y --> -(X * Y)
if (match(&I, m_c_Mul(m_OneUse(m_Neg(m_Value(X))), m_Value(Y))))
  return BinaryOperator::CreateNeg(Builder.CreateMul(X, Y));
llvm/test/Transforms/InstCombine/mul.ll
457–468

I almost complained that this is a regression.
Can you please split the NFC test update into a separate preparatory differential,
and only *regenerate* the check lines here?

shchenz updated this revision to Diff 179685.Dec 29 2018, 4:43 AM

fix according to Roman's comments.

shchenz added a comment.Dec 29 2018, 4:45 AM

Hi Roman @lebedev.ri, I have updated according to your comments. Updated testcases are committed in https://reviews.llvm.org/rL350154. Thanks very much.

lebedev.ri added inline comments.Dec 29 2018, 9:07 AM
llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
247

That || looks confusing. Maybe just keep that as two lines?

llvm/test/Transforms/InstCombine/operand-complexity.ll
4

I guess this test no longer serves it's purpose.
Not sure what to do here.

shchenz updated this revision to Diff 179717.Dec 29 2018, 3:55 PM

fix Roman's comments

shchenz marked an inline comment as done.Dec 29 2018, 3:59 PM

@lebedev.ri Updated. Thanks.

llvm/test/Transforms/InstCombine/operand-complexity.ll
4

I changed the binop here to keep original testcases. It will not change these cases testing point.
new testcases for MUL canonicalization are all in file mul.ll.

lebedev.ri accepted this revision.Dec 29 2018, 10:14 PM

LGTM, thanks.
I think this is good to go.
Not sure whether you want to wait for another review.

This revision is now accepted and ready to land.Dec 29 2018, 10:14 PM
spatel accepted this revision.Dec 31 2018, 6:16 AM

LGTM

Closed by commit rL350185: [InstCombine] canonicalize MUL with NEG operand (authored by shchenz). · Explain WhyDec 31 2018, 5:12 PM
This revision was automatically updated to reflect the committed changes.
fhahn mentioned this in D56679: [InstCombine] Don't undo 0 - (X * Y) canonicalization when combining subs..Jan 14 2019, 11:32 AM
fhahn mentioned this in rL351187: [InstCombine] Don't undo 0 - (X * Y) canonicalization when combining subs..Jan 15 2019, 3:22 AM

Revision Contents

PathSize
llvm/
lib/
Transforms/
InstCombine/
5 lines
test/
Transforms/
InstCombine/
24 lines
12 lines

Diff 179717

llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

Show First 20 Lines • Show All 238 Lines • ▼ Show 20 Lines if (match(Op0, m_Neg(m_Value(X))) && match(Op1, m_Neg(m_Value(Y)))) {
auto *NewMul = BinaryOperator::CreateMul(X, Y); auto *NewMul = BinaryOperator::CreateMul(X, Y);
if (I.hasNoSignedWrap() && if (I.hasNoSignedWrap() &&
cast<OverflowingBinaryOperator>(Op0)->hasNoSignedWrap() && cast<OverflowingBinaryOperator>(Op0)->hasNoSignedWrap() &&
cast<OverflowingBinaryOperator>(Op1)->hasNoSignedWrap()) cast<OverflowingBinaryOperator>(Op1)->hasNoSignedWrap())
NewMul->setHasNoSignedWrap(); NewMul->setHasNoSignedWrap();
return NewMul; return NewMul;
} }
// -X * Y --> -(X * Y)
lebedev.riUnsubmitted
Not Done
ReplyInline Actions

That || looks confusing. Maybe just keep that as two lines?

lebedev.ri: That `||` looks confusing. Maybe just keep that as two lines?
// X * -Y --> -(X * Y)
if (match(&I, m_c_Mul(m_OneUse(m_Neg(m_Value(X))), m_Value(Y))))
return BinaryOperator::CreateNeg(Builder.CreateMul(X, Y));
// (X / Y) * Y = X - (X % Y) // (X / Y) * Y = X - (X % Y)
// (X / Y) * -Y = (X % Y) - X // (X / Y) * -Y = (X % Y) - X
lebedev.riUnsubmitted
Not Done
ReplyInline Actions

This seems correct now, but i wonder if it would be better to fold this into a single branch:

// -X * Y --> -(X * Y)
if (match(&I, m_c_Mul(m_OneUse(m_Neg(m_Value(X))), m_Value(Y))))
  return BinaryOperator::CreateNeg(Builder.CreateMul(X, Y));
lebedev.ri: This seems correct now, but i //wonder// if it would be better to fold this into a single…
{ {
Value *Y = Op1; Value *Y = Op1;
BinaryOperator *Div = dyn_cast<BinaryOperator>(Op0); BinaryOperator *Div = dyn_cast<BinaryOperator>(Op0);
if (!Div || (Div->getOpcode() != Instruction::UDiv && if (!Div || (Div->getOpcode() != Instruction::UDiv &&
Div->getOpcode() != Instruction::SDiv)) { Div->getOpcode() != Instruction::SDiv)) {
Y = Op0; Y = Op0;
Div = dyn_cast<BinaryOperator>(Op1); Div = dyn_cast<BinaryOperator>(Op1);
} }
▲ Show 20 Lines • Show All 1,107 Lines • Show Last 20 Lines

llvm/test/Transforms/InstCombine/mul.ll

Show First 20 Lines • Show All 439 Lines • ▼ Show 20 Lines
; CHECK-NEXT: ret i128 [[MUL]] ; CHECK-NEXT: ret i128 [[MUL]]
; ;
%mul = mul nsw i128 %X, 2 %mul = mul nsw i128 %X, 2
ret i128 %mul ret i128 %mul
} }
define i32 @test_mul_canonicalize_op0(i32 %x, i32 %y) { define i32 @test_mul_canonicalize_op0(i32 %x, i32 %y) {
; CHECK-LABEL: @test_mul_canonicalize_op0( ; CHECK-LABEL: @test_mul_canonicalize_op0(
; CHECK-NEXT: [[NEG:%.*]] = sub i32 0, [[X:%.*]] ; CHECK-NEXT: [[MUL:%.*]] = mul i32 [[X:%.*]], [[Y:%.*]]
; CHECK-NEXT: [[MUL:%.*]] = mul i32 [[NEG]], [[Y:%.*]] ; CHECK-NEXT: [[NEG:%.*]] = sub i32 0, [[MUL]]
; CHECK-NEXT: ret i32 [[MUL]] ; CHECK-NEXT: ret i32 [[NEG]]
; ;
%neg = sub i32 0, %x %neg = sub i32 0, %x
%mul = mul i32 %neg, %y %mul = mul i32 %neg, %y
ret i32 %mul ret i32 %mul
} }
define i32 @test_mul_canonicalize_op1(i32 %x, i32 %z) { define i32 @test_mul_canonicalize_op1(i32 %x, i32 %z) {
; CHECK-LABEL: @test_mul_canonicalize_op1( ; CHECK-LABEL: @test_mul_canonicalize_op1(
; CHECK-NEXT: [[Y:%.*]] = mul i32 [[Z:%.*]], 3 ; CHECK-NEXT: [[Y:%.*]] = mul i32 [[Z:%.*]], 3
; CHECK-NEXT: [[NEG:%.*]] = sub i32 0, [[X:%.*]] ; CHECK-NEXT: [[MUL:%.*]] = mul i32 [[X:%.*]], [[Y:%.*]]
; CHECK-NEXT: [[MUL:%.*]] = mul i32 [[Y]], [[NEG]] ; CHECK-NEXT: [[NEG:%.*]] = sub i32 0, [[MUL]]
; CHECK-NEXT: ret i32 [[MUL]] ; CHECK-NEXT: ret i32 [[NEG]]
; ;
%y = mul i32 %z, 3 %y = mul i32 %z, 3
%neg = sub i32 0, %x %neg = sub i32 0, %x
%mul = mul i32 %y, %neg %mul = mul i32 %y, %neg
ret i32 %mul ret i32 %mul
} }
lebedev.riUnsubmitted
Not Done
ReplyInline Actions

I almost complained that this is a regression.
Can you please split the NFC test update into a separate preparatory differential,
and only *regenerate* the check lines here?

lebedev.ri: I almost complained that this is a regression. Can you please split the NFC test update into a…
define i32 @test_mul_canonicalize_nsw(i32 %x, i32 %y) { define i32 @test_mul_canonicalize_nsw(i32 %x, i32 %y) {
; CHECK-LABEL: @test_mul_canonicalize_nsw( ; CHECK-LABEL: @test_mul_canonicalize_nsw(
; CHECK-NEXT: [[NEG:%.*]] = sub nsw i32 0, [[X:%.*]] ; CHECK-NEXT: [[MUL:%.*]] = mul i32 [[X:%.*]], [[Y:%.*]]
; CHECK-NEXT: [[MUL:%.*]] = mul nsw i32 [[NEG]], [[Y:%.*]] ; CHECK-NEXT: [[NEG:%.*]] = sub i32 0, [[MUL]]
; CHECK-NEXT: ret i32 [[MUL]] ; CHECK-NEXT: ret i32 [[NEG]]
; ;
%neg = sub nsw i32 0, %x %neg = sub nsw i32 0, %x
%mul = mul nsw i32 %neg, %y %mul = mul nsw i32 %neg, %y
ret i32 %mul ret i32 %mul
} }
define <2 x i32> @test_mul_canonicalize_vec(<2 x i32> %x, <2 x i32> %y) { define <2 x i32> @test_mul_canonicalize_vec(<2 x i32> %x, <2 x i32> %y) {
; CHECK-LABEL: @test_mul_canonicalize_vec( ; CHECK-LABEL: @test_mul_canonicalize_vec(
; CHECK-NEXT: [[NEG:%.*]] = sub <2 x i32> zeroinitializer, [[X:%.*]] ; CHECK-NEXT: [[MUL:%.*]] = mul <2 x i32> [[X:%.*]], [[Y:%.*]]
; CHECK-NEXT: [[MUL:%.*]] = mul <2 x i32> [[NEG]], [[Y:%.*]] ; CHECK-NEXT: [[NEG:%.*]] = sub <2 x i32> zeroinitializer, [[MUL]]
; CHECK-NEXT: ret <2 x i32> [[MUL]] ; CHECK-NEXT: ret <2 x i32> [[NEG]]
; ;
%neg = sub <2 x i32> <i32 0, i32 0>, %x %neg = sub <2 x i32> <i32 0, i32 0>, %x
%mul = mul <2 x i32> %neg, %y %mul = mul <2 x i32> %neg, %y
ret <2 x i32> %mul ret <2 x i32> %mul
} }
define i32 @test_mul_canonicalize_multiple_uses(i32 %x, i32 %y) { define i32 @test_mul_canonicalize_multiple_uses(i32 %x, i32 %y) {
; CHECK-LABEL: @test_mul_canonicalize_multiple_uses( ; CHECK-LABEL: @test_mul_canonicalize_multiple_uses(
Show All 10 Lines

llvm/test/Transforms/InstCombine/operand-complexity.ll

; NOTE: Assertions have been autogenerated by utils/update_test_checks.py ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
; RUN: opt < %s -instcombine -S | FileCheck %s ; RUN: opt < %s -instcombine -S | FileCheck %s
; 'Negate' is considered less complex than a normal binop, so the mul should have the binop as the first operand. ; 'Negate' is considered less complex than a normal binop, so the mul should have the binop as the first operand.
lebedev.riUnsubmitted
Not Done
ReplyInline Actions

I guess this test no longer serves it's purpose.
Not sure what to do here.

lebedev.ri: I guess this test no longer serves it's purpose. Not sure what to do here.
shchenzAuthorUnsubmitted
Done
ReplyInline Actions

I changed the binop here to keep original testcases. It will not change these cases testing point.
new testcases for MUL canonicalization are all in file mul.ll.

shchenz: I changed the binop here to keep original testcases. It will not change these cases testing…
define i8 @neg(i8 %x) { define i8 @neg(i8 %x) {
; CHECK-LABEL: @neg( ; CHECK-LABEL: @neg(
; CHECK-NEXT: [[BO:%.*]] = udiv i8 [[X:%.*]], 42 ; CHECK-NEXT: [[BO:%.*]] = udiv i8 [[X:%.*]], 42
; CHECK-NEXT: [[NEGX:%.*]] = sub i8 0, [[X]] ; CHECK-NEXT: [[NEGX:%.*]] = sub i8 0, [[X]]
; CHECK-NEXT: [[R:%.*]] = mul i8 [[BO]], [[NEGX]] ; CHECK-NEXT: [[R:%.*]] = xor i8 [[BO]], [[NEGX]]
; CHECK-NEXT: ret i8 [[R]] ; CHECK-NEXT: ret i8 [[R]]
; ;
%bo = udiv i8 %x, 42 %bo = udiv i8 %x, 42
%negx = sub i8 0, %x %negx = sub i8 0, %x
%r = mul i8 %negx, %bo %r = xor i8 %negx, %bo
ret i8 %r ret i8 %r
} }
define <2 x i8> @neg_vec(<2 x i8> %x) { define <2 x i8> @neg_vec(<2 x i8> %x) {
; CHECK-LABEL: @neg_vec( ; CHECK-LABEL: @neg_vec(
; CHECK-NEXT: [[BO:%.*]] = udiv <2 x i8> [[X:%.*]], <i8 42, i8 -42> ; CHECK-NEXT: [[BO:%.*]] = udiv <2 x i8> [[X:%.*]], <i8 42, i8 -42>
; CHECK-NEXT: [[NEGX:%.*]] = sub <2 x i8> zeroinitializer, [[X]] ; CHECK-NEXT: [[NEGX:%.*]] = sub <2 x i8> zeroinitializer, [[X]]
; CHECK-NEXT: [[R:%.*]] = mul <2 x i8> [[BO]], [[NEGX]] ; CHECK-NEXT: [[R:%.*]] = xor <2 x i8> [[BO]], [[NEGX]]
; CHECK-NEXT: ret <2 x i8> [[R]] ; CHECK-NEXT: ret <2 x i8> [[R]]
; ;
%bo = udiv <2 x i8> %x, <i8 42, i8 -42> %bo = udiv <2 x i8> %x, <i8 42, i8 -42>
%negx = sub <2 x i8> <i8 0, i8 0>, %x %negx = sub <2 x i8> <i8 0, i8 0>, %x
%r = mul <2 x i8> %negx, %bo %r = xor <2 x i8> %negx, %bo
ret <2 x i8> %r ret <2 x i8> %r
} }
define <2 x i8> @neg_vec_undef(<2 x i8> %x) { define <2 x i8> @neg_vec_undef(<2 x i8> %x) {
; CHECK-LABEL: @neg_vec_undef( ; CHECK-LABEL: @neg_vec_undef(
; CHECK-NEXT: [[BO:%.*]] = udiv <2 x i8> [[X:%.*]], <i8 42, i8 -42> ; CHECK-NEXT: [[BO:%.*]] = udiv <2 x i8> [[X:%.*]], <i8 42, i8 -42>
; CHECK-NEXT: [[NEGX:%.*]] = sub <2 x i8> <i8 0, i8 undef>, [[X]] ; CHECK-NEXT: [[NEGX:%.*]] = sub <2 x i8> <i8 0, i8 undef>, [[X]]
; CHECK-NEXT: [[R:%.*]] = mul <2 x i8> [[BO]], [[NEGX]] ; CHECK-NEXT: [[R:%.*]] = xor <2 x i8> [[BO]], [[NEGX]]
; CHECK-NEXT: ret <2 x i8> [[R]] ; CHECK-NEXT: ret <2 x i8> [[R]]
; ;
%bo = udiv <2 x i8> %x, <i8 42, i8 -42> %bo = udiv <2 x i8> %x, <i8 42, i8 -42>
%negx = sub <2 x i8> <i8 0, i8 undef>, %x %negx = sub <2 x i8> <i8 0, i8 undef>, %x
%r = mul <2 x i8> %negx, %bo %r = xor <2 x i8> %negx, %bo
ret <2 x i8> %r ret <2 x i8> %r
} }
; 'Not' is considered less complex than a normal binop, so the mul should have the binop as the first operand. ; 'Not' is considered less complex than a normal binop, so the mul should have the binop as the first operand.
define i8 @not(i8 %x) { define i8 @not(i8 %x) {
; CHECK-LABEL: @not( ; CHECK-LABEL: @not(
; CHECK-NEXT: [[BO:%.*]] = udiv i8 [[X:%.*]], 42 ; CHECK-NEXT: [[BO:%.*]] = udiv i8 [[X:%.*]], 42
▲ Show 20 Lines • Show All 87 Lines • Show Last 20 Lines