Thumbnail
Access Restriction
Subscribed

Author Brandner, Florian ♦ Kadlec, Albrecht ♦ Scholz, Bernhard ♦ Ebner, Dietmar ♦ Krall, Andreas ♦ Wiedermann, Peter
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data
Subject Keyword Code generation ♦ Compiler ♦ Pbqp ♦ Instruction selection
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.
Description Affiliation: University of Sydney, Sydney, Australia (Scholz, Bernhard) || Vienna University of Technology, Vienna, Austria (Ebner, Dietmar; Brandner, Florian; Krall, Andreas; Wiedermann, Peter; Kadlec, Albrecht)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1983-05-01
Publisher Place New York
Journal ACM SIGPLAN Notices (SIGP)
Volume Number 43
Issue Number 7
Page Count 10
Starting Page 31
Ending Page 40


Open content in new tab

   Open content in new tab
Source: ACM Digital Library