原文はこちら。
The original article was written by Chris Seaton (Researcher and Senior Staff Engineer at Shopify).
https://chrisseaton.com/truffleruby/basic-graal-graphs
【訳注】原文では、Graalという表現をGraalVM JITコンパイラの意味で使っていたり、GraalVMの意味で使っています。原文の意図に合わせて、GraalVM JITコンパイラを表現するGraalはGraalVM JITコンパイラ、GraalVMを表現するGraalはGraalVMとして記載しています。
GraalVM JITコンパイラはJVMのための新しいJITコンパイラで、Javaプログラムを実行中にマシン語に変換します。Truffle という言語実装フレームワークを使って、Java上で他言語を実行するためにGraalVMを利用できます。Shopifyでは、TruffleRubyを使ってRubyをJITコンパイルしてネイティブコードにするためにGraalVM JITコンパイラを使っていますが、この記事ではできるだけ簡単にするためにJavaについてのみ取り扱います。
Javaを使う場合、javacコンパイラを使ってアプリケーションをバイトコードと呼ばれるデータ構造にコンパイルすることはご存知の方が多いでしょうし、コンパイル中にJavaコンパイラがJavaソースコードを表現する際に用いる、AST（Abstract syntax tree、抽象構文木）データ構造もご存知のことでしょう。
実行時にJavaプログラムをネイティブコードにJITコンパイルするために使われる、別の重要なデータ構造のコンパイラ中間表現、つまりIRのことは認識してらっしゃる方はあまりいらっしゃらないようです。コンパイラはこのデータ構造を操作することでコードを変換して最適化するため、IRを見れば、コンパイラがやっていることに関する多くの情報を得ることができますが、このためには特別なツール、例えば、Oracle LabsのIdeal Graph Visualizer（IGV）や、この記事で利用しているShopifyの内部ツールであるSeafoamなどを使用する必要があります。
GraalのIR が特に興味深いのは、循環グラフだからです。これはつまり、これは、エッジをたどると円を描くことができる、ということです。ソースコードのほとんどのIRは、循環グラフではなく、ある種の木の形をしています。そのため、多くの人にとっては、IRは自分のコードを見たり、考えたりするための新しい方法でしょう。また、筆者は本当にIRを見るのも、IRを扱うのも好きで、芸術的だな、と思っています。
この記事では、Javaの基本的な言語構成のGraalグラフを紹介しながら、グラフの各部分の意味と、Javaがどのようにコンパイルされ最適化されているかを理解するために、ここから何を学ぶことができるのかを説明します。
少し歴史を振り返ってみると、コンパイラは伝統的にIRに直線フォーマットを使用しています（Linear IR）。これは、基本ブロックと呼ばれる塊（チャンク）の中に、次から次へと命令が連続していることを意味します。命令は、スタック上の仮称やエントリを使って、情報を互いに受け渡します。これらのブロック間には制御フローのグラフがありますが、各ブロック内では命令は直線で、推論がしやすく、テキストとして出力しやすくなっています。SSA（Static Single Assignment、静的単一代入） と呼ばれるモデルでは、各々の仮称に一度のみ代入されるよう制約を課しています。
順々と並ぶ命令の明示的な順序をなくせば、プログラムの表現はより自由になります。また、仮称を削除して、代わりにグラフ内の命令ノード間の値をエッジにすることもできます。これは長い間行われており、Program Dependence Graph（PDG） として知られていますが、特に注目されるようになったのは、HotSpotやOpenJDKを使用している場合に通常使用されるC2 と呼ばれる最も有名なJava最適化JITです。このコンパイラはCliff Clickが設計したもので、sea-of-nodesとかsoup-of-nodesと呼ばれる、非常に自由な形式のグラフを使用しています。これは、ゆるく構造化されたグラフは理解しづらいという欠点を浮き彫りにしています。人間はグラフを推論するのが苦手ですし、文章で表現するのも難しいです。だからこそ、グラフとして描きたいのかもしれません。それがこの記事でやろうとしていることです。
GraalVM JITコンパイラはC2と類似のsea-of-nodesのグラフィカルなIRを使います。
Arithmetic and logic
private static int exampleArithOperator(int x, int y) {
return x + y;
}
グラフにはノード（小さな箱や楕円）とエッジ（それらの間の線）があります。各ノードのテキストは、参照しやすいように一意の番号で始まります。大まかに言えば、ノードはある種の命令を、エッジは命令間のデータフローまたは制御フローを意味します。この区別は重要なので、ここではデータエッジを薄い緑で、制御エッジを濃い赤で示しています。緑のデータフローのエッジは、あるノード（命令）の結果が他のノードの入力として使われることを意味します。赤色の制御フローのエッジは、最初に実行されるノードから次に実行されるノードへ制御が渡されることを意味します。あるノードが必要なデータを供給する別のノードに依存していることを示す場合、通常GraalVM JITコンパイラのIRではデータフローエッジを上向きにモデル化しますが、依存関係の方向よりもデータフローの方向が人々にとって理解しやすいことがわかっているので、下向きに描いています。
このグラフにあるのは、Javaの加算演算子の加算ノードです。このメソッドへの1個目と2個目のパラメータを意味するP(0)とP(1)を入力としてとります。これらのエッジは、加算演算子の2つのオペランドに対して、xとyのラベルが付けられています。これらは加算ノードのオペランドの名前であり、Javaソースコードの名前とは関係がないことに注意してください。このメソッドは結果を生成してReturnノードに送信されます。このメソッドにはStartノードもあり、制御はstartからreturnへと流れます。startノードから始まり、赤い制御フローのエッジに沿って、何かをする必要があるたびに、入力に必要なデータを生成するすべてのノードを実行する、という流れで、頭の中で関数を実行できます。
private static boolean exampleCompareOperator(int x, int y) {
return x <= y;
}
このグラフでは、GraalVM JITコンパイラが自由形式グラフのデータ構造を使ってプログラムを推論する方法を確認できます。less-thanノードがありますが、私たちのコードでは less-than-or-equal toと書いています。そして、trueValueエッジはC(0)から来ていて、定数値0、つまりfalseを意味し、falseValueはC(1)から来ていることに注目してください。
何が起こったかというと、GraalVM JITコンパイラは私たちのプログラムを x <= y から !(y <x) に書き換えたのです。これは正準化と呼ばれるプロセスの一部で、desugaringと呼ばれる概念に似ています。この考え方別の文脈で聞いたことがあるかもしれませんが、less-than-or-equal-to ではなく less-than だけを使うようにすれば、 less-than-or-equal-to を扱う必要がないため、コンパイラの残りの部分をよりシンプルにすることができるというものです。GraalVM JITコンパイラは正規形としてless-than-thanかgreater-thanのどちらかを使うことができますが、違いはありませんし、どちらかが選ばれただだけです。条件ノードは三項演算子のようなもので、条件から2つの値のうちの1つを選択します。
int exampleExactArith(int x, int y) throws ArithmeticException {
return Math.addExact(x, y);
}
Math.addExactは足し算を行いますが、オーバーフローした場合は例外をスローします。GraalVM JITコンパイラはこれをランタイムルーチンへのメソッド呼び出しで実装するのではなく、置換やグラフビルダープラグインと呼ばれるシステムを使ってノードを挿入しています。ここでのaddExactは、AddExactOverflowとAddExactの2つのノードで構成されています。最初のノードは演算がオーバーフローするかどうかを伝え、2番目のノードは演算を実行します。2 つの演算を分離することで、独立して演算を最適化することができます。
オレンジ色のGuardノードはオーバーフローテストの結果をチェックし、必要であればArithmeticExceptionをスローします。Guardノードは後により重要になります。
Local variables
private static int exampleLocalVariables(int x, int y) {
int a = x + y;
return a * 2 + a;
}
ローカル変数について考えると、グラフ表現の違いがより明確になります。このグラフを見ると、ローカル変数が完全になくなっているように見えます。ここではローカル変数の名前は見えず、ただのエッジです。値がパラメータから来たものであっても、ローカル変数から来たものであっても、式から来たものであっても、それは常にエッジでしかありません。GraalVM JITコンパイラがどのように乗算演算をよりシンプルな左1ビットシフト演算で表現することを選択したかもこれからわかります。
private static int exampleLocalVariablesState(int x, int y) {
int a = x + y;
/*
* The purpose of this function call to is to create a 'safepoint' - that
* means a location where a debugger could be attached. It means that the
* user may request the value of the local variable a at this point.
*/
opaqueCall();
return a * 2 + a;
}
GraalVM JITコンパイラはこのようなローカル変数に関する情報をどのようにして捨てることができるのでしょうか？そのメソッドの2行目にデバッガを付ければ、その時点でのローカル変数aの値を見たかったでしょう。これはどのように動作するのでしょうか？GraalVM JITコンパイラは、フレームステート（frame states）と呼ばれる場所にプログラムの状態に関するメタデータを保持しています。これらは、メソッドの開始時やメソッド呼び出しのような場所（ここでは opaqueCall の呼び出し）など、必要な場所にのみ追加されます。デバッガと同様に、コードを最適化したり、デバッガをアタッチした場合に最適化解除されるようにフレームステートは使われます。これらはほとんどのツールではデフォルトで非表示ですが、必要に応じて表示できます。ローカル変数 a の値は加算演算の結果であり、その演算から FrameState へのエッジと、それが実際に使用されている2か所へのエッジを確認できます。
Method calls
private static class ExampleObject {
public int x;
public ExampleObject(int x) {
this.x = x;
}
public int instanceCall(int y) {
return x + y;
}
}
private static int exampleSimpleCall(ExampleObject object, int x) {
return object.instanceCall(x);
}
GraalVM JITコンパイラにおけるシンプルなメソッド呼び出しはCallノードで表現されます。呼び出しに関する情報はMethodCallTargetという別のノードにアタッチされます。破線を使うことで、エッジが単なる情報であることを示しています。arg[0]とarg[1]がMethodCallTargetへの入力であることがわかります。arg[0]はインスタンスコールのためのレシーバー、もしくはthisオブジェクト（RubyやPythonではselfと呼ばれます）です。
private static int exampleStaticCall(int x) {
return staticCall(x);
}
レシーバーを渡さない点を除けば、静的呼び出しも同じです。
private interface InterfaceOneImpl {
int interfaceCall();
}
private static class OneImpl implements InterfaceOneImpl {
public int interfaceCall() {
return 14;
}
}
private static int exampleInterfaceCallOneImpl(InterfaceOneImpl x) {
return x.interfaceCall();
}
インターフェース呼び出しはまずCallノードによって表現されます。
コンパイルフェーズの後、GraalVM JITコンパイラがオブジェクトが期待される型であるかどうかを確認した上で、πノードがInterfaceOneImplに一致するように型を狭めていることが確認できます。πノードについてはスタンプに関する章で詳細を説明します。Callノードをコンパイルすると、特定メソッドへのdevirtualized呼び出しを実行できます。
private interface InterfaceManyImpls {
int interfaceCall();
}
private static class ManyImplsA implements InterfaceManyImpls {
public int interfaceCall() {
return 14;
}
}
private static class ManyImplsB implements InterfaceManyImpls {
public int interfaceCall() {
return 14;
}
}
private static int exampleInterfaceCallManyImpls(InterfaceManyImpls x) {
return x.interfaceCall();
}
many-implementationの場合、これらの余計なノードを取得しません。よりシンプルになったように思われますが、Callノードからπノードへ向かうレシーバーの値にスタンプがないため、適切な仮想インターフェース呼び出しのままです。
Control flow
private static int exampleIf(boolean condition, int x, int y) {
final int a;
if (condition) {
intField = x;
a = x;
} else {
intField = y;
a = y;
}
return a;
}
これまでの例では、赤の制御ラインはプログラムで1個のパスを形成していました。if-else文を書くと、制御フローは分岐します。この場合、if-elseブロックの後のreturn文のために再度合流します。Ifノードへの入力は分岐のために使う条件です。次にϕノードについて説明します。
private static int examplePhi(boolean condition, int x) {
final int a;
if (condition) {
a = opaqueCall();
} else {
a = opaqueCall();
}
return a + x;
}
典型的な SSA 形式のグラフと Graalグラフの両方で、人々が能力を試されると感じる概念がϕノードです。名前の由来は ph-ony、つまり、それらは実際の命令ではありません。この Java コードでは、ローカル変数 a を 2 つの場所で代入していますが、SSA では値は 1 つの場所でしか代入されないと言いました。制御フローが合流した後で、どうやって2つの異なる式の値を得ることができるのでしょうか？やっていることは、両方の値を入力としてϕノードに送り、どちらの値が生成されたかに基づいて 1 つの出力が生成されます。制御フローの合流点にϕノードがアタッチされ、この値を取得するトリガーの制御フローエッジでϕノードへのエッジをラベル付けします。この後でループについて話す際に、より複雑なϕノードを見ることにしましょう。
private static int exampleIfNeverTaken(boolean condition, int x, int y) {
final int a;t
if (condition) {
intField = x;
a = x;
} else {
intField = y;
a = y;
}
return a;
}
exampleIfNeverTaken(false, RANDOM.nextInt(), RANDOM.nextInt());
実際にはTrueのケースを使うことがないif-else文のバージョンを書く場合、GraalVM JITコンパイラは一度も使われないと想定してそれをコンパイルして（バイトおよびネイティブ）コードにはしません。そのかわりに、値がまだtrueではないことを確認するGuardノードを配置します。もし値がtrueであれば、コードは最適化を解除してインタプリタに戻ります。これはuncommon trapと呼ばれることがあります。
private static int exampleIntSwitch(int value, int x, int y, int z) {
final int a;
switch (value) {
case 0:
intField = x;
a = x;
break;
case 1:
intField = y;
a = y;
break;
default:
intField = z;
a = z;
break;
}
return a;
}
swich文は整数の場合、多岐分岐するIfノードのようです。キーの値はノードでラベル付けされ、ノードから出てくるエッジはエッジに対応するキーでラベル付けされます（デフォルトのケースの場合はその条件でラベル付けされます）。ϕには3個の値が入ろうとしています。switchの外部で計算された値がどう奇妙に見えるかに着目してください。なお、制御フローとデータフローはここでは完全に分離されています。
private static int exampleStringSwitch(String value, int x, int y, int z) {
final int a;
switch (value) {
case "foo":
intField = x;
a = x;
break;
case "bar":
intField = y;
a = y;
break;
default:
intField = z;
a = z;
break;
}
return a;
}
文字列のswitch文は整数のそれと同じように見えますが、実際にはもっと複雑なものであることがGraalグラフからわかります。この変換の一部はjavac Javaコンパイラで、一部はGraal JITコンパイラで行われています。
ここには本当に興味深い構造があります。最もはっきりしているのは、ノードからなる2つの菱形である、2つの大きな制御フローの分岐がある点です。一つは上方に、一つは下にあります。我々が持っているのは、どの文字列を持っているかを見つけるためのコードと、その下にある別の通常のIntegerSwitchで、これが実際のswitchの本体です。
どの文字列を持っているかを調べるコードは、それ自体も最初は文字列のハッシュコード上の整数のswitchです。そして、そのswitchの各ケースは、文字列がcase式の定数と同じインスタンスであるかどうかをチェックし、そうでない場合は同じ長さであるかどうかをチェックします。もし文字列長が一致すれば、配列比較を行うことで文字が等しいかどうかをチェックします。その際、データ構造の一部がNULLでないことを確認しています。文字列のswitchという、一見アトミックな演算のように見えるものを、なぜこんなにたくさんの小さな演算に分解してしまうのでしょうか？その理由の一部は、文字列のswitchのバイトコードが存在せず、バイトコードを追加したくなかったために、既存のバイトコードで表現する必要があったからだけでなく、GraalVM JITコンパイラでは、演算を分解すれば、その部分を独立して最適化できるという考えがあるからです。このグラフのある点では文字列の長さをロードしていますが、もし文字列の長さを他の場所で使用する場合は、一度だけロードして、プログラムのその両箇所で結果を使用できます。
Loops
private static int exampleWhile(int count) {
int a = count;
while (a > 0) {
intField = a;
a--;
}
return count;
}
これまでのところ、（破線の情報エッジを除いて）すべての矢印は下を向いています。これは、プログラムが一方向にしか進んでいないことを意味します。ループを持つプログラムでは、プログラムの初期の部分に戻る必要があります。これを赤い太線の矢印で示しています。これらのエッジが非常に重要であるため、太く描いています。ループは重要な最適化が見つかる場所であり、多くの複雑な制約がある場所です。
開始の制御フローだけを見てみると、このループがどのように始まるのか、そして終わり（end）と出口（exit）の両方を持っていることがわかります。終わり（end）にはループの開始点に戻る矢印があり、出口（exit）は、ループを離れて別のコードに進むところです。この例ではreturnに進んでいます。
制御フローを見てみると、ϕ はもう少し複雑です。ループに入る時の値は P(0) で、その後の値はそれ自体が定数 -1 に加算されていることがわかります（GraalVM JITコンパイラは負の値で減算を加算に正規化します）。これがループを抜けるかどうかを決めるための値になります。
つまり、グラフの中に2つのサイクルがあります。1つは制御フローで、もう1つはデータフローです。これらは別々になっていますが、一緒に動作しています。
private static int exampleFor(int count) {
for (int a = count; a > 0; a--) {
intField = a;
}
return count;
}
forループのグラフはまさにwhileループと同じです。javac Javaコンパイラにおいて、for desugarの余分な構文は同じバイトコードになります。
private static int exampleNestedWhile(int count) {
int a = count;
while (a > 0) {
int y = count;
while (y > 0) {
intField = a;
y--;
}
a--;
}
return count;
}
ループを入れ子にすると、制御フロー構造が非常に面白くなります。2個の太い線の逆向き（上方に戻る）エッジがあります。return文がグラフの中ほどにあることに注目してください。
private static int exampleWhileBreak(int count) {
int a = count;
while (a > 0) {
if (a == 4) {
break;
}
intField = a;
a--;
}
return count;
}
break文つきのループでは2個のループ出口ができます。breakからの出口が条件からの出口と違いがないことに注目してください。
private static int exampleNestedWhileBreak(int count) {
int a = count;
outer: while (a > 0) {
int b = count;
while (b > 0) {
if (b == 4) {
break outer;
}
intField = a;
b--;
}
a--;
}
return count;
}
入れ子のループ内のbreakの場合、どのループから抜け出しているかを示す破線が便利なことに注目してください。
private static int exampleReducible(boolean condition, int count) {
int a = count;
if (condition) {
a = count - 1;
}
while (a > 0) {
intField = a;
inner:
a--;
}
return count;
}
GraalVM JITコンパイラには、ループの構造化された表現があります。他のコンパイラがやっているようなgotoのようなものまでは下げられていません。これは、reducible loop（single-entry loop）と呼ばれる構造のループのようなものには問題なく動作します。Javaにはgotoがないので、これはJavaコードで書ける唯一のループです。しかし、JVMバイトコードを直接書くと、それほど単純な構造化されていないループを作成できます。このループをirreducible loop（もしくはnot-reducibleと呼んでいる場合もあります）と呼んでいます。
iload_1
istore_2
iload_0
ifeq L_start_of_loop
goto L_inside_loop # jump inside the loop
L_start_of_loop:
iload_2
ifle L_end_of_loop
iload_2
putstatic Field Irreducible intField I
L_inside_loop:
iinc 2 -1
goto L_start_of_loop
L_end_of_loop:
iload_1
ireturn
GraalVM JITコンパイラはこの非構造化ループを複数のエントリポイントを使ってシンプルに表現できません。コンパイラのロガーを有効にすると、コンパイル対象から外されていることがわかるでしょう。
231 355 4 Irreducible::exampleIrreducible (25 bytes) COMPILE SKIPPED: Non-reducible loop (not retryable)
このコードを逆コンパイルしてみると、（不可能と言っていたのに）Javaコードで表現できることに驚くかもしれません。ここで何が起こっているかというと、ループの残りの部分が2番目のエントリポイントを必要としないように、1つの反復が剥ぎ取られて複製されているということです。ではなぜGraalVM JITコンパイラはこのようなことをしないのでしょうか？Javaコードではこの類いのループを生成しないので、今のところ優先度が付けられていません。
public class IrreducibleDecompiled {
private static volatile int intField;
public static int exampleIrreducible(boolean var0, int var1) {
int var2 = var1;
if (var0) {
var2 = var1 - 1;
}
while(var2 > 0) {
intField = var2--;
}
return var1;
}
}
Objects
private static ExampleObject exampleObjectAllocation(int x) {
return new ExampleObject(x);
}
Newノードを使ってオブジェクトを割り当てます。コンストラクタへの別の呼び出しを確認できます。NewノードからCallノードへの制御フローのエッジがあることに着目してください。これはNewノードがヒープにスペースを作成しているためで、これが最初に発生する必要があります。
private static int[] exampleArrayAllocation(int x, int y) {
return new int[]{x, y};
}
配列の割り当てで配列が作成され、2個のストア演算を確認できます。
private static int exampleFieldRead(ExampleObject object) {
assert object != null; // otherwise this is a 'trivial' method and won't go past tier 1
return object.x;
}
フィールドの読み取りではLoadFieldノードを生成します。
このメソッドにはアサートの形でコードを追加しなければならないことに注意してください。そうでなければ、JVMがtrivialとして分類するためです。これはつまり、他の何かによってインライン化され、その一部としてコンパイルされる可能性が高いため、単純すぎてコンパイルする価値がないということです。
後に最適化を実行した後の同じグラフがどうなっているか見てみましょう。ハイレベルのロード操作は低レベルのメモリリード操作になり、アドレス計算はより多くのノードで明示的に行われるようになりました。これもまた、独立して最適化できるようにするためです。そこにある定数値C(12)は、オブジェクト内のオフセットです。後でπノードを説明します。
多くのオブジェクト操作は、フィールドの書き込み、配列の読み取りと書き込み、および安全でない読み取りと書き込みを含め、同じ方法で特定のノードに直接表現されます。
private static void exampleFieldWrite(ExampleObject object, int x) {
object.x = x;
}
private static int exampleArrayRead(int[] array, int n) {
return array[n];
}
private static void exampleArrayWrite(int[] array, int n, int x) {
array[n] = x;
}
private static boolean exampleInstanceOfOneImpl(Object x) {
return x instanceof InterfaceOneImpl;
}
instanceof式は最初ノードによって表現されますが、後にコンパイラが通ると下げられます。
ここでは、1つの実装を持つインターフェイスのinstanceofは、クラスポインタの単純な比較になっています – Graal用語ではハブ (hub) と呼ばれています。インターフェースの新しいインスタンスがロードされるとどうなるでしょうか？その場合、VMは最適化を解除し、コンパイルされたコードを捨ててコンパイルしなおします。
private static boolean exampleInstanceOfManyImpls(Object x) {
return x instanceof InterfaceManyImpls;
}
複数の実装を持つインターフェースのinstanceof式は、全ての実装に対してチェックしなければなりません。
後のコンパイルで、これがどのように比較的複雑なループに拡張されるかを確認できます。
Stamps and escape analysis
private static int exampleStamp(int x) {
return x & 0x1234;
}
スタンプ (stamp) とは、プログラム内の値についてGraalVM JITコンパイラが知っている情報のことです。スタンプは、Javaの型システムで表現できる以上の情報を伝えることができます。例えば、x & 0x1234と書いた場合、この値が0x1234（10進数で4660）より大きくなることはないことがわかります。このことをエッジにアノテーションすることができます。これは後続のノードがその情報を念頭に置いて最適化するのに役立つ可能性があります。
先ほどのπノードは、値に追加のスタンプを付けるためのものです。πノードのアイデアは配列の境界をチェックする作業から来ています。この名前は思いつきで、著者によると何の意味もありません。
private static int exampleFullEscape(int x) {
final int[] a = new int[]{x};
objectField = a;
return a[0];
}
GraalVM JITコンパイラはオブジェクトの仮想化や、部分的なエスケープ解析（partial escape analysis）を含むエスケープ解析（escape analysis）を高度にサポートしています。後のフェーズでオブジェクトの割り当てや参照をどのように表現しているかを見ると、その証拠を確認できます。最初このグラフにはNewArrayノードがありますが、これは後に分解されます。
これで、実際の割り当てへの入力である、配列の仮想表現と、割り当てられたオブジェクトを表現するためのノードを別々に持っています。
private static int exampleNoEscape(int x) {
final int[] a = new int[]{x};
return a[0];
}
今、同じコードのバージョンで配列がメソッドをエスケープしないものを試してみると、これによりオブジェクトの割り当てを削除できること、オブジェクトに書き込んだ値を読み返して、直接返し得ることがわかります。
private static int examplePartialEscape(boolean condition, int x) {
final int[] a = new int[]{x};
if (condition) {
objectField = a;
return a[0];
} else {
return a[0];
}
}
オブジェクトがあるコードパスでエスケープし、別のところではエスケープしないという、部分エスケープの場合にさらに明確です。これがGraalVM JITコンパイラの本当の強みです。
後のグラフでは割り当てが1個のブランチにのみ残り、別のブランチでは削除されていることがわかります。
Exceptions
private static void exampleThrow() {
throw RUNTIME_EXCEPTION;
}
例外のスローは送出対象の例外を取るUnwindノードによって表現されます。
private static void exampleCatch() {
try {
exampleThrow();
} catch (RuntimeException e) {
objectField = e;
}
}
例外送出の可能性のある呼び出しからは2個の制御フローのエッジが出ています。1個は正常ケースでもう一方は例外ケースでこの場合に例外送出します。ExceptionObjectで例外を取得してから、先ほどと同様に、InstanceOfノードを使って正しいcatchブランチにマッチさせることができます。
private static void exampleThrowCatch() {
try {
throw RUNTIME_EXCEPTION;
} catch (RuntimeException e) {
}
}
tryとcatchを同じメソッドで使って例外が逃げない場合、GraalVM JITコンパイラがどのようにコンパイルしているかに注目してください。ここにはいくつかの残骸が残っていますが、trueを取るIfブランチは後にクリーンアップされます。
Synchronization
private static void exampleSynchronized(Object object, int x) {
synchronized (object) {
intField = x;
}
}
SynchronizedブロックはMonitorEnterノードとMonitorExitノードのペアによって表されます。別のノードであるMonitorIdが現在使用中のモニターを識別します。
private static void exampleDoubleSynchronized(Object object, int x) {
synchronized (object) {
intField = x;
}
synchronized (object) {
intField = x;
}
}
説明したい最適化は、2個のsynchronizedブロックが同じロックを使って隣り合っている場合に、GraalVM JITコンパイラはまとめて1個にするというものです。
最初にノードがいくらか下がっていることがわかります。
で、ここでまとめられています。この段階で、1個の入口と出口に両方のボディが入っています。
private static void exampleLocalSynchronized(int x) {
final Object object = new Object();
synchronized (object) {
intField = x;
}
}
エスケープ解析を伴うオブジェクト割り当てのように、メソッドをエスケープしないモニターを最適化により除去できます。これは、他の誰もそれを競合できないことがわかっているためです。
Summary
これらの基本的なことで、ほとんどのGraalグラフが何をしているのかを理解できるでしょう。ここで見覚えのないノードがあった場合は、その名前から何をしているのかを判断するか、GraalVMのソースリポジトリで調べてみてください。
Graalグラフの自由形式（free-form）の構造のおかげで、プログラムがコンパイラを通過する際に、ノードを交換したり、再接続したり、削除したり、複数のよりシンプルなノードに置き換えたりして、プログラムを簡単に操作できます。バランスとしては、構造が緩いために、特に非常に大きなグラフになると読みづらくなることがあります。
今後のブログ記事では、Graalグラフについてもう少し詳しく書いていく予定です。その中で、Graalグラフを使うためのツールや、ShopifyでRubyに対しどのようにツールを使っているかをご紹介したいと考えています。
References
- The Program Dependence Graph and its use in optimization, Jeanne Ferrante, Karl Ottenstein, Joe Warren, 1987, or on Wikipedia
- Global value numbers and redundant computations, Barry Rosen, Mark Wegman, Kenneth Zadeck, 1998, or on Wikipedia
- A simple graph-based intermediate representation, Cliff Click, Michael Paleczny, 1995
- ABCD: eliminating array bounds checks on demand, Rastislav Bodík, Rajiv Gupta, Vivek Sarkar, 2000
- An intermediate representation for speculative optimizations in a dynamic compiler, Gilles Duboscq, Thomas Würthinger, Lukas Stadler, Christian Wimmer, Doug Simon, Hanspeter Mössenböck, 2013
- Practical partial evaluation for high-performance dynamic language runtimes, Thomas Würthinger, Christian Wimmer, Christian Humer, Andreas Wöß, Lukas Stadler, Chris Seaton, Gilles Duboscq, Doug Simon, Matthias Grimmer, 2017
- Specialising dynamic techniques for implementing the Ruby programming language, Chris Seaton, 2015
- Escape analysis for Java: theory and practice, Bruno Blanchet, 2003, or on Wikipedia
- Partial escape analysis and scalar replacement for Java, Lukas Stadler, Thomas Würthinger, Hanspeter Mössenböck, 2014
Notes
Javaのメソッドの例を示している箇所では、メソッドをループ内でランダムな入力で呼び出しています。
while (true) {
exampleLocalVariables(RANDOM.nextInt(), RANDOM.nextInt());
exampleLocalVariablesState(RANDOM.nextInt(), RANDOM.nextInt());
}
ソースコードで表現されているようにメソッドにコンパイル単位を制約するため、オンスタック再置換（On-stack-replacement、ループ本体を独立してコンパイルすること）とインライン化は無効になっています。ランダム入力により、値のプロファイリングがパラメータを定数に変えないようにしています。
Logico Inside 