循环优化 | 编译器

本文是系列视频 循环优化 的笔记。

循环展开和压紧

基础概念

• 减少循环分支指令执行的次数
• 获得了更多的指令级并行
• 增加了寄存器的重用

循环展开的合法性

循环展开需要在不影响原程序语义的情况下进行，上图中的展开就会改变原始语义。

循环完全展开

过度循环展开可能会增加寄存器的压力，引起指令缓冲区的溢出。

尾循环处理

编译器循环展开

依赖复杂的情况下编译器无法进行循环展开。

Clang 中和循环展开的编译选项：

选项	功能
-funroll-loops	打开循环展开
-fno-unroll-loops	关闭循环展开
-mllvm -unroll-max-count	为部分和运行时展开设置最大
-mllvm -unroll-count	确定展开次数
-mllvm -unroll-runtime	使用运行时行程计数展开循环
-mllvm -unroll-threshold	设定循环展开的成本限值
-mllvm -unroll-remainder	允许循环展开后有尾循环
-Rpass=loop-unroll	显示循环展开的优化信息
-Rpass-missed=loop-unroll	显示循环展开失败的信息

pragma 指令循环展开

• 指示编译器进行循环展开
• 指示编译器进行完全循环展开，需要在编译期确定循环次数
• 指示编译器按照指定的展开次数进行循环展开

向量化程序循环展开

循环合并

基础概念

循环合并是将具有相同迭代空问的两个循环合成一个循环的过程，属于语句层次的循环变换。具有以下优点：

• 减小循环的迭代开销
• 增强数据重用，寄存器重用
• 减小并行化的启动开销，消除合并前多个循环间的线程同步开销
• 增加循环优化的范围

循环合并的合法性

循环合并的有利性

并不是所有循环合并都可以给并行化带来收益，有以下两种情况：

• 分离限制：当一个并行循环和一个串行循环合并时，结果必然是串行执行的：

• 阻止并行性的依赖限制：当两个都可并行的循环存在一个阻止并行的依赖，进行循环合并后该依赖被合并后的循环携带：

这种情况下如果一定要进行循环合并，需要在两条语句中添加一个同步操作。

编译器中的循环合并

LLVM 中进行循环合并需要满足以下条件：

• 两个循环必须相邻
• 两个循环必须有相同的迭代次数
• 循环必须是等价的控制流，如果一个循环执行，另一个循环也保证执行

DO I = 1, N
  IF (I > 10) THEN
    A(I) = B(I) + C1
  ELSE
    A(I) = B(I) - C1
  ENDIF
ENDDO

DO I = 1, N
  IF (I > 10) THEN
    D(I) = A(I) + C2
  ENDIF
ENDDO 

此时合并两个循环需要考虑到控制流，合并后的结果如下：

DO I = 1, N
  IF (I > 10) THEN
    A(I) = B(I) + C1
    D(I) = A(I) + C2
  ELSE
    A(I) = B(I) - C1
    ! No fusion here
  ENDIF
ENDDO

• 循环之间不能有负距离依赖关系（即上一节「阻止并行性的依赖限制」中的例子）

选项	功能
-fproactive-loop-fusion-analysis	打开循环合并分析遍
-fproactive-loop-fusion	打开循环合并优化遍
-loop-fusion	通过 opt 工具对中间码进行循环合并优化

循环分布

基础概念

循环分布是将一个循环分解为多个循环，且每个循环都有与原循环相同的迭代空间，但只包含原循环的语句子集，常用于分解出可向量化或者可并行化的循环，进而将可向量化部分的代码转为向量执行。

循环分布效果

经过循环分布优化后，循环依赖被消除，S1 和 S2 都满足了并行化的条件：

与循环交换优化的配合

若循环不是紧嵌套循环导致无法进行后续优化操作时，可以使用循环分布将循环体变换为紧嵌套循环：

与循环合并优化的配合

编译器中的循环分布

选项	功能
-mllvm -enable-loop-distribute	打开循环分布优化
-Rpass=loop-distribute	打印循环分布优化成功的信息
-Rpass-missed=loop-distribute	打印循环分布优化失败以及失败的分析的相关信息
-Rpass-analysis=loop-distribute	打印循环分布优化失败以及失败的分析的相关信息

通过 pragma 进行循环分布

如果想指定某一个循环实现循环分布，则可以通过编译指示语句指定循环 #pragma clang loop distribute(enable) 开启循环分布优化。

循环交换

基础概念

当一个循环体中包含一个以上的循环，且循环语句之间不包含其它语句，则称这个循环为紧嵌套循环，交换紧嵌套中两个循环的嵌顺序是提高程序性能最有效的变换之一。循环交换是一个重排序变换，仅改变了参数化迭代的执行顺序，但是并没有删除任何语句或产生任何新的语句，所以循环交换的合法性需要通过循环的依赖关系进行判定。

循环交换有利性

循环交换后，A 的访问变为行优先，提高了数组 A 的局部性，也可以提高向量化的效果。

如果把这个过程反过来，则可以提高寄存器的重用性，即读取操作的次数从 M*N 次减少到了 N 次。

