Compilação de Expressões no MIPS

Olá Pessoa! Hoje vamos aprender um pouco mais sobre o conjunto de instruções MIPS. No artigo anterior, vimos uma conversão simples. Hoje vamos usar uma instrução menos simples. Vamos lá?

Conversão de uma instrução com parênteses

Considere a seguinte instrução em linguagem C:

a = b - ( c  -  d ) + e

Como resolveríamos isso na mão, com uma folha de almaço? Sem saber os valores reais, e considerando a ordem de prioridade de execução das operações, a resolução dessa instrução ficaria assim:

a = b - ( c  -  d ) + e

a = b - T1 + e

a = T3 + e

a = T4

Onde T1, T2, T3 e T4 são os valores resultantes e o negrito/itálico representa a parte da expressão matemática que está sendo resolvida naquele instante. Se você substituir b, c, d, e e com valores de números inteiros ou reais, chegará em um resultado final. O que eu fiz acima foi uma generalização de uma resolução matemática, algo abstrato e que nos permite entender o passo a passo. Bom, se é assim que fazemos na unha, como é que faremos a conversão para MIPS? Não é muito diferente.

Linguagem de Montagem

Vamos fazer a conversão, começamos pela Linguagem de Montagem, lembrando sempre de consultar as tabelas da arquitetura do conjunto de instruções MIPS 32 bits. Como é uma instrução com parênteses, devemos primeiro resolver os parênteses, assim como em qualquer outra expressão matemática.

Depois dos parênteses, devemos voltar fazendo a leitura da expressão da ESQUERDA para a DIREITA, sem alterar a ordem em que os operandos aparecem na expressão. Então, primeiro o parênteses, depois b - ( c - d ) e somente depois somamos com e. Usaremos os seguintes registradores: a = $s0, b = $s1, c = $s2, d = $s3 e e = $s4. Também precisaremos usar registradores temporários $t para poder armazenar os valores de cada parte da expressão.

 Listagem 1: Código MIPS correspondente à expressão a = b - ( c - d ) + e

SUB $t1, $s2, $s3     # $t1 = ( $s2 - $s3 ) é o mesmo que $t1 = ( c - d )
SUB $t2, $s1, $t1    # $t2 = $s1 - $t1 é o mesmo que $t2 = b - ( c - d )
ADD $s0, $t2, $s4     # $s0 = $t2 + $s4 é o mesmo que $s0 = b - ( c - d ) + e

O caractere # nos permite comentar o código MIPS. $t1 é um registrador temporário que armazenará o resultado da subtração de ( c - d ). Assim resolvemos a primeira parte da expressão correspondente à prioridade parênteses. A próxima parte da expressão matemática a ser resolvida é b - ( c - d ).

O registrador $t1 é utilizado na linha dois e, observe, ele é o último registrador a aparecer na instrução, isto porque é ele quem guarda o valor resultante de ( c - d ). O primeiro registrador é outro temporário, $t2, que armazenará o resultado de b - ( c - d ). O segundo registrador, $s1 é correspondente à variável b. Assim, a segunda linha executa a segunda parte da expressão matemática.

A última parte da expressão é a resolução dela inteira. A última parte então que falta é b - ( c - d ) + e, agora então temos de somar e ao restante que já foi calculado. Assim na terceira linha, o primeiro registrador é o $s0, que é a variável a; o segundo registrador é $t2, que armazena o resultado de b - ( c - d ); e, por fim, o terceiro registrador da instrução é $s4, correspondente à variável e.

Você notou que a resolução da expressão é cumulativa? Uma parte da expressão é resolvida e armazenada em um registrador e depois utilizada na instrução seguinte, e assim por diante, até terminar toda a expressão. Assim sendo, podemos reescrever o código MIPS da listagem 1 para economizar um registrador temporário. Ao invés de usarmos dois registradores diferentes, podemos usar apenas um, somente $t1 e descartamos $t2. "Economizar" registradores temporários é importante, assim eles ficam livres para serem usados em outras instruções que realmente precisem. Sempre que a instrução de alto nível for acumulativa, você pode também acumular valores em um registrador, mas tome cuidado ao fazer isso, para não gerar erros no resultado final.

Listagem 2: Código MIPS correspondente à expressão a = b - ( c - d ) + e

SUB $t1, $s2, $s3     # $t1 = ( $s2 - $s3 ) é o mesmo que $t1 = ( c - d )
SUB $t1, $s1, $t1    # $t1 = $s1 - $t1 é o mesmo que $t1 = b - ( c - d )
ADD $s0, $t1, $s4     # $s0 = $t1 + $s4 é o mesmo que $s0 = b - ( c - d ) + e

Na Listagem 2 eu substitui $t2 por $t1 pois isso não influenciará o resultado final. Ao fazer ADD $t1,  $s1, $t1 o valor de $t1 será sobrescrito ao final da execução da instrução, isto é, o valor original será perdido e um novo valor será armazenado ali. Primeiro os operandos fontes, $s1 e $t1, são buscados da memória, depois eles são somados e, por último, o resultado é armazenado em $t1. Se por um acaso você precisar do valor de $t1, que é o valor de c - d, para ser usado em outra instrução posterior, então você não deve trocar $t2 por $t1, você na verdade deve manter $t2 para que o valor de $t1 não seja perdido.

Linguagem de Máquina

A linguagem de máquina corresponde a trocar os nomes dos registradores pelo seu número, então nosso código ficará assim:

Listagem 3: Código MIPS correspondente à expressão a = b - ( c - d ) + e

SUB $9, $18, $19     # $t1 = ( $s2 - $s3 ) é o mesmo que $t1 = ( c - d )
SUB $9, $17, $9    # $t1 = $s1 - $t1 é o mesmo que $t1 = b - ( c - d )
ADD $16, $9, $20     # $s0 = $t1 + $s4 é o mesmo que $s0 = b - ( c - d ) + e

Representação

A representação corresponde a pegar as nossas instruções MIPS e colocá-las no formato correspondente, conforme mostra a Tabela 1:

Tabela 1: Representação das instruções

Para preencher a tabela eu consultei o artigo anterior que contém a tabela de operações e formatos de instruções do TIPO R explicadinhos. RS e RT são os operandos FONTES e RD é o operando DESTINO. Como ADD e SUB são operações matemáticas, o código de operação delas é ZERO, mas o código de FUNCT é 32 e 34 respectivamente.

Código de Máquina

O código de máquina corresponde a pegar a representação da instrução e converte-la para número binário. OP e FUNCT são seis bits e os outros campos são cinco bits. A Tabela 2 apresenta a Tabela 1 em forma de código binário:

Tabela 2: Código binário para cada campo do formato de instrução

Assim, o código de máquina final é o seguinte:

00000010010100110100100000100010

00000010001010010100100000100010

00000001001101001000000000100000

Exercícios

Vamos exercitar um pouco? Se tiverem dúvidas, deixem nos comentários ok?! Muito Obrigada.

Considere os seguintes registradores para cada variável: a = $s0, b = $s1, c = $s2, d = $s3, e = $s4, f = $s5.

1. a = b - c
2. b = a + c
3. d = (a + b - c)
4. f = (a + b) - d
5. c = a - ( b + d)
6. e = ( a - ( b - c )
7. e = ( a - ( b - c ) + f )
8. f = e -  (a - b ) + ( b - c )