LLVM优化通过中断递归代码

Question

我有一些关于 LLVM 优化过程的问题，它修改了编译输出，因此它不再起作用。

这是斐波那契算法的输入源代码：

f<int> fib(int n) {
    if n <= 1 { return 1; }
    return fib(n - 1) + fib(n - 2);
}

f<int> main() {
    printf("Result: %d", fib(46));
    return 0;
}

在没有优化的情况下，我的编译器吐出以下 IR 代码，它工作得很好：

; ModuleID = 'Module'
source_filename = "Module"

@0 = private unnamed_addr constant [11 x i8] c"Result: %d[=11=]", align 1

declare i32 @printf(i8*, ...)

define i32 @"fib(int)"(i32 %0) {
entry:
  %n = alloca i32, align 4
  store i32 %0, i32* %n, align 4
  %result = alloca i32, align 4
  %1 = load i32, i32* %n, align 4
  %le = icmp sle i32 %1, 1
  br i1 %le, label %then, label %end

then:                                             ; preds = %entry
  ret i32 1
  br label %end

end:                                              ; preds = %then, %entry
  %2 = load i32, i32* %n, align 4
  %sub = sub i32 %2, 1
  %3 = call i32 @"fib(int)"(i32 %sub)
  %4 = load i32, i32* %n, align 4
  %sub1 = sub i32 %4, 2
  %5 = call i32 @"fib(int)"(i32 %sub1)
  %add = add i32 %3, %5
  ret i32 %add
}

define i32 @main() {
main_entry:
  %result = alloca i32, align 4
  %0 = call i32 @"fib(int)"(i32 46)
  %1 = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([11 x i8], [11 x i8]* @0, i32 0, i32 0), i32 %0)
  ret i32 0
}

然后我对其应用了一些优化过程。这是我的通行证链：

fpm->add(llvm::createDeadCodeEliminationPass());
fpm->add(llvm::createLoopDeletionPass());
fpm->add(llvm::createDeadStoreEliminationPass());
fpm->add(llvm::createGVNPass());
fpm->add(llvm::createPromoteMemoryToRegisterPass());
fpm->add(llvm::createInstructionCombiningPass());
fpm->add(llvm::createReassociatePass());
fpm->add(llvm::createCFGSimplificationPass()); // Breaks recursion
fpm->add(llvm::createCorrelatedValuePropagationPass());
fpm->add(llvm::createLoopSimplifyPass());

启用此优化通道后，我得到以下 IR 代码：

; ModuleID = 'Module'
source_filename = "Module"

@0 = private unnamed_addr constant [11 x i8] c"Result: %d[=13=]", align 1

declare i32 @printf(i8*, ...)

define i32 @"fib(int)"(i32 %0) {
entry:
  %le = icmp slt i32 %0, 2
  %sub = add i32 %0, -1
  %1 = call i32 @"fib(int)"(i32 %sub)
  %sub1 = add i32 %0, -2
  %2 = call i32 @"fib(int)"(i32 %sub1)
  %add = add i32 %2, %1
  ret i32 %add
}

define i32 @main() {
main_entry:
  %0 = call i32 @"fib(int)"(i32 46)
  %1 = call i32 (i8*, ...) @printf(i8* noundef nonnull dereferenceable(1) getelementptr inbounds ([11 x i8], [11 x i8]* @0, i64 0, i64 0), i32 %0)
  ret i32 0
}

显然，这段代码确实产生了堆栈溢出，因为递归锚点已经不存在了。似乎 CFGSimplificationPass 以错误的方式合并块/消除了 if 主体，尽管它是相关的。当我删除 'createCFGSimplificationPass' 行时，优化工作正常并且可执行结果运行良好。

现在我的问题是：我做错了什么？或者这可能是 LLVM 中的错误？

感谢您的帮助！

Answer 1

then:                                             ; preds = %entry
  ret i32 1
  br label %end

一个块不能有两个终止符，所以这个IR是无效的。这会导致优化行为异常，因为它们无法判断哪个是预期的终止符。

为了将来更容易捕获此类错误，您应该使用 llvm::verifyModule 来验证您生成的 IR，然后再运行对其进行额外的传递。

LLVM优化通过中断递归代码

LLVM optimization passes break recursive code

optimization

llvm

intermediate-code