LRM Prof. Mantovani ← Aulas da disciplina
Semana 12 · Aula 12 de 14

Geração de código e organização do computador

A fase final: traduzir a RI para a máquina-alvo, com seleção de instruções, alocação de registradores e a influência da organização do computador.

📚 Compiladores🧪 1 simulador(es)📝 mini-quiz ao final
Objetivos da aula

O que você vai aprender

1

Traduzir código de três endereços para instruções da máquina-alvo.

2

Explicar a alocação de registradores e o spilling.

3

Modelar a alocação de registradores como coloração de grafos.

4

Relacionar a geração de código à arquitetura do processador.

1 · Motivação

Da forma neutra à máquina real

O TAC é elegante e independente de máquina — mas o processador não o entende. A geração de código traduz cada instrução de três endereços para o assembly real do alvo, lidando com suas restrições: poucos registradores, conjunto fixo de instruções, modos de endereçamento.

É aqui que o compilador finalmente "aterrissa" na arquitetura, e decisões como quais valores ficam em registradores afetam diretamente o desempenho do programa.

💡
É a última fase obrigatória: depois dela, há código que a máquina pode executar (após montagem e ligação).
2 · Mapa

O fim do pipeline

A geração de código fecha a jornada iniciada no scanner:

RI
TAC→Seleção de
instruções→Alocação de
registradores→Código-alvo
assembly

Por depender da máquina, é a parte central do back-end: o mesmo TAC gera assembly diferente para x86, ARM ou RISC-V.

3 · Conceito

Seleção de instruções

Seleção de instruções. Mapeamento de cada operação da RI para uma ou mais instruções da máquina-alvo que produzam o mesmo efeito.

Uma instrução de três endereços simples pode exigir várias instruções de máquina (carregar operandos, operar, guardar resultado), ou uma única instrução poderosa pode cobrir várias da RI.

4 · Explicação

De uma soma TAC ao assembly

A instrução TAC t = a + b tipicamente exige carregar os operandos da memória para registradores, somar e guardar:

; máquina-alvo com registradores R LOAD R1, a LOAD R2, b ADD R3, R1, R2 STORE t, R3

Quatro instruções de máquina para uma de três endereços. Reduzir esse número (mantendo valores em registradores) é o papel da otimização e da alocação.

5 · Exemplo

Gerando código para uma expressão

O TAC de (a + b) * c é t1 = a + b; t2 = t1 * c. Em assembly didático:

; t1 = a + b LOAD R1, a LOAD R2, b ADD R1, R1, R2 ; reusa R1 para t1 ; t2 = t1 * c LOAD R2, c MUL R1, R1, R2 ; R1 agora guarda t2 STORE t2, R1

Com reuso esperto, bastaram dois registradores.

6 · Interativo

Traduza TAC passo a passo

Passo 1
Os operandos a e b estão na memória; o ALU só opera em registradores. Precisamos carregá-los.
Passo 2
Emite LOAD R1, a e LOAD R2, b: traz os valores para registradores.
Passo 3
Emite ADD R3, R1, R2: soma e deixa o resultado em R3.
Passo 4
Emite STORE t, R3: grava o resultado de volta na memória (variável t).
Passo 5
Se R3 fosse necessário em seguida, poderíamos manter o valor lá e evitar o STORE/LOAD.
7 · Conceito

Alocação de registradores

Alocação de registradores. Decisão sobre quais valores ficam nos registradores (rápidos, porém poucos) e quais vão para a memória. Quando faltam registradores, alguns valores são "derramados" — o spilling.

Registradores são a memória mais rápida do processador, mas existem em número pequeno (dezenas). Usá-los bem é decisivo para o desempenho.

8 · Explicação

Spilling: quando faltam registradores

Spilling. Mover um valor de um registrador para a memória (e recarregá-lo depois) porque não há registradores suficientes para todos os valores vivos ao mesmo tempo.

O spilling tem custo: cada LOAD/STORE extra é lento comparado a operar direto em registrador. Um bom alocador minimiza spills, mantendo nos registradores os valores mais usados.

9 · Analogia

A bancada do marceneiro

🪚 Analogia
Os registradores são a bancada de trabalho: cabem poucas ferramentas, mas tudo ali é alcançável num instante. A memória é o armário no fundo da oficina: cabe tudo, mas buscar leva tempo. Spilling é guardar uma ferramenta no armário para liberar espaço na bancada — e ter de ir buscá-la de novo quando precisar. O bom marceneiro deixa na bancada só o que usa o tempo todo.
10 · Comparação

RISC × CISC

RISCCISC
InstruçõesPoucas, simples, tamanho fixoMuitas, complexas, tamanho variável
Acesso à memóriaSó via load/storeOperações direto na memória
RegistradoresMuitosMenos
ExemplosARM, RISC-V, MIPSx86

O estilo da arquitetura muda profundamente o código gerado: em RISC, tudo passa por registradores; em CISC, instruções acessam a memória diretamente.

11 · Fluxo

Registradores e a hierarquia de memória

Registradores
+ rápido→Cache L1/L2→RAM→Disco
+ lento

Quanto mais perto do processador, mais rápido e mais escasso. Manter valores em registradores (e evitar idas à memória) é a base da geração de código eficiente.

12 · Aprofundamento

Alocação como coloração de grafos

