第4章
支配分析

支配关系在编译优化中非常重要，在LLVM中有众多分析和变换依赖于支配分析。例如中端优化ADCE（Aggressive Dead Code Elimination，激进的死代码消除）、SimplifyCFG、BasicAliasAnalysis、LoopPass等。本章将介绍支配相关的概念和算法。

4.1 支配和逆支配

本节首先介绍支配、逆支配等相关定义，然后分析支配和逆支配的具体含义。

4.1.1 支配和逆支配相关定义

给定有向图 G =< V , E , r >，其中 V 表示图的顶点集合， E 表示图的边集合， r 表示图的起始节点集合（或者称为根节点集合、入口节点集合），如果在 G 中 存在一条 从 r 到节点 v 的路径，则称 v 是 可达 的；反之，如果 不存在任何一条 从 r 到 v 的路径，则称 v 是 不可达 的。基于可达或者不可达可以计算图中节点的支配和逆支配关系。

1.支配

支配 （dominance）：如果从 r 出发到达节点 w 的每一条路径都经过节点 v ，则称节点 v 支配节点 w 。我们使用符号Dom( w )来表示所有能支配节点 w 的节点所组成的集合。

根据支配关系的定义，对于一个可达的节点 w ，根集合 r 和节点 w 一定存在支配节点 w ，即Dom( w ) ⊇ { r , w }。以可达节点 w 为例，在支配关系中，支配节点 r 和 w 一般称为 无价值支配节点 （trivial dominator），而Dom( w ) - w 构成的节点集合称为节点 w 的完美支配节点（proper dominator）或者严格支配节点（Strictly Dominators，SDom）。因为在支配中还有半支配节点的概念，其缩写也为SDom，所以本书不使用严格支配节点的概念，统一使用完美支配节点）。如果存在节点 w 的支配节点 v ，满足 v ≠ w 且 v 被{Dom( w ) - w }中所有的节点支配，则称节点 v 为节点 w 的IDom（Immediate Dominator，直接支配节点）。

使用直接支配节点构造一棵树，称为 DT （Dominator Tree，支配树），其中节点表示有向图中的节点，边表示父节点直接支配子节点，当计算得到IDom时就可以轻易构造出支配树。支配树用于各种优化，例如优化循环、重新排序基本块、调度指令、构建控制流等都会涉及支配树的使用。

支配关系中另一个非常重要的概念是 DF （Dominance Frontier，支配边界）。在SSA的构造过程中使用支配边界确定φ函数的位置，在ADCE中使用逆支配边界来确定控制依赖，从而确定活跃变量。

当且仅当 X 支配 Y 的一个前驱节点，且 X 并不完美支配 Y 时，称 Y 是 X 的一个支配边界。通常 X 的 支配边界包含多个节点，是节点构成的集合 。

从支配边界的定义可以看出，对于节点 X 的支配边界 Y ，一定存在别的路径可以不经过 X 达到 Y （否则 X 就支配 Y ），这对 X 来说就意味着，支配边界 Y 一定是汇聚节点（join point）。根据支配边界的这一特性可以得到一个重要的结论：如果节点 X 中的活跃变量在支配边界 Y 包含的节点中也活跃，那么该活跃变量可能来自其他路径，即 Y 中的这些节点是该活跃变量的汇聚节点。在SSA的构造过程中，需要为汇聚节点插入额外的φ函数。因此在SSA的构造过程中，首先计算节点的支配边界，然后根据支配边界插入φ函数。假设 X 支配 P ，但 X 不支配 Y ₁ 和 Y ₂ ，则 Y ₁ 和 Y ₂ 都是 X 的支配边界，如图4-1所示。

图4-2为CFG及其对应的支配树，该图直观地演示了支配边界的概念。下面使用一个例子来演示如何计算支配关系。

图4-2a中CFG的入口节点是1，入口节点支配所有节点；节点2支配节点2、节点3、节点4和节点6，但是节点2并不支配节点7，因为节点7可以通过路径1→5→7到达；节点3、节点4、节点5、节点6以及节点7都只支配自己。基于上述描述，可以得到每个节点的支配、直接支配、支配边界集合结果，如表4-1所示。

