注: 本文于 2024-03-02 更新循环相关优化部分，其他部分稍作修改。

课程要求，写了一个简单语言 Mx* 的编译器，语法规则请点击这里 。笔者写的很烂，而且项目还烂尾了，所以不放自己写的链接了。

其简单来说是一个残疾版 Java + C ，拥有类似 Java 的对象模型，所有 class 都是引用类型 (笔者汇编实现其实就是指针)，且有最基本的构造函数和成员函数 ，但没有复杂的面向对象特性 (比如继承，虚函数等等) ，甚至连常见关键词如 static 什么的都没有。当然，解决一些简单的问题还是绰绰有余的。

编译器最后生成汇编代码的目标平台是 RISC-V 32bit, Integer Extended , 测评使用的是 ravel 模拟器 不过bug(feature)还不少 。

AST

笔者前端使用的是 antlr ，通过自己编写 g4 实现 Lexer/Parser 的功能 ，基本属于是自动生成。这部分个人感觉难度不高，除了语法检查有很多细枝末节要考虑，其他基本没啥值得讲的。不过其实在这一部分，其实已经有可以优化的空间了，例如对于无副作用的一些恒等表达式，以及无用的数组 new 。当然，由于笔者实在是没空，在 AST 上我没有做任何优化。

IR

IR 上的优化可以说是编译器优化的核心。可以说我 90% 的优化都是作用在 IR 上的。

笔者的 IR 采用的是简化版本的 llvm IR (至少生成的.ll 可以用 clang 编译运行且不会出错)。下面将会简单讲讲笔者在 IR 上具体写了那些玄学优化，以及计划(但实际没写)的那些优化。

mem2reg-SSA

前置知识: 支配树 。

SSA(Static single assign) 是指满足虚拟寄存器只会被被单一赋值的 IR ，在 SSA 上，许多的优化可以被简化，且时间复杂度会更优。显然，内存是不能也不需要保证 SSA 的。而局部变量，其可能被多次赋值，不一定能满足 SSA 的条件，所以在生成 IR 的时候一般会用 alloc 申请栈空间用于其值的存储。

但是实际上，很多时候，寄存器是充足的，我们期望可以把局部变量的值放在寄存器(在 IR 中呈现为虚拟寄存器) 里面，从而避免了高开销的内存读写操作。但是前面也说了，局部变量可以被重复赋值，比如在不同分支中有不同的取值，导致不一定能放入虚拟寄存器。

1
2
3
4
5
6
7
8
9
int func(bool cond) {
    int z;
    if(cond) {
        z = 1;
    } else {
        z = 2;
    }
    return z;
}

但是，mem2reg 为我们提供了一种消除 SSA 形式 IR 中部分 alloc 的方法。其思路大致如下:

我们把每条指令看作图中的一个节点。除了分支指令有两个后继 (即出边)，其他指令有唯一后继。如果一个局部变量 x 在一条指令的位置被赋值，那么在这条指令所支配 (此处指的是支配树的支配关系) 的范围内，在下一次被赋值之前，其值不会改变，这是由支配树的性质所保证的。但是在其支配边界上，到达该位置的 x 可能就不止来自这个方向的赋值。还可能存在其他方向的赋值，这也很符合支配 “边界” 的直观。为了保险起见，我们要根据其来的方向，为这个 “边界” 上的指令进行值合并。在这里，llvm IR 为我们提供了一个工具函数: phi 函数。其不是真正的函数调用(call) 指令，其作用是根据跳转的分支为一个变量赋值。例如，对于上面那段 C++ 代码，其可以生成类似如下的 llvm IR 代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

entry:
    br i1 %cond-0, label %if-0-true-0, label %if-0-false-0

if-0-true-0:
    br label %if-0-end

if-0-false-0:
    br label %if-0-end

if-0-end:
    %z-1.mem.0 = phi i32 [ 1 , %if-0-true-0 ] , [ 2 , %if-0-false-0 ]
    ret i32 %z-1.mem.0

简而言之，phi 函数可以用来合并来自不同分支的赋值，类似维护了变量的不同版本，从而保证了 SSA 的形式。这也带来了 mem2reg 这一优化，其可以把所有没有被取地址，且不是 volatile 的局部变量转化为虚拟寄存器，进而消除相关的 load/store。由于 Mx* 的语言特性，其天然不存在取地址，因此所有天然的 alloca 理论上都能被消除，

