research-article

Generalized instruction selection using SSA-graphs

Authors:

Florian Brandner,

Bernhard Scholz,

Peter Wiedermann,

Albrecht KadlecAuthors Info & Claims

LCTES '08: Proceedings of the 2008 ACM SIGPLAN-SIGBED conference on Languages, compilers, and tools for embedded systems

Pages 31 - 40

https://doi.org/10.1145/1375657.1375663

Published: 12 June 2008 Publication History

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.

References

[1]

Warren P. Adams and Richard J. Forrester. A simple recipe for concise mixed 0-1 linearizations. Oper. Res. Lett., 33(1):55--61, 2005.

Digital Library

[2]

A. V. Aho and S. C. Johnson. Optimal code generation for expression trees. J. ACM, 23(3):488--501, 1976.

Digital Library

[3]

A. Balachandran, D. M. Dhamdhere, and S. Biswas. Efficient retargetable code generation using bottom-up tree pattern matching. Computer Languages, 15(3):127--140, 1990.

Digital Library

[4]

Ron Cytron, Jeanne Ferrante, Barry K. Rosen, Mark N. Wegman, and F. Kenneth Zadeck. Efficiently Computing Static Single Assignment Form and the Control Dependence Graph. ACM Transactions on Programming Languages and Systems, 13(4):451--490, October 1991.

Digital Library

[5]

João Dias and Norman Ramsey. Converting intermediate code to assembly code using declarative machine descriptions. In Alan Mycroft and Andreas Zeller, editors, CC, volume 3923 of Lecture Notes in Computer Science, pages 217--231. Springer, 2006.

Digital Library

[6]

Erik Eckstein. Code Optimization for Digital Signal Processors. PhD Thesis. TU Wien, November 2003.

[7]

Erik Eckstein, Oliver König, and Bernhard Scholz. Code Instruction Selection Based on SSA-Graphs. In Andreas Krall, editor, SCOPES, volume 2826 of Lecture Notes in Computer Science, pages 49--65. Springer, 2003.

[8]

