<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Tue, May 5, 2015 at 10:31 AM, Daniel Berlin <span dir="ltr"><<a href="mailto:dberlin@dberlin.org" target="_blank">dberlin@dberlin.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class="">On Tue, May 5, 2015 at 10:20 AM, Jingyue Wu <<a href="mailto:jingyue@google.com">jingyue@google.com</a>> wrote:<br>
> Hi Daniel,<br>
><br>
> I presume you mean, instead of assigning function arguments distinct ranks<br>
> (<a href="http://llvm.org/docs/doxygen/html/Reassociate_8cpp_source.html#l00282" target="_blank">http://llvm.org/docs/doxygen/html/Reassociate_8cpp_source.html#l00282</a>), we<br>
> should group function arguments in favor of existing pairings.<br>
<br>
</span>Existing = pairings reassociate already chose before<br>
*not*<br>
existing = pairings that already exist in the source IR<br>
<br>
Given that, we should probably group everything in favor of existing<br>
pairings when possible.<br></blockquote><div><br></div><div>Makes sense. </div><div> <br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<span class=""><br>
<br>
> You are not<br>
> suggesting discarding the entire ranking system, right?<br>
<br>
</span>The only three cases that should matter hugely are constants,<br>
arguments, and non-movable instructions.<br>
<br>
The rest should hopefully already end up with consistent decisions.<br>
If not, we have larger problems.<br>
<span class=""><br>
<br>
> I'll look into how that works on my benchmarks. AFAIK, we encountered some<br>
> cases that seem beyond the fix you suggested. These cases involve constants,<br>
> and I attached one reduced example in<br>
> <a href="https://llvm.org/bugs/show_bug.cgi?id=22357" target="_blank">https://llvm.org/bugs/show_bug.cgi?id=22357</a>.<br>
><br>
<br>
> void foo(int a, int b, int c, int *x, int *y) {<br>
>   *x = (a + b);<br>
>   *y = (a + 2) + b;<br>
> }<br>
><br>
> Reassociate assigns constants a lower rank than variables, which prevents<br>
> Reassociate from transforming the above example to<br>
><br>
> *x = a + b;<br>
> *y = (a + b) + 2;<br>
><br>
<br>
</span>This is a variant of the problem above, except you are getting ranks<br>
0, 1, 2 vs 1, 2<br></blockquote><div><br></div><div>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. </div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
It thus chooses 0,1 as one tree, and 2 as the other for the A+b+2 case.<br>
<br>
If we made it make consistent decisions, you would get the right results.<br>
<br>
There is an optimal order to make these decisions in, too.  It<br>
probably should be making decisions in order of smallest computation<br>
tree to largest computation tree, because the small trees have the<br>
least freedom.  Otherwise, you have the same problem if you write this<br>
as:<br>
<span class=""> *y = (a + 2) + b;<br>
</span><span class=""> *x = a + b;<br>
</span>instead :)<br>
<br>
(IE if you don't process smallest to largest, you will choose a+2+b,<br>
and not be able to make a decision consistent with that when you get<br>
to the a+b tree)<br>
<br>
The above change should not be difficult. I'll take a crack at it<br>
today and send you a patch.<br>
<div class="HOEnZb"><div class="h5"><br>
<br></div></div></blockquote><div><br></div><div>Great! Thank you! Things will be clearer when I see your patch. </div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="HOEnZb"><div class="h5">
<br>
> Jingyue<br>
><br>
> On Mon, May 4, 2015 at 4:45 PM Daniel Berlin <<a href="mailto:dberlin@dberlin.org">dberlin@dberlin.org</a>> wrote:<br>
>><br>
>> Whoops, forgot llvmdev<br>
>><br>
>><br>
>> On Mon, May 4, 2015 at 4:12 PM, Daniel Berlin <<a href="mailto:dberlin@dberlin.org">dberlin@dberlin.org</a>> wrote:<br>
>> > So i started by looking at naryreassociate, whose pass<br>
>> > description/reason listed for doing it is actually describes bug in<br>
>> > reassociate, and discovered that, in fact, reassociate seems broken,<br>
>> > and should be doing the right thing on most of your testcases.<br>
>> ><br>
>> > Let's take nary-add.ll, left_reassociate<br>
>> ><br>
>> > ; RUN: opt < %s -nary-reassociate -S | FileCheck %s<br>
>> ><br>
>> > target datalayout = "e-i64:64-v16:16-v32:32-n16:32:64"<br>
>> ><br>
>> > declare void @foo(i32)<br>
>> ><br>
>> > ; foo(a + c);<br>
>> > ; foo((a + (b + c));<br>
>> > ;   =><br>
>> > ; t = a + c;<br>
>> > ; foo(t);<br>
>> > ; foo(t + b);<br>
>> > define void @left_reassociate(i32 %a, i32 %b, i32 %c) {<br>
>> >   %1 = add i32 %a, %c<br>
>> >   call void @foo(i32 %1)<br>
>> >   %2 = add i32 %b, %c<br>
>> >   %3 = add i32 %a, %2<br>
>> >   call void @foo(i32 %3)<br>
>> >   ret void<br>
>> > }<br>
>> ><br>
>> ><br>
>> > normal reassociate transforms this, IMHO, wrongly, into:<br>
>> ><br>
>> > define void @left_reassociate(i32 %a, i32 %b, i32 %c) {<br>
>> >   %1 = add i32 %c, %a<br>
>> >   call void @foo(i32 %1)<br>
>> >   %2 = add i32 %b, %a<br>
>> >   %3 = add i32 %2, %c<br>
>> >   call void @foo(i32 %3)<br>
>> >   ret void<br>
>> > }<br>
>> ><br>
>> ><br>
>> > This is because for the first expression:<br>
>> ><br>
>> > RAIn: add i32 [ %a, #3] [ %c, #5]<br>
>> > RAOut: add i32 [ %c, #5] [ %a, #3]<br>
>> ><br>
>> ><br>
>> > and<br>
>> > for the second:<br>
>> > RAIn: add i32 [ %a, #3] [ %b, #4] [ %c, #5]<br>
>> > RAOut: add i32 [ %c, #5] [ %b, #4] [ %a, #3]<br>
>> ><br>
>> ><br>
>> > This makes it transform the first into add c, a<br>
>> > and the second into<br>
>> > %1 = add b, a<br>
>> > add c, %1<br>
>> ><br>
>> ><br>
>> > This is caused by these arguments having different ranks (because they<br>
>> > are function arguments), and it not respecting the same order it has<br>
>> > already chosen once.<br>
>> ><br>
>> ><br>
>> > This is, IMHO, pretty clearly a bug.<br>
>> ><br>
>> > It screws up right_reassociate, no_reassociate, and conditional tests<br>
>> > for the same reason.<br>
>> ><br>
>> > If you fix this, i expect you will find a lot less use cases for<br>
>> > nary-reassociate.<br>
>> ><br>
>> ><br>
>> > The simple way to fix this is to mark which operands it's paired<br>
>> > together in the past, and always try to pair the same ones together if<br>
>> > it can, regardless of rank.<br>
>><br>
>> Or simply adjust the ranks of paired operands to be the same and<br>
>> different from all other ranks<br>
>><br>
>> (BBrank is << 16, so you should have room do to this)<br>
</div></div></blockquote></div><br></div></div>