👨🏾‍🌾 🎻 ❕ एलएलवीएम कैसे फ़ंक्शन का अनुकूलन करता है 📑 😀 👨🏼‍💻

AOT संकलक का अनुकूलन आमतौर पर इस तरह संरचित होता है:

मध्यवर्ती प्रतिनिधित्व के लिए स्रोत कोड परिवर्तित करना दृश्यपटल
मशीन-इंडिपेंडेंट ऑप्टिमाइज़ेशन (IR) पाइपलाइन: पास का एक क्रम जो अक्षम वर्गों और संरचनाओं को खत्म करने के लिए IR को फिर से लिखता है जिसे सीधे मशीन कोड में परिवर्तित नहीं किया जा सकता है। कभी-कभी इस भाग को मध्य-अंत कहा जाता है।
असेंबली कोड या मशीन कोड जनरेट करने के लिए मशीन आश्रित बैकएंड।

कुछ कंपाइलरों में, आईआर प्रारूप पूरे अनुकूलन प्रक्रिया में अपरिवर्तित रहता है, दूसरों में इसका प्रारूप या शब्दार्थ बदलता है। LLVM में, प्रारूप और शब्दार्थ निश्चित हैं, और इसलिए गलत संकलन या संकलक क्रैश के जोखिम के बिना किसी भी क्रम में पास चलाना संभव है।

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

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

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

आइए देखें कि Clang / LLVM 6.0.1 इस C ++ कोड का अनुकूलन कैसे करता है:

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; }

उसी समय, हमें याद है कि अनुकूलन पाइपलाइन बहुत व्यस्त जगह है, और हम बहुत सारे मजेदार क्षणों को याद करेंगे, जैसे:

इनलाइनिंग एक सरल लेकिन बहुत महत्वपूर्ण अनुकूलन है जो इस उदाहरण में नहीं होता है, क्योंकि हम केवल एक कार्य पर विचार करते हैं। सी ++ के लिए विशिष्ट लगभग सभी अनुकूलन, लेकिन सी-ऑटो-वैश्वीकरण के लिए नहीं, जो लूप से जल्दी बाहर निकलने से रोकता है

नीचे दिए गए पाठ में, मैं उन सभी पास को छोड़ दूंगा जो कोड में परिवर्तन नहीं करते हैं। इसके अलावा, हम बैकएंड पर ध्यान नहीं देंगे, जो बहुत काम भी करता है। लेकिन यहां तक कि शेष मार्ग बहुत सारे हैं! (तस्वीरों के लिए खेद है, लेकिन यह स्वरूपण कठिनाइयों से बचने का सबसे अच्छा तरीका है)।

यहाँ Clang द्वारा बनाई गई IR फ़ाइल है (मैंने मैन्युअल रूप से "Optnone" विशेषता को हटा दिया है, जो Clang डाला गया है) और प्रत्येक अनुकूलन पास के प्रभाव को देखने के लिए उपयोग की जाने वाली कमांड लाइन:

 opt -O2 -print-before-all -print-after-all is_sorted2.ll

पहला पास सीएफजी सरलीकरण (नियंत्रण प्रवाह ग्राफ) है। चूंकि क्लैंग अनुकूलन का प्रदर्शन नहीं करता है, इसलिए आईआर जो इसे बनाता है उसमें सरल अनुकूलन विकल्प होते हैं:

यहाँ, बेस यूनिट 26 बस 27 को ब्लॉक करने के लिए चलती है। इस तरह के ब्लॉक को गंतव्य ब्लॉक द्वारा संदर्भों को पुनर्निर्देशित करके हटाया जा सकता है। एलएलवीएम स्वचालित रूप से ब्लॉक को फिर से कायम करेगा। SimplifyCFG द्वारा निर्मित रूपांतरणों की पूरी सूची गलियारे के शीर्ष पर सूचीबद्ध है।

, . :

, , . phi- , . , . invoke nounwind- call "if (x) if (y)" "if (x&y)"

, . : , , . phi- , . , . invoke nounwind- call "if (x) if (y)" "if (x&y)"
, . : , , . phi- , . , . invoke nounwind- call "if (x) if (y)" "if (x&y)"
, . : , , . phi- , . , . invoke nounwind- call "if (x) if (y)" "if (x&y)"
, . : , , . phi- , . , . invoke nounwind- call "if (x) if (y)" "if (x&y)"
, . : , , . phi- , . , . invoke nounwind- call "if (x) if (y)" "if (x&y)"
, . : , , . phi- , . , . invoke nounwind- call "if (x) if (y)" "if (x&y)"

, . :

, , . phi- , . , . invoke nounwind- call "if (x) if (y)" "if (x&y)"

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

