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

[Tobias Burnus]

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).
-------------- next part --------------
A non-text attachment was scrubbed...
Name: tree-walk_PATCH_1.diff
Type: text/x-patch
Size: 2013 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/fortran/attachments/20111101/ad5fe93a/attachment.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: tree-walk_PATCH_2.diff
Type: text/x-patch
Size: 3462 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/fortran/attachments/20111101/ad5fe93a/attachment-0001.bin>