Effective compiler generation by architecture description

Abstract

Embedded systems have an extremely short time to market and therefore require easily retargetable compilers. Architecture description languages (ADLs) provide a single concise architecture specification for the generation of hardware, instruction set simulators and compilers. In this article, we present an ADL for compiler generation. From a specification, we can derive an optimized tree pattern matching instruction selector, a register allocator and an instruction scheduler. Compared to a hand-crafted back end, the generated compiler produces smaller and faster code.The ADL is rich enough that other tools, such as assemblers, linkers, simulators and documentation, can all be obtained from a single specification.

References

1. Alfred V. Aho, Mahadevan Ganapathi, and Steven W. K. Tjiang. Code generation using tree matching and dynamic programming. ACM Transactions on Programming Languages and Systems, 11(4):491--516, October 1989.
2. Alfred V. Aho and Stephen C. Johnson. Optimal code generation for expression trees. Journal of the ACM, 23(3):488--501, July 1976.
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.
4. Gunnar Braun, Achim Nohl, Weihua Sheng, Jianjiang Ceng, Manuel Hohenauer, Hanno Scharwächter, Rainer Leupers, and Heinrich Meyr. A novel approach for flexible and consistent ADL-driven ASIP design. In DAC '04: Proceedings of the 41st Design Automation Conference, pages 717--722. ACM Press, June 2004.
5. Jianjiang Ceng, Manuel Hohenauer, Rainer Leupers, Gerd Ascheid, Heinrich Meyr, and Gunnar Braun. C compiler retargeting based on instruction semantics models. In DATE '05: Proceedings of the conference on Design, Automation and Test in Europe, pages 1150--1155. IEEE Computer Society, March 2005.
6. M. Anton Ertl, Kevin Casey, and David Gregg. Fast and flexible instruction selection with on-demand treeparsing automata. In PLDI 2006: Proceedings of the SIGPLAN Conference on Programming Language Design and Implementation. ACM Press, June 2006.
7. Helmut Emmelmann, Friedrich-Wilhelm Schröer, and Rudolf Landwehr. Beg - a generator for efficient back ends. In PLDI '89: Proceedings of the SIGPLAN Conference on Programming Language Design and Implementation, pages 227--237, June 1989.
8. Andreas Fauth, Günter Hommel, Carsten Müller, and Alois Knoll. Global code selection of directed acyclic graphs. In CC '94: Proceedings of the 5th International Conference on Compiler Construction, pages 128--142. Springer, April 1994.
9. 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.
10. Christopher W. Fraser, Robert R. Henry, and Todd A. Proebsting. BURG - fast optimal instruction selection and tree parsing. ACM SIGPLAN Notices, 27(4):68--76, April 1992.
11. Andreas Fauth, Johan Van Praet, and Markus Freericks. Describing instruction set processors using nML. In EDTC'95: Proceedings of the 1995 European Design and Test Conference, pages 503--507. IEEE Computer Society, March 1995.
12. Silvina Hanono and Srinivas Devadas. Instruction selection, resource allocation, and scheduling in the AVIV retargetable code generator. In DAC '98: Proceedings of the 35th Design Automation Conference, pages 510--515. ACM Press, June 1998.
13. Ashok Halambi, Peter Grun, Vijay Ganesh, Asheesh Khare, Nikil Dutt, and Alex Nicolau. EXPRESSION: A language for architecture exploration through compiler/simulator retargetability. In DATE '99: Proceedings of the conference on Design, Automation and Test in Europe, pages 485--490. IEEE Computer Society, March 1999.
14. Ulrich Hirnschrott, Andreas Krall, and Bernhard Scholz. Graph-coloring vs. optimal register allocation for optimizing compilers. In Laszlo Böszörmenyi, editor, Proceedings of the Joint Modular Language Conference (JMLC) 2003, LNCS, Klagenfurt, August 2003. Springer.
15. Ashok Halambi, Aviral Shrivastava, Nikil Dutt, and Alex Nicolau. A customizable compiler framework for embedded systems. In SCOPES '01: Proceedings of 5th International Workshop on Software and Compilers for Embedded Systems. Springer, March 2001.
16. Andreas Krall, Stefan Farfeleder, and Nigel Horspool. Ultra fast cycle-accurate compiled emulation of inorder pipelined architectures. In Jarmo Takala, editor, SAMOS 2005, LNCS 3553, pages 222--231, Samos, July 2005. Springer.
17. Andreas Krall, Ulrich Hirnschrott, Christian Panis, and Ivan Pryanishnikov. xDSPcore: A Compiler-Based Configureable Digital Signal Processor. IEEE Micro, 24(4):67--78, July/August 2004.
18. Rainer Leupers and Peter Marwedel. A BDD-based frontend for retargetable compilers. In EDTC '95: Proceedings of the 1995 European Design and Test Conference, pages 239--243. IEEE Computer Society, March 1995.
19. Rainer Leupers and Peter Marwedel. Retargetable generation of code selectors from HDL processor models. In EDTC '97: Proceedings of the 1997 European Design and Test Conference, pages 140--145. IEEE Computer Society, March 1997.
20. Dirk Lanneer, Johan Van Praet, Augusli Kifli, Koen Schoofs, Werner Geurts, Filip Thoen, and Gert Goossens. CHESS: Retargetable code generation for embedded DSP processors. In Peter Marwedel and Gert Goossens, editors, Code Generation for Embedded Processors, pages 85--102. Kluwer Academic Publishers, 1995.
21. Peter Marwedel. The Mimola design system: Tools for the design of digital processors. In DAC '84: Proceedings of the 21st Design Automation Conference, pages 587--593. IEEE Press, June 1984.
22. Stefan Pees, Andreas Hoffmann, and Heinrich Meyr. Retargeting of compiled simulators for digital signal processors using a machine description language. In DATE '00: Proceedings of the conference on Design, Automation and Test in Europe, pages 669--673. IEEE Computer Society, March 2000.
23. Wei Qin, Subramanian Rajagopalan, and Sharad Malik. A formal concurrency model based architecture description language for synthesis of software development tools. In LCTES '04: Proceedings of the 2004 ACM SIGPLAN/SIGBED Conference on Languages, Compilers, and Tools for Embedded Systems, pages 47--56. ACM Press, June 2004.

Index Terms

• Software and its engineering

  • Software notations and tools

    • Compilers

      • Retargetable compilers

      • Source code generation

      • Translator writing systems and compiler generators