Node.js でつくる Node.js ミニコンパイラ - 08 : Whileループを実装する

はじめに

「RubyでつくるRuby ゼロから学びなおすプログラミング言語入門」(ラムダノート, Amazon) と Turing Complete FM の影響で、Node.jsミニコンパイラ作りにもチャレンジ中です。
前回は条件分岐を実装しました。今回はループ処理(while)をサポートします。

• コンパイラ編 もくじ

CのソースからLLVM IRを調べる

いつものようにC言語から出発します。用意したのはこちら。

while.c

#include <stdio.h>

void putn(int n) {
  printf("%d\n", n);

}

int main() {
  int a = 0;
  while (a < 10) {
    putn(a);
    a = a + 1;
  }

  return 0;
}

コンパイルして、LLVM IRを生成します。メイン関数部分はこうなりました。

define i32 @main() #0 {
  %1 = alloca i32, align 4
  %2 = alloca i32, align 4
  store i32 0, i32* %1, align 4
  store i32 0, i32* %2, align 4
  br label %3 ;--- 条件判定の処理にジャンプ 

; --- 条件判定 ---
; <label>:3:                                      ; preds = %6, %0
  %4 = load i32, i32* %2, align 4
  %5 = icmp slt i32 %4, 10
  br i1 %5, label %6, label %10 ;--- 条件が成立していたらループ内の処理に、不成立なら後続処理にジャンプ

; --- ループ内の処理 ---
; <label>:6:                                      ; preds = %3
  %7 = load i32, i32* %2, align 4
  call void @putn(i32 %7)
  %8 = load i32, i32* %2, align 4
  %9 = add nsw i32 %8, 1
  store i32 %9, i32* %2, align 4
  br label %3 ; --- 条件判定にジャンプ

; --- 後続処理 ---
; <label>:10:                                     ; preds = %3
  ret i32 0
}

条件判定部分の前にラベルを作って、そこにジャンプすることでループを実現しているようです。なるほど。
ここで「%名前」で表記されるレジスタは再代入は不可のはずですが、brでジャンプした場合は再代入とはみなされない様です。（仕様のどこで説明されているのかは見つけられませんでした)

whileのコンパイル

jsソースのパース

こちらのミニNode.js のソースを用意します。

while.js

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

0;

whileの部分をパース→単純化した結果はこうなります。

  [ 'while',
    [ '<', [ 'var_ref', 'a' ], [ 'lit', 10 ] ],
    [ 'stmts',
      [ 'func_call', 'putn', [ 'var_ref', 'a' ] ],
      [ 'var_assign', 'a', [ '+', [ 'var_ref', 'a' ], [ 'lit', 1 ] ] ]
    ]
  ]

これをコンパイルできる様にしていきます。

generate()の拡張

whileの処理を生成できるようにgenerate()を拡張していきますが、考え方はifの場合と同じです。まずラベル名を生成ルールは、このようにしました。

• Ln_WHILE_BEGIN: whileの始まり。条件判断の部分
• Ln_WHILE_BODY: ループ内部の処理の開始
• Ln_WHILE_END: ループを抜けて、後続処理の開始

generate()の拡張部分は次の通りです。ifの場合と同じ様に、必要に応じてi32型からi1型へのキャスト処理も含めています。

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

  if (tree[0] === 'while') {
    const label = makeTempLabelName(lctx);
    const labelWhile = label + 'WHILE_BEGIN';
    const labelBody = label + 'WHILE_BODY';
    const labelEnd = label + 'WHILE_END';

    // --- begin of while : condition block ---
    let block = TAB() + 'br label %' + labelWhile + ' ; -- jump to begin of while_block:' + label + ' --' + LF();
    block = block + labelWhile + ':' + LF();

    // --- condition ---
    const condition = generate(tree[1], lctx);
    block = block + condition;

    // -- cast i32 to i1, if needed --
    const castBlock = castToI1(lctx);
    block = block + castBlock;

    const conditionName = currentTempName(lctx);
    block = block + TAB() + 'br i1 ' + conditionName + ', label %' + labelBody + ', label %' + labelEnd + LF();

    // --- while body --
    const blockBody = generate(tree[2], lctx);
    block = block + labelBody + ':' + LF();
    block = block + blockBody;
    block = block + TAB() + 'br label %' + labelWhile + LF();

    // --- end of while --
    block = block + labelEnd + ':' + ' ; --- end while_block:' + label + ' ---' + LF();

    return block;
  }

  // ... 省略 ...
}

コンパイル結果

先ほどの while.js をコンパイルして生成されたLLVM IRはこちらです。

generated.ll

define i32 @main() {
  %t1 = alloca i32, align 4 ;alloc localVariable:a
  %t2 = or i32 0, 0
  store i32 %t2, i32* %t1, align 4 ;store init localVariable:a

  br label %L3_WHILE_BEGIN ; -- jump to begin of while_block:L3_ --
L3_WHILE_BEGIN:
  %t4 = load i32, i32* %t1, align 4 ;load localVariable:a
  %t5 = or i32 10, 0
  %t6 = icmp slt i32 %t4, %t5
  br i1 %t6, label %L3_WHILE_BODY, label %L3_WHILE_END
L3_WHILE_BODY:
  %t7 = load i32, i32* %t1, align 4 ;load localVariable:a
  call void @putn(i32 %t7)

  %t8 = load i32, i32* %t1, align 4 ;load localVariable:a
  %t9 = or i32 1, 0
  %t10 = add i32 %t8, %t9

  store i32 %t10, i32* %t1, align 4 ;store localVariable:a

  br label %L3_WHILE_BEGIN
L3_WHILE_END: ; --- end while_block:L3_ ---

  %t11 = or i32 0, 0

  ret i32 %t11
}

; --- builtin functions ---
@.sputn = private unnamed_addr constant [5 x i8] c"%d\0D\0A\00", align 1
declare i32 @printf(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
}

実行結果

lliで実行してみると、ちゃんとループ処理が動きました。やったね！

$ lli generated.ll
0
1
2
3
4
5
6
7
8
9

ミニNode.jsインタープリター経由でもコンパイルできるか確認してみましょう。

$ node mininode_extra_3.js mininode_compiler08.js while.js
$ lli generated.ll
0
1
2
3
4
5
6
7
8
9

動いている様ですね。さらに、バイナリも生成してみます（手順はMac OS Xの場合）

$ 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 while
$ ./while
0
1
2
3
4
5
6
7
8
9

ばっちり動きました。

次回は

ループ処理ができたので、次回はひとまず現時点でのFizzBuzzを実装してみます。それに必要となる文字列出力の組み込み関数も用意します。

ここまでのソース

• mininode_compiler08.js
• sample/while.js