Re: Language-independent functions-as-trees representation

[Mark Mitchell <mark at codesourcery dot com>]

> > 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.)

Consider that you want to do value-numbering to find places where you
compute the same value multiple times.  (Perhaps so as to move
computations to some point that dominates all of the uses, for example.)

Without sharing, you must recursively examine each new expression to see
to which existing expressions is identical.  (You can use hashing to speed
this up, but you must ultimately do a recursive walk.)

With sharing, you just do a pointer comparison.

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.

--
Mark Mitchell                mark@codesourcery.com
CodeSourcery, LLC            http://www.codesourcery.com