2025-北航编译技术设计文档

前言

2025年9月10日完稿

在上编译课之前，我就早有耳闻编译的大名。有很多学长对编译课赞不绝口，称赞其为绝世好课；也有很多学长是苦不堪言，认为其是噩梦。这种两极分化的评价让我对编译这门课充满了敬畏，也多了一丝好奇，到底是怎样的课设才能收获如此丰富的评价呢？希望经过本学期的学习后，我能形成自己的评价，收获自我的感悟。

最后写下我对于编译课的希望吧，在之前学习CO的时候，经常听助教说要多思考少debug，希望在写编译器的时候也可以这样，先思考架构，之后再动手实现，尽量不debug，愉快又轻松。

参考编译器介绍

2025年9月27日完稿

在搜集参考资料时，我找了很多。主要还是广泛阅读了编译课提供的模版代码以及学长博客中流传的经典代码。具体来源如下：

1. LLVM官方文档：https://llvm.org/docs/
2. LLVM框架参考：https://github.com/Hyggge/Petrichor
3. 编译课示例代码：https://github.com/zhhangBian/Compiler-Techniques
4. 学长代码：
   • https://github.com/Galaxy-JewXW/buaa-compiler-2024
   • https://github.com/zhangyitonggg/BUAA-2024-compiler
5. SysY 的语言说明和2025文法说明

在我阅读的大部分编译器中，总体结构的设计都是相似的，大体可以分为前端、中端、后端、utils等。前端主要负责词法分析、语法分析、语义分析。中端做中间代码生成和代码优化。后端再把 IR 映射到 MIPS。utils是一些工具类，比如输出到文件，或者添加错误类型等等。

接口设计上，重点是每个编译阶段之间的衔接。好的接口设计都是流水线一样工作的，上一个阶段的结果作为下一个阶段的输入，这样的好处是功能隔离、高内聚低耦合。比如词法分析最后的结果会返回 Token 流，该 Token 流就是语法分析的输入。因此只需要预先设计每个阶段的输入输出是什么，就可以设计出对应的接口。

文件组织上，大部分编译器都是按阶段分包，原因很简单，调试时打开目录就知道这段代码属于哪一段，不会在一个包里乱成一团。一个典型的文件组织结构如下所示：

• frontend：词法、语法、语义、符号表
• middle：IR 构建与 IR 数据结构
• optimize：中端优化 Pass
• backend：MIPS 生成与后端小优化
• utils：错误收集与输出

编译器总体设计

2025年9月28日初稿，2026年1月2日完稿

在看了许多优秀的编译器架构设计后，我打算参考学长们成熟的架构来设计我自己的编译器。

总体结构

在整体的构建中，我将编译器分为了前中后三段，并设计了错误处理端。在编译器的运行中，在每一端各司其职，仅能通过顶层的端级进行交互，达到了高内聚低耦合的效果。

同时，在编译器的书写中，我还尽量运用了多种面向对象设计思想，融入了多种复杂设计模式，使得编译器的整体书写较为优雅，具有良好的阅读效果。

接口设计

在我的编译器中，把前中后三端设计为了静态类，提供了静态交互方法，不暴露内部的接口。每个阶段都分别用单例模式进行管理，这样方便其他阶段调用该类，同时也只保留一个功能实例，方便功能拆分和统一。

阶段	操作	输入	输出
1	读入文件	testfile.txt	字符流
2	Lexer.lex()	字符流	TokenStream
3	Parser.parse()	TokenStream	AST
4	Visitor.check()	AST	SymbolTable
5	ErrorLog检查	ErrorLog	error.txt
6	IRBuilder.build()	AST + SymbolTable	Module
7	Optimizer.optimize()	Module	Module
8	MipsBuilder.build()	Module	MipsFile

文件组织

编译器的整体代码结构为：

src/
├─Compiler.java
├─backend
│ └─...
├─frontend
│ ├─lexer
│ │ └─...
│ ├─parser
│ │ └─...
│ └─Visitor
│   └─...
├─middle
│ ├─IRBuilder.java
│ ├─IRData.java
│ └─component
│   └─...
├─optimize
│ └─...
└─utils
  ├─Config.java
  ├─Error.java
  ├─ErrorLog.java
  └─Printer.java

三端式结构分明，方便代码管理和debug。每个阶段内部采取单例模式，围绕一个主类添加其他功能类，完成词法分析、语法分析、语义分析等阶段的操作。还设置 utils 类方便错误管理和输入输出等。

词法分析设计

2025年9月28日完稿

编码前设计

文件组织

词法分析这块基本是经典四件套：

• Lexer：扫描字符流并产出 token
• Token：类型 + 字面值 + 行号
• TokenStream：token 列表 + 指针，支持 next/peek/last/setCurPos
• TokenType：所有终结符/关键字枚举

