diff mbox

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

Message ID 4EB065AE.1070704@net-b.de
State New
Headers show

Commit Message

Tobias Burnus Nov. 1, 2011, 9:33 p.m. UTC 
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).

Comments

Tobias Schlüter Nov. 1, 2011, 9:40 p.m. UTC | #1 
Dear Tobias,

On 2011-11-01 22:33, Tobias Burnus wrote:
> 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 don't remember all this very clearly, but I think that the 
gfc_symbol::tlink field is intended for something like this, even though 
this is not very clear (at least to me) from the explanatory comment I 
quoted below.  Anyway, I thought I might point this out, as it might 
help you getting things working since the problem it addresses at least 
appears similar:

   /* Change management fields.  Symbols that might be modified by the
      current statement have the mark member nonzero and are kept in a
      singly linked list through the tlink field.  Of these symbols,
      symbols with old_symbol equal to NULL are symbols created within
      the current statement.  Otherwise, old_symbol points to a copy of
      the old symbol.  */

   struct gfc_symbol *old_symbol, *tlink;

Cheers,
- Tobi
diff mbox

Patch

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);
 }