UNIT-6

What is code optimization: The code optimization is required to produce an efficient target code.
Issues in code optimization:
1. The semantic equivalence of the source program must not be changed.
2. The improvement over the program efficiency.
Advantages:
1. The intermediate code can be optimized to produce efficient target code.
2. The code optimization allows faster execution of source program.

Code optimization is two types:

Machine dependent code optimization: The machine dependent optimization based on characteristics
of the target machine.
Machine independent code optimization: The machine independent optimization based on
characteristics of the programming Languages

The principal sources of optimization:-

1. Function preserving transformations/Semantics-Preserving Transformations:-
A compiler can improve a program in number of ways without changing the meaning of the program.
The following types of function preserving transformations.
1. Common sub expression elimination.
2. Copy propagation
3. dead-code elimination and
4. Constant folding
Common sub expression elimination:-
An expression E is called a common sub-expression if E was previously computed, and the values of
variables in E have not changed since the previous computation. We can avoid re-computing the
expression if we can use the previously computed value.

Consider the input source and the corresponding intermediate code in TAC format in below table.

Input source TAC

Swap(i,j) (0) proce_begin

(1) t0 = i*8
{ (2) t1=a[t0]
x=a[i]; (3) x=t1
a[i]=a[j]; (4) t2=i*8
(5) t3=a[t2]
a[j]=x (6) t4=j*8
} (7) t5 =a[t4]
(8) t3=t5
(9) t6=j*8
(10) t7=a[t6]
(11) t7=x
(12) proce_end

The above table line (1) , (4) and(6) (9), are the same. The intermediate code compute the value of the
common sub expression i*8 and j*8. It is possible to optimize the intermediate code to have common sub
expressions computed only once in the function.

1| SIET D e p a r t me nt o f C S E
(0) proce_begin
(1) t0 = i*8
(2) t1=a[t0]
(3) x=t1
(4) t3=a[t0]
(5) t4=j*8
(6) t5 =a[t4]
(7) t3=t5
(8) t7=a[t4]
(9) t7=x
(10) proce_end

This process of identifying common sub expressions and eliminating their computation multiple times
in the intermediate code is known as common-sub expression elimination.
Copy propagation:-
Copy propagation is another commonly used transformation in order to improve the intermediate
code. In copy propagation, the use of the variable ‘y’ instead of ‘x’ is propagated in the stmts
following a copy stmt x=y.
(0) Proc_begin main
(1) t0 =0
(2) t1 =&arr1
(3) t1[t0] =3
(4) t2 =4
(5) t3=&arr1
(6) t3[t2] =4
(7) proce_end

In the above table, there are two assignment stmts (are called as copy stmts). They are
a. The assignment stmt(1) where the temporary variable t0 is assign 0.
b. The assign stmt(4), where the temporary variable t2 is assigned 4.
The use of the value 0 can be propagated in the place of t0 in the stmts following the assignment at
stmt(1). In other words, the variable t0 can be replaced with 0 in stmt(3). Similarly, the variable t2
can be replaced with value 4 in stmt(6) following the assignment at stmt(4). The resultant
intermediate code after the copy propagates is shown below table.
(0) proc begin main
(1) t0 =0
(2) t1 = &arr1
(3) t1[0] =3
(4) t2 =4
(5) t3 =& arr1
(6) t3[4] =4
(7) proc end main
The stmt(3) where t0 has been replaced with 0 and stmt(6) where t2 has been replaced with 4.
Elimination of Dead Code:-
Copy propagation does not vastly improve the quality of intermediate code. We will now see how copy
propagation facilitates an optimizing transformation called dead store elimination to be performed on the
resultant code.
(0) proc begin main
(1) t0=0
(2) t1 -&arr1
(3) t1[0] =3
(4) t2=4
(5) t3=&arr1
(6) t3[4]=4
(7) proc end main
2| SIET D e p a r t me nt o f C S E
In the intermediate cod shown in above table, the assignment stmt (1) can be eliminated, because t0 is no
longer used in any of the stmts following the assignment. similarly, the assignment stmt(4) can also be
eliminated. since t2 is no longer used in any of the stmts following the assignment.

(0) proc begin main

