Article

Optimal chain rule placement for instruction selection based on SSA graphs

Authors:

Stefan Schäfer,

Bernhard ScholzAuthors Info & Claims

SCOPES '07: Proceedingsof the 10th international workshop on Software & compilers for embedded systems

Pages 91 - 100

https://doi.org/10.1145/1269843.1269857

Published: 20 April 2007 Publication History

Abstract

Instruction selection is a compiler optimisation that translates the intermediate representation of a program into a lower intermediate representation or an assembler program. We use the SSA form as an intermediate representation for instruction selection. Patterns are used for translation and are expressed as production rules in a graph grammar. The instruction selector seeks for a syntax derivation with minimal costs optimising execution time, code size, or a combination of both. Production rules are either base rules which match nodes in the SSA graph or chain rules which convert results of operations.

We present a new algorithm for placing chain rules in a control flow graph. This new algorithm places chain rules optimally for an arbitrary cost metric. Experiments with the MiBench and SPEC2000 benchmark suites show that our proposed algorithm is feasible and always yields better results than simple strategies currently in use. We reduce the costs for placing chain rules by 25% for the MiBench suite and by 11% for the SPEC2000 suite.

References

[1]

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

Digital Library

[2]

B. V. Cherkassky and A. V. Goldberg. On implementing the push-relabel method for the maximum flow problem. Algorithmica, 19(4):390--410, 1997.

[3]

R. Cytron, J. Ferrante, B. K. Rosen, M. N. Wegman, and F. K. 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

[4]

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

[5]

J. Edmonds and R. M. Karp. Theoretical improvements in algorithmic efficiency for network flow problems. J. ACM, 19(2):248--264, 1972.

Digital Library

[6]

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

Digital Library

[7]

M. A. Ertl, K. Casey, and D. 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

[8]

J. L. Ford and D. R. Fulkerson. Flows in Networks. Princeton University Press, Princeton, N.J., 1962.

[9]

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

[10]

M. P. Gerlek, E. Stoltz, and M. 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

[11]

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

[12]

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

[13]

D. R. Karger and C. Stein. A new approach to the minimum cut problem. J. ACM, 43(4):601--640, 1996.

Digital Library

[14]

J. Knoop, O. Ruething, and B. Steffen. Lazy Code Motion. In Proceedings of the ACM SIGPLAN '92 Conference on Programming Language Design and Implementation, volume 27, pages 224--234, San Francisco, CA, June 1992.

Digital Library

[15]

Spec2000 Website, http://www.spec.org.

[16]

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

Digital Library

[17]

S. Liao, S. Devadas, K. Keutzer, and S. 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

[18]

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

[19]

LLVM Website. http://llvm.cs.uiuc.edu.

[20]

A. Nymeyer and J.-P. Katoen. Code generation based on formal burs therory and heuristic search. Acta Inf., 34(8):597--635, 1997.

Cited By

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
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
de Oliveira ASaif Ur Rehman AFischmeister S(2012)mTagsACM SIGOPS Operating Systems Review10.1145/2331576.233158746:2(67-79)Online publication date: 16-Jul-2012
https://dl.acm.org/doi/10.1145/2331576.2331587
Show More Cited By

Recommendations

Generalized instruction selection using SSA-graphs
LCTES '08: Proceedings of the 2008 ACM SIGPLAN-SIGBED conference on Languages, compilers, and tools for embedded systems

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 ...
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 ...
Studying optimal spilling in the light of SSA
CASES '11: Proceedings of the 14th international conference on Compilers, architectures and synthesis for embedded systems

Recent developments in register allocation, mostly linked to static single assignment (SSA) form, have shown that it is possible to decouple the problem in two successive phases: a first spilling phase places load and store instructions so that the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SCOPES '07: Proceedingsof the 10th international workshop on Software & compilers for embedded systems

April 2007

127 pages

ISBN:9781450378345

DOI:10.1145/1269843

Editors:
Heiko Falk
University of Dortmund, Germany
,
Peter Marwedel
University of Dortmund, Germany

Copyright © 2007 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

EDAA: European Design Automation Association
ACE Associated Compiler Experts bv
SIGBED: ACM Special Interest Group on Embedded Systems
Artist2 European NoE

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 20 April 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 38 of 79 submissions, 48%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
269
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

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
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
de Oliveira ASaif Ur Rehman AFischmeister S(2012)mTagsACM SIGOPS Operating Systems Review10.1145/2331576.233158746:2(67-79)Online publication date: 16-Jul-2012
https://dl.acm.org/doi/10.1145/2331576.2331587
Ebner DBrandner FScholz BKrall AWiedermann PKadlec A(2008)Generalized instruction selection using SSA-graphsACM SIGPLAN Notices10.1145/1379023.137566343:7(31-40)Online publication date: 12-Jun-2008
https://dl.acm.org/doi/10.1145/1379023.1375663
Ebner DBrandner FScholz BKrall AWiedermann PKadlec AFlautner KRegehr J(2008)Generalized instruction selection using SSA-graphsProceedings of the 2008 ACM SIGPLAN-SIGBED conference on Languages, compilers, and tools for embedded systems10.1145/1375657.1375663(31-40)Online publication date: 12-Jun-2008
https://dl.acm.org/doi/10.1145/1375657.1375663

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