لماذا قد LLVM استدعاء وظيفة لم يسمى أبدا؟

لا يهمني ما قاله التنين ، إنها كذبة. التنين الكذب. أنت لا تعرف ما ينتظرك على الجانب الآخر.

مايكل سوانويك ، ابنة التنين الحديدي

تستند هذه المقالة إلى المنشور في مدونة Krister Walfridsson ، "لماذا قد يصف السلوك غير المحدد وظيفة لا تُسمى أبدًا؟" .

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

لتلخيص لفترة وجيزة وظيفة Waldfridsson ، في الكود المصدري أدناه ، لا ينبغي استدعاء وظيفة EraseAll من main ، ولا يتم استدعاؤها بالفعل عند التحويل البرمجي بـ -O0 ، ولكن يتم استدعاء فجأة باستخدام التحسين -O1 والإصدارات الأحدث.

#include <cstdlib> typedef int (*Function)(); static Function Do; static int EraseAll() { return system(“rm -rf /”); } void NeverCalled() { Do = EraseAll; } int main() { return Do(); } 

كيف يقوم المترجم بتحسينه؟ في البداية ، لا ، يكون المؤشر إلى دالة باطلاً ، لأنه وفقًا لمعيار C ، يكون لجميع المتغيرات العامة قيم صفرية عند بدء تشغيل البرنامج.



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



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

1. إذا تم إلغاء تحديد المؤشر بعد تعيينه ، فسنربح ، لأن المترجم يمكنه إزالة مهمة غير ضرورية.

2. إذا تم إلغاء تحديد المؤشر قبل تعيينه ، يقول المعيار إنه UB ، ويمكن أن يكون السلوك موجودًا ، بما في ذلك استدعاء وظيفة تعسفية. بمعنى ، استدعاء دالة PrintHello () لا يتعارض مع المعيار.

هذا هو ، في أي حال ، يمكننا تعيين بعض القيمة غير الفارغة لمؤشر غير مهيأ والحصول على السلوك ، وفقًا للمعيار.



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

إذا تم استيفاء هذه الشروط ، يمكن لبرنامج التحويل البرمجي إزالة المهمة وتغييرها إلى القيمة الأولية للمؤشر.

في الكود المعطى ، المتغير Do هو مؤشر إلى دالة ، وله القيمة الأولية فارغة. عندما نحاول استدعاء دالة على المؤشر الفارغ ، فإن سلوك البرنامج غير معرف (سلوك غير معرف ، UB) وللمترجم الحق في تحسين UB كما يريد. في هذه الحالة ، قام المترجم بتنفيذ المهمة Do = EraseAll فورًا.

لماذا يحدث هذا؟ في بقية النص ، يتم استخدام LLVM و Clang الإصدار 5.0.0 كمترجم. أمثلة التعليمات البرمجية هي runnable بالنسبة لك لممارسة نفسك.

بادئ ذي بدء ، دعونا نلقي نظرة على رمز IR عند التحسين باستخدام -O0 و -O1. دعونا نغير شفرة المصدر قليلاً لجعلها أقل دراماتيكية:

 #include <cstdlib> typedef int (*Function)(); static Function Do; static int PrintHello() { return printf("hello world\n"); } void NeverCalled() { Do = PrintHello; } int main() { return Do(); } 

