LoginSignup
2
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

@massie_g(がねこ まさし)

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

Last updated at Posted at 2018-07-24

はじめに

「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 には条件なしのジャンプもあります。上記でも次の様に無条件ジャンプが利用されています。

 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にあげておきます。

2
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
2
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?