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.
- 1.A. Aho, J. Hopcroft, and J. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974. Google ScholarDigital Library
- 2.A. Aho, R. Sethi, and J. Ullman. Compilers Principles, Techniques and Tools. Addison-Wesley, 1986. Google ScholarDigital Library
- 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.Google Scholar
- 4.John R. Ellis. A Compiler for VLiW Architectures. MIT Press, 1985. Google ScholarDigital Library
- 5.J. A. Fisher. Trace Scheduling: A Technique for Global Microcode Compaction. IEEE Trnsactions on Computers, C-30(7):478-490, 1981.Google ScholarDigital Library
- 6.J. G. Ganssle. The Art of Programming Embedded Systems. San Diego, CA: Academic Press, Inc., 1992. Google ScholarDigital Library
- 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.Google Scholar
- 8.S. Liao, S. Devadas, and K. Keutzer. Code Density Optimization for Embedded DSP Processors Using Data Compression Techniques. In Proceedings of the Chapel Hill Conference on Advanced Research in VLSI, March 1995. Google ScholarDigital Library
- 9.S. Liao, S. Devadas, K. Keutzer, S. Tjiang, and A. Wang. Code Optimization Techniques for Embedded DSP Microprocessors. In Proceedings of the 32nd Design Automation Conference, June 1995. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 11.K. Rimey. A Compiler for Application-Specific signal Processors. PhD thesis, University of California, Berkeley, 1989. Google ScholarDigital Library
- 12.R. Wilson, R. French, C. Wilson, S. Amarasinghe, J. Anderson, S. Tjiang, S.-W. Liao, C.-W. Tseng, M. Hall, M. Lam, and J. Hennessy. SUIF: A Parallelizing and Optimizing Research Compiler. Technical Report CSL-TR-94-620, Stanford University, May 1994. Google ScholarDigital Library
Index Terms
- Storage assignment to decrease code size
Recommendations
Storage assignment to decrease code size
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 ...
Storage assignment to decrease code size
DSP architectures typically provide indirect addressing modes with autoincrement and decrement. In addition, indexing mode is generally not available, and there are usually few, if any, general-purpose registers. Hence, it is necessary to use address ...
Reducing code size through address register assignment
In DSP processors, minimizing the amount of address calculations is critical for reducing code size and improving performance, since studies of programs have shown that instructions that manipulate address registers constitute a significant portion of ...
Comments