Re: Link-time optimzation

[Kenneth Zadeck <Kenneth.Zadeck@NaturalBridge.com>]

On Wed, Nov 16, 2005 at 02:26:28PM -0800, Mark Mitchell wrote:
> >   http://gcc.gnu.org/projects/lto/lto.pdf
> 
> Section 4.2
> 
>   What is the rationale for using a stack-based representation rather
>   than a register-based representation?  A infinite register based
>   solution would seem to map better onto gimple, making it easier to
>   understand the conversion into and out of.  The required stacking
>   and unstacking operations would seem to get in the way.
> 
>   C.f. plan9's inferno, rather than jvm or cil.

What we wanted was something that was portable and easy to specify but
also easily exported from and imported into GCC.  With respect to
those constraints, JVM, CIL and LLVM do not make the cut because they
are different enough from the tree-gimple code that we have to make
the translation into and/or out of gcc difficult.  This is not NIH,
just being pragmatic about not wanting to have to commit resources into
things that are not important.

A stack machine representation was chosen for the same reason.  Tree
gimple is a series of statements each statement being a tree.
Smashing the trees and introducing temps is easy on the output side
but requires a lot of work on the input side.  I am not a fan of our
tree representations, but I did not believe that changing them should
be a necessary to get to link time optimization.  If we decide we want
to get rid if trees as an intermediate form, this decision should
change.

A well designed stack machine also provides for a very tight encoding.
It is very desirable from a size of portable code point of view to
minimize the number of temps that you create.  You can do this in
several ways:

1) Do some register allocation of the temps so that they are reused.
   This is non trivial to undo (but truely doable), especially where
   you wish to not adversely impact debugging.

2) Just generate a lot of temps and hope that some other form of
   compression will save the day.

3) Use a stack to represent the intermediate nodes of the tree.  This
   is what we chose to do.

It is trivial to generate the stack code from a single walk of the
tree.  It is trivial to regenerate the tree from a single pass over
the stack code.

The stack machine that we have in mind will be as stripped down as
possible.  The idea is just to get the trees in and get them back out.


Kenny