[llvm-dev] Finding label of basic block where a conditional branch merges (original) (raw)

David Greene via llvm-dev llvm-dev at lists.llvm.org
Tue Jan 29 12:40:17 PST 2019

Sebastian Roland via llvm-dev <llvm-dev at lists.llvm.org> writes:

is there any standard way to figure out the label of the basic block where a conditional branch merges?

What do you need to use this block for? The immediate post-dominator will be the block where control essentially re-converges. It is the "nearest" block guaranteed to execute if the block containing the branch executes.

See PostDominatorTreeAnalysis.

Depending on where you are in the pass pipeline, the CFG maty bear little resemblence to high-level control flow.

If we have a branch statement without an else part this is straightforward:

br i1 %cmp, label %if.then, label %if.end, !dbg !24 We only need to check the operand names whether they contain "end".

This seems extremely brittle. Post-dominators is the compiler-theory-y way to determine this.

However things are getting more complex when there is an else branch and in particular when we have nested branches.

Take for example the following C code: if (x == NULL || y == NULL) { do { // ... } while (0); } This yields the following IR: br i1 %cmp, label %if.then, label %lor.lhs.false, !dbg !31 lor.lhs.false:                                    ; preds = %entry %1 = load %struct.s1*, %struct.s1** %s1.addr, align 8, !dbg !32 %cmp1 = icmp eq %struct.s1* %1, null, !dbg !33 br i1 %cmp1, label %if.then, label %if.end, !dbg !34 if.then:                                          ; preds = %lor.lhs.false, %entry br label %do.body, !dbg !35, !llvm.loop !37 do.body:                                          ; preds = %if.then br label %do.end, !dbg !39 do.end:                                           ; preds = %do.body br label %if.end, !dbg !41 if.end:                                           ; preds = %do.end, %lor.lhs.false call void @llvm.dbg.declare(metadata i32* %a, metadata !42, metadata !24), !dbg !43

The question now is how to obtain "if.end" given br i1 %cmp, label %if.then, label %lor.lhs.false, !dbg !31.

if.end post-dominates the block containing the branch in question and it is also the immediate post-dominator (it does not post-dominate any other block that post-dominates the block containing the branch).

I am wondering whether there is any known graph algorithm I could use to solve the problem or even better something that is already implemented within LLVM?

Post-dominators. :)

                             -David

More information about the llvm-dev mailing list