今まで
Understanding How Graal Works - a Java JIT Compiler Written in Java
に沿ってGraalの理解を深めていたのですが、記事の最後に"Some practicalities that I haven’t talked about"として2つ挙げられています。
- Register allocation
- Scheduling
これから一人で学びを進めていきます。まず"Register allocation"を学ぶことにしました。しかし"GraalのRegister allocation"の前にそもそも"Register allocation"がわかりません。記事にはこうありました。
Graal uses similar register allocation algorithms to other JIT-compilers (it’s the linear scan algorithm).
Graalでは"linear scan"アルゴリズムを"register allocation: レジスタ割り付け"に使っているようです。"linear scan"で検索すると、論文が見つかりました。
http://www.christianwimmer.at/Publications/Wimmer04a/Wimmer04a.pdf
"Linear Scan Register Allocation for the Java HotSpot™ Client Compiler"というタイトルで、少し読んでみたところ非常にわかりやすいので、今そのまま読み進めています。2004年と新しくはない論文ですが（32ビットだったりJDK 1.4だったり）、修士論文のようで基本的な用語もすべて説明があります。英語ですが通常の技術文書と変わりありません。
Christian Wimmerさん
論文を読み進めてふと著者を見ると、Christian Wimmerさんとありました。何か見覚えがある気がして、JVM Language Summitのアジェンダ*1を見返すと、"Wimmer: Truffle & Graal"と…念のためYouTubeのJVMLSのセッション動画を確認すると、"Polyglot Native: Java, Scala, Kotlin, and JVM languages with Christian Wimmer"！つまり、この方はGraalに関わっていて、そのregister allocationのアルゴリズムをHotSpotに適用する論文もこの方が書いているわけです。僕は今この方の13年前いた場所の、さらに入り口に立っているに過ぎないと知り、改めて自分の浅さを突きつけられた感じがします。
レジスタ割り付け
JITコンパイルではJavaバイトコードをマシンコードに変換する以上、各マシンコードが使用するレジスタを割り付けなければなりません。AMD64では汎用レジスタが16本あります。IA-32時代の8本 （EAX、EBX、ECX、EDX、ESI、EDI、EBP、ESP）とR8〜R15の8本を加えた16本です。このうち、EBP（ベースポインタ）とESP（スタックポインタ）は用途が決まっています。
レジスタ割り付けでは古くは"graph coloring: グラフ彩色"アルゴリズムがあります。マシンコードが使うレジスタをすべて仮想レジスタに割り付け、利用期間を考慮しつつ数に限りがある実レジスタに割り付けます。実レジスタに割り付けられずあふれたものは、メモリ上に保持することになり、したがってパフォーマンスに影響します。
たとえば、今マシンコードで仮想レジスタv1からv5の5つを使っているとします。
http://www.christianwimmer.at/Publications/Wimmer04a/Wimmer04a.pdf P.7 Figure 2.1
実レジスタが2つとすると、この5つの仮想レジスタ利用を、利用期間に合わせてうまく2つでやりくりするということです。
http://www.christianwimmer.at/Publications/Wimmer04a/Wimmer04a.pdf P.10 Figure 2.5
同時に、グラフ彩色アルゴリズムではすべてを俯瞰してからレジスタ割り付けをするため、処理が遅いです。通常のコンパイルではなくJITコンパイルでは、処理時間はアプリケーションのパフォーマンスに直接影響するため、グラフ彩色アルゴリズムではなくlinear scanアルゴリズムが採用されています。
JITコンパイルでは、マシンコードへのコンパイル時間と、コンパイルしたマシンコードそのものの実行パフォーマンスとの間にトレードオフがあるということになります。
linear scanアルゴリズムでは、上記のv1にあるような途中にある間（hole）を考慮しません。holeの部分もレジスタを利用しているものとして扱い、アルゴリズムを簡略化して処理時間を短縮します。そうすると、メモリにあふれるケースが増えてしまいます。そのためlinear scanアルゴリズムの改良として"Second-Chance Bin Packing"があります。
Graalでのlinear scan
org.graalvm.compiler.lir.alloc.lsra.LinearScanPhaseクラスがあります。
public final class LinearScanPhase extends AllocationPhase { ... @Override protected void run(TargetDescription target, LIRGenerationResult lirGenRes, AllocationContext context) { ... final LinearScan allocator = new SSALinearScan(target, lirGenRes, spillMoveFactory, registerAllocationConfig, lirGenRes.getLIR().linearScanOrder(), neverSpillConstants); allocator.allocate(target, lirGenRes, context); }
org.graalvm.compiler.lir.alloc.lsra.ssa.SSALinearScanクラスが実際の処理です。このSSAはstatic single assignment (SSA: 静的単一代入) です。
public final class SSALinearScan extends LinearScan {
ほとんどの処理はスーパークラスのorg.graalvm.compiler.lir.alloc.lsra.LinearScanクラスです。そこからorg.graalvm.compiler.lir.alloc.lsra.LinearScanRegisterAllocationPhaseクラスの処理を呼び出します。
public final class LinearScanRegisterAllocationPhase extends LinearScanAllocationPhase { private final LinearScan allocator; ... @SuppressWarnings("try") void allocateRegisters() { try (Indent indent = allocator.getDebug().logAndIndent("allocate registers")) { Interval precoloredIntervals; Interval notPrecoloredIntervals; Pair<Interval, Interval> result = allocator.createUnhandledLists(LinearScan.IS_PRECOLORED_INTERVAL, LinearScan.IS_VARIABLE_INTERVAL); precoloredIntervals = result.getLeft(); notPrecoloredIntervals = result.getRight(); // allocate cpu registers LinearScanWalker lsw; if (OptimizingLinearScanWalker.Options.LSRAOptimization.getValue(allocator.getOptions())) { lsw = new OptimizingLinearScanWalker(allocator, precoloredIntervals, notPrecoloredIntervals); } else { lsw = new LinearScanWalker(allocator, precoloredIntervals, notPrecoloredIntervals); } lsw.walk(); lsw.finishAllocation(); } }
実際のレジスタ割り付けはorg.graalvm.compiler.lir.alloc.lsra.IntervalWalker#walk()です。ですが、読んでも理解できていません…
