第5章
循环基本知识

循环一般指程序中重复执行的指令序列，从程序的控制流图看，循环是CFG中的一个强连通分量子图。强连通指的是有向图中两个顶点存在有向边，可以相互到达；强连通分量子图是有向图中的“极大”强连通子图。“极大”的含义是指把图划分为若干强连通分量后，强连通分量之间不可以相互到达。

根据循环优化的便利性将循环分为两类：可归约循环和不可归约循环。两者的正式定义区分可以参见论文 ，本章简单地根据循环是否具有多个入口节点进行区分。有多个入口节点的是不可归约循环，如图5-1a所示；只有一个入口节点的循环是可归约循环，如图5-1b所示。

单入口可归约循环又称为自然循环，LLVM编译器里实现的循环就特指自然循环，其他的现代编译器（如GCC等）基本上也只支持自然循环。主要的原因是大部分循环优化方法仅适用于自然循环，不适用于不可归约循环（通常对不可归约循环不做优化）。本章主要介绍LLVM实现的循环，只会涉及自然循环的相关内容，因此在没有特别说明的情况下，本章会按照LLVM的习惯把自然循环简称为循环。下面首先介绍自然循环的性质，然后介绍LLVM实现的循环形态和特性，最后会对本章进行简单总结。

5.1 自然循环

自然循环的定义有许多的描述方式，直观地描述是“只有单入口、内部基本块可以构成环的子图”。下面采用支配关系（参考第4章）来给出自然循环的正式定义。首先我们需要用支配关系定义 回边 （Back Edge）。

回边：如果控制流图中存在边的目的节点支配其源节点的情况，则将这条边称为回边。

我们以图5-2为例进行说明：假设存在一条从节点BB2到节点BB1的边，同时节点BB1支配节点BB2，则这条边是回边；假设存在一条节点BB5到节点BB3的边，但节点BB3不支配节点BB5（因为存在从节点BB4到节点BB5的路径），所以这条边不是回边。

根据回边的含义，可以定义 自然循环 为：假设一条从节点 b 到节点 h 的回边（记为 b → h ），其中 h 支配 b ，则可以形成一个可归约循环；如果节点 x 属于这个自然循环，则满足 h 支配 x ，且存在一条可以从 x 直接到 b 的路径且路径不经过 h 。

我们根据这个定义就识别出哪些节点构成了自然循环。例如在图5-3中存在回边BB4→BB2，则其构成的自然循环只包含BB2、BB3和BB4，不包含BB1和BB5。因为BB1到BB4必定要经过BB2，而BB5不存在到BB4的路径，所以BB1和BB5不属于这个循环。

通过自然循环的定义，可以在程序的控制流中找出自然循环。但当程序较为复杂的时候，会出现多个自然循环，这些循环会存在嵌套的情况，即一个循环包含另一个循环。为了区分这种包含关系的循环，通常将位于外层的循环称为外循环（outer loop），位于内层的循环称为内循环（inner loop）。如图5-4所示，BB3和BB4组成的循环是BB2、BB3和BB4组成的循环的内循环，而BB2、BB3和BB4组成的循环是BB3和BB4组成的循环的外循环。

5.2 LLVM的循环实现

LLVM中实现的循环数据结构和循环相关的优化都是基于自然循环，不可规约的循环被当成基本的控制流处理（一般不会被优化）。为了便于后续分析和变换，会根据节点相对循环回边的位置，对一些特定位置节点用特定的术语来命名。主要有：

❑header（循环头）节点：回边的目的节点。

❑latch（闩）节点：回边的源节点。

❑exiting（待退出）节点：可以跳出循环的节点，即它有不在循环里的后继节点。

相关节点示例如图5-5所示。

为了便于优化，在循环外面也定义两种特殊的节点。

❑entering（待进入）节点：header节点在循环之外的前驱称为entering节点。

❑exit（退出）节点：entering节点在循环外的后继节点。

循环相关的entering、exit节点示例如图5-6所示。

注意

