使用llvm实现一门语言 —— cava

cava 产生的背景，是由于ha3业务方对插件定制及版本兼容需求，要求我们基于llvm开发一种性能与c++相当的类java脚本语言。

经过我们的调查发现：

可备选项由例如sp上的lua，elasticsearch上的groovy等，但最终得出的结论是现有的脚本语言都不能很好的满足ha3的需求。

groovy是jvm语言，它和用java开发的elasticsearch比较配。ha3是用c++开发的，ha3上插件的内存管理模式很固定，插件中的内存分配可以和请求session的pool绑定，请求结束整个pool释放，不需引入gc；另外jni比较重和c++交互的效率不高，因jvm语言不满足要求。

公认和c++结合比较好的是lua，它在游戏领域被广泛使用，lua本身比较轻量，它通过lua栈和c++交互，lua有个非官方版的jit实现luajit，不考虑和c++交互的话，luajit的性能非常不错。但是在ha3算分过滤等场景，脚本和c++交互的次数能达到百万级别，c++交互上的开销是一个不能忽略的因素，lua在这种场景性能还是满足不了我们的要求。

最终，我们决定自己实现一门类java脚本语言——cava。

编译器通过词法分析 -> 语法分析 -> 语义分析 -> 中间代码优化 -> 目标代码生成，最终生成汇编指令，再由汇编语言根据不同的指令集生成对应的可执行程序

cava使用Bison和flex来实现词法语法分析，使用llvm来实现中间代码到编译执行

token定义

cava在词法分析阶段就透出了位置信息，记录下了所有token所在文件的行列号，用于后续报错处理时能够准确的定位错误位置

利用Bison定义语法规则，维护token之间的排列关系

在语法分析的时候，cava利用NodeFactory类生成对应的AST，把token连接成语法树

<a href="https://www.cs.cornell.edu/projects/polyglot/">AST设计参考</a>

以上文中 BinaryOpExpr 为例， binaryOpExpr 表示二元表达式。先创建对应的BinaryOpExpr 类，继承Expr类，里面包含成员左表达式 _left，右表达式 _right, 以及 表达式类型 _op。

创建节点并将左右子表达式及Op类型填入后，填充对应的位置信息，维护ASTContext(用于记录所有的AST信息)

编译模块(Module): has a module

编译单元(CompilationUnit): has Package Impot and ClassDecl (0 1 or more)

类(ClassDecl): has className and ClassBody

ClassBodyDecl: has ClassMemberDecl (0 1 or more)

类成员(ClassMemberDecl): is a

构造(ConstructorDecl): has className, a list of Formal and a block

Formal: has name and TypeNode

block: has a CompoundStmt Stmt

字段(FieldDecl): has TypeNode and VarDecl

VarDecl: has a valName and maybe with a Expr as initializer

方法(MethodDecl): has methodName a list of Formal and a block

类型(TypeNode) 语句(Stmt) 表达式(Expr)

基础类型(CanonicalTypeNode): boolean, char, int, double ...

class类型(AmbTypeNode): unresolved class type (除了基础类型，和数组类型，其余都是class类型)

数组类型(ArrayTypeNode): has a TypeNode and dims

CompoundStmt: { ...; ...; } contain multi Stmts

EmptyStmt

ExprStmt: has a Expr

BreakStmt

ContinueStmt

ReturnStmt

LocalVarDeclStmt: has TypeNode and VarDecl

IfStmt: has a ifExpr ifStmt and may has elseStmt

ForStmt: a list of initStmt, stopStmt, updateStmt and bodyStmt

DoWhileStmt

WhileStmt

SwitchStmt

ArrayInitExpr: {1, 2, 3}

ConditionalExpr: a &gt; b ? 0 : 1

BinaryOpExpr: &amp;&amp; || | &amp; ^ == &gt;= &lt;= &gt; &lt; != &gt;&gt; &lt;&lt; + - * / % ...

UnaryOpExpr: ++ -- !

LiteralExpr: 1 1.1 'a' "abc" null ...

NewExpr: new class

NewArrayExpr

FieldAccessExpr

AssignExpr: = += -= ...

ArrayAccessExpr

CallExpr

AmbExpr: a.b.c.d

cava支持多种用户自定义的插件，其中重要的一类是自定义AST改写插件，由于在AST层面上，能够拿到整颗语法树的信息，可以很方便的进行一些改写语法树的操作，使得脚本语言更加灵活，可以在用户代码无感知的情况下做一些改写工作，比如可以更好的做到版本兼容问题，帮助用户完成一些代码逻辑。AST插件的执行位置在生成AST之后。以下介绍几种插件：

用于检测用户在函数的函数中未实现return语句，插件自动填充return语句，该功能仅限返回值为void使用，其余类型无法确定返回值，因此加入了检测分支为实现return即报错。

