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

["steven at gcc dot gnu dot org" <gcc-bugzilla at gcc dot gnu dot org>]

------- Comment #9 from steven at gcc dot gnu dot org  2009-02-21 15:25 -------
It looks like this is some kind of quadratic insertion problem, maybe PPRE
after all.  I hacked GCSE a bit to see what is going on.

I fist counted the number basic blocks and edges per function, the number of
expressions considered by PRE, and the block with the largest number of
predecessor edges.  Then, I counted for each partially redundant expression how
many inserts are necessary to make the expression fully redundant. Here are the
numbers of the two largest functions:

counting (nbb = 9189 ; nedges = 15477 ; nexpr = 2417 ; max(preds) = 583)
1164, 1162, 1160, 1158, 1156, 1154, 1152, 1150, 1148, 1146, 

counting (nbb = 5834 ; nedges = 9727 ; nexpr = 1936 ; max(preds) = 489)
976, 974, 972, 970, 968, 966, 964, 962, 960, 958, 

See how there is a series there?

1164 = 2*583 = 2*max(preds) for the first function, and from thereon, we have a
series of n(i+1) = n(i) - 2.  This goes on for a long time (I've only included
the top 10 partially redundant expressions in the above numbers).

Likewise for the second function: 976 = 2*489 etc.

This *is* the same behavior as what we see with PPRE in tree-ssa-pre.c.  But I
don't understand enough of what is going on to be sure that this is PPRE in
gcse.c.


-- 

steven at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |steven at gcc dot gnu dot
                   |                            |org


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=39077