This is the mail archive of the
gcc-bugs@gcc.gnu.org
mailing list for the GCC project.
[Bug tree-optimization/18595] [4.0 Regression] IV-OPTS is O(N^3)
- From: "sebastian dot pop at cri dot ensmp dot fr" <gcc-bugzilla at gcc dot gnu dot org>
- To: gcc-bugs at gcc dot gnu dot org
- Date: 27 Jan 2005 13:18:43 -0000
- Subject: [Bug tree-optimization/18595] [4.0 Regression] IV-OPTS is O(N^3)
- References: <20041121145949.18595.pinskia@gcc.gnu.org>
- Reply-to: gcc-bugzilla at gcc dot gnu dot org
------- 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