Page MenuHomePhabricator

Reorder shuffle and binary operation.
ClosedPublic

Authored by sepavloff on Apr 27 2014, 9:46 AM.

Details

Summary

This patch allows simplification:

BinOp(shuffle(v1), shuffle(v2)) -> shuffle(BinOp(v1, v2))

if both shuffles use the same mask, and both shuffle within a single vector.

Diff Detail

Repository
rL LLVM

Event Timeline

sepavloff updated this revision to Diff 8874.Apr 27 2014, 9:46 AM
sepavloff retitled this revision from to Reorder shuffle and binary operation..
sepavloff updated this object.
sepavloff edited the test plan for this revision. (Show Details)
sepavloff added a subscriber: Unknown Object (MLST).
sepavloff updated this revision to Diff 9016.May 1 2014, 11:29 AM

Updated patch, added new pattern.

With this patch instcombiner tries making transformation like:

BinOp(shuffle(v1), const1) -> shuffle(BinOp(V1, const2))

This reordering allows removal of extra shuffles, for instance the code:

%t1 = shufflevector <4 x i32> %v, <4 x i32> undef, <4 x i32> <i32 3, i32 2, i32 1, i32 0>
%t2 = mul <4 x i32> %t1, %t1
%r = shufflevector <4 x i32> %t2, <4 x i32> undef, <4 x i32> <i32 3, i32 2, i32 1, i32 0>

transforms to:

