はじめに
「RubyでつくるRuby ゼロから学びなおすプログラミング言語入門」(ラムダノート, Amazon) という本の影響で自分でもミニNode.jsインタープリターを作ってみました。
さらにポッドキャストのTuring Complete FMの影響も受けて、ミニコンパイラ作りにもチャレンジしています。
前回はLLVM IRの書き方を調べて見ました。今回はその成果をつかって整数リテラルと、足し算の実現まで目指します。
基本の構造
インタープリターの esprima --> simplify() の流れはそのまま利用します。
evaluate()で実行していた代わりに、compile()を用意して、中間表現であるLLVR IRのテキストを生成、ファイルに保存します。
- esprimaでjsのソースを読み込み、パース
- simplify()で単純化
- compile()でLLVR IRのテキストを生成、ファイルに保存
整数を返すだけのコード
目標とするLLVM IR
想像できる限り一番シンプルなコードからスタートします。元になるjsのソースはこちら。
1;
単純化したtreeはリテラルが1つになります。
[ 'lit', 1 ]
ここから次のIRを作ることが目標です。
define i32 @main() {
ret i32 1
}
コンパイル処理
ミニNode.jsインタープリター(Extra 2)で作ったモジュールを使い、ソースコードをパース、単純化します。
const tree = loadAndParseSrc();
// --- compile ----
const ll = compile(tree);
writeFile('generated.ll', ll);
compile()の中ではインタープリターと同様に単純化したTreeを再帰的に処理することになるので、その部分はgenerate()として別に用意しました。
// ---- compile simplified tree into LLVM IR ---
function compile(tree) {
let mainBlock = generate(tree);
let mainFunc = generateMain(mainBlock);
return mainFunc;
}
// ---- genereate LLVM IR block ---
function generate(tree) {
// --- int32 literal ---
if (tree[0] === 'lit') {
return tree[1];
}
println('-- ERROR: unknown node in generate() ---');
printObj(tree);
abort();
}
まだgenerate()では整数リテラルの値をそのまま返すだけしかできません。
その結果をつかって、main()関数を整えます。
const LF = '\n';
const TAB = ' ';
function generateMain(mainBlock) {
let block = '';
block = block + 'define i32 @main() {' + LF;
block = block + TAB + 'ret i32 ' + mainBlock + LF;
block = block + '}' + LF;
return block;
}
最後に、ファイルに保存しておきます。
const fs = require('fs');
function writeFile(filename, str) {
fs.writeFileSync(filename, str);
return null;
}
実行結果
ここまでのソースを mininode_compiler03.js、対象となるソースをone.jsとします。出力されるIRファイルはgenerated.llとしています。
$ node.js mininode_compiler03.js one.js
$ more generated.ll
define i32 @main() {
ret i32 1
}
$ lli generated.ll || echo $?
1
正しくコンパイル、実行できました！ 超ミニミニコンパイラーの完成です。
ここで対象ソースの整数をちょっと変えて、実行してみましょう。100, 200, 300とします。
$ lli generated.ll || echo $?
100
$ lli generated.ll || echo $?
200
$ lli generated.ll || echo $?
44
おっと、300の場合が予想と違いました。調べて見たらプロセスの終了コードは8ビット符号なし整数の範囲なのですね。300-256=44 ということで、計算は合っています。
足し算のコード
次の目標
ターゲットとするjsのソースはこちら。
4 + 5;
単純化したtreeはこのようになります。
[ '+', [ 'lit', 4 ], [ 'lit', 5 ] ]
ここから次のようなIRを作ることが目標です。
define i32 @main() {
%temp = add i32 4, 5
ret i32 %temp
}
レジスタの利用
演算の結果は一時的なレジスタ（%1 や %temp など）に格納されます。そのレジスタの値を ret で返します。
最初の整数リテラル1個の例では、整数値をそのまま ret で返していました。今後の処理を単純にするため、演算結果だけでなくリテラルも必ずレジスタに格納するように変更します。
LLVMのリファレンス(LLVM Language Reference Manual)を見ても、レジスタに値を直接代入する命令は見つかりません。そこで無理やり演算をしながらレジスタに値を格納します。
%t1 = or i32 4, 0
これでレジスタ%t1に、4が代入されます。（addなどの整数演算を使っても良いのですが、今回はビット演算にしました）
足し算全体の処理は、次のようになるはずです。
define i32 @main() {
%t1 = or i32 4, 0
%t2 = or i32 5, 0
%t3 = add i32 %t1, %t2
ret i32 %t3
}
コンテキストの導入
レジスタの名前を重複しないように割り振るため、インデックス値（通し番号）を管理することにします。これを保持するために、コンテキストのハッシュ(lctx)を用意することにしました。（ミニRubyやミニNode.jsで利用していた lenv に相当します）
それを、compile(), generate()などの関数の引数に追加します。
let lctx = {
'tempIdx': 0, // temp index
};
// ---- compile simplified tree into LLVM IR ---
function compile(tree, lctx) {
let mainBlock = generate(tree, lctx);
let mainFunc = generateMain(mainBlock, lctx);
return mainFunc;
}
// ---- genereate LLVM IR block ---
function generate(tree, lctx) {
// ... 省略 ...
}
整数リテラルの生成
用意したコンテキストを使って、generate()の処理を拡張します。
// ---- genereate LLVM IR block ---
function generate(tree, lctx) {
// --- int32 literal ---
if (tree[0] === 'lit') {
let idx = lctx['tempIdx'];
idx = idx + 1;
lctx['tempIdx'] = idx;
let tempName = '%t' + idx;
return TAB + tempName + ' = or i32 ' + tree[1] + ', 0' + LF;
}
// ... 省略 ...
}
コンテキストからインデックス値を取得し、1つカウントアップしてレジスタ名に利用します。新しいインデックス値はコンテキストに再設定しておきます。
足し算の生成
次は足し算です。左の項と右の項を生成しますが、それぞれの値が格納されたレジスタ名を、コンテキストのインデックス値から決定しています。
// ---- genereate LLVM IR block ---
function generate(tree, lctx) {
// ... 省略 ...
// --- binary operator ---
if (tree[0] === '+') {
const leftBlock = generate(tree[1], lctx);
const leftTempName = '%t' + lctx['tempIdx']
const rightBlock = generate(tree[2], lctx);
const rightTempName = '%t' + lctx['tempIdx']
// prepare temp register
let idx = lctx['tempIdx'];
idx = idx + 1;
lctx['tempIdx'] = idx;
let tempName = '%t' + idx;
const addBlock = TAB + tempName + ' = add i32 ' + leftTempName + ', ' + rightTempName + LF;
return (leftBlock + rightBlock + addBlock);
}
println('-- ERROR: unknown node in generate() ---');
printObj(tree);
abort();
}
メイン関数の生成
メイン関数の生成でも、コンテキストを使って最後の結果が格納されているレジスタ名を取得します。
function generateMain(mainBlock, lctx) {
let lastTempName = '%t' + lctx['tempIdx']
let block = '';
block = block + 'define i32 @main() {' + LF;
//block = block + TAB + 'ret i32 ' + mainBlock + LF;
block = block + mainBlock;
block = block + TAB + 'ret i32 ' + lastTempName + LF;
block = block + '}' + LF;
return block;
}
実行結果
整数だけの場合
処理を変更しているので、まず整数だけの場合を確認しておきましょう。
$ node mininode_compiler03.js one.js
$ more generated.ll
define i32 @main() {
%t1 = or i32 1, 0
ret i32 %t1
}
$
$ lli generated.ll || echo $?
1
コンパイル結果、実行結果共にOKです。
足し算の場合
いよいよ足し算です。うまくいくでしょうか。
$ node mininode_compiler03.js add.js
$ more generated.ll
define i32 @main() {
%t1 = or i32 4, 0
%t2 = or i32 5, 0
%t3 = add i32 %t1, %t2
ret i32 %t3
}
$
$ lli generated.ll || echo $?
9
やった！ コンパイル結果、実行結果共に大丈夫なようです。
複数の足し算の場合
今度は複数の足し算を実行してみましょう。
1 + 2 + (3 + (4 + 5) );
$ node mininode_compiler03.js add_many.js
$ more generated.ll
define i32 @main() {
%t1 = or i32 1, 0
%t2 = or i32 2, 0
%t3 = add i32 %t1, %t2
%t4 = or i32 3, 0
%t5 = or i32 4, 0
%t6 = or i32 5, 0
%t7 = add i32 %t5, %t6
%t8 = add i32 %t4, %t7
%t9 = add i32 %t3, %t8
ret i32 %t9
}
コンパイル結果をみると、評価順の含めて正しく生成できているようです。
では実行してみましょう。
$ lli generated.ll || echo $?
15
成功ですね。
バイナリの生成
いよいよバイナリを生成してみます。llcでオブジェクトファイルを生成し、ldでリンクしてバイナリにします。(gcc を使う方法もあるようです）
以下はMax OS Xの場合です。こちらを参考にしました。
$ node mininode_compiler03.js add_many.js
$ llc generated.ll -O0 -march=x86-64 -filetype=obj -o=generated.o
$ ld -arch x86_64 -macosx_version_min 10.12.0 generated.o -lSystem -o add_many
$ ls add_many
add_many*
これで実行可能なバイナリ add_manyが生成されました。早速実行してみます。
$ ./add_many || echo $?
15
実行できました。感激です！ これでミニミニコンパイラと名乗れそうです。
次回は
次は残りの四則演算と、余りを求められるようにします。
ここまでのソース
// -------------------------
// mininode_compiler.js - Mini Node.js Compiler by Node.js
// - 03: i32 literal
// - binary operator
// - 03: +
// - -, *, /, %
// -------------------------
const loadAndParseSrc = require('./module_parser_extra2.js');
const println = require('./module_println.js');
const printObj = require('./module_printobj.js');
const abort = require('./module_abort.js');
//const callBuiltinByName = require('./module_builtin_extra2.js');
// --- for compiler ---
const fs = require('fs');
function writeFile(filename, str) {
fs.writeFileSync(filename, str);
return null;
}
// ======== for comiler =======
const LF = '\n';
const TAB = ' ';
let lctx = {
'tempIdx': 0, // temp index
};
// ---- compile simplified tree into LLVM IR ---
function compile(tree, lctx) {
let mainBlock = generate(tree, lctx);
let mainFunc = generateMain(mainBlock, lctx);
return mainFunc;
}
// ---- genereate LLVM IR block ---
function generate(tree, lctx) {
// --- int32 literal ---
if (tree[0] === 'lit') {
let idx = lctx['tempIdx'];
idx = idx + 1;
lctx['tempIdx'] = idx;
let tempName = '%t' + idx;
return TAB + tempName + ' = or i32 ' + tree[1] + ', 0' + LF;
}
// --- binary operator ---
if (tree[0] === '+') {
const leftBlock = generate(tree[1], lctx);
const leftTempName = '%t' + lctx['tempIdx']
const rightBlock = generate(tree[2], lctx);
const rightTempName = '%t' + lctx['tempIdx']
// prepare temp register
let idx = lctx['tempIdx'];
idx = idx + 1;
lctx['tempIdx'] = idx;
let tempName = '%t' + idx;
const addBlock = TAB + tempName + ' = add i32 ' + leftTempName + ', ' + rightTempName + LF;
return (leftBlock + rightBlock + addBlock);
}
println('-- ERROR: unknown node in generate() ---');
printObj(tree);
abort();
}
function generateMain(mainBlock, lctx) {
let lastTempName = '%t' + lctx['tempIdx']
let block = '';
block = block + 'define i32 @main() {' + LF;
//block = block + TAB + 'ret i32 ' + mainBlock + LF;
block = block + mainBlock;
block = block + TAB + 'ret i32 ' + lastTempName + LF;
block = block + '}' + LF;
return block;
}
// ======== start compiler =======
// --- load and parse source ---
const tree = loadAndParseSrc();
//println('--- tree ---');
//printObj(tree);
// --- compile ----
const ll = compile(tree, lctx);
//println('--- result ---');
//println(ll);
writeFile('generated.ll', ll);
GitHubにもあげておきます。