|Graph coloring and JIT compilers. email@example.com (Poseidon13) (2006-03-29)|
|Re: Graph coloring and JIT compilers. firstname.lastname@example.org (Diego Novillo) (2006-04-01)|
|Re: Graph coloring and JIT compilers. email@example.com (Abdulaziz Ghuloum) (2006-04-01)|
|Re: Graph coloring and JIT compilers. firstname.lastname@example.org (Paolo Bonzini) (2006-04-01)|
|Re: Graph coloring and JIT compilers. email@example.com (2006-04-03)|
|Re: Graph coloring and JIT compilers. firstname.lastname@example.org (Richard) (2006-04-03)|
|Re: Graph coloring and JIT compilers. email@example.com (firstname.lastname@example.org) (2006-04-03)|
|Re: Graph coloring and JIT compilers. email@example.com (2006-04-03)|
|Graph coloring and JIT compilers. firstname.lastname@example.org (Inderaj Bains) (2006-04-03)|
|Re: Graph coloring and JIT compilers. email@example.com (2006-04-08)|
|Date:||3 Apr 2006 01:11:12 -0400|
|Organization:||Department of Computer Science, University of Copenhagen|
|Posted-Date:||03 Apr 2006 01:11:12 EDT|
"Poseidon13" <firstname.lastname@example.org> writes:
> I am a second year computing student studying at
> Imperial College London, whose exams are dangerously approaching.
> I've been revising compilers, one of my favorites courses and tried
> out a past paper, however I am somewhat stuck on a question, here it
> comes :
> In a Java Just-In-Time compiler(JIT) it is essential to minimise the time
> spent on code generation. Is graph coloring a good approach to register
> allocation in a JIT?
> I would say no because although graph colouring is an efficient technique it
> does however take a rather long time to perform the register allocation.
> I don't know what else I could say ( and I'm pretty sure the examiner would
> be expecting much more:( ).
Your answer is basically correct, but there is (as you suspect) more
- 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. 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. 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).
- Some people have suggested using linear-scan register allocation
for JIT (Massimiliano Poletto and Vivek Sarkar. Linear Scan
Register Allocation. ACM TOPLAS, 1999). While this is faster than
graph-colouring, I'm not convinced you gain much, as you still need
to do liveness analysis, which is often the most time-consuming
part of register allocation.
- In the JVM, there is no explicit liveness information, so any kind
of register allocation that requires liveness will be slow. Since
liveness is independent of the target architecture, it would make
sense to add liveness information to a VM intended for JIT, e.g.,
in the form of "last use" annotations on variable reads, so
register allocation (e.g., by linear scan) could be done quickly.
Return to the
Search the comp.compilers archives again.