LLVM IR dan Go

Pada artikel ini, kita akan melihat bagaimana membangun program Go, seperti kompiler atau penganalisa statis, yang berinteraksi dengan kerangka kerja LLVM menggunakan bahasa assembly IR LLVM.

TL; DR kami menulis perpustakaan untuk berinteraksi dengan LLVM IR di Go murni, lihat tautan ke kode dan contoh proyek.

Contoh sederhana tentang LLVM IR

(Bagi Anda yang akrab dengan LLVM IR dapat melompat ke bagian berikutnya).

LLVM IR adalah representasi menengah tingkat rendah yang digunakan oleh kerangka kompilasi LLVM. Anda dapat menganggap LLVM IR sebagai assembler independen platform dengan jumlah register lokal yang tak terbatas.

Saat mendesain kompiler, ada keuntungan besar dalam mengkompilasi bahasa sumber ke dalam representasi perantara (IR, representasi perantara) alih-alih mengompilasinya menjadi arsitektur target (mis. X86).


Karena banyak teknik optimasi yang umum (misalnya, menghapus kode yang tidak digunakan, mendistribusikan konstanta), lintasan optimasi ini dapat dilakukan secara langsung di tingkat IR dan digunakan oleh semua platform target.


Dengan demikian, kompiler sering terdiri dari tiga bagian: frontend, middleland dan backend, masing-masing melakukan tugasnya sendiri, menerima input dan / atau memberikan output IR.

• Frontend: mengkompilasi bahasa sumber di IR
• Middleland: mengoptimalkan IR
• Backend: mengkompilasi IR ke dalam kode mesin

Program sampel assembler LLVM IR

Untuk mendapatkan gambaran seperti apa assembler LLVM IR, pertimbangkan program berikut.

int f(int a, int b) { return a + 2*b; } int main() { return f(10, 20); } 

Kami menggunakan Dentang dan mengkompilasi kode C di atas ke assembler LLVM IR.

 define i32 @f(i32 %a, i32 %b) { ; <label>:0 %1 = mul i32 2, %b %2 = add i32 %a, %1 ret i32 %2 } define i32 @main() { ; <label>:0 %1 = call i32 @f(i32 10, i32 20) ret i32 %1 } 

Melihat kode assembler LLVM IR di atas, kita dapat melihat beberapa fitur IR LLVM yang patut diperhatikan, yaitu:

LLVM IR diketik secara statis (mis. Integer 32-bit berpotongan dengan tipe i32).

Variabel lokal memiliki cakupan dalam fungsi (mis.,% 1 pada main berbeda dari% 1 pada @f).

Tanpa nama (register sementara) menerima pengidentifikasi lokal (misalnya,% 1,% 2), dalam urutan menaik, di masing-masing fungsi. Setiap fungsi dapat menggunakan jumlah register yang tidak terbatas (tidak terbatas pada 32 register tujuan umum). Pengidentifikasi global (mis. @F) dan pengidentifikasi lokal (mis.% A,% 1) dibedakan dengan awalan (masing-masing @ dan%).

Sebagian besar perintah melakukan apa yang Anda harapkan, jadi mul melakukan perkalian, menambahkan penambahan, dll

Komentar dimulai dengan, seperti biasa dalam bahasa majelis.

LLMV IR Assembler Structure

Isi file perakitan IR LLVM adalah modul. Modul ini berisi deklarasi tingkat tinggi, seperti variabel dan fungsi global.

Deklarasi fungsi tidak mengandung blok dasar, definisi fungsi berisi satu atau lebih blok dasar (mis., Badan fungsi).

Contoh yang lebih terperinci dari modul IR LLVM diberikan di bawah ini. termasuk definisi variabel global @foo dan definisi fungsi @f yang berisi tiga blok dasar (% entri,% blok_1 dan% blok_2).

 ;  ,  32-  21 @foo = global i32 21 ; f  42,   cond ,  0    define i32 @f(i1 %cond) { ;       ,     ;      entry: ;     br    block_1,  %cond ; ,   block_2   . br i1 %cond, label %block_1, label %block_2 ;     ,    ,     block_1: %tmp = load i32, i32* @foo %result = mul i32 %tmp, 2 ret i32 %result ;     ,     ,     block_2: ret i32 0 } 

Unit dasar

