optimization.md

Optimization

Pass Manager

PassManager 是 SIR、IR、MIR 共用的模块。他们分别根据其数据结构特化通用的 PassManager

Analysis Manager

主要管理 Analysis Pass 的缓存与生命周期, 使用 PreservedAnalyses 跟踪分析结果有效性。

• 通过 getResult() 获取缓存结果，避免重复计算
• 通过 getFreshResult() 强制重新计算

Transform Pass Manager

按顺序执行加入到其中的 Pass，并且：

• 记录每个 Pass 的执行状态（时间，改动，指令数量）
• 汇总 Pass 返回的 PreservedAnalyses

Fixed-Point Transform Pass Manager

同 Transform Pass Manager，但是重复执行直到没有变化

Dependency

我们的 PassManager 的设计主要参考了 LLVM 的 NewPassManager，但在实现上做了极大的简化。这样轻量级结构更适应我们有限的 Pipeline。
其中简化的主要部分在于我们手动处理 Analysis Pass 之间的依赖关系：

• 每个 Transform Pass 可能使一个或多个 Analysis Pass 失效
• 当 Transform Pass 使某个 Analysis Pass 失效时，必须手动将所有依赖该 Analysis Pass 的其他分析 Analysis Pass 全部 invalidate

如

graph LR
    TA(TransformA) -- invalidate --> AA(AnalysisA)
    TA -- invalidate --> AB(AnalysisB)
    AA -- used by --> AB

Loading

Transform A 使 Analysis A 失效，同时 Analysis B 又依赖于 Analysis A。则在 Transform A 中必须同时将 Analysis A 和 Analysis B invalidate。
这样做会导致增加 Analysis Pass 时可能会需要修改已有的 Transform Pass，但是考虑到我们的 pipeline 较为有限，这样也能满足我们的需求。而且这样可以简化 撰写 Analysis 的步骤，且依赖关系清晰明确，便于调试。

SIR

Intro

SIR 是 AST 与 IR 之间的中间表示。SIR 无基本块，If-else/While/For 均由相关辅助指令（IFInst/WhileInst /...）实现，这样一来，编写前端时无需考虑 SSA 构造和基本块划分。

Structure

SIR 中由于存在嵌套的 If-else/While/For，导致普通的遍历通常不能很好的操作 SIR。因此 SIR 上大多数 pass 是借助 Visitor 模式实现的。
目前 SIR 上有两类 Visitor：

• 普通的 Visitor：仅遍历，不携带额外信息，通常和直接遍历 nested_insts() 效果一样
• 带有上下文的 ContextVisitor：携带额外的上下文信息，如上一层指令的指针，遍历中指令的迭代器，遍历深度等

Analysis Passes

Instruction Dominance Analysis

分析指令的支配关系。
这个 Analysis 先将 SIR 划分为 PseudoCFG，后在 PseudoBasicBlock 上进行通用的支配分析。 目前该 analysis 主要被 Early Mem2Reg 使用。

Affine Alias Analysis

关于 For 的 Alias Analysis。
我们将 Memory Access 分为 Scalar Access 和 Array Access。其中 Array Access 如下，

struct ArrayAccess {
    Value *base;
    std::vector<AffineExpr> indices;
    std::map<IndVar*, IterRange> domain;
}

Array Access 由 base, indices, domain 三个部分组成：

• base: 数组的基地址，只能为 ALLOCAInst、GlobalVaraiable 或 FormalParam
• indices: 索引表达式，每个元素为 AffineExpr，表示该索引的表达式。
• domain: indices 中，各 AffineExpr 内归纳变量的范围。

依赖测试部分我们使用了 Omega Test，包装成了 OmegaSolver，在 include/constraint/ 目录下。

Omega Test 是一个整数线性规划算法，给定一组整数的线性约束，它可以判断是否可能存在整数解。 它先消除等式约束，将整个系统转为一组不等式约束。然后通过 Fourier-Motzkin 消去法消元。
直观上来讲，如果把所有的不等式约束抽象成一个 N 维空间上的多面体，Omega Test 利用 Fourier-Motzkin 消去法求其在 N - 1 维空间上的投影。分析投影与投影变量的上下界以推断 原多面体内是否可能存在整数点。

参考资料

• A fast and practical integer programming algorithm for dependence analysis
• 《多面体编译理论与深度学习实践》 3.4.4 Omega 测试

Transform Passes

Early Promote Memory to Register

SIR 上的 mem2reg。由于 SIR 无 Phi 节点，这里的 mem2reg 应用范围较窄，只能将与循环无关的一部分内存提升为寄存器。

While to For

