Take a look at the new version of this page: [ beta version ]. Tell us what you think.

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 which is difficult to maintain and reuse. In this paper, we present a code-size-directed compiler. 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. Our experiments show that our compiler, when applied to two commercial microcontroller programs, generates code as compact as carefully crafted code.

REFERENCES

• 1: CPLEX mixed integer optimizer. www.ilog.com/products/cplex/product/mip.cfm
• 2: Greenhill Manufacturing. www.greenhillmfg.com
• 3: Zilog, Inc. www.zilog.com
• 4: 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
• 5: 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
• 6: R. Fourer, D. M. Gay, and B. W. Kernighan. AMPL: A Modeling Language for Mathematical Programming. The Scientific Press, 1993. www.ampl.com
• 7: 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]
• 8: 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
• 9: 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
• 10: 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]
• 11: Vincenzo Liberatore , Martin Farach-Colton , Ulrich Kremer, Evaluation of Algorithms for Local Register Allocation, Proceedings of the 8th International Conference on Compiler Construction, Held as Part of the European Joint Conferences on the Theory and Practice of Software, ETAPS'99, p.137-152, March 22-28, 1999
• 12: 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]
• 13: 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
• 14: 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
• 15: 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
• 16: 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]
• 17: 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
• 18: 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]

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