(1) t1=&arr1
(2) t1[0]=3
(3) t3=&arr1
(4) t3[4]=4
(5) proc end main
The dead store elimination improves the speed of execution because we have less instruction to execute at
the run time. The dead store elimination also reduces the memory required for storing the code.
Constant Folding:-
Another common optimization performed on the intermediate code as known as constant folding.
In constant folding, the constant expressions in the input source are evaluated and replace by the
equivalent values at the time of compilation. A constant expression involving only constants like, say
4*1, 2*0 and so on. Constant folding improves the speed of execution, since the calculations involving
constant expressions are performed at compile time, not at a run time.

(0) proc begin main

(1) t0=0*4
(2) t1=&arr1
(3) t1[t0]=3
(4) t2=1*4
(5) t3=&arr1
(6) t3[t2]=4
(7) proc end main
In the stmt(1), the value 0*4 is computed, which is known to be 0 at the compile time itself. Similarly, in
stmt(4), the value 1*4 is computed, which is known to be 4 at the time of compilation itself.
In stmt(1), 0*4 can be folded into 0 and in stmt(4), 1*4 can be folded into 4 at the time of
compilation itself. The resulting stmts from the constant folding are t0=0 for (1) and t2=4 for (4)
respectively.
(0) proc begin main
(1) t0=0
(2) t1=&arr1
(3) t1[t0]=3
(4) t2=4
(5) t3=&arr1
(6) t3[t2]=4
(7) proc end main
Loop optimization:-
Inner most loops are most important source of optimization. Even if a few stmts are eliminated in the
inner most loops, then code improvement is high.
Five important techniques of loop optimization are.
1) Loop invariant code motion 2) reduce in strength/strength reduction on induction variables
3) Induction variable. 4) Loop Unrolling 5.Loop fusion

1) Code motion:- Code motion reduces the number of instructions in a loop by moving instruction
outside a loop.
Ex:
while(x!=n-2)
{
x=x+2;
}
In the above loop, the value evaluated by the expression 'n-2' is independent of number of times the while
loop is executed. Now the expression n-2 can be written before the while loop begins as shown below
3| SIET D e p a r t me nt o f C S E
Ex: m=n-2;
while(x!=m)
{
x=x+2; }

2) Elimination of induction variable:-

An induction variable is a loop control variable or any other variable that depends on the induction
variable in some fixed way. If there are two o more induction variables in a loop then by the induction
variable elimination process all can be eliminated.
Ex: - int a[10],b[10];
void func(void)
{
int i,j,k;
for(i=0,j=0,k=0;i<10;i++)
a[j++]=b[k++];
}
In the above example there are three induction variables i,j and k, which take on the values 1,2,3------10.
Suppose that the values of variables j and 'k' are not used after the end of the loop then we can eliminate
then from the func() by replacing then by variable 'i'.
After induction variable elimination, the above code becomes
Ex:-
int a[10],b[10];
void func(void)
{
int i;
for(i=0;i<10;i++)
a[i]=b[i];
}
The use of induction variables elimination reduces code space and also improves the run time
performance.
3) Reduction in strength:-
Strength reduction is the process of replacing expensive operator by equivalent cheaper operator on the
target machine. On many machines a multiplication operation takes more time than addition or
subtraction. On such machines, the speed of the object code can be increased by replacing a
multiplication by a sub/add. This is called reduction in strength.
Ex: X=0
for (i=1; i<5; i++)
{
X=4*i;
}
This instruction x=4*i in the above loop can be replaced by equivalent addition instruction as x=x+4.
X=0
for (i=1; i<5;i++)
{
X=x+4;
}
4. Loop unrolling:
In this method the number of jumps and tests can be reduced by written the code two times.

4| SIET D e p a r t me nt o f C S E
int i=1;
while(i<=100)
{
a[i]=b[i];
i++; }

After optimization
int i=1;
while(i<=100)
{
a[i]=b[i];
i++;
a[i]=b[i];
i++;
}

5.Loop fusion:
In loop fusion method several loops are merged to one loop.
for i=1 to n do
a[i]=10 for i=1 to n do
for j=1 to n do  a[i]=10
b[j]=20 b[i]=20

