Centro de Estudos, Desenvolvimento e Inovação em Software | Universidade de Brasília

Geração de código final

FGA0003 - Compiladores 1 | Semana 10 | Aula teórica

Prof. Sergio Antônio Andrade de Freitas

Compiladores 1 - Engenharia de Software · 2025/2

CEDIS

2/30

Objetivos de aprendizagem

Definir a geração de código final e sua posição no back-end.
Relacionar RI, arquitetura-alvo e código produzido.
Traduzir TAC simples para uma máquina abstrata.
Explicar seleção de instruções, alocação de registradores e escalonamento.
Comparar assembly, objeto, executável e bytecode.

CEDIS

3/30

Roteiro da aula

01Revisão do pipeline
02Entradas e saídas da geração final
03Tradução de TAC para código-alvo
04Seleção de instruções
05Registradores, spilling e escalonamento
06Formatos de saída e síntese

CEDIS

4/30

Onde estamos no compilador?

A geração final consome a RI, já verificada e eventualmente otimizada, e produz código para um alvo.

A fase é parte do back-end.
As decisões passam a depender da máquina-alvo.
A correção semântica continua sendo obrigatória.
O código produzido pode não ser ainda o executável final.

Fluxo da RI ao executável — A cadeia completa pode envolver assembler, linker e loader.

seção

A pergunta central

Como uma operação abstrata da RI vira instruções de uma máquina concreta?

CEDIS

6/30

Três restrições permanentes

✓

Semântica

O código-alvo deve preservar o comportamento do programa.

⚙

Eficiência

Instruções, registradores e memória devem ser usados com critério.

🎯

Adaptação

O código precisa respeitar a arquitetura ou máquina virtual de destino.

CEDIS

7/30

atividade

Objetivos da geração final

Qual tarefa não pertence à geração de código final?

Preservar a semântica do programa.
Selecionar instruções da máquina-alvo.
Reconhecer lexemas e produzir tokens.
Utilizar registradores e memória.

Responder

Resumo ao vivo

CEDIS

8/30

Entradas e saídas

Entradas principais

RI otimizada ou não otimizada
Tabela de símbolos
Informações de tipos e escopos
Descrição da arquitetura-alvo

Saídas possíveis

Assembly
Arquivo objeto relocável
Código de máquina absoluto
Bytecode para máquina virtual

CEDIS

9/30

Cadeia de ferramentas após a geração final — Compilador, montador, ligador e carregador formam uma cadeia.

A cadeia depois do compilador

A geração de código final pode produzir um artefato que ainda será processado por outras ferramentas.

Assembly precisa ser montado.
Arquivos objeto precisam ser ligados.
O executável precisa ser carregado em memória.
Bytecode depende de uma máquina virtual.

CEDIS

10/30

Exemplo de RI para acompanhar a aula

Usaremos o mesmo TAC em várias decisões do gerador.

t1 = b * c
t2 = a + t1
x = t2

CEDIS

11/30

Tradução para máquina abstrata

Uma tradução possível carrega valores em registradores, executa operações e armazena o resultado.

R1 guarda o resultado de b * c.
R2 combina a com o valor de R1.
STORE grava o resultado final em x.
Outras sequências podem ser corretas, com custos diferentes.

TAC traduzido para instruções de registradores — Uma RI permite gerar códigos diferentes para alvos diferentes.

CEDIS

12/30

atividade

Tradução de TAC

Para t1 = a + b; x = t1, qual sequência é coerente?

LOAD R1,a; ADD R1,b; STORE x,R1
STORE a,R1; ADD x,b; LOAD t1,x
LOAD R1,x; ADD R1,t1; STORE b,R1
ADD a,b; LOAD x; STORE t1

Responder

Resumo ao vivo

seção

Três subtarefas centrais

Selecionar instruções, alocar registradores e escalonar instruções.

CEDIS

14/30

Subtarefas do gerador

Seleção de instruções

Mapeia operações da RI para instruções do alvo.

Alocação de registradores

Decide quais valores ficam em registradores ou na memória.

Escalonamento

Reordena instruções para reduzir esperas sem alterar dependências.

Endereçamento

Define como variáveis, temporários e estruturas são acessados.

CEDIS

15/30

Árvore de expressão e padrões de instrução — A melhor escolha depende do custo definido para o alvo.

Seleção de instruções

A seleção tenta cobrir a representação intermediária com padrões de instruções disponíveis.

Um mesmo trecho da RI pode ter várias traduções.
Maximal munch escolhe padrões grandes de modo guloso.
Programação dinâmica busca menor custo combinado.
Gramáticas de árvore formalizam padrões de tradução.

CEDIS

16/30

Exemplo de escolhas possíveis

RI

x = y + 1

Pode virar soma genérica.
Pode virar incremento se x e y forem o mesmo local.
Pode exigir LOAD e STORE se os valores estiverem na memória.

Decisão do gerador

Escolher a sequência correta e barata para o alvo.

Verificar instruções disponíveis.
Considerar registradores livres.
Respeitar efeitos colaterais e endereçamento.

CEDIS

17/30

Alocação de registradores

Registradores são rápidos, mas escassos. A alocação decide quais valores permanecem neles.

Valores vivos ao mesmo tempo interferem.
Cores representam registradores físicos.
Sem cores suficientes, ocorre spilling.
Spilling adiciona acessos à memória.

Grafo de interferência com cores e spilling — Arestas indicam impossibilidade de compartilhar registrador.

CEDIS

18/30

atividade

Grafo de interferência

O que indica uma aresta em um grafo de interferência?

As variáveis devem ocupar o mesmo registrador.
As variáveis estão vivas simultaneamente e não podem compartilhar registrador.
As variáveis possuem obrigatoriamente o mesmo tipo.
Uma variável depende sintaticamente da declaração da outra.

Responder

Resumo ao vivo

CEDIS

19/30

Spilling: quando falta registrador

Problema

Há mais valores vivos que registradores disponíveis.

Solução

Mover temporariamente algum valor para a memória.

Custo

Gerar instruções extras de LOAD e STORE.

Heurística

Derramar valores menos usados ou de menor impacto.

CEDIS

20/30

Comparação de instruções antes e depois do escalonamento — A reordenação só é válida quando respeita dependências.

Escalonamento de instruções

A ordem das instruções pode ser modificada para reduzir latências e aproveitar paralelismo.

Dependências verdadeiras não podem ser violadas.
Instruções independentes podem preencher esperas.
O objetivo é manter o pipeline mais ocupado.
A semântica observável precisa ser preservada.

CEDIS

21/30

atividade

Escalonamento e dependências

Qual condição deve ser preservada ao reordenar instruções?

A ordem textual original, sem exceção.
As dependências de dados e o comportamento do programa.
O nome das temporárias da RI.
A quantidade original de acessos à memória.

Responder

Resumo ao vivo

CEDIS

22/30

Arquitetura-alvo importa

RISC

Instruções simples e regulares.
Modelo frequentemente load-store.
Mais trabalho explícito para o compilador.
Exemplos: ARM, MIPS, RISC-V.

CISC

Instruções mais expressivas.
Modos de endereçamento mais variados.
Mais alternativas para seleção de instruções.
Exemplos: x86, VAX.

CEDIS

23/30

Formato de saída e implicações

Assembly

Legível por humanos, mas dependente da arquitetura.

Objeto relocável

Permite compilação separada e ligação posterior.

Máquina absoluto

Executável em contexto fixo, com baixa portabilidade.

Bytecode

Portável para ambientes com máquina virtual compatível.

CEDIS

24/30

atividade

Formatos de saída

Qual formato é projetado para execução por uma máquina virtual em diferentes plataformas?

Código de máquina absoluto.
Arquivo objeto específico de uma arquitetura.
Bytecode.
Microcódigo interno do processador.

Responder

Resumo ao vivo

CEDIS

25/30

Máquinas virtuais e bytecode

Bytecode desloca parte da geração final para o ambiente de execução.

O compilador gera uma forma portável.
A VM interpreta, compila JIT ou executa AOT.
Segurança e verificação podem ocorrer na VM.
Desempenho depende do ambiente e do aquecimento.

Fluxo com bytecode e VM — Bytecode favorece portabilidade, mas exige infraestrutura de execução.

seção

Modelo mental da geração final

Escolher instruções, administrar registradores e organizar o código sem mudar o programa.

CEDIS

27/30

Síntese do fluxo

1

RI otimizada

Entrada principal do gerador.

2

Seleção de instruções

Mapeia operações para o alvo.

3

Alocação de registradores

Decide onde valores ficam.

4

Escalonamento

Reordena respeitando dependências.

5

Saída

Assembly, objeto, executável ou bytecode.

CEDIS

28/30

Conexão com a prática

Usar uma máquina abstrata simplificada.
Mapear expressões para instruções de pilha ou registradores.
Comparar a saída gerada com o TAC original.
Criar testes para preservar equivalência semântica.
Documentar decisões de tradução no projeto da equipe.

CEDIS

29/30

Referências

Aho, A. V., Lam, M. S., Sethi, R., & Ullman, J. D. (2007). Compilers: Principles, techniques, and tools (2nd ed.). Pearson.
Appel, A. W. (2002). Modern compiler implementation in Java (2nd ed.). Cambridge University Press.
Cooper, K. D., & Torczon, L. (2012). Engineering a compiler (2nd ed.). Morgan Kaufmann.
Tremblay, J. P., & Sorenson, P. G. (2008). Theory and practice of compiler writing. BS Publications.
Wirth, N. (2005). Compiler construction. ETH Zürich.

CEDIS

30/30

Encerramento

Próximo passo: prototipar a geração de código final no projeto da equipe.