INTRODUÇÃO À COMPILAÇÃO
Geração de código
Ivan Ricarte
2008
INTRODUÇÃO À COMPILAÇÃO
Sumário
Geração de código intermediárioCódigo de três endereçosNotação pós-fixa
Otimização de códigoHeurísticas de otimização
Geração de código em linguagem simbólica
INTRODUÇÃO À COMPILAÇÃO
Estrutura geral do compiladorAtividades de síntese
Arquivo de
origem
GramáticasArquivo de
destino
análise
síntese
internas
Estruturas
geração de
código intermediário
geração de
código final
otimização
INTRODUÇÃO À COMPILAÇÃO
Produção de código
I Etapa de síntese da compilaçãoI Em geral, em duas fases
1. Tradução da estrutura construída na análise sintática paraum código em linguagem intermediária independente doprocessador
2. Tradução do código em linguagem intermediária para alinguagem simbólica do processador-alvo
I Produção do código binário é realizada por outroprograma do sistema (montador)
INTRODUÇÃO À COMPILAÇÃO
Geração de código intermediário
Com o reconhecimento da estrutura de expressões básicas nocódigo, é possível sintetizar expressões equivalentes nalinguagem em formato intermediário
I Pela varredura da árvore sintáticaI Durante o reconhecimento de expressões, na análise
sintáticaI Tradução dirigida pela sintaxe (ações semânticas)
Formatos usuais para a linguagem em formato intermediário:I Código de três endereçosI Notação posfixa
INTRODUÇÃO À COMPILAÇÃO
Código de três endereços
I Operações têm, no máximo, referências a três variáveis(dois operandos e um resultado)
I Expressões complexas devem ser decompostas em váriasexpressões nesse formato
I Formato independente de processador específicoI Fácil de traduzir para linguagem simbólica de qualquer
processador
INTRODUÇÃO À COMPILAÇÃO
Tipos de instruções
I Instruções de atribuiçãoI cópiaI resultado de operações bináriasI resultado de operações unárias
I Instruções de desvioI incondicionalI condicionalI invocação de rotinas
I Operadores de endereçamentoI indexadoI indireto
INTRODUÇÃO À COMPILAÇÃO
Código de três endereçosInstruções de atribuição
Atribuição simplesle := ld
ExemploCódigo C/C++:
x = a;
Tradução:
x := a
INTRODUÇÃO À COMPILAÇÃO
Código de três endereçosInstruções de atribuição
Operação binária com atribuiçãole := ld1 op ld2
ExemploCódigo C/C++:
x = a + b;
Tradução:
x := a + b
INTRODUÇÃO À COMPILAÇÃO
Código de três endereçosInstruções de atribuição
Operação unária com atribuiçãole := op ld
ExemploCódigo C/C++:
x = -a;
Tradução:
x := -a
INTRODUÇÃO À COMPILAÇÃO
Código de três endereçosInstruções de atribuição
Expressões mais complexas são traduzidas para uma série deexpressões nesse formato
I Variáveis temporárias são criadas para armazenarresultados intermediários, conforme necessário
ExemploExpressão C/C++:
a = b + c * d;
Tradução:
_t1 := c * da := b + _t1
INTRODUÇÃO À COMPILAÇÃO
Código de três endereçosInstruções de desvio
L é um rótulo de uma linha do código intermediário
Desvio incondicionalgoto L
Desvio condicionalif x opr y goto L
onde opr é um operador relacional
INTRODUÇÃO À COMPILAÇÃO
Código de três endereçosExemplo de tradução para instrução de desvio
C++
while (i++ <= k)x[i] = 0;
x[0] = 0;
Tradução
_L1: if i > k goto _L2i := i + 1x[i] := 0goto _L1
_L2: x[0] := 0
INTRODUÇÃO À COMPILAÇÃO
Código de três endereçosInvocação de subrotinas
Padrão de invocação:I Parâmetros da função, se presentes, são registrados com
instrução param
I Subrotina é invocada com instrução call, com indicaçãodo número de parâmetros
I Retorno, se presente, pode ser obtido a partir deatribuição do resultado de call
INTRODUÇÃO À COMPILAÇÃO
Código de três endereçosExemplo de tradução de invocação de subrotina
C++
x = f (a, g (b));
Tradução
param aparam b_t1 := call g, 1param _t1x := call f, 2
INTRODUÇÃO À COMPILAÇÃO
Código de três endereçosModos de endereçamento
Modo diretox := a
Modo indexadox := y[i]x[i] := y
com i em bytes!
Modo indiretox := &yw := *x
*x := z
INTRODUÇÃO À COMPILAÇÃO
Código de três endereçosEstruturas de representação interna
QuádruplasTabela com quatro colunas:
1. operador2. primeiro argumento3. segundo argumento4. resultado
INTRODUÇÃO À COMPILAÇÃO
Código de três endereçosEstruturas de representação interna
TriplasColuna com resultado é omitida
I Referência à linha da tabela é utilizada para indicarresultados intermediários
I Operador de atribuição simples deve ser utilizado paraexplicitar armazenamento de resultados não temporários
INTRODUÇÃO À COMPILAÇÃO
Estruturas de representação internaExemplo
C++a = b + c * d;
Quádruplaoperador arg 1 arg 2 resultado
1 * c d _t12 + b _t1 a
INTRODUÇÃO À COMPILAÇÃO
Estruturas de representação internaExemplo
C++a = b + c * d;
Triplaoperador arg 1 arg 2
1 * c d2 + b (1)3 := a (2)
INTRODUÇÃO À COMPILAÇÃO
Notação pós-fixa
I Alternativa para representação de expressõesI Operações são indicadas após operandosI Representação interna de cada expressão na forma de
uma listaI Não há necessidade de parênteses
INTRODUÇÃO À COMPILAÇÃO
Notação pós-fixa
C++a = b*(c+d)+e;
Árvore sintática abstrata:=
a +
*
b +
c d
e
Tradução (varredura pós-ordem)a b c d + * e + :=
INTRODUÇÃO À COMPILAÇÃO
Otimização de código
I Código gerado automaticamente pode ser ineficienteI RedundânciasI Instruções desnecessárias
I Ineficiência pode vir também da codificação originalI Heurísticas de otimização podem ser aplicadas no código
em formato intermediário antes da produção do código emlinguagem simbólica
INTRODUÇÃO À COMPILAÇÃO
Eliminação de subexpressões comuns
Operações que se repetem sem que seus argumentos sejamalterados podem ser realizadas uma única vez
ExemploSem atribuição a a ou b entre as duas instruções:
x = a + b + c;...y = a + b + d;
Sem otimização:
_t1 := a + bx := _t1 + c..._t2 := a + by := _t2 + d
Com otimização:
_t1 := a + bx := _t1 + c...y := _t1 + d
INTRODUÇÃO À COMPILAÇÃO
Eliminação de código redundante
Instruções sem efeito podem ser eliminadas
ExemploSem nenhuma atribuição a x ou a y entre as duas instruções,
x := y...x := y
x := y...y := x
a segunda instrução pode ser seguramente eliminada
INTRODUÇÃO À COMPILAÇÃO
Propagação de cópias
Variáveis que só mantêm cópia de um valor, sem outros usos,podem ser eliminadas
ExemploSem outras atribuições a y e sem outros usos de x
x := y...z := x
pode ser reduzido a
...z := y
INTRODUÇÃO À COMPILAÇÃO
Eliminação de desvios desnecessários
Desvio incondicional para a próxima instrução pode sereliminado
Exemploa := _t2goto _L6
_L6: c := a + b
equivale a
a := _t2c := a + b
INTRODUÇÃO À COMPILAÇÃO
Eliminação de código não-alcançável
Instruções que nunca serão executadas podem ser eliminadas
Exemplogoto _L3_t1 := x
_L4: _t2 := b + c_L3: d := a + _t2
equivale a
goto _L3_L4: _t2 := b + c_L3: d := a + _t2
INTRODUÇÃO À COMPILAÇÃO
Movimentação de código
Retirar do corpo de comandos iterativos (laços) cálculo deexpressões invariáveis
Exemplowhile ( i < 2*max )
a[i] = i + max/4;
Como valor de max não varia, equivale a
_t1 = 2*max;_t2 = max/4;while (i < _t1)
a[i] = i + _t2;
INTRODUÇÃO À COMPILAÇÃO
Uso de propriedades algébricas
Substituição de expressões aritméticas por formasequivalentes
Original Equivalentex + y y + xx + 0 xx - 0 xx * y y * xx * 1 xx / 1 x2 * x x + xx2 x * x
INTRODUÇÃO À COMPILAÇÃO
Limites e objetivos de otimizaçãoEm geral, usuário pode indicar ao compilador quanto deesforço deve ser dispendido em otimização
Compilador gcc/g++-O0 nenhuma otimização deve ser feita, compilação
fica mais rápida mas programa gerado é menoseficiente
I Mas pode ficar mais fácil de seguir execuçãonum processo de depuração, por estar maispróximo do código original
-O3 máxima otimização, programa gerado tem menortempo de execução mas tempo de compilação émais longo
-O1, -O2 graus de otimização intermediários-Os Se objetivo da otimização não for tempo de
execução, mas a minimização do espaço ocupadoem memória
INTRODUÇÃO À COMPILAÇÃO
Geração de código em linguagem simbólica
Objetivo Obter, a partir das instruções elementares usadasno código em formato intermediário, códigoequivalente na linguagem simbólica doprocessador-alvo
I Diferentes processadores podem ter distintos formatos deinstruções
I Classificação pelo número de endereços na instrução:3 dois operandos e o resultado2 dois operandos (resultado sobrescreve
primeiro operando)1 só segundo operando, primeiro operando
implícito (registrador acumulador), resultadosobrescreve primeiro operando
0 operandos e resultado numa pilha, semendereço explícitos
INTRODUÇÃO À COMPILAÇÃO
Tradução para linguagem simbólica
Tradução ocorre segundo gabaritos definidos de acordo com otipo de máquina
Exemplo: x := y + z
3-endADD y, z, x
2-endMOVE Ri, yADD Ri, zMOVE x, Ri
1-endLOAD yADD zSTORE x
0-endPUSH yPUSH zADDPOP x
INTRODUÇÃO À COMPILAÇÃO
Otimização no código em linguagem simbólica
Ao combinar seqüências de instruções traduzidas pelosgabaritos, estratégias de otimização podem ser tambémaplicadas ao código em linguagem simbólica
I Eliminação de código redundanteI Eliminação de instruções desnecessárias
Além disso, há uma oportunidade de realizar otimizações quesão específicas para um determinado processador
I Otimizações dependentes de máquinaI Permitem o aproveitamento de instruções pouco usuais,
de uso restritoI Muitas vezes, é difícil para o compilador reconhecer a
possibilidade de uso dessas instruções
INTRODUÇÃO À COMPILAÇÃO
Sugestões de leitura
Artigos na Wikipedia sobreI Geração de código: http://en.wikipedia.org/wiki/Code_generation_(compiler)
I Otimização de código: http://en.wikipedia.org/wiki/Optimization_(computer_science)