Grafo de interferência. Grafo em que cada nó é uma variável (ou temporário) e há uma aresta entre duas variáveis que estão "vivas" ao mesmo tempo — não podem compartilhar registrador.

Atribuir registradores vira colorir esse grafo com k cores (k = número de registradores), de modo que vizinhos tenham cores diferentes. Se não couber em k cores, algumas variáveis sofrem spilling.

🔑
Variáveis que vivem ao mesmo tempo interferem; cores distintas garantem que não dividam o mesmo registrador.
13 · Interativo

Verifique seu entendimento

O que acontece quando há mais valores vivos do que registradores disponíveis?

Faltando registradores, valores são derramados (spill) para a memória e recarregados quando necessário.
14 · Caso prático

Compilando com poucos registradores

Suponha o TAC t1 = a + b; t2 = c + d; t3 = t1 * t2 e apenas 2 registradores. As variáveis t1 e t2 ficam vivas simultaneamente até t3, mais os operandos — não cabem todas.

⚠️
Com 2 registradores, será preciso guardar t1 na memória (spill) enquanto se calcula t2, e recarregá-lo para o produto. Com 3+ registradores, nenhum spill seria necessário. A escassez custa instruções extras.
15 · Erros comuns

Tropeços na geração de código

⚠️
Confundir temporários do TAC com registradores. t1, t2 são lógicos; a alocação real só acontece nesta fase.

Ignorar a escassez de registradores. Assumir registradores infinitos gera código que não roda na máquina real.

Spilling excessivo. Derramar valores muito usados degrada o desempenho.

Esquecer a arquitetura. Gerar código x86 supondo o modelo RISC (ou vice-versa) produz assembly inválido.
16 · Dicas

Gerando bom código de máquina

✅
Mantenha em registradores os valores mais usados e de vida curta; evite idas desnecessárias à memória.

Use o grafo de interferência para alocar: vizinhos (vivos juntos) recebem registradores diferentes.

Quando o spilling for inevitável, derrame o valor menos usado dali em diante.

Conheça o alvo: número de registradores, RISC/CISC e modos de endereçamento moldam o melhor código.
17 · Interativo

Pense antes de revelar

Por que a alocação de registradores é modelada como coloração de grafos, e não como uma simples ordenação?
Porque o problema não é colocar variáveis em sequência, mas sim decidir quais podem compartilhar o mesmo registrador sem conflito. Duas variáveis podem usar o mesmo registrador se nunca estão vivas ao mesmo tempo. Construímos um grafo de interferência (aresta = vivas simultaneamente) e o problema vira: pintar os nós com k cores (k registradores) sem que vizinhos tenham a mesma cor — exatamente a coloração de grafos. Se k cores não bastam, algumas variáveis sofrem spilling. Ordenar não capturaria essa relação de conflito simultâneo.
18 · Flashcards

Revise os termos

Seleção de instruçõesvirar
Mapear cada operação da RI para instruções equivalentes da máquina-alvo.
Alocação de registradoresvirar
Decidir quais valores ficam nos poucos registradores e quais vão à memória.
Spillingvirar
Derramar um valor para a memória por falta de registradores; custa LOAD/STORE extras.
Grafo de interferênciavirar
Nós = variáveis; arestas = vivas ao mesmo tempo. Colori-lo com k cores = alocar k registradores.
19 · Conexões

Como esta aula se liga ao curso

  • Consome a aula 10 (RI): o TAC é a entrada da geração de código.
  • Usa a aula 11 (execução): chamadas e variáveis locais viram acessos ao frame na pilha.
  • Realiza a aula 2 (back-end): é aqui que a dependência da máquina se concretiza.
  • Conecta a Organização de Computadores: registradores, RISC/CISC e cache definem o código gerado.
20 · Síntese

O essencial da aula

🔑
A geração de código mapeia o TAC para instruções do alvo (seleção de instruções). Registradores são rápidos e escassos: a alocação de registradores decide o que cabe neles, e o que sobra sofre spilling para a memória. O problema é modelado como coloração de grafos. O back-end depende da arquitetura (RISC/CISC, nº de registradores, cache).
Mão na massa · colaborativo

Atividade em grupo · Compilando à mão

Em trios, traduzam TAC para um assembly didático.

⏱️ 25 min👥 trios🧩 laboratório

Roteiro

  1. Gerem o TAC de (a + b) * c (usem o simulador da aula 10).
  2. Traduzam cada instrução de três endereços para LOAD/ADD/MUL/STORE.
  3. Contem quantos registradores foram necessários.
  4. Discutam o que aconteceria com apenas 2 registradores (spilling).
Tradutorgera o assembly
Alocadorgerencia os registradores
Analistaavalia o spilling
📤 Entrega: Assembly didático da expressão + contagem de registradores usados.
Teste seu conhecimento

Mini-quiz · Aula 12

20 questões sobre esta aula. Escolha e veja a explicação na hora.

0/20

📌 Resumo — leve isto para a prova

  • A geração de código mapeia o TAC para instruções do alvo (seleção de instruções).
  • Registradores são rápidos e escassos; o que não cabe sofre spilling para a memória.
  • A alocação de registradores é modelada como coloração de um grafo de interferência.
  • O back-end depende da arquitetura: RISC/CISC, número de registradores e cache.
  • Manter valores muito usados em registradores é a chave do desempenho.