5 Intermediate Code Generation

Chapter 5
5.1 BASIC OF INTERMEDIATE CODE GENERATION
y Compiler may generate sequential intermediate representations to
translate a source code to a target machine code language.

y Source program is associated with “High level intermediate

representation”, and the target machine code is with “Low level
intermediate representation”.
y Syntax tree is high level intermediate representation which shows the
natural hierarchical structure of the source program. They are well
suited for the tasks like static type checking.
y Register allocations and instruction selection these kinds of machine
dependent jobs can be done efficiently using “Low level intermediate
representation”.

5.2 REPRESENTATION OF INTERMEDIATE CODE

Fig. 5.1 Representation of Intermediate Code

3-Address code:
y Three address code is built from two concepts: address and instructions.
y The implementation of three address codes consists of records as well
the address fields
y Three address instructions consist of at most three addresses in a line
Intermediate Code Generation

of code.
y An address can be one of the following:
1) A name: For convenience, we allow the source program name to
appear as in the 3-address code.
2) A constant: Constants and variables are the mandatory fields with
which compiler has to deal with
3) A compiler-generated temporary variable: Temporary variable is
mainly for optimising compiler to store intermediate results each
time a temporary variable is needed.

97
Chapter 5

y Types of 3-address code:

i) x = y op z || x stores the result of y operator z
ii) x = op y || x stores result of unary operator y
iii) x = y || x stores y
iv) x = a [i] || x stores value of array a at index i
v) a [i] = x || Stores the value of x in an array a at index i
vi) x = f(a)  || x stores the value return by function ‘f’ with
parameter ‘a’
vii) if x < y goto z {conditional goto}
viii) goto x {Unconditional goto}
ix) z = x[i] [j] || This is not 3-address code representation because
it uses variables z, x, i, j
x) x = f(a, b) || This is not 3-address code representation because
it uses 4 variables x, f, a, b
xi) x = &a || address assignment

Types of 3-address code representation:

Basically, there are 3-ways of representing 3-address code
1) Quadruple
2) Triple
3) Indirect triple

Let us consider an expression:

a=b*–c+b*–c;
Three address code:
t1 = minus c

t2 = b * t1

t3 = minus c

t4 = b * t3
Intermediate Code Generation

t5 = t2 + t4

a = t5

98
 Chapter 5
1) Quadruples representation of 3-address code:

Op arg1 arg2 result

0. minus c – t1
1. * b t1 t2
2. minus c – t3
3. * b t3 t4
4. + t2 t4 t5
5. = t5 – a
Fig. 5.2 Quadruples Representation of 3-Address Code

For readability, we use actual identifiers like a, b, and c in the field arg1, arg2 and result
instead of pointers to their symbol table entries.
y Op field contains the internal code for the operator.
y arg1 and arg2 contain the operand.
y result field stores the result.

2) Triplet representation of 3-address code:

y A triplet has only tree fields Op, arg1, arg2
y Using triplet, we refer to the result of an operation x op y by its position rather than
an explicit temporary name.
y Above 3-address code representation in triplet.

Op arg1 arg2

0. minus c –
1. * b (0)
2. minus c –
Intermediate Code Generation

3. * b (2)
4. + (1) (3)
5. = a (4)
Fig. 5.3 Triplet Representation of 3-Address Code

Triple representation of a = b * – c + b * – c ;

99
Chapter 5

3) Indirect triple representation of 3-address code:

y Indirect triples do not list the triples, but they list the pointers of
triples. For eg: an array of instructions to list pointers to triples in
the desired order.
y An optimising compiler is able to reorder the instruction in triples
without affecting the triples themselves.

Instruction Op arg1 arg2

35. (0) 0. minus c –
36. (1) 1. * b (0)
37. (2) 2. minus c –
38. (3) 3. * b (2)
39. (4) 4. + (1) (3)
40. (5) 5. = a (4)
……………
Fig. 5.4 (Indirect Triple Representation of
3-Address Code)
Rack Your Brain
Indirect-triple representation of a = b * (–c)
+ b * (–c) ; What could be the benefit of
y Instruction is an array that contains a quadruples over triple?
pointer to triple in the desired order.

SOLVED EXAMPLES

Q.1 Write 3-address code for the following program

x=2;
for (x = 25 ; x £ 100 ; x ++)
{
Intermediate Code Generation

x=p+q+r;
}

Sol: 1000: x = 2
1001: x = 25
1002: if x ≤ 100 goto 1004.

100
 Chapter 5
1003: goto 1009
1004: t1 = p + q
1005: t2 = t1 + r
1006: x = t2
1007: x = x + 1
1008: goto 1002
1009: _________

Q2 3-address code representation in quadruple form for the expression

x=b+b+b+b+b

Sol: 3-address code representation:

t1 = b + b
t2 = t1 + b
t3 = t2 + b
t4 = t3 + b
x = t4
Quadruple form representation of 3-address code:

Op arg1 arg2 result

(0) + b b t1
(1) + t1 b t2
(2) + t2 b t3
(3) + t3 b t4
(4) = t4 – x
Fig. 5.5 (Quadruple Representation)
Intermediate Code Generation

