[LLVMdev] Naryreassociate vs reassociate

[Daniel Berlin]

On Fri, May 8, 2015 at 10:35 AM, Jingyue Wu <jingyue at google.com> wrote:
> Hi Daniel,
>
> I tried your patch. It indeed solves some (but not all) of the issues
> NaryReassociate aims to address. One thing NaryReassociate will work on but
> Reassociate will probably miss is to transform
>
> p = &input[a]
> q = &input[a + b]
>
> to
>
> p = &input[a]
> q = p + b;
>
> I don't see an easy way to merge this into Reassociate unless we peep into
> GEPs. However, that doesn't say I don't like your approach.
>
> That said, I would definitely like to see your patch in, and thanks for
> working on it. Some general comments on the implementation:
>
> 1. Instead of hoisting the rank of last pairing, can we assign them a
> minimum value (e.g. -1)? This allows us to maintain the original sorting
> order (highest first) and at the same time group last paired values.

We can assign the ranks in reverse order :)

>
> 2. LastPairingMap doesn't reflect dominance. If you have
> a+c
> and
> a+b+c
> but a+c doesn't dominate a+b+c, it might not be beneficial to put a and c
> next to each other. I suspect a simple way of making LastPairingMap per-bb
> will work for most cases.

Or we could just store DFS pairs from the domtree and include them in
the sort order.

>
> 3. FYI, Ken Kennedy et al. published a paper
> (http://dl.acm.org/citation.cfm?id=1454120) on a global reassociation
> algorithm, which shares the same spirit as your approach. Instead of
> considering last pairings, their algorithm collects more history and tends
> to group the pairs that appear most frequently. It's much more expensive
> than your approach, so I don't recommend to use their approach yet (unless
> there's enough need). Just let you know some work explored this area.
Interesting.

The approach reassociation uses now is the one Briggs/Cooper came up
with earlier, and has the widely known issues that we've talked about
:)