elang/4. 抽象语法树编译到 llvm

抽象语法树编译到 llvm

上一节: https://bbs.125.la/thread-14706398-1-1.html 源代码 git: http://gogs.mkyr.fun:99/myuan/elang

前言

本节的目标是把上一节的「语言」编译到 llvm IR, 要想简单快捷地生成 llvm IR, 官方的方案是 C++, 虽然有 C 绑定, 但是我测试编译出来的 dll 易语言总是莫名其妙报错或者找不到到导出函数, 而在 dllexport viewer 中却可以看到. 编译 llvm dll 然后让易语言调用花了大部分的时, 以至于这篇文章拖到了现在.

另外还有一个选项是 binaryen, 如果是 binaryen IR 的话, 倒还可以用易语言手写生成, 但是 binaryen 最终是运行在 wasm 上的, 不直接原生运行的话, 就代表着无法简单使用操作系统 API, 以及与已有的易语言生态相容, 那么这次的经验就对未来无用了.

最终, 我选择了 Python 的 llvmlite 绑定, Python 的 llvmlite 也是对 C API 的封装, 未来也许有机会白嫖 llvmlite 的 DLL.

在生成 IR 后, 事实上这个计算语言已经可以跨平台(Windows/Linux/OSX)跨指令集(x86-64/ARM/MIPS/龙芯)了, 至于32位还是64位程序也是无所谓的事情, 甚至如果有一个嵌入式系统里支持llvm, 那现在也可以在嵌入式裸机里跑.

未来兼求助

