Dart VM Advent Calendar 2012 12/07¶
VM Advent Calendar 2012/12/07
Dart VMの概要(3)¶
前回の続き、fiboが2000回以上よばれて最適化JITコンパイルされるところから！！！
Dart VMは、2000回以上実行された関数は、returnする際にOptimizeFunctionを呼び出し、最適化JITコンパイルします。
stub_OptimizeFunction自体は、Dart VMのRuntime API(OptimizeInvokedFunction)を呼び出すためのstubです。
Returnのコード
0xb30482b1 ba11042db3 mov edx,0xb32d0411 'Function 'fibo': static.'
0xb30482b6 ff422b inc [edx+0x2b] // fiboのusage_counterをinc
0xb30482b9 817a2bd0070000 cmp [edx+0x2b],0x7d0 // 2000と比較してhotcode check
0xb30482c0 7c05 jl 0xb30482c7
0xb30482c2 e8e185ffff call 0xb30408a8 [stub: OptimizeFunction]
stub: OptimizeFuntion:
Code for stub '_stub_OptimizeFunction': {
0xb30408a8 55 push ebp
0xb30408a9 89e5 mov ebp,esp
0xb30408ab 6800000000 push 0
0xb30408b0 50 push eax
0xb30408b1 52 push edx
0xb30408b2 b950070b08 mov ecx,0x80b0750
0xb30408b7 ba01000000 mov edx,0x1
0xb30408bc e867f73702 call 0xb53c0028 [stub: CallToRuntime]
0xb30408c1 5a pop edx
0xb30408c2 58 pop eax
0xb30408c3 89ec mov esp,ebp
0xb30408c5 5d pop ebp
0xb30408c6 c3 ret
Dart VMは、JITコンパイルしたコードに、Dart VMが提供するRuntime APIを呼び出すStubを埋め込みます。
fiboの中間表現(非最適化時)¶
==== file:///home/elise/language/dart/work/adven/fibo.dart_::_fibo
B0[graph]
B1[target]
CheckStackOverflow:2()
t0 <- LoadLocal:3(n lvl:0) //変数nをLoad(引数という概念はここではない)
t1 <- Constant:4(#2) //定数2を生成
Branch if RelationalOp:5(<, t0, t1) goto (2, 3) //(t0 < t1)だったら、B2へjump、もしくはB3へjump
B2[target]
t0 <- LoadLocal:7(n lvl:0) //定数nをLoad
Return:8(t0) //Return
B3[target]
t0 <- LoadLocal:9(n lvl:0) //変数nをLoad
PushArgument:10(t0) //nを引数にpush
t0 <- Constant:11(#1) //定数1を生成
PushArgument:12(t0) //#1を引数にpush
t0 <- InstanceCall:13(-, t0, t0) //InstanceCall (-)(n, #1)みたいなメソッドコール
PushArgument:14(t0) //返値をpush [`n-1`]
t0 <- StaticCall:15(fibo t0) //fibo(n-1)に相当
PushArgument:16(t0) //返値をpush [`fibo(n-1)`]
t0 <- LoadLocal:17(n lvl:0) //変数nをLoad
PushArgument:18(t0) //nをpush
t0 <- Constant:19(#2) //定数2を生成
PushArgument:20(t0) //#2をpush
t0 <- InstanceCall:21(-, t0, t0) //InstanceCall (-)(n, 2)みたいなメソッドコール
PushArgument:22(t0) //返値をpush [`fibo(n-1)`, `n-2`]
t0 <- StaticCall:23(fibo t0) //fibo(n-2)に相当
PushArgument:24(t0) //返値をpush [`fibo(n-1)`, `fibo(n-2)`]
t0 <- InstanceCall:25(+, t0, t0) //InstanceCall (+)(`fibo(n-1)`, `fibo(n-2)`)
Return:26(t0) //返値をreturn
JITコンパイル(非最適化)とJITコンパイル(最適化)の中間表現を比較してみます。
fiboの中間表現(最適化時、型情報のフィードバック後)¶
==== file:///home/elise/language/dart/work/adven/fibo.dart_::_fibo
B0[graph] {
v0 <- Constant:29(#null)
v1 <- Parameter:30(0)
}
B1[target]
CheckStackOverflow:2()
v2 <- Constant:4(#2)
Branch if RelationalOp:5(<, v1, v2 IC[1: _Smi@0x36924d72, _Smi@0x36924d72 #588]) goto (2, 3) env={ v1, v1, v2 }
B2[target] ^ (<)のreceiverがSmi ^ arg1がSmi
Return:8(v1)
B3[target]
PushArgument:10(v1)
v3 <- Constant:11(#1)
PushArgument:12(v3)
v4 <- InstanceCall:13(-, v1, v3 IC[1: _Smi@0x36924d72, _Smi@0x36924d72 #309]) env={ v1, a0, a1 }
PushArgument:14(v4) ^ (-)のreceiverがSmi ^ arg1がSmi
v5 <- StaticCall:15(fibo v4) env={ v1, a0 }
PushArgument:16(v5)
PushArgument:18(v1)
v6 <- Constant:19(#2)
PushArgument:20(v6)
v7 <- InstanceCall:21(-, v1, v6 IC[1: _Smi@0x36924d72, _Smi@0x36924d72 #278]) env={ v1, a0, a1, a2 }
PushArgument:22(v7) ^ (-)のreceiverがSmi ^ arg1がSmi
v8 <- StaticCall:23(fibo v7) env={ v1, a0, a1 }
PushArgument:24(v8)
v9 <- InstanceCall:25(+, v5, v8 IC[1: _Smi@0x36924d72, _Smi@0x36924d72 #274]) env={ v1, a0, a1 }
Return:26(v9) ^ (+)のreceiverがSmi ^ arg1がSmi
非最適化のfiboのコードを実行した際に、InlineCacheは値がSmi型であると記録しておきます。
最適化JITコンパイル時には、その型情報をフィードバックして最適化を行います。
型情報は、receiverとargsのtripleで記録されます。
仮に、複数の型が混在する場合、
[PT: _Smi, _Smi | _Smi, _Double | _Double, _Smi]のような表現になるはずです。
Note
一言断っておくと、JITコンパイル(非最適化)の中間表現は非SSA形式です。
JITコンパイル(最適化)の中間表現はSSA形式になるため、 IRのdefinevalueはtからvに変わって、重ならないようにnumberingされます。
fiboの中間表現(最適化後)¶
==== file:///home/elise/language/dart/work/adven/fibo.dart_::_fibo
0: B0[graph] {
v0 <- Constant:29(#null)
v1 <- Parameter:30(0) {PT: dynamic} {PCid: dynamic}
}
2: B1[target] ParallelMove eax <- S-1
4: CheckStackOverflow:2()
6: v2 <- Constant:4(#2) {PT: _Smi@0x36924d72} {PCid: _Smi@0x36924d72} [2, 2]
8: CheckSmi:5(v1) env={ v1 [eax], v1 [eax], v2 [C] }
10: Branch if RelationalOp:5(<, v1, v2 IC[1: _Smi@0x36924d72, _Smi@0x36924d72 #588]) goto (2, 3)
12: B2[target]
13: ParallelMove eax <- eax
14: Return:8(v1)
16: B3[target]
18: v3 <- Constant:11(#1) {PT: _Smi@0x36924d72} {PCid: _Smi@0x36924d72} [1, 1]
20: ParallelMove ecx <- eax
//v4 <- InstanceCall:13(-, v1, v3 IC[1: _Smi@0x36924d72, _Smi@0x36924d72 #309]) env={ v1, a0, a1 }
20: v4 <- BinarySmiOp:13(-, v1, v3) {PT: _Smi@0x36924d72} {PCid: _Smi@0x36924d72} [1, 1073741822] -o <-- Smi型に特殊化された中間表現
22: PushArgument:14(v4) {PCid: dynamic}
//v5 <- StaticCall:15(fibo v4) env={ v1, a0 }
24: v5 <- StaticCall:15(fibo v4) {PT: dynamic} {PCid: dynamic} env={ v1 [S-1], a0 }
25: ParallelMove eax <- eax
26: ParallelMove ecx <- S-1, S+0 <- eax
//v7 <- InstanceCall:21(-, v1, v6 IC[1: _Smi@0x36924d72, _Smi@0x36924d72 #278]) env={ v1, a0, a1, a2 }
26: v7 <- BinarySmiOp:21(-, v1, v2) {PT: _Smi@0x36924d72} {PCid: _Smi@0x36924d72} [0, 1073741821] -o <-- Smi型に特殊化された中間表現
28: PushArgument:22(v7) {PCid: dynamic}
//v8 <- StaticCall:23(fibo v7) env={ v1, a0, a1 }
30: v8 <- StaticCall:23(fibo v7) {PT: dynamic} {PCid: dynamic} env={ v1 [S-1], v5 [S+0], a0 }
31: ParallelMove ecx <- eax, eax <- S+0
32: CheckSmi:25(v5) env={ v1 [S-1], v5 [eax], v8 [ecx] }
34: CheckSmi:25(v8) env={ v1 [S-1], v5 [eax], v8 [ecx] }
36: ParallelMove edx <- eax
//v9 <- InstanceCall:25(+, v5, v8 IC[1: _Smi@0x36924d72, _Smi@0x36924d72 #274]) env={ v1, a0, a1 }
36: v9 <- BinarySmiOp:25(+, v5, v8) {PT: _Smi@0x36924d72} {PCid: _Smi@0x36924d72} [-inf, +inf] +o env={ v1 [S-1], v5 [eax], v8 [ecx] } <-- Smi型に特殊化された中間表現
37: ParallelMove eax <- edx
38: Return:26(v9)
最適化後の中間表現です。最適化により様々な変化があります。
- 型情報のフィードバック結果から型推論を行う。
- CheckSmi命令の挿入
- 型推論の結果、高速な中間表現に置き換える。
- スタックとレジスタ割付けが行われ、ParallelMove命令に置き換える。
高速な命令に置き換える、では、Smi型でのみ呼び出すInstanceCallをBinarySmiOpに置き換えています。
BinarySmiOpは、receiverとarg1がSmi型である場合に置き換えられる(特殊化)命令になります。
BinarySmiOpは、最終的にアセンブラ数命令に変換されます。
Type Guard¶
Check命令の挿入は、少々特殊なことを行います。
24: v5 <- StaticCall:15(fibo v4)
30: v8 <- StaticCall:23(fibo v7)
32: CheckSmi:25(v5) env={ v1 [S-1], v5 [eax], v8 [ecx] } <-- CheckSmi
34: CheckSmi:25(v8) env={ v1 [S-1], v5 [eax], v8 [ecx] } <-- CheckSmi
36: ParallelMove edx <- eax
36: v9 <- BinarySmiOp:25(+, v5, v8) {PT: _Smi@0x36924d72} {PCid: _Smi@0x36924d72}
上記は、v5とv8をCheckSmi命令で、Smi型であることを保証した上で(Smi型のGuard) BinarySmiOp(+, v5, v8)を行っています。
v5とv8は、StaiticCall(fibo)の返値であり、Smi型である保証がないため、CheckSmiで確認を行っています。
BinarySmiOpはSmi型でしか動作しない命令であるため、 Smi型以外が入ってきたら異常終了してしまう可能性があります。
仮に、StaticCall(fibo)の返値がdouble型やnull型だった場合、CheckSmiにひっかかってしまいます。
Smi型以外だった場合、CheckSmiは脱最適化(Deoptimization)を行い、この最適化したコードを捨て、 元のどんな型でも動く非最適化コードに戻します。
型情報のフィードバックを受けたこの最適化JITコンパイルが生成したコードは、 Smi型が入ってくる限り非常に高速に動作します。
fiboのアセンブラ(最適化)¶
Code for optimized function 'file:///home/elise/language/dart/work/adven/fibo.dart_::_fibo' {
0xb3048308 55 push ebp // v0 <- Constant:29(#null)
0xb3048309 89e5 mov ebp,esp // v1 <- Parameter:30(0) {PT: dynamic} {PCid: dynamic}
0xb304830b e800000000 call 0xb3048310
0xb3048310 83ec04 sub esp,0x4
0xb3048313 8b4508 mov eax,[ebp+0x8] // 2: B1[target] ParallelMove eax <- S-1
0xb3048316 3b257c7a6b08 cmp esp,[0x86b7a7c] // 4: CheckStackOverflow:2()
0xb304831c 0f8668000000 jna 0xb304838a
// 8: CheckSmi:5(v1) env={ v1 [eax], v1 [eax], v2 [C] }
0xb3048322 a801 test al,0x1 // check SmiTag
0xb3048324 0f8573000000 jnz 0xb304839d // goto DeoptimizeStub
// 6: v2 <- Constant:4(#2) {PT: _Smi@0x36924d72} {PCid: _Smi@0x36924d72} [2, 2]
// 10: Branch if RelationalOp:5(<, v1, v2 IC[1: _Smi@0x36924d72, _Smi@0x36924d72 #588]) goto (2, 3)
0xb304832a 83f804 cmp eax,0x4 // if n < 2 // (n<<1 < 2<<1)
0xb304832d 0f8d05000000 jnl 0xb3048338 // goto B3[target]
0xb3048333 89ec mov esp,ebp // 14: Return:8(v1)
0xb3048335 5d pop ebp
0xb3048336 c3 ret
0xb3048337 90 nop // 16: B3[target]
// 18: v3 <- Constant:11(#1) {PT: _Smi@0x36924d72} {PCid: _Smi@0x36924d72} [1, 1]
// 20: ParallelMove ecx <- eax
// 20: v4 <- BinarySmiOp:13(-, v1, v3) {PT: _Smi@0x36924d72} {PCid: _Smi@0x36924d72} [1, 1073741822] -o
0xb3048338 89c1 mov ecx,eax
0xb304833a 83e902 sub ecx,0x2 // n - 1 (n<<1 - 1<<1)
0xb304833d 51 push ecx // 22: PushArgument:14(v4) {PCid: dynamic}
0xb304833e bab16b0fb3 mov edx,0xb30f6bb1 // 24: v5 <- StaticCall:15(fibo v4) {PT: dynamic} {PCid: dynamic} env={ v1 [S-1], a0 }
0xb3048343 e8c0803702 call 0xb53c0408 [stub: CallStaticFunction] // call fibo(n-1)
0xb3048348 83c404 add esp,0x4
0xb304834b 8b4d08 mov ecx,[ebp+0x8] // 26: ParallelMove ecx <- S-1, S+0 <- eax
0xb304834e 8945f8 mov [ebp-0x8],eax
// 26: v7 <- BinarySmiOp:21(-, v1, v2) {PT: _Smi@0x36924d72} {PCid: _Smi@0x36924d72} [0, 1073741821] -o
0xb3048351 83e904 sub ecx,0x4 // n - 2 (n<<1 - 2<<1)
0xb3048354 51 push ecx // 28: PushArgument:22(v7) {PCid: dynamic}
0xb3048355 bab16b0fb3 mov edx,0xb30f6bb1 // 30: v8 <- StaticCall:23(fibo v7) {PT: dynamic} {PCid: dynamic} env={ v1 [S-1], v5 [S+0], a0 }
0xb304835a e8a9803702 call 0xb53c0408 [stub: CallStaticFunction] // call fibo(n-2)
0xb304835f 83c404 add esp,0x4
0xb3048362 89c1 mov ecx,eax // 31: ParallelMove ecx <- eax, eax <- S+0
0xb3048364 8b45f8 mov eax,[ebp-0x8]
// 32: CheckSmi:25(v5) env={ v1 [S-1], v5 [eax], v8 [ecx] }
0xb3048367 a801 test al,0x1 // check SmiTag
0xb3048369 0f8533000000 jnz 0xb30483a2 // goto DeoptimizeStub
// 34: CheckSmi:25(v8) env={ v1 [S-1], v5 [eax], v8 [ecx] }
0xb304836f f6c101 test_b ecx,0x1 // check SmiTag
0xb3048372 0f852f000000 jnz 0xb30483a7 // goto DeoptimizeStub
0xb3048378 89c2 mov edx,eax // 36: ParallelMove edx <- eax
// 36: v9 <- BinarySmiOp:25(+, v5, v8) {PT: _Smi@0x36924d72} {PCid: _Smi@0x36924d72} [-inf, +inf] +o env={ v1 [S-1], v5 [eax], v8 [ecx] }
0xb304837a 03d1 add edx,ecx // fibo(n-1) + fibo(n-2)
0xb304837c 0f802a000000 jo 0xb30483ac
0xb3048382 89d0 mov eax,edx // 37: ParallelMove eax <- edx
0xb3048384 89ec mov esp,ebp // 38: Return:26(v9)
0xb3048386 5d pop ebp
0xb3048387 c3 ret
//Runtime
0xb3048388 90 nop
0xb3048389 cc int3
0xb304838a 50 push eax
0xb304838b b9f0c20a08 mov ecx,0x80ac2f0
0xb3048390 ba00000000 mov edx,0
0xb3048395 e88e7c3702 call 0xb53c0028 [stub: CallToRuntime]
0xb304839a 58 pop eax
0xb304839b eb85 jmp 0xb3048322
0xb304839d e8c6813702 call 0xb53c0568 [stub: Deoptimize]
0xb30483a2 e8c1813702 call 0xb53c0568 [stub: Deoptimize]
0xb30483a7 e8bc813702 call 0xb53c0568 [stub: Deoptimize]
0xb30483ac e8b7813702 call 0xb53c0568 [stub: Deoptimize]
0xb30483b1 e972813702 jmp 0xb53c0528 [stub: FixCallersTarget]
0xb30483b6 e94d823702 jmp 0xb53c0608 [stub: DeoptimizeLazy]
}
非最適化のコードと比較して、高速なコードを生成しています。
特に、InlineCacheのStub呼び出しをしていたところは、すべて高速な命令に置き換えられており、 BinarySmiOpは、アセンブラ1-2命令になっています。
またBinarySmiOpでは、両者ともSmi型であるため、1bit左シフト済みの値が入っているはずですが、
右シフトで元の値に戻さずに、add sub cmp命令を行っています。
print(ret)など、int値を参照する場合には、右シフトが挿入されるはずです。
Dart VMの初期化、JITコンパイル(非最適化)、JITコンパイル(最適化)、fibo(40)の計算まで、 大体900msecくらいなので、かなり速いと思います。
corei7(ia32)にて、
dart$ time dart --time-all fibo.dart
102334155
ret = 897 ms <-- fibo(40)の処理時間
Script Loading : 93 micros. <-- Dart VMがソースコードを読み込んだ合計時間
Snapshot Creation : 0 micros. <-- Snapshotの合計時間、最後に行うんだっけかな？
Isolate initialization : 11019 micros. <-- Isolateの初期化時間
Function compilation : 11742 micros. <-- Compileの合計時間 main, fibo以外のcoreも含む。
Bootstrap of core classes : 28 micros. <-- Bootstrap時の、core libのdeserialize処理時間
Total runtime for isolate : 909578 micros. <-- main以降の合計時間
real 0m0.924s <-- VMの起動時間は、25,000 microsくらいかな？
user 0m0.920s
sys 0m0.000s
まとめ¶
- 最適化JITコンパイルは、型情報のフィードバックをもらう。
- 最適化JITコンパイルは、特殊化された中間表現に置き換える。
- 特殊化された中間表現は、少ないアセンブラ命令に落ちる。