Q3 3-address code representation for expression

x = (a + b) * a * b * (c + d) ;

101
Chapter 5

Sol: 3-address code for given expression

t1 = a + b
t2 = t1 * a
t3 = t2 * b
t4 = c + d
t5 = t3 * t4
x = t5

Postfix notation:
y Let us consider there are two expressions X1 and X2 and there is an operand
op which are represented as X1 op X2 then in postfix notation it will be
represented as X1 X2 op.

SOLVED EXAMPLES

Q4 Convert the following expression in postfix notation.

x=a*b+c*d+d*e
where * has higher precedence, and both are left-associative, and ‘=’ has the
least precedence.

Sol: * has higher precedence thus they will be calculated first.

\ (x) = (a*b) + (c*d) + (d*e)
(x) = (ab*) + (cd*) + (de*)
(x) = ((ab*cd*)+) + (de*)
Intermediate Code Generation

(x) = (ab*cd*+de*+)
xab*cd* + de* + =

102
 Chapter 5
Q5 Given an expression
x$y$z#x$b#t Å d
Convert the expression in postfix notation when the precedence order of the
operator is $ > # > Å and all the three operators are left-associative.

Sol: $ has highest precedence and Å has the least precedence.

\ (x y $) $ z # x $ b # t Å d
Þ (x y $ z $) # (x $ b) # t Å d
Þ (x y $ z $) # (x b $) # t Å d
Þ (x y $ z $ x b $ # ) # t Å d
Þ (x y $ z $ x b $ # t #) Å d
Þ xy$z$xb$#t#d Å
Post order notation Þ x y $ z $ x b $ # t # d Å

Q6 x = a + uminus b+ uminus d
All the operators have these usual precedences and associativity then convert
given expression in postfix notation uminus represent uniary minus operator.

Sol: As we know, uniary operator has the highest precedence

\ Order of precedence uminus > + > =
Postfix notation: x = a +(b uminus) + (d uminus)
x = (a b uminus +) + (d uminus)
x = (a b uminus + d uminus +)
x a b uminus + d uminus + =

Syntax tree:
y Syntax tree is the representation in the form of tree in which each internal
Intermediate Code Generation

node represents the operators, and the leaf node represents the operand.
y During the formation of a syntax tree of any code, we should design tree in
such a form that lower precedence operator should be on the top level and
higher precedence should be on lower levels.

103
Chapter 5

SOLVED EXAMPLES

Q7 x=a*b+c
Syntax tree for the above expression when all the operators have their usual
associativity and precedence.

Sol: The Precedence order of operators:

*>+>=
Syntax Tree:

Fig. 5.6 Syntax Tree

Q8 x=a*b ¸ c*d
Syntax tree for the above expression when operators have their usual prece-
dence and associativity.

Sol: Both ‘*’ and ‘ ¸ ’ have the same precedence. Thus, syntax tree will be formed on
the basis of associativity.
Syntax Tree:
Intermediate Code Generation

Fig. 5.7 Syntax Tree

104
 Chapter 5
Directed acyclic graphs:
y It is similar to a syntax tree except that common sub-expression are
represented by a single node.
y Common subexpression is represented with a single node to get the
optimised code, i.e., instead of evaluating again and again, we can
evaluate common expression only once.

SOLVED EXAMPLES

Q9 x=t+t+t+t
For the given expression form DAG.

Sol: Here identifier ‘t’ is used many times in the expression, and ‘t+t’ is evaluated
twice so in the graph, we will use only one node for the identifier ‘t’ and ‘t+t’
evaluation.

Fig. 5.8 DAG

Q10 x = a * b * c +b * a
Intermediate Code Generation

All operator have their usual precedence and associativity, then form the DAG
for the above expression.

Sol: Here (a * b) can be used again as it is repeated in the expression there again
forming the node for (a * b), we have reused it.

105
Chapter 5

Fig. 5.9 DAG

5.3 STATIC SINGLE ASSIGNMENT

y Static Single Assignment (SSA) is the property of intermediate code
representation where each variable should be assigned exactly once
and each variable should be defined before its use.
y Each expression must be in 3-address representation only and following
the above two conditions.

SOLVED EXAMPLES

Q11 Check whether given 3-address code in SSA representation or not.

T1 = a * a
T2 = y * a
T2 = z * b

Sol: Given 3-address code is not in SSA representation because variable T2 is assigned
more than one time.
Intermediate Code Generation

Q12 Check whether the given code is in SSA representation or not.

T1 = a * b
T2 = c * T1
T3 = d + T2
T4 = T1 + T2

106
 Chapter 5
Sol: Given 3-address code is in SSA representation because each variable has been
assigned exactly once.

Q13 Write SSA representation of given expression

x=b*c+d+a+b

Sol: ‘*’ is computed first because multiplication has higher precedence than addition.
T1 = b * c
T2 = T1 + d
T3 = T2 + a
T4 = T3 + b
x = T4

Q14 Given a three address code

x=a+b
y=c+d
x=y+d
c=c+b
z=c+y
Convert the given 3-address code into a single static assignment.

Sol: Here in this 3-address code representation, variables x and c are assigned twice;
thus, it is not in SSA.
SSA representation of above code:
x=a+b
y=c+d
Intermediate Code Generation

T1 = y + d
T2 = c + b
z = T2 + y

107
Chapter 5

Previous Years’ Question

Consider the following code segment

x=u–t;
y=x*v;
x=y+w;
y=t–z;
y=x*y;
Minimum number of variables required to convert the above code in
single static assignment.
Sol: 10 variables [GATE: CS-2016]

Previous Years’ Question

Consider the following intermediate program in three address code:

p=a–b

q=p*c

p=u*v

q=p+q
Which of the following corresponds to a static single assignment from
the above code?

a) p1 = a–b c) p1 = a – b
q1 = p1 * c q1 = p2 * c
Intermediate Code Generation

