Node.js でつくる Node.js ミニコンパイラ - 04 : 四則演算と余りをサポートする

はじめに

「RubyでつくるRuby ゼロから学びなおすプログラミング言語入門」(ラムダノート, Amazon) という本の影響で自分でもミニNode.jsインタープリターを作ってみました。
さらにポッドキャストの Turing Complete FM の影響も受けて、ミニコンパイラ作りにもチャレンジしています。

前回は足し算(+演算子)を実現しました。今回は四則演算の残りと、FizzBuzzに欠かせない余りの計算までできるようにします。

• コンパイラ編 もくじ

コードの整理

前回はコンテキストを導入してレジスタのインデックスを管理するようにしましたが、ハッシュを直接いじるコードでした。機能を追加する前に少しコードを整理しておきます。

ハッシュの扱いを関数に

まず、ハッシュをいじる部分を関数に隠蔽します。

let lctx = {
  'tempIdx': 0, // temp index
};

// -- 次のレジスタ名を得る --
function nextTempName(lctx) {
  let idx = lctx['tempIdx'];
  idx = idx + 1;
  lctx['tempIdx'] = idx;

  const name = _makeTempName(idx);
  return name;
}

// -- 現在のレジスタ名を得る --
function currentTempName(lctx) {
  const idx = lctx['tempIdx'];
  const name = _makeTempName(idx);
  return name;
}

function _makeTempName(idx) {
  return '%t' + idx;
}

整数、+演算子

これを用いて、整数リテラルと+演算子の処理を整理します。

function generate(tree, lctx) {
  // --- int32 literal ---
  if (tree[0] === 'lit') {
    let tempName = nextTempName(lctx);
    return TAB + tempName + ' = or i32 ' + tree[1] + ', 0' + LF;
  }

  // --- binary operator ---
  if (tree[0] === '+') {
    const leftBlock = generate(tree[1], lctx);
    const leftTempName = currentTempName(lctx);
    const rightBlock = generate(tree[2], lctx);
    const rightTempName = currentTempName(lctx);
 
    const tempName = nextTempName(lctx);
    const addBlock = TAB + tempName + ' = add i32 ' + leftTempName + ', ' + rightTempName + LF;
    return (leftBlock + rightBlock + addBlock);
  }

  // ... 省略 ...
}

少しスッキリしました。

メイン関数の生成

同様に、メイン関数の生成部分でも最後のレジスタ名を得る関数を利用するように修正します。

function generateMain(mainBlock, lctx) {
  const lastTempName = currentTempName(lctx);

  // ... 省略 ...
}

四則演算と余りのサポート

二項演算子の生成

残りの演算子(-, *, /, %)は全て項目を2つ取る二項演算子なので、処理は実装済みの+演算子(add)とほぼ同じです。なので、共通する部分を関数にくくり出すことにしました。

function generateBinaryOperator(tree, operator, lctx) {
  const leftBlock = generate(tree[1], lctx);
  const leftTempName = currentTempName(lctx);
  const rightBlock = generate(tree[2], lctx);
  const rightTempName = currentTempName(lctx);

  const tempName = nextTempName(lctx);
  const operatorBlock = TAB + tempName + ' = ' + operator + ' i32 ' + leftTempName + ', ' + rightTempName + LF;
  return (leftBlock + rightBlock + operatorBlock);
}

operator の部分に、LLVMで生成したい演算命令(add, sub, mul, sdiv, srem)を渡します。

演算子を追加

用意した generateBinaryOperator() を使って、残りの演算子を実装しましょう。

function generate(tree, lctx) {
  // ... 省略 ...

  // --- binary operator ---
  if (tree[0] === '+') {
    return generateBinaryOperator(tree, 'add', lctx);
  }
  if (tree[0] === '-') {
    return generateBinaryOperator(tree, 'sub', lctx);
  }
  if (tree[0] === '*') {
    return generateBinaryOperator(tree, 'mul', lctx);
  }
  if (tree[0] === '/') {
    return generateBinaryOperator(tree, 'sdiv', lctx);
  }
  if (tree[0] === '%') {
    return generateBinaryOperator(tree, 'srem', lctx);
  }

  // ... 省略 ...
}

実行結果

いろいろな演算子を含んだコンパイル対象ソースを用意しました。

binoperator.js

// expect 2
(1 + 3*5 - 4/2) % 3;

これを今回のコンパイラ(mininode_compiler04.js)にかけてみましょう。

$ node mininode_compiler04.js binoperator.js

生成されたLLVM IRはこちらです。演算子の評価順も含めて正しいようです。

generated.ll

define i32 @main() {
  %t1 = or i32 1, 0
  %t2 = or i32 3, 0
  %t3 = or i32 5, 0
  %t4 = mul i32 %t2, %t3
  %t5 = add i32 %t1, %t4
  %t6 = or i32 4, 0
  %t7 = or i32 2, 0
  %t8 = sdiv i32 %t6, %t7
  %t9 = sub i32 %t5, %t8
  %t10 = or i32 3, 0
  %t11 = srem i32 %t9, %t10
  ret i32 %t11
}

実行してみます。期待通り 2 が得られます。

$  lli generated.ll || echo $?
2

