CompilerBagel-Make our compiler(SysY2022 to RISC-V asm)

发表于 阅读次数： Disqus：

项目地址：https://github.com/CompilerBagel/CompilerBagel

本项目为2023 年华为毕昇杯 CompilerBagel 组参赛作品，基于Java语言和Antlr框架，实现从SysY2022语言（C语言的子集）到RISC-V架构下汇编语言的完整编译器。

项目整体流程：词法、语法分析->中间代码生成->目标代码生成->寄存器分配->代码优化

Lexer and Parser

一个现代的编译器，总是从词法分析器（lexer）和语法分析器（Parser）开始。如今，词法分析和语法分析技术已经相当成熟，有许多现成的工具可以帮助我们自动生成词法分析器和语法分析器。这里我们选用Antlr作为编译器前端生成的工具。

Write a g4 file

我们需要为SysY2022语法编写词法和语法的g4文件，例如（节选）

SysYLexer.g4:

1
2
3
4
5
6
7
8
9
10
IDENT : (LETTER | '_') (LETTER | DIGIT | '_')* ;

fragment
DECIMAL_CONST : '0' | [1-9] [0-9]*;

fragment
OCTAL_CONST : '0' [0-7]+;

fragment
HEX_CONST : ('0x' | '0X') (DIGIT | [a-fA-F])+ ;

SysYParser.g4:

1
2
3
4
5
6
7
8
9
10
11
12
varDecl
   : bType varDef (COMMA varDef)* SEMICOLON
   ;

varDef
   : IDENT (L_BRACKT constExp R_BRACKT)* (ASSIGN initVal)?
   ;

initVal
   : exp
   | L_BRACE (initVal (COMMA initVal)*)? R_BRACE
   ;

注：完整代码见项目仓库

Write a Makefile to generate Lexer and Parser

g4文件完成后，编写Makefile方便生成词法分析器和语法分析器对应的Java代码。当编译脚本较复杂时，Makefile文件能有效降低工作量，只需在终端运行make antlr。

Makefile

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
export CLASSPATH=./lib/antlr-4.12.0-complete.jar

ANTLR = java -jar ./lib/antlr-4.12.0-complete.jar -listener -visitor -long-messages
JAVAC = javac -g
JAVA = java

PFILE = $(shell find ./src/main/java/antlr/ -name "SysYParser.g4")
LFILE = $(shell find ./src/main/java/antlr/ -name "SysYLexer.g4")
JAVAFILE = $(shell find ./src/main/java/antlr/ -name "*.java")
ANTLRPATH = $(shell find /usr/local/lib -name "antlr-*-complete.jar")

antlr: $(LFILE) $(PFILE)
	$(ANTLR) $(PFILE) $(LFILE)

