| [buchwald11cc] | Sebastian Buchwald, Andreas Zwinkau, Thomas Bersch, SSA-Based Register Allocation with PBQP, Knoop, Jens (Ed.), Compiler Construction, pp. 42--61, Springer Berlin / Heidelberg, 2011.
10.1007/978-3-642-19861-8_4 |
Abstract
Recent research shows that maintaining SSA form allows to split register
allocation into separate phases: spilling, register assignment and
copy coalescing. After spilling, register assignment can be done
in polynomial time, but copy coalescing is NP-complete. In this paper
we present an assignment approach with integrated copy coalescing,
which maps the problem to the Partitioned Boolean Quadratic Problem
(PBQP). Compared to the state-of-the-art recoloring approach, this
reduces the relative number of swap and copy instructions for the
SPEC CINT2000 benchmark to 99.6% and 95.2%, respectively, while taking
19% less time for assignment and coalescing.
Download
Original article available at springerlink.com.
BibTeX
Authors at the institute
Projects
