From: Richard Guenther <richard.guenther@gmail.com>
To: Jeff Law <law@redhat.com>
Cc: gcc-patches <gcc-patches@gcc.gnu.org>
Subject: Re: Improve jump threading #5 of N
Date: Thu, 16 Jun 2011 07:57:00 -0000 [thread overview]
Message-ID: <BANLkTin1b3yNMeveJqr9yJerth2Jz0EMSQ@mail.gmail.com> (raw)
In-Reply-To: <4DF985ED.30406@redhat.com>
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-----
>
next prev parent reply other threads:[~2011-06-16 7:45 UTC|newest]
Thread overview: 5+ messages / expand[flat|nested] mbox.gz Atom feed top
2011-06-16 5:49 Jeff Law
2011-06-16 7:57 ` Richard Guenther [this message]
2011-06-19 7:30 ` H.J. Lu
2011-06-22 4:19 ` Hans-Peter Nilsson
2011-06-22 14:13 ` Jeff Law
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=BANLkTin1b3yNMeveJqr9yJerth2Jz0EMSQ@mail.gmail.com \
--to=richard.guenther@gmail.com \
--cc=gcc-patches@gcc.gnu.org \
--cc=law@redhat.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).