Compiler-编译设计文档

jkm Lv2

BUAA-Compiler-2023


前言

北航计算机学院2021级编译技术课设的设计文档,代码见:BUAA-Compiler-2023-Fall

一、参考编译器

Pascal编译器主要由词法分析、语法分析、语义分析、代码生成、优化和链接等模块组成,以下是Pascal编译器的总体结构和各个模块的功能:

  1. 词法分析器:负责将源代码分解为词法单元,如标识符、关键字、运算符等。词法分析器通常使用有限自动机或正则表达式来识别词法单元,并将它们转换成内部表示形式。

    1
    2
    3
    procedure insymbol;  {reads next symbol}
    procedure nextch;
    ...
  2. 语法分析器:将词法单元转换成语法树,以便后续处理。语法分析器通常使用递归下降分析、LR分析等算法来构建语法树。

    1
    2
    3
    4
    procedure constdec;
    procedure typedeclaration;
    procedure variabledeclaration;
    ...
  3. 语义分析器:检查语法树的语义正确性,如类型检查、作用域检查等。语义分析器将对语法树进行遍历,查找并修正语义错误。

    1
    2
    3
    procedure errormsg;
    procedure fatal( n: integer );
    ...
  4. 代码生成器:将语法树转换为目标机器的可执行代码。代码生成器将语法树转换成目标机器的汇编或机器码。

在接口设计方面,Pascal编译器可能提供命令行接口或集成开发环境(IDE)界面,用于用户输入源代码并获取编译结果。用户可以通过命令行参数或IDE菜单来指定编译选项和目标平台等参数。文件组织方面,编译器通常会将中间代码或目标代码输出到特定格式的文件中,以便后续链接、优化或执行。

除了Pascal编译器,我参考的更多的其实是理论课程的课件和往届学长的博客与代码,再加上与同学的交流,在此基础上完成了我的编译器。

二、编译器总体设计

2.1 总体结构

本编译器采用目前静态编译器最主流的三端设计:前端(Frontend)、中端(Middle)、后端(Backend)。这三端分别有如下工作:

  • 前端:词法分析、语法分析、错误处理、符号表的建立
  • 中端:中间代码生成(LLVM),部分代码优化
  • 后端:目标代码生成

2.2 接口设计

上述编译阶段各自独立工作,在主类Compiler里串连在一起,其中各工作阶段之间传递信息如下所示:

  • 词法分析 -> 语法分析:Lexer产出一个ArrayList<Token>,作为Parser类的输入,其中Token是一个词法标志,具有类型、行号等信息。
  • 语法分析 -> 中间代码生成:Parser负责建立语法树,并将语法树的根节点CompUnit返回,作为中间代码架构器IrBuilder的输入。
  • 中间代码生成 -> 目标代码生成IrBuilder在中间代码生成阶段同样建立一个树形结构,其中IrModule是LLVM的最上层单元,也是该树的根节点,将IrModule作为输入传入目标代码生成器MipsBuilder

除了以上各编译阶段之间的接口设计,在各阶段内部还设计有若干接口(Interface)以更好地实现功能,下面将依次阐述:

  • 语法分析
    依据文法,凡是具有共性的文法单元均可建立接口,从上到下依次是:
    • 块内元素:BlockItem
    • 语句:Stmt
    • 初值:InitialValue
    • 单目表达式的组成部分:UnaryBase
  • 中间代码生成
    • 指令:Instruction
  • 目标代码生成
    • 指令:MipsInstruction

2.3 文件组织

本编译器整体文件树如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
├─Backend
├─Instrctions
├─Macro
└─ macro...
└─instructions...
├─MipsSymbolManager
├─MipsSymbolTable
├─MipsValue
├─MipsBuilder
├─MipsInstrType
├─MipsModule
└─RegManager
├─Frontend
├─Lexer
├─Lexer
├─Token
├─Parser
├─Error
├─Parser
├─SymbolTableManager
├─FuncSymbol
├─Symbol
├─SymbolTable
├─SymbolType
└─SyntaxComponents
└─syntax components...
├─Middle
├─IrComponents
└─ir components...
└─IrBuilder
└─Compiler

三、词法分析设计

3.1 读入文件

词法分析是编译器工作的首个阶段,首先要将待编译的源文件读进编译器。经过我和同伴的交流,读入文件有两种方式,其一是一次性将程序读入编译器,这应该也是大多数人采用的方式;其二是我本人采用的由源文件逐行读入进编译器。

这两种方式可以说是各有千秋,若是逐行读入程序,则每个词法单元的行号是不需要单独考虑的,不会受到字符串里'\n'的影响;但由于每一行的字符串单独处理,需要时常考虑字符串下标是否越界的情况。而若是整体读入源程序,则不需要考虑字符串下标越界的情况,但是对于换行的处理就复杂很多,要屏蔽掉注释与字符串里的'\n'

3.2 架构

3.2.1 Token

设计Token类来代表词法单元,记录下该token的名称、种类、行号,并对这三个属性分别提供get方法。

3.2.2 Lexer

设计Lexer类(词法分析器),其属性有:

