BUAA Compiler 实验报告

说在前面

本篇文章的内容并不能达到可以让你跟着做完整个编译器项目的程度，它只是我最终总结时的一些回忆，而非施工现场。

倘若能在某个时候激发起你的共鸣，给予你信心或是方向，那便已是极好的了。

整体架构

bzh学长的架构

顶层文件夹是Compiler与config，还有frontend,midend,backend,utils,optimise,error六个包。

error进行错误处理，前端处理词法与语法分析，中端进行语义分析，LLVM体系定义与中间代码生成，后端进行MIPS语言体系的定义，optimise进行中端优化，utils是一些功能启动、文件输入输出、性能结果展示等附加功能的定义。

compiler首先调用工具进行testfile的读入，然后调用前端得到tokenlist与语法树，语法树树根传给中端，中端遍历语法树得到符号表与中间代码结构，将中间代码模块传递给optimiser进行优化后，再传递给后端，后端递归执行toMips，得到最终的MIPS模块结构。

所有产物都可以借助IOHandler输出为文件。

再详细的架构再讲就讲不完了。

我的简单改装

在细节上的架构，我和学长代码保持了较为高度的一致，最多只是将某些类进行合并或者拆分。

但在宏观上我根据自己的主观理解，进行了较大的调整。不过意义也不是很大。

我顶层的包分为前端，中端，后端，错误与工具。

frontend处理词法分析，语法分析之外，我没有传递语法树，而是继续在前端进行语义分析与中间代码生成。因为这一段本就是与源代码高度相关，语法树更是直接来源于源代码的文法。

我在思考，如果真的做到修改源代码不必修改midend的话，midend里该有的内容，可能只有llvm那个文件夹。而visit与symbol都是属于与源代码有关的内容，如果更改了文法，肯定是要有改动的。

因此我前端内部的文件夹有lexer,parse,ast,还有llvm_ir这个包，这个包包含symbol与visit，主要负责的就是产出中端所需的架构。

midend在严格意义上，包含的动作只有中间代码优化。此外他还包括llvm的架构定义。因此里面包括llvm和optimiser两个包。

backend则涵盖中间代码生成目标代码所需要的架构信息与Builder。有一个现象值得注意：后端的实质翻译工作 toMips() 实际上定义在midend文件夹，也即llvm文件夹，因为从前往后推进的过程中，后端貌似就是要依赖于中端的架构才可以工作。

那如果后端发生改变，需要更改的为什么是midend文件夹而不是backend文件夹呢？我想，可能只有优化严格属于中端，中端到后端的toMips函数可能只是身在中端，其实不属于中端吧。

无论怎样，关于我的代码架构，我可以说，如果期末考试源代码文法发生改变，我确实只应当修改frontend文件夹。

词法分析

刚开始接触编译器的搭建时，面对复杂多样的文法，茫然的情绪是毋庸置疑的。但我一直对词法分析抱有美好愿想，因为它看起来只不过是把token提取出来，这和整体的结构关系不大。

但尽管是相对独立的结构，也需要融入整个大型框架。因此我借鉴了往届的优秀代码，对编译器整体的前中后端与错误处理框架形成了基础认知，才开始了编写工作。

不过官方已经给出了确定的token类别，其实词法分析的问题并不是很多。需要注意的点是注释的处理，可以检查一下/*/与/***/能否正确处理。

Oct.4更新：
注释相关的处理出现了问题！

跨行的注释请注意不能无脑read，要记录行数的增加！

对于//，读取到\n之后要再read一次去掉换行符，否则会影响行数记录

Oct.22更新：
注释相关的处理再次出现了问题！参见讨论区。

Jan.1更新：

jym同学的测试点中包含转义字符相关内容。所以顺便也实现了一下。

从架构而言，首先要形成frontend/midend/backend/utils这样的系统结构观念；其次在frontend中需要有一个frontend类，还要有parser/ast/lexer等等。我们在lexer中主要实现的就是针对读取到的char分析出是什么单词，并加入单词列表，因此还需要实现Token类和token类型。

另外，作为最起始的框架，IO操作也是一个关键点，不过参考学长代码之后不难解决其处理模式，放在utils包中很有结构感。

语法分析

语法分析的难度个人认为远超词法分析。因为他看似只是进行结构的划分，但是结构的性质，也就是语义分析部分极为重要，要尽可能形成相对科学合理的结构。而这个结构，虽然文法已经给出了一些提示，但还是有许多需要自己决定的结构。

FIRST集

对于多分支的处理，我们常常使用FIRST集来尽可能区分不同的分支。

简单的比如Decl → ConstDecl | VarDecl，可以用const来区分。

稍微复杂一点的比如BlockItem → Decl | Stmt，经过多层分析发现，First(Decl) 包括 CONSTTK | STATICTK | INTTK，并且这些都不出现在stmt中，从而可以区分。

最复杂的就是Stmt了，他的情况极其多，虽然大多数还是很好区分的，比如if,for,continue,break,return,printf,block。但是不好区分的就是LVal=Exp;和Exp;。原则上我们总可以发现在某个时候可能出现可观测的差距，但是我们不妨可以使用这样的一种方法：

回溯

仔细观察LVal=Exp;和Exp;，可以知道LVal也属于Exp，因此一定可以被Exp识别。那么只需要看读取Exp之后的符号即可，如果是=，则说明是前者。

但是原则上，LVal和Exp是不同的，形成的语法树结构也不同。因此前面的分析只能用来判断，而不能用来构造语法树。

这时候的识别就需要被回溯了。我们需要注意三点：

尝试的时候不能更改树的结构，可以new，可以parse，但是不能add到树上。
尝试过程中如果遇到语法错误，不可以记录。
在尝试前标记当前位置用于回溯。

期中考试 Update：

考了回溯，不过不能像原来那样直接预读Exp了，或者说公共部分不是已有的非终结符。

不过没关系，你只需要自己创建这样一个非终结符就好了，这个非终结符的parse也只需要复制公共部分的相关内容就好。

我们只需

记录位置，关闭报错

parse完这个公共部分

通过peek找差异，判定好类型

回到原位，开启报错

按照你识别的类型addNode即可。

递归

对于Exp的那一堆，经过一系列拆解，会发现真正的递归其实只出现在UnaryExp中。不过这里是右递归，所以我们可以大胆递归。

右递归本来就是安全的，不安全的是在重重循环中从未consume的左递归。

左递归结构还原

针对Exp出现的大量左递归，我们一般的处理方法就是直接消除左递归，把LOrExp → LAndExp | LOrExp '||' LAndExp 改成LOrExp → LAndExp {'||' LAndExp}

这用来解析当然是没问题的，但是这其实已经修改了文法，导致语法树的结构发生了变化，输出的结果就会不一样。

因此，我们需要对语法树进行还原，使其恢复原来的结构。我们知道除了最后一个LAndExp是真的LAndExp，其余的其实都是LOrExp->LAndExp。所以我们要new一个新的LOrExp，把LAndExp放进去，然后再装进components里面。

语义分析

