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
instanceofWithProfile(Object object, @VarargsParameter KlassPointer[] hints, @VarargsParameter boolean[] hintIsPositive, Object trueValue, Object falseValue, @ConstantParameter boolean nullSeen, @ConstantParameter Counters counters)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
instanceofExact(Object object, KlassPointer exactHub, Object trueValue, Object falseValue, @ConstantParameter Counters counters)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
instanceofPrimary(KlassPointer hub, Object object, @ConstantParameter int superCheckOffset, Object trueValue, Object falseValue, @ConstantParameter Counters counters)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
instanceofSecondary(KlassPointer hub, Object object, @VarargsParameter KlassPointer[] hints, @VarargsParameter boolean[] hintIsPositive, Object trueValue, Object falseValue, @ConstantParameter Counters counters)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
instanceofDynamic(KlassPointer hub, Object object, Object trueValue, Object falseValue, @ConstantParameter boolean allowNull, @ConstantParameter Counters counters)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
isAssignableFrom(@onNullParameter Class<?> thisClassNonNull, Class<?> otherClass, Object trueValue, Object falseValue, @ConstantParameter Counters counters)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 
Templates(OptionValues options, Iterable<DebugHandlersFactory> factories, SnippetCounter.Group.Factory factory, HotSpotProviders providers, TargetDescription target)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
makeArguments(InstanceOfUsageReplacer replacer, LoweringTool tool)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 }
351