Intermediate Code

Generation
 OUTLINE

Intermediate code : need, types, Syntax

directed translation scheme,

Intermediate code generation for

assignment statement,
declaration statement,
Boolean expression,
if-else statement,
do -while statement,
array assignment.
2
 Compiler Architecture

Intermediate Code
tokens Syntactic
Scanner Parser Semantic Code
Source structure Target
language
(lexical (syntax Analysis Generator
language
analysis) analysis) (IC generator)
Intermediate Code

Intermediate Code
Code
Optimizer

Symbol
Table

3
 Intermediate Code Generation

 After syntax and semantic analysis, some compilers

generate an explicit intermediate representation of
the source program.
 ICG is not machine language, but can be somewhat
similar for many languages.
 e.g. GCC compiler. Family of GNU compilers use
same form of ICG.
 Advantage is that, we can write single code
optimizer for many languages, if ICG is of same
form.

 two important properties: It

should be easy to
produce and it should be easy to translate into
target program.
4
 Summary of Front End

Lexical Analyzer (Scanner)

+
Syntax Analyzer (Parser)
+ Semantic Analyzer

Front
Abstract Syntax Tree w/Attributes End

Intermediate-code Generator

Error Non-optimized Intermediate Code

Message
5
 Intermediate Code
 Similar terms: Intermediate representation, intermediate
language

 Ties the front and back ends together

 Explains how SDT methods can be used to translate into an

intermediate form.

 Most SDD can be implemented during either BUP or TDP .

 So ICG can be folded into parsing , if desired.

 More than one intermediate language may be used by a

compiler
6
 Intermediate Code Generation(IMPORTANT)
 Intermediate codes are machine independent codes, but close to
machine instructions.

 Program in a source language is converted to an equivalent program in

an intermediate language by the intermediate code generator.

 Intermediate language can be many different languages, and the

designer of the compiler decides this intermediate language.
 syntax trees can be used as an intermediate language.
 postfix notation can be used as an intermediate language.
 three-address code (Quadraples) can be used as an intermediate language
 use quadraples to discuss intermediate code generation
 quadraples are close to machine instructions, but they are not actual machine
instructions.

 some programming languages have well defined intermediate languages.

 java – java virtual machine
 prolog – warren abstract machine
 In fact, there are byte-code emulators to execute instructions in these intermediate
languages.

8
 Intermediate Languages Types
Graphical IRs:
 Abstract Syntax trees
 DAGs
 Control Flow Graphs

Linear IRs:
Stack based (postfix)
Three address code (quadruples)

9
 Graphical IRs

Abstract Syntax Trees (AST) – retain essential

structure of the parse tree, eliminating
unneeded nodes.

Directed Acyclic Graphs (DAG) – compacted AST

to avoid duplication – smaller footprint as well

10 Control flow graphs (CFG) – explicitly model

 ASTs and DAGs
a := b *-c + b*-c

:= :=
a + a +
* * *
b - (uni) b - (uni) b - (uni)

c c c

11
 Linearized IC
 Postfix Notation(stack based)

 a := b *-c + b*-c

abc uminus * bc uminus * + :=

12
 Linearized IC

Stack based (one Three address (quadruples)

address) – compact – up to three operands, one
push 2 operator
push y t1 <- 2
multiply t2 <- y
push x t3 <- t1 * t2
Subtract t4 <- x
t5 <- t4 – t3

2*Y-X Postfix Notation 2Y*X-

13
 Syntax tree vs. Three address code

Expression: (A+B*C) + (-B*A) - B

_
+ B T1 := B * C
T2 = A + T1
+ * T3 = - B
_ A
A * T4 = T3 * A
T5 = T2 + T4
B C
B T6 = T5 – B

Three address code is a linearized representation of a syntax tree (or a

DAG) in which explicit names (temporaries) correspond to the interior
nodes of the graph.
14
 DAG vs. Three address code

Expression: D = ((A+B*C) + (A*B*C))/ -C

=
D T1 := A T1 := B * C
/ T2 := C T2 := A+T1
+ _ T3 := B * T2 T3 := A*T1
+ T4 := T1+T3 T4 := T2+T3
*
T5 := T1*T3 T5 := – C
T6 := T4 + T5 T6 := T4 / T5
* T7 := – T2 D := T6
A T8 := T6 / T7
B C
D := T8
Question: Which IR code sequence is better?
15
 Three-Address Code (Quadraples)
 A quadraple is:
