Re: CIL question (Anton Ertl)
28 Jan 2006 15:12:05 -0500

          From comp.compilers

Related articles
CIL question (Stefan Mandel) (2006-01-19)
Re: CIL question (Paolo Molaro) (2006-01-20)
Re: CIL question (Hans-Peter Diettrich) (2006-01-20)
Re: CIL question (Stefan Mandel) (2006-01-26)
Re: CIL question (2006-01-28)
Re: CIL question (Paolo Molaro) (2006-01-28)
Re: CIL question (Hans-Peter Diettrich) (2006-01-28)
Re: CIL question (Nathan Moore) (2006-01-28)
| List of all articles for this month |

From: (Anton Ertl)
Newsgroups: comp.compilers
Date: 28 Jan 2006 15:12:05 -0500
Organization: Institut fuer Computersprachen, Technische Universitaet Wien
References: 06-01-065 06-01-068 06-01-076
Keywords: code, design
Posted-Date: 28 Jan 2006 15:12:05 EST

Stefan Mandel <> 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

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

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

Post a followup to this message

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