https://gcc.gnu.org/bugzilla/show_bug.cgi?id=86628
--- Comment #6 from rguenther at suse dot de <rguenther at suse dot de> --- On Mon, 23 Jul 2018, glisse at gcc dot gnu.org wrote: > https://gcc.gnu.org/bugzilla/show_bug.cgi?id=86628 > > --- Comment #5 from Marc Glisse <glisse at gcc dot gnu.org> --- > (In reply to Richard Biener from comment #4) > > Yeah, generally we can't associate because (x*y)*z may not overflow because > > x == 0 but x*(y*z) may because y*z overflows. > > We can do it > > - in the wrapping case (I think you were considering making signed operations > wrap starting from a late reassoc pass) Yes. > - when y*z gets computed anyway (if y*z is computed before x*y*z, value > numbering could help, but otherwise, it is inconvenient, one would either have > to let x*y*z register a trigger (not a true value) for y*z, or make several > passes. It may be easier to walk through the uses of z when we see x*y*z with > a > single-use x*y) > > > I wonder if we have in general ((x*y)*z)*...)*k what it takes to prove > > that it is valid to factor out a random pair (already computed elsewhere). > > I suppose we have to move that factored pair innermost for the case it > > is zero? > > Or outermost for the case something else is 0? It seems hard unless you know > that no variable is 0 or -1 and all the operations are adjacent. The good > thing > is that the frequency of occurrence decreases quickly with the size of the > pattern, so handling the case of size 3 might reap a large part of the > benefits. OK, so one possibility is to do this at VN elimination time when seeing x*c match (a*b)*c and see whether {a,b}*c is available, if so replace x*c accordingly. This might not make the computation of x dead though. Generally reassoc is a global association + CSE problem of course but reassoc is currently formulated as a local problem.
