Το κάλεσμα διαδικασίας (procedure call) γίνεται μέσω της εντολής jal (jump and link - άλμα και σύνδεση), η δε επιστροφή από διαδικασία (procedure return) γίνεται μέσω της εντολής jr (jump register - άλμα εκεί που δείχνει ένας καταχωρητής), όπως είδαμε στην άσκηση 6.
 

Τίνος Ευθύνη είναι το Σώσιμο των Καταχωρητών:

• Α: "η καλούσα διαδικασία" (caller), και την
• Β: "η καλουμένη διαδικασία" (callee).

  Προσωρινοί Καταχωρητές $t0 - $t9 ($8-$15 και $24-$25) -- temporary registers: Η τιμή των καταχωρητών αυτών δεν διατηρείται μετά από ένα κάλεσμα διαδικασίας (not preserved across call), δηλαδή η καλούμενη διαδικασία (ή άλλες που τυχόν καλιούνται από αυτήν) επιτρέπεται να μεταβάλει την τιμή αυτών των καταχωρητών χωρίς προηγουμένως να σώσει την τιμή που τυχόν είχε μείνει εκεί από την καλούσα διαδικασία, επομένως και χωρίς να επαναφέρει την παλαιά εκείνη τιμή προ της επιστροφής στην καλούσα διαδικασία. Αρα, αν η καλούσα διαδικασία έχει κάτι χρήσιμο μέσα σε έναν τέτοιο καταχωρητή ενώ ετοιμάζεται να καλέσει μιάν άλλη διαδικασία, το οποίο χρήσιμο επιθυμεί να το ξαναβρεί στη θέση του μετά την επιστροφή του καλέσματος, είναι ευθύνη της καλούσας διαδικασίας να σώσει την χρήσιμη τιμή πριν το κάλεσμα ("caller-saved"), και να την επαναφέρει αμέσως μετά από αυτό (δηλ. μετά την επιστροφή του). Προσωρινές τιμές των οποίων η διάρκεια ζωής (lifetime) δεν περιλαμβάνει καλέσματα διαδικασιών συμφέρει να τοποθετούνται σε τέτοιους καταχωρητές, διότι δεν χρειάζεται να σώσουμε τα παλαιά περιεχόμενα (από αυτόν που μας κάλεσε) αυτών των καταχωρητών πριν τους χρησιμοποιήσουμε.

[Σημείωση: "διάρκεια ζωής (lifetime)" μιάς μεταβλητής ή ενός καταχωρητή λέγεται η χρονική περίοδος (ή οι εντολές που περιλαμβάνονται) από τη στιγμή πού στη μεταβλητή ή στον καταχωρητή εκχωρείται μία τιμή, μέχρι την τελευταία ανάγνωση της τιμής αυτής πριν την επόμενη εκχώρηση νέας τιμής σε αυτή τη μεταβλητή ή τον καταχωρητή. Μετά το τέλος μιάς διάρκειας ζωής μιάς μεταβλητής ή ενός καταχωρητή, και μέχρι την έναρξη της επόμενης διάρκειας ζωής της/του, η μεταβλητή ή ο καταχωρητής θεωρείται "νεκρή/νεκρός", διότι η τιμή της/του δεν μας ενδιαφέρει --κανείς δεν πρόκειται να την διαβάσει πριν την ξαναλλάξουμε-- άρα είμαστε ελεύθεροι να την καταστρέψουμε].

