Constraint-Based Register Allocation and Instruction Scheduling

Roberto Castañeda Lozano; Mats Carlsson; Frej Drejhammar; Christian Schulte

doi:10.1007/978-3-642-33558-7_54

Constraint-Based Register Allocation and Instruction Scheduling

Roberto Castañeda Lozano, Mats Carlsson, Frej Drejhammar, Christian Schulte

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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.

Original language	English
Title of host publication	Principles and Practice of Constraint Programming
Editors	Michela Milano
Place of Publication	Berlin, Heidelberg
Publisher	Springer
Pages	750-766
Number of pages	17
ISBN (Electronic)	978-3-642-33558-7
ISBN (Print)	978-3-642-33557-0
DOIs	https://doi.org/10.1007/978-3-642-33558-7_54
Publication status	Published - 31 Dec 2012
Event	18th International Conference on Principles and Practice of Constraint Programming - Québec City, Canada Duration: 8 Oct 2012 → 12 Oct 2012 Conference number: 18 https://archive.a4cp.org/cp2012/index.php

Publication series

Name	Lecture Notes in Computer Science (LNCS)
Publisher	Springer, Berlin, Heidelberg
Volume	7514
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	18th International Conference on Principles and Practice of Constraint Programming
Abbreviated title	CP 2012
Country/Territory	Canada
City	Québec City
Period	8/10/12 → 12/10/12
Internet address	https://archive.a4cp.org/cp2012/index.php

Keywords / Materials (for Non-textual outputs)

Constraint Programming
Constraint Model
Register Allocation
Code Quality
Instruction Schedule

Access to Document

10.1007/978-3-642-33558-7_54Licence: All Rights Reserved

https://link.springer.com/chapter/10.1007/978-3-642-33558-7_54Licence: All Rights Reserved

Cite this

@inproceedings{afd406cd27a74504afbda8af7862ed18,

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.",

keywords = "Constraint Programming, Constraint Model, Register Allocation, Code Quality, Instruction Schedule",

author = "Lozano, {Roberto Casta{\~n}eda} and Mats Carlsson and Frej Drejhammar and Christian Schulte",

year = "2012",

month = dec,

day = "31",

doi = "10.1007/978-3-642-33558-7_54",

language = "English",

isbn = "978-3-642-33557-0",

series = "Lecture Notes in Computer Science (LNCS)",

publisher = "Springer",

pages = "750--766",

editor = "Michela Milano",

booktitle = "Principles and Practice of Constraint Programming",

address = "United Kingdom",

note = "18th International Conference on Principles and Practice of Constraint Programming , CP 2012 ; Conference date: 08-10-2012 Through 12-10-2012",

url = "https://archive.a4cp.org/cp2012/index.php",

}

Lozano, RC, Carlsson, M, Drejhammar, F & Schulte, C 2012, Constraint-Based Register Allocation and Instruction Scheduling. in M Milano (ed.), Principles and Practice of Constraint Programming . Lecture Notes in Computer Science (LNCS), vol. 7514, Springer, Berlin, Heidelberg, pp. 750-766, 18th International Conference on Principles and Practice of Constraint Programming , Québec City, Quebec, Canada, 8/10/12. https://doi.org/10.1007/978-3-642-33558-7_54

Constraint-Based Register Allocation and Instruction Scheduling. / Lozano, Roberto Castañeda; Carlsson, Mats; Drejhammar, Frej et al.
Principles and Practice of Constraint Programming . ed. / Michela Milano. Berlin, Heidelberg: Springer, 2012. p. 750-766 (Lecture Notes in Computer Science (LNCS); Vol. 7514).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Constraint-Based Register Allocation and Instruction Scheduling

AU - Lozano, Roberto Castañeda

AU - Carlsson, Mats

AU - Drejhammar, Frej

AU - Schulte, Christian

N1 - Conference code: 18

PY - 2012/12/31

Y1 - 2012/12/31

N2 - 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.

AB - 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.

KW - Constraint Programming

KW - Constraint Model

KW - Register Allocation

KW - Code Quality

KW - Instruction Schedule

U2 - 10.1007/978-3-642-33558-7_54

DO - 10.1007/978-3-642-33558-7_54

M3 - Conference contribution

SN - 978-3-642-33557-0

T3 - Lecture Notes in Computer Science (LNCS)

SP - 750

EP - 766

BT - Principles and Practice of Constraint Programming

A2 - Milano, Michela

PB - Springer

CY - Berlin, Heidelberg

T2 - 18th International Conference on Principles and Practice of Constraint Programming

Y2 - 8 October 2012 through 12 October 2012

ER -

Constraint-Based Register Allocation and Instruction Scheduling

Abstract

Publication series

Conference

Keywords / Materials (for Non-textual outputs)

Access to Document

Fingerprint

Cite this