LoginSignup
2
1

More than 5 years have passed since last update.

@massie_g(がねこ まさし)

Node.js でつくる Node.js ミニコンパイラ - 06 : 比較を行う

Last updated at Posted at 2018-07-21

はじめに

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

LLVM IRの表記

いつものようにC言語から調べましたが、手順は省略します。記述の形は2項演算子とよく似ています。

等号(===)
  %3 = icmp eq i32 %1, %2

各比較演算子は、それぞれ次の命令に対応します。

  • === ... icmp eq
  • !== ... icmp ne
  • < ... icmp slt
  • <= ... icmp sle
  • > ... icmp sgt
  • >= ... icmp sge

不等号には符号あり/なしの区別があるようです。

比較演算子の生成

generate()の拡張

比較演算子に対応するため、generate()を拡張します。実際の生成は別関数 generateCompareOperator() を呼び出す形にしました。

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

  // --- compare operator ---
  if (tree[0] === '===') {
    const block = generateCompareOperator(tree, 'icmp eq', lctx);
    return block;
  }
  if (tree[0] === '!==') {
    const block = generateCompareOperator(tree, 'icmp ne', lctx);
    return block;
  }
  if (tree[0] === '<') {
    const block = generateCompareOperator(tree, 'icmp slt', lctx);
    return block;
  }
  if (tree[0] === '<=') {
    const block = generateCompareOperator(tree, 'icmp sle', lctx);
    return block;
  }
  if (tree[0] === '>') {
    const block = generateCompareOperator(tree, 'icmp sgt', lctx);
    return block;
  }
  if (tree[0] === '>=') {
    const block = generateCompareOperator(tree, 'icmp sge', lctx);
    return block;
  }

  // ... 省略 ...
}

// --- compare operator ---
function generateCompareOperator(tree, operator, lctx) {
  const block = generateBinaryOperator(tree, operator, lctx);
  return block;
}

generateCompareOperator()では、さらにgenerateBinaryOperator()を流用しています。

エラーの発生

LLVM IRの生成

こちらのjsのコードを用意します。

equal.js
let a;
a = (1 === 2);
putn(a);

比較演算子に対応したミニコンパイラを mininode_compiler06.js とし、用意したjsをコンパイルします。生成された LLVM IR はこちらになります。

generated.ll
define i32 @main() {
  %t1 = alloca i32, align 4 ;alloc localVariable:a

  %t2 = or i32 1, 0
  %t3 = or i32 2, 0
  %t4 = icmp eq i32 %t2, %t3

  store i32 %t4, i32* %t1, align 4 ;store localVariable:a

  %t5 = load i32, i32* %t1, align 4 ;load localVariable:a
  call void @putn(i32 %t5)

  ret i32 %t5
}

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

実行結果

生成したLLVM IRを実行してみると、何やらエラーがで出てしまいました。

$ lli generated.ll
~/Applications/clang/bin/lli: generated.ll:8:13: error: '%t4' defined with type 'i1'
  store i32 %t4, i32* %t1, align 4 ;store localVariable:a

どうやら型が一致していません。調べてみると、比較演算子の結果は1ビット整数（ブール型に相当）になるようです。ミニコンパイラでは型は32ビット符号付き整数に限る予定でしたが、そうは簡単には行かないようです。

型変換の導入

直前の型情報の保持

明示的にi1型（ブール型）を用意することも考えましたが、今回はレジスタに格納する際に暗黙の型変換を行うことにしました。また型変換の要否を判断できるように、直前の演算結果の型をコンテキストに保持する様にしました。

直前の型の保持
function setCurrentTempType(lctx, t) {
  lctx['tempType'] = t;
}

function currentTempType(lctx) {
  return lctx['tempType'];
}

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

  // -- set type as i32 (default type) --
  setCurrentTempType(lctx, 'i32');

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

新しくレジスタ名を発行したタイミングで、直前の型はデフォルトの32ビット符号付き整数(i32)に設定しています。比較演算子では結果の型が i1 になるので、型をセットします。

比較演算子の修正
function generateCompareOperator(tree, operator, lctx) {
  const block = generateBinaryOperator(tree, operator, lctx);
  setCurrentTempType(lctx, 'i1');
  return block;
}

型変換

型の変換（ビット長の拡張）には符号の有無を考慮する必要がありますが、1ビット整数（ブール型）は符号なしと考えられます。そこで拡張には zext 命令を使います。(リファンレンス)

 %t32bit = zext i1 %t1bit to i32

