[llvm-dev] Finding label of basic block where a conditional branch merges

[David Greene via llvm-dev]

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