Mengapa LLVM dapat memanggil fungsi yang tidak pernah dipanggil?

Aku tidak peduli apa yang dikatakan nagamu, itu bohong. Naga berbohong. Anda tidak tahu apa yang menunggu Anda di sisi lain.

Michael Swanwick, Putri Naga Besi

Artikel ini didasarkan pada posting di blog Krister Walfridsson, "Mengapa perilaku yang tidak terdefinisi dapat memanggil fungsi yang tidak pernah disebut?" .

Artikel menarik kesimpulan sederhana: perilaku tidak terdefinisi dalam kompiler dapat melakukan apa saja, bahkan sesuatu yang benar-benar tak terduga. Pada artikel ini, saya memeriksa mekanisme internal dari pengoptimalan ini berfungsi.

Untuk rekap singkat pos Waldfridsson, dalam kode sumber di bawah ini, fungsi EraseAll tidak boleh dipanggil dari main, dan tidak benar-benar dipanggil saat dikompilasi dengan -O0, tetapi tiba-tiba dipanggil dengan optimasi -O1 dan lebih tinggi.

#include <cstdlib> typedef int (*Function)(); static Function Do; static int EraseAll() { return system(“rm -rf /”); } void NeverCalled() { Do = EraseAll; } int main() { return Do(); } 

Bagaimana cara kompiler mengoptimalkannya? Pada awalnya, Do, pointer ke suatu fungsi batal, karena, sesuai dengan standar C, semua variabel global memiliki nilai nol ketika sebuah program dimulai.



Program akan mencoba melakukan dereferensi pada penunjuk Do dan memanggil fungsi yang ditugaskan. Tetapi jika kita mencoba untuk mengubah pointer nol, standar mengatakan bahwa itu adalah perilaku undefined UB. Biasanya, jika kita mengkompilasi tanpa optimisasi, dengan opsi -O0, kita akan mendapatkan Kesalahan Segmentasi (di Linux). Tetapi Standar mengatakan, bahwa dalam hal UB, sebuah program dapat melakukan apa saja.



Kompiler menggunakan fitur standar ini untuk menghapus operasi yang tidak perlu. Jika kompilator melihat bahwa Do ditugaskan di mana saja dalam program, ia dapat menetapkan nilai ini dalam waktu inisialisasi, dan tidak menetapkannya di runtime. Pada kenyataannya, ada dua kemungkinan:

1. jika sebuah pointer ditereferensi setelah ditetapkan, kita menang, karena kompiler dapat menghapus tugas yang tidak perlu.

2. jika pointer direferensikan sebelum ditetapkan, standar mengatakan bahwa itu adalah UB, dan perilaku dapat berupa apa saja, termasuk memanggil fungsi arbitrer. Artinya, memanggil fungsi PrintHello () tidak bertentangan dengan standar.

Artinya, dalam hal apa pun, kami dapat menetapkan beberapa nilai tidak-nol ke pointer yang tidak diinisialisasi dan mendapatkan perilaku, sesuai dengan standar.



Apa kondisi yang memungkinkan pengoptimalan ini? Pada awalnya, sebuah program harus berisi sebuah penunjuk global tanpa nilai awal atau dengan nilai nol (itu sama). Selanjutnya, program harus berisi tugas nilai untuk pointer ini, di mana saja, tidak peduli, sebelum pointer dereferencing atau sesudahnya. Dalam contoh di atas, tugas belum terjadi sama sekali, tetapi kompiler melihat bahwa tugas itu ada.

Jika kondisi ini terpenuhi, kompiler dapat menghapus tugas dan mengubahnya menjadi nilai awal pointer.

Dalam kode yang diberikan variabel Do adalah penunjuk ke fungsi, dan memiliki nilai awal nol. Ketika kami mencoba memanggil fungsi pada penunjuk nol, perilaku program tidak terdefinisi (perilaku tidak terdefinisi, UB) dan kompiler berhak untuk mengoptimalkan UB seperti yang diinginkan. Dalam hal ini, kompiler segera menjalankan tugas Do = EraseAll.

Mengapa ini terjadi? Dalam sisa teks, LLVM dan Dentang versi 5.0.0 digunakan sebagai kompiler. Contoh kode bisa dijalankan untuk Anda berlatih sendiri.

Untuk memulainya, mari kita lihat kode IR saat mengoptimalkan dengan -O0 dan -O1. Mari kita ubah sedikit kode sumber agar tidak terlalu dramatis:

 #include <cstdlib> typedef int (*Function)(); static Function Do; static int PrintHello() { return printf("hello world\n"); } void NeverCalled() { Do = PrintHello; } int main() { return Do(); } 

Dan kami mengkompilasi kode IR dengan -O0 (informasi debugging dihilangkan untuk kejelasan):

 ; ModuleID = 'test.c' source_filename = "test.c" target datalayout = "em:e-i64:64-f80:128-n8:16:32:64-S128" target triple = "x86_64-unknown-linux-gnu" @Do = internal global i32 (...)* null, align 8 @.str = private unnamed_addr constant [13 x i8] c"hello world\0A\00", align 1 ; Function Attrs: noinline nounwind optnone uwtable define void @NeverCalled() #0 { entry: store i32 (...)* bitcast (i32 ()* @PrintHello to i32 (...)*), i32 (...)** @Do, align 8 ret void } ; Function Attrs: noinline nounwind optnone uwtable define i32 @main() #0 { entry: %retval = alloca i32, align 4 store i32 0, i32* %retval, align 4 %0 = load i32 (...)*, i32 (...)** @Do, align 8 %call = call i32 (...) %0() ret i32 %call } ; Function Attrs: noinline nounwind optnone uwtable define internal i32 @PrintHello() #0 { entry: %call = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([13 x i8], [13 x i8]* @.str, i32 0, i32 0)) ret i32 %call } declare i32 @printf(i8*, ...) #1 And with -O1: ; ModuleID = 'test.ll' source_filename = "test.c" target datalayout = "em:e-i64:64-f80:128-n8:16:32:64-S128" target triple = "x86_64-unknown-linux-gnu" @.str = private unnamed_addr constant [13 x i8] c"hello world\0A\00", align 1 ; Function Attrs: noinline nounwind optnone uwtable define void @NeverCalled() local_unnamed_addr #0 { entry: ret void } ; Function Attrs: noinline nounwind optnone uwtable define i32 @main() local_unnamed_addr #0 { entry: %retval = alloca i32, align 4 store i32 0, i32* %retval, align 4 %call = call i32 (...) bitcast (i32 ()* @PrintHello to i32 (...)*)() ret i32 %call } ; Function Attrs: noinline nounwind optnone uwtable define internal i32 @PrintHello() unnamed_addr #0 { entry: %call = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([13 x i8], [13 x i8]* @.str, i32 0, i32 0)) ret i32 %call } declare i32 @printf(i8*, ...) local_unnamed_addr #1 

Jika Anda mengkompilasi executable, Anda akan mengonfirmasi bahwa dalam kasus pertama, kesalahan segmentasi terjadi, dan dalam kasus kedua, "halo dunia" ditampilkan. Dengan opsi pengoptimalan lainnya, hasilnya sama dengan -O1.

Sekarang temukan bagian dari kode kompiler yang melakukan optimasi ini. Arsitektur LLVM frontend tidak berurusan dengan optimisasi itu sendiri, mis. Cfe (Clang Frontend) selalu menghasilkan kode tanpa optimisasi, yang kita lihat dalam versi untuk -O0, dan semua optimasi dilakukan oleh utilitas opt:



Dengan -O1, 186 lintasan optimasi dilakukan.

Mematikan pass satu demi satu, kami menemukan apa yang kami cari: globalopt pass. Kami hanya dapat meninggalkan pass optimasi ini, dan memastikan bahwa itu, dan tidak ada orang lain, menghasilkan kode yang kami butuhkan. Sumbernya ada di file /lib/Transforms/IPO/GlobalOpt.cpp. Anda dapat melihat kode sumber di repositori LLVM. Untuk singkatnya, saya hanya menyediakan fungsi yang penting untuk memahami cara kerjanya.



