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? -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20180508/62b66114/attachment.html>
1. The reassociate pass that exists right now was *originally* (AFAIK) written to enable CSE/GVN to do better. That particular issue is solvable in other ways, because there are good ways to integrate reassociation into CSE/GVN (and at this point, it would probably be cheaper than -reassociate since it would modify code less, only changing it when there are actual redundancies ) I don't know what other things people are trying to target with reassociate these days, it would be good to understand what others see as the use cases. My only other fear with removing it is that we have a tendency to try to make every optimization do everything, so i fear removing reassociate might just have people try to improve every pass to do reassociation instead of declaring what is good enough. (For example, GVN already does some reassociation, as do some analysis. Other analysis relies more on a canonical form existing and don't, for example, try to perform commutativity on their own. IMHO, we should just declare one or the other to be the case, and hold that line, rather than generate a mishmash) 2. "Keep in mind that instcombine runs 1st, runs to fixed-point, and runs 8 times in the -O2 pipeline." Y'all know how i feel about this one, so i'll leave it alone :) --Dan -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20180508/271c6189/attachment-0001.html>
( 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, 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? 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? If not, could there be conflicts among different reassociation orders depending on what folding we want? 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? > > > >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20180508/c4948961/attachment.html>
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.> 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.> >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.> 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/20180508/f9ae6ca9/attachment.html>
> On May 8, 2018, at 9:50 AM, Daniel Berlin via llvm-dev <llvm-dev at lists.llvm.org> wrote: > > 1. The reassociate pass that exists right now was *originally* (AFAIK) written to enable CSE/GVN to do better.Agreed. The original mindset included a (naive) belief that going with a canonical form was better than teaching redundancy elimination to handle abstractions (as a matter of separation of concerns). I think that that was a failed experiment at this point :-). We should still canonicalize x*x*x into powi, but the more aggressive canonicalization (like distribution) shouldn’t be used IMO. -Chris> That particular issue is solvable in other ways, because there are good ways to integrate reassociation into CSE/GVN (and at this point, it would probably be cheaper than -reassociate since it would modify code less, only changing it when there are actual redundancies ) > > I don't know what other things people are trying to target with reassociate these days, it would be good to understand what others see as the use cases. > > My only other fear with removing it is that we have a tendency to try to make every optimization do everything, so i fear removing reassociate might just have people try to improve every pass to do reassociation instead of declaring what is good enough. > > (For example, GVN already does some reassociation, as do some analysis. Other analysis relies more on a canonical form existing and don't, for example, try to perform commutativity on their own. IMHO, we should just declare one or the other to be the case, and hold that line, rather than generate a mishmash) > > > 2. "Keep in mind that instcombine runs 1st, runs to fixed-point, and runs 8 times in the -O2 pipeline." > > Y'all know how i feel about this one, so i'll leave it alone :) > > > > --Dan > _______________________________________________ > 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/20180508/ec320421/attachment.html>