Generalized Instruction Selection using SSA-Graphs

Dietmar Ebner, Florian Brandner, Bernhard Scholz, Andreas Krall, Peter Wiedermann, Albrecht Kadlec

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

Abstract

Instruction selection is a well-studied compiler phase that translates the compiler's intermediate representation of programs to a sequence of target-dependent machine instructions optimizing for various compiler objectives (e.g. speed and space). Most existing instruction selection techniques are limited to the scope of a single statement or a basic block and cannot cope with irregular instruction sets that are frequently found in embedded systems. We consider an optimal technique for instruction selection that uses Static Single Assignment (SSA) graphs as an intermediate representation of programs and employs the Partitioned Boolean Quadratic Problem (PBQP) for finding an optimal instruction selection. While existing approaches are limited to instruction Patterns that can be expressed in a simple tree structure, we consider complex patterns producing multiple results at the same time including pre/post increment addressing modes, div-mod instructions, and SIMD extensions frequently found in embedded systems. Although both instruction selection on SSA-graphs and PBQP are known to be NP-complete, the problem can be solved efficiently-even for very large instances. Our approach has been implemented in LLVM for an embedded ARMv5 architecture. Extensive experiments show speedups of up to 57% on typical DSP kernels and up to 10% on SPECINT 2000 and MiBench benchmarks. All of the test programs could be compiled within less than half a minute using a heuristic PBQP solver that solves 99.83% of all instances optimally.
Keyword: Compiler,PBQP,Code Generation,COMPUTER,FORM,CODE GENERATION,Instruction Selection
Original languageEnglish
Title of host publicationLCTES'08: PROCEEDINGS OF THE 2008 ACM SIGPLAN-SIGBED CONFERENCE ON LANGUAGES, COMPILERS, AND TOOLS FOR EMBEDDED SYSTEMS
PublisherASSOC COMPUTING MACHINERY
Publication date2008
Pages31-40
ISBN (Print)978-1-60558-104-0
DOIs
Publication statusPublished - 2008
Externally publishedYes
EventConference on Languages, Compilers and Tools for Embedded Systems -
Duration: 1 Jan 2008 → …

Conference

ConferenceConference on Languages, Compilers and Tools for Embedded Systems
Period01/01/2008 → …

Cite this

Ebner, D., Brandner, F., Scholz, B., Krall, A., Wiedermann, P., & Kadlec, A. (2008). Generalized Instruction Selection using SSA-Graphs. In LCTES'08: PROCEEDINGS OF THE 2008 ACM SIGPLAN-SIGBED CONFERENCE ON LANGUAGES, COMPILERS, AND TOOLS FOR EMBEDDED SYSTEMS (pp. 31-40). ASSOC COMPUTING MACHINERY. https://doi.org/10.1145/1375657.1375663