[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