Re: Graph coloring and JIT compilers. (Anton Ertl)
8 Apr 2006 17:09:38 -0400

          From comp.compilers

Related articles
[3 earlier articles]
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)
Re: Graph coloring and JIT compilers. (2006-04-08)
| List of all articles for this month |

From: (Anton Ertl)
Newsgroups: comp.compilers
Date: 8 Apr 2006 17:09:38 -0400
Organization: Institut fuer Computersprachen, Technische Universitaet Wien
References: 06-03-097 06-04-006
Keywords: optimize, Java
Posted-Date: 08 Apr 2006 17:09:38 EDT (=?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
<>. 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


which is translated to

iload b
iload c
bipush 1
istore a

With the register assignment


this can be compiled into

lea 1(%ebx,%ecx), %eax

without needing a single register for the stack items involved.

- anton
M. Anton Ertl

Post a followup to this message

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