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

91

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ć ||?

vwvw
źródło
1
phiWęzeł jest rozwiązanie tego problemu w celu przekształcenia kompilatorów IR w „statyczne pojedyncze przypisanie” formie. Aby lepiej zrozumieć rozwiązanie, sugerowałbym lepsze zrozumienie problemu. Więc powiem ci " Dlaczego phiwęzeł ".
Vraj Pandya

Odpowiedzi:

77

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 ]
Guy Adini
źródło
6
Węzeł TL; DR φ jest wyrażeniem trójskładnikowym. Ktoś mógłby argumentować, że nie zawiera warunku, ale tak naprawdę po konwersji do końcowego kodu nie można określić inaczej, który z argumentów jest aktywny, więc φ też trzeba mieć warunek.
Hi-Angel,
31

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.

Mārtiņš Možeiko
źródło
4
Z tego, co przeczytałem, wygląda na to, że istnieje kilka ograniczeń, o których należy pamiętać. mem2reg jest omawianym przebiegiem optymalizacji i ma kilka ograniczeń wskazanych w przykładzie Kalejdoskop . Wygląda na to, że jest to jednak preferowany sposób rozwiązania problemu i jest używany przez Clang.
Matthew Sanders