はじめに

「RubyでつくるRuby ゼロから学びなおすプログラミング言語入門」(ラムダノート, Amazon) と Turing Complete FM の影響で、Node.jsミニコンパイラ作りにもチャレンジ中です。
前回はループ処理(while)を実装しました。今回はそれを使ってFizzBuzzに挑みます。

コンパイラ編もくじ

文字列の出力

LLVM IR で文字列出力

FizzBuzzを実現するには、固定の文字列も表示できる必要があります。ちょうどCの標準ライブラリにある puts() が呼べる様にしたいところです。
固定文字列を使うのは、すでに自分で用意したputn()から標準ライブラリのprintf()を呼び出す際のフォーマット指定に使っていました。同様にすれば、文字列をLLVM IRから表示することができます。

puts_simple.ll

@.string_message1 = private constant [17 x i8] c"hello llvm world\00", align 1


define i32 @main() {
  %t1 = getelementptr inbounds [17 x i8], [17 x i8]* @.string_message1, i32 0, i32 0
  %t2 = call i32 @puts(i8* %t1)
  ret i32 0
}

declare i32 @puts(i8*)

文字列リテラルの確保

関連モジュールの準備

ミニNode.js（元のミニRubyも）では、"hello"という文字列リテラルをパースすると次の単純化した表現が得られます。

[ 'lit', 'hello' ]

この段階で数値なのか文字列なのか型をもっていなので、JavaScriptの typeof を使って識別することにしました。この関数はミニNode.jsインタープリターで実行できる様にコンパイラ本体ではなく、別モジュールに追い出しています。

module_gettypeof.js

module.exports = getTypeOf;

function getTypeOf(obj) {
  const t = typeof obj;
  return t;
}

ついでに、後で必要になる文字列の長さを取得する関数も別モジュールで用意します。

module_getlength.js

module.exports = getLength;

function getLength(obj) {
  const len = obj.length;
  return len;
}

LLVM IRではバイト数で文字列の長さを指定する必要がありますが、用意した関数ではバイト数にはなっていません。なので現状は正しく動作するのは1バイトで表現できるASCII文字列だけになっています。

グローバルコンテキストの導入

文字列リテラルを保持しておくために、グルーバルコンテキストを導入することにしました。今回はこのような形でハッシュを用意して、LLVMコードを生成する関数に渡して上げます。

let g_ctx = {
  'strIdx' : 0, // string index
  'strList' : {}, // string hash:  strList['@s_1'] = ['xxxxx', length]
}

また、文字列を新たに追加したり、追加済みの文字列を取り出す関数を用意します。
コンテキストで管理しているインデックスをカウントアップしながら「@名前」を決め、終了文字(\00)を含めた文字列と長さを保持するようにしました。


const getLength = require('./module_getlength.js');

// -- add global string, return name of string --
function addGlobalString(str, gctx) {
  // -- strings --
  // '@.s_1' : ['xxxxxxx', len],

  // --- name of string
  let idx = gctx['strIdx'];
  const name = '@.s_' + idx;
  idx = idx + 1;
  gctx['strIdx'] = idx;

  const len = getLength(str);
  const cstr = str + '\\00';
  const clen = len + 1;

  const globalString = [cstr, clen];
  let strList = gctx['strList'];
  strList[name] = globalString;

  return name;
}

function getGlobalString(name, gctx) {
  const strList = gctx['strList'];
  return strList[name];
}

用意したグローバルコンテキストを、compile(), generate()といった関数の引数で渡す様に変更します。関数本体だけでなく、関数を呼び出している箇所全てを変更してあげます。

修正例

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

generate(tree[2], lctx);

// --- after ---
function generate(tree, gctx, lctx) {
  // ... 省略 ...
}

generate(tree[2], gctx, lctx);

文字列リテラルの処理

実際に文字列リテラルを扱う部分は、次の様に拡張しました。

const getTypeOf = require('./module_gettypeof.js');

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

if (tree[0] === 'lit') {
    const t = getTypeOf(tree[1]); // move typeof to module
    if (t === 'number') {
      // --- int32 literal ---
      const tempName = nextTempName(lctx);
      return TAB() + tempName + ' = or i32 ' + tree[1] + ', 0' + LF();
    }

    if (t === 'string') {
      // --- string literal ---
      const name = addGlobalString(tree[1], gctx);
      const gstr = getGlobalString(name, gctx); // ['xxxxxx', length]
      const tempName = nextTempName(lctx);
      setCurrentTempType(lctx, 'i8*');
      const block = TAB() + tempName + ' = getelementptr inbounds [' + gstr[1] +  ' x i8], [' + gstr[1] + ' x i8]* ' + name + ', i32 0, i32 0' + LF();
      return block;
    }

    println('---ERROR: unknwon type of literal--:' + t);
    abort();
  }

  // ... 省略 ...
}

