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

Otimização de código

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

Prof. Sergio Antônio Andrade de Freitas

Compiladores 1 - Engenharia de Software · 2025/2

CEDIS

2/27

Objetivos de aprendizagem

Definir otimização de código e seus objetivos.
Relacionar otimização com o pipeline do compilador.
Comparar otimizações manuais, automáticas, independentes e dependentes de máquina.
Aplicar a regra as-if em exemplos simples.
Identificar técnicas como folding, DCE, strength reduction e CSE.

CEDIS

3/27

Roteiro da aula

01Revisão do pipeline e da RI
02Conceito de otimização e regra as-if
03Níveis e tipos de otimização
04Técnicas clássicas sobre código intermediário
05Laços, caching, memoization e flags
06Síntese para o projeto da disciplina

CEDIS

4/27

Depois do TAC, por que otimizar?

O código intermediário torna o programa mais fácil de transformar, comparar e testar.

TAC explicita dependências e resultados temporários.
A AST anotada preserva informações semânticas úteis.
A otimização atua sobre formas mais regulares que o código-fonte.
O objetivo não é mudar o programa, mas reduzir custo.

Pipeline do compilador com pontos de otimização — A RI é o ponto típico para otimizações independentes de máquina.

seção

Otimizar não é alterar o programa

A transformação só é válida quando preserva o comportamento observável.

CEDIS

6/27

O que a otimização tenta melhorar

⏱

Tempo

Reduzir operações, desvios e acessos custosos.

💾

Memória

Diminuir uso de temporários, pilha, heap e caches.

📦

Tamanho

Gerar código menor quando espaço é restrição.

⚡

Energia

Evitar trabalho desnecessário, especialmente em dispositivos restritos.

CEDIS

7/27

atividade

Verificação rápida

Uma otimização de compilador é válida quando:

preserva o comportamento observável do programa.
reduz linhas de código, mesmo alterando a saída.
remove todas as instruções consideradas lentas.
substitui qualquer expressão por uma constante.

Responder

Resumo ao vivo

CEDIS

8/27

Pipeline mostrando otimização na fonte, RI e alvo — O local da otimização influencia quais informações estão disponíveis.

Onde a otimização pode ocorrer

Otimizações podem atuar em diferentes representações do programa.

No código-fonte ou AST: transformações de alto nível.
Na RI: folding, propagação, DCE e CSE.
No código final: peephole, registradores e instruções específicas.
Em JIT: durante a execução, com perfil real.

CEDIS

9/27

atividade

Fases de otimização

Em que fases a otimização pode ocorrer em um compilador?

No código intermediário, no código-alvo e até no código-fonte.
Apenas na análise léxica.
Apenas na geração de código final.
Apenas depois que o executável já está pronto.

Responder

Resumo ao vivo

CEDIS

10/27

Classificações úteis

Quem otimiza?

Manual: depende do programador.
Automática: feita pelo compilador.
Guiada por perfil: usa medições reais.

De que depende?

Independente de máquina: atua na RI.
Dependente de máquina: explora a arquitetura.
Alto nível ou baixo nível, conforme a representação.

CEDIS

11/27

atividade

Dependência da arquitetura

Qual exemplo descreve uma otimização de baixo nível e dependente de máquina?

Escolher uma instrução específica para um processador particular.
Trocar uma lista por uma tabela hash no código-fonte.
Renomear variáveis para melhorar legibilidade.
Remover comentários do programa-fonte.

Responder

Resumo ao vivo

CEDIS

12/27

Regra as-if

O compilador pode transformar o programa como se nada tivesse mudado para o observador externo.

Saídas devem permanecer equivalentes.
Efeitos colaterais observáveis não podem ser removidos indevidamente.
A validade depende da semântica da linguagem.
Otimizações agressivas exigem mais cuidado.

Comparação antes e depois da regra as-if — Código sem efeito observável pode ser eliminado.

CEDIS

13/27

atividade

Aplicando a regra as-if

O compilador pode eliminar uma instrução quando:

ela não afeta o comportamento observável do programa.
ela aparece dentro de qualquer laço.
ela usa multiplicação, pois multiplicar é sempre caro.
ela foi escrita manualmente pelo programador.

Responder

Resumo ao vivo

CEDIS

14/27

Mapa de técnicas de otimização — Cada técnica procura um padrão específico de redundância ou custo.

