Compiladores

A estrutura de um compilador e um tradutor simples

Um compilador lê um programa em uma linguagem fonte e escreve um programa equivalente em uma linguagem alvo. O programa novo roda depois, sozinho. Um interpretador não escreve programa novo. Ele lê o seu programa e faz o que ele manda, na hora, usando a entrada que o usuário dá.

As fases

O compilador é uma cadeia de fases. Cada fase recebe o que a anterior produziu. A primeira metade, chamada front end, entende o programa fonte. A segunda metade, o back end, escreve o programa para a máquina alvo.

caracteres
    |  análise léxica
    v
 tokens
    |  análise sintática
    v
 árvore sintática
    |  análise semântica
    v
 árvore verificada
    |  geração de código intermediário
    v
 código intermediário   <-- aqui termina o front end
    |  otimização, geração de código
    v
 código alvo            <-- back end

Um token é um pedacinho do texto com uma etiqueta. Em geral é um par: o nome do token (por exemplo id) e um atributo (por exemplo um ponteiro para a entrada desse nome na tabela de símbolos). A fase léxica é a que lê o fluxo de caracteres, agrupa em pedaços e entrega os tokens para a fase seguinte.

A tabela de símbolos é a lista telefônica do compilador. Para cada nome do programa (uma variável, uma função, um tipo) ela guarda um registro com os atributos desse nome: o tipo, o escopo, onde fica guardado e, para funções, o número e os tipos dos parâmetros. As fases de análise a preenchem e todas as fases, até a geração de código, a consultam. Quando a linguagem tem blocos aninhados, costuma haver uma tabela por escopo, e cada tabela é encadeada com a tabela do bloco que a envolve.

Por que front end e back end são separados

O front end depende da linguagem fonte. O back end depende da máquina alvo. Os dois só se encontram na representação intermediária. Assim, com m linguagens e n máquinas você escreve m + n componentes e obtém m × n compiladores.

É por isso que sistemas como LLVM e GCC atendem muitas linguagens e muitas arquiteturas.

Do texto ao programa em execução

1. O pré-processador expande macros e inclui outros arquivos.
2. O compilador gera código assembly.
3. O montador (assembler) transforma o assembly em código de máquina relocável.
4. O linkador junta os arquivos objeto e as bibliotecas e resolve os endereços de coisas definidas em outro lugar.
5. O carregador (loader) coloca o executável na memória.

Escopo e parâmetros

O escopo de um nome diz onde o nome pode ser usado. No escopo estático (também chamado léxico), um uso de nome se refere à declaração do bloco que o envolve no texto do programa. O compilador consegue decidir isso antes de rodar. No escopo dinâmico, o uso se refere à declaração mais recente ainda ativa na pilha de chamadas, o que só se sabe durante a execução.

var x = 1;
function show() { print(x); }
function test() { var x = 2; show(); }
test();

Parâmetros podem ser passados de duas formas principais. Na passagem por valor, o parâmetro é uma variável nova que recebe uma cópia do argumento, então mudá-lo não muda a variável de quem chamou. Na passagem por referência, o parâmetro recebe o endereço do argumento e vira outro nome para a mesma memória. Se dois parâmetros apontam para o mesmo lugar, eles são aliases: escrever por um muda o que o outro lê.

void f(int a, int b) { a = a + 10; b = b * 2; }
int x = 1;
f(x, x);
print(x);

Um tradutor minúsculo: infixa para pós-fixa

Na notação pós-fixa o operador vem depois dos operandos. A tradução de E1 op E2 é a tradução de E1, depois a de E2, depois o operador. Os parênteses desaparecem, porque a posição do operador já diz a quais operandos ele se aplica. Um esquema de tradução imprime o operador no fim de cada produção, e o resultado é exatamente o programa de uma máquina de pilha.

Análise léxica: regex, AFN e AFD

Quando você lê 'o gato dorme', não olha letra por letra. Você vê palavras. O analisador léxico (ou lexer) faz o mesmo com um programa: transforma o fluxo de caracteres em um fluxo de tokens como id, num e if. Ele também joga fora espaços em branco e comentários. Assim a fase seguinte trabalha com palavras e não com letras, e o lexer pode usar autômatos finitos, que são muito rápidos.

Padrão, lexema e token

• O padrão é a regra que diz como são as cadeias de uma categoria.
• O lexema é uma cadeia real do programa que casa com um padrão, por exemplo total ou 42.
• O token é o que o lexer entrega ao parser: o nome da categoria mais um atributo opcional.

Então total e sum são dois lexemas diferentes do mesmo token id.

Expressões regulares

Uma expressão regular (regex) é um jeito curto de descrever um conjunto de cadeias. Ela usa três operações: concatenação (uma coisa depois da outra), alternância | (isto ou aquilo) e o fecho de Kleene * (zero ou mais repetições). Precedência: o asterisco liga primeiro, depois a concatenação, e o | por último. Uma definição regular dá um nome a uma expressão para você reutilizá-la.

letter = [A-Za-z]
digit  = [0-9]
id     = letter (letter | digit)*

A expressão acima diz: um identificador começa com uma letra e continua com qualquer quantidade de letras ou dígitos.

Qual token vence? Casamento mais longo

A regra do casamento mais longo (maximal munch) diz que o lexer deve pegar o maior prefixo da entrada que case com algum padrão. Só quando dois padrões casam com o mesmo lexema é que a ordem das regras desempata. É assim que if vira palavra reservada e não identificador: a regra dele vem antes de id. Juntas, as duas regras dão uma única forma de dividir a entrada.

Um lexer implementado com AFD lê enquanto houver transição. Ele lembra a posição e a regra do último estado de aceitação que visitou. Quando trava, volta o ponteiro da entrada até essa posição, emite o token guardado e lê de novo os caracteres a mais como parte dos próximos tokens.

Lendo a entrada rápido

Pedir um caractere de cada vez ao sistema operacional seria muito lento. Por isso o lexer lê blocos grandes. Ele usa um par de buffers: duas metades, para que um lexema possa atravessar a fronteira entre dois blocos. No fim de cada metade há um caractere especial, a sentinela. O laço já precisa olhar todo caractere, então o teste de fim de buffer vira só mais um caso desse mesmo olhar, e uma comparação sai do laço mais executado do compilador.

