Terminal recursion

[Herakles]

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.

S_n := Sumⁿ_i-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. S_n can be calculated through the following programme fragment:

Code Select Expand

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 S_n through terminal recursion:

Code Select Expand

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 S_n forward.

Code Select Expand

.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

[clive]

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

Code Select Expand

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?

Code Select Expand

move $a0, $s0   # initialisation of n
jal sum2 # procedure call


Two implementations of sum1

Code Select Expand

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

Code Select Expand

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

[clive]

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

[Herakles]

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

Code Select Expand

.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 $ra

[clive]

This code does not appear to be compliant with standard MIPS practice

Code Select Expand

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.

[Herakles]

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.

[clive]

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)

[Herakles]

This David Ditzel?

http://www.intel.com/pressroom/kits/bios/ditzel.htm

[clive]

Yes, that one. I met him when he was running Transmeta.

[Herakles]

Unlike the German computer professors at university, he made it outside! :clap: