LLVMとコンパイラとVM

Google I/O 2014のARTのプレゼンがyoutubeで公開されてました。
英語字幕を追加された人がおり、英語字幕付きで見れるようです。


プレゼンでは、大きく分けてAOTコンパイル、GC、64bit対応に関して紹介していました。
64bit対応に関してはよくわかっていませんが、
ARTのAOTコンパイルとGCに関して、ざっくり実装がどうなっているのか読んでみた結果をまとめてみようと思います。

(1) ARTのAOTコンパイル

ARTではLLVMを使ったコンパイルに注目が集まっていましたが、
今年になってquick(dalvikのJITコンパイラを改造), portable(LLVM用), sea_ir(謎)に続く、
第4のコンパイラであるoptimizingが追加されたようです。

LLVMはLLVM3.4からC++11で書き直され、Androidでの追従が難しくなったのか、他の理由かはわからないけれども、
ここ1年くらい、portableは大きな変更はされていないです。
LLVM3.3のリビジョンを合わせているため、変更がないといえばないのだが、
周辺のリファクタリングに伴い、修正されているだけのように見えます。

また、上記のGoogle I/O 2014のyoutubeでは、quickに関してはold dalvik jitがベースと言及していましたが、
portable(LLVM)に関してはふれなかったので、いろいろと方針が変わったのかもしれません。

optimizingに関して
===

optimizingは、art/compiler/optimizing配下に入っており、今後はこれが本命になるかもしれない。
2014年の2月頃に最初のコミットがあり、コミットログは以下のようになってました。

initial checkin::

  Author: Nicolas Geoffray 
  Date:   Tue Feb 18 16:43:35 2014 +0000
  
  Initial check-in of an optimizing compiler.
          
  The classes and the names are very much inspired by V8/Dart.
  It currently only supports the RETURN_VOID dex instruction,
  and there is a pretty printer to check if the building of the graph is correct.

V8とDart VMに関して言及がありますが、
Optimizing内部のクラス名、HBasicBlockやHInstructionは、V8のCrankshaft由来っぽい。
クラスの構成やレジスタ割付周りを見ると、V8よりDart VMがベースになっているのかなと思いました。
また、Dart VMからのバックポートっぽいコミットもありました。

  Merge "Import Dart's parallel move resolver."

