http://gcc.gnu.org/bugzilla/show_bug.cgi?id=54896
--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> 2012-10-11 14:08:16 UTC --- (In reply to comment #3) > Thanks for the test case! > > Bug is confirmed with GCC 4.8 (trunk revision 192219). > > Problem areas at -O1: > alias stmt walking : 31.68 (36%) usr > tree DSE : 10.83 (12%) usr > CSE : 9.02 (10%) usr > reload CSE regs : 23.17 (26%) usr > TOTAL : 87.99 > > Problem areas at -O2 are pretty much the same: > alias stmt walking : 47.29 (28%) usr > tree DSE : 10.84 ( 7%) usr > CSE : 9.12 ( 5%) usr > CSE 2 : 34.66 (21%) usr > reload CSE regs : 45.37 (27%) usr > TOTAL : 166.12 > > > GCC 4.3.2 has the same problems at the RTL level: > tree DSE : 11.60 (17%) usr > CSE : 19.74 (28%) usr > CSE 2 : 12.63 (18%) usr > reload CSE regs : 8.49 (12%) usr > TOTAL : 69.68 > > > tree-DSE, CSE and reload-CSE are both quadratic in the number of > instructions per basic block, and all basic blocks in this test > case contain O(10^3) instructions. tree-DSE isn't quadratic but linear in the number of instructions (again with a high factor, up to 256, without a --param). > The alias stmt walking slowness is a regression, but I suspect > there a dup that Rick Biener already knows about... There are (for 4.8) limits in place everywhere to make alias-stmt walking O(1) (well, with a high constant overhead ;)). My numbers for 4.7 are, at -O2 alias stmt walking : 13.55 (19%) usr tree DSE : 2.60 ( 4%) usr CSE : 8.79 (13%) usr CSE 2 : 17.52 (25%) usr reload CSE regs : 21.23 (30%) usr with -m32 reload CSE regs is even worse.