尝试将 While 循环转换为 For 循环，此时归纳变量变为 IndVar，它与 Phi 节点类似，在 lower 到 IR 时直接替换为 Header 里面的 Phi，所以也可看作在循环内做了局部的 mem2reg。

Early Dead Code Elimination (EarlyDCE)

SIR 上的死代码消除，early 指相对于 IR 上的 DCE 和 ADCE.

Constant Fold

常量折叠。

Early Function Inline

SIR 的函数内联。

Loop Unswitch

尝试将循环条件分支移出循环。

Loop Fusion

尝试将两个循环融合为一个循环。

Loop Interchange

尝试将交换嵌套的循环以优化访问的局部性。

Affine Loop Invariant Code Motion (AffineLICM)

尝试将 For 内的代码移动到循环外。

参考资料:

• MLIR Affine Loop Invariant Code Motion

Reshape Fold

将 For 内数组的复制，转置等等传播到使用点，消除不必要中间数组复制。

Relayout

对于访问模式局部性差的循环，如果 LoopInterchange 不能优化访问模式，则 Relayout 尝试将数组转置，改变数据的排布，从而提升访问的局部性。

Utility Passes

Print Function/Module

将 SIR 打印到指定的流

IR

Intro

IR 是 SIR 的后继，我们使用的 IR 是 LLVM IR 的子集, 以便使用 LLVM 的工具链进行调试。

Structure

相关指令在 这里。

Analysis Passes

Dominance Analysis

支配关系分析，使用 Semi-NCA 算法

参考资料：

• 再谈Dominator Tree的计算
• llvm浅谈5 domtree
• 编译器中的图论算法
• OI Wiki - 支配树

Liveness Analysis

活跃区间分析。

Loop Analysis

自然循环识别。

自然循环，直观来讲，是只有单入口、内部基本块可以构成环的 CFG 子图。后面提到的循环，除非特别声明，都指自然循环。

自然循环的相关术语详见 LLVM Loop Terminology (and Canonical Forms)

• Header：循环的唯一入口，支配循环内所有节点。
• Entering Block：进入循环的非循环节点（该边必然指向 Header）。
• PreHeader：若仅存在一个 Entering block，且其唯一出边指向 Header，则该块为 PreHeader。注意它不属于循环本身。
• Latch：循环内拥有指向 Header 的边的节点。
• Backedge：从 Latch 指向 Header 的边。
• Exiting Block：循环内拥有循环外后继的节点。
• Exit Block：Exiting Block 不在循环内的后继节点。

循环识别算法大致流程如下：
逆序遍历支配树，并对支配树中的每个节点 N 进行以下操作：

• 找到所有 N 构成的回边：遍历 N 的所有前驱，如果 N 支配了某个前驱 P，则 N 与 P 构成一条回边。
• 如果找到了回边，则以 N 为 Header 构建循环，并将所有回边的前驱块（即 Latch）放入一个 worklist 中。之后遍历这个 worklist，判断节点是否属于某个循环，并分为如下两种情况处理：
  1. 如果节点不属于任何循环（第一次发现的节点），则它属于以 N 为 Header 的循环。接着判断它是否为 N 本身。如果不是，则它的所有的前驱节点加入 worklist；反之，则不需要处理（因为已经到达循环头）。
  2. 如果节点已经属于一个循环 L，则找到它所在的最外层循环，如果最外层循环是以 N 为 Header 的循环，则不需要进一步处理；反之，则它所在的最外层循环作为以 N 为 Header 循环的子循环，并将所有不在 L 内的前驱加入 worklist。

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

参考资料：

• LLVM Loop Terminology (and Canonical Forms)
• 深入理解 LLVM：代码生成 第 5 章 循环基本知识

Scalar Evolution (SCEV)

标量演化

这个 Pass 主要获取循环归纳变量的相关信息。

SCEV 的分析结果以 TREC 的形式呈现。TREC 即 Tree of Recurrences，也有人称作 Chrec, Chains of Recurrences。 TREC 又分为以下几种

• Expr: 循环不变量
• AddRec (Add Recurrence): 最常见的归纳变量的形式，也可表示复杂的多项式。形式为 {a, +, b, + c, +, ... }，常见的线性归纳变量为 {base, +, step}
• Peeled: 初次迭代为 first，后续迭代符合 rest 的规律。注意 first 为 Expr, 而 rest 为 TREC。形式为 (first, rest)
• Periodic: 周期性变化的 TREC，形式为[a, b] （尚未实现）
• Untracked/Undef: 表示 SCEV 无法分析这个值

利用 SCEV 可以分析出循环的迭代次数，归纳变量的变化规律、取值范围以及循环结束后的值。
例如，针对下面这个复杂的函数，

int sum(int n)
{
    int i = 1;
    int sum = 0;
    while (i <= n) {
        sum = sum + i * i * i;
        i = i + 2;
    }
    return sum;
}