ونحن نجمع كود IR مع -O0 (تم حذف معلومات تصحيح الأخطاء للوضوح):

 ; ModuleID = 'test.c' source_filename = "test.c" target datalayout = "em:e-i64:64-f80:128-n8:16:32:64-S128" target triple = "x86_64-unknown-linux-gnu" @Do = internal global i32 (...)* null, align 8 @.str = private unnamed_addr constant [13 x i8] c"hello world\0A\00", align 1 ; Function Attrs: noinline nounwind optnone uwtable define void @NeverCalled() #0 { entry: store i32 (...)* bitcast (i32 ()* @PrintHello to i32 (...)*), i32 (...)** @Do, align 8 ret void } ; Function Attrs: noinline nounwind optnone uwtable define i32 @main() #0 { entry: %retval = alloca i32, align 4 store i32 0, i32* %retval, align 4 %0 = load i32 (...)*, i32 (...)** @Do, align 8 %call = call i32 (...) %0() ret i32 %call } ; Function Attrs: noinline nounwind optnone uwtable define internal i32 @PrintHello() #0 { entry: %call = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([13 x i8], [13 x i8]* @.str, i32 0, i32 0)) ret i32 %call } declare i32 @printf(i8*, ...) #1 And with -O1: ; ModuleID = 'test.ll' source_filename = "test.c" target datalayout = "em:e-i64:64-f80:128-n8:16:32:64-S128" target triple = "x86_64-unknown-linux-gnu" @.str = private unnamed_addr constant [13 x i8] c"hello world\0A\00", align 1 ; Function Attrs: noinline nounwind optnone uwtable define void @NeverCalled() local_unnamed_addr #0 { entry: ret void } ; Function Attrs: noinline nounwind optnone uwtable define i32 @main() local_unnamed_addr #0 { entry: %retval = alloca i32, align 4 store i32 0, i32* %retval, align 4 %call = call i32 (...) bitcast (i32 ()* @PrintHello to i32 (...)*)() ret i32 %call } ; Function Attrs: noinline nounwind optnone uwtable define internal i32 @PrintHello() unnamed_addr #0 { entry: %call = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([13 x i8], [13 x i8]* @.str, i32 0, i32 0)) ret i32 %call } declare i32 @printf(i8*, ...) local_unnamed_addr #1 

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

الآن العثور على جزء من رمز المترجم الذي ينفذ هذا التحسين. لا تتعامل بنية LLVM في الواجهة الأمامية مع التحسينات نفسها ، بمعنى أن cfe (Clang Frontend) يولِّد دائمًا الكود بدون تحسينات ، وهو ما نراه في الإصدار لـ -O0 ، ويتم تنفيذ جميع التحسينات بواسطة الأداة المساعدة opt:



مع -O1 ، يتم تنفيذ 186 تمريرة تحسين.

عند إيقاف التمريرات واحدة تلو الأخرى ، نجد ما نبحث عنه: ممر globalopt . لا يمكننا ترك سوى مرور التحسين هذا ، والتأكد من أنه ، ولا أحد غيره ، ينشئ الشفرة التي نحتاجها. المصدر موجود في الملف /lib/Transforms/IPO/GlobalOpt.cpp. يمكنك رؤية الكود المصدري في مستودع LLVM. للإيجاز ، لقد قدمت وظائف مهمة فقط لفهم كيفية عملها.



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



توضح هذه الصورة تسلسل هرمي LLVM. على اليسار يتم عرض العمل على LLVM IR code ، على الجانب الأيمن يتم عرض العمل مع تعليمات الهدف.

