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