Combinatorial Spill Code Optimization and Ultimate Coalescing

Roberto Castañeda Lozano; Mats Carlsson; Gabriel Hjort Blindell; Christian Schulte

doi:10.1145/2597809.2597815

Combinatorial Spill Code Optimization and Ultimate Coalescing

Roberto Castañeda Lozano, Mats Carlsson, Gabriel Hjort Blindell, Christian Schulte

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

Abstract / Description of output

This paper presents a novel combinatorial model that integrates global register allocation based on ultimate coalescing, spill code optimization, register packing, and multiple register banks with instruction scheduling (including VLIW). The model exploits alternative temporaries that hold the same value as a new concept for ultimate coalescing and spill code optimization.

The paper presents Unison as a code generator based on the model and advanced solving techniques using constraint programming. Thorough experiments using MediaBench and a processor (Hexagon) that are typical for embedded systems demonstrate that Unison: is robust and scalable; generates faster code than LLVM (up to 41% with a mean improvement of 7%); possibly generates optimal code (for 29% of the experiments); effortlessly supports different optimization criteria (code size on par with LLVM).

Unison is significant as it addresses the same aspects as traditional code generation algorithms, yet is based on a simple integrated model and robustly can generate optimal code.

Original language	English
Title of host publication	Proceedings of the 2014 SIGPLAN/SIGBED Conference on Languages, Compilers and Tools for Embedded Systems
Place of Publication	New York, NY, USA
Publisher	Association for Computing Machinery, Inc
Pages	23–32
Number of pages	10
ISBN (Print)	9781450328777
DOIs	https://doi.org/10.1145/2597809.2597815
Publication status	Published - 13 Jun 2014
Event	2014 SIGPLAN/SIGBED Conference on Languages, Compilers and Tools for Embedded Systems - Edinburgh, United Kingdom Duration: 12 Jun 2014 → 13 Jun 2014 http://www.ittc.ku.edu/lctes14/

Conference

Conference	2014 SIGPLAN/SIGBED Conference on Languages, Compilers and Tools for Embedded Systems
Abbreviated title	LCTES 2014
Country/Territory	United Kingdom
City	Edinburgh
Period	12/06/14 → 13/06/14
Internet address	http://www.ittc.ku.edu/lctes14/

Keywords / Materials (for Non-textual outputs)

spill code optimization
register allocation
ultimate coalescing
instruction scheduling
combinatorial optimization

Access to Document

10.1145/2597809.2597815Licence: All Rights Reserved

https://dl.acm.org/doi/10.1145/2597809.2597815Licence: All Rights Reserved

Cite this

@inproceedings{0f689b67978c4cdcb744ee326ee10bfd,

title = "Combinatorial Spill Code Optimization and Ultimate Coalescing",

abstract = "This paper presents a novel combinatorial model that integrates global register allocation based on ultimate coalescing, spill code optimization, register packing, and multiple register banks with instruction scheduling (including VLIW). The model exploits alternative temporaries that hold the same value as a new concept for ultimate coalescing and spill code optimization.The paper presents Unison as a code generator based on the model and advanced solving techniques using constraint programming. Thorough experiments using MediaBench and a processor (Hexagon) that are typical for embedded systems demonstrate that Unison: is robust and scalable; generates faster code than LLVM (up to 41% with a mean improvement of 7%); possibly generates optimal code (for 29% of the experiments); effortlessly supports different optimization criteria (code size on par with LLVM).Unison is significant as it addresses the same aspects as traditional code generation algorithms, yet is based on a simple integrated model and robustly can generate optimal code.",

keywords = "spill code optimization, register allocation, ultimate coalescing, instruction scheduling, combinatorial optimization",

author = "{Casta{\~n}eda Lozano}, Roberto and Mats Carlsson and {Hjort Blindell}, Gabriel and Christian Schulte",

year = "2014",

month = jun,

day = "13",

doi = "10.1145/2597809.2597815",

language = "English",

isbn = "9781450328777",

pages = "23–32",

booktitle = "Proceedings of the 2014 SIGPLAN/SIGBED Conference on Languages, Compilers and Tools for Embedded Systems",

publisher = "Association for Computing Machinery, Inc",

note = "2014 SIGPLAN/SIGBED Conference on Languages, Compilers and Tools for Embedded Systems, LCTES 2014 ; Conference date: 12-06-2014 Through 13-06-2014",

url = "http://www.ittc.ku.edu/lctes14/",

}

