はじめに

「RubyでつくるRuby ゼロから学びなおすプログラミング言語入門」(ラムダノート, Amazon) と Turing Complete FM の影響で、Node.jsミニコンパイラ作りにもチャレンジ中です。
前回はユーザ定義関数を実現しました。今回それを使って目標だったFizzBuzzとフィボナッチ数列の計算を行います。

コンパイラ編もくじ

FizzBuzz の逆襲

jsのソース

それでは、第9回で取り上げたFizzBuzzを関数を使った形に書き直して、実行してみます。

fizzbuzz_func.js


function fizzbuzz(n) {
  if (n % (3*5) === 0) {
    puts('FizzBuzz');
    return 15;
  }
  else if (n % 3 === 0) {
    puts('Fizz');
    return 3;
  }
  else if (n % 5 === 0) {
    puts('Buzz');
    return 5;
  }
  else {
    putn(n);
    return n;
  }
}

let i = 1;
let ret;
while (i <= 100) {
  ret = fizzbuzz(i)
  i = i + 1;
}

コンパイルして実行すると、何やらエラーが出てしまいます。

$ lli generated.ll
lli: generated.ll:104:1: error: expected instruction opcode
}
^

LLVM IRの該当箇所を見ると、ユーザー定義関数の最後でエラーになっているようです。

; --- user_defined functions ---
define i32 @fizzbuzz(i32) {
  %t1 = alloca i32, align 4 ;alloc arg Variable:n
  store i32 %0, i32* %t1, align 4 ;store arg Variable:n
  ; --- begin if_block:L2_ ---

  ; ... 省略 ...

L22_NEGATIVE:
  ;--- calling func: @putn()
  %t31 = load i32, i32* %t1, align 4 ;load localVariable:n
  call void @putn(i32 %t31)

  %t32 = load i32, i32* %t1, align 4 ;load localVariable:n
  ret i32 %t32

  br label %L22_END
L22_END: ; --- end if_block:L22_ ---
  br label %L13_END
L13_END: ; --- end if_block:L13_ ---
  br label %L2_END
L2_END: ; --- end if_block:L2_ ---
}  ; <--- ここでエラー

入れ子になったif の終了後のラベルにジャンプした後に、何も実行する命令がないことがエラーの原因です。元のjsコードでは、elseで処理しているので、このラベルの後ろに制御が到達することはありません。本来は不要なラベルを生成してしまっています。

ダミーの ret を生成

まっとうに対応するなら余計なラベルを生成しなようにするべきですが、今回は手を抜いてダミーの ret を生成することにしました。

L2_END: ; --- end if_block:L2_ ---
  ret 9999 ; -- dummy ret --
}

if/else や While の場合は必ずラベルにジャンプしているので、最後に処理した値の型を void に設定
ユーザ定義関数の終わりで、最後の型を見て、必要ならダミーの ret を生成
- ※本来なら、最後の命令を見て ret でなかったらダミー生成、が適切かもしれません

// --- generate dummy ret, if necessary ---
function generateDummyRet(lctx) {
  const currentType = currentTempType(lctx);
  if (currentType === 'void') {
    // --- dummy ret for when func is not end with 'ret', such as if/else or while block --
    const dummyRet = TAB() + 'ret i32 9999 ;  dummy ret for when returning from if/while block' + LF();
    return dummyRet;
  }

  // --- dummy ret not needed ---
  return '';
}

function generate(tree, gctx, lctx) {
  // ... 省略 ...

  if (tree[0] === 'func_def') {
    // ... 省略 ...

    // ==== function body =====
    const funcBody = generate(tree[3], gctx, newLctx);

    // --- dummy ret for when func is not end with 'ret', such as if/else or while block --
    const dummyRet = generateDummyRet(newLctx);

    // ==== whole func definition ===
    const funcBlock = funcStart + loadArgBlock + funcBody + dummyRet + funcEnd;
    addGlobalFunc(gctx, funcName, funcSymbol, funcType, argCount, funcBlock);

    // --- no codes in this timing --
    const empty = '';
    return empty;
  }

  // ... 省略 ...

  if (tree[0] === 'while') {
    // ... 省略 ...

    // --- end of while --
    block = block + labelEnd + ':' + ' ; --- end while_block:' + label + ' ---' + LF();
    setCurrentTempType(lctx, 'void');  // 最後の型を void に

    return block;
  }

  if (tree[0] === 'if') {
    // ... 省略 ...

    // --- end ---
    block = block + labelEnd + ':' + ' ; --- end if_block:' + label + ' ---' + LF();
    setCurrentTempType(lctx, 'void');  // 最後の型を void に

    return block;
  }
}

ちゃんと ret で終わっている場合はダミーが付かない様になるはずです。

main処理のエラーに対処

この対応をしてコンパイルすると、今度はコンパイル時にエラーが出てしまいました。

$ node mininode_compiler11.js fizzbuzz_func.js
-- ERROR: unknown type in castToI32() ---
'void'

mainの終了時に i32型の終了コードを返すためにキャスト処理を挟んでいますが、先ほどの while での方設定の影響で、最後の型が void になっています。こちらもダミーの値を返す様に変更してしまいましょう。

// --- cast ---
// cast i1 to i32, if necessary 
function castToI32(lctx) {
  const currentType = currentTempType(lctx);
  if (currentType === 'i32') {
    return '';
  }

  if (currentType === 'i1') {
    const currentName = currentTempName(lctx);
    const castedName = nextTempName(lctx);
    const castBlock = TAB() + castedName + ' = zext i1 ' + currentName + ' to i32 ;cast i1 to i32' + LF();
    return castBlock;  
  }

  if (currentType === 'void') {
    const castedName = nextTempName(lctx);
    const castBlock = TAB() + castedName + ' = or i32 254, 254 ;-- dummy value for casting void to i32 --' + LF();
    return castBlock;
  }

  println('-- ERROR: unknown type in castToI32() ---');
  printObj(currentType);
  abort();
}

もう一度コンパイルすると、今度は無事LLVM IRが generated.ll として生成されました。生成した結果がこちらです。

generated.ll

define i32 @main() {

  %t1 = alloca i32, align 4 ;alloc localVariable:i
  %t2 = or i32 1, 0
  store i32 %t2, i32* %t1, align 4 ;store init localVariable:i

  %t3 = alloca i32, align 4 ;alloc localVariable:ret

  br label %L4_WHILE_BEGIN ; -- jump to begin of while_block:L4_ --
L4_WHILE_BEGIN:
  %t5 = load i32, i32* %t1, align 4 ;load localVariable:i
  %t6 = or i32 100, 0
  %t7 = icmp sle i32 %t5, %t6
  br i1 %t7, label %L4_WHILE_BODY, label %L4_WHILE_END
L4_WHILE_BODY:
  ;--- calling func: @fizzbuzz()
  %t8 = load i32, i32* %t1, align 4 ;load localVariable:i
  %t9 = call i32 @fizzbuzz(i32 %t8)

  store i32 %t9, i32* %t3, align 4 ;store localVariable:ret

  %t10 = load i32, i32* %t1, align 4 ;load localVariable:i
  %t11 = or i32 1, 0
  %t12 = add i32 %t10, %t11

  store i32 %t12, i32* %t1, align 4 ;store localVariable:i

  br label %L4_WHILE_BEGIN
L4_WHILE_END: ; --- end while_block:L4_ ---

  %t13 = or i32 254, 254 ;-- dummy value for casting void to i32 --
  ret i32 %t13
}

; --- user_defined functions ---
define i32 @fizzbuzz(i32) {
  %t1 = alloca i32, align 4 ;alloc arg Variable:n
  store i32 %0, i32* %t1, align 4 ;store arg Variable:n
  ; --- begin if_block:L2_ ---
  %t3 = load i32, i32* %t1, align 4 ;load localVariable:n
  %t4 = or i32 3, 0
  %t5 = or i32 5, 0
  %t6 = mul i32 %t4, %t5
  %t7 = srem i32 %t3, %t6
  %t8 = or i32 0, 0
  %t9 = icmp eq i32 %t7, %t8
  br i1 %t9, label %L2_POSITIVE, label %L2_NEGATIVE
L2_POSITIVE:
  ;--- calling func: @puts()
  %t10 = getelementptr inbounds [9 x i8], [9 x i8]* @.s_0, i32 0, i32 0
  %t11 = call i32 @puts(i8* %t10)

  %t12 = or i32 15, 0
  ret i32 %t12

  br label %L2_END
L2_NEGATIVE:
  ; --- begin if_block:L13_ ---
  %t14 = load i32, i32* %t1, align 4 ;load localVariable:n
  %t15 = or i32 3, 0
  %t16 = srem i32 %t14, %t15
  %t17 = or i32 0, 0
  %t18 = icmp eq i32 %t16, %t17
  br i1 %t18, label %L13_POSITIVE, label %L13_NEGATIVE
L13_POSITIVE:
  ;--- calling func: @puts()
  %t19 = getelementptr inbounds [5 x i8], [5 x i8]* @.s_1, i32 0, i32 0
  %t20 = call i32 @puts(i8* %t19)

  %t21 = or i32 3, 0
  ret i32 %t21

  br label %L13_END
L13_NEGATIVE:
  ; --- begin if_block:L22_ ---
  %t23 = load i32, i32* %t1, align 4 ;load localVariable:n
  %t24 = or i32 5, 0
  %t25 = srem i32 %t23, %t24
  %t26 = or i32 0, 0
  %t27 = icmp eq i32 %t25, %t26
  br i1 %t27, label %L22_POSITIVE, label %L22_NEGATIVE
L22_POSITIVE:
  ;--- calling func: @puts()
  %t28 = getelementptr inbounds [5 x i8], [5 x i8]* @.s_2, i32 0, i32 0
  %t29 = call i32 @puts(i8* %t28)

  %t30 = or i32 5, 0
  ret i32 %t30

  br label %L22_END
L22_NEGATIVE:
  ;--- calling func: @putn()
  %t31 = load i32, i32* %t1, align 4 ;load localVariable:n
  call void @putn(i32 %t31)

  %t32 = load i32, i32* %t1, align 4 ;load localVariable:n
  ret i32 %t32

  br label %L22_END
L22_END: ; --- end if_block:L22_ ---
  br label %L13_END
L13_END: ; --- end if_block:L13_ ---
  br label %L2_END
L2_END: ; --- end if_block:L2_ ---
  ret i32 9999 ;  dummy ret for when returning from if/while block
}


