Compilando Switch/Case no MIPS

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

No último artigo eu apresentei para vocês a compilação do comando de controle while, hoje vou mostrar como se traduz o switch case no MIPS. Este será um pouco mais extenso e complexo, assim tentarei ser bem didática para que vocês consigam entender, ok? Bora lá então!

SWITCH/CASE

Este comando permite que seja feita uma escolha dentre várias, assim poderíamos ter, por exemplo, quatro opções e escolher apenas uma, como um menu. Esse tipo de seleção pode ser implementada com o switch/case ou, então, podemos usar if/then/else para fazer a mesma coisa! Veja o exemplo de código-fonte em linguagem C abaixo:

K é a variável que contém o número escolhido da seleção, por exemplo, vamos supor que algo aconteceu antes de se chegar nesse trecho de código e o número 2 foi selecionado, assim, K = 2. case 0 é diferente de 2, então pula, case 1 é diferente de 2 então pula, mas case 2 é igual a 2, então executa o bloco de código que está ali dentro e, quando termina, sai do bloco e continua a execução das instruções seguintes. Cada case aqui no MIPS será tratado como um LABEL, que chamaremos de L0, L1, e assim por diante, sendo que cada um deles será correspondente a um endereço de memória, formando algo como uma Tabela de Endereços de Desvios. Não nos esqueçamos que switch/case é um comando de controle que desvia a execução do programa para o ponto desejado, conforme já expliquei em um artigo da série Introdução a Algoritmos. Podemos imaginar essa Tabela de Endereços de Desvios da seguinte forma:

ENDEREÇO

LABEL

INSTRUÇÃO

0x0040003c

L0

f = i + j;

0x00400044

L1

f = g + h;

0x0040004c

L2

f = g – h;

0x00400054

L3

f = i – j;

Assim, precisamos criar no MIPS essa Tabela, que nada mais é que um Array:

.data

jTable: .word L0,L1,L2,L3      #jump table definition

Dei o nome de jTable para a minha Tabela de Endereços e defini quatro Laels L0, L1, L2 e L3, agora é possível usá-los como cases. Agora precisamos atribuir o endereço base dessa tabela para algum registrador, da seguinte forma:

la  $t4, jTable                         # $t4 = base address of the jump table

Carreguei em um registrador temporário ($t4) o endereço da Tabela para que ela possa ser referenciada no código Assembly, algo muito parecido com ponteiros em linguagem C. Bem, depois de já termos a Tabela definida, podemos continuar com o restante da tradução. Antes de testar se case 1 = 2, por exemplo, precisamos verificar se K é válido, isto é, ele precisa ser igual a um dos valores presentes nos Labels, portanto, K deve estar entre 0 e 3 (4 valores diferentes). Se K não estiver dentro dessa faixa de valores, o switch não pode ser executado. Para fazermos isso temos de utilizar instruções de comparação, e conforme já estudamos, a SLT pode ser então escolhida para fazer essa tradução:

slt $t3, $s5, $zero                   # $t3 = ($s5 <= 0)

O registrador $t3 é temporário e armazenará o resultado da comparação entre o registrador $s5, que é K, e o registrador $zero, testando assim se K < 0. A instrução BNE pode nos ajudar a direcionar os desvios, lembrando que essa instrução significa “Branch Not Equal”, ou seja, “desvie se não for igual”, assim, se $t3 for diferente de zero, então desvia para EXIT, caso contrário executa as próximas instruções:

bne $t3, $zero, EXIT              # desvia para EXIT se $t3 < > 0

Ótimo, testamos se K < 0, agora precisamos testar o outro limite, isto é, K precisa estar entre 0 e 3, portanto testa se K < 4:

slti $st3, $s5, 4           # $t3 = ($s5 <= 4)

Usamos agora a instrução SLTI pois precisamos comparar o valor de $s5 (K) com um imediato (4). Lembrando que o resultado da comparação entre o registrador $s5 (K) é armazenado em $t3, o qual será usado na instrução BEQ (Branch if Equal – “desvie se igual”) para desviar ou não para EXIT. Se $t3 for igual a zero, então desviará para EXIT, caso contrário executará o bloco de comandos.

beq $t3, $zero, EXIT              # desvia para EXIT se $t3 = 0

Dessa forma vai desviar para EXIT se K >= 4. Para elucidar e ficar melhor de entender esta sequência, vamos supor que K = 6.

slt $t3, $s5, $zero

$s5 <= $zero

6 <= 0

F

Portanto, $t3 = 0

bne $t3, $zero, EXIT

$t3 < > $zero

0 < > 0

F

Portanto, não desvia!

slti $st3, $s5, 4

$s5 <= 4

6 <= 4

F

Portanto, $t3 = 0

beq $t3, $zero, EXIT 

$t3 = $zero

0 = zero

V

Portanto, desvia para EXIT

Vamos ver outro exemplo sendo K = 2. 

slt $t3, $s5, $zero

$s5 <= $zero

2 <= 0

F

Portanto, $t3 = 0

bne $t3, $zero, EXIT

$t3 < > $zero

0 < > 0

F

Portanto, não desvia!

slti $st3, $s5, 4

$s5 < 4

2 < 4

V

Portanto, $t3 = 1

beq $t3, $zero, EXIT 

$t3 = $zero

1 = zero

F

Portanto, não desvia

Vamos ver outro exemplo sendo K = 0.

slt $t3, $s5, $zero

$s5 <= $zero

0 <= 0

F

Portanto, $t3 = 0

bne $t3, $zero, EXIT

$t3 < > $zero

0 < > 0

F

Portanto, não desvia!

slti $st3, $s5, 4

$s5 < 4

0 < 4

V

Portanto, $t3 = 1

beq $t3, $zero, EXIT 

$t3 = $zero

1 = zero

F

Portanto, não desvia

Vamos finalizar com K = -1

slt $t3, $s5, $zero

$s5 <= $zero

-1 <= 0

V

Portanto, $t3 = 1

bne $t3, $zero, EXIT

$t3 < > $zero

1 < > 0

V

Portanto, desvia para EXIT!

Legal né! Agora que a verificação de K está traduzida, precisamos fazer o cálculo do endereço dos labels, assim o primeiro passo é somar 4 ao endereço, conforme também já estudamos.

sll $t1, $s5, 2                          # calcula o endereçamento de 4 bytes

A instrução SLL fará a soma de mais 4 bytes ao endereço de $s5 (k), agora precisamos somar isso com o endereço da Tabela de Desvios ($t4):

add $t1, $t1, $t4                     # $t1 será o endereço de jTable

De posse do endereço completo, podemos agora carregar o valor da Tabela. Não nos esqueçamos que a jTable começa no endereço que está em $t4, assim o endereço do desvio é carregado em um registrador temporário que neste exemplo será $t0:

lw  $t0, 0($t1)                        # $t0 é onde está o label desejado

A execução de uma instrução de desvio para o conteúdo de um registrador faz com que o programa passe a executar a instrução apontada na tabela de endereços de desvio, assim precisamos usar a instrução JR para que o desvio ocorra:

jr $t0                                       # desvia com base no conteúdo de $t0

Essa instrução vai forçar o desvio para o Label escolhido, por exemplo, se o endereço é de L2, ele vai desviar para lá exatamente! Então, notem que a dinâmica aqui é um pouco diferente de como acontece na programação de médio e alto nível, temos de pensar um pouquinho diferente do que estamos acostumados, tudo bem? A compilação feita até agora é a parte mais difícil da tradução de um código switch/case, os cases por si só são bem fáceis de se traduzir, vejam:

L0:      add $s0, $s3, $s4        # Se K = 0 então f = i + j

j EXIT                                      # fim deste case, desvia para EXIT

L1:      add $s0, $s1, $s2        # Se K = 1 então f = g + h

j EXIT                                      # fim deste case, desvia para EXIT

L2:      sub $s0, $s1, $s2        # Se K = 2 então f = g – h

j EXIT                                      # fim deste case, desvia para EXIT

L3:      sub $s0, $s3, $s4        # Se K = 3 então f = i – j

EXIT:                                      # sai do Switch definitivamente

No último case podemos eliminar o desvio para a saída do comando SWITCH, pois as instruções deste case são as últimas, no entanto, um LABEL EXIT deve ser adicionado depois do último comando deste case para marcar o final do comando switch. Assim, o código na íntegra, para você testar no MARS, fica da seguinte forma:

Para finalizar, vamos fazer a tradução para:

a) Linguagem de máquina:

b) Representação das instruções

A instrução LA (load address) é uma pseudoinstrução, isso significa que ela é um tipo de instrução diferente das outras. Essas pseudoinstruções representam outas instruções e facilitam o trabalho de tradução, portanto, LA é uma combinação de duas outras instruções, LUI e ORI, você vai perceber isso ao executar o código no MARS. A instrução LUI significa Load Upper Immediate (Carregar Superior Imediato) e é responsável por carregar a halfword (meia palavra, isto é, 16 bits) menos significativa do valor imediato na halfword mais significativa do registrador RT, sendo os bits menos significativos do registrador colocados em zero.

A instrução ORI significa OR Immediate (Ou imediato) e é responsável por colocar o OR lógico do registrador RS e o valor imediato estendido com zero no registrador RT. Outra instrução que vocês vão notar diferença é a LI, que também é uma pseudoinstrução representando a ADDIU (adição de imediato sem overflow), a qual é responsável por colocar a soma do registrador RS e o valor imediato com sinal estendido no registrador RT, portanto, a tradução da Linguagem de Máquina para a representação não ficará idêntica! Não se esqueçam de que o registrador RT se comporta como o registrador RD (registrador destino) para algumas instruções, como é o caso das instruções envolvendo valores Imediatos. Veja como fica a representação:

Endereço em hexadecimal

Instrução

Representação

OPCODE

RS

RT

RD

SHAMT

FUNCT

0x 1001 0000

jTable

 

 

 

 

 

 

0x 0040 0000

li $17, 15

addiu $17, $0, 0x 0000 000F

9

$0

$17

0x 0000 000F

0x 0040 004

li $18, 20  

addiu $18, $0, 0x 0000 0014

9

$0

$18

0x 0000 0014

0x 0040 008

li $19, 10

addiu $19, $0, 0x 0000 000A

9

$0

$19

0x 0000 000A

0x 0040 000C

li $20, 5

addiu $20, $0, 0x 0000 0005

9

$0

$20

0x 0000 0005

0x 0040 0010

li $21, 2

addiu $21, $0, 0x 0000 0002

9

$0

$21

0x 0000 0002

 

la $12, jTable    

0x 0040 0014

lui $1, 0x 0000 1001

F

0

$1

0x 0000 1001

0x 0040 0018

ori $12, $1, 0x 0000 0000

D

$1

$12

0x 0000 0000

0x 0040 001C

slt $11, $21, $zero

0

$21

$0

$11

0

42

0x 0040 0020

bne $11, $zero, EXIT

5

$11

$0

0x 0040 0058

0x 0040 0024

slti $11, $21, 4

A

$21

$11

4

0x 0040 0028

beq $11, $zero, EXIT

4

$11

$0

0x 0040 0058

0x 0040 002C

sll $9, $21, 2     

0

0

$21

$9

2

0

0x 0040 0030

add $9, $9, $12

0

$9

$12

$9

0

32

0x 0040 0034

lw $8, 0($9)

23

$9

$8

0

0x 0040 0038

jr $8

0

$8

0

8

0x 0040 003C

L0:    add $16, $19, $20

0

$19

$20

$16

0

32

0x 0040 0040

j EXIT

2

0 x 0040 0058

0x 0040 0044

L1:    add $16, $17, $18

0

$17

$18

$16

0

32

0x 0040 0048

j EXIT

2

0 x 0040 0058

0x 0040 004C

L2:    sub $16, $17, $18

0

$17

$18

$16

0

34

0x 0040 0050

j EXIT

2

0 x 0040 0058

0x 0040 0054

L3:    sub $16, $19, $20  

0

$19

$20

$16

0

34

0x 0040 0058

EXIT:

 

c) Código de Máquina

 

Instrução

Representação

OPCODE

RS

RT

RD

SHAMT

FUNCT

0x10010000

jTable

 

 

 

 

 

 

0x00400000

li $17, 15

addiu $17, $0, 0x0000000F

001001

00000

10001

0000 0000 0001 1111

0x0040004

li $18, 20  

addiu $18, $0, 0x00000014

001001

00000

10010

0000 0000 0001 0100

0x0040008

li $19, 10

addiu $19, $0, 0x0000000A

001001

00000

10011

0000 0000 0000 1010

0x0040000C

li $20, 5

addiu $20, $0, 0x00000005

001001

00000

10100

0000 0000 0000 0101

0x00400010

li $21, 2

addiu $21, $0, 0x00000002

001001

00000

10101

0000 0000 0000 0010

 

la $12, jTable    

0x00400014

lui $1, 0x00001001

001111

00000

00001

0001 0000 0000 0001

0x00400018

ori $12, $1, 0x00000000

001101

00001

01100

0000 0000 0000 0000

0x0040001C

slt $11, $21, $zero

000000

10101

00000

01011

00000

101010

0x00400020

bne $11, $zero, EXIT

000101

01011

00000

0100 0000 0101 1000

0x00400024

slti $11, $21, 4

001010

10101

01011

0000 0000 0000 0100

0x00400028

beq $11, $zero, EXIT

000100

01011

00000

0100 0000 0101 1000

0x0040002C

sll $9, $21, 2     

000000

00000

10101

01001

00010

000000

0x00400030

add $9, $9, $12

000000

01001

01100

01001

00000

100000

0x00400034

lw $8, 0($9)

010111

01001

01000

00000

0x00400038

jr $8

000000

01000

0000 0000 0000 000

001000

0x0040003C

L0:    add $16, $19, $20

000000

10000

10011

10100

00000

100000

0x00400040

j EXIT

000010

0100 0000 0101 1000

0x00400044

L1:    add $16, $17, $18

000000

10000

10001

10000

00000

100000

0x00400048

j EXIT

000010

0100 0000 0101 1000

0x0040004C

L2:    sub $16, $17, $18

000000

10000

10001

10000

00000

100010

0x00400050

j EXIT

000010

0100 0000 0101 1000

0x00400054

L3:    sub $16, $19, $20

000000

10000

10011

10100

00000

100010

0x00400058

EXIT:

 

Assim finalizamos o processo de tradução do switch/case em C para MIPS.

Conclusão

Pessoal, sugiro que vocês tentem refazer o exemplo demonstrado aqui e, além disso, tentem colocar mais labels e inserir outros tipos de instruções dentro de cada label. A única forma de realmente aprender é praticando, assim, sugiro também que vocês peguem alguns exemplos de switch/cases de algoritmos simples que tenham feito, ou até mesmo aqui dos meus artigos de Algoritmos, para tentar fazer a compilação para o MIPS. Tudo bem? É isso ai pessoal, se tiverem dúvidas, deixem aqui nos comentário tá bom. Muito Obrigada e até o próximo artigo.

Saiba mais

Conceitos básicos de algoritmos

Comando de Controle Switch Case

Técnicas de Mapeamento de Memória em Linguagem C

Outros artigos da série

<< Compilando While no MIPSCompilando Funções e Procedimentos no MIPS >>
Website | Veja + conteúdo

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!

Licença Creative Commons Esta obra está licenciada com uma Licença Creative Commons Atribuição-CompartilhaIgual 4.0 Internacional.

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

Comentários:
Notificações
Notificar
guest
0 Comentários
Inline Feedbacks
View all comments
Talvez você goste:

Séries



Outros da Série

Menu