The For Structure

Code Block

多数通用语言的 for loop 具备以下的结构：

1
2
3
for (InitStmt; Condition; IncStmt) {
  // code block to be executed
}

注：for range 是语言层面对于迭代器封装的语法糖。

结合 for 的上下文，可以将代码按以下块进行划分：

1
for.before for{for.init for.cond for.body for.inc } for.after

其中 for.init 通常亦会提取到 for loop 外进行，其唯一的区别在于作用域是否扩展到 for.after，所以可以进一步划分：

1
{for.before for.init} for.cond for.body for.inc for.after

Control Flow

对于一个 for loop，可以简单的看做：

1
2
3
4
5
6
for.head
  [jmp for.tail]
  [jmp for.head | jmp for.tail]
  [jmp for.head | jmp for.tail]
  ...
for.tail

jmp for.head: 对应于 continue，或单次循环执行完毕
jmp for.tail：对应于 break，或 for.cond 为 false

LLVM Loop Terminology (and Canonical Forms) 中对 loop 控制流的结构进行了定义：

header：代码由循环外进入循环的唯一入口，header 将支配循环的所有节点。未优化时，对应于 for.cond 块
preheader：唯一进入循环(或外部跳转到 header)的代码块；无论有1个或多个进入循环的基础块，都称之为 entering block 或 loop predecessor
latch：跳转到 header 的代码块(jmp for.head)
backedge：latch 到 header 的边
exiting：跳转出循环的代码块(jmp for.tail)

Loop Simplify Form

Loop Simplify Form 具备以下特征：

仅有一个 preheader
仅有一个 latch，即仅有一个 backedge
不允许 exiting 存在循环外的 predecessor，即不应有循环外的 block 直接跳转到 exiting block，即所有 exiting 必须被 header 所支配

LCSSA(Loop Closed SSA)

Loop Closed SSA：对于 SSA 形式的循环，定义在循环中的值仅能在循环内使用。

实现上，通过在循环外添加冗余的 phi 节点，指向循环中的值，这样当发生循环拷贝等优化行为时，只要修改循环外的 phi 节点即可。

LLVM Loop vs Function

若将循环体映射到函数域：

Control Flow：header 相当于函数打头的基础块，并且包含了函数的形参，循环变更的值必须在 header 处收敛
Loop Simplify Form：仅有一个 preheader 约定了循环外的值循环内使用时，必须收敛一处，就像调用函数传递的实参一样
Loop Simplify Form：仅有一个 latch 约定了循环结构为最简单的单环，如存在 continue 的场景，将先跳转到 latch
LCSSA：约定了循环内的值循环外使用时，必须收敛一处，就像函数返回值一样。

Simple For Loop in LLVM IR

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
const int cnt = 10;
int sum(int i, int j) __attribute__((noinline)) {
  return i + j;
}

int loop() {
  int s = 3;
  for (int i = 1; i < cnt; ++i) {
    s = sum(s, i);
  }
  return s;
}

编译生成 llvm ir：

1
clang++ -S -emit-llvm loop.cpp -o loop.ll

 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
; Function Attrs: mustprogress noinline nounwind ssp uwtable
define i32 @_Z4loopv() #0 {
entry:
  %s = alloca i32, align 4
  %i = alloca i32, align 4
  store i32 3, i32* %s, align 4
  store i32 1, i32* %i, align 4
  br label %for.cond

for.cond:                                         ; preds = %for.inc, %entry
  %0 = load i32, i32* %i, align 4
  %cmp = icmp slt i32 %0, 4
  br i1 %cmp, label %for.body, label %for.end

for.body:                                         ; preds = %for.cond
  %1 = load i32, i32* %s, align 4
  %2 = load i32, i32* %i, align 4
  %call = call i32 @_Z3sumii(i32 %1, i32 %2)
  store i32 %call, i32* %s, align 4
  br label %for.inc

for.inc:                                          ; preds = %for.body
  %3 = load i32, i32* %i, align 4
  %inc = add nsw i32 %3, 1
  store i32 %inc, i32* %i, align 4
  br label %for.cond, !llvm.loop !5

for.end:                                          ; preds = %for.cond
  %4 = load i32, i32* %s, align 4
  ret i32 %4
}

Simple Loop Full Unroll Route - Compiled with O2

通过跟踪 O2 级别的编译优化日志，梳理出 loop full unroll 的主要 pass：

SROA
LoopRotate
LoopUnrollFull
GVN

1
clang++ -S -emit-llvm -O2 -mllvm -print-after-all -o loop.O2.ll loop.cpp

Pass: sroa(Scalar Replacement of Aggregates)

用标量寄存器替换函数作用域内分配的聚合对象(array, struct)。

该 pass 执行具有两个特征：

寄存器替换 alloca 的对象
生成 phi 节点

1
opt -S -debug-pass-manager -passes="sroa" < loop.ll

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
define i32 @_Z4loopv() #0 {
entry:
  br label %for.cond

for.cond:                                         ; preds = %for.inc, %entry
  %s.0 = phi i32 [ 3, %entry ], [ %call, %for.inc ]
  %i.0 = phi i32 [ 1, %entry ], [ %inc, %for.inc ]
  %cmp = icmp slt i32 %i.0, 4
  br i1 %cmp, label %for.body, label %for.end

