编译原理实验设计文档

\(\mathcal{Author:gpf}\)

源码见 https://github.com/solor-wind/BUAA_Compiler

参考编译器介绍

参考pl0-compiler编译器

总体分为getsym，block，interpret三个部分

getsym负责读取和识别源代码中下一个符号，类似词法分析。通过跳过空白和注释、识别不同类型的符号来更新符号表并返回符号（token）

block负责处理程序的一个逻辑块，负责解析和生成代码，处理变量声明、语句和表达式等。通过递归调用子函数如statement等函数来递归下降解析源程序，类似于语法分析和语义分析。

interpret负责解析执行，类似生成目标代码。

编译器总体设计

词法分析设计

词法分析主要涉及3个类：Lexer,Token,TkenType ，其中最后一个是枚举类，对应单词的类别码。

Token类存储每个token的信息，包括类别码、值（比如变量名、字符串等等）、行数

Lexer类是进行词法分析的主要部分，使用 PushbackReader 读入，便于回退。读到字母或下划线、数字、符号、换行符则交由3种不同的方法处理。具体而言，读到字母或下划线则一直读下去直至出现非字母、非数字、非下划线，然后将读到的字符串进行匹配，判断是标识符还是关键字；读到数字则为数字常量；读到符号则分情况处理，比如 / 可能是除号，也可能是注释的一部分，需要再读入字符进行判断，如果是除号则进行回退。

特别的，对于转译字符需要原样输出

最终，将处理完毕的token存储到链表中，输出。

编码后的修改：为了让架构更加美观，将三个类移动至Lexer软件包中。同时，增加了TokenStream类来定位、输出、判断token

语法分析设计

目前的代码结构如下所示，units中的软件包下面是各个非终结符对应的类。

image-20240929084737230

存储结构方面，采用树形，将几乎每个非终结符建一个类，存储可能推出的下一个终结符/非终结符。每个类还重写了toString方法，便于最后的输出。

Parser类负责解析，采用递归下降解析，针对每一条文法几乎都有对应的解析方法。同时改写了部分左递归文法，方便处理。

错误处理方面，在对应位置判断是否为对应的终结符，如果不是则加入负责存储错误的TreeMap中，最后统一输出。如 parseAddExp() 会调用 parseMulExp() 等等，直至解析完成返回最顶层的存储单元

编码后的修改：错误处理不能仅仅在对应位置判断，对于一些同样依靠终结符得出解析方向的方法，需要进行修改。如 UnaryExp → Ident '(' [FuncRParams] ')' ，之前的写法是看一下有无右括号来判断是否有参数项，但这样无法正确处理错误。最终阅读文法之后得出 First(FuncRParams) 集合，通过判断相应的终结符来处理。

错误处理设计

由于词法分析部分只涉及一种错误，只需对 | 和 & 进行特判处理即可。

语法分析错误处理方面，在对应位置判断是否为对应的终结符，如果不是则加入负责存储错误的TreeMap中，最后统一输出。如 parseAddExp() 会调用 parseMulExp() 等等，直至解析完成返回最顶层的存储单元

语义分析错误处理，只需查对应的符号表。建立符号表的过程中，可以进行错误处理。如b类错误可以查询当前已经建立好的符号表中有无使用的相同符号名。除此之外，建立符号表的过程还可以添加多余信息方便错误处理，比如在LVal中利用符号表判断标识符是数组还是一般变量、字符类型还是整数类型等等，方便后续函数参数类型匹配。

代码生成设计

语义分析——符号表的建立

代码总体架构仍然是递归下降，初始给出符号表根节点，从编译单元根节点开始递归调用checkError方法进行解析，遇到变量/常量声明则建立新的符号并加入当前符号表，遇到Block或者函数声明就建立新的符号表，作为当前符号表的子节点之一。

新建立GetSymTable作为工具类，SymbolTable作为符号表，以及Symbol作为存储符号的类。具体的ArraySym，VarSym，FuncSym继承自Symbol并有各自的新增属性，如ArraySym需要存储数组长度，FuncSym需要存储参数个数以及参数类型等等。

建立符号表的过程中，可以进行错误处理。如b类错误可以查询当前已经建立好的符号表中有无使用的相同符号名。除此之外，建立符号表的过程还可以添加多余信息方便错误处理，比如在LVal中利用符号表判断标识符是数组还是一般变量、字符类型还是整数类型等等，方便后续函数参数类型匹配。

输出方面，从根符号表逐层调用子符号表即可。

生成LLVM IR

总体架构上类似语义分析，逐层调用每层类的genIR方法来获得相应的ir，具体设计如下

存储结构

采用LLVM的“万物皆value”思想，主要层次是irModule-Function-BasicBlock-Instruction，具体如下图所示，更详细的继承结构参考LLVM: llvm::Value Class Reference和LLVM: llvm::Type Class Reference

image-20241105091931445

其中，value类内容如下，提供了

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Value {
    private String name;
    private Type type;

    @Override
    public String toString() {/**/}

    @Override
    public boolean equals(Object o) {/**/}

    @Override
    public int hashCode() {/**/}
}

生成MIPS

由于有了LLVM的基础，生成MIPS只需如实翻译ir即可。后端相应的存储结构类似于LLVM，大体分为ObjModule,ObjFunction,ObjBlock,ObjInstr四层，而所有操作数都继承自ObjOperand，有标签、立即数、虚拟寄存器和实际寄存器四类。

翻译过程中，将LLVM value替换为相应的后端操作数，并完成指令的替换。如Br指令可根据有无条件分别翻译成bne和j指令。比较复杂的地方在于函数调用，涉及栈帧的涉及，而我的栈帧涉及如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/*
当前栈帧sp，函数A调用B
调用前：
----高地址
alloca的变量
...
ra
s0
...
s7
....
arg1(sp+4)
arg0(sp)
----低地址
ra为A的ra，arg为传入B的参数

通过遍历指令，确定需要alloca的大小、最多预留多少参数空间
函数A调用B时，保存ra,s0-s8,传递参数
函数B开头通过以上类似过程确定大小+ra+s0-s7申请自己的栈空间，即sp=sp-size
随后取出A传递的参数
返回时销毁栈帧
*/

完成了翻译，只剩下为指令中的虚拟寄存器分配实际寄存器的环节。这里采用比较简单的栈式分配，更复杂的图着色在代码优化部分。栈式分配即所有虚拟寄存器都为之分配栈空间，并将数值存到栈上。具体来说，遍历每个函数的每条指令，确定虚拟寄存器对应的栈空间位移，当虚拟寄存器vr0被更新时，用 sw vr0,offset(sp) 更新栈上存储的数值；当vr0被使用时，用 lw vr0,offset(sp) 获取最新的数值。由于每条指令的操作数不超过3，因此用t0,t1,t2三个实际寄存器即可完成所有指令的寄存器替换。

代码优化设计

前端优化

Mem2Reg

参考资料主要是https://github.com/No-SF-Work/miniSysY-tutorial/blob/master/challenge/mem2reg/help.md

mem2reg的主要内容是将以alloca、store、load为主要结构的局部变量存储与赋值转换为真正的SSA形式，最终实现去掉大部分的alloca、store、load指令

步骤一：求程序流图

所谓程序流图（CFG），实际上就是求出每个基本块的前驱与后继，即基本块basicBlock可能来自于哪些基本块，又可能跳转到哪些基本块

由于LLVM的语法约束，每个基本块有且仅有一条终结语句（br或ret，其他指令暂未用到），并且放置在最后，因此只需遍历每个基本块的最后一条指令即可构建出CFG

存储结构如下

1
2
3
HashMap<BasicBlock, HashSet<BasicBlock>> prevs = new HashMap<>();
HashMap<BasicBlock, HashSet<BasicBlock>> nexts = new HashMap<>();
HashSet<Pair<BasicBlock, BasicBlock>> edges = new HashSet<>();