; --- global strings ---
@.s_0 = private constant [9 x i8] c"FizzBuzz\00", align 1
@.s_1 = private constant [5 x i8] c"Fizz\00", align 1
@.s_2 = private constant [5 x i8] c"Buzz\00", align 1

; --- builtin functions ---
@.sputn = private unnamed_addr constant [5 x i8] c"%d\0D\0A\00", align 1
declare i32 @printf(i8*, ...)
declare i32 @puts(i8*)

define void @putn(i32) {
  %r1 = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([5 x i8], [5 x i8]* @.sputn, i32 0, i32 0), i32 %0)
  ret void
}

FizzBuzz 実行結果

先ほどの生成結果を実行してみると、無事動く様になりました。

$ lli generated.ll
1
2
Fizz
4
Buzz
... 省略 ...

バイナリも生成、実行してみます。

$ 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 fizzbuzz_func
$ ./fizzbuzz_func
... 省略 ...
89
FizzBuzz
91
92
Fizz
94
Buzz
Fizz
97
98
Fizz
Buzz

ちゃんと動いていますね。

再帰呼び出しでフィボナッチ数列

再帰呼び出しの罠

さて、今度は再帰呼び出しを使ったフィボナッチ数列の計算をやってみましょう。こちらのjsソースを用意しました。

fib_func.js

function fib(x) {
  if (x <= 1) {
    return x
  }
  else {
    return fib(x - 1) + fib(x - 2);
  }
}

let i = 0;
while (i < 10) {
  putn(fib(i));
  i = i + 1;
}

これをコンパイルすると、ユーザ定義関数が見つからないとエラーが出てしまいました。

$ node mininode_compiler11.js fib_func.js
-- ERROR: unknown func name in generate() --
[ 'func_call', 'fib', [ '-', [ 'var_ref', 'x' ], [ 'lit', 1 ] ] ]

fib()は定義しているなずなのに一体どういうことかと悩みましたが、思わぬ落とし穴にはまっていました。ユーザ定義関数のfib()を定義している最中にfib()を呼び出していますが、その段階ではまだユーザー定義関数の情報がグローバルコンテキストに登録されていないためでした。
それを回避するため、最初に処理の中身がない状態でユーザ定義関数を仮登録し、最後に正しい中身で置き換える方法に変更します。

function generate(tree, gctx, lctx) {
  // ... 省略 ...

  if (tree[0] === 'func_def') {
    // -- append to global context --
    // function hash: funcList['func1'] = [func_type, func_symbol, ret_type, args_count, func_block]
    //  ex) funcList['add'] = ['user_defined', '@add', 'i32', 2, '...']

    const funcName = tree[1];
    const argCount = getLength(tree[2]);
    const funcSymbol = '@' + funcName;
    const funcType = 'i32';
    const argListBlock = generateArgListBlock(argCount);

    // --- prepare new local context for inside of function --
    let newLctx = {
      '_tempIdx': 0, // temp index
      '_tempType': 'i32', // current temp type
    };
    // -- load args to local variable --
    const loadArgBlock = generateLoadArgBlock(tree, argCount, newLctx);

    const funcStart = 'define i32 ' + funcSymbol + '(' + argListBlock + ') {' + LF();
    const funcEnd = '}' + LF();

    // -- add temporary with empty body --- 空の中身で関数を仮登録
    addGlobalFunc(gctx, funcName, funcSymbol, funcType, argCount, '');

    // ==== function body =====
    const funcBody = generate(tree[3], gctx, newLctx);

    // --- dummy ret for when func is not end with 'ret', such as if/else or while block --
    const dummyRet = generateDummyRet(newLctx);

    // ==== whole func definition ===
    const funcBlock = funcStart + loadArgBlock + funcBody + dummyRet + funcEnd;
    addGlobalFunc(gctx, funcName, funcSymbol, funcType, argCount, funcBlock); // 実際の中身で関数を本登録

    // --- no codes in this timing --
    const empty = '';
    return empty;
  }

  // ... 省略 ...
}

