on-stack replacement メモ

今、LLVMのソースを読んでいます。そしたら、recompileAndRelinkFunctionなるメソッドを見つけました。後は、実行中のフレームを書き換える目処が付いたらLLVMでon-stack replacementできそうです。フレームを書き換えるところは、GC APIが有望そうなのですが、果たしてどうなることか・・・。
この日記は、Wikiみたいにすると後でいろんなページに飛ばなくて済むから便利かなと思って、新しいエントリーを起さずに更新を繰り返しています。更新履歴を書くようにしました。最後に更新した小項目を前に持ってくるようにしました。ただし、更新履歴, yarv2llvmへの応用のまとめは常に先頭です。

更新履歴

2009/04/06 ShadowStackについて更新しました。
2009/04/06 更新履歴を作りました。

yarv2llvmへの応用のまとめ

  • 結局、gcrootで適当なタイミングでメタデータを生成してやってそれをどっかに保存しておけばスタックの構造が把握でき、on-stack replacementできるのだが、めちゃめちゃ重そう。
  • on-stack replacement対応は速度低下との戦いになりそうだ
  • LLVMのフレームとYARVのフレームを相互変換できるとめちゃめちゃ面白い、に決まってる。
  • ShadowStackGC.cppでは各命令にフックしているが静的にわかるところは静的にメタ情報を生成してコンパイル時にはそのメタ情報のインデックスだけを出力すればいいのではないかと考えています。
    • yarv2llvmでは関数内のスタックフレームの構造はspillしたレジスタ退避領域も含めて静的に決定できるのであらかじめ作っておけると思う
    • プログラムカウンタ毎にフレームの構造が違うため(PUSH/POPするし、最適化すると同じ領域を使いまわすから)、プログラムカウンタ毎にフレームのメタ構造を記録する必要がある。
    • 実際に参照されるのは普通はcall命令の後だけ。再コンパイルが起動されるのはevalやcore#define_methodが呼び出されたときだけなので、一般の関数はその関数を呼び出すチェーンの中しか参照されないから。
    • yarv2llvmのメタ情報はcall命令の後のPCから、スタックのフレーム構造へのハッシュテーブルになると思う。LLVMではメタ情報領域として1ワードあるので、ここにハッシュテーブルのアドレスを格納しようと思う
    • プログラムを解析して、再コンパイルが起こる関数の呼び出しが起こる場合だけメタ情報を作ればよい。多分、ほとんどの関数はメタ情報を作らなくても良くなると思う。
  • 当然だけど正確なGCも実現できると思う
    • これも、アロケーションが生じる関数呼び出しだけメタ情報を作ればよい。再コンパイルが起こる関数ほどじゃないけど意外とメタ情報を削減できると思う
  • llvmrubyにon-stack replacement対応のGC戦略の定義を加える。できれば枠組みだけ定義して中身はRubyでカスタマイズできるとうまい

lib/CodeGen/ShadowStackGC.cpp

これが、GC戦略のカスタマイズのお手本。shadow stackというポータブルなスタックのメタ情報を得るアルゴリズムを実現している。見てみると、次のように命令の生成をフックしてメタ情報を得ている様子

  • gcroot擬似命令の呼び出し。これは、第1引数がallocaの戻り値かチェックして、メタ情報があれば記憶するということをやっている
  • gep命令。アクセス履歴を取っているみたいだが良くわからない。
    • よくみたら、CreateGEPはprivateメソッド。フックではなく、純粋にコード生成用のものと思われる
  • Shadow stackのオーバヘッドに触れたblogの記事を発見

http://flyingfrogblog.blogspot.com/2009/03/current-shadow-stack-overheads-in-hlvm.html

    • HVLMとocaml bindingはやはり要調査か？
  • 他もいろいろやってそうなので後で書く

llvmruby対応

llvmrubyを改造してGCのコードを吐けるようにしました。まだ不完全です。
http://github.com/miura1729/llvmruby/tree/master

  def test_setgc
    m = LLVM::Module.new('test_gc')
    type = Type::function(MACHINE_WORD, [])
    f = m.get_or_insert_function("gcfunc", type)
    f.set_gc("shadow-stack")

    type = Type::function(Type::VoidTy, [Type.pointer(P_CHAR), P_CHAR])
    gcroot = m.get_or_insert_function("llvm.gcroot", type)

    b = f.create_block.builder
    aa = b.alloca(P_CHAR, 1)
    mp = b.int_to_ptr(3.llvm, P_CHAR)
    b.call(gcroot, aa, mp)
    b.return(0.llvm)
    ExecutionEngine.get(m)
    m.write_bitcode("test/gc.bc")
  end

