Re: Language-independent functions-as-trees representation

[Jason Merrill <jason at redhat dot com>]

>>>>> "Mark" == Mark Mitchell <mark@codesourcery.com> writes:

>>> I was implicitly (sorry!) in SSA form.
>> 
>> I remain unenlightened.  Can you give an example of where such sharing
>> would be useful?

> You mean, I assume, other than the obvious memory savings.  (In practice,
> those savings can be rather substantial, and since we are trying to
> avoid making compile-time any worse than it already is, something that
> substantially reduces memory use may be worthwhile for that reason if
> for no other.)

Yep.

> Consider that you want to do value-numbering to find places where you
> compute the same value multiple times.  [snip]

Sure, any time you need to compare things it's faster if you can use
pointer comparison.  I was actually hoping for a small testcase, so we
could talk about the tradeoffs.

> However, with sharing, you must do work as you build the structure so that
> you make sure that you really are sharing.  But that is not so hard; you
> just keep tables of the things built from nodes you already have and check
> to see if the node you are building uses the same operation to combine
> the arguments as the one you already have.

The tricky part, as I mentioned before, is maintaining proper semantics
when simplifying shared trees, or indeed when making any modifications.
Sharing makes copying and comparison fast, but makes modification slow.
Simplification generally involves the recursive replacement of expressions
with temporary variables.  If the expressions are shared, this will change
semantics unless you somehow arrange to unshare them on modification, which
could imply an arbitrary amount of backtracking.  If I have a+b+c+d+e+f+g
and I want to replace a+b with a temp, I have to make a new copy of the
whole expression everywhere it appears, or suddenly all instances will use
the same temp, which is wrong if 'a' changes in the interim.

Or are you suggesting that we start sharing trees after simplification?
Given that we only do GC between functions, I don't think that would
provide any memory savings.

And I still don't see how this relates to the statement/expression
distinction.

Jason