001/*
002 * Copyright (c) 2012, 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.nodes;
024
025import java.util.*;
026
027import jdk.internal.jvmci.meta.*;
028import jdk.internal.jvmci.meta.Assumptions.*;
029import jdk.internal.jvmci.meta.JavaTypeProfile.*;
030
031/**
032 * Utility for deriving hint types for a type check instruction (e.g. checkcast or instanceof) based
033 * on the target type of the check and any profiling information available for the instruction.
034 */
035public class TypeCheckHints {
036
037    /**
038     * A receiver type profiled in a type check instruction.
039     */
040    public static class Hint {
041
042        /**
043         * A type seen while profiling a type check instruction.
044         */
045        public final ResolvedJavaType type;
046
047        /**
048         * Specifies if {@link #type} is a sub-type of the checked type.
049         */
050        public final boolean positive;
051
052        Hint(ResolvedJavaType type, boolean positive) {
053            this.type = type;
054            this.positive = positive;
055        }
056    }
057
058    private static final Hint[] NO_HINTS = {};
059
060    /**
061     * If non-null, then this is the only type that could pass the type check because the target of
062     * the type check is a final class or has been speculated to be a final class and this value is
063     * the only concrete subclass of the target type.
064     */
065    public final ResolvedJavaType exact;
066
067    /**
068     * The most likely types that the type check instruction will see.
069     */
070    public final Hint[] hints;
071
072    /**
073     * The profile from which this information was derived.
074     */
075    public final JavaTypeProfile profile;
076
077    /**
078     * The total probability that the type check will hit one of the types in {@link #hints}.
079     */
080    public final double hintHitProbability;
081
082    /**
083     * Derives hint information for use when generating the code for a type check instruction.
084     *
085     * @param targetType the target type of the type check
086     * @param profile the profiling information available for the instruction (if any)
087     * @param assumptions the object in which speculations are recorded. This is null if
088     *            speculations are not supported.
089     * @param minHintHitProbability if the probability that the type check will hit one of the
090     *            profiled types (up to {@code maxHints}) is below this value, then {@link #hints}
091     *            will be null
092     * @param maxHints the maximum length of {@link #hints}
093     */
094    public TypeCheckHints(ResolvedJavaType targetType, JavaTypeProfile profile, Assumptions assumptions, double minHintHitProbability, int maxHints) {
095        this.profile = profile;
096        if (targetType != null && targetType.isLeaf()) {
097            exact = targetType;
098        } else {
099            if (assumptions != null) {
100                AssumptionResult<ResolvedJavaType> leafConcreteSubtype = targetType == null ? null : targetType.findLeafConcreteSubtype();
101                if (leafConcreteSubtype != null) {
102                    assumptions.record(leafConcreteSubtype);
103                    exact = leafConcreteSubtype.getResult();
104                } else {
105                    exact = null;
106                }
107            } else {
108                exact = null;
109            }
110        }
111        Double[] hitProbability = {null};
112        this.hints = makeHints(targetType, profile, minHintHitProbability, maxHints, hitProbability);
113        this.hintHitProbability = hitProbability[0];
114    }
115
116    private static Hint[] makeHints(ResolvedJavaType targetType, JavaTypeProfile profile, double minHintHitProbability, int maxHints, Double[] hitProbability) {
117        double hitProb = 0.0d;
118        Hint[] hintsBuf = NO_HINTS;
119        if (profile != null) {
120            double notRecordedTypes = profile.getNotRecordedProbability();
121            ProfiledType[] ptypes = profile.getTypes();
122            if (notRecordedTypes < (1D - minHintHitProbability) && ptypes != null && ptypes.length > 0) {
123                hintsBuf = new Hint[ptypes.length];
124                int hintCount = 0;
125                for (ProfiledType ptype : ptypes) {
126                    if (targetType != null) {
127                        ResolvedJavaType hintType = ptype.getType();
128                        hintsBuf[hintCount++] = new Hint(hintType, targetType.isAssignableFrom(hintType));
129                        hitProb += ptype.getProbability();
130                    }
131                    if (hintCount == maxHints) {
132                        break;
133                    }
134                }
135                if (hitProb >= minHintHitProbability) {
136                    if (hintsBuf.length != hintCount || hintCount > maxHints) {
137                        hintsBuf = Arrays.copyOf(hintsBuf, Math.min(maxHints, hintCount));
138                    }
139                } else {
140                    hintsBuf = NO_HINTS;
141                    hitProb = 0.0d;
142                }
143            }
144        }
145        hitProbability[0] = hitProb;
146        return hintsBuf;
147    }
148}