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 للحصول على خيارات لتخصيص المعلمات وتثبيتها.
يتم الحفاظ على واجهة سطر الأوامر مماثلة لمجموعات مجلس التعاون الخليجي وغيرها من المجمعين ، باستخدام مجموعة فرعية من نفس الأعلام والخيارات.
-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 بمثابة غلاف لرابط النظام /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 تليها echo $? يجب طباعة 120 .
يتم كتابة المترجم في C89 ، ويعدل حوالي 19 كيلو خط من الكود في المجموع. لا توجد تبعيات خارجية باستثناء L libary القياسية ، وبعض مكالمات النظام المطلوبة لاستدعاء الرابط.
يتم تنظيم التنفيذ في أربعة أجزاء رئيسية ؛ المعالج المسبق ، المحلل ، المحسن ، والخلفية ، كل في دليل خاص بهم بموجب 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 فقط هدفًا للخصم ، أو القيمة L.IMMEDIATE رقمًا ثابتًا أو سلسلة. تقييم المعاملات الفورية تقوم بطي ثابت تلقائيًا.المحلل هو النسب المتكرر باليد ، مع تقسيم الأجزاء الرئيسية إلى src/parser/denaration.c ، src/parser/ulthemizer.c ، src/parser/expression.c ، و src/parser/state.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. لاحظ أنه في أي وقت من الأوقات ، هناك أي بنية شجرة بناء الجملة. إنه موجود ضمنيًا فقط في العودية.
الدافع الرئيسي لبناء رسم بياني لتدفق التحكم هو أن تكون قادرًا على إجراء تحليل تدفق البيانات والتحسين. لا تزال القدرات الحالية هنا محدودة ، ولكن يمكن تمديدها بسهولة مع تمريرات وتحليل إضافي ومزيد من التحليل والتحسين.
يتم استخدام تحليل LEBING لمعرفة ذلك ، في كل عبارة ، يمكن قراءة الرموز لاحقًا. يتم تنفيذ خوارزمية بيانات البيانات باستخدام أقنعة بت لتمثيل الرموز ، وترقيمها 1-63. نتيجة لذلك ، يعمل التحسين فقط على وظائف مع أقل من 64 متغير. كما يجب أن تكون الخوارزمية محافظة للغاية ، حيث لا يوجد تحليل اسم مستعار المؤشر (حتى الآن).
باستخدام معلومات Lifik ، يمكن أن يؤدي ممر التحول الذي يقوم بإزالة المتجر الميت بإزالة العقد IR_ASSIGN التي لا تفعل شيئًا بشكل واضح ، مما يقلل من حجم الرمز الذي تم إنشاؤه.
هناك ثلاثة أهداف للواجهة الخلفية: رمز التجميع النصي ، وملفات كائن ELF ، ونقطة للتمثيل الوسيط. يتم تمرير كل كائن struct definition تم إنتاجه من المحلل إلى وحدة SRC/الخلفية/compile.c. نحن هنا نقوم برسم خرائط من تمثيل الرسم البياني لتدفق التحكم الوسيط وصولاً إلى IR من المستوى الأدنى ، مما يقلل من الرمز إلى شيء يمثل تعليمات x86_64 مباشرة. يمكن العثور على تعريف ذلك في SRC/Backend/x86_64/encoding.h.
اعتمادًا على مؤشرات الوظيفة التي تم إعدادها في بدء البرنامج ، يتم إرسال التعليمات إلى الواجهة الخلفية ELF أو تجميع النص. وبالتالي فإن رمز تجميع النص الإخراج بسيط للغاية ، أكثر أو أقل مجرد رسم خرائط بين تعليمات الأشعة تحت الحمراء منخفضة المستوى ورمز تجميع بناء جملة GNU الخاص بهم. انظر SRC/Backend/x86_64/comple.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. يتم توزيع رمز المصدر على أنه ملف واحد ~ 7 ميغابايت (7184634 بايت) ملف C كبير يمتد على أكثر من 200 كيلو بايت (بما في ذلك التعليقات والمساحة البيضاء) ، وهو مثالي لاختبار الإجهاد.
تم إجراء التجارب التالية على جهاز كمبيوتر محمول باستخدام وحدة المعالجة المركزية I5-7300U ، الإصدار 3.20.1 من SQLITE3. يتم إجراء القياسات من التجميع إلى رمز الكائن (-C).
يتطلب الأمر أقل من 200 مللي ثانية لتجميع الملف باستخدام LACC ، ولكن بدلاً من الوقت ، ننظر إلى أخذ عينات أكثر دقة لدورات وحدة المعالجة المركزية والتعليمات التي تم تنفيذها. يتم جمع بيانات عداد أداء الأجهزة باستخدام 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 | 41233434 | 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 |
| Clang (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 Binary مقابل ثنائي تم بناؤه بواسطة GCC. نقوم بتشغيل نفس الاختبار على النحو الوارد أعلاه ، وتجميع SQLite إلى رمز الكائن. أهداف الاختبار هي البناء الافتراضي للمترجم ( bin/lacc ) التي تنتجها مجلس التعاون الخليجي ، وذاتي الثنائي ( bin/selfhost/lacc ) الذي تنتجه LACC. يتم إنتاج كلا هذين الهدفين دون تمكين أي تحسينات ، ودون تحديد NDEBUG .
| المترجم | دورات | تعليمات |
|---|---|---|
| LACC | 946،315،653 | 1،481،608،726 |
| LACC (المضيف الذاتي) | 1،417،112،690 | 2،046،996،115 |
يعتبر الثنائي المستقل ذاتيًا أبطأ في تجميع SQLite من المترجم الذي صممه GCC ، مما يدل على أن LACC يولد بالفعل رمزًا غير فعال إلى حد ما. يعد تحسين الواجهة الخلفية باختيار تعليمات أفضل أولوية ، لذلك نأمل أن تقترب هذه الأرقام في المستقبل.
هذه بعض الموارد المفيدة لبناء مترجم C الذي يستهدف x86_64.
