Machine Code Optimization

Candidate: Goss,Clinton Francis

Abstract

This dissertation explores classes of compiler optimization techniques which are applicable late in the compilation process, after all executable code for a program has been linked. We concentrate on techniques which, for various reasons, cannot be applied earlier in the compilation process. We begin by demonstrating the need for optimizations at this level in the UNIX('(REGTM)) programming environment. We then describe a Machine Code Optimizer which improves code in executable task files in that environment. The specific details of certain algorithms are then described: code elimination to remove unreachable code, code distribution to re-order sections of code, operand reduction which converts operands to use more advantageous addressing modes available on the target architecture, and macro compression which collapses common sequences of instructions. We show that the problem of finding optimal solutions for code distribution is NP-Complete and discuss heuristics for practical solutions. We then describe the implementation of a Machine Code Optimizer containing the code elimination, code distribution, and operand reduction algorithms. This optimizer operates in a production environment and incorporates a machine independent architecture representation which allows it to be ported across a large class of machines. We demonstrate the portability of the Machine Code Optimizer to the Motorola MC68000('(REGTM)) and the Digital VAX-11('(REGTM)) instruction sets. Finally, metrics on the improvements obtained across architectures and the optimization techniques are provided along with proposed lines of further research. The methods demonstrate that substantial reductions in code space and more modest improvements in execution speed can be obtained using these techniques.