グローバル文字列のコード出力

グローバルコンテキストに確保した文字列を、最終的にLLVM IRに書き出してやる必要があります。今回はこのように対応しました。


const getKeys = require('./module_getkeys.js');

function compile(tree, gctx, lctx) {
  const mainBlock = generate(tree, gctx, lctx);
  const mainFunc = generateMain(mainBlock, lctx);
  const builtinFunc = generateBuiltin();
  const globalStrings = generateGlobalString(gctx);
  return mainFunc + globalStrings + builtinFunc;
}

function generateGlobalString(gctx) {
  let block = LF();
  block = block + '; --- global strings ---' + LF();

  const strList = gctx['strList'];  
  const keys = getKeys(strList);
  const len = getLength(keys);
  let key;
  let i = 0;
  let gstr;
  while (i < len) {
    key = keys[i];
    gstr = strList[key]; // ['xxxxxxx', length]
    block = block + key + ' = private constant [' + gstr[1] + ' x i8] c"' + gstr[0] + '", align 1' + LF();
    i = i + 1;
  }

  return block;
}

グローバル文字列のコードを書き出す generateGlobalString() を用意して、compile() から呼び出しています。
新しくハッシュの情報を取得する関数が必要になったので、こちらモジュールとして用意しました。

module_getkeys.js

module.exports = getKeys;

function getKeys(hash) {
  let keys = [];
  for (let key in hash) {
    keys.push(key);
  }

  return keys;
}

puts()関数のサポート

ようやく puts() 関数を作る準備ができました。まず、Cの標準ライブラリのputs()の宣言を追加します。

function generateBuiltin() {
  let block = LF();
  block = block + '; --- builtin functions ---' + LF();
  block = block + '@.sputn = private unnamed_addr constant [5 x i8] c"%d\\0D\\0A\\00", align 1' + LF();
  block = block + 'declare i32 @printf(i8*, ...)' + LF();
  block = block + 'declare i32 @puts(i8*)' + LF(); // <=== puts()の宣言を追加
  block = block + LF();
  block = block + 'define void @putn(i32) {' + LF();
  block = block + '  %r1 = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([5 x i8], [5 x i8]* @.sputn, i32 0, i32 0), i32 %0)' + LF();
  block = block + '  ret void' + LF();
  block = block + '}' + LF();
  return block;
}

ダミーで用意した関数呼び出しを、putn()決め打ちから、putn()とputs()の2種類を使い分けられるよにします。


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

  if (tree[0] === 'func_call') {
    if (tree[1] === 'putn') {
      const argBlock = generate(tree[2], gctx, lctx);
      const argTempName = currentTempName(lctx);
      const callBlock = TAB() + 'call void @putn(i32 ' + argTempName + ')' + LF();
      return argBlock + callBlock;
    }

    if (tree[1] === 'puts') {
      const argBlock = generate(tree[2], gctx, lctx);
      const argTempName = currentTempName(lctx);
      const retTempName = nextTempName(lctx);
      const callBlock = TAB() + retTempName + ' = call i32 @puts(i8* ' + argTempName + ')' + LF();
      return argBlock + callBlock;
    }

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

  // ... 省略 ...
}

実行結果

こちらのjsソースを用意しました。

puts.js

puts('hello mininode compiler!');

これをコンパイルしてみます。（ここまでのコンパイラのコードは、mininode_compiler09.jsとします)

$ node mininode_compiler09.js puts.js

生成されたIIVM IRはこちらです。「@.s_0」として、グローバル文字列定数が確保されています。

generated.ll

define i32 @main() {
  %t1 = getelementptr inbounds [25 x i8], [25 x i8]* @.s_0, i32 0, i32 0
  %t2 = call i32 @puts(i8* %t1)
  ret i32 %t2
}

; --- global strings ---
@.s_0 = private constant [25 x i8] c"hello mininode compiler!\00", align 1

; --- 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
}

実行してみると、正しく文字列が表示されました。予想より手間がかかってしまいました。

$ lli generated.ll
hello mininode compiler!

