In this work we present a new heuristic for PBQP which significantly improves the quality of its register allocations and
extends the range of viable target architectures. We also introduce a new branch-and-bound technique for PBQP that is able
to find optimal register allocations.
We evaluate each of these methods, as well as a state of the art graph colouring method, using SPEC2000 and IA-32 as a testbed.
Spill costs are used as a metric for comparison. We provide experimental evidence that our new heuristic allows PBQP to remain
effective even for relatively regular architectures such as IA-32, generating results equal to those of a start-of-the-art
graph colouring technique. Our method is shown to run 3–4 times slower than graph colouring, however it supports a wide range
of irregularities.
Using our branch-and-bound solver for PBQP we were able to solve 97.4% of the functions in SPEC2000 optimally. These results
are used as a yardstick to show that both PBQP and graph colouring produce results which are very close to optimal.
This work has been supported by the ARC Discovery Project Grant “Compilation Techniques for Embedded Systems” under Contract
DP 0560190.