Graalのグラフ

こちらの内容に沿って、Graalの理解を深めています。

Understanding How Graal Works - a Java JIT Compiler Written in Java

前回はGraalにJITコンパイルをさせました。

jyukutyo.hatenablog.com

今回はGraalのグラフについてです。いわゆるプログラム依存グラフ（program-dependence-graph）です。無駄な処理を発見するために、コードをデータ構造（今回はグラフ）で表現するようにしているのです。これはGraalに限ったことではなく、C2コンパイラもこういった表現をしています（sea-of-nodes）。

x + yを例にします。x,yはローカル変数、+は演算子です。

矢印がデータフローです。2つのローカル変数が、+演算子に流れていきます。

また、データフローとは別に実行順序もあります。たとえばx,yがローカル変数ではなく、それぞれ値をgetterから取得するコードの場合を考えます。getX() + getY()です。

この場合、まずgetX()、そしてgetY()を呼び出すという実行順序があります。この流れもグラフに加えます。

緑の矢印がデータフロー、オレンジの矢印が実行順序です。この実行順序は内部の詳細を知らない限り順序を変えることができません。

IGV

Graalが作るこうしたグラフを実際に見ることができます。IGV（IdealGraphVisualiser）です。Graalをビルドした際にIGVもビルドできています。mx igvで起動できます。

IGVを起動したまま、-Dgraal.DumpオプションをつけてJavaアプリケーションを起動すると、IGVが出力を認識するのですぐにグラフが見れます。

サンプルとして適当なクラスを作りました。このaverage()メソッドのグラフを出してみます。

public class IGV {

    public static void main(String[] args) {
        while (true) {
            new IGV().average(1, 2);
        }
    }

    int average(int a, int b) {
        return (a + b) / 2;
    }
}

$ java \
--module-path=/Users/jyukutyo/code/graal/sdk/mxbuild/modules/org.graalvm.graal_sdk:/Users/jyukutyo/code/graal/truffle/mxbuild/modules/com.oracle.truffle.truffle_api.jar \
--upgrade-module-path=/Users/jyukutyo/code/graal/compiler/mxbuild/modules/jdk.internal.vm.compiler \
-XX:+UnlockExperimentalVMOptions \
-XX:+EnableJVMCI \
-XX:+UseJVMCICompiler \
-XX:-TieredCompilation \
-XX:+PrintCompilation \
-XX:CompileOnly=IGV::average \
-XX:CompileCommand=quiet \
-Dgraal.Dump \
IGV
...
Connected to the IGV on 127.0.0.1:4445
...
Dumping debug output in /Users/jyukutyo/code/one-trip/src/dumps/1511769737361
...

"Connected to the IGV"でIGVに接続され、"Dumping debug output"されるとIGVでグラフを見ることができます。

拡大します。

"P"はパラメータ、"C"は定数です。P(1)とP(2)で2つのパラメータ、C(2)は定数で数値（i32）の2です。

このグラフでは青の矢印がデータフロー、赤の矢印が実行順序です。

出力はどのようなものでしょうか？dumps/1511769737361ディレクトリにはHotSpotCompilation-28[IGV.average(int,_int)int].cfgといったファイルがあります。こんな感じです。

$ less HotSpotCompilation-28\[IGV.average\(int,_int\)int\].cfg
begin_compilation
  name " HotSpotCompilation-28[IGV.average(int, int)]"
  method "HotSpotCompilation-28[IGV.average(int, int)]"
  date 1511769737368
end_compilation
begin_cfg
  name "Final HIR schedule"
  begin_block
    name "B0"
    from_bci -1
    to_bci -1
    predecessors
    successors
    xhandlers
    flags
    probability 4607182418800017408
    begin_IR
      HIR
f <@#|@fixed with next>@ <|@
tid v0 <|@
d <@d|@=== Debug Properties ===
stamp: void
=== Inputs ===
stateAfter: -
=== Succesors ===
next: v8
=== Usages ===
=== Predecessor ===
- >@ <|@
instruction <@StartNode|@org.graalvm.compiler.nodes.StartNode>@ stateAfter: - #next: v8  <|@  <|@
f <@~|@floating>@ <|@
tid i2 <|@
d <@d|@=== Debug Properties ===
index: 1
stamp: i32
uncheckedStamp: [null]
=== Inputs ===
=== Succesors ===
=== Usages ===
i5
...

ループを使ってみます。グラフはどうなるでしょうか？

    int average(int[] values) {
        int sum = 0;
        for (int n = 0; n < values.length; n++) {
            sum += values[n];
        }
        return sum / values.length;
    }

グラフがすごく長くなりました。

今回はGraalのグラフ表現を見てみました。