1 /*
2 * Copyright (c) 2011, 2018, 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 }