BUAA 2025 编译器设计说明

实现词法分析 + 递归下降语法分析 + 语义分析（符号表与约束检查）+ LLVM IR 中间代码生成 + 中端优化 + Mips 目标代码生成

仓库地址：wrongization/compile: 2025BUAA编译代码仓库

1. 总体目标

该项目实现一个精简 C / SysY 风格语言的编译器五个核心阶段：

词法分析—— 将源代码字符流转换为 Token 序列，并进行最基本的错误分类。
语法分析—— 基于递归下降结构 + FIRST 集判断与有限回溯，将 Token 序列还原为抽象/混合语法树（目前更接近具体语法树）。
语义分析—— 基于作用域栈构建符号表，完成重定义、未定义引用、函数调用实参与形参检查、左值可赋性、return 规则、循环控制语句使用、printf 占位符数量等检查。
中间代码生成和优化—— 遍历语法树生成 LLVM IR 中间代码，包含基本块管理、寄存器分配、控制流处理、优化 pass 框架等。
目标代码生成—— 将 LLVM IR 转换为 MIPS 汇编代码。

设计强调：

模块化：frontend 下按阶段与节点类型分类，midend 下按 IR 生成与优化分类。
可扩展：BNF 规则集中于 frontend/BNF/Gram.java，IR 生成逻辑集中于 midend/LLVMGenerator.java，优化 pass 可插拔式添加，Mips 生成逻辑集中于 backend/MIPSGenerator.java。
错误恢复策略：仅在缺失分号、右括号、右中括号时报错，节点仍然添加并继续。
输出：词法结果 lexer.txt，语法树 + 规约序列 parser.txt，符号表 symbol.txt，所有阶段合并错误 error.txt，LLVM IR 代码 llvm_ir.txt，Mips 目标代码 mips.txt。
近期修复：后端在 icmp/zext 的布尔结果生成后立即落栈并标记为 clean，防止寄存器复用导致布尔打印/逻辑判断拿到旧值（触发场景：开启 Mem2Reg + Phi 展开 + StrengthReduction + GVN + DCE 时的 not 输出偏差）。

2. 目录结构与职责

README.md                   // 本文档
config.json                 // 配置
Compiler.java               // 统一驱动：文件读取、注释预处理、阶段调度、结果落盘
frontend/
  Lexer.java                // 词法分析器（行扫描 + 正则分类 + 手写多字符运算符匹配）
  Parser.java               // 语法分析入口（调用 Gram.CompUnit）
  Symboler.java             // 语义分析入口（调用 Sym.CompUnit）
  BNF/
    Gram.java               // 所有产生式 + 递归下降实现 + FIRST 集登记
    Sym.java                // 语义遍历：依据语法节点逐步建表与检查
  nodes/
    Node.java               // 抽象语法树节点基类（含输出 DFS）
    Symbol.java             // 符号条目：变量/数组/常量/函数/符号表（含形参列表与作用域号）
    Token.java              // 终结符 Token 封装
    Unit.java               // 非终结符节点
  result/
    Result.java             // 阶段结果与错误集合基类
    Scope.java              // 作用域记录：符号表节点、编号、类型、返回态
    SymbolResult.java       // 语义阶段结果（符号表、作用域栈、检查接口）
    TokenResult.java        // 词法阶段结果
    UnitResult.java         // 语法阶段结果
midend/
  LLVMGenerator.java        // LLVM IR 生成主逻辑（遍历 AST + 指令构建）
  ir/
    ModuleBuilder.java      // 全局声明管理（全局变量、常量数组、字符串池）
    FunctionContext.java    // 函数局部上下文（寄存器/标签计数、符号表）
    Addr.java               // 地址/变量抽象
    Value.java              // 值抽象（立即数/寄存器/全局变量）
    LocalVar.java           // 局部变量/数组元素的地址与类型信息
    StringConst.java        // 字符串常量封装
  opt/
    PassManager.java        // 优化 pass 管理器
    OptimizationPass.java   // 优化 pass 接口（含 normalizeIndent 辅助方法）
    OptimizationOptions.java // 优化选项配置
    SSATransformPass.java   // SSA 转换（前端已完成，NO-OP）
    Mem2RegPass.java        // 内存到寄存器提升（含 Phi 节点最小化）
    PhiEliminationPass.java // Phi 节点删除（基于内存展开，必要时为使用块注入 reload 保证支配关系）
    InstSimplifyPass.java   // 指令简化（zext 消除、常量折叠、代数简化；分支改写默认关闭以避免后端分支语义歧义）
    FunctionInliningPass.java // 函数内联（小函数、递归检测、寄存器重命名）
    LoopUnrollingPass.java  // 循环展开（完全/部分展开、智能决策）
    ConstantPropagationPass.java // 常量传播（含数组常量传播）
    StrengthReductionPass.java // 强度削减（乘除法→移位、小常数优化）
    GVNPass.java            // 全局值编号（公共子表达式消除、重复 load 消除）
    CFGSimplifyPass.java    // 控制流简化（常量分支折叠、死块删除）
    TailCallOptimizationPass.java // 尾递归优化（尾调用→循环转换
    DeadCodeEliminationPass.java // 死代码删除
backend/
  MIPSGenerator.java        // MIPS 目标代码生成
  MIPSContext.java          // MIPS 生成上下文

3. 词法分析设计

3.1 处理流程

Compiler 逐行读取 testfile.txt，按照行存入 lines 列表，然后调用 preprocess 进行注释预处理，存入 preprocessedLines 列表。
Lexer 调用analyze 方法，传入 preprocessedLines 列表。
注释预处理后的非空行传递给 analyzeLine 方法：
- 基于单次线性扫描：
  - 维护临时 StringBuilder token 累积潜在标识符 / 数字 / 字符串常量。
  - 每遇到：
    - 双字符候选（如 <=, >=, ==, !=, &&, ||）优先匹配。
    - 单字符分隔符 / 运算符立即截断并归约前一 Token。
    - " 进入字符串提取直到下一个 "（无转义支持，缺失闭合时报错）。
  - 行尾人为补一空格触发最后一个 token flush。

3.2 关键数据结构

关键字映射 KEYWORDS：Map<String, TokenType>
符号映射 SYMBOLS：包含单双字符运算符，提前硬编码。
Token 分类优先级：符号 > 关键字 > 字符串常量 > 标识符 > 整数常量 > 错误。

3.3 正则与最小化判断

类别	正则 / 判定	说明
标识符	`[a-zA-Z_][a-zA-Z0-9_]*`	兼容下划线开头
整数常量	`\d+`	仅十进制
字符串常量	`"[^\"]*"`	不含内部引号（无转义机制）

3.4 错误处理策略

非法字符输出报错，不产生“a”错误，修改Success为false。
针对孤立 | 或 & 容错：token 仍然映射为 OR 或 AND（降低级联错误），输出错误信息“a”

3.5 设计亮点

使用函数 handleToken() 统一 flush 逻辑，避免重复 if 栈。
双字符运算符通过前瞻 line.substring(i,i+2) 零回溯匹配。
将错误与成功 token 均写入序列，以定位后续语法文法更多错误。

4. 语法分析设计

4.1 方法论

采用手写递归下降解析器，不借助自动生成器，优势：

代码即文法：Gram 内部类一一对应产生式，易维护。
通过 FIRST 集 + 适度向前看消除二义性（函数定义 vs 变量声明、Unary/Call 分支、Stmt的EXP和Lval等）。
运行期构建语法树节点 Unit（非终结符）与 Token（终结符）混合结构，可直接用于后继语义/IR。

4.2 文法（简化 BNF 摘要）

（与代码保持一致，省略空产生式 [] 与重复 {} 的括号说明）

CompUnit      -> {Decl} {FuncDef} MainFuncDef
Decl          -> ConstDecl | VarDecl
ConstDecl     -> 'const' BType ConstDef {',' ConstDef} ';'
ConstDef      -> Ident {'[' ConstExp ']'} '=' ConstInitVal
ConstInitVal  -> ConstExp | '{' [ ConstExp {',' ConstExp} ] '}'
BType         -> 'int'
VarDecl       -> ['static'] BType VarDef {',' VarDef} ';'
VarDef        -> Ident {'[' ConstExp ']'} [ '=' InitVal ]
InitVal       -> Exp | '{' [ Exp {',' Exp} ] '}'
FuncType      -> 'void' | 'int'
FuncDef       -> FuncType Ident '(' [FuncFParams] ')' Block
MainFuncDef   -> 'int' 'main' '(' ')' Block
FuncFParams   -> FuncFParam {',' FuncFParam}
FuncFParam    -> BType Ident ['[' ']']
Block         -> '{' { BlockItem } '}'
BlockItem     -> Decl | Stmt
Stmt          -> LVal '=' Exp ';'
               | [Exp] ';'
               | Block
               | 'if' '(' Cond ')' Stmt ['else' Stmt]
               | 'for' '(' [ForStmt] ';' [Cond] ';' [ForStmt] ')' Stmt
               | 'break' ';'
               | 'continue' ';'
               | 'return' [Exp] ';'
               | 'printf' '(' STRCON {',' Exp} ')' ';'
ForStmt       -> LVal '=' Exp { ',' LVal '=' Exp }
Exp           -> AddExp
Cond          -> LOrExp
LVal          -> Ident {'[' Exp ']'}
PrimaryExp    -> '(' Exp ')' | LVal | Number
Number        -> INTCON
UnaryExp      -> PrimaryExp | Ident '(' [FuncRParams] ')' | UnaryOp UnaryExp
UnaryOp       -> '+' | '-' | '!'
FuncRParams   -> Exp {',' Exp}
MulExp        -> UnaryExp { ('*'|'/'|'%') UnaryExp }
AddExp        -> MulExp { ('+'|'-') MulExp }
RelExp        -> AddExp { ('<' | '>' | '<=' | '>=') AddExp }
EqExp         -> RelExp { ('==' | '!=') RelExp }
LAndExp       -> EqExp { '&&' EqExp }
LOrExp        -> LAndExp { '||' LAndExp }
ConstExp      -> AddExp

4.3 关键消除二义性/左递归策略

场景	冲突来源	解决手法	代码位置
Decl vs FuncDef vs MainFuncDef	`int Ident ( ...` 既可能是函数（主函数）定义也可能是变量声明（数组）	预读 `INTTK IDENFR LPARENT` 判定	`CompUnit.parse` while 循环条件内部
赋值语句 vs 表达式语句	`Ident ...` 开头既可能是 LVal 或普通EXP	调用 `LVal.parse_back` 预读判断后跟 `ASSIGN`	`Stmt.parse` 第一分支
UnaryExp 分支冲突	`Ident` 既可能是函数调用也可能是 LVal/PrimaryExp	向前看后一个 token 是否 `LPARENT`	`UnaryExp.parse`
左递归（E -> E op T）	直接写递归会无限	改写为迭代收集，再“回填”成左结合树	`MulExp`, `AddExp`, `RelExp`, `EqExp`, `LAndExp`, `LOrExp`

左结合树重构技巧

解析形如 A op B op C op D：

线性收集为节点序列 [A, op1, B, op2, C, op3, D]。
逆向折叠构造：最右 (C op3 D) 作为最里层，逐步外包，保证遍历输出次序仍符合递归下降生成顺序。代码以 for (int i = children.size()-1; i>0; i-=2) 反向建新父节点。

4.4 FIRST 集与可选/重复部分

每个内部类维护 FirstToken 静态列表；在构造块中组合所依赖子产生式 FIRST 集。
可选部分 [X] 统一通过 if (X.FirstToken.contains(currentType)) 判定。
重复部分 {X} 使用 while，并在体内推进 pos。

4.5 错误检测与恢复

expectToken(result, parent, tokens, pos, expectedType)：

若匹配失败：
- 针对 ;，),]追加错误
- 其他情况控制台输出dubug信息
- 不回退、不跳过（当前实现直接返回原 pos，后续可能导致级联，但保留树结构）。
成功：将终结符挂入父节点。

对于报错i，即缺少;，对于stmt->[exp] ';',在块的最后可能缺失语句，这时仍然需要报错缺少i,需要将}纳入lval和exp的判断分支，然后进行预读回溯。

LVal.parse_back

左值和表达式的预读判断。

不实际移动pos，虚假处理一个lval，但是注意最后一个“]”不能改变temp的success判断，只做pos移动，同时语法部分success的修改只发生在除去）]}以外的情况下，如果缺少右括号不修改success。

4.6 语法树输出策略

Node.output() 对非终结符采用后序遍历（children 先输出到AST列表，再输出自身 <Type>，对于题目要求的<BlockItem>, <Decl>, <BType>实际添加节点，但是输出时删去，最后统一输出AST列表到文件）。

4.7 设计亮点总结

点	价值
统一 `Unit` 节点枚举	避免字符串判断，提升类型安全与可维护性
局部 FIRST 集缓存	减少重复分支判断逻辑，可做 LL(1) 验证扩展
`lval`预读函数 `parse_back`	将模糊前缀解析与正式构建分离，降低副作用
左结合逆向折叠算法	保持语义正确 + 最小化栈深度
错误类型内聚 `expectToken`	单点维护错误策略，方便扩展更多错误码

4.8 FIRST集列表

CompUnit: [CONSTTK, INTTK, STATICTK]
Decl: [CONSTTK, INTTK, STATICTK]
ConstDecl: [CONSTTK]
ConstDef: [CONSTTK]
ConstInitVal: [LPARENT, IDENFR, INTCON, IDENFR, PLUS, MINU, NOT, LBRACE]
BType: [INTTK]
VarDecl: [INTTK, STATICTK]
VarDef: [IDENFR]
InitVal: [LPARENT, IDENFR, INTCON, IDENFR, PLUS, MINU, NOT, LBRACE]
FuncDef: [VOIDTK, INTTK]
FuncType: [VOIDTK, INTTK]
MainFuncDef: [INTTK]
FuncFParams: [INTTK]
FuncFParam: [INTTK]
Block: [LBRACE]
BlockItem: [CONSTTK, INTTK, STATICTK, IDENFR, LPARENT, IDENFR, INTCON, IDENFR, PLUS, MINU, NOT, SEMICN, LBRACE, IFTK, FORTK, BREAKTK, CONTINUETK, RETURNTK, PRINTFTK]
Stmt: [IDENFR, LPARENT, IDENFR, INTCON, IDENFR, PLUS, MINU, NOT, SEMICN, LBRACE, IFTK, FORTK, BREAKTK, CONTINUETK, RETURNTK, PRINTFTK]
ForStmt: [IDENFR]
Exp: [LPARENT, IDENFR, INTCON, IDENFR, PLUS, MINU, NOT]
Cond: [LPARENT, IDENFR, INTCON, IDENFR, PLUS, MINU, NOT]
LVal: [IDENFR]
PrimaryExp: [LPARENT, IDENFR, INTCON]
Number: [INTCON]
UnaryExp: [LPARENT, IDENFR, INTCON, IDENFR, PLUS, MINU, NOT]
UnaryOp: [PLUS, MINU, NOT]
FuncRParams: [LPARENT, IDENFR, INTCON, IDENFR, PLUS, MINU, NOT]
MulExp: [LPARENT, IDENFR, INTCON, IDENFR, PLUS, MINU, NOT]
AddExp: [LPARENT, IDENFR, INTCON, IDENFR, PLUS, MINU, NOT]
RelExp: [LPARENT, IDENFR, INTCON, IDENFR, PLUS, MINU, NOT]
EqExp: [LPARENT, IDENFR, INTCON, IDENFR, PLUS, MINU, NOT]
LAndExp: [LPARENT, IDENFR, INTCON, IDENFR, PLUS, MINU, NOT]
LOrExp: [LPARENT, IDENFR, INTCON, IDENFR, PLUS, MINU, NOT]
ConstExp: [LPARENT, IDENFR, INTCON, IDENFR, PLUS, MINU, NOT]

5. 语义分析设计

5.1 核心思路与职责

采用“按语法树语义遍历”的方式：Symboler.analyze(root, result) 入口调用 Sym.CompUnit.symbolize，以与语法产生式一致的内部类分发，逐节点处理。
建立“作用域栈”（SymbolResult.scopes），每进入 Block/函数体等新作用域时 pushnumber(type)，离开时 popnumber()；每个作用域拥有一个符号表节点（Symbol(SymbolTable)），编号自增并记录在符号条目的 number 字段；记录深度depth，以便中间代码生成使用。
symbolize()每层传入上一层type，block进入后读取，然后重置为普通类型。for对于stmt传入for类型，用于判断单句for语句。
符号输出为“扁平列表”symbols，但作用域查询基于栈顶至全局逐层查找，支持同名屏蔽。
语义检查与建表同步进行，尽量沿语法树遍历顺序定位并报告错误。

5.2 符号模型与条目类型

frontend/nodes/Symbol.SymbolType 支持：

变量：Int、StaticInt
数组：IntArray、StaticIntArray
常量：ConstInt、ConstIntArray
函数：IntFunc、VoidFunc（含形参列表 parameterlist）
特殊：SymbolTable（仅作为作用域内的符号表根节点）

函数符号的形参列表在函数体建表时补全：先插入函数符号（参数列表为空），解析 FuncFParams 到临时 SymbolResult，注意此时也有可能报错重定义，但是报错存储在temp，需要之后读取存入真正的result，进入函数体 Block 前将形参迁入当前作用域并回填到函数符号的 parameterlist。

内建函数：在编译单元开始时注入 getint（IntFunc，无参数），用于通过语义检查；落盘到 symbol.txt 前会移除该内建条目（仅用于检查与查询）。

5.3 作用域类型与返回值约束

Scopetype：RETURNFUNC、NORETURNFUNC、NORMALBLOCK、PARAMS、FOR。

仅当作用域类型为 RETURNFUNC 时，进入作用域时将 returned=false，return时将当前作用域修改为true（文法要求只判断结尾处的return）
如果向上层找，inreturn()==false且return后方有数值，报错不匹配return（错误码f）。
block结束时候判断是否为true，离开作用域若仍为 false，报告缺失 return（错误码 g），报错行号定位在函数 } 行。
MainFuncDef 按返回值函数处理（RETURNFUNC），要求显式 return。
FOR 用于标识循环体，配合 infor()和上一层传入的type（单语句for）检查 break/continue 的合法性。

5.4 主要检查点（与触发位置）

重定义（b）：在当前作用域 localhasSymbol 命中即报错。位置：ConstDef、VarDef、FuncDef、FuncFParam。
未定义/非法引用（c）：
- 标识符用作变量/数组：LVal 未在任一可见作用域出现globalhasSymbol未命中则报错。
- 标识符用作函数调用：不存在或非函数同名符号时报错。
函数调用实参与形参：
- 数量不匹配（d）。
- 维度不匹配（e）：仅区分“标量 vs 数组”。当前实现通过实参与形参的“是否数组”判定；实参侧以表达式原样字符串去符号表查询是否为数组，未做常量折叠/类型推导。
return 规则：
- 无返回值函数含有带返回值的 return（f）。
- 有返回值函数末尾缺少 return（g）。
左值可赋性（h）：赋值语句左侧为常量、函数名或仅为数组名（缺少下标）时非法。
循环控制语句位置（m）：不在 for 语义区域内使用 break/continue。
printf 校验（l）：格式串中 %d 的数量须与后随表达式个数一致，仅统计“%d”模式，不解析其他转义。

限制与约定：

数组”大小与初始化值”的表达式未进行常量折叠与语义校验,当前仅登记名称与数组属性。
实参数组判断采用表达式字符串级别的符号表查询,未进行更深的类型推断。
static 变量作用域处理：static 关键字修饰的变量在语义分析阶段仍按局部变量处理,登记在当前作用域的符号表中,类型标记为 StaticInt / StaticIntArray。与普通局部变量的区别在中间代码生成阶段体现：static 变量会被提升为全局变量(但仅在声明函数内可见),生成全局声明而非栈上 alloca,从而保证生命周期跨函数调用。

5.5 符号表输出

symbol.txt 输出经作用域编号排序后的条目，格式为：<scopeNumber> <name> <SymbolType>。内建 getint 不输出。该文件用于辅助评测与调试。

5.6错误与日志

错误码	触发条件	说明
a	词法非法 token	含未识别字符（如孤立 \|、& 等）
i	缺少 `;`	语句/声明结束分号缺失（语法阶段）
j	缺少 `)`	括号未闭合（语法阶段）
k	缺少 `]`	数组下标/形参方括号未闭合（语法阶段）
b	符号重定义	同一作用域内重复定义变量/常量/函数（语义阶段）
c	未定义引用/非法使用	变量或函数未定义，或以非函数实体进行函数调用（语义阶段）
d	实参与形参数量不匹配	函数调用（语义阶段）
e	实参与形参类型不匹配	仅区分数组与标量（语义阶段）
f	无返回值函数带返回值	`return exp;` 出现在 `void` 函数内（语义阶段）
g	有返回值函数缺少 return	函数末尾未返回（报 `}` 行）（语义阶段）
h	非法左值赋值	对常量/函数名/数组名（无下标）赋值（语义阶段）
l	printf 占位符不匹配	`%d` 数量与实参个数不一致（语义阶段）
m	非循环内使用 break/continue	语句出现在非 `for` 区域（语义阶段）
(预留)	其他可扩展	如缺少 `}`、函数重定义细化等

6. 中间代码生成设计

6.1 核心思路与架构

中间代码生成阶段将语法树转换为 LLVM IR（中间表示），采用以下设计原则：

单遍遍历：基于语法树结构，对每个节点递归生成对应的 IR 指令
静态单赋值（SSA）形式：每个虚拟寄存器只赋值一次，通过寄存器计数器自动生成唯一标识
基本块管理：自动插入标签、维护控制流跳转
类型系统：支持 i32（整数）、i32（指针/数组）、i8（字符串指针）
优化框架：可插拔式 pass 管理器，支持后续添加各类优化

6.2 关键组件

6.2.1 ModuleBuilder（全局管理器）

职责：

管理全局变量声明（globalDecls）
字符串常量池（stringPool + stringCount）
常量数组与初始化值映射（constArrays、constArraysInit）
函数形参信息缓存（funcParamIsArray、funcParamNumber）
函数返回值类型映射（funcRet）

关键方法：

addGlobalDecl(String)：添加全局声明
addStringConst(String)：注册字符串常量并返回全局变量名（如 @.str.0）
addConstArray(String, ArrayList<Integer>)：登记常量数组
build()：输出完整的 LLVM IR 模块（声明 + 全局变量 + 函数定义）

附加说明（局部 const 缓存）：

为了支持函数内部常量（const 标量与 const 数组）在常量表达式中的求值，生成器在生成局部 const 定义时会把其常量值写入 ModuleBuilder 的常量映射；键使用 funcName::varName 的复合形式，以区分同名的全局与局部常量。这样 evalConst 在遇到 LVal 时可以优先查找当前函数作用域的常量缓存，再回退到模块级全局常量缓存。该策略为低侵入实现，后续可考虑把常量缓存改为显式的 per-function map 以提升可维护性。

6.2.2 FunctionContext（函数上下文）

职责：

虚拟寄存器计数（regCounter）：生成 %1, %2, ...
基本块标签计数（labelCounter）：生成 label1, label2, ...
局部变量表（localVars）：变量名 → LocalVar（地址、类型、维度）
作用域深度管理（depth）

关键方法：

nextReg()：分配新寄存器
nextLabel()：分配新标签
addLocalVar(String, Addr, ...)：登记局部变量
lookupVar(String)：查找变量（支持作用域穿透）
enterScope() / exitScope()：维护作用域深度

6.2.3 LLVMGenerator（IR 生成核心）

主要职责与设计要点：

目标：从前端语法树生成语义正确、风格统一且可被后端优化器（text-based passes）消费的 LLVM IR 文本。
原则：生成的 IR 要满足下列条件：
- 可读性：每个基本块、寄存器、全局常量都有可预测命名（便于调试与测试）。
- 可重构性：避免把语义嵌入注释或不可解析的格式，保证优化 pass 能通过文本正则或行级解析可靠工作。
- 语义等价：生成的指令序列在语义上等价于源程序（符合 SysY/C 子集语义），并遵守左到右求值约定（printf 等处明确实现）。

主要流程（简要）：

预处理：收集全局/函数签名、常量数组与字符串常量表（ModuleBuilder）。
生成运行时声明：输出 declare/内建 runtime（getint, putint, putch, putstr 等）。
遍历 AST：按产生式分发到对应 gen* 方法（genCompUnit, genFuncDef, genBlock, genStmt, genExp 等）。
每个函数：创建 FunctionContext（寄存器/标签计数器、局部变量表），生成入口块、指令与控制流，确保终结 ret。
可选：将生成的 IR 传入 PassManager.runAll(...) 进行一轮或多轮优化。
输出：将最终 IR 写入 llvm_ir.txt（并可同时输出模块级别声明文件）。

关键生成接口（示例）：

String genCompUnit(Unit root)：生成整个模块的 IR 文本。
String genFuncDef(Unit funcNode, FunctionContext ctx)：在给定上下文中生成函数体。
Value genExp(Unit expNode, FunctionContext ctx)：生成表达式并返回 Value 抽象（立即数/寄存器/全局）。
Addr genLVal(Unit lvalNode, FunctionContext ctx)：返回可以被 load/store 操作使用的地址表达式。

实现细节与注意点：

寄存器与标签命名使用 FunctionContext.nextReg() / nextLabel() 保证在一个函数内唯一，并在模块级通过函数名前缀避免冲突。
对于 printf/格式化输出，采用两阶段生成：先按左到右顺序评估所有实参并保存临时寄存器，然后按格式串生成 putstr/putint 调用，保证有副作用的表达式按语言语义执行顺序。
对数组、getelementptr 的生成要保留一致的格式（例如 getelementptr [N x i32], [N x i32]* @arr, i32 0, i32 %idx），便于后续 pass 的正则匹配与模式识别。
在生成 alloca/load/store 时保留标准缩进与行分割，优化 pass 依赖这些约定进行文本级分析（本项目中的多数学流变换基于文本匹配实现）。

局部 const 求值实现说明：

在函数生成阶段，LLVMGenerator 会维护一个 CURRENT_FUNCTION（类型为 FunctionContext）用于标记正在处理的函数；当进入函数生成时设置该变量，离开时清除。
当遇到局部 const 定义（genConstDef）时，生成器会把常量值（标量或数组）写入 ModuleBuilder 的常量映射，并以 funcName::varName 作为键；同时仍会在函数上下文中为变量分配 alloca 并存储初始值。
常量求值函数 evalConst 在解析到 LVal（PrimaryExp -> LVal）时会：
1. 若存在 CURRENT_FUNCTION，先以 funcName::name 的键查找 ModuleBuilder 的局部常量缓存；
2. 若未命中，再查找模块级的全局常量缓存（constInts / constArrays）；
3. 若均未命中或索引越界，则返回空或按防御策略返回 0。
该实现可让局部 const 与全局 const 在常量表达式求值中正确区分并优先使用局部定义，修复了先前只能读取模块级常量的问题。

示例（函数片段）：

define i32 @add_one(i32 %x) {
entry:
  %r = add i32 %x, 1
  ret i32 %r
}

可扩展点：

如果将来迁移到更结构化的 IR（AST/IR 对象图），LLVMGenerator 的 gen* 接口可直接输出中间数据结构，再由一个独立的后端序列化为文本；当前实现优先保证可调试性与 pass 的可工作性。

6.3 关键技术点

6.3.1 变量与数组处理

全局变量：
1
@globalVar = dso_local global i32 0
全局数组：
1
@arr = dso_local global [10 x i32] zeroinitializer
初始化值存储在 constArraysInit，生成时展开

局部变量：

1 2	%1 = alloca i32 store i32 %initVal, i32* %1

局部数组：
1
%1 = alloca [10 x i32]
通过 getelementptr 计算元素地址

