Skip to content

Latest commit

 

History

History
110 lines (88 loc) · 3.51 KB

README.md

File metadata and controls

110 lines (88 loc) · 3.51 KB
Raw

Data Flow Analysis: Reaching Definitions

若程序中 P 点的定义 D 可以沿着 CFG 内的某条路径到达点 Q, 且这条路径中 D 没有被重新定义，则称程序中 P 到 Q 点的 D 是定义可达的。

注意，由于只要某条路径可达即满足条件，因此 Reaching Definitions 是 may analysis.

  • Reaching Definitions 的控制流： IN[B] = all_union(OUT, predecessor_of_b).
  • Reaching Definitions 的转移函数： OUT[B] = union(generated_of_B, exclude(IN[B], killed_in_B)).

注意，这里的 generated_of_B 是指块 B 内新定义的变量所在的行；kill_in_B 是指在块 B 内被覆盖的定义的行号。

Reaching Definitions 的算法实现

  • 输入：CFG
  • 输出：每个 BB 的 IN[B] 和 OUT[B].

其算法实现为：

OUT[entry] = empty
for BB in exclude(all_bbs, entry) {
  OUT[BB] = empty
}
while has_any_changed(OUT) {
  for BB in exclude(all_bbs, entry) {
    IN[B] = all_union (OUT, predecessor_of_b)
    OUT[B] = union(generated_of_B, exclude(IN[B], killed_in_B))
  }
}

示例

来看下面控制流图的定义可达性：

           Entry
             |
            \/
        |---------------|
B1      | 1. x = p + 1  |
        | 2. y = q + 2  |
        |---------------|
        |    |          |
        |   \/          |
    --> |---------------|
B2  |   | 3. m = k      |
    |   | 4. y = q - 1  |
    |   |---------------| ------
    |   |    |          |      |
    |   |   \/          |     \/
    |   |---------------|   |----------------|
B4  |   | 5. x = 4      |   | 7. x = m - 3   | B3
    |   | 6. z = 5      |   |                |
    --- |---------------|   |----------------|
        |    |          |      |
        |   \/          |      |
        |---------------|  <----
B5      | 8. z = 2p     |
        |---------------|
             |
            \/
           Exit

下表中 IN/OUT 的每一位分别代表 [D1, D2, D3, D4, D5, D6, D7, D8], 其中 D1 表示第一行，以此类推。

初始化：

BB IN OUT
1 xxxx xxxx 0000 0000
2 xxxx xxxx 0000 0000
3 xxxx xxxx 0000 0000
4 xxxx xxxx 0000 0000
5 xxxx xxxx 0000 0000

第一轮：

BB IN OUT 备注
1 0000 0000 1100 0000
2 1100 0000 1011 0000 IN[B[2]] = union(OUT[B4], OUT[B1])
3 1011 0000 0011 0010
4 1011 0000 0011 1100
5 0011 1110 0011 1011

相较于初始化后的 OUT, 第一轮后的 OUT 都发生了变化，因此需要第二轮：

BB IN OUT
1 0000 0000 1100 0000
2 1111 1100 1011 1100
3 1011 1100 0011 0110
4 1011 1100 0011 1100
5 0011 1110 0011 1011

相较于第一轮后的 OUT, 第二轮后的 OUT[B[2]], OUT[B[3]] 发生了变化，所以需要第三轮：

BB IN OUT
1 0000 0000 1100 0000
2 1111 1100 1011 1100
3 1011 1100 0011 0110
4 1011 1100 0011
5 0011 1110 0011 1011

第三轮结束后，OUT 没有发生变化，迭代结束。

下面来看 OUT 的含义，以 OUT[B[3]] 为例，0011 0110 表示第 3, 4, 6, 7 行的定义可以到达第 7 行。