[Patch,Fortran] Fix tree-walking issue (was: gfortran tree walking issue)

[Tobias Burnus <burnus at net-b dot de>]

Dear all, dear Paul,

(For gcc-patch@ readers: gfortran has issues with tree walking: During 
traversal it does not touch all tree nodes if the function called during 
traversal adds new nodes to the tree - as this will rebalance the tree. 
This causes a regression with my recently posted RFC patch for 
constructors.)


Paul Richard Thomas wrote:
> Maybe we should decide a priority order?  Your patch and those of
> Mikael could cause regressions other than in code involving OOP.  I
> would suggest, therefore, that we should find a fix for your problem
> below and get these patches committed first.  I will still try to get
> mine completed before the end of Stage 1 but it will not matter as
> much if I am a week or so late.

I think it makes sense to have mine and Mikael's patch first. Actually, 
I just saw that you approved Mikael's patch. For my patch, the 
class_21.f03/tree-walking issue is solved by the attached patch 2. I 
think after that issue is solved, you can continue working on your patch.

Constructor patch: I still have another rejects-valid issue related to 
multiple USE, ONLY for the same module, but I don't think that it makes 
sense that we both simultaneously try tackle that issue. When I have 
solved the use-only issue, I can start cleaning up the patch, add two 
diagnostic checks, tweak some diagnostics/dg-error checks, write a 
ChangeLog, re-test the patch with real-world codes, and hopefully submit 
it by next weekend.

 * * *

Regarding the tree-walking issue: I think it is a general issue which 
could also affect other things. I really wonder why we haven't been 
bitten by it before. However, it might be that we hit those problems and 
fixed them by "re"-resolving symbols at later parts. My feeling is that 
the issue occurs either only with vtab/vtree or at least also due to 
those functions. However, I might be wrong as I do not quickly see which 
of the tree-traversal callers can generate new trees.

I made two attempts to fix the issue. The first one fails - hence, I use 
the second one. In particular, I seek comments and approval for the 
second patch.


**** PATCH 1 ****

Ensuring that every tree node gets touched once. This patch works by 
traversing the tree until all nodes are touched at least once. That 
means that one has a couple of light-weight extra walks, which *includes 
the newly added nodes*.

The patch does:
a) Ensure that all trees are walked
b) Mark symbol nodes as already walked when finding a vtab
c) Skip vtab/vtype in resolve symbol

(b) and (c) do not seem to have any effect. The patch regtests*, except 
for gfortran.dg/class_21.f03, which still has an endless loop. (Cf. 
previous email.)


**** PATCH 2 ****

This patch uses a different approach to makes sure that *newly added 
nodes* do *not* get visited. It does so by saving the symtree in a 
vector and then one walks the vector. Except for the additional memory 
requirement for the vector, this version should also be quick and avoids 
walking the tree multiple times. It also preserves the order the trees 
are walked.

This patch builds and regtests* (gfortran + libgomp) on x86-64-linux.
OK for the trunk?

Tobias

* Except for the known and meanwhile old failures for 
gfortran.dg/select_type_12.f03 (P1 regression), 
gfortran.fortran-torture/execute/entry_4.f90 (P1 regression) and 
gfortran.dg/realloc_on_assign_5.f03 (failed since committal).
NOTE: The following patch does not regtest. Hence, I do not seek approval
      for this patch.

2011-11-01  Tobias Burnus  <burnus@net-b.de>

	* symbol.c (all_marked): New file-global variable.
	(is_all_marked): New function which checks whether a variable
	is marked.
	(gfc_traverse_symtree): Use them to ensure that all tree nodes
	are touched, even if the tree changes during tranversal.
	* class.c (gfc_find_derived_vtab): Mark vtab symbol to avoid double
	resolution.

diff --git a/gcc/fortran/class.c b/gcc/fortran/class.c
index f64cc1b..8880d65 100644
--- a/gcc/fortran/class.c
+++ b/gcc/fortran/class.c
@@ -591,6 +591,10 @@ have_vtype:
 
   found_sym = vtab;
 
+  /* Avoid double evaluation.  */
+  if (found_sym)
+    found_sym->mark = 1;
+
 cleanup:
   /* It is unexpected to have some symbols added at resolution or code
      generation time. We commit the changes in order to keep a clean state.  */
diff --git a/gcc/fortran/symbol.c b/gcc/fortran/symbol.c
index 67d65cb..11c83cc 100644
--- a/gcc/fortran/symbol.c
+++ b/gcc/fortran/symbol.c
@@ -102,6 +102,7 @@ static gfc_symbol *changed_syms = NULL;
 
 gfc_dt_list *gfc_derived_types;
 
+static bool all_marked;
 
 /* List of tentative typebound-procedures.  */
 
@@ -3353,6 +3354,14 @@ traverse_ns (gfc_symtree *st, void (*func) (gfc_symbol *))
 }
 
 
+static void
+is_all_marked (gfc_symtree *st)
+{
+  if (!st->n.sym->mark)
+    all_marked = false;
+}
+
+
 /* Call a given function for all symbols in the namespace.  We take
    care that each gfc_symbol node is called exactly once.  */
 
