Re: Improve jump threading #5 of N

["H.J. Lu" <hjl dot tools at gmail dot com>]

On Wed, Jun 15, 2011 at 9:26 PM, 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?
>

This caused:

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=49465

-- 
H.J.