Explore RCompiler
埋一个坑，有空整理一下自己在完成RCompiler和学习编译原理过程中学到的东西。况且下学期也选了高编，也可以往里面加后端和优化的内容。
Parser & Semantic Check
毕竟似乎是第一年手搓parser，还是写两句吧，parser主要问题在于对expression建AST，这里推荐阅读Pratt Parser，伪代码和原理写的很明白了，其他东西顺序就行。
Semantic Check 我的方法比较神秘，可以实现两遍结束，但是不建议吧，因为写到IR时我发现我完全忘了维护左值右值的信息了，于是又回炉重造加逻辑了，所以建议老实按照要求扫4、5遍。
别的感觉没啥好说的。
IR Generation
和Parser建AST的过程几乎一致，递归写，比较容易，调试也有不少技巧，笔者实现了24小时调完。但写的时候由于笔者一开始设计有问题，导致经历了一次大的代码重构，外加笔者去年年底生病了，导致写代码写的非常痛苦。
Codegen
实现：不做任何寄存器分配，所有东西都spill 到栈上，每次需要操作时，把变量从栈上load 到寄存器里，操作完了再store回去。但这样会造成大量的load和store指令，性能很差。
一些可能的雷点： 能容纳函数参数的寄存器数量有限，只有a0-a7 8个寄存器，参数大于8时需要spill到栈上；m-extension 指令注意符号拓展；指针解引用时的load store操作；reimu模拟器栈内存默认是32K，很多点需要认为调大栈内存，亲测4096K差不多了；函数返回值是数组或结构体时需要最后将返回值写入a0寄存器；phi指令在ASM中时不存在的，需要人为拆解，一个简单的想法是，每次处理IR Br指令时，前瞻一下跳转到的块内有没有phi指令，如果有，就把phi指令的结果先spill 到栈上保存下来，因为ASM无法记录你是从哪个块跳转过来的。
Register Allocation
lz先写（借用一些神力）了一版linear scan寄存器分配算法，但写完调完的第二天高编集会得知要写图染色，于是被迫再写一遍图染色reg alloc。
Linear Scan
线性扫描寄存器分配相对来说比较好理解，首先我复用了codegen部分的一部分代码，做出的修改是，在codegen中对于所有临时变量，我都通过存储在栈上，需要的时候load/store访问，而在reg alloc 里，我先给这些临时变量都分配了一个虚拟寄存器，以便我后续进行reg alloc。线性扫描寄存器分配的核心在于CFG 的构建和live interval的计算。每一个codegen得到的ASM Block都对应了一个CFG block，用来保存这个block的首指令和尾指令编号、def/use 变量集合、liveIn/liveOut 变量集合等信息。首先我们构建一张CFG，方法就是通过块内跳转指令找后继块。得到CFG后就可以计算每个块的liveIn/liveOut了，这是一个虚拟寄存器到存活区间的映射，我们有如下关系：
1 | liveIn[B] = use[B] U (liveOut[B] - def[B]) |
进行反向迭代直到liveIn/liveOut不再变化为止。
接下来就可以计算每个虚拟寄存器的live interval了，live interval是一个区间，表示这个寄存器在程序中被定义和最后一次使用之间的范围。计算live interval的方法是遍历CFG中的每个块，对于每个块中的每条指令，更新对应寄存器的live interval。最后我们就得到了每个虚拟寄存器的live interval，可以用来进行线性扫描寄存器分配了。线性扫描寄存器分配的核心思想是按照live interval的起始位置对虚拟寄存器进行排序，然后从左到右扫描这些live interval，尝试将它们分配到物理寄存器上。如果当前扫描到的live interval与已经分配的live interval有重叠，那么就需要将其中一个live interval spill到内存上。
值得注意的是，我们需要考虑跨call的情形。在RISC-V架构中，寄存器分为caller-saved和callee-saved两类，caller-saved寄存器在函数调用时需要保存和恢复，而callee-saved寄存器则由被调用函数负责保存和恢复。因此，在进行寄存器分配时，我们需要确保跨call的live interval不会被分配到caller-saved寄存器上，否则就需要将它们spill到内存上。而在进入每个函数前，我们需要将callee-saved寄存器的值保存到栈上，以便在函数返回时恢复它们的值。
Graph Coloring
TBD 其实吧，我觉得 Mx Tutorial 里图染色的讲解已经非常清楚了，笔者甚至都不太打算写。。。anyway，这个再说（
IR Generation Optimization
Mem2Reg
mem2reg 优化本质上是一种去alloca的优化，想法是将本来分配在栈上的对象移动到虚拟寄存器中，首先我用了一个晚上快速写了3种最基础的mem2reg优化：
- alloca 但没用过的不alloca（毫无效果）
- 只被定义了一次，那么所有值都可以用定义的值代替（效果明显）
- 如果一个alloca 只在当前块被使用，那么所有的use都可以被向上最近的一个def替代（效果微弱，可能是因为很少有变量只在一个块里出现吧）
接下来主要分析一下第4种mem2reg优化：如果一个 alloca 只被 load 和 store，那么可以通过在支配边界插入 phi 指令，并将所有的 use 替换为对应的 phi 指令的结果。其实笔者在思考第3种mem2reg优化时就隐约有了推广到跨block处理def/use的一些想法了，利用phi确实是其中之一。
支配树的构建与支配边界
支配集可以这样理解，就是要想到达某个块，必须经过的块的集合，而这构成了一条链，接着就可以构造出支配树了。构建方法是先构建出CFG得到前驱后继关系，然后给所有前驱块找LCA。接下来需要找到支配边界，首先明确支配边界的定义：一个节点 X 是节点 Y 的支配边界，当且仅当 Y 在 X 的一个前驱节点的支配集中但 Y 不在 X 的支配集中。计算方法是遍历前驱块，如果前驱块的支配边界自然是当前块（前驱块数量大于2），往上找前驱块的上一个支配块，递归，直到也在当前块的支配集里为止。
Phi指令的插入和指令删除
Phi指令的插入方法是：对于每个alloca，找到所有def块，遍历def块的支配边界，在支配边界块首插入一个phi指令，重命名入口顶部的 phi 指令所定义的值为alloca定义的值，接着递归地再支配边界的支配边界添加phi指令。接着对每一个被alloca出来的量维护一个栈，每遇到store指令或者新插入phi指令，就把对应的值压入栈顶，每遇到load指令，就把栈顶的值替换掉load指令的结果（和前三种优化类似的，维护一个replaceMap）。同时用当前栈顶更新phi指令的参数。最后，对当前基本块在支配树中的子节点进行递归处理。
codegen中对phi指令的消除
phi指令并不是risc-v指令集中的指令，所以在codegen阶段需要将phi指令消除掉。事实上，笔者本人在写mem2reg优化前先实现了一个版本的phi指令消除：在每个前驱块中插入一个副本（一个新的虚拟寄存器），在末尾进行mv dst tmp的指令添加。很简单的想法，鉴于是虚拟寄存器存储所以不存在数据冲突问题，也顺利通过了测试点，不过事后来看，这种写法有性能上的缺陷：
- 徒增虚拟寄存器数量，给regalloc带来压力
- 产生更多死代码
更标准的解法应该是————拆分关键边！想法是在关键边上加入一个块，把要给到下游块的值先copy到这个块中。but转折来了，笔者实现之后进行了一个测试，发现和我原本的实现竟然没有任何区别，是的，没有一个测试点有任何一点性能上的差异！于是笔者细细品味了一下，发现这两种实现本质上似乎是基本等价的。没啥说的必要了。建议用我第一遍的实现，因为实现难度低且非常容易理解。
Dead Code Elimination
从死代码消除开始就是上古 Mx Tutorial 里不涉及的部分了。
DCE的目的是删除那些“计算了一个值，但这个值不会影响程序可观察结果”的指令，举个例子：
1 | b = 114514 |
其中 c 的值在后续程序中永远不会被使用到，所以c = b + 1 是死代码，可以被删除掉。
如果你已经实现了linearScan regalloc，那么恭喜你，DCE的剩余码量不超过30行，在每个块中，我没维护一个liveSet，初始时是liveOut集合，逆序遍历每条指令，如果指令的 def 变量不在liveSet中，那么这个指令就是死代码，可以删除掉；如果指令不是死代码，那么就把它 use 的变量加入liveSet中，并把它定义的变量从liveSet中移除掉。多次遍历直至没有代码被删除。