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