mem2reg 首先建立一个函数的控制流图，然后对于所有的局部变量 (alloca 产生)，对每个对这个局部变量的赋值 (目前只含 store 指令)，我们在其支配边界标记插入关于该变量的 phi 函数 (注意，phi 函数也是关于这个变量的赋值。我的解决方案是先处理原来的 store，第二遍再处理 phi 产生的赋值)。

通过扫描，我们容易确定每个块结束后，一个局部变量在当前块结束时候的值。对于每个新插入的 phi 以及其对应的原本的局部变量 x ，我们只需去每个前驱块或许该局部变量的值并且填入 phi 即可。

当然，既然讲到了 phi 函数，就需要特别地说明一下，phi 函数的赋值是并行进行的，即一个块里面所有 phi 同时赋值，例如下面的 两个 phi 语句会交换 x 和 y 的值 (当从 %BB1 跳过来的时候):

1
2
%x = phi i32 [ 0 , %entry ] , [ %y , %BB1 ]
%y = phi i32 [ 1 , %entry ] , [ %y , %BB1 ]

在后文的关于 IR 优化讨论中，我们都假定是在 SSA 形式的 IR 上进行。

DCE&ADCE

死代码消除是一个非常常见的优化。在程序中，难免会出现一些无效的死代码。事实上，在上一步 mem2reg 之后，由于其保守地在每个支配边界都会插入 phi，这可能会导致出现一些无效的 phi (即结果在后面用不到，但是由于 mem2reg 维护了变量在每个块的不同版本，保证正确性，因此插入了不必要的 phi)。这时候，死代码消除就能很好的简化生成的 IR 。

死代码消除有很多种，笔者想出的一个最基础的版本大致如下:

  • 没被标记为副作用的指令都是无用的。
  • 有副作用的指令用到的变量，其定值(因为 SSA ，所以有且仅有一次定值(即被定义)) 语句是有副作用的。
  • 内置的 IO 函数 / 存在全局影响的函数 是有副作用的
  • store 指令认为是有副作用的
  • branch 指令认为是有副作用的
  • return 指令认为有副作用的

通过沿着 def-use 链条前向传播 (依赖 SSA!)，我们可以在线性时间内确定所有的活指令，从而删除死指令。这个死代码消除相当的 naive ，也不能消除空循环这种无效代码，不过好处是其跑的非常快，只需要线性的时间很小的常数就能跑完，且不会修改控制流图，因此被我用来作为其他所有优化结束后顺便跑掉的一个 pass 。

真正的死代码消除，应该能够识别那些没有副作用的分支，从而把那些无效分支清除干净 (包括死循环) 。事实上，基础版本的死代码优化对于分支估计还是过于保守。ADCE (Aggressive Dead Code Elimination) ，可以通过控制流图分析来确定那些有效的分支，不过需要的是反向流图的支配关系。过程大致如下:

  • 所有基本块初始认为是死的
  • 有副作用的指令的块都是活块
  • 内置的 IO 函数 / 存在全局影响的函数 是有副作用的
  • store 指令认为是有副作用的
  • return 指令认为是有副作用的
  • jump 指令到活块认为是有副作用
  • branch 指令，只有当其处于某个活块的反向支配边界上，其才是存活的。

ADCE 比起 DCE，虽然依赖反向流图的支配关系 (这个东西的建立特别费时) ，但是可以消除那些无效的分支 (例如空循环或无效循环)，的确对的上 “Aggressive” 这个名字。

SCCP

常量传播也是非常常见的一个优化。其降低程序员的心智负担，让其大胆写出更多烂代码主要是优化一些表示常数的变量(其实就是临时寄存器)所以为什么不引入 const ，将其在使用处直接替换为对应的常数，这便是最基本的常量传播。

当然，如果两个 SSA 的变量表示相同的数值 (例如 x = y + 0，显然 x = y)，那么显然我们也可以把 x 在所有使用处替换为 y 。注意，其正确性其实并不 trivial。SSA 要求每个变量只能在其支配的基本块内出现，x 支配的块 y 也一定支配，这并不 trivial 。但是注意到 x = y + 0 ，说明 y 必然支配 x 所在位置，因此 x 所支配的块 y 也必然支配 (看看支配的定义即可)。