他所对应的 IR 为：

define dso_local i32 @sum(i32 noundef %n) {
entry:
  br label %while.cond

while.cond:        ;preds = %entry, %while.body
  %i.def0.1 = phi i32 [ 1, %entry ], [ %bin13, %while.body ]
  %sum.def1.1 = phi i32 [ 0, %entry ], [ %bin11, %while.body ]
  %icmp4 = icmp sle i32 %i.def0.1, %n
  br i1 %icmp4, label %while.body, label %while.end

while.body:        ;preds = %while.cond
  %bin8 = mul i32 %i.def0.1, %i.def0.1
  %bin10 = mul i32 %bin8, %i.def0.1
  %bin11 = add i32 %sum.def1.1, %bin10
  %bin13 = add i32 %i.def0.1, 2
  br label %while.cond

while.end:        ;preds = %while.cond
  ret i32 %sum.def1.1

}

SCEV 的分析结果如下：

'%while.cond' Trip Count: ( ( 1 + %n ) / 2 )
%i.def0.1 at block '%while.cond': { 1, +, 2 }_%while.cond
%i.def0.1 at block '%while.body': { 1, +, 2 }_%while.cond
%i.def0.1 at block '%while.end': ( 1 + ( 2 * ( ( 1 + %n ) / 2 ) ) )
%sum.def1.1 at block '%while.cond': { 0, +, { 1, +, { 26, +, { 72, +, 48 }_%while.cond }_%while.cond }_%while.cond }_%while.cond
%sum.def1.1 at block '%while.body': { 0, +, { 1, +, { 26, +, { 72, +, 48 }_%while.cond }_%while.cond }_%while.cond }_%while.cond
%sum.def1.1 at block '%while.end': ( ( 48 * ( ( ( -3 + ( ( 1 + %n ) / 2 ) ) * ( ( -2 + ( ( 1 + %n ) / 2 ) ) * ( ( -1 + ( ( 1 + %n ) / 2 ) ) * ( ( 1 + %n ) / 2 ) ) ) ) / 24 ) ) + ( ( 72 * ( ( ( -2 + ( ( 1 + %n ) / 2 ) ) * ( ( -1 + ( ( 1 + %n ) / 2 ) ) * ( ( 1 + %n ) / 2 ) ) ) / 6 ) ) + ( ( ( 1 + %n ) / 2 ) + ( 26 * ( ( ( -1 + ( ( 1 + %n ) / 2 ) ) * ( ( 1 + %n ) / 2 ) ) / 2 ) ) ) ) )
%bin8 at block '%while.body': { 1, +, { 8, +, 8 }_%while.cond }_%while.cond
%bin10 at block '%while.body': { 1, +, { 26, +, { 72, +, 48 }_%while.cond }_%while.cond }_%while.cond
%bin11 at block '%while.body': { 1, +, { { 27, +, { 26, +, { 72, +, 48 }_%while.cond }_%while.cond }_%while.cond, +, { 72, +, 48 }_%while.cond }_%while.cond }_%while.cond
%bin13 at block '%while.body': { 3, +, 2 }_%while.cond

这样我们可以得到

• 循环的迭代次数为 ( 1 + %n ) / 2
• 归纳变量 i 在循环体内的变化规律为 { 1, +, 2 }，即初始值为 1，每次迭代增加 2
• 返回值 sum 的变化规律。他在循环结束后的值可以直接表示为参数 n 的表达式

其中最重要的是 sum 关于 n 的表达式，利用这个信息可以直接把循环改写为几条四则运算，不经迭代就可得到循环的结果。不过实际使用中很少有循环可以直接得到这样的表达式，即使得到了通常也会因为副作用或 use-def 依赖而无法删除循环。

相关资料：

• Fast Recognition of Scalar Evolutions on Three-Address SSA Code
• Induction Variable Analysis with Delayed Abstractions
• The SSA Representation Framework: Semantics, Analyses and GCC Implementation.
• Scalar evolution技术与i^n求和优化

Basic Alias Analysis

简单的别名分析，它是跨函数的（inter-procedural）但是是字段不敏感的（field-insensitive）。

两个指针的 Alias 关系可以分为：

• MustAlias 一定相同
• MayAlias 可能相同，也可能没关系
• NoAlias 一定不同

某一操作针对指针的 ModRef 关系可以分为

• Mod 可能修改
• Ref 可能引用
• ModRef 可能修改也可能引用
• NoModRef 一定不会修改也不会引用

而 Basic Alias Analysis 的分析结果主要可以：

• 判断两个指针的 Alias 关系
• 判断指令对指针的 ModRef 关系
• 判断指针是否为函数内部数组的指针
• 判断函数关于函数参数和所有全局变量的 ModRef

