Constraint-Based Register Allocation and Instruction Scheduling
2012 (English)In: Principles and Practice of Constraint Programming: 18th International Conference, CP 2012, Québec City, QC, Canada, October 8-12, 2012. Proceedings / [ed] Michela Milano, Springer, 2012, 750-766 p.Conference paper (Refereed)
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.
Place, publisher, year, edition, pages
Springer, 2012. 750-766 p.
, Lecture Notes in Computer Science, ISSN 0302-9743 ; 7514
Computer programming, Constraint theory, Flocculation, Network components
Computer Science Computer Systems
IdentifiersURN: urn:nbn:se:kth:diva-104554DOI: 10.1007/978-3-642-33558-7_54ScopusID: 2-s2.0-84868266938ISBN: 978-3-642-33557-0 (print)ISBN: 978-3-642-33558-7 (online)OAI: oai:DiVA.org:kth-104554DiVA: diva2:565033
18th International Conference on Principles and Practice of Constraint Programming, CP 2012; Quebec City, QC; 8 October 2012 through 12 October 2012
QC 201212122012-11-052012-11-052016-04-21Bibliographically approved