x := y op z
where x, y and z are names, constants or compiler-generated
temporaries; op is any operator.
 Another notation for quadraples (much better notation because it looks
like a machine code instruction)
op y,z,x
apply operator op to y and z, and store the result in x.
Eg. x+y*z in TAC is t1:=y*z, t2:=x+t1
 The term “three-address code” means each statement usually contains
three addresses (two for operands, one for the result).
 Linearized representation of syntax tree or a DAG.
16
 Implementation of Three Address Code
(Con’t)

Triples
• Three fields: op, arg1, and arg2. Result become
implicit.
• arg1 and arg2 are either pointers to the symbol table
or index/pointers to the triple structure.
Example: d = a + (b*c)
Problem in
1 * b, c
reorder the
2 + a, (1)
codes?
3 assign d, (2)
• No explicit temporary names used.
• Need more than one entries for ternary operations
such as x:=y[i], a=b+c, x[i]=y, … etc.
17
 Three-Address Code (Quadraples)

 A quadraple is:
x := y op z
where x, y and z are names, constants or compiler-generated
temporaries; op is any operator.

 But we may also use the following notation for quadraples

(much better notation because it looks like a machine code
instruction)
op y,z,x
apply operator op to y and z, and store the result in x.

 We use the term “three-address code” because each statement

usually contains three addresses (two for operands, one for the
result).
18
 Three-Address Statements
Binary Operator: op y,z,result or result :=
y op z
where op is a binary arithmetic or logical operator. This binary
operator is applied to y and z, and the result of the operation is
stored in result.
Ex: add a,b,c or c:=a+b
gt a,b,c or c:=a>b

Unary Operator: op y,,result or result :=

op y
where op is a unary arithmetic or logical operator. This unary
operator is applied to y, and the result of the operation is stored
in result.
Ex: uminus a,,c or c:=-a
not a,,c or c!=a
19 inttoreal a,,c or c=inttoreal(a)
 Three-Address Statements
(cont.)
Move Operator: mov y,,result or
result := y
where the content of y is copied into result.
Ex: mov a,,c or c:=a
movi a,,c
movr a,,c

Unconditional Jumps: jmp ,,L or goto L

We will jump to the three-address code with the label L, and
the execution continues from that statement.
Ex: jmp ,,L1 // jump to L1 or goto L1
jmp ,,7 // jump to the statement 7 or goto 7

20
 Three-Address Statements
(cont.)
Conditional Jumps: jmprelop y,z,L or if y relop z goto L
We will jump to the three-address code with the label L if the result of y relop
z is true, and the execution continues from that statement. If the result is false,
the execution continues from the statement following this conditional jump
statement.
Ex: jmpgt y,z,L1 // jump to L1 if y>z or if y>z goto L1
jmpgte y,z,L1 // jump to L1 if y>=z orif y>=z goto L1
jmpe y,z,L1 // jump to L1 if y==z or if y==z goto L1
jmpne y,z,L1 // jump to L1 if y!=z or if y!=z goto L1

Our relational operator can also be a unary operator.

jmpnz y,,L1 // jump to L1 if y is not zero or if y!=0 goto L1
jmpz y,,L1 // jump to L1 if y is zero or if y==0 goto L1
jmpt y,,L1 // jump to L1 if y is true or if y goto L1
jmpf y,,L1 // jump to L1 if y is false or if !y goto L1
21
 Three-Address Statements
(cont.)
Procedure Parameters: param x,, or param x
Procedure Calls: call p,n, or call p,n
where x is an actual parameter, we invoke the procedure p with n
parameters.
Ex: param x1,,
param x2,,
 p(x1,...,xn)
param xn,,
call p,n,

Function call: ICG (1):- ICG(2):-

fun1(x+1,y);  add x,1,t1 t1:=x+1
param t1,, param t1
param y,, param y
22 call fun1,2, call fun1,2
 Three-Address Statements
(cont.)
Indexed Assignments:
move y[i],,x or x := y[i]
move x,,y[i] or y[i] := x

Address and Pointer Assignments:

moveaddr y,,x or x := &y
movecont y,,x or x := *y

23
 Example: Three Address Code Generation
while (A<C && B>D) 1. if A<C goto 3
{ 2. goto 15
if (A==3) 3. if B>D goto 5
C=C+1; 4. goto 15
else 5. if A==3 goto 7
{ ICG 6. goto 10
while (A<=D) 7. t1:=C+1
A=A+3; 8. C:=t1
} 9. goto 1
} 10. if A<=D goto 12
11. goto 1
12. t2:= A+3
13. A:=t2
14. goto 1
15. end

24
 Three Address Codes - Example

x:=1; 01: mov 1,,x 1. t1:=1

y:=x+10; 02: add x,10,t1 2. X:=t1
while (x<y) {  03: mov t1,,y 3. t2:=t1+10
x:=x+1; 04: lt x,y,t2 4. Y:=t2
if (x%2==1) then y:=y+1; 05: jmpf t2,,17 5. if X<Y
goto 7
else y:=y-2; 06: add x,1,t3 6. goto 14
} 07: mov t3,,x 7. t3:=X+1
08: mod x,2,t4 8. t4:=X%2
09: eq t4,1,t5 9. if t4==1 goto 12
10: jmpf t5,,14 10. t5:=Y-2
11: add y,1,t6 11. Y:=t5
12: mov t6,,y 12. t6:=Y+1
13: jmp ,,16 13. Y:=t6
14: sub y,2,t7 14. end
15: mov t7,,y
16: jmp ,,4
25 17: stop
Arrays
 Elements of arrays can be accessed quickly if the elements are
stored in a block of consecutive locations.

A one-dimensional array A:

… …

baseA low i width

baseA -is the address of the first location of the array A,

width -is the width of each array element.
low -is the index of the first array element

location of A[i]  baseA+(i-low)*width

26
 Arrays (cont…..)

baseA+(i-low)*width
can be re-written as i*width + (baseA-low*width)

 So, the location of A[i] can be computed at the run-time by evaluating

the formula i*width+c where c is (baseA-low*width) which is
evaluated at compile-time.

 Intermediate code generator should produce the code to evaluate this

formula i*width+c (one multiplication and one addition operation).
 ICG (three address code) for A[i] is:

t1:=baseaddr(A) or t1:=addr(A)
t2:=t1[i*width] i.e. t2:=t1[i*2] , if array is of int type where i is
27
index
Two-Dimensional Arrays
A two-dimensional array can be stored in
either row-major (row-by-row) or
column-major (column-by-column).
Most of the programming languages use row-
major method.

Row-major representation of a two-dimensional

array:

row1 row2 rown 28

 1 2 3
Matrix A:- 1 1 2 3

2 4 5
6
3 7 8 9
4 10 11 12
A[2][3]
1 2 3 4 5 6 10 11 12

Assume that the array index starts from 1.

Location of A[2][3]=
=baseA+ ((i1-low1)*n2+i2-low2)*width
=100+ ((2-1)*3 + 3-1)*2
= 100 + (3+2)*2
=100+10= 110
 Two-Dimensional Arrays (cont...)
The location (address) of A[i ,i ] or A[i ][i ] is:-
1 2 1 2

baseA+ ((i1-low1)*n2+i2-low2)*width

baseA is the location of the array A.

low1 is the index of the first row
low2 is the index of the first column
n2 is the number of elements in each row
width is the width of each array element
Again, this formula can be re-written as

((i1*n2)+i2)*width + (baseA-((low1*n2)+low2)*width)

30should be computed at run-time can be computed at compile-time

 Multi-Dimensional Arrays
In general, the location of A[i 1,i2,...,ik] is

(( ... ((i1*n2)+i2) ...)*nk+ik)*width + (baseA-((...((low1*n1)+low2)...)*nk+lowk)*width)

So, the intermediate code generator should produce the codes

to evaluate the following formula (to find the location of
A[i1,i2,...,ik]) :

(( ... ((i1*n2)+i2) ...)*nk+ik)*width + c

To evaluate the (( ... ((i1*n2)+i2) ...)*nk+ik portion of this formula,

we can use the recurrence equation:

e1 = i1
em = em-1 * nm + im
32 CS416 Compiler Design
Translation of Array References
Translation of Array References
L -> L [ E] | id [ E ]
 Translation of Array References
 Nonterminal L has three synthesized attributes:

1. [Link] denotes a temporary that is used while computing the offset

for the array reference by summing the terms i j x wj.

2. [Link] is a pointer to the symbol table entry for the array name. The
base address of the array, say, [Link] is used to determine the
actual l-value of an array reference after all the index expressions are
analyzed.

3. [Link] is the type of the sub array generated by L. For any type·t, we
assume that its width is given by [Link]. We use types as attributes,
rather than widths, since types are needed anyway for type checking.
For any array type t, suppose that [Link] gives the element type.

 The location for the array reference is therefore [Link][[Link]] .

 Syntax-Directed Translation Into Three-
Address code

• The syntax-directed definition for E in a production

id := E, has following two attributes:

1. [Link] - the location (variable name or offset) that
holds the value corresponding to the nonterminal.
2. [Link] - the sequence of three-address statements
representing the intermediate code for the nonterminal.

36
 Syntax-Directed Translation into Three-Address Code for
assignment stmt
Grammar:- Semantic rules :-
S id := E [Link] = [Link] || gen(‘mov’ [Link] ‘, , ’ [Link])

E E1 + E2 [Link] = newtemp(); //t1 is created and it’s value assigned to E as

[Link]
[Link] = [Link] || [Link] || gen(‘add’ [Link] ‘,’ [Link] ‘,’
[Link])

E id [Link] = [Link]; // [Link] holds value of id

[Link] = null // no TAC code for E

[Link]  synthesized attribute represents three address code for

assignment S
[Link] the name that will hold the value of E
[Link] the sequence of three address code evaluating E.
Newtemp() :- function call that returns a sequence of temporary variables
t1, t2,…
gen(
37 ) :- generates ICG (TAC) like t1= [Link] + [Link] and evaluate it.
 Syntax-Directed Translation into Three-Address Code for
assignment stmt
S  id := E [Link] = [Link] || gen(‘mov’ [Link] ‘,,’ [Link])
E  E1 + E2 [Link] = newtemp();
[Link] = [Link] || [Link] || gen(‘add’ [Link] ‘,’ [Link] ‘,’
[Link])
E  E1 * E2 [Link] = newtemp();
[Link] = [Link] || [Link] || gen(‘mult’ [Link] ‘,’ [Link] ‘,’
[Link])
E  - E1 [Link] = newtemp();
[Link] = [Link] || gen(‘uminus’ [Link] ‘,,’ [Link])
E  ( E1 ) [Link] = [Link];
[Link] = [Link] // ICG of E1 copied to E
E  id [Link] = [Link];
[Link] = null // no ICG code
[Link]  synthesized attribute represents three address code for assignment
S
[Link] the name that will hold the value of E &
38
[Link] the sequence of three address code evaluating E.
 Translation Scheme to Produce
Three-Address Code
S  id := E{ p= lookup([Link]);
if (p is not nil) then emit(‘mov’ [Link] ‘,,’
p)
else error(“undefined-variable”) }
E  E1 + E2{ [Link] = newtemp();
emit(‘add’ [Link] ‘,’ [Link] ‘,’ [Link]) }
E  E1 * E2{ [Link] = newtemp();
emit(‘mult’ [Link] ‘,’ [Link] ‘,’ [Link])}
• lookup() function searches that id in symbol table.
• [Link] is synthesized attribute.
• emit( ) function generates Three address code.
39
 Translation Scheme to Produce Three-Address Code

E  - E1{ [Link] = newtemp();

emit(‘uminus’ [Link] ‘,,’ [Link]) }

E  ( E1 ){ [Link] = [Link]; }

E  id{ p= lookup([Link]);
if (p is not nil) then [Link] = [Link]
else error(“undefined-variable”) }

40
next
Control Flow statements

newlabel () creates a new label each time it

is called, and that label(L) attaches label L
to the next three-address instruction to be
generated.
We use a local variable begin to hold a new
label attached to the first instruction for this
while-statement, which is also the first
instruction for B.
We use a variable rather than an attribute,
because begin is local to the semantic rules for
this production
Syntax-Directed Translation for if
else and while
Syntax-Directed Translation for if
else and while

The code for S -> S1 S2 consists of the code for

S1 followed by the code for S2•
 The semantic rules manage the labels; the first
instruction after the code for S1 is the
beginning of the code for S2; and the
instruction after the code for S2 is also the
instruction after the code for S.
 Syntax Directed Translation ( Translation
scheme) of Boolean expressions
E → E1 or E2{[Link] := newtmp()
emit([Link] ':=' [Link] 'or'
[Link]) }

E → E1 and E2 {[Link]:= newtmp()

emit([Link] ':=' [Link] 'and'
[Link]) }

E → not E1 {[Link] := newtmp()

emit([Link] ':=' 'not' [Link])}

45
 Syntax directed translation ( Translation
scheme) of Boolean expressions
E → id1 relop id2 {
[Link] := newtmp()
emit(if [Link] relop [Link]
goto nextstat+3)
emit([Link] = 0)
emit(goto nextstat+2)
emit([Link] = 1) }
E → true {[Link] := newtmp()
emit([Link] = '1') }

E → false {[Link] := newtmp()

emit([Link] = '0')}
46
 Example:
Code for a < b or c < d and e < f

100: if a < b goto 103 109: t3 = 0

101: tl = 0 110: goto 112
102: goto 104 111: t3 = 1
103: tl = 1 112: t4 = t2 and t3
104: if c < d goto
107 113: t5 = tl or t4
105: t2 = 0
106: goto 108
107: t2 = 1
108:if e < f goto 111
47
 Syntax-Directed Translation (cont.)
S  if E then S1 else S2 [Link] = newlabel();
[Link] = newlabel(); //[Link]
[Link] = [Link] ||
gen(‘jmpf’ [Link] ‘,,’ [Link]) ||
[Link] ||
gen(‘jmp’ ‘,,’ [Link]) ||
gen([Link] ‘:”) || [Link] ||
gen([Link] ‘:”)

 newlabel () creates a new label each time it is

called.
48
 Syntax-Directed Translation (cont.)
S while E do S1 [Link] = newlabel();
[Link] = newlabel();
[Link] = gen([Link] “:”) || [Link] ||
gen(‘jmpf’ [Link] ‘,,’ [Link]) ||
[Link] ||
gen(‘jmp’ ‘,,’ [Link]) ||
gen([Link] ‘:”)

newlabel () creates a new label each time it is called, and that

label(L) attaches label L to the next three-address instruction
to be generated.

49
Control-Flow Translation of Boolean Expressions

back
 Control-Flow Translation of Boolean
Expressions
Suppose B is of the form B1 || B2:-

If B1 is true, then we immediately know that B itself

is true, so [Link] is the same as [Link].
If B1 is false, then B2 must be evaluated, so we
make [Link] be the label of the first instruction in
the code for B2.
The true and false exits of B2 are the same as the
true and false exits of B, respectively.
Control-Flow Translation of Boolean
Expressions
 Control-Flow Translation of Boolean
Expressions

• No code is needed for an expression B of the form ! B1.

• Just interchange the true and false exits of B to get the true and
false exits of B1.
Control-Flow Translation of Boolean
Expressions
The fourth production B -> E1 reI E2, is translated
directly into a comparison three-address instruction
with jumps to the appropriate places.
For instance, B of the form a < b translates into:
1. if a < b goto [Link]
2. goto [Link]
 B-> true
B->false
 The constants true and false translate into jumps
to [Link] and
B·false, respectively.
 Translation Schemes for Declarations
statements
For each name create symbol table entry with
information like type and relative address

P → {offset=0} D

D→D;D

D → id : T {enter([Link], [Link], offset);

offset = offset + [Link] }

T → integer {[Link] = integer; [Link] = 4}

T → real {[Link] = real; [Link] = 8}

58
 Declarations …
T → array [ num ] of T1
{[Link] = array([Link], [Link])
[Link] = [Link] x [Link]}

T → ↑T1
{[Link] = pointer([Link])
[Link] = 4}

59
 Case Statement
switch expression
begin
case value: statement
case value: statement
….
case value: statement
default: statement
end
 evaluate the expression

 find which value in the list of cases is the same as the

value of the expression.
 Default value matches the expression if none of the
values explicitly mentioned in the cases matches the expression
72  execute the statement associated with the value found
 Translation
code to evaluate E code to evaluate E into t
into t goto test
if t <> V1 goto L1 L1: code for S1
code for S1 goto next
L2: code for S2
goto next
goto next
L1 if t <> V2 goto L2
……
code for S2 Ln: code for Sn
goto next goto next
L2: …… test: if t = V1 goto L1
Ln-2 if t <> Vn-l goto if t = V2 goto L2
Ln-l ….
code for Sn-l if t = Vn-1 goto Ln-1
goto next goto Ln
next: stmt after switch case block
Ln-1: code for Sn
next:
73 Efficient for n-way
branch
 Back Patching

It is a way to implement Boolean

expressions and flow of control statements
in one pass.

The idea of backpatching is to leave the

label unspecified and fill it later once we get
it in future.

 Intermediate code is generated as

quadruples into an array.
74  Labels are indices into this array.
 Back Patching
a<b or c>d and e<f

100: if a<b goto 106 106:

101: goto 102
102: if c>d goto 104
103: goto 107
104: if e<f goto 106
107:
105: goto 106
106: (true)
107: (false)
 Back Patching

Functions in backpatching:
 makelist(i): create a newlist containing index i. It
returns a pointer to the list.

 merge(L1,L2): merge lists pointed to by L1 and L2

and return a pointer to the concatenated list

 backpatch(L, label): insert the target label for the

statements in the list pointed to by L

 nextquad : gives index of next quadruple.

76
 Boolean Expressions
E → E1 or M E2
| E1 and M E2
| not E1
| (E1)
| id1 relop id2
| true
| false
M→Ɛ

 Insert a marker non terminal M into the grammar to pick up index or

address of next quadruple.

 Attributes truelist and falselist are used to generate jump code for
boolean expressions

 Incomplete jumps are placed on lists pointed to by [Link] and

[Link]
77
 Boolean expressions …
Consider E → E1 and M E2

if E is false then E is also false, so statements in

1
[Link] become part of [Link]

if E is true then E must be tested, so target of

1 2
[Link] is beginning of E2

target is obtained by marker M

attribute [Link] records the number of the first

statement of [Link]

78
 Syntax Directed Translation for Boolean expression using back patching

E → E1 or M E2
{backpatch([Link], [Link])
[Link] = merge([Link], [Link])
[Link] = [Link]}

E → E1 and M E2
{backpatch([Link], [Link])
[Link] = [Link]
[Link] = merge([Link], [Link])}

E → not E1
[Link] = E1 falselist
[Link] = [Link]

E → ( E1 )
[Link] = [Link]
79
[Link] = [Link]
 E → id1 relop id2
[Link] = makelist(nextquad)
[Link] = makelist(nextquad+1)
gen(if id1 relop id2 goto --- )
gen(goto ---)

M→ Ɛ
[Link] = nextquad // M have the index or address of
E2.
// if E1 is false, then we have to evaluate
E2 by jumping on E2

80
 Generate code for 100: if a < b goto 106
a < b or c < d and e < f 101: goto 102
102: if c < d goto 104
103: goto 107
Initialize nextquad to 100 104: if e < f goto 106
105: goto 107
106: (true)
E.t={100,104} 107: (false)
E.f={103,105}

backpatch(102,104)
E.t={100} E.t={104} backpatch(101,102)
or M.q=102
E.f={101} E.f={103,105}
Є
a < b E.t={102} E.t ={104}
M.q=104
E.f={103} and E.f={105}

c < d Є
81 e < f
 Flow of Control Statements
S  if E then S1
| if E then S1 else S2
| while E do S1
| begin L end
|A

LL;S
| S

S : Statement
A : Assignment
L : Statement list
82
 Position := initial + rate * 60
intermediate code generator
lexical analyzer
temp1 := inttoreal (60)
id1 := id2 + id3 * 60 temp2 := id3 * temp1
temp3 := id2 + temp2
syntax analyzer id1 := temp3
:=
code optimizer
id1 +
id2 * temp1 := id3 * 60.0
id1 := id2 + temp1
id3 60
code generator
semantic analyzer
MOVF id3, R2
:= MULF #60.0, R2
id1 + MOVF id2, R1
ADDF R2, R1
id2 * MOVF R1, id1
id3 inttoreal
60
The Phases of a Compiler
83