General and efficient methods for global code improvement
Mark N. Wegman · 1981
Code sequences produced by compiler code generators can often be improved by replacing some subsequences with equivalent sequences having faster execution or shorter length or both. If the correctness of the replacements depends on global considerations, special analytic techniques are needed. This dissertation presents new techniques for determining whether particular replacements are correct. New methods are also given to modify code sequences so that certain subsequent beneficial transformations become possible. A general framework is presented on which to prove simple theorems about programs automatically. An algorithm is given which derives (or proves) these theorems on reducible graphs representing programs. For a graph of e edges the algorithm has a worst-case time bound of O (e log e) function operations. A different analysis demonstrates that, in programming terms, the number of operations is proportional to e plus the number of exits from program loops. Consequently a restriction to one-entry one-exit control structures guarantees linearity. A generalization of the algorithm to irreducible graphs is also given and it is shown that the time bound increases to a cubic function of the number of nodes in the graph representing the program. If there are multiple execution paths to a certain code in a program, it is sometimes advantageous to duplicate that code so that different paths lead to different copies. It may then be possible to apply different program improvement transformations to the different copies, depending on the context in which they occur. In the dissertation, techniques are explored for allowing code improvement by such duplication without increasing the overall code size too much. Several applications of this idea are discussed, and it is shown that this technique can be viewed as a generalization of loop unrolling and movement of invariant code out of loops.