1
2
3
4
5
6
7
8
9
10
private String input;   //输入,单行程序
private int pos = 0; //处理到了输入的哪个字符
private final String[] keywords; //关键词集合,在初始时已确定
private final String[] operator; //操作符集合,在初始时已确定
private final String[] brackets; //括号集合,在初始时已确定
private final String[] punctuation; //标点集合,在初始时已确定
private final String[] whitespace; //空白符集合,在初始时已确定
private final ArrayList<Token>; //解析出的token集合
private boolean isSingleLineComment; //判断是否处于单行注释中
private boolean isMultilineComment; //判断是否处于多行注释中

工作流程:遍历input,判断pos位置上的字符。可以进入以下分支:关键词、标识符、数字、运算符、括号、标点符号。其中关键词与标识符的first集有重叠,可以将单词解析完以后再进行判断,其余分支的first集无重叠。整体流程参考理论课程内容。

方法:根据上述不同分支,提供以下方法

1
2
3
4
5
6
7
8
9
public String getWord()     //解析一个单词
public String getNum() //解析一个数字
public Token dealOperator(int line) //处理操作符
public String getString() //解析一个字符串
public void initializeMap() { //初始化token与type的映射
tokenTypeMap = new HashMap<>();
tokenTypeMap.put("Ident", "IDENFR");
......
}

3.3 编码完成之后的修改

正如同之前所说,我读入文件的方式是逐行读入,Lexer的input属性是源程序的一行,所以在逐个字符解析input的时候需要特别注意下标越界的问题,否则诸如input.charAt(pos)这样的代码就有可能抛出异常。

以下是一个需要特别考虑的例子,这个例子在词法分析、语法分析甚至期中考试都没有遇到,但在代码生成二中耗费了我很长时间去debug。

1
2
3
4
if (a <
b) {
// code
}

四、语法分析

4.1 架构

4.1.1 Parser

属性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
private final ArrayList<Token> tokens; //Lexer的输出,token集合
private int pointer; //与tokens配合,判断当前处理到哪个token
private String curToken; //当前处理的token
private final ArrayList<String> syntaxOutput; //输出集合
private final ArrayList<Error> errorOutput; //错误处理的输出
//两个临时集合,目的在后续会详细解释
private final ArrayList<String> tmpOutput;
private final ArrayList<Error> tmpErrorOutput;

//有关符号表的属性
private static final HashMap<Integer, SymbolTable>
symbolTables; //所有的符号表
private int currentTableId; //当前表的id
private int fatherTableId; //父级表的id
private int countOfTable; //符号表的数量

//一些状态标记,有时需要跨函数判断
private int currentFuncType; //当前函数的类型,0:void,1:int
private boolean canBorC; // 可不可以break或continue
private boolean timeStop;

4.1.2 SyntaxComponents 语法成分

文法中有很多种语法成分,一眼望去让人非常眼花缭乱,在语法分析之前我们有必要先对诸多语法成分进行分类和抽象。

4.1.2.1 Exp

各种Exp,如AddExp、MulExp等等,占据了语法成分的很大一部分,然而我们不难发现各种表达式都具有极高的相似度。例如AddExp在文法中:

1
AddExp → MulExp | AddExp ('+' | '−') MulExp

其他表达式的解析文法类似于AddExp,并且其是左递归的,可以将其改写为:

1
AddExp → MulExp {('+' | '−') MulExp}

所以可以将所有表达式抽象为如下形式:

1
Exp -> Base {('op1' | 'op2' |...) Base}

故建立一个ExpTemplate类(表达式模版),如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class ExpTemplate {
//此表达式实际有的操作符
protected ArrayList<String> opList;
//构成表达式的操作数
protected ArrayList<ExpTemplate> bases;
//该类表达式允许有的操作符
protected ArrayList<String> stdOpList;

public ExpTemplate()
//添加op之前要验证op在不在stdOpList里
public void addOp(String op)

public void addBase(ExpTemplate base)

......
}

让所有的表达式都继承这个父类,只需要重写构造函数,在初始时就加入该类表达式应该有的操作符即可。例如:

1
2
3
4
5
public AddExp() {
super();
super.stdOpList.add("+");
super.stdOpList.add("-");
}

如此便省去了我们许多编码的时间。

4.1.2.2 InitVal 初值

观察语法成分,ConstInitVal与InitVal除了需要判断表达式是否为常量外,没有区别,故可以建立一个接口将二者统一起来,并且后续在中间代码生成阶段需要获取初值的表达式时,也可以不用区分二者。可以建立如下接口:

1
2
3
4
5
public interface InitialVal {
Exp getExp(); //普通常量
ArrayList<Exp> getExps(); //一维数组
ArrayList<ArrayList<Exp>> getExpArrays(); //二维数组
}
4.1.2.3 Def与Decl

Def、ConstDef与ConstDecl也是文法中的两对成分,而他们之间除了是否是常量以外也没有任何区别,所以不用对此进行区分,只需要在属性中加入一个isConst即可

4.1.2.3 Stmt与BlockItem

各种Stmt与BlockItem只需建立一个接口即可,但他们之间并没有什么方法可以抽象,但是后续中间代码生成时需要使用。

4.1.2.4 其他

