Aula 22: Alocação de Registros

Objetivos

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

Conteúdo

Esta é frequentemente considerada a otimização mais importante de um backend. Problema: Temos infinitas variáveis na IR (SSA), mas a CPU tem apenas 16 (x86-64) ou 32 (ARM/RISC-V) registradores gerais. Acesso a registrador é imediato; acesso à RAM (Stack) é lento. Objetivo: Maximizar o uso de registradores.

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.

Referências

  • Aho, A. V., Lam, M. S., Sethi, R., & Ullman, J. D. (2006). Compilers: Principles, Techniques, and Tools.
  • Cooper, K., & Torczon, L. (2011). Engineering a Compiler.
Back to top