LoginSignup
70
66

More than 5 years have passed since last update.

言語実装Advent Calendar 2016Day 12
@yuhr

Lisp系自作言語のx86_64コンパイラを作り始めたときの話

Last updated at Posted at 2016-12-11

ふと、あなた1は、Lisp風の新しいプログラミング言語と、そのネイティブコンパイラとを作りたい、と思い立ちました。

Common LispやSchemeのネイティブコンパイラは、いったいどのように作られているのか？ 既存の実装のソースコードを繙ひもとけばいい話ではある。しかしそこではきっと、クロスプラットフォームにするための非本質的なコードが繰り広げられているに違いない。まずは自分のアタマで、Lisp系言語のネイティブコンパイラに求められる本質的な要素をゼロから考えてみようじゃないか。

この記事では、ガベコレの仔細やインライン展開などの最適化は扱いません。あくまでLispコードのネイティブコードへのコンパイラを初めて実装したときの備忘録的なものです。アセンブリは少しわかるけどマシンコードを直接読むのは初めてという人向け。

何コンパイル？

どのようにネイティブコンパイラを作るかということでいろいろ検索してみたのですが、そもそもここで言うネイティブ（コード）というのはバイトコードと対比したときの言い方であって、あえてネイティブコンパイラを調べる必要はないことに気づきました。じゃあ普通の（Cなどの）コンパイラとLispコンパイラとの違いって何だろう？ 実行時コンパイルというやつか？

インクリメンタルコンパイルという用語は、聞いたことはあるものの詳しい意味を知りませんでした。「インクリメンタルコンパイル」で検索したところ、出てきたのはハードウェア分野における用例のみで、ソフトウェアのコンパイルの話ではないように思えました。"incremental compile" で検索すると、ようやく2Wikipediaにそのページがあり、Interactive programmingというセクションに以下のようなことが書いてありました。

... The compiler can be invoked at runtime on some source code or data structure managed by the program, which then produces a new compiled program fragment containing machine code that is then immediately available for use by the runtime system. If the newly compiled fragment replaces a previous compiled procedure the old one will be garbage collected. This scheme allows for a degree of self-modifying code and requires metaprogramming language features. ...

まさにLispのことを言っているかのような記述がありました。特にメタプログラミングというのはLispの十八番でもありますよね。このページには同時に "... incremental compiler recompiles only those portions of a program that have been modified." とも書いてあります。まとめると、

  • 変更部分だけを再コンパイルし、古い定義は捨てる
  • 実行時にプログラムがコンパイラを呼べる
  • コンパイル後のマシンコードが実行時システムからすぐさま利用可能である

というような性質が、少なくとも対話的プログラミングにおけるインクリメンタルコンパイルの本質のようです3。

どうやるの？

とりあえずLispコンパイラにインクリメンタルコンパイルという方式が求められるらしいことと、その方式の要点を掴むことはできました。一般的にネイティブコンパイラとは、構文木を引数にとり、ネイティブコードを返す関数であると看做せますよね。問題はこれをどのようにしてインクリメンタルに行うかです。おそらく、構文木を解析して変換したネイティブコードを動的に確保したメモリ領域に書き込むことになるでしょう。そのアドレスを関数ポインタとして呼び出すわけですね。

そのものずばりなページがありました。普通に確保しただけでは、メモリ領域を関数として実行することはできないようです。

本来、こういうページ領域上にバイトコードを置いて、それを呼び出そうとしても、
実行できないように設定されています。

（実行できるようになっていると、プロセスに脆弱性があったとき、悪意のあるコードを攻撃者から送信されて、実行されてしまう危険性が格段に上がる）

ですが、さすがに完全に実行できないと、Java VM をはじめとしたソフトウェアが稼働できなくなってしまうため、
OSから実行可能にフラグを書き換えるAPIが提供されています。

とりあえずLinuxで動けばいいので、mprotectを呼ぶと良いみたいですね。

実行可能なバイトコードは、x86 プロセッサ共通なので、同じプロセッサならどれでも動きますが、
各オペレーティングシステムに合わせて、上記に挙げた関数を利用して、実行可能に設定する必要があります。

まずはアセンブリで機械語を学ぶ

ようやくネイティブコードを弄る段階に入れます。演算をマシンコードに変換するにはまず、どのマシンコードがどの命令に対応するのか知る必要があります。とりあえず命令セットはx86_64に絞るとしましょう。ニーモニックとマシンコードとの対応表はどこかに載っているかなと思って検索したら、それっぽいものがこれしかなかったのですが（Intelによる仕様書にも載っているらしいですが、ページ数が多すぎて探すのを断念しました）、各カラムの説明を読んでも理解できず……これなら、アセンブリコードと、それをアセンブルした実行可能ファイルのマシンコードとを見比べた方が早いですね。

