H e l π σε mips (fibonaci)

[nikos134]

Λοιπον σε c εχουμε αυτο

int fib (int n)
{
int f:
If (n<2)
f=n;
else
f=fib(n-1)+fib(n-2);
return f;
}
 

και σε mips:

data
msg1:.asciiz "Give a number: "
.text
.globl main
main:

li $v0,4
la $a0,msg1
syscall #print msg
li $v0,5
syscall #read an int
add $a0,$v0,$zero #move to $a0

jal fib #call fib

add $a0,$v0,$zero
li $v0,1
syscall

li $v0,10
syscall

fib:
#a0=y
#if (y==0) return 0;
#if (y==1) return 1;
#return( fib(y-1)+fib(y-2) );

addi $sp,$sp,-12 #save in stack
sw $ra,0($sp)
sw $s0,4($sp)
sw $s1,8($sp)

add $s0,$a0,$zero

addi $t1,$zero,1
beq $s0,$zero,return0
beq $s0,$t1,return1

addi $a0,$s0,-1

jal fib

add $s1,$zero,$v0 #s1=fib(y-1)

addi $a0,$s0,-2

jal fib #v0=fib(n-2)

add $v0,$v0,$s1 #v0=fib(n-2)+$s1
exitfib:

lw $ra,0($sp) #read registers from stack
lw $s0,4($sp)
lw $s1,8($sp)
addi $sp,$sp,12 #bring back stack pointer
jr $ra

return1:
li $v0,1
j exitfib
return0 : li $v0,0
j exitfib 

εγω δεν εχω καταλαβει καλα την στοιβα στο σημειο με  τους $sp..

Αν εχει κανεισ κανενα hint..

 

 

*Για ποιο λογο δεν μπορω να βαλω help ston titlo?

[gon1332]

Ελπίζω να σε καλύψει αυτή η διάλεξη.

 

Γενικά, όταν καλούμε μία διαδικασία (συνάρτηση), πρέπει να:

1. περάσουμε τα ορίσματα στους καταχωρητές $a0-$a3 (αν έχουμε ορίσματα)
2. να καλέσουμε τη συνάρτηση με jal (jump-and-link), η οποία ενημερώνει τον καταχωρητή $ra για την θέση στην οποία θα επιστρέψει η συνάρτηση ($ra = PC + 4)
3. όταν είμαστε πλέον στον κώδικα της συνάρτησης αν πρόκειται να χρησιμοποιήσουμε κάποιον καταχωρητή ο οποίος πιθανότατα να έχει κάποια συγκεκριμένη τιμή κάπου αλλού στο πρόγραμμα (το πιο πιθανό σε προηγούμενο stack frame), τότε την αποθηκεύουμε στη στοίβα και είμαστε ελεύθυεροι να τον χρησιμοποιήσουμε.
4. αφού τελειώσαμε ότι είναι να κάνουμε, επαναφέρουμε τα δεδομένα από τη στοίβα στους καταχωρητές που βρίσκονταν πριν καλέσουμε τη συνάρτηση και επιστρέφουμε με jr $ra (jump-register)

Εσύ βλέπεις ένα παράδειγμα fibonacci, το οποίο είναι αναδρομικά λυμένο.

Κάθε νέα κλήση της συνάρητησης πρέπει να αποθηκεύει στη στοίβα τον καταχωρητή που περιέχει τη διεύθυνση επιστροφής ($ra). Αν το χάσεις αυτόν, τότε χάθηκες στις αναδρομές. Για να αποθηκεύσεις κάτι στη στοίβα, πρέπει πρώτα να "δημιουργήσεις" χώρο σε αυτή για τα δεδομένα σου. Για τη στοίβα γνωρίζεις τη διεύθυνση του στοιχείου top ($sp - stack pointer). Επειδή η στοίβα του MIPS αυξάνει και πληθαίνει προς τις μικρότερες διευθύνσεις, τότε αφαιρούμε bytes από τον stack pointer. Έτσι αν θέλουμε να εποθηκεύσουμε 3 καταχωρητές (words), θα αφαιρέσουμε 3*4 bytes από το $sp. Θα αποθηκεύσουμε να δεδομένα μας και θα συνεχίσουμε τη δουλειά μας:

addi $sp,$sp,-12 #save in stack
sw $ra,0($sp)
sw $s0,4($sp)
sw $s1,8($sp)

Στο τέλος θα τραβήξουμε τα δεδομένα και θα επαναφέρουμε τη στοίβα στη θέση της προσθέτοντας 3*4 bytes:

lw $ra,0($sp) #read registers from stack
lw $s0,4($sp)
lw $s1,8($sp)
addi $sp,$sp,12 #bring back stack pointer
jr $ra

[ChRis6]

Ο $sp ( stack pointer) σου δείχνει τη διεύθυνση που ξεκινάει η στοίβα.

Όταν καλείς τη συνάρτηση, μειώνεις τη διεύθυνση στοίβας που δείχνει ο $sp για να αποθηκεύσεις τον $ra στη στοίβα ώστε να ξέρεις σε ποια διεύθυνση του προγράμματος ( σε ποια εντολή με άλλα λόγια) επιστρέφεις μόλις τελειώσει η current κλήση.Αποθηκεύεις επίσης τους $s0 και $s1 γιατί κατα σύμβαση θεωρείται οτι οι καταχωρητές $s* δεν αλλάζουν τιμή όταν καλείς μια συνάρτηση.Άρα πρέπει να κρατήσεις στη μνήμη τη παλιά τιμής τους για να τους χρησιμοποιήσεις.O $t1 δεν χρειάζεται να αποθηκευτει στη μνήμη,αφού θεωρείται "temp  register".

Όταν μπαίνεις στην συνάρτηση μειώνεις τον $sp κατα 12 γιατί αποθηκεύεις 3 λέξεις ( τον $ra,$s1 και $s2)  και προτού κάνεις jump register $ra κάνεις πάλι load τις τιμές που αποθήκευσες,φέρνεις τον $sp 12 bytes πίσω και έτσι "ελευθερώνεις" τη μνήμη που δέσμευσες ( δηλάδή απλά αλλάζεις τη διεύθυνση που μπορείς να γράψεις/διαβάσεις ).

Αν δεν μειώσεις τον $sp και γράψεις στη διεύθυνση που δείχνει,τότε θα πειράξεις δεδομένα που δεν σου ανήκουν

 

Edit:
Πολύ Παν.Θεσσαλίας Πέφτει στο forum τώρα τελευταία.Τι γίνεται ;

[gon1332]

Πολύ Παν.Θεσσαλίας Πέφτει στο forum τώρα τελευταία.Τι γίνεται ;

 

Άρχισαν να πέφτουν σιγά σιγά οι μάσκες.

[ChRis6]

Άρχισαν να πέφτουν σιγά σιγά οι μάσκες.

I see what you did there

[nikos134]

 

 

Edit:
Πολύ Παν.Θεσσαλίας Πέφτει στο forum τώρα τελευταία.Τι γίνεται ; 

 

ολα τα διαβαστερα παιδια ειναι εκει :D

 

 

 

 

thx for the help

[gon1332]

*Για ποιο λογο δεν μπορω να βαλω help ston titlo?

 

Μάλλον έπεσες θύμα parsing.