Storage assignment to decrease code size

ABSTRACT

DSP architectures typically provide indirect addressing modes with auto-increment and decrement. In addition, indexing mode is not available, and there are usually few, if any, general-purpose registers. Hence, it is necessary to use address registers and perform address arithmetic to access automatic variables. Subsuming the address arithmetic into auto-increment and auto-decrement modes improves the size of the generated code.In this paper we present a formulation of the problem of optimal storage assignment such that explicit instructions for address arithmetic are minimized. We prove that for the case of a single address register the decision problem is NP-complete. We then generalize the problem to multiple address registers. For both cases heuristic algorithms are given. Our experimental results indicate an improvement of 3.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 3: G. Araujo, S. Devadas, K. Keutzer, S. Liao, S. Malik, A. Sudarsanam, S. Tjiang, and A. Wang. Challenges in code generation for embedded processors. In P. Marwedel and G. Goossens, editors, Code Generation for Embedded Processors. Kluwer Academic Publishers, 1995. In press.
• 4: John R. Ellis, Bulldog: a compiler for VLSI architectures, MIT Press, Cambridge, MA, 1986
• 5: J. A. Fisher. Trace Scheduling: A Technique for Global Microcode Compaction. IEEE Trnsactions on Computers, C-30(7):478-490, 1981.
• 6: Jack G. Ganssle, The Art of Programming Embedded Systems, Academic Press, Inc., Orlando, FL, 1991
• 7: G. Goossens, J. Rabaey, F. Catthoor, J Vanhoof, R. Jain, H. De Man, and J. Vandewalle. A Computer- Aided Design Methodology for Mapping DSP Algorithms onto Custom Multiprocessor Architectures. In Proceedings of IEEE International Symposium on Circuits and Systems, pages 924-925, May 1986.
• 8: S. Y. Liao , S. Devadas , K. Keutzer, Code density optimization for embedded DSP processors using data compression techniques, Proceedings of the 16th Conference on Advanced Research in VLSI (ARVLSI'95), p.272, March 27-29, 1995
• 9: Stan Liao , Srinivas Devadas , Kurt Keutzer , Steve Tjiang , Albert Wang, Code optimization techniques for embedded DSP microprocessors, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.599-604, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217596]
• 10: C. Liem, T. May, and P. Paulin. Instruction-Set Matching and Selection for DSP and ASIP Code Generation. In Proceedings of European Design and Test Conference, March 1994.
• 11: Kenneth Edward Rimey , Paul Hilfinger, A compiler for application-specific signal processors, 1989
• 12: Robert Wilson , Robert French , Christopher Wilson , Saman Amarasinghe , Jennifer Anderson , Steve Tjiang , Shih Liao , Chau Tseng , Mary Hall , Monica Lam , John Hennessy, The SUIF Compiler System: a Parallelizing and Optimizing Research Compiler, Stanford University, Stanford, CA, 1994

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.2 Language Classifications

          Nouns: C
      D.3.4 Processors
          Subjects: Compilers

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

General Terms:
Algorithms, Experimentation, Languages, Theory, Verification