static 变量处理：

语义分析阶段：标记为 StaticInt / StaticIntArray，登记在函数作用域符号表中
IR 生成阶段：提升为全局变量，生命周期跨函数调用
命名策略：使用函数名前缀避免冲突，如 @func_staticVar
可见性：仅在声明函数内可访问（通过符号表查询控制）
初始化：
- 全局声明时初始化（与普通全局变量相同）
- 初始化表达式在首次执行时计算（需要运行时初始化则使用构造函数或入口块）

示例：

void func() {
    static int counter = 0;
    counter++;
    putint(counter);
}

生成的 IR：

@func_counter = dso_local global i32 0

define void @func() {
entry:
  %1 = load i32, i32* @func_counter
  %2 = add i32 %1, 1
  store i32 %2, i32* @func_counter
  call void @putint(i32 %2)
  ret void
}

优势：
- 保证变量值在函数调用间保持（持久化状态）
- 避免栈上分配，减少栈帧大小
- 符合 C 语言 static 变量语义

数组元素访问：

1 2	%addr = getelementptr [10 x i32], [10 x i32]* %arr, i32 0, i32 %index %val = load i32, i32* %addr

6.3.2 控制流处理

if-else 语句：

br i1 %cond, label %then, label %else
then:
  ...
  br label %end
else:
  ...
  br label %end
end:

for 循环：

br label %cond
cond:
  %c = ...
  br i1 %c, label %body, label %end
body:
  ...
  br label %step
step:
  ...
  br label %cond
end:

短路求值（&& / ||）：

实现策略：基于条件分支的惰性求值，避免不必要的计算
&& 短路逻辑：
1. 计算左操作数，结果存入 %left
2. 创建三个基本块：evalRight（计算右操作数）、shortCircuit（短路跳过）、end（合并结果）
3. 若 %left 为 false，直接跳转到 end，结果为 0（false）
4. 若 %left 为 true，跳转到 evalRight 计算右操作数
5. 使用 phi 节点在 end 块合并两条路径的结果
|| 短路逻辑：
1. 计算左操作数，结果存入 %left
2. 若 %left 为 true，直接跳转到 end，结果为 1（true）
3. 若 %left 为 false，计算右操作数
4. 使用 phi 节点合并结果

示例（a && b）：

%left = <evaluate a>
%cond = icmp ne i32 %left, 0
br i1 %cond, label %evalRight, label %end
evalRight:
  %right = <evaluate b>
  %rcond = icmp ne i32 %right, 0
  br label %end
end:
  %result = phi i1 [0, %entry], [%rcond, %evalRight]
  %final = zext i1 %result to i32

优势：
- 避免无效计算：当 a && b 中 a 为 false 时，不计算 b
- 支持副作用控制：如 p != NULL && *p == 0，防止空指针解引用
- 符合 C 语言语义标准

6.3.3 函数调用

参数传递：
- 标量参数：直接传值（i32 %val）
- 数组参数：传递指针（i32* %arr）
- 数组首地址通过 getelementptr 提取

返回值处理：

1	%ret = call i32 @func(i32 %arg1, i32* %arg2)

内建函数：
- getint()：读取整数
- putint(i32)：输出整数
- putch(i32)：输出字符
- putstr(i8*)：输出字符串

6.3.4 printf 转换

将 printf 转换为 putint、putch、putstr 的组合：

解析格式串：提取 %d 占位符位置
分段输出：普通字符串与整数值交替输出

参数求值顺序处理：

问题：C 语言中函数参数的求值顺序是未定义的（unspecified），但 SysY 要求从左到右求值
解决方案：在生成 putint 调用前，预先按顺序计算所有实参表达式，将结果存入临时寄存器
具体实现：
1. 第一遍遍历：按顺序计算所有实参表达式（包括可能包含函数调用的复杂表达式），存储到 ArrayList<Value> evaluatedArgs
2. 第二遍遍历：按格式串解析结果，依次生成 putstr 和 putint 调用，使用预先计算好的参数值
3. 确保即使实参中包含有副作用的函数调用（如 getint()），也能保证从左到右的求值顺序

示例说明：

1 2	// 源代码 printf("%d %d\n", getint(), getint());

生成的 IR（简化）：

; 第一步：按顺序求值所有实参
%arg1 = call i32 @getint()    ; 第一个实参先求值
%arg2 = call i32 @getint()    ; 第二个实参后求值

; 第二步：按格式串输出
call void @putint(i32 %arg1)  ; 输出第一个整数
call void @putch(i32 32)      ; 输出空格
call void @putint(i32 %arg2)  ; 输出第二个整数
call void @putch(i32 10)      ; 输出换行

关键点：
- 避免了参数求值顺序不确定导致的输出错误
- 支持实参表达式中包含函数调用、数组访问等复杂操作
- 保证与 SysY 语义一致

完整示例：

1	printf("x=%d, y=%d\n", x, y);

转换为：

call void @putstr(i8* getelementptr([3 x i8], [3 x i8]* @.str.0, i32 0, i32 0))  ; "x="
call void @putint(i32 %x)
call void @putstr(i8* getelementptr([4 x i8], [4 x i8]* @.str.1, i32 0, i32 0))  ; ", y="
call void @putint(i32 %y)
call void @putch(i32 10)  ; '\n'

6.4 类型系统与值表示

Value 抽象

IMMEDIATE：立即数（如 42）
REGISTER：虚拟寄存器（如 %1）
GLOBAL：全局变量（如 @arr）

Addr 抽象

封装变量地址（寄存器或全局符号）
支持 load / store 操作

LocalVar

变量名、地址、类型、数组维度
数组大小信息（用于 getelementptr 计算）

6.5 设计亮点

亮点	价值
SSA 形式	简化数据流分析，便于后续优化
作用域深度追踪	支持变量遮蔽与生命周期管理
字符串常量池	避免重复字符串，减少代码体积
短路求值优化	减少不必要的计算，提升运行效率
printf 智能转换	将格式化输出转换为高效的运行时库调用
可插拔优化框架	支持灵活添加各类优化 pass
统一的值抽象（Value）	简化表达式生成逻辑，支持立即数与寄存器统一处理

6.6 优化框架设计

本项目的中端优化采用可插拔的 pass 框架，源码位于 src/midend/opt。核心部件包括：

OptimizationPass.java：优化 pass 的接口契约。每个 pass 至少应实现 String run(String ir)（对整个模块文本 IR 做变换并返回新 IR），并可使用 normalizeIndent(String) 做行级缩进规范化。
PassManager.java：负责按 OptimizationOptions 中的开关构建 pass 列表，并按序执行（runAll(String ir)）。在执行前以及所有 pass 执行完后各调用一次 PassManager.normalizeIr(String) 做统一预处理（即只在开始和结束各调用一次，而不是在每个 pass 之后）：移除行内注释（保留字符串常量内的分号）、合并多余空行，并统一基本块标签与指令缩进，以避免注释或格式差异干扰基于行/正则的匹配。
OptimizationOptions.java：开关配置（例如 enableMem2Reg, enableInstSimplify, enableConstProp, enableStrengthReduction, enableGVN, enableLoopUnrolling, enableFunctionInlining, enableDCE, enableCFGSimplify, enableTailCallOptimization 等），用于在 PassManager 构建时决定哪些 pass 被注入以及是否重复插入第二轮。
若要运行并验证效果，请使用测试驱动 src/midend/opt/OptimizationTest.java，它包含若干最小复现用例和 testCombined() 用于做多轮/组合优化验证并打印每步差异。最近新增了针对 InstSimplifyPass 中 icmp/zext 链折叠的单元用例，以及针对 PassManager.normalizeIr 的格式化/注释移除验证用例。

主要设计原则

文本友好与可观测：当前 pass 以“文本 + 行级正则/模式”方式实现，便于调试与快速迭代，但对 IR 格式（缩进、空行、注释）敏感。因此约定使用 PassManager.normalizeIr（集中处理行内注释、空行与缩进）与 OptimizationPass.normalizeIndent 做简单规范化。
可插拔与配置化：通过 OptimizationOptions 控制每个 pass 的启用，PassManager 按顺序将所选 pass 串联在一起；新增或删除 pass 只需实现/移除对应的 OptimizationPass 实现并更新 PassManager 注册或测试中的局部注册点。
多轮与收敛：部分 pass（如常量传播、指令简化、强度削减、GVN）可能需要多轮交替运行才能收敛。PassManager 已在构造器中为这些 pass 预置了两轮运行的位置（第一轮与第二轮），但也支持在测试/工具中按需做“迭代直到不变点”的策略。

推荐的默认执行顺序（实现中顺序）

Pass 的实际注入顺序由 PassManager(OptimizationOptions) 构建，当前实现的经验顺序如下（亦见 PassManager 源码）：

SSA 可选转换（SSATransformPass，llvm默认已经是SSA的，置空）
Mem2RegPass（内存到寄存器提升，插入 phi 节点）
PhiEliminationPass（Phi 删除，基于内存展开 phi 节点）
FunctionInliningPass（函数内联）
InstSimplifyPass（指令级简化、常量折叠、代数规则）
ConstantPropagationPass（常量传播）
StrengthReductionPass（强度削减，乘除→移位等）
GVNPass（全局值编号，公共子表达式消除）
LoopUnrollingPass（循环展开）
第二轮 InstSimplify / ConstantPropagation / StrengthReduction / GVN（收敛清理）
DeadCodeEliminationPass（删除不可达/无用指令）
CFGSimplifyPass（控制流简化：常量分支折叠、死块删除）
TailCallOptimizationPass（尾调用/尾递归转换）
最终 DeadCodeEliminationPass（再次清理）

各 Pass 简短说明（与源码一一对应）

SSATransformPass：可选的 SSA 重写（项目内前端已做部分 SSA，运行此 pass 为可选）。
Mem2RegPass：识别可提升的 alloca 并把栈上变量提升为寄存器（使用 phi 合并），以便减少 load/store 干扰。
PhiEliminationPass：单独实现的 Phi 删除 Pass。该 Pass 将 SSA 中的 phi 节点通过基于内存的方式展开为普通指令序列，便于后续基于文本的优化（如 InstSimplify、GVN 等）更可靠地识别和处理值流。
FunctionInliningPass：内联小函数（含递归检测、寄存器重命名与阈值），内联会产生更多的常量/局部化机会，需紧随清理 pass。内联实现已改进以不输出以 ; 开头的行内注释，从而避免把调试注释混入最终 IR。
InstSimplifyPass：做局部指令简化与常量折叠（例如消除无意义的 zext、把 add 0/eliminate、常量表达式直接折叠成立即数）。近期增强：识别并折叠连续的 zext/icmp 链（例如 zext i1 -> i32 后接 icmp eq/ne i32, 0），将分支条件恢复为原始 i1 并在必要时交换分支目标，从而显著简化常见的逻辑序列。
ConstantPropagationPass：跨指令传播常量并替换寄存器为常量立即数，常与 GVN/InstSimplify 联合提升效果。
StrengthReductionPass：将高成本算术（乘法/除法）转换为低成本等价（移位/加法）当满足模式时。
GVNPass：全局值编号以检测并消除基本块间的公共子表达式，复用先前计算的值。
LoopUnrollingPass：对小循环做完全或部分展开以提高后续优化与并行机会，同时受展开阈值控制以避免代码爆炸。
DeadCodeEliminationPass：删除无用指令与不可达代码，是收敛流程中频繁使用的清理工具。近期改进：在删除死赋值前，先在函数内部执行基于标签可达性分析的不可达基本块删除（removing unreachable blocks），从而能移除包含 unreachable 或从入口不可达的整块代码及其内部不再被引用的定义。
CFGSimplifyPass：基于分支常量化和基本块可达性分析做控制流层面的简化。近期增强：对无显式标签的函数，也会在必要时插入保守的 unreachable 终结指令，保证每个函数在语法层面具有终结器。
TailCallOptimizationPass：将尾递归或可转化的尾调用改写为循环形式以节省栈深度。

7. 目标代码生成设计

7.1 总体架构

目标代码生成阶段将优化后的LLVM IR转换为MIPS汇编代码。主要组件：

MIPSGenerator.java：主生成器，负责解析IR并生成MIPS指令
MIPSContext.java：上下文管理器，维护寄存器分配、栈偏移、符号映射等状态

7.2 自定义栈帧布局

栈帧结构

本项目采用帧指针（$fp）为基准的栈帧布局，兼容MARS模拟器的调用约定：

