LLVM من حيث الذهاب

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

المثال الأول

الوظيفة الأولى التي سأقوم بتحليلها هنا هي آلية بسيطة لإضافة أرقام:

func myAdd(a, b int) int{    return a + b } 

هذه الوظيفة بسيطة للغاية ، وربما ليس من السهل عدم الخروج بها. إنه يترجم إلى رمز Go SSA التالي:

 func myAdd(a int, b int) int: entry:   t0 = a + b                                                    int   return t0 

باستخدام هذا التمثيل للوظيفة ، توضع تلميحات حول أنواع البيانات على اليمين ، وفي معظم الحالات يمكنك تجاهلها.

يتيح لك هذا المثال الصغير بالفعل رؤية جوهر جانب واحد من SSA. وهي ، عند تحويل الشفرة إلى نموذج SSA ، ينقسم كل تعبير إلى الأجزاء الأولية التي يتكون منها. في حالتنا ، return a + b أمر return a + b ، في الواقع ، عمليتين: إضافة رقمين وإرجاع النتيجة.

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

يمكن تحويل رمز الدخول إلى SSA بسهولة إلى LLVM IR:

 define i64 @myAdd(i64 %a, i64 %b) { entry: %0 = add i64 %a, %b ret i64 %0 } 

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

إحدى ميزات هذا الرمز التي تحتاج إلى الانتباه إليها هي أن قرار تمثيل النوع Go int ، والذي يمكن تمثيله بقيمة 32 بت أو 64 بت ، اعتمادًا على المترجم والغرض من الترجمة ، يتم اتخاذه عند إنشاء LLVM كود الأشعة تحت الحمراء. هذا أحد الأسباب العديدة التي تجعل LLVM IR code غير مستقل عن النظام الأساسي. لا يمكن ببساطة أخذ مثل هذه الشفرة التي تم إنشاؤها لنظام أساسي واحد وتجميعها لمنصة أخرى (إلا إذا كنت تتناول هذه المهمة بحذر شديد ).

ومن النقاط المهمة الأخرى الجديرة بالملاحظة أن النوع i64 ليس عددًا صحيحًا موقَّعًا: إنه محايد من حيث تمثيل علامة الرقم. بناءً على التعليمات ، يمكن أن يمثل كل من الأرقام الموقعة والأرقام غير الموقعة. في حالة تمثيل عملية الإضافة ، لا يلعب هذا دورًا ، لذلك لا يوجد فرق في التعامل مع الأرقام مع أو بدون علامة. هنا ، أود أن أشير إلى أنه في C يؤدي تجاوز سعة عدد صحيح موقّع إلى سلوك غير محدد ، وبالتالي ، تضيف الواجهة الأمامية Clang علامة nsw (بدون غلاف موقّع) إلى العملية ، مما يشير إلى LLVM أنه يمكن المضي قدمًا من الافتراض بأنه مع إضافة أبدا يحدث تجاوز.

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

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

المثال الثاني

المثال التالي ، الذي سنبحثه ، سيكون أكثر تعقيدًا بعض الشيء. أي ، نحن نتحدث عن دالة تلخص شريحة الأعداد الصحيحة:

 func sum(numbers []int) int {   n := 0   for i := 0; i < len(numbers); i++ {       n += numbers[i]   }   return n } 

يتم تحويل هذا الرمز إلى رمز Go SSA التالي:

 func sum(numbers []int) int: entry:   jump for.loop for.loop:   t0 = phi [entry: 0:int, for.body: t6] #n                       int   t1 = phi [entry: 0:int, for.body: t7] #i                       int   t2 = len(numbers)                                              int   t3 = t1 < t2                                                  bool   if t3 goto for.body else for.done for.body:   t4 = &numbers[t1]                                             *int   t5 = *t4                                                       int   t6 = t0 + t5                                                   int   t7 = t1 + 1:int                                                int   jump for.loop for.done:   return t0 

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

