- Arquitetura de Conjunto de Instruções MIPS
- Primeira Instrução MIPS
- Compilação de Expressões no MIPS
- Convertendo uma instrução com Array no MIPS
- Armazenando um valor em Array no MIPS
- Instruções LW e SW com Array no MIPS
- Instrução IF Simples no MIPS
- Instrução IF Composto no MIPS
- Instrução SLT no MIPS
- Operações Lógicas no MIPS
- Operação Lógica AND no MIPS
- Operação Lógica OR no MIPS
- Operação Lógica NOT no MIPS
- Endereços de Memória no MIPS
- Operandos Imediatos e Constantes no MIPS
- Compilando Arrays com índice variável no MIPS
- Testando as instruções MIPS no MARS
- Executando um Array no MARS para MIPS
- Sinal e Overflow no MIPS
- Compilando instruções com ou sem Sinal, Overflow e Imediato no MIPS
- Compilando While no MIPS
- Compilando Switch/Case no MIPS
- Compilando Funções e Procedimentos no MIPS
- Compilando Procedimentos Recursivos e Aninhados no MIPS
- Detalhamento da Compilação de Procedimentos no MIPS
- MIPS: Instruções de Multiplicação
- MIPS: Instruções de Divisão
- MIPS: Subtração e outras instruções
- Compilando o comando FOR no MIPS
- Ponto Flutuante no MIPS
- Convertendo Código de Máquina em Assembly MIPS – Parte 1
- MIPS: Resolução dos exercícios – Parte 1
- MIPS: Resolução de Exercícios Parte 2
Oi pessoal! No artigo anterior eu mostrei para vocês como funcionam os procedimentos/funções no Assembly MIPS, aprendemos instruções novas e utilizamos outras já conhecidas. Hoje retomamos este assunto, mas vamos tratar de uma particularidade importante em programação, os procedimentos aninhados recursivos. Uma dica, antes de continuar aqui, leia o meu artigo sobre Recursividade na série Algoritmos e depois volte para cá, tudo bem? Então vamos lá.
Procedimentos Folha e não Folha
Algo importante sobre procedimentos é que eles não são algo isolado, eles sempre estão conectados com outras partes do programa e devemos tomar o máximo de cuidado possível com os valores que manipulamos ao usar procedimentos, para que estes não se percam ou sejam substituídos erroneamente. Assim, um procedimento folha é um procedimento que não chama outros, e um procedimento não folha é aquele que chama outros procedimentos, sendo este o mais comum. Para ilustrar, veja o código abaixo:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
float n1, n2; void leitura() { printf(" \n Digite o valor do primeiro numero: "); scanf("%f%*c", &n1); printf(" \n Digite o valor do segundo numero: "); scanf("%f%*c", &n2); } float soma(float n1, float n2) { leitura() return (n1 + n2); } int main() { soma(n1,n2) printf(" \n O resultado da soma é: %.2f", soma(n1, n2)); return 0; } |
MAIN, o programa principal, é um procedimento que chama outro procedimento, a soma e, convenhamos, na maioria dos nossos programas em C é isso o que fazemos: enxugamos o programa principal e colocamos tudo em funções para deixar o programa o mais organizado possível. Note também que o procedimento soma chama outro procedimento, leitura, criando assim uma cascata e dependência. Bom, isso já foi muito bem explicado nos artigos da série Algoritmos, mas estou reforçando aqui pois o impacto disto no Assembly é mais delicado.
Suponha que o procedimento soma coloque seus argumentos n1 e n2 nos registradores $a0 e $a1 e então use a instrução jal. Suponha agora que o procedimento soma chama um outro procedimento chamado TESTE também usando jal com outros dois argumentos que serão armazenados em $a0 e $a1. Como soma ainda está executando e não terminou, temos um conflito pois precisamos do registrador $a0 mas ele já tem um valor que ainda será usado. Para ajudar, temos outro conflito do mesmo tipo em relação ao endereço de retorno do registrador $ra. O procedimento TESTE executa dentro do procedimento SOMA e isso torna complicado o uso dos registradores, pois eles já estarão ocupados e estão sendo requisitados por outras partes do programa.
O que precisamos fazer então? Temos de preservar os valores do procedimento SOMA para que o procedimento TESTE execute corretamente e retorne ao endereço correto. Para que os conflitos sejam revolvidos pode-se empilhar os registradores da seguinte forma:
- Caller: empilha registradores de argumentos e registradores temporários que sejam necessários após a chamada ($a0 – $a3 e $t0 – $t9)
- Callee: empilha o registrador de endereço de retorno e registradores salvos usados por ele ($ra, $s0 – $s7)
- Stack Pointer: $sp é ajustado considerando a quantidade de registradores colocados na pilha. Os registradores são restaurados da memória e o $sp é ajustado quando ocorre o retorno.
Compilando Procedimento Recursivo
Para ficar mais fácil o entendimento, vamos fazer a compilação de um código recursivo em C:
|
1 2 3 4 5 6 |
int fatorial ( int n) { if ( n < 1 ) return 1; else return ( n * fatorial ( n – 1 ) ); } |
Este é o famoso Fatorial, uma função recursiva, isto é, que chama a si mesma, várias vezes. Como esse código fica em Assembly? Vamos começar pelo nome do rótulo, ou label, que neste caso será “fatorial:”. A função tem um parâmetro do tipo inteiro, n, portanto um argumento que deve ser armazenado em $a0. Agora como já aprendemos no artigo anterior, precisamos salvar os registradores, os argumentos e o endereço de retorno na pilha:
|
1 2 3 4 |
fatorial: addi $sp, $sp, -8 # colocaremos 2 itens na pilha sw $ra, 4 ($sp) # salvamos o endereço de retorno sw $a0, 0 ($sp) # salvamos o argumento n |
Primeiro passo concluído com sucesso, lembrem-se, a primeira coisa a se fazer sempre ao se trabalhar com procedimentos é salvar os dados! Agora, temos de tratar a recursão. Fatorial é chamado pela primeira vez, neste momento sw salva um endereço do programa que chamou Fatorial. Depois é feito o teste e o desvio:
|
1 2 |
slti $t0, $a0, 1 # n é menor que 1? beq $t0, $zero, L1 # vai para L1 se (n >= 1) |
Fatorial retornará 1 se (n < 1), portanto 1 será colocado no registrador e depois dois valores salvos da pilha serão retirados, finalizando com o desvio para o endereço de retorno:
|
1 2 3 |
addi $v0, $zero, 1 # retorna 1 se ( n < 1 ) addi $sp, $sp, 8 # retira dois itens da pilha jr $ra # retorna |
Bom, tratamos o primeiro caso do Fatorial que é quando o fatorial é menor que 1 e retorna 1. Mas e se não for este o caso? Vamos tratar então agora da outra parte da função. O argumento n é decrementado se (n >= 1) e Fatorial é chamado novamente com o valor decrementado:
|
1 2 3 |
L1: addi $a0, $a0, -1 # (n – 1 ) se (n >= 1) jal fatorial # chama fatorial novamente com o argumento decrementado |
Como estamos chamando o Fatorial novamente, precisamos agora restaurar o endereço de retorno e o argumento n:
|
1 2 3 |
lw $a0, 0 ($sp) # restaura o argumento n lw $ra, 4 ($sp) # restaura o endereço de retorno addi $sp, $sp, 8 # ajusta o stack pointer – retira dois itens da pilha |
Para finalizar a compilação, precisamos atualizar o registrador $v0, que receberá o produto do argumento antigo de $a0 e também o valor atual do registrador de valor, e por último pular para o endereço de retorno:
|
1 2 |
mul $v0, $a0, $v0 # retorna n * fatorial ( n – 1 ) jr $ra # retorna para o procedimento que o chamou |
Assim finalizamos a compilação de um procedimento recursivo para o Assembly MIPS, é um pouco confuso, mas também não é tão complicado quanto a maioria deve pensar que seja. Abaixo segue o código completo para ser executado no MARS:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
.text li $a0, 5 fatorial: addi $sp, $sp, -8 sw $ra, 4 ($sp) sw $a0, 0 ($sp) slti $t0, $a0, 1 beq $t0, $zero, L1 addi $v0, $zero, 1 addi $sp, $sp, 8 jr $ra L1: addi $a0, $a0, -1 jal fatorial lw $a0, 0 ($sp) lw $ra, 4 ($sp) addi $sp, $sp, 8 mul $v0, $a0, $v0 jr $ra |
O vídeo abaixo mostra a execução passo a passo do código no MARS para n = 5. Notem que o PC sempre tem seu valor alterado conforme a execução ocorre, assim como outros valores de áreas de memória e registradores!
Conclusão
Pessoal, se vocês tiverem dúvidas, por favor, deixem aqui nos comentários tá ok! Sugiro que peguem exemplos de códigos simples em C tentem fazer a compilação para o Assembly, de forma a treinar o que aprendemos hoje. No próximo artigo vou apresentar alguns detalhes sobre procedimentos que não foram abordados neste artigo e no anterior! Até lá.
Saiba mais
Funções e Procedimentos – Parte 1
Compilando Switch/Case no MIPS
Técnicas de Mapeamento de Memória em Linguagem C
Atuo como Professora de Informática e Computação desde 2001. Desde 2009 venho atuando como Docente no Ensino Superior em diversos cursos de Graduação e Pós Graduação Lato Sensu, tanto presenciais, quanto semipresenciais e à distância. Ministrei várias disciplinas onde ensino os estudantes a desenvolverem plataformas e sistemas computacionais. Orientei vários trabalhos acadêmicos, desenvolvi inúmeros materiais didáticos, trabalhei com pesquisa, ensino, extensão e inovação. Também ministrei palestras em vários eventos. Comecei meu Doutorado na área de Machine Learning - mais especificamente na area de Multi-label Classification - na UFSCar em 02/2019 e devo terminar em 01/2023. Também estudo canto, jogo vôlei, sou geek, nerd, otaku e gamer (twitch.tv/cissagatto)
Esse jr $ra na última linha 22, não está errado ? A instrução jal da linha 16 seta o $ra de forma automática para o endereço da linha 18 e quando $t0 (int n) for igual a zero, e a instrução jr $ra da linha 12 encaminhar para o endereço referente a linha 18, ele não se repetirá infinitamente ? Pensei da seguinte maneira, no ultimo ciclo, como o endereço de $ra está setado para a linha 18, e a ultima linha do código, linha 22, está forçando o loop eterno. Sou novo em instruções MIPS, mas caso meu entendimento… Leia mais »
Creio que o programa final mostrado não esteja funcionando, pelo menos aqui obtive erro ao testar, então fiz da seguinte forma .text li $a0, 1 callFatorial: jal fatorial j exit fatorial: addi $sp, $sp, -8 # -8 / 4 = 2, ou seja, iremos armazenar dois valores sw $ra, 4 ($sp) # Armazenando primeiro elemento sw $a0, 0 ($sp) # Armazenando segundo elemento slti $t0, $a0, 2 # $a0 < 2 ? 1 : 0 beq $t0, $zero, L1 # Se $t0 = 0 va para L1 li $v0, 1 # Carregando 1 por ser o elemento neutro da multiplicacao… Leia mais »
Olá, Elaine!
Quando eu executo ao fim apresenta o seguinte erro:
Error in : invalid program counter value: 0x00000000
Isso poderia causar algum problema caso tivesse mais instruções após o fim da recursão? Como eu poderia resolver esse problema?
Desde já agradeço a atenção.
Oi Matheus, td bom? Desculpe só responder seu comentário hoje. Esse erro acontece no simulador? Eu acho que o simulador JAVA é um pouco limitante mesmo e não está tendo updates dele. Vou dar uma conferida ta bom. Obrigada.
O problema está em que o $ra no primeiro loop não contém um endereço válido, ele está sempre zerado por padrão, ai não consegue voltar para um endereço válido