文件结构如图所示：

lexer
 Ⓒ Lexer
 Ⓒ Token
 Ⓒ TokenStream
 Ⓔ TokenType

工作流程

首先 compiler 是编译器的入口，先读入 testfile.txt 文件，然后传入 Lexer 进行词法分析。Lexer 是单例模式，因此调用 Lexer.getInstance() 可以获取到唯一的 Lexer 单例，再调用 lex() 方法进行词法分析，最后返回一个 TokenStream，里面每个单元是一个 Token。

PushbackReader pushbackReader;
try {
    pushbackReader = new PushbackReader(new BufferedReader(new
    FileReader(filePath, StandardCharsets.UTF_8)), 2);
} catch (FileNotFoundException e) {
    throw new RuntimeException("初始化 Lexer 失败: 文件未找到 " + filePath, e);
} catch (IOException e) {
    throw new RuntimeException(e);
}
// 词法分析
TokenStream tokenStream = Lexer.getInstance(pushbackReader).lex();
Printer.printToLexer(tokenStream.toString());

编码完成之后的修改

工作流程

为了简化文件读取流程，我封装了 read() 方法和 currentChar，方便词法分析操作。currentChar 相当于一个指针，用来指向当前正在处理的字符。如果想访问当前字符，只需要直接访问 currentChar 即可。如果要处理下一个字符并且不需要当前字符了，只需要调用 read() 方法就可以。如果想保留当前字符同时提前看下一个字符，只需要调用 peek() 方法。

实际的实现代码如下所示：

public char read() throws IOException {
    int t = reader.read();
    currentChar = (char) t;
    return currentChar;
}

public void unread() {
    try {
        reader.unread(currentChar);
    } catch (IOException e) {
        throw new RuntimeException(e);
    }
}

public char peek() throws IOException {
    int t = reader.read();
    char c = (char) t;
    reader.unread(c);
    return c;
}

public boolean isEOF() {
    return currentChar == EOF;
}

在词法分析主流程中，我采用循环写法，每次循环中先跳过空白符，再读取下一个token。

我把“跳空白 + 跳注释”单独抽成了 skipWhitespaceAndComments()，其核心功能是跳过换行和注释。在 Lexer 类里面维护一个 line，如果遇到换行，包括多行注释里面的换行，则 line++，同时跳过该字符。如果是 /，则看后面是否是 // 或 /*，如果是 // 则一直读字符直到读取至换行，如果是 /* 则一直读取至 */ 或者文件结尾。 因为这块一开始没抽出来的时候特别容易漏掉“多行注释里行号递增”，导致后面语法/语义报错行号一塌糊涂。具体代码如下所示：