说到语义分析，主要内容就是符号表管理与错误处理两大部分。其中关于符号表的内容，仅从通过测试来考虑的话，只需要考虑decl语句即可。错误处理部分相对就更加复杂，同时也需要利用符号表的相关信息。

符号表管理

这个部分最难的地方应该在于结构的组织，我参考了往届优秀代码，构建了Symbol相关的多个类，类型上大体分为变量与函数，功能上还有全局管理的SymbolRecorder 以及每个Scope的SymbolTable。

Symbol本身的属性在这个阶段相对简单，我们主要关注名称，类型和初始值。

SymbolRecorder需要着重管理的就是符号表的组织与切换，并实现addSymbol方法。当然addSymbol还是要落实到 SymbolTable的addSymbol方法上。

SymbolTable的作用就是管理符号的声明与查找，主要的方法是addSymbol和getSymbol，其中关于addSymbol的调用，就在VarDef与FuncDef中；关于getSymbol的书写，需要注意scope规则。

错误处理

break与continue

这一点我借鉴了学长的代码，在parse的过程中完成了break与continue的处理。它相比于重新 visit一遍更加简单，因为parse过程中结构已知。

redefine与undefined

这两个的区别在于，一个只能看当前scope，一个必须看完所有嵌套scope。当前scope就直接看当前的符号表就可以，嵌套的scope其实就是getSymbol的过程。

函数调用

函数调用的错误处理主要是参数的数量与类型。数量还比较好解决，类型的判断，尤其是实参就复杂的多。

实参是Exp，要判断Exp是不是数组，就要求他必须是单一的AddExp,单一的MulExp,单一的UnaryExp, 单一的PrimaryExp,单一的LVal，并且这个LVal 的symbol类型必须是数组。

当然这么简单的判断条件是基于课程组的文法简化

return

这里涉及到两种错误，int函数最后一句不是return，以及 void函数存在return Exp

int函数要想完备地判断是否能return还是比较复杂的，所以题目加以限制，必须是最后一句，其实也就是 Block的BlockItem的最后一项。

关于void函数的return，要详细地寻找到每一个return，就不仅要寻找当前的Block的BlockItem中的ReturnStmt, 还要考虑其他Stmt。

容易想到的是BlockStmt，容易被忽略的则是IfStmt与ForStmt。他们两个也会嵌套Stmt，也需要进行寻找。

中间代码生成

过了很久，我终于决定认真复盘这个最为复杂的单元。

中间代码生成仍然属于前端的内容，他和语义分析一样，都是与源语言文法、语义紧密相关的内容。

二次扫描语法树——简介

我们中间代码生成的过程，就是要根据语法树的信息进一步提炼出抽象的中间代码逻辑。

大家在做语义分析的时候也会注意到，符号表蕴含的信息只是一次小范围的总结，并没有对控制流逻辑有所分析，所以我们AST的信息并没有提取足够，需要二次扫描，在扫描的过程中顺势输出有结构的中间代码。

不过要想知道怎么输出中间代码，我们必须先要深入了解LLVM IR。

我们生成的LLVM IR必须是有一定结构的，我们将利用这个结构去递归完成toMips()的内容。

LLVM-IR体系构建

这个结构的顶端就是 IrModule 。

IrModule 包括以下四个部分：

functions：每个 FuncDef（包括Main）映射成 IrFunction，内部是 IrBasicBlock。
globalValues：遇到全局/静态变量时要映射成 IrGlobalValue。
stringConstantMap：printf 拆出来的字符串常量以 IrConstantString 形式缓存。
declares：IO 内建函数声明（getint/putint/…）也要预置在LLVM IR中。

输出 IR 时，IrModule.toString() 先打印声明、常量、全局变量，再打印所有函数体。

value

IrValue 是LLVM IR中最基础的概念，包括常量、变量、函数、乃至指令、基本块，都属于IrValue。指令就是可以利用其他IrValue值的IrValue，他自己的值也可以被其他指令使用。也就是说 IrValue 是一个统一接口，提供 getIrName()、getIrType()、toString()、toMips() 等通用行为。

use

在未来的优化部分，我们希望自己可以知道 IrValue 之间的关系，而不是只有代码的简单翻译，因此我们要引入 IrUse 与 IrUser，强调 IrValue 之间的依赖关系。

具体怎么构建use关系，还需阅读下文的Instr部分。

每个 IrValue 都能用Value + Type + Use这套语言描述。

type

IrType 是所有type的抽象基类，每个 IrValue 都要携带一个 IrType。

核心的静态方法 convertType(originValue, targetType)：

转 i32，若源已是 i32 就直接返回，否则生成一条 ExtendInstr。
转 i8：i32 -> TruncInstr，i8 保持不变，i1 -> ExtendInstr。
转 i1：本质上是转布尔数，此处不是截断，而是icmp，与0比较。
如果目标是数组，则递归转换其元素类型，保证数组初始化时的元素类型一致。

IrBaseType：内置的标量类型常量（VOID, INT1, INT8, INT32），toString() 对应 LLVM 文本 void/i1/i8/i32。

IrPointerType：包装任意目标类型，toString() 追加 *。

对数组/全局变量来说，我们用 IrPointerType 描述地址，这也是 GepInstr、LoadInstr 根据 getTargetType() 决定步长的依据。

IrArrayType：记录数组长度和元素类型。 [N x i…]。

IrFunctionType：只强调返回类型（参数类型由 IrFunction 的 IrParameter 决定）。

IrBasicBlockType：它没有信息量，就仅仅是BasicBlock，没有人需要getType来确认，toString() 为空字符串。

但我们需要有一个 IrType，使得 IrBasicBlock 能继承 IrValue。

具体的value

IrFunction

IrFunction 类型是 IrFunctionType，属于IrUser。

包含 parameterList 保存 IrParameter，还包含 basicBlockList 是顺序化的 IrBasicBlock。

toString() ： define dso_local type @name(param...) { basicBlock IR }。每个 IrBasicBlock 的 toString() 被拼接成函数体。

isMainFunction() 检查名字是否为 @main，决定这个IrFunction是整个程序的入口。

IrParameter

类型取决于源代码。

独立出来的作用就是因为其toString是函数参数调用这一特殊形式。

toString() ： irType + " " + irName

它也只是一个普通的变量，在自已的作用域里被use。

IrBasicBlock

IrBasicBlock 类型是 IrBasicBlockType.BASIC_BLOCK。

核心数据：instrList，块就是指令的合集。

toString() 打印 b_x: + 指令的LLVM。

基本块在代码优化意义重大，不过仅从代码生成角度考虑，他也只是一层无意义的包装。

IrLoop

他其实并不是IrValue。准确来说，他只是一个栈的结构体单元。

它用来记录四个基本块：条件 condBlock、循环体 bodyBlock、步进 stepBlock、退出 followBlock。

在面临多重循环时，栈式的结构可以帮助你更好地确定当前循环的各项信息。

IrConstant

IrConstant 是编译时常量，包括以下三种：

