Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Integrated Register Allocation and Instruction Scheduling with Constraint Programming
KTH, School of Information and Communication Technology (ICT), Software and Computer systems, SCS. SICS (Swedish Institute of Computer Science) and KTH (Royal Institute of Technology).ORCID iD: 0000-0002-2806-7333
2014 (English)Licentiate thesis, comprehensive summary (Other academic)
Abstract [en]

This dissertation proposes a combinatorial model, program representations, and constraint solving techniques for integrated register allocation and instruction scheduling in compiler back-ends. In contrast to traditional compilers based on heuristics, the proposed approach generates potentially optimal code by considering all trade-offs between interdependent decisions as a single optimization problem.

The combinatorial model is the first to handle a wide array of global register allocation subtasks, including spill code optimization, ultimate coalescing, register packing, and register bank assignment, as well as instruction scheduling for Very Long Instruction Word (VLIW) processors. The model is based on three novel, complementary program representations: Linear Static Single Assignment for global register allocation; copy extension for spilling, basic coalescing, and register bank assignment; and alternative temporaries for spill code optimization and ultimate coalescing. Solving techniques are proposed that exploit the program representation properties for scalability.

The model, program representations, and solving techniques are implemented in Unison, a code generator that delivers potentially optimal code while scaling to medium-size functions. Thorough experiments show that Unison: generates faster code (up to 41% with a mean improvement of 7%) than LLVM (a state-of-the-art compiler) for Hexagon (a challenging VLIW processor), generates code that is competitive with LLVM for MIPS32 (a simpler RISC processor), is robust across different benchmarks such as MediaBench and SPECint 2006, scales up to medium-size functions of up to 1000 instructions, and adapts easily to different optimization criteria.

The contributions of this dissertation are significant. They lead to a combinatorial approach for integrated register allocation and instruction scheduling that is, for the first time, practical (it robustly scales to medium-size functions) and effective (it yields better code than traditional heuristic approaches).

Place, publisher, year, edition, pages
Stockholm, Sweden: KTH Royal Institute of Technology, 2014. , 48 p.
Series
TRITA-ICT-ECS AVH, ISSN 1653-6363 ; 14:13
National Category
Computer Science
Research subject
Computer Science
Identifiers
URN: urn:nbn:se:kth:diva-154599ISBN: 978-91-7595-311-3 (print)OAI: oai:DiVA.org:kth-154599DiVA: diva2:758121
Presentation
2014-11-27, Sal A, Electrum, Kistagången 16, Kista, Stockholm, 14:00 (English)
Opponent
Supervisors
Note

QC 20141117

Available from: 2014-11-17 Created: 2014-10-24 Last updated: 2014-11-17Bibliographically approved
List of papers
1. Survey on Combinatorial Register Allocation and Instruction Scheduling
Open this publication in new window or tab >>Survey on Combinatorial Register Allocation and Instruction Scheduling
2014 (English)Report (Other academic)
Abstract [en]

Register allocation and instruction scheduling are two central compiler back-end problems that are critical for quality. In the last two decades, combinatorial optimization has emerged as an alternative approach to traditional, heuristic algorithms for these problems. Combinatorial approaches are generally slower but more flexible than their heuristic counterparts and have the potential to generate optimal code. This paper surveys existing literature on combinatorial register allocation and instruction scheduling. The survey covers approaches that solve each problem in isolation as well as approaches that integrate both problems. The latter have the potential to generate code that is globally optimal by capturing the trade-off between conflicting register allocation and instruction scheduling decisions.

National Category
Computer Systems
Research subject
Computer Science
Identifiers
urn:nbn:se:kth:diva-154598 (URN)
Funder
Vinnova, VR 621-2011-6229
Note

QC 20141117.

Archived at: arXiv:1409.7628 [cs.PL]

Available from: 2014-10-24 Created: 2014-10-24 Last updated: 2014-11-17Bibliographically approved
2. Constraint-Based Register Allocation and Instruction Scheduling
Open this publication in new window or tab >>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, Published paper (Refereed)
Abstract [en]

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
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 7514
Keyword
Computer programming, Constraint theory, Flocculation, Network components
National Category
Computer Science Computer Systems
Identifiers
urn:nbn:se:kth:diva-104554 (URN)10.1007/978-3-642-33558-7_54 (DOI)2-s2.0-84868266938 (Scopus ID)978-3-642-33557-0 (ISBN)978-3-642-33558-7 (ISBN)
Conference
18th International Conference on Principles and Practice of Constraint Programming, CP 2012; Quebec City, QC; 8 October 2012 through 12 October 2012
Note

QC 20121212

Available from: 2012-11-05 Created: 2012-11-05 Last updated: 2016-04-21Bibliographically approved
3. Combinatorial Spill Code Optimization and Ultimate Coalescing
Open this publication in new window or tab >>Combinatorial Spill Code Optimization and Ultimate Coalescing
2014 (English)In: SIGPLAN notices, ISSN 0362-1340, E-ISSN 1558-1160, Vol. 49, no 5, 23-32 p.Article in journal (Refereed) Published
Abstract [en]

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 4 1 % with a mean improvement of 7 %); possibly generates optimal code (for 2 9 % 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.

Keyword
spill code optimization, ultimate coalescing, combinatorial optimization, register allocation, instruction scheduling
National Category
Computer Systems
Identifiers
urn:nbn:se:kth:diva-154398 (URN)10.1145/2597809.2597815 (DOI)000341937800004 ()2-s2.0-84905660668 (Scopus ID)
Funder
Swedish Research Council, VR 621-2011-6229
Note

QC 20141021

Available from: 2014-10-21 Created: 2014-10-20 Last updated: 2017-12-05Bibliographically approved

Open Access in DiVA

Licentiate Thesis(647 kB)192 downloads
File information
File name FULLTEXT02.pdfFile size 647 kBChecksum SHA-512
54d89ee41097f63423f886148ce23441a794e07f5378124b68b64826a7503a28fe0f41a96e4de8459738efc6740ff7a809db2d5ba84645ca2bd4bc377cf981f1
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Castañeda Lozano, Roberto
By organisation
Software and Computer systems, SCS
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 192 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 1052 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf