Transfer Function：OUT[B] = genB U (IN[B] - killB)
OUT[B]: 是基本块B的输出可用表达式集合，即离开基本块B仍然有效的表达式集合
genB: 是在基本块B中生成表达式集合，这些表达式在B中计算并且其值在B的末尾是已知的
IN[B]: 是进入基本块B的输入可用表达式集合，即到达基本块B之前已经计算并且其值仍然有效的表达式集合
killB: 是在基本块B中被“杀死”的表达式集合，即因为这些表达式中的变量在B中被重新赋值，所以它们在B的末尾不再有效
这个等式可以这样理解:
-
IN[B] - killB 表示从输入集合中移除所有在当前基本块中被重复赋值的变量所对应的表达式
-
genB U (IN[B] - killB) 表示将当前基本块中生成的表达式与调整的输入集合合并，形成输出集合
代码片段
a = b + c;
d = a + 1;
e = a + 1; // 这可能是公共子表达式
对应的三个基本块(为了简化，假设每行代码对应一个基本块):
-
基本块B1: a = b + c
-
基本块B2: d = a + 1
-
基本块B3: e = a + 1
分析过程如下:
对于基本块B1:
-
genB1 = { a = b + c}
-
killB1 = {} (因为a在B1中是第一次被赋值，没有表达式被杀死)
-
OUT[B1] = {} (因为这是程序开始，没有输入表达式) 并上 genB1 = {a = b + c}
对于基本块B2:
-
IN[B2] = OUT[B1] = {a = b + c}
-
genB2 = {d = a + 1}
-
killB2 = {a} （因为a在B2中被重新赋值）
-
OUT[B2] = genB2 U (IN[B2] - killB2) = {d = a + 1} (注意 a = b + c 因为a被重新赋值而失效)
对于基本块B3:
-
IN[B3] = OUT[B2] = {d = a + 1}
-
genB3 = {e = a + 1}
-
killB3 = {a} (因为a在B3中被重新赋值，但实际上这里没有改变输入集合，因为a在B2已经被杀死了)
-
OUT[B3] = genB3 U (IN[B3] - killB3) = {d = a + 1, e = a + 1} （此时，由于a没有被使用，所以e = a + 1可以作为可用表达式）
Control Flow：IN[B] = ∩P a_predecessor_of_B OUT[P]
IN[B]：表示进入基本块B的可用表达式集合
OUT[P]：表示从基本块P出去的可用表达式集合
∩P a_predecessor_of_B：表示对所有P的交集，其中P是基本块B的所有前置基本块（即所有直接指向B的基本块）
例子:
1. a = b + c;
2. if (a > 10) {
3. d = a + 1;
4. } else {
5. d = a - 1;
6. }
7. e = a + d;
对应的基本块可以是：
-
B1: a = b + c;
-
B2: if (a > 10) {
-
B3: d = a + 1;
-
B4: } else {
-
B5: d = a - 1;
-
B6: }
-
B7: e = a + d;
现在，我们来看基本块B7的输入可用表达式集合IN[B7]
B7的前置基本块是B3和B5，因为它们在控制流中直接指向B7
-
OUT[B3] 可能包含 {d = a + 1, a = b + c}（假设在B3中没有其他对a和d的赋值）
-
OUT[B5] 可能包含 {d = a - 1, a = b + c}（同样假设在B5中没有其他对a和d的赋值）
那么，IN[B7] = ∩{B3, B5} OUT[P] 将是两个集合的交集：
-
{d = a + 1, a = b + c} ∩ {d = a - 1, a = b + c}
-
交集为 {a = b + c}，因为d的值在两个分支中是不同的，所以在B7中不能确定d的确切值
因此，进入B7的可用表达式集合只包含 {a = b + c}，这意味着在B7中，我们可以使用表达式 a = b + c 的值，但是不能确定d的值，因为d的值依赖于控制流