@@ -3362,7 +3371,15 @@ gfc_traverse_ns (gfc_namespace *ns, void (*func) (gfc_symbol *))
 
   gfc_traverse_symtree (ns->sym_root, clear_sym_mark);
 
-  traverse_ns (ns->sym_root, func);
+  /* As "func" might change the symtree, we need to go through
+     multiple times.  */
+  do
+    {
+       traverse_ns (ns->sym_root, func);
+       all_marked = true;
+       gfc_traverse_symtree (ns->sym_root, is_all_marked);
+    }
+  while (!all_marked);
 }
 
 

NOTE: This patch regtests. Please review.

2011-11-01  Tobias Burnus  <burnus@net-b.de>

	* symbol.c (node_cntr): New file-global variable.
	(clear_sym_mark, traverse_ns): Remove static functions.
	(count_st_nodes, do_traverse_symtree): New static functions.
	(gfc_traverse_symtree, gfc_traverse_ns): Call do_traverse_symtree.

diff --git a/gcc/fortran/symbol.c b/gcc/fortran/symbol.c
index 67d65cb..f61406b 100644
--- a/gcc/fortran/symbol.c
+++ b/gcc/fortran/symbol.c
@@ -102,6 +102,9 @@ static gfc_symbol *changed_syms = NULL;
 
 gfc_dt_list *gfc_derived_types;
 
+/* Store current symtree node-counter, used by fill_st_vector.  */
+static unsigned node_cntr;
+
 
 /* List of tentative typebound-procedures.  */
 
@@ -3310,46 +3313,77 @@ gfc_symbol_done_2 (void)
 }
 
 
-/* Clear mark bits from symbol nodes associated with a symtree node.  */
+/* Count how many nodes a symtree has.  */
 
-static void
-clear_sym_mark (gfc_symtree *st)
+static unsigned
+count_st_nodes (const gfc_symtree *st)
 {
+  unsigned nodes;
+  if (!st)
+    return 0;
+
+  nodes = count_st_nodes (st->left);
+  nodes++;
+  nodes += count_st_nodes (st->right);
 
-  st->n.sym->mark = 0;
+  return nodes;
 }
 
 
-/* Recursively traverse the symtree nodes.  */
+/* Convert symtree tree into symtree vector.  */
 
-void
-gfc_traverse_symtree (gfc_symtree *st, void (*func) (gfc_symtree *))
+static void
+fill_st_vector (gfc_symtree *st, gfc_symtree **st_vec)
 {
   if (!st)
     return;
 
-  gfc_traverse_symtree (st->left, func);
-  (*func) (st);
-  gfc_traverse_symtree (st->right, func);
+  fill_st_vector (st->left, st_vec);
+  st_vec[node_cntr++] = st;
+  fill_st_vector (st->right, st_vec);
 }
 
 
-/* Recursive namespace traversal function.  */
+/* Traverse namespace. As the functions might modify the symtree, we store the
+   symtree as a vector and operate on this vector.  */
 
 static void
-traverse_ns (gfc_symtree *st, void (*func) (gfc_symbol *))
+do_traverse_symtree (gfc_symtree *st, void (*st_func) (gfc_symtree *),
+		     void (*sym_func) (gfc_symbol *))
 {
+  gfc_symtree **st_vec;
+  unsigned nodes, i;
 
-  if (st == NULL)
-    return;
+  gcc_assert ((st_func && !sym_func) || (!st_func && sym_func));
+  nodes = count_st_nodes (st);
+  st_vec = XALLOCAVEC (gfc_symtree *, nodes);
+  node_cntr = 0; 
+  fill_st_vector (st, st_vec);
+
+  if (sym_func)
+    {
+      /* Clear marks.  */
+      for (i = 0; i < nodes; i++)
+	st_vec[i]->n.sym->mark = 0;
+      for (i = 0; i < nodes; i++)
+	if (!st_vec[i]->n.sym->mark)
+	  {
+	    (*sym_func) (st_vec[i]->n.sym);
+	    st_vec[i]->n.sym->mark = 1;
+	  }
+     }
+   else
+      for (i = 0; i < nodes; i++)
+	(*st_func) (st_vec[i]);
+}
 
-  traverse_ns (st->left, func);
 
-  if (st->n.sym->mark == 0)
-    (*func) (st->n.sym);
-  st->n.sym->mark = 1;
+/* Recursively traverse the symtree nodes.  */
 
-  traverse_ns (st->right, func);
+void
+gfc_traverse_symtree (gfc_symtree *st, void (*st_func) (gfc_symtree *))
+{
+  do_traverse_symtree (st, st_func, NULL);
 }
 
 
@@ -3357,12 +3391,9 @@ traverse_ns (gfc_symtree *st, void (*func) (gfc_symbol *))
    care that each gfc_symbol node is called exactly once.  */
 
 void
-gfc_traverse_ns (gfc_namespace *ns, void (*func) (gfc_symbol *))
+gfc_traverse_ns (gfc_namespace *ns, void (*sym_func) (gfc_symbol *))
 {
-
-  gfc_traverse_symtree (ns->sym_root, clear_sym_mark);
-
-  traverse_ns (ns->sym_root, func);
+  do_traverse_symtree (ns->sym_root, NULL, sym_func);
 }