原文はこちら。
The original article was written by Cesar Soares (Senior Software Engineer, Microsoft).
https://devblogs.microsoft.com/java/how-tiered-compilation-works-in-openjdk/

OpenJDK HotSpotのランタイムシステムは、Javaプログラムの実行を実行中に最適化するための技術を採用した複雑なソフトウェアです。このシステムは、2つの異なるコンパイラー、ひとつのインタープリタ、そしていくつかの異なるガベージコレクタ、その他のコンポーネントで構成されています。これらのコンパイラは、各メソッドに最適なコンパイラを使用しようとする階層コンパイルメカニズムで編成されています。

HotSpotは、ランタイムコストを最小限に抑えながら効率的なマシンコードを生成するという重要な目標を掲げています。これを実現するために、階層化コンパイル、動的プロファイリング、推論（Speculation）、最適化解除（deoptimization）、アーキテクチャ依存・非依存のさまざまなコンパイラ最適化など、さまざまな戦略を採用しています。このエントリでは、階層化コンパイルの背後にある動機を掘り下げ、それがどのように機能するかを理解していきます。

The Right Tool for The Job 

階層化コンパイルの基本的な考え方は、

• プログラムの実行時間の大半はコードのごく一部（つまり少数のメソッド）に費やされる
• メソッドのコンパイルにかかるコスト（CPUサイクル）は、メソッドが1回しか実行されなくても100万回実行されても同じ

というものです。こうした観察結果に基づき、VMは、「何度も」実行されないメソッド、すなわちコールドメソッドには 「シンプルなコンパイラ」を使用し、「たくさん」実行されるメソッド、すなわちホット・メソッドにはより「最適化」されたコンパイラを使用するように設計されています。その根拠は以下の通りです。

1. 一度しか実行されないメソッドのコンパイルに多くのCPUサイクルを費やしたくない、つまるところ、メソッド実行よりもコンパイルに多くのCPUサイクルを費やしたくないのです
2. メソッドの実行回数が十分に多ければ、最適化された形でコンパイルするコストとそのメソッドを実行するコストは、最適化されていない形でメソッドを実行するコストよりも低くなります。

上記の点を例証するために、いくつかの仮想的な値を使ってみましょう。3つの異なるコンパイラ（Comp1、Comp2、Comp3）を持つVMを考えます。これらのコンパイラーはそれぞれ、前のコンパイラーよりもコードを生成するのが遅いのですが、実際に生成されるコードは前のコンパイラーが生成したコードよりも優れています。Comp1は高速でシンプルなコンパイラで、「遅いコード」を生成します。Comp2はComp1より遅いが、わずかに「速いコード」を生成します。Comp3は非常に効率的なコードを生成するコンパイラですが、Comp1やComp2よりはるかに遅い、つまり時間がかかります。

これらの説明に基づき、下表のような値がランダム・メソッドのコンパイルについて適用されるものとします。Compilationの列は、メソッドをコンパイルするためのCPUサイクル数で、コストを示しています。Cycle Countの列は、メソッドに生成されたコードが実行されるのにかかるサイクル数を示しています。

これらの値が意味するのは、Comp1 は Comp3 よりも 100 倍速くメソッドをコンパイルできるが、生成されたコードは 5 倍遅く実行される、ということです。下の表は、異なる4シナリオにおいて、メソッドのコンパイルと実行に必要なCPUサイクルの総数を示しています。

シナリオAでComp1を使った場合、メソッドのコンパイルと実行の合計サイクル数は51（コンパイル1回＋1回実行50回）です。同じシナリオでComp2を使用した場合、合計サイクル数は40（メソッドのコンパイルに10サイクル、1回の実行に30サイクル）です。一方Comp3を使用した場合、総サイクル数は110（コンパイルに100サイクル＋1回実行に10サイクル）です。したがって、メソッドが一度しか実行されない場合における最適なコンパイラはComp2といえます。

シナリオDでは、Comp1を使用した場合、総サイクル数は50,000,001（メソッドのコンパイルに1、実行に50,000,000）ですが、このシナリオでComp3を使えば、総サイクル数は10,000,100（メソッドのコンパイルに100サイクル、実行に1,000,000回）になります。

おわかりのように、使用するコンパイラやメソッドの実行回数によって、この数字はかなり違います。言い換えれば、メソッドをコンパイルするのに最適なコンパイラは、メソッドの実行回数に依存するということです。次章では、メソッドの実行回数を “予測”（推測）する方法を見ていきます。

Hot Code Prediction 

前章では、「たくさんの」「単純な」などの言葉を意図的に使いました。この章では、それぞれ何を意味しているのかを正確に説明します。

「単純な」コンパイラとは、コードを素早く生成できる（つまりコンパイルコストが大きくない）が、生成されるマシンコードが可能な限り最も効率的であることを厳しく要求されないものを意味します。一方、洗練されたコンパイラ（最適化コンパイラと呼ばれることもあります）とは、可能な限り最も効率的なマシンコードを生成することを目指し、多くの最適化を行うコンパイラのことです。ご想像の通り、コンパイルコストは2つのコンパイラで異なります。また、両極端な2つのコンパイラだけで解決する必要はなく、能力の異なるさまざまなコンパイラを採用することもできますし、同じコンパイラを使いながら、（最適化のレベルが異なるGCCやClangのように）コードの部分ごとに異なる最適化のリストを実行することもできます。

前章で、メソッドの実行回数が、どのコンパイラを使うかを決める重要な要素であることを理解しました。今回の例では、メソッドをコンパイルする前に、そのメソッドが何回実行されるかを知っているという前提がありました。

では、メソッドをコンパイルする前に、そのメソッドが 「何回も」実行されるかどうかをどうやって判断するのでしょうか？「何回も」とはどういうことでしょう？まぁ、答えは判断「できない」です。解決しようとしている問題は、計算機科学の重要な、そして決定不可能な問題である停止性問題（Halting Problem）の一種です。

Halting problem
https://en.wikipedia.org/wiki/Halting_problem
https://ja.wikipedia.org/wiki/停止性問題

実際に行うのは、この問題の回避策を見つけることです。メソッドがコールドメソッドで、シンプルなコンパイラでコンパイルし、メソッドを数回実行します。例えばN回実行するものとしましょう。メソッドがN回実行されたら、将来少なくともN回以上実行されると仮定します。したがってそのメソッドはホットメソッドです。もしそのメソッドがN回も実行されなければ、そのメソッドはコールドメソッドであり、すでにそのメソッドに適切なコンパイラ（シンプルなコンパイラ）を使っていると言えます。言い換えれば、あるメソッドがいつホットな状態になったかを見つけるのにしきい値Nを使い、そのメソッドが将来もホットであり続けることを示す指標として使うのです。

問題は、しきい値Nの値をどのように選ぶかです。もしN = 1にすれば、我々の仮定（メソッドがN回以上実行される）がほとんどの時間成立する可能性が高くなるものの、ホットメソッドを見つけるのにはあまり役に立ちません。N = 1,000,000にすると、本当にホットなメソッドを見つける可能性は上がるが、われわれの仮定（メソッドがあとN回実行される）が偽になる確率も上がります。さらに、シンプルなコンパイラでコンパイルしたメソッドを1,000,000回実行してしまいます。

実際には、経験的証拠に基づいてNを選択します。コンパイルのコスト、コンパイラが生成するコードの性能、ワークロードの種類、コンパイラの数などを考慮し、しきい値について経験則に基づいた推測を試みるのです。すべての状況に対応できる理想的なしきい値はほとんどありません。例えば、GUIプログラムのように実行がソースコード全体に広がるプログラムもあれば、科学プログラムやベンチマークなどのように実行がソースコードのごく一部に限定されるプログラムもあります。プログラムの挙動によっては、コードの異なる部分が異なる瞬間にホットな状態になるように、いくつかのフェーズを遷移する場合もあります。

次章では、HotSpotがこの問題にどのように対処するかを簡単に見ていきます。 

Tiered Compilation in HotSpot 

