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