利用这个 Pass, 我们可以判断函数是否有副作用 (side effect)，是否为纯函数 (pure)。

Loop-oriented Alias Analysis

基于 SCEV 的针对循环的别名分析，它是函数内的（intra-procedural）但是是字段敏感的（field-sensitive）。 它基于 AMM (Access-based Memory Modeling)，提供比 Basic Alias Analysis 粒度更细的结果。

在我们的实现中，它利用 SCEV 提供的归纳变量信息准确的分析循环内指针的变化规律，同时也可以得到指针是否相邻的信息。
目前主要在向量化和循环并行使用。

参考资料：

• Loop-Oriented Array- and Field-Sensitive Pointer Analysis for Automatic SIMD Vectorization

Range Analysis

值范围分析

我们的实现比较简单直接，没有使用 eSSA，也没有利用溢出的信息。它从这些地方获取范围信息：

getelementptr

注意我们的 getelementptr 操作数索引只能为正数，不过 LLVM 是允许负数索引的，详见 The Often Misunderstood GEP Instruction

predicate of def block

即到达值定义块所满足的条件。
比如

if (a > 10) {
  // (1)
  if (a < 5) {
    // (2)
  }
}

在 （1） 所在的块内，a 的范围一定为 [11, inf) 的子集，利用这个范围，我们可以推导出 a < 5 一定为 false。

函数参数

分析参数在所有调用点的范围的并集。

特殊指令

如 zext 和 sext 的范围一定在原类型范围内。

SCEV

利用 SCEV 的信息可以推断出很多与循环归纳变量相关的值的正负。

Transform Passes

Promote Memory to Register (mem2reg)

将内存访问 (alloca, load, store) 等提升至寄存器，此后的 IR 除数组外大部分情况下无指针类型，便于后续优化。

Dead Code Elimination (DCE)

简单的死代码消除，递归地删除 use count 为 0 的指令。

Aggressive Dead Code Elimination (ADCE)

激进的死代码消除，基于 EAC2 的 Mark-Sweep 算法实现。

类似于 Mark-Sweep 垃圾收集器，我们把 IR 视为数据。
进行两次遍历，第一次（Mark）标记有用的指令为 critical，第二次（Sweep）删除无标记的指令。 一个指令是 critical 的除非：

• 有副作用
• 无条件分支
• 条件分支，且是任一 critical 指令的控制依赖
• 是任一 critical 指令的操作数

Mark 阶段从已知 critical 的集合（有副作用指令和无条件分支）开始反向传播：

• 沿着数据依赖（SSA 的 use-def chain）回溯到操作数的定义点。
• 沿着控制依赖（利用逆支配边界）回溯到决定 critical 操作所在基本块是否执行的分支点。

Sweep 阶段：

• 将无标记普通操作直接删除
• 改写无标记条件分支为到到最近 critical 逆支配点的无条件分支

参考资料：

• Engineering A Compiler 2nd, 10.2.1 and 10.2.2 (Mark, Sweep)

Control Flow Graph Simplify (CFGSimplify)

CFG 简化，基于 EAC2 的 Clean 算法实现。
实际上在 EAC2 中， Mark, Sweep 与 Clean 是合在一起的，但拆开更方便使用。

这个 pass 主要处理这四种情况：

Case 1

flowchart TD
    src -->|true| dest
    src -->|false| dest
    dest --> next

Loading

flowchart TD
    src --> dest
    dest --> next

Loading

Case 2

flowchart TD
    pred1 --> curr[Empty Block]
    pred2 --> curr
    curr --> dest
    other --> dest

Loading

flowchart TD
    pred1 --> dest
    pred2 --> dest
    other --> dest

Loading

Case 3

flowchart TD
    prev --> curr[Has Single Succ] --> dest[Has Single Pred] --> next

Loading

flowchart TD
    prev --> Combined --> next

Loading

Case 4

flowchart TD
    curr --> dest[Empty Block]
    dest -->|true| succ1
    dest -->|false| succ2

Loading

flowchart TD
    curr -->|true| succ1
    curr -->|false| succ2

Loading

参考资料：

• Engineering A Compiler 2nd, 10.2.1 and 10.2.2 (Clean)

If Conversion

这个 Pass 用 select 指令来替代掉一部分的条件分支，可以消除条件跳转。

在 SIR 经过 CFGBuilder 得到 IR 后，if 一般以下的形式呈现：

flowchart LR
    ifcond[if.cond] -->|true| ifthen[if.then] --> ifend[if.end]
    ifcond[if.cond] -->|false| ifelse[if.else] --> ifend[if.end]

Loading

经 CFGSimplify 后可以化简为这样的 CFG

