C Compilers and Code Optimization for DSPs - Signal Processing Systems - page 1011

a b

for (i = 0; i < M; i ++) { for (i = 0; i < M; i ++) {

for (j = 0; j M; j ++) { for (j = 0; j M; j ++) {

< <

a[i ][ j] = 5 ∗ j; ∗ (a+M ∗ i+j ) = 5 ∗ j;

} }

} }

Fig. 10 Example: loop invariant code motion, Part I . ( a ) Original code. ( b )Codeafterlowering

a b

ivar pa = a;
for (i = 0; i < M; for (i = 0; i < M; i ++) { i ++) {

pa = a+M ∗ i; ivar1 j=ivarpa ;

ivar2 j=0;
for (j = 0; j < M;

for (j = 0; j < M; j ++) { j ++) {

∗ (pa+j) = 5 ∗ j; ∗ ( ivar1 j) = ivar2 j;

ivar1 j++;
ivar2 j+=5;
ivar pa += M;

}

} }

Fig. 11 Example: loop invariant code motion, Part II . ( a ) After loop invariant code motion.
( b ) After induction variable creation

3.3.5 Loop Invariant Code Motion

Loop Invariant Code Motion [ 40 ] moves constant expressions out of the loop body
and, hence, reduces the number of instructions executed per loop iteration. An
example of this transformation is shown in Figs. 10 and 11 . After the original loop in
Fig. 10 a has been lowered address computations for the array access in the loop body
become explicit (see Fig. 10 b ). The first part of the address expression, however, is
only dependent on the outer loop iterator i , but is constant for any value of the inner
loop iterator j . “Hoisting” this constant subexpression out of the j -loop results in the
code shown in Fig. 11 a . Not only does this code avoid the repeated computation of a
constant expression, it is also amendable to further optimization. Strength Reduction
(see also Sect. 3.5.1 ) can be applied to replace the costly multiplication operation
with a cheaper addition, and Induction Variable Creation can eliminate the use of
the loop iterator j in favor of an induction variable incremented in each iteration that
can be mapped efficiently the available post-increment addressing modes (see [ 45 ] )
offered by many DSPs.
Before any loop-invariant computation can be moved out of a loop the compiler
needs to verify this property. This is easy for genuine constants. For general
expression it must be shown that all reaching definitions of the arguments of an
expression are outside the loop. After that a new block of code containing the
hoisted, loop-invariant computation is inserted as a pre-header to the loop.