[Bug tree-optimization/86628] Missed simplification of division
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=86628 Andrew Pinski changed: What|Removed |Added Severity|normal |enhancement Last reconfirmed|2018-07-23 00:00:00 |2021-12-12 --- Comment #7 from Andrew Pinski --- Note -fwrapv is able to detect the multiply because we can association when dealing with wrapping case.
[Bug tree-optimization/86628] Missed simplification of division
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=86628
--- Comment #6 from 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 ---
> (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.
[Bug tree-optimization/86628] Missed simplification of division
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=86628 --- Comment #5 from Marc Glisse --- (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) - 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.
[Bug tree-optimization/86628] Missed simplification of division
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=86628 Richard Biener changed: What|Removed |Added Status|UNCONFIRMED |NEW Last reconfirmed||2018-07-23 CC||rguenth at gcc dot gnu.org Ever confirmed|0 |1 --- Comment #4 from Richard Biener --- (In reply to Marc Glisse from comment #3) > We already simplify some simple cases like x*t/t -> x in match.pd. Larger > cases are for a pass like reassoc. In this particular case, we could also > imagine somehow noticing that (x*y)*z is better reassociated as x*(y*z) > because y*z is already computed. 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. 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? Note the reassoc pass doesn't handle TYPE_OVERFLOW_UNDEFINED types at all at the moment. > A later pass would then cleanup x*t/t. > Simplifying the unsigned case looks wrong to me.
[Bug tree-optimization/86628] Missed simplification of division
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=86628 --- Comment #3 from Marc Glisse --- We already simplify some simple cases like x*t/t -> x in match.pd. Larger cases are for a pass like reassoc. In this particular case, we could also imagine somehow noticing that (x*y)*z is better reassociated as x*(y*z) because y*z is already computed. A later pass would then cleanup x*t/t. Simplifying the unsigned case looks wrong to me.
[Bug tree-optimization/86628] Missed simplification of division
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=86628 --- Comment #2 from Dávid Bolvanský --- Something/0 is undefined behaviour
[Bug tree-optimization/86628] Missed simplification of division
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=86628 Andrew Pinski changed: What|Removed |Added Keywords||missed-optimization Component|c |tree-optimization Version|tree-ssa|8.1.0 --- Comment #1 from Andrew Pinski --- For the second case, what happens if z is 0?