高地址
+----------------+
| 第n个参数      | +4*(n-1)($fp)  ; 第5个及以上参数（如果有）
| ...            |
| 第5个参数      | +16($fp)
| 第4个参数      | +12($fp)
| 第3个参数      | +8($fp)
| 第2个参数      | +4($fp)
| 第1个参数      | +0($fp)         ; 参数1-4也会备份到栈上
+----------------+ <- $fp (新) = $sp (旧)
| $ra            | -4($fp)         ; 返回地址
| $fp (旧)       | -8($fp)         ; 调用者的帧指针
+----------------+
| $t0 (临时0)    | -12($fp)        ; 临时寄存器保存区开始
| $t1 (临时1)    | -16($fp)
| ...            |
| $t19 (临时19)  | -12-19*4($fp)   ; 共20个临时寄存器（$8-$27）
+----------------+
| alloca变量1    | -92($fp)        ; 局部变量区（动态分配）
| alloca变量2    |
| alloca数组     |
| phi临时变量    |
| spill槽        |
+----------------+ <- $sp (新，低地址）
低地址

设计要点

参数传递：
- 前4个参数通过$a0-$a3传递
- 第5个及以上参数通过栈传递，位于$fp正偏移
- 即使参数在寄存器传递，函数入口也会将其备份到栈上（+0($fp)到+12($fp)）
临时寄存器区：
- 固定预留20个字（80字节）用于保存$t0-$t19（即MIPS的$8-$27）
- 函数调用前保存，返回后恢复
- 仅保存已使用的临时寄存器（通过usedTempRegs跟踪）
局部变量区：
- 所有alloca指令分配的变量/数组
- Phi消除后产生的%phi_slot*变量
- 动态计算栈空间大小，避免重叠

栈帧大小计算

栈帧大小由以下部分组成，在函数解析前通过两遍扫描精确计算：

第一遍：活跃变量峰值分析

// 扫描函数体，记录每个变量的定义位置和最后使用位置
Map<String, Integer> lastUse = new HashMap<>();
Map<String, Integer> defIndex = new HashMap<>();

// 计算每一时刻的活跃变量数量
int peakLive = 0;
for (int idx = 0; idx < totalLines; idx++) {
    int liveCount = 0;
    for (String var : defIndex.keySet()) {
        if (defIndex.get(var) <= idx && lastUse.get(var) >= idx) {
            liveCount++;
        }
    }
    peakLive = Math.max(peakLive, liveCount);
}

// 为活跃变量峰值预留 Spill 槽
funcInfo.tempSpillCount = Math.max(funcInfo.tempSpillCount, peakLive);

第二遍：统计栈使用情况

// 统计各类资源使用
while (scanning function body) {
    if (line.contains("alloca")) {
        // 记录局部变量/数组大小
        int size = extractArraySize(line);
        funcInfo.allocas.put(varName, size);
    }
    if (line.contains("call")) {
        // 记录最大参数数量（用于调用栈预留）
        funcInfo.hasCall = true;
        funcInfo.maxArgs = Math.max(funcInfo.maxArgs, argCount);
    }
    // 标记实际使用的变量（未使用的不分配空间）
    if (line references allocaVar) {
        funcInfo.usedAllocas.add(allocaVar);
    }
}

最终大小计算

private void calculateStackSize(FunctionInfo funcInfo) {
    // 1. 基础空间：$ra + $fp
    int baseSize = 8;

    // 2. 临时寄存器保存区：20个寄存器 × 4字节
    int tempregSize = 20 * 4;  // 80字节

    // 3. Spill 槽：活跃变量峰值 + 安全余量
    final int SPILL_SAFETY_MARGIN = 40;
    int spillSize = (funcInfo.tempSpillCount + SPILL_SAFETY_MARGIN) * 4;

    // 4. 局部变量区：仅统计实际使用的 alloca
    int usedAllocaSize = 0;
    for (Map.Entry<String, Integer> e : funcInfo.allocas.entrySet()) {
        if (funcInfo.usedAllocas.contains(e.getKey())) {
            usedAllocaSize += e.getValue();
        }
    }

    // 5. 调用参数预留区：支持嵌套调用
    int maxArgs = funcInfo.maxArgs * 4;

    // 6. 总大小（16字节对齐）
    int totalSize = baseSize + tempregSize + spillSize + usedAllocaSize + maxArgs;
    totalSize = ((totalSize + 15) / 16) * 16;

    funcInfo.stackSize = totalSize;
}

示例计算

假设函数 foo(a, b, c) 有：

2个局部变量（8字节）
1个数组 [10 x i32]（40字节）
活跃变量峰值 5 个
调用其他函数传递 3 个参数

栈帧大小 = 
    8 (RA/FP) +
    80 (临时寄存器区) +
    (5 + 40) * 4 = 180 (Spill槽) +
    48 (局部变量) +
    12 (调用参数区) 
    = 328 字节
    
对齐到16字节 = 336 字节

优化亮点：

按需分配：未使用的 alloca 变量不占用栈空间。
精确预估：通过活跃变量分析避免过度预留 Spill 槽。
安全余量：预留 40 字节防止优化导致的低估。

7.3 寄存器分配与管理策略

本项目实现了基于引用计数的寄存器分配与Lazy Spill（延迟溢出）策略，并引入了 Dirty Bit（脏位）机制、Store-to-Load Forwarding等优化，旨在最大化寄存器利用率并减少内存访问。寄存器分配的核心流程由以下几个关键函数协同完成。

7.3.1 寄存器资源概览

可用寄存器池：

临时寄存器：$8-$27（20个），用于变量与临时计算
参数寄存器：$a0-$a3（仅用于参数传递）
返回值寄存器：$v0（仅用于返回值）
上下文维护：双向映射 varToReg / regToVar，引用计数表 refCountMap

7.3.2 底层寄存器分配：`nextTempReg()`

职责：从寄存器池中选择一个物理寄存器，基于引用计数策略优先选择”最不活跃”的寄存器。

实现逻辑：

// MIPSContext.nextTempReg()
public int nextTempReg() {
    // 策略1：优先选择完全空闲的寄存器（未使用 + 未映射）
    for (int i = 0; i < TEMP_REG_NUM; i++) {
        int cand = TEMP_REG_BEGIN + i;
        String regName = "$" + cand;
        if (!usedTempRegs.contains(cand) && !regToVar.containsKey(regName)) {
            usedTempRegs.add(cand);
            return cand;
        }
    }
    
    // 策略2：选择引用计数最小的寄存器（优先淘汰"不活跃"变量）
    int bestReg = -1;
    int minRefCount = Integer.MAX_VALUE;
    for (int i = 0; i < TEMP_REG_NUM; i++) {
        int cand = TEMP_REG_BEGIN + i;
        String regName = "$" + cand;
        String var = regToVar.get(regName);
        if (var != null) {
            int refCount = refCountMap.getOrDefault(var, 0);
            if (refCount < minRefCount) {
                minRefCount = refCount;
                bestReg = cand;
            }
        }
    }
    
    // 策略3：轮询分配（兜底）
    return bestReg != -1 ? bestReg : TEMP_REG_BEGIN + (tempRegCounter++ % TEMP_REG_NUM);
}

关键点：

引用计数驱动：优先淘汰 refCount == 0 的变量（已无后续使用）
避免频繁 Spill：通过统计活跃度，减少热点变量被驱逐的概率
引用计数更新：每次 loadOperand 使用变量时递减计数（见 7.3.5）

7.3.3 临时寄存器获取：`getTempRegister()`

职责：在需要临时寄存器时调用，处理旧变量的 Spill（如果需要）并返回可用寄存器。

实现逻辑：

// MIPSGenerator.getTempRegister()
private String getTempRegister() {
    int regNum = context.nextTempReg();  // 调用底层分配
    String reg = "$" + regNum;

    // 如果该寄存器已映射到某个变量，需要先保护旧变量
    String oldVar = context.getVarForReg(reg);
    if (oldVar != null) {
        // Dirty Bit 检查：仅 Spill 脏变量
        if (dirtyVars.contains(oldVar)) {
            Integer off = context.getStackOffset(oldVar);
            if (off == null) {
                int size = context.getVarSize(oldVar) != null ? context.getVarSize(oldVar) : 4;
                off = context.allocateStack(oldVar, size);
            }
            generateSw(reg, String.valueOf(off), "$fp");
            dirtyVars.remove(oldVar);  // Spill 后变 Clean
        }
        context.clearRegisterMapping(reg);  // 解除旧映射
    }
    
    // Store-to-Load Forwarding：清除该寄存器的 forwarding 信息
    invalidateForwardingForReg(reg);
    
    return reg;
}

关键点：

Lazy Spill：仅在寄存器需要复用时 Spill，而非每次指令后
Dirty Bit 优化：Clean 变量直接丢弃，减少 95% 的不必要 sw
Forwarding 失效：防止使用过期的 Store-to-Load 缓存

7.3.4 变量寄存器分配：`allocateRegister(varName)`

职责：为新生成的变量（如计算结果）分配寄存器，并建立映射关系。

实现逻辑：

// MIPSGenerator.allocateRegister()
private String allocateRegister(String varName) {
    // 复用检查：如果变量已有寄存器，直接返回
    String reg = context.getRegister(varName);
    if (reg != null) {
        return reg;
    }

    // 获取新寄存器（可能触发 Spill）
    reg = getTempRegister();
    
    // 建立映射
    context.setRegister(varName, reg);
    
    // Dirty Bit：新分配的变量标记为 Dirty（计算结果尚未写入栈）
    dirtyVars.add(varName);
    
    // Store-to-Load Forwarding：清除该寄存器的 forwarding 信息
    invalidateForwardingForReg(reg);
    
    return reg;
}

关键点：

自动 Dirty 标记：新计算的结果默认为 Dirty，确保后续会被 Spill
映射管理：通过 context.setRegister 更新双向映射表
防止 Forwarding 错误：新变量分配后，该寄存器的旧 forwarding 信息失效

7.3.5 操作数加载：`loadOperand(operand)`

职责：将操作数（常量、变量、全局符号）加载到寄存器，是寄存器分配的”消费端”。

实现逻辑：

// MIPSGenerator.loadOperand()
private String loadOperand(String operand) {
    // 情况1：常量立即数
    if (operand.matches("-?\\d+")) {
        String reg = getTempRegister();
        mipsCode.append("    li ").append(reg).append(", ").append(operand).append("\n");
        return reg;
    }
    
    // 情况2：变量（去除 % 前缀）
    String varName = operand.startsWith("%") ? operand.substring(1) : operand;
    
    // 2.1 寄存器复用：变量已在寄存器中
    String existingReg = context.getRegister(varName);
    if (existingReg != null) {
        // 引用计数递减（该变量被使用一次）
        Integer refCount = refCountMap.get(varName);
        if (refCount != null && refCount > 0) {
            refCountMap.put(varName, refCount - 1);
        }
        return existingReg;  // 直接复用
    }
    
    // 2.2 从栈加载：变量在栈上
    Integer offset = context.getStackOffset(varName);
    if (offset != null) {
        String reg = getTempRegister();
        
        // getelementptr 特殊处理：区分"地址"和"值"
        if (context.getPointerOrigin(varName) != null) {
            // 栈上存的是地址，先加载地址再从地址加载值
            String addrReg = getTempRegister();
            generateLw(addrReg, String.valueOf(offset), "$fp");
            generateLw(reg, "0", addrReg);
        } else {
            // 栈上存的是值，直接加载
            generateLw(reg, String.valueOf(offset), "$fp");
        }
        
        // 从栈加载的变量是 Clean 的（栈上已有副本）
        // 不加入 dirtyVars
        
        // 引用计数递减
        Integer refCount = refCountMap.get(varName);
        if (refCount != null && refCount > 0) {
            refCountMap.put(varName, refCount - 1);
        }
        
        return reg;
    }
    
    // 情况3：全局变量
    if (context.isGlobalVar(varName)) {
        String baseReg = getTempRegister();
        String reg = getTempRegister();
        mipsCode.append("    la ").append(baseReg).append(", ").append(varName).append("\n");
        generateLw(reg, "0", baseReg);
        return reg;
    }
    
    // 兜底：返回零寄存器
    return "$zero";
}

关键点：

寄存器复用：优先返回已分配的寄存器，避免重复加载
引用计数递减：每次使用后递减，为后续 nextTempReg() 提供淘汰依据
Clean 标记：从栈加载的变量不标记为 Dirty（栈上已有副本）
getelementptr 语义修正：区分”地址”和”值”，防止输出地址而非元素值

7.3.6 寄存器 Spill 策略：`spillAllRegisters()`

职责：在基本块边界或函数调用前，将所有活跃的 Dirty 变量写回栈。

实现逻辑：

// MIPSGenerator.spillAllRegisters()
private void spillAllRegisters() {
    // 收集需要 Spill 的变量信息
    List<SpillInfo> toSpill = new ArrayList<>();
    List<Integer> regs = context.getNeedSaveTempRegsList();
    
    for (Integer regNum : regs) {
        String reg = "$" + regNum;
        String var = context.getVarForReg(reg);
        if (var != null && dirtyVars.contains(var)) {  // 仅 Spill Dirty 变量
            Integer off = context.getStackOffset(var);
            if (off == null) {
                int size = context.getVarSize(var) != null ? context.getVarSize(var) : 4;
                off = context.allocateStack(var, size);
            }
            toSpill.add(new SpillInfo(reg, var, off));
        }
    }
    
    // 按栈偏移排序，利用缓存局部性
    toSpill.sort((a, b) -> Integer.compare(a.offset, b.offset));
    
    // 批量生成 Spill 指令
    for (SpillInfo info : toSpill) {
        generateSw(info.reg, String.valueOf(info.offset), "$fp");
        dirtyVars.remove(info.var);  // Spill 后变 Clean
    }
}

优化效果：

Dirty Bit 过滤：仅保存修改过的变量，减少 95% 的无效 sw
批量排序：按内存地址顺序写入，提升缓存命中率

7.3.7 基本块边界处理

触发时机：

进入新基本块（标签 label:）
分支跳转前（br / j）
函数调用前（call）

处理流程：

// 进入新基本块
if (line.endsWith(":")) {
    spillAllRegisters();               // 保存所有 Dirty 变量
    clearForwardingInfo();             // 清除 Store-to-Load 缓存
    mipsCode.append(label).append(":\n");
    context.clearAllRegisterMappings(); // 清除寄存器映射
    context.resetTempRegs();           // 重置临时寄存器标记
}

// 分支跳转前
spillAllRegisters();
clearForwardingInfo();
mipsCode.append("    j ").append(targetLabel).append("\n");

原因：

新基本块可能有多个前驱，寄存器状态不确定
必须通过栈传递变量值，确保语义正确
Forwarding 缓存仅在单个基本块内有效

7.3.8 避开指定寄存器的分配：`getTempRegisterAvoid(avoidReg)`

场景：同一指令的两个操作数如果落在同一物理寄存器会相互覆盖，需要拿到一个“不是 avoidReg” 的寄存器。常见于交换/比较指令左、右操作数冲突时的兜底分配。

实现要点：

尝试两次 nextTempReg()，遇到与 avoidReg 相同则跳过；否则按常规流程复用/Spill 脏变量、清 forwarding。
如两次都撞上或没有更优选择，退回 getTempRegister()，极端情况下允许返回 avoidReg 以保证可用性。
Spill 时同样仅对脏变量落栈，并在复用后清除寄存器映射与 forwarding 信息，保持 Lazy Spill 语义。

7.3.9 强制重新加载操作数：`reloadOperandFresh(operand, avoidReg)`

目的：当两个不同操作数被分配到同一寄存器（例如共用一条寄存器映射或立即数装载到冲突寄存器）时，强制把 operand 重新装入一个避开 avoidReg 的新寄存器，消除覆盖风险。

处理分支：

立即数：直接用 getTempRegisterAvoid 拿新寄存器，li 装载。
%var：优先从栈偏移重新加载；若有寄存器映射则复制一份；全局符号回退为 la，否则默认 li 0 兜底。重新加载后会通过 context.setRegister 更新映射，使后续使用指向最新副本。
@global：la 到新寄存器即可。

关键收益：

保证二元指令左右操作数的寄存器互不覆盖，避免 sw/add 等写回破坏另一操作数。
与 getTempRegisterAvoid 协同工作，在保持 Lazy Spill 的同时，为冲突场景提供低侵入的安全修正。

7.4 内存分配与访问

7.4.1 变量访问模式

全局变量访问：

1
2
3

la $t0, global_var    # 加载地址
lw $t1, 0($t0)        # 读取值
sw $t2, 0($t0)        # 存储值

局部变量访问：

1 2	lw $t0, -100($fp) # 从栈加载 sw $t1, -100($fp) # 存储到栈

数组元素访问：

# 全局数组：array[i]
la $t0, array              # 数组基址
sll $t1, $i_reg, 2         # 索引 * 4
addu $t2, $t0, $t1         # 计算元素地址
lw $t3, 0($t2)             # 加载元素

# 局部数组：local_array[const_idx]（常量索引优化）
addiu $t0, $fp, -200       # 基址 = $fp + offset + idx*4（直接计算）
lw $t1, 0($t0)             # 加载元素

7.4.2 getelementptr 处理优化

情况1：全局数组常量索引

// 优化前（3条指令）：
la $t0, array
sll $t1, $idx, 2
addu $t2, $t0, $t1

// 优化后（2条指令）：
la $t0, array
addiu $t0, $t0, 16     // offset = idx * 4 直接计算

情况2：局部数组常量索引

// 优化前（4条指令）：
addiu $t0, $fp, -200   // 数组基址
sll $t1, $idx, 2
addu $t2, $t0, $t1

// 优化后（1条指令）：
addiu $t0, $fp, -184   // 直接计算 -200 + idx*4

情况3：指针参数传递修正

问题：getelementptr 结果是地址，但 processLoad / processStore 需要区分”地址”和”值”。

解决方案：

// processLoad 中检查 pointerOrigin
String ptrReg = context.getRegister(varName);
if (ptrReg != null) {
    // 寄存器存的是地址，从地址加载值
    generateLw(resultReg, "0", ptrReg);
} else {
    Integer offset = context.getStackOffset(varName);
    if (context.getPointerOrigin(varName) != null) {
        // 栈上存的是地址，先加载地址再从地址加载值
        String addrReg = getTempRegister();
        generateLw(addrReg, String.valueOf(offset), "$fp");
        generateLw(resultReg, "0", addrReg);
    } else {
        // 栈上存的是值，直接加载
        generateLw(resultReg, String.valueOf(offset), "$fp");
    }
}

7.5 计算指令处理

7.5 函数调用处理：`processCall()` 详解

函数调用是寄存器分配中最复杂的场景，涉及参数传递、寄存器保护、调用约定等多个环节。

7.5.1 `processCall()` 完整流程

输入：LLVM IR 指令 %result = call i32 @func(i32 %a, i32 %b, ...)

处理流程：

1. 解析调用信息
   ├─ 提取函数名、参数列表、返回类型
   └─ 判断是否为 IO 函数（getint/putint/putch/putstr）

2. IO 函数特殊处理
   ├─ putint: 加载参数到 $a0，syscall 1
   ├─ putch: 加载参数到 $a0，syscall 11
   ├─ getint: syscall 5，返回值在 $v0
   └─ putstr: 加载字符串地址到 $a0，syscall 4

3. 用户函数调用
   ├─ 阶段1：寄存器保护
   │   └─ spillAllRegisters()  // Dirty Bit + Lazy Spill
   │
   ├─ 阶段2：参数传递
   │   ├─ 前4个参数 → $a0-$a3（寄存器传递）
   │   └─ 剩余参数 → 栈传递（$sp + offset）
   │
   ├─ 阶段3：执行调用
   │   └─ jal func  // 跳转并保存返回地址到 $ra
   │
   └─ 阶段4：返回值处理
       ├─ $v0 → allocateRegister(result)  // 返回值存入结果寄存器
       └─ 标记为 Dirty（结果需要后续 Spill）

4. Forwarding 缓存清除
   └─ clearForwardingInfo()  // 函数调用后清除所有 Store-to-Load 缓存

7.5.2 参数传递详解

参数传递约定（MIPS O32 calling convention）：

前4个参数：通过 $a0-$a3 传递
第5+个参数：通过栈传递（相对 $sp 的正偏移）

实现代码：

// 解析参数列表
List<String> params = parseParams(paramsStr);

// 参数传递
for (int i = 0; i < params.size(); i++) {
    String param = params.get(i);
    
    if (i < 4) {
        // 前4个参数 → $a0-$a3
        String argReg = "$a" + i;
        String srcReg = loadOperand(param);  // 加载参数值到临时寄存器
        if (!srcReg.equals(argReg)) {
            mipsCode.append("    move ").append(argReg).append(", ")
                .append(srcReg).append("\n");
        }
    } else {
        // 第5+个参数 → 栈
        String srcReg = loadOperand(param);
        int offset = (i - 4) * 4;  // 栈上参数偏移
        generateSw(srcReg, String.valueOf(offset), "$sp");
    }
}

特殊情况：指针参数修正

如果参数是 getelementptr 的结果（地址），需传递地址而非值：

if (context.getPointerOrigin(param) != null) {
    // 参数是地址，从栈中加载地址（而非从地址加载值）
    Integer off = context.getStackOffset(param);
    if (off != null) {
        generateLw(srcReg, String.valueOf(off), "$fp");  // 直接加载地址
    }
}

7.5.3 寄存器保护策略

保护时机：在参数传递前调用 spillAllRegisters()。

保护对象：

仅保护 Dirty 变量（Dirty Bit 过滤）
Clean 变量（从栈加载且未修改）直接丢弃
减少 95% 的不必要 sw 指令

实现：

// 函数调用前保存寄存器
spillAllRegisters();

// 清除寄存器映射（调用后寄存器状态不确定）
context.clearAllRegisterMappings();
context.resetTempRegs();

为何清除映射？

被调用函数可能修改 $8-$27 的值（临时寄存器）
调用返回后，寄存器内容不可信，必须从栈重新加载

7.5.4 IO 函数优化

IO 函数特征：

函数名：getint / putint / putch / putstr
无需保存寄存器（系统调用不破坏 $8-$27）
直接使用 MIPS syscall

实现：

if (funcName.equals("putint")) {
    // putint(x) → syscall 1
    String srcReg = loadOperand(params.get(0));
    if (!srcReg.equals("$a0")) {
        mipsCode.append("    move $a0, ").append(srcReg).append("\n");
    }
    mipsCode.append("    li $v0, 1\n");
    mipsCode.append("    syscall\n");
} else if (funcName.equals("getint")) {
    // getint() → syscall 5
    mipsCode.append("    li $v0, 5\n");
    mipsCode.append("    syscall\n");
    
    // 返回值处理
    if (result != null && !result.isEmpty()) {
        String resultReg = allocateRegister(result);
        if (!resultReg.equals("$v0")) {
            mipsCode.append("    move ").append(resultReg).append(", $v0\n");
        }
    }
} else if (funcName.equals("putstr")) {
    // putstr(str) → syscall 4
    String strName = params.get(0);
    mipsCode.append("    la $a0, ").append(strName).append("\n");
    mipsCode.append("    li $v0, 4\n");
    mipsCode.append("    syscall\n");
}

优化效果：

IO 函数无需 spillAllRegisters()，减少大量 sw 指令
直接使用 syscall，避免 jal 跳转开销

7.5.5 返回值处理

返回值约定：函数返回值存放在 $v0。

处理流程：

// 调用后获取返回值
if (result != null && !result.isEmpty()) {
    String resultReg = allocateRegister(result);  // 分配结果寄存器
    if (!resultReg.equals("$v0")) {
        mipsCode.append("    move ").append(resultReg).append(", $v0\n");
    }
    dirtyVars.add(result);  // 标记为 Dirty（结果尚未写回栈）
}

关键点：

allocateRegister(result) 可能复用寄存器（触发 Spill）
新结果自动标记为 Dirty，确保后续会写回栈

7.5.6 Forwarding 缓存清除

原因：函数调用可能修改内存（例如修改全局变量、数组），导致旧的 Store-to-Load 缓存失效。

实现：

1 2	// 调用后清除所有 forwarding 信息 clearForwardingInfo();

示例：

// 调用前
sw $8, 0($fp)       // 记录：0@$fp → $8
lw $9, 0($fp)       // 优化为：move $9, $8

// 如果中间有 call
call func           // func 可能修改栈
lw $9, 0($fp)       // 必须重新 lw（缓存失效）

7.6 跳转分支指令处理

7.6.1 基本块管理

进入新基本块时：

if (line.endsWith(":")) {
    spillAllRegisters();           // Spill 所有 Dirty 变量
    clearForwardingInfo();         // 清除 Store-to-Load 缓存
    mipsCode.append(label).append(":\n");
    context.clearAllRegisterMappings();  // 清除寄存器映射
    context.resetTempRegs();       // 重置临时寄存器标记
}

原因：新基本块可能有多个前驱，寄存器状态不确定，必须从栈重新加载。

7.6.2 条件分支

无条件跳转：

br label %target
=>
    spillAllRegisters()      # Spill 前保存活跃变量
    j target                 # 跳转

7.7 指令解析健壮性（避免命名碰撞）

问题场景：后端若用 line.contains("store") / line.contains("call") 这类子串匹配来分派指令，会在指令名或寄存器名包含关键字时误判，例如 @compute_and_store 被当作 store 指令，导致调用不生成 jal。

解决方案：统一使用 extractOpcode()：

1) 用正则剥离可选前缀 `%tmp = `，再取首个 token 作为 opcode。
2) 预扫描（栈大小估计）和正式分派都复用该函数，保证一致。

