Re: Link-time optimzation

[Jan Hubicka <hubicka at ucw dot cz>]

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

Actually I also tend to think that using stack based IL would be mistake
here.  Gimple is represented as tree in low level, but basically it is
flat IL with registers, so having the representation close to such
language would actually make translation more direct, I would expect.
I think we can gradually move away from the nested tree representation
of gimple and thus it would be better to not push it deeper into our
design decisions.
> 
> 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.

I have a feeling that going in/out of stack representation will cause
some extra garbage to be produced (pretty much like we do with reg-stack
that solve sort of similar problem), making it bit more challenging to
optimize code at compilation time and save work by not re-doing it all
at link time.  It seems important to me that saving/restoring pair don't
actually introduce any non-trivial suboptimalities.  I would probably
preffer if it was possible to save IL in SSA form unless this is really
seen as overkill file size wise.

Compactness is important here, but since we are going to expand
everything into temporary form in memory anyway we are not going to win
that much I would say.  My preferences here (at this very moment) would
be to hope for 2) to save day ;))

I am on the vacation now, so I won't comment much before I have chance
to look closer into the proposal at monday, so these are just my 2
cents...
But thanks for all the work,
Honza