1 /*
2 * Copyright (c) 2012, 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.replacements;
24
25 import static org.graalvm.compiler.nodes.calc.CompareNode.createCompareNode;
26
27 import java.util.List;
28
29 import org.graalvm.compiler.api.replacements.SnippetReflectionProvider;
30 import org.graalvm.compiler.core.common.calc.Condition;
31 import org.graalvm.compiler.graph.Node;
32 import org.graalvm.compiler.nodes.ConditionAnchorNode;
33 import org.graalvm.compiler.nodes.ConstantNode;
34 import org.graalvm.compiler.nodes.FixedGuardNode;
35 import org.graalvm.compiler.nodes.IfNode;
36 import org.graalvm.compiler.nodes.LogicConstantNode;
37 import org.graalvm.compiler.nodes.LogicNode;
38 import org.graalvm.compiler.nodes.PhiNode;
39 import org.graalvm.compiler.nodes.ShortCircuitOrNode;
40 import org.graalvm.compiler.nodes.StructuredGraph;
41 import org.graalvm.compiler.nodes.ValueNode;
42 import org.graalvm.compiler.nodes.calc.CompareNode;
43 import org.graalvm.compiler.nodes.calc.ConditionalNode;
44 import org.graalvm.compiler.nodes.calc.FloatingNode;
45 import org.graalvm.compiler.nodes.java.ClassIsAssignableFromNode;
46 import org.graalvm.compiler.nodes.java.InstanceOfDynamicNode;
47 import org.graalvm.compiler.nodes.java.InstanceOfNode;
48 import org.graalvm.compiler.nodes.spi.LoweringTool;
49 import org.graalvm.compiler.nodes.util.GraphUtil;
50 import org.graalvm.compiler.phases.util.Providers;
51 import org.graalvm.compiler.replacements.SnippetTemplate.AbstractTemplates;
52 import org.graalvm.compiler.replacements.SnippetTemplate.Arguments;
53 import org.graalvm.compiler.replacements.SnippetTemplate.UsageReplacer;
54
55 import jdk.vm.ci.code.TargetDescription;
56
57 /**
58 * Helper class for lowering {@link InstanceOfNode}s with snippets. The majority of the complexity
59 * in such a lowering derives from the fact that {@link InstanceOfNode} is a floating node. A
60 * snippet used to lower an {@link InstanceOfNode} will almost always incorporate control flow and
61 * replacing a floating node with control flow is not trivial.
62 * <p>
63 * The mechanism implemented in this class ensures that the graph for an instanceof snippet is
64 * instantiated once per {@link InstanceOfNode} being lowered. The result produced is then re-used
65 * by all usages of the node. Additionally, if there is a single usage that is an {@link IfNode},
66 * the control flow in the snippet is connected directly to the true and false successors of the
67 * {@link IfNode}. This avoids materializing the instanceof test as a boolean which is then retested
68 * by the {@link IfNode}.
69 */
70 public abstract class InstanceOfSnippetsTemplates extends AbstractTemplates {
71
72 public InstanceOfSnippetsTemplates(Providers providers, SnippetReflectionProvider snippetReflection, TargetDescription target) {
73 super(providers, snippetReflection, target);
74 }
75
76 /**
77 * Gets the arguments used to retrieve and instantiate an instanceof snippet template.
78 */
79 protected abstract Arguments makeArguments(InstanceOfUsageReplacer replacer, LoweringTool tool);
80
81 public void lower(FloatingNode instanceOf, LoweringTool tool) {
82 assert instanceOf instanceof InstanceOfNode || instanceOf instanceof InstanceOfDynamicNode || instanceOf instanceof ClassIsAssignableFromNode;
83 List<Node> usages = instanceOf.usages().snapshot();
84
85 Instantiation instantiation = new Instantiation();
86 for (Node usage : usages) {
87 final StructuredGraph graph = (StructuredGraph) usage.graph();
88
89 InstanceOfUsageReplacer replacer = createReplacer(instanceOf, instantiation, usage, graph);
90
91 if (instantiation.isInitialized()) {
92 // No need to re-instantiate the snippet - just re-use its result
93 replacer.replaceUsingInstantiation();
94 } else {
95 Arguments args = makeArguments(replacer, tool);
96 template(args).instantiate(providers.getMetaAccess(), instanceOf, replacer, tool, args);
97 }
98 }
99
100 assert instanceOf.hasNoUsages();
101 if (!instanceOf.isDeleted()) {
102 GraphUtil.killWithUnusedFloatingInputs(instanceOf);
103 }
104 }
105
106 /**
107 * Gets the specific replacer object used to replace the usage of an instanceof node with the
108 * result of an instantiated instanceof snippet.
109 */
110 protected InstanceOfUsageReplacer createReplacer(FloatingNode instanceOf, Instantiation instantiation, Node usage, final StructuredGraph graph) {
111 InstanceOfUsageReplacer replacer;
112 if (!canMaterialize(usage)) {
113 ValueNode trueValue = ConstantNode.forInt(1, graph);
114 ValueNode falseValue = ConstantNode.forInt(0, graph);
115 if (instantiation.isInitialized() && (trueValue != instantiation.trueValue || falseValue != instantiation.falseValue)) {
116 /*
117 * This code doesn't really care what values are used so adopt the values from the
118 * previous instantiation.
119 */
120 trueValue = instantiation.trueValue;
121 falseValue = instantiation.falseValue;
122 }
123 replacer = new NonMaterializationUsageReplacer(instantiation, trueValue, falseValue, instanceOf, usage);
124 } else {
125 assert usage instanceof ConditionalNode : "unexpected usage of " + instanceOf + ": " + usage;
126 ConditionalNode c = (ConditionalNode) usage;
127 replacer = new MaterializationUsageReplacer(instantiation, c.trueValue(), c.falseValue(), instanceOf, c);
128 }
129 return replacer;
130 }
131
132 /**
133 * Determines if an {@code instanceof} usage can be materialized.
134 */
135 protected boolean canMaterialize(Node usage) {
136 if (usage instanceof ConditionalNode) {
137 ConditionalNode cn = (ConditionalNode) usage;
138 return cn.trueValue().isConstant() && cn.falseValue().isConstant();
139 }
140 if (usage instanceof IfNode || usage instanceof FixedGuardNode || usage instanceof ShortCircuitOrNode || usage instanceof ConditionAnchorNode) {
141 return false;
142 }
143 return true;
144 }
145
146 /**
147 * The result of instantiating an instanceof snippet. This enables a snippet instantiation to be
148 * re-used which reduces compile time and produces better code.
149 */
150 public static final class Instantiation {
151
152 private ValueNode result;
153 private LogicNode condition;
154 private ValueNode trueValue;
155 private ValueNode falseValue;
156
157 /**
158 * Determines if the instantiation has occurred.
159 */
160 boolean isInitialized() {
161 return result != null;
162 }
163
164 void initialize(ValueNode r, ValueNode t, ValueNode f) {
165 assert !isInitialized();
166 this.result = r;
167 this.trueValue = t;
168 this.falseValue = f;
169 }
170
171 /**
172 * Gets the result of this instantiation as a condition.
173 *
174 * @param testValue the returned condition is true if the result is equal to this value
175 */
176 LogicNode asCondition(ValueNode testValue) {
177 assert isInitialized();
178 if (result.isConstant()) {
179 assert testValue.isConstant();
180 return LogicConstantNode.forBoolean(result.asConstant().equals(testValue.asConstant()), result.graph());
181 }
182 if (condition == null || (!(condition instanceof CompareNode)) || ((CompareNode) condition).getY() != testValue) {
183 // Re-use previously generated condition if the trueValue for the test is the same
184 condition = createCompareNode(result.graph(), Condition.EQ, result, testValue, null);
185 }
186 return condition;
187 }
188
189 /**
190 * Gets the result of the instantiation as a materialized value.
191 *
192 * @param t the true value for the materialization
193 * @param f the false value for the materialization
194 */
195 ValueNode asMaterialization(StructuredGraph graph, ValueNode t, ValueNode f) {
196 assert isInitialized();
197 if (t == this.trueValue && f == this.falseValue) {
198 // Can simply use the phi result if the same materialized values are expected.
199 return result;
200 } else {
201 return graph.unique(new ConditionalNode(asCondition(trueValue), t, f));
202 }
203 }
204 }
205
206 /**
207 * Replaces a usage of an {@link InstanceOfNode} or {@link InstanceOfDynamicNode}.
208 */
209 public abstract static class InstanceOfUsageReplacer implements UsageReplacer {
210
211 public final Instantiation instantiation;
212 public final FloatingNode instanceOf;
213 public final ValueNode trueValue;
214 public final ValueNode falseValue;
215
216 public InstanceOfUsageReplacer(Instantiation instantiation, FloatingNode instanceOf, ValueNode trueValue, ValueNode falseValue) {
217 assert instanceOf instanceof InstanceOfNode || instanceOf instanceof InstanceOfDynamicNode || instanceOf instanceof ClassIsAssignableFromNode;
218 this.instantiation = instantiation;
219 this.instanceOf = instanceOf;
220 this.trueValue = trueValue;
221 this.falseValue = falseValue;
222 }
223
224 /**
225 * Does the replacement based on a previously snippet instantiation.
226 */
227 public abstract void replaceUsingInstantiation();
228 }
229
230 /**
231 * Replaces the usage of an {@link InstanceOfNode} or {@link InstanceOfDynamicNode} that does
232 * not materialize the result of the type test.
233 */
234 public static class NonMaterializationUsageReplacer extends InstanceOfUsageReplacer {
235
236 private final Node usage;
237
238 public NonMaterializationUsageReplacer(Instantiation instantiation, ValueNode trueValue, ValueNode falseValue, FloatingNode instanceOf, Node usage) {
239 super(instantiation, instanceOf, trueValue, falseValue);
240 this.usage = usage;
241 }
242
243 @Override
244 public void replaceUsingInstantiation() {
245 usage.replaceFirstInput(instanceOf, instantiation.asCondition(trueValue));
246 }
247
248 @Override
249 public void replace(ValueNode oldNode, ValueNode newNode) {
250 assert newNode instanceof PhiNode;
251 assert oldNode == instanceOf;
252 newNode.inferStamp();
253 instantiation.initialize(newNode, trueValue, falseValue);
254 usage.replaceFirstInput(oldNode, instantiation.asCondition(trueValue));
255 }
256 }
257
258 /**
259 * Replaces the usage of an {@link InstanceOfNode} or {@link InstanceOfDynamicNode} that does
260 * materializes the result of the type test.
261 */
262 public static class MaterializationUsageReplacer extends InstanceOfUsageReplacer {
263
264 public final ConditionalNode usage;
265
266 public MaterializationUsageReplacer(Instantiation instantiation, ValueNode trueValue, ValueNode falseValue, FloatingNode instanceOf, ConditionalNode usage) {
267 super(instantiation, instanceOf, trueValue, falseValue);
268 this.usage = usage;
269 }
270
271 @Override
272 public void replaceUsingInstantiation() {
273 ValueNode newValue = instantiation.asMaterialization(usage.graph(), trueValue, falseValue);
274 usage.replaceAtUsages(newValue);
275 assert usage.hasNoUsages();
276 GraphUtil.killWithUnusedFloatingInputs(usage);
277 }
278
279 @Override
280 public void replace(ValueNode oldNode, ValueNode newNode) {
281 assert newNode instanceof PhiNode;
282 assert oldNode == instanceOf;
283 newNode.inferStamp();
284 instantiation.initialize(newNode, trueValue, falseValue);
285 usage.replaceAtUsages(newNode);
286 assert usage.hasNoUsages();
287 GraphUtil.killWithUnusedFloatingInputs(usage);
288 }
289 }
290 }