Node.js でつくる Node.js ミニコンパイラ - 05 : ローカル変数を使う

# はじめに

「RubyでつくるRuby ゼロから学びなおすプログラミング言語入門」([ラムダノート](https://www.lambdanote.com/products/ruby-ruby), [Amazon](https://www.amazon.co.jp/dp/4908686017)) という本の影響で自分でもミニNode.jsインタープリターを作ってみました。
さらにポッドキャストの [Turing Complete FM](https://turingcomplete.fm) の影響も受けて、ミニコンパイラ作りにもチャレンジしています。

[前回は四則演算と余り](https://qiita.com/massie_g/items/07b2bec3d7266faf9785)を実装しました。今回はローカル変数をサポートします。合わせて複数行への対応と、簡易デバッグ出力を用意します。

* [コンパイラ編 もくじ](https://qiita.com/massie_g/items/3ba1ba5d55499ee84b0b)

# 簡易デバッグ出力

変数を使えるようになると、自然と複数行のコードを書きたくなります。複数行のコードを書くと、最後の終了コードだけでなく、途中の状態も出力したくなります。
そこで簡易的なデバッグ出力を用意します。

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

デバッグ出力は組み込み関数として用意しますが、その関数呼び出しをLLVM IRでどう表現するのか調べます。

まず、C言語のソースを用意します。putn()が今回用意した関数で、32ビット符号付き整数を出力します。内部では普通にprintf()を利用しています。

```c:putn.c
#include <stdio.h>

// デバッグ出力
void putn(int n) {
  printf("%d\n", n);
}

int main() {
  putn(123);
  return 0;
}
```

これをClangでLLVM IRに変換します。

```
$ clang -S -emit-llvm -O0 putn.c
```

得られたLLVM IRから、付加情報を削ったものがこちら。

```text:putn.ll
@.str = private unnamed_addr constant [4 x i8] c"%d\0A\00", align 1

define void @putn(i32) #0 {
  %2 = alloca i32, align 4
  store i32 %0, i32* %2, align 4
  %3 = load i32, i32* %2, align 4
  %4 = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([6 x i8], [6 x i8]* @.str, i32 0, i32 0), i32 %3)
  ret void
}

declare i32 @printf(i8*, ...) #1

define i32 @main() #0 {
  %1 = alloca i32, align 4
  store i32 0, i32* %1, align 4
  call void @putn(i32 123)
  ret i32 0
}
```

~~これをlliで実行しても、残念ながら改行が正しく行われません。~~（改行のエスケープシーケンスが間違っていました。修正したら正しく動きました）そこで手を加えつつ更にシンプルにしたものがこちらです。

```text:putn_simple.ll
@.str = private unnamed_addr constant [5 x i8] c"%d\0D\0A\00", align 1

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

declare i32 @printf(i8*, ...)

define i32 @main() {
  call void @putn(i32 123)
  ret i32 0
}
```

ここから次のことが読み取れます。

- 標準ライブラリの関数を利用するには、 declare で利用したい関数を宣言する
- 自分で関数を定義するには、 define を使う
- 関数の宣言/定義は、戻り値の型、引数の型を指定する
    - 関数内から引数を参照するには、%0, %1, ... を使う
    - おそらく最後の引数の次には、関数からの戻り先が格納されている
- 関数を呼ぶには call を使う。戻り値の型や引数の型を明示的に記述する
- 文字列リテラルは、「@名前」という形で、型(i8=8ビット整数)と長さを指定して確保しておく

## putn()を用意する

コンパイル時に上記のputn()を一緒に書き出すための関数generateBuiltin()を用意し、compile()から利用します。

```js
function compile(tree, lctx) {
  const mainBlock = generate(tree, lctx);
  const mainFunc = generateMain(mainBlock, lctx);
  const builtinFunc = generateBuiltin()
  return mainFunc + builtinFunc;
}

function generateBuiltin() {
  let block = LF();
  block = block + '; --- builtin functions ---' + LF();
  block = block + '@.sputn = private unnamed_addr constant [5 x i8] c"%d\\0D\\0A\\00", align 1' + LF();
  block = block + 'declare i32 @printf(i8*, ...)' +　LF();
  block = block + 'declare i32 @puts(i8*)' +　LFR();
  block = block + LF();
  block = block + 'define void @putn(i32) {' +　LF();
  block = block + '  %r1 = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([5 x i8], [5 x i8]* @.sputn, i32 0, i32 0), i32 %0)' +　BR();
  block = block + '  ret void' +　LF();
  block = block + '}' +　LF();
  return block;
}
```


## putn()を利用する

このputs()を利用するjsのソースコードを用意します。

```js:putn.js
putn(111);
```

これをパースして単純化した結果がこちらです。

```
[ 'func_call', 'putn', [ 'lit', 111 ] ]
```

暫定的に、関数呼び出し func_call が登場したら、putn を呼び出すようにLLVM IRを生成します。

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

  // --- debug print ---
  if (tree[0] === 'func_call') {
    if (tree[1] === 'putn') {
      const argBlock = generate(tree[2], lctx);
      const argTempName = currentTempName(lctx);
      const callBlock = TAB() + 'call void @putn(i32 ' + argTempName + ')' + LF();
      return argBlock + callBlock;
    }

    println('-- ERROR: unknown func name in generate() ---');
    printObj(tree);
    abort();
  }

  // ... 省略 ...
}
```

## コンパイル結果

ここまで対応したミニコンパイラで、putn.js をコンパイルした結果がこちらです。

```text:generated.ll
define i32 @main() {
  %t1 = or i32 111, 0
  call void @putn(i32 %t1)
  ret i32 %t1
}

; --- 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 generated.ll
111
```

無事「111」が出力されました。これで動作確認が楽になりました。

# 複数行の対応

次は複数行への対応です。先ほど対応したputn()を使った2行のjsソースコードを要します。

```js:multi_lines.js
putn(1);
putn(2+3);
```

これをパースして単純化した結果はこちらです。

```
[ 'stmts',
  [ 'func_call', 'putn', [ 'lit', 1 ] ],
  [ 'func_call', 'putn', [ '+', [ 'lit', 2 ], [ 'lit', 3 ] ] ] ]
```

stmts が登場したら、各行に対応する要素を順番に処理すれば良さそうです。

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

  // --- multi lines ---
  if (tree[0] === 'stmts') {
    let i = 1;
    let block = '';
    while (tree[i]) {
      block = block + generate(tree[i], lctx) + LF();
      i = i + 1;
    }
    return block;
  }

  // ... 省略 ...
}
```

# ローカル変数の利用

変数を扱うには、次の3つの処理があります。

- 変数の宣言（と初期値の代入）: var_decl
- 変数の再代入: var_assign
- 変数の参照: var_ref

これをLLVM IRで表現するのか、C言語から変換して調べてみましょう。

## C言語からLLVM IRを生成

こちらのCのソースを用意しました。

```c:add_var.c
int main() {
  int a = 1;
  return a + 2;
}
```

ClangでLLVM IRを生成します。

```
$ clang -S -emit-llvm -O0 add_var.c
```

生成されたIRはこちら。

```text:add_var.ll
; ModuleID = 'add_var.c'
source_filename = "add_var.c"
target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-apple-macosx10.12.0"

; Function Attrs: noinline nounwind ssp uwtable
define i32 @main() #0 {
  %1 = alloca i32, align 4
  %2 = alloca i32, align 4
  store i32 0, i32* %1, align 4
  store i32 1, i32* %2, align 4
  %3 = load i32, i32* %2, align 4
  %4 = add nsw i32 %3, 2
  ret i32 %4
}

attributes #0 = { noinline nounwind ssp uwtable "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="penryn" "target-features"="+cx16,+fxsr,+mmx,+sse,+sse2,+sse3,+sse4.1,+ssse3,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }

!llvm.module.flags = !{!0}
!llvm.ident = !{!1}

!0 = !{i32 1, !"PIC Level", i32 2}
!1 = !{!"Apple LLVM version 9.0.0 (clang-900.0.39.2)"}
```

これをシンプルに整形した結果がこちらです。

```
define i32 @main() #0 {
  %1 = alloca i32, align 4
  store i32 1, i32* %1, align 4

  %2 = load i32, i32* %1, align 4
  %3 = add i32 %2, 2
  ret i32 %3
}
```

新しく登場した命令は、それぞれ次の役割を持っています。ちょうど変数を扱う各要素に対応しています。

- alloca でスタック上に変数領域を確保し、そのアドレスをレジスタに代入 ... var_decl
- store で、レジスタの示すアドレスに値を代入 ... var_assign
- load で、レジスタの示すアドレスの値を、別のレジスタに取り出す ... var_ref

## JavaScriptの場合

上記と同様のjsのコードを用意します。ただしせっかくなので今回用意したputn()を使って画面に出力しましょう。

```js:add_var.js
let a = 1;
a = a + 2;
putn(a);
```

パースして単純化したTreeはこちらです。var_decl, var_assign, var_ref 全てが登場します。

```
[ 'stmts',
  [ 'var_decl', 'a', [ 'lit', 1 ] ],
  [ 'var_assign', 'a', [ '+', [ 'var_ref', 'a' ], [ 'lit', 2 ] ] ],
  [ 'func_call', 'putn', [ 'var_ref', 'a' ] ] ]
```

## コード(LLVM IR)の生成

### コンテキストで変数定義を保持

新しい変数が宣言されたら、コンテキスト lctx に次の様に格納することにしました。

```
lctx['変数名'] = ['local_var', 'i32', 'アドレスを保持しているレジスタ名']
```

### 変数の宣言

var_decl に該当するIRの生成はこのようにしました。初期値がある場合は、その値を求めて代入(store)します。

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

  if (tree[0] === 'var_decl') {
    // -- check NOT exist --
    const name = tree[1];
    if (name in lctx) {
      println('---ERROR: varbable ALREADY exist (compiler) --');
      abort();
    }

    let block = '';
    // -- alloc on stack --
    const addrVar = nextTempName(lctx);
    block = block + TAB() + addrVar + ' = alloca i32, align 4' + ' ;alloc localVariable:' + name + LF();
    lctx[name] = ['local_var', 'i32', addrVar];

    // --- assign initial value --
    const init = generate(tree[2], lctx);
    if (init !== '') {
      const initVar = currentTempName(lctx);
      block = block + init;
      block = block + TAB() + 'store i32 ' + initVar + ', i32* ' + addrVar + ', align 4' + ' ;store init localVariable:' + name + LF();
    }

    return block;
  }

  // ... 省略 ...
}
```

IRを見てわかる様に、'; 〜'というコメントも生成するようにしています。

### 変数への代入

変数の代入処理はこうします。コンテキスト lctxからアドレスを保持しているレジスタを取得し、右辺を処理した結果を代入(store)します。

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

  if (tree[0] === 'var_assign') {
    // -- check EXIST --
    const name = tree[1];
    if (name in lctx) {
      let block = '';
      const localVar = lctx[name];
      const addrVar = localVar[2];
      const valBlock =  generate(tree[2], lctx);
      if (valBlock === '') {
        println('---ERROR: var assign value NOT exist --');
        abort();
      }
      const lastVar = currentTempName(lctx)
      block = block + valBlock + LF();
      block = block + TAB() + 'store i32 ' + lastVar + ', i32* ' + addrVar + ', align 4' + ' ;store localVariable:' + name + LF();
      
      return block;
    }

    println('---ERROR: varibable NOT declarated (assign)--:' + name);
    abort();
  }

  // ... 省略 ...
}
```


### 変数の参照

変数の参照でも、コンテキスト lctxからアドレスを保持しているレジスタを取得し、その内容を新しいレジスタに取り出します(lod)。

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

  if (tree[0] === 'var_ref') {
    // -- check EXIST --
    const name = tree[1];
    if (name in lctx) {
      let block = '';
      const localVar = lctx[name];
      const addrVar = localVar[2];
      const val = nextTempName(lctx);

      // %t1 = load i32, i32* %v1, align 4
      block = TAB() + val + ' = load i32, i32* ' + addrVar + ', align 4' + ' ;load localVariable:' + name + LF();
      return block;
    }

    println('---ERROR: varibable NOT declarated (ref)--:' + name);
    abort();
  }

  // ... 省略 ...
}
```

# 実行結果

## コンパイルしてみると

ここまで実装したミニコンパイラのソースを mininode_compile05.js とします。先ほどの add_var.js をコンパイルして見ましょう。

```
$ node mininode_compiler05.js add_var.js
```

生成されたLLVM IRはこちらです。

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

  %t3 = load i32, i32* %t1, align 4 ;load localVariable:a
  %t4 = or i32 2, 0
  %t5 = add i32 %t3, %t4

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

  %t6 = load i32, i32* %t1, align 4 ;load localVariable:a
  call void @putn(i32 %t6)

  ret i32 %t6
}

; --- 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 generated.ll
3
```

putn()による出力も含めて、うまく動きました。

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

```
$ node mininode_extra_3.js mininode_compiler05.js add_var.js
```

こちらもOKです。

## バイナリの生成

バイナリ生成も確認して見ましょう。

```
$ 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_var
$ ls add_var
add_var*
$ ./add_var
3
```

動きました！ 標準ライブラリもちゃんとリンクされている様です。


# 次回は

[次は比較演算子を実装する](https://qiita.com/massie_g/items/fd309c8cada1b0d5a416)予定です。

# これまでのソース

ソースコードは[GitHub](https://github.com/mganeko/mininode_compiler)に上げておきます。

- [mininode_compiler05.js](https://github.com/mganeko/mininode_compiler/blob/master/mininode_compiler05.js)
- [sample/add_var.js](https://github.com/mganeko/mininode_compiler/blob/master/sample/add_var.js)