编译器中激进蝴蝶优化方法的研究与实现*

朱广林,吕 方,赖庆宽,陈华英,何先波

(1.中国科学院计算技术研究所计算机体系结构国家重点实验室，北京 100190;2.西华师范大学计算机学院，四川 南充 637009;3.中国民用航空飞行学院，四川 广汉 618307)

1 引言

冗余代码是程序中较为常见的问题，通过动态、静态分析以及插桩方法都能定位到一些冗余代码，可以辅助编译器进行冗余代码删除操作。但是，受限于保守的分析手段，编译器中仍有一部分冗余代码无法被发现，以至于无法对其优化。而程序中的冗余代码会致使布局优化难以实施，甚至会导致严重的寄存器溢出等问题。

编译优化是非常成熟的领域，国内清华大学、中国科学院计算技术研究所以及国防科技大学和江南计算所等都有相关的研究和积累。例如，清华大学Zhou等人[1]将最小割法应用于控制流图形成的流网络中，提出了最小割法的静态单赋值部分冗余消除MC-SSAPRE(Min-Cut Static Single Assignment Partial Redundancy Elimination)算法，以获得部分冗余消除的最大收益；周虎成[2]研究总结了现有的冗余消除优化研究中存在的局限性，提出了有效的优化方法，降低了数据流分析的复杂度。计算技术研究所Lü等人[3]提出一种空闲寄存器利用的代码优化方法，能够有效减少寄存器溢出。但是，针对冗余代码的优化研究仍然有继续深挖的必要性。

编译器的优化性能受诸多因素影响，如何使编译器结合处理器架构，将应用程序的性能最大化地发挥出来，是一个值得探索的方向。程序代码在编译器中的表示形式对编译器的优化性能有较大的影响，程序中的某些代码重用或是优化处理，可能会导致无效代码的出现[4]。无效代码是程序中不会被访问到的变量或不会被执行到的代码块，消除无效代码可以通过删除程序中那些不影响运行结果的部分，以节省代码占用的内存空间，提高程序执行效率。编译器中的无效代码删除算法依赖数据流分析技术，该算法利用收集的全局信息，通过删除无效变量或代码块，调整程序的控制流程图，从而为优化公共子表达式删除、循环等创造条件[5]。GCC编译器中保守的无效代码删除和常量传播优化，在函数调用层数或结构体层数太多、复杂度太高时，优化效果存在一定的局限性。

本文提出一种依赖数据流分析的激进蝴蝶优化方法，作为无效代码删除优化的一个动态扩展方案，侧重解决分支路径与运行时输入参数值相关的这类应用程序的优化问题。该方法利用静态单赋值SSA(Static Single Assignment)中间表示，根据动态运行时输入参数的传递过程，分析出特定区域中关键变量的可能值，结合变量值，自动为程序生成多个代码形状类似蝴蝶(butterfly)的分支代码，称为butterfly分支，使编译器在程序编译阶段，构建出所有可能的流程分支。最后通过分析验证了该方法的可行性，并在SPEC CPU 2017上进行实验测试取得了一定的性能提升。

2 相关工作

随着机器学习技术的日趋成熟和在各领域的广泛应用，AI编译器也呈现出蓬勃发展的态势，AI编译器优化技术的研究也愈加被重视。寒武纪针对智能处理器架构而设计的BANG语言及其编译工具链，提升了智能计算编译器的开发效率。华为为解决安卓系统碎片化问题研发了方舟编译器。阿里巴巴和腾讯等众多企业都为智能芯片搭载了相应的编译器。编译优化技术也越来越趋向自动化和智能化。例如，为在众多优化方法中预测出程序最佳的编译优化参数组合，Ballal等人[6]提出一种迭代编译的遗传算法;刘慧等人[7]通过使用监督学习的方法对函数特征进行提取，并建立了学习模型以对程序最佳优化参数组合进行预测。而文献[8]则是直接基于GCC开发更高效的机器学习编译器Milepost GCC，并经过系列优化后能更好地减小代码大小和缩短编译时间，提高程序执行效率。

