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

[Jeff Law <law at redhat dot com>]

-----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.

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-----