AFN e AFD

Um autômato finito é uma máquina com poucos estados e setas entre eles, rotuladas com símbolos. Pense num jogo de tabuleiro com casas e setas. Um AFD (determinístico) tem exatamente uma seta para cada estado e símbolo, então existe um único caminho. Um AFN (não determinístico) pode ter várias setas com o mesmo símbolo e também transições ε, que não gastam símbolo da entrada. Um AFN aceita se algum caminho termina em estado de aceitação. Os dois têm o mesmo poder: reconhecem exatamente as linguagens regulares.

• Fecho ε de um conjunto de estados: tudo que se alcança a partir deles seguindo só setas ε, zero ou mais vezes. O próprio conjunto está incluído. Calcula-se com uma busca em grafo.
• A construção de Thompson transforma uma regex em um AFN, peça por peça. Cada símbolo dá um autômato de 2 estados. Alternância e fecho adicionam 2 estados novos cada (um inicial e um de aceitação). A concatenação junta o estado de aceitação da primeira peça com o inicial da segunda. O tamanho cresce só linearmente: no máximo cerca de o dobro do número de símbolos e operadores. Exemplo: ab* tem 2 + (2 + 2) estados, menos 1 estado unido, então 5.
• A construção de subconjuntos transforma um AFN em AFD. Cada estado do AFD é um conjunto de estados do AFN, os lugares onde o AFN pode estar depois de ler um prefixo. Começa com o fecho do estado inicial e, para cada conjunto novo e cada símbolo, junta os destinos. Na teoria pode haver até 2^n conjuntos, mas só os alcançáveis são criados, e costumam ser poucos.
• A minimização junta estados equivalentes. Dois estados são equivalentes se nenhuma cadeia leva um à aceitação e o outro à rejeição. Comece separando estados de aceitação dos demais, depois divida qualquer grupo cujos estados vão, com o mesmo símbolo, para grupos diferentes. Quando nada mais divide, cada grupo é um estado. O AFD mínimo é único.

Tempo contra espaço

Os números foram medidos pelo mini-projeto regex-engine deste repositório. Um padrão assim num serviço que recebe entrada de usuários pode travá-lo (ReDoS). Casar com autômatos não explode desse jeito.

O que um lexer pode e não pode fazer

O lexer enxerga um lexema de cada vez e não conhece a estrutura do programa. Ele só acha erros em que nenhum padrão casa com o resto da entrada: um caractere inválido, uma string ou comentário que nunca fecha, um número malformado. Uma ordem errada de tokens é erro sintático. Um significado errado é erro semântico.

Análise sintática: gramáticas e árvores

Palavras soltas não são uma frase. 'Gato o dorme' tem as palavras certas na ordem errada. O parser confere se os tokens seguem a gramática da linguagem e monta uma árvore que mostra como as peças se encaixam.

Gramáticas livres de contexto

Uma gramática livre de contexto tem quatro partes: terminais (os tokens, as palavras de verdade), não terminais (nomes para tipos de frase), produções (regras, cada uma com um não terminal à esquerda e uma sequência de símbolos à direita) e um símbolo inicial. A linguagem da gramática é o conjunto de cadeias de terminais que se derivam do símbolo inicial.

S -> A B
A -> a
B -> b

Uma derivação começa no símbolo inicial e, a cada passo, troca um não terminal pelo lado direito de uma de suas produções. Na derivação mais à esquerda você sempre troca o não terminal mais à esquerda; na derivação mais à direita, o mais à direita. As duas podem montar a mesma árvore, só a ordem muda.

esquerda: S => A B => a B => a b
direita:  S => A B => A b => a b

Árvore de derivação e árvore sintática abstrata

A árvore de derivação (parse tree) tem um nó para cada símbolo da gramática usado, até os não terminais que existem só para codificar precedência. A árvore sintática abstrata (AST) guarda só o que importa para as fases seguintes: cada construção e suas partes. O formato da árvore já diz o que os parênteses e os níveis da gramática diziam.

árvore de derivação de 1 + 2    AST

        E                    +
      / | \                 / \
     E  +  T               1   2
     |     |
     T     F
     |     |
     F     2
     |
     1

Ambiguidade, precedência e associatividade

Uma gramática é ambígua quando uma cadeia tem mais de uma árvore de derivação. O caso clássico é E -> E + E | E * E | id: a cadeia id + id * id pode ser agrupada de duas formas. Como o compilador dá significado a partir da árvore, a ambiguidade precisa ser removida, reescrevendo a gramática ou com regras de desempate de precedência e associatividade.

E -> E + T | T       (menor precedência, perto do início)
T -> T * F | F
F -> id | ( E )       (maior precedência, perto dos operandos)

• Cada nível de precedência ganha seu próprio não terminal. Operadores de menor precedência ficam perto do símbolo inicial, e os de maior precedência mais fundo, perto dos operandos. Por isso * liga mais forte que + aqui: suas partes precisam ser agrupadas primeiro, mais fundo na árvore.
• A recursão à esquerda (E -> E + T) faz um operador ser associativo à esquerda: 1 - 2 - 3 significa (1 - 2) - 3. A recursão à direita o tornaria associativo à direita.

Erros

A recuperação mais simples é o modo pânico. Quando o parser encontra um erro, ele descarta tokens até achar um token de sincronização, em geral um delimitador como ponto e vírgula ou chave de fechamento, e então segue. Pode pular um trecho longo sem conferir, mas nunca entra em laço infinito, e deixa o compilador relatar vários erros numa só execução.

Análise descendente: descida recursiva e LL(1)

Um parser descendente (top-down) começa no símbolo inicial e tenta montar a árvore em direção aos tokens, como montar um quebra-cabeça olhando a figura da caixa. O mais simples é a descida recursiva: escreva uma função por não terminal. A pilha de chamadas da linguagem faz o papel da pilha do parser. Ele é preditivo quando o próximo token basta para escolher a produção, sem backtracking.