在传统的编译器优化技术中，数据流分析方法被应用于常量传播、无效代码删除、向量化优化、并行化和冗余删除等诸多程序优化技术中。数据流描述的是操作和数据之间的关系，由控制流图CFG(Control Flow Graph)、基本块(basic_block)等要素组成。在关于数据流分析问题的研究中，连瑞琦等人[9]提出一种增量式数据流分析方法，该方法解决了数据流信息的失效和重算等问题，能更好地处理、维护数据流信息。Li等人[10]采用运行时数据流信息消除并行编译器中无效代码引起的不准确问题。汪小飞等人[11]介绍了数据流方程的几种求解方法，给出了最常用的迭代求解算法的具体实现，并简要分析了GCC编译器中的数据流分析实现方法。杨小川等人[12]根据分析关键变量的数据流信息，提出了一种程序切片技术，通过该技术能更好地利用编译时信息，减小程序的规模。

基于数据流分析方法的静态单赋值SSA表示在现代编译器甚至是虚拟机中都有着极其重要的作用，它的出现使数据流分析和优化算法实现更容易。文献[1]提出了MC-SSAPRE算法，以获得部分冗余消除的最大收益。文献[2]研究总结了现有的冗余消除优化中存在的局限性，提出了更为有效的优化方法。文献[13]根据数据流分析结果，针对部分冗余消除优化进行了论述和变换证明。文献[14]提出基于代码动作扩展的部分无效代码删除，有效提高了优化效率。

3 激进蝴蝶优化方法的设计与实现

3.1 总体设计

程序的总体设计示意图如图1所示，假设指定代码区域在函数functionA中，该区域程序的流程分支与type参数的取值相关，且依赖于运行时参数，可能值为a、b或c，只有当type值为b时才是有效的流程分支；而当type值为a或者c时，该区域代码为无效代码，此时不再需要进行逻辑运算，可以直接删除。因此，通过设计butterfly优化，对该区域代码创建条件分别为type等于a，b和c的3个流程分支，使程序在编译期为代码可能的参数值生成条件分支，在程序运行时根据输入参数值可以直接运行正确的流程分支，从而避免代码中不必要的逻辑运算。

Figure 1 Schematic diagram of the overall design of the program

3.2 SSA中间表示介绍

静态单赋值(SSA)表示是和前端语言与目标机器无关的一种中间表示，它在程序的编译过程中对每条语句的变量定义一个唯一的名称[15]。通过使用静态单赋值中间表示能简化程序的全局过程间优化，它消除了复杂的寻址方式和指令语义的副作用[16]，是一种不可或缺的全局过程间数据流分析形式，不管是GCC、LLVM这些开源编译器或是ICC、AOCC等商业编译器都在使用SSA形式的中间表示[17]。

GCC中的Tree-SSA包含原始程序的完整控制、数据和类型信息，是一种基于SSA表示的扩展型框架，它对GCC的树表示进行操作[18]。GIMPLE中间表示转换为SSA中间表示之后经过了多个SSA pass优化才转换为寄存器传输语言RTL(Register Transform Language)中间表示，然后在RTL上根据机器模型进行指令选择并输出最终的目标文件。

3.3 构建butterfly分支

butterfly分支由控制流图的基本块(basic_block)复制而来。程序控制流图中一个流程分支的基本块从另一部分复制而来，再通过获取变量最终所有可能的值、切分原始基本块之间的连接边、创建条件基本块并构建then分支和else分支以形成具有2个或多个流程分支的控制流程图，它的每一个分支即称为butterfly分支。

