[Bug fortran/18937] quadratic behaviour with many label spaghetti code
--- 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=gccview=revrev=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
--- 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
--- 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
--- 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
--- 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 9 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
--- 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
--- 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
--- 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=gccview=revrev=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
--- 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 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
--- 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
--- 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
--- Additional Comments From Thomas dot Koenig at online dot de 2004-12-12 16:19 --- g77 has the same problem: $ time g77 spaghetti.f real0m11.649s user0m11.516s sys 0m0.068s $ ./spaghetti 2 spaghetti.f $ time g77 spaghetti.f real0m50.604s user0m48.738s sys 0m0.153s -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18937
[Bug fortran/18937] quadratic behaviour with many label spaghetti code
--- 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|-00-00 00:00:00 |2004-12-11 08:45:22 date|| http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18937
[Bug fortran/18937] quadratic behaviour with many label spaghetti code
--- 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
real0m0.244s
user0m0.224s
sys 0m0.012s
$ ./spaghetti-c 1 sp.c
$ time gcc sp.c
real0m2.594s
user0m2.473s
sys 0m0.058s
$ ./spaghetti-c 10 sp.c
$ time gcc sp.c
real0m32.483s
user0m31.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:\ni++;\ngoto 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
--- 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
--- 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
