.bp
.NH 1
Strength reduction
.NH 2
Introduction
.PP
The Strength Reduction optimization technique (SR)
tries to replace expensive operators
by cheaper ones,
in order to decrease the execution time
of the program.
A classical example is replacing a 'multiplication by 2'
by an addition or a shift instruction.
These kinds of local transformations are already
done by the EM Peephole Optimizer.
Strength reduction can also be applied
more generally to operators used in a loop.
.DS
.TS
l l.
i := 1;	i := 1;
while i < 100 loop\ \ \ \ \ \ \ -->	TMP := i * 118;
   put(i * 118);	while i < 100 loop
   i := i + 1;	   put(TMP);
end loop;	   i := i + 1;
	   TMP := TMP + 118;
	end loop;
.TE

Fig. 6.1 An example of Strenght Reduction
.DE
In Fig. 6.1, a multiplication inside a loop is
replaced by an addition inside the loop and a multiplication
outside the loop.
Clearly, this is a global optimization; it cannot
be done by a peephole optimizer.
.PP
In some cases a related technique, \fItest replacement\fR,
can be used to eliminate the
loop variable i.
This technique will not be discussed in this report.
.sp 0
In the example above, the resulting code
can be further optimized by using
constant propagation.
Obviously, this is not the task of the
Strength Reduction phase.