fasmのコード例が参考になりそうです。中でもLinux AMD64 examplesというセットに含まれているconsole/00/a00.fasmというファイルがとてもシンプルで短いので、全文引用させていただきます。

console/00/a00.fasm
; fasm demonstration of writing 64-bit ELF executable
; note that linux from kernel 2.6.??? needs last segment to be writeable
; else segmentation fault is generated
; compiled with fasm 1.66

; syscall numbers: /usr/src/linux/include/asm-x86_64/unistd.h
; kernel parameters:
; r9    ; 6th param
; r8    ; 5th param
; r10   ; 4th param
; rdx   ; 3rd param
; rsi   ; 2nd param
; rdi   ; 1st param
; eax   ; syscall_number
; syscall
;
; return register:
; rax   ; 1st
; rdx   ; 2nd
;
; preserved accross function call: RBX RBP ESP R12 R13 R14 R15
;
; function parameter (when linked with external libraries):
; r9    ; 6th param
; r8    ; 5th param
; rcx   ; 4th param
; rdx   ; 3rd param
; rsi   ; 2nd param
; rdi   ; 1st param
; call library

format ELF64 executable at 0000000100000000h    ; put image over 32-bit limit

segment readable executable

entry $

    mov rdx,msg_size    ; CPU zero extends 32-bit operation to 64-bit
                ; we can use less bytes than in case mov rdx,...
    lea rsi,[msg]
    mov edi,1       ; STDOUT
    mov eax,1       ; sys_write
    syscall

    xor edi,edi     ; exit code 0
    mov eax,60      ; sys_exit
    syscall

segment readable writeable

msg db 'Hello 64-bit world!',0xA
msg_size = $-msg

このコードをアセンブルすると、以下のようなプログラムになります。ハローワールドですね。目標は、これと同じ挙動をするプログラムを、Lispの構文木からネイティブコンパイルして実行できるようにすることです。

$ ./a00
Hello 64-bit world!

このプログラムの中身は以下のようになっています。このマシンコードとさきほどのアセンブリコードとを見比べていきます。とりあえず今は、エントリポイントからの処理をマシンコードに変換するだけでよく、実行可能ファイルにまでする必要はないので、ELF64ヘッダはほとんど読み飛ばします。バイナリの0x00000018の位置（2行目の右半分）にちょうどエントリポイントの位置（ELF64ヘッダ構造体Elf64_EhdrのElf64_Addr e_entry;メンバにあたる情報）が0x00000001000000b04と記録されているので、そこから読み始めるとすぐに処理に入れます。

$ hexdump -C a00
00000000  7f 45 4c 46 02 01 01 00  00 00 00 00 00 00 00 00  |.ELF............|
00000010  02 00 3e 00 01 00 00 00  b0 00 00 00 01 00 00 00  |..>.............|
00000020  40 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |@...............|
00000030  00 00 00 00 40 00 38 00  02 00 40 00 00 00 00 00  |....@.8...@.....|
00000040  01 00 00 00 05 00 00 00  b0 00 00 00 00 00 00 00  |................|
00000050  b0 00 00 00 01 00 00 00  b0 00 00 00 01 00 00 00  |................|
00000060  21 00 00 00 00 00 00 00  21 00 00 00 00 00 00 00  |!.......!.......|
00000070  00 10 00 00 00 00 00 00  01 00 00 00 06 00 00 00  |................|
00000080  d1 00 00 00 00 00 00 00  d1 10 00 00 01 00 00 00  |................|
00000090  d1 10 00 00 01 00 00 00  14 00 00 00 00 00 00 00  |................|
000000a0  14 00 00 00 00 00 00 00  00 10 00 00 00 00 00 00  |................|
000000b0  ba 14 00 00 00 48 8d 35  15 10 00 00 bf 01 00 00  |.....H.5........|
000000c0  00 b8 01 00 00 00 0f 05  31 ff b8 3c 00 00 00 0f  |........1..<....|
000000d0  05 48 65 6c 6c 6f 20 36  34 2d 62 69 74 20 77 6f  |.Hello 64-bit wo|
000000e0  72 6c 64 21 0a                                    |rld!.|
000000e5

アセンブリコードでは以下のあたりからエントリポイントが始まります。このプログラムでは、システムコールsys_writeで標準出力にハローワールドしたのち、sys_exitで終了しています。簡単ですね。

segment readable executable

