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

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

Εισαγωγή

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

Παραγωγή ενδιάμεσου κώδικα

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

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

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

Ορισμένες κοινές βελτιστοποιήσεις είναι οι παρακάτω:

Απαλοιφή κοινών υποεκφράσεων
Εκφράσεις με κοινά στοιχεία υπολογίζονται μόνο μια φορά. Για παράδειγμα η ακολουθία:
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;
                printf("%d\n", z);
        }
}
μετασχηματίζεται στην ακολουθία:
{
        int a, b, z;

        a = 8; b = 4;
        z = a / b;
        for (i = 0; i < 10; i++) {
                printf("%d\n", z);
        }
}
Απαλοιφή άχρηστου κώδικα
Κώδικας που δεν εκτελείται ποτέ απαλείφεται. Για παράδειγμα η ακολουθία:
{
        int a, q;

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

        q = 48;
        return (q);
}
Απαλοιφή κλήσεων σε συναρτήσεις (function inlining)
Κλήσεις σε συναρτήσεις μετασχηματίζονται σε απευθείας χρήση του αντίστοιχου κώδικα. Για παράδειγμα η ακολουθία:
int
sqr(int a)
{
        return (a * a);
}

main()
{
        printf("%d\n", sqr(12));
}
μετασχηματίζεται στην ακολουθία:
main()
{
        printf("%d\n", (12 * 12));
}
Απαλοιφή αναδρομής από το τέλος συνάρτησης (tail recursion elimination)
Αναδρομή στο τέλος μιας συνάρτησης μετασχηματίζεται σε βρόχο. Για παράδειγμα η ακολουθία:
foo()
{
        printf("foo\n");
        foo();
}
μετασχηματίζεται στην ακολουθία:
foo()
{
        for (;;)
                printf("foo\n";);
}

Παραγωγή τελικού κώδικα

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

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

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

Για παράδειγμα η ακολουθία:

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

Σύνδεση

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

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

Creative Commons License  Τελευταία αλλαγή: Τρίτη, 19 Σεπτεμβρίου 2006 6:27 μμ
 Εκτός αν αναφέρεται κάτι διαφορετικό, όλο το πρωτότυπο υλικό της σελίδας αυτής του οποίου δημιουργός είναι ο Διομήδης Σπινέλλης παρέχεται σύμφωνα με τους όρους της άδειας «Creative Commons Attribution-Share Alike 3.0 Greece License».