使用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>