Open64 课程–全局标量优化(WOPT II)

open64, 编译技术, 编译理论实践和应用 Add comments

十二 132009

此文是Fred Chow在德拉华大学所讲open64课程讲义的翻译，转载请注明出处 http://www.lingcc.com
Fred Chow 原版讲义见最后一页

全局标量优化II-Main-OPT

三种和依赖有关的优化策略(Re-cap?)
- 删除无用计算—死存储删除
- 删除冗余计算—通用子表达式、循环无关代码移动、部分冗余删除
- 计算排序—循环转换、指令调度
- 本节将会讨论前两种
部分冗余删除
- 什么是部分冗余—执行某些路径时的冗余计算
- 方法：在非冗余路径上插入的计算导致的完全的冗余(相对于部分冗余)
- 这样，完全的冗余就会被删除
- 部分冗余删除比循环无关代码外提要好

部分冗余删除算法
- 懒代码外提是最好的PRE算法

1. 1. 最理想计算方式—没有其他的代码能使编译生成的二进制隐形更快–更何况在执行过程中的路径跳转
  2. 活跃区间最优化—没有其他的最优化计算代码能获得临时变量更小的活跃区间
  3. 另外，不需要双向的数据流(?)

- SSAPRE是能应用在 SSA图上的PRE算法
  - 稀疏变量version的懒代码外提(?)
  - 理解算法需要更多的直觉
SSAPRE的动机
- 完全冗余首先开始于在支配边界计算/转换为部分冗余(?)
- 使用SSA解决冗余问题
  - 使用临时变量h对问题建模来为表达式构建SSA
    - h的定义：计算表达式并保存结果
    - h的使用：重新装载较早时保存的结果
  - 相同的SSA version表示相同的计算结果
  - 仅需要在phi节点的入边插入
  - PRE数据流分析在SSA图上进行
- SSAPRE算法
1. 1. SSA构建
1. 1. 1. 插入PHI
    2. 重命名
  2. 数据流分析
1. 1. 1. DownSafety
    2. WillBeAvail
  2. 转换程序
    1. 最终化SSA
    2. 代码外提
- 第一步：插入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节点
  - 使用两个沿使用-定义边的向前传播(?)
  - 第一部分：为实现计算最优化
1. 1. 1. can_be_avail给出最优化计算的可能插入点
    2. 将所有的PHI初始化为can_be_avail
    3. 将所有非downsafe且有至少一个操作数为步骤二中重命名的操作数的PHI节点标记为not-can_be_avail(边界条件)
    4. 将not-can_be_avail属性沿定义-使用边向上传播给非downsafe节点
- - 第二部分：实现活跃区间最优化
1. 1. 1. 找到最新的插入点
    2. 对于所有can_be_avail的PHI节点：later表示次要的，not-later表示最新的插入点
    3. 主要想法：若PHI操作数由真实计算定义，插入就不能是次要的，否则会引入冗余(?)
    4. 将所有任一操作数由真实计算定义且标记为not-later的PHI节点标记为can_be_avail（边界条件)
    5. 将此not-later属性沿定义-使用边向前传播
- - 插入标准：
    - WillBeAvail = can_be_avail 和not-later的交集
    - 在willBeAvail的PHI节点处，满足以下两种情况之一时，插入PHI操作数
      - 操作数步骤二中插入的
      - has_real_use为假且此值由非WillBeAvail的PHI节点定义
- 步骤五：最终化
  - 将h整合为真正的SSA形式
    - 对于每一个real occurrence：
1. 1. 1. 1. 如果occurrence是冗余的，设置reload位
      2. 如果计算需要保存，设置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可以删除—导致反方向的冗余问题(?)
（译者注：此处略去了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算法特殊化就能用于完全冗余
- 强度削弱
  - 归约表达式—归约变量的线性函数(?)
  - 强度削弱使用归约变量的递增代替归约表达式的计算
  - 反向循环规范化(?)—定义：归约表达式提升为归约变量过程中可能会出错
  - 处理方法：
  - 1. 先将PRE应用于归约表达式上，不管是否出错。
    2. PRE之后，通过更新存储归约表达式值的临时变量来修复
- 线性函数删除测试
  - 在最终测试(?)中，使用强度削弱归约表达式代替归约变量的使用
  - 目的：使原规约变量废弃
  - 归约表达式是归约变量的线性函数
  - 在SSAPRE规约表达式过程中进行：
    - LFTR中的实例机会将使用SSA图中的COMP_OCCUR表示
    - 当归约表达式在比较点可用时，也许能删除
    - 根据将归约表达式转换成归约变量函数形式的特点来调整比较的r.h.s(?)
  - Main-OPT阶段的累计优化效果
    - 结合了以下优化效果：PRE、强度削弱、线性函数测试删除
- Main-OPT阶段结果：
1. 1. 降低位域代码(opt_revise_ssa.cxx)
  2. 表达式PRE(opt_etable.cxx)
- - - 强度削弱(opt_estr.cxx)
- - - 代码提升(opt_ehoist.cxx)
    - 线性函数测试删除(opt_lftr2.cxx)
1. 1. 基于值编号的完全冗余删除(opt_vn.cxx)
  2. 死代码删除(opt_dce.cxx)
  3. 寄存器提升：
  4. 位域的死代码删除(opt_bdce.cxx)
- - - 本地寄存器变量识别(opt_sym.cxx)
- - - Load PRE (opt_ltable.cxx)–活跃区间收缩
    - Store PRE (opt_stable.cxx)
1. 1. 获得WHIRL(opt_htable_emit.cxx)