CP-Homework9

:material-circle-edit-outline: 约 527 个字 :fontawesome-solid-code: 15 行代码 :material-clock-time-two-outline: 预计阅读时间 2 分钟

[!ABSTRACT] Modern Compiler Implementation in C.pdf
3220104929 250514

11.1

f : c ←r3
    p ←r1
    if p = 0 goto L1
    r1 ← M[p]
    call f           (uses r1,defines r1,r2)
    s ←r1
    r1 ← M[p+4]
    call f           (uses r1,defines r1,r2)
    t ←r1
    u ←s+t
    goto L2
L1 : u ←1
L2 : r1 ←u
    r3 ← c
    return           (uses r1,r3)

首先算出各指令的 in 与 out 集合：

行号	In	Out
1	r1, r3	c, r1
2	c, r1	c, p
3	c, p	c, p
4	c, p	c, p, r1
5	c, p, r1	c, p, r1
6	c, p, r1	s, c, p
7	s, c, p	s, c, r1
8	s, c, r1	s, c, r1
9	s, c, r1	s, t, c
10	s, t, c	c
12	c	c, u
13	c, u	r1, c
14	r1, c	r1, r3
15	r1, r3

基于此画出干涉图

K = 3，发现没有 degree 小于 3 的无合并边的结点，所以直接进行 coalescing，采用 George

然后溢出 s，然后简化 p，然后简化 r3, c，然后简化 r1, u, t，得到空图与 stack

然后开始分配颜色，发现 s 无法分配

改写原程序：

f : c1 ←r3
    M[cloc]←c1
    p ←r1
    if p = 0 goto L1
    r1 ← M[p]
    call f           (uses r1,defines r1,r2)
    s ←r1
    r1 ← M[p+4]
    call f           (uses r1,defines r1,r2)
    t ←r1
    u ←s+t
    goto L2
L1 : u ←1
L2 : r1 ←u
    c2←M[cloc]
    r3 ← c2
    return           (uses r1,r3)

算出各指令的 in 与 out 集合：

行号	In	Out
1	r1, r3	c1, r1
2	c1, r1	r1
3	r1	p
4	p	p
5	p	p, r1
6	p, r1	p, r1
7	p, r1	s, p
8	s, p	s, r1
9	s, r1	s, r1
10	s, r1	s, t
11	s, t
13		u
14	u	r1
15	r1	r1, c2
16	r1, c2	r1, r3
17	r1, r3

基于此画出干涉图

K = 3，发现没有 degree 小于 3 的无合并边的结点，所以直接进行 coalescing，采用 George

然后简化 p，然后简化 s，然后简化 r1, u, t，然后简化 c1, c2, r3，得到空图与 stack

然后开始分配颜色

Node	Color
c1	r3
c2	r3
r1	r1
r2	r2
r3	r3
p	r3
s	r2
t	r1
u	r1

11.3

a

先 spill 掉 a，然后 stack 如下：

g
f
e
d
c
b
a

然后染色：

Node	Color
g	4
f	4
e	3
d	2
c	1
b	2
a	1

能够全部染色，故有一个 potential spill，无 actual spill

b

如果 Briggs criterion 发现可合并 f 和 g

stack 如下：

b
a
f, g
e
c
b

然后染色：

Node	Color
b	4
c	1
e	2
f, g	3
a	2
b	1

能够全部染色，故无 potential spill，无 actual spill