अगला मार्ग, एसआरए (एग्रीगेट्स का स्केलर प्रतिस्थापन), सबसे अधिक इस्तेमाल किया जाने वाला एक है। इसका नाम कुछ भ्रम की ओर जाता है क्योंकि SROA अपने कार्यों में से एक है। पास प्रत्येक आवक निर्देश (फ़ंक्शन स्टैक पर मेमोरी आवंटन) की जांच करता है, और इसे एसएसए रजिस्टरों में बदलने की कोशिश करता है। एक एलोका निर्देश ( जो वास्तव में, लगभग स्टैक पर एक चर है। ट्रांसलेशन ..) कई रजिस्टरों में बदल जाता है यदि इसे सांख्यिकीय रूप से कई बार सौंपा जाता है, और यदि एलोका एक वर्ग या संरचना है, तो इसे घटकों में विभाजित किया जाता है (इसे "स्केलर" कहा जाता है) प्रतिस्थापन "मार्ग के नाम से संदर्भित)। एसआरए का एक सरल संस्करण चर को ढेर करने के लिए आत्मसमर्पण करेगा जिसके लिए एक पता लेने के संचालन का उपयोग किया जाता है, लेकिन एलएलवीएम संस्करण एक अन्य विश्लेषण एल्गोरिथ्म के साथ बातचीत करता है और एक बुद्धिमान तरीके से कार्य करता है (हालांकि निम्नलिखित उदाहरण में इसकी आवश्यकता नहीं है)।

एसआरएए के बाद, एलोका निर्देश (और संबंधित लोड और स्टोर निर्देश) गायब हो जाते हैं, और कोड क्लीनर और बाद के अनुकूलन के लिए अधिक उपयुक्त हो जाता है (बेशक, एसआरओ सामान्य मामले में सभी एलोक को हटा नहीं सकता है, यह केवल तब होता है जब सूचक विश्लेषण कर सकता है पूरी तरह से उपनाम से छुटकारा)। इस प्रक्रिया में, SROA कोड में phi निर्देशों को सम्मिलित करता है। Phi निर्देश SSA प्रतिनिधित्व के मूल का निर्माण करते हैं, और Clang उत्पन्न करने वाले कोड में phi की कमी हमें बताती है कि Clang SSA का एक तुच्छ संस्करण उत्पन्न करता है, जिसमें आधार ब्लॉक मेमोरी के माध्यम से जुड़े होते हैं न कि SSA रजिस्टरों के माध्यम से।

इस प्रकार है " प्रारंभिक आम सबप्रेस्प्रेशन एलिमिनेशन ", सीएसई (आम सबएक्सप्रेसन के शुरुआती हटाने)। CSE अत्यधिक उप-संदर्भों के मामलों को समाप्त करने की कोशिश करता है जो मानव-लिखित कोड और आंशिक रूप से अनुकूलित कोड दोनों में हो सकते हैं। "प्रारंभिक सीएसई" सीएसई का एक त्वरित और आसान संस्करण है जो तुच्छ अनावश्यक गणना की पहचान करता है।

यहां,% 10 और% 17 एक ही काम करते हैं, अर्थात, कोड को फिर से लिखा जा सकता है ताकि एक मान का उपयोग किया जाए, और दूसरा हटा दिया जाए। यह एसएसए के लाभों में कुछ अंतर्दृष्टि देता है: जब प्रत्येक रजिस्टर को केवल एक बार सौंपा जाता है, तो एकल रजिस्टर के कई संस्करणों जैसी कोई चीज नहीं होती है। इस प्रकार, प्रोग्राम के इन-डेप्थ विश्लेषण का उपयोग किए बिना, सिंटैक्टिक तुल्यता का उपयोग करके अनावश्यक गणना का पता लगाया जा सकता है (यह एसएसए दुनिया के बाहर मौजूद मेमोरी स्थानों के लिए नहीं है)।

अगला, कई पास लॉन्च किए गए हैं जिनका हमारे मामले में कोई प्रभाव नहीं है, और फिर " वैश्विक चर अनुकूलक " लॉन्च किया गया है, जिसे निम्नानुसार वर्णित किया गया है:

, . , , , , ..

यह मार्ग निम्नलिखित परिवर्तन करता है:

उन्होंने एक फ़ंक्शन विशेषता जोड़ी: संकलक के एक हिस्से के लिए उपयोगी क्या हो सकता है, इसके बारे में जानकारी संग्रहीत करने के लिए संकलक के एक हिस्से द्वारा उपयोग किए गए मेटाडेटा। आप इस विशेषता के उद्देश्य के बारे में यहां पढ़ सकते हैं।

