Code Optimization

Part 3
Prepared By: Dr. D. P. Singh
Graphic Era Deemed to be University, Dehradun
Themes behind Optimization Techniques
• Avoid Redundancy
• Reuse results that are already computed and store them for later use, instead
of recomputing them.
• Smaller Code
• Remove unnecessary computations and intermediate values. Less work for
the CPU, cache, and memory usually results in faster execution.
• Less Jumps
• Less complicated code. Jumps interfere with the prefetching of instructions,
thus slowing down code.
• Code Locality
• Code and data that are accessed closely together in time should be placed
close together in memory to increase spatial locality of reference.
• Extract more information about code
• More information better code generation
Optimizing Transformations
• Compile Time Evaluation
• Expression whose values can be precomputed at the compilation time
• Types:
1. Constant Folding
2. Constant Propagation
1. Constant Folding
The expression which contains only constant operands, can be replaced
with an evaluated single value
e.g. perimeter=2*(22/7)*r perimeter=2*3.14*r

2. Constant Propagation
Replace a variable with constant which has been assigned to it earlier
e.g.
pi=3.14 perimeter=2*3.14*r
perimeter=2*pi*r
Optimizing Transformations cntd…

• Common Subexpression evaluation

• Identify common subexpression presents in different expression , compute
once, and use the result in all places
• e.g.

a=b*c a=b*c
x=b*c+5 x=a+5
Optimizing Transformations cntd…

• Code Motion
• Moving code from one part of the program to other without changing the
meaning
• e.g.
if(a<b)then t=x^2
p=x^2 if(a<b)then
else p=t
y=x^2+10 else
y=t+10
Optimizing Transformations cntd…

• Strength Reduction
• Replacement of an Operator with a less costly one.
• e.g.

for i=1 to 10 do t=5

x=i*5 for i=1 to 10 do
end x=t
t=t+5
end
Optimizing Transformations cntd…

• Dead Code Elimination

• Dead code are the segment of the program which will not be
executed in any path of the program

• e.g.

d=0
if(d) then
print(“Optimization”)
end
Optimizing Transformations cntd…

• Copy Propagation
• Do not create the copy, use the original value
• E.g.

x=y
z=x+p*q z=y+p*q
Loop Transformations
• Loop Interchange
• Switch the nesting order of loops in a perfect loop nest
• Can increase parallelism, can improve spatial locality
• Inner-loop can be vectorized (Vectorization is the process of
rewriting a loop so that instead of processing a single element of an
array N times, it processes (let) 4 elements of the array
simultaneously N/4 times.)
• E.g.
for I = 1 to N do for J = 1 to M do
for J = 1 to M do for I = 1 to N do
A(I,J+1) = A(I,J) + B A(I,J+1) = A(I,J) + B
end end
end end
Loop Transformations cntd…

• Loop Peeling
• Splits any problematic first or last few iterations from the loop
body
• Change from a loop-carried dependence to loop-independent
dependence

• E.g. A[1]=A[1]+x
for i=1 to n do for i=2 to n do
A[i]=A[i]+x A[2]=A[2]+x
end end
Loop Peeling cntd…
• E.g.

int p = 10;
y[0] = x[0] + x[10];
for (int i = 0; i < 10; ++i) { for (int i = 1; i < 10; ++i) {
y[i] = x[i] + x[p]; y[i] = x[i] + x[i-1];
p = i; } }
Loop Transformations cntd…

• Loop Splitting
• Eliminate dependencies by breaking it into multiple loops which
have the same bodies but iterate over different contiguous
portions of the index range.
m=n/2
• E.g. Suppose n is divisible by 2 for i=1 to m-1 do
A[i]= A[n/2]+B[i]
for i=1 to n do end
A[m]=A[n/2]+B[i]
A[i]=A[n/2] +B[i]
for i=m+1 to n do
end A[i]= A[n/2]+B[i]
end
Loop Transformations cntd…
• Loop Unrolling (Loop Unwinding)
• Reduce number of iterations of loops
• Add statement(s) to do work of missing iterations
• JIT compilers try to perform unrolling at run-time
• Increases operation-level parallelism in loop body
• Allows other optimizations like reuse of temporaries across iterations
• Increases the executable size and register usage

for(i=1;i<n;i =i+4)
{
• E.g. A[i]=A[i-1]+A[i+2];
for(i=1;i<n;i++) A[i+1]=A[i]+A[i+3];
{ A[i+2]=A[i+1]+A[i+4];
A[i] =A[i-1]+A[i+2]; A[i+3]=A[i+2]+A[i+5];
} }
Loop Transformations cntd…
• Loop Fission (Loop Distribution)
• loop fission attempts to break a loop into multiple loops over the same index
range, but each new loop takes only part of the original loop's body.
• A loop with two statements can be distributed if there are no dependences from
any instance of the later statement to any instance of the earlier one
• improve locality of reference, both of the data being accessed in the loop and the
code in the loop's body.
• E.g. for I = 1 to 100 do
for I = 1 to 100 do for J = 1 to100 do
for J = 1 to 100 do A(I,J) = B(I,J) + C(I,J)
A(I,J) = B(I,J) + C(I,J) end
for J = 1 to 100 do
D(I,J) = A(I,J-1)*2.0
D(I,J) = A(I,J-1)*2.0
end
end
end end
Loop Transformations cntd…

• Loop Fusion (Loop Jamming)

• combines the bodies of two adjacent loops that would iterate the same
number of times
• Loop fusion may increase the level of parallelism, data locality, and decrease
the loop control overhead (by reducing the number of loops), but may also
increase the pressure on register allocation.
• E.g.
for(i=1;i<n;i++)
A[i]=B[i]+1;
for(i=1;i<n;i++)
end A[i]=B[i]+1;
for(i=1;i<n;i++) D[i]=A[i]+x;
D[i]=A[i]+x; end
end
Thank You