for.body:                                         ; preds = %for.cond
  %call = call i32 @_Z3sumii(i32 %s.0, i32 %i.0)
  br label %for.inc

for.inc:                                          ; preds = %for.body
  %inc = add nsw i32 %i.0, 1
  br label %for.cond, !llvm.loop !5

for.end:                                          ; preds = %for.cond
  ret i32 %s.0
}

Pass: loop-rotate

将 for 循环转换为 do…while 循环，如：

1
2
3
  for (int i = 0; i < n; i += 1) {
    // Loop body
  }

转换为：

1
2
3
4
5
6
7
  int i = 0;
  if (n > 0) {
    do {
      // Loop body
      i += 1;
    } while (i < n);
  }

参考 wikipedia: Loop inversion 该优化可以通过改善指令流水从而提升性能，同时也会将循环不变量外提的优化变得更加安全。

从 sroa pass 结果来看，循环中仍存在两个无法消除的跳转：for.cond -> [for.body | for.end]，for.inc -> for.cond。

经过反转之后，如下所示，就只剩下 for.inc -> [for.body | for.end]，而 for.inc -> for.cond 被消除，这是后续优化变得更加简单

1
opt -S -debug-pass-manager -passes="sroa,loop-rotate" < loop.ll

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
define i32 @_Z4loopv() #0 {
entry:
  br label %for.body

for.body:                                         ; preds = %entry, %for.inc
  %i.05 = phi i32 [ 1, %entry ], [ %inc, %for.inc ]
  %s.04 = phi i32 [ 3, %entry ], [ %call, %for.inc ]
  %call = call i32 @_Z3sumii(i32 %s.04, i32 %i.05)
  br label %for.inc

for.inc:                                          ; preds = %for.body
  %inc = add nsw i32 %i.05, 1
  %cmp = icmp slt i32 %inc, 4
  br i1 %cmp, label %for.body, label %for.end, !llvm.loop !5

for.end:                                          ; preds = %for.inc
  %s.0.lcssa = phi i32 [ %call, %for.inc ]
  ret i32 %s.0.lcssa
}

Pass: loop-unroll-full

Loop Unrolling 将循环次数降低为原来的1/n，循环体单次处理原来n倍的任务，从而降低循环次数提升循环体内的并发度。当循环次数降低到1时，循环消除，称之为全展开(Loop Full Unroll)。

1
opt -S -debug-pass-manager -passes="sroa,loop-rotate,loop-unroll-full" -unroll-count=4 < loop.ll

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
define i32 @_Z4loopv() #0 {
entry:
  br label %for.body

for.body:                                         ; preds = %entry
  %call = call i32 @_Z3sumii(i32 3, i32 1)
  br label %for.inc

for.inc:                                          ; preds = %for.body
  %call.1 = call i32 @_Z3sumii(i32 %call, i32 2)
  br label %for.inc.1

for.inc.1:                                        ; preds = %for.inc
  %call.2 = call i32 @_Z3sumii(i32 %call.1, i32 3)
  br label %for.inc.2

for.inc.2:                                        ; preds = %for.inc.1
  ret i32 %call.2
}

循环全展开的必要条件：

通过 for.cond 可以在编译期计算出循环次数，循环次数在限定范围内(unroll count)
计量循环体的大小，并评估循环展开的开销，全展开的开销在限定范围内(const threshold)
必须是 Loop Simplify Form
必须是 LCSSA
循环体是否可安全复制，如循环体内不存在不可复制的指令

Pass: gvn(Global Value Numbering)

GVN-PRE：Global Value Numbering and Partial Redundancy Elimination

https://llvm.org/doxygen/GVN_8cpp_source.html: 2481

1
2
// Merge unconditional branches, allowing PRE to catch more
// optimization opportunities.

1
opt -S -debug-pass-manager -passes="sroa,loop-rotate,loop-unroll-full,gvn" -unroll-count=4 < loop.ll

1
2
3
4
5
6
7
define i32 @_Z4loopv() #0 {
entry:
  %call = call i32 @_Z3sumii(i32 3, i32 1)
  %call.1 = call i32 @_Z3sumii(i32 %call, i32 2)
  %call.2 = call i32 @_Z3sumii(i32 %call.1, i32 3)
  ret i32 %call.2
}

Simple Loop Full Unroll Route - Simplify

Pass: mem2reg

经分析，sroa pass 仅简化了 for loop 的结构，消除了 alloca 指令，用 mem2reg pass 或更为合适。

1
opt -S -debug-pass-manager -passes="mem2reg" < loop.ll

转换结果与 sroa 相同：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
define i32 @_Z4loopv() #0 {
entry:
  br label %for.cond

for.cond:                                         ; preds = %for.inc, %entry
  %i.0 = phi i32 [ 1, %entry ], [ %inc, %for.inc ]
  %s.0 = phi i32 [ 3, %entry ], [ %call, %for.inc ]
  %cmp = icmp slt i32 %i.0, 4
  br i1 %cmp, label %for.body, label %for.end