M. Anton Ertl. Optimal Code Selection in DAGs. In Principles of Programming Languages (POPL '99), 1999.

Digital Library

[9]

M. Anton Ertl, Kevin Casey, and David Gregg. Fast and flexible instruction selection with on-demand tree-parsing automata. In PLDI '06: Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, pages 52--60, New York, NY, USA, 2006. ACM Press.

Digital Library

[10]

Robert W. Floyd. Algorithm 97: Shortest path. Commun. ACM, 5(6):345, 1962.

Digital Library

[11]

C. Fraser, R. Henry, and T. Proebsting. BURG - Fast Optimal Instruction Selection and Tree Parsing. ACM SIGPLAN Notices, 27(4):68--76, April 1992.

Digital Library

[12]

Christopher W. Fraser, David R. Hanson, and Todd A. Proebsting. Engineering a simple, efficient code-generator generator. ACM Letters on Programming Languages and Systems, 1(3):213--226, September 1992.

Digital Library

[13]

Michael P. Gerlek, Eric Stoltz, and Michael Wolfe. Beyond Induction Variables: Detecting and Classifying Sequences Using a Demand-Driven SSA Form. ACM Transactions on Programming Languages and Systems, 17(1):85--122, 1995.

Digital Library

[14]

J. Guo, T. Limberg, E. Matus, B. Mennenga, R. Klemm, and G. Fettweis. Code generation for STA architecture. In Proc. of the 12th European Conference on Parallel Computing (Euro-Par'06). Springer LNCS, 2006.

Digital Library

[15]

Lang Hames and Bernhard Scholz. Nearly optimal register allocation with PBQP. In David E. Lightfoot and Clemens A. Szyperski, editors, JMLC, volume 4228 of Lecture Notes in Computer Science, pages 346--361. Springer, 2006.

Digital Library

[16]

Hannes Jakschitsch. "Befehlsauswahl auf SSA-Graphen". Master's thesis, Fakultät für Informatik, Universität Karlsruhe (TH),Germany, 2004.

[17]

SPEC2000 Website. http://www.spec.org.

[18]

Chris Lattner and Vikram S. Adve. LLVM: A compilation framework for lifelong program analysis & transformation. In Code Generation and Optimization, CGO 2004, pages 75--88, Palo Alto, CA, March 2004. IEEE Computer Society.

Digital Library

[19]

Rainer Leupers and Steven Bashford. Graph-based code selection techniques for embedded processors. ACM Transactions on Design Automation of Electronic Systems., 5(4):794--814, 2000.

Digital Library

[20]

Stan Liao, Srinivas Devadas, Kurt Keutzer, and Steve Tjiang. Instruction selection using binate covering for code size optimization. In Proc. Int'l Conf. on Computer-Aided Design, pages 393--399, 1995.

Digital Library

[21]

MiBench Website. http://www.eecs.umich.edu/mibench/.

[22]

Albert Nymeyer and Joost-Pieter Katoen. Code generation based on formal BURS therory and heuristic search. Acta Inf., 34(8):597--635, 1997.

[23]

Todd A. Proebsting. Least-Cost Instruction Selection in DAGs is NP-Complete. http://research.microsoft.com/~toddpro/papers/proof.htm, 1998.

[24]

Stefan Schäfer and Bernhard Scholz. Optimal chain rule placement for instruction selection based on SSA graphs. In SCOPES '07: Proceedingsof the 10th international workshop on Software & compilers for embedded systems, pages 91--100, Nice, France, 2007. ACM.

Digital Library

[25]

Bernhard Scholz and Erik Eckstein. Register Allocation for Irregular Architectures. In LCTES-SCOPES '02: Proceedings of the Joint Conference on Languages, Compilers and Tools for Embedded Systems, pages 139--148, 2002.

Digital Library

[26]

Vojin živojnovi#263;, Juan M. Velarde, Christian Schläger, and Heinrich Meyr. DSPSTONE: A DSP-oriented benchmarking methodology. In Proceedings of the International Conference on Signal Processing and Technology (ICSPAT'94), 1994.

Cited By

Zhuang YLin THuang Y(2023)The algorithm and implementation of an extension to LLVM for solving the blocking between instruction sink and division-modulo combineConnection Science10.1080/09540091.2023.227321935:1Online publication date: 30-Oct-2023
https://doi.org/10.1080/09540091.2023.2273219
Kumar SSingh SAggarwal NGupta BAlhalabi WBand S(2022)An efficient hardware supported and parallelization architecture for intelligent systems to overcome speculative overheadsInternational Journal of Intelligent Systems10.1002/int.2306237:12(11764-11790)Online publication date: 8-Sep-2022
https://doi.org/10.1002/int.23062
Ebner DKrall AScholz B(2021)Instruction Code SelectionSSA-based Compiler Design10.1007/978-3-030-80515-9_19(257-268)Online publication date: 12-Jun-2021
https://doi.org/10.1007/978-3-030-80515-9_19
Show More Cited By

Index Terms

Generalized instruction selection using SSA-graphs
1. Software and its engineering
  1. Software notations and tools
    1. Compilers

Recommendations

Generalized instruction selection using SSA-graphs
LCTES '08

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 ...
Instruction selection using binate covering for code size optimization
ICCAD '95: Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design

We address the problem of instruction selection in code generation for embedded DSP microprocessors. Such processors have highly irregular data-paths, and conventional code generation methods typically result in inefficient code. Instruction selection ...
Complete and Practical Universal Instruction Selection
Special Issue ESWEEK 2017, CASES 2017, CODES + ISSS 2017 and EMSOFT 2017

In code generation, instruction selection chooses processor instructions to implement a program under compilation where code quality crucially depends on the choice of instructions. Using methods from combinatorial optimization, this paper proposes an ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

LCTES '08: Proceedings of the 2008 ACM SIGPLAN-SIGBED conference on Languages, compilers, and tools for embedded systems

June 2008

180 pages

ISBN:9781605581040

DOI:10.1145/1375657

General Chair:
Krisztián Flautner
ARM Limited, UK
,
Program Chair:
John Regehr
University of Utah, USA

ACM SIGPLAN Notices Volume 43, Issue 7
LCTES '08
July 2008
167 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/1379023
Issue’s Table of Contents

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 June 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

LCTES08

Sponsor:

LCTES08: ACM SIGPLAN/SIGBED 2008 Conference on Languages, Compilers, and Tools for Embedded Systems

June 12 - 13, 2008

AZ, Tucson, USA

Acceptance Rates

Overall Acceptance Rate 116 of 438 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

18
Total Citations
View Citations
697
Total Downloads

Downloads (Last 12 months)24
Downloads (Last 6 weeks)3

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhuang YLin THuang Y(2023)The algorithm and implementation of an extension to LLVM for solving the blocking between instruction sink and division-modulo combineConnection Science10.1080/09540091.2023.227321935:1Online publication date: 30-Oct-2023
https://doi.org/10.1080/09540091.2023.2273219
Kumar SSingh SAggarwal NGupta BAlhalabi WBand S(2022)An efficient hardware supported and parallelization architecture for intelligent systems to overcome speculative overheadsInternational Journal of Intelligent Systems10.1002/int.2306237:12(11764-11790)Online publication date: 8-Sep-2022
https://doi.org/10.1002/int.23062
Ebner DKrall AScholz B(2021)Instruction Code SelectionSSA-based Compiler Design10.1007/978-3-030-80515-9_19(257-268)Online publication date: 12-Jun-2021
https://doi.org/10.1007/978-3-030-80515-9_19
Stanier JRastello F(2021)Graphs and Gating FunctionsSSA-based Compiler Design10.1007/978-3-030-80515-9_14(185-199)Online publication date: 12-Jun-2021
https://doi.org/10.1007/978-3-030-80515-9_14
Thier PErtl MKrall ADubach CXue J(2018)Fast and flexible instruction selection with constraintsProceedings of the 27th International Conference on Compiler Construction10.1145/3178372.3179501(93-103)Online publication date: 24-Feb-2018
https://dl.acm.org/doi/10.1145/3178372.3179501
Buchwald SFried AHack SKnoop JSchordan MJohnson TO'Boyle M(2018)Synthesizing an instruction selection rule library from semantic specificationsProceedings of the 2018 International Symposium on Code Generation and Optimization10.1145/3168821(300-313)Online publication date: 24-Feb-2018
https://dl.acm.org/doi/10.1145/3168821
Blindell GCarlsson MLozano RSchulte C(2017)Complete and Practical Universal Instruction SelectionACM Transactions on Embedded Computing Systems10.1145/312652816:5s(1-18)Online publication date: 27-Sep-2017
https://dl.acm.org/doi/10.1145/3126528
Stanier JWatson D(2013)Intermediate representations in imperative compilersACM Computing Surveys10.1145/2480741.248074345:3(1-27)Online publication date: 3-Jul-2013
https://dl.acm.org/doi/10.1145/2480741.2480743
Brandner FPavlu VKrall A(2013)Automatic generation of compiler backendsSoftware—Practice & Experience10.1002/spe.210643:2(207-240)Online publication date: 1-Feb-2013
https://dl.acm.org/doi/10.1002/spe.2106
Murray AFranke BEidt CHoller ASrinivasan UAmarasinghe S(2012)Compiling for automatically generated instruction set extensionsProceedings of the Tenth International Symposium on Code Generation and Optimization10.1145/2259016.2259019(13-22)Online publication date: 31-Mar-2012
https://dl.acm.org/doi/10.1145/2259016.2259019
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents