Source code

001/*
002 * Copyright (c) 2012, 2015, Oracle and/or its affiliates. All rights reserved.
003 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004 *
005 * This code is free software; you can redistribute it and/or modify it
006 * under the terms of the GNU General Public License version 2 only, as
007 * published by the Free Software Foundation.
008 *
009 * This code is distributed in the hope that it will be useful, but WITHOUT
010 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
011 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
012 * version 2 for more details (a copy is included in the LICENSE file that
013 * accompanied this code).
014 *
015 * You should have received a copy of the GNU General Public License version
016 * 2 along with this work; if not, write to the Free Software Foundation,
017 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
018 *
019 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
020 * or visit www.oracle.com if you need additional information or have any
021 * questions.
022 */
023package com.oracle.graal.hotspot.replacements;
024
025import jdk.internal.jvmci.code.*;
026import jdk.internal.jvmci.common.*;
027import jdk.internal.jvmci.hotspot.*;
028import jdk.internal.jvmci.meta.*;
029import jdk.internal.jvmci.options.*;
030import static com.oracle.graal.hotspot.replacements.HotSpotReplacementsUtil.*;
031import static com.oracle.graal.hotspot.replacements.InstanceOfSnippets.Options.*;
032import static com.oracle.graal.hotspot.replacements.TypeCheckSnippetUtils.*;
033import static com.oracle.graal.nodes.extended.BranchProbabilityNode.*;
034import static jdk.internal.jvmci.meta.DeoptimizationAction.*;
035import static jdk.internal.jvmci.meta.DeoptimizationReason.*;
036
037import com.oracle.graal.compiler.common.type.*;
038import com.oracle.graal.hotspot.meta.*;
039import com.oracle.graal.hotspot.nodes.*;
040import com.oracle.graal.hotspot.replacements.TypeCheckSnippetUtils.Hints;
041import com.oracle.graal.hotspot.word.*;
042import com.oracle.graal.nodes.*;
043import com.oracle.graal.nodes.extended.*;
044import com.oracle.graal.nodes.java.*;
045import com.oracle.graal.nodes.spi.*;
046import com.oracle.graal.replacements.*;
047import com.oracle.graal.replacements.Snippet.ConstantParameter;
048import com.oracle.graal.replacements.Snippet.VarargsParameter;
049import com.oracle.graal.replacements.SnippetTemplate.Arguments;
050import com.oracle.graal.replacements.SnippetTemplate.SnippetInfo;
051import com.oracle.graal.replacements.nodes.*;
052
053/**
054 * Snippets used for implementing the type test of an instanceof instruction. Since instanceof is a
055 * floating node, it is lowered separately for each of its usages.
056 *
057 * The type tests implemented are described in the paper <a
058 * href="http://dl.acm.org/citation.cfm?id=583821"> Fast subtype checking in the HotSpot JVM</a> by
059 * Cliff Click and John Rose.
060 */
061public class InstanceOfSnippets implements Snippets {
062
063    /**
064     * A test against a set of hints derived from a profile with 100% precise coverage of seen
065     * types. This snippet deoptimizes on hint miss paths.
066     */
067    @Snippet
068    public static Object instanceofWithProfile(Object object, @VarargsParameter KlassPointer[] hints, @VarargsParameter boolean[] hintIsPositive, Object trueValue, Object falseValue,
069                    @ConstantParameter boolean nullSeen) {
070        if (probability(NOT_FREQUENT_PROBABILITY, object == null)) {
071            isNull.inc();
072            if (!nullSeen) {
073                // See comment below for other deoptimization path; the
074                // same reasoning applies here.
075                DeoptimizeNode.deopt(InvalidateReprofile, OptimizedTypeCheckViolated);
076            }
077            return falseValue;
078        }
079        GuardingNode anchorNode = SnippetAnchorNode.anchor();
080        KlassPointer objectHub = loadHubIntrinsic(object, anchorNode);
081        // if we get an exact match: succeed immediately
082        ExplodeLoopNode.explodeLoop();
083        for (int i = 0; i < hints.length; i++) {
084            KlassPointer hintHub = hints[i];
085            boolean positive = hintIsPositive[i];
086            if (probability(LIKELY_PROBABILITY, hintHub.equal(objectHub))) {
087                hintsHit.inc();
088                return positive ? trueValue : falseValue;
089            }
090            hintsMiss.inc();
091        }
092        // This maybe just be a rare event but it might also indicate a phase change
093        // in the application. Ideally we want to use DeoptimizationAction.None for
094        // the former but the cost is too high if indeed it is the latter. As such,
095        // we defensively opt for InvalidateReprofile.
096        DeoptimizeNode.deopt(DeoptimizationAction.InvalidateReprofile, OptimizedTypeCheckViolated);
097        return falseValue;
098    }
099
100    /**
101     * A test against a final type.
102     */
103    @Snippet
104    public static Object instanceofExact(Object object, KlassPointer exactHub, Object trueValue, Object falseValue) {
105        if (probability(NOT_FREQUENT_PROBABILITY, object == null)) {
106            isNull.inc();
107            return falseValue;
108        }
109        GuardingNode anchorNode = SnippetAnchorNode.anchor();
110        KlassPointer objectHub = loadHubIntrinsic(object, anchorNode);
111        if (probability(LIKELY_PROBABILITY, objectHub.notEqual(exactHub))) {
112            exactMiss.inc();
113            return falseValue;
114        }
115        exactHit.inc();
116        return trueValue;
117    }
118
119    /**
120     * A test against a primary type.
121     */
122    @Snippet
123    public static Object instanceofPrimary(KlassPointer hub, Object object, @ConstantParameter int superCheckOffset, Object trueValue, Object falseValue) {
124        if (probability(NOT_FREQUENT_PROBABILITY, object == null)) {
125            isNull.inc();
126            return falseValue;
127        }
128        GuardingNode anchorNode = SnippetAnchorNode.anchor();
129        KlassPointer objectHub = loadHubIntrinsic(object, anchorNode);
130        if (probability(NOT_LIKELY_PROBABILITY, objectHub.readKlassPointer(superCheckOffset, PRIMARY_SUPERS_LOCATION).notEqual(hub))) {
131            displayMiss.inc();
132            return falseValue;
133        }
134        displayHit.inc();
135        return trueValue;
136    }
137
138    /**
139     * A test against a restricted secondary type type.
140     */
141    @Snippet
142    public static Object instanceofSecondary(KlassPointer hub, Object object, @VarargsParameter KlassPointer[] hints, @VarargsParameter boolean[] hintIsPositive, Object trueValue, Object falseValue) {
143        if (probability(NOT_FREQUENT_PROBABILITY, object == null)) {
144            isNull.inc();
145            return falseValue;
146        }
147        GuardingNode anchorNode = SnippetAnchorNode.anchor();
148        KlassPointer objectHub = loadHubIntrinsic(object, anchorNode);
149        // if we get an exact match: succeed immediately
150        ExplodeLoopNode.explodeLoop();
151        for (int i = 0; i < hints.length; i++) {
152            KlassPointer hintHub = hints[i];
153            boolean positive = hintIsPositive[i];
154            if (probability(NOT_FREQUENT_PROBABILITY, hintHub.equal(objectHub))) {
155                hintsHit.inc();
156                return positive ? trueValue : falseValue;
157            }
158        }
159        hintsMiss.inc();
160        if (!checkSecondarySubType(hub, objectHub)) {
161            return falseValue;
162        }
163        return trueValue;
164    }
165
166    /**
167     * Type test used when the type being tested against is not known at compile time.
168     */
169    @Snippet
170    public static Object instanceofDynamic(Class<?> mirror, Object object, Object trueValue, Object falseValue) {
171        if (probability(NOT_FREQUENT_PROBABILITY, object == null)) {
172            isNull.inc();
173            return falseValue;
174        }
175        GuardingNode anchorNode = SnippetAnchorNode.anchor();
176        KlassPointer hub = ClassGetHubNode.readClass(mirror, anchorNode);
177        KlassPointer objectHub = loadHubIntrinsic(object, anchorNode);
178        if (hub.isNull() || !checkUnknownSubType(hub, objectHub)) {
179            return falseValue;
180        }
181        return trueValue;
182    }
183
184    @Snippet
185    public static Object isAssignableFrom(Class<?> thisClass, Class<?> otherClass, Object trueValue, Object falseValue) {
186        if (BranchProbabilityNode.probability(BranchProbabilityNode.NOT_FREQUENT_PROBABILITY, otherClass == null)) {
187            DeoptimizeNode.deopt(DeoptimizationAction.InvalidateReprofile, DeoptimizationReason.NullCheckException);
188            return false;
189        }
190        GuardingNode anchorNode = SnippetAnchorNode.anchor();
191        KlassPointer thisHub = ClassGetHubNode.readClass(thisClass, anchorNode);
192        KlassPointer otherHub = ClassGetHubNode.readClass(otherClass, anchorNode);
193        if (thisHub.isNull() || otherHub.isNull()) {
194            // primitive types, only true if equal.
195            return thisClass == otherClass ? trueValue : falseValue;
196        }
197        if (!TypeCheckSnippetUtils.checkUnknownSubType(thisHub, otherHub)) {
198            return falseValue;
199        }
200        return trueValue;
201    }
202
203    static class Options {
204
205        // @formatter:off
206        @Option(help = "If the probability that a type check will hit one the profiled types (up to " +
207                       "TypeCheckMaxHints) is below this value, the type check will be compiled without profiling info", type = OptionType.Expert)
208        static final OptionValue<Double> TypeCheckMinProfileHitProbability = new OptionValue<>(0.5);
209
210        @Option(help = "The maximum number of profiled types that will be used when compiling a profiled type check. " +
211                        "Note that TypeCheckMinProfileHitProbability also influences whether profiling info is used in compiled type checks.", type = OptionType.Expert)
212        static final OptionValue<Integer> TypeCheckMaxHints = new OptionValue<>(2);
213        // @formatter:on
214    }
215
216    public static class Templates extends InstanceOfSnippetsTemplates {
217
218        private final SnippetInfo instanceofWithProfile = snippet(InstanceOfSnippets.class, "instanceofWithProfile");
219        private final SnippetInfo instanceofExact = snippet(InstanceOfSnippets.class, "instanceofExact");
220        private final SnippetInfo instanceofPrimary = snippet(InstanceOfSnippets.class, "instanceofPrimary");
221        private final SnippetInfo instanceofSecondary = snippet(InstanceOfSnippets.class, "instanceofSecondary", SECONDARY_SUPER_CACHE_LOCATION);
222        private final SnippetInfo instanceofDynamic = snippet(InstanceOfSnippets.class, "instanceofDynamic", SECONDARY_SUPER_CACHE_LOCATION);
223        private final SnippetInfo isAssignableFrom = snippet(InstanceOfSnippets.class, "isAssignableFrom", SECONDARY_SUPER_CACHE_LOCATION);
224
225        public Templates(HotSpotProviders providers, TargetDescription target) {
226            super(providers, providers.getSnippetReflection(), target);
227        }
228
229        @Override
230        protected Arguments makeArguments(InstanceOfUsageReplacer replacer, LoweringTool tool) {
231            Stamp hubStamp = tool.getStampProvider().createHubStamp(true);
232            if (replacer.instanceOf instanceof InstanceOfNode) {
233                InstanceOfNode instanceOf = (InstanceOfNode) replacer.instanceOf;
234                ValueNode object = instanceOf.getValue();
235                Assumptions assumptions = instanceOf.graph().getAssumptions();
236                TypeCheckHints hintInfo = new TypeCheckHints(instanceOf.type(), instanceOf.profile(), assumptions, TypeCheckMinProfileHitProbability.getValue(), TypeCheckMaxHints.getValue());
237                final HotSpotResolvedObjectType type = (HotSpotResolvedObjectType) instanceOf.type();
238                ConstantNode hub = ConstantNode.forConstant(hubStamp, type.klass(), providers.getMetaAccess(), instanceOf.graph());
239
240                Arguments args;
241
242                StructuredGraph graph = instanceOf.graph();
243                if (hintInfo.hintHitProbability >= 1.0 && hintInfo.exact == null) {
244                    Hints hints = createHints(hintInfo, providers.getMetaAccess(), false, graph, tool);
245                    args = new Arguments(instanceofWithProfile, graph.getGuardsStage(), tool.getLoweringStage());
246                    args.add("object", object);
247                    args.addVarargs("hints", KlassPointer.class, hubStamp, hints.hubs);
248                    args.addVarargs("hintIsPositive", boolean.class, StampFactory.forKind(Kind.Boolean), hints.isPositive);
249                } else if (hintInfo.exact != null) {
250                    args = new Arguments(instanceofExact, graph.getGuardsStage(), tool.getLoweringStage());
251                    args.add("object", object);
252                    args.add("exactHub", ConstantNode.forConstant(hubStamp, ((HotSpotResolvedObjectType) hintInfo.exact).klass(), providers.getMetaAccess(), graph));
253                } else if (type.isPrimaryType()) {
254                    args = new Arguments(instanceofPrimary, graph.getGuardsStage(), tool.getLoweringStage());
255                    args.add("hub", hub);
256                    args.add("object", object);
257                    args.addConst("superCheckOffset", type.superCheckOffset());
258                } else {
259                    Hints hints = createHints(hintInfo, providers.getMetaAccess(), false, graph, tool);
260                    args = new Arguments(instanceofSecondary, graph.getGuardsStage(), tool.getLoweringStage());
261                    args.add("hub", hub);
262                    args.add("object", object);
263                    args.addVarargs("hints", KlassPointer.class, hubStamp, hints.hubs);
264                    args.addVarargs("hintIsPositive", boolean.class, StampFactory.forKind(Kind.Boolean), hints.isPositive);
265                }
266                args.add("trueValue", replacer.trueValue);
267                args.add("falseValue", replacer.falseValue);
268                if (hintInfo.hintHitProbability >= 1.0 && hintInfo.exact == null) {
269                    args.addConst("nullSeen", hintInfo.profile.getNullSeen() != TriState.FALSE);
270                }
271                return args;
272
273            } else if (replacer.instanceOf instanceof TypeCheckNode) {
274                TypeCheckNode typeCheck = (TypeCheckNode) replacer.instanceOf;
275                ValueNode object = typeCheck.getValue();
276                Arguments args = new Arguments(instanceofExact, typeCheck.graph().getGuardsStage(), tool.getLoweringStage());
277                args.add("object", object);
278                args.add("exactHub", ConstantNode.forConstant(hubStamp, ((HotSpotResolvedObjectType) typeCheck.type()).klass(), providers.getMetaAccess(), typeCheck.graph()));
279                args.add("trueValue", replacer.trueValue);
280                args.add("falseValue", replacer.falseValue);
281                return args;
282            } else if (replacer.instanceOf instanceof InstanceOfDynamicNode) {
283                InstanceOfDynamicNode instanceOf = (InstanceOfDynamicNode) replacer.instanceOf;
284                ValueNode object = instanceOf.object();
285
286                Arguments args = new Arguments(instanceofDynamic, instanceOf.graph().getGuardsStage(), tool.getLoweringStage());
287                args.add("mirror", instanceOf.mirror());
288                args.add("object", object);
289                args.add("trueValue", replacer.trueValue);
290                args.add("falseValue", replacer.falseValue);
291                return args;
292            } else if (replacer.instanceOf instanceof ClassIsAssignableFromNode) {
293                ClassIsAssignableFromNode isAssignable = (ClassIsAssignableFromNode) replacer.instanceOf;
294                Arguments args = new Arguments(isAssignableFrom, isAssignable.graph().getGuardsStage(), tool.getLoweringStage());
295                args.add("thisClass", isAssignable.getThisClass());
296                args.add("otherClass", isAssignable.getOtherClass());
297                args.add("trueValue", replacer.trueValue);
298                args.add("falseValue", replacer.falseValue);
299                return args;
300            } else {
301                throw JVMCIError.shouldNotReachHere();
302            }
303        }
304    }
305}