昨年から、Esquisという言語を作っている。Rubyっぽい文法の静的型付け言語になる予定で、実行はLLVM IRを経由して行う。

ということで、(クラスベースの)オブジェクト指向言語をLLVM IRで表現する方法について考えていたので、分かったことをまとめておく。既存の実装としては主にCrystalの生成するLLVM IRを参考にした。

オブジェクトをstructに対応させる

LLVMにはstruct型というものがあり、オブジェクトはこれで表現することができる。問題はどのようなstruct型を定義するかだ。

最初に考えたのは、EsObjという型を作って、すべてのオブジェクトを表現するという方法だ。

%EsObj = type { ... }

だがすぐに、この方法では上手くいかない点が見つかった。オブジェクトはインスタンス変数の値を保持する必要があるが、オブジェクトがどのようなインスタンス変数を持つかは属するクラスによって異なるので、一つのLLVM structで全てを表現することはできない。

ということでEsquisの1クラスごとに、対応するstruct型を定義する必要がある(ちなみにCrystalの生成するLLVM IRもそのようになっている)。以下は例である(Esquisの言語仕様はまだちゃんと決めてないので雰囲気で読んで下さい)。

; 1. インスタンス変数を持たないクラス
; class A
; end
%A = type {}

; 2. 整数型のインスタンス変数をひとつ持つクラス
; class B
;   def initialize(Int @i)
;   end
; end
%B = type { i32 }

インスタンス生成

次にインスタンス生成のコンパイルを考える。メモリを確保する必要があるので、今回はBoehm GCを使う。@GC_mallocを呼べばメモリの確保(と、必要に応じてメモリの回収)が行われるので、何バイト確保するのかだけ考えればよい。structのサイズ計算については前の記事で触れた。

これを使って、クラスAのインスタンスを生成する関数を書く。名前は@"A.new"としよう。この関数は新しくメモリを確保して、struct Aのポインタ(%A*)を返す。

define %A* @"A.new"() {
  ; struct Aのサイズを計算する
  %A_size = ptrtoint %"A"* getelementptr (%"A", %"A"* null, i32 1) to i64
  ; メモリを確保する
  %raw_addr = call i8* @GC_malloc(i64 %A_size)
  ; i8*を%A*に変換する
  %addr = bitcast i8* %raw_addr to %A*
  ; 変換後のアドレスを返す
  ret %A* %addr
}

これだけでも動くが、CrystalのLLVM IRを見るとメモリ確保後に@llvm.memsetで内容をゼロクリアしていることが分かる。ゼロクリアしないと、作っている処理系にバグがあったときに毎回挙動が違うことになりかねないので、クリアしたほうが良さそうだ。

declare void @llvm.memset.p0i8.i64(i8* nocapture, i8, i64, i32, i1)
...
  call void @llvm.memset.p0i8.i64(i8* %raw_addr, i8 0, i64 %A_size, i32 4, i1 false)

インスタンスを生成する側は以下のようになる。

define i32 @main() {
  ...
  ; a = A.new
  %a = call %A* @"A.new"()
  ...

メソッド呼び出し

次にメソッド呼び出しを考える。継承はまだ考えないものとする。オブジェクトの型が事前に分かっている(= 呼ばれるメソッドが事前に特定できる)のであれば、以下のように単なる関数呼び出しにコンパイルできる。ただしメソッドに対応する関数は、第一引数として当該オブジェクトのアドレス%selfを受け取るものとする(今回は必要ないが、インスタンス変数の値を参照したりする場合に必要となる)。

; class A
;   def foo
;     213
;   end
; end
%A = type { }
define i32 @"A#foo"(%A* %self) {
  ret i32 213
}

define i32 @main() {
  ...
  ; a = A.new
  %a = call %A* @"A.new"()
  ; a.foo
  %result = call i32 @"A#foo"(%A* %a)
  ...

多態

次に、継承について考える。継承がある場合、ある変数に代入されているオブジェクトのクラスは実行時まで確定しないことがある。

例として、「図形」を表すShapeクラスと、そのサブクラスであるCircleクラスおよびSquareクラスがあるとしよう。各クラスは面積を計算して返すareaというメソッドをもつとする。

以下のような場合、変数sがCircleなのかSquareなのかは、実行時になるまで確定しない。そのため、どちらであっても対応できるようなLLVM IRを生成する必要がある。

; sampleメソッドは、配列のいずれかの要素をランダムに返す
s = [Circle.new(10), Square.new(20)].sample
s.area

クラスID

これに対応するには、各オブジェクトに所属するクラスの情報を入れておく必要がある。例えば各クラスに番号(以下、クラスID)を振り、それをstructの最初の要素とするというのは一つの方法である。

; class A
; end
%A = type { i32 }   ; クラスID 

; class B
;   def initialize(Int @i)
;   end
; end
%B = type { i32, i32 }  ; クラスID、インスタンス変数@i

クラスIDは、クラスのインスタンスを生成したタイミングでそのインスタンスに書き込む。クラスAの場合でいえば、先ほどの@"A.new"を改修する。

多態に対応したメソッド呼び出し

areaメソッドの呼び出しを考える。Shape#areaメソッドを作り、CircleかSquareか分からないオブジェクトsはとりあえずこの関数に渡すことにする。Shape#areaはclass_idを見て、Circle#areaまたはSquare#areaをcallする。

define i32 @"Shape#area"(%"Shape"* %self) {
  %id_addr = getelementptr inbounds %"Shape", %"Shape"* %a, i32 0, i32 0
  %class_id = load i32, i32* %id_addr

  ; %class_idが1ならCircle#areaをcall
  ...
  ; %class_idが2ならSquare#areaをcall
  %sq = bitcast %Shape* %self to %Square*  ; %selfは%Shape*なので、%Square*にキャストする必要がある
  %ret = call i32 @"Square#area"(%Square* %sq)
  ret i32 %ret
}

おわりに

大したことはやってないのだが、分かったことを一つずつまとめていたら長くなってしまった。いままでクラスやオブジェクトといったものがどのように実現されるかについてはあまり深く考えて無かったので、いろいろな発見があって面白かった。