Geekly articles weekly

Pembuatan Kode dengan LLVM

Kutukan Non-Determinisme



Upaya pertama saya untuk menulis perikop LLVM - Saya suka segfolty ini

Baru-baru ini, saya menemukan masalah yang menarik - saya membutuhkan cara deterministik dan lintas-platform untuk menentukan runtime kode C ++. Dengan kata "deterministik" maksud saya bahwa kode yang sama akan dieksekusi untuk jumlah unit waktu yang sama. Dengan lintas platform, saya mengerti bahwa kode yang sama di bawah Windows dan di bawah Ubuntu akan berjalan untuk jumlah unit waktu yang sama.

Secara alami, mengukur waktu pada CPU tidak memenuhi kondisi ini. Kode mesin bervariasi tergantung pada arsitektur dan sistem operasi, dan kode yang sama akan membutuhkan waktu yang berbeda untuk dieksekusi. Bahkan pada mesin yang sama, faktor-faktor seperti cache misses akan memainkan peran besar - cukup untuk mengubah hasil pengukuran waktu eksekusi kode yang sama. Saya membutuhkan sesuatu yang lebih pintar ...

Motivasi


Saya mengalami masalah ini ketika saya sedang mengerjakan proyek saya, Code Character. Code Character adalah kompetisi AI online di mana peserta menulis bot untuk mengendalikan pasukan dalam strategi berbasis giliran. Saya ingin membatasi jumlah kode yang dapat dijalankan oleh satu peserta dalam satu gerakan.

Pikiran pertama saya hanyalah mengukur waktu eksekusi kode, tetapi, seperti yang dapat kita lihat, strategi ini tidak deterministik, dan peserta yang mengirim kode yang sama dua kali akan mendapatkan hasil yang sama sekali berbeda. Bahkan, kami mencoba menerapkan solusi ini, dan hasilnya sangat berubah sehingga peserta dapat menang atau kalah dengan kode yang sama. Hasilnya akan sepenuhnya acak, dan kami membuang ide untuk mengukur waktu.

Bytecode LLVM


Karena kami tidak dapat mengukur waktu, kami memutuskan untuk mengukur jumlah instruksi yang dieksekusi. Karena itu, kita perlu memasukkan kode peserta. Jika Anda tidak terbiasa dengan istilah ini, ini menambahkan beberapa kode ke aplikasi, untuk memantau beberapa parameter, misalnya, penggunaan atau runtime CPU. Secara alami, kami tidak mengharapkan para peserta untuk melakukan ini sendiri, kami harus mengotomatiskan prosesnya.

Kami ingin menghindari biaya overhead untuk alat runtime ketika bekerja di server kami, dan karena itu sesuatu seperti alat PIN tidak cocok untuk tujuan kami. Sebagai gantinya, kami memutuskan untuk secara langsung menginstruksikan kode peserta untuk menghitung jumlah instruksi yang akan dieksekusi. Alih-alih menginstruksikan binari (kode mesin), kami memutuskan untuk menggunakan Dentang untuk mengkompilasi kode dan instrumen bytecode LLVM.

Jika Anda baru mengenal LLVM, ini adalah kumpulan teknologi kompiler dan toolchain modular dan dapat digunakan kembali. Salah satu proyek utama adalah LLVM IR dan backend. Secara sederhana, Representasi Menengah telah dikembangkan ke mana kompilasi frontend mengkompilasi kode. Kode ini, LLVM IR, kemudian dikompilasi ke dalam kode mesin oleh backend LLVM. Jadi, jika Anda membuat bahasa baru, Anda dapat memutuskan untuk mengizinkan LLVM untuk mendukung pembuatan dan optimisasi kode mesin, dan menulis tampilan depan untuk mengonversi bahasa Anda ke LLVM IR.


Dentang mengkonversi kode C ++ ke LLVM IR, yang kemudian dikonversi ke kode mesin oleh backend LLVM.

Dentang adalah garis depan LLVM. Karena kita memerlukan metode lintas platform untuk mengukur kode, kita tidak dapat memasukkan kode biner. LLVM IR, bagaimanapun, adalah platform independen, karena hanya merupakan representasi kode yang sedang. Menginstruksikan kode IR dengan perpustakaan LLVM adalah solusi lintas platform yang sederhana.

