LLVM IR و Go

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

TL ؛ DR ، لقد كتبنا مكتبة للتفاعل مع LLVM IR على تطبيق Go النقي ، انظر روابط إلى الكود ومثال المشروع.

مثال بسيط على LLVM IR

(أولئك الذين لديهم دراية بـ LLVM IR يمكنهم الانتقال إلى القسم التالي).

LLVM IR هو تمثيل متوسط ​​المستوى يستخدمه إطار تجميع LLVM. يمكنك التفكير في LLVM IR كمجمع مستقل عن النظام الأساسي مع عدد لا حصر له من السجلات المحلية.

عند تصميم برنامج التحويل البرمجي ، هناك ميزة كبيرة في ترجمة لغة المصدر إلى تمثيل وسيط (IR ، تمثيل وسيط) بدلاً من تجميعها في بنية هدف (على سبيل المثال ، x86).


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


وبالتالي ، يتكون المترجمون غالبًا من ثلاثة أجزاء: الواجهة الأمامية والميدلاند والخلفية ، كل واحد منهم يؤدي مهمته الخاصة ، ويقبل المدخلات و / أو يعطي إخراج الأشعة تحت الحمراء.

• Frontend: يجمع لغة المصدر في IR
• Middleland: يحسن IR
• الخلفية: يجمع IR إلى رمز الجهاز

برنامج LLVM IR لتجميع العينات

من أجل الحصول على فكرة عن شكل مجمع LLVM IR ، فكر في البرنامج التالي.

int f(int a, int b) { return a + 2*b; } int main() { return f(10, 20); } 

نحن نستخدم Clang ونجمع الشفرة C أعلاه في مجمع LLVM IR.

 define i32 @f(i32 %a, i32 %b) { ; <label>:0 %1 = mul i32 2, %b %2 = add i32 %a, %1 ret i32 %2 } define i32 @main() { ; <label>:0 %1 = call i32 @f(i32 10, i32 20) ret i32 %1 } 

بالنظر إلى رمز أداة تجميع LLVM IR أعلاه ، يمكننا ملاحظة بعض ميزات LLVM IR الجديرة بالملاحظة ، وهي:

يتم كتابة LLVM IR بشكل ثابت (على سبيل المثال ، تتقاطع أعداد صحيحة 32 بت حسب النوع i32).

المتغيرات المحلية لها نطاق داخل الوظيفة (بمعنى ،٪ 1 ​​في الرئيسي يختلف عن٪ 1 فيf).

تتلقى "السجلات المؤقتة" (بدون تسجيلات) معرفات محلية (على سبيل المثال ،٪ 1 ​​،٪ 2) ، بترتيب تصاعدي ، في كل وظيفة من الوظائف. يمكن لكل وظيفة استخدام عدد لا حصر له من السجلات (لا تقتصر على 32 سجلات للأغراض العامة). يتم تمييز المعرّفات العمومية (مثل ،f) والمعرفات المحلية (مثل٪ a ،٪ 1) ببادئة (@ و٪ ، على التوالي).

تفعل معظم الأوامر ما تتوقعه ، لذلك يقوم mul بالضرب ، وإضافة الإضافة ، إلخ.

تبدأ التعليقات ؛ كما هي العادة في لغات التجميع.

LLMV هيكل مجمع IR

محتويات ملف التجميع LLVM IR هي وحدة نمطية. تحتوي الوحدة النمطية على إعلانات عالية المستوى ، مثل المتغيرات والوظائف العامة.

لا يحتوي إعلان الوظيفة على كتل أساسية ، وتعريف الوظيفة يحتوي على واحد أو أكثر من القطع الأساسية (أي نص دالة).

