nudt-compiler-cpp/doc/preliminary-design.md

编译系统实现赛道初赛设计文档

1. 项目概述

本项目面向 2026 年全国大学生计算机系统能力大赛编译系统设计赛实现赛道 ARM 后端方向，目标是实现一个从 SysY2026 源程序到 AArch64 汇编程序的自研编译器。

编译器整体采用经典分层架构：

SysY 源程序
  -> 词法/语法分析
  -> 语义分析
  -> IR 生成
  -> IR 优化
  -> MIR lowering
  -> MIR 优化
  -> 寄存器分配
  -> 栈帧布局
  -> AArch64 汇编输出

目标平台为 ARMv8-A 64 位架构，汇编输出兼容 GNU assembler，并可由比赛环境中的 gcc -march=armv8-a 汇编和链接。

2. 编译器模块划分

2.1 前端

前端负责完成源程序解析、基础错误检查和语义信息收集。

主要模块包括：

• frontend：基于 ANTLR4 生成的 SysY 语法分析器完成词法和语法分析。
• sem：完成作用域管理、符号表维护、类型检查、函数声明检查、数组维度检查和内建函数建模。
• irgen：将语法树和语义信息转换为自定义 IR。

语义分析阶段维护了函数副作用信息，包括函数是否可能读取/写入全局内存、参数指针内存等。这些信息后续被中端内存优化、函数内联和后端 memory peephole 使用。

2.2 中间表示 IR

IR 是本编译器的主要优化表示。IR 采用接近 SSA 的结构，包含：

• Module
• Function
• BasicBlock
• Instruction
• Value/User/Use
• GlobalValue
• 常量、数组、指针和基础标量类型

IR 支持整数、浮点、布尔、指针、多维数组、函数调用、分支、Phi、Load/Store、GEP、Memset 等核心指令。局部变量在初始 IR 中可以通过 alloca/load/store 表示，随后由 Mem2Reg 提升为 SSA 形式。

2.3 MIR 与后端

MIR 是面向机器后端的中间表示。IR lowering 后不直接固定到少数物理寄存器，而是先生成虚拟寄存器形式的机器指令，再进入后端优化与寄存器分配。

主要后端模块包括：

• Lowering：将 IR 指令转换为 MIR 指令。
• AddressHoisting：提升复杂地址计算，减少重复地址表达式。
• RegAlloc：执行图着色风格寄存器分配。
• FrameLowering：分配栈对象、spill slot 和 callee-saved 保存槽。
• AsmPrinter：根据分配结果生成最终 AArch64 汇编。
• mir/passes：执行机器级 peephole、CFG 清理和 spill reduction。

3. IR 优化设计

IR 优化流水线由 src/ir/passes/PassManager.cpp 管理，采用多轮迭代方式运行。每轮优化后如果 IR 继续变化，则再次执行相关 pass，直到达到固定点或达到迭代上限。

当前主要 IR 优化包括：

• Mem2Reg：将可提升的局部变量从内存形式提升为 SSA Phi 形式。
• ConstProp：常量传播。
• ConstFold：常量折叠和代数化简。
• DCE：删除无副作用且结果未使用的死代码。
• CFGSimplify：清理不可达块、简化分支和 Phi。
• CSE：基本公共子表达式消除。
• GVN：基于支配关系的全局值编号，跨基本块复用等价表达式。
• LoadStoreElim：IR 级 load/store 消除，包含 store-to-load forwarding、冗余 load 删除和部分死 store 删除。
• FunctionInlining：面向小函数的内联，使常量传播、GVN、DCE 等优化能跨函数生效。

这些优化的核心目标是减少冗余计算、减少内存访问、压缩控制流，并为后端生成更直接的机器代码。

4. 循环优化设计

循环优化建立在 DominatorTree 和 LoopInfo 之上。循环分析识别自然循环、循环头、latch、preheader、退出块和循环层次关系。

当前循环相关优化包括：

• LICM：循环不变代码外提。
• LoopMemoryPromotion：将循环内反复访问的安全内存位置提升为 SSA 标量，减少循环内 load/store。
• LoopUnswitch：对循环不变条件进行简单 unswitch，减少循环体内重复判断。
• LoopStrengthReduction：归纳变量相关强度削弱。
• LoopFission：在依赖允许时拆分循环，改善局部性和后续优化机会。
• LoopUnroll：对简单计数循环进行保守展开，降低循环控制开销。

内存相关循环优化使用 LoopMemoryUtils 中的简单 alias/mod-ref 分析，结合 induction variable、affine 下标表达、内存 root、逃逸分析和循环内读写集合判断优化合法性。

当前没有默认启用运行时多线程并行化。原因是比赛测试程序和运行环境对正确性、可复现性要求较高，且真正并行化需要额外 runtime、任务划分和同步机制。当前实现重点放在稳定的单线程循环优化上。

5. 后端优化设计

5.1 寄存器分配

后端寄存器分配采用图着色风格算法。主要步骤包括：

• 基于 MIR CFG 进行活跃变量分析。
• 构建虚拟寄存器干涉图。
• 识别 copy 相关节点并尝试合并。
• 根据寄存器类别区分 GPR 和 FPR。
• 标记跨调用活跃的虚拟寄存器，避免错误使用 caller-saved 寄存器。
• 对无法分配的虚拟寄存器创建 spill slot。
• 记录实际使用到的 callee-saved 寄存器，供栈帧阶段保存和恢复。

当前 GPR/FPR 可分配集合优先使用稳定寄存器集合，避免与 AArch64 ABI、临时 scratch register 和调用约定冲突。

5.2 MIR 优化

MIR 优化分为 pre-RA 和 post-RA 两部分。

