क्लैंग कैसे एक समारोह को संकलित करता है

मैंने एक लेख लिखने की योजना बनाई है कि कैसे एलएलवीएम एक फ़ंक्शन का अनुकूलन करता है, लेकिन सबसे पहले आपको यह लिखना होगा कि क्लैंग एलएलवीएम में सी या सी ++ का अनुवाद कैसे करता है।




क्लैंग की गहराई में गोता लगाने के बिना उच्च-स्तरीय पहलुओं पर विचार करें। मैं इस बात पर ध्यान देना चाहता हूं कि क्लैंग आउटपुट इनपुट से कैसे संबंधित है, जबकि हम सी ++ की गैर-तुच्छ विशेषताओं पर विचार नहीं करेंगे। हम इस छोटे से समारोह का उपयोग करते हैं, जिसे मैंने चक्रीय अनुकूलन पर उत्कृष्ट व्याख्यान से उधार लिया था:

bool is_sorted(int *a, int n) { for (int i = 0; i < n - 1; i++) if (a[i] > a[i + 1]) return false; return true; } 

चूंकि क्लैंग कोई अनुकूलन नहीं करता है, और चूंकि एलएलवीएम आईआर मूल रूप से सी और सी ++ के साथ काम करने के लिए डिज़ाइन किया गया था, इसलिए रूपांतरण अपेक्षाकृत आसान है। मैं Cl86 6.0.1 (या एक करीबी संस्करण का उपयोग करूंगा, क्योंकि यह अभी तक जारी नहीं हुआ है) x86-64 पर।

कमांड लाइन इस प्रकार है:

 clang++ is_sorted.cpp -O0 -S -emit-llvm 

दूसरे शब्दों में: हम is_sorted.cpp फ़ाइल को C ++ के रूप में संकलित करते हैं और फिर LLVM टूलचिन को निम्नलिखित बताते हैं: एलएलवीएम आईआर के एक पाठीय प्रतिनिधित्व के रूप में कोडांतरक को आउटपुट न करें। LLVM IR स्वैच्छिक है, और इसे जल्दी से प्रदर्शित या पार्स नहीं किया जा सकता है, यदि किसी व्यक्ति को इस कोड को देखने की आवश्यकता नहीं है, तो एक द्विआधारी बिटकोड प्रारूप हमेशा बेहतर होता है। यहां पूर्ण एलएलवीएम आईआर है, हम इसे भागों में समीक्षा करेंगे।

चलो फ़ाइल के शीर्ष पर शुरू करते हैं:

 ; ModuleID = 'is_sorted.cpp' source_filename = "is_sorted.cpp" target datalayout = "em:e-i64:64-f80:128-n8:16:32:64-S128" target triple = "x86_64-unknown-linux-gnu" 

अर्धविराम और पंक्ति के अंत के बीच का पूरा पाठ एक टिप्पणी है, जिसका अर्थ है कि पहली पंक्ति कुछ नहीं करती है, लेकिन, यदि आप रुचि रखते हैं, तो एलएलवीएम में "मॉड्यूल" एक संकलन इकाई, कोड और डेटा के लिए एक कंटेनर है। दूसरी पंक्ति हमें परेशान नहीं करना चाहिए। तीसरी पंक्ति संकलक द्वारा बनाई गई कुछ मान्यताओं का वर्णन करती है, वे इस लेख में भूमिका नहीं निभाते हैं, लेकिन आप यहां और अधिक पढ़ सकते हैं। लक्ष्य तीन gcc की विरासत है और अब हमें जरूरत नहीं है।

LLVM फ़ंक्शन में वैकल्पिक विशेषताएँ हैं:

 ; Function Attrs: noinline nounwind optnone uwtable 

उनमें से कुछ (जैसे ये) फ्रंट-एंड द्वारा समर्थित हैं, अन्य को बाद में ऑप्टिमाइज़ेशन पास द्वारा जोड़ा जाता है। इन विशेषताओं का कोड के अर्थ से कोई लेना-देना नहीं है, मैं यहां उनकी चर्चा नहीं करूंगा, लेकिन यदि आप रुचि रखते हैं तो आप उनके बारे में यहां पढ़ सकते हैं।

और अंत में, हमारा कार्य:

 define zeroext i1 @_Z9is_sortedPii(i32* %a, i32 %n) #0 { 

"ज़ीरोक्स्ट" का अर्थ है कि फ़ंक्शन के रिटर्न वैल्यू (i1, एक एकल-बिट पूर्णांक) को बैकेंड में शून्य के साथ उस चौड़ाई तक विस्तारित किया जाना चाहिए, जिसकी एबीआई को आवश्यकता है। फिर "mangled" फ़ंक्शन नाम आता है, फिर मापदंडों की सूची, मूल रूप से C ++ कोड के समान है, सिवाय इसके कि i32 एक 32-बिट चर को परिभाषित करता है। # 1 फ़ाइल के अंत में फ़ंक्शन को विशेषता समूह से जोड़ता है।

