Desain Kompilator - Pembuatan Kode

Pembuatan kode dapat dianggap sebagai tahap akhir kompilasi. Melalui pembuatan kode pos, proses optimasi dapat diterapkan pada kode, tetapi itu dapat dilihat sebagai bagian dari fase pembuatan kode itu sendiri. Kode yang dihasilkan oleh compiler adalah kode objek dari beberapa bahasa pemrograman tingkat rendah, misalnya bahasa assembly. Kita telah melihat bahwa kode sumber yang ditulis dalam bahasa tingkat yang lebih tinggi diubah menjadi bahasa tingkat yang lebih rendah yang menghasilkan kode objek tingkat yang lebih rendah, yang seharusnya memiliki properti minimum berikut:

Ini harus membawa arti yang tepat dari kode sumber.
Ini harus efisien dalam hal penggunaan CPU dan manajemen memori.

Sekarang kita akan melihat bagaimana kode perantara diubah menjadi kode objek target (kode assembly, dalam hal ini).

Grafik Asiklik Terarah

Grafik Asiklik Terarah (DAG) adalah alat yang menggambarkan struktur blok dasar, membantu melihat aliran nilai yang mengalir di antara blok dasar, dan menawarkan pengoptimalan juga. DAG menyediakan transformasi yang mudah pada blok dasar. DAG dapat dipahami di sini:

Simpul daun mewakili pengenal, nama, atau konstanta.
Node interior mewakili operator.
Node interior juga mewakili hasil ekspresi atau pengenal / nama tempat nilai-nilai akan disimpan atau ditetapkan.

Example:

t₀ = a + b
t₁ = t₀ + c
d = t₀ + t₁

[t ₀ = a + b]	[t ₁ = t ₀ + c]	[d = t ₀ + t ₁ ]

Optimasi Lubang intip

Teknik pengoptimalan ini bekerja secara lokal pada kode sumber untuk mengubahnya menjadi kode yang dioptimalkan. Secara lokal, yang kami maksud adalah sebagian kecil dari blok kode yang ada. Metode ini dapat diterapkan pada kode perantara maupun pada kode target. Sekumpulan pernyataan dianalisis dan diperiksa untuk kemungkinan pengoptimalan berikut:

Penghapusan instruksi yang berlebihan

Pada level kode sumber, hal berikut ini dapat dilakukan oleh pengguna:

int add_ten(int x)
   {
   int y, z;
   y = 10;
   z = x + y;
   return z;
   }

int add_ten(int x)
   {
   int y;
   y = 10;
   y = x + y;
   return y;
   }

int add_ten(int x)
   {
   int y = 10;
   return x + y;
   }

int add_ten(int x)
   {
   return x + 10;
   }

Pada level kompilasi, kompilator mencari instruksi yang bersifat redundan. Beberapa instruksi pemuatan dan penyimpanan mungkin memiliki arti yang sama bahkan jika beberapa di antaranya dihapus. Sebagai contoh:

MOV x, R0
MOV R0, R1

Kita dapat menghapus instruksi pertama dan menulis ulang kalimatnya sebagai:

MOV x, R1

Kode tidak dapat dijangkau

Kode tidak dapat dijangkau adalah bagian dari kode program yang tidak pernah diakses karena konstruksi pemrograman. Pemrogram mungkin secara tidak sengaja menulis sepotong kode yang tidak pernah bisa dijangkau.

Example:

void add_ten(int x)
{
   return x + 10;
   printf(“value of x is %d”, x);
}

Di segmen kode ini, printf pernyataan tidak akan pernah dieksekusi karena kontrol program kembali sebelum dapat dieksekusi, karenanya printf bisa dilepas.

Arus pengoptimalan kontrol

Ada beberapa contoh dalam kode di mana kontrol program melompat-lompat tanpa melakukan tugas yang signifikan. Lompatan ini bisa dihilangkan. Pertimbangkan potongan kode berikut:

...		
MOV R1, R2
GOTO L1
...
L1 :   GOTO L2
L2 :   INC R1

Dalam kode ini, label L1 dapat dihapus saat melewati kontrol ke L2. Jadi alih-alih melompat ke L1 lalu ke L2, kontrolnya bisa langsung mencapai L2, seperti gambar di bawah ini:

...		
MOV R1, R2
GOTO L2
...
L2 :   INC R1

Penyederhanaan ekspresi aljabar

Ada kalanya ekspresi aljabar dapat dibuat sederhana. Misalnya ekspresia = a + 0 bisa diganti dengan a dirinya sendiri dan ekspresi a = a + 1 dapat dengan mudah diganti dengan INC a.

Pengurangan kekuatan

Ada operasi yang menghabiskan lebih banyak waktu dan ruang. 'Kekuatan' mereka dapat dikurangi dengan menggantinya dengan operasi lain yang menghabiskan lebih sedikit waktu dan ruang, tetapi menghasilkan hasil yang sama.

Sebagai contoh, x * 2 bisa diganti dengan x << 1, yang hanya melibatkan satu shift kiri. Meskipun keluaran dari a * a dan ² sama, ² jauh lebih efisien untuk diterapkan.

Mengakses instruksi mesin

