究竟什么是PHI指令以及如何在LLVM中使用它

Question

LLVM有phi指令,有很奇怪的解释:

'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节点产生可以使用的结果.而且我的印象是,phi节点只是定义了哪些路径值.

有人可以解释什么是Phi节点,以及如何实现||它？

Answer 1

phi节点是用于根据当前块的前任选择值的指令(在此处查看完整的层次结构 - 它也用作值,它是从其继承的类之一).

由于LLVM代码的SSA(静态单一赋值)样式的结构,Phi节点是必需的 - 例如,以下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,在LLVM IR中,它必须定义一次.所以我们检查是否%tobool为真,然后跳转到lor.end或lor.rhs.

在lor.end我们终于有了||的价值 运营商.如果我们从入境区到达 - 那就是真的.否则,它等于 - 的值%tobool2- 这正是我们从以下IR线得到的:

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

Answer 2

你根本不需要使用phi.只需创建一堆临时变量.LLVM优化传递将负责优化临时变量,并将自动使用phi节点.

例如,如果要执行此操作:

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

你可以使用phi节点(伪代码):

1. 将4分配给x1
2. if(!something)分支到4
3. 通过加2来从x1计算x2
4. 从x1和x2分配x3 phi
5. 用x3打印

但你可以没有phi节点(在伪代码中):

1. 在名为x的堆栈上分配局部变量
2. 加载到temp x1值4
3. 将x1存储到x
4. if(!something)分支到8
5. 将x加载到temp x2
6. 将x2与4添加到temp x3
7. 将x3存储到x
8. 将x加载到temp x4
9. 用x4打印

通过使用llvm运行优化传递,第二个代码将优化为第一个代码.

Answer 3

现有的答案都很好。但是，我想让它变得更简单、更短。

block3:
    %result = phi i32 [%a, %block1], [%b, %block2]

这意味着如果前一个块是block1，则选择 value a。如果前一个块是block2，则选择 value b。

我们为什么要这样写？这是为了防止result在两个不同的块（例如if块和else块）中进行分配。因为，我们不想违反SSA原则。SSA帮助编译器应用各种优化，它是中间代码事实上的标准。有关详细信息，请参阅此参考。