IrConstantInt：最常见的标量常量，类型固定 i32。irName 就是数字文本。toString() 输出 i32 数字文本。
IrConstantArray：用于全局/常量数组初值。内部保存元素的类型，元素常量列表 valueList 与 arraySize。toString() 生成 [N x type] [elem0, elem1, …] 或 zeroinitializer；若初始化列表不足，会自动补0。
IrConstantString：封装字符串字面量。类型是 i8* 指向 [len x i8] 数组（len 包含 \0），存储时会把 \n 转义为 \0A。toString() 生成 @s = constant [len x i8] c"…\00"。

Instr

最后一类 IrValue 就是我们最关键的 IrUser: Instr！

每条指令既是可被引用的IrValue，又可引用其他值。

分类：

算术/逻辑：AluInstr（加减乘除/模）、CompareInstr、ExtendInstr/TruncInstr（类型转换）。它们通常产生新 SSA 值，toString() 形如 %v1 = add i32 %v0, 1。
内存与地址：AllocateInstr（栈分配）、LoadInstr、StoreInstr、GepInstr（数组/指针偏移），MoveInstr 用于优化阶段的平行拷贝。
控制流：JumpInstr（无条件跳转）、BranchInstr（条件跳转）、ReturnInstr。它们通常不定义新值，但会更新基本块的前驱/后继关系。
调用：CallInstr 负责函数调用，收集参数列表并决定返回值类型。
IO：instr/io 目录下的 PrintIntInstr、PrintCharInstr、PrintStrInstr、GetIntInstr，属于自动生成的declare。

指令	LLVM IR
AllocateInstr	%vx = alloca <element_type>（数组为 [N x i32]）
AluInstr	%vx = add/sub/mul/… i32 lhs, rhs，操作符小写，始终声明 i32 操作数
BranchInstr	br i1 cond, label %true, label %false，cond 必须是 i1，块标签用 %
CallInstr	call type @f(args…)，每个参数写成 type name，若函数有返回值则前缀 %vx =
CompareInstr	%vx = icmp eq/ne/sgt/… i32 lhs, rhs
ExtendInstr	%vx = zext type name to type
GepInstr	区分数组和普通指针：数组时打印 getelementptr inbounds [N x target_type], ptr_type ptr, i32 0, offset_type offset，否则为 getelementptr inbounds target_type, ptr_type ptr, offset_type offset. 原因在于gep是计算基地址+索引*类型大小，支持多级索引，而数组第一级索引是0，第二级索引才是数组内偏移
JumpInstr	br label %target
LoadInstr	%vx = load target_type, ptr_type addr
ReturnInstr	ret void 或 ret type value
StoreInstr	store type value, ptr_type addr
TruncInstr	%vx = trunc type name to type，用于 i32→i1/i8 等截断。
GetIntInstr等IO类	%vx = call i32 @getint()

特别注意：

为了避免大量的重复内容，我们将addInstr与addUse这两个操作直接放置于构造函数内。

指令本身不复杂，复杂的是下一部分，也就是怎么生成LLVM IR。

二次遍历语法树——实操

架构构建者：IrBuilder

IrBuilder 是生成中间代码的核心部件之一，它持有全局单例 IrModule，并通过静态字段跟踪当前 IrFunction、IrBasicBlock，以及循环栈 loopStack，让 Visitor 在任何时刻都能把新指令、新块挂到正确的位置。

模块管理： IrBuilder需要负责组织各模块之间的关系，包括创建Function,Block,Instr,Global_Var以及addBlock,addInstr等操作。

命名服务：newFuncName, newBasicBlockName, newGlobalVarName, newLocalVarName 统一生成 @f_name, b_#, @g_#, %v# 等符号。对局部命名，Builder 以函数为粒度维护计数器，保证每个函数的 %v0, %v1, … 独立递增。

架构填充者：Visitor

我们终于谈到了中间代码生成的核心，也就是真正二次遍历语法树的过程。

Visitor.generateIr 是中端的入口，持有完整 CompUnit，依次对全局 Decl、普通 FuncDef、MainFuncDef 调用专门的 Visitor。

Decl

VisitorDecl：处理所有的decl语句，区分好全局、局部static与局部，以及数组与标量。

我们只依赖 VarSymbol 中的语义信息（作用域、类型、是否数组、初值列表等）就足以完成翻译。

generateDeclIr(Decl) 先区分常量/变量，逐个 ConstDef/VarDef 处理。

全局/局部静态变量：

无论是否const，VarSymbol.isGlobal() 或 isStatic() 时使用 IrBuilder.getNewIrGlobalValue(new IrPointerType(type), initConstant)。初始化的值通过symbol构造 IrConstantInt 或 IrConstantArray，数组要自动补零。生成的 IrGlobalValue 存回 symbol.setIrValue，后续访值都指向这个全局指针。

局部变量：

统一先 new AllocateInstr(type) 在栈上开空间，再视情况写初值。

非数组：若提供初值（ConstDef 一定有，VarDef 可能有），就 new StoreInstr(value, alloc)；常量的初值来自符号表中提前计算好的 initValueList。
数组：遍历初值表达式列表，对每个元素 VisitorExp.generateExpIr → convertType → GepInstr → StoreInstr，未提供的尾部元素由 ConstDef 分支提前填 0。

常量的局部分支和变量一样，区别在于 VarSymbol 里 initValueList 已经静态求值完毕，而变量不能保证第一遍扫描的时候就已求值，而是用 VisitorExp.generateExpIr 来生成现场计算的表达式。

FuncDef

在遇到函数节点时利用 IrBuilder 创建 IrFunction，把形参列表映射成 IrParameter，再借助局部 Alloc+Store 把参数写入栈。随后 VisitorBlock。

需要注意作用域的改变时机：在解析形参时进入子作用域，Block生成完毕后退出子作用域。

Block

VisitorBlock 遍历 BlockItem。遇到 Decl 转交 VisitorDecl，遇到 Stmt 转交 VisitorStmt。

Stmt

VisitorStmt 以语句类型为分发点：IF/FOR 创建新的基本块并通过 IrBuilder 管理跳转；ASSIGN 找到左值地址（调用 VisitorLVal）并生成 StoreInstr；PRINTF 先把字符串拆成常量块和占位符，再插入对应的 IO 指令；RETURN 根据函数返回类型自动补 0。循环语句通过 IrLoop 堆栈记录 break/continue 的目标块。

VisitorStmt 根据 StmtType 分别处理不同类型的语句。

LVal：

后面会用到，这里先讲清楚： VisitorLVal.generateLValIr(lval, false) 给左值对象的值，

VisitorLVal.generateLValIr(lval, true) 给左值对象的地址。

具体而言：
- 返回地址时：
  - 非数组变量直接返回符号表记录的 IrValue（通常是 AllocateInstr / IrGlobalValue），即地址。
  - 针对数组或指针：先取符号的 IrValue。如果这是一个指向数组的指针(作为 IrPointerType，其 target 还是指针)，说明它需要先 LoadInstr 读出真实首地址；然后根据下标生成 GepInstr(pointer, index)，当然要先生成算出index的IR。
