Redundant basic blocks in llvm IR

Question

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;
        }
    }
}

Corresponding 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

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.

Answer 1

(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 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.

• 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

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.