Whole-program optimization of binary executables

Abstract|Compiler optimization research has a long his-tory and very complex algorithms were developed to opti-mize code. Unfortunately these algorithms, however com-plex they may be, su®er from the modular design of soft-ware. Compilers compile and optimize one source code mod-ule at a time. While they do so, they have no or few knowl-edge about the context in which the code will be executed. Even if summary information about all involved source code ¯les is collected or if programs consist of one source code ¯le only (which is not trivial for mixed-language programs) all kinds of code libraries will be linked with the programmer's code to produce the ¯nal executable binary. These libraries are often only available in object code and therefor no candi-dates for global analyses and optimizations by the compiler. A solution to this problem is to relegate part of the global optimizations to the linker, which has-by its nature- a global overview of the application. Unfortunately, the linker does not have access to the wealth of (semantic) information about the program that is available in the compiler. There-for, a linker has to painstakingly reconstruct part of that information by analyzing object ¯les. Nevertheless, it turns out to be possible to do this in a reasonable time, and to produce speedups of 19 % for code that was already highly optimized by the compiler. In the paper, we describe Alto, a link time optimizer for the alpha architecture. We describe Alto's frame-work, the analyses performed, the advantages and disad-vantages of optimizing programs at link time, and an anal-ysis of the speedups attained for the Spec benchmarks. We also describe additional program transformations applied by Squeeze, an Alto-derivative aimed at link-time code com-pression. Squeeze obtains additional link-time code com-pression of 23 % on already compact compiler generated bi-naries. Keywords|linker, whole-program optimization, code com-pression, I