गो दृष्टीकोनातून LLVM

कंपाइलर विकसित करणे हे खूप कठीण काम आहे. परंतु, सुदैवाने, LLVM सारख्या प्रकल्पांच्या विकासामुळे, या समस्येचे निराकरण मोठ्या प्रमाणात सोपे केले गेले आहे, ज्यामुळे एका प्रोग्रामरला एक नवीन भाषा तयार करता येते जी C च्या कार्यक्षमतेच्या अगदी जवळ आहे. सिस्टीम मोठ्या प्रमाणात कोडद्वारे दर्शविले जाते, थोड्या दस्तऐवजांसह सुसज्ज आहे. ही उणीव दूर करण्याचा प्रयत्न करण्यासाठी, साहित्याचा लेखक, ज्याचा अनुवाद आम्ही आज प्रकाशित करत आहोत, Go मध्ये लिहिलेल्या कोडची उदाहरणे दाखवणार आहे आणि ते प्रथम भाषांतरित कसे केले गेले हे दाखवणार आहे. SSA जा, आणि नंतर कंपाइलर वापरून 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 भाषेत, चिन्हांकित पूर्णांक व्हेरिएबल ओव्हरफ्लो केल्याने अपरिभाषित वर्तन होते, म्हणून क्लॅंग फ्रंटएंड ऑपरेशनमध्ये ध्वज जोडतो 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. सूचना अतिशय असामान्य आहेत आणि समजण्यास थोडा वेळ लागू शकतो. लक्षात ठेवा, ते एसएसए स्टॅटिक सिंगल असाइनमेंटसाठी लहान आहे. हे कंपाइलर्सद्वारे वापरल्या जाणार्‍या कोडचे मध्यवर्ती प्रतिनिधित्व आहे, ज्यामध्ये प्रत्येक व्हेरिएबलला फक्त एकदाच मूल्य नियुक्त केले जाते. आमच्या फंक्शनसारख्या साध्या फंक्शन्स व्यक्त करण्यासाठी हे उत्तम आहे myAddवर दर्शविले आहे, परंतु या विभागात चर्चा केलेल्या कार्यासारख्या अधिक जटिल कार्यांसाठी योग्य नाही sum. विशेषतः, लूपच्या अंमलबजावणीदरम्यान व्हेरिएबल्स बदलतात i и n.

SSA एकदा तथाकथित सूचना वापरून व्हेरिएबल व्हॅल्यू नियुक्त करण्याच्या निर्बंधाला बायपास करते phi (त्याचे नाव ग्रीक वर्णमालावरून घेतले आहे). वस्तुस्थिती अशी आहे की सी सारख्या भाषांसाठी कोडचे SSA प्रतिनिधित्व तयार करण्यासाठी, तुम्हाला काही युक्त्या वापराव्या लागतील. ही सूचना कॉल केल्याचे परिणाम व्हेरिएबलचे वर्तमान मूल्य आहे (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