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 }