[PR rtl-optimization/39077] [4.3/4.4/4.5/4.6 Regression] GCSE-optimization causes enormous binary size increase (~20 times !)

Richard Guenther richard.guenther@gmail.com
Thu Jan 13 13:54:00 GMT 2011


On Thu, Jan 13, 2011 at 2:36 PM, Jeff Law <law@redhat.com> wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> On 01/13/11 03:45, Richard Guenther wrote:
>> On Thu, Jan 13, 2011 at 5:10 AM, Jeff Law <law@redhat.com> wrote:
>> So the problem here isn't abnormal edges at all (except that they create
>> a large, complex CFG).  Attempts to fix this problem by filtering out
>> expressions on abnormal edges/blocks is ultimately doomed to failure.
>>
>> What we're running into here is expressions which are evaluated on a
>> small number of paths, but which have to be inserted on a huge number of
>> paths to make them fully redundant.
>>
>> I grabbed an expression at random (Index #999 to make it easy to find).
>>  It's computed in a whopping 3 blocks, two of which are partially
>> redundant.  The expression is transparent virtually everywhere (it's
>> just an address computation).   The expression needs to be inserted on >
>> 100 edges to make 2 of the 3 original evaluations fully redundant.
>>
>> I saw that scenario play out over and over and over.  Filtering out
>> based on abnormal edges isn't sufficient as many of the insertions are
>> bubbling up through the CFG via normal edges.
>>
>> The test we need to do is build a ratio of the number of locations where
>> an expression evaluation must be inserted to make a number of original
>> locations fully redundant (and thus removable).
>>
>> This is relatively easy to do after the call to pre_edge_lcm.  That
>> routine gives us a vector of sbitmaps which tell us which expressions
>> need to be inserted on a given edge and the routine gives us a vector of
>> sbitmaps which tell us which blocks have evaluations of the expression
>> which can then be deleted.
>>
>> So, for each expression, we compute how many insertions are required to
>> delete some number of original evaluations.  If that ratio gets big, we
>> remove the insertion & deletion points and go on our merry way.
>>
>> Right now I've set the limit so that if we need more than 20 insertions
>> per deletion then the PRE of that particular expression is cancelled.  I
>> haven't spent any time trying to tune that parameter.  A ratio of 20 is
>> enough to eliminate the huge bloat from PRE (2000% down to 6%).  An
>> interested party could certainly tune this further.
>>
>> It'd be nice if building the counts of insertions/deletions wasn't so
>> cumbersome, but it is what it is.  pre_edge_lcm can't do it any better
>> because it computes the appropriate sbitmaps in parallel.
>>
>> Also note that one could tune this to make PRE -Os safe as well by
>> making this parameter suitably small for -Os.  Extra credit for suitably
>> interested parties.
>>
>> Also note there was a minor buglet where pre_edge_lcm didn't properly
>> initialize its resulting sbitmaps.  The uninitialized entries didn't
>> cause problems until we wanted to iterate over the sbitmap using
>> EXECUTE_IF_SET_IN_SBITMAP.  That bug is fixed by this patch.
>>
>>
>> Bootstrapped and regression tested on x86_64-unknown-linux-gnu. OK for
>> mainline?
>>
>>> I think you could use sbitmap_alloc_with_popcount and at least
>>> sbitmap_popcount for doing the counting of bits.
> I don't think so.  That would count totally the wrong thing.
>
> What we care about is how often a given index/bit is set across all the
> entries in the pre_insert and pre_delete sbitmap vectors.  Doing a
> popcount won't tell us that, it'll tell us how many bits are set in a
> given sbitmap.

Ah, too little coffee for me at the time of review.

So the patch looks ok as-is.

Thanks,
Richard.

> Jeff
>
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.4.11 (GNU/Linux)
> Comment: Using GnuPG with Fedora - http://enigmail.mozdev.org/
>
> iQEcBAEBAgAGBQJNLv/jAAoJEBRtltQi2kC7BPgH/jUxTN466wfsmkgqsXOgDCoO
> pqt8GcEazZXex7eXOK2jyQRjj2Y904u+BdN39UreFd672YEP/NkEmx8OZwmwsW7v
> LPyXoMuJgZGxATUO6t7/+O6XF3e0Aq1GmbNjwE03cO735aaE/LZK5X4uEsgJxUe9
> z9SwD7msCTB17P7Cu/lkXVQv/6qhGlXGPWQWbSxcsWfCJRbMZkMosnDIH6/Jt2Up
> Lm2Nna2Sz/f6w14/LzW4yl5OUi/zPYYKW2/NAPJqRS6IqK1395MTHvnM+H8qltEi
> xkpnd64Q5TAtORYYFqEjsC5HxqoNdL+KmehZcWzEy6kieMp4f1NxuJtyvr3WLKQ=
> =H+JN
> -----END PGP SIGNATURE-----
>



More information about the Gcc-patches mailing list