التنميط رمز مع LLVM

لعنة اللا حتمية

محاولتي الأولى لكتابة مقطع LLVM - أنا أحب هذه السذاجة

واجهت مؤخرًا مشكلة مثيرة للاهتمام - كنت بحاجة إلى طريقة حتمية وعبر الأنظمة الأساسية لتحديد وقت تشغيل شفرة C ++. أعني بكلمة "حتمية" أنه سيتم تنفيذ نفس الرمز لنفس عدد الوحدات الزمنية. عبر النظام الأساسي ، أفهم أن نفس الرمز تحت Windows وتحت Ubuntu سيتم تشغيله لنفس عدد الوحدات الزمنية.

بطبيعة الحال ، لا يفي قياس الوقت على وحدة المعالجة المركزية بهذه الشروط. يختلف رمز الجهاز حسب البنية ونظام التشغيل ، وسيستغرق تنفيذ نفس الرمز وقتًا مختلفًا. حتى على نفس الجهاز ، ستلعب عوامل مثل أخطاء التخزين المؤقت دورًا كبيرًا - بما يكفي لتشويه نتائج القياس لوقت تنفيذ نفس الرمز. كنت بحاجة إلى شيء أكثر ذكاء ...

الدافع

لقد واجهت هذه المشكلة عندما كنت أعمل على مشروعي ، حرف الرمز. Code Character هي مسابقة الذكاء الاصطناعي على الإنترنت حيث يكتب المشاركون الروبوتات للسيطرة على الجيش في استراتيجية قائمة على الأدوار. أردت تحديد مقدار الشفرة التي يمكن للمشارك تنفيذها في خطوة واحدة.

فكرتي الأولى كانت ببساطة قياس وقت تنفيذ الكود ، ولكن ، كما نرى ، هذه الإستراتيجية ليست حتمية ، وسيحصل المشترك الذي أرسل نفس الكود مرتين على نتائج مختلفة تمامًا. في الواقع ، حاولنا تنفيذ هذا الحل ، وتغيرت النتائج كثيرًا بحيث يمكن للمشارك الفوز أو الخسارة بنفس الرمز. ستكون النتيجة عشوائية تمامًا ، وتجاهلنا فكرة قياس الوقت.

LLVM Bytecode

نظرًا لأنه لا يمكننا قياس الوقت ، قررنا بدلاً من ذلك قياس عدد التعليمات المنفذة. لذلك ، نحن بحاجة إلى صياغة رمز المشارك. إذا لم تكن على دراية بهذا المصطلح ، فهذا يضيف بعض التعليمات البرمجية إلى التطبيق ، من أجل مراقبة بعض المعلمات ، على سبيل المثال ، استخدام وحدة المعالجة المركزية أو وقت التشغيل. بطبيعة الحال ، لا نتوقع من المشاركين القيام بذلك بأنفسهم ، يجب علينا أتمتة العملية.

أردنا تجنب التكاليف العامة لأدوات وقت التشغيل عند العمل على الخادم الخاص بنا ، وبالتالي فإن شيئًا مثل أداة PIN غير مناسب لأغراضنا. بدلاً من ذلك ، قررنا توجيه تعليمات المشاركين مباشرةً من أجل حساب عدد التعليمات التي سيتم تنفيذها. بدلاً من ثنائيات الأدوات (رمز الآلة) ، قررنا استخدام Clang لتجميع الشفرة والأداة LLVM bytecode.

إذا كنت جديدًا في LLVM ، فهي عبارة عن مجموعة من تقنيات المترجم المعيارية والقابلة لإعادة الاستخدام وتقنيات سلسلة الأدوات. أحد المشاريع الرئيسية هو LLVM IR والخلفية. بعبارات بسيطة ، تم تطوير تمثيل متوسط ​​تقوم فيه واجهة أمامية مترجمة بتجميع التعليمات البرمجية. ثم يتم تجميع هذا الرمز ، LLVM IR ، في كود الجهاز بواسطة الواجهة الخلفية LLVM. وبالتالي ، إذا كنت تقوم بإنشاء لغة جديدة ، يمكنك أن تقرر السماح لـ LLVM بدعم إنشاء كود الجهاز وتحسينه ، وكتابة واجهة أمامية لتحويل لغتك إلى LLVM IR.


يحول Clang كود C ++ إلى LLVM IR ، والذي يتم تحويله بعد ذلك إلى رمز الجهاز بواسطة الواجهة الخلفية LLVM.