في الواقع ، هنا يمكنك الانتباه إلى حقيقة أن البرنامج لا ينقسم إلى كتل باستخدام الأقواس المتعرجة (كما هو الحال في لغات عائلة C). يتم تقسيمها بواسطة التسميات ، التي تشبه لغات التجميع ، ويتم تقديمها في شكل كتل أساسية. في SSA ، الكتل الأساسية عبارة عن سلاسل متتالية من التعليمات البرمجية تبدأ بالتسمية وتنتهي بتعليمات لإكمال الكتلة الأساسية ، على سبيل المثال ، return jump .

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

يتجاوز SSA التقييد الخاص بمهمة واحدة من القيم المتغيرة باستخدام تعليمة phi (يتم أخذ اسمه من الأبجدية اليونانية). والحقيقة هي أنه من أجل تشكيل SSA - تمثيل الكود للغات مثل C ، عليك اللجوء إلى بعض الحيل. نتيجة استدعاء هذه التعليمات هي القيمة الحالية للمتغير ( i أو n ) ، ويتم استخدام قائمة الكتل الأساسية كمعلمات لها. على سبيل المثال ، ضع في الاعتبار هذه التعليمات:

 t0 = phi [entry: 0:int, for.body: t6] #n 

يكون معناها كما يلي: إذا كانت الكتلة الأساسية السابقة عبارة عن كتلة entry (إدخال) ، فإن t0 تكون ثابتة 0 ، وإذا كانت الكتلة الأساسية السابقة for.body ، فأنت بحاجة إلى أخذ القيمة t6 من هذه الكتلة. قد يبدو كل هذا غامضًا ، لكن بفضل هذه الآلية ، يتم ضمان SSA. من وجهة نظر الإنسان ، كل هذا يعقد فهم الكود ، ولكن حقيقة أن كل قيمة يتم تخصيصها مرة واحدة فقط يبسط كثيرا من التحسينات.

لاحظ أنك إذا كنت تكتب المترجم الخاص بك ، فإنك عادة لا تحتاج إلى التعامل مع مثل هذه الأشياء. حتى Clang لا تنشئ كل هذه التعليمات ، فهي تستخدم آلية alloca (تشبه العمل مع المتغيرات المحلية العادية). بعد ذلك ، عند إجراء تمرير تحسين LLVM ، يسمى mem2reg ، يتم تحويل إرشادات تخصيص إلى نموذج SSA. TinyGo ، ومع ذلك ، يتلقى مدخلات من Go SSA ، والتي ، مريح ، تم بالفعل تحويلها إلى نموذج SSA.

هناك ابتكار آخر لهذه القطعة من الشفرة الوسيطة وهو أن الوصول إلى عناصر الشريحة حسب الفهرس يتم تقديمه في شكل عملية حساب العنوان وعملية إلغاء تأشير المؤشر الذي تم الحصول عليه. هنا يمكنك أن ترى الإضافة المباشرة للثوابت إلى كود IR (على سبيل المثال - 1:int ). في المثال مع الدالة myAdd لم يتم استخدام هذا. الآن وبعد أن اكتشفنا هذه الميزات ، سنلقي نظرة على ما سيتحول إليه هذا الرمز عند تحويله إلى نموذج LLVM IR:

 define i64 @sum(i64* %ptr, i64 %len, i64 %cap) { entry: br label %for.loop for.loop:                                         ; preds = %for.body, %entry %0 = phi i64 [ 0, %entry ], [ %5, %deref.next ] %1 = phi i64 [ 0, %entry ], [ %6, %deref.next ] %2 = icmp slt i64 %1, %len br i1 %2, label %for.body, label %for.done for.body:                                         ; preds = %for.loop %3 = getelementptr i64, i64* %ptr, i64 %1 %4 = load i64, i64* %3 %5 = add i64 %0, %4 %6 = add i64 %1, 1 br label %for.loop for.done:                                         ; preds = %for.loop ret i64 %0 } 

