Geração de Código
• Fase final do compilador
• Transforma o código da representação
intermediária no código final
• Independente de otimizações
• Código deve estar correto e ser de alta
qualidade, fazendo uso eficiente dos
recursos da máquina-destino.
Geração de Código
front-end
otimizador de
código
tabela de
símbolos
gerador
de código
Geração de código
• geração de código ótimo é um problema
indecidível.
• Usa-se hurísticas para gerar código bom,
mas não ótimo.
• Qualidade do gerador de código afeta
significativamente a performance de um
programa.
Geração de código – aspectos
relevantes
• entrada para o gerador de código – sem
erros, na notação intermediária
• Programas gerados: código objeto
relocável/não relocável, assembler, C.
• Gerenciamento de memória
• Seleção de instruções – uniformidade de
instruções, completude, velocidade,
tamanho
Seleção de instruções - exemplo
• para este tipo de instrução:
x := y + z
• usar este template:
MOV y, R0
ADD z, R0
MOV R0,x
Seleção de instruções – exemplo
(cont.)
• compilar:
a := b + c
d := a + e
• MOV b, R0
ADD c, R0
MOV R0,a
MOV a,R0
ADD e,R0
MOV R0,d
Geração de código – aspectos
relevantes (cont.)
• Alocação de registradores – problema NPcompleto.
• Escolha da ordem de avaliação – problema
NP-completo
• Técnicas de geração de código.
Conjunto de instruções da
máquina-destino
• n registradores R0, R1, …, Rn-1
• instruções do tipo
op source, destination
por exemplo MOV, ADD, SUB
• modos de endereçamento: absoluto,
registrador, indexado, indeireto por
registrador, indireto indexado
Modos de endereçamento
Modo
Forma
Endereço
Custo
absoluto
M
M
1
registrador
R
R
0
indexado
c(R)
c + contents(R)
1
registrador
indexado
indireto
indexado
literal
*R
contents(R)
0
*c(R)
contents(c +
contents(R))
c
1
#c
1
Modos de endereçamento exemplos
• MOV R0, M
• MOV 4(R0),M
contents(4 + contents(R0))
• MOV *4(R0),M
contents(contents(4 + contents(R0)))
• MOV #1,R0
• SUB 4(R0), *12(R1)
contents(contents(12 + contents(R1))) –
contents(contents(4 + R0))
Custo de instruções
• 1 + custo do modo de endereçamento do
operando de origem + custo do modo de
endereçamento do operando de destino
• Comprimento da instrução.
Custo de instruções - exemplo
• a := b + c
• MOV b,R0
ADD c,R0
MOV R0,a
• MOV b,a
ADD c,a
• se R0, R1 e R2 contém o endereço de a, b e c:
MOV *R1, *R0
ADD *R2, *R0
Gerenciamento do ambiente de
tempo de execução
/* código de c */
action1
call p
action2
halt
/* código de p */
action3
return
Registro de ativação
de c (64 bytes)
Registro de ativação
de p (88 bytes)
0:
return address
0:
return address
8:
arr
4:
buf
56:
i
84:
n
60:
j
Grafo de Fluxo
• um grafo representando comandos de três
endereços é chamado de grafo de fluxo (flow
graph) é usado para entender algorítmos de
geração de código, mesmo que não seja
efetivamente construido.
• Nós representam computações, e arestas
representam o fluxo de controle.
Blocos Básicos
• Sequência de comandos consecutivos em que o
fluxo de controle entra no início e sai no final,
sem possibilidade de desvio exceto no final.
• x := y + z
define x e usa (ou referencia) y e z
• um nome em um bloco básico está vivo em um
determinado ponto, se ele é usado depois
daquele ponto do programa, possivelmente em
outro bloco básico.
Blocos Básicos - exemplo
• begin
prod := 0;
i := 1;
do begin
prod := prod + a[i] * b[i];
I := i + 1;
end
while i <= 20
end
Blocos Básicos - exemplo
• (1) prod := 0
(2) i := 1
(3) t1 := 4 * i
(4) t2 := a [t1]
(5) t3 := 4 * i
(6) t4 := b [t3]
(7) t5 := t2 * t4
(8) t6 := prod + t5
(9) prod := t6
(10) t7 := i + 1
(11) i := t7
(12) if i <= 20 goto (3)
Transformações em blocos
básicos
• transformações têm que preservar a semântica
do bloco básico: os blocos antes e depois da
transformação tem que ser equivalentes, i.e.
computar o mesmo conjunto de expressões para
os nomes vivos na saída do bloco.
• Transformações locais x transformações globais
Transformações locais
• transformações que preservam a estrutura:
–
–
–
–
eliminação de subexpressão comum
eliminação de código morto
renomeação de variáveis temporárias
troca de dois comandos adjacentes independentes
• transformações algébricas
– x := x + 0
– x := x * 1
– de x := y ** 2 para x := y * y
Eliminação de subexpressão
comum
• a := b + c
b := a – d
c := b + c
d := a – d
• a := b + c
b := a – d
c := b + c
d := b
Eliminação de código morto
• suponha que a variável x está morta no
ponto em que ocorre a atribuição
x := y + z
Este comando pode ser removido sem
mudar o resultado do bloco básico.
Renomeação de variáveis
• se temos o comando
t := b + c
onde t é uma variável temporária, podemos
substitui-lo por
u := b + c
onde u é uma nova variável temporária, e substituir
todas as referências a t por referências a u.
Troca de comandos
• t1 := b + c
t2 := x + y
• t2 := x + y
t1 := b + c
Grafo de Fluxo
prod := 0
i := 1
t1 := 4 * i
t2 := a [t1]
t3 := 4 * i
t4 := b [t3]
t5 := t2 * t4
t6 := prod + t5
prod := t6
t7 := i + 1
i := t7
if i <= 20 goto B2
B1
B2
Informações sobre próximo uso
• Coleta informações para cada variável em um
bloco básico:
– se ela está viva ao final do bloco
– onde ela é usada (onde é seu próximo uso) dentro do
bloco.
• Permite reuso de variáveis temporárias, e
facilita geração de código.