[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 #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
--- 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 #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 #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 #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 #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 #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
--- 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 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 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
--- 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 < int main() { int i=0; goto l_1; EOF print @lines; printf ("l_%d:\n",$last+1); print < 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 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