Arquitetura de Computadores Capitulo 7

Prévia do material em texto

1
OAC – Ling. de Máquina – Strings, Endereçamento - 1 Juliana F Camapum Wanderley
Organização e Arquitetura de Computadores 
Aula 7 – Linguagem de Máquina
Strings, Endereçamento Imediato e Relativo
e Pseudo-Instruções
2002
Juliana F. Camapum Wanderley
http://www.cic.unb.br/docentes/juliana/cursos/oac
OAC – Ling. de Máquina – Strings, Endereçamento - 2 Juliana F Camapum Wanderley
Panorama
„ Além dos Números →Textos
„ Endereçamento imediato (constantes)
„ Endereçamento relativo (desvios 
condicionais)
„ Endereçamento absoluto (desvios 
incondicionais)
„ Montador → Pseudo-instruções
2
OAC – Ling. de Máquina – Strings, Endereçamento - 3 Juliana F Camapum Wanderley
Além dos Números
„ Computadores: inicialmente números.
„ Depois: textos.
„ Muito usado: código ASCII.
„ Seria possível usar instruções vistas até agora (carga de palavra de 32 bits).
„ Entretanto: operação muito comum → uma instrução específica:
OAC – Ling. de Máquina – Strings, Endereçamento - 4 Juliana F Camapum Wanderley
Transferência de Bytes
„ lb $t0,0($sp) # ler um byte da memória.
„ sb $t0,0($sp) # escrever um byte.
„ Cada byte ocupa uma posição da memória.
„ Representação de caracteres:
„ 1a posição é reservada para o tamanho do mesmo.
„ Uma variável associada ao string guarda o tamanho.
„ Na última posição do string aparece um caracter nulo 
(ASCII '0'). Usado na linguagem C.
„ Exemplo: rotina para copiar um string para outro.
Void strcpy(char x[ ], char y[ ]) {
int i;
i =0;
while (x[i]=y[i]!= 0) i = i+1;
}
3
OAC – Ling. de Máquina – Strings, Endereçamento - 5 Juliana F Camapum Wanderley
Compilação (1/2)
„ x e y: $a0 e $a1, $s0 para i
strcpy: addi $sp,$sp,-4 # reserva espaço na pilha
sw $s0,0($sp) # salva $s0 (índice i)
add $s0,$zero,$zero # i = 0
L1: add $t1,$a1,$s0 # $t1=end. de y[i]=y+i
lb $t2,0($t1) # $t2 ← y[i]
add $t3,$a0,$s0 # $t3=end de x[i]=x+i
sb $t2,0($t3) # x[i] ← y[i]
addi $s0,$s0,1 # i ← i + 1
bne $t2,$zero,L1 # Volta se y[i]≠0
lw $s0,0($sp) # restaura $s0
addi $sp,$sp,4 # restaura $sp
jr $ra
Void strcpy(char x[ ], char y[ ]) {
int i;
i =0;
while (x[i]=y[i]!= 0) i = i+1;
}
OAC – Ling. de Máquina – Strings, Endereçamento - 6 Juliana F Camapum Wanderley
Compilação (2/2)
„ Nota:
„ Procedimento anterior: folha.
„ Seria melhor, ao invés de usar $s0, usar $t0.
„ Não é obrigatório preservar valores de variáveis temporárias.
4
OAC – Ling. de Máquina – Strings, Endereçamento - 7 Juliana F Camapum Wanderley
Operandos Imediatos ou Constantes
„ Incremento do índice de um array.
„ Incremento do contador de um laço.
„ Ajuste do $sp.
„ Exemplo: SPEC...
„ gcc: 52% das ops: imediatos.
„ Spice: 69%.
„ Oferecer versões de instruções em que um dos
operandos é uma constante.
„ Constante: mantida dentro da própria instrução 
(regularidade).
„ Tipo I (I-type): “I” de Imediato.
„ Tamanho da constante: 16 bits.
OAC – Ling. de Máquina – Strings, Endereçamento - 8 Juliana F Camapum Wanderley
Instruções Imediatas
„ Princípio de projeto 4: Torne o caso comum mais 
rápido.
„ Com estas instruções, não é preciso carregar 
primeiramente as constantes em registradores antes de 
operar.
„ Nomes das Instruções:
„ addi $sp,$sp,4 # $sp ← $sp + 40
op rs rt Imediato
8 29 29 4
6 bits 5 bits 5 bits 16 bits
001000 11101 11101 0000 0000 0000 0100
„ slti $t0,$s2,10 # seta $t0 se $s2 < 10
5
OAC – Ling. de Máquina – Strings, Endereçamento - 9 Juliana F Camapum Wanderley
Instrução “lui” (load upper immediate)
„ Problema: às vezes são necessárias constantes de 32 
bits.
„ Solução: Carregar nos registradores.
„ lui $t0, 255 # 16 bits sup. de $t0 ← 255
„ Exemplo: Carregar este padrão em $s0:
0000 0000 0011 1101 0000 1001 0000 0000
lui $s0,0x003D
addi $s0,$s0,0x0900
OAC – Ling. de Máquina – Strings, Endereçamento - 10 Juliana F Camapum Wanderley
Endereçamento nos Desvios Condicionais e 
Incondicionais
„ Desvio incondicional:
„ j Fim # desvia para Fim (end.800000=0x000C3500)
„ Formato do desvio condicional
„ bne $s0,$s1,Exit # desvia para Exit (end.100) se $s0 ≠ $s1
„ Efeito do end. Relativo: os 16 bits são um offset que somado à próxima 
posição do PC compõe o endereço de destino.
„ J e JAL: não usa end. Relativo.
2 200000=0x0030D40
6 bits 26 bits
5 16 17 6
6 bits 5 bits 5 bits 16 bits
( ) 44end.origemdestino end. )()()( ×++= palavrasPClabel offset
Op endereço (palavras)
Op rs rt offset do endereço(palavras)
End. Instrução bne = 72
(Campo endereço x 4 ) ocupa 28bits: serão 
concatenados 4 bits mais significativos do PC para 
formar o endereço de 32 bits
6
OAC – Ling. de Máquina – Strings, Endereçamento - 11 Juliana F Camapum Wanderley
Exemplo: loop while
Loop: add $t1,$s3,$s3
add $t1,$t1,$t1
add $t1,$t1,$s5
lw $t0,0($t1)
bne $t0,$s5,Exit
add $s3,$s3,$s4
j Loop
Exit:
80000 0 19 19 9 0 32
80004 0 9 9 9 0 32
80008 0 9 21 9 0 32
80012 35 9 8 0
80016 5 8 21 2
80020 0 19 20 19 0 32
80024 2 20000
80028 -----
80032 35 9 8 0
Exit
palavrasbne
palavras
OAC – Ling. de Máquina – Strings, Endereçamento - 12 Juliana F Camapum Wanderley
Desvio condicional grande
„ Neste caso, o montador insere um jump
„ Campo offset (end. relativo) é de 16 bits –
beq, bne
„ Como o campo de offset é relativo a uma 
palavra, representa end. em bytes de 18bits, 
ou seja, ±217= ±128KB
„ Campo end. absoluto é de 26 bits – j, jal
„ Como o campo de endereço é relativo a uma 
palavra, representa end. em bytes de 28bits, 
ou seja, 228= 256MB
„ Acima deste valor (32 bits) usar registrador –
jr $registrador
Exemplo:
Instrução original
beq $s0,$s1,L1
Instrução modificada
bne $s0,$s1,L2
J L1
L2:
7
OAC – Ling. de Máquina – Strings, Endereçamento - 13 Juliana F Camapum Wanderley
„ 4 passos: C → Linguagem de máquina.
Transformação C → Executável (1/8)
OAC – Ling. de Máquina – Strings, Endereçamento - 14 Juliana F Camapum Wanderley
Transformação C → Executável (2/8)
„ Compilador
„ Transforma C → Assembly
„ Linguagem de alto nível: maior produtividade.
„ Antigamente: escrito em Assembly. Presentemente: em ling. de 
alto nível.
„ Montador
„ Assembly → Ling. de máquina.
„ MIPS: O assembly “incrementa” artificialmente o set de instruções.
„ Pseudo-instruções:
„ Não existem na máquina.
„ O montador as cria.
„ Melhora os recursos do Assembly.
8
OAC – Ling. de Máquina – Strings, Endereçamento - 15 Juliana F Camapum Wanderley
Transformação C → Executável (3/8)
„ Pseudo-instruções
„ move $t0,$t1 # $t0 ← $t1
„ o montador transforma em: add $t0,$zero,$t1
„ blt (branch if less than).
„ o montador substitui esta pseudo-instrução automaticamente por uma 
combinação de slt/bne.
„ bgt, bge, ble
„ Montador do MIPS: converte um branch fora da faixa em um 
branch mais um jump. 
„ Permite carregar constantes de 32 bits em um registrador, usando 
combinação de instruções.
„ O MIPS utiliza o registrador $at para uso exclusivo do montador.
OAC – Ling. de Máquina – Strings, Endereçamento - 16 Juliana F Camapum Wanderley
Transformação C → Executável (4/8)
„ Montador
„ aceitam números em diferentes bases: decimal, binário, 
hexadecimal.
„ 0000 0000 1010 1111 1000 0000 0010 0000 = 00af 8020hexa
„ transforma o programa em linguagem de máquina em 
um arquivo objeto → combinação de:
„ instruções em linguagem de máquina;
„ dados; 
„ informações necessárias para carregar o programa 
adequadamente na memória. 
9
OAC – Ling. de Máquina – Strings, Endereçamento - 17 Juliana F Camapum Wanderley
Transformação C → Executável (5/8)
„ Para produzir a versão binária: 
„ É preciso saber os endereços dos labels (tabela de símbolos).
„ Arquivo objeto: deve conter...
„ Cabeçalho do arquivo objeto, com tamanho e posição.
„ O segmento de texto que contém o código em linguagemde 
máquina.
„ O segmento de dados, que contém os dados necessários.
„ Informação sobre relocação: como os endereços absolutos são 
redefinidos.
„ Tabela de símbolos: labels não-definidos, como referências 
externas.
„ Informações para análise de erros (debbuger). 
OAC – Ling. de Máquina – Strings, Endereçamento - 18 Juliana F Camapum Wanderley
Transformação C → Executável (6/8)
„ Ligador
„ Mudança em um programa, que é parte de um conjunto: tem 
que mudar todo o programa?
„ Não. Só uma parte é recompilada.
„ Cada programa já pode estar compilado (em ling. de máquina).
„ Um programa chamado ligador (linker) “monta” os programas 
como um único programa.
„ 3 passos:
„ Colocar os módulos de código e dados 
simbolicamente na memória
„ Determinar os endereços dos labels de dados e de 
instruções.
„ Resolver as referências externas e internas.
„ Usa, para tal, as informações do programa objeto.
10
OAC – Ling. de Máquina – Strings, Endereçamento - 19 Juliana F Camapum Wanderley
Transformação C → Executável (7/8)
„ MIPS: convenções para o linker alocar 
endereços para dados e programas:
„ O ligador “monta” o arquivo, colocando os 
endereços certos. Gera um arquivo 
executável.
„ Resolver o exemplo no livro: ligação de 
arquivos hipotéticos.
$gp – global pointer – aponta para o endereço 
1000 8000hexa – inst. lw e sw $t0,offset($gp) 
$gp+offset = [1000 0000 – 1000 7FFF]
se offset = [8000 – FFFF]
$gp+offset = [1000 8000 – 1000 FFFF]
se offset = [0000 – 7FFF]
OAC – Ling. de Máquina – Strings, Endereçamento - 20 Juliana F Camapum Wanderley
Exemplo: Ligação de Arquivos-Objeto
Tabela de Símbolos
…X
B
Xlw 0
jal 4
(X)0
……
Informação relocação
lw $a0,0($gp)0
jal 04
……
Segmento (dados)
Segmento (código)
Cabeçalho(arq. Obj)
Proced. ANome
…B
InstruçãoEndereço
20hexaTam(dados)
100hexaTam(cód)
Tabela de Símbolos
…Y
A
Ysw 0
Jal 4
(Y)0
……
Informação relocação
sw $a1,0($gp)0
jal 04
……
Segmento (dados)
Segmento (código)
Cabeçalho (arq. Obj)
Proced. BNome
…A
InstruçãoEndereço
30hexaTam(dados)
200hexaTam(cód)
……
(Y)
(X)
……
jal 0040 0000hexa
sw $a1, 8020hexa($gp)0040 0100hexa
0040 0104hexa
Segmento (dados)
……
1000 0020hexa
lw $a0, 8000hexa($gp)0040 0000hexa
jal 0040 0100hexa0040 0004hexa
……
1000 0000hexa
Segmento (código)
Cabeçalho (executável)
InstruçãoEndereço
50hexaTam(dados)
300hexaTam(cód)
11
OAC – Ling. de Máquina – Strings, Endereçamento - 21 Juliana F Camapum Wanderley
Transformação C → Executável (8/8)
„ Carregador (Loader)
„ Realiza o carregamento do programa na memória. 
No UNIX:
1. Leitura do cabeçalho.
2. Criação de espaço de cód. e dados.
3. Copiar instr. e dados para a memória.
4. Copiar os parâmetros p/ a pilha (quando houver).
5. Iniciar o SP.
6. Desviar para a rotina de inicialização
OAC – Ling. de Máquina – Strings, Endereçamento - 22 Juliana F Camapum Wanderley
Exemplo Para Juntar as Peças
„ O procedimento swap (folha).
„ Troca dois elementos consecutivos no array.
„ Na tradução:
1. Alocar registradores para as variáveis.
2. Produzir código para o procedimento.
3. Preservar os registradores nas chamadas.
12
OAC – Ling. de Máquina – Strings, Endereçamento - 23 Juliana F Camapum Wanderley
Tradução do procedimento swap
Swap:
add $t1, $a1, $a1 # $t1←2*k
add $t1, $t1, $t1 # $t1←4*k
add $t1, $a0, $t1 # base de v[k]
lw $t0, 0($t1) # $t0 ← v[k]
lw $t2, 4($t1) # $t2 ← v[k+1]
sw $t2, 0($t1) # v[k] ← $t2
sw $t0, 4($t1) # v[k+1] ← $t0
jr $ra # retorna
Swap(int v[ ], int k) {
int temp;
temp=v[k];
v[k]=v[k+1];
v[k+1]=temp; }
v : $a0, k: $a1, temp: $t0
OAC – Ling. de Máquina – Strings, Endereçamento - 24 Juliana F Camapum Wanderley
Procedimento sort (não-folha)
sort (int v[ ], int n) {
int i,j;
for (i=0; i < n; i = i+1)
for (j=i-1; j>=0 &&v[j]>v[j+1];j=j-1)
swap(v, j); }
v : $a0, n: $a1, i: $s0, j: $s1
# for externo → for (i=0; i < n; i = i+1)
move $s0, $zero # i=0
for1tst: slt $t0,$s0,$a1 # i<n?
beq $t0,$0,exit1 #não: vá para exit1 (sai)
# sim: executa segundo loop for (corpo do primeiro loop for)
addi $s0,$s0,1 # i → i+1
j for1tst # vá p/ for1tst
exit1:
13
OAC – Ling. de Máquina – Strings, Endereçamento - 25 Juliana F Camapum Wanderley
· # Segundo loop for→ for (j=i-1; j>=0 && v[j]>v[j+1] ;j= j-1) swap(v, j); 
addi $s1,$s0,-1 # j←i-1
for2tst: slti $t0,$s1,0 # j<0?
bne $t0,$zero,exit2 #sim (j<0 ): vá para exit2 (sai)
add $t1,$s1,$s1 #não (j≥0): $t1←2*j
add $t1,$t1,$t1 #$t1←4*j
add $t2,$a0,$t1 # end v[j]
lw $t3,0($t2) # $t3 ← v[j]
lw $t4,4($t2) # $t4 ←v[j+1]
slt $t0,$t4,$t3 # v[j]>v[j+1] ?deixa loop
beq $t0,$zero,exit2 #não: vá para exit2(sai)
# sim: executa swap (corpo do segundo loop for)
addi $s1,$s1,-1 # j ← j-1
j for2tst
exit2: 
v : $a0, n: $a1, i: $s0, j: $s1
OAC – Ling. de Máquina – Strings, Endereçamento - 26 Juliana F Camapum Wanderley
Passagem de parâmetros e chamada
„ A rotina sort e swap utilizam os mesmos parâmetros de 
passagem $a0 e $a1 → é preciso salvá-los antes de 
passá-los para swap.
„ Uma opção → salvar na pilha, e recuperar depois.
„ Outra opção → salvar em outros regs. (usaremos esta).
„ Salvando parâmetros de sort (v[ ],n) v : $a0, n: $a1
„ move $s2, $a0 # $s2 ← $a0
„ move $s3, $a1 # $s3 ← $a1
„ Passando parâmetros para rotina swap(v,j) v : $s2, j: $s1
„ move $a0, $s2 # $ a0← $ s2
„ move $a1, $s1 # $ a1← $ s1
„ jal swap
14
OAC – Ling. de Máquina – Strings, Endereçamento - 27 Juliana F Camapum Wanderley
Preservação dos Valores dos Registradores 
de sort
„ sort é chamada por outra subrotina.
„ Não deve destruir os registradores permanentes 
utilizados, $s0 a $s3.
„ Dever preservar o $ra.
„ Inicialização da rotina sort: salvar reg. na pilha
„ Antes de sair de sort: reverter estas seqüências.
addi $sp,$sp,-20
sw $ra,16($sp)
sw $s3,12($sp)
sw $s2,8($sp)
sw $s1,4($sp)
sw $s0,0($sp)
OAC – Ling. de Máquina – Strings, Endereçamento - 28 Juliana F Camapum Wanderley
Procedimento sort completo 
15
OAC – Ling. de Máquina – Strings, Endereçamento - 29 Juliana F Camapum Wanderley
Programa sort
„ C: 9 linhas.
„ Assembly: 35 linhas.
„ Outro método: “inlining”.
„ Vantagem: economiza 4 chamadas.
„ Desvantagem: caso seja utilizada por outras rotinas.
OAC – Ling. de Máquina – Strings, Endereçamento - 30 Juliana F Camapum Wanderley
Programa Clear usando Array e ponteiros.
„ Comparar duas implementações de uma rotina 
(para casa).