在上述示例图中，这些特殊节点都只画了一个。除了header节点外，循环中的特殊节点可能会有多个，而且还存在一个节点可以表示多个特殊节点的情况。例如，在如图5-7所示的循环中，它的3个特殊节点都是同一个节点。

此外，如果循环的待进入节点只有一个的话，也可以将其称为preheader节点（前置头）。

因为LLVM IR（包括后端IR）本身不保存循环信息，所以LLVM将从控制流中获取循环信息的功能作为一个公共分析Pass（记为循环识别Pass），当其他Pass需要循环信息的时候，只要调用循环识别Pass即可获得。因此大部分循环优化Pass都可以抽象成两步，即先调用循环识别Pass获取循环信息，然后对获得的循环进行优化。

因为LLVM支持多种高级语言循环语法，会产生多种不同的LLVM IR循环形式，这不利于实现各种通用的循环优化，所以LLVM提供了3种规范化的循环形式，并实现了相应的转换算法，可以将符合要求的循环转为规范化的循环形式。下面简单介绍LLVM里的循环识别和循环规范化的相关概念。

5.2.1 循环识别

从代码控制流中识别出循环有许多种算法，一种朴素的算法思想是通过深度遍历控制流来识别。而LLVM需要识别出来的循环都是自然循环，所以它使用了基于支配树的算法。这个算法首先找到循环的回边，然后利用回边找到循环包含的基本块，从而构造循环。在这个过程中，还会构建出循环之间的层级关系。整个实现的详细步骤是，逆序遍历待控制流对应的支配树，并对支配树中的每个节点 N 进行以下操作。

1）识别出所有 N 构成的回边，即遍历 N 的所有前驱节点。如果 N 支配了某个前驱节点 P ，则 N 和 P 构成一条回边。

2）如果 N 有一到多条回边，则以 N 为header节点构建循环，并将所有回边的header节点放入一个工作链表（worklist，是一个数据结构）中。之后遍历这个工作链表的节点，判断节点是否属于某个循环，并分为如下两种情况处理。

①如果节点不属于某个循环，则设定它属于节点 N 的循环。接着判断它是否为 N ，如果不是，则将节点所有的前驱节点加入工作链表；反之，则不需要处理（因为已经到达循环头）。

②如果节点已经属于一个循环 L ，则找到它所在的最外层循环，如果最外层循环是 N 的循环，则不需要进一步处理；反之，则将节点所在的最外层循环作为循环 N 的子循环，并将所有不在循环 L 里的前驱节点加入工作链表。

当整个支配树遍历完成之后，就找到了控制流中的所有循环，后续主要是填充各个基本块和循环间的映射信息。

5.2.2 循环规范化

自然循环的形式也是多样的，如可能会没有Preheader，或者有多条回边等情况。如果循环具有不同形态，则后续循环相关的优化要分别适配这些形态，才能保证优化效果，这会增加循环优化算法实现的复杂度。因此，LLVM实现了3种规范化循环形式：循环化简（Loop Simplify）形式、循环旋转（Loop Rotation）形式和循环封闭SSA（Loop-Closed SSA，LCSSA）形式。将各种类型的循环尽可能转换为统一的循环形式，便于后续的循环优化。

1.循环化简形式

循环化简后，循环的形式具有以下3个性质。

1）有循环前置节点，即有且只有一个preheader节点。

2）循环有且只有一条回边。

3）循环专用的exit节点可以被循环的header节点支配，所有exit节点的前驱节点都是循环内的节点。

循环化简形式示意图如图5-8所示，符合上述3个性质。

图5-9的3个循环都不是循环化简形式，图5-9a没有循环前置节点，因为它有多个待进入节点；图5-9b有多条回边；图5-9c的exit节点有循环外的节点（BB2节点）。因此3个循环都不符合循环化简的形式。

循环化简形式比较方便于做一些循环优化，如循环不变量外提（可以直接外提到循环前置节点里）和代码下沉（将代码下沉到exit节点里）等。为了将一些不符合循环化简形式的循环尽可能地进行化简，LLVM还专门实现了一个Pass。这个Pass针对循环化简形式的性质设置了下面3个主要功能。每个功能点都是先判断循环是否符合对应的性质，如果不符合则执行相应的变换，并尝试让其符合。