- 直接取值时：
  - 若符号是标量，直接 new LoadInstr(symbol.getIrValue()) 取内存中的内容。
  - 数组情况更复杂：首先特别注意：若 pointerType.getTargetType() 仍是 IrPointerType，说明 symbol.getIrValue() 存的是指向指针的地址，必须先 LoadInstr 取到真正数组指针。
  拿到数组指针之后就继续找值：
  - 如果没有下标（size == null），意味着把整个数组当作指针使用，返回 new GepInstr(pointer, new IrConstantInt(0))，相当于数组首地址。
  - 如果有下标，就先算index，然后 GepInstr(pointer, index) 计算元素地址，再 LoadInstr 读取元素值。
block：

进入子作用域，VisitBlock，离开子作用域。
exp与assign：

generateExpStmtIr 纯调用 VisitorExp.generateExpIr，如果没有表达式就直接返回；
generateAssignStmtIr 先用 VisitorLVal.generateLValIr(lval, true) 拿到地址，再把翻译右侧表达式，并转成目标类型，最终 new StoreInstr(value, address)。
printf：

手动解析格式串：遇到 %d/%c 时调用 VisitorExp 获取实参，转换类型后 PrintIntInstr/PrintCharInstr; 普通字符串则直接用 IrBuilder.getNewIrConstantString + PrintStrInstr。
if:

先建 ifBlock（真分支），若有 else 再建 elseBlock.

VisitorExp.generateCondIr(cond, ifBlock, elseBlock/followBlock) 生成条件跳转。

特别注意！ cond和exp的不同点在于cond的解析为了处理短路求值，是自带跳转功能的！

因此我们看似只是生成条件的IR，其实已经把根据条件进行跳转的指令也涵盖了。

接下来就分别生成if与else本身 stmt 的代码，注意结尾都要跳转到 follow 块！
for:

建四个块：cond, body, step, follow，并把它们打包成 IrLoop 压入 IrBuilder.loopStack。多重循环一定要成套记录。

入栈 IrLoop: IrBuilder.LoopStackPush(new IrLoop(condBlock, bodyBlock, stepBlock, followBlock));

首先是起点：处理 init 这个 ForStmt，并跳到 condBlock。

进入条件块：直接生成cond的IR（自带跳转）

需要注意 cond块的跳转指令是cond生成的，而不是人为添加的！如果不存在cond，该块将无跳转语句造成OCE。因此最后需要一轮check或者在这里强制手动多添加一个无条件jump。

进入body块：直接翻译 body 这个 Stmt ，然后跳到 stepBlock。

进入stepBlock：处理 step 这个 ForStmt，并跳到 condBlock。

出栈 IrLoop。

进入 followBlock。

关于 ForStmt：其实就是多个 assign 语句。
break / continue:

直接查看当前所在的循环体 IrBuilder.LoopStackPeek()，break 跳到 followBlock，continue 跳到 stepBlock。
return：

generateReturnStmtIr 若语句带表达式则生成该表达式，否则对 int 函数默认补 0。返回值统一转到函数返回类型，然后 new ReturnInstr(value or null)。

Exp

Exp 就是一个 AddExp。

结点提供子表达式与连接符号，我们按子表达式列表迭代，逐个拼接 AluInstr。

要注意在每次二元运算前，都把操作数提升到 i32，保证算术统一在 32 位整型上进行。

新的 AluInstr 既作为指令插入，也作为下一轮的左操作数。这样实现了 AST → SSA 的顺序化运算。

一直迭代到的最底层：一元表达式，分为三种。

Primary（括号、数字、左值）：括号就调用 generateExpIr，数字就构造 IrConstantInt，左值调用 VisitorLVal.generateLValIr(lval, false) 获取值。

Ident 函数调用：getint（直接返回 GetIntInstr），其他函数从 SymbolRecorder 取 FuncSymbol，把实参列表递归成 IrValue，最后 new CallInstr(irFunction, paramList)。

一元运算符：+ 返回原值；- 构造 0 - value 的 AluInstr；! 则先转 i32，再生成 CompareInstr("==", 0, value)，最后 ExtendInstr 把布尔结果扩展成 i32。

Cond

generateCondIr 是 if、for 条件代码的入口。它把 Cond 降成 LOrExp，以 trueBlock 和 falseBlock 为目标生成短路控制流。

generateLOrExpIr 为下一个 || 子表达式创建一个中间块，在每个块里调用 generateLAndExpIr，得到的值通过 BranchInstr 控制跳转；若当前子表达式为真，立刻跳trueBlock；否则落到下一个 LAnd 块，实现短路。

generateLAndExpIr 类似，不过 && 的短路条件是中途为假就跳 falseBlock。

最后一个子表达式产生的 BranchInstr 直接指向 trueBlock/falseBlock。

EqExp、RelExp 链式构建 CompareInstr，因为 a == b == c 这种语法递归展开后需要把前一次比较的结果转换为 i32 再与下一项比较。generateEqExpIr 保证自己是i1，因此还要把链式结果与 0 再比较一次，统一转换成 i1。

构建的画笔：toString()

首先是IrModule本身的toString(),作为顶层架构，输出 IR 时，IrModule.toString() 先打印声明、常量、全局变量，再打印所有函数体。
函数体的toString()：

define dso_local type() irName(IrParameter.toString()) {IrBasicBlock.toString()\n}