flowchart LR
    bb0 -->|true| bb1
    bb1 --> bb3
    bb0 -->|false| bb3

Loading

此时经 If-Conversion 转换后得到：

flowchart LR
    bb0 --> bb1
    bb1 --> bb3

Loading

其中 bb1 中存在 select，它包含原 bb1 和 bb2 中的指令。在 CFGSimplify 后，bb1 可以和 bb3 合并，从而得到：

flowchart LR
    bb0 --> bb3

Loading

可以看到，这个 Pass 会造成一条路径上的冗余，因此他的执行有较为严格的 threshold，而且被复制的指令也不能有副作用。

Dead Argument Elimination (DAE)

删除无用的参数。
如果某个函数参数在所有调用点都为同一个全局变量+偏移或静态常量，直接将其删除。

Sparse Conditional Constant Propagation (SCCP)

稀疏条件常量传播

区别于传统的密集 (Dense) 数据流分析，SCCP 不在所有基本块入口/出口处计算和传播所有变量的状态。 这是因为 SSA 中，每个值都有唯一定义，数据流信息实际上是直接沿着 SSA 的边传播的，我们只需要特殊处理 phi 节点。

参考资料：

• Static Single Assignment Book, P104, 8.2.2, Algorithm 8.1
• Wegman, Mark N. and Zadeck, F. Kenneth. "Constant Propagation with Conditional Branches.
• LLVM SparseSolver

Dead Store Elimination (DSE)

删除无用的 store
具体而言如果一个 store

• 内存后续不再被引用
• 被后续 store 覆盖
• store 的值是刚从这块内存中 load 出来的

则可以删除该 store。

Redundant Load Elimination (LoadElim)

冗余 load 消除
具体而言，如果一个 load

• 在之前已经被 load 过一次了
• load 的内存是刚被 store 过的

则可以把 load 替换为先前的 load 或者 store 的值

Break Critical Edges (BCE)

删除关键边，是 GVN-PRE 的前置 pass

关键边：从拥有多个后继的基本块指向拥有多个前驱的基本块的边，如

flowchart LR
    bb0 --> bb2
    bb0 -->|critical edge| bb3
    bb1 --> bb3

Loading

这个 pass 会在由关键边连接的两个基本块之间插入一个空基本块，从而消除关键边，比如上面的例子就得到：

flowchart LR
    bb0 --> bb2
    bb0 --> bb4[New block]
    bb4 --> bb3
    bb1 --> bb3

Loading

参考资料：

• Critical Edge Splitting

Value-Based Partial Redundancy Elimination (GVN-PRE)

基于值的部分冗余消除，可以认为是 GVN 和 PRE 的结合。

参考资料：

• Thomas VanDrunen and Antony L. Hosking "Value-based Partial Redundancy Elimination
• Optimizing SSA Code: GVN-PRE
• GVN - LLVM
• GVN-PRE - GCC Wiki

Range-Aware Simplify

基于 Range Analysis 的优化，进行一部分除法和取余的强度削弱以及替换可以推导出的 icmp/fcmp。

Reassociate

表达式重结合。

一条含有常量的表达式中可能会有其他 pass 发现不了的优化机会，如

y = 1 + x + 3

在 IR 中我们可能看到的是

tmp = 1 + x
y = tmp + 3

重结合可以发现 1 + 3 这样的优化机会。
此外这个 pass 还会提取乘法的公因式，交换操作数的顺序，从而使程序更有利于被 LICM, GVN-PRE 优化。 （因为循环外指令的 Rank 更小，Reassociate 会尽量使循环不变量排在一起，这样排列可以出现更多的循环不变量）

Instruction Simplify

针对单条指令的简化

• 常量折叠：如 1 + 1 -> 2
• 简单的算数化简：如 x + 0 -> x
• 基于四则运算法则的化简：如 x - -y -> x + y
• 特殊冗余指令 icmp eq x, x -> i1 true
• ...

Loop Simplify

循环简化。

简化后的循环符合 Loop Simplify Form，即：

• 唯一的 PreHeader
• 唯一的 Back Edge（唯一 Latch）
• Dedicated Exits （所有的 Exit Block 都被 Header 支配）

参考资料：

• LLVM Loop Terminology (and Canonical Forms)

Loop-Closed SSA Construction (LCSSA)

循环闭包 SSA 构造。

LCSSA 后所有的循环符合 LCSSA Form，即循环内定义的值只在循环内被使用。 这是通过将循环外的 use 都替换为 Exit Block 内的 LCSSA Phi 实现的。 LCSSA Phi 是一种只有一个项的完全冗余的 Phi 节点，将循环外所有的 use 替换为 LCSSA Phi 即可构造出 LCSSA Form.