用于对为实现构造函数的类自动生成的默认构造函数

报错信息中定义了错误类型，报错的位置信息，以及具体的错误内容，错误信息需要分布在编译的各个阶段产生，如词法语法错误，插件报错，类型系统的错误，类型推导阶段错误，codegen报错，jit报错等。也需要思考如何才能报错精准，能够让用户清晰的知道自己的错误在哪里，cava的报错会向java靠近，目前的实现还不尽如人意，后续版本中会逐渐完善报错内容的精准度，以及覆盖所有错误分支的测试。

类型分为基础类型，数组类型和class类型三个大类。

我们引入了类型系统来管理所有的基础类型，数组类型以及class类型，提供了注册类型，管理类型的功能。

由class 定义的类型均称为cava的class类型，class类型中包含每个类型所属的module，package等信息，能够记录类型的生命周期，作用域，类型间的关系等功能。

与java一致，我们引入了package概念，每个class类型都有对应的package，用以区分不同的类。

cava是以module形式管理代码的，类型的注册和生命周期都是基于module产生的，module分为external和internal两类，external允许外部module调用本module中的类型，用于做跨模块的链接，而internal设计为不允许外部module使用，属于私有module。

数组类型由数组的维数和其基类型（class类型或基础类型）共同组成，cava定义数组类型，数组可以显示的调用length:

可以看出，不同维数的数组是不一样的类型，因此，当生成n维数组的时候，我们会递归的生成n-1维到1维数组类型。

因此，cava会遍历整颗语法树中的所有变量常量等做类型的推导检测，以保证符合语法。

在经历完以上步骤后的语法树，我们正式用到了llvm，接下来我们将使用llvm生成语法树对应的LLVM IR(LLVM 自带的中间码)。

生成Module

遍历Module中的所有的类（Module -&gt; cava Class）

生成类中所有的构造及方法，构造函数是特殊的方法（cava Class -&gt; cava Ctor, Function), cava Ctor 是特殊的Function

生成方法对应的代码块(Function -&gt; Basic Block)

生成代码块中的语句(Basic Block -&gt; cava Stmt)

Stmt和Expr 对应到llvm中均为llvm::Instructions

分支语句的生成，以if语句为例：

生成表达式的IR(cava Stmt -&gt; cava Expr)

目前cava的异常检测还比较弱小，不支持用户try，catch逻辑

现有的异常检测实现方法是在所有的数组下标调用前，除法前以及对象下标访问前，进行判定是否合法，将if语句IR植入到代码中，使用if语句判断实现，遇到异常进行标记，并逐层返回。目前支持的异常检测包括：

数组边界检测

除0检测

null对象下标访问检测

cava不提供类似JVM的GC机制，作为一门脚步语言，采用允许用户自定义的内存分配方式。目前默认的简单内存实现是使用mem pool，作为脚步语言内存的持有一直到cava生命周期结束。

在CavaCtx 类中包含了可自定义的内存管理工具userCtx，所有的cava函数的第一项非this指针参数，均为 *CavaCtx，用于在每个方法中管理内存和异常信息。

以ha3调用cava举例，ha3使用mem pool自定义了Ha3CavaAllocator用于cava内存管理，在每个线程开始时创建cavaCtx的Ha3CavaAllocator，在调用插件的接口处传入cavaCtx，用于执行cava脚本

score = _scorerModuleInfo-&gt;scoreFunc(_scorerObj, _cavaCtx, doc);在线程结束前析构Ha3CavaAllocator，释放资源。

截止到目前，已经生成了未经过Pass优化前的llvm IR代码，通过llvm::errs() &lt;&lt; module; 打印出llvm Module 对应的IR代码：

cava代码

对应的未经过pass优化的IR，由于cava有一些内置的异常检测，以及未经过任何pass优化，所以会显得复杂点，后续会将异常检测重新设计，不再程序中内置检测，能够减少指令数，

执行代码通过找到函数符号对应的地址，直接调用function即可

cava 的设计之初就是追求高性能，尤其是与c++的交互

static int add(int a, int b) 转换成 define i32 @_ZN7Example3addEP7CavaCtxii(%class.CavaCtx* %"@cavaCtx@", i32 %a, i32 %b)，CavaCtx是上文提到的cava自带的参数

有了加载bc后，可以将cava原生代码和c++代码联合在一起编译，但是仍未解决cava调用c++函数这一层函数调用的开销，于是就有了跨模块inline的pass设计。我们利用IR定制了一个跨模块clone function的Pass，将不同module的函数及全局变量等通过递归的形式clone到本module中，再进行inline 优化，从而减少了函数调用。

<a href="https://llvm.org/docs/tutorial/LangImpl01.html">Kaleidoscope tutorial</a>

<a href="https://llvm.org/docs/CommandGuide/">llvm tools</a>