compiler-construction - 如何在 LLVM 上创建 Loop 对象？

Question

我想知道 LLVM 如何创建 Loop 对象。

Loop相关的对象有很多，比如LoopInfo、LoopBase、Loop等。

但我找不到他们创建这些对象的 LLVM 源代码的位置。

我想知道他们如何跟踪后缘，以及如何识别那是一个循环。

可以这么说，我想学习在LLVM上检测和分析循环信息的整个原理

Answer 1

有两种方法可以用来实现传统的循环。一个不使用 phi然而，指令和指令都使用 br运营商。

看看下面的代码:

#include <stdio.h>

int main () {

   for(int i = 0; i < 10; i++) {
      printf("Test.\n");
   }

   return 0;
}

在这里，我使用带有命令 clang -S loop.c -emit-llvm 的 Clang 生成了一个示例，导致它实现第一个选项:

@.str = private unnamed_addr constant [7 x i8] c"Test.\0A\00", align 1

; Function Attrs: nounwind
define i32 @main() #0 {
entry:
  %retval = alloca i32, align 4
  %i = alloca i32, align 4
  store i32 0, i32* %retval
  store i32 0, i32* %i, align 4
  br label %for.cond

for.cond:                                         ; preds = %for.inc, %entry
  %0 = load i32* %i, align 4
  %cmp = icmp slt i32 %0, 10
  br i1 %cmp, label %for.body, label %for.end

for.body:                                         ; preds = %for.cond
  %call = call i32 (i8*, ...)* @printf(i8* getelementptr inbounds ([7 x i8]* @.str, i32 0, i32 0)) #1
  br label %for.inc

for.inc:                                          ; preds = %for.body
  %1 = load i32* %i, align 4
  %inc = add nsw i32 %1, 1
  store i32 %inc, i32* %i, align 4
  br label %for.cond

for.end:                                          ; preds = %for.cond
  ret i32 0
}

; Function Attrs: nounwind
declare i32 @printf(i8*, ...) #0

首先，我们创建标识符来表示我们的 i并返回值变量，然后将它们分别设置为 0。它转到第一个标签并开始循环，从计算 icmp <cond> <ty> <op1>, <op2> 产生的 bool 值开始。指令，其中 slt =“签名小于”。如果%i小于10，true会存入%cmp ，否则，将存储 false。br 的重载语法接下来的说明，br i1 <cond>, label <iftrue>, label <iffalse>定义如果%cmp为真，程序会跳转到iftrue标签，在本例中为 %for.body ，否则会跳转到iffalse标签，在本例中为 %for.end .总结一下，这条指令如果%i就会进入循环体还是小于10，如果达到10就退出循环。有了关于 br 的最终知识指令，程序其余部分的行为应该是显而易见的。

现在，虽然第二种方法更短，但稍微复杂一些。我使用带有命令 clang -S loop.c -emit-llvm -O1 的 Clang 生成了这段代码，即标记 1 级优化标志，使其实现第二个选项:

@.str = private unnamed_addr constant [7 x i8] c"Test.\0A\00", align 1
@str = private unnamed_addr constant [6 x i8] c"Test.\00"

; Function Attrs: nounwind
define i32 @main() #0 {
entry:
  br label %for.body

for.body:                                         ; preds = %for.body, %entry
  %i.02 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
  %puts = tail call i32 @puts(i8* getelementptr inbounds ([6 x i8]* @str, i32 0, i32 0))
  %inc = add nuw nsw i32 %i.02, 1
  %exitcond = icmp eq i32 %inc, 10
  br i1 %exitcond, label %for.end, label %for.body

for.end:                                          ; preds = %for.body
  ret i32 0
}

; Function Attrs: nounwind
declare i32 @puts(i8* nocapture readonly) #1

忽略增量技术的有趣语法 %inc = add nuw nsw i32 %i.02, 1 ，它只是整数数学溢出错误处理。我们专注于 phi说明这是手册中的说明:

At runtime, the ‘phi‘ instruction logically takes on the value specified by the pair corresponding to the predecessor basic block that executed just prior to the current block.

那么，让我们再次关注有问题的代码:

for.body:
          %i.02 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
          %puts = tail call i32 @puts(i8* getelementptr inbounds ([6 x i8]* @str, i32 0, i32 0))
          %inc = add nuw nsw i32 %i.02, 1
          %exitcond = icmp eq i32 %inc, 10
          br i1 %exitcond, label %for.end, label %for.body

当我们第一次遇到%i.02 ，我们传递的最后一个标签是 entry .因此，我们被指示设置 %i.02到 0。即使我们已经通过了 for.body标签，执行命令的最后一个前置 block 在 entry 中 block ，制作 entry最后一个标签。接下来，我们调用我们的控制台打印功能。然后，我们声明一个变量 %inc并将其设置为我们的“i”变量 + 1，这是第一个增量，它将变为 0。最后，我们进行 bool 比较，检查我们的“i”值是否小于 10，在本例中，它是，br指令将我们送回顶部。现在是棘手的部分:phi可以看出代码最后在 for.body 中执行标签。这意味着我们仍在 for.body 中。前导 block 和 %inc仍在我们的符号表中，这就是为什么我们可以设置 %i.02至 %inc . %inc将继续递增，直到等于 10，即 br指令将跳转到 %for.end标签，从而退出循环。

有关上述所有说明的更多信息，请访问 LLVM Language Reference Manual .