Code drop from //branches/cupcake/...@124589

6 files changed, 1865 insertions, 218 deletions

diff --git a/vm/analysis/CodeVerify.c b/vm/analysis/CodeVerify.c
index fd4c75b14..b4fde5a62 100644
--- a/vm/analysis/CodeVerify.c
+++ b/vm/analysis/CodeVerify.c
@@ -13,6 +13,7 @@
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */
+
 /*
  * Dalvik bytecode structural verifier.  The only public entry point
  * (except for a few shared utility functions) is dvmVerifyCodeFlow().
@@ -184,6 +185,8 @@ typedef struct RegisterTable {
 /* fwd */
 static void checkMergeTab(void);
 static bool isInitMethod(const Method* meth);
+static void logUnableToResolveClass(const char* missingClassDescr,\
+    const Method* meth);
 static RegType getInvocationThis(const RegType* insnRegs,\
     const int insnRegCount, const DecodedInstruction* pDecInsn, bool* pOkay);
 static void verifyRegisterType(const RegType* insnRegs, const int insnRegCount,\
@@ -360,6 +363,40 @@ static bool canConvertTo2(RegType srcType, RegType checkType)
 }
 
 /*
+ * Determine whether or not "srcType" and "checkType" have the same width.
+ * The idea is to determine whether or not it's okay to use a sub-integer
+ * instruction (say, sget-short) with a primitive field of a specific type.
+ *
+ * We should always be passed "definite" types here; pseudo-types like
+ * kRegTypeZero are not expected.  We could get kRegTypeUnknown if a type
+ * lookup failed.
+ */
+static bool isTypeWidthEqual1nr(RegType type1, RegType type2)
+{
+    /* primitive sizes; we use zero for boolean so it's not equal to others */
+    static const char sizeTab[kRegType1nrEND-kRegType1nrSTART+1] = {
+        /* F  0  1  Z  b  B  s  S  C  I */
+           4, 8, 9, 0, 1, 1, 2, 2, 2, 4
+    };
+
+    assert(type1 != kRegTypeZero && type1 != kRegTypeOne &&
+           type1 != kRegTypePosByte && type1 != kRegTypePosShort);
+    assert(type2 != kRegTypeZero && type2 != kRegTypeOne &&
+           type2 != kRegTypePosByte && type2 != kRegTypePosShort);
+
+    if (type1 == type2)
+        return true;            /* quick positive; most common case */
+
+    /* might be able to eliminate one of these by narrowly defining our args? */
+    if (type1 < kRegType1nrSTART || type1 > kRegType1nrEND)
+        return false;
+    if (type2 < kRegType1nrSTART || type2 > kRegType1nrEND)
+        return false;
+
+    return sizeTab[type1-kRegType1nrSTART] == sizeTab[type2-kRegType1nrSTART];
+}
+
+/*
  * Given a 32-bit constant, return the most-restricted RegType that can hold
  * the value.
  */