对于分支和 phi 函数，常量传播依然可以进行下去: 我们先从入口出发。如果遇到 phi 函数，我们先按照来的方向给赋值，如果之后从别的方向来并产生了矛盾，那么再标记这个值不是常量 (或者其他固定值) 。如果遇到一个分支，显然，branch 语句的 condition 的值肯定已经确定是常量或者不是常量。如果是常量，我们就根据 condition 走对应的分支。如果不是常量，我们只能假定两个分支都会走。

因此，常量传播流程大致如下:

首先标记所有的变量 (临时寄存器) 的状态为未知。变量状态有三种: 未知(Unknown) ， 已知 (Known，必须是常量或者其他固定值)，非常量 (Non-const)。状态合并规则如下:

  • Unknown + any = any.
  • Non-const + any = Non-const
  • Known_i + Known_i = Known_i
  • Known_i + Known_j = Non-const (i,j 不同)

然后，我们从入口出发(把入口加入块的工作列表 work_list_1)。

对于 work_list_1 的块，我们按顺序遍历当前工作的块。对于 jump 指令，我们将其目标块加入 work_list_1。对于 branch ，按照之前所讲处理即可。对于其他语句，我们正常进行赋值，并且将 赋值结果 与 结果变量的当前状态 进行合并。如果发现合并结果发生改变，那么我们把这个变量所有被使用的地方(指令)加入 work_list_2 (指令工作列表)。

对于 work_list_2 的指令，我们尝试对其重新计算，并且将 赋值结果 与 结果变量的当前状态 进行合并。如果发生改变，那么类似地，那么我们把这个变量所有被使用的地方(指令)加入 work_list_2 。

我们一直执行，直到两个 work_list 都被清空。由于状态合并最多改变两次 (Unknown->known->non_const 的过程是单向不可逆)，所以不用担心该操作的复杂度爆炸。不过要特别注意的是，我们沿着某一条边进入一个块，遍历一个块的所有语句，这个操作只会执行至多一次，因为后面如果产生了更新，那么肯定会通过 work_list_2 更新过来，所以不用再 visit 一遍。而同时，一个块除了 phi 语句之外的其他语句至多只需要 visit 一遍，在第二次从 work_list_1 取出的时候，只需要重新 visit 那些 phi 函数就行了。如果存在依赖的改变，那么自然会从 work_list_2 更新过来；如果不存在依赖 (比如两个常数的和) ，那么第一次 visit 的时候的结果就自然是正确的了。

这部分的证明还是不难但也不 trivial 的，建议读者自行思考各种 corner case 下的正确性。如果有任何疑问，可以参考原始论文。(不过主体部分还是很好想到的，事实上笔者一开始基本就是按照自己的理解搓了一个几乎差不多的 SCCP，不过论文还考虑了各种优化，包括哪些只 visit 一次，的确人类智慧)。

CFG

流图化简，即 CFG 上的化简，是一个完全由我自己构思的优化 (其实是没看到类似的论文 其实还是懒得找 )。其可以尽可能地消除无效的 jump ，同时消除部分 phi 语句 (不过笔者还没 100% 实现)。

Jump-Elimination

在前面这几个不痛不痒的小优化之后，我们会发现出现了很多基本块的体积减少了一点，很多甚至只剩下一个 jump 语句。在极端的情况下，我们可以看到一堆由连续重复 jump 指令，例如:

1
2
3
4
5
6
7
8
9
10
11
12
BB0:
    br label BB4
BB1:
    br label BB2
BB2:
    br label BB3
BB3:
    br label BB4
BB4:
    br label exit
exit:
    ret void

事实上，这些无效的 jump 都可以被直接压缩为一条语句: ret void 。你可能觉得这不过是常数级别的优化。的确，jump 的确太快了，这些优化显得略有点没用。但是如果 jump 多达几百个呢，这好像就不仅仅是常数了吧。

Condition-Phi-Elimination

考虑如下语句:

1
2
3
BB2:
    %cond = phi i1 [ false , %BB0 ] , [ true , %BB1 ]
    br i1 %cond BB2, label %BB3, label %BB4

如果从 %BB0 过来，那么显然只会跳到 %BB4 。如果 %cond 只在当前条件语句被使用到，那么我们甚至可以直接消除这个 %cond 变量，将这个条件分支直接压缩没了。要知道条件分支对于现代 CPU 的流水线可是一个很糟糕的东西，分支预测错误可是会带来流水线的中断等一系列后果，其速度很慢。因此，我们可以考虑把条件分支顺便也压缩了。

