SSA-based reduction of operator strength

[摘要] Reduction of operator strength is a well-known code improvement technique. It seeks to improve compiler-generated code by replacing repeated multiplications with repeated additions. Opportunities often occur in array addressing expressions inside loops. Strength reduction is generally combined with linear function test replacement, an optimization which removes induction variables whose uses have been strength reduced away by rewriting loop exit tests. This can reduce both the number of instructions in loops which contain array references and their cost. Perhaps the best known technique for performing strength reduction and linear function test replacement is the eight step approach presented by Allen, Cocke, and Kennedy. This work explores the potential benefits of using the Static Single Assignment (SSA) form of the program as the intermediate representation for performing strength reduction and linear function test replacement. It follows the basic form of the Allen, Cocke, and Kennedy technique, but many of the individual steps will be modified to take advantage of the special attributes of the SSA form wherever it improves either the asymptotic complexity of the operation or the precision of the information generated. It is intended that this work would be integrated into an optimizer comprised of a full suite of optimizations using the SSA representation.

[发布机构] Rice University