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