Node.js でつくる Node.js ミニコンパイラ - 10 : ユーザー定義関数

# はじめに

「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ミニコンパイラ作りにもチャレンジ中です。
[前回はループ処理を使ってFizzBuzzを実現](https://qiita.com/massie_g/items/b84c7ede1a2b91f33bdd)しました。今回はユーザー定義関数に着手します。

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

# LLVM IRでの関数定義と引数の受け渡し

## C言語のソースから調査

いつものように、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ソースを用意します。

```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を並べます

```text:生成したい行
define i32 @add(i32, i32) 
```

```js:引数の数だけ、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;
}
```

また、関数の中で最初に渡された引数の値をローカル変数に読み込む処理を生成する関数も用意します。

```js
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()関数は次の様な形になります。

```js
let funcList = gctx['funcList'];
funcList['add'] = ['user_defined', '@add', 'i32', 2, '関数の定義内容'];
```

グローバルコンテキストにユーザ定義関数を保持する処理、取得する処理を次の様に用意しました。

```js
//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()を拡張します。

```js
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コードの出力

保持しておいた関数の定義は、グローバル文字列定数などと同じ様に最後に出力するようにしました。

```js

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文も必要になります。

```js
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種類の組み込み関数だけをサポートしていました。今回のユーザー定義関数の対応で、どちらも同じやり方で呼び出せる様にします。
準備として、あらかじめグローバルコンテキストに組み込み関数を登録しておきます。

```js
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型でない例外的な扱いになってしまいました）

```js
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はこちらの通りです。

```text: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とフィボナッチ数列の計算を実行してみます。](https://qiita.com/massie_g/items/3b73a8d7ab3324aba36e)

# ここまでのソース

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

- [mininode_compiler10.js](https://github.com/mganeko/mininode_compiler/blob/master/mininode_compiler10.js)
- [sample/func_add.js](https://github.com/mganeko/mininode_compiler/blob/master/sample/func_add.js)