Open64课程—代码生成(CG)

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

代码生成

• 目标机信息表(targ_info)

该机制来自Cydrome，并进行了增强。将目标机指令集，ABI和调度信息参数化。通过表生成机制来编译和链接，生成的表是用于CG阶段的C++文件(?).这种机制能将优化算法和体系结构细节分开，而且再移植到新结构上时能最小化编译器的改动，因为机器相关的内容存放在机器相关的文件夹内。支持ISA子集。不同处理器的调度信息实现编译成独立的.so文件，并使用编译选项控制dlopen()使用哪个.so文件

• 代码生成中间表示(CGIR)

这种中间表示的每个操作(op)对应一条机器指令，通过targ_info来格式化指令。在一个目标机op中操作数和结果都存放在TN中(或者寄存器符号中).TN有符号、直接量和寄存器三种类型。TN的类型都是依据指令格式制定的。每个操作都使用两个操作数，并写出一个结果(和RISC相似),某些特殊的指令也能写两个结果(如 mul)

• 代码生成阶段结构

• CG展开

这部分的作用是将WHIRL展开成CGIR中的操作(whirl2ops.cxx,cgexp.cxx,x8664/exp*.cxx).TN的创建是用来存储中间结果。并且采用单赋值TN的形式来最小化依赖。CG阶段接下来的工作都在CGIR上做。每个机器op包含有指向WHIRL的指针，用来做别名分析和依赖信息查询，整个CG展开部分是机器相关的。对于X86，在LRA之前做展开，这样能通过创建拷贝指令，增强两个操作数之间的指令错左。如r=s+t —> r=s,r+=t。通过这种方式能将LRA中的寄存器合并，避免不必要的拷贝。

• 扩展的基本块优化

即在扩展的基本块内做窥孔优化(ebo.cxx).什么是扩展基本块？即由串联的基本块构成，单个入口，可以有多个出口边。所做的优化包括：向前传播，通用子表达式删除，常数折叠，死代码删除（冗余load和store删除)，机器相关优化(如x86中的load-执行指令优化，add使用LEA指令)

• 扩展块优化算法

首先，创建TNINFO来跟踪TN值，每个TN都有独立的TNINFO，能够跟踪TN值可用，识别定义TN值操作等，使用较早的TN替代操作数中被移除的TN。其次创建Op哈希表，将相似的op哈希到同一个表段中，允许快速识别”匹配”op,若两个op访问同一块内存则视为它们存储匹配，这样能删除多余的存储访问。如果两个op完成相同的功能，则视为ALU匹配，这样能做通用子表达式删除。该EBO优化在CG中被调用了多次。

• 控制流优化

控制流图在CG展开之后创建，所做的优化有以下几个(cflow.cxx):分支删除，将常条件分支转换为goto指令，将分支到分支，分支到goto，分支到return的指令折叠；热基本块定位，使用反馈信息评估或者用户提示的方式找到热基本块，重新排列基本块，使得流图尽量直线少跳转；增长基本块链(?);通过复制基本块来减少分支(尾部冗余)，不可到达代码删除。

• 内循环优化

跨迭代循环优化(?)(cio_rwtrans.cxx)、最内层循环展开优化(cg_loop.cxx)、预取修剪优化

• 跨迭代循环优化

删除数组元素跨迭代边界带来的冗余，构建循环体中指令访存的依赖关系，引入变量omega表示循环迭代间依赖到距离。

如果变量的活跃区间交叉，则插入寄存器移动，在循环入口前初始化临时变量。
从写内存中读入冗余

使用较小的omega开始跟踪冗余指导寄存器压力达到某个阈值。
写写冗余

需要在循环出口插入剩余store

• 跨迭代CSE(?)

建立在跨迭代读冗余删除操作和减少寄存器压力操作的基础上

• 指令调度

在基本块范围内进行(hb_sched,cxx),基于WOPT的别名信息和LNO的依赖信息来创建依赖图(cg_dep_graph.cxx).指令调度和寄存器分配相互关联，好的寄存器调度可能增加寄存器压力。CG阶段的指令调度执行两次：第一遍用来评估良好的指令调度前提下的寄存器需求情况，之后全局的寄存器分配器将许可每个基本块所需要的寄存器数，紧接着进行在寄存器分配后进行第二遍调度。寄存器分配之后，就能将依赖建立在真实的寄存器上，使用列表调度算法(list scheduling algorithm),这种策略在向前和向后两个方向上都能进行。

• 寄存器分配的作用