ويرد أدناه مثال أكثر تفصيلاً لوحدة LLVM IR. بما في ذلك تعريف المتغير العام @ foo وتعريف الدالةf التي تحتوي على ثلاث كتل أساسية (٪ entry و٪ block_1 و٪ block_2).

 ;  ,  32-  21 @foo = global i32 21 ; f  42,   cond ,  0    define i32 @f(i1 %cond) { ;       ,     ;      entry: ;     br    block_1,  %cond ; ,   block_2   . br i1 %cond, label %block_1, label %block_2 ;     ,    ,     block_1: %tmp = load i32, i32* @foo %result = mul i32 %tmp, 2 ret i32 %result ;     ,     ,     block_2: ret i32 0 } 

الوحدة الأساسية

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

الفريق

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

فريق الإنهاء

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

شكل SSA

من الخصائص المهمة للغاية في LLVM IR أنها مكتوبة في نموذج SSA (تعيين أحادي ثابت) ، مما يعني في الأساس أن كل سجل يتم تخصيصه مرة واحدة فقط. تبسط هذه الخاصية التحليل الثابت لدفق البيانات.

لمعالجة المتغيرات التي تم تعيينها أكثر من مرة في التعليمات البرمجية المصدر الأصلي ، يتم استخدام الأمر phi في LLVM IR. يُرجع الأمر phi أساسًا قيمة واحدة من مجموعة من قيم الإدخال ، وفقًا لمسار التنفيذ الذي تم الوصول إليه. وبالتالي ، ترتبط كل قيمة إدخال بكتلة إدخال سابقة.

كمثال ، خذ بعين الاعتبار وظيفة LLVM IR التالية:

 define i32 @f(i32 %a) { ; <label>:0 switch i32 %a, label %default [ i32 42, label %case1 ] case1: %x.1 = mul i32 %a, 2 br label %ret default: %x.2 = mul i32 %a, 3 br label %ret ret: %x.0 = phi i32 [ %x.2, %default ], [ %x.1, %case1 ] ret i32 %x.0 } 

يحاكي أمر phi (يُسمى أحيانًا عقدة phi) في المثال أعلاه تعيينات متعددة باستخدام مجموعة من قيم الإدخال الممكنة ، واحدة لكل مسار ممكن في سلسلة عمليات التنفيذ ، مما يؤدي إلى تعيين متغير. على سبيل المثال ، أحد المسارات المقابلة في دفق البيانات هو كما يلي:



بشكل عام ، عند تطوير برنامج التحويل البرمجي الذي يحول كود المصدر إلى LLVM IR ، يمكن تحويل جميع متغيرات كود المصدر المحلي إلى نموذج SSA ، باستثناء المتغيرات التي يتم أخذ عنوانها من أجلها.

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

LLVM مكتبة الأشعة تحت الحمراء على الذهاب النقي

هناك مكتبتان رئيسيتان للعمل مع LLVM IR في Go:

https://godoc.org/llvm.org/llvm/bindings/go/llvm : روابط LLVM الرسمية للغة Go.
github.com/llir/llvm : مكتبة Go نظيفة للتفاعل مع LLVM IR.

تستخدم روابط LLVM الرسمية للغة Go Cgo لتوفير الوصول إلى واجهات برمجة التطبيقات الغنية والقوية لإطار عمل مترجم LLVM ، في حين أن مشروع llir / llvm مكتوب بالكامل في Go ويستخدم LLVM IR للتفاعل مع إطار عمل LLVM.

تركز هذه المقالة على llir / llvm ، ولكن يمكن تعميمها للعمل مع المكتبات الأخرى.

لماذا تكتب مكتبة جديدة؟

كان الدافع الرئيسي لتطوير مكتبة Go نظيفة للتفاعل مع LLVM IR هو جعل مترجمي الكتابة وأدوات التحليل الثابتة ، والتي تستند إلى إطار تجميع LLVM IR ، وهي مهمة أكثر متعة. تأثر أيضًا بحقيقة أن وقت التحويل البرمجي لمشروع يستند إلى روابط LLVM الرسمية مع Go يمكن أن يكون مهمًا (بفضلaykevl ، مؤلف TinyGo ، أصبح من الممكن الآن تسريع عملية التجميع بسبب الارتباط الديناميكي ، على عكس الإصدار القياسي من LLVM 4).