核心代码：

private String extractOpcode(String line) {
  String body = line.trim();
  Matcher m = Pattern.compile("^%[A-Za-z0-9_.]+\\s*=\\s*(.*)$").matcher(body);
  if (m.find()) {
    body = m.group(1).trim();
  }
  int sp = body.indexOf(' ');
  return sp == -1 ? body : body.substring(0, sp);
}

实践提示：凡是“识别是否为某指令”或“统计指令类型”的地方，都应依赖 opcode 而非字符串包含匹配。

条件跳转：

br i1 %cond, label %true, label %false
=>
    move $t0, %cond_reg      # 复制条件到独立寄存器
    spillAllRegisters()      # Spill 前保存活跃变量
    bnez $t0, true           # 非零跳转
    j false                  # 零跳转

关键点：

使用独立寄存器 $t0 保存条件，防止 spillAllRegisters 覆盖
分支前必须 Spill，确保目标块能正确加载变量

7.6.3 循环优化

for 循环结构：

for_cond:
    # 条件检查
    bnez $cond, for_body
    j for_end
for_body:
    # 循环体
    j for_post
for_post:
    # 后置语句（i++）
    j for_cond
for_end:

优化点：

循环变量尽量保持在寄存器中（减少 lw/sw）
for_post 块内的自增操作直接用 addiu

