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

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

On Wed, 2005-02-09 at 12:23 -0500, Kazu Hirata wrote:
> Hi Jeff,
> 
> > > 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?)
> 
> Thanks.  Yes, PR 19794 is the meta-bug for missed jump threading
> opportunities.
OK.  I'll tack it onto 19794 tomorrow (I'll be out of the office most of
today).

> 
> >   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.
> 
> What criteria do you use for jump threading?  If we duplicate a big
> basic block, we might end up increasing code size.  Or maybe I should
> wait until I see your patch. :-)
There's currently no limitation on the size of the duplicated block,
though that could be trivially added.

The way I would approach this would be for DOM to go ahead and record
the fact that it could thread through the block.  tree-ssa-threadupdate
would have the task of examining the set of requested jump threads and
determining if it was profitable.

This roughly mirrors how we handle threading through blocks which are
the targets of backedges in the CFG.  We let DOM go ahead and record
the jump thread request, then tree-ssa-threadupdate.c prunes out jump
threading requests which will create irreducible regions.


> > Oh yea, we're able to thread something like 40% more jumps statically, I
> > haven't measured dynamic jump counts yet.
> 
> What do you mean by static and dynamic here?  Do you find 40% more
> jumps in the first iteration of DOM?
Static counts are gathered by instrumenting DOM to record how many times
it is able to thread a jump.  I run a bunch of files through the
compiler, once with the old jump thread selection code, then again with
the new selection code.    Viola, static jump threading counts.


A dynamic count of jumps threaded can be determined by using
-fprofile-arcs and some post-processing of the profiling information.

-fprofile-arcs (for our purposes) basically gives us runtime conditional
branching behavior for a program.  ie, for each conditional branch
in the program it records how many times the branch was taken and
how many times it was not taken at (that's an over simplification, but
is sufficient for our purposes).

So, we can compile some code using -fprofile-arcs with the original
compiler.  Then we run the resulting executable to get our branch
profiling data.  We can then do some post-processing on it to get
the branching behavior for that program in a nice usable form
(basically the total number of conditional branches executed).

We then repeat the process, but using the compiler with the new
jump thread selection code.

We can then compare the total number of executed conditional
branches from the profiling data.


Jeff