前回はノードの正規化による最適化でした。
こちらの記事に沿って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; } }