构建butterfly分支是该方法的核心部分，通过对程序的指定区域创建条件判断语句，构建出butterfly分支，调整修复控制流图，并更新SSA的PHI节点信息，得到的代码中包含了几个流程分支条件及其对应分支代码，再经过常量传播、无效数据删除等全局优化之后简化控制流。这一系列操作在编译器的编译阶段进行，在程序的运行阶段会根据输入的参数值，找到正确的流程分支，从而简化程序中不必要的逻辑运算，减少运行时间，以此达到对程序优化的目的。

如图2所示是具有2个butterfly分支的控制流图抽象模型。图2中包含了原始代码的控制流图和进行butterfly优化之后的控制流图。

Figure 2 Abstract model of butterfly control flow graph

图2a是一个简化的程序控制流图，其包含1个entry_bb、1个exit_bb和程序的主体代码基本块，它们分别通过ENTRY_EDGE、EXIT_EDGE和ORIG_BBS进行关联。图2b所示是将源码控制流图抽象成butterfly的设计模式，corig_bbs是根据orig_bbs复制而来的代码主要逻辑部分，作为条件语句块cond_bb2的then分支，false_bb是由orig_bbs中EXIT基本块的前置基本块复制而来，作为条件语句块cond_bb2的else分支，条件语句块cond_bb1和cond_bb2是根据参数的2个可能值创建出的基本块，cond_bb2作为cond_bb1的else分支，orig_bbs基本块作为条件语句块cond_bb1的then分支。

若判断出参数有多个可能的值，需要对程序代码创建多个分支结构，则可按照该butterfly的控制流图模型继续创建条件基本块cond_bb3，并添加其then分支和else分支代码。如图3所示，条件基本块cond_bb2的else分支指向一个新创建的基本块，以此形成一个新的语句分支，表明该方法在复杂的控制流结构中的适用性。

Figure 3 Abstract model of control flow graph with multiple of possible values of parameters

3.4 与其它优化组合

在GCC编译器中Tree-SSA上进行的优化包括：无效数据删除、无效指令和存储删除、公共子表达式消除、部分循环优化以及常量传播等。本文提出的激进蝴蝶优化方法处于SSA优化pass的前期部分，能有效结合SSA中间表示上的其余优化，最大化地发挥出组合优化的性能。LLVM编译器中的SSA中间表示是各阶段使用的通用代码，贯穿于整个中间过程，众多优化pass都在SSA上进行，该方法能有效结合其它优化方法，发挥出优化效果。

对于一些逻辑相对较复杂的程序代码，采用激进蝴蝶优化方法对局部代码构建butterfly分支后，代码中包含参数取值的流程分支。在程序运行时这些流程分支中只有一个会被执行，这便会促进SSA上众多优化操作的进行。对于逻辑相对较简单的程序，通过控制流分析或相关支配关系优化，可以找出程序中的部分常量和不可访问的代码段，直接删除无效代码段，从而达到优化效果。

4 实验与结果分析

4.1 实验平台

为了对本文提出的激进蝴蝶优化方法的可行性和有效性进行评估，本文主要采用GCC编译器进行实验，将优化方法应用到GCC 8.2.0编译器，在Intel的Ubuntu Linux和AMD的Red Hat Linux 2种平台上，对优化前后的GCC 8.2.0编译器进行实验。表1给出了实验中所使用平台的主要信息。

Table 1 Main information of the experimental platform

在Intel和AMD 2种平台上，对GCC 8.2.0编译器进行SPEC CPU 2017基准测试。SPEC CPU 2017包含43个基准测试套件，涵盖区域海洋模拟、天气预报等众多领域，是一套被国际上广泛用于评估编译器性能的标准测试套件[19,20]。选定优化前GCC 8.2.0编译器为参考编译器(base compiler)，优化后的GCC 8.2.0编译器为目标编译器(target compiler)，使用ref输入数据集进行基准测试。

采用测试结果的ratio值来进行编译器优化前后的性能对比，根据式(1)，以参考编译器运行benchmark得出的ratio值为基准，根据目标编译器运行benchmark得出的ratio值计算出目标编译器的性能提升比ratiospeedup。

