Aula 19: Representação SSA

Objetivos

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

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 simplesmente alocação de registrador inteligente.

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