pre-RA 阶段主要优化虚拟寄存器形式的 MIR：

• 冗余 copy 消除。
• 恒等算术简化，如 add x, 0、mul x, 1。
• 条件分支简化。
• 基于 CFG 的 load/store 状态传播。
• store-to-load forwarding。
• 冗余 store 删除。
• 简单 rematerialization 和 spill 压力降低。

post-RA 阶段主要在寄存器分配结果基础上继续清理：

• 删除物理寄存器层面等价的 copy。
• 利用分配结果消除无效 move。
• 清理跳转链、空块和落空分支。

5.3 AArch64 指令选择优化

汇编输出阶段加入了若干 ARMv8-A 专项优化：

• mul + add/sub 融合为 madd/msub。
• 常数乘法 lowering 为 lsl/add/sub/neg 组合。
• 常数除法和取模使用 signed magic multiply 降低 sdiv 使用。
• spill load/store 优先直接使用 [x29, #offset]、ldur/stur。
• callee-saved 保存恢复使用 stp/ldp 合并。
• 相邻且安全的普通 load/store 尝试合并为 ldp/stp。
• 输出层消除跳向直接后继基本块的无条件分支。
• 对 icmp/fcmp + condbr 做分支融合，减少中间布尔值物化。

浮点 fmadd/fmsub 没有默认启用。原因是它会改变单精度浮点逐步舍入语义，可能导致十六进制浮点输出样例不一致。当前只保留语义稳定的整数 madd/msub。

6. ARM 目标平台适配

比赛 ARM 赛道目标平台为 ARMv8-A AArch64，CPU 为 Cortex-A53。当前后端设计遵循以下原则：

• 汇编输出使用 GNU assembler 兼容语法。
• 函数调用遵循 AArch64 基本调用约定。
• 整数返回值使用 w0/x0，浮点返回值使用 s0。
• 前若干整数参数使用 x0-x7/w0-w7，浮点参数使用 s0-s7。
• 栈帧以 x29 作为 frame pointer。
• 使用 x16/x17 作为汇编输出阶段 scratch register，避免与寄存器分配结果冲突。
• callee-saved GPR/FPR 在函数入口保存、出口恢复。

考虑 Cortex-A53 的缓存和指令流水特性，优化策略重点放在减少访存、减少分支、减少冗余地址计算和降低 spill 数量上。

7. 正确性验证

项目提供脚本进行自动化验证：

scripts/lab2_build_test.sh
scripts/lab3_build_test.sh
scripts/verify_ir.sh
scripts/verify_asm.sh

其中 lab3_build_test.sh 会执行完整后端路径：

SysY -> compiler -> AArch64 asm -> aarch64-linux-gnu-gcc -> qemu-aarch64 -> diff output

近期后端专项优化完成后，已对除法、取模、复杂调用、嵌套循环、多参数、矩阵和浮点敏感样例进行了针对性验证，代表性样例包括：

• 17_div.sy
• 18_divc.sy
• 19_mod.sy
• 20_rem.sy
• 66_exgcd.sy
• 94_nested_loops.sy
• 32_many_params3.sy
• 34_multi_loop.sy
• 22_matrix_multiply.sy
• 37_dct.sy

该组 targeted regression 结果为：

10 PASS / 0 FAIL

后续初赛提交前仍需要在比赛平台或本地等价环境中执行完整功能测试和性能测试，确认最终提交版本没有回归。

8. 合规性说明

本项目没有直接使用 GCC、LLVM 等现有开源编译器框架源码，也没有基于这些框架进行裁剪。编译器核心 IR、优化 pass、MIR、寄存器分配和 AArch64 汇编输出均为本项目自研实现。

项目使用 ANTLR4 作为通用语法分析器生成工具，用于生成 SysY 语法分析相关代码。ANTLR4 属于比赛技术方案允许使用的通用词法/语法解析器生成工具。

本项目的优化策略均基于通用程序结构和目标平台特性，例如循环结构、支配关系、内存读写关系、表达式等价性、寄存器压力、AArch64 指令模式等。没有根据特定测试用例名称、函数名、输入数据模式或输出结果进行硬编码优化。

在开发过程中使用了大模型辅助进行代码阅读、优化方案讨论、部分代码生成和调试定位。所有生成或修改内容均经过人工审查、构建和测试验证，并已纳入项目源码维护。参赛队需要在最终提交材料中继续保留该说明，并能够解释相关实现原理和代码细节。

9. 当前限制与后续工作

当前编译器已经具备较完整的前端、IR 优化、MIR 后端、寄存器分配和 AArch64 汇编输出能力，但仍有进一步提升空间：

• 需要在初赛提交前执行完整功能和性能回归。
• NEON 自动向量化尚未实现，原因是当前 IR/MIR 暂无 vector type 和 vector register 表示，需要单独设计。
• 显式 spill/reload MIR 化尚未完全重构，目前主要在汇编输出阶段根据分配结果生成 spill 访存。
• 循环优化仍以保守正确性为先，后续可继续加强 loop interchange、tiling、store sinking 和更强依赖分析。
• 性能优化需要结合 ARM 平台实测热点继续推进，重点关注矩阵、FFT、稀疏访存、排序和大循环程序。

10. 总结

本编译器已经形成从 SysY 源程序到 AArch64 汇编输出的完整编译链路。前端能够完成语法和语义处理，中端具备 SSA 化、标量优化、内存优化、函数优化和循环优化能力，后端具备虚拟寄存器 MIR、图着色寄存器分配、栈帧布局、机器级 peephole 和 ARMv8-A 专项汇编优化。

后续初赛阶段的重点是继续保证功能正确性，并围绕 ARM Cortex-A53 的实际性能表现持续优化生成代码质量。