所属栏目：计算机应用论文范文发布时间：2026-01-22浏览量:338
循环不变量外提算法是一种针对程序中循环结构的常用编译优化算法，其通过将循环体中的不变计算移动到循环外部来减少重复计算的开销，从而提高程序运行的速度。但在LLVM编译器中，传统的循环不变量外提算法会将全部循环不变量外提到循环体外部，当循环不变量达到一定数量时会导致寄存器溢出，在循环内引入额外的访存代价，对循环产生负优化效果。针对上述问题，在传统LLVM循环不变量外提算法的基础上，引入了一种循环代价分析算法，通过计算循环不变量在循环体中的运行代价和外提操作可能带来的溢出代价，评估其外提可能带来的收益，只对产生正收益的循环不变量进行外提，在有效减少循环体内重复计算的同时，规避引入额外开销的风险。在国产申威831处理器平台，使用典型用例进行优化效果测评，在千万级循环下，相较于传统循环不变量优化算法，提出的新优化算法具有17%以上的性能提升;使用SPECCPU2017基准测试集(SPECspeed2017Interger套件)、Perl解释器DKbench基准测试集、Python解释器pyperformance基准测试集进行综合优化效果测评，结果表明，相较于传统循环不变量优化算法，提出的新优化算法分别具有0.4%、0.63%和1%的性能提升。
关键词：LLVM编译器;编译优化;循环不变量外提;寄存器溢出;循环代价分析
论文《基于循环代价分析的循环不变量外提算法》发表在《计算机科学》，版权归《计算机科学》所有。本文来自网络平台，仅供参考。
1 引言
LLVM(Low-Level Virtual Machine)[1]是一个开源的编译器基础设施项目，旨在提供一个通用的编译器框架，用于各种编程语言和目标架构。其具有轻量级、模块化设计以及高度可扩展性等特点，被广泛应用于云计算、人工智能、科学计算、游戏设计等领域[2-5]。随着这些领域的快速发展，应用程序代码的复杂度越来越高，数据计算量越来越大。为了使程序能够高效地运行，LLVM的编译优化引起了学术界和工业界的广泛关注[6-8]。
在大数据、云计算等场景中经常出现复杂的数学计算，LLVM编译器通常将其编译生成多层嵌套循环结构，每层循环可能存在与循环变量无关的复杂表达式计算，如果每次循环都进行相关计算，会浪费计算机资源，影响性能。为消除循环内的冗余计算，LLVM利用循环不变量外提(Loop-Invariant Code Motion, LICM)优化算法[9]识别循环中的不变量，并将其提到循环体外进行计算，有效避免了大量重复的计算，提高了代码生成质量和程序运行性能。
但在Perl解释器场景中，其热点函数中存在一种由while+switch/goto组成的特殊循环结构，且每个case中包含一定量用于访问结构体成员的地址计算操作。在LLVM中，这类操作被称为GEP节点(GetElementPtr)[10]。针对此类场景，传统LICM算法将作为循环不变量的GEP全部外提，使用大量虚拟寄存器存放GEP结果，在寄存器分配阶段产生溢出，GEP结果被存储在栈上，导致循环中原始的GEP从低延迟的简单运算操作变成高延迟的访存操作，降低了循环的运行效率。该现象表明，传统的LICM算法存在一定缺陷，无法适用于部分特殊场景。
针对上述问题，本文提出了一种基于循环代价分析的LICM算法，对循环不变量外提操作进行代价分析，在确定其外提不会加重循环负担的情况下再执行外提操作，有效避免了优化使得循环运行效率下降的情况。同时，为了验证该算法的有效性，在LLVM13.0.0编译器上进行实现，并在国产申威831处理器平台上针对典型样例与基准测试集进行了优化效果验证。
2 研究背景
2.1 LLVM编译器系统结构
LLVM是以C++语言为基础编写的开源编译器项目，它提供了一套强大的工具和框架，用于构建编译器、即时编译器、静态分析工具和其他与编译器相关的软件。LLVM同时支持多种前端语言，如C、C++、Rust等，以及多种目标架构，如X86、AArch64、RISCV等。LLVM的整体架构采用传统的三段式结构设计，如图1所示，将编程语言转换到目标机器代码的过程分为前端、中端、后端3个部分。
| 前端语言 | 前端工具 | 中端 | 后端架构 | 目标代码 |
| C语言 | Clang前端 | LLVM IR优化 | X86后端 | X86代码 |
| C++语言 | Clang++前端 | LLVM IR优化 | AArch64后端 | AArch64代码 |
| Rust语言 | Rust前端 | LLVM IR优化 | RISCV后端 | RISCV代码 |
图1 LLVM整体结构(Fig.1 LLVM architecture)
LLVM前端通过词法分析、语法分析、语义分析等过程将编程语言转换为一种高度抽象的中间表示LLVM IR(Intermediate Representation)，这是一种静态单赋值(Static Single Assignment, SSA)[11]形式的表示，有助于编译器适用于多种语言和架构。
LLVM中端的任务是对IR进行一系列的优化操作[12]，形成更高效的IR。LLVM目前针对IR已经实现了多种优化方法，它们可以分为以下几类：
1. 基础块(Basic Block)级优化：对基本块内部的指令进行优化调整，如指令合并[13]、常量折叠、无用代码删除[14]等。
2. 函数级优化：对整个函数的结构进行优化，如函数内联[15]等。
3. 循环优化：对循环结构进行优化，包括循环展开[16]、循环合并、循环不变量外提、循环剥离[17]等。
4. 控制流优化：优化分支和跳转的控制流，如控制流简化[18]等。
5. 数据流分析：通过数据流分析来进行更高级别的优化，包括过程内和过程间数据流分析[19]。
此外，LLVM中端优化模块可以按照一定的顺序应用不同的优化。通常，LLVM使用一系列优化遍(Optimization Passes)，每个遍都会执行一组相关的优化。优化遍的顺序可以由用户配置，以满足特定的性能目标或需求。
LLVM后端的主要任务是将经过优化后的IR转化为目标机器代码[20]。这个过程涵盖了多个阶段，如图2所示。其中，右侧的优化遍是可选项，能够结合中端优化进一步提高生成代码的质量。左侧的框表示后端的各个必要阶段，其中指令选择阶段会根据IR中的指令匹配相应的目标机器指令[21];指令调度阶段用于调整生成的机器指令的顺序，以最大程度地利用目标机器的流水线和其他硬件特征[22];寄存器分配阶段为虚拟寄存器分配目标机器的物理寄存器[23];代码发射阶段将最终的目标机器指令生成到汇编代码或目标机器代码。
图2 LLVM后端代码生成流程图(Fig.2 LLVM backend codegen flowchart)
LLVM IR → 优化遍 → 指令选择 → 前指令调度 → 优化遍 → 寄存器分配 → 优化遍 → 后指令调度 → 优化遍 → 代码发射 → 汇编代码/目标机器代码
2.2 LLVM循环不变量外提
如图3所示，LLVM的循环结构主要由preheader基本块、循环体和exit基本块组成(虚线表示路径上可存在多个基本块)。其中，循环体内由多个循环内部基本块相互连接形成环路，完成循环计算;preheader和exit基本块分别负责循环前、循环后的工作。
图3 LLVM循环结构(Fig.3 LLVM loop structure)
preheader基本块 → 循环体(包含多个循环内部基本块)→ exit基本块
循环不变量外提的基本思想是识别循环内部基本块中取值不随循环发生变化的表达式，在不影响程序正确性的前提下，尽可能多地将其外提至preheader基本块或exit基本块[24]。此类表达式包括常量、在循环外赋值的变量、循环中保持相对固定的运算表达式、内存地址或偏移量等。
LLVM在中端优化模块和后端代码生成模块中分别设置了LICM优化遍，前者在IR层面进行初步LICM优化，后者结合寄存器压力和指令延迟进一步进行LICM优化。
3 传统LICM算法分析
本章在理论上分析了对循环结构进行循环不变量外提优化会产生的收益，并设计了典型样例，结合汇编代码阐述了传统的LICM算法在一些特殊场景中的缺陷。
3.1 循环不变量外提代价分析
如2.2节所述，一个任意层数的循环可以分为3个部分，即preheader基本块、循环体、exit基本块，其中循环体内又包含多个内部基本块。用(C_{P})、(C_{B})、(C_{E})表示各部分的运行代价，用(C_{loop})表示整个循环的运行代价，则(C_{loop})可以表示为：
[C_{loop} = C_{P} + C_{B} + C_{E} quad (1)]
而循环体的运行代价与循环体的执行次数以及循环体内的每个基本块的运行代价和执行频率相关，可以表示为：
[C_{B} = L * sum_{i=1}^{n} C_{bi} * f_{bi} quad (2)]
其中，(L)表示循环执行次数，(n)表示循环体中基本块的总数，(C_{bi})表示循环体中每个基本块的执行代价，(f_{bi})表示循环体内基本块的执行频率。将式(2)代入式(1)，可得循环的运行代价为：
[C_{loop} = C_{P} + L * sum_{i=1}^{n} C_{bi} * f_{bi} + C_{E} quad (3)]
从式(3)可以看出，随着循环次数的增加，循环的主要运行代价会由循环体的运行代价决定。当循环体内存在与循环变量不相关的复杂表达式计算时，大量重复计算会严重影响整个循环的运行效率。LICM优化算法的核心思想是通过将循环体中的循环不变量外提，来降低循环体的运行代价，从而降低整个循环的运行代价。
用(C_{B}')表示循环不变量外提后循环体的运行代价：
[C_{B}' = L * sum_{i=1}^{n} (C_{bi} - C_{vi}) * f_{bi} quad (4)]
其中，(C_{vi})是每个基本块中循环不变量执行的代价。
但在将循环不变量外提后，如果其在循环体内被引用会被提升到preheader基本块，反之会下沉到exit基本块。分别用(C_{pvi})和(C_{evi})表示每个基本块中循环不变量外提操作带来的提升到preheader基本块和下沉到exit基本块的运行代价，则执行LICM算法后，preheader基本块和exit基本块的运行代价(C_{P}')和(C_{E}')可以表示为：
[C_{P}' = C_{P} + sum_{i=1}^{n} C_{pvi} quad (5)]
[C_{E}' = C_{E} + sum_{i=1}^{n} C_{evi} quad (6)]
根据式(1)，在将循环不变量外提后，循环的整体运行代价(C_{loop}')为：
[
egin{aligned}
C_{loop}' & = C_{P}' + C_{B}' + C_{E}' \
& = C_{P} + sum_{i=1}^{n} C_{pvi} + L * sum_{i=1}^{n} (C_{bi} - C_{vi}) * f_{bi} + C_{E} + sum_{i=1}^{n} C_{evi} quad (7)
end{aligned}
]
利用式(3)减去式(7)，可得循环不变量外提后整体循环运行减少的代价(C_{reduce})：
[C_{reduce} = L * sum_{i=1}^{n} C_{vi} * f_{bi} - sum_{i=1}^{n} (C_{pvi} + C_{evi}) quad (8)]
而在实际的LICM算法执行中，由于运行机器寄存器数量有限，可能会导致部分不变量被存放在内存中，在preheader基本块和循环体中会存在额外的访存操作。分别用(C_{psi})和(C_{lrsi})表示这两部分的运行代价，则实际执行LICM算法后，循环的运行代价可以表示为：
[
egin{aligned}
C_{loop}' = & C_{P} + sum_{i=1}^{n} C_{pvi} + C_{psi} + L * sum_{i=1}^{n} (C_{bi} - C_{vi} + C_{lrsi}) * f_{bi} + C_{E} + sum_{i=1}^{n} C_{evi} quad (9)
end{aligned}
]
利用式(3)减去式(9)可得，在实际进行循环不变量外提后，循环运行代价降低值为：
[C_{reduce} = L * sum_{i=1}^{n} (C_{vi} - C_{lrsi}) * f_{bi} - sum_{i=1}^{n} (C_{pvi} + C_{psi} + C_{evi}) quad (10)]
从式(10)可以看出，LICM对循环的优化依赖于循环体内循环不变量外提后产生的代价降低，即(C_{vi} - C_{lrsi})的值。显然当(C_{vi} < C_{lrsi})，即循环不变量在循环体中原本的运行代价小于因为外提操作而产生的额外的访存操作的运行代价时，LICM不仅不会对循环进行优化，反而会增加循环运行的代价。
使用CPU时钟周期作为参考标准，对循环代价计算的准确性进行论证。现代处理器的超标量和乱序执行设计，导致精确地确定不同程序单个指令的时钟周期(即(C_{vi}))较为困难，因此设计一个典型样例来间接验证公式的准确性。源代码如下：
```c
int func(int x, int y, int z) {
for (int i = 0; i < 1000000000; i += 16) {
[i] = 21 * y + y * z + x;
x += y * z;
}
}
```
在样例循环中有两个不变量分别是(21 * y)和(y * z)，在O2优化选项下生成如下汇编代码：
```asm
func:
mull $18, $17, $0
s4addl $17, $17, $1
sll $17, 4, $21
addl $21, $1, $1
ldl $2, a($29)
ldi $3, -16($31)
.LBB0_1:
addl $16, 0, $16
addl $16, $1, $4
stw $4, 0($2)
ldi $3, 16($3)
ldih $4, 1526($31)
ldi $4, -7952($4)
cmpult $3, $4, $4
ldi $2, 64($2)
bne $4, .LBB0_1
.LBB0_2:
bis $31, $31, $0
ret
```
在上述汇编中计算不变量(21 * y)和(y * z)的指令分别是由s4addl、sll以及addl组成的指令序列和mull指令。通过移动计算循环不变量汇编位置的方法，分别测量4个实验场景所耗费的CPU时钟周期。
实验1：仅包含循环控制
实验2：仅包含循环不变量
实验3：循环不变量外提
实验4：循环不变量不外提
实验1循环体为空，只测量循环本身所消耗的CPU时钟周期;实验2测量循环中包含(21 * y)和(y * z)两个循环不变量所消耗的CPU时钟周期;实验3测量在循环不变量外提的情况下，完整循环所消耗的CPU时钟周期;实验4测量在循环不变量不外提的情况下，完整循环所消耗的CPU时钟周期。
测量结果如表1所列。
表1 循环代价测量实验(Table1 Loop cost measurement experiments)
| 实验编号 | 实验描述 | CPU时钟周期 |
| 实验1 | 仅循环控制 | 12550505 |
| 实验2 | 仅循环不变量 | 27141695 |
| 实验3 | 循环不变量外提 | 384547297 |
| 实验4 | 循环不变量不外提 | 400172340 |
根据式(8)的推导过程，(C_{reduce})由式(3)减去式(7)得出，即实验4的结果减去实验3的结果为15625043;根据(C_{reduce})定义，(C_{reduce})可由实验2的结果减去实验1结果得出，为14591190。由公式推导得出的计算结果与由定义得出的计算结果的比值为1.07，证明公式具备一定的准确度。
3.2 传统LICM缺陷分析
为了更好地阐述传统LICM算法在优化部分循环场景时的不足，设计了一个典型用例。源代码如下所示：
```c
func() {
int x, y, z;
int arr[16];
int case_val;
for (;;) {
switch (case_val) {
case 0:
arr[i + 1] = x - y;
arr[i + 2] = x * y + z;
arr[i + 3] = x * y - z;
arr[i + 4] = x ^ y - z;
arr[i + 5] = x * y - z;
break;
case 1:
arr[i + 6] = x * y - z;
arr[i + 7] = x - y * z;
arr[i + 8] = x + y + z;
arr[i + 9] = x | y - z;
arr[i + 10] = x * y | z;
arr[i + 11] = x * y | z;
break;
case 2:
arr[i + 12] = x ^ y | z;
arr[i + 13] = x | y ^ z;
arr[i + 14] = x - y * z;
arr[i + 15] = ~x + y | z;
break;
}
}
_func();
return 0;
}
```
在上述用例中，for/switch构成了程序的主循环，在每个case节点下都具有一定的计算操作，由于变量x、y、z的取值不随循环发生变化，因此基于它们的算术表达式的结果都是循环不变量。
在没有开启传统LICM算法优化的情况下，所生成的部分汇编代码如下所示：
```asm
preheader
case
.LBB0_7:
subl $12, $11, $0
stl $0, 0($1)
bis $2, 16, $1
addl $14, $10, $0
stl $0, 0($1)
br $31, .LBB0_2
```
从汇编代码可以看出，循环体中的循环不变量的运行代价主要是addl/subl指令(长字加法/减法运算)带来的代价，即式中的(C_{vi})。
在上述场景中，进行中端优化时，LLVM传统的LICM算法会将符合外提条件的循环不变量全部外提。在后端代码生成中，由于寄存器数量的限制，外提的不变量会有一部分溢出到栈中，导致生成了如下所示的部分汇编代码：
```asm
preheader
addl $17, $16, $5
stl $5, 104($30)
subl $16, $17, $1
stl $1, 72($30)
...
case
.LBB0_7:
ldl $3, 104($30)
stl $3, 0($2)
addl $11, $3, $5
ldl $6, 72($30)
stl $6, 0($5)
br $31, .LBB0_2
```
从上述汇编代码可以看出，case内部的addl/subl操作被提取到了循环体外，放到了preheader中;并且这些操作的结果被存在栈中，导致循环体内用到该结果时需要从栈中取出，循环体内因为操作外提而产生的访存代价(C_{lrsi})显然大于addl/subl操作在原本循环体中的执行代价，导致LICM算法不仅没有进行循环优化，反而增加了循环运行的代价，降低了程序的运行效率。
4 基于循环代价分析的LICM算法
本章将详细介绍本文提出的基于循环代价分析的LICM算法的流程和实现，从中端和后端两个阶段阐述了相对于传统LICM算法的改进，并重点介绍了所提循环代价分析算法。
4.1 总体算法设计
传统LICM优化遍涉及中端和后端两个部分。中端主要在IR层面识别循环不变量，并将识别到的循环不变量不加选择地进行外提。后端结合寄存器压力和指令延迟，对不变量进行选择性的外提。
为了能够解决传统LICM算法无法对一些包含大量循环不变量的循环结构进行优化，且会增加循环运行代价的问题，基于传统LICM算法，在LLVM中端和后端两个阶段进行改进，有选择地对循环不变量进行外提。总体算法框架示意图如图4所示。
图4 总体LICM算法框架示意图(Fig.4 Overall framework diagram of LICM algorithm)
开始 → 中端：循环不变量识别 → 阈值判定 → 循环代价分析算法 → 不变量外提 → 后端：寄存器压力重设 → 循环不变量识别 → 不变量外提收益判定 → 不变量外提 → 结束
从图4可以看出，在中端LICM中，对循环不变量进行识别后，引入了用于判定寄存器是否溢出的阈值;基于该阈值，设计了对循环不变量外提代价进行评估的循环代价分析算法，有选择地对循环不变量进行外提。在后端LICM中，在循环不变量识别前，对寄存器压力进行了重新设置;在识别后利用后端对指令延迟的精确计算，对不变量外提收益进行更精确的判定。
4.2 中端LICM算法
在中端优化模块中，传统的LICM算法将识别到的循环不变量全部外提，并不考虑外提后产生的溢出代价可能会大于循环体内循环不变量本身的执行代价。为了解决该问题，本文在LLVM中端LICM优化模块中引入了循环代价分析算法，有选择地对中端识别到的循环不变量进行外提。整个LLVM中端LICM优化模块阶段的算法流程如图5所示。
图5 LLVM中端优化阶段的LICM算法流程(Fig.5 LICM algorithm flow in LLVM intermediate optimization stage)
开始 → 获取下一条IR指令 → 是否为循环不变量?(否→继续获取)→ 指令可外提?(否→继续获取)→ 指令安全无条件执行?(否→继续获取)→ 指令插入外提队列 → 是否遍历完成?(否→继续获取)→ 执行循环代价分析算法 → 结束
从图5可以看出，所提出的LICM算法在中端对IR的优化具体包含以下步骤：
步骤1：识别循环中的不变量。遍历循环对应的IR指令，检查指令含有的操作数，如果该指令所有操作数均不是来自其他指令，则该指令是循环不变量。此外，如果指令的所有操作数的定义都不在本循环中，那么该指令是本循环的循环不变量。
步骤2：对于步骤1得到的循环不变量指令，判断其是否可以被外提。对于算法中预设的指令，如访存、调用、比较和GEP等指令，编译器可以通过内存分析、操作数来源分析等手段判断该指令是否可以外提。对于不在预设范围内的指令，算法默认其不可以外提。
步骤3：判断指令是否可以被安全、无条件地执行。如果指令可能会产生自陷，或者指令有副作用，则不能将其外提。
步骤4：将经过步骤3得到的可外提的指令插入到等待外提的优先队列。
步骤5：执行循环代价分析算法，对具备外提条件的循环不变量IR指令进行评估，对符合评估条件的指令进行外提。
4.3 循环代价分析算法
为了评估当前循环中的循环不变量的运行代价与对其进行外提可能产生的溢出代价，并根据式(10)挑选其中最值得外提的指令进行不变量外提，设计了一种新的循环代价分析算法。在该算法中设计了两个阈值(T_{call})和(T_{normal})，其分别表示循环中存在函数调用的情况与普通循环的情况下能够被寄存器保持的最大变量数。(T_{call})主要依据被调用者保护寄存器的数量进行设定，(T_{normal})主要依据可用的临时寄存器(包括被调用者保护寄存器)的数量进行设定，两者的值可以根据程序特征进行调整，设计相应的编译选项，允许用户手动设置经验值。
算法的具体步骤如下：
步骤1：遍历循环，收集循环内的指令类型信息，如果循环内存在函数调用指令，只有部分寄存器被子函数保护，循环内能够用于保持变量的寄存器数较少，则设置判定阈值为(T_{call})，否则为(T_{normal})。
步骤2：统计待外提队列中的指令数量，如果数量小于或等于阈值，则循环不变量指令外提不会产生其他影响，将待外提队列的指令全部进行外提操作。
步骤3：对于外提指令数量大于阈值的情况，计算并维护待外提指令优先级队列。通过LLVM预留的接口，调用后端架构的目标平台转换信息计算该条指令的预计运行代价(C_{vi})，并根据代价数值将指令插入优先级队列，保证队列头的指令在循环体内的运行代价最大。
步骤4：遍历优先级队列，依次从队列中取出等待外提的循环不变量指令，得到指令在循环体内的运行代价(C_{vi})，根据指令数据类型可以获得指令进行外提可能产生的溢出代价(C_{lrsi})。根据式(10)，当(C_{vi} leq C_{lrsi})时，该循环不变量外提会使得优化后循环降低的代价小于零，产生负收益，故不进行外提操作;仅当(C_{vi} > C_{lrsi})时，进行外提操作。当取出的指令运行代价数值为0时，不再需要对其进行外提，停止从队列中获取指令。
4.4 后端LICM算法改进
在完成中端LICM优化后，在测试分析的过程中，发现以下缺陷需要后端协同解决：
1. 在中端LICM算法设计中的阈值尽管可以使用编译选项调整，但有时并不能很好地反映不同架构寄存器数量的区别。
2. 在中端进行预期代价的计算时，没有考虑因CPU型号支持的指令不同而实际执行代价不同的情况。
针对这两类缺陷，在LLVM后端对传统LICM优化遍进行了改进。首先，对函数调用阈值进行动态调整，针对循环内存在函数调用的情况，查看寄存器表，根据不同平台的保留寄存器重新计算LICM的阈值。其次，在指令调度阶段针对指令的延迟进行精确计算，当指令延迟大于典型的访存延迟时，该指令外提不会劣化循环性能，带来的潜在性能收益高于不外提，从而将该指令进行外提。通过这两方面的改进，来弥补所提出的算法在中端LICM模块中存在的缺陷。
5 实验与结果分析
5.1 实验环境
本文在开源编译器LLVM13.0.0上实现了基于循环代价分析的LICM算法，并在国产申威831处理器平台上针对传统的LICM算法和本文提出的新LICM(以下简称本文LICM)算法进行了对比测评。实验软硬件环境参数如表2所列。
表2 软硬件环境参数(Table2 Software and hardware environment parameters)
| 参数 | 参数值 |
| 指令集架构 | SW64 |
| CPU主频 | 2.5GHz |
| 内存大小 | 16GB |
| 内核版本 | 4.19.0 |
| 操作系统 | - |
5.2 典型用例性能提升效果
针对3.2节设计的典型用例，本文对循环体内x、y、z组成的表达式进行代价分析，有选择地进行外提，以有效规避潜在的寄存器溢出风险。在千万级的循环规模下，本文LICM较传统LICM有17%以上的性能提升。
5.3 基准测试集
为了能够更全面地评估本文LICM算法的有效性，采用CPU标准性能评估测试集SPEC CPU2017、典型应用Perl解释器的基准测试集DKbench和典型应用Python解释器的基准测试集pyperformance这3个公开基准测试集来评测算法的综合表现。其中，Perl和Python解释器的核心代码均主要由循环结构组成，涉及大量循环不变量的处理，适用于本文算法的效果验证。
5.3.1 SPEC CPU2017
SPEC CPU2017包含SPECspeed2017 Integer、SPECspeed2017 Floating Point、SPECrate2017 Integer、SPECrate2017 Floating Point共4个套件，分别用于测评处理器整数单任务、浮点单任务、整数多任务、浮点多任务的处理能力[25]，本文采用SPECspeed2017 Integer套件(包含10个测试程序)，使用SPEC CPU2017规定的几何平均计算综合结果。
5.3.2 DKbench
本文基于Perl5.28.1对DKbench2.4进行实验。DKbench2.4包含Moose(Perl对象框架)、DBI、SQL(Perl数据库接口)、Regex(Perl正则表达式)等18个Perl典型应用，支持Single和Multi共2个测试套件，分别用于测评处理器单任务和多任务的处理能力。本文采用Single套件，使用DKbench规定的算术平均计算综合结果。
5.3.3 pyperformance
本文基于Python3.9.9对pyperformance1.10.0进行实验。pyperformance1.10.0包含91个Python典型用例，根据测试重点的不同分为高层应用、异步IO、数学运算、正则表达式、序列化、启动时间、模板库共7个子类。本文采用pyperformance默认的测试和结果对比方法。
5.4 基准测试集实验数据与分析
在国产申威831处理器平台上，分别在SPEC CPU2017、DKbench和pyperformance相应的套件上进行测试，均采用-O2和-static编译选项。
5.4.1 SPEC CPU2017测试结果
在测评SPEC CPU2017时，LICM算法阈值设置为(T_{call}=6)，(T_{normal}=24)的效果较好，测评结果如表3所列。从表中可以看出，本文LICM算法相比传统LICM算法在600.perlbench_s、625.x264_s、648.exchange2_s等程序上具有一定幅度的性能提升，在几何平均上具有0.4%的性能优势，且针对单个程序无负效果。
表3 SPEC CPU2017测试结果(Table3 SPEC CPU2017 test results)(%)
| 程序 | 传统LICM的性能提升效果 | 本文LICM的性能提升效果 |
| 600.perlbench_s | -2.68 | 0 |
| 602.gcc_s | 1.27 | 0 |
| 605.mcf_s | 0 | 0 |
| 620.omnetpp_s | 0 | 0 |
| 623.xalancbmk_s | 3.12 | 3.01 |
| 625.x264_s | 0.58 | 1.16 |
| 631.deepsjeng_s | 0 | 0 |
| 641.leela_s | 3.88 | 5.85 |
| 648.exchange2_s | 3.88 | 4.09 |
| 657.xz_s | -0.23 | 0.11 |
| 几何平均 | 0.98 | 1.38 |
5.4.2 DKbench测试结果
在测评DKbench时，算法阈值设置为(T_{call}=6)，(T_{normal}=24)的效果较好，测评结果如表4所列。从表中可以看出，本文LICM算法相比传统LICM算法在Math::DCT、Regex/Subst、Regex/Substutf8等程序上具有一定幅度的性能提升，在算术平均上以0.63%的性能优势规避了传统LICM引入的负效果。
表4 DKbench测试结果(Table4 DKbench test results)(%)
| 程序 | 传统LICM的性能提升效果 | 本文LICM的性能提升效果 |
| CSS::Inliner | -0.72 | 0 |
| Crypt::JWT | 0 | -0.72 |
| Astro | -1.77 | 0 |
| DBI/SQL | 0 | 0 |
| DateTime | 0.77 | 0 |
| Digest | 0.33 | 0 |
| Encode | 1.61 | 1.20 |
| HTML::FormatText | 0.92 | 1.83 |
| Imager | 0 | 0 |
| JSON::XS | 0.52 | 1.56 |
| Math::DCT | -1.95 | 0.65 |
| Math::MatrixReal | 1.56 | 0.78 |
| Moose | 0.96 | 0.96 |
| Mooseprove | -1.87 | 1.32 |
| Primes | -0.93 | -1.97 |
| Regex/Subst | -4.82 | -1.37 |
| Regex/Substutf8 | -4.78 | 1.81 |
| Text::Levenshtein | -0.29 | 0.06 |
| 算术平均 | -0.29 | 0.63 |
5.4.3 pyperformance测试结果
在测评pyperformance时，算法阈值设置为(T_{call}=6)，(T_{normal}=24)的效果较好，测评结果如表5所列。从表中可以看出，本文LICM算法相比传统LICM算法，在7个测试子类上普遍存在性能提升，在整体上具有1%的性能优势。
表5 pyperformance测试结果(Table5 pyperformance test results)
| 程序 | 本文LICM较传统LICM的性能提升 |
| apps | 1.01× faster |
| asyncio | 1.02× faster |
| math | 1.00× faster |
| regex | 1.01× faster |
| serialize | 1.01× faster |
| startup | 1.02× faster |
| template | 1.01× faster |
| all | 1.01× faster |
5.4.4 实验结论
综上，相比传统LICM算法，本文LICM算法在CPU标准基准测试集和典型应用上具有较好的综合性能表现，实验结果大多为正向提升，具有较好的普适性;部分程序存在性能下降的问题，如SPEC CPU2017的602.gcc_s程序、DKbench的Primes程序等，原因为设定的(T_{call})和(T_{normal})阈值不适用于这些程序的行为特征。
结束语
针对传统的LLVM LICM算法无法对部分含有大量循环不变量的循环结构进行有效优化的问题，本文提出了一种新的基于循环代价分析的LICM算法。通过对循环中的不变量进行代价评估，有选择地进行循环不变量外提操作，避免出现寄存器溢出、循环体内因为大量不变量外提而带来的额外访存开销等问题，有效地对循环进行了优化。通过在国产申威831处理器平台对典型样例和基准测试集SPEC CPU2017、Perl DKbench、Python pyperformance进行性能测试，验证了本文提出的基于循环代价分析的LICM算法相比传统的LICM算法的优化效果更好。本文中端LICM算法中用于判定寄存器是否溢出的阈值主要依赖于针对应用特征和架构特点进行的手动设定，无法针对复杂代码场景进行自适应;后端LICM算法的改进空间有限，尤其是无法还原中端已外提的循环不变量。下一步将深入研究该阈值的自动计算技术，以进一步提高算法优化效果。
参考文献
[1] LATTNER C, ADVE V. LLVM: A compilation framework for lifelong program analysis & transformation[C]∥International Symposium on Code Generation and Optimization. IEEE, 2004: 75-86.
[2] CHO J, CHO D, KIM Y. Study on LLVM application in Parallel Computing System[J]. The Journal of the Convergence on Culture Technology, 2019, 5(1): 395-399.
[3] WANG L, GAO K, ZHAO Y Q, et al. Deep Learning Compiler Load Balancing Optimization Method for Model Training[J]. Journal of Frontiers of Computer Science and Technology, 2024, 18(1): 111-126.
[4] ZHU X L. The implementation and optimization of deep learning compiler based on GPDSP[D]. Changsha: National University of Defense Technology, 2021.
[5] XIE H C. An Auto Performance Predict Research for Scientific Program Based on LLVM [D]. Harbin: Harbin Institute of Technology, 2016.
[6] PEELER H, LISS, SLOSSA N, et al. Optimizing LLVM pass sequences with Shackleton: a linear genetic programming framework[C]∥Proceedings of the Genetic and Evolutionary Computation Conference Companion. 2022: 578-581.
[7] CHAI Y, CHEN M, LI J, et al. Implementation and optimization of data prefetching algorithm based on LLVM compilation system[C]∥6th International Conference on Electronic Technology and Information Science. 2021.
[8] HUANG Z F, SHANG J D. Optimization based on LLVM global instruction selection[C]∥2021 International Conference on Computer Network Security and Software Engineering. 2021.
[9] AHO A V, SETHI R, ULLMAN J D. Compilers: principles, techniques, and tools[M]. Reading: Addison-Wesley, 1986.
[10] ZAKOWSKI Y, BECK C, YOON I, et al. Modular, compositional, and executable formal semantics for LLVM IR[J]. Proceedings of the ACM on Programming Languages, 2021, 5 (ICFP): 1-30.
[11] ANDREW W A. SSA is Functional Programming[J]. Acm Sigplan Notices, 1998, 33(4): 17-20.
[12] YAN Y, PAN Z, YU L, et al. Research on the influencing factors of LLVM IR optimization effect[C]∥2023 IEEE 3rd International Conference on Information Technology, Big Data and Artificial Intelligence (ICIBA). IEEE, 2023, 3: 756-763.
[13] SHANG J, XU K, HAN L, et al. Optimization of Access Address Calculation for LLVM[C]∥2023 4th International Conference on Information Science, Parallel and Distributed Systems (ISPDS). IEEE, 2023: 458-464.
[14] RODRIGUEZ G CANCIO M, COMBEMALE B, BAUDRY B. Automatic microbenchmark generation to prevent dead code elimination and constant folding[C]∥Proceedings of the 31st IEEE/ACM International Conference on Automated Software Engineering. 2016: 132-143.
[15] GUO Z H, WU Y X, AN L F, et al. Study on function inlining optimization technologies based on LLVM[J]. Computer Engineering and Applications, 2017, 53(3): 41-46.
[16] WANG C X, HAN L, LIU H H. Optimization of loop unrolling based on instruction Cache and register pressure[J]. Computer Engineering & Science, 2022, 44(12): 2111-2119.
[17] HU Y X, ZHENG Q L. Research on Deep Learning Based Loop Auto-Schedule[J]. Journal of Chinese Computer Systems, 2024, 45(7): 1770-1777.
[18] MELLOR G, CRUMMEY J, ADVE V. Simplifying control flow in compiler-generated parallel code[J]. International Journal of Parallel Programming, 1998, 26(5): 613-638.
[19] LI H X, LIU J. Methods of Data Flow Analysis[J]. Computer Engineering and Applications, 2003, 39(13): 142-144.
[20] GONG L Q, SHEN L, ZHOU Q L, et al. Research and Implementation of Compile Lock Mechanism Based on LLVM[J]. Computer Application and Software, 2021, 38(11): 11-17.
[21] EBNER D, BRANDNER F, SCHOLZ B, et al. Generalized instruction selection using SSAG graphs[C]∥Proceedings of the 2008 ACM SIGPLAN SIGBED Conference on Languages, Compilers, and Tools for Embedded Systems. 2008: 31-40.
[22] LOZANO R C, CARLSSON M, DREJHAMMAR F, et al. Constraint-based register allocation and instruction scheduling[C]∥International Conference on Principles and Practice of Constraint Programming. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012: 750-766.
[23] DE SOUZA XAVIER T C, OLIVEIRA G S, DE LIMA E D, et al. A detailed analysis of the llvm’s register allocators[C]∥2012 31st International Conference of the Chilean Computer Science Society. IEEE, 2012: 190-198.
[24] LIANG J L, HUA B J, LV Y S, et al. Loop Invariant Code Motion Algorithm for Deep Learning Operators[J]. Journal of Frontiers of Computer Science and Technology, 2023, 17(1): 127-139.
[25] SHIH K, WANG Z S, ZHANG S Z, et al. Performance Evaluation Benchmark of General Purpose CPU: A Survey[J]. Acta Electronica Sinica, 2023, 51(1): 246-256.