entry $

    mov edx,msg_size    ; CPU zero extends 32-bit operation to 64-bit
                ; we can use less bytes than in case mov rdx,...
    lea rsi,[msg]
    mov edi,1       ; STDOUT
    mov eax,1       ; sys_write
    syscall

    xor edi,edi     ; exit code 0
    mov eax,60      ; sys_exit
    syscall

segment readable writeable

msg db 'Hello 64-bit world!',0xA
msg_size = $-msg

まずエントリポイントに入ると、mov edx,msg_sizeという命令が見えます。コード前半に付いているコメントの、以下の部分を読むと、rdxはシステムコールの第3引数として扱われるようです。ちなみにrdxのように先頭がrのレジスタは64ビットレジスタで、eはその下位32ビット部分を意味します5。

; rdx   ; 3rd param
; rsi   ; 2nd param
; rdi   ; 1st param
; eax   ; syscall_number
; syscall

sys_writeの引数にはそれぞれ、書き込み先のファイルデスクリプタ1、書き込み内容のあるメモリ領域のアドレス[msg]、書き込むサイズmsg_sizeが渡されています。

msg_sizeというのは、コードの末尾に定義があります。$-msgという式の意味は、「現在行の先頭アドレスからmsg領域の先頭アドレスを引いた値」でしょうか。つまりこれはmsgという静的領域のサイズを表現する値――ここではHello 64-bit world!\nという文字列のサイズである0x14――です。アセンブル後のバイナリにこの値を見つけられるでしょうか？ エントリポイントが0x000000b0ということはわかっているので、そこから辿っていくと……。

000000b0  ba 14 00 00 00 48 8d 35  15 10 00 00 bf 01 00 00  |.....H.5........|
             ^^ ^^ ^^ ^^

ここです。本来x86_64環境でのメモリ領域のサイズ表現は8バイトのはずですが、コメントにもあるとおり、ここではmov edx,...しているので、4バイトぶんだけで済んでいるようです6。さきほどは読めなかった対応表から0xbaに対応する命令を探してみます。このコードは、B8+r以上C0未満に対応しているMOVニーモニックに当てはまるようです。どうも単純に単射ではないようです。+rは0から7までのレジスタコードというものらしく、0xbaは0xb8+0x02なので、ここでのedxレジスタのコードは0x02にあたるのでしょう。

レジスタコードというのは、こちらのページに詳しい対応表があります。ちょうどRDXは2進数表記で010と書いてあるのでやはり0x02ですね。

だんだんわかってきました。次のシステムコールsys_exitでは、第1引数のためにxor edi,ediという処理をしているのが見えます。

    xor edi,edi     ; exit code 0
    mov eax,60      ; sys_exit
    syscall

これは単純に0を格納するのと同じことです。たしか、新しい即値をレジスタに入れるよりも、レジスタに既存の値で演算した方が効率が良いからこのようにするんだったと思います。この方法は0の場合にしか使えず、現に次のシステムコール番号の設定では即値60をmovしています。

このようにして解読していくと、それぞれの命令について、以下のような対応関係が見えてきます。

アセンブリコード マシンコード
mov edx,msg_size ba 14 00 00 00
lea rsi,[msg] 48 8d 35 15 10 00 00
mov edi,1 bf 01 00 00 00
mov eax,1 b8 01 00 00 00
syscall 0f 05
xor edi,edi 31 ff
mov eax,60 b8 3c 00 00 00
syscall 0f 05

これでひとまず、プログラムコード部分のマシンコードの理解が終わりました。これ以降のコードはもう別のプログラムヘッダエントリになります。

これを見て下さい！ 最後の命令である0f 05の次のバイトは、息を吐く暇もなくHello 64-bit world!\nという文字列の最初の文字――Hえっちです。

000000c0  00 b8 01 00 00 00 0f 05  31 ff b8 3c 00 00 00 0f  |........1..<....|
000000d0  05 48 65 6c 6c 6f 20 36  34 2d 62 69 74 20 77 6f  |.Hello 64-bit wo|
000000e0  72 6c 64 21 0a                                    |rld!.|

んああぁっ♡ …気持ちぃ……いっ♡7

処理を関数で包む

さて実装――と行きたいところですが、まだ足りないものがあります。ここまで読んできたコードは、エントリポイントから直接実行に入っているものなので、関数に包まれていないナマのコードです。このまま呼び出してしまうと制御が返ってきません。呼び出し元に制御を戻す処理がないからです。

そして関数に呼び出し元がどこなのかを知らせるために、関数が呼び出される際には、呼び出し命令の次の命令のアドレスが関数に渡ります（これは暗黙的に行われます）。このとき、このアドレスはスタックという特別なメモリ領域に入ります。

