------- Comment #7 from law at redhat dot com 2005-11-03 01:35 -------
Subject: Re: [4.1 Regression] jump threading
causing excessive code duplication
On Mon, 2005-10-31 at 18:56 -0700, Jeffrey A Law wrote:
> On Mon, 2005-10-31 at 03:43 +0000, mmitchel at gcc dot gnu dot org
> wrote:
> >
> > ------- Comment #5 from mmitchel at gcc dot gnu dot org 2005-10-31 03:43
> > -------
> > Downgraded to P2. Important, but not a showstopper. We really should have
> > some kind of throttle, even if it's a bit simplistic.
> We could easily put in a trivial throttle. If there's more than N
> statements + phis, then the block is considered not threadable. Choose
> N and it'll take about 5 minutes of work (and 3 hours to test :-)
>
> I'll throw out 50 as a very very very conservative number. If we're OK
> with that number, then let's do it.
>
> We might be better around 10, but 50 ought to catch the pathological
> cases without impacting much of anything.
FWIW with a nice blob of .i files I measured how many real phis + real
statements appeared in blocks we are able to thread through.
Ultimately we threaded 28911 incoming edges for my little test bucket.
Results:
Phis+stmts Threaded Edges Cumulative Percentage
1 5955 5955 20.6%
2 15706 21661 74.9%
3 3787 25448 88.0%
4 1396 26844 92.9%
5 795 27639 95.6%
6 331 27970 96.7%
7 236 28206 97.6%
8 132 28338 98.0%
9 114 28452 98.4%
10 60 28512 98.6%
11 68 28580 98.9%
12 17 28597 98.9%
13 91 28688 99.2%
14 11 28699 99.3%
15 23 28722 99.3%
16 17 28739 99.4%
17 16 28755 99.5%
18 44 28799 99.6%
19 9 28808 99.6%
20 2 28810 99.7%
21 2 28812 99.7%
22 93 28905 99.98%
27 2 28907 99.99%
61 4 28911 100%
Note that at least some of the PHIs are either dead or will
disappear due to copy propagation& coalescing. Some of the
statements are also going to be dead, in fact, these numbers
include the control statement at the end of the block which
we already know is going to disappear :-) So IMHO these are
conservative numbers.
[ Even more so since only one copy is made if multiple
incoming edges thread to the same outgoing edge. ]
We can see that the vast majority of blocks of interest
have a small number of statements (again remembering that
one or more will ultimately disappear as they are dead).
In fact, if we were to put the limit at 15 phis+statements,
then we would still pick up over 99% of the jump threading
opportunities for this little test bucket.
Unless there is some objection, I'm planning to put in a
limit of 15 phis+statements in the target block for jump
threading. That should be enough for us to defer this PR
to 4.2..
jeff
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=21883
