JavaScript
Node.js
LLVM

Node.js でつくる Node.js ミニコンパイラ - 02 : LLVM IRの下調べ

はじめに

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

初めてのLLVM

前回の記事でコンパイラを作るにあたって、バイナリ生成の部分はLLVMに任せることにしました。以前から気になる存在ではあったのですが、近寄りがたく感じていたのも事実です。それを乗り越えるきっかけになったのは、この記事でした。

Clangを使ってLLVM IRを生成、さらに必須ではない部分を削って最低限の記述を探り出すというアプローチで、LLVMをぐっと身近にしてくれました。今回そのアプローチを踏襲してLLVM IRの書き方を探ります.

1番シンプルなコード

用意するのは1を返すだけの一番シンプルなC言語のサンプルです。

one.c
int main() {
  return 1;
}

これをClangで最適化オフでコンパイルし、LLVMの中間表現IRを生成します。

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

得られたLLVM IRはこちら。色々な補足情報が付加されています。

one.ll
; ModuleID = 'one.c'
source_filename = "one.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
  store i32 0, i32* %1, align 4
  ret i32 1
}

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)"}

ここから付加情報を削り、ぎりぎり実行できるところまでシンプルにします。

one_simple.ll
define i32 @main() {
  ret i32 1
}

これなら意味は理解できますね。

  • define で関数宣言
  • i32 が型(符号あり32ビット整数)
  • ret は return

実際に実行してみると、元の one.llも、シンプル化後の one_simple.llも、どちらも終了コードとして1を返すことが確認できます。

$ lli one.ll || echo $?
1
$ lli one_simple.ll || echo $?
1

演算子

足し算 (+)

今度は足し算です。Cのソースはこちら。

add.c
int main() {
  return 1 + 2;
}

Clangで最適化を無効にしてLLVM IRに変換し、付加情報を削るとこうなりました。

add.ll
define i32 @main() {
  %1 = alloca i32, align 4
  store i32 0, i32* %1, align 4
  ret i32 3
}

... うむむ。main()の中身の最初の2行はなんのためにあるのか分かりません。最適化を無効にしているのに、肝心の「1 + 2」の部分は「3」に変換されてしまいました。
もう少しだけ複雑なコードにしたらどうなるでしょうか。今度は変数も使ってみます。

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

生成されたLLVM IR(を削ぎ落としたもの)はこちら。

add2.ll
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
}

重要なのは「ret」の直前の行です。期待通り「add」がありました。おまけについてる nsw はオーバーフロー時の挙動を指定するようです。
これをベースに add を使うできるかぎり単純なIRになるように、手で直しました。

add_simple.ll
define i32 @main() {
  %1 = add i32 1, 2
  ret i32 %1 
}

実行してみると、結果は期待通り3になりした。

$ lli add_simple.ll || echo $?
3

IRの中で%1とあるのは値を一時的に保持するためのレジスタのようなものです。値は1度だけしか代入できず、変更はできないという制約があります。(参照は何回でもできます)
%1, %2, ... という連番で利用し、番号を飛ばすとエラーになるようです。

こちらはOK
define i32 @main() {
  %1 = add i32 1, 2
  %2 = add i32 %1, 4
  ret i32 %2
}
これはエラー
define i32 @main() {
  %1 = add i32 1, 2
  %3 = add i32 %1, 4
  ret i32 %3
}

また連番ではなく、名前をつけることもできるようです。

連番ではない名前もOK
define i32 @main() {
  %1 = add i32 1, 2
  %add_result = add i32 %1, 4
  ret i32 %add_result 
}

引き算、掛け算、割り算、余り

他の演算も同様に調べてみました。結果は以下の通り。

引き算
define i32 @main() {
  %1 = sub i32 3, 2
  ret i32 %1
}
掛け算
define i32 @main() {
  %1 = mul i32 5, 2
  ret i32 %1
}
割り算
define i32 @main() {
  %1 = sdiv i32 5, 2
  ret i32 %1
}
余り
define i32 @main() {
  %1 = srem i32 5, 3
  ret i32 %1
}

割り算(div)と余り(rem)では、符号ありと符号なしを命令で明示的に区別しているようです(LLVM Language Reference Manual)。今回は符号付きのsdiv, sremを使います。

次回は

LLVM IRの調査は一区切りにして、次回はコンパイラの最初のとっかかりに取り組みます。
目標としては足し算(+演算子)を実行できるとこまでを目指します。