Συμβατική μηχανή και συμβολική γλώσσα

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

Άξονες σχεδιασμού αρχιτεκτονικής εντολών

Η αρχιτεκτονική εντολών ενός επεξεργαστή σχεδιάζεται γύρω από τους παρακάτω άξονες:

Που φυλάσσονται στον επεξεργαστή οι τελεστέοι όταν δεν προέρχονται από τη μνήμη;
- Στοίβα
- Γενικός καταχωρητής (accumulator)
- Σύνολο καταχωρητών
Αριθμός ρητών τελεστέων (explicit operands) ανά εντολή (0-3)
Πόσοι από τους τελεστέους μπορεί να βρίσκονται στη μνήμη;
Τι εντολές παρέχονται;
Είδος και μέγεθος τελεστέων
- Ακέραιοι 8, 16, 32, 64 bit
- Αριθμοί κινητής υποδιαστολής μονής και διπλής ακρίβειας
- Χαρακτήρες
- Συσκευασμένοι δεκαδικοί (packed decimal) αριθμοί
- Συμβολοσειρές (character strings)
- Σειρές bit (bit strings)

Η οικογένεια επεξεργαστών iAPX86

8080 (8 bit, ο πρόγονος)
8086/8088 (16 bit)
80286 (24 bit, προστατευμένος ρυθμός)
80386 (32 bit, ιδεατή μνήμη)
80486 (απόδοση, μαθηματικός επεξεργαστής)
Pentium (παράλληλη εκτέλεση εντολών)
Pentium MMX (εκτέλεση πολλαπλών ακέραιων δεδομένων)
Pentium II (δυναμική εκτέλεση εντολών, διπλός δίαυλος)
Pentium III (εκτέλεση πολλαπλών δεδομένων κινητής υποδιαστολής)

Καταχωρητές

Το μοντέλο καταχωρητών ειδικής χρήσης
Καταχωρητές δεδομένων
- EAX (AX (AH/AL)): Συσσωρευτής (Accumulator)
- EBX (BX (BH/BL)): Βάση μνήμης
- ECX (DX (CH/CL)): Μετρητής
- EDX (DX (DH/DL)): Πολλαπλασιασμός, διαίρεση
Καταχωρητές διευθύνσεων
- SP: (stack pointer) Δείκτης στοίβας (Stack pointer)
- BP: (base pointer) Βάση μνήμης
- SI: (source index) Δείκτης προέλευσης
- DI: (desination index) Δείκτης προορισμού
Καταχωρητές τμημάτων μνήμης
- CS: (code segment) Τμήμα εντολών
- DS: (data segment) Τμήμα δεδομένων
- SS: (stack segment) Τμήμα στοίβας
- ES: (extra segment) Πρόσθετο τμήμα
- FS: (extra segment) Πρόσθετο τμήμα
- GS: (extra segment) Πρόσθετο τμήμα
Καταχωρητές ελέγχου
- IP: (instruction pointer) Μετρητής εντολής
- FLAGS: Ενδείκτες (Flags)

Προσδιορισμός τελεστέων

Σημείωση

Η σύνταξη που χρησιμοποιούμε είναι αυτή των συμβολομεταφραστών της AT&T που υποστηρίζονται στο λειτουργικό σύστημα Unix (π.χ. GNU as). Η σύνταξη αυτή διαφέρει σημαντικά από αυτή που χρησιμοποιεί η Intel.

Περιεχόμενο καταχωρητή: %EAX
'Αμεσος τελεστέος (Immediate operand): $1234
'Αμεση διεύθυνση (Direct address): 1234(,1)
Έμμεση διεύθυνση από καταχωρητή (Register indirect address): (%ebx)
Διεύθυνση με βάση (Based address): 1234(%ebx)
Διεύθυνση με δείκτη (Indexed address): 1234(%esi)
Διεύθυνση με βάση και δείκτη (Based indexed address): 1234(%esi,%ebx)
Διεύθυνση με βάση, δείκτη και πολλαπλασιαστή (Based indexed scaled address): 1234(%esi,%ebx,4)

Το μέγεθος του τελεστή ορίζεται από το τελευταίο γράμμα της εντολής:

l: long (4 byte, long ή int)
w: word (2 byte, short)
b: byte (1 byte, char)

Συνδιασμοί τελεστών:

Καταχωρητής, Καταχωρητής (π.χ. addl %eax, %eax)
'Αμεσος, Καταχωρητής (π.χ. subl $3, %ecx)
Μνήμη, Καταχωρητής (π.χ. addl 54(%esi), %ax)
'Αμεσος, Μνήμη (π.χ. movl $45, 12(%ebp, %esi))

Απόδοση εντολών με στοίβα

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

Παράδειγμα

Συνάρτηση σε C (μια ρίζα δευτεροβάθμιας εξίσωσης):

#include <math.h>

double
root1(double a, double b, double c)
{
	double d;

	d = b * b - 4.0 * a * c;
	return (-b + sqrt(d)) / (2.0 * a);
}

Αντίστοιχος κώδικας σε συμβολική γλώσσα. Η πρόσβαση στη στοίβα γίνεται με τη ST(Ν) όπου Ν ο αριθμός του στοιχείου στη στοίβα.

CONST	SEGMENT
$FOUR	DQ	04010000000000000r		; 4
CONST	ENDS
_TEXT	SEGMENT
_a$ = 8
_b$ = 16
_c$ = 24
_root1	PROC NEAR
	fld	QWORD PTR _c$[esp-4]
	fmul	QWORD PTR _a$[esp-4]
	fld	QWORD PTR _b$[esp-4]
	fmul	ST(0), ST(0)
	fld	QWORD PTR _a$[esp-4]
	fxch	ST(2)
	fmul	QWORD PTR $FOUR
	fxch	ST(2)
	fadd	ST(0), ST(0)
	fxch	ST(2)
	fsubp	ST(1), ST(0)
	fsqrt
	fsub	QWORD PTR _b$[esp-4]
	fxch	ST(1)
	fdivp	ST(1), ST(0)
	ret	0
_root1	ENDP
_TEXT	ENDS
END

Παράσταση εντολών

Δυαδική παράσταση: 01000011
Συμβολική παράσταση: incl %ebx
Αναπτυσσόμενος κωδικός πράξης (expanding opcode)

Κωδικοποίηση εντολών σε επεξεργαστές της Intel

Βασική κωδικοποίηση εντολών

Κωδικοποίηση εντολών ενός byte

Το byte ModR/M προσδιορίζει τις διευθύνσεις των εντολών

Το byte SIB (scale, index, base) επιτρέπει τον ορθόγωνο προσδιορισμό κλίμακας, δείκτη και βάσης.

Ενδείκτης διακλάδωσης

CF:: (Carry flag)
Κρατούμενο (Carry):
1 αν η πράξη δημιούργησε κρατούμενο.
ZF:: (Zero flag)
Μηδέν:
1 αν το αποτέλεσμα της πράξης είναι 0.
SF:: (Sign flag)
Πρόσημο (sign)
1 αν το αποτέλεσμα είναι αρνητικός αριθμός.
PF:: (Parity flag)
Ισοτιμία
1 αν το αποτέλεσμα έχει μονό αριθμό από bit που είναι 1.
OF:: (Overflow flag)
Υπερχείλιση:
1 αν το αποτέλεσμα δε μπορεί να παρασταθεί ως θετικός η αρνητικός αριθμός.

Εντολές μεταφοράς δεδομένων

mov πηγή, προορισμός: (Move)
Μεταφορά
πηγή -> προορισμό
push πηγή: Μεταφορά στη στοίβα
%esp <- %esp - $4
(%esp) <- πηγή
pop προορισμός: Μεταφορά από τη στοίβα
προορισμός <- (%esp)
%esp <- %esp + $4
xchg προορισμός, πηγή: (Exchange)
Εναλλαγή
προορισμός <- πηγή
πηγή <- προορισμός
(ταυτόχρονα)

Αριθμητικές εντολές

add πηγή, προορισμός: (Add)
Πρόσθεση
προορισμός <- προορισμός + πηγή
inc προορισμός: (Increment)
Αύξηση κατά ένα
προορισμός <- προορισμός + 1
sub πηγή, προορισμός: (Subtract)
Αφαίρεση
προορισμός <- προορισμός - πηγή
dec προορισμός: (Decrement)
Μείωση κατά ένα
προορισμός <- προορισμός - 1
neg προορισμός: (Negate)
Αλλαγή προσήμου
προορισμός <- - προορισμός
cmp πηγή, προορισμός: (Compare)
Σύγκριση
Εκτελείται η πράξη προορισμός - πηγή και ενημερώνονται οι ενδείκτες διακλάδωσης.
mul πηγή: (Multiply)
Πολλαπλασιασμός
%edx:%eax <- %eax * πηγή
div πηγή: (Divide)
Διαίρεση
%eax <- %edx:%eax / πηγή
%edx <- %edx:%eax mod πηγή
Για να μετατρέψουμε τον ακέραιο 32 bit στον καταχωρητή %eax σε ακέραιο διαιρετέο 64 bit στο ζευγάρι καταχωρητών %edx:%eax (όπως απαιτεί η div) χρησιμοποιούμε την εντολή cltd (χωρίς παραμέτρους) (convert long to double long).

Εντολές δυαδικών ψηφίων

and πηγή, προορισμός: Σύζευξη
προορισμός <- προορισμός & πηγή
or πηγή, προορισμός: Διάζευξη
προορισμός <- προορισμός | πηγή
xor πηγή, προορισμός: Αποκλειστική διάζευξη
προορισμός <- προορισμός ^ πηγή
not προορισμός: Αντιστροφή
προορισμός <- ~ προορισμός
test πηγή, προορισμός: Έλεγχος
shl αριθμός, προορισμός: (Shift left)
Ολίσθηση (Shift) αριστερά
προορισμός <- προορισμός << πηγή
shr αριθμός, προορισμός: (Shift right)
Ολίσθηση δεξιά
προορισμός <- προορισμός >> πηγή
sar αριθμός, προορισμός: (Shift arithmetic right)
Αριθμητική ολίσθηση δεξιά
προορισμός <- προορισμός >> πηγή
rol αριθμός, προορισμός: (Rotate left)
Περιστροφή αριστερά
ror αριθμός, προορισμός: (Rotate right)
Περιστροφή δεξιά
bsf προορισμός, πηγή: (Bit scan forward)
Εύρεση πρώτου bit με τιμή 1 στην πηγή
bsr προορισμός, πηγή: (Bit scan reverse)
Αντίστροφη εύρεση πρώτου bit με τιμή 1 στην πηγή
bt πηγή, αριθμός: (Bit test)
Έλεγχος bit σε σειρά από bit
btc προορισμός, αριθμός: (Bit test and complement)
Αντιστροφή bit σε σειρά από bit
btr προορισμός, αριθμός: (Bit test and reset)
Μηδενισμός bit σε σειρά από bit
bts προορισμός, αριθμός: (Bit test and set)
Θέτει σε 1 bit σε σειρά από bit

Εντολές άλματος

JMP προορισμός: Άλμα
CALL προορισμός: Κλήση
RET: (Return)
Επιστροφή
JA/JNBE προορισμός: (Jump above)
Άλμα αν μεγαλύτερο (χωρίς πρόσημο)
JAE/JNB προορισμός: (Jump above or equal)
Άλμα αν μεγαλύτερο ή ίσο (χωρίς πρόσημο)
JB/JNAE προορισμός: (Jump bellow)
Άλμα αν μικρότερο (χωρίς πρόσημο)
JBE/JNA προορισμός: (Jump below or equal)
Άλμα αν μικρότερο ή ίσο (χωρίς πρόσημο)
JC προορισμός: (Jump carry)
Άλμα αν κρατούμενο
JNC προορισμός: (Jump no carry)
Άλμα αν όχι κρατούμενο
JE/JZ προορισμός: (Jump equal)
Άλμα αν ίσο
JNE/JNZ προορισμός: (Jump not equal)
Άλμα αν όχι ίσο
JG/JNLE προορισμός: (Jump greater)
Άλμα αν μεγαλύτερο (με πρόσημο)
JGE/JNL προορισμός: (Jump greater or equal)
Άλμα αν μεγαλύτερο ή ίσο (με πρόσημο)
JL/JNGE προορισμός: (Jump less)
Άλμα αν μικρότερο (με πρόσημο)
JLE/JNG προορισμός: (Jump less or equal)
Άλμα αν μικρότερο ή ίσο (με πρόσημο)
JO προορισμός: (Jump overflow)
Άλμα αν υπερχείλιση
JNO προορισμός: (Jump no overflow)
Άλμα αν όχι υπερχείλιση
JS προορισμός: (Jump sign)
Άλμα αν πρόσημο
JNS προορισμός: (Jump no sign)
Άλμα αν όχι πρόσημο

