LoginSignup
4
1

More than 5 years have passed since last update.

@massie_g(がねこ まさし)

Node.js でつくる Node.js ミニコンパイラ - 05 : ローカル変数を使う

Last updated at Posted at 2018-07-18

はじめに

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

前回は四則演算と余りを実装しました。今回はローカル変数をサポートします。合わせて複数行への対応と、簡易デバッグ出力を用意します。

簡易デバッグ出力

変数を使えるようになると、自然と複数行のコードを書きたくなります。複数行のコードを書くと、最後の終了コードだけでなく、途中の状態も出力したくなります。
そこで簡易的なデバッグ出力を用意します。

CのソースからLLVM IRを調べる

デバッグ出力は組み込み関数として用意しますが、その関数呼び出しをLLVM IRでどう表現するのか調べます。

まず、C言語のソースを用意します。putn()が今回用意した関数で、32ビット符号付き整数を出力します。内部では普通にprintf()を利用しています。

putn.c
#include <stdio.h>

// デバッグ出力
void putn(int n) {
  printf("%d\n", n);
}

int main() {
  putn(123);
  return 0;
}

これをClangでLLVM IRに変換します。

$ clang -S -emit-llvm -O0 putn.c

得られたLLVM IRから、付加情報を削ったものがこちら。

putn.ll
@.str = private unnamed_addr constant [4 x i8] c"%d\0A\00", align 1

define void @putn(i32) #0 {
  %2 = alloca i32, align 4
  store i32 %0, i32* %2, align 4
  %3 = load i32, i32* %2, align 4
  %4 = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([6 x i8], [6 x i8]* @.str, i32 0, i32 0), i32 %3)
  ret void
}

declare i32 @printf(i8*, ...) #1

define i32 @main() #0 {
  %1 = alloca i32, align 4
  store i32 0, i32* %1, align 4
  call void @putn(i32 123)
  ret i32 0
}

これをlliで実行しても、残念ながら改行が正しく行われません。（改行のエスケープシーケンスが間違っていました。修正したら正しく動きました）そこで手を加えつつ更にシンプルにしたものがこちらです。

putn_simple.ll
@.str = private unnamed_addr constant [5 x i8] c"%d\0D\0A\00", align 1

define void @putn(i32) {
  %2 = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([5 x i8], [5 x i8]* @.str, i32 0, i32 0), i32 %0)
  ret void
}

declare i32 @printf(i8*, ...)

define i32 @main() {
  call void @putn(i32 123)
  ret i32 0
}

ここから次のことが読み取れます。

  • 標準ライブラリの関数を利用するには、 declare で利用したい関数を宣言する
  • 自分で関数を定義するには、 define を使う
  • 関数の宣言/定義は、戻り値の型、引数の型を指定する
    • 関数内から引数を参照するには、%0, %1, ... を使う
    • おそらく最後の引数の次には、関数からの戻り先が格納されている
  • 関数を呼ぶには call を使う。戻り値の型や引数の型を明示的に記述する
  • 文字列リテラルは、「@名前」という形で、型(i8=8ビット整数)と長さを指定して確保しておく

putn()を用意する

コンパイル時に上記のputn()を一緒に書き出すための関数generateBuiltin()を用意し、compile()から利用します。

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

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*)' +　LFR();
  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)' +　BR();
  block = block + '  ret void' +　LF();
  block = block + '}' +　LF();
  return block;
}

putn()を利用する

このputs()を利用するjsのソースコードを用意します。

putn.js
putn(111);

これをパースして単純化した結果がこちらです。

[ 'func_call', 'putn', [ 'lit', 111 ] ]

暫定的に、関数呼び出し func_call が登場したら、putn を呼び出すようにLLVM IRを生成します。

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

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

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

  // ... 省略 ...
}

コンパイル結果

ここまで対応したミニコンパイラで、putn.js をコンパイルした結果がこちらです。

generated.ll
define i32 @main() {
  %t1 = or i32 111, 0
  call void @putn(i32 %t1)
  ret i32 %t1
}

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

無事「111」が出力されました。これで動作確認が楽になりました。

複数行の対応

次は複数行への対応です。先ほど対応したputn()を使った2行のjsソースコードを要します。

multi_lines.js
putn(1);
putn(2+3);

これをパースして単純化した結果はこちらです。

[ 'stmts',
  [ 'func_call', 'putn', [ 'lit', 1 ] ],
  [ 'func_call', 'putn', [ '+', [ 'lit', 2 ], [ 'lit', 3 ] ] ] ]

stmts が登場したら、各行に対応する要素を順番に処理すれば良さそうです。

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

  // --- multi lines ---
  if (tree[0] === 'stmts') {
    let i = 1;
    let block = '';
    while (tree[i]) {
      block = block + generate(tree[i], lctx) + LF();
      i = i + 1;
    }
    return block;
  }

  // ... 省略 ...
}

ローカル変数の利用

変数を扱うには、次の3つの処理があります。

  • 変数の宣言（と初期値の代入）: var_decl
  • 変数の再代入: var_assign
  • 変数の参照: var_ref

これをLLVM IRで表現するのか、C言語から変換して調べてみましょう。

C言語からLLVM IRを生成

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

add_var.c
int main() {
  int a = 1;
  return a + 2;
}

ClangでLLVM IRを生成します。

$ clang -S -emit-llvm -O0 add_var.c

生成されたIRはこちら。

add_var.ll
; ModuleID = 'add_var.c'
source_filename = "add_var.c"
target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-apple-macosx10.12.0"

; Function Attrs: noinline nounwind ssp uwtable
define i32 @main() #0 {
  %1 = alloca i32, align 4
  %2 = alloca i32, align 4
  store i32 0, i32* %1, align 4
  store i32 1, i32* %2, align 4
  %3 = load i32, i32* %2, align 4
  %4 = add nsw i32 %3, 2
  ret i32 %4
}

attributes #0 = { noinline nounwind ssp uwtable "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="penryn" "target-features"="+cx16,+fxsr,+mmx,+sse,+sse2,+sse3,+sse4.1,+ssse3,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }

!llvm.module.flags = !{!0}
!llvm.ident = !{!1}

!0 = !{i32 1, !"PIC Level", i32 2}
!1 = !{!"Apple LLVM version 9.0.0 (clang-900.0.39.2)"}

これをシンプルに整形した結果がこちらです。

define i32 @main() #0 {
  %1 = alloca i32, align 4
  store i32 1, i32* %1, align 4

  %2 = load i32, i32* %1, align 4
  %3 = add i32 %2, 2
  ret i32 %3
}

新しく登場した命令は、それぞれ次の役割を持っています。ちょうど変数を扱う各要素に対応しています。

  • alloca でスタック上に変数領域を確保し、そのアドレスをレジスタに代入 ... var_decl
  • store で、レジスタの示すアドレスに値を代入 ... var_assign
  • load で、レジスタの示すアドレスの値を、別のレジスタに取り出す ... var_ref

JavaScriptの場合

上記と同様のjsのコードを用意します。ただしせっかくなので今回用意したputn()を使って画面に出力しましょう。

add_var.js
let a = 1;
a = a + 2;
putn(a);

パースして単純化したTreeはこちらです。var_decl, var_assign, var_ref 全てが登場します。

[ 'stmts',
  [ 'var_decl', 'a', [ 'lit', 1 ] ],
  [ 'var_assign', 'a', [ '+', [ 'var_ref', 'a' ], [ 'lit', 2 ] ] ],
  [ 'func_call', 'putn', [ 'var_ref', 'a' ] ] ]

コード(LLVM IR)の生成

コンテキストで変数定義を保持

新しい変数が宣言されたら、コンテキスト lctx に次の様に格納することにしました。

lctx['変数名'] = ['local_var', 'i32', 'アドレスを保持しているレジスタ名']

変数の宣言

var_decl に該当するIRの生成はこのようにしました。初期値がある場合は、その値を求めて代入(store)します。

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 !== '') {
      const initVar = currentTempName(lctx);
      block = block + init;
      block = block + TAB() + 'store i32 ' + initVar + ', i32* ' + addrVar + ', align 4' + ' ;store init localVariable:' + name + LF();
    }

    return block;
  }

  // ... 省略 ...
}

IRを見てわかる様に、'; 〜'というコメントも生成するようにしています。

変数への代入

変数の代入処理はこうします。コンテキスト lctxからアドレスを保持しているレジスタを取得し、右辺を処理した結果を代入(store)します。

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

  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();
      }
      const lastVar = currentTempName(lctx)
      block = block + valBlock + LF();
      block = block + TAB() + 'store i32 ' + lastVar + ', i32* ' + addrVar + ', align 4' + ' ;store localVariable:' + name + LF();

      return block;
    }

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

  // ... 省略 ...
}

変数の参照

変数の参照でも、コンテキスト lctxからアドレスを保持しているレジスタを取得し、その内容を新しいレジスタに取り出します(lod)。

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

  if (tree[0] === 'var_ref') {
    // -- check EXIST --
    const name = tree[1];
    if (name in lctx) {
      let block = '';
      const localVar = lctx[name];
      const addrVar = localVar[2];
      const val = nextTempName(lctx);

      // %t1 = load i32, i32* %v1, align 4
      block = TAB() + val + ' = load i32, i32* ' + addrVar + ', align 4' + ' ;load localVariable:' + name + LF();
      return block;
    }

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

  // ... 省略 ...
}

実行結果

コンパイルしてみると

ここまで実装したミニコンパイラのソースを mininode_compile05.js とします。先ほどの add_var.js をコンパイルして見ましょう。

$ node mininode_compiler05.js add_var.js

生成されたLLVM IRはこちらです。

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

  %t3 = load i32, i32* %t1, align 4 ;load localVariable:a
  %t4 = or i32 2, 0
  %t5 = add i32 %t3, %t4

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

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

  ret i32 %t6
}

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

putn()による出力も含めて、うまく動きました。

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

$ node mininode_extra_3.js mininode_compiler05.js add_var.js

こちらもOKです。

バイナリの生成

バイナリ生成も確認して見ましょう。

$ llc generated.ll -O0 -march=x86-64 -filetype=obj -o=generated.o
$ ld -arch x86_64 -macosx_version_min 10.12.0 generated.o -lSystem -o add_var
$ ls add_var
add_var*
$ ./add_var
3

動きました！ 標準ライブラリもちゃんとリンクされている様です。

次回は

次は比較演算子を実装する予定です。

これまでのソース

ソースコードはGitHubに上げておきます。

4
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
4
1