FizzBuzzの達成 (ループ版）

ようやく目標の一つであるFizzBuzzを実現する準備が整いました。用意したjsコードはこちらです。

fizzbuzz_loop.js

let i = 1;
while (i <= 100) {
  if (i % (3*5) === 0) {
    puts('FizzBuzz');
  }
  else if (i % 3 === 0) {
    puts('Fizz');
  }
  else if (i % 5 === 0) {
    puts('Buzz');
  }
  else {
    putn(i);
  }

  i = i + 1;
}

コンパイル結果はこちらです。だんだん長くなってきました。

generated.ll

define i32 @main() {
  %t1 = alloca i32, align 4 ;alloc localVariable:i
  %t2 = or i32 1, 0
  store i32 %t2, i32* %t1, align 4 ;store init localVariable:i

  br label %L3_WHILE_BEGIN ; -- jump to begin of while_block:L3_ --
L3_WHILE_BEGIN:
  %t4 = load i32, i32* %t1, align 4 ;load localVariable:i
  %t5 = or i32 100, 0
  %t6 = icmp sle i32 %t4, %t5
  br i1 %t6, label %L3_WHILE_BODY, label %L3_WHILE_END
L3_WHILE_BODY:
  ; --- begin if_block:L7_ ---
  %t8 = load i32, i32* %t1, align 4 ;load localVariable:i
  %t9 = or i32 3, 0
  %t10 = or i32 5, 0
  %t11 = mul i32 %t9, %t10
  %t12 = srem i32 %t8, %t11
  %t13 = or i32 0, 0
  %t14 = icmp eq i32 %t12, %t13
  br i1 %t14, label %L7_POSITIVE, label %L7_NEGATIVE
L7_POSITIVE:
  %t15 = getelementptr inbounds [9 x i8], [9 x i8]* @.s_0, i32 0, i32 0
  %t16 = call i32 @puts(i8* %t15)
  br label %L7_END
L7_NEGATIVE:
  ; --- begin if_block:L17_ ---
  %t18 = load i32, i32* %t1, align 4 ;load localVariable:i
  %t19 = or i32 3, 0
  %t20 = srem i32 %t18, %t19
  %t21 = or i32 0, 0
  %t22 = icmp eq i32 %t20, %t21
  br i1 %t22, label %L17_POSITIVE, label %L17_NEGATIVE
L17_POSITIVE:
  %t23 = getelementptr inbounds [5 x i8], [5 x i8]* @.s_1, i32 0, i32 0
  %t24 = call i32 @puts(i8* %t23)
  br label %L17_END
L17_NEGATIVE:
  ; --- begin if_block:L25_ ---
  %t26 = load i32, i32* %t1, align 4 ;load localVariable:i
  %t27 = or i32 5, 0
  %t28 = srem i32 %t26, %t27
  %t29 = or i32 0, 0
  %t30 = icmp eq i32 %t28, %t29
  br i1 %t30, label %L25_POSITIVE, label %L25_NEGATIVE
L25_POSITIVE:
  %t31 = getelementptr inbounds [5 x i8], [5 x i8]* @.s_2, i32 0, i32 0
  %t32 = call i32 @puts(i8* %t31)
  br label %L25_END
L25_NEGATIVE:
  %t33 = load i32, i32* %t1, align 4 ;load localVariable:i
  call void @putn(i32 %t33)
  br label %L25_END
L25_END: ; --- end if_block:L25_ ---
  br label %L17_END
L17_END: ; --- end if_block:L17_ ---
  br label %L7_END
L7_END: ; --- end if_block:L7_ ---

  %t34 = load i32, i32* %t1, align 4 ;load localVariable:i
  %t35 = or i32 1, 0
  %t36 = add i32 %t34, %t35

  store i32 %t36, i32* %t1, align 4 ;store localVariable:i

  br label %L3_WHILE_BEGIN
L3_WHILE_END: ; --- end while_block:L3_ ---

  ret i32 %t36
}

; --- global strings ---
@.s_0 = private constant [9 x i8] c"FizzBuzz\00", align 1
@.s_1 = private constant [5 x i8] c"Fizz\00", align 1
@.s_2 = private constant [5 x i8] c"Buzz\00", align 1

; --- 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
}

それでは、実行してみます。ドキドキします。

$ lli generated.ll
1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
FizzBuzz
16
...省略...
98
Fizz
Buzz

ちゃんと動きました！

次回は

いよいよユーザー定義関数に着手します。だんだんゴールが見えてきました。

ここまでのソース

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