Abstract
DSP processors have address generation units that can perform address computation in parallel with other operations. This feature reduces explicit address arithmetic instructions, often required to access locations in the stack frame, through auto-increment and decrement addressing modes, thereby decreasing the code size. Decreasing code size in embedded applications is extremely important as it directly impacts the size of on-chip program memory and hence the cost of the system.
Effective utilization of auto-increment and decrement modes requires an intelligent placement of variables in the stack frame which is termed as “offset assignment”. Although a number of algorithms for efficient offset assignment have been proposed in the literature, they do not consider possible instruction reordering to reduce the number of address arithmetic instructions. In this paper, we propose an integrated approach that combines instruction reordering and algebraic transformations to reduce the number of address arithmetic instructions. The proposed approach has been implemented in the SUIF compiler framework. We conducted our experiments on a set of real programs. and compared its performance with that of Liao’s heuristic for Simple Offset Assignment (SOA), Tie-break SOA, Naive offset assignment, and Rao and Pande’s algebraic transformation approach.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aho, A.V., Sethi, R., Ullman, J.D.: Compilers Principles, Techniques and Tools. Addison Weseley, Reading (1988)
Atri, S., Ramanujam, J., Kandemir, M.: Improving offset assignment for embedded processors. In: Midkiff, S.P., Moreira, J.E., Gupta, M., Chatterjee, S., Ferrante, J., Prins, J.F., Pugh, B., Tseng, C.-W. (eds.) LCPC 2000. LNCS, vol. 2017, p. 158. Springer, Heidelberg (2000)
Bartley, D.: Optimizing stack frame accesses for processors with restricted addressing modes. Software Practice and Experience 22(2), 101–110 (1992)
Choi, Y., Kim, T.: Address assignment combined with scheduling in DSP code generation. In: Proc. of the Design Automation Conference, New Orleans, LA (June 2002)
Lee, C., Potkonjak, M., Mangione-Smith, W.H.: MediaBench: A tool for evaluating and synthesizing multimedia and communication systems. In: Proc. of the 30th Ann. Intl. Symp. on Microarchitecture (MICRO-30), Raleigh, NC (1997)
Leupers, R., Marwedel, P.: Algorithms for address assignment in DSP code generation. In: Intl. Conf. on Computer Aided Design, San Jose, CA (November 1996)
Leupers, R., David, F.: A Uniform Optimization technique for Offset Assignment. In: Proc. the 11th International Symposium on System Synthesis (1998)
Leupers, R.: Code generation for embedded processors. In: Proc. of the 13th Intl. Symp. on System Synthesis (September 2000)
Liao, S., Devadas, S., Keutzer, K., Tjiang, S., Wang, A.: Storage assignment to decrease code size. In: Proc. of 1995 ACM SIGPLAN Conference on Programming Language Design and Implementation, La Jolla, CA (June 1995)
Liao, S.: Code Generation and Optimization for Embedded Digital Signal Processors. Ph.D thesis, Department of EECS, Massachusetts Institute of Technology, Cambridge, MA (January 1996)
Muchnick, S.S.: Advanced Compiler Design and Implementation. Morgan Kauffman Publishers, San Francisco (1997)
Rao, A., Pande, S.: Storage assignment to generate compact and efficient code on embedded DSPs. In: Proc. 1999 ACM SIGPLAN Conference on Programming Language Design and Implementation, Montreal, Canada (June 1998)
Rao, A.: Compiler optimizations for storage assignment on embedded DSPs. Master’s Thesis, Dept. of ECECS, Univ. of Cincinnati, OH (October 1998)
Sarvani, V.V.N.S., Govindarajan, R.: Unified instruction reordering and algebraic transformations for minimum cost offset assignment. In: Student poster session, Programming Languages Design and Implementation, Berlin, Germany (June 2002)
Stanford University Intermediate Format, http://suif.stanford.edu
Sudarshanam, A., Malik, S.: Memory bank and register allocation in software synthesis of ASIPs. In: Proc. of 1997 ACM/IEEE Design Automation Conference on Computer-Aided Design, San Jose, CA, November 1997, pp. 388–392 (1997)
Sudarsanam, A., Liao, S., Devadas, S.: Analysis and evaluation of address arithmetic capabilities in custom DSP architectures. In: Proc. of the 1997 ACM/IEEE Design Automation Conference, Anaheim, CA, June 1997, pp. 297–292 (1997)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Sarvani, V.V.N.S., Govindarajan, R. (2003). Unified Instruction Reordering and Algebraic Transformations for Minimum Cost Offset Assignment. In: Krall, A. (eds) Software and Compilers for Embedded Systems. SCOPES 2003. Lecture Notes in Computer Science, vol 2826. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-39920-9_19
Download citation
DOI: https://doi.org/10.1007/978-3-540-39920-9_19
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-20145-8
Online ISBN: 978-3-540-39920-9
eBook Packages: Springer Book Archive