放置Φ函数

朴素的算法会在每个汇合点结点起始处为每个变量放置一个Φ函数，有了支配边界之后，编译器可以更精确地判断何处可能需要Φ函数

其基本思想很简单，基本程序块b中对x的定义，则要求在DF(b)集合包含的每个结点起始处都放置一个对应的Φ函数。因为Φ函数是对x的一个新的定义，此处插入的Φ函数进而可能导致插入额外的Φ函数

编译器可以进一步缩小插入的Φ函数集合。只在单个基本程序块中活动变量，绝不会出现与之相应的活动的Φ函数。为应用这一见解，编译器可以计算跨多个程序块的活动变量名的集合，该集合被称为全局名字(global name)集合，它可以对该集合中的名字插入Φ函数，而忽略不在该集合中的名字

编译器可以用很小的代价找到全局集合。在每个基本程序块中，编译器可以查找具有向上展现用法的名字，即活动变量计算的UEVar集合

任何出现一个或多个LiveOut集合中的名字，都必须出现在某个基本块中的UEVar集合中

将所有UEVar集合取并集，编译器即可得到在一个或多个基本程序块入口处活动的名字的集合，显然此即活动于多个程序块中的名字和集合

如图9-9a所示的算法衍生自计算UEVar的显然算法。该算法构造了单个集合Globals,而LiveOut的计算则必须对每个基本程序分别计算则必须对每个程序分别计算出一个不同的集合

随着算法构建Globals集合，它同时也为每个名字构造一个列表，包含了所有定义该名字的基本程序块。这些程序块列表充当了一个初始化的WorkList，供插入Φ函数的算法使用

插入Φ函数的算法如图9-9b所示。对于每个全局名字x，算法将WorkList初始化为Blocks(x). 对于WorkList上每个基本块程序块b，算法在b的支配边界中每个程序块d的起始处插入Φ函数

因为根据定义，一个基本块程序中的所有Φ函数都是并发执行的，所以算法可以按任何次序在d的起始插入这些Φ函数。在向d添加对应于x的Φ函数之后，算法将d添加WorkList，以反映d中对x的新赋值操作

Φ函数插入算法

Φ函数插入算法中第一步是找到全局名字集合并为每个名字计算Blocks集合。对于图9-10a中的代码，全局名字集合是{a, b, c, d, i}

图9-10d给出了Blocks集合，请注意，算法为y和z创建Blocks集合，虽然二者并不在Globals中。将Globals和Blocks的计算分离开来，可以避免实例化这些额外的集合，代价是需要增加一趟对代码对处理

Φ函数重写算法

Φ函数重写算法逐个处理各个名字。考虑其对例子中变量a的操作，它会将WorkList 初始化为Blocks(a)，其中包含B1和B5

B1中的定义使得在DF(B1) = {B1} 中的各个基本块起始处插入一个Φ函数，该操作也将B1加入到WorkList中

接下来，它从WorkList 删除B5，并在DF(B5) = {B3} 中的每个基本程序起始处插入一个Φ函数

在程序块B3处的插入操作也会将B3置于WorkList上。在算法将B3从WorkList移除时，它试图将一个Φ函数添加到B1起始处，因为B1 ∈ DF(B3)

在算法将B3从WorkList移除时，因此不会执行插入。因而，对a的处理停止下来，此时WorkList为空

算法对Globals中的每个名字遵循相同的逻辑，如此会产生以下插入操作

由此生成的代码如下

将算法的处理限于全局名字集合，使其避免了对基本块B1中的x和y插入"死亡"的Φ函数(B1 ∈ DF(B3), B3包含了对x和y的定义)

但局部名字和全局名字之间的区分不足以避免所有的“死亡”Φ函数

• 例如, B1中b的Φ函数是不活动的，因为在使用b值之前重新定义定义了b

• 为避免插入这些Φ函数，编译器可以构建LiveOut集合，并在插入Φ函数之算法的内层循环中增加一个对变量活动性的条件判断

  • 这一改动使得算法可以产生剪枝静态单赋值形式