Unit dasar adalah urutan perintah yang bukan perintah transisi (perintah terminasi). Gagasan kunci dari unit dasar adalah bahwa jika satu perintah dari unit dasar dijalankan, maka semua perintah lain dari unit dasar dijalankan. Ini menyederhanakan analisis aliran eksekusi.

Tim

Perintah yang bukan perintah lompat biasanya melakukan perhitungan atau akses memori (misalnya, tambahkan, muat), tetapi tidak mengubah aliran kontrol program.

Tim pemutusan hubungan kerja

Perintah terminasi terletak di akhir setiap unit dasar, dan menentukan di mana transisi akan dilakukan pada akhir unit dasar. Sebagai contoh, perintah ret terminating mengembalikan aliran kontrol dari fungsi pemanggilan, dan br melakukan transisi, kondisional atau tanpa syarat.

Formulir SSA

Satu properti yang sangat penting dari LLVM IR adalah bahwa ia ditulis dalam bentuk SSA (Static Single Assignment), yang pada dasarnya berarti bahwa setiap register hanya ditugaskan satu kali. Properti ini menyederhanakan analisis statis aliran data.

Untuk memproses variabel yang ditetapkan lebih dari satu kali dalam kode sumber asli, perintah phi digunakan dalam LLVM IR. Perintah phi pada dasarnya mengembalikan nilai tunggal dari satu set nilai input, tergantung pada jalur eksekusi mana perintah ini tercapai. Dengan demikian, setiap nilai input dikaitkan dengan blok input sebelumnya.

Sebagai contoh, pertimbangkan fungsi IR LLVM berikut:

 define i32 @f(i32 %a) { ; <label>:0 switch i32 %a, label %default [ i32 42, label %case1 ] case1: %x.1 = mul i32 %a, 2 br label %ret default: %x.2 = mul i32 %a, 3 br label %ret ret: %x.0 = phi i32 [ %x.2, %default ], [ %x.1, %case1 ] ret i32 %x.0 } 

Perintah phi (juga kadang-kadang disebut simpul phi) dalam contoh di atas mensimulasikan berbagai penugasan menggunakan set nilai input yang mungkin, satu untuk setiap jalur yang mungkin dalam utas eksekusi, yang mengarah ke penugasan variabel. Misalnya, salah satu jalur terkait dalam aliran data adalah sebagai berikut:



Secara umum, ketika mengembangkan kompiler yang mengubah kode sumber ke LLVM IR, semua variabel kode sumber lokal dapat dikonversi ke bentuk SSA, dengan pengecualian variabel yang alamatnya diambil.

Untuk menyederhanakan implementasi frontend LLVM, direkomendasikan untuk memodelkan variabel lokal dalam bahasa sumber sebagai variabel yang dialokasikan dalam memori (menggunakan alokasi), mensimulasikan tugas ke variabel lokal sebagai menulis ke memori, dan menggunakan variabel lokal sebagai dibaca dari memori. Alasannya adalah bahwa itu bisa menjadi tugas nontrivial untuk secara langsung menerjemahkan bahasa sumber ke LLVM IR dalam bentuk SSA. Selama akses memori mengikuti pola-pola tertentu, kita dapat mengandalkan pass optimasi mem2reg sebagai bagian dari LLVM untuk mengubah variabel lokal yang dialokasikan dalam memori menjadi register dalam bentuk SSA (menggunakan node phi jika diperlukan).

Perpustakaan LLVM IR on Go murni

Ada dua perpustakaan utama untuk bekerja dengan LLVM IR in Go:

https://godoc.org/llvm.org/llvm/bindings/go/llvm : binding LLVM resmi untuk bahasa Go.
github.com/llir/llvm : Pustaka Go yang bersih untuk berinteraksi dengan LLVM IR.

Ikatan LLVM resmi untuk bahasa Go menggunakan Cgo untuk menyediakan akses ke API yang kaya dan kuat dari kerangka kerja penyusun LLVM, sementara proyek llir / llvm sepenuhnya ditulis dalam Go dan menggunakan LLVM IR untuk berinteraksi dengan kerangka kerja LLVM.

Artikel ini berfokus pada llir / llvm, tetapi dapat digeneralisasi untuk bekerja dengan perpustakaan lain.

Mengapa menulis perpustakaan baru?

