mac - Qué hace exactamente la instrucción PHI y cómo usarla en LLVM

llvm tutorial

Question

LLVM tiene instrucción phi con una explicación bastante extraña:

La instrucción ''phi'' se usa para implementar el nodo en el gráfico SSA que representa la función.

Normalmente se utiliza para implementar la bifurcación. Si entendí correctamente, es necesario para 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 qué hace exactamente.

El example caleidoscopio lo explica bastante bien para el caso. Sin embargo, no está tan claro cómo implementar operaciones lógicas como && y || . Si escribo lo siguiente para el compilador llvm en línea :

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

Las ú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 phi node produce un resultado que puede ser usado. Y tuve la impresión de que phi node simplemente define de qué rutas provienen los valores.

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

Answer 1

El nodo phi es una solución del problema en los compiladores para convertir el IR en una forma de "asignación única estática". Para entender mejor la solución, sugiero entender mejor el problema.

Así que uno de ustedes arriba " ¿Por qué es phi node ".

Answer 2

No necesitas usar phi en absoluto. Sólo crea un montón de variables temporales. Los pases de optimización de LLVM se ocuparán de optimizar las variables temporales y utilizarán phi node para eso automáticamente.

Por ejemplo, si quieres hacer esto:

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

Puedes usar el nodo phi para eso (en pseudocódigo):

1. asigna 4 a x1
2. si (! algo) se ramifica a 4
3. calcula x2 a partir de x1 sumando 2
4. asignar x3 phi de x1 y x2
5. llamada de impresión con x3

Pero puedes hacerlo sin phi node (en pseudocódigo):

1. asignar la variable local en la pila llamada x
2. carga en temp x1 valor 4
3. almacenar x1 a x
4. si (! algo) se ramifica a 8
5. carga x a temp x2
6. agrega x2 con 4 a temp x3
7. almacenar x3 a x
8. carga x a temp x4
9. llamada de impresión con x4

Al ejecutar pases de optimización con llvm, este segundo código se optimizará al primer código.

Answer 3

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

Los nodos phi son necesarios debido a la estructura del estilo SSA (asignación única estática) del código LLVM, por ejemplo, la siguiente función C ++

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

se traduce al siguiente IR: (creado a través de clang -c -emit-llvm file.c -o out.bc - y luego visto a través de 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
}

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

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

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