さらに、いくつかの引数（x86_64では第6引数まではレジスタ経由で渡すので、第7引数からスタックに行きます）と、いわゆるローカル変数（クロージャなどのある言語ではヒープに行くこともあるでしょう）も同じくスタック領域に確保されます。基本的には、これらの変数と呼び出し元アドレスとを合わせてスタックフレームと呼びます。ヒープよりもスタックのがパフォーマンスが良いみたい。もっと最適化するなら局所関数とかをスタックに入れたりするのかな？

良い勉強の機会なので、さきほどのシステムコールsys_writeを呼び出しているコードを、関数として正しく呼び出せるように自分で改変してみることにします。以下のように呼び出せる関数をアセンブリで書いてみましょう。

    mov rsi,msg_size ; 2nd param
    lea rdi,[msg]    ; 1st param
    call print

第1引数に文字列の先頭を指すアドレス、第2引数に文字列のサイズを表現する整数を渡して、それを標準出力にプリントしたあと、何も値を返さずに制御を返すような関数です。

sys_write_stdout:
    mov edx,esi     ; 2nd arg to 3rd param
    mov rsi,rdi     ; 1st arg to 2nd param
    mov edi,1       ; STDOUT
    mov eax,1       ; sys_write
    syscall
    ret

このコードをエントリポイントの前あたりに挿入して、さきほどのコードで呼び出してみると、ちゃんとプリントされます。callで自動的に戻り先アドレスがスタックに積まれ、retでそれが降ろされて制御が返されます。今回は引数が2つだけでローカル変数も使わないので、スタック領域のさらなる確保は行っていません。これをアセンブルすると、プログラムコード部分は以下のようになります。

000000b0  89 f2 48 89 fe bf 01 00  00 00 b8 01 00 00 00 0f  |..H.............|
000000c0  05 c3 be 14 00 00 00 48  8d 3d 0e 10 00 00 e8 dd  |.......H.=......|
000000d0  ff ff ff 31 ff b8 3c 00  00 00 0f 05 48 65 6c 6c  |...1..<.....Hell|
000000e0  6f 20 36 34 2d 62 69 74  20 77 6f 72 6c 64 21 0a  |o 64-bit world!.|
000000f0
アセンブリコード マシンコード
mov edx,esi 89 f2
mov rsi,rdi 48 89 fe
mov edi,1 bf 01 00 00 00
mov eax,1 b8 01 00 00 00
syscall 0f 05
ret c3
アセンブリコード マシンコード
mov esi,msg_size be 14 00 00 00
lea rdi,[msg] 48 8d 3d 0e 10 00 00
call print e8 dd ff ff ff

sys_exitを呼び出すコードはさっきと同じなので省きます。48というのは、64ビット拡張の汎用レジスタへアクセスするための接頭辞です。r8とかの新しいレジスタを使うときにはこれが48ではなく49になります。オペランドを指定しているであろうf2やfeなどは、実はModR/Mという指定子で、さきほどちらっと紹介したページを読むと全部わかるのですが、ちょっとこれはめんどくさすぎるのでここでは体系的に解説はしません。

[msg]が0x0000100eと展開されています。2バイト目の0x10の意味が、上記のページを読んでもよくわからなかった8のですが、1バイト目の0x0eはどうもオフセットみたいです。次の命令の位置0x000000ceに0x0eを足すと0x000000dcとなり、ちょうど文字列の開始位置になります。

そして最後の命令であるcallへ渡されているアドレスがdd ff ff ffとなっていますが、こんなのは明らかに負の値ですよね。次の命令の位置0x000000d3から、0xffffffddの符号付き整数解釈である-35の位置まで数えてみるとわかります。35は0x23なので、0x000000d3から0x23を引くと0x000000b0、つまりsys_write_stdout関数の先頭を指しているわけです。

実行可能ファイルを直接読むのって、思ったより難しくない感じですね。ヘッダのリファレンスと適切な対応表とがあれば割とどうにかなってしまいます。他にもいろいろアセンブリコードを書いてfasmに読ませてみると、いろいろな気付きがあって面白いです。

今回の実装では、上記の2つのマシンコードを実際に使ってみます。

計画

C++で実装します9。ソースコードを読み込んで構文木を構築する手続きについては、ここでは非本質的なため割愛します。これからやるべきことは、まずC++側でシンボルテーブルオブジェクトを作り、以下のような2つのエントリ

  • sys-write-stdout: ネイティブコード89 f2 48 89 fe bf 01 00 00 00 b8 01 00 00 00 0f 05 c3
  • msg: 文字列"Hello 64-bit world!"

を追加したのち、以下のようなLisp構文木

(sys-write-stdout msg)

を、ほにゃららして以下のようなネイティブコードにコンパイルすることです。