Tail-Phi-Elimination

特别地，如果一个 phi 语句后面紧跟 ret 语句，那么显然其与 ret 的返回值相关(否则，之前的死代码消除将会干碎这个无效 phi)。那么，我们可以把当前块拆开，不同块跳过来的时候直接 return 不同的值。这个操作几乎无法消除多少 phi ，看起来没啥大用处，但是其可以为尾递归优化留下空间。考虑以下的 C++ 代码:

1
2
3
int tail(int n) {
    return n < 0 ? n : tail(n - 10);
}

在正常的 IR 生成中，我们会用 phi 来合并三目运算符的结果。但是这并不利于尾递归优化。当我们手动拆开 phi，相当于将原来的 C++ 代码拆成如下形式:

1
2
3
4
int tail(int n) {
    if (n < 0) return n;
    else return tail(n - 10);
}

显然，这种形式的代码看起来就可以尾递归优化 (甚至是再把尾递归优化为循环)。这也是这个优化的另一个好处。

Summary

以上就是我个人想到的 CFG 上几处小优化。Jump-Elimination 可用于清除并简化其他优化之后复杂的流图，Condition-Phi-Elimination 则对于 复杂短路逻辑表达式 的优化有奇效，Tail-Phi-Elimination 则能帮助尾递归优化。

Local-optimization

这里面涉及了很多块内的优化。这些优化不需要复杂的控制流图，只需要逐块分析即可，不过全是人类智慧。当然，该优化其实可以 global 化，但是由于笔者实在是太累了，所以暂时只写了局部的版本。

Arithmetic-Simplification

算术化简是最常见的一个优化了。在 IR 层级，能做的算术化简其实已经所剩无几了。换句话说，该优化其实本应该在 AST 就做掉不少，至少笔者是这么认为的。

尽管 IR 上处处受限，但是我们依然可以发现以下这些比较 trivial 的表达式优化 (以下摘自笔者的破烂代码的注释):

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
/**
 * Swap operands if the left one is a constant
 * for those symmetric operators: + * & | ^ 
 * 
 * Strength reduction and replacement:
 * X - C        --> X + (-C)
 * X + X        --> X << 1
 * X * pow(2,n) --> X << n
 * 
 * Negative elimination rule:
 * 0 - Y        --> (-Y)
 * X + (-Y)     --> X - Y
 * (-Y) + X     --> X - Y
 * X - (-Y)     --> X + Y
 * (-X) * C     --> X * (-C)    // iff non-power-of-2 C
 * (-X) * (-Y)  --> X * Y
 * (-X) / C     --> X / (-C)
 * C / (-X)     --> (-C) / X
 * (-X) / (-Y)  --> X / Y
 * X % (-Y)     --> X % Y
 * 
 * 
 * Merge operators to try generate deadcode (to be removed~):
 *  Bitwise:
 * (X & C1) & C2    --> X & (C1 & C2)
 * (X | C1) | C2    --> X | (C1 | C2)
 * (X ^ C1) ^ C2    --> X ^ (C1 ^ C2)
 *  Add or Sub:
 * (X + C1) + C2    --> X + (C1 + C2)
 * (X - C1) + C2    --> X + (C2 - C1)
 *  Mult or Div:
 * (X << C1) * C2   --> X * (C2 << C1)
 * (X *  C1) * C2   --> X * (C1 * C2)
 * (X *  C1) / C2   --> X * (C1 / C2)        // iff C2 divides C1
 * (X *  C1) % C2   --> 0 + 0 = 0            // iff C2 divides C1
 * (X << C1) % C2   --> 0 + 0 = 0            // iff C2 divides pow(2,C1)
 *  Shift:
 * (X << C1) << C2  --> X << (C1 + C2)
 * (X >> C1) >> C2  --> X >> (C1 + C2)
 * (X << C1) >> C2  --> X << (C1 - C2) or X >> (C2 - C1)
 * 
 * Special case in merging operators.
 * (C1 - X) + C2    --> (C1 + C2) - X
 * C1 - (X + C2)    --> (C1 - C2) - X
 * C1 - (C2 - X)    --> (C1 - C2) + X
 * 
 * Maybe I will write this: (Actually not).
 * (0 - X) / X      --> 0 + -1 = -1
 * (0 - X) % X      --> 0 + 0 = 0
 * X / (0 - X)      --> 0 + -1 = -1
 * X % (0 - X)      --> 0 + 0 = 0
 * 
 * Special case for non-constant test:
 * (X ^ Y) ^ X      --> Y + 0 = Y
 * (X | Y) & X      --> X + 0 = X
 * (X & Y) | X      --> X + 0 = X
 * (X | Y) | X      --> X | Y
 * (X & Y) & X      --> X & Y
 * 
 * (X - Y) + Y      --> X + 0 = X
 * (X + Y) - X      --> Y + 0 = Y
 * (X * Y) / X      --> Y + 0 = Y
 * (X * Y) % X      --> 0 + 0 = 0
 * 
 * Negative generation rule:
 * 0 - X        --> (-X)
 * X * (-1)     --> (-X)
 * X / (-1)     --> (-X)
 *
 *
*/

