similar to: [LLVMdev] Reassociate and Canonicalization of Expressions

>> On Feb 2, 2015, at 11:12 AM, Mehdi Amini <mehdi.amini at apple.com> wrote: >> >> Hi, >> >> I encountered some bugs in Reassociate [1] where we are hitting some >> assertions: >> >> assert(!Duplicates.count(Factor) && >> "Shouldn't have two constant factors, missed a >> canonicalize");

> Hi Chad, > > Thanks for you answer. > >> On Feb 4, 2015, at 11:22 AM, Chad Rosier <mcrosier at codeaurora.org> >> wrote: >> >>>> On Feb 2, 2015, at 11:12 AM, Mehdi Amini <mehdi.amini at apple.com> >>>> wrote: >>>> >>>> Hi, >>>> >>>> I encountered some bugs in Reassociate [1] where we

On Apr 23, 2013, at 10:37 AM, Shuxin Yang <shuxin.llvm at gmail.com> wrote: > As far as I can understand of the code, the Reassociate tries to achieve this result by its "ranking" mechanism. > > If it dose not, it is not hard to achieve this result, just restructure the expression in a way such that > the earlier definition of the sub-expression is permute earlier in

Owen/All, I've been working on adding support for reassociation with unsafe math (see: http://reviews.llvm.org/D4129). Do you know if this change, r156323, is still necessary? Specifically, do we need the reassociation pass to canonicalize FP operands for CSE to work effectively? This kinda scares me if it does! :( Side note: Without this canonicalization, I did see a 3% regression in Mesa

When playing around with reassociate I noticed a seemingly obvious optimization that was not getting done anywhere in llvm… nor in gcc or ICC. Consider the following trivial function: void foo(int a, int b, int c, int d, int e, int *res) { res[0] = (e * a) * d; res[1] = (e * b) * d; res[2] = (e * c) * d; } This function can be optimized down to 4 multiplies instead of 6 by reassociating

On Tue, May 5, 2015 at 10:20 AM, Jingyue Wu <jingyue at google.com> wrote: > Hi Daniel, > > I presume you mean, instead of assigning function arguments distinct ranks > (http://llvm.org/docs/doxygen/html/Reassociate_8cpp_source.html#l00282), we > should group function arguments in favor of existing pairings. Existing = pairings reassociate already chose before *not* existing

As far as I can understand of the code, the Reassociate tries to achieve this result by its "ranking" mechanism. If it dose not, it is not hard to achieve this result, just restructure the expression in a way such that the earlier definition of the sub-expression is permute earlier in the resulting expr. e.g. outer-loop1 x= outer-loop2 y =

On Apr 25, 2013, at 10:51 AM, Preston Briggs <preston.briggs at gmail.com> wrote: > It's an interesting problem. > The best stuff I've seen published is by Cooper, Eckhart, & Kennedy, in PACT '08. > Cooper gives a nice intro in one of his lectures: http://www.cs.rice.edu/~keith/512/2012/Lectures/26ReassocII-1up.pdf > I can't tell, quickly, what's going on

It's an interesting problem. The best stuff I've seen published is by Cooper, Eckhart, & Kennedy, in PACT '08. Cooper gives a nice intro in one of his lectures: http://www.cs.rice.edu/~keith/512/2012/Lectures/26ReassocII-1up.pdf I can't tell, quickly, what's going on in Reassociate; as usual, the documentation resolutely avoids giving any credit for the ideas. Why is that?

On Fri, 20 Apr 2007, Dan Gohman wrote: > The SCEV framework sorts operands of commutative SCEVs by their > getSCEVType() value, and then does an ad-hoc sort to group repeated > operands, but it does not do a full sort. In some test cases I'm > looking at right now, this causes it to miss opportunities to reuse > SCEV objects, as in cases like this: > > ( %i + %r54 +

> 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

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

Hi, I am investigating a performance degradation between llvm-3.1 and llvm-3.2 (Note: current top-of-tree shows a similar degradation) One issue I see is the following: - 'loop invariant code motion' seems to be depending on the result of the 'reassociate expression' pass: In the samples below I observer the following behavior: Both start with the same expression: %add = add

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

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

The SCEV framework sorts operands of commutative SCEVs by their getSCEVType() value, and then does an ad-hoc sort to group repeated operands, but it does not do a full sort. In some test cases I'm looking at right now, this causes it to miss opportunities to reuse SCEV objects, as in cases like this: ( %i + %r54 + %r59) ( %r54 + %r59 + %i) As a result, passes like LoopStrengthReduce

( ​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

Hi Daniel, I presume you mean, instead of assigning function arguments distinct ranks ( http://llvm.org/docs/doxygen/html/Reassociate_8cpp_source.html#l00282), we should group function arguments in favor of existing pairings. You are not suggesting discarding the entire ranking system, right? I'll look into how that works on my benchmarks. AFAIK, we encountered some cases that seem beyond

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. > >

Hi Andrew, Shuxin, Thanks for the explanation about 'Reassociate'. The problem is indeed that one of the variables, becomes loop invariant after some of the loop transformations. > -----Original Message----- > From: Andrew Trick [mailto:atrick at apple.com] [...] > Right. Reassociate ranks expressions by their order in the IR, so shouldn't > make matters worse, but it