Node.js でつくる Node.js ミニコンパイラ - 07 : 条件分岐を行う

# はじめに

「RubyでつくるRuby ゼロから学びなおすプログラミング言語入門」([ラムダノート](https://www.lambdanote.com/products/ruby-ruby), [Amazon](https://www.amazon.co.jp/dp/4908686017)) と [Turing Complete FM](https://turingcomplete.fm/) の影響で、Node.jsミニコンパイラ作りにもチャレンジ中です。
[前回は比較演算子を実装](https://qiita.com/massie_g/items/fd309c8cada1b0d5a416)しました。今回は条件分岐(if)をサポートします。

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

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

## if だけの場合

いつものようにC言語のソースからスタートします。まずはifだけで、elseなしのコードから。

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

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

int main() {
  int a = 3;
  if ( a > 1 ) {
    putn(333);
  }

  return 0;
}
```

コンパイルして、LLVM IRを生成します。

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

得られた結果から、メイン関数の部分を取り出すとこんな感じです。一部コメントを手で追記しました。


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

  ; --- if (a > 1) に相当 ---
  %4 = icmp sgt i32 %3, 1
  br i1 %4, label %5, label %6

; -- 条件が真(1)の場合 ---
; <label>:5:                                      ; preds = %0
  call void @putn(i32 333)
  br label %6 ; -- 後続処理にジャンプ --

; --- 条件が偽(0) は、後続処理を実行 ---
; <label>:6:                                      ; preds = %5, %0
  ret i32 0
}
```

if の行に相当するのはこの部分ですね。

```
  ; --- if (a > 1) に相当 ---
  %4 = icmp sgt i32 %3, 1
  br i1 %4, label %5, label %6
```

icmp sgt （符号あり >） で 「%3」と「1」を比較しています。
次の br は i1(1ビット整数=ブール型)の値の真偽で異なる飛び先にジャンプする、条件付きジャンプ命令です。値が真(1)なら最初のラベルに、偽(0)なら2番目のラベルにジャプします。

- ‘br’ Instruction ([LLVM Reference](http://llvm.org/docs/LangRef.html#br-instruction))

また br には条件なしのジャンプもあります。上記でも次の様に無条件ジャンプが利用されています。

```
 br label %6 ; -- 後続処理にジャンプ --
```

## ラベルの表記方法

ラベルの表記は連番を使ったものだけでなく、次の様に"文字列"＋":" で表記することもできます。

```
  br %LABEL_TO_JUMP  ; -- ジャンプするときは %ラベル名

LABEL_TO_JUMP:  ; -- 飛び先は % をつけずにラベル名:
  ; -- 処理が続く --

```

## if 〜 else の場合

今度は if 〜 else のCのソースを用意します。

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

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

int main() {
  int a = 3;
  if ( a > 1 ) {
    putn(333);
  }
  else {
    putn(111);
  }

  return 0;
}
```

生成されたLLVM IRのメイン関数部分はこちら。

```text:
define i32 @main() #0 {
  %1 = alloca i32, align 4
  %2 = alloca i32, align 4
  store i32 0, i32* %1, align 4
  store i32 3, i32* %2, align 4
  %3 = load i32, i32* %2, align 4

  ; --- if (a > 1) に相当 ---
  %4 = icmp sgt i32 %3, 1
  br i1 %4, label %5, label %6

; -- 条件が真(1)の場合 ---
; <label>:5:                                      ; preds = %0
  call void @putn(i32 333)
  br label %7 ; -- 後続処理にジャンプ -- 

; -- 条件が偽(0)の場合 ---
; <label>:6:                                      ; preds = %0
  call void @putn(i32 111)
  br label %7 ; -- 後続処理にジャンプ -- 

; -- 後続処理 -- 
; <label>:7:                                      ; preds = %6, %5
  ret i32 0
}
```

基本的な記述は同じで、elseに相当する部分のラベルと処理が追加されています。条件が成立した場合もそうでない場合も、最後は後続処理のラベルに無条件ジャンプしています。

# 条件分岐のコンパイル

## jsソースの単純化結果

それでは、次はミニNode.js のソースを用意しましょう。

```js:if.js
let a = 3;
if ( a > 1 ) {
  putn(333);
}

0;  // 終了コード0
```

これをパースして単純化した結果から、if の部分を取り出したのがこちらです。

```
[ 'if',
    [ '>', [ 'var_ref', 'a' ], [ 'lit', 1 ] ],
    [ 'func_call', 'putn', [ 'lit', 333 ] ]
]
```

[ 'if', 条件の部分、条件が成立したら実行する内容 ] という形になっています。

もう一つ、elseありの場合も見てみます。

```js:if_else.js
let a = 3;
if ( a > 1 ) {
  putn(333);
}
else {
  putn(111);
}

0;
```

パースして単純化した結果の if 〜 else 部分はこちら。

```
[ 'if',
    [ '>', [ 'var_ref', 'a' ], [ 'lit', 1 ] ],
    [ 'func_call', 'putn', [ 'lit', 333 ] ],
    [ 'func_call', 'putn', [ 'lit', 111 ] ]
]
```

今度は [ 'if', 条件の部分、条件が成立したら実行する内容, 成立しない場合に実行する内容 ] という形になります。 

## generate()の拡張

ifの処理を生成できるようにgenerate()を拡張していきますが、まずラベル名を生成する処理を用意しておきましょう。コンテキストが持つインデックス値 n を用いて、次の様に生成するルールにしました。

- Ln_POSITIVE: 条件成立時（値が真）の処理の開始
- Ln_NAGETIVE: 不成立時（値が偽）の処理の開始
- Ln_END: 後続処理の開始

```js
function makeTempLabelName(lctx) {
  let idx = lctx['tempIdx'];
  idx = idx + 1;
  lctx['tempIdx'] = idx;

  const name = 'L' + idx + '_';
  return name;
}

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

  if (tree[0] === 'if') {
    const label = makeTempLabelName(lctx);
    const labelPositive = label + 'POSITIVE';
    const labelNegative = label + 'NEGATIVE';
    const labelEnd = label + 'END';

    // --- condition ---
    const condition = generate(tree[1], lctx);
    const conditionName = currentTempName(lctx);
    let block = TAB() + '; --- begin if_block:' + label + ' ---' + LF();
    block = block + condition;
    block = block + TAB() + 'br i1 ' + conditionName + ', label %' + labelPositive + ', label %' + labelNegative + LF();

    // --- positive ---
    const blockPositive = generate(tree[2], lctx);
    block = block + labelPositive + ':' + LF();
    block = block + blockPositive;
    block = block + TAB() + 'br label %' + labelEnd + LF();

    // --- negative ---
    block = block + labelNegative + ':' + LF();
    if (tree[3]) {
      const blockNagetive = generate(tree[3], lctx);
      block = block + blockNagetive;
    }
    block = block + TAB() + 'br label %' + labelEnd + LF();

    // --- end ---
    block = block + labelEnd + ':' + ' ; --- end if_block:' + label + ' ---' + LF();

    return block;
  }

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

## コンパイル結果

先ほどのjsファイルをコンパイルして得られたLLVM IRはそれぞれ次の通りです。

### ifだけの場合

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

  ; --- begin if_block:L3_ ---
  %t4 = load i32, i32* %t1, align 4 ;load localVariable:a
  %t5 = or i32 1, 0
  %t6 = icmp sgt i32 %t4, %t5
  br i1 %t6, label %L3_POSITIVE, label %L3_NEGATIVE
L3_POSITIVE:
  %t7 = or i32 333, 0
  call void @putn(i32 %t7)
  br label %L3_END
L3_NEGATIVE:
  br label %L3_END
L3_END: ; --- end if_block:L3_ ---

  %t8 = or i32 0, 0

  ret i32 %t8
}

; --- 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
}
```

else {} が無いのですが、手を抜いていて、一旦 NEGATIVE にジャンプしています。そのまま何もせずに、END までジャンプしています。

### if 〜 else の場合

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

  ; --- begin if_block:L3_ ---
  %t4 = load i32, i32* %t1, align 4 ;load localVariable:a
  %t5 = or i32 1, 0
  %t6 = icmp sgt i32 %t4, %t5
  br i1 %t6, label %L3_POSITIVE, label %L3_NEGATIVE
L3_POSITIVE:
  %t7 = or i32 333, 0
  call void @putn(i32 %t7)
  br label %L3_END
L3_NEGATIVE:
  %t8 = or i32 111, 0
  call void @putn(i32 %t8)
  br label %L3_END
L3_END: ; --- end if_block:L3_ ---

  %t9 = or i32 0, 0

  ret i32 %t9
}

; --- 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
}
```

今度は NEGATIVE の部分にも処理があります。

これを実行すると、条件成立なので「333」と表示されます。

```
$ lli generated.ll
333
```

# 暗黙の型変換（再び）

## 32ビット整数による条件分岐

条件ジャンプの br では、i1（1ビット整数）を受け取る前提になっています。今回のミニNode.jsでは型を32ビット整数にしているので、例えば次の様なコードをコンパイルして実行すると型不一致のエラーが出てしまいます。

元のjsファイル

```js:if32.js
let a = 3;
if ( a ) {
  putn(333);
}

0;
```

コンパイル結果

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

  ; --- begin if_block:L3_ ---
  %t4 = load i32, i32* %t1, align 4 ;load localVariable:a
  br i1 %t4, label %L3_POSITIVE, label %L3_NEGATIVE  ; 32ビット整数の %t4の値で分岐しようとしている
L3_POSITIVE:
  %t5 = or i32 333, 0
  call void @putn(i32 %t5)
  br label %L3_END
L3_NEGATIVE:
  br label %L3_END
L3_END: ; --- end if_block:L3_ ---

  %t6 = or i32 0, 0

  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
lli: generated.ll:8:9: error: '%t4' defined with type 'i32'
  br i1 %t4, label %L3_POSITIVE, label %L3_NEGATIVE
        ^
```

# 1ビット整数への型変換

## 1ビットへのキャスト処理

最後の演算結果が i32型（32ビット符号付き整数）の場合に、i1型（1ビット整数）に変換します。実際は値が0に等しいかどうかを比較演算子で求めるようにしました。

```js

// cast i32 to i1, if necessary
function castToI1(lctx) {
  if (currentTempType(lctx) === 'i1') {
    return '';
  }

  const currentName = currentTempName(lctx);
  const castedName = nextTempName(lctx);
  const castBlock = TAB() + castedName + ' = icmp ne i32 ' + currentName + ', 0' + LF();
  return castBlock;
}
```

最後の演算結果が i1 型の場合には、何もしません。

## genereate()の修正

条件部分を計算した後に、先ほどのキャスト処理の生成を呼び出します。

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

  if (tree[0] === 'if') {
    const label = makeTempLabelName(lctx);
    const labelPositive = label + 'POSITIVE';
    const labelNegative = label + 'NEGATIVE';
    const labelEnd = label + 'END';

    // --- condition ---
    const condition = generate(tree[1], lctx);
    //const conditionName = currentTempName(lctx);
    let block = TAB() + '; --- begin if_block:' + label + ' ---' + LF();
    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 %' + labelPositive + ', label %' + labelNegative + LF();

    // ... 省略 ...
  }

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

## コンパイル結果

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

  ; --- begin if_block:L3_ ---
  %t4 = load i32, i32* %t1, align 4 ;load localVariable:a
  %t5 = icmp ne i32 %t4, 0   ; --- i32型の%t4から、i1型の%t5に変換
  br i1 %t5, label %L3_POSITIVE, label %L3_NEGATIVE
L3_POSITIVE:
  %t6 = or i32 333, 0
  call void @putn(i32 %t6)
  br label %L3_END
L3_NEGATIVE:
  br label %L3_END
L3_END: ; --- end if_block:L3_ ---

  %t7 = or i32 0, 0

  ret i32 %t7
}

; --- 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
}

```

該当部分は次の様に、i1型への変換が行われる様になっています。

```
  ; --- begin if_block:L3_ ---
  %t4 = load i32, i32* %t1, align 4 ;load localVariable:a
  %t5 = icmp ne i32 %t4, 0   ; --- i32型の%t4から、i1型の%t5に変換
  br i1 %t5, label %L3_POSITIVE, label %L3_NEGATIVE
```

## 実行結果

これでエラーが出ずに、正しく実行できるようになりました。

```
$ lli generated.ll
333
```

# 次回は

ミニNode.jsがサポートする唯一のループ処理、 [while に取り掛かります。](https://qiita.com/massie_g/items/80e9aedc613900c2de7d)

# ここまでのソース

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

- [mininode_compiler07.js](https://github.com/mganeko/mininode_compiler/blob/master/mininode_compiler07.js)
- [sample/if.js](https://github.com/mganeko/mininode_compiler/blob/master/sample/if.js)
- [sample/if_else.js](https://github.com/mganeko/mininode_compiler/blob/master/sample/if_else.js)
- [sample/if32.js](https://github.com/mganeko/mininode_compiler/blob/master/sample/if32.js)