flowchart LR
A["texto-fonte"] --> B["análise<br/>tokens, árvore, tipos"]
B --> C["representação intermediária<br/>vive na memória do processo"]
C --> D["gerador de código"]
D --> E["programa objeto<br/>arquivo que sobrevive ao processo"]
E --> F["executor"]
F --> G["efeito observável<br/>sobre a entrada real"]
C -. "até aqui, tudo morria<br/>com o fim do processo" .-> C
1 Módulo 14: Geração de Código
Bem-vindo ao módulo em que aparece um arquivo. Até agora, tudo o que o seu compilador produziu morreu junto com o processo. Aqui ele passa a escrever algo que sobrevive, que você copia para outra máquina e executa semana que vem. É também o módulo em que a natureza do trabalho muda: pela primeira vez não existe a resposta certa, existem muitas respostas corretas, e a tarefa é escolher uma boa.
1.1 O problema: um verificador caríssimo
Imagina a cena. Você roda o seu compilador sobre um programa: ele analisa o texto, monta a árvore, confere os tipos, gera a representação intermediária com temporários e desvios — e termina. O processo devolve a memória ao sistema operacional e não deixa rastro. O que você tem em mãos é um programa que sabe dizer “está bem formado” e nada mais. Um verificador caríssimo.
Aviso de mudança de tom. Na metade de análise, as perguntas tinham resposta única e havia critério objetivo separando certo de errado. Aqui não há: dada uma representação intermediária, infinitas sequências de instruções produzem o efeito correto. Por isso o que vem a seguir trata de compromissos, e não de teoremas.
Este capítulo é o que mais depende do anterior em todo o livro, e quero ser explícito sobre o que ele pressupõe, porque a lacuna, se houver, custa caro aqui.
Pressuponho que você tenha em mãos uma representação intermediária linear, no estilo do código de três endereços, com temporários, desvios condicionais e incondicionais, e com as listas de desvios pendentes já preenchidas para os operadores lógicos — o mecanismo que construímos ao tratar de representações intermediárias. Pressuponho também uma especificação escrita do formato do programa objeto e do modelo de execução: quais seções o arquivo tem, o que cada campo significa, e o que o executor faz a cada passo. Se essa especificação não existir, ou existir apenas na sua cabeça, a leitura deste capítulo funciona, mas a implementação não: sem ela, o executor acaba escrito contra o gerador, e o capítulo inteiro argumenta contra isso.
Do primeiro bloco do livro, pressuponho o caminho completo da expressão regular ao autômato finito determinístico mínimo — notação, árvore, construção de Thompson, determinização por subconjuntos e minimização por refinamento de partições —, porque a Seção 8 volta a esse material e o trata como dado a ser gravado em um arquivo, e não mais como algoritmo a ser executado. Pressuponho ainda o vocabulário de grafos: vértice, aresta, grau, coloração própria e percurso, que é o que a Seção 7 usa sem reapresentar.
O que não pressuponho é qualquer familiaridade com arquiteturas de processadores reais, com conjuntos de instruções concretos ou com formatos de arquivo objeto de sistemas operacionais em uso. Tudo o que este capítulo precisa dessas coisas é construído aqui, em uma máquina abstrata pequena o bastante para caber inteira em uma página.
1.2 Escolher, não decidir
Um gerador de código é uma função G que leva cada representação intermediária bem formada r a uma sequência de instruções da máquina, de modo que executar G(r) sobre uma entrada produza o mesmo resultado que a semântica atribui a r sobre ela. É a igualdade de significados do primeiro módulo, aplicada ao último trecho da cadeia.
O que é novo é que essa condição não determina G: dá sempre para acrescentar instruções sem efeito observável, reordenar operações independentes, chegar ao mesmo lugar por outro caminho. E aí, uma boa sob qual critério? Pode ser o tempo de execução, o tamanho do código, o consumo de energia ou a previsibilidade do tempo de resposta — e neste último caso uma transformação que reduz o tempo médio e piora o pior caso é uma piora.
Pare e pense. Alguém diz que o compilador A gera código melhor que o B. Que pergunta você faz antes de acreditar?
O problema se decompõe em três subproblemas. A seleção de instruções decide quais instruções realizam cada operação da representação. Parece consulta a tabela, e é isso quando o conjunto é pequeno e regular; deixa de ser trivial quando a máquina oferece mais de uma forma de fazer a mesma coisa, com custos diferentes, e algumas delas cobrem várias operações de uma vez. Quando a representação tem forma de árvore, esse ladrilhamento de custo mínimo tem solução ótima por programação dinâmica em tempo linear, resultado de Alfred Aho e Stephen Johnson publicado em 1976 — um dos pouquíssimos lugares da área em que há algoritmo ótimo e não heurística, porque a árvore impede que a escolha numa subárvore afete a outra.
A alocação de registradores decorre de um fato bruto: a máquina tem poucos registradores e o programa produz um número ilimitado de valores intermediários. Quando eles não bastam, algum valor vai para a memória — é o derramamento, uma derrota localizada, porque o código continua correto e fica mais lento.
A ordenação da avaliação é a mais sutil: ordens diferentes de avaliar subexpressões independentes produzem números diferentes de valores vivos ao mesmo tempo, porque, ao somar dois produtos, o primeiro calculado ocupa espaço durante todo o cálculo do segundo. Ravi Sethi e Jeffrey Ullman resolveram isso exatamente para árvores, em 1970: rotule cada folha com 1 e cada nó com o máximo dos rótulos dos filhos quando diferem, ou com esse valor mais um quando são iguais; o rótulo da raiz é o número mínimo de registradores, atingido avaliando sempre primeiro a subárvore de maior rótulo. As hipóteses delimitam tudo — precisa ser árvore de verdade, e os operadores precisam ser livres de efeito colateral.
flowchart LR
S["seleção de instruções<br/>quais instruções cobrem<br/>cada operação"]
A["alocação de registradores<br/>quais valores moram<br/>em registrador"]
O["ordenação da avaliação<br/>em que ordem avaliar<br/>subexpressões independentes"]
S -- "instruções escolhidas mudam<br/>os tempos de vida" --> A
A -- "registradores disponíveis mudam<br/>o que compensa selecionar" --> S
O -- "a ordem decide quem<br/>está vivo ao mesmo tempo" --> A
A -- "a pressão sobre registradores<br/>sugere outra ordem" --> O
S -- "cada instrução consome<br/>uma quantidade diferente" --> O
Agora o incômodo: os três se mordem a cauda. A melhor seleção depende de quantos registradores há, a alocação depende da ordem de avaliação, e a melhor ordem depende de quais instruções foram selecionadas. Formulado como problema único, o conjunto é intratável — ele contém a coloração de grafos como caso particular. A prática decompõe e aceita o subótimo, decisão consciente que troca otimalidade por tratabilidade e por modularidade, porque três componentes separados se testam e se substituem, e um bloco monolítico não se depura.
A ordem de prioridades é contraintuitiva. Primeiro correção, inegociável; segundo previsibilidade, porque um gerador fácil de descrever produz código conferível por inspeção; só em terceiro a qualidade do código gerado. Inverter essa ordem é a forma mais comum de terminar o semestre com um gerador sofisticado que não funciona.
1.3 Pilha ou registradores: onde mora a dificuldade
Escolher o modelo de máquina não elimina dificuldade — redistribui.
O estado é o contador de instruções, uma pilha de avaliação e a memória. As instruções aritméticas e lógicas não nomeiam operandos: retiram do topo o que consomem e depositam no topo o que produzem. O gerador não decide onde pôr nada, porque a posição faz o trabalho do nome.
O estado inclui um conjunto finito e nomeado de posições rápidas, e cada instrução diz de onde lê e onde escreve. Executa menos instruções, porque não gasta nenhuma movendo valores para dentro e para fora de uma pilha, e em troca transfere ao gerador a decisão de qual valor mora em qual registrador.
flowchart TB
E["mesma operação:<br/>somar dois valores"]
E --> P["máquina de pilha"]
E --> R["máquina de registradores"]
P --> P1["carrega primeiro valor"]
P1 --> P2["carrega segundo valor"]
P2 --> P3["soma<br/>sem nomear nada"]
P3 --> PC["gerador simples<br/>executor simples<br/>mais instruções executadas"]
R --> R1["soma r1 e r2<br/>e escreve em r3"]
R1 --> RC["menos instruções<br/>gerador carrega a<br/>alocação de registradores"]
| Aspecto | Máquina de pilha | Máquina de registradores |
|---|---|---|
| Operandos das operações | implícitos, no topo | nomeados na instrução |
| Alocação de registradores | não existe | é o subproblema dominante |
| Ordenação da avaliação | fixada pela pós-ordem | há liberdade a explorar |
| Tamanho do código | menor | maior |
| Instruções executadas | mais | menos |
| Dificuldade do gerador | baixa | alta |
| Verificação estática | direta, pela altura da pilha | mais trabalhosa |
Leia a tabela como redistribuição, não como classificação de qualidade: a dificuldade total é aproximadamente constante, o que muda é onde ela mora. E note o que costuma passar batido: código de três endereços é código para uma máquina de registradores ilimitados, com cada temporário no papel de registrador virtual. A alocação é o mapeamento desse conjunto no conjunto finito da máquina real — e não existe quando o destino é uma pilha, porque não há nomes nos quais mapear.
Prefira a pilha quando o destino for uma máquina virtual que você mesmo escreverá, quando a portabilidade importar mais que o desempenho bruto, quando o código precisar ser verificado antes de executar, ou quando as expressões forem rasas — esta última condição é a mais esquecida e é decisiva, porque se as expressões nunca passam de dois ou três níveis, a pilha nunca fica funda e a simplicidade do gerador é ganho puro. Prefira registradores quando o destino for processador real e o desempenho for dominante. E note o que a escolha não decide: a representação intermediária. Usar três endereços e gerar para pilha é coerente, e é o que faremos.
1.4 Projetar o conjunto de instruções
Aqui você deixa de ser usuário de um conjunto de instruções e passa a ser projetista de um — e entender por que uma instrução existe é diferente de saber usá-la.
flowchart TB
I["instrução"] --> C["código de operação"]
I --> A["argumento<br/>sempre um índice inteiro"]
I --> D["declaração do efeito"]
D --> D1["quantos valores consome"]
D --> D2["quantos valores deposita"]
D --> D3["que faz com o<br/>contador de instruções"]
D1 --> H["efeito de pilha<br/>depositados menos consumidos"]
D2 --> H
H --> V["altura conhecida<br/>sem executar nada"]
V --> V1["profundidade máxima reservada<br/>antes de começar"]
V --> V2["programa cuja pilha<br/>não fecha é rejeitado"]
Uma instrução é caracterizada por um código de operação, um argumento opcional e — a parte que quase todo mundo omite — a declaração do seu efeito: quantos valores consome, quantos deposita, o que faz com o contador e com a memória. É essa terceira componente que transforma o conjunto em especificação, em vez de lista de nomes. Instrução com efeito não declarado é instrução sobre a qual duas pessoas discordam de boa-fé, e discordância entre quem gera e quem executa é o defeito mais caro desta altura do projeto: cada lado testa contra a própria interpretação e os dois passam.
Declare por escrito qual operando sai primeiro da pilha. O segundo foi empilhado por último e sai primeiro. Numa soma ou numa multiplicação, trocar a ordem não altera nada e o erro passa despercebido. Numa subtração, numa divisão ou numa comparação de ordem, o resultado sai errado — e só nos casos assimétricos, o que significa que metade dos testes ingênuos continua passando alegremente.
Do efeito declarado sai uma verificação barata. O efeito de pilha de uma instrução é a diferença entre o que ela deposita e o que consome, e sobre código linear a altura em cada ponto é a soma desses efeitos, conhecida estaticamente. Com desvios, a altura continua bem definida desde que todos os caminhos que chegam a um ponto o deixem na mesma altura — e o que importa aí não é a demonstração, que é indução imediata, e sim o requisito de projeto: faça todo desvio saltar um trecho cujo efeito líquido seja igual ao do caminho alternativo, e ganha de graça a profundidade máxima a reservar e a rejeição de qualquer objeto cuja pilha não fecha.
Três decisões de formato fecham a seção. Tamanho fixo das instruções desperdiça alguns bytes e compra um executor mais simples, a impossibilidade estrutural de um desvio cair no meio de uma instrução, e a indexação do código como vetor. Granularidade: cubra cada operação da representação sem duplicar nenhuma, e resista à tentação de instruções especializadas sem evidência de que se pagam; instruções de forma idêntica merecem virar família — das quinze da nossa máquina, seis são de comparação, igualdade, desigualdade e as quatro de ordem, e viram um caso único no executor parametrizado pela variante. E a área de constantes: um vetor de literais gravado uma vez e referenciado por índice, que além de acomodar textos longos uniformiza a decodificação.
O teste do implementador independente
A sua especificação está completa quando outra pessoa, lendo apenas ela, consegue escrever um executor compatível. Comportamento que só se descobre lendo o seu código não está especificado — está implementado, que é coisa diferente. E é isso que permite escrever o executor contra a especificação, como segunda implementação independente: escrito contra o gerador, ele concorda com os defeitos do gerador e todos os testes passam.
1.5 Emitir por pós-ordem, e a invariante que sustenta tudo
Com a máquina projetada, o gerador fica curto. O percurso em pós-ordem visita, para cada nó interno, todos os filhos da esquerda para a direita e só então o próprio nó.
flowchart TB
S["subtração<br/>visitada em 7º"] --> M["produto<br/>visitado em 3º"]
S --> D["soma<br/>visitada em 6º"]
M --> F1["valor<br/>1º"]
M --> F2["valor<br/>2º"]
D --> F3["valor<br/>4º"]
D --> F4["valor<br/>5º"]
Se o gerador emite, para cada nó visitado nessa ordem, a carga do valor (folhas) ou a instrução da operação (nós internos), a execução deixa na pilha exatamente um valor, igual ao da expressão. A demonstração é indução sobre a altura: cada subsequência deixa um valor e não perturba o que está abaixo, de modo que os operandos estão todos lá quando a instrução da raiz executa. Acompanhe o diagrama: carregar, carregar, multiplicar, carregar, carregar, somar, subtrair — sete instruções, e a altura percorre um, dois, um, dois, três, dois, um. O pico de três acontece quando o produto espera enquanto a soma é calculada, que é o fenômeno que a numeração de Sethi e Ullman quantifica.
A pós-ordem não é escolha estética: a instrução da operação exige os operandos já empilhados, e emiti-la antes deles produziria uma instrução consumindo de uma pilha vazia. É a única ordem possível, e é consequência do modelo.
Agora a propriedade silenciosa da qual tudo depende. Uma sequência satisfaz a invariante de leitura única quando cada valor depositado é consumido por exatamente uma instrução posterior. A razão é elementar: numa máquina de pilha, ler é desempilhar, e um valor lido some. Se duas instruções pretenderem ler o mesmo valor, a segunda encontra a pilha já consumida e lê o que estiver abaixo — outro valor, do tamanho certo e possivelmente do tipo certo, e portanto um erro que não se anuncia.
Pare e pense. Código de três endereços permite definir um temporário uma vez e lê-lo duas — é assim que se reaproveita um resultado calculado. O que acontece com a tradução direta para pilha nesse caso, e por que os seus testes de soma e de igualdade continuariam passando?
Ou você constrói a representação de modo que satisfaça a invariante, recalculando o valor a cada uso, ou acrescenta à máquina uma instrução de duplicação do topo. Escolhida qualquer das duas, faça a terceira coisa: verifique a invariante em código, contando as leituras de cada temporário e recusando a geração quando alguma passar de um. Garantias “por construção” são justamente as que se perdem em manutenção. E cuidado ao implementar a contagem: varrer todos os campos de operando conta como temporário coisas que não são, como literais e índices.
1.6 Curto-circuito: quando gerar deixa de ser traduzir
Chegamos ao ponto tecnicamente mais difícil do módulo. Até aqui a geração foi tradução direta; agora o gerador passa a construir estrutura de controle que não corresponde a nada visível no fonte.
Um operador lógico é avaliado com curto-circuito quando o operando direito só é avaliado nos casos em que o esquerdo não decide sozinho. Primeira coisa a desentortar: curto-circuito não é otimização. Ele altera o comportamento observável de programas cujo operando direito tem efeito colateral ou pode falhar — um programa que testa se um índice é válido e, na conjunção, acessa a posição funciona sob curto-circuito e falha sob avaliação ansiosa. Os dois esquemas não são duas implementações da mesma linguagem: são duas linguagens diferentes, e a escolha pertence à especificação, não ao gerador.
A dificuldade técnica vem do modelo de máquina. Suponha uma instrução de conjunção que consome dois valores lógicos e deposita a conjunção. Para executá-la, os dois precisam estar na pilha; para estarem na pilha, as duas subexpressões precisam ter sido avaliadas. Logo, ela implementa necessariamente avaliação ansiosa. Curto-circuito não é operação sobre valores: é fluxo de controle, e se exprime com desvios condicionais.
flowchart TB
A["código do operando esquerdo"] --> B{"resultado"}
B -- "falso" --> F["destino da lista de falso<br/>preenchido depois"]
B -- "verdadeiro" --> C["código do operando direito<br/>começa aqui"]
C --> E{"resultado"}
E -- "falso" --> F
E -- "verdadeiro" --> G["corpo da regra"]
F -. "as duas listas de falso<br/>foram unidas" .-> F
O esquema consagrado inverte a perspectiva: em vez de traduzir a expressão lógica para código que calcula verdadeiro ou falso, traduz-se para código que desvia para um lugar quando ela é verdadeira e para outro quando é falsa. Junto com o código, o gerador devolve dois conjuntos de desvios com destino em branco: a lista de verdadeiro e a lista de falso. Numa comparação simples, emitem-se os operandos, a comparação e um desvio condicional em branco, que entra na lista de falso. Numa conjunção, traduz-se o esquerdo, preenche-se a sua lista de verdadeiro com a posição em que o direito começa, traduz-se o direito, e devolve-se como lista de falso a união das duas — lido em português, é a semântica: se o esquerdo for verdadeiro, siga para o direito; se qualquer um for falso, o destino é o mesmo. Na disjunção o esquema é simétrico, com as listas trocando de papel, e o aninhamento não exige nada de novo, porque as listas são a interface entre os níveis.
Falta preencher as listas. Quando o gerador emite um desvio para a frente, o endereço do destino não é difícil de calcular: é inexistente. Ou se gera em duas passagens, ou se emite o desvio em branco, guarda-se a posição e volta-se a preenchê-la depois — o preenchimento retroativo. Uma referência pendente jamais preenchida é defeito grave e silencioso: o programa desvia para um lugar arbitrário na primeira execução que passar por ali.
1.7 Referências pendentes e o mapa de endereços
O problema do desvio para a frente é mais geral que o curto-circuito. Uma referência pendente é qualquer campo de instrução já emitida cujo valor correto ainda não se conhece — destinos de desvio, endereços de dados não alocados, nomes definidos em outra unidade de compilação.
flowchart LR
subgraph P1["primeira passagem: emitir"]
A["percorre a representação"] --> B["registra em que endereço<br/>do objeto cada instrução começou"]
B --> C["emite o desvio com<br/>destino em branco"]
end
subgraph P2["segunda passagem: preencher"]
D["percorre os desvios emitidos"] --> E["consulta o mapa"]
E --> F["substitui o índice da representação<br/>pelo endereço do objeto"]
end
C --> D
B -. "o mapa tem um elemento a mais:<br/>logo depois da última é<br/>destino legítimo" .-> E
O caso mais frequente é este: os desvios da representação apontam para índices da representação, e o objeto precisa de índices do objeto. A solução é um mapa preenchido durante a emissão e consultado numa segunda passagem, que substitui cada destino intermediário pelo endereço correspondente do objeto. Não tente corrigir na mesma passagem que emite: a única forma seria voltar atrás depois, que já é a segunda passagem, escrita pior.
Dois detalhes do mapa produzem defeitos reais quando esquecidos. Ele precisa ter um elemento a mais que o número de instruções da representação, porque “logo depois da última” é destino legítimo — é para lá que aponta o desvio de uma condição falsa cujo corpo termina no fim do trecho. E nem toda instrução da representação produz uma do objeto: uma operação de rótulo não emite nada, e ali o contador da representação avança enquanto o do objeto não.
Coincidência não é invariante. É comum a correspondência sair um para um e o mapa acabar sendo a identidade, e é natural concluir dali que ele é desnecessário — errado de um jeito que não se manifesta. Uma operação de rótulo já quebra a identidade; uma instrução futura traduzida por duas de máquina também. Quando quebrar, não haverá mensagem de erro: haverá um desvio para a instrução errada.
1.8 Alocação de registradores como coloração
Este subproblema some quando o destino é uma máquina de pilha, e ainda assim vale estudá-lo: a redução a coloração de grafo é um dos exemplos mais limpos de modelagem em construção de compiladores, e qualquer geração para hardware real passa por aqui.
A faixa de vida de um temporário vai da instrução que o define até a última que o lê, e o intervalo é semiaberto, com o extremo direito excluído. Não é convenção arbitrária: um valor morre na instrução que o lê pela última vez, e depois que ela executou o registrador está livre, inclusive para receber o valor que essa mesma instrução acabou de produzir. Dois temporários interferem quando suas faixas se sobrepõem, e o grafo de interferência tem os temporários como vértices e a interferência como arestas.
flowchart LR
T0["t0<br/>vive de 0 a 1"] --- T1["t1<br/>vive de 1 a 3"]
T1 --- T2["t2<br/>vive de 2 a 3"]
T3["t3<br/>vive de 3 a 4"]
T0 -.- L1["cor 0"]
T2 -.- L2["cor 1"]
T3 -.- L1
A redução é exata: uma atribuição de registradores é válida se e somente se é uma coloração própria do grafo de interferência, e o número mínimo de registradores é o número cromático. A demonstração é a leitura das definições nos dois sentidos — “temporários que interferem recebem registradores diferentes” e “vértices adjacentes recebem cores diferentes” são a mesma condição, com vocabulário trocado. É por isso que gosto deste exemplo: modelar bem é achar um problema matemático que é o mesmo problema, não um parecido. O primeiro alocador construído sobre essa correspondência deve-se a Gregory Chaitin e colaboradores, na IBM, no início dos anos 1980.
A má notícia vem junto: decidir se um grafo admite coloração com k cores é NP-completo para todo k \ge 3, e o problema está na lista clássica de Richard Karp, de 1972. Como a redução é exata, a alocação ótima herda a dificuldade — compiladores reais usam heurística porque a alternativa é intratável. A heurística fundadora é a simplificação: enquanto houver vértice de grau menor que k, remova-o e empilhe-o, porque quem tem menos de k vizinhos sempre acha cor livre na reinserção; esvaziado o grafo, desempilhe atribuindo a menor cor não usada pelos vizinhos. Se os restantes tiverem grau alto demais, escolhe-se um para derramar.
O erro clássico, e por que ele é perigoso. Tratar as faixas de vida como intervalos fechados faz o resultado de uma instrução interferir com os operandos que ela acabou de matar, e o alocador conclui que precisa de mais registradores do que precisa. O código sai correto e desnecessariamente conservador: nenhum teste acusa, o compilador não reclama, e o número devolvido é plausível — três registradores para uma expressão de profundidade dois não tem cara de defeito. Defeitos que produzem números implausíveis se denunciam sozinhos; os que produzem números plausíveis moram no código por anos.
Uma boa notícia para fechar. Dentro de um trecho linear, cada faixa de vida é um intervalo da reta e o grafo de interferência é um grafo de intervalos, classe para a qual a coloração ótima sai por um algoritmo guloso; a dificuldade geral vem da alocação entre blocos, quando o fluxo de controle espalha as faixas. Isso explica a coincidência entre o número de cores e a altura máxima da pilha: com temporários lidos uma única vez e código linear, o número de valores vivos num ponto é a altura da pilha ali. As duas máquinas precisam do mesmo espaço de trabalho; o que difere é quem o endereça.
1.9 O objeto como artefato: quando os autômatos viram produto
Um programa objeto tem seções de código, com instruções, e seções de dados, com valores determinados em tempo de compilação que o programa consultará durante a execução. É na seção de dados que mora a novidade deste módulo.
flowchart TB
O["programa objeto"] --> D["seção de dados"]
O --> C["seção de código"]
D --> D1["área de constantes<br/>literais referenciados por índice"]
D --> D2["tabelas de transição dos autômatos<br/>determinísticos mínimos"]
D --> D3["propriedades apuradas<br/>na análise semântica"]
C --> C1["instruções de tamanho fixo<br/>código e argumento"]
D2 -. "milhares de células" .-> M["a maior parte do arquivo,<br/>em bytes, é autômato"]
C1 -. "algumas dezenas" .-> M
Considere uma linguagem cujo domínio seja o reconhecimento de padrões em texto. Compilar um programa dela envolve converter cada padrão declarado num reconhecedor, e um reconhecedor é um autômato finito determinístico — construído pelo caminho dos primeiros módulos: da notação para a árvore, da árvore para o autômato não determinístico pela construção de Thompson, deste para o determinístico por subconjuntos, e deste para o mínimo por refinamento de partições. O que o gerador faz com esses autômatos? Ele os serializa na seção de dados: a tabela de transição de cada um vira um vetor de números gravado no arquivo, e o executor a consulta uma vez por caractere da entrada.
Lá atrás, os autômatos eram mecanismo interno do analisador léxico, invisível no resultado; aqui aparecem do outro lado, executados pelo programa que o compilador produziu. Não é analogia — é o mesmo objeto matemático, com a mesma tabela de transição, reaparecendo como produto. E há um detalhe quantitativo que inverte a intuição: um autômato com poucas dezenas de estados sobre um alfabeto de bytes ocupa milhares de células, enquanto as instruções que implementam as regras são algumas dezenas. A maior parte do arquivo, em bytes, é autômato.
Duas decisões de formato merecem nota. Dentro do compilador, a função de transição é convenientemente esparsa, porque o autômato é construído e transformado repetidamente; no objeto, a decisão se inverte para matriz densa, mesmo com quase todas as células vazias, porque ali ele não é mais transformado, apenas consultado, no laço mais interno do executor. A representação deve seguir o papel que a estrutura desempenha, não a sua natureza matemática. A segunda decisão é gravar o objeto em forma textual: a binária é menor, mas a textual pode ser lida, e conferir à mão se a tabela tem os estados esperados encontra o que nenhum teste automático encontraria, porque o teste verifica o que alguém pensou em verificar e a leitura vê o que está lá.
1.10 O caso conduzido
Antes de olhar o código, fixe o que procurar nele. Procure onde os três subproblemas aparecem e onde eles somem, e por quê. Procure a tabela de seleção, que deve ser curta, o mapa de endereços e a segunda passagem. Procure a verificação da invariante de leitura única, que existe apesar de a invariante ser garantida por construção. E procure a comparação entre o número de cores e a altura máxima da pilha.
1.10.1 9.1 A máquina de destino da Peneira
A linguagem que este livro constrói compila para uma máquina de pilha, e vale reconstruir o argumento da Seção 2.4 aplicado a ela, porque a decisão não é automática.
As expressões da Peneira são rasas. Uma condição típica é uma comparação, eventualmente duas ligadas por um conectivo lógico; não há chamadas de função, não há aritmética composta, não há aninhamento profundo. Sob a Seção 2.4, essa é exatamente a situação em que a máquina de pilha ganha: a pilha nunca fica funda, o custo de empilhar e desempilhar é pequeno em termos absolutos, e a simplicidade do gerador é ganho puro. Numa linguagem com expressões profundas a conta se inverteria, e registro isso porque a escolha certa aqui é a errada em outro projeto.
O conjunto de instruções tem quinze códigos de operação, dos quais seis formam a família das comparações — igualdade, desigualdade e as quatro de ordem —, tratadas como família pela razão da Seção 3.4: elas têm forma idêntica e um único caso no executor, parametrizado pela variante. As demais empilham uma constante da área de constantes, empilham o texto reconhecido pela ligação corrente, convertem texto em número, combinam valores lógicos de forma ansiosa, desviam condicional ou incondicionalmente, emitem um resultado rotulado e encerram a regra.
Duas observações sobre esse conjunto, ambas de decisões que preferi registrar a silenciar.
A primeira é que as duas instruções de desvio foram acréscimo deliberado ao desenho original da máquina. O desenho inicial listava conjunção e disjunção como instruções, o que, pela Seção 5.2, implica avaliação ansiosa e torna o curto-circuito inexprimível. Mantive as duas no conjunto — elas continuam válidas, e são o que um gerador ansioso emitiria — e acrescentei os desvios, que são o que o nosso gerador de fato usa. Um executor compatível precisa implementar todas.
A segunda é que toda instrução ocupa dois campos, código e argumento, mesmo quando o argumento não é usado. É a decisão de tamanho fixo da Seção 3.3, com as três consequências que discuti ali: avançar é somar uma constante, um desvio nunca cai no meio de uma instrução, e o código é indexável como vetor.
1.10.2 9.2 A seleção de instruções, e os dois subproblemas que somem
Os três subproblemas da Seção 1 estão todos presentes neste compilador, e dois deles desaparecem — não por esperteza, mas como consequência de decisões já tomadas.
A ordenação da avaliação foi resolvida no capítulo anterior: o código de três endereços é linear, e a ordem de avaliação está na sequência das instruções. Não há nada a ordenar aqui. A alocação de registradores não existe, porque a máquina de pilha não tem registradores — o operando fica no topo, e o topo é implícito.
Sobra a seleção, que aqui é quase uma tabela: cada operação da representação intermediária tem uma instrução correspondente.
14_codegen.h
#ifndef PENEIRA_14_CODEGEN_H
#define PENEIRA_14_CODEGEN_H
#include <cstddef>
#include <string>
#include <vector>
#include "10_ast.h"
#include "12_sema.h"
#include "13_objeto.h"
#include "13_ri.h"
namespace peneira {
// GERAÇÃO DE CÓDIGO: da representação intermediária para o programa objeto.
//
// Os três subproblemas clássicos da geração de código são seleção de
// instruções, alocação de registradores e ordenação da avaliação, e eles são
// interdependentes — a melhor seleção depende de quantos registradores
// sobraram, que depende da ordem escolhida, que depende de quais instruções
// foram selecionadas. Resolver os três juntos é intratável; a prática é
// decompor e aceitar o resultado subótimo.
//
// Nesta máquina de destino, dois dos três **desaparecem**, e vale saber por
// quê antes de ler o código:
//
// - A ORDENAÇÃO já foi decidida no módulo 13. O código de três endereços é
// linear: a ordem de avaliação está na sequência das instruções.
// - A ALOCAÇÃO DE REGISTRADORES não existe, porque a máquina é de pilha e
// não tem registradores. O operando fica no topo, e o topo é implícito.
//
// Sobra a SELEÇÃO, que aqui é quase uma tabela: cada operação da representação
// intermediária tem uma instrução correspondente. Essa simplicidade é o que se
// compra ao escolher máquina de pilha, e o preço está pago no módulo 13 — o
// preço é que o objeto executa mais instruções do que executaria numa máquina
// de registradores.
//
// Para não deixar a alocação de registradores como assunto puramente verbal,
// este módulo CALCULA o que ela custaria: monta o grafo de interferência dos
// temporários da representação intermediária e o colore. O número de cores é o
// número de registradores que uma máquina de registradores precisaria.
// ---------------------------------------------------------------------------
// Geração
// ---------------------------------------------------------------------------
struct RelatorioDeGeracao {
std::size_t regrasGeradas = 0;
std::size_t instrucoesEmitidas = 0;
std::size_t referenciasResolvidas = 0;
// Profundidade máxima da pilha de avaliação, calculada por simulação
// estática. O executor pode pré-alocar exatamente isto.
std::size_t profundidadeMaximaDaPilha = 0;
// Falha dura: um temporário lido mais de uma vez quebraria a disciplina de
// pilha (o valor é consumido ao ser lido). Ver `verificarUsoUnico`.
std::vector<std::string> violacoesDeUsoUnico;
};
// Gera o programa objeto completo a partir do resultado da análise semântica e
// da árvore verificada.
ProgramaObjeto gerarObjeto(const ResultadoSemantico& semantico,
const NoAst& raiz, RelatorioDeGeracao& relatorio);
// Traduz o código de uma regra. Exposta separadamente porque é o miolo do
// módulo e a demonstração a exercita isolada.
std::vector<Instrucao> gerarCodigoDaRegra(const CodigoRI& ri,
ProgramaObjeto& objeto,
RelatorioDeGeracao& relatorio);
// A disciplina de pilha só funciona se cada temporário for lido EXATAMENTE uma
// vez: ler é desempilhar, e um segundo leitor encontraria a pilha já consumida.
// A representação intermediária do módulo 13 satisfaz isso por construção — ela
// reemite o casamento a cada uso em vez de reaproveitar o temporário —, mas
// "por construção" é exatamente o tipo de garantia que se perde numa alteração
// futura. A verificação custa um percurso e transforma um defeito silencioso de
// execução em erro de compilação.
std::vector<std::string> verificarUsoUnico(const CodigoRI& ri);
// ---------------------------------------------------------------------------
// Alocação de registradores, calculada (tratamento conceitual, número real)
// ---------------------------------------------------------------------------
// A faixa de vida de um temporário: da instrução que o define à última que o
// lê. Dois temporários INTERFEREM quando as faixas se sobrepõem — eles não
// podem compartilhar registrador.
struct FaixaDeVida {
std::string temporario;
std::size_t definicao = 0;
std::size_t ultimoUso = 0;
};
struct GrafoDeInterferencia {
std::vector<FaixaDeVida> faixas;
// Matriz de adjacência achatada: interfere[i * n + j].
std::vector<std::uint8_t> interfere;
std::size_t n = 0;
bool haAresta(std::size_t i, std::size_t j) const;
};
GrafoDeInterferencia construirInterferencia(const CodigoRI& ri);
// Coloração gulosa: percorre os temporários e dá a cada um a menor cor que
// nenhum vizinho usa. Não é ótima em geral — colorir com o número mínimo de
// cores é problema difícil, e é por isso que compiladores reais usam heurística
// —, mas em grafos de intervalo como estes ela encontra o mínimo.
struct Coloracao {
std::vector<std::size_t> corDoTemporario;
std::size_t cores = 0;
};
Coloracao colorir(const GrafoDeInterferencia& g);
// Grava o objeto em disco, para inspeção. Devolve false e preenche `erro` em
// caso de falha.
bool gravarObjeto(const ProgramaObjeto& objeto, const std::string& caminho,
std::string& erro);
} // namespace peneira
#endif // PENEIRA_14_CODEGEN_H
A demonstração de seleção põe as duas formas lado a lado, com o código de três endereços à esquerda e o de pilha à direita, para a mesma regra:
tres enderecos (maquina de registradores infinitos) pilha
---------------------------------------------------- --------------------
0: t0 := casamento n 0: PUSH_MATCH 0
1: t1 := valor t0 1: VALUE
2: t2 := 100 2: PUSH_CONST 0
3: t3 := t1 > t2 3: CMP_GT
4: se_falso t3 desvia para 12 4: JUMP_IF_FALSE 12
5: t4 := casamento n 5: PUSH_MATCH 0
6: t5 := valor t4 6: VALUE
7: t6 := 500 7: PUSH_CONST 1
8: t7 := t5 < t6 8: CMP_LT
9: se_falso t7 desvia para 12 9: JUMP_IF_FALSE 12
10: t8 := casamento n 10: PUSH_MATCH 0
11: emite "faixa", t8 11: EMIT 2Repare no que a coluna da direita não tem: nomes. O código de três endereços é, como argumentei na Seção 2.2, código para uma máquina de registradores infinitos, e cada temporário é um registrador virtual. A máquina de pilha apaga todos eles e deixa a posição fazer o trabalho que o nome fazia.
A simplicidade dessa coluna foi comprada, e o preço está pago no capítulo anterior: o objeto executa mais instruções do que executaria numa máquina de registradores, porque empilhar e desempilhar são trabalho que o registrador nomeado dispensa. É exatamente a redistribuição da tabela da Seção 2.3, vista em um caso concreto.
Sobre a invariante de leitura única da Seção 4.3: a representação intermediária deste compilador a satisfaz por construção, porque ela reemite o casamento a cada uso em vez de reaproveitar o temporário — é por isso que a extração de valor aparece duas vezes na condição acima e gera dois empilhamentos do texto reconhecido. Mesmo assim, escrevi a verificação em código, pela razão que defendi naquela seção: “por construção” é precisamente o tipo de garantia que se perde numa alteração futura. A verificação percorre a representação contando leituras por temporário, e uma violação vira erro de compilação em vez de defeito silencioso de execução.
Registro a armadilha que a Seção 4.3 antecipa, porque eu a encontrei ao escrever: contar como leitura de temporário todo campo de operando produz nomes fantasmas, porque o campo de operando de uma constante é um literal e não um temporário. A verificação despacha por tipo de operação em vez de varrer os campos.
1.10.3 9.3 O mapa de endereços e a segunda passagem
O curto-circuito, neste compilador, já vem resolvido do capítulo anterior — as listas de desvios da Seção 5.3 foram preenchidas lá, e os desvios chegam aqui com destino definido. O que não vem resolvido é que aqueles destinos são índices da representação intermediária, e o objeto precisa de índices do objeto. É o problema da Seção 6.2, na sua forma exata.
14_codegen.cpp
#include "14_codegen.h"
#include <fstream>
#include <unordered_map>
namespace peneira {
namespace {
// Seleção de instruções: a tabela que mapeia operador de comparação da fonte
// para o código da máquina. É literalmente a "seleção de instruções" do
// módulo, e ela cabe numa função porque a máquina foi projetada para isso.
OpCode selecionarComparacao(const std::string& operador) noexcept {
if (operador == ">") return OpCode::CMP_GT;
if (operador == "<") return OpCode::CMP_LT;
if (operador == ">=") return OpCode::CMP_GE;
if (operador == "<=") return OpCode::CMP_LE;
if (operador == "==") return OpCode::CMP_EQ;
if (operador == "!=") return OpCode::CMP_NE;
return OpCode::CMP_EQ;
}
// Efeito de cada instrução sobre a altura da pilha. Serve para calcular a
// profundidade máxima por simulação estática, sem executar.
int efeitoNaPilha(OpCode op) noexcept {
switch (op) {
case OpCode::PUSH_CONST:
case OpCode::PUSH_MATCH:
return +1;
case OpCode::VALUE:
return 0; // desempilha um, empilha um
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:
return -1; // desempilha dois, empilha um
case OpCode::JUMP_IF_FALSE:
case OpCode::EMIT:
return -1;
case OpCode::JUMP:
case OpCode::HALT:
return 0;
}
return 0;
}
void colherAcoes(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) {
colherAcoes(*filho, saida);
}
}
}
} // namespace
std::vector<std::string> verificarUsoUnico(const CodigoRI& ri) {
std::unordered_map<std::string, std::size_t> leituras;
for (const InstrucaoRI& ins : ri.instrucoes) {
// Os campos que CONTÊM leitura de temporário variam por operação, e
// listá-los explicitamente é mais seguro que varrer todos os campos:
// `arg1` de uma constante é um literal, não um temporário.
switch (ins.op) {
case OpRI::Valor:
++leituras[ins.arg1];
break;
case OpRI::Comparacao:
++leituras[ins.arg1];
++leituras[ins.arg2];
break;
case OpRI::DesvioSeFalso:
++leituras[ins.arg1];
break;
case OpRI::Emite:
++leituras[ins.arg2];
break;
default:
break;
}
}
std::vector<std::string> violacoes;
for (const InstrucaoRI& ins : ri.instrucoes) {
const bool define = ins.op == OpRI::Constante ||
ins.op == OpRI::CasamentoDe ||
ins.op == OpRI::Valor ||
ins.op == OpRI::Comparacao;
if (!define) {
continue;
}
const auto it = leituras.find(ins.resultado);
const std::size_t vezes = it == leituras.end() ? 0 : it->second;
if (vezes > 1) {
violacoes.push_back(ins.resultado + " lido " +
std::to_string(vezes) + " vezes");
}
}
return violacoes;
}
std::vector<Instrucao> gerarCodigoDaRegra(const CodigoRI& ri,
ProgramaObjeto& objeto,
RelatorioDeGeracao& relatorio) {
std::vector<Instrucao> codigo;
// O mapa de endereços. A representação intermediária desvia para ÍNDICES
// DELA MESMA, e o objeto precisa desviar para índices DO OBJETO. Como uma
// instrução intermediária pode virar zero, uma ou várias instruções de
// máquina, os dois numeradores não coincidem em geral, e supor que
// coincidem é o erro que produz desvio para o meio de outra instrução.
//
// O mapa tem um elemento A MAIS que o número de instruções: o índice
// "logo depois da última" é destino legítimo — é para lá que apontam os
// desvios de condição falsa.
std::vector<std::size_t> enderecoDe(ri.instrucoes.size() + 1, 0);
for (std::size_t i = 0; i < ri.instrucoes.size(); ++i) {
enderecoDe[i] = codigo.size();
const InstrucaoRI& ins = ri.instrucoes[i];
switch (ins.op) {
case OpRI::Constante: {
// O literal vai para a área de constantes; a instrução carrega
// o índice. Reaproveitamento é automático: constante repetida
// ocupa uma entrada só.
std::string valor = ins.arg1;
if (valor.size() >= 2 && valor.front() == '"' &&
valor.back() == '"') {
valor = valor.substr(1, valor.size() - 2);
}
codigo.push_back(Instrucao{OpCode::PUSH_CONST,
objeto.adicionarConstante(valor)});
break;
}
case OpRI::CasamentoDe:
// Argumento 0: cada regra tem exatamente uma ligação nesta
// linguagem. O campo existe para o dia em que houver mais.
codigo.push_back(Instrucao{OpCode::PUSH_MATCH, 0});
break;
case OpRI::Valor:
codigo.push_back(Instrucao{OpCode::VALUE, 0});
break;
case OpRI::Comparacao:
codigo.push_back(
Instrucao{selecionarComparacao(ins.operador), 0});
break;
case OpRI::DesvioSeFalso:
// Destino ainda desconhecido em endereços de objeto: fica zero
// e é corrigido na passagem seguinte.
codigo.push_back(Instrucao{OpCode::JUMP_IF_FALSE, 0});
break;
case OpRI::Desvio:
codigo.push_back(Instrucao{OpCode::JUMP, 0});
break;
case OpRI::Emite: {
std::string rotulo = ins.arg1;
if (rotulo.size() >= 2 && rotulo.front() == '"' &&
rotulo.back() == '"') {
rotulo = rotulo.substr(1, rotulo.size() - 2);
}
codigo.push_back(Instrucao{OpCode::EMIT,
objeto.adicionarConstante(rotulo)});
break;
}
case OpRI::Rotulo:
// Não emite instrução nenhuma: o rótulo é posição, e a posição
// já está registrada no mapa. É o caso que torna o mapa
// necessário — aqui o numerador do objeto NÃO avança.
break;
}
}
enderecoDe[ri.instrucoes.size()] = codigo.size();
// Toda regra termina em HALT explícito. Poderia ser implícito — passar da
// última instrução encerra —, e deixar explícito custa um byte e elimina
// um caso especial do executor.
codigo.push_back(Instrucao{OpCode::HALT, 0});
// Segunda passagem: resolver as referências pendentes. Agora os dois
// numeradores são conhecidos, e a tradução de um para o outro é o mapa.
std::size_t resolvidas = 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;
}
if (ins.destino == kDestinoPendente ||
ins.destino > ri.instrucoes.size()) {
// Desvio sem destino chegou até aqui: é defeito do módulo 13, e
// gerar código a partir dele produziria objeto malformado.
continue;
}
codigo[enderecoDe[i]].argumento =
static_cast<std::uint32_t>(enderecoDe[ins.destino]);
++resolvidas;
}
relatorio.referenciasResolvidas += resolvidas;
// Profundidade máxima da pilha, por simulação estática. Percorrer
// linearmente é aproximação segura aqui porque todo desvio salta para a
// frente e os dois caminhos chegam com a mesma altura — propriedade que a
// tradução do módulo 13 garante e que uma tradução futura poderia quebrar.
int altura = 0;
int maximo = 0;
for (const Instrucao& ins : codigo) {
altura += efeitoNaPilha(ins.op);
if (altura > maximo) {
maximo = altura;
}
}
if (static_cast<std::size_t>(maximo) > relatorio.profundidadeMaximaDaPilha) {
relatorio.profundidadeMaximaDaPilha = static_cast<std::size_t>(maximo);
}
relatorio.instrucoesEmitidas += codigo.size();
return codigo;
}
ProgramaObjeto gerarObjeto(const ResultadoSemantico& semantico,
const NoAst& raiz, RelatorioDeGeracao& relatorio) {
ProgramaObjeto objeto;
// Seção 1: os autômatos. É aqui que o conteúdo do primeiro bloco do
// semestre entra, literalmente, dentro do arquivo gerado.
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));
}
// Seção 2: o código das regras.
std::vector<const NoAst*> acoes;
colherAcoes(raiz, acoes);
for (const NoAst* acao : acoes) {
TradutorRI tradutor;
const CodigoRI ri = tradutor.traduzirAcao(*acao);
const std::vector<std::string> violacoes = verificarUsoUnico(ri);
for (const std::string& v : violacoes) {
relatorio.violacoesDeUsoUnico.push_back(acao->texto + ": " + v);
}
RegraObjeto regra;
const auto it = indiceDoPadrao.find(acao->texto);
if (it == indiceDoPadrao.end()) {
// Padrão inexistente já foi reportado pela análise semântica; aqui
// a ação é simplesmente pulada, para não emitir objeto que
// referencia padrão que não existe.
continue;
}
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;
}
// ---------------------------------------------------------------------------
// Interferência e coloração
// ---------------------------------------------------------------------------
bool GrafoDeInterferencia::haAresta(std::size_t i, std::size_t j) const {
if (i >= n || j >= n) {
return false;
}
return interfere[i * n + j] != 0;
}
GrafoDeInterferencia construirInterferencia(const CodigoRI& ri) {
GrafoDeInterferencia g;
std::unordered_map<std::string, std::size_t> indice;
// Faixa de vida: da definição ao último uso.
for (std::size_t i = 0; i < ri.instrucoes.size(); ++i) {
const InstrucaoRI& ins = ri.instrucoes[i];
const bool define = ins.op == OpRI::Constante ||
ins.op == OpRI::CasamentoDe ||
ins.op == OpRI::Valor ||
ins.op == OpRI::Comparacao;
if (define && !ins.resultado.empty()) {
indice.emplace(ins.resultado, g.faixas.size());
g.faixas.push_back(FaixaDeVida{ins.resultado, i, i});
}
auto registrarUso = [&](const std::string& nome) {
const auto it = indice.find(nome);
if (it != indice.end()) {
g.faixas[it->second].ultimoUso = i;
}
};
switch (ins.op) {
case OpRI::Valor:
case OpRI::DesvioSeFalso:
registrarUso(ins.arg1);
break;
case OpRI::Comparacao:
registrarUso(ins.arg1);
registrarUso(ins.arg2);
break;
case OpRI::Emite:
registrarUso(ins.arg2);
break;
default:
break;
}
}
g.n = g.faixas.size();
g.interfere.assign(g.n * g.n, 0);
for (std::size_t i = 0; i < g.n; ++i) {
for (std::size_t j = i + 1; j < g.n; ++j) {
// Sobreposição em intervalo SEMIABERTO, e a diferença em relação ao
// fechado não é detalhe: um valor MORRE na instrução que o lê pela
// última vez, e o valor que essa mesma instrução produz pode ocupar
// o registrador que acabou de vagar.
//
// Com intervalo fechado, `t3 := t1 > t2` faria t3 interferir com t1
// e t2, e a conta pediria um registrador a mais do que o necessário.
// Foi exatamente o que a primeira versão desta função respondeu — 3
// registradores para uma expressão de profundidade 2 —, e o erro só
// apareceu porque o número foi confrontado com a altura da pilha.
const bool sobrepoe = g.faixas[i].definicao < g.faixas[j].ultimoUso &&
g.faixas[j].definicao < g.faixas[i].ultimoUso;
if (sobrepoe) {
g.interfere[i * g.n + j] = 1;
g.interfere[j * g.n + i] = 1;
}
}
}
return g;
}
Coloracao colorir(const GrafoDeInterferencia& g) {
Coloracao c;
c.corDoTemporario.assign(g.n, 0);
for (std::size_t i = 0; i < g.n; ++i) {
std::vector<bool> usada(g.n + 1, false);
for (std::size_t j = 0; j < g.n; ++j) {
if (j != i && g.haAresta(i, j) && j < i) {
usada[c.corDoTemporario[j]] = true;
}
}
std::size_t cor = 0;
while (cor < usada.size() && usada[cor]) {
++cor;
}
c.corDoTemporario[i] = cor;
if (cor + 1 > c.cores) {
c.cores = cor + 1;
}
}
return c;
}
bool gravarObjeto(const ProgramaObjeto& objeto, const std::string& caminho,
std::string& erro) {
std::ofstream saida(caminho, std::ios::binary);
if (!saida) {
erro = "nao foi possivel abrir para escrita";
return false;
}
// Forma textual, e não binária. A decisão é didática e assumida: o objeto
// deste compilador é para ser LIDO na correção e na aula. Um formato
// binário seria menor e ilegível, e a economia não tem valor aqui.
saida << formatarObjeto(objeto);
if (!saida) {
erro = "falha ao escrever";
return false;
}
return true;
}
} // namespace peneira
A solução é o mapa construído durante a emissão e consultado numa segunda passagem, com os dois detalhes que a Seção 6.2 destacou: o elemento a mais, porque “logo depois da última” é destino legítimo e é para lá que apontam os desvios de condição falsa; e o fato de a operação de rótulo não emitir instrução alguma, ponto em que o contador da representação avança e o do objeto não.
A demonstração confere o resultado, e ele é honesto de um jeito que vale registrar:
faixa.pen, regra on numero(n):
instrucoes intermediarias: 12, de maquina: 13
referencias resolvidas: 2
RI 4 desvia para RI 12 -> objeto 4 desvia para 12
RI 9 desvia para RI 12 -> objeto 9 desvia para 12A correspondência saiu um para um neste artefato, porque toda instrução intermediária virou exatamente uma de máquina. Eu poderia ter concluído dali que o mapa é desnecessário e escrito o gerador supondo identidade — e teria caído exatamente na armadilha da Seção 6.3. A coincidência é propriedade deste conjunto de instruções, não garantia. A operação de rótulo já quebraria a identidade se fosse usada, e qualquer instrução futura que precise de duas de máquina também. Supor identidade produz desvio para a instrução errada, defeito que não aparece em teste algum até a entrada certa aparecer.
1.10.4 9.4 A alocação de registradores, calculada — e o defeito que o cálculo revelou
Esta máquina não tem registradores, e o assunto da Seção 7 poderia, portanto, ficar no verbal. Preferi calcular o que ele custaria: montar o grafo de interferência dos temporários da representação intermediária e colori-lo. O número de cores é o número de registradores que uma máquina de registradores precisaria para a mesma regra.
O resultado, para a regra do exemplo anterior:
temporario | definido em | ultimo uso | cor
-----------+-------------+------------+----
t0 | 0 | 1 | 0
t1 | 1 | 3 | 0
t2 | 2 | 3 | 1
t3 | 3 | 4 | 0
...
temporarios: 9, arestas de interferencia: 2
registradores necessarios (cores): 2
profundidade maxima da pilha: 2Dois registradores, e profundidade de pilha dois. Os números coincidem, e a Seção 7.6 explica por que não é acaso: com cada temporário lido uma única vez, o número de valores vivos ao mesmo tempo é a altura da pilha naquele ponto. As duas máquinas precisam da mesma quantidade de espaço de trabalho; a diferença está em quem o endereça.
Agora o que interessa. A primeira versão desta rotina respondeu três registradores contra pilha de dois, e é esse desencontro que quero registrar.
A causa é o erro clássico da Seção 7.5. Eu tratava as faixas de vida como intervalos fechados, de modo que, na instrução que compara dois temporários e produz um terceiro, o resultado interferia com os dois operandos. Como argumentei ali, um valor morre na instrução que o lê pela última vez, e o valor que essa mesma instrução produz pode ocupar o registrador que acabou de vagar. A sobreposição correta é em intervalo semiaberto, e a correção foi trocar duas comparações.
O que quero deixar registrado não é o erro; é o mecanismo que o pegou. Três registradores para uma expressão de profundidade dois é um número perfeitamente plausível — não tem cara de defeito, nenhum teste de compilação o acusaria, e o compilador não reclama. Ele só caiu porque havia um segundo caminho independente para chegar à mesma grandeza, a simulação estática da pilha, e os dois foram impressos lado a lado. É o mesmo padrão que usei ao confrontar o autômato gerado com o desenhado à mão, e ao testar o autômato mínimo obtido por duas vias com um teste de isomorfismo. Calcular a mesma coisa de dois jeitos independentes é a técnica de verificação mais barata deste projeto, e é a que mais defeitos encontrou.
1.10.5 9.5 O executor mínimo
“Mínimo” tem significado preciso aqui: suficiente para demonstrar que o objeto está correto. O tratamento completo de erro e de casos de fronteira é do capítulo seguinte, e superdimensionar o executor agora atrasaria a única coisa que ele precisa provar.
14_vm.h
#ifndef PENEIRA_14_VM_H
#define PENEIRA_14_VM_H
#include <cstddef>
#include <string>
#include <vector>
#include "13_objeto.h"
namespace peneira {
// EXECUTOR MÍNIMO do programa objeto.
//
// Mínimo tem significado preciso aqui: suficiente para demonstrar que o objeto
// gerado está correto. O tratamento completo de erro e de casos de fronteira é
// do módulo 15, e superdimensionar este executor agora atrasaria a única coisa
// que ele precisa provar — que o que o gerador emitiu executa e produz o efeito
// esperado.
//
// Ele é escrito contra a ESPECIFICAÇÃO do módulo 13, e não contra o gerador do
// módulo 14. A diferença importa: escrito contra o gerador, ele concordaria com
// os defeitos do gerador. Escrito contra a especificação, uma divergência entre
// os dois acusa que um dos dois está errado — que é justamente o teste que o
// critério de completude da especificação queria permitir.
// Um valor na pilha de avaliação. A linguagem tem dois tipos, e o executor
// carrega os dois numa estrutura só porque a análise semântica já garantiu que
// nenhuma instrução vai receber o tipo errado.
struct Valor {
bool ehNumero = false;
double numero = 0.0;
std::string texto;
};
// Uma emissão produzida pela execução: o par (rótulo, valor) que `emit` gera.
struct Emissao {
std::string rotulo;
std::string valor;
std::size_t posicao = 0; // onde na entrada o casamento começou
};
struct ResultadoExecucao {
std::vector<Emissao> emissoes;
std::size_t casamentos = 0;
std::size_t bytesLidos = 0;
std::size_t instrucoesExecutadas = 0;
std::vector<std::string> erros;
};
// Executa o programa objeto sobre a entrada.
//
// O laço principal implementa o casamento mais longo especificado no módulo 13:
// na posição corrente, avança todos os autômatos em paralelo enquanto algum
// tiver transição, lembrando a última posição em que algum esteve em estado
// final. Empate no mesmo comprimento resolve-se pela ordem de declaração — o
// primeiro padrão declarado vence, exatamente como está escrito na
// especificação.
ResultadoExecucao executar(const ProgramaObjeto& objeto,
const std::string& entrada);
} // namespace peneira
#endif // PENEIRA_14_VM_H
A decisão de método vale mais que o código, e é a da Seção 8.6: escrevi o executor contra a especificação do formato, e não contra o gerador. A diferença não é retórica. Escrito contra o gerador, ele concordaria com os defeitos do gerador — os dois estariam errados juntos e os testes passariam. Escrito contra a especificação, uma divergência entre gerador e executor acusa que um dos dois está errado. É exatamente o teste que o critério de completude existia para tornar possível, e é a razão de a especificação ter vindo antes.
14_vm.cpp
#include "14_vm.h"
#include <cstdlib>
namespace peneira {
namespace {
// Consulta a tabela de transição densa. É a operação do laço interno — roda uma
// vez por byte da entrada e por padrão —, e é ela que justifica a matriz densa
// escolhida no módulo 13.
std::uint32_t transicaoDe(const PadraoObjeto& p, std::uint32_t estado,
unsigned char simbolo) noexcept {
const std::size_t indice =
static_cast<std::size_t>(estado) * kTamanhoDoAlfabeto +
static_cast<std::size_t>(simbolo);
if (indice >= p.transicoes.size()) {
return kSemTransicao;
}
return p.transicoes[indice];
}
// Verdade nesta linguagem: número diferente de zero, ou texto não vazio. A
// definição precisa estar num lugar só, porque JUMP_IF_FALSE e os conectivos a
// consultam.
bool ehVerdadeiro(const Valor& v) noexcept {
return v.ehNumero ? v.numero != 0.0 : !v.texto.empty();
}
std::string comoTexto(const Valor& v) {
if (!v.ehNumero) {
return v.texto;
}
// Sem casas decimais quando o número é inteiro: 250 e não 250.000000. É
// cosmético e afeta a saída observável, então está aqui e não no chamador.
const double arredondado = static_cast<double>(static_cast<long long>(v.numero));
if (v.numero == arredondado) {
return std::to_string(static_cast<long long>(v.numero));
}
return std::to_string(v.numero);
}
// Executa o código de uma regra sobre um casamento. Devolve false se o objeto
// estiver malformado — pilha vazia numa instrução que desempilha, ou desvio
// fora de faixa. As duas são as condições de erro listadas na especificação.
bool executarRegra(const ProgramaObjeto& objeto, const RegraObjeto& regra,
const std::string& casamento, std::size_t posicao,
ResultadoExecucao& resultado) {
std::vector<Valor> pilha;
std::size_t pc = 0;
auto desempilhar = [&](Valor& destino) -> bool {
if (pilha.empty()) {
resultado.erros.push_back(
"objeto malformado: pilha vazia em instrucao que desempilha");
return false;
}
destino = pilha.back();
pilha.pop_back();
return true;
};
while (pc < regra.codigo.size()) {
const Instrucao& ins = regra.codigo[pc];
++resultado.instrucoesExecutadas;
switch (ins.op) {
case OpCode::PUSH_CONST: {
if (ins.argumento >= objeto.constantes.size()) {
resultado.erros.push_back(
"objeto malformado: constante fora de faixa");
return false;
}
Valor v;
// A constante é guardada como texto; se ela denota um número,
// entra como número. A análise semântica já garantiu a
// coerência de tipos, então esta conversão não pode
// surpreender.
const std::string& bruto = objeto.constantes[ins.argumento];
char* fim = nullptr;
const double numero = std::strtod(bruto.c_str(), &fim);
if (fim != nullptr && *fim == '\0' && !bruto.empty()) {
v.ehNumero = true;
v.numero = numero;
} else {
v.texto = bruto;
}
pilha.push_back(v);
break;
}
case OpCode::PUSH_MATCH: {
Valor v;
v.texto = casamento;
pilha.push_back(v);
break;
}
case OpCode::VALUE: {
Valor v;
if (!desempilhar(v)) {
return false;
}
Valor n;
n.ehNumero = true;
n.numero = v.ehNumero ? v.numero : std::strtod(v.texto.c_str(), nullptr);
pilha.push_back(n);
break;
}
case OpCode::CMP_GT:
case OpCode::CMP_LT:
case OpCode::CMP_GE:
case OpCode::CMP_LE:
case OpCode::CMP_EQ:
case OpCode::CMP_NE: {
// A ordem importa: o segundo operando foi empilhado por
// último, então sai primeiro. Inverter aqui produz comparações
// trocadas que passam despercebidas nos casos simétricos.
Valor b;
Valor a;
if (!desempilhar(b) || !desempilhar(a)) {
return false;
}
bool r = false;
if (a.ehNumero && b.ehNumero) {
switch (ins.op) {
case OpCode::CMP_GT: r = a.numero > b.numero; break;
case OpCode::CMP_LT: r = a.numero < b.numero; break;
case OpCode::CMP_GE: r = a.numero >= b.numero; break;
case OpCode::CMP_LE: r = a.numero <= b.numero; break;
case OpCode::CMP_EQ: r = a.numero == b.numero; break;
default: r = a.numero != b.numero; break;
}
} else {
const std::string ta = comoTexto(a);
const std::string tb = comoTexto(b);
switch (ins.op) {
case OpCode::CMP_EQ: r = ta == tb; break;
case OpCode::CMP_NE: r = ta != tb; break;
default:
// Ordem sobre texto foi recusada na analise
// semantica, entao chegar aqui e objeto adulterado.
resultado.erros.push_back(
"objeto malformado: operador de ordem sobre texto");
return false;
}
}
Valor v;
v.ehNumero = true;
v.numero = r ? 1.0 : 0.0;
pilha.push_back(v);
break;
}
case OpCode::AND:
case OpCode::OR: {
Valor b;
Valor a;
if (!desempilhar(b) || !desempilhar(a)) {
return false;
}
Valor v;
v.ehNumero = true;
const bool r = ins.op == OpCode::AND
? (ehVerdadeiro(a) && ehVerdadeiro(b))
: (ehVerdadeiro(a) || ehVerdadeiro(b));
v.numero = r ? 1.0 : 0.0;
pilha.push_back(v);
break;
}
case OpCode::JUMP_IF_FALSE: {
Valor v;
if (!desempilhar(v)) {
return false;
}
if (!ehVerdadeiro(v)) {
if (ins.argumento > regra.codigo.size()) {
resultado.erros.push_back(
"objeto malformado: desvio fora de faixa");
return false;
}
pc = ins.argumento;
continue;
}
break;
}
case OpCode::JUMP: {
if (ins.argumento > regra.codigo.size()) {
resultado.erros.push_back(
"objeto malformado: desvio fora de faixa");
return false;
}
pc = ins.argumento;
continue;
}
case OpCode::EMIT: {
Valor v;
if (!desempilhar(v)) {
return false;
}
if (ins.argumento >= objeto.constantes.size()) {
resultado.erros.push_back(
"objeto malformado: rotulo fora de faixa");
return false;
}
resultado.emissoes.push_back(Emissao{
objeto.constantes[ins.argumento], comoTexto(v), posicao});
break;
}
case OpCode::HALT:
return true;
}
++pc;
}
return true;
}
} // namespace
ResultadoExecucao executar(const ProgramaObjeto& objeto,
const std::string& entrada) {
ResultadoExecucao resultado;
resultado.bytesLidos = entrada.size();
std::size_t posicao = 0;
while (posicao < entrada.size()) {
// Casamento mais longo: avança todos os autômatos em paralelo.
std::vector<std::uint32_t> estados(objeto.padroes.size());
std::vector<bool> vivo(objeto.padroes.size(), true);
for (std::size_t p = 0; p < objeto.padroes.size(); ++p) {
estados[p] = objeto.padroes[p].estadoInicial;
if (objeto.padroes[p].quantidadeDeEstados == 0) {
vivo[p] = false;
}
}
std::size_t melhorFim = posicao;
std::size_t melhorPadrao = objeto.padroes.size();
bool houveCasamento = false;
// Um padrão pode aceitar a cadeia vazia; conferir o estado inicial
// antes de consumir byte nenhum evita perder esse caso — e evita
// também o laço infinito que ele causaria se fosse aceito com
// comprimento zero, tratado adiante.
for (std::size_t p = 0; p < objeto.padroes.size(); ++p) {
if (vivo[p] && objeto.padroes[p].finais[estados[p]] != 0) {
houveCasamento = true;
melhorFim = posicao;
melhorPadrao = p;
break;
}
}
std::size_t i = posicao;
while (i < entrada.size()) {
const unsigned char simbolo = static_cast<unsigned char>(entrada[i]);
bool algumVivo = false;
for (std::size_t p = 0; p < objeto.padroes.size(); ++p) {
if (!vivo[p]) {
continue;
}
const std::uint32_t proximo =
transicaoDe(objeto.padroes[p], estados[p], simbolo);
if (proximo == kSemTransicao) {
vivo[p] = false;
continue;
}
estados[p] = proximo;
algumVivo = true;
}
if (!algumVivo) {
break;
}
++i;
// Registra o casamento mais longo visto até agora. A varredura é
// da esquerda para a direita, e o desempate por ORDEM DE
// DECLARAÇÃO sai de graça: o laço testa os padrões na ordem do
// vetor e o `>` estrito impede que um padrão posterior substitua
// um anterior de mesmo comprimento.
for (std::size_t p = 0; p < objeto.padroes.size(); ++p) {
if (vivo[p] && objeto.padroes[p].finais[estados[p]] != 0) {
if (!houveCasamento || i > melhorFim) {
houveCasamento = true;
melhorFim = i;
melhorPadrao = p;
}
break;
}
}
}
// Casamento de comprimento zero não faz progresso e travaria o laço.
// Tratar como ausência de casamento é o que garante terminação.
if (!houveCasamento || melhorFim == posicao ||
melhorPadrao >= objeto.padroes.size()) {
++posicao;
continue;
}
const std::string casado =
entrada.substr(posicao, melhorFim - posicao);
++resultado.casamentos;
// Todas as regras daquele padrão disparam, na ordem de declaração.
for (const RegraObjeto& regra : objeto.regras) {
if (regra.indiceDoPadrao != melhorPadrao) {
continue;
}
if (!executarRegra(objeto, regra, casado, posicao, resultado)) {
return resultado;
}
}
posicao = melhorFim;
}
return resultado;
}
} // namespace peneira
Três pontos do laço principal mereceram cuidado.
O casamento mais longo avança todos os autômatos em paralelo enquanto algum tiver transição, lembrando a última posição em que algum esteve em estado final. É a mesma regra do analisador léxico, e reusá-la é o que mantém a linguagem coerente consigo mesma: o critério com que a Peneira reconhece os seus próprios símbolos é o critério com que os programas escritos nela reconhecem padrões no texto de entrada.
O desempate por ordem de declaração sai praticamente de graça: o laço testa os padrões na ordem do vetor, e a comparação estrita impede que um padrão posterior substitua um anterior de mesmo comprimento. Uma decisão que custou uma linha de código e teria custado dias de confusão se não estivesse na especificação — e ela só entrou na especificação porque escrevê-la antes obrigou a decidir.
O casamento de comprimento zero é a armadilha da Seção 8.6, e ela apareceu de verdade. Um padrão que aceita a cadeia vazia casaria sem consumir nada, e a posição de leitura nunca avançaria: o executor trava sem erro, sem mensagem e sem sintoma visível. Tratar comprimento zero como ausência de casamento é o que garante a terminação, e está no código com comentário porque não é dedutível de olhar.
A ordem dos operandos nas comparações é o quarto ponto, e é o da Seção 3.1: o segundo operando foi empilhado por último e sai primeiro. Inverter aqui produz comparações trocadas que passam despercebidas em todos os casos simétricos — igualdade e desigualdade continuam certas, e só as comparações de ordem denunciam.
1.10.6 9.6 Os três programas, compilados e executados
Escolhi três programas que exercitam coisas diferentes, porque três programas parecidos demonstram uma coisa só. A saída literal da demonstração:
faixa.pen — curto-circuito do 'and' e desvios para a frente
entrada: valores: 7 250 1200 480 -3 99 101
saida:
faixa = 250 (posicao 11)
faixa = 480 (posicao 20)
faixa = 101 (posicao 30)
casamentos: 7, instrucoes executadas: 68, bytes: 33
extremo.pen — curto-circuito do 'or', com desvio incondicional
entrada: leituras 5 -12 1500 800 -1 2000
saida:
extremo = -12 (posicao 11)
extremo = 1500 (posicao 15)
extremo = -1 (posicao 24)
extremo = 2000 (posicao 27)
casamentos: 6, instrucoes executadas: 66, bytes: 31
contatos.pen — dois padroes competindo, casamento mais longo
entrada: ana@teste.com 42 bruno@x.org 350
saida:
contato = ana@teste.com (posicao 0)
contato = bruno@x.org (posicao 17)
grande = 350 (posicao 29)
casamentos: 4, instrucoes executadas: 20, bytes: 32Conferi as três à mão, e é a conferência que dá valor à demonstração.
No primeiro, dos sete números da entrada, apenas 250, 480 e 101 estão estritamente entre 100 e 500; os outros quatro falham por um dos dois lados, e três deles falham já na primeira comparação, com a segunda extração de valor nunca avaliada. É o curto-circuito funcionando, e ele é observável exatamente onde a Seção 5.5 disse que seria: na contagem de instruções. Sessenta e oito instruções para sete casamentos dá menos de dez por casamento, quando o caminho completo tem doze.
No segundo, a condição é disjuntiva e os quatro extremos saem: dois negativos e dois acima de mil. Repare que o valor negativo casa com o sinal, porque a expressão regular do padrão o inclui — se o padrão fosse só de dígitos, o executor casaria o número sem o sinal, a condição daria falso, e o defeito pareceria ser da condição quando seria do padrão. É o tipo de confusão que a competição entre camadas produz e que só a conferência manual desfaz.
No terceiro, os dois padrões competem sobre a mesma entrada e o casamento mais longo decide: o endereço casa inteiro, e não como uma sequência de pedaços. E um dos números casa e não emite, porque a regra tem condição, enquanto o outro casa e emite. As duas regras convivem sobre padrões diferentes.
O comando principal do compilador passa a fazer o ciclo completo:
> peneira exemplos/contatos.pen < exemplos/entrada.txt
fases do compilador:
analise lexica pronta
analise sintatica pronta
analise semantica pronta
geracao de codigo pronta
execucao minima
padroes compilados: 2, regras: 2, instrucoes: 11
objeto gravado ao lado do fonte
execucao sobre 33 bytes de entrada:
contato ana@teste.com
contato bruno@x.org
grande 350
3 emissao(oes) em 4 casamento(s)O objeto é gravado em forma textual, pela razão da Seção 8.5: o objeto deste compilador existe para ser lido na conferência e em aula. Um formato binário seria menor e ilegível, e a economia não tem valor nesta escala.
Sobre o projeto dos casos de teste, seguindo o critério da Seção 5.5: cada entrada foi montada com casos que passam e casos que falham por cada motivo possível. Uma entrada só com números dentro da faixa não distinguiria curto-circuito de avaliação completa, e uma entrada sem endereços não testaria a competição entre padrões. E a saída esperada foi escrita antes de rodar — conferir depois é confirmar o que o programa fez, não verificar o que ele deveria fazer.
1.10.7 9.7 Os autômatos dentro do arquivo gerado
Encerro olhando a primeira seção do objeto, porque é aqui que a Seção 8.2 deixa de ser argumento e vira arquivo:
tabela de padroes (2):
[0] email: 6 estados, inicial 0, 1 final(is)
celulas: 1536, preenchidas: 182
casa somente numeros: nao
[1] numero: 5 estados, inicial 0, 2 final(is)
celulas: 1280, preenchidas: 52
casa somente numeros: simEsses dois autômatos não são estruturas auxiliares do compilador. São o produto. Cada um deles percorreu o caminho inteiro do primeiro bloco do livro — a notação foi analisada, virou autômato não determinístico pela construção de Thompson, foi determinizada por subconjuntos e minimizada por refinamento de partições — e agora está gravado, como tabela de transição, no arquivo que o compilador escreveu.
E o número confirma a observação quantitativa da Seção 8.2: são 2816 células de transição contra 11 instruções. A maior parte do arquivo gerado, em bytes, é autômato. O código convencional é a minoria.
A linha que informa se o padrão reconhece somente números vem de mais longe ainda, e é o caso da Seção 8.4: ela é o resultado de uma decisão de inclusão de linguagens tomada na análise semântica, que por sua vez usou a diferença de autômatos e o teste de vacuidade. Uma informação de sistema de tipos, gravada no programa objeto, calculada por operações sobre autômatos.
Vale ver o compilador inteiro numa tabela, com o resultado de cada fase sobre o mesmo programa:
| Fase | Resultado neste programa |
|---|---|
| Análise léxica | símbolos reconhecidos por autômato determinístico |
| Análise sintática | 13 nós na árvore |
| Análise semântica | 2 padrões, 0 erros |
| Representação intermediária | três endereços com desvios |
| Geração de código | 11 instruções, 2816 células de transição |
| Execução | 3 emissões em 4 casamentos |
É a tabela de interfaces do primeiro capítulo, preenchida com números reais de um compilador que existe.
1.11 Síntese
A geração de código é o ponto em que o compilador deixa de decidir e passa a escolher: o contrato de correção é o mesmo do primeiro módulo, e ele deixa de fora tudo o que interessa, porque infinitas sequências o satisfazem. Os três subproblemas interagem em ciclo, resolvê-los conjuntamente é intratável, e a decomposição troca otimalidade por tratabilidade e modularidade. A escolha entre pilha e registradores redistribui a dificuldade em vez de eliminá-la.
O conjunto de instruções é uma especificação, não uma lista de nomes, e da declaração do efeito decorre a altura estática da pilha. A emissão é um percurso em pós-ordem — consequência do modelo, não escolha — e depende da invariante de leitura única, porque numa máquina de pilha ler é desempilhar. O curto-circuito é semântica e não otimização, exprime-se com fluxo de controle, e a sua diferença aparece na contagem de instruções. As referências pendentes se resolvem registrando a posição e completando depois, com um mapa que precisa de uma entrada a mais. E a alocação de registradores reduz-se exatamente à coloração do grafo de interferência, herdando dela a NP-completude.
O produto é um arquivo com código e dados, cuja seção de dados pode conter tabelas de transição de autômatos determinísticos — e aí as máquinas dos primeiros módulos deixam de ser infraestrutura e passam a ser o resultado da compilação. Volto ao verificador caríssimo da abertura: ele agora escreve um arquivo, e dentro dele está a teoria com que o semestre começou.