Graalでの大域的値番号付け

前回はノードの正規化による最適化でした。

jyukutyo.hatenablog.com

こちらの記事に沿ってGraalの理解を深めます。

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

今回は大域的値番号付けです。大域的値番号付け（Global value numbering, GVN）はコンパイラ最適化手法の1つです。単純に言うと、同一内容の処理が複数あれば、ノードは1つしか使わないということです。

次のコードを考えてみます。

int workload(int a, int b) {
  return (a + b) * (a + b);
}

Graalでは同一の入力であれば等しいとみなします。すべてのノードをハッシュマップに入れておき、等価かを効果的に判定します。ノードのキャッシュのような感じです。大域的値番号付けはorg.graalvm.compiler.phases.common.CanonicalizerPhaseの内部クラスInstanceでやっています。

    private final class Instance extends Phase {
        public boolean tryGlobalValueNumbering(Node node, NodeClass<?> nodeClass) {
            if (nodeClass.valueNumberable()) {
                Node newNode = node.graph().findDuplicate(node);
                if (newNode != null) {
                    assert !(node instanceof FixedNode || newNode instanceof FixedNode);
                    node.replaceAtUsagesAndDelete(newNode);
                    COUNTER_GLOBAL_VALUE_NUMBERING_HITS.increment(debug);
                    debug.log("GVN applied and new node is %1s", newNode);
                    return true;
                }
            }
            return false;
        }
    }

グラフから重複を探し、あれば重複ノードを削除してこのノードに置き換えています。

なお、Instanceクラスが継承しているorg.graalvm.compiler.phases.Phaseは、Graalのグラフを変更する処理のためのインタフェースです。

/**
 * Base class for compiler phases that don't need a context object.
 */
public abstract class Phase extends BasePhase<Object> {
...
    protected abstract void run(StructuredGraph graph);
...
}

IGVで見てみます。

5から6に青い矢印が2本出ています。乗算で同一ノードを2回使っているのがわかります。

ここでassert !(node instanceof FixedNode || newNode instanceof FixedNode);をしていることに着目します。FixedNodeでないということは、副作用を持たないことを意味します。副作用を持っていない場合のみ大域的値番号付けし、持っていればそのまま別のノードとして扱います。(a + b) * (a + b)ではなく(getA() + getB()) * (getA() + getB())のようにメソッド呼び出しにすると、メソッド内で副作用があるかもしれないためFixedNodeとなり、大域的値番号付けをしません。

class Demo3 {
    public static void main(String[] args) {
        while (true) {
            new Demo3().workload();
        }
    }

    private int workload() {
        return (getA() + getB()) * (getA() + getB());
    }

    private int getA() {
        return 14;
    }

    private int getB() {
        return 2;
    }
}