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.

Persoalan-persoalan dalam merancang code generator

Persoalan-persoalan Seperti memory management, instruction selection, register allocation dan evaluation order adalah masalah-masalah yang ada dihampir semua code generation. Pada bab ini, kita akan menjelaskan permasalahan yg umum dlm merancang pembangkitan kode. Input ke code generator
Input ke pembangkit code terdiri dari representasi source program lanjutan yang menghasilkan ujung akhir, bersamaan dengan informasi di tabel symbol yg di gunakan untuk menentukan alamat run-time dari data objek yang ditandai dgn nama dan representasi lanjutan. Target program Output dari pembangkitan code adalah target program. Output ini mungkin memiliki bentuk yang berbeda: bahasa mesin absolut, bahasa mesin relocatable, atau bahasa assembly. Membuat program bahasa mesin sebagai output memiliki pengembangan yang ditempatkan di lokasi memori yg tetap dan dieksekusi segera. Program yg kecil dapat di-compil dan dieksekusi dgn cepat.

Membuat program bahasa mesin yg ditempatkan kembali (modul objek) sebagai output menizinkan sub-program di-compile secara terpisah. Pengaturan modul objek yg ditmpatkan kembali bisa di-link bersamaan dan diproses untuk dieksekusi.
Membuat program bahasa assembli sebagai output membuat proses pembangkitan kode mudah. Kita bisa mengembangkan instruksi simbolik dan menggunakan fasilitas-fasilitas macro dalam pembangkitan kode. Harga terbayarkan tahapan rakitan setalah pembangkitan kode. Karena membuat kode rakitan tidak bisa menduplikat tugas-tugas assembler, pilihan ini adalah alternativ lain khususnya untuk mesin dgn memori yg kecil, dimana kompiler harus memakai pass lainnya.

Memory management Pemetaan nama dalam source program ke alamat-alamat data objek di memory run-time dilakukan bersama diujung akhir dan pembangkit code.
Jika kode mesin dibangkitkan, lebel di pernyataan tiga-alamat harus dikonversi ke instruksi alamat. Proses ini dianalogikan seperti teknik ”backpatching”.

Instruction selection Pengaturan instruksi dari target mesin menentukan kesulitan instruksi pilihan. Keseragaman dan kelengkapan set instuksi adalah factor penting. Jika target mesin tidak mendukung setiap tipe data yang seragam. Kecepatan instruksi dan idiom mesin adalah faktor penting lainnya.Kualitas dari kode pembangkit ditentukan oleh speed dan size-nya. Contoh, setiap statement tiga-alamat dgn bentuk x:=y+z, bisa diubah kedlm urutan code.

Mov y,R0 /* proses y ke register R0 */

Add z,R0 /* tambah z ke R0 */

Mov R0,x /* simpan R0 ke x */

Sayangnya, statement-statement kode pembangkit seperti ini sering salah kode prosedur. Contoh, statement a := b + c + d := a + e akan diterjemahkan kedalam MOV b,R0

ADD c,R0

MOV R0,a

MOV a,R0

ADD e,R0

MOV R0,d

Pada statement keempat di-redundant, begitu juga yg ketiga jika a bukan kelanjutan yg digunakan. Register allocation Perintah-perintah menyertakan operasi register biasanya untuk memperpendek dan mempercepat dari pada perintah-perintah tersebut menyertakan operasi di memori. Menggunakan register sering dibagi lagi kedalam 2 sub-masalah:

- Selama register allocation, kita pilih variabel yang akan kita letakkan di register didalam sebuah program.

- Kemudian saat fase register assignment, kita angkat register yang khusus itu yang akan diletakkan variabel didalamnya.

Secara matematis, masalahnya adalah NP-complete. Maslahnya lebih rumit karena hardware dan/atau operating system target mesin yg mungkin membutuhkan aturan register-usage tertentu untuk diamati.

