Loopinfo find multiple headers

IR & Optimizations Loop Optimizations
, ,
1

hello!

I am writing a pass for LLVM generated by Rust. Basically, I am trying to identify the body of a loop. With clang, it is easy because the basic blocks are labeled (for.cond, for.body, for.inc etc) however rust names basic blocks by numbers. My initial thought was to get the header block with loopinfo and assume that the successor block is the body. However, there can be multiple blocks belonging to the body as well as the header it seems. An example:

let mut arr: [i32; 5] = [1, 2, 3, 4, 5]; 
for i in 0..arr.len() {
    ...
}

and the section of the IR:

bb3:                                              ; preds = %bb9, %bb2
  %22 = call { i64, i64 } @"_ZN4core4iter5range93_$LT$impl$u20$core..iter..iterator..Iterator$u20$for$u20$core..ops..range..Range$LT$A$GT$$GT$4next17h08af673f70db9933E"({ i64, i64 }* dereferenceable(16) %iter)
  store { i64, i64 } %22, { i64, i64 }* %_17, align 8
  br label %bb4


bb4:                                              ; preds = %bb3
  %23 = bitcast { i64, i64 }* %_17 to i64*
  %24 = load i64, i64* %23, align 8
  %25 = bitcast { i64, i64 }* %_17 to i64*
  %26 = load i64, i64* %25, align 8
  switch i64 %26, label %bb6 [
    i64 0, label %bb5
    i64 1, label %bb7
  ]

Loopinfo tells me, bb3 is the header and this is what the latch jumps back to. In my understanding this is also the block which is equivalent to the for.inc block where the iterator gets updated to the next value. Then bb4 would be the for.cond block deciding whether to enter the body or the exit block.

So can I then assume bb5 is the body? what if there is a situation where there is another header block before bb4. a custom front end could break up the basic blocks in the header an it would still be correct but my assumption that the 3rd block in the loop is the body would be wrong. Is it even true to say bb3 and bb4 both belong to the header?

thanks!

2

Loops can have an arbitrarily large number of blocks that constitute the body. Consider code like the following:

for (int i = 0; i < N; i++) {
  if (A[i] > 3) {
    A[i] *= B[i];
  } else {
    B[i] *= C[i];
  }
  A[i] += C[i];
}

In this example, the loop would consist of three or four distinct blocks (four if the condition remains at the head of the loop, three if loop rotation has occurred). It’s possible of course to have nested loops, and there, all the blocks in the inner loop still remain part of the body of the outer loop.

LLVM’s LoopInfo class represents the concept of “natural loops”, which is definitionally based on control flow and dominance of basic blocks. In a natural loop, there are three different conceptual kinds of special blocks. The loop header is the single block that dominates all of the basic blocks in the loop–if no basic block dominates the others in a loop, there is no natural loop. The loop latch is any block which has the loop header as one of its successor blocks. The loop exiting block is any block which has a basic block not in the loop as one of its successors. (There are also concepts of loop exit blocks, loop preheaders, and loop predecessors, but these refer to blocks outside of the natural loop.)

Note that it is possible for there to exist multiple loop latches and multiple loop exiting blocks, but it is only ever possible for there to exist one loop header. Note that it is also possible for a single basic block in a natural loop to exist in many, none, or even all of these roles at the same time. It’s also possible for loop exiting blocks to not exist–infinite loops are still natural loops. (It’s also possible for cycles to exist in the control flow graph that do not correspond to natural loops–these would be irreducible loops).

From your problem statement, it is not clear to me what the criteria you actually want to use is. If you want to find all of the blocks in a loop, you can simply iterate over loop->blocks(). Or perhaps you’re interested in code that is after a loop exiting block and before the loop latch (though my personal experience is usually that you still care about all blocks, and the loop exiting block only matters in terms of knowing if you’re before or after it). Consider carefully what properties you really care about for your algorithm, and try to base them not on descriptions of control flow constructs at a programming language level but properties such as control dependence, dominance, or postdominance–high-level structures do not generally persist unmolested into LLVM IR.

1 Like
3

thanks for the clear response!

so the project I am working with did what I am attempting to do for rust front end with clang. the idea is to find that part of the body, that is not executed anymore once the condition becomes false.

for this, they rely on the labels emitted by clang when used with the “fno-discard-value-names”. In the loop example you provided, there would then be one for.end labeled block, one for.cond labeled block and one for.body labeled block and the rest would be if.then, if.else, if.end.

for.cond:                                         ; preds = %for.inc, %entry
  br i1 %cmp, label %for.body, label %for.end, !dbg !30

for.body:                                         ; preds = %for.cond
  br i1 %cmp1, label %if.then, label %if.else, !dbg !36

if.then:                                          ; preds = %for.body
  br label %if.end, !dbg !43

