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
1 Módulo 14: Geração de Código — Resumo
Esta é a versão de revisão. Recapitulo aqui, em ritmo de véspera, o que este módulo pede que fique guardado; nada é demonstrado por inteiro, e para isso existem a versão completa do material deste módulo e o livro. Use este texto para conferir se você reconstrói de cabeça o caminho da representação intermediária até um arquivo que outra pessoa executa.
Rode o seu compilador sobre um programa: ele analisa o texto, monta a árvore, confere os tipos, gera a representação intermediária — e termina, devolvendo a memória ao sistema. O que você construiu até aqui é um verificador caríssimo: sabe dizer “está bem formado” e mais nada. Este módulo é o que faz aparecer um arquivo, e é também onde a natureza do trabalho muda, porque pela primeira vez não existe a resposta certa.
1.1 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) dê o mesmo resultado que a semântica atribui a r. É a igualdade de significados do primeiro módulo — e o problema é que ela não determina G. Sempre dá para acrescentar instrução sem efeito observável, reordenar operações independentes, chegar ao mesmo lugar por outro caminho. Boa sob qual critério? Tempo, tamanho, energia, previsibilidade — e neste último caso uma transformação que melhora o caso médio e piora o pior caso é uma piora.
O problema se decompõe em três. A seleção de instruções decide quais instruções realizam cada operação; parece consulta a tabela, e é, enquanto o conjunto for pequeno e regular. Sobre árvores, o ladrilhamento de custo mínimo tem solução ótima por programação dinâmica em tempo linear, resultado de Alfred Aho e Stephen Johnson de 1976 — um dos raríssimos lugares da área com algoritmo ótimo. A alocação de registradores vem de um fato bruto: a máquina tem poucos registradores e o programa produz valores intermediários sem limite; quando não bastam, algum valor vai para a memória, que é o derramamento. A ordenação da avaliação é a mais sutil, 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.
Os três se mordem a cauda: a melhor seleção depende de quantos registradores há, a alocação depende da ordem, a ordem depende das instruções. Formulado como problema único, o conjunto é intratável — contém a coloração de grafos como caso particular. A prática decompõe e aceita o subótimo: 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; segundo previsibilidade, porque gerador fácil de descrever produz código conferível por inspeção; só em terceiro a qualidade do código gerado. Inverter isso é a forma mais comum de terminar o semestre com um gerador sofisticado que não funciona.
1.2 Pilha ou registradores: onde mora a dificuldade
Escolher o modelo de máquina não elimina dificuldade, redistribui. Numa máquina de pilha as operações não nomeiam operandos: retiram do topo o que consomem e depositam no topo o que produzem, e o gerador não decide onde pôr nada porque a posição faz o trabalho do nome. Numa máquina de registradores cada instrução diz de onde lê e onde escreve, executam-se menos instruções — e em troca a decisão de qual valor mora onde volta para o gerador.
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 | implícitos, no topo | nomeados na instrução |
| Alocação de registradores | não existe | subproblema dominante |
| Ordenação da avaliação | fixada pela pós-ordem | há liberdade a explorar |
| Instruções executadas | mais | menos |
| Dificuldade do gerador | baixa | alta |
Leia a tabela como redistribuição e não como classificação: a dificuldade total é aproximadamente constante. E note o que costuma passar batido — código de três endereços é código para uma máquina de registradores ilimitados, cada temporário um registrador virtual; a alocação é o mapeamento desse conjunto no conjunto finito da máquina real, e não existe quando o destino é pilha porque não há nomes nos quais mapear. Prefira pilha quando o destino for uma máquina virtual sua, quando a portabilidade pesar mais que o desempenho, ou quando as expressões forem rasas — a condição mais esquecida e a decisiva. Na Peneira uma condição é uma comparação, no máximo duas ligadas por conectivo, e por isso a pilha ganha ali; noutro projeto a mesma escolha seria a errada.
1.3 Instruções como especificação, e a emissão em pós-ordem
Aqui você deixa de ser usuário de um conjunto de instruções e passa a ser projetista de um. Uma instrução é código de operação, 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: cada lado testa contra a própria interpretação e os dois passam. Do efeito declarado sai de graça a altura estática da pilha, e daí a profundidade a reservar e a rejeição de objeto cuja pilha não fecha. Tamanho fixo das instruções desperdiça bytes e compra um executor mais simples.
Declare por escrito qual operando sai primeiro da pilha. O segundo foi empilhado por último e sai primeiro. Numa soma, trocar não altera nada; numa subtração, numa divisão ou numa comparação de ordem, o resultado sai errado — e só nos casos assimétricos, de modo que metade dos testes ingênuos continua passando alegremente.
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º"]
Com a máquina projetada, o gerador fica curto: percurso em pós-ordem, emitindo a carga do valor nas folhas e a instrução da operação nos nós internos. A execução deixa na pilha exatamente um valor, por indução sobre a altura. Isso não é escolha estética: a instrução da operação exige os operandos já empilhados, então emiti-la antes deles consumiria de uma pilha vazia — é a única ordem possível. Sustentando tudo há a invariante de leitura única: cada valor depositado é consumido por exatamente uma instrução posterior, porque ler é desempilhar e um valor lido some. Ou você constrói a representação de modo a satisfazê-la, ou acrescenta uma instrução de duplicação do topo — e, em qualquer dos casos, verifique em código, porque garantia “por construção” é a que se perde na manutenção.
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. O que a tradução direta para pilha faz nesse caso, e por que os seus testes de soma e de igualdade continuariam passando?
1.4 Curto-circuito, referências pendentes e o mapa de endereços
Aqui a geração deixa de ser tradução e passa a construir estrutura de controle que não corresponde a nada visível no fonte. Primeira coisa a desentortar: curto-circuito não é otimização. Ele altera o comportamento observável quando o operando direito tem efeito colateral ou pode falhar — testar se um índice é válido e, na conjunção, acessar a posição funciona sob curto-circuito e falha sob avaliação ansiosa. São duas linguagens diferentes, e a escolha pertence à especificação. A dificuldade vem do modelo: uma instrução de conjunção precisa dos dois valores na pilha, logo implementa necessariamente avaliação ansiosa. Curto-circuito é fluxo de controle.
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 código que calcula verdadeiro ou falso, código que desvia para um lugar quando é verdadeira e para outro quando é falsa, devolvendo duas listas de desvios em branco. Numa conjunção, traduz-se o esquerdo, preenche-se a sua lista de verdadeiro com a posição em que o direito começa, e devolve-se como lista de falso a união das duas — lido em português, é a semântica; na disjunção as listas trocam de papel. E o destino de um desvio para a frente não é difícil de calcular, é inexistente: emite-se em branco, guarda-se a posição e volta-se depois, no preenchimento retroativo.
O problema é mais geral. Os desvios da representação apontam para índices da representação, e o objeto precisa de índices do objeto; a solução é um mapa construído durante a emissão e consultado numa segunda passagem. Dois detalhes produzem defeitos reais: o mapa precisa de um elemento a mais que o número de instruções, porque “logo depois da última” é destino legítimo, e nem toda instrução intermediária gera uma de máquina. Na Peneira:
Coincidência não é invariante. No artefato conduzido a correspondência saiu um para um e o mapa virou a identidade — concluir dali que ele é dispensável está errado de um jeito que não se manifesta. Um rótulo já quebra a identidade, e uma instrução traduzida por duas de máquina também. Quando quebrar, não haverá mensagem de erro: haverá desvio para a instrução errada.
1.5 Alocação de registradores como coloração
Este subproblema some quando o destino é pilha, e ainda assim vale estudá-lo. 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 — um valor morre na instrução que o lê pela última vez, e depois disso o registrador está livre, inclusive para receber o valor que essa mesma instrução produziu. Dois temporários interferem quando as faixas se sobrepõem, e o grafo de interferência tem os temporários como vértices.
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, e o mínimo de registradores é o número cromático. Gosto deste exemplo porque modelar bem é achar um problema que é o mesmo, não um parecido. O primeiro alocador construído sobre essa correspondência é de 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, da lista clássica de Richard Karp de 1972 — daí a heurística de simplificação, que empilha vértices de grau menor que k e depois os desempilha atribuindo a menor cor livre.
O erro clássico. Tratar as faixas como intervalos fechados faz o resultado de uma instrução interferir com os operandos que ela acabou de matar, e o alocador pede mais registradores do que precisa. O código sai correto e conservador: nenhum teste acusa, e três registradores para uma expressão de profundidade dois é número plausível — e defeitos plausíveis moram no código por anos. Na implementação de referência esse só caiu porque a mesma grandeza vinha por dois caminhos independentes, a coloração e a simulação estática da pilha, impressos lado a lado.
Dentro de um trecho linear cada faixa é um intervalo da reta e a coloração ótima sai por algoritmo guloso; a dificuldade geral vem da alocação entre blocos. Isso explica a coincidência entre número de cores e altura máxima da pilha: com leitura única e código linear, o número de valores vivos num ponto é a altura ali.
1.6 O objeto como artefato: quando os autômatos viram produto
O programa objeto tem seção de código e seção de dados, e é na de dados que mora a novidade. Compilar um programa da Peneira converte cada padrão declarado num autômato finito determinístico — notação, árvore, Thompson, subconjuntos, minimização — e o gerador serializa esses autômatos na seção de dados: a tabela de transição vira vetor de números que o executor consulta uma vez por caractere.
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
Lá atrás os autômatos eram mecanismo interno do analisador léxico, invisíveis no resultado; aqui aparecem do outro lado, executados pelo programa que o compilador produziu. E há um número que inverte a intuição: no artefato conduzido, dois padrões dão 2816 células de transição contra 11 instruções — a maior parte do arquivo, em bytes, é autômato. Duas decisões de formato fecham a seção. Dentro do compilador a função de transição é esparsa, porque o autômato é transformado o tempo todo; no objeto vira matriz densa, porque ali ele só é consultado — a representação segue o papel da estrutura, não a natureza matemática dela. E grave o objeto em forma textual: a binária é menor, a textual pode ser lida.
Pare e pense. Se você escrever o executor contra o seu gerador, em vez de contra a especificação do formato, o que exatamente os seus testes deixam de detectar?
1.7 Síntese
Geração de código é o ponto em que o compilador deixa de decidir e passa a escolher: o contrato de correção deixa de fora tudo o que interessa, porque infinitas sequências o satisfazem. Os três subproblemas interagem em ciclo, resolvê-los juntos é intratável, e a decomposição troca otimalidade por tratabilidade. Pilha ou registradores redistribui a dificuldade em vez de eliminá-la. O conjunto de instruções é especificação, e da declaração do efeito sai a altura estática. A emissão em pós-ordem é consequência do modelo e depende da leitura única. Curto-circuito é semântica e se exprime com desvios, e o preenchimento retroativo resolve as pendências com um mapa que precisa de uma entrada a mais. A alocação reduz-se exatamente à coloração e herda a NP-completude. A sua entrega tem a mesma forma sobre a linguagem do seu grupo: máquina especificada por escrito, gerador que produz o arquivo, executor mínimo escrito contra a especificação. E o verificador caríssimo da abertura agora escreve um arquivo — dentro do qual está a teoria com que o semestre começou.