The authors present an aggressive approach to code compaction. Starting with an effective interprocedural optimizer, they then show that many common interprocedural optimizations can be combined with code factoring to significantly reduce the size of programs. Experimental results show size reductions of close to 30 percent compared to non-compacted programs. Code factoring analyzes the instructions within the control flow graph of a program. The algorithms account for trivial differences in program fragments, such as register renaming, and for architecture-dependent common code fragments, such as the procedure prologues and epilogues defined by a calling convention.
Code factoring can introduce new procedures that can be called from several sites.
Factoring can also eliminate common instruction sequences by moving them to points in the control flow graph that either dominate or postdominate their original sites. In this case, no new procedures or calls have to be introduced. Perhaps not surprisingly, some programs run faster when compacted, while others run slower. The speedups may be due to the use of a number of effective interprocedural analysis algorithms that may speed up a program even without the code factoring phase. Also, some code motion techniques are low-overhead.