Home | History | Annotate | Download | only in analysis 
      1 /*
      2  * Copyright (C) 2010 The Android Open Source Project
      3  *
      4  * Licensed under the Apache License, Version 2.0 (the "License");
      5  * you may not use this file except in compliance with the License.
      6  * You may obtain a copy of the License at
      7  *
      8  *      http://www.apache.org/licenses/LICENSE-2.0
      9  *
     10  * Unless required by applicable law or agreed to in writing, software
     11  * distributed under the License is distributed on an "AS IS" BASIS,
     12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     13  * See the License for the specific language governing permissions and
     14  * limitations under the License.
     15  */
     16 
     17 /*
     18  * Liveness analysis for Dalvik bytecode.
     19  */
     20 #include "Dalvik.h"
     21 #include "analysis/Liveness.h"
     22 #include "analysis/CodeVerify.h"
     23 
     24 static bool processInstruction(VerifierData* vdata, u4 curIdx,
     25     BitVector* workBits);
     26 static bool markDebugLocals(VerifierData* vdata);
     27 static void dumpLiveState(const VerifierData* vdata, u4 curIdx,
     28     const BitVector* workBits);
     29 
     30 
     31 /*
     32  * Create a table of instruction widths that indicate the width of the
     33  * *previous* instruction.  The values are copied from the width table
     34  * in "vdata", not derived from the instruction stream.
     35  *
     36  * Caller must free the return value.
     37  */
     38 static InstructionWidth* createBackwardWidthTable(VerifierData* vdata)
     39 {
     40     InstructionWidth* widths;
     41 
     42     widths = (InstructionWidth*)
     43             calloc(vdata->insnsSize, sizeof(InstructionWidth));
     44     if (widths == NULL)
     45         return NULL;
     46 
     47     u4 insnWidth = 0;
     48     for (u4 idx = 0; idx < vdata->insnsSize; ) {
     49         widths[idx] = insnWidth;
     50         insnWidth = dvmInsnGetWidth(vdata->insnFlags, idx);
     51         idx += insnWidth;
     52     }
     53 
     54     return widths;
     55 }
     56 
     57 /*
     58  * Compute the "liveness" of every register at all GC points.
     59  */
     60 bool dvmComputeLiveness(VerifierData* vdata)
     61 {
     62     const InsnFlags* insnFlags = vdata->insnFlags;
     63     InstructionWidth* backwardWidth;
     64     VfyBasicBlock* startGuess = NULL;
     65     BitVector* workBits = NULL;
     66     bool result = false;
     67 
     68     bool verbose = false; //= dvmWantVerboseVerification(vdata->method);
     69     if (verbose) {
     70         const Method* meth = vdata->method;
     71         ALOGI("Computing liveness for %s.%s:%s",
     72             meth->clazz->descriptor, meth->name, meth->shorty);
     73     }
     74 
     75     assert(vdata->registerLines != NULL);
     76 
     77     backwardWidth = createBackwardWidthTable(vdata);
     78     if (backwardWidth == NULL)
     79         goto bail;
     80 
     81     /*
     82      * Allocate space for intra-block work set.  Does not include space
     83      * for method result "registers", which aren't visible to the GC.
     84      * (They would be made live by move-result and then die on the
     85      * instruction immediately before it.)
     86      */
     87     workBits = dvmAllocBitVector(vdata->insnRegCount, false);
     88     if (workBits == NULL)
     89         goto bail;
     90 
     91     /*
     92      * We continue until all blocks have been visited, and no block
     93      * requires further attention ("visited" is set and "changed" is
     94      * clear).
     95      *
     96      * TODO: consider creating a "dense" array of basic blocks to make
     97      * the walking faster.
     98      */
     99     for (int iter = 0;;) {
    100         VfyBasicBlock* workBlock = NULL;
    101 
    102         if (iter++ > 100000) {
    103             LOG_VFY_METH(vdata->method, "oh dear");
    104             dvmAbort();
    105         }
    106 
    107         /*
    108          * If a block is marked "changed", we stop and handle it.  If it
    109          * just hasn't been visited yet, we remember it but keep searching
    110          * for one that has been changed.
    111          *
    112          * The thought here is that this is more likely to let us work
    113          * from end to start, which reduces the amount of re-evaluation
    114          * required (both by using "changed" as a work list, and by picking
    115          * un-visited blocks from the tail end of the method).
    116          */
    117         if (startGuess != NULL) {
    118             assert(startGuess->changed);
    119             workBlock = startGuess;
    120         } else {
    121             for (u4 idx = 0; idx < vdata->insnsSize; idx++) {
    122                 VfyBasicBlock* block = vdata->basicBlocks[idx];
    123                 if (block == NULL)
    124                     continue;
    125 
    126                 if (block->changed) {
    127                     workBlock = block;
    128                     break;
    129                 } else if (!block->visited) {
    130                     workBlock = block;
    131                 }
    132             }
    133         }
    134 
    135         if (workBlock == NULL) {
    136             /* all done */
    137             break;
    138         }
    139 
    140         assert(workBlock->changed || !workBlock->visited);
    141         startGuess = NULL;
    142 
    143         /*
    144          * Load work bits.  These represent the liveness of registers
    145          * after the last instruction in the block has finished executing.
    146          */
    147         assert(workBlock->liveRegs != NULL);
    148         dvmCopyBitVector(workBits, workBlock->liveRegs);
    149         if (verbose) {
    150             ALOGI("Loaded work bits from last=0x%04x", workBlock->lastAddr);
    151             dumpLiveState(vdata, 0xfffd, workBlock->liveRegs);
    152             dumpLiveState(vdata, 0xffff, workBits);
    153         }
    154 
    155         /*
    156          * Process a single basic block.
    157          *
    158          * If this instruction is a GC point, we want to save the result
    159          * in the RegisterLine.
    160          *
    161          * We don't break basic blocks on every GC point -- in particular,
    162          * instructions that might throw but have no "try" block don't
    163          * end a basic block -- so there could be more than one GC point
    164          * in a given basic block.
    165          *
    166          * We could change this, but it turns out to be not all that useful.
    167          * At first glance it appears that we could share the liveness bit
    168          * vector between the basic block struct and the register line,
    169          * but the basic block needs to reflect the state *after* the
    170          * instruction has finished, while the GC points need to describe
    171          * the state before the instruction starts.
    172          */
    173         u4 curIdx = workBlock->lastAddr;
    174         while (true) {
    175             if (!processInstruction(vdata, curIdx, workBits))
    176                 goto bail;
    177 
    178             if (verbose) {
    179                 dumpLiveState(vdata, curIdx + 0x8000, workBits);
    180             }
    181 
    182             if (dvmInsnIsGcPoint(insnFlags, curIdx)) {
    183                 BitVector* lineBits = vdata->registerLines[curIdx].liveRegs;
    184                 if (lineBits == NULL) {
    185                     lineBits = vdata->registerLines[curIdx].liveRegs =
    186                         dvmAllocBitVector(vdata->insnRegCount, false);
    187                 }
    188                 dvmCopyBitVector(lineBits, workBits);
    189             }
    190 
    191             if (curIdx == workBlock->firstAddr)
    192                 break;
    193             assert(curIdx >= backwardWidth[curIdx]);
    194             curIdx -= backwardWidth[curIdx];
    195         }
    196 
    197         workBlock->visited = true;
    198         workBlock->changed = false;
    199 
    200         if (verbose) {
    201             dumpLiveState(vdata, curIdx, workBits);
    202         }
    203 
    204         /*
    205          * Merge changes to all predecessors.  If the new bits don't match
    206          * the old bits, set the "changed" flag.
    207          */
    208         PointerSet* preds = workBlock->predecessors;
    209         size_t numPreds = dvmPointerSetGetCount(preds);
    210         unsigned int predIdx;
    211 
    212         for (predIdx = 0; predIdx < numPreds; predIdx++) {
    213             VfyBasicBlock* pred =
    214                     (VfyBasicBlock*) dvmPointerSetGetEntry(preds, predIdx);
    215 
    216             pred->changed = dvmCheckMergeBitVectors(pred->liveRegs, workBits);
    217             if (verbose) {
    218                 ALOGI("merging cur=%04x into pred last=%04x (ch=%d)",
    219                     curIdx, pred->lastAddr, pred->changed);
    220                 dumpLiveState(vdata, 0xfffa, pred->liveRegs);
    221                 dumpLiveState(vdata, 0xfffb, workBits);
    222             }
    223 
    224             /*
    225              * We want to set the "changed" flag on unvisited predecessors
    226              * as a way of guiding the verifier through basic blocks in
    227              * a reasonable order.  We can't count on variable liveness
    228              * changing, so we force "changed" to true even if it hasn't.
    229              */
    230             if (!pred->visited)
    231                 pred->changed = true;
    232 
    233             /*
    234              * Keep track of one of the changed blocks so we can start
    235              * there instead of having to scan through the list.
    236              */
    237             if (pred->changed)
    238                 startGuess = pred;
    239         }
    240     }
    241 
    242 #ifndef NDEBUG
    243     /*
    244      * Sanity check: verify that all GC point register lines have a
    245      * liveness bit vector allocated.  Also, we're not expecting non-GC
    246      * points to have them.
    247      */
    248     u4 checkIdx;
    249     for (checkIdx = 0; checkIdx < vdata->insnsSize; ) {
    250         if (dvmInsnIsGcPoint(insnFlags, checkIdx)) {
    251             if (vdata->registerLines[checkIdx].liveRegs == NULL) {
    252                 LOG_VFY_METH(vdata->method,
    253                     "GLITCH: no liveRegs for GC point 0x%04x", checkIdx);
    254                 dvmAbort();
    255             }
    256         } else if (vdata->registerLines[checkIdx].liveRegs != NULL) {
    257             LOG_VFY_METH(vdata->method,
    258                 "GLITCH: liveRegs for non-GC point 0x%04x", checkIdx);
    259             dvmAbort();
    260         }
    261         u4 insnWidth = dvmInsnGetWidth(insnFlags, checkIdx);
    262         checkIdx += insnWidth;
    263     }
    264 #endif
    265 
    266     /*
    267      * Factor in the debug info, if any.
    268      */
    269     if (!markDebugLocals(vdata))
    270         goto bail;
    271 
    272     result = true;
    273 
    274 bail:
    275     free(backwardWidth);
    276     dvmFreeBitVector(workBits);
    277     return result;
    278 }
    279 
    280 
    281 /*
    282  * Add a register to the LIVE set.
    283  */
    284 static inline void GEN(BitVector* workBits, u4 regIndex)
    285 {
    286     dvmSetBit(workBits, regIndex);
    287 }
    288 
    289 /*
    290  * Add a register pair to the LIVE set.
    291  */
    292 static inline void GENW(BitVector* workBits, u4 regIndex)
    293 {
    294     dvmSetBit(workBits, regIndex);
    295     dvmSetBit(workBits, regIndex+1);
    296 }
    297 
    298 /*
    299  * Remove a register from the LIVE set.
    300  */
    301 static inline void KILL(BitVector* workBits, u4 regIndex)
    302 {
    303     dvmClearBit(workBits, regIndex);
    304 }
    305 
    306 /*
    307  * Remove a register pair from the LIVE set.
    308  */
    309 static inline void KILLW(BitVector* workBits, u4 regIndex)
    310 {
    311     dvmClearBit(workBits, regIndex);
    312     dvmClearBit(workBits, regIndex+1);
    313 }
    314 
    315 /*
    316  * Process a single instruction.
    317  *
    318  * Returns "false" if something goes fatally wrong.
    319  */
    320 static bool processInstruction(VerifierData* vdata, u4 insnIdx,
    321     BitVector* workBits)
    322 {
    323     const Method* meth = vdata->method;
    324     const u2* insns = meth->insns + insnIdx;
    325     DecodedInstruction decInsn;
    326 
    327     dexDecodeInstruction(insns, &decInsn);
    328 
    329     /*
    330      * Add registers to the "GEN" or "KILL" sets.  We want to do KILL
    331      * before GEN to handle cases where the source and destination
    332      * register is the same.
    333      */
    334     switch (decInsn.opcode) {
    335     case OP_NOP:
    336     case OP_RETURN_VOID:
    337     case OP_GOTO:
    338     case OP_GOTO_16:
    339     case OP_GOTO_32:
    340         /* no registers are used */
    341         break;
    342 
    343     case OP_RETURN:
    344     case OP_RETURN_OBJECT:
    345     case OP_MONITOR_ENTER:
    346     case OP_MONITOR_EXIT:
    347     case OP_CHECK_CAST:
    348     case OP_THROW:
    349     case OP_PACKED_SWITCH:
    350     case OP_SPARSE_SWITCH:
    351     case OP_FILL_ARRAY_DATA:
    352     case OP_IF_EQZ:
    353     case OP_IF_NEZ:
    354     case OP_IF_LTZ:
    355     case OP_IF_GEZ:
    356     case OP_IF_GTZ:
    357     case OP_IF_LEZ:
    358     case OP_SPUT:
    359     case OP_SPUT_BOOLEAN:
    360     case OP_SPUT_BYTE:
    361     case OP_SPUT_CHAR:
    362     case OP_SPUT_SHORT:
    363     case OP_SPUT_OBJECT:
    364         /* action <- vA */
    365         GEN(workBits, decInsn.vA);
    366         break;
    367 
    368     case OP_RETURN_WIDE:
    369     case OP_SPUT_WIDE:
    370         /* action <- vA(wide) */
    371         GENW(workBits, decInsn.vA);
    372         break;
    373 
    374     case OP_IF_EQ:
    375     case OP_IF_NE:
    376     case OP_IF_LT:
    377     case OP_IF_GE:
    378     case OP_IF_GT:
    379     case OP_IF_LE:
    380     case OP_IPUT:
    381     case OP_IPUT_BOOLEAN:
    382     case OP_IPUT_BYTE:
    383     case OP_IPUT_CHAR:
    384     case OP_IPUT_SHORT:
    385     case OP_IPUT_OBJECT:
    386         /* action <- vA, vB */
    387         GEN(workBits, decInsn.vA);
    388         GEN(workBits, decInsn.vB);
    389         break;
    390 
    391     case OP_IPUT_WIDE:
    392         /* action <- vA(wide), vB */
    393         GENW(workBits, decInsn.vA);
    394         GEN(workBits, decInsn.vB);
    395         break;
    396 
    397     case OP_APUT:
    398     case OP_APUT_BOOLEAN:
    399     case OP_APUT_BYTE:
    400     case OP_APUT_CHAR:
    401     case OP_APUT_SHORT:
    402     case OP_APUT_OBJECT:
    403         /* action <- vA, vB, vC */
    404         GEN(workBits, decInsn.vA);
    405         GEN(workBits, decInsn.vB);
    406         GEN(workBits, decInsn.vC);
    407         break;
    408 
    409     case OP_APUT_WIDE:
    410         /* action <- vA(wide), vB, vC */
    411         GENW(workBits, decInsn.vA);
    412         GEN(workBits, decInsn.vB);
    413         GEN(workBits, decInsn.vC);
    414         break;
    415 
    416     case OP_FILLED_NEW_ARRAY:
    417     case OP_INVOKE_VIRTUAL:
    418     case OP_INVOKE_SUPER:
    419     case OP_INVOKE_DIRECT:
    420     case OP_INVOKE_STATIC:
    421     case OP_INVOKE_INTERFACE:
    422         /* action <- vararg */
    423         {
    424             unsigned int idx;
    425             for (idx = 0; idx < decInsn.vA; idx++) {
    426                 GEN(workBits, decInsn.arg[idx]);
    427             }
    428         }
    429         break;
    430 
    431     case OP_FILLED_NEW_ARRAY_RANGE:
    432     case OP_INVOKE_VIRTUAL_RANGE:
    433     case OP_INVOKE_SUPER_RANGE:
    434     case OP_INVOKE_DIRECT_RANGE:
    435     case OP_INVOKE_STATIC_RANGE:
    436     case OP_INVOKE_INTERFACE_RANGE:
    437         /* action <- vararg/range */
    438         {
    439             unsigned int idx;
    440             for (idx = 0; idx < decInsn.vA; idx++) {
    441                 GEN(workBits, decInsn.vC + idx);
    442             }
    443         }
    444         break;
    445 
    446     case OP_MOVE_RESULT:
    447     case OP_MOVE_RESULT_WIDE:
    448     case OP_MOVE_RESULT_OBJECT:
    449     case OP_MOVE_EXCEPTION:
    450     case OP_CONST_4:
    451     case OP_CONST_16:
    452     case OP_CONST:
    453     case OP_CONST_HIGH16:
    454     case OP_CONST_STRING:
    455     case OP_CONST_STRING_JUMBO:
    456     case OP_CONST_CLASS:
    457     case OP_NEW_INSTANCE:
    458     case OP_SGET:
    459     case OP_SGET_BOOLEAN:
    460     case OP_SGET_BYTE:
    461     case OP_SGET_CHAR:
    462     case OP_SGET_SHORT:
    463     case OP_SGET_OBJECT:
    464         /* vA <- value */
    465         KILL(workBits, decInsn.vA);
    466         break;
    467 
    468     case OP_CONST_WIDE_16:
    469     case OP_CONST_WIDE_32:
    470     case OP_CONST_WIDE:
    471     case OP_CONST_WIDE_HIGH16:
    472     case OP_SGET_WIDE:
    473         /* vA(wide) <- value */
    474         KILLW(workBits, decInsn.vA);
    475         break;
    476 
    477     case OP_MOVE:
    478     case OP_MOVE_FROM16:
    479     case OP_MOVE_16:
    480     case OP_MOVE_OBJECT:
    481     case OP_MOVE_OBJECT_FROM16:
    482     case OP_MOVE_OBJECT_16:
    483     case OP_INSTANCE_OF:
    484     case OP_ARRAY_LENGTH:
    485     case OP_NEW_ARRAY:
    486     case OP_IGET:
    487     case OP_IGET_BOOLEAN:
    488     case OP_IGET_BYTE:
    489     case OP_IGET_CHAR:
    490     case OP_IGET_SHORT:
    491     case OP_IGET_OBJECT:
    492     case OP_NEG_INT:
    493     case OP_NOT_INT:
    494     case OP_NEG_FLOAT:
    495     case OP_INT_TO_FLOAT:
    496     case OP_FLOAT_TO_INT:
    497     case OP_INT_TO_BYTE:
    498     case OP_INT_TO_CHAR:
    499     case OP_INT_TO_SHORT:
    500     case OP_ADD_INT_LIT16:
    501     case OP_RSUB_INT:
    502     case OP_MUL_INT_LIT16:
    503     case OP_DIV_INT_LIT16:
    504     case OP_REM_INT_LIT16:
    505     case OP_AND_INT_LIT16:
    506     case OP_OR_INT_LIT16:
    507     case OP_XOR_INT_LIT16:
    508     case OP_ADD_INT_LIT8:
    509     case OP_RSUB_INT_LIT8:
    510     case OP_MUL_INT_LIT8:
    511     case OP_DIV_INT_LIT8:
    512     case OP_REM_INT_LIT8:
    513     case OP_SHL_INT_LIT8:
    514     case OP_SHR_INT_LIT8:
    515     case OP_USHR_INT_LIT8:
    516     case OP_AND_INT_LIT8:
    517     case OP_OR_INT_LIT8:
    518     case OP_XOR_INT_LIT8:
    519         /* vA <- vB */
    520         KILL(workBits, decInsn.vA);
    521         GEN(workBits, decInsn.vB);
    522         break;
    523 
    524     case OP_IGET_WIDE:
    525     case OP_INT_TO_LONG:
    526     case OP_INT_TO_DOUBLE:
    527     case OP_FLOAT_TO_LONG:
    528     case OP_FLOAT_TO_DOUBLE:
    529         /* vA(wide) <- vB */
    530         KILLW(workBits, decInsn.vA);
    531         GEN(workBits, decInsn.vB);
    532         break;
    533 
    534     case OP_LONG_TO_INT:
    535     case OP_LONG_TO_FLOAT:
    536     case OP_DOUBLE_TO_INT:
    537     case OP_DOUBLE_TO_FLOAT:
    538         /* vA <- vB(wide) */
    539         KILL(workBits, decInsn.vA);
    540         GENW(workBits, decInsn.vB);
    541         break;
    542 
    543     case OP_MOVE_WIDE:
    544     case OP_MOVE_WIDE_FROM16:
    545     case OP_MOVE_WIDE_16:
    546     case OP_NEG_LONG:
    547     case OP_NOT_LONG:
    548     case OP_NEG_DOUBLE:
    549     case OP_LONG_TO_DOUBLE:
    550     case OP_DOUBLE_TO_LONG:
    551         /* vA(wide) <- vB(wide) */
    552         KILLW(workBits, decInsn.vA);
    553         GENW(workBits, decInsn.vB);
    554         break;
    555 
    556     case OP_CMPL_FLOAT:
    557     case OP_CMPG_FLOAT:
    558     case OP_AGET:
    559     case OP_AGET_BOOLEAN:
    560     case OP_AGET_BYTE:
    561     case OP_AGET_CHAR:
    562     case OP_AGET_SHORT:
    563     case OP_AGET_OBJECT:
    564     case OP_ADD_INT:
    565     case OP_SUB_INT:
    566     case OP_MUL_INT:
    567     case OP_REM_INT:
    568     case OP_DIV_INT:
    569     case OP_AND_INT:
    570     case OP_OR_INT:
    571     case OP_XOR_INT:
    572     case OP_SHL_INT:
    573     case OP_SHR_INT:
    574     case OP_USHR_INT:
    575     case OP_ADD_FLOAT:
    576     case OP_SUB_FLOAT:
    577     case OP_MUL_FLOAT:
    578     case OP_DIV_FLOAT:
    579     case OP_REM_FLOAT:
    580         /* vA <- vB, vC */
    581         KILL(workBits, decInsn.vA);
    582         GEN(workBits, decInsn.vB);
    583         GEN(workBits, decInsn.vC);
    584         break;
    585 
    586     case OP_AGET_WIDE:
    587         /* vA(wide) <- vB, vC */
    588         KILLW(workBits, decInsn.vA);
    589         GEN(workBits, decInsn.vB);
    590         GEN(workBits, decInsn.vC);
    591         break;
    592 
    593     case OP_CMPL_DOUBLE:
    594     case OP_CMPG_DOUBLE:
    595     case OP_CMP_LONG:
    596         /* vA <- vB(wide), vC(wide) */
    597         KILL(workBits, decInsn.vA);
    598         GENW(workBits, decInsn.vB);
    599         GENW(workBits, decInsn.vC);
    600         break;
    601 
    602     case OP_SHL_LONG:
    603     case OP_SHR_LONG:
    604     case OP_USHR_LONG:
    605         /* vA(wide) <- vB(wide), vC */
    606         KILLW(workBits, decInsn.vA);
    607         GENW(workBits, decInsn.vB);
    608         GEN(workBits, decInsn.vC);
    609         break;
    610 
    611     case OP_ADD_LONG:
    612     case OP_SUB_LONG:
    613     case OP_MUL_LONG:
    614     case OP_DIV_LONG:
    615     case OP_REM_LONG:
    616     case OP_AND_LONG:
    617     case OP_OR_LONG:
    618     case OP_XOR_LONG:
    619     case OP_ADD_DOUBLE:
    620     case OP_SUB_DOUBLE:
    621     case OP_MUL_DOUBLE:
    622     case OP_DIV_DOUBLE:
    623     case OP_REM_DOUBLE:
    624         /* vA(wide) <- vB(wide), vC(wide) */
    625         KILLW(workBits, decInsn.vA);
    626         GENW(workBits, decInsn.vB);
    627         GENW(workBits, decInsn.vC);
    628         break;
    629 
    630     case OP_ADD_INT_2ADDR:
    631     case OP_SUB_INT_2ADDR:
    632     case OP_MUL_INT_2ADDR:
    633     case OP_REM_INT_2ADDR:
    634     case OP_SHL_INT_2ADDR:
    635     case OP_SHR_INT_2ADDR:
    636     case OP_USHR_INT_2ADDR:
    637     case OP_AND_INT_2ADDR:
    638     case OP_OR_INT_2ADDR:
    639     case OP_XOR_INT_2ADDR:
    640     case OP_DIV_INT_2ADDR:
    641         /* vA <- vA, vB */
    642         /* KILL(workBits, decInsn.vA); */
    643         GEN(workBits, decInsn.vA);
    644         GEN(workBits, decInsn.vB);
    645         break;
    646 
    647     case OP_SHL_LONG_2ADDR:
    648     case OP_SHR_LONG_2ADDR:
    649     case OP_USHR_LONG_2ADDR:
    650         /* vA(wide) <- vA(wide), vB */
    651         /* KILLW(workBits, decInsn.vA); */
    652         GENW(workBits, decInsn.vA);
    653         GEN(workBits, decInsn.vB);
    654         break;
    655 
    656     case OP_ADD_LONG_2ADDR:
    657     case OP_SUB_LONG_2ADDR:
    658     case OP_MUL_LONG_2ADDR:
    659     case OP_DIV_LONG_2ADDR:
    660     case OP_REM_LONG_2ADDR:
    661     case OP_AND_LONG_2ADDR:
    662     case OP_OR_LONG_2ADDR:
    663     case OP_XOR_LONG_2ADDR:
    664     case OP_ADD_FLOAT_2ADDR:
    665     case OP_SUB_FLOAT_2ADDR:
    666     case OP_MUL_FLOAT_2ADDR:
    667     case OP_DIV_FLOAT_2ADDR:
    668     case OP_REM_FLOAT_2ADDR:
    669     case OP_ADD_DOUBLE_2ADDR:
    670     case OP_SUB_DOUBLE_2ADDR:
    671     case OP_MUL_DOUBLE_2ADDR:
    672     case OP_DIV_DOUBLE_2ADDR:
    673     case OP_REM_DOUBLE_2ADDR:
    674         /* vA(wide) <- vA(wide), vB(wide) */
    675         /* KILLW(workBits, decInsn.vA); */
    676         GENW(workBits, decInsn.vA);
    677         GENW(workBits, decInsn.vB);
    678         break;
    679 
    680     /* we will only see this if liveness analysis is done after general vfy */
    681     case OP_THROW_VERIFICATION_ERROR:
    682         /* no registers used */
    683         break;
    684 
    685     /* quickened instructions, not expected to appear */
    686     case OP_EXECUTE_INLINE:
    687     case OP_EXECUTE_INLINE_RANGE:
    688     case OP_IGET_QUICK:
    689     case OP_IGET_WIDE_QUICK:
    690     case OP_IGET_OBJECT_QUICK:
    691     case OP_IPUT_QUICK:
    692     case OP_IPUT_WIDE_QUICK:
    693     case OP_IPUT_OBJECT_QUICK:
    694     case OP_INVOKE_VIRTUAL_QUICK:
    695     case OP_INVOKE_VIRTUAL_QUICK_RANGE:
    696     case OP_INVOKE_SUPER_QUICK:
    697     case OP_INVOKE_SUPER_QUICK_RANGE:
    698         /* fall through to failure */
    699 
    700     /* correctness fixes, not expected to appear */
    701     case OP_INVOKE_OBJECT_INIT_RANGE:
    702     case OP_RETURN_VOID_BARRIER:
    703     case OP_SPUT_VOLATILE:
    704     case OP_SPUT_OBJECT_VOLATILE:
    705     case OP_SPUT_WIDE_VOLATILE:
    706     case OP_IPUT_VOLATILE:
    707     case OP_IPUT_OBJECT_VOLATILE:
    708     case OP_IPUT_WIDE_VOLATILE:
    709     case OP_SGET_VOLATILE:
    710     case OP_SGET_OBJECT_VOLATILE:
    711     case OP_SGET_WIDE_VOLATILE:
    712     case OP_IGET_VOLATILE:
    713     case OP_IGET_OBJECT_VOLATILE:
    714     case OP_IGET_WIDE_VOLATILE:
    715         /* fall through to failure */
    716 
    717     /* these should never appear during verification */
    718     case OP_UNUSED_3E:
    719     case OP_UNUSED_3F:
    720     case OP_UNUSED_40:
    721     case OP_UNUSED_41:
    722     case OP_UNUSED_42:
    723     case OP_UNUSED_43:
    724     case OP_UNUSED_73:
    725     case OP_UNUSED_79:
    726     case OP_UNUSED_7A:
    727     case OP_BREAKPOINT:
    728     case OP_UNUSED_FF:
    729         return false;
    730     }
    731 
    732     return true;
    733 }
    734 
    735 /*
    736  * This is a dexDecodeDebugInfo callback, used by markDebugLocals().
    737  */
    738 static void markLocalsCb(void* ctxt, u2 reg, u4 startAddress, u4 endAddress,
    739     const char* name, const char* descriptor, const char* signature)
    740 {
    741     VerifierData* vdata = (VerifierData*) ctxt;
    742     bool verbose = dvmWantVerboseVerification(vdata->method);
    743 
    744     if (verbose) {
    745         ALOGI("%04x-%04x %2d (%s %s)",
    746             startAddress, endAddress, reg, name, descriptor);
    747     }
    748 
    749     bool wide = (descriptor[0] == 'D' || descriptor[0] == 'J');
    750     assert(reg <= vdata->insnRegCount + (wide ? 1 : 0));
    751 
    752     /*
    753      * Set the bit in all GC point instructions in the range
    754      * [startAddress, endAddress).
    755      */
    756     unsigned int idx;
    757     for (idx = startAddress; idx < endAddress; idx++) {
    758         BitVector* liveRegs = vdata->registerLines[idx].liveRegs;
    759         if (liveRegs != NULL) {
    760             if (wide) {
    761                 GENW(liveRegs, reg);
    762             } else {
    763                 GEN(liveRegs, reg);
    764             }
    765         }
    766     }
    767 }
    768 
    769 /*
    770  * Mark all debugger-visible locals as live.
    771  *
    772  * The "locals" table describes the positions of the various locals in the
    773  * stack frame based on the current execution address.  If the debugger
    774  * wants to display one, it issues a request by "slot number".  We need
    775  * to ensure that references in stack slots that might be queried by the
    776  * debugger aren't GCed.
    777  *
    778  * (If the GC had some way to mark the slot as invalid we wouldn't have
    779  * to do this.  We could also have the debugger interface check the
    780  * register map and simply refuse to return a "dead" value, but that's
    781  * potentially confusing since the referred-to object might actually be
    782  * alive, and being able to see it without having to hunt around for a
    783  * "live" stack frame is useful.)
    784  */
    785 static bool markDebugLocals(VerifierData* vdata)
    786 {
    787     const Method* meth = vdata->method;
    788 
    789     dexDecodeDebugInfo(meth->clazz->pDvmDex->pDexFile, dvmGetMethodCode(meth),
    790         meth->clazz->descriptor, meth->prototype.protoIdx, meth->accessFlags,
    791         NULL, markLocalsCb, vdata);
    792 
    793     return true;
    794 }
    795 
    796 
    797 /*
    798  * Dump the liveness bits to the log.
    799  *
    800  * "curIdx" is for display only.
    801  */
    802 static void dumpLiveState(const VerifierData* vdata, u4 curIdx,
    803     const BitVector* workBits)
    804 {
    805     u4 insnRegCount = vdata->insnRegCount;
    806     size_t regCharSize = insnRegCount + (insnRegCount-1)/4 + 2 +1;
    807     char regChars[regCharSize +1];
    808     unsigned int idx;
    809 
    810     memset(regChars, ' ', regCharSize);
    811     regChars[0] = '[';
    812     if (insnRegCount == 0)
    813         regChars[1] = ']';
    814     else
    815         regChars[1 + (insnRegCount-1) + (insnRegCount-1)/4 +1] = ']';
    816     regChars[regCharSize] = '\0';
    817 
    818     for (idx = 0; idx < insnRegCount; idx++) {
    819         char ch = dvmIsBitSet(workBits, idx) ? '+' : '-';
    820         regChars[1 + idx + (idx/4)] = ch;
    821     }
    822 
    823     ALOGI("0x%04x %s", curIdx, regChars);
    824 }
    825