Re: Great example of why "everything is a tree" sucks

[Steven Bosscher <stevenb dot gcc at gmail dot com>]

On Wed, Nov 13, 2013 at 11:15 AM, Richard Biener wrote:
> You know - 'tree's were a design decision (well, just my guess - I wasn't
> around 25 years ago ...).  They are a perfect match to represent an AST.

I'd argue against that, but perhaps some other time, in a different thread...


> So I'd say whoever introduced that middle-end between the FEs AST
> and RTL was at fault :P  (luckily I wasn't around either ... ;))

A brief history of 'tree' for you, then! :-)

Originally 'tree' wasn't a very long-living structure. The front ends
would build some declaration or expression as a 'tree', expand it to
RTL immediately, and free the 'tree'.

Then we got functions-as-trees, at first for a C++ front-end specific
inliner and later for a generic tree inliner for all front ends (you
can still see the C++ front-end specific code in tree-inline.c).

Next up was tree-ssa as an experiment. Turned out perhaps a somewhat
bigger project than initially anticipated, but the idea was: "Hey, we
have functions as 'tree' now, let's see if we can do some code
transformations on it!" I don't think it was a concious design
decision at the time to make 'tree' the new IL for a complete new
optimization framework. What started as convenient ("it's there, let's
do something with it") is now considered inappropriate use of FE-trees
in the middle end.

The funny thing is that 'tree' also doesn't really work for the front
ends because many language specific things are more easily expressed
in front-end specific types and data structures. Remember the
discussions about the C++ front end AST being too far away from the
source language? That's still true, and one reason for it is 'tree'.
The Ada, Fortran, and even C front ends use front-end specific data
structures for most parsed entities and only produce 'tree' from it in
the process of generatic GENERIC.



> Still splitting 'tree's into a few separate classes is not hard.  It's just
> work - and in the end even the frontends will benefit.  Oh, and I believe
> it is a project that has a much higher success rate than trying to
> replace trees with "something else" in the GIMPLE and RTL middle-end
> only and have that cooperate sanely with the rest of the compiler.
> Something along 1 man year for the first with a 75% success chance
> against 6 man years for the second with a 20% success chance.
> And the nice thing is that the first can be done incrementally
> (we _are_ already in the process of that transition - see the changes
> done to 'tree' during the last 6 years).  And the other nice thing is that
> even non-100% success will end up in something better than we have now.
> With the second project it's a all-or-nothing (or rather
> all-or-just-uglification).

Agreed. Obviously something has to be done, but I've got the feeling
we may be attacking the problem from the wrong end...

Ciao!
Steven