Re: [Patch,Fortran] Fix tree-walking issue
On Wed, Nov 2, 2011 at 09:33, Tobias Burnus bur...@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 -- Janne Blomqvist
Re: [Patch,Fortran] Fix tree-walking issue
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
2011-11-02 Tobias Burnus bur...@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);
}
[Patch,Fortran] Fix tree-walking issue (was: gfortran tree walking issue)
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 bur...@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
Re: [Patch,Fortran] Fix tree-walking issue
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