これからご紹介するHotSpotのTiered Compilationプロセスは非常に手の込んだものですが、考え方は前のセクションで説明したものと同じで、「その仕事に対して最善のツールを使う」という考え方に基づいています。

HotSpotには2つのコンパイラ、C1とC2、そしてインタープリタがあります。

C1 Compiler
https://github.com/openjdk/jdk/blob/c8add223a10030e40ccef42e081fd0d8f00e0593/src/hotspot/share/c1/c1_Compilation.cpp#L429
C2 Compiler
https://github.com/openjdk/jdk/blob/c8add223a10030e40ccef42e081fd0d8f00e0593/src/hotspot/share/opto/c2compiler.cpp#L97

各コンパイラを実行するスレッドは複数存在する可能性があり、その数はシステムの負荷に応じて動的に調整されます。つまり、複数のメソッドが同時にコンパイルされる可能性がある、ということです。さらに、あるメソッドの実行は、そのメソッドの別のバージョンがコンパイルされている間、現在の形で中断されることなく続けられる可能性があります。コンパイラスレッドは、コンパイラごとに1つずつ、特にどのメソッドをコンパイルすべきかを記述したCompilation Taskを含む2つの優先順位キューで動作します。

Compilation Task
https://github.com/JohnTortugo/jdk/blob/8eed7dea7b92dd98b74277e8521100f7f807eabb/src/hotspot/share/compiler/compileTask.hpp#L43

異なる構成の2個のコンパイラがインタープリタと組み合わさって、合計5段階の最適化レベルができあがります。

通常、メソッドの実行はインタープリタで始まります。これはHotSpotがコードを実行するための最もシンプルで安価なメカニズムです。インタープリタ、またはコンパイルされた形式でメソッドを実行する間に、インスツルメンテーションを使用してメソッドの動的プロファイルを収集します。メソッドのプロファイルを使用して、メソッドをコンパイルするか、別のレベルで再コンパイルするか、どの最適化を実行するかなどをヒューリスティックが決定します。

メソッドの実行中にHotSpotが収集する最も基本的な情報は、メソッドの実行回数とメソッド内のループの反復回数です。この情報はCompilation Policyが使用し、メソッドをコンパイルするかどうか、どのレベルでコンパイルするかを決定します。

Compilation Policy
https://github.com/JohnTortugo/jdk/blob/8eed7dea7b92dd98b74277e8521100f7f807eabb/src/hotspot/share/compiler/compilationPolicy.hpp#L36

また、HotSpotにはOn-Stack-Replacement（OSR）と呼ばれる、ホットループを含むメソッドとは独立してコンパイルできる機能があります。これは、ホットループがそれ自身がホットになっていないメソッド内にあるケースを回避するための興味深い機能です。

Compilation Policyは以下の式を使って、現在インタープリタで動作しているメソッドに対してレベル3でコンパイルリクエストを作成するかどうかを決定します。

apply_scaled
https://github.com/JohnTortugo/jdk/blob/8eed7dea7b92dd98b74277e8521100f7f807eabb/src/hotspot/share/compiler/compilationPolicy.cpp#L268
i > TierXInvocationThreshold * s || (i > TierXMinInvocationThreshold * s && i + b > TierXCompileThreshold * s)
https://github.com/JohnTortugo/jdk/blob/8eed7dea7b92dd98b74277e8521100f7f807eabb/src/hotspot/share/compiler/compilationPolicy.hpp#L105

メソッドが現在レベル3のコンパイルとして実行されている場合において、レベル4でメソッドをコンパイルするリクエストを作成すべきかどうかを決定する際にも、同じ式を使っています。同様の式はOSRコンパイルの制御にも使われます。

(Executions > TierXInvocationThreshold * Scale)

または  

(Executions > TierXMinInvocationThreshold * Scale かつ Executions + Iterations > TierXCompileThreshold * Scale) 

ここで、 

HotSpotは、システムの他の部分におけるコンパイルの影響や、システムが現在処理している負荷の大きさも考慮します。 メソッドがインタープリタで動作していて、レベル3でコンパイルするための上記の式が満たされていると仮定すると、コンパイルポリシーは実際にはレベル3（完全なプロファイリングを行うC1）ではなく、レベル2（基本的なプロファイリングを行うC1）でコンパイルすることを決定する可能性があります。これは以下の要因に基づいて判断されます。

