Graalのノードの正規化

前回はマシンコードの生成処理を見ました。

jyukutyo.hatenablog.com

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

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

今回はグラフを最適化することでより効率的なコードを生成する、という部分です。

正規化（Canonicalisation）

ここでの正規化は、ノードを再配置することを意味しています。さまざまな目的のためのものですが、定数畳み込みとノードの簡素化に着目します。

ノード自体に（子ノードを含む）自分自身を簡素化するメソッドがあります。各ノードはorg.graalvm.compiler.graph.spi.Canonicalizableを実装しています。

/**
 * Nodes can implement {@link Canonicalizable} or one of the two sub-interfaces {@link Unary} and
 * {@link Binary} to provide local optimizations like constant folding and strength reduction.
 * Implementations should return a replacement that is always semantically correct for the given
 * inputs, or "this" if they do not see an opportunity for improvement.<br/>
 * <br/>
 * <b>Implementations of {@link Canonicalizable#canonical(CanonicalizerTool)} or the equivalent
 * methods of the two sub-interfaces must not have any side effects.</b><br/>
 * They are not allowed to change inputs, successors or properties of any node (including the
 * current one) and they also cannot add new nodes to the graph.<br/>
 * <br/>
 * In addition to pre-existing nodes they can return newly created nodes, which will be added to the
 * graph automatically if (and only if) the effects of the canonicalization are committed.
 * Non-cyclic graphs (DAGs) of newly created nodes (i.e., one newly created node with an input to
 * another newly created node) will be handled correctly.
 */
public interface Canonicalizable {
    /**
     * Implementations of this method can provide local optimizations like constant folding and
     * strength reduction. Implementations should look at the properties and inputs of the current
     * node and determine if there is a more optimal and always semantically correct replacement.
     * <br/>
     * The return value determines the effect that the canonicalization will have:
     * <ul>
     * <li>Returning an pre-existing node will replace the current node with the given one.</li>
     * <li>Returning a newly created node (that was not yet added to the graph) will replace the
     * current node with the given one, after adding it to the graph. If both the replacement and
     * the replacee are anchored in control flow (fixed nodes), the replacement will be added to the
     * control flow. It is invalid to replace a non-fixed node with a newly created fixed node
     * (because its placement in the control flow cannot be determined without scheduling).</li>
     * <li>Returning {@code null} will delete the current node and replace it with {@code null} at
     * all usages. Note that it is not necessary to delete floating nodes that have no more usages
     * this way - they will be deleted automatically.</li>
     * </ul>
     *
     * @param tool provides access to runtime interfaces like {@link MetaAccessProvider}
     */
    Node canonical(CanonicalizerTool tool);
}

ここで、-(-x)という式を考えます（xは数値）。当然-(-x) = xです。これをノード上で見てみます。-はnegate、org.graalvm.compiler.nodes.calc.NegateNodeがあります。前述の式の変換と同様に、NegateNodeの子ノードがNegateNodeであれば、値をそのまま返すだけにして、簡素化します。

    @Override
    public ValueNode canonical(CanonicalizerTool tool, ValueNode forValue) {
        ValueNode synonym = findSynonym(forValue, getOp(forValue));
        if (synonym != null) {
            return synonym;
        }
        return this;
    }

    protected static ValueNode findSynonym(ValueNode forValue) {
        ArithmeticOpTable.UnaryOp<Neg> negOp = ArithmeticOpTable.forStamp(forValue.stamp()).getNeg();
        ValueNode synonym = UnaryArithmeticNode.findSynonym(forValue, negOp);
        if (synonym != null) {
            return synonym;
        }
        if (forValue instanceof NegateNode) {
            return ((NegateNode) forValue).getValue();
        }
        if (forValue instanceof SubNode && !(forValue.stamp() instanceof FloatStamp)) {
            SubNode sub = (SubNode) forValue;
            return SubNode.create(sub.getY(), sub.getX());
        }
        return null;
    }

forValue instanceof NegateNodeであればreturn ((NegateNode) forValue).getValue();で値だけ取り出しています。これでNegateNodeを取り除けたので、出力するマシンコードもより少ない命令にできます。

ただ、実はfindSynonym(ValueNode)はcanonical()から呼び出されていません（引数の数が合わない）。findSynonym(ValueNode)はNegateNode#create()で呼び出されます。簡素化としては単純な処理なので、生成時にやっているのでしょう。

AddNodeのcanonical()では、同じ値の加算と減算があるときにまとめたりしています。

    private static ValueNode canonical(AddNode addNode, BinaryOp<Add> op, ValueNode forX, ValueNode forY) {
        AddNode self = addNode;
        boolean associative = op.isAssociative();
        if (associative) {
            if (forX instanceof SubNode) {
                SubNode sub = (SubNode) forX;
                if (sub.getY() == forY) {
                    // (a - b) + b
                    return sub.getX();
                }
            }
            if (forY instanceof SubNode) {
                SubNode sub = (SubNode) forY;
                if (sub.getY() == forX) {
                    // b + (a - b)
                    return sub.getX();
                }
            }
        }