Paper Info
Title
Constraint-Based register allocation and instruction scheduling
Abstract
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.
Year
Venue
Keywords
2012
CP'12 Proceedings of the 18th international conference on Principles and Practice of Constraint Programming
constraint-based register allocation,high-level model,compiler construction,global register allocation,constraint programming,new model,constraint model,code quality,code generation,state-of-the-art compiler infrastructure,instruction scheduling,high-quality code generator,computer science
Field
DocType
Volume
Dead code elimination,Mathematical optimization,Programming language,Instruction scheduling,Register allocation,Loop-invariant code motion,Computer science,Constraint programming,Parallel computing,Code generation,Compiler,Compiler construction
Conference
abs/1804.02452
Citations 
PageRank 
References 
7
0.50
26
Authors
4
Name
Order
Citations
PageRank
Roberto Castañeda Lozano1223.45
Mats Carlsson297579.24
Frej Drejhammar3142.03
Christian Schulte438733.89