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?

up vote 4 down vote accepted

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? – Maggie Nov 1 '15 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 Nov 1 '15 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. – usr2564301 Nov 1 '15 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 Nov 3 '15 at 7:26

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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