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 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;
case 2:
    return 10;
case 3:
    return 100;
case 4:
    return 1000;
case 5:
    return 10000;
    return -1;

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?
    – Maggie
    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
  • 2
    A switch can also be compiled as jmp [table+4*offset], and in that case you may have lots of branches.
    – Jongware
    Commented Nov 1, 2015 at 15:03
  • 1
    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/…
    – Ian Cook
    Commented Nov 3, 2015 at 7:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.