Intermediate Code Generation
Intermediate
Code
Linear Form Tree Form
Three
PostFix Syntax tree DAG
address code
(a+b) * (a + b + c)
• Post fix
o ab+ab+c+*
• Three address code
o t1 = a+b
o t2 = a+b
o t3 = t2 + c
o t4 = t1 * t3
• Syntax Tree
• Direct Acyclic Graph
3 Address Code
Types of 3 address codes
1) x = y operator z
2) x = operator z
3) x = y
4) goto L
5) A[i] = x
y = A[i]
6) x = *p
y = &x
• 3 address codes can be implemented in a number of ways
(a + b) * (c + d) + (a + b + c)
1) t1 = a+b
2) t2 = -t1
3) t3 = c+d
4) t4 = t2 * t3
5) t5 = a+b
6) t6 = t5 + c
7) t7 = t4 + t6
Quadruples
Operator Operand1 Operand2 Result
1) + a b t1
2) - t1 t2
3) + c d t3
4) * t2 t3 t4
5) + a b t5
6) + t5 c t6
7) + t4 t6 t7
• Advantage
o statement can be moved around
• Disadvantage
o too much of space is wasted
Triplet
Operator Operand1 Operand2
1) + a b
2) - 1
3) + c d
4) * 2 3
5) + a b
6) + 5 c
7) + 4 6
• Advantage
o Space is not wasted
• Disadvantage
o Statement cannot be moved
Indirect triple
triple can be separated by order of execution and uses the pointers concepts
• Advantage
o Statement can be moved
• Disadvantage
o two memory access
if(a, b) then t=1
else t = 0
i) if (a<b) goto (i+3)
i+1) t=0
i+2) goto (i+4)
i+3) t=1
i+4) exit
while(C) do S
i) if (E) goto i+2
i+1) goto i+4
i+2) S
i+3) goto i
i+4) exit
for(1=0; i<10 ; i++)
s
i) i=0
i+1) if(i<10) goto i+3
i+2) goto i+6
i+3) S
i+4) i=i+1
i+5) goto i+1
i+6) exit
Q One of the purposes of using intermediate code in compilers is to (Gate-2014) (1 Marks)
(a) make parsing and semantic analysis simpler
(b) improve error recovery and error reporting.
(c) increase the chances of reusing the machine-independent code optimizer in other
compilers
(d) improve the register allocation.
ANSWER -C
Optimization
• Process of reducing the execution time of a code without effecting the outcome of the
source program, is called as optimization.
Optimization
Machine
Machine
Independe
Dependent
nt
Loop Constant Redundanc Algebraic Use of Peephole
Constant Strength Register
Optimizati Propogatio y Simplificati addressing Optimizati
Folding reduction allocation
on n Elimination on mode on
Flow of
Use of
Loop Loop Code Redundant control Strenght
Machine
Unrolling Jamming movement load optimizatio reduction
idoms
n
Constant Folding: Replacing the value of expression before compilation is called as constant
folding
x=a+b+2*3+4
x = a + b + 10
Constant Propagation: replacing the value of constant before compile time, is called as
constant propagation.
pi = 3.1415
x = 360 / pi
x = 360/3.1415
Strength reduction: replacing the costly operator by cheaper operator, this process is called
strength reduction.
y=2*x
y=x+x
Redundant code Elimination: avoiding the evaluation of any expression more than once is
redundant code elimination.
x=a+b
y=b+a
x=a+b
y=x
Algebraic Simplification: Basic laws of math’s which can be solved directly.
a = b*1
a=b
a=b+0
a=b
• Loop Optimization
o To apply loop optimization, we must first detect loops.
o For detecting loops, we use control flow analysis (CFA) using program flow graph
(PFG)
o To find PFG, we need to find basic blocks.
o A Basic block is a sequence of 3-adress statements where control enters at the
beginning and leaves only at the end without any jumps or halts
• The block can be identified with the help of leader
o Finding the leader
o Finding the bocks
o Construct PFG
• In order to find the basic blocks, we need to finds the leader in the program then a basic
block will start from one leader to the next leader but not including next leader.
• identifying leaders in a basic block
o First statement is a leader
o Statement that is the target of conditional or unconditional statement is a leader
o Statement that follow immediately a conditional or unconditional statement is a
leader
Fact(x)
{
int f=1
for(i=2 ; i<=x ; i++)
f = f*i;
return f;
}
1) f=1;
2) i=2
3) if(i>x), goto 9
4) t1=f*i;
5) f=t1;
6) t2=i+1;
7) i=t2;
8) goto(3)
9) goto calling program
1) f=1;
2) i=2
3) if(i>x), goto 9
4) t1=f*i;
5) f=t1;
6) t2=i+1;
7) i=t2;
8) goto(3)
9) goto calling program
Loop Jamming: combining the bodies of two loops, whenever they share the same index and
same no o variables
for (int i=0; i<=10; i++)
for (int j=0; j<=10; j++)
x[i, j]=”TOC”
for (int j=0; j<=10; j++)
y[i]=”CD”
for (int i=0; i<=10; i++)
{
for (int j=0; j<=10; j++)
{
x[i, j]=”TOC”
}
y[i]=”CD”
}
Loop Unrolling: getting the same output with less no of iteration is called loop unrolling
int i=1;
while(i<=100)
{
print(i)
i++
}
int i=1;
while(i<=100)
{
print(i)
i++
print(i)
i++
}
Code movement: removing those code out from the loop which is not related to loop.
int i=1;
while(i<=100)
{
a =b+c
print(i)
i++
}
Q In compiler design ‘reducing the strength’ refers to (NET-DEC-2012)
(A) reducing the range of values of input variables.
(B) code optimization using cheaper machine instructions.
(C) reducing efficiency of program.
(D) None of the above
Ans: B
Q Loop unrolling is a code optimization technique: (NET-DEC-2015)
a) that avoids tests at every iteration of the loop.
b) that improves performance by decreasing the number of instructions in a basic block.
c) that exchanges inner loops with outer loops
d) that reorders operations to allow multiple computations to happen in parallel
Ans: a
Q In compiler optimization, operator strength reduction uses mathematical identities to
replace slow math operations with faster operations. Which of the following code
replacements is an illustration of operator strength reduction? (NET-AUG-2016)
a) Replace P + P by 2 * P or Replace 3 + 4 by 7.
b) Replace P * 32 by P < < 5
c) Replace P * 0 by 0
d) Replace (P < <4) – P by P * 15
Q Consider the following intermediate program in three address code
p=a-b
q=p*c
p=u*v
q=p+q
Which one of the following corresponds to a static single assignment from the above code
(Gate - 2017) (2 Marks)?
A) B) C) D)
p1 = a - b p3 = a - b p1=a-b p1 = a - b
q 1 = p1 * c q4 = p3 * c q1 = p2 * c q1 = p * c
p1 = u * v p4 = u * v p3 = u * v p2 = u * v
q1 = p1 + q1 q5 = p4 + q4 q2 = p4 + q3 q2 = p + q
ANSWER B
Q Consider the following code segment.
x = u - t;
y = x * v;
x = y + w;
y = t - z;
y = x * y;
The minimum number of variables required to convert the above code segment to static single
assignment form is ________. (Gate - 2017) (2 Marks)
ANSWER 10
Q The least number of temporary variables required to create a three-address code in static
single assignment form for the expression q + r/3 + s – t * 5 + u * v/w is _________. (Gate -
2015) (1 Marks)
ANSWER 8
(a) p, s, u (b) r, s, u (c) r, u (d) q, v
Answer 3
Q Consider the intermediate code given below:
1. i = 1
2. j = 1
3. t1 = 5 * i
4. t2 = t1 + j
5. t3 = 4 * t2
6. t4 = t3
7. a[t4] = –1
8. j = j + 1
9. if j <= 5 goto(3)
10. i = i + 1
11. if i < 5 goto(2)
The number of nodes and edges in the control-flow-graph constructed for the above code,
respectively, are (Gate - 2015) (2 Marks)
a) 5 and 7 b) 6 and 7 c) 5 and 5 d) 7 and 8
ANSWER B
Q Which one of the following is FALSE? (Gate - 2014) (1 Marks)
(1) A basic block is a sequence of instructions where control enters the sequence at the
beginning and exits at the end.
(2) Available expression analysis can be used for common subexpression elimination
(3) Live variable analysis can be used for dead code elimination
(4) x=4*5⇒x=20 is an example of common subexpression elimination
ANSWER D
(GATE - 2011) (2 Marks)
ANSWER 3
(GATE - 2010) (2 Marks)
ANSWER 3
Q Some code optimizations are carried out on the intermediate code because (GATE - 2008) (1
Marks)
a) They enhance the portability of the compiler to other target processors
b) Program analysis is more accurate on intermediate code than on machine code
c) The information from dataflow analysis cannot otherwise be used for optimization
d) The information from the front end cannot otherwise be used for optimization
ANSWER a
Q A simplified computer the instructions are (GATE-2007) (2 Marks)
The computer has only to registers, and OP is either ADD or SUB. Consider the following basic
block:
Assume that all operands are initially in memory. The final value of the computation should be
in memory. What is the minimum number of MOV instructions in the code generated for this
basic block?
(A) 2 (B) 3 (C) 5 (D) 6
Answer: (B)
Q Consider the following C code segment. (Gate-2006) (1 Marks)
for (i = 0, i<n; i++)
{
for (j=0; j<n; j++)
{
if (i%2)
{
x += (4*j + 5*i);
y += (7 + 4*j);
}
}
}
Which one of the following is false?
(A) The code contains loop invariant computation
(B) There is scope of common sub-expression elimination in this code
(C) There is scope of strength reduction in this code
(D) There is scope of dead code elimination in this code
Answer: (B)
Q Consider the grammar rule E → E1 – E2 for arithmetic expressions. The code generated is
targeted to a CPU having a single user register. The subtraction operation requires the first
operand to be in the register. If E1 and E2 do not have any common sub expression, in order to
get the shortest possible code (Gate-2014) (2 Marks)
(A) E1 should be evaluated first
(B) E2 should be evaluated first
(C) Evaluation of E1 and E2 should necessarily be interleaved
(D) Order of evaluation of E1 and E2 is of no consequence
Answer: (B)
Q Consider the following code segment.
x = u - t;
y = x * v;
x = y + w;
y = t - z;
y = x * y;
The minimum number of total variables required to convert the above code segment to static
single assignment form is (Gate-2016) (2 Marks)
Note: This question was asked as Numerical Answer Type.
(A) 6 (B) 8 (C) 9 (D) 10
Answer: (D)
Q Match all items in Group 1 with correct options from those given in Group 2. (Gate - 2009)
(2 Marks)
Group 1 Group 2
P. Regular expression 1. Syntax analysis
Q. Pushdown automata 2. Code generation
R. Dataflow analysis 3. Lexical analysis
S. Register allocation 4. Code optimization
(A) P-4. Q-1, R-2, S-3 (B) P-3, Q-1, R-4, S-2
(C) P-3, Q-4, R-1, S-2 (D) P-2, Q-1, R-4, S-3
Answer: (B)