# Toyc **Repository Path**: junboz581/toyc ## Basic Information - **Project Name**: Toyc - **Description**: 本项目是 ToyC 编译器的 C++ 实现版本 - **Primary Language**: C++ - **License**: Not specified - **Default Branch**: main - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 0 - **Forks**: 0 - **Created**: 2025-12-09 - **Last Updated**: 2026-01-03 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README # ToyC Compiler (C++ 版本) 本项目是 ToyC 编译器的 C++ 实现版本。编译器以 ToyC 源文件（`.tc`）为输入,经过词法分析、语法分析、语义分析与代码生成等阶段,输出可在 RISC-V32 架构上运行的汇编代码（`.s` 文件）。 ## 项目目标 - 使用 **C++** 开发完整的 ToyC 编译器 - 支持从 ToyC 源代码生成有效、正确、规范的 RISC-V 汇编代码 - 满足课程提供的所有测试用例的语义与语法约束 - 尽可能实现中间代码与汇编优化,提高程序运行性能 ## ToyC 语言特性 ToyC 是 C 语言的子集,具有以下特性： - 支持函数定义、变量声明与赋值、控制流（if-else、while）、break、continue、return 等语句 - 支持 void 函数的汇编 - 支持变量的块作用域隐藏；支持多参数的函数调用 - 表达式支持基本的算术、关系、逻辑运算,运算规则与优先级同 C 语言 - 不支持函数的前向声明 - 不支持数组、指针、结构体、I/O、多文件等高级特性 - 每个程序必须包含一个 `int main()` 入口函数 详细文法和语义规则见课程任务书。 ## 编译器结构 编译器实现分为如下几个阶段： 1. **词法分析**：使用 **Flex** 生成词法分析器，将源文件解析为标记流（token stream） 2. **语法分析**：使用 **Bison** 生成语法分析器，根据文法规则构建抽象语法树（AST） 3. **语义分析**：进行类型检查、作用域检查、控制流合法性分析等 4. **中间表示生成**：生成适合进一步优化与代码生成的中间表示 5. **优化阶段**：如常量传播、死代码消除、常量函数内联等 6. **代码生成**：生成 RISC-V32 汇编代码 ### 词法/语法分析器实现 本项目使用业界标准工具 **Flex** 和 **Bison** 实现词法和语法分析： - **词法分析器** (`src/lexer.l`): 使用 Flex 定义词法规则，自动生成高效的词法分析代码 - **语法分析器** (`src/parser.y`): 使用 Bison 定义 LALR(1) 文法规则，自动生成语法分析代码 - **适配层** (`src/parser_adapter.cpp`): 提供统一的接口，保持与项目其他模块的兼容性 **备份**：手写版本的词法/语法分析器同样已备份供参考 ## 项目结构 ``` ├── include/ # 头文件目录 │ ├── ast.h # 抽象语法树定义 │ ├── ir.h # 中间表示定义 │ ├── lexer.h # 词法分析器 │ ├── parser.h # 语法分析器 │ ├── astToIR.h # AST→IR 转换 │ ├── irToAsm.h # IR→RISC-V 汇编生成 │ ├── cfg.h # 控制流图构建与优化入口 │ ├── optimization.h # 多Pass优化框架与活跃变量分析 │ ├── regAllocation.h # 寄存器分配策略（线性扫描分配） │ ├── print_ast.h # AST 打印器 │ └── print_ir.h # IR 打印器 │ ├── src/ # 源文件目录 │ ├── ast.cpp # AST 实现 │ ├── ir.cpp # IR 实现 │ ├── lexer.l # Flex 词法分析规则 │ ├── parser.y # Bison 语法分析规则 │ ├── parser_adapter.cpp # 词法/语法分析器适配层 │ ├── astToIR.cpp # AST→IR 转换 │ ├── irToAsm.cpp # IR→RISC-V 汇编生成 │ ├── cfg.cpp # 控制流图构建及常量传播 │ ├── optimization.cpp # 活跃变量分析 │ ├── regAllocation.cpp # 寄存器分配策略（线性扫描分配） │ ├── print_ast.cpp # AST 打印器 │ ├── print_ir.cpp # IR 打印器 │ └── main.cpp # 编译器主入口 │ ├── backup_handwritten/ # 手写版本词法/语法分析器备份 │ ├── lexer.cpp │ └── parser.cpp │ ├── test/ # 测试文件目录 │ ├── functional/ # 功能测试用例 │ └── performance/ # 性能测试用例 │ ├── CMakeLists.txt # CMake 构建配置 └── README.md # 本文件 ``` ## 编译方法 ### 前置要求 - C++17 或更高版本的编译器（g++/clang++） - CMake 3.10 或更高版本 - **Flex** 2.5 或更高版本 - **Bison** 2.3 或更高版本 ### 编译步骤 ```bash mkdir build cd build cmake .. make ``` 编译过程中，Flex 和 Bison 会自动生成词法分析器和语法分析器的 C++ 代码。 编译完成后,可执行文件为 `toyc_compiler`。 ## 使用方法 本编译器从标准输入流（stdin）中读取源程序代码,最终向标准输出流（stdout）中写入汇编程序代码。 ```bash ./toyc_compiler [选项] < input.tc > output.s ``` ### 可用选项 - `-print_ast`: 打印抽象语法树 - `-print_ir`: 打印中间表示 - `-block-ir`: 使用块级 IR（启用优化） - `-opt`: 启用优化的编译策略 - `-print_live`: 打印活跃变量分析结果 - `-print_alloc`: 打印寄存器分配结果 ### 示例 ```bash # 基本编译 ./toyc_compiler < test/fib.tc > test/fib.s # 启用优化并打印 IR ./toyc_compiler -opt -print_ir < test/fib.tc > test/fib.s ``` ## 实现的功能 ### 核心功能 - **正确的语义翻译和汇编**：完整支持 ToyC 语言的所有特性 - **完整的控制流处理**：正确处理 if-else、while、break、continue、return 等控制流 - **函数调用支持**：支持递归调用、多参数调用（包括超过 8 个参数的溢出参数处理） ### 寄存器分配策略 - **线性扫描寄存器分配算法**：基于活跃区间的寄存器分配 - **调用者保存寄存器（Caller-saved）**：使用 a0-a7, t0-t3 作为可分配寄存器 - **临时寄存器 Spill 策略**：所有 IR 中的临时寄存器（t0, t1, t2, ...）统一 spill 到栈上，避免与工作寄存器冲突 - **智能工作寄存器选择**：Binop/Unop 指令动态选择不与操作数冲突的工作寄存器（优先使用 t4, t5, t6） ### 动态栈帧分配策略 - 根据函数实际需要的变量数量动态计算栈大小 - 正确处理函数参数、局部变量、临时寄存器 spill 空间 - 完全符合 RISC-V ABI 标准的栈帧布局 - 正确处理函数调用后参数寄存器被破坏的情况 ### 代码优化 本编译器实现了类似 LLVM/Clang 的多 Pass 优化框架，支持多轮迭代优化直到不动点。 #### 优化 Pass 列表 1. **常量折叠（Constant Folding）** - 编译时计算常量表达式：`2 + 3` → `5` - 代数恒等式简化： - `x * 1` → `x`，`x + 0` → `x`，`x * 0` → `0` - `x - x` → `0`，`x - 0` → `x` - `0 - x` → `-x`（一元取负） - `x + x` → `x * 2`（加法强度削弱） - `x << 0` → `x`，`x >> 0` → `x` - `0 << x` → `0`，`0 >> x` → `0` - 强度削弱：`x * 2` → `x << 1` 2. **常量传播（Constant Propagation）** - 跟踪变量的常量值，替换使用处为立即数 - 使用工作列表算法进行数据流分析 3. **复写传播（Copy Propagation）** - 将 `a = b; ... use(a)` 替换为 `use(b)` - 追踪复写链，消除中间变量 4. **公共子表达式消除（CSE）** - 识别相同的表达式计算，复用之前的结果 - 局部 CSE 在基本块内进行 5. **死代码消除（Dead Code Elimination）** - 删除结果从未被使用的指令 - 使用活跃变量分析识别死代码 6. **不可达代码消除（Unreachable Code Elimination）** - 删除永远不会执行的基本块 - 从入口块进行 DFS 可达性分析 7. **分支简化（Branch Simplification）** - 简化条件恒为真/假的分支 - `if (0) { ... }` → 直接删除 8. **跳转链简化（Jump Threading）** - 将跳转到只包含另一个跳转的块简化为直接跳转到最终目标 9. **空块消除（Empty Block Elimination）** - 删除只包含一个跳转的空块 10. **循环不变量外提（LICM）** - 将循环中不变的计算移到循环外 - 支持嵌套循环（从内到外处理） - 仅外提单次定义的变量，确保正确性 11. **循环累加识别优化（Loop Accumulation Optimization）** - 识别循环中的简单累加模式：`while (i < N) { sum += value; i++; }` - 转换为乘法：`sum = N * value` - 支持识别间接累加模式（通过临时寄存器） - 显著减少循环迭代次数和计算开销 12. **归纳变量优化（Induction Variable Elimination）** - 识别循环中的归纳变量（每次迭代增加固定步长的变量） - 分析归纳变量的使用模式 - 为后续优化（如强度削弱）提供信息 - 支持识别间接归纳变量模式 13. **死循环消除（Dead Loop Elimination）** - 删除结果不被循环外代码使用的循环 - 检测循环无副作用（无函数调用、无存储操作） 14. **函数内联（Function Inlining）** - 将小函数的调用展开为函数体 - 自动识别可内联的函数（代码量小、无递归、单一返回点） - 对频繁调用的辅助函数（如 `mod`、`fastPow`）效果显著 - 内联阈值：30 条有效指令（不含 Label、Ret、Goto） 15. **模运算优化（Modulo Optimization）** - 识别和消除重复的模运算：`(a % m) % m` → `a % m` - 代数简化： - `x % 1` → `0` - `0 % x` → `0` - 针对数学密集型程序（如 `p09_advanced_graph.tc`、`p10_advanced_matrix.tc`）优化模运算模式 16. **尾递归优化** - 将尾递归转换为循环 ### 栈帧布局 ``` 栈帧布局（从低地址到高地址）： sp+0 ～ sp+(N-9): 变量区域（函数参数、局部变量、临时寄存器spill） sp+(N-8): 保存s0（旧的帧指针） sp+(N-4): 保存ra（返回地址） s0 = sp + N （指向栈帧底部） ``` 其中 N 是栈帧大小（16 字节对齐） ### 叶函数优化 对于简单的叶函数（不调用其他函数、不使用 IR 临时寄存器、参数未被修改），会进行特殊优化： 1. **删除完整的栈帧设置**：不需要保存 ra 和 s0，不需要调整 sp 2. **直接使用参数寄存器**：参数直接使用 a0-a7 寄存器，不需要保存到栈 3. **使用临时寄存器进行中间计算**：使用 t0-t6 寄存器保存中间结果 ### 溢出参数处理 对于需要处理溢出参数（超过 8 个参数）的函数： 1. **调用方**：在 call 指令前，先调整 sp 为溢出参数腾出空间，然后存储参数，调用函数后再恢复 sp 2. **被调用方**：从 s0 向正方向偏移来加载溢出参数，正确计算偏移量 ### 函数调用后参数保护 对于非叶函数，编译器会分析哪些参数在函数调用后仍会被使用，并将这些参数保存到栈上。这避免了 RISC-V 调用约定中 a0-a7 寄存器被调用破坏导致的值丢失问题。 编译器采用保守策略： - **无循环场景**：只保存在函数调用之后被使用的参数 - **有循环场景**：当检测到向后跳转（循环）时，保守地保存所有被使用的参数，因为循环可能导致调用后再次使用调用前的参数值 ## 循环优化详解 针对循环密集型代码（如 `test/performance/p07_loop.tc`），编译器实现了以下专门的循环优化： ### 1. 循环不变式外提（Loop-Invariant Code Motion, LICM） **原理**：将循环中每次迭代都计算相同结果的表达式移到循环外 **示例**： ```c // 优化前 while (i < n) { int t1 = x * 3 + 1; // 循环不变 int t2 = y * 3 + 1; // 循环不变 result += t1 + t2; i++; } // 优化后 int t1 = x * 3 + 1; int t2 = y * 3 + 1; int t3 = t1 + t2; while (i < n) { result += t3; i++; } ``` **效果**：减少循环内的冗余计算，提高执行效率 ### 2. 循环累加识别优化 **原理**：识别简单的累加循环并转换为乘法 **示例**： ```c // 优化前 int sum = 0; int k = 0; while (k < 5) { sum = sum + value; k = k + 1; } // 优化后 int sum = 5 * value; ``` **效果**：将 O(n) 的循环累加优化为 O(1) 的乘法运算 **实际应用**：在 `p07_loop.tc` 中成功识别并优化了： - 内层循环：`while (k < 5) { t5 += t3; k++; }` → `t5 = 5 * t3` - 中层循环：10次迭代的j循环被完全消除 ### 3. 运算强度削弱（Strength Reduction） **原理**：用更廉价的运算替代昂贵的运算 **示例**： - `x * 2` → `x << 1` （乘法转换为移位） - `x * 8` → `x << 3` ### 4. 归纳变量优化 **原理**：识别和优化循环中的归纳变量（每次迭代增加固定值的变量） **效果**： - 识别基本归纳变量：`i = i + 1` - 识别派生归纳变量：`j = 2 * i + 1` - 为其他优化提供信息 ### 优化效果示例 对于 `test/performance/p07_loop.tc`（包含三层嵌套循环）： **优化前代码结构**： ```c while (i < n) { // 外层循环：n次 t1 = x * 3 + 1; // 循环不变式 t2 = y * 3 + 1; // 循环不变式 t3 = t1 + t2; // 循环不变式 j = 0; while (j < 10) { // 中层循环：10次 k = 0; t5 = 0; while (k < 5) { // 内层循环：5次 t5 += t3; // 累加 k++; } t4 = t1 + t2 - t3; // = 0 j++; } result = ((result + (t4 - t5) % MOD) % MOD - i % MOD) % MOD; i++; } ``` **优化后代码结构**： ```c t1 = x * 3 + 1; // 循环不变式外提 t2 = y * 3 + 1; t3 = t1 + t2; t5_7 = 5 * t3; // 内层循环优化为乘法 t13 = -t5_7; // 0 - x 优化为 -x t14 = t13 % MOD; // 常量折叠 while (i < n) { // 只剩外层循环 result = ((result + t14) % MOD - i % MOD) % MOD; i++; } ``` ## 待改进 - 寄存器分配策略可进一步优化，提高寄存器复用率 - 循环展开优化 - 更多的窥孔优化 - 全局值编号（GVN） - 部分冗余消除（PRE） - 循环向量化