V.M. Dhaneshwar, D.M. Dhamdhere
Strength reduction of large expressions,
Journal of Programming Languages, vol. 3 (1995), 95-120.
Strength reduction of a large expression cannot be performed as a second order effect of optimizing its subexpression(s). We use the ideas of composite hoisting and strength reduction [1,2,3] to develop an algorithm for the strength reduction of a large expression (SRLE) as a single entity using the framework for partial redundancy elimination [4,5,6]. SRLE subsumes the conventional optimizations of code hoisting, common subexpression elimination, loop invariant movement and strength reduction, thereby performing comprehensive optimization of a program. %This algorithm (SRLE) It performs partial redundancy elimination as effectively as the recent algorithms [5,21,22], and also eliminates several suboptimalities of previously published work in partial-redundancy--based strength reduction [2,3].
The SRLE algorithm involves use of nonsingular bidirectional data flows, giving rise to interesting issues concerning the desired fixed point of the data flows. A solution method based on the principle of decomposition of bidirectional data flows into a sequence of unidirectional data flows is shown to achieve the desired fixed point of the bidirectional data flows more elegantly than earlier methods. Experimental results as well as proof of correctness of the algorithm are included.