/*

 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

 *

 * This code is free software; you can redistribute it and/or modify it

 * under the terms of the GNU General Public License version 2 only, as

 * published by the Free Software Foundation.

 *

 * This code is distributed in the hope that it will be useful, but WITHOUT

 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

 * version 2 for more details (a copy is included in the LICENSE file that

 * accompanied this code).

 *

 * You should have received a copy of the GNU General Public License version

 * 2 along with this work; if not, write to the Free Software Foundation,

 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

 *

 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

 * or visit www.oracle.com if you need additional information or have any

 * questions.

 */

package org.graalvm.compiler.hotspot.replacements;

import static jdk.vm.ci.meta.DeoptimizationAction.InvalidateReprofile;

import static jdk.vm.ci.meta.DeoptimizationReason.OptimizedTypeCheckViolated;

import static org.graalvm.compiler.core.common.GraalOptions.GeneratePIC;

import static org.graalvm.compiler.hotspot.replacements.HotSpotReplacementsUtil.PRIMARY_SUPERS_LOCATION;

import static org.graalvm.compiler.hotspot.replacements.HotSpotReplacementsUtil.SECONDARY_SUPER_CACHE_LOCATION;

import static org.graalvm.compiler.hotspot.replacements.HotSpotReplacementsUtil.loadHubIntrinsic;

import static org.graalvm.compiler.hotspot.replacements.HotspotSnippetsOptions.TypeCheckMaxHints;

import static org.graalvm.compiler.hotspot.replacements.HotspotSnippetsOptions.TypeCheckMinProfileHitProbability;

import static org.graalvm.compiler.hotspot.replacements.TypeCheckSnippetUtils.checkSecondarySubType;

import static org.graalvm.compiler.hotspot.replacements.TypeCheckSnippetUtils.checkUnknownSubType;

import static org.graalvm.compiler.hotspot.replacements.TypeCheckSnippetUtils.createHints;

import static org.graalvm.compiler.nodes.extended.BranchProbabilityNode.LIKELY_PROBABILITY;

import static org.graalvm.compiler.nodes.extended.BranchProbabilityNode.NOT_FREQUENT_PROBABILITY;

import static org.graalvm.compiler.nodes.extended.BranchProbabilityNode.NOT_LIKELY_PROBABILITY;

import static org.graalvm.compiler.nodes.extended.BranchProbabilityNode.probability;

import org.graalvm.compiler.api.replacements.Snippet;

import org.graalvm.compiler.api.replacements.Snippet.ConstantParameter;

import org.graalvm.compiler.api.replacements.Snippet.NonNullParameter;

import org.graalvm.compiler.api.replacements.Snippet.VarargsParameter;

import org.graalvm.compiler.core.common.type.ObjectStamp;

import org.graalvm.compiler.core.common.type.StampFactory;

import org.graalvm.compiler.debug.DebugHandlersFactory;

import org.graalvm.compiler.debug.GraalError;

import org.graalvm.compiler.hotspot.meta.HotSpotProviders;

import org.graalvm.compiler.hotspot.nodes.type.KlassPointerStamp;

import org.graalvm.compiler.hotspot.replacements.TypeCheckSnippetUtils.Counters;

import org.graalvm.compiler.hotspot.replacements.TypeCheckSnippetUtils.Hints;

import org.graalvm.compiler.hotspot.word.KlassPointer;

import org.graalvm.compiler.nodes.ConstantNode;

import org.graalvm.compiler.nodes.DeoptimizeNode;

import org.graalvm.compiler.nodes.NodeView;

import org.graalvm.compiler.nodes.PiNode;

import org.graalvm.compiler.nodes.SnippetAnchorNode;

import org.graalvm.compiler.nodes.StructuredGraph;

import org.graalvm.compiler.nodes.TypeCheckHints;

import org.graalvm.compiler.nodes.ValueNode;

import org.graalvm.compiler.nodes.extended.BranchProbabilityNode;

import org.graalvm.compiler.nodes.extended.GuardingNode;

import org.graalvm.compiler.nodes.java.ClassIsAssignableFromNode;

import org.graalvm.compiler.nodes.java.InstanceOfDynamicNode;

import org.graalvm.compiler.nodes.java.InstanceOfNode;

import org.graalvm.compiler.nodes.spi.LoweringTool;

import org.graalvm.compiler.options.OptionValues;

import org.graalvm.compiler.replacements.InstanceOfSnippetsTemplates;

import org.graalvm.compiler.replacements.SnippetCounter;

import org.graalvm.compiler.replacements.SnippetTemplate.Arguments;

import org.graalvm.compiler.replacements.SnippetTemplate.SnippetInfo;

import org.graalvm.compiler.replacements.Snippets;

import org.graalvm.compiler.replacements.nodes.ExplodeLoopNode;

import jdk.vm.ci.code.TargetDescription;

