Efficient Code Motion and an Adaption to Strength Reduction

this paper we consider two elaborations of this algorithm, which are dealt with in Part I and Part II, respectively. Part I deals with the problem that the full variant of the algorithm of [SKR1] may excessively introduce trivial redefinitions of registers in order to cover a single computation. Rosen, Wegman and Zadeck avoided such a too excessive introduction of trivial redefinitions by means of some practically oriented restrictions, and they proposed an efficient algorithm, which optimally moves the computations of acyclic flow graphs under these additional constraints (the algorithm is "RWZoptimal " for acyclic flow graphs) [RWZ]. Here we adapt our algorithm to this notion of optimality. The result is a modular and efficient algorithm, which avoids a too excessive introduction of trivial redefinitions along the lines of [RWZ], and is RWZ-optimal for arbitrary flow graphs. Part II modularly extends the algorithm of [SKR1] in order to additionally cover strength reduction. This extension generalizes and improves all classical techniques for strength reduction in that it overcomes their structural restrictions concerning admissible program structures (e.g. previously determined loops) and admissible term structures (e.g. terms built of induction variables and region constants). Additionally, the program transformation obtained by our algorithm is guaranteed to be safe and to improve run-time efficiency. Both properties are not guaranteed by previous techniques. Structure of the Pape