A PRACTICAL SYSTEM FOR INTERMODULE CODE OPTIMIZATION AT LINK-TIME

A system called OM has been developed to explore the problem of code o ptimization al link-time. OM takes a collection of object modules cons tituting the entire program, and converts the object code into a symbo lic register transfer language form that can be easily manipulated. Th is is transformed by intermodule optimization and converted back into object form. Although much high-level information about the program is gone at link-time, this approach enables optimizations to be performe d that a compiler looking at a single module cannot see. Since object modules are more or less independent of the particular source language or compiler, this also allows the code to be improved in ways that so me compilers might simply have missed. To test the concept, OM has bee n used to build an optimizer that does interprocedural code motion. It moves simple loop-invariant code out of loops, even when the loop bod y extends across many procedures and the loop control is in a differen t procedure from the invariant code. The technique also easily handles 'loops' induced by recursion rather than iteration. The code motion t echnique makes use of an interprocedural liveness analysis to discover dead registers that can be used to hold loop-invariant results. This liveness analysis also enables interprocedural dead code elimination. Code motion and dead code removal were applied to SPEC benchmarks comp iled with optimization using the standard compilers for the DECstation 5000. The system improved performance by 5% on average and by more th an 14% in one case. More improvement should soon be possible; at prese nt only simple load and load-address operations are moved out of loops , and registers are scavenged to hold these values, rather than comple tely re-allocated.