be 14 00 00 00
48 8d 3d 0e 10 00 00
e8 dd ff ff ff

もちろんこれを文字通り出力するのではなく、ヒープ領域の手続きや文字列へのアドレスをシンボルテーブルから解決し、うまいこと組み合わせて、関数ポインタとして実行できるコードをがんばって作ってみます。

最小限の言語仕様

この記事の冒頭で言ったとおり、あなたの真の目的は自分の言語とその処理系を作ることなので、言語仕様から考えてみます。それでいて、できるだけ上記の問題を単純化するような最小限の部分だけを定めておきます。

  • Lisp方言の一
    • Lisp-1
    • シンボルの大文字小文字は区別
    • 構文木の要素
      • 式（ファーストクラスオブジェクト）
        • リスト（式と式のペア）
        • nil
        • シンボル（文字列）
        • 文字列
        • 手続き（ネイティブコード）
        • シンボルテーブル（シンボルと手続きのペア）
  • 実行されるコードは必ずネイティブコンパイル済であること
    1. 少なくともx86_64をサポート
    2. 評価とは構文木をコンパイルして実行すること
  • 少なくともLinuxで動く

構文木の論理表現

ここから実際にC++コードを見ていきます。まずは必要なヘッダをインクルードします。

#include <memory>
#include <string>
#include <functional>
#include <unordered_map>
#include <unistd.h>

さきに述べたように、ソースコードから構文木を構築する手続きについてはここでは扱いませんが、構文木をネイティブコードに変換するためには、構文木の論理表現をここで示しておく必要がありますね。上記の言語仕様の「式」それぞれについて、型を定義します。

enum expr_type // 第一級オブジェクト
{
  type_list,
  type_nil,
  type_symbol,
  type_string,
  type_procedure,
  type_symboltable,
};

次にこれらに対応するクラスを定義します。using namespace std;してあるとします。

class Expr // これを直接インスタンス化することはたぶんない
{
  public:
    expr_type type;
    Expr(expr_type t) : type(t) {}
    virtual ~Expr() {}
};
#define EXPR shared_ptr<Expr>
class List : public Expr
{
  public:
    EXPR car, cdr;
    List(EXPR a, EXPR d) : Expr(type_list), car(a), cdr(d) {}
};
class Nil : public Expr
{
  public:
    Nil() : Expr(type_nil) {}
};
class Symbol : public Expr
{
  public:
    string value;
    Symbol(string x) : Expr(type_symbol), value(x) {}
};
class String : public Expr
{
  public:
    string value;
    String(string x) : Expr(type_string), value(x) {}
};
class Procedure :public Expr
{
  public:
    uint8_t *code;
    Procedure(uint8_t *ptr) : Expr(type_procedure), code(ptr) {}
};
class SymbolTable :public Expr
{
  public:
    unordered_map<string, EXPR> table;
    SymbolTable() : Expr(type_symboltable) {}
};

単純な話で、NilやSymbolなどすべての構文木の要素はスーパークラスExprを継承するクラスです。ガベコレもここではどうでもいいのでshared_ptrの参照カウント頼りですね。さらに、構文木を手動で作るための便利なマクロを定義します。

#define CONS(a,d) (make_shared<List>((a),(d)))
#define NIL (make_shared<Nil>())
#define SYM(x) (make_shared<Symbol>(x))
#define STR(x) (make_shared<String>(x))
#define PROC(x) (make_shared<Procedure>(x))

inline EXPR LIST() { return NIL; }
template<typename T, typename ... Ts>
inline EXPR LIST(T const &head, Ts ... tail)
{ return CONS (head, LIST(tail ...)); }

inline EXPR CAR (EXPR e)
{ return ((static_pointer_cast<List>(e))->car); }
inline EXPR CDR (EXPR e)
{ return ((static_pointer_cast<List>(e))->cdr); }

インライン関数LISTは再帰でCONSしてるだけなんですが、なんだか異常に読みづらいし重要ではないので使い方だけ見ます。詳しく知りたい方は「可変長テンプレート」とかで検索してください。というかどうやってこれを書いたのかあなたもよく覚えていません。ロステクか？

LIST(SYM("quote"), LIST(SYM("the-answer"), SYM("is"), STR("forty-two")))

こんな感じに書けます。これは以下のS式表現と同じものです。

'(the-answer is "forty-two")

コンパイルの準備

何はともあれmain関数を定義します。最初の3つの変数はこのあと複数の関数から使うのでグローバルにしてしまいます。よいこはまねしないでね。

// グローバルな名前空間として使うシンボルテーブル
SymbolTable st;

// コンパイルしたコードを格納するメモリ領域
uint8_t *data;

// data の未使用領域へのオフセット
uint64_t offset = 0;

