[LLVMdev] Naryreassociate vs reassociate

[Daniel Berlin]

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)