thr3ads.net - llvm dev - [LLVMdev] Naryreassociate vs reassociate [May 2015]

If this information is useful, please help other people find it:
Share via:

Daniel Berlin

2015-May-04 23:45 UTC

[LLVMdev] Naryreassociate vs reassociate

Whoops, forgot llvmdev


On Mon, May 4, 2015 at 4:12 PM, Daniel Berlin <dberlin at dberlin.org>
wrote:> So i started by looking at naryreassociate, whose pass
> description/reason listed for doing it is actually describes bug in
> reassociate, and discovered that, in fact, reassociate seems broken,
> and should be doing the right thing on most of your testcases.
>
> Let's take nary-add.ll, left_reassociate
>
> ; RUN: opt < %s -nary-reassociate -S | FileCheck %s
>
> target datalayout = "e-i64:64-v16:16-v32:32-n16:32:64"
>
> declare void @foo(i32)
>
> ; foo(a + c);
> ; foo((a + (b + c));
> ;   =>
> ; t = a + c;
> ; foo(t);
> ; foo(t + b);
> define void @left_reassociate(i32 %a, i32 %b, i32 %c) {
>   %1 = add i32 %a, %c
>   call void @foo(i32 %1)
>   %2 = add i32 %b, %c
>   %3 = add i32 %a, %2
>   call void @foo(i32 %3)
>   ret void
> }
>
>
> normal reassociate transforms this, IMHO, wrongly, into:
>
> define void @left_reassociate(i32 %a, i32 %b, i32 %c) {
>   %1 = add i32 %c, %a
>   call void @foo(i32 %1)
>   %2 = add i32 %b, %a
>   %3 = add i32 %2, %c
>   call void @foo(i32 %3)
>   ret void
> }
>
>
> This is because for the first expression:
>
> RAIn: add i32 [ %a, #3] [ %c, #5]
> RAOut: add i32 [ %c, #5] [ %a, #3]
>
>
> and
> for the second:
> RAIn: add i32 [ %a, #3] [ %b, #4] [ %c, #5]
> RAOut: add i32 [ %c, #5] [ %b, #4] [ %a, #3]
>
>
> This makes it transform the first into add c, a
> and the second into
> %1 = add b, a
> add c, %1
>
>
> This is caused by these arguments having different ranks (because they
> are function arguments), and it not respecting the same order it has
> already chosen once.
>
>
> This is, IMHO, pretty clearly a bug.
>
> It screws up right_reassociate, no_reassociate, and conditional tests
> for the same reason.
>
> If you fix this, i expect you will find a lot less use cases for
> nary-reassociate.
>
>
> The simple way to fix this is to mark which operands it's paired
> together in the past, and always try to pair the same ones together if
> it can, regardless of rank.
Or simply adjust the ranks of paired operands to be the same and
different from all other ranks

(BBrank is << 16, so you should have room do to this)

Jingyue Wu

2015-May-05 17:20 UTC

head link

[LLVMdev] Naryreassociate vs reassociate

Hi Daniel,

I presume you mean, instead of assigning function arguments distinct ranks (
http://llvm.org/docs/doxygen/html/Reassociate_8cpp_source.html#l00282), we
should group function arguments in favor of existing pairings. You are not
suggesting discarding the entire ranking system, right?

I'll look into how that works on my benchmarks. AFAIK, we encountered some
cases that seem beyond the fix you suggested. These cases involve
constants, and I attached one reduced example in
https://llvm.org/bugs/show_bug.cgi?id=22357.

void foo(int a, int b, int c, int *x, int *y) {
  *x = (a + b);
  *y = (a + 2) + b;
}

Reassociate assigns constants a lower rank than variables, which prevents
Reassociate from transforming the above example to

*x = a + b;
*y = (a + b) + 2;

Jingyue

On Mon, May 4, 2015 at 4:45 PM Daniel Berlin <dberlin at dberlin.org>
wrote:
> Whoops, forgot llvmdev
>
>
> On Mon, May 4, 2015 at 4:12 PM, Daniel Berlin <dberlin at
dberlin.org> wrote:
> > So i started by looking at naryreassociate, whose pass
> > description/reason listed for doing it is actually describes bug in
> > reassociate, and discovered that, in fact, reassociate seems broken,
> > and should be doing the right thing on most of your testcases.
> >
> > Let's take nary-add.ll, left_reassociate
> >
> > ; RUN: opt < %s -nary-reassociate -S | FileCheck %s
> >
> > target datalayout = "e-i64:64-v16:16-v32:32-n16:32:64"
> >
> > declare void @foo(i32)
> >
> > ; foo(a + c);
> > ; foo((a + (b + c));
> > ;   =>
> > ; t = a + c;
> > ; foo(t);
> > ; foo(t + b);
> > define void @left_reassociate(i32 %a, i32 %b, i32 %c) {
> >   %1 = add i32 %a, %c
> >   call void @foo(i32 %1)
> >   %2 = add i32 %b, %c
> >   %3 = add i32 %a, %2
> >   call void @foo(i32 %3)
> >   ret void
> > }
> >
> >
> > normal reassociate transforms this, IMHO, wrongly, into:
> >
> > define void @left_reassociate(i32 %a, i32 %b, i32 %c) {
> >   %1 = add i32 %c, %a
> >   call void @foo(i32 %1)
> >   %2 = add i32 %b, %a
> >   %3 = add i32 %2, %c
> >   call void @foo(i32 %3)
> >   ret void
> > }
> >
> >
> > This is because for the first expression:
> >
> > RAIn: add i32 [ %a, #3] [ %c, #5]
> > RAOut: add i32 [ %c, #5] [ %a, #3]
> >
> >
> > and
> > for the second:
> > RAIn: add i32 [ %a, #3] [ %b, #4] [ %c, #5]
> > RAOut: add i32 [ %c, #5] [ %b, #4] [ %a, #3]
> >
> >
> > This makes it transform the first into add c, a
> > and the second into
> > %1 = add b, a
> > add c, %1
> >
> >
> > This is caused by these arguments having different ranks (because they
> > are function arguments), and it not respecting the same order it has
> > already chosen once.
> >
> >
> > This is, IMHO, pretty clearly a bug.
> >
> > It screws up right_reassociate, no_reassociate, and conditional tests
> > for the same reason.
> >
> > If you fix this, i expect you will find a lot less use cases for
> > nary-reassociate.
> >
> >
> > The simple way to fix this is to mark which operands it's paired
> > together in the past, and always try to pair the same ones together if
> > it can, regardless of rank.
>
> Or simply adjust the ranks of paired operands to be the same and
> different from all other ranks
>
> (BBrank is << 16, so you should have room do to this)
>-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150505/f07cb7d4/attachment.html>

Daniel Berlin

2015-May-05 17:31 UTC

head link

[LLVMdev] Naryreassociate vs reassociate

On Tue, May 5, 2015 at 10:20 AM, Jingyue Wu <jingyue at google.com>
wrote:> Hi Daniel,
>
> I presume you mean, instead of assigning function arguments distinct ranks
> (http://llvm.org/docs/doxygen/html/Reassociate_8cpp_source.html#l00282), we
> should group function arguments in favor of existing pairings.
Existing = pairings reassociate already chose before
*not*
existing = pairings that already exist in the source IR

Given that, we should probably group everything in favor of existing
pairings when possible.

> You are not
> suggesting discarding the entire ranking system, right?
The only three cases that should matter hugely are constants,
arguments, and non-movable instructions.

The rest should hopefully already end up with consistent decisions.
If not, we have larger problems.

> I'll look into how that works on my benchmarks. AFAIK, we encountered
some
> cases that seem beyond the fix you suggested. These cases involve
constants,
> and I attached one reduced example in
> https://llvm.org/bugs/show_bug.cgi?id=22357.
>
> void foo(int a, int b, int c, int *x, int *y) {
>   *x = (a + b);
>   *y = (a + 2) + b;
> }
>
> Reassociate assigns constants a lower rank than variables, which prevents
> Reassociate from transforming the above example to
>
> *x = a + b;
> *y = (a + b) + 2;
>
This is a variant of the problem above, except you are getting ranks
0, 1, 2 vs 1, 2

It thus chooses 0,1 as one tree, and 2 as the other for the A+b+2 case.

If we made it make consistent decisions, you would get the right results.

There is an optimal order to make these decisions in, too.  It
probably should be making decisions in order of smallest computation
tree to largest computation tree, because the small trees have the
least freedom.  Otherwise, you have the same problem if you write this
as:
 *y = (a + 2) + b;
 *x = a + b;
instead :)

(IE if you don't process smallest to largest, you will choose a+2+b,
and not be able to make a decision consistent with that when you get
to the a+b tree)

The above change should not be difficult. I'll take a crack at it
today and send you a patch.


> Jingyue
>
> On Mon, May 4, 2015 at 4:45 PM Daniel Berlin <dberlin at dberlin.org>
wrote:
>>
>> Whoops, forgot llvmdev
>>
>>
>> On Mon, May 4, 2015 at 4:12 PM, Daniel Berlin <dberlin at
dberlin.org> wrote:
>> > So i started by looking at naryreassociate, whose pass
>> > description/reason listed for doing it is actually describes bug
in
>> > reassociate, and discovered that, in fact, reassociate seems
broken,
>> > and should be doing the right thing on most of your testcases.
>> >
>> > Let's take nary-add.ll, left_reassociate
>> >
>> > ; RUN: opt < %s -nary-reassociate -S | FileCheck %s
>> >
>> > target datalayout = "e-i64:64-v16:16-v32:32-n16:32:64"
>> >
>> > declare void @foo(i32)
>> >
>> > ; foo(a + c);
>> > ; foo((a + (b + c));
>> > ;   =>
>> > ; t = a + c;
>> > ; foo(t);
>> > ; foo(t + b);
>> > define void @left_reassociate(i32 %a, i32 %b, i32 %c) {
>> >   %1 = add i32 %a, %c
>> >   call void @foo(i32 %1)
>> >   %2 = add i32 %b, %c
>> >   %3 = add i32 %a, %2
>> >   call void @foo(i32 %3)
>> >   ret void
>> > }
>> >
>> >
>> > normal reassociate transforms this, IMHO, wrongly, into:
>> >
>> > define void @left_reassociate(i32 %a, i32 %b, i32 %c) {
>> >   %1 = add i32 %c, %a
>> >   call void @foo(i32 %1)
>> >   %2 = add i32 %b, %a
>> >   %3 = add i32 %2, %c
>> >   call void @foo(i32 %3)
>> >   ret void
>> > }
>> >
>> >
>> > This is because for the first expression:
>> >
>> > RAIn: add i32 [ %a, #3] [ %c, #5]
>> > RAOut: add i32 [ %c, #5] [ %a, #3]
>> >
>> >
>> > and
>> > for the second:
>> > RAIn: add i32 [ %a, #3] [ %b, #4] [ %c, #5]
>> > RAOut: add i32 [ %c, #5] [ %b, #4] [ %a, #3]
>> >
>> >
>> > This makes it transform the first into add c, a
>> > and the second into
>> > %1 = add b, a
>> > add c, %1
>> >
>> >
>> > This is caused by these arguments having different ranks (because
they
>> > are function arguments), and it not respecting the same order it
has
>> > already chosen once.
>> >
>> >
>> > This is, IMHO, pretty clearly a bug.
>> >
>> > It screws up right_reassociate, no_reassociate, and conditional
tests
>> > for the same reason.
>> >
>> > If you fix this, i expect you will find a lot less use cases for
>> > nary-reassociate.
>> >
>> >
>> > The simple way to fix this is to mark which operands it's
paired
>> > together in the past, and always try to pair the same ones
together if
>> > it can, regardless of rank.
>>
>> Or simply adjust the ranks of paired operands to be the same and
>> different from all other ranks
>>
>> (BBrank is << 16, so you should have room do to this)

Possibly Parallel Threads

Search for more reasonably related threads

llvm dev - May 2015 - [LLVMdev] Naryreassociate vs reassociate

[LLVMdev] Naryreassociate vs reassociate

[LLVMdev] Naryreassociate vs reassociate

[LLVMdev] Naryreassociate vs reassociate

Possibly Parallel Threads