Dois problemas a resolver antes

Recursão à esquerda. Uma produção A -> A α faz a função de A chamar a si mesma antes de ler qualquer token. Nunca termina. A correção, para A -> A α | β, é A -> β A' e A' -> α A' | ε. A linguagem é a mesma, mas agora a repetição acontece à direita.

antes:   E -> E + T | T
depois:  E  -> T E'
         E' -> + T E' | ε

Prefixo comum. Quando duas alternativas começam igual, um parser preditivo não consegue escolher olhando um único token. A fatoração à esquerda adia a decisão: A -> α β1 | α β2 vira A -> α A' e A' -> β1 | β2. O parser lê primeiro o prefixo comum e só escolhe onde as alternativas diferem.

antes:   S -> if E then S | if E then S else S
depois:  S  -> if E then S S'
         S' -> else S | ε

FIRST e FOLLOW

Para decidir, o parser precisa de dois conjuntos. FIRST(α) é o conjunto de terminais que podem iniciar uma cadeia derivada de α, mais ε se α pode derivar a cadeia vazia. Para um corpo X1 X2 ... Xn você pega FIRST(X1) sem ε e, enquanto todos os símbolos até ali podem ser vazios, soma o FIRST do próximo. ε só entra se todos os símbolos do corpo podem ser vazios.

FOLLOW(A) é o conjunto de terminais que podem aparecer logo depois de A em alguma derivação. $ representa o fim da entrada. Para cada produção X -> α A β, some FIRST(β) sem ε; se β é vazio ou pode ser vazio, some também FOLLOW(X). O FOLLOW do símbolo inicial sempre tem $, e ε nunca aparece em um conjunto FOLLOW.

S -> A d
A -> a | ε

FIRST(A)  = { a, ε }
FIRST(S)  = { a, d }     (A pode ser vazio, então d pode iniciar S)
FOLLOW(A) = { d }

A tabela LL(1)

A tabela LL(1) M[A, t] diz qual produção usar quando o não terminal A está no topo da pilha e o próximo token é t. Uma produção A -> α entra em M[A, t] para todo terminal t em FIRST(α) e, se α pode derivar ε, também para todo terminal em FOLLOW(A). Células vazias são erros de sintaxe. O primeiro L significa que a entrada é lida da esquerda, o segundo L que se constrói uma derivação mais à esquerda, e 1 é um token de lookahead.

Uma gramática é LL(1) quando nenhuma célula recebe mais de uma produção. De forma equivalente, para cada par de alternativas A -> α | β: FIRST(α) e FIRST(β) são disjuntos e, se uma pode derivar ε, o FIRST da outra não pode encontrar FOLLOW(A).

Escalada de precedência (parser de Pratt)

Um parser de Pratt dá a cada operador um poder de ligação (binding power), um número que diz com que força ele agarra os vizinhos. A função que analisa uma expressão recebe o poder mínimo que aceita. Depois de um operando, ela só pega o próximo operador se o poder dele for maior que esse mínimo. Para um operador associativo à esquerda, o operando da direita é analisado com o mínimo igual ao poder do próprio operador, então um segundo operador igual não é engolido pelo operando da direita.

Análise ascendente: shift-reduce e LR

Um parser ascendente (bottom-up) trabalha ao contrário: começa pelos tokens e os junta em pedaços cada vez maiores até a entrada inteira virar o símbolo inicial. Pense em construir com blocos pequenos até ter o castelo todo. Ele constrói uma derivação mais à direita, de trás para frente.

Shift e reduce

Um parser shift-reduce mantém uma pilha. A cada passo ele escolhe entre dois movimentos: shift (empilhar o próximo token) ou reduce (trocar o topo da pilha, que casa com o corpo de uma produção, pela cabeça dessa produção). Um handle é um pedaço que casa com o corpo de uma produção e cuja redução é um passo de uma derivação mais à direita feita de trás para frente.

Itens LR, closure e goto

Um item LR(0) é uma produção com um ponto, como A -> α · β. O ponto marca quanto do corpo já foi visto. O closure de um conjunto de itens acrescenta os itens iniciais de todo não terminal que aparece logo depois de um ponto. O goto de um conjunto e um símbolo move o ponto sobre esse símbolo. Os conjuntos de itens são os estados do parser.

Um estado com um item completo (ponto no fim) e outro item que quer fazer shift é um conflito em LR(0). O SLR(1) resolve isso quando o token do shift não pertence ao FOLLOW do não terminal a reduzir.

Três métodos LR

Eles compartilham um só algoritmo. Diferem apenas em como decidem quando reduzir.

Conflitos

• Conflito shift/reduce: no mesmo estado e com o mesmo lookahead o parser poderia fazer shift ou reduce.
• Conflito reduce/reduce: duas produções diferentes poderiam ser reduzidas.
• O Yacc resolve o primeiro fazendo shift e o segundo escolhendo a produção que aparece primeiro na gramática, sempre com um aviso.

O exemplo famoso é o else pendente (dangling else). Com if c then S e if c then S else S, no token else um estado tem um item completo e outro que pode fazer shift de else. Fazer shift significa que cada else fica com o if mais próximo que ainda não tem else, que é a regra que as pessoas esperam.

Tradução dirigida por sintaxe

Agora o compilador conhece o formato do programa. Como ele descobre o significado? A ideia: pendurar pequenas anotações, chamadas atributos, nos nós da árvore (um tipo, um valor, um pedaço de código) e escrever regras para calculá-las. Isso é a tradução dirigida por sintaxe.

Atributos sintetizados e herdados

SDD e esquema de tradução

Uma definição dirigida por sintaxe (SDD) associa atributos a símbolos da gramática e regras a produções, sem dizer em que ordem as regras rodam. Um esquema de tradução (SDT) está mais perto do programa real: ações entre chaves são escritas em posições exatas dentro dos corpos das produções e rodam quando o parser chega a elas. A SDD é mais fácil de ler como especificação. O esquema é mais eficiente porque já carrega a ordem de avaliação.

Árvores anotadas e o grafo de dependências

