Rajkishore Barik, Register Allocation using Bipartite Liveness Graphs

Register Allocation continues to be a topic of active research to cater to the needs of new software and hardware trends. The major categories of existing research on register allocation techniques include Graph Coloring, Linear Scan, Chordal Graphs and Puzzle Solving. Due to the increased use of dynamic compilation in modern software, Linear Scan register allocation is the preferred approach for virtual machines and managed runtimes because it has the lowest space and time compilation overhead among the four categories. However, Linear Scan is known to lag other approaches in runtime performance.

In this talk we present a novel approach to register allocation that builds on the foundations of Linear Scan (thereby taking advantage of compile time and space efficiencies), while delivering runtime performance superior to Linear Scan. In our approach, we separate the allocation and assignment phases. The allocation phase is modeled as an optimization problem on Bipartite Liveness Graphs (BLG's). In the assignment phase, we focus on reducing the number of spill instructions by using register-to-register move and exchange instructions wherever possible to maximize the use of registers. We model register assignment as a second optimization problem, that includes register moves, exchanges, coalescing as well as register class constraints, and provide a heuristic solution to this problem as well. A prototype implementation of our BLG register allocation phase combined with the constrained assignment in Jikes RVM demonstrates runtime performances improvements of up to 3.52x relative to Linear Scan on an x86 processor.