Compilando Procedimentos Recursivos e Aninhados 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:

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.

Os Melhores Treinamentos sobre Sistemas embarcados e IoT

Cursos com professores qualificados para acelerar sua carreira e projetos

MATRÍCULE-SE AGORA

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:

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:

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:

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:

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:

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:

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:

mul $v0, $a0, $v0 # retorna n * fatorial ( n – 1 )
jr $ra # retorna para o procedimento que o chamou

Este é o exemplo de fatorial que consta no livro do Patterson & Hannessey e está resumido a seguir:

.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

No entanto, eu fiz outro código com base em outros materiais que pesquisei e ele segue aqui embaixo completinho:

.data
	mensagem1:	.asciiz "\nDigite um número inteiro: "
	mensagem2:	.asciiz "\nO fatorial é: "
	numero:		.word 0
	resultado:	.word 0

.text
	.globl main
	
	main:
		# Solicita dados para o usuário no console
		li $v0, 4
		la $a0, mensagem1
		syscall
		
		li $v0, 5
		syscall				
		sw $v0, numero	       # salva em numero o valor digitado pelo usuario
		
		# Apresenta os resultados no console
		lw $a0, numero		# carrega o numero digitado pelo usuario
		jal findFactorial	# chama a função
		sw $v0, resultado	# armazena o resultado do calculo em resultado
		
		li $v0, 4
		la $a0, mensagem2
		syscall
		
		li $v0, 1
		lw $a0, resultado
		syscall
		
		# FINALIZA O PROGRAMA CORRETAMENTE
		li $v0, 10
		syscall

.globl calculaFatorial

calculaFatorial:
	# configurações da pilha
	subu	$sp, $sp, 8	
	sw 	$ra, ($sp)		# retorno da função
	sw	$s0, 4($sp)		# salva resultado
	
	# caso base
	li $v0, 1			# v0 = 1
	beq $a0, 0, fatorialStop	# desvia para factorialDone se a0=0
	
	# calculaFatorial(resultado-1)
	move	$s0, $a0		# move o valor de v0 para a0
	sub	$a0, $a0, 1		# a0 = a0 -1
	jal	calculaFatorial		# chama a função recursivamente
	
	mul $v0, $s0, $v0		# v0 = s0 - v0 --> calcula o valor do fatorial de fato
	
	# para o fatorial
	fatorialStop:
		lw $ra, ($sp)		# retorno da pilha
		lw $s0, 4($sp)		# retorno da função
		addu $sp, $sp, 8	# incrementa pilha
		jr $ra			# retorna

Notem que para testar no MARS nem sempre é obrigatório colocar todas as configurações de pilha, o programa vai rodar normalmente, mesmo porque o MARS é um simulador que não tem toda a arquitetura implementada. No entanto, se você for trabalhar com esse tipo de microprocessador, o ideal é que você siga todas as recomendações da linguagem MIPS!!! Segue uma imagem do resultado final:

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