Graph-based code selection techniques for embedded processors

ABSTRACT

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 selection are based on tree parsing which enables fast and optimal code selection for intermediate code given as a set of data-flow trees. While this approach is generally useful in compilers for general-purpose processors, it may lead to poor code quality in the case of embedded processors. The reason is that the special architectural features of embedded processors require performing code selection on data-flow graphs, which are a more general representation of intermediate code. In this paper, we present data-flow graph-based code selection techniques for two architectural families of embedded processors: media processors with support for SIMD instructions and fixed-point DSPs with irregular data paths. Both techniques exploit the fact that, in the area of embedded systems, high code quality is a much more important goal than high compilation speed. We demonstrate that certain architectural features can only be utilized by graph-based code selection, while in other cases this approach leads to a significant increase in code quality as compared to tree-based code selection.

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: Guido Araujo , Sharad Malik , Mike Tien-Chien Lee, Using register-transfer paths in code generation for heterogeneous memory-register architectures, Proceedings of the 33rd annual conference on Design automation, p.591-596, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240630]
• 4: BASHFORD, S. AND LEUPERS R. 1999. Phase-coupled mapping of data flow graphs to irregular data paths. In Design Automation for Embedded Systems, 4, 2/3, Kluwer Academic Publishers.
• 5: G. J. Chaitin, Register allocation & spilling via graph coloring, Proceedings of the 1982 SIGPLAN symposium on Compiler construction, p.98-105, June 23-25, 1982, Boston, Massachusetts, United States
• 6: Eindhoven University of Technology. ftp.es.ele.tue.nl/pub/lp solve.
• 7: M. Anton Ertl, Optimal code selection in DAGs, Proceedings of the 26th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.242-249, January 20-22, 1999, San Antonio, Texas, United States [doi>10.1145/292540.292562]
• 8: Randall J. Fisher , Henry G. Dietz, Compiling for SIMD Within a Register, Proceedings of the 11th International Workshop on Languages and Compilers for Parallel Computing, p.290-304, August 07-09, 1998
• 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: Robert Steven Glanville, A machine independent algorithm for code generation and its use in retargetable compilers., 1977
• 11: INTEL. 1998. MMX Technology Application Notes. http://developer.intel.com/drg/mmx/appnotes.
• 12: LANCE V1.0 Software and User's Guide, 2000. University of Dortmund, Dept. of Computer Science 12, IS12-www.cs.uni-dortmund.de/~leupers.
• 13: R. Leupers , P. Marwedel, Instruction selection for embedded DSPs with complex instructions, Proceedings of the conference on European design automation, p.200-205, September 1996, Geneva, Switzerland
• 14: Stan Liao , Srinivas Devadas , Kurt Keutzer , Steve Tjiang, Instruction selection using binate covering for code size optimization, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.393-399, November 05-09, 1995, San Jose, California, United States
• 15: MARRIOTT, K. AND STUCKEY, P. J. 1998. Programming with Constraints: An Introduction, The MIT Press.
• 16: Peter Marwedel , Gert Goossens, Code Generation for Embedded Processors, Kluwer Academic Publishers, Norwell, MA, 1995
• 17: Alex Peleg , Sam Wilkie , Uri Weiser, Intel MMX for multimedia PCs, Communications of the ACM, v.40 n.1, p.24-38, Jan. 1997 [doi>10.1145/242857.242865]
• 18: PHILIPS. 1998. http://www.trimedia.philips.com.
• 19: TEXAS INSTRUMENTS. 1998. TMS320C62xx CPU and Instruction Set Reference Guide, http://www. ti.com/sc/c6x.
• 20: Pascal Van Hentenryck, Constraint satisfaction in logic programming, MIT Press, Cambridge, MA, 1989
• 21: WALLACE, M. 1995. Constraint Programming. Contact address: IC-Parc, William Penney Laboratory, Imperial College, London SW7 2AZ, email: [e-mail]. Publications at http://www.icparc.ic.ac.uk/.
• 22: WALLACE, M., NOVELLO, S., AND SCHIMPF, J. 1997. ECL PS: A Platform for Constraint Logic Programming. Contact address: IC-Parc, William Penney Laboratory, Imperial College, London SW7 2AZ, email: [e-mail].
• 23: Renhard Wilhelm , Dieter Maurer , R. Wilhelm, Compiler Design, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1995
• 24: ZIVOJNOVIC, V., VELARDE, J. M., SCHL~GER, C. AND MEYR, H. 1994. DSPStone-a dsp-oriented benchmarking methodology. In International Conference on Signal Processing Applications and Technology (ICSPAT).

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Code generation

General Terms:
Algorithms, Experimentation

Keywords:
SIMD instructions, code selection, data-flow graphs, embedded processors, irregular data paths