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

Question

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?

Answer 1

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.