[llvm-dev] more reassociation in IR

[Hiroshi Yamauchi via llvm-dev]

On Tue, May 8, 2018 at 11:15 AM Daniel Berlin <dberlin at dberlin.org> wrote:

>
>
> On Tue, May 8, 2018 at 10:38 AM, Hiroshi Yamauchi via llvm-dev <
> llvm-dev at lists.llvm.org> wrote:
>
>> (
>> ​I came across this issue in the context of
>>  D46336 <https://reviews.llvm.org/D46336>.
>> ​ ​
>> Thanks, Sanjay, for starting this discussion.)
>>
>> If
>> ​we will
>>  move
>> ​reassociation,
>> or keep additional ones
>> ​,​
>> out of instcombine,
>> ​open questions for me would be
>> ​​:
>>
>>
>> 1. Since -reassociate isn't a fixed point pass,
>>
>
> This is fixable, fwiw, without fixpointing it.
>

How?


>
>> we might need to repeat "-instcombine -reassociate" multiple times to
>> ​fold
>>  down to what we want (relating to my comment here
>> <https://reviews.llvm.org/D46336#1087082>). I assumed this isn't not
>> what we want to do
>> ​? My impression is we don't do a fixed-point with passes?
>>
>
> Well, i mean there is no practical difference between passes that we
> fixpoint externally and fixpoint internally.
>
​​
I had the following in mind: Does the pass manager support fixpointing
externally? Is there any performance difference? Are people okay with that
in general?

But if there is no practical difference, I don't see any problem with that
:)


>
>>
>>
> 2.
>> ​Since -reassociate needs to come up with one operand order (at least
>> currently as the only reassociate pass), would there exist a single,
>> unique operand order that would enable all reassociative/commutative
>> foldings that we want?
>>
>
> In what way?
> Are you asking whether there is a single reassociation order that makes
> all foldings occur in the same operation or something?
> I don't feel like i understand what you are asking.
>

Does this rephrase help: with the motivating examples (like and-of-shifts
or bit check patterns) from the above differentials in mind, can we come up
with a single reassociation order that solves all those and all the others
that may come up in the future? Would we need different reassociation
orders to fold different patterns?


>
>
>> If not, could there be conflicts among different reassociation orders
>> depending on what folding we want?
>>
>
> We actually do try to have a single canonical form at various points in
> the compiler.
>
> We may want to canonicalize differently in different parts of the
> compiler, but it would be nice to at least be self consistent.
>
>>
>>
>> On Tue, May 8, 2018 at 9:19 AM Sanjay Patel <spatel at rotateright.com>
>> wrote:
>>
>>> There are at least 3 active proposals to add reassociative optimizations
>>> in IR:
>>> [1] D41574 <https://reviews.llvm.org/D41574>- a new pass for
>>> reassociation/factoring
>>> [2] D46336 <https://reviews.llvm.org/D46336> - enhance -instcombine to
>>> do more reassociation/factoring
>>> [3] D45842 <https://reviews.llvm.org/D45842> - add to the existing
>>> -reassociate pass to enable factoring
>>>
>>> Here's a basic motivating example that we fail to optimize:
>>> https://godbolt.org/g/64NmJM
>>> https://rise4fun.com/Alive/wec
>>>
>>> Currently, responsibility for reassociative transforms is split between
>>> -reassociate and -instcombine. I don't know if that split is intentional or
>>> just how the code evolved. Debug stats for test-suite compiled with -O3
>>> show:
>>> 78K "reassociations" by -instcombine.
>>> 58K "reassociated" by -reassociate
>>>
>>> A debug stat with D45842 showed that that transform fired 1.3K times.
>>>
>>> Keep in mind that instcombine runs 1st, runs to fixed-point, and runs 8
>>> times in the -O2 pipeline. Reassociate runs 1 time and doesn't run to
>>> fixed-point. Some transforms are unique to 1 pass or the other, but there
>>> is some overlapping functionality already there.
>>>
>>> So the questions are:
>>> 1. How do we solve these remaining reassociation optimizations?
>>> 2. Do we want to consolidate existing reassociation transforms in 1 pass
>>> or is there value in splitting the folds across multiple passes?
>>>
>>>
>>>
>>>
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org
>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20180509/e8646ee2/attachment-0001.html>