* [Bug fortran/18937] quadratic behaviour with many label "spaghetti" code
2004-12-11 8:28 [Bug middle-end/18937] New: quadratic behaviour with many label "spaghetti" code Thomas dot Koenig at online dot de
@ 2004-12-11 8:45 ` pinskia at gcc dot gnu dot org
2004-12-11 8:49 ` pinskia at gcc dot gnu dot org
` (4 subsequent siblings)
5 siblings, 0 replies; 18+ messages in thread
From: pinskia at gcc dot gnu dot org @ 2004-12-11 8:45 UTC (permalink / raw)
To: gcc-bugs
------- 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
^ permalink raw reply [flat|nested] 18+ messages in thread
* [Bug fortran/18937] quadratic behaviour with many label "spaghetti" code
2004-12-11 8:28 [Bug middle-end/18937] New: quadratic behaviour with many label "spaghetti" code Thomas dot Koenig at online dot de
2004-12-11 8:45 ` [Bug fortran/18937] " pinskia at gcc dot gnu dot org
@ 2004-12-11 8:49 ` pinskia at gcc dot gnu dot org
2004-12-11 10:40 ` Thomas dot Koenig at online dot de
` (3 subsequent siblings)
5 siblings, 0 replies; 18+ messages in thread
From: pinskia at gcc dot gnu dot org @ 2004-12-11 8:49 UTC (permalink / raw)
To: gcc-bugs
------- 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
^ permalink raw reply [flat|nested] 18+ messages in thread
* [Bug fortran/18937] quadratic behaviour with many label "spaghetti" code
2004-12-11 8:28 [Bug middle-end/18937] New: quadratic behaviour with many label "spaghetti" code Thomas dot Koenig at online dot de
2004-12-11 8:45 ` [Bug fortran/18937] " pinskia at gcc dot gnu dot org
2004-12-11 8:49 ` pinskia at gcc dot gnu dot org
@ 2004-12-11 10:40 ` Thomas dot Koenig at online dot de
2004-12-11 11:55 ` steven at gcc dot gnu dot org
` (2 subsequent siblings)
5 siblings, 0 replies; 18+ messages in thread
From: Thomas dot Koenig at online dot de @ 2004-12-11 10:40 UTC (permalink / raw)
To: gcc-bugs
------- 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
^ permalink raw reply [flat|nested] 18+ messages in thread
* [Bug fortran/18937] quadratic behaviour with many label "spaghetti" code
2004-12-11 8:28 [Bug middle-end/18937] New: quadratic behaviour with many label "spaghetti" code Thomas dot Koenig at online dot de
` (2 preceding siblings ...)
2004-12-11 10:40 ` Thomas dot Koenig at online dot de
@ 2004-12-11 11:55 ` steven at gcc dot gnu dot org
2004-12-12 16:19 ` Thomas dot Koenig at online dot de
2004-12-14 22:09 ` tobi at gcc dot gnu dot org
5 siblings, 0 replies; 18+ messages in thread
From: steven at gcc dot gnu dot org @ 2004-12-11 11:55 UTC (permalink / raw)
To: gcc-bugs
------- 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
^ permalink raw reply [flat|nested] 18+ messages in thread
* [Bug fortran/18937] quadratic behaviour with many label "spaghetti" code
2004-12-11 8:28 [Bug middle-end/18937] New: quadratic behaviour with many label "spaghetti" code Thomas dot Koenig at online dot de
` (3 preceding siblings ...)
2004-12-11 11:55 ` steven at gcc dot gnu dot org
@ 2004-12-12 16:19 ` Thomas dot Koenig at online dot de
2004-12-14 22:09 ` tobi at gcc dot gnu dot org
5 siblings, 0 replies; 18+ messages in thread
From: Thomas dot Koenig at online dot de @ 2004-12-12 16:19 UTC (permalink / raw)
To: gcc-bugs
------- 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
^ permalink raw reply [flat|nested] 18+ messages in thread
* [Bug fortran/18937] quadratic behaviour with many label "spaghetti" code
2004-12-11 8:28 [Bug middle-end/18937] New: quadratic behaviour with many label "spaghetti" code Thomas dot Koenig at online dot de
` (4 preceding siblings ...)
2004-12-12 16:19 ` Thomas dot Koenig at online dot de
@ 2004-12-14 22:09 ` tobi at gcc dot gnu dot org
5 siblings, 0 replies; 18+ messages in thread
From: tobi at gcc dot gnu dot org @ 2004-12-14 22:09 UTC (permalink / raw)
To: gcc-bugs
------- 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
^ permalink raw reply [flat|nested] 18+ messages in thread
* [Bug fortran/18937] quadratic behaviour with many label "spaghetti" code
[not found] <bug-18937-9515@http.gcc.gnu.org/bugzilla/>
@ 2006-01-09 18:57 ` tobi at gcc dot gnu dot org
2006-01-14 19:03 ` tobi at gcc dot gnu dot org
` (9 subsequent siblings)
10 siblings, 0 replies; 18+ messages in thread
From: tobi at gcc dot gnu dot org @ 2006-01-09 18:57 UTC (permalink / raw)
To: gcc-bugs
------- 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
^ permalink raw reply [flat|nested] 18+ messages in thread
* [Bug fortran/18937] quadratic behaviour with many label "spaghetti" code
[not found] <bug-18937-9515@http.gcc.gnu.org/bugzilla/>
2006-01-09 18:57 ` tobi at gcc dot gnu dot org
@ 2006-01-14 19:03 ` tobi at gcc dot gnu dot org
2006-01-18 20:54 ` tobi at gcc dot gnu dot org
` (8 subsequent siblings)
10 siblings, 0 replies; 18+ messages in thread
From: tobi at gcc dot gnu dot org @ 2006-01-14 19:03 UTC (permalink / raw)
To: gcc-bugs
--
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
^ permalink raw reply [flat|nested] 18+ messages in thread
* [Bug fortran/18937] quadratic behaviour with many label "spaghetti" code
[not found] <bug-18937-9515@http.gcc.gnu.org/bugzilla/>
2006-01-09 18:57 ` tobi at gcc dot gnu dot org
2006-01-14 19:03 ` tobi at gcc dot gnu dot org
@ 2006-01-18 20:54 ` tobi at gcc dot gnu dot org
2006-01-18 21:07 ` tobi at gcc dot gnu dot org
` (7 subsequent siblings)
10 siblings, 0 replies; 18+ messages in thread
From: tobi at gcc dot gnu dot org @ 2006-01-18 20:54 UTC (permalink / raw)
To: gcc-bugs
------- 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
^ permalink raw reply [flat|nested] 18+ messages in thread
* [Bug fortran/18937] quadratic behaviour with many label "spaghetti" code
[not found] <bug-18937-9515@http.gcc.gnu.org/bugzilla/>
` (2 preceding siblings ...)
2006-01-18 20:54 ` tobi at gcc dot gnu dot org
@ 2006-01-18 21:07 ` tobi at gcc dot gnu dot org
2006-01-26 16:46 ` tobi at gcc dot gnu dot org
` (6 subsequent siblings)
10 siblings, 0 replies; 18+ messages in thread
From: tobi at gcc dot gnu dot org @ 2006-01-18 21:07 UTC (permalink / raw)
To: gcc-bugs
------- 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
^ permalink raw reply [flat|nested] 18+ messages in thread
* [Bug fortran/18937] quadratic behaviour with many label "spaghetti" code
[not found] <bug-18937-9515@http.gcc.gnu.org/bugzilla/>
` (3 preceding siblings ...)
2006-01-18 21:07 ` tobi at gcc dot gnu dot org
@ 2006-01-26 16:46 ` tobi at gcc dot gnu dot org
2007-03-23 22:27 ` tobi at gcc dot gnu dot org
` (5 subsequent siblings)
10 siblings, 0 replies; 18+ messages in thread
From: tobi at gcc dot gnu dot org @ 2006-01-26 16:46 UTC (permalink / raw)
To: gcc-bugs
------- 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
^ permalink raw reply [flat|nested] 18+ messages in thread
* [Bug fortran/18937] quadratic behaviour with many label "spaghetti" code
[not found] <bug-18937-9515@http.gcc.gnu.org/bugzilla/>
` (4 preceding siblings ...)
2006-01-26 16:46 ` tobi at gcc dot gnu dot org
@ 2007-03-23 22:27 ` tobi at gcc dot gnu dot org
2007-03-23 22:35 ` tobi at gcc dot gnu dot org
` (4 subsequent siblings)
10 siblings, 0 replies; 18+ messages in thread
From: tobi at gcc dot gnu dot org @ 2007-03-23 22:27 UTC (permalink / raw)
To: gcc-bugs
------- 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
^ permalink raw reply [flat|nested] 18+ messages in thread
* [Bug fortran/18937] quadratic behaviour with many label "spaghetti" code
[not found] <bug-18937-9515@http.gcc.gnu.org/bugzilla/>
` (5 preceding siblings ...)
2007-03-23 22:27 ` tobi at gcc dot gnu dot org
@ 2007-03-23 22:35 ` tobi at gcc dot gnu dot org
2007-03-25 18:51 ` tobi at gcc dot gnu dot org
` (3 subsequent siblings)
10 siblings, 0 replies; 18+ messages in thread
From: tobi at gcc dot gnu dot org @ 2007-03-23 22:35 UTC (permalink / raw)
To: gcc-bugs
------- 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
^ permalink raw reply [flat|nested] 18+ messages in thread
* [Bug fortran/18937] quadratic behaviour with many label "spaghetti" code
[not found] <bug-18937-9515@http.gcc.gnu.org/bugzilla/>
` (6 preceding siblings ...)
2007-03-23 22:35 ` tobi at gcc dot gnu dot org
@ 2007-03-25 18:51 ` tobi at gcc dot gnu dot org
2007-03-26 3:41 ` patchapp at dberlin dot org
` (2 subsequent siblings)
10 siblings, 0 replies; 18+ messages in thread
From: tobi at gcc dot gnu dot org @ 2007-03-25 18:51 UTC (permalink / raw)
To: gcc-bugs
------- 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
^ permalink raw reply [flat|nested] 18+ messages in thread
* [Bug fortran/18937] quadratic behaviour with many label "spaghetti" code
[not found] <bug-18937-9515@http.gcc.gnu.org/bugzilla/>
` (7 preceding siblings ...)
2007-03-25 18:51 ` tobi at gcc dot gnu dot org
@ 2007-03-26 3:41 ` patchapp at dberlin dot org
2007-04-13 13:48 ` tobi at gcc dot gnu dot org
2007-04-13 14:16 ` tobi at gcc dot gnu dot org
10 siblings, 0 replies; 18+ messages in thread
From: patchapp at dberlin dot org @ 2007-03-26 3:41 UTC (permalink / raw)
To: gcc-bugs
------- 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
^ permalink raw reply [flat|nested] 18+ messages in thread
* [Bug fortran/18937] quadratic behaviour with many label "spaghetti" code
[not found] <bug-18937-9515@http.gcc.gnu.org/bugzilla/>
` (8 preceding siblings ...)
2007-03-26 3:41 ` patchapp at dberlin dot org
@ 2007-04-13 13:48 ` tobi at gcc dot gnu dot org
2007-04-13 14:16 ` tobi at gcc dot gnu dot org
10 siblings, 0 replies; 18+ messages in thread
From: tobi at gcc dot gnu dot org @ 2007-04-13 13:48 UTC (permalink / raw)
To: gcc-bugs
------- 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
^ permalink raw reply [flat|nested] 18+ messages in thread
* [Bug fortran/18937] quadratic behaviour with many label "spaghetti" code
[not found] <bug-18937-9515@http.gcc.gnu.org/bugzilla/>
` (9 preceding siblings ...)
2007-04-13 13:48 ` tobi at gcc dot gnu dot org
@ 2007-04-13 14:16 ` tobi at gcc dot gnu dot org
10 siblings, 0 replies; 18+ messages in thread
From: tobi at gcc dot gnu dot org @ 2007-04-13 14:16 UTC (permalink / raw)
To: gcc-bugs
------- 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
^ permalink raw reply [flat|nested] 18+ messages in thread