Scribd
Upload
144 views

Loop Optimization

Uploaded by

nexexa6242
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
144 views

Loop Optimization

Uploaded by

nexexa6242
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 15

Department of Computer Science & Engineering

UIT-RGPV

Topic: Loop Optimization

Course: Compiler Design (CS701)

By:
Mr. Praveen Yadav
Assistant Professor
DoCSE, UIT-RGPV
Bhopal
Loop Optimization
• The running time of a program can be improved if we decree
the amount of instructions in an inner loop.
• Three techniques are important for loop optimization:
1. Code Motion.
2. Induction Variable Elimination.
3. Reduction in Strength.

Compiler Design By Asst. Prof. Praveen Yadav, DoCSE, UIT-RGPV 2


Code Motion
• Code Motion is an important modification that decreases the
amount of code in a loop.
• This transformation takes an expression that yields the same
result independent of number of times a loop is executed
(loop invariant computation) and place expression before the
loop.
• Example. Consider the following while statement:
while (i <= limit - 2) do
• The expression limit - 2 is loop invariant.
• Code motion transformation will result in:
t = limit -2;
while (i <= t) do

Compiler Design By Asst. Prof. Praveen Yadav, DoCSE, UIT-RGPV 3


Reduction in Strength
• It is based on the replacement of a computation with a
less expensive one.
• Example. Consider the assignment t4 := 4 * j in
Block B3 (see in next slide). j is decremented by 1
each time, then t4 = 4 * j − 4.
• Thus, we may replace t4 := 4 * j by t4 := t4 − 4.
• Problem: We need to initialize t4 to t4 := 4 * j before
entering the Block B3.
• Note: The substitution of a multiplication by a
subtraction will speed up the resulting code.

Compiler Design By Asst. Prof. Praveen Yadav, DoCSE, UIT-RGPV 4


Reduction in Strength

Compiler Design By Asst. Prof. Praveen Yadav, DoCSE, UIT-RGPV 5


Induction Variables Elimination
Induction Variable:
• A variable x is an Induction Variable of a loop if every time the variable x
changes values; it is incremented or decremented by some constant.
• A common situation is the one in which an induction variable, say i,
indexes an array, and some other induction variable, say t, is the actual
offset to access the array:
Example: Induction Variables Elimination
• Consider the loop of Block B3 (see next slide). The variables j and t4 are
Induction Variables. The same applies for variables i and t2 in Block B2.
• After Reduction in Strength is applied to both t2 and t4, the only use of i
and j is to determine the test in B4.
• Since t2 := 4 * i and t4 := 4 * j, the test i > j is equivalent to t2 > t4.
• After this replacement in the test, both i (in Block B2) and j (in Block B3)
become dead-variables and can be eliminated.

Compiler Design By Asst. Prof. Praveen Yadav, DoCSE, UIT-RGPV 6


Induction Variables Elimination

Compiler Design By Asst. Prof. Praveen Yadav, DoCSE, UIT-RGPV 7


Induction Variables Elimination

Compiler Design By Asst. Prof. Praveen Yadav, DoCSE, UIT-RGPV 8


Other Loop Optimization Techniques

Compiler Design By Asst. Prof. Praveen Yadav, DoCSE, UIT-RGPV 9


Other Loop Optimization Techniques
4. Loop Unrolling
5. Loop Jamming (Loop Fusion)
6. Loop Fission

Compiler Design By Asst. Prof. Praveen Yadav, DoCSE, UIT-RGPV 10


Other Loop Optimization Techniques
4. Loop Unrolling:
Loop unrolling is a loop transformation technique that helps
to optimize the execution time of a program.
• We basically remove or reduce iterations.
• Example:

Initial code: Optimized code:

for (int i=0; i<5; i++) printf("Compiler Design\n ");


{ printf("Compiler Design\n ");
printf("Compiler Design\n"); printf("Compiler Design\n ");
} printf("Compiler Design\n ");
printf("Compiler Design\n ");

Compiler Design By Asst. Prof. Praveen Yadav, DoCSE, UIT-RGPV 11


Loop Unrolling cont…
Example-2:

Initial code:
Optimized code:

Int i = 1; Int i = 1;
while(I <= 100) while(I <= 100)
{ {
a[i] = b[i]; a[i] = b[i];
i++; i++;
} a[i] = b[i];
i++;
}

Compiler Design By Asst. Prof. Praveen Yadav, DoCSE, UIT-RGPV 12


Other Loop Optimization Techniques
5. Loop Jamming (Loop Fusion):
Loop jamming is the combining the two or more loops in a
single loop.
• It reduces the time taken to compile the many number of
loops.
• Example:
Optimized code:
Initial Code:
for(int i=0; i<5; i++)
for(int i=0; i<5; i++)
{
a = i + 5;
a = i + 5;
for(int i=0; i<5; i++)
b = i + 10;
b = i + 10;
}
Compiler Design By Asst. Prof. Praveen Yadav, DoCSE, UIT-RGPV 13
Other Loop Optimization Techniques
6. Loop Fission
• Break a loop into multiple loops.
• Following example take advantage of locality of reference.
Optimized code:
Initial Code:
for(int i=1; i<100; i++)
for(int i=1; i<100; i++) {
{ a[i] = i;
a[i] = i; }
b[i] = i+2; for(int i=1; i<100; i++)
} {
b[i] = i+2;
}

Compiler Design By Asst. Prof. Praveen Yadav, DoCSE, UIT-RGPV 14


Thank You

Compiler Design By Asst. Prof. Praveen Yadav, DoCSE, UIT-RGPV 15

You might also like