基于表4-1可以非常容易地构造支配树，如图4-2b所示。

2.逆支配

逆支配 （post-dominance，也称为后支配）的定义是，如果从节点 w 出发到达每一个CFG出口（CFG可能有多个出口）的每一条路径都经过节点 v ，则称节点 v 逆支配节点 w 。使用符号Post-Dom( w )表示所有逆支配节点 w 的节点组成的集合。

仍然以图4-2a为例，基本块7逆支配基本块6、5、1，基本块6逆支配基本块2、3、4。得到逆支配树如图4-3所示。

逆支配树的计算方式和支配树的计算方式非常类似，通常是将CFG进行反转，但因为CFG可能存在多个出口，所以一般会引入一个虚拟的出口节点。虚拟出口节点连接原来所有的出口节点，这样构造的逆CFG就有一个唯一的出口，进而可以使用计算支配树的算法来计算逆支配树。

4.1.2 支配和逆支配含义解析

支配和逆支配在编译技术中是非常重要的概念，但是仅仅知道定义是不够的。下面通过简单的例子来进一步解析其作用。以图4-2a中的基本块2、3、4、6为例，在表4-1中可以看到基本块2支配基本块2、3、4、6，但是基本块3、4并不支配基本块6；在逆支配树中，基本块6逆支配基本块2、3、4、6，但是基本块3、4并不逆支配基本块6。结合图4-2b和图4-3可以得到基本块2支配基本块6、基本块6逆支配基本块2，说明到达基本块2的所有路径都经过基本块6。

假设有这样一个编译优化需求，将基本块2中的指令往下移动（假设往下移动后程序的语义逻辑仍然正确），因为基本块2有两条执行路径，所以为了保证程序逻辑的正确性，需要将基本块2的指令同时下移到基本块3和基本块4。但是这样指令下移后会导致代码量（code size）变多（基本块3、4包含了重复指令），所以在有些场景下并不符合优化预期。但是如果将指令下移到基本块6（而不是重复放置在基本块3、4），这样的下移则并不会增加代码量。基本块6的位置就可以通过支配和逆支配快速计算得到。

根据支配信息可以计算支配边界，因为支配边界是汇聚点，所以在汇聚点处插入φ函数。根据逆支配信息同样可以得到逆支配边界，逆支配边界是分叉点（逆支配信息是基于逆CFG计算得到），通常也称逆支配边界 控制依赖 节点。根据图4-2b所示的支配树得到节点3、4的 支配边界 为节点6，所以节点6便是插入φ函数的位置，如图4-4a所示。根据图4-3所示的逆支配树得到节点3、4的 逆支配边界 为节点2（说明节点2是分叉点），也称节点3、4 控制依赖 节点2，如图4-4b所示。

注意

控制依赖研究的是一个基本块的执行是否依赖于另一个基本块的执行。例如两个基本块A和B，基本块A能否控制基本块B的执行？如果基本块A支配基本块B，那么基本块A执行一定会导致基本块B也执行（根据支配定义，所有经过基本块A的路径都经过基本块B），所以基本块A不控制基本块B。但是如果基本块A有路径到达出口，而不用经过基本块B，则说明基本块B控制依赖基本块A，因此基本块A一定存在多个后继节点。基本块B只是其中一个后继节点（基本块A相当于一个控制是否执行基本块B的开关），并且基本块B不能逆支配基本块A（即从基本块A出发有其他路径达到出口），同时基本块A还应该是距离基本块B最近的节点。（应该将那些较远的节点视为控制基本块A的执行，而不应该视为控制基本块B的执行。）综合这些发现，逆支配边界信息刚好就是控制依赖信息。

4.2 支配树和支配边界的实现

LLVM中支配树的实现经历过2个版本，在LLVM 8.0以前是基于SLT（Simple Lengauer-Tarjan）算法，在2017年重新将SLT算法实现为Semi-NCA（SemiDominator-Nearest Common Ancestor）算法。其主要原因如下。

1）在静态构建DT时，在统计意义上，Semi-NCA较SLT算法有优势（有时会出现Semi-NCA时间复杂度更高的极端场景）。Google测试数据显示，如果在LTO（Link Time Optimization）场景中较多使用了DT，则性能提升会在2%～20%。