Clang هي الواجهة الأمامية لـ LLVM. نظرًا لأننا نحتاج إلى طريقة عبر النظام الأساسي لقياس الشفرة ، فلا يمكننا وضع رمز ثنائي. LLVM IR ، مع ذلك ، مستقل عن النظام الأساسي ، حيث إنه مجرد تمثيل وسيط للكود. إن استخدام رمز IR مع مكتبات LLVM هو حل بسيط عبر الأنظمة الأساسية.

الحل

من الواضح أن عدد تعليمات LLVM IR البسيط غير مناسب ، لأننا نحتاج إلى عدد التعليمات التي سيتم تنفيذها بالفعل ، وليس فقط عدد التعليمات في التعليمات البرمجية. في النهاية ، قمنا بتطوير خوارزمية بسيطة تعتمد على مفهوم الكتل الأساسية للتعليمات البرمجية.

الوحدة الأساسية هي مجموعة من التعليمات التي يمكن أن تكون فيها التعليمات الأولى هي نقطة الإدخال فقط ، ويمكن أن تكون التعليمات الأخيرة فقط هي نقطة الإخراج. ( أي انتقالات داخل الكتلة الأساسية ممنوعة أيضًا - تقريبًا. ) لفهم ذلك ، حاول تقسيم الرمز إلى أجزاء يمكن أن تكون فيها تعليمات الفرع (الانتقالات والحلقات والإرجاع) هي الأخيرة فقط في المجموعة ، والإدخال إلى الكتلة (التعليمات الأولى في وظيفة ، حلقة أو كتلة if / else) ممكنة فقط في التعليمات الأولى. والنتيجة هي مجموعة من الكتل الأساسية - كتل من التعليمات البرمجية التسلسلية التي يتم تنفيذها بشكل تسلسلي ، دون تحديد التعليمات التي سيتم تنفيذها بعد ذلك.

لماذا لا نجربه الآن؟ هذا هو مقتطف من التعليمات البرمجية المقدمة من قبل مساهم حرف الرمز:

// Make the soldiers who aren't patrolling attack the enemy for (int i = NUM_SOLDIERS / 2; i < NUM_SOLDIERS; ++i) { auto &soldier = state.soldiers[i]; if (soldier.hp == 0) // If this soldier is dead, skip it continue; for (auto enemy_soldier : state.enemy_soldiers) { if (enemy_soldier.hp != 0) { // Ensure your prospective target has // not already been slain soldier.soldier_target = enemy_soldier.id; break; } } } 

رابط Github: https://gist.github.com/JHurricane96/8c9c3a45ec5e969de4d9fecb47ebef69#file-player_code-cpp

باستخدام حقيقة أن الوحدة الأساسية لديها نقطة إدخال واحدة فقط (التعليمات الأولى) ، يمكننا تقسيم هذا الجزء إلى الوحدات الأساسية التالية:

 //-------------------------------- BB 1 ---------------------------------- for (int i = NUM_SOLDIERS / 2; i < NUM_SOLDIERS; ++i) { //-------------------------------- BB 2 ---------------------------------- auto &soldier = state.soldiers[i]; if (soldier.hp == 0) //-------------------------------- BB 3 ---------------------------------- continue; //-------------------------------- BB 4 ---------------------------------- for (auto enemy_soldier : state.enemy_soldiers) { //-------------------------------- BB 5 ---------------------------------- if (enemy_soldier.hp != 0) { //-------------------------------- BB 6 ---------------------------------- soldier.soldier_target = enemy_soldier.id; break; //-------------------------------- BB 7 ---------------------------------- } } } 

جيث لينك
ساعدنا هذا على فهم كيفية عمل الكتل الأساسية ، فلنلقِ نظرة الآن على هذه الخوارزمية في LLVM IR:

 ; <label>:140: ; preds = %181, %139 %141 = load i32, i32* %19, align 4 %142 = sext i32 %141 to i64 %143 = icmp slt i64 %142, 20 br i1 %143, label %144, label %184 ; <label>:144: ; preds = %140 %145 = getelementptr inbounds %"struct.player_state::State", %"struct.player_state::State"* %2, i32 0, i32 1 %146 = load i32, i32* %19, align 4 %147 = sext i32 %146 to i64 %148 = call dereferenceable(72) %"struct.player_state::Soldier"* @_ZNSt5arrayIN12player_state7SoldierELm20EEixEm( %"struct.std::array.10"* %145, i64 %147) #3 store %"struct.player_state::Soldier"* %148, %"struct.player_state::Soldier"** %20, align 8 %149 = load %"struct.player_state::Soldier"*, %"struct.player_state::Soldier"** %20, align 8 %150 = getelementptr inbounds %"struct.player_state::Soldier", %"struct.player_state::Soldier"* %149, i32 0, i32 2 %151 = load i64, i64* %150, align 8 %152 = icmp eq i64 %151, 0 br i1 %152, label %153, label %154 ; <label>:153: ; preds = %144 br label %181 

