Função recursiva usando o conjunto MIPS

Estou a ter problemas numa missão e gostaria de Ajuda. Eu não estou pedindo a resposta, eu prefiro colocar dois mais dois juntos para descobrir por mim mesmo, mas eu sei tão pouco sobre MIPS é difícil para mim saber por onde começar.

Aqui está o que eu comecei com 

.data


.text
main:

addi $sp, $sp, -16  #prepare stack for 4 items
sw $s0, 0($sp)
sw $s1, 4($sp)
sw $s2, 8($sp)
sw $ra, 12($sp)
move $s0, $a0
move $s1, $a1

add $s2, $s0, $s1   #add two previous numbers and store result in $s2

move $v0, $s2   #put answer into $v0

lw $s0, 0($sp)
lw $s1, 4($sp)
lw $s2, 8($sp)
lw $ra, 12($sp)
addi $sp, $sp, 16
jr$ra
Basicamente, vamos usar uma função recursiva para calcular os números de fibonacci e um laço para imprimir os primeiros 10 números da sequência de fibonacci.

Já procurei muitos. exemplos, mas todos eles usam instruções que ainda não aprendemos, por isso não consigo perceber e só posso assumir que não se espera que as usemos. No código acima estou essencialmente criando uma pilha para armazenar o $ ra junto com três valores, os dois números a serem adicionados e a soma. Parte do meu problema é entender onde a função começa e termina e qual é a totalidade do trabalho que está sendo feito.

também nos foi dado que para imprimir você usa o seguinte 

li $v0, 1
move $a0, $s0
syscall

Sou Eu correcto ao pensar que isto é imprimir o valor armazenado em $v0?

obrigado antecipadamente

Author: TheDubiousDubber, 2015-10-28
Source

2 answers

Aqui está o código da sua função. Eu sei que você não está procurando a resposta, mas algum dia procurando por um exemplo e como ele funciona é o seu mais fácil no ponto em que você entende como ele realmente funcionou. 
.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);

    #save in stack
    addi $sp, $sp, -12 
    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
Como Gusbro disse para usar a recursão em mips você terá que fazer duas coisas. jal (salto e ligação) para o nome da função, mas primeiro armazene sempre o endereço de retorno numa pilha: $ra por isso, no futuro, se quiser voltar ao início, será capaz de utilizar jr $ra. Se você não gravar um endereço de retorno e tentar acessá-lo através de jr você provavelmente terá um invalid program counter error. Espero ter-te ajudado e boa sorte a perceberes melhor a programação MIPS!
 4
Author: Korpel, 2015-10-29 06:50:30
Aqui vão algumas dicas:

Você tem que escrever uma função recursiva, mas você não está escrevendo uma função em tudo. Para escrever esta função no Montador MIPS, sugiro que a escreva primeiro numa linguagem de nível superior (C). Então, seria algo assim: 

int fib(int n)
{
  if(n == 0 or n == 1)
    return n;
  else return fib(n-1) + fib(n-2);
}

A primeira linha verifica se você está num caso base da recursão (n=0 ou n=1). Se for esse o caso, o fib (n) devolve n. Caso contrário, o passo recursivo vai que devolve a soma do fib (n-1) mais fib (n-2).

Então você terá que escrever uma função, definir os parâmetros de entrada/saída (que registrador será mantido n e que irá retornar fib(n). A compilação manual do código C. Para iniciar uma função, basta adicionar uma legenda 

fib:
    Então coloque o seu código de gestão da pilha aí.
  • em seguida, traduza o se-então-ELSE para MIPS montar.
  • para emitir a chamada recursiva, use a instrução jal.
  • antes de retornar da função com jr $ra restaurar o salvo valores da pilha.
  • o seu programa principal irá carregar o parâmetro de entrada(o registo usado para o argumento de entrada n), depois jal fib.
 2
Author: gusbro, 2015-10-28 13:33:34