Παγίδες

Η παγίδα (trap) εξασφαλίζει την αυτόματη κλήση κώδικα μόλις ικανοποιηθεί κάποια (μη κανονική) συνθήκη.
Παραδείγματα :
- Υπερχείλιση (overflow) πράξεων
- Απώλεια ακρίβειας
- Υποχείλιση στοίβας
- Αντικανονική πρόσβαση στη μνήμη
- Παραβίαση προστασίας
- Διαίρεση με το 0
Είναι ακόμα δυνατή η κλήση παγίδας μέσω λογισμικού (software trap). Ο τρόπος αυτός χρησιμοποιείται συχνά για κλήση συναρτήσεων του λειτουργικού συστήματος μια και εξασφαλίζει την αλλαγή κατάστασης του επεξεργαστή σε προστατευμένο ρυθμό.

Διακοπές

Η διακοπή (interrupt) εξασφαλίζει την αυτόματη κλήση κώδικα μόλις ικανοποιηθεί κάποια εξωτερική συνθήκη.
Παραδείγματα :
- Τέλος Ε/Ε από περιφερειακό
- Σήμα από το ρολόι πραγματικού χρόνου
- Λάθος μνήμης
Στους επεξεργαστές τις Intel οι παγίδες και οι διακοπές έχουν τον ίδιο χειρισμό.

Αποσφαλμάτωση

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

Σημεία διακοπής (breakpoint): Διακοπή του προγράμματος μέσω παγίδας όταν η εκτέλεση φτάσει σε ένα σημείο.
Εκτέλεση εντολών βήμα-βήμα (single step execution): Εκτέλεση μιας παγίδας μετά από την εκτέλεση κάθε εντολής.
Σημεία διακοπής δεδομένων (data breakpoint): Διακοπή του προγράμματος μέσω παγίδας όταν υπάρξει πρόσβαση σε συγκεκριμένη μνήμη.

Παράλληλα εντολές επιτρέπουν τον καθαρισμό της κρυφής μνήμης για την υλοποίηση προγραμμάτων που μετατρέπουν τον εαυτό τους.

Λειτουργίες του συμβολομεταφραστή

Χρήση συμβολικών εντολών
Χρήση συμβολικών τελεστέων
Αυτόματη ανάθεση διευθύνσεων
Δημιουργία αρχείων συνδέτη
Σχόλια
Υπολογισμός σταθερών
Μακροεντολές

Δομή του πηγαίου κώδικα

Ο πηγαίος κώδικας της συμβολικής γλώσσας είναι δομημένος με βάση ξεχωριστές γραμμές κώδικα.
Κάθε γραμμή μπορεί να περιέχει μία και μόνο μία εντολή.
Οι εντολές δεν απαιτείται να τερματίζονται με κάποιον ειδικό χαρακτήρα.
Τα σχόλια γράφονται με τη μορφή της C++:
```
// This is a comment
```
Ο συμβολομεταφραστής δέχεται και ειδικές εντολές. Αυτές αρχίζουν πάντα με μια τελεία:
```
.text
```
Οι εντολές χωρίζονται από τις παραμέτρους και τους τελεστέους με κενά.
Οι τελεστέοι χωρίζονται μεταξύ τους με κόμμα.

Παράδειγμα:

	cmp $10,%ebx
	je end
	push %ebx
	mov %ebx, %esi
	inc %esi
	push $intform

Προσδιορισμός σταθερών

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

