Register Allocation on SSA form for Java Just-in-Time Compilation
Register allocation is one of the most important, but also the most expensive compiler optimizations. This is especially critical for Java just-in-time compilation where compilation time adds to run time, and led to different register allocation algorithms that trade code quality for compilation time. Static single assignment (SSA) form is a type of intermediate representation that simplifies many compiler optimizations. However, only recently it was discovered that SSA form is also beneficial for register allocation. The two main register allocation algorithms, graph coloring and linear scan, are now available in versions that operate directly on SSA form. This talk presents the details of the changes that are necessary for this, and explains the benefits gained by SSA form. Our implementation for the Java HotSpot VM shows that register allocation gets both faster and simpler.