其他语法成分没有什么可以进一步抽象的,为每一个成分单独建类即可。

4.1.3 Error

顾名思义,代表一个错误,为错误处理而建立的类,记录下该错误所在的行号与类型。

1
2
3
4
5
6
7
8
9
10
public class Error {
private final int line;
private final char errorType;

public Error(int line, char errorType)

public int getLine()

public char getErrorType()
}

4.2 符号表

如果只是单纯的建立语法树,那么符号表并非必须,但后续的中间代码生成以及错误处理部分,就需要符号表的帮助了。

4.2.1 Symbol

有如下几种情况需要建立一个symbol:

  • ConstDef
  • Def
  • FuncDef

并且Symbol应当存储有以下信息(此处仅考虑错误处理时的设计,后续中端代码生成阶段还需要增量开发):

  • 行号(错误处理需要输出)
  • 所在的符号表
  • 符号名称
  • 种类
  • 是否为常量

故Symbol的属性有:

1
2
3
4
5
6
7
8
public class Symbol {
private final int id;
private final int line;
private final SymbolTable symbolTable;
private final String token;
private final SymbolType type;
private final boolean isConst;
}

上述代码中出现的SymbolType为一枚举类,记录符号的类型,如下所示:

1
2
3
4
5
6
7
public enum SymbolType {
VAR, //普通变量
ARRAY1, //一维数组
ARRAY2, //二维数组
FUNC, //函数
ERROR //错误
}

4.2.2 SymbolTable

本编译器采用的符号表是树形符号表,而非理论课所讲的栈式符号表,树形符号表更适合递归下降的处理方式,故采用。

首先依旧是明确什么时候需要建立一个符号表:

  • 程序最开始时
  • 进入到一个block时

只有以上两点需要建立符号表。其次是符号表需要记录的信息,如下所示:

  • id(符号表的标识)
  • 父表(结束一个block时要退回到父表)
  • 符号集合

将上述分析过程转换为代码,即:

1
2
3
4
5
public class SymbolTable {
private final int id;
private final SymbolTable fatherTable;
private final HashMap<String, Symbol> symbols;
}

最后是功能分析,符号表的主要功能主要有两点:

  • 增加符号(如果重复添加就报b类错误)
  • 查找符号(如果本层没有就要去父表继续查找)

转化为代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class SymbolTable {
// 属性...

public void addSymbol(Symbol symbol) {
if (symbols.containsKey(token)) {
//转错误处理
} else {
// add symbol
}
}

public Symbol findSymbol(String token) {
//从自己开始查
currentTable = this;
while (/*当前表不为null*/) {
if (currentTable.containsSymbol(token)) {
return currentTable.getSymbol(token);
}
//在当前表没找到就去父表继续查
currentTable = currentTable.getFatherTable();
}
//没找到
return null;
}
}

4.3 部分实现细节

4.3.1 整体思路

整体的实现思路是为每一条文法都建立一个方法,在方法内部不断调用next()方法读取下一个Token。并且各个方法之间存在着递归下降的关系,之前也提到过已经在设计部分将左递归文法改写完毕,所以不存在无法终止的现象,这一点与理论课程及其他编译器的处理类似,此处不过多赘述。以下针对一些特殊情况简要介绍一下本人的处理思路。

4.3.2 多产生式的处理

对于多产生式,如果是各个产生式的First集不存在交集的情况,只需要根据各个产生式的First集判断然后进入不同的分支即可,对于绝大多数的多产生式,我们都可以通过预读一个token的方法来解决。故需要实现一个getNextToken()方法,注意此处只能预读而不能将pointer真的增加。:

1
2
3
private String getNextToken() {
return tokens.get(pointer + 1).getToken();
}

而对于个别情况,其产生式的First集是有交集的,例如:

1
2
3
Stmt → LVal '=' Exp ';'    // FIRST={Ident}
| LVal '=' 'getint''('')'';' // FIRST={Ident}
| [Exp] ';' // FIRST={(,Number,Ident,+,-,!}

本编译器处理这种情况采取的方法整体借鉴教程,但实现细节不太一样。此前提到过,我在Parser类里开了几个全局变量:

1
2
3
4
5
6
7
public class Parser {
// ...
private final ArrayList<String> tmpOutput;
private final ArrayList<Error> tmpErrorOutput;
private boolean timeStop;
// ...
}

其中,timeStop是一个状态标记,当解析到一个标识符(上述三条产生式的First集的交集)时,就将timeStop置为true,意为此时模拟一种暂停的情况,是一个“试探”的过程。然后调用parseExp()方法,注意此时解析带来的所有语法输出不能直接加入syntaxOutput,应该先加入一个临时的集合中,因为如果最后发现正在解析的不是Exp而是LVal,再去删除这部分语法输出就会很麻烦,错误处理输出同理。

1
2
3
4
5
6
7
private void addSyntaxOutput(String s) {
if (!timeStop) {
syntaxOutput.add(s);
} else {
tmpOutput.add(s);
}
}

解析完以后观察curToken,若是';',就说明是[Exp] ';'这条文法,就将临时集合里的输出加入正式结果;若是 '=',就说明是LVal '=' Exp ';'或者LVal '=' 'getint''('')'';',再进行进一步判断就很简单了。