Uma árvore de derivação anotada mostra o valor de todo atributo em todo nó. Com atributos sintetizados, os valores são calculados das folhas até a raiz. Para decidir a ordem no caso geral, desenhe o grafo de dependências: um nó para cada instância de atributo e uma seta de x para y quando a regra de y usa x. Qualquer ordem topológica desse grafo (cada atributo depois de tudo de que precisa) é uma ordem válida de avaliação. Se o grafo tem um ciclo, não existe ordem e a definição não pode ser avaliada.

E -> E1 + T   E.val = E1.val + T.val
E -> T        E.val = T.val
T -> num      T.val = num.value

entrada 2 + 3 + 4:  T.val=2, 3, 4  ->  E.val = 2 -> 5 -> 9

S-atribuída e L-atribuída

• S-atribuída: só atributos sintetizados. Podem ser calculados de baixo para cima durante a análise.
• L-atribuída: cada atributo é sintetizado, ou é um atributo herdado de um símbolo X do corpo que depende apenas de atributos herdados da cabeça, de atributos de símbolos à esquerda de X no corpo e de atributos do próprio X, sem ciclo. A informação flui da esquerda para a direita, então tudo pode ser avaliado numa só travessia em profundidade, como faz um parser descendente.

Construindo uma AST

Uma AST se constrói com regras sintetizadas: quando a produção representa uma construção, crie um nó; em produções auxiliares como E -> T, apenas passe o ponteiro para cima. O atributo é sintetizado, então a definição é S-atribuída e a árvore é montada de baixo para cima durante a análise. A árvore de a + b + c tem 5 nós: três folhas e dois nós +.

Quando as ações rodam?

Em um esquema de tradução, uma ação roda assim que tudo à esquerda dela foi processado. Na árvore de derivação, as ações contam como folhas extras, e a ordem é uma travessia em profundidade, da esquerda para a direita. Uma ação colocada depois de um não terminal recursivo só roda depois que toda a subárvore desse não terminal foi percorrida.

T -> x { print('x') } T { print('y') }
T -> ε

entrada: x x     saída: x x y y

Atributos em um parser de descida recursiva

Em um parser de descida recursiva, cada não terminal é uma função. Os atributos herdados viram parâmetros e os sintetizados viram valores de retorno. Depois que a recursão à esquerda é removida, o operando da esquerda de um operador é reconhecido por outra função. Para manter a associatividade à esquerda, o valor calculado até ali desce como atributo herdado, e o resultado final volta para cima como atributo sintetizado quando se chega à produção ε.

// E -> T R      R -> - T R | ε
function R(acc: number): number {
	if (next() === "-") {
		match("-");
		return R(acc - T());   // (acc - t), não (acc - (resto))
	}
	return acc;              // ε: devolve o resultado para cima
}

Geração de código intermediário

A árvore sintática é boa para entender o programa, mas não para executá-lo nem para deixá-lo rápido. Por isso o compilador a transforma numa linguagem simples e plana, que não é nem fonte nem máquina: o código intermediário.

Código de três endereços

No código de três endereços cada instrução tem no máximo um operador do lado direito, como em x = y op z. Uma expressão longa é desmontada, e o compilador inventa nomes temporários para os valores intermediários. Um endereço pode ser um nome do programa, uma constante ou um temporário.

a = b * c + d

t1 = b * c
t2 = t1 + d
a  = t2

Então o número de temporários é igual ao número de nós de operador da árvore. Partir de um DAG (abaixo) cria menos, porque subexpressões repetidas viram um só nó.

Como guardar: quádruplas e triplas

As triplas economizam temporários, mas são difíceis de mover: quando uma tripla muda de lugar, toda referência a ela muda. As triplas indiretas resolvem isso.

Atribuição única estática (SSA)

Na forma SSA toda variável é atribuída em exatamente um lugar do texto do programa. Cada atribuição nova cria uma versão nova (x1, x2, e assim por diante). Quando dois caminhos com versões diferentes se encontram, depois de um if ou no topo de um laço, uma função φ cria uma versão nova cujo valor é uma ou outra, conforme o caminho por onde o controle chegou. Isso deixa claro qual definição chega a cada uso.

x1 = 1
if c goto L1 else L2
L1: x2 = 2
L2: x3 = φ(x1, x2)    // x1 se pulamos L1, x2 se passamos por ele

Tipos e conversões

Uma conversão pode ser explícita (o programador escreve um cast) ou implícita (o compilador a insere sozinho, o que se chama coerção). Muitas linguagens permitem só coerções de alargamento (widening), que preservam toda a informação, como inteiro para ponto flutuante. No código intermediário a coerção é uma instrução de conversão como t1 = (float) i.

DAG: compartilhando trabalho repetido

Um DAG de expressão (grafo acíclico dirigido) é como a árvore sintática, mas um nó pode ter mais de um pai: uma subexpressão que aparece várias vezes é guardada uma vez só. Antes de criar um nó, o compilador procura um nó existente com o mesmo operador e os mesmos filhos. Folhas iguais também são compartilhadas. Isso expõe as subexpressões comuns, que podem ser calculadas uma única vez.

(x + y) * (x + y)

árvore: 7 nós           DAG: 4 nós
      *                     *
     / \                   / \
    +   +                  \ /
   / \ / \                  +
  x  y x  y                / \
                          x   y

Arrays

Com armazenamento por linhas (row-major) e índices começando em 0, o endereço de A[i][j] é base + (i · n2 + j) · w. Aqui n2 é o número de colunas e w a largura de um elemento. O número de linhas não aparece, só o número de colunas.

A tem 5 linhas, 3 colunas, w = 4 bytes, base = 200
endereço de A[2][1] = 200 + (2 * 3 + 1) * 4 = 228

Booleanos e saltos

No código de saltos (jumping code) o valor de uma expressão booleana não é guardado em variável. Ele é o lugar onde o controle termina. Em B1 || B2, se B1 é verdadeiro o controle salta direto para a saída verdadeira; em B1 && B2, se B1 é falso ele salta direto para a saída falsa. Operandos que não podem mudar o resultado nunca são avaliados. Isso é a avaliação em curto-circuito.