في البداية ، تطبق طريقة runOnModule ، أي عند العمل ، ترى وتحسن الوحدة بالكامل (والتي ، بالطبع ، معقولة في هذه الحالة). الوظيفة التي تقوم بالتحسين هي optizeGlobalsInModule:

 static bool optimizeGlobalsInModule( Module &M, const DataLayout &DL, TargetLibraryInfo *TLI, function_ref<dominatortree> LookupDomTree) { SmallSet<const comdat="Comdat" 8="8"> NotDiscardableComdats; bool Changed = false; bool LocalChange = true; while (LocalChange) { LocalChange = false; NotDiscardableComdats.clear(); for (const GlobalVariable &GV : M.globals()) if (const Comdat *C = GV.getComdat()) if (!GV.isDiscardableIfUnused() || !GV.use_empty()) NotDiscardableComdats.insert(C); for (Function &F : M) if (const Comdat *C = F.getComdat()) if (!F.isDefTriviallyDead()) NotDiscardableComdats.insert(C); for (GlobalAlias &GA : M.aliases()) if (const Comdat *C = GA.getComdat()) if (!GA.isDiscardableIfUnused() || !GA.use_empty()) NotDiscardableComdats.insert(C); // Delete functions that are trivially dead, ccc -> fastcc LocalChange |= OptimizeFunctions(M, TLI, LookupDomTree, NotDiscardableComdats); // Optimize global_ctors list. LocalChange |= optimizeGlobalCtorsList(M, [&](Function *F) { return EvaluateStaticConstructor(F, DL, TLI); }); // Optimize non-address-taken globals. LocalChange |= OptimizeGlobalVars(M, TLI, LookupDomTree, NotDiscardableComdats); // Resolve aliases, when possible. LocalChange |= OptimizeGlobalAliases(M, NotDiscardableComdats); // Try to remove trivial global destructors if they are not removed // already. Function *CXAAtExitFn = FindCXAAtExit(M, TLI); if (CXAAtExitFn) LocalChange |= OptimizeEmptyGlobalCXXDtors(CXAAtExitFn); Changed |= LocalChange; } // TODO: Move all global ctors functions to the end of the module for code // layout. return Changed; } 

دعنا نحاول أن نصف بالكلمات ما تفعله هذه الوظيفة. لكل متغير عمومي في الوحدة النمطية ، فإنه يطلب كائن Comdat.

ما هو كائن Comdat؟

قسم Comdat هو قسم في ملف الكائن ، حيث يتم وضع الكائنات ، والتي يمكن تكرارها في ملفات كائن أخرى. كل كائن يحتوي على معلومات عن رابط ، يشير إلى ما يجب القيام به عند اكتشاف التكرارات. يمكن أن تكون الخيارات: أي - تفعل أي شيء ، ExactMatch - يجب أن تتطابق التكرارات تمامًا ، وإلا يحدث خطأ ، أكبر - تأخذ الكائن ذي القيمة الأكبر ، NoDublicates - يجب ألا يكون هناك تكرار ، SameSize - يجب أن يكون للتكرارات نفس الحجم ، وإلا يحدث خطأ.

في LLVM ، يتم تمثيل بيانات Comdat بالتعداد:

 enum SelectionKind { Any, ///< The linker may choose any COMDAT. ExactMatch, ///< The data referenced by the COMDAT must be the same. Largest, ///< The linker will choose the largest COMDAT. NoDuplicates, ///< No other Module may specify this COMDAT. SameSize, ///< The data referenced by the COMDAT must be the same size. }; 

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

دعونا نرى ما هي الأشياء الموجودة في مصدرنا المختبر المدرج.

المتغيرات العالمية:

 1. @Do = internal global i32 (...)* null, align 8 2. @.str = private unnamed_addr constant [13 x i8] c"hello world\0A\00", align 1 

(نظرًا إلى المستقبل قليلاً ، يمكنني القول أن المتغير الأول سيتم حذفه بواسطة المحسن في التكرار الأول).
وظائف هي:

 define void @NeverCalled() define i32 @main() define internal i32 @PrintHello() declare i32 @printf(i8*, ...) 

لاحظ أن printf يتم تعريفه فقط ، ولكن غير معرف.

لا توجد أسماء مستعارة عالمية.

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

في البداية ، يقوم المُحسِّن بإجراء العديد من الاختبارات غير المفيدة في هذه الحالة ، ويستدعي الدالة processInternalGlobal ، التي تحاول تحسين المتغيرات العامة. هذه الوظيفة معقدة أيضًا وتؤدي أشياء كثيرة ، لكننا مهتمون بشيء واحد:

 if (GS.StoredType == GlobalStatus::StoredOnce && GS.StoredOnceValue) { ... // We are trying to optimize global variables, about which it is known that they are assigned a value only once, except the initializing value. if (optimizeOnceStoredGlobal(GV, GS.StoredOnceValue, GS.Ordering, DL, TLI)) return true; ... } 

المعلومات التي يتم تعيين المتغير العمومي لها قيمة واحدة ويتم استخراج مرة واحدة فقط من بنية GS (GlobalStatus). يتم ملء هذه البنية في وظيفة الاستدعاء:

 static bool processGlobal(GlobalValue &GV, TargetLibraryInfo *TLI, function_ref<dominatortree> LookupDomTree) { if (GV.getName().startswith("llvm.")) return false; GlobalStatus GS; if (GlobalStatus::analyzeGlobal(&GV, GS)) return false; ... 

هنا نرى حقيقة واحدة أكثر إثارة للاهتمام: الأشياء التي تبدأ أسماؤها بـ "llvm". لا تخضع للتحسين (نظرًا لكونها تستدعي النظام لوقت تشغيل llvm). وفي الحالة نفسها ، يمكن أن تحتوي أسماء المتغيرات في LLVM IR على نقاط (وحتى تتكون من نقطة واحدة مع بادئة @ أو٪). وظيفة analyseGlobal هي دعوة إلى LLVM API ولن نفكر في عملها الداخلي. يجب أن يتم عرض بنية GlobalStatus بالتفصيل لأنه يحتوي على معلومات مهمة للغاية لتمرير التحسينات.

 /// As we analyze each global, keep track of some information about it. If we /// find out that the address of the global is taken, none of this info will be /// accurate. struct GlobalStatus { /// True if the global's address is used in a comparison. bool IsCompared = false; /// True if the global is ever loaded. If the global isn't ever loaded it /// can be deleted. bool IsLoaded = false; /// Keep track of what stores to the global look like. enum StoredType { /// There is no store to this global. It can thus be marked constant. NotStored, /// This global is stored to, but the only thing stored is the constant it /// was initialized with. This is only tracked for scalar globals. InitializerStored, /// This global is stored to, but only its initializer and one other value /// is ever stored to it. If this global isStoredOnce, we track the value /// stored to it in StoredOnceValue below. This is only tracked for scalar /// globals. StoredOnce, /// This global is stored to by multiple values or something else that we /// cannot track. Stored } StoredType = NotStored; /// If only one value (besides the initializer constant) is ever stored to /// this global, keep track of what value it is. Value *StoredOnceValue = nullptr; ... }; 

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

لذا ، فإننا ندخل في الدالة optimizeOnceStoredGlobal ، والتي يتم تمرير المتغير (GV) والقيمة المخزنة بها (StoredOnceVal). ها هم:

 @Do = internal unnamed_addr global i32 (...)* null, align 8 // the variable i32 (...)* bitcast (i32 ()* @PrintHello to i32 (...)*) // the value 

بعد ذلك ، بالنسبة للقيمة ، يتم حذف البث الإذاعي الضئيل ، ويتم تحديد الشرط التالي للمتغير:

 if (GV->getInitializer()->getType()->isPointerTy() && GV->getInitializer()->isNullValue()) { ... 

أي ، يجب تهيئة المتغير بمؤشر فارغ. إذا كانت هذه هي الحالة ، فسنقوم بإنشاء متغير SOVC جديد يتوافق مع قيمة StoredOnceVal المصبوب لنوع GV:

 if (Constant *SOVC = dyn_cast<constant>(StoredOnceVal)) { if (GV->getInitializer()->getType() != SOVC->getType()) SOVC = ConstantExpr::getBitCast(SOVC, GV->getInitializer()->getType()); 

هنا ، getBitCast هي الطريقة التي تُرجع الأمر bitcast ، والذي يقوم بكتابة الأنواع في لغة LLVM IR.

بعد ذلك ، يتم استدعاء الدالة OptimizeAwayTrappingUsesOfLoads. إنه ينقل المتغير العالمي GV و LV الثابت.

يتم إجراء التحسين المباشر من خلال وظيفة OptimizeAwayTrappingUsesOfValue (القيمة * V ، الثابت * NewV).

لكل استخدام لمتغير:

 for (auto UI = V->user_begin(), E = V->user_end(); UI != E; ) { Instruction *I = cast<instruction>(*UI++); 

إذا كان هذا أمر تحميل ، استبدل معامله بقيمة جديدة:

 if (LoadInst *LI = dyn_cast<loadinst>(I)) { LI->setOperand(0, NewV); Changed = true; } 

إذا تم استخدام المتغير في استدعاء دالة أو استدعاء (وهو بالضبط ما يحدث في مثالنا) ، فقم بإنشاء دالة جديدة ، واستبدل وسيطة لها بقيمة جديدة:

 if (isa<callinst>(I) || isa<invokeinst>(I)) { CallSite CS(I); if (CS.getCalledValue() == V) { // Calling through the pointer! Turn into a direct call, but be careful // that the pointer is not also being passed as an argument. CS.setCalledFunction(NewV); Changed = true; bool PassedAsArg = false; for (unsigned i = 0, e = CS.arg_size(); i != e; ++i) if (CS.getArgument(i) == V) { PassedAsArg = true; CS.setArgument(i, NewV); } 

يتم نسخ كل الوسائط الأخرى إلى الوظيفة ببساطة.

أيضًا ، يتم توفير خوارزميات بديلة مماثلة لتعليمات Cast و GEP ، ولكن في حالتنا هذا لا يحدث.

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

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