Improve jump threading #5 of N

[Richard Guenther]

On Thu, Jun 16, 2011 at 6:26 AM, Jeff Law <law@redhat.com> wrote:
> -----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?

Ok.

Thanks,
Richard.

>
>
>
>
>
> -----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-----
>