Aula 19: Representação SSA

Data de Publicação

25/03/2026

Data de Modificação

08/03/2026

Objetivos

  • Entender o conceito de SSA (Static Single Assignment).
  • Dominar a construção e uso da função Phi.

Motivação

SSA é a base de praticamente todos os compiladores modernos de alto desempenho (LLVM, GCC, JITs de VMs). Ela simplifica:

  • Análise de fluxo de dados (é fácil responder "de onde vem o valor desta variável?").
  • Otimizações como propagação de cópias, eliminação de código morto e renomeação de registradores.
  • Implementação de alocadores de registradores eficientes.

Conteúdo

A Single Static Assignment (SSA) é a revolução moderna nos compiladores. Adotada pelo GCC 4, LLVM, HotSpot e V8, ela simplifica drasticamente a análise de fluxo de dados.

O Princípio SSA

“Cada variável é atribuída exatamente uma vez no texto do programa.” Para isso, versionamos as variáveis: Original:

x = 1;
x = 2;
y = x;

SSA:

x1 = 1;
x2 = 2;
y1 = x2;

Vantagem Imediata: Não existe ambiguidade sobre “qual valor de x” estamos usando em \(y = x\). É sempre a definição única que domina o uso. x1 e x2 são variáveis totalmente independentes.

A Função \(\phi\) (Phi)

O problema surge em junções de controle (Joins do CFG):

if (cond) { x = 1; } else { x = 2; }
print(x); // Qual x?

Em SSA, introduzimos uma função mágica \(\phi\) no início do bloco de junção:

if (cond) { x1 = 1; } else { x2 = 2; }
x3 = phi(x1, x2);
print(x3);

O \(\phi\) diz: “Se vim do bloco ‘then’, x3 valerá x1. Se vim do ‘else’, valerá x2”. Na geração de código real, isso vira um move ou alocação de registrador no merge.

Fluxo de conversão para SSA

flowchart LR
  IR[IR convencional] --> Domin[Dominância]
  Domin --> Rename[Renomear definições]
  Rename --> Phi[Inserir phi nos merges]
  Phi --> SSA[IR em SSA]
  1. Calcular dominância: um bloco \(B\) domina \(B'\) se todo caminho da entrada até \(B'\) passa por \(B\). Isso define os pontos de merge (blocos com mais de um predecessor).
  2. Renomear: cada definição de variável recebe um índice novo (\(x \to x_1, x_2, \ldots\)); usos referenciam a definição que os domina (versão mais recente no caminho).
  3. Inserir \(\phi\): nos blocos de merge, para cada variável \(x\) que tem definições em pelo menos dois predecessores, inserir \(x_k = \phi(x_{i}, x_{j}, \ldots)\) com um argumento por predecessor.

Vantagens para otimização

  • Propagação de constantes: se a única definição que alcança um uso é uma constante, substituir o uso pela constante.
  • Eliminação de código morto: definições cujo valor nunca é usado podem ser removidas (em SSA, “não usado” é mais simples de detectar).
  • Alocação de registradores: em SSA, intervalos de vida são mais claros; muitos compiladores fazem alocação diretamente sobre os nomes SSA (ex.: LLVM).

Resumo

  • SSA: cada “variável” é definida no máximo uma vez no texto; versões (\(x_1, x_2, \ldots\)) eliminam ambiguidade.
  • \(\phi\): nos merges do CFG, escolhe o valor correto conforme o predecessor; na codegen vira movimentação ou alocação.
  • SSA simplifica análise de fluxo, otimizações e alocação de registradores.

Referências

  • Aho et al. (2006). Compilers: Principles, Techniques, and Tools. Cap. 6 e 9.
  • Cooper & Torczon (2011). Engineering a Compiler.

Materiais da aula

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

De volta ao topo