Home > Archive > Compilers > April 2006 > Graph coloring and JIT compilers.
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
Graph coloring and JIT compilers.
|
|
| Poseidon13 2006-03-29, 7:04 pm |
| 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.
| |
| Abdulaziz Ghuloum 2006-04-01, 10:03 pm |
| 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
| |
| Diego Novillo 2006-04-01, 10:03 pm |
| On 03/29/06 18:56, Poseidon13 wrote:
> 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?
The short answer seems to be yes. You may be interested in
Tailoring Graph-Coloring Register Allocation for Runtime Compilation
K. D. Cooper and A. Dasgupta
Proceedings of the 2006 Symposium on Code Generation and Optimization (CGO)
Not sure whether the paper is available online, though.
| |
| Paolo Bonzini 2006-04-01, 10:03 pm |
| > In a Java Just-In-Time compiler(JIT) it is essential to minimise the time
> spent on code generation.
The hypothesis is not even completely correct -- it depends very much
on the underlying systems (think of multicore chips), on how long the
program being JIT-compiled will run, on whether most of the execution
takes place in some hot spots of the program, and so on.
Paolo
| |
| Torben Ęgidius Mogensen 2006-04-03, 4:14 am |
| "Poseidon13" <julian_solo13@hotmail.com> 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
to say.
- 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.
Torben
| |
| Richard 2006-04-03, 4:14 am |
| Poseidon13 wrote:
>...
> 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?
>
What is the average time complexity of graph coloring and what is the
worse case? Figure that out and you are on your way in answering the
question. When all else fails, goodle "JIT register allocation" should
give you plenty hit on Linear Scan register allocation.
| |
| oliverhunt@gmail.com 2006-04-03, 4:15 am |
| Well there's also linear scan register allocation, which is meant to be
fairly close (performance wise) to graph colouring (there's a paper at
http://www.research.ibm.com/jalapen...rs/toplas99.pdf though google
should return a number of others).
I haven't personally implemented any form of register allocation as I'm
not writing a JIT copmiler, so can safely be lazy and target higher
level compilers like C/C#/etc that do all that hard work for me :)
Cheers,
Oliver
| |
| Anton Ertl 2006-04-03, 4:15 am |
| "Poseidon13" <julian_solo13@hotmail.com> writes:
> 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.
Well, the Sun HotSpot JIT (don't know whether the server VM, client
VM, or both) uses graph colouring.
Also, at CC a few days ago I heard that the Jikes RVM contains two
JITs; for historical reasons, the faster JIT (that generates slower
code) uses graph colouring, and the slower JIT (that generates faster
code) uses linear scan register allocation.
I guess you can answer the question either way, just use the right
arguments to support your position.
- anton
--
M. Anton Ertl
anton@mips.complang.tuwien.ac.at
http://www.complang.tuwien.ac.at/anton/home.html
| |
| Anton Ertl 2006-04-08, 7:03 pm |
| torbenm@app-4.diku.dk (=?iso-8859-1?q?Torben_=C6gidius_Mogensen?=) writes:
> - 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.
Graph colouring works on a conflict graph. Getting from a stack-based
form to the conflict graph seems a little bit easer to me than from a
named-variable form, because liveness information is explicit in the
stack 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.
Yes, as long as you use the stack only within basic blocks (as is done
most of the time by most compilers that generate JVM code), register
allocation for the stack is trivial; register allocation for variables
in basic blocks (without scheduling) is also easy and does not need
graph colouring or similar stuff.
> 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).
Even for Forth, which uses the stack much more extensively than the
JVM (e.g., across basic blocks), having more than three registers for
stack items provides very little benefit
<http://www.complang.tuwien.ac.at/pa...26gregg05.ps.gz>. That
would leave another 4 registers for locals.
However, for the JVM the stack items often don't need a register, as
they are often coming from locals in registers, in memory, or from
immediate values, and the access to them can often be integrated into
the actual instruction. E.g., for the JAVA statement
a=b+c=1;
which is translated to
iload b
iload c
iadd
bipush 1
iadd
istore a
With the register assignment
a=%eax
b=%ebx
c-%ecx
this can be compiled into
lea 1(%ebx,%ecx), %eax
without needing a single register for the stack items involved.
- anton
--
M. Anton Ertl
anton@mips.complang.tuwien.ac.at
http://www.complang.tuwien.ac.at/anton/home.html
|
|
|
|
|