article

Processor modeling and code selection for retargetable compilation

Editor: C. L. Liu Authors:

G. GoossensAuthors Info & Claims

ACM Transactions on Design Automation of Electronic Systems (TODAES), Volume 6, Issue 3

Pages 277 - 307

https://doi.org/10.1145/383251.383252

Published: 01 July 2001 Publication History

Abstract

Embedded processors in electronic systems typically are tuned to a few applications. Development of processor-specific compilers is prohibitively expensive and, as a result, such compilers, if existing, yield code of an unacceptable quality. To improve this code quality, we developed a processor model that captures the connectivity, the parallelism, and all architectural peculiarities of an embedded processor. We also implemented a retargetable and optimizing compiler working on this model. We present the graph-based processor model, and formally define the code generation task as binding the intermediate representation of an application to this model. We also present a new method for code selection, based on this processor model, that is capable of handling directed acyclic graphs instead of trees.

References

[1]

AD. 1990. ADSP-2111, User's Manual. Analog Devices.

[2]

AHO,A.V.,SETHI, R., AND ULLMAN, J. D. 1986. Compilers : Principles, Techniques, and Tools. Addison-Wesley, Reading, Mass.

[3]

CCITT. 1990. General Aspects of Digital Transmission Systems; Terminal Equipments. Recommendation G.726 ed. The International Telegraph and Telephone Consultative Committee.

[4]

COUDERT, O. 1996. On solving covering problems. In Proceedings of the 33rd Design Automation Conference (June 1996). pp. 197-202.

[5]

COUDERT,O.,AND MADRE, J.-C. 1995. New ideas for solving covering problems. In Proceedings of the 32nd Design Automation Conference (June 1995). pp. 641-646.

[6]

ETSI. 1994. European Digital Cellular Telecommunications System (Phase 2); Full rate speech transcoding. ETSI spec. GSM 06.10, GSM 06.32 ed. The International Telegraph and Telephone Consultative Committee.

[7]

FAUTH, A., VAN PRAET,J.,AND FREERICKS, M. 1995. Describing instruction set processors using nML. In Proceedings of the European Design and Test Conference (EDTC) (1995). pp. 503-507.

[8]

FERDINAND, C., SEIDL, H., AND WILHELM, R. 1994. Tree automata for code selection. Acta Inf. 31,8, 741-760.

[9]

FRASER,C.W.,AND HANSON, D. R. 1995. A Retargetable C Compiler: Design and Implementation. Addison-Wesley, Reading, Mass.

[10]

FRASER, C. W., HANSON,D.R.,AND PROEBSTING, T. A. 1993. Engineering a simple, efficient codegenerator generator. ACM Lett. Prog. Lang. Syst. 1, 3 (Sept.), 213-226.

[11]

GAREY,M.R.,AND JOHNSON, D. S. 1979. Computers and Intractability: A guide to the Theory of NP-completeness. Freeman and Co.

[12]

GOOSSENS, G., VAN PRAET, J., LANNEER, D., GEURTS,W.,AND THOEN, F. 1996. Programmable chips in consumer electronics and telecommunications. In Hardware/Software Co-Design, G. De Micheli and M. Sami, Eds., NATO ASI Series E: Applied Sciences vol. 310. Kluwer Academic Publishers, pp. 135-164.

[13]

LANDSKOV, D., DAVIDSON, S., SHRIVER,B.,AND MALLETT, P. 1980. Local microcode compaction techniques. ACM Comput. Surv. 12, 3 (Sept.), 261-294.

[14]

LANNEER, D. 1993. Design Models and Data-Path Mapping for Signal Processing Architectures. Ph.D. dissertation, K.U.Leuven (IMEC); Leuven, Belgium.

[15]

LIAO, S., DEVADAS, S., KEUTZER, K., AND TJIANG, S. 1995. Instruction selection using binate covering for code size optimization. In Proceedings of the International Conference on Computer-Aided Design (ICCAD) (Nov. 1995). pp. 393-399.

[16]

PAPADIMITRIOU, C. H., AND STEIGLITZ, K. 1982. Combinatorial Optimization-Algorithms and Complexity. Prentice-Hall, Englewood Cliffs, New Jersey.

[17]

PAULIN,P.G.,LIEM, C., CORNERO, M., NAC, ABAL,F.,AND GOOSSENS, G. 1997. Embedded software in real-time signal processing systems: Application and architecture trends. Proc. IEEE 85, 3 (Mar.), 419-435.

[18]

RUDELL, R. L. 1989. Logic Synthesis for VLSI Design. Ph.D. dissertation, University of California, Berkeley. Memorandum No. UCB/ERL M89/49.

[19]

VAN PRAET, J. 1997. Processor Modelling and Code Generation Techniques for Retargetable Compilation. Ph.D. dissertation, K.U. Leuven (IMEC), Leuven, Belgium.

[20]

VAN PRAET, J., LANNEER, D., GEURTS,W.,AND GOOSSENS, G. 1998. Method of generating code for programmable processor, code generator and application thereof. European Patent and U.S. Patent No. 5,854,929.

[21]

VAN PRAET, J., LANNEER, D., GEURTS,W.,AND GOOSSENS, G. 1999. A method for processor modeling in code generation and instruction set simulation. U.S. Patent No. 5,918,035.

[22]

VAN PRAET, J., LANNEER, D., GEURTS, W., GOOSSENS,G.,AND DE MAN, H. 1996. Modelling hardwarespecific data-types for simulation and compilation in hw/sw co-design. In Proceedings of the Workshop on Synthesis and System Integration of Mixed Technologies (SASIMI) (Fukuoka, Japan, Nov. 1996). pp. 255-262.