exit_block:
%x.lcssa = phi [%x, %bb]

这里需要注意的是，phi 的 incoming value 的 use 是看作在相对应的前驱内 的，因此 LCSSA Phi 的 use 还是在循环内。

参考资料：

• LLVM Loop Terminology (and Canonical Forms)
• LLVM Language Reference Manual

Loop Rotate

循环旋转

普通的 while/for 循环 lower 之后的一般为 Header 退出循环。经过 Rotate 之后，变为 Latch 退出循环。这样可以简化 CFG，并利于 LICM 进行。例如：

graph LR
    PreHeader --> Header
    Header --> Body
    Body --> Latch
    Latch --> Header
    Header --> Exit

Loading

经过 Rotate 之后变为：

graph LR
    PreHeader+Header --> Body
    PreHeader+Header --> Exit
    Body --> Latch
    Latch --> Header
    Header --> Body
    Header --> Exit

Loading

注意到第二个图中，原来的 Body 变为了 Header，原来的 Header 变为了 Latch。
如果只有一个 Latch，那么 Latch 还可以与原来的 Header 合并。如果循环会执行至少一次，PreHeader 到 Body 的边也可消除。
此外，Rotate 会先复制 Header 中的指令到 PreHeader，而且 Rotate 对 CFG 也有一定要求，因此并不是所有循环都可以被 Rotate。

参考资料：

• LLVM Loop Terminology (and Canonical Forms)

Loop Strength Reduce

强度削弱

基于 SCEV 将循环内的乘法/含有乘法的 getelementptr 转换为加法/不含乘法的 getelementptr。
这是通过在 Header 里面插入 Phi，把乘法改为归纳变量的加法实现的。

Useless Loop Elimination (LoopElimination)

无用循环消除

对于无副作用的循环，尝试通过 SCEV 计算出循环退出后各个变量的值，并替换掉循环外对他们的 use，从而使整个循环可以被消除。此外它还把 SCEV 可以推断出只执行一次的循环的回边打破。

Loop Invariant Code Motion (LICM)

将每次循环迭代时计算结果都相同的表达式移到循环外。减少重复计算，提高程序性能。
在移动指令时，需考虑循环中的 use-def 关系与 control flow equivalence。
此外，我们的实现中不会破坏 LCSSA 形式

LICM 进行的代码移动分为 hoist 和 sink

hoist

1. 按拓扑顺序遍历循环基本块
2. 检查指令是否满足：

• 操作数都是循环不变的
• 指令可以安全移动
• 基本块后支配 preheader

3. 将符合条件的指令移到 preheader

sink

1. 按逆拓扑顺序遍历循环基本块
2. 检查指令是否满足：

• 指令可以安全移动
• 循环内没有使用该指令的结果
• 操作数都是循环不变的

3. 将指令克隆到支配的退出块

Loop Unroll

循环展开，包含：

• Fully Unroll
• Partially Unroll
• Runtime Unroll
• Peeling

参考资料：

• Deep diving into LLVM loop unroll

SLP Vectorizer

自动向量化

我们使用 Bottom Up SLP，从基本块内的 store 寻找向量化机会，配合循环展开效果更好。

参考资料：

• Exploiting Superword Level Parallelism with Multimedia Instruction Sets
• Loop-Aware SLP in GCC - Proceedings of the GCC Developers’ Summit
• VeGen: a vectorizer generator for SIMD and beyond

Loop Parallel

循环并行

Function Inline

函数内联

Function Specialization

函数特化

这个 pass 将常量参数的调用换为特化过的版本

int foo(int x, int flag) {
    if (flag)
        return x + 1;
    return x - 1;
}

如下面两个调用则会特化出相应的 foo(int)

foo(x, 1);
foo(x, 0);

参考资料

• Introducing Function Specialization, and can we enable it by default ?

Tail Recursion Elimination

• 将尾递归转换为循环，从而减少函数调用开销和栈空间使用。
• 对于非递归的尾调用，仅设置标记而不改变结构。

Memoization

将纯递归函数记忆化

参考资料

• Clava - C/C++/CUDA/OpenCL source-to-source compiler
• A framework for automatic and parameterizable memoization
• A methodology and framework for software memoization of functions.

Constraint Elimination

消除冗余的条件。

如在下面的 (*) 处 的 a > c 是冗余的。

if (a > b && b > c) {
  if (a > c) {
    // (*)    
  }
}

这个 pass 是借助 OmegaSolver 实现的。

Code Sink

在不改变语义的情况下，将每条指令尽可能 sink 到最早的 User。

Code Generation Prepare (CodeGenPrepare)

为后续 lower 至 MIR 做准备。目前主要是破除关键边。

Flatten getelementptr to Arithmetics (GepFlatten)

