001 /*
002 * This file is part of the Jikes RVM project (http://jikesrvm.org).
003 *
004 * This file is licensed to You under the Eclipse Public License (EPL);
005 * You may not use this file except in compliance with the License. You
006 * may obtain a copy of the License at
007 *
008 * http://www.opensource.org/licenses/eclipse-1.0.php
009 *
010 * See the COPYRIGHT.txt file distributed with this work for information
011 * regarding copyright ownership.
012 */
013 package org.jikesrvm.classloader;
014
015 import org.jikesrvm.VM;
016 import org.jikesrvm.mm.mminterface.MemoryManager;
017 import org.jikesrvm.objectmodel.TIB;
018 import org.jikesrvm.objectmodel.TIBLayoutConstants;
019 import org.jikesrvm.runtime.Magic;
020 import org.vmmagic.pragma.Uninterruptible;
021
022 /**
023 * Data structures and code for fast dynamic type checking.
024 * <p>
025 * As a convention, we convert all dynamic type checking
026 * operations into the following question: LHS :?= RHS
027 * (i.e. can an instance of the RHS class be stored in a
028 * variable of the LHS class or interface.) This question
029 * arises for four bytecodes: instanceof, checkcast, aastore
030 * and invokeinterface and entry into catch blocks.
031 * This gives us a uniform terminology, but in some cases
032 * (instanceof) can be somewhat counter-intuitive since despite
033 * the fact that the Java source code is written as
034 * <code>x instanceof C</code>, for the purposes of dynamic type checking
035 * <code>x</code> is the RHS and <code>C</code> is the LHS!
036 * <p>
037 * The idea of the optimizations presented below is to treat
038 * each context in which these queries arises as a special
039 * case to be optimised in isolation. Consider the following
040 * taxonomy of dynamic type checking conexts:
041 * <p>
042 * (1) Is the LHS unknown at compile time? True only for aastore?
043 * If so, the following test will be fast in most instances:
044 * is the runtime type of the LHS array the same as compile-time
045 * type of the variable that contains it? If so, the Java-to-bytecode
046 * compiler (and the verifier) guarantees that the test passes.
047 * Unfortunately, this test can only be used in two of three cases:
048 * when the LHS variable is a field or a parameter. When the LHS is
049 * in a local variable the Java-to-bytecode compiler has thrown away
050 * the necessary type information.
051 * <p>
052 * (2) Otherwise, is the LHS an array?
053 * If so, there are three sub-cases
054 * <ul>
055 * <li>(2a) LHS is [^k primitive:
056 * If so, the dimensionality of the RHS must be k
057 * and the baseclass of the RHS must be the same primitive
058 * <li>(2b) LHS is [^k class:
059 * If so, the dimensionality of the RHS must be k
060 * and the baseclass of the RHS must be assignable with class (see #3)
061 * _OR_ the dimensionality of the RHS must be >k
062 * and the baseclass of the LHS is java.lang.Cloneable or java.io.Serializable
063 * <li>(2c) LHS is [^k Ljava.lang.Object:
064 * If so, either the dimensionality of the RHS is greater than k
065 * or, this dimensionality is k and the baseclass is NOT primitive
066 * <ul>
067 * <p>
068 * (3) Otherwise, is the LHS unresolved?
069 * If so, fall back to calling RuntimeEntrypoints.instanceOf at runtime which will
070 * load/resolve the types and then call DynamicTypeCheck.instanceOf.
071 * <p>
072 * (4) Otherwise, is the LHS an interface?
073 * If so, query the doesImplement array of the RHS's TIB at the entry
074 * for the interface ID. If a class does not directly implement any
075 * interfaces then it inherits the doesImplement array from its superclass.
076 * <p>
077 * (5) Otherwise, is the depth of the LHS greater than
078 * MIN_SUPERCLASS_IDS_SIZE? If so, if LHS depth is greater that
079 * RHS's superclassIds.length, the test fails. Else, see #6.
080 * <p>
081 * (6) Otherwise. If the LHS depth component of the RHS's superclassIds
082 * array is the LHS class ID, the test succeeds. Else, it fails.
083 *
084 * @see org.jikesrvm.compilers.opt.hir2lir.DynamicTypeCheckExpansion
085 * @see RVMType
086 * @see RVMClass
087 * @see RVMArray
088 */
089 public class DynamicTypeCheck implements TIBLayoutConstants {
090
091 /**
092 * Minimum length of the superclassIds array in TIB.
093 * Note: this array is padded to save a index out of
094 * bounds test for classes with shallow class depth.
095 */
096 public static final int MIN_SUPERCLASS_IDS_SIZE = 6; // a short[], so multiple of 2.
097
098 /**
099 * Minimum length of the doesImplements array in TIB.
100 * Note: this array is padded to save a index out of
101 * bounds test for the first 32 * MIN_DOES_IMPLEMENT_SIZE interfaces loaded.
102 */
103 public static final int MIN_DOES_IMPLEMENT_SIZE = 5; // an int[]
104
105 /**
106 * Create the superclass Id vector for a RVMType.
107 *
108 * @param t a RVMType to create a superclass Id vector for
109 * @return the superclass Id vector
110 */
111 static short[] buildSuperclassIds(RVMType t) {
112 int depth = t.getTypeDepth();
113 short[] tsi;
114 if (t.isJavaLangObjectType()) {
115 if (VM.VerifyAssertions) VM._assert(depth == 0);
116 tsi = MemoryManager.newNonMovingShortArray(1);
117 } else {
118 int size = MIN_SUPERCLASS_IDS_SIZE <= depth ? depth + 1 : MIN_SUPERCLASS_IDS_SIZE;
119 tsi = MemoryManager.newNonMovingShortArray(size);
120 RVMType p;
121 if (t.isArrayType() || t.asClass().isInterface()) {
122 p = RVMType.JavaLangObjectType;
123 } else {
124 p = t.asClass().getSuperClass();
125 }
126 short[] psi = p.getSuperclassIds();
127 for (int i = 0; i < depth; i++) {
128 tsi[i] = psi[i];
129 }
130 }
131 int id = t.getId();
132 if (VM.VerifyAssertions) VM._assert(id <= 0xFFFF); // when this fails, make superclassIds int[]
133 tsi[depth] = (short) id;
134 return tsi;
135 }
136
137 private static int[] arrayDoesImplement;
138
139 /**
140 * Create the doesImplement vector for a RVMArray.
141 * All arrays implement exactly java.io.Serializable and java.lang.Cloneable.
142 *
143 * @param t a RVMArray to create a doesImplement vector for
144 * @return the doesImplement vector
145 */
146 static int[] buildDoesImplement(RVMArray t) {
147 if (arrayDoesImplement == null) {
148 int cloneIdx = RVMType.JavaLangCloneableType.getDoesImplementIndex();
149 int serialIdx = RVMType.JavaIoSerializableType.getDoesImplementIndex();
150 int size = Math.max(cloneIdx, serialIdx);
151 size = Math.max(MIN_DOES_IMPLEMENT_SIZE, size + 1);
152 int[] tmp = MemoryManager.newNonMovingIntArray(size);
153 tmp[cloneIdx] = RVMType.JavaLangCloneableType.getDoesImplementBitMask();
154 tmp[serialIdx] |= RVMType.JavaIoSerializableType.getDoesImplementBitMask();
155 arrayDoesImplement = tmp;
156 }
157 return arrayDoesImplement;
158 }
159
160 /**
161 * Create the doesImplement vector for a RVMClass.
162 *
163 * @param t a RVMClass to create a doesImplement vector for
164 * @return the doesImplement vector
165 */
166 static int[] buildDoesImplement(RVMClass t) {
167 if (t.isJavaLangObjectType()) {
168 // object implements no interfaces.
169 return MemoryManager.newNonMovingIntArray(MIN_DOES_IMPLEMENT_SIZE);
170 }
171
172 RVMClass[] superInterfaces = t.getDeclaredInterfaces();
173
174 if (!t.isInterface() && superInterfaces.length == 0) {
175 // I add nothing new; share with parent.
176 return t.getSuperClass().getDoesImplement();
177 }
178
179 // I need one of my own; first figure out how big it needs to be.
180 int size;
181 if (t.isInterface()) {
182 size = Math.max(MIN_DOES_IMPLEMENT_SIZE, t.getDoesImplementIndex() + 1);
183 } else {
184 size = t.getSuperClass().getDoesImplement().length;
185 }
186 for (RVMClass superInterface : superInterfaces) {
187 size = Math.max(size, superInterface.getDoesImplement().length);
188 }
189
190 // then create and populate it
191 int[] mine = MemoryManager.newNonMovingIntArray(size);
192 if (t.isInterface()) {
193 mine[t.getDoesImplementIndex()] = t.getDoesImplementBitMask();
194 } else {
195 int[] parent = t.getSuperClass().getDoesImplement();
196 for (int j = 0; j < parent.length; j++) {
197 mine[j] |= parent[j];
198 }
199 }
200 for (RVMClass superInterface : superInterfaces) {
201 int[] parent = superInterface.getDoesImplement();
202 for (int j = 0; j < parent.length; j++) {
203 mine[j] |= parent[j];
204 }
205 }
206
207 return mine;
208 }
209
210 /**
211 * LHSclass is a fully loaded class or interface.
212 * Is rhsTIB the TIB of an instanceof LHSclass?
213 *
214 * @param LHSclass a fully loaded class or interface class
215 * @param rhsTIB the TIB of an object that might be an instance of LHSclass
216 * @return <code>true</code> if the object is an instance of LHSClass
217 * or <code>false</code> if it is not
218 */
219 public static boolean instanceOfNonArray(RVMClass LHSclass, TIB rhsTIB) {
220 if (LHSclass.isInterface()) {
221 return instanceOfInterface(LHSclass, rhsTIB);
222 } else {
223 return instanceOfClass(LHSclass, rhsTIB);
224 }
225 }
226
227 /**
228 * LHSclass is a fully loaded class.
229 * Is rhsTIB the TIB of a subclass of LHSclass?
230 *
231 * @param LHSclass a (fully loaded) class
232 * @param rhsTIB the TIB of an object that might be an instance of LHSclass
233 * @return <code>true</code> if the object is an instance of LHSClass
234 * or <code>false</code> if it is not
235 */
236 @Uninterruptible
237 public static boolean instanceOfClass(RVMClass LHSclass, TIB rhsTIB) {
238 if (VM.VerifyAssertions) {
239 VM._assert(rhsTIB != null);
240 VM._assert(rhsTIB.getSuperclassIds() != null);
241 }
242 short[] superclassIds = Magic.objectAsShortArray(rhsTIB.getSuperclassIds());
243 int LHSDepth = LHSclass.getTypeDepth();
244 if (LHSDepth >= superclassIds.length) return false;
245 int LHSId = LHSclass.getId();
246 return (superclassIds[LHSDepth] & 0xFFFF) == LHSId;
247 }
248
249 /**
250 * LHSclass is a fully loaded interface.
251 * Is rhsTIB the TIB of a class that implements LHSclass?
252 *
253 * @param LHSclass a class (that is a fully loaded interface)
254 * @param rhsTIB the TIB of an object that might be an instance of LHSclass
255 * @return <code>true</code> if the object is an instance of LHSClass
256 * or <code>false</code> if it is not
257 */
258 public static boolean instanceOfInterface(RVMClass LHSclass, TIB rhsTIB) {
259 int[] doesImplement = rhsTIB.getDoesImplement();
260 int idx = LHSclass.getDoesImplementIndex();
261 int mask = LHSclass.getDoesImplementBitMask();
262 return idx < doesImplement.length && ((doesImplement[idx] & mask) != 0);
263 }
264
265 /**
266 * Can we store an object of type RHSType in a variable of type LHSType?
267 * Assumption. LHSType and RHSType are already resolved.
268 *
269 * @param LHSType the left-hand-side type
270 * @param RHSType the right-hand-size type
271 * @return <code>true</code> if we can store an object of
272 * RHSType into a variable of type LSType
273 * or <code>false</code> if we cannot.
274 */
275 public static boolean instanceOfResolved(RVMType LHSType, RVMType RHSType) {
276 int LHSDimension = LHSType.getDimensionality();
277 int RHSDimension = RHSType.getDimensionality();
278 if (LHSDimension < 0 || RHSDimension < 0) return false;
279 if (LHSDimension == 0) {
280 return instanceOfNonArray(LHSType.asClass(), RHSType.getTypeInformationBlock());
281 }
282 RVMType LHSInnermostElementType = LHSType.asArray().getInnermostElementType();
283 if (LHSInnermostElementType == RVMType.JavaLangObjectType) {
284 if (RHSDimension < LHSDimension) return false;
285 if (RHSDimension > LHSDimension) return true;
286 return RHSType.asArray().getInnermostElementType().isClassType(); // !primitive
287 } else if (!(LHSInnermostElementType.isPrimitiveType() || LHSInnermostElementType.isUnboxedType())) {
288 if (RHSDimension == LHSDimension) {
289 RVMType RHSInnermostElementType = RHSType.asArray().getInnermostElementType();
290 if ((RHSInnermostElementType.isPrimitiveType() || RHSInnermostElementType.isUnboxedType())) return false;
291 return instanceOfNonArray(LHSInnermostElementType.asClass(), RHSInnermostElementType.getTypeInformationBlock());
292 } else {
293 // All array types implicitly implement java.lang.Cloneable and java.io.Serializable
294 // so if LHS is if lesser dimensionality then this check must succeed if its innermost
295 // element type is one of these special interfaces.
296 return (LHSDimension < RHSDimension &&
297 (LHSInnermostElementType == RVMType.JavaLangCloneableType ||
298 LHSInnermostElementType == RVMType.JavaIoSerializableType));
299 }
300 } else {
301 return false;
302 }
303 }
304 }