Loop Optimization:
The optimization performed on inner loops is called loop
optimization
Generally, inner loop is a place where program spends large
amount of time. Hence, if number of instructions is less in inner loop the
running time of the program decreases
The following techniques can be performed on inner loops:
Code
Motion/Loop Invariant
Induction
Variable
Reduction
in Strength
Loop
Fusion/Loop Jamming
Loop
Unrolling
Code Motion/Loop
Invariant:
The optimization performed on inner loop, in which the code
moves outside the loop called as code motion
If there are a number of lines inside the loop whose result
remains same even after executing the loop for several times, such an
expression should be placed outside the loop, i.e., just before the loop
Example:
int i,
max = 10;
for(i
=10; I <= max-z; i ++)
{
Printf(“%d”,
i);
}
In the example code, the result of an expression max-1
remains same for 11 iterations. Hence, this code can be optimized by removing
the computing of maz-1 outside the loop. i.e., by placing this expression
before the loop thereby avoiding multiple computations
The optimized code is
int I,
max = 10, r;
r =
max-1;
for(i =
0; i <=r; i++);
{
Printf(“%d”,
i);
}
Induction Variable:
A variable x is called an induction variable of loop L every
time the variable x changes values, it is incremented or decremented by some
constant
Example 1:
int i,
maz = 10, r;
r =
max-1;
for(i=10;i<=r;i++)
{
Printf(“%d”,
i);
}
In the above code, variable i is called induction variable
as values of I get incremented by 1, i.e., 0,1,2,3,4,5,6,7,8,9,10
The strength of certain operators is higher than other
operators
For example, strength of * is higher than +. Usually,
compiler takes more time for higher strength operators and execution speed is
less
Replacement of higher strength operator by lower strength
operator is called a strength reduction technique
Optimization can be done by applying strength reduction
technique where higher strength can be replaced by lower strength operators
Example:
for
(i=1;i<=10;i++)
{
sum = I
* 7;
printf(“%d”,
sum);
}
In the above code replacement of * by + will speed up the
object code. Thus, optimization is done without changing the meaning of a code
The optimized code is
temp =
7;
for(i=1;i<=10;i++)
{
temp =
temp + 7;
sum =
temp;
printf(“%d”,
sum)
}
Note: This technique is not applied to the floating point
expressions because such a use may yield different results.
This technique combines the bodies of two loops whenever the
same index variable and number of iterations are shared
Example:
for(i=0;i<=10;i++)
{
Printf(“TOC”);
}
For(i=0;i<=10;i++)
{
Printf(“CD”);
}
The above code can be merged on one loop and optimized code can
be rewritten as
for(i=0;i<=10;i++)
{
Printf(“TOC”);
Printf(“CD”);
}
In this technique the number of jumps and tests can be
optimized by writing the code to times without changing the meaning of a code
Example:
int i =
1;
while(i<100)
{
a[i] =
b[i];
i++;
}
The example code can be optimized as
int i =
1;
while(i<100)
{
a[i] =
b[i];
i++;
a[i] =
b[i];
i++;
}
The first code loop repeats 50 times whereas second code
loop repeats 25 times. Hence, optimization is done.
