Unifying Strength Reduction and Semantic Code Motion

J. Knoop, B. Steffen

	   We present an algorithm that unifies strength reduction and
	   semantic code motion.  This algorithm evolves as a modular
	   extension of the semantic code motion algorithm of \cite{SKR1},
	   which optimally moves computations within programs with
	   respect to Herbrand equivalence.  Our algorithm 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. Previous
	   techniques fail both of these properties.