Motivasi utama untuk mengembangkan perpustakaan Go yang bersih untuk berinteraksi dengan LLVM IR adalah membuat kompiler penulisan dan alat analisis statis, yang didasarkan pada kerangka kompilasi LLVM IR, tugas yang lebih menyenangkan. Itu juga dipengaruhi oleh fakta bahwa waktu kompilasi suatu proyek berdasarkan ikatan LLVM resmi dengan Go dapat menjadi signifikan (terima kasih kepada @aykevl, penulis TinyGo, sekarang dimungkinkan untuk mempercepat kompilasi karena tautan dinamis, berbeda dengan versi standar LLVM 4).


Motivasi besar lainnya adalah mencoba mengembangkan API Go dari awal. Perbedaan utama antara API yang mengikat LLVM untuk Go dan llir / llvm adalah bagaimana nilai-nilai LLVM dimodelkan. Dalam pengikat LLVM untuk Go, nilai-nilai LLVM dimodelkan sebagai tipe struktural beton, yang, pada dasarnya, berisi semua metode yang mungkin untuk semua kemungkinan nilai LLVM. Pengalaman pribadi saya menggunakan API ini menunjukkan bahwa sulit untuk mengetahui bagian metode yang diizinkan untuk memanggil nilai tertentu. Misalnya, untuk mendapatkan opcode instruksi, Anda memanggil metode InstructionOpcode, yang intuitif. Namun, jika Anda memanggil metode Opcode, yang dirancang untuk mendapatkan opcode dari ekspresi konstan, Anda akan mendapatkan kesalahan runtime: “cast () argumen tipe tidak kompatibel!” (Konversi argumen ke tipe yang tidak kompatibel).

Perpustakaan llir / llvm dirancang untuk memeriksa jenis pada waktu kompilasi dan memastikan bahwa mereka digunakan dengan benar dengan sistem tipe Go. Nilai LLVM di llir / llvm dimodelkan sebagai tipe antarmuka. Pendekatan ini hanya menyediakan sekumpulan metode minimal, dibagikan oleh semua nilai, dan jika Anda ingin mengakses metode atau bidang tertentu, gunakan pengalihan tipe (seperti yang ditunjukkan dalam contoh di bawah).

Contoh penggunaan

Sekarang mari kita lihat beberapa contoh kegunaan khusus. mari kita memiliki perpustakaan, tetapi apa yang harus kita lakukan dengan LLVM IR?

Pertama, kita mungkin ingin mem-parsing LLVM IR yang dihasilkan oleh alat lain, seperti Dentang dan pengoptimal LLVM opt (lihat contoh input di bawah).

Kedua, kami mungkin ingin memproses LLVM IR dan melakukan analisis kami sendiri tentang itu, atau membuat melewati optimasi kami sendiri, atau menerapkan juru bahasa, atau kompiler JIT (lihat contoh analisis di bawah).

Ketiga, kami mungkin ingin menghasilkan LLVM IR, yang akan menjadi input untuk instrumen lain. Pendekatan ini dapat dipilih jika kita mengembangkan antarmuka untuk bahasa pemrograman baru (lihat contoh kode keluaran di bawah).

Contoh Kode Masukan - LLVM IR Parsing

 //       LLVM IR,    //     package main import ( "fmt" "github.com/llir/llvm/asm" ) func main() { //    LLVM IR. m, err := asm.ParseFile("foo.ll") if err != nil { panic(err) } // ,    LLVM IR. // Print LLVM IR module. fmt.Println(m) } 

Contoh Analisis - Memproses LLVM IR

 //      LLVM IR     //  Graphviz DOT package main import ( "bytes" "fmt" "io/ioutil" "github.com/llir/llvm/asm" "github.com/llir/llvm/ir" ) func main() { //    LLVM IR. m, err := asm.ParseFile("foo.ll") if err != nil { panic(err) } //    . callgraph := genCallgraph(m) //      Graphviz DOT. if err := ioutil.WriteFile("callgraph.dot", callgraph, 0644); err != nil { panic(err) } } // genCallgraph      Graphviz DOT    LLVM IR func genCallgraph(m *ir.Module) []byte { buf := &bytes.Buffer{} buf.WriteString("digraph {\n") //      for _, f := range m.Funcs { //   caller := f.Ident() fmt.Fprintf(buf, "\t%q\n", caller) //       for _, block := range f.Blocks { //   ,       . for _, inst := range block.Insts { //  .   call. switch inst := inst.(type) { case *ir.InstCall: callee := inst.Callee.Ident() //        . fmt.Fprintf(buf, "\t%q -> %q\n", caller, callee) } } //     switch term := block.Term.(type) { case *ir.TermRet: //  - _ = term } } } buf.WriteString("}") return buf.Bytes() } 

