------- 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