Open BruceChen7 opened 1 year ago
位置u和v在同一时间是否都是活跃的？的问题
如果变量或寄存器的当前值在程序的某个后续点中被使用，则该变量或寄存器是活跃的。
将变量、栈位置和寄存器统称为位置
movq $5, a movq $30, b movq a, c movq $10, b addq b, c
因为 a 在第 1 行到第 3 行是活跃的，
b 在第 4 行到第 5 行是活跃的。
在第 2 行写入的整数从未使用，因为它在下一次读取（第 5 行）之前被覆盖（第 4 行）
每条指令的活跃位置能通过反向遍历指令序列（即按执行顺序向后）来计算。
设 I1，...，In 为指令序列。写 Lafter（k）表示指令 Ik 之后的活跃位置集，写 Lbefore（k）表示指令Ik 之前的活跃位置集。
活跃期定义是从变量第一次被定义（赋值）开始，到它下一次被赋值前的最后一次被使用为止。
在一条指令执行后，其活跃位置就是其 live-after 集合，而在一条指令执行前，其活跃位置就是其 live-before 集合。
一条指令的live-after 集合始终等于下一条指令的 live-before 集合。
Lafter(n) =∅
Lafter(k) =Lbefore(k+ 1)
Lbefore(k) = (Lafter(k) –W(k))∪R(k),
对于 addq b, c 指令，Lafter 为∅，因为它是最后一条指令。这个指令的 Lbefore 是{b,c}，因为它从变量 b 和 c 读取。
每条指令都有一个编号，从 1 到 n。对于每个指令，定义以下集合：
例外情况：如果 Succ[i]=∅，那么 out[i]是出现在函数结果中的变量集合。
方程通过迭代到一个固定点来解决：in[i]和 out[i]被初始化为∅，并迭代直到没有更改发生。
int a, b, c, d, e, f; a = c – d; e = a – b; f = e + 3;
在表达式 e = a – b;之后，变量a 就没有被再使用。
同样，在表达式 f = e + 3;之后，变量 e 就没有被再使用。
因此，a、e、f能被分配给同一个寄存器而寄存器中保存的值不会产生冲突。
经过上述处理，能只使用 4 个寄存器 s1、s2、s3、s4 替换 6 个变量，代码可表示为：
s1 = s2 - s3 s1 = s1 - s4 s1 = s1 + 3
如果程序中临时变量 t1 和 t2 在任何时候只有一个是活跃的，那么它们能共用同一个寄存器！
参考资料
寄存器分配
位置u和v在同一时间是否都是活跃的？的问题（如果是，它们不能分配到同一个寄存器）如何做到将一个寄存器分配给多个变量又不至引起冲突呢？
活性分析（Liveness Analysis）
如果变量或寄存器的当前值在程序的某个后续点中被使用，则该变量或寄存器是活跃的。
将变量、栈位置和寄存器统称为位置
因为 a 在第 1 行到第 3 行是活跃的，
b 在第 4 行到第 5 行是活跃的。
在第 2 行写入的整数从未使用，因为它在下一次读取（第 5 行）之前被覆盖（第 4 行）
每条指令的活跃位置能通过反向遍历指令序列（即按执行顺序向后）来计算。
设 I1，...，In 为指令序列。写 Lafter（k）表示指令 Ik 之后的活跃位置集，写 Lbefore（k）表示指令Ik 之前的活跃位置集。
活跃期定义是从变量第一次被定义（赋值）开始，到它下一次被赋值前的最后一次被使用为止。
在一条指令执行后，其活跃位置就是其 live-after 集合，而在一条指令执行前，其活跃位置就是其 live-before 集合。
一条指令的live-after 集合始终等于下一条指令的 live-before 集合。
Lafter(n) =∅
Lafter(k) =Lbefore(k+ 1)
Lbefore(k) = (Lafter(k) –W(k))∪R(k),
对于 addq b, c 指令，Lafter 为∅，因为它是最后一条指令。这个指令的 Lbefore 是{b,c}，因为它从变量 b 和 c 读取。
换个方式理解活性分析
每条指令都有一个编号，从 1 到 n。对于每个指令，定义以下集合：
例外情况：如果 Succ[i]=∅，那么 out[i]是出现在函数结果中的变量集合。
方程通过迭代到一个固定点来解决：in[i]和 out[i]被初始化为∅，并迭代直到没有更改发生。
一个例子
在表达式 e = a – b;之后，变量a 就没有被再使用。
同样，在表达式 f = e + 3;之后，变量 e 就没有被再使用。
因此，a、e、f能被分配给同一个寄存器而寄存器中保存的值不会产生冲突。
经过上述处理，能只使用 4 个寄存器 s1、s2、s3、s4 替换 6 个变量，代码可表示为：
如果程序中临时变量 t1 和 t2 在任何时候只有一个是活跃的，那么它们能共用同一个寄存器！
冲突图 (interference Graph)
type/system #public