Basic Blocks:
Basic Block is a sequence of three-address instructions. We begin a new basic block with the first
instruction and keep adding instructions until we meet a jump, a conditional jump, or a label on the
following instruction.
Algorithm: Partitioning three-address instructions into basic blocks.
INPUT: A sequence of three-address instructions.
OUTPUT: A list of the basic blocks
METHOD:
1. The first three-address instruction in the intermediate code is a leader.
2. Any instruction that is the target of a conditional or unconditional jump is a leader.
3. Any instruction that immediately follows a conditional or unconditional jump is a leader.
Note: Refer class notes for example
Control Flow graphs:-
A flow graph is a graphical representation of three address statements. It is used to show the flow of
control information to the set of basic blocks of a program. It consists of nodes and edges. A node of
a flow graph is basic block that performs some computations.

INPUT SOURCE TAC

Int v1 , v2, v3, v4, v5 (0) proc begin
Int func (int c) (1) v3 =v1 +v2
{ (2) If c>100 goto L0
V3 =v1 +v2 ; (3)goto L1
If(c>100) (4) Label L0
{ (5) V4 =v1 +v2
V4 =v1 +v2 ; (6) v1 =0
V1 =0; (7) Label L1
} (8) v5 =v1 +v2
V5 =v1 +v2 ; (9) proc end

}
5| SIET D e p a r t me nt o f C S E
(0) Proc begin
(1) V3 = v1+v2 B0
(2) If c>100 goto L o

(3) goto L1 B1
(4) Label L0
(5) V4 =v1 +v2
(6) v1 =0 B2
(7) Label L1
(8) V5 =v1 +v2 B3

(9) Proc end B4

Each node in a flow graph is a basic block. The starting node in a flow graph is called as initial node.
This is the basic block whose leader is the first TAC stmt in the procedure. The node B0 is the initial
node. The flow of control can go to back B1 or B2 from the block b0 .

Instruction Scheduling :- Using DAG we can rearrange some sequence of instructions and
generate an efficient code using minimum number of registers. The order of three address code
affects the cost of object code being generated. Changing the order in which computations are done
we can obtain the object code with minimum cost. Thus code optimization can be achieved by
scheduling the instructions in proper order. The technique of code optimization done by
rearrangement of some sequence of instructions is called Instruction Scheduling.

Example:- Rearrange the following three address statements.

Now if we change the ordering sequence of the above three address code.

6| SIET D e p a r t me nt o f C S E
In the first case the assembly code contains 10 lines. After rearranging the three address code
sequence then the assembly code contains 8 lines. So by rearranging some sequence of instructions
we can generate an efficient code using minimum number of registers. Thus here, an optimal order
means the order that yields the shortest instruction sequence.

Inter procedural optimization: - Inter procedural optimization technique is a kind of code

optimization in which collection of optimization techniques are used to improve the performance of
the program that contain many frequently used functions of blocks. IPO reduces or eliminates
duplicate calculations, inefficient use of memory and to simplify loops. IPO may reorder the routines
for better memory utilization. IPO checks the branches that are never taken and removes the code in
that branch.

Source program TAC CODE

func () ( 0) proc_fun
{ (1) t1=v1+v2
V3=v1+v2; (2) v3=t1
If(c>100) (3) If c>100 goto L0
{ (4)goto L1
V4=v1+v2; (5) Label L0
V5=v1+v2+v3 (6) t2 =v1+v2
} (7) v4=t2
(8) t3=v1+v2
V6=v1+v2; (9) t4=t3+v3
} (10) v5=t4
(11) Label L1
(12) t5=v1+v2
(13) v6=t5

7| SIET D e p a r t me nt o f C S E
( 0) proc_fun
(1) t1=v1+v2 B0
(2) v3=t1
(3) If c>100 goto L0

(5) Label L0
(4)goto L1 B1 (6) t2 =v1+v2 B2
(7) v4=t2
(8) t3=v1+v2
(9) t4=t3+v3
(10) v5=t4

(9) t4=t3+v3
(10) v5=t4

(11) Label L1
(12) t5=v1+v2 B3
(13) v6=t5

Now we apply the transformations on block B2 .In block B2 there are common sub expressions
v1+v2. we will remove these common sub expressions and the code will be

(5) Label L0
(6) t2 =v1+v2 B2
(7) v4=t2
(9) t4=t2+v3
(10) v5=t4

Thus the local transformation to block B2 will be completed. Now we will apply the global
transformations: on B3. As v1+v2 is already computed as t2 in B2, so we can replace t2 by t1.
Similarly as v1+v2 is already computed as t5, so t5 can be replaced by t1. Hence t5 can be
eliminated.

(11) Label L1
(13) v6=t1
B3

8| SIET D e p a r t me nt o f C S E