p1 = u*v p2 = u * v
q1 = p1 + q1 q2 = p4 + q3
b) p3 = a–b d) p1 = a – b
q4 = p3 * c q1 = p * c
p4 = u*v p2 = u * v
q5 = p4 + q4 q2 = p + q

Sol: b) [GATE: CS-2016]

108
 Chapter 5
Previous Years’ Question

Consider the basic block given below:

a=b+c
c=a+d
d=b+c
e=d–b
a=e+b
The minimum number of nodes and edges present in the DAG
representation of the above basic block respectively are.
a) 6 and 6 b) 8 and 10
c) 9 and 12 d) 4 and 4
Sol: a) [GATE: CS-2014]

5.4 CONTROL FLOW GRAPHS

Backpatching:
There is a problem when writing the code for the flow of control statements
that match the jump instruction with the target of the jump.
The solution to this problem is back patching, in which when we don’t
know the target of the jump statement, we leave it unspecified.
When we know the target address, then we fill that unspecified blank space.

For eg:
100: if a < 100 goto ____
101: goto ____
102: if a > 200 goto 104
103: goto ____
104: if a ! = b goto ____
Intermediate Code Generation

105: goto ____

After backpatching 104 goes to instruction 102.

100: if a < 100 goto ____
101: goto 102
102: if a > 200 goto 104
103: goto ____

109
Chapter 5

104: if a ! = b goto ____

105: goto ____

After backpatching 102 into instruction 101.

Leader:
1) The first statement of the intermediate code is the leader.
2) Target statement of the goto is the leader.
3) Next statement after goto is the leader.

Basic block:
y Basic block is the set of statements of intermediate code which consist
of one entry point and one exit point in between which there can be no
halt or jump.
y Each basic block consists of one leader.
y Basic block starts from the leader statement and ends one statement
before the next leader.
y Number of Basic blocks = Number of leaders.

SOLVED EXAMPLES

Q15 Draw the control flow graph of the given code.

100: if x < 100 goto 104
101: x = a + b ;
102: x = x + 7 ;
104: if x > 200 goto 106
105: x = x + 1
106: z = x + 200

Sol:
Intermediate Code Generation

110
 Chapter 5
Control flow graph:

Fig. 5.10 Control Flow Graph

Q16 100: i = 1 ;
101: j = 2 ;
102: if i > 100 goto 106
103: i = i + 1 ;
104: if j > 100 goto 107
105: j = j + 1 ;
106: z = z + 200
107: z = z + 200
108: if z < 500 goto 101
The total number of nodes and edges will be there in the control flow graph of
above code.

Sol:
Intermediate Code Generation

111
Chapter 5

Control flow graph:

Fig. 5.11 Control Flow Graph

\ Total number of nodes and edges = 7 + 9 = 16

Previous Years’ Question

Consider the intermediated code given below:

1) i=1 7) a[t4] = –1
2) j=1 8) j = j + 1
3) t1 = 5 * i 9) if j < = 5 goto (3)
4) t2 = t1 + j 10) i = i + 1
5) t3 = 4 * t2 11) if i < 5 goto (2)
6) t4 = t3

The number of nodes and edges in the control-flow graph constructed for the above
code respectively are
a) 5 and 7 b) 5 and 5 c) 6 and 7 d) 7 and 8
Intermediate Code Generation

Sol: c)

112
 Chapter 5
Chapter Summary

y Intermediate code is used to translate the source code into the machine code. It
lies between high level language and machine language.
y Intermediate code is present in two forms:
i) Linear form:
a) 3-address code
b) Postfix notation
ii) Tree form:
a) Syntax tree
b) Directed Acyclic Graph (DAG)
y 3-address code can have a maximum of 3-address in its expression and is built on
two concept address and instruction.
y 3-address codes are of the following types:
i) Quadruples
ii) Tripple
iii) Indirect tripple
y Postfix notation is the conversion of expression in the postfix form.
y Syntax tree represented in the form of tree where internal nodes represent
operators and leaf nodes represent operands.
y Static single assignment (SSA) is the representation of the code in which each
variable can only be assigned once, and the variable should be defined before its
use.

Intermediate Code Generation

113