1 Code Size reduction by difference classification and customized look-up table generation

Code size has become an important constraint for applications on mobile devices. Not only should the applications be very responsive and execute fast, they should also consume low power, and be reasonably compact in size to fit in the limited memory of the mobile devices. In this paper we focus on a specific opportunity of code size optimization that is detected in software for mobile devices like wireless networking protocols, modems, etc. These applications have large amount of code-regions across the control-flow graph that are inherently similar, but with slight differences that are compile time constants. Examples of such similar code regions are: case statements labeled by “jump tables”, tail regions that merge to a common point, cascaded sequence of similar code-regions with unique predecessor-successor relationship, etc. This paper presents a novel approach where similar code-regions across the control flow graph are classified into disjoint sets based on their differences, and then replaced by a single representative code-region with the differences encoded in customized look-up tables resulting in reduced code size. The methodology shows remarkable reduction in code size for large switch-case constructs that have very similar case statements. Implementation is done in the Open64 compiler, even though it could be integrated with other compilers (e.g., GCC). We also provide some results of code size reduction, which are in the range of 30 % to 80 % for pure text (instructions only), and 5 % to 60 % for total text (instructions and read only data), achieved by the algorithm on some of the functions in software applications for mobile devices. 1