Information Technology Reference
In-Depth Information
8. Loop unrolling
9. Loop jamming
17.7.1
Reduction in Strength
A reduction in strength is a type of compiler optimization in which an expensive
operation is combined with a less expensive one. More specifically, strength reduction
is a transformation that a compiler uses to replace strong, costly instructions with
cheaper and weaker instructions (Cooper et al., 2005). For example, a weak form of
strength reduction replaces 2 x x with either x
1.
Another type of strength reduction replaces an iterated series of strong computa-
tions with an equivalent series of weaker computations. For example, the reduction
replaces certain multiplications inside a loop with repeated additions, which results
in loop nests that manipulate arrays. These resulting additions are usually cheaper
than the multiplications they replace. It should be noted that many operations, other
than multiplication, also can be reduced in this manner.
Strength reduction is important for two reasons. First, multiplying integers usually
has taken longer than adding them. This makes strength reduction profitable, as the
amount of improvement varies with the relative costs of addition and multiplication.
Second, strength reduction decreases the “overhead” introduced by translation from
a higher level language down to assembly code. Strength reduction often decreases
the total number of operations in a loop. Smaller operations lead to faster code. The
shorter sequences used to generate addresses may lead to tighter schedules as well.
+
x, or x
17.7.2
Common Subexpression Elimination
Repeated calculations of the same subexpression in two different equations should
be avoided in code. The following is an example of subexpression elimination:
x
=
6
+
a
×
b;
y
=
a
×
b
+
z;
could be replaced with
t
=
a
×
b;
x
=
y
+
t;
y
=
t
+
z;
The purpose of common subexpression elimination is to reduce the runtime
of a program by avoiding the repetition of the same computation (Chiil, 1997).
Search WWH ::
Custom Search