UNIT-5
CODE OPTIMIZATION & CODE GENERATION
Contents
• Code Optimization: Consideration for optimization, scope of
optimization, loop optimization, frequency reduction folding, DAG
representation, reduction in strengths.
• Object Code Generation: Object code forms, machine dependent code
optimization, register allocation and assignment generic code
generation algorithms.
2
void quicksort(m, n)
int m, n;
{ int i, j;
if (n <= m ) return;
/* fragment begins here */
i = m-1; j = n; v = a[n];
while(1) {
do i = i+1;
while( a[i] < v );
do j = j-1;
while( a[j] > v );
if( i >= j ) break;
x = a[i]; a[i] = a[j]; a[j] = x; }
x = a[i]; a[i] = a[n]; a[n]= x;
/* fragment ends here */ quicksort(m, j); quicksort(i+1, n); }
3
Three address code for quick sort
1. i = m - 1 16. t7 = 4 * i
2. j = n 17. t8 = 4 * j
3. t1 =4 * n 18. t9 = a[t8]
4. v = a[t1] 19. a[t7] = t9
5. i = i + 1 20. t10 = 4 * j
6. t2 = 4 * i 21. a[t10] = x
7. t3 = a[t2] 22. goto (5)
8. if t3 < v goto (5) 23. t11 = 4 * i
9. j = j – 1 24. x = a[t11]
10. t4 = 4 * j 25. t12 = 4 * i
11. t5 = a[t4] 26. t13 = 4 * n
12. if t5 > v goto (9) 27. t14 = a[t13]
13. if i >= j goto (23) 28. a[t12] = t14
14. t6 = 4 * i 29. t15 = 4 * n
15. x = a[t6] 30. a[t15] = x
4
Principle Sources of Optimization
I. Function preserving Transformation
Constant Folding
II. Loop Optimization
#include <stdio.h> Hence, the optimized code will be-
void main() { #include <stdio.h>
void main() {
int a = 50; int a = 50;
int x, y = 10, z = 10; int x, y = 10, z = 10;
while(a>0) { x = y + z;
x = y + z; while(a>0) {
if(a%x==0)
if(a%x==0)
printf("%d",a);
printf("%d",a); a--; } }
a--; } }
9
Take this simple program as an example:
int j = 0; for (int i = 0; i < 100; i++) { j = 2*i; } return j;
j is an induction variable dervied by applying a multiplication
After optimization
int j = 0; for (int i = 0; i < 100; i++) { j = j + 2; } return j;
It's important to note that j no longer has a direct dependence on i since
there are no instructions which read from i and write to j. Strength
reduction often helps remove data dependencies, paving the way for
optimizations.
#include <stdio.h> #include <stdio.h>
void main() { void main() {
int a[20], b[20]; int a[20], b[20];
int i, j, k; for (i = 0, j = 0, k = 0; i < 20; i++) int i;
a[j++] = b[k++]; } for (i = 0; i < 20; i++)
a[i] = b[i]; }
#include <stdio.h>
#include <stdio.h>
void main() {
void main() {
int a = 1, b;
int a = 1, b;
while (a<10) {
while (a<10) {
b = a * 2;
b = a + a;
a++; } }
a++; } }
11
Loop Fusion
• Also known as Loop Jamming, this technique combines two or more
loops which have the same index variable and number of iterations.
• This technique reduces the time taken in compiling all the loops.
• Let’s take an example to understand this technique.
#include <stdio.h> Hence, the optimized code will be-
void main() { #include <stdio.h>
int a[10], b[10], i; void main() {
int a[10], b[10], i;
for(i = 0; i < 10; i++)
for(i = 0; i < 10; i++) {
a[i] = 1; a[i] = 1; b[i] = 2; } }
for(i = 0; i < 10; i++)
b[i] = 2; }
12
Loop Unrolling
The loop unrolling technique transforms the loop. In this technique, the
number of jumps and tests can be optimized by writing the code to times
without changing the meaning of the code. It reduces the number of
iterations and increases the program’s speed by eliminating the loop
control instructions and loop test instructions.
#include <stdio.h>
void main() {
int i = 1; int a[100], b[100];
while(i<100) { a[i] = b[i]; i++; } }
In the above code, a loop is running 100 times. We can optimize this
code by repeating the statements so that the loop runs only 50 times.
Hence, the optimized code will be-
#include <stdio.h>
void main() {
int i = 1; int a[100], b[100];
while(i<100) { a[i] = b[i]; i++; a[i] = b[i]; i++; } }
13
• Example: Consider the following expression: (a + b) * (a + b +c)
• The above expression can be divided into three statements.
• t1 = a + b
• t2 = t1 + c
• t3 = t1 * t2
16
CODE GENERATION
24
Introduction
Intermediate Intermediate target
Source Front code Code code Code program
program
end Optimizer generator
Symbol
table
Position of code generator
Input to the Code Generator
• We assume, front end has
– Scanned, parsed and translate the source program into a
reasonably detailed intermediate representations
– Type checking, type conversion and obvious semantic errors
have already been detected
– Symbol table is able to provide run-time address of the data
objects
– Intermediate representations may be
• Postfix notations
• Three address representations
• Stack machine code
• Syntax tree
• DAG
Object Code Forms (Target Programs)
• The output of the code generator is the target program.
• Target program may be
– Absolute machine language
• It can be placed in a fixed location of memory and immediately executed
– Re-locatable machine language
• Subprograms to be compiled separately
• A set of re-locatable object modules can be linked together and loaded for execution by
a linker
– Assembly language
• Easier
Issues in the Design of a Code Generator
• Details depend on
– Target language
– Operating System
• But following issues are inherent in all code generation problems
– Memory management
– Instruction Selection
– Evaluation order
– Register allocation
Memory Management
Mapping names in the source program to addresses of data objects in run
time memory is done cooperatively by the front end and the code
generator.
The names in three address code are placed in symbol table.
Instruction Selection
It is determined by the nature of the instruction set. The factors that affect
code generation are:
•The instruction set of the target machine should be uniform and complete.
•Instruction speed and machine idioms determine the efficiency of the
code generation.
•Direct translation of TAC to assembly code may result in redundant
statements.
Evaluation order
An efficient order of computation is also an important issue in code
generation. Reducing number of loads and stores improve the speed of the
code generation.
Register Allocation
• Instructions involving register operands are usually shorter and faster
than those involving operands in memory.
• Efficient utilization of register is particularly important in code
generation.
• The use of register is subdivided into two sub problems
– During register allocation, we select the set of variables that will
reside in register at a point in the program.
– During a subsequent register assignment phase, we pick the specific
register that a variable will reside in.
Instruction Cost
Here, cost 1 means that it occupies only one word of memory.
Each instruction has a cost of 1 plus added costs for the source and
destination.
Instruction cost = 1 + cost is used for source and destination mode.
MODE FORM ADDRESS EXAMPLE ADDED COST
absolute M M Add R0, M 1
register R R Add R0, R1 0
indexed c(R) C+ ADD 100 1
contents(R) (R2), R1
indirect *R contents(R) ADD * 100 0
register
indirect *c(R) contents(c+ (R2), R1 1
indexed contents(R))
literal #c c ADD #3, R1 1
31
32
Simple code generator
Register and Address descriptors:
The code generation algorithm uses descriptors to keep track of register
contents and addresses for names.
• A register descriptor keeps track of what is currently in each register
• An address descriptor keeps track of the location where the current
value of the name can be found at run time
A code generation algorithm
For each 3-address statement of the form x:=y op z we perform
following actions
1. Invoke a function getreg() to determine the location L where the
result of the computation y op z should be stored.
2. Consult the address descriptor for y to determine y1 .Prefer the
register for y1 if the value of y is currently both in memory and a
register. If the value of y is not already in L, generate the
instruction MOV y1 , L
3. Generate the instruction op z1 , L where z1 is a current location of
Z
A code generation algorithm (cont..)
The function getreg :
The function getreg returns the location L to hold the value of x for
the assignment x:=y op z
1.If y is in register, and y is not live after execution of x:=y op z then
return the register of y for L.
2. Failing (1) , return an empty register for L
3. Failing (2) and x is not used in the block, return memory location of
x as L
Code sequences for an assignment statement
d:=(a-b) + (a-c) + (a-c)
Three address code:
t := a –b
u := a – c
v := t + u
d := v + u
Consider d live at end.
Code sequence
STATEMENTS CODE GENERATED REGISTER DESCRIPTER ADDRESS DESCRIPTER
t := a - b MOV a , R0 R0 contains t t in R0
SUB b , R0
u:= a – c MOV a , R1 R0 contains t t in R0
SUB c , R1 R1 contains u u in R1
v := t + u ADD R1 , R0 R0 contains v u in R1
R1 contains u v in R0
d := v + u ADD R1 , R0 R0 contains d d in R0
MOV R0 , d d in R0 and memory
d:=(a+b) – (e-(c+d))
Three address code:
t := a +b
u := c+d
v := e-u
STATEMENTS CODE GENERATED REGISTER DESCRIPTER ADDRESS DESCRIPTER
d := t - v
Consider d live at end. t := a +b MOV a , R0 R0 contains t t in R0
ADD b , R0
u:= c + d MOV c , R1 R0 contains t t in R0
ADD d , R1 R1 contains u u in R1
v := e - u
SUB u, R1 R0 contains t v in
R1
R1 contains v t in R0
d := t – v SUB R1 , R0 R0 contains d d in R0
MOV R0 , d d in R0 and
memory
Conditional statements
Conditional statements are implemented using condition codes
Ex : if x<y goto z is implemented as
CMP x , y
CJ< z
