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