将 getelementptr 转为 ptrtoint + mul/add + inttoptr + zext

Internalize

全局变量尽量转为局部变量

Globalize

将大的局部变量转为全局变量

Lower Intrinsics

SIR Gen 时，数组局部变量可能会使用 memset 进行数组初始化。Internalize 将全局数组转为局部数组时，可能使用 memcpy。 而有些平台不支持这些 Intrinsic，此时这个 pass 就地实现一个函数来代替。

Name Normalize

修复指令的命名以符合 LLVM IR 格式。

Tree Shaking

删除无用的全局变量和函数。

Unify Exits

将退出块统一为一个块。

Utility Passes

Print CFG as "dot" (DotCFG)

将 CFG 转为 dot，效果与 opt -disable-output --passes=dot-cfg 类似

Print CFG as "png" (PngCFG)

将 CFG 先转为 dot，再转为 png。

Run Test

运行给的测试用例并验证的 pass，便于插入到 pipeline 中验证 Transform 正确性。
命令行传入 --test-out xxx/--test-in xxx 可在每个 pass 后自动开启。其中 --test-in 为可选的。

Verify

简单的正确性检查，能查出编写 pass 初期相当一部分 bug。
命令行传入 --verify 可在每个 pass 后自动开启。

Print Function/Module

以 LLVM IR 格式打印 Function/Module 到指定流

MIR

Intro

MIR 是针对目标机器架构特定的中间表示，抽象程度更低，不符合 SSA 形式。 本 MIR 在经过最终的 CodeGen 之后可以分别转化为 RISCV64 或者 AArch64 的符合 GNU 汇编器标准的汇编指令。

PS: LegacyMIR 是比赛章程正式发布前的 MIR，用于生成 ARMv7 指令集下的汇编指令，效果上仅保证基本的正确性.

Structure

• MIRModule：代表一整个编译单元，Function 和全局变量的集合，
• MIRFunction：用于存放函数体，持有基本块，存放栈空间信息
• MIRBlk：
  • 持有该基本块中所有的指令
  • 维护其前驱和后继的基本块
  • FlattenCFG 中将与其直接邻近的基本块
  • 块中使用了文字池的基本块，将在块的末尾插入文字池，以此尝试减少 Data Cache Miss
• MIRInst：
  • mOpcode 用于标记该 Inst 具体执行什么操作，为了兼容不同的指令集，mOpcode 是一个 variant
  • mOperands 存放操作数列表，每种指令对于操作数列表的使用（存放多少以及存放在哪里）都有规定，不过没有设置对此的专门地检查
  • 对于该 Inst 具体操作的位宽，通过 mOperands 推断得到，不过这种方法实际上缺乏可拓展性，并非最佳实践
• MIROperand：内容比较丰富的一个结构
  • mOperand：用于标识该操作数的类型，variant 从前到后依次表示寄存器（虚拟的或者ISA寄存器）、重定向地址（一般就是汇编中的标签）、u32 或者 f32 立即数（都用 unsigned 存储）、u64 立即数、分支概率、以及最后的文字池数据
  • mType：该 Operand 的类型，用于上面提到的推断
• CodeGenContext：存放架构相关的信息，如寄存器使用，调用规约等
  • nextId: 给虚拟寄存器命名，方便调试
  • referCnt: 引用计数，可以比较方面的消除死代码，不过在寄存器分配后删除冗余 Copy 指令后就不能再用了

Analysis Passes

MIR 上的分析Pass主要有

• Branch Frequency Analysis: 分析基本块之间的跳转频率
• Dominance Analysis：分析基本块之间的支配关系
• LiveAnalysis：分析变量的活跃信息，包括基本块的 livein，liveout，单个变量的 liveinterval length 等
• LoopAnalysis：通过基本块的前驱后继关系，寻找 loop，算法和 IR 上的分析一致

Transform Passes

首先需要通过 Lowering 才能从 IR 转到 MIR，此时的 MIR 都是 GenericMIR，包括一些向量指令 这个过程进行 Phi 节点消除，Phi 节点消除使用简单的拓扑排序和插入拷贝完成。

MIR 形式上进行等效转换的Pass如下

FusedAddress

中端 IR 形式上，通常使用 getelementptr 指令获取数据地址，这种方式通常无法充分利用指令集提供的寻址模式 该 pass 将识别指针的运算指令，并尝试将其中的加法指令替换为 LDR/STR 中的基址或者变址寻址

MachineConstantFold

IR 形式上，为了获取一个多级数组中的某一个元素地址，需要使用多级的 gep 逐级添加偏移量，对于汇编指令而言，这些计算是不必要的，偏移可以一次计算完毕

ISel

