Storage assignment to decrease code size

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Storage assignment to decrease code size

Full text

Pdf (122 KB)

Source

ACM Transactions on Programming Languages and Systems (TOPLAS) archive
Volume 18 , Issue 3 (May 1996) table of contents

Pages: 235 - 253

Year of Publication: 1996

ISSN:0164-0925

Authors

Stan Liao	Synopsys, Inc.
Srinivas Devadas	Massachusetts Institute of Technology
Kurt Keutzer	Synopsys, Inc.
Steven Tjiang	Synopsys, Inc.
Albert Wang	Synopsys, Inc.

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 52, Citation Count: 27

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/229542.229543 What is a DOI?

ABSTRACT

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 registers and perform address arithmetic to access automatic variables. Subsuming the address arithmetic into autoincrement and decrement modes improves the size of the generated code. In this article 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, even for a single basic block. We then generalize the problem to multiple address registers. For both cases heuristic algorithms are given, and experimental results are presented.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked 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	ARAUJO, G., DEVADAS, S., KEUTZER, K., LIAO, S., MALIK, S., SUDARSANAM, A., TJIANG, S., AND WANG, A. 1995. Challenges in code generation for embedded processors. In Code Generation for Embedded Processors, P. Marwedel and G. Goossens, Eds. Kluwer Academic, Boston, Mass., 48-64.
	4	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]
	5	David Callahan , Brian Koblenz, Register allocation via hierarchical graph coloring, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.192-203, June 24-28, 1991, Toronto, Ontario, Canada
	6	CHAITIN, G., AUSLANDER, M., CHANDRA, A., COCKE, J., HOPKINS, M., AND MARKSTEIN, P. 1981. Register allocation via coloring. Comput. Lang. 6, 47-57.
	7	John R. Ellis, Bulldog: a compiler for VLSI architectures, MIT Press, Cambridge, MA, 1986
	8	FISHER, J. A. 1981. Trace scheduling: A technique for global microcode compaction. IEEE Trans. Comput. C-30, 7, 478-490.
	9	Christopher W. Fraser , Eugene W. Myers , Alan L. Wendt, Analyzing and compressing assembly code, Proceedings of the 1984 SIGPLAN symposium on Compiler construction, p.117-121, June 17-22, 1984, Montreal, Canada
	10	Jack G. Ganssle, The Art of Programming Embedded Systems, Academic Press, Inc., Orlando, FL, 1991
	11	GOOSSENS, G., RABAEY, J., CATTHOOR, F., VANHOOF, J., JAIN, R., MAN, H. D., AND VANDEWALLE, J. 1986. A computer-aided design methodology for mapping DSP algorithms onto custom multiprocessor architectures. In Proceedings of the 1986 IEEE International Symposium on Circuits and Systems. IEEE, New York, 924-925.
	12	Stan Yi-Huang Liao , Srinivas Devadas, Code generation and optimization for embedded digital signal processors, 1996
	13	LIEM, C., MAY, T., AND PAULIN, P. 1994. Instruction-set matching and selection for DSP and ASIP code generation. In Proceedings of the 1994 European Design and Test Conference. IEEE, New York.
	14	Kenneth Edward Rimey , Paul Hilfinger, A compiler for application-specific signal processors, 1989
	15	ZIVOJNOVIC, V., VELARDE, J. M., AND SCHLAGER, C. 1994. DSPstone: A DSP-oriented benchmarking methodology. In Proceedings of the 5th International Conference on Signal Processing Applications and Technology. Miller Freeman, San Francisco, Calif.
	16	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

