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 , Steven W. K. Tjiang, Code generation using tree matching and dynamic programming, ACM Transactions on Programming Languages and Systems (TOPLAS), v.11 n.4, p.491-516, Oct. 1989 [doi>10.1145/69558.75700]
• 2: A. V. Aho , S. C. Johnson, Optimal Code Generation for Expression Trees, Journal of the ACM (JACM), v.23 n.3, p.488-501, July 1976 [doi>10.1145/321958.321970]
• 3: A. Balachandran , D. M. Dhamdhere , S. Biswas, Efficient retargetable code generation using bottom-up tree pattern matching, Computer Languages, v.15 n.3, p.127-140, 1990 [doi>10.1016/0096-0551(90)90006-B]
• 4: Gunnar Braun , Achim Nohl , Weihua Sheng , Jianjiang Ceng , Manuel Hohenauer , Hanno Scharwächter , Rainer Leupers , Heinrich Meyr, A novel approach for flexible and consistent ADL-driven ASIP design, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996763]
• 5: Jianjiang Ceng , Manuel Hohenauer , Rainer Leupers , Gerd Ascheid , Heinrich Meyr , Gunnar Braun, C Compiler Retargeting Based on Instruction Semantics Models, Proceedings of the conference on Design, Automation and Test in Europe, p.1150-1155, March 07-11, 2005 [doi>10.1109/DATE.2005.88]
• 6: M. Anton Ertl , Kevin Casey , David Gregg, Fast and flexible instruction selection with on-demand tree-parsing automata, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
• 7: H. Emmelmann , F.-W. Schröer , L. Landwehr, BEG: a generation for efficient back ends, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.227-237, June 19-23, 1989, Portland, Oregon, United States
• 8: Andreas Fauth , Günter Hommel , Alois Knoll , Carsten Müller, Global Code Selection of Directed Acyclic Graphs, Proceedings of the 5th International Conference on Compiler Construction, p.128-142, April 07-09, 1994
• 9: Christopher W. Fraser , David R. Hanson , Todd A. Proebsting, Engineering a simple, efficient code-generator generator, ACM Letters on Programming Languages and Systems (LOPLAS), v.1 n.3, p.213-226, Sept. 1992 [doi>10.1145/151640.151642]
• 10: Christopher W. Fraser , Robert R. Henry , Todd A. Proebsting, BURG: fast optimal instruction selection and tree parsing, ACM SIGPLAN Notices, v.27 n.4, p.68-76, April 1992 [doi>10.1145/131080.131089]
• 11: A. Fauth , J. Van Praet , M. Freericks, Describing instruction set processors using nML, Proceedings of the 1995 European conference on Design and Test, p.503, March 06-09, 1995
• 12: Silvina Hanono , Srinivas Devadas, Instruction selection, resource allocation, and scheduling in the AVIV retargetable code generator, Proceedings of the 35th annual conference on Design automation, p.510-515, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277184]
• 13: Ashok Halambi , Peter Grun , Vijay Ganesh , Asheesh Khare , Nikil Dutt , Alex Nicolau, EXPRESSION: a language for architecture exploration through compiler/simulator retargetability, Proceedings of the conference on Design, automation and test in Europe, p.100-es, January 1999, Munich, Germany [doi>10.1145/307418.307549]
• 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 , Ivan Pryanishnikov , Ulrich Hirnschrott , Christian Panis, xDSPcore: A Compiler-Based Configurable Digital Signal Processor, IEEE Micro, v.24 n.4, p.67-78, July 2004 [doi>10.1109/MM.2004.40]
• 18: R. Leupers , P. Marwedel, A BDD-based frontend for retargetable compilers, Proceedings of the 1995 European conference on Design and Test, p.239, March 06-09, 1995
• 19: Rainer Leupers , Peter Marwedel, Retargetable Generation of Code Selectors from HDL Processor Models, Proceedings of the 1997 European conference on Design and Test, p.140, March 17-20, 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, Proceedings of the 21st conference on Design automation, p.587-593, June 25-27, 1984, Albuquerque, New Mexico, United States
• 22: Stefan Pees , Andreas Hoffmann , Heinrich Meyr, Retargeting of compiled simulators for digital signal processors using a machine description language, Proceedings of the conference on Design, automation and test in Europe, p.669-673, March 27-30, 2000, Paris, France [doi>10.1145/343647.343888]
• 23: Wei Qin , Subramanian Rajagopalan , Sharad Malik, A formal concurrency model based architecture description language for synthesis of software development tools, Proceedings of the 2004 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems, June 11-13, 2004, Washington, DC, USA

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Retargetable compilers

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Translator writing systems and compiler generators; Code generation

General Terms:
Algorithms, Languages

Keywords:
architecture description language, code generation, compiler generation