はじめに
「RubyでつくるRuby ゼロから学びなおすプログラミング言語入門」(ラムダノート, Amazon) と Turing Complete FM の影響で、Node.jsミニコンパイラ作りにもチャレンジ中です。
前回はループ処理を使ってFizzBuzzを実現しました。今回はユーザー定義関数に着手します。
LLVM IRでの関数定義と引数の受け渡し
C言語のソースから調査
いつものように、C言語のソースを用意します。足し算を行う関数を作ってみました。
func_add.c
int add(int x, int y) {
return x + y;
}
int main() {
int n = add(1, 2);
return n;
}
これをLLVM IRにコンパイルします。 add()の関数定義部分だけを取り出したのがこちらです。
define i32 @add(i32, i32) #0 {
%3 = alloca i32, align 4
%4 = alloca i32, align 4
store i32 %0, i32* %3, align 4
store i32 %1, i32* %4, align 4
%5 = load i32, i32* %3, align 4
%6 = load i32, i32* %4, align 4
%7 = add nsw i32 %5, %6
ret i32 %7
}
LLVM IRの整理
先ほどのIRを元のCのソースとの対応が分かりやすい様に変更しました。実行結果は同じです。
define i32 @add(i32, i32) {
; -- 引数をローカル変数に格納する --
%x_addr = alloca i32, align 4
store i32 %0, i32* %x_addr, align 4
%y_addr = alloca i32, align 4
store i32 %1, i32* %y_addr, align 4
; -- ロカル変数から値を取り出して計算する --
%temp1 = load i32, i32* %x_addr, align 4
%temp2 = load i32, i32* %y_addr, align 4
%temp3 = add i32 %temp1, %temp2
ret i32 %temp3
}
- 引数 %0, %1 の値を、ローカル変数として確保したアドレスに格納
- その後は今までのローカル変数を使った処理と同じように実行
- 最後は ret で値を返す
という流れを実現すれば良さそうです。
ユーザ定義関数への対応
関数の定義
次の様なjsソースを用意します。
func_add.js
function add(x, y) {
return x + y;
}
let n = add(1, 2);
putn(n);
ミニNode.jsでは、関数の定義の単純化構文木Treeは次の様な形です。
[ 'func_def',
'add',
[ 'x', 'y' ],
[ 'ret', [ '+', [ 'var_ref', 'x' ], [ 'var_ref', 'y' ] ] ]
],
まず、関数宣言の引数の部分を生成する関数を用意しました。このように型はi32だけなので、引数の数だけi32を並べます
生成したい行
define i32 @add(i32, i32)
引数の数だけ、i32を羅列する
function generateArgListBlock(argCount) {
let argList = '';
let i = 0;
while (i < argCount) {
if (i === 0) {
argList = argList + 'i32';
}
else {
argList = argList + ', i32';
}
i = i + 1;
}
return argList;
}
また、関数の中で最初に渡された引数の値をローカル変数に読み込む処理を生成する関数も用意します。
function generateLoadArgBlock(tree, argCount, lctx) {
const args = tree[2];
let argName = '';
let addrVar = null;
let argLoadBlock = '';
let i = 0;
let argIdx;
while (i < argCount) {
// -- alloc on stack --
argIdx = '%' + i;
argName = args[i];
addrVar = nextTempName(lctx);
addLocalVariable(lctx, argName, 'i32', addrVar);
argLoadBlock = argLoadBlock + TAB() + addrVar + ' = alloca i32, align 4' + ' ;alloc arg Variable:' + argName + LF();
argLoadBlock = argLoadBlock + TAB() + 'store i32 ' + argIdx + ', i32* ' + addrVar + ', align 4' + ' ;store arg Variable:' + argName + LF();
//setLastVarType(newLctx, 'i32*');
i = i + 1;
}
return argLoadBlock;
}
関数定義は、一旦グルーバルコンテキストに保持しておいて、最後にLLVM IRコードに吐き出すようにします。
gcrtx['funcList'] に、関数名をキーとして、[関数種別、関数のシンボル名、戻り値の型、引数の数、関数の定義内容]を保持します。例えばadd()関数は次の様な形になります。
let funcList = gctx['funcList'];
funcList['add'] = ['user_defined', '@add', 'i32', 2, '関数の定義内容'];
グローバルコンテキストにユーザ定義関数を保持する処理、取得する処理を次の様に用意しました。
//ex) funcList['add'] = ['user_defined', '@add', 'i32', 2, '.....']
function addGlobalFunc(gctx, name, symbol, type, argCount, funcBlock) {
let funcList = gctx['funcList'];
funcList[name] = ['user_defined', symbol, type, argCount, funcBlock];
}
function getGlobalFunc(gctx, name) {
const funcList = gctx['funcList'];
return funcList[name];
}
準備した関数を使いながら、ユーザ定義部分のLLVM IRを生成できるように、generate()を拡張します。
function generate(tree, gctx, lctx) {
// ... 省略 ...
if (tree[0] === 'func_def') {
// -- append to global context --
// function hash: funcList['func1'] = [func_type, func_symbol, ret_type, args_count, func_block]
// ex) funcList['add'] = ['user_defined', '@add', 'i32', 2, '...']
const funcName = tree[1];
const argCount = getLength(tree[2]);
const funcSymbol = '@' + funcName;
const funcType = 'i32';
const argListBlock = generateArgListBlock(argCount);
// --- prepare new local context for inside of function --
let newLctx = {
'_tempIdx': 0, // temp index
'_tempType': 'i32', // current temp type
};
// -- load args to local variable --
const loadArgBlock = generateLoadArgBlock(tree, argCount, newLctx);
const funcStart = 'define i32 ' + funcSymbol + '(' + argListBlock + ') {' + LF();
const funcEnd = '}' + LF();
// ==== function body =====
const funcBody = generate(tree[3], gctx, newLctx);
// ==== whole func definition ===
const funcBlock = funcStart + loadArgBlock + funcBody + funcEnd;
addGlobalFunc(gctx, funcName, funcSymbol, funcType, argCount, funcBlock);
// --- no codes in this timing --
const empty = '';
return empty;
}
// ... 省略 ...
}
ユーザ定義関数の中では、新しいローカルコンテキストを使う様にしています。
この処理ではLLVM IRはグローバルコンテキストに保持しておいて直接生成していないため、空の文字列を返しています。
LLVM IRコードの出力
保持しておいた関数の定義は、グローバル文字列定数などと同じ様に最後に出力するようにしました。
function generateGlobalFunctions(gctx) {
let block = LF();
block = block + '; --- user_defined functions ---' + LF();
const keys = getGlobalFunctionNames(gctx);
const len = getLength(keys);
let key;
let i = 0;
let gfunc;
while (i < len) {
key = keys[i];
gfunc = getGlobalFunc(gctx, key);
// grunc : ['user_defined', symbol, type, argCount, funcBlock];
if (gfunc[0] === 'user_defined') {
block = block + gfunc[4] + LF();
}
i = i + 1;
}
return block;
}
function getGlobalFunctionNames(gctx) {
const funcList = gctx['funcList'];
const keys = getKeys(funcList);
return keys;
}
function compile(tree, gctx, lctx) {
const mainBlock = generate(tree, gctx, lctx);
const mainFunc = generateMain(mainBlock, lctx);
const builtinFunc = generateBuiltin();
const grobalFunctions = generateGlobalFunctions(gctx); // 追加
const globalStrings = generateGlobalString(gctx);
return mainFunc + grobalFunctions + globalStrings + builtinFunc; // 修正
}
return文への対応
ユーザ定義関数のサポートでは、いままで扱っていなかった return文も必要になります。
function generate(tree, gctx, lctx) {
// ... 省略 ...
if (tree[0] === 'ret') {
let block = '';
const valueBlock = generate(tree[1], gctx, lctx);
// ----- return with value ----
block = block + valueBlock;
// -- cast i1 to i32, if needed --
const castBlock = castToI32(lctx);
block = block + castBlock;
const retName = currentTempName(lctx);
block = block + TAB() + 'ret i32 ' + retName + LF();
return block;
}
// ... 省略 ...
}
関数の呼び出し
ビルトイン関数の準備
関数呼び出しは、今まで暫定的に putn() と puts() の2種類の組み込み関数だけをサポートしていました。今回のユーザー定義関数の対応で、どちらも同じやり方で呼び出せる様にします。
準備として、あらかじめグローバルコンテキストに組み込み関数を登録しておきます。
function setupBuiltinFunc(gctx) {
let funcList = gctx['funcList'];
funcList['putn'] = ['builtin_func', '@putn', 'void', 1]; // no func_body for builtin
funcList['puts'] = ['builtin_func', '@puts', 'i32', 1]; // no func_body for builtin
}
// ===== コンパイルの処理 ====
// --- load and parse source ---
const tree = loadAndParseSrc();
// --- compile ----
setupBuiltinFunc(g_ctx);
const ll = compile(tree, g_ctx, l_ctx);
関数呼び出しのコード生成
関数呼び出しのコード生成部分はこのようにしました。引数部分は式になっている可能性があるので、まずその値を算出するコードを生成します。その時のレジスタ名を引数のリストとして保持しておきます。
関数の呼び出しでは、用意した引数のリストを使って call を生成します。組み込み関数 putn() は戻り値void型にしているので、呼び出し結果がi32の場合とvoidの両方に対応するようにしています。（ここもi32型でない例外的な扱いになってしまいました）
function generate(tree, gctx, lctx) {
// ... 省略 ...
if (tree[0] === 'func_call') { // tree = ['func_call', 'name', arg1, arg2, ... ]
const func = getGlobalFunc(gctx, tree[1]);
// func : ['user_defined', '@add', 'i32', 2, '.....']
let block = '';
if (func) {
// --- args ---
let arg = '';
let argBlock = '';
let argList = '';
let i = 0;
while (tree[2 + i]) {
// ---- 引数の値を求める ---
argBlock = argBlock + generate(tree[2 + i], gctx, lctx);
arg = currentTempType(lctx) + ' ' + currentTempName(lctx);
// --- 引数のリストを作る ---
if (i > 0) {
argList = argList + ', ';
}
argList = argList + arg;
i = i + 1;
}
if (i !== func[3]) {
println('-- WARN: arg count NOT same :' + func[1]);
}
// --- call ---
const funcSymbol = func[1];
const funcType = func[2];
block = block + TAB() + ';--- calling func: ' + funcSymbol + '()' + LF();
block = block + argBlock;
if (funcType === 'void') {
block = block + TAB() + 'call void ' + funcSymbol + '(' + argList + ')' + LF();
return block;
}
else if (funcType === 'i32') {
const retName = nextTempName(lctx);
block = block + TAB() + retName + ' = call i32 ' + funcSymbol + '(' + argList + ')' + LF();
return block;
}
else {
println('--- ERROR, unknown func ret type:' + funcType);
abort();
}
}
println('-- ERROR: unknown func name in generate() --');
printObj(tree);
abort();
}
// ... 省略 ...
}
実行結果
先ほど用意した func_add.js をコンパイルしてみましょう。
$ node mininode_compiler10.js func_add.js
生成されたLLVM IRはこちらの通りです。
generated.ll
define i32 @main() {
%t1 = alloca i32, align 4 ;alloc localVariable:n
;--- calling func: @add()
%t2 = or i32 1, 0
%t3 = or i32 2, 0
%t4 = call i32 @add(i32 %t2, i32 %t3)
store i32 %t4, i32* %t1, align 4 ;store init localVariable:n
;--- calling func: @putn()
%t5 = load i32, i32* %t1, align 4 ;load localVariable:n
call void @putn(i32 %t5)
ret i32 %t5
}
; --- user_defined functions ---
define i32 @add(i32, i32) {
%t1 = alloca i32, align 4 ;alloc arg Variable:x
store i32 %0, i32* %t1, align 4 ;store arg Variable:x
%t2 = alloca i32, align 4 ;alloc arg Variable:y
store i32 %1, i32* %t2, align 4 ;store arg Variable:y
%t3 = load i32, i32* %t1, align 4 ;load localVariable:x
%t4 = load i32, i32* %t2, align 4 ;load localVariable:y
%t5 = add i32 %t3, %t4
ret i32 %t5
}
; --- global strings ---
; --- builtin functions ---
@.sputn = private unnamed_addr constant [5 x i8] c"%d\0D\0A\00", align 1
declare i32 @printf(i8*, ...)
declare i32 @puts(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
}
ユーザ定義関数 @add が定義されて、@main の中から呼び出す様になりました。
それでは実際に実行してみましょう。
$ lli generated.ll
3
add(1, 2) が計算されて、putn(3)で「3」が出力されました。ユーザ定義関数、組み込み関数ともに呼び出し成功です。
次回は
いよいよミニコンパイラ編の総仕上げです。関数を利用してFizzBuzzとフィボナッチ数列の計算を実行してみます。
ここまでのソース
ソースコードはGitHubに上げておきます。