4.3.3 进入一个作用域的流程

1
2
3
4
5
6
7
8
public class Parser {
// ...
// 为处理符号表设计的全局变量
private int currentTableId; // 当前表的id
private int fatherTableId; // 父级表的id
private int countOfTable; // 表的数量
// ...
}

进入一个作用域(block),有如下几件事需要做:

  1. 将全局变量中的fatherTableId赋值为当前符号表的id
  2. 建立属于本作用域的符号表
  3. 将currentTableId赋值为新建立的表的id
  4. 语法分析
  5. 将currentTableId重新赋为fatherTableId

五、错误处理

本编译器所有错误处理均是在语法分析过程中实现,没有将其作为一个单独的步骤。

5.1 非法符号

  • 错误类别码:a
  • 解释:格式字符串中出现非法字符报错行号为FormatString所在行数。
  • 处理思路:在语法分析中实现,遍历到printf时检查一下formatString是否符合要求即可。只是对字符串进行处理,较为简单,不多赘述。

5.2 名字重定义

  • 错误类别码:b
  • 解释:函数名或者变量名在当前作用域下重复定义。注意,变量一定是同一级作用域下才会判定出错,不同级作用域下,内层会覆盖外层定义。报错行号为 Ident所在行数。
  • 处理思路:在parseDef/parseConstDef中实现,当定义一个新的标识符时,就要加入符号表,在加入符号表的时候检查是否重复,具体代码如4.2.2所示

5.3 未定义的名字

  • 错误类别码:c
  • 解释:使用了未定义的标识符报错行号为 Ident 所在行数。
  • 处理思路:在语法分析中实现,如4.2.2 SymbolTable一节中代码所示,当我需要查找符号表时,自底向上查找,如果没有找到就说明使用了未定义的名字。

5.4 函数参数个数不匹配

  • 错误类别码:d
  • 解释:函数调用语句中,参数个数与函数定义中的参数个数不匹配。报错行号为函数调用语句的函数名所在行数。
  • 处理思路:单独为函数型符号设置一个类,让其继承Symbol类,除了常规symbol记录的信息外,还需记录函数的类型,参数。代码如下所示:
    1
    2
    3
    4
    5
    public class FuncSymbol extends Symbol {
    private final int funcType; // 0: void, 1: int
    // 只存储参数的类型
    private final ArrayList<SymbolType> params;
    }
    由于编译器只需要校验参数的类型、个数,所以我只需要存储参数的类型即可。在调用函数时,也就是parseLval()这个函数中,需要解析小括号内有多少个逗号,参数的个数应该是逗号的个数+1。注意这里不能直接解析参数的个数,因为这样是要以右括号为循环终止条件的,右括号有可能缺失。

5.5 函数参数类型不匹配

  • 错误类别码:e
  • 解释:函数调用语句中,参数个数与函数定义中的参数类型不匹配。报错行号为函数调用语句的函数名所在行数。
  • 处理思路:类比5.5 函数参数个数不匹配这一部分,只要在检查参数个数的时候再检查类型就行了。

5.6 无返回值的函数存在不匹配的return语句

  • 错误类别码:f
  • 解释:报错行号为 ‘return’ 所在行号。
  • 处理思路:如此前代码所示,在Parser中开一个全局变量currentFuncType,在parseFuncDef()中为currentFuncType赋值,如果是void就是0,是int就是1。在parseReturnStmt(),如果当前currentFuncType = 0,并且如果return之后的token的类别是IdentIntCon或者是UnaryOp,那么就需要说明存在f类错误。

5.7 有返回值的函数缺少return语句

  • 错误类别码:g
  • 解释:只需要考虑函数末尾是否存在return语句,无需考虑数据流。报错行号为函数结尾的’}’ 所在行号。
  • 处理思路:类比上一类错误,在函数解析完后,如果currentFuncType = 1,并且block的最后一条语句不是return,就要报错。

5.8 不能改变常量的值

  • 错误类别码:h
  • 解释LVal为常量时,不能对其修改。报错行号为 LVal 所在行号。
  • 处理思路:在赋值语句与getint语句时,检查LVal所对应的Symbol是否是常量,如果是的话,报错。

5.9 缺少分号

  • 错误类别码:i
  • 解释:报错行号为分号前一个非终结符所在行号。
  • 处理思路:这类错误非常常见,没有什么特别好的处理办法,只能在逐个token解析时加以判断。

5.10 缺少右小括号

  • 错误类别码:j
  • 解释:报错行号为右小括号前一个非终结符所在行号。
  • 处理思路:在逐个token解析时加以判断。

5.11 缺少右中括号

  • 错误类别码:k
  • 解释:报错行号为右中括号前一个非终结符所在行号。
  • 处理思路:在逐个token解析时加以判断。

5.12 printf中格式字符与表达式个数不匹配

  • 错误类别码:l
  • 解释:报错行号为 ‘printf’ 所在行号。
  • 处理思路:类似于函数调用的实参问题,统计逗号的个数,再与%d的个数相比较,对不上就报错。