2）在动态增量构建DT时，Semi-NCA算法可以通过批操作合并多次插入和删除边的操作，以 O ( m * min{ k , n }+ k * n )的时间复杂度完成DT的构建（其中 m 是边的个数， n 是顶点个数， k 表示插入/删除边的次数）。

注意

Semi-NCA算法在2004年由Loukas Georgiadis等人提出（参见论文“Finding dominators revisited”）。增量构建DT是在2012年提出，并在2016年更新了该算法（参见论文“An Experimental Study of Dynamic Dominators”）。2017年，谷歌的工程师实现了该算法，并用其替换了SLT算法。

为什么增量构建DT如此重要？首先，在LLVM中有众多Pass都依赖DT，同时很多优化会修改CFG，这意味着DT发生了变化，所以必须在优化后重新构建DT或者增量构建DT。Google工程师在使用LTO针对一些基准测试（如Clang、SQLite等）验证时发现，重构DT耗时占比达到3%。而增量构建DT在过去数十年又一直是难点，传统的增量构建算法在插入一条边或者删除一条边时，重新构造支配树的复杂度为 O ( n )，由此可见 m 次修改的时间复杂度为 O ( mn )。而Georgiadis等人基于Semi-NCA算法，证明了 k 次边操作只需要 O ( m *min{ k , n } + k * n )的时间复杂度完成DT的增量构建，这对编译器来说非常具有吸引力。在论文中，增量构建DT依赖于DT的两个特性：父特性（parent property）和兄弟特性（sibling property）。其中父特性指的是DT中所有从一个可达顶点 v 出发的边，记为( v ， w )， t ( w )是 v 的祖先，其中 t ( w )是指 w 的父节点；兄弟特征指的是如果节点 v 和节点 w 是兄弟，则节点 v 不支配节点 w 。同时满足父特性和兄弟特性的树是DT。（相关证明可以参考论文“Dominator tree certification and divergent spanning trees”。）通过观察和证明，可以得出结论：边插入只会影响父特性的变化、边删除只会影响兄弟特性的变化，由此可知边插入和删除时哪些节点会受到影响，只需要在DT中更新这些受到影响的节点即可。增量更新依赖节点DFS遍历时的深度，而Semi-NCA天然会保存其深度，所以使用NCA可以快速计算得出受影响的节点以及更新后的支配关系。

另外，增量构建DT是批处理算法，当多次更新CFG时，每一次更新都是先更新CFG后更新DT，如果不想每次更新CFG，可以将多次DT的更新合并成批量进行（基于最初的CFG）。另外，谷歌的工程师还增强了原始论文中并未提及的逆支配树（Post Domianter Tree，PDT）的增量更新，原因是逆支配树中可能会遇到无限循环，需要对无限循环进行特殊处理，以便准确计算PDT，更多详细信息可以参考相关资料 。

本节主要关注SLT算法和Semi-NCA算法，关于支配树的其他构造算法以及性能比较可以参考4.3节扩展阅读的相关内容。

SLT算法和Semi-NCA算法都使用了半支配节点概念，但两个算法在构造IDom时有所不同。

4.2.1 半支配节点及相关概念

给定一个CFG，对图采用深度优先遍历，从而构成一个深度优先生成树（Depth-First-Spanning-Tree，DFST或DFS）。在遍历每一个节点时记录DFS遍历节点的序号，记为df _num 。对df _num 进行分析，并做以下定义。

1） 前向边 （forwarding edge）：在DFS中有一条从根节点出发的路径，且路径能从节点 v 到达节点 w 。如果df _num ( v )<df _num ( w )，并且节点 w 是 v 的后继节点，则称 v 到 w 有一个前向边。

2） 后向边 （back edge）：在DFS中有一条从根节点出发的路径，且路径可从节点 v 到达节点 w ，如果df _num ( v ) > df _num ( w )，并且节点 w 是 v 的祖先，则称 v 到 w 有一个后向边。

