1 /*
   2  * Copyright (c) 2011, 2014, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  */
  23 
  24 
  25 package org.graalvm.compiler.graph.spi;
  26 
  27 import org.graalvm.compiler.graph.Graph;
  28 import org.graalvm.compiler.graph.Node;
  29 
  30 import jdk.vm.ci.meta.MetaAccessProvider;
  31 
  32 /**
  33  * Nodes can implement {@link Canonicalizable} or one of the two sub-interfaces {@link Unary} and
  34  * {@link Binary} to provide local optimizations like constant folding and strength reduction.
  35  * Implementations should return a replacement that is always semantically correct for the given
  36  * inputs, or "this" if they do not see an opportunity for improvement.<br/>
  37  * <br/>
  38  * <b>Implementations of {@link Canonicalizable#canonical(CanonicalizerTool)} or the equivalent
  39  * methods of the two sub-interfaces must not have any side effects.</b><br/>
  40  * They are not allowed to change inputs, successors or properties of any node (including the
  41  * current one) and they also cannot add new nodes to the graph.<br/>
  42  * <br/>
  43  * In addition to pre-existing nodes they can return newly created nodes, which will be added to the
  44  * graph automatically if (and only if) the effects of the canonicalization are committed.
  45  * Non-cyclic graphs (DAGs) of newly created nodes (i.e., one newly created node with an input to
  46  * another newly created node) will be handled correctly.
  47  */
  48 public interface Canonicalizable {
  49 
  50     /**
  51      * Implementations of this method can provide local optimizations like constant folding and
  52      * strength reduction. Implementations should look at the properties and inputs of the current
  53      * node and determine if there is a more optimal and always semantically correct replacement.
  54      * <br/>
  55      * The return value determines the effect that the canonicalization will have:
  56      * <ul>
  57      * <li>Returning an pre-existing node will replace the current node with the given one.</li>
  58      * <li>Returning a newly created node (that was not yet added to the graph) will replace the
  59      * current node with the given one, after adding it to the graph. If both the replacement and
  60      * the replacee are anchored in control flow (fixed nodes), the replacement will be added to the
  61      * control flow. It is invalid to replace a non-fixed node with a newly created fixed node
  62      * (because its placement in the control flow cannot be determined without scheduling).</li>
  63      * <li>Returning {@code null} will delete the current node and replace it with {@code null} at
  64      * all usages. Note that it is not necessary to delete floating nodes that have no more usages
  65      * this way - they will be deleted automatically.</li>
  66      * </ul>
  67      *
  68      * @param tool provides access to runtime interfaces like {@link MetaAccessProvider}
  69      */
  70     Node canonical(CanonicalizerTool tool);
  71 
  72     /**
  73      * This sub-interface of {@link Canonicalizable} is intended for nodes that have exactly one
  74      * input. It has an additional {@link #canonical(CanonicalizerTool, Node)} method that looks at
  75      * the given input instead of the current input of the node - which can be used to ask "what if
  76      * this input is changed to this node" - questions.
  77      *
  78      * @param <T> the common supertype of all inputs of this node
  79      */
  80     public interface Unary<T extends Node> extends Canonicalizable {
  81 
  82         /**
  83          * Similar to {@link Canonicalizable#canonical(CanonicalizerTool)}, except that
  84          * implementations should act as if the current input of the node was the given one, i.e.,
  85          * they should never look at the inputs via the this pointer.
  86          */
  87         Node canonical(CanonicalizerTool tool, T forValue);
  88 
  89         /**
  90          * Gets the current value of the input, so that calling
  91          * {@link #canonical(CanonicalizerTool, Node)} with the value returned from this method
  92          * should behave exactly like {@link Canonicalizable#canonical(CanonicalizerTool)}.
  93          */
  94         T getValue();
  95 
  96         @SuppressWarnings("unchecked")
  97         @Override
  98         default T canonical(CanonicalizerTool tool) {
  99             return (T) canonical(tool, getValue());
 100         }
 101     }
 102 
 103     /**
 104      * This sub-interface of {@link Canonicalizable} is intended for nodes that have exactly two
 105      * inputs. It has an additional {@link #canonical(CanonicalizerTool, Node, Node)} method that
 106      * looks at the given inputs instead of the current inputs of the node - which can be used to
 107      * ask "what if this input is changed to this node" - questions.
 108      *
 109      * @param <T> the common supertype of all inputs of this node
 110      */
 111     public interface Binary<T extends Node> extends Canonicalizable {
 112 
 113         /**
 114          * Similar to {@link Canonicalizable#canonical(CanonicalizerTool)}, except that
 115          * implementations should act as if the current input of the node was the given one, i.e.,
 116          * they should never look at the inputs via the this pointer.
 117          */
 118         Node canonical(CanonicalizerTool tool, T forX, T forY);
 119 
 120         /**
 121          * Gets the current value of the input, so that calling
 122          * {@link #canonical(CanonicalizerTool, Node, Node)} with the value returned from this
 123          * method should behave exactly like {@link Canonicalizable#canonical(CanonicalizerTool)}.
 124          */
 125         T getX();
 126 
 127         /**
 128          * Gets the current value of the input, so that calling
 129          * {@link #canonical(CanonicalizerTool, Node, Node)} with the value returned from this
 130          * method should behave exactly like {@link Canonicalizable#canonical(CanonicalizerTool)}.
 131          */
 132         T getY();
 133 
 134         @SuppressWarnings("unchecked")
 135         @Override
 136         default T canonical(CanonicalizerTool tool) {
 137             return (T) canonical(tool, getX(), getY());
 138         }
 139     }
 140 
 141     /**
 142      * This sub-interface of {@link Canonicalizable.Binary} is for nodes with two inputs where the
 143      * operation is commutative. It is used to improve GVN by trying to merge nodes with the same
 144      * inputs in different order.
 145      */
 146     public interface BinaryCommutative<T extends Node> extends Binary<T> {
 147 
 148         /**
 149          * Ensure a canonical ordering of inputs for commutative nodes to improve GVN results. Order
 150          * the inputs by increasing {@link Node#id} and call {@link Graph#findDuplicate(Node)} on
 151          * the node if it's currently in a graph. It's assumed that if there was a constant on the
 152          * left it's been moved to the right by other code and that ordering is left alone.
 153          *
 154          * @return the original node or another node with the same input ordering
 155          */
 156         Node maybeCommuteInputs();
 157     }
 158 }