5.13 在非循环块中使用break和continue语句

  • 错误类别码:m
  • 解释:报错行号为 ‘break’ 与 ’continue’ 所在行号。
  • 处理思路:全局变量开了一个canBorC,意思是判断是否可以出现breakcontinue。当解析到if语句或者for语句时,就将该全局变量设为真,解析结束就将其置为假。

六、中端代码生成

综合多方面考虑,我选择了LLVM作为本编译器的中端代码。选择LLVM作为中端代码有诸多好处,比如课程网站有详细的教程可以参考,课程组提供评测机检验正确性,省去了自己设计四元式的时间,还有往届学长的思路可以参考。并且LLVM本身的代码结构也和mips比较相近,就拿我本人而言,在生成了LLVM以后,只花了半个礼拜就顺利通过了mips的测评。下面开始介绍一些相关设计。

6.1 架构

6.1.1 总体思路

中端代码的总体架构参考教程介绍,Module->Function->Basic Block->Instruction。遍历语法分析阶段产生的语法树,自顶向下建立一个中端代码树,如果语法分析阶段建立的语法树有序且正确的话,中端代码生成阶段再建立一个中端语法书应该是不难的。此处还需特别说明一下,中端代码所用到的符号表即为语法分析阶段所建立的符号表,并没有针对LLVM新建一张,而是在之前的符号表上进行增量开发,但后端代码生成需要有一张自己的符号表。

中端代码必须要对符号表进行一些必要的修改,举个例子来说:

1
2
3
4
5
6
7
const int a = 1;
int main() {
int b = a;
printf("%d", b);
const int a = 2;
return 0;
}

对于上述代码,如果依据我们此前的符号表,b的正确输出应该是1,但实际上会被输出成2,因为我们的符号表找一个symbol是自底向上查找的,且不会考虑symbol出现的顺序,符号表在最底层找到了a,那么就会把最底层的a返回。所以我们在遍历符号表的时候必须要考虑symbol出现的顺序,可以对符号表作如下修改:

1
2
3
4
5
6
7
8
9
10
11
public class Symbol {
// 记录总的symbol的数量
private static int SymbolCnt = 0;
// 为每个symbol设置一个id,即出现的顺序,id = SymbolCnt++
private final int id;
// ...
}

public class SymbolTable {
public Symbol findSymbolByOrder(String token, int targetId)
}

SymbolTable中提供按顺序查找symbol的方法,传入targetId,即当前处理的symbol的id,判断symbol的token相等的同时还要判断查找出来的symbol的id要小于targetId,两个条件都满足才能说明找到了正确的symbol

此外,对于每个中端代码成分,都提供toLlvm方法,返回一个字符串,可以输出LLVM代码。

6.1.2 Value

Value是LLVM中非常重要的一个概念,LLVM中几乎所有的结构都可以认为是一个Value,所以对于Value的设计是非常重要的。经过笔者本人惨痛的教训,经过几轮缝缝补补,终于得出了最终版的Value,需要记录的信息如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Value {
private String name;
/**
* 1. i32
* 2. i32*
* 3. i32** 函数传参传过来的一维数组
* 4. [n x i32]*
* 5. [m x [n x i32]]* 正常声明的二维数组
* 6. [n x i32]** 函数传参传过来二维数组
* 7. i1
*/
private int varType = 1;
private int row = 0;
private int col = 0;

/* 需要提供三种构造方法 */
// 普通变量
public Value(String name, int varType)
// 一维数组
public Value(String name, int varType, int col)
// 二维数组
public Value(String name, int varType, int row, int col)
}

其中最重要的是Value的类型,教程中并没有地方显式的说明,需要自己总结。经总结后,一共有以下七种类型:

  1. i32:整数类型
  2. __i32*__:整数类型的地址
  3. __i32**__:函数传参传过来的一维数组
  4. __[n x i32]*__:正常声明的一维数组
  5. __[m x [n x i32]]*__:正常声明的二维数组
  6. __[n x i32]**__:函数传参传过来二维数组
  7. __i1__:条件变量

6.1.3 IrBuilder

作用类似语法分析阶段里的Parser,提供以下方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 最上层的build方法,按全局变量、函数、基本块、指令的顺序依次调用各成分的build方法
public IrModule build()

// 构建全局变量的中间代码
public IrGlobalVar buildGlobalVar(Def globalDef)

// 构建函数的中间代码
public IrFunction buildFunction(FuncDef funcDef)

// 构建主函数的中间代码
public IrFunction buildMainFunction(MainFuncDef mainFuncDef)

// 构建基本块的中间代码
public void buildBasicBlock(String label)

// 构建指令的中间代码
public void buildInstruction(BlockItem blockItem)

具体到不同的语法成分,还需要单独的提供转化成LLVM的方法,此处不多赘述。

6.1.4 IrComponents

6.1.4.1 IrGlobalVar

IrGlobalVar指的是LLVM里的全局变量,需要记录以下信息:

1
2
3
4
5
6
7
8
9
10
public class IrGlobalVar {
private final int type; // 0: 普通变量,1:一维数组,2:二维数组
private final String token;
private boolean isConst;
private int dim1;
private int dim2;
private boolean hasInitialValue = false;
private InitialVal initialVal;
private final SymbolTable symbolTable;
}

