Re: Graph coloring and JIT compilers.

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.


Aziz,,,


[1] Available online at:
          http://www.oberon.ethz.ch/WirthPubl/CBEAll.pdf
          The linking page (containing other books) is:
          http://www.oberon.ethz.ch/books.html
[2] Register Allocation Using Lazy Saves, Eager Restores, and Greedy
          Shuffling:
          http://citeseer.ist.psu.edu/burger95register.html

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