5-10
SC100 C Compiler
Optimization Techniques and Hints
5.3.2.1 Strength reduction (loop transformations)
The purpose of strength reduction is to increase the effectiveness of the code by transforming operations
which are
“
expensive
”
in terms of resources, into less expensive, linear operations. For example, addition
and subtraction are linear functions which require less operation cycles than multiplication and division.
When an address calculation that contains multiplication is replaced by one containing addition, the
amount of resources required by the code is significantly reduced, since addition can be implemented using
the complex addressing mode of the Address Generation Unit (AGU). Where the multiplication appears
within a loop, the benefit of the replacement is further increased.
The strength reduction optimization identifies and transforms induction variables, meaning variables
whose successive values form an arithmetic progression, usually within a loop. An example of an
induction variable is a subscript which points to the addresses of array elements, and increases with each
iteration of the loop. The computation of such a variable can be moved to a position outside the loop to
avoid repeated operations, and/or transformed for use with linear operations.
Simple and complex loops and array access patterns are transformed where possible into simpler, linear
forms, as described in the sections that follow.
5.3.2.1.1 Simple loops
Example 5-8 shows the generated pseudocode and output assembly code for a simple loop which
initializes an array. The loop structure is static, meaning that its induction variables, the loop counter
i
and
the array offset
t1
, both increase by increments of known constant values.
Before optimization, the calculation of the value of
t1
is within the loop, and is incremented by
multiplication. After optimization, the initial value of
t1
is set outside the loop, and its value is
incremented inside the loop by addition. The resulting values are identical for both forms, but in the
optimized version the resource overhead is considerably lower.
Example 5-8. Loop transformation - simple loop
C source code
int table[100];
step = 1;
for(i=0; i<100; i+=step)
table[i] = 0;
Pseudocode before optimization
Pseudocode after optimization
i = 0;
t1 = i * 4;
table[t1] = 0;
i++;
if(i<100) goto L1
L1
i = 0;
t1 = i * 4;
table[t1] = 0;
t1 = t1 + 4;
i++;
if(i<100) goto L1
L1
Assembly code output
move.l #_table,r0 clr d2
loopstart3
move.l d2,(r0)+
loopend3