research-article

Instruction selection by graph transformation

Authors:

Sebastian Buchwald,

Andreas ZwinkauAuthors Info & Claims

CASES '10: Proceedings of the 2010 international conference on Compilers, architectures and synthesis for embedded systems

Pages 31 - 40

https://doi.org/10.1145/1878921.1878926

Published: 24 October 2010 Publication History

Abstract

Common generated instruction selections are based on tree pattern matching, but modern and custom architectures feature instructions, which cannot be covered by trees. To overcome this limitation, we are the first to employ graph transformation, the natural generalization of tree rewriting. Currently, the only approach allowing us to pair graph-based instruction selection with linear time complexity is the mapping to the Partitioned Boolean Quadratic Problem (PBQP). We present formal foundations to verify this approach and therewith identify two problems of the common method and resolve them. We confirm the capabilities of PBQP-based instruction selection by a comparison with a finely-tuned hand-written instruction selection.

References

[1]

P. Biswas and G. Venkataramani. Comprehensive isomorphic subtree enumeration. In CASES '08: Proceedings of the 2008 international conference on Compilers, architectures and synthesis for embedded systems, pages 177--186, New York, NY, USA, 2008. ACM.

Digital Library

[2]

S. Buchwald and A. Zwinkau. Befehlsauswahl auf expliziten Abhängigkeitsgraphen. Master's thesis, Universität Karlsruhe (TH), IPD Goos, December 2008.

[3]

H. Bunke, T. Glauser, and T. Tran. An efficient implementation of graph grammars based on the RETE matching algorithm. In H. Ehrig, H.-J. Kreowski, and G. Rozenberg, editors, Graph Grammars and Their Application to Computer Science, volume 532 of Lecture Notes in Computer Science, chapter 17, pages 174--189. Springer-Verlag, Berlin/Heidelberg, 1991.

Digital Library

[4]

C. N. Click. Combining Analyses, Combining Optimizations. PhD thesis, Rice University, February 1995.

Digital Library

[5]

G. Cohen, J.-P. Quadrat, G. J. Olsder, and F. Baccelli. Synchronization and linearity, an algebra for discrete event systems, 1992.

[6]

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 Trans. Program. Lang. Syst., 13(4):451--490, October 1991.

Digital Library

[7]

D. Ebner, F. Brandner, B. Scholz, A. Krall, P. Wiedermann, and A. Kadlec. 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, pages 31--40, New York, NY, USA, 2008. ACM.

Digital Library

[8]

E. Eckstein. Code optimizations for digital signal processors. PhD thesis, TU Wien, November 2003.

[9]

E. Eckstein, O. König, and B. Scholz. Code instruction selection based on SSA-graphs. In SCOPES, pages 49--65, 2003.

[10]

E. Eckstein and B. Scholz. Addressing mode selection. In CGO '03: Proceedings of the international symposium on Code generation and optimization, pages 337--346, Washington, DC, USA, 2003. IEEE Computer Society.

Digital Library

[11]

H. Ehrig, K. Ehrig, U. Prange, and G. Taentzer. Fundamentals of Algebraic Graph Transformation (Monographs in Theoretical Computer Science. An EATCS Series). Springer-Verlag New York, Inc., Secaucus, NJ, USA, 2006.

Digital Library

[12]

S. Eilenberg and S. MacLane. General theory of natural equivalences. Transactions of the American Mathematical Society, 58(2):231--294, 1945.

[13]

M. A. Ertl. Optimal code selection in DAGs. In POPL '99: Proceedings of the 26th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, pages 242--249, New York, NY, USA, 1999. ACM.

Digital Library

[14]

C. W. Fraser, R. R. Henry, and T. A. Proebsting. Burg: fast optimal instruction selection and tree parsing. SIGPLAN Not., 27(4):68--76, 1992.

Digital Library

[15]

R. Geiß, G. V. Batz, D. Grund, S. Hack, and A. M. Szalkowski. GrGen: A fast SPO-based graph writing tool. In A. Corradini, H. Ehrig, U. Montanari, L. Ribeiro, and G. Rozenberg, editors, Graph Transformations - ICGT 2006, Lecture Notes in Computer Science, pages 383--397. Springer, 2006. Natal, Brasil.

Digital Library

[16]

A. Habel, R. Heckel, and G. Taentzer. Graph grammars with negative application conditions. Fundam. Inf., 26(3--4):287--313, 1996.

Digital Library

[17]

L. Hames and B. Scholz. Nearly optimal register allocation with PBQP. In D. E. Lightfoot and C. A. Szyperski, editors, Modular Programming Languages, 7th Joint Modular Languages Conference, JMLC 2006, Oxford, UK, September 13--15, 2006, Proceedings, volume 4228 of Lecture Notes in Computer Science, pages 346--361. Springer, 2006.

Digital Library

[18]

R. Heckel. Graph transformation in a nutshell. Electronic Notes in Theoretical Computer Science, 148(1):187--198, February 2006.

Digital Library

[19]

H. Jakschitsch. Befehlsauswahl auf SSA-Graphen. Master's thesis, IPD Goos, November 2004.

[20]

D. Koes and S. C. Goldstein. A progressive register allocator for irregular architectures. In CGO '05: Proceedings of the international symposium on Code generation and optimization, pages 269--280, Washington, DC, USA, 2005. IEEE Computer Society.

Digital Library

[21]

T. Li, Z. Sun, W. Jigang, and X. Lu. Fast enumeration of maximal valid subgraphs for custom-instruction identification. In CASES '09: Proceedings of the 2009 international conference on Compilers, architecture, and synthesis for embedded systems, pages 29--36, New York, NY, USA, 2009. ACM.

