# Can a basic-block have more than 2 outgoing edges?

For the ease of analysis (i.e., static analysis), I am planning to convert a control-flow graph, of a function, into a spanning tree by removing the backward edges. I wonder whether this spanning tree can be considered as a binary tree? That is, is it possible for a basic-block to have more than 2 out-going edges?

## 1 Answer

It depends on target's assembly language and compiler which your executable was compiled with. For example C language switch/case clause may be implemented in a manner which allows your tree to be not binary.

``````switch (a)
{
case 1:
return 1;
break;
case 2:
return 10;
break;
case 3:
return 100;
break;
case 4:
return 1000;
break;
case 5:
return 10000;
break;
default:
return -1;
break;
}

00000000004004ed <main>:
4004ed:   55                      push   %rbp
4004ee:   48 89 e5                mov    %rsp,%rbp
4004f1:   89 7d fc                mov    %edi,-0x4(%rbp)
4004f4:   48 89 75 f0             mov    %rsi,-0x10(%rbp)
4004f8:   83 7d fc 05             cmpl   \$0x5,-0x4(%rbp)
4004fc:   77 47                   ja     400545 <main+0x58>
4004fe:   8b 45 fc                mov    -0x4(%rbp),%eax
400501:   48 8d 14 85 00 00 00    lea    0x0(,%rax,4),%rdx
400508:   00
400509:   48 8d 05 c4 00 00 00    lea    0xc4(%rip),%rax        # 4005d4 <_IO_stdin_used+0x4>
400510:   8b 04 02                mov    (%rdx,%rax,1),%eax
400513:   48 63 d0                movslq %eax,%rdx
400516:   48 8d 05 b7 00 00 00    lea    0xb7(%rip),%rax        # 4005d4 <_IO_stdin_used+0x4>
40051d:   48 01 d0                add    %rdx,%rax
400520:   ff e0                   **jmpq   *%rax**
400522:   b8 01 00 00 00          mov    \$0x1,%eax
400527:   eb 21                   jmp    40054a <main+0x5d>
400529:   b8 0a 00 00 00          mov    \$0xa,%eax
40052e:   eb 1a                   jmp    40054a <main+0x5d>
400530:   b8 64 00 00 00          mov    \$0x64,%eax
400535:   eb 13                   jmp    40054a <main+0x5d>
400537:   b8 e8 03 00 00          mov    \$0x3e8,%eax
40053c:   eb 0c                   jmp    40054a <main+0x5d>
40053e:   b8 10 27 00 00          mov    \$0x2710,%eax
400543:   eb 05                   jmp    40054a <main+0x5d>
400545:   b8 ff ff ff ff          mov    \$0xffffffff,%eax
40054a:   5d                      pop    %rbp
40054b:   c3                      retq
``````

for example

``````400520: ff e0                   **jmpq   *%rax**
``````

instruction implements switch.case jumps in this example. Obviously the basic block which ends with this jump will have 6 out-going edges.

Any other indirect jump may also produce such a situation.

There are some good examples in this article. So, the answer to your question is definitely yes, there are basic blocks with more than 2 out-going edges and your spanning tree can not be considered as binary.

• I agree with your answer. But, if its a indirect jmp, then is it even possible to determine the jmp targets without using any program analysis technique such as VSA (value set analysis). In such situation (i.e., unable to resolve the indirect jump staticly, which is common most of the cases). Is it safe to assume it jumps to only 1 target? Commented Nov 1, 2015 at 11:25
• If I understand your question correctly it is not safe. The simplest example that comes to mind is C++ code with calls to virtual functions.
– w s
Commented Nov 1, 2015 at 11:41
• A switch can also be compiled as `jmp [table+4*offset]`, and in that case you may have lots of branches. Commented Nov 1, 2015 at 15:03
• The ARM architecture has a couple of 32-bit Thumb instructions,`TBB` and `TBH`, for simple jump table calculations like this. infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.dui0489c/… Commented Nov 3, 2015 at 7:26