有沒有更高層次的llvm？

09-04

LLVM不assume runtime，所支持的特性也很小，所以難以應用於有runtime的語言（比如Java，Haskell，OCaml。。）
所以，能否做一個更高級的llvm，加入多一點assumption（有adt，closure，boxing，reference，基本上就是SML簡化，利用這三個來做GC），然後能優化pattern matching/deforestation/unpack，再加上cps/monorphization/anf等大家都要的pass，這樣就不需要Haskell/OCaml/SML都重新實現這些。。但是又不像CLI/JVM assume那麼多（RTTI/Reflection）
Object應該也可以通過編譯成dictionary of function with self來實現吧？

不怎麼會編譯器，如果有什麼常識性錯誤，多多包涵。

我有一個，因為需求的差異，沒有做得多high level。開發中且諸多功能可用。

thautwarm/LLAST?

github.com

從問題關注度看起來，提供llvm上的high level language constructs好像是一種真實的需求。

其實llvm是有提供c++的ir builder, 但這個東西，無論是從身邊人的反響，還是個人的體驗，都實在算不上好。原因很簡單，c++那邊api的抽象層次有一些不太一致，一個比較簡單的說明就是，有些時候，你用著結構化的數據結構(Value, Function, Module)去進行high level的構造，但有些時候你卻要寫Builder.CreateXXX這種和拼字元串只隔了一張紙的操作 —— 如果拼積木時，以最少數量的幾塊大積木，便足以構造出絕大多數工作正常的積木建築，你為什麼非要拿著一些小積木去拼拼湊湊呢？

假如你可以做一套用ADT寫的、能正交且完備地表達llvm ir的抽象(具體地說可以就是一套AST)，不管我們是什麼語言，設計了怎樣的奇奇怪怪的語法、語義，我們只要最後往那套標準的AST上做一個轉換，就是一個可靠且高效的後端，何如？

如果有這樣一套標準抽象，我們可以共享所有優化的pass，方便集成各種各樣的後端優化;

如果有這樣一套標準抽象，我們可以不再糾結於拼字元串，讓codegen/emit變得優雅；

如果有這樣一套標準抽象，我們可以將永遠抵達相對於當前極為舒適的抽象層次，忘記長時間刀耕火種的過去，並且在新的高度互噴互扯互黑，用新的姿勢水平迎接新的挑戰...

當然上面幾句話下來我自己都覺得有點浮誇，因為，事實上必然需要有人處在更low level的層次做優化。但是，一套標準抽象的出現可以明確地制訂抽象層次的分界線，low level的大佬專心於如何在某種狀態下的某些AST優化到某種程度，而high level的用戶(jit框架的作者們，語言的創造者們)則只專心於語義和組合。

而我呢，從幾個月前開始，就因為各種各樣的原因在找這樣的抽象。像ocaml的binding這樣的。

Codegen.ml?

github.com

| Ast.Call (callee, args) -&> ... | Ast.If (cond, then_, else_) -&> ... | Ast.For (var_name, start, end_, step, body) -&> ...

就一個簡單的visitor，多好。

不過ocaml binding本身並沒有這種配置，這裡只是ocaml實現的Kaleidoscope里搞的一些簡單的抽象。並且，這邊的construct層次過於高了一點。

在我的實現里，原先也是把控制流寫死成if-expr, for-expr, yield三種，而我mentor認為應該把label, branch, switch這些加入，仔細思考後我覺得很對：if-else, loop, generator之類的，讓用戶拼ast拼出它們根本不是什麼麻煩的事情，而且如果用戶需要實現pattern matching，也有最大限度的優化許可權。

當然代價也不是沒有的，估計是因為我還比較菜，允許了各種什麼什麼鬼的branch之後，有些情況下類型安全變得非常難以保證(主要是沒有拒絕用戶寫一些畸形的代碼，比如在let ... in ...里突然跳出let作用域)，unification估計是也沒法在這一層做了。。

