Optimal code generation for embedded memory non-homogeneous register architectures

ABSTRACT

Abstract: This paper examines the problem of code generation for expression trees on non-homogeneous register set architectures. It proposes and proves the optimality of an O(n) algorithm for the tasks of instruction selection, register allocation and scheduling on a class of architectures defined as the [1,/spl infin/] model. Optimality is guaranteed by sufficient conditions derived from the register transfer graph (RTG), a structural representation of the architecture which depends exclusively on the processor instruction set architecture (ISA). Experimental results using the TMS320C25 as the target processor show the efficacy of the approach.

REFERENCES

• 1: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 2: 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
• 3: 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]
• 4: B. Wess. Automatic instruction code generation based on trellis diagrams. In Proc. Int. Conf. Circuits and Systems, volume 2, pages 645-648, 1992.
• 5: 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]
• 6: C.W. Fraser, D.R. Hanson, and T.A. Proebsting. Engineering a simple, efficient code generator. Journal of the A CM, 22(12):248-262, March 1993.
• 7: Tjiang S.W.K. An olive twig. Technical report, Synopsys Inc., 1993.
• 8: 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]
• 9: V. Zivojnovic, J.M. Velarde, and C. Scl~ger. DSP- stone, a DSP benchmarking methodology. Technical report, Aachen University of Thecnology, August 1994.
• 10: Stan Liao , Srinivas Devadas , Kurt Keutzer , Steve Tjiang , Albert Wang, Storage assignment to decrease code size, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.186-195, June 18-21, 1995, La Jolla, California, United States

INDEX TERMS

Primary Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION
      B.5.1 Design
          Subjects: Arithmetic and logic units

Additional Classification:
  C. Computer Systems Organization
  C.0 GENERAL
      Subjects: Instruction set design (e.g., RISC, CISC, VLIW)

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

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

General Terms:
Algorithms, Design, Performance, Theory, Verification

Keywords:
TMS320C25 processor, [1, /spl infin/] model, computational complexity, computer architecture, embedded memory nonhomogeneous register architectures, expression trees, graph theory, instruction selection, instruction set architecture, instruction sets, microprocessor chips, optimal code generation, optimisation, processor scheduling, register allocation, register transfer graph, scheduling, storage allocation, structural representation, sufficient conditions