Optimizing for reduced code space using genetic algorithms
Keith D. Cooper, Philip J. Schielke, Devika Subramanian · 1999
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.
Cited by 316 works. doi:10.1145/314403.314414 Open-access PDF
Authors
References
- Adaptation in Natural and Artificial Systems
- Genetic Algorithms in Search, Optimization and Machine Learning
- Handbook of Genetic Algorithms
- An Introduction to Genetic Algorithms
- Computer methods for mathematical computations
- Register allocation via coloring
- Efficiently computing static single assignment form and the control dependence graph
- Constant propagation with conditional branches
- Global optimization by suppression of partial redundancies
- Improvements to graph coloring register allocation