यहाँ पहली आधार इकाई है:

 entry: %retval = alloca i1, align 1 %a.addr = alloca i32*, align 8 %n.addr = alloca i32, align 4 %i = alloca i32, align 4 store i32* %a, i32** %a.addr, align 8 store i32 %n, i32* %n.addr, align 4 store i32 0, i32* %i, align 4 br label %for.cond 

प्रत्येक एलएलवीएम निर्देश को आधार इकाई के अंदर स्थित होना चाहिए: निर्देशों का एक सेट जिसमें शुरुआत में एक इनपुट और अंत में एक आउटपुट होता है। आधार इकाई का अंतिम निर्देश एक समाप्ति निर्देश होना चाहिए: अगली आधार इकाई में "विफल" अस्वीकार्य है। प्रत्येक फ़ंक्शन में एक इनपुट ब्लॉक होना चाहिए जिसमें पूर्ववर्ती नहीं होते हैं जो इस ब्लॉक में संक्रमण करते हैं। आईआर को पार्स करते समय इस और अन्य गुणों की जांच की जाती है; इन मॉड्यूल को "मॉड्यूल सत्यापनकर्ता" द्वारा संकलन प्रक्रिया के दौरान कई बार कहा जा सकता है। सत्यापनकर्ता डीबगिंग के लिए उपयोगी है जब एक पास एक अवैध आईआर उत्पन्न करता है।

इस बेस ब्लॉक में पहले चार निर्देश "एलोका" हैं: स्टैक मेमोरी आवंटित करना। संकलन के दौरान अनुमानित रूप से बनाए गए पहले तीन चर, चौथे - एक लूप चर। इस तरह से आवंटित चर केवल लोड और स्टोर निर्देशों के माध्यम से पहुँचा जा सकता है। निम्नलिखित तीन निर्देश तीन स्टैक स्लॉट्स को इनिशियलाइज़ करते हैं, a.addr और n.addr को फंक्शन में दिए गए मानों को पैरामीटर के रूप में उपयोग करके इनिशियलाइज़ किया जाता है, और मुझे शून्य पर आरम्भ किया जाता है। रिटर्न वैल्यू को इनिशियलाइज़ करने की ज़रूरत नहीं है, कोई भी कोड जो C और C ++ में अपरिभाषित नहीं है, उसे इस बात का ध्यान रखना होगा। आखिरी निर्देश अगली बेस यूनिट के लिए बिना शर्त संक्रमण है (हम इस बारे में अभी तक चिंतित नहीं हैं, सबसे अनावश्यक बदलाव एलएलवीएम बैकएंड द्वारा हटा दिए जाएंगे)।

आप पूछ सकते हैं: क्लैंग ए और एन के लिए स्टैक स्लॉट क्यों आवंटित करता है? वह सीधे इन मूल्यों का उपयोग क्यों नहीं करता है? इस फ़ंक्शन में, चूंकि और n नहीं बदलते हैं, इसलिए ऐसी रणनीति काम करेगी, लेकिन इस मामले को ऑप्टिमाइज़र द्वारा ध्यान में रखा जाएगा, और कैलेंग की क्षमता से बाहर है। यदि ए और एन को संशोधित किया जा सकता है, तो उन्हें स्मृति में होना चाहिए, और एसएसए-मूल्य नहीं होना चाहिए, जो परिभाषा से, कार्यक्रम में केवल एक बिंदु पर मूल्य ले सकते हैं। मेमोरी सेल एसएसए दुनिया से बाहर हैं और इसे किसी भी समय संशोधित किया जा सकता है। यह अजीब लग सकता है, लेकिन ऐसा समाधान आपको प्राकृतिक और कुशल तरीके से कंपाइलर के सभी हिस्सों के काम को व्यवस्थित करने की अनुमति देता है।

मैं क्लैंग को पतित एसएसए कोड के एक जनरेटर के रूप में समझता हूं जो एसएसए की सभी आवश्यकताओं को पूरा करता है, लेकिन केवल इसलिए कि आधार इकाइयों के बीच सूचना का आदान-प्रदान स्मृति के माध्यम से होता है। गैर-पतित कोड उत्पन्न करने के लिए कुछ ध्यान देने और कुछ विश्लेषण की आवश्यकता होती है, और कोड को उत्पन्न करने और अनुकूलन करने की जिम्मेदारियों को अलग करने के लिए क्लैंग डेवलपर्स ने ऐसा करने से इनकार कर दिया। मैंने माप परिणाम नहीं देखे, लेकिन मेरी समझ में, बहुत सारे मेमोरी ऑपरेशन उत्पन्न होते हैं, और फिर, लगभग तुरंत ही, उनमें से अधिकांश को आशावादी द्वारा हटा दिया जाता है, संकलन समय के बड़े ओवरहेड के बिना,