レベル3でコンパイルされたメソッドが十分な回数実行され、レベル4への移行条件式を満たすと、そのレベルでメソッドを再コンパイルするリクエストが作成されます。このレベルでは、HotSpotはC2コンパイラを使用してコードをコンパイルし、長期的なパフォーマンスを最大化します。レベル4のコードは完全に最適化されていると考えられるため、JVMはプロファイリング情報の収集を停止します。

C1がメソッドを最初にコンパイルすると、命令数やループ数など、メソッドの構造に関する基本的な情報を収集します。その情報に基づいて、メソッドが（定数を返す、getterやsetterといった）普通のメソッドと判断されます。

is_constant_getter
https://github.com/openjdk/jdk/blob/8eed7dea7b92dd98b74277e8521100f7f807eabb/src/hotspot/share/oops/method.cpp#L883

結果、C1でコンパイルしても同じコードが得られます。この場合、メソッドは常にレベル1でコンパイルされます。

上記の説明はCompilation Policyの簡略版です。HotSpotがメソッドのコンパイルや再コンパイルを決定する際に考慮する点は他にもいくつかあり、JVMのユーザーがポリシーをカスタマイズするために使用できるフラグもいくつかあります。ここでの議論では、おそらくDeoptimizationが最も関連性の高いトピックです。

C2は、メソッドの動的プロファイルに関する情報を使用して、いくつかの最適化を導きます。いくつか例を挙げましょう： インライン化(Inlining)、クラス階層解析（Class Hierarchy Analysis / CHA）、基本的なブロック順序、ループ最適化などです。

しかし、次のような問題があります。メソッドの動的プロファイルは、言っても動的です。アプリケーションの実行中、メソッドのプロファイルが安定しているという保証はありません。いくつか例を挙げましょう。

• if-else “文で使用されている条件が、プログラムの実行中はほとんどtrueだったのに、突然falseを返すようになる。
• トリガーされたことのない例外がトリガーされ始める。
• nullではなかった参照変数がnullとして表示され始める。
• 新しいクラスがシステムにロードされ、以前は単純だったクラス階層がより複雑になる。
• 通常は何千回も反復するループが、わずか数回反復するだけになってしまう。

このような動的な挙動を考慮するため、C2はコンパイル済みコードにpredicateを挿入し、プロファイル情報に基づいて行った仮定が将来の実行でも有効かどうかをチェックします。predicateがfalseの場合、Trap（JVM内部への呼び出し）が実行され、どの仮定がfalseであったかをHotSpotに通知します。Trapが提供した情報をもとに、HotSpotは何をすべきかを決定します。メソッドの現在のコンパイルを破棄し、メソッドを再コンパイルする必要があるかもしれませんし、インタープリターに実行を切り替える必要があるかもしれません。Trapが実行される可能性のある理由のリスト（What condition caused the deoptimization?）と、必要なアクションのリスト（What action must be taken by the runtime?）を以下に示します。

What condition caused the deoptimization?
https://github.com/openjdk/jdk/blob/8eed7dea7b92dd98b74277e8521100f7f807eabb/src/hotspot/share/runtime/deoptimization.hpp#L76
What action must be taken by the runtime?
https://github.com/openjdk/jdk/blob/8eed7dea7b92dd98b74277e8521100f7f807eabb/src/hotspot/share/runtime/deoptimization.hpp#L144

次章では、HotSpotが生成したコンパイルリストを調べる方法を見てみましょう。

Controlling Compilation 

この章では、HotSpotでコンパイルを制御するために使用されるいくつかの基本的なフラグについて説明します。最初に言っておきますが、これらのフラグはアプリケーションのパフォーマンスを「調整」するためのものではありません。バグの根本原因を調査するためのものです。

 -Xcompと-Xintオプションは、JVMにメソッドをコンパイルする（-Xcomp）か、インタープリタで動作する（-Xint）かどちらかを指示します。言い換えると、JVMに-Xintを渡すと、すべてのJITコンパイラが無効になり、HotSpotがプログラムを実行するために使用する唯一のメカニズムはインタープリタになります。一方、-Xcompを渡すと、HotSpotはインタープリタを使用せず、メソッドは常にコンパイルされます。

