A friendlier visualization of Java’s JIT compiler based on control flow

原文はこちら。
The original article was written by Roberto Castañeda Lozano (Senior Member Of Technical Staff at Oracle).
https://robcasloz.github.io/blog/2022/05/24/a-friendlier-visualization-of-javas-jit-compiler-based-on-control-flow.html

前回の記事では、OpenJDKの主要なジャストインタイムコンパイラの内部構造を可視化するツールであるIGV (Ideal Graph Visualizer) を紹介しました。今回の記事は、OpenJDK 19でリリースされる予定のIGVの新機能に焦点を当て、コンパイラの専門家がコンパイラの保守と拡張を容易にし、上級Javaユーザーがコンパイラを把握できるようにすることを目的としています。

Improving the Ideal Graph Visualizer for better comprehension of Java’s main JIT compiler
https://robcasloz.github.io/blog/2021/04/22/improving-the-ideal-graph-visualizer.html
https://logico-jp.io/2021/05/13/improving-the-ideal-graph-visualizer-for-better-comprehension-of-javas-main-jit-compiler/
Ideal Graph Visualizer
https://github.com/openjdk/jdk/tree/master/src/utils/IdealGraphVisualizer

The rough sea of nodes

OpenJDKのメインJITコンパイラであるC2は、コンパイル対象のプログラムをプログラム依存性グラフ (PDG) を用いて表現します。

Proceedings of the Java™ Virtual Machine Research and Technology Symposium (JVM ’01)
https://www.usenix.org/legacy/events/jvm01/full_papers/paleczny/paleczny.pdf
The program dependence graph and its use in optimization
https://dl.acm.org/doi/10.1145/24039.24041

PDGでは、ノードがオペレーションに対応し、エッジがオペレーション間の依存関係に対応します。PDGの特徴は、データと制御を一体化していることです。ノードは通常の算術・論理演算だけでなく、条件付きジャンプやループなどの制御演算にも対応しています。C2で使われているPDGは、「sea-of-nodes」と呼ばれることが多くあります。

A simple graph-based intermediate representation
https://dl.acm.org/doi/10.1145/202530.202534

以下の例は、2つのexitを持つ単純なループのPDGです。

PDG of a simple loop with two exits
PDG of a simple loop with two exits

Sea-of-Nodesの表現が持つ統一的な性質により、多くの最適化の実装が容易になりますが、比較的小さなプログラムに対応するグラフでさえ、すぐに把握が困難な「ノードの海」になってしまうという大きな欠点があります。OpenJDKのVMの主要な設計者の一人であるJohn Rose氏の言葉を借りれば以下のようです。

Engineers (…) find it easy to read sequential presentations of CFG basic blocks, but usually cannot read PDG graphs directly without assistance; this affects debugging speed.
エンジニアは(中略)通常、支援なしにPDGグラフを直接読むことができない。これはデバッグのスピードに影響する。

Thinking About Intermediate Representations
http://cr.openjdk.java.net/~jrose/draft/code-media.html

From program dependence graphs to control-flow graphs

コンパイラで最もよく使われるプログラム表現は、おそらく古き良き制御フローグラフ(CFG)でしょう。CFGでは、ノードは基本ブロック(常に一緒に実行される操作のシーケンス)に対応し、エッジは基本ブロック間の制御ジャンプに対応します。PDGとは異なり、CFGは各操作に基本ブロックを明示的に割り当て、各基本ブロック内の操作を順序付けます。このため、コンパイラによる最適化が複雑になりますが、構造化された逐次的なプログラムビューが得られるので理解やデバッグが容易です。さらに、CFGは多くのシステムエンジニアにとって馴染みのある抽象概念ですが、PDGは上級コンパイラコースでもよくわからないトピックのままです。

様々な組織の多くのC2エンジニアから集められたフィードバックと、John Roseの以下の呼びかけに触発され、C2のPDGベースのプログラム表現をCFGとして提示する新しいIGVビューを開発しました。

Even in a PDG, debugging presentations can easily include trial schedules to be competitive with CFG presentations.
PDGであっても、デバッグのプレゼンテーションには、CFGのプレゼンテーションに負けないような試行スケジュールを簡単に含めることができる

Thinking About Intermediate Representations
http://cr.openjdk.java.net/~jrose/draft/code-media.html

8282547: IGV: add control-flow graph view #7817
https://github.com/openjdk/jdk/pull/7817