Um while vira três peças: o teste no topo com um salto de saída para logo depois do laço, o corpo e um salto incondicional de volta ao teste. Um if sem else vira um teste que pula só o comando controlado.

while (i < n) i = i + 1;

L1: ifFalse i < n goto L2
    i = i + 1
    goto L1
L2: ...

Backpatching

Em uma só passada, um salto é escrito antes de o destino existir. O backpatching deixa o destino em branco e põe a instrução numa lista: a truelist tem os saltos tomados quando a condição é verdadeira, a falselist os tomados quando é falsa. Quando o destino é conhecido, todos os saltos da lista são preenchidos de uma vez. Para B1 || B2: a falselist de B1 é preenchida com o início de B2; a truelist do todo é a união das duas truelists; a falselist do todo é a falselist de B2.

Ambientes de execução: layout da memória e chamadas

Enquanto o programa roda, onde ficam as coisas dele? Pense na sua carteira na escola. Algumas coisas ficam coladas nela para sempre (a etiqueta com seu nome), outras ficam numa bandeja que cresce e diminui em ordem (os livros de hoje), e outras ficam numa caixa grande no canto, de onde você tira e põe coisas em qualquer ordem. Os programas têm os mesmos três tipos de lugar.

As quatro áreas

endereço baixo
+--------------------+
| código             |  tamanho conhecido na compilação
+--------------------+
| dados estáticos    |  tamanho conhecido na compilação
+--------------------+
| heap               |  cresce em direção ao
|               v    |  espaço livre
|   (espaço livre)   |
|               ^    |  cresce em direção ao
| pilha              |  espaço livre
+--------------------+
endereço alto

Código e dados estáticos têm tamanho conhecido na compilação. A pilha e o heap mudam de tamanho enquanto o programa roda. Colocá-los em pontas opostas da mesma região livre deixa qualquer um crescer enquanto sobrar espaço entre eles.

• Alocação estática: o endereço é escolhido na compilação (ou no link). Serve para dados que existem exatamente uma vez durante toda a execução, como variáveis globais e constantes.
• Pilha: dados cuja vida está ligada a uma chamada.
• Heap: dados cuja vida não depende das chamadas, e dados cujo tamanho só se conhece na execução.

Registros de ativação

Toda vez que um procedimento é chamado, um registro de ativação (stack frame) é empilhado. Quando a chamada retorna, ele é desempilhado. Ele guarda os dados daquela execução: os parâmetros reais, o valor retornado, o elo de controle (control link), o elo de acesso (access link), o estado salvo da máquina (incluindo o endereço de retorno), as variáveis locais e os temporários. É isso que torna a recursão possível: cada chamada tem suas próprias variáveis locais.

Elo de controle e elo de acesso

Os dois coincidem só quando quem chamou é o próprio procedimento que envolve. Com procedimentos aninhados e escopo estático, um nome que pertence a um procedimento externo é achado pelo par (diferença de profundidade de aninhamento, deslocamento no registro). O código segue tantos elos de acesso quanto a diferença entre a profundidade do procedimento que usa o nome e a do que o declara.

procedure main (profundidade 1): var x
  procedure a (profundidade 2)
    procedure b (profundidade 3): usa x

chamadas: main -> a -> b
b usa x, declarado em main: 3 - 1 = 2 elos de acesso
b --> a --> main  (depois o deslocamento de x)

Closures quebram a regra da pilha

A pilha supõe que os dados de uma chamada morrem quando a chamada retorna. Uma closure quebra isso: ela lembra o ambiente onde foi criada e pode ser chamada depois que a função externa terminou.

function makeCounter() {
	let n = 0;
	return () => { n = n + 1; return n; };
}
const next = makeCounter();
next(); next();   // n precisa continuar existindo aqui

Por isso as variáveis capturadas vivem em um ambiente no heap, liberado só quando nenhuma closure aponta para ele.

Dois erros clássicos da memória manual

• Vazamento de memória (memory leak): esquecer de liberar o que não será mais usado. O programa continua correto, mas usa cada vez mais memória.
• Ponteiro pendente (dangling pointer): liberar o que ainda será usado. O programa então lê ou escreve em memória que pode já pertencer a outro objeto.

Alocação no heap e coleta de lixo

O heap é uma caixa grande onde o programa pede pedaços de memória de qualquer tamanho. Alguém precisa lembrar quais pedaços estão livres e quais estão ocupados, e limpar quando um pedaço deixa de ser necessário. Vamos ver como.

Achando um pedaço livre

Os pedaços livres ficam numa lista livre. O first fit pega o primeiro pedaço grande o bastante. É rápido, mas tende a quebrar pedaços grandes. O best fit pega o menor pedaço que seja grande o bastante. Guarda pedaços grandes para pedidos grandes, mas a busca é mais longa e deixa sobras minúsculas. Os dois tentam limitar a fragmentação: o espaço livre total basta, mas está espalhado em pedaços pequenos demais para usar.

lista livre: [40] -> [10] -> [25] -> [18]
pedido: 12 bytes

first fit: [40]  (primeiro grande o bastante, sobram 28)
best fit:  [18]  (menor grande o bastante, sobram 6)

Coleta de lixo

Um coletor de lixo (garbage collector) libera memória automaticamente: ele recupera só objetos que não podem mais ser alcançados, então elimina o erro do ponteiro pendente. As raízes são os lugares de onde o programa pode partir (variáveis da pilha, globais). Um objeto está vivo se um caminho de ponteiros leva até ele a partir de uma raiz.

Contagem de referências

Cada objeto conta quantos ponteiros se referem a ele. Quando a contagem chega a zero, o objeto é liberado na hora, e os objetos para os quais ele apontava têm a contagem diminuída, possivelmente em cadeia. A fraqueza clássica são os ciclos: objetos que apontam um para o outro mantêm contagem positiva mesmo quando nenhuma raiz os alcança, então vazam. Os coletores por rastreamento não têm esse problema, porque usam alcançabilidade a partir das raízes.

raízes: p -> A -> B
        F <-> E   (apontam um para o outro, ninguém aponta para eles)