for.body:                                         ; preds = %for.cond
  %call = call i32 @_Z3sumii(i32 %s.0, i32 %i.0)
  br label %for.inc

for.inc:                                          ; preds = %for.body
  %inc = add nsw i32 %i.0, 1
  br label %for.cond, !llvm.loop !5

for.end:                                          ; preds = %for.cond
  ret i32 %s.0
}

Pass: loop-unroll-full

1
opt -S -debug-pass-manager -passes="mem2reg,loop-unroll-full" < loop.ll

 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
37
38
39
define i32 @_Z4loopv() #0 {
entry:
  br label %for.cond

for.cond:                                         ; preds = %entry
  br label %for.body

for.body:                                         ; preds = %for.cond
  %call = call i32 @_Z3sumii(i32 3, i32 1)
  br label %for.inc

for.inc:                                          ; preds = %for.body
  br label %for.body.1

for.body.1:                                       ; preds = %for.inc
  %call.1 = call i32 @_Z3sumii(i32 %call, i32 2)
  br label %for.inc.1

for.inc.1:                                        ; preds = %for.body.1
  br label %for.body.2

for.body.2:                                       ; preds = %for.inc.1
  %call.2 = call i32 @_Z3sumii(i32 %call.1, i32 3)
  br label %for.inc.2

for.inc.2:                                        ; preds = %for.body.2
  br i1 false, label %for.body.3, label %for.end

for.body.3:                                       ; preds = %for.inc.2
  %call.3 = call i32 @_Z3sumii(i32 %call.2, i32 4)
  br label %for.inc.3

for.inc.3:                                        ; preds = %for.body.3
  unreachable

for.end:                                          ; preds = %for.inc.2
  %s.0.lcssa = phi i32 [ %call.2, %for.inc.2 ]
  ret i32 %s.0.lcssa
}

未经过 loop-rotate 转换，冗余的分支节点明显多了很多:

1
2
3
4
5
6
for.body:                                         ; preds = %for.cond
  %call = call i32 @_Z3sumii(i32 3, i32 1)
  br label %for.inc

for.inc:                                          ; preds = %for.body
  br label %for.body.1

而且产生了一个 unreachable 的循环边界(for.body.3, for.inc.3)：

1
2
3
4
5
6
7
8
9
for.inc.2:                                        ; preds = %for.body.2
  br i1 false, label %for.body.3, label %for.end

for.body.3:                                       ; preds = %for.inc.2
  %call.3 = call i32 @_Z3sumii(i32 %call.2, i32 4)
  br label %for.inc.3

for.inc.3:                                        ; preds = %for.body.3
  unreachable

注：推测 unreachable 循环边界的产生是由于 llvm 中存在 DCE passes，所以 loop-unroll-full 在实现上未额外处理边界。

Pass: simplifycfg

gvn pass 虽然可以消除 br 直接跳转，但对于 br const condition 似乎无能为力。最后遇到的问题其实时候对于冗余或无效指令的清理，simplifycfg 比较合适。

Simplify the CFG 执行 DCE 以及基础块合并：

移除无前驱的基础块
如果一个基础块有唯一的前驱，是前驱的唯一后继，则将当前基础块合并到前驱基础块
如果一个基础块有唯一的前驱，消除其中的 phi 节点
消除仅包含非条件跳转的基础块

1
opt -S -debug-pass-manager -passes="mem2reg,loop-unroll-full,simplifycfg" -unroll-count=4 < loop.ll

1
2
3
4
5
6
7
define i32 @_Z4loopv() #0 {
entry:
  %call = call i32 @_Z3sumii(i32 3, i32 1)
  %call.1 = call i32 @_Z3sumii(i32 %call, i32 2)
  %call.2 = call i32 @_Z3sumii(i32 %call.1, i32 3)
  ret i32 %call.2
}

Reference

[1] LLVM Loop Terminology (and Canonical Forms). https://llvm.org/docs/LoopTerminology.html

[2] LLVM’s Analysis and Transform Passes. https://llvm.org/docs/Passes.html#sroa-scalar-replacement-of-aggregates

[3] How LLVM Optimizes a Function. https://blog.regehr.org/archives/1603

[4] The new intraprocedural Scalar Replacement of Aggregates. https://gcc.gnu.org/wiki/summit2010?action=AttachFile&do=get&target=jambor.pdf

[5] GVN-PRE. https://gcc.gnu.org/wiki/GVN-PRE

[6] Loop unrolling. https://en.wikipedia.org/wiki/Loop_unrolling

LLVM Loop Optimization - Full Unroll

Contents

The For Structure

Code Block

Control Flow

Loop Simplify Form

LCSSA(Loop Closed SSA)

LLVM Loop vs Function

Simple For Loop in LLVM IR

Simple Loop Full Unroll Route - Compiled with O2

Pass: sroa(Scalar Replacement of Aggregates)

Pass: loop-rotate

Pass: loop-unroll-full

Pass: gvn(Global Value Numbering)

Simple Loop Full Unroll Route - Simplify

Pass: mem2reg

Pass: loop-unroll-full

Pass: simplifycfg

Reference