JITの出力するx64アセンブリを深追いしてみた
こないだ行ってきたThe Server Side Java Symposium 2008で、JITの出力するアセンブリコードを見る方法がわかったので、早速試してみました。
まず最初に注意事項。
要するに、VMは日々進化しているので、この結果が将来のJVMでも有効だとは限りません、ということです。でも、現在でもVMはこの程度の事は既にやっているんだ、という役には立つでしょう。
さて、この機能を利用するには、デバッグ版のJDKが必要です。このテスト走行ではJDK6 u10 b14を使いました。ここからダウンロードできます。
$ java -fullversion java full version "1.6.0_10-beta-fastdebug-b14"
まずは小手調べ。
public class Main { public static void main(String[] args) { for(int i=0; i<100; i++) foo(); } private static void foo() { for(int i=0; i<100; i++) bar(); } private static void bar() { } }
これをコンパイルして、次のようにして走らせます。
$ java -XX:+PrintOptoAssembly -server -cp . Main
この-XX:+PrintOptoAssemblyが魔法のオプションです。この例では、fooメソッドがコンパイルされると次の結果が表示されました:
000 B1: # N1 <- BLOCK HEAD IS JUNK Freq: 100
000 pushq rbp
subq rsp, #16 # Create frame
nop # nop for patch_verified_entry
006 addq rsp, 16 # Destroy frame
popq rbp
testl rax, [rip + #offset_to_poll_page] # Safepoint: poll for GC
011 ret見てわかるように、bar()の呼び出しとループは死んでいるコードと正しく判定されて、跡形もありません。素晴らしい。
では次はもう少し面白いコードに行ってみましょう。
private static byte[] foo() { byte[] buf = new byte[256]; for( int i=0; i<buf.length; i++ ) buf[i] = 0; return buf; }
これは次のような結果になります。
000 B1: # B15 B2 <- BLOCK HEAD IS JUNK Freq: 78
000 # stack bang
pushq rbp
subq rsp, #80 # Create frame
00c # TLS is in R15
00c movq R8, [R15 + #120 (8-bit)] # ptr
010 movq R10, R8 # spill
013 addq R10, #280 # ptr
01a cmpq R10, [R15 + #136 (32-bit)] # raw ptr
021 jge,u B15 P=0.000100 C=-1.000000
021
027 B2: # B3 <- B1 Freq: 77.9922
027 movq [R15 + #120 (8-bit)], R10 # ptr
02b PREFETCHNTA [R10 + #256 (32-bit)] # Prefetch to non-temporal cache for write
033 movq [R8], 0x0000000000000001 # ptr
03a PREFETCHNTA [R10 + #320 (32-bit)] # Prefetch to non-temporal cache for write
042 movq RDI, R8 # spill
045 addq RDI, #24 # ptr
049 PREFETCHNTA [R10 + #384 (32-bit)] # Prefetch to non-temporal cache for write
051 movl RCX, #32 # long (unsigned 32-bit)
056 movq R10, precise klass [B: 0x00002aaaab076708:Constant:exact * # ptr
060 movq [R8 + #8 (8-bit)], R10 # ptr
064 movl [R8 + #16 (8-bit)], #256 # int
06c xorl rax, rax # ClearArray:
rep stosq # Store rax to *rdi++ while rcx--
071
071 B3: # B4 <- B16 B2 Freq: 78
071
071 # checkcastPP of R8
071 xorl R10, R10 # int
074 movl R9, #256 # int
nop # 2 bytes pad for loops and calls
07c B4: # B17 B5 <- B3 B5 Loop: B4-B5 inner stride: not constant pre of N153 Freq: 19850.2
07c cmpl R10, #256 # unsigned
083 jge,u B17 P=0.000001 C=-1.000000
083
089 B5: # B4 B6 <- B4 Freq: 19850.2
089 movslq R11, R10 # i2l
08c movb [R8 + #24 + R11], #0 # byte
092 incl R10 # int
095 cmpl R10, #8
099 jlt,s B4 P=0.996072 C=22313.000000
099
09b B6: # B11 B7 <- B5 Freq: 77.9799
09b subl R9, R10 # int
09e andl R9, #-16 # int
0a2 addl R9, R10 # int
0a5 cmpl R10, R9
0a8 jge,s B11 P=0.500000 C=-1.000000
0a8
0aa B7: # B8 <- B6 Freq: 38.9899
0aa PXOR XMM0,XMM0 ! replicate8B
nop # 2 bytes pad for loops and calls
0b0 B8: # B10 B9 <- B7 B9 Loop: B8-B9 inner stride: not constant main of N85 Freq: 9925.09
0b0 movslq R11, R10 # i2l
0b3 MOVQ [R8 + #24 + R11],XMM0 ! packed8B
0ba movl R11, R10 # spill
0bd addl R11, #16 # int
0c1 movslq R10, R10 # i2l
0c4 MOVQ [R8 + #32 + R10],XMM0 ! packed8B
0cb cmpl R11, R9
0ce jge,s B10 P=0.003928 C=22313.000000
0ce
0d0 B9: # B8 <- B8 Freq: 9886.1
0d0 movl R10, R11 # spill
0d3 jmp,s B8
0d3
0d5 B10: # B11 <- B8 Freq: 38.9899
0d5 movl R10, R11 # spill
0d5
0d8 B11: # B14 B12 <- B6 B10 Freq: 77.9799
0d8 cmpl R10, #256
0df jge,s B14 P=0.500000 C=-1.000000
nop # 3 bytes pad for loops and calls
0e4 B12: # B17 B13 <- B11 B13 Loop: B12-B13 inner stride: not constant post of N153 Freq: 9922.54
0e4 cmpl R10, #256 # unsigned
0eb jge,us B17 P=0.000001 C=-1.000000
0eb
0ed B13: # B12 B14 <- B12 Freq: 9922.53
0ed movslq R11, R10 # i2l
0f0 movb [R8 + #24 + R11], #0 # byte
0f6 incl R10 # int
0f9 cmpl R10, #256
100 jlt,s B12 P=0.996072 C=22313.000000
100
102 B14: # N1 <- B13 B11 Freq: 77.9698
102 movq RAX, R8 # spill
105 addq rsp, 80 # Destroy frame
popq rbp
testl rax, [rip + #offset_to_poll_page] # Safepoint: poll for GC
110 ret
110
111 B15: # B18 B16 <- B1 Freq: 0.00780129
111 movq RSI, precise klass [B: 0x00002aaaab076708:Constant:exact * # ptr
11b movl RDX, #256 # int
120 nop # 3 bytes pad for loops and calls
123 call,static wrapper for: _new_array_Java
# Main::foo @ bci:3 L[0]=_ L[1]=_
#
128
128 B16: # B3 <- B15 Freq: 0.00780114
# Block is sole successor of call
128 movq R8, RAX # spill
12b jmp B3
12b
130 B17: # N1 <- B12 B4 Freq: 1e-06
130 movl RSI, #-28 # int
135 movq RBP, R8 # spill
138 movl [rsp + #0], R10 # spill
13c nop # 3 bytes pad for loops and calls
13f call,static wrapper for: uncommon_trap(reason='range_check' action='make_not_entrant')
# Main::foo @ bci:17 L[0]=RBP L[1]=rsp + #0 STK[0]=RBP STK[1]=rsp + #0 STK[2]=#0
# AllocatedObj(0x0000000040c31880)
144 int3 # ShouldNotReachHere
144
151 B18: # N1 <- B15 Freq: 7.80129e-08
151 # exception oop is in rax; no code emitted
151 movq RSI, RAX # spill
154 addq rsp, 80 # Destroy frame
popq rbp
159 jmp rethrow_stub僕のようにx86でアセンブラの知識が止まっている人向けに復習すると、R8-R15はamd64で追加された汎用レジスタです。R0-R7は旧来のAX,BX,...レジスタを64bitに拡張したものです。amd64についてのより詳しい説明はこちらへどうぞ。
冒頭の部分(00c-027)が配列をアロケートする部分で、出だしから既にかなり面白いです。 コメントにあるように、R15はスレッド毎のデータ構造へのポインタとして使われているようで、R15[120]は中でもスレッドローカルなヒープの利用可能領域の先頭を指しているようです。つまり、byte[]の割り当ては、単にこのスレッドローカルな領域から256+32バイトを割り振るだけです。Cにありがちな空きメモリリストを辿ったりとかいった処理は一切ありません。かなり高速です。ここでスレッドローカル領域にメモリが足りないと（リミットはR15[136]）、ラベルB15から始まる遅いアロケートコードにジャンプします。このコードは、エデン領域から新たなスレッドローカルヒープを割り当てたりするのでしょう。
でもって、06cで配列の先頭がR8にセットされると、その後には初期化コードが続きます(033-071)。オブジェクト毎に24バイトのヘッダブロックがあるようで、最初の8バイトはロックかGCか何かに使われているようで、次の8バイトがクラスへのポインタ、でさらに次の8バイトが配列の長さです。06cが配列をゼロクリアしているのですが、元のJavaコードでは配列の値は後で書き換えるのでこの初期化は必要ないのですが、JITはこの分の最適化には失敗しています。とはいえ、配列の長さが8の倍数なのを活かして、stosbではなくstosqを使って8バイトづつ初期化しているのは見逃せません。
02b, 03aと049にあるプリフェッチは今ひとつよくわかりません。見た感じ、次のオブジェクトアロケーションに備えてヒープの次の領域をキャッシュに持ってくるような感じに見えますが、256,320,384のオフセット値はどういう意味があるんでしょうか？amd64のキャッシュのライン長って何バイトだっけ？
074の時点では、R8は'buf'変数のポインタ、R9が配列の長さになっています。注目するべき部分は、buf.lengthがいつも256だというのを正しくJITは認識しているらしく、R9の初期化はmovl R9,256であってmovl R9,[R8+16]ではありません。賢いですね。R9の初期化がループの外なのも注目です。ということは良くありがちな次のようなコードには全く意味がないということがわかります。
int len = buf.length; for( int i=0; i<len; i++ ) ...
同様に、ループの方向を逆にしてi<buf.lengthを節約しようというせせこましい最適化にも、もはや意味がないことがわかります。
このループのコンパイルされ方は非常に興味深いです。まず、ウォームアップとでもいうべき部分(07c-099)があって、想像ではこれは8バイト境界に並ぶまでの部分を担当し、次にメインのループ部分(09b-0d3)が続いて、一気に8バイトづつ0クリアしていきます。これが終わるとクールダウンの部分(0d5-100)で、最後の8バイト境界から残りの部分を埋めると思われます。元のJavaコードでは配列の大きさは必ず8の倍数なのでこのメイン部分以外は不要なのですが、JITはそこには気づいていないようです。同様に、配列はそもそも０に初期化されているのでこのループ全体が無意味なのですが、ループ全体を捨てる、というような最適化はできていません。
とはいえ、このループの展開の仕方はなかなか見事です。1バイト毎の書き込みを8バイトごとにまとめて安全だということには正しく気がついているからです。ループをもう少し複雑にした時にどうなるかは興味深いところです。特にメインループ部分に配列の境界チェックをするコードがないのも秀逸です。
さて、では次に行ってみましょう。JDK6にはロック粗粒度化とロック除去が入っているのは有名な話ですね。では、この働きを見てみましょう。このために、次のコードをコンパイルします。
private static void foo() { Vector v = new Vector(); v.add("abc"); v.add("def"); v.add("ghi"); }
実行結果は次の様になります。
000 B1: # B10 B2 <- BLOCK HEAD IS JUNK Freq: 20168
000 # stack bang
pushq rbp
subq rsp, #80 # Create frame
00c # TLS is in R15
00c movq RAX, [R15 + #120 (8-bit)] # ptr
010 movq R10, RAX # spill
013 addq R10, #40 # ptr
017 # TLS is in R15
017 cmpq R10, [R15 + #136 (32-bit)] # raw ptr
01e jge,u B10 P=0.000100 C=-1.000000
01e
024 B2: # B3 <- B1 Freq: 20166
024 # TLS is in R15
024 movq [R15 + #120 (8-bit)], R10 # ptr
028 PREFETCHNTA [R10 + #256 (32-bit)] # Prefetch to non-temporal cache for write
030 movq R10, precise klass java/util/Vector: 0x00002aaaf2649f38:Constant:exact * # ptr
03a movq R11, [R10 + #176 (32-bit)] # ptr
041 movq [RAX], R11 # ptr
044 movq [RAX + #8 (8-bit)], R10 # ptr
048 movq [RAX + #16 (8-bit)], #0 # long
050 movq [RAX + #24 (8-bit)], #0 # long
058 movq [RAX + #32 (8-bit)], #0 # long
058
060 B3: # B12 B4 <- B11 B2 Freq: 20168
060
060 movq RBP, RAX # spill
063 # checkcastPP of RBP
063 # TLS is in R15
063 movq R11, [R15 + #120 (8-bit)] # ptr
067 movq R10, R11 # spill
06a addq R10, #104 # ptr
06e # TLS is in R15
06e cmpq R10, [R15 + #136 (32-bit)] # raw ptr
075 jge,u B12 P=0.000100 C=-1.000000
075
07b B4: # B5 <- B3 Freq: 20166
07b # TLS is in R15
07b movq [R15 + #120 (8-bit)], R10 # ptr
07f PREFETCHNTA [R10 + #256 (32-bit)] # Prefetch to non-temporal cache for write
087 movq [R11], 0x0000000000000001 # ptr
08e PREFETCHNTA [R10 + #320 (32-bit)] # Prefetch to non-temporal cache for write
096 movq RDI, R11 # spill
099 addq RDI, #24 # ptr
09d PREFETCHNTA [R10 + #384 (32-bit)] # Prefetch to non-temporal cache for write
0a5 movq R10, precise klass [Ljava/lang/Object;: 0x00002aaaf264e928:Constant:exact * # ptr
0af movq [R11 + #8 (8-bit)], R10 # ptr
0b3 movl [R11 + #16 (8-bit)], #10 # int
0bb movl RCX, #10 # long (unsigned 32-bit)
0c0 xorl rax, rax # ClearArray:
rep stosq # Store rax to *rdi++ while rcx--
0c5
0c5 B5: # B16 B6 <- B13 B4 Freq: 20168
0c5
0c5 # checkcastPP of R11
0c5 movq [RBP + #32 (8-bit)], R11 # ptr ! Field java/util/Vector.elementData
0c9 movq R10, RBP # ptr -> long
0cc shrq R10, #9
0d0 movq RDX, java/lang/String:exact * # ptr
0da movq R11, 0x00002a959c9da580 # ptr
0e4 movb [R11 + R10], #0 # byte
0e9 movq RSI, RBP # spill
0ec nop # 3 bytes pad for loops and calls
0ef call,static java.util.Vector::add
# Main::foo @ bci:11 L[0]=RBP
# AllocatedObj(0x0000000040b30680)
0f4
0f4 B6: # B15 B7 <- B5 Freq: 20167.6
# Block is sole successor of call
0f4 movq RDX, java/lang/String:exact * # ptr
0fe movq RSI, RBP # spill
101 nop # 2 bytes pad for loops and calls
103 call,static java.util.Vector::add
# Main::foo @ bci:18 L[0]=RBP
# AllocatedObj(0x0000000040b30680)
108
108 B7: # B14 B8 <- B6 Freq: 20167.2
# Block is sole successor of call
108 movq RDX, java/lang/String:exact * # ptr
112 movq RSI, RBP # spill
115 nop # 2 bytes pad for loops and calls
117 call,static java.util.Vector::add
# Main::foo @ bci:25 L[0]=_
#
11c
11c B8: # N1 <- B7 Freq: 20166.8
# Block is sole successor of call
11c addq rsp, 80 # Destroy frame
popq rbp
testl rax, [rip + #offset_to_poll_page] # Safepoint: poll for GC
127 ret
（以下略）Vectorのアロケート部分(00c-058)は前見た配列確保のこーどとそっくりなので、あえて説明の必要はないでしょう。048-058の部分はフィールドを初期化する部分です。続いてはVector.elementDataを確保する似たようなコードが続きます(060-0C0)。
ここで注目すべきはコンストラクタの展開のされ方です。元のソースではこれは次のように定義されているのですが、
public Vector(int initialCapacity, int capacityIncrement) { super(); if (initialCapacity < 0) throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); this.elementData = new Object[initialCapacity]; this.capacityIncrement = capacityIncrement; } public Vector(int initialCapacity) { this(initialCapacity, 0); } public Vector() { this(10); }
熱いインライン展開と死んだコードの除去により、最終的にはあたかも元のコードが次のように書かれていたかのようになっています。素晴らしいですね。
public Vector() { this.elementData = new Object[10]; this.capacityIncrement = 0; }
しかし残念ながら素晴らしいのはここまでで、この後に続いているのは単なるVector.addの三連続呼び出しです。ロック関係の最適化は何もおこっていません。なんたる事。Vector.addが複雑過ぎてインライン展開できないのが原因でしょうか？次のコードを試してみましょう。
private static void foo() { Foo foo = new Foo(); foo.inc(); foo.inc(); foo.inc(); } private static final class Foo { int i=0; public synchronized void inc() { i++; } }
実行結果は次の様になります。
000 B1: # B6 B2 <- BLOCK HEAD IS JUNK Freq: 19972
000 # stack bang
pushq rbp
subq rsp, #80 # Create frame
00c # TLS is in R15
00c movq RBP, [R15 + #120 (8-bit)] # ptr
010 movq R10, RBP # spill
013 addq R10, #24 # ptr
017 cmpq R10, [R15 + #136 (32-bit)] # raw ptr
01e jge,u B6 P=0.000100 C=-1.000000
01e
024 B2: # B3 <- B1 Freq: 19970
024 movq [R15 + #120 (8-bit)], R10 # ptr
028 PREFETCHNTA [R10 + #256 (32-bit)] # Prefetch to non-temporal cache for write
030 movq R10, precise klass Main$Foo: 0x00002aaaf2646e58:Constant:exact * # ptr
03a movq R11, [R10 + #176 (32-bit)] # ptr
041 movq [RBP], R11 # ptr
045 movq [RBP + #8 (8-bit)], R10 # ptr
049 movq [RBP + #16 (8-bit)], #0 # long
049
051 B3: # B8 B4 <- B7 B2 Freq: 19972
051
051 # checkcastPP of RBP
051 leaq R11, [rsp + #64] # box lock
056 fastlock RBP,R11,RAX,R10
135 jne B8 P=0.000001 C=-1.000000
135
13b B4: # B9 B5 <- B8 B3 Freq: 19972
13b MEMBAR-acquire (prior CMPXCHG in FastLock so empty encoding)
13b movl R11, [RBP + #16 (8-bit)] # int ! Field Main$Foo.i
13f incl R11 # int
142 movl [RBP + #16 (8-bit)], R11 # int ! Field Main$Foo.i
146 MEMBAR-release
146 MEMBAR-acquire
146 movl R11, [RBP + #16 (8-bit)] # int ! Field Main$Foo.i
14a incl R11 # int
14d movl [RBP + #16 (8-bit)], R11 # int ! Field Main$Foo.i
151 MEMBAR-release
151 MEMBAR-acquire
151 movl R11, [RBP + #16 (8-bit)] # int ! Field Main$Foo.i
155 incl R11 # int
158 movl [RBP + #16 (8-bit)], R11 # int ! Field Main$Foo.i
15c MEMBAR-release (a FastUnlock follows so empty encoding)
15c leaq RAX, [rsp + #64] # box lock
161 fastunlock RBP, RAX, R10
218 jne,s B9 P=0.000001 C=-1.000000
218
21a B5: # N1 <- B9 B4 Freq: 19972
21a addq rsp, 80 # Destroy frame
popq rbp
testl rax, [rip + #offset_to_poll_page] # Safepoint: poll for GC
225 ret
（以下略）「fastlock」は明らかに疑似命令です。そんなCPU命令は聞いたことがないし、大体一つの命令が223バイトもコード領域を消費するわけがありません。実際にはここに定型のコードが挿入されているものと思われます。しかし、ここでは見事、ロックが粗粒度化されていて、一回のロックで３回のinc()呼び出しが起こっています。やった！！MEMBAR-acquire/releaseは命令長が0なので、メモリバリアを示す疑似命令でしょう。
しかし、ここでも残念ながらロックは依然として残っています。Fooがスタックから逃げ出さないことは明らかなので、ここではロックが完全に除去されるべきところなのですが...。ちょっと調べてみたところ、JDK6はescape analysisをほとんどやってないというブログが見付かりましたが、いっぽう、何か下らない間違いを僕がしている可能性も十分あります。
また、メモリバリアのなごりか、ロックが粗粒度化されたのにも関わらず、数字のインクリメントは一々メモリに書き戻されています。これは残念な事です。実際、ここで「synchronized」キーワードを除去すると次の結果が得られ、
000 B1: # B4 B2 <- BLOCK HEAD IS JUNK Freq: 27066
000 # stack bang
pushq rbp
subq rsp, #16 # Create frame
00c # TLS is in R15
00c movq RAX, [R15 + #120 (8-bit)] # ptr
010 movq R10, RAX # spill
013 addq R10, #24 # ptr
017 cmpq R10, [R15 + #136 (32-bit)] # raw ptr
01e jge,us B4 P=0.000100 C=-1.000000
01e
020 B2: # B3 <- B1 Freq: 27063.3
020 movq [R15 + #120 (8-bit)], R10 # ptr
024 PREFETCHNTA [R10 + #256 (32-bit)] # Prefetch to non-temporal cache for write
02c movq R10, precise klass Main$Foo: 0x00002aaaf25dfbc8:Constant:exact * # ptr
036 movq R11, [R10 + #176 (32-bit)] # ptr
03d movq [RAX], R11 # ptr
040 movq [RAX + #8 (8-bit)], R10 # ptr
040
044 B3: # N1 <- B5 B2 Freq: 27066
044 movq [RAX + #16 (8-bit)], #3 # long
04c
04c addq rsp, 16 # Destroy frame
popq rbp
testl rax, [rip + #offset_to_poll_page] # Safepoint: poll for GC
057 ret
（以下略）3回のインクリメントと初期化が全部まとめられて単なるmovq rax[16],3という風に素晴らしく最適化されます。さすが。
随分長くなりましたが、現代のJVMはどうでしょうか？なかなかいい線を行っていると思いますが、どうでしょうか。バイトコードの逐次変換のような単純な処理とは一線を画しているのが見て取れますね。一方、エスケープ解析を利用した高度な最適化はまだ全然行われていないようです。もったいないですね。
たまには皆さんも深追いしてJITと戯れてみましょう。面白いですよ。
