Operações e Chamadas de Procedimentos em MIPS

Prévia do material em texto

Operações para Tomada de Decisões Suporte a Procedimentos no Hardware do Computador
Organização de Computadores
Marcelo Lobosco
Universidade Federal de Juiz de Fora
Aula 06 - Instruções: a Linguagem de Máquina
Departamento de Ciência da Computação Universidade Federal de Juiz de Fora
Operações para Tomada de Decisões Suporte a Procedimentos no Hardware do Computador
Operações para Tomada de Decisões
Suporte a Procedimentos no Hardware do Computador
Departamento de Ciência da Computação Universidade Federal de Juiz de Fora
Operações para Tomada de Decisões Suporte a Procedimentos no Hardware do Computador
Operações para Tomada de Decisões
I Instruções de tomada de decisão alteram o fluxo de instruções
I Muda a próxima instrução a ser executada
I Instruções de desvio condicional do MIPS (beq e bne)
I beq registrador1, registrador2, L1
I Significa ir até instrução rotulada por L1 se conteúdos de
ambos os registradores forem iguais
I branch if equal (desviar se for igual)
I bne registrador1, registrador2, L1
I Significa ir até instrução rotulada por L1 se conteúdos de
ambos os registradores forem diferentes
I branch if not equal (desviar se diferente)
Departamento de Ciência da Computação Universidade Federal de Juiz de Fora
Operações para Tomada de Decisões Suporte a Procedimentos no Hardware do Computador
Exercício
I Transforme o fragmento de código C abaixo em código
assembly MIPS. Considere que a variável i é armazenada em
$s0, j em $s1 e h em $s3.
if (i==j) h = i + j;
I Uma das formas de se implementar em MIPS...
bne $s0, $s1, Label
add $s3, $s0, $s1
Label: ....
Departamento de Ciência da Computação Universidade Federal de Juiz de Fora
Operações para Tomada de Decisões Suporte a Procedimentos no Hardware do Computador
Operações para Tomada de Decisões
I Instrução de desvio incondicional do MIPS (j)
I Desvia para instruções que segue rótulo independente de
condição
I j label
I Exemplo: transformar o código C abaixo em assembly MIPS
i f ( i!=j )
h=i+j ;
e l s e
h=i−j ;
beq $s4, $s5, Lab1
add $s3, $s4, $s5
j Lab2
Lab1: sub $s3, $s4, $s5
Lab2: ...
Departamento de Ciência da Computação Universidade Federal de Juiz de Fora
Operações para Tomada de Decisões Suporte a Procedimentos no Hardware do Computador
Operações para Tomada de Decisões
I Sequências de instruções que terminam em um desvio são
chamados de bloco básico
I Não possuem destinos de desvio ou rótulos de desvio
I Exceto, possivelmente, no início
I Testes de igualdade/desigualdade não resolvem todos os
problemas
I E se decisão baseada em uma variável ser ou não menor do
que outra?
Departamento de Ciência da Computação Universidade Federal de Juiz de Fora
Operações para Tomada de Decisões Suporte a Procedimentos no Hardware do Computador
Operações para Tomada de Decisões
I Instrução slt (set on less than: atribui se menor que)
I slt $t0, $s3, $s4 # $t0 = 1 se $s3 < $s4
I Valor 1 atribuído ao registrador $t0 se o valor de $s3 for menor
que $s4, caso contrário atribuído valor 0
I Operadores constantes populares em atribuições
I slti $t0, $s2, 10 # $t0 = 1 se $s2 < 10
Departamento de Ciência da Computação Universidade Federal de Juiz de Fora
Operações para Tomada de Decisões Suporte a Procedimentos no Hardware do Computador
Chamadas de procedimento
I Procedimento (ou função)
I Sub-rotina armazenada que realiza uma tarefa com base nos
parâmetros com os quais ela é provida
I Usada para estruturar programas
I Permite que código seja reutilizado
Departamento de Ciência da Computação Universidade Federal de Juiz de Fora
Operações para Tomada de Decisões Suporte a Procedimentos no Hardware do Computador
Etapas na chamadas de procedimentos
I Seis etapas precisam ser seguidas:
I Colocar parâmetros onde procedimento possa acessá-los
I Transferir controle para o procedimento
I Adquirir recursos necessários para o procedimento
I Realizar tarefa desejada
I Colocar valor de retorno onde código que o chamou possa
acessá-lo
I Retornar controle para o ponto de origem
Departamento de Ciência da Computação Universidade Federal de Juiz de Fora
Operações para Tomada de Decisões Suporte a Procedimentos no Hardware do Computador
Etapas na chamadas de procedimentos
I Registradores usados para a chamada de procedimento:
I $a0 - $a3: usados para passar parâmetros
I $v0 - $v1: usados para valores de retorno
I $ra: registrador de endereço de retorno, usado para retornar ao
ponto de origem
I Instrução para invocar procedimentos: jal
I jal EndereçoProcedimento # jal (jump and link)
I Desvia para endereço e simultaneamente salva endereço da
instrução seguinte no registrador $ra
I Instrução seguinte dada por PC + 4
I PC (Program counter ou contador de programa): registrador
que contém o endereço da instrução que está sendo executada
Departamento de Ciência da Computação Universidade Federal de Juiz de Fora
Operações para Tomada de Decisões Suporte a Procedimentos no Hardware do Computador
Etapas nas chamadas de procedimentos
I Instrução jump register (jr) permite fazer desvio incondicional
para endereço especificado em um registrador
I jr $ra
I Cabe ao código que chama o procedimento (caller)
I Colocar valores dos parâmetros em $a0-$a3
I Utilizar jal X para desviar para o procedimento X
I Cabe ao código invocado (callee)
I Executar as instruções
I Colocar eventuais resultados em $v0 - $v1
I Retornar controle para caller usando jr $ra
Departamento de Ciência da Computação Universidade Federal de Juiz de Fora
Operações para Tomada de Decisões Suporte a Procedimentos no Hardware do Computador
Observações sobre chamada de procedimentos
I Durante execução, procedimento pode precisar usar
registradores
I Mas e se os registradores estavam sendo usados pelo caller?
I Depois de completar a chamada, caller espera que os valores
originais dos seus registradores sejam mantidos
I Se registradores usados durante execução do procedimento,
valores originais devem ser salvos e depois restaurados
Departamento de Ciência da Computação Universidade Federal de Juiz de Fora
Operações para Tomada de Decisões Suporte a Procedimentos no Hardware do Computador
Observações sobre chamadas de procedimentos
I Conceito de spilling registers utilizado
I Variáveis menos utilizadas armazenadas na memória
I Pilha usada para implementar spilling registers
I Organizada como fila do tipo “último a entrar, primeiro a sair”
I Ponteiro para endereço mais recentemente alocado na pilha
I Chamado de stack pointer ($sp)
I Indica onde valores antigos estão localizados e/ou
I Mostra onde próximo procedimento deverá alocar os spilling
registers
Departamento de Ciência da Computação Universidade Federal de Juiz de Fora
Operações para Tomada de Decisões Suporte a Procedimentos no Hardware do Computador
Observações sobre chamadas de procedimentos
Departamento de Ciência da Computação Universidade Federal de Juiz de Fora
Operações para Tomada de Decisões Suporte a Procedimentos no Hardware do Computador
Observações sobre chamadas de procedimentos
I Exemplo: Qual o código assembly MIPS compilado para a
seguinte função?
i n t exemplo ( i n t g , i n t h , i n t i , i n t j ) {
i n t f ;
f=(g+h)−(i+j ) ;
r e t u r n f ;
}
Departamento de Ciência da Computação Universidade Federal de Juiz de Fora
Operações para Tomada de Decisões Suporte a Procedimentos no Hardware do Computador
Exemplo
I Variáveis g, h, i e j correspondem aos registradores $a0, $a1,
$a2 e $a3
I Variável f corresponde a $s0
I Procedimento começa com rótulo (label) com o nome do
procedimento
exemplo:
Departamento de Ciência da Computação Universidade Federal de Juiz de Fora
Operações para Tomada de Decisões Suporte a Procedimentos no Hardware do Computador
Exemplo
I Próximo passo: salvar registradores usados pelo procedimento
I Valores antigos empilhados
I Importante: registradores temporários não precisam ser
preservados em uma chamada de procedimento
I Só precisamos salvar registrador $s0
Departamento de Ciência da ComputaçãoUniversidade Federal de Juiz de Fora
Operações para Tomada de Decisões Suporte a Procedimentos no Hardware do Computador
Exemplo
I Precisamos primeiro criar espaço na pilha: para isso
subtraímos de $sp o valor que precisamos
addi $sp, $sp, -4 # ajustamos a pilha
sw $s0, 0 ($sp) # salva registrador para uso posterior
I Corpo do procedimento
add $t0, $a0, $a1 # $t0 = g + h
add $t1, $a2, $a3 # $t1 = i + j
sub $s0, $t0, $t1 # f = $t0 - $t1
add $v0, $s0, $zero # retorna f ($v0 = $s0 + 0)
I Restauramos valores dos registradores antes do retorno
lw $s0, 0 ($sp) # restaura registrador utilizado
addi $sp, $sp, 4 # exclui um item da pilha
I Procedimento termina com salto para endereço de retorno
jr $ra # retorna para código que chamou procedimento
Departamento de Ciência da Computação Universidade Federal de Juiz de Fora
Operações para Tomada de Decisões Suporte a Procedimentos no Hardware do Computador
Exemplo
Departamento de Ciência da Computação Universidade Federal de Juiz de Fora
Operações para Tomada de Decisões Suporte a Procedimentos no Hardware do Computador
Observações sobre chamadas de procedimentos
I Procedimentos aninhados
I Procedimentos que não chamam outros procedimentos
chamados folha
I Procedimentos podem chamar outros procedimentos?
I O que ocorreria se seguinte sequência ocorresse:
I Programa principal chama procedimento A, passando 3 como
argumento
I Procedimento A chama procedimento B, passando 7 como
argumento
Departamento de Ciência da Computação Universidade Federal de Juiz de Fora
Operações para Tomada de Decisões Suporte a Procedimentos no Hardware do Computador
Observações sobre chamadas de procedimentos
I Poderíamos perder valores originais de $a0 e de $ra
I Solução: empilhar todos os registradores que precisam ser
preservados
I Neste caso, incluindo qualquer registrador temporário que
precise ser utilizado posteriormente
I Caller empilha registradores de argumento ($a0-$a3) e
temporários ($t0-$t9) que sejam necessários após chamada
I Callee empilha $ra e quaisquer registradores $s0-$s7 usados
por ele
I Stack pointer atualizado para refletir total de registradores
salvos na pilha
I No retorno, registradores restaurados e $sp reajustado
Departamento de Ciência da Computação Universidade Federal de Juiz de Fora
Operações para Tomada de Decisões Suporte a Procedimentos no Hardware do Computador
Observações sobre chamadas de procedimentos
I Exercício: Qual o código assembly para a função recursiva
abaixo?
i n t fact ( i n t n ) {
i f ( n < 1) r e t u r n 1 ;
e l s e r e t u r n ( n ∗ fact ( n −1)) ;
}
Departamento de Ciência da Computação Universidade Federal de Juiz de Fora
Operações para Tomada de Decisões Suporte a Procedimentos no Hardware do Computador
Exercício
I Parâmetro n corresponde ao registrador $a0
I Função começa com rótulo, e depois salva registradores na
pilha
fact:
addi $sp, $sp, -8 # ajusta pilha para dois itens
sw $ra, 4($sp) # salva endereço de retorno
sw $a0, 0($sp) # salva argumento n
I Primeira vez que fact chamado: salva endereço do código que
o chamou
I Instruções seguintes testam se n é menor que 1
slti $t0, $a0, 1 #teste se n < 1
beq $t0, $zero, L1 # se n >=1, vai para L1
Departamento de Ciência da Computação Universidade Federal de Juiz de Fora
Operações para Tomada de Decisões Suporte a Procedimentos no Hardware do Computador
Exercício
I Se n<1, fact retorna 1 e restaura valores da pilha
addi $v0, $zero, 1 # retorna 1
addi $sp, $sp, 8 # retira 2 itens da pilha
jr $ra # retorna para depois de jal
I Porque não restauramos $a0 e $ra?
I Porque seus valores não mudaram!
I Se n é maior ou igual à 1, argumento decrementado, e fact
chamado com valor decrementado
L1: addi $a0, $a0, -1 # n >=1 : argumento recebe (n-1)
jal fact # chama fact com (n-1)
Departamento de Ciência da Computação Universidade Federal de Juiz de Fora
Operações para Tomada de Decisões Suporte a Procedimentos no Hardware do Computador
Exercício
I Próxima instrução é onde fact retorna: endereço de retorno
antigo, argumento antigo e stack pointer restaurados
lw $a0, 0 ($sp) # retorna de jal, restaura argumento n
lw $ra, 4 ($sp) # restaura endereço de retorno
addi $sp, $sp, 8 # ajusta stack pointer para retirar 2 itens
I Operação final antes do retorno: cálculo do produto do
argumento antigo pelo valor retornado
mul $v0, $a0, $v0 # retorna n * fact (n - 1)
I Salto para endereço de retorno original
jr $ra # retorna para que chamou
Departamento de Ciência da Computação Universidade Federal de Juiz de Fora
Operações para Tomada de Decisões Suporte a Procedimentos no Hardware do Computador
Observações sobre chamadas de procedimentos
I Alocando espaço para novos dados na pilha
I Pilha também usada para armazenar variáveis locais ao
procedimento que não cabem nos registradores
I Segmento da pilha que contém registradores salvos e variáveis
locais de um procedimento chamado de registro de ativação
(ou frame de procedimento)
I $fp aponta para primeira palavra do registro de ativação
I Como $sp pode mudar ao longo da execução do código,
referência a variáveis locais poderia ter offsets diferentes,
dependendo de onde estiverem no código
I Evitaremos seu uso
Departamento de Ciência da Computação Universidade Federal de Juiz de Fora
Operações para Tomada de Decisões Suporte a Procedimentos no Hardware do Computador
Observações sobre chamadas de procedimentos
Departamento de Ciência da Computação Universidade Federal de Juiz de Fora
Operações para Tomada de Decisões Suporte a Procedimentos no Hardware do Computador
Observações sobre chamadas de procedimentos
I Alocando espaço para novos dados na heap
I Programas C possuem dois tipos de variáveis
I Automáticas: escopo local a um procedimento, sendo
descartadas quanto este termina
I Estáticas: escopo global para variáveis declaradas fora de um
procedimento ou com uso da palavra reservada static
I Registrador $gp simplifica acesso aos dados estáticos
Departamento de Ciência da Computação Universidade Federal de Juiz de Fora
Operações para Tomada de Decisões Suporte a Procedimentos no Hardware do Computador
Observações sobre chamadas de procedimentos
I Variáveis estáticas e estruturas de dados dinâmicas alocadas
segundo uma convenção
Departamento de Ciência da Computação Universidade Federal de Juiz de Fora
Operações para Tomada de Decisões Suporte a Procedimentos no Hardware do Computador
Observações sobre chamadas de procedimentos
I Pilha começa na parte alta da memória e “cresce” para baixo,
como já visto
I Primeira parte da extremidade baixa da memória é reservada
I Código de máquina do MIPS na sequência
I Denominado segmento de texto
I Segmento seguinte chamado de segmento de dados estáticos
I Local para constantes e outras variáveis estáticas
I Heap na sequência
I Armazena dados dinâmicos (malloc do C e new do Java)
Departamento de Ciência da Computação Universidade Federal de Juiz de Fora
Operações para Tomada de Decisões Suporte a Procedimentos no Hardware do Computador
Observações sobre chamadas de procedimentos
I E se houver mais de quatro parâmetros?
I Quatro primeiros parâmetros alocados nos registradores
I Parâmetros extras alocados na pilha
Departamento de Ciência da Computação Universidade Federal de Juiz de Fora
Operações para Tomada de Decisões Suporte a Procedimentos no Hardware do Computador
Próxima aula...
I Instruções: a Linguagem de Máquina
I Comunicando-se com as Pessoas
I Endereçamento no MIPS
I Traduzindo e Iniciando um Programa
Departamento de Ciência da Computação Universidade Federal de Juiz de Fora
	Operações para Tomada de Decisões
	Suporte a Procedimentos no Hardware do Computador