int main()
{
  // ここにコードを追加していく 

  return 0;
}

シンボルテーブルに追加するエントリを準備します。sys-write-stdoutはC++側であらかじめ用意してしまうことにしたので、まずそのネイティブコードをヒープメモリに用意します。

  // mprotect するためにはページサイズでアラインする
  long page_size = sysconf(_SC_PAGESIZE);
  posix_memalign((void **)&data, page_size, page_size);
  // 実行可能設定     
  mprotect((void *)data, page_size, PROT_READ | PROT_WRITE | PROT_EXEC);

ここがとんでもないつまづきポイントだったのですが、mprotectするメモリ領域はnewやmallocで普通に確保してもダメで、posix_memalignなどのアライメントを指定できるAPIでページ境界にアラインしてやる必要があります。以下のページにあるコードを見てようやくこのことに気が付きました。

ページ境界にアラインする必要があるということは、メモリ効率を考えるとページサイズ単位で確保するしかないということです。一見するとめんどくさそうに思えますが、コンパイル開始時にこのあとどれくらいのメモリ領域が必要になるかがわからないので、足りなくなったときだけまた新しくページ単位で確保するというのは、理にかなっているかもしれません。

メモリを確保したら、ネィティブコードを書き込みます。さきほど自分でアセンブリを書くことで得たsys_write_stdoutのマシンコードそのまんまです。

  // コードを書き込む 
  uint8_t _data[18] = 
    {0x89, 0xf2,      
     0x48, 0x89, 0xfe,
     0xbf, 0x01, 0x00, 0x00, 0x00,
     0xb8, 0x01, 0x00, 0x00, 0x00,
     0x0f, 0x05,      
     0xc3};           
  for(uint i=0; i<sizeof(_data); ++i)
    data[offset+i] = _data[i];
  offset += sizeof(_data);

上記コードのあとに、このようなテストコード

  char str[] = "hey\n";
  ((void (*)(const char *, size_t))data)(str, sizeof(str));

を書いてみると、ちゃんと以下のように出力されるはずです。

hey
^@

最後の^@はおそらく、C言語で文字列リテラルの末尾に暗黙的に追加されるヌル文字ですね。次はシンボルテーブルを整えます。

  st.table["sys-write-stdout"] = PROC(data);
  st.table["msg"]              = STR("Hello my compiler!\n");

解放処理も忘れないうちに、return 0;の前あたりに書いておきましょう。

  free(data);

コンパイル

さて、ここで一旦main関数は置いといて、main関数の直前に、構文木を評価する関数を作りましょう。

EXPR evaluate(EXPR e) { return execute(compile(e)); }

次はexecute関数です。簡単化のため、この関数で実行されるネイティブコードは常に引数を何も取らず値も返さない手続きとしましょう。アドバンスドな実装をするときにはもちろん返り値が必要になりますが、この記事ではそこまでやりません。常にnilを返します。

EXPR execute(shared_ptr<Procedure> p)
{ ((void (*)(void))(p->code))(); return NIL; }

いよいよ本命です。とりあえず動かせるだけのcompile関数を作っていきます。こちらも簡単化のため、まったく条件分岐を入れずに「渡される式はリストであること」「carは手続きに束縛されたシンボルであること」「cadrは文字列に束縛されたシンボルであること」を前提として処理してしまっています。言わば関数に文字列を一つ渡す処理専用のコンパイラですね。

