重命名

在最终的静态单赋值形式，每个全局名字都变为一个基本名，而对该基本名的各个定义则通过添加数字下标区分

对于对应到源语音变量的名字，比如说x，算法使用x作为基本名。因而，重命名算法遇到的对x的第一个定义将命名为x0,第二个将命名为x1

该算法如上图所示，对过程的支配者树进行了先根次序遍历，其中对定义和使用都进行了重命名

在每个基本程序块中，算法首先重命名由程序块顶部的Φ函数定义的值，然后按序访问程序块中的各个操作。算法会用当前的静态单赋值形式重写各个操作数，接下来为操作的结果创建一个新的静态单赋值形式名(NewName())

算法的后一步使得新名字成为当前的名字。在程序块中所有的操作都已经重写之后，算法将使用当前的静态单赋值形式名重写程序块在CFG中各后继结点中的适当Φ函数参数

最后，算法对当前程序块在支配树中的子结点进行递归处理。当算法从这些递归调用返回时，它会将当前静态单赋值形式名的复合恢复到访问当前程序块之前的状态

为管理这一处理过程(递归流程)，算法对每个全局名字使用一个计数器和一个栈

• 全局名字的栈包含了该名字当前静态单赋值形式的下标

• 在每个定义处，算法通过将目标名字的当前计数器值压栈产生新的下标，并将计数器加1

• 因而，名字n栈顶的值总是n当前静态单赋值形式名的下标

• 作为处理程序块的最后一步，算法会将该程序块中产生的所有名字从栈中弹出，以恢复在该程序块的直接支配结点末尾处的当前静态单赋值形式名字集合

• 处理当前程序块在支配者树中余下的兄弟结点，可能需要这些名字

栈和计数器服务于不同且分离的目的。当算法中的控制流在支配者树中上下移动时，栈模拟了当前程序块中最新定义的生命周期。另一方面，计数器则是单调递增的，以确保各个连续的定义都能分配一个唯一的静态单赋值形式名

图9-12总结了该算法。该算法初始化了栈和计数器，然后对支配者树的根结点(CFG的入口结点)调用Rename

Rename 会重写该程序块，并下降到其在支配者树的各个后继结点上递归处理。为完成对该程序块的处理，Rename会弹出处理该程序块期间压栈的任何名字

函数NewName会操纵计数器和栈，以按需创建新的静态单赋值形式名

在程序块b末尾处，Rename必须重写b在CFG中的各个后继结点中Φ函数的参数。编译器必须在这些Φ函数中为b按序分配一个参数槽位

在绘制静态单赋值形式时，总是假定从左到右的次序，以便匹配从左到右绘制边的次序。但在内部，编译器可以按任何一致的方式对边和参数槽位编号，以产生所需的结果。这要求构建静态单赋值形式的代码与构建CFG的代码之间的协作

将重命名算法应用到 9-11中的代码中。假定a0、b0、c0和d0是在进入B0时时定义的

图9-13给出了全局名字集合中各个名字的计数器和栈在重命名处理期间各个时间点上的状态。算法对支配者树进行一趟先根次序遍历，这对于按名字的递增次序访问各个结点，从B0到B8,各个栈和计数器的配置如图9-13a所示

程序块B0 该程序只包含一个操作

• Rename 会将i重写为i0,将计数器加1，并将i0压入i的栈中

• 接下来，算法将访问B0在CFG中的后继结点B1,并将与B0对应的Φ函数参数重写为其当前名字: a0, b0, c0, d0和i0

• 接下来，算法递归到B0在支配树中的子结点B1

• 处理完B1之后，算法将弹出i的栈并返回

程序块B1 Rename进入B1时的状态如图9-13b所示

• 算法会将Φ函数的目标重写为新的名字a1,b1,c1,d1和i

• 接下来，算法为a和c的定义创建新名字，并重写它们，它还会重写比较操作使用的a和c

• 它还会重写比较操作中使用的a和c

• B1在CFG的两个后继结点都没有Φ函数，因此算法将递归到B1在支配树中的子结点B2、B3和B5

• 处理完这些子结点，算法会弹出处理B1期间压栈的数据并返回

程序块B2 Rename进入B2时的状态如图9-13c所示

• 该程序块没有需要重写的Φ函数

• Rename重写了b，c和d的定义，并为其分别创建了一个新的静态单赋值形式名

• 算法接下来重写B2在CFG中后继结点B3中的Φ函数的参数

图9-13d给出了在弹栈之前的栈和计数器。最后，算法会弹栈并返回

程序块B3 Rename进入B3时的状态如图9-13e所示

• 请注意，此时栈已经恢复到Rename进入B2时的状态，但计数器仍然反映出算法曾经在B2内部创建的新名字

• 在B3中，Rename会重写Φ函数的目标，并为这些目标分别创建新的静态单赋值形式名

• 接着，算法重写程序块中的各个赋值操作，将使用替换为当前的静态单赋值形式名，将定义替换为创建的新静态单赋值形式名

B3在CFG中有两个后继结点B1和B4。在B1中，算法使用如图9-13f所示的栈和计数器，重写了与来自B3的边对应的Φ函数参数。接下来，R ename递归到B3在支配者树中的子结点B4.在调用返回时，Rename将弹栈并返回

程序块B4 该程序块只包含一条返回语句

• 其中没有Φ函数、定义、使用，而其在CFG或支配者树中也没有后继结点

• 因为，Rename不执行任何操作，不会改变栈和计数器

程序块B5 在处理B4之后，Rename将弹出B3期间的压栈数据，返回到B1末尾处的状态

• 此时的栈如图9-13g所示，算法将递归到B3期间的压栈数据，返回到B1末尾处的状态

• B5没有函数。Rename会重写两个赋值语句和条件语句中的表达式，并按需创建新的静态单赋值形式名

• B5在CFG中的两个后继结点都没有Φ函数

• Rename接下来递归到B5在支配者树中的子结点B6、B7、B8

• 最后，算法会弹栈并返回

程序块B6 Rename 进入B6时的状态如图9-13h 所示

• B6 没有Φ函数，Rename将重写对d的赋值，产生新的静态单赋值形式d5

• 接着，算法访问B6在CFG中的后继结点B7中的Φ函数

• 它会将对应于来自B6的代码路径的Φ函数参数重写为当前的名字C2和d5

• 由于B6在支配者树中没有子结点，它将对d弹栈并返回

程序块B7 Rename进入B7时的状态图9-13i所示

• 算法首先用新的静态单赋值形式名c5和d6重命名Φ函数的目标

• 接下来，它用新的静态单赋值形式名b4重写对b的赋值操作

• 然后，算法用当前静态单赋值形式名的集合，来重写B7在CFG中后继结点B3中Φ函数的参数

• 由于B7在支配者树中没有子结点，算法将弹栈并返回

程序块B8 Rename 进入B8时的状态9-13j所示

• B8没有Φ函数。Rename将用新的静态单赋值形式名C6重写对C的赋值操作

• 算法会考察B8在CFG中后继结点B7，并将对应的Φ函数参数重写为其当前的静态单赋值形式名C6和d4

• 由于B8在支配者树中没有子结点，算法将弹栈并返回

图9-14给出了Rename停止之后的示例代码