lacc
1.0.0
Ini adalah proyek mainan saya, dengan tujuan membuat kompiler untuk C, yang ditulis dalam C, yang mampu mengkompilasi dirinya sendiri.
Klon dan build dari sumber, dan biner akan ditempatkan di bin/lacc .
git clone https://github.com/larmel/lacc.git
cd lacc
./configure
make
make install
Konfigurasi default mencakup beberapa penyelidikan dasar lingkungan untuk mendeteksi mesin dan libc yang kami kompilasi. Platform yang diakui saat ini termasuk Linux dengan GLIBC atau MUSL, dan OpenBSD.
Header perpustakaan standar tertentu, seperti stddef.h dan stdarg.h , berisi definisi yang secara inheren kompiler spesifik, dan disediakan khusus untuk LACC di bawah lib/. Jika Anda ingin menggunakan bin/lacc secara langsung tanpa memasang header, Anda dapat mengganti lokasi dengan mengatur --libdir untuk menunjuk ke folder ini secara langsung.
Target install akan menyalin biner dan header ke lokasi yang biasa, atau seperti yang dikonfigurasi dengan --prefix atau --bindir . Ada juga opsi untuk mengatur DESTDIR . Execute make uninstall untuk menghapus semua file yang disalin.
Lihat ./configure --help untuk opsi untuk menyesuaikan parameter build dan instal.
Antarmuka baris perintah tetap mirip dengan GCC dan kompiler lainnya, menggunakan sebagian besar subset dari bendera dan opsi yang sama.
-E Output preprocessed.
-S Output GNU style textual x86_64 assembly.
-c Output x86_64 ELF object file.
-dot Output intermediate representation in dot format.
-o Specify output file name. If not speficied, default to input file
name with suffix changed to '.s', '.o' or '.dot' when compiling
with -S, -c or -dot, respectively. Otherwise use stdout.
-std= Specify C standard, valid options are c89, c99, and c11.
-I Add directory to search for included files.
-w Disable warnings.
-g Generate debug information (DWARF).
-O{0..3} Set optimization level.
-D X[=] Define macro, optionally with a value. For example -DNDEBUG, or
-D 'FOO(a)=a*2+1'.
-f[no-]PIC Generate position-independent code.
-v Print verbose diagnostic information. This will dump a lot of
internal state during compilation, and can be useful for debugging.
--help Print help text.
Argumen yang tidak cocok dengan opsi apa pun dianggap sebagai file input. Jika tidak ada mode kompilasi yang ditentukan, LACC akan bertindak sebagai pembungkus untuk penghubung sistem /bin/ld . Beberapa bendera penghubung umum didukung.
-Wl, Specify linker options, separated by commas.
-L Add linker include directory.
-l Add linker library.
-shared Passed to linker as is.
-rdynamic Pass -export-dynamic to linker.
Sebagai contoh doa, berikut adalah kompilasi tes/c89/fact.c ke kode objek, dan kemudian menggunakan linker sistem untuk menghasilkan yang dapat dieksekusi akhir.
bin/lacc -c test/c89/fact.c -o fact.o
bin/lacc fact.o -o fact
Program ini adalah bagian dari suite tes, menghitung 5! Menggunakan rekursi, dan keluar dengan jawabannya. Menjalankan ./fact diikuti oleh echo $? harus mencetak 120 .
Kompiler ditulis dalam C89, menghitung sekitar 19 ribu baris kode secara total. Tidak ada dependensi eksternal kecuali untuk C Standard Lebary, dan beberapa panggilan sistem yang diperlukan untuk memohon linker.
Implementasi disusun menjadi empat bagian utama; Preprocessor, parser, pengoptimal, dan backend, masing -masing di direktori mereka sendiri di bawah SRC/. Secara umum, setiap modul (file .c biasanya dipasangkan dengan file .h yang mendefinisikan antarmuka publik) sebagian besar bergantung pada header di subtree mereka sendiri. Deklarasi yang dibagikan di tingkat global berada di Incluble/LACC/. Di sinilah Anda akan menemukan struktur data inti, dan antarmuka antara preprocessing, parsing, dan pembuatan kode.
Preprocessing termasuk membaca file, tokenisasi, ekspansi makro, dan penanganan arahan. Antarmuka ke preprocessor adalah peek(0) , peekn(1) , consume(1) , try_consume(1) , dan next(0) , yang melihat aliran objek struct token yang diproses preproses. Ini didefinisikan dalam include/lacc/token.h.
Pemrosesan input dilakukan sepenuhnya malas, didorong oleh parser yang memanggil fungsi -fungsi ini untuk mengkonsumsi lebih banyak input. Buffer token preproses disimpan untuk Lookahead, dan diisi sesuai permintaan saat mengintip ke depan.
Kode dimodelkan sebagai grafik aliran kontrol blok dasar, masing-masing memegang urutan pernyataan kode tiga-alamat. Setiap variabel eksternal atau definisi fungsi diwakili oleh objek struct definition , mendefinisikan struct symbol tunggal dan CFG yang memegang kode. Struktur data yang mendukung representasi perantara dapat ditemukan di Incerted/LACC/IR.H.
Visualisasi representasi perantara adalah target output terpisah. Jika opsi -dot ditentukan, file teks yang diformat dot diproduksi sebagai output.
bin/lacc -dot -I include src/backend/compile.c -o compile.dot
dot -Tps compile.dot -o compile.ps
Di bawah ini adalah contoh dari fungsi yang ditemukan di SRC/Backend/Compile.c, menunjukkan sepotong grafik lengkap. Output lengkap dapat dihasilkan sebagai file PostScript dengan menjalankan perintah yang ditampilkan.
Setiap blok dasar dalam grafik memiliki daftar pernyataan, paling umum IR_ASSIGN , yang menetapkan ekspresi ( struct expression ) ke variabel ( struct var ). Ekspresi juga mengandung operan variabel, yang dapat mengkodekan lokasi memori, alamat dan pointer di level tinggi.
DIRECT merujuk ke memori di *(&symbol + offset) , di mana simbol adalah variabel atau sementara di lokasi tertentu dalam memori (misalnya tumpukan).ADDRESS operan mewakili secara tepat alamat operan DIRECT , yaitu (&symbol + offset) .DEREF merujuk pada memori yang ditunjukkan oleh simbol (yang harus dari tipe pointer). Ekspresi adalah *(symbol + offset) , yang membutuhkan dua operasi beban untuk memetakan ke perakitan. Hanya variabel DEREF dan DIRECT yang dapat menjadi target untuk penugasan, atau nilai-L.IMMEDIATE memiliki angka konstan, atau string. Evaluasi operan langsung melakukan lipat konstan secara otomatis.Parser adalah penurunan rekursif tangan tangan, dengan bagian utama dibagi menjadi SRC/parser/deklarasi.c, src/parser/initializer.c, src/parser/ekspresi.c, dan src/parser/pernyataan.c. Grafik aliran kontrol fungsi saat ini, dan blok dasar aktif saat ini dalam grafik itu, dilewatkan sebagai argumen untuk setiap produksi. Grafik ini secara bertahap dibangun sebagai instruksi kode tiga-alamat baru ditambahkan ke blok saat ini.
Contoh berikut menunjukkan aturan parsing untuk bitwise atau ekspresi, yang menambahkan operasi IR_OP_OR baru ke blok saat ini. Logika di eval_expr akan memastikan bahwa value operan dan block->expr adalah valid, diakhiri jika terjadi kesalahan.
static struct block *inclusive_or_expression(
struct definition *def,
struct block *block)
{
struct var value;
block = exclusive_or_expression(def, block);
while (try_consume('|')) {
value = eval(def, block, block->expr);
block = exclusive_or_expression(def, block);
block->expr = eval_or(def, block, value, eval(def, block, block->expr));
}
return block;
}
Hasil evaluasi terbaru selalu disimpan dalam block->expr . Percabangan dilakukan dengan membuat blok dasar baru dan memelihara pointer. Setiap blok dasar memiliki penunjuk cabang yang benar dan palsu ke blok lain, yang merupakan bagaimana cabang dan gotos dimodelkan. Perhatikan bahwa tidak ada struktur pohon sintaks yang sedang dibangun. Itu hanya ada secara implisit dalam rekursi.
Motivasi utama untuk membangun grafik aliran kontrol adalah untuk dapat melakukan analisis dan optimasi Dataflow. Kemampuan saat ini di sini masih terbatas, tetapi dapat dengan mudah diperluas dengan analisis tambahan dan lebih canggih dan lulus optimasi.
Analisis livene digunakan untuk mencari tahu, pada setiap pernyataan, simbol mana yang kemudian dapat dibaca. Algoritma DataFlow diimplementasikan menggunakan masker bit untuk mewakili simbol, menunjuknya 1-63. Sebagai akibatnya, optimasi hanya berfungsi pada fungsi dengan kurang dari 64 variabel. Algoritma ini juga harus sangat konservatif, karena tidak ada analisis pointer alias (belum).
Menggunakan informasi livitas, umpan transformasi yang melakukan eliminasi toko mati dapat menghapus node IR_ASSIGN yang terbukti tidak melakukan apa -apa, mengurangi ukuran kode yang dihasilkan.
Ada tiga target backend: kode perakitan tekstual, file objek ELF, dan titik untuk representasi perantara. Setiap objek struct definition yang dihasilkan dari parser diteruskan ke modul SRC/Backend/Compile.c. Di sini kami melakukan pemetaan dari representasi grafik aliran kontrol menengah ke tingkat yang lebih rendah, mengurangi kode menjadi sesuatu yang secara langsung mewakili instruksi x86_64. Definisi untuk ini dapat ditemukan di SRC/Backend/x86_64/encoding.h.
Bergantung pada pointer fungsi yang diatur pada awal program, instruksi dikirim ke backend ELF, atau perakitan teks. Oleh karena itu kode untuk output rakitan teks sangat sederhana, kurang lebih hanya pemetaan antara instruksi IR level rendah dan kode perakitan sintaks GNU mereka. Lihat SRC/Backend/X86_64/Assemble.c.
Output DOT adalah pipa terpisah yang tidak perlu IR level rendah untuk dihasilkan. Modul Compile hanya akan meneruskan CFG ke SRC/Backend/GraphViz/DOT.C.
Pengujian dilakukan dengan membandingkan output runtime dari program yang dikompilasi dengan LACC dan System Compiler (CC). Kumpulan program mandiri kecil yang digunakan untuk validasi dapat ditemukan di bawah Tes/ Direktori. Tes dijalankan menggunakan check.sh, yang akan memvalidasi output preprocessing, perakitan, dan ELF.
$ test/check.sh bin/lacc test/c89/fact.c
[-E: Ok!] [-S: Ok!] [-c: Ok!] [-c -O1: Ok!] :: test/c89/fact.c
Tes lengkap dari kompiler dilakukan dengan melalui semua kasus uji pada versi self-hosting LACC.
make -C test
Ini pertama -tama akan menggunakan bin/lacc yang sudah dibangun untuk memproduksi bin/bootstrap/lacc , yang pada gilirannya digunakan untuk membangun bin/selfhost/lacc . Antara tahap bootstrap dan selfhost, file objek menengah dibandingkan untuk kesetaraan. Jika semuanya bekerja dengan benar, tahapan ini harus menghasilkan biner yang identik. Kompilernya adalah '' baik '' ketika semua tes meneruskan biner diri sendiri. Ini harus selalu hijau, pada setiap komit.
Sulit untuk menghasilkan suite tes yang baik yang mencakup semua kasus yang mungkin. Untuk menghilangkan bug, kita dapat menggunakan CSMITH untuk menghasilkan program acak yang cocok untuk validasi.
./csmith.sh
Skrip csmith.sh menjalankan CSMITH untuk menghasilkan urutan program acak yang tak terbatas sampai sesuatu gagal dalam harness tes. Ini biasanya akan menjalankan ribuan tes tanpa kegagalan.
Program yang dihasilkan oleh CSMITH berisi serangkaian variabel global, dan fungsi membuat mutasi pada ini. Pada akhirnya, checksum dari keadaan lengkap dari semua variabel adalah output. Checksum ini kemudian dapat dibandingkan dengan kompiler yang berbeda untuk menemukan diskrepsi, atau bug. Lihat DOC/RANCE.C Untuk contoh program yang dihasilkan oleh CSMITH, yang juga dikompilasi dengan benar oleh LACC.
Ketika sebuah bug ditemukan, kita dapat menggunakan Creduce untuk membuat repro minimal. Ini kemudian akan berakhir sebagai kasus uji baru di rangkaian uji normal.
Beberapa upaya telah dilakukan untuk membuat kompiler itu sendiri dengan cepat (meskipun kode yang dihasilkan masih sangat tidak dioptimalkan). Melayani sebagai tolok ukur kinerja dan uji kebenaran, kami menggunakan mesin basis data SQLite. Kode sumber didistribusikan sebagai file C besar ~ 7 Mb (7184634) yang mencakup lebih dari 200 K baris (termasuk komentar dan whitespace), yang sempurna untuk menguji stres kompiler.
Eksperimen berikut dijalankan pada laptop dengan CPU I5-7300U, mengkompilasi versi 3.20.1 dari SQLite3. Pengukuran dibuat dari kompilasi ke kode objek (-c).
Dibutuhkan kurang dari 200 ms untuk mengkompilasi file dengan LACC, tetapi bukannya waktu kita melihat pengambilan sampel yang lebih akurat dari siklus CPU dan instruksi yang dieksekusi. Data penghitung kinerja perangkat keras dikumpulkan dengan perf stat , dan alokasi memori dengan valgrind --trace-children=yes . Di Valgrind, kami hanya menghitung kontribusi dari kompiler itu sendiri ( cc1 dapat dieksekusi) saat menjalankan GCC.
Angka untuk LACC berasal dari build yang dioptimalkan yang diproduksi oleh make CC='clang -O3 -DNDEBUG' bin/lacc . Setiap kompiler dipanggil dengan argumen -c sqlite/sqlite3.c -o foo.o
| Penyusun | Siklus | Instruksi | Alokasi | Byte dialokasikan | Ukuran hasil |
|---|---|---|---|---|---|
| lacc | 412.334.334 | 619.466.003 | 49.020 | 24.244.107 | 1.590.482 |
| TCC (0.9.27) | 245.142.166 | 397.514.762 | 2.909 | 23.020.917 | 1.409.716 |
| GCC (9.3.0) | 9.958.514.599 | 14.524.274.665 | 1.546.790 | 1.111.331.606 | 1.098.408 |
| dentang (10.0.0) | 4.351.456.211 | 5.466.808.426 | 1.434.072 | 476.529.342 | 1.116.992 |
Belum ada pekerjaan yang harus dilakukan untuk lebih dekat dengan TCC, yang mungkin merupakan salah satu kompiler C tercepat yang tersedia. Namun, kami berada dalam jarak yang wajar dari kinerja TCC, dan urutan besarnya lebih baik daripada GCC dan Clang.
Dari tabel di atas, kita dapat melihat bahwa ukuran file objek SQLite yang dihasilkan oleh LACC lebih besar daripada yang dihasilkan oleh kompiler lain, menunjukkan bahwa kami menghasilkan kode yang kurang optimal.
Untuk membandingkan kualitas relatif kode yang dihasilkan dari LACC dan GCC, kita dapat melihat jumlah instruksi dinamis yang dieksekusi oleh biner selfhost versus biner yang dibangun oleh GCC. Kami menjalankan tes yang sama seperti di atas, menyusun SQLite ke kode objek. Target untuk pengujian adalah compiler build ( bin/lacc ) yang diproduksi oleh GCC, dan biner selfhost ( bin/selfhost/lacc ) yang diproduksi oleh LACC. Kedua target ini diproduksi tanpa optimasi yang diaktifkan, dan tanpa mendefinisikan NDEBUG .
| Penyusun | Siklus | Instruksi |
|---|---|---|
| lacc | 946.315.653 | 1.481.608.726 |
| LACC (Self -Host) | 1.417.112.690 | 2.046.996.115 |
Biner yang diselesaikan lebih lambat untuk menyusun SQLite daripada kompiler yang dibangun oleh GCC, menunjukkan bahwa LACC memang menghasilkan kode yang agak tidak efisien. Meningkatkan backend dengan pemilihan instruksi yang lebih baik adalah prioritas, jadi angka -angka ini semoga lebih dekat di masa depan.
Ini adalah beberapa sumber daya yang berguna untuk membangun kompiler C yang menargetkan x86_64.
