Saya berencana untuk menulis artikel tentang bagaimana LLVM mengoptimalkan suatu fungsi, tetapi pertama-tama Anda perlu menulis bagaimana Dentang menerjemahkan C atau C ++ ke LLVM.
Pertimbangkan aspek tingkat tinggi tanpa menyelam ke kedalaman Dentang. Saya ingin memperhatikan bagaimana dentang output terkait dengan input, sementara kami tidak akan mempertimbangkan fitur non-sepele dari C ++. Kami menggunakan fungsi kecil ini, yang saya pinjam dari
kuliah luar biasa
tentang optimisasi siklik :
bool is_sorted(int *a, int n) { for (int i = 0; i < n - 1; i++) if (a[i] > a[i + 1]) return false; return true; }
Karena Dentang tidak membuat optimasi apa pun, dan karena LLVM IR pada awalnya dirancang untuk bekerja dengan C dan C ++, konversi relatif mudah. Saya akan menggunakan Dentang 6.0.1 (atau versi dekat, karena yang ini belum dirilis) di x86-64.
Baris perintah adalah sebagai berikut:
clang++ is_sorted.cpp -O0 -S -emit-llvm
Dengan kata lain: kita mengkompilasi file is_sorted.cpp sebagai C ++ dan kemudian memberi tahu rantai alat LLVM berikut ini: jangan mengoptimalkan, mengeluarkan assembler sebagai representasi tekstual dari LLVM IR. LLVM IR adalah produktif, dan tidak dapat dengan cepat ditampilkan atau diurai; format kode bit biner selalu lebih disukai jika seseorang tidak perlu melihat kode ini.
Berikut adalah LLVM IR lengkap, kami akan memeriksanya di beberapa bagian.
Mari kita mulai dari bagian atas file:
; ModuleID = 'is_sorted.cpp' source_filename = "is_sorted.cpp" target datalayout = "em:e-i64:64-f80:128-n8:16:32:64-S128" target triple = "x86_64-unknown-linux-gnu"
Seluruh teks antara titik koma dan akhir baris adalah komentar, yang berarti bahwa baris pertama tidak melakukan apa-apa, tetapi, jika Anda tertarik, dalam LLVM "modul" adalah unit kompilasi, wadah untuk kode dan data. Baris kedua seharusnya tidak mengganggu kita juga. Baris ketiga menjelaskan beberapa asumsi yang dibuat oleh kompiler, mereka tidak berperan dalam artikel ini, tetapi Anda dapat membaca lebih lanjut di
sini .
Target tiga adalah warisan gcc dan tidak lagi membutuhkan kita.
Fungsi LLVM memiliki atribut opsional:
; Function Attrs: noinline nounwind optnone uwtable
Beberapa dari mereka (seperti ini) didukung oleh front-end, yang lain ditambahkan kemudian oleh melewati optimasi. Atribut ini tidak ada hubungannya dengan arti kode, saya tidak akan membahasnya di sini, tetapi Anda dapat membaca tentang mereka di
sini jika Anda tertarik.
Dan akhirnya, fungsi kami:
define zeroext i1 @_Z9is_sortedPii(i32* %a, i32 %n)
"Zeroext" berarti bahwa nilai balik fungsi (i1, bilangan bulat tunggal) harus diperluas dengan nol di backend ke lebar yang dibutuhkan ABI. Kemudian muncul nama fungsi "mangled", kemudian daftar parameter pada dasarnya sama dengan kode C ++, kecuali bahwa i32 mendefinisikan variabel 32-bit. # 0 menghubungkan fungsi ke
grup atribut di akhir file.
Ini adalah unit dasar pertama:
entry: %retval = alloca i1, align 1 %a.addr = alloca i32*, align 8 %n.addr = alloca i32, align 4 %i = alloca i32, align 4 store i32* %a, i32** %a.addr, align 8 store i32 %n, i32* %n.addr, align 4 store i32 0, i32* %i, align 4 br label %for.cond
Setiap instruksi LLVM harus ditempatkan di dalam unit dasar: satu set instruksi yang memiliki satu input di awal dan satu output di akhir. Instruksi terakhir dari unit dasar harus berupa
instruksi terminasi : "gagal" ke unit dasar berikutnya tidak dapat diterima. Setiap fungsi harus memiliki blok input yang tidak memiliki pendahulu yang melakukan transisi ke blok ini. Properti ini dan
lainnya diperiksa ketika parsing IR; pemeriksaan ini juga dapat dipanggil beberapa kali selama proses kompilasi oleh "module verifier". Verifier berguna untuk debugging ketika pass menghasilkan IR yang tidak valid.
Empat instruksi pertama dalam blok dasar ini adalah "mengalokasikan": mengalokasikan memori tumpukan. Tiga variabel pertama dibuat secara implisit dibuat selama kompilasi, yang keempat - variabel loop. Variabel yang dialokasikan dengan cara ini hanya dapat diakses melalui instruksi memuat dan menyimpan. Tiga instruksi berikut menginisialisasi tiga slot stack, a.addr dan n.addr diinisialisasi menggunakan nilai yang diteruskan ke fungsi sebagai parameter, dan saya diinisialisasi ke nol. Nilai kembali tidak perlu diinisialisasi, kode apa pun yang tidak terdefinisi dalam C dan C ++ harus mengurus hal ini. Instruksi terakhir adalah transisi tanpa syarat ke unit dasar berikutnya (kami belum khawatir tentang hal ini, transisi yang paling tidak perlu akan dihapus oleh backend LLVM).
Anda mungkin bertanya: mengapa Dentang mengalokasikan slot stack untuk a dan n? Mengapa dia tidak menggunakan nilai-nilai ini secara langsung? Dalam fungsi ini, karena a dan n tidak berubah, strategi seperti itu akan berhasil, tetapi kasus ini akan diperhitungkan oleh pengoptimal, dan berada di luar kompetensi Calng. Jika a dan n dapat dimodifikasi, mereka harus di memori, dan tidak boleh nilai SSA, yang, menurut definisi, dapat mengambil nilai hanya pada satu titik dalam program. Sel memori berada di luar dunia SSA dan dapat dimodifikasi kapan saja. Ini mungkin tampak aneh, tetapi solusi semacam itu memungkinkan Anda untuk mengatur pekerjaan semua bagian kompiler dengan cara yang alami dan efisien.
Saya menganggap Dentang sebagai generator kode SSA yang merosot yang memenuhi semua persyaratan SSA, tetapi hanya karena pertukaran informasi antara unit dasar terjadi melalui memori. Membuat kode non-degenerasi memerlukan perhatian dan analisis, dan pengembang Clang menolak untuk melakukan ini untuk memisahkan tanggung jawab menghasilkan dan mengoptimalkan kode. Saya tidak melihat hasil pengukuran, tetapi dalam pemahaman saya, banyak operasi memori dihasilkan, dan kemudian, hampir segera, sebagian besar dari mereka dihapus oleh pengoptimal, tanpa mengarah ke overhead besar waktu kompilasi,
Pertimbangkan bagaimana loop for diterjemahkan. Secara umum, tampilannya seperti ini:
for (initializer; condition; modifier) { body }
Ini diterjemahkan menjadi sesuatu seperti ini:
initializer goto COND COND: if (condition) goto BODY else goto EXIT BODY: body modifier goto COND EXIT:
Tentu saja, terjemahan seperti itu tidak spesifik untuk Dentang, setiap kompiler C dan C ++ melakukan hal yang sama.
Dalam contoh kami, penginisialisasi loop runtuh ke dalam blok basis input. Unit dasar berikut adalah pemeriksaan kondisi loop:
for.cond: ; preds = %for.inc, %entry %0 = load i32, i32* %i, align 4 %1 = load i32, i32* %n.addr, align 4 %sub = sub nsw i32 %1, 1 %cmp = icmp slt i32 %0, %sub br i1 %cmp, label %for.body, label %for.end
Dentang juga membuat komentar yang berguna bahwa blok dasar ini dapat dicapai baik dari for.inc atau dari blok basis input. Blok ini memuat i dan n dari memori, mengurangi n (bendera nsw mencerminkan properti bahasa C yang sign overflow tidak didefinisikan; tanpa flag ini LLVM menggunakan semantik kode tambahan), membandingkan nilai yang dikurangi dengan saya menggunakan slt (ditandatangani kurang dari, tandatangani kurang dari) dan akhirnya cabang ke pangkalan untuk blok .body atau blok.
Pintu masuk ke badan loop hanya dimungkinkan dari blok for.cond:
for.body: %2 = load i32*, i32** %a.addr, align 8 %3 = load i32, i32* %i, align 4 %idxprom = sext i32 %3 to i64 %arrayidx = getelementptr inbounds i32, i32* %2, i64 %idxprom %4 = load i32, i32* %arrayidx, align 4 %5 = load i32*, i32** %a.addr, align 8 %6 = load i32, i32* %i, align 4 %add = add nsw i32 %6, 1 %idxprom1 = sext i32 %add to i64 %arrayidx2 = getelementptr inbounds i32, i32* %5, i64 %idxprom1 %7 = load i32, i32* %arrayidx2, align 4 %cmp3 = icmp sgt i32 %4, %7 br i1 %cmp3, label %if.then, label %if.end
Dua baris pertama memuat a dan i di register SSA; saya kemudian mengembang menjadi 64 bit dan dapat mengambil bagian dalam menghitung alamat. Perintah
getelementptr (atau gep disingkat) adalah perintah LLVM yang dikenal karena pretensinya, bahkan memiliki
bagian bantuannya sendiri. Tidak seperti bahasa mesin, LLVM tidak memperlakukan pointer sebagai bilangan bulat. Ini memfasilitasi analisis alias dan optimisasi memori lainnya. Kode ini memuat [i] dan [i +1], membandingkannya dan melakukan percabangan tergantung pada hasilnya.
Blok if.then menyimpan 0 ke slot stack untuk nilai kembali fungsi dan tanpa syarat melompat ke blok output fungsi:
if.then: store i1 false, i1* %retval, align 1 br label %return
Blok lain sepele:
if.end: br label %for.inc
Dan blok untuk menambahkan satu ke variabel loop juga sangat sederhana:
for.inc: %8 = load i32, i32* %i, align 4 %inc = add nsw i32 %8, 1 store i32 %inc, i32* %i, align 4 br label %for.cond
Kode ini melompat kembali untuk memeriksa kondisi loop.
Jika loop selesai secara normal, kami mengembalikan true:
for.end: store i1 true, i1* %retval, align 1 br label %return
Dan akhirnya, apa yang kita muat ke dalam slot stack dari nilai yang dikembalikan dimuat dan dikembalikan:
return: %9 = load i1, i1* %retval, align 1 ret i1 %9
Tidak ada yang istimewa di akhir fungsi. Posnya ternyata lebih panjang dari yang saya kira, di pos berikutnya kita akan mempertimbangkan untuk mengoptimalkan level IR untuk fungsi ini.
(Terima kasih kepada Xi Wang dan Alex Rosenberg untuk koreksi yang dikirim)