Mesin target dapat menerapkan instruksi yang lebih canggih, yang dapat memiliki kemampuan untuk melakukan operasi tertentu dengan lebih efisien. Jika kode target dapat mengakomodasi instruksi tersebut secara langsung, itu tidak hanya akan meningkatkan kualitas kode, tetapi juga menghasilkan hasil yang lebih efisien.

Generator kode

Generator kode diharapkan memiliki pemahaman tentang lingkungan runtime mesin target dan set instruksinya. Pembuat kode harus mempertimbangkan hal-hal berikut untuk menghasilkan kode:

Target language: Pembuat kode harus menyadari sifat bahasa target yang kode akan diubah. Bahasa tersebut dapat memfasilitasi beberapa instruksi khusus mesin untuk membantu kompilator menghasilkan kode dengan cara yang lebih nyaman. Mesin target dapat memiliki arsitektur prosesor CISC atau RISC.
IR Type: Representasi perantara memiliki berbagai bentuk. Ini bisa dalam struktur Abstrak Syntax Tree (AST), Reverse Polish Notation, atau kode 3-alamat.
Selection of instruction: Generator kode menggunakan Representasi Menengah sebagai input dan mengubahnya (memetakan) menjadi set instruksi mesin target. Satu representasi dapat memiliki banyak cara (instruksi) untuk mengubahnya, sehingga menjadi tanggung jawab pembuat kode untuk memilih instruksi yang sesuai dengan bijak.
Register allocation: Sebuah program memiliki sejumlah nilai yang harus dipertahankan selama eksekusi. Arsitektur mesin target mungkin tidak mengizinkan semua nilai disimpan dalam memori CPU atau register. Pembuat kode memutuskan nilai apa yang harus disimpan dalam register. Juga, ia memutuskan register yang akan digunakan untuk menyimpan nilai-nilai ini.
Ordering of instructions: Akhirnya, pembuat kode memutuskan urutan eksekusi instruksi. Ini membuat jadwal untuk instruksi untuk melaksanakannya.

Deskriptor

Pembuat kode harus melacak register (untuk ketersediaan) dan alamat (lokasi nilai) saat membuat kode. Untuk keduanya, dua deskriptor berikut digunakan:

Register descriptor: Deskriptor register digunakan untuk menginformasikan pembuat kode tentang ketersediaan register. Deskriptor register melacak nilai-nilai yang disimpan di setiap register. Kapanpun register baru diperlukan selama pembuatan kode, deskriptor ini dikonsultasikan untuk ketersediaan register.
Address descriptor: Nilai dari nama (pengenal) yang digunakan dalam program mungkin disimpan di lokasi yang berbeda saat dijalankan. Deskriptor alamat digunakan untuk melacak lokasi memori tempat nilai pengenal disimpan. Lokasi ini mungkin termasuk register CPU, heaps, stack, memori atau kombinasi dari lokasi yang disebutkan.

Pembuat kode terus memperbarui deskriptor secara real-time. Untuk pernyataan beban, LD R1, x, pembuat kode:

memperbarui Register Descriptor R1 yang memiliki nilai x dan
memperbarui Address Descriptor (x) untuk menunjukkan bahwa satu contoh x ada di R1.

Pembuatan Kode

Blok dasar terdiri dari urutan instruksi tiga alamat. Generator kode mengambil urutan instruksi ini sebagai input.

Note: Jika nilai sebuah nama ditemukan di lebih dari satu tempat (register, cache, atau memori), nilai register akan lebih disukai daripada cache dan memori utama. Nilai cache juga akan lebih disukai daripada memori utama. Memori utama hampir tidak diberi preferensi apa pun.

getReg: Generator kode menggunakan fungsi getReg untuk menentukan status register yang tersedia dan lokasi nilai nama. getReg bekerja sebagai berikut:

Jika variabel Y sudah ada di register R, ia menggunakan register itu.
Lain jika beberapa register R tersedia, ia menggunakan register itu.
Jika kedua opsi di atas tidak memungkinkan, ia memilih register yang membutuhkan jumlah minimal memuat dan menyimpan instruksi.

Untuk instruksi x = y OP z, pembuat kode dapat melakukan tindakan berikut. Mari kita asumsikan bahwa L adalah lokasi (sebaiknya register) di mana output dari y OP z akan disimpan:

Panggil fungsi getReg, untuk menentukan lokasi L.
Tentukan lokasi sekarang (register atau memori) dari y dengan berkonsultasi dengan Penjelasan Alamat y. Jikay saat ini tidak terdaftar L, lalu buat instruksi berikut untuk menyalin nilai y untuk L:

MOV y ', L

dimana y’ mewakili nilai yang disalin dari y.
Tentukan lokasi sekarang dari z menggunakan metode yang sama dengan yang digunakan pada langkah 2 untuk y dan buat instruksi berikut:

OP z ', L

dimana z’ mewakili nilai yang disalin dari z.
Sekarang L berisi nilai y OP z, yang dimaksudkan untuk ditugaskan x. Jadi, jika L adalah sebuah register, perbarui deskriptornya untuk menunjukkan bahwa ia berisi nilaix. Perbarui deskriptor darix untuk menunjukkan bahwa itu disimpan di lokasi L.
Jika y dan z tidak lagi digunakan, mereka dapat dikembalikan ke sistem.

Konstruksi kode lain seperti loop dan pernyataan bersyarat diubah menjadi bahasa assembly dengan cara assembly umum.