Constraint-based Register Allocation and Instruction Scheduling

Castañeda Lozano, Roberto and Carlsson, Mats and Drejhammar, Frej and Schulte, Christian (2012) Constraint-based Register Allocation and Instruction Scheduling. In: Eighteenth International Conference on Principles and Practice of Constraint Programming, 8-12 Oct 2012, Québec City, Canada.

This is the latest version of this item.

Full text not available from this repository.


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.

Item Type:Conference or Workshop Item (Paper)
ID Code:5542
Deposited By:Roberto Castañeda
Deposited On:12 Aug 2013 12:52
Last Modified:12 Aug 2013 12:52

Available Versions of this Item

Repository Staff Only: item control page