Desain Kompilator - Optimasi Kode

Optimasi adalah teknik transformasi program, yang mencoba memperbaiki kode dengan membuatnya mengkonsumsi lebih sedikit sumber daya (yaitu CPU, Memori) dan memberikan kecepatan tinggi.

Dalam pengoptimalan, konstruksi pemrograman umum tingkat tinggi diganti dengan kode pemrograman tingkat rendah yang sangat efisien. Proses pengoptimalan kode harus mengikuti tiga aturan yang diberikan di bawah ini:

Kode keluaran tidak boleh, dengan cara apapun, mengubah arti program.
Pengoptimalan harus meningkatkan kecepatan program dan jika memungkinkan, program harus meminta lebih sedikit sumber daya.
Pengoptimalannya sendiri harus cepat dan tidak menunda proses kompilasi secara keseluruhan.

Upaya untuk kode yang dioptimalkan dapat dilakukan di berbagai tingkat proses kompilasi.

Pada awalnya, pengguna dapat mengubah / menyusun ulang kode atau menggunakan algoritme yang lebih baik untuk menulis kode.
Setelah membuat kode perantara, compiler dapat memodifikasi kode perantara dengan kalkulasi alamat dan meningkatkan loop.
Saat menghasilkan kode mesin target, kompilator dapat menggunakan hierarki memori dan register CPU.

Pengoptimalan dapat dikategorikan secara luas menjadi dua jenis: tidak tergantung mesin dan tergantung mesin.

Pengoptimalan Tanpa Mesin

Dalam pengoptimalan ini, compiler mengambil kode perantara dan mengubah bagian dari kode yang tidak melibatkan register CPU dan / atau lokasi memori absolut. Sebagai contoh:

do
{
   item = 10;
   value = value + item; 
} while(value<100);

Kode ini melibatkan penugasan berulang dari item pengenal, yang jika kita begini:

Item = 10;
do
{
   value = value + item; 
} while(value<100);

seharusnya tidak hanya menyimpan siklus CPU, tetapi dapat digunakan pada prosesor apa pun.

Pengoptimalan yang Tergantung Mesin

Pengoptimalan yang bergantung pada mesin dilakukan setelah kode target dibuat dan ketika kode diubah sesuai dengan arsitektur mesin target. Ini melibatkan register CPU dan mungkin memiliki referensi memori absolut daripada referensi relatif. Pengoptimal yang bergantung pada mesin berupaya untuk memanfaatkan hierarki memori secara maksimal.

Blok Dasar

Kode sumber umumnya memiliki sejumlah instruksi, yang selalu dieksekusi secara berurutan dan dianggap sebagai blok dasar kode. Blok dasar ini tidak memiliki pernyataan lompat di antara mereka, yaitu, ketika instruksi pertama dijalankan, semua instruksi dalam blok dasar yang sama akan dieksekusi dalam urutan kemunculannya tanpa kehilangan kontrol aliran program.

Sebuah program dapat memiliki berbagai konstruksi sebagai blok dasar, seperti IF-THEN-ELSE, SWITCH-CASE pernyataan bersyarat dan loop seperti DO-WHILE, FOR, dan REPEAT-UNTIL, dll.

Identifikasi blok dasar

Kami dapat menggunakan algoritma berikut untuk menemukan blok dasar dalam sebuah program:

Cari pernyataan tajuk dari semua blok dasar tempat blok dasar dimulai:
- Pernyataan pertama dari sebuah program.
- Pernyataan yang menjadi target cabang mana pun (bersyarat / tidak bersyarat).
- Pernyataan yang mengikuti pernyataan cabang mana pun.
Pernyataan header dan pernyataan yang mengikutinya membentuk blok dasar.
Blok dasar tidak menyertakan pernyataan header dari blok dasar lainnya.

Blok dasar adalah konsep penting baik dari segi pembuatan kode dan pengoptimalan.

Blok dasar memainkan peran penting dalam mengidentifikasi variabel, yang digunakan lebih dari sekali dalam satu blok dasar. Jika ada variabel yang digunakan lebih dari sekali, memori register yang dialokasikan ke variabel itu tidak perlu dikosongkan kecuali blok tersebut menyelesaikan eksekusi.

