[LLVMdev] Naryreassociate vs reassociate

Tue May 5 13:09:47 PDT 2015

On Tue, May 5, 2015 at 10:31 AM, Daniel Berlin <dberlin at dberlin.org> wrote:

> 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.
>

Makes sense.

>
>
> > 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
>

The key difference is that constants are designed to be lowest ranked, and
then the current reassociation algorithm always groups the constant 2 with
other variables. Looks like your new solution will favor existing pairings
regardless of the ranks. Then, it should be able to solve the a+b+2 case
nicely.

>
> 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.
>
>
>
Great! Thank you! Things will be clearer when I see your 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)
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150505/d10900a7/attachment.html>