shared_ptr<Procedure> compile(EXPR e)
{
  uint8_t *code = data + offset;
  vector<uint8_t> v (0);

  auto p = static_pointer_cast<Procedure>(st.table.at( (static_pointer_cast<Symbol>( CAR(e) ))->value ));
  auto s = static_pointer_cast<String>(st.table.at( (static_pointer_cast<Symbol>( CAR(CDR(e)) ))->value ));

  // ...

static_pointer_castのあたりは読まないほうが身のためです。渡された構文木のcarとcadrとを取り出して、シンボルと看做して解決し、得られたExprをそれぞれProcedureとStringとに決め打ちで型キャストしています。なんと横暴な！

これからvに1バイトずつ書き込んでいき、最後にcodeの位置にまるごとコピーします。今回のネイティブコードはさきほどのように改変なしではうまくいきません。何が問題なのか、もう一度コードを見てみましょう。

アセンブリコード マシンコード
mov esi,msg_size be 14 00 00 00
lea rdi,[msg] 48 8d 3d 0e 10 00 00
call print e8 dd ff ff ff

このコードの問題は、やはりret命令がないので呼び出すと制御が戻らないことと、call命令の呼び出し先がオフセットで指定されていることです。さらに、今回はヒープ領域に確保したメモリを実行するので、アドレスは8バイトになるはずですが、この命令では4バイトしか指定できなそうです。どうすればいいのでしょうか。

さきほどの見づらい対応表が役に立ちます。"call"でページ内検索をかけてみると、call命令に対応するコードがE8に加えてFFとあり、これしかなさそうです。再びfasmを引っ張り出してきてどのようにすればこのコードが生成されるのか試してみます。

まず思いつくのはcallにむりやり8バイト幅の即値を与えることです。たとえばcall 123456789abcdef0hみたいに。

$ fasm a00.asm
flat assembler  version 1.71.57  (16384 kilobytes memory)
a00.asm [50]:
  call 123456789abcdef0h
processed: call 123456789abcdef0h
error: relative jump out of range.

怒られてしまいました。では、64ビットレジスタをぶち込んでやるとどうなるでしょうか？

    mov rax,sys_write_stdout
    call rax
    ret

000000c0  05 c3 be 14 00 00 00 48  8d 3d 1b 10 00 00 48 b8  |.......H.=....H.|
000000d0  b0 00 00 00 01 00 00 00  ff d0 c3 e8 e2 ff ff ff  |................|
                                   ^^ ^^

完全にffになってます。ヒープ領域のアドレスはレジスタ経由で渡されるのがイイんですね？

それから、lea命令もmovでアドレスを転送することになるでしょう。まとめると、コンパイル結果は以下のようなコードにすればいいことになります。

アセンブリコード マシンコード
mov esi,<size of string> be xx xx xx xx
mov rdi,<address of string> 48 bf xx xx xx xx xx xx xx xx
mov rax,<function ptr> 48 b8 xx xx xx xx xx xx xx xx
call rax ff d0
ret c3

これをそのまま、べクタvにプッシュしていきます。

  // mov esi,<size of string>
  v.push_back(0xbe);
  uint32_t size = s->value.size();
  // 下位バイトからプッシュ
  for(uint i=0; i<4; ++i)
    v.push_back((size >> (i*8)) & 0xff);

  // mov rdi,<address of string>
  v.push_back(0x48);
  v.push_back(0xbf);
  for(uint i=0; i<8; ++i)
    v.push_back((((uint64_t)(&s->value[0])) >> (i*8)) & 0xff);

  // mov rax,<function ptr>
  v.push_back(0x48);
  v.push_back(0xb8);
  for(uint i=0; i<8; ++i)
    v.push_back((((uint64_t)(p->code)) >> (i*8)) & 0xff);

  // call rax
  v.push_back(0xff);
  v.push_back(0xd0);

  // ret
  v.push_back(0xc3);

こんなところでしょうか。最後に、実行可能に設定したメモリ領域にまるごとコピーします。

  for(uint i=0; i<v.size(); ++i)
    code[i] = v[i];
  offset += v.size();

  return PROC(code);
}

以上でcompile関数の実装は終わりです。

実行してみる

ようやくここまでこれました。evaluateに読み込ませるために心を込めて構文木を作り、献上します。1文字1文字丁寧にタイプしてください。

  // ...

  st.table["sys-write-stdout"] = PROC(data);
  st.table["msg"]              = STR("Hello my compiler!\n");

  EXPR e = LIST(SYM("sys-write-stdout"), SYM("msg"));
  evaluate(e);

  free(data);

  // ...

Hello my compiler!

デキタ！！！！！！！

あとがき

この記事は言語実装 Advent Calendar 2016の12日目のために書かれました。最初に予定していたよりも記事が長くなり、公開が少し遅れてしまいました（ごめんなさい）。ここでの実装はコンパイラ開発の第一歩にも過ぎないと思うのですが、何かしらの参考になれば幸いです。

メリクリ&よいお年を！ Archのロゴ、ちょっとクリスマスツリーっぽくないですか？

