此文是Fred Chow在德拉华大学所讲open64课程讲义的翻译，转载请注明出处 http://www.lingcc.com
Fred Chow 原版讲义见最后一页
全局标量优化II-Main-OPT
- 三种和依赖有关的优化策略(Re-cap?)
- 删除无用计算—死存储删除
- 删除冗余计算—通用子表达式、循环无关代码移动、部分冗余删除
- 计算排序—循环转换、指令调度
- 本节将会讨论前两种
- 部分冗余删除
- 什么是部分冗余—执行某些路径时的冗余计算
- 方法：在非冗余路径上插入的计算导致的完全的冗余(相对于部分冗余)
- 这样，完全的冗余就会被删除
- 部分冗余删除比循环无关代码外提要好
- 部分冗余删除算法
- 懒代码外提是最好的PRE算法
-
-
- 最理想计算方式—没有其他的代码能使编译生成的二进制隐形更快–更何况在执行过程中的路径跳转
- 活跃区间最优化—没有其他的最优化计算代码能获得临时变量更小的活跃区间
- 另外，不需要双向的数据流(?)
-
-
- SSAPRE是能应用在 SSA图上的PRE算法
- 稀疏变量version的懒代码外提(?)
- 理解算法需要更多的直觉
- SSAPRE是能应用在 SSA图上的PRE算法
- SSAPRE的动机
- 完全冗余首先开始于在支配边界计算/转换为部分冗余(?)
- 使用SSA解决冗余问题
- 使用临时变量h对问题建模来为表达式构建SSA
- h的定义：计算表达式并保存结果
- h的使用：重新装载较早时保存的结果
- 相同的SSA version表示相同的计算结果
- 仅需要在phi节点的入边插入
- PRE数据流分析在SSA图上进行
- 使用临时变量h对问题建模来为表达式构建SSA
- SSAPRE算法
-
- SSA构建
-
-
- 插入PHI
- 重命名
- 数据流分析
-
-
-
- DownSafety
- WillBeAvail
- 转换程序
- 最终化SSA
- 代码外提
-
- 第一步：插入PHI
- 如同SSA中的变量：在表达式的支配边界上
- 附加规则：将变量的值转换为phi节点结果的变量值.
- 第二步重命名
- 像SSA的重命名一样对h赋予SSA中的version
- 附加的规则：仅在一个变量相同的SSA version处有相同的h version
- 第三步DownSafety
- 仅能在表达式能被预测的PHI节点(downsafe)处插入—计算最优化的时候需要(?)
- 将所有的PHI节点初始化为downsafe
- 将没有出现又能到达出口的PHI节点定义为not-downsafe（边界条件)
- 依据使用-定义边向后传播not-downsafe属性
- 排除有真实出现的使用-定义边(通过has-real-use标记)
- 第四步WillBeAvail
- 目的：为PRE插入识别PHI节点
- 使用两个沿使用-定义边的向前传播(?)
- 第一部分：为实现计算最优化
-
-
-
can_be_avail给出最优化计算的可能插入点
-
将所有的PHI初始化为can_be_avail
-
将所有非downsafe且有至少一个操作数为步骤二中重命名的操作数的PHI节点标记为not-can_be_avail(边界条件)
-
将not-can_be_avail属性沿定义-使用边向上传播给非downsafe节点
-
-
-
-
第二部分：实现活跃区间最优化
-
-
-
-
找到最新的插入点
- 对于所有can_be_avail的PHI节点：later表示次要的，not-later表示最新的插入点
- 主要想法：若PHI操作数由真实计算定义，插入就不能是次要的，否则会引入冗余(?)
- 将所有任一操作数由真实计算定义且标记为not-later的PHI节点标记为can_be_avail（边界条件)
- 将此not-later属性沿定义-使用边向前传播
-
-
-
-
插入标准：
- WillBeAvail = can_be_avail 和not-later的交集
- 在willBeAvail的PHI节点处，满足以下两种情况之一时，插入PHI操作数
-
操作数步骤二中插入的
- has_real_use为假且此值由非WillBeAvail的PHI节点定义
-
-
-
步骤五：最终化
- 将h整合为真正的SSA形式
- 对于每一个real occurrence：
- 将h整合为真正的SSA形式
-
-
-
- 如果occurrence是冗余的，设置reload位
- 如果计算需要保存，设置save位
-
-
-
-
- 对所有标记为insert的PHI操作数进行插入
- 将操作数未定义的PHI节点删除
-
-
步骤六：代码外提
-
引入真正的临时变量t
-
转换整个程序
- t的SSA形式从h的SSA形式转换而来
-
（译者注：在介绍SSAPRE算法的过程中略去了Fred Chow讲义中的两个小例子)
- SSAPRE的实际实现
- 从词法上相同的表达式列表中依次应用SSAPRE算法
- 对于高度-1的表达式效果明显
-
子树无冗余说明树的祖先部分也无冗余
- PRE合理的扩展到loads或非直接loads
- load PRE应该从LHS的出现中获得好处
（译者注：此处略去了Fred Chow讲义中的小例子)
- 死存储删除可以看作是L-值的冗余
- 在L-值冗余中：
- 使用使L-值无意义(?)—使store有意义
- 较早的stores可以删除—导致反方向的冗余问题(?)
- 在L-值冗余中：
（译者注：此处略去了Fred Chow讲义中的小例子)
- store部分冗余删除(SPRE)
-
执行结果是不完全的死存储删除
-
基于反向CFG
-
需要静态单使用形式(Static Single Use ,SSU)
- 在分支上翻转PHI节点
- 目前通过模式匹配在SSA实现
-
（译者注：此处略去了Fred Chow讲义中的小例子)
- 寄存器提升(寄存器变量识别)
- 通过提升变量到伪寄存器(TNs in CG)来识别寄存器分配后备。即无数量限制的寄存器分配
- 对于无别名的本地变量无意义(不需要取地址)，本地的RVI(寄存器变量识别)只需要在符号表上工作。
- 对于其他类型变量，问题转化为对load和store做优化
- 寄存器提升就是：对load做PRE，再对store做PRE，先做Load PRE，将为Store PRE创造更多机会。
- 高效的寄存器提升还需要投机PRE(?)，这种PRE适用于循环内的分支。
（译者注：此处略去了Fred Chow讲义中的小例子)
-
基于全局值编号的冗余
-
PRE仅仅识别词法上独立表达式之间的冗余
-
能从非语法独立表达式中提取冗余
-
全局值编号能识别计算相同值的非独立表达式
-
Open64的GVN算法基于Taylor Simpson的论文
-
GVN之后，在相同值编号的表达式之间删除冗余
-
-
基于值编号的完全冗余删除(VNFRE)
-
PRE中设计的表达式不计算相同俄值，PHI在流图汇合点将不同的值合并
-
在计算相同值的表达式之间尽可能存在完全冗余
-
VNFRE消除具有相同GVN的表达式之间的完全冗余
- 将SSAPRE算法特殊化就能用于完全冗余
-
-
强度削弱
-
归约表达式—归约变量的线性函数(?)
-
强度削弱使用归约变量的递增代替归约表达式的计算
-
反向循环规范化(?)—定义：归约表达式提升为归约变量过程中可能会出错
- 处理方法：
-
- 先将PRE应用于归约表达式上，不管是否出错。
- PRE之后，通过更新存储归约表达式值的临时变量来修复
-
- 线性函数删除测试
- 在最终测试(?)中，使用强度削弱归约表达式代替归约变量的使用
- 目的：使原规约变量废弃
- 归约表达式是归约变量的线性函数
- 在SSAPRE规约表达式过程中进行：
- LFTR中的实例机会将使用SSA图中的COMP_OCCUR表示
- 当归约表达式在比较点可用时，也许能删除
- 根据将归约表达式转换成归约变量函数形式的特点来调整比较的r.h.s(?)
- Main-OPT阶段的累计优化效果
- 结合了以下优化效果：PRE、强度削弱、线性函数测试删除
- Main-OPT阶段结果：
-
- 降低位域代码(opt_revise_ssa.cxx)
- 表达式PRE(opt_etable.cxx)
-
-
- 强度削弱(opt_estr.cxx)
-
-
-
- 代码提升(opt_ehoist.cxx)
- 线性函数测试删除(opt_lftr2.cxx)
-
-
- 基于值编号的完全冗余删除(opt_vn.cxx)
- 死代码删除(opt_dce.cxx)
- 寄存器提升：
- 位域的死代码删除(opt_bdce.cxx)
-
-
- 本地寄存器变量识别(opt_sym.cxx)
-
-
-
- Load PRE (opt_ltable.cxx)–活跃区间收缩
- Store PRE (opt_stable.cxx)
-
-
- 获得WHIRL(opt_htable_emit.cxx)
- 完全冗余首先开始于在支配边界计算/转换为部分冗余(?)
整个Open64课程系列的文章包括以下，请阅读中指正
Pingback: Open64课程-结语 « 编译点滴
Pingback: 编译点滴 » Open64课程-循环嵌套优化(LNO)
Pingback: 《编译点滴》半年记 « 编译点滴