Open64课程-简介，概述和中间表示

转载自：http://www.lingcc.com/2009/11/18/10000/

这是Fred chow 在德拉华大学所讲的open64课程讲稿的翻译。若需要原文ppt，请发邮件向我索取。
转载请注明出处: http://lingcc.com

Fred Chow 原版幻灯片见最后一页
1，历史：
1980-83 斯坦福大学RISC编译器研究
1987 MIPS Ucode编译器(R2000) -O2下的全局优化
1991 MIPS UCode编译器(R4000) -O3下的循环优化

另外：
1989 Cydrome Cydra5编译器 软流水优化
1994  SGI Ragnarok编译器(R8000) 浮点性能优化(Floating-pt performance?）

1997年SGI将上面两个分支连同斯坦福SUIF的工作，Rice的IPA整合在一起发布MIPSpro编译器(R10000)
2000年Pro64/Open64编译器(安腾)诞生

2，Open64大事记：

1994：MIPS R10000编译器开发工作开始
1996 ：SGI MIPSpro 编译器合并
1998：开始移植后端到安腾，并将前段变更为gcc/g++
2000: Pro64编译器通过GPL协议开源
2001：SGI放弃支持，德拉华大学将编译器重新命名为open64
2001-2004： 计算所和Intel开始合作开展针对安腾的ORC
2003：PathScale开始支持x86后端的移植工作
2004：四月PathScale X86编译器合并

3，Open64的重要特性
在当今的产品级编译器中是最先进的设计
架构设计的重点放在优化实现上
1996年作为产品级编译器，2000年开源
兼容gcc/g++并能和其交互工作,包括源码结构，命令行，ABI和装载
易扩展和增强
易移植到新处理器
被广泛使用在当今的很多优化研究中
适合小团队的开发环境

4，PathScale编译器的重要贡献
移植到X86/X86-64
从2004年开始一直是x86 64位中性能最好的
在GNU和Open64之间建立了桥梁，以便方便的跟随GNU的发布
拥有OpenMP运行时库的专利权
质量评价和编译机制

5，Open64总体设计
全范围优化兼容的编译器架构
重要组成—-一个通用的中间表示WHIRL：
a,支持多前端的独立后端
b,一种中间表示，多层表示
c,编译处理过程即为中间表示不断降低的过程。
给予优化范围的特定成分：
a,LNO:Loop-oriented,基于数据依赖的优化
b,WOPT:基于SSA的全局范围优化
c,IPA:inter-procedural,过程间优化，需要对整个程序的分析
d,CG:代码生成，依赖于目标机
在不同阶段之间无重复工作：
a,所有阶段都可调用WHIRL简化函数
b,共享的分析结果
c,彼此调用来完成工作

6，编译器中中间表示(IR)的角色
支持多前端
支持多处理器
进行优化变换的中介
各个阶段间的通用接口
促进编译器设计中的模块化
减少多余功能
现代编译器中的关键设施

7，IR的语法层次：
从高到低，高层次靠近源程序，低此次接近机器指令
在较高层次中：
a,较多样的组成
b,较短的代码序列
c,较多的程序信息表示
d,分层次的结构
e,不能进行很多优化
在较低层次中:
a,较少的程序信息
b,较少的结构种类
c,较长的代码序列
d,较平坦的结构
e,所有的优化都能进行

8，Open64的WHIRL IR
WHIRL由SGI的Open64小组开发：
a,一种IR，多层表示
b,编译过程即不断降低表示层次的过程
c,每个优化都有其最适合做的表示层
d,共享分析结果
e,阶段之间没有冗余操作

9.编译过程：
源码->前段(FE)->高层优化(VHO)->过程间优化(IPA)->循环嵌套优化(LNO)->全局优化(WOPT)->代码生成(CG)->汇编码输出
对应中间表示：
源码->非常高层WHIRL->高层WHIRL->中间层次WHIRL->较低层WHIRL->目标机指令->汇编码输出

10，优化设计的总原则
在能榨取转换机会的最高层次做优化，即在尽可能高层次做优化
a,有更多能协助分析的源程序信息
b,需要操作的代码序列较短
c,对于相同的计算，变更最少
将使得：
a,实现代价较小
b,更快更高效的优化
c,更稳定(便于测试和debug)

11,阶段次序设计原则
较低层处理的需求：在较低层次暴露的优化机会需要在较晚时做
能暴露优化机会的较早的阶段：内联(Inline),常数传播，循环合并
能为较后阶段计算有利信息的阶段：别名和指针冲突消除，使用-定义关系，数据依赖
能规范代码的较早阶段：相比其他阶段对代码的变动较小的，不能提高程序性能de，依赖较后阶段清理操作的
会被使用多次的小代价优化
将破坏源程序信息的优化尽可能的放在后面

12，WHIRL的设计
可执行代码的WHIRL树节点：
a,WHIRL节点在common/com/wn_core.h文件中被定义
b.每个函数体被一个大树表示
用于定义的WHIRL符号表：
a,不同的表用于表示不同的声明结构
b,参见common/com/symtab*.h文件
最小的WHIRL节点是24字节
使用了域压缩来节省空间
二进制读写—WHIRL文件是ELF文件格式的
不同的阶段有唯一的WHIRL文件后缀:
a,前端：.B
b,IPA/内联器: .I
c,LNO: .N
d.WOPT: .O
ASCII 翻译器

13，重要的WHIRL概念
operator:操作的名称
desc:操作数的机器类型(标量)
rtype:结果数的机器类型(标量)
opcode:三元组(operator,rtype,desc）
symbol table index:一个源码中符号对应的唯一标识符
high level type:和源码声明相同的类型结构–对实现ANSI别名规则很重要(?)
field-id:在一个结构体或union中唯一的标识符，较新的为X86 MMX/SSE定义的128-位SIMD机器类型

14,优化中的WHIRL概念
语句节点是序列点(？ Statement nodes are sequence points)
a,仅在语句边界可能有副作用
b,有副作用的语句有：Stores(存储),Calls(调用),asms（汇编？)
表达式节点不是序列点
表达式执行无副作用的计算–允许激进的表达式转换
源码位置信息(为了调试需要)仅应用于语句节点

15.WHIRL 映射(?)
注释型WHIRL节点有附加信息
解决WHIRL节点大小固定问题
对临时信息很有用
WHIRL节点归类
Map_id存储在每个WHIRL节点中–同一类中map_id唯一
信息存储在map 表中，并以map_id作为索引

16，更高层WHIRL(Very High WHIRL)
维持源码中的抽象表示
能在损失较少语义的情况下转回C/F90
最初被使用于FORTRAN 90，随后扩展到C/C++中
尽在VH WHIRL中允许的结构：逗号操作符，嵌套函数调用，C选择符(?和:),F90中的triplet,arrayexp,arrsection,where
内联器能够工作在此层

17，高层WHIRL
支持循环级优化的结构
固定的控制流(虽然还不精确)
关键结构:ARRAY(数组,数据依赖分析和向量化)，DO循环，IF语句，FORTRAN I/O语句
IPA，PREOPT和LNO工作在此层
能转换回源语言—允许用户看到内联和LNO的效果

18，中间层WHIRL
一对一映射到RISC指令
通过jumps(跳转)实现精确的控制流
地址计算暴露出来(因为无ARRAY了？)
位域访问暴露
复数被扩展为浮点数操作
WOPT在此层工作—统一的表示提升了优化的机会

19，低层WHIRL
为了便于在CG转换为机器指令而出现的最后的WHIRL形式
一些内在intrinsics(?)使用calls(调用)代替
遵循连接协议的形式暴露(?)
数据布局结束

Open64课程-编译过程

转载自：http://www.lingcc.com/2009/11/19/10024/

此文是Fred Chow在德拉华大学所讲open64课程讲义的翻译，转载请注明出处 http://lingcc.com
若需要此讲义的原版，请email我

Fred Chow 原版讲义见最后一页

—————————————————

1.优化控制哲学

• 低优化级别–更短优化时间，更安全优化，更精确的计算，较缓慢的代码产生速度
• 高优化级别–较长优化时间，更激进优化，精确性让步于高性能，更快的代码生成
• 通过大量选项较好的控制优化–PathOpt2(?)提供了很多帮助

2,优化标志与涉及的阶段

• -O0(-g下默认)—前端和代码生成器，关闭所有优化
• -O1–前端和代码生成器，仅作本地优化
• -O2(默认)—增加WOPT和其余的CG优化
• -O3 —增加LNO
• -ipa(能在任何优化级别进行)–增加IPA
• -Ofast—和-O3 -ipa -OPT:Ofast -fno-math-errno -ffast-math效果相同
• -OPT:Ofast是-OPT:ro=2:Olime=0:div_split=ON:alias=typed

3,选项组

• 选项通过编译器不同阶段或者通过特征分组
• 通用语法–   -GROUPNAME:opt[=val]{:opt=[val]}
• 一些GNU类型的选项直接映射过来 -march -ffast-math -ffloat-store -fno-inline
• 组名称： -LIST： 用户列出(?)    -OPT: 优化   -TARG:目标机器 -TENV:目标环境  -INLINE后端内联  -IPA:过程间分析  -LANG: 语言特征 -CG:代码生成  -WOPT:全局范围优化 -LNO:循环嵌套优化

4,编译器驱动器的角色

• 在open64/driver中实现
• 处理所有的命令行中的选项
• 调用所有的编译阶段–预处理，前端，内联器，后端(be,lno,wopt,cg),汇编器，连接器
• 保持和GNU选项的兼容

5,编译器驱动器

• open64/driver/OPTIONS  具体选项表，能将一个选项对应到另一个选项
• 单个运行，多个软链接
• arg[0]字符串用于识别语言
• 查询编译相关的环境变量
• 在-march=auto时查询主机处理器类型(默认)
• 查询compiler.defaults文件来得到系统相关选项

6,C/C++前端历史

• 2000年开源时使用GNU2.95前端–直接从GNU内部语法树转换成WHIRL，在Open64中嵌入相互独立的C和C++前端
• 2004年升级到GNU3.3.1
• 206年类似于虚拟机，定义.spin文件格式—-GNU编译器不再作为Open64的一部分维护，简化升级到每个GNU发行版本的工作，C和C++前段中冗余代码消除
• 2007年3月移植GNU4.0.2前端
• 2007年10月移植GNU4.2.0前端
• 考虑了会增加的未来GNU语言(?)

7,用GNU编译器作为前端

• 使用为X86-64配置的GNU编译器
• 过去的方式：  C语言前端open64/kgccfe      C++前端open64/kg++fe       调用嵌入在GNU代码中WHIRL生成代码       c++需要将整个编译结果转换为汇编语言来结束数据转换(?)        c和c++前端中有冗余代码
• 新的方式:gspin树节点–GNU语法树建模工具：   在libspin库中功能实现，   gspin树节点可以提取到.spin文件中   识别GNU语法树中阻止gcc编译的点(?)  gspin树节点由gcc/tree.c所产生的GNU语法数生成    open64/wgen 将 gspin语法树节点(.spin文件)翻译成WHIRL节点(.B文件) wgen中操作的形式在kgccfe/kg++fe之后进行建模(?)

8,Gspin树节点

• 目的：将GNU树中的所有信息编码到.spin文件中
• 8-字节大小的gspin节点作为构建程序块的基本单元：在libspin/gspin-tree.h文件中定义  表示GNU语法树节点中的一个信息域   相邻的gspin簇表示一个GNU语法树节点   重新表示机制定义在libspin/gspin-tel.h文件
• libspin管理gspin节点的布局
• gspin节点的 I/O通过mmap()实现
• ASCII抽取琦–为防止无限递归每个节点仅被处理一次

9，gspin节点例子

GNU的PLUS树节点有14个域，gspin根节点来编码PLUS，再加上13个表示剩余域的gspin节点

tree_code = PLUS
tree-code_class = BINARY
tree_type
tree_chain = NULL
flags
arity = 13
file name
line no
operand 0
operand 1
unused
unused
unused
unused

10,FORTRAN前端

Open64课程-内联

转载自：http://www.lingcc.com/2009/11/20/10068/

Open64 课程–全局标量优化(WOPT I) part 1

转载自：http://www.lingcc.com/2009/11/25/10127/

全局标量优化(WOPT)一–Pre-OPT part 1

此文是Fred Chow在德拉华大学所讲open64课程讲义的翻译，转载请注明出处 http://lingcc.com
若需要此讲义的原版，请email我

Fred Chow 原版讲义见最后一页

1. 全局标量优化WOPT总览
   工作在函数域内
   构建控制流图
   进行别名分析
   将程序表示为SSA形式
   基于SSA的优化算法
   采用多阶段协同的方式达到最终优化效果
   优化顺序重新设计以实现性能提升最大化
   分成PreOpt和MainOpt两个阶段：PreOpt工作机制类似LNO和IPA的预优化前段(在高层WHIRL中)
   为LNO和IPA提供use-def(使用-定义)信息
   为CG提供别名信息
2. 本节要点
   SSA基础
   一些基于SSA的优化
   WOPT中的别名分析
   WOPT的SSA表示
   在WOPT中表示别名信息
   将SSA优化一般化到任何存储操作
   符号(sign-)和零扩展(zero-extension)操作优化
   预优化(Pre-optimizer)阶段结构
   SSAPRE
   其他冗余方面的优化
   主优化(Main-optimizer)阶段结构
3. 什么是SSA                http://www.lingcc.com/2011/08/13/11685/
   名字：静态单赋值形式(Static Single Assignment):整个程序中每个变量仅允许定义一次
   作用：用于程序中间表示中的内建use-def依赖信息
   Use-def:从变量的每个使用指向它的定义的一条单向边
4. 直线代码(Straight-line code)中的数据依赖
   每个被使用的变量有且仅有一个定义
   直线代码一般为单赋值
   使用到定义(Uses-to-defs）:多对一的映射
   每个定义支配所有它的使用
5. 非直线代码(Non-straight-line)中的Use-def依赖
   多个使用和多个定义之间有依赖 ：在转换成中间表示过程中代价很大，难于掌控
   使用SSA能够从繁杂的依赖中恢复直线代码的特性
6. 算符φ
   很显著的减少依赖边个数
   一个φ节点被认为是一种定义(它的所有参数被认为是使用)
   采用这种方式将多个的引用转化为一个定义
   每个定义反过来支配该节点之后的引用

   定义：当多个Use-def边要经过同一个bb时，创建一个φ节点，让所有的依赖边都经过它。

7. 用重命名方式表示use-def边

   不再需要精确的指定use-def边

8. 将程序转换成SSA
   φ仅在定义支配边界出需要(即它停止支配处)
   支配边界基于控制流图已提前计算
   两个阶段：在每个定义的支配边界插入φ(递归式地);将所有支配边界内的使用重命名为定义名字(在前序遍历支配树的过程中管理更新存储变量版本的栈

   (译者注:此处为了简便起见，略去了原作者的例子)

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

转载自：http://www.lingcc.com/2009/11/30/10168/

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

转载自：http://www.lingcc.com/2009/12/13/10273/

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

全局标量优化II-Main-OPT

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

  

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

1. 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算法特殊化就能用于完全冗余

  • 强度削弱

    • 归约表达式—归约变量的线性函数(?)

    • 强度削弱使用归约变量的递增代替归约表达式的计算

    • 反向循环规范化(?)—定义：归约表达式提升为归约变量过程中可能会出错

    • 处理方法：