Mengembangkan kompiler adalah tugas yang sangat sulit. Namun, untungnya, dengan berkembangnya proyek seperti LLVM, solusi untuk masalah ini menjadi sangat disederhanakan, yang memungkinkan bahkan seorang pemrogram untuk membuat bahasa baru yang kinerjanya mendekati C. Bekerja dengan LLVM menjadi rumit karena hal ini sistem diwakili oleh sejumlah besar kode, dilengkapi dengan sedikit dokumentasi. Untuk mencoba memperbaiki kekurangan ini, penulis materi, terjemahan yang kami terbitkan hari ini, akan mendemonstrasikan contoh kode yang ditulis dalam Go dan menunjukkan bagaimana kode tersebut pertama kali diterjemahkan ke dalam bahasa Go. , dan kemudian di LLVM IR menggunakan kompiler . Kode Go SSA dan LLVM IR telah sedikit diedit untuk menghilangkan hal-hal yang tidak relevan dengan penjelasan yang diberikan di sini, agar penjelasan lebih mudah dipahami.
Contoh pertama
Fungsi pertama yang akan saya lihat di sini adalah mekanisme sederhana untuk menjumlahkan angka:
func myAdd(a, b int) int{
return a + b
}Fungsi ini sangat sederhana, dan mungkin tidak ada yang lebih sederhana. Ini diterjemahkan ke dalam kode Go SSA berikut:
func myAdd(a int, b int) int:
entry:
t0 = a + b int
return t0Dengan tampilan ini, petunjuk tipe data ditempatkan di sebelah kanan dan dalam banyak kasus dapat diabaikan.
Contoh kecil ini sudah memungkinkan Anda melihat esensi dari salah satu aspek SSA. Yaitu, ketika mengubah kode menjadi bentuk SSA, setiap ekspresi dipecah menjadi bagian-bagian paling dasar yang menyusunnya. Dalam kasus kami, perintahnya 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 - blok entri. Kami akan berbicara lebih banyak tentang blok di bawah.
Kode Go SSA dengan mudah dikonversi ke LLVM IR:
define i64 @myAdd(i64 %a, i64 %b) {
entry:
%0 = add i64 %a, %b
ret i64 %0
}
Apa yang dapat Anda perhatikan adalah meskipun struktur sintaksis berbeda digunakan di sini, struktur fungsinya pada dasarnya tidak berubah. Kode IR LLVM sedikit lebih kuat daripada kode Go SSA, mirip dengan C. Di sini, dalam deklarasi fungsi, deskripsi tipe data yang dikembalikan terlebih dahulu dijelaskan, tipe argumen ditunjukkan sebelum nama argumen. Selain itu, untuk menyederhanakan penguraian IR, nama entitas global diawali dengan simbol @, dan sebelum nama lokal ada simbolnya % (suatu fungsi juga dianggap sebagai entitas global).
Satu hal yang perlu diperhatikan tentang kode ini adalah keputusan representasi tipe Go int, yang dapat direpresentasikan sebagai nilai 32-bit atau 64-bit, bergantung pada kompiler dan target kompilasi, diterima ketika LLVM menghasilkan kode IR. Ini adalah salah satu dari banyak alasan mengapa kode IR LLVM, seperti yang dipikirkan banyak orang, tidak bergantung pada platform. Kode tersebut, yang dibuat untuk satu platform, tidak dapat diambil dan dikompilasi begitu saja untuk platform lain (kecuali Anda cocok untuk memecahkan masalah ini ).
Hal menarik lainnya yang perlu diperhatikan adalah tipenya i64 bukan bilangan bulat bertanda: ia netral dalam mewakili tanda bilangan. Tergantung pada instruksinya, ini dapat mewakili nomor yang ditandatangani dan tidak ditandatangani. Dalam hal representasi operasi penjumlahan, hal ini tidak menjadi masalah, jadi tidak ada perbedaan dalam bekerja dengan bilangan bertanda tangan atau tidak bertanda tangan. Di sini saya ingin mencatat bahwa dalam bahasa C, meluapnya variabel integer bertanda menyebabkan perilaku tidak terdefinisi, sehingga frontend Dentang menambahkan tanda ke operasi nsw (tidak ada bungkus yang ditandatangani), yang memberi tahu LLVM bahwa ia dapat berasumsi bahwa penambahan tidak pernah meluap.
Ini mungkin penting untuk beberapa pengoptimalan. Misalnya menambahkan dua nilai i16 pada platform 32-bit (dengan register 32-bit) memerlukan, setelah penambahan, operasi perluasan tanda agar tetap berada dalam jangkauan i16. Oleh karena itu, seringkali lebih efisien untuk melakukan operasi bilangan bulat berdasarkan ukuran register mesin.
Apa yang terjadi selanjutnya dengan kode IR ini bukanlah hal yang menarik bagi kami saat ini. Kode tersebut dioptimalkan (tetapi dalam kasus contoh sederhana seperti kita, tidak ada yang dioptimalkan) dan kemudian diubah menjadi kode mesin.
Contoh kedua
Contoh berikutnya yang akan kita lihat akan sedikit lebih rumit. Yaitu, kita berbicara tentang fungsi yang menjumlahkan sepotong bilangan bulat:
func sum(numbers []int) int {
n := 0
for i := 0; i < len(numbers); i++ {
n += numbers[i]
}
return n
}Kode ini diubah 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 t0Di sini Anda sudah dapat melihat lebih banyak konstruksi khas untuk merepresentasikan 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 tidak bersyarat, dan jika kita menganggap perintah ini sebagai perintah untuk mengontrol aliran, maka perintah kembali.
Faktanya, di sini Anda dapat memperhatikan fakta bahwa program tidak dibagi menjadi blok-blok menggunakan kurung kurawal (seperti dalam keluarga bahasa C). Itu dibagi berdasarkan label, mengingatkan pada bahasa rakitan, dan disajikan dalam bentuk blok dasar. Dalam SSA, blok dasar didefinisikan sebagai rangkaian kode yang berdekatan dimulai dengan label dan diakhiri dengan instruksi penyelesaian blok dasar, seperti - return и jump.
Detail menarik lainnya dari kode ini diwakili oleh instruksi phi. Petunjuknya sangat tidak biasa dan mungkin memerlukan waktu untuk dipahami. ingat itu adalah kependekan dari Static Single Assignment. Ini adalah representasi perantara dari kode yang digunakan oleh kompiler, di mana setiap variabel diberi nilai hanya satu kali. Ini bagus untuk mengekspresikan fungsi sederhana seperti fungsi kita myAddditunjukkan di atas, namun tidak cocok untuk fungsi yang lebih kompleks seperti fungsi yang dibahas di bagian ini sum. Secara khusus, variabel berubah selama eksekusi loop i и n.
SSA melewati batasan dalam menetapkan nilai variabel setelah menggunakan apa yang disebut instruksi phi (namanya diambil dari alfabet Yunani). Faktanya adalah agar representasi kode SSA dihasilkan untuk bahasa seperti C, Anda harus menggunakan beberapa trik. Hasil dari pemanggilan instruksi ini adalah nilai variabel saat ini (i или n), dan daftar blok dasar digunakan sebagai parameternya. Misalnya, pertimbangkan instruksi ini:
t0 = phi [entry: 0:int, for.body: t6] #n
Artinya sebagai berikut: jika blok dasar sebelumnya adalah blok entry (masukan), lalu t0 adalah sebuah konstanta 0, dan jika blok dasar sebelumnya adalah for.body, maka Anda perlu mengambil nilainya t6 dari blok ini. Ini semua mungkin tampak cukup misterius, namun mekanisme inilah yang membuat SSA bekerja. Dari sudut pandang manusia, ini semua membuat kode sulit untuk dipahami, namun fakta bahwa setiap nilai hanya diberikan satu kali membuat banyak optimasi menjadi lebih mudah.
Perhatikan bahwa jika Anda menulis kompiler sendiri, biasanya Anda tidak perlu berurusan dengan hal-hal semacam ini. Bahkan Dentang tidak menghasilkan semua instruksi ini phi, ia menggunakan mekanisme alloca (seperti bekerja dengan variabel lokal biasa). Kemudian, saat menjalankan optimasi LLVM, pass dipanggil , instruksi alloca dikonversi ke bentuk SSA. TinyGo, bagaimanapun, menerima masukan dari Go SSA, yang sudah dikonversi ke formulir SSA.
Inovasi lain dari fragmen kode perantara yang sedang dipertimbangkan adalah bahwa akses ke elemen irisan berdasarkan indeks direpresentasikan dalam bentuk operasi penghitungan alamat dan operasi dereferensi penunjuk yang dihasilkan. Di sini Anda dapat melihat penambahan langsung konstanta ke kode IR (misalnya - 1:int). Dalam contoh dengan fungsi myAdd ini belum digunakan. Sekarang setelah kita menghilangkan fitur-fitur tersebut, mari kita lihat apa jadinya kode ini ketika dikonversi ke 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 struktur sintaksis lainnya. Misalnya saja dalam panggilan phi nilai dan label ditukar. Namun, ada sesuatu di sini yang patut mendapat perhatian khusus.
Untuk memulainya, di sini Anda dapat melihat tanda tangan fungsi yang sangat berbeda. LLVM tidak mendukung irisan, dan sebagai hasilnya, sebagai pengoptimalan, kompiler TinyGo yang menghasilkan kode perantara ini membagi deskripsi struktur data ini menjadi beberapa bagian. Itu bisa mewakili tiga elemen irisan (ptr, len и cap) sebagai struktur (struct), tetapi merepresentasikannya sebagai tiga entitas terpisah memungkinkan beberapa pengoptimalan. Kompiler lain mungkin merepresentasikan irisan dengan cara lain, bergantung pada konvensi pemanggilan fungsi platform target.
Fitur menarik lainnya dari kode ini adalah penggunaan instruksi getelementptr (sering disingkat GEP).
Instruksi ini bekerja dengan pointer dan digunakan untuk mendapatkan pointer ke elemen irisan. Sebagai contoh, mari kita bandingkan dengan kode berikut yang ditulis dalam C:
int* sliceptr(int *ptr, int index) {
return &ptr[index];
}Atau dengan persamaan berikut ini:
int* sliceptr(int *ptr, int index) {
return ptr + index;
}
Yang terpenting di sini adalah instruksinya getelementptr tidak melakukan operasi dereferensi. Itu hanya menghitung pointer baru berdasarkan yang sudah ada. Itu bisa dianggap sebagai instruksi mul и add pada tingkat perangkat keras. Anda dapat membaca lebih lanjut tentang petunjuk GEP .
Fitur menarik lainnya dari kode perantara ini adalah penggunaan instruksi icmp. Ini adalah instruksi tujuan umum yang digunakan untuk mengimplementasikan perbandingan bilangan bulat. Hasil dari instruksi ini selalu berupa nilai bertipe i1 — nilai logis. Dalam hal ini perbandingan dilakukan dengan menggunakan kata kunci slt (ditandai kurang dari), karena kita membandingkan dua bilangan yang sebelumnya diwakili oleh tipenya int. Jika kita membandingkan dua bilangan bulat tak bertanda, maka kita akan menggunakan icmp, dan kata kunci yang digunakan dalam perbandingan adalah ult. Untuk membandingkan bilangan floating point, instruksi lain digunakan, fcmp, yang bekerja dengan cara serupa.
Hasil
Saya yakin dalam materi ini saya telah membahas fitur terpenting LLVM IR. Tentu saja, masih banyak lagi di sini. Secara khusus, representasi perantara dari kode mungkin berisi banyak anotasi yang memungkinkan lintasan pengoptimalan memperhitungkan fitur-fitur tertentu dari kode yang diketahui oleh kompiler yang tidak dapat dinyatakan dalam IR. Misalnya, ini adalah sebuah bendera inbounds Instruksi GEP, atau bendera nsw и nuw, yang dapat ditambahkan ke instruksi add. Hal yang sama berlaku untuk kata kunci private, menunjukkan kepada pengoptimal bahwa fungsi yang ditandainya tidak akan direferensikan dari luar unit kompilasi saat ini. Hal ini memungkinkan banyak optimasi antarprosedural yang menarik seperti menghilangkan argumen yang tidak digunakan.
Anda dapat membaca lebih lanjut tentang LLVM di , yang akan sering Anda rujuk saat mengembangkan kompiler berbasis LLVM Anda sendiri. Di Sini , yang membahas pengembangan kompiler untuk bahasa yang sangat sederhana. Kedua sumber informasi ini akan berguna bagi Anda saat membuat kompiler Anda sendiri.
Pembaca yang terhormat Apakah Anda menggunakan LLVM?
Sumber: www.habr.com