Que fait exactement l'instruction PHI et comment l'utiliser dans LLVM

LLVM a une instruction phi avec une explication assez étrange:

L'instruction 'phi' est utilisée pour implémenter le nœud φ dans le graphe SSA représentant la fonction.

Il est généralement utilisé pour implémenter le branchement. Si j'ai bien compris, il est nécessaire de rendre l'analyse des dépendances possible et dans certains cas, cela pourrait aider à éviter un chargement inutile. Cependant, il est encore difficile de comprendre ce qu'il fait exactement.

L' exemple de Kaléidoscope l' explique assez bien pour le ifcas. Cependant, la manière d'implémenter des opérations logiques telles que &&et ||. Si je tape ce qui suit dans le compilateur llvm en ligne :

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

Les dernières lignes me confondent complètement:

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

On dirait que le nœud phi produit un résultat qui peut être utilisé. Et j'avais l'impression que le nœud phi définit simplement de quels chemins les valeurs proviennent.

Quelqu'un pourrait-il expliquer ce qu'est un nœud Phi et comment l'implémenter ||?

Un nœud phi est une instruction permettant de sélectionner une valeur en fonction du prédécesseur du bloc courant (Regardez ici pour voir la hiérarchie complète - il est également utilisé comme valeur, qui est l'une des classes dont il hérite).

Les nœuds Phi sont nécessaires en raison de la structure du style SSA (affectation unique statique) du code LLVM - par exemple, la fonction C ++ suivante

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

est traduit dans l'IR suivant: (créé via clang -c -emit-llvm file.c -o out.bc- puis visualisé via 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
}

Alors que se passe-t-il ici? Contrairement au code C ++, où la variable bool lpeut être 0 ou 1, dans LLVM IR, elle doit être définie une fois . Nous vérifions donc si %toboolc'est vrai, puis passons à lor.endoulor.rhs .

Dans lor.endnous avons enfin la valeur du || opérateur. Si nous sommes arrivés du bloc d'entrée - alors c'est juste vrai. Sinon, il est égal à la valeur de %tobool2- et c'est exactement ce que nous obtenons de la ligne IR suivante:

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

Vous n'avez pas du tout besoin d'utiliser phi. Créez simplement un tas de variables temporaires. Les passes d'optimisation LLVM se chargeront d'optimiser les variables temporaires et utiliseront automatiquement le nœud phi pour cela.

Par exemple, si vous souhaitez faire ceci:

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

Vous pouvez utiliser le nœud phi pour cela (en pseudocode):

1. attribuer 4 à x1
2. si (! quelque chose) branche à 4
3. calculer x2 à partir de x1 en ajoutant 2
4. attribuer x3 phi de x1 et x2
5. impression d'appel avec x3

Mais vous pouvez vous passer du nœud phi (en pseudocode):

1. allouer une variable locale sur la pile appelée x
2. charge en température x1 valeur 4
3. stocker x1 à x
4. si (! quelque chose) branche à 8
5. charger x à la température x2
6. ajouter x2 avec 4 à la température x3
7. stocker x3 à x
8. charger x à la température x4
9. appelez l'impression avec x4

En exécutant des passes d'optimisation avec llvm, ce deuxième code sera optimisé pour le premier code.