(1)

4.2 方法的可行性分析

在可行性方面，采用优化前的编译器编译经手工修改的代码，若得到的关键中间表示与优化后的编译器编译原始代码得到的关键中间表示一致，说明该方法可行。

下面列举了一个示例程序以及该示例程序的源码butterfly变换：

示例代码：

long functionA(const Typetype){

longi;

longresult=0;

longresult1=0;

unsignedj=0;

for(j=0;j<100000;++j){

for(i=0;i

inttemp;

get_value(i,&temp);

result+=temp;

}

}

if(type&type1){

result1=getResult(result);

}

returnresult1;

}

源码butterfly变换：

long functionA(const Typetype){

longi;

longresult=0;

longresult1=0;

unsignedj=0;

if(type==type1){

for(j=0;j<100000;++j){

for(i=0;i

inttemp;

get_value(i,&temp);

result+=temp;

}

}

if(type&type1){

result1=getResult(result);

}

}

if(type==type2){

……

}

returnresult1;

}

示例代码描述了一个循环计算的热区域，for循环在某种常数参数下为冗余代码，其计算结果result在其后的条件判断中使用。条件语句中参数type的取值与运行时输入的参数值相关，该参数的可能值为type1和type2。源码butterfly变换是根据type1和type2这2个取值来创建2个代码分支，一个进行激进冗余删除优化，另一个维持原有保守设计，确保非常数参数条件下的正确性。

以上述代码为实验代码，进行2组对照实验，以对比编译器优化前后的控制流程图。图4a所示为采用优化后的编译器编译示例代码所得到的控制流程图。图4b所示是对上述源码butterfly变换后的代码采用优化前的编译器进行编译所得到的控制流程图。

图4a示例代码的控制流图中return语句所在的基本块和得到结果值的基本块被合并为bb17，所以比图4b少一个基本块bb18。从实验结果可以看出，编译器优化前后的控制流图一致，通过对比分析其汇编码也有相似的结构，由此说明该优化方法可行。

Figure 4 Control flow graph before and after compiler optimization

4.3 方法的有效性分析

在方法的有效性方面，主要通过在Intel和AMD的2个平台上分别进行基准测试，观察其性能表现。第1组实验在Intel平台上进行，分别使用优化前GCC和优化后的GCC对SPEC CPU 2017进行ref数据集的浮点测试；第2组实验在AMD平台上进行，同样采用优化前后的GCC进行ref数据集的浮点测试，分别得出在638.imagick_s测试用例上的ratio值。

根据式(1)对实验的ratio值进行计算得到性能提升比，如图5所示。实验数据表明，对于638.imagick_s测试用例，在Intel平台上，优化改进后的GCC 8.2.0性能提升比达到了26%，在AMD平台上的性能提升比达到了25%，该优化方法的有效性得到了验证。

Figure 5 Performance comparison of dead code elimination optimization dynamic extension technology of 638 imagick_s benchmark on Intel and AMD platforms

综合以上实验论述，验证了本文提出的激进蝴蝶优化方法的可行性和有效性。通过对程序代码块构建butterfly分支可以有效进行无效代码的删除，达到提升程序性能的目的。

5 结束语

本文提出一种依赖数据流分析的激进蝴蝶优化方法，作为无效代码删除优化的一个动态扩展方案，最后通过实验验证了该方法在GCC编译器上的可行性和有效性。该方法利用SSA中间表示，根据动态运行时输入参数的传递过程，分析出特定区域中关键变量的可能值，结合变量值，自动为程序生成多个代码形状类似butterfly的分支代码，使编译器在程序编译阶段为无效代码删除等相关组合优化提供可行的优化依据。该方法通过构建butterfly分支能调整程序的控制流程图，以促进其它优化的进行。接下来的工作是优化改进该方法，使其能在更多的程序中发挥优化作用，并且能做出更激进的优化，更自动化的判断。