Grafik Alir Kontrol

Blok-blok dasar dalam sebuah program dapat direpresentasikan dengan menggunakan grafik aliran kendali. Grafik aliran kendali menggambarkan bagaimana kendali program dilewatkan di antara blok-blok. Ini adalah alat yang berguna yang membantu dalam pengoptimalan dengan membantu menemukan loop yang tidak diinginkan dalam program.

Optimasi Loop

Sebagian besar program berjalan sebagai loop dalam sistem. Menjadi perlu untuk mengoptimalkan loop untuk menghemat siklus CPU dan memori. Loop dapat dioptimalkan dengan teknik berikut:

Invariant code: Fragmen kode yang berada dalam loop dan menghitung nilai yang sama pada setiap iterasi disebut kode loop-invariant. Kode ini dapat dipindahkan keluar dari loop dengan menyimpannya untuk dihitung hanya sekali, bukan dengan setiap iterasi.
Induction analysis : Sebuah variabel disebut variabel induksi jika nilainya diubah dalam loop oleh nilai invarian-loop.
Strength reduction: Ada ekspresi yang mengonsumsi lebih banyak siklus CPU, waktu, dan memori. Ekspresi ini harus diganti dengan ekspresi yang lebih murah tanpa mengorbankan keluaran ekspresi. Misalnya, perkalian (x * 2) mahal dalam hal siklus CPU daripada (x << 1) dan menghasilkan hasil yang sama.

Penghapusan Kode Mati

Kode mati adalah satu atau lebih dari satu pernyataan kode, yaitu:

Tidak pernah dieksekusi atau tidak dapat dijangkau,
Atau jika dijalankan, outputnya tidak pernah digunakan.

Jadi, kode mati tidak berperan dalam operasi program apa pun dan oleh karena itu dapat dihilangkan dengan mudah.

Kode mati sebagian

Ada beberapa pernyataan kode yang nilai yang dihitung hanya digunakan dalam keadaan tertentu, yaitu, terkadang nilai digunakan dan terkadang tidak. Kode semacam itu dikenal sebagai kode mati sebagian.

Grafik aliran kontrol di atas menggambarkan potongan program di mana variabel 'a' digunakan untuk menetapkan keluaran dari ekspresi 'x * y'. Mari kita asumsikan bahwa nilai yang diberikan ke 'a' tidak pernah digunakan di dalam loop. Segera setelah kontrol meninggalkan loop, 'a' diberi nilai variabel 'z', yang akan digunakan nanti dalam program. Kami menyimpulkan di sini bahwa kode penugasan 'a' tidak pernah digunakan di mana pun, oleh karena itu memenuhi syarat untuk dihilangkan.

Demikian pula, gambar di atas menggambarkan bahwa pernyataan bersyarat selalu salah, menyiratkan bahwa kode, yang ditulis dalam kasus yang benar, tidak akan pernah dijalankan, oleh karena itu dapat dihapus.

Redundansi Parsial

Ekspresi redundan dihitung lebih dari sekali dalam jalur paralel, tanpa perubahan apa pun dalam operan. Sedangkan ekspresi redundan parsial dihitung lebih dari sekali dalam sebuah jalur, tanpa perubahan apa pun dalam operan. Sebagai contoh,

[ekspresi yang berlebihan]	[ekspresi yang sebagian berlebihan]

Kode invarian-loop sebagian berlebihan dan dapat dihilangkan dengan menggunakan teknik gerakan kode.

Contoh lain dari kode yang sebagian berlebihan dapat berupa:

If (condition)
{
   a = y OP z;
}
else
{
   ...
}
c = y OP z;

Kami berasumsi bahwa nilai-nilai operan (y dan z) tidak diubah dari penugasan variabel a ke variabel c. Di sini, jika pernyataan kondisi benar, maka y OP z dihitung dua kali, sebaliknya sekali. Gerakan kode dapat digunakan untuk menghilangkan redundansi ini, seperti yang ditunjukkan di bawah ini:

If (condition)
{
   ...
   tmp = y OP z;
   a = tmp;
   ...
}
else
{
   ...
   tmp = y OP z;
}
c = tmp;

Di sini, apakah kondisinya benar atau salah; y OP z harus dihitung hanya sekali.