Nearly optimal register allocation with PBQP
L Hames, B Scholz - Joint Modular Languages Conference, 2006 - Springer
L Hames, B Scholz
Joint Modular Languages Conference, 2006•SpringerIn 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 …
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 …
Abstract
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.
Springer
以上显示的是最相近的搜索结果。 查看全部搜索结果