新しいIGVビューは、基本ブロックへの操作の割り当て(グローバルスケジュール)と各基本ブロック内の操作の順序(ローカルスケジュール)を含む独自の試行スケジュール(trial schedule)を計算します。C2の最後のコンパイルフェーズで利用可能になった時点で、試行スケジュールをC2の実際のスケジュールに置き換えます。これが古典的なPDGビューと単純な方法の新しいCFGビューです。

PDG and CFG of a tiny Java method
PDG (left) and CFG (right) of a tiny Java method

Trying it out

もっと探求したい場合は、上記の例を使って新しいビューを試すことができます。以下の手順を踏んでください。

1. OpenJDKのソースコードをダウンロードします(IGVのビルドはJDKと一緒に配布されていません)。

$ wget https://github.com/openjdk/jdk/archive/refs/heads/master.zip
$ unzip master.zip

2. Mavenを使い、IGVをビルドします。

$ cd jdk-master/src/utils/IdealGraphVisualizer
$ mvn install

3. IGVを実行します。

$ sh igv.sh

4. このIGVグラフファイルを開きます。ご自身のグラフファイル (foo.xml) を生成するには、オプション -XX:PrintIdealGraphLevel=3 -XX:PrintIdealGraphFile=foo.xml を使って仮想マシンのデバッグビルドを実行してください。詳細は以下をご覧ください。

Ideal Graph Visualizer : Usage
https://github.com/openjdk/jdk/blob/master/src/utils/IdealGraphVisualizer/README.md#usage

5. Outlineウィンドウで、example graphsというグラフグループを展開し、グラフ (graph) をダブルクリックします。デフォルトでは、PDGビューが表示されます。

6. 以下のツールバーボタンをクリックして、CFGビューに切り替えます。

IGV のソースコードのコピーを手にされましたので、このツールを改善するために提案されている複数の「スターター」タスクがあることを思い出していただけますと幸いです。

labels = c2-igv AND labels = starter AND (status = open OR status = new) AND assignee = null
https://bugs.openjdk.java.net/browse/JDK-8287094?jql=labels%20%3D%20c2-igv%20AND%20labels%20%3D%20starter%20AND%20(status%20%3D%20open%20OR%20status%20%3D%20new)%20AND%20assignee%20%3D%20null

コントリビューションをお待ちしております。IGVのハックは、C2がどのように動作するかを学び、OpenJDKプロジェクト一般に手を入れるためのフレンドリーな方法です。

Possible extensions

CFGはコンパイラの可視化における最後の言葉なのでしょうか?そうではありません。IGVを拡張して、コンパイラの開発者にとってより便利なものにする方法はたくさんあります。ここでは、いくつかのアイデアを紹介します。

プログラム領域の可視化(Visualizing program regions)

プログラムには、素の基本ブロックよりも多くの構造があります。IGVは、基本ブロックを(ネストされた)ループやif-then-else構造などにクラスタリングすることで、トップダウンの探索を向上させることができる可能性があります。

実行頻度の見積もり(Estimating execution frequencies

基本ブロックの実行頻度は、「重要」なプログラム領域(最も頻繁に実行される基本ブロック)を素早く特定するための非常に強力な視覚的な補助になり得ます。現在IGVは、入力の一部として情報が提供された場合にのみ、実行頻度によってブロックを着色しますが、スケジューリング情報に対して行われるのと同様に、分析自体を実行するように拡張できる可能性があります。

CFG colored by execution frequency (cold blocks in blue, hot blocks in red)
CFG colored by execution frequency (cold blocks in blue, hot blocks in red)

CFGベース・コンパイラの可視化(Visualizing CFG-based compilers)

これまでIGVはPDG表現を用いたコンパイラに限定されていましたが、この新しいビューのおかげで、CFGベースのコンパイラ(例えばOpenJDKの軽量JITコンパイラであるC1など)もその恩恵を受けることができるようになりました。

Other improvements in JDK 19

新しいCFGビューの導入に加え、IGVはJDK 17にアップグレードされ、これまで以上に高速化されました(スケジューリングとグラフの表示で平均15倍と2.4倍のスピードアップを実現しました)。

8279068: IGV: Update to work with JDK 16 and 17 #7347
https://github.com/openjdk/jdk/pull/7347
8282043: IGV: speed up schedule approximation #8037
https://github.com/openjdk/jdk/pull/8037
8283684: IGV: speed up filter application #8073
https://github.com/openjdk/jdk/pull/8073

もし、フィードバック、質問、または上記のアイデアについて議論したいことがあれば、是非お知らせください

謝辞

この記事の早期バージョンに対してフィードバックをくださった、Jesper WilhelmssonとVladimir Kozlovに感謝します。

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト /  変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト /  変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト /  変更 )

%s と連携中