Re: CIL question

Stefan Mandel <stefan.mandel@iese.fraunhofer.de> writes:
>Most optimizing compilers translate the source language to an
>intermediate representation with a infinite number of registers (e.g.
>SSA code). Optimization and register allocation should be quite
>efficient with this IR.


>I yet do not know how to map
>stack code


Converting stack code with statically determined stack depth (as
required by JVM) to SSA is trivial: Maintain a stack of SSA registers
at compile time.


For a simple VM instruction like iadd, at compile-time take two items
i1 and i2 from the stack, generate a new register i3, and generate an
instruction


i3 = i1+i2;


For a stack manipulation instruction like DUP, perform the stack
manipulation at compile time and generate no code.


For a control flow join, where the two control flows have the stack
depth n (the VM guarantees that the stack depth is the same), with the
stacks containing (a1, ... , an) and (b1, ..., bn), the new basic
block starts with new registers (c1, ..., cn), and generate the
following code:


c1 = phi(a1, b1)
...
cn = phi(an, bn)


(as an optimization, if ai=bi, don't create a new ci and the phi node,
and let ci=ai).


You can find a longer description (except that it produces C code in
this spirit, not SSA form) in
<http://www.complang.tuwien.ac.at/papers/ertl%26maierhofer95.ps.gz>.


However, since the JVM is not a pure stack VM, things are a little
more complicated. You have to deal with the local variables, too, and
that requires some additional effort.


Maybe it's easier to process a linearized SSA form, but the difference
is not big, and it probably is not worth the additional space
requirement. You could go to a compressed form as is done in SafeTSA,
but that is more complicated (but offers other advantages), and was
only researched after the JVM was designed.


- anton
--
M. Anton Ertl
anton@mips.complang.tuwien.ac.at
http://www.complang.tuwien.ac.at/anton/home.html

Return to the comp.compilers page.
Search the comp.compilers archives again.