[Bug fortran/18937] quadratic behaviour with many label "spaghetti" code

[Thomas dot Koenig at online dot de]

------- Additional Comments From Thomas dot Koenig at online dot de  2004-12-11 
10:40 -------
(In reply to comment #1)
> Actually all of the time is spent in the parser so this is not a middle-end
problem.

You're correct.  For example, the C frontend does not exhibit
this behavior:
$ ./spaghetti-c 1000 > sp.c
$ time gcc sp.c

real    0m0.244s
user    0m0.224s
sys     0m0.012s
$ ./spaghetti-c 10000 > sp.c
$ time gcc sp.c

real    0m2.594s
user    0m2.473s
sys     0m0.058s
$ ./spaghetti-c 100000 > sp.c
$ time gcc sp.c

real    0m32.483s
user    0m31.169s
sys     0m0.501s
$ gcc -v
Reading specs from /home/ig25/lib/gcc/i686-pc-linux-gnu/4.0.0/specs
Configured with: ../gcc/configure --prefix=/home/ig25 
--enable-languages=c,c++,f95
Thread model: posix
gcc version 4.0.0 20041208 (experimental)

(also with checks enabled).

$ cat spaghetti-c
#! /usr/bin/perl

$last = shift;

for ($i=1; $i<=$last; $i++) {
    push(@lines, sprintf("l_%d:\n    i++;\n    goto l_%d;\n", $i, $i+1));
}
for ($i=0; $i<=$last; $i++) {
    $j = int(rand($last));
    $temp = $lines[$i];
    $lines[$i] = $lines[$j];
    $lines[$j] = $temp;
}
print <<EOF;
#include <stdio.h>
int main()
{
    int i=0;
    goto l_1;
EOF
print @lines;
printf ("l_%d:\n",$last+1);
print <<EOF
    printf("%d\\n",i);
    return 0;
}
EOF
$ ./spaghetti-c 5
#include <stdio.h>
int main()
{
    int i=0;
    goto l_1;
l_4:
    i++;
    goto l_5;
l_1:
    i++;
    goto l_2;
l_5:
    i++;
    goto l_6;
l_3:
    i++;
    goto l_4;
l_2:
    i++;
    goto l_3;
l_6:
    printf("%d\n",i);
    return 0;
}


-- 


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