import jdk.vm.ci.hotspot.HotSpotResolvedObjectType;

import jdk.vm.ci.meta.Assumptions;

import jdk.vm.ci.meta.DeoptimizationAction;

import jdk.vm.ci.meta.DeoptimizationReason;

import jdk.vm.ci.meta.JavaKind;

import jdk.vm.ci.meta.JavaTypeProfile;

import jdk.vm.ci.meta.TriState;

/**

 * Snippets used for implementing the type test of an instanceof instruction. Since instanceof is a

 * floating node, it is lowered separately for each of its usages.

 *

 * The type tests implemented are described in the paper

 * <a href="http://dl.acm.org/citation.cfm?id=583821"> Fast subtype checking in the HotSpot JVM</a>

 * by Cliff Click and John Rose.

 */

public class InstanceOfSnippets implements Snippets {

    /**

     * A test against a set of hints derived from a profile with 100% precise coverage of seen

     * types. This snippet deoptimizes on hint miss paths.

     */

    @Snippet

    public static Object instanceofWithProfile(Object object, @VarargsParameter KlassPointer[] hints, @VarargsParameter boolean[] hintIsPositive, Object trueValue, Object falseValue,

                    @ConstantParameter boolean nullSeen, @ConstantParameter Counters counters) {

        if (probability(NOT_FREQUENT_PROBABILITY, object == null)) {

            counters.isNull.inc();

            if (!nullSeen) {

                // See comment below for other deoptimization path; the

                // same reasoning applies here.

                DeoptimizeNode.deopt(InvalidateReprofile, OptimizedTypeCheckViolated);

            }

            return falseValue;

        }

        GuardingNode anchorNode = SnippetAnchorNode.anchor();

        KlassPointer objectHub = loadHubIntrinsic(PiNode.piCastNonNull(object, anchorNode));

        // if we get an exact match: succeed immediately

        ExplodeLoopNode.explodeLoop();

        for (int i = 0; i < hints.length; i++) {

            KlassPointer hintHub = hints[i];

            boolean positive = hintIsPositive[i];

            if (probability(LIKELY_PROBABILITY, hintHub.equal(objectHub))) {

                counters.hintsHit.inc();

                return positive ? trueValue : falseValue;

            }

            counters.hintsMiss.inc();

        }

        // This maybe just be a rare event but it might also indicate a phase change

        // in the application. Ideally we want to use DeoptimizationAction.None for

        // the former but the cost is too high if indeed it is the latter. As such,

        // we defensively opt for InvalidateReprofile.

        DeoptimizeNode.deopt(DeoptimizationAction.InvalidateReprofile, OptimizedTypeCheckViolated);

        return falseValue;

    }

    /**

     * A test against a final type.

     */

    @Snippet

    public static Object instanceofExact(Object object, KlassPointer exactHub, Object trueValue, Object falseValue, @ConstantParameter Counters counters) {

        if (probability(NOT_FREQUENT_PROBABILITY, object == null)) {

            counters.isNull.inc();

            return falseValue;

        }

        GuardingNode anchorNode = SnippetAnchorNode.anchor();

        KlassPointer objectHub = loadHubIntrinsic(PiNode.piCastNonNull(object, anchorNode));

        if (probability(LIKELY_PROBABILITY, objectHub.notEqual(exactHub))) {

            counters.exactMiss.inc();

            return falseValue;

        }

        counters.exactHit.inc();

        return trueValue;

    }

    /**

     * A test against a primary type.

     */

    @Snippet

    public static Object instanceofPrimary(KlassPointer hub, Object object, @ConstantParameter int superCheckOffset, Object trueValue, Object falseValue, @ConstantParameter Counters counters) {

        if (probability(NOT_FREQUENT_PROBABILITY, object == null)) {

            counters.isNull.inc();

            return falseValue;

        }

        GuardingNode anchorNode = SnippetAnchorNode.anchor();

        KlassPointer objectHub = loadHubIntrinsic(PiNode.piCastNonNull(object, anchorNode));

        if (probability(NOT_LIKELY_PROBABILITY, objectHub.readKlassPointer(superCheckOffset, PRIMARY_SUPERS_LOCATION).notEqual(hub))) {

            counters.displayMiss.inc();

            return falseValue;

        }

        counters.displayHit.inc();

        return trueValue;

    }

    /**

     * A test against a restricted secondary type type.

     */

    @Snippet