Contoh Kode Keluaran - LLVM IR Generation

 //     LLVM IR,    C, //    . // // int abs(int x); // // int seed = 0; // // // ref: https://en.wikipedia.org/wiki/Linear_congruential_generator // // a = 0x15A4E35 // // c = 1 // int rand(void) { // seed = seed*0x15A4E35 + 1; // return abs(seed); // } package main import ( "fmt" "github.com/llir/llvm/ir" "github.com/llir/llvm/ir/constant" "github.com/llir/llvm/ir/types" ) func main() { //      i32 := types.I32 zero := constant.NewInt(i32, 0) a := constant.NewInt(i32, 0x15A4E35) //  PRNG. c := constant.NewInt(i32, 1) //  PRNG. //    LLVM IR. m := ir.NewModule() //         . // // int abs(int x); abs := m.NewFunc("abs", i32, ir.NewParam("x", i32)) //         . // // int seed = 0; seed := m.NewGlobalDef("seed", zero) //        . // // int rand(void) { ... } rand := m.NewFunc("rand", i32) //           `rand`. entry := rand.NewBlock("") //         . tmp1 := entry.NewLoad(seed) tmp2 := entry.NewMul(tmp1, a) tmp3 := entry.NewAdd(tmp2, c) entry.NewStore(tmp3, seed) tmp4 := entry.NewCall(abs, tmp3) entry.NewRet(tmp4) //   LLVM IR  . fmt.Println(m) } 

Kesimpulan

Pengembangan dan implementasi llir / llvm dilakukan dan dipimpin oleh komunitas kontributor yang tidak hanya menulis kode, tetapi juga memimpin diskusi, memasangkan sesi pemrograman, men-debug, membuat profil, dan menunjukkan rasa ingin tahu dalam proses pembelajaran.

Salah satu bagian yang paling sulit dari proyek llir / llvm adalah pembangunan tata bahasa EBNF untuk LLVM IR, mencakup seluruh bahasa IR LLVM hingga versi LLVM 7.0. Kesulitan di sini bukanlah dalam proses itu sendiri, tetapi pada kenyataan bahwa tidak ada tata bahasa yang diterbitkan secara resmi yang mencakup seluruh bahasa. Beberapa komunitas open source telah mencoba mendefinisikan tata bahasa formal untuk assembler LLVM, tetapi mereka mencakup, sejauh yang kami tahu, hanya himpunan bagian dari bahasa.

Grammar LLVM IR membuka jalan bagi proyek yang menarik. Misalnya, generasi assembler IR LLVM yang valid secara sintaksis dapat digunakan untuk berbagai alat dan pustaka menggunakan LLVM IR, pendekatan yang sama digunakan di GoSmith. Ini dapat digunakan untuk validasi silang dari proyek LLVM yang dilaksanakan dalam bahasa lain, serta memeriksa kerentanan dan bug implementasi.

Masa depan luar biasa, selamat retas!

Referensi

1. Bab yang ditulis dengan sangat baik tentang LLVM, ditulis oleh Chris Lattner, penulis proyek LLVM awal, dalam buku "Arsitektur Aplikasi Sumber Terbuka".

2. Implementasikan bahasa dengan tutorial LLVM - sering juga disebut Panduan Bahasa Kaleidoskop - menjelaskan secara rinci bagaimana mengimplementasikan bahasa pemrograman sederhana yang dikompilasi dalam LLVM IR. Artikel ini menjelaskan semua tahapan utama penulisan frontend, termasuk penganalisis leksikal, pengurai, dan pembuatan kode.

3. Bagi mereka yang tertarik untuk menulis kompiler dari bahasa input ke LLVM IR, buku " Pemetaan Konstruksi Tingkat Tinggi ke LLVM IR " direkomendasikan.

Satu set slide yang baik adalah LLVM, dalam Great Detail , yang menjelaskan konsep-konsep penting dari LLVM IR, memberikan pengantar untuk LLVM C ++ API, dan menjelaskan beberapa bagian optimasi LLVM yang sangat berguna.

Binding Go resmi untuk LLVM cocok untuk banyak proyek, mereka mewakili LLVM C API, kuat dan stabil.

Tambahan yang baik untuk posting adalah Pengantar LLVM in Go.