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

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

[tobi at gcc dot gnu dot org]

------- Comment #7 from tobi at gcc dot gnu dot org  2006-01-09 18:57 -------
Discussion on how to fix this has taken place in PR18540.


-- 

tobi at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |tobi at gcc dot gnu dot org


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

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

[tobi at gcc dot gnu dot org]

-- 

tobi at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |tobi at gcc dot gnu dot org
                   |dot org                     |
             Status|NEW                         |ASSIGNED
   Last reconfirmed|2005-12-30 18:52:55         |2006-01-14 19:03:18
               date|                            |


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

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

[tobi at gcc dot gnu dot org]

------- Comment #8 from tobi at gcc dot gnu dot org  2006-01-18 20:54 -------
Subject: Bug 18937

Author: tobi
Date: Wed Jan 18 20:54:49 2006
New Revision: 109914

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=109914
Log:
PR fortran/18540
PR fortran/18937
* gfortran.h (BBT_HEADER): Move definition up.
(gfc_st_label): Add BBT_HEADER, remove 'prev' and 'next'.
* io.c (format_asterisk): Adapt initializer.
* resolve.c (resolve_branch): Allow FORTRAN 66 cross-block GOTOs
as extension.
* symbol.c (compare_st_labels): New function.
(gfc_free_st_label, free_st_labels, gfc_get_st_label): Convert to
using balanced binary tree.
* decl.c (match_char_length, gfc_match_old_kind_spec): Do away
with 'cnt'.
(warn_unused_label): Adapt to binary tree.
* match.c (gfc_match_small_literal_int): Only set cnt if non-NULL.
* primary.c (match_kind_param): Do away with cnt.

Also converted the ChangeLog to use latin1 characters.

Modified:
    trunk/gcc/fortran/ChangeLog
    trunk/gcc/fortran/decl.c
    trunk/gcc/fortran/gfortran.h
    trunk/gcc/fortran/io.c
    trunk/gcc/fortran/match.c
    trunk/gcc/fortran/primary.c
    trunk/gcc/fortran/resolve.c
    trunk/gcc/fortran/symbol.c


-- 


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

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

[tobi at gcc dot gnu dot org]

------- Comment #9 from tobi at gcc dot gnu dot org  2006-01-18 21:07 -------
The committed patch fixes only part of the problem, this is still a quadratic
bottleneck.


-- 


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

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

[tobi at gcc dot gnu dot org]

------- Comment #10 from tobi at gcc dot gnu dot org  2006-01-26 16:46 -------
I don't know when I will have time for this, so I'm unassigning myself.


-- 

tobi at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|tobi at gcc dot gnu dot org |unassigned at gcc dot gnu
                   |                            |dot org
             Status|ASSIGNED                    |NEW


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

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

[tobi at gcc dot gnu dot org]

------- Comment #11 from tobi at gcc dot gnu dot org  2007-03-23 22:27 -------
I've implemented Steven's bitmap idea (see PR18540).  spaghetti 99999 compiles
within the blink of an eye.  Unfortunately, my current patch foregos step four
from resolve_branch, which is necessary to establish validity of the source
program, and at the moment I have no convincong idea on how to implement this
in the framework with bitmaps.  I hope I can attend to this soon, thus
re-assigning to myself.


-- 

tobi at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |tobi at gcc dot gnu dot org
                   |dot org                     |
             Status|NEW                         |ASSIGNED
   Last reconfirmed|2006-01-14 19:03:18         |2007-03-23 22:27:07
               date|                            |


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

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

[tobi at gcc dot gnu dot org]

------- Comment #12 from tobi at gcc dot gnu dot org  2007-03-23 22:35 -------
Well, "within the blink of an eye" because I was looking at spaghetti 1000 :-) 
But the increase in time is linear.


-- 


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

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

[tobi at gcc dot gnu dot org]