हमने जिन अन्य ऑप्टिमाइज़ेशनों पर विचार किया है, उनके विपरीत, ग्लोबल वैरिएबल्स का ऑप्टिमाइज़र इंटरप्रोड्यूरल है, यह पूरी तरह से एलएलवीएम मॉड्यूल को देखता है। एक मॉड्यूल सी और सी ++ में एक संकलन इकाई के बराबर (अधिक या कम) है। इंटरप्रोडेक्टोरल ऑप्टिमाइज़ेशन के विपरीत, इंट्राप्रोसेरेडुरल एक समय में केवल एक ही फंक्शन देखता है।

अगला मार्ग निर्देश को जोड़ता है और इसे " निर्देश संयोजन ", InstCombine कहा जाता है। यह पीपहोल अनुकूलन का एक बड़ा और विविध संग्रह है, जो (आमतौर पर) कुछ निर्देशों को फिर से लिखता है , जो आम डेटा द्वारा संयुक्त रूप से अधिक कुशल रूप में प्रस्तुत किए जाते हैं। InstCombine एक फ़ंक्शन के नियंत्रण प्रवाह को नहीं बदलता है। उपर्युक्त उदाहरण में, वह बहुत नहीं बदला:

यहां,% 1 से 1 को घटाने के बजाय,% 4 की गणना करने के लिए, हम -1 जोड़ते हैं। यह अनुकूलन नहीं है, लेकिन विहितीकरण है। जब गणना करने के कई तरीके होते हैं, तो एलएलवीएम इसे कैनोनिकल (अक्सर बेतरतीब ढंग से चुने हुए) रूप में लाने की कोशिश करता है जो बाद में गुजरता है और बैकेंड देखने की उम्मीद करता है। दूसरा बदलाव InstCombine किया गया है जो दो हस्ताक्षरित विस्तार कार्यों (सेक्स्ट इंस्ट्रक्शन) का विहित रूप है, जो% 7 की गणना करता है और 11% शून्य विस्तार (zext) में परिवर्तित हो जाता है। यह रूपांतरण सुरक्षित है जब कंपाइलर साबित कर सकता है कि सेक्स्ट ऑपरेंड गैर-नकारात्मक है। इस स्थिति में, यह इसलिए है क्योंकि लूप वेरिएबल 0 से n में बदलता है (यदि एन नकारात्मक है, तो लूप बिल्कुल भी निष्पादित नहीं होता है)। नवीनतम परिवर्तन "nuw" (बिना अहस्ताक्षरित लपेट) के निर्देश के अतिरिक्त था जो% 10 की गणना करता है। हम देख सकते हैं कि यह इस तथ्य से सुरक्षित है कि (1) लूप वैरिएबल हमेशा बढ़ता रहता है और (2) यदि वैरिएबल शून्य से शुरू होता है और बढ़ता है, तो यह अनिर्धारित हो जाएगा, जब साइन इन करें INT_MAX चौराहे पर एक अहस्ताक्षरित ओवरफ्लो तक पहुंचने से पहले, UINT_MAX के बाद। इस ध्वज का उपयोग बाद के अनुकूलन के लिए किया जा सकता है।

अगला, SimpleifyCFG दूसरी बार शुरू होता है, और दो खाली बेस ब्लॉक निकालता है:

फिर, "Deduce फ़ंक्शन विशेषताएँ" पास फ़ंक्शन को एनोटेट करता है:

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

फिर " रोटेट लूप्स " पास बाद के अनुकूलन के लिए स्थितियों में सुधार करने के प्रयास में कोड को स्थानांतरित करता है:

हालांकि अंतर डराने वाला लगता है, परिवर्तन वास्तव में छोटे हैं। हम देख सकते हैं कि क्या हुआ, एक और अधिक पठनीय तरीके से, अगर हम एलएलवीएम को रोटेशन चक्रों से गुजरने से पहले और बाद में एक नियंत्रण हस्तांतरण ग्राफ खींचने के लिए कहते हैं। यहाँ (पहले) और बाद में (दाएं) उनका दृष्टिकोण है:

मूल कोड अभी भी लूप संरचना का अनुसरण करता है जो क्लैंग उत्पन्न करता है:

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

रन के बाद, लूप इस तरह दिखता है:

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

(जोहान्स डर्फ़र्ट द्वारा प्रस्तावित सुधार नीचे सूचीबद्ध हैं - धन्यवाद!)

लूप रोटेशन पास का उद्देश्य एक शाखा को निकालना है, जो आगे अनुकूलन के लिए अनुमति देता है। मुझे इंटरनेट पर इस रूपांतरण का बेहतर विवरण नहीं मिला।

CFG सरलीकरण पास दो बेस ब्लॉक को कम करता है जिसमें केवल पतित (एकल-इनपुट) phi निर्देश होते हैं:

