Pembangkit Kode
1
Learning Outcomes Pada akhir pertemuan ini, diharapkan mahasiswa akan mampu : Mahasiswa dapat menunjukkan hasil code genarator dari suatu kasus kompilasi program (C3) Mahasiswa dapat membuat diagram / skema perancangan compiler yang paling optimal (C4)
2
Outline Materi
Issues dalam disain code generator The target machine Basic block dan flow graph Representasi DAG dari basic block Register allocation and assignment
3
Posisi Code Generation Tahap terakhir dari kompiler adalah code generator. Input code generator adalah intermediate representation dari source program, sedangkan outputnya adalah target program yang ekivalen. Posisi code generator dalam kompiler adalah sebagai berikut : source program
front end
intermediate code
code optimizer
intermediate code
code generator
target program
symbol table
4
Persyaratan code generator : output code harus benar dan berkualitas tinggi, yaitu harus menggunakan resources dari target machine secara efektif. harus efisien. Secara matematis, masalah untuk membangkitkan code yang optimal adalah undecidable. Secara praktek, kita akan mengguna-kan teknik heuristik yang bagus, tapi tidak selalu berarti optimal code. 5
Issue-issue dalam Code Generator Design Walaupun sangat tergantung kepada target machine dan operating system, masalahmasalah yang penting dalam code generation adalah : – – – – – – –
Input untuk code generator Target program Memory Management Instruction Selection Register Allocation Pemilihan Urutan Evaluation Pendekatan Code Generator 6
Input Untuk Code Generator Input untuk code generator terdiri dari intermediate representation dari source program yang dihasilkan oleh front-end, bersama dengan informasi di dalam symbol table yang digunakan untuk menentukan run time address dari data object yang ditunjukkan oleh namanama dalam intermediate representation. Diasumsikan bahwa sebelum code generation, front-end telah men-scan, men-parse, & menerjemahkan source program ke dalam intermediate repre-sentation detail. Selain itu, diasumsikan telah dilakukan type checking, sehingga type-conver-sion operator telah di-insert dimana perlu & semantic error telah dideteksi. 7
Target Program
Output dari code generator adalah target program, yang bisa mengambil bentuk : – – –
Absolute Machine Language Relocatable Machine Language Assembly Language
Target program dalam bentuk Absolute machine language mem-punyai keuntungan dapat ditempatkan dalam lokasi yang fixed di dalam memory & langsung dapat dieksekusi. Program yang kecil dapat di-kompile dan dieksekusi dengan cepat. Contoh : sejumlah “student-job” compiler, seperti WATFIV dan PL/C Keuntungan target program dalam bentuk Relocatable Machine Language Program (Object Module) adalah sub-program dapat di-kompile secara terpi-sah.Satu set relocatable object module dapat di-link bersama-sama & di-load oleh linking loader untuk dieksekusi. Walaupun keluar usaha ekstra untuk linking & loading,namun kita mendapat fleksibilitas karena dapat mengkompile subroutine secara terpisah. Assembly Language program sbg tar-get program mempunyai keuntungan kemudahan proses code generation. Kita dapat men-generate symbolic instruction & menggunakan fasilitas makro dari assembler untuk men-generate code. Biaya yang harus dikeluarkan adalah tahap assembly setelah code generation. 8
Memory Management Memetakan nama di dalam source program ke address dari data object dalam run-time memory dikerjakan bersama-sama oleh frontend dan code generator. Diasumsikan bahwa nama dalam three-address statement merefer kepada symbol-table entry untuk nama tersebut. Tipe dalam deklarasi menentukan lebar (jumlah storage) yang diperlukan untuk nama yang dideklarasikan. – Register R0, R1, . . ., Rn-1 – op source, destination
MOV (move source to destination) ADD (add source to destination) SUB (subtract source to destination) – Address mode – Instruction Cost 9
Instruction Selection
Uniformity dan completeness dari instruction set adalah faktor yang penting. Selain itu, faktor yang penting lainnya adalah instruction speed dan machine idiom. Contoh : – Setiap threethree-address statement dalam bentuk : x := y + z – dimana x, y, dan z dialokasikan secara static, dapat diterjemahkan ke dalam sekuens code : MOV y, R0 /* load y ke register R0 */ ADD z, R0 /* add z ke R0 */ MOV R0, x /* store R0 ke dalam x */
Namun statement-by-statement code generation ini sering menghasilkan code yang buruk.
Contoh : Sekuens dari statement a := b + c d := a + e dapat diterjemahkan ke dalam : MOV b, R0 ADD c, R0 MOV R0, a MOV a, R0 ADD e, R0 MOV R0, d
Di sini statement ketiga dan keempat akan redundant, juga statement yang ketiga jika a tidak digunakan secara berurutan. 10
Register Allocation
Instruksi yang melibatkan register operand biasanya lebih pendek dan lebih cepat daripada yang melibatkan operand di dalam memory. Karena itu, penggunaan register yang efisien sangat penting untuk membangkitkan code yang baik. Penggunaan register dibagi ke dalam 2 sub-masalah : – Selama register allocation, dipilih variable-variable yang akan mene-tap di dalam register pada suatu titik dalam program. – Selama register assignment, diam-bil register khusus dimana variabel akan menetap. Menemukan optimal assignment dari register untuk variabel sulit, walaupun dengan single register. Secara matematis, problem ini adalah NP-Complete. 11
Pemilihan Urutan Evaluasi Urutan dilakukannya komputasi dapat mempengaruhi efisiensi dari target code. Beberapa urutan komputasi memerlukan register yang lebih sedikit untuk menampung intermediate result daripada yang lainnya. Mengambil urutan terbaik adalah NP-Complete Problem.
12
Pendekatan Code Generator
Kriteria terpenting untuk code genera-tor adalah menghasilkan code yang baik. Salah satu tujuan perancangan yang penting dari Code Generator adalah : – mudah diimplementasikan – mudah ditest – mudah di-maintain
13
Run-Time Storage Strategi alokasi : Static dan Stack Static allocation – Pada static allocation statement call diterjemahkan menjadi : Move #here + 20, callee.static_area GOTO calle.code_area
Three-Address Code
Activation Record for c (64 bytes)
Activation Record for p (88 bytes)
/* code for c */ action1 call p action2 halt /* code for p */ action3 return
0:return address 8: arr
0:return address 4: buf
56:i 60:j
84:n
14
