编译器设计文档
文档要求
请自选一种编译器的源代码进行阅读分析，在此基础上完成总体架构设计，然后在编译器实现的每个阶段完成相应部分的设计文档，格式及内容不限，每个阶段均需写出编码之前的设计，编码完成之后对设计的修改情况。
文档包括如下内容：
- 参考编译器介绍：总结所阅读的编译器的总体结构、接口设计、文件组织等内容
- 编译器总体设计：介绍自己的将要实现的编译器的总体结构、接口设计、文件组织等内容
- 词法分析设计：编码前的设计、编码完成之后的修改
- 语法分析设计：编码前的设计、编码完成之后的修改
- 错误处理设计：编码前的设计、编码完成之后的修改
- 代码生成设计：编码前的设计、编码完成之后的修改
- 代码优化设计：编码前的设计、编码完成之后的修改，未选择 MIPS 代码生成的同学无需完成此项内容
应在各个阶段任务完成相应部分并提交，最终提交一份完整的文档，文档格式为 pdf 版本。
参考编译器介绍
一个凝练的小编译器 c4，实现了词法分析、语法分析、目标代码生成，在 525 行内使用了四个函数（实际上也就是三个大模块 + main 函数）完成对简单 C 语言程序的编译，虽然其中的代码实现比较复杂，但是逻辑相对清晰，能够很直观地理解编译的进程。但是它没有实现错误处理和代码优化（）
除此之外也参考了许多往届学长的课设代码，大致地了解了编译器的各个模块
编译器总体设计
总体结构
本编译器设计按照主流编译器的编译过程，也就是课程释放的作业顺序编排工作的步骤实现了从 SysC 语言的输入到 mips 汇编语言的输出：
词法分析 → 语法分析 → 语义分析与中间代码生成 → 目标代码生成 → 代码优化
符号表管理与错误处理
这五个主要流程分为前端和后端两部分，前端包括词法分析（核心类为 TokenAnalyzer）、语法分析（核心类为 NodePaeser）、中间代码生成（核心类为 LLCenter），后端包括目标代码生成（核心类为 MipsCenter）和代码优化（实际未进行优化）。
文件组织
总体文件组织如下：
src
| Compiler.java
| config.json
|
+---exception
| NoFileException.java
| StatusCode.java
|
+---frontend
| | ErrorChecker.java
| | NodeParser.java
| | TokenAnalyzer.java
| |
| +---ast
| | AddExpNode.java
| | BlockItemNode.java
| | BlockNode.java
| | BTypeNode.java
| | CompUnitNode.java
| | CondNode.java
| | ConstDeclNode.java
| | ConstDefNode.java
| | ConstExpNode.java
| | ConstInitValNode.java
| | DeclNode.java
| | EqExpNode.java
| | ExpNode.java
| | ForStmtNode.java
| | FuncDefNode.java
| | FuncFParamNode.java
| | FuncFParamsNode.java
| | FuncRParamsNode.java
| | FuncTypeNode.java
| | IdentNode.java
| | InitValNode.java
| | LAndExpNode.java
| | LOrExpNode.java
| | LValNode.java
| | MainFuncDefNode.java
| | MulExpNode.java
| | NodeCategory.java
| | NumberNode.java
| | PrimaryExpNode.java
| | RelExpNode.java
| | StmtCategory.java
| | StmtNode.java
| | UnaryExpNode.java
| | UnaryOpNode.java
| | VarDeclNode.java
| | VarDefNode.java
| |
| +---shortSymbol
| | Function.java
| | Symbol.java
| | SymbolTable.java
| | Var.java
| |
| \---token
| Token.java
| TokenCategory.java
|
+---llvm
| | LLCenter.java
| | Visitor.java
| |
| +---identifier
| | Identifier.java
| |
| +---symbol
| | Symbol.java
| | SymbolTable.java
| |
| +---type
| | ArrayType.java
| | BasicType.java
| | BlockType.java
| | LabelType.java
| | PointerType.java
| | Type.java
| | TypeList.java
| | VoidType.java
| |
| \---value
| | ArrayValue.java
| | BasicBlock.java
| | Builder.java
| | ConstantValue.java
| | FuncFParam.java
| | Function.java
| | GlobalVar.java
| | Use.java
| | User.java
| | Value.java
| |
| \---instruction
| AllocaInstr.java
| BinaryInstr.java
| BitCastInstr.java
| BranchInstr.java
| CallInstr.java
| GepInstr.java
| IcmpInstr.java
| InstrType.java
| Instruction.java
| JumpInstr.java
| LoadInstr.java
| ReturnInstr.java
| StoreInstr.java
|
+---mips
| | Builder.java
| | MipsCenter.java
| | RegisterFile.java
| |
| +---data
| +---instr
| | AbstractInstr.java
| | BranchDInstr.java
| | CalDInstr.java
| | CalSInstr.java
| | DataRecord.java
| | DataTag.java
| | InstrType.java
| | JumpInstr.java
| | LabelInstr.java
| | MemSInstr.java
| | PseudoInstruction.java
| | Syscall.java
| | UtilsSInstr.java
| |
| \---operands
| Imm.java
| Label.java
| Operand.java
| Register.java
|
\---utils
| Calculator.java
| Logger.java
| OutputRecord.java
| Pair.java
| ParameterParser.java
| Settings.java
|
\---error
Error.java
ErrorType.java
|
分功能介绍见文档后续内容
接口设计
各功能部分按照一定的规则输入和输出进行划分，接口供给定义如下：
- 工具类：创建文件流，从源文件读入字符串序列；分析参数并创建输出文件
- 词法分析：输入为工具类提供的
ArrayList<String> 形式的源文件，输出为语法分析后得到的 ArrayList<Token> 形式的词法单元
- 语法分析：输入为词法分析提供的
ArrayList<Token>，输出为语法分析后得到的语法树顶层节点 CompUnitNode
- 错误处理：输入为语法分析得到的语法树，输出为语法树中存在的语法错误，若存在错误则不进行后续部分，编译程序直接退出
- 中间代码生成：输入为语法分析得到的语法树，输出为语法树对应的线性
ArrayList<Value> llvm 指令序列和等价的字符序列
- 目标代码生成：输入为中间代码生成得到的 llvm 指令序列，输出为
ArrayList<AbstrctInstruction> 的线性 mips 指令序列和等价字符序列
- 代码优化：本编译器不涉及代码优化部分，故不存在相应接口
工具类设计
文件组织
src
|
+---exception
| NoFileException.java
| StatusCode.java
|
\---utils
| Calculator.java
| Logger.java
| OutputRecord.java
| Pair.java
| ParameterParser.java
| Settings.java
|
\---error
Error.java
ErrorType.java
|
具体设计
utils 包包括了编译器执行过程中需要用到的一些辅助类、保存类和相关的信息。
utils/Calculator
public static produceConst(Value v1, TokenCategory tc, Value v2)
按照 TokenCategory 不同，执行在中间代码生成过程中对常数进行对应的优化运算，减少 llvm 指令的条数
utils/Logger
public static void initLogger()
初始化输入输出文件流，为各功能部分提供对应的写入/读取文件
public static void process(int statusCode, String msg)
编译器运行过程中的相关信息显示，根据不同 statusCode 区分信息级别
public static void printFile(String content, String targetType)
编译器各功能部分对外的输出接口，根据所处的功能阶段不同调用不同的 targetType 进行对应文件的输出
utils/*
Settings 类与 Logger 类联动控制文件的输出与否
Pair 类是一个实现 <K, V> 结构的工具类
ParameterParser 类实现了对命令行参数的解析，实际测评无用，可供课下测试使用
OutputRecord 类已弃用
软件包 error 存放运行时产生的错误种类，供 Logger 进行信息级别区分和输出
exception/*
- 本软件包提供具体的错误类，可加入更具体的错误信息供
Logger 输出
Compiler
在主运行类中调用方式如下，解析参数并初始化设置
if (args.length > 0) { ParameterParser.setParameter(args); }
Logger.initLogger();
|
词法分析设计
文件组织
src
|
+---frontend
| TokenAnalyzer.java
|
\---token
Token.java
TokenCategory.java
|
具体设计
frontend/TokenAnalyzer
词法分析的核心类，采用单例模式进行调用。关键处理点在于通过字符的移动和匹配对当前的短语进行匹配，匹配成功后形成对应的 Token，存入短语集合中，供后续词法分析使用。
public int getChar(BufferedInputStream buffer) ：从输入字符串中获取下一个字符，进行后续匹配
public int getChar(BufferedInputStream buffer) {
int c = 0;
try {
c = buffer.read();
} catch (IOException e) {
e.printStackTrace();
}
return c;
}
|
public ArrayList<Token> getToken(BufferedInputStream buffer)：解析核心函数，通过对输入字符串的逐字符判断，进入不同的解析方法得出具体单词，最终返回解析得到的 token 序列
public ArrayList<Token> getToken(BufferedInputStream buffer) {
int cha = getChar(buffer);
while (cha != -1) {
if ((char) cha == '/') {
}
while ((char) cha == '\n' || Character.isWhitespace((char) cha)) {
}
if ((char) cha == '"') {
} else if ((char) cha == '=') {
} else if ((char) cha == '!') {
} else if ((char) cha == '>' || (char) cha == '<') {
} else if ((char) cha == '&' || ((char) cha == '|') {
} else if (Character.isLetter((char) cha) || (char) cha == '_') {
}
String tk = stringBuilder.toString();
switch (tk) {
case "main" ->
case "const" ->
case "int" ->
}
} else if () {
}
}
}
|
frontend/token/*
- Token 类是保存短语单元的对象类，保存了当前词的详细信息（类型、字符串、所在行数）
- TokenCategory 类是枚举类，用于保存所有可能出现的 token 种类
package frontend.token;
public enum TokenCategory {
IDENFR, INTCON, STRCON,
MAINTK, CONSTTK, INTTK, BREAKTK, CONTINUETK, VOIDTK, IFTK, ELSETK, FORTK,
NOT, AND, OR, PLUS, MINU, MULT, DIV, MOD,
GETINTTK, PRINTFTK, RETURNTK,
LSS, LEQ, GRE, GEQ, EQL, NEQ, ASSIGN,
SEMICN, COMMA, LPARENT, RPARENT, LBRACK, RBRACK, LBRACE, RBRACE
}
|
Compiler
在主运行类中调用方式如下，产生一个 ArrayList<Token> 供语法分析解析
ArrayList<Token> tokenList = TokenAnalyzer.getInstance().getToken(Logger.getSource());
StringBuilder tokens = new StringBuilder();
tokenList.forEach(i -> tokens.append(i.toString()));
Logger.printFile(tokens.toString(), "lexer");
|
语法分析设计
文件组织
src
|
|
+---frontend
| NodeParser.java
|
+---ast
AddExpNode.java
BlockItemNode.java
BlockNode.java
BTypeNode.java
CompUnitNode.java
CondNode.java
ConstDeclNode.java
ConstDefNode.java
ConstExpNode.java
ConstInitValNode.java
DeclNode.java
EqExpNode.java
ExpNode.java
ForStmtNode.java
FuncDefNode.java
FuncFParamNode.java
FuncFParamsNode.java
FuncRParamsNode.java
FuncTypeNode.java
IdentNode.java
InitValNode.java
LAndExpNode.java
LOrExpNode.java
LValNode.java
MainFuncDefNode.java
MulExpNode.java
NodeCategory.java
NumberNode.java
PrimaryExpNode.java
RelExpNode.java
StmtCategory.java
StmtNode.java
UnaryExpNode.java
UnaryOpNode.java
VarDeclNode.java
VarDefNode.java
|
具体设计
frontend/NodeParser
语法分析核心类，采用单例模式调用。通过逐个读取 token 的内容来进行语法树的构建。
private Token matchToken(TokenCategory tokenCategory)：读取 token 的函数，如果待取出的 token 和预想的种类不同就不进行取出，同时具有一定的错误处理能力
private Token matchToken(TokenCategory tokenCategory) {
if (token.getTokenCategory() == tokenCategory) {
Token temp = token;
getToken();
return temp;
} else {
switch(tokenCategory) {
case SEMICN ->
case RPARENT ->
case RBRACK ->
default -> {
Logger.process(StatusCode.UNEXPECTED_TOKEN_ERROR, "Match utils.error frontend.token " + token.getToken() + " at line " + lineCount);
Logger.exit(StatusCode.UNEXPECTED_TOKEN_ERROR);
}
}
}
return null;
}
|
public CompUnitNode compUnitNode()：解析 compUnit 节点，也就是语法树的根节点，通过逐层调用内部函数来进行语法成分的解析，每一个相对应的函数都会返回一个和函数名相同的类型的对象，其余函数完全按照语法树进行解析即可，不再占用篇幅展示
public CompUnitNode compUnitNode() {
ArrayList<DeclNode> declNodes = new ArrayList<>();
ArrayList<FuncDefNode> funcDefNodes = new ArrayList<>();
MainFuncDefNode mainFuncDefNode;
while (!peekAt(2).getTokenCategory().equals(TokenCategory.LPARENT)) {
declNodes.add(declNode());
}
while(!peekAt(1).getTokenCategory().equals(TokenCategory.MAINTK)) {
funcDefNodes.add(funcDefNode());
}
mainFuncDefNode = mainFuncDefNode();
outputs.add(new OutputRecord(NodeCategory.CompUnit));
return new CompUnitNode(declNodes, funcDefNodes, mainFuncDefNode);
}
|
frontend/ast/*
ast 软件包内包含了所有在核心类 NodeParser 中创建的节点类，同时对应了语法文档中的非终结符，文档中以较为复杂的 StmtNode，也就是语法中的 Stmt 作为示例进行说明
public class StmtNode {
private final LValNode lValNode;
private final ExpNode expNode;
private final ArrayList<ExpNode> expNodes;
private final BlockNode blockNode;
private final CondNode condNode;
private final ArrayList<StmtNode> stmtNodes;
private final ForStmtNode forStmtNode1, forStmtNode2;
private final Token tokenCategory;
private final String formatString;
private final StmtCategory stmtCategory;
private Token ifTk, elseTk, forTk;
private Token lp, rp;
private Token eq, semicolon, semicolon2;
private ArrayList<Token> comma;
private int line;
public StmtNode(LValNode lValNode, ExpNode expNode, Token eq, Token semicolon) { }
public StmtNode(ExpNode expNode, Token semicolon) { }
public StmtNode(BlockNode blockNode) { }
public StmtNode(CondNode condNode, ArrayList<StmtNode> stmtNodes,
Token ifTk, Token elseTk, Token lp, Token rp) { }
public StmtNode(CondNode condNode, ArrayList<StmtNode> stmtNodes,
ForStmtNode forStmtNode1, ForStmtNode forStmtNode2,
Token forTk, Token semicolon, Token semicolon2, Token lp, Token rp) { }
public StmtNode(CondNode condNode, ForStmtNode forStmtNode2, ArrayList<StmtNode> stmtNodes, Token lp, Token rp) { }
public StmtNode(Token tokenCategory, Token semicolon) { }
public StmtNode(ExpNode expNode, Token tokenCategory, Token semicolon) { }
public StmtNode(LValNode lValNode, Token tokenCategory, Token eq, Token lp,
Token rp, Token semicolon) { }
public StmtNode(ArrayList<ExpNode> expNodes, Token tokenCategory, String formatString,
ArrayList<Token> comma, Token lp, Token rp, Token semicolon, int line) { }
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
switch (stmtCategory) {
case LVal -> {
sb.append(lValNode);
sb.append(eq);
sb.append(expNode);
sb.append(semicolon);
}
case Exp -> { }
case Block -> { }
case If -> { }
case For -> { }
case Continue, Break -> { }
case Return -> { }
case GetInt -> { }
case Printf -> {
sb.append(tokenCategory).append(lp).append("STRCON ").append(formatString).append("\n");
for (int i = 0; i < expNodes.size(); i++) {
sb.append(comma.get(i)).append(expNodes.get(i));
}
sb.append(rp).append(semicolon);
}
}
sb.append("<").append(NodeCategory.Stmt).append(">\n");
return sb.toString();
}
}
|
在语法分析部分结束后，会形成一个以 CompUnitNode 为根节点的语法树，每个非叶节点都含有语法成分对应的子节点对象，输出语法树成分时调用递归的 toString 函数即可全部输出
Compiler
在主运行类中调用方式如下，返回一个 CompUnitNode 供错误处理和中间代码生成使用
NodeParser.getInstance().setTokenList(tokenList);
CompUnitNode compUnit = NodeParser.getInstance().compUnitNode();
Logger.printFile(compUnit.toString(), "parser");
|
错误处理设计
文件组织
src
|
+---frontend
| ErrorChecker.java
|
+---shortSymbol
Function.java
Symbol.java
SymbolTable.java
Var.java
|
具体设计
frontend/ErrorChecker
错误处理的核心类，采用单例模式调用。对可能出现错误的 ast 语法类和其父类，都编写了相应的 Error 函数，递归调用到指定的对象中检查是否存在错误，如对变量可能的重定义错误，设置了如下函数：
private void varDeclError(VarDeclNode node) {
node.getVarDefNodes().forEach(this::varDefError);
}
private void varDefError(VarDefNode node) {
if (existNow(node.getIdentNode().getIdent())) {
insert(new Error(node.getIdentNode().getLineCount(), ErrorType.NameRedefinition));
return ;
}
node.getConstExpNodes().forEach(this::constExpError);
tables.get(tables.size() - 1).add(node.getIdentNode().getIdent(),
new Var(node.getIdentNode().getIdent(), node.getConstExpNodes().size(), false));
if (node.getInitValNode() != null) {
initValError(node.getInitValNode());
}
}
|
其余的语法类同理，均为逐层调用函数进行错误的检查
frontend/shortSymbol/*
shortSymbol 软件包主要作用为建立错误处理时使用的符号表，该符号表包含的信息要少于代码生成时使用的符号表，结构也相对简单
SymbolTable 类是符号表类，创建一个可以存放当前层符号的表，内部符号使用 HashMap<String, Symbol> 进行管理，便于快速查找；同时提供了查找、插入等操作函数，供错误处理核心类调用对是否发生错误进行判断Symbol 类是符号类，仅包含标识符名，Var 和 Function 两个类对其进行继承，分别代表当前符号表管理区域中的变量声明和函数声明，两个类的对象都要存放在符号表的 HashMap 中管理
Compiler
在主运行类中调用方式如下，调用错误处理类单例进行解析并输出，如果存在错误则使用 Logger 终止编译程序
ErrorChecker.getInstance().compUnitError(compUnit);
Logger.printFile(ErrorChecker.getInstance().getErrors(), "error");
if (Logger.hasError) { Logger.exit(0); }
|
中间代码生成设计
文件组织
src
|
+---llvm
| LLCenter.java
| Visitor.java
|
+---identifier
| Identifier.java
|
+---symbol
| Symbol.java
| SymbolTable.java
|
+---type
| ArrayType.java
| BasicType.java
| BlockType.java
| LabelType.java
| PointerType.java
| Type.java
| TypeList.java
| VoidType.java
|
\---value
| ArrayValue.java
| BasicBlock.java
| Builder.java
| ConstantValue.java
| FuncFParam.java
| Function.java
| GlobalVar.java
| Use.java
| User.java
| Value.java
|
\---instruction
AllocaInstr.java
BinaryInstr.java
BitCastInstr.java
BranchInstr.java
CallInstr.java
GepInstr.java
IcmpInstr.java
InstrType.java
Instruction.java
JumpInstr.java
LoadInstr.java
ReturnInstr.java
StoreInstr.java
|
具体设计
llvm/LLCenter
LLCenter 类是生成中间代码时的中控类，编译过程中产生的 llvm 指令都会存放在中控类中，并指导进行输出，同时存放 llvm 产生的函数和全局变量，生成复杂的全局函数/变量表
public static void initFunction()：初始化函数表，添加四个库函数
public static void initFunction() {
Function getInt = new Function(TypeList.I32_TYPE, "getint", new ArrayList<>());
Function putint = new Function(TypeList.VOID_TYPE, "putint", new ArrayList<>() {{
add(new FuncFParam(TypeList.I32_TYPE, "0"));
}});
Function putch = new Function(TypeList.VOID_TYPE, "putch", new ArrayList<>() {{
add(new FuncFParam(TypeList.I32_TYPE, "0"));
}});
Function putstr = new Function(TypeList.VOID_TYPE, "putstr", new ArrayList<>() {{
add(new FuncFParam(new PointerType(TypeList.I8_TYPE), "0"));
}});
declareFunction.put("getint", getInt);
declareFunction.put("putint", putint);
declareFunction.put("putch", putch);
declareFunction.put("putstr", putstr);
}
|
llvm/Vistor
Vistor 类是 llvm 生成过程中重要的类，从语法树的根节点开始，开始逐级调用传递 Vistor 的 visit 函数，并在 visit 函数中解析语法结构，生成语法树对应的 llvm 语句。Vistor 类主要在遍历过程中存放当前处理的上下文信息，如是否在函数中、循环层数、基本块信息和跳转目标地址等。
private static final Visitor visitor = new Visitor();
private static int blockCount = 0;
private static int paramCount = 0;
private static int loopDepth = 0;
private BasicBlock currentBlock = new BasicBlock(this);
private ArrayList<BasicBlock> continueBlocks = new ArrayList<>();
private ArrayList<BasicBlock> breakBlocks = new ArrayList<>();
private Function currentFunction;
private SymbolTable currentTable = new SymbolTable();
private final HashMap<String, GlobalVar> globalVarTable = LLCenter.globalVarTable;
private final HashMap<String, Function> functionTable = LLCenter.functionTable;
public final Builder builder = Builder.getInstance();
private boolean isGlobal = true;
private boolean inFuncDef = false;
private boolean isFillValue = false;
|
llvm/identifier/*
identifier 软件包只含有一个 Identifier 类，存放 llvm 指令的序号、标识等信息，标识的产生并不重复，由 Vistor 在遍历语法树的过程中产生
llvm/symbol/*
symbol 软件包存放了代码生成过程中用到的符号结构和符号表结构，只有变量/常量会使用此类，当 vistor 发现一个对象的定义时就创建一个 Symbol 对象存放在 vistor 携带的 SymbolTable 实例中
llvm/type/*
type 软件包包含了llvm 指令对象的种类，包含基本类型（i32、i1）、指针类型（i32*）、数组类型（[a x i32]）和空类型，每一个 llvm 的 value 都拥有其对应的 type
llvm/value/*
value 软件包包含了 llvm 的绝大部分指令，“万物皆 value”，本编译器首先将 value 的指令划分出来形成一个独立的软件包 instruction，其余的 value 直接形成文件（数组量ArrayValue、基本块BasicBlock、常值量ConstantValue、函数形参FuncFParam、 函数Function、全局变量GlobalVar），并形成一个工厂类Builder负责在 vistor 遍历时产生 llvm 指令插入到 LLCenter 中。instruction 软件包包含了 llvm 最终生成时的所有可见指令，继承 Instruction 类，并持有一个枚举类选择指令的类型与功能，最后重写指令的 toString 方法便于最后部分对指令进行输出
public enum InstrType {
ADD("add"), SUB("sub"), MUL("mul"), DIV("sdiv"), REM("srem"),
BR("br"), CALL("call"), RET("ret"),
ALLOCA("alloca"), STORE("store"), LOAD("load"), GEP("getelementptr"),
ZEXT("zext"),
EQ("icmp eq"), NE("icmp ne"), SGT("icmp sgt"),
SGE("icmp sge"), SLT("icmp slt"), SLE("icmp sle"),
ICMP("icmp"), AND("and"), OR("or"), NOR("nor"), NOT("not"), BITCAST("bitcast"),
;
private final String typeName;
InstrType(String typeName) { this.typeName = typeName; }
public String toString() { return typeName; }
}
|
frontend/ast/*
- 语法树类中在 llvm 部分为每个语法结构都添加了
visit 函数用于访问并生成 llvm 代码，以条件表达式为例，进行短路求值的构造：
public Value visit(Visitor visitor, BasicBlock thenBlock, BasicBlock elseBlock) {
return lOrExpNode.visit(visitor, thenBlock, elseBlock, visitor.getBlock());
}
public Value visit(Visitor visitor, BasicBlock thenBlock, BasicBlock elseBlock, BasicBlock andBlock) {
BasicBlock currentBlock = andBlock;
visitor.setBlock(currentBlock);
if (or == null) {
Value andValue = lAndExpNode.visit(visitor, thenBlock, elseBlock, andBlock);
} else {
BasicBlock childAndBlock = visitor.builder.buildBlockBegin(visitor.getCurrentFunction());
visitor.getCurrentFunction().pushBlock(childAndBlock);
visitor.setBlock(currentBlock);
lAndExpNode.visit(visitor, thenBlock, childAndBlock, andBlock);
Objects.requireNonNull(lOrExpNode).visit(visitor, thenBlock, elseBlock, childAndBlock);
}
return null;
}
public Value visit(Visitor visitor, BasicBlock thenBlock, BasicBlock elseBlock, BasicBlock eqBlock) {
BasicBlock currentBlock = eqBlock;
visitor.setBlock(currentBlock);
Value eqValue = eqExpNode.visit(visitor);
if (and == null) {
BranchInstr finalBranch = visitor.builder.buildBranch(eqValue, thenBlock, elseBlock, visitor.getBlock());
} else {
BasicBlock childEqBlock = visitor.builder.buildBlockBegin(visitor.getCurrentFunction());
visitor.getCurrentFunction().pushBlock(childEqBlock);
visitor.setBlock(currentBlock);
BranchInstr finalBranch = visitor.builder.buildBranch(eqValue, childEqBlock, elseBlock, visitor.getBlock());
Value andExpValue = Objects.requireNonNull(lAndExpNode).visit(visitor, thenBlock, elseBlock, childEqBlock);
}
return null;
}
|
目标代码生成
文件组织
src
|
+---mips
| Builder.java
| MipsCenter.java
| RegisterFile.java
|
+---data
+---instr
| AbstractInstr.java
| BranchDInstr.java
| CalDInstr.java
| CalSInstr.java
| DataRecord.java
| DataTag.java
| InstrType.java
| JumpInstr.java
| LabelInstr.java
| MemSInstr.java
| PseudoInstruction.java
| Syscall.java
| UtilsSInstr.java
|
\---operands
Imm.java
Label.java
Operand.java
Register.java
|
具体设计
mips/MipsCenter
和中间代码生成类似，在目标代码生成时也设置了一个中控类，用于存放所有的 mips 指令和编译时的信息，其功能比 LLCenter 更复杂，分成了几个区段，在生成 mips 指令时进行辅助
private final ArrayList<DataRecord> dataSegment = new ArrayList<>();
private final HashMap<GlobalVar, DataRecord> tagMap = new HashMap<>();
private static int dataOffset;
private static int gpValue = 0x10008000;
private static int spValue = 0x7fffeffc;
private final ArrayList<AbstractInstr> instructions = new ArrayList<>();
public ArrayList<DataRecord> getDataSegment() { return dataSegment; }
public void pushData(GlobalVar globalVar, DataTag data) { }
public void pushFunction() { }
public void pushInstr(String comment,AbstractInstr instruction) { }
public void pushInstr(AbstractInstr instruction, String blockLabel) { }
private final LinkedHashMap<Value, Integer> stacks = new LinkedHashMap<>(){{ put(new Value(TypeList.I1_TYPE, null), 4); }};
public boolean findStackValue(Value target) { return stacks.containsKey(target); }
public void pushStack(Value target) { }
private void flushStack() { }
public int getStackSize() { }
public int getStackOffset(Value target) { }
public final RegisterFile registerFile = RegisterFile.getInstance();
public Operand dispatchRegister(Value patch, boolean needLoad, boolean... inStorePointer) { }
private void loadStore(Pair<Register, Value> storePair, boolean isLoad) { }
public void writeRegisterBack() { }
public String getMips() { }
|
mips/RegisterFile
- 在生成目标代码指令过程中对寄存器进行管理的类，模拟一个真正的寄存器，记录其中正在被占用的寄存器和可释放、申请的寄存器
public void initial() { }
public Register dispatchIdleRegister(Value value) { }
public Register dispatchTargetRegister(Value value, Register register) { }
public Register recycleRegister(Value value) { }
public Register recycleRegister(Register recycle) { }
public Pair<Register, Value> recycleRegister() { }
public Register pickOut() { return useList.getFirst(); }
public boolean hasIdle() { return !idles.isEmpty(); }
public Value getValue(Register register) { return dispatches.getOrDefault(register, null); }
public Register getRegister(Value value) { }
public HashMap<Register, Value> getDispatches() { return dispatches; }
|
mips/operands/*
operands 软件包存放的是 mips 指令的操作数类，可以分为立即数（Imm）、寄存器（Register）和标签（Label）三类，它们在不同的指令中出现，不可直接换用
操作数是指令内部 value 的具象，也就是承载着 llvm 的 value 的一个对象，我们将多种 llvm 指令转化为 能够表达同等意思的 mips 指令，靠的就是 mips 指令对这些操作数的动作。例如一个 Binary 的 llvm 指令可以将其两个运算的 value 提取出来当作两个 operands，并生成一条同样的运算类的 mips 指令，而运算的两个操作数就是这两个 value，由此就简单地实现了 llvm 到 mips 的转化。
mips/instr/*
instr 软件包存放的是 mips 指令的种类，这些类的对象就实际对应一条可执行的 mips 指令，均继承自 AbstractInstr 类，再额外实现相关的字段
llvm/value/instruction/*
- llvm 的每一条指令都需要转化成对应的 mips 指令，所以在每个 llvm 指令类中都新建
generateMips 方法，实现从 llvm 到 mips 的转化
以 BinaryInstr 为例进行转换：
@Override
public void generateMips() {
Operand lhs = MipsCenter.getInstance().dispatchRegister(operands.get(0).getUseValue(), true);
Operand rhs = MipsCenter.getInstance().dispatchRegister(operands.get(1).getUseValue(), true);
Operand rd = MipsCenter.getInstance().dispatchRegister(this, false);
if (lhs instanceof Register && rhs instanceof Register) {
switch (instrType) {
case ADD, SUB ->
case EQ ->
}
} else if (lhs instanceof Register && rhs instanceof Imm) {
} else if (lhs instanceof Imm && rhs instanceof Register) {
} else {
assert lhs instanceof Imm;
int lhsImm = ((Imm) lhs).getImmValue();
int rhsImm = ((Imm) rhs).getImmValue();
int res = 0;
switch (instrType) {
case ADD -> res = lhsImm + rhsImm;
case SUB -> res = lhsImm - rhsImm;
}
MipsCenter.getInstance().pushInstr(this.toString(), new PseudoInstruction(LI, (Register) rd, new Imm(res)));
}
}
|
代码优化
本编译器未进行代码优化，本部分无相关内容
