Code generation for fixed-point DSPs

ABSTRACT

This paper examines the problem of code-generation for Digital Signal Processors (DSPs). We make two major contributions. First, for an important class of DSP architectures, we propose an optimal O(n) algorithm for the tasks of register allocation and instruction scheduling for expression trees. Optimality is guaranteed by sufficient conditions derived from a structural representation of the processor Instruction Set Architecture (ISA). Second, we develop heuristics for the case when basic blocks are Directed Acyclic Graphs (DAGs).

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. V. Aho , S. C. Johnson , J. D. Ullman, Code Generation for Expressions with Common Subexpressions, Journal of the ACM (JACM), v.24 n.1, p.146-160, Jan. 1977 [doi>10.1145/321992.322001]
• 4: A. V. Aho , S. C. Johnson , J. D. Ullman, Code-generation for machines with multiregister operations, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.21-28, January 17-19, 1977, Los Angeles, California [doi>10.1145/512950.512953]
• 5: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 6: A. W. Appel , K. J. Supowit, Generalization of the Sethi-Ullman algorithm for register allocation, Software—Practice & Experience, v.17 n.6, p.417-421, June 1987 [doi>10.1002/spe.4380170607]
• 7: Guido Araujo , Sharad Malik, Optimal code generation for embedded memory non-homogeneous register architectures, Proceedings of the 8th international symposium on System synthesis, p.36-41, September 13-15, 1995, Cannes, France [doi>10.1145/224486.224493]
• 8: 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]
• 9: J. L. Bruno , T. Lassagne, The Generation of Optimal Code for Stack Machines, Journal of the ACM (JACM), v.22 n.3, p.382-396, July 1975 [doi>10.1145/321892.321901]
• 10: John Bruno , Ravi Sethi, Code Generation for a One-Register Machine, Journal of the ACM (JACM), v.23 n.3, p.502-510, July 1976 [doi>10.1145/321958.321971]
• 11: E. G. Coffman, Jr. , Ravi Sethi, Instruction Sets for Evaluating Arithmetic Expressions, Journal of the ACM (JACM), v.30 n.3, p.457-478, July 1983 [doi>10.1145/2402.322388]
• 12: FRASER, C., HANSON, D., AND PROEBSTING, T. 1993. Engineering a simple, efficient code generator. J. ACM 22, 12 (Mar.), 248-262.
• 13: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 14: Christoph M. Hoffmann , Michael J. O'Donnell, Pattern Matching in Trees, Journal of the ACM (JACM), v.29 n.1, p.68-95, Jan. 1982 [doi>10.1145/322290.322295]
• 15: David J. Kolson , Alexandru Nicolau , Nikil Dutt , Ken Kennedy, Optimal register assignment to loops for embedded code generation, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.1 n.2, p.251-279, April 1996 [doi>10.1145/233539.233542]
• 16: Dirk Lanneer , Marco Cornero , Gert Goossens , Hugo De Man, Data routing: a paradigm for efficient data-path synthesis and code generation, Proceedings of the 7th international symposium on High-level synthesis, p.17-22, May 18-20, 1994, Niagra-on-the-Lake, Ontario, Canada
• 17: Phil Lapsley , Jeff Bier , Amit Shinham , Edward A. Lee , Amit Shoham , Amit Shohsm, DSP Processor Fundamentals: Architectures and Features, Wiley-IEEE Press, 1996
• 18: LEE, E.A. 1988. Programmable DSP architectures: Part I. IEEE ASSP Mag., 4-19.
• 19: LEE, E.A. 1989. Programmable DSP architectures: Part II. IEEE ASSP Mag., 4-14.
• 20: 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
• 21: LIEM, C. M. T. AND P., P. 1994. Instruction-set matching and selection for DSP and ASIP code generation. In Proceedings of the European Design and Test Conference. 31-37.
• 22: Peter Marwedel , Gert Goossens, Code Generation for Embedded Processors, Kluwer Academic Publishers, Norwell, MA, 1995
• 23: Peter Marwedel, Tree-based mapping of algorithms to predefined structures, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.586-593, November 07-11, 1993, Santa Clara, California, United States
• 24: MOTOROLA, 1990. DSP56000/DSP56001 Digital Signal Processor User's Manual. Motorola Inc., Phoenix, AZ.
• 25: Bhaskaram Prabhala , Ravi Sethi, Efficient Computation of Expressions with Common Subexpressions, Journal of the ACM (JACM), v.27 n.1, p.146-163, Jan. 1980 [doi>10.1145/322169.322182]
• 26: SETHI, R. 1975. Complete register allocation problems. SIAM J. Comput. 4, 3 (Sept.), 226 -248.
• 27: Ravi Sethi , J. D. Ullman, The Generation of Optimal Code for Arithmetic Expressions, Journal of the ACM (JACM), v.17 n.4, p.715-728, Oct. 1970 [doi>10.1145/321607.321620]
• 28: Panos E. Papamichalis, Digital signal processing applications with the TMS320 family (vol. 2), Prentice-Hall, Inc., Upper Saddle River, NJ, 1991
• 29: TJIANG, S. 1993. An Olive Twig. Synopsys, Inc., Mountain View, CA.
• 30: WESS, B. 1990. On the optimal code generation for signal flow computation. In Proceedings of the International Conference on Proceedings of the International Conference on Circuits and Systems. 444-447.
• 31: WESS, B. 1992. Automatic instruction code generation based on trellis diagrams. In Proceedings of the International Conference on Proceedings of the International Conference on Circuits and Systems. 645-648.
• 32: ZIVOJNOVIC, V., VELARDE, J., AND SCLAAGER, C. 1994. DSPstone, a DSP benchmarking methodology. Aachen University of Technology, Aachen, Germany.

INDEX TERMS

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

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

General Terms:
Algorithms

Keywords:
code generation, register allocation, scheduling