Skip to content

wrongization/compile

BranchesTags

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

1 Commit
src
src
 
 
上机
上机
 
 
官方文档
官方文档
 
 
README.md
README.md
 
 
优化文档.md
优化文档.md
 
 
总结感想.md
总结感想.md
 
 

Repository files navigation

2025BUAA编译代码仓库

TODO:

  • 词法分析
  • 语法分析
  • 语义分析
  • 中间代码生成
  • 中间代码优化
  • 目标代码生成

编译器设计说明

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

1. 总体目标

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

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

  1. Compiler 逐行读取 testfile.txt，按照行存入 lines 列表，然后调用 preprocess 进行注释预处理，存入 preprocessedLines 列表。
  2. Lexer 调用analyze 方法，传入 preprocessedLines 列表。
  3. 注释预处理后的非空行传递给 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：

  1. 线性收集为节点序列 [A, op1, B, op2, C, op3, D]。
  2. 逆向折叠构造：最右 (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 等处明确实现）。

主要流程（简要）：

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

  • 全局变量：

    @globalVar = dso_local global i32 0

  • 全局数组：

    @arr = dso_local global [10 x i32] zeroinitializer

    初始化值存储在 constArraysInit，生成时展开

  • 局部变量：

    %1 = alloca i32
store i32 %initVal, i32* %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 变量语义

  • 数组元素访问：

    %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 提取

  • 返回值处理：

    %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()），也能保证从左到右的求值顺序
    • 示例说明： 
      // 源代码
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 语义一致

  • 完整示例：

    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 源码）：

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

设计要点

  1. 参数传递：
    • 前4个参数通过$a0-$a3传递
    • 第5个及以上参数通过栈传递，位于$fp正偏移
    • 即使参数在寄存器传递，函数入口也会将其备份到栈上（+0($fp)到+12($fp)）
  2. 临时寄存器区：
    • 固定预留20个字（80字节）用于保存$t0-$t19（即MIPS的$8-$27）
    • 函数调用前保存，返回后恢复
    • 仅保存已使用的临时寄存器（通过usedTempRegs跟踪）
  3. 局部变量区：
    • 所有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 字节

优化亮点：

  1. 按需分配：未使用的 alloca 变量不占用栈空间。
  2. 精确预估：通过活跃变量分析避免过度预留 Spill 槽。
  3. 安全余量：预留 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 变量访问模式

全局变量访问：

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

局部变量访问：

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 缓存失效。

实现：

// 调用后清除所有 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 多级优化：

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

7.8.3 控制流优化

基本块边界优化：

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

条件分支优化：

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

About

2025BUAA编译代码仓库

Resources

Readme
Activity

Stars

0 stars

Watchers

0 watching

Forks

0 forks
Report repository

Releases

No releases published

Packages

 
 
 

Contributors

Languages