[PATCH]: Rewrite reassociation pass
Jeffrey A Law
law@redhat.com
Fri Dec 9 08:43:00 GMT 2005
On Tue, 2005-12-06 at 22:21 -0500, Daniel Berlin wrote:
> > We can't use this (as-is) to optimize not-not (and neg-neg)
> > expressions that are currently handled by DOM -- unless the
> > not-not feeds into some associative operation. I haven't
> > looked into how difficult it might be to do that.
>
> The problem with extending the code to handle multiple types of ops at
> once is obviously that then you have to pay attention to ordering, etc.
> It's certainly possible, but it's not clear how much of a maintenance
> burden it would be.
Yea, thinking more about it, I don't think handling naked not-not
or neg-neg really belongs in reassociation. It's really just a
matter of following one link in the use-def chains to see if the
current not/neg is defined by a previous not/neg. Nor does that code
really belong in DOM.
> Yes, it can also generate dead code on it's own. In my original tree,
> it ran after split crit edges, before PRE, and then had another DCE
> after it.
Clearly we'd like to avoid having to add another DCE pass :-)
> The most expensive part is computing the post dominators to get the
> ordering right to break up subtracts. If you don't tell it to break up
> subtracts, (or just do it in RPO and hope for the best there) we could
> probably just run it twice without it even showing up in the time
> output.
Note that running another pass just after loop exposed a latent
problem, namely that we don't wipe post-dominator information
consistently. This eventually led to a crash in DCE because
the pdoms where not consistent with the CFG.
One could argue that every time we call free_dominance_info
for dominators that we should do the same for post-doms.
Similarly if we incrementally update the dominators we should
incrementally update the post-dominators (or free them if the
update is going to be hard).
We've always been rather inconsistent in this regard; right now
every pass that uses pdoms calculates & frees them within the
pass, and until we fix all the problems noted above we should
probably do the same thing in reassociation. ie, I don't
necessarily want to hold up the reassociation rewrite and
minor DOM cleanups it allows on revamping our code to handle
doms and pdoms in a consistent manner.
[ Handling them in a consistent manner would be a good thing
as we might get away without rebuilding pdoms so often. Right
now we need them for if-conversion, dce, dse, math-opts, pre
reassociation and sinking. Some of those passes even run
back to back with just a CFG cleanup inbetween.... ]
Jeff
More information about the Gcc-patches
mailing list