Re: Link-time optimzation

[Michael Matz <matz@suse.de>]

Hi,

On Thu, 17 Nov 2005, Kenneth Zadeck wrote:

> A stack machine representation was chosen for the same reason.  Tree
> gimple is a series of statements each statement being a tree.

IMHO we should follow that path of thinking.  The representation of GIMPLE 
where we do most optimizations on (i.e. tree-ssa) is implemented as 
GCC trees, thats true.  But this is just an implementation detail, and one 
which somewhen in the future hopefully will be changed.  Because in 
essence GIMPLE is a rather flat intermediate form, most of the time just 
three address form.  I think it would be a mistake in the long run if we 
would now use a stack based external representation just because right now 
gimple is implemeted via trees.  For instance the gimple statement

  a = b + c

would need to be implemented ala
  push id_b
  push id_c
  add
  pop id_a

The expansion of the trivial operation into four stackops is horrible to 
read (think reading debug dumps).  Additionally the change of 
representation form might introduce hard to overcome issues due to 
mismatches in the expressiveness.  We would possibly need a mini stack 
optimizer for just reading back this form into gimple.

I think writing out gimple directly, i.e. using a register machine and 
three address code, is the better way.  I could even imagine some custom 
extensions to the three address form to easily represent nested constructs 
which still happen in gimple (e.g. type conversions, address taking etc).

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

In the above light I would go for 2) together with perhaps relatively 
trivial form of 1)  (e.g. reusing temps per gimple statements, which 
reduces the overall need for temps to the max Sethi-Ullman number for the 
statements to be converted, most of the time lower than lets say 20).

OTOH it might be a good idea to persue both strategies at first (i.e. a 
gimple writer/reader based on stack machine and one based on register 
machine), and then see which feels better.  Perhaps even a merger of both 
approaches is sensible, three address form for most simple gimple 
statements with falling back to stack encoding for deeply nested operands.


Ciao,
Michael.