|Graph coloring and JIT compilers. firstname.lastname@example.org (Poseidon13) (2006-03-29)|
|Re: Graph coloring and JIT compilers. email@example.com (Diego Novillo) (2006-04-01)|
|Re: Graph coloring and JIT compilers. firstname.lastname@example.org (Abdulaziz Ghuloum) (2006-04-01)|
|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)|
|[1 later articles]|
|From:||Abdulaziz Ghuloum <firstname.lastname@example.org>|
|Date:||1 Apr 2006 20:50:58 -0500|
|Posted-Date:||01 Apr 2006 20:50:58 EST|
> Good evening everyone!
> It took me some time to figure out how to register to a Newsgroup but
> now I'm here:). 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:( ).
> Could you please help me out for this question?
> Thank you in advance.
The answer is yes. You can use the graph-coloring register allocator
for jit. I have been using it in my Scheme compiler and can compile
medium-size programs (some 26,000 lines of code that uses macros, which
boils to around 100,000 of C code) in acceptable compile times (around
10 secs on a 1.6GHz G5) and this includes reading the program, macro
expansion (around 4 secs), some 10 passes for the front-end, some 20
passes in the backend including register-allocation, and assembly of
the machine-code in-core. The largest procedure I have compiled had
around 16,000 variables and the interference graph had some 1/4 million
edges (meaning it took several iterations to color).
Now that's research; as for your exam, I would say that the expected
answer is no. Graph-coloring, *as presented in compiler books*, is
inefficient for interactive development. Refer to Niklaus Wirth's
"Compiler Construction" for a one-pass compiler for Oberon that
does not perform register-allocation. Also refer to  for a linear
register allocator that is used in a production-quality compiler.
 Available online at:
The linking page (containing other books) is:
 Register Allocation Using Lazy Saves, Eager Restores, and Greedy
Return to the
Search the comp.compilers archives again.