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

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

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

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

Калейдоскоп пример объясняет это довольно хорошо для if случае. Однако это не так ясно, как реализовать логические операции, как && и ||. Если я наберу следующее online 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 выдает результат, который можно использовать. И у меня сложилось впечатление, что узел phi просто определяет, из каких путей значения приход.

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

3 61
llvm

3 ответа:

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

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

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

переводится в следующий ИК: (создается через clang-c-emit-llvm файл.с-о выезде.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++, где переменная l может быть либо 0, либо 1, в LLVM IR она должна быть определена после. Поэтому мы проверяем, является ли %tobool истинным, а затем переходим к lor.конец или ЛОР.правая сторона.

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

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

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

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

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

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

  1. присвоить 4 x1
  2. если (!что-то ветка) до 4
  3. вычислить x2 из x1, добавив 2
  4. присвоить x3 phi от x1 и x2
  5. вызов печати с x3

но вы можете обойтись без узла phi (в псевдокоде):

  1. выделите локальную переменную в стеке с именем x
  2. загрузить в temp x1 значение 4
  3. хранить x1 в x
  4. если (!что-то ветка) до 8
  5. загрузить x в temp x2
  6. добавить x2 с 4 до temp x3
  7. хранить x3 в x
  8. загрузить x в temp x4
  9. вызовите печать с x4

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

19

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

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

0