6.1.4.2 IrFunction

IrFunction指的是LLVM里的Function部分,根据LLVM里一切皆Value的原则,我们让IrFunction继承Value,需要记录以下信息:

1
2
3
4
5
6
public class IrFunction extends Value {
private final String funcName;
private final int funcType; // 0: void, 1: int
private final ArrayList<Value> params;
private final ArrayList<BasicBlock> basicBlocks;
}

6.1.4.3 BasicBlock

依旧是让BasicBlock继承Value,需要记录以下信息:

1
2
3
4
public class BasicBlock extends Value {
private final String label;
private final ArrayList<Instruction> instructions;
}

6.1.4.4 IrInstructions

对于每一种Instruction,都让其继承Value,具体的属性设置完全依照教程中提供的指令集,值得一提的是,指令的属性能用Value表示的一定不要用String,因为指令归根到底也是一个ValueString能表示的信息非常有限,我们对于任何一个指令,当这条指令被当作Value看待时,可能不止要知道指令的名字,也要知道类型等其他信息。这个时候我们需要让指令的Result代表整条指令的Value,所以需要重写Value中的一些方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
@Override
public int getVarType() {
return super.getResult().getVarType();
}

@Override
public String typeToLlvm() {
return super.getResult().typeToLlvm();
}

@Override
public int getRow() {
return super.getResult().getRow();
}

@Override
public int getCol() {
return super.getResult().getCol();
}

6.2 实现难点

6.2.1 跳转标签

IfFor语句中要用到大量的跳转指令,但跳转的标签很有可能是不确定的,就比如分支语句中,至少要设置两个标签,一个是进入分支的标签,另一个if结束的标签,但是我们并不知道是否会有else的标签,所有就不能提前开好这些标签。

这里我们可以运用java中引用的一个特性,即java中对象之间的赋值均为浅拷贝。我们可以将未知跳转标签的跳转指令加进一个容器中,当处理到了目标基本块的时候就把他们都回填成该基本块的标签。

6.2.2 GEP指令

我们在LLVM中操作数组时,不可避免的需要用到getelementptr指令,但gep指令的类型部分非常难以确定,不过好在我们在设计Value时已经设计好了不同种类,我们可以根据该种类判断具体是哪种情况,直接挪用即可。针对gep指令,我还特地为Value设计了一个类型转换的方法,即根据类型编码转化为对应的LLVM语句:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public String typeToLlvm() {
switch (varType) {
case 2 -> {
return "i32*";
}
case 3 -> {
return "i32**";
}
case 4 -> {
return "[" + col + " x i32]*";
}
case 5 -> {
return "[" + row + " x [" + col + " x i32]]*";
}
case 6 -> {
return "[" + col + " x i32]**";
}
case 7 -> {
return "i1";
}
default -> {
return "i32";
}
}
}

其次,对于函数传进来的数组,我们是不需要先加一个i32 0的。

注意好以上两点,gep指令基本上没什么问题了。

七、后端代码生成

在生成LLVM以后,生成mips代码就显得简单许多。

7.1 架构

7.1.1 整体思路

因为LLVM已经为我们构建了中间代码语法树,我们从Module入手,自顶向下地分析即可,同样也是构建一个MipsBuilder用来构建后端代码。

MipsBuilder里,首先需要建立一个HashMap,存储寄存器的编号和名称的映射关系,之后即与ParserIrBuilder类似,为FunctionBasicBlockInstruction分别提供build方法。

7.1.2 RegManager

在优化之前,我的寄存器分配思路是先把能分配的都分配了,剩下的再推进内存,因此我建立了一个RegManager,用于管理寄存器。
RegManager应当具有以下功能:

  • 查看一个寄存器是否被占用
  • 分配给MipsBuilder一个空闲的寄存器
  • 释放一个正在被占用的寄存器

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class RegManager {
// key:寄存器编号,value:是否被占用
private final HashMap<Integer, Boolean> regMap;

public RegManager() {
regMap = new HashMap<>();
//初始化时全部寄存器都为空闲
for (int i = 0; i < 32; i++) {
regMap.put(i, false);
}
}

// 分配一个空闲的寄存器
public int allocTmpReg()

// 判断一个寄存器是否被占用
public boolean isUsed(int reg)

// 释放一个寄存器
public void unmap(int reg)

}

在RegManager里,分配寄存器时只能分配t类和s类,如果没有空闲的寄存器就返回-1。

7.1.3 后端符号表

生成中间代码时,我们还能勉强采用之前的符号表,但是到了后端,我们就不能偷懒了,因为LLVM产生了很多中间变量,在中端时我们不用管他们,但后端不同,我们需要为其分配寄存器或者内存,需要记录寄存器编号和在内存中的相对位置,所以我们必须要新开一个符号表。

对于后端的Symbol,我们不需要记录太多信息,只需要记录其在LLVM中的名字与寄存器编号/在内存中的位置即可。

1
2
3
4
5
6
7
public class MipsValue {
/** 若变量存入内存,需要记录相对于base的偏移量 */
private int baseReg;
private int offset;
private final boolean isInReg;
private int tmpReg; // 如果变量在寄存器中,则记录临时的寄存器
}

