Re: [RFC] Catch 11.8% more jump threading opportunities at treelevel.

[Jeffrey A Law <law at redhat dot com>]

On Tue, 2005-02-08 at 17:48 -0500, Kazu Hirata wrote:
> Hi Jeff,
> 
> > I have changed queued for 4.1 which revamp the thread selection code
> > which are far more effective than what you have posted.
> 
> Wow.  Is there any way I could take a peek at it?
Certainly.  What would probably work best is to attach it to the
meta-bug we are using to track 4.1 and/or missed jump threading
issues. (do you have either of those meta-bug id#s handy?)

There's basically two changes:


  1. Change the jump thread selection code to allow threading through
     blocks with side effects that need to be preserved.  This actually
     simplifies the jump thread selection code and other parts of DOM
     as it no longer needs to track the current definition of variables
     anymore.

  2. Change the thread update code to avoid creating irreducible
     regions.  The improved jump threading we get from #1 was creating
     more irreducible regions -- enough that it was starting to become
     a problem.

[ Note that as expected the thread updating code did not need to be
  changed to handle threading through blocks with side effects :-) ]

>From a correctness standpoint, I'm pretty happy with the code.  There's
some interactions between the thread update code and DOM that need some
cleanup (the thread update code needs to cleanly signal to DOM that we
need to rediscover loops and back edges in the CFG).

There's a small compile-time hit that I'm still sorting through.  Things
that work to our advantage from a compile-time standpoint:

  1. We find jump threading opportunities much earlier and thus may
     actually need fewer iteration steps inside DOM.

  2. We no longer need to track currdef in DOM :-)

Working against us:

  1. We find threading opportunities that we missed before, which
     sometimes causes DOM to iterate when it did not do so previously.

  2. We're doing more operand twiddling in the jump thread selection
     code.

  3. Sometimes we find a jump threading opportunity later because
     we have more accurate loop information in DOM (which can suppress
     copy propagation in some cases).   This can cause DOM to
     iterate in a later pass when previously the jump thread was handled
     with other jump threading opportunities in earlier passes.


Oh yea, we're able to thread something like 40% more jumps statically, I
haven't measured dynamic jump counts yet.

jeff