在此阶段，可以简单合并一下基本块，并删除基本块。若A仅有一个后继B且B仅有一个前驱A，则AB可合并。求出CFG后，从起始节点进行DFS，没有遍历到的基本块即访问不到，可以删除

步骤二：求支配树和支配边界

支配涉及到多个概念，参考教程中的解释即可，下面给出大致定义

  • 支配：若CFG中从起始基本块到基本块B的每条路径都经过了A，则称基本块A支配B

  • 严格支配：A支配B，且A不是B

  • 直接支配：A严格支配B，并且不存在使得A严格支配C和C严格支配B同时成立。感性理解就是A是支配B的所有基本块中离B最近的哪一个。需要注意，每个基本块的直接支配者有且仅有一个

  • 支配树：由上可知，基本块之间的直接支配关系可以构成一棵树

  • 支配边界DF：\(DF(n)=\{x|n支配x的前驱结点，但n不严格支配x\}\)

存储结构如下：

1
2
3
4
HashMap<BasicBlock, HashSet<BasicBlock>> doms = new HashMap<>();//A被哪些块支配
HashMap<BasicBlock, BasicBlock> idoms = new HashMap<>();//直接支配者(A被B支配)
HashMap<BasicBlock, HashSet<BasicBlock>> domTree = new HashMap<>();//支配树，A直接支配哪些块
HashMap<BasicBlock, HashSet<BasicBlock>> DF = new HashMap<>();//支配边界

首先计算支配，计院教程中的计算方式貌似有误，无法处理循环的情况。由于测试点不大，可以采用最简单的做法：针对每个基本块A，标记A为被删除的块，然后从起始结点开始根据CFG图进行DFS，没有被遍历到的基本块则是被A支配的基本块。求出支配后，严格支配也被求出

接着计算直接支配。遍历每个基本块A的支配节点B（B支配A），如果B1严格支配B2则更新B2为A的直接支配者，依次更新。

其次计算支配边界

伪代码以及对应的真实代码如下：

image-20241128224826296

1
2
3
4
5
6
7
8
9
for (Pair<BasicBlock, BasicBlock> pair : cfg.edges) {
    BasicBlock a = pair.getFirst();
    BasicBlock b = pair.getSecond();
    BasicBlock x = a;
    while (!doms.get(b).contains(x) || x.equals(b)) {
        DF.get(x).add(b);
        x = idoms.get(x);
    }
}
步骤三：在支配边界插入phi

这一步骤没啥好说的，直接看代码即可

image-20241128224940507

插入空的phi语句后，DFS遍历支配树，对于每个基本块，遍历每一条指令，记录每个alloca的局部变量的最新的load的值和store的值，并在CFG的后继中插入phi指令的赋值部分

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
public void rename(BasicBlock block) {
        ArrayList<Instruction> newInstrs = new ArrayList<>();
        for (Instruction instr : block.getInstructions()) {
            replaceValue(instr);
            if (instr instanceof AllocaInstr alloca) {
                if (defs.containsKey(alloca.getVar())) {
                    localValMap.put(alloca.getVar(), new Literal(0, ((PointerType) alloca.getVar().getType()).getBaseType()));
                    //局部变量未定义就使用，文法没说，但默认为0
                    continue;
                }
            } else if (instr instanceof StoreInstr store) {
                if (defs.containsKey(store.getAddr())) {
                    localValMap.put(store.getAddr(), store.getValue());
                    continue;
                }
            } else if (instr instanceof LoadInstr load) {
                if (defs.containsKey(load.getAddr())) {
                    loadValMap.put(load.getRes(), localValMap.get(load.getAddr()));
                    continue;
                }
            } else if (instr instanceof PhiInstr phi) {
                localValMap.put(phiValMap.get(phi.getRes()), phi.getRes());//更新局部变量对应的值
            }
            newInstrs.add(instr);
        }
        block.setInstructions(newInstrs);
        for (BasicBlock nextBlock : cfg.nexts.get(block)) {
            for (Instruction instr : nextBlock.getInstructions()) {
                if (instr instanceof PhiInstr phi) {
                    if (localValMap.containsKey(phiValMap.get(phi.getRes()))) {
                        phi.addValLabel(new Pair<>(localValMap.get(phiValMap.get(phi.getRes())), block));
                    }
                } else {
                    break;
                }
            }
        }
        for (BasicBlock domBlock : domTree.domTree.get(block)) {
            HashMap<Value, Value> tmpMap = (HashMap<Value, Value>) localValMap.clone();
            rename(domBlock);//前序遍历支配树，每个子节点使用相同的当前父节点的stackMap（子节点1更新时不能影响子节点2）
            localValMap = tmpMap;
        }
    }

