Skip to content

Latest commit

 

History

History
94 lines (78 loc) · 2.31 KB

README.md

File metadata and controls

94 lines (78 loc) · 2.31 KB

Basic Block and Control Flow Graph

本文介绍程序静态分析中两个最基本的概念：控制流图(Control Flow Graph, CFG)和基本块(Basic Block, bb)

Basic Block

Basic Block 是指满足以下特征的最长连续指令序列：

  • 只有一个入口，且该入口为这个 Basic Block 的第一个指令；
  • 只有一个出口，且该出口为这个 Basic Block 的最后一个指令。

构建 Basic Block 的算法

  1. 确定每个 Basic Block 的入口：
  • 程序的入口是一个 Basic Block 的入口；
  • 跳转语句的目标是一个 Basic Block 的入口；
  • 跳转语句后的下一个语句是一个 Basic Block 的入口；
  1. 每个 Basic Block 是以其入口为开始，到下一个 Basic Block 的入口前结束。

例如：

1.  x = input
2.  y = x - 1
3.  z = x * y
4.  if z < x goto (7)
5.  p = x / y
6.  q = p + y
7.  a = q
8.  b = x + a
9.  c = 2a - b
10. if p == q goto (12)
11. goto (3)
12. return

上述指令流的 Basic Block 可以划分为：

|-------------------------|
| 1.  x = input           |  程序入口
| 2.  y = x - 1           |
|-------------------------|
| 3.  z = x * y           |  跳转语句 11 的目标
| 4.  if z < x goto (7)   |
|-------------------------|
| 5.  p = x / y           |  跳转语句 4 的下一条语句
| 6.  q = p + y           |
|-------------------------|
| 7.  a = q               |  跳转语句 7 的目标
| 8.  b = x + a           |
| 9.  c = 2a - b          |
| 10. if p == q goto (12) |
|-------------------------|
| 11. goto (3)            |  跳转语句 10 的下一条语句
|-------------------------|
| 12. return              |  跳转语句 11 的下一条语句
|-------------------------|

Control Flow Graph

控制流图是一个有向图结构：

  • 节点为基本块；
  • 若块 A 的出口可以跳转到块 B, 则块 A 存在指向块 B 的边。此时，块 A 为块 B 的前驱；块 B 是块 A 的后继。

依据定义，上例中的控制流图为：

    Entry
      |
     \/
    {1, 2}
      |
     \/
|-> {3, 4}   ---
|     |        |
|    \/        |
|   {5, 6}     |
|     |        |
|    \/       \/
|   {7, 8, 9, 10}  ---
|     |              |
|    \/              |
|-- {11}             |
      |              |
     \/              |
    {12}  <-----------
      |
     \/
    Exit