| For memory constrained environments like embedded systems, optimization for program size is often as important as, if not more important than, optimization for execution speed.;A common technique for compacting code is procedural abstraction. Equivalent code fragments are identified and abstracted into a procedure. The standard algorithm for identifying these fragments is based on suffix trees. We propose in this dissertation the calculation of suffix trees over the program text not in the common top-down fashion, but reversed, i.e. bottom-up. With this simple modification, not only can equivalent fragments be identified, but also fragments equivalent to (possibly often differently long) suffixes of the longest fragments. A longest fragment is then abstracted, and all fragments are replaced by procedure calls to their corresponding start instruction somewhere in the abstracted procedure. This allows us to harvest more and longer fragments than with standard suffix trees, improving code size reductions by 8.277% on average eventually further resulting in 0.283% smaller programs.;Research in the field of program size optimization concentrates on code size. We present in this dissertation also a stack size reduction algorithm for recursive functions. Formal parameters and local variables that are dead at recursive calls can be declared global so that only one instance exists independent of the call depth. By this, 70% of popular recursive algorithms could be optimized.;The purpose of visualizations is to make obvious what is not. Data is an obvious candidate for visualization, but software can be visualized as well. In this dissertation, we visualize the computational processes of procedural abstraction by drawing abstracted fragments in their original programs We show how these visualizations help us better understand and eventually improve our procedural abstraction implementations. |
