lacc
1.0.0
นี่เป็นโครงการของเล่นของฉันโดยมีเป้าหมายในการสร้างคอมไพเลอร์สำหรับ C ซึ่งเขียนด้วย C ซึ่งสามารถรวบรวมตัวเองได้
โคลนและสร้างจากแหล่งที่มาและไบนารีจะถูกวางไว้ใน bin/lacc
git clone https://github.com/larmel/lacc.git
cd lacc
./configure
make
make install
การกำหนดค่าเริ่มต้นรวมถึงการตรวจสอบพื้นฐานของสภาพแวดล้อมเพื่อตรวจสอบว่าเครื่องใดและ LIBC ที่เรากำลังรวบรวม แพลตฟอร์มที่ได้รับการยอมรับในปัจจุบันรวมถึง Linux ด้วย GLIBC หรือ MUSL และ OpenBSD
ส่วนหัวของไลบรารีมาตรฐานบางอย่างเช่น stddef.h และ stdarg.h มีคำจำกัดความที่เป็นคอมไพเลอร์โดยเนื้อแท้และมีให้เฉพาะสำหรับ LACC ภายใต้ LIB/ หากคุณต้องการใช้ bin/lacc โดยตรงโดยไม่ต้องติดตั้งส่วนหัวคุณสามารถแทนที่ตำแหน่งโดยการตั้งค่า --libdir เพื่อชี้ไปที่โฟลเดอร์นี้โดยตรง
เป้าหมาย install จะคัดลอกไบนารีและส่วนหัวไปยังตำแหน่งปกติหรือกำหนดค่าด้วย --prefix หรือ --bindir นอกจากนี้ยังมีตัวเลือกในการตั้งค่า DESTDIR ดำเนินการ make uninstall เพื่อลบไฟล์ทั้งหมดที่คัดลอก
ดู ./configure --help สำหรับตัวเลือกในการปรับแต่งพารามิเตอร์การสร้างและติดตั้ง
อินเทอร์เฟซบรรทัดคำสั่งจะถูกเก็บไว้คล้ายกับ GCC และคอมไพเลอร์อื่น ๆ โดยใช้ชุดย่อยส่วนใหญ่ของธงและตัวเลือกเดียวกัน
-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.
อาร์กิวเมนต์ที่ไม่ตรงกับตัวเลือกใด ๆ จะถูกนำมาเป็นไฟล์อินพุต หากไม่ได้ระบุโหมดการรวบรวม LACC จะทำหน้าที่เป็น wrapper สำหรับระบบ linker /bin/ld รองรับธงเชื่อมโยงทั่วไปบางตัวได้รับการสนับสนุน
-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.
เป็นตัวอย่างการเรียกใช้นี่คือการรวบรวมการทดสอบ/C89/fact.c เป็นรหัสวัตถุจากนั้นใช้ตัวเชื่อมโยงระบบเพื่อสร้างการเรียกใช้งานขั้นสุดท้าย
bin/lacc -c test/c89/fact.c -o fact.o
bin/lacc fact.o -o fact
โปรแกรมเป็นส่วนหนึ่งของชุดทดสอบโดยคำนวณ 5! ใช้การเรียกซ้ำและออกพร้อมกับคำตอบ วิ่ง ./fact facting ตามด้วย echo $? ควรพิมพ์ 120
คอมไพเลอร์เขียนใน C89 นับรหัสทั้งหมด 19k บรรทัดทั้งหมด ไม่มีการพึ่งพาภายนอกยกเว้น libary มาตรฐาน C และการโทรบางระบบที่จำเป็นในการเรียกใช้ linker
การดำเนินการถูกจัดเป็นสี่ส่วนหลัก ตัวประมวลผลล่วงหน้า, ตัวแยกวิเคราะห์, เครื่องมือเพิ่มประสิทธิภาพและแบ็กเอนด์แต่ละตัวอยู่ในไดเรกทอรีของตนเองภายใต้ SRC/ โดยทั่วไปแต่ละโมดูล (ไฟล์ .c มักจะจับคู่กับไฟล์ .h ที่กำหนดอินเทอร์เฟซสาธารณะ) ขึ้นอยู่กับส่วนใหญ่ในทรีย่อยของตนเอง การประกาศที่ใช้ร่วมกันในระดับโลกอยู่ในรวมถึง/LACC/ นี่คือที่ที่คุณจะพบโครงสร้างข้อมูลหลักและอินเทอร์เฟซระหว่างการประมวลผลล่วงหน้าการแยกวิเคราะห์และการสร้างรหัส
การประมวลผลล่วงหน้ารวมถึงการอ่านไฟล์โทเค็นการขยายตัวของแมโครและการจัดการคำสั่ง อินเทอร์เฟซไปยังตัวประมวลผลล่วงหน้าคือ peek(0) , peekn(1) , consume(1) , try_consume(1) และ next(0) ซึ่งดูที่กระแสของวัตถุ struct token ที่ถูกประมวลผลล่วงหน้า สิ่งเหล่านี้ถูกกำหนดไว้ในรวมถึง/lacc/token.h
การประมวลผลอินพุตทำได้อย่างเกียจคร้านอย่างสมบูรณ์ขับเคลื่อนโดยตัวแยกวิเคราะห์การเรียกใช้ฟังก์ชั่นเหล่านี้เพื่อใช้อินพุตมากขึ้น บัฟเฟอร์ของโทเค็นที่ประมวลผลล่วงหน้าจะถูกเก็บไว้สำหรับ lookahead และเติมเต็มความต้องการเมื่อมองไปข้างหน้า
รหัสถูกสร้างแบบจำลองเป็นกราฟการควบคุมการควบคุมของบล็อกพื้นฐานแต่ละรายการที่ถือลำดับของคำสั่งรหัสที่อยู่สามส่วน แต่ละตัวแปรภายนอกหรือนิยามฟังก์ชั่นจะถูกแสดงโดยวัตถุ struct definition โดยกำหนด struct symbol เดียวและ CFG ที่ถือรหัส โครงสร้างข้อมูลที่สนับสนุนการเป็นตัวแทนระดับกลางสามารถพบได้ในรวมถึง/LACC/IR.H
การแสดงภาพการเป็นตัวแทนระดับกลางเป็นเป้าหมายที่แยกต่างหาก หากระบุตัวเลือก -DOT ไฟล์ข้อความที่จัดรูปแบบ DOT จะถูกสร้างขึ้นเป็นเอาต์พุต
bin/lacc -dot -I include src/backend/compile.c -o compile.dot
dot -Tps compile.dot -o compile.ps
ด้านล่างเป็นตัวอย่างจากฟังก์ชั่นที่พบใน SRC/Backend/Compile.c แสดงชิ้นส่วนของกราฟที่สมบูรณ์ เอาต์พุตแบบเต็มสามารถสร้างเป็นไฟล์ postscript โดยเรียกใช้คำสั่งที่แสดง
แต่ละบล็อกพื้นฐานในกราฟมีรายการคำสั่งส่วนใหญ่ IR_ASSIGN ซึ่งกำหนดนิพจน์ ( struct expression ) ให้กับตัวแปร ( struct var ) นิพจน์ยังมีตัวดำเนินการแปรผันซึ่งสามารถเข้ารหัสตำแหน่งหน่วยความจำที่อยู่และพอยน์เตอร์ที่อ้างอิงได้ในระดับสูง
DIRECT อ้างถึงหน่วยความจำที่ *(&symbol + offset) โดยที่สัญลักษณ์เป็นตัวแปรหรือชั่วคราวที่ตำแหน่งเฉพาะในหน่วยความจำ (ตัวอย่างเช่นสแต็ก)ADDRESS แสดงถึงที่อยู่ของตัวถูกดำเนินการ DIRECT คือ (&symbol + offset)DEREF อ้างถึงหน่วยความจำที่ชี้ไปที่สัญลักษณ์ (ซึ่งต้องเป็นประเภทตัวชี้) นิพจน์คือ *(symbol + offset) ซึ่งต้องใช้การโหลดสองแบบเพื่อทำแผนที่ไปยังแอสเซมบลี เฉพาะ DEREF และตัวแปร DIRECT เท่านั้นที่สามารถเป็นเป้าหมายสำหรับการกำหนดหรือค่า LIMMEDIATE มีหมายเลขคงที่หรือสตริง การประเมินผลการดำเนินการทันทีจะพับได้อย่างต่อเนื่องโดยอัตโนมัติตัวแยกวิเคราะห์เป็นโคตรแบบเรียกซ้ำด้วยมือโดยมีส่วนหลักแบ่งออกเป็น src/parser/declaration.c, src/parser/initializer.c, src/parser/expression.c และ src/parser/statement.c กราฟการควบคุมฟังก์ชั่นการควบคุมฟังก์ชั่นปัจจุบันและบล็อกพื้นฐานที่ใช้งานอยู่ในกราฟนั้นจะถูกส่งผ่านเป็นอาร์กิวเมนต์ไปยังการผลิตแต่ละครั้ง กราฟจะค่อยๆสร้างขึ้นเป็นคำแนะนำรหัสสามส่วนใหม่จะถูกเพิ่มลงในบล็อกปัจจุบัน
ตัวอย่างต่อไปนี้แสดงกฎการแยกวิเคราะห์สำหรับ bitwise หรือนิพจน์ซึ่งเพิ่มการดำเนินการ IR_OP_OR ใหม่ให้กับบล็อกปัจจุบัน ตรรกะใน eval_expr จะตรวจสอบให้แน่ใจว่า value ตัวถูกดำเนินการและ block->expr นั้นถูกต้องโดยสิ้นสุดในกรณีที่เกิดข้อผิดพลาด
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;
}
ผลการประเมินล่าสุดจะถูกเก็บไว้ใน block->expr เสมอ การแตกแขนงทำโดยการสร้างอินสแตนซ์บล็อกพื้นฐานใหม่และการบำรุงรักษาพอยน์เตอร์ แต่ละบล็อกพื้นฐานมีตัวชี้สาขาที่แท้จริงและเท็จไปยังบล็อกอื่น ๆ ซึ่งเป็นวิธีการที่สาขาและ gotos เป็นแบบจำลอง โปรดทราบว่าไม่มีจุดใดโครงสร้างต้นไม้ไวยากรณ์ใด ๆ ที่ถูกสร้างขึ้น มันมีอยู่โดยปริยายในการเรียกซ้ำ
แรงจูงใจหลักสำหรับการสร้างกราฟการควบคุมการไหลคือการทำการวิเคราะห์ DataFlow และการเพิ่มประสิทธิภาพ ความสามารถในปัจจุบันที่นี่ยังคงมี จำกัด แต่สามารถขยายได้อย่างง่ายดายด้วยการวิเคราะห์เพิ่มเติมและขั้นสูงและการเพิ่มประสิทธิภาพผ่าน
การวิเคราะห์ Livence ใช้เพื่อค้นหาทุกคำสั่งซึ่งอาจอ่านสัญลักษณ์ในภายหลัง อัลกอริทึม DataFlow ถูกนำมาใช้โดยใช้มาสก์บิตเพื่อแสดงสัญลักษณ์โดยนับ 1-63 เป็นผลให้การเพิ่มประสิทธิภาพใช้งานได้เฉพาะฟังก์ชั่นที่มีตัวแปรน้อยกว่า 64 ตัวเท่านั้น อัลกอริทึมจะต้องอนุรักษ์นิยมมากเนื่องจากไม่มีการวิเคราะห์ตัวชี้นามแฝง (ยัง)
การใช้ข้อมูล Livence การแปลงผ่านการกำจัดร้านค้า Dead Store สามารถลบโหนด IR_ASSIGN ซึ่งไม่ได้ทำอะไรเลยลดขนาดของรหัสที่สร้างขึ้น
มีสามเป้าหมายแบ็กเอนด์: รหัสประกอบข้อความไฟล์วัตถุ ELF และ DOT สำหรับการเป็นตัวแทนระดับกลาง แต่ละวัตถุ struct definition ที่ได้จากตัวแยกวิเคราะห์จะถูกส่งผ่านไปยังโมดูล SRC/Backend/Compile.C ที่นี่เราทำการแมปจากการแสดงกราฟการไหลของการควบคุมระดับกลางลงไปที่ IR ระดับต่ำกว่าลดรหัสเป็นสิ่งที่แสดงถึงคำแนะนำ x86_64 โดยตรง คำจำกัดความสำหรับสิ่งนี้สามารถพบได้ใน src/backend/x86_64/encoding.h
ขึ้นอยู่กับพอยน์เตอร์ฟังก์ชั่นที่ตั้งค่าบนโปรแกรมเริ่มต้นคำแนะนำจะถูกส่งไปยังแบ็กเอนด์เอลฟ์หรือชุดข้อความ การประกอบรหัสเพื่อเอาต์พุตจึงง่ายมากไม่มากก็น้อยเพียงแค่การแมประหว่างคำแนะนำ IR ระดับต่ำและรหัสประกอบไวยากรณ์ GNU ของพวกเขา ดู src/backend/x86_64/assemble.c
เอาต์พุต DOT เป็นไปป์ไลน์แยกต่างหากที่ไม่จำเป็นต้องสร้าง IR ระดับต่ำ โมดูลคอมไพล์จะส่งต่อ CFG ไปยัง SRC/Backend/graphviz/dot.c
การทดสอบทำได้โดยการเปรียบเทียบเอาต์พุตรันไทม์ของโปรแกรมที่รวบรวมด้วย LACC และคอมไพเลอร์ระบบ (CC) คอลเลกชันของโปรแกรมสแตนด์อโลนขนาดเล็กที่ใช้สำหรับการตรวจสอบสามารถพบได้ภายใต้การทดสอบ/ ไดเรกทอรี การทดสอบจะดำเนินการโดยใช้ check.sh ซึ่งจะตรวจสอบการประมวลผลล่วงหน้าการประกอบและเอาต์พุต ELF
$ test/check.sh bin/lacc test/c89/fact.c
[-E: Ok!] [-S: Ok!] [-c: Ok!] [-c -O1: Ok!] :: test/c89/fact.c
การทดสอบที่สมบูรณ์ของคอมไพเลอร์ทำได้โดยผ่านกรณีทดสอบทั้งหมดใน LACC รุ่นโฮสต์ด้วยตนเอง
make -C test
สิ่งนี้จะใช้ bin/lacc ที่สร้างขึ้นแล้วเพื่อผลิต bin/bootstrap/lacc ซึ่งจะใช้ในการสร้าง bin/selfhost/lacc ระหว่างขั้นตอน bootstrap และ selfhost ไฟล์วัตถุกลางจะถูกเปรียบเทียบเพื่อความเท่าเทียมกัน หากทุกอย่างทำงานได้อย่างถูกต้องขั้นตอนเหล่านี้ควรสร้างไบนารีที่เหมือนกัน คอมไพเลอร์คือ '' ดี '' เมื่อการทดสอบทั้งหมดผ่านไบนารีตัวเอง สิ่งนี้ควรเป็นสีเขียวเสมอในทุกการกระทำ
มันยากที่จะเกิดขึ้นกับชุดทดสอบที่ดีครอบคลุมทุกกรณีที่เป็นไปได้ เพื่อที่จะกำจัดข้อบกพร่องเราสามารถใช้ CSMITH เพื่อสร้างโปรแกรมแบบสุ่มที่เหมาะสมสำหรับการตรวจสอบความถูกต้อง
./csmith.sh
สคริปต์ CSMITH.SH เรียกใช้ CSMITH เพื่อสร้างลำดับที่ไม่มีที่สิ้นสุดของโปรแกรมสุ่มจนกว่าจะมีบางสิ่งที่ล้มเหลวในการทดสอบสายรัด โดยทั่วไปแล้วจะทำการทดสอบหลายพันครั้งโดยไม่ล้มเหลว
โปรแกรมที่สร้างโดย CSMITH มีชุดของตัวแปรทั่วโลกและฟังก์ชั่นทำให้การกลายพันธุ์ของสิ่งเหล่านี้ ในตอนท้ายการตรวจสอบสถานะที่สมบูรณ์ของตัวแปรทั้งหมดคือเอาต์พุต การตรวจสอบนี้สามารถเปรียบเทียบกับคอมไพเลอร์ที่แตกต่างกันเพื่อค้นหาความโดดเด่นหรือข้อบกพร่อง ดู doc/random.c สำหรับโปรแกรมตัวอย่างที่สร้างโดย CSMITH ซึ่งรวบรวมอย่างถูกต้องโดย LACC
เมื่อพบข้อผิดพลาดเราสามารถใช้ Creduce เพื่อทำซ้ำน้อยที่สุด สิ่งนี้จะจบลงด้วยกรณีทดสอบใหม่ในชุดทดสอบปกติ
ความพยายามบางอย่างได้ถูกนำมาใช้ในการทำให้คอมไพเลอร์ตัวเองเร็ว (แม้ว่ารหัสที่สร้างขึ้นยังคงไม่ได้รับการปรับสภาพเป็นอย่างมาก) ทำหน้าที่เป็นทั้งมาตรฐานประสิทธิภาพและการทดสอบความถูกต้องเราใช้เอ็นจินฐานข้อมูล SQLite ซอร์สโค้ดถูกแจกจ่ายเป็นไฟล์ C ขนาดใหญ่ ~ 7 MB (7184634 ไบต์) ขนาดใหญ่ที่ครอบคลุมมากกว่า 200 K บรรทัด (รวมถึงความคิดเห็นและช่องว่าง) ซึ่งเหมาะสำหรับการทดสอบความเครียดคอมไพเลอร์
การทดลองต่อไปนี้ทำงานบนแล็ปท็อปด้วย CPU i5-7300U รวบรวมเวอร์ชัน 3.20.1 ของ SQLite3 การวัดทำจากการรวบรวมเป็นรหัสวัตถุ (-C)
ใช้เวลาน้อยกว่า 200 มิลลิวินาทีในการรวบรวมไฟล์ด้วย LACC แต่แทนที่จะเป็นเวลาที่เราจะดูการสุ่มตัวอย่างที่แม่นยำยิ่งขึ้นของวัฏจักร CPU และคำแนะนำที่ดำเนินการ ข้อมูลตัวนับประสิทธิภาพของฮาร์ดแวร์จะถูกรวบรวมด้วย perf stat และการจัดสรรหน่วยความจำด้วย valgrind --trace-children=yes ใน Valgrind เราเพียงแค่นับการมีส่วนร่วมจากคอมไพเลอร์เอง ( cc1 ที่เรียกใช้งานได้) ในขณะที่เรียกใช้ GCC
ตัวเลขสำหรับ LACC นั้นมาจากการสร้างที่ดีที่สุดที่ผลิตโดย make CC='clang -O3 -DNDEBUG' bin/lacc คอมไพเลอร์แต่ละตัวจะถูกเรียกใช้ด้วยอาร์กิวเมนต์ -c sqlite/sqlite3.c -o foo.o
| ผู้ประกอบการ | รอบ | คำแนะนำ | การจัดสรร | ไบต์จัดสรร | ขนาดผลลัพธ์ |
|---|---|---|---|---|---|
| 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 |
| เสียงดัง (10.0.0) | 4,351,456,211 | 5,466,808,426 | 1,434,072 | 476,529,342 | 1,116,992 |
ยังมีงานที่ต้องทำเพื่อให้ใกล้ชิดกับ TCC ซึ่งอาจเป็นหนึ่งในคอมไพเลอร์ C ที่เร็วที่สุดที่มีอยู่ ถึงกระนั้นเราอยู่ในระยะที่เหมาะสมจากประสิทธิภาพของ TCC และลำดับความสำคัญที่ดีกว่า GCC และ Clang
จากตารางด้านบนเราจะเห็นได้ว่าขนาดของไฟล์วัตถุ SQLite ที่สร้างโดย LACC นั้นมีขนาดใหญ่กว่าที่สร้างโดยคอมไพเลอร์อื่น ๆ โดยบอกว่าเราส่งออกรหัสที่ดีที่สุดน้อยกว่า
เพื่อเปรียบเทียบคุณภาพสัมพัทธ์ของรหัสที่สร้างขึ้นจาก LACC และ GCC เราสามารถดูจำนวนคำสั่งแบบไดนามิกที่ดำเนินการโดยไบนารี Selfhost กับไบนารีที่สร้างโดย GCC เราเรียกใช้การทดสอบเดียวกับด้านบนรวบรวม SQLite เป็นรหัสวัตถุ เป้าหมายสำหรับการทดสอบคือการสร้างคอมไพเลอร์เริ่มต้น ( bin/lacc ) ที่ผลิตโดย GCC และ Selfhost binary ( bin/selfhost/lacc ) ที่ผลิตโดย LACC เป้าหมายทั้งสองนี้ผลิตโดยไม่เปิดใช้งานการปรับให้เหมาะสมและไม่ต้องกำหนด NDEBUG
| ผู้ประกอบการ | รอบ | คำแนะนำ |
|---|---|---|
| LACC | 946,315,653 | 1,481,608,726 |
| LACC (selfhost) | 1,417,112,690 | 2,046,996,115 |
ไบนารี selfhosted ช้ากว่าในการรวบรวม SQLite มากกว่าคอมไพเลอร์ที่สร้างโดย GCC แสดงให้เห็นว่า LACC สร้างรหัสที่ไม่มีประสิทธิภาพ การปรับปรุงแบ็กเอนด์ด้วยการเลือกคำแนะนำที่ดีขึ้นเป็นสิ่งสำคัญดังนั้นตัวเลขเหล่านี้ควรเข้าใกล้ในอนาคต
เหล่านี้เป็นทรัพยากรที่มีประโยชน์สำหรับการสร้างคอมไพเลอร์ C ที่กำหนดเป้าหมาย x86_64
