Constraint-based Register Allocation and Instruction Scheduling
Roberto Castañeda Lozano, Mats Carlsson, Frej Drejhammar, Christian Schulte.
This paper introduces a constraint model and solving techniques for code generation in a compiler back-end. It contributes a new model for global register allocation that combines several advanced aspects: multiple register banks (subsuming spilling to memory), coalescing, and packing. The model is extended to include instruction scheduling and bundling. The paper introduces a decomposition scheme exploiting the underlying program structure and exhibiting robust behavior for functions with thousands of instructions. Evaluation shows that code quality is on par with LLVM, a state-of-the-art compiler infrastructure.
The paper makes important contributions to the applicability of constraint programming as well as compiler construction: essential concepts are unified in a high-level model that can be solved by readily available modern solvers. This is a significant step towards basing code generation entirely on a high-level model and by this facilitates the construction of correct, simple, flexible, robust, and high-quality code generators.
In: Michela Milano, editor, Eighteenth International Conference on Principles and Practice of Constraint Programming, Québec City, Canada, volume 7514 of Lecture Notes in Computer Science, pages 750-766. Springer-Verlag, October, 2012. DOI 10.1007/978-3-642-33558-7_54.
Copyright Springer-Verlag, the original publication is available at www.springerlink.com