LLVM IR 嵌套 phi 指令

Question

我正在使用我自己的编程语言。我目前在 LLVM IR 中生成代码。我有一个关于带 phi 的嵌套 If 语句的问题。所以假设我有我的语言：

  if n < 0 then
        print("n < 0")
    else
        if 100 < n then
            print("100")
        else
            print("\n")

我在 llvm ir 中生成了这个：

; If
; ObjectIdentifier
%15 = load %struct.Main*, %struct.Main** %2
%16 = getelementptr inbounds %struct.Main, %struct.Main* %15, i32 0, i32 1
%17 = load i32, i32* %16

; VarValue
%18 = alloca i32
store i32 0, i32* %18
%19 = load i32, i32* %18

; Lower
%20 = icmp slt i32 %17, %19

br i1 %20, label %condIf1, label %condElse1 

condIf1:
    ; Call Method
    %21 = load %struct.Main*, %struct.Main** %2
    %22 = getelementptr inbounds %struct.Main, %struct.Main* %21, i32 0, i32 0
    ; Arguments
    ; VarValue
    %23 = alloca [6 x i8]
    store [6 x i8] c"n < 0[=11=]", [6 x i8]* %23
    %24 = bitcast [6 x i8]* %23 to i8*

    %25 = call %struct.IO* @IO_print(%struct.IO* %22, i8* %24)

    br label %condEnd1

condElse1:
    ; If
    ; VarValue
    %26 = alloca i32
    store i32 100, i32* %26
    %27 = load i32, i32* %26

    ; ObjectIdentifier
    %28 = load %struct.Main*, %struct.Main** %2
    %29 = getelementptr inbounds %struct.Main, %struct.Main* %28, i32 0, i32 1
    %30 = load i32, i32* %29

    ; Lower
    %31 = icmp slt i32 %27, %30

    br i1 %31, label %condIf2, label %condElse2     

    condIf2:
        ; Call Method
        %32 = load %struct.Main*, %struct.Main** %2
        %33 = getelementptr inbounds %struct.Main, %struct.Main* %32, i32 0, i32 0
        ; Arguments
        ; VarValue
        %34 = alloca [8 x i8]
        store [8 x i8] c"n > 100[=11=]", [8 x i8]* %34
        %35 = bitcast [8 x i8]* %34 to i8*

        %36 = call %struct.IO* @IO_print(%struct.IO* %33, i8* %35)

        br label %condEnd2

    condElse2:
        ; Call Method
        %37 = load %struct.Main*, %struct.Main** %2
        %38 = getelementptr inbounds %struct.Main, %struct.Main* %37, i32 0, i32 0
        ; Arguments
        ; VarValue
        %39 = alloca [2 x i8]
        store [2 x i8] c"[=11=]a[=11=]", [2 x i8]* %39
        %40 = bitcast [2 x i8]* %39 to i8*

        %41 = call %struct.IO* @IO_print(%struct.IO* %38, i8* %40)

        br label %condEnd2

    condEnd2:
        %42 = phi %struct.IO* [%36, %condIf2], [%41, %condElse2]

    br label %condEnd1

condEnd1:
    %43 = phi %struct.IO* [%25, %condIf1], [%43, %condElse1]

一切都已编译，但我收到这些错误:

 PHI node entries do not match predecessors!
 %43 = phi %struct.IO* [ %25, %condIf1 ], [ %42, %condElse1 ]
 label %condElse1
 label %condEnd2 
 Instruction does not dominate all uses!
 %42 = phi %struct.IO* [ %36, %condIf2 ], [ %41, %condElse2 ]
 %43 = phi %struct.IO* [ %25, %condIf1 ], [ %42, %condElse1 ]

我无法弄清楚 phi 到底有什么问题。您对如何解决此问题或使用其他东西有任何提示吗？谢谢！

Answer 1

condEnd1:
    %43 = phi %struct.IO* [%25, %condIf1], [%test, %condElse1]

condEnd1的前身（即跳转到condEnd1的块）是condIf1和condEnd2，而不是condElse1（这就是错误消息告诉你）。一个 phi 节点应该列出所有块的前身，而不是其他块，因为它说 "if you jumped here from block foo, use value bar" 并且只有当 foo 是一个可以实际跳转到 phi 节点所在的块的块时才有意义。

此外 %test 在块 %condElse1 中不可用（%condElse1 不包含 %test 的定义，也不包含到 %condElse1 遍历那个块），所以如果 %condElse1 是一个前导，你不会被允许从那里跳转时取 %test 的值。

这两个问题都可以通过将 phi 中的 %condElse1 替换为 %condEnd2 来解决。 %condEnd2实际上是condEnd1的前身，它包含了%test的定义。

关于使用 phi 节点的替代方法：

表示局部变量的常用方法是在函数开头使用 alloca 为每个变量分配堆栈 space，然后在需要该值时从该内存写入和读取。这样，每个变量都有一个寄存器来存储变量的地址，该地址将在函数的第一个块中定义，从而支配整个函数，然后，每次使用变量时，临时寄存器都不会t 比当前块长。所以不需要 phi 节点。

在从未使用过变量地址的情况下，LLVM 的 mem2reg 阶段会将其重写为使用寄存器和 phi 节点的版本，因此您将获得相同的可优化性和性能，但不必转换所有内容到 SSA 形成自己。

LLVM IR 嵌套 phi 指令

LLVM IR nested phi instruction

compiler-construction

llvm

llvm-ir