現在のOptimizingは、Quickと置き換え可能なように作られているらしく、
動かすためには、dex2oatのコマンドラインから制御できるみたいです。

   static dex2oat() ::

    } else if (option.starts_with("--compiler-backend=")) {
      StringPiece backend_str = option.substr(strlen("--compiler-backend=")).data();
      if (backend_str == "Quick") {
        compiler_kind = Compiler::kQuick;
      } else if (backend_str == "Optimizing") { <-- ここで切り替え可能
        compiler_kind = Compiler::kOptimizing;
      } else if (backend_str == "Portable") {
        compiler_kind = Compiler::kPortable;
      }

完成度はどんな感じかというと、まだまだ開発中です。
しかし、アセンブリ出力する後ろのほうから作っているので、既にテスト等ではある程度動いているように見えます。

quickと並行してoptimizingにも頻繁に機能追加されているので、今後に期待です。

quickに関して
===

quickは現在のARTのデフォルトコンパイラです。

以前みたときはdalvik vmっぽいなーと思っていたのですが、
いまはLLVMに似た構造になってました、特にpassやpass_driverが追加されており、内部の見通しが良くなりました。
そのため、dex->mirへ変換して最適化するまでのfrontendが整理されたように思います。

quickのfrontendのpass(mirの最適化)の一覧です。
ディレクトリは、art/compiler/dex

bb_optimizationsの一覧 ::

  CacheFieldLoweringInfo
  CacheMethodLoweringInfo
  CodeLayout
  NullCheckaEliminationAndTypeInference
  ClassInitCheckElimination
  GlobalValueNumbering
  BBCombine
  BBOptimizations

いくつかはdalvik vm jitにはなかった機能であるため、機能追加されており、性能向上してそうです。
また、上記とは別に、quickではinliningとdevirtualizeが追加されたようです。
devirtualizeとは、interface(やvirtual call)で呼ばれた先のmethodを一意(もしくは複数候補に対して)
に特定する機能です。
多くの場合、その後inliningを行います。

dalvik vmのjit compilerにもdevirtualizeがあったのですが、機能が貧弱だったため、
ボトルネックになりうる箇所では、interfaceを使わないなんてテクニックが活用されていたように思います。

ARTでは、その辺にも力を入れていて、
interface/virtual callからconcrete methodを検索する機能に力を入れているようです。
詳細はdex/verified_methodのconcrete_methodの検索を参照。

また、ARTではtrampolineを頻繁に使っている印象を受けました。
entry_pointを事前に作成し、entry_pointへtrampolineでjumpするコードを、コンパイル時に埋め込むことにより、
コンパイルされたコードを実行している最中から、特定の条件に合致したらvmのruntimeに制御を戻し、
vmで何か処理してもどす。

特にコンパイルしたコードで、呼び出し先が未解決(dexにないとか)とか、
特定の処理のslow pathでは頻繁にtrampolineするコードを生成するようでした。

trampolineの際のstackのレイアウトや、entry_pointの詳細、使い方のパターンなんかはまだ読み足りないので、
今後の課題。。

ART GC
===

ARTではGCの実装を頑張っているらしく、Google I/O 2014でも長い時間をかけて解説されていました。

ARTにはコンパイラが3-4個もありましたが、
GCはそれに負けないくらいの種類とオプション、組み合わせが用意されてびびってます。。

Google I/O 2014では、様々なGCのアルゴリズムを組み合わせて、問題を解決しているようでした。

ARTのGCは、Small Objectを高速にざっくり回収するためのstiky GCを頻繁に実行しながら、
低いpause timeでごっそり回収できる、CMS(Concurrent Mark-Sweep)を実行するようです。

また、Mark-Sweepでは解決できないcompactionへ対応するため、Moving Collectorを用意し、
boot時のzygote起動前後や、background実行中の低pauseを要求しないアプリなんかに使うのだとか。

さらにlarge objectの回収時にpause timeが長くなる問題を、
通常のheapではない、large object専用の領域に追い出すことで対応するようでした。


おー、なるほどーとおもって実装のほうチラ見してみたところ、上記のようなことは読み取れないくらい、
様々な実装のオプションがありました。 なんかHotSpotっぽいけど、さらに複雑。。

まず、GCのCollectorTypeの一覧を以下に示します。 ::

  MS (mark-sweep)
  CMS (concurrent mark-sweep)
  SS (mark-sweep hybrid, enables compaction), moving
  GSS (generational), moving
  MC (Mark compact colector), moving
  CC (Mostly concurrent copying collector), moving
  HomogeneousSpaceCompact(homogeneous space compaction collector, moving, CompactionしてOOMに備える

上記をオプションで切り替え可能です。

さらに、上記のCollectorは、
foreground_collector_typeの指定、background_collector_typeの指定により、2つまで併用可能です。
また、collectorを実行時に動的切り替えが可能なようでした。

MovingCollector系は、from/toに分割したSemispace collectorを使うか、
単一領域でbumppointer spaceを併用する形式を選択できる。

TLABの併用を指定できる(ThreadLocalAllocationBuffer), この場合Bumppointerは併用不可なのかな。

GSS(世代別)は上記の組み合わせのうち、HotSpotっぽい組み合わせを選択するようでした。
Semi-space collectorでfrom/toのcopying GC、次の世代でconcurrent_copying_collector,
最後の世代でmark_compact_collectorを使い、かつTLABを併用。

vm heapを確保するmallocの実装を指定できる。
以前はDoug Lea作成のdlmallocがデフォルトだったけど、今はART自作のrosallocがデフォルト。

Allocatorの種類を指定できる。この指定は、alloc()関数実行時のtypeで動的に切り替え可能らしい。

BumpPointerAllocator
TLABAllocator
RosAlloc
DlMalloc
NonMovingAllocator
LOS(Large object space)Allocator

各種参照の保持方法を選択できる。
たぶんデフォルトはcardtable方式で、
ModUnionTableか、RememberedSetを併用可能らしい。


種類とオプションがたくさんありすぎて、何がデフォルトなのかコードを読んだ限りはよく分からなかったけど、
Google I/O 2014で紹介していた構成が、現状のベストな組み合わせになっているのかな

特にforegroundとbackgroundのcollectorを2種併用できる点、
実行時にcollectorを入れ替えできる点に驚きました。

GCのほうも淘汰が進むと、特定の組み合わせだけが残るのでしょうかね。。