SSA para código de máquina de pilha

Question

Eu estou trabalhando em um compilador para uma máquina de pilha (especificamente CIL ) e eu' ve analisado o código em um gráfico de blocos básicos. A partir daqui eu estou olhando para aplicar SSA aos métodos, mas ele não está indo muito bem. Minha primeira tentativa (enquanto trabalhava com uma lista plana, ao invés do gráfico) foi para iterar sobre o código e manter uma pilha de ids SSA (isto é, para os alvos atribuir), empurrando-os quando eu produzir uma atribuição, popping-los quando eles são usados. Isso funciona muito bem para um único bloco básico, mas eu simplesmente não consigo descobrir como lidar com produzindo funções & Phi.

A idéia eu fui jogar em torno é para anexar uma posição pilha para os ids SSA e depois olhar para o que é ainda na pilha quando os caminhos de código convergem, mas isso não parece ser o caminho certo (TM) de fazer as coisas.

Existe um algoritmo simples para acompanhar as manipulações pilha em vários caminhos de código e determinar as colisões quando eles convergem?

Answer 1

Você precisa olhar para o múltiplo conjunto de SSA ids convergindo para um nó (bloco básico). Manter a estrutura bloco básico intermediário, dessa forma você pode facilmente usar (por exemplo, consulta) todos os identificadores em um bloco.

Eu não tenho certeza do que você quer dizer com a colisão, mas eu suponho que você quer resolver algo como

 if (bExp)                  if (bExp)
   x := 1                    x1 := 1
 else            SSA:       else
   x := 2                    x2 := 2
 y := x;                    y := Phi(x1,x2)

que é, você quer o Phi neste lugar. Perceba que não há Phi em código executável! Usando as informações que y é (dependente) em x1 ou x2, você pode reescrever isso na próxima etapa. Por exemplo, em uma representação de memória-centric, o Phi (x1, x2) diz que X1 e X2 deve ser de dois aliases para o mesmo local de memória, ou seja, que de y. Phi apenas junta as informações.

if (bExp)
  stackframe[y_index] = 1     (y_index being some offset)
else
  stackframe[y_index] = 2
nop

Espero que isso ajude um pouco!