p = null:  A contagem 0 -> liberado, depois B contagem 0 -> liberado
E e F ficam com contagem 1 cada -> vazam na contagem de referências

Mark-and-sweep e cópia

Coleta geracional

A maioria dos objetos morre jovem. Por isso um coletor geracional coleta a geração jovem com frequência, recuperando muito lixo com pouco trabalho. Para uma coleta parcial ser segura, todo ponteiro que entra na região jovem vindo de fora deve ser tratado como raiz. O coletor mantém um conjunto lembrado (remembered set), atualizado por uma barreira de escrita (write barrier), um pedacinho de código que roda em toda atribuição de ponteiro. Se um objeto velho é alterado para apontar para um jovem, o conjunto lembrado registra isso, e o objeto jovem não é liberado por engano.

Coleta incremental

Um coletor incremental marca um pouco de cada vez, misturado com o programa em execução, que continua mudando o grafo de objetos. O perigo: o programa guarda um ponteiro para um objeto ainda não marcado dentro de um objeto que já foi varrido e remove o caminho original. O objeto vivo escapa da marcação e é liberado por engano. Uma barreira de escrita anota essas escritas, então o destino é marcado ou o objeto alterado é varrido de novo. O preço é um pouco de lixo flutuante (floating garbage), objetos mortos que sobrevivem a mais um ciclo.

Geração de código

O último grande passo: do código intermediário para instruções que a máquina consegue executar. O gerador de código tem três tarefas principais: seleção de instruções (quais instruções de máquina usar), alocação e atribuição de registradores (quais valores ficam em registradores, e em qual) e ordenação de instruções (em que ordem). Registradores são a memória mais rápida e mais escassa da máquina, então decidir o que fica neles pesa muito na velocidade. Achar a melhor atribuição é NP-completo, então na prática os compiladores usam heurísticas como a coloração de grafos.

Máquinas de pilha e máquinas de registradores

Em uma máquina de pilha as instruções não nomeiam seus operandos. Elas pegam os operandos do topo da pilha e empilham o resultado. O código de uma expressão é a sua forma pós-fixa: primeiro o operando da esquerda, depois o da direita, depois o operador. Em uma máquina de registradores cada instrução nomeia onde está cada valor, como em MUL R1, R1, R2.

Blocos básicos e o grafo de fluxo

Um bloco básico é uma sequência máxima de instruções consecutivas com uma única entrada (a primeira instrução) e uma única saída (a última). Dentro dele não há saltos nem destinos de salto, então as instruções sempre rodam juntas e em ordem. Para achar os blocos, marque os líderes: a primeira instrução, toda instrução que é destino de um salto e toda instrução que vem logo depois de um salto. Um bloco vai de um líder até a instrução anterior ao próximo líder, então o número de blocos é igual ao número de líderes. Os blocos são os nós do grafo de fluxo, e as arestas dizem qual bloco pode rodar depois de qual.

1: i = 0
2: if i > 9 goto 5
3: i = i + 1
4: goto 2
5: print i

líderes: 1 (primeira), 2 (destino de 4), 3 (depois de um salto), 5 (destino de 2)
blocos: [1] [2] [3-4] [5]  ->  4 blocos

Vivacidade dentro de um bloco

Uma variável está viva em um ponto se o valor dela ali ainda pode ser usado antes de ser sobrescrito. Dentro de um bloco, ande para trás. Comece pelo conjunto vivo na saída. Para cada instrução x = y op z, primeiro remova x, depois adicione y e z. O gerador usa isso para saber quando um registrador pode ser reaproveitado.

vivas na saída: {z}
3: z = y + 1      antes de 3: ({z} - z) + y = {y}
2: y = x * 2      antes de 2: ({y} - y) + x = {x}
1: x = x + 1      antes de 1: ({x} - x) + x = {x}

Um modelo de custo

Um modelo simples dá a cada instrução o seu tamanho em palavras: 1 pela instrução mais o custo do modo de endereçamento de cada operando. Registradores custam 0, endereços de memória e constantes custam 1 porque ocupam uma palavra extra. Assim a seleção de instruções prefere manter valores em registradores e evitar loads e stores inúteis.

Registradores: coloração e o número de Ershov

Na alocação por coloração de grafos, cada variável é um nó, cada interferência (duas variáveis vivas ao mesmo tempo) é uma aresta, e cada registrador é uma cor. Vizinhos precisam de cores diferentes. O menor número de registradores que funciona sem derramar é o número cromático do grafo. Se a máquina tem menos registradores, alguma variável é derramada (spilled): ela vive na memória, com loads e stores em volta de cada uso.

Para uma árvore de expressão, o número de Ershov diz quantos registradores bastam para avaliá-la sem guardar temporários. Folhas valem 1. Um nó cujos filhos têm números diferentes recebe o maior. Se os números são iguais, ele recebe esse valor mais 1. O truque é avaliar primeiro o filho mais exigente: o resultado dele então ocupa só um registrador enquanto o outro filho é calculado.

(a + b) * c        a+b: 1,1 iguais -> 2     raiz: 2 e 1 -> 2
(a + b) * (c + d)  dois filhos 2, iguais -> 3

Descritores e peephole

O gerador simples mantém duas tabelas. O descritor de registradores diz quais variáveis têm o valor atual em cada registrador. O descritor de endereços diz em quais lugares (registradores, memória) está o valor atual de cada variável. Antes de reutilizar um registrador, o gerador os consulta: se o registrador guarda a única cópia de um valor vivo, ele primeiro emite um store. No fim de um bloco, toda variável viva cuja cópia na memória está desatualizada também é guardada.

Um otimizador peephole olha por uma pequena janela deslizante de poucas instruções e troca o que encontra por algo mais curto ou mais rápido. Por exemplo, remove um load logo depois de um store no mesmo endereço, remove código inalcançável, encurta um salto para um salto e troca x * 2 por x + x. Cada melhoria pode abrir espaço para outras, então a passada costuma ser repetida.

Otimizações independentes de máquina