CITED BY 27

	Sreeranga P. Rajan , Masahiro Fujita , Ashok Sudarsanam , Sharad Malik, Development of an optimizing compiler for a Fujitsu fixed-point digital signal processor, Proceedings of the seventh international workshop on Hardware/software codesign, p.2-6, March 1999, Rome, Italy
	Keith D. Cooper , Nathaniel McIntosh, Enhanced code compression for embedded RISC processors, ACM SIGPLAN Notices, v.34 n.5, p.139-149, May 1999
	Nikil Dutt , Alex Nicolau , Hiroyuki Tomiyama , Ashok Halambi, New directions in compiler technology for embedded systems (embedded tutorial), Proceedings of the 2001 conference on Asia South Pacific design automation, p.409-414, January 2001, Yokohama, Japan
	S. Liao , K. Keutzer , S. Tjiang , S. Devadas, A new viewpoint on code generation for directed acyclic graphs, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.3 n.1, p.51-75, Jan. 1998
	Mayur Naik , Jens Palsberg, Compiling with code-size constraints, ACM SIGPLAN Notices, v.37 n.7, July 2002
	Wei-Kai Cheng , Youn-Long Lin, Addressing optimization for loop execution targeting DSP with auto-increment/decrement architecture, Proceedings of the 11th international symposium on System synthesis, p.15-20, December 02-04, 1998, Hsinchu, Taiwan, China
	Oliver Rüthing , Jens Knoop , Bernhard Steffen, Sparse code motion, Proceedings of the 27th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.170-183, January 19-21, 2000, Boston, MA, USA
	Erik Eckstein , Andreas Krall, Minimizing cost of local variables access for DSP-processors, ACM SIGPLAN Notices, v.34 n.7, p.20-27, July 1999
	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
	Ashok Sudarsanam , Sharad Malik , Masahiro Fujita, A retargetable compilation methodology for embedded digital signal processors using a machine-dependent code optimizaton library, Readings in hardware/software co-design, Kluwer Academic Publishers, Norwell, MA, 2001
	Jan Sjödin , Carl von Platen, Storage allocation for embedded processors, Proceedings of the 2001 international conference on Compilers, architecture, and synthesis for embedded systems, November 16-17, 2001, Atlanta, Georgia, USA
	Bengu Li , Rajiv Gupta, Simple offset assignment in presence of subword data, Proceedings of the 2003 international conference on Compilers, architecture and synthesis for embedded systems, October 30-November 01, 2003, San Jose, California, USA
	J.-Y. Lee , I.-C. Park, Address code generation for DSP instruction-set architectures, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.8 n.3, p.384-395, July 2003
	Xiaotong Zhuang , ChokSheak Lau , Santosh Pande, Storage assignment optimizations through variable coalescence for embedded processors, ACM SIGPLAN Notices, v.38 n.7, July 2003
	Erik Eckstein , Bernhard Scholz, Addressing mode selection, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, March 23-26, 2003, San Francisco, California
	V. Krishna Nandivada , Jens Palsberg, Efficient spill code for SDRAM, Proceedings of the 2003 international conference on Compilers, architecture and synthesis for embedded systems, October 30-November 01, 2003, San Jose, California, USA
	Amit Rao , Santosh Pande, Storage assignment optimizations to generate compact and efficient code on embedded DSPs, ACM SIGPLAN Notices, v.34 n.5, p.128-138, May 1999
	Xiaotong Zhuang , Santosh Pande, Power-efficient prefetching via bit-differential offset assignment on embedded processors, ACM SIGPLAN Notices, v.39 n.7, July 2004
	Mayur Naik , Jens Palsberg, Compiling with code-size constraints, ACM Transactions on Embedded Computing Systems (TECS), v.3 n.1, p.163-181, February 2004
	Yoonseo Choi , Taewhan Kim, Address assignment combined with scheduling in DSP code generation, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA
	Sean Leventhal , Lin Yuan , Neal K. Bambha , Shuvra S. Bhattacharyya , Gang Qu, DSP address optimization using evolutionary algorithms, Proceedings of the 2005 workshop on Software and compilers for embedded systems, p.91-98, September 29-October 01, 2005, Dallas, Texas
	O. Ozturk , M. Kandemir , S. Tosun, An ILP based approach to address code generation for digital signal processors, Proceedings of the 16th ACM Great Lakes symposium on VLSI, April 30-May 01, 2006, Philadelphia, PA, USA
	Desiree Ottoni , Guilherme Ottoni , Guido Araujo , Rainer Leupers, Offset assignment using simultaneous variable coalescing, ACM Transactions on Embedded Computing Systems (TECS), v.5 n.4, p.864-883, November 2006
	Milenko Drinić , Darko Kirovski , Hoi Vo, PPMexe: Program compression, ACM Transactions on Programming Languages and Systems (TOPLAS), v.29 n.1, p.3-es, January 2007
	Xiaotong Zhuang , Santosh Pande, Power-efficient prefetching for embedded processors, ACM Transactions on Embedded Computing Systems (TECS), v.6 n.1, February 2007
	Guilin Chen , Mahmut Kandemir, Optimizing Address Code Generation for Array-Intensive DSP Applications, Proceedings of the international symposium on Code generation and optimization, p.141-152, March 20-23, 2005
	Chris J. Michael , Maciej Brodowicz , Thomas Sterling, Improving code compression using clustered modalities, Proceedings of the 46th Annual Southeast Regional Conference on XX, March 28-29, 2008, Auburn, Alabama