On Wed, Jun 15, 2011 at 9:26 PM, 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? >
This caused: http://gcc.gnu.org/bugzilla/show_bug.cgi?id=49465 -- H.J.