后端的SymbolTable与前端差别不大,不多赘述

7.2 实现细节

7.2.1 全局变量

对于全局变量的处理,我并没有采用教程中介绍的.data的方式,而是直接把全局变量用sw指令压在$gp中。因为我懒得再多写一个.data的功能

7.2.2 函数调用

函数调用是mips的一大难点,在我的编译器中,一旦涉及到函数调用,就需要执行如下几个步骤:

  • 保存$ra$sp中,栈顶减4。
  • 将函数实参压入栈中:
    • 小于4个参数:将参数的值赋给a系列寄存器,
    • 多于4个参数:将参数的值压进内存,并将其在内存中的位置记录在符号表中。
  • 然后是至关重要的一步,要将$fp的值赋给$v1$v1是一个机动寄存器。这一步的目的是,要记录下保存完参数、保存临时寄存器之前的地址,子函数可以从这里往回找参数。因为之后还要把临时寄存器存进$fp中,所以不在此时记录下fp的值就会导致子函数找不到形参。
  • 然后是将用到的临时寄存器保存起来,这里只存用到的t类和s类即可。这里在函数内部还要维护一个HashMap,记录下寄存器编号和内存里的地址的对应关系,方便函数调用结束后找回这些寄存的值。
  • $fp自增fpOffset
  • 将所有寄存器解除映射,子函数可以随意使用寄存器,因为已经保存过了。
  • 加入Jal指令。
  • $sp自增4,恢复$ra
  • 恢复$fp,将$fp减去fpOffset。
  • 恢复fpOffset。
  • 恢复临时寄存器,从之前提到过的HashMap中取出寄存器的值。
  • 处理函数返回值,将$v0存入内存中。

经历了上述步骤,函数调用就算处理完了。

7.3.3 数组处理

数组处理我本来是想按照写mips的习惯,写两个宏指令来处理的,但是不知道为什么课程组不让用macro,于是只能放弃。当遇到一个LLVM中的gep指令时,有如下步骤需要做:
一维数组

  • 获取数组中括号里的值,先左移两位(乘以4),得到相对于数组基地址的偏移量。
  • 从符号表中查到该数组的基地址
  • 将基地址与偏移量相加,得到目标元素的地址。

二维数组

  • 获取该数组的第二维的值dim2,用数组第一维的偏移乘以dim2
  • 用上一步得到的地址加上第二维的偏移
  • 乘以4
  • 与数组的基地址相加。

八、优化部分

由于本学期数据库的截止时间与编译实验的截止时间高度重合,所以我优化部分做的不是很多,当然一方面也有自己的懒惰、保守等原因,总归确实还挺遗憾的。

8.1 乘除法优化

乘法优化
先判断乘法的两个操作数有没有常数:

  • 有常数,判断是否是2的幂次,若是,则转变为sll,若不是,用乘法指令
  • 没有常数,用乘法指令

除法优化
具体方法参见教程和往届各个大佬的博客就好,我这里就不多做赘述了,直接放上我的实现代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
public void optimizeDiv(int targetReg, int regOp1, int d) {
// 选择multiplier和shift部分
int N = 32;
int precision = N - 1; //除数的大小描述,有 divisor < 2^precision
int dAbs = Math.abs(d); //除数的绝对值
int log = N - Integer.numberOfLeadingZeros(dAbs - 1);
int shift = log;
double low = Math.floor(Math.pow(2, N + log) / dAbs);
double high = Math.floor((Math.pow(2, N + log)
+ Math.pow(2, N + log - precision)) / dAbs);
while (Math.floor(low / 2.0) < Math.floor(high / 2.0) && shift > 0) {
// 求shift
}
long m = (long) high;
if (dAbs == 1) {
// 结果等于被除数
} else if (dAbs == Math.pow(2, log)) { // 除2的幂
// 类比乘法,转化为右移指令
} else if (m < Math.pow(2, N - 1)) { // multiplier比较小
Li li = new Li(targetReg, (int) m);
addMipsInstr(MipsInstrType.COMMON, li);
Mult mult = new Mult(targetReg, regOp1);
addMipsInstr(MipsInstrType.COMMON, mult);
Mfhi mfhi = new Mfhi(targetReg);
addMipsInstr(MipsInstrType.COMMON, mfhi);
Sra sra1 = new Sra(targetReg, targetReg, shift);
addMipsInstr(MipsInstrType.COMMON, sra1);
Sra sra2 = new Sra(regOp1, regOp1, 31);
addMipsInstr(MipsInstrType.COMMON, sra2);
Subu subu = new Subu(targetReg, targetReg, regOp1);
addMipsInstr(MipsInstrType.COMMON, subu);
} else {
long m1 = m - (long) Math.pow(2, N);
Li li = new Li(targetReg, (int) m1);
addMipsInstr(MipsInstrType.COMMON, li);
Mult mult = new Mult(targetReg, regOp1);
addMipsInstr(MipsInstrType.COMMON, mult);
Mfhi mfhi = new Mfhi(targetReg);
addMipsInstr(MipsInstrType.COMMON, mfhi);
Addu addu = new Addu(targetReg, targetReg, regOp1);
addMipsInstr(MipsInstrType.COMMON, addu);
Sra sra1 = new Sra(targetReg, targetReg, shift);
addMipsInstr(MipsInstrType.COMMON, sra1);
Sra sra2 = new Sra(regOp1, regOp1, 31);
addMipsInstr(MipsInstrType.COMMON, sra2);
Subu subu = new Subu(targetReg, targetReg, regOp1);
addMipsInstr(MipsInstrType.COMMON, subu);
}
if (d < 0) {
// 负数的情况
Subu subu = new Subu(targetReg, 0, targetReg);
addMipsInstr(MipsInstrType.COMMON, subu);
}
}