if.else:                                          ; preds = %for.body
  br label %if.end

if.end:                                           ; preds = %if.else, %if.then

  br label %for.inc, !dbg !55

for.inc:                                          ; preds = %if.end

  br label %for.cond, !dbg !57, !llvm.loop !58

for.end:

I removed the code that does not belong to the control flow for readability.

basically, I want to find for.cond but the blocks are not labeled and the for.cond block in rust is spread out over multiple basic blocks. with clang, I would just assume the for.inc and for.cond are the latch and the header and the other blocks are the body that I am interested in. with nested loops, I would have something like for.cond1, for.cond2 as labels then.

Otherwise I do not know how I can differentiate whether a basic block belongs to the conditional part of the loop and gets executed even if the condition is not met or to the body part where it doesnt get executed anymore, right?

another example would be if I insert a counter function call in the cond block, it would count one more than the number of times the loop is actually executed. I want to find the first block within the loop that does not belong to the conditional part and thus gets executed just as often as the loop(ignoring any other control flow)

4

so the project I am working with did what I am attempting to do for rust front end with clang. the idea is to find that part of the body, that is not executed anymore once the condition becomes false.

The general theme of what you are looking for is control dependence. A basic block A is control-dependent on another block B if A postdominates a successor of B but does not postdominate B itself. LLVM itself does not directly provide interfaces for computing control dependencies, but it does provide postdominators, which is sufficient to recreate control-dependency information. (Although I would note that loops do cause control dependency to get weird, see my comments in [RFC] Control-Depent Function Returns and Redefining Control Dependencies).

Given the definition you had, you would look for code in the loop that is postdominated by the loop header. That is to say, all the code that would have to travel through a loop latch and consequently the loop header before it can potentially reach any loop exiting block.

However, I suspect the definition you give isn’t actually what you want. To give a concrete example, your definition would report an empty loop body given a bottom-tested loop, which would look as follows in Rust:

loop {
  // Code, code, more code, large loop body.
  if cond { break; }
}
5

The following documentation may help you: LLVM Loop Terminology (and Canonical Forms) — LLVM 16.0.0git documentation

You mention you would like to identify the loop body, but I think in its generality this is the wrong question. Loops are canonicalized, especially by LoopRotate, which blurs the line between loop body and non-body code. You may want to go the other way around: Assume everything is part of the body and only assume instructions that are used for nothing else but to determine the exit condition is control code. in case of induction variables these are side-effect free and would be removed by ADCE anyway if you chose to modify the control code of the loop.

6

thanks. So with clang then, if you generate the IR the basic blocks for loops will have basic block labels when used with the “foo-discard-value-names” flag e.g. for a for loop it will output something like

for(int i =0; i<10; i++) {
  
 }



entry:
  %retval = alloca i32, align 4
  %i = alloca i32, align 4
  store i32 0, i32* %retval, align 4
  call void @llvm.dbg.declare(metadata i32* %i, metadata !12, metadata !DIExpression()), !dbg !14
  store i32 0, i32* %i, align 4, !dbg !14
  br label %for.cond, !dbg !15

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

for.body:                                         ; preds = %for.cond
  br label %for.inc, !dbg !20

for.inc:                                          ; preds = %for.body
  %1 = load i32, i32* %i, align 4, !dbg !22
  %inc = add nsw i32 %1, 1, !dbg !22
  store i32 %inc, i32* %i, align 4, !dbg !22
  br label %for.cond, !dbg !23, !llvm.loop !24

for.end:                                          ; preds = %for.cond
  %2 = load i32, i32* %retval, align 4, !dbg !26
  ret i32 %2, !dbg !26

so from this I want all instructions that are in the block for.body

how exactly would clang then determine this if the lines are blurred? after all this is exactly what I would need however swift front end does not provide these labels.

7

As mentioned, you cannot reliably (and should not) identify the loop body by basic block names for a lot of reasons. E.g. the SimplifyCFG pass will merge for.body and for.inc into a single block. Other issues are nested for-loops which may have names such as for.body.if.for.body4.

Clang choses some block name as a jump target for syntactical for-statements (llvm-project/CGStmt.cpp at 7c26641d9dcea70a75ca48d2e3a5bf6ca7a925bb · llvm/llvm-project · GitHub). It doesn’t mean it will reliably do so. For instance, in the linked code it will not even create such a basic block if the for statement has no condition (llvm-project/CGStmt.cpp at 7c26641d9dcea70a75ca48d2e3a5bf6ca7a925bb · llvm/llvm-project · GitHub) because no jump target is needed. For other kinds of loops, it uses different names such as while.body (llvm-project/CGStmt.cpp at 7c26641d9dcea70a75ca48d2e3a5bf6ca7a925bb · llvm/llvm-project · GitHub). If you build a loop out of gotos, it will not even have those.