Compiler techniques for code compaction

In recent years there has been an increasing trend toward the incorporation of computers into a variety of devices where the amount of memory availabl e is limited. This makes it desirable to try to reduce the size of applicat ions where possible. This article explores the use of compiler techniques t o accomplish code compaction to yield smaller executables. The main contrib ution of this article is to show that careful, aggressive, interprocedural optimization, together with procedural abstraction of repeated code fragmen ts, can yield significantly better reductions in code size than previous ap proaches, which have generally focused on abstraction of repeated instructi on 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 c an be more flexible in its treatment of what code fragments are considered equivalent. Our ideas have been implemented in the form of a binary-rewriti ng tool that reduces the size of executables by about 30% on the average.