型変換処理を生成するコードを用意します。最後の型がi1だったら型変換を行い、それ以外は何もしません。

// --- cast ---
// cast i1 to i32, if necessary 
function castToI32(lctx) {
  if (currentTempType(lctx) === 'i1') {
    const currentName = currentTempName(lctx);
    const castedName = nextTempName(lctx);
    const castBlock = TAB() + castedName + ' = zext i1 ' + currentName + ' to i32 ;cast i1 to i32' + LF();
    return castBlock;  
  }

  return '';
}

変数の宣言や代入する際に、型変換処理を挟むように変更しました。

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

  if (tree[0] === 'var_decl') {
    // -- check NOT exist --
    const name = tree[1];
    if (name in lctx) {
      println('---ERROR: varbable ALREADY exist (compiler) --');
      abort();
    }

    let block = '';
    // -- alloc on stack --
    const addrVar = nextTempName(lctx);
    block = block + TAB() + addrVar + ' = alloca i32, align 4' + ' ;alloc localVariable:' + name + LF();
    lctx[name] = ['local_var', 'i32', addrVar];

    // --- assign initial value --
    const init = generate(tree[2], lctx);
    if (init !== '') {
      block = block + init;

      // -- cast i1 to i32, if needed --
      const castBlock = castToI32(lctx);
      block = block + castBlock;

      const initValue = currentTempName(lctx);
      block = block + TAB() + 'store i32 ' + initValue + ', i32* ' + addrVar + ', align 4' + ' ;store init localVariable:' + name + LF();
    }

    return block;
  }
  if (tree[0] === 'var_assign') {
    // -- check EXIST --
    const name = tree[1];
    if (name in lctx) {
      let block = '';
      const localVar = lctx[name];
      const addrVar = localVar[2];
      const valBlock =  generate(tree[2], lctx);
      if (valBlock === '') {
        println('---ERROR: var assign value NOT exist --');
        abort();
      }
      block = block + valBlock + LF();

      // -- cast i1 to i32, if needed --
      const castBlock = castToI32(lctx);
      block = block + castBlock;

      const lastValue = currentTempName(lctx);
      block = block + TAB() + 'store i32 ' + lastValue + ', i32* ' + addrVar + ', align 4' + ' ;store localVariable:' + name + LF();

      return block;
    }

    println('---ERROR: varibable NOT declarated (assign)--:' + name);
    abort();
  }

  // ... 省略 ...
}

メイン関数の戻り値でも型変換が必要なケースが考えられるので、同様に変更しました。

function generateMain(mainBlock, lctx) {
  let block = '';
  block = block + 'define i32 @main() {' + LF();
  block = block + mainBlock;

  // -- cast i1 to i32, if needed --
  const castBlock = castToI32(lctx);
  block = block + castBlock;

  const lastTempName = currentTempName(lctx);
  block = block + TAB() + 'ret i32 ' + lastTempName + LF();
  block = block + '}' + LF();
  return block;
}

再び実行

LLVM IRの生成

こちらのjsのコードを用意します。

equal2.js
let a = (1 === 1);
a = (1 === 2);
putn(a);

(1 !== 2);

ミニコンパイラでLLVM IRを生成してみます。

$ node mininode_compiler06.js equal2.js

生成されたIRはこちらです。キャスト処理が含まれる様になりました。

generated.ll
define i32 @main() {
  %t1 = alloca i32, align 4 ;alloc localVariable:a
  %t2 = or i32 1, 0
  %t3 = or i32 1, 0
  %t4 = icmp eq i32 %t2, %t3
  %t5 = zext i1 %t4 to i32 ;cast i1 to i32
  store i32 %t5, i32* %t1, align 4 ;store init localVariable:a

  %t6 = or i32 1, 0
  %t7 = or i32 2, 0
  %t8 = icmp eq i32 %t6, %t7

  %t9 = zext i1 %t8 to i32 ;cast i1 to i32
  store i32 %t9, i32* %t1, align 4 ;store localVariable:a

  %t10 = load i32, i32* %t1, align 4 ;load localVariable:a
  call void @putn(i32 %t10)

  %t11 = or i32 1, 0
  %t12 = or i32 2, 0
  %t13 = icmp ne i32 %t11, %t12

  %t14 = zext i1 %t13 to i32 ;cast i1 to i32
  ret i32 %t14
}

; --- 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
0
$ echo $?
1

終了コードも含めて、ちゃんと実行できるようになりました。

次回は

目標としているFizzBuzzに必要な、条件分岐を実装する予定です。

ここまでのソース

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

2
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
2
1