ÍNDICE DE CONTEÚDO
- 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, atendendo de forma especial a Terceira Idade e Concurseiros. 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, trabalhei com pesquisa, ensino, extensão e inovação, ministrei palestras em vários eventos. Mais recentemente venho ofertando serviços na área de tecnologia como desenvolvimento de sistemas, treinamentos, consultoria, mentoria, etc. Comecei meu Doutorado na área de Machine Learning (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!
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.