Compiler generation from structural architecture descriptions

ABSTRACT

With increasing complexity of modern embedded systems, the availability of highly optimizing compilers becomes more and more important. At the same time, application specific instruction-set processors (ASIPs) are used to fine-tune hardware platforms to the intended application, demanding the availability of retargetable components throughout thewhole tool chain.

A very promising approach is to model the target architecture using a dedicated description language that is rich enough to generate hardware components and the required tool chain, e.g., assembler, linker, simulator, and compiler.

In this work we present a new structural architecture description language (ADL) that is used to derive the architecture dependent components of a compiler backend - most notably an instruction selector based on tree pattern matching. We combine our backend with gcc, thereby opening up the way for a large number of readily available high level optimizations. Experimental results show that the automatically derived code generator is competitive in comparison to a handcrafted compiler backend.

REFERENCES

• 1: 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]
• 2: Rodolfo Azevedo , Sandro Rigo , Marcus Bartholomeu , Guido Araujo , Cristiano Araujo , Edna Barros, The ArchC architecture description language and tools, International Journal of Parallel Programming, v.33 n.5, p.453-484, October 2005 [doi>10.1007/s10766-005-7301-0]
• 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: Stefan Farfeleder , Andreas Krall , Edwin Steiner , Florian Brandner, Effective compiler generation by architecture description, Proceedings of the 2006 ACM SIGPLAN/SIGBED conference on Language, compilers, and tool support for embedded systems, June 14-16, 2006, Ottawa, Ontario, Canada
• 7: 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
• 8: 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
• 9: C. W. Fraser and D. R. Hanson. A retargetable compiler for ANSI C. Technical Report CS-TR-303-91, Princeton, N.J., 1991.
• 10: 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]
• 11: 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]
• 12: David Goodwin , Darin Petkov, Automatic generation of application specific processors, Proceedings of the 2003 international conference on Compilers, architecture and synthesis for embedded systems, October 30-November 01, 2003, San Jose, California, USA [doi>10.1145/951710.951730]
• 13: M. R. Guthaus , J. S. Ringenberg , D. Ernst , T. M. Austin , T. Mudge , R. B. Brown, MiBench: A free, commercially representative embedded benchmark suite, Proceedings of the Workload Characterization, 2001. WWC-4. 2001 IEEE International Workshop, p.3-14, December 02-02, 2001 [doi>10.1109/WWC.2001.15]
• 14: J. Gyllenhaal. A machine description language for compilation. Master's thesis, 1994.
• 15: 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]
• 16: 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]
• 17: 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.
• 18: Chunho Lee , Miodrag Potkonjak , William H. Mangione-Smith, MediaBench: a tool for evaluating and synthesizing multimedia and communicatons systems, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.330-335, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 19: 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
• 20: 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
• 21: The gnu compiler collection. http://gcc.gnu.org/.
• 22: 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
• 23: Prabhat Mishra , Arun Kejariwal , Nikil Dutt, Synthesis-driven Exploration of Pipelined Embedded Processors, Proceedings of the 17th International Conference on VLSI Design, p.921, January 05-09, 2004
• 24: Sanghyun Park , Eugene Earlie , Aviral Shrivastava , Alex Nicolau , Nikil Dutt , Yunheung Paek, Automatic generation of operation tables for fast exploration of bypasses in embedded processors, Proceedings of the conference on Design, automation and test in Europe: Proceedings, March 06-10, 2006, Munich, Germany
• 25: David A. Patterson , John L. Hennessy, Computer organization & design: the hardware/software interface, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• 26: 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]
• 27: 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
• 28: Johan Runeson and Sven-Olof Nyström. Retargetable graph-coloring register allocation for irregular architectures. In Andreas Krall, editor, Software and Compilers for Embedded Systems, 7th International Workshop, SCOPES 2003, Vienna, Austria, September 24-26, 2003, Proceedings, volume 2826 of Lecture Notes in Computer Science, pages 240--254. Springer, 2003.
• 29: S. P. Seng, K. V. Palem, R. M. Rabbah, W. F. Wong, W. Luk, and P. Y. K Cheung. PD-XML: extensible markup language for processor description. In Field-Programmable Technology, pages 437--440, 2002.
• 30: Aviral Shrivastava , Eugene Earlie , Nikil Dutt , Alex Nicolau, Operation tables for scheduling in the presence of incomplete bypassing, Proceedings of the 2nd IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, September 08-10, 2004, Stockholm, Sweden [doi>10.1145/1016720.1016768]
• 31: Albert Wang , Earl Killian , Dror Maydan , Chris Rowen, Hardware/software instruction set configurability for system-on-chip processors, Proceedings of the 38th conference on Design automation, p.184-188, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.378460]

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: Code generation

General Terms:
Algorithms, Languages, Measurement, Performance

Keywords:
ADL, architecture description, retargetable compiler