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 * (2a) LHS is [^k primitive:
055 * If so, the dimensionality of the RHS must be k
056 * and the baseclass of the RHS must be the same primitive
057 * (2b) LHS is [^k class:
058 * If so, the dimensionality of the RHS must be k
059 * and the baseclass of the RHS must be assignable with class (see #3)
060 * _OR_ the dimensionality of the RHS must be >k
061 * and the baseclass of the LHS is java.lang.Cloneable or java.io.Serializable
062 * (2c) LHS is [^k Ljava.lang.Object:
063 * If so, either the dimensionality of the RHS is greater than k
064 * or, this dimensionality is k and the baseclass is NOT primitive
065 * <p>
066 * (3) Otherwise, is the LHS unresolved?
067 * If so, fall back to calling RuntimeEntrypoints.instanceOf at runtime which will
068 * load/resolve the types and then call DynamicTypeCheck.instanceOf.
069 * <p>
070 * (4) Otherwise, is the LHS an interface?
071 * If so, query the doesImplement array of the RHS's TIB at the entry
072 * for the interface ID. If a class does not directly implement any
073 * interfaces then it inherits the doesImplement array from its superclass.
074 * <p>
075 * (5) Otherwise, is the depth of the LHS greater than
076 * MIN_SUPERCLASS_IDS_SIZE? If so, if LHS depth is greater that
077 * RHS's superclassIds.length, the test fails. Else, see #6.
078 * <p>
079 * (6) Otherwise. If the LHS depth component of the RHS's superclassIds
080 * array is the LHS class ID, the test succeeds. Else, it fails.
081 *
082 * @see org.jikesrvm.compilers.opt.hir2lir.DynamicTypeCheckExpansion
083 * @see RVMType
084 * @see RVMClass
085 * @see RVMArray
086 */
087 public class DynamicTypeCheck implements TIBLayoutConstants {
088
089 /**
090 * Minimum length of the superclassIds array in TIB.
091 * Note: this array is padded to save a index out of
092 * bounds test for classes with shallow class depth.
093 */
094 public static final int MIN_SUPERCLASS_IDS_SIZE = 6; // a short[], so multiple of 2.
095
096 /**
097 * Minimum length of the doesImplements array in TIB.
098 * Note: this array is padded to save a index out of
099 * bounds test for the first 32 * MIN_DOES_IMPLEMENT_SIZE interfaces loaded.
100 */
101 public static final int MIN_DOES_IMPLEMENT_SIZE = 5; // an int[]
102
103 /**
104 * Create the superclass Id vector for a RVMType.
105 *
106 * @param t a RVMType to create a superclass Id vector for
107 * @return the superclass Id vector
108 */
109 static short[] buildSuperclassIds(RVMType t) {
110 int depth = t.getTypeDepth();
111 short[] tsi;
112 if (t.isJavaLangObjectType()) {
113 if (VM.VerifyAssertions) VM._assert(depth == 0);
114 tsi = MemoryManager.newNonMovingShortArray(1);
115 } else {
116 int size = MIN_SUPERCLASS_IDS_SIZE <= depth ? depth + 1 : MIN_SUPERCLASS_IDS_SIZE;
117 tsi = MemoryManager.newNonMovingShortArray(size);
118 RVMType p;
119 if (t.isArrayType() || t.asClass().isInterface()) {
120 p = RVMType.JavaLangObjectType;
121 } else {
122 p = t.asClass().getSuperClass();
123 }
124 short[] psi = p.getSuperclassIds();
125 for (int i = 0; i < depth; i++) {
126 tsi[i] = psi[i];
127 }
128 }
129 int id = t.getId();
130 if (VM.VerifyAssertions) VM._assert(id <= 0xFFFF); // when this fails, make superclassIds int[]
131 tsi[depth] = (short) id;
132 return tsi;
133 }
134
135 private static int[] arrayDoesImplement;
136
137 /**
138 * Create the doesImplement vector for a RVMArray.
139 * All arrays implement exactly java.io.Serializable and java.lang.Cloneable.
140 *
141 * @param t a RVMArray to create a doesImplement vector for
142 * @return the doesImplement vector
143 */
144 static int[] buildDoesImplement(RVMArray t) {
145 if (arrayDoesImplement == null) {
146 int cloneIdx = RVMType.JavaLangCloneableType.getDoesImplementIndex();
147 int serialIdx = RVMType.JavaIoSerializableType.getDoesImplementIndex();
148 int size = Math.max(cloneIdx, serialIdx);
149 size = Math.max(MIN_DOES_IMPLEMENT_SIZE, size + 1);
150 int[] tmp = MemoryManager.newNonMovingIntArray(size);
151 tmp[cloneIdx] = RVMType.JavaLangCloneableType.getDoesImplementBitMask();
152 tmp[serialIdx] |= RVMType.JavaIoSerializableType.getDoesImplementBitMask();
153 arrayDoesImplement = tmp;
154 }
155 return arrayDoesImplement;
156 }
157
158 /**
159 * Create the doesImplement vector for a RVMClass.
160 *
161 * @param t a RVMClass to create a doesImplement vector for
162 * @return the doesImplement vector
163 */
164 static int[] buildDoesImplement(RVMClass t) {
165 if (t.isJavaLangObjectType()) {
166 // object implements no interfaces.
167 return MemoryManager.newNonMovingIntArray(MIN_DOES_IMPLEMENT_SIZE);
168 }
169
170 RVMClass[] superInterfaces = t.getDeclaredInterfaces();
171
172 if (!t.isInterface() && superInterfaces.length == 0) {
173 // I add nothing new; share with parent.
174 return t.getSuperClass().getDoesImplement();
175 }
176
177 // I need one of my own; first figure out how big it needs to be.
178 int size;
179 if (t.isInterface()) {
180 size = Math.max(MIN_DOES_IMPLEMENT_SIZE, t.getDoesImplementIndex() + 1);
181 } else {
182 size = t.getSuperClass().getDoesImplement().length;
183 }
184 for (RVMClass superInterface : superInterfaces) {
185 size = Math.max(size, superInterface.getDoesImplement().length);
186 }
187
188 // then create and populate it
189 int[] mine = MemoryManager.newNonMovingIntArray(size);
190 if (t.isInterface()) {
191 mine[t.getDoesImplementIndex()] = t.getDoesImplementBitMask();
192 } else {
193 int[] parent = t.getSuperClass().getDoesImplement();
194 for (int j = 0; j < parent.length; j++) {
195 mine[j] |= parent[j];
196 }
197 }
198 for (RVMClass superInterface : superInterfaces) {
199 int[] parent = superInterface.getDoesImplement();
200 for (int j = 0; j < parent.length; j++) {
201 mine[j] |= parent[j];
202 }
203 }
204
205 return mine;
206 }
207
208 /**
209 * LHSclass is a fully loaded class or interface.
210 * Is rhsTIB the TIB of an instanceof LHSclass?
211 *
212 * @param LHSclass a fully loaded class or interface class
213 * @param rhsTIB the TIB of an object that might be an instance of LHSclass
214 * @return <code>true</code> if the object is an instance of LHSClass
215 * or <code>false</code> if it is not
216 */
217 public static boolean instanceOfNonArray(RVMClass LHSclass, TIB rhsTIB) {
218 if (LHSclass.isInterface()) {
219 return instanceOfInterface(LHSclass, rhsTIB);
220 } else {
221 return instanceOfClass(LHSclass, rhsTIB);
222 }
223 }
224
225 /**
226 * LHSclass is a fully loaded class.
227 * Is rhsTIB the TIB of a subclass of LHSclass?
228 *
229 * @param LHSclass a (fully loaded) class
230 * @param rhsTIB the TIB of an object that might be an instance of LHSclass
231 * @return <code>true</code> if the object is an instance of LHSClass
232 * or <code>false</code> if it is not
233 */
234 @Uninterruptible
235 public static boolean instanceOfClass(RVMClass LHSclass, TIB rhsTIB) {
236 if (VM.VerifyAssertions) {
237 VM._assert(rhsTIB != null);
238 VM._assert(rhsTIB.getSuperclassIds() != null);
239 }
240 short[] superclassIds = Magic.objectAsShortArray(rhsTIB.getSuperclassIds());
241 int LHSDepth = LHSclass.getTypeDepth();
242 if (LHSDepth >= superclassIds.length) return false;
243 int LHSId = LHSclass.getId();
244 return (superclassIds[LHSDepth] & 0xFFFF) == LHSId;
245 }
246
247 /**
248 * LHSclass is a fully loaded interface.
249 * Is rhsTIB the TIB of a class that implements LHSclass?
250 *
251 * @param LHSclass a class (that is a fully loaded interface)
252 * @param rhsTIB the TIB of an object that might be an instance of LHSclass
253 * @return <code>true</code> if the object is an instance of LHSClass
254 * or <code>false</code> if it is not
255 */
256 public static boolean instanceOfInterface(RVMClass LHSclass, TIB rhsTIB) {
257 int[] doesImplement = rhsTIB.getDoesImplement();
258 int idx = LHSclass.getDoesImplementIndex();
259 int mask = LHSclass.getDoesImplementBitMask();
260 return idx < doesImplement.length && ((doesImplement[idx] & mask) != 0);
261 }
262
263 /**
264 * Can we store an object of type RHSType in a variable of type LHSType?
265 * Assumption. LHSType and RHSType are already resolved.
266 *
267 * @param LHSType the left-hand-side type
268 * @param RHSType the right-hand-size type
269 * @return <code>true</code> if we can store an object of
270 * RHSType into a variable of type LSType
271 * or <code>false</code> if we cannot.
272 */
273 public static boolean instanceOfResolved(RVMType LHSType, RVMType RHSType) {
274 int LHSDimension = LHSType.getDimensionality();
275 int RHSDimension = RHSType.getDimensionality();
276 if (LHSDimension < 0 || RHSDimension < 0) return false;
277 if (LHSDimension == 0) {
278 return instanceOfNonArray(LHSType.asClass(), RHSType.getTypeInformationBlock());
279 }
280 RVMType LHSInnermostElementType = LHSType.asArray().getInnermostElementType();
281 if (LHSInnermostElementType == RVMType.JavaLangObjectType) {
282 if (RHSDimension < LHSDimension) return false;
283 if (RHSDimension > LHSDimension) return true;
284 return RHSType.asArray().getInnermostElementType().isClassType(); // !primitive
285 } else if (!(LHSInnermostElementType.isPrimitiveType() || LHSInnermostElementType.isUnboxedType())) {
286 if (RHSDimension == LHSDimension) {
287 RVMType RHSInnermostElementType = RHSType.asArray().getInnermostElementType();
288 if ((RHSInnermostElementType.isPrimitiveType() || RHSInnermostElementType.isUnboxedType())) return false;
289 return instanceOfNonArray(LHSInnermostElementType.asClass(), RHSInnermostElementType.getTypeInformationBlock());
290 } else {
291 // All array types implicitly implement java.lang.Cloneable and java.io.Serializable
292 // so if LHS is if lesser dimensionality then this check must succeed if its innermost
293 // element type is one of these special interfaces.
294 return (LHSDimension < RHSDimension &&
295 (LHSInnermostElementType == RVMType.JavaLangCloneableType ||
296 LHSInnermostElementType == RVMType.JavaIoSerializableType));
297 }
298 } else {
299 return false;
300 }
301 }
302 }