गो परिप्रेक्ष्य से एलएलवीएम

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

पहला उदाहरण

पहला फ़ंक्शन जो मैं यहां देखने जा रहा हूं वह संख्याओं को जोड़ने के लिए एक सरल तंत्र है:

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

यह फ़ंक्शन बहुत सरल है, और, शायद, इससे अधिक सरल कुछ नहीं हो सकता। यह निम्नलिखित गो एसएसए कोड में अनुवाद करता है:

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

इस दृश्य के साथ, डेटा प्रकार के संकेत दाईं ओर रखे गए हैं और अधिकांश मामलों में इन्हें अनदेखा किया जा सकता है।

यह छोटा सा उदाहरण आपको पहले से ही एसएसए के एक पहलू का सार देखने की अनुमति देता है। अर्थात्, कोड को एसएसए फॉर्म में परिवर्तित करते समय, प्रत्येक अभिव्यक्ति को सबसे प्रारंभिक भागों में तोड़ दिया जाता है जिससे वह बना है। हमारे मामले में, आदेश return a + b, वास्तव में, दो ऑपरेशनों का प्रतिनिधित्व करता है: दो संख्याओं को जोड़ना और परिणाम लौटाना।

इसके अलावा, यहां आप प्रोग्राम के मूल ब्लॉक देख सकते हैं; इस कोड में केवल एक ब्लॉक है - एंट्री ब्लॉक। हम नीचे ब्लॉकों के बारे में अधिक बात करेंगे।

गो एसएसए कोड आसानी से एलएलवीएम आईआर में परिवर्तित हो जाता है:

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

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

इस कोड के बारे में ध्यान देने वाली एक बात यह है कि गो का प्रकार प्रतिनिधित्व निर्णय है int, जिसे कंपाइलर और संकलन के लक्ष्य के आधार पर 32-बिट या 64-बिट मान के रूप में दर्शाया जा सकता है, तब स्वीकार किया जाता है जब एलएलवीएम आईआर कोड उत्पन्न करता है। यह कई कारणों में से एक है कि एलएलवीएम आईआर कोड, जैसा कि कई लोग सोचते हैं, प्लेटफ़ॉर्म स्वतंत्र नहीं है। एक प्लेटफ़ॉर्म के लिए बनाए गए ऐसे कोड को आसानी से दूसरे प्लेटफ़ॉर्म के लिए नहीं लिया और संकलित किया जा सकता है (जब तक कि आप इस समस्या को हल करने के लिए उपयुक्त न हों अत्यधिक सावधानी के साथ).

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

यह कुछ अनुकूलन के लिए महत्वपूर्ण हो सकता है. उदाहरण के लिए, दो मान जोड़ना i16 32-बिट प्लेटफ़ॉर्म पर (32-बिट रजिस्टरों के साथ) सीमा में बने रहने के लिए, जोड़ने के बाद, एक साइन विस्तार ऑपरेशन की आवश्यकता होती है i16. इस वजह से, मशीन रजिस्टर आकारों के आधार पर पूर्णांक संचालन करना अक्सर अधिक कुशल होता है।

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

दूसरा उदाहरण

अगला उदाहरण जिसे हम देखेंगे वह थोड़ा अधिक जटिल होगा। अर्थात्, हम एक ऐसे फ़ंक्शन के बारे में बात कर रहे हैं जो पूर्णांकों के एक टुकड़े का योग करता है:

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

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

वास्तव में, यहां आप इस तथ्य पर ध्यान दे सकते हैं कि प्रोग्राम को घुंघराले ब्रेसिज़ (जैसे भाषाओं के सी परिवार में) का उपयोग करके ब्लॉकों में विभाजित नहीं किया गया है। इसे असेंबली भाषाओं की याद दिलाते हुए लेबलों द्वारा विभाजित किया गया है, और मूल ब्लॉकों के रूप में प्रस्तुत किया गया है। एसएसए में, बुनियादी ब्लॉकों को एक लेबल से शुरू होने वाले और बुनियादी ब्लॉक पूरा करने के निर्देशों के साथ समाप्त होने वाले कोड के सन्निहित अनुक्रमों के रूप में परिभाषित किया गया है, जैसे - return и jump.

इस कोड का एक और दिलचस्प विवरण निर्देश द्वारा दर्शाया गया है phi. निर्देश काफी असामान्य हैं और इन्हें समझने में कुछ समय लग सकता है। उसे याद रखो सर्व शिक्षा अभियान स्टेटिक सिंगल असाइनमेंट का संक्षिप्त रूप है। यह कंपाइलरों द्वारा उपयोग किए गए कोड का एक मध्यवर्ती प्रतिनिधित्व है, जिसमें प्रत्येक चर को केवल एक बार मान निर्दिष्ट किया जाता है। यह हमारे फ़ंक्शन जैसे सरल कार्यों को व्यक्त करने के लिए बहुत अच्छा है myAddऊपर दिखाया गया है, लेकिन यह इस अनुभाग में चर्चा किए गए फ़ंक्शन जैसे अधिक जटिल कार्यों के लिए उपयुक्त नहीं है sum. विशेष रूप से, लूप के निष्पादन के दौरान चर बदलते हैं i и n.

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

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

