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;
     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     return result;
    277 }
    278 
    279 
    280 /*
    281  * Add a register to the LIVE set.
    282  */
    283 static inline void GEN(BitVector* workBits, u4 regIndex)
    284 {
    285     dvmSetBit(workBits, regIndex);
    286 }
    287 
    288 /*
    289  * Add a register pair to the LIVE set.
    290  */
    291 static inline void GENW(BitVector* workBits, u4 regIndex)
    292 {
    293     dvmSetBit(workBits, regIndex);
    294     dvmSetBit(workBits, regIndex+1);
    295 }
    296 
    297 /*
    298  * Remove a register from the LIVE set.
    299  */
    300 static inline void KILL(BitVector* workBits, u4 regIndex)
    301 {
    302     dvmClearBit(workBits, regIndex);
    303 }
    304 
    305 /*
    306  * Remove a register pair from the LIVE set.
    307  */
    308 static inline void KILLW(BitVector* workBits, u4 regIndex)
    309 {
    310     dvmClearBit(workBits, regIndex);
    311     dvmClearBit(workBits, regIndex+1);
    312 }
    313 
    314 /*
    315  * Process a single instruction.
    316  *
    317  * Returns "false" if something goes fatally wrong.
    318  */
    319 static bool processInstruction(VerifierData* vdata, u4 insnIdx,
    320     BitVector* workBits)
    321 {
    322     const Method* meth = vdata->method;
    323     const u2* insns = meth->insns + insnIdx;
    324     DecodedInstruction decInsn;
    325 
    326     dexDecodeInstruction(insns, &decInsn);
    327 
    328     /*
    329      * Add registers to the "GEN" or "KILL" sets.  We want to do KILL
    330      * before GEN to handle cases where the source and destination
    331      * register is the same.
    332      */
    333     switch (decInsn.opcode) {
    334     case OP_NOP:
    335     case OP_RETURN_VOID:
    336     case OP_GOTO:
    337     case OP_GOTO_16:
    338     case OP_GOTO_32:
    339         /* no registers are used */
    340         break;
    341 
    342     case OP_RETURN:
    343     case OP_RETURN_OBJECT:
    344     case OP_MONITOR_ENTER:
    345     case OP_MONITOR_EXIT:
    346     case OP_CHECK_CAST:
    347     case OP_THROW:
    348     case OP_PACKED_SWITCH:
    349     case OP_SPARSE_SWITCH:
    350     case OP_FILL_ARRAY_DATA:
    351     case OP_IF_EQZ:
    352     case OP_IF_NEZ:
    353     case OP_IF_LTZ:
    354     case OP_IF_GEZ:
    355     case OP_IF_GTZ:
    356     case OP_IF_LEZ:
    357     case OP_SPUT:
    358     case OP_SPUT_BOOLEAN:
    359     case OP_SPUT_BYTE:
    360     case OP_SPUT_CHAR:
    361     case OP_SPUT_SHORT:
    362     case OP_SPUT_OBJECT:
    363         /* action <- vA */
    364         GEN(workBits, decInsn.vA);
    365         break;
    366 
    367     case OP_RETURN_WIDE:
    368     case OP_SPUT_WIDE:
    369         /* action <- vA(wide) */
    370         GENW(workBits, decInsn.vA);
    371         break;
    372 
    373     case OP_IF_EQ:
    374     case OP_IF_NE:
    375     case OP_IF_LT:
    376     case OP_IF_GE:
    377     case OP_IF_GT:
    378     case OP_IF_LE:
    379     case OP_IPUT:
    380     case OP_IPUT_BOOLEAN:
    381     case OP_IPUT_BYTE:
    382     case OP_IPUT_CHAR:
    383     case OP_IPUT_SHORT:
    384     case OP_IPUT_OBJECT:
    385         /* action <- vA, vB */
    386         GEN(workBits, decInsn.vA);
    387         GEN(workBits, decInsn.vB);
    388         break;
    389 
    390     case OP_IPUT_WIDE:
    391         /* action <- vA(wide), vB */
    392         GENW(workBits, decInsn.vA);
    393         GEN(workBits, decInsn.vB);
    394         break;
    395 
    396     case OP_APUT:
    397     case OP_APUT_BOOLEAN:
    398     case OP_APUT_BYTE:
    399     case OP_APUT_CHAR:
    400     case OP_APUT_SHORT:
    401     case OP_APUT_OBJECT:
    402         /* action <- vA, vB, vC */
    403         GEN(workBits, decInsn.vA);
    404         GEN(workBits, decInsn.vB);
    405         GEN(workBits, decInsn.vC);
    406         break;
    407 
    408     case OP_APUT_WIDE:
    409         /* action <- vA(wide), vB, vC */
    410         GENW(workBits, decInsn.vA);
    411         GEN(workBits, decInsn.vB);
    412         GEN(workBits, decInsn.vC);
    413         break;
    414 
    415     case OP_FILLED_NEW_ARRAY:
    416     case OP_INVOKE_VIRTUAL:
    417     case OP_INVOKE_SUPER:
    418     case OP_INVOKE_DIRECT:
    419     case OP_INVOKE_STATIC:
    420     case OP_INVOKE_INTERFACE:
    421         /* action <- vararg */
    422         {
    423             unsigned int idx;
    424             for (idx = 0; idx < decInsn.vA; idx++) {
    425                 GEN(workBits, decInsn.arg[idx]);
    426             }
    427         }
    428         break;
    429 
    430     case OP_FILLED_NEW_ARRAY_RANGE:
    431     case OP_INVOKE_VIRTUAL_RANGE:
    432     case OP_INVOKE_SUPER_RANGE:
    433     case OP_INVOKE_DIRECT_RANGE:
    434     case OP_INVOKE_STATIC_RANGE:
    435     case OP_INVOKE_INTERFACE_RANGE:
    436         /* action <- vararg/range */
    437         {
    438             unsigned int idx;
    439             for (idx = 0; idx < decInsn.vA; idx++) {
    440                 GEN(workBits, decInsn.vC + idx);
    441             }
    442         }
    443         break;
    444 
    445     case OP_MOVE_RESULT:
    446     case OP_MOVE_RESULT_WIDE:
    447     case OP_MOVE_RESULT_OBJECT:
    448     case OP_MOVE_EXCEPTION:
    449     case OP_CONST_4:
    450     case OP_CONST_16:
    451     case OP_CONST:
    452     case OP_CONST_HIGH16:
    453     case OP_CONST_STRING:
    454     case OP_CONST_STRING_JUMBO:
    455     case OP_CONST_CLASS:
    456     case OP_NEW_INSTANCE:
    457     case OP_SGET:
    458     case OP_SGET_BOOLEAN:
    459     case OP_SGET_BYTE:
    460     case OP_SGET_CHAR:
    461     case OP_SGET_SHORT:
    462     case OP_SGET_OBJECT:
    463         /* vA <- value */
    464         KILL(workBits, decInsn.vA);
    465         break;
    466 
    467     case OP_CONST_WIDE_16:
    468     case OP_CONST_WIDE_32:
    469     case OP_CONST_WIDE:
    470     case OP_CONST_WIDE_HIGH16:
    471     case OP_SGET_WIDE:
    472         /* vA(wide) <- value */
    473         KILLW(workBits, decInsn.vA);
    474         break;
    475 
    476     case OP_MOVE:
    477     case OP_MOVE_FROM16:
    478     case OP_MOVE_16:
    479     case OP_MOVE_OBJECT:
    480     case OP_MOVE_OBJECT_FROM16:
    481     case OP_MOVE_OBJECT_16:
    482     case OP_INSTANCE_OF:
    483     case OP_ARRAY_LENGTH:
    484     case OP_NEW_ARRAY:
    485     case OP_IGET:
    486     case OP_IGET_BOOLEAN:
    487     case OP_IGET_BYTE:
    488     case OP_IGET_CHAR:
    489     case OP_IGET_SHORT:
    490     case OP_IGET_OBJECT:
    491     case OP_NEG_INT:
    492     case OP_NOT_INT:
    493     case OP_NEG_FLOAT:
    494     case OP_INT_TO_FLOAT:
    495     case OP_FLOAT_TO_INT:
    496     case OP_INT_TO_BYTE:
    497     case OP_INT_TO_CHAR:
    498     case OP_INT_TO_SHORT:
    499     case OP_ADD_INT_LIT16:
    500     case OP_RSUB_INT:
    501     case OP_MUL_INT_LIT16:
    502     case OP_DIV_INT_LIT16:
    503     case OP_REM_INT_LIT16:
    504     case OP_AND_INT_LIT16:
    505     case OP_OR_INT_LIT16:
    506     case OP_XOR_INT_LIT16:
    507     case OP_ADD_INT_LIT8:
    508     case OP_RSUB_INT_LIT8:
    509     case OP_MUL_INT_LIT8:
    510     case OP_DIV_INT_LIT8:
    511     case OP_REM_INT_LIT8:
    512     case OP_SHL_INT_LIT8:
    513     case OP_SHR_INT_LIT8:
    514     case OP_USHR_INT_LIT8:
    515     case OP_AND_INT_LIT8:
    516     case OP_OR_INT_LIT8:
    517     case OP_XOR_INT_LIT8:
    518         /* vA <- vB */
    519         KILL(workBits, decInsn.vA);
    520         GEN(workBits, decInsn.vB);
    521         break;
    522 
    523     case OP_IGET_WIDE:
    524     case OP_INT_TO_LONG:
    525     case OP_INT_TO_DOUBLE:
    526     case OP_FLOAT_TO_LONG:
    527     case OP_FLOAT_TO_DOUBLE:
    528         /* vA(wide) <- vB */
    529         KILLW(workBits, decInsn.vA);
    530         GEN(workBits, decInsn.vB);
    531         break;
    532 
    533     case OP_LONG_TO_INT:
    534     case OP_LONG_TO_FLOAT:
    535     case OP_DOUBLE_TO_INT:
    536     case OP_DOUBLE_TO_FLOAT:
    537         /* vA <- vB(wide) */
    538         KILL(workBits, decInsn.vA);
    539         GENW(workBits, decInsn.vB);
    540         break;
    541 
    542     case OP_MOVE_WIDE:
    543     case OP_MOVE_WIDE_FROM16:
    544     case OP_MOVE_WIDE_16:
    545     case OP_NEG_LONG:
    546     case OP_NOT_LONG:
    547     case OP_NEG_DOUBLE:
    548     case OP_LONG_TO_DOUBLE:
    549     case OP_DOUBLE_TO_LONG:
    550         /* vA(wide) <- vB(wide) */
    551         KILLW(workBits, decInsn.vA);
    552         GENW(workBits, decInsn.vB);
    553         break;
    554 
    555     case OP_CMPL_FLOAT:
    556     case OP_CMPG_FLOAT:
    557     case OP_AGET:
    558     case OP_AGET_BOOLEAN:
    559     case OP_AGET_BYTE:
    560     case OP_AGET_CHAR:
    561     case OP_AGET_SHORT:
    562     case OP_AGET_OBJECT:
    563     case OP_ADD_INT:
    564     case OP_SUB_INT:
    565     case OP_MUL_INT:
    566     case OP_REM_INT:
    567     case OP_DIV_INT:
    568     case OP_AND_INT:
    569     case OP_OR_INT:
    570     case OP_XOR_INT:
    571     case OP_SHL_INT:
    572     case OP_SHR_INT:
    573     case OP_USHR_INT:
    574     case OP_ADD_FLOAT:
    575     case OP_SUB_FLOAT:
    576     case OP_MUL_FLOAT:
    577     case OP_DIV_FLOAT:
    578     case OP_REM_FLOAT:
    579         /* vA <- vB, vC */
    580         KILL(workBits, decInsn.vA);
    581         GEN(workBits, decInsn.vB);
    582         GEN(workBits, decInsn.vC);
    583         break;
    584 
    585     case OP_AGET_WIDE:
    586         /* vA(wide) <- vB, vC */
    587         KILLW(workBits, decInsn.vA);
    588         GEN(workBits, decInsn.vB);
    589         GEN(workBits, decInsn.vC);
    590         break;
    591 
    592     case OP_CMPL_DOUBLE:
    593     case OP_CMPG_DOUBLE:
    594     case OP_CMP_LONG:
    595         /* vA <- vB(wide), vC(wide) */
    596         KILL(workBits, decInsn.vA);
    597         GENW(workBits, decInsn.vB);
    598         GENW(workBits, decInsn.vC);
    599         break;
    600 
    601     case OP_SHL_LONG:
    602     case OP_SHR_LONG:
    603     case OP_USHR_LONG:
    604         /* vA(wide) <- vB(wide), vC */
    605         KILLW(workBits, decInsn.vA);
    606         GENW(workBits, decInsn.vB);
    607         GEN(workBits, decInsn.vC);
    608         break;
    609 
    610     case OP_ADD_LONG:
    611     case OP_SUB_LONG:
    612     case OP_MUL_LONG:
    613     case OP_DIV_LONG:
    614     case OP_REM_LONG:
    615     case OP_AND_LONG:
    616     case OP_OR_LONG:
    617     case OP_XOR_LONG:
    618     case OP_ADD_DOUBLE:
    619     case OP_SUB_DOUBLE:
    620     case OP_MUL_DOUBLE:
    621     case OP_DIV_DOUBLE:
    622     case OP_REM_DOUBLE:
    623         /* vA(wide) <- vB(wide), vC(wide) */
    624         KILLW(workBits, decInsn.vA);
    625         GENW(workBits, decInsn.vB);
    626         GENW(workBits, decInsn.vC);
    627         break;
    628 
    629     case OP_ADD_INT_2ADDR:
    630     case OP_SUB_INT_2ADDR:
    631     case OP_MUL_INT_2ADDR:
    632     case OP_REM_INT_2ADDR:
    633     case OP_SHL_INT_2ADDR:
    634     case OP_SHR_INT_2ADDR:
    635     case OP_USHR_INT_2ADDR:
    636     case OP_AND_INT_2ADDR:
    637     case OP_OR_INT_2ADDR:
    638     case OP_XOR_INT_2ADDR:
    639     case OP_DIV_INT_2ADDR:
    640         /* vA <- vA, vB */
    641         /* KILL(workBits, decInsn.vA); */
    642         GEN(workBits, decInsn.vA);
    643         GEN(workBits, decInsn.vB);
    644         break;
    645 
    646     case OP_SHL_LONG_2ADDR:
    647     case OP_SHR_LONG_2ADDR:
    648     case OP_USHR_LONG_2ADDR:
    649         /* vA(wide) <- vA(wide), vB */
    650         /* KILLW(workBits, decInsn.vA); */
    651         GENW(workBits, decInsn.vA);
    652         GEN(workBits, decInsn.vB);
    653         break;
    654 
    655     case OP_ADD_LONG_2ADDR:
    656     case OP_SUB_LONG_2ADDR:
    657     case OP_MUL_LONG_2ADDR:
    658     case OP_DIV_LONG_2ADDR:
    659     case OP_REM_LONG_2ADDR:
    660     case OP_AND_LONG_2ADDR:
    661     case OP_OR_LONG_2ADDR:
    662     case OP_XOR_LONG_2ADDR:
    663     case OP_ADD_FLOAT_2ADDR:
    664     case OP_SUB_FLOAT_2ADDR:
    665     case OP_MUL_FLOAT_2ADDR:
    666     case OP_DIV_FLOAT_2ADDR:
    667     case OP_REM_FLOAT_2ADDR:
    668     case OP_ADD_DOUBLE_2ADDR:
    669     case OP_SUB_DOUBLE_2ADDR:
    670     case OP_MUL_DOUBLE_2ADDR:
    671     case OP_DIV_DOUBLE_2ADDR:
    672     case OP_REM_DOUBLE_2ADDR:
    673         /* vA(wide) <- vA(wide), vB(wide) */
    674         /* KILLW(workBits, decInsn.vA); */
    675         GENW(workBits, decInsn.vA);
    676         GENW(workBits, decInsn.vB);
    677         break;
    678 
    679     /* we will only see this if liveness analysis is done after general vfy */
    680     case OP_THROW_VERIFICATION_ERROR:
    681         /* no registers used */
    682         break;
    683 
    684     /* quickened instructions, not expected to appear */
    685     case OP_EXECUTE_INLINE:
    686     case OP_EXECUTE_INLINE_RANGE:
    687     case OP_IGET_QUICK:
    688     case OP_IGET_WIDE_QUICK:
    689     case OP_IGET_OBJECT_QUICK:
    690     case OP_IPUT_QUICK:
    691     case OP_IPUT_WIDE_QUICK:
    692     case OP_IPUT_OBJECT_QUICK:
    693     case OP_INVOKE_VIRTUAL_QUICK:
    694     case OP_INVOKE_VIRTUAL_QUICK_RANGE:
    695     case OP_INVOKE_SUPER_QUICK:
    696     case OP_INVOKE_SUPER_QUICK_RANGE:
    697         /* fall through to failure */
    698 
    699     /* correctness fixes, not expected to appear */
    700     case OP_INVOKE_OBJECT_INIT_RANGE:
    701     case OP_RETURN_VOID_BARRIER:
    702     case OP_SPUT_VOLATILE:
    703     case OP_SPUT_OBJECT_VOLATILE:
    704     case OP_SPUT_WIDE_VOLATILE:
    705     case OP_IPUT_VOLATILE:
    706     case OP_IPUT_OBJECT_VOLATILE:
    707     case OP_IPUT_WIDE_VOLATILE:
    708     case OP_SGET_VOLATILE:
    709     case OP_SGET_OBJECT_VOLATILE:
    710     case OP_SGET_WIDE_VOLATILE:
    711     case OP_IGET_VOLATILE:
    712     case OP_IGET_OBJECT_VOLATILE:
    713     case OP_IGET_WIDE_VOLATILE:
    714         /* fall through to failure */
    715 
    716     /* these should never appear during verification */
    717     case OP_UNUSED_3E:
    718     case OP_UNUSED_3F:
    719     case OP_UNUSED_40:
    720     case OP_UNUSED_41:
    721     case OP_UNUSED_42:
    722     case OP_UNUSED_43:
    723     case OP_UNUSED_73:
    724     case OP_UNUSED_79:
    725     case OP_UNUSED_7A:
    726     case OP_BREAKPOINT:
    727     case OP_UNUSED_FF:
    728         return false;
    729     }
    730 
    731     return true;
    732 }
    733 
    734 /*
    735  * This is a dexDecodeDebugInfo callback, used by markDebugLocals().
    736  */
    737 static void markLocalsCb(void* ctxt, u2 reg, u4 startAddress, u4 endAddress,
    738     const char* name, const char* descriptor, const char* signature)
    739 {
    740     VerifierData* vdata = (VerifierData*) ctxt;
    741     bool verbose = dvmWantVerboseVerification(vdata->method);
    742 
    743     if (verbose) {
    744         ALOGI("%04x-%04x %2d (%s %s)",
    745             startAddress, endAddress, reg, name, descriptor);
    746     }
    747 
    748     bool wide = (descriptor[0] == 'D' || descriptor[0] == 'J');
    749     assert(reg <= vdata->insnRegCount + (wide ? 1 : 0));
    750 
    751     /*
    752      * Set the bit in all GC point instructions in the range
    753      * [startAddress, endAddress).
    754      */
    755     unsigned int idx;
    756     for (idx = startAddress; idx < endAddress; idx++) {
    757         BitVector* liveRegs = vdata->registerLines[idx].liveRegs;
    758         if (liveRegs != NULL) {
    759             if (wide) {
    760                 GENW(liveRegs, reg);
    761             } else {
    762                 GEN(liveRegs, reg);
    763             }
    764         }
    765     }
    766 }
    767 
    768 /*
    769  * Mark all debugger-visible locals as live.
    770  *
    771  * The "locals" table describes the positions of the various locals in the
    772  * stack frame based on the current execution address.  If the debugger
    773  * wants to display one, it issues a request by "slot number".  We need
    774  * to ensure that references in stack slots that might be queried by the
    775  * debugger aren't GCed.
    776  *
    777  * (If the GC had some way to mark the slot as invalid we wouldn't have
    778  * to do this.  We could also have the debugger interface check the
    779  * register map and simply refuse to return a "dead" value, but that's
    780  * potentially confusing since the referred-to object might actually be
    781  * alive, and being able to see it without having to hunt around for a
    782  * "live" stack frame is useful.)
    783  */
    784 static bool markDebugLocals(VerifierData* vdata)
    785 {
    786     const Method* meth = vdata->method;
    787 
    788     dexDecodeDebugInfo(meth->clazz->pDvmDex->pDexFile, dvmGetMethodCode(meth),
    789         meth->clazz->descriptor, meth->prototype.protoIdx, meth->accessFlags,
    790         NULL, markLocalsCb, vdata);
    791 
    792     return true;
    793 }
    794 
    795 
    796 /*
    797  * Dump the liveness bits to the log.
    798  *
    799  * "curIdx" is for display only.
    800  */
    801 static void dumpLiveState(const VerifierData* vdata, u4 curIdx,
    802     const BitVector* workBits)
    803 {
    804     u4 insnRegCount = vdata->insnRegCount;
    805     size_t regCharSize = insnRegCount + (insnRegCount-1)/4 + 2 +1;
    806     char regChars[regCharSize +1];
    807     unsigned int idx;
    808 
    809     memset(regChars, ' ', regCharSize);
    810     regChars[0] = '[';
    811     if (insnRegCount == 0)
    812         regChars[1] = ']';
    813     else
    814         regChars[1 + (insnRegCount-1) + (insnRegCount-1)/4 +1] = ']';
    815     regChars[regCharSize] = '\0';
    816 
    817     for (idx = 0; idx < insnRegCount; idx++) {
    818         char ch = dvmIsBitSet(workBits, idx) ? '+' : '-';
    819         regChars[1 + idx + (idx/4)] = ch;
    820     }
    821 
    822     ALOGI("0x%04x %s", curIdx, regChars);
    823 }
    824