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
Universal Instruction Selection
KTH, School of Information and Communication Technology (ICT), Software and Computer systems, SCS. KTH, School of Electrical Engineering and Computer Science (EECS). RISE SICS.ORCID iD: 0000-0001-6794-6413
2018 (English)Doctoral thesis, monograph (Other academic)
Abstract [en]

In code generation, instruction selection chooses instructions to implement a given program under compilation, global code motion moves computations from one part of the program to another, and block ordering places program blocks in a consecutive sequence. Local instruction selection chooses instructions one program block at a time while global instruction selection does so for the entire function. This dissertation introduces a new approach called universal instruction selection that integrates global instruction selection with global code motion and block ordering. By doing so, it addresses limitations of existing instruction selection techniques that fail to exploit many of the instructions provided by modern processors.

To handle the combinatorial nature of these problems, the approach is based on constraint programming, a combinatorial optimization method. It relies on a novel model that is simpler and more flexible compared to the techniques used in modern compilers and that captures crucial features ignored by other combinatorial approaches. The dissertation also proposes extensions to the model for integrating instruction scheduling and register allocation, two other important problems of code generation.

The model is enabled by a novel, graph-based representation that unifies data and control flow for entire functions. The representation is crucial for integrating instruction selection with global code motion and for modeling sophisticated instructions, whose behavior contains both data and control flow, as graphs.

Through experimental evaluation, universal instruction selection is demonstrated to handle architectures with a rich instruction set and scales up to functions with hundreds of operations. For these functions, it generates code of equal or better quality compared to the state of the art. The dissertation also demonstrates that there is sufficient data parallelism to be exploited through selection of SIMD instructions and that this exploitation benefits from global code motion. With these results, it is argued that constraint programming is a flexible, practical, competitive, and extensible approach for combining global instruction selection, global code motion, and block ordering.

Abstract [sv]

Inom kodgenerering väljer instruktionsselektering (eng. instruction selection) instruktioner för att implementera ett givet program under kompilering, global kodförflyttning (eng. global code motion) flyttar beräkningar från en del av programmet till en annan, och blockläggning (eng. block ordering) placerar programblock i en sekventiell följd. Lokal instruktionsselektering väljer instruktioner ett programblock i taget medan global instruktionsselektering gör så för hela funktionen. Denna avhandling introducerar en ny metod, kallad universell instruktionsselektering, som integrerar global instruktionsselektering med global kodförflyttning och blockläggning. På så vis åtgärdar den begränsningar hos befintliga instruktionsselekteringsmetoder som misslyckas med att utnyttja många av instruktionerna som erbjuds av moderna processorer.

För att hantera den kombinatoriska naturen av dessa problem tillämpas villkorsprogrammering (eng. constraint programming), en teknik för kombinatorisk optimering. Metoden använder en innovativ model som är enklare och mer flexibel jämfört med metoderna som används i moderna kompilatorer och som fångar viktiga särdrag som ignoreras av andra kombinatoriska metoder. Avhandlingen föreslår också utökningar av modellen för att integrera instruktionsschemaläggning (eng. instruction scheduling) och registerallokering (eng. register allocation), två andra viktiga kodgenereringsproblem.

Modellen möjliggörs av en innovativ, grafbaserad representation som förenar data- och kontrollflöde för hela funktioner. Representationen är avgörande för att integrera instruktionsselektering med global kodförflyttning och för att modellera sofistikerade instruktioner, vars beteende omfattar både data- och kontrollflöde, som grafer.

Genom experimentell utvärdering visas att universell instruktionsselektering kan hantera arkitekturer med ett rikt instruktionsset och skalar upp till funktioner med hundratals beräkningar. För dessa funktioner genererar den kod av motsvarande eller bättre kvalitet än den senaste tekniken. Avhandlingen visar också att det finns tillräckligt med dataparallellism att utnyttja genom selektering av SIMD-instruktioner och att denna exploatering gynnas av global kodförflyttning. Med dessa resultat argumenteras för att villkorsprogrammering är en flexibel, praktisk, konkurrenskraftig, och utökningsbar metod för att kombinera global instruktionsselektering, global kodförflyttning, och blockläggning.

Place, publisher, year, edition, pages
KTH Royal Institute of Technology, 2018. , p. 314
Series
TRITA-EECS-AVL ; 2018:11
Keywords [en]
instruction selection, code generation, compilers, constraint programming, combinatorial optimization
National Category
Computer Sciences
Research subject
Information and Communication Technology
Identifiers
URN: urn:nbn:se:kth:diva-223599ISBN: 978-91-7729-683-6 (print)OAI: oai:DiVA.org:kth-223599DiVA, id: diva2:1185339
Public defence
2018-04-06, Sal B, Electrum, Kungliga Tekniska Högskolan, Kistagången 16, Kista, Stockholm, 13:15 (English)
Opponent
Supervisors
Note

QC 20180226

Available from: 2018-02-26 Created: 2018-02-23 Last updated: 2018-04-11Bibliographically approved

Open Access in DiVA

fulltext(1942 kB)163 downloads
File information
File name FULLTEXT03.pdfFile size 1942 kBChecksum SHA-512
2751af6ac89c4bb2713334d8a217317d3f4bf979b041098716b8eddbea77daa63623084ed206bd1b87d8b910e912a883e95b832d68357de7d187dc850da7c6cb
Type fulltextMimetype application/pdf
fulltext(91 kB)11 downloads
File information
File name FULLTEXT04.pdfFile size 91 kBChecksum SHA-512
2c1b38ee67e929f75e077c33900a4ebe68d38835a175769af20a5629f3710c5eceb136cbb214abf198f8fb251d78959ed6e074162642b2812720434ef1e9d7ff
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Hjort Blindell, Gabriel
By organisation
Software and Computer systems, SCSSchool of Electrical Engineering and Computer Science (EECS)
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 390 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: 3030 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