Uma otimização deixa o programa mais rápido ou menor sem mudar o que ele faz. 'Independente de máquina' quer dizer que ela trabalha sobre o código intermediário, então não depende do processador.

Truques locais simples

As otimizações funcionam em cadeia: uma prepara o terreno para a próxima.

Subexpressões comuns

Uma ocorrência de expressão é uma subexpressão comum se foi calculada antes e nenhum de seus operandos mudou desde então. Uma atribuição a um operando mata a expressão. A versão local olha um bloco básico; a versão global usa a análise de expressões disponíveis para reaproveitar valores entre blocos.

(1) t1 = a + b
(2) t2 = a + b    reaproveita t1 (a, b não mudaram)
(3) a  = t2 * 2    mata a + b
(4) t3 = a + b    precisa ser calculada de novo

Laços: onde o tempo vai

Os programas gastam a maior parte do tempo em laços, então as otimizações de laço compensam. Um comando é invariante de laço quando seus operandos são constantes, ou são definidos só fora do laço, ou são definidos por outros comandos invariantes. A movimentação de código o leva para o pré-cabeçalho (preheader), um bloco logo antes do laço, para que rode uma vez em vez de uma vez por iteração. Uma variável de indução muda por um passo fixo a cada iteração, como i e t = i * 4. Essas são tratadas por redução de força (strength reduction), que troca a multiplicação por uma adição feita a cada passo, e não pela movimentação de código.

antes:   L: t1 = n - 2      depois:  t1 = n - 2      (movido para fora)
            t2 = i * 4               L: t2 = i * 4
            ...                           ...

Análise de fluxo de dados e laços

Para saber o que é seguro, o compilador faz perguntas sobre o grafo de fluxo inteiro: 'qual atribuição pode chegar até aqui?', 'esta variável ainda vai ser usada?', 'este valor já foi calculado em todos os caminhos?'. A análise de fluxo de dados responde a essas perguntas com uma receita comum.

O arcabouço

• Uma direção: para frente (a partir da entrada) ou para trás (a partir da saída).
• Funções de transferência: como cada bloco muda a informação.
• Um operador de encontro (meet): como combinar a informação que vem de vários caminhos (união ou interseção).
• A análise é conservadora: na dúvida, assume o pior, então as otimizações que a usam continuam seguras.

A união serve para as perguntas 'existe algum caminho'. A interseção serve para as de 'em todos os caminhos', porque a eliminação global de subexpressões comuns só é segura se o valor está pronto por qualquer caminho de chegada.

Definições alcançantes

Uma definição d alcança um ponto se existe um caminho de d até ele sem outra definição da mesma variável no meio. Para cada bloco, gen guarda as definições do bloco que sobrevivem até o fim dele, e kill guarda as outras definições das mesmas variáveis. As equações são OUT[B] = gen[B] ∪ (IN[B] − kill[B]) e IN[B] = ∪ OUT[P] sobre os predecessores P. Elas são resolvidas repetindo até nada mais mudar.

B1: d1: x = 1      B2: d2: x = x + 1 ; if x < 9 goto B2     B3: d3: y = x
arestas: B1->B2, B2->B2, B2->B3

IN[B2]  = OUT[B1] ∪ OUT[B2] = {d1} ∪ {d2} = {d1, d2}
IN[B3]  = OUT[B2] = {d2}      (d2 mata d1: mesma variável x)

Variáveis vivas

Percorra o código para trás. Para x = y op z, o conjunto antes dela é (conjunto depois − {x}) ∪ {y, z}: a definição mata x, e os usos tornam y e z vivas. Uma variável está viva na entrada de um bloco se é lida no bloco antes de ser redefinida, ou se está viva na saída e não é redefinida nele. O resultado orienta a eliminação de código morto e a alocação de registradores.

Expressões disponíveis

Uma expressão está disponível em um ponto se, em todo caminho da entrada até ele, a expressão foi calculada e nenhum operando foi atribuído depois do último cálculo. A ordem importa dentro de um bloco: calcular e depois matar deixa a expressão indisponível na saída.

         B1: t1 = a + b
          /           \
 B2: t2 = a + b    B3: d = t1 - c
     a = t2 * 2            |
          \           /
           B4: t3 = a + b

por B3: a + b está disponível.
por B2: a mudou depois, então foi morta.
Interseção dos dois caminhos: NÃO disponível em B4.

Dominadores e laços naturais

Um nó d domina n se todo caminho da entrada até n passa por d. Uma aresta de retorno (back edge) é uma aresta cujo destino domina a origem. O destino é o cabeçalho do laço. O laço natural de uma aresta de retorno é o cabeçalho mais todos os nós que alcançam a origem da aresta sem passar pelo cabeçalho, achados andando para trás pelos predecessores a partir da origem. Blocos onde o controle sai do laço não fazem parte dele.

B1 -> B2 -> B3 -> B4 -> B2      (B4 -> B2 é a aresta de retorno)
      B2 -> B5

B2 domina B4, então o cabeçalho é B2.
Laço = {B2, B3, B4}.  B5 fica fora (a saída).

Paralelismo em nível de instrução e localidade

Um processador moderno não faz uma coisa de cada vez. E a memória é muito mais lenta que o processador, então o lugar onde os dados ficam importa. O compilador ajuda nas duas coisas.

Pipelines

Um processador com pipeline corta o trabalho de uma instrução em estágios: busca, decodificação, execução, acesso à memória e escrita do resultado. Ele começa a próxima instrução antes que a anterior termine. Esse é o tipo mais simples de paralelismo em nível de instrução.

tempo ->  1    2    3    4    5    6
instr 1   B    D    E    M    W
instr 2        B    D    E    M    W
instr 3             B    D    E    M    W

Ele é limitado por dependências: uma instrução que precisa do resultado da anterior, ou um desvio cujo destino ainda não se conhece, faz o pipeline esperar.

Dependências de dados

Duas instruções dependem uma da outra quando usam o mesmo local e pelo menos uma delas o escreve. Há três tipos, e qualquer escalonador, no compilador ou no processador, só pode reordenar ou sobrepor instruções que não estejam presas por eles, nem por dependências de controle.

