Storage assignment optimizations through variable coalescence for embedded processors

ABSTRACT

Modern embedded processors with dedicated address generation unit support memory access with indirect addressing mode with auto-increment and decrement. The auto-increment/decrement mode saves address arithmetic instructions.Liao et al [2][3] categorized this problem as simple offset assignment (SOA) problem and general offset assignment (GOA) problem, which involve storage layout of variables and assignment of address registers respectively proposing heuristic solutions. Later work [6][7] proposed improvements in the performance of Liao's solution by undertaking program and storage transformations that affect access sequence.The algorithms are incorporated into and evaluated on the commercial compiler provided by Motorola to boost code generation performance on the DSP 56k chip. Compared to previous approaches, variable coalescence with program reordering reduces SOA costs by 48% and GOA (2AR) costs by 66% for Mediabench and SPEC benchmarks. Moreover, we show that our approach obtains theoretically optimal solution (zero cost) for the GOA problem in 87% of the cases with just 2 address registers and in 94% of the cases with 3 address registers.

REFERENCES

• 1: David H. Bartley, Optimizing stack frame accesses for processors with restricted addressing modes, Software—Practice & Experience, v.22 n.2, p.101-110, Feb. 1992 [doi>10.1002/spe.4380220202]
• 2: 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
• 3: Stan Liao , Srinivas Devadas , Kurt Keutzer , Steven Tjiang , Albert Wang, Storage assignment to decrease code size, ACM Transactions on Programming Languages and Systems (TOPLAS), v.18 n.3, p.235-253, May 1996 [doi>10.1145/229542.229543]
• 4: A. Sudarsanam , S. Malik , S. Tjiang , S. Liao, Optimization of Embedded DSP Programs Using Post-Pass Data-Flow Analysis, Proceedings of the 1997 IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP '97) -Volume 1, p.695, April 21-24, 1997
• 5: Ashok Sudarsanam , Stan Liao , Srinivas Devadas, Analysis and evaluation of address arithmetic capabilities in custom DSP architectures, Proceedings of the 34th annual conference on Design automation, p.287-292, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266103]
• 6: Amit Rao , Santosh Pande, Storage assignment optimizations to generate compact and efficient code on embedded DSPs, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.128-138, May 01-04, 1999, Atlanta, Georgia, United States
• 7: A. Rao Compiler Optimizations for Storage Assignment on Embedded DSPs. Master's thesis, Dept. of ECECS, Univ. of Cincinnati, Oct. 1998.
• 8: Motorola, Inc., Motorola DSP56300 Family Optimizing C Compiler User's Manual.
• 9: Steven S. Muchnick, Advanced compiler design and implementation, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 10: Rainer Leupers , Peter Marwedel, Algorithms for address assignment in DSP code generation, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.109-112, November 10-14, 1996, San Jose, California, United States
• 11: Sathishkumar Udayanarayanan , Chaitali Chakrabarti, Address code generation for digital signal processors, Proceedings of the 38th conference on Design automation, p.353-358, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.378521]
• 12: Sunil Atri , J. Ramanujam , Mahmut T. Kandemir, Improving Offset Assignment for Embedded Processors, Proceedings of the 13th International Workshop on Languages and Compilers for Parallel Computing-Revised Papers, p.158-172, August 10-12, 2000
• 13: Guilherme Ottoni , Sandro Rigo , Guido Araujo , Subramanian Rajagopalan , Sharad Malik, Optimal Live Range Merge for Address Register Allocation in Embedded Programs, Proceedings of the 10th International Conference on Compiler Construction, p.274-288, April 02-06, 2001
• 14: Guido Araujo , Ashok Sudarsanam , Sharad Malik, Instruction Set Design and Optimizations for Address Computation in DSP Architectures, Proceedings of the 9th international symposium on System synthesis, p.105, November 06-08, 1996
• 15: Catherine Gebotys, DSP address optimization using a minimum cost circulation technique, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.100-103, November 09-13, 1997, San Jose, California, United States
• 16: Leupers, R., Basu, A., and Marwedel, P, "Optimized array index computation in DSP programs", In Proceedings of the ASP-DAC (February 1998), IEEE.
• 17: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

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

General Terms:
Design, Performance

Keywords:
GOA, SOA, storage assignment, variable coalescence