Solusi


Jumlah instruksi IR LLVM sederhana jelas tidak cocok, karena kita membutuhkan jumlah instruksi yang benar-benar akan dieksekusi, dan bukan hanya jumlah instruksi dalam kode. Pada akhirnya, kami mengembangkan algoritma sederhana berdasarkan konsep blok kode dasar.

Unit dasar adalah seperangkat instruksi di mana hanya instruksi pertama yang dapat menjadi titik input, dan hanya instruksi terakhir yang dapat menjadi titik output. ( Transisi apa pun di dalam blok dasar juga dilarang - kira-kira terjemahan. ) Untuk memahami hal ini, cobalah untuk membagi kode menjadi potongan-potongan di mana instruksi cabang (transisi, loop, dan kembali) hanya dapat menjadi yang terakhir dalam set, dan input ke blok (instruksi pertama dalam fungsi, loop atau jika / else memblokir) hanya mungkin pada instruksi pertama. Hasilnya adalah satu set blok dasar - blok kode sekuensial yang hanya menjalankan secara berurutan, tanpa memutuskan instruksi mana yang akan dieksekusi selanjutnya.

Kenapa kita tidak mencobanya sekarang? Ini adalah cuplikan kode yang disediakan oleh kontributor Karakter Kode:

// Make the soldiers who aren't patrolling attack the enemy for (int i = NUM_SOLDIERS / 2; i < NUM_SOLDIERS; ++i) { auto &soldier = state.soldiers[i]; if (soldier.hp == 0) // If this soldier is dead, skip it continue; for (auto enemy_soldier : state.enemy_soldiers) { if (enemy_soldier.hp != 0) { // Ensure your prospective target has // not already been slain soldier.soldier_target = enemy_soldier.id; break; } } }

Tautan Github: https://gist.github.com/JHurricane96/8c9c3a45ec5e969de4d9fecb47ebef69#file-player_code-cpp

Dengan menggunakan fakta bahwa unit dasar hanya memiliki satu titik input (instruksi pertama), kita dapat membagi fragmen ini menjadi unit dasar berikut:

 //-------------------------------- BB 1 ---------------------------------- for (int i = NUM_SOLDIERS / 2; i < NUM_SOLDIERS; ++i) { //-------------------------------- BB 2 ---------------------------------- auto &soldier = state.soldiers[i]; if (soldier.hp == 0) //-------------------------------- BB 3 ---------------------------------- continue; //-------------------------------- BB 4 ---------------------------------- for (auto enemy_soldier : state.enemy_soldiers) { //-------------------------------- BB 5 ---------------------------------- if (enemy_soldier.hp != 0) { //-------------------------------- BB 6 ---------------------------------- soldier.soldier_target = enemy_soldier.id; break; //-------------------------------- BB 7 ---------------------------------- } } }

Github Link
Ini membantu kami memahami bagaimana blok dasar bekerja, sekarang mari kita lihat algoritma ini di LLVM IR:

 ; <label>:140: ; preds = %181, %139 %141 = load i32, i32* %19, align 4 %142 = sext i32 %141 to i64 %143 = icmp slt i64 %142, 20 br i1 %143, label %144, label %184 ; <label>:144: ; preds = %140 %145 = getelementptr inbounds %"struct.player_state::State", %"struct.player_state::State"* %2, i32 0, i32 1 %146 = load i32, i32* %19, align 4 %147 = sext i32 %146 to i64 %148 = call dereferenceable(72) %"struct.player_state::Soldier"* @_ZNSt5arrayIN12player_state7SoldierELm20EEixEm( %"struct.std::array.10"* %145, i64 %147) #3 store %"struct.player_state::Soldier"* %148, %"struct.player_state::Soldier"** %20, align 8 %149 = load %"struct.player_state::Soldier"*, %"struct.player_state::Soldier"** %20, align 8 %150 = getelementptr inbounds %"struct.player_state::Soldier", %"struct.player_state::Soldier"* %149, i32 0, i32 2 %151 = load i64, i64* %150, align 8 %152 = icmp eq i64 %151, 0 br i1 %152, label %153, label %154 ; <label>:153: ; preds = %144 br label %181

Github Link

