[Bug tree-optimization/18595] [4.0 Regression] IV-OPTS is O(N^3)

["belyshev at lubercy dot com" <gcc-bugzilla@gcc.gnu.org>]

------- Additional Comments From belyshev at lubercy dot com  2004-11-25 11:16 -------
use this awk script to generate testcase (first arg is number of loops):
----------------------------------------------------------------------------------------
BEGIN {
	ORS=""
	print "int f ()\n{\tint "
	for (j = 0; j < ARGV [1]; j++)
		print "j" j ", "
	print "a;\n\ta = 0;\n"
	print "\tfor (j0 = 0; j0 < 2; j0 ++)\n"
	for (j = 1; j < ARGV [1]; j++)
		print "\tfor (j" j " = j" j-1 "; j" j " < 2; j" j" ++)\n"
	print "\ta += "
	for (j = 0; j < ARGV [1]-1; j++)
		print "j" j " + "
	print "j" j ";\n\treturn a;\n}\n"
}
----------------------------------------------------------------------------------------

N loops   Time, s
 5        0.05
10        0.17
15        0.38
20        1.14
25        2.81
30        4.68
35        7.52
40        13.6
45        21.8
50        25.6
55        33.9


-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|minor                       |normal
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|                            |1
           Keywords|                            |memory-hog
      Known to fail|                            |4.0.0
   Last reconfirmed|0000-00-00 00:00:00         |2004-11-25 11:16:30
               date|                            |
            Summary|IV-OPTS is slow (and does   |[4.0 Regression] IV-OPTS is
                   |not scale)                  |O(N^3)
   Target Milestone|---                         |4.0.0


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