public void skipWhitespaceAndComments() throws IOException {
    while (Character.isWhitespace(currentChar) || currentChar == '/') {
        if (currentChar == '\n') {
            line++;
            read();
        } else if (Character.isWhitespace(currentChar)) {
            read();
        } else if (currentChar == '/') {
            try {
                char nextChar = peek();
                if (nextChar == '/') {
                    // Single-line comment
                    while (currentChar != '\n' && !isEOF()) {
                        read();
                    }
                    if (currentChar == '\n') {
                        line++;
                        read();
                    }
                } else if (nextChar == '*') {
                    // Multi-line comment
                    read(); // consume '*'
                    read(); // consume first char inside comment
                    while (true) {
                        if (isEOF()) {
                            break; // Unterminated comment
                        }
                        if (currentChar == '*' && peek() == '/') {
                            read(); // consume '*'
                            read(); // consume '/'
                            break;
                        }
                        if (currentChar == '\n') {
                            line++;
                        }
                        read();
                    }
                } else {
                    // Not a comment, just a '/'
                    return;
                }
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
    }
}

先跳过空白符，然后判断是否遇到了文件结尾，如果是结尾则直接结束。否则读取下一个 Token，并添加至 TokenStream 中。

token 识别上主要分几类：

• 单字符直接定类：括号、分号、+ - * / % , 等
• 需要向前看一位的：= ! < > & |，用 peek() 分辨 ==/=、!=/!、&&/非法 & 等
• 数字：连续读数字得到 INTCON
• 标识符/关键字：连续读字母/数字/下划线，然后用 switch 匹配关键字（const/int/static/…）
• 字符串：遇到 “ 一直读到下一个 “

这样做的好处是按照类别分类，保证了正确性，方便后续扩展与迭代开发。核心分拣代码如下：

public Token getNextToken() throws IOException {
    if (isSingleToken()) {
        // 单字符就可以判定为 Token
        return tackleSingleToken();
    } else if (isOneOrTwoToken()) {
        // 需要再向后读一个字符来判定的 Token
        return tackleOneOrTwoToken();
    } else if (currentChar == '\"') {
        // 字符串字面量
        return tackleStringLiteral();
    } else if (Character.isDigit(currentChar)) {
        // 数字字面量
        return tackleDigit();
    } else {
        // 标识符或关键字
        return tackleIdent();
    }
}

错误处理

词法阶段我只处理了一类比较“硬”的错误：单个 & 或 |。按要求应该是 &&/||，所以这里直接记一个错误码 a，但仍然返回一个逻辑与/或 token，让后续阶段能继续跑下去，否则错误恢复会更麻烦。

语法分析设计

2025年10月1日完稿

编码前设计

语法分析做的事就是把 TokenStream 还原成结构化的 AST。

我的 AST 节点类是按文法一比一建造的，优点是写起来直接，缺点就是类很多、文件夹会很大。

对于 Parser 采用单例模式设计，用 Node 接口来统一串联所有节点。为了更好的管理每种语法类型，我还对所有语法成分进行了目录分类，比如所有语句类 Stmt 可以单独存放，所有表达式 Exp 也可以存放，所有初始值 IV, CIV 也可以单独存放。

文件组织

• frontend/parser/Parser.java：递归下降解析
• frontend/parser/AST/*：各语法节点类

具体文件结构如图所示：

parser
 └─ AST
    ├─ CIV
    ├─ Exp
    ├─ Func
    ├─ IV
    ├─ Stmt
    │  Ⓒ Block
    │  Ⓘ BlockItem
    Ⓒ CompUnit
    Ⓒ ConstDecl
    Ⓒ ConstDef
    Ⓘ Decl
    Ⓒ VarDecl
    Ⓒ VarDef
 Ⓘ Node
 Ⓒ Parser

编码完成之后的修改

工作流程

为了更方便的处理 TokenStream，我依旧仿照词法分析的方式设置了很多方法，例如 next，getCurToken，peek等。

其用途是，getCurToken 相当于一个 Token 指针，指向当前处理的 Token，想要获取当前 Token 只需要调用 getCurToken 方法。如果处理完当前 Token 想要处理下一个 Token，只需要调用 next 方法即可。这里还支持 peek，可以动态向前查看多个 Token 字符。为了查看上一个字符，还可以调用 last 方法。同时为了支持回溯，我还支持用 getCurPos 获取当前的 pos，在需要回溯的时候再 setCurPos 重新设置 pos 位置，达到回溯的效果。

核心代码如下所示：

public Token next() {
    if (pos >= tokens.size()) {
        curToken = new Token(TokenType.EOF, "end", -1);
        return curToken;
    }
    // System.out.println(p + " " + tokens.get(p).getLine() + " " + tokens.get(p));
    curToken = tokens.get(pos++);
    return curToken;
}

public Token getCurToken() {
    return curToken;
}

public Token peek(int delta) {
    if (pos + delta - 1 >= tokens.size()) {
        return new Token(TokenType.EOF, "end", -1);
    }
    return tokens.get(pos + delta - 1);
}

public Token last() {
    if (pos <= 0) {
        return new Token(TokenType.EOF, "end", -1);
    }
    return tokens.get(pos - 2);
}

public int getCurPos() {
    return pos;
}

public void setCurPos(int pos) {
    this.pos = pos;
    if (pos > 0 && pos <= tokens.size()) {
        this.curToken = tokens.get(pos - 1);
    } else {
        this.curToken = null;
    }
}

递归下降

整体就是递归下降：parseCompUnit() 往下调 parseDecl/parseFuncDef/parseStmt/parseExp…。对于每一个语法成分，我都建立了一个类，在语法分析时只需要调用该语法成分的 parse 方法，然后依次调用子成分的 parse 方法，最后返回该语法成分的实例即可。

我们首先改写文法，消除其中的左递归，然后在各个节点类中按照改写后的文法定义各个节点的属性和相应的Get和Set方法。之后，我们在Parser类中递归向下分析每个节点类即可。具体细节如下：

1. 递归下降解析
   每种语法规则对应一个解析函数。例如：
   • parseAddExp() 用于解析 AddExp，它递归调用 parseMulExp()。
2. 回溯支持
   • 在可能的多分支选择中，通过预读下一个 Token 判断选择路径。
   • 如果无法通过预读解决选择路径的话，则需要进行回溯，此时仅需要记录下回溯返回的位置，并在结束时返回合适的位置即可。

有个我觉得比较关键的点是语句分支的判定，比如 Stmt 里要区分：

• LVal '=' Exp ';'
• [Exp] ';'

这块我用了“试探 + 回退”：先记下 curPos，临时解析一次 LVal 看下一 token 是不是 ASSIGN，然后再 setCurPos(curPos) 回去走真正的分支。

一个典型的代码示例为：

// Stmt -> 'printf' '(' StringConst { ',' Exp } ')' ';' // i j
public PrintfStmt parsePrintfStmt() {
    Token printfToken = tokenStream.getCurToken(); // printf
    tokenStream.next(); // printf
    tokenStream.next(); // (
    Token stringConst = tokenStream.getCurToken(); // stringConst
    tokenStream.next(); // stringConst
    ArrayList<Exp> exps = new ArrayList<>();
    while (tokenStream.getCurToken().is(COMMA)) {
        tokenStream.next(); // ,
        exps.add(parseExp());
    }
    checkParserError(RPARENT);
    checkParserError(SEMICN);
    return new PrintfStmt(stringConst, exps);
}

错误处理

语法阶段主要按课程要求处理 i/j/k 三类缺符号：

• i：缺 ;
• j：缺 )
• k：缺 ]

实现上统一走 checkParserError：如果当前 token 不是期望符号，就用 tokenStream.last().getLine() 去报错，也就是“报在上一个正常 token 的行号上”，否则就消费掉这个符号。

另外我加了一个 errorLayer：在“试探解析”期间把它加一，避免试探过程触发一堆无意义的 i/j/k，这类误报非常影响调试心情。

• 增加 errorLayer，把“试探解析”从错误收集里隔离出去。
• i/j/k 统一封装到 checkParserError，不在各个 parseXxx 里散落重复逻辑。

语义分析设计

2025年10月7日完稿

编码前设计

语义分析主要需要做两件事：

• 对于正确的源程序，需要从源程序中识别出定义的常量、变量等，输出它们的作用域序号，单词的字符/字符串形式，类型名称。
• 对于错误的源程序，需要识别出错误，并输出错误所在的行号和错误的类别码。

可以看到课程组有意识地将错误处理分散在编译器的全流程中，事实上这确实是合理的，因为真正的编译器不可能是只在考察编译器错误处理能力时提供错误的代码。

文件组织

语义分析主要在 Visitor 中完成，核心是遍历 AST 并维护符号表。

• frontend/Visitor/Visitor.java：语义检查主体，实现 AST 节点的 visit 方法。
• frontend/Visitor/SymbolTable.java：树形符号表，支持父子作用域嵌套。
• frontend/Visitor/Symbol/*：
  • VarSymbol：变量/常量符号，记录类型、维度、是否全局等。
  • FuncSymbol：函数符号，记录返回值类型、形参列表。
  • SymbolType：符号类型枚举。

具体文件结构如下图所示：

Visitor
 └─ Symbol
    Ⓒ FuncSymbol
    Ⓒ Symbol
    Ⓔ SymbolType
    Ⓒ VarSymbol
 Ⓒ SymbolTable
 Ⓒ Visitor

工作流程

入口从 CompUnit 开始，顺序检查：全局声明 → 函数定义 → main 函数。

对于每个语法成分，先用 get 方法获得其子成分，然后再依次调用 check 方法检查其子语法成分是否有语义错误。

代码示例为：

// Stmt -> 'for' '(' [ForStmt] ';' [Cond] ';' [ForStmt] ')' Stmt // h
public void checkForCycleStmt(ForCycleStmt stmt) {
    ForStmt initStmt = stmt.getInitStmt();
    Cond cond = stmt.getCond();
    ForStmt stepStmt = stmt.getStepStmt();
    Stmt bodyStmt = stmt.getBodyStmt();
    if (initStmt != null) {
        checkForStmt(initStmt);
    }
    if (cond != null) {
        checkCond(cond);
    }
    if (stepStmt != null) {
        checkForStmt(stepStmt);
    }
    loopNum++;
    checkStmt(bodyStmt);
    loopNum--;
}

在作用域管理上，采用树形 SymbolTable 结构。每当进入一个新的代码块，Block，就调用 enterBlock() 创建一个新的子符号表，并将当前符号表指针 curTable 指向它；离开代码块时，调用 leaveBlock() 回退到父符号表。

具体代码如下：

private void enterBlock() {
    idCount++;
    SymbolTable child = new SymbolTable(idCount, curTable);
    curTable.addChild(child);
    curTable = child;
}

private void leaveBlock() {
    curTable = curTable.getFather();
}

编码完成之后的修改

工作流程

在编码过程中，为了方便后续中间代码生成时能正确映射符号，我严格保证了 Visitor 建立符号表的顺序与 IRBuilder 遍历 AST 的顺序一致。

此外，对于库函数，getint, putint, putch, putstr，我在 Visitor 的构造函数中直接将它们加入到了顶层全局符号表中。这样在处理函数调用时，无需对库函数做特殊判断，除了 getint 需要检查无参，统一了处理逻辑。最后在输出 symbol.txt 的时候去掉库函数的输出即可。

错误处理

语义错误主要依据课程要求的错误码进行检查，重点处理了以下几类：

错误类别码	错误类型	解决思路
a	操作符有错误（ & 和 | ）	在语法分析阶段进行
b	名字重定义（函数名和变量名重定义）	在当前作用域内查找
c	可执行语句使用未定义的名字	利用符号表的父指针，不断向外查找
d	函数参数个数不匹配	解析完函数调用后进行确认
e	函数参数类型不匹配	解析完函数调用后进行确认
h	不能改变常量的值	检查Symbol的类型是否为const
f	无返回值的函数存在不匹配的return语句	在 FuncDef 内进行处理
g	有返回值的函数缺少return语句	在 FuncDef 解析结束后对函数Block进行查找

对于新增的错误类型，我采用在 check 方法中特判的做法。

如果有语义错误，则新建 Error 实例并调用 addError 添加至 ErrorLog 中，具体代码如下：

public void addError(Token ident, char errorKey) {
    Error error = new Error(ident.getLine(), errorKey);
    ErrorLog.getInstance().addError(error);
}

代码生成设计

2025年11月15日初稿，2025年12月20日完稿

编码前设计

中间代码选择

代码生成分为中间代码生成 LLVM IR 和目标代码生成 MIPS 两个阶段。

我是选择的LLVM作为中间代码，原因主要有三：

• 有很多往年学长的博客、代码可以参考，便于实现；
• LLVM 本身是十分易于优化的。
• 即使最后完不成 mips 代码生成，也可以选择 LLVM 作为目标代码，可谓是进可攻、退可守。

LLVM 介绍

LLVM 中有四个具有依次包含关系的基本概念：

• Module 是一份 LLVM IR 的顶层容器，对应于编译前端的每个翻译单元。一个 Module 由若干 GlobalValue 组成，而一个GlobalValue 可以是全局变量 GlobalVariable，也可以是函数 Function。
• Function 就是编程语言中的函数，包括函数签名和若干个基本块。函数内的第一个基本块叫做入口基本块。
• BasicBlock 是一组顺序执行的指令集合，只有一个入口和一个出口，非头尾指令执行时不会违背顺序跳转到其他指令上去
  • 每个基本块最后一条指令一般是跳转指令
  • 每个 BasicBlock 都有一个 label，label 使得该 BasicBlock 有一个符号表的入口点
  • 函数内最后一个基本块的最后条指令是函数返回指令，以terminator instruction（ret、br等）结尾
• Instruction 是 LLVM IR 的最小可执行单位，每一条指令都单占一行

Value-Use

LLVM 中所有类都直接或间接继承自 Value，在 LLVM 中，有“一切皆 Value”的说法。通过规整的继承关系，就得到了 LLVM 的类型系统。

为了表达 Value 之间的引用关系，LLVM 中还有一种特殊的 Value 叫做 User，其将其他 Value 作为参数。

Instruction 继承自 User，因此它可以将其他 Value 作为参数。对于指令 %add1 = add nsw i32 %a, %b，在 %add1 与 %a、%b 之间分别构成了 Use 关系。后续的相关指令也可以继续进行调用，形成 Use 链。

这种指令间的关系正是 LLVM 的核心之一，实现了 SSA 形式的中间代码。这样的形式可以方便 LLVM 进行分析和优化，如：

• 可以快速分析两个值是否是同一个值，是否要删除冗余代码。
• 如果一个 Value 没有 Use 关系，很可能就是可以删除的冗余代码。

在设计中间代码生成的过程中，我一开始并不理解其 value-use 关系的设计目的，直到后期做到了代码优化，才明白其重要性，可以便捷地找到在函数的值实体之间的依赖关系。

文件组织

• 中间代码：
  • middle/IRBuilder.java：IR 生成总入口。
  • middle/component/*：IR 组件，包括 Module, Function, BasicBlock, Instruction 等。
• 目标代码：
  • backend/MipsBuilder.java：MIPS 生成总入口。
  • backend/MipsFile.java：负责管理 .data 和 .text 段并输出。
  • backend/component/*：MIPS 指令与操作数类。

具体文件组织如下图：

middle
 └─ component
    ├─ instruction
    ├─ model
    └─ type
    Ⓒ BasicBlock
    Ⓒ ConstInt
    Ⓒ ConstString
    Ⓒ ForLoop
    Ⓒ FuncParam
    Ⓒ Function
    Ⓒ GlobalVar
    Ⓒ InitialValue
    Ⓒ Module
    Ⓒ Undefined
 Ⓒ IRBuilder
 Ⓒ IRData

工作流程

1. IR 生成：遍历 AST，将全局变量转换为 GlobalVar，将函数体转换为 BasicBlock 和 Instruction 序列。
2. MIPS 生成：遍历生成的 IR Module，将每个 IR 指令映射为对应的 MIPS 指令序列。

编码完成之后的修改

我使用了 LLVM-IR 来作为中间代码。使得程序真正有了可运行的结果。

中间代码生成无疑是工作量最大的一部分，我几乎投入了完整的五天才解决了中间代码生成过程中的全部问题。

中间代码生成

在 IRBuilder 中，我维护了一个 lookupTable，用于建立 AST 中的 Symbol 到 LLVM IR Value 的映射。

作用域管理

为了保证符号查找的正确性，我严格按照 AST 遍历顺序维护符号表栈。
这样可以跟语义分析保持同样的逻辑，方便我书写代码，同样也方便我梳理思路，防止出错。

代码如下：

private void enterScope() {
    int index = childIndexMap.getOrDefault(currentTable, 0);
    if (index < currentTable.getChildren().size()) {
        currentTable = currentTable.getChildren().get(index);
        childIndexMap.put(currentTable.getFather(), index + 1);
    } else {
        throw new RuntimeException("Scope mismatch...");
    }
    lookupTable = new SymbolTable(currentTable.getId(), lookupTable);
}

控制流生成

对于 if-else 语句，我采用了标准的“基本块 + 跳转”模式。
特别注意了短路求值和空 else 块的处理。

相关代码如下所示：

private void buildIfElseStmt(IfElseStmt stmt) {
    BasicBlock trueBlock = new BasicBlock(IRData.getBlockName());
    BasicBlock falseBlock = stmt.getElseStmt() != null ? new
    BasicBlock(IRData.getBlockName()) : null;
    BasicBlock nextBlock = new BasicBlock(IRData.getBlockName());

    // 设置基本块所属函数
    trueBlock.setFunction(currentFunction);
    if (falseBlock != null) falseBlock.setFunction(currentFunction);
    nextBlock.setFunction(currentFunction);

    // 生成条件跳转
    buildCond(stmt.getCond(), trueBlock, falseBlock != null ? falseBlock : nextBlock);

    // 生成 True 分支
    IRData.setCurrentBlock(trueBlock);
    currentBlock = trueBlock;
    buildStmt(stmt.getIfStmt());
    if (!isBlockTerminated(currentBlock)) {
        new BrInst(nextBlock);
    }

    // 生成 False 分支（如果有）
    if (falseBlock != null) {
        IRData.setCurrentBlock(falseBlock);
        currentBlock = falseBlock;
        buildStmt(stmt.getElseStmt());
        if (!isBlockTerminated(currentBlock)) {
            new BrInst(nextBlock);
        }
    }

    // 汇合点
    IRData.setCurrentBlock(nextBlock);
    currentBlock = nextBlock;
}

数组初始化

为了处理局部数组的初始化，我实现了 buildLocalArrayInit 方法。
利用 GepInst 计算地址并逐个 Store。

代码如下：

private void buildLocalArrayInit(Value baseAddr, InitVal initVal) {
    if (initVal instanceof IVExps) {
        IVExps ivExps = (IVExps) initVal;
        int size = ivExps.getExps().size();
        int arrayLen = ((ArrayType) ((PointerType)baseAddr.getValueType()).getTargetType()).getElementNum();

        // 显式初始化的部分
        for (int i = 0; i < size; i++) {
            Exp exp = ivExps.getExps().get(i);
            Value val = buildExp(exp);
            Instruction gep = new GepInst(baseAddr, new ConstInt(IntegerType.i32, i));
            new StoreInst(gep, val);
        }

        // 未显式初始化的部分补 0
        for (int i = size; i < arrayLen; i++) {
            Instruction gep = new GepInst(baseAddr, new ConstInt(IntegerType.i32, i));
            new StoreInst(gep, new ConstInt(IntegerType.i32, 0));
        }
    }
}

MIPS目标代码生成

在 MipsBuilder 中，我使用了 Map<Class, Consumer> 的方式来分发指令生成逻辑。
这样做的好处是可以避免冗长的 if-else 或 switch 结构。

代码如下：

private void initInstructionHandlers() {
    instructionHandlers.put(AllocInst.class, inst -> buildAllocInst((AllocInst) inst));
    instructionHandlers.put(BinaryInst.class, inst -> {
        BinaryInst binaryInst = (BinaryInst) inst;
        if (OperatorType.isLogicalOperator(binaryInst.getOpType())) {
            buildIcmp(binaryInst);
        } else {
            buildBinaryInst(binaryInst);
        }
    });
    // ... 其他指令映射
}

栈帧管理与寄存器分配

在函数生成开始时，我会计算所有局部变量的栈偏移量。
如果开启优化，还会根据寄存器分配结果预留寄存器。

代码如下：

private void buildFunction(Function function) {
    currentFunction = function;
    var2Offset = new HashMap<>();
    curStackOffset = 0;
    // 获取寄存器分配结果
    var2reg = optimizeOn ? new HashMap<>(function.getVar2reg()) : new HashMap<>();

    new Label("func_" + function.getName().substring(1));

    // 处理参数：前4个参数在寄存器，后续参数在栈上
    for (int i = 0; i < function.getFuncParams().size(); i++) {
        curStackOffset -= 4;
        if (i < 4) {
            var2reg.put(function.getFuncParams().get(i),
            Register.getByOffset(Register.A0, i));
        }
        var2Offset.put(function.getFuncParams().get(i), curStackOffset);
    }
    // 为其他指令分配栈空间（如果未分配寄存器）
    for (BasicBlock block : function.getBasicBlocks()) {
        for (Instruction instruction : block.getInstructions()) {
            if (!instruction.getName().isEmpty() && !var2reg.containsKey(instruction)) {
                curStackOffset -= 4;
                var2Offset.put(instruction, curStackOffset);
            }
        }
    }
    // ... 生成基本块
}

比较指令生成

对于比较指令，如 icmp eq，我将其转换为 MIPS 的 seq 等指令。
如果操作数在寄存器中则直接使用，否则从栈中加载。

代码如下：

private void buildIcmp(BinaryInst binaryInst) {
    // ... 确定操作码 asmOp (SEQ, SNE, SLT 等)
    Value operand1 = binaryInst.getOperand1();
    Value operand2 = binaryInst.getOperand2();
    Register reg1 = Register.K0;
    Register reg2 = Register.K1;

    // 加载操作数到寄存器
    if (operand1 instanceof ConstInt constInt) {
        new LiAsm(reg1, constInt.getIntValue());
    } else if (var2reg.containsKey(operand1)) {
        reg1 = var2reg.get(operand1);
    } else {
        new MemAsm(AsmOp.LW, reg1, Register.SP, var2Offset.get(operand1));
    }
    // ... 加载 operand2

    // 生成比较指令
    Register targetReg = var2reg.getOrDefault(binaryInst, Register.K0);
    new CmpAsm(asmOp, targetReg, reg1, reg2);

    // 如果结果未分配寄存器，存回栈
    if (!var2reg.containsKey(binaryInst)) {
        new MemAsm(AsmOp.SW, targetReg, Register.SP, var2Offset.get(binaryInst));
    }
}

编码前后的改变主要如下：

1. 在每条指令翻译后都添加相应的注释输出中间代码，这样可以便于debug
2. 对栈的操作核查了多次，小心再小心

代码优化设计

2026年1月2日完稿

编码前设计

文件组织

• optimize/Optimizer.java：优化器入口，组织所有 Pass 的执行顺序。
• optimize/*：各种具体的优化 Pass 类，如 Mem2Reg, GVN, LoopUnroll 等。

所做的优化大概如下：

optimize
 Ⓒ BlockSimplify
 Ⓒ CodeRemoval
 Ⓒ CondConstProp
 Ⓒ DivideCall
 Ⓒ FixMD
 Ⓒ FunctionCopy
 Ⓒ FunctionSideEffect
 Ⓒ GCM
 Ⓒ GlobalVarLocalize
 Ⓒ GVN
 Ⓒ IcmpOptimize
 Ⓒ InlinedFunction
 Ⓒ LocalConstArrayToValue
 Ⓒ LoopAnalysis
 Ⓒ LoopInvariantHoist
 Ⓒ LoopRecord
 Ⓒ LoopUnroll
 Ⓒ Mem2Reg
 Ⓒ MemoryOptimize
 Ⓒ Optimizer
 Ⓒ PhiOptimize
 Ⓒ PickGep
 Ⓒ PrintOptimize
 Ⓒ PureFunctionEval
 Ⓒ SpecificOptimize
 Ⓒ SurplusBlock
 Ⓒ UnusedFunction
 Ⓒ UnusedLocalArray

工作流程

优化器接收一个 Module，按顺序执行一系列优化 Pass，对 IR 进行转换和精简，最后输出优化后的 Module。

编码完成之后的修改

优化具体可见优化文档，这里挑几个有代表性的优化讲一下。

工作流程

我采用了“多轮迭代”的策略，将主要的优化 Pass 放入一个循环中执行多次，目前设定为 10 轮，以便不同优化之间能够相互促进。例如，Mem2Reg 可能会产生无用代码，随后的 CodeRemoval 可以将其删除，从而暴露更多的优化机会。

public void optimize() {
    UnusedLocalArray.run(module);
    PureFunctionEval.run(module); // 纯函数常量参数求值
    for (int i = 0; i < 10; i++) {
        SurplusBlock.build(module);
        Mem2Reg.run(module, true);
        // ...
        GVN.run(module);
        LoopUnroll.run(module);
    }
    SurplusBlock.build(module);
}

关键优化 Pass 实现

Mem2Reg

这是中端优化的核心，通过计算支配树和支配边界，插入 Phi 节点并重命名变量，将内存访问（ alloca/load/store ）提升为寄存器操作。

private static void optimize(Function function, boolean simplify) {
    currentFunction = function;
    calcControlFlowGraph(); // 计算 CFG
    calcDominatorTree();    // 计算支配树
    calcDominanceFrontier();// 计算支配边界

    if (!simplify) return;

    // 对每个整型 AllocInst 进行提升
    for (BasicBlock block : function.getBasicBlocks()) {
        ArrayList<Instruction> instructions = new ArrayList<>(block.getInstructions());
        for (Instruction instruction : instructions) {
            if (instruction instanceof AllocInst allocInst
            && (allocInst.getTargetType().equals(IntegerType.i32)))
            {
                currentAlloc = allocInst;
                initMem2Reg();
                insertPhi(); // 在支配边界插入 Phi
                renameVariables(currentFunction.getEntryBlock()); // 变量重命名
            }
        }
    }
}

LoopUnroll

针对小循环进行完全展开，消除循环控制开销。我主要识别单回边、单基本块的简单循环。

private static boolean tryUnroll(LoopRecord loop) {
    BasicBlock header = loop.getEntry();
    // 仅处理单回边的循环
    if (loop.getEnds().size() != 1) return false;

    // 检查循环结构（必须是条件跳转结尾）
    Instruction term = header.getLastInstruction();
    if (!(term instanceof BrInst br) || !br.isConditional()) return false;

    // 识别归纳变量和步长
    // ... (代码省略：查找 Phi 节点和更新指令)

    // 模拟循环执行，如果迭代次数在阈值内（MAX_TRIP_COUNT = 32），则进行展开
    // ...
}

PureFunctionEval

这是一个比较有特色的优化，针对无副作用且参数为常量的函数调用，在编译期直接计算结果。这对于递归计算非常有效。

private static boolean tryEvaluateCall(CallInst callInst, BasicBlock block, Module module) {
    Function calledFunc = callInst.getCalledFunction();
    // 检查是否是可求值的纯函数（无全局变量读写、无 IO）
    if (!calledFunc.canReplace()) return false;

    // 检查所有参数是否为常量
    ArrayList<Value> params = callInst.getParameters();
    ArrayList<Integer> constArgs = new ArrayList<>();
    for (Value param : params) {
        if (param instanceof ConstInt constInt) {
            constArgs.add(constInt.getIntValue());
        } else {
            return false; // 参数不是常量，无法求值
        }
    }
    // 尝试模拟执行并缓存结果
    // ...
    // 替换 call 为常量结果
    ConstInt constResult = new ConstInt(IntegerType.i32, result);
    callInst.replaceByNewValue(constResult);
    block.getInstructions().remove(callInst);
    return true;
}

PeepHole

在后端生成汇编后，通过模式匹配消除冗余指令。例如，将“比较生成 0/1”和“根据 0/1 跳转”融合为一条条件跳转指令。

/**
* 将“cmp 生成 0/1 + 分支判断该结果是否为 0”融合为一条直接分支。
* seq $t, $a, $b
* beq $t, 0, L => bne $a, $b, L
*/
private static void fuseCmpAndBranchOnZero() {
    // ... 遍历指令序列
    if (cur instanceof BrAsm candidate
    && (candidate.getOp() == AsmOp.BEQ || candidate.getOp() == AsmOp.BNE)
    && candidate.getRs() == cmpAsm.getRd()) {
        // 检查 cmp 结果是否只被该分支使用
        // ...
        // 替换为新的分支指令，直接比较原操作数
        // ...
    }
}

总结

2026年1月2日完稿

感想具体可见总结感想，这里简单说两句。

整体做下来，我觉得这个项目最大的收益是把可调试性先立住：每个阶段都有明确的输入输出结构，并且都有对应的落盘结果可以看。这样不管是前端的缺符号、语义的某个错误码，还是后端寄存器/栈偏移的问题，定位路径都会短很多。

编译器很有意思，写编译的过程也既痛苦又快乐，不过总之还是能学到很多有用的编译知识的，我很满意了。

感谢为我铺路的学长们，感谢伟大的助教和老师，感谢这门课！