1）添加循环前置节点。

2）添加专用的循环退出节点。

3）拆分多回边共用头节点的循环。

此外，该Pass还具有删除循环中所有不可达基本块等功能，这主要也是为简化循环服务的。更具体的内容读者可以参阅代码了解，这里不再赘述。例如，将图5-9a进行循环化简，如图5-10所示。

2.循环旋转形式

循环旋转形式指的是循环的latch节点同时是一个exiting节点（即do-while形式的循环），其示意图如图5-11所示。

因为循环旋转形式比循环化简形式更加规范化，所以它也满足循环化简形式。循环旋转形式擅长外提循环中的“load指令”，同时它也擅长进行循环向量化。LLVM提供了一个Pass尝试将循环化简形式变换成循环旋转形式。该Pass迭代地旋转循环中的指令位置，直到将循环变成do-while形式，或者无法再进行位置旋转为止。（这也是循环旋转形式的由来。）此外，为了保证与原始循环语义相同（例如循环体一次都没有执行的情况），会添加一个用于判定循环执行次数的节点，称为guard（守卫）节点。

循环旋转示例如代码清单5-1所示。该示例中有一个循环，该循环执行一条乘法和加法的语句。

代码清单5-1 循环旋转示例代码

图5-12展示了对代码清单5-1中的循环进行旋转变换的状态变化。其中，图5-12a是循环旋转前的示意图，循环是从循环头退出，所以不是do-while的形式；图5-12b是经过旋转之后的循环，从循环尾部退出，变成了do-while的形式；图5-12c是添加了guard节点后的最终形式。

3.循环封闭SSA

如果LLVM IR中存在循环，则为循环增加额外的约束：循环中定义的值只在循环中使用，如果循环中定义的值逃逸到循环外，则在循环出口处的基本块中插入φ函数。满足这种约束的LLVM IR称为循环封闭SSA（即LCSSA）。本节示例来自LLVM官网 。

循环封闭SSA示例如代码清单5-2所示。

代码清单5-2 循环封闭SSA示例代码

在代码清单5-2中，X3在循环外被使用，所以不符合循环封闭SSA的形式。为了满足循环封闭SSA的形式，在循环出口处插入φ函数。因为本例中的循环出口刚好和X3的使用点位于同一基本块，所以插入φ函数后得到的结果如代码清单5-3所示。

代码清单5-3 在循环出口处插入φ函数

虽然这个φ函数是冗余节点，但是完全不影响程序的正确性，而且这些冗余节点可以在后续的优化中删除，但是额外引入的φ函数让许多循环优化更加简单。

例如，一些优化（如值范围分析）需要分析出在循环中定义而在循环外使用的值，刚好就是为了满足LCSSA而创建的φ函数，所以就不用分析和关注循环了，只需要关注循环出口基本块的φ函数即可。读者可以参考LLVM官网中关于LCSSA的一些案例（例如有关规约变量、循环变量替代等），获得更多内容。

LLVM的实现中有一个Pass（rewrite into loop closed SSA）用来将SSA形式的IR重写为LCSSA形式，还有一个Pass（verify loop closed SSA）是用来检查LCSSA的循环不变性。读者也可以自行验证，此处不再赘述。

5.3 本章小结

现代程序越来越复杂，其中针对循环的优化是提高编译器性能的关键。LLVM不仅提供了循环相关的公共分析Pass，涉及循环表示、循环识别和循环规范化，同时提供了许多的循环优化Pass，如循环不变量外提、代码下沉、软流水和硬件循环等。本章主要介绍循环的基本概念和循环标准形式变换，而循环优化相关的介绍读者可以参阅本书第9章、第11章的内容和相关资料。 jFb3f1Ph00B2EqUFO7hF9lzIHHW4nm4Y1C365xQMcXVrl2ClYPwL5w53XjdsPa00