Intermediate Code Generation
Ms. Trusha Patel
Assistant Professor
[Link]
Language Processor
Source Program
Front Intermediate Back Target Program
Representation
End End
IR
INTERMEDIATE REPRESENTATION
Source Target
IR
program program
Machine
WHY
?
independent
Advantages Source language
Front-end phases
1
IR
Back-end phases Back-end phases Back-end phases
Machine code - 1 Machine code - 2 Machine code - 3
Advantages
Can apply machine independent code optimizer on IR
2
Intermediate
Language
Three
Syntax Postfix
address
tree notation
code
Syntax
Natural hierarchical structure of a source program
tree
DAG More compact than Syntax tree
Postfix
Linearized representation of syntax tree
notation
Three
address Sequence of statements of form x = y op z
code
x y z op
• Names
• Constants • Any operator
• Compiler generated temporaries
Contain maximum 3 addresses
Three
address
code
t1 = y * z
x+y*z
t2 = x + t 1
Source language expression Three Address Code
Three
address
code
assign
t1 = - c
t2 = b * t1 a +
t3 = - c
t4 = b * t3 * *
- b -
t5 = t2 + t4 b
a = t5
c c
Three Address Code Syntax Tree
Three
address
code
assign
t1 = - c
t2 = b * t1 a +
t3 = t-2c+ t2
at4 == tb3 * t3
*
t5 = t2 + t4
b -
a = t5
c
Three Address Code DAG
Types of statements
Three
address
code
Unconditional Conditional
Assignment Copy
jump jump
x = y op z x=y goto L if x relop y goto L
“op” binary operator
x = op z
“op” unary operator
Types of statements
Three
address
code
Address &
Index Procedure call
Pointer
assignment and return
assignment
param x1
param x2
x[i]=y x = &y .
.
.
x=y[i] x = *y param xn
call P, n
*x = y
return y
Implementation
Three
address
code
Indirect
Quadruples Triples
Triples
Implementation
Three
address
code
Indirect
Quadruples Triples
Triples
Record structure of 4 fields
op arg1 arg2 result
(0) - c t1 t1 = - c
(1) * b t1 t2 t2 = b * t1
(2) - c t3 t3 = - c
(4) * b t3 t4 t4 = b * t3
(5) + t2 t4 t5 t5 = t2 + t4
(6) = t5 a a = t5
Implementation
Three
address
code
Indirect
Quadruples Triples
Triples
Record structure of 3 fields
Avoid to enter temporary in table, Refer temporary with position
op arg1 arg2
(0) - c t1 = - c
(1) * b (0) t2 = b * t1
(2) - c t3 = - c
(4) * b (2) t4 = b * t3
(5) + t2 (3) t5 = t2 + t4
(6) = t5 (5) a = t5
Implementation
Three
address
code
Indirect
Quadruples Triples
Triples
Listing pointers to triples,
rather than listing triples themselves
op op arg1 arg2
(0) (14) (14) - c
(1) (15) (15) * b (14)
(2) (16) (16) - c
(4) (17) (17) * b (16)
(5) (18) (18) + t2 (17)
(6) (19) (19) = t5 (18)
Reference
Alfred Aho, Ravi Sethi, Jeffrey D Ullman, Compilers Principles, Techniques and Tools,
Pearson Education Asia.