Ce que fait exactement l'instruction PHI et comment l'utiliser dans LLVM

Question

LLVM a phi instruction avec une explication assez bizarre :

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

Il est généralement utilisé pour mettre en œuvre le branchement. Si j'ai bien compris, il est nécessaire pour rendre possible l'analyse des dépendances et, dans certains cas, il pourrait aider à éviter les chargements inutiles. Cependant, il est toujours difficile de comprendre ce qu'il fait exactement.

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

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

Les dernières lignes m'embrouillent 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éfinissait simplement de quels chemins provenaient les valeurs.

Quelqu'un pourrait-il expliquer ce qu'est un nœud Phi, et comment mettre en place || avec elle ?

Answer 1

Un nœud phi est une instruction utilisée pour sélectionner une valeur en fonction du prédécesseur du bloc actuel (Look aquí pour voir la hiérarchie complète - elle est également utilisée comme valeur, qui est l'une des classes dont elle hérite).

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

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

se traduit par l'IR suivant : (créé par clang -c -emit-llvm file.c -o out.bc - et ensuite visualisé à travers 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 l peut être soit 0 soit 1, dans l'IR LLVM il doit être défini. une fois . Nous vérifions donc si %tobool est vrai, et ensuite sauter à lor.end o lor.rhs .

Sur lor.end nous avons enfin la valeur de l'opérateur ||. Si nous sommes arrivés depuis le bloc d'entrée - alors c'est juste vrai. Sinon, c'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 ]

Answer 2

Vous n'avez pas besoin d'utiliser phi du tout. Il suffit de créer un tas de variables temporaires. Les passes d'optimisation de LLVM s'occuperont de l'optimisation des variables temporaires et utiliseront le noeud phi pour cela automatiquement.

Par exemple, si vous voulez faire ceci :

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

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

1. assigner 4 à x1
2. si (!quelque chose) passer à 4
3. calculer x2 à partir de x1 en ajoutant 2
4. attribuer à x3 le phi de x1 et x2
5. appeler l'impression 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. charger dans temp x1 valeur 4
3. stocker x1 en x
4. si (!quelque chose) passer à 8
5. charger x dans temp x2
6. ajouter x2 avec 4 pour temp x3
7. stocker x3 en x
8. charger x à temp x4
9. impression d'appel avec x4

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

Answer 3

Les réponses existantes sont bonnes. Mais, je veux la rendre encore plus simple et plus courte.

block3:
    %result = phi i32 [%a, %block1], [%b, %block2]

Cela signifie que si le bloc précédent était block1 , choisir la valeur a . Si le bloc précédent était block2 , choisir la valeur b .

Pourquoi écrivons-nous comme ça ? C'est pour éviter d'assigner result dans deux blocs différents tels que if et else bloc. En effet, nous ne voulons pas violer le principe SSA. SSA aide les compilateurs à appliquer une variété d'optimisations et c'est un standard de-facto pour les codes intermédiaires. Pour plus d'informations, reportez-vous à cette référence .