Digital Library

[22]

M. Löwe and H. Ehrig. Algebraic approach to graph transformation based on single pushout derivations. In WG '90: Proceedings of the 16th international workshop on Graph-theoretic concepts in computer science, pages 338--353, New York, NY, USA, 1991. Springer-Verlag New York, Inc.

Digital Library

[23]

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

[24]

E. Pelegrí-Llopart and S. L. Graham. Optimal code generation for expression trees: an application BURS theory. In POPL '88: Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, pages 294--308, New York, NY, USA, 1988. ACM.

Digital Library

[25]

F. M. Q. Pereira and J. Palsberg. Register allocation by puzzle solving. SIGPLAN Not., 43(6):216--226, 2008.

Digital Library

[26]

T. Proebsting. Least-cost instruction selection in DAGs is NP-complete. Privately published online, 1998.

[27]

B. K. Rosen, M. N. Wegman, and F. K. Zadeck. Global value numbers and redundant computations. In POPL '88: Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, pages 12--27, New York, NY, USA, 1988. ACM.

Digital Library

[28]

G. Rozenberg, editor. Handbook of graph grammars and computing by graph transformation: volume I. foundations. World Scientific Publishing Co., Inc., River Edge, NJ, USA, 1997.

Digital Library

[29]

B. Scholz and E. Eckstein. Register allocation for irregular architectures. In LCTES-SCOPES, pages 139--148. ACM, 2002.

Digital Library

[30]

A. Schösser. Graphersetzungsregelgewinnung aus Hochsprachen und deren Anwendung. Master's thesis, Universität Karlsruhe (TH), IPD, 9 2007.

[31]

M. D. Smith, N. Ramsey, and G. Holloway. A generalized algorithm for graph-coloring register allocation. In PLDI '04: Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, pages 277--288, New York, NY, USA, 2004. ACM.

Digital Library

Cited By

Sovetov P(2021)Development of DSL Compilers for Specialized ProcessorsProgramming and Computer Software10.1134/S036176882107008247:7(541-554)Online publication date: 3-Dec-2021
https://doi.org/10.1134/S0361768821070082
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
Hjort Blindell GCastañeda Lozano RCarlsson MSchulte C(2015)Modeling Universal Instruction SelectionPrinciples and Practice of Constraint Programming10.1007/978-3-319-23219-5_42(609-626)Online publication date: 13-Aug-2015
https://doi.org/10.1007/978-3-319-23219-5_42
Show More Cited By

Index Terms

Instruction selection by graph transformation
1. Software and its engineering
  1. Software notations and tools
    1. Compilers
      1. Retargetable compilers
  2. Software organization and properties
    1. Software functional properties
      1. Correctness
2. Theory of computation
  1. Logic
    1. Proof theory

Recommendations

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 ...
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 ...
Near-optimal instruction selection on dags
CGO '08: Proceedings of the 6th annual IEEE/ACM international symposium on Code generation and optimization

Instruction selection is a key component of code generation. High quality instruction selection is of particular importance in the embedded space where complex instruction sets are common and code size is a prime concern. Although instruction selection ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CASES '10: Proceedings of the 2010 international conference on Compilers, architectures and synthesis for embedded systems

October 2010

276 pages

ISBN:9781605589039

DOI:10.1145/1878921

Program Chairs:
Vinod Kathail
USA
,
Reid Tatge
Texas Instruments, USA
,
Rajeev Barua
University of Maryland, College Park, USA

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

In-Cooperation

CEDA
IEEE CAS
IEEE CS

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 24 October 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tag

instruction selection

Qualifiers

Research-article

Conference

ESWeek '10

Sponsor:

ESWeek '10: Sixth Embedded Systems Week

October 24 - 29, 2010

Arizona, Scottsdale, USA

Acceptance Rates

Overall Acceptance Rate 52 of 230 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
251
Total Downloads

Downloads (Last 12 months)9
Downloads (Last 6 weeks)1

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Sovetov P(2021)Development of DSL Compilers for Specialized ProcessorsProgramming and Computer Software10.1134/S036176882107008247:7(541-554)Online publication date: 3-Dec-2021
https://doi.org/10.1134/S0361768821070082
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
Hjort Blindell GCastañeda Lozano RCarlsson MSchulte C(2015)Modeling Universal Instruction SelectionPrinciples and Practice of Constraint Programming10.1007/978-3-319-23219-5_42(609-626)Online publication date: 13-Aug-2015
https://doi.org/10.1007/978-3-319-23219-5_42
Buchwald SZwinkau ABersch T(2011)SSA-based register allocation with PBQPProceedings of the 20th international conference on Compiler construction: part of the joint European conferences on theory and practice of software10.5555/1987237.1987243(42-61)Online publication date: 26-Mar-2011
https://dl.acm.org/doi/10.5555/1987237.1987243
Buchwald SJakumeit E(2011)Solving the TTC 2011 Compiler Optimization Case with GrGen.NETElectronic Proceedings in Theoretical Computer Science10.4204/EPTCS.74.774(42-53)Online publication date: 16-Nov-2011
https://doi.org/10.4204/EPTCS.74.7
Buchwald SZwinkau ABersch T(2011)SSA-Based Register Allocation with PBQPCompiler Construction10.1007/978-3-642-19861-8_4(42-61)Online publication date: 2011
https://doi.org/10.1007/978-3-642-19861-8_4

View Options

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