    public static Object instanceofSecondary(KlassPointer hub, Object object, @VarargsParameter KlassPointer[] hints, @VarargsParameter boolean[] hintIsPositive, Object trueValue, Object falseValue,

                    @ConstantParameter Counters counters) {

        if (probability(NOT_FREQUENT_PROBABILITY, object == null)) {

            counters.isNull.inc();

            return falseValue;

        }

        GuardingNode anchorNode = SnippetAnchorNode.anchor();

        KlassPointer objectHub = loadHubIntrinsic(PiNode.piCastNonNull(object, anchorNode));

        // if we get an exact match: succeed immediately

        ExplodeLoopNode.explodeLoop();

        for (int i = 0; i < hints.length; i++) {

            KlassPointer hintHub = hints[i];

            boolean positive = hintIsPositive[i];

            if (probability(NOT_FREQUENT_PROBABILITY, hintHub.equal(objectHub))) {

                counters.hintsHit.inc();

                return positive ? trueValue : falseValue;

            }

        }

        counters.hintsMiss.inc();

        if (!checkSecondarySubType(hub, objectHub, counters)) {

            return falseValue;

        }

        return trueValue;

    }

    /**

     * Type test used when the type being tested against is not known at compile time.

     */

    @Snippet

    public static Object instanceofDynamic(KlassPointer hub, Object object, Object trueValue, Object falseValue, @ConstantParameter boolean allowNull, @ConstantParameter Counters counters) {

        if (probability(NOT_FREQUENT_PROBABILITY, object == null)) {

            counters.isNull.inc();

            if (allowNull) {

                return trueValue;

            } else {

                return falseValue;

            }

        }

        GuardingNode anchorNode = SnippetAnchorNode.anchor();

        KlassPointer nonNullObjectHub = loadHubIntrinsic(PiNode.piCastNonNull(object, anchorNode));

        // The hub of a primitive type can be null => always return false in this case.

        if (BranchProbabilityNode.probability(BranchProbabilityNode.FAST_PATH_PROBABILITY, !hub.isNull())) {

            if (checkUnknownSubType(hub, nonNullObjectHub, counters)) {

                return trueValue;

            }

        }

        return falseValue;

    }

    @Snippet

    public static Object isAssignableFrom(@NonNullParameter Class<?> thisClassNonNull, Class<?> otherClass, Object trueValue, Object falseValue, @ConstantParameter Counters counters) {

        if (otherClass == null) {

            DeoptimizeNode.deopt(DeoptimizationAction.InvalidateReprofile, DeoptimizationReason.NullCheckException);

            return false;

        }

        GuardingNode anchorNode = SnippetAnchorNode.anchor();

        Class<?> otherClassNonNull = PiNode.piCastNonNullClass(otherClass, anchorNode);

        if (BranchProbabilityNode.probability(BranchProbabilityNode.NOT_LIKELY_PROBABILITY, thisClassNonNull == otherClassNonNull)) {

            return trueValue;

        }

        KlassPointer thisHub = ClassGetHubNode.readClass(thisClassNonNull);

        KlassPointer otherHub = ClassGetHubNode.readClass(otherClassNonNull);

        if (BranchProbabilityNode.probability(BranchProbabilityNode.FAST_PATH_PROBABILITY, !thisHub.isNull())) {

            if (BranchProbabilityNode.probability(BranchProbabilityNode.FAST_PATH_PROBABILITY, !otherHub.isNull())) {

                GuardingNode guardNonNull = SnippetAnchorNode.anchor();

                KlassPointer nonNullOtherHub = ClassGetHubNode.piCastNonNull(otherHub, guardNonNull);

                if (TypeCheckSnippetUtils.checkUnknownSubType(thisHub, nonNullOtherHub, counters)) {

                    return trueValue;

                }

            }

        }

        // If either hub is null, one of them is a primitive type and given that the class is not

        // equal, return false.

        return falseValue;

    }

    public static class Templates extends InstanceOfSnippetsTemplates {

        private final SnippetInfo instanceofWithProfile = snippet(InstanceOfSnippets.class, "instanceofWithProfile");

        private final SnippetInfo instanceofExact = snippet(InstanceOfSnippets.class, "instanceofExact");

        private final SnippetInfo instanceofPrimary = snippet(InstanceOfSnippets.class, "instanceofPrimary");

        private final SnippetInfo instanceofSecondary = snippet(InstanceOfSnippets.class, "instanceofSecondary", SECONDARY_SUPER_CACHE_LOCATION);

        private final SnippetInfo instanceofDynamic = snippet(InstanceOfSnippets.class, "instanceofDynamic", SECONDARY_SUPER_CACHE_LOCATION);

        private final SnippetInfo isAssignableFrom = snippet(InstanceOfSnippets.class, "isAssignableFrom", SECONDARY_SUPER_CACHE_LOCATION);

        private final Counters counters;

        public Templates(OptionValues options, Iterable<DebugHandlersFactory> factories, SnippetCounter.Group.Factory factory, HotSpotProviders providers, TargetDescription target) {

            super(options, factories, providers, providers.getSnippetReflection(), target);

            this.counters = new Counters(factory);

        }

        @Override

