Что такое инструкция PHI и как ее использовать в LLVM

У LLVM есть инструкция фи с довольно странным объяснением:

Инструкция 'phi' используется для реализации узла φ в графе SSA, представляющем функцию.

Обычно это используется для реализации ветвления. Если я правильно понял, необходимо сделать анализ зависимостей возможным, а в некоторых случаях это может помочь избежать ненужной загрузки. Однако все еще трудно понять, что именно он делает.

Пример калейдоскопа объясняет это довольно хорошо для случая if. Однако не очень понятно, как реализовать логические операции вроде && и || , Если я введу следующее в онлайн компилятор llvm:

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

Последние несколько строк меня полностью смущают:

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

Похоже, фи-узел выдает результат, который можно использовать. И у меня сложилось впечатление, что фи-узел просто определяет, из каких путей исходят значения.

Может ли кто-нибудь объяснить, что такое Phi-узел и как его реализовать || с этим?

Ответы

Ответ 1

Phi-узел - это инструкция, используемая для выбора значения в зависимости от предшественника текущего блока (смотрите здесь, чтобы увидеть полную иерархию - он также используется в качестве значения, которое является одним из классов, от которых он наследует).

Фи-узлы необходимы из-за структуры стиля SSA (статическое одиночное назначение) кода LLVM - например, следующая функция C++

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

переводится в следующий IR: (создается через clang -c -emit-llvm file.c -o out.bc - и затем просматривается через 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
}

Так что здесь происходит? В отличие от кода C++, где переменная bool l может быть либо 0, либо 1, в IR LLVM она должна быть определена один раз. Таким образом, мы проверяем, является ли %tobool истинным, и затем переходим к lor.end или lor.rhs.

В lor.end у нас наконец есть значение || оператор. Если мы приехали из блока въезда - то это просто правда. В противном случае он равен значению %tobool2 - и это именно то, что мы получаем из следующей строки IR:

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

Ответ 2

Вам вообще не нужно использовать phi. Просто создайте кучу временных переменных. Пропуск оптимизации LLVM будет заботиться об оптимизации временных переменных и автоматически будет использовать phi node.

Например, если вы хотите сделать это:

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

Вы можете использовать phi node для этого (в псевдокоде):

  • назначить 4 x1
  • if (! something) branch to 4
  • вычислить x2 из x1, добавив 2
  • назначить x3 phi из x1 и x2
  • вызов печати с помощью x3

Но вы можете обойтись без phi node (в псевдокоде):

  • выделить локальную переменную в стеке, называемую x
  • загрузить в значение temp x1 4
  • сохранить x1 в x
  • if (! something) branch to 8
  • загрузить x в temp x2
  • добавить x2 с 4 до temp x3
  • сохранить x3 в x
  • загрузить x в temp x4
  • вызов печати с помощью x4

Путем выполнения оптимизационных проходов с llvm этот второй код будет оптимизирован для первого кода.

Ответ 3

phi узел - это решение проблемы в компиляторах по преобразованию IR в форму "Статическое одиночное назначение". Чтобы понять лучше понять решение, я бы предложил лучше понять проблему.

Так что я буду один из вас " Почему это phi узел ".