------- Comment #13 from tobi at gcc dot gnu dot org  2007-03-25 20:51 -------
I have a patch which does eveything, except detecting branches to END DOs.  I
can't seem to figure out how to do this in a sensible way without introducing a
replacement quadratic bottleneck :-(


-- 


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

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

[patchapp at dberlin dot org]

------- Comment #14 from patchapp at dberlin dot org  2007-03-26 04:41 -------
Subject: Bug number PR 18937

A patch for this bug has been added to the patch tracker.
The mailing list url for the patch is
http://gcc.gnu.org/ml/gcc-patches/2007-03/msg01650.html


-- 


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

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

[tobi at gcc dot gnu dot org]

------- Comment #15 from tobi at gcc dot gnu dot org  2007-04-13 14:48 -------
Subject: Bug 18937

Author: tobi
Date: Fri Apr 13 14:48:08 2007
New Revision: 123789

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=123789
Log:
PR fortran/18937
fortran/
* resolve.c: Include obstack.h and bitmap.h.  New variable
labels_obstack.
(code_stack): Add tail and reachable_labels fields.
(reachable_labels): New function.
(resolve_branch): Rework to use new fields in code_stack.
(resolve_code): Call reachable_labels.
(resolve_codes): Allocate and free labels_obstack.
testsuite/
* gfortran.dg/goto_2.f90: New.
* gfortran.dg/goto_3.f90: New.
* gfortran.dg/pr17708.f90: Rename to ...
* gfortran.dg/goto_4.f90: ... this, add comment pointing to
PR.

Added:
    trunk/gcc/testsuite/gfortran.dg/goto_2.f90
    trunk/gcc/testsuite/gfortran.dg/goto_3.f90
    trunk/gcc/testsuite/gfortran.dg/goto_4.f90
      - copied, changed from r123784,
trunk/gcc/testsuite/gfortran.dg/pr17708.f90
Removed:
    trunk/gcc/testsuite/gfortran.dg/pr17708.f90
Modified:
    trunk/gcc/fortran/ChangeLog
    trunk/gcc/fortran/resolve.c
    trunk/gcc/testsuite/ChangeLog


-- 


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

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

[tobi at gcc dot gnu dot org]

------- Comment #16 from tobi at gcc dot gnu dot org  2007-04-13 15:16 -------
Fixed.


-- 

tobi at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |FIXED
   Target Milestone|---                         |4.3.0


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

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

[tobi at gcc dot gnu dot org]

------- Additional Comments From tobi at gcc dot gnu dot org  2004-12-14 22:09 -------
*** Bug 18943 has been marked as a duplicate of this bug. ***

-- 


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

[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-12 16:19 -------
g77 has the same problem:

$ time g77 spaghetti.f

real    0m11.649s
user    0m11.516s
sys     0m0.068s
$ ./spaghetti 20000 > spaghetti.f
$ time g77 spaghetti.f

real    0m50.604s
user    0m48.738s
sys     0m0.153s


-- 


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

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

[steven at gcc dot gnu dot org]

------- Additional Comments From steven at gcc dot gnu dot org  2004-12-11 11:55 -------
The problem in gfc_get_st_label() is easy to solve - just turn st_labels 
into a hash table.  The problem in resolve.c is more difficult, I need to 
think about that a little more... 
 

-- 


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

[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

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

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2004-12-11 08:49 -------
One more note g77 in 3.3 is faster.

-- 


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

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

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2004-12-11 08:45 -------
Actually all of the time is spent in the parser so this is not a middle-end problem.

Also note you did you did not disable checking which is enabled by default on non release branches.

 parser                :  20.34 (90%) usr   0.15 (19%) sys  22.35 (88%) wall

The compile time problems comes from transfering linked lists.
One is in resolve.c:3067-3076
Another is in symbol.c:1401-1403.

I don't know if the linked lists are long are just looked over and over.  I am going to assume the former.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|enhancement                 |minor
             Status|UNCONFIRMED                 |NEW
          Component|middle-end                  |fortran
     Ever Confirmed|                            |1
           Keywords|                            |compile-time-hog
   Last reconfirmed|0000-00-00 00:00:00         |2004-12-11 08:45:22
               date|                            |


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