clean:
	rm -f ./src/main/java/antlr/*.tokens
	rm -f ./src/main/java/antlr/*.interp
	rm -f ./src/main/java/antlr/*.java
	rm -f ./src/main/java/antlr/*.class
	rm -f ./src/main/java/antlr/SysYLexer.java ./src/main/java/antlr/SysYParser.java ./src/main/java/antlr/SysYParserBaseListener.java ./src/main/java/antlr/SysYParserBaseVisitor.java ./src/main/java/antlr/SysYParserListener.java ./src/main/java/antlr/SysYParserVisitor.java
	rm -rf classes

.PHONY: antlr clean

Test our Lexer and Parser

测试词法分析器和语法分析器，主要是对我们g4文件正确性的检查。这里使用antlr包下的TestRig工具，输入SysY语言的符合规范的代码进行测试。为此，我们编写了test.sh脚本：

注：由于项目结构调整，这段代码无法在Project中直接运行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
err_count=0
wrong_num=0

for sy_file in $(find ./resources -name "*.sy")
do
  (java org.antlr.v4.gui.TestRig SysY program -tokens < ${sy_file} | grep line) >& output.txt
  err_count=`cat output.txt | wc -l`
  if [ ${err_count} -gt 0 ]
  then
      echo ${sy_file}
      ((wrong_num++))
  fi
done
echo ${wrong_num}

小插曲：这里利用报错信息中的line关键词进行检索计数，凑巧的是，输入的源文件中也有line这个变量

，导致误将正确的用例判成错误的。由于这种用例数量较少，我们选择了人工直接排查。

至此，我们完成了Lexer and Parser 的实现。

Generate LLVM-like IR

下面正式进入编译器前端的部分。我们选择类LLVM IR作为我们的中间代码，下面便是利用Parser生成的抽象语法树生成中间代码。

Class Structure Design

IR Module，FunctionBlock and BasicBlock

仿照LLVM，我们需要实现一个IRModule类，每个IRMoudle中包含了若干个FunctionBlock，每个FunctionBlock中又包含了若干基本块BasicBlock。基本块中包含若干按顺序执行的指令（中间代码）。

Type System

仿照LLVM，我们设计了一套类型系统，所有具体类型实现了Type接口

image-20231007151442055

对于IntType，FloatType等类型，我们实现了单例模式以方便使用==进行类型判断。

为类型系统编写Junit单元测试：

1
2
3
4
5
6
7
8
9
10
@Test
public void arrayTypeTest2() {
    Type array1 = new ArrayType(int32Type, 5);
    Type array2 = new ArrayType(array1, 2);
    List<Integer> elementDimension = new ArrayList<>();
    elementDimension.add(2);
    elementDimension.add(5);
    assertEquals(array2.getText(), "[2 x [5 x i32]]");
    assertEquals(((ArrayType) array2).getElementDimension(), elementDimension);
}

Scope

作用域(Scope)，用于处理程序变量作用域的问题，并充当符号表的功能。

  • 分为全局作用域（GlobalScope）和局部作用域（LocalScope）。

  • 作用域记录自己的父作用域，能递归地向上搜索符号。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public interface Scope {
    Scope getEnclosingScope();
    void define(String name, ValueRef valueRef, Type type);
    ValueRef getValueRef(String name);
    Type getType(String name);
    String getScopeName();
    void setScopeName(String scopeName);
}

public class BaseScope implements Scope {...}

public class GlobalScope extends BaseScope{

    public GlobalScope(String scopeName, Scope enclosingScope) {
        super(scopeName, enclosingScope);
    }
}

public class LocalScope extends BaseScope{
    public LocalScope(String scopeName, Scope enclosingScope) {
        super(scopeName, enclosingScope);
    }
}

注：GlobalScope类和LocalScope类实际上可以合并

IRBuilder

：定义一个StringBuilder，利用Visitor设计模式直接遍历语法树，在遍历的同时直接追加字符串怎么样？

：哦，这糟糕透了，我们会出现许多重复的字符串常量，而且导致控制流语句的生成十分困难。

如何解决？加一层!

我们对直接生成中间代码文本和实体类的代码进行一次封装，实现了一个IRbuilder，并提供一套API向IRVistor（负责生成中间代码的类）提供服务。为了方便分工和项目的维护，我们编写了APIs的详细文档。

文档节选：

1
2
3
4
5
6
7
8
// 从内存中将值取出 
ValueRef value = IRBuildLoad(builder, /*pointer: ValueRef*/pointer, /*varName:String*/"value"); 

// 全局变量 
// 申明全局变量
ValueRef IRAddGlobal(module , type , "globalVarName"); 
// 初始化全局变量 
void IRSetInitializer(module , valueRef , valueRef);

Instruction and Virtual Regiser

LLVM IR 代码是SSA形式的中间代码，虚拟寄存器数量无限多。我们设计了BaseRegister类并实现ValueRef接口，利用静态成员tempCounter进行计数管理，保证虚拟寄存器不重复命名。

我们既需要文本形式的中间代码，也需要内存形式的中间代码。

  • 文本形式：编译利用LLVM工具对中间代码进行测试，降低测试和编写难度（越早测试越好）

  • 内存形式：即将Insturction对象传递到编译器后端，进行目标代码翻译

我们根据仿LLVM IR设计了若干指令，并统一实现了Insturction接口

  • AllocationInstruction
  • BrInsturction
  • CalculateInstruction
  • …

IRGenVisitor

这里是生成中间代码的核心部分，我们利用Visitor的设计模式，遍历Antlr生成的语法分析树，根据遍历到的不同的标识生成不同的指令。具体细节和算法请前往具体项目，下面简单介绍和举例：

