On Thu, Jun 16, 2011 at 6:26 AM, Jeff Law <l...@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----- >