実行結果

改めて実行してみると、うまく動く様になりました。

$ node mininode_compiler11.js fib_func.js
$ lli generated.ll
0
1
1
2
3
5
8
13
21
34

バイナリ生成も大丈夫ですね。

$ 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 fib_func
$ ./fib_func
0
1
1
2
3
5
8
13
21
34

ミニインタープリターからの実行

今回のもう一つの目標として、（コンパイラでコンパイラを生成するセルフホストは狙わないが、）「ミニコンパイラをミニインタープリターで実行可能にする」というものがあります。早速ためしてみます。

$ node mininode_extra_3.js mininode_compiler11.js fib_func.js
mininode_extra_3.js:105
    if (mhd[0] === 'builtin') {
           ^

TypeError: Cannot read property '0' of undefined

やっぱりすんなりとは動きません。
調べて見ると、コンパイラのために新しく追加したビルトイン関数が見当たらないということでした。

getTypeOf()
getLength()
getKeys()

確かにインタープリターの方に存在しないビルトイン関数なので、新しく追加しました。

これで再度実行すると、今度は別のエラーが出てしまいます。

$ node mininode_extra_4.js mininode_compiler11.js fib_func.js
---ERROR: varibable ALREADY exist --:keys

なぜだかコンパイラのソースでローカル変数の2重定義が起きています。やっかいな問題でしたが、理由は変数の保持に使っているローカルコンテキストにありました。
ローカルコンテキストはRubyで言う所のハッシュで、JavaScriptでは連想配列です。ところがJavaScriptの連想配列が元々持っているkeysと、ローカル変数として用意したkeysがかぶって言うというのが原因の様です。
ちゃんと対策するが難しそうなので、今回はコンパイラのローカル変数の名前をkeysから変更することで逃げました。

function getGlobalFunctionNames(gctx) {
  const funcList = gctx['funcList'];
  const names = getKeys(funcList);
  return names;
}

function generateGlobalString(gctx) {
  let block = LF();
  block = block + '; --- global strings ---' + LF();

  const strList = gctx['strList'];  
  const strings = getKeys(strList);
  const len = getLength(strings);
  let key;
  let i = 0;
  let gstr;
  while (i < len) {
    key = strings[i];
    gstr = strList[key]; // ['xxxxxxx', length]
    block = block + key + ' = private constant [' + gstr[1] + ' x i8] c"' + gstr[0] + '", align 1' + LF();
    i = i + 1;
  }

  return block;
}

function generateGlobalFunctions(gctx) {
  let block = LF();
  block = block + '; --- user_defined functions ---' + LF();

  const names = getGlobalFunctionNames(gctx);
  const len = getLength(names);
  let key;
  let i = 0;
  let gfunc;
  while (i < len) {
    key = names[i];
    gfunc = getGlobalFunc(gctx, key);
      // grunc : ['user_defined', symbol, type, argCount, funcBlock];
    if (gfunc[0] === 'user_defined') {
      block = block + gfunc[4] + LF();
    }

    i = i + 1;
  }

  return block;
}

さて、うまく動くでしょうか？

$ node mininode_extra_4.js mininode_compiler11.js fib_func.js
$ lli generated.ll
0
1
1
2
3
5
8
13
21
34

動きました！全目標達成です。

終わりに

LLVMを使ったNode.jsミニコンパイラを作る取り組みは、当初の目的を達成したのでひとまず終了です。ソースのパースやバイナリの生成を他のツールに任せているのでかなりシンプルですが、それでも実際にやってみるとすんなりとは行きませんでした。それでも Turing Complete FM で何度も話が出ている様に、ちょっとずつインクリメンタルに進めることで、ゴールにたどり着くことができました。

今回の取り組みをきっかけにLLVMについても少しは理解できたので、また何かやってみたいと思います。

ここまでのソース

ミニコンパイラ

ミニインタープリター