[Bug fortran/80440] New: Slow compile when USEing modules

[abensonca at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=80440

            Bug ID: 80440
           Summary: Slow compile when USEing modules
           Product: gcc
           Version: 7.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: fortran
          Assignee: unassigned at gcc dot gnu.org
          Reporter: abensonca at gmail dot com
  Target Milestone: ---

Compile times for code that makes extensive USEs of modules seems to be very 
slow in some cases. I've been doing some investigation of the cause of this 
with the hope that I can maybe figure out some way to speed things up.

For example, I have a smallish file - 700 lines of code, which takes around 3 
minutes to compile with a recent build of gfortran. Profiling f951 with 
valgrind I find that 63% of that time is spent in find_symtree_for_symbol(), 
which (if I understand correctly) is searching for a node in the symtree that 
already references some symbol being imported from a module. 

find_symtree_for_symbol() gets called directly 245,658 times in compiling this 
source file (and calls itself recursively almost 19 billion times!).

find_symtree_for_symbol() is just stepping through a binary branching tree 
looking for a reference to a given symbol, but (again, if I understood 
correctly), it can't use the usual bbt search approach because the tree is not 
ordered by the symbol name, so the search is O(n) rather than O(log n). 

If I ignore my ignorance of why the ordered tree isn't used here and go ahead
and search it using the symbol name (ignoring case which seems to differ
between the symbol name and the name of the symtree node) then I certainly get
a substantial speed-up (the file I mentioned now compiles in 40s), and nothing
seems to break. I ran the gfortan test suite which shows two FAILs:

gcc/testsuite/gfortran/gfortran.sum:FAIL: gfortran.dg/graphite/pr68279.f90   -
O  (internal compiler error)
gcc/testsuite/gfortran/gfortran.sum:FAIL: gfortran.dg/graphite/pr68279.f90   -
O  (test for excess errors)

but those show up when I run the test suite without any change to module.c 
anyway.

The patch I used is:

diff --git a/gcc/fortran/module.c b/gcc/fortran/module.c
index 6d3860e..f28a7b7 100644
--- a/gcc/fortran/module.c
+++ b/gcc/fortran/module.c
@@ -4286,22 +4286,25 @@ mio_symbol (gfc_symbol *sym)
 static gfc_symtree *
 find_symtree_for_symbol (gfc_symtree *st, gfc_symbol *sym)
 {
-  gfc_symtree *s = NULL;
-
-  if (st == NULL)
-    return s;
-
-  s = find_symtree_for_symbol (st->right, sym);
-  if (s != NULL)
-    return s;
-  s = find_symtree_for_symbol (st->left, sym);
-  if (s != NULL)
-    return s;
+  int c;
+  
+  while (st != NULL)
+    {
+      c = strcasecmp(sym->name, st->name);
+      if ( c == 0 )
+       {
+         if ( !check_unique_name (st->name))
+           {
+             return st;
+           } else {
+           return NULL;
+         }
+       }

-  if (st->n.sym == sym && !check_unique_name (st->name))
-    return st;
+      st = (c < 0) ? st->left : st->right;
+    }

-  return s;
+  return NULL;
 }