On Tue, May 22, 2012 at 2:50 PM, Ulrich Weigand <uweig...@de.ibm.com> wrote: > Richard Guenther wrote: > >> Btw, reassoc (and your patch?) would have the issue that for >> a + (b + c) - a it would yield b + c as result which is not an atom >> (but still ok, since it is a pre-existing value that is computed in the IL >> already). The simple forwprop matching catches this as it doesn't >> even look into the (b + c) expression but just sees a temporary as >> atom here. > > Yes, that is a problem, and my patch partially solves it by being > very eager in performing optimizations and checking whether we have > found a simplified solution. For example, in your case we'd see > > y = b + c > x = a + y > r = x - a > > and then, when looking at "r": > > - push "x" and "-a" onto the operand stack > - notice no simplification yet > - expand "x" one stage into "a" and "y" > - immediately cancel "a" and "-a" when pushing onto the stack > - notice the stack is now just "y", which represents a simplification > - stop > > This is not a *complete* solution, since by expanding "x" we might > miss solutions we could have seen only when expanding "-a" instead; > we'd really have to search the full solution space or back-track > an already performed expansion. I have not implemented this due > to concerns about combinatorial explosion ... > > > Solving this problem in the context of the existing tree-ssa-reassoc > algorithm is indeed yet another issue that I need to think about.
I suppose we'd have to go the full way making the reassoc intermediate IL a tree and not just a linear list of operands ... which incidentially also would pave the way for supporting multiple operations. Each operation node could then link to a stmt (or have an SSA name) that represents its value as long as we have it. Associating would simply remove that link, forcing a new stmt computation. Re-structuring reassoc that way would also make its IL and optimizations possibly usable by other passes that construct expressions, allowing optimizing them without relying on fold and later gimplification ... Richard. > Bye, > Ulrich > > -- > Dr. Ulrich Weigand > GNU Toolchain for Linux on System z and Cell BE > ulrich.weig...@de.ibm.com >
