ÍNDICE DE CONTEÚDO
- Arquitetura de Conjunto de Instruções MIPS
- Primeira Instrução MIPS
- Compilação de Expressões no MIPS
- Convertendo uma instrução com Array no MIPS
- Armazenando um valor em Array no MIPS
- Instruções LW e SW com Array no MIPS
- Instrução IF Simples no MIPS
- Instrução IF Composto no MIPS
- Instrução SLT no MIPS
- Operações Lógicas no MIPS
- Operação Lógica AND no MIPS
- Operação Lógica OR no MIPS
- Operação Lógica NOT no MIPS
- Endereços de Memória no MIPS
- Operandos Imediatos e Constantes no MIPS
- Compilando Arrays com índice variável no MIPS
- Testando as instruções MIPS no MARS
- Executando um Array no MARS para MIPS
- Sinal e Overflow no MIPS
- Compilando instruções com ou sem Sinal, Overflow e Imediato no MIPS
- Compilando While no MIPS
- Compilando Switch/Case no MIPS
- Compilando Funções e Procedimentos no MIPS
- Compilando Procedimentos Recursivos e Aninhados no MIPS
- Detalhamento da Compilação de Procedimentos no MIPS
- MIPS: Instruções de Multiplicação
- MIPS: Instruções de Divisão
- MIPS: Subtração e outras instruções
- Compilando o comando FOR no MIPS
- Ponto Flutuante no MIPS
- Convertendo Código de Máquina em Assembly MIPS – Parte 1
- MIPS: Resolução dos exercícios – Parte 1
- MIPS: Resolução de Exercícios Parte 2
- Compilando Potência no MIPS
- Criando e Manipulando Matrizes no MIPS
Neste artigo vou mostrar para vocês como criar e manipular matrizes de duas dimensões usando o MARS como simulador MIPS. A partir desta base você será capaz de fazer outras operações com matrizes no MIPS. Vai ser divertido! Usarei funções neste artigo então, caso você ainda não tenha lido meus artigos sobre o tema, seria bom fazê-lo antes de começar aqui ta ok?! Bora lá!
Entendendo as Matrizes no MIPS
Antes de começarmos a codificar no MARS vamos dar uma olhada em como a matriz é organizada para a codificação. Na Figura 1 apresento uma matriz com 4 linhas e 4 colunas o que resulta em 16 elementos. Observe que a contagem começa com zero!!! A Figura 2 apresenta uma abstração da Matriz 4×4.
Vou indicar a matriz com a letra m e m[i,j] a posição de cada elemento na matriz: m[0,0] é o cruzamento da linha zero com a coluna zero, m[1,2] é o cruzamento da linha 1 com a coluna2, e assim por diante. Apesar de representarmos as matrizes em duas ou mais dimensões, elas na verdade são uma abstração. Toda a memória é unidimensional!!! Isso signfica que a memória de um computador de 32 bits consiste em uma matriz de bytes começando do índice (endereço) 0 x 0000 0000 e indo até o índice (endereço) 0 x ffff ffff. No entanto, muitos tipos de problemas são muito mais fáceis de resolver se pudermos não apenas pensar em termos de matrizes bidimensionais, mas também expressar nossa solução de uma forma que use diretamente os índices de linha e coluna de uma matriz bidimensional.
As matrizes bidimensionais são frequentemente implementadas da esquerda para a direita e de cima pra baixo, o que é chamado de row-major, ou traduzindo para pt-br: ordem de linha principal. Também é possível implementar como column-major, isto é, de cima para baixo e da esquerda para a direita, portanto, em ordem de coluna principal. As Figuras 4 e 5 ilustram essas duas formas. Em row-major, a linha fica travada até que todas as colunas sejam lidas ou escritas, ai passa-se para a próxima linha, le/escreve as colunas e assim continua até terminar. Em column-major, as colunas ficam travadas e as linhas são lidas ou escritas, até que todas as posições sejam lidas/escritas. Em seguida de cada Figura está o código correspondente.
|
1 2 3 4 5 |
for(int linha=0; linha<tamanho_linha; linha++ ){ for(int coluna=0, coluna<tamanho_coluna, coluna++){ // m[i][j] } } |
|
1 2 3 4 5 |
for(int coluna=0; coluna<tamanho_coluna; coluna++ ){ for(int linha=0, linha<tamanho_linha, linha++){ // m[i][j] } } |
A Figura 3 apresenta como fica a Matriz Bidimensional 4×4 na Memória usando row-major, enquanto a Figura 4 mostra a organização como column-major.
A partir daqui já podemos abstrair algumas informações importantes para codificarmos a matriz no MIPS:
- L: número total de linhas da matriz (4)
- C: número total de colunas da matriz (4)
- eL: número de elementos em uma linha (4)
- eC: número de elementos em uma coluna (4)
- iL: índice da linha
- iC: índice da coluna
- M: nome da matriz
- M[linha][coluna]: um elemento da matriz
- bM: endereço base da matriz
- aM: endereço de um elemento da matriz
- T: tamanho total da matriz (16)
Precisaremos de algumas dessas informações para construir nosso código em MIPS. O que vamos implementar aqui será o row_major.
Definindo a matriz
Bom, a primeira coisa que precisamos fazer em nosso código MIPS é definir a matriz e isso é feito no segmento de dados
|
1 2 3 |
.data M: .word 0:16 # inicializa todos os elementos da matriz com zero tamanho: .word 16 # tamanho da matriz |
M é o nome da matriz. Como ela terá 16 elementos (4×4) então colocamos .word 0:16 que já vai inicializar cada elemento da matriz com o valor zero. Você também pode definir aqui o tamanho e as outras abstrações que listamos e usar dentro do seu codigo. Por simplicidade do entendimento, optei por não fazer isto, mas sinta-se livre para otimizar o código e deixá-lo com sua cara!
Outra coisa que quero fazer é pedir para que o usuário digite os valores para essa matriz. Se você não quer fazer isso, basta inicializar a matriz da seguinte forma:
|
1 2 3 4 5 |
.data M: .word 3, 14, 15, 9 .word 2, 6, 53, 5 .word 89, 79, 3, 23 .word 84, 62, 643, 38 |
Como vou solicitar os valores, preciso imprimir uma mensagem no console, avisando o usuário. Essas mensagens também devem ser definidas no segmento de dados. Portanto, ficará assim:
|
1 2 3 4 5 6 |
.data .align 4 # alinhamento de memória m1: .asciiz "\nDigite um número inteiro:\t" m2: .asciiz "\nM[linha][coluna]:\t" M: .word 0:16 # inicializa todos os elementos da matriz com zero tamanho: .word 16 # tamanho da matriz |
Não esqueça de colocar .align 4 para que o alinhamento de memória seja feito corretamente!
Função MAIN
Definida a matriz, precisamos agora codificar o programa principal já que farei duas funções aqui: uma para preencher a matriz e outra para imprimi-la. Para facilitar ainda mais, não passarei nenhum parametro nessas funções. Mas, novamente, sintam-se livre para modificar o código!
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
.text main: # setando a pilha de chamada de procedimentos subu $sp, $sp, 32 # o frame de pilha tenm 32 bytes sw $ra, 20($sp) # salva o endereço de retorno sw $fp, 16($sp) # salva o ponteiro do frame addiu $sp, $sp, 28 # prepara o ponteiro do frame jal matriz_preenche jal matriz_imprime # re-setando a pilha de chamada de procedimentos lw $ra, 20($sp) # restaura o endereço lw $fp, 16($sp) # restaura o frame pointer addiu $sp, $sp, 32 # remove do frame j FIM # finaliza o programa FIM: li $v0, 10 syscall |
Lembram-se que sempre que trabalhamos com funções precisamos definir as configurações do frame de pilha? Caso ainda não saiba como fazer isto, por favor, leia os seguintes artigos antes de continuar aqui:
Basicamente, na função main, inicializamos o frame de pilha, chamamos as funções para preencher e imprimir a matriz e então finalizamos com as configurações do frame de pilha. A linha j FIM chama a finalização correta do programa.
Função para popular a matriz
Como estamos lidando com função, então, aqui novamente precisamos inicializar e finalizar as configurações do frame de pilha. Dei o nome de matriz_preenche à função e ao LOOP para preencher a matriz eu dei o nome de popula_matriz. Dentro da função matriz_preenche a primeira coisa que fazemos é inicializar o frame de pilha.
|
1 2 3 4 5 6 7 |
matriz_preenche: # configurações da pilha subu $sp, $sp, 32 # reserva o espaço do frame ($sp) sw $ra, 20($sp) # salva o endereço de retorno ($ra) sw $fp, 16($sp) # salva o frame pointer ($fp) addiu $fp, $sp, 28 # prepara o frame pointer sw $a0, 0($fp) # salva o argumento ($a0) |
Em seguida inicializo os registradores do número de linhas, número de colunas, contador da linha, contador da coluna e o registrador que guardará o valor do elemento da matriz.
|
1 2 3 4 5 |
li $t0, 4 # $t0: número de linhas li $t1, 4 # $t1: número de colunas move $s0, $zero # $s0: contador da linha move $s1, $zero # $s1: contador da coluna move $t2, $zero # $t2: valor a ser lido/armazenado |
O próximo passo é o LOOP! Aqui precisamos fazer o cálculo correto do endereço do elemento da matriz. Cada iteração do LOOP armazenará o valor de $t1 incrementado no próximo elemento da matriz. O deslocamento é calculado a cada iteração: deslocamento = 4 * (linha * número de colunas + coluna)
|
1 2 3 4 5 |
popula_matriz: mult $s0, $t1 # $s2 = linha * numero de colunas mflo $s2 # move o resultado da multiplicação do registrador lo para $s2 add $s2, $s2, $s1 # $s2 += contador de coluna sll $s2, $s2, 2 # $s2 *= 4 (deslocamento 2 bits para a esquerda) para deslocamento de byte |
Depois de realizar o cálculo, podemos solicitar ao usuário que digite o valor do elemento
|
1 2 3 4 5 6 |
li $v0, 4 la $a0, m1 syscall li $v0, 5 syscall move $t2, $v0 |
Digitado no console, já conseguimos pegar o valor e salvá-lo no registrador:
|
1 |
sw $t2, M($s2) |
Agora temos de incrementar o contador
|
1 |
addi $t2, $t2, 1 |
O próximo passo é verificar se estamos no limite do número de linhas e de colunas. Se ainda não chegamos no final de uma linha, voltamos ao LOOP. Quando chegamos ao final de uma linha, precisamos ir para a próxima linha, até que todas as linhas sejam preenchidas. O mesmo se aplica à coluna. O contador da coluna precisa ser resetado pois ao terminar uma linha passamos por toda as colunas daquela linha e a próxima linha começa na coluna zero.
|
1 2 3 4 5 |
addi $s1, $s1, 1 # incrementa contador da coluna bne $s1, $t1, popula_matriz # não é o fim da linha então LOOP move $s1, $zero # reseta o contador da coluna addi $s0, $s0, 1 # incrementa o contador da linha bne $s0, $t0, popula_matriz # não é o fim da matriz então LOOP |
Note que, no primeiro BNE, o desvio só vai acontecer se $s1 não for diferente de $t1, e no segundo BNE, só vai desviar se $s0 for diferente de $t0. Depois disso precisamos finalizar a função corretamente:
|
1 2 |
add $v0, $s1, $zero jr $ra |
Função para imprimir a matriz
A função para imprimir a matriz é exatamente igual à função para preencher a matriz. A principal diferença é que aqui não vamos pedir para o usuário digitar nada, vamos apenas pegar os valores que estão armazenados e printar no console.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
matriz_imprime: # configurações da pilha subu $sp, $sp, 32 # reserva o espaço do frame ($sp) sw $ra, 20($sp) # salva o endereço de retorno ($ra) sw $fp, 16($sp) # salva o frame pointer ($fp) addiu $fp, $sp, 28 # prepara o frame pointer sw $a0, 0($fp) # salva o argumento ($a0) li $t0, 4 # $t0: número de linhas li $t1, 4 # $t1: número de colunas move $s0, $zero # $s0: contador da linha move $s1, $zero # $s1: contador da coluna move $t2, $zero # $t2: valor a ser lido/armazenado imprime_matriz: # calcula o endereço correto do array mult $s0, $t1 # $s2 = linha * numero de colunas mflo $s2 # move o resultado da multiplicação do registrador lo para $s2 add $s2, $s2, $s1 # $s2 += contador de coluna sll $s2, $s2, 2 # $s2 *= 4 (deslocamento 2 bits para a esquerda) para deslocamento de byte # obtem o valor do elemento armazenado lw $t2, M($s2) # imprime no console o valor do elemento da matriz li $v0, 4 la $a0, m2 syscall li $v0,1 move $a0, $t2 syscall # incrementa o contador addi $t2, $t2, 1 addi $s1, $s1, 1 # incrementa contador de coluna bne $s1, $t1, imprime_matriz # não é o fim da linha então LOOP move $s1, $zero # reseta o contador da coluna addi $s0, $s0, 1 # increment row counter bne $s0, $t0, imprime_matriz # não é o fim da matriz então LOOP jr $ra # configurações do procedimento add $v0, $s1, $zero # retorna para quem chamou jr $ra |
Código Completo
Segue aqui o código completinho para você testar no MARS.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 |
.data .align 4 # alinhamento de memória m1: .asciiz "\nDigite um número inteiro:\t" m2: .asciiz "\nM[linha][coluna]:\t" M: .word 0:16 # inicializa todos os elementos da matriz com zero tamanho: .word 16 # tamanho da matriz .text main: # setando a pilha de chamada de procedimentos subu $sp, $sp, 32 # o frame de pilha tenm 32 bytes sw $ra, 20($sp) # salva o endereço de retorno sw $fp, 16($sp) # salva o ponteiro do frame addiu $sp, $sp, 28 # prepara o ponteiro do frame jal matriz_preenche jal matriz_imprime # re-setando a pilha de chamada de procedimentos lw $ra, 20($sp) # restaura o endereço lw $fp, 16($sp) # restaura o frame pointer addiu $sp, $sp, 32 # remove do frame j FIM # finaliza o programa matriz_preenche: # configurações da pilha subu $sp, $sp, 32 # reserva o espaço do frame ($sp) sw $ra, 20($sp) # salva o endereço de retorno ($ra) sw $fp, 16($sp) # salva o frame pointer ($fp) addiu $fp, $sp, 28 # prepara o frame pointer sw $a0, 0($fp) # salva o argumento ($a0) li $t0, 4 # $t0: número de linhas li $t1, 4 # $t1: número de colunas move $s0, $zero # $s0: contador da linha move $s1, $zero # $s1: contador da coluna move $t2, $zero # $t2: valor a ser lido/armazenado popula_matriz: # Cada iteração de loop armazenará o valor de $t1 incrementado no próximo elemento da matriz # O deslocamento é calculado a cada iteração: deslocamento = 4 * (linha * número de colunas + coluna) # calcula o endereço correto do array mult $s0, $t1 # $s2 = linha * numero de colunas mflo $s2 # move o resultado da multiplicação do registrador lo para $s2 add $s2, $s2, $s1 # $s2 += contador de coluna sll $s2, $s2, 2 # $s2 *= 4 (deslocamento 2 bits para a esquerda) para deslocamento de byte # solicita que o usuário digite um número inteiro li $v0, 4 la $a0, m1 syscall li $v0, 5 syscall move $t2, $v0 # armazena o valor digitado pelo usuário sw $t2, M($s2) # incrementa o contador addi $t2, $t2, 1 # Controle de loop: # se incrementarmos além da última coluna, redefinir o contador de coluna # e incrementar o contador de linha # se incrementarmos além da última linha, terminaremos. addi $s1, $s1, 1 # incrementa contador da coluna bne $s1, $t1, popula_matriz # não é o fim da linha então LOOP move $s1, $zero # reseta o contador da coluna addi $s0, $s0, 1 # incrementa o contador da linha bne $s0, $t0, popula_matriz # não é o fim da matriz então LOOP jr $ra # configurações do procedimento add $v0, $s1, $zero # retorna para quem chamou jr $ra matriz_imprime: # configurações da pilha subu $sp, $sp, 32 # reserva o espaço do frame ($sp) sw $ra, 20($sp) # salva o endereço de retorno ($ra) sw $fp, 16($sp) # salva o frame pointer ($fp) addiu $fp, $sp, 28 # prepara o frame pointer sw $a0, 0($fp) # salva o argumento ($a0) li $t0, 4 # $t0: número de linhas li $t1, 4 # $t1: número de colunas move $s0, $zero # $s0: contador da linha move $s1, $zero # $s1: contador da coluna move $t2, $zero # $t2: valor a ser lido/armazenado imprime_matriz: # calcula o endereço correto do array mult $s0, $t1 # $s2 = linha * numero de colunas mflo $s2 # move o resultado da multiplicação do registrador lo para $s2 add $s2, $s2, $s1 # $s2 += contador de coluna sll $s2, $s2, 2 # $s2 *= 4 (deslocamento 2 bits para a esquerda) para deslocamento de byte # obtem o valor do elemento armazenado lw $t2, M($s2) # imprime no console o valor do elemento da matriz li $v0, 4 la $a0, m2 syscall li $v0,1 move $a0, $t2 syscall # incrementa o contador addi $t2, $t2, 1 addi $s1, $s1, 1 # increment column counter bne $s1, $t1, imprime_matriz # not at end of row so loop back move $s1, $zero # reset column counter addi $s0, $s0, 1 # increment row counter bne $s0, $t0, imprime_matriz # not at end of matrix so loop back jr $ra # configurações do procedimento add $v0, $s1, $zero # retorna para quem chamou jr $ra FIM: li $v0, 10 syscall |
Cheat Sheets (resumo)
Pessoal, eu fiz um resumão sobre MIPS e PIPELINE que estão disponíveis no meu Github. Espero que este material seja útil para vocês. Se gostarem, por favor, compartilhem e deixem uma estrelinha lá pra mim. Seguem os links:
https://github.com/cissagatto/CheatSheetPipelineMIPS32Bits
https://github.com/cissagatto/MIPS32BitsCheatsheet
É isso pessoal! Espero que vocês tenham gostado. Caso não tenham entendido algo, por favor, deixem aqui nos comentários que responderei ok!?? Até o próximo artigo.
Referências
https://courses.missouristate.edu/kenvollmar/mars/CCSC-CP%20material/row-major.asm
https://courses.missouristate.edu/KenVollmar/mars/CCSC-CP%20material/column-major.asm