(下面是一個我實現一個具體的if的示例，當然這裡為了便於示意強行使用branch。實際上，這種判斷進行前就可以得到iftrue和iffalse結果的if應該用select指令。

let cond = Bin(Eq, Const &<| ID(32, 10L), Get("arg1")) let branch = Branch(cond, "truelabel", "falselabel") let iftrue = Suite([Mark "truelabel"; Store(Get "result", Const &<| ID(32, 100L))]) let iffalse = Suite([Mark "falselabel"; Store(Get "result", Const &<| ID(32, 10L))]) let ifexp = Let("result", Alloca(I 32, None), Suite([branch; iftrue; iffalse; Load(Get "result")]))

actually我們需要的，正是上圖中那些Branch, Bin, Get, Let, Suite...之類的東西。

這種抽象看起來似乎並不是很難，但是你真動手的話，很容易變成一對一翻譯llvm（笑

我花了比較多的時間在上面，雖說參閱了不少資料，但靠譜的也不是很多。

我認為比較有價值的是llvm-hs-pure和這篇文章(尤其是裡面那個BNF，我喜歡的就是這種...), 但是我認為它們也還是有相當一些「不足」的，比如llvm-hs-pure用起來可能和手寫LLVM IR差得不是很多... 如果你看過我寫過的parser generator和type checker，你就會發現某些領域裡我在優化易用性，復用性和冗餘度這些事上相當地執著。

int8 ----- I 8 float32 ----- F 32 // 放心, 試圖構造float85會在編譯期(雖然是compiler的運行期...)報錯， // 但隨時等候著llvm更新，並輕易地進行擴展。

sitofp & to & ----- CompatCast(&, F 64) // 避免用戶構造ast時還需要考慮是什麼cast，我們可以默認使用算術意義上的轉換， // 並分離出 zext和bitcast 兩個特殊指令

正是因為在這種東西上下功夫，才可能幫high level用戶徹底地抹除那些在抽象世界裡的坑窪和丘陵。過高的易用性可能會有代價，但是不能因此就爭做易用性窪地。

雖然上面吹了很多，我自己的實現卻也並非做到多好。事實上，得益於mapping-high-level-constructs-to-llvm-ir和我自己的積累，我可能知道幾乎所有的high level language constructs的llvmir實現，從generator到zero cost exception handling，從(mutable/once)lambda到union type到interface，即使是pattern matching，有過數個語言相關的動態、靜態實現的我也實在說不上不熟。但即便如此，想要完成理想中那個完備且正交的抽象，也還是需要相當的時間。

以下給出我的抽象核心(發現blockaddress沒加，明兒加...)

module LLVM.IR


type location = {

(**

for location resolving in exception reporting.

   *)

    filename: string

    lineno  : int

    colno   : int

}
type a undecided = {

(**

for prospective partial processing at AST level.

   *)

    id: int

}
type v asoc_list = (string * v) list
type ``type`` =

| I     of bit: int

| F     of bit: int

| Arr   of len: int * ``type``

| Vec   of len: int * ``type``

| Agg   of ``type`` list

| Func  of ``type`` list * ``type``

| Ptr   of ``type``

| Alias of name: string

| Label      (** not sure to handle make abstractions for label type*)

| Terminator (** only works when jump appears inner expression.*)

| Void

| PendingTy of ``type`` undecided
type llvm =

| Bin         of binary_operation
(** application *)

| App         of llvm * llvm list
(** get local var *)

| Get         of name: string
(** bind local var which create new context*)

| Let         of name: string * value: llvm * body: llvm
(** define function **)

| Defun       of name: string * args: ``type`` asoc_list * ret_ty: ``type`` * body : llvm
| Decl        of name: string * arg_tys: ``type`` list * ret_ty: ``type``
| Const       of constant
| DefTy       of name: string * ``type`` list
(** control flow*)

| Switch      of cond: llvm * cases: (llvm * string) list * default: string

| IndrBr      of cond: llvm * labels: string list

| Return      of llvm

| Mark        of name: string (** make label*)

| Branch      of cond: llvm * iftrue: string * iffalse: string

| Jump        of label: string
(** conversions: trunc, fptrunc, ..., bitcast *)

| ZeroExt     of src: llvm * dest: ``type``    // zext; Ext means extending

| CompatCast  of src: llvm * dest: ``type``

| Bitcast     of src: llvm * dest: ``type``
(** data accessing and manipulations *)

(**

including: load, store, alloca, getelementptr

           for aggregate:

            extractvalue

            insertvalue

           for vec:

            extractelement

            insertelement

*)

| Alloca      of ``type`` * data: llvm option

| Load        of subject: llvm

| Store       of subject: llvm * data: llvm

| GEP         of subject: llvm * idx : llvm * offsets: int list

| ExtractElem of subject: llvm * idx: llvm

| InsertElem  of subject: llvm * val: llvm * idx: llvm

| ExtractVal  of subject: llvm * indices: int list

| InsertVal   of subject: llvm * val: llvm * indices: int list
(** others *)

| Suite       of llvm list

| Locate      of location * llvm

| PendingLLVM of llvm undecided
and binary_operator =

| Add

| Sub

| Mul

| Div

| Rem

| LSh

| LShr

| AShr

| And

| Or

| XOr

// comparator

| Eq

| Gt

| Ge

| Lt

| Le

| Ne

| PendingBinOp of binary_operator undecided
and binary_operation = binary_operator * llvm * llvm

OCaml 的 Unlambda，了解一下

http://microvm.org?

microvm.org

這個項目可能和你的描述有些接近。IR接近LLVM，但集成了大部分需要的runtime語義，比如垃圾回收、異常處理、線程/棧的管理等等。

但在設計上並沒有加入那些你提到的「大家都要的pass」。其實你列出的那些優化，針對函數式語言比較通用。對於過程式語言、面向對象的語言，都會需求不同的「大家都要的pass」。這個項目的設計思路是，保證IR底層，加入runtime的支持，同時允許在IR上有效率的實現那些「大家都要的pass」。

zetavm/zetav
libcxx/coreVM
dirk/hivm
eclipse/omr

有，Common Lisp 就是。（真顏）

Runtime 和 IO 直接都有了。對生成彙編和內存表示的控制力也比較強，GC 都可以自己按需實現。反正都有 Yale Haskell 這種先例了。等 Lisp OS 項目完成，自定義個系統級別功能都不是事兒，為了方便指令層次優化，就專註 RSIC-V 好了。

還可以實驗用 MOP 實現編譯器優化啥的（編不下去了……

PS: 前段日子 Robert S. 在 irc 里問了 RMS 寫 GCC 的時候為什麼沒有用 Lisp，比如 MacLisp 什麼的……

有，JavaScript就是