ακέραιους στο δεκαδικό σύστημα (π.χ. 10, 454, 23)
ακέραιους στο δεκαεξαδικό (hexadecimal) σύστημα αρχίζοντάς τους με 0x (π.χ. 0x5e, 0x34, 0xa23f)
χαρακτήρες αρχίζοντάς τους με ένα μονό εισαγωγικό (π.χ. 'a, '4, '\n)

Μπορούμε να συνδυάσουμε σταθερές με τελεστές με σημασιολογία ίδια με αυτή της C. Μοναδιαίοι (unary) τελεστές:

Δυαδικοί (binary) τελεστές:

Μέγιστη προτεραιότητα
- *
- /
- %
- <<
- >>
Ενδιάμεση προτεραιότητα
- |
- &
- ^
Ελάχιστη προτεραιότητα
- +
- -

Η εισαγωγή των σταθερών στη μνήμη γίνεται με εντολές του συμβολομεταφραστή:

Στο συμβολομεταφραστή gas οι σταθερές εισάγονται με τις παρακάτω εντολές:

.byte
Εισαγωγή σταθερών με μήκος 1 byte
.short
Εισαγωγή σταθερών με μήκος 2 byte
.word
Εισαγωγή σταθερών με μήκος 4 byte
.string
Εισαγωγή συμβολοσειρών
Μετά από κάθε εντολή μπορούν να γραφούν μια ή περισσότερες σταθερές χωρισμένες με κόμμα.

Παράδειγμα:

.byte	'a', 'b'
.short 578
.word 324234
.string "hello, world\n"

Χρήση συμβόλων

Σε αρχεία πηγαίου κώδικα του συμβολομεταφραστή μπορούμε να αναφερθούμε με συμβολικό τρόπο σε διευθύνσεις μνήμης (memory addresses) δεδομένων ή κώδικα.
Ο κώδικας και τα δεδομένα που γράφουμε καταχωρούνται σε αυξανόμενες διευθύνσεις μνήμης.
Μπορούμε να αποδώσουμε την τρέχουσα διεύθυνση μνήμης σε μια συμβολική σταθερά (ετικέτα (label))) γράφοντας στην αρχή της γραμμής το όνομα της σταθεράς (σύμφωνα με τους κανόνες ονομασίας μεταβλητών της C) ακολουθούμενο από μια άνω κάτω τελεία:
```
thisaddress:
```

Παράδειγμα:

intform: .string	"%d\n"
.globl main
main:
	mov  $0, %ebx
loop:
	cmp $10,%ebx

Βιβλιογραφία και πηγές στο Internet

Andrew S. Tanenbaum Η αρχιτεκτονική των υπολογιστών: μια δομημένη προσέγγιση. Τρίτη αμερικάνικη έκδοση. σ. 273-368, 467-502. Κλειδάριθμος 1995.
Εμμ. Σ. Σκορδαλάκης. Εισαγωγή στους Μεταγλωττιστές σ. 172-180, 246. Συμμετρία 1993.

Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman. Compilers, Principles, Techniques, and Tools, pages 519–520. Addison-Wesley, 1985.
Dawson R. Engler and Wilson C. Hsieh. DERIVE: A tool that automatically reverse-engineers instruction encodings. In Proceedings of the ACM SIGPLAN Workshop on Dynamic and Adaptive Compilation and Optimization (Dynamo '00), pages 12–22. ACM Press, July 2000. ACM SIGPLAN Notices 35(7).
Free Software Foundation. Using as, 1999. http://www.gnu.org/manual/gas-2.9.1/.
John L. Hennessy and David A. Patterson. Computer Architecture: A Quantitative Approach, pages 89–197. Morgan Kaufmann Publishers, second edition, 1996.
Intel Corporation. The Intel Architecture Software Developer's Manual, Volume 1: Basic Architecture, 1999. http://www.intel.com/design/PentiumII/manuals/243190.htm.
Intel Corporation. Intel Architecture Software Developer's Manual, Volume 2: Instruction Set Reference Manual, 1999. http://www.intel.com/design/PentiumII/manuals/243190.htm.
Jr. Philip J. Koopman. Stack Computers: the New Wave. Ellis Horwood, 1989. Available online http://www.cs.cmu.edu/~koopman/stack_computers/index.html.

Ασκήσεις

Πως θα κωδικοποιηθεί η παρακάτω ακολουθία εντολών Intel IA32;

movl -140(%ebp),%eax
movl (%edx,%eax,8),%ecx
addl %ecx,%ecx
movl %ecx,(%edx,%eax,8)
movl -140(%ebp),%eax
incl %eax

Τι εντολές Intel IA32 παριστάνει η παρακάτω ακολουθία;
```
55
89 E5
81 EC B8 00 00 00
C7 85 74 FF FF FF 00 00 00 00
```

Στην απάντησή σας να δείξετε πως καταλήξατε σε κάθε αποτέλεσμα.

Περιεχόμενα