这些优化单独来看几乎没啥用，但是结合其他的会有奇效。

CSE

公共子表达式消除是一个常见的优化。对于公共子表达式，我们可以用前者在后者使用处替换。但是，这并不一定是好事情。因为如果这个计算过程是非常廉价的，且计算结果的寿命并不长，那么你重复使用第一次的计算结果，可能会导致一个无效的寄存器占用，甚至不如每次都重新计算。不过由于是在块内，所以一般来说还是 ok 的，不会带来过多的副作用。

UB-elimination

在代码优化的过程中，我们可能会遇到一些含有未定义行为的语句。例如: 整数除以 0 ，一个没有控制流的基本块 (常见于函数无返回值)，读写空指针…… 由于我们可以假定程序是正确的，因此我们可以直接消除这些未定义行为的语句，但这是远远不够的。事实上，到达这些基本块的途径都应当是非法的 (因为假定没有未定义行为)，因此，我们可以把这个基本块从控制流图中直接移除。

具体流程大致如下: 首先标记所有含 UB 的块为不可达。然后直接分析控制流图，其中入口为第一个基本块，出口为所有含 return 的基本块。我们分别从出口/入口进行 bfs/dfs 。只有当一个块可以从入口到达，并且可以从出口到达，我们才认为这个块是可达的。最后，我们把所有不可达的块从控制流图中移除。

特别地，对于那些跳往不可达块的分支，需要把分支转化为无条件跳转。同时，对于 phi 节点中不可达块跳过来的那个格子，其也需要被清空。简而言之，注意下细节即可。

Load/Store tracing

这个技术其实理论上需要用到更加复杂内存追踪技术，例如 equalSet 什么的，但是笔者实在是太忙了，所以没写这么多。笔者实现的简单版本如下:

核心思路是维护同一个地址的 load 和 store ，同一个地址后面的 load 一定是上一次 store 的结果。只有当出现了地址可能重叠的 store ，我们才认为这个位置的 load 是不安全。当然，由于 Mx 里面不存在 reinterpret_cast, void 等危险指针操作，所有类型都是可以追溯的，因此我们可以根据 load/store 的类型来判断是否安全。同时，如果 load/store 的是一个类的成员，那么同一个类的不同成员的地址也是不会重叠的。如果不能保证不会重叠，那么我们只能做最坏假设: 认为已经重叠，该值可能失效。当然，全局变量之间肯定不会重叠。因为没有取地址操作，这也使得整个优化可以变得更加激进一些，不用考虑各种阴间 corner cases.

Inlining

inline 是老熟人了，这里也就不多说啥了，简单来说就是把部分函数代码内嵌到当前位置。不过，inline 还是有不少细节的 (花了我整整6个小时的说) 。首先是要跑函数调用图。由于函数之间可能会互相调用，因此我们需要先用 tarjan 算法缩点，把那些环形的调用关系缩成一个点。在此之后，函数调用图 call-graph 满足 DAG 。我们可以在 DAG 上按照拓扑序逐一 inline 各个函数。当然，每次 inline 完，我们也需要跑一遍优化 pass，因为 inline 完往往能产生新的优化点。例如:

1
2
3
4
5
6
int add(int x,int y) { return x + y; }
int main() {
    int x = 100;
    int y = 10;
    return add(x,-y); // inline + 常量传播直接变成 90
}

