Compiling with code-size constraints

ABSTRACT

Most compilers ignore the problems of limited code space in embedded systems. Designers of embedded software often have no better alternative than to manually reduce the size of the source code or even the compiled code. Besides being tedious and error prone, such optimization results in obfuscated code that is difficult to maintain and reuse. In this paper, we present a step towards code-size-aware compilation. We phrase register allocation and code generation as an integer linear programming problem where the upper bound on the code size can simply be expressed as an additional constraint. The resulting compiler, when applied to six commercial microcontroller programs, generates code nearly as compact as carefully crafted code.

REFERENCES

• 1: Andrew W. Appel , Lal George, Optimal spilling for CISC machines with few registers, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.243-253, June 2001, Snowbird, Utah, United States
• 2: Oren Avissar , Rajeev Barua , Dave Stewart, Heterogeneous memory management for embedded systems, Proceedings of the 2001 international conference on Compilers, architecture, and synthesis for embedded systems, November 16-17, 2001, Atlanta, Georgia, USA [doi>10.1145/502217.502223]
• 3: Dennis Brylow , Niels Damgaard , Jens Palsberg, Static checking of interrupt-driven software, Proceedings of the 23rd International Conference on Software Engineering, p.47-56, May 12-19, 2001, Toronto, Ontario, Canada
• 4: Fourer, R., Gay, D. M., and Kernighan, B. W. 1993. AMPL: A Modeling Language for Mathematical Programming. The Scientific Press.
• 5: David W. Goodwin , Kent D. Wilken, Optimal and near-optimal global register allocations using 0–1 integer programming, Software—Practice & Experience, v.26 n.8, p.929-965, Aug. 1996 [doi>10.1002/(SICI)1097-024X(199608)26:8<929::AID-SPE40>3.3.CO;2-K]
• 6: Timothy Kong , Kent D. Wilken, Precise register allocation for irregular architectures, Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture, p.297-307, November 1998, Dallas, Texas, United States
• 7: Kremer, U. 1997. Optimal and near-optimal solutions for hard compilation problems. Parallel Processing Letters 7, 4.
• 8: 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
• 9: 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]
• 10: Liberatore, V., Farach-Colton, M., and Kremer, U. 1999. Evaluation of algorithms for local register allocation. 137--152.
• 11: Rajeev Motwani , Krishna V. Palem , Vivek Sarkar , Salem Reyen, Combining Register Allocation and Instruction Scheduling, Stanford University, Stanford, CA, 1995
• 12: Mayur Naik , Jens Palsberg, Compiling with code-size constraints, Proceedings of the joint conference on Languages, compilers and tools for embedded systems: software and compilers for embedded systems, June 19-21, 2002, Berlin, Germany
• 13: Palsberg, J. and Wallace, M. 2002. Reverse engineering of real-time assembly code. Manuscript.
• 14: Jinpyo Park , Je-Hyung Lee , Soo-Mook Moon, Register Allocation for Banked Register File, Proceedings of the ACM SIGPLAN workshop on Languages, compilers and tools for embedded systems, p.39-47, August 2001, Snow Bird, Utah, United States
• 15: 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
• 16: John Ruttenberg , G. R. Gao , A. Stoutchinin , W. Lichtenstein, Software pipelining showdown: optimal vs. heuristic methods in a production compiler, Proceedings of the ACM SIGPLAN 1996 conference on Programming language design and implementation, p.1-11, May 21-24, 1996, Philadelphia, Pennsylvania, United States
• 17: 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 [doi>10.1145/502217.502221]
• 18: Artour Stoutchinin, An Integer Linear Programming Model of Software Pipelining for the MIPS R8000 Processor, Proceedings of the 4th International Conference on Parallel Computing Technologies, p.121-135, September 08-12, 1997
• 19: Ashok Sudarsanam , Sharad Malik, Simultaneous reference allocation in code generation for dual data memory bank ASIPs, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.5 n.2, p.242-264, April 2000 [doi>10.1145/335043.335047]
• 20: Zilog. Z8 Microcontroller User's Manual. See http://www.zilog.com.

INDEX TERMS

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

General Terms:
Algorithms, Measurement, Performance

Keywords:
Banked architecture, integer linear programming, register allocation, space optimization