编译原理(十) wu-kan

考虑以下基本块

t0 = 5;
t1 = 3 * t0;
t2 = R + r;
t3 = t1 * t2;
t4 = t2;
t5 = t3 - t4;
t6 = t1 * t2;
A = t6 + t5;
B = A – r;
t7 = t1;
B = t7 + B;

构造这一基本块的 DAG

flowchart BT
N3-->N5
N4-->N5
N2-->N6
N5-->N6
N5-->N7
N6-->N7
N6-->N8
N7-->N8
N8-->N9
N4-->N9
N2-->N10
N9-->N10
N1["
    N1
    t0
    5
"]
N2["
    N2
    t1, t7
    15
"]
N3["
    N3
    R
"]
N4["
    N4
    r
"]
N5["
    N5
    t2, t4
    R + r
"]
N6["
    N6
    t3, t6
    t1 * t2
"]
N7["
    N7
    t5
    t3 - t4
"]
N8["
    N8
    A
    t6 + t5
"]
N9["
    N9
    B
    A - r
"]
N10["
    N10
    B
    t7 + B
"]

假设只有 A 和 B 在基本块后面还要被引用, 产生优化后的三地址代码

t2 = R + r;
t3 = 15 * t2;
t5 = t3 - t2;
A = t3 + t5;
B = A - r;
B = B + 15;

考虑下列代码片段, 为这段代码划分基本块(Basic Block),并画出控制流图(Control Flow Graph). 在答案中你可以直接画出控制流图,但对图中的每个结点,请用 m~n 表示相应的基本块由第 m 至第 n 条语句组成

m = 0               // 1
v = 0               // 2
if v >= n goto (19) // 3
r = v               // 4
s = 0               // 5
if r < n goto (9)   // 6
v = v + 1           // 7
goto (3)            // 8
s = v + r           // 9
y = 0 * x           // 10
z = v - y           // 11
x = z + r           // 12
r = m - x           // 13
if s <= m goto (17) // 14
m = s               // 15
s = s + r           // 16
r = r+1             // 17
goto (6)            // 18
return m            // 19

在下面的控制流图中,每个节点代表一个划分的基本块。

flowchart TB
N1-->N2
N2--else-->N3
N3-->N4
N4--else-->N5
N5-->N2
N4--"if r < n"-->N6
N6-->N7
N7--else-->N8
N8-->N9
N7--"if s <= m"-->N9
N9-->N4
N2--"if v >= n"-->N11
N1["1~2"]
N2["3"]
N3["4~5"]
N4["6"]
N5["7~8"]
N6["9~13"]
N7["14"]
N8["15~16"]
N9["17~18"]
N11["19"]