|[3 earlier articles]|
|Re: Graph coloring and JIT compilers. email@example.com (Paolo Bonzini) (2006-04-01)|
|Re: Graph coloring and JIT compilers. firstname.lastname@example.org (2006-04-03)|
|Re: Graph coloring and JIT compilers. email@example.com (Richard) (2006-04-03)|
|Re: Graph coloring and JIT compilers. firstname.lastname@example.org (email@example.com) (2006-04-03)|
|Re: Graph coloring and JIT compilers. firstname.lastname@example.org (2006-04-03)|
|Graph coloring and JIT compilers. email@example.com (Inderaj Bains) (2006-04-03)|
|Re: Graph coloring and JIT compilers. firstname.lastname@example.org (2006-04-08)|
|From:||email@example.com (Anton Ertl)|
|Date:||8 Apr 2006 17:09:38 -0400|
|Organization:||Institut fuer Computersprachen, Technische Universitaet Wien|
|Posted-Date:||08 Apr 2006 17:09:38 EDT|
firstname.lastname@example.org (=?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
> 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
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
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
which is translated to
With the register assignment
this can be compiled into
lea 1(%ebx,%ecx), %eax
without needing a single register for the stack items involved.
M. Anton Ertl
Return to the
Search the comp.compilers archives again.