[Bug middle-end/18937] New: quadratic behaviour with many label "spaghetti" code

[Thomas dot Koenig at online dot de]

I've written a short script to generate test cases
with many random goto's.

Here it is, with sample output:
$ cat spaghetti
#! /usr/bin/perl

$last = shift;

for ($i=1; $i<=$last; $i++) {
    push(@lines, sprintf("%5d i=i+1\n      goto %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 "      i=0\n";
print "      goto 1\n";
print @lines;
printf "%5d continue\n",$last+1;
print  "      print *,i\n";
print  "      end\n";
$ ./spaghetti 10
      i=0
      goto 1
    6 i=i+1
      goto 7
    1 i=i+1
      goto 2
    8 i=i+1
      goto 9
    3 i=i+1
      goto 4
    7 i=i+1
      goto 8
    2 i=i+1
      goto 3
    9 i=i+1
      goto 10
   10 i=i+1
      goto 11
    5 i=i+1
      goto 6
    4 i=i+1
      goto 5
   11 continue
      print *,i
      end


Compiling this with gfortran yielded compilation times which were pretty
long for large numbers of labels and which were quadratic:

$ ./spaghetti 10000 > spaghetti.f
$ time gfortran -O3 spaghetti.f

real    0m27.876s
user    0m27.827s
sys     0m0.041s
$ ./spaghetti 20000 > spaghetti.f
$ time gfortran -O3 spaghetti.f

real    1m51.228s
user    1m51.022s
sys     0m0.089s
$ ./spaghetti 40000 > spaghetti.f
$ time gfortran -O3 spaghetti.f

real    7m18.125s
user    7m16.173s
sys     0m0.215s

This is on an Atholon 2600+.

The quality of the resulting code is excellent, BTW - the additions
are reduced to a single assignment with -O3.

$ gfortran -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)

-- 
           Summary: quadratic behaviour with many label "spaghetti" code
           Product: gcc
           Version: 4.0.0
            Status: UNCONFIRMED
          Severity: enhancement
          Priority: P2
         Component: middle-end
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: Thomas dot Koenig at online dot de
                CC: gcc-bugs at gcc dot gnu dot org


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