इसका अर्थ इस प्रकार है: यदि पिछला मूल ब्लॉक एक ब्लॉक था entry (इनपुट), फिर t0 एक स्थिरांक है 0, और यदि पिछला मूल ब्लॉक था for.body, तो आपको मान लेने की आवश्यकता है t6 इस ब्लॉक से. यह सब काफी रहस्यमय लग सकता है, लेकिन यही तंत्र एसएसए को काम करता है। मानवीय दृष्टिकोण से, यह सब कोड को समझना कठिन बना देता है, लेकिन तथ्य यह है कि प्रत्येक मान केवल एक बार निर्दिष्ट किया जाता है, जिससे कई अनुकूलन बहुत आसान हो जाते हैं।

ध्यान दें कि यदि आप अपना स्वयं का कंपाइलर लिखते हैं, तो आपको आमतौर पर इस तरह की चीज़ों से नहीं जूझना पड़ेगा। यहां तक ​​कि क्लैंग भी ये सभी निर्देश उत्पन्न नहीं करता है phi, यह एक तंत्र का उपयोग करता है alloca (यह सामान्य स्थानीय चर के साथ काम करने जैसा है)। फिर, एलएलवीएम ऑप्टिमाइज़ेशन पास चलाते समय कॉल किया जाता है mem2reg, निर्देश alloca एसएसए फॉर्म में परिवर्तित किया गया। हालाँकि, टिनीगो को गो एसएसए से इनपुट प्राप्त होता है, जो सुविधाजनक रूप से पहले से ही एसएसए फॉर्म में परिवर्तित हो जाता है।

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

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 मान और लेबल की अदला-बदली की गई। हालाँकि, यहाँ कुछ ऐसा है जिस पर विशेष ध्यान देने योग्य है।

आरंभ करने के लिए, यहां आप एक पूरी तरह से अलग फ़ंक्शन हस्ताक्षर देख सकते हैं। एलएलवीएम स्लाइस का समर्थन नहीं करता है, और परिणामस्वरूप, एक अनुकूलन के रूप में, इस मध्यवर्ती कोड को उत्पन्न करने वाले टिनीगो कंपाइलर ने इस डेटा संरचना के विवरण को भागों में विभाजित कर दिया है। यह तीन स्लाइस तत्वों का प्रतिनिधित्व कर सकता है (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, जो इसी तरह से काम करता है।

परिणाम

मेरा मानना ​​है कि इस सामग्री में मैंने एलएलवीएम आईआर की सबसे महत्वपूर्ण विशेषताओं को शामिल किया है। बेशक, यहां और भी बहुत कुछ है। विशेष रूप से, कोड के मध्यवर्ती प्रतिनिधित्व में कई एनोटेशन शामिल हो सकते हैं जो कंपाइलर को ज्ञात कोड की कुछ विशेषताओं को ध्यान में रखने के लिए ऑप्टिमाइज़ेशन पास की अनुमति देते हैं जिन्हें अन्यथा आईआर में व्यक्त नहीं किया जा सकता है। उदाहरण के लिए, यह एक झंडा है inbounds जीईपी निर्देश, या झंडे nsw и nuw, जिसे निर्देशों में जोड़ा जा सकता है add. यही बात कीवर्ड के लिए भी लागू होती है private, ऑप्टिमाइज़र को इंगित करता है कि जिस फ़ंक्शन को वह चिह्नित करता है उसे वर्तमान संकलन इकाई के बाहर से संदर्भित नहीं किया जाएगा। यह अप्रयुक्त तर्कों को खत्म करने जैसे कई दिलचस्प अंतरप्रक्रियात्मक अनुकूलन की अनुमति देता है।

आप एलएलवीएम के बारे में अधिक पढ़ सकते हैं प्रलेखन, जिसका संदर्भ आप अपना स्वयं का एलएलवीएम-आधारित कंपाइलर विकसित करते समय अक्सर करेंगे। यहाँ नेतृत्व, जो एक बहुत ही सरल भाषा के लिए एक कंपाइलर विकसित करने पर विचार करता है। जानकारी के ये दोनों स्रोत अपना स्वयं का कंपाइलर बनाते समय आपके लिए उपयोगी होंगे।

प्रिय पाठकों! क्या आप एलएलवीएम का उपयोग कर रहे हैं?

स्रोत: www.habr.com