Mesin-mesin tertentu meminta register-pairs untuk beberapa operasi dan hasil. Contoh, pd mesin IBM system/370 Choice of evaluation order
Pesanan dimana proses perhitungan dilakukan bisa mempengaruhi efisiensi target code. Awalnya, kita seharusnya menghindari masalah dengan me-generat code untuk stetmen three-address, selama pesanan yang mereka telah dibuat oleh code generator lanjutan. Approaches to code generation Tidak diragukan lagi bahwa ukuran yang terpenting untuk code generator adalah peng-code-an yang benar.

Target mesin

Pada bab ini, kita akan guanakan target computer sebagai mesin register yang mewakili beberapa minikomputer. Biargimanapun teknik code-generation dijelaskan di bab ini telah digunakan pada kelas-kelas mesin lain.

Instruction costs

Contoh:
1. instruksi MOV R0,R1 copy isi yg ada di register R0 ke register R1. insstruksi ini memiliki nilai satu, sejak itu menempati satu kata dr memori.
2. instruksi ADD #1,R3 menambah constanta 1 ke isi dr register 3, dan memiliki nilai dua, sejak konstanta 1 harus muncul di kata selanjutnya mengikuti instruksinya.

Run-Time Storage Management

Informasi dibutuhkan selama eksekusi dr suatu prosedur disimpan di blok penyimpanan yang memanggil aktivasi record; penyimpanan untuk nama local ke prosedur juga kelihatan pd saat melakukan record.
Saat run-time alokasi dan dealokasi melakukan record terjadi sebagai bagian dari prosedur rangkaian call dan return, kita focus pd three-address statements berikut:

1. call,

2. return,

3. halt, dan

4. action, suatu tempat untuk statement lainnya.

Basic Blocks And Flow Graphs

Sebuah graph mewakili statement three-address, yang disebut alur graph(flow graph), digunakan untuk menjelaskan algoritma code-generator, bahkan jika graph tidak dibuat dengan tegas oleh algoritma code-generator. Node-node menjelalaskan proses computasi, dan edge-edge manjelaskan arah alur.

Basic blocks Basic blok adalah sebuah rangkaian statement yang dpt memutuskan dimana arah alur masuk saat mulai dan keluar saat akhir. Transformations on basic blocks Basic blok menghitung suatu set ekspresion. Ekspresion tersebut berupa nilai dr nama blok. Dua basic blok dinyatakan equivalen jika melakukan suatu set ekspresion yg sama. Bilangan dr trnsformasi bisa diterapkan ke sebuah basic blok tanpa merubah set ekspresion hitung oleh blok.

Structure-preserving transformations Srtucture-preserving transformation yg utama pd basic blok adalah:

1. common subexpression elimination

2. dead-code elimination

3. renaming of temporary variables

4. interchange of two independent adjacent statement

Algebraic transformation Transformation aljabar bisa digunakan untuk merubah set ekspresion yg dihitung oleh sebuah basic blok kedalam set equivalent aljabar.
Contoh:

x:= x + 0

or

x:= x * 1

bisa dieliminasi dari block dasar tanpa mengganti set kalimat penghitungan itu. Operasi eksponen pada statement

x:= y ** 2

biasanya permintaan fungsi call untuk diimplementasi. Dengan transformasi aljabar, statement ini bisa diganti dgn murah, tapi statement equivalen

x:= y * y

Flow graphs Kita bisa menambahkan informasi arah alur ke set basic blok yg dpt meningkatkan program dengan membuat arah graph yg disebut flow graph. Node-node dr flow graph adlah basic blok. Satu node dibedakan sebagai inisial; blok yg pertama adalah statement yang pertama. Representation of basic bloks
Basic blok dapat direpresentasikan oleh struktur data yg berbeda.
Loops Loop adalah kumpulan node-node dalm flow graph. Loop yg berisi tdk lain loop disebut inner loop.

Next-Use Information