كان الدافع الكبير الآخر هو محاولة تطوير واجهة برمجة تطبيقات Go من البداية. يتمثل الاختلاف الرئيسي بين واجهات برمجة التطبيقات المرتبطة LLVM لـ Go و llir / llvm في كيفية تصميم قيم LLVM. في مجلدات LLVM لـ Go ، يتم تصميم قيم LLVM كنوع هيكلي ملموس ، والذي يحتوي ، في جوهره ، على جميع الطرق الممكنة لجميع قيم LLVM الممكنة. تشير تجربتي الشخصية باستخدام واجهة برمجة التطبيقات هذه إلى أنه من الصعب معرفة المجموعة الفرعية من الطرق المسموح بها للاتصال بقيمة معينة. على سبيل المثال ، للحصول على شفرة تشغيل التعليمات ، يمكنك استدعاء الأسلوب InstructionOpcode ، وهو أمر سهل الاستخدام. ومع ذلك ، إذا قمت بدلاً من ذلك باستدعاء أسلوب Opcode ، والذي تم تصميمه للحصول على شفرة التشغيل لتعبير ثابت ، فستظهر لك خطأ في وقت التشغيل: "وسيطة cast () لنوع غير متوافق!" (تحويل الوسيطة إلى نوع غير متوافق).

تم تصميم مكتبة llir / llvm للتحقق من الأنواع في وقت الترجمة والتأكد من استخدامها بشكل صحيح مع نظام Go type. يتم نمذجة قيم LLVM في llir / llvm كأنواع واجهة. لا يتيح هذا النهج سوى مجموعة قليلة من الأساليب المتاحة ، وتتقاسمها جميع القيم ، وإذا كنت تريد الوصول إلى طرق أو حقول محددة ، فاستخدم تبديل الكتابة (كما هو موضح في المثال أدناه).

مثال للاستخدام

الآن دعونا نلقي نظرة على بعض الأمثلة لاستخدامات محددة. دعنا نملك مكتبة ، لكن ماذا يجب أن نفعل مع LLVM IR؟

أولاً ، قد نرغب في تحليل LLVM IR الذي تم إنشاؤه بواسطة أداة أخرى ، مثل Clang و opt LLVM opt (اختر نموذج الإدخال أدناه).

ثانياً ، قد نرغب في معالجة LLVM IR وإجراء التحليل الخاص بنا عليه ، أو إجراء تحسينات خاصة بنا ، أو تنفيذ مترجم ، أو مترجم JIT (انظر مثال التحليل أدناه).

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

نموذج إدخال رمز - LLVM IR تحليل

 //       LLVM IR,    //     package main import ( "fmt" "github.com/llir/llvm/asm" ) func main() { //    LLVM IR. m, err := asm.ParseFile("foo.ll") if err != nil { panic(err) } // ,    LLVM IR. // Print LLVM IR module. fmt.Println(m) } 

مثال تحليل - معالجة LLVM IR

 //      LLVM IR     //  Graphviz DOT package main import ( "bytes" "fmt" "io/ioutil" "github.com/llir/llvm/asm" "github.com/llir/llvm/ir" ) func main() { //    LLVM IR. m, err := asm.ParseFile("foo.ll") if err != nil { panic(err) } //    . callgraph := genCallgraph(m) //      Graphviz DOT. if err := ioutil.WriteFile("callgraph.dot", callgraph, 0644); err != nil { panic(err) } } // genCallgraph      Graphviz DOT    LLVM IR func genCallgraph(m *ir.Module) []byte { buf := &bytes.Buffer{} buf.WriteString("digraph {\n") //      for _, f := range m.Funcs { //   caller := f.Ident() fmt.Fprintf(buf, "\t%q\n", caller) //       for _, block := range f.Blocks { //   ,       . for _, inst := range block.Insts { //  .   call. switch inst := inst.(type) { case *ir.InstCall: callee := inst.Callee.Ident() //        . fmt.Fprintf(buf, "\t%q -> %q\n", caller, callee) } } //     switch term := block.Term.(type) { case *ir.TermRet: //  - _ = term } } } buf.WriteString("}") return buf.Bytes() } 

