llvm IR中的冗余基本块 [英] Redundant basic blocks in llvm IR

问题描述

我只是在玩一个程序，并在llvm中观看它的IR，我注意到某些对我来说没有意义的基本块. 我的代码:

I was just playing around with a program and watching its IR in llvm and I noticed certain basic blocks that don't make sense to me. My code:

void proc()
{
    int i, j, k, m, n, l;
    k = 119;
    for (i = 20; i < 200; i++)
    {
        for (j = 13; j < 130; j++)
        {
                l = 80;
        }
    }
}

对应的IR:

 store i32 119, i32* %3, align 4
  store i32 20, i32* %1, align 4
  br label %7

; <label>:7:                                      ; preds = %19, %0
  %8 = load i32, i32* %1, align 4
  %9 = icmp slt i32 %8, 200
  br i1 %9, label %10, label %22

; <label>:10:                                     ; preds = %7
  store i32 13, i32* %2, align 4
  br label %11

; <label>:11:                                     ; preds = %15, %10
  %12 = load i32, i32* %2, align 4
  %13 = icmp slt i32 %12, 130
  br i1 %13, label %14, label %18

; <label>:14:                                     ; preds = %11
  store i32 80, i32* %6, align 4
  br label %15

; <label>:15:                                     ; preds = %14
  %16 = load i32, i32* %2, align 4
  %17 = add nsw i32 %16, 1
  store i32 %17, i32* %2, align 4
  br label %11

; <label>:18:                                     ; preds = %11
  br label %19

; <label>:19:                                     ; preds = %18
  %20 = load i32, i32* %1, align 4
  %21 = add nsw i32 %20, 1
  store i32 %21, i32* %1, align 4
  br label %7

; <label>:22:                                     ; preds = %7
  ret void

我的问题是标签14和15.看来标签15只有一个前身14.既然如此，为什么我们不能只将它与标签14合并呢?我假设基本块的构造是通过此处中提到的算法完成的.

My problem is with labels 14 and 15. It looks like label 15 has just one predecessor, 14. Given that, why can't we just merge it with label 14? I am assuming that the basic block construction is done by the algorithm mentioned here.

推荐答案

(此答案主要是我在评论中已经推测的内容的摘要，只是更详细且不再推测，因为我现在已经潜心学习了.进入clang的源代码以验证发生了什么

(This answer is mostly a summary of what I've already speculated in my comments, except it's more detailed and no longer speculation because I've now actually dived into clang's source code to verify that is what's happening)

LLVM代码始终被构造为基本块，并且用于表示API中的LLVM代码的类型已经形成了控制流程图.没有基本块就没有非结构化LLVM的形式，因此就没有将非结构化LLVM转换为CFG的过程. Clang直接将C AST转换为LLVM.因此，它不会在非结构化的三地址代码中找到基本块，而是在一步之内将C转换为LLVM时就找到了基本块.因此，维基百科的算法不适用.

LLVM code is always structured into basic blocks and the types used to represent LLVM code in the API already form a control flow graph. There is no such thing as an unstructured form of LLVM without basic blocks and thus no process of converting unstructured LLVM to a CFG. Clang directly translates the C AST to LLVM. So it does not find basic blocks in unstructured three-address code, it finds the basic blocks while translating from C to LLVM in a single step. Therefore the algorithm from Wikipedia does not apply.

下面基于

What's happening instead is summarized by the following heavily simplified pseudo code loosely based on CodeGenFunction::EmitForStmt in CodeGen/CGStmt.cpp. This is the logic for translating a statement of the form for(init; cond; incr) body. For simplicity we assume that neither cond nor incr are empty and that cond is an expression, not a declaration.

• 创建新的基本块:conditionBlock，bodyBlock，incrBlock和exitBlock
• 将初始化代码附加到当前基本块上，然后跳转到conditionBlock
• 将cond的代码附加到conditionBlock，后跟br i1 %cond, label %bodyBlock, label %exitBlock
• 将{break: exitBlock, continue: incrBlock}推入中断/继续堆栈
• 将body的代码附加到bodyBlock，然后跳转到conditionBlock
• 弹出中断/继续堆栈
• 将exitBlock设置为当前基本块

• Create the new basic blocks: conditionBlock, bodyBlock, incrBlock and exitBlock
• append code for init to the current basic block, followed by a jump to conditionBlock
• append code for cond to conditionBlock, followed by br i1 %cond, label %bodyBlock, label %exitBlock
• Push {break: exitBlock, continue: incrBlock} onto the break/continue stack
• append code for body to bodyBlock, followed by a jump to conditionBlock
• Pop the break/continue stack
• Set exitBlock as the current basic block

要获得所需的输出，必须将incr的代码发送到bodyBlock中，而不是使用单独的块.但是随后它无法将incrBlock推入中断/继续堆栈.当然，这对您而言并不重要，因为您的代码不包含任何continue语句，但是在一般情况下，编译器需要break/continue堆栈来知道在break s或<情况下跳转到的位置. c20> s.

To get the output that you expected, it would have to emit the code for incr into bodyBlock instead of having a separate block for it. But then it couldn't push incrBlock onto the break/continue stack. Of course that wouldn't matter in your case since your code does not contain any continue statements, but in the general case the compiler needs the break/continue stack to know where to jump to in case of breaks or continues.

因此，编译器仅总是生成这些块，然后在优化阶段将不必要的块合并.

So the compiler simply always generates these blocks and then unnecessary blocks get merged during the optimization phase.

这篇关于llvm IR中的冗余基本块的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！