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

[sebastian dot pop at cri dot ensmp dot fr]

------- Comment #56 from sebastian dot pop at cri dot ensmp dot fr  2005-11-03 13:24 -------
Subject: Re:  [4.0/4.1 Regression] IV-OPTS is O(N^3)

> 
> So, I'd suggest that we add a --param here for max-loop-nest-depth, and then
> just not do this stuff on deeper nests, or ignore all the outer loops in that
> case.
> 
> Is that feasible?
> 

Mark, I think that this has already been fixed by the patch that added
PARAM_SCEV_MAX_EXPR_SIZE: we give up when the expressions that we
handle are longer than this size (if I remember correctly this
defaults to 20).  For the example in this bug,

{       int j0, j1, j2, j3, j4, j5, j6, j7, j8, j9, a;
        a = 0;
        for (j0 = 0; j0 < 2; j0 ++)
        for (j1 = j0; j1 < 2; j1 ++)
        for (j2 = j1; j2 < 2; j2 ++)
        for (j3 = j2; j3 < 2; j3 ++)
        for (j4 = j3; j4 < 2; j4 ++)
        for (j5 = j4; j5 < 2; j5 ++)
        for (j6 = j5; j6 < 2; j6 ++)
        for (j7 = j6; j7 < 2; j7 ++)
        for (j8 = j7; j8 < 2; j8 ++)
        for (j9 = j8; j9 < 2; j9 ++)
        a += j0 + j1 + j2 + j3 + j4 + j5 + j6 + j7 + j8 + j9;
        return a;
}

we would have a scev with 10 dimensions, i.e. an evolution in each
dimension, thus an expression with about 10 components.

Some numbers for mainline with -O2 (on amd64 with cpufreq):

time ./gcc/cc1 -O2 ~/ex/pr18595_10.c 
real    0m0.345s
user    0m0.089s
sys     0m0.017s

time ./gcc/cc1 -O2 ~/ex/pr18595_100.c 
 tree PRE              :   0.28 (21%) usr   0.02 (50%) sys   0.29 (20%) wall   
7742 kB (59%) ggc
 tree loop bounds      :   0.14 (10%) usr   0.00 ( 0%) sys   0.15 (10%) wall   
   0 kB ( 0%) ggc
real    0m1.776s
user    0m1.348s
sys     0m0.050s

time ./gcc/cc1 -O2 ~/ex/pr18595_200.c 
 tree PRE              :   1.53 (24%) usr   0.09 (60%) sys   1.63 (25%) wall  
31149 kB (74%) ggc
 tree loop bounds      :   1.21 (19%) usr   0.00 ( 0%) sys   1.21 (18%) wall   
   0 kB ( 0%) ggc
real    0m7.077s
user    0m6.363s
sys     0m0.167s

time ./gcc/cc1 -O2 ~/ex/pr18595_300.c
 tree PRE              :   4.69 (28%) usr   0.21 (68%) sys   5.03 (29%) wall  
69961 kB (80%) ggc
 tree loop bounds      :   4.03 (24%) usr   0.00 ( 0%) sys   4.06 (23%) wall   
   0 kB ( 0%) ggc
real    0m18.126s
user    0m17.022s
sys     0m0.333s

Now, if we remove PRE, we can even compile the case with 1000 nested
loops in a reasonable time:

time ./gcc/cc1 -O2 -fno-tree-pre ~/ex/pr18595_300.c 
 tree loop bounds      :   0.09 ( 4%) usr   0.00 ( 0%) sys   0.24 ( 9%) wall   
   0 kB ( 0%) ggc
real    0m3.184s
user    0m2.147s
sys     0m0.054s

time ./gcc/cc1 -O2 -fno-tree-pre ~/ex/pr18595_1000.c 
 tree loop bounds      :   2.00 ( 8%) usr   0.00 ( 0%) sys   2.00 ( 8%) wall   
   0 kB ( 0%) ggc
real    0m27.171s
user    0m26.298s
sys     0m0.169s

So, I think that we can safely close this PR.

Seb


-- 


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