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

[Sebastian Roland via llvm-dev]

Hi,

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

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

My current algorithm basically works for a lot of cases but fails here. 
What I am doing is to push the branch instruction to a stack and then 
always use the left most label of the next terminator instruction to 
move forward. Whenever I encounter a basic block that contains an "end" 
in its label I pop from the stack, whenever there is a conditional 
branch I push. If the stack is empty I have reached the correct basic 
block. For the example given it would however yield "do.end" which is 
not correct.

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?

--Sebastian

-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 3992 bytes
Desc: S/MIME Cryptographic Signature
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20190129/d982ce5e/attachment.bin>