flowchart TD
E([entrada]) --> B0
B0["B0<br/>instrucoes 0 a 4<br/>primeira comparacao"]
B1["B1<br/>instrucoes 5 a 9<br/>segunda comparacao"]
B2["B2<br/>instrucoes 10 e 11<br/>emissao"]
B0 -->|condicao passou| B1
B0 -->|condicao falhou| F
B1 -->|condicao passou| B2
B1 -->|condicao falhou| F
B2 --> F
F([fim da regra])
1 Módulo 15: Otimização e Integração Final — Resumo
Esta é a versão de revisão do último módulo. Recapitulo em ritmo de véspera o que fecha o semestre; nada é demonstrado por inteiro — para isso existem a versão completa do material deste módulo e o livro. Use este texto para conferir se você identifica blocos básicos, monta o grafo de fluxo e enuncia a condição de segurança de cada transformação.
Começo pelo resultado que decepciona: o otimizador do nosso compilador, rodado sobre um programa típico da Peneira, remove zero instruções. Entram doze, saem doze. Ele não está quebrado — não acha nada porque não há nada: a representação intermediária sai da tradução apertada, com cada valor consumido logo depois de produzido. Publica-se o que a medição deu, e esse número desloca a pergunta certa. Se a otimização não se paga em desempenho aqui, por que ocupa um módulo inteiro? Porque ela não é sobre velocidade: é sobre transformar um programa preservando o seu significado.
1.1 A estrutura sobre a qual a otimização opera
Por que uma otimização precisa de estrutura? Para trocar a soma de dois literais pelo resultado, basta olhar a instrução. A estrutura entra assim que a transformação precisar saber algo que a instrução isolada não contém: apagar uma instrução cujo resultado ninguém lê exige olhar adiante, por todos os caminhos alcançáveis. Sem representar o fluxo de controle, a maioria das transformações não consegue nem enunciar a própria condição de aplicabilidade — e transformação sem condição enunciada é defeito esperando o programa que o revele.
São duas camadas. Embaixo, o bloco básico: uma subsequência contígua maximal de instruções em que o controle só entra pela primeira e só sai pela última. A palavra “maximal” carrega a definição inteira, porque qualquer instrução isolada já satisfaz as duas condições. A construção sai do algoritmo dos líderes: é líder a primeira instrução, toda alvo de desvio e toda que segue imediatamente um desvio. Essa terceira é a que se esquece. Em cima está o grafo de fluxo de controle, com aresta de um bloco a outro quando a última instrução do primeiro pode transferir o controle para a primeira do segundo — e os sucessores se calculam exclusivamente a partir dessa última instrução.
Duas verificações de sanidade saem de graça: a soma dos tamanhos dos blocos tem de bater com o número de instruções, e todo alvo de desvio precisa ser início de bloco. E não descarte as arestas que apontam para o fim da regra: o fim não é bloco, mas sem elas um desvio condicional apareceria com um único sucessor. O ganho do grafo não é decorativo — perguntas indecidíveis sobre o comportamento viram perguntas decidíveis sobre um objeto finito. O preço é precisão, porque nem todo caminho do grafo é execução real: a análise é conservadora e erra sempre para o mesmo lado.
Pare e pense. O que acontece com as transformações locais se você esquecer a terceira condição de líder? Todas elas assumem execução estritamente sequencial dentro do bloco.
1.2 Transformações locais, cada uma com a sua condição
Antes de qualquer transformação, a regra sob a qual todas operam. Dois programas são observacionalmente equivalentes quando, para toda entrada, produzem a mesma sequência de efeitos observáveis, idêntica em conteúdo e em ordem; uma transformação é segura quando o transformado é sempre equivalente ao original. Repare no que a definição ignora de propósito — tempo, memória, contagem de instruções — e no que ela observa: numa linguagem que emite resultados rotulados, trocar a ordem das emissões muda o que o usuário vê. Daí a formulação que quero que você adote: otimização é transformação com condição de aplicabilidade, e a condição é o que a separa de um defeito.
| Transformação | O que faz | Condição de segurança |
|---|---|---|
| Dobramento de constantes | calcula em compilação uma operação entre literais | operandos literais e operação pura, que não falha |
| Propagação de cópias | troca a leitura de um nome pela da origem | nenhum dos dois nomes redefinido entre cópia e uso |
| Subexpressões comuns | reusa resultado já computado | operandos não redefinidos, expressão pura, mesmo bloco |
| Código morto | remove instrução cujo resultado ninguém lê | resultado não vivo e sem efeito colateral |
No dobramento, a segunda metade da condição é a esquecida: a expressão que falha em execução não pode virar valor em compilação, porque falhar é um comportamento, não um acidente. A propagação de cópias, sozinha, não remove nada — só troca quem cada uso lê, e o ganho vem depois, quando a cópia fica sem leitor; no nosso compilador ela nem tem alvo, porque a tradução nunca emite cópia. Na eliminação de subexpressões, a exigência de mesmo bloco limita a versão local, e é ela que a global troca por “disponível em todos os caminhos”. Falta o código morto, onde mora o erro clássico da área: a instrução pode importar mesmo que o resultado dela não importe. A emissão é o caso exemplar, porque não define temporário algum; um verificador que pergunte só “o resultado é lido?” conclui que ela é morta e a remove, e o programa resultante passa em toda checagem estrutural sem produzir saída alguma.
Uma transformação correta pode ser inaplicável. A eliminação de subexpressões existe para que um resultado sirva a vários leitores. A nossa máquina de destino é de pilha, e ler um temporário nela é desempilhá-lo: o segundo leitor acharia a pilha vazia. Ela preserva a semântica e viola uma precondição do gerador. Critério correto: segura semanticamente e compatível com as fases posteriores.
Em que ordem aplicar as transformações, e quantas vezes? Uma passada de cada é insuficiente, porque elas se alimentam: dobrar uma comparação entre constantes deixa sem leitor as instruções que carregavam os operandos, e removê-las pode desligar as que as alimentavam. A solução é a que já apareceu duas vezes no curso — repetir até nada mais mudar —, e é o que o condutor da implementação de referência faz:
// A eliminação de subexpressões NÃO entra aqui, e o motivo está no
// cabeçalho: ela é correta e incompatível com o gerador de código desta
// máquina. Deixá-la de fora é decisão registrada, não esquecimento.
for (;;) {
++e.iteracoes;
const std::size_t antes = atual.instrucoes.size();
atual = dobrarConstantes(atual, e);
atual = eliminarCodigoMorto(atual, e, true);
if (atual.instrucoes.size() >= antes) {
break;
}
}flowchart TD
A[sequencia de instrucoes] --> B[dobramento de constantes]
B --> C[propagacao de copias]
C --> D[eliminacao de codigo morto]
D --> E{alguma coisa mudou<br/>nesta rodada?}
E -->|sim| B
E -->|nao| F[ponto fixo alcancado]
B -.->|deixa operandos<br/>sem leitor| D
D -.->|expoe novas<br/>constantes| B
A terminação é garantida porque cada passo ou remove uma instrução ou troca uma expressão por constante, e nenhuma das duas coisas acontece indefinidamente numa sequência finita. Guarde a armadilha: remover uma instrução renumera todas as seguintes, e se os desvios guardam índices absolutos, esquecer de corrigi-los produz um programa bem formado que salta para os lugares errados.
1.3 Análise de fluxo de dados: o panorama
Um nome está vivo em um ponto quando existe um caminho no grafo, começando ali, que o lê antes de redefini-lo. Repare na quantificação: basta um caminho — se em dez o valor é descartado e num só ele é lido, ele está vivo. Com \mathrm{usa}(i) o que a instrução lê e \mathrm{def}(i) o que ela define, as equações são
\mathrm{vivo_{ent}}(i) = \mathrm{usa}(i) \cup \bigl(\mathrm{vivo_{sai}}(i) \setminus \mathrm{def}(i)\bigr), \qquad \mathrm{vivo_{sai}}(i) = \bigcup_{s \in \mathrm{suc}(i)} \mathrm{vivo_{ent}}(s).
A vivacidade é caso particular de um esquema que se repete na área inteira: toda análise associa a cada ponto um elemento de um conjunto de valores possíveis, dá a cada instrução uma função de transferência e usa uma operação de encontro onde caminhos se juntam. Duas escolhas caracterizam cada uma: a direção, que diz se a informação flui a favor ou contra a execução, e o encontro, que codifica se a pergunta é sobre algum caminho (união) ou sobre todos (interseção).
flowchart LR
subgraph PT["analise para tras"]
direction TB
S1[saida da instrucao] --> T1[funcao de transferencia]
T1 --> E1[entrada da instrucao]
SU[sucessores] -.->|encontro| S1
end
subgraph PF["analise para a frente"]
direction TB
E2[entrada da instrucao] --> T2[funcao de transferencia]
T2 --> S2[saida da instrucao]
PR[predecessores] -.->|encontro| E2
end
PT --- V["vivacidade<br/>encontro por uniao<br/>basta um caminho"]
PF --- A["definicoes alcancaveis: uniao<br/>expressoes disponiveis: intersecao"]
| Análise | Direção e encontro | Para que serve |
|---|---|---|
| Vivacidade | para trás, união | eliminação de código morto e alocação de registradores |
| Definições alcançáveis | para a frente, união | propagação de cópias no caso geral |
| Expressões disponíveis | para a frente, interseção | versão global da eliminação de subexpressões |
Que iterar funcione não é óbvio, já que as equações são recursivas e o grafo pode ter ciclos. A garantia vem do teorema de Knaster e Tarski: função monótona sobre reticulado completo tem menor ponto fixo, e com altura finita a iteração a partir do menor elemento estabiliza nele em número finito de passos — aqui o reticulado é o conjunto das partes dos nomes do programa e a altura é o número de nomes. Recomendação que economiza horas: conte as rodadas, porque análise que não converge tem defeito na função de transferência. Com as análises prontas abre-se a família global — subexpressões, código invariante de laço, propagação de constantes, código morto —, e o que importa não é a lista: todas têm a mesma forma, uma análise que estabelece um fato sobre todos os caminhos seguida de uma transformação cuja condição de segurança é esse fato.
Pare e pense. Esta é a terceira vez no semestre que um conjunto se define em função de si mesmo e a solução sai por iteração. Você consegue nomear as duas primeiras?
1.4 Quanto otimizar: a conta entre compilar e executar
flowchart TD
Q{quantas execucoes<br/>por compilacao?} -->|muitas| M[compilar uma vez<br/>executar milhoes de vezes]
Q -->|poucas| P[recompilar a cada alteracao<br/>executar meia duzia de vezes]
M --> MA[vale pagar analise cara<br/>nivel alto de otimizacao]
P --> PA[compilacao rapida<br/>codigo depuravel]
MA --> C1[custo pago uma vez<br/>por compilacao]
PA --> C1
C1 --> G[ganho colhido uma vez<br/>por execucao]
O custo é pago uma vez por compilação, o ganho é colhido uma vez por execução, e a razão entre esses números varia por ordens de grandeza: programa executado milhões de vezes justifica minutos de compilação; programa recompilado a cada alteração, quase nada. É por isso que compiladores de produção oferecem níveis em vez de um comportamento único — a escolha não é técnica, é de contexto de uso. Há um segundo custo que não é de tempo: código otimizado é mais difícil de relacionar ao escrito, e daí o modo de desenvolvimento com otimização desligada. E há um terceiro, o problema da ordem das fases — aplicar uma transformação antes de outra pode habilitá-la e, na ordem inversa, destruir a oportunidade; a sequência dos compiladores reais é calibragem empírica. Fecho com o conselho metodológico do módulo: ao avaliar uma otimização, resista a escolher o exemplo. Zero é um resultado publicável.
1.5 Integração final: do texto ao efeito observável
flowchart TD
T[texto do programa] --> L[analise lexica<br/>caracteres para tokens]
L --> S[analise sintatica<br/>tokens para arvore]
S --> M[analise semantica<br/>arvore anotada e tabela de simbolos]
M --> R[traducao<br/>instrucoes de tres enderecos]
R --> O[otimizacao<br/>instrucoes equivalentes]
O --> G[geracao de codigo<br/>programa objeto]
G --> V{validacao estatica<br/>do objeto}
V -->|reprovado| X[erro: o objeto nao e gravado]
V -->|aprovado| A[objeto gravado]
A --> X2[execucao sobre a entrada]
X2 --> EF[efeitos observaveis]
D[coleta de diagnosticos] -.- L
D -.- S
D -.- M
D -.- G
Duas caixas não existiam no mapa do primeiro módulo: a otimização e a validação. O executor de antes detectava objeto malformado em execução, o que basta para não produzir resultado errado e é insuficiente — um objeto quebrado num caminho raro passa por bom até a entrada certa aparecer. A integração faz as mesmas checagens estaticamente: índices na faixa, destinos de desvio válidos, toda regra alcançando um fim e o balanço da pilha consistente — esta última simulando apenas a altura, sem valores e sem executar nada.
A altura da pilha precisa ser propriedade do ponto, não do caminho. Se dois caminhos chegam à mesma instrução com alturas diferentes, o objeto é malformado — mesmo que nenhuma entrada exercite os dois. É verificável estaticamente e mais forte que qualquer bateria de testes. Termina porque todo desvio nosso salta para a frente e o fluxo é acíclico; com laços, exigiria o ponto fixo da seção anterior.
Um sistema exercitado só sobre os exemplos que o autor preparou não foi exercitado. O corpus precisa das entradas degeneradas — a vazia, a que não casa com padrão algum, a só de separadores —, dos casos de fronteira das condições e dos dois lados de cada desvio. O tratamento de erro, apresentado no primeiro módulo como serviço transversal, volta agora como atributo de projeto: a posição, que nasce no analisador léxico e sobrevive a todas as fases; a causa provável, que separa diagnóstico de relato; a sugestão de correção, útil quando ela é única; a recuperação, com o risco da cascata; e a consistência de formato entre as fases. E como saber que a otimização preservou a semântica? Não por argumento, que estabelece a segurança se a implementação estiver correta — e é ela que se quer verificar. O método é o confronto: compilar com e sem otimização, executar os dois objetos sobre o mesmo corpus e exigir efeitos idênticos em rótulo, valor e posição. Isso é evidência, não prova.
1.6 O caso conduzido e o que o seu grupo entrega
Sobre a condição composta da Peneira, o cálculo devolve três blocos com a estrutura exata do curto-circuito, e a vivacidade estabiliza em duas rodadas — uma que calcula e outra que confirma que nada mudou. O grafo não foi desenhado, foi calculado. No programa artificial que escrevi para exercitar as transformações, e rotulei como artificial, a representação vai de seis para quatro instruções, com um dobramento, duas mortas e duas iterações; e o destino de um desvio muda de seis para quatro — a renumeração em ação. Quem acusou a incompatibilidade das subexpressões comuns com a máquina de pilha foi a verificação de uso único escrita um módulo antes, quando o otimizador nem existia. A sua entrega é a mesma disciplina em escala menor: blocos e grafo de fluxo sobre a sua representação intermediária, duas transformações locais com a preservação demonstrada, o executor completo sobre entrada real com todo o tratamento de erro, documentação revisada e apresentação preparada.
1.7 Síntese
flowchart LR
RE[expressao regular] --> AFN[automato nao determinista<br/>construcao de Thompson]
AFN --> AFD[automato determinista<br/>determinizado e minimizado]
AFD --> LEX[analisador lexico]
AFD --> OBJ[tabelas de transicao<br/>no programa objeto]
LEX --> PAR[analisador sintatico<br/>descida recursiva]
PAR --> SEM[analise semantica<br/>simbolos e tipos]
SEM --> RI[representacao intermediaria<br/>tres enderecos]
RI --> OTI[otimizacao local]
OTI --> COD[geracao para maquina de pilha]
COD --> OBJ
OBJ --> VM[execucao sobre entrada real]
Volte ao otimizador que não removeu nada. Ele mostrou que a otimização opera sobre blocos e grafo de fluxo, e que essa construção troca perguntas indecidíveis sobre execuções por perguntas decidíveis sobre um grafo finito. Cada transformação veio com a sua condição, e dois resultados ficam: uma transformação semanticamente correta pode ser inaplicável quando viola precondição de fase posterior, e a preservação se estabelece por confronto de execuções, que dá evidência e não prova. Prefiro delimitar as ausências: a otimização global ficou no panorama e laços não apareceram, porque a nossa linguagem não tem laços. O que fica do semestre é que as peças teóricas não foram consumidas pelo compilador, ficaram no produto — o autômato mínimo que construímos como exercício de teoria está gravado, como tabela de transição, no arquivo objeto. Se você reconhece o mesmo módulo de autômatos trabalhando nas duas pontas, a aposta do curso se pagou.