هنا ، كما كان من قبل ، يمكننا أن نرى نفس البنية ، والتي تشمل الإنشاءات النحوية الأخرى. على سبيل المثال ، في مكالمات phi ، يتم تبديل القيم والتسميات. ومع ذلك ، هناك أيضا شيء يستحق إيلاء اهتمام خاص ل.

بالنسبة للمبتدئين ، هنا يمكنك رؤية توقيع مختلف تمامًا للوظيفة. LLVM لا يدعم الشرائح ، ونتيجة لذلك ، في شكل التحسين ، قام برنامج التحويل البرمجي TinyGo ، الذي أنشأ هذا الكود الوسيط ، بتقسيم وصف بنية البيانات هذه إلى أجزاء. يمكن أن يمثل ثلاثة عناصر شريحة ( ptr و len و cap ) كهيكل (struct) ، لكن تقديمها ككيانات منفصلة ثلاث تسمح ببعض التحسينات. قد يقدم المترجمون الآخرون الشريحة بطريقة أخرى ، ويعتمد ذلك على اصطلاحات استدعاء وظائف النظام الأساسي الهدف.

ميزة أخرى مثيرة للاهتمام في هذا الرمز هي استخدام getelementptr (غالبًا ما تسمى GEP باختصار).

يعمل هذا التعليمات مع المؤشرات ويستخدم للحصول على مؤشر لعنصر شريحة. على سبيل المثال ، دعنا نقارن ذلك بالكود التالي المكتوب بلغة C:

 int* sliceptr(int *ptr, int index) {   return &ptr[index]; } 

أو مع ما يعادلها التالية لهذا:

 int* sliceptr(int *ptr, int index) {   return ptr + index; } 

الشيء الأكثر أهمية هنا هو أن العبارة getelementptr تؤدي عمليات dereference. يقوم فقط بحساب مؤشر جديد بناءً على المؤشر الموجود. يمكن تفسيره على أنه mul add على مستوى الأجهزة. يمكن الاطلاع على تفاصيل تعليمات GEP هنا .

ميزة أخرى مثيرة للاهتمام في هذا الكود الوسيط هي استخدام تعليمة icmp . هذا تعليمة عامة الغرض تستخدم لتنفيذ مقارنات عدد صحيح. تكون نتيجة هذه التعليمات دائمًا قيمة من النوع i1 - قيمة منطقية. في هذه الحالة ، يتم إجراء مقارنة باستخدام الكلمة المفتاحية slt (الموقعة أقل من) ، لأننا نقارن رقمين سبق int بالنوع int . إذا قمنا بمقارنة اثنين من الأعداد الصحيحة غير الموقعة ، icmp ، وستكون الكلمة الأساسية المستخدمة في المقارنة هي ult . لمقارنة أرقام fcmp العائمة ، يتم استخدام تعليمة أخرى ، fcmp ، والتي تعمل بطريقة مماثلة.

النتائج

أعتقد أنه في هذه المقالة درست أهم ميزات LLVM IR. بالطبع ، لا يزال هناك الكثير من الأشياء. على وجه الخصوص ، قد يحتوي التمثيل الوسيط للرمز على الكثير من التعليقات التوضيحية ، مما يسمح بمراعاة بعض ميزات التحسين المعروفة للمترجم أثناء تصاريح التحسين التي لا يمكن التعبير عنها في IR بأي طريقة أخرى. على سبيل المثال ، هذه هي العلامة الداخلية لتعليمات inbounds ، أو nuw nsw و nuw ، والتي يمكن إضافتها إلى عبارة add . ينطبق الأمر نفسه على الكلمة الأساسية private ، والتي تشير إلى المُحسِّن أن الوظيفة المحددة عليه لن يتم الرجوع إليها من خارج وحدة الترجمة الحالية. يتيح لك ذلك إجراء العديد من عمليات تحسين interprocedural المثيرة للاهتمام ، مثل التخلص من الوسائط غير المستخدمة.

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

أعزائي القراء! هل تستخدم LLVM؟