循环交换合法性

重排序某个依赖端点的循环交换是不合法的，即不要引起依赖关系的反转。

编器中的循环交换

选项	功能
-mllvm -enable-loopinterchange	打开循环交换优化
-Rpass=loop-interchange	打印循环交换优化成功的信息
-Rpass-missed=loop-interchange	打印循环交换优化失败以及失败的分析的相关信息
-Rpass-analysis=loop-interchange	打印循环交换优化失败以及失败的分析的相关信息

循环不变量外提

基础概念

循环不变量是指在循环迭代空间内值不发生变化的变量。由于循环不变量的值在循环的迭代空间内不发生变化，因此可将其外提到循环外仅计算一次，避免其在循环体内重复计算。

编译器中的循环不变量外提

循环分段

基础概念

循环分段是将单层循环变换为两层嵌套循环，内层循环遍历的是迭代次数为 strip 的连续区域（或叫条带循环），外层循环的步进单位为 strip，这个 strip 就是分段因子，分段因子需要根据硬件情况选取。

• 充分利用多个处理器资源
• 将可用的并行性转换成更适合硬件的形式

不适用的情况

每次循环的循环次数是不固定的：

循环分块

基础概念

循环分块是指通过增加循环嵌套的维度来提升数据局部性的循环变换技术，是对多重循环的迭代空间进行重新划分的过程。

三层嵌套循环分块

循环分裂

基础概念

循环分裂是将循环的迭代次数拆成两段或者多段，拆分后的循环不存在主体循环之说，也就是拆分成迭代次数都比较多的两个或者多个循环。

循环分裂的有利性

可以通过循环分裂将数组 coff 和数组 diff 的计算分开，得到两个循环，优化后的循环内引用数组的数量减少，这样每个循环的数据局部性都得到了提升。

循环倾斜

基础概念

循环倾斜是一种改变迭代空间形式的变换，用于挖掘循环中的并行潜能的优化方式，可以把存在的并行性用传统的并行循环的形式表示出来。

从原始的依赖关系中分析，可以看出示例 i 层迭代与 j 层迭代均存在依赖关系，所以 i 层与 j 层循环均不可以并行执行。然而，从数据读取顺序图中可以看出，按照从左到右、从下到上的执行顺序，一旦 i=1,j=1 执行完之后，i=2,j=1 和 i=1,j=2 即可并行执行，以此类推，当这两次迭代计算完成之后，i=1,j=3、i=2,j=2、i=3,j=1 即可执行，也就是对角线上的数据存在并行性。为了从迭代空间中提取出包含并行性的对角线，对该循环进行循环倾斜操作。

进行循环倾斜重映射迭代空间后，优化后迭代空间和数据读取顺序变为上图右边所示，从优化后的数据读取顺序图中可以看出，它的执行顺序依然是按照从左到右、从下到上，所以目前只是循环倾斜的第一步，此时循环内依然存在着依赖，而此时外层循环携带的依赖是交换敏感的，从而可以通过循环交换的方式生成并行循环。

变换方式

将 i 层和j层进行循环交换，优化后产生了梯形的迭代空间，从数据读取表格中看出，此时执行顺序依然是从左至右，从下到上，可以看出颜色相同的一行由于不存在依赖则可以并行执行。

循环倾斜优化后该循环可以转为向量执行，但是这种形式的向量代码存在一些缺点，向量的长度从 1 到 N，最后又变为 1，平均的长度为 N/2。简单来说，比如向量存储单元一次可以存储四个数据，那当 N=4 时，程序中只有蓝色框内数据可以满载向量存储单元，大部分向量指令（如左右两边的红色框内）是非满载的情况，在编译器中需要通过混洗指令组成需要计算的向量数据，也会带来较多的额外开销，所以优化人员需要衡量开销与收益，争取找到两者间的平衡，在采取是否进行循环倾斜优化。

针对上述问题，陈华军提出了一种基于全局数据重组的循环倾斜优化，针对迭代执行次数不一致的问题，实现非满载向量操作，使尾循环得以向量执行。

对于非满载的向量计算，读数据时，读取相应向量长度的数据，不需要计算的数据则为冗余数据，在计算过程中，冗余数据同样参与计算，但是将计算结果写回时，不写回冗余计算的结果。这里向量写操作是先将数据写入一个内存中新申请的临时向量空间中，再通过这个新申请的临时空间，将需要写回数组的合法数据写入计算后数组中数据相应的位置。

三层嵌套循环倾斜

第一步是先进行循环倾斜，即将 k 层迭代变成 i+j+1 的形式，再进行循环交换。这里需要注意最内层需要的是 j 循环，而中间一层是 i 循环。由于毎个循环携带一个依赖，该循环不能被并行化。对该循环实施循环倾斜后，最内层循环的依赖方向将改变，最内层循环可以通过使用替换 k=K+I+J 相对于两个外层循环被倾斜，进而使得其满足外层循环的并行化要求，将 K 层循环和 J 层循环交换后，内层循环的携带依赖被消除，因此内层的两个循环都可以被并行化。