MinCamlのコンパイル時の中間コードを出力してみる
#OCaml #MinCaml
MinCamlのコンパイル時の中間コードを画面に出力してみた時の覚え書き。
まとめはこちら → MinCamlの中間コード出力方法まとめ
実行環境について
中間コードを画面に表示するにあたり、OCamlの対話環境を利用する。MinCamlビルド時に一緒に生成される min-caml.top を実行することでMinCamlのライブラリがロード済みの対話環境を起動できる
また、手元のMac環境では min-caml も min-caml.top も動かないので、事前に用意してるDocker環境で実行する必要がある
code:sh
$ docker run -it --rm -v pwd:/root -w /root my/min-caml bash
# ./min-caml.top
手作業でアセンブリコードを出力（最適化なし）
min-caml.top の上で以下のコードを実行することでアセンブリコードを出力できる（最適化の呼び出しは省略している）
code:ml
let src = "let x = 123 in print_int x" in Emit.f stdout (RegAlloc.f (Simm.f (Virtual.f (Closure.f (Alpha.f (KNormal.f (Typing.f (Parser.exp Lexer.token (Lexing.from_string src)))))))));;
出力結果はこんな感じ。
code:sh
$ ./min-caml.top
# let src = "let x = 123 in print_int x" in Emit.f stdout (RegAlloc.f (Simm.f (Virtual.f (Closure.f (Alpha.f (KNormal.f (Typing.f (Parser.exp Lexer.token (Lexing.from_string src)))))))));;
free variable print_int assumed as external
register allocation: may take some time (up to a few minutes, depending on the size of functions)
generating assembly...
.text
.globl _min_caml_start
.align 2
_min_caml_start: # main entry point
stp fp, lr, sp, -16!
# main program starts
mov x0, 123
stp fp, lr, sp, -16!
bl _min_caml_print_int
ldp fp, lr, sp, 16
# main program ends
ldp fp, lr, sp, 16
ret
- : unit = ()
#
手作業でアセンブリコードを出力（最適化あり）
以下の方法を使って最適化ありでアセンブリコードを出力することもできる。
code:ocaml
let limit = ref 1000
;;
let rec iter n e = (* 最適化処理をくりかえす (caml2html: main_iter) *)
Format.eprintf "iteration %d@." n;
if n = 0 then e else
let e' = Elim.f (ConstFold.f (Inline.f (Assoc.f (Beta.f e)))) in
if e = e' then e else
iter (n - 1) e'
;;
let lexbuf outchan l = (* バッファをコンパイルしてチャンネルへ出力する (caml2html: main_lexbuf) *)
Id.counter := 0;
Typing.extenv := M.empty;
Emit.f outchan
(RegAlloc.f
(Simm.f
(Virtual.f
(Closure.f
(iter !limit
(Alpha.f
(KNormal.f
(Typing.f
(Parser.exp Lexer.token l)))))))))
;;
lexbuf stdout (Lexing.from_string "let x = 123 in print_int x")
;;
出力された「詳細情報」と「アセンブリコード」
code:assembly.asm
free variable print_int assumed as external
iteration 1000
register allocation: may take some time (up to a few minutes, depending on the size of functions)
generating assembly...
.text
.globl _min_caml_start
.align 2
_min_caml_start: # main entry point
mflr r0
stmw r30, -8(r1)
stw r0, 8(r1)
stwu r1, -96(r1)
# main program starts
li r2, 123
mflr r31
stw r31, 4(r3)
addi r3, r3, 8
bl min_caml_print_int
subi r3, r3, 8
lwz r31, 4(r3)
mtlr r31
# main program ends
lwz r1, 0(r1)
lwz r0, 8(r1)
mtlr r0
lmw r30, -8(r1)
blr
- : unit = ()
MinCamlのデータフロー
MiniCamlで書かれたソースコードからアセンブリコードまでの変換は以下の手順で行われる。それぞれの出力を確認してみる
Lexer.from_string（字句解析その１）
入力：MiniCamlソース
出力：Lexing.lexbuf
Lexer.token（字句解析その２）
入力：Lexing.lexbuf
出力：Parser.token
Parser.exp（構文解析）
入力：Parser.token
出力：Syntax.t
Typing.f（型推論）
入力：Syntax.t
出力：Syntax.t
KNormal.f（K正規化）
入力：Syntax.t
出力：KNormal.t
Alpha.f（アルファ変換）
入力：KNormal.t
出力：KNormal.t
=== 最適化処理ここから ===
Beta.f（ベータ簡約）
入力：KNormal.t
出力：KNormal.t
Assoc.f（ネストしたletの簡約）
入力：KNormal.t
出力：KNormal.t
Inline.f（インライン展開）
入力：KNormal.t
出力：KNormal.t
ConstFold.f（定数畳み込み）
入力：KNormal.t
出力：KNormal.t
Elim.f（不要定義削除）
入力：KNormal.t
出力：KNormal.t
=== 最適化処理ここまで ===
Closure.f（クロージャ変換）
入力：KNormal.t
出力：Closure.prog
Virtual.f（仮想マシンコード生成）
入力：Closure.prog
出力：Asm.prog
Simm.f（13bit即値最適化）
入力：Asm.prog
出力：Asm.prog
RegAlloc.f（レジスタ割り当て）
入力：Asm.prog
出力：Asm.prog
Emit.f（アセンブリ生成）
入力
出力チャンネル
Asm.prog
出力：
（出力チャンネルへソースコードが出力される）
字句解析と構文解析（Lexer → Parser）
対話環境で以下のコードを入力することで、MiniCamlで書かれたソースコードに対してを字句解析（Lexer）と構文解析（Parser）が行われて構文木が返る
code:ocaml
let parse s =
let l = Lexing.from_string s in
Parser.exp Lexer.token l
;;
let s = "let x = 4649 in print_int x" in parse s
;;
code:出力結果.ocaml
(* 出力結果 *)
- : Syntax.t =
Syntax.Let (("x", Type.Var {contents = None}), Syntax.Int 4649,
Syntax.App (Syntax.Var "print_int", Syntax.Var "x"))
型推論（Typing）
Letのx が型推論されて Type.Int になってる（st は Syntax Tree（構文木） の略）
code:ocaml
let st = Syntax.Let (("x", Type.Var {contents = None}), Syntax.Int 4649, Syntax.App (Syntax.Var "print_int", Syntax.Var "x")) in
Typing.f st
;;
code:出力結果.ocaml
- : Syntax.t =
Syntax.Let (("x", Type.Int), Syntax.Int 4649,
Syntax.App (Syntax.Var "print_int", Syntax.Var "x"))
K正規化（KNormal）
構文木が正規化されてK正規形の形で返される
code:ocaml
let st = Syntax.Let (("x", Type.Int), Syntax.Int 4649, Syntax.App (Syntax.Var "print_int", Syntax.Var "x")) in
KNormal.f st
;;
code:出力結果.ocaml
- : KNormal.t =
KNormal.Let (("x", Type.Int), KNormal.Int 4649,
KNormal.ExtFunApp ("print_int", "x"))
アルファ変換（Alpha）
異なる変数に異なる名前をつけるため、x が x.1 などにリネームされる
code:ocaml
let k = KNormal.Let (("x", Type.Int), KNormal.Int 4649, KNormal.ExtFunApp ("print_int", "x")) in
Alpha.f k
;;
code:出力結果.ocaml
- : KNormal.t =
KNormal.Let (("x.1", Type.Int), KNormal.Int 4649,
KNormal.ExtFunApp ("print_int", "x.1"))
クロージャ変換（Closure）
ネストした関数定義を平らにするのがクロージャ変換（まだピンと来ていない）
合わせて KNormal.t から Closure.t への変換が行われる
code:ocaml
let k = KNormal.Let (("x.1", Type.Int), KNormal.Int 4649, KNormal.ExtFunApp ("print_int", "x.1")) in
Closure.f k
;;
code:出力結果.ocaml
- : Closure.prog =
Closure.Prog ([],
Closure.Let (("x.1", Type.Int), Closure.Int 4649,
Closure.AppDir (Id.L "min_caml_print_int", "x.1")))
仮想マシンコード生成（Virtual）
中間コード（K正規形、クロージャ変換後の中間コード）からよりターゲットアーキテクチャ（SPARC、MIPS、x86、RISC-Vなど）に類似した仮想マシンコードを生成する。
どう「仮想」かというと
変数（レジスタ）が無限にある
ブランチやジャンプの代わりに「if-then-else」や「関数呼び出し」がある
の2点が主となる（らしい）
Asm.prog が返る。
virtual.ml 以降の処理はターゲットアーキテクチャごとに作成し直す必要がある。
code:ocaml
let c = Closure.Prog ([], Closure.Let (("x.1", Type.Int), Closure.Int 4649, Closure.AppDir (Id.L "min_caml_print_int", "x.1"))) in
Virtual.f c
;;
code:出力結果.ocaml
- : Asm.prog =
Asm.Prog ([], [],
Asm.Let (("x.1", Type.Int), Asm.Li 4649,
Asm.Ans (Asm.CallDir (Id.L "min_caml_print_int", "x.1", []))))
13bit即値最適化（Simm）
（あとで調べる）
レジスタ割り当て（RegAlloc）
x.1 が %r2 になってる
code:ocaml
let a = Asm.Prog ([], [], Asm.Let (("x.1", Type.Int), Asm.Li 4649, Asm.Ans (Asm.CallDir (Id.L "min_caml_print_int", "x.1", [])))) in
RegAlloc.f a
;;
code:出力結果.ocaml
- : Asm.prog =
Asm.Prog ([], [],
Asm.Let (("%r2", Type.Int), Asm.Li 4649,
Asm.Ans (Asm.CallDir (Id.L "min_caml_print_int", "%r2", []))))
アセンブリ生成（Emit）
仮想マシンコードを食わせてアセンブリソースを出力する
code:ocaml
let a = Asm.Prog ([], [], Asm.Let (("%r2", Type.Int), Asm.Li 4649, Asm.Ans (Asm.CallDir (Id.L "min_caml_print_int", "%r2", [])))) in
Emit.f stdout a
;;
code:出力結果.ocaml
.text
.globl _min_caml_start
.align 2
_min_caml_start: # main entry point
mflr r0
stmw r30, -8(r1)
stw r0, 8(r1)
stwu r1, -96(r1)
# main program starts
li r2, 4649
mflr r31
stw r31, 4(r3)
addi r3, r3, 8
bl min_caml_print_int
subi r3, r3, 8
lwz r31, 4(r3)
mtlr r31
# main program ends
lwz r1, 0(r1)
lwz r0, 8(r1)
mtlr r0
lmw r30, -8(r1)
blr
- : unit = ()
参考
速攻MinCaml コンパイラ概説
https://esumii.github.io/min-caml/index.html
MinCaml のコードリーディング
【メモ】CPUアーキテクチャごとに異なるソースとその内容
asm.ml （Virtual.f 以降の中間コードの定義）
virtual.ml （K正規形 → asm中間コード）
simm.ml （即値最適化？）
regAlloc.ml （レジスタ割り当て？）
emit.ml （asm中間コード → アセンブリコード）
libmincaml.S （ライブラリ関数）