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

[sebastian dot pop at cri dot ensmp dot fr]

------- Additional Comments From sebastian dot pop at cri dot ensmp dot fr  2005-01-27 13:18 -------
Subject: Re:  [4.0 Regression] IV-OPTS is O(N^3)

With the following patch I got some speedup for depth 100.

from: 
 tree iv optimization  :   2.62 (62%) usr   0.27 (82%) sys   2.92 (62%) wall
 tree iv optimization  :   2.33 (59%) usr   0.25 (83%) sys   2.63 (54%) wall

to:
 tree iv optimization  :   1.19 (46%) usr   0.04 (40%) sys   1.26 (45%) wall
 tree iv optimization  :   1.21 (47%) usr   0.05 (45%) sys   1.30 (46%) wall

Basically we're reseting too much information each time scev_reset is
called.  It would even be possible to reset only the part of the scev
database that contains symbols instead of erasing everything.

Do somebody know how to iterate over all the elements of the hash
setting to NULL_TREE the elements that answer true to
chrec_contains_symbols?

Index: tree-scalar-evolution.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-scalar-evolution.c,v
retrieving revision 2.16
diff -d -u -p -r2.16 tree-scalar-evolution.c
--- tree-scalar-evolution.c	18 Jan 2005 11:36:26 -0000	2.16
+++ tree-scalar-evolution.c	27 Jan 2005 13:12:36 -0000
@@ -2490,7 +2490,7 @@ scev_reset (void)
   for (i = 1; i < current_loops->num; i++)
     {
       loop = current_loops->parray[i];
-      if (loop)
+      if (loop && chrec_contains_symbols (loop->nb_iterations))
 	loop->nb_iterations = NULL_TREE;
     }
 }


-- 


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