[Bug rtl-optimization/19097] [3.4/4.0/4.1/4.2 regression] Quadratic behavior with many sets for the same register in gcse CPROP

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

------- Comment #33 from steven at gcc dot gnu dot org  2006-01-08 18:32 -------
So where are we wrt. GCC 3.3-hammer at -O2?

compiler     absolute time       relative to 3.3-hammer
GCC 3.3      0m30.390s           1.00
GCC 4.0      0m38.118s           1.25
GCC 4.1      0m51.059s           1.68

Jump bypassing is new in GCC 3.4, that accounts for a 5.47s slowdown.  Without
jump bypassing, GCC 4.0 would be ~7% slower than GCC 3.3.

The time for "tree VRP" in GCC 4.1 is 12.12s.  Together with jump bypassing,
this is a ~18s slowdown for GCC 4.1 wrt. GCC 3.3 just due to new passes. 
Without VRP and jump bypassing, GCC 4.1 would be 11% slower than GCC 3.3.

>From the GCC 4.1 .vrp tree dump: "Number of ASSERT_EXPR expressions inserted:
10000".  This is exactly the number of "else" clauses in the test case.  This
requires a huge effort on update_ssa (which is slow already anyway) to fix up
SSA form for all these pseudo-copies (ASSERT_EXPRs are really just copies). 
The resulting SSA replacement table is therefore also just _huge_ (also from
the .vrp dump):

SSA replacement table
N_i -> { O_1 ... O_j } means that N_i replaces O_1, ..., O_j

b_2 -> { b_1 }
b_3 -> { b_1 }
b_4 -> { b_1 }
b_5 -> { b_1 }
b_6 -> { b_1 }
b_7 -> { b_1 }
b_8 -> { b_1 }
b_9 -> { b_1 }
(etc.)

This is unique behavior that can only be triggered for unreasonable code like
this test case.  Eventually it doesn't help to insert all those ASSERT_EXPRs,
so it would still be nice, perhaps, to fix ASSERT_EXPR insertion to better
understand that it is acting stupidly.


-- 


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