> 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>
My 5 cent, since i've been recently working on instcombine a bit. First of all, I do acknowledge and recognize the problem at hand - the IR is not getting fully optimized. I think that should be solved. As it is evident, LLVM is quite modular, there are separate passes. This is good. It allows to test things separately. Unfortunately, that is also bad, because there are always these things that fall through the cracks between passes... instcombine is rather huge as is. Almost "all size fits all". It tries to do everything. Sometimes it does wonders, sometimes not. It is not modular. The order of folds is completely hardcoded, not documented, with no obvious logic to it. And only the full and final IR produced by the whole pass is testable. Personally, i think this is bad. I'd prefer something else, like having *separate* folds within instcombine, each tested on it's own, (much like clang-tidy checks vs monolithic clang diagnostics) and then somehow combined, not unlike the usual optimization pipelines. The second problem is the size/complexity of the instcombine pass. I do acknowledge that D46336 / D46595 (both in instcombine) is an improvement, which results in more folds that didn't happen before. But it makes the already-large inscombine even more complex, and i'm not sure how it affects the performance. Then there is D45842. That code is pretty simple, and takes ~one page. It does not do any change unless that opens the road for further simplification. (I hope that is what the D46336 / D46595 do, but i don't know.) As stated in https://reviews.llvm.org/D46336#1090588, the D45842 does allow instcombine to do //most// of the folds that would D46336 do. But there is an open problem - several consecutive runs of instcombine and reassociate passes are needed. So basically we'd need to have a umbrella-pass which would run -instcombine -reassociate until they stop making changes. TLDR: monolithic code is bad. instcombine is monolithic, bloated. The problem at hand can be solved by a separate pass, which would reduce(*) the size of instcombine, provided there is a way to have such an umbrella-pass to combine them. * I do think that we should not only not do that instcombine, but check what else is solved by the separate reassociate pass (not talking about commutative matchers here), and consider removing that. Roman. On Wed, May 9, 2018 at 6:22 AM, Chris Lattner via llvm-dev <llvm-dev at lists.llvm.org> wrote:> > > 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 > > > > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev >
When you say that distribution shouldn't be used, do you mean within instcombine rather than some other pass? Or not all as an IR optimization? A dedicated optimization pass that looks for and makes factoring/distribution folds to eliminate instructions seems like it would solve the problems that I'm seeing. Ie, I'm leaning towards the proposal here: https://reviews.llvm.org/D41574 But I'd make it less "weak". :) Ideally, that allows removing duplicate functionality from instcombine, but I'm guessing that it will take a lot of work to cut that cord without causing regressions. Note that instcombine even has a specialized reassociation pass-within-a-pass for fadd/fsub alone: https://reviews.llvm.org/rL170471 On Tue, May 8, 2018 at 9:22 PM, Chris Lattner <clattner at nondot.org> wrote:> > > 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/20180509/1a60bbf7/attachment.html>
> > > As stated in https://reviews.llvm.org/D46336#1090588, the D45842 > does allow instcombine to do //most// of the folds that would D46336 do. >The (large) 4th test output differs this way: https://reviews.llvm.org/D46336#1093161 It may be due to the same underlying issue with the first test. -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20180509/4705364f/attachment.html>
Here are my thoughts on the issue at hand: As far as I understand the current reassociate pass is a rather niche pass, not intended for extensive use. It also has quite a few weaknesses, the most prominent one is its aggressive re-arrangement of the topology of the associative operator tree into "linear tree", e.g. for addition you’ll get a_0 + (a_1 + (a_2 + ... (a_n-1 + a_n))...) regardless of the topology you started with. Due to that, and because reassociations of all kinds and types are sometimes a key component of a transformation (which is either missing from an InstCombine transformation or unnaturally added to it), these reassociations, as of today, don’t have a “home”. For example, when I suggested https://reviews.llvm.org/D41574, the “Weak reassociation pass”, it was to complement a transformation I’m adding to InstCombine – My transformation involved a reassociation of the form (a_0 + a_1) + (a_2 + a_3) -> (a_0 + a_2) + (a_1 + a_3) which can’t be expressed in the existing reassociate pass, so I had to write a new pass. That is, amongst the rest, why It’s called “weak” - it doesn’t change the topology of the associative operator tree. I believe that a new reassociation pass that will complement InstCombine and will run with it under a “parent” pass is the way to go. However, there is clearly much work involved in such a process. Omer From: Sanjay Patel [mailto:spatel at rotateright.com] Sent: Wednesday, May 09, 2018 16:09 To: Chris Lattner <clattner at nondot.org> Cc: Daniel Berlin <dberlin at dberlin.org>; llvm-dev <llvm-dev at lists.llvm.org>; Paparo Bivas, Omer <omer.paparo.bivas at intel.com> Subject: Re: [llvm-dev] more reassociation in IR When you say that distribution shouldn't be used, do you mean within instcombine rather than some other pass? Or not all as an IR optimization? A dedicated optimization pass that looks for and makes factoring/distribution folds to eliminate instructions seems like it would solve the problems that I'm seeing. Ie, I'm leaning towards the proposal here: https://reviews.llvm.org/D41574 But I'd make it less "weak". :) Ideally, that allows removing duplicate functionality from instcombine, but I'm guessing that it will take a lot of work to cut that cord without causing regressions. Note that instcombine even has a specialized reassociation pass-within-a-pass for fadd/fsub alone: https://reviews.llvm.org/rL170471 On Tue, May 8, 2018 at 9:22 PM, Chris Lattner <clattner at nondot.org<mailto:clattner at nondot.org>> wrote: On May 8, 2018, at 9:50 AM, Daniel Berlin via llvm-dev <llvm-dev at lists.llvm.org<mailto: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<mailto:llvm-dev at lists.llvm.org> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev --------------------------------------------------------------------- Intel Israel (74) Limited This e-mail and any attachments may contain confidential material for the sole use of the intended recipient(s). Any review or distribution by others is strictly prohibited. If you are not the intended recipient, please contact the sender and delete all copies. -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20180510/aa62e0a2/attachment.html>