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 package org.graalvm.compiler.graph.spi;
24
25 import org.graalvm.compiler.graph.Graph;
26 import org.graalvm.compiler.graph.Node;
27
28 import jdk.vm.ci.meta.MetaAccessProvider;
29
30 /**
31 * Nodes can implement {@link Canonicalizable} or one of the two sub-interfaces {@link Unary} and
32 * {@link Binary} to provide local optimizations like constant folding and strength reduction.
33 * Implementations should return a replacement that is always semantically correct for the given
34 * inputs, or "this" if they do not see an opportunity for improvement.<br/>
35 * <br/>
36 * <b>Implementations of {@link Canonicalizable#canonical(CanonicalizerTool)} or the equivalent
37 * methods of the two sub-interfaces must not have any side effects.</b><br/>
38 * They are not allowed to change inputs, successors or properties of any node (including the
39 * current one) and they also cannot add new nodes to the graph.<br/>
40 * <br/>
41 * In addition to pre-existing nodes they can return newly created nodes, which will be added to the
42 * graph automatically if (and only if) the effects of the canonicalization are committed.
43 * Non-cyclic graphs (DAGs) of newly created nodes (i.e., one newly created node with an input to
44 * another newly created node) will be handled correctly.
45 */
46 public interface Canonicalizable {
47
48 /**
49 * Implementations of this method can provide local optimizations like constant folding and
50 * strength reduction. Implementations should look at the properties and inputs of the current
51 * node and determine if there is a more optimal and always semantically correct replacement.
52 * <br/>
53 * The return value determines the effect that the canonicalization will have:
54 * <ul>
55 * <li>Returning an pre-existing node will replace the current node with the given one.</li>
56 * <li>Returning a newly created node (that was not yet added to the graph) will replace the
57 * current node with the given one, after adding it to the graph. If both the replacement and
58 * the replacee are anchored in control flow (fixed nodes), the replacement will be added to the
59 * control flow. It is invalid to replace a non-fixed node with a newly created fixed node
60 * (because its placement in the control flow cannot be determined without scheduling).</li>
61 * <li>Returning {@code null} will delete the current node and replace it with {@code null} at
62 * all usages. Note that it is not necessary to delete floating nodes that have no more usages
63 * this way - they will be deleted automatically.</li>
64 * </ul>
65 *
66 * @param tool provides access to runtime interfaces like {@link MetaAccessProvider}
67 */
68 Node canonical(CanonicalizerTool tool);
69
70 /**
71 * This sub-interface of {@link Canonicalizable} is intended for nodes that have exactly one
72 * input. It has an additional {@link #canonical(CanonicalizerTool, Node)} method that looks at
73 * the given input instead of the current input of the node - which can be used to ask "what if
74 * this input is changed to this node" - questions.
75 *
76 * @param <T> the common supertype of all inputs of this node
77 */
78 public interface Unary<T extends Node> extends Canonicalizable {
79
80 /**
81 * Similar to {@link Canonicalizable#canonical(CanonicalizerTool)}, except that
82 * implementations should act as if the current input of the node was the given one, i.e.,
83 * they should never look at the inputs via the this pointer.
84 */
85 Node canonical(CanonicalizerTool tool, T forValue);
86
87 /**
88 * Gets the current value of the input, so that calling
89 * {@link #canonical(CanonicalizerTool, Node)} with the value returned from this method
90 * should behave exactly like {@link Canonicalizable#canonical(CanonicalizerTool)}.
91 */
92 T getValue();
93
94 @SuppressWarnings("unchecked")
95 @Override
96 default T canonical(CanonicalizerTool tool) {
97 return (T) canonical(tool, getValue());
98 }
99 }
100
101 /**
102 * This sub-interface of {@link Canonicalizable} is intended for nodes that have exactly two
103 * inputs. It has an additional {@link #canonical(CanonicalizerTool, Node, Node)} method that
104 * looks at the given inputs instead of the current inputs of the node - which can be used to
105 * ask "what if this input is changed to this node" - questions.
106 *
107 * @param <T> the common supertype of all inputs of this node
108 */
109 public interface Binary<T extends Node> extends Canonicalizable {
110
111 /**
112 * Similar to {@link Canonicalizable#canonical(CanonicalizerTool)}, except that
113 * implementations should act as if the current input of the node was the given one, i.e.,
114 * they should never look at the inputs via the this pointer.
115 */
116 Node canonical(CanonicalizerTool tool, T forX, T forY);
117
118 /**
119 * Gets the current value of the input, so that calling
120 * {@link #canonical(CanonicalizerTool, Node, Node)} with the value returned from this
121 * method should behave exactly like {@link Canonicalizable#canonical(CanonicalizerTool)}.
122 */
123 T getX();
124
125 /**
126 * Gets the current value of the input, so that calling
127 * {@link #canonical(CanonicalizerTool, Node, Node)} with the value returned from this
128 * method should behave exactly like {@link Canonicalizable#canonical(CanonicalizerTool)}.
129 */
130 T getY();
131
132 @SuppressWarnings("unchecked")
133 @Override
134 default T canonical(CanonicalizerTool tool) {
135 return (T) canonical(tool, getX(), getY());
136 }
137 }
138
139 /**
140 * This sub-interface of {@link Canonicalizable.Binary} is for nodes with two inputs where the
141 * operation is commutative. It is used to improve GVN by trying to merge nodes with the same
142 * inputs in different order.
143 */
144 public interface BinaryCommutative<T extends Node> extends Binary<T> {
145
146 /**
147 * Ensure a canonical ordering of inputs for commutative nodes to improve GVN results. Order
148 * the inputs by increasing {@link Node#id} and call {@link Graph#findDuplicate(Node)} on
149 * the node if it's currently in a graph. It's assumed that if there was a constant on the
150 * left it's been moved to the right by other code and that ordering is left alone.
151 *
152 * @return the original node or another node with the same input ordering
153 */
154 Node maybeCommuteInputs();
155 }
156 }