3） 树枝或交叉边 （cross edge）：在DFS中有一条从节点 v 到节点 w 的路径，如果df _num ( v ) > df _num ( w )，并且 w 既不是 v 的后继节点也不是 v 的祖先节点，则称 v 到 w 有一个树枝（此时 v 和 w 位于DFS的不同子树中）。

对于一个节点 U ，若存在节点 V 能够通过一些节点 V _i （不包含 V 和 U ）到达节点 U ，且对于任意节点 V _i 都有df _num ( V _i ) > df _num ( V )，在所有满足条件的 V 中，能使df _num ( V )最小的 V 称为 U 的半支配节点，记为sdom[ U ]= V 。半支配节点的形式化描述为：

sdom( v )=min{ v ₀ |存在路径 v ₀ , v ₁ ,..., v _k = v ，使得df _num ( v _i ) > df _num ( v )，当0< i < k 时成立}

在CFG的DFS访问中，如果有一个边( t ， w )，并且df _num ( t ) > df _num ( w )，说明边( t ， w )不是前向边，这意味着 w 是一个汇聚点（除了前向边外，还有一个交叉边同时达到节点 w ），也意味着在由 前向边 构成的路径（从更早遍历的节点 s 到 w ）中一定有一个分叉点 u ，使得从分叉点 u 起，有一条路径到达节点 w ，此时称 u 为 w 的半支配节点，如图4-5所示。

注意

s 到 w 路径中的分叉点 u 可能并不支配 w （即并不属于Dom( w )），所以称 u 为 w 的半支配节点。例如图4-6a为CFG图，图4-6b中蓝色路径是DFS的边。

在图4-6a中，节点0、1、2、3、5的sdom节点和IDom节点相同，分别是0、0、1、0、0，可以通过sdom公式计算得到。而对节点4来说，从图4-6b中很容易找到对应的sdom(4)=1（节点1有分叉节点4，它满足半支配节点定义），但是节点1并 不支配 节点4（从节点5可以达到节点3再到节点4，所以节点1并不支配节点5）。

小结： 半支配节点隐含了sdom( n )= u ，表示 u 位于前向边构成的一条路径中，而 n 的直接支配节点也一定存在于前向边构成的路径中。但是 u 可能不支配 n ，所以 u 是IDom( n )的候选节点，如果 u 不是IDom( n )，说明在 u 之上可能还有分叉路径，所以只需要找到分叉点即可（这是一个递归过程）。

4.2.2 LT算法和Semi-NCA的差异

现在寻找支配分叉点 u （ u 是 w 的半支配节点，记为sdom）的一个节点 n ， n 是Dom( w )中df _num 最大的节点。因为 n 支配节点 w ，所以 n 是Dom( w )中的一个元素，并且df _num 最大，说明节点 n 距离节点 w 最近，那么 n 就是 w 的直接支配节点。又因为IDom( w )此时也是未知的，所以需要进一步根据以下规则计算。（LT和Semi-NCA区别就是计算IDom的方法不同。）

对LT算法来说 ： 。

在LT算法中，如果sdom( w )等于sdom( u )，则说明此时 u 就是 n 的直接支配节点，即sdom( w )等于 u ，故有IDom( w )等于sdom( w )；如果sdom( w )不等于sdom( u )，则说明还需要进一步向上递归查找，查找sdom( u )、sdom( w )中df _num 小的节点的直接支配节点，即 w 的直接支配节点，在递归实现中一般将 w 更新为sdom( w )， u 更新为sdom( u )即可。

对Semi-NCA算法来说 ：IDom( v )=NCA(parent( v ),sdom( w ))，其中NCA是指两个节点的公共节点，parent( v )是 v 的父节点。

在Semi-NCA算法中，假设 w 的父节点为 v ，只需要找到 v 和sdom( w )的一个公共节点，这个公共节点就是 w 的直接支配节点。

仍然以图4-6b的节点4为例，求节点4的直接支配节点，此时LT和Semi-NCA区别在于：

1）LT算法：比较sdom(1)和sdom(4)是否相同，如果不相同则继续比较，最后得到节点0是节点4的直接支配节点。

2）Semi-NCA算法：寻找节点3和sdom(4)的公共节点，即节点0。

4.2.3 支配边界的实现

