Re: Graph coloring and JIT compilers.

Abdulaziz Ghuloum <>
1 Apr 2006 20:50:58 -0500

          From comp.compilers

Related articles
Graph coloring and JIT compilers. (Poseidon13) (2006-03-29)
Re: Graph coloring and JIT compilers. (Diego Novillo) (2006-04-01)
Re: Graph coloring and JIT compilers. (Abdulaziz Ghuloum) (2006-04-01)
Re: Graph coloring and JIT compilers. (Paolo Bonzini) (2006-04-01)
Re: Graph coloring and JIT compilers. (2006-04-03)
Re: Graph coloring and JIT compilers. (Richard) (2006-04-03)
Re: Graph coloring and JIT compilers. ( (2006-04-03)
Re: Graph coloring and JIT compilers. (2006-04-03)
Graph coloring and JIT compilers. (Inderaj Bains) (2006-04-03)
[1 later articles]
| List of all articles for this month |

From: Abdulaziz Ghuloum <>
Newsgroups: comp.compilers
Date: 1 Apr 2006 20:50:58 -0500
Organization: Indiana University
References: 06-03-097
Keywords: optimize, Java
Posted-Date: 01 Apr 2006 20:50:58 EST

Poseidon13 wrote:

> 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"[1] for a one-pass compiler for Oberon that
does not perform register-allocation. Also refer to [2] for a linear
register allocator that is used in a production-quality compiler.


[1] Available online at:

          The linking page (containing other books) is:

[2] Register Allocation Using Lazy Saves, Eager Restores, and Greedy

Post a followup to this message

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