Gambar ini mewakili struktur representasi IR. Kode dalam representasi IR LLVM memiliki level hierarkis: modul mewakili level hierarki tertinggi, dan mencakup semua fungsi dan objek global, seperti variabel global. Suatu fungsi adalah level paling penting dari representasi IR dan sebagian besar pass berfungsi pada level ini. Blok dasar adalah salah satu konsep terpenting dari teori kompiler. Blok dasar terdiri dari instruksi, yang tidak dapat membuat lompatan dari tengah blok dasar atau di dalam blok dasar. Semua transisi antara blok dasar hanya dimungkinkan dari ujung blok dasar dan ke awal blok dasar, dan setiap lompatan dari atau ke tengah blok dasar tidak pernah mungkin. Level instruksi mewakili instruksi kode IR LLVM. Ini bukan instruksi prosesor, ini adalah instruksi dari beberapa mesin virtual yang sangat umum dengan jumlah register yang tidak terbatas.



Gambar ini menunjukkan hierarki lintasan LLVM. Di lintasan kiri bekerja pada kode LLVM IR ditampilkan, di lintasan kanan bekerja dengan instruksi target ditampilkan.

Awalnya, ia mengimplementasikan metode runOnModule, yaitu ketika bekerja, ia melihat dan mengoptimalkan seluruh modul (yang, tentu saja, masuk akal dalam kasus ini). Fungsi yang melakukan optimasi adalah mengoptimalkanGlobalsInModule:

 static bool optimizeGlobalsInModule( Module &M, const DataLayout &DL, TargetLibraryInfo *TLI, function_ref<dominatortree> LookupDomTree) { SmallSet<const comdat="Comdat" 8="8"> NotDiscardableComdats; bool Changed = false; bool LocalChange = true; while (LocalChange) { LocalChange = false; NotDiscardableComdats.clear(); for (const GlobalVariable &GV : M.globals()) if (const Comdat *C = GV.getComdat()) if (!GV.isDiscardableIfUnused() || !GV.use_empty()) NotDiscardableComdats.insert(C); for (Function &F : M) if (const Comdat *C = F.getComdat()) if (!F.isDefTriviallyDead()) NotDiscardableComdats.insert(C); for (GlobalAlias &GA : M.aliases()) if (const Comdat *C = GA.getComdat()) if (!GA.isDiscardableIfUnused() || !GA.use_empty()) NotDiscardableComdats.insert(C); // Delete functions that are trivially dead, ccc -> fastcc LocalChange |= OptimizeFunctions(M, TLI, LookupDomTree, NotDiscardableComdats); // Optimize global_ctors list. LocalChange |= optimizeGlobalCtorsList(M, [&](Function *F) { return EvaluateStaticConstructor(F, DL, TLI); }); // Optimize non-address-taken globals. LocalChange |= OptimizeGlobalVars(M, TLI, LookupDomTree, NotDiscardableComdats); // Resolve aliases, when possible. LocalChange |= OptimizeGlobalAliases(M, NotDiscardableComdats); // Try to remove trivial global destructors if they are not removed // already. Function *CXAAtExitFn = FindCXAAtExit(M, TLI); if (CXAAtExitFn) LocalChange |= OptimizeEmptyGlobalCXXDtors(CXAAtExitFn); Changed |= LocalChange; } // TODO: Move all global ctors functions to the end of the module for code // layout. return Changed; } 

Mari kita coba gambarkan dengan kata-kata apa fungsi ini. Untuk setiap variabel global dalam modul, ia meminta objek Comdat.

Apa itu objek Comdat?

Bagian Comdat adalah bagian dalam file objek, di mana objek ditempatkan, yang dapat diduplikasi dalam file objek lainnya. Setiap objek memiliki informasi untuk linker, menunjukkan apa yang harus dilakukan ketika duplikat terdeteksi. Opsinya bisa: Apa saja - lakukan apa saja, ExactMatch - duplikat harus benar-benar cocok, jika tidak terjadi kesalahan, Terbesar - ambil objek dengan nilai terbesar, NoDublicates - tidak boleh ada duplikat, SameSize - duplikat harus memiliki ukuran yang sama, jika tidak terjadi kesalahan.

Dalam LLVM, data Comdat diwakili oleh enumerasi:

 enum SelectionKind { Any, ///< The linker may choose any COMDAT. ExactMatch, ///< The data referenced by the COMDAT must be the same. Largest, ///< The linker will choose the largest COMDAT. NoDuplicates, ///< No other Module may specify this COMDAT. SameSize, ///< The data referenced by the COMDAT must be the same size. }; 

dan kelas Comdat sebenarnya mewakili pasangan (Nama, SelectionKind). (Faktanya, semuanya lebih rumit.) Semua variabel yang karena alasan tertentu tidak dapat dihapus ditempatkan di set NotDiscardableComdats. Dengan fungsi dan alias global, kami melakukan hal yang sama - sesuatu yang tidak dapat dihapus ditempatkan di NotDiscardableComdats. Kemudian, fungsi optimisasi terpisah untuk konstruktor global, fungsi global, variabel global, alias global, dan destruktor global disebut. Optimasi berlanjut dalam loop sampai tidak ada optimasi yang dilakukan. Pada setiap iterasi loop, himpunan NotDiscardableComdats diatur ke nol.

Mari kita lihat objek apa yang terdaftar dari sumber pengujian kami.

Variabel global:

 1. @Do = internal global i32 (...)* null, align 8 2. @.str = private unnamed_addr constant [13 x i8] c"hello world\0A\00", align 1 

(sedikit ke depan, saya dapat mengatakan bahwa variabel pertama akan dihapus oleh pengoptimal pada iterasi pertama).
Fungsi:

 define void @NeverCalled() define i32 @main() define internal i32 @PrintHello() declare i32 @printf(i8*, ...) 

Perhatikan bahwa printf hanya dideklarasikan, tetapi tidak didefinisikan.

Tidak ada alias global.

Mari kita lihat contoh pass optimasi ini dan perhatikan bagaimana hasil ini ternyata. Tentu saja, untuk menganalisis semua opsi pengoptimalan bahkan dalam satu langkah adalah tugas yang sangat besar, karena melibatkan banyak kasus khusus pengoptimalan. Kami akan berkonsentrasi pada contoh kami, dengan mempertimbangkan fungsi-fungsi dan struktur data yang penting untuk memahami pekerjaan pass optimasi ini.

Awalnya, pengoptimal melakukan berbagai pemeriksaan yang tidak menarik dalam kasus ini, dan memanggil fungsi processInternalGlobal, yang mencoba mengoptimalkan variabel global. Fungsi ini juga cukup kompleks dan melakukan banyak hal berbeda, tetapi kami tertarik pada satu hal:

 if (GS.StoredType == GlobalStatus::StoredOnce && GS.StoredOnceValue) { ... // We are trying to optimize global variables, about which it is known that they are assigned a value only once, except the initializing value. if (optimizeOnceStoredGlobal(GV, GS.StoredOnceValue, GS.Ordering, DL, TLI)) return true; ... } 

Informasi bahwa variabel global diberi nilai satu dan hanya sekali diekstraksi dari struktur GS (GlobalStatus). Struktur ini diisi dalam fungsi panggilan:

 static bool processGlobal(GlobalValue &GV, TargetLibraryInfo *TLI, function_ref<dominatortree> LookupDomTree) { if (GV.getName().startswith("llvm.")) return false; GlobalStatus GS; if (GlobalStatus::analyzeGlobal(&GV, GS)) return false; ... 

Di sini kita melihat satu fakta yang lebih menarik: objek yang namanya dimulai dengan "llvm." tidak tunduk pada optimasi (karena mereka adalah panggilan sistem untuk runtime llvm). Dan, untuk berjaga-jaga, nama-nama variabel dalam LLVM IR dapat berisi titik (dan bahkan terdiri dari satu titik dengan awalan @ atau%). Function analysisGlobal adalah panggilan ke API LLVM dan kami tidak akan mempertimbangkan pekerjaan internalnya. Struktur GlobalStatus harus dilihat secara terperinci karena mengandung informasi yang sangat penting untuk lintasan optimasi.

 /// As we analyze each global, keep track of some information about it. If we /// find out that the address of the global is taken, none of this info will be /// accurate. struct GlobalStatus { /// True if the global's address is used in a comparison. bool IsCompared = false; /// True if the global is ever loaded. If the global isn't ever loaded it /// can be deleted. bool IsLoaded = false; /// Keep track of what stores to the global look like. enum StoredType { /// There is no store to this global. It can thus be marked constant. NotStored, /// This global is stored to, but the only thing stored is the constant it /// was initialized with. This is only tracked for scalar globals. InitializerStored, /// This global is stored to, but only its initializer and one other value /// is ever stored to it. If this global isStoredOnce, we track the value /// stored to it in StoredOnceValue below. This is only tracked for scalar /// globals. StoredOnce, /// This global is stored to by multiple values or something else that we /// cannot track. Stored } StoredType = NotStored; /// If only one value (besides the initializer constant) is ever stored to /// this global, keep track of what value it is. Value *StoredOnceValue = nullptr; ... }; 

Perlu dijelaskan mengapa "Jika kami mengetahui bahwa alamat global diambil, tidak ada info ini yang akurat." Bahkan, jika kita mengambil alamat variabel global, dan kemudian menulis sesuatu di alamat ini, bukan dengan nama, maka akan sangat sulit untuk melacak ini, dan lebih baik meninggalkan variabel seperti apa adanya, tanpa mencoba mengoptimalkan .

Jadi, kita masuk ke fungsi optimOnceStoredGlobal, di mana variabel (GV) dan nilai tersimpan (StoredOnceVal) dilewatkan. Inilah mereka:

 @Do = internal unnamed_addr global i32 (...)* null, align 8 // the variable i32 (...)* bitcast (i32 ()* @PrintHello to i32 (...)*) // the value 

Selanjutnya, untuk nilainya, bitcast tidak signifikan dihapus, dan untuk variabel kondisi berikut diperiksa:

 if (GV->getInitializer()->getType()->isPointerTy() && GV->getInitializer()->isNullValue()) { ... 

yaitu variabel harus diinisialisasi dengan pointer nol. Jika ini masalahnya, maka kami membuat variabel SOVC baru yang sesuai dengan nilai StoredOnceVal yang digunakan untuk tipe GV:

 if (Constant *SOVC = dyn_cast<constant>(StoredOnceVal)) { if (GV->getInitializer()->getType() != SOVC->getType()) SOVC = ConstantExpr::getBitCast(SOVC, GV->getInitializer()->getType()); 

Di sini, getBitCast adalah metode yang mengembalikan perintah bitcast, yang mengetikkan tipe-tipe dalam bahasa IR LLVM.

Setelah itu, fungsi OptimizeAwayTrappingUsesOfLoads dipanggil. Ini mentransfer variabel global GV dan LV konstan.

Optimalisasi langsung dilakukan oleh fungsi OptimizeAwayTrappingUsesOfValue (Value * V, Constant * NewV).

Untuk setiap penggunaan variabel:

 for (auto UI = V->user_begin(), E = V->user_end(); UI != E; ) { Instruction *I = cast<instruction>(*UI++); 

jika ini adalah perintah Load, ganti operan dengan nilai baru:

 if (LoadInst *LI = dyn_cast<loadinst>(I)) { LI->setOperand(0, NewV); Changed = true; } 

Jika variabel digunakan dalam pemanggilan fungsi atau memanggil (yang persis seperti yang terjadi dalam contoh kita), buat fungsi baru, ganti argumennya dengan nilai baru:

 if (isa<callinst>(I) || isa<invokeinst>(I)) { CallSite CS(I); if (CS.getCalledValue() == V) { // Calling through the pointer! Turn into a direct call, but be careful // that the pointer is not also being passed as an argument. CS.setCalledFunction(NewV); Changed = true; bool PassedAsArg = false; for (unsigned i = 0, e = CS.arg_size(); i != e; ++i) if (CS.getArgument(i) == V) { PassedAsArg = true; CS.setArgument(i, NewV); } 

Semua argumen lain ke fungsi cukup disalin.

Juga, algoritma penggantian serupa disediakan untuk instruksi Cast dan GEP, tetapi dalam kasus kami ini tidak terjadi.

Tindakan selanjutnya adalah sebagai berikut: kita melihat melalui semua penggunaan variabel global, mencoba untuk menghapus semuanya, kecuali penugasan nilai. Jika ini berhasil, maka kita dapat menghapus variabel Do.

Jadi, kami meninjau secara singkat pekerjaan optimasi lulus LLVM pada contoh tertentu. Pada prinsipnya, tidak ada yang super rumit di sini, tetapi pemrograman yang lebih cermat diperlukan untuk menyediakan semua kemungkinan kombinasi perintah dan tipe variabel. Tentu saja, semua ini harus ditanggung oleh tes. Mempelajari kode sumber pengoptimal LLVM akan membantu Anda menulis pengoptimalan, yang memungkinkan Anda meningkatkan kode untuk beberapa kasus tertentu.