LLVM من منظور Go

إن تطوير المترجم مهمة صعبة للغاية. ولكن، لحسن الحظ، مع تطوير مشاريع مثل LLVM، تم تبسيط حل هذه المشكلة إلى حد كبير، مما يسمح حتى لمبرمج واحد بإنشاء لغة جديدة قريبة في الأداء من لغة C. إن العمل مع LLVM معقد بسبب حقيقة أن هذا يتم تمثيل النظام بكمية هائلة من التعليمات البرمجية، ومجهزة بالقليل من الوثائق. من أجل محاولة تصحيح هذا النقص، سيقوم مؤلف المادة، التي ننشر ترجمتها اليوم، بإظهار أمثلة على التعليمات البرمجية المكتوبة في Go وإظهار كيفية ترجمتها لأول مرة إلى اذهب إلى جنوب أفريقيا، ثم في LLVM IR باستخدام المترجم تينيغو. تم تعديل كود 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في الواقع يمثل عمليتين: إضافة رقمين وإرجاع النتيجة.

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

يتحول رمز Go 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 بإنشاء رمز IR. هذا هو أحد الأسباب العديدة التي تجعل كود LLVM IR ليس مستقلاً عن النظام الأساسي، كما يعتقد الكثير من الناس. مثل هذه التعليمات البرمجية، التي تم إنشاؤها لمنصة واحدة، لا يمكن أخذها وتجميعها ببساطة لمنصة أخرى (إلا إذا كنت مناسبًا لحل هذه المشكلة بحذر شديد).

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

قد يكون هذا مهمًا لبعض التحسينات. على سبيل المثال، إضافة قيمتين 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 اختصار لـ Static Single Assignment. هذا هو تمثيل وسيط للتعليمات البرمجية المستخدمة من قبل المترجمين، حيث يتم تعيين قيمة لكل متغير مرة واحدة فقط. يعد هذا أمرًا رائعًا للتعبير عن وظائف بسيطة مثل وظيفتنا 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 لا يصدر كل هذه التعليمات phi، ويستخدم آلية alloca (يشبه العمل مع المتغيرات المحلية العادية). ثم، عند تشغيل ممر تحسين LLVM يسمى mem2reg، تعليمات alloca تحويلها إلى نموذج 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) كبنية (بنية)، ولكن تمثيلها كثلاثة كيانات منفصلة يسمح ببعض التحسينات. قد يقوم المترجمون الآخرون بتمثيل الشريحة بطرق أخرى، اعتمادًا على اصطلاحات الاتصال الخاصة بوظائف النظام الأساسي المستهدف.

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

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

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

أو بالمعادل التالي لذلك:

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

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

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

نتائج

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

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

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

المصدر: www.habr.com