1 /* 2 * Copyright (c) 2012, 2015, 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.hotspot.replacements; 24 25 import static org.graalvm.compiler.core.common.GraalOptions.GeneratePIC; 26 import static org.graalvm.compiler.hotspot.replacements.HotSpotReplacementsUtil.PRIMARY_SUPERS_LOCATION; 27 import static org.graalvm.compiler.hotspot.replacements.HotSpotReplacementsUtil.SECONDARY_SUPER_CACHE_LOCATION; 28 import static org.graalvm.compiler.hotspot.replacements.HotSpotReplacementsUtil.loadHubIntrinsic; 29 import static org.graalvm.compiler.hotspot.replacements.HotspotSnippetsOptions.TypeCheckMaxHints; 30 import static org.graalvm.compiler.hotspot.replacements.HotspotSnippetsOptions.TypeCheckMinProfileHitProbability; 31 import static org.graalvm.compiler.hotspot.replacements.TypeCheckSnippetUtils.checkSecondarySubType; 32 import static org.graalvm.compiler.hotspot.replacements.TypeCheckSnippetUtils.checkUnknownSubType; 33 import static org.graalvm.compiler.hotspot.replacements.TypeCheckSnippetUtils.createHints; 34 import static org.graalvm.compiler.hotspot.replacements.TypeCheckSnippetUtils.displayHit; 35 import static org.graalvm.compiler.hotspot.replacements.TypeCheckSnippetUtils.displayMiss; 36 import static org.graalvm.compiler.hotspot.replacements.TypeCheckSnippetUtils.exactHit; 37 import static org.graalvm.compiler.hotspot.replacements.TypeCheckSnippetUtils.exactMiss; 38 import static org.graalvm.compiler.hotspot.replacements.TypeCheckSnippetUtils.hintsHit; 39 import static org.graalvm.compiler.hotspot.replacements.TypeCheckSnippetUtils.hintsMiss; 40 import static org.graalvm.compiler.hotspot.replacements.TypeCheckSnippetUtils.isNull; 41 import static org.graalvm.compiler.nodes.extended.BranchProbabilityNode.LIKELY_PROBABILITY; 42 import static org.graalvm.compiler.nodes.extended.BranchProbabilityNode.NOT_FREQUENT_PROBABILITY; 43 import static org.graalvm.compiler.nodes.extended.BranchProbabilityNode.NOT_LIKELY_PROBABILITY; 44 import static org.graalvm.compiler.nodes.extended.BranchProbabilityNode.probability; 45 import static jdk.vm.ci.meta.DeoptimizationAction.InvalidateReprofile; 46 import static jdk.vm.ci.meta.DeoptimizationReason.OptimizedTypeCheckViolated; 47 48 import org.graalvm.compiler.api.replacements.Snippet; 49 import org.graalvm.compiler.api.replacements.Snippet.ConstantParameter; 50 import org.graalvm.compiler.api.replacements.Snippet.VarargsParameter; 51 import org.graalvm.compiler.core.common.type.StampFactory; 52 import org.graalvm.compiler.debug.GraalError; 53 import org.graalvm.compiler.hotspot.meta.HotSpotProviders; 54 import org.graalvm.compiler.hotspot.nodes.SnippetAnchorNode; 55 import org.graalvm.compiler.hotspot.nodes.type.KlassPointerStamp; 56 import org.graalvm.compiler.hotspot.replacements.TypeCheckSnippetUtils.Hints; 57 import org.graalvm.compiler.hotspot.replacements.aot.ResolveConstantSnippets; 58 import org.graalvm.compiler.hotspot.word.KlassPointer; 59 import org.graalvm.compiler.nodes.ConstantNode; 60 import org.graalvm.compiler.nodes.DeoptimizeNode; 61 import org.graalvm.compiler.nodes.PiNode; 62 import org.graalvm.compiler.nodes.StructuredGraph; 63 import org.graalvm.compiler.nodes.TypeCheckHints; 64 import org.graalvm.compiler.nodes.ValueNode; 65 import org.graalvm.compiler.nodes.extended.BranchProbabilityNode; 66 import org.graalvm.compiler.nodes.extended.GuardingNode; 67 import org.graalvm.compiler.nodes.java.ClassIsAssignableFromNode; 68 import org.graalvm.compiler.nodes.java.InstanceOfDynamicNode; 69 import org.graalvm.compiler.nodes.java.InstanceOfNode; 70 import org.graalvm.compiler.nodes.spi.LoweringTool; 71 import org.graalvm.compiler.replacements.InstanceOfSnippetsTemplates; 72 import org.graalvm.compiler.replacements.SnippetTemplate.Arguments; 73 import org.graalvm.compiler.replacements.SnippetTemplate.SnippetInfo; 74 import org.graalvm.compiler.replacements.Snippets; 75 import org.graalvm.compiler.replacements.nodes.ExplodeLoopNode; 76 77 import jdk.vm.ci.code.TargetDescription; 78 import jdk.vm.ci.hotspot.HotSpotResolvedObjectType; 79 import jdk.vm.ci.meta.Assumptions; 80 import jdk.vm.ci.meta.DeoptimizationAction; 81 import jdk.vm.ci.meta.DeoptimizationReason; 82 import jdk.vm.ci.meta.JavaKind; 83 import jdk.vm.ci.meta.JavaTypeProfile; 84 import jdk.vm.ci.meta.TriState; 85 86 /** 87 * Snippets used for implementing the type test of an instanceof instruction. Since instanceof is a 88 * floating node, it is lowered separately for each of its usages. 89 * 90 * The type tests implemented are described in the paper 91 * <a href="http://dl.acm.org/citation.cfm?id=583821"> Fast subtype checking in the HotSpot JVM</a> 92 * by Cliff Click and John Rose. 93 */ 94 public class InstanceOfSnippets implements Snippets { 95 96 /** 97 * A test against a set of hints derived from a profile with 100% precise coverage of seen 98 * types. This snippet deoptimizes on hint miss paths. 99 */ 100 @Snippet 101 public static Object instanceofWithProfile(Object object, @VarargsParameter KlassPointer[] hints, @VarargsParameter boolean[] hintIsPositive, Object trueValue, Object falseValue, 102 @ConstantParameter boolean nullSeen) { 103 if (probability(NOT_FREQUENT_PROBABILITY, object == null)) { 104 isNull.inc(); 105 if (!nullSeen) { 106 // See comment below for other deoptimization path; the 107 // same reasoning applies here. 108 DeoptimizeNode.deopt(InvalidateReprofile, OptimizedTypeCheckViolated); 109 } 110 return falseValue; 111 } 112 GuardingNode anchorNode = SnippetAnchorNode.anchor(); 113 KlassPointer objectHub = loadHubIntrinsic(PiNode.piCastNonNull(object, anchorNode)); 114 // if we get an exact match: succeed immediately 115 ExplodeLoopNode.explodeLoop(); 116 for (int i = 0; i < hints.length; i++) { 117 KlassPointer hintHub = hints[i]; 118 boolean positive = hintIsPositive[i]; 119 if (probability(LIKELY_PROBABILITY, hintHub.equal(objectHub))) { 120 hintsHit.inc(); 121 return positive ? trueValue : falseValue; 122 } 123 hintsMiss.inc(); 124 } 125 // This maybe just be a rare event but it might also indicate a phase change 126 // in the application. Ideally we want to use DeoptimizationAction.None for 127 // the former but the cost is too high if indeed it is the latter. As such, 128 // we defensively opt for InvalidateReprofile. 129 DeoptimizeNode.deopt(DeoptimizationAction.InvalidateReprofile, OptimizedTypeCheckViolated); 130 return falseValue; 131 } 132 133 /** 134 * A test against a final type. 135 */ 136 @Snippet 137 public static Object instanceofExact(Object object, KlassPointer exactHub, Object trueValue, Object falseValue) { 138 if (probability(NOT_FREQUENT_PROBABILITY, object == null)) { 139 isNull.inc(); 140 return falseValue; 141 } 142 GuardingNode anchorNode = SnippetAnchorNode.anchor(); 143 KlassPointer objectHub = loadHubIntrinsic(PiNode.piCastNonNull(object, anchorNode)); 144 if (probability(LIKELY_PROBABILITY, objectHub.notEqual(exactHub))) { 145 exactMiss.inc(); 146 return falseValue; 147 } 148 exactHit.inc(); 149 return trueValue; 150 } 151 152 @Snippet 153 public static Object instanceofExactPIC(Object object, KlassPointer exactHub, Object trueValue, Object falseValue) { 154 KlassPointer exactHubPIC = ResolveConstantSnippets.resolveKlassConstant(exactHub); 155 return instanceofExact(object, exactHubPIC, trueValue, falseValue); 156 } 157 158 /** 159 * A test against a primary type. 160 */ 161 @Snippet 162 public static Object instanceofPrimary(KlassPointer hub, Object object, @ConstantParameter int superCheckOffset, Object trueValue, Object falseValue) { 163 if (probability(NOT_FREQUENT_PROBABILITY, object == null)) { 164 isNull.inc(); 165 return falseValue; 166 } 167 GuardingNode anchorNode = SnippetAnchorNode.anchor(); 168 KlassPointer objectHub = loadHubIntrinsic(PiNode.piCastNonNull(object, anchorNode)); 169 if (probability(NOT_LIKELY_PROBABILITY, objectHub.readKlassPointer(superCheckOffset, PRIMARY_SUPERS_LOCATION).notEqual(hub))) { 170 displayMiss.inc(); 171 return falseValue; 172 } 173 displayHit.inc(); 174 return trueValue; 175 } 176 177 @Snippet 178 public static Object instanceofPrimaryPIC(KlassPointer hub, Object object, @ConstantParameter int superCheckOffset, Object trueValue, Object falseValue) { 179 KlassPointer resolvedHub = ResolveConstantSnippets.resolveKlassConstant(hub); 180 return instanceofPrimary(resolvedHub, object, superCheckOffset, trueValue, falseValue); 181 } 182 183 /** 184 * A test against a restricted secondary type type. 185 */ 186 @Snippet 187 public static Object instanceofSecondary(KlassPointer hub, Object object, @VarargsParameter KlassPointer[] hints, @VarargsParameter boolean[] hintIsPositive, Object trueValue, Object falseValue) { 188 if (probability(NOT_FREQUENT_PROBABILITY, object == null)) { 189 isNull.inc(); 190 return falseValue; 191 } 192 GuardingNode anchorNode = SnippetAnchorNode.anchor(); 193 KlassPointer objectHub = loadHubIntrinsic(PiNode.piCastNonNull(object, anchorNode)); 194 // if we get an exact match: succeed immediately 195 ExplodeLoopNode.explodeLoop(); 196 for (int i = 0; i < hints.length; i++) { 197 KlassPointer hintHub = hints[i]; 198 boolean positive = hintIsPositive[i]; 199 if (probability(NOT_FREQUENT_PROBABILITY, hintHub.equal(objectHub))) { 200 hintsHit.inc(); 201 return positive ? trueValue : falseValue; 202 } 203 } 204 hintsMiss.inc(); 205 if (!checkSecondarySubType(hub, objectHub)) { 206 return falseValue; 207 } 208 return trueValue; 209 } 210 211 @Snippet 212 public static Object instanceofSecondaryPIC(KlassPointer hub, Object object, @VarargsParameter KlassPointer[] hints, @VarargsParameter boolean[] hintIsPositive, Object trueValue, 213 Object falseValue) { 214 KlassPointer resolvedHub = ResolveConstantSnippets.resolveKlassConstant(hub); 215 return instanceofSecondary(resolvedHub, object, hints, hintIsPositive, trueValue, falseValue); 216 } 217 218 /** 219 * Type test used when the type being tested against is not known at compile time. 220 */ 221 @Snippet 222 public static Object instanceofDynamic(KlassPointer hub, Object object, Object trueValue, Object falseValue, @ConstantParameter boolean allowNull) { 223 if (probability(NOT_FREQUENT_PROBABILITY, object == null)) { 224 isNull.inc(); 225 if (allowNull) { 226 return trueValue; 227 } else { 228 return falseValue; 229 } 230 } 231 GuardingNode anchorNode = SnippetAnchorNode.anchor(); 232 KlassPointer objectHub = loadHubIntrinsic(PiNode.piCastNonNull(object, anchorNode)); 233 // The hub of a primitive type can be null => always return false in this case. 234 if (hub.isNull() || !checkUnknownSubType(hub, objectHub)) { 235 return falseValue; 236 } 237 return trueValue; 238 } 239 240 @Snippet 241 public static Object isAssignableFrom(Class<?> thisClass, Class<?> otherClass, Object trueValue, Object falseValue) { 242 if (BranchProbabilityNode.probability(BranchProbabilityNode.NOT_FREQUENT_PROBABILITY, otherClass == null)) { 243 DeoptimizeNode.deopt(DeoptimizationAction.InvalidateReprofile, DeoptimizationReason.NullCheckException); 244 return false; 245 } 246 GuardingNode anchorNode = SnippetAnchorNode.anchor(); 247 KlassPointer thisHub = ClassGetHubNode.readClass(thisClass, anchorNode); 248 KlassPointer otherHub = ClassGetHubNode.readClass(otherClass, anchorNode); 249 if (thisHub.isNull() || otherHub.isNull()) { 250 // primitive types, only true if equal. 251 return thisClass == otherClass ? trueValue : falseValue; 252 } 253 if (!TypeCheckSnippetUtils.checkUnknownSubType(thisHub, otherHub)) { 254 return falseValue; 255 } 256 return trueValue; 257 } 258 259 public static class Templates extends InstanceOfSnippetsTemplates { 260 261 private final SnippetInfo instanceofWithProfile = snippet(InstanceOfSnippets.class, "instanceofWithProfile"); 262 private final SnippetInfo instanceofExact = snippet(InstanceOfSnippets.class, "instanceofExact"); 263 private final SnippetInfo instanceofExactPIC = snippet(InstanceOfSnippets.class, "instanceofExactPIC"); 264 private final SnippetInfo instanceofPrimary = snippet(InstanceOfSnippets.class, "instanceofPrimary"); 265 private final SnippetInfo instanceofPrimaryPIC = snippet(InstanceOfSnippets.class, "instanceofPrimaryPIC"); 266 private final SnippetInfo instanceofSecondary = snippet(InstanceOfSnippets.class, "instanceofSecondary", SECONDARY_SUPER_CACHE_LOCATION); 267 private final SnippetInfo instanceofSecondaryPIC = snippet(InstanceOfSnippets.class, "instanceofSecondaryPIC", SECONDARY_SUPER_CACHE_LOCATION); 268 private final SnippetInfo instanceofDynamic = snippet(InstanceOfSnippets.class, "instanceofDynamic", SECONDARY_SUPER_CACHE_LOCATION); 269 private final SnippetInfo isAssignableFrom = snippet(InstanceOfSnippets.class, "isAssignableFrom", SECONDARY_SUPER_CACHE_LOCATION); 270 271 public Templates(HotSpotProviders providers, TargetDescription target) { 272 super(providers, providers.getSnippetReflection(), target); 273 } 274 275 @Override 276 protected Arguments makeArguments(InstanceOfUsageReplacer replacer, LoweringTool tool) { 277 if (replacer.instanceOf instanceof InstanceOfNode) { 278 InstanceOfNode instanceOf = (InstanceOfNode) replacer.instanceOf; 279 ValueNode object = instanceOf.getValue(); 280 Assumptions assumptions = instanceOf.graph().getAssumptions(); 281 282 JavaTypeProfile profile = instanceOf.profile(); 283 if (GeneratePIC.getValue()) { 284 // FIXME: We can't embed constants in hints. We can't really load them from GOT 285 // either. Hard problem. 286 profile = null; 287 } 288 TypeCheckHints hintInfo = new TypeCheckHints(instanceOf.type(), profile, assumptions, TypeCheckMinProfileHitProbability.getValue(), TypeCheckMaxHints.getValue()); 289 final HotSpotResolvedObjectType type = (HotSpotResolvedObjectType) instanceOf.type().getType(); 290 ConstantNode hub = ConstantNode.forConstant(KlassPointerStamp.klassNonNull(), type.klass(), providers.getMetaAccess(), instanceOf.graph()); 291 292 Arguments args; 293 294 StructuredGraph graph = instanceOf.graph(); 295 if (hintInfo.hintHitProbability >= 1.0 && hintInfo.exact == null) { 296 Hints hints = createHints(hintInfo, providers.getMetaAccess(), false, graph); 297 args = new Arguments(instanceofWithProfile, graph.getGuardsStage(), tool.getLoweringStage()); 298 args.add("object", object); 299 args.addVarargs("hints", KlassPointer.class, KlassPointerStamp.klassNonNull(), hints.hubs); 300 args.addVarargs("hintIsPositive", boolean.class, StampFactory.forKind(JavaKind.Boolean), hints.isPositive); 301 } else if (hintInfo.exact != null) { 302 SnippetInfo snippet = GeneratePIC.getValue() ? instanceofExactPIC : instanceofExact; 303 args = new Arguments(snippet, graph.getGuardsStage(), tool.getLoweringStage()); 304 args.add("object", object); 305 args.add("exactHub", ConstantNode.forConstant(KlassPointerStamp.klassNonNull(), ((HotSpotResolvedObjectType) hintInfo.exact).klass(), providers.getMetaAccess(), graph)); 306 } else if (type.isPrimaryType()) { 307 SnippetInfo snippet = GeneratePIC.getValue() ? instanceofPrimaryPIC : instanceofPrimary; 308 args = new Arguments(snippet, graph.getGuardsStage(), tool.getLoweringStage()); 309 args.add("hub", hub); 310 args.add("object", object); 311 args.addConst("superCheckOffset", type.superCheckOffset()); 312 } else { 313 Hints hints = createHints(hintInfo, providers.getMetaAccess(), false, graph); 314 SnippetInfo snippet = GeneratePIC.getValue() ? instanceofSecondaryPIC : instanceofSecondary; 315 args = new Arguments(snippet, graph.getGuardsStage(), tool.getLoweringStage()); 316 args.add("hub", hub); 317 args.add("object", object); 318 args.addVarargs("hints", KlassPointer.class, KlassPointerStamp.klassNonNull(), hints.hubs); 319 args.addVarargs("hintIsPositive", boolean.class, StampFactory.forKind(JavaKind.Boolean), hints.isPositive); 320 } 321 args.add("trueValue", replacer.trueValue); 322 args.add("falseValue", replacer.falseValue); 323 if (hintInfo.hintHitProbability >= 1.0 && hintInfo.exact == null) { 324 args.addConst("nullSeen", hintInfo.profile.getNullSeen() != TriState.FALSE); 325 } 326 return args; 327 } else if (replacer.instanceOf instanceof InstanceOfDynamicNode) { 328 InstanceOfDynamicNode instanceOf = (InstanceOfDynamicNode) replacer.instanceOf; 329 ValueNode object = instanceOf.getObject(); 330 331 Arguments args = new Arguments(instanceofDynamic, instanceOf.graph().getGuardsStage(), tool.getLoweringStage()); 332 args.add("hub", instanceOf.getMirrorOrHub()); 333 args.add("object", object); 334 args.add("trueValue", replacer.trueValue); 335 args.add("falseValue", replacer.falseValue); 336 args.addConst("allowNull", instanceOf.allowsNull()); 337 return args; 338 } else if (replacer.instanceOf instanceof ClassIsAssignableFromNode) { 339 ClassIsAssignableFromNode isAssignable = (ClassIsAssignableFromNode) replacer.instanceOf; 340 Arguments args = new Arguments(isAssignableFrom, isAssignable.graph().getGuardsStage(), tool.getLoweringStage()); 341 args.add("thisClass", isAssignable.getThisClass()); 342 args.add("otherClass", isAssignable.getOtherClass()); 343 args.add("trueValue", replacer.trueValue); 344 args.add("falseValue", replacer.falseValue); 345 return args; 346 } else { 347 throw GraalError.shouldNotReachHere(); 348 } 349 } 350 } 351 }