参数的toString：类型+名字
基本块的toString：irName(也就是IrBuilder给他生成的那个b_#): Instr.toString()
Instr.toString: 我们在介绍Instr的时候已经说过了。

目标代码生成

最后一关，把llvm转变为mips！这一段内容很考验计算机底层逻辑的一些内容，毕竟我们已经从高级语言迈向了汇编语言。

同样都是从某种语言转向某种语言，为什么高级语言到中间代码这么复杂，但是中间代码到目标代码只需要简单一步呢？

因为我们在遇到高级语言时，接受的只是字符串，我们要先把它的架构建造起来，才能完成语义翻译。而中间代码被生成时，其结构是先被搭建出来的，反倒代码本身才是toString的附属品。

在熟悉了LLVM的Module-Function-Block-Instr结构之后，如何转为mips并不是一件特别难的事。

MIPS体系构建

像生成中间代码一样，我们首先要把MIPS的架构建造起来。

类似地，这个结构的顶端是MipsModule.

MipsModule被简单地分为两个部分，分别是.data和.text，这些我们已经很熟悉了。

.data

.data包含 .asciiz .space .word 分别用来定义字符串，数组空间和具体的值。

使用方法大家可能也直接就想到了：

IrConstantString 对应一条 .asciiz、 IrConstantInt 对应一条 .word、 IrConstantArray 初始化为0可直接对应一条 .space，有其他初始值则对应 .word + 一堆数。

Register

寄存器当然是mips最最不能缺少的概念了，也是后端优化的核心难点所在。不过在基础架构这一环节，我们只需要把寄存器的定义列出来就好。

Register.java 是一个枚举类，用于定义MIPS架构中的寄存器，在此我们需要强调哪些寄存器是不能动的。

类型	名称	用途说明
零寄存器（专用）	`$zero`	恒为0，不可修改，常用于需要常数0的场景（如清空寄存器）。
返回值寄存器（专用）	`$v0`, `$v1`	用于存储函数的返回值，以及决定syscall的功能。不过v1就相对自由。
参数寄存器（专用？）	`$a0`-`$a3`	用于传递函数的前4个参数，超过4个的参数通过栈传递（优化时可以考虑只传一部分哦）
临时寄存器	`$t0`-`$t7`, `$t8`-`$t9`	临时使用的寄存器，函数调用时无需保存其值。
保存寄存器	`$s0`-`$s7`	用于保存需要跨函数调用维持的值，函数调用时需保存和恢复其值。
内核寄存器（专用）	`$k0`, `$k1`	内核专用寄存器，用户程序一般不使用。不过我们这里因为不涉及，所以反倒十分自由地使用了他们。
全局指针（可专用）	`$gp`	全局指针，用于访问全局变量，也就是 la $gp, g_1 然后lw
栈指针（专用）	`$sp`	指向当前栈顶。其重要性无需多言。
帧指针（可专用）	`$fp`	指向当前函数栈帧的底部。我在本设计中没有使用。
返回地址（专用）	`$ra`	保存函数调用后的返回地址，`jal`指令强制使用该寄存器，所以不能乱用

我们有方法：getUsableRegisters()，返回程序中可自由使用的寄存器列表，包括：

临时寄存器：T0-T9
保存寄存器：S0-S7
其他的，比如V1以及只有特定时候才有用的A0-A3，我们暂且不放进去。

.text

接下来才是重头戏，也就是MIPS指令集。

text 文件夹中包含的 MIPS 文本段（代码段）相关类及其对应指令类型如下：

MipsAlu：R: add,sub,addu,subu,and,or,nor,xor,slt,sltu I: addi,addiu,andi,ori,xori,slti,sltiu shiftv: sllv,srav,srlv shift: sll,sra,srl MipsCompare：slt、seq、sne、sle、sgt、sge、slti MipsBranch：beq、bne、bgtz、blez、bgez、bltz MipsJump：j、jal、jr MipsLoad：lw、lh、lhu、lb、lbu MipsStore：sw、sh、sb MipsMD：mult、div、mfhi、mflo、mthi、mtlo MipsSyscall：syscall MipsLabel：用于定义代码中的标签 MipsAnnotation：用于添加注释（以 # 开头的说明文本） MarsLi（fake）：li（伪指令，加载立即数到寄存器） MarsLa（fake）：la（伪指令，加载标签地址到寄存器） MarsMove（fake）：move（伪指令，寄存器间数据移动）

需要特别注意的是，由于我们按照大类来划分，因此add与addi的构造方法显然应该是不同的，需要支持多构造函数。

不过听起来复杂，其实也只是把指令的构造方法与toString实现了而已。指令具体的作用呢？那就是计组做的事情了。

从中间代码到MIPS

backend就这么简单的结束了。那还缺什么呢？要怎么把LLVM转到MIPS呢？这其实就是对LLVM的语义分析了：也就是我们生成的llvm代码的含义是什么？究竟该如何用mips表达？

这个问题看起来复杂，但是LLVM与MIPS的相似度很高，结构也都比较简单，所以其实并不太难。整体的逻辑是一致的，两个工具：Builder和toString。

MipsBuilder

MipsBuilder和IrBuilder类似，都是控制整体逻辑结构的重要管理者。

addContent 方法，实现将具体内容放入MipsModule的data与text段中。
寄存器分配管理
- 维护 valueRegisterMap 映射表，记录 LLVM IR 中的 IrValue与 MIPS 寄存器的对应关系。
- 提供 allocateReg 方法记录 IrValue 分配的寄存器
- getValueToRegister 方法查询IrValue 分配的寄存器
- getAllocatedRegList 方法获取已分配的寄存器集合，用于寄存器资源的跟踪与管理。
栈空间分配管理
- 通过 stackOffset 记录当前栈偏移量（初始为 0，分配时递减）
- 提供 allocateStackForValue 为 IrValue 分配 4 字节栈空间并记录偏移地址
- getStackValueOffset 查询 irValue 所在的栈空间位置。
注意：setCurrentFunction切换函数时，也要切换寄存器映射表，重置栈偏移为0，确保不同函数的寄存器和栈空间独立管理。

遍历 IrModule

首先是最顶层的IrModule：

declares、stringConstantMap、globalValues、functions.

如何书写它的toMips?

declare是LLVM要知道的，但在MIPS中直接靠syscall实现，无需提前声明。stringConstantMap对应生成.data段的.asciiz，globalValues对应生成.data段的.word与.space。

asciiz和word的名字怎么取？可直接用irName去掉@这个首字母。

把这些全局的东西做完，就开始具体的函数程序流了。

首先是进入main函数： jal main + j end

然后是各函数的具体内容。

最后是end: new MipsLabel("end")，并syscall 10结束程序。

function

new MipsLabel("函数名")
MipsBuilder.setCurrentFunction(this);
函数形参分配寄存器，根据IrParameter的信息，前四个参数要占用寄存器（具体传值是callInstr的事），并且所有参数都在栈上分配4字节空间（同样，传值不归它管）
遍历IrBasicBlock

basicBlock

最简单的一集：

new MipsLabel("block名")
遍历Instr

Instr

听起来很简单。不就是把原来的指令变成现在的指令嘛，逻辑我当然懂。可是难点不止这一个，不仅是操作符的更新，更复杂的是操作数的变化。不再像以前一样，可以弄出来一大堆变量，现在只有32个寄存器和立即数（含label）可以用，你该如何保证一致性？

这里就介绍几个必要的方法，他们定义在Instr这个父类中：

loadValue(IrValue, Register) 把一个 LLVM 的 IrValue 装进某个寄存器。指令在需要寄存器时，我们需要这个操作来将IrValue进行转换。
- IrValue 是个常量 IrConstant，那就用li直接装进寄存器。
- IrValue 是个全局变量 IrGlobalValue，那他的值就是地址，直接la就可以。（后续做了优化，统一使用gp，这样不变的时候就不用再la，变的时候再move）
- IrValue 是个普通的变量：
  - 他已经在某寄存器上了，那就move过来。
  - 他还在栈上，先MipsBuilder.getStackValueOffset(irValue)，然后lw。
getRegisterOrXXForValue 刚才提到要把值放进寄存器，那该放进哪个寄存器呢？现在就做寄存器分配的话还是太难了，所以我腾了两个寄存器出来专门在无可奈何的时候用：就是K0和K1。（bzh学长的思路）如果做了寄存器分配，当然是可以知道现在它有什么寄存器的，但是没做的话，或者压根没分配，那我就要暂时占用K0了。
saveResult(IrValue, Register)
有load当然就有store，不过我这里起名叫save。什么叫save呢？因为这个值如果没有分配寄存器的话，算出来默认占用的是K0,别人还要用呢。所以如果你有寄存器，就把这个值move到寄存器，否则就要allocateStackForValue，降低offset记录IrValue，用sw把它存栈上了。总之得记录一下到底放在哪。

好嘞，这三个方法讲完，IrValue和寄存器的转移相信你已经了解了。相对于操作数的问题，运算符的问题其实是容易解决的，只是相对繁琐。

接下来就是每个LLVM Instr的翻译过程了。

IOInstr

getint -> new MarsLi(Register.V0, 5); new MipsSyscall(); saveResult(this, Register.V0);

printchar/int -> loadValue(printValue, Register.A0); new MarsLi(Register.V0, 11/1); new MipsSyscall();

printstr -> new MarsLa(Register.A0, irConstantString.getMipsLabel()); （也可以用loadValue） new MarsLi(Register.V0, 4); new MipsSyscall();

AllocateInstr

在初级阶段，我们的数都是存在栈上，霸占寄存器这种事还没有算好。因此这里就直接MipsBuilder.allocateStackSpace。具体的大小还要看一下IrValue的类型，如果是数组还要乘上size。

有关栈的操作，我们一定要注意实时更新sp寄存器！这里就需要用ADDU，把sp减去我们分配的大小。

CallInstr与ReturnInstr

这算是最难的一个部分了。前面我们提到IrFunction要登记a0-a3寄存器，但是具体传值是callInstr进行的。不仅如此，callInstr的整体流程为：保护现场->传参->jal->恢复现场->处理返回值。

saveCurrent
- 保存所有的寄存器，包括当前的ra，然后栈指针向下移动
fillParam
- 前四个直接将值load进对应的寄存器，之后的就先随便load个寄存器，然后sw进栈。
jal function_label
恢复现场
- 栈指针向上移动，把值lw回寄存器
处理返回值
- 函数的IrValue直接save进V0寄存器。

关于return就相对简单，因为事情都给callInstr做了。 return要提供返回值的内容到某寄存器（load），以及jr $ra

BranchInstr

首先把cond放进寄存器，然后直接用bne跳转真，否则无条件跳转假

1
2
3
4


Register condRegister = getRegisterOrK0ForValue(cond);
loadValue(cond, condRegister);
new MipsBranch(MipsBranch.BranchType.BNE, condRegister, Register.ZERO, getTrueBlock().getMipsLabel());
new MipsJump(MipsJump.JumpType.J, getFalseBlock().getMipsLabel());

GepInstr

这个指令可谓是LLVM时很特殊的指令了，现在转为MIPS其意义也很明显：目标地址 = 基地址 + 偏移量 × 4。

所以就只是load一下，先左移，再add，最后save。

Load/StoreInstr

出于简单考虑，我们统一使用new MipsLoad(MipsLoad.LoadType.LW, targetRegister, pointerRegister, 0); 默认设置偏移为0，值和址都放入寄存器。

MoveInstr

此move非彼move，不过也只是操作数不同。

ExtendInstr

这个指令在MIPS没有意义，因为没有type的区分。所以只需要进行一个赋值，和MoveInstr一样，把原来的ir的值赋给新的ir即可。

TruncInstr

这个就有意义了，如果要压缩到一位，就需要和1进行andi。

CompareInstr

load+比较+save，比较运算符更是都能一一对应。

AluInstr

运算符也都能对上。处于简单考虑，我们都先放进寄存器，然后用不含立即数的指令进行运算。

注意：对于乘除法，还要加一句MFLO，取余则为MFHI

后端的内容说多也不多，但是一定需要谨慎思考再落笔，否则很容易出现恶劣bug。其次，我们肉眼可见有大量值得优化的内容需要完成。

中间代码优化

代码优化分为体系结构无关的中间代码优化与体系结构相关的目标代码优化。

在边遍历边生成的过程中，不可避免会有很多冗余与机械性的指令产生。中端优化不仅可以直接缩减中间代码的行数，还能让后续的某些后端优化更容易发生。

关于中端优化，最核心的对象不在于某一条指令，而是宏观上的感知，要充分挖掘指令之间、Value之间、基本块之间的联系。基本块之间的联系简单来说就是流图，Value之间的联系则是我们一直在维护的Use关系。

需要注意：很多优化会改写控制流边（例如把 branch 改写成 jump、删除 block、插入中间块），所以流水线中会多次执行 CfgBuilder 来重建 CFG 与支配信息，并同步修 phi 的前驱列表。

为什么我们需要CFG并实时更新CFG？

CFG 直接提供的关键信息

前驱/后继（Pred/Succ）：CFG帮我们统计好所有的前驱与后继。这个的用处太多了，修 phi incoming、跳转改写时都得用到。

结构信息：哪里是 if/else，哪里汇和，哪里是循环回边。宏观上的结构提取离不开对CFG的分析。

为什么优化会依赖 CFG

MemToReg / SSA / phi 插入：phi 的语义就是来自不同前驱边的值在这里合并。phi 插入位置依赖支配关系/支配边界，没有 CFG 的前驱列表，连phi 应该有几个 incoming都不知道。

常量传播 / 活跃分析等数据流分析：理论课知识，经典数据流方程都是依赖于流图的前驱/后继块信息。

循环优化：要判断某指令外提到循环前是否安全，需要先准确知道哪些块属于这个循环、循环入口从哪来。这些都需要来自 CFG 。

CFG 的构建

RemoveUnreachableCode

为什么先说这个呢？因为这个逻辑太简单了，而且这个优化能够在一定程度上帮助CFG的构建。

单个基本块内：跳转指令之后的指令在语义上永远不会执行。因为跳转以基本块为单位，执行完跳转指令一定会到达某基本块的开头。

基本块内遇到 jump/branch/return，删除后续所有指令。
整体来看，entry不能跳转到的块也都是不可达的。从入口块 DFS，只保留可达块，其余块从函数的 blockList 中移除。

实现起来很简单，不过注意删东西的时候要把Use关系也尽量删干净。

CfgBuilder

1
2
3
4
5
6
7
8


public void optimize() {
        initFunctions();
        buildCfg();
        syncPhiIncomingBlocks();
        buildDominateRelationship();
        buildDirectDominator();
        buildDominateFrontier();
    }

扫描每个基本块末尾终结指令来重建 beforeBlocks/nextBlocks，再把块首 phi 的 predecessor 列表与当前 beforeBlocks 对齐，最后计算支配关系、立即支配与支配边界。

initFunctions() 先把每个基本块里旧的 CFG 信息清空，然后 buildCfg() 重新连边。这里的图并不是单独的Graph对象，而是存放在每个基本块的两个属性里：beforeBlocks 表示前驱，nextBlocks 表示后继。

buildCfg() 的逻辑非常直观：遇到无条件跳转就把target加到nextBlocks，同时把block加到target.beforeBlocks。遇到条件分支就分别对 true/false 两个目标都做同样的加后继/加前驱。

需要注意把块开头的 phi 的 incoming block 列表对齐到最新的 beforeBlocks。支配关系的判断和上课讲的方法一样，假装把一个块从图里删掉，然后从入口块做一次 DFS，走不到的块就是依赖于被删的块。

无效代码删除

JumpThreading

跳转穿线的出发点是因为在处理控制流时，IR 很容易生成跳板块，也就是块里只有一条无条件跳转，这类块本身不提供任何语义增量，却会把 CFG 拉长、制造额外边与额外分支，从而让后续优化更难看清结构。

我在实现时只处理了非 entry 且仅含无条件跳转的块，把所有前驱直接改跳到 target

为了避免破坏 phi 语义，如果 target 块开头存在 phi，我选择保守地不做穿线，因为那意味着需要补齐 incoming value 才能保持语义一致。

RemoveDeadCode

在中间代码非常容易产生算出来但没人用的值，这些值如果留到后端，会产生大量的寄存器压力与访存压力，还会阻碍后续的常量传播与去重（因为它们占据了 use/def 的一部分）。它不仅能删指令，更重要的是把依赖图变稀疏，让后续每一步优化都更容易触发。

我们先从main出发构建调用可达信息，并标记有副作用的函数（包含 IO、store，或调用了有副作用的函数），然后以关键use指令为根（return、branch/jump、store、IO、以及调用了副作用函数的 call），逆着 use 关系把依赖链标记为 active，删除所有非 active 指令。

我还做了一些简单的结构性清理：

删除无前驱且非 entry 的块并在后继块里移除对应的 phi incoming
合并满足前驱唯一且前驱只有这一个后继的块
把只有一个 incoming 的 phi 直接展开为普通值。

RemoveDeadFunctions

不可达函数删除在没有函数指针的语言里收益很直接：函数可达性完全由 call 决定，删掉 main 不可达函数既能减小输出规模，也能减少后续优化的工作量。

直接从 main 出发沿 CallInstr -> targetFunction 做 DFS 标记 reachable，然后删除不可达函数即可。

SSA

MemToReg + InsertPhi

前端生成 IR 时局部标量往往落成 alloca + store/load，各种变量都放在内存里。如果不提升至SSA，后端会机械地产生大量 lw/sw，而这些访存其实只是为了模拟变量当前值。一旦把它提升到 SSA，就把内存问题变成了值问题，常量传播、去重与窥孔会变得非常自然。

我在实现时只处理了非数组的 alloca，先扫描该 alloca 的 use 收集 define（store）与 use（load），再利用支配边界在需要的块开头插入 phi，最后沿支配树做 rename。

rename: 我们用栈来维护当前最新值，把 load 替换为栈顶值除，把 store 变成入栈，栈为空时用 0 作为默认初值。

MemForward

即便做了 MemToReg，局部数组/局部指针这类不使用SSA，而是确定地址的对象仍然可能出现 store→load、重复 store 或重复 load。

我当前实现是块内优化。在单个基本块内维护 address -> MemState：

遇到 store 就记录最新地址写入值。
遇到 load
- 若该地址的值已有缓存，则替换 load 的 user 并删除该 load。
- 否则把该 load 的值记为已知值，用来做 load-load 的消除。

DeadLocalAllocaStore

这个优化的动机来自一种很典型的冗余：局部数组或局部变量可能被写了很多次（尤其是初始化）但从未被读过，这些 store 对语义没有任何贡献。我们可以把只写不读的初始化彻底抹掉。

我以 alloca 为根向下追踪由它派生的 gep 地址，收集相关 store；只要发现任意 load，我就放弃优化，否则就删除所有相关 store，并进一步清理因为 store 消失而变成无用的 gep/alloca。

表达式

Inline Function

这个测试点对testfile6有奇效。我在此仅实现了很简单保守的函数内联，就已经为后续的优化提供了极大的便利。函数内联的意思是把一次函数调用直接改写为被调函数的函数体。这样不仅消除了 call 本身的大量开销，还能把原本跨函数边界的常量传播、公共子表达式删除和死代码删除等暴露给后续优化。

本次仅对非常小且形态简单的函数进行内联：目标函数 callee 满足非 main、非自递归、仅包含一个基本块、最后一条指令为 ReturnInstr、指令条数不超过阈值，且函数体中不包含 call/IO/load/store/alloca/分支跳转/phi 等可能引入副作用或 CFG 复杂性的指令时才允许内联。

具体实现层面，首先建立好形参与实参的映射。然后按原顺序遍历基本块中的每条纯计算指令（Alu/Compare/Extend/Trunc/Gep），在调用点所在的基本块中利用映射关系创建一条新指令插入到 call 之前。当所有指令克隆完毕后，将 return 的返回值同样通过映射到调用点语境下得到 returnValue，还要将返回值的所有user替换为内联后的值，最后删除原 call 指令并清理 use-def 边。

GVN

这里参考了bzh学长的字符串哈希法，为表达式维护了一个hash标识。我们沿支配树遍历，用 getGvnHash() 为表达式做哈希并维护一个当前支配路径上的表达式表，当发现哈希已出现就用已有值替换当前指令并删除它。

LVN

LVN 比 GVN 更适合边走边化简：在遍历过程中顺手做常量折叠、代数恒等化简，能把很多小冗余直接掐掉，不必等到后端再清。

对 ALU/CMP/EXTEND/TRUNC 可以做常量折叠与简单代数化简，对 ALU/CMP/GEP 做基于哈希与MoveInstr的消除，也就是常量传播。其中针对MoveInstr，直接传播给user，然后删除 move。

Sparse Conditional Constant Propagation

稍微深入处理一点常量折叠：常量不仅来自字面量，还来自某些路径根本走不到：简单的说，就是提前预判某些分支是否必走，从而方便我们的传播。

我对SSA值维护了三值格 UNDEFINED/CONSTANT/OVERDEFINED，并不断传播，phi指令触发值合并从而改变状态，最终把 CONSTANT 的SSA值替换成常量。

PureFunctionEvaluation

这个点是testfile7直接提醒到的。在无副作用、返回值只由参数决定的前提下，call 可以被当成一种可优化的表达式：参数全为常量时可以直接算出结果。此外，同一支配区域内对同一参数重复调用也可以复用结果。

首先是纯函数候选：非main、非void、有函数体、不出现 load/store/alloca/gep/io、不调用非纯函数。然后在遇到纯函数就解释执行目标函数（设置了较强的限制，防止算太久），得到结果并替换 call。我还沿支配树维护 (callee, args) 表，若已有支配的同 key 调用就复用结果。

循环

LoopCanonicalization

循环规范化是为了便于LICM的执行的。因为 LICM 需要一个循环外唯一入口，也就是说被外提的指令需要一个确定且唯一的放置点。

如果存在一条边 tail -> header，并且 header 支配 tail，那么 tail -> header 是回边，header 是循环头。然后从 tail 反向沿前驱回溯，把能回溯到 header 的那些块收集起来，得到循环块集合。

我们观察header的前驱，有多少来自循环外，也就是外部入口有多少。若循环头存在多个来自循环外的前驱，我就插入新的 preheader统一外部入口，把所有外部入口重定向到 preheader，并修复 header 的 phi：把外部 incoming 先在 preheader 合并（必要时插入新的 phi），让 header 只从 preheader 接收一个外部 incoming。

LICM

LICM 的直觉是：循环里有些表达式每次迭代都一样，留在循环体内就是重复算，把它们挪到 preheader 只算一次，循环体就能更短更快。

我只外提无副作用、无定义新值的指令（ALU/CMP/EXTEND/TRUNC/GEP），明确排除 load/store/call/IO/控制流/phi。更宽泛地，如果某指令的 operand 在循环内定义时，倘若能判定该 operand 也是 invariant的就也能外提。最终把可外提指令插入到 preheader 的终结指令之前。

后端准备

ActiveAnalysis

活跃分析的原因是寄存器分配必须知道哪些值必须跨块保留，否则很容易把仍在后续使用的值提前释放掉；而跨块活跃由每个块的 in/out 集合决定。我们先计算每块的 def/use，再迭代求解 in/out（out 为后继 in 的并集，in 为 use 并上 out−def），并额外处理 phi 的沿边使用：把从当前块流向后继块那条边对应的 phi incoming value 纳入 out 集合，保证跨边的真实需求被计入。

AllocateRegister

我做寄存器分配的目标是尽可能把 SSA 值放进物理寄存器，让后端少发 lw/sw，没有实现 spill。通过沿支配树递归分配，进入子块时临时释放不在子块 in 集合里的寄存器，处理完子块再恢复。

在块内我记录每个 useValue 的 last-use，当某值在本条指令里是最后一次使用且该值不属于 block-out，就立即释放它占用的寄存器。

RemovePhi

对每个基本块开头的 phi，先按从哪个前驱跳过来就取哪个 incoming 值的含义，把它拆成写在各条前驱边上的一组并行拷贝（同一条边上可能要同时给多个 phi 结果赋值，所以逻辑上必须并行）

如果某条边前驱有多个后继且后继有多个前驱，就无法把拷贝安全地放在前驱块末尾或后继块开头，因此要先插入一个只服务这条边的中间块，把拷贝放到中间块里；接着把并行拷贝集合线性化成若干条顺序 MoveInstr。

并行操作转为顺序操作可能出现矛盾，比如环状赋值。这个时候就需要引入临时变量先把右值存下来，再move肯定不会错。

目标代码优化

后端优化我分为两各方面：一部分发生在 IR 的 toMips() 过程中，本质是指令翻译时就直接简化，是指令单位本身的优化，在不改变语义的前提下直接选择更省的 MIPS 序列。第二部分就是相对宏观的指令间优化，不过实际上还是非常局部、非常确定的窥孔。

翻译期优化

立即数优先

对于ADD/SUB/AND/OR ，如果有一项是常数，我会在立即数满足范围时优先选用 addiu/andi/ori，可以少加载一次寄存器。如果这个常数是0/1还可以做特判。

乘除模优化

乘法优化：对 0/1/-1、2^k、小常数（如 3/5/7/9/15）分别用 move/neg/shift/shift+add-sub 分解来避免 mult，此外如果执行了mult还会对 HI/LO 复用缓存。

除法优化：对 1/-1 特判，对 ±2^k 走算术右移 + 符号修正的无 DIV 路径，对其它常数走 magic-number division（mult/mfhi + shift + 符号修正）尽量避免真实 div，对非常数才使用 div + mflo

取余优化：对 ±1 直接为 0，对 ±2^k 用移位/掩码实现符合向 0 取整的余数语义，对其它常数直接用真实 div 并取 mfhi 。

MipsOptimiser（peephole）

MipsOptimiser 我也单独写成了一个类，其实做的都是窥孔。我把它写成了多条规则迭代到稳定的形式：每一轮按固定顺序尝试所有规则，只要本轮有改动就继续下一轮，直到整个 textSegment 不再变化。

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


public void optimize() {
        boolean changed;
        do {
            changed = false;
            changed |= forwardStoreLoads();
            changed |= removeDuplicateStores();
            changed |= dropTrivialMoves();
            changed |= simplifyZeroAlu();
            changed |= removeJumpToNextLabel();
            changed |= removeDuplicateLoads();
            changed |= removeLoadStoreBack();
        } while (changed);
    }

forwardStoreLoads

刚 store 完马上又从同一地址 load等价于直接复用被 store 的那个寄存器值。它的价值是把一次访存变成一次 move，甚至在后续再被 move 消除。我们在遇到一条 sw/sh/sb 之后向后扫描，若遇到对同一地址且类型匹配的 lw/lh/lb...，就把该 load 替换成 move。扫描会在危险的地方直接停止（label、jump、branch、syscall 以及大多数乘除相关指令）。如果扫描过程中同址再次 store，要更新可转发的最新值寄存器。

removeDuplicateStores

我做连续 store 合并的原因是刚才的操作虽然消除了load，但没消除store。所以又判断了一下相邻 store 是否写同一地址，若相同就删除前一条。

removeDuplicateLoads

相邻两次从同一地址、同一类型的 load 在中间没有可能改写该地址的情况下，第二次 load 的值与第一次完全一致。若目标寄存器也相同就删除后一条，否则把后一条替换为 move dstB, dstA。

removeLoadStoreBack

针对lw r, addr; sw r, addr ， store 写回的就是刚读到的值，内存内容不变，属于纯浪费。

dropTrivialMoves

move r, r 直接删除。这个其实可以在翻译时实现的。

simplifyZeroAlu

addi/sll/srl/sra 带 0 立即数，留着只会浪费一条指令。不过这个翻译时也有所实现。

removeJumpToNextLabel

这种跳转对控制流没有任何实际作用。检查 j L 的下一条有效指令（忽略 annotation）是否正好是标签 L:，若是就删除该跳转。

小结

请总结本学期编译技术课程学习的收获，并提出对课程改进的意见、建议。

我的收获

如果要对整门编译技术课进行总结，在理论课上的收获可能感受起来更加真实。或者说本来形式语言与自动机的理论就比较有趣，在计组课上初步接触状态机后，还能在编译课上以文法为媒介学习更多细节的知识，体验还是很不错的。此外，课堂上还涉及到了有关运行栈的计算机底层知识，使其和COOS一脉相承。第三点就是理论与实验的联动比较强，这里主要指的就是LL分析以及中间代码优化的部分，课上的知识真的能为实验提供理论支持，这种体验感上次感受还是在一年前的CO理论讲冒险的时候。

在实验上，虽然每项作业也有ddl，但整体的节奏感没有COOS那么紧张，这也导致了我在做编译这件事上很难做到久久为功，而往往是以多次集中突击的形式完成。编译实验是一门从0开始完成的大型项目，尽管经历了OO的磨练，我依旧难以培养起来比较清晰的模块观念，许多文件的设计都大量借鉴了学长的示例，例如IrModule，IrBuilder这样的类的设计。抛开这些不谈，经过编译实验我当然收获颇丰。从语法分析开始便一次又一次超出我的认知，类的数量太多以至于必须创建module，提取特征写父类，写抽象类，写记录类……静态类也是我之前OO课上未曾使用，但编译实验中频频使用的典例。

意见与建议

编译课程整体的体验感就是难。削减难度这样的事可能未必是改进，但还是希望同学们能够稍微更轻松地完成实验，比如理论课可以增设llvm的讲解，然后适当减少用属性翻译文法进行中间代码生成那一部分的课时。