虽然可以根据定义可以直接求解支配边界，但是算法的复杂度比较高，所以LLVM在实现时采用了论文“A linear time algorithm for placing φ-nodes” 的算法，该算法的时间复杂度为 O ( n )。这个算法的思想和实现都不复杂，它是以支配树为基础构造DJ-Graph（在支配树的基础上加上Join边，支配树中的边称为D-edge），然后基于DJ-Grapch直接计算支配边界。

Join边的定义 ：假设 x → y 是CFG上的一条边（这里是指直接边），如果 x 不是 y 的直接支配节点（ x ≠idom( y )），则称边 x → y 是一条Join边。

根据构造的DJ-Graph可以得到以下信息。

1）对Join边来说，假设边 x → y ，则 y 是 x 的支配边界集合元素，同时 y 也是 x 祖先的支配边界集合元素。

2）如果 y 是 x 的支配边界，可以发现 y 在支配树的层次小于等于 x 的层次（支配树的根节点层次为0，可以参考图4-2b）。

3）如果 y 是 x 的支配边界，当且仅当 x 存在一个子树subTree( x )记为 z ，则 z → y 是Join边，且 y 的层次小于等于 x 的层次。

由此可得到支配边界的计算方法，如代码清单4-1所示：

代码清单4-1 支配边界计算方法

4.3 扩展阅读：支配树相关小课堂

支配树在编译优化中使用非常广泛，其研究历史也非常久远，本节首先对求解支配树的不同算法进行介绍和比较，然后介绍如何快速判断两个节点是否存在支配关系。

4.3.1 支配树构造算法及比较

本节内容主要来自Henrik于2016年的论文“Algorithms for Finding Dominators in Directed Graphs”，更多详情可以参考原始论文 。

1.定义法

根据支配树的定义，对于图 G ，如果从 s 到 w 的任意一条路径都经过节点 v ，则 v 支配 w ，那么可以得到结论：如果从图中删除节点 v ， s 不能到达节点 w ，那么节点 v 支配节点 w 。由此可以得到算法步骤如下。

1）依次删除图中的顶点 v _i 。

2）遍历更新后的图，如果从 s 出发无法到达顶点的集合记为{ w ₁ , w ₂ ,..., w _k }，则 v _i 支配{ w ₁ , w ₂ ,..., w _k }。

3）根据支配关系构造支配树。

2.数据流分析法

根据CFG建立的数据流方程，迭代求解每个节点的支配节点。假定IN[ B ]为基本块 B 入口处的支配节点集合，OUT[ B ]为基本块 B 出口处的支配节点集合，则支配节点的数据流方程的定义如下：

1）OUT[Entry]={Entry}

2）OUT[ B ]=IN[ B ]∪{ B }, B ≠Entry

3） , B ≠Entry

这是一个前向数据流方程。因为数据流方程是单调的，所以通过迭代可以得到不动点。根据数据流方程的定义得出：OUT[ B ]中的节点都支配 B ，即OUT[ B ]就是Dom( B )。

该迭代算法需要存储每个顶点Dom，若顶点个数为 n ，则每轮迭代计算所有节点交集的总时间为 O ( mn )。由于算法最多迭代 n - 1次，故而总的迭代时间复杂度是 O ( mn ² )，空间复杂度为 O ( n ² )。

除了上述的数据流方程外，还有其他研究者构建了不同的数据流方程，不断优化基础数据流方程。例如可以直接基于IDom来构建，即Dom( v )={ v }∪IDom( v )∪IDom(IDom( v ))∪IDom(IDom...( v ))。其中IDom可以通过NCA算法来计算，总的迭代时间复杂度是 O ( mn ² )，空间复杂度为 O ( m + n )。虽然时间复杂度不变，但是实际效率更高。

3.支配树小结

加上4.2节中介绍的SLT算法和Semi-NCA算法，共有4种计算支配树的算法，它们的时间和空间复杂度如表4-2所示，表中 m 表示边的数目， n 表示顶点个数。

当然支配算法还有很多可以挖掘的细节，但是Semi-NCA算法看起来是当前比较稳定的最优选择算法。