通过最佳化使用可用的物理寄存器提升执行性能，在需要的时候生成溢出代码。需要遵守ABI和ISA中关于寄存器的使用：参数寄存器，函数返回寄存器，被调用函数保存寄存器(在过程进入或退出的时候保存或弹出值)、调用函数寄存器(在调用时保存或弹出值)、在某些特殊指令中所使用的特殊寄存器。

• 寄存器分配

依据targ_info的寄存器文件参数执行，应用在寄存器TN(即符号寄存器)上，活跃分析能识别全局的TN(GTN),这些GTN的活跃区间将跨基本块(gra_live.cxx)，全局寄存器分配(GRA)采用下面的方式应用在GTN上(gra_mon/*.cxx):基本块粒度的分配，使用基于优先级的图着色算法，允许指定数量的寄存器给LRA。本地寄存器分配(LRA)采用下面的方式使用GRA允许数量的寄存器在每个基本块之间分配(lra.cxx):指令级的粒度，仅在指令间向后遍历一次。若无法使用GRA，则通过插入溢出代码将GTN转换为本地的方式来本地化。

• 活跃分析

使用的是传统的数据流分析，使用基于每个BB中TN数的位向量,通过传递以下信息来设置本地信息：live_use—本地向上展开使用的TN；defreach_gen—BB中定义的TN。使用数据流来计算：defreach_in—-能够到达bb顶端的定义， defreach_out–能够到达bb下端的定义 live_in—-在bb顶端使用向上展开 live_out—在BB下端使用向上展开。 在BB i中，全局TN的集合由 defreach_in i and live_in i or defreach_out i and live_out i 给出

• 通过基于优先级寄存器分配的GRA

使用粗粒度的干扰方式，分配是以BB为单位进行的，每个BB中，每个寄存器赋值为1个TN，活跃区间也由BB构成，若两个TN的活跃区间重叠，则视为干扰。这种GRA算法是域驱动的，即在BB之间管理寄存器资源，当有可用寄存器时，就将活跃区间分割用来匹配域。这种算法无回溯。

• 寄存器分配的数据结构

LV即活跃区间，LU即一个活跃区间(活跃单元)内的单元（BB).因此一个LV指向它的LU列表。为了能测试干扰，我们使用BB(基于BB号)的位容器,称之为BBmem，如果两个LV的BBmem交叉则视为它们有串扰。 所有的LU默认信息为：0 use，0 def，0 call，无引用等，此时不需要LU节点的分配。干涉图即一个所有LV之间两两有干扰的指针链表

• 代价/获利建模

通过比较是否分配时指令数的不同。若不分配，每个TN本地向上扩展的BB中，一个load指令，在每个有TN定义的BB中，一个store指令；如果分配，可能需要重新在活跃区间入口载入,也可能从活跃区间出口处溢出。于是每个BB的获利=避免的load指令数/避免的store数*频率，每个BB的代价=需要的溢出数/重载入数*频率。每个LV的优先级=每个bb中TN的获利和代价之差的总和/BB总数。

• 寄存器代价建模

调用者保存的寄存器–需要在调用中保存/重存；被调用者保存的寄存器—需要在PU首次使用情况下进入/退出时保存/重存；参数寄存器–为用于传参的TN优先分配(负代价).函数返回寄存器–优先分配给存函数返回值的TN

• 寄存器分配算法

定义：无约束LV：干扰图中的邻居数小于能赋值的寄存器数的LV。具体算法如下:首先计算每个LV的禁止赋值寄存器(forbidden)集合，将LV分成无约束和约束两类。对于每个寄存器类，重复下面的步骤知道所以非溢出LV都被分配：1，计算所有新LV的优先级，若为负则溢出；2，将未分配的LV设置为最高优先级LV-best；3，对于每个在LV-best的禁止赋值寄存器集合(~forbidden(LV-best))中的寄存器r，计算其分配代价Regcost(LV-best,r);4,将最小Regcost定位r-best。5，若LV-best的优先级(Priority(LV-best))小于Regcost(LV-best,r-best),溢出LV-best,否则，将r-best赋值给LV-best；在干扰LV-best的LV列表中，更新禁止赋值寄存器集，分离出无法着色的LV，溢出无法分离的LV，最后将寄存器分配给无约束的LV。

• 分割的目的

一是为了增强着色性，二是为了改变活跃范围的大小。对于前者，当forbidden(LV)=寄存器集合数时分割，若当出现TN处，它的所有BB中无可用寄存器时，将真个LV溢出。对于后者，自动将非相邻的块和lV分开，当被调用保存寄存器调出时分割，被分割出的域若0出现，则溢出.

• 分割活跃范围

尽最大可能将LV-new分割出LV-orig从而使forbidden(LV-new)不至于满(?).保留下来的LV-orig或者能分配或者不能.依照控制流图(不计回边)的拓扑序管理LU表.
具体算法:
1. Go through LU list to pick LU such that TN appears and register is available
2. For each LU in LV-new:
For each BB-succ of LU
If BB-succ is member of LV-orig, and adding BB-succ to LV-new does
not cause forbidden(LV-new) to become full,
Move BB-succ from LV-orig to LV-new;
Update forbidden(LV-new) and LV-new’s LU list

• 本地寄存器分配

该过程是在一个向后遍历BB中的指令过程中将寄存器分配给本地TN的,BB的每一类可用寄存器集合在这个过程中飞速的更新.在一个向后过程中,对于每个指令,先处理结果TN再处理操作数TN;每个本地TN最先考虑的是在该TN的活跃范围内的最后一次使用;采用时间片轮转的方式给TN赋寄存器;对于出现在结果中的本地TN,通过将该寄存器添加回可用集合的方式来释放;相同的寄存器可以分配给同个指令中的结果和操作数,这种情况下,寄存器移动的指令可以直接删除.

• 应对X86寄存器的古怪特性

需要在LRA开始阶段为每个BB增加带额外拷贝的额外TN.为遵守两个操作数格式:
TN100=TN101+TN102
变为
TN100 = TN101
TN100 = TN100 +TN102
为遵守8位寄存器子类:
TN100 = sete ….
变为
TN101 = sete …
TN100 = TN101
TN101是8位寄存器子类,TN100没有这种约束。

• 应对X86的特殊寄存器

一些指令需要特定的寄存器，需要为rax，rcx和rdx创建单寄存器子类。引入涉及严格遵循寄存器子类的TN拷贝
如
TN100 TN101 = mul32 TN200 TN201
变为
eax = TN200
eax edx = mul32 eax TN201
TN100 = eax
TN101 = edx

• LRA可能耗尽寄存器

因为每个TN必须分配一个寄存器，当无可用的寄存器分配给TN时，就调用Fix_LRA_Blues()来释放额外的寄存器，或者尝试重新LRA这个BB。对于函数Fix_LRA_Blues()，k可以使用不同的策略。主要有以下三种策略：溢出一个已经通过GRA分配的寄存器；重新做指令调度来减小寄存器压力；溢出一个先前分配且超过其活跃范围的寄存器。

• 应对X87中的寄存器栈

x87仅在-m32下支持，x87栈寄存器视为普通寄存器文件建模，在最后的指令调度阶段，将X87寄存器转换为类似栈的操作(x8664/cg_convert_x87.cxx);在BB之间转换时，栈都被维持在相同的状态。需要插入fxch指令。如果寄存器栈不再活跃，就使用X87指令中的弹出版本(pop version)

• 全局代码外提

该过程在本地寄存器分配和最终指令调度阶段之间进行(gcm.cxx)；计算每个基本块中的关键路径；通过移动指令来调整基本块的方式来寻找缩短关键路径的机会，如将开始指令移动到基本块的前驱，将结束指令移动到基本块的后继。

• 应对汇编代码潜逃(asm())

在WHIRL中，使用ASM_STMT表示一个汇编语句，ASM_STMT的输入输出维护着WHIRL的接口。在CG中，展开成汇编伪操作(whirl2ops.cxx).输入和输出的接口也转换为了TN。接下来TN通过GRA/LRA赋予真实的寄存器。在代码输出阶段，使用被赋予的寄存器替换汇编代码串中的操作数(cgemit.cxx,x8664/cgtarget.cxx)

整个Open64课程系列的文章包括以下，请阅读中指正

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

Open64课程- 编译过程

Open64课程-内联

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

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

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

open64课程–过程间分析优化(IPA)

Open64课程—代码生成(CG)

相关文章:

• Open64课程-编译过程
• Open64课程–OpenMp和自动并行化
• Open64课程-内联
• Open64课程-结语
• Open64 课程–全局标量优化(WOPT II)
• Open64 课程–全局标量优化(WOPT I) part II
• open64课程–过程间分析优化(IPA)
• Open64课程–反馈指导优化(FDO)
• Open64课程-简介，概述和中间表示
• Open64课程-循环嵌套优化(LNO)