在 LLVM 程序集中递归的正确方法是什么？

Question

这是我的完整程序；我正在使用一种愚蠢的递归算法来熟悉 LLVM 程序集：

declare void @print_int(i32)

define i32 @rec_add(i32 %a, i32 %b) {
entry:
    %tmp1 = icmp eq i32 %a, 0
    br i1 %tmp1, label %done, label %recurse
    recurse:
        %tmp2 = sub i32 %a, 1
        %tmp3 = add i32 %b, 1
        ret i32 @rec_add(i32 %tmp2, i32 %tmp3)
    done:
        ret i32 %b
}

define i32 @main() {
    %tmp4 = i32 4;
    %tmp5 = i32 1;
    %cast = call i32 @rec_add(i32 %tmp4, i32 %tmp5)
    call void @print_int(i32 %cast)
}

当我用 $ llvm-as rec_add.ll 编译这个程序时，我收到这个错误信息：

llvm-as: rec_add.ll:10:11: error: global variable reference must have pointer type
                ret i32 @rec_add(i32 %tmp2, i32 %tmp3)
                        ^

我不明白这个错误信息是什么意思，因为我的程序没有全局变量。我知道 LLVM 程序集不需要指针作为其参数。

Answer 1

我什至不知道 llvm-as 的存在，但是将递归调用结果分配给一个变量是可行的。然后return那个。这甚至在 -O0 处也进行了优化。请参阅 Oak 的 answer/comments 了解正确的术语。

define i32 @rec_add(i32 %a, i32 %b) {
entry:
    %tmp1 = icmp eq i32 %a, 0
    br i1 %tmp1, label %done, label %recurse
    recurse:
        %tmp2 = sub i32 %a, 1
        %tmp3 = add i32 %b, 1
        %tmp4 = call i32 @rec_add(i32 %tmp2, i32 %tmp3)
        ret i32 %tmp4
    done:
        ret i32 %b
}

编译为 clang-3.8 -O0 -S -o- 的递归调用。

用clang-3.8 -Wall -O3 rec-add.ll -S -masm=intel -o-，llvm看透递归：

rec_add:                                # @rec_add
# BB#0:                                 # %entry
        lea     eax, [rdi + rsi]
        ret

你的 main 没有编译：

rec-add.ll:17:13: error: expected instruction opcode
    %tmp4 = i32 4;

这样就可以了：

define i32 @main() {
    %cast = call i32 @rec_add(i32  4, i32 1)
    call void @print_int(i32 %cast)
    ret i32 0
}

Answer 2

与高级语言不同，LLVM 指令不能由复合表达式组成。所以这不是一个有效的指令：

ret i32 @rec_add(i32 %tmp2, i32 %tmp3)

您可以选择 ret 或 call，但不能同时选择两者*。您实际上在这里写的是试图 return 函数的地址 - 这当然不是 i32，因此是类型错误。相反，您需要执行以下操作：

%something = call i32 @rec_add(i32 %tmp2, i32 %tmp3)
ret i32 %something

_{* 好吧，如果这些是 constant expressions，你可以做复合的东西，但这里不是这种情况。}

在 LLVM 程序集中递归的正确方法是什么？

What's the proper way to recurse in LLVM assembly?

recursion

assembly

pointers

llvm