Η ανάπτυξη ενός μεταγλωττιστή είναι ένα πολύ δύσκολο έργο. Αλλά, ευτυχώς, με την ανάπτυξη έργων όπως το LLVM, η λύση σε αυτό το πρόβλημα απλοποιείται πολύ, γεγονός που επιτρέπει ακόμη και σε έναν μόνο προγραμματιστή να δημιουργήσει μια νέα γλώσσα που να είναι κοντά στην απόδοση της C. Η εργασία με την LLVM περιπλέκεται από το γεγονός ότι αυτό το σύστημα αντιπροσωπεύεται από έναν τεράστιο όγκο κώδικα, εξοπλισμένο με μικρή τεκμηρίωση. Για να προσπαθήσει να διορθώσει αυτό το μειονέκτημα, ο συγγραφέας του υλικού, τη μετάφραση του οποίου δημοσιεύουμε σήμερα, πρόκειται να επιδείξει παραδείγματα κώδικα γραμμένου στο Go και να δείξει πώς μεταφράζονται για πρώτη φορά σε , και στη συνέχεια σε LLVM IR χρησιμοποιώντας τον μεταγλωττιστή . Ο κώδικας IR Go SSA και LLVM έχει τροποποιηθεί ελαφρώς για να αφαιρεθούν πράγματα που δεν σχετίζονται με τις επεξηγήσεις που δίνονται εδώ, προκειμένου να γίνουν πιο κατανοητές οι επεξηγήσεις.
Πρώτο παράδειγμα
Η πρώτη συνάρτηση που θα εξετάσω εδώ είναι ένας απλός μηχανισμός για την πρόσθεση αριθμών:
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
}
Αυτό που μπορείτε να παρατηρήσετε είναι ότι παρόλο που χρησιμοποιούνται διαφορετικές συντακτικές δομές εδώ, η δομή της συνάρτησης είναι βασικά αμετάβλητη. Ο κώδικας IR LLVM είναι λίγο ισχυρότερος από τον κώδικα Go SSA, παρόμοιος με τον C. Εδώ, στη δήλωση συνάρτησης, πρώτα υπάρχει μια περιγραφή του τύπου δεδομένων που επιστρέφει, ο τύπος ορίσματος υποδεικνύεται πριν από το όνομα του ορίσματος. Επιπλέον, για να απλοποιηθεί η ανάλυση υπερύθρων, τα ονόματα των καθολικών οντοτήτων προηγούνται από το σύμβολο @, και πριν από τα τοπικά ονόματα υπάρχει ένα σύμβολο % (μια συνάρτηση θεωρείται επίσης καθολική οντότητα).
Ένα πράγμα που πρέπει να σημειωθεί σχετικά με αυτόν τον κώδικα είναι ότι η απόφαση αναπαράστασης τύπου του Go int, η οποία μπορεί να αναπαρασταθεί ως τιμή 32-bit ή 64-bit, ανάλογα με τον μεταγλωττιστή και τον στόχο της μεταγλώττισης, γίνεται αποδεκτή όταν το LLVM δημιουργεί τον κώδικα IR. Αυτός είναι ένας από τους πολλούς λόγους που ο κώδικας IR LLVM δεν είναι, όπως πολλοί πιστεύουν, ανεξάρτητος από την πλατφόρμα. Ένας τέτοιος κώδικας, που δημιουργήθηκε για μια πλατφόρμα, δεν μπορεί απλώς να ληφθεί και να μεταγλωττιστεί για άλλη πλατφόρμα (εκτός εάν είστε κατάλληλοι για την επίλυση αυτού του προβλήματος ).
Ένα άλλο ενδιαφέρον σημείο που αξίζει να σημειωθεί είναι ότι ο τύπος i64 δεν είναι προσημασμένος ακέραιος: είναι ουδέτερος όσον αφορά την αναπαράσταση του πρόσημου του αριθμού. Ανάλογα με την εντολή, μπορεί να αντιπροσωπεύει και ενυπόγραφους και ανυπόγραφους αριθμούς. Στην περίπτωση της αναπαράστασης της πράξης πρόσθεσης, αυτό δεν έχει σημασία, επομένως δεν υπάρχει διαφορά στην εργασία με προσημασμένους ή μη αριθμούς. Εδώ θα ήθελα να σημειώσω ότι στη γλώσσα C, η υπερχείλιση μιας μεταβλητής ακέραιου αριθμού οδηγεί σε απροσδιόριστη συμπεριφορά, επομένως η διεπαφή Clang προσθέτει μια σημαία στη λειτουργία nsw (χωρίς υπογεγραμμένο περιτύλιγμα), το οποίο λέει στο LLVM ότι μπορεί να υποθέσει ότι η προσθήκη δεν υπερχειλίζει ποτέ.
Αυτό μπορεί να είναι σημαντικό για ορισμένες βελτιστοποιήσεις. Για παράδειγμα, προσθέτοντας δύο τιμές i16 σε μια πλατφόρμα 32 bit (με καταχωρητές 32 bit) απαιτεί, μετά την προσθήκη, μια λειτουργία επέκτασης σήματος για να παραμείνει εντός εμβέλειας 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. Οι οδηγίες είναι αρκετά ασυνήθιστες και μπορεί να χρειαστεί λίγος χρόνος για να τις καταλάβετε. να θυμάστε ότι είναι συντομογραφία του Static Single Assignment. Αυτή είναι μια ενδιάμεση αναπαράσταση του κώδικα που χρησιμοποιείται από τους μεταγλωττιστές, στην οποία κάθε μεταβλητή εκχωρείται μια τιμή μόνο μία φορά. Αυτό είναι εξαιρετικό για την έκφραση απλών συναρτήσεων όπως η συνάρτησή μας myAddφαίνεται παραπάνω, αλλά δεν είναι κατάλληλο για πιο σύνθετες λειτουργίες όπως η συνάρτηση που συζητείται σε αυτήν την ενότητα sum. Συγκεκριμένα, οι μεταβλητές αλλάζουν κατά την εκτέλεση του βρόχου i и n.
Το SSA παρακάμπτει τον περιορισμό της εκχώρησης μεταβλητών τιμών μία φορά χρησιμοποιώντας μια λεγόμενη εντολή phi (το όνομά του προέρχεται από το ελληνικό αλφάβητο). Το γεγονός είναι ότι για να δημιουργηθεί η αναπαράσταση κώδικα SSA για γλώσσες όπως η C, πρέπει να καταφύγετε σε κάποια κόλπα. Το αποτέλεσμα της κλήσης αυτής της εντολής είναι η τρέχουσα τιμή της μεταβλητής (i ή n), και μια λίστα βασικών μπλοκ χρησιμοποιείται ως παράμετρός του. Για παράδειγμα, εξετάστε αυτήν την οδηγία:
t0 = phi [entry: 0:int, for.body: t6] #n
Η σημασία του είναι η εξής: αν το προηγούμενο βασικό μπλοκ ήταν μπλοκ entry (εισαγωγή), τότε t0 είναι μια σταθερά 0, και αν το προηγούμενο βασικό μπλοκ ήταν for.body, τότε πρέπει να πάρετε την τιμή t6 από αυτό το μπλοκ. Μπορεί όλα αυτά να φαίνονται αρκετά μυστηριώδη, αλλά αυτός ο μηχανισμός είναι που κάνει το SSA να λειτουργεί. Από ανθρώπινη σκοπιά, όλα αυτά καθιστούν τον κώδικα δυσνόητο, αλλά το γεγονός ότι κάθε τιμή εκχωρείται μόνο μία φορά κάνει πολλές βελτιστοποιήσεις πολύ πιο εύκολες.
Σημειώστε ότι εάν γράψετε τον δικό σας μεταγλωττιστή, συνήθως δεν θα χρειαστεί να ασχοληθείτε με τέτοιου είδους πράγματα. Ακόμη και το Clang δεν παράγει όλες αυτές τις οδηγίες phi, χρησιμοποιεί μηχανισμό alloca (μοιάζει με την εργασία με συνηθισμένες τοπικές μεταβλητές). Στη συνέχεια, όταν εκτελείται ένα πάσο βελτιστοποίησης LLVM καλείται , οδηγίες 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 δεν υποστηρίζει slices και ως αποτέλεσμα, ως βελτιστοποίηση, ο μεταγλωττιστής TinyGo που δημιούργησε αυτόν τον ενδιάμεσο κώδικα χώρισε την περιγραφή αυτής της δομής δεδομένων σε μέρη. Θα μπορούσε να αντιπροσωπεύει τρία στοιχεία φέτας (ptr, len и cap) ως δομή (struct), αλλά η αναπαράστασή τους ως τρεις ξεχωριστές οντότητες επιτρέπει ορισμένες βελτιστοποιήσεις. Άλλοι μεταγλωττιστές ενδέχεται να αντιπροσωπεύουν το slice με άλλους τρόπους, ανάλογα με τις συμβάσεις κλήσης των λειτουργιών της πλατφόρμας προορισμού.
Ένα άλλο ενδιαφέρον χαρακτηριστικό αυτού του κώδικα είναι η χρήση της εντολής 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