由于 Dark 有空了,这一部分又出来了。

在寒假中，笔者重构了自己的编译器。

loop-nest-tree

首先，需要获得循环信息。一个简单可行的方法是直接在 build IR 的时候往标准块上记录一些 metadata 对于一个 general 的 natural loop (换句话说，没有 goto 带来一些奇怪的控制流)，其有这些显著特征:

  • 循环的入口唯一存在，称作 loop header。其支配了所有循环内的块。
  • 循环必定存在至少一个 back-edge，即从循环体的某个块跳到 loop header。
  • 循环之间要么嵌套，要么完全不相交。

因此，我们可以简单的寻找所有的 back-edge (即从一个块 A ，跳到一个支配块 A 的块 B) ，记录所有的 B ，即为所有的 loop header，同时把 A 记录为 loop body 的一部分。然后，对于所有的 loop header ，我们从目前 loop body 开始，沿着 反向流图 bfs/dfs ，直到遇到 loop header ，这样我们就找到了这个循环所有的 loop body 块。

循环之间可能存在嵌套关系，我们可以用一个树形结构来表征这种关系。注意到，两个循环只可能嵌套或完全不相交，不存在其他的情况。因此，我们之前得到的 loop body 两两之间，要么一个完全被另一个包含，要么完全不相交。通过简单的枚举 (但实际笔者的实践借助了支配关系稍稍优化) 即可构建出嵌套关系的树，即为 loop-nest-tree 。

loop-invariant-code-motion

事实上，笔者并没有写这个，而是实现了一个更加 general 的 pass: global code motion。具体细节可参考那篇经典的 GCM/GVN 的论文。

回想一下所谓的 LICM ，其所做的不过是把一些语句移动到了其他的地方。而之所以可以这么做，是因为在 SSA 形式上，只要一个语句 use 在到达这个语句之前都已经被定义了，其即为合法。除了内存操作/函数调用/输入输出 等含有副作用的语句，其他语句都是可以安全的交换顺序，只要满足了合法性。因此，我们可以考虑激进地移动部分语句。

具体而言，我们先固定那些含副作用的语句 (load/store/call/控制流相关)，然后根据 use->def 关系后序去遍历所有的指令，确定每个语句可以被定义的最早的位置 (以基本块为单位)。对于任意基本块 A 中某一语句，我们只需保证该语句所有的 use，其所被定义时所在的块支配了块 A 即可。这个过程被称作 scheduleEarly，伪代码如下:

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
void scheduleEarly() {
    markFixed();
    for (auto block : blocks)
        for (auto inst : block->insts)
            dfs(inst);
}

void markFixed() {
    for (auto block : blocks)
        for (auto inst : block->insts)
            if (isFixed(inst))
                first[inst] = block;
            else
                first[inst] = entry;
}

/**
 * Post-order dfs.
 * First work out all uses of an inst.
*/
void dfs(instruction *inst) {
    if (isFixed(inst)) return;
    if (visited[inst]) return;

    visited[inst] = true;
    auto block = entry;
    for (auto use : inst->uses) { 
        dfs(use);
        // Choose the deepest one in the dominator tree.
        if (first[use]->depth > block->depth)
            block = first[use];
    }
    first[inst] = block;
}

同理，我们也可以对应的 scheduleLate，即为确定每个语句可以被定义的最晚的位置。我们只需根据 def->use 关系，保证 def 被用到的地方都被 def 所在的块所支配即可。换言之，def 所在块是其所有 use 可以处于的最晚的块的 LCA (最近公共祖先) 即可，代码几乎完全一致，这里就不再赘述。

在上面 scheduleLate 的 dfs 函数返回之前，我们得到了每条指令可以位于的最早的块 first 和最晚的块 last (事实上，其是支配树上连续的一段树链，沿着 last 往上跳可以跳到 first)。因此，我们可以尝试规划每条指令所处于的位置。首先，我们显然会让其 loop-nest 的深度尽可能地浅。我们挑选 first 到 last 中最浅地一个块即可。这样的块可能有很多，我们选择就近原则，即尽可能晚地放置这条指令。最后，选择这个循环嵌套深度最浅，且在这个深度上最晚的块，作为真正的 last 返回并记录。

具体细节建议参考论文，当然论文里面貌似伪代码是错的，建议结合支配关系好好想明白后再动手。

