前期优化之全局复写传播
春秋十二月发表于 2023-09-06 15:13:00
【输入输出】
一个过程的所有基本块，除entry和exit外的每个基本块包含指令序列
【流程】
由前向数据流分析、局部复写传播和遍历基本块构成
1. 前向数据流分析：目标是计算出每个基本块入口处有效的复写赋值集合，这里定义为CPin(i)，i为基本块，其元素为表示复写赋值的四元组<u,v,blk,pos>，u为左变量，v为右变量，blk为基本块，pos为在blk中的位置。另外定义COPY(i)为基本块i中出现且到达了出口的那些复写赋值集合，即u和v在i中pos后没被赋值；KILL(i)为被基本块i杀死的那些赋值集合，即i中存在对其它基本块复写赋值右变量的赋值；CPout(i)为基本块i出口处有效的复写赋值集合。以上四种集合的数据流方程为：CPin(i)等于i的每个前驱p的CPout的交集，CPout(i)等于COPY(i)与CPin(i)减去KILL(i)之差的并集。CPout(entry)初值为空集，其它基本块的CPout初值为全集U，U为过程所有复写赋值的集合即所有基本块的COPY之并集，根据迭代求不动点法可算出每个基本块最终的CPin值
2. 局部复写传播：作为被全局复写传播调用的例程，有两个参数，一个为输入输出参数单个基本块，另一个为输入参数CPin，即前向数据流分析求得的结果。该例程内部维护一个有效复写赋值的表，称作ACP，其元素为二元组<u,v>，u是复写赋值的左变量，v是右变量。首先初始化ACP即将CPin中的复写赋值加入到ACP，再遍历基本块的每条指令，针对指令类别做对应的处理，有以下几种情况
a）对于一元/二元表达式及过程调用，将表达式的操作数或调用参数替换为ACP中对应元组的第二分量，若不存在这样的元组则不用替换
b）对于赋值语句（包括复写赋值），从ACP中删除第一或第二分量为赋值语句左变量的元组，这是为了删除被杀死的复写赋值
c）对于复写赋值且左变量u不等于右变量v，将元组<u,v>加入到ACP
当遍历结束后，局部复写传播就完成了
3. 遍历基本块：对每个基本块调用局部复写传播，当遍历结束后，全局复写传播就完成了
【分析】
数据流分析的复杂度取决于基本块总数及指令总数，局部复写传播的复杂度取决于基本块的指令总数，遍历基本块复杂度取决于基本块数量。全局复写传播会造成无用的赋值指令，但是这正给死代码删除和强度削减（比如两个相同的整型变量加法用移位代替）提供了机会