DCE

DCE即删除死代码，做法就是先求出有用的部分，剩下的都删掉

具体而言，遍历每个变量，得到def-use关系，即每个变量在哪里定义，用到了哪些变量。

初始先设置一些有用变量如返回值、跳转的cond、函数调用的参数等等，将他们加入usedValues集合，同时将他们用到的变量也加入这个集合，再递归查找用到的变量直至集合不再变化。没有产生在usedValues里定义过的变量的指令就可以删掉了。

1
2
HashMap<Value, Pair<BasicBlock, Integer>> defMap;//每个变量的定义点
HashSet<Value> usedValues;

DCE和mem2reg都会暴露出新的优化机会，可以再通过CFG合并、删除多余基本块

后端优化

RemovePhi

mem2reg后，留下了许多Phi指令来自不同基本块的数据流为变量赋值，但phi无法直接翻译，因此必须消除phi指令，消除的方式就是用并行赋值指令PC（一堆move的集合）。对于A到B的一条CFG边，如果A有多个后继，就不能直接在A后面添加PC，需要新建一个基本块，在其中添加PC指令，同时修改相应的前驱、后继、跳转指令、CFG图

图着色

最重要的后端优化，目的是合理的分配寄存器。

首先求出每个指令的use、def集合，根据指令的use、def求出基本块的use、def集合。use即一个变量还未被定义过就被使用，def即一个变量还未被使用过就被定义。use和def交集应为空。

求出use、def集合后，进行活跃变量分析。首先进行基本块的活跃变量分析，之后将每个基本块的out加入到基本块最后一个指令的out集合中，进行指令的活跃变量分析。活跃变量的in、out按如下公式求出 \[ out[m]=\cup_{s\in succ[m]}in[s]\\ in[m]=use[m]\cup(out[m]-def[m])\\ \] 随后构建冲突图，位于同一条指令出口变量或寄存器以及定义的变量或寄存器相互冲突，根据这个冲突的定义即可完成冲突图的构建，具体存储结构如下

1
2
3
private HashMap<ObjReg, HashSet<ObjReg>> conflictMap = new HashMap<>();//寄存器A与哪些寄存器冲突
private Stack<ObjReg> stack = new Stack<>();//分配颜色的顺序
private HashMap<ObjReg, Integer> spilled = new HashMap<>();//溢出的变量对应的栈空间

随后，循环进行简化和溢出，直至冲突图没有虚拟寄存器节点为止。简化，将冲突数小于等于实际寄存器个数的寄存器删除并存到栈上，随后进行溢出，将一个冲突数大于实际寄存器个数的寄存器删除并存到栈上，此时冲突图可能可以重新简化，因此循环。

之后，就根据栈的顺序逐步弹出虚拟寄存器，并加入冲突图中，查看是否有实际寄存器能够分配给它并使它不与当前的冲突图中的寄存器冲突。如果有，则分配相应的寄存器。否则，将其作为溢出的变量，分配栈空间。

最后，将虚拟寄存器替换为对应的实际寄存器，并针对剩余的虚拟寄存器进行栈式分配。

鸡肋优化

食之无用，弃之可惜

常数优化如下

1
2
3
4
5
a+0=a;
a-0=a;
a*1=a;	a*-1=a;	a*0=0;
a*4=a<<2;
a/1=a;	a/-1=-a;
专业课
编译原理实验设计文档
https://solor-wind.github.io/2025/01/01/编译原理实验设计文档/
作者
gpf
发布于
2025年1月1日
许可协议