Pengembangan kompiler adalah tugas yang sangat sulit. Tetapi, untungnya, dengan pengembangan proyek-proyek seperti LLVM, solusi untuk masalah ini sangat disederhanakan, yang bahkan memungkinkan seorang programmer tunggal untuk membuat bahasa baru yang mendekati kinerja C. C. Bekerja dengan LLVM rumit oleh fakta bahwa sistem ini diwakili oleh sejumlah besar kode, dilengkapi dengan dokumentasi kecil. Untuk mencoba memperbaiki kesalahan ini, penulis materi, yang kami terbitkan hari ini, akan mendemonstrasikan contoh kode yang ditulis dalam Go dan menunjukkan bagaimana mereka ditransmisikan terlebih dahulu ke
Go SSA dan kemudian ke LLVM IR menggunakan kompiler
TinyGO . Kode IR SSA dan LLVM Go telah sedikit diedit, sesuatu yang tidak relevan dengan penjelasan yang diberikan di sini telah dihapus darinya untuk membuat penjelasan ini lebih dimengerti.
Contoh pertama
Fungsi pertama yang akan saya uraikan di sini adalah mekanisme sederhana untuk menambahkan angka:
func myAdd(a, b int) int{ return a + b }
Fungsi ini sangat sederhana, dan, mungkin, tidak ada yang lebih mudah untuk tidak muncul. Ini diterjemahkan ke kode Go SSA berikut:
func myAdd(a int, b int) int: entry: t0 = a + b int return t0
Dengan representasi fungsi ini, petunjuk tentang tipe data ditempatkan di sebelah kanan, dalam kebanyakan kasus Anda dapat mengabaikannya.
Contoh kecil ini sudah memungkinkan Anda untuk melihat inti dari satu aspek SSA. Yaitu, ketika mengkonversi kode ke bentuk SSA, setiap ekspresi dibagi menjadi bagian-bagian paling dasar yang terdiri darinya. Dalam kasus kami, perintah
return a + b , sebenarnya, mewakili dua operasi: menambahkan dua angka dan mengembalikan hasilnya.
Selain itu, di sini Anda dapat melihat blok dasar program, dalam kode ini hanya ada satu blok - input (blok entri). Kami akan berbicara lebih banyak tentang blok di bawah ini.
Go SSA code dapat dengan mudah dikonversi ke LLVM IR:
define i64 @myAdd(i64 %a, i64 %b) { entry: %0 = add i64 %a, %b ret i64 %0 }
Anda mungkin memperhatikan bahwa walaupun konstruksi sintaksis lain digunakan di sini, struktur fungsi pada dasarnya tidak berubah. Kode IR LLVM sedikit lebih kuat daripada kode Go SSA, mirip dengan C. Di sini, dalam deklarasi fungsi, pertama kali datang deskripsi tipe data yang dikembalikan ke sana, tipe argumen ditunjukkan sebelum nama argumen. Selain itu, untuk menyederhanakan IR parsing, nama entitas global didahului oleh simbol
@ , dan sebelum nama entitas lokal dengan karakter
% (fungsi ini juga dianggap sebagai entitas global).
Salah satu fitur dari kode ini yang perlu Anda perhatikan adalah bahwa keputusan untuk mewakili tipe Go
int , yang dapat diwakili oleh nilai 32-bit atau 64-bit, tergantung pada kompiler dan tujuan kompilasi, dibuat saat membuat LLVM Kode IR. Ini adalah salah satu dari banyak alasan bahwa kode IR LLVM bukan platform independen. Kode seperti itu dibuat untuk satu platform tidak bisa begitu saja diambil dan dikompilasi untuk platform lain (kecuali jika Anda mendekati tugas ini
dengan sangat hati-hati ).
Hal menarik lainnya yang patut dicatat adalah bahwa tipe
i64 bukan bilangan bulat yang ditandatangani: itu netral dalam hal mewakili tanda angka. Bergantung pada instruksinya, ini dapat mewakili angka yang ditandatangani dan angka yang tidak ditandatangani. Dalam hal mewakili operasi penambahan, ini tidak berperan, jadi tidak ada perbedaan dalam bekerja dengan angka dengan atau tanpa tanda. Di sini, saya ingin mencatat bahwa dalam C, overflow dari variabel integer yang ditandatangani mengarah ke perilaku yang tidak terdefinisi, oleh karena itu, frontend Dentang menambahkan bendera
nsw (no wrap wraped) ke operasi, yang menunjukkan kepada LLVM bahwa ia dapat melanjutkan dari asumsi bahwa dengan Selain itu tidak pernah terjadi overflow.
Ini mungkin penting untuk beberapa optimasi. Misalnya, penambahan dua nilai
i16 pada platform 32-bit (dengan register 32-bit) mengharuskan, setelah penambahan selesai, operasi ekstensi tanda untuk tetap berada dalam kisaran
i16 . Karena itu, sering kali lebih efisien untuk melakukan operasi integer dengan mempertimbangkan ukuran mesin register.
Apa yang terjadi di masa depan dengan kode IR ini tidak terlalu menarik bagi kita sekarang. Kode dioptimalkan (tetapi dalam kasus contoh sederhana seperti kita, tidak ada yang dioptimalkan), dan kemudian dikonversi ke kode mesin.
Contoh kedua
Contoh berikut, yang akan kita periksa, akan sedikit lebih rumit. Yaitu, kita berbicara tentang fungsi yang menjumlahkan irisan integer:
func sum(numbers []int) int { n := 0 for i := 0; i < len(numbers); i++ { n += numbers[i] } return n }
Kode ini dikonversi menjadi kode Go SSA berikut:
func sum(numbers []int) int: entry: jump for.loop for.loop: t0 = phi [entry: 0:int, for.body: t6] #n int t1 = phi [entry: 0:int, for.body: t7] #i int t2 = len(numbers) int t3 = t1 < t2 bool if t3 goto for.body else for.done for.body: t4 = &numbers[t1] *int t5 = *t4 int t6 = t0 + t5 int t7 = t1 + 1:int int jump for.loop for.done: return t0
Di sini Anda sudah dapat melihat lebih banyak konstruksi khusus untuk penyajian kode dalam bentuk SSA. Mungkin fitur yang paling jelas dari kode ini adalah kenyataan bahwa tidak ada perintah kontrol aliran terstruktur. Untuk mengontrol aliran perhitungan, hanya ada lompatan bersyarat dan tanpa syarat, dan, jika kita menganggap perintah ini sebagai perintah untuk mengontrol aliran, perintah balik.
Bahkan, di sini Anda dapat memperhatikan fakta bahwa program tidak dibagi menjadi blok menggunakan kurung kurawal (seperti dalam bahasa keluarga C). Ini dibagi dengan label, yang menyerupai bahasa assembly, dan disajikan dalam bentuk blok dasar. Dalam SSA, blok dasar adalah urutan kode yang berdekatan yang dimulai dengan label dan diakhiri dengan instruksi untuk menyelesaikan blok dasar, misalnya,
return dan
jump .
Detail menarik lainnya dari kode ini adalah instruksi
phi . Instruksi ini sangat tidak biasa, mungkin perlu beberapa waktu untuk mengetahuinya. Ingat bahwa
SSA adalah kependekan dari Static Single Assignment. Ini adalah representasi perantara dari kode yang digunakan oleh kompiler, di mana setiap variabel hanya ditugaskan satu kali. Ini bagus untuk mengekspresikan fungsi sederhana seperti fungsi
myAdd kami yang ditunjukkan di atas, tetapi tidak untuk fungsi yang lebih kompleks seperti fungsi
sum dibahas di bagian ini. Secara khusus, selama eksekusi loop, variabel
i dan
n berubah.
SSA memintas batasan pada penugasan tunggal nilai variabel menggunakan apa yang disebut instruksi
phi (namanya diambil dari alfabet Yunani). Faktanya adalah agar representasi SSA dari kode dapat dibentuk untuk bahasa seperti C, Anda harus menggunakan beberapa trik. Hasil dari pemanggilan instruksi ini adalah nilai variabel saat ini (
i atau
n ), dan daftar blok dasar digunakan sebagai parameternya. Sebagai contoh, pertimbangkan instruksi ini:
t0 = phi [entry: 0:int, for.body: t6] #n
Artinya adalah sebagai berikut: jika blok dasar sebelumnya adalah blok
entry (input), maka
t0 adalah konstan
0 , dan jika blok dasar sebelumnya adalah
for.body , maka Anda perlu mengambil nilai
t6 dari blok ini. Semua ini mungkin terlihat agak misterius, tetapi berkat mekanisme ini, SSA dipastikan. Dari sudut pandang manusia, semua ini memperumit pemahaman kode, tetapi fakta bahwa setiap nilai hanya diberikan sekali sangat menyederhanakan banyak optimasi.
Perhatikan bahwa jika Anda menulis kompiler sendiri, maka Anda biasanya tidak harus berurusan dengan hal-hal seperti itu. Bahkan Dentang tidak menghasilkan semua instruksi
phi ini, ia menggunakan mekanisme
alloca (seperti bekerja dengan variabel lokal biasa). Kemudian, ketika melakukan pass optimasi LLVM, yang disebut
mem2reg , instruksi
alloca dikonversi ke bentuk SSA. TinyGo, bagaimanapun, menerima input dari Go SSA, yang, dengan mudah, telah dikonversi ke bentuk SSA.
Inovasi lain dari potongan kode perantara ini adalah bahwa akses ke elemen slice menurut indeks disajikan dalam bentuk operasi penghitungan alamat dan operasi dereferencing dari pointer yang diperoleh. Di sini Anda dapat melihat penambahan konstanta langsung ke kode IR (misalnya -
1:int ). Dalam contoh dengan fungsi
myAdd ini tidak digunakan. Sekarang kami telah menemukan fitur-fitur ini, kami akan melihat apa yang akan menjadi kode ini ketika mengubahnya menjadi bentuk LLVM IR:
define i64 @sum(i64* %ptr, i64 %len, i64 %cap) { entry: br label %for.loop for.loop: ; preds = %for.body, %entry %0 = phi i64 [ 0, %entry ], [ %5, %deref.next ] %1 = phi i64 [ 0, %entry ], [ %6, %deref.next ] %2 = icmp slt i64 %1, %len br i1 %2, label %for.body, label %for.done for.body: ; preds = %for.loop %3 = getelementptr i64, i64* %ptr, i64 %1 %4 = load i64, i64* %3 %5 = add i64 %0, %4 %6 = add i64 %1, 1 br label %for.loop for.done: ; preds = %for.loop ret i64 %0 }
Di sini, seperti sebelumnya, kita dapat melihat struktur yang sama, yang mencakup konstruksi sintaksis lainnya. Misalnya, dalam panggilan
phi , nilai dan label ditukar. Namun, ada juga sesuatu yang layak diperhatikan.
Sebagai permulaan, di sini Anda dapat melihat tanda tangan fungsi yang sama sekali berbeda. LLVM tidak mendukung irisan, sebagai hasilnya, dalam bentuk optimasi, kompiler TinyGo, yang menghasilkan kode perantara ini, membagi deskripsi struktur data ini menjadi beberapa bagian. Dia bisa mewakili tiga elemen irisan (
ptr ,
len dan
cap ) sebagai struktur (struct), tetapi menghadirkannya sebagai tiga entitas terpisah memungkinkan untuk beberapa optimasi. Kompiler lain mungkin menyajikan irisan dengan beberapa cara lain, itu tergantung pada konvensi untuk memanggil fungsi platform target.
Fitur lain yang menarik dari kode ini adalah penggunaan
getelementptr (sering disebut GEP).
Instruksi ini bekerja dengan pointer dan digunakan untuk mendapatkan pointer ke elemen slice. Sebagai contoh, mari kita bandingkan dengan kode berikut yang ditulis dalam C:
int* sliceptr(int *ptr, int index) { return &ptr[index]; }
Atau dengan yang setara dengan ini:
int* sliceptr(int *ptr, int index) { return ptr + index; }
Yang paling penting di sini adalah pernyataan
getelementptr tidak melakukan operasi dereference. Ini hanya menghitung pointer baru berdasarkan yang sudah ada. Ini dapat diartikan sebagai
mul dan
add di tingkat perangkat keras. Detail tentang instruksi GEP dapat ditemukan di
sini .
Fitur lain yang menarik dari kode perantara ini adalah penggunaan instruksi
icmp . Ini adalah instruksi tujuan umum yang digunakan untuk mengimplementasikan perbandingan integer. Hasil instruksi ini selalu berupa nilai tipe
i1 - nilai logis. Dalam hal ini, perbandingan dibuat menggunakan
slt kata kunci (masuk kurang dari), karena kami membandingkan dua angka yang sebelumnya diwakili oleh tipe
int . Jika kita membandingkan dua bilangan bulat yang tidak ditandatangani, maka kita akan menggunakan
icmp sebagai instruksi, dan kata kunci yang digunakan dalam perbandingan akan menjadi
ult . Untuk membandingkan angka floating point, instruksi lain digunakan,
fcmp , yang bekerja dengan cara yang sama.
Ringkasan
Saya percaya bahwa dalam artikel ini saya memeriksa fitur yang paling penting dari LLVM IR. Tentu saja masih banyak hal. Secara khusus, dalam representasi kode yang sedang, mungkin ada banyak anotasi yang memungkinkan mempertimbangkan fitur-fitur tertentu dari kode yang diketahui oleh kompiler selama melewati optimisasi yang tidak dapat diekspresikan dengan cara lain dalam IR. Misalnya, ini adalah flag
inbounds dari instruksi
inbounds , atau
nuw nsw dan
nuw , yang dapat ditambahkan ke pernyataan
add . Hal yang sama berlaku untuk kata kunci
private , yang menunjukkan kepada pengoptimal bahwa fungsi yang ditandai olehnya tidak akan dirujuk dari luar unit kompilasi saat ini. Ini memungkinkan Anda untuk melakukan banyak optimasi antar-prosedur yang menarik, seperti menghilangkan argumen yang tidak digunakan.
Anda dapat membaca lebih lanjut tentang LLVM dalam
dokumentasi , yang akan sering Anda rujuk ketika mengembangkan kompiler berbasis LLVM Anda sendiri. Berikut ini adalah
panduan yang membahas pengembangan kompiler untuk bahasa yang sangat sederhana. Kedua sumber informasi ini akan berguna ketika membuat kompiler Anda sendiri.
Pembaca yang budiman! Apakah Anda menggunakan LLVM?