Re: Graph coloring and JIT compilers.

torbenm@app-4.diku.dk (=?iso-8859-1?q?Torben_=C6gidius_Mogensen?=) writes:
> - The Java JVM is (mostly) stack-based, so you can't directly apply
> graph colouring to do register allocation -- you would first have
> to convert to named-variable form.


Graph colouring works on a conflict graph. Getting from a stack-based
form to the conflict graph seems a little bit easer to me than from a
named-variable form, because liveness information is explicit in the
stack form.


> The usual approach to
> stack-to-register conversion used a near-minimal number of
> registers, so tehre is no need for a separate register-allocation
> phase.


Yes, as long as you use the stack only within basic blocks (as is done
most of the time by most compilers that generate JVM code), register
allocation for the stack is trivial; register allocation for variables
in basic blocks (without scheduling) is also easy and does not need
graph colouring or similar stuff.


> You can use register allocation for local variables in the
> frame, but if you only have the pityful number of registers on an
> x86 processor, this is probably not worth it (it wold be better to
> use them all for the stack).


Even for Forth, which uses the stack much more extensively than the
JVM (e.g., across basic blocks), having more than three registers for
stack items provides very little benefit
<http://www.complang.tuwien.ac.at/papers/ertl%26gregg05.ps.gz>. That
would leave another 4 registers for locals.


However, for the JVM the stack items often don't need a register, as
they are often coming from locals in registers, in memory, or from
immediate values, and the access to them can often be integrated into
the actual instruction. E.g., for the JAVA statement


a=b+c=1;


which is translated to


iload b
iload c
iadd
bipush 1
iadd
istore a


With the register assignment


a=%eax
b=%ebx
c-%ecx


this can be compiled into


lea 1(%ebx,%ecx), %eax


without needing a single register for the stack items involved.


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