@@ -599,6 +636,14 @@ static bool isInitMethod(const Method* meth)
 }
 
 /*
+ * Is this method a class initializer?
+ */
+static bool isClassInitMethod(const Method* meth)
+{
+    return (*meth->name == '<' && strcmp(meth->name+1, "clinit>") == 0);
+}
+
+/*
  * Look up a class reference given as a simple string descriptor.
  */
 static ClassObject* lookupClassByDescriptor(const Method* meth,
@@ -624,18 +669,18 @@ static ClassObject* lookupClassByDescriptor(const Method* meth,
     if (clazz == NULL) {
         dvmClearOptException(dvmThreadSelf());
         if (strchr(pDescriptor, '$') != NULL) {
-            LOGV("VFY: unable to find class referenced in "
-                "signature (%s)\n", pDescriptor);
+            LOGV("VFY: unable to find class referenced in signature (%s)\n",
+                pDescriptor);
         } else {
-            LOG_VFY("VFY: unable to find class referenced in "
-                "signature (%s)\n", pDescriptor);
+            LOG_VFY("VFY: unable to find class referenced in signature (%s)\n",
+                pDescriptor);
         }
 
         if (pDescriptor[0] == '[') {
             /* We are looking at an array descriptor. */
 
             /*
-             * There should never be a problem loading primitive arrays.  
+             * There should never be a problem loading primitive arrays.
              */
             if (pDescriptor[1] != 'L' && pDescriptor[1] != '[') {
                 LOG_VFY("VFY: invalid char in signature in '%s'\n",
@@ -775,6 +820,8 @@ static bool setTypesFromSignature(const Method* meth, RegType* regTypes,
     expectedArgs = meth->insSize;     /* long/double count as two */
     actualArgs = 0;
 
+    assert(argStart >= 0);      /* should have been verified earlier */
+
     /*
      * Include the "this" pointer.
      */
@@ -948,7 +995,7 @@ static RegType getMethodReturnType(const Method* meth)
     RegType type;
     bool okay = true;
     const char* descriptor = dexProtoGetReturnType(&meth->prototype);
-    
+
     switch (*descriptor) {
     case 'I':
         type = kRegTypeInteger;
@@ -1098,6 +1145,22 @@ static Method* verifyInvocationArgs(const Method* meth, const RegType* insnRegs,
         methodDesc = dexCopyDescriptorFromMethodId(pDexFile, pMethodId);
         classDescriptor = dexStringByTypeIdx(pDexFile, pMethodId->classIdx);
 
+        if (!gDvm.optimizing) {
+            char* dotMissingClass = dvmDescriptorToDot(classDescriptor);
+            char* dotMethClass = dvmDescriptorToDot(meth->clazz->descriptor);
+            //char* curMethodDesc =
+            //    dexProtoCopyMethodDescriptor(&meth->prototype);
+
+            LOGE("Could not find method %s.%s, referenced from "
+                 "method %s.%s\n",
+                 dotMissingClass, methodName/*, methodDesc*/,
+                 dotMethClass, meth->name/*, curMethodDesc*/);
+
+            free(dotMissingClass);
+            free(dotMethClass);
+            //free(curMethodDesc);
+        }
+
         LOG_VFY("VFY: unable to resolve %s method %u: %s.%s %s\n",
             dvmMethodTypeStr(methodType), pDecInsn->vB,
             classDescriptor, methodName, methodDesc);
@@ -1629,7 +1692,7 @@ static void verifyRegisterType(const RegType* insnRegs, const int insnRegCount,
                  * See comments above findCommonSuperclass.
                  */
                 /*
-                if (srcClass != checkClass && 
+                if (srcClass != checkClass &&
                     !dvmImplements(srcClass, checkClass))
                 {
                     LOG_VFY("VFY: %s does not implement %s\n",
@@ -1887,7 +1950,7 @@ static void copyResultRegister1(RegType* insnRegs, const int insnRegCount,
 {
     RegType type;
     u4 vsrc;
-    
+
     vsrc = RESULT_REGISTER(insnRegCount);
     type = getRegisterType(insnRegs, insnRegCount + kExtraRegs, vsrc, pOkay);
     if (*pOkay)
@@ -1915,7 +1978,7 @@ static void copyResultRegister2(RegType* insnRegs, const int insnRegCount,
 {
     RegType typel, typeh;
     u4 vsrc;
-    
+
     vsrc = RESULT_REGISTER(insnRegCount);
     typel = getRegisterType(insnRegs, insnRegCount + kExtraRegs, vsrc, pOkay);
     typeh = getRegisterType(insnRegs, insnRegCount + kExtraRegs, vsrc+1, pOkay);
@@ -2350,10 +2413,12 @@ void dvmLogVerifyFailure(const Method* meth, const char* format, ...)
     va_list ap;
     int logLevel;
 
-    if (gDvm.optimizing)
-        return; /* logLevel = ANDROID_LOG_DEBUG; */
-    else
+    if (gDvm.optimizing) {
+        return;
+        //logLevel = ANDROID_LOG_DEBUG;
+    } else {
         logLevel = ANDROID_LOG_WARN;
+    }
 
     va_start(ap, format);
     LOG_PRI_VA(logLevel, LOG_TAG, format, ap);
@@ -2366,6 +2431,28 @@ void dvmLogVerifyFailure(const Method* meth, const char* format, ...)
 }
 
 /*
+ * Show a relatively human-readable message describing the failure to
+ * resolve a class.
+ */
+static void logUnableToResolveClass(const char* missingClassDescr,
+    const Method* meth)
+{
+    if (gDvm.optimizing)
+        return;
+
+    char* dotMissingClass = dvmDescriptorToDot(missingClassDescr);
+    char* dotFromClass = dvmDescriptorToDot(meth->clazz->descriptor);
+    //char* methodDescr = dexProtoCopyMethodDescriptor(&meth->prototype);
+
+    LOGE("Could not find class '%s', referenced from method %s.%s\n",
+        dotMissingClass, dotFromClass, meth->name/*, methodDescr*/);
+
+    free(dotMissingClass);
+    free(dotFromClass);
+    //free(methodDescr);
+}
+
+/*
  * Extract the relative offset from a branch instruction.
  *
  * Returns "false" on failure (e.g. this isn't a branch instruction).
@@ -2518,6 +2605,64 @@ bail:
 }
 
 /*
+ * If "field" is marked "final", make sure this is the either <clinit>
+ * or <init> as appropriate.
+ *
+ * Sets "*pOkay" to false on failure.
+ */
+static void checkFinalFieldAccess(const Method* meth, const Field* field,
+    bool* pOkay)
+{
+    if (!dvmIsFinalField(field))
+        return;
+
+    /* make sure we're in the same class */
+    if (meth->clazz != field->clazz) {
+        LOG_VFY_METH(meth, "VFY: can't modify final field %s.%\n",
+            field->clazz->descriptor, field->name);
+        *pOkay = false;
+        return;
+    }
+
+    /* make sure we're in the right kind of constructor */
+    if (dvmIsStaticField(field)) {
+        if (!isClassInitMethod(meth)) {
+            LOG_VFY_METH(meth,
+                "VFY: can't modify final static field outside <clinit>\n");
+            *pOkay = false;
+        }
+    } else {
+        if (!isInitMethod(meth)) {
+            LOG_VFY_METH(meth,
+                "VFY: can't modify final field outside <init>\n");
+            *pOkay = false;
+        }
+    }
+}
+
+/*
+ * Make sure that the register type is suitable for use as an array index.
+ *
+ * Sets "*pOkay" to false if not.
+ */
+static void checkArrayIndexType(const Method* meth, RegType regType,
+    bool* pOkay)
+{
+    if (*pOkay) {
+        /*
+         * The 1nr types are interchangeable at this level.  We could
+         * do something special if we can definitively identify it as a
+         * float, but there's no real value in doing so.
+         */
+        checkTypeCategory(regType, kTypeCategory1nr, pOkay);
+        if (!*pOkay) {
+            LOG_VFY_METH(meth, "Invalid reg type for array index (%d)\n",
+                regType);
+        }
+    }
+}
+
+/*
  * Check constraints on constructor return.  Specifically, make sure that
  * the "this" argument got initialized.
  *
@@ -2608,7 +2753,7 @@ static ClassObject* getCaughtExceptionType(const Method* meth, int insnIdx)
             if (handler == NULL) {
                 break;
             }
-        
+
             if (handler->address == (u4) insnIdx) {
                 ClassObject* clazz;
 
@@ -2618,8 +2763,9 @@ static ClassObject* getCaughtExceptionType(const Method* meth, int insnIdx)
                     clazz = dvmOptResolveClass(meth->clazz, handler->typeIdx);
 
                 if (clazz == NULL) {
-                    LOGD("VFY: unable to resolve exceptionIdx=%u\n",
-                        handler->typeIdx);
+                    LOG_VFY("VFY: unable to resolve exception class %u (%s)\n",
+                        handler->typeIdx,
+                        dexStringByTypeIdx(pDexFile, handler->typeIdx));
                 } else {
                     if (commonSuper == NULL)
                         commonSuper = clazz;
@@ -3020,7 +3166,7 @@ static bool doCodeVerification(const Method* meth, InsnFlags* insnFlags,
                         meth->clazz->descriptor, meth->name, desc);
                     free(desc);
                 }
-                
+
                 deadStart = -1;
             }
         }
@@ -3118,7 +3264,15 @@ static bool verifyInstruction(const Method* meth, InsnFlags* insnFlags,
 
     switch (decInsn.opCode) {
     case OP_NOP:
-        /* no effect on anything */
+        /*
+         * A "pure" NOP has no effect on anything.  Data tables start with
+         * a signature that looks like a NOP; if we see one of these in
+         * the course of executing code then we have a problem.
+         */
+        if (decInsn.vA != 0) {
+            LOG_VFY("VFY: encountered data table in instruction stream\n");
+            okay = false;
+        }
         break;
 
     case OP_MOVE:
@@ -3256,7 +3410,7 @@ static bool verifyInstruction(const Method* meth, InsnFlags* insnFlags,
              * returned.
              */
             ClassObject* declClass;
-            
+
             declClass = regTypeInitializedReferenceToClass(returnType);
             resClass = getClassFromRegister(workRegs, insnRegCount,
                             decInsn.vA, &okay);
@@ -3298,23 +3452,13 @@ static bool verifyInstruction(const Method* meth, InsnFlags* insnFlags,
     case OP_CONST_STRING:
     case OP_CONST_STRING_JUMBO:
         assert(gDvm.classJavaLangString != NULL);
-        if (decInsn.vB >= pDexFile->pHeader->stringIdsSize) {
-            LOG_VFY("VFY: invalid string pool index %u\n", decInsn.vB);
-            okay = false;
-        } else {
-            setRegisterType(workRegs, insnRegCount, decInsn.vA,
-                regTypeFromClass(gDvm.classJavaLangString), &okay);
-        }
+        setRegisterType(workRegs, insnRegCount, decInsn.vA,
+            regTypeFromClass(gDvm.classJavaLangString), &okay);
         break;
     case OP_CONST_CLASS:
         assert(gDvm.classJavaLangClass != NULL);
-        if (decInsn.vB >= pDexFile->pHeader->typeIdsSize) {
-            LOG_VFY("VFY: invalid class pool index %u\n", decInsn.vB);
-            okay = false;
-        } else {
-            setRegisterType(workRegs, insnRegCount, decInsn.vA,
-                regTypeFromClass(gDvm.classJavaLangClass), &okay);
-        }
+        setRegisterType(workRegs, insnRegCount, decInsn.vA,
+            regTypeFromClass(gDvm.classJavaLangClass), &okay);
         break;
 
     case OP_MONITOR_ENTER:
@@ -3337,9 +3481,10 @@ static bool verifyInstruction(const Method* meth, InsnFlags* insnFlags,
          */
         resClass = dvmOptResolveClass(meth->clazz, decInsn.vB);
         if (resClass == NULL) {
+            const char* badClassDesc = dexStringByTypeIdx(pDexFile, decInsn.vB);
+            logUnableToResolveClass(badClassDesc, meth);
             LOG_VFY("VFY: unable to resolve check-cast %d (%s) in %s\n",
-                    decInsn.vB, dexStringByTypeIdx(pDexFile, decInsn.vB),
-                    meth->clazz->descriptor);
+                decInsn.vB, badClassDesc, meth->clazz->descriptor);
             okay = false;
         } else {
             RegType origType;
@@ -3358,11 +3503,6 @@ static bool verifyInstruction(const Method* meth, InsnFlags* insnFlags,
         }
         break;
     case OP_INSTANCE_OF:
-        if (decInsn.vC >= pDexFile->pHeader->typeIdsSize) {
-            LOG_VFY("VFY: invalid class pool index %u\n", decInsn.vC);
-            okay = false;
-            break;
-        }
         tmpType = getRegisterType(workRegs, insnRegCount, decInsn.vB, &okay);
         if (!okay)
             break;
@@ -3399,9 +3539,10 @@ static bool verifyInstruction(const Method* meth, InsnFlags* insnFlags,
          */
         resClass = dvmOptResolveClass(meth->clazz, decInsn.vB);
         if (resClass == NULL) {
+            const char* badClassDesc = dexStringByTypeIdx(pDexFile, decInsn.vB);
+            logUnableToResolveClass(badClassDesc, meth);
             LOG_VFY("VFY: unable to resolve new-instance %d (%s) in %s\n",
-                    decInsn.vB, dexStringByTypeIdx(pDexFile, decInsn.vB),
-                    meth->clazz->descriptor);
+                decInsn.vB, badClassDesc, meth->clazz->descriptor);
             okay = false;
         } else {
             RegType uninitType;
@@ -3426,9 +3567,10 @@ static bool verifyInstruction(const Method* meth, InsnFlags* insnFlags,
     case OP_NEW_ARRAY:
         resClass = dvmOptResolveClass(meth->clazz, decInsn.vC);
         if (resClass == NULL) {
+            const char* badClassDesc = dexStringByTypeIdx(pDexFile, decInsn.vB);
+            logUnableToResolveClass(badClassDesc, meth);
             LOG_VFY("VFY: unable to resolve new-array %d (%s) in %s\n",
-                    decInsn.vC, dexStringByTypeIdx(pDexFile, decInsn.vB),
-                    meth->clazz->descriptor);
+                decInsn.vC, badClassDesc, meth->clazz->descriptor);
             okay = false;
         } else if (!dvmIsArrayClass(resClass)) {
             LOG_VFY("VFY: new-array on non-array class\n");
@@ -3444,15 +3586,17 @@ static bool verifyInstruction(const Method* meth, InsnFlags* insnFlags,
         /* (decInsn.vA == 0) is silly, but not illegal */
         resClass = dvmOptResolveClass(meth->clazz, decInsn.vB);
         if (resClass == NULL) {
+            const char* badClassDesc = dexStringByTypeIdx(pDexFile, decInsn.vB);
+            logUnableToResolveClass(badClassDesc, meth);
             LOG_VFY("VFY: unable to resolve filled-array %d (%s) in %s\n",
-                    decInsn.vB, dexStringByTypeIdx(pDexFile, decInsn.vB),
-                    meth->clazz->descriptor);
+                decInsn.vB, badClassDesc, meth->clazz->descriptor);
             okay = false;
         } else if (!dvmIsArrayClass(resClass)) {
             LOG_VFY("VFY: filled-new-array on non-array class\n");
             okay = false;
         } else {
             /*
+             * TODO: verify decInsn.vA range
              * TODO: if resClass is array of references, verify the registers
              * in the argument list against the array type.
              * TODO: if resClass is array of primitives, verify that the
@@ -3537,7 +3681,7 @@ static bool verifyInstruction(const Method* meth, InsnFlags* insnFlags,
                 resClass->elementClass->primitiveType == PRIM_NOT ||
                 resClass->elementClass->primitiveType == PRIM_VOID)
             {
-                LOG_VFY("VFY: invalid fill-array-data on %s\n", 
+                LOG_VFY("VFY: invalid fill-array-data on %s\n",
                         resClass->descriptor);
                 okay = false;
                 break;
@@ -3547,17 +3691,17 @@ static bool verifyInstruction(const Method* meth, InsnFlags* insnFlags,
                                     resClass->elementClass->primitiveType);
             assert(valueType != kRegTypeUnknown);
 
-            /* 
+            /*
              * Now verify if the element width in the table matches the element
              * width declared in the array
              */
             arrayData = insns + (insns[1] | (((s4)insns[2]) << 16));
             if (arrayData[0] != kArrayDataSignature) {
-                LOG_VFY("VFY: invalid magic for array-data\n"); 
+                LOG_VFY("VFY: invalid magic for array-data\n");
                 okay = false;
                 break;
             }
-            
+
             switch (resClass->elementClass->primitiveType) {
                 case PRIM_BOOLEAN:
                 case PRIM_BYTE:
@@ -3580,14 +3724,14 @@ static bool verifyInstruction(const Method* meth, InsnFlags* insnFlags,
                      break;
             }
 
-            /* 
+            /*
              * Since we don't compress the data in Dex, expect to see equal
              * width of data stored in the table and expected from the array
              * class.
              */
             if (arrayData[1] != elemWidth) {
-                LOG_VFY("VFY: array-data size mismatch (%d vs %d)\n", 
-                        arrayData[1], elemWidth); 
+                LOG_VFY("VFY: array-data size mismatch (%d vs %d)\n",
+                        arrayData[1], elemWidth);
                 okay = false;
             }
         }
@@ -3678,30 +3822,37 @@ static bool verifyInstruction(const Method* meth, InsnFlags* insnFlags,
         goto aget_1nr_common;
 aget_1nr_common:
         {
-            RegType srcType;
+            RegType srcType, indexType;
+
+            indexType = getRegisterType(workRegs, insnRegCount, decInsn.vC,
+                            &okay);
+            checkArrayIndexType(meth, indexType, &okay);
+            if (!okay)
+                break;
 
             resClass = getClassFromRegister(workRegs, insnRegCount,
                             decInsn.vB, &okay);
             if (!okay)
                 break;
             if (resClass != NULL) {
-                /* verify the class and check "tmpType" */
+                /* verify the class */
                 if (!dvmIsArrayClass(resClass) || resClass->arrayDim != 1 ||
                     resClass->elementClass->primitiveType == PRIM_NOT)
                 {
-                    LOG_VFY("VFY: invalid aget-1nr on %s\n",
-                            resClass->descriptor);
+                    LOG_VFY("VFY: invalid aget-1nr target %s\n",
+                        resClass->descriptor);
                     okay = false;
                     break;
                 }
 
+                /* make sure array type matches instruction */
                 srcType = primitiveTypeToRegType(
                                         resClass->elementClass->primitiveType);
 
-                if (!canConvertTo1nr(srcType, tmpType)) {
-                    LOG_VFY("VFY: unable to aget array type=%d into local type=%d"
-                            " (on %s)\n",
-                            srcType, tmpType, resClass->descriptor);
+                if (!isTypeWidthEqual1nr(tmpType, srcType)) {
+                    LOG_VFY("VFY: invalid aget-1nr, array type=%d with"
+                            " inst type=%d (on %s)\n",
+                        srcType, tmpType, resClass->descriptor);
                     okay = false;
                     break;
                 }
@@ -3714,23 +3865,30 @@ aget_1nr_common:
 
     case OP_AGET_WIDE:
         {
-            RegType dstType = kRegTypeUnknown;
+            RegType dstType, indexType;
+
+            indexType = getRegisterType(workRegs, insnRegCount, decInsn.vC,
+                            &okay);
+            checkArrayIndexType(meth, indexType, &okay);
+            if (!okay)
+                break;
 
             resClass = getClassFromRegister(workRegs, insnRegCount,
                             decInsn.vB, &okay);
             if (!okay)
                 break;
             if (resClass != NULL) {
-                /* verify the class and try to refine "dstType" */
+                /* verify the class */
                 if (!dvmIsArrayClass(resClass) || resClass->arrayDim != 1 ||
                     resClass->elementClass->primitiveType == PRIM_NOT)
                 {
-                    LOG_VFY("VFY: invalid aget-wide on %s\n",
-                            resClass->descriptor);
+                    LOG_VFY("VFY: invalid aget-wide target %s\n",
+                        resClass->descriptor);
                     okay = false;
                     break;
                 }
 
+                /* try to refine "dstType" */
                 switch (resClass->elementClass->primitiveType) {
                 case PRIM_LONG:
                     dstType = kRegTypeLongLo;
@@ -3740,11 +3898,19 @@ aget_1nr_common:
                     break;
                 default:
                     LOG_VFY("VFY: invalid aget-wide on %s\n",
-                            resClass->descriptor);
+                        resClass->descriptor);
                     dstType = kRegTypeUnknown;
                     okay = false;
                     break;
                 }
+            } else {
+                /*
+                 * Null array ref; this code path will fail at runtime.  We
+                 * know this is either long or double, and we don't really
+                 * discriminate between those during verification, so we
+                 * call it a long.
+                 */
+                dstType = kRegTypeLongLo;
             }
             setRegisterType(workRegs, insnRegCount, decInsn.vA,
                 dstType, &okay);
@@ -3753,7 +3919,13 @@ aget_1nr_common:
 
     case OP_AGET_OBJECT:
         {
-            RegType dstType;
+            RegType dstType, indexType;
+
+            indexType = getRegisterType(workRegs, insnRegCount, decInsn.vC,
+                            &okay);
+            checkArrayIndexType(meth, indexType, &okay);
+            if (!okay)
+                break;
 
             resClass = getClassFromRegister(workRegs, insnRegCount,
                             decInsn.vB, &okay);
@@ -3816,7 +3988,13 @@ aget_1nr_common:
         goto aput_1nr_common;
 aput_1nr_common:
         {
-            RegType srcType, dstType;
+            RegType srcType, dstType, indexType;
+
+            indexType = getRegisterType(workRegs, insnRegCount, decInsn.vC,
+                            &okay);
+            checkArrayIndexType(meth, indexType, &okay);
+            if (!okay)
+                break;
 
             /* make sure the source register has the correct type */
             srcType = getRegisterType(workRegs, insnRegCount, decInsn.vA,
@@ -3845,22 +4023,29 @@ aput_1nr_common:
                 break;
             }
 
+            /* verify that instruction matches array */
             dstType = primitiveTypeToRegType(
                                     resClass->elementClass->primitiveType);
             assert(dstType != kRegTypeUnknown);
 
-            if (!canConvertTo1nr(srcType, dstType)) {
-                LOG_VFY("VFY: invalid aput-1nr on %s (src=%d dst=%d)\n",
-                        resClass->descriptor, srcType, dstType);
+            if (!isTypeWidthEqual1nr(tmpType, dstType)) {
+                LOG_VFY("VFY: invalid aput-1nr on %s (inst=%d dst=%d)\n",
+                        resClass->descriptor, tmpType, dstType);
                 okay = false;
                 break;
             }
         }
         break;
     case OP_APUT_WIDE:
+        tmpType = getRegisterType(workRegs, insnRegCount, decInsn.vC,
+                        &okay);
+        checkArrayIndexType(meth, tmpType, &okay);
+        if (!okay)
+            break;
+
         tmpType = getRegisterType(workRegs, insnRegCount, decInsn.vA, &okay);
         if (okay) {
-            RegType typeHi = 
+            RegType typeHi =
                 getRegisterType(workRegs, insnRegCount, decInsn.vA+1, &okay);
             checkTypeCategory(tmpType, kTypeCategory2, &okay);
             checkWidePair(tmpType, typeHi, &okay);
@@ -3897,6 +4082,12 @@ aput_1nr_common:
         }
         break;
     case OP_APUT_OBJECT:
+        tmpType = getRegisterType(workRegs, insnRegCount, decInsn.vC,
+                        &okay);
+        checkArrayIndexType(meth, tmpType, &okay);
+        if (!okay)
+            break;
+
         /* get the ref we're storing; Zero is okay, Uninit is not */
         resClass = getClassFromRegister(workRegs, insnRegCount,
                         decInsn.vA, &okay);
@@ -3984,9 +4175,9 @@ iget_1nr_common:
             /* make sure the field's type is compatible with expectation */
             fieldType = primSigCharToRegType(instField->field.signature[0]);
             if (fieldType == kRegTypeUnknown ||
-                !canConvertTo1nr(fieldType, tmpType))
+                !isTypeWidthEqual1nr(tmpType, fieldType))
             {
-                LOG_VFY("VFY: invalid iget-1nr of %s.%s (req=%d actual=%d)\n",
+                LOG_VFY("VFY: invalid iget-1nr of %s.%s (inst=%d field=%d)\n",
                         instField->field.clazz->descriptor,
                         instField->field.name, tmpType, fieldType);
                 okay = false;
@@ -4082,7 +4273,7 @@ iput_1nr_common:
             RegType srcType, fieldType, objType;
             ClassObject* fieldClass;
             InstField* instField;
-            
+
             /* make sure the source register has the correct type */
             srcType = getRegisterType(workRegs, insnRegCount, decInsn.vA,
                         &okay);
@@ -4101,15 +4292,18 @@ iput_1nr_common:
                             &okay);
             if (!okay)
                 break;
+            checkFinalFieldAccess(meth, &instField->field, &okay);
+            if (!okay)
+                break;
 
             /* get type of field we're storing into */
             fieldType = primSigCharToRegType(instField->field.signature[0]);
             if (fieldType == kRegTypeUnknown ||
-                !canConvertTo1nr(srcType, fieldType))
+                !isTypeWidthEqual1nr(tmpType, fieldType))
             {
-                LOG_VFY("VFY: invalid iput-1nr of %s.%s (src=%d dst=%d)\n",
+                LOG_VFY("VFY: invalid iput-1nr of %s.%s (inst=%d field=%d)\n",
                         instField->field.clazz->descriptor,
-                        instField->field.name, srcType, fieldType);
+                        instField->field.name, tmpType, fieldType);
                 okay = false;
                 break;
             }
@@ -4118,7 +4312,7 @@ iput_1nr_common:
     case OP_IPUT_WIDE:
         tmpType = getRegisterType(workRegs, insnRegCount, decInsn.vA, &okay);
         if (okay) {
-            RegType typeHi = 
+            RegType typeHi =
                 getRegisterType(workRegs, insnRegCount, decInsn.vA+1, &okay);
             checkTypeCategory(tmpType, kTypeCategory2, &okay);
             checkWidePair(tmpType, typeHi, &okay);
@@ -4136,6 +4330,10 @@ iput_1nr_common:
                             &okay);
             if (!okay)
                 break;
+            checkFinalFieldAccess(meth, &instField->field, &okay);
+            if (!okay)
+                break;
+
             /* check the type, which should be prim */
             switch (instField->field.signature[0]) {
             case 'D':
@@ -4166,6 +4364,10 @@ iput_1nr_common:
                             &okay);
             if (!okay)
                 break;
+            checkFinalFieldAccess(meth, &instField->field, &okay);
+            if (!okay)
+                break;
+
             fieldClass = getFieldClass(meth, &instField->field);
             if (fieldClass == NULL) {
                 LOG_VFY("VFY: unable to recover field class from '%s'\n",
@@ -4232,14 +4434,19 @@ sget_1nr_common:
             if (!okay)
                 break;
 
-            /* make sure the field's type is compatible with expectation */
+            /*
+             * Make sure the field's type is compatible with expectation.
+             * We can get ourselves into trouble if we mix & match loads
+             * and stores with different widths, so rather than just checking
+             * "canConvertTo1nr" we require that the field types have equal
+             * widths.  (We can't generally require an exact type match,
+             * because e.g. "int" and "float" are interchangeable.)
+             */
             fieldType = primSigCharToRegType(staticField->field.signature[0]);
-            if (fieldType == kRegTypeUnknown ||
-                !canConvertTo1nr(fieldType, tmpType))
-            {
-                LOG_VFY("VFY: invalid sget-1nr of %s.%s (req=%d actual=%d)\n",
-                        staticField->field.clazz->descriptor,
-                        staticField->field.name, tmpType, fieldType);
+            if (!isTypeWidthEqual1nr(tmpType, fieldType)) {
+                LOG_VFY("VFY: invalid sget-1nr of %s.%s (inst=%d actual=%d)\n",
+                    staticField->field.clazz->descriptor,
+                    staticField->field.name, tmpType, fieldType);
                 okay = false;
                 break;
             }
@@ -4320,7 +4527,7 @@ sput_1nr_common:
         {
             RegType srcType, fieldType;
             StaticField* staticField;
-            
+
             /* make sure the source register has the correct type */
             srcType = getRegisterType(workRegs, insnRegCount, decInsn.vA,
                         &okay);
@@ -4334,15 +4541,22 @@ sput_1nr_common:
             staticField = getStaticField(meth, decInsn.vB, &okay);
             if (!okay)
                 break;
+            checkFinalFieldAccess(meth, &staticField->field, &okay);
+            if (!okay)
+                break;
 
-            /* get type of field we're storing into */
+            /*
+             * Get type of field we're storing into.  We know that the
+             * contents of the register match the instruction, but we also
+             * need to ensure that the instruction matches the field type.
+             * Using e.g. sput-short to write into a 32-bit integer field
+             * can lead to trouble if we do 16-bit writes.
+             */
             fieldType = primSigCharToRegType(staticField->field.signature[0]);
-            if (fieldType == kRegTypeUnknown ||
-                !canConvertTo1nr(srcType, fieldType))
-            {
-                LOG_VFY("VFY: invalid sput-1nr of %s.%s (req=%d actual=%d)\n",
-                        staticField->field.clazz->descriptor,
-                        staticField->field.name, tmpType, fieldType);
+            if (!isTypeWidthEqual1nr(tmpType, fieldType)) {
+                LOG_VFY("VFY: invalid sput-1nr of %s.%s (inst=%d actual=%d)\n",
+                    staticField->field.clazz->descriptor,
+                    staticField->field.name, tmpType, fieldType);
                 okay = false;
                 break;
             }
@@ -4351,7 +4565,7 @@ sput_1nr_common:
     case OP_SPUT_WIDE:
         tmpType = getRegisterType(workRegs, insnRegCount, decInsn.vA, &okay);
         if (okay) {
-            RegType typeHi = 
+            RegType typeHi =
                 getRegisterType(workRegs, insnRegCount, decInsn.vA+1, &okay);
             checkTypeCategory(tmpType, kTypeCategory2, &okay);
             checkWidePair(tmpType, typeHi, &okay);
@@ -4362,6 +4576,10 @@ sput_1nr_common:
             staticField = getStaticField(meth, decInsn.vB, &okay);
             if (!okay)
                 break;
+            checkFinalFieldAccess(meth, &staticField->field, &okay);
+            if (!okay)
+                break;
+
             /* check the type, which should be prim */
             switch (staticField->field.signature[0]) {
             case 'D':
@@ -4387,6 +4605,10 @@ sput_1nr_common:
             staticField = getStaticField(meth, decInsn.vB, &okay);
             if (!okay)
                 break;
+            checkFinalFieldAccess(meth, &staticField->field, &okay);
+            if (!okay)
+                break;
+
             fieldClass = getFieldClass(meth, &staticField->field);
             if (fieldClass == NULL) {
                 LOG_VFY("VFY: unable to recover field class from '%s'\n",
@@ -4492,7 +4714,7 @@ sput_1nr_common:
                 }
 
                 ClassObject* thisClass;
-                
+
                 thisClass = regTypeReferenceToClass(thisType, uninitMap);
                 assert(thisClass != NULL);
 
@@ -4947,6 +5169,13 @@ sput_1nr_common:
 
     /*
      * Handle "branch".  Tag the branch target.
+     *
+     * NOTE: instructions like OP_EQZ provide information about the state
+     * of the register when the branch is taken or not taken.  For example,
+     * somebody could get a reference field, check it for zero, and if the
+     * branch is taken immediately store that register in a boolean field
+     * since the value is known to be zero.  We do not currently account for
+     * that, and will reject the code.
      */
     if ((nextFlags & kInstrCanBranch) != 0) {
         bool isConditional;
@@ -5058,7 +5287,7 @@ bail:
 /*
  * callback function used in dumpRegTypes to print local vars
  * valid at a given address.
- */ 
+ */
 static void logLocalsCb(void *cnxt, u2 reg, u4 startAddress, u4 endAddress,
         const char *name, const char *descriptor,
         const char *signature)
@@ -5146,7 +5375,7 @@ static void dumpRegTypes(const Method* meth, const InsnFlags* insnFlags,
             if (regTypeIsReference(addrRegs[i]) && addrRegs[i] != kRegTypeZero)
             {
                 ClassObject* clazz;
-                
+
                 clazz = regTypeReferenceToClass(addrRegs[i], uninitMap);
                 assert(dvmValidateObject((Object*)clazz));
                 if (i < regCount) {
@@ -5172,3 +5401,4 @@ static void dumpRegTypes(const Method* meth, const InsnFlags* insnFlags,
                 NULL, logLocalsCb, &addr);
     }
 }
+
diff --git a/vm/analysis/DexOptimize.c b/vm/analysis/DexOptimize.c
index a726bf97e..90e4c6feb 100644
--- a/vm/analysis/DexOptimize.c
+++ b/vm/analysis/DexOptimize.c
@@ -13,6 +13,7 @@
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */
+
 /*
  * Convert the output from "dx" into a locally-optimized DEX file.
  *
@@ -45,14 +46,17 @@ typedef struct InlineSub {
     int     inlineIdx;
 } InlineSub;
 
+
 /* fwd */
 static int writeDependencies(int fd, u4 modWhen, u4 crc);
-static bool writeAuxData(int fd, const DexClassLookup* pClassLookup);
+static bool writeAuxData(int fd, const DexClassLookup* pClassLookup,\
+    const IndexMapSet* pIndexMapSet);
 static void logFailedWrite(size_t expected, ssize_t actual, const char* msg,
     int err);
 
 static bool rewriteDex(u1* addr, int len, bool doVerify, bool doOpt,\
     u4* pHeaderFlags, DexClassLookup** ppClassLookup);
+static void updateChecksum(u1* addr, int len, DexHeader* pHeader);
 static bool loadAllClasses(DvmDex* pDvmDex);
 static void optimizeLoadedClasses(DexFile* pDexFile);
 static void optimizeClass(ClassObject* clazz, const InlineSub* inlineSubs);
@@ -87,21 +91,15 @@ static bool rewriteExecuteInline(Method* method, u2* insns,
  * file header, and will be locked with flock.  "*pCachedName" will point
  * to newly-allocated storage.
  */
-int dvmOpenCachedDexFile(const char* fileName, const char* subFileName,
-    u4 modWhen, u4 crc, bool isBootstrap, char** pCachedName, bool* pNewFile,
-    bool createIfMissing)
+int dvmOpenCachedDexFile(const char* fileName, const char* cacheFileName,
+    u4 modWhen, u4 crc, bool isBootstrap, bool* pNewFile, bool createIfMissing)
 {
-    char cacheFileName[512];
     int fd, cc;
     struct stat fdStat, fileStat;
     bool readOnly = false;
 
     *pNewFile = false;
 
-    if (!dexOptGenerateCacheFileName(fileName, subFileName, cacheFileName,
-            sizeof(cacheFileName)))
-        return -1;
-
 retry:
     /*
      * Try to open the cache file.  If we've been asked to,
@@ -156,7 +154,7 @@ retry:
         goto close_fail;
     }
     cc = stat(cacheFileName, &fileStat);
-    if (cc != 0 || 
+    if (cc != 0 ||
         fdStat.st_dev != fileStat.st_dev || fdStat.st_ino != fileStat.st_ino)
     {
         LOGD("DexOpt: our open cache file is stale; sleeping and retrying\n");
@@ -262,8 +260,6 @@ retry:
         }
     }
 
-    *pCachedName = strdup(cacheFileName);
-
     assert(fd >= 0);
     return fd;
 
@@ -316,7 +312,7 @@ bool dvmOptimizeDexFile(int fd, off_t dexOffset, long dexLength,
     if (lastPart != NULL)
         lastPart++;
     else
-        lastPart = "";
+        lastPart = fileName;
 
     /*
      * For basic optimizations (byte-swapping and structure aligning) we
@@ -487,8 +483,8 @@ bool dvmOptimizeDexFile(int fd, off_t dexOffset, long dexLength,
 }
 
 /*
- * Do the actual optimization.  This is called directly, for "minimal"
- * optimization, or from a newly-created process.
+ * Do the actual optimization.  This is called directly for "minimal"
+ * optimization, or from a newly-created process for "full" optimization.
  *
  * For best use of disk/memory, we want to extract once and perform
  * optimizations in place.  If the file has to expand or contract
@@ -504,6 +500,7 @@ bool dvmContinueOptimization(int fd, off_t dexOffset, long dexLength,
     const char* fileName, u4 modWhen, u4 crc, bool isBootstrap)
 {
     DexClassLookup* pClassLookup = NULL;
+    IndexMapSet* pIndexMapSet = NULL;
     bool doVerify, doOpt;
     u4 headerFlags = 0;
 
@@ -531,6 +528,10 @@ bool dvmContinueOptimization(int fd, off_t dexOffset, long dexLength,
         LOGE("too small to be DEX\n");
         return false;
     }
+    if (dexOffset < (int) sizeof(DexOptHeader)) {
+        LOGE("not enough room for opt header\n");
+        return false;
+    }
 
     bool result = false;
 
@@ -543,9 +544,9 @@ bool dvmContinueOptimization(int fd, off_t dexOffset, long dexLength,
 
     {
         /*
-         * Map the entire file (so we don't have to worry about page alignment).
-         * The expectation is that the output file contains our DEX data plus
-         * a small header.
+         * Map the entire file (so we don't have to worry about page
+         * alignment).  The expectation is that the output file contains
+         * our DEX data plus room for a small header.
          */
         bool success;
         void* mapAddr;
@@ -564,6 +565,29 @@ bool dvmContinueOptimization(int fd, off_t dexOffset, long dexLength,
         success = rewriteDex(((u1*) mapAddr) + dexOffset, dexLength,
                     doVerify, doOpt, &headerFlags, &pClassLookup);
 
+        if (success) {
+            DvmDex* pDvmDex = NULL;
+            u1* dexAddr = ((u1*) mapAddr) + dexOffset;
+
+            if (dvmDexFileOpenPartial(dexAddr, dexLength, &pDvmDex) != 0) {
+                LOGE("Unable to create DexFile\n");
+            } else {
+                /*
+                 * If configured to do so, scan the instructions, looking
+                 * for ways to reduce the size of the resolved-constant table.
+                 * This is done post-optimization, across the instructions
+                 * in all methods in all classes (even the ones that failed
+                 * to load).
+                 */
+                pIndexMapSet = dvmRewriteConstants(pDvmDex);
+
+                updateChecksum(dexAddr, dexLength,
+                    (DexHeader*) pDvmDex->pHeader);
+
+                dvmDexFileFree(pDvmDex);
+            }
+        }
+
         /* unmap the read-write version, forcing writes to disk */
         if (msync(mapAddr, dexOffset + dexLength, MS_SYNC) != 0) {
             LOGW("msync failed: %s\n", strerror(errno));
@@ -627,7 +651,7 @@ bool dvmContinueOptimization(int fd, off_t dexOffset, long dexLength,
     /*
      * Append any auxillary pre-computed data structures.
      */
-    if (!writeAuxData(fd, pClassLookup)) {
+    if (!writeAuxData(fd, pClassLookup, pIndexMapSet)) {
         LOGW("Failed writing aux data\n");
         goto bail;
     }
@@ -664,6 +688,7 @@ bool dvmContinueOptimization(int fd, off_t dexOffset, long dexLength,
     result = true;
 
 bail:
+    dvmFreeIndexMapSet(pIndexMapSet);
     free(pClassLookup);
     return result;
 }
@@ -995,30 +1020,85 @@ static int writeDependencies(int fd, u4 modWhen, u4 crc)
     return result;
 }
 
+
 /*
- * Write aux data.
+ * Write a block of data in "chunk" format.
  *
- * At the moment this is just the DexClassLookup structure.  In theory we
- * will tuck other stuff in here.  When theory becomes reality, we will need
- * to stow a TOC in here (or use a "chunk" format).  Until then we just
- * write a zero into the first 4 bytes so future generations have something
- * to test for.
+ * The chunk header fields are always in "native" byte order.  If "size"
+ * is not a multiple of 8 bytes, the data area is padded out.
  */
-static bool writeAuxData(int fd, const DexClassLookup* pClassLookup)
+static bool writeChunk(int fd, u4 type, const void* data, size_t size)
 {
-    DexFile* pDexFile;
     ssize_t actual;
-    int zero = 0;
+    union {             /* save a syscall by grouping these together */
+        char raw[8];
+        struct {
+            u4 type;
+            u4 size;
+        } ts;
+    } header;
+
+    assert(sizeof(header) == 8);
+
+    LOGV("Writing chunk, type=%.4s size=%d\n", (char*) &type, size);
+
+    header.ts.type = type;
+    header.ts.size = (u4) size;
+    actual = write(fd, &header, sizeof(header));
+    if (actual != sizeof(header)) {
+        logFailedWrite(size, actual, "aux chunk header write", errno);
+        return false;
+    }
+
+    if (size > 0) {
+        actual = write(fd, data, size);
+        if (actual != (ssize_t) size) {
+            logFailedWrite(size, actual, "aux chunk write", errno);
+            return false;
+        }
+    }
+
+    /* if necessary, pad to 64-bit alignment */
+    if ((size & 7) != 0) {
+        int padSize = 8 - (size & 7);
+        LOGV("size was %d, inserting %d pad bytes\n", size, padSize);
+        lseek(fd, padSize, SEEK_CUR);
+    }
+
+    assert( ((int)lseek(fd, 0, SEEK_CUR) & 7) == 0);
+
+    return true;
+}
 
-    actual = write(fd, &zero, sizeof(zero));
-    if (actual != sizeof(zero)) {
-        logFailedWrite(sizeof(zero), actual, "aux header", errno);
+/*
+ * Write aux data.
+ *
+ * We have different pieces, some of which may be optional.  To make the
+ * most effective use of space, we use a "chunk" format, with a 4-byte
+ * type and a 4-byte length.  We guarantee 64-bit alignment for the data,
+ * so it can be used directly when the file is mapped for reading.
+ */
+static bool writeAuxData(int fd, const DexClassLookup* pClassLookup,
+    const IndexMapSet* pIndexMapSet)
+{
+    /* pre-computed class lookup hash table */
+    if (!writeChunk(fd, (u4) kDexChunkClassLookup, pClassLookup,
+            pClassLookup->size))
+    {
         return false;
     }
 
-    actual = write(fd, pClassLookup, pClassLookup->size);
-    if (actual != pClassLookup->size) {
-        logFailedWrite(pClassLookup->size, actual, "class lookup table", errno);
+    /* remapped constants (optional) */
+    if (pIndexMapSet != NULL) {
+        if (!writeChunk(fd, pIndexMapSet->chunkType, pIndexMapSet->chunkData,
+                pIndexMapSet->chunkDataLen))
+        {
+            return false;
+        }
+    }
+
+    /* write the end marker */
+    if (!writeChunk(fd, (u4) kDexChunkEnd, NULL, 0)) {
         return false;
     }
 
@@ -1134,15 +1214,30 @@ static bool rewriteDex(u1* addr, int len, bool doVerify, bool doOpt,
     result = true;
 
 bail:
-    /*
-     * Free up storage.
-     */
+    /* free up storage */
     dvmDexFileFree(pDvmDex);
 
     return result;
 }
 
 /*
+ * Update the Adler-32 checksum stored in the DEX file.  This covers the
+ * swapped and optimized DEX data, but does not include the opt header
+ * or auxillary data.
+ */
+static void updateChecksum(u1* addr, int len, DexHeader* pHeader)
+{
+    /*
+     * Rewrite the checksum.  We leave the SHA-1 signature alone.
+     */
+    uLong adler = adler32(0L, Z_NULL, 0);
+    const int nonSum = sizeof(pHeader->magic) + sizeof(pHeader->checksum);
+
+    adler = adler32(adler, addr + nonSum, len - nonSum);
+    pHeader->checksum = adler;
+}
+
+/*
  * Try to load all classes in the specified DEX.  If they have some sort
  * of broken dependency, e.g. their superclass lives in a different DEX
  * that wasn't previously loaded into the bootstrap class path, loading
@@ -1187,7 +1282,7 @@ static bool loadAllClasses(DvmDex* pDvmDex)
         const DexClassDef* pClassDef;
         const char* classDescriptor;
         ClassObject* newClass;
-        
+
         pClassDef = dexGetClassDef(pDvmDex->pDexFile, idx);
         classDescriptor =
             dexStringByTypeIdx(pDvmDex->pDexFile, pClassDef->classIdx);
@@ -1251,12 +1346,6 @@ static InlineSub* createInlineSubsTable(void)
              * Method could be virtual or direct.  Try both.  Don't use
              * the "hier" versions.
              */
-            if (!dvmIsFinalClass(clazz)) {
-                LOGW("DexOpt: WARNING: inline op on non-final class '%s'\n",
-                    clazz->descriptor);
-                // TODO: final methods in non-final classes are okay too
-                /* keep going, I guess */
-            }
             method = dvmFindDirectMethodByDescriptor(clazz, ops[i].methodName,
                         ops[i].methodSignature);
             if (method == NULL)
@@ -1267,6 +1356,21 @@ static InlineSub* createInlineSubsTable(void)
                     ops[i].classDescriptor, ops[i].methodName,
                     ops[i].methodSignature);
             } else {
+                if (!dvmIsFinalClass(clazz) && !dvmIsFinalMethod(method)) {
+                    LOGW("DexOpt: WARNING: inline op on non-final class/method "
+                         "%s.%s\n",
+                        clazz->descriptor, method->name);
+                    /* fail? */
+                }
+                if (dvmIsSynchronizedMethod(method) ||
+                    dvmIsDeclaredSynchronizedMethod(method))
+                {
+                    LOGW("DexOpt: WARNING: inline op on synchronized method "
+                         "%s.%s\n",
+                        clazz->descriptor, method->name);
+                    /* fail? */
+                }
+
                 table[tableIndex].method = method;
                 table[tableIndex].inlineIdx = i;
                 tableIndex++;
@@ -1304,9 +1408,9 @@ static void optimizeLoadedClasses(DexFile* pDexFile)
         const DexClassDef* pClassDef;
         const char* classDescriptor;
         ClassObject* clazz;
-        
+
         pClassDef = dexGetClassDef(pDexFile, idx);
-        classDescriptor= dexStringByTypeIdx(pDexFile, pClassDef->classIdx);
+        classDescriptor = dexStringByTypeIdx(pDexFile, pClassDef->classIdx);
 
         /* all classes are loaded into the bootstrap class loader */
         clazz = dvmLookupClass(classDescriptor, NULL, false);
@@ -1332,7 +1436,7 @@ static void optimizeLoadedClasses(DexFile* pDexFile)
                 classDescriptor);
         }
     }
-    
+
     free(inlineSubs);
 }
 
diff --git a/vm/analysis/DexOptimize.h b/vm/analysis/DexOptimize.h
index 207140bbb..ecb71d32f 100644
--- a/vm/analysis/DexOptimize.h
+++ b/vm/analysis/DexOptimize.h
@@ -39,9 +39,8 @@ typedef enum DexOptimizerMode {
  *
  * Returns the file descriptor, locked and seeked past the "opt" header.
  */
-int dvmOpenCachedDexFile(const char* fileName, const char* subFileName,
-    u4 modWhen, u4 crc, bool isBootstrap, char** pCachedName, bool* pNewFile,
-    bool createIfMissing);
+int dvmOpenCachedDexFile(const char* fileName, const char* cachedFile,
+    u4 modWhen, u4 crc, bool isBootstrap, bool* pNewFile, bool createIfMissing);
 
 /*
  * Unlock the specified file descriptor.  Use in conjunction with
diff --git a/vm/analysis/DexVerify.c b/vm/analysis/DexVerify.c
index ab1e50b4f..3b69e8326 100644
--- a/vm/analysis/DexVerify.c
+++ b/vm/analysis/DexVerify.c
@@ -13,6 +13,7 @@
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */
+
 /*
  * Dalvik classfile verification.  This file contains the verifier entry
  * points and the static constraint checks.
@@ -36,8 +37,6 @@ static bool setTryFlags(const Method* meth, InsnFlags* insnFlags);
 static bool verifyMethod(Method* meth, int verifyFlags);
 static bool verifyInstructions(const Method* meth, InsnFlags* insnFlags,
     int verifyFlags);
-static bool checkNewInstance(const Method* meth, int insnIdx);
-static bool checkNewArray(const Method* meth, int insnIdx);
 
 
 /*
@@ -90,7 +89,7 @@ bool dvmVerifyAllClasses(DexFile* pDexFile)
         const DexClassDef* pClassDef;
         const char* classDescriptor;
         ClassObject* clazz;
-        
+
         pClassDef = dexGetClassDef(pDexFile, idx);
         classDescriptor = dexStringByTypeIdx(pDexFile, pClassDef->classIdx);
 
@@ -197,7 +196,17 @@ static bool verifyMethod(Method* meth, int verifyFlags)
 
         goto success;
     }
-        
+
+    /*
+     * Sanity-check the register counts.  ins + locals = registers, so make
+     * sure that ins <= registers.
+     */
+    if (meth->insSize > meth->registersSize) {
+        LOG_VFY_METH(meth, "VFY: bad register counts (ins=%d regs=%d)\n",
+            meth->insSize, meth->registersSize);
+        goto bail;
+    }
+
     /*
      * Allocate and populate an array to hold instruction data.
      *
@@ -281,16 +290,14 @@ static bool computeCodeWidths(const Method* meth, InsnFlags* insnFlags,
         int width;
 
         /*
-         * Switch tables are identified with "extended NOP" opcodes.  They
-         * contain no executable code, so we can just skip past them.
+         * Switch tables and array data tables are identified with
+         * "extended NOP" opcodes.  They contain no executable code,
+         * so we can just skip past them.
          */
         if (*insns == kPackedSwitchSignature) {
             width = 4 + insns[1] * 2;
         } else if (*insns == kSparseSwitchSignature) {
             width = 2 + insns[1] * 4;
-        /*
-         * Array data table is identified with similar extended NOP opcode.
-         */
         } else if (*insns == kArrayDataSignature) {
             u4 size = insns[2] | (((u4)insns[3]) << 16);
             width = 4 + (insns[1] * size + 1) / 2;
@@ -396,7 +403,7 @@ static bool setTryFlags(const Method* meth, InsnFlags* insnFlags)
         for (;;) {
             DexCatchHandler* handler = dexCatchIteratorNext(&iterator);
             u4 addr;
-            
+
             if (handler == NULL) {
                 break;
             }
@@ -408,7 +415,7 @@ static bool setTryFlags(const Method* meth, InsnFlags* insnFlags)
                     addr);
                 return false;
             }
-        
+
             dvmInsnSetBranchTarget(insnFlags, addr, true);
         }
 
@@ -481,7 +488,7 @@ static bool checkSwitchTargets(const Method* meth, InsnFlags* insnFlags,
     /* for a sparse switch, verify the keys are in ascending order */
     if (offsetToKeys > 0 && switchCount > 1) {
         s4 lastKey;
-        
+
         lastKey = switchInsns[offsetToKeys] |
                   (switchInsns[offsetToKeys+1] << 16);
         for (targ = 1; targ < switchCount; targ++) {
@@ -625,6 +632,162 @@ static bool checkBranchTarget(const Method* meth, InsnFlags* insnFlags,
     return true;
 }
 
+
+/*
+ * Decode the current instruction.
+ */
+static void decodeInstruction(const Method* meth, int insnIdx,
+    DecodedInstruction* pDecInsn)
+{
+    dexDecodeInstruction(gDvm.instrFormat, meth->insns + insnIdx, pDecInsn);
+}
+
+
+/*
+ * Perform static checks on a "new-instance" instruction.  Specifically,
+ * make sure the class reference isn't for an array class.
+ *
+ * We don't need the actual class, just a pointer to the class name.
+ */
+static bool checkNewInstance(const Method* meth, int insnIdx)
+{
+    DexFile* pDexFile = meth->clazz->pDvmDex->pDexFile;
+    DecodedInstruction decInsn;
+    const char* classDescriptor;
+
+    decodeInstruction(meth, insnIdx, &decInsn);
+    classDescriptor = dexStringByTypeIdx(pDexFile, decInsn.vB); // 2nd item
+
+    if (classDescriptor[0] != 'L') {
+        LOG_VFY_METH(meth, "VFY: can't call new-instance on type '%s'\n",
+            classDescriptor);
+        return false;
+    }
+
+    return true;
+}
+
+/*
+ * Perform static checks on a "new-array" instruction.  Specifically, make
+ * sure they aren't creating an array of arrays that causes the number of
+ * dimensions to exceed 255.
+ */
+static bool checkNewArray(const Method* meth, int insnIdx)
+{
+    DexFile* pDexFile = meth->clazz->pDvmDex->pDexFile;
+    DecodedInstruction decInsn;
+    const char* classDescriptor;
+
+    decodeInstruction(meth, insnIdx, &decInsn);
+    classDescriptor = dexStringByTypeIdx(pDexFile, decInsn.vC); // 3rd item
+
+    int bracketCount = 0;
+    const char* cp = classDescriptor;
+    while (*cp++ == '[')
+        bracketCount++;
+
+    if (bracketCount == 0) {
+        /* The given class must be an array type. */
+        LOG_VFY_METH(meth, "VFY: can't new-array class '%s' (not an array)\n",
+            classDescriptor);
+        return false;
+    } else if (bracketCount > 255) {
+        /* It is illegal to create an array of more than 255 dimensions. */
+        LOG_VFY_METH(meth, "VFY: can't new-array class '%s' (exceeds limit)\n",
+            classDescriptor);
+        return false;
+    }
+
+    return true;
+}
+
+/*
+ * Perform static checks on an instruction that takes a class constant.
+ * Ensure that the class index is in the valid range.
+ */
+static bool checkTypeIndex(const Method* meth, int insnIdx, bool useB)
+{
+    DvmDex* pDvmDex = meth->clazz->pDvmDex;
+    DecodedInstruction decInsn;
+    u4 idx;
+
+    decodeInstruction(meth, insnIdx, &decInsn);
+    if (useB)
+        idx = decInsn.vB;
+    else
+        idx = decInsn.vC;
+    if (idx >= pDvmDex->pHeader->typeIdsSize) {
+        LOG_VFY_METH(meth, "VFY: bad type index %d (max %d)\n",
+            idx, pDvmDex->pHeader->typeIdsSize);
+        return false;
+    }
+
+    return true;
+}
+
+/*
+ * Perform static checks on a field get or set instruction.  All we do
+ * here is ensure that the field index is in the valid range.
+ */
+static bool checkFieldIndex(const Method* meth, int insnIdx, bool useB)
+{
+    DvmDex* pDvmDex = meth->clazz->pDvmDex;
+    DecodedInstruction decInsn;
+    u4 idx;
+
+    decodeInstruction(meth, insnIdx, &decInsn);
+    if (useB)
+        idx = decInsn.vB;
+    else
+        idx = decInsn.vC;
+    if (idx >= pDvmDex->pHeader->fieldIdsSize) {
+        LOG_VFY_METH(meth,
+            "VFY: bad field index %d (max %d) at offset 0x%04x\n",
+            idx, pDvmDex->pHeader->fieldIdsSize, insnIdx);
+        return false;
+    }
+
+    return true;
+}
+
+/*
+ * Perform static checks on a method invocation instruction.  All we do
+ * here is ensure that the method index is in the valid range.
+ */
+static bool checkMethodIndex(const Method* meth, int insnIdx)
+{
+    DvmDex* pDvmDex = meth->clazz->pDvmDex;
+    DecodedInstruction decInsn;
+
+    decodeInstruction(meth, insnIdx, &decInsn);
+    if (decInsn.vB >= pDvmDex->pHeader->methodIdsSize) {
+        LOG_VFY_METH(meth, "VFY: bad method index %d (max %d)\n",
+            decInsn.vB, pDvmDex->pHeader->methodIdsSize);
+        return false;
+    }
+
+    return true;
+}
+
+/*
+ * Perform static checks on a string constant instruction.  All we do
+ * here is ensure that the string index is in the valid range.
+ */
+static bool checkStringIndex(const Method* meth, int insnIdx)
+{
+    DvmDex* pDvmDex = meth->clazz->pDvmDex;
+    DecodedInstruction decInsn;
+
+    decodeInstruction(meth, insnIdx, &decInsn);
+    if (decInsn.vB >= pDvmDex->pHeader->stringIdsSize) {
+        LOG_VFY_METH(meth, "VFY: bad string index %d (max %d)\n",
+            decInsn.vB, pDvmDex->pHeader->stringIdsSize);
+        return false;
+    }
+
+    return true;
+}
+
 /*
  * Perform static verification on instructions.
  *
@@ -659,6 +822,10 @@ static bool checkBranchTarget(const Method* meth, InsnFlags* insnFlags,
  *   end at the start of an instruction (end can be at the end of the code)
  * - (earlier) for each exception handler, the handler must start at a valid
  *   instruction
+ *
+ * TODO: move some of the "CF" items in here for better performance (the
+ * code-flow analysis sometimes has to process the same instruction several
+ * times).
  */
 static bool verifyInstructions(const Method* meth, InsnFlags* insnFlags,
     int verifyFlags)
@@ -678,6 +845,22 @@ static bool verifyInstructions(const Method* meth, InsnFlags* insnFlags,
             /* plain no-op or switch table data; nothing to do here */
             break;
 
+        case OP_CONST_STRING:
+        case OP_CONST_STRING_JUMBO:
+            if (!checkStringIndex(meth, i))
+                return false;
+            break;
+
+        case OP_CONST_CLASS:
+        case OP_CHECK_CAST:
+            if (!checkTypeIndex(meth, i, true))
+                return false;
+            break;
+        case OP_INSTANCE_OF:
+            if (!checkTypeIndex(meth, i, false))
+                return false;
+            break;
+
         case OP_PACKED_SWITCH:
         case OP_SPARSE_SWITCH:
             /* verify the associated table */
@@ -690,7 +873,7 @@ static bool verifyInstructions(const Method* meth, InsnFlags* insnFlags,
             if (!checkArrayData(meth, i))
                 return false;
             break;
-            
+
         case OP_GOTO:
         case OP_GOTO_16:
         case OP_IF_EQ:
@@ -725,6 +908,67 @@ static bool verifyInstructions(const Method* meth, InsnFlags* insnFlags,
                 return false;
             break;
 
+        case OP_FILLED_NEW_ARRAY:
+            if (!checkTypeIndex(meth, i, false))
+                return false;
+            break;
+        case OP_FILLED_NEW_ARRAY_RANGE:
+            if (!checkTypeIndex(meth, i, true))
+                return false;
+            break;
+
+        case OP_IGET:
+        case OP_IGET_WIDE:
+        case OP_IGET_OBJECT:
+        case OP_IGET_BOOLEAN:
+        case OP_IGET_BYTE:
+        case OP_IGET_CHAR:
+        case OP_IGET_SHORT:
+        case OP_IPUT:
+        case OP_IPUT_WIDE:
+        case OP_IPUT_OBJECT:
+        case OP_IPUT_BOOLEAN:
+        case OP_IPUT_BYTE:
+        case OP_IPUT_CHAR:
+        case OP_IPUT_SHORT:
+            /* check the field index */
+            if (!checkFieldIndex(meth, i, false))
+                return false;
+            break;
+        case OP_SGET:
+        case OP_SGET_WIDE:
+        case OP_SGET_OBJECT:
+        case OP_SGET_BOOLEAN:
+        case OP_SGET_BYTE:
+        case OP_SGET_CHAR:
+        case OP_SGET_SHORT:
+        case OP_SPUT:
+        case OP_SPUT_WIDE:
+        case OP_SPUT_OBJECT:
+        case OP_SPUT_BOOLEAN:
+        case OP_SPUT_BYTE:
+        case OP_SPUT_CHAR:
+        case OP_SPUT_SHORT:
+            /* check the field index */
+            if (!checkFieldIndex(meth, i, true))
+                return false;
+            break;
+
+        case OP_INVOKE_VIRTUAL:
+        case OP_INVOKE_SUPER:
+        case OP_INVOKE_DIRECT:
+        case OP_INVOKE_STATIC:
+        case OP_INVOKE_INTERFACE:
+        case OP_INVOKE_VIRTUAL_RANGE:
+        case OP_INVOKE_SUPER_RANGE:
+        case OP_INVOKE_DIRECT_RANGE:
+        case OP_INVOKE_STATIC_RANGE:
+        case OP_INVOKE_INTERFACE_RANGE:
+            /* check the method index */
+            if (!checkMethodIndex(meth, i))
+                return false;
+            break;
+
         case OP_EXECUTE_INLINE:
         case OP_INVOKE_DIRECT_EMPTY:
         case OP_IGET_QUICK:
@@ -763,61 +1007,3 @@ static bool verifyInstructions(const Method* meth, InsnFlags* insnFlags,
 
     return true;
 }
-
-/*
- * Perform static checks on a "new-instance" instruction.  Specifically,
- * make sure the class reference isn't for an array class.
- *
- * We don't need the actual class, just a pointer to the class name.
- */
-static bool checkNewInstance(const Method* meth, int insnIdx)
-{
-    DexFile* pDexFile = meth->clazz->pDvmDex->pDexFile;
-    DecodedInstruction decInsn;
-    const char* classDescriptor;
-
-    dexDecodeInstruction(gDvm.instrFormat, meth->insns + insnIdx, &decInsn);
-    classDescriptor = dexStringByTypeIdx(pDexFile, decInsn.vB); // 2nd item
-
-    if (classDescriptor[0] != 'L') {
-        LOG_VFY_METH(meth, "VFY: can't call new-instance on type '%s'\n",
-            classDescriptor);
-        return false;
-    }
-
-    return true;
-}
-
-/*
- * Perform static checks on a "new-array" instruction.  Specifically, make
- * sure they aren't creating an array of arrays that causes the number of
- * dimensions to exceed 255.
- */
-static bool checkNewArray(const Method* meth, int insnIdx)
-{
-    DexFile* pDexFile = meth->clazz->pDvmDex->pDexFile;
-    DecodedInstruction decInsn;
-    const char* classDescriptor;
-
-    dexDecodeInstruction(gDvm.instrFormat, meth->insns + insnIdx, &decInsn);
-    classDescriptor = dexStringByTypeIdx(pDexFile, decInsn.vC); // 3rd item
-
-    int bracketCount = 0;
-    const char* cp = classDescriptor;
-    while (*cp++ == '[')
-        bracketCount++;
-
-    if (bracketCount == 0) {
-        /* The given class must be an array type. */
-        LOG_VFY_METH(meth, "VFY: can't new-array class '%s' (not an array)\n",
-            classDescriptor);
-        return false;
-    } else if (bracketCount > 255) {
-        /* It is illegal to create an array of more than 255 dimensions. */
-        LOG_VFY_METH(meth, "VFY: can't new-array class '%s' (exceeds limit)\n",
-            classDescriptor);
-        return false;
-    }
-
-    return true;
-}
diff --git a/vm/analysis/ReduceConstants.c b/vm/analysis/ReduceConstants.c
new file mode 100644
index 000000000..ec7ba0f3a
--- /dev/null
+++ b/vm/analysis/ReduceConstants.c
@@ -0,0 +1,1057 @@
+/*
+ * Copyright (C) 2008 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+/*
+ * Compress the range of "constant pool" indexes in instructions and
+ * annotations to lower runtime RAM footprint.
+ *
+ * NOTE: this is an incomplete experimental feature.  Do not try to use it.
+ */
+#include "Dalvik.h"
+#include "libdex/InstrUtils.h"
+#include "libdex/OptInvocation.h"
+#include "libdex/DexClass.h"
+
+/*
+Overview
+
+When a class, method, field, or string constant is referred to from
+Dalvik bytecode, the reference takes the form of an integer index value.
+This value indexes into an array of type_id_item, method_id_item,
+field_id_item, or string_id_item in the DEX file.  The first three
+themselves contain (directly or indirectly) indexes to strings that the
+resolver uses to convert the instruction stream index into a pointer to
+the appropriate object or struct.
+
+For example, an invoke-virtual instruction needs to specify which method
+is to be invoked.  The method constant indexes into the method_id_item
+array, each entry of which has indexes that specify the defining class
+(type_id_item), method name (string_id_item), and method prototype
+(proto_id_item).  The type_id_item just holds an index to a string_id_item,
+which holds the file offset to the string with the class name.  The VM
+finds the class by name, then searches through the class' table of virtual
+methods to find one with a matching name and prototype.
+
+This process is fairly expensive, so after the first time it completes
+successfully, the VM records that the method index resolved to a specific
+Method struct.  On subsequent execution, the VM just pulls the Method ptr
+out of the resolved-methods array.  A similar approach is used with
+the indexes for classes, fields, and string constants.
+
+The problem with this approach is that we need to have a "resolved" entry
+for every possible class, method, field, and string constant in every
+DEX file, even if some of those aren't used from code.  The DEX string
+constant table has entries for method prototypes and class names that are
+never used by the code, and "public static final" fields often turn into
+immediate constants.  The resolution table entries are only 4 bytes each,
+but there are roughly 200,000 of them in the bootstrap classes alone.
+
+DEX optimization removes many index references by replacing virtual method
+indexes with vtable offsets and instance field indexes with byte offsets.
+In the earlier example, the method would be resolved at "dexopt" time, and
+the instruction rewritten as invoke-virtual-quick with the vtable offset.
+
+(There are comparatively few classes compared to other constant pool
+entries, and a much higher percentage (typically 60-70%) are used.  The
+biggest gains come from the string pool.)
+
+Using the resolved-entity tables provides a substantial performance
+improvement, but results in applications allocating 1MB+ of tables that
+are 70% unused.  The used and unused entries are freely intermixed,
+preventing effective sharing with the zygote process, and resulting in
+large numbers of private/dirty pages on the native heap as the tables
+populate on first use.
+
+The trick is to reduce the memory usage without decreasing performance.
+Using smaller resolved-entity tables can actually give us a speed boost,
+because we'll have a smaller "live" set of pages and make more effective
+use of the data cache.
+
+
+The approach we're going to use is to determine the set of indexes that
+could potentially be resolved, generate a mapping from the minimal set to
+the full set, and append the mapping to the DEX file.  This is done at
+"dexopt" time, because we need to keep the changes in shared/read-only
+pages or we'll lose the benefits of doing the work.
+
+There are two ways to create and use the new mapping:
+
+ (1) Write the entire full->minimal mapping to the ".odex" file.  On every
+ instruction that uses an index, use the mapping to determine the
+ "compressed" constant value, and then use that to index into the
+ resolved-entity tables on the heap.  The instruction stream is unchanged,
+ and the resolver can easily tell if a given index is cacheable.
+
+ (2) Write the inverse miminal->full mapping to the ".odex" file, and
+ rewrite the constants in the instruction stream.  The interpreter is
+ unchanged, and the resolver code uses the mapping to find the original
+ data in the DEX.
+
+Approach #1 is easier and safer to implement, but it requires a table
+lookup every time we execute an instruction that includes a constant
+pool reference.  This causes an unacceptable performance hit, chiefly
+because we're hitting semi-random memory pages and hosing the data cache.
+This is mitigated somewhat by DEX optimizations that replace the constant
+with a vtable index or field byte offset.  Approach #1 also requires
+a larger map table, increasing the size of the DEX on disk.  One nice
+property of approach #1 is that most of the DEX file is unmodified,
+so use of the mapping is a runtime decision.
+
+Approach #2 is preferred for performance reasons.
+
+
+The class/method/field/string resolver code has to handle indices from
+three sources: interpreted instructions, annotations, and exception
+"catch" lists.  Sometimes these occur indirectly, e.g. we need to resolve
+the declaring class associated with fields and methods when the latter
+two are themselves resolved.  Parsing and rewriting instructions is fairly
+straightforward, but annotations use a complex format with variable-width
+index values.
+
+We can safely rewrite index values in annotations if we guarantee that the
+new value is smaller than the original.  This implies a two-pass approach:
+the first determines the set of indexes actually used, the second does the
+rewrite.  Doing the rewrite in a single pass would be much harder.
+
+Instances of the "original" indices will still be found in the file; if
+we try to be all-inclusive we will include some stuff that doesn't need
+to be there (e.g. we don't generally need to cache the class name string
+index result, since once we have the class resolved we don't need to look
+it up by name through the resolver again).  There is some potential for
+performance improvement by caching more than we strictly need, but we can
+afford to give up a little performance during class loading if it allows
+us to regain some memory.
+
+For safety and debugging, it's useful to distinguish the "compressed"
+constants in some way, e.g. setting the high bit when we rewrite them.
+In practice we don't have any free bits: indexes are usually 16-bit
+values, and we have more than 32,767 string constants in at least one of
+our core DEX files.  Also, this does not work with constants embedded in
+annotations, because of the variable-width encoding.
+
+We should be safe if we can establish a clear distinction between sources
+of "original" and "compressed" indices.  If the values get crossed up we
+can end up with elusive bugs.  The easiest approach is to declare that
+only indices pulled from certain locations (the instruction stream and/or
+annotations) are compressed.  This prevents us from adding indices in
+arbitrary locations to the compressed set, but should allow a reasonably
+robust implementation.
+
+
+Further implementation thoughts:
+
+ - We don't have to do annotations in the first pass.  At heart the
+   resolved entity cache is a performance optimization, not necessary for
+   correctness, and we're not making annotation performance a priority
+   at this stage.
+ - The most important "fast path" is instruction processing.  Everything
+   else can do additional work without having a measurable impact.
+   However...
+ - We need to keep an eye on uncached resolves to ensure that we haven't
+   introduced noticeable performance losses.  In particular, the use of
+   runtime annotations with string constants may suffer if we don't include
+   annotation rewriting in the solution.
+ - We can have separate resolver functions for "original" and "compressed"
+   indices.  This way we don't have to add a flag argument to the resolver
+   functions (which would require passing an additional parameter in from
+   the interpreter).
+ - The VM spec has some specific things to say about string constant
+   equality and interning.  Index compression should have no effect on
+   that; we just change how long it takes to find the interned string in
+   certain circumstances.  The impact can be mitigated somewhat by
+   improving the performance of the interned string table code.
+ - This can make e.g. method resolution slower.  The method_id_item has
+   an index to a method name string, and we will no longer cache the
+   result of resolving that string.  This impacts resolution of any method
+   with the same name as a previously-resolved method.
+ - We may need to tweak the tools, particularly "dexdump", to show the
+   translated values.
+ - We can use 16-bit values in the mapping table, since we should have
+   fewer than 2^16 remapped entries.  If we overflow we can skip the remap
+   for that table or for the entire DEX file.  The resolver will need to
+   check for the existence of the table to determine whether or not entries
+   must be remapped.  The cost of the extra check is acceptable for
+   approach #2, since it's only at resolve time, but may be undesirable
+   for approach #1.
+*/
+/*
+Output Formats
+ 
+There are two possible output formats, from which we choose based on how
+we plan to take advantage of the remapped constants.  At most one of these
+will appear in the DEX.
+
+NOTE: if EIXM appears in the DEX, the VM *must* be configured with
+DVM_RESOLVER_CACHE=DVM_RC_EXPANDING (2).  Otherwise the constants we
+pull from the instruction stream will be wrong and we will fail quickly.
+
+For approach #1: map from original indices to the reduced set.
+
+  This includes the four "mapToNew" tables.
+
+  Format (RIXM):
+   u4 classCount            // #of entries in classMap[]; == typeIdsSize
+   u4 reducedClassCount     // #of entries in remapped table (for alloc)
+   u2 classMap[]
+   u4 methodCount
+   u4 reducedMethodCount
+   u2 methodMap[]
+   u4 fieldCount
+   u4 reducedFieldCount
+   u2 fieldMap[]
+   u4 stringCount
+   u4 reducedStringCount
+   u2 stringMap[]
+
+For approach #2: map from the reduced set back to the originals.
+
+  This includes the four "mapToOld" tables.
+
+  Format (EIXM):
+   u4 classCount            // #of entries in classMap[]; post-reduction
+   u2 classMap[]
+   u4 methodCount
+   u2 methodMap[]
+   u4 fieldCount
+   u2 fieldMap[]
+   u4 stringCount
+   u2 stringMap[]
+
+The arrays are padded so that the "count" values are always aligned on
+32-bit boundaries.  All multi-byte values are in native host order.
+*/
+
+
+/*
+ * Gather results from the post-optimization instruction scan.
+ */
+typedef struct ScanResults {
+    /* output */
+    BitVector*  usedClasses;
+    BitVector*  usedMethods;
+    BitVector*  usedFields;
+    BitVector*  usedStrings;
+} ScanResults;
+
+/* prototype for the for-all-methods function */
+typedef void (AllMethodsFunc)(DexFile* pDexFile, const char* classDescriptor,
+    DexMethod* pDexMethod, void* arg);
+
+
+/*
+ * Free scan results.
+ */
+static void freeScanResults(ScanResults* pResults)
+{
+    if (pResults == NULL)
+        return;
+
+    dvmFreeBitVector(pResults->usedClasses);
+    dvmFreeBitVector(pResults->usedMethods);
+    dvmFreeBitVector(pResults->usedFields);
+    dvmFreeBitVector(pResults->usedStrings);
+    free(pResults);
+}
+
+/*
+ * Allocate storage for the results of the instruction scan.
+ */
+static ScanResults* allocScanResults(const DexFile* pDexFile)
+{
+    ScanResults* pResults;
+    const DexHeader* pHeader = pDexFile->pHeader;
+
+    pResults = (ScanResults*) calloc(1, sizeof(ScanResults));
+    if (pResults == NULL)
+        return NULL;
+
+    pResults->usedClasses = dvmAllocBitVector(pHeader->typeIdsSize, false);
+    pResults->usedMethods = dvmAllocBitVector(pHeader->methodIdsSize, false);
+    pResults->usedFields = dvmAllocBitVector(pHeader->fieldIdsSize, false);
+    pResults->usedStrings = dvmAllocBitVector(pHeader->stringIdsSize, false);
+
+    if (pResults->usedClasses == NULL ||
+        pResults->usedMethods == NULL ||
+        pResults->usedFields == NULL ||
+        pResults->usedStrings == NULL)
+    {
+        freeScanResults(pResults);
+        return NULL;
+    }
+
+    return pResults;
+}
+
+/*
+ * Call "func(method, arg)" on all methods in the specified class.
+ *
+ * Pass in a pointer to the class_data_item, positioned at the start of
+ * the field data (i.e. just past the class data header).
+ *
+ * "classDescriptor" is for debug messages.
+ */
+static void forAllMethodsInClass(DexFile* pDexFile, const u1** ppEncodedData,
+    const DexClassDataHeader* pHeader, const char* classDescriptor,
+    AllMethodsFunc func, void* arg)
+{
+    int i;
+
+    /*
+     * Consume field data.
+     */
+    if (pHeader->staticFieldsSize != 0) {
+        int count = (int) pHeader->staticFieldsSize;
+        u4 lastIndex = 0;
+        DexField field;
+        for (i = 0; i < count; i++) {
+            dexReadClassDataField(ppEncodedData, &field, &lastIndex);
+        }
+    }
+    if (pHeader->instanceFieldsSize != 0) {
+        int count = (int) pHeader->instanceFieldsSize;
+        u4 lastIndex = 0;
+        DexField field;
+        for (i = 0; i < count; i++) {
+            dexReadClassDataField(ppEncodedData, &field, &lastIndex);
+        }
+    }
+
+    /*
+     * Run through all methods.
+     */
+    if (pHeader->directMethodsSize != 0) {
+        int count = (int) pHeader->directMethodsSize;
+        u4 lastIndex = 0;
+        DexMethod method;
+
+        for (i = 0; i < count; i++) {
+            dexReadClassDataMethod(ppEncodedData, &method, &lastIndex);
+            (func)(pDexFile, classDescriptor, &method, arg);
+        }
+    }
+    if (pHeader->virtualMethodsSize != 0) {
+        int count = (int) pHeader->virtualMethodsSize;
+        u4 lastIndex = 0;
+        DexMethod method;
+
+        for (i = 0; i < count; i++) {
+            dexReadClassDataMethod(ppEncodedData, &method, &lastIndex);
+            (func)(pDexFile, classDescriptor, &method, arg);
+        }
+    }
+}
+
+/*
+ * Call "func(method, arg)" on all methods in all classes in DexFile.
+ */
+static void forAllMethods(DexFile* pDexFile, AllMethodsFunc func, void* arg)
+{
+    u4 count = pDexFile->pHeader->classDefsSize;
+    u4 idx;
+
+    for (idx = 0; idx < count; idx++) {
+        const DexClassDef* pClassDef;
+        DexClassDataHeader header;
+        const u1* pEncodedData;
+
+        pClassDef = dexGetClassDef(pDexFile, idx);
+        pEncodedData = dexGetClassData(pDexFile, pClassDef);
+
+        const char* classDescriptor;
+        classDescriptor = dexStringByTypeIdx(pDexFile, pClassDef->classIdx);
+
+        if (pEncodedData != NULL) {
+            dexReadClassDataHeader(&pEncodedData, &header);
+
+            forAllMethodsInClass(pDexFile, &pEncodedData, &header,
+                classDescriptor, func, arg);
+        } else {
+            //printf("%s: no class data\n", classDescriptor);
+            /* no class data, e.g. "marker interface" */
+        }
+    }
+}
+
+/*
+ * Mark a class ID as referenced.
+ */
+static void markClass(const u2* ptr, ScanResults* pResults)
+{
+    u2 classIdx = *ptr;
+    if (!dvmSetBit(pResults->usedClasses, classIdx)) {
+        LOGE("Unable to mark class %d as in-use\n", classIdx);
+    }
+}
+
+/*
+ * Mark a method ID as referenced.
+ */
+static void markMethod(const u2* ptr, ScanResults* pResults)
+{
+    u2 methodIdx = *ptr;
+    if (!dvmSetBit(pResults->usedMethods, methodIdx)) {
+        LOGE("Unable to mark method %d as in-use\n", methodIdx);
+    }
+}
+
+/*
+ * Mark a field ID as referenced.
+ */
+static void markField(const u2* ptr, ScanResults* pResults)
+{
+    u2 fieldIdx = *ptr;
+    if (!dvmSetBit(pResults->usedFields, fieldIdx)) {
+        LOGE("Unable to mark field %d as in-use\n", fieldIdx);
+    }
+}
+
+/*
+ * Mark a string constant as referenced.
+ */
+static void markString(const u2* ptr, ScanResults* pResults)
+{
+    u2 stringIdx = *ptr;
+    if (!dvmSetBit(pResults->usedStrings, stringIdx)) {
+        LOGE("Unable to mark string %d as in-use\n", stringIdx);
+    }
+}
+
+/*
+ * Mark a "jumbo" string constant as referenced.
+ */
+static void markJumboString(u2* ptr, ScanResults* pResults)
+{
+    u4 stringIdx;
+
+    /* it's in native byte order, but might not be 32-bit aligned */
+    memcpy(&stringIdx, ptr, sizeof(u4));
+    if (!dvmSetBit(pResults->usedStrings, stringIdx)) {
+        LOGE("Unable to mark string %d as in-use\n", stringIdx);
+    }
+}
+
+/*
+ * Remap a value in the instruction stream.
+ */
+static inline void updateValue(u2* ptr, const IndexMapSet* pIndexMapSet,
+    int whichMap)
+{
+    const IndexMap* pMap = &pIndexMapSet->map[whichMap];
+    if (pMap != NULL) {
+        u2 newIdx = pMap->mapToNew[*ptr];
+        assert(newIdx != kNoIndexMapping);
+        *ptr = newIdx;
+    }
+}
+static void updateClass(u2* ptr, const IndexMapSet* pIndexMapSet)
+{
+    updateValue(ptr, pIndexMapSet, kMapClasses);
+}
+static void updateMethod(u2* ptr, const IndexMapSet* pIndexMapSet)
+{
+    updateValue(ptr, pIndexMapSet, kMapMethods);
+}
+static void updateField(u2* ptr, const IndexMapSet* pIndexMapSet)
+{
+    updateValue(ptr, pIndexMapSet, kMapFields);
+}
+static void updateString(u2* ptr, const IndexMapSet* pIndexMapSet)
+{
+    updateValue(ptr, pIndexMapSet, kMapStrings);
+}
+static void updateJumboString(u2* ptr, const IndexMapSet* pIndexMapSet)
+{
+    u4 stringIdx;
+    u4 newIdx;
+
+    /* it's in native byte order, but might not be 32-bit aligned */
+    memcpy(&stringIdx, ptr, sizeof(stringIdx));
+
+    /* get new value */
+    newIdx = pIndexMapSet->map[kMapStrings].mapToNew[*ptr];
+    assert(newIdx != kNoIndexMapping);
+
+    /* copy it out */
+    memcpy(ptr, &newIdx, sizeof(newIdx));
+}
+
+/*
+ * Run through an instructions stream, marking constants as we see them.
+ *
+ * If "pResults" is non-NULL, we populate "pResults" with what we find,
+ * making no changes to the instruction stream.
+ *
+ * If "pIndexMapSet" is non-NULL, we rewrite the constants in the
+ * instruction stream.
+ */
+static void markUsedConstantsFromInsns(u2* insns, u4 insnsSize,
+    ScanResults* pResults, const IndexMapSet* pIndexMapSet)
+{
+    //printf(" %p %u units\n", insns, insnsSize);
+
+    while (insnsSize > 0) {
+        int width;
+        u2* pConst = insns + 1;
+
+        switch (*insns & 0xff) {
+        case OP_IGET:
+        case OP_IGET_WIDE:
+        case OP_IGET_OBJECT:
+        case OP_IGET_BOOLEAN:
+        case OP_IGET_BYTE:
+        case OP_IGET_CHAR:
+        case OP_IGET_SHORT:
+        case OP_IPUT:
+        case OP_IPUT_WIDE:
+        case OP_IPUT_OBJECT:
+        case OP_IPUT_BOOLEAN:
+        case OP_IPUT_BYTE:
+        case OP_IPUT_CHAR:
+        case OP_IPUT_SHORT:
+        case OP_SGET:
+        case OP_SGET_WIDE:
+        case OP_SGET_OBJECT:
+        case OP_SGET_BOOLEAN:
+        case OP_SGET_BYTE:
+        case OP_SGET_CHAR:
+        case OP_SGET_SHORT:
+        case OP_SPUT:
+        case OP_SPUT_WIDE:
+        case OP_SPUT_OBJECT:
+        case OP_SPUT_BOOLEAN:
+        case OP_SPUT_BYTE:
+        case OP_SPUT_CHAR:
+        case OP_SPUT_SHORT:
+            /* instanceop vA, vB, field@CCCC */
+            /* staticop vAA, field@BBBB */
+            if (pResults != NULL)
+                markField(pConst, pResults);
+            else
+                updateField(pConst, pIndexMapSet);
+            break;
+
+        case OP_CONST_STRING:
+            /* const-string vAA, string@BBBB */
+            if (pResults != NULL)
+                markString(pConst, pResults);
+            else
+                updateString(pConst, pIndexMapSet);
+            break;
+
+        case OP_CONST_STRING_JUMBO:
+            /* const-string/jumbo vAA, string@BBBBBBBB */
+            if (pResults != NULL)
+                markJumboString(pConst, pResults);
+            else
+                updateJumboString(pConst, pIndexMapSet);
+            break;
+
+        case OP_CONST_CLASS:
+        case OP_CHECK_CAST:
+        case OP_NEW_INSTANCE:
+        case OP_FILLED_NEW_ARRAY_RANGE:
+        case OP_INSTANCE_OF:
+        case OP_NEW_ARRAY:
+        case OP_FILLED_NEW_ARRAY:
+            /* const-class vAA, type@BBBB */
+            /* check-cast vAA, type@BBBB */
+            /* new-instance vAA, type@BBBB */
+            /* filled-new-array/range {vCCCC .. vNNNN}, type@BBBB */
+            /* instance-of vA, vB, type@CCCC */
+            /* new-array vA, vB, type@CCCC */
+            /* filled-new-array {vD, vE, vF, vG, vA}, type@CCCC */
+            if (pResults != NULL)
+                markClass(pConst, pResults);
+            else
+                updateClass(pConst, pIndexMapSet);
+            break;
+
+        case OP_INVOKE_VIRTUAL:
+        case OP_INVOKE_SUPER:
+        case OP_INVOKE_DIRECT:
+        case OP_INVOKE_STATIC:
+        case OP_INVOKE_INTERFACE:
+        case OP_INVOKE_VIRTUAL_RANGE:
+        case OP_INVOKE_SUPER_RANGE:
+        case OP_INVOKE_DIRECT_RANGE:
+        case OP_INVOKE_STATIC_RANGE:
+        case OP_INVOKE_INTERFACE_RANGE:
+            /* invoke-kind {vD, vE, vF, vG, vA}, meth@CCCC */
+            /* invoke-kind/range {vCCCC .. vNNNN}, meth@BBBB */
+            if (pResults != NULL)
+                markMethod(pConst, pResults);
+            else
+                updateMethod(pConst, pIndexMapSet);
+            break;
+
+        default:
+            // ignore this instruction
+            ;
+        }
+
+        width = dexGetInstrOrTableWidthAbs(gDvm.instrWidth, insns);
+        assert(width > 0 && width <= (int)insnsSize);
+
+        insns += width;
+        insnsSize -= width;
+    }
+}
+
+/*
+ * This is an AllMethodsFunc implementation.
+ *
+ * Run through the instructions in this method, setting bits in the "pResults"
+ * struct as we locate constants.
+ */
+static void markUsedConstants(DexFile* pDexFile, const char* classDescriptor,
+    DexMethod* pDexMethod, void* arg)
+{
+    ScanResults* pResults = (ScanResults*) arg;
+    const DexCode* pDexCode = dexGetCode(pDexFile, pDexMethod);
+
+    if (false) {
+        const DexMethodId* pMethodId;
+        const char* methodName;
+        pMethodId = dexGetMethodId(pDexFile, pDexMethod->methodIdx);
+        methodName = dexStringById(pDexFile, pMethodId->nameIdx);
+        printf(" %s.%s\n", classDescriptor, methodName);
+    }
+
+    if (pDexCode != NULL) {
+        u2* insns = (u2*) pDexCode->insns;
+        u4 insnsSize = pDexCode->insnsSize;
+        markUsedConstantsFromInsns(insns, insnsSize, pResults, NULL);
+    } else {
+        //printf(" (no code)\n");
+    }
+}
+
+/*
+ * This is an AllMethodsFunc implementation.
+ *
+ * Run through the instructions in this method, altering the constants used.
+ */
+static void updateUsedConstants(DexFile* pDexFile, const char* classDescriptor,
+    DexMethod* pDexMethod, void* arg)
+{
+    const IndexMapSet* pIndexMapSet = (const IndexMapSet*) arg;
+    const DexCode* pDexCode = dexGetCode(pDexFile, pDexMethod);
+
+    if (false) {
+        const DexMethodId* pMethodId;
+        const char* methodName;
+        pMethodId = dexGetMethodId(pDexFile, pDexMethod->methodIdx);
+        methodName = dexStringById(pDexFile, pMethodId->nameIdx);
+        printf(" %s.%s\n", classDescriptor, methodName);
+    }
+
+    if (pDexCode != NULL) {
+        u2* insns = (u2*) pDexCode->insns;
+        u4 insnsSize = pDexCode->insnsSize;
+        markUsedConstantsFromInsns(insns, insnsSize, NULL, pIndexMapSet);
+    } else {
+        //printf(" (no code)\n");
+    }
+}
+
+/*
+ * Count up the bits and show a count.
+ */
+static void showBitCount(const char* label, int setCount, int maxCount)
+{
+    printf("%s: %d of %d (%.1f%% unused)\n", label, setCount, maxCount,
+        ((maxCount - setCount) * 100.0f) / maxCount);
+}
+
+/*
+ * Print some debug info.
+ */
+static void summarizeResults(DvmDex* pDvmDex, ScanResults* pResults)
+{
+    DexFile* pDexFile = pDvmDex->pDexFile;
+    int i;
+
+#if 0
+    for (i = 0; i < (int) pDvmDex->pDexFile->pHeader->typeIdsSize; i++) {
+        const DexTypeId* pDexTypeId;
+        const char* classDescr;
+
+        pDexTypeId = dexGetTypeId(pDexFile, i);
+        classDescr = dexStringById(pDexFile, pDexTypeId->descriptorIdx);
+
+        if (dvmIsBitSet(pResults->usedStrings, i))
+            printf("used  : %04x '%s'\n", i, classDescr);
+        else
+            printf("unused: %04x '%s'\n", i, classDescr);
+    }
+#endif
+#if 0
+    for (i = 0; i < (int) pDvmDex->pDexFile->pHeader->methodIdsSize; i++) {
+        const DexMethodId* pDexMethodId;
+        const DexTypeId* pDexTypeId;
+        const char* classDescr;
+        const char* methodName;
+
+        pDexMethodId = dexGetMethodId(pDexFile, i);
+        methodName = dexStringById(pDexFile, pDexMethodId->nameIdx);
+
+        pDexTypeId = dexGetTypeId(pDexFile, pDexMethodId->classIdx);
+        classDescr = dexStringById(pDexFile, pDexTypeId->descriptorIdx);
+        if (dvmIsBitSet(pResults->usedMethods, i))
+            printf("used  : %s.%s\n", classDescr, methodName);
+        else
+            printf("unused: %s.%s\n", classDescr, methodName);
+    }
+#endif
+#if 0
+    for (i = 0; i < (int) pDvmDex->pDexFile->pHeader->fieldIdsSize; i++) {
+        const DexFieldId* pDexFieldId;
+        const DexTypeId* pDexTypeId;
+        const char* classDescr;
+        const char* fieldName;
+
+        pDexFieldId = dexGetFieldId(pDexFile, i);
+        fieldName = dexStringById(pDexFile, pDexFieldId->nameIdx);
+
+        pDexTypeId = dexGetTypeId(pDexFile, pDexFieldId->classIdx);
+        classDescr = dexStringById(pDexFile, pDexTypeId->descriptorIdx);
+        if (dvmIsBitSet(pResults->usedFields, i))
+            printf("used  : %s.%s\n", classDescr, fieldName);
+        else
+            printf("unused: %s.%s\n", classDescr, fieldName);
+    }
+#endif
+#if 0
+    for (i = 0; i < (int) pDvmDex->pDexFile->pHeader->stringIdsSize; i++) {
+        const char* str;
+
+        str = dexStringById(pDexFile, i);
+
+        if (dvmIsBitSet(pResults->usedStrings, i))
+            printf("used  : %04x '%s'\n", i, str);
+        else
+            printf("unused: %04x '%s'\n", i, str);
+    }
+#endif
+
+    int totalMax, totalSet;
+    int setCount;
+
+    totalMax = totalSet = 0;
+
+    setCount = dvmCountSetBits(pResults->usedClasses);
+    showBitCount("classes", setCount, pDexFile->pHeader->typeIdsSize);
+    totalSet += setCount;
+    totalMax += pDexFile->pHeader->typeIdsSize;
+
+    setCount = dvmCountSetBits(pResults->usedMethods);
+    showBitCount("methods", setCount, pDexFile->pHeader->methodIdsSize);
+    totalSet += setCount;
+    totalMax += pDexFile->pHeader->methodIdsSize;
+
+    setCount = dvmCountSetBits(pResults->usedFields);
+    showBitCount("fields",  setCount, pDexFile->pHeader->fieldIdsSize);
+    totalSet += setCount;
+    totalMax += pDexFile->pHeader->fieldIdsSize;
+
+    setCount = dvmCountSetBits(pResults->usedStrings);
+    showBitCount("strings", setCount, pDexFile->pHeader->stringIdsSize);
+    totalSet += setCount;
+    totalMax += pDexFile->pHeader->stringIdsSize;
+
+    printf("TOTAL %d of %d (%.1f%% unused -- %.1fK)\n", totalSet, totalMax,
+        ((totalMax - totalSet) * 100.0f) / totalMax,
+        (totalMax - totalSet) / 256.0f);
+}
+
+/*
+ * Fill out an index map set entry.
+ *
+ * If we can't fit the map into our base type, we don't create the map.
+ *
+ * Returns "false" if allocation fails.
+ */
+static bool constructIndexMap(int totalCount, const BitVector* pBits,
+    IndexMap* pMap)
+{
+    const int kMaxIndex = 65534;        // 65535, a/k/a -1, is special
+    int setCount;
+
+    setCount = dvmCountSetBits(pBits);
+    if (setCount < 0 || setCount > kMaxIndex)
+        return true;
+
+    u2* mapToOld = (u2*) malloc(setCount * sizeof(u2));
+    u2* mapToNew = (u2*) malloc(totalCount * sizeof(u2));
+    if (mapToOld == NULL || mapToNew == NULL) {
+        free(mapToOld);
+        free(mapToNew);
+        return false;
+    }
+
+    /* fill in both arrays */
+    int entry, idx = 0;
+    for (entry = 0; entry < totalCount; entry++) {
+        if (dvmIsBitSet(pBits, entry)) {
+            mapToNew[entry] = idx;
+            mapToOld[idx] = entry;
+            idx++;
+        } else {
+            mapToNew[entry] = kNoIndexMapping;
+        }
+    }
+
+    if (idx != setCount) {
+        LOGE("GLITCH: idx=%d setCount=%d\n", idx, setCount);
+        dvmAbort();
+    }
+
+    /* success */
+    pMap->mapToOld = mapToOld;
+    pMap->mapToNew = mapToNew;
+    pMap->origCount = totalCount;
+    pMap->newCount = setCount;
+
+    return true;
+}
+
+/*
+ * Construct a "reducing" chunk, with maps that convert the constants in
+ * instructions to their reduced value for the cache lookup.
+ */
+static bool constructReducingDataChunk(IndexMapSet* pIndexMapSet)
+{
+    int chunkLen = 0;
+    int i;
+
+    pIndexMapSet->chunkType = kDexChunkReducingIndexMap;
+
+    /*
+     * Compute space requirements and allocate storage.
+     */
+    for (i = 0; i < kNumIndexMaps; i++) {
+        /* space for the "original" count */
+        chunkLen += sizeof(u4);
+
+        /* space for the "reduced" count */
+        chunkLen += sizeof(u4);
+
+        /* add data length, round up to 32-bit boundary */
+        chunkLen += pIndexMapSet->map[i].origCount * sizeof(u2);
+        chunkLen = (chunkLen + 3) & ~3;
+    }
+
+    pIndexMapSet->chunkDataLen = chunkLen;
+    pIndexMapSet->chunkData = (u1*) calloc(1, chunkLen);
+    if (pIndexMapSet->chunkData == NULL)
+        return false;
+
+    /*
+     * Copy the data in.
+     */
+    u1* ptr = pIndexMapSet->chunkData;
+    for (i = 0; i < kNumIndexMaps; i++) {
+        u4* wordPtr = (u4*) ptr;
+        int dataLen = pIndexMapSet->map[i].origCount * sizeof(u2);
+
+        *wordPtr++ = pIndexMapSet->map[i].origCount;
+        *wordPtr++ = pIndexMapSet->map[i].newCount;
+        if (dataLen != 0)
+            memcpy(wordPtr, pIndexMapSet->map[i].mapToNew, dataLen);
+
+        /* advance pointer, maintaining 32-bit alignment */
+        ptr = ((u1*) wordPtr) + dataLen;
+        ptr = (u1*) (((int) ptr + 3) & ~3);
+    }
+
+    if (ptr - (u1*) pIndexMapSet->chunkData != chunkLen) {
+        LOGE("GLITCH: expected len=%d, actual=%d\n",
+            chunkLen, ptr - (u1*) pIndexMapSet->chunkData);
+        dvmAbort();
+    }
+
+    return true;
+}
+
+/*
+ * Construct an "expanding" chunk, with maps that convert instructions
+ * with reduced constants back to their full original values.
+ */
+static bool constructExpandingDataChunk(IndexMapSet* pIndexMapSet)
+{
+    int chunkLen = 0;
+    int i;
+
+    pIndexMapSet->chunkType = kDexChunkExpandingIndexMap;
+
+    /*
+     * Compute space requirements and allocate storage.
+     */
+    for (i = 0; i < kNumIndexMaps; i++) {
+        /* space for the length word */
+        chunkLen += sizeof(u4);
+
+        /* add data length, round up to 32-bit boundary */
+        chunkLen += pIndexMapSet->map[i].newCount * sizeof(u2);
+        chunkLen = (chunkLen + 3) & ~3;
+    }
+
+    pIndexMapSet->chunkDataLen = chunkLen;
+    pIndexMapSet->chunkData = (u1*) calloc(1, chunkLen);
+    if (pIndexMapSet->chunkData == NULL)
+        return false;
+
+    /*
+     * Copy the data in.
+     */
+    u1* ptr = pIndexMapSet->chunkData;
+    for (i = 0; i < kNumIndexMaps; i++) {
+        u4* wordPtr = (u4*) ptr;
+        int dataLen = pIndexMapSet->map[i].newCount * sizeof(u2);
+
+        *wordPtr++ = pIndexMapSet->map[i].newCount;
+        if (dataLen != 0)
+            memcpy(wordPtr, pIndexMapSet->map[i].mapToOld, dataLen);
+
+        /* advance pointer, maintaining 32-bit alignment */
+        ptr = ((u1*) wordPtr) + dataLen;
+        ptr = (u1*) (((int) ptr + 3) & ~3);
+    }
+
+    if (ptr - (u1*) pIndexMapSet->chunkData != chunkLen) {
+        LOGE("GLITCH: expected len=%d, actual=%d\n",
+            chunkLen, ptr - (u1*) pIndexMapSet->chunkData);
+        dvmAbort();
+    }
+
+    return true;
+}
+
+/*
+ * Construct the "chunk" of data that will be appended to the optimized DEX
+ * file.
+ */
+static bool constructDataChunk(IndexMapSet* pIndexMapSet)
+{
+    assert(sizeof(pIndexMapSet->map[0].mapToOld[0]) == sizeof(u2));
+    assert(sizeof(pIndexMapSet->map[0].mapToNew[0]) == sizeof(u2));
+
+#if DVM_RESOLVER_CACHE == DVM_RC_EXPANDING
+    return constructExpandingDataChunk(pIndexMapSet);
+#else
+    return constructReducingDataChunk(pIndexMapSet);
+#endif
+}
+
+/*
+ * Allocate storage to hold the maps.
+ */
+static IndexMapSet* createIndexMapSet(const DexFile* pDexFile,
+    ScanResults* pResults)
+{
+    IndexMapSet* pIndexMapSet;
+    int setCount;
+    bool okay = true;
+
+    pIndexMapSet = calloc(1, sizeof(*pIndexMapSet));
+    if (pIndexMapSet == NULL)
+        return NULL;
+
+    okay = okay && constructIndexMap(pDexFile->pHeader->typeIdsSize,
+            pResults->usedClasses, &pIndexMapSet->map[kMapClasses]);
+    okay = okay && constructIndexMap(pDexFile->pHeader->methodIdsSize,
+            pResults->usedMethods, &pIndexMapSet->map[kMapMethods]);
+    okay = okay && constructIndexMap(pDexFile->pHeader->fieldIdsSize,
+            pResults->usedFields, &pIndexMapSet->map[kMapFields]);
+    okay = okay && constructIndexMap(pDexFile->pHeader->stringIdsSize,
+            pResults->usedStrings, &pIndexMapSet->map[kMapStrings]);
+
+    LOGVV("Constr: %d %d %d %d\n",
+        pIndexMapSet->map[kMapClasses].mapToOld[0],
+        pIndexMapSet->map[kMapMethods].mapToOld[0],
+        pIndexMapSet->map[kMapFields].mapToOld[0],
+        pIndexMapSet->map[kMapStrings].mapToOld[0]);
+
+    okay = okay && constructDataChunk(pIndexMapSet);
+
+    if (!okay) {
+        dvmFreeIndexMapSet(pIndexMapSet);
+        return NULL;
+    }
+
+    return pIndexMapSet;
+}
+
+/*
+ * Free map storage.
+ *
+ * "pIndexMapSet" may be incomplete.
+ */
+void dvmFreeIndexMapSet(IndexMapSet* pIndexMapSet)
+{
+    int i;
+
+    if (pIndexMapSet == NULL)
+        return;
+
+    for (i = 0; i < kNumIndexMaps; i++) {
+        free(pIndexMapSet->map[i].mapToOld);
+        free(pIndexMapSet->map[i].mapToNew);
+    }
+    free(pIndexMapSet->chunkData);
+    free(pIndexMapSet);
+}
+
+/*
+ * Rewrite constant indexes to reduce heap requirements.
+ */
+IndexMapSet* dvmRewriteConstants(DvmDex* pDvmDex)
+{
+#if (DVM_RESOLVER_CACHE != DVM_RC_REDUCING) && \
+    (DVM_RESOLVER_CACHE != DVM_RC_EXPANDING)
+    /* nothing to do */
+    return NULL;
+#endif
+
+    /*
+     * We're looking for instructions that use "constant pool" entries for
+     * classes, methods, fields, and strings.  Many field and method entries
+     * are optimized away, and many string constants are never accessed from
+     * code or annotations.
+     */
+    ScanResults* pResults = allocScanResults(pDvmDex->pDexFile);
+    forAllMethods(pDvmDex->pDexFile, markUsedConstants, pResults);
+
+    summarizeResults(pDvmDex, pResults);
+
+    /*
+     * Allocate and populate the index maps.
+     */
+    IndexMapSet* pIndexMapSet = createIndexMapSet(pDvmDex->pDexFile, pResults);
+#if DVM_RESOLVER_CACHE == DVM_RC_EXPANDING
+    if (pIndexMapSet != NULL) {
+        /*
+         * Rewrite the constants to use the reduced set.
+         */
+        forAllMethods(pDvmDex->pDexFile, updateUsedConstants, pIndexMapSet);
+    }
+#endif
+
+    freeScanResults(pResults);
+
+    return pIndexMapSet;
+}
+
diff --git a/vm/analysis/ReduceConstants.h b/vm/analysis/ReduceConstants.h
new file mode 100644
index 000000000..342e12531
--- /dev/null
+++ b/vm/analysis/ReduceConstants.h
@@ -0,0 +1,71 @@
+/*
+ * Copyright (C) 2008 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+/*
+ * DEX constant-reduction declarations.
+ */
+#ifndef _DALVIK_REDUCECONSTANTS
+#define _DALVIK_REDUCECONSTANTS
+
+#define DVM_RC_DISABLED     0       /* no reduction, 1:1 map */
+#define DVM_RC_REDUCING     1       /* normal constants, reduced lookup table */
+#define DVM_RC_EXPANDING    2       /* reduced constants, expanded on resolve */
+#define DVM_RC_NO_CACHE     3       /* disable the cache (reduce to zero) */
+
+enum {
+    kMapClasses     = 0,
+    kMapMethods     = 1,
+    kMapFields      = 2,
+    kMapStrings     = 3,
+
+    kNumIndexMaps
+};
+
+struct DvmDex;
+
+#define kNoIndexMapping     ((u2) -1)
+
+/*
+ * Map indices back to the original.
+ */
+typedef struct IndexMap {
+    int origCount;      /* original size; describes range of entries in map */
+    int newCount;       /* reduced size */
+    u2* mapToNew;       /* sparse map, from "orig" to "new" */
+    u2* mapToOld;       /* dense map, from "new" back to "orig" */
+} IndexMap;
+typedef struct IndexMapSet {
+    /* maps for the different sections */
+    IndexMap    map[kNumIndexMaps];
+
+    /* data stream that gets appended to the optimized DEX file */
+    u4          chunkType;
+    int         chunkDataLen;
+    u1*         chunkData;
+} IndexMapSet;
+
+/*
+ * Constant pool compaction.
+ *
+ * The caller is responsible for freeing the returned structure by
+ * calling dvmFreeIndexMap().
+ */
+IndexMapSet* dvmRewriteConstants(struct DvmDex* pDvmDex);
+
+/* free an index map set */
+void dvmFreeIndexMapSet(IndexMapSet* indexMapSet);
+
+#endif /*_DALVIK_REDUCECONSTANTS*/