【输入输出】
一个过程的所有基本块,除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. 遍历基本块:对每个基本块调用局部复写传播,当遍历结束后,全局复写传播就完成了
【分析】
数据流分析的复杂度取决于基本块总数及指令总数,局部复写传播的复杂度取决于基本块的指令总数,遍历基本块复杂度取决于基本块数量。全局复写传播会造成无用的赋值指令,但是这正给死代码删除和强度削减(比如两个相同的整型变量加法用移位代替)提供了机会
posted on 2023-09-06 23:13
春秋十二月 阅读(77)
评论(0) 编辑 收藏 引用 所属分类:
Compiler