Co dokładnie robi instrukcja PHI i jak jej używać w LLVM

LLVM ma instrukcję phi z dość dziwnym wyjaśnieniem:

Instrukcja „phi” służy do implementacji węzła φ na grafie SSA reprezentującym funkcję.

Zwykle jest używany do implementacji rozgałęziania. Jeśli dobrze zrozumiałem, jest to potrzebne, aby umożliwić analizę zależności, aw niektórych przypadkach może pomóc uniknąć niepotrzebnego ładowania. Jednak nadal trudno jest zrozumieć, co dokładnie robi.

Przykład Kalejdoskopu wyjaśnia to całkiem dobrze na potrzeby ifprzypadku. Jednak nie jest tak jasne, jak zaimplementować operacje logiczne, takie jak &&i ||. Jeśli wpiszę następujące polecenie do kompilatora online llvm :

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

Ostatnie kilka wierszy całkowicie mnie zmyliło:

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

Wygląda na to, że węzeł phi daje wynik, który można wykorzystać. Miałem wrażenie, że węzeł phi po prostu określa, z których ścieżek przychodzą wartości.

Czy ktoś mógłby wyjaśnić, czym jest węzeł Phi i jak go zaimplementować ||?

Węzeł phi to instrukcja służąca do wybierania wartości w zależności od poprzednika bieżącego bloku (spójrz tutaj, aby zobaczyć pełną hierarchię - jest również używany jako wartość, która jest jedną z klas, z których dziedziczy).

Węzły Phi są niezbędne ze względu na strukturę stylu SSA (static single assignment) kodu LLVM - na przykład poniższa funkcja C ++

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

zostanie przetłumaczony na następujący IR: (utworzony przez clang -c -emit-llvm file.c -o out.bc- a następnie przeglądany 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
}

Więc co się tutaj dzieje? W przeciwieństwie do kodu C ++, w którym zmienna bool lmoże mieć wartość 0 lub 1, w LLVM IR musi być zdefiniowana raz . Sprawdzamy więc, czy %tobooljest prawdą, a następnie przechodzimy do lor.endlub lor.rhs.

W lor.endkońcu mamy wartość || operator. Jeśli przyjechaliśmy z bloku wejściowego - to po prostu prawda. W przeciwnym razie jest równa wartości %tobool2- i dokładnie to otrzymujemy z następującej linii IR:

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

W ogóle nie musisz używać phi. Po prostu utwórz kilka tymczasowych zmiennych. Przebiegi optymalizacji LLVM zajmą się optymalizacją zmiennych tymczasowych i automatycznie użyją do tego węzła phi.

Na przykład, jeśli chcesz to zrobić:

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

Możesz do tego użyć węzła phi (w pseudokodzie):

1. przypisz 4 do x1
2. jeśli (! coś) rozgałęzia się do 4
3. oblicz x2 z x1, dodając 2
4. przypisz x3 phi z x1 i x2
5. Call print with x3

Ale możesz obejść się bez węzła phi (w pseudokodzie):

1. alokuj lokalną zmienną na stosie o nazwie x
2. załaduj do temp x1 wartość 4
3. zapisz x1 do x
4. jeśli (! coś) rozgałęź się do 8
5. załaduj x do temp. x2
6. dodaj x2 z 4 do temp x3
7. zapisz x3 do x
8. załaduj x do temp. x4
9. Call print with x4

Uruchamiając przebiegi optymalizacji z llvm, ten drugi kod zostanie zoptymalizowany do pierwszego kodu.