Essentials of Compilations (Part 1)

Chapter 2

%rsp 总是指向 stack 的 top。

当调用函数时，函数的 return address 会被 push 到 stack 上，即这时 %rsp 指向 return address。然后

pushq %rbp
movq %rsp %rbp
subq 16 %rsp

把 %rbp (即 old %rbp，函数调用前的值) push 到 stack 上，这时 %rsp 指向这个位置，然后 movq %rsp %rbp 即当前的 %rbp 指向这个位置，然后把 stack 向下扩展 16 Bytes，供存放参数等。

在结束函数调用时，用相反的顺序

addq 16 %rsp
popq %rbp
retq

缩减 %rsp (%rsp => %rbp)，恢复 %rbp (%rsp => return address)，然后 retq 会从 stack 弹出 return address 并把 program counter 置为 return address，程序结束此次函数调用继续运行。

Chapter 3

1. 在 "build-interference" pass, live-after set 的内在含义是什么？

《编译器设计 (Engineering a Compiler)》(2rd Edition) 11.5.1 节有解释 LiveNow 集合，及这里的 live-after 集合。

2. 为什么需要从后向前计算？

Lbefore(k) = (Lafter(k) − W(k)) ∪ R(k)

我们来描述一下，如指令 Ik 如 (movq (var x) (var y))，首先删除 W(k) 即 {y}，因为在这条指令后， y 就要被更新了，如果y在这条指令前是Live状态，那么y原本的值将丢失，则程序是错误的。所以y在这条指令前一定是Unlive状态，所以应该从 Lafter(k)集合中去掉。添加 R(k)即{x}同理可以解释为，因为在执行这条指令时要读取 x，在这条指令前一定是Live状态（如果不是Live状态呢？x的值是什么？)。

3. 可不可以从前向后计算，公式逆一下？

Lbefore(k) = (Lafter(k) − W(k)) ∪ R(k)

Lafter(k) = (Lbefore(k) − R(k)) ∪ W(k)

应该是不行，因为 ∪ 的逆不等价于 −。举例 Figure 3.2 的一段：

5 (addq (int 7) (var x))    {w, x}
6 (movq (var x) (var y))   {w, x, y}

如果按逆向

Lbefore(6) = (Lafter(6) - W(6)) ∪ R(6) = ({w, x, y} - {y}) ∪ {x} = {w, x} = Lafter(5)

计算出的 live-before 集合是正确的，如果按正向

Lafter(6) = (Lbefore(6) - R(6)) ∪ W(6) = (Lafter(5) - R(6)) ∪ W(6) = ({w, x} - {x}) ∪ {y} = {w, y} /= {w, x, y}

计算出的 live-after 集合是错误的。

wangwangwar / daily-notes