Hi everybody! :wink
First: we are talking about MIPS R2000.
I have to solve this exercise and unfortunately it's the most difficult one, so far... I read the documents about the stack and procedures, but I am not able to use the information in an acceptable way.
As you have much more experience than me, it would be appreciated if you could give me some tips, how to solve that exercise with the new techniques "stack" and "procedures".
Regards,
Herakles
EDIT:
I hope the task doesn't sound strange to you, since I've translated it from German and English is not my native language... In case a word/sentence sounds strange to you, please don't hesitate to ask me. Thanks.
QuoteSn := Sumni-1 i
You are only allowed to make changes at the marked places.
Hint:
Make yourself familiar with the stack programming and the calling of subroutines, before you start this exercise.
a. Sn can be calculated through the following programme fragment:
int sum(int n){
if(n==0){
return 0;
}else{
return sum(n-1)+n;
}
}
Implement this fragment at the marked place of the file.
b. The following programme fragment calculates Sn through terminal recursion:
int sum2(int n, int akk){
if(n==0){
return akk;
}else{
return sum2(n-1,akk+n);
}
}
Implement this fragment at the marked place of the file, too.
c. Compare your parts of the programme. Which part would you choose in case of limited resources. Why?
d. Put a better solution for the calculation of Sn forward.
.data
in: .asciiz "Please insert n: "
out1: .asciiz "Result 1: "
out2: .asciiz "Result 2: "
nl: .asciiz "\n"
.text
main: # Insertion of n
la $a0, in # print "Please insert n:"
li $v0, 4
syscall
li $v0, 5 # read insertion
syscall
move $s0, $v0 # save insertion
# first alternative
la $a0, out1 # print "Result 1:"
li $v0, 4
syscall
move $a0, $s0 # initialisation of n
jal sum1 # procedure call
move $a0, $v0 # print result
li $v0, 1
syscall
la $a0, nl # print line break
li $v0, 4
syscall
# second alternative
la $a0, out2 # print "Result 2:"
li $v0, 4
syscall
move $a0, $s0 # initialisation of n
jal sum2 # procedure call
move $a0, $v0 # print result
li $v0, 1
syscall
la $a0, nl # print line break
li $v0, 4
syscall
li $v0, 10 # terminate
syscall
sum1:
#########################################
# Implement here subtask (a)
#########################################
jr $ra
sum2:
#########################################
# Implement here subtask (b)
#########################################
jr $ra
No, makes sense.
The parameters are passed as registers, if you want to preserve the registers as you call another subroutine you will have to push them on the stack, and pop them back after it returns. Also you are going to have to stack $ra (return address, linking) before you call another subroutine.
If you need a MIPS C compiler look at SDE which includes GCC.
http://www.mips.com/products/software-tools/mips-sde-lite/
The magic to get assembler out is
sde-gcc -S -O2 test.c
sde-gcc -S -O2 -mips2 test.c
An example of minimal prologue/epilogue code for a subroutine that calls out to another subroutine
xxx:
addiu $sp,$sp,-4 # Prologue, push stack
sw $ra,0($sp) # save return address
jal xxx # changes $ra
lw $ra,0($sp) # Epilogue, restore entry return address
addiu $sp,$sp,4 # pop stack
jr $ra # return to caller
Also the framework appears not to be initializing the second parameter, should $a1 (akk) be set to something specific?
move $a0, $s0 # initialisation of n
jal sum2 # procedure call
Two implementations of sum1
sum1: move $v0, $zero
beq $a0, $zero, sum1x
addiu $sp, $sp, -8
sw $s0, 0($sp)
sw $ra, 4($sp)
move $s0, $a0
addiu $a0, $a0, -1
jal sum1
add $v0, $v0, $s0
lw $ra, 4($sp)
lw $s0, 0($sp)
addiu $sp, $sp, 8
sum1x: jr $ra
sum1: move $v0, $zero
beq $a0, $zero, sum1x
addiu $sp, $sp, -4
sw $ra, 0($sp)
addiu $a0, $a0, -1
jal sum1
addiu $a0, $a0, 1
lw $ra, 0($sp)
addiu $sp, $sp, 4
add $v0, $v0, $a0
sum1x: jr $ra
This book has a particularly good coverage of the MIPS calling conventions, and instruction set.
http://www.amazon.com/gp/product/1558602976/
The MIPS Programmer's Handbook (The Morgan Kaufmann Series in Computer Architecture and Design) (Paperback)
by Erin Farquhar, Philip J. Bunce
ISBN 1558602976
Sorry, clive for the very late feedback. :(
I have been very busy with my other four courses, so I didn't have the time for "computer architecture."
Thank you very much for your help and for the link.
MIPS makes up only 25% of the test in July, so I think it's the best when I become an expert in the exercises they give us for homework every week and this should be enough for a good mark in the test. Although the book seems to be excellent, I have to admit that I wouldn't have the time to read it, since I have too much stress because of the five courses. Maybe I'll buy and read it in summer, provided I'll pass all five of tests.
Concerning the MIPS C compiler:
Does it manage to convert code written in C to MIPS code?
They gave us a sample solution for the implementation thing and it would be nice to hear your opinion about it.
They always say to us "Make comments! Make comments! Make comments!", but they are using comments only sporadic, so they shouldn't point a finger at us...
Regards,
Herakles
.data
in: .asciiz "Please insert n: "
out1: .asciiz "Result 1: "
out2: .asciiz "Result 2: "
nl: .asciiz "\n"
.text
main: # Insertion of n
la $a0, in # print "Please insert n:"
li $v0, 4
syscall
li $v0, 5 # read insertion
syscall
move $s0, $v0 # save insertion
# first alternative
la $a0, out1 # print "Result 1:"
li $v0, 4
syscall
move $a0, $s0 # initialisation of n
jal sum1 # procedure call
move $a0, $v0 # print result
li $v0, 1
syscall
la $a0, nl # print line break
li $v0, 4
syscall
# second alternative
la $a0, out2 # print "Result 2:"
li $v0, 4
syscall
move $a0, $s0 # initialisation of n
jal sum2 # procedure call
move $a0, $v0 # print result
li $v0, 1
syscall
la $a0, nl # print line break
li $v0, 4
syscall
li $v0, 10 # terminate
syscall
#########################################
# Implement here subtask (a)
#########################################
sum1: move $v0, $zero
sum1r: beqz $a0, sum1basis # if $a0=0 then base case
addi $sp, -8 # Callee-Prolog
sw $ra, 8($sp)
sw $a0, 4($sp)
sub $a0, $a0, 1 # self-call
jal sum1r
lw $ra, 8($sp) # Callee-Epilog
lw $a0, 4($sp)
addi $sp, 8
add $v0, $v0, $a0
jr $ra
sum1basis:
move $v0, $zero
jr $ra
#########################################
# Implement here subtask (b)
#########################################
sum2: move $a1, $zero
sum2r: beqz $a0, sum2basis
addi $sp, -4
sw $ra, 4($sp)
add $a1, $a1, $a0
addi $a0, $a0, -1
jal sum2r
lw $ra, 4($sp)
addi $sp, $sp, 4
jr $ra
sum2basis:
move $v0, $a1
jr $raQuote
This code does not appear to be compliant with standard MIPS practice
addi $sp, -8 # Callee-Prolog
sw $ra, 8($sp)
sw $a0, 4($sp)
If you subtract by 8, the available slots are 0($sp) and 4($sp).
The previously mentioned book uses the style in my example, the compiler uses it. Pretty much any standard text I can find.
Check out the Fibonacci example on page 22
If you subtract by 12, the available slots are 0($sp), 4($sp) and 8($sp).
http://www.cl.cam.ac.uk/teaching/0809/OpSysI/os1a-handout2.pdf
Kind of scary how close my answer was to the example.
The C Compiler converts C to MIPS, not sure I understand your question. The output doesn't look as nice as handcrafted code, but I can give some insight into methods/instructions that work.
You are right. Even I know that it must be 0($sp) and 4($sp). I checked again the sample solution, not to have made any mistakes while tipping it here on the thread, but it's wrong there, too.
I don't know how the situation in other countries looks like, but in Germany the people who work at university in the special subject of computer science, are completely incompetent. They stayed at university and became a doctor or professor, just because they saw, that the employment market doesn't need them, because they are too silly. If they were real experts, they would earn a lot of money outside there.
The coincidence is really scary. :toothy
I was just astonished that there exists a programme which is able to convert C to MIPS... It must have been lots of work to create such a programme.
Well MIPS (1981) is a very old RISC design, and was designed to be a good target for compilers. ie Large register set, orthogonal instruction set. A lot of work was done on compilers, and code analysis, as part of proving the "RISC" methodology.
David Ditzel worked on compilers at Berkeley 1977-1979 and went on to do design work on the Sparc processor, and later started Transmeta. Been I few years since I met him, but a pretty cool guy. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.68.9623&rep=rep1&type=pdf
IBM 801 (1975)
Berkeley RISC (1980)
MIPS (1981)
ARM (1983)
MIPS-X (1984)
SPARC (1986)
This David Ditzel?
http://www.intel.com/pressroom/kits/bios/ditzel.htm
Yes, that one. I met him when he was running Transmeta.
Unlike the German computer professors at university, he made it outside! :clap: