flowchart LR
F1[Origem 1] --> RI
F2[Origem 2] --> RI
F3[Origem m] --> RI
RI{{Representacao<br/>intermediaria}}
RI --> G1[Destino 1]
RI --> G2[Destino 2]
RI --> G3[Destino n]
1 Módulo 13: Representações Intermediárias e Ambientes de Execução — Resumo
Esta é a versão de revisão. Recapitulo aqui, em ritmo de véspera, o que este módulo tem de 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ê consegue explicar, sem consultar nada, por que um desvio pode nascer sem destino e como ele ganha um depois.
Traduza “a < b e c < d” para instruções de máquina respeitando a regra que qualquer linguagem de uso corrente impõe: se o primeiro teste falhar, o segundo nem chega a ser executado. Compare, e se der falso, desvie. Desvie para onde? Para o ponto depois do comando inteiro, que ainda não foi traduzido e cujo endereço, portanto, não existe ainda. O módulo inteiro gira em torno dessa pergunta.
1.1 Por que existe uma camada no meio
Uma representação intermediária é uma linguagem L_i, distinta da fonte L_f e do alvo L_a, tal que o compilador se decompõe em F: L_f \to L_i e G: L_i \to L_a, com C = G \circ F, e tal que L_i é independente das particularidades das duas pontas. A independência dá conteúdo à definição — sem ela qualquer estrutura interna seria intermediária, inclusive a árvore sintática, toda moldada pela gramática da origem.
O argumento clássico é uma conta: m origens e n destinos custam m \times n tradutores diretos e apenas m + n peças com a camada. Faça a conta para o seu caso, que é o que quase ninguém faz. Com uma origem e um destino — a situação de praticamente todo compilador que você vai escrever na vida — a direta custa uma peça e a camada custa duas: o argumento combinatório condena a camada, e o ponto de virada só aparece em três por três.
Pare e pense. Se o argumento mais citado a favor da camada não vale para o seu projeto, por que quase todo compilador sério tem uma? Responda sem repetir a frase do livro.
A resposta é a segunda justificativa, menos citada e mais útil: a separação de dificuldades. Ordem de avaliação com desvios é fluxo de controle; codificação de instruções é formato de arquivo. Resolvidos no mesmo laço, cada erro de um parece defeito do outro — eu mesmo já perdi dias assim. A camada permite resolver um antes de o outro existir, porque é uma fronteira observável: você imprime, confere à mão e testa a tradução contra uma sequência esperada, sem uma linha do gerador final. Guarde também o teste do apagamento: se eu apagar esta camada e ligar as pontas, o que fica mais difícil? Se a resposta honesta for “nada”, você economizou um mês.
1.2 As formas usuais, comparadas na construção mais difícil
Compare as formas sempre sobre a mesma expressão, e que seja a mais difícil que a linguagem admite — o que brilha numa soma pode ser inservível numa condição composta. A árvore abstrata é a mais informativa e sustenta o mapeamento entre código e texto-fonte de que um depurador precisa, mas a ordem de avaliação fica implícita na estrutura e não há nela onde escrever “se este subteste falhar, pule aquele nó”. A notação pós-fixada sai de graça do percurso em pós-ordem, dispensa parênteses e usa a pilha como temporário; e não exprime desvio. O código de três endereços tem no máximo um operador por instrução, tipicamente x := y \;\Theta\; z, dando nome a cada resultado parcial, e traz o que faltava às outras duas: desvios que carregam um destino.
flowchart TD
A[Arvore verificada] --> B{A forma<br/>exprime desvio?}
B -- nao --> C[Arvore sintatica abstrata<br/>ordem de avaliacao implicita]
B -- nao --> D[Notacao pos-fixada<br/>ordem explicita, sem desvio]
B -- sim --> E[Codigo de tres enderecos<br/>ordem explicita e desvio com destino]
C --> F[Reprovada no curto-circuito]
D --> F
E --> G[Escolhida]
A escolha não é por elegância: a pós-fixada é a mais curta e a mais fácil de executar, e é a errada, porque sem desvio não há curto-circuito e o conectivo avalia sempre os dois lados — o que não é ineficiência, é mudança de semântica.
Falta decidir como guardar. Quádruplas guardam operador, dois operandos e resultado; triplas eliminam o campo de resultado e usam a posição da instrução como nome do valor produzido, o que as deixa hostis à reordenação, e as indiretas corrigem isso com um vetor de índices que dá a ordem de execução. Recomendo quádruplas: o recurso escasso do seu compilador é a sua atenção. Em panorama, um código está na forma de atribuição única estática quando cada nome é destino de exatamente uma atribuição no texto do programa, com funções \phi nos encontros de caminhos — “estática” é sobre o texto, não sobre a execução. Formalizada em 1991 por Ron Cytron, Jeanne Ferrante e colaboradores, ela existe para viabilizar análises globais de fluxo de dados, e sem elas não paga o próprio custo.
1.3 Tradução, curto-circuito e preenchimento retroativo
A tradução é um percurso recursivo em que cada nó devolve algo ao pai e, no caminho, emite instruções numa lista que cresce. A frase que torna tudo quase mecânico: o atributo devolvido por um nó de expressão é o nome do temporário que contém o seu valor. Traduza os filhos, guarde os nomes, crie um temporário, emita e devolva o nome novo — sem caso especial e sem tabela de precedência, que a análise sintática já gravou na forma da árvore. Vem de graça uma verificação: o número de temporários criados é igual ao de nós de expressão visitados.
Os comandos é que começam o assunto. No condicional emitem-se dois desvios para a frente, ambos com destino desconhecido; no laço, marca-se a posição atual e o desvio de volta aponta para instrução já emitida. Daí a assimetria que quero gravada: o desvio para trás é o caso fácil.
Na tradução por valor cada lado da condição vira expressão comum com um temporário booleano, e uma instrução de conjunção combina os dois; é curta e é ansiosa por construção, porque combinar dois valores exige ter calculado os dois. A que funciona é a tradução por fluxo de controle: a condição não devolve valor, devolve duas listas de desvios pendentes. Na conjunção, a lista verdadeira do lado esquerdo recebe como destino o início do direito — é isso que significa “continue testando” —, a verdadeira do conjunto é a do direito, e a falsa é a união das duas falsas. Na disjunção o esquema é simétrico, e nasce um desvio incondicional pendente porque o caminho verdadeiro da esquerda precisa pular o lado direito inteiro.
flowchart TD
A[Emitir desvio<br/>com destino vazio] --> B[criar lista<br/>com um indice]
B --> C{Combinar<br/>com outro operando?}
C -- sim --> D[fundir listas<br/>em uma so]
D --> C
C -- nao --> E{Destino ja<br/>conhecido?}
E -- nao --> F[devolver a lista<br/>ao chamador]
F --> C
E -- sim --> G[preencher<br/>toda a lista de uma vez]
G --> H[verificacao final:<br/>zero desvios pendentes]
O preenchimento retroativo costura tudo com três operações: criar uma lista com um único índice, fundir duas listas, e escrever o mesmo destino em todas as instruções de uma lista. No compilador da Peneira, a assinatura já conta a história:
// Traduz uma condição. Devolve as listas de instruções de desvio que ainda
// precisam de destino: as que saem quando a condição é verdadeira e as que
// saem quando é falsa.
struct ListasDeDesvio {
std::vector<std::size_t> verdadeiro;
std::vector<std::size_t> falso;
};
ListasDeDesvio traduzirCondicao(const NoAst& cond);
// Preenche o destino de todas as instruções da lista.
void preencher(const std::vector<std::size_t>& lista, std::size_t destino); ListasDeDesvio esquerda = traduzirCondicao(*cond.filhos[0]);
// O verdadeiro do esquerdo aponta para onde o direito começa, que é
// a próxima instrução a ser emitida.
preencher(esquerda.verdadeiro, instrucoes_.size());
ListasDeDesvio direita = traduzirCondicao(*cond.filhos[1]);
listas.verdadeiro = std::move(direita.verdadeiro);
listas.falso = std::move(esquerda.falso);
for (const std::size_t i : direita.falso) {
listas.falso.push_back(i);
}Na conjunção do programa de referência, as duas saídas falsas apontam para o mesmo endereço, que nenhuma conhecia ao ser gerada: entraram na mesma lista e foram preenchidas juntas ao fim da regra.
A verificação que você deve escrever hoje. O esquema não deixa desvio pendente ao término de um comando completo: conte-os ao final; o número tem de ser zero. O defeito que essa contagem pega é um desvio para lugar nenhum, que não dá erro de compilação — dá comportamento errado semanas depois.
1.4 O programa objeto e a sua especificação
Decidida a representação, decide-se o que sai do compilador, e defendo uma ordem minoritária: a especificação do formato antes do código que a produz. Documentação escrita a partir do código registra as decisões acidentais junto com as deliberadas e não distingue umas das outras.
Critério de completude. Uma especificação de formato objeto é completa quando alguém que leia apenas ela consegue escrever um executor compatível. Entregue-a a outra pessoa com um objeto e uma entrada, e peça que descreva a saída: onde ela precisar perguntar, falta texto — e o que falta não é redação, é decisão.
A decisão mais estrutural é o modelo de máquina. Numa máquina de pilha as instruções não nomeiam operandos e a geração é quase o percurso em pós-ordem, ao custo de todo valor intermediário passar pela memória; numa de registradores o código é mais rápido e a geração é mais difícil, porque é preciso decidir quais valores merecem registrador. O critério depende da linguagem, não da máquina: a profundidade das expressões, calculável por
d(\text{folha}) = 1, \qquad d(T) = \max\bigl(d(T_e),\; 1 + d(T_d)\bigr),
vale 2 na cadeia inclinada à esquerda ((a+b)+c)+d e 4 na simétrica a+(b+(c+d)) — mesma conta, custos de pilha diferentes, e a diferença está só na forma da árvore. Como d(T) é conhecida na compilação, o compilador grava no objeto de quanta pilha o programa precisa. Instruções de tamanho fixo fazem a posição ser o índice, o que torna o preenchimento retroativo utilizável também no objeto. E a mesma estrutura pode ter representações diferentes dentro e fora: a função de transição de um autômato é esparsa no compilador e densa no objeto, onde é consultada uma vez por símbolo da entrada — na Peneira medi quatro por cento das posições preenchidas, e defendo a densa com esse número na mesa, não com intuição. Falta o modelo de execução: o casamento mais longo, uma regra de desempate escrita para reconhecedores que empatam em comprimento, e as condições de erro listadas inclusive quando as fases anteriores provaram que não ocorrem — o objeto é um arquivo, e arquivos podem ser adulterados.
1.5 Ambientes de execução
A memória divide-se convencionalmente em código, área estática, pilha e monte. Proponho leitura mais útil: o corte que interessa é entre o que o compilador sabe e o que só a execução descobre.
flowchart TD
M[Memoria do programa<br/>em execucao] --> S1[O compilador sabe]
M --> S2[So a execucao descobre]
S1 --> C[Codigo:<br/>instrucoes emitidas]
S1 --> E[Area estatica:<br/>constantes e tabelas]
S2 --> P[Pilha:<br/>registros de ativacao]
S2 --> H[Monte:<br/>alocacao dinamica]
P --> N[Profundidade maxima:<br/>calculavel na compilacao]
A fronteira é menos nítida do que parece — a profundidade máxima da pilha de avaliação é calculável na compilação, embora o conteúdo não seja. A área de cada dado decorre do tempo de vida e de o tamanho ser conhecido ou não: vida do programa inteiro com tamanho conhecido vai para a estática; vida de bloco vai para a pilha, cuja disciplina de crescimento é a do aninhamento; o resto vai para o monte. Uma linguagem em que nada sobrevive ao bloco que o criou não precisa de monte.
O registro de ativação é o bloco contíguo com tudo o que uma execução de procedimento precisa: valor devolvido, parâmetros, elo de controle, elo de acesso, estado salvo, locais e temporários. Cada execução tem o seu — com um bloco fixo por procedimento a recursão seria impossível, razão histórica de linguagens antigas sem pilha não a admitirem. Ativação não é sinônimo de chamada: qualquer construção com ponto de entrada, valores ligados nessa entrada, espaço próprio e retorno é uma ativação. O protocolo de chamada e retorno divide o trabalho entre as duas partes, e a divisão exata não importa desde que seja uma só e documentada — o que só o chamador sabe cabe ao chamador.
flowchart TD
Q0[Quadro 0<br/>principal, nivel 0]
Q1[Quadro 1<br/>externo, nivel 1]
Q2[Quadro 2<br/>interno, nivel 2]
Q3[Quadro 3<br/>externo, nivel 1]
Q3 -- elo de controle --> Q2
Q2 -- elo de controle --> Q1
Q1 -- elo de controle --> Q0
Q3 -. elo de acesso .-> Q0
Q2 -. elo de acesso .-> Q1
Q1 -. elo de acesso .-> Q0
O elo de controle aponta para o registro de quem chamou e segue a ordem de execução; o elo de acesso aponta para o registro do procedimento que contém lexicamente o ativado e segue a ordem léxica. Uma responde “para onde volto”; a outra, “onde estão as variáveis que eu enxergo”. O menor exemplo de divergência precisa de três níveis, e nele uma variável do procedimento mais interno não é visível ainda que o registro dele esteja na pilha logo abaixo: estar na pilha e ser visível são coisas diferentes. Um procedimento de nível n_p que acessa variável de nível n_v \le n_p segue exatamente n_p - n_v elos, número conhecido na compilação — o que parecia exigir procura vira aritmética de endereço, e é isso que torna o escopo estático barato.
Na gerência explícita os dois modos de errar são simétricos — devolver cedo demais e nunca devolver —, e vem junto a fragmentação externa, com a memória livre partida em pedaços pequenos demais, e a interna, perdida dentro de blocos arredondados. A alocação por região devolve de uma vez tudo o que foi alocado numa fase. Quando dados sobrevivem à construção que os criou, entra a coleta automática, construída sobre a alcançabilidade: a contagem de referências distribui bem o custo e não trata ciclos; a marcação e varredura, da primeira implementação de LISP, por John McCarthy, no início dos anos 1960, trata ciclos e paga com pausa proporcional à memória; cópia e geracionais atacam o custo pelo lado do que sobrevive.
Pergunta para a sua entrega. O seu projeto tem coleta automática? Se não tem, consegue escrever a frase de engenharia que justifica a ausência — “nada sobrevive à ativação que o criou”? Omitir o assunto não é resposta.
1.6 Síntese
A camada intermediária existe por duas razões, e a combinatória só é decisiva a partir de três origens e três destinos; o que a sustenta em compilador de origem única é a separação de dificuldades. Entre as formas, a árvore deixa a ordem implícita, a pós-fixada não exprime desvio, e o código de três endereços é o que se usa — comparadas sempre sobre a construção mais difícil da linguagem. A tradução é um esquema dirigido pela sintaxe em que cada nó de expressão devolve o nome do seu temporário, enquanto as condições devolvem duas listas de desvios pendentes; o preenchimento retroativo fecha o mecanismo com criar, fundir e preencher, mais a verificação de zero pendências. Do lado do produto, a especificação vem antes do código, e o critério de completude revela comportamentos não decididos. Do lado da execução, o corte útil separa o que o compilador prova do que só a execução descobre; cada ativação tem o seu registro, e duas cadeias atravessam a pilha respondendo a perguntas diferentes. Volto ao desvio da abertura: agora ele tem nome, tem lista, tem três operações e tem uma contagem que pega o defeito no dia em que ele nasce. O próximo módulo escreve a peça que liga a representação ao formato — e prepare-se, porque os autômatos do começo do curso reaparecem lá, como tabelas de transição dentro do arquivo que o compilador gera.