十一 302009
全局标量优化(WOPT)一–Pre-OPT part 1
此文是Fred Chow在德拉华大学所讲open64课程讲义的翻译，转载请注明出处 http://www.lingcc.com
Fred Chow 原版讲义见最后一页
- 目的：在尽量不影响优化效果的前提下降低SSA表示的代价
-
- 放弃完整的带MayDefs的使用-定义链表示。
- 使用特定的version-Zero Version:标记不完整的使用-定义信息，不要将其对应到单赋值中的属性
方法:
- SSA和非SSA的version能够共存
- 易失变量仅又有zero version
- 定义：Real occurrence–在构建SSA形式之前所有在程序中的出现。 对于虚变量，real occurrences 只它的非直接变量出现的地方。
- 定义：Zero version–非真实出现在程序中但它的值是由至少一个chi节点或至少包含zero version的phi节点得到的标量version.
- 初衷：在chi节点处引入zero version.
- 使用-定义边在有zero version时是不完整的
- 对于死存储删除，一个phi或chi节点，若它的结果是zero version，则不能删除
需要两遍SSA构造：
-
- 第一遍：先在WHIRL中表示，SSA的version存储在WN的ST_IDX域中，ver_stab 是SSA的version表(VER_STAB_ENTRY).将WHILR映射到相关的出现节点(OCC_TAB_ENTRY)来保存mu和chi节点。在第一遍SSA中，对于没有real occurrence的version,若由chi定义，或由ohi定义，且操作数中有一个为zero version则定义为zero version.使用一个worklist来遍历所有phi节点指导结果不再改变。
- 第二遍：构建出HSSA，对于每个变量的zero version,仅创建一个coderep节点
(译者注:此处略去Fred Chow的例子)
- 直接应用SSA的死存储删除算法并不能识别很多死非直接存储。需要通过对虚变量的使用-定义链的分析来增强算法。
- 基于非直接变量节点定义域剧的指针，使用定义语句的r.h.s代替非直接变量；依据虚变量的使用-定义链能传播到更接近定义语句的地方(地址表达式要明显，确定无非直接存储地址间的交叉)
- 任何访存的结构都能表示为SSA
- 高层次表示:数组集合，复合数据结构(结构体，类，C++模板)
- 低层次表示：位域内的
- 能够在它们上面应用基于SSA的优化算法
- 大的结构体复制往往降级成循环实现，增加优化难度
- 在结构体降级前应用SSA优化：死结构体拷贝的删除，结构体的复写传播
- 域访问时考虑别名
(译者注:此处略去Fred Chow的例子)
- 位域能够当成独立域实施更激进的优化
- SSA优化在域降级抽取或隐藏前应用：由于较小的覆盖区使关联的别名较少、和标量的表示相同
- 降级到域抽取或隐藏之后：得到word范围的寄存器访问，减少存储访问、在标记操作时实现冗余删除
- 动机：
-
- 符号/零 扩展操作在整数大小比操作大小更小的时候
- 在用户需要的时候也能进行：强制类型转换、截断
- 对于安腾很重要：仅提供无符号loads，在指令系统结构中最常见的都是64位操作(绝大部分程序都是32位的)
- 定义
-
- sext n-符号位为n-1,所有>=n的位都合符号位相同
- zext n-n位无符号整数，所有>=n的位都为0
- 是SSA死代码删除算法的扩展(同时实现死代码删除)
- 对每个变量使用一个标记活跃的位(而非一个单独的flag)
- 对每个表达式树节点使用一个标记活跃的位
-
- 依据使用-定义边，计算边和控制依赖向后传播单个bit的活跃信息
- 删除操作
两个阶段：
(在be/opt/opt_bdce.cxx中实现)
- 在表达式树中自上而下传播(从表达式结果到它的操作数)
- 基于语句的语义，仅影响结果的操作数的位被标记为活跃
- 在叶子节点，依据使用-定义边找到SSA变量的定义语句
- 在没有新的活跃变量发现时传播结束
-
- 赋值语句:如果该SSA变量没有活跃标记就被删除
- 其他语句:如果没被标记为必须，则删除
- 零/符号扩展操作：在以下两种情况下被删除–死bit标记(?)、冗余扩展(?)
遍历整个程序：
- 与常数的位与操作：和0的位与操作标记为dead
- 与常数的位或操作：和1的位或操作被标记为dead
- 使用EXTRACT_BITS和COMPOSE_BITS(?)
- “sext n（opnd)”和“zext n (opnd)”:操作数n之后的高位标记为dead
- 右移：被右移出的右bit标记为dead
- 左移：被左移出的左bit标记为dead
- 还有其他情况
- 给定”sext n (操作数)”和“zext n (操作数)”下列情况将符号/凌扩展判定为冗余
- 操作数是<=n的小整数(通过较高位已知值)
- 操作数是整型常数
- 操作数是针对存储地址大小<=n的load
- 操作数是另外一个长度<=n的符号/零扩展操作
- 操作数是SSA变量：能否递归地通过使用-定义关系找到它的定义，分析它的r.h.s
- 在连接多个阶段的过程中起作用
- 循环常规化：为每个循环插入一个人工索引变量，从0还是，间隔为1，递增
- 索引变量标准化：基于SSA图检测每个循环中的所有索引变量；在所用索引变量中，挑选一个主索引变量IV，对每个其他IV，在循环开始阶段插入使用主IV表示的赋值语句
- 复写传播：所有次要IV的使用都使用主IV的使用代替
- 死存储删除:删除所有次要IV的出现
- 删除无用计算–死存储删除
- 删除冗余计算–通用子表达式、循环不变代码移动、部分冗余删除
- 计算重排序：循环转换、指令调度
SSA为1和2提供了解决方法。1前面已经讲过，2属于Main-OPT阶段
-
-
- Goto转换
- 循环常规化
- 别名分析(流无关和流相关)
- 尾递归删除(?)
- 死存储删除
- 索引变量标准化
- 复写传播
- 死代码删除
- 为LNO和IPA计算定义-使用链
- 将别名信息传送到CG
-
Pre-optimizer
-
-
- 基于SSAPRE机制的部分冗余删除:全局通用表达式、循环无关代码移动、强度削弱、线性函数测试代替
- 基于值编号的完全冗余删除
- 索引变量删除
- 寄存器推销
- 位域内的死存储删除
-
Main optimizer
- Goto 转换(opt_goto.cxx)
- 循环标准化(opt_loop.cxx:Normalize_loop())
- 创建优化符号表(opt_sym.cxx)
- 别名分类(opt_alias_class.cxx)
- 创建CFG(opt_cfg.cxx)
- 控制流分析(opt_cfg.cxx):支配节点、支配边界、后继支配、后继支配边界、不能到达代码、if语句转换、循环结构表示
- 尾递归删除(opt_tail.cxx)
- 流无关别名分析(opt_alias_analysis.cxx:Compute_FFA())
- 创建基于WHIRL的SSA(opt_ssa.cxx)
- 流敏感别名分析(opt_alias_analysis.cxx:Compute_FSA())
- 死存储删除(opt_dse.cxx)
- 查找zero version（opt_dse.cxx)
- 创建HSSA(stmtrep,coderep)(opt_htable.cxx)
- 索引变量标准化(opt_ivr.cxx)
- 复写传播(opt_prop.cxx)
- 将非直接变量展开成直接变量(opt_revise_ssa.cxx)
- 死代码删除(opt_dce.cxx)
- 迭代，直到不再有变化：
- 控制流转换(opt_cfg_trans.cxx）
- 更新SSA(opt_rename.cxx)
- 复写传播(opt_prop.cxx)
- 展开非直接变量为直接变量(opt_revise_ssa.cxx)
- 死代码删除(opt_dce.cxx)
- 如果有IPA或LNO
- 获得WHIRL(opt_emit.cxx)
- 创建定义-使用信息(opt_du.cxx)
整个Open64课程系列的文章包括以下，请阅读中指正
[...] Open64 课程–全局标量优化(WOPT I) part II [...]
[...] Open64 课程–全局标量优化(WOPT I) part II [...]
[...] Open64 课程–全局标量优化(WOPT I) part II « 编译点滴 Pingback | 2009/12/29 [...]
[...] Open64 课程–全局标量优化(WOPT I) part II « 编译点滴 on Open64课程-循环嵌套优化(LNO)Open64 课程–全局标量优化(WOPT I) part [...]