Aula 22: Alocação de Registros

Data de Publicação

25/03/2026

Data de Modificação

08/03/2026

Objetivos

  • Mapear variáveis virtuais para registradores físicos limited.
  • Algoritmo de Coloração de Grafos de Chaitin.

Motivação

Alocação de registradores é o ponto onde teoria de grafos encontra performance de hardware:

  • Uso inteligente de registradores reduz drasticamente o número de acessos à memória, melhorando tempo de execução e consumo de energia.
  • Em arquiteturas embarcadas com poucos registradores, um bom alocador é a diferença entre um firmware que cabe na memória e um que não cabe.

Conteúdo

A IR (ou SSA) usa variáveis virtuais em número ilimitado; a máquina tem um número limitado de registradores. O alocador de registradores mapeia variáveis para registradores (ou para slots na pilha quando não houver registrador disponível). Acesso a registrador é muito mais rápido que acesso à memória; maximizar o uso de registradores é crucial para desempenho.

flowchart LR
  IR[IR/SSA] --> Liveness[Análise de vida]
  Liveness --> Grafo[Grafo de interferência]
  Grafo --> Color[Coloração]
  Color --> Spill[Spill se necessário]
  Spill --> Color

Análise de Vida (Liveness Analysis)

Primeiro, determinamos o Live Range de cada variável: o intervalo entre sua definição e seu último uso. Se duas variáveis têm intervalos que se sobrepoem, elas são ditas “interferentes” (não podem ocupar o mesmo registrador ao mesmo tempo).

Coloração de Grafos

Modelamos o problema como coloração de grafos: - Nós: Variáveis. - Arestas: Interferência. - Cores: Registradores Físicos (K cores).

Se o grafo for K-colorível, perfeito! Cada cor vira um registrador. Se não for (Spill), escolhemos a variável menos importante (heurística: menor uso dentro de loops), “vazamos” ela para a memória (Stack) e tentamos colorir novamente. O grafo fica mais simples pois a variável removida não interfere mais em registradores.

Resumo

  • Liveness: intervalo entre definição e último uso; duas variáveis vivas ao mesmo tempo interferem (não podem compartilhar registrador).
  • Grafo de interferência: nós = variáveis; arestas = interferência. Coloração com K cores (K = número de registradores). Se não for K-colorível, spill e repita.

Referências

  • Aho et al. (2006); Cooper & Torczon (2011).

Materiais da aula

Última atualização: 08/03/2026

De volta ao topo