Castañeda Lozano, R, Carlsson, M, Hjort Blindell, G & Schulte, C 2014, Combinatorial Spill Code Optimization and Ultimate Coalescing. in Proceedings of the 2014 SIGPLAN/SIGBED Conference on Languages, Compilers and Tools for Embedded Systems. Association for Computing Machinery, Inc, New York, NY, USA, pp. 23–32, 2014 SIGPLAN/SIGBED Conference on Languages, Compilers and Tools for Embedded Systems, Edinburgh, United Kingdom, 12/06/14. https://doi.org/10.1145/2597809.2597815

Combinatorial Spill Code Optimization and Ultimate Coalescing. / Castañeda Lozano, Roberto; Carlsson, Mats; Hjort Blindell, Gabriel et al.
Proceedings of the 2014 SIGPLAN/SIGBED Conference on Languages, Compilers and Tools for Embedded Systems. New York, NY, USA: Association for Computing Machinery, Inc, 2014. p. 23–32.

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

TY - GEN

T1 - Combinatorial Spill Code Optimization and Ultimate Coalescing

AU - Castañeda Lozano, Roberto

AU - Carlsson, Mats

AU - Hjort Blindell, Gabriel

AU - Schulte, Christian

PY - 2014/6/13

Y1 - 2014/6/13

N2 - This paper presents a novel combinatorial model that integrates global register allocation based on ultimate coalescing, spill code optimization, register packing, and multiple register banks with instruction scheduling (including VLIW). The model exploits alternative temporaries that hold the same value as a new concept for ultimate coalescing and spill code optimization.The paper presents Unison as a code generator based on the model and advanced solving techniques using constraint programming. Thorough experiments using MediaBench and a processor (Hexagon) that are typical for embedded systems demonstrate that Unison: is robust and scalable; generates faster code than LLVM (up to 41% with a mean improvement of 7%); possibly generates optimal code (for 29% of the experiments); effortlessly supports different optimization criteria (code size on par with LLVM).Unison is significant as it addresses the same aspects as traditional code generation algorithms, yet is based on a simple integrated model and robustly can generate optimal code.

AB - This paper presents a novel combinatorial model that integrates global register allocation based on ultimate coalescing, spill code optimization, register packing, and multiple register banks with instruction scheduling (including VLIW). The model exploits alternative temporaries that hold the same value as a new concept for ultimate coalescing and spill code optimization.The paper presents Unison as a code generator based on the model and advanced solving techniques using constraint programming. Thorough experiments using MediaBench and a processor (Hexagon) that are typical for embedded systems demonstrate that Unison: is robust and scalable; generates faster code than LLVM (up to 41% with a mean improvement of 7%); possibly generates optimal code (for 29% of the experiments); effortlessly supports different optimization criteria (code size on par with LLVM).Unison is significant as it addresses the same aspects as traditional code generation algorithms, yet is based on a simple integrated model and robustly can generate optimal code.

KW - spill code optimization

KW - register allocation

KW - ultimate coalescing

KW - instruction scheduling

KW - combinatorial optimization

U2 - 10.1145/2597809.2597815

DO - 10.1145/2597809.2597815

M3 - Conference contribution

SN - 9781450328777

SP - 23

EP - 32

BT - Proceedings of the 2014 SIGPLAN/SIGBED Conference on Languages, Compilers and Tools for Embedded Systems

PB - Association for Computing Machinery, Inc

CY - New York, NY, USA

T2 - 2014 SIGPLAN/SIGBED Conference on Languages, Compilers and Tools for Embedded Systems

Y2 - 12 June 2014 through 13 June 2014

ER -

Combinatorial Spill Code Optimization and Ultimate Coalescing

Abstract / Description of output

Conference

Keywords / Materials (for Non-textual outputs)

Access to Document

Fingerprint

Cite this