diff mbox

[Fortran] Fix tree-walking issue

Message ID 4EB0F254.4020002@net-b.de
State New
Headers show

Commit Message

Tobias Burnus Nov. 2, 2011, 7:33 a.m. UTC 
Dear all,

attached is an updated version of Patch 2. The change is that I removed 
the global variable for fill_st_vector and updated the comment for 
do_traverse_symtree to make assumptions clearer.

This version of the patch was build and regtested (gfortran + libgomp).
OK?


Dear Tobias S.,

Tobias Schlüter wrote:
> I don't remember all this very clearly, but I think that the 
> gfc_symbol::tlink field is intended for something like this

I think that's a rather different issue: It relates to undoing a symbol, 
which I do not want to do. Additionally, a tlink symbol is already added 
to a symtree (which is hence rebalanced). One possibility is to delay 
the inclusion of symbols into the symtree - and do only so after the 
traversal - but that might cause issues if one later searches in called 
function for that symtree. Thus, I think my current patch should be 
sufficiently simple, fast and solid.

Tobias

Comments

Janne Blomqvist Nov. 9, 2011, 7:04 p.m. UTC | #1 
On Wed, Nov 2, 2011 at 09:33, Tobias Burnus <burnus@net-b.de> wrote:
> Dear all,
>
> attached is an updated version of Patch 2. The change is that I removed the
> global variable for fill_st_vector and updated the comment for
> do_traverse_symtree to make assumptions clearer.
>
> This version of the patch was build and regtested (gfortran + libgomp).
> OK?

Ok.

It seems a bit unclear whether marking helps or not, but at least it
doesn't seem to make anything worse..

>
>
> Dear Tobias S.,
>
> Tobias Schlüter wrote:
>>
>> I don't remember all this very clearly, but I think that the
>> gfc_symbol::tlink field is intended for something like this
>
> I think that's a rather different issue: It relates to undoing a symbol,
> which I do not want to do. Additionally, a tlink symbol is already added to
> a symtree (which is hence rebalanced). One possibility is to delay the
> inclusion of symbols into the symtree - and do only so after the traversal -
> but that might cause issues if one later searches in called function for
> that symtree. Thus, I think my current patch should be sufficiently simple,
> fast and solid.
>
> Tobias
>
diff mbox

Patch

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

	* symbol.c (clear_sym_mark, traverse_ns): Remove functions.
	(count_st_nodes, do_traverse_symtree, fill_st_vector): New 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..c3a0867 100644
--- a/gcc/fortran/symbol.c
+++ b/gcc/fortran/symbol.c
@@ -3310,46 +3310,81 @@  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;
 
-  st->n.sym->mark = 0;
+  nodes = count_st_nodes (st->left);
+  nodes++;
+  nodes += count_st_nodes (st->right);
+
+  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 unsigned
+fill_st_vector (gfc_symtree *st, gfc_symtree **st_vec, unsigned node_cntr)
 {
   if (!st)
-    return;
+    return node_cntr;
+
+  node_cntr = fill_st_vector (st->left, st_vec, node_cntr);
+  st_vec[node_cntr++] = st;
+  node_cntr = fill_st_vector (st->right, st_vec, node_cntr);
 
-  gfc_traverse_symtree (st->left, func);
-  (*func) (st);
-  gfc_traverse_symtree (st->right, func);
+  return node_cntr;
 }
 
 
-/* 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.  Note: We assume that
+   sym_func or st_func never deletes nodes from the symtree - only adding is
+   allowed.  */
 
 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, node_cntr;
 
-  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, node_cntr);
+
+  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 +3392,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);
 }