7.7 函数序言与尾声

7.7.1 函数序言（Prologue）

职责：初始化函数栈帧，保存调用上下文，准备参数访问。

func:
    # 1. 分配栈空间
    addiu $sp, $sp, -stackSize
    
    # 2. 保存 $ra 和 $fp（调用者上下文）
    sw $ra, (stackSize-4)($sp)
    sw $fp, (stackSize-8)($sp)
    
    # 3. 设置新的 $fp（栈帧基址）
    move $fp, $sp
    addiu $fp, $fp, stackSize
    
    # 4. 保存参数到栈（前4个参数通过 $a0-$a3 传递）
    sw $a0, 4($fp)       # 第1个参数
    sw $a1, 8($fp)       # 第2个参数
    sw $a2, 12($fp)      # 第3个参数
    sw $a3, 16($fp)      # 第4个参数

栈帧布局：

高地址
+----------------+
| 参数5+         | ← 调用者栈（如果参数 > 4）
+----------------+
| $a3 (参数4)    | $fp + 16
+----------------+
| $a2 (参数3)    | $fp + 12
+----------------+
| $a1 (参数2)    | $fp + 8
+----------------+
| $a0 (参数1)    | $fp + 4
+----------------+
| (栈帧起点)     | ← $fp
+----------------+
| $ra            | $fp - 4
+----------------+
| $fp (旧)       | $fp - 8
+----------------+
| 局部变量       | $fp - 12, $fp - 16, ...
+----------------+
| (栈帧终点)     | ← $sp
低地址

7.7.2 函数尾声（Epilogue）

职责：恢复调用者上下文，释放栈帧，返回调用点。

# 1. 恢复 $ra 和 $fp
lw $ra, -4($fp)
lw $fp, -8($fp)

# 2. 恢复栈指针
addiu $sp, $sp, stackSize

# 3. 返回
jr $ra

关键点：

$ra 保存返回地址，必须在 jr 前恢复
$fp 必须在 $sp 恢复前先恢复（因为 $fp 是栈帧基址）
栈帧大小在编译时确定（见 7.2 节）

7.8 设计亮点

7.8.1 核心优化策略

优化技术	实现方式	效果
Dirty Bit 机制	区分 Clean/Dirty 变量，Spill 时仅保存 Dirty	减少 95% 的函数调用寄存器保存
引用计数分配	优先分配引用计数小的寄存器，减少 Spill	减少 10-20% 的 Spill 操作
Store-to-Load Forwarding	`sw` 后立即 `lw` 改为 `move`	减少 5-10% 的 `lw` 指令
Copy Propagation	消除 `la`/`li` 后的冗余 `move`	减少 15-25% 的 `move` 指令
立即数指令	使用 `addiu`/`slti` 替代 `li` + `add`/`slt`	减少 15-20% 的 `li` 指令
常量索引优化	数组访问时直接计算偏移，避免 `sll`+`addu`	减少 30-40% 的数组访问指令
IO 函数快速路径	IO 函数跳过寄存器保存/恢复	减少 100% 的 IO 调用开销

7.8.2 内存访问优化

批量 Spill：

// 按栈偏移排序，利用缓存局部性
toSpill.sort((a, b) -> Integer.compare(a.offset, b.offset));
for (SpillInfo info : toSpill) {
    generateSw(info.reg, String.valueOf(info.offset), "$fp");
}

getelementptr 多级优化：

常量索引直接计算偏移（减少2-3条指令）
全局数组 la 直接到目标寄存器（减少1条 move）
指针参数区分”地址”和”值”（修复语义错误）

7.8.3 控制流优化

基本块边界优化：

仅在必要时 Spill（Lazy Spill）
清除 forwarding 缓存防止跨块错误
重置寄存器映射确保语义正确

条件分支优化：

独立寄存器保存条件，防止 Spill 覆盖
短路求值生成高效的跳转序列

编译-系列：

BUAA 2025 编译器设计说明

1. 总体目标

2. 目录结构与职责

3. 词法分析设计

3.1 处理流程

3.2 关键数据结构

3.3 正则与最小化判断

3.4 错误处理策略

3.5 设计亮点

4. 语法分析设计

4.1 方法论

4.2 文法（简化 BNF 摘要）

4.3 关键消除二义性/左递归策略

左结合树重构技巧

4.4 FIRST 集与可选/重复部分

4.5 错误检测与恢复

4.6 语法树输出策略

4.7 设计亮点总结

4.8 FIRST集列表

5. 语义分析设计

5.1 核心思路与职责

5.2 符号模型与条目类型

5.3 作用域类型与返回值约束

5.4 主要检查点（与触发位置）

5.5 符号表输出

5.6错误与日志

6. 中间代码生成设计

6.1 核心思路与架构

6.2 关键组件

6.2.1 ModuleBuilder（全局管理器）

6.2.2 FunctionContext（函数上下文）

6.2.3 LLVMGenerator（IR 生成核心）

6.3 关键技术点

6.3.1 变量与数组处理

6.3.2 控制流处理

6.3.3 函数调用

6.3.4 printf 转换

6.4 类型系统与值表示

Value 抽象

Addr 抽象

LocalVar

6.5 设计亮点

6.6 优化框架设计

7. 目标代码生成设计

7.1 总体架构

7.2 自定义栈帧布局

栈帧结构

设计要点

栈帧大小计算

第一遍：活跃变量峰值分析

第二遍：统计栈使用情况

最终大小计算

示例计算

7.3 寄存器分配与管理策略

7.3.1 寄存器资源概览

7.3.2 底层寄存器分配：nextTempReg()

7.3.3 临时寄存器获取：getTempRegister()

7.3.4 变量寄存器分配：allocateRegister(varName)

7.3.5 操作数加载：loadOperand(operand)

7.3.6 寄存器 Spill 策略：spillAllRegisters()

7.3.7 基本块边界处理

7.3.8 避开指定寄存器的分配：getTempRegisterAvoid(avoidReg)

7.3.9 强制重新加载操作数：reloadOperandFresh(operand, avoidReg)

7.4 内存分配与访问

7.4.1 变量访问模式

7.4.2 getelementptr 处理优化

7.5 计算指令处理

7.5 函数调用处理：processCall() 详解

7.5.1 processCall() 完整流程

7.5.2 参数传递详解

7.5.3 寄存器保护策略

7.5.4 IO 函数优化

7.5.5 返回值处理

7.5.6 Forwarding 缓存清除

7.6 跳转分支指令处理

7.6.1 基本块管理

7.6.2 条件分支

7.7 指令解析健壮性（避免命名碰撞）

7.6.3 循环优化

7.3.2 底层寄存器分配：`nextTempReg()`

7.3.3 临时寄存器获取：`getTempRegister()`

7.3.4 变量寄存器分配：`allocateRegister(varName)`

7.3.5 操作数加载：`loadOperand(operand)`

7.3.6 寄存器 Spill 策略：`spillAllRegisters()`

7.3.8 避开指定寄存器的分配：`getTempRegisterAvoid(avoidReg)`

7.3.9 强制重新加载操作数：`reloadOperandFresh(operand, avoidReg)`

7.5 函数调用处理：`processCall()` 详解

7.5.1 `processCall()` 完整流程