query regarding iterating DOM on jump threading oppurtunities

[Jeff Law]

Ramana Radhakrishnan wrote:
> Hi Jeffrey,
>
> I'm seeing a few performance regressions similar to
> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=32306 and
> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=33315 in a port where I'm
> working off the 4.3 branch. These regressions are caused by the
> decision to stop iterating DOM on identifying jump threading
> oppurtunities and splitting up VRP into a separate pass based on your
> patch at http://gcc.gnu.org/ml/gcc-patches/2006-02/msg00586.html and
> as described by Richard here
> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=32306#c7.
>
> I'm going to try a quick experiment by re-running DOM if jump
> threading is turned on in the 4.3 branch. I know there are a number of
> changes I need to do and I'm looking into them. I wanted to check back
> if you still had any record of the small number of performance
> regressions that you mention in the posting of the afore mentioned
> patch.
>   
I didn't keep a record of things we missed due to removal of the 
iteration step.  My experience was that they were relatively rare and 
the cost to pick them up was fairly high, so the decision was made to 
remove the iteration step.  So while there are some codes where we miss 
threading opportunities, it's my belief that we're on the right side of 
the cost/benefit curve.

I've postulated in the past that I believe the iteration step could be 
faster by moving to a worklist based algorithm for DOM -- the theory 
being that the cascading optimization opportunities exposed by jump 
threading are actually rather limited both in terms of paths that need 
revisiting and in how newly exposed equivalences can be utilized.   I 
was never able to convince myself that the scheme would work though and 
thus I never wrote code to try it.

There was also a master's thesis which touched on these issues and 
approached path specific optimizations with a PRE-like framework.  I 
could probably dig this up if you wanted to look at it -- the overall 
approach seemed based on fairly solid fundamentals as opposed to the 
ad-hoc threading+DOM stuff we're using.


I would welcome investigations into solving some of these problems and I 
would certainly encourage you to submit testcases for the testsuite 
which test for the missed optimizations.

Jeff