Compilando Procedimentos Recursivos e Aninhados no MIPS

instrução MIPS LW e SW IF Simples no MIPS

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:

 

 

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:

 

 

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:

 

 

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:

 

 

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:

 

 

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:

 

 

Como estamos chamando o Fatorial novamente, precisamos agora restaurar o endereço de retorno e o argumento n:

 

 

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:

 

 

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:

 

 

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

Outros artigos da série

<< Compilando Funções e Procedimentos no MIPSDetalhamento da Compilação de Procedimentos no MIPS >>

NEWSLETTER

Receba os melhores conteúdos sobre sistemas eletrônicos embarcados, dicas, tutoriais e promoções.

Obrigado! Sua inscrição foi um sucesso.

Ops, algo deu errado. Por favor tente novamente.

Elaine Cecília Gatto
Bacharel em Engenharia de Computação. Mestre em Ciência da Computação. Co-fundarora e Líder das #GarotasCPBr. Pesquisadora Convidada no Grupo de Pesquisa de "Artes em Tecnologias Emergentes" do Programa de Pós Graduação em Design na UNESP Campus Bauru. Cantora, Docente no Magistério Superior, Geek, Nerd, Otaku e Gamer. Apaixonada por Michael Jackson, Macross, Séries e Filmes de Super Heróis, Cervejas e Vinhos. Mais informações sobre mim você encontra em: http://lattes.cnpq.br/8559022477811603.

Deixe um comentário

avatar
 
  Notificações  
Notificar