Intermediate Code Generator

1
 Learning Outcomes

Pada akhir pertemuan ini, diharapkan mahasiswa

akan mampu :
• Mahasiswa dapat menerangkan tahapan dan
proses intermediate code genarator (C2)
• Mahasiswa dapat mendemonstrasikan metode
implementasi intermediate code generator (C3)

2
 Outline Materi

• Keguanaan intermediate code genarator

• Intermediate languages
• Syntax tree
• Posfix notation
• Three address code
• Implementasi three address statement
• Representasi quadruple
• Representasi triple
• Representasi indirect triple

3
 Intermediate Code Generation
• Intermediate codes are machine independent codes, but they are
close to machine instructions.
• The given 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
• we will 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. 4
 Intermediate Code Generation

• Walaupun sumber program dapat diubah secara langsung

menjadi bahasa target, ada manfaat yang dapat diambil dari
pemakaian bentuk antara yang tidak tergantung pada mesin
yang digunakan yaitu :
– Suatu kompilator untuk mesin yang berbeda dapat
dibentuk
– Optimasi kode dapat dilakukan pad representasi antara,
dimana optimasi ini tidak tergantung pada mesin
• Bentuk representasi antara ada 3 yaitu :
– Pohon sintak
– Notasi postfik
– Kode tiga alamat
• Aturan semantik untuk membentuk kode tiga alamat dari
konstrak bahasa pemrograman adalah sama dengan aturan
semantik untuk membentuk pohon sintak atau membentuk 5
notasi postfik
 Pohon Syntak & Notasi Postfik
• Suatu pohon sintak menggambarkan struktur hirarkis dari suatu program
sumber
• DAG juga memberikan informasi yang sama tetapi dalam bentuk yang lebih
padat karena beberapa subekspresi yang sering muncul
• Contoh : Statement assignment a = b * -c + b * -c
Pohon Sintak DAG
assign
assign

a +
a +

* * *

b uminus b uminus b uminus

c c
c
• Notasi postfik merupakan representasi linier dari pohon sintak dgn melakukan
kunjungan post order notasi postfik untuk pohan sintak di atas :
• a b c uminus * b c uminus * + assigg 6
7
8
9
 Kode Tiga Alamat

• Kode tiga alamat  barisan statement dalam bentuk umum :

x=y op z
– x,y,z  nama, konstanta, variabel sementara yg dibentuk oleh
kompilator
– op  sembarang operator misal aritmetika floating point, aritmetika
tertentu, logika pada data bernilai boolean
– Tidak boleh ada ekspresi yang dibuat lebih dari satu operator
• Ekspresi x+y*z dapat diubah menjadi barisan :
– t1 = y * z
– t2 =x + t
– t1dan t2  nama sementara yang dibentuk oleh kompilator
• Kode tiga alamat merupakan representasi linier dari suatu
pohon sintak atau suatu DAG  nama-nama
berkorespondensi dengan node-node interior dari graph
• Nama-nama variabel dpt muncul langsung di dalam
statement tiga alamat
10
 Contoh Kode Tiga Alamat
• Contoh : Statement assignment a = b * -c + b * -c
assign assign

a + t5 a + t3

t2 * t4 *
t1 t3 t2 *
b uminus b uminus t1
b uminus

c c
t1= -c c
t1= -c
t2=b*t1
t2=b*t1
t3=-c
t3=t2+t2
t4=b*t3
a=t3
t5=t2+t4
11
a=t5
 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 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).
12
 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
gt a,b,c
addr a,b,c
addi a,b,c

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
not a,,c
inttoreal a,,c
13
 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
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
jmp ,,7 // jump to the statement 7

14
 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
jmpgte y,z,L1 // jump to L1 if y>=z
jmpe y,z,L1 // jump to L1 if y==z
jmpne y,z,L1 // jump to L1 if y!=z

Our relational operator can also be a unary operator.

jmpnz y,,L1 // jump to L1 if y is not zero
jmpz y,,L1 // jump to L1 if y is zero
jmpt y,,L1 // jump to L1 if y is true
jmpf y,,L1 // jump to L1 if y is false

15
 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,

f(x+1,y)  add x,1,t1

param t1,,
param y,,
call f,2,

16
 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

17
 Implementasi Tiga Alamat Quadrupel

• Struktur record dgn empat field  op, arg1,arg2,result

• Field op  mengandung kode internal utk operator
• Statement tiga-alamat x = y op z direpresentasi dng menempatkan y
di dalam arg1, z didlm arg2, dan x didlm result
• Statement dgn operator unari seperti x=-y atau x=y tidak memakai
arg2
• Isi dari field arg1,arg2 dan result biasanya berupa pointer yg
menunjuk pd entri tabel simbol
• Contoh : Statement assignment a = b * -c + b * -c
Quadrupel

Kode Tiga Alamat : Op arg1 arg 2 result

t1 = -c uminus c t1
t2 = b * t1 * b t1 t2
t3 = -c uminus c t3
t4 = b * t3 * b t3 t4
t5 = t2 + t4 + t2 t4 t5
a =t5 = t5 a 18
 Implementasi Tiga Alamat tripel
• Untuk menghindari nama sementara pad tabel simbol dapat
menyebutkan nilai semantara dengan posisi dari statement
yg menghitung nilai itu
• Statement tiga alamat dapat direpresentasikan dengan
record yg hanya mengandung tiga field yaitu op, arg1, arg2
• Contoh : Statement assignment a = b * -c + b * -c

Tripel

Kode Tiga Alamat : Posisi Op arg1 arg 2

t1 = -c 0 uminus c
t2 = b * t1 1 * b 0
t3 = -c 2 uminus c
t4 = b * t3 3 * b 2
t5 = t2 + t4 4 + 1 3
a =t 5 5 = a 4 19
20
 Three Address Codes - Example
x:=1; 01: mov 1,,x
y:=x+10; 02: add x,10,t1
while (x<y) {  03: mov t1,,y
x:=x+1; 04: lt x,y,t2
if (x%2==1) then y:=y+1; 05: jmpf t2,,17
else y:=y-2; 06: add x,1,t3
} 07: mov t3,,x
08: mod x,2,t4
09: eq t4,1,t5
10: jmpf t5,,14
11: add y,1,t6
12: mov t6,,y
13: jmp ,,16
14: sub y,2,t7
15: mov t7,,y
16: jmp ,,4
17:

21
22
23
24
 quiz

25