Keith D. Cooper
Philip J. Schielke
Devika Subramanian
Abstract
Code space is a critical issue facing designers of software for embedded systems. Many traditional compiler optimizations are designed to reduce the execution time of compiled code, but not necessarily the size of the compiled code. Further, different results can be achieved by running some optimizations more than once and changing the order in which optimizations are applied. Register allocation only complicates matters, as the interactions between different optimizations can cause more spill code to be generated. The compiler for embedded systems, then, must take care to use the best sequence of optimizations to minimize code space.Since much of the code for embedded systems is compiled once and then burned into ROM, the software designer will often tolerate much longer compile times in the hope of reducing the size of the compiled code. We take advantage of this by using a genetic algorithm to find optimization sequences that generate small object codes. The solutions generated by this algorithm are compared to solutions found using a fixed optimization sequence and solutions found by testing random optimization sequences. Based on the results found by the genetic algorithm, a new fixed sequence is developed to reduce code size. Finally, we explore the idea of using different optimization sequences for different modules and functions of the same program.
- 1 Steven John Beaty. b~struction Scheduling Using Genetic Algorithms. PhD thesis, Colorado State University, Fort Collins, Colorado, 1991.Google Scholar
- 2 Preston Briggs and Keith D. Cooper. Effective partial redundancy elimination. SIGPLAN Notices, 29(6):159- 170, June 1994. Proceedings ol the A CM SIGPLAN '94 Conference on Programming Language Design and Implementation. Google ScholarDigital Library
- 3 Preston Briggs, Keith D. Cooper, and L. Taylor Simpson. Value numbering. Software - Practice and Experience, 27(6):701-724, June 1997. Google ScholarDigital Library
- 4 Preston Briggs, Keith D Cooper, and Linda Torczon. Improvements to graph coloring register allocation. A CM Transactions on Programming Languages and Systems, 16(3):428-455, May 1994. Google ScholarDigital Library
- 5 Gregory J. Chaitin, Marc A. Auslander, Ashok K. Chandra, John Cocke, Martin E. Hopkins, and Peter W. Markstein. Register allocation via coloring. Computer Languages, 6(1):47-57, January 1981.Google ScholarCross Ref
- 6 Keith D. Cooper and L. Taylor Simpson. Scc-based value numbering. Technical Report CRPC-TR95636- S, Center for Research on Parallel Computation, Rice University, 1995.Google Scholar
- 7 Keith D. Cooper, L. Taylor Simpson, and Chris A Vick. Operator strength reduction. Technical Report CRPC- TR95635-S, Center for Research on Parallel Computation, Rice University, 1995.Google Scholar
- 8 Ron Cytron, Jeanne Ferrante, Barry K. Rosen, Mark N. Wegman, and F. Kenneth Zadeck. Et~ciently computing static single assignment form and the control dependence graph. A CM Transactions on Programming Languages and Systems, 13(4):451-490, October 1991. Google ScholarDigital Library
- 9 Lawrence Davis, editor. Handbook of Genetic Algorithms. Van Nostrand Reinhold, 1991.Google Scholar
- 10 Karl-Heinz Drechsler and Manfred P. Stadel. A solution to a problem with Morel and Renvoise's "Global optimization by suppression of partial redundancies". A CM Transactions on Programming Languages and Systems, 10(4):635--640, October 1988. Google ScholarDigital Library
- 11 Karl-Heinz Drechsler and Manfred P. Stadel. A variation of Knoop, Rfithing, and Steffen's "lazy code motion". SIGPLAN Notices, 28(5):29-38, May 1993. Google ScholarDigital Library
- 12 G. E. Forsythe, M. A. Malcolm, and C. B. Moler. Computer Methods }or Mathematical Computations. Prentice-Hall, Inc., Englewood Cliffs, NJ, 1977. Google ScholarDigital Library
- 13 David E. Goldberg. Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesly, 1989. Google ScholarDigital Library
- 14 John H. Holland. Adaptation in natural and artificial systems. University of Michigan Press, 1975. Google ScholarDigital Library
- 15 Ken Kennedy. A survey of data flow analysis techniques, in Steven S. Muchnick and Neil D. Jones, editors, Program Flow Analysis: Theory and Applications. Prentice-HMl, 1981.Google Scholar
- 16 Jens Knoop, Oliver Riithing, and Bernhard Stetfen. Optimal code motion: Theory and practice. A CM Transactions on Programming Languages and Systems, 16(4):1117-1155, July 1994. Google ScholarDigital Library
- 17 Melanie Mitchell. An introduction to genetic algorithms. MIT Press, 1998. Google ScholarDigital Library
- 18 Etienne Morel and Claude Renvoise. Global optimization by suppression of partial redundancies. Communications of the A CM, 22(2):96-103, February 1979. Google ScholarDigital Library
- 19 Andy P Nisbet. GAPS: A compiler framework for genetic algorithm (GA) optimised parallelisation. In Poster Session at The International Conference and Exhibition on High-Performance Computing and Networking, HPCN Europe '98, 1998. Google ScholarDigital Library
- 20 Randolph G. Scarborough and Harwood G. Kolsky. Improved optimization of FORTRAN object programs. IBM Journal of Research and Development, pages 660- 676, November 1980.Google Scholar
- 21 L. Taylor Simpson. Value-Driven Redundancy Elimination. PhD thesis, Rice University, May 1996. Google ScholarDigital Library
- 22 Mark N. Wegman and F. Kenneth Zadeck. Constant propagation with conditional branches. A CM Transactions on Programming Languages and Systems, 13(2):181-210, April 1991. Google ScholarDigital Library
Index Terms
- Optimizing for reduced code space using genetic algorithms
Recommendations
Optimizing for reduced code space using genetic algorithms
LCTES '99: Proceedings of the ACM SIGPLAN 1999 workshop on Languages, compilers, and tools for embedded systemsCode space is a critical issue facing designers of software for embedded systems. Many traditional compiler optimizations are designed to reduce the execution time of compiled code, but not necessarily the size of the compiled code. Further, different ...
Optimising the fit of stack overflow code snippets into existing code
GECCO '20: Proceedings of the 2020 Genetic and Evolutionary Computation Conference CompanionSoftware developers often reuse code from online sources such as Stack Overflow within their projects. However, the process of searching for code snippets and integrating them within existing source code can be tedious. In order to improve efficiency ...
Prioritising Refactoring Using Code Bad Smells
ICSTW '11: Proceedings of the 2011 IEEE Fourth International Conference on Software Testing, Verification and Validation WorkshopsWe investigated the relationship between six of Fowler et al.'s Code Bad Smells (Duplicated Code, Data Clumps, Switch Statements, Speculative Generality, Message Chains, and Middle Man) and software faults. In this paper we discuss how our results can ...
Comments