はじめに

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

コンパイラ編もくじ

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

if だけの場合

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

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)

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

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

ラベルの表記方法

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

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

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

if 〜 else の場合

今度は if 〜 else の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のメイン関数部分はこちら。

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 のソースを用意しましょう。

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ありの場合も見てみます。

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: 後続処理の開始

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だけの場合

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 の場合

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ファイル

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に等しいかどうかを比較演算子で求めるようにしました。


// 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()の修正

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

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 に取り掛かります。

ここまでのソース

ソースはGitHubにあげておきます。