ただし、-Xcompオプションは、HotSpotが特定の最適化レベルでメソッドをコンパイルすることを強制するものではありません。そのために他のオプションを使用することができ、その中に-XX:TieredStopAtLevelと-XX:-TieredCompilationがあります。前者はコンパイルレベルの上限を設定するものです。最も一般的な使用例は、C2のバグを回避するため、またはC1のストレステストを行うために、HotSpotにC1コンパイラのみを使用させる、といった具合です。後者は、HotSpotがTiered Compilation（階層コンパイル）ヒューリスティックを使用してコンパイル間の移行を誘導せず、代わりに別のヒューリスティックを使用してすべてのコンパイルでC1とC2のどちらかを選択するようにする、というものです。

階層コンパイルがプログラムの実行時間に与える影響を説明するために、先ほど見たオプションを使って簡単な実験をしてみましょう。これは包括的な実験ではなく、これらの異なるコンパイル戦略がJVMとアプリケーションのパフォーマンスに与える影響のアイデアを与えることだけを目的としています。

下表は、Ubuntu 20.04が動作するAMD Ryzen 7 1800Xマシンで

java-17.07 [FLAGS] HelloWorld

を実行するのにかかる平均wall timeを示しています。このHelloWorldプログラムは、コンソールに「Hello World」メッセージを表示するだけです。

これらの結果から、この例では、インタープリタを無効にする（つまり-Xcomp）と、デフォルトのJVMオプションと比較して実行時間が大幅に増加することがわかります。その理由は、上で説明したように、多くのメソッドがコンパイル・コストを償却するほど実行されないからです。一方、この例では、インタープリタだけを使うようにJVMを設定すると、パフォーマンスはまったくカスタマイズしないときと同じになります。これは、この例においては長く実行されるメソッドがないため、インタープリターがとにかく最良の選択だからです。

Conclusion 

階層コンパイルは、プログラムの実行をより効率的にするために多くの仮想マシンで使われているテクニックです。その核となる考え方は、メソッドのコンパイル・コストとコンパイル後のコードのパフォーマンスとの間のスイート・スポットを見つけることです。これを実現するために、VMは頻繁に実行されるメソッドにのみ最適化コンパイラを使用し、あまり実行されないメソッドには非最適化コンパイラー（またはインタープリタ）を使用します。言い換えれば、VMはコンパイル済みコードとインタプリタ済みコードを組み合わせてクライアント・プログラムを実行する、ということです。

OpenJDKのJVMは、2つのJITコンパイラと1つのインタープリタを採用し、洗練された形式の階層化コンパイルを実装しています。JVMは最初にインタプリタを使ってメソッドを実行し、メソッドの実行回数がヒューリスティックを満たすと、そのメソッドはC1コンパイラを使ったコンパイルのためにキューに入れられます。メソッドの実行カウントが十分に大きければ、別の条件を満たし、そのメソッドはC2最適化コンパイラーを使ってコンパイルされます。インタープリタ版とC1コンパイル版のメソッドから収集されたプロファイリング情報を使い、C2は多くの最適化を推進します。

プログラムのほとんどのメソッドは数回しか実行されない一方で、何百万回も実行されるメソッドもあります。プログラムには、実行時間の90％は10％のメソッドしか実行しないという非公式の格言があります。プログラムの実行に重要でないメソッドのコンパイルにCPUの時間を費やすことは、不必要なオーバーヘッドを生むことになります。階層コンパイルは、エンジニアリングとヒューリスティックを組み合わせた実用的なアプローチであり、メソッドが頻繁に実行されるかどうかをVMが推測し、その情報を使ってメソッドをインタープリタで実行すべきかコンパイルすべきかを決定します。一例として、コンパイルだけで “Hello World “Javaプログラムを実行すると、インタープリタだけで実行するよりも実行時間が40倍長くなります。

• Java
• Technology