[23]

VEGDAHL, S. R. 1982. Phase coupling and constant generation in an optimizing microcode compiler. Proceedings of 15th Annual Workshop on Microprogramming (Micro-15), Sigmicro Newsletter 13, pp. 125-133.

[24]

WILHELM, R., AND MAURER, D. 1995. Compiler Design. International Computer Science Series. Addison-Wesley, Reading, Mass.

[25]

ZIVOJNOVIC, V., VELARDE, J. M., CHRISTIAN,S.,AND MEYR, H. 1994. DSPSTONE: A DSP-oriented benchmarking methodology. In Proceedings of the International Conference on Signal Processing Applications and Technology (ICSPAT) (Dallas, Texas, Oct. 1994). pp. 715-720.

Cited By

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
Patyk TSalmela PPitkänen TJääskeläinen PTakala J(2011)Design Methodology for Offloading Software Executions to FPGAJournal of Signal Processing Systems10.5555/2070637.207065065:2(245-259)Online publication date: 1-Nov-2011
https://dl.acm.org/doi/10.5555/2070637.2070650
Patyk TSalmela PPitkänen TJääskeläinen PTakala J(2011)Design Methodology for Offloading Software Executions to FPGAJournal of Signal Processing Systems10.1007/s11265-011-0606-x65:2(245-259)Online publication date: 30-Jul-2011
https://doi.org/10.1007/s11265-011-0606-x
Show More Cited By

Index Terms

Processor modeling and code selection for retargetable compilation
1. Software and its engineering
  1. Software notations and tools
    1. Compilers
      1. Source code generation

Recommendations

Retargetable Code Generation Based on Structural Processor Description

Design automation for embedded systems comprising both hardware and software components demands for code generators integrated into electronic CAD systems. These code generators provide the necessary link between software synthesis tools in HW/SW ...
Graph-based code selection techniques for embedded processors

Code selection is an important task in code generation for programmable processors, where the goal is to find an efficient mapping of machine-independent intermediate code to processor-specific machine instructions. Traditional approaches to code ...
Retargetable code optimization with SIMD instructions
CODES+ISSS '06: Proceedings of the 4th international conference on Hardware/software codesign and system synthesis

Retargetable C compilers are nowadays widely used to quickly obtain compiler support for new embedded processors and to perform early processor architecture exploration. One frequent concern about retargetable compilers, though, is their lack of machine-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Design Automation of Electronic Systems

ACM Transactions on Design Automation of Electronic Systems Volume 6, Issue 3

July 2001

169 pages

ISSN:1084-4309

EISSN:1557-7309

DOI:10.1145/383251

Editor:
C. L. Liu
Univ. of Illinois at Urbana-Champaign, Urbana, IL

Issue’s Table of Contents

Copyright © 2001 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Journal Family

ACM Journals for the Design of Smart and Connected Systems

Publication History

Published: 01 July 2001

Published in TODAES Volume 6, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

20
Total Citations
View Citations
571
Total Downloads

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

Reflects downloads up to 21 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

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
Patyk TSalmela PPitkänen TJääskeläinen PTakala J(2011)Design Methodology for Offloading Software Executions to FPGAJournal of Signal Processing Systems10.5555/2070637.207065065:2(245-259)Online publication date: 1-Nov-2011
https://dl.acm.org/doi/10.5555/2070637.2070650
Patyk TSalmela PPitkänen TJääskeläinen PTakala J(2011)Design Methodology for Offloading Software Executions to FPGAJournal of Signal Processing Systems10.1007/s11265-011-0606-x65:2(245-259)Online publication date: 30-Jul-2011
https://doi.org/10.1007/s11265-011-0606-x
Rajagopalan SMalik S(2010)Retargetable Very Long InstructionWord Compiler Framework for Digital Signal ProcessorsThe Compiler Design Handbook10.1201/9781420040579.ch16Online publication date: 7-Mar-2010
https://doi.org/10.1201/9781420040579.ch16
Shankar P(2010)Instruction Selection Using Tree ParsingThe Compiler Design Handbook10.1201/9781420040579.ch15Online publication date: 7-Mar-2010
https://doi.org/10.1201/9781420040579.ch15
Patyk TSalmela PPitkanen TTakala J(2010)Design methodology for accelerating software executions with FPGA2010 IEEE Workshop On Signal Processing Systems10.1109/SIPS.2010.5624761(46-51)Online publication date: Oct-2010
https://doi.org/10.1109/SIPS.2010.5624761
Rajagopalan SMalik S(2009)A Retargetable Very Long Instruction Word Compiler Framework for Digital Signal ProcessorsThe Compiler Design Handbook10.1201/9781420043839.ch18(18-1-18-28)Online publication date: 7-Dec-2009
https://doi.org/10.1201/9781420043839.ch18
Shankar P(2009)Instruction Selection Using Tree ParsingThe Compiler Design Handbook10.1201/9781420043839.ch17(17-1-17-36)Online publication date: 7-Dec-2009
https://doi.org/10.1201/9781420043839.ch17
Goossens GDytrych PLanneer D(2009)Design of Low-Power Processor Cores Using a Retargetable Tool FlowLow-Power Processors and Systems on Chips10.1201/9781420037203.ch19(19-1-19-20)Online publication date: 4-Dec-2009
https://doi.org/10.1201/9781420037203.ch19
Van Praet JLanneer DGeurts WGoossens G(2008)nMLProcessor Description Languages10.1016/B978-012374287-2.50007-0(65-93)Online publication date: 2008
https://doi.org/10.1016/B978-012374287-2.50007-0
Show More Cited By

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 Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents