Re: Graph coloring and JIT compilers.

"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

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