001/*
002 * Copyright (c) 2011, 2014, Oracle and/or its affiliates. All rights reserved.
003 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004 *
005 * This code is free software; you can redistribute it and/or modify it
006 * under the terms of the GNU General Public License version 2 only, as
007 * published by the Free Software Foundation.
008 *
009 * This code is distributed in the hope that it will be useful, but WITHOUT
010 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
011 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
012 * version 2 for more details (a copy is included in the LICENSE file that
013 * accompanied this code).
014 *
015 * You should have received a copy of the GNU General Public License version
016 * 2 along with this work; if not, write to the Free Software Foundation,
017 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
018 *
019 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
020 * or visit www.oracle.com if you need additional information or have any
021 * questions.
022 */
023package com.oracle.graal.graph.spi;
024
025import jdk.internal.jvmci.meta.*;
026
027import com.oracle.graal.graph.*;
028
029/**
030 * Nodes can implement {@link Canonicalizable} or one of the two sub-interfaces {@link Unary} and
031 * {@link Binary} to provide local optimizations like constant folding and strength reduction.
032 * Implementations should return a replacement that is always semantically correct for the given
033 * inputs, or "this" if they do not see an opportunity for improvement.<br/>
034 * <br/>
035 * <b>Implementations of {@link Canonicalizable#canonical(CanonicalizerTool)} or the equivalent
036 * methods of the two sub-interfaces must not have any side effects.</b><br/>
037 * They are not allowed to change inputs, successors or properties of any node (including the
038 * current one) and they also cannot add new nodes to the graph.<br/>
039 * <br/>
040 * In addition to pre-existing nodes they can return newly created nodes, which will be added to the
041 * graph automatically if (and only if) the effects of the canonicalization are committed.
042 * Non-cyclic graphs (DAGs) of newly created nodes (i.e., one newly created node with an input to
043 * another newly created node) will be handled correctly.
044 */
045public interface Canonicalizable {
046
047    /**
048     * Implementations of this method can provide local optimizations like constant folding and
049     * strength reduction. Implementations should look at the properties and inputs of the current
050     * node and determine if there is a more optimal and always semantically correct replacement.<br/>
051     * The return value determines the effect that the canonicalization will have:
052     * <ul>
053     * <li>Returning an pre-existing node will replace the current node with the given one.</li>
054     * <li>Returning a newly created node (that was not yet added to the graph) will replace the
055     * current node with the given one, after adding it to the graph. If both the replacement and
056     * the replacee are anchored in control flow (fixed nodes), the replacement will be added to the
057     * control flow. It is invalid to replace a non-fixed node with a newly created fixed node
058     * (because its placement in the control flow cannot be determined without scheduling).</li>
059     * <li>Returning {@code null} will delete the current node and replace it with {@code null} at
060     * all usages. Note that it is not necessary to delete floating nodes that have no more usages
061     * this way - they will be deleted automatically.</li>
062     * </ul>
063     *
064     * @param tool provides access to runtime interfaces like {@link MetaAccessProvider}
065     */
066    Node canonical(CanonicalizerTool tool);
067
068    /**
069     * This sub-interface of {@link Canonicalizable} is intended for nodes that have exactly one
070     * input. It has an additional {@link #canonical(CanonicalizerTool, Node)} method that looks at
071     * the given input instead of the current input of the node - which can be used to ask
072     * "what if this input is changed to this node" - questions.
073     *
074     * @param <T> the common supertype of all inputs of this node
075     */
076    public interface Unary<T extends Node> extends Canonicalizable {
077
078        /**
079         * Similar to {@link Canonicalizable#canonical(CanonicalizerTool)}, except that
080         * implementations should act as if the current input of the node was the given one, i.e.,
081         * they should never look at the inputs via the this pointer.
082         */
083        Node canonical(CanonicalizerTool tool, T forValue);
084
085        /**
086         * Gets the current value of the input, so that calling
087         * {@link #canonical(CanonicalizerTool, Node)} with the value returned from this method
088         * should behave exactly like {@link Canonicalizable#canonical(CanonicalizerTool)}.
089         */
090        T getValue();
091
092        default Node canonical(CanonicalizerTool tool) {
093            return canonical(tool, getValue());
094        }
095    }
096
097    /**
098     * This sub-interface of {@link Canonicalizable} is intended for nodes that have exactly two
099     * inputs. It has an additional {@link #canonical(CanonicalizerTool, Node, Node)} method that
100     * looks at the given inputs instead of the current inputs of the node - which can be used to
101     * ask "what if this input is changed to this node" - questions.
102     *
103     * @param <T> the common supertype of all inputs of this node
104     */
105    public interface Binary<T extends Node> extends Canonicalizable {
106
107        /**
108         * Similar to {@link Canonicalizable#canonical(CanonicalizerTool)}, except that
109         * implementations should act as if the current input of the node was the given one, i.e.,
110         * they should never look at the inputs via the this pointer.
111         */
112        Node canonical(CanonicalizerTool tool, T forX, T forY);
113
114        /**
115         * Gets the current value of the input, so that calling
116         * {@link #canonical(CanonicalizerTool, Node, Node)} with the value returned from this
117         * method should behave exactly like {@link Canonicalizable#canonical(CanonicalizerTool)}.
118         */
119        T getX();
120
121        /**
122         * Gets the current value of the input, so that calling
123         * {@link #canonical(CanonicalizerTool, Node, Node)} with the value returned from this
124         * method should behave exactly like {@link Canonicalizable#canonical(CanonicalizerTool)}.
125         */
126        T getY();
127
128        default Node canonical(CanonicalizerTool tool) {
129            return canonical(tool, getX(), getY());
130        }
131    }
132
133    /**
134     * This sub-interface of {@link Canonicalizable.Binary} is for nodes with two inputs where the
135     * operation is commutative. It is used to improve GVN by trying to merge nodes with the same
136     * inputs in different order.
137     */
138    public interface BinaryCommutative<T extends Node> extends Binary<T> {
139
140        /**
141         * Ensure a canonical ordering of inputs for commutative nodes to improve GVN results. Order
142         * the inputs by increasing {@link Node#id} and call {@link Graph#findDuplicate(Node)} on
143         * the node if it's currently in a graph. It's assumed that if there was a constant on the
144         * left it's been moved to the right by other code and that ordering is left alone.
145         *
146         * @return the original node or another node with the same input ordering
147         */
148        Node maybeCommuteInputs();
149    }
150}