HIGH IR
Return Insertion
正如字面意思，这个 pass 很简单，就是给所有没有写上 return 指令的函数补上 return 指令。也不需要考虑很多，看见缺了就填，反正后面会进行的 pass 会消除这个 pass 的副作用。
简单常量传播
在 sysy （c 语言的一个子集） 中，store 语句只会在这几种情况下出现：
int a = 1声明语句a = 2赋值语句void foo(int a)函数声明
load 语句只会在这几种情况下出现：
int b = a + 1声明语句if (a)条件语句，可以认为循环的 cond 部分也是条件语句return a返回语句foo(a)函数调用
若在线性顺序下有如下情况：
|
|
我们目前只考虑 i32 和 f32 变量，不考虑数组。
很容易想到，在调用 foo 前的语句，可以把 a 视作常量，这样 b 就可以拿着 a 的值折叠。虽然中间对 a 进行了一次修改，但是我们可以记录这次修改，这样传播到 c 的就是修改后的 a 了。
在线处理，按照顺序扫描，我们依次插入 a，b，c 到「可以进行常量传播的值集合」。
由于 sysy 不允许函数传递指针/引用，函数其实是无法修改外部变量的值的。很容易引申出来：函数前记录下来的「可进行常量传播的值集合」不会被 call 函数指令的副作用改变，所以 call 指令对我们的常量传播没什么影响。更加准确的说，call 指令只会影响全局变量。
进一步，我们只需要注意「可能会修改可以进行常量传播值集合」的指令。在 sysy 中，就是三个指令 call，if，while。
由于在目前阶段还没有进行 mem2reg，进行活跃变量区间分析比较困难，我采取一个很保守的优化原则。遇到 if，while，则清空当前维护的「常量传播值集合」，遇到 call，则清空「常量传播值集合里面的全局变量」。然后对每一个 op 都尝试进行常量传播即可。顺便也把复制传播做了一下。
这样的效果应该还不错，因为声明周期很长的变量远少于声明周期短的 tmp 变量。
简单死代码消除
这个 pass 也比较简单，简述一下流程。
我们维护一个 liveset 和 worklist。首先标记出不能删除的指令加入到 worklist，他们有：
- 外部链接函数
- store 指令
- ret 指令
- 控制流终结符
然后进行反向传播（倒序遍历），如果一个指令处于 worklist，那么他自身和其引用的指令也要加入到 liveset 和 worklist，如果一个 if/while 内部有指令在 liveset 中，那么保守起见，整个 if/while 都加入到 liveset 中。反向传播完毕后，就可以清除所有不属于 liveset 中的指令了。这就是 bfs 吧
Inline 优化
Inline 其实是一个非常复杂的优化，在什么时候应该 inline，这是一个 NP hard 的问题，一个函数是否应该 inline，我们需要几个标准来权衡：
- inline 前后是否有性能提升。
- 在上面这一点，就算 inline 没有显示的性能提升，如果在 inline 后，能够进行更多 pass 来优化，导致最终结果比 inline 前好。
- 我们是否能够承担 inline 带来的副作用，比如栈开销。
- inline 会导致代码体积变大。
- …
不仅仅有上面列出的点，我们还要考虑什么时候进行 inline，以什么顺序，付出多少代价等等。。。是一个非常复杂的问题。
由于其是一个 NP hard 的问题，我们很难找到一个多项式时间内处理 inline 的算法，通常我们基于启发式算法来处理 inline。
所以呢，我从 llvm 剽窃 偷学了他们的启发式算法（阉割版）。接下来要做非常复杂的算法了哦~嘿嘿嘿嘿
参考论文：http://impact.crhc.illinois.edu/shared/papers/p246-chang.pdf
描述一下宏观流程：
- 构建加权调用图
- 强连通分量分解
- 内联决策
- 代码转化
思路是这样的，代码的遍历流程天然和图相符，我们采用图来建模是很自然的想法：将函数视为节点，每个 call 指令视为弧，就能构建出一个有向图。
这样建模的话，我们可以很轻松的发现递归函数：一个环。在有向图中，环的存在很不好处理，所以我们进行 SCC 缩点，也就是 tarjan 算法。缩点后再跑一遍拓扑排序即可。在 topo 过程中，我们对每个 call 指令计算 cost，再设置一个阈值（threshold），与 cost 比较，来判断是否应该内联，最终依据结果进行内联。内联后再跑一遍 CP 和 DCE。
思路很简单，难的是如何计算 cost。inline 的 cost 的时刻在变化的，并且他的阈值也不同，举个例子，一个在 while 里面被调用的函数 inline 的性价比明显比在 while 外面的函数 inline 高。为了权衡这些复杂的情况，我们的 cost 的计算也必须是动态的。
按照 LLVM 的 cost 体系，基础指令/内存访问的 cost 为 5，跳转/分支的 cost 为 10，函数调用的 cost 为 25，昂贵运算 mul/div 等在 10-20 左右，全零初始化的 cost 是 0。
然后是奖励分，如果能够 SRAO 优化，则减 15-20。如果能够常量折叠，将指令 cost 变为 0（这个很重要，比如一个递归的斐波那契函数 fib(12)，可以不断 inline，常量传播，最终优化成一个具体的数值）。
我们的初始阈值设为 225，在一定的情况下，我们会对阈值进行调整，比如说在 while 里面的函数，我们采用 $T_{final} = T_{base} + (depth \times 150)$ 公式 scale up。如果在一个经常为 false 的语句，比如 if (bad situation) { call function; break; } 这种我们就要降低其阈值（$\div 10$），因为这种内联反而没那么划算。
最终我们依据 cost < threshold 的结果来判断是否内联。当然存在一些特殊情况，有些很小的函数（指令数 < 10），简单函数包装（包装另一个函数返回结果）我们可以直接内联。还有我们得考虑函数的栈开销，如果全部 inline 了导致爆栈可不太好。