ミニNode.jsインタープリターからの実行

今回のミニコンパイラを作るにあたって、ミニNode.jsインタープリター(mininode)上で実行できることが目標の一つです。早速実行してみると、いくつか引っかかる部分があります。

• fs.writeFileSync() が simplify() で解釈できない。mininodeではオブジェクト表記（プロパティ、メソッド）をサポートしていないため
• TAB, LFがエラー ... mininodeではグローバル変数をサポートしていないため

writeFile()のモジュール化

module_writefile.js

const fs = require('fs');

// === exports ===
module.exports = writeFile;

function writeFile(filename, str) {
  fs.writeFileSync(filename, str);
  return null;
}

こちらのモジュールを利用するように、ミニNode.jsコンパイラ(mininode_compiler)とミニNode.jsインタープリター(mininode_extra_3.js, module_builtin_extra3.js)どちらも変更しました。

TAB, LFを関数化

function LF() {
  return '\n';
}

function TAB() {
  return '  ';
}

ミニNode.jsインタープリターからの実行

あらためて、ミニインタープリターを使って、ミニコンパイラを動かしてみましょう。

$ node mininode_extra_3.js mininode_compiler04.js binoperator.js
$ lli generated.ll || echo $?
2

無事実行できるようになりました。

次回は

次はローカル変数を扱えるようにする予定です。複数行の対応も行います。

ここまでのソース

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

• mininode_compiler04.js
• module_writefile.js
• mininode_extra_3.js
• module_builtin_extra3.js
• sample/binoperator.js

mininode_compiler04.js

// -------------------------
// mininode_compiler.js - Mini Node.js Compiler by Node.js
// - 01: i32 literal
// - binary operator
//   - 01: +
//   - 04: -, *, /, % 
// - run on mininode interpriter
// -------------------------

"use strict"

const loadAndParseSrc = require('./module_parser_extra2.js');
const println = require('./module_println.js');
const printObj = require('./module_printobj.js');
const abort = require('./module_abort.js');
//const callBuiltinByName = require('./module_builtin_extra2.js');

// --- for compiler ---
/*
const fs = require('fs');
function writeFile(filename, str) {
  fs.writeFileSync(filename, str);
  return null;
}
*/

const writeFile = require('./module_writefile.js');

// ======== for comiler =======
//const LF = '\n';
//const TAB = '  ';

function LF() {
  return '\n';
}

function TAB() {
  return '  ';
}

let lctx = {
  'tempIdx': 0, // temp index
};

function nextTempName(lctx) {
  let idx = lctx['tempIdx'];
  idx = idx + 1;
  lctx['tempIdx'] = idx;

  const name = _makeTempName(idx);
  return name;
}

function currentTempName(lctx) {
  const idx = lctx['tempIdx'];
  const name = _makeTempName(idx);
  return name;
}

function _makeTempName(idx) {
  return '%t' + idx;
}

// ---- compile simplified tree into LLVM IR ---
function compile(tree, lctx) {
  const mainBlock = generate(tree, lctx);
  const mainFunc = generateMain(mainBlock, lctx);
  return mainFunc;
}

// ---- genereate LLVM IR block ---
function generate(tree, lctx) {
  // --- int32 literal ---
  if (tree[0] === 'lit') {
    let tempName = nextTempName(lctx);
    return TAB() + tempName + ' = or i32 ' + tree[1] + ', 0' + LF();
  }

  // --- binary operator ---
  if (tree[0] === '+') {
    return generateBinaryOperator(tree, 'add', lctx);
  }
  if (tree[0] === '-') {
    return generateBinaryOperator(tree, 'sub', lctx);
  }
  if (tree[0] === '*') {
    return generateBinaryOperator(tree, 'mul', lctx);
  }
  if (tree[0] === '/') {
    return generateBinaryOperator(tree, 'sdiv', lctx);
  }
  if (tree[0] === '%') {
    return generateBinaryOperator(tree, 'srem', lctx);
  }

  println('-- ERROR: unknown node in generate() ---');
  printObj(tree);
  abort();
}

function generateBinaryOperator(tree, operator, lctx) {
  const leftBlock = generate(tree[1], lctx);
  const leftTempName = currentTempName(lctx);
  const rightBlock = generate(tree[2], lctx);
  const rightTempName = currentTempName(lctx);

  const tempName = nextTempName(lctx);
  const operatorBlock = TAB() + tempName + ' = ' + operator + ' i32 ' + leftTempName + ', ' + rightTempName + LF();
  return (leftBlock + rightBlock + operatorBlock);
}

function generateMain(mainBlock, lctx) {
  //let lastTempName = '%t' + lctx['tempIdx']
  const lastTempName = currentTempName(lctx);

  let block = '';
  block = block + 'define i32 @main() {' + LF();

  block = block + mainBlock;
  block = block + TAB() + 'ret i32 ' + lastTempName + LF();

  block = block + '}' + LF();
  return block;
}

// ======== start compiler =======

// --- load and parse source ---
const tree = loadAndParseSrc();
//println('--- tree ---');
//printObj(tree);

// --- compile ----
const ll = compile(tree, lctx);
//println('--- result ---');
//println(ll);
writeFile('generated.ll', ll);