[Bug tree-optimization/46590] [4.6/4.7/4.8 Regression] long compile time with -O2 and many loops

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

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

--- Comment #26 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-08-21 14:56:41 UTC ---
For a somewhat reduced testcase I now get at -O1:

 alias stmt walking      : 105.51 (45%) usr   0.33 (24%) sys
 tree SSA rewrite        :  22.01 ( 9%) usr   0.04 ( 3%) sys
 tree SSA incremental    :  25.25 (11%) usr   0.07 ( 5%) sys
 dominance frontiers     :  35.35 (15%) usr   0.02 ( 1%) sys
 dominance computation   :  14.60 ( 6%) usr   0.09 ( 7%) sys
 TOTAL                 : 234.28             1.38

as previously said most of the non-alias-stmt walk time is spent
on loop header copying.  WIth -O1 -fno-tree-ch we have

 alias stmt walking      : 101.52 (68%) usr   0.37 (34%) sys
 tree SSA rewrite        :   4.14 ( 3%) usr   0.01 ( 1%) sys
 tree SSA incremental    :   8.00 ( 5%) usr   0.02 ( 2%) sys
 dominance frontiers     :   6.14 ( 4%) usr   0.01 ( 1%) sys
 dominance computation   :   4.74 ( 3%) usr   0.06 ( 6%) sys
 TOTAL                 : 150.14             1.09

limiting stmt walk results in the ability to arbitrarily scale down its cost
with a param (we can either limit alias oracle query numbers or SCCVN
table lookups).  With 100 alias oracle queries per load/store we end up with

 alias stmt walking      :   1.60 ( 3%) usr   0.05 ( 5%) sys

with 100 SCCVN table lookups the figure is

 alias stmt walking      :   1.60 ( 3%) usr   0.06 ( 6%) sys

one assumes the lookups are expensive, the other one assumes the walk itself
is.
Increasing the latter to 1000 SCCVN table lookup produces

 alias stmt walking      :   9.24 (16%) usr   0.18 (19%) sys

which is around the expected 10-fold increase (but still reasonable given
the artificial nature of the testcase).  We could also, instead of
limiting each walk to a constant cost, have a per-function budget that
we can use up first before limiting further walks individually (helps
to not regress reasonably sized cases).