This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.
Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
---|---|---|
Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |
Other format: | [Raw text] |
-----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
Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
---|---|---|
Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |