Teknik Kompilasi- Teknik Optimasi

TEKNIK OPTIMASI

Teknik Optimasi ada tiga(3) yaitu
1. Dependensi Optimasi.
2. Optimasi Lokal.
3. Optimasi Global.
Berikut penjelasannya
1. Dependensi optimasi bertujuan untuk menghasilkan kode program yang berukuran lebih kecil dan lebih cepat.
2. Optimasi lokal adalah optimasi yang dilakukan hanya pada bagian blok tertentu dari source code.di dalam optimasi lokal terdapat lima(5) cara pengomptimasiannya.
a. Folding yaitu mengganti konstanta atau ekspresi yang bisa dievaluasi pada saat compile time dengan nilai komputasinya. misalnya : A = 5+4+B bisa di ganti dengan A=9+B karena 9 dapat menggantikan ekspresi 5+4.
b. Redundant-Subexpression Elimination : hasilnya digunakan lagi dari pada dilakukan komputasi ulang, contohnya
A=B+C
X=Y+B+C
dapat diganti dengan 
A=B+C
X=Y+A (karena isi dari A sudah bisa mengganti B+C)

 
c. Loop Unrolling : mengganti suatu loop dengan menulis statement yang ada di dalam loop ditulis beberapa kali, contoh:
For i=1 to 2 do
A[i]=0;
dapat diganti dengan
A[1]=0;
A[2]=0;
d. Frequency Reduction : pemindahan statement ke tempat yang lebih jarang dieksekusi. contoh
for i=1 to 10 do
begin
X=5
A=A+1
end
karena X itu diisi dengan nilai yang tetap yaitu 5 maka bisa dipindahkan menjadi
x=5
for i=1 to 10 do

Teknik Kompilasi- Code Generator

CODE GENERATOR

Fase terakhir dalam model compiler adalah code generator. Code generator sebagai input yang representasi lanjutan dari source program dan hasil sebagai output equivalent dgn target program. Sesuai gambar 9.1. teknik pembangkit dalam bab ini digunakan sebagai tahap optimasi sebelum pembangkit code, hal ini disebut compiler “optimizing”.

Code Generation (kode pembangkit) Source intermediate intermediate  Program code code target program.

Tujuan secara tradisional membuat pembangkit code secara mencukil. code Output harus benar dan berkualitas, berarti harus efektiv pengguanan resource dari target mesin. Lebih dari itu pembangkit code dapat dijalankan penterjemah secara efektif. Masalah untuk membangkitkan code optimal secara matematika tdk dapat dijalankan. Secara praktis harus berisi cara-cara heuristik yg membangkitkan produk, tetapi tdk perlu mendapati code optimal. Pemilihan kode heuristic ini perlu dan dirancang dgn algoritma pembangkit code yang lebih mudah dan lebih cepat dgn algoritma yg diprkirakan secara serentak.

Teknik Kompilasi- Intermediate Code Generator

INTERMEDIATE CODE GENERATOR

Proses kompilasi dari suatu kompilator pada dasarnya dapat dibagi ke dalam 2 bagian utama yaitu bagian analisis dan bagian sintesis.Pada saat proses compiler ada tahap di mana pembentukan program sasaran dibentuk berdasarkan reprensentasi antara yang dihasilkan pada tahap analisis,tahap yang di maksud adalah tahap sintesis dimana tahapa sintesis terbagi dalam 3 bagian yaitu

• intermediate code generator
• code optimizer
• code generator.

Sintesis adalah membangun program sasaran yang diinginkan dari bentuk antara . Pada bagian ini kita akan menjelaskan sedikit tentang bagian pertama dari tahap sintesis yaitu intermediate code generator,yaitu membangkitkan kode antara (intermediate code) berdasarkan pohon parsing. Pohon parse selanjutnya diterjemahkan oleh suatu penerjemah yang dinamakan penerjemah berdasarkan sintak (syntax-directed translator). Hasil penerjemahan ini biasanya merupakan perintah tiga alamat (three-address code) yang merupakan representasi program untuk suatu mesin abstrak. Perintah tiga alamat bisa berbentuk quadruples (op, arg1, arg2, result), tripels (op, arg1, arg2). Ekspresi dengan satu argumen dinyatakan dengan menetapkan arg2 dengan - (strip, dash).

Intermediate adalah adalah sebuah representasi yang disiapkan untuk mesin abstrak tertentu.Di mana intermediatae tersebut harus memiliki dua sifat yang harus terpenuhi yaitu:

· Dapat dihasilkan dengan mudah

· Mudah ditranslasikan menjadi program sasaran(target program)

Representasi kode antara biasanya berbentuk perintah tiga alamat (three-address code),

baik berbentuk quadruples ataupun triples.Jika kita ingin mengambil sedikit contoh tentang cara kerja intermediate maka kita bisa melihat bagaimana intermediate bekerja dalam mengcompile sebuah bahasa pemrograman yang sederhana,dimana Tahap-tahap compiler yang dianalisa meliputi tahap scanner, parser, constrainer dan tahap code generator. Scanner mengambil karakter-karakter input dan mengelompokkannya menjadi token-token. Parser pada compiler ini merupakan program-driven parser yang mewujudkan grammar dalam bentuk algoritma, bersifat top-down dan termasuk recursive-descent parser untuk grammar LL(1). Constrainer memeriksa aturan pendeklarasian variabel, sedangkan tahap intermediate code generator menghasilkan bentuk positifinya yang memudahkan proses pembentukan kode output pada tahap code generator.

Bentuk dari intermediate code generator tergantung bagaimana pemrosesan yang dilakukan selama tahap sintesis,

temp1 := inttoreal(60)

temp2 := id3 * temp1

temp3 := id2 + temp2

id1 := temp3

Implementasi dari bentuk intermediate code generator dapat kita lihat seperti contoh berikut:

Syntax-Directed Translation

Bagian yang akan menghasilkan intermediate form dari source code. Fungsinya untuk menentukan maksud dari suatu source code. Meskipun secara konseptual sintaks dari suatu program dipisahkan dari semantiknya, mereka bekerja sama secara dekat. Keluaran dari bagian ini akan diberikan ke code genereator.

Kode-antara (intermediate code) dibentuk dari sebuah kalimat x dalam bahasa

context free. Kalimat x ini adalah keluaran dari parser. Syntax-directed transalation

adalah suatu urutan proses yang mentranslasikan parse tree menjadi kode-antara. Tahap

pertama dari pembentukan kode antara adalah evaluasi atribut setiap token dalam

kalimat x. Yang dapat menjadi atribut setiap token adalah semua informasi yang

disimpan di dalam tabel symbol. Evaluasi dimulai dari parse tree. Kumpulan aturan yang menetapkan aturanaturan semantik untuk setiap produksinya dinamakan syntax-directed definition. syntax-directed translation yang mentranslasikan ekspresi intinya menjadi ekspresi positfinya. Ekspresi intinya ini dapat dilihat sebagai sebuah kalimat yang dihasilkan oleh parser.

Contoh 1:

Diketahui : 1. kalimat x : 9 - 5 + 2

2. grammar Q = {E . E + T.E - T.T, T . 0.1.3.....9}

3. syntax-directed definition :

Produksi Aturan Semantik

E . E 1 + T E := E 1 .t ¦ T.t ¦ ‘+ ‘

E . E 1 - T E := E 1 .t¦ T.t ¦ ‘-‘

E . T E := T.t

E . 0 E := ‘0’

E . 1 E := ‘1’

... ...

E . 9 E := ‘9’

catatan : 1. Lambang ‘¦‘ menyatakan concatenation.

2. Mengingat catatan 1, aturan semantik kedua produksi pertama

adalah concate dua operan diikuti sebuah operator.

Langkah-langkah translasi

1. pembentukan parse tree : 2. pembentukan annonated parse tree :

E E = 95-2+

E + T E.t = 95- + T.t = 2

E - T 2 E.t = 9 - T.t = 5 2

T 5 T.t = 9 5

9 9

Translation Scheme

Translation scheme adalah grammar context free dimana sebuah frase yang

disebut semantic actions disertakan di sisi kanan setiap produksinya. Semantic actions ini adalah sebuah nilai sebagai hasil evaluasi atribut pada sebuah node. Dalam translation schemes, frase yang menyatakan action diapit dengan kurung kurawal. . Pada syntax-directed translation hasil akhir evaluasi atribut ditetapkan pada root dari parse tree melalui kunjungan dept-first traversal sedangkan pada translation scheme hasil tersebut ditetapkan pada setiap node (termasuk leaf) juga secara dept-first traversal. Contoh sebuah translation scheme dengan semantic action-nya adalah :

rest . + term {print(‘+’)} rest 1 ,

Pada contoh di atas, aksi {print(‘+’)} akan dilakukan setalah evaluasi terhadap term

selesai dan evaluasi terhadap rest 1 belum dilakukan. Dalam representasi parse tree,

semantic action pada translation scheme digambarkan dengan garis putus-putus sebagai

leaf tambahan. Dari penjelasan di atas terlihat bahwa translation scheme mirip dengan syntax-directed translation kecuali dalam prosedur evaluasi nilai atribut pada setiap nodenya. Pada syntax-directed translation hasil akhir evaluasi atribut ditetapkan pada root dari parse tree melalui kunjungan dept-first traversal sedangkan pada translation scheme hasil tersebut ditetapkan pada setiap node (termasuk leaf) juga secara dept-first traversal. Gramar dan kalimat pada contoh 1 di atas mempunyai translation schemes dan parse tree sebagai berikut

E

E . E + T {print(‘+’)}

E . E - T {print(‘-’)}

E . T E T

T . 0 {print(‘0’)}

E . 1 {print(‘1’)}

E - {print(‘-’)}2 {print(‘2’)}

...

T

E . 9 {print(‘9’)} T

5{print(‘5’)}

9 print(‘9’)}

+ {print(‘+’)}

Syntax Tree

Parse tree seringkali disebut sebagai concrete syntax tree. Parse tree tidak efisien

karena mengandung informasi yang berlebihan; sebagai gantinya, kalimat dinyatakan

sebagai abstract syntax tree atau sering disingkat sebagai syntax tree saja. Dalam syntax

tree setiap operator maupun keyword tidak muncul sebagai leaf.

contoh :

syntax tree untuk kalimat x : 9 - 5 + 2 dan y : if B then S 1 else S 2 :

+ if-then-else

- 2

B S 1 S 2

9 5

Membentuk Syntax Tree Sebuah Ekspresi

Pada pasal ini akan dibentuk sebuah syntax tree dimana setiap node-nya dinyata-

kan sebagai data record. Setiap record paling tidak mengandung sebuah label yang dapat berupa identifier, konstanta, atau operator. Proses pembentukan ini memerlukan tiga buah

function berikut :

1. mknode(op, left, right) : membentuk node operator dengan label op dan dua field

lainnya berupa pointer ke anak kiri dan anak kanan,

2. mkleaf(id, entry) : membentuk node identifier dengan label id dan sebuah field berupa pointer ke symbol table. Pelacakan identifier pada symbol table.

3. mkleaf(num, val) : membentuk node konstanta dengan label id dan sebuah field yang mengandung nilai bilangan.

Contoh: Diberikan ekspresi : a - 4 + c, dengan a dan c adalah identifier. Syntax tree akan dibentuk secara bottom-up. Berikut ini adalah algoritma pembentukan syntax tree untuk ekspresi yang diinginkan beserta bentuk syntax tree yang dihasilkannya :

(1) p1 := mkleaf(id, entrya); dimana :

(2) p2 := mkleaf(num, 4); -p1, p2, p3, p4, p5 : pointer ke node

(3) p3 := mknode(‘-‘, p1, p2); -entrya, entryc : pointer ke symbol table

(4) p4 := mkleaf(id, entryc); masing-masing untuk identifier a dan c

(5) p5 := mknode(‘+‘, p3, p4);

+

- id

id num 4 entry untuk c

entry untuk a

Grammar untuk ekspresi contoh 2 adalah : Q = {E . E + T.E-T.T, T. (E).id.num},

sedangkan syntax directed definition-nya adalah :

Produksi Aturan Semanti

E . E 1 + T E.nptr := mknode(‘+’, E 1 .nptr, T.nptr)

E . E 1 - T E.nptr := mknode(‘-’, E 1 .nptr, T.nptr)

E . T E.nptr := T.nptr

E . (E) T.nptr := E.nptr

E . id T.nptr := mkleaf(id, id.entry)

E . num T.nptr := mkleaf(num, num.val)

pada tabel di atas nptr adalah synthesized attribute, masing-masing untuk E dan T.

Sebuah atribut di sebuah node adalah synthesized attribute jika nilai atribut pada node tersebut ditentukan dari nilai-nilai atribut anak-anaknya.

Three Address Code

Bentuk umum three address code bagi sebuah pernyataan adalah : x := y op z,

dimana x, y, z adalah nama atau konstanta, sedangkan op adalah operator aritmatika atau operator logika. Ekspresi panjang seperti v := x + y * z dapat dinyatakan dengan three address code menjadi : t1 := y * z; t2 := x + t1; v := t2. Terdapat dua format untuk three address code, yaitu format quadruple (op, arg1, arg2, result) dan format triple (op, arg1, arg2). Isi dari arg1, arg2, dan result adalah pointer ke symbol table. Jika isi tersebut adalah temporary identifier, maka nama tersebut harus dimasukkan ke dalam symbol table begitu nama tersebut dideklarasikan atau diciptakan.

Contoh:Diberikan pernyataan : a := b * - c + b * - c.

Rangkaian three address code dari pernyataan ini adalah :

t1 := - c; t2 := b * t1; t3 := - c; t4 := b * t3; t5 := t2 := t4; a := t5

Pernyataan quadruple dan triple dari pernyataan di atas adalah :

Tabel format quadruple Tabel format truple :

NO	OP arg1 arg2 result	Op arg1 arg2
0	uminus c t1	uminus c
1	* b t1 t2	* b (0)
2	uminus c t3	uminus c
3	* b t3 t4	(3) * b (2)
4	+ t2 t4 t5	+ (1) (3)
5	:= t5 a	:= a (4)

Format quadruple untuk opearor unary seperti ‘- c’ menyebabkan arg2 tidak digunakan.

Format triple digunakan untuk menghindari penggunaan temporary identifier seperti

yang terjadi pada format quadruple. Format triple ini benar-benar mendayagunakan posisi

baris pernyataan. Sebagai contoh, pada baris kedua dari tabel format triple terlihat bahwa

isi arg2 adalah (0), yang tak lain dari ‘uminus c’.