教你使用swift写编译器玩具（3）

前言

本章对应官方教程第3章，本章介绍如何将抽象语法树(AST)转换为中间代码(LLVM IR)。

教程如下:

教你使用swift写编译器玩具（0）

教你使用swift写编译器玩具（1）

教你使用swift写编译器玩具（2）

教你使用swift写编译器玩具（3）

教你使用swift写编译器玩具（4）

教你使用swift写编译器玩具（5）

教你使用swift写编译器玩具（6）

教你使用swift写编译器玩具（7）

教你使用swift写编译器玩具（8）

仓库在这

开始

在生成IR开始之前我们需要为为ExprAST协议定一个codeGen方法，并返回LLVM的IRValue对象。这个方法表示该AST所表示的IR。

1
2
3
4
5
protocol ExprAST {
    
    func codeGen() -> IRValue?
    
}

接着我们创建Module对象theModule，它是一个包含函数和全局变量的LLVM数据结构，它拥有我们生成的所以IR的内存。

1
var theModule: Module! = Module(name: "main")

接着我们创建IRBuilder对象builder，它可以用来生成LLVM指令。

1
let builder = IRBuilder(module: theModule)

定义代码符号表namedValues，表中的内容为当前范围内的值以及他们的IRValue。在Kaleidoscope中，它会在函数体生成的时候用到。

1
var namedValues: [String: IRValue] = [:]

表达式代码生成

首先我们先从最简单的写起，那就是NumberExprAST

1
2
3
func codeGen() -> IRValue? {
    return FloatType.double.constant(value)
}

这段代码把swift的Double表示转化为了LLVM IR的Double表示。

变量的codeGen也十分简单

1
2
3
4
5
6
7
func codeGen() -> IRValue? {
    let value = namedValues[name]
    guard value != nil else {
        fatalError("unknow variable name.")
    }
return value!.asLLVM()
}

实际上目前namedValues中的内容只唯一有函数参数的变量。所以在返回值之前先要检查一下是否以及是被解析为函数的参数了。

二元运算符的代码生成思路是递归的生成左侧的IRValue以及右侧的IRValue。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func codeGen() -> IRValue? {
    let l = lhs!.codeGen()
    let r = rhs!.codeGen()
    guard l != nil && r != nil else {
        return nil
    }
    switch op! {
    case "+":
        return builder.buildAdd(l!, r!, name: "add")
    case "-":
        return builder.buildSub(l!, r!, name: "sub")
    case "*":
        return builder.buildMul(l!, r!, name: "mul")
    case "<":
        return builder.buildFCmp(l!, r!, .unorderedLessThan, name: "boolCmp")
    default:
        fatalError("Invalid binary operator.")
    }
}

在上面的代码中，builder是知道在哪里插入指令，所以我们需要做的仅仅只是指定使用哪个指令而已。比如说buildAdd或者buildFCmp。

LLVM指令有很严格的约束，比如说buildAdd指令的的左右两侧都必须是同一类型，但是在Kaleidoscope中我们只支持了Double类型，所以不是很需要操心。

另外，符号”<”对应的指令buildFCmp始终返回i1类型，在这里我们与官方教程不一样的一点就是我们并不需要操心这个类型不是Double类型，我们只需要返回出去即可。

接着我们来实现函数调用的codeGen。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func codeGen() -> IRValue? {
    let calleeF = theModule.function(named: callee!)
    guard calleeF != nil else {
        return nil
    }
    if calleeF!.parameterCount != args!.count {
        fatalError("Incorrect arguments passed.")
    }
    var argsV: [IRValue] = []
    for arg in args! {
        if let gen = arg.codeGen() {
            argsV.append(gen)
        } else {
            return nil
        }
    }
    return builder.buildCall(calleeF!, args: argsV, name: "call")
}

我们只需要在LLVM Module中查找函数名并设置参数即可生成函数调用的IRValue。

功能代码生成

原型和函数的codeGen比较复杂一些。值得注意的是原型和函数的codeGen方法的返回类型并不是IRValue类型而是Function类型。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func codeGen() -> Function {
    let doubles = Array(repeating: FloatType.double, count: args.count)
    let ft = FunctionType(doubles, FloatType.double, variadic: false)
    var f: Function = theModule.addFunction(name, type: ft)
    //这其实是默认linkage，这里为了和官方教程保持一致，显示的写一下
    f.linkage = .external
    //设置参数名
    var p = f.firstParameter
    for i in 0..<args.count {
        p?.name = args[i]
        p = p?.next()
    }
    return f
}

FunctionType第一个参数为一个类型的数组代表这个函数每个参数的类型，第二个参数为函数返回值的类型，第三个参数的含义为是否为可变变量，这里设置为false。

接着我们要在FunctionAST的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
func codeGen() -> Function? {
    functionProtos[proto!.name!] = proto
    let theFunction = getFunction(named: proto!.name!)
    guard theFunction != nil else {
        return nil
    }
    
  	//创建一个基本块(BasicBlock)
    let entry = theFunction!.appendBasicBlock(named: "entry")
  	//这行代码告诉bulder应该把新的指令插在基本块的末尾，你可以理解为插在名为entry的这个基本块里
    builder.positionAtEnd(of: entry)
    
  	//我们把函数参数添加到namedValues中以便VariableExprAST可以访问到
    namedValues.removeAll()
    var p = theFunction!.firstParameter
    while p != nil {
        namedValues[p!.name] = p!
        p = p?.next()
    }
    
  	//解析函数体对应的IRValue
    if let retValue = body!.codeGen() {
        builder.buildRet(retValue)
        do {
          	//验证函数，这个方法可以检查出函数生成IR是否出现问题。
            try theModule.verify()
            return theFunction
        } catch {
            print("verify failure: \(error)")
        }
    }
    //函数体出现问题，移除函数
    theFunction!.eraseFromParent()
    return nil
}

函数体解析过程中的要点都在注释中体现了，下面我们可以使用Function对象的dump()方法打印出函数的IR。

我们在Parser中实现Lexer的代理LexerDelegate

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
extension Parser: LexerDelegate {
    
    func lexerWithDefinition(_ lexer: Lexer) {
        if let p = parseDefinition() {
            if let f = p.codeGen() {
                print("Read function definition:")
                f.dump()
            }
        } else {
            lexer.nextToken()
        }
    }
    
    func lexerWithExtern(_ lexer: Lexer) {
        let p = parseExtern()
        let f = p.codeGen()
        f.dump()
        functionProtos[p.name] = p
    }
    
    func lexerWithTopLevelExpression(_ lexer: Lexer) {
        if let p = parseTopLevelExpr() {
            if let f = p.codeGen() {
                print("Read top-level expression:")
                f.dump()
            }
        } else {
            lexer.nextToken()
        }
    }
    
}

现在就可以打印出IR了。

我们将在下一章实现IR的优化以及对JIT的支持。

测试

我们编写一个扩展类型为.k的文件

1
def foo(a b) a*a + 2*a*b + b*b;
1
2
3
4
5
6
7
8
9
10
11
12
Read function definition:

define i64 @foo(i64 %a, i64 %b) {
entry:
  %mul = mul i64 %a, %a
  %mul1 = mul i64 2, %a
  %mul2 = mul i64 %mul1, %b
  %add = add i64 %mul, %mul2
  %mul3 = mul i64 %b, %b
  %add4 = add i64 %add, %mul3
  ret i64 %add4
}

请忽略我生成的IR中值的type是i64。因为我在最开始实现时并没有按照教程说的使用Double类型。