Pada bagian ini,kami kumpulkan informasi yg digunakan tentang nama-nama di dasar blok. Jika nama di register tidak lagi diperlukan, maka register dapat diberi nama lain. Ide ini, nama dalam penyimpanan hanya jika akan digunakan kemudian dapat diterapkan dalam sejumlah konteks. kode generator yang sederhana di bagian selanjutnya berlaku untuk tugas register. Sebagai akhir aplikasi, kami mempertimbangkan tugas penyimpanan sementara untuk nama. Penyimpanan untuk nama yg sementara walaupun mungkin berguna dalam mengoptimalkan kompiler untuk membuat nama sementara yang berbeda setiap kali diperlukan, ruang harus dialokasikan untuk memegang nilai-nilai temporaries. ukuran field yg sementara dlm aktivasi umum yg dicatatan pd bagian 7,2 tumbuh dengan jumlah sementara.
Umumnya,kumpulan dua temporariries kedalam lokasi yg sama jika tdak berlangsung secara simulta. Kita bisa menempatkan lokasi penyimpanan untuk sementara oleh masing-masing secara bergantian memeriksa dan menugaskan sementara ke lokasi yang pertama di lapangan untuk temporaries yang tidak berisi tinggal sementara. jika sementara tidak dapat diberikan ke setiap lokasi dibuat sebelumnya, tambahkan ke lokasi baru data daerah untuk prosedur saat ini. dalam banyak kasus, temporaries dapat dikemas ke dalam register daripada memori lokasi.

A Simple Code generator

Contoh, kita asumsikan; untuk setiap operasi statement ada sesuai target bahasa operator. Kita juga asumsikan bahwa hasil penghitungan bisa dapat dibiarkan dalam register selama mungkin, mereka hanya menyimpan (a) jika register diperlukan untuk komputasi lain atau (b) hanya sebelum prosedure call, jump atau pernyataan berlabel. Kondisi (b) menunjukkan bahwa semuanya harus disimpan sebelum akhir dasar blok.

Register dan deskripsi Alamat Algoritma Kode pembangkit menggunakan descriptors untuk melacak konten register dan alamat untuk nama.

1. register melacak keterangan atas apa yang sedang disetiap register. berkonsultasi ketika ia baru register diperlukan. Kami menganggap bahwa pada awalnya register keterangan menunjukkan bahwa semua register yg kosong.Sebagai kode pembangkit blok berlangsung.masing-masing register akan memegang nilai nol atau lebih nama pada suatu waktu.

2. keterangan alamat melacak lokasi dimana nama nilai bisa ditemukan saat dijalankan. Lokasi mungkin di register, tumpukan lokasi, memori alamat atau beberapa set ini, sejak saat disalin, nilai juga tetap di mana itu berada. informasi ini dapat disimpan dalam tabel simbol dan digunakan untuk menentukan metode untuk mengakses nama. Algoritma Code generation Algoritma code pembangkit mengambil sebagai masukan yang urutan tiga alamat dasar pernyataan constituting blok. untuk setiap tiga alamat-pernyataan dalam bentuk x:= y kami melakukan tindakan berikut:

1. memohon fungsi getreg untuk menentukan lokasi di mana L hasil penghitungan

y op z harus disimpan.

2. berkonsultasi dengan alamat dan keterangan untuk menentukan y '. register lebih memilih untuk y 'jika nilai y saat ini baik dalam memori dan register. jika nilai y belum di L, menghasilkan instruksi MOV y', L untuk menempatkan salinan y di L.

3. menghasilkan instruksi op z’ , L dimana z’ adalah lokasi z. lagi, lebih suka mendaftar ke lokasi memori jika z dalam keduanya. memperbarui alamat keterangan of x untuk menunjukkan bahwa x adalah di lokasi L.

4. jika saat ini nilai-nilai y and/or z tidak menggunakan keluar, tidak tinggal di keluar dari blok, dan berada dalam register, mengubah register keterangan untuk menunjukkan bahwa, setelah pelaksanaan x:= y op z, register yang tidak lagi akan mengandung y and/or z, masing-masing.