¿Qué es exactamente la instrucción PHI hace y cómo usarlo en LLVM

Question

LLVM tiene phi instrucción con la explicación bastante raro:

El 'phi' instrucción se utiliza para implementar el nodo φ en el gráfico de la SSA que representa la función .

Normalmente se utiliza para implementar la bifurcación. Si entendí correctamente, es necesario hacer posible el análisis de dependencia y, en algunos casos, podría ayudar a evitar una carga innecesaria. Sin embargo, todavía es difícil entender lo que hace exactamente.

Calidoscopio example lo explica bastante bien para el caso if. Sin embargo, no está claro cómo implementar operaciones lógicas como && y ||. Si escribo lo siguiente para online llvm compilador:

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

últimas líneas me confunden por completo:

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

Parece que el nodo phi produce un resultado que se puede utilizar. Y tuve la impresión de que el nodo phi solo define de qué rutas provienen los valores.

¿Podría alguien explicar qué es un nodo Phi, y cómo implementar || con él?

Answer 1

Un nodo phi es una instrucción que se usa para seleccionar un valor según el predecesor del bloque actual (consulte here para ver la jerarquía completa; también se usa como valor, que es una de las clases heredadas) .

nodos Phi son necesarias debido a la estructura del estilo SSA (single asignación estática) del código LLVM - por ejemplo, la siguiente función de C++

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

se traduce en la siguiente IR: (creados a través -c-ruido metálico -emit llvm file.c -o out.bc - y luego se ve a través 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 
} 

Así que lo que sucede aquí? A diferencia del código C++, donde la variable l podría ser 0 o 1, en LLVM IR debe definirse una vez. Entonces, verificamos si% tobool es verdadero, y luego saltamos a lor.end o lor.rhs.

En lor.e finalmente tenemos el valor de || operador. Si llegamos desde el bloque de entrada, entonces es cierto. De lo contrario, es igual al valor de% tobool2 - y eso es exactamente lo que obtenemos de la siguiente línea de IR:

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

Answer 2

No es necesario utilizar phi en absoluto. Solo crea un montón de variables temporales. Los pases de optimización de LLVM se encargarán de optimizar las variables temporales y usarán el nodo phi automáticamente.

Por ejemplo, si usted quiere hacer esto:

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

Puede utilizar el nodo phi para que (en pseudocódigo):

1. de asignación de 4 a x1
2. si (algo) rama a 4
3. calcule x2 desde x1 agregando 2
4. asigne x3 phi de x1 y x2
impresión
5. llamada con x3

Pero se puede prescindir de nodo phi (en pseudocódigo):

1. asignar variables locales en la pila llamada x
2. carga en valor x1 temp 4
3. tienda x1 a
x
4. if (! algo) a la rama 8
5. carga x x2 a temperatura
6. añadir x2 con 4 a x3 temp
7. tienda x3 ax
8. carga de x para x4 temp
de impresión
9. llamada con x4

Mediante la ejecución de optimización pasa con llvm este segundo código conseguirá optimizado a primera código.