Διατηρούμενοι Καταχωρητές $s0 - $s7 ($16-$23) -- saved registers: Η τιμή των καταχωρητών αυτών διατηρείται μετά από ένα κάλεσμα διαδικασίας (preserved across call), δηλαδή είναι ευθύνη της καλούμενης διαδικασίας να σώσει την παλαιά τιμή κάθε τέτοιου καταχωρητή πριν την χαλάσει ("callee-saved"), και να την επαναφέρει στη θέση της πριν επιστρέψει στην καλούσα διαδικασία. Αρα, η καλούσα διαδικασία μπορεί να αφήνει χρήσιμες τιμές σε αυτούς τους καταχωρητές, πριν καλέσει άλλες διαδικασίες, και να τις ξαναβρίσκει μετά την επιστροφή από αυτές, χωρίς να χρειάζεται --η καλούσα διαδικασία-- να κάνει κάτι ιδιαίτερο γι' αυτό. Μεταβλητές και τιμές των οποίων η διάρκεια ζωής (lifetime) περιλαμβάνει πολλά καλέσματα διαδικασιών, με επανειλημμένη χρήση της παλαιάς τιμής τους μεταξύ των καλεσμάτων, συμφέρει να τοποθετούνται σε τέτοιους καταχωρητές, διότι, αν οι καλούμενες διαδικασίες (και οι τυχόν δικοί τους απόγονοι) δεν χρησιμοποιούν αυτούς τους καταχωρητές, γλιτώνουμε τα πολλαπλά σωσίματα και επαναφορές (σώζουμε και επαναφέρουμε μόνο μία φορά την τιμή που είχε αφήσει εκεί η διαδικασία που κάλεσε εμάς τους ίδιους).
 

Άλλοι Καταχωρητές:

• $ra ($31) Return Address: κάθε κάλεσμα διαδικασίας καταστρέφει το προηγούμενο περιεχόμενο του καταχωρητή αυτού, άρα κάθε διαδικασία που καλεί άλλες διαδικασίες (δηλ. κάθε διαδικασία που δεν είναι φύλλο στο δέντρο των καλεσμάτων) πρέπει να σώσει τη διεύθυνση επιστροφής της στην αρχή της εκτέλεσής της (πριν το πρώτο κάλεσμα), και να την επαναφέρει αφού επιστρέψει το τελευταίο παιδί της, πριν να επιστρέψει η ίδια. (Το σημείο αυτό είναι ασαφές στο σχήμα 3.11 του βιβλίου (σελ. 138): η διεύθυνση επιστροφής στην οποία αναφέρεται εκείνο το σχήμα είναι η διεύθυνση του παρόντος καλέσματος, και όχι η διεύθυνση επιστροφής της διαδικασίας μέσα από την οποία γίνεται το κάλεσμα).
• $sp ($29) Stack Pointer, $fp ($30) Frame Pointer: όποιος τους αλλάζει τους επαναφέρει κιόλας. Πολλοί compilers δεν χρησιμοποιούν frame pointer --το ίδιο κάνει και το βιβλίο στην παράγρ. 3.6, και το ίδιο θα κάνουμε και εμείς. Γιά το πώς θα μπορούσε να χρησιμοποιηθεί ο frame pointer δείτε (προαιρετικά) την παράγρ. Α.6 του Παραρτήματος του βιβλίου.
   
• $gp ($28) Global Area Pointer: Δεν τον αλλάζει (ούτε τον σώζει) καμία διαδικασία. Δείχνει στη μέση μιάς περιοχής μνήμης μεγέθους 64 KBytes τα περιεχόμενα της οποίας μπορούμε να προσπελάσουμε με μία μόνο εντολή load ή store χρησιμοποιώντας αυτόν τον καταχωρητή, και στην οποία επομένως συμφέρει να τοποθετούνται οι γενικές (global) βαθμωτές (scalar) μεταβλητές του προγράμματος.
• $k0-$k1 ($26-$27) Kernel Reserved, $at ($1) Assembler Temporary: δεν τους χρησιμοποιούν οι compilers και τα προγράμματα χρήστη --κρατημένοι γιά το λειτουργικό σύστημα και τον Assembler.
• $zero ($0) = 0: περιέχει την σταθερά (hardwired) μηδέν. Επιτρέπονται εγγραφές σε αυτόν, αλλά δεν αλλάζουν το μηδενικό (hardwired) περιεχόμενο του.
   