loop-induction-variable

很多循环都存在归纳变量，即在一次循环过程中，仅仅加或乘一个常数。而对于常量加上循环变量，其很容易带来一些强度下降，并且给我们带来更多的循环信息(比如循环的次数等等)。

1
2
3
4
5
6
void func1(int *x) {
    for (int i = 0; i < 100; ++i) x[i] = i % 32;
}
void func2(int *x) {
    for (int i = 0, *y = x; i < 100; ++i) *(y++) = i % 32;
}

如上例，两个函数是完全一样的，但是后者在循环内会少一次左移操作 (用来求数组的偏移量)，这便是因为 IR 中 getelementpr 指令的基地址是循环不变量，而偏移量又是归纳变量，我们知道其改变规律。因此我们可以不用借助归纳变量，直接操纵基地址，这样可以减少一次左移操作，而每次循环少一次操作，这个优化力度是很大的。

同时，由于我们知道了 i 的范围，i 一定是非负的，因此 i % 32 可以进一步的被优化为 i & 31 ，这样可以减少一次取模操作，这个优化力度也是很大的，而且非常常见、通用。

以上是归纳变量优化的基本运用。进阶优化还有很多，例如循环展开、把循环连续拷贝改为 memcpy/memmove 等等。极端的优化甚至可以直接把循环求和优化为等差数列求和公式，但是针对性较强，且比较复杂，笔者暂时没有实现。

Scalar-replacement

标量替换指的是把一个没有用到取地址操作的类直接拆成几个标量。例如把一个含有两个 int 的类拆成两个 int 局部变量。

然而，由于 Mx * 类似 Java 的语法，这导致所有类都是引用类型，而且成员函数 (包括构造函数) 都是需要用到地址(指针)的，标量替换的前提看似很难满足。但是，我们可以一步一步来。

首先，我们可以通过分析函数调用关系，我们容易得到哪些 new 出来的类 (其实就是 malloc 的空间) 是已经泄露的。泄露指的是这个分配的空间被存到了其他的地方，导致其离开当前函数作用域之后依然可能被访问到，直接泄露的形式有 ret 和 store ，其也可能通过函数调用，phi 函数传播。

对于那些没有泄露的变量，有一个非常显然的小优化: 我们可以把 malloc 优化为 alloca 。是的，因为其在函数作用域结束后不再会被访问，所以我们可以用更加紧密的栈空间代替堆空间，其可以增加缓存命中率，防止污染缓存，效果还是很好的，尤其是对于那些不是特别大的中小类型。

然后，再注意到我们其实有 inline 优化，因此很多时候我们会把短的成员函数直接内联了，从而实际上最后我们对于一个类指针的操作仅限于 getelementptr 。在这样的情况下，我们便可以把这个类标量替换，拆为其各个成员。显然，聪明的您肯定也发现了，那些可能被潜在标量替换的变量，一定也是 malloc 优化成为的 alloca 变量。

以上便是本人标量替换的主体思路。由于时间限制，笔者只完成了标量替换的第一步: 把未泄露的小类型的 malloc 语句替换为了 alloca 。在特定的测试函数中，其性能能提升 10 倍甚至是 9 倍，当然核心原因还是因为其对缓存友好，且避免了费时的 malloc。

Others

其他小优化还有一大堆，但是时间限制暂时不详细写了。包括但不限于:

  • 尾递归优化
  • Mx *语言特性优化
  • buitlin 函数内联
  • UB 信息利用

ASM

暂时先摸了。计划讲讲线性染色 Linear scan register allocation 。事实上，笔者写的超级烂，现在还在改，之前写的 Linear scan 可以说是完美结合了 Linear scan 质量低的缺点和 Graph coloring 非线性的缺点。

计划改为 SSA 上寄存器分配，其不仅线性而且质量不低。不过前提是我的有空啊啊啊

后记

没人会看到这里的吧我也不知道为什么，但是这次编译器写的我很累，可能是因为自己真的去证明了很多优化的正确性以及复杂度，同时还自己构思了很多优化(虽然基本都是论文里面的弱化版)，或许以后不应该浪费这么多时间自己瞎想。写的真的挺烂的，烂的不能再烂了，收集了一堆信息却几乎没用上多少，最后榜一还是偷上来的……唯一的好处，或许是对于 C++ 工程代码的经验积攒了不少。