विचार करें कि लूप का अनुवाद कैसे होता है। सामान्य शब्दों में, यह इस तरह दिखता है:

 for (initializer; condition; modifier) { body } 

यह कुछ इस तरह से अनुवाद करता है:

  initializer goto COND COND: if (condition) goto BODY else goto EXIT BODY: body modifier goto COND EXIT: 

बेशक, ऐसा अनुवाद क्लैंग के लिए विशिष्ट नहीं है, कोई भी C और C ++ कंपाइलर ऐसा ही करता है।

हमारे उदाहरण में, लूप इनिशियलाइज़र इनपुट बेस ब्लॉक में ढह जाता है। निम्नलिखित आधार इकाई एक लूप कंडीशन चेक है:

 for.cond: ; preds = %for.inc, %entry %0 = load i32, i32* %i, align 4 %1 = load i32, i32* %n.addr, align 4 %sub = sub nsw i32 %1, 1 %cmp = icmp slt i32 %0, %sub br i1 %cmp, label %for.body, label %for.end 

क्लैंग एक उपयोगी टिप्पणी भी करता है कि इस बेस ब्लॉक को for.inc या इनपुट बेस ब्लॉक से पहुँचा जा सकता है। यह ब्लॉक i और n को मेमोरी से लोड करता है, n को कम करता है (nsw फ़्लैग C भाषा गुण दर्शाता है जो ओवरफ़्लो पर हस्ताक्षर नहीं करता है; इस फ़्लैग के बिना LLVM अतिरिक्त कोड के शब्दार्थ का उपयोग करता है), मैंने slt का उपयोग करते हुए कम मान की तुलना की है (साइन इन से कम, से कम पर हस्ताक्षर करें) और फिर अंततः for.body या for.end ब्लॉक में शाखा।

लूप बॉडी में प्रवेश केवल for.cond ब्लॉक से संभव है:

 for.body: %2 = load i32*, i32** %a.addr, align 8 %3 = load i32, i32* %i, align 4 %idxprom = sext i32 %3 to i64 %arrayidx = getelementptr inbounds i32, i32* %2, i64 %idxprom %4 = load i32, i32* %arrayidx, align 4 %5 = load i32*, i32** %a.addr, align 8 %6 = load i32, i32* %i, align 4 %add = add nsw i32 %6, 1 %idxprom1 = sext i32 %add to i64 %arrayidx2 = getelementptr inbounds i32, i32* %5, i64 %idxprom1 %7 = load i32, i32* %arrayidx2, align 4 %cmp3 = icmp sgt i32 %4, %7 br i1 %cmp3, label %if.then, label %if.end 

पहले दो पंक्तियाँ SSA रजिस्टर में एक और i लोड करती हैं; मैं फिर 64 बिट्स तक फैलता हूं और पते की गणना में भाग ले सकता हूं। Getelementptr कमांड (या संक्षिप्त रूप से जिप ) LLVM कमांड है, जो अपने दिखावा के लिए जाना जाता है, यहां तक ​​कि इसका अपना सहायता अनुभाग भी है । मशीन की भाषा के विपरीत, LLVM पॉइंटर्स को पूर्णांक नहीं मानता है। यह उर्फ ​​विश्लेषण और अन्य मेमोरी ऑप्टिमाइजेशन की सुविधा प्रदान करता है। यह कोड एक [i] और एक [i + 1] को लोड करता है, उनकी तुलना करता है और परिणाम के आधार पर शाखा करता है।

If.then ब्लॉक फ़ंक्शन के रिटर्न मान के लिए स्टैक स्लॉट में 0 बचाता है और फ़ंक्शन के आउटपुट ब्लॉक में बिना शर्त कूदता है:

 if.then: store i1 false, i1* %retval, align 1 br label %return 

अन्य ब्लॉक तुच्छ है:

 if.end: br label %for.inc 

और एक लूप चर में जोड़ने के लिए ब्लॉक भी बहुत सरल है:

 for.inc: %8 = load i32, i32* %i, align 4 %inc = add nsw i32 %8, 1 store i32 %inc, i32* %i, align 4 br label %for.cond 

यह कोड लूप स्थितियों की जांच करने के लिए वापस कूदता है।

यदि लूप सामान्य रूप से पूरा होता है, तो हम सही लौटाते हैं:

 for.end: store i1 true, i1* %retval, align 1 br label %return 

और अंत में, जो हमने रिटर्न वैल्यू के स्टैक स्लॉट में लोड किया है और लोड किया है:

 return: %9 = load i1, i1* %retval, align 1 ret i1 %9 

फ़ंक्शन के अंत में कुछ खास नहीं है। पोस्ट मेरे विचार से अधिक लंबी हो गई है, अगली पोस्ट में हम इस फ़ंक्शन के लिए आईआर स्तर को अनुकूलित करने पर विचार करेंगे।

(भेजे गए सुधार के लिए शी वांग और एलेक्स रोसेनबर्ग को धन्यवाद)