• $a0-$a3 ($4-$7) Procedure Argument Registers: περιέχουν τα πρώτα 4 ορίσματα (arguments) της διαδικασίας. Αν υπάρχουν περισσότερα από 4 ορίσματα, τα υπόλοιπα περνιούνται στη στοίβα. Αν υπάρχουν λιγότερα από 4 ορίσματα, τότε οι υπόλοιποι (μη χρησιμοποιούμενοι) καταχωρητές $a3-$a0 χρησιμοποιούνται σαν τους προσωρινούς καταχωρητές $t0-$t9. Π.χ., αν η παρούσα διαδικασία έχει δύο ορίσματα μόνο, τότε είναι ελεύθερη να χρησιμοποιήσει τους $a2, $a3 σαν προσωρινούς καταχωρητές χωρίς να σώσει τις τιμές τους, αρκεί να μην ζητά να διατηρούνται αυτές οι τιμές όταν καλεί παιδιά της: αν τα παιδιά της έχουν πολλά ορίσματα τότε πρέπει να τους χρησιμοποιήσει γιά να βάλει εκεί τα ορίσματά τους, κι αν έχουν λίγα ορίσματα τότε επιτρέπεται τα παιδιά αυτά να χαλάσουν τις τιμές των $a2, $a3. Κατ' αναλογία, και οι $a0, $a1 περιέχουν τα ορίσματα της παρούσας διαδικασίας μόνο μέχρι το κάλεσμα του πρώτου παιδιού της --γιά το κάλεσμα αυτό, οι καταχωρητές αυτοί πρέπει να χρησιμοποιηθούν γιά τα ορίσματα των παιδιών (ή σαν προσωρινοί των παιδιών αν τα ορίσματά τους είναι λιγότερα).
• $v0-$v1 ($2-$3) Procedure Return Values: περιέχει (ο $v0) την τιμή που κάθε διαδικασία επιστρέφει στην καλούσα διαδικασία (ανάλογα και ο $v1 γιά την περίπτωση επιστροφής δύο τιμών). Η τιμή που επεστράφη ισχύει μόνο μέχρι το επόμενο κάλεσμα διαδικασίας. Ο μη χρησιμοποιούμενος καταχωρητής επιστροφής τιμών (π.χ. $v1) χρησιμοποιείται σαν τους προσωρινούς καταχωρητές $t0-$t9.
   

Πού Σώζονται οι Καταχωρητές:

Η στοίβα (χρήστη) στον MIPS ξεκινάει από τη διεύθυνση 7f.ff.ff.ff (δεκαεξαδικό), δηλαδή από τη μέση της μνήμης, και μεγαλώνει προς τις μικρότερες διευθύνσεις (προς τη διεύθυνση 0). Ο $sp δείχνει στην τελευταία χρησιμοποιούμενη λέξη της στοίβας. Πριν αποθηκεύσουμε Ν νέες λέξεις στη στοίβα πρέπει να ελαττώσουμε τον $sp κατά 4Ν, πράγμα που ισοδυναμεί με την δήλωση από πλευράς του προγράμματός μας (προς το λειτουργικό σύστημα, σε περίπτωση διακοπής (interrupt)) ότι τώρα η στοίβα μας είναι μεγλύτερη κατά Ν λέξεις. Η αντίστροφη πράξη (αύξηση του $sp κατά 4Ν --απελευθέρωση μνήμης) πρέπει να γίνει αφού πάρουμε τις αποθηκευμένες λέξεις και δεν τις χρειαζόμαστε άλλο πιά στη στοίβα. Οι τιμές που βρίσκονται αποθηκευμένες στη στοίβα προσπελαύνονται συνήθως μέσω εντολών load και store με διευθυνσιοδότηση σχετικά με τον $sp. Καθώς ο $sp αυξομειώνεται λόγω παραχώρησης/απελευθέρωσης μνήμης, η απόσταση των αποθηκευμένων τιμών στη στοίβα από τον $sp αλλάζει, αλλά παραμένει πάντοτε γνωστή στον compiler/προγραμματιστή (εκτός των περιπτώσεων δυναμικής παραχώρησης μνήμης στη στοίβα --πράγμα σπάνιο στις γλώσσες προγραμματισμού-- οπότε και απαιτείται η χρήση του $fp).
 
 
 

Άσκηση 9: Αναδρομική Διαδικασία Fibonacci

Γράψτε σε Assembly του MIPS και τρέξτε στο προσομοιωτή SPIM μιά αναδρομική διαδικασία η οποία θα υλοποιεί τη συνάρτηση του Fibonacci:

με αρχικές τιμές: f(0)=0, και f(1)=1. Γιά αρνητικούς αριθμούς, neg<0, η συνάρτηση f(neg)=-1.

