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
Chegamos ao último módulo. Aqui não entra modelo formal novo: tudo o que fazemos é operar sobre o que já está construído. Ao fim desta leitura você deve saber identificar blocos básicos, montar o grafo de fluxo, enunciar a condição de segurança de cada transformação local e verificar que a otimização não estragou nada.
1.1 O problema: o otimizador que não remove nada
Vou abrir com um resultado que costuma decepcionar. O otimizador deste módulo, rodado sobre um programa típico da nossa linguagem, remove zero instruções: entram doze, saem doze, e o relatório registra zero dobramentos e zero remoções.
Se a sua primeira reação foi desconfiar do otimizador, o instinto é o certo — e desta vez está errado. Ele funciona. Não acha nada porque não há nada: a representação intermediária que a tradução produz já sai apertada, cada valor é consumido logo depois de ser produzido, não sobra redundância.
Registro esse número na abertura por dois motivos. O primeiro é hábito de trabalho: publica-se o resultado que a medição deu, não o que a narrativa pedia. O segundo é que a decepção desloca a pergunta certa. Se a otimização não se paga por desempenho aqui, por que ela ocupa um módulo inteiro? Porque este módulo não é, no fundo, sobre desempenho. Ele é sobre transformar um programa preservando o seu significado — o problema mais delicado de toda a construção de compiladores — e sobre a estrutura que torna essa transformação possível de raciocinar. E antecipo um segundo resultado: uma das transformações clássicas que vamos estudar é semanticamente correta e, mesmo assim, não pode ser aplicada ao nosso compilador, porque viola uma precondição da máquina de destino.
Este é o último capítulo, e ele é o único que não introduz nenhum modelo formal novo. Tudo o que ele faz é operar sobre o que já está construído, e por isso vale enunciar com precisão o que estou pressupondo pronto — se alguma dessas peças estiver frouxa na sua cabeça, o capítulo vai parecer uma coleção de truques em vez de um fecho.
Pressuponho a representação intermediária de três endereços apresentada no capítulo sobre representações intermediárias: uma sequência linear de instruções, com temporários nomeados, desvios explícitos para índices dessa sequência e a propriedade de que cada temporário é atribuído uma única vez. Essa última propriedade não é decorativa; ela é o que dispensa metade das verificações que uma otimização precisaria fazer, e vou apoiar-me nela sem cerimônia.
Pressuponho a geração de código para máquina de pilha do capítulo anterior, e em particular a invariante que ela exige: cada temporário é lido exatamente uma vez, porque ler é desempilhar. Vou mostrar adiante uma transformação impecável do ponto de vista semântico que quebra precisamente essa invariante, e a demonstração só funciona para quem lembra por que a invariante existe.
Pressuponho o cálculo por ponto fixo, que já apareceu duas vezes no livro — nos conjuntos de símbolos anuláveis e produtivos de uma gramática, e nos conjuntos de primeiros e seguidores. É a terceira aparição do mesmo padrão, e a repetição é deliberada: quando a definição de um conjunto se refere a si mesma, calcula-se iterando até estabilizar. Se você reconhecer a forma, a análise de fluxo de dados deste capítulo custará muito pouco.
E pressuponho o motor de autômatos dos primeiros capítulos, porque a integração final o coloca de volta em cena: o mesmo autômato determinístico minimizado que reconhece os símbolos da linguagem é o que, gravado no programa objeto, varre a entrada em tempo de execução. O fecho conceitual do livro depende de você enxergar essa peça nos dois lugares.
1.2 A estrutura sobre a qual a otimização opera
Comece pela pergunta que parece ingênua e não é: por que uma otimização precisa de estrutura alguma? Se eu quero trocar a soma de dois literais pelo resultado, basta olhar a instrução e trocar. Onde entram blocos e grafos?
Entram assim que a transformação precisar saber algo que a instrução isolada não contém. Pense na mais simples das remoções: apagar uma instrução cujo resultado ninguém usa. Para saber que ninguém usa, é preciso olhar adiante — não só a instrução seguinte, mas todas as alcançáveis dali, por todos os caminhos. “Este resultado será lido?” não é propriedade da instrução; é propriedade da instrução no contexto do fluxo de controle. Sem uma representação desse fluxo, 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.
A estrutura tem duas camadas. Embaixo está o bloco básico: um trecho onde não há decisão a tomar, o controle entra por cima e sai por baixo, e a ordem de execução é a ordem do texto; raciocinar ali dentro é barato. Em cima está o grafo de fluxo de controle, que registra como os blocos se ligam — e ali, sim, há bifurcações e, em geral, ciclos. Transformação que opera dentro de um bloco chama-se local e é barata; a que atravessa blocos chama-se global e exige análise de fluxo de dados. Este módulo implementa as primeiras com rigor e apresenta as segundas em panorama.
Formalmente, um bloco básico é uma subsequência contígua maximal de instruções tal que o controle só entra pela primeira e só sai pela última. A palavra “maximal” carrega a definição inteira: qualquer instrução isolada satisfaz as duas condições, e o que torna um bloco um bloco é ser o maior trecho possível com essa propriedade. A construção se faz pelo algoritmo dos líderes: se o controle só entra por cima, um bloco começa onde o controle pode chegar de outro lugar. Uma instrução é líder quando é a primeira da sequência, ou é alvo de desvio, ou segue imediatamente um desvio — e a terceira condição é a que se esquece, porque o desvio, ao ser tomado, encerra o bloco anterior.
Pare e pense. O que acontece com as transformações locais se você esquecer a terceira condição de líder? Antes de responder, lembre que todas elas assumem execução sequencial dentro do bloco.
O resultado que autoriza usar a decomposição sem receio é este: sendo \ell_0 < \ell_1 < \cdots < \ell_{m-1} os líderes, com \ell_0 = 0, os intervalos semiabertos entre líderes consecutivos formam uma partição das instruções, e cada um é um bloco básico. A demonstração é direta: eles cobrem tudo sem sobreposição por serem intervalos consecutivos entre pontos ordenados, e nenhuma instrução estritamente interna é alvo de desvio nem é desvio — se fosse, ela ou a seguinte seria líder, e o intervalo teria terminado ali. Daí saem duas verificações de sanidade: 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.
Com os blocos identificados, resta ligá-los: existe aresta de um bloco para outro quando a última instrução do primeiro pode transferir o controle para a primeira do segundo. Numa sutileza que apanha quase todo mundo, os sucessores se calculam exclusivamente a partir da última instrução do bloco — usar qualquer outra produz arestas fantasma, defeito que só aparece muitos passos adiante.
Repare no destino “fim da regra”. Ele não é um bloco — não há instrução nenhuma lá — e é tentador descartar as arestas que apontam para ele. Não descarte: um bloco terminado em desvio condicional apareceria com um único sucessor, e condicional com um sucessor só contradiz a definição de bifurcação. A estrutura estaria escondendo justamente o que o grafo existe para exibir.
O ganho não é decorativo. Com o grafo pronto, uma classe inteira de perguntas ganha formulação precisa: alcançabilidade vira conectividade, “este valor chega até lá?” vira pergunta sobre caminhos, “existe laço?” vira pergunta sobre ciclos — todas indecidíveis sobre o comportamento do programa, e decidíveis sobre o grafo, que é finito. Essa troca é a manobra central da análise estática, e o preço é perda de precisão, porque nem todo caminho do grafo corresponde a execução real. A análise é, portanto, conservadora, e erra sempre para o mesmo lado.
1.3 Transformações locais, cada uma com a sua condição
Antes de qualquer transformação concreta, preciso fixar 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 programa transformado é sempre observacionalmente equivalente ao original.
Note o que essa definição ignora: tempo, memória, número de instruções — de propósito, porque é isso que a otimização quer mudar. E note que ela observa a ordem: numa linguagem cujo efeito é emitir resultados rotulados, trocar a ordem das emissões muda o que o usuário vê. Você já viu essa igualdade no primeiro módulo, na correção da tradução; é o mesmo contrato, agora entre dois programas da mesma linguagem intermediária, e a otimização é onde ele fica sob pressão máxima. Daí a formulação operacional que quero que você adote: uma otimização é uma transformação com condição de aplicabilidade, e a condição é o que a separa de um defeito. Não existe transformação boa e ruim; existe condição verificada e condição presumida.
| Transformação | O que faz | Condição de segurança |
|---|---|---|
| Dobramento de constantes | calcula em compilação uma operação entre literais | operandos literais no ponto e operação pura, que não falha em execução |
| Propagação de cópias | troca a leitura de um nome pela leitura da origem | nenhum dos dois nomes é redefinido entre a cópia e o uso |
| Eliminação de subexpressões comuns | reusa um resultado já computado | operandos não redefinidos, expressão pura e ocorrências no mesmo bloco |
| Eliminação de código morto | remove instrução cujo resultado ninguém lê | resultado não vivo na saída e ausência de efeito colateral |
No dobramento, a segunda parte da condição é a esquecida. A comparação entre inteiros é pura e não falha, então dobra sem susto. Mas imagine uma divisão com divisor zero: em execução isso é uma falha, e substituí-la por um valor qualquer troca um programa que falha por um que não falha. Guarde a formulação geral — a expressão que falha em execução não pode virar valor em compilação, porque falhar é um comportamento, não um acidente. Há ainda o cuidado aritmético: o dobramento acontece na máquina que compila e o valor é usado na que executa.
A propagação de cópias, sozinha, não remove nada — só troca quem cada uso lê. O ganho vem depois: sem leitor, a cópia fica morta e a transformação seguinte a remove. Aqui aparece o fenômeno que governa o desenho de um otimizador: as transformações se alimentam umas das outras. E vai uma honestidade que quase nunca aparece em livro de compiladores: no nosso compilador ela não tem alvo, porque a tradução nunca emite instrução de cópia. Transformação implementada só para constar é código que ninguém exercita, e é aí que os defeitos se escondem.
Na eliminação de subexpressões comuns, a terceira componente limita a versão local: as ocorrências têm de estar no mesmo bloco, porque fora dele não há garantia de que a primeira computação aconteceu. É essa exigência sintática que a versão global troca por “disponível em todos os caminhos”.
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 máquina de destino do nosso compilador é de pilha, e ler um temporário nela significa desempilhá-lo: o segundo leitor encontraria a pilha vazia. A transformação preserva a semântica da representação intermediária e viola uma precondição do gerador de código.
Extraia disso dois hábitos. O primeiro é o critério correto de aplicabilidade: uma transformação vale quando é semanticamente segura e respeita as precondições das fases posteriores. O segundo serve para qualquer projeto longo: mantenha as invariantes ligadas. Quem acusou a incompatibilidade foi a verificação de uso único escrita um módulo antes, quando o otimizador nem existia — invariante que segue rodando pega o que nenhum teste teria pensado em procurar.
Falta a eliminação de código morto, onde mora o erro clássico da área. A primeira condição vem naturalmente: se o resultado não vai ser lido, calcular é desperdício. A segunda é a que se esquece: a instrução pode importar mesmo que o resultado dela não importe. Na nossa linguagem, a emissão é o caso exemplar, porque não define temporário algum. Um verificador que pergunte só “o resultado é lido?” conclui, com impecável coerência interna, que a emissão é morta, e a remove. O programa resultante compila, executa, passa em toda verificação estrutural, e não produz saída alguma — indistinguível do correto por qualquer critério que não seja o comportamento observável.
Resta a pergunta de projeto: em que ordem aplicar as transformações, e quantas vezes? A resposta ingênua — 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 deixar sem leitor as que as alimentavam. A solução é a que já apareceu duas vezes no curso: repetir até nada mais mudar.
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 transformação ou remove uma instrução ou troca uma expressão por uma constante, e nenhuma das duas acontece indefinidamente numa sequência finita. E registro a armadilha mais comum daqui: remover uma instrução renumera todas as que vêm depois. Se os desvios guardam índices absolutos, cada remoção invalida os alvos posteriores, e esquecer de corrigi-los produz um programa bem formado, que executa e salta para os lugares errados.
1.4 Análise de fluxo de dados: o panorama
A eliminação de código morto precisou saber se um valor ainda seria lido, e essa pergunta não se responde localmente. Um nome está vivo em um ponto quando existe um caminho no grafo de fluxo, começando ali, que o lê antes de redefini-lo. Repare na quantificação existencial: basta um caminho. Se em dez caminhos o valor é descartado e num só ele é lido, o valor está vivo, e removê-lo seria inseguro.
A vivacidade é caso de um esquema que se repete na área inteira, e quem o reconhece aprende as análises particulares quase de graça. Toda análise de fluxo associa a cada ponto do programa um elemento de um conjunto de valores possíveis e relaciona esses elementos por equações: cada instrução tem uma função de transferência, e onde caminhos se juntam uma operação de encontro combina as contribuições. Duas escolhas caracterizam cada análise: a direção, que diz se a informação flui no sentido da execução ou no contrário, e o encontro, que codifica se a pergunta é sobre algum caminho, e aí é união, ou sobre todos, e aí é 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"]
Para a vivacidade, com \mathrm{usa}(i) o conjunto de nomes que a instrução lê e \mathrm{def}(i) o nome 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 primeira é transparente: está vivo na entrada de uma instrução tudo o que ela lê, mais o que estava vivo na saída e não foi redefinido por ela. A segunda diz que o vivo na saída é o vivo na entrada de algum sucessor — união, porque basta um caminho.
Para trás, encontro por união. Pergunta se existe caminho adiante que lê o valor. Habilita a eliminação de código morto e a alocação de registradores, e continua necessária em atribuição única, porque fala de leituras futuras e não de redefinições.
Para a frente, encontro por união. Uma definição alcança um ponto quando existe caminho até ele sem redefinição do nome no meio. É a informação de que a propagação de cópias precisa no caso geral; em atribuição única, o conjunto que cada instrução destrói é vazio e a análise degenera.
Para a frente, encontro por interseção, porque a expressão precisa ter sido computada em todos os caminhos que chegam ao ponto. É o que habilita a versão global da eliminação de subexpressões comuns, aquela que enxerga recomputações espalhadas por blocos distintos.
Que iterar funcione não é óbvio, porque as equações são recursivas e o grafo pode ter ciclos. A garantia vem do teorema de Knaster e Tarski: uma função monótona sobre um reticulado completo tem menor ponto fixo e, se o reticulado tem altura finita, iterar a partir do menor elemento produz uma sequência crescente que estabiliza nesse ponto fixo em número finito de passos. Aqui o reticulado é o conjunto das partes dos nomes do programa, ordenado por inclusão; a altura é o número de nomes; e as funções de transferência são monótonas por serem compostas de união e de subtração de conjunto fixo. O algoritmo termina sempre, com a menor solução — a mais precisa entre as seguras.
Pare e pense. Esta é a terceira vez no curso 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?
E uma recomendação que economiza horas: conte e reporte quantas rodadas foram necessárias, porque análise que nunca converge tem defeito na função de transferência.
Com as análises disponíveis abre-se a família que a versão local não alcança: eliminação global de subexpressões, movimentação de código invariante de laço, propagação global de constantes, eliminação global de código morto. O que quero que fique não é a lista, e sim que 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. Separar a análise, que descobre, da transformação, que age, é a arquitetura consagrada da área.
1.5 Quanto otimizar: a conta entre compilar e executar
Otimizar custa tempo de compilação e economiza tempo de execução — uma troca, e troca se avalia com números.
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. A decisão depende da razão entre esses dois números, e ela varia por ordens de grandeza: programa compilado uma vez e executado milhões de vezes justifica minutos de compilação para arrancar percentuais de execução; programa recompilado a cada alteração não justifica quase nada. É por isso que compiladores de produção oferecem níveis de otimização em vez de um comportamento único — a escolha não é técnica, é de contexto de uso, e fica exposta a quem chama o compilador.
Há um segundo custo, e não é de tempo. Quanto mais o código executado difere do escrito, mais difícil fica relacionar um ao outro — e essa relação é o que a depuração usa: valor removido por estar morto não existe para inspecionar, expressão dobrada nunca é avaliada. É por isso que existe o modo de desenvolvimento com otimização desligada. E há um terceiro custo, que vale conhecer pelo nome: o problema da ordem das fases — aplicar uma transformação antes de outra pode habilitá-la, e na ordem inversa pode destruir a oportunidade. A sequência usada em compiladores reais é calibragem empírica, não derivação teórica.
Fecho com o conselho metodológico mais valioso do módulo: ao avaliar o efeito de uma otimização, resista à tentação de escolher o exemplo. É fácil construir um programa em que uma transformação brilha, e apresentá-lo como típico é o engano involuntário mais comum da área. Meça sobre o que você realmente compila e, ao demonstrar a transformação operando, rotule o exemplo como construído. O corolário é que zero é um resultado publicável.
1.6 Integração final: do texto ao efeito observável
Todas as peças existem agora ao mesmo tempo, e a cadeia nunca foi vista inteira.
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 desse diagrama não existiam no mapa do primeiro módulo: a otimização e a validação. O executor apresentado antes era mínimo por decisão deliberada, detectando objeto malformado em execução, quando a instrução defeituosa fosse alcançada. Isso basta para não produzir resultado errado, e é insuficiente por um motivo que merece clareza: um objeto quebrado em um caminho raro passa por bom até a entrada certa aparecer. A integração final faz as mesmas checagens estaticamente, antes de qualquer execução — verifica que todo índice de constante e de padrão está na faixa, que todo destino de desvio aponta para posição válida, que toda regra alcança um fim, e que o balanço da pilha é consistente.
Essa última é o exemplo mais bonito de verificação estática do curso. Cada instrução tem efeito conhecido sobre a altura da pilha; simulando apenas a altura, sem valores e sem executar nada, determina-se a altura em cada ponto.
A altura da pilha precisa ser propriedade do ponto, não do caminho. Se dois caminhos distintos chegam à mesma instrução com alturas diferentes, o objeto é malformado — mesmo que nenhuma entrada exercite os dois caminhos, e mesmo que todas as execuções observadas funcionem. A condição é verificável estaticamente e é mais forte que qualquer bateria de testes.
Que essa verificação termine não é óbvio, e a razão é uma propriedade do código que geramos: todo desvio salta para a frente, o fluxo é acíclico e uma varredura em profundidade com marcação cobre tudo. Com laços, ela exigiria a maquinaria de ponto fixo da seção anterior — que é como verificadores de máquinas virtuais reais a fazem. E a decisão que acompanha a validação também é de projeto: objeto que não passa não é gravado.
Sobre a execução, uma frase dura e verdadeira: um sistema que só foi exercitado sobre os exemplos que o autor preparou não foi exercitado. O corpus precisa incluir as entradas degeneradas — a vazia, a que não casa com padrão algum, a composta só de separadores —, que travam um executor mal terminado; os casos de fronteira das condições, porque uma regra que testa se um valor é maior que cem pede o cem, o noventa e nove e o cento e um; e os dois lados de cada desvio, sem o que não se distingue uma otimização correta de uma que apagou um caminho.
O tratamento de erro, apresentado no primeiro módulo como serviço transversal, volta agora como atributo de projeto, decidido por escolhas pequenas e acumuladas. A posição vem primeiro: toda mensagem diz onde, o que exige que ela nasça no analisador léxico e sobreviva a todas as fases. Depois a causa provável, que separa diagnóstico de relato — dizer que apareceu um símbolo inesperado é relato; dizer qual era esperado ali, e por qual construção em aberto, é diagnóstico, e a informação já está calculada dentro do analisador. Depois a sugestão de correção, que só compensa quando a correção é única e óbvia. Depois a recuperação, que reporta vários problemas por compilação e traz o risco do erro em cascata. E, por fim, a consistência entre fases: um formato único de severidade, posição e mensagem, que ainda vira navegação clicável se for o formato que editores sabem interpretar.
Falta fechar a promessa da seção anterior: como saber que a otimização preservou a semântica? Não por argumento — argumento estabelece que a transformação é segura se implementada corretamente, e é a implementação que se quer verificar. O método é o confronto: compilar o mesmo programa com e sem otimização, executar os dois objetos sobre o mesmo corpus e exigir efeitos observáveis idênticos, comparando rótulo, valor e posição. A posição não é zelo excessivo — comparar só os valores deixaria passar uma transformação que reordena emissões. Uma verificação vale exatamente o que ela é capaz de reprovar.
Isto é evidência, não prova. Um corpus finito não cobre todas as entradas, e a equivalência observacional quantifica sobre todas. O que a execução diferencial estabelece é que, nas entradas testadas, não houve divergência — a evidência mais forte disponível a custo razoável, e não a mesma coisa que correção.
1.7 O caso conduzido: o compilador fica pronto
Aqui o caso conduzido chega ao fim. Os números apresentados são os que a execução deu, inclusive os que não favorecem a narrativa; e o caso da eliminação de subexpressões comuns é onde a lição de que correção semântica não basta vira relatório.
1.7.1 6.1 Os blocos e o fluxo, sobre a representação intermediária real
A primeira peça é a que descobre a estrutura. Ela recebe a sequência de instruções produzida pela tradução e devolve os blocos básicos, o grafo de fluxo e a informação de qual bloco contém cada instrução.
15_blocos.h
#ifndef PENEIRA_15_BLOCOS_H
#define PENEIRA_15_BLOCOS_H
#include <cstddef>
#include <set>
#include <string>
#include <vector>
#include "13_ri.h"
namespace peneira {
// BLOCOS BÁSICOS E GRAFO DE FLUXO DE CONTROLE.
//
// Um bloco básico é uma sequência maximal de instruções em que o controle entra
// pela primeira e sai pela última — sem desvio para dentro do meio e sem desvio
// para fora antes do fim. É a unidade sobre a qual a otimização local opera, e
// a razão de ela existir é simples: dentro de um bloco, a ordem de execução é a
// ordem do texto, e isso dispensa raciocinar sobre caminhos.
// Um bloco básico, dado pelo intervalo semiaberto de instruções que o compõe.
struct BlocoBasico {
std::size_t inicio = 0;
std::size_t fim = 0; // exclusivo
std::vector<std::size_t> sucessores;
// O fim da regra não é um bloco — não há instrução lá —, mas é um destino
// legítimo, e é para onde vão os desvios de condição falsa. Sem este campo
// um bloco que só sai pelo fim apareceria sem sucessor nenhum, e um
// condicional cujo alvo é o fim apareceria com um sucessor só, escondendo
// justamente a bifurcação que o grafo existe para mostrar.
bool saiParaOFim = false;
};
struct GrafoDeFluxo {
std::vector<BlocoBasico> blocos;
// Índice do bloco que contém cada instrução.
std::vector<std::size_t> blocoDaInstrucao;
};
// O algoritmo dos líderes. Um líder é: a primeira instrução; toda instrução
// alvo de desvio; e toda instrução que segue imediatamente um desvio. Cada
// líder abre um bloco, que vai até o líder seguinte.
std::vector<std::size_t> lideres(const CodigoRI& ri);
GrafoDeFluxo construirGrafo(const CodigoRI& ri);
std::string formatarGrafo(const CodigoRI& ri, const GrafoDeFluxo& g);
// ---------------------------------------------------------------------------
// Análise de fluxo de dados: variáveis vivas, por ponto fixo
// ---------------------------------------------------------------------------
//
// Um temporário está VIVO num ponto se algum caminho a partir dali o lê antes
// de redefini-lo. É a informação que torna a eliminação de código morto segura:
// só se remove a definição de algo que não está vivo na saída.
//
// A análise é PARA TRÁS — a informação flui do uso para a definição — e é
// resolvida por ponto fixo: repetir as equações até nada mudar. É exatamente a
// mesma técnica dos conjuntos de anuláveis e produtivos do módulo 8 e dos
// primeiros e seguidores do módulo 10. Terceira aparição do mesmo padrão no
// semestre, e vale nomear: quando a definição de um conjunto se refere a si
// mesma, calcula-se por ponto fixo.
struct AnaliseDeVivacidade {
// Para cada instrução, os temporários vivos na saída dela.
std::vector<std::set<std::string>> vivosNaSaida;
// Quantas rodadas até estabilizar. Serve para mostrar que o ponto fixo
// existe e é alcançado, em vez de afirmá-lo.
std::size_t iteracoes = 0;
};
AnaliseDeVivacidade analisarVivacidade(const CodigoRI& ri);
std::string formatarVivacidade(const CodigoRI& ri,
const AnaliseDeVivacidade& a);
// Sucessores de uma instrução no fluxo de controle. O índice igual ao tamanho
// do vetor representa o fim da regra e não tem sucessor.
std::vector<std::size_t> sucessoresDe(const CodigoRI& ri, std::size_t i);
// O que a instrução define e o que ela lê. Separado porque três clientes
// precisam da mesma informação — vivacidade, eliminação de morto e o cálculo de
// subexpressões — e tê-la em um lugar só evita que divirjam.
std::string definidoPor(const InstrucaoRI& ins);
std::vector<std::string> lidosPor(const InstrucaoRI& ins);
// Uma instrução tem efeito colateral quando sua execução importa mesmo que seu
// resultado não seja lido. Nesta linguagem, só a emissão — e essa distinção é
// o que separa uma eliminação de código morto correta de uma que apaga a saída
// do programa.
bool temEfeitoColateral(const InstrucaoRI& ins);
} // namespace peneira
#endif // PENEIRA_15_BLOCOS_H
Repare em duas decisões de interface, porque as duas foram tomadas depois de errar. A primeira é o campo que marca a saída de um bloco para o fim da regra. O fim não é um bloco — não há instrução alguma lá —, e a versão inicial simplesmente descartava as arestas que apontavam para ele. O efeito era que um bloco terminado em desvio condicional aparecia com um único sucessor, contradizendo a própria definição de bifurcação. A exibição escondia o conceito que o grafo existe para mostrar. A segunda é a separação das funções que dizem o que uma instrução define e o que ela lê: três clientes diferentes precisam dessa mesma informação — a análise de vivacidade, a eliminação de código morto e o cálculo de subexpressões comuns —, e tê-la em um lugar só é o que impede que divirjam silenciosamente.
15_blocos.cpp
#include "15_blocos.h"
#include <algorithm>
#include <sstream>
namespace peneira {
std::string definidoPor(const InstrucaoRI& ins) {
switch (ins.op) {
case OpRI::Constante:
case OpRI::CasamentoDe:
case OpRI::Valor:
case OpRI::Comparacao:
return ins.resultado;
default:
return std::string();
}
}
std::vector<std::string> lidosPor(const InstrucaoRI& ins) {
switch (ins.op) {
case OpRI::Valor:
case OpRI::DesvioSeFalso:
return {ins.arg1};
case OpRI::Comparacao:
return {ins.arg1, ins.arg2};
case OpRI::Emite:
// arg1 é o rótulo literal, não um temporário. Incluí-lo aqui faria
// o rótulo virar um nome vivo e nunca eliminado — inofensivo por
// acaso, e errado por princípio.
return {ins.arg2};
default:
return {};
}
}
bool temEfeitoColateral(const InstrucaoRI& ins) {
return ins.op == OpRI::Emite;
}
std::vector<std::size_t> sucessoresDe(const CodigoRI& ri, std::size_t i) {
if (i >= ri.instrucoes.size()) {
return {};
}
const InstrucaoRI& ins = ri.instrucoes[i];
if (ins.op == OpRI::Desvio) {
return {ins.destino};
}
if (ins.op == OpRI::DesvioSeFalso) {
// Dois sucessores: a queda e o alvo. É esta instrução que faz o fluxo
// deixar de ser uma linha e virar grafo.
if (ins.destino == i + 1) {
return {i + 1};
}
return {i + 1, ins.destino};
}
return {i + 1};
}
std::vector<std::size_t> lideres(const CodigoRI& ri) {
std::set<std::size_t> marcados;
if (!ri.instrucoes.empty()) {
marcados.insert(0);
}
for (std::size_t i = 0; i < ri.instrucoes.size(); ++i) {
const InstrucaoRI& ins = ri.instrucoes[i];
const bool ehDesvio =
ins.op == OpRI::Desvio || ins.op == OpRI::DesvioSeFalso;
if (!ehDesvio) {
continue;
}
// Alvo do desvio é líder — desde que caia dentro do código. O destino
// igual ao tamanho é o fim da regra, que não abre bloco.
if (ins.destino < ri.instrucoes.size()) {
marcados.insert(ins.destino);
}
// A instrução seguinte a um desvio também é líder: se o desvio for
// tomado, o controle nunca chega nela pela queda.
if (i + 1 < ri.instrucoes.size()) {
marcados.insert(i + 1);
}
}
return std::vector<std::size_t>(marcados.begin(), marcados.end());
}
GrafoDeFluxo construirGrafo(const CodigoRI& ri) {
GrafoDeFluxo g;
const std::vector<std::size_t> ls = lideres(ri);
if (ls.empty()) {
return g;
}
for (std::size_t k = 0; k < ls.size(); ++k) {
BlocoBasico b;
b.inicio = ls[k];
b.fim = (k + 1 < ls.size()) ? ls[k + 1] : ri.instrucoes.size();
g.blocos.push_back(b);
}
g.blocoDaInstrucao.assign(ri.instrucoes.size(), 0);
for (std::size_t k = 0; k < g.blocos.size(); ++k) {
for (std::size_t i = g.blocos[k].inicio; i < g.blocos[k].fim; ++i) {
g.blocoDaInstrucao[i] = k;
}
}
// Arestas: saem da ÚLTIMA instrução de cada bloco, porque é a única de onde
// o controle pode deixar o bloco. Calcular a partir de qualquer outra
// produziria arestas que não existem.
for (std::size_t k = 0; k < g.blocos.size(); ++k) {
if (g.blocos[k].fim == g.blocos[k].inicio) {
continue;
}
const std::size_t ultima = g.blocos[k].fim - 1;
for (const std::size_t s : sucessoresDe(ri, ultima)) {
if (s >= ri.instrucoes.size()) {
g.blocos[k].saiParaOFim = true;
continue;
}
const std::size_t destino = g.blocoDaInstrucao[s];
auto& suc = g.blocos[k].sucessores;
if (std::find(suc.begin(), suc.end(), destino) == suc.end()) {
suc.push_back(destino);
}
}
}
return g;
}
std::string formatarGrafo(const CodigoRI& ri, const GrafoDeFluxo& g) {
std::ostringstream out;
out << " bloco | instrucoes | sucessores\n";
out << " ------+------------+-----------\n";
for (std::size_t k = 0; k < g.blocos.size(); ++k) {
const BlocoBasico& b = g.blocos[k];
const std::string faixa =
std::to_string(b.inicio) + ".." + std::to_string(b.fim - 1);
out << " B" << k << " | " << faixa;
for (std::size_t i = faixa.size(); i < 9; ++i) {
out << ' ';
}
out << " | ";
bool primeiro = true;
for (const std::size_t s : b.sucessores) {
if (!primeiro) {
out << ", ";
}
out << "B" << s;
primeiro = false;
}
if (b.saiParaOFim) {
if (!primeiro) {
out << ", ";
}
out << "(fim)";
primeiro = false;
}
if (primeiro) {
out << "(fim)";
}
out << '\n';
}
(void)ri;
return out.str();
}
AnaliseDeVivacidade analisarVivacidade(const CodigoRI& ri) {
AnaliseDeVivacidade a;
const std::size_t n = ri.instrucoes.size();
a.vivosNaSaida.assign(n, std::set<std::string>());
std::vector<std::set<std::string>> vivosNaEntrada(n);
bool mudou = true;
while (mudou) {
mudou = false;
++a.iteracoes;
// Percorre de trás para a frente: a informação flui do uso para a
// definição, e ir na direção do fluxo faz o ponto fixo convergir em
// menos rodadas. Ir para a frente também converge — só demora mais.
for (std::size_t k = n; k > 0; --k) {
const std::size_t i = k - 1;
std::set<std::string> saida;
for (const std::size_t s : sucessoresDe(ri, i)) {
if (s < n) {
saida.insert(vivosNaEntrada[s].begin(),
vivosNaEntrada[s].end());
}
}
std::set<std::string> entrada = saida;
const std::string def = definidoPor(ri.instrucoes[i]);
if (!def.empty()) {
entrada.erase(def);
}
for (const std::string& uso : lidosPor(ri.instrucoes[i])) {
if (!uso.empty()) {
entrada.insert(uso);
}
}
if (saida != a.vivosNaSaida[i] || entrada != vivosNaEntrada[i]) {
a.vivosNaSaida[i] = saida;
vivosNaEntrada[i] = entrada;
mudou = true;
}
}
}
return a;
}
std::string formatarVivacidade(const CodigoRI& ri,
const AnaliseDeVivacidade& a) {
std::ostringstream out;
out << " instr | vivos na saida\n";
out << " ------+---------------\n";
for (std::size_t i = 0; i < ri.instrucoes.size(); ++i) {
out << " " << i;
if (i < 10) {
out << ' ';
}
out << " | ";
if (a.vivosNaSaida[i].empty()) {
out << "(nenhum)";
} else {
bool primeiro = true;
for (const std::string& v : a.vivosNaSaida[i]) {
if (!primeiro) {
out << ", ";
}
out << v;
primeiro = false;
}
}
out << '\n';
}
return out.str();
}
} // namespace peneira
Sobre a condição composta que a tradução produz para uma regra com conjunção, o resultado é este:
lideres: 0, 5, 10
bloco | instrucoes | sucessores
------+------------+-----------
B0 | 0..4 | B1, (fim)
B1 | 5..9 | B2, (fim)
B2 | 10..11 | (fim)Três blocos, um por operando da conjunção mais o da emissão, e a estrutura é exatamente a do curto-circuito: de B0 sai-se para B1 se a primeira comparação passar, e direto para o fim se não passar. O grafo não foi desenhado, foi calculado — e é o mesmo objeto sobre o qual a análise de vivacidade vai operar.
A análise de vivacidade devolve, além do resultado, o número de rodadas até estabilizar:
instr | vivos na saida
------+---------------
0 | t0
1 | t1
2 | t1, t2
3 | t3
4 | (nenhum)
5 | t4
...
ponto fixo alcancado em 2 rodada(s)Duas rodadas: uma que calcula e outra que confirma que nada mudou. Publiquei o número em vez de afirmar que o ponto fixo existe. E há uma leitura dessa tabela que explica o capítulo inteiro: quase nenhum temporário fica vivo por muito tempo — no máximo dois ao mesmo tempo, cada valor consumido logo depois de produzido. É a mesma quantidade que a análise de interferência do capítulo anterior apontou, calculada por outro caminho.
1.7.2 6.2 As transformações, com a condição de segurança declarada em cada uma
15_otimizacao.h
#ifndef PENEIRA_15_OTIMIZACAO_H
#define PENEIRA_15_OTIMIZACAO_H
#include <cstddef>
#include <string>
#include <vector>
#include "10_ast.h"
#include "12_sema.h"
#include "13_objeto.h"
#include "13_ri.h"
#include "14_codegen.h"
#include "15_blocos.h"
namespace peneira {
// OTIMIZAÇÕES LOCAIS, cada uma com a condição que a torna segura.
//
// A regra que governa tudo aqui é absoluta e não negociável: a transformação
// tem de PRESERVAR A SEMÂNTICA. Otimização não é esperteza — é transformação
// com condição de aplicabilidade, e a condição é o que separa uma otimização de
// um defeito. Toda função deste arquivo declara a sua.
//
// Uma propriedade da nossa representação intermediária simplifica a vida e vale
// nomear: cada temporário é atribuído UMA ÚNICA VEZ. Isso é, em pequeno, o que
// a forma de atribuição única estática mencionada no módulo 13 faz em grande, e
// é o que torna dispensável verificar se um valor foi redefinido entre a
// definição e o uso — não há redefinição possível.
struct EstatisticasDeOtimizacao {
std::size_t dobramentos = 0;
std::size_t subexpressoesEliminadas = 0;
std::size_t instrucoesMortas = 0;
std::size_t iteracoes = 0;
std::size_t instrucoesAntes = 0;
std::size_t instrucoesDepois = 0;
};
// ---------------------------------------------------------------------------
// Dobramento de constantes
// ---------------------------------------------------------------------------
//
// Substitui uma comparação entre dois valores conhecidos na compilação pelo
// resultado dela.
//
// CONDIÇÃO DE SEGURANÇA: os dois operandos têm de ser constantes literais, e a
// operação tem de ser pura — sem efeito e sem depender de nada além dos
// operandos. Comparação satisfaz. Se a linguagem tivesse divisão, o dobramento
// precisaria excluir o divisor zero, porque a expressão que falha em execução
// não pode ser substituída por um valor em compilação.
CodigoRI dobrarConstantes(const CodigoRI& ri, EstatisticasDeOtimizacao& e);
// ---------------------------------------------------------------------------
// Eliminação de código morto
// ---------------------------------------------------------------------------
//
// Remove instruções cujo resultado não é lido em caminho nenhum.
//
// CONDIÇÃO DE SEGURANÇA: duas, e esquecer a segunda é o erro clássico. O
// resultado não pode estar vivo na saída — o que a análise de vivacidade
// responde — E a instrução não pode ter efeito colateral. Uma emissão não
// produz resultado algum, então um verificador que olhe só a primeira condição
// a considera morta e apaga a saída inteira do programa.
//
// O parâmetro `guardaDeEfeito` existe para DEMONSTRAR esse erro: com ele em
// falso, a função vira a versão defeituosa. Não é código morto nem opção de
// configuração — é o contraexemplo executável de que a condição importa.
CodigoRI eliminarCodigoMorto(const CodigoRI& ri, EstatisticasDeOtimizacao& e,
bool guardaDeEfeito = true);
// ---------------------------------------------------------------------------
// Eliminação de subexpressões comuns
// ---------------------------------------------------------------------------
//
// Quando a mesma expressão é computada duas vezes dentro de um bloco, sem que
// seus operandos mudem entre as duas, a segunda pode reusar o resultado da
// primeira.
//
// CONDIÇÃO DE SEGURANÇA: os operandos não podem ser redefinidos entre as duas
// ocorrências (garantido pela atribuição única), a expressão tem de ser pura, e
// as duas ocorrências têm de estar NO MESMO BLOCO — fora do bloco não há
// garantia de que a primeira tenha sido executada.
//
// ATENÇÃO, e este é o achado deste módulo: esta transformação é semanticamente
// correta e MESMO ASSIM não pode ser aplicada neste compilador. Ver
// `cseQuebraGeracao` e o relatório da demonstração.
CodigoRI eliminarSubexpressoes(const CodigoRI& ri, const GrafoDeFluxo& g,
EstatisticasDeOtimizacao& e);
// Devolve os temporários que passariam a ser lidos mais de uma vez se a
// eliminação de subexpressões fosse aplicada. Vazio significa que a
// transformação é compatível com o gerador de código.
//
// A máquina de destino é de pilha, e ler um temporário é DESEMPILHÁ-LO. O
// gerador do módulo 14 verifica que cada temporário é lido exatamente uma vez,
// e a eliminação de subexpressões faz exatamente o contrário: ela existe para
// que um resultado sirva a vários leitores. Correta para uma máquina de
// registradores, incompatível com esta.
std::vector<std::string> cseQuebraGeracao(const CodigoRI& original,
const CodigoRI& otimizado);
// ---------------------------------------------------------------------------
// Condutor
// ---------------------------------------------------------------------------
//
// Aplica as transformações seguras repetidamente até nada mais mudar — um ponto
// fixo, pelo mesmo motivo dos módulos 8, 10 e da análise de vivacidade: cada
// transformação cria oportunidades para as outras. Dobrar uma constante torna
// morto o cálculo que a produzia; remover o cálculo pode tornar morto o que o
// alimentava.
CodigoRI otimizar(const CodigoRI& ri, EstatisticasDeOtimizacao& e);
// Gera o objeto inserindo a otimização entre a representação intermediária e a
// emissão. Espelha `gerarObjeto` do módulo 14, com uma passada a mais no meio.
//
// Mora aqui, e não no módulo 14, para que a dependência aponte para a frente:
// o gerador não pode precisar do otimizador, senão o compilador do módulo 14
// deixaria de compilar sozinho. O preço é a repetição do laço que percorre as
// ações, e é preço consciente.
ProgramaObjeto gerarObjetoOtimizado(const ResultadoSemantico& semantico,
const NoAst& raiz,
RelatorioDeGeracao& relatorio,
EstatisticasDeOtimizacao& e);
} // namespace peneira
#endif // PENEIRA_15_OTIMIZACAO_H
Cada função declara, no seu comentário de cabeçalho, a condição que a torna segura. Isso não é zelo documental: é a única forma de tornar revisável uma transformação. Uma otimização cuja condição de aplicabilidade não está escrita em lugar nenhum é indistinguível de um defeito que ainda não se manifestou.
15_otimizacao.cpp
#include "15_otimizacao.h"
#include <cstdlib>
#include <unordered_map>
namespace peneira {
namespace {
// Uma constante literal, se a instrução for uma. `ehNumero` distingue "100" de
// um texto, porque comparar texto por ordem não é permitido nesta linguagem e
// o dobramento não pode inventar essa comparação.
struct Literal {
bool existe = false;
bool ehNumero = false;
double numero = 0.0;
std::string texto;
};
Literal literalDe(const InstrucaoRI& ins) {
Literal l;
if (ins.op != OpRI::Constante) {
return l;
}
const std::string& bruto = ins.arg1;
if (bruto.size() >= 2 && bruto.front() == '"' && bruto.back() == '"') {
l.existe = true;
l.texto = bruto.substr(1, bruto.size() - 2);
return l;
}
char* fim = nullptr;
const double n = std::strtod(bruto.c_str(), &fim);
if (fim != nullptr && *fim == '\0' && !bruto.empty()) {
l.existe = true;
l.ehNumero = true;
l.numero = n;
}
return l;
}
bool avaliar(const std::string& operador, const Literal& a, const Literal& b,
bool& resultado) {
if (a.ehNumero != b.ehNumero) {
return false; // tipos diferentes: a semântica já recusou isto antes
}
if (a.ehNumero) {
if (operador == ">") { resultado = a.numero > b.numero; return true; }
if (operador == "<") { resultado = a.numero < b.numero; return true; }
if (operador == ">=") { resultado = a.numero >= b.numero; return true; }
if (operador == "<=") { resultado = a.numero <= b.numero; return true; }
if (operador == "==") { resultado = a.numero == b.numero; return true; }
if (operador == "!=") { resultado = a.numero != b.numero; return true; }
return false;
}
// Texto: só igualdade, porque só ela foi permitida na análise semântica.
if (operador == "==") { resultado = a.texto == b.texto; return true; }
if (operador == "!=") { resultado = a.texto != b.texto; return true; }
return false;
}
// Assinatura de uma expressão, para reconhecer repetição. Duas instruções com a
// mesma assinatura computam a mesma coisa.
std::string assinaturaDe(const InstrucaoRI& ins) {
switch (ins.op) {
case OpRI::CasamentoDe:
return "casamento:" + ins.arg1;
case OpRI::Valor:
return "valor:" + ins.arg1;
case OpRI::Constante:
return "const:" + ins.arg1;
case OpRI::Comparacao:
return "cmp:" + ins.operador + ":" + ins.arg1 + ":" + ins.arg2;
default:
return std::string();
}
}
// Reescreve os operandos de leitura conforme o mapa de substituição.
void substituirLeituras(InstrucaoRI& ins,
const std::unordered_map<std::string, std::string>& de) {
auto trocar = [&](std::string& campo) {
const auto it = de.find(campo);
if (it != de.end()) {
campo = it->second;
}
};
switch (ins.op) {
case OpRI::Valor:
case OpRI::DesvioSeFalso:
trocar(ins.arg1);
break;
case OpRI::Comparacao:
trocar(ins.arg1);
trocar(ins.arg2);
break;
case OpRI::Emite:
trocar(ins.arg2);
break;
default:
break;
}
}
// Reconstrói o código sem as instruções marcadas, corrigindo os destinos dos
// desvios. Remover instrução renumera tudo que vem depois, e esquecer de
// corrigir os desvios é o modo mais rápido de transformar uma otimização
// correta num objeto quebrado.
CodigoRI removerMarcadas(const CodigoRI& ri, const std::vector<bool>& remover) {
const std::size_t n = ri.instrucoes.size();
std::vector<std::size_t> novoIndice(n + 1, 0);
std::size_t k = 0;
for (std::size_t i = 0; i < n; ++i) {
novoIndice[i] = k;
if (!remover[i]) {
++k;
}
}
novoIndice[n] = k;
CodigoRI saida;
saida.padrao = ri.padrao;
saida.ligacao = ri.ligacao;
for (std::size_t i = 0; i < n; ++i) {
if (remover[i]) {
continue;
}
InstrucaoRI ins = ri.instrucoes[i];
if (ins.op == OpRI::Desvio || ins.op == OpRI::DesvioSeFalso) {
if (ins.destino <= n) {
ins.destino = novoIndice[ins.destino];
}
}
saida.instrucoes.push_back(ins);
}
return saida;
}
} // namespace
CodigoRI dobrarConstantes(const CodigoRI& ri, EstatisticasDeOtimizacao& e) {
// Mapa de temporário para o literal que ele contém. Vale porque cada
// temporário é atribuído uma única vez.
std::unordered_map<std::string, Literal> constantes;
CodigoRI saida;
saida.padrao = ri.padrao;
saida.ligacao = ri.ligacao;
saida.instrucoes = ri.instrucoes;
for (std::size_t i = 0; i < saida.instrucoes.size(); ++i) {
InstrucaoRI& ins = saida.instrucoes[i];
if (ins.op == OpRI::Constante) {
const Literal l = literalDe(ins);
if (l.existe) {
constantes[ins.resultado] = l;
}
continue;
}
if (ins.op != OpRI::Comparacao) {
continue;
}
const auto a = constantes.find(ins.arg1);
const auto b = constantes.find(ins.arg2);
if (a == constantes.end() || b == constantes.end()) {
continue;
}
bool valor = false;
if (!avaliar(ins.operador, a->second, b->second, valor)) {
continue;
}
// A comparação vira uma constante. Os operandos ficam sem leitor e
// serão removidos pela eliminação de código morto — não aqui, porque
// cada transformação faz uma coisa só.
const std::string resultado = ins.resultado;
ins = InstrucaoRI{};
ins.op = OpRI::Constante;
ins.resultado = resultado;
ins.arg1 = valor ? "1" : "0";
constantes[resultado] = literalDe(ins);
++e.dobramentos;
}
return saida;
}
CodigoRI eliminarCodigoMorto(const CodigoRI& ri, EstatisticasDeOtimizacao& e,
bool guardaDeEfeito) {
const AnaliseDeVivacidade vivacidade = analisarVivacidade(ri);
std::vector<bool> remover(ri.instrucoes.size(), false);
for (std::size_t i = 0; i < ri.instrucoes.size(); ++i) {
const InstrucaoRI& ins = ri.instrucoes[i];
// Desvios nunca são mortos: eles não definem valor, definem controle.
if (ins.op == OpRI::Desvio || ins.op == OpRI::DesvioSeFalso) {
continue;
}
// A segunda condição de segurança. Sem ela, toda emissão é considerada
// morta — ela não define temporário nenhum — e o programa otimizado
// deixa de produzir saída.
if (guardaDeEfeito && temEfeitoColateral(ins)) {
continue;
}
const std::string def = definidoPor(ins);
if (def.empty()) {
// Não define nada e não tem efeito guardado: só sobra a emissão
// quando a guarda está desligada, que é o caso do contraexemplo.
if (!guardaDeEfeito && temEfeitoColateral(ins)) {
remover[i] = true;
++e.instrucoesMortas;
}
continue;
}
if (vivacidade.vivosNaSaida[i].count(def) == 0) {
remover[i] = true;
++e.instrucoesMortas;
}
}
return removerMarcadas(ri, remover);
}
CodigoRI eliminarSubexpressoes(const CodigoRI& ri, const GrafoDeFluxo& g,
EstatisticasDeOtimizacao& e) {
std::vector<bool> remover(ri.instrucoes.size(), false);
std::unordered_map<std::string, std::string> substituir;
for (const BlocoBasico& bloco : g.blocos) {
// O dicionário é reiniciado a cada bloco, e é isso que mantém a
// transformação LOCAL: fora do bloco não há garantia de que a primeira
// ocorrência tenha sido executada.
std::unordered_map<std::string, std::string> disponivel;
for (std::size_t i = bloco.inicio; i < bloco.fim; ++i) {
const InstrucaoRI& ins = ri.instrucoes[i];
if (temEfeitoColateral(ins)) {
continue;
}
const std::string chave = assinaturaDe(ins);
if (chave.empty() || ins.resultado.empty()) {
continue;
}
const auto it = disponivel.find(chave);
if (it == disponivel.end()) {
disponivel.emplace(chave, ins.resultado);
continue;
}
// Já calculado neste bloco: a segunda ocorrência some e seus
// leitores passam a ler o primeiro resultado.
remover[i] = true;
substituir[ins.resultado] = it->second;
++e.subexpressoesEliminadas;
}
}
CodigoRI intermediario = ri;
for (InstrucaoRI& ins : intermediario.instrucoes) {
substituirLeituras(ins, substituir);
}
return removerMarcadas(intermediario, remover);
}
std::vector<std::string> cseQuebraGeracao(const CodigoRI& original,
const CodigoRI& otimizado) {
(void)original;
std::unordered_map<std::string, std::size_t> leituras;
for (const InstrucaoRI& ins : otimizado.instrucoes) {
for (const std::string& t : lidosPor(ins)) {
if (!t.empty()) {
++leituras[t];
}
}
}
std::vector<std::string> violacoes;
for (const auto& par : leituras) {
if (par.second > 1) {
violacoes.push_back(par.first + " passaria a ser lido " +
std::to_string(par.second) + " vezes");
}
}
return violacoes;
}
CodigoRI otimizar(const CodigoRI& ri, EstatisticasDeOtimizacao& e) {
e.instrucoesAntes = ri.instrucoes.size();
CodigoRI atual = ri;
// Ponto fixo: repete enquanto o tamanho encolher. Cada transformação cria
// oportunidade para a outra — dobrar uma constante deixa órfão o cálculo
// que a produzia, e removê-lo pode deixar órfão o que o alimentava.
//
// 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;
}
}
e.instrucoesDepois = atual.instrucoes.size();
return atual;
}
namespace {
void colherAcoesOtim(const NoAst& no, std::vector<const NoAst*>& saida) {
if (no.tipo == TipoAst::Acao) {
saida.push_back(&no);
return;
}
for (const AstPtr& filho : no.filhos) {
if (filho) {
colherAcoesOtim(*filho, saida);
}
}
}
} // namespace
ProgramaObjeto gerarObjetoOtimizado(const ResultadoSemantico& semantico,
const NoAst& raiz,
RelatorioDeGeracao& relatorio,
EstatisticasDeOtimizacao& e) {
ProgramaObjeto objeto;
std::unordered_map<std::string, std::uint32_t> indiceDoPadrao;
for (const PadraoCompilado& p : semantico.padroes) {
indiceDoPadrao.emplace(
p.nome, static_cast<std::uint32_t>(objeto.padroes.size()));
objeto.padroes.push_back(serializarPadrao(
p.automato, p.nome, p.tipoDoCasamento == Tipo::Numero));
}
std::vector<const NoAst*> acoes;
colherAcoesOtim(raiz, acoes);
for (const NoAst* acao : acoes) {
TradutorRI tradutor;
const CodigoRI bruta = tradutor.traduzirAcao(*acao);
// A única diferença em relação ao gerador do módulo 14.
EstatisticasDeOtimizacao parcial;
const CodigoRI ri = otimizar(bruta, parcial);
e.dobramentos += parcial.dobramentos;
e.instrucoesMortas += parcial.instrucoesMortas;
e.iteracoes += parcial.iteracoes;
e.instrucoesAntes += parcial.instrucoesAntes;
e.instrucoesDepois += parcial.instrucoesDepois;
const auto it = indiceDoPadrao.find(acao->texto);
if (it == indiceDoPadrao.end()) {
continue;
}
RegraObjeto regra;
regra.indiceDoPadrao = it->second;
regra.ligacao = acao->conteudo;
regra.codigo = gerarCodigoDaRegra(ri, objeto, relatorio);
objeto.regras.push_back(std::move(regra));
++relatorio.regrasGeradas;
}
return objeto;
}
} // namespace peneira
Sobre um programa típico da linguagem, o condutor não encontra nada:
CASO 1 — programa tipico da linguagem
instrucoes antes: 12, depois: 12
dobramentos: 0, instrucoes mortas removidas: 0A tentação, aqui, seria escolher um exemplo que rendesse e apresentá-lo como típico. O resultado honesto é este, e ele tem explicação: a representação intermediária sai de uma tradução direta da árvore, cada valor é usado logo depois de produzido, e não há redundância a remover. Um otimizador que não acha nada em código apertado está funcionando.
Para mostrar as transformações operando, escrevi um programa artificial, e o rotulei como tal — a condição é decidível na compilação, coisa que nenhum programa útil faria:
antes: depois:
0: t0 := 100 0: t2 := 1
1: t1 := 500 1: se_falso t2 desvia para 4
2: t2 := t0 < t1 2: t3 := casamento n
3: se_falso t2 desvia para 6 3: emite "sempre", t3
4: t3 := casamento n 4: (fim da regra)
5: emite "sempre", t3
6: (fim da regra)
instrucoes: 6 -> 4, dobramentos: 1, mortas: 2, iteracoes: 2Duas coisas para reparar, e as duas foram anunciadas na teoria. As transformações se alimentam: dobrar a comparação deixa os dois operandos sem leitor, e a eliminação de código morto os remove — por isso o condutor repete até o ponto fixo em vez de fazer uma passada de cada. E o destino do desvio mudou de seis para quatro: remover instrução renumera tudo que vem depois, e esquecer de corrigir os desvios é o modo mais rápido de transformar uma otimização correta num objeto quebrado.
1.7.3 6.3 A preservação verificada por confronto, e a transformação que apaga a saída
A comparação diferencial roda sobre o corpus e devolve:
caso 1: 13 instrucoes sem otimizacao, 13 com
entradas comparadas: 5, emissoes conferidas: 5
equivalentes: SIM
caso 2: 7 instrucoes sem otimizacao, 5 com
entradas comparadas: 5, emissoes conferidas: 17
equivalentes: SIMA comparação confere rótulo, valor e posição. Comparar só o valor deixaria passar uma transformação que reordena emissões ou desloca o casamento — dois defeitos plausíveis que a comparação frouxa não pegaria. E isto continua sendo evidência, não prova.
A demonstração do erro clássico está no parâmetro que desliga a guarda de efeito colateral. Com ele desligado, a eliminação de código morto considera a emissão morta, porque a emissão não produz resultado algum:
com guarda: 12 instrucoes, 0 removidas
sem guarda: 11 instrucoes, 1 removidas
emissoes no programa: 1 antes, 0 depois da versao sem guardaO programa otimizado não produz saída alguma. Continua compilando, continua executando, não acusa erro nenhum, passa em toda checagem estrutural — e não faz mais nada. É o exemplo mais direto de por que a preservação de semântica é requisito e não recomendação: a versão quebrada é indistinguível da correta por qualquer critério que não seja o comportamento observável.
1.7.4 6.4 A eliminação de subexpressões comuns, correta e inaplicável
Este é o achado do capítulo, e não estava previsto quando comecei a implementação. A eliminação de subexpressões está escrita, e o relatório sobre dois programas é este:
programa tipico (where com 'and'):
blocos: 3, subexpressoes eliminadas: 0, instrucoes: 12 -> 12
nenhuma violacao: as repeticoes de 'casamento n' caem em
blocos DIFERENTES, e a transformacao local nao as alcanca.
programa artificial (where value(n) > value(n)):
blocos: 2, subexpressoes eliminadas: 1, instrucoes: 8 -> 7
VIOLACOES da invariante de uso unico do modulo 14:
t0 passaria a ser lido 2 vezes
O gerador do modulo 14 RECUSA este codigo.No programa típico a transformação não dispara, e a razão é instrutiva: as repetições caem em blocos diferentes, e uma transformação local não as alcança. Capturá-las exigiria análise global — que é exatamente o panorama da seção sobre fluxo de dados, e que este compilador não implementa. O limite da otimização local está medido, não afirmado.
No programa artificial ela dispara, e aí aparece o problema. A eliminação de subexpressões existe para que um resultado sirva a vários leitores. A máquina de destino é de pilha, e ler um temporário é desempilhá-lo: o segundo leitor encontraria a pilha vazia. A transformação preserva a semântica e viola a precondição do gerador de código — e quem a acusa é a verificação de uso único escrita um capítulo antes, sem prever este uso. Por isso ela está implementada e fora do condutor, com a decisão registrada no cabeçalho: deixá-la de fora sem explicação pareceria esquecimento, e deixá-la dentro produziria objeto quebrado.
1.7.5 6.5 A validação estática e o fecho ponta a ponta
15_validacao.h
#ifndef PENEIRA_15_VALIDACAO_H
#define PENEIRA_15_VALIDACAO_H
#include <string>
#include <vector>
#include "13_objeto.h"
namespace peneira {
// INTEGRAÇÃO FINAL: tratamento de erro completo.
//
// O executor do módulo 14 era mínimo por decisão: ele detectava objeto
// malformado em EXECUÇÃO, quando a instrução defeituosa era alcançada. Isso
// significa que um objeto quebrado num caminho raro passa por bom até a entrada
// certa aparecer.
//
// A validação abaixo faz as mesmas checagens ESTATICAMENTE, antes de qualquer
// execução, percorrendo todo o objeto em vez de só o caminho tomado. É a
// diferença entre "não deu erro nos testes" e "não pode dar erro".
struct ProblemaNoObjeto {
std::string onde;
std::string mensagem;
};
// Percorre o objeto inteiro e devolve tudo que está errado. Lista vazia
// significa que nenhuma das condições de erro previstas na especificação do
// módulo 13 pode ocorrer em execução.
//
// Checa: índices de constante e de padrão dentro da faixa; destinos de desvio
// dentro da faixa; toda regra alcançando um fim; e — a mais interessante — o
// BALANÇO DA PILHA, por simulação estática de todos os caminhos. Um objeto em
// que algum caminho desempilha de pilha vazia é malformado, e descobrir isso
// sem executar é possível porque o fluxo é acíclico.
std::vector<ProblemaNoObjeto> validarObjeto(const ProgramaObjeto& objeto);
// ---------------------------------------------------------------------------
// Preservação de semântica, verificada por execução diferencial
// ---------------------------------------------------------------------------
//
// A exigência de preservar a semântica não se demonstra por argumento — se
// demonstra por confronto. Compilamos o mesmo programa com e sem otimização,
// executamos os dois objetos sobre o mesmo corpus e exigimos emissões
// idênticas, na mesma ordem e nas mesmas posições.
//
// Isso não é prova: um corpus finito não cobre todas as entradas. É evidência,
// e é a evidência mais forte disponível a custo razoável — a mesma natureza do
// confronto entre autômato gerado e manual do módulo 4.
struct ResultadoDaComparacao {
bool equivalentes = true;
std::size_t entradasComparadas = 0;
std::size_t emissoesComparadas = 0;
std::string divergencia;
};
ResultadoDaComparacao compararExecucoes(const ProgramaObjeto& a,
const ProgramaObjeto& b,
const std::vector<std::string>& corpus);
} // namespace peneira
#endif // PENEIRA_15_VALIDACAO_H
15_validacao.cpp
#include "15_validacao.h"
#include <algorithm>
#include <vector>
#include "14_vm.h"
namespace peneira {
namespace {
int efeitoNaPilhaDe(OpCode op) noexcept {
switch (op) {
case OpCode::PUSH_CONST:
case OpCode::PUSH_MATCH:
return +1;
case OpCode::VALUE:
return 0;
case OpCode::CMP_GT:
case OpCode::CMP_LT:
case OpCode::CMP_GE:
case OpCode::CMP_LE:
case OpCode::CMP_EQ:
case OpCode::CMP_NE:
case OpCode::AND:
case OpCode::OR:
case OpCode::JUMP_IF_FALSE:
case OpCode::EMIT:
return -1;
case OpCode::JUMP:
case OpCode::HALT:
return 0;
}
return 0;
}
std::string ondeRegra(std::size_t r, std::size_t i) {
return "regra " + std::to_string(r) + ", instrucao " + std::to_string(i);
}
} // namespace
std::vector<ProblemaNoObjeto> validarObjeto(const ProgramaObjeto& objeto) {
std::vector<ProblemaNoObjeto> problemas;
// Padrões: tabela coerente com a quantidade de estados declarada.
for (std::size_t p = 0; p < objeto.padroes.size(); ++p) {
const PadraoObjeto& pd = objeto.padroes[p];
const std::string onde = "padrao " + std::to_string(p);
if (pd.finais.size() != pd.quantidadeDeEstados) {
problemas.push_back(ProblemaNoObjeto{
onde, "vetor de finais nao bate com a quantidade de estados"});
}
if (pd.transicoes.size() !=
static_cast<std::size_t>(pd.quantidadeDeEstados) *
kTamanhoDoAlfabeto) {
problemas.push_back(ProblemaNoObjeto{
onde, "tabela de transicao com tamanho errado"});
}
if (pd.quantidadeDeEstados > 0 &&
pd.estadoInicial >= pd.quantidadeDeEstados) {
problemas.push_back(
ProblemaNoObjeto{onde, "estado inicial fora de faixa"});
}
for (const std::uint32_t t : pd.transicoes) {
if (t != kSemTransicao && t >= pd.quantidadeDeEstados) {
problemas.push_back(
ProblemaNoObjeto{onde, "transicao para estado inexistente"});
break;
}
}
}
for (std::size_t r = 0; r < objeto.regras.size(); ++r) {
const RegraObjeto& regra = objeto.regras[r];
if (regra.indiceDoPadrao >= objeto.padroes.size()) {
problemas.push_back(ProblemaNoObjeto{
"regra " + std::to_string(r), "referencia padrao inexistente"});
continue;
}
if (regra.codigo.empty()) {
problemas.push_back(
ProblemaNoObjeto{"regra " + std::to_string(r), "codigo vazio"});
continue;
}
for (std::size_t i = 0; i < regra.codigo.size(); ++i) {
const Instrucao& ins = regra.codigo[i];
switch (ins.op) {
case OpCode::PUSH_CONST:
case OpCode::EMIT:
if (ins.argumento >= objeto.constantes.size()) {
problemas.push_back(ProblemaNoObjeto{
ondeRegra(r, i), "indice de constante fora de faixa"});
}
break;
case OpCode::JUMP:
case OpCode::JUMP_IF_FALSE:
if (ins.argumento >= regra.codigo.size()) {
problemas.push_back(ProblemaNoObjeto{
ondeRegra(r, i), "desvio fora de faixa"});
}
break;
default:
break;
}
}
// Balanço da pilha por simulação de todos os caminhos. O fluxo gerado
// por este compilador é acíclico — todo desvio vai para a frente —,
// então uma varredura em profundidade com marcação de visitado termina
// e cobre tudo.
//
// Guardamos a altura com que cada instrução é alcançada. Se a mesma
// instrução for alcançada com alturas diferentes, o objeto é
// malformado: a altura da pilha num ponto tem de ser propriedade do
// ponto, e não do caminho.
std::vector<int> alturaEm(regra.codigo.size(), -1);
std::vector<std::pair<std::size_t, int>> pendentes;
pendentes.push_back({0, 0});
bool jaReclamou = false;
while (!pendentes.empty()) {
const std::size_t pc = pendentes.back().first;
const int altura = pendentes.back().second;
pendentes.pop_back();
if (pc >= regra.codigo.size()) {
continue;
}
if (alturaEm[pc] >= 0) {
if (alturaEm[pc] != altura && !jaReclamou) {
problemas.push_back(ProblemaNoObjeto{
ondeRegra(r, pc),
"altura da pilha depende do caminho (" +
std::to_string(alturaEm[pc]) + " ou " +
std::to_string(altura) + ")"});
jaReclamou = true;
}
continue;
}
alturaEm[pc] = altura;
const Instrucao& ins = regra.codigo[pc];
const int depois = altura + efeitoNaPilhaDe(ins.op);
if (depois < 0 && !jaReclamou) {
problemas.push_back(ProblemaNoObjeto{
ondeRegra(r, pc), "desempilha de pilha vazia"});
jaReclamou = true;
continue;
}
if (ins.op == OpCode::HALT) {
continue;
}
if (ins.op == OpCode::JUMP) {
pendentes.push_back({ins.argumento, depois});
continue;
}
if (ins.op == OpCode::JUMP_IF_FALSE) {
pendentes.push_back({ins.argumento, depois});
pendentes.push_back({pc + 1, depois});
continue;
}
pendentes.push_back({pc + 1, depois});
}
// Toda regra tem de poder terminar. Sem HALT alcançável, o executor
// sai por passar da última instrução — o que funciona, mas deixa de
// ser garantia e vira acidente.
bool temHalt = false;
for (std::size_t i = 0; i < regra.codigo.size(); ++i) {
if (regra.codigo[i].op == OpCode::HALT && alturaEm[i] >= 0) {
temHalt = true;
break;
}
}
if (!temHalt) {
problemas.push_back(ProblemaNoObjeto{
"regra " + std::to_string(r), "nenhum HALT alcancavel"});
}
}
return problemas;
}
ResultadoDaComparacao compararExecucoes(
const ProgramaObjeto& a, const ProgramaObjeto& b,
const std::vector<std::string>& corpus) {
ResultadoDaComparacao r;
for (const std::string& entrada : corpus) {
++r.entradasComparadas;
const ResultadoExecucao ra = executar(a, entrada);
const ResultadoExecucao rb = executar(b, entrada);
if (ra.emissoes.size() != rb.emissoes.size()) {
r.equivalentes = false;
r.divergencia = "entrada \"" + entrada + "\": " +
std::to_string(ra.emissoes.size()) +
" emissoes antes, " +
std::to_string(rb.emissoes.size()) + " depois";
return r;
}
for (std::size_t i = 0; i < ra.emissoes.size(); ++i) {
++r.emissoesComparadas;
const Emissao& ea = ra.emissoes[i];
const Emissao& eb = rb.emissoes[i];
// Rótulo, valor E posição. Comparar só o valor deixaria passar uma
// transformação que reordena emissões ou desloca o casamento.
if (ea.rotulo != eb.rotulo || ea.valor != eb.valor ||
ea.posicao != eb.posicao) {
r.equivalentes = false;
r.divergencia = "entrada \"" + entrada + "\", emissao " +
std::to_string(i) + ": (" + ea.rotulo + ", " +
ea.valor + ", " + std::to_string(ea.posicao) +
") contra (" + eb.rotulo + ", " + eb.valor +
", " + std::to_string(eb.posicao) + ")";
return r;
}
}
}
return r;
}
} // namespace peneira
A checagem que mais rende é a do balanço da pilha, e ela é possível por uma propriedade do código gerado: todo desvio salta para a frente, então o fluxo é acíclico e uma varredura em profundidade com marcação termina cobrindo tudo. A exigência é mais forte que “a pilha nunca fica negativa”: exige-se que a altura em cada instrução seja propriedade do ponto e não do caminho. Se dois caminhos chegam à mesma instrução com alturas diferentes, o objeto é malformado — mesmo que nenhuma entrada exercite os dois.
A execução sobre o corpus inclui as entradas degeneradas de propósito:
"valores: 7 250 1200 480 -3 99 101"
grande = 250 / 1200 / 480 / 101 7 casamentos, 0 erros
"nada aqui"
(nenhuma emissao) 0 casamentos, 0 erros
"0 100 101 499 500 501"
grande = 101 / 499 / 500 / 501 6 casamentos, 0 erros
""
(nenhuma emissao) 0 casamentos, 0 errosA entrada vazia e a que não casa com nada estão ali porque são onde um executor mal terminado trava ou acusa erro sem motivo. Conferi a terceira à mão: dos seis números, saem os quatro estritamente maiores que cem — o cem não sai, e é o caso de fronteira que distingue o maior do maior ou igual.
E o relatório de fases, que desde o primeiro capítulo listava etapas pendentes, fecha assim:
fases do compilador:
analise lexica pronta
analise sintatica pronta
analise semantica pronta
geracao de codigo pronta
otimizacao pronta
execucao prontaUm objeto que não passa na validação não é gravado, e o compilador sai com erro. Gravar um objeto que sabemos malformado seria produzir um artefato que só falha adiante, na mão de quem for executá-lo.
O arquivo objeto final tem duas mil oitocentas e dezesseis células de transição e onze instruções. A maior parte do programa objeto, em bytes, são os autômatos — o que é a última evidência do argumento que atravessa o livro: nesta linguagem, a teoria de autômatos não é infraestrutura escondida do compilador, é o produto que ele entrega.
1.8 Retrospectiva e 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]
Olhe o diagrama e repare na propriedade que não é óbvia enquanto se está no meio do caminho: as peças teóricas não foram consumidas pelo compilador, elas ficaram no produto. O autômato determinístico minimizado que construímos como exercício de teoria de linguagens formais está gravado, como tabela de transição, no arquivo objeto — e a maior parte desse arquivo, em bytes, são os autômatos. A diferença entre autômatos, vista como propriedade de fechamento das linguagens regulares, é o que decide o sistema de tipos; e o casamento mais longo, visto como regra de desempate do analisador léxico, é o laço principal do executor. Se você reconhece o mesmo módulo de autômatos trabalhando nas duas pontas, a aposta do curso se pagou.
Prefiro delimitar as ausências a deixar impressão de cobertura completa. A otimização global ficou no panorama, com as análises enunciadas e nenhuma transformação global implementada. O tratamento de laços não apareceu, porque a nossa linguagem não tem laços — e é por isso que o fluxo é acíclico e a validação termina sem ponto fixo. A alocação de registradores apareceu em versão reduzida, porque a máquina de destino é de pilha, e a compilação separada não foi tratada, porque o nosso objeto é autocontido. Três direções continuam daqui: a compilação sob demanda durante a execução, as infraestruturas organizadas em torno de uma representação intermediária comum, e o projeto de linguagens de domínio específico — a aplicação mais provável do que você aprendeu.
Recapitulando: a otimização opera sobre blocos básicos e grafo de fluxo, e essa construção troca perguntas indecidíveis sobre execuções por perguntas decidíveis sobre caminhos de um grafo finito. As transformações locais vieram cada uma com a sua condição, porque a condição é o que separa otimização de defeito. Dois resultados merecem ficar: 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 entrega evidência e não prova.
Encerro com a herança do percurso, e não é uma técnica. Nenhum dos defeitos mais sérios do artefato de referência foi encontrado por revisão nem por teste. Um apareceu quando uma peça passou a ser usada de verdade, no lugar da versão provisória. Outro, porque a mesma grandeza era calculada por dois caminhos independentes e os dois discordaram. O terceiro, porque uma invariante escrita para outro fim continuou ligada. Construir de verdade, medir por dois caminhos e manter as invariantes ligadas: é isso que sobrevive à obsolescência de qualquer técnica que este curso apresentou.