は、次のようなコードが出てきます。
set_gc("shadow-stack")と、b.call(gcroot, aa, mp)が肝です。

	.text
	.align	16
	.globl	_gcfunc
	.def	 _gcfunc;	.scl	2;	.type	32;	.endef
_gcfunc:
Llabel1:
	subl	$12, %esp
	movl	_llvm_gc_root_chain, %eax
	movl	$___gc_gcfunc, 4(%esp)
	movl	%eax, (%esp)
	leal	(%esp), %eax
	movl	%eax, _llvm_gc_root_chain
	movl	$0, 8(%esp)
	movl	(%esp), %eax
	movl	%eax, _llvm_gc_root_chain
	xorl	%eax, %eax
	addl	$12, %esp
	ret
	.section	.data$linkoncellvm_gc_root_chain,"w"
	.comm	_llvm_gc_root_chain,4
	.data
	.align	8
___gc_gcfunc:
	.long	1
	.long	1
	.long	3

生成コード読んでみた。

  • _llvm_gc_root_chainにスタックフレームが、リンクリストの形ではいる
  • スタックトップがcalleeのフレーム
  • +4 オフセットをつけるとメタ情報のポインタ
  • メタ情報は__gc_関数名 というラベルで生成。ちゃんと上記、calleeフレーム, メタ情報のポインタもエントリーがある。メタ情報として1が入っている。あとは、llvm.gcrootで設定した値が入る

思ったより軽いという印象。もっと複雑なことをやらせるとわからないけど。

GC　APIの概要(嘘かも知れないので注意)

  • 関数ごとにGC戦略の名前を指定する。その名前に対応するプラグインがコンパイル時に使われる。こんな感じ
    • define void @f() gc "name" { ...
  • プラグインでは、次のような疑似関数がどうコンパイルされるか決める。
    1. declare void @llvm.gcroot(i8** %ptrloc, i8* %metadata)
    2. declare i8* @llvm.gcread(i8* %ObjPtr, i8** %Ptr)
    3. declare void @llvm.gcwrite(i8* %P1, i8* %Obj, i8** %P2)
  • llvm.gcrootはptrlocをGCから守らなければならないオブジェクトであることを宣言する。metadataはシステムでは詳細は決まっていないのでプラグインとLLVM IRのコンパイラで整合を取ってユーザが意味づけを決めないといけない(と思う)
  • llvm.gcread, llvm.gcwriteはload/storeの代わりに使う。１つ引数が多いのはオブジェクトの先頭を渡すため。オブジェクトの先頭にマークビットがあったりする場合を想定していると思う。

再コンパイルAPI

  /// recompileAndRelinkFunction - This method is used to force a function
  /// which has already been compiled to be compiled again, possibly
  /// after it has been modified. Then the entry to the old copy is overwritten
  /// with a branch to the new copy. If there was no old copy, this acts
  /// just like VM::getPointerToFunction().
  ///
  virtual void *recompileAndRelinkFunction(Function *F) = 0;

(include/llvm/ExecutionEngine/ExecutionEngine.h)

/// recompileAndRelinkFunction - This method is used to force a function
/// which has already been compiled, to be compiled again, possibly
/// after it has been modified. Then the entry to the old copy is overwritten
/// with a branch to the new copy. If there was no old copy, this acts
/// just like JIT::getPointerToFunction().
///
void *JIT::recompileAndRelinkFunction(Function *F) {
  void *OldAddr = getPointerToGlobalIfAvailable(F);

  // If it's not already compiled there is no reason to patch it up.
  if (OldAddr == 0) { return getPointerToFunction(F); }

  // Delete the old function mapping.
  addGlobalMapping(F, 0);

  // Recodegen the function
  runJITOnFunction(F);

  // Update state, forward the old function to the new function.
  void *Addr = getPointerToGlobalIfAvailable(F);
  assert(Addr && "Code generation didn't add function to GlobalAddress table!");
  TJI.replaceMachineCodeForFunction(OldAddr, Addr);
  return Addr;
}

(lib/ExecutionEngine/JIT/JIT.cpp)

ソースコード読み TODO

(lib/CodeGen/GCStrategy.cpp)