Jika Anda perhatikan dengan teliti, Anda akan melihat bahwa fragmen kode di atas adalah tiga blok pertama dari fragmen kode C ++ yang dikompilasi dalam LLVM IR (setiap baris adalah awal dari blok dasar).

LLVM memiliki perpustakaan yang memungkinkan kita untuk menulis "melewati" - kode yang dapat mengubah LLVM IR. API LLVM memungkinkan kita untuk dengan mudah membaca dan menganalisis LLVM IR dengan melakukan iterasi melalui modul, fungsi, dan blok dasar, dan memodifikasi LLVM IR sebelum dikompilasi ke dalam kode mesin.

Sekarang kita memiliki blok dasar dan API LLVM, menjadi hal yang sederhana untuk menghitung jumlah instruksi yang akan dieksekusi menggunakan algoritma sederhana seperti itu:

  1. Kami menulis fungsi IncrementCount, yang mengambil bilangan bulat dan menambah bilangan bulat statis dengan nilai ini, setiap kali disebut. Itu harus dikaitkan dengan kode anggota.
  2. Kami melakukan iterasi pada semua blok dasar. Untuk setiap unit dasar, lakukan langkah 3 dan 4.
  3. Kami menemukan n - jumlah instruksi dalam unit dasar ini.
  4. Kami memasukkan panggilan ke fungsi IncrementCount sebelum instruksi terakhir dari unit dasar, dengan argumen n.
  5. Integer statis yang berfungsi dengan IncrementCount akan menjadi penghitung instruksi setelah kode dieksekusi. Itu dapat disimpan di suatu tempat dan kemudian diperiksa.

IR instrumen kami berfungsi seperti ini:

 ; <label>:140: ; preds = %181, %139 %141 = load i32, i32* %19, align 4 %142 = sext i32 %141 to i64 %143 = icmp slt i64 %142, 20 call void @_Z14IncrementCountm(i32 4) br i1 %143, label %144, label %184 ; <label>:144: ; preds = %140 %145 = getelementptr inbounds %"struct.player_state::State", %"struct.player_state::State"* %2, i32 0, i32 1 %146 = load i32, i32* %19, align 4 %147 = sext i32 %146 to i64 %148 = call dereferenceable(72) %"struct.player_state::Soldier"* @_ZNSt5arrayIN12player_state7SoldierELm20EEixEm( %"struct.std::array.10"* %145, i64 %147) #3 store %"struct.player_state::Soldier"* %148, %"struct.player_state::Soldier"** %20, align 8 %149 = load %"struct.player_state::Soldier"*, %"struct.player_state::Soldier"** %20, align 8 %150 = getelementptr inbounds %"struct.player_state::Soldier", %"struct.player_state::Soldier"* %149, i32 0, i32 2 %151 = load i64, i64* %150, align 8 %152 = icmp eq i64 %151, 0 call void @_Z14IncrementCountm(i32 10) br i1 %152, label %153, label %154 ; <label>:153: ; preds = %144 call void @_Z14IncrementCountm(i32 1) br label %181

Github Link

Seperti yang bisa kita lihat, panggilan IncrementCount dibuat di akhir setiap blok dasar, tepat sebelum pernyataan terakhir. Menggunakan int statis yang bekerja dengan IncrementCount, kita bisa mendapatkan jumlah instruksi di akhir setiap gerakan peserta. Metode ini bersifat deterministik dan lintas platform, sebagai kode sumber yang sama dijamin untuk menghasilkan LLVM IR yang sama jika kita menggunakan versi yang sama dari kompiler dan bendera yang sama.

Kesimpulan


Pembuatan kode bukanlah hal yang sederhana seperti yang pernah saya pikirkan. Dalam proses mengerjakan tugas yang relatif sederhana, saya berkenalan dengan cara kerja kompiler dan cara menulis pass LLVM. Jika Anda tertarik untuk menghasilkan kode dan ingin menulis bagian Anda sendiri, LLVM memiliki panduan pemula . ada juga artikel blog yang bagus yang saya gunakan untuk menulis bagian saya sendiri. Karena LLVM API tidak kompatibel mundur antara versi utama, perhatikan versi LLVM yang Anda gunakan.

Anda bisa mendapatkan kode sumber pass di sini .

Source: https://habr.com/ru/post/id417029/

More articles:


All Articles