Adding Static Single Assignment Form and a Graph Coloring Register Allocator to the Java Hotspot Client Compiler

Hanspeter Mössenböck
Johannes Kepler University Linz
Institute for Practical Computer Science
Altenbergerstraße 69, A-4040 Linz
moessenboeck@ssw.uni-linz.ac.at

Abstract

This report describes the work that I performed during my sabbatical in the Java Hotspotª group at Sun Microsystems in Cupertino between June and August 2000. The goal was to find out how much effort it was to augment the Java Hotspotª Client Compiler with Static Single Assignment (SSA) Form and with a Graph Coloring Register Allocator. SSA form not only simplifies register allocation but also helps performing optimi-zations such as common subexpression elimination, loop-invariant code motion or instruction scheduling.

I implemented a prototype compiler that creates a control flow graph (CFG), transforms the intermediate representation (IR) of the program into SSA form and does register allocation with graph coloring. The code generator is still missing. On the basis of this work, the Hotspot team should be able to decide whether or not it is worth adding SSA form and register allocation to the client compiler.

Throughout this report the term current compiler refers to the Hotspotª Client Compiler [GrMi00] at the time when my work began. The term new compiler refers to our prototype compiler.

Technical Report 15, Institute for Practical Computer Science, Johannes Kepler University Linz, Austria, November 2000.
You can download the full technical report in PDF.