Laços e iterações paralelas

Uma dependência é carregada pelo laço (loop-carried) quando duas iterações diferentes usam o mesmo local de memória e pelo menos uma delas escreve. Se não há nenhuma, as iterações são independentes e podem ser dadas a processadores diferentes, em qualquer ordem. A análise de dependência de dados compara os índices das escritas com os das leituras e escritas das outras iterações. Acessos só de leitura nunca criam dependência.

for (i = 1; i < n; i++) a[i] = a[i-1] + 1;   // carregada: precisa da iteração anterior
for (i = 1; i < n; i++) a[i] = b[i] + 1;     // independente: pode rodar em paralelo

Localidade

O cache traz de uma vez uma linha inteira de memória vizinha. Localidade espacial é usar dados próximos na memória em momentos próximos, de modo que todo elemento trazido seja usado. Em C, uma matriz é guardada linha por linha (row-major). Descer por uma coluna dá um salto longo na memória a cada passo. A troca de laços (loop interchange) inverte os laços aninhados para que o laço interno percorra a dimensão guardada de forma contígua.

// lento: o laço interno salta uma linha inteira a cada passo
for (j = 0; j < N; j++) for (i = 0; i < N; i++) sum += m[i][j];
// rápido: o laço interno anda ao longo de uma linha
for (i = 0; i < N; i++) for (j = 0; j < N; j++) sum += m[i][j];

Interpretadores, máquinas virtuais e JIT

Começamos com a diferença entre compiladores e interpretadores. As linguagens reais misturam as duas ideias, em etapas: de um interpretador simples e lento para um rápido, e depois para uma máquina que compila enquanto roda.

Interpretador que percorre a árvore

Um interpretador que percorre a árvore (tree-walking) executa o programa visitando recursivamente os nós da árvore sintática. É a forma mais simples de implementar uma linguagem. Mas cada operação paga por seguir ponteiros, escolher o código pelo tipo do nó e procurar nomes em ambientes.

Bytecode e máquinas virtuais

Bytecode é uma lista compacta e plana de instruções para uma máquina imaginária, a máquina virtual (VM). Os nomes já foram trocados por números, o que melhora a localidade e reduz o trabalho por operação.

No mini-projeto bytecode-vm deste repositório, uma VM ficou cerca de 2 vezes mais rápida que o interpretador de árvore em um laço e de 3 a 5 vezes mais rápida em uma função recursiva, usando cerca de 2 MiB de memória contra 58 a 98 MiB. São os resultados medidos da execução registrada nele.

VM de pilha ou de registradores?

• VM de pilha: as instruções trocam valores por uma pilha de operandos. Quem produz valor empilha, quem consome desempilha. As instruções são curtas e fáceis de gerar a partir da árvore, em pós-ordem.
• VM de registradores: cada instrução nomeia suas fontes e o destino. Precisa de menos instruções para o mesmo trabalho, mas cada uma é maior e o compilador é mais difícil de escrever.

O bytecode de pilha é a expressão em pós-fixa. As instruções binárias desempilham primeiro o operando da direita, depois o da esquerda, e empilham o resultado. Isso importa para subtração e divisão.

O laço de despacho

O núcleo de uma VM é o laço de despacho (dispatch loop): ler o opcode para o qual o ponteiro de instrução aponta, avançar o ponteiro e saltar para o código que executa esse opcode. Esse custo fixo é pago uma vez por instrução executada, não por instrução escrita, então domina o tempo dos laços. Se o corpo de um laço tem 5 instruções e roda 100 vezes, o laço paga esse custo 500 vezes. Truques como threaded code e superinstruções o reduzem.

Compilação JIT

Um compilador JIT (just-in-time) traduz para código de máquina, enquanto o programa roda, os pedaços que o perfil (profile) mostra serem quentes (mais usados). Compilar também gasta tempo. Por isso as VMs usam camadas (tiers): interpretam primeiro, compilam rápido depois e otimizam pesado só o que continua quente. O preço é o aquecimento (warm-up): o programa começa lento e vai ficando mais rápido. A compilação antecipada (AOT, ahead-of-time) começa rápido, mas não conhece o comportamento real do programa.

Especulação e desotimização

O JIT pode apostar. Ele gera código rápido para o caso que o perfil mostrou ser comum e o protege com guardas (guards), testes da suposição. Quando uma guarda falha, a VM desotimiza: move a execução, até no meio de uma função, para a versão genérica, reconstruindo o estado que essa versão espera. Assim, apostas agressivas nunca quebram a regra de que o programa deve continuar se comportando igual.

chamada add(a, b)
   |
 [guarda: os dois são inteiros?] -- sim --> soma de máquina rápida
   |
   não
   v
 desotimiza --> versão genérica (trata strings, floats...)

Juntando tudo

Você viu a linha de fábrica inteira. Aqui está ela numa tabela só, com a saída típica de cada estação e a ideia típica para lembrar.

Erros a evitar

• Achar que um lexer confere parênteses balanceados: não confere, um autômato finito não conta sem limite.
• Esquecer a condição do FOLLOW quando uma produção pode ser vazia na checagem LL(1).
• Misturar o elo de controle (quem chamou) com o elo de acesso (quem envolve no texto).
• Usar união onde a pergunta diz 'em todos os caminhos': isso pede interseção.
• Reordenar um laço ou comandos sem checar as dependências.
• Achar que escopo dinâmico e escopo estático dão a mesma resposta: não dão quando uma função é chamada de um lugar onde os nomes dela têm outro significado.

Como as ideias se conectam

• Uma regex vira um AFN, depois um AFD: a mesma máquina roda o lexer e o motor de regex.
• Uma gramática dá a árvore; atributos na árvore dão o significado; a árvore vira código intermediário plano.
• O mesmo grafo de fluxo alimenta as análises de fluxo de dados, as otimizações e a alocação de registradores.
• Um interpretador de árvore, uma VM de bytecode e um JIT rodam a mesma linguagem com custos diferentes.
• A notação pós-fixa aparece três vezes: no tradutor simples, no código de máquina de pilha e no bytecode de pilha.