8.2 基本块优化

mips中指令是顺序执行的,而LLVM中指令是一定要在一个基本块内执行,这就为我们带来了很多的优化空间,尤其是本人在实现LLVM中由于跳转语句的逻辑不是很清晰,带来了很多没有用的基本块和跳转语句,所以我选择这步优化是非常必要的且比较卓有成效。
其中基本块优化中我实现了合并基本块这部分,流程如下:

  • 构建两个HashMap,分别是前驱集合和后继集合,两个集合的key都是BasicBlock,value都是ArrayList<BasicBlock>。代表着当前的基本块的前驱和后继集合。
  • 构建基本块之间的流图。由于基本块的最后一条语句一定是一条出口语句(跳转语句或者返回语句),所以我们只需要看这个基本块最后一条语句是什么类型的语句即可,有以下这么几种情况:
    • br Label,将当前基本块与Label进行双向链接,过程可类比双向链表
    • br cond trueLabel, falseLabel,与两个目标基本块都进行连接
    • return,没有后继,不用理会
  • 我们合并基本块有两个基本条件,一个是当前基本块要和后继基本块相邻,另一个是该后继基本块不能有其他后继,如果满足上述两个条件,就可进行进一步的优化。
  • 合并基本块的方法就是把该基本块的最后一条语句(一定是跳转语句)删掉,把后继基本块的指令全部加到该基本块中,删除后继基本块。这就要求我们的基本块内有且只有一条跳转语句,再之前生成LLVM的时候其实我是不能保证这一点的,所以完成这次优化我也顺便删除了一些不会被执行到的死代码。

8.3 指令选择

把所有的subiu都换成addiu,由于我本身用到的指令类型也不是很多,伪指令中有不合理展开的只有这一条,所以我就只优化了这一条代码。

9. 总结感想

   来到计算机学院以后,类似这样的总结感想已经写过三篇了,这是第四篇。每当我写总结感想的时候都比较感慨,心情也很复杂,一方面是要和自己耕耘了一个学期的代码说再见了,难免有点不舍;另一方面是经过自己一个学期的反复增删修改,代码难免有点不能看了,可算是个解脱。
   说回到编译,这一学期的编译实验还是让我收获非常丰富的。首先就是让我更加深刻的理解了编译的原理与技术,加深了我对于理论课程的理解,尤其是优化部分和理论的关联程度比较密切。看着自己的编译器能将一段C语言程序翻译成汇编代码,还是非常有成就感的。此外,抛开编译本身的内容不谈,编译应该是我人生第一次管理一个如此庞大的项目,上学期的面向对象课程虽然也用的是java完成一个个小型项目,但编译涉及的工程量显然不是OO可以比拟的。尤其是语法分析这部分,我们将其戏称为OO第一单元Pro Max,想了想其实OO第一单元的表达式计算涉及的文法相比于编译来说真的很少,递归下降也只有三个函数。当然如此大的码量,我自然是应对的有些吃力的。我之前自认为我对代码的优雅程度是有一定要求的,但面对编译庞大的工作量我也只能屈服,一个类里上千行、大量的代码重复等在OO里不符合代码规范的行为都出现在了我的编译器里。有时候在GitHub上看到的一些学长的代码真的是非常公正优雅,令我非常羡慕。
   这次编译最大的遗憾就是没能实现很多优化了吧,但确实没有办法,因为和数据库的截止时间完美重合了,这也是我对编译课的建议之一,实验的截止时间最好能和数据库岔开,即使一周也好,当然这也是我对数据库的建议。还有一个建议就是,我真诚强烈地建议编译理论课程课件中所讲的代码可以不用Pascal而是用现在主流的一些语言,毕竟编译本身就已经很难了,让我们再理解一门过时且没学过的语言更是雪上加霜。
   这里我要特别鸣谢一下杨博文同学,如果不是他的话我应该编译器会完成得更加吃力,这学期我可以说是没少叨扰他,感谢他不厌其烦地回答了我每一个愚蠢的问题。
   至此,我已经实现了自己的处理器、操作系统与编译器,并且已经可以运行由SysY文法生成的所有程序了。经过三个学期后再回首望去,看到自己的成就,虽然每一学期都没有做到很顶尖的程度,但至少也是对自己的努力感到比较欣慰的。

  • 标题: Compiler-编译设计文档
  • 作者: jkm
  • 创建于 : 2024-08-18 00:42:00
  • 更新于 : 2024-08-24 23:19:29
  • 链接: https://goldenkm.github.io/2024/08/18/Compiler-Doc/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。