O que exatamente a instrução PHI faz e como usá-la no LLVM

LLVM tem instrução phi com explicação bastante estranha:

A instrução 'phi' é usada para implementar o nó φ no gráfico SSA que representa a função.

Normalmente, é usado para implementar ramificações. Se bem entendi, é necessário para possibilitar a análise de dependências e, em alguns casos, pode ajudar a evitar carregamentos desnecessários. No entanto, ainda é difícil entender o que ele faz exatamente.

O exemplo do caleidoscópio explica muito bem para o ifcaso. No entanto, não está claro como implementar operações lógicas como &&e ||. Se eu digitar o seguinte no compilador llvm online :

void main1(bool r, bool y) {
    bool l = y || r;
}

As últimas linhas me confundem completamente:

; <label>:10                                      ; preds = %7, %0
%11 = phi i1 [ true, %0 ], [ %9, %7 ]
%12 = zext i1 %11 to i8

Parece que o nó phi produz um resultado que pode ser usado. E fiquei com a impressão de que o nó phi apenas define de quais caminhos os valores vêm.

Alguém poderia explicar o que é um nó Phi e como implementar ||com ele?

Um nó phi é uma instrução usada para selecionar um valor dependendo do predecessor do bloco atual (Veja aqui para ver a hierarquia completa - também é usado como um valor, que é uma das classes da qual herda).

Os nós Phi são necessários devido à estrutura do estilo SSA (atribuição única estática) do código LLVM - por exemplo, a seguinte função C ++

void m(bool r, bool y){
    bool l = y || r ;
}

é traduzido para o seguinte IR: (criado por meio de clang -c -emit-llvm file.c -o out.bc- e então visualizado por meio llvm-dis)

define void @_Z1mbb(i1 zeroext %r, i1 zeroext %y) nounwind {
entry:
  %r.addr = alloca i8, align 1
  %y.addr = alloca i8, align 1
  %l = alloca i8, align 1
  %frombool = zext i1 %r to i8
  store i8 %frombool, i8* %r.addr, align 1
  %frombool1 = zext i1 %y to i8
  store i8 %frombool1, i8* %y.addr, align 1
  %0 = load i8* %y.addr, align 1
  %tobool = trunc i8 %0 to i1
  br i1 %tobool, label %lor.end, label %lor.rhs

lor.rhs:                                          ; preds = %entry
  %1 = load i8* %r.addr, align 1
  %tobool2 = trunc i8 %1 to i1
  br label %lor.end

lor.end:                                          ; preds = %lor.rhs, %entry
  %2 = phi i1 [ true, %entry ], [ %tobool2, %lor.rhs ]
  %frombool3 = zext i1 %2 to i8
  store i8 %frombool3, i8* %l, align 1
  ret void
}

Então, o que acontece aqui? Ao contrário do código C ++, onde a variável bool lpode ser 0 ou 1, no LLVM IR ela deve ser definida uma vez . Portanto, verificamos se isso %toboolé verdadeiro e, em seguida, vamos para lor.endou lor.rhs.

Em lor.endnós finalmente temos o valor de || operador. Se chegamos do bloco de entrada - então é verdade. Caso contrário, é igual ao valor de %tobool2- e é exatamente o que obtemos da seguinte linha de IR:

%2 = phi i1 [ true, %entry ], [ %tobool2, %lor.rhs ]

Você não precisa usar phi. Basta criar um monte de variáveis ​​temporárias. Os passos de otimização do LLVM cuidarão da otimização das variáveis ​​temporárias e usarão o nó phi para isso automaticamente.

Por exemplo, se você quiser fazer isso:

x = 4;
if (something) x = x + 2;
print(x);

Você pode usar o nó phi para isso (em pseudocódigo):

1. atribuir 4 a x1
2. se (! algo) ramificar para 4
3. calcular x2 de x1 adicionando 2
4. atribuir x3 phi de x1 e x2
5. ligue para imprimir com x3

Mas você pode fazer sem o nó phi (em pseudocódigo):

1. alocar variável local na pilha chamada x
2. carregar na temperatura x1 valor 4
3. armazenar x1 a x
4. se (! algo) ramificar para 8
5. carregar x para temp x2
6. adicione x2 com 4 para temp x3
7. armazenar x3 a x
8. carregar x para temp x4
9. ligue para imprimir com x4

Ao executar passos de otimização com llvm, este segundo código será otimizado para o primeiro código.