Τεχνολογίες μεταγλώττισης και εκτέλεσης

Διομήδης Σπινέλλης
 Τμήμα Διοικητικής Επιστήμης και Τεχνολογίας
Οικονομικό Πανεπιστήμιο Αθηνών
dds@aueb.gr

Το χάσμα υλικού και λογισμικού

Οι δυνατότητες που προσφέρει το υλικό και το λογισμικό έρχονται συχνά σε αντίθεση ή αλληλοσυμπληρώνονται. Οι γλώσσες προγραμματισμού και τα λειτουργικά συστήματα είναι δύο τεχνολογίες που επιτρέπουν τη βέλτιστη συνύπαρξη του υλικού με το λογισμικό.

Υλοποίηση γλωσσών προγραμματισμού

Μια γλώσσα προγραμματισμού μπορεί - ανάλογα με τη γλώσσα - να υλοποιηθεί με τους παρακάτω τρόπους: καθώς και με συνδυασμούς τους.

Αρχιτεκτονική του μεταγλωττιστή

Η διεργασία της μεταγλώττισης μπορεί να διαχωριστεί στις παρακάτω ξεχωριστές λειτουργίες οι οποίες εκτελούνται σε διαδοχικές φάσεις:

Λεκτική ανάλυση

Ο λεκτικός αναλυτής παρέχει τις παρακάτω λειτουργίες: Με τον τρόπο αυτό διαχωρίζονται οι εργασίες της λεκτικής και της συντακτικής ανάλυσης και κάθε μια υλοποιείται με τον πιο αποδοτικό τρόπο.

Λεκτικές μονάδες

Χρήση λεκτικών μονάδων

Ο συντακτικός αναλυτής

Ο συντακτικός αναλυτής:

Παράδειγμα

    i = 0;
    while ( i < 10) {
        System.out.println(i);
        i = i + 1;
    }

(Το δέντρο μπορεί να κατασκευαστεί και ζωντανά από 17 άτομα.)

Συντακτικό δένδρο

Parse graph

Παραγωγή κώδικα

Η παραγωγή κώδικα αποτελεί το πιο ενδιαφέρον και σύνθετο στάδιο της μεταγλώττισης. Κατά το στάδιο αυτό μπορούν να υλοποιηθούν τεχνικές βελτιστοποίησης προσανατολισμένες στη συγκεκριμένη γλώσσα ή αρχιτεκτονική και να υλοποιηθούν αλγόριθμοι βέλτιστης χρήσης των στοιχείων της αρχιτεκτονικής. Η παραγωγή του τελικού εκτελέσιμου κώδικα μπορεί να διακριθεί στα παρακάτω στάδια:

Βελτιστοποίηση του ενδιάμεσου κώδικα

Η βελτιστοποίηση του κώδικα μετασχηματίζει τον κώδικα σε μια μορφή που παράγει τα ίδια αποτελέσματα με τον αρχικά αλλά βελτιωμένα κάποια κριτήρια απόδοσης. Τέτοια κριτήρια μπορεί να είναι:

Πλεονεκτήματα βελτιστοποίησης

Η βελτιστοποίηση μπορεί να απαλλάξει τον προγραμματιστή από αντιπαραγωγικές αλλαγές του κώδικα που έχουν ως στόχο να ικανοποιήσουν τα κριτήρια αυτά και να του επιτρέψει να συγκεντρωθεί σε άλλα ποιοτικά στοιχεία του παραγόμενου κώδικα όπως την ορθότητα, την ασφάλεια, τη διαθεσιμότητα, τη συντηρησιμότητα, και τη μεταφερσιμότητα. Συχνά βελτιστοποιήσεις που γίνονται από τον προγραμματιστή έρχονται σε αντίθεση με τα παραπάνω ποιοτικά στοιχεία.

Παράδειγμα βελτιστοποίησης

Απαλοιφή κοινών υποεκφράσεων (common subexpression elimination)
Εκφράσεις με κοινά στοιχεία υπολογίζονται μόνο μια φορά. Η ακολουθία: 
x = b / c;
y = 42 + b / c;
μετασχηματίζεται στην ακολουθία: 
x = b / c;
y = 42 + x;

Παράδειγμα βελτιστοποίησης

Μετακίνηση κώδικα βρόχων (loop code motion)
Εκφράσεις που δεν αλλάζουν μέσα σε ένα βρόχο μετακινούνται έξω από αυτόν. Η ακολουθία: 
{
    int a, b, z;

    a = 8; b = 4;
    for (i = 0; i < 10; i++) {
        z = a / b;
        System.out.println(z);
    }
}
μετασχηματίζεται στην ακολουθία: 
{
    int a, b, z;

    a = 8; b = 4;
    z = a / b;
    for (i = 0; i < 10; i++) {
        System.out.println(z);
    }
}

Παράδειγμα βελτιστοποίησης

Απαλοιφή άχρηστου κώδικα (dead code removal)
Κώδικας που δεν εκτελείται ποτέ απαλείφεται. Η ακολουθία: 
{
    int a, q;

    q = 48;
    return (q);
    a = q / 2;
}
μετασχηματίζεται στην ακολουθία: 
{
    int a, q;

    q = 48;
    return (q);
}

Παράδειγμα βελτιστοποίησης