عينة رمز الإخراج - LLVM IR جيل

 //     LLVM IR,    C, //    . // // int abs(int x); // // int seed = 0; // // // ref: https://en.wikipedia.org/wiki/Linear_congruential_generator // // a = 0x15A4E35 // // c = 1 // int rand(void) { // seed = seed*0x15A4E35 + 1; // return abs(seed); // } package main import ( "fmt" "github.com/llir/llvm/ir" "github.com/llir/llvm/ir/constant" "github.com/llir/llvm/ir/types" ) func main() { //      i32 := types.I32 zero := constant.NewInt(i32, 0) a := constant.NewInt(i32, 0x15A4E35) //  PRNG. c := constant.NewInt(i32, 1) //  PRNG. //    LLVM IR. m := ir.NewModule() //         . // // int abs(int x); abs := m.NewFunc("abs", i32, ir.NewParam("x", i32)) //         . // // int seed = 0; seed := m.NewGlobalDef("seed", zero) //        . // // int rand(void) { ... } rand := m.NewFunc("rand", i32) //           `rand`. entry := rand.NewBlock("") //         . tmp1 := entry.NewLoad(seed) tmp2 := entry.NewMul(tmp1, a) tmp3 := entry.NewAdd(tmp2, c) entry.NewStore(tmp3, seed) tmp4 := entry.NewCall(abs, tmp3) entry.NewRet(tmp4) //   LLVM IR  . fmt.Println(m) } 

استنتاج

تم تنفيذ وتطوير llir / llvm وقادته مجموعة من المساهمين الذين لم يكتبوا الكود فحسب ، بل قادوا أيضًا المناقشات وجلسات البرمجة المقترنة والمصححة والمنقحة وأظهروا فضولًا في عملية التعلم.

أحد أصعب أجزاء مشروع llir / llvm هو بناء قواعد EBNF لـ LLVM IR ، تغطي كامل لغة LLVM IR حتى إصدار LLVM 7.0. الصعوبة هنا ليست في العملية نفسها ، ولكن في حقيقة أنه لا توجد قواعد منشورة رسميًا تغطي اللغة بأكملها. لقد حاولت بعض مجتمعات المصادر المفتوحة تحديد قواعد اللغة الرسمية لمجمع LLVM ، لكنها تغطي ، حسب علمنا ، مجموعات فرعية فقط من اللغة.

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

المستقبل رائع ، القرصنة السعيدة!

مراجع

1. فصل مكتوب جيدًا عن LLVM ، كتبه كريس لاتنر ، مؤلف مشروع LLVM الأولي ، في كتاب "هندسة تطبيقات المصادر المفتوحة".

2. يطبق تطبيق لغة باستخدام تعليمي LLVM - غالبًا ما يُسمى أيضًا دليل لغة المشكال - بالتفصيل كيفية تنفيذ لغة برمجة بسيطة مترجمة في LLVM IR. توضح هذه المقالة جميع المراحل الرئيسية لكتابة الواجهة الأمامية ، بما في ذلك محلل معجم ، ومحلل ، وتوليد الكود.

3. بالنسبة لأولئك الذين يرغبون في كتابة مترجم من لغة الإدخال إلى LLVM IR ، يوصى كتاب " Mapping High Level Constructs to LLVM IR ".

هناك مجموعة جيدة من الشرائح هي LLVM ، في Great Detail ، التي تصف مفاهيم LLVM IR المهمة ، وتوفر مقدمة ل LLVM C ++ API ، وتصف بعض مقاطع تحسين LLVM المفيدة للغاية.

روابط Go الرسمية لـ LLVM مناسبة للعديد من المشروعات ، فهي تمثل LLVM C API ، قوية ومستقرة.

إضافة جيدة إلى المنشور مقدمة عن LLVM في Go.