Improve jump threading #5 of N

[Jeff Law <law at redhat dot com>]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1




So as I've mentioned previously, I've been working on a relatively small
change to the jump threading code which would allow it to duplicate a
join block when doing so allows us to thread through a successor of the
join block.  This is expected to be the last extension to the existing
jump threading code.

This was mainly done to improve our ability to eliminate unexecutable
paths through the CFG which helps avoid false positives with certain
warnings.  It also has the nice property that it eliminates conditionals
and often results in further optimization of nearby code.

To help evaluate the code generation improvements of this change I built
gcc-4.6 (checking enabled) using a compiler with and without this
improvement.  I then used the 4.6 cc1s to compile a bunch of .i files
under the watchful eye of valgrind.

                        without patch    with patch
Total cbranches          231072754220     229626578262
Total ibranches:	   7687404775       7686994201


cbranches shows the number of dynamically executed conditional branches.
 As you can see, with the patch we eliminated about .625% of the runtime
conditional branches.  Not bad at all.  We eliminated a trivial number
of indirect branches.  In all we eliminated 1446595532 runtime branches.

                        without patch    with patch
Total instructions:     1254106133886    1247718004946


I was expecting a reduction in the total number of instructions
executed, but was quite surprised at the actual data.  We end up
eliminating 6388128940 dynamic instructions --- which means that for
every dynamic branch eliminated, on average we were able to eliminate an
additional 3.4 dynamic instructions -- that's a huge secondary effect.
Clearly improving jump threading in this way is allowing the rest of the
optimizers to do a better job.

Anyway, attached is the patch.  Again, the concept is pretty simple,
when we have a join block which can not be threaded, we peek at the
successors of the join block and see if one or more of them can be threaded.

If so, we make a duplicate of the join block, wire the incoming edge we
were originally trying to thread to reach the duplicate rather than the
original join block.  We then wire the outgoing edge from the duplicate
to the final jump thread target.

So if given a CFG like this (from  a routine in cfgexpand):

           A
          / \
         B   C
         |  / \
         | D   E
         | |  / \
         | | F   G
          \| |
            \|
             H
            / \
           I   J
          / \
         L   M
         |  / \
         | N   O
         | |  / \
         | | P   Q
          \| |
            \|
             R


As it turns out some blocks have the same condition (A,I), (C,M), (E,O).
But because of the merge block H, no threading is possible.  What we
want to do is make 3 copies of H, each reachable from one predecessor of
the original H.  That exposes the jump threading opportunities B->L,
D->N and F->P.  The final CFG looks something like this:

           A
          / \
        BH'L C
         |  / \
         |DH'N E
         | |  / \
         | |FH'P G
          \| |
            \|
             R



Where each H' also has an edge to J from the original CFG, but which is
hard to show here... Note that I, M, O & Q all disappear and each
dynamic path through the cfg is shortened, even though we had to
duplicate H multiple times.

Bootstrapped and regression tested on x86_64-unknown-linux-gnu.

OK for mainline?






-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (GNU/Linux)
Comment: Using GnuPG with Fedora - http://enigmail.mozdev.org/

iQEcBAEBAgAGBQJN+YXtAAoJEBRtltQi2kC7ncwH/2RqgygBPIdholt7jxRH6X1X
7xeBarsQX7SyhO6X1kT7KpWy1tdFElv2UlmqYVKq1Z6U8OZtCwAU3skePk7WcZ/c
gmsUJYLrrDEz93poPgaOnVP62iqa2svFI20xjUDyxN9xf/82Tc6/emV+fmrStxk3
AsgrmfGR31mKtot0HxDFAT14+sqLrrcJ49WFpgfAj1FDLXAajX+q8hAf6cXABHJS
YdFZXeo8NohvYDezLgOhD+YY4/afKzZ3L41ka5gb2fKWrsRwFqCECk7VpbfdDsKc
9EqK+X8Xte/Cy0SmSUQU9/vBoN3Wj0O9kA5Bp3UknbjK9WtrLVKAjjz0b7AaxHg=
=DMtP
-----END PGP SIGNATURE-----

Attachment: patch3
Description: Text document