# TXT-Compiler **Repository Path**: Hmount/txt-compiler ## Basic Information - **Project Name**: TXT-Compiler - **Description**: 根据编译原理实验课要求实现的一个 Java 实现的 TXT 语言(简单类C)编译器, 目标平台为 RISC-V 32 (指令集 RV32M). - **Primary Language**: Java - **License**: Not specified - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 2 - **Forks**: 0 - **Created**: 2022-09-12 - **Last Updated**: 2022-10-27 ## Categories & Tags **Categories**: Uncategorized **Tags**: Compiler, Java ## README # TXT-Compiler ### 介绍 根据编译原理实验课要求实现的一个 Java 实现的 TXT 语言(简单类C)编译器, 目标平台为 RISC-V 32 (指令集 RV32M). ### 编译器架构 ![layout](assets/layout.png) ### 框架结构 ``` . ├── data │ ├── in # 提供给程序的输入数据 │ ├── out # 程序的输出数据 │ └── std # 用作参考的标准输出数据 └── src # 源码目录 ``` ``` src/cn/edu/hitsz/compiler ├── asm # 实验四: 汇编生成 │ └── AssemblyGenerator.java # 汇编生成器 ├── ir # 基础架构: IR │ ├── Instruction.java # IR 指令 │ ├── InstructionKind.java # IR 指令类型 │ ├── IRImmediate.java # IR 立即数 │ ├── IRValue.java # IR 值 │ └── IRVariable.java # IR 变量 ├── lexer # 实验一: 词法分析 │ ├── LexicalAnalyzer.java # 词法分析器 │ ├── Token.java # 词法单元 │ └── TokenKind.java # 词法单元类别 ├── parser # 实验二/三: 语法分析, 语义分析, IR 生成 │ ├── table # 读取/生成 LR 表的工具 │ ├── ActionObserver.java # 观察者接口 │ ├── IRGenerator.java # IR 生成 │ ├── ProductionCollector.java # 规约产生式记录 │ ├── SemanticAnalyzer.java # 语义分析 │ └── SyntaxAnalyzer.java # 语法分析 ├── symtab # 符号表 │ ├── SourceCodeType.java # 源语言变量类型 │ ├── SymbolTableEntry.java # 符号表条目 │ └── SymbolTable.java # 符号表 ├── utils # 杂项/工具 │ ├── FilePathConfig.java # 记录程序中用到的各种路径 │ ├── FileUtils.java # 文件读写工具 │ └── IREmulator.java # 评测用 IR 解释器 ├── Main.java # 主函数 └── NotImplementedException.java # 用于填充待实现部分的异常 ``` ### 源语言 由于我们的语言代码文件后缀为 txt, 于是我们姑且称之为 TXT 语言. 以下为一个简单的代码示例: ```c int result; int a; int b; int c; a = 8; b = 5; c = 3 - a; result = a * b - ( 3 + b ) * ( c - a ); return result; ``` 相关词法语法将会在下面介绍 ### 目标语言 && 目标平台 我们的目标是生成在支持 RV32M 指令集的 RISC-V 32 机器上可以成功运行的汇编代码. 然而这份代码要成功运行还得通过汇编器和链接器生成可执行文件并链接到相应的库上. 然而在实际操作中我们并没有一台 RISC-V 32 的机器, 就算通过 qemu 模拟, 我们仍不可避免地需要与 GNU 汇编伪指令操作打交道. 为了避免这些麻烦, 我们使用 RARS(RISC-V Assembler and Runtime Simulator) 进行模拟. 可以认为我们的目标机器为 RARS. 根据 RISC-V 的寄存器使用约定, 我们使用 Caller 保存的 t0 到 t6, 亦即 x5-7, x28-31 作为汇编代码中任意使用的寄存器, 使用 a0, 亦即 x10 作为程序的返回值. 并且我们使用 CompactDataAtZero 选项规定 data 的开始地址为 0x0. 通过 RARS 我们可以这样进行汇编程序的执行: ```shell $ java -jar rars.jar mc CompactDataAtZero a0 nc dec ae255 riscv1.asm Program terminated by dropping off the bottom. a0 10945 ``` ### 运行环境 1. Java 17 及以上版本. 2. RARS. 3. 编译工作台 (可选) ### 词法分析 ##### 1. 词法规则 ![lexical_rules](assets/lexical_rules.png) **id的词法规则修改为[a-zA-Z_][a-zA-Z0-9]*** ##### 2. DFA **我们使用DFA的方式识别Token** ![DFA](assets/DFA.png) ### 语法分析 ##### 1. 语法规则 **文法如下** ```shell P -> S_list; S_list -> S Semicolon S_list; S_list -> S Semicolon; S -> D id; D -> int; S -> id = E; S -> return E; E -> E + A; E -> E - A; E -> A; A -> A * B; A -> B; B -> ( E ); B -> id; B -> IntConst; ``` ##### 2. LR分析表 在语法分析的过程中，我们采用了LR分析表驱动的自底向上语法分析方式 根据文法生成的LR1分析表如下 ![LR1](assets/LR1.png) ### 语义分析 ##### 1. 声明语句的翻译 由于我们的编译器文法相对简单，因此在语义分析中, 只需要在遇到每次声明的时候, 于符号表中记录每个标识符的类型信息即可. 且由于我们只支持Int类型变量，对应到 RISC-V 中的 32 位有符号整数类型.因此我们只需要在归约声明语句时将对应id.type置为Int(更新符号表)即可. **在语义分析中，尽管我们只有Int数据类型，但是为了保证编译器的拓展性，我们还是设置了相关的SDD语义规则，并使用属性栈完成语义分析** ##### 2. 约定的语义属性和方法 ```shell # 语义属性 name -> 变量名、寄存器号或常量值 # 翻译方法 addTable(id.text, Int) -> 表示更新当前id在符号表中的类型为Int gen(IR) -> 表示生成对应的IR tempReg() -> 表示生成新的寄存器号 ``` ##### 3. S-SDD语义规则 ```shell P -> S_list; S_list -> S Semicolon S_list; S_list -> S Semicolon; S -> D id; { addTable(id.text, Int) } D -> int; S -> id = E; { gen(MOV, id, E.val) } S -> return E { gen(RET, , E.name) }; E -> E + A; { E.name = tempReg(), gen(ADD, E.name, E1.name, A.name) } E -> E - A; { E.name = tempReg(), gen(SUB, E.name, E1.name, A.name)} E -> A; { E.name = A.name } A -> A * B; { A.name = tempReg(), gen(MUL, A.name, A1.name, B.name) } A -> B; { A.name = B.name } B -> ( E ); { B.name = E.name } B -> id; { B.name = id.text } B -> IntConst; { B.name = IntConst.text } ``` ### 中间代码生成 ##### 1. 初步生成 当前支持的所有中间代码类型文本表示及其含义 ```shell # 将from的值存入res (MOV, res, from) # 计算 (lhs + rhs) 并将结果存入res (ADD, res, lhs, rhs) # 计算 (lhs - rhs) 并将结果存入res (SUB, res, lhs, rhs) # 计算 (lhs * rhs) 并将结果存入res (MUL, res, lhs, rhs) # 返回returnValue的结果 (RET, , returnValue) ``` 这其中 ```` res -> 必须是变量(IRVariable) from、 lhs 、 rhs、 returnValue -> 既可以是变量(IRVariable)也可以是立即数(IRImmediate) ```` 中间代码的初步生成完全按照上述L-SDD在语法制导翻译中完成 ##### 2. 中间代码规范化 在后续**汇编代码生成**的**指令选择**过程中，我们可以**预见**到： **带有常量操作数的二元运算中间代码不能直接转化为一条汇编指令** **e.g:** ```shell (SUB, $1, $0, 1) # 不能直接转换为汇编代码: sub t1, t0, 1 (SUB, $0, 1, 1) # 不能直接转换为汇编代码: sub t0, 1, 1 (MUL, $1, $0, 1) # 不能直接转换为汇编代码: mul t1, t0, 1 (MUL, $0, 1, 1) # 不能直接转换为汇编代码: mul t0, 1, 1 # RISC-V指令集中尚不支持subi和muli 指令 # 而sub和mul指令均不支持立即数运算，因此直接生成的汇编指令都不合法 ``` 因此，与其在汇编代码生成阶段再为运算所需的常量分配寄存器，不如直接规范中间代码的格式。 我们规定：**在二元运算符中间代码中，任何一个操作数都不应该是常量** 这样一来，中间代码优化的任务就很明确了： **每次生成一条运算IR时，假如操作数中存在常量(IRImmediate)，则将这个常量存入一个新的寄存器变量(IRVariable)，再将运算的操作数改为这个寄存器变量。** **e.g:** ```shell # 每次SDT生成 (SUB, $1, $0, 1)时, 改为生成: (MOV, $1, 1) (SUB, $2, $0, $1) # 每次SDT生成 (MUL, $0, 1, 2)时, 改为生成: (MOV, $0, 1) (MOV, $1, 2) (MUL, $2, $0, $1) # 由于存在伪指令li,因此MOV运算中操作数为常量是无所谓的 (MOV, $0, 1) -> li t0, 1 ``` 特别地，对于形如 **(ADD, $0, 1)** 和 **(ADD, 1, $0)** 的IR，我们虽然存在指令**addi**可以轻易处理，但是考虑到整体IR的**统一性**我们将同样对其作出上述优化。 ##### 3. 中间代码优化 + 启用方式 在 **main.java** 中提供了是否进行中间代码优化的选项，默认会不启用. ```java ... ... // 各 Observer 输出结果 productionCollector.dumpToFile(FilePathConfig.PARSER_PATH); symbolTable.dumpTable(FilePathConfig.NEW_SYMBOL_TABLE); final var irOptimizer = new IROptimizer(irGenerator.getIR()); // 是否进行中间代码优化 (可选) // irOptimizer.run(); final var instructions = irOptimizer.getIR(); irGenerator.dumpIR(FilePathConfig.INTERMEDIATE_CODE_PATH); ... ... ``` + 优化内容 优化选项开启后，编译器会将生成的中间代码进行如下优化: **常量传播: 编译期间，能够直接计算出结果的变量，将被编译器由直接计算出的结果常量来替换这个变量.** **常量复写: 编译期间，如果有可能，将多个变量的多级冗余计算被替换为一个变量的一级计算.** **死指令删除: 删除掉永远不能被执行到的代码或者没有任何意义的代码.** 优化思想参考各大主流编译器遵循 **“如果计算过程能在编译过程中完成，就无需在程序运行时计算.”** 的原则. e.g **优化前** ```c int result; int a; int b; int c; a = 8; b = 5; c = 3 - a; result = a * b - ( 3 + b ) * ( c - a ); return result; ``` **优化后** ```c return 144 ``` **优化后对应的IR和asm** ```c # IR (RET, , 144) # asm .text li a0, 144 # (RET, , 144) ``` 由于我们目前编译的语法比较简单，因此优化的力度会显得比较大，使得后续的asm生成和寄存器分配失去意义，因此默认关闭这一优化. + 优化实现 在当前编译器支持的语法中，所有代码是 **单基本块结构**, 没有分支、循环结构，没有过程调用, 这使得复写传播的优化过程非常便捷. 使用从前往后的数据流分析，定义相关的数据流记号 ```java /** 基本块入口处的活跃变量集合 */ private HashSet in = new HashSet(); /** 基本块出口处的活跃变量集合 */ private HashSet out = new HashSet(); /** 在基本块中被定义，且在定义前在块中未被引用的变量集合 */ private HashSet def = new HashSet(); /** 在基本块中被引用，且在引用前未在块中被定义过的(变量名,变量值)键值对集合 */ private HashMap use = new HashMap(); ``` 首先进行**活跃变量分析**： 对于 **单基本块结构** , 待分析的基本块没有前驱和后继节点，因此其 **in** 集合为空，**def** 集合为块中涉及到的全体变量. 且受限于语法分析，块的出口一定是返回指令**RET**，因此 **out** 集中只有最后一个变量. 优化过程：顺序遍历所有IR，对于MOV和OP指令中的变量我们都查找use集将其替换为对应常量，我们能计算出res的结果时，则删除这条指令，并加res和对应结果加入use集，随后从头开始遍历，反复迭代直到RET语句，查use集合将返回值返回. **对于所有单基本块结构IR，如果整个过程不出错的话，迭代的终点只会剩下一条RET语句.** **PS: 在后续的asm代码生成时默认不启用这一优化.** ### 汇编代码生成 ##### 0. 概述 & 约定 **目标RISC-V指令集** ```shell add rd, rs1, rs2 # 寄存器加法 sub rd, rs1, rs2 # 寄存器减法 mul rd, rs1, rs2 # 寄存器乘法 addi rd, rs1, imm # 立即数加法 lw rd, offset(rs1) # 内存读 sw rs2, offset(rs1) # 内存写 mv rd, rs # addi rd, rs, 0 li rd, imm # addi rd, x0, imm ``` **寄存器约定**: 根据 RISC-V 的函数调用规范, 我们在代码生成时只使用 Caller 保存的 t0 到 t6, 亦即 x5-7, x28-31 作为汇编代码中任意使用的寄存器. **栈约定**: 我们使用 CompactDataAtZero 选项规定 data 的开始地址为 0x0，于是我们可以基于 x0 寄存器与偏移量定位内存空间. **返回值约定**: 我们使用 a0, 亦即 x10 作为程序的返回值 ##### 1. 指令选择 如果之前的操作按照约定的完成，那么在本环节中所有可能出现的IR生成asm示例如下 ```shell # MOV指令的目标代码 (MOV, $0, 1) -> li t0, 1 (MOV, $1, $0) -> mv t1, t0 # ADD指令的目标代码 (ADD, $0, $1, $2) -> add t0, t1, t2 # SUB指令的目标代码 (SUB, $0, $1, $2) -> sub t0, t1, t2 # MUL指令的目标代码 (MUL, $0, $1, $2) -> mul t0, t1, t2 # RET指令的目标代码 (RET, , $0) -> mv a0, t0 (RET, , 1) -> li a0, 1 ``` ##### 2. 寄存器分配 由于上述中间代码优化中我们已经去除了所有不能用立即数指令替代的常量IR,因此我们不需要考虑为常量(**IRImmediate**)分配寄存器的问题. 我们只用考虑为IR中的每个变量(**IRVariable**)分配寄存器的方案. ###### i. 寄存器管理 ```java /** 我们直接使用对应的字符串表示对应的寄存器t0-t6, 例如: */ t0 = "t0"; /** 寄存器描述符: 用于记录t0-t6寄存器中存放的变量 */ private Map registerDescriptor; /** 使用一个List存放当前空闲的寄存器，初始状态下存放["t0"-"t6"] */ private List freeReg; ``` ###### ii. 寄存器冲突抢占管理 我们使用计数器轮询方式选取每次发生寄存器发生冲突时要抢占的寄存器号,保证每次发生冲突时各个寄存器需要礼让的机会均等. 我们使用寄存器锁保护一个寄存器不会被抢占，保证一条指令的生成中不会出现dst、rs1、rs2互相抢占的现象. 提供加锁和解锁方法保证一条中间代码的分析中变量与寄存器的映射**同步** 或者说，加锁是为了保证在同一条IR的分析期间，每一个已经分配的寄存器不能再被分配，应该是互斥的,属于临界资源. ```java /** 本次发生冲突时要抢占的寄存器号 */ private int regCount = 0; /** 寄存器锁 * 被锁住的寄存器号将不能被抢占 * 例如ir (op, $1, $2, $3) 中 * 按从左到右的顺序为三个变量分配寄存器 * 后者不能抢占前者的寄存器 故在为右边的变量分配寄存器时需要对左边已确定的寄存器加锁 * **/ private int lock1 = -1; private int lock2 = -1; /** 释放所有寄存器锁 */ public void releaseLock(); /** 为寄存器加锁 */ public void aquireLock(String reg); ``` ###### iii. 变量生命周期统计 因为汇编代码生成是根据逐条分析IR生成的，我们把一条IR的分析称为**一轮** 在我们初次加载IR时，将统计IR中所有变量最后活跃的轮数，以此获取并记录下每个变量的生命周期 我们在汇编代码生成的每一轮开始前都会根据这个表进行寄存器的再分配，也即将所有已失效的变量所占用的寄存器释放出来 这样一来能极大地缓解寄存器的紧缺，降低局部临时变量对寄存器资源的压力. ```java /** 地址描述符 统计每个变量所占用的寄存器或内存地址 */ private Map addressDescriptor; /** 存放IR中涉及的所有变量 */ private Set vars; /** 统计每个变量的最后活跃时间（轮数）*/ private Map expire; /** 在每轮分析的开始，根据变量的最后活跃时间对寄存器进行重新分配 */ private void realloc(int count); ``` ###### iiii. 栈管理 每次发生寄存器冲突时，我们会根据上述方法选中一个寄存器进行礼让后，会将这个寄存器原本存的值溢出到内存中（栈数据段）,然后更新地址描述符,再将新数据存入寄存器。 显然有一个策略是，在每次汇编代码生成开始时，我们统计涉及到的所有变量的个数，并一次性地为每个变量都开辟一块栈空间。 在能解决寄存器冲突的前提下，为了尽可能使用更小的栈空间, 同时兼顾方便性, 我们打算采取如下的动态分配栈空间的方式: ```java /** 栈底指针ebp 约定为0x0地址 */ /** 栈顶指针esp 初始情况下未开辟栈空间时offset为0 */ private int offset; /** 我们在每次遇到一次寄存器冲突时，才开辟出一块空间，存放寄存器溢出的值 */ sw tx offset(x0); /** 我们的编译器中所有变量只有Int型，因此每次开辟的空间大小为4字节 */ offset += 4; ``` 由于发生寄存器冲突的次数肯定比IR中出现的变量总个数少，因此这个方法**一定程度**上减少了栈空间的占用 显然这个方案是比较粗糙的，还存在很多可以优化的地方：比如应该释放一些已经失效的变量的栈空间地址，使得已经开辟过的空间得到重复利用 等. **但是目前的方案已经能够比较完备地解决问题，因此暂时不做改动.** 特别地，对于 **sw** **lw** 指令中的偏移值立即数最大只能达到4095 也就是说目前我们栈空间的大小最多为4k. 如果想提高栈空间的上限，或许我们可以将高于4096的地址用其他寄存器保存，再基于那个地址使用偏移值对内存进行读写. ###### iiiii. 寄存器分配详细流程 为一个变量分配寄存器的流程图如下: ![reg_alloc](assets/reg_alloc.png) ##### 3. 压力测试 输入文件中的**reg-alloc.txt**提供了测试寄存器冲突分配的压力测试输入样例 输入文件中的**imm-alloc.txt**提供了测试常量分配的压力测试输入样例 **本项目的编译器目前为止已通过如上压力测试,完成了本课程全部实验以及附加题的要求**