4.3.2 如何快速判断任意两个节点的支配关系

假设已知控制流图的DT，如何快速判断任意两个节点 x 和 y 是否存在支配关系？

判断 节点 之间是否存在支配关系在整个编译优化中的常见操作。在LLVM的实现中有两种判断方法供读者参考。

1.第一种方法

由于已知支配树，故而可以通过遍历支配树进行判断。为支配树的每一层设置一个高度，根节点的高度为0，叶子节点高度最大。根据支配的特性，可得到以下事实。

1）如果节点 x 支配节点 y ，那么 x 的高度一定小于等于 y 的高度。

2）如果 x 的高度等于 y 的高度，且节点 x 等于节点 y ，则 x 支配 y 。

3）如果 x 的高度小于 y 的高度，且节点 x 等于节点 y 的IDom，则 x 支配 y 。

由上述事实可以得到第一种快速判断任意两个节点支配关系的算法，步骤如下。

1）计算节点 x 和 y 的高度，高度小的节点可能会支配另一个节点。假设 x 的高度小（高度记为 h _x ），节点 y 的高度大。

2）从DT中遍历节点 y 的IDom，直到IDom的高度小于或等于 h _x 。

3）判断IDom和 x 是否相等，如果相等则说明 x 支配 y ，否则 x 不支配 y 。

2.第二种方法

第一种方法总是需要遍历IDom，然后访问高度数据，最后再判断。对高性能场景来说效率略低，故而LLVM设计了第二种方法，具体如下：首先对DT重新进行DFS遍历，同时为每个节点增加2个属性，分别为DFSNumIn和DFSNumOut，其中DFSNumIn记录的是对DT进行DFS遍历时第一次被访问节点的序号，而DFSNumOut记录的是对DT进行DFS遍历时最后一次被访问节点的序号，可以得到如下结论。

1）父节点的DFSNumIn一定小于子节点的DFSNumIn（DFS遍历时总是先到达父节点，然后才能访问子节点）。

2）左边兄弟节点的DFSNumIn一定小于右边兄弟节点的DFSNumIn（DFS遍历时总是先达到左边的节点）。

3）子节点的DFSNumOut一定小于父节点的DFSNumOut（DFS遍历时总是要求先处理完子节点，再处理父节点）。

4）左边兄弟节点的DFSNumOut一定小于右边兄弟节点的DFSNumOut（DFS遍历时总是先完成左边节点的处理）。

综合这4个条件可以快速判断 x 是否支配 y ，如果同时有：① x .DFSNumIn小于等于 y .DFSNumIn；② x .DFSNumOut大于等于 y .DFSNumOut。则 x 支配 y 。假设有CFG如图4-7a所示，经过DFS遍历后每个节点的DFSNumIn和DFSNumOut如图4-7b所示。

通过上述规则可以快速判断4个节点的支配关系。例如节点 a 的DFSNumIn（为1）小于节点 b 、 c 、 d 的DFSNumIn（分别为2、3、5），同时 a 的DFSNumOut（为8）大于节点 b 、 c 、 d 的DFSNumOut（分别为7、4、6），则节点 a 支配节点 b 、 c 、 d 。根据这一方法，可以得到节点之间的支配关系如表4-3所示。表中每个格子表示每行节点是否支配每列节点，如果行节点支配列节点用√表示；表中节点用类似 a (DFSNumIn,DFSNumOut)的方式表示，例如 a (1,8)表示节点 a 的DFSNumIn是1，DFSNumOut是8。

4.4 本章小结

本章主要介绍支配分析相关内容。介绍了支配、支配树、逆支配、逆支配树等基础知识，简单探讨了LLVM中支配树和支配边界的演化历程。4.3节比较了4种求解支配树算法的差异。本章最后对LLVM如何快速判断两个节点的支配关系进行了介绍。 SE0ZoYfYtX3CMKztS7rWp0lGR/QGQUP7f/P/a8jlPoaNlwELKCpq2VZ6+8otF7mq

第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章的内容和相关资料。 SE0ZoYfYtX3CMKztS7rWp0lGR/QGQUP7f/P/a8jlPoaNlwELKCpq2VZ6+8otF7mq