$ screenfetch
                   -`
                  .o+`                 yuhr@arche
                 `ooo/                 OS: Arch Linux 
                `+oooo:                Kernel: x86_64 Linux 4.8.10-1-ARCH
               `+oooooo:               Uptime: 0m
               -+oooooo+:              Packages: 1227
             `/:-:++oooo+:             Shell: bash 4.4.5
            `/++++/+++++++:            Resolution: 2560x1440
           `/++++++++++++++:           DE: Gnome 
          `/+++ooooooooooooo/`         WM: GNOME Shell
         ./ooosssso++osssssso+`        WM Theme: Adwaita
        .oossssso-````/ossssss+`       GTK Theme: Arc-Red-Darker [GTK2/3]
       -osssssso.      :ssssssso.      Icon Theme: la-capitaine-icon-theme
      :osssssss/        osssso+++.     Font: Noto Sans CJK JP 11
     /ossssssss/        +ssssooo/-     CPU: Intel Core i5-6600K CPU @ 4.6GHz
   `/ossssso+/:-        -:/+osssso+-   GPU: GeForce GTX 960
  `+sso+:-`                 `.-/+oso:  RAM: 755MiB / 7860MiB
 `++:.                           `-/+/
 .`                                 `/

  1. 筆者のことです。 ↩

  2. その後、いろいろ検索するうちに辿り着いたWikipedia日本語版の動的コンパイルというページに、増分コンパイルという用語がありました。聞いたことはありませんが、「Lispの一部（省略）で用いられている」と書いてあって、どうやらこれのことのようです。英語版のページにはちゃんと"Incremental compilation"と書いてありました。わかりにくい！ ↩

  3. インクリメンタルコンパイルがLispコンパイラで使われていることの本質的意味とは何でしょうか？ 例えばCLのリードマクロ定義は、展開後の式を返す式（つまりマクロ本体）がコンパイルされても、（set-macro-characterが）すぐさま実行されずリードテーブルにそのエントリが追加されないままだったら、それ以後のコードをリードするときに使うことができませんよね。そういうことでしょうか？ ↩

  4. リトルエンディアンなのでバイト単位で逆に記録されています。あと、今回はあまり関係なさそうなのでスルーしましたが、このfasmの例でなぜ"put image over 32-bit limit"しているのか、あなたはよくわかっていません。マニュアルを読んだりして理解したら追記するかもしれません。 ↩

  5. あなたはすでにmasm64でx86_64アセンブリをちょろっと触ったことがあるので、ここら辺は知っていました。レジスタはアセンブリ言語の基礎の基礎なので、知らない方はまずそちらを勉強すると理解がかなり円滑になるはずです。 ↩

  6. ただしfasmでは、ここを単純にmov rdx,msg_sizeとしても48 c7 c2 14 00 00 00のようにアセンブルされます。これはfasmによる最適化だと思います（もちろん他のアセンブラも似たようなことをやっていることでしょう）。実際、たとえばmov rdx,123456789abcdef0hのように8バイト幅の値を入れればちゃんと48 ba f0 de bc 9a 78 56 34 12のようにアセンブルされます。 ↩

  7. 無駄がなくて気持ちいいという意味です。 ↩

  8. 3dは0b00111101、すなわちRDIと[RIP + disp32]の組み合わせなので2バイト目以降も有効な情報のはずなんですが、たとえばlea rdi,[rip+0000000eh]とすると48 8d 3d 0e 00 00 00となって0x10は消えているのに問題なく動くし、かといってlea rdi,[rip+0000100eh]としてもちゃんと動く……なんもわからん…………。 ↩

  9. 単純にあなたが慣れているからというのが大きいです。あと他の言語ではファイルサイズの問題もありました。最初は、どうも関数型のパラダイムでは処理系を書きやすいみたいな話を耳にして、じゃあOCamlなんてどうだろう、ということで学習も兼ねて書き始めたのですが、ocamloptの吐くファイルのサイズが大きいのがいやでした。これさえじゅうぶんに小さかったなら、スレッドサポートが並列に動いてないらしいことも、intが31ビットであることも、ほとんど気にならなかったと思います。ヴァリアント型やパターンマッチは確かに強力だと思ったので、OCamlは言語の意味論としてはとても素敵だと思いました。もちろん、こなれてきたSchemeで書くという手もありました。ocamloptによるハローワールドが約240キロバイトなのに対し、あなたの好きな実装であるChez Schemeでは、ネイティブコンパイル後のファイルサイズは420バイトと、ここだけ見ればアセンブリにも迫らんとする（fasmでは229バイト！）驚異的な小ささなのですが、実を言うとこれはスタンドアロンの実行可能ファイルではない（ネイティブコードを圧縮したGzipアーカイブのようです）ので、処理系経由で実行する必要があります。つまり、アプリケーションを配布する際には、実行環境の方にもChez Schemeをインストールしてもらうか、あるいは処理系（約388キロバイトのファイル一つ）をアプリケーションにバンドルする必要があります。たしかSBCLでは、実行可能ファイルを作る際には実行環境のコアイメージごと埋め込むので、仕様の大きいCommon Lispの実装をまるごと抱え込むかたちになり、ファイルサイズが巨大に膨れ上がりますよね（うろ覚えですがハローワールドが数十メガバイトあったと思います）。これらはまあ、動的に構文木やシンボルを操作したりすることがあるので仕方ないのですが、そのためにも、処理系のファイルサイズというのは経済的に超重要なわけです。 ↩

70
66
4

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
70
66