Compiler Techniques for Code Compaction
Department of Computer Science
University of Arizona
Tucson, AZ 85721, U.S.A.
Bjorn De Sutter
Department of Electronics and Information Systems
University of Ghent
B-9000 Ghent, Belgium
In recent years there has been an increasing trend towards the incorporation of computers into a variety of devices where the amount of memory available is limited. This makes it desirable to try to reduce the size of applications where possible. This paper explores the use of compiler techniques to accomplish code compaction to yield smaller executables. The main contribution of this paper is to show that careful, aggressive, interprocedural optimization, together with procedural abstraction of repeated code fragments, can yield significantly better reductions in code size than previous approaches, which have generally focused on abstraction of repeated instruction sequences. We also show how ``equivalent'' code fragments can be detected and factored out using conventional compiler techniques, and without having to resort to purely linear treatments of code sequences as in suffix-tree-based approaches, thereby setting up a framework for code compaction that can be more flexible in its treatment of what code fragments are considered equivalent. Our ideas have been implemented in the form of a binary-rewriting tool that reduces the size of executables by about 30% on the average.