Re: Graph coloring and JIT compilers.

Abdulaziz Ghuloum <aghuloum@cs.indiana.edu>
1 Apr 2006 20:50:58 -0500

          From comp.compilers

Related articles
Graph coloring and JIT compilers. julian_solo13@hotmail.com (Poseidon13) (2006-03-29)
Re: Graph coloring and JIT compilers. dnovillo@redhat.com (Diego Novillo) (2006-04-01)
Re: Graph coloring and JIT compilers. aghuloum@cs.indiana.edu (Abdulaziz Ghuloum) (2006-04-01)
Re: Graph coloring and JIT compilers. bonzini@gnu.org (Paolo Bonzini) (2006-04-01)
Re: Graph coloring and JIT compilers. torbenm@app-4.diku.dk (2006-04-03)
Re: Graph coloring and JIT compilers. richard@imagecraft.com (Richard) (2006-04-03)
Re: Graph coloring and JIT compilers. oliverhunt@gmail.com (oliverhunt@gmail.com) (2006-04-03)
Re: Graph coloring and JIT compilers. anton@mips.complang.tuwien.ac.at (2006-04-03)
Graph coloring and JIT compilers. inderaj@gmail.com (Inderaj Bains) (2006-04-03)
[1 later articles]
| List of all articles for this month |

From: Abdulaziz Ghuloum <aghuloum@cs.indiana.edu>
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.


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


Post a followup to this message

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