%1 = mul <4 x i32> %v, %v
bkramer added inline comments.May 2 2014, 9:50 AM
lib/Transforms/InstCombine/InstructionCombining.cpp
1125–1131 ↗(On Diff #9016)

This could be

std::equal(LHSMask.begin(), LHSMask.end(), RHSMask.begin())
1143–1148 ↗(On Diff #9016)

If you have a binary operator with a shuffle and a constant, the constant will always be canonicalized to the RHS.

sepavloff updated this revision to Diff 9078.May 5 2014, 8:32 AM

Updated patch

Thank you for feedback!

lib/Transforms/InstCombine/InstructionCombining.cpp
1125–1131 ↗(On Diff #9016)

Indeed. Replaced.

1143–1148 ↗(On Diff #9016)

This transformation should also be applicable to non-commutative operations such as div, sub.

I think this is good now. Adding nadav to make sure I didn't miss some shufflevector lowering issue.

Thank you for review!
Waiting nadav's opinion.

--Serge

2014-05-10 0:42 GMT+07:00 Benjamin Kramer <benny.kra@gmail.com>:

I think this is good now. Adding nadav to make sure I didn't miss some
shufflevector lowering issue.

http://reviews.llvm.org/D3525

andreadb added inline comments.
lib/Transforms/InstCombine/InstructionCombining.cpp
1123–1125 ↗(On Diff #9078)

I might be wrong but,
wouldn't be easier in this case to simply compare the addresses of the two shuffle masks?

As far as I understand, the shuffle mask (third operand of a ShuffleVectorInst) is always a Constant; therefore, you should be able to check if two masks are equal by simply comparing their addresses. I expect that something like this should work:

cast<ShuffleVectorInst>(LHS)->getMask() == cast<ShuffleVectorInst>(RHS)->getMask().

quoting what is written in Constant.h, "two structurally equivalent constants will always have the same address". Also, "The shuffle mask operand is required to be a constant vector with either constant integer or undef values".

I hope this helps.

nadav edited edge metadata.May 9 2014, 12:39 PM

I did not review the code carefully but I think it looks fine. We are not generating new shuffle masks so there should not be any lowering problems.

Thank you for advice and detailed explanation!
I updated the patch according your recommendation.

--Serge

2014-05-10 1:17 GMT+07:00 Andrea Di Biagio <Andrea_DiBiagio@sn.scee.net>:

================
Comment at: lib/Transforms/InstCombine/InstructionCombining.cpp:1123-1125
@@ +1122,5 @@
+ isa<UndefValue>(RShuf->getOperand(1))) {
+ SmallVector<int, 16> LHSMask = LShuf->getShuffleMask();
+ SmallVector<int, 16> RHSMask = RShuf->getShuffleMask();
+ if (std::equal(LHSMask.begin(), LHSMask.end(), RHSMask.begin())) {
+ BinaryOperator *NewBO = CreateBinOpAsGiven(Inst,
LShuf->getOperand(0),


I might be wrong but,
wouldn't be easier in this case to simply compare the addresses of the two
shuffle masks?

As far as I understand, the shuffle mask (third operand of a
ShuffleVectorInst) is always a Constant; therefore, you should be able to
check if two masks are equal by simply comparing their addresses. I expect
that something like this should work:

cast<ShuffleVectorInst>(LHS)->getMask() ==
cast<ShuffleVectorInst>(RHS)->getMask().

quoting what is written in Constant.h, "two structurally equivalent
constants will always have the same address". Also, "The shuffle mask
operand is required to be a constant vector with either constant integer or
undef values".

I hope this helps.

http://reviews.llvm.org/D3525

Hi Serge,

It seems that your patch introduces a bug when two shuffles have different
operand types.
See more details in http://llvm.org/bugs/show_bug.cgi?id=19717.

Thanks,
-Hao

-----Original Message-----
From: llvm-commits-bounces@cs.uiuc.edu [mailto:llvm-commits-
bounces@cs.uiuc.edu] On Behalf Of Serge Pavlov
Sent: Sunday, May 11, 2014 4:42 PM
To: sepavloff@gmail.com; eli.friedman@gmail.com; benny.kra@gmail.com;
nrotem@apple.com
Cc: llvm-commits@cs.uiuc.edu
Subject: Re: [PATCH] Reorder shuffle and binary operation.

Thank you for advice and detailed explanation!
I updated the patch according your recommendation.

--Serge

2014-05-10 1:17 GMT+07:00 Andrea Di Biagio
<Andrea_DiBiagio@sn.scee.net>:

> ================
> Comment at:
> lib/Transforms/InstCombine/InstructionCombining.cpp:1123-1125
> @@ +1122,5 @@
> + isa<UndefValue>(RShuf->getOperand(1))) {
> + SmallVector<int, 16> LHSMask = LShuf->getShuffleMask();
> + SmallVector<int, 16> RHSMask = RShuf->getShuffleMask();
> + if (std::equal(LHSMask.begin(), LHSMask.end(), RHSMask.begin()))

{

> + BinaryOperator *NewBO = CreateBinOpAsGiven(Inst,
> LShuf->getOperand(0),
> ----------------
> I might be wrong but,
> wouldn't be easier in this case to simply compare the addresses of the
> two shuffle masks?
>
> As far as I understand, the shuffle mask (third operand of a
> ShuffleVectorInst) is always a Constant; therefore, you should be able
> to check if two masks are equal by simply comparing their addresses. I
> expect that something like this should work:
>
> cast<ShuffleVectorInst>(LHS)->getMask() ==
> cast<ShuffleVectorInst>(RHS)->getMask().
>
> quoting what is written in Constant.h, "two structurally equivalent
> constants will always have the same address". Also, "The shuffle mask
> operand is required to be a constant vector with either constant
> integer or undef values".
>
> I hope this helps.
>
> http://reviews.llvm.org/D3525
>
>
>

http://reviews.llvm.org/D3525


llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

Thank you for catching that.
In the revision 208518 this problem must be fixed.

Hi Serge,

It seems there is another bug. Also see http://llvm.org/bugs/show_bug.cgi?id=19717.

Thanks,
-Hao

Hi Serge,

It seems that there is another bug http://llvm.org/bugs/show_bug.cgi?id=19730.
When two shuffles have different types and the same mask, there may be an assertion failure.

Thanks,
-Hao

-----Original Message-----
From: llvm-commits-bounces@cs.uiuc.edu [mailto:llvm-commits-
bounces@cs.uiuc.edu] On Behalf Of Hao Liu
Sent: Monday, May 12, 2014 11:20 AM
To: reviews+D3525+public+b0fd3ed101ab4b75@reviews.llvm.org;
eli.friedman@gmail.com; benny.kra@gmail.com; nrotem@apple.com
Cc: llvm-commits@cs.uiuc.edu
Subject: RE: [PATCH] Reorder shuffle and binary operation.

Hi Serge,

It seems that your patch introduces a bug when two shuffles have different
operand types.
See more details in http://llvm.org/bugs/show_bug.cgi?id=19717.

Thanks,
-Hao

> -----Original Message-----
> From: llvm-commits-bounces@cs.uiuc.edu [mailto:llvm-commits-
> bounces@cs.uiuc.edu] On Behalf Of Serge Pavlov
> Sent: Sunday, May 11, 2014 4:42 PM
> To: sepavloff@gmail.com; eli.friedman@gmail.com; benny.kra@gmail.com;
> nrotem@apple.com
> Cc: llvm-commits@cs.uiuc.edu
> Subject: Re: [PATCH] Reorder shuffle and binary operation.
>
> Thank you for advice and detailed explanation!
> I updated the patch according your recommendation.
>
> --Serge
>
>
> 2014-05-10 1:17 GMT+07:00 Andrea Di Biagio
> <Andrea_DiBiagio@sn.scee.net>:
>
> > ================
> > Comment at:
> > lib/Transforms/InstCombine/InstructionCombining.cpp:1123-1125
> > @@ +1122,5 @@
> > + isa<UndefValue>(RShuf->getOperand(1))) {
> > + SmallVector<int, 16> LHSMask = LShuf->getShuffleMask();
> > + SmallVector<int, 16> RHSMask = RShuf->getShuffleMask();
> > + if (std::equal(LHSMask.begin(), LHSMask.end(),
> > + RHSMask.begin()))
{
> > + BinaryOperator *NewBO = CreateBinOpAsGiven(Inst,
> > LShuf->getOperand(0),
> > ----------------
> > I might be wrong but,
> > wouldn't be easier in this case to simply compare the addresses of
> > the two shuffle masks?
> >
> > As far as I understand, the shuffle mask (third operand of a
> > ShuffleVectorInst) is always a Constant; therefore, you should be
> > able to check if two masks are equal by simply comparing their
> > addresses. I expect that something like this should work:
> >
> > cast<ShuffleVectorInst>(LHS)->getMask() ==
> > cast<ShuffleVectorInst>(RHS)->getMask().
> >
> > quoting what is written in Constant.h, "two structurally equivalent
> > constants will always have the same address". Also, "The shuffle
> > mask operand is required to be a constant vector with either
> > constant integer or undef values".
> >
> > I hope this helps.
> >
> > http://reviews.llvm.org/D3525
> >
> >
> >
>
> http://reviews.llvm.org/D3525
>
>
>
> _______________________________________________
> llvm-commits mailing list
> llvm-commits@cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits


llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

  • IMPORTANT NOTICE: The contents of this email and any attachments are confidential and may also be privileged. If you are not the intended recipient, please notify the sender immediately and do not disclose the contents to any other person, use it for any purpose, or store or copy the information in any medium. Thank you.

ARM Limited, Registered office 110 Fulbourn Road, Cambridge CB1 9NJ, Registered in England & Wales, Company No: 2557590
ARM Holdings plc, Registered office 110 Fulbourn Road, Cambridge CB1 9NJ, Registered in England & Wales, Company No: 2548782

Hi Serge,

Sorry to bother you again.
It seems there is still a bug http://llvm.org/bugs/show_bug.cgi?id=19737
when creating binary operator.
I've looked at your code. Except this minor bug, your patch may not have any
other problems.

Thanks,
-Hao

-----Original Message-----
From: llvm-commits-bounces@cs.uiuc.edu [mailto:llvm-commits-
bounces@cs.uiuc.edu] On Behalf Of Hao Liu
Sent: Monday, May 12, 2014 11:20 AM
To: reviews+D3525+public+b0fd3ed101ab4b75@reviews.llvm.org;
eli.friedman@gmail.com; benny.kra@gmail.com; nrotem@apple.com
Cc: llvm-commits@cs.uiuc.edu
Subject: RE: [PATCH] Reorder shuffle and binary operation.

Hi Serge,

It seems that your patch introduces a bug when two shuffles have different
operand types.
See more details in http://llvm.org/bugs/show_bug.cgi?id=19717.

Thanks,
-Hao

> -----Original Message-----
> From: llvm-commits-bounces@cs.uiuc.edu [mailto:llvm-commits-
> bounces@cs.uiuc.edu] On Behalf Of Serge Pavlov
> Sent: Sunday, May 11, 2014 4:42 PM
> To: sepavloff@gmail.com; eli.friedman@gmail.com; benny.kra@gmail.com;
> nrotem@apple.com
> Cc: llvm-commits@cs.uiuc.edu
> Subject: Re: [PATCH] Reorder shuffle and binary operation.
>
> Thank you for advice and detailed explanation!
> I updated the patch according your recommendation.
>
> --Serge
>
>
> 2014-05-10 1:17 GMT+07:00 Andrea Di Biagio
> <Andrea_DiBiagio@sn.scee.net>:
>
> > ================
> > Comment at:
> > lib/Transforms/InstCombine/InstructionCombining.cpp:1123-1125
> > @@ +1122,5 @@
> > + isa<UndefValue>(RShuf->getOperand(1))) {
> > + SmallVector<int, 16> LHSMask = LShuf->getShuffleMask();
> > + SmallVector<int, 16> RHSMask = RShuf->getShuffleMask();
> > + if (std::equal(LHSMask.begin(), LHSMask.end(),
> > + RHSMask.begin()))
{
> > + BinaryOperator *NewBO = CreateBinOpAsGiven(Inst,
> > LShuf->getOperand(0),
> > ----------------
> > I might be wrong but,
> > wouldn't be easier in this case to simply compare the addresses of
> > the two shuffle masks?
> >
> > As far as I understand, the shuffle mask (third operand of a
> > ShuffleVectorInst) is always a Constant; therefore, you should be
> > able to check if two masks are equal by simply comparing their
> > addresses. I expect that something like this should work:
> >
> > cast<ShuffleVectorInst>(LHS)->getMask() ==
> > cast<ShuffleVectorInst>(RHS)->getMask().
> >
> > quoting what is written in Constant.h, "two structurally equivalent
> > constants will always have the same address". Also, "The shuffle
> > mask operand is required to be a constant vector with either
> > constant integer or undef values".
> >
> > I hope this helps.
> >
> > http://reviews.llvm.org/D3525
> >
> >
> >
>
> http://reviews.llvm.org/D3525
>
>
>
> _______________________________________________
> llvm-commits mailing list
> llvm-commits@cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits


llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

Hi Serge,

This patch has been breaking our internal builders since Sunday - it breaks
all random vector intrinsics tests.

Thanks for responding so quickly to the first reported bug but we've had one
outstanding since Monday morning. As it is now Wednesday, I think unless you
can address this soon we should start thinking about reverting this change
until you fix it.

Do you have any idea when you could get around to it?

Cheers,

James

-----Original Message-----
From: llvm-commits-bounces@cs.uiuc.edu [mailto:llvm-commits-
bounces@cs.uiuc.edu] On Behalf Of Hao Liu
Sent: 14 May 2014 07:30
To: sepavloff@gmail.com; eli.friedman@gmail.com; benny.kra@gmail.com;
nrotem@apple.com
Cc: llvm-commits@cs.uiuc.edu
Subject: Re: [PATCH] Reorder shuffle and binary operation.

Hi Serge,

Sorry to bother you again.
It seems there is still a bug http://llvm.org/bugs/show_bug.cgi?id=19737
when creating binary operator.
I've looked at your code. Except this minor bug, your patch may not have

any

other problems.

Thanks,
-Hao

> -----Original Message-----
> From: llvm-commits-bounces@cs.uiuc.edu [mailto:llvm-commits-
> bounces@cs.uiuc.edu] On Behalf Of Hao Liu
> Sent: Monday, May 12, 2014 11:20 AM
> To: reviews+D3525+public+b0fd3ed101ab4b75@reviews.llvm.org;
> eli.friedman@gmail.com; benny.kra@gmail.com; nrotem@apple.com
> Cc: llvm-commits@cs.uiuc.edu
> Subject: RE: [PATCH] Reorder shuffle and binary operation.
>
> Hi Serge,
>
> It seems that your patch introduces a bug when two shuffles have
different
> operand types.
> See more details in http://llvm.org/bugs/show_bug.cgi?id=19717.
>
> Thanks,
> -Hao
>
> > -----Original Message-----
> > From: llvm-commits-bounces@cs.uiuc.edu [mailto:llvm-commits-
> > bounces@cs.uiuc.edu] On Behalf Of Serge Pavlov
> > Sent: Sunday, May 11, 2014 4:42 PM
> > To: sepavloff@gmail.com; eli.friedman@gmail.com;
benny.kra@gmail.com;
> > nrotem@apple.com
> > Cc: llvm-commits@cs.uiuc.edu
> > Subject: Re: [PATCH] Reorder shuffle and binary operation.
> >
> > Thank you for advice and detailed explanation!
> > I updated the patch according your recommendation.
> >
> > --Serge
> >
> >
> > 2014-05-10 1:17 GMT+07:00 Andrea Di Biagio
> > <Andrea_DiBiagio@sn.scee.net>:
> >
> > > ================
> > > Comment at:
> > > lib/Transforms/InstCombine/InstructionCombining.cpp:1123-1125
> > > @@ +1122,5 @@
> > > + isa<UndefValue>(RShuf->getOperand(1))) {
> > > + SmallVector<int, 16> LHSMask = LShuf->getShuffleMask();
> > > + SmallVector<int, 16> RHSMask = RShuf->getShuffleMask();
> > > + if (std::equal(LHSMask.begin(), LHSMask.end(),
> > > + RHSMask.begin()))
> {
> > > + BinaryOperator *NewBO = CreateBinOpAsGiven(Inst,
> > > LShuf->getOperand(0),
> > > ----------------
> > > I might be wrong but,
> > > wouldn't be easier in this case to simply compare the addresses of
> > > the two shuffle masks?
> > >
> > > As far as I understand, the shuffle mask (third operand of a
> > > ShuffleVectorInst) is always a Constant; therefore, you should be
> > > able to check if two masks are equal by simply comparing their
> > > addresses. I expect that something like this should work:
> > >
> > > cast<ShuffleVectorInst>(LHS)->getMask() ==
> > > cast<ShuffleVectorInst>(RHS)->getMask().
> > >
> > > quoting what is written in Constant.h, "two structurally equivalent
> > > constants will always have the same address". Also, "The shuffle
> > > mask operand is required to be a constant vector with either
> > > constant integer or undef values".
> > >
> > > I hope this helps.
> > >
> > > http://reviews.llvm.org/D3525
> > >
> > >
> > >
> >
> > http://reviews.llvm.org/D3525
> >
> >
> >
> > _______________________________________________
> > llvm-commits mailing list
> > llvm-commits@cs.uiuc.edu
> > http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
>
>
>
>
> _______________________________________________
> llvm-commits mailing list
> llvm-commits@cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

http://reviews.llvm.org/D3525


llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

Hi James,

I regret that the fix makes you troubles. Nor llvm tests neither test-suit discovered any problems, you have a nice test suit and I am thankful to Hao for providing test cases. All reported problems were resolved in < 4 hours, did you reported the problem that is outstanding since Monday morning?

Thanks,
--Serge

sepavloff closed this revision.May 19 2014, 7:24 AM
sepavloff updated this revision to Diff 9556.

Closed by commit rL208488 (authored by @sepavloff).