جيث لينك

إذا نظرت بعناية ، ستلاحظ أن جزء التعليمات البرمجية أعلاه هو أول ثلاث كتل من جزء كود C ++ المترجمة في LLVM IR (كل سطر هو بداية الكتلة الأساسية).

لدى LLVM مكتبات تسمح لنا بكتابة "تصاريح" - كود يمكنه تحويل LLVM IR. تسمح لنا واجهة برمجة التطبيقات LLVM بقراءة وتحليل LLVM IR بسهولة من خلال التكرار من خلال الوحدات والوظائف والكتل الأساسية وتعديل LLVM IR قبل تجميعها في رمز الجهاز.

الآن بعد أن أصبح لدينا الكتل الأساسية وواجهة برمجة التطبيقات LLVM ، أصبح من السهل حساب عدد الإرشادات التي سيتم تنفيذها باستخدام مثل هذه الخوارزمية البسيطة:

1. نكتب الدالة IncrementCount ، التي تأخذ عددًا صحيحًا وتزيد من عدد صحيح ثابت بهذه القيمة ، في كل مرة يتم استدعاؤها. يجب أن يكون مرتبطًا بكود العضو.
2. نقوم بالتكرارات على جميع الكتل الأساسية. لكل وحدة قاعدة ، نفذ الخطوتين 3 و 4.
3. نجد n - عدد التعليمات في هذه الوحدة الأساسية.
4. نقوم بإدراج الاستدعاء للدالة IncrementCount قبل آخر تعليمات للوحدة الأساسية ، مع الوسيطة n.
5. العدد الصحيح الثابت الذي يعمل معه IncrementCount سيكون عداد التعليمات بعد تنفيذ الكود. يمكن حفظه في مكان ما ثم فحصه.

تعمل الأشعة تحت الحمراء المجهزة لدينا على النحو التالي:

 ; <label>:140: ; preds = %181, %139 %141 = load i32, i32* %19, align 4 %142 = sext i32 %141 to i64 %143 = icmp slt i64 %142, 20 call void @_Z14IncrementCountm(i32 4) br i1 %143, label %144, label %184 ; <label>:144: ; preds = %140 %145 = getelementptr inbounds %"struct.player_state::State", %"struct.player_state::State"* %2, i32 0, i32 1 %146 = load i32, i32* %19, align 4 %147 = sext i32 %146 to i64 %148 = call dereferenceable(72) %"struct.player_state::Soldier"* @_ZNSt5arrayIN12player_state7SoldierELm20EEixEm( %"struct.std::array.10"* %145, i64 %147) #3 store %"struct.player_state::Soldier"* %148, %"struct.player_state::Soldier"** %20, align 8 %149 = load %"struct.player_state::Soldier"*, %"struct.player_state::Soldier"** %20, align 8 %150 = getelementptr inbounds %"struct.player_state::Soldier", %"struct.player_state::Soldier"* %149, i32 0, i32 2 %151 = load i64, i64* %150, align 8 %152 = icmp eq i64 %151, 0 call void @_Z14IncrementCountm(i32 10) br i1 %152, label %153, label %154 ; <label>:153: ; preds = %144 call void @_Z14IncrementCountm(i32 1) br label %181 

جيث لينك

كما نرى ، يتم إجراء مكالمة IncrementCount في نهاية كل كتلة أساسية ، قبل العبارة الأخيرة مباشرةً. باستخدام العدد الثابت الذي يعمل معه IncrementCount ، يمكننا الحصول على عدد التعليمات في نهاية حركة كل مشارك. هذه الطريقة حتمية وعبر منصة ، كما يتم ضمان نفس رمز المصدر لإنشاء نفس LLVM IR إذا استخدمنا نفس الإصدار من المترجم ونفس العلامات.

الخلاصة

التنميط الشفري ليس شيئًا بسيطًا كما اعتقدت ذات مرة. في عملية العمل على مثل هذه المهمة البسيطة نسبيًا ، تعرفت على كيفية عمل المترجم وكيفية كتابة تصاريح LLVM. إذا كنت مهتمًا بإنشاء رمز وتريد كتابة مقاطعك الخاصة ، فإن LLVM لديها دليل للمبتدئين . هناك أيضًا مقالة مدونة رائعة اعتدت على كتابة المقطع الخاص بي. نظرًا لأن LLVM API غير متوافق مع الإصدارات السابقة بين الإصدارات الرئيسية ، انتبه إلى إصدار LLVM الذي تستخدمه.

يمكنك الحصول على الكود المصدري هنا .