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.nodes;
26 
27 import java.util.Arrays;
28 
29 import org.graalvm.compiler.core.common.type.TypeReference;
30 
31 import jdk.vm.ci.meta.Assumptions;
32 import jdk.vm.ci.meta.JavaTypeProfile;
33 import jdk.vm.ci.meta.JavaTypeProfile.ProfiledType;
34 import jdk.vm.ci.meta.ResolvedJavaType;
35 
36 /**
37  * Utility for deriving hint types for a type check instruction (e.g. checkcast or instanceof) based
38  * on the target type of the check and any profiling information available for the instruction.
39  */
40 public class TypeCheckHints {
41 
42     /**
43      * A receiver type profiled in a type check instruction.
44      */
45     public static class Hint {
46 
47         /**
48          * A type seen while profiling a type check instruction.
49          */
50         public final ResolvedJavaType type;
51 
52         /**
53          * Specifies if {@link #type} is a sub-type of the checked type.
54          */
55         public final boolean positive;
56 
Hint(ResolvedJavaType type, boolean positive)57         Hint(ResolvedJavaType type, boolean positive) {
58             this.type = type;
59             this.positive = positive;
60         }
61     }
62 
63     private static final Hint[] NO_HINTS = {};
64 
65     /**
66      * If non-null, then this is the only type that could pass the type check because the target of
67      * the type check is a final class or has been speculated to be a final class and this value is
68      * the only concrete subclass of the target type.
69      */
70     public final ResolvedJavaType exact;
71 
72     /**
73      * The most likely types that the type check instruction will see.
74      */
75     public final Hint[] hints;
76 
77     /**
78      * The profile from which this information was derived.
79      */
80     public final JavaTypeProfile profile;
81 
82     /**
83      * The total probability that the type check will hit one of the types in {@link #hints}.
84      */
85     public final double hintHitProbability;
86 
87     /**
88      * Derives hint information for use when generating the code for a type check instruction.
89      *
90      * @param targetType the target type of the type check
91      * @param profile the profiling information available for the instruction (if any)
92      * @param assumptions the object in which speculations are recorded. This is null if
93      *            speculations are not supported.
94      * @param minHintHitProbability if the probability that the type check will hit one of the
95      *            profiled types (up to {@code maxHints}) is below this value, then {@link #hints}
96      *            will be null
97      * @param maxHints the maximum length of {@link #hints}
98      */
TypeCheckHints(TypeReference targetType, JavaTypeProfile profile, Assumptions assumptions, double minHintHitProbability, int maxHints)99     public TypeCheckHints(TypeReference targetType, JavaTypeProfile profile, Assumptions assumptions, double minHintHitProbability, int maxHints) {
100         this.profile = profile;
101         if (targetType != null && targetType.isExact()) {
102             exact = targetType.getType();
103         } else {
104             exact = null;
105         }
106         Double[] hitProbability = {null};
107         this.hints = makeHints(targetType, profile, minHintHitProbability, maxHints, hitProbability);
108         this.hintHitProbability = hitProbability[0];
109     }
110 
makeHints(TypeReference targetType, JavaTypeProfile profile, double minHintHitProbability, int maxHints, Double[] hitProbability)111     private static Hint[] makeHints(TypeReference targetType, JavaTypeProfile profile, double minHintHitProbability, int maxHints, Double[] hitProbability) {
112         double hitProb = 0.0d;
113         Hint[] hintsBuf = NO_HINTS;
114         if (profile != null) {
115             double notRecordedTypes = profile.getNotRecordedProbability();
116             ProfiledType[] ptypes = profile.getTypes();
117             if (notRecordedTypes < (1D - minHintHitProbability) && ptypes != null && ptypes.length > 0) {
118                 hintsBuf = new Hint[ptypes.length];
119                 int hintCount = 0;
120                 for (ProfiledType ptype : ptypes) {
121                     if (targetType != null) {
122                         ResolvedJavaType hintType = ptype.getType();
123                         hintsBuf[hintCount++] = new Hint(hintType, targetType.getType().isAssignableFrom(hintType));
124                         hitProb += ptype.getProbability();
125                     }
126                     if (hintCount == maxHints) {
127                         break;
128                     }
129                 }
130                 if (hitProb >= minHintHitProbability) {
131                     if (hintsBuf.length != hintCount || hintCount > maxHints) {
132                         hintsBuf = Arrays.copyOf(hintsBuf, Math.min(maxHints, hintCount));
133                     }
134                 } else {
135                     hintsBuf = NO_HINTS;
136                     hitProb = 0.0d;
137                 }
138             }
139         }
140         hitProbability[0] = hitProb;
141         return hintsBuf;
142     }
143 }
144