之前写 canonicalization 对循环的概念直接略过了，没做展开，循环在日常开发中使用还是挺广泛的，这里简单介绍 LLVM 中循环的概念。

1、基本概念

在 LLVM 当中，会使用 LoopInfo (用于持有循环信息的核心分析) 在 CFG(control-flow graph，控制流图，节点是 Basic Block 基本块) 来检测出循环。

1
2
3
4
5

LoopInfo &LI = FAM.getResult<LoopAnalysis>(F);   
// `LI` contains ALL `Loop` instances in `F`  
for (Loop *LP : LI) {     
    // Working with one of the loops, `LP`
}

关于 Loop，有几个术语需要解释一下:

  • Header Block，循环的入口(entry)，支配循环当中所有的节点，也是回边所指向的节点。
  • Entering Block，不是循环的一部分，但有边可以进入循环的节点。
  • Pre-Header Block，虽然不是循环的一部分，但它代表 header block 的唯一前继节点(即只有唯一一个 Entering Block，且它唯一的边是指向 Header)。用于方便进行循环转换(比如把重复计算放到循环外，没有这个术语概念的话，就得把重复的指令写到循环的每一个前继节点)。
  • Back Edge，从某个节点回到 header block 的控制流边，循环起码会有一条，可以有多条。
  • Latch Block，这是 back edge 的出边节点。
  • Exiting Block，具有 exit edge 的节点，在循环内指向循环外的出边节点。
  • Exit Edge，由循环内控制流指向跳到循环外的边。
  • Exit Block，跳出到循环外的节点，不是循环的一部分，一个循环可以有多个 exit block。

组成一个循环的核心，要有 header block、back edge、latch block。

一个最小型的循环如下图，即只有一个基本块节点(可以是死循环，这时候就不会是 exiting block)：

1.1、示例

1
2
3

for (int i = 0; i < 128; ++i)
  for (int j = 0; j < 128; ++j)
    body(i,j);

使用 opt -enable-new-pm=0 -analyze -loops loop.ll 可以输出循环相关信息：

1
2
3

Printing analysis 'Natural Loop Information' for function 'main':
Loop at depth 1 containing: %4<header><exiting>,%7,%8,%17,%18<latch>,%11,%14
	Loop at depth 2 containing: %8<header><exiting>,%11,%14<latch>

可以用 opt -enable-new-pm=0 -dot-cfg 和 dot -Tpng -o main.png main.dot 生成 CFG 图对照着看：

2、canonical loop

一个 Loop 实例如果有较好的基础属性可以简便地进行循环转换的话，则称之为 canonical loop。而 LLVM 当中有两种 canonical loop 的格式，分别是 simplified 格式和 rotated 格式(关于 canonical 的概念可以翻翻我之前写的文章)。

一开始是大部分循环的 pass 都需要依赖 simplified 格式，不过也分出了派系，一些 pass 则需要 rotated 格式来进行分析，rotated 格式是可转换的，官网对于 rotated 格式还标着双引号为 “More Canonical” Loops。

2.1、simplified

simplified 格式有以下属性：

  • 一个 pre-header block。
  • 只有一条 back edge (因此也只有一个 latch block)。
  • exit blocks 的前继节点都来源于循环当中，也就是说，header block 支配所有的 exit blocks。

可以通过对原始的循环执行 LoopSimplfyPass (-loop-simplify)方法得到 simplified 格式的循环，但首先应该使用 Loop::isLoopSimplifyForm 检查是否满足要求。

只有一条 back edge，我们可以很容易地分析出哪些变量是用于循环迭代的(这种变量称之为 induction variable，比如 for(int i=0; i<9; ++i) 里面的变量 i，可以知道循环迭代的次数)。而因为每个 exit blocks 都被循环内的节点所支配，可以很容易地把一些不影响其他控制流路径的指令，放到循环的外面上头。

2.2、rotated

使用 LoopRotationPass 可以进行转换，使用 Loop::isRotatedForm 判断是否能进行转换。rotated 格式基本上是把一个任意的循环转换成 do-while 的结构。

1
2
3
4
5
6
7
8
9

// `N` is not a constant 
for (int i = 0; i < N; ++i){…}

// 转换
if (i < N) { // loop guard，进入循环前的判断，这个很重要
    do {
        ++i;
    } while(i < N);
}

除了多出 loop guard 之外，还有 header、latch、exiting 块节点结合在一起，这样可以保证这个节点里的所有指令拥有一样的执行次数(execution count)，对于进行循环向量化(loop vectorization)很有帮助。

为什么这里会多出 loop guard？官网有举例说明：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

// 原版
for (int i = 0; i < n; ++i) {
  auto v = *p;
  use(v);
}

// 假设从 p 读取的是常量，那么只需要一次读取操作就够了，放到循环外
auto v = *p;
for (int i = 0; i < n; ++i) {
  use(v);
}

// 但是上面的操作是有问题的，如果 n <= 0，那循环体根本不应该执行
// 所以才插入保护
if (n > 0) {  // loop guard
  auto v = *p;
  for (int i = 0; i < n; ++i) {
    use(v);
  }
}

// 最后转换成 do-while 形式，还可以节省一次 n 和 0 的比较

把不变部分移出循环体通常不是 LoopRotate 做的，而是由其他 pass 像 Loop-Invariant Code Motion (-licm) 来完成。

3、Loop Pass

除了 Module 和 Function 可以编写 Pass 之外，Loop 也是支持的，但它的 run 方法签名不太一样。

1
2
3
4
5

PreservedAnalyses run(Loop &LP, LoopAnalysisManager &LAM,
                        LoopStandardAnalysisResults &LAR,
                        LPMUpdater &U);
// 第三个参数提供了分析结果数据
// 第四个参数用来告知 PassManager 可能会产生的新循环，这样新循环就会进入分析队列里

对于嵌套的循环(nested loop)，通常会描述成树结构，称之为 loop tree(循环树)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

// 实际上我们对于嵌套循环的遍历，是需要按层来获取的
// `LP` has the type of `Loop&`
for (Loop *SubLP : LP) {   
    // `SubLP` is one of the sub-loops at the next layer 
}

// 如果想一次性遍历完层级下的所有子循环，可以使用 Loop::getLoopsInPreorder()
// 或者采用前面说到的 GraphTraits 提供的方法
// `RootL` has the type of `Loop*`
for (Loop *L : depth_first(RootL)) {   
    // Work with `L`
}

// LoopNest 封装了所有的子循环 API 操作接口
LoopNest &LN = LAM.getResult<LoopNestAnalysis>(LP, LAR);
// getOutermostLoop()/getInnermostLoop() 获取最外层/最内层循环
// areAllLoopsSimplifyForm()/areAllLoopsRotatedForm() 判断所有循环的格式

// getPerfectLoops(…) 所谓 perfecr loop 即嵌套的循环之间没有 gap
// 对于做循环展开非常有帮助
// Perfect loops 
for(int i=…) {   
    for(int j=…){…} 
} 
// Non-perfect loops 
for(int x=…) {   
    foo();   
    for(int y=…){…} 
}

// 获取 induction variable
// getCanonicalInductionVariable 用在从 0 开始，每次迭代增加 1
// getInductionVariable 可以应对大多复杂情况，但需要参数 ScalarEvolution 实例
// ScalarEvolution 是一个追踪 values 变化的框架
// Loop::getInductionDescriptor 可以获取初始值、变化幅度(step value)、更新的指令
// Loop::getBounds 可以获取初始值、变化幅度，还有结束值

参考