Το κυρίως πρόγραμμά σας θα είναι ένας άπειρος βρόχος ο οποίος θα αρχικοποιεί τις γενικές (global) μεταβλητές, θα ζητά και θα διαβάζει έναν ακέραιο αριθμό n, θα καλεί τη διαδικασία f(n), θα τυπώνει το αποτέλεσμα που αυτή επέστρεψε --καθώς και το συνολικό πλήθος των λέξεων που "σώθηκαν" στη στοίβα (βλ. παρακάτω)-- και μετά θα ξαναρχίζει πάλι από την αρχή. Το πρόγραμμά σας θα διατηρεί τρείς γενικές (global) μεταβλητές:

• Το αρχικό n που δόθηκε από το χρήστη.
• Το παρόν βάθος της αναδρομής: αυτό είναι 0 μέσα στην ενεργοποίηση της f(n) που καλέστηκε από το κυρίως πρόγραμμα, είναι 1 μέσα στις ενεργοποιήσεις f(n-1) και f(n-2) που αυτή καλεί, κ.ο.κ.
• Το συνολικό πλήθος των λέξεων που "σώθηκαν" στη στοίβα. Το πλήθος των λέξεων που σώθηκαν στη στοίβα μετράει όλες τις λέξεις που οι ενεργοποιήσεις της διαδικασίας σας γράφουν στη στοίβα με σκοπό να τις επαναφέρουν αργότερα (περιλαμβανόμενης και της διεύθυνσης επιστροφής). Κάθε λέξη που αποθηκεύετε τη μετράτε μία φορά, όταν την αποθηκεύετε --δεν την ξαναμετράτε όταν την επαναφέρετε.

Γράψτε την αναδρομική διαδικασία σας σεβόμενοι τις παραπάνω συμβάσεις χρήσης των καταχωρητών, δηλαδή χωρίς να εκμεταλλεύεστε το γεγονός ότι ξέρετε το εσωτερικό της καλούμενης διαδικασίας. Οργανώστε τη στοίβα σας όπως φαίνεται στο σχήμα 3.10 του βιβλίου (σελ. 135) --αλλά προφανώς αποθηκεύοντας μόνο όσους καταχωρητές πρέπει να αποθηκεύσετε βάσει των παραπάνω συμβάσεων-- ή όπως στο σχήμα 3.12 (σελ. 139) αλλά χωρίς τον $fp. Προσπαθείστε να ελαττώστε το συνολικό πλήθος των λέξεων που σώζονται στη στοίβα γιά δεδομένη τιμή του n --πειραματιστείτε λίγο με διαφορετικές μορφές του κώδικα γιά να δείτε πώς αυτό επηρεάζεται. Μην κάνετε βελτιστοποιήσεις που εκμεταλλεύονται γνωστές τιμές της f(i) γιά μικρά i: κάθε ενεργοποίηση της f(i) γιά i>1 θα κάνει δύο καλέσματα, στις f(i-1) και f(i-2) παρά το γεγονός ότι ενδέχεται τα f(i-2) ή/και f(i-1) να είναι τα γνωστά f(0) ή f(1). (Επίσης, μην βάλετε την f(i) να επιστρέφει και την τιμή f(i-1) που τυχαίνει να έχει επίσης ζητήσει/υπολογίσει...).

Στην αρχή της αναδρομικής διαδικασίας σας, αφού κάνετε αριθμητικούς ελέγχους στο όρισμα σας αλλά πριν καλέσετε άλλη ενεργοποίηση της διαδικασίας, και μόνον εάν πρόκειται να καλέσετε άλλη τέτοια ενεργοποίηση, θα τυπώνετε ένα string της μορφής "    enter f(5)\n", όπου το πλήθος των κενών χαρακτήρων (spaces) στην αρχή της γραμμής ισούται με το παρόν βάθος της αναδρομής (απο τη σχετική γενική μεταβλητή), ο δε αριθμός μέσα στις παρενθέσεις είναι το παρόν όρισμα με το οποίο μας καλέσανε.

Παραδώστε, όπως και στις προηγούμενες ασκήσεις, τον κώδικά σας και ένα στιγμιότυπο της εκτέλεσής του στον SPIM, πακεταρισμένα στο αρχείο "ask9.tar", μέσω:

        tar -cvf ask9.tar   ask9.s ask9.jpg
        ~hy225/bin/submit 9