Técnicas clássicas sobre a RI

Muitas otimizações introdutórias podem ser entendidas como padrões locais em TAC ou SSA.

Constant folding: avalia constantes em tempo de compilação.
Constant propagation: substitui usos por valores conhecidos.
DCE: remove código que não contribui para o resultado.
CSE: evita recomputar expressões idênticas.

CEDIS

15/27

Constant folding e propagation

Antes

x = 2 + 3 * 4
a = 10
y = a + 2

Depois

x = 14
a = 10
y = 12

CEDIS

16/27

Código morto e código inalcançável

Dead code

A instrução executa, mas seu resultado não é usado.
Exemplo: atribuição sobrescrita antes de qualquer leitura.
Depende de análise de uso e definição.

Unreachable code

O trecho nunca pode ser executado.
Exemplo: bloco após return incondicional.
Depende do fluxo de controle.

CEDIS

17/27

Três padrões frequentes

Strength reduction

Trocar operação custosa por equivalente mais barata, como multiplicação por soma incremental.

Copy propagation

Substituir o uso de uma cópia pelo valor original, quando seguro.

CSE

Calcular uma expressão repetida uma vez e reutilizar o resultado.

CEDIS

18/27

atividade

Reconhecimento de técnica

Em x = a + b; y = a + b;, qual técnica evita recomputar a mesma expressão?

Eliminação de subexpressões comuns.
Loop unrolling.
Análise léxica.
Alocação de registradores.

Responder

Resumo ao vivo

CEDIS

19/27

Otimizações de laço

Laços concentram custo porque repetem operações muitas vezes.

Loop-invariant code motion move cálculos estáveis para fora do laço.
Loop unrolling reduz overhead de controle e expõe paralelismo.
Fusion melhora localidade quando laços percorrem os mesmos dados.
Fission pode facilitar paralelização ou reduzir pressão por registradores.

Exemplos de otimizações de laço — O ganho depende das dependências e da arquitetura.

CEDIS

20/27

Caching e memoization

Caching

Reutiliza dados já obtidos ou computados.
Pode ocorrer em software ou hardware.
Nem sempre depende de funções puras.

Memoization

Armazena resultados de chamadas de função.
Funciona melhor com funções puras.
Evita recomputação de entradas repetidas.

CEDIS

21/27

Comparação dos níveis de otimização — Níveis mais altos não significam melhor resultado em todos os programas.

Flags de otimização

Compiladores reais oferecem níveis que equilibram desempenho, tamanho e depuração.

-O0: favorece depuração e previsibilidade.
-O1 e -O2: aplicam otimizações comuns com custo moderado.
-O3: pode aumentar código e tempo de compilação.
-Ofast: pode relaxar garantias numéricas e padrões.

CEDIS

22/27

A otimização prematura é a raiz de muitos problemas de engenharia.

Síntese inspirada na advertência clássica de Donald Knuth

CEDIS

23/27

Como aplicar no projeto da disciplina

Escolha uma RI

Use TAC ou estrutura equivalente que possa ser impressa e testada.

Defina um padrão

Exemplo: t1 = 2 + 3 vira t1 = 5.

Implemente um passe

Percorra a lista de instruções e gere uma versão otimizada.

Teste antes e depois

Mostre equivalência e redução de custo quando possível.

CEDIS

24/27

Roteiro mínimo de uma otimização didática

1

Detectar

Reconhecer o padrão na RI ou no TAC.

2

Verificar

Confirmar que a transformação preserva a semântica.

3

Transformar

Produzir instruções equivalentes e mais simples.

4

Validar

Comparar saídas e registrar casos de teste.

CEDIS

25/27

Síntese

Otimizar é reduzir custo preservando comportamento observável.
A RI facilita transformações independentes de máquina.
Técnicas clássicas removem redundância, código inútil e recomputação.
Laços exigem atenção por concentrar custo e dependências.
No projeto, priorize corretude, testes e uma otimização pequena bem demonstrada.

CEDIS

26/27

Referências

Aho, A. V., Lam, M. S., Sethi, R., & Ullman, J. D. (2007). Compilers: Principles, Techniques, and Tools (2nd ed.). Addison-Wesley.
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 Zurich.

CEDIS

27/27

Encerramento

Na próxima prática: aplicar otimizações simples e testar o impacto sobre o código intermediário.