Code Generation

Tahap terakhir dari kompilasi adalah code generator. Input code generator adalah intermediate representation dari source program, sedangkan outputnya adalah program yang ekivalen.

Posisi code generator dalam kompilasi adalah sebagai berikut:

Persyaratan code generator

• Output code harus benar dan berkualitas tinggi, yaitu harus menggunakan resources dan target machine secara efektif.
• Harus efisien

Secara matematiks, masalah untuk membangkitkan code yang optimal adalah undercidable. Secara praktik kita akan menggunakan teknik heuristic yang bagus, tetapi tidak selalu berarti optimal code.

Issue-issue dalam Code Generator Design

Walaupun sangat tergantung kepada target machine dan operating system, masalah-masalah yang penting dalam code generator adalah:

• Input untuk code generator
• Target program
• Memory management
• Instruction selection
• Register allocation
• Pemulihan urutan evaluation
• Pendekatan code generation

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 nama-nama dalam intermediate representation.

Diasumsikan bahwa sebelum code generator, fron-end teleh men-scan, memparse, dan menerjemahkan source ke dalam intermediate representation detail. Selain itu juga diasumsikan telah diadakan type checking sehingga type-conversion operator telah di-insert di mana perlu dan semantic error telah dideteksi.

Target Program

Output dari code generator adalah target program yang bisa mengambil bentuk:

• Absolute Machine Language
• Recocatable Machine Language
• Assembly LanQuange

Target program dalam bentuk Absolute machine language mempunyai keuntungan dapat ditempatkan dalam lokasi yang fixed di dalam memori dan langsung dapat dieksekusi. Program yang kecil dapat dikomplasi 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 subprogram yang dapat dikompilasi secara terpisah. Satu set relocatable object module dapat di link bersama-sama dan dapat di load oleh linking loader untuk dieksekusi.

Walaupun keluar usaha ekstra untuk linking dan loading, namun kita mendapat fleksibilitas karena dapat mengkompilasi subroutine secara terpisah.

Assembly Language program sebagai target program mempunyai keuntungan kemudahan proses code generation. Kita dapat menggenerate symbolic instruction dan menggunakan fasilitas makro dari assembler untuk meng-generate code. Biaya yang harus dikeluarkan adalah tahap assembly setelah code generator.

Memory Management

Memetakan nama di dalam source program ke address, dari object dalam run-time memory dikerjakan bersama-sama oleh front-end 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.

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 three-address statement dalam bentuk x:=y+z di mana x,y dan z dialokasikan secara static, dapat diterjemahkan ke dalam sekuens code:

MOV y, RO        /* load y ke dalam register RO */

ADD z, RO        /* add z ke RO */

MOV RO, x        /* store RO ke dalam x

Namun statement-by-statement code generation ini sering menghasilkan code yang buruk.

Contoh: Sekuens dari statement

a := b + c

d := a + c

dapat diterjemahkan ke dalam:

MOV v, RO
ADD c, RO
MOV RO, a
MOV a, RO
ADD e, RO
MOV RO, d

Di sini statement ke-empat akan redundant, juga statement yang ketiga jika a tidak digunakan secara berurutan.

Register Allocation

Instruksi yang melibatkan register operand biasanya lebih pendek dan lebih cepat daripada yang memperlihatkan operand di dalam memori.

Karena itu penggunaan register yang efisien sangat penting untuk mengenerate code yang baik.

Penggunaan register dibagi ke dalam 2 sub-masalah:

1. Selama register allocation, dipilih variabel-variabel yang akan menetap di dalam register pada suatu titik dalam program
2. Selama register assigenment, diambil register khsusus di mana variabel akan menetap.

Menemukan optimal assigment dari register untuk variabel sulit, walaupun dengan single register. Secara matematis, problem ini adalah NP-Complete.

Pemilihan Urutan Evaluasi

Urutan pelaksanaan komputasi dapat mempengharuhi efiensi dari target code. Beberapa urutan komputasi memerlukan register yang lebih sedikit untuk menampung intermediate result daripada yang lainnya. Mengambil problem ini adalah NP-Complete Problem.

Pendekatan Code Generator

Kriteria terpenting untuk code generator adalah menghasilkan code yang baik. Salah satu tujuan design yang penting dari code generator adalah:

• Mudah diimplementasikan
• Mudah ditest
• Mudah dipelihara