निर्देश कॉम्बिनर पास "% 4 = 0 s <(% 1 - 1)" को "% 4 =% 1 s> 1 <(जहाँ s <और s> हस्ताक्षरित ऑपरेंड की तुलना के लिए संचालन कर रहे हैं) में बदल जाता है," उपयोगी परिवर्तन, यह निर्भरता श्रृंखला की लंबाई कम कर देता है और "मृत" (अप्राप्य) निर्देश भी बना सकता है ( पैच को देखें)। यह पास भी तुच्छ phi निर्देशों को हटा देता है जो लूप रोटेशन पास द्वारा जोड़े गए थे।

निम्नलिखित " कैनोनिकलाइज़ नेचुरल लूप्स " मार्ग है, जो अपने स्वयं के सोर्स कोड में निम्नानुसार वर्णित है:

, .

(Loop pre-header) , , . ,, LICM.

, , ( ) ( ). , , "store-sinking", LICM.

, (backedge).

Indirectbr . , . , , .

, simplifycfg , , , .

, , CFG, .

यहाँ हम देखते हैं कि आउटपुट ब्लॉक डाला गया था:

फिर " लूप चर का सरलीकरण " इस प्रकार है:

( , ), , .

, :

, . , 'for (i = 7; i*i < 1000; ++i)' 'for (i = 0; i != 25; ++i)'.

indvar , . , "".

इस पास का प्रभाव 32-बिट लूप चर को 64-बिट में बदलने के लिए होगा:

मुझे नहीं पता कि क्यों zext - पहले सेक्स्ट से विहित रूप में डाली गई, फिर से sext में लौट आई।

अब " वैश्विक मूल्य अंकन " पास बहुत ही स्मार्ट अनुकूलन कर रहा है। इस पोस्ट को लिखने का एक कारण यह दिखाने की इच्छा है। क्या आप उसे यहाँ देख सकते हैं?

क्या आपने देखा? हां, [i] और [i + 1] के अनुरूप, बाईं ओर लूप में दो लोड निर्देश। यहां, GVN ने पाया कि [i] लोड करना आवश्यक नहीं है, क्योंकि लूप के एक पुनरावृत्ति से [i + 1] को अगले [i] की तरह स्थानांतरित किया जा सकता है। यह सरल चाल समारोह द्वारा किए गए मेमोरी रीड की संख्या को आधे से कम कर देती है। LLVM और GCC दोनों ने हाल ही में इस परिवर्तन को करना सीखा है।

आप अपने आप से पूछ सकते हैं कि क्या यह तरकीब काम करेगी अगर हम [i] की तुलना [i + 2] से करें। यह पता चला है कि नहीं, लेकिन जीसीसी ऐसे मामलों के लिए अधिकतम चार रजिस्टर आवंटित कर सकता है।

फिर " बिट-ट्रैकिंग डेड कोड एलिमिनेशन " पास शुरू होता है:

"Bit-Tracking Dead Code Elimination". (, "" "" ..) "" . , "" .

लेकिन यहां यह पता चला है कि इस तरह के ट्रिक्स की जरूरत नहीं है, क्योंकि एकमात्र डेड कोड GEP (एलिमेंट पॉइंटर) इंस्ट्रक्शन है, और यह तुच्छ रूप से डेड है (GVN पास ने लोड इंस्ट्रक्शन को डिलीट कर दिया, जो इस इंस्ट्रक्शन द्वारा गणना किए गए एड्रेस का इस्तेमाल करता है:

अब निर्देशों के संयोजन के लिए एल्गोरिथ्म ने एक और आधार इकाई में जोड़ दिया है। जिस तर्क से इस परिवर्तन को InstCombine में रखा गया था वह मेरे लिए स्पष्ट नहीं है, शायद कोई स्पष्ट स्थान नहीं था जहां इसे रखा जा सकता है:

अब कुछ ज्यादा ही अजीब हो रहा है: " जंप थ्रेडिंग " पास ने क्या हटा दिया है "प्राकृतिक छोरों" को पास किया गया है:

फिर हम फिर से विहित रूप में ढले:

और सीएफजी सरलीकरण इसे अलग तरीके से बदल देता है:

और पीछे:

और फिर से:

और पीछे:

और वहाँ:

और अंत में, हम मिडलैंड के साथ कर रहे हैं! दाईं ओर वाला कोड वह कोड है जिसे हम (हमारे मामले में) x86-64 बैकेंड को पास करेंगे।

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

आभार: मेरे इन-इन-कंपाइलर कोर्स के कुछ छात्रों ने इस पोस्ट के मसौदे पर अपनी प्रतिक्रिया छोड़ दी (और मैंने होमवर्क के लिए इस सामग्री का उपयोग भी किया)। मैं लूप ऑप्टिमाइज़ेशन पर व्याख्यान के इस अच्छे सेट में यहां चर्चा किए गए कार्यों के माध्यम से चला गया।

एलएलवीएम कैसे फ़ंक्शन का अनुकूलन करता है

More articles: