Compilando Switch/Case no MIPS

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

ÍNDICE DE CONTEÚDO

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 >>
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.

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

Elaine Cecília Gatto
Bacharel em Engenharia de Computação. Mestre em Ciência da Computação. Doutoranda em Ciência da Computação. Co-fundarora e Líder das #GarotasCPBr. Pesquisadora Convidada no Grupo de Pesquisa: "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, Rocky Balboa, Séries, Filmes, Cervejas e Vinhos. Mais informações sobre mim você encontra em: http://lattes.cnpq.br/8559022477811603.

Deixe um comentário

avatar
 
  Notificações  
Notificar