• 指令选择，但主要是将 GenericMIR 处理成接近汇编指令形式，AArch64 架构和 RISCV64 架构的某些特化指令将在这个过程插入，

GenericPeephole

• 窥孔优化的集合，在很多其他 pass 之后都可以使用，但其中有一些限制了使用时期，尤其是那些需要引用计数的窥孔

CFGsimplifyBeforeRA

• 删除死块（如果 IR 形式时没删）
• 尝试合并 bool 的定义和使用，即从存储 bool 值到寄存器，修改到直接使用 CPSR

LoadEli

由于汇编指令无法接受立即数作为操作数，在 ISel 阶段会使用显式的各种 Load 将立即数加载到对应寄存器中，由于 ISel 阶段一次仅处理一条指令，并不考虑其他指令，故 Load 实际上有可能是多余的，即已经被加载到某个虚拟寄存器中，可以考虑将 Load 替换为 Copy

• 扫描 MIRInst ，对于每个被显式加载的立即数，构建表项，记录所有出现 Load 的基本块，以及块内的 Load 指令
• 对于记录的所有的基本块，计算出它们在支配树上的 LCA 基本块
• 由于 Copy 会延长操作数的活跃区间，可能导致更多寄存器溢出，所以对每个基本块使用启发式算法，决定对于该块是进行全局替换（Copy LCA 基本块中的虚拟寄存器），还是局部替换（Copy 基本块内的虚拟寄存器）
• 判断完成之后，将 Load 替换为 Copy

MachineLICM

由于 ISel 中可能在循环中插入其他指令，这些指令实际上极有可能是循环不变量，故可以将其外提

RegisterAlloc

采用图着色寄存器分配，原理参见Iterated Register Coalescing

CodeLayout

对整体的代码布局进行调整，期望减少 Instruction cache miss 由于测例一般进行了大量的函数内联，故 CodeLayOut 主要是对基本块布局进行调整，即基本块重排

CFGsimplifyAfterRA

1. 在寄存器分配后，合并冗余的 Copy 之后，有一些块将成为只有无条件跳转的块，可以将该块在 CFG 中删去

flowchart TB
    subgraph 优化后CFG
        A_opt["Block A: ..."] --> C_opt["Block C: ..."]
        D_opt["Block D: ..."] --> C_opt
    end

    subgraph 原始CFG
        A["Block A: ..."] --> B["Block B (冗余块): br C"]
        B --> C["Block C: ..."]
        D["Block D: ..."] --> B
    end

Loading

2. 对于某些基本块，其最后一条指令为无条件跳转，并且在 FlattenCFG 中其后紧邻的基本块即为跳转目标，可消除该无条件跳转，改为顺序执行

flowchart LR
subgraph 优化后CFG
X_opt["BB X: 
            ..."] -- fallthrough --> Y_opt["BB Y:
..."]
end
subgraph 原始CFG
X["BB X:
...
jmp Y"] --> Y["BB Y:
..."]
end

Loading

3. 对于一些有条件跳转的基本块，可以通过反转条件和目的基本块，形成 2 中描述的场景

flowchart TB
subgraph 优化后CFG
P_opt["BB P: 
            ...
cmp %0, %1
bne S"] -- fallthrough --> R_opt["BB R:
..."]
R_opt --> S_opt["BB S:
..."]
end

subgraph 原始CFG
P["BB P:
...
cmp %0, %1
beq S
b R"]
P -- fallthrough avaliable --> R["BB R:
..."]
P --> S["BB S:
..."]
end

Loading

PostRaScheduling

进行基本块内的指令调度和重排，目前只有 AArch64 后端有这个功能

• 对指令和寄存器进行依赖分析和拓扑排序
• 模拟时钟周期，CPU运算部件以及寄存器的就绪情况
• 模拟指令的发射和资源占用

关于毕昇杯

决赛刚开始时我们的编译器出现了大量的 WA + TLE，由于决赛时间短且每次评测时间很长（我们的寄存器分配存在随机性，导致平台的缓存几乎无法命中），再加上决赛测例不公布，几乎无法调试。 因此我们不断打开关闭了一些 pass，发现下列 pass 中可能存在 bug，会导致编译产物结果错误或死循环。 由于当时时间有限（通宵爆肝 30+ h 😭），并没有排查出具体是哪个 pass 有问题，它们在决赛时都没有开启。

• MemoizePass
• LoopInterchangePass
• FunctionSpecializationPass
• ReassociatePass

以下 pass 由于效果不好未开启

• RelayoutPass
• LoopPeel in LoopUnrollPass
• CodeSinkPass
• GepFlattenPass

以下 pass 截至决赛时尚未完成

• LoopTilingPass
• LoopUnswitchPass
• IndVarSimplifyPass