Απαλοιφή κλήσεων σε συναρτήσεις (function inlining)
Κλήσεις σε συναρτήσεις μετασχηματίζονται σε απευθείας χρήση του αντίστοιχου κώδικα. Η ακολουθία: 
static int
square(int a) {
    return (a * a);
}

public static void main(String args[]) {
    System.out.println(square(12));
}
μετασχηματίζεται στην ακολουθία: 
public static void main(String args[]) {
    System.out.println(12 * 12);
}

Παράδειγμα βελτιστοποίησης

Απαλοιφή αναδρομής από το τέλος συνάρτησης (tail recursion elimination)
Αναδρομή στο τέλος μιας συνάρτησης μετασχηματίζεται σε βρόχο. Η ακολουθία: 
foo() {
    System.out.println("foo");
    foo();
}
μετασχηματίζεται στην ακολουθία: 
foo() {
    for (;;)
        System.out.println("foo");
}

Βελτιστοποίηση του τελικού κώδικα

Συχνά ο τελικός κώδικας που παράγεται μπορεί να περιέχει ακολουθίες εντολών οι οποίες να μπορούν να βελτιστοποιηθούν για το συγκεκριμένο επεξεργαστή. Οι ακολουθίες αυτές μπορούν να βρεθούν εξετάζοντας ένα μικρό παράθυρο του τελικού κώδικα, όπως αυτό θα φαίνονταν κοιτάζοντας τον κώδικα από μια κλειδαρότρυπα. Για το λόγο αυτό οι βελτιστοποιήσεις αυτές λέγονται και βελτιστοποιήσεις κλειδαρότρυπας (peephole optimizations).

Παράδειγμα βελτιστοποίησης τελικού κώδικα

Η ακολουθία: 
    mov $12, %rax
    mov %rax, %rbx
    mov $20, %rax
μετασχηματίζεται στην ακολουθία: 
    mov $12, %rbx
    mov $20, %rax
Επίσης η διάταξη των εντολών μπορεί να βελτιωθεί για να γίνεται καλύτερη χρήση πολλαπλών υπολογιστικών στοιχείων που διαθέτει ο επεξεργαστής. Για παράδειγμα σε ορισμένους επεξεργαστές η εναλλαγή εντολών κινητής υποδιαστολής με εντολές ακεραίων επιτρέπει στις δύο λειτουργικές μονάδες να δουλεύουν παράλληλα.

Σύνδεση

Κατά τη σύνδεση τα ανεξάρτητα μεταγλωττισμένα τμήματα του προγράμματος συνδέονται μεταξύ τους και με τις βιβλιοθήκες της γλώσσας για να δημιουργηθεί το τελικό εκτελέσιμο πρόγραμμα. Συχνά οι βιβλιοθήκες που χρησιμοποιούνται είναι κοινές ανάμεσα σε προγράμματα και φορτώνονται δυναμικά κατά το στάδιο εκτέλεσης του προγράμματος (Unix shared libraries, Windows DLLs). Κατά τη φάση της σύνδεσης γίνεται έλεγχος πως όλες οι συναρτήσεις και μεταβλητές που χρησιμοποιούνται έχουν οριστεί και, για ορισμένες γλώσσες όπως η C++, πως οι τύποι των συμβόλων που έχουν οριστεί σε διαφορετικά αρχεία είναι συμβατοί μεταξύ τους. Ορισμένες γλώσσες όπως η Java υλοποιούν μεγάλο μέρος της σύνδεσης κατά τη φόρτωση του προγράμματος στη μνήμη για εκτέλεση.

Ιδεατές μηχανές

Μια ιδεατή μηχανή (virtual machine) εμφανίζει στο λογισμικό που τρέχει πάνω σε αυτήν μια διαφορετική διεπαφή από αυτή στην οποία βασίζεται η μηχανή για την υλοποίησή της. Συχνά οι ιδεατές μηχανές υλοποιούνται σε ιεραρχία.

Πλεονεκτήματα και προβλήματα ιδεατών μηχανών

Διαχείριση μνήμης

Κατά τη διάρκεια ζωής του προγράμματος υπάρχουν απαιτήσεις για τη φύλαξη δεδομένων με διαφορετική διάρκεια ζωής. Συγκεκριμένα, πρέπει να υπάρχει υποστήριξη για δεδομένα που διατηρούνται:

Παράδειγμα διάταξης μνήμης

Στοίβα (stack)
...

...
Σωρός (heap)
(Δυναμική μνήμη)
...
Στατικά δεδομένα (static data)
...
Μεταγλωττισμένος κώδικας (code (text))

Τρόποι διαχείρισης μνήμης

Όταν ο όγκος της κύριας μνήμης του υπολογιστή δεν επαρκεί μπορεί να χρησιμοποιηθεί:

Τέλος, για οικονομία στο χώρο που απαιτεί ο κώδικας των προγραμμάτων σε δευτερεύουσα αποθήκευση, χρησιμοποιούνται συχνά μοιρασμένες βιβλιοθήκες (shared libraries) (π.χ. .DLL, .so).

Άσκηση: ορίσματα, εκφράσεις, βρόχοι και αποφάσεις

Άσκηση 2

Μπορείτε να κατεβάσετε το αντίστοιχο αρχείο και να στείλετε τους βαθμούς σας από τους δεσμούς που βρίσκονται στη σελίδα των ασκήσεων.

Βιβλιογραφία

Περιεχόμενα