        protected Arguments makeArguments(InstanceOfUsageReplacer replacer, LoweringTool tool) {

            if (replacer.instanceOf instanceof InstanceOfNode) {

                InstanceOfNode instanceOf = (InstanceOfNode) replacer.instanceOf;

                ValueNode object = instanceOf.getValue();

                Assumptions assumptions = instanceOf.graph().getAssumptions();

                OptionValues localOptions = instanceOf.getOptions();

                JavaTypeProfile profile = instanceOf.profile();

                if (GeneratePIC.getValue(localOptions)) {

                    // FIXME: We can't embed constants in hints. We can't really load them from GOT

                    // either. Hard problem.

                    profile = null;

                }

                TypeCheckHints hintInfo = new TypeCheckHints(instanceOf.type(), profile, assumptions, TypeCheckMinProfileHitProbability.getValue(localOptions),

                                TypeCheckMaxHints.getValue(localOptions));

                final HotSpotResolvedObjectType type = (HotSpotResolvedObjectType) instanceOf.type().getType();

                ConstantNode hub = ConstantNode.forConstant(KlassPointerStamp.klassNonNull(), type.klass(), providers.getMetaAccess(), instanceOf.graph());

                Arguments args;

                StructuredGraph graph = instanceOf.graph();

                if (hintInfo.hintHitProbability >= 1.0 && hintInfo.exact == null) {

                    Hints hints = createHints(hintInfo, providers.getMetaAccess(), false, graph);

                    args = new Arguments(instanceofWithProfile, graph.getGuardsStage(), tool.getLoweringStage());

                    args.add("object", object);

                    args.addVarargs("hints", KlassPointer.class, KlassPointerStamp.klassNonNull(), hints.hubs);

                    args.addVarargs("hintIsPositive", boolean.class, StampFactory.forKind(JavaKind.Boolean), hints.isPositive);

                } else if (hintInfo.exact != null) {

                    args = new Arguments(instanceofExact, graph.getGuardsStage(), tool.getLoweringStage());

                    args.add("object", object);

                    args.add("exactHub", ConstantNode.forConstant(KlassPointerStamp.klassNonNull(), ((HotSpotResolvedObjectType) hintInfo.exact).klass(), providers.getMetaAccess(), graph));

                } else if (type.isPrimaryType()) {

                    args = new Arguments(instanceofPrimary, graph.getGuardsStage(), tool.getLoweringStage());

                    args.add("hub", hub);

                    args.add("object", object);

                    args.addConst("superCheckOffset", type.superCheckOffset());

                } else {

                    Hints hints = createHints(hintInfo, providers.getMetaAccess(), false, graph);

                    args = new Arguments(instanceofSecondary, graph.getGuardsStage(), tool.getLoweringStage());

                    args.add("hub", hub);

                    args.add("object", object);

                    args.addVarargs("hints", KlassPointer.class, KlassPointerStamp.klassNonNull(), hints.hubs);

                    args.addVarargs("hintIsPositive", boolean.class, StampFactory.forKind(JavaKind.Boolean), hints.isPositive);

                }

                args.add("trueValue", replacer.trueValue);

                args.add("falseValue", replacer.falseValue);

                if (hintInfo.hintHitProbability >= 1.0 && hintInfo.exact == null) {

                    args.addConst("nullSeen", hintInfo.profile.getNullSeen() != TriState.FALSE);

                }

                args.addConst("counters", counters);

                return args;

            } else if (replacer.instanceOf instanceof InstanceOfDynamicNode) {

                InstanceOfDynamicNode instanceOf = (InstanceOfDynamicNode) replacer.instanceOf;

                ValueNode object = instanceOf.getObject();

                Arguments args = new Arguments(instanceofDynamic, instanceOf.graph().getGuardsStage(), tool.getLoweringStage());

                args.add("hub", instanceOf.getMirrorOrHub());

                args.add("object", object);

                args.add("trueValue", replacer.trueValue);

                args.add("falseValue", replacer.falseValue);

                args.addConst("allowNull", instanceOf.allowsNull());

                args.addConst("counters", counters);

                return args;

            } else if (replacer.instanceOf instanceof ClassIsAssignableFromNode) {

                ClassIsAssignableFromNode isAssignable = (ClassIsAssignableFromNode) replacer.instanceOf;

                Arguments args = new Arguments(isAssignableFrom, isAssignable.graph().getGuardsStage(), tool.getLoweringStage());

                assert ((ObjectStamp) isAssignable.getThisClass().stamp(NodeView.DEFAULT)).nonNull();

                args.add("thisClassNonNull", isAssignable.getThisClass());

                args.add("otherClass", isAssignable.getOtherClass());

                args.add("trueValue", replacer.trueValue);

                args.add("falseValue", replacer.falseValue);

                args.addConst("counters", counters);

                return args;

            } else {

                throw GraalError.shouldNotReachHere();

            }

        }

    }

}