运算指令的生成：

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
@Override
public ValueRef visitPlusExp(SysYParser.PlusExpContext ctx) {
    ValueRef left = visit(ctx.exp(0));
    ValueRef right = visit(ctx.exp(1));
    if(ConstIntVarMap.get(left.getText())!=null){
        left = new ConstIntValueRef(ConstIntVarMap.get(left.getText()));
    }
    if (ConstFloatVarMap.get(left.getText())!=null) {
        left = new ConstFloatValueRef(ConstFloatVarMap.get(left.getText()));
    }
    if(ConstIntVarMap.get(right.getText())!=null){
        right = new ConstIntValueRef(ConstIntVarMap.get(right.getText()));
    }
    if (ConstFloatVarMap.get(right.getText())!=null) {
        right = new ConstFloatValueRef(ConstFloatVarMap.get(right.getText()));
    }
    if (ctx.PLUS() != null) {
        if(left.getType() == int32Type && right.getType() == int32Type) {
            return IRBuildCalc(builder, left, right, "add_", ADD);
        }else{
            return IRBuildCalc(builder, left, right, "fadd_", FADD);
        }
    } else if (ctx.MINUS() != null) {
        if(left.getType() == int32Type && right.getType() == int32Type) {
            return IRBuildCalc(builder, left, right, "sub_", SUB);
        }else{
            return IRBuildCalc(builder, left, right, "fsub_", FSUB);
        }
    }

    return null;
}

比较指令的生成：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
@Override
public ValueRef visitLtCond(SysYParser.LtCondContext ctx) {
    ValueRef lVal = this.visit(ctx.cond(0));
    ValueRef rVal = this.visit(ctx.cond(1));
    ValueRef cmpResult = null;

    if (ctx.LT() != null) {
        cmpResult = IRBuildICmp(builder, IRIntSLT, lVal, rVal, "icmp_LT");
    } else if (ctx.LE() != null) {
        cmpResult = IRBuildICmp(builder, IRIntSLE, lVal, rVal, "icmp_LE");
    } else if (ctx.GE() != null) {
        cmpResult = IRBuildICmp(builder, IRIntSGE, lVal, rVal, "icmp_GE");
    } else if (ctx.GT() != null) {
        cmpResult = IRBuildICmp(builder, IRIntSGT, lVal, rVal, "icmp_GT");
    }

    // return IRBuildZExt(builder,cmpResult,int32Type,"tmp_");
    return cmpResult;
}

控制流语句翻译

使用栈来控制break和continue语句的跳转，将当前的标签记录在栈中，break一次弹出一层。

其他一些复杂的地方：int类型和float类型之间的类型转换，16进制数的处理等

特别地，由于比赛官方需要我们支持一些库函数，我们在前端额外进行了addLib操作。

工具推荐：一个好用在线编译工具https://godbolt.org

Test our IR code

因为我们实现的是基本兼容LLVM IR的中间代码，所以我们可以直接利用LLVM的工具链进行测试

一些技术要点：

  1. 如何查看main函数的返回值

    使用echo $?命令

  2. Unix 中 main函数返回值的范围

    0~255，8bit

测试代码原理不难，循环遍历测试数据，利用clang编译中间代码，将main函数的返回值和程序标准输出与所期望的输出用diff命令进行比对。(lli工具也可以用于测试LLVM IR代码)

frontend_test.sh:

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
55
pass_num=0
test_num=0
error_files=()

testcases=$(find ./src/test/resources/functional -name "*.sy" | sort)
for sysy_filename in ${testcases}
do
    ((test_num++))
    echo "${test_num}: ${sysy_filename}"
    input_file="${sysy_filename%.sy}.in"

    rm ans out answer.txt output.txt out_without_sylib.ll

    echo "#include \"./src/test/resources/sylib.c\"" > sample.c
    cat ${sysy_filename} >> sample.c

    clang sample.c -w -o ans
    if [ -f $input_file ]; then
        ./ans < $input_file > answer.txt
    else
        ./ans > answer.txt
    fi
    echo $? >> answer.txt

    java -Dfile.encoding=UTF-8 -classpath ./target/classes:./lib/antlr-4.12.0-complete.jar Main ${sysy_filename} out_without_sylib.ll test.s raw.s
    clang out_without_sylib.ll ./src/test/resources/sylib.c -w -o out
    if [ -f $input_file ]; then
        timeout 60s ./out < $input_file > output.txt
    else
        timeout 60s ./out > output.txt
    fi
    echo $? >> output.txt

    diff answer.txt output.txt > /dev/null
    if [ $? == 0 ]; then
        ((pass_num++))
        echo -e "\e[32mPass"
    else
        echo "Wrong return value in $sysy_filename"
        error_files+=($sysy_filename)
    fi
    if [[ "$1" == "d" ]]; then
        read
    fi
    echo -e "\e[0m"
done

echo "Pass cases ($pass_num/$test_num)"

for failed_file in "${error_files[@]}"
do
    echo $failed_file
done

rm ans out answer.txt output.txt out_without_sylib.ll sample.c

注：考虑到后端代码生成的需要，我们的代码并不能通过所有的前端测试，但不影响后端代码生成。

Backend of Our Compiler

终于，我们完成了编译器前端的工作。但是，编译器真正精彩的地方才刚刚开始。由于比赛时间有限，我们编译器的后端相对较简单。

编译器后端主要要实现指令选择、寄存器分配、栈空间分配等。

Instruction Selection

同样的，我们实现了一系列的后端指令类，这些类实现了MachineCode接口。注意区别的是，在后端浮点数和非浮点数使用不同的指令和寄存器。

CodeGen类负责生成目标代码，下面简单介绍一些项目难点

Calculation

需要区分浮点数和整数，使用不同的指令，这里利用表驱动的方式简化代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static Map<String, String> intOperatorMap = Stream.of(new String[][] {
    { IRConstants.ADD, ADDW },
    { IRConstants.SUB, SUBW },
    { IRConstants.MUL, MULW },
    { IRConstants.SDIV, DIVW },
    { IRConstants.XOR, XOR },
    { IRConstants.SREM, REM },
    { IRConstants.AND, AND},
    { IRConstants.SHL, SLLW},
}).collect(Collectors.toMap(data -> data[0], data -> data[1]));

public static Map<String, String> floatOperatorMap = Stream.of(new String[][] {
    { IRConstants.FADD, FADD_S },
    { IRConstants.FSUB, FSUB_S },
    { IRConstants.FMUL, FMUL_S },
    { IRConstants.FDIV, FDIV_S },
}).collect(Collectors.toMap(data -> data[0], data -> data[1]));

Array

我们的项目需要实现多维数组，我们需要计算偏移量，区分数组类型和指针类型。对于数组初始化，我们编写了一个memset汇编函数，大大提高了速度，减少了汇编代码量。

Label and Local Variable

变量存储在栈中，全局变量存储在.data区，我们需要拿到地址或标签，利用Load或Store指令进行取数据和存数据。这里需要设计一个变量表，记录变量位置。

Immediate Number

在IR层面的字面量常量，在目标代码中需要添加li指令进行。在项目中，我们实现了addLiOperation方法

部分指令如addi的立即数是有范围的，我们需要特别判断。当数据过大时，需要先使用li指令。

1
2
3
private boolean isLegalImm(int imm) {
        return imm >= -2048 && imm <= 2047;
}

CodeGen代码举例：

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
public void parseReturnInstr(RetInstruction instr, MachineBlock block) {
    List<ValueRef> rets = instr.getOperands();
    if (null != rets.get(0)) {
        // return not void
        MachineOperand src = parseOperand(rets.get(0)); // rets.get(0) retValueRef
        if (src.isImm()) {
            if (((Immeidiate) src).isFloatImm()) {
                src = addLiOperation(src, block);
                src.setPhysicsReg(fa0Reg);
            } else {
                MCLi li = new MCLi(a0Reg, src);
                block.getMachineCodes().add(li);
                setDefUse(src, li);
                setDefUse(a0Reg, li);
            }

        } else {
            Type type = ((BaseRegister) src).getType();
            if (type == int32Type) {
                MCBinaryInteger addw = new MCBinaryInteger(a0Reg, src, new Immeidiate(0), ADDI);
                block.getMachineCodes().add(addw);
                setDefUse(src, addw);
                setDefUse(a0Reg, addw);
            } else {
                BaseRegister ret = new BaseRegister("ret", floatType);
                MCFMv fmv = new MCFMv(ret, src, FMV_S);
                ret.setPhysicsReg(fa0Reg);
                setDefUse(src, fmv);
                setDefUse(ret, fmv);
                block.getMachineCodes().add(fmv);
            }
        }
    }
    MCReturn ret = new MCReturn();
    block.getMachineCodes().add(ret);
}

Register Allocation

动态分配和指定分配寄存器

Structure

我们实现了FloatPhysicsReg和PhysicsReg类，其中FloatPhysicsReg继承了PhysicsReg

寄存器分配由RegisterAllocate类实现

Simple Allocation

由于时间关系，我们实现了一个类似先来先服务策略的寄存器分配方法。

缺点：部分寄存器反复被用到，导致指令较难并行处理。

算法：

  1. 遇到IR代码中的虚拟寄存器时
    • 若该虚拟寄存器未分配物理寄存器，在寄存器池中寻找还未用过的寄存器，并分配给它，将物理寄存器设置为不可分配状态。
    • 否则，返回之前分配的物理寄存器。（使用HashMap记录）
  2. 虚拟寄存器保存的接下来还会用到该虚拟寄存器的代码数--,当该值减为0后，释放分配给虚拟寄存器的物理寄存器，设置为可以被分配状态。

Function Call

要生成RISC-V汇编代码，必须要对C语言函数调用的底层实现有所了解。函数传参中，参数以此存入a0, a1,a2寄存器，函数返回值存入a0， a1寄存器（我们只用到a0）。

当函数参数过多时，我们需要将参数存入栈中。具有调用关系的两个函数FunctionA和FunctionB，它们占据的栈空间是相邻的，传递的参数存放在栈空间相接的地方。

浮点数需要使用fa0, fa1,fa2等寄存器，我们需要根据类型指派不同的寄存器

Stack Allocation

栈分配在指令生成之后，根据指令中需要内存空间分配栈。在指令生成时，不断将栈的大小扩大（记录在变量中）。在指令生成完毕后再回填需要栈大小的语句。

Optimization

我们必须反思，由于对编译器后端结构的不熟悉，导致寄存器分配和栈分配不支持寄存器的溢出，这导致了Mem2Reg的优化难以进行。并且，由于时间关系，我们只实现了一些基本的窥孔优化。

除了再CodeGen类中直接修改外，我们添加了一个opt包，在代码生成后添加代码优化类。

frontend optimization

常量立即数化，将文本中的3 + 5由编译器直接计算成8

backend optimization

代数化简和强度消减

  • 代数化简，类似x = x + 0可被删除。

  • 强度消减，把代价比较高的运算替换成目标机器上代价较低的等价运算。

    例如：含2的幂次方的乘法指令转化成相应的左移指令，含2的幂次方的除法指令转化成相应的右移指令，2的幂次方的取余指令转化成相应的and指令

1
mul a1, a1, 2 -> slliw a1, a1, 1

消除冗余的加载和保存指令

1
2
ld a0, addr
sd addr, a0 # 此条语句可被删除

消除不可达代码

在同一个基本块中，跟在无条件跳转指令或函数返回指令后的代码可被消除。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
while (iterator.hasNext()) {
    MachineCode code = iterator.next();
    if (lastCode instanceof MCReturn) {
        removeList.add(code);
        continue;
    } else if (lastCode instanceof MCJump && ((MCJump) lastCode).getType().equals(J)) {
        removeList.add(code);
        continue;
    } else if (isRedundancyLS(lastCode, code)) {
        // 1. LD r0, a  2. ST a, R0
        removeList.add(code);
        continue;
    } else if (isRedundancyLoad(lastCode, code)) {
        // 1. ST a, R0 2. LD R0, a
        removeList.add(code);
        continue;
    } else if (isRepeatCode(lastCode, code)) {
        removeList.add(lastCode);
    }
    lastCode = code;
}

其他无用代码

例如mv a1, a1等

Thanks

感谢南京大学软件学院的编译原理课程，给了我们参加这类比赛的能力与勇气。

感谢冯洋老师的指导与比赛全程给我们的支持。

感谢队友陈欣怡、黄炜、倪匀博，大家的共同努力才有这个项目的成果。