[Bug c/54896] [4.7/4.8 Regression] Some optimization slowness with GCC 4.7.2

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

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.