编译器前端要用 DSL 生成不能用易语言写, 后端又不能调用 llvm (最接近的是论坛找到的一个 clang 的 SDK, https://bbs.125.la/forum.php?mod=viewthread&tid=14543661), 所以生成 IR 的逻辑也不能用易语言写, 可以说使用易语言编译易语言的最终目标完全落空. 我之前写过的那些目标本来都是为了这个最终目标努力的, 虽然某些目标仍然可以用易语言实现(比如易语言实现 lisp, 栈虚拟机, 语法扩展), 但是我现在的确非常意兴阑珊.

加上易语言又跟易语言 IDE 强绑定, 之前考虑易语言语法扩展的时候, 我还觉得可以扩展 IDE 来兼容新语法, 但是后来我翻了一些逆向出来的东西, 发现以我的能力基本碰不了易语言 IDE 核心逻辑部分, 如果是在其他地方写然后转译成易语言, 那等于换了一门语言, 毕竟手写易语言的文本格式太笨了, 肯定是要用另一种表达生成易语言的, 那能换一门语言的时候, 为什么不用 C# 呢?

综合来讲, 现在唯一能做的接近原来目标的, 就是用易语言做一个易语言的虚拟机, 但是众所周知易语言语法已经很古老了, 写起来十分无聊, 我绝对没有勇气完全用易语言实现易语言的解释器. 第一篇第二篇实际上我曾经用 Python 实现过, 约 200 行就能完成, 但是在易语言里花了 844 行, 单独虚拟机我在 Python 中总共花了 95 行(平均每行 30 字符), 相当于是 Python 300 行就够完成全部了, 而易语言用了 1359 行. 我曾见过有人用 Python 实现了 lc3 虚拟机, 大概花了 688 行, 按这个比例光 lc3 虚拟机部分大约在易语言里需要两千八百行, 易语言语法前端估计又要三四千行. 这样又回到了扩展语法, 而上面分析看来扩展语法是很麻烦的.

关于扩展语法与现有 IDE 兼容, 如果你有任何解决问题的想法, 请留言告知.
只要能扩展语法, 我可以先用旧易语言扩展语法, 扩展差不多了就在其他语言用 socket 接口把 llvm 的相关操作封装起来, 让扩展后的易语言通过 socket 调用, 最终勉强还算是使用易语言编译易语言.

操作分解

在虚拟机中, 我自己写的代码可以随意操作逻辑, 但是到 llvm 层面, 就得自己新加逻辑来控制常量匹配了. 以如下代码举例:

f(0) = 1
f(x) = x * f(x - 1)
f(x, y) = f(x) + f(y)

应当编译成四个函数, 一个总入口(master func), 三个子函数. 以下写法并非标准 C 语言.

// f(0)
inline double "f[CONST 0]"(double _) {
    return 1;
} 
// f(x)
inline double "f[VAR x]"(double x) {
    return x * f(1, x - 1, 0);
}
// f(x, y)
inline double "f[VAR x, VAR y]"(double x, double y) {
    return f(1, x, 0) + f(1, y, 0);
}

double f_master(int args_count, double arg0, double arg1) {
    switch (args_count) {
        case 1:
            if (arg0 == 0) 
                return "f[CONST 0]"(arg0);
            else
                return "f[VAR x]"(arg0);
            break;
        case 2:
            return "f[VAR x, VAR y]"(arg0, arg1);
    }
}

因为在子函数里可以调用其他函数, 而主函数又要调用子函数, 因此要先把所有函数都取出来, 生成对应的master函数的声明, 声明完成后可以开始处理子函数, 子函数逻辑生成完毕后才可以开始写主函数逻辑.

然后这门语言除了函数就没东西了, 就这样. 归纳一下用到的功能:

• 加减乘除
• 语言内部函数调用
• 判断
• switch
• 外部 C 函数, printf

实际上再加点关键词, 就可以实现 lisp 了

AST 导出

没什么好说的, 手写了一个按 JSON 格式输出 AST 的函数. 这是最后的荣耀, 最后的完全使用易语言标准库完成的东西

LLVM IR 生成

几乎跟上一节写虚拟机差不多, 我甚至还写了一个 Python 的虚拟机作为 llvm 的骨架, 上一节直接求值的地方, 这一节要做一个中间变量, 然后生成对应的 llvm ir, 要判断的地方生成判断对应的 ir, 要调用的时候生成调用的 ir, 如此反复操作即可.

几乎所有用法都是参考 llvmlite 的测试学到的 https://github.com/numba/llvmlite/blob/master/llvmlite/tests/test_ir.py

用于生成 IR 的代码比较长, 都在压缩包里了, 用上一节示例生成的 IR 如下:

target triple = "x86_64-unknown-linux-gnu"
target datalayout = ""

define void @"main"() 
{
entry:
  %".2" = bitcast [8 x i8]* @"fstr" to i8*
  %".3" = fmul double 0x4000000000000000, 0x4008000000000000
  %".4" = fdiv double %".3", 0x4010000000000000
  %".5" = fadd double 0x3ff0000000000000, %".4"
  %".6" = call i64 (i8*, ...) @"printf"(i8* %".2", double %".5")
  %".7" = sitofp i64 %".6" to double
  %".8" = call i64 (i8*, ...) @"printf"(i8* %".2", double %".7")
  %".9" = call double @"f_master"(i64 1, double 0x4024000000000000, double              0x0)
  %".10" = call i64 (i8*, ...) @"printf"(i8* %".2", double %".9")
  %".11" = call double @"f_master"(i64 2, double 0x3ff0000000000000, double 0x4000000000000000)
  %".12" = call i64 (i8*, ...) @"printf"(i8* %".2", double %".11")
  %".13" = call double @"fib_master"(i64 1, double 0x4034000000000000)
  %".14" = call i64 (i8*, ...) @"printf"(i8* %".2", double %".13")
  %".15" = call double @"square_master"(i64 1, double 0x4000000000000000)
  %".16" = call double @"exp_master"(i64 2, double 0x4000000000000000, double %".15")
  %".17" = call i64 (i8*, ...) @"printf"(i8* %".2", double %".16")
  %".18" = call double @"sqrt_master"(i64 1, double 0x4000000000000000, double              0x0, double              0x0, double              0x0)
  %".19" = call double @"sqrt_master"(i64 1, double 0x4000000000000000, double              0x0, double              0x0, double              0x0)
  %".20" = call double @"square_master"(i64 1, double %".19")
  %".21" = call i64 (i8*, ...) @"printf"(i8* %".2", double %".18", double %".20")
  ret void
}

declare i64 @"printf"(i8* %".1", ...) 

@"fstr" = internal constant [8 x i8] c"> %.8f\0a\00"
@"cond_global_fmt" = internal constant [12 x i8] c"> cond: %d\0a\00"
define double @"f_master"(i64 %".1", double %".2", double %".3") 
{
entry:
  switch i64 %".1", label %"switch_default" [i64 1, label %"f_arg_1" i64 2, label %"f_arg_2"]
exit:
  ret double 0xbff0000000000000
switch_default:
  br label %"exit"
f_arg_1:
  %".8" = bitcast [12 x i8]* @"cond_global_fmt" to i8*
  %"cmp_0" = fcmp ueq double %".2",              0x0
  %".9" = and i1 1, %"cmp_0"
  br i1 %".9", label %"f_arg_1.if", label %"f_arg_1.endif"
f_arg_1.if:
  %".11" = call double @"f[CONST 0]"(double              0x0)
  ret double %".11"
f_arg_1.endif:
  br i1 1, label %"f_arg_1.endif.if", label %"f_arg_1.endif.endif"
f_arg_1.endif.if:
  %".14" = call double @"f[VAR x]"(double %".2")
  ret double %".14"
f_arg_1.endif.endif:
  br label %"exit"
f_arg_2:
  %".17" = bitcast [12 x i8]* @"cond_global_fmt" to i8*
  br i1 1, label %"f_arg_2.if", label %"f_arg_2.endif"
f_arg_2.if:
  %".19" = call double @"f[VAR x, VAR y]"(double %".2", double %".3")
  ret double %".19"
f_arg_2.endif:
  br label %"exit"
}

define double @"fib_master"(i64 %".1", double %".2") 
{
entry:
  switch i64 %".1", label %"switch_default" [i64 1, label %"fib_arg_1"]
exit:
  ret double 0xbff0000000000000
switch_default:
  br label %"exit"
fib_arg_1:
  %".7" = bitcast [12 x i8]* @"cond_global_fmt" to i8*
  %"cmp_1" = fcmp ueq double %".2", 0x3ff0000000000000
  %".8" = and i1 1, %"cmp_1"
  br i1 %".8", label %"fib_arg_1.if", label %"fib_arg_1.endif"
fib_arg_1.if:
  %".10" = call double @"fib[CONST 1]"(double 0x3ff0000000000000)
  ret double %".10"
fib_arg_1.endif:
  %"cmp_2" = fcmp ueq double %".2", 0x4000000000000000
  %".12" = and i1 1, %"cmp_2"
  br i1 %".12", label %"fib_arg_1.endif.if", label %"fib_arg_1.endif.endif"
fib_arg_1.endif.if:
  %".14" = call double @"fib[CONST 2]"(double 0x4000000000000000)
  ret double %".14"
fib_arg_1.endif.endif:
  br i1 1, label %"fib_arg_1.endif.endif.if", label %"fib_arg_1.endif.endif.endif"
fib_arg_1.endif.endif.if:
  %".17" = call double @"fib[VAR x]"(double %".2")
  ret double %".17"
fib_arg_1.endif.endif.endif:
  br label %"exit"
}

define double @"exp_master"(i64 %".1", double %".2", double %".3") 
{
entry:
  switch i64 %".1", label %"switch_default" [i64 2, label %"exp_arg_2"]
exit:
  ret double 0xbff0000000000000
switch_default:
  br label %"exit"
exp_arg_2:
  %".8" = bitcast [12 x i8]* @"cond_global_fmt" to i8*
  %"cmp_0" = fcmp ueq double %".3",              0x0
  %".9" = and i1 1, %"cmp_0"
  br i1 %".9", label %"exp_arg_2.if", label %"exp_arg_2.endif"
exp_arg_2.if:
  %".11" = call double @"exp[VAR x, CONST 0]"(double %".2", double              0x0)
  ret double %".11"
exp_arg_2.endif:
  br i1 1, label %"exp_arg_2.endif.if", label %"exp_arg_2.endif.endif"
exp_arg_2.endif.if:
  %".14" = call double @"exp[VAR x, VAR y]"(double %".2", double %".3")
  ret double %".14"
exp_arg_2.endif.endif:
  br label %"exit"
}

define double @"square_master"(i64 %".1", double %".2") 
{
entry:
  switch i64 %".1", label %"switch_default" [i64 1, label %"square_arg_1"]
exit:
  ret double 0xbff0000000000000
switch_default:
  br label %"exit"
square_arg_1:
  %".7" = bitcast [12 x i8]* @"cond_global_fmt" to i8*
  br i1 1, label %"square_arg_1.if", label %"square_arg_1.endif"
square_arg_1.if:
  %".9" = call double @"square[VAR x]"(double %".2")
  ret double %".9"
square_arg_1.endif:
  br label %"exit"
}

define double @"sqrt_master"(i64 %".1", double %".2", double %".3", double %".4", double %".5") 
{
entry:
  switch i64 %".1", label %"switch_default" [i64 1, label %"sqrt_arg_1" i64 4, label %"sqrt_arg_4"]
exit:
  ret double 0xbff0000000000000
switch_default:
  br label %"exit"
sqrt_arg_1:
  %".10" = bitcast [12 x i8]* @"cond_global_fmt" to i8*
  br i1 1, label %"sqrt_arg_1.if", label %"sqrt_arg_1.endif"
sqrt_arg_1.if:
  %".12" = call double @"sqrt[VAR x]"(double %".2")
  ret double %".12"
sqrt_arg_1.endif:
  br label %"exit"
sqrt_arg_4:
  %".15" = bitcast [12 x i8]* @"cond_global_fmt" to i8*
  %"cmp_0" = fcmp ueq double %".5",              0x0
  %".16" = and i1 1, %"cmp_0"
  br i1 %".16", label %"sqrt_arg_4.if", label %"sqrt_arg_4.endif"
sqrt_arg_4.if:
  %".18" = call double @"sqrt[VAR x, VAR s, VAR y, CONST 0]"(double %".2", double %".3", double %".4", double              0x0)
  ret double %".18"
sqrt_arg_4.endif:
  br i1 1, label %"sqrt_arg_4.endif.if", label %"sqrt_arg_4.endif.endif"
sqrt_arg_4.endif.if:
  %".21" = call double @"sqrt[VAR x, VAR s, VAR y, VAR n]"(double %".2", double %".3", double %".4", double %".5")
  ret double %".21"
sqrt_arg_4.endif.endif:
  br label %"exit"
}

define double @"f[CONST 0]"(double %".1") 
{
entry:
  ret double              0x0
}

define double @"f[VAR x]"(double %".1") 
{
entry:
  %".3" = fsub double %".1", 0x3ff0000000000000
  %".4" = call double @"f_master"(i64 1, double %".3", double              0x0)
  %".5" = fadd double %".1", %".4"
  ret double %".5"
}

define double @"f[VAR x, VAR y]"(double %".1", double %".2") 
{
entry:
  %".4" = fadd double %".1", %".2"
  ret double %".4"
}

define double @"fib[CONST 1]"(double %".1") 
{
entry:
  ret double 0x3ff0000000000000
}

define double @"fib[CONST 2]"(double %".1") 
{
entry:
  ret double 0x3ff0000000000000
}

define double @"fib[VAR x]"(double %".1") 
{
entry:
  %".3" = fsub double %".1", 0x3ff0000000000000
  %".4" = call double @"fib_master"(i64 1, double %".3")
  %".5" = fsub double %".1", 0x4000000000000000
  %".6" = call double @"fib_master"(i64 1, double %".5")
  %".7" = fadd double %".4", %".6"
  ret double %".7"
}

define double @"exp[VAR x, CONST 0]"(double %".1", double %".2") 
{
entry:
  ret double 0x3ff0000000000000
}

define double @"exp[VAR x, VAR y]"(double %".1", double %".2") 
{
entry:
  %".4" = fsub double %".2", 0x3ff0000000000000
  %".5" = call double @"exp_master"(i64 2, double %".1", double %".4")
  %".6" = fmul double %".5", %".1"
  ret double %".6"
}

define double @"square[VAR x]"(double %".1") 
{
entry:
  %".3" = fptosi double %".1" to i64
  %".4" = call double @"exp_master"(i64 %".3", double 0x4000000000000000, double              0x0)
  ret double %".4"
}

define double @"sqrt[VAR x]"(double %".1") 
{
entry:
  %".3" = fdiv double %".1", 0x4000000000000000
  %".4" = call double @"sqrt_master"(i64 4, double %".1", double %".3", double 0x3ff0000000000000, double 0x4024000000000000)
  ret double %".4"
}

define double @"sqrt[VAR x, VAR s, VAR y, CONST 0]"(double %".1", double %".2", double %".3", double %".4") 
{
entry:
  ret double %".2"
}

define double @"sqrt[VAR x, VAR s, VAR y, VAR n]"(double %".1", double %".2", double %".3", double %".4") 
{
entry:
  %".6" = fadd double %".2", %".3"
  %".7" = fdiv double %".6", 0x4000000000000000
  %".8" = fadd double %".2", %".3"
  %".9" = fdiv double %".8", 0x4000000000000000
  %".10" = fdiv double %".1", %".9"
  %".11" = fsub double %".4", 0x3ff0000000000000
  %".12" = call double @"sqrt_master"(i64 4, double %".1", double %".7", double %".10", double %".11")
  ret double %".12"
}

LLVM IR 编译

在Linux上直接用系统的包管理器安装最新的 llvm 和 clang, 在 Windows 上需要使用 VS2017+ 安装 clang, 然后用这位老哥编译好的 Windows 上的 llvm(https://github.com/vovkos/llvm-package-windows).

通过 Python 代码把 AST 变成 IR 后, 把 IR 放到一个文件中, 假设名为 test.ll, 那么接下来的命令是:

# Windows
llc -filetype=obj test.ll -o test.o
clang test.o -o test.exe
./test.exe

# Linux
llc -filetype=obj --relocation-model=pic test.ll -o test.o
clang test.o -o test
./test

我在本机上(Manjaro)运行时间大概是 0.4ms, 在一个Windows虚拟机上, AST 解释器需要 360ms 左右, 二进制版需要 10 ms左右, 如果大家有闲, 可以在易语言里实现同样功能测测时间(记得实现运行时函数重载).

附录

虚拟机 in Python

这个短, 可以放进来.

from json import load
import string
from collections import defaultdict


ast = load(open("ast.json", encoding="utf8"))
funcs = defaultdict(list) # {name: [{args: body}]}

op_funcs = {
    "+": lambda x, y: x + y, "-": lambda x, y: x - y,
    "*": lambda x, y: x * y, "/": lambda x, y: x / y,
}
builtin_func = {
    'output': lambda *x: print(*x),
    'dir': lambda *_: print(funcs)
}

is_number = lambda x: all([i in string.digits + "." for i in x])

get_dict_key = lambda x: list(x.keys())
get_dict_value = lambda x: list(x.values())


def eval_function(name: str, params: list, env: dict):
    current_funcs = funcs.get(name)
    candidate_func_match = [0 for _ in current_funcs]

    for func_index, (args, body) in enumerate(current_funcs):
        if len(args) != len(params):
            candidate_func_match[func_index] -= 99999
            continue
        for i, arg in enumerate(args):
            if not all([a in string.digits for a in arg]):
                continue
            # only digits here
            if params[i] != float(arg):
                candidate_func_match[func_index] -= 99999
                break
            candidate_func_match[func_index] += 1

    candidate_func = sorted(
        zip(current_funcs, candidate_func_match),
        key=lambda x: x[1]
    )

    if not candidate_func or candidate_func[-1][1] < 0:
        print("error: cannot find a suitable overloaded function for", name)
        return
    
    args, body = candidate_func[-1][0]
    return eval_line(body, dict(zip(args, params)))


def eval_line(line: dict, envs: dict):
    if isinstance(line, dict):
        name: str = get_dict_key(line)[0]
        params: list = get_dict_value(line)[0]
    else:
        print('error line', line)
        return
    if name == 'root':
        for arg in params:
            eval_line(arg, envs)
    elif name.startswith('#'):
        pass
    elif name == '括号':
        return eval_line(params[0], envs)
    elif name == '=':
        assert len(params) == 2
        func_name, args = list(params[0].items())[0]
        args = [get_dict_key(i)[0] for i in args]
        funcs[func_name].append([args, params[1]])
    elif is_number(name):
        assert not params
        return float(name)
    elif name in op_funcs:
        assert len(params) == 2
        return op_funcs[name](
            eval_line(params[0], envs), 
            eval_line(params[1], envs)
        )
    elif name in builtin_func:
        return builtin_func[name](">", *[
            eval_line(arg, envs) for arg in params
        ])
    elif name in funcs:
        return eval_function(name, [
            eval_line(arg, envs) for arg in params
        ], envs)
    elif name in envs:
        return envs.get(name)
    else:
        print('cannot find', name)
eval_line(ast, {})