| /* |
| * Copyright (C) 2010 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. |
| */ |
| |
| /* |
| * Liveness analysis for Dalvik bytecode. |
| */ |
| #include "Dalvik.h" |
| #include "analysis/Liveness.h" |
| #include "analysis/CodeVerify.h" |
| |
| static bool processInstruction(VerifierData* vdata, u4 curIdx, |
| BitVector* workBits); |
| static bool markDebugLocals(VerifierData* vdata); |
| static void dumpLiveState(const VerifierData* vdata, u4 curIdx, |
| const BitVector* workBits); |
| |
| |
| /* |
| * Create a table of instruction widths that indicate the width of the |
| * *previous* instruction. The values are copied from the width table |
| * in "vdata", not derived from the instruction stream. |
| * |
| * Caller must free the return value. |
| */ |
| static InstructionWidth* createBackwardWidthTable(VerifierData* vdata) |
| { |
| InstructionWidth* widths; |
| |
| widths = (InstructionWidth*) |
| calloc(vdata->insnsSize, sizeof(InstructionWidth)); |
| if (widths == NULL) |
| return NULL; |
| |
| unsigned int idx; |
| u4 insnWidth = 0; |
| for (idx = 0; idx < vdata->insnsSize; ) { |
| widths[idx] = insnWidth; |
| insnWidth = dvmInsnGetWidth(vdata->insnFlags, idx); |
| idx += insnWidth; |
| } |
| |
| return widths; |
| } |
| |
| /* |
| * Compute the "liveness" of every register at all GC points. |
| */ |
| bool dvmComputeLiveness(VerifierData* vdata) |
| { |
| const InsnFlags* insnFlags = vdata->insnFlags; |
| InstructionWidth* backwardWidth; |
| VfyBasicBlock* startGuess = NULL; |
| BitVector* workBits; |
| bool result = false; |
| |
| bool verbose = false; //= dvmWantVerboseVerification(vdata->method); |
| if (verbose) { |
| const Method* meth = vdata->method; |
| LOGI("Computing liveness for %s.%s:%s\n", |
| meth->clazz->descriptor, meth->name, meth->shorty); |
| } |
| |
| assert(vdata->registerLines != NULL); |
| |
| backwardWidth = createBackwardWidthTable(vdata); |
| if (backwardWidth == NULL) |
| goto bail; |
| |
| /* |
| * Allocate space for intra-block work set. Does not include space |
| * for method result "registers", which aren't visible to the GC. |
| * (They would be made live by move-result and then die on the |
| * instruction immediately before it.) |
| */ |
| workBits = dvmAllocBitVector(vdata->insnRegCount, false); |
| if (workBits == NULL) |
| goto bail; |
| |
| /* |
| * We continue until all blocks have been visited, and no block |
| * requires further attention ("visited" is set and "changed" is |
| * clear). |
| * |
| * TODO: consider creating a "dense" array of basic blocks to make |
| * the walking faster. |
| */ |
| int iter = 0; |
| while (true) { |
| VfyBasicBlock* workBlock = NULL; |
| unsigned int idx; |
| |
| if (iter++ > 100000) { |
| LOG_VFY_METH(vdata->method, "oh dear"); |
| dvmAbort(); |
| } |
| |
| /* |
| * If a block is marked "changed", we stop and handle it. If it |
| * just hasn't been visited yet, we remember it but keep searching |
| * for one that has been changed. |
| * |
| * The thought here is that this is more likely to let us work |
| * from end to start, which reduces the amount of re-evaluation |
| * required (both by using "changed" as a work list, and by picking |
| * un-visited blocks from the tail end of the method). |
| */ |
| if (startGuess != NULL) { |
| assert(startGuess->changed); |
| workBlock = startGuess; |
| } else { |
| for (idx = 0; idx < vdata->insnsSize; idx++) { |
| VfyBasicBlock* block = vdata->basicBlocks[idx]; |
| if (block == NULL) |
| continue; |
| |
| if (block->changed) { |
| workBlock = block; |
| break; |
| } else if (!block->visited) { |
| workBlock = block; |
| } |
| } |
| } |
| |
| if (workBlock == NULL) { |
| /* all done */ |
| break; |
| } |
| |
| assert(workBlock->changed || !workBlock->visited); |
| startGuess = NULL; |
| |
| /* |
| * Load work bits. These represent the liveness of registers |
| * after the last instruction in the block has finished executing. |
| */ |
| assert(workBlock->liveRegs != NULL); |
| dvmCopyBitVector(workBits, workBlock->liveRegs); |
| if (verbose) { |
| LOGI("Loaded work bits from last=0x%04x\n", workBlock->lastAddr); |
| dumpLiveState(vdata, 0xfffd, workBlock->liveRegs); |
| dumpLiveState(vdata, 0xffff, workBits); |
| } |
| |
| /* |
| * Process a single basic block. |
| * |
| * If this instruction is a GC point, we want to save the result |
| * in the RegisterLine. |
| * |
| * We don't break basic blocks on every GC point -- in particular, |
| * instructions that might throw but have no "try" block don't |
| * end a basic block -- so there could be more than one GC point |
| * in a given basic block. |
| * |
| * We could change this, but it turns out to be not all that useful. |
| * At first glance it appears that we could share the liveness bit |
| * vector between the basic block struct and the register line, |
| * but the basic block needs to reflect the state *after* the |
| * instruction has finished, while the GC points need to describe |
| * the state before the instruction starts. |
| */ |
| u4 curIdx = workBlock->lastAddr; |
| while (true) { |
| if (!processInstruction(vdata, curIdx, workBits)) |
| goto bail; |
| |
| if (verbose) { |
| dumpLiveState(vdata, curIdx + 0x8000, workBits); |
| } |
| |
| if (dvmInsnIsGcPoint(insnFlags, curIdx)) { |
| BitVector* lineBits = vdata->registerLines[curIdx].liveRegs; |
| if (lineBits == NULL) { |
| lineBits = vdata->registerLines[curIdx].liveRegs = |
| dvmAllocBitVector(vdata->insnRegCount, false); |
| } |
| dvmCopyBitVector(lineBits, workBits); |
| } |
| |
| if (curIdx == workBlock->firstAddr) |
| break; |
| assert(curIdx >= backwardWidth[curIdx]); |
| curIdx -= backwardWidth[curIdx]; |
| } |
| |
| workBlock->visited = true; |
| workBlock->changed = false; |
| |
| if (verbose) { |
| dumpLiveState(vdata, curIdx, workBits); |
| } |
| |
| /* |
| * Merge changes to all predecessors. If the new bits don't match |
| * the old bits, set the "changed" flag. |
| */ |
| PointerSet* preds = workBlock->predecessors; |
| size_t numPreds = dvmPointerSetGetCount(preds); |
| unsigned int predIdx; |
| |
| for (predIdx = 0; predIdx < numPreds; predIdx++) { |
| VfyBasicBlock* pred = |
| (VfyBasicBlock*) dvmPointerSetGetEntry(preds, predIdx); |
| |
| pred->changed = dvmCheckMergeBitVectors(pred->liveRegs, workBits); |
| if (verbose) { |
| LOGI("merging cur=%04x into pred last=%04x (ch=%d)\n", |
| curIdx, pred->lastAddr, pred->changed); |
| dumpLiveState(vdata, 0xfffa, pred->liveRegs); |
| dumpLiveState(vdata, 0xfffb, workBits); |
| } |
| |
| /* |
| * We want to set the "changed" flag on unvisited predecessors |
| * as a way of guiding the verifier through basic blocks in |
| * a reasonable order. We can't count on variable liveness |
| * changing, so we force "changed" to true even if it hasn't. |
| */ |
| if (!pred->visited) |
| pred->changed = true; |
| |
| /* |
| * Keep track of one of the changed blocks so we can start |
| * there instead of having to scan through the list. |
| */ |
| if (pred->changed) |
| startGuess = pred; |
| } |
| } |
| |
| #ifndef NDEBUG |
| /* |
| * Sanity check: verify that all GC point register lines have a |
| * liveness bit vector allocated. Also, we're not expecting non-GC |
| * points to have them. |
| */ |
| u4 checkIdx; |
| for (checkIdx = 0; checkIdx < vdata->insnsSize; ) { |
| if (dvmInsnIsGcPoint(insnFlags, checkIdx)) { |
| if (vdata->registerLines[checkIdx].liveRegs == NULL) { |
| LOG_VFY_METH(vdata->method, |
| "GLITCH: no liveRegs for GC point 0x%04x\n", checkIdx); |
| dvmAbort(); |
| } |
| } else if (vdata->registerLines[checkIdx].liveRegs != NULL) { |
| LOG_VFY_METH(vdata->method, |
| "GLITCH: liveRegs for non-GC point 0x%04x\n", checkIdx); |
| dvmAbort(); |
| } |
| u4 insnWidth = dvmInsnGetWidth(insnFlags, checkIdx); |
| checkIdx += insnWidth; |
| } |
| #endif |
| |
| /* |
| * Factor in the debug info, if any. |
| */ |
| if (!markDebugLocals(vdata)) |
| goto bail; |
| |
| result = true; |
| |
| bail: |
| free(backwardWidth); |
| return result; |
| } |
| |
| |
| /* |
| * Add a register to the LIVE set. |
| */ |
| static inline void GEN(BitVector* workBits, u4 regIndex) |
| { |
| dvmSetBit(workBits, regIndex); |
| } |
| |
| /* |
| * Add a register pair to the LIVE set. |
| */ |
| static inline void GENW(BitVector* workBits, u4 regIndex) |
| { |
| dvmSetBit(workBits, regIndex); |
| dvmSetBit(workBits, regIndex+1); |
| } |
| |
| /* |
| * Remove a register from the LIVE set. |
| */ |
| static inline void KILL(BitVector* workBits, u4 regIndex) |
| { |
| dvmClearBit(workBits, regIndex); |
| } |
| |
| /* |
| * Remove a register pair from the LIVE set. |
| */ |
| static inline void KILLW(BitVector* workBits, u4 regIndex) |
| { |
| dvmClearBit(workBits, regIndex); |
| dvmClearBit(workBits, regIndex+1); |
| } |
| |
| /* |
| * Process a single instruction. |
| * |
| * Returns "false" if something goes fatally wrong. |
| */ |
| static bool processInstruction(VerifierData* vdata, u4 insnIdx, |
| BitVector* workBits) |
| { |
| const Method* meth = vdata->method; |
| const u2* insns = meth->insns + insnIdx; |
| DecodedInstruction decInsn; |
| |
| dexDecodeInstruction(insns, &decInsn); |
| |
| /* |
| * Add registers to the "GEN" or "KILL" sets. We want to do KILL |
| * before GEN to handle cases where the source and destination |
| * register is the same. |
| */ |
| switch (decInsn.opcode) { |
| case OP_NOP: |
| case OP_RETURN_VOID: |
| case OP_GOTO: |
| case OP_GOTO_16: |
| case OP_GOTO_32: |
| /* no registers are used */ |
| break; |
| |
| case OP_RETURN: |
| case OP_RETURN_OBJECT: |
| case OP_MONITOR_ENTER: |
| case OP_MONITOR_EXIT: |
| case OP_CHECK_CAST: |
| case OP_CHECK_CAST_JUMBO: |
| case OP_THROW: |
| case OP_PACKED_SWITCH: |
| case OP_SPARSE_SWITCH: |
| case OP_FILL_ARRAY_DATA: |
| case OP_IF_EQZ: |
| case OP_IF_NEZ: |
| case OP_IF_LTZ: |
| case OP_IF_GEZ: |
| case OP_IF_GTZ: |
| case OP_IF_LEZ: |
| case OP_SPUT: |
| case OP_SPUT_VOLATILE: |
| case OP_SPUT_JUMBO: |
| case OP_SPUT_VOLATILE_JUMBO: |
| case OP_SPUT_BOOLEAN: |
| case OP_SPUT_BOOLEAN_JUMBO: |
| case OP_SPUT_BYTE: |
| case OP_SPUT_BYTE_JUMBO: |
| case OP_SPUT_CHAR: |
| case OP_SPUT_CHAR_JUMBO: |
| case OP_SPUT_SHORT: |
| case OP_SPUT_SHORT_JUMBO: |
| case OP_SPUT_OBJECT: |
| case OP_SPUT_OBJECT_VOLATILE: |
| case OP_SPUT_OBJECT_JUMBO: |
| case OP_SPUT_OBJECT_VOLATILE_JUMBO: |
| /* action <- vA */ |
| GEN(workBits, decInsn.vA); |
| break; |
| |
| case OP_RETURN_WIDE: |
| case OP_SPUT_WIDE: |
| case OP_SPUT_WIDE_VOLATILE: |
| case OP_SPUT_WIDE_JUMBO: |
| case OP_SPUT_WIDE_VOLATILE_JUMBO: |
| /* action <- vA(wide) */ |
| GENW(workBits, decInsn.vA); |
| break; |
| |
| case OP_IF_EQ: |
| case OP_IF_NE: |
| case OP_IF_LT: |
| case OP_IF_GE: |
| case OP_IF_GT: |
| case OP_IF_LE: |
| case OP_IPUT: |
| case OP_IPUT_VOLATILE: |
| case OP_IPUT_JUMBO: |
| case OP_IPUT_VOLATILE_JUMBO: |
| case OP_IPUT_BOOLEAN: |
| case OP_IPUT_BOOLEAN_JUMBO: |
| case OP_IPUT_BYTE: |
| case OP_IPUT_BYTE_JUMBO: |
| case OP_IPUT_CHAR: |
| case OP_IPUT_CHAR_JUMBO: |
| case OP_IPUT_SHORT: |
| case OP_IPUT_SHORT_JUMBO: |
| case OP_IPUT_OBJECT: |
| case OP_IPUT_OBJECT_VOLATILE: |
| case OP_IPUT_OBJECT_JUMBO: |
| case OP_IPUT_OBJECT_VOLATILE_JUMBO: |
| /* action <- vA, vB */ |
| GEN(workBits, decInsn.vA); |
| GEN(workBits, decInsn.vB); |
| break; |
| |
| case OP_IPUT_WIDE: |
| case OP_IPUT_WIDE_VOLATILE: |
| case OP_IPUT_WIDE_JUMBO: |
| case OP_IPUT_WIDE_VOLATILE_JUMBO: |
| /* action <- vA(wide), vB */ |
| GENW(workBits, decInsn.vA); |
| GEN(workBits, decInsn.vB); |
| break; |
| |
| case OP_APUT: |
| case OP_APUT_BOOLEAN: |
| case OP_APUT_BYTE: |
| case OP_APUT_CHAR: |
| case OP_APUT_SHORT: |
| case OP_APUT_OBJECT: |
| /* action <- vA, vB, vC */ |
| GEN(workBits, decInsn.vA); |
| GEN(workBits, decInsn.vB); |
| GEN(workBits, decInsn.vC); |
| break; |
| |
| case OP_APUT_WIDE: |
| /* action <- vA(wide), vB, vC */ |
| GENW(workBits, decInsn.vA); |
| GEN(workBits, decInsn.vB); |
| GEN(workBits, decInsn.vC); |
| break; |
| |
| case OP_FILLED_NEW_ARRAY: |
| case OP_INVOKE_VIRTUAL: |
| case OP_INVOKE_SUPER: |
| case OP_INVOKE_DIRECT: |
| case OP_INVOKE_STATIC: |
| case OP_INVOKE_INTERFACE: |
| /* action <- vararg */ |
| { |
| unsigned int idx; |
| for (idx = 0; idx < decInsn.vA; idx++) { |
| GEN(workBits, decInsn.arg[idx]); |
| } |
| } |
| break; |
| |
| case OP_FILLED_NEW_ARRAY_RANGE: |
| case OP_FILLED_NEW_ARRAY_JUMBO: |
| case OP_INVOKE_VIRTUAL_RANGE: |
| case OP_INVOKE_VIRTUAL_JUMBO: |
| case OP_INVOKE_SUPER_RANGE: |
| case OP_INVOKE_SUPER_JUMBO: |
| case OP_INVOKE_DIRECT_RANGE: |
| case OP_INVOKE_DIRECT_JUMBO: |
| case OP_INVOKE_STATIC_RANGE: |
| case OP_INVOKE_STATIC_JUMBO: |
| case OP_INVOKE_INTERFACE_RANGE: |
| case OP_INVOKE_INTERFACE_JUMBO: |
| /* action <- vararg/range */ |
| { |
| unsigned int idx; |
| for (idx = 0; idx < decInsn.vA; idx++) { |
| GEN(workBits, decInsn.vC + idx); |
| } |
| } |
| break; |
| |
| case OP_MOVE_RESULT: |
| case OP_MOVE_RESULT_WIDE: |
| case OP_MOVE_RESULT_OBJECT: |
| case OP_MOVE_EXCEPTION: |
| case OP_CONST_4: |
| case OP_CONST_16: |
| case OP_CONST: |
| case OP_CONST_HIGH16: |
| case OP_CONST_STRING: |
| case OP_CONST_STRING_JUMBO: |
| case OP_CONST_CLASS: |
| case OP_CONST_CLASS_JUMBO: |
| case OP_NEW_INSTANCE: |
| case OP_NEW_INSTANCE_JUMBO: |
| case OP_SGET: |
| case OP_SGET_VOLATILE: |
| case OP_SGET_JUMBO: |
| case OP_SGET_VOLATILE_JUMBO: |
| case OP_SGET_BOOLEAN: |
| case OP_SGET_BOOLEAN_JUMBO: |
| case OP_SGET_BYTE: |
| case OP_SGET_BYTE_JUMBO: |
| case OP_SGET_CHAR: |
| case OP_SGET_CHAR_JUMBO: |
| case OP_SGET_SHORT: |
| case OP_SGET_SHORT_JUMBO: |
| case OP_SGET_OBJECT: |
| case OP_SGET_OBJECT_VOLATILE: |
| case OP_SGET_OBJECT_JUMBO: |
| case OP_SGET_OBJECT_VOLATILE_JUMBO: |
| /* vA <- value */ |
| KILL(workBits, decInsn.vA); |
| break; |
| |
| case OP_CONST_WIDE_16: |
| case OP_CONST_WIDE_32: |
| case OP_CONST_WIDE: |
| case OP_CONST_WIDE_HIGH16: |
| case OP_SGET_WIDE: |
| case OP_SGET_WIDE_VOLATILE: |
| case OP_SGET_WIDE_JUMBO: |
| case OP_SGET_WIDE_VOLATILE_JUMBO: |
| /* vA(wide) <- value */ |
| KILLW(workBits, decInsn.vA); |
| break; |
| |
| case OP_MOVE: |
| case OP_MOVE_FROM16: |
| case OP_MOVE_16: |
| case OP_MOVE_OBJECT: |
| case OP_MOVE_OBJECT_FROM16: |
| case OP_MOVE_OBJECT_16: |
| case OP_INSTANCE_OF: |
| case OP_INSTANCE_OF_JUMBO: |
| case OP_ARRAY_LENGTH: |
| case OP_NEW_ARRAY: |
| case OP_NEW_ARRAY_JUMBO: |
| case OP_IGET: |
| case OP_IGET_VOLATILE: |
| case OP_IGET_JUMBO: |
| case OP_IGET_VOLATILE_JUMBO: |
| case OP_IGET_BOOLEAN: |
| case OP_IGET_BOOLEAN_JUMBO: |
| case OP_IGET_BYTE: |
| case OP_IGET_BYTE_JUMBO: |
| case OP_IGET_CHAR: |
| case OP_IGET_CHAR_JUMBO: |
| case OP_IGET_SHORT: |
| case OP_IGET_SHORT_JUMBO: |
| case OP_IGET_OBJECT: |
| case OP_IGET_OBJECT_VOLATILE: |
| case OP_IGET_OBJECT_JUMBO: |
| case OP_IGET_OBJECT_VOLATILE_JUMBO: |
| case OP_NEG_INT: |
| case OP_NOT_INT: |
| case OP_NEG_FLOAT: |
| case OP_INT_TO_FLOAT: |
| case OP_FLOAT_TO_INT: |
| case OP_INT_TO_BYTE: |
| case OP_INT_TO_CHAR: |
| case OP_INT_TO_SHORT: |
| case OP_ADD_INT_LIT16: |
| case OP_RSUB_INT: |
| case OP_MUL_INT_LIT16: |
| case OP_DIV_INT_LIT16: |
| case OP_REM_INT_LIT16: |
| case OP_AND_INT_LIT16: |
| case OP_OR_INT_LIT16: |
| case OP_XOR_INT_LIT16: |
| case OP_ADD_INT_LIT8: |
| case OP_RSUB_INT_LIT8: |
| case OP_MUL_INT_LIT8: |
| case OP_DIV_INT_LIT8: |
| case OP_REM_INT_LIT8: |
| case OP_SHL_INT_LIT8: |
| case OP_SHR_INT_LIT8: |
| case OP_USHR_INT_LIT8: |
| case OP_AND_INT_LIT8: |
| case OP_OR_INT_LIT8: |
| case OP_XOR_INT_LIT8: |
| /* vA <- vB */ |
| KILL(workBits, decInsn.vA); |
| GEN(workBits, decInsn.vB); |
| break; |
| |
| case OP_IGET_WIDE: |
| case OP_IGET_WIDE_VOLATILE: |
| case OP_IGET_WIDE_JUMBO: |
| case OP_IGET_WIDE_VOLATILE_JUMBO: |
| case OP_INT_TO_LONG: |
| case OP_INT_TO_DOUBLE: |
| case OP_FLOAT_TO_LONG: |
| case OP_FLOAT_TO_DOUBLE: |
| /* vA(wide) <- vB */ |
| KILLW(workBits, decInsn.vA); |
| GEN(workBits, decInsn.vB); |
| break; |
| |
| case OP_LONG_TO_INT: |
| case OP_LONG_TO_FLOAT: |
| case OP_DOUBLE_TO_INT: |
| case OP_DOUBLE_TO_FLOAT: |
| /* vA <- vB(wide) */ |
| KILL(workBits, decInsn.vA); |
| GENW(workBits, decInsn.vB); |
| break; |
| |
| case OP_MOVE_WIDE: |
| case OP_MOVE_WIDE_FROM16: |
| case OP_MOVE_WIDE_16: |
| case OP_NEG_LONG: |
| case OP_NOT_LONG: |
| case OP_NEG_DOUBLE: |
| case OP_LONG_TO_DOUBLE: |
| case OP_DOUBLE_TO_LONG: |
| /* vA(wide) <- vB(wide) */ |
| KILLW(workBits, decInsn.vA); |
| GENW(workBits, decInsn.vB); |
| break; |
| |
| case OP_CMPL_FLOAT: |
| case OP_CMPG_FLOAT: |
| case OP_AGET: |
| case OP_AGET_BOOLEAN: |
| case OP_AGET_BYTE: |
| case OP_AGET_CHAR: |
| case OP_AGET_SHORT: |
| case OP_AGET_OBJECT: |
| case OP_ADD_INT: |
| case OP_SUB_INT: |
| case OP_MUL_INT: |
| case OP_REM_INT: |
| case OP_DIV_INT: |
| case OP_AND_INT: |
| case OP_OR_INT: |
| case OP_XOR_INT: |
| case OP_SHL_INT: |
| case OP_SHR_INT: |
| case OP_USHR_INT: |
| case OP_ADD_FLOAT: |
| case OP_SUB_FLOAT: |
| case OP_MUL_FLOAT: |
| case OP_DIV_FLOAT: |
| case OP_REM_FLOAT: |
| /* vA <- vB, vC */ |
| KILL(workBits, decInsn.vA); |
| GEN(workBits, decInsn.vB); |
| GEN(workBits, decInsn.vC); |
| break; |
| |
| case OP_AGET_WIDE: |
| /* vA(wide) <- vB, vC */ |
| KILLW(workBits, decInsn.vA); |
| GEN(workBits, decInsn.vB); |
| GEN(workBits, decInsn.vC); |
| break; |
| |
| case OP_CMPL_DOUBLE: |
| case OP_CMPG_DOUBLE: |
| case OP_CMP_LONG: |
| /* vA <- vB(wide), vC(wide) */ |
| KILL(workBits, decInsn.vA); |
| GENW(workBits, decInsn.vB); |
| GENW(workBits, decInsn.vC); |
| break; |
| |
| case OP_SHL_LONG: |
| case OP_SHR_LONG: |
| case OP_USHR_LONG: |
| /* vA(wide) <- vB(wide), vC */ |
| KILLW(workBits, decInsn.vA); |
| GENW(workBits, decInsn.vB); |
| GEN(workBits, decInsn.vC); |
| break; |
| |
| case OP_ADD_LONG: |
| case OP_SUB_LONG: |
| case OP_MUL_LONG: |
| case OP_DIV_LONG: |
| case OP_REM_LONG: |
| case OP_AND_LONG: |
| case OP_OR_LONG: |
| case OP_XOR_LONG: |
| case OP_ADD_DOUBLE: |
| case OP_SUB_DOUBLE: |
| case OP_MUL_DOUBLE: |
| case OP_DIV_DOUBLE: |
| case OP_REM_DOUBLE: |
| /* vA(wide) <- vB(wide), vC(wide) */ |
| KILLW(workBits, decInsn.vA); |
| GENW(workBits, decInsn.vB); |
| GENW(workBits, decInsn.vC); |
| break; |
| |
| case OP_ADD_INT_2ADDR: |
| case OP_SUB_INT_2ADDR: |
| case OP_MUL_INT_2ADDR: |
| case OP_REM_INT_2ADDR: |
| case OP_SHL_INT_2ADDR: |
| case OP_SHR_INT_2ADDR: |
| case OP_USHR_INT_2ADDR: |
| case OP_AND_INT_2ADDR: |
| case OP_OR_INT_2ADDR: |
| case OP_XOR_INT_2ADDR: |
| case OP_DIV_INT_2ADDR: |
| /* vA <- vA, vB */ |
| /* KILL(workBits, decInsn.vA); */ |
| GEN(workBits, decInsn.vA); |
| GEN(workBits, decInsn.vB); |
| break; |
| |
| case OP_SHL_LONG_2ADDR: |
| case OP_SHR_LONG_2ADDR: |
| case OP_USHR_LONG_2ADDR: |
| /* vA(wide) <- vA(wide), vB */ |
| /* KILLW(workBits, decInsn.vA); */ |
| GENW(workBits, decInsn.vA); |
| GEN(workBits, decInsn.vB); |
| break; |
| |
| case OP_ADD_LONG_2ADDR: |
| case OP_SUB_LONG_2ADDR: |
| case OP_MUL_LONG_2ADDR: |
| case OP_DIV_LONG_2ADDR: |
| case OP_REM_LONG_2ADDR: |
| case OP_AND_LONG_2ADDR: |
| case OP_OR_LONG_2ADDR: |
| case OP_XOR_LONG_2ADDR: |
| case OP_ADD_FLOAT_2ADDR: |
| case OP_SUB_FLOAT_2ADDR: |
| case OP_MUL_FLOAT_2ADDR: |
| case OP_DIV_FLOAT_2ADDR: |
| case OP_REM_FLOAT_2ADDR: |
| case OP_ADD_DOUBLE_2ADDR: |
| case OP_SUB_DOUBLE_2ADDR: |
| case OP_MUL_DOUBLE_2ADDR: |
| case OP_DIV_DOUBLE_2ADDR: |
| case OP_REM_DOUBLE_2ADDR: |
| /* vA(wide) <- vA(wide), vB(wide) */ |
| /* KILLW(workBits, decInsn.vA); */ |
| GENW(workBits, decInsn.vA); |
| GENW(workBits, decInsn.vB); |
| break; |
| |
| /* we will only see this if liveness analysis is done after general vfy */ |
| case OP_THROW_VERIFICATION_ERROR: |
| case OP_THROW_VERIFICATION_ERROR_JUMBO: |
| /* no registers used */ |
| break; |
| |
| /* quickened instructions, not expected to appear */ |
| case OP_EXECUTE_INLINE: |
| case OP_EXECUTE_INLINE_RANGE: |
| case OP_INVOKE_OBJECT_INIT_RANGE: |
| case OP_INVOKE_OBJECT_INIT_JUMBO: |
| case OP_IGET_QUICK: |
| case OP_IGET_WIDE_QUICK: |
| case OP_IGET_OBJECT_QUICK: |
| case OP_IPUT_QUICK: |
| case OP_IPUT_WIDE_QUICK: |
| case OP_IPUT_OBJECT_QUICK: |
| case OP_INVOKE_VIRTUAL_QUICK: |
| case OP_INVOKE_VIRTUAL_QUICK_RANGE: |
| case OP_INVOKE_SUPER_QUICK: |
| case OP_INVOKE_SUPER_QUICK_RANGE: |
| case OP_RETURN_VOID_BARRIER: |
| return false; |
| |
| /* these should never appear during verification */ |
| case OP_UNUSED_3E: |
| case OP_UNUSED_3F: |
| case OP_UNUSED_40: |
| case OP_UNUSED_41: |
| case OP_UNUSED_42: |
| case OP_UNUSED_43: |
| case OP_UNUSED_73: |
| case OP_UNUSED_79: |
| case OP_UNUSED_7A: |
| case OP_BREAKPOINT: |
| case OP_DISPATCH_FF: |
| case OP_UNUSED_27FF: |
| case OP_UNUSED_28FF: |
| case OP_UNUSED_29FF: |
| case OP_UNUSED_2AFF: |
| case OP_UNUSED_2BFF: |
| case OP_UNUSED_2CFF: |
| case OP_UNUSED_2DFF: |
| case OP_UNUSED_2EFF: |
| case OP_UNUSED_2FFF: |
| case OP_UNUSED_30FF: |
| case OP_UNUSED_31FF: |
| case OP_UNUSED_32FF: |
| case OP_UNUSED_33FF: |
| case OP_UNUSED_34FF: |
| case OP_UNUSED_35FF: |
| case OP_UNUSED_36FF: |
| case OP_UNUSED_37FF: |
| case OP_UNUSED_38FF: |
| case OP_UNUSED_39FF: |
| case OP_UNUSED_3AFF: |
| case OP_UNUSED_3BFF: |
| case OP_UNUSED_3CFF: |
| case OP_UNUSED_3DFF: |
| case OP_UNUSED_3EFF: |
| case OP_UNUSED_3FFF: |
| case OP_UNUSED_40FF: |
| case OP_UNUSED_41FF: |
| case OP_UNUSED_42FF: |
| case OP_UNUSED_43FF: |
| case OP_UNUSED_44FF: |
| case OP_UNUSED_45FF: |
| case OP_UNUSED_46FF: |
| case OP_UNUSED_47FF: |
| case OP_UNUSED_48FF: |
| case OP_UNUSED_49FF: |
| case OP_UNUSED_4AFF: |
| case OP_UNUSED_4BFF: |
| case OP_UNUSED_4CFF: |
| case OP_UNUSED_4DFF: |
| case OP_UNUSED_4EFF: |
| case OP_UNUSED_4FFF: |
| case OP_UNUSED_50FF: |
| case OP_UNUSED_51FF: |
| case OP_UNUSED_52FF: |
| case OP_UNUSED_53FF: |
| case OP_UNUSED_54FF: |
| case OP_UNUSED_55FF: |
| case OP_UNUSED_56FF: |
| case OP_UNUSED_57FF: |
| case OP_UNUSED_58FF: |
| case OP_UNUSED_59FF: |
| case OP_UNUSED_5AFF: |
| case OP_UNUSED_5BFF: |
| case OP_UNUSED_5CFF: |
| case OP_UNUSED_5DFF: |
| case OP_UNUSED_5EFF: |
| case OP_UNUSED_5FFF: |
| case OP_UNUSED_60FF: |
| case OP_UNUSED_61FF: |
| case OP_UNUSED_62FF: |
| case OP_UNUSED_63FF: |
| case OP_UNUSED_64FF: |
| case OP_UNUSED_65FF: |
| case OP_UNUSED_66FF: |
| case OP_UNUSED_67FF: |
| case OP_UNUSED_68FF: |
| case OP_UNUSED_69FF: |
| case OP_UNUSED_6AFF: |
| case OP_UNUSED_6BFF: |
| case OP_UNUSED_6CFF: |
| case OP_UNUSED_6DFF: |
| case OP_UNUSED_6EFF: |
| case OP_UNUSED_6FFF: |
| case OP_UNUSED_70FF: |
| case OP_UNUSED_71FF: |
| case OP_UNUSED_72FF: |
| case OP_UNUSED_73FF: |
| case OP_UNUSED_74FF: |
| case OP_UNUSED_75FF: |
| case OP_UNUSED_76FF: |
| case OP_UNUSED_77FF: |
| case OP_UNUSED_78FF: |
| case OP_UNUSED_79FF: |
| case OP_UNUSED_7AFF: |
| case OP_UNUSED_7BFF: |
| case OP_UNUSED_7CFF: |
| case OP_UNUSED_7DFF: |
| case OP_UNUSED_7EFF: |
| case OP_UNUSED_7FFF: |
| case OP_UNUSED_80FF: |
| case OP_UNUSED_81FF: |
| case OP_UNUSED_82FF: |
| case OP_UNUSED_83FF: |
| case OP_UNUSED_84FF: |
| case OP_UNUSED_85FF: |
| case OP_UNUSED_86FF: |
| case OP_UNUSED_87FF: |
| case OP_UNUSED_88FF: |
| case OP_UNUSED_89FF: |
| case OP_UNUSED_8AFF: |
| case OP_UNUSED_8BFF: |
| case OP_UNUSED_8CFF: |
| case OP_UNUSED_8DFF: |
| case OP_UNUSED_8EFF: |
| case OP_UNUSED_8FFF: |
| case OP_UNUSED_90FF: |
| case OP_UNUSED_91FF: |
| case OP_UNUSED_92FF: |
| case OP_UNUSED_93FF: |
| case OP_UNUSED_94FF: |
| case OP_UNUSED_95FF: |
| case OP_UNUSED_96FF: |
| case OP_UNUSED_97FF: |
| case OP_UNUSED_98FF: |
| case OP_UNUSED_99FF: |
| case OP_UNUSED_9AFF: |
| case OP_UNUSED_9BFF: |
| case OP_UNUSED_9CFF: |
| case OP_UNUSED_9DFF: |
| case OP_UNUSED_9EFF: |
| case OP_UNUSED_9FFF: |
| case OP_UNUSED_A0FF: |
| case OP_UNUSED_A1FF: |
| case OP_UNUSED_A2FF: |
| case OP_UNUSED_A3FF: |
| case OP_UNUSED_A4FF: |
| case OP_UNUSED_A5FF: |
| case OP_UNUSED_A6FF: |
| case OP_UNUSED_A7FF: |
| case OP_UNUSED_A8FF: |
| case OP_UNUSED_A9FF: |
| case OP_UNUSED_AAFF: |
| case OP_UNUSED_ABFF: |
| case OP_UNUSED_ACFF: |
| case OP_UNUSED_ADFF: |
| case OP_UNUSED_AEFF: |
| case OP_UNUSED_AFFF: |
| case OP_UNUSED_B0FF: |
| case OP_UNUSED_B1FF: |
| case OP_UNUSED_B2FF: |
| case OP_UNUSED_B3FF: |
| case OP_UNUSED_B4FF: |
| case OP_UNUSED_B5FF: |
| case OP_UNUSED_B6FF: |
| case OP_UNUSED_B7FF: |
| case OP_UNUSED_B8FF: |
| case OP_UNUSED_B9FF: |
| case OP_UNUSED_BAFF: |
| case OP_UNUSED_BBFF: |
| case OP_UNUSED_BCFF: |
| case OP_UNUSED_BDFF: |
| case OP_UNUSED_BEFF: |
| case OP_UNUSED_BFFF: |
| case OP_UNUSED_C0FF: |
| case OP_UNUSED_C1FF: |
| case OP_UNUSED_C2FF: |
| case OP_UNUSED_C3FF: |
| case OP_UNUSED_C4FF: |
| case OP_UNUSED_C5FF: |
| case OP_UNUSED_C6FF: |
| case OP_UNUSED_C7FF: |
| case OP_UNUSED_C8FF: |
| case OP_UNUSED_C9FF: |
| case OP_UNUSED_CAFF: |
| case OP_UNUSED_CBFF: |
| case OP_UNUSED_CCFF: |
| case OP_UNUSED_CDFF: |
| case OP_UNUSED_CEFF: |
| case OP_UNUSED_CFFF: |
| case OP_UNUSED_D0FF: |
| case OP_UNUSED_D1FF: |
| case OP_UNUSED_D2FF: |
| case OP_UNUSED_D3FF: |
| case OP_UNUSED_D4FF: |
| case OP_UNUSED_D5FF: |
| case OP_UNUSED_D6FF: |
| case OP_UNUSED_D7FF: |
| case OP_UNUSED_D8FF: |
| case OP_UNUSED_D9FF: |
| case OP_UNUSED_DAFF: |
| case OP_UNUSED_DBFF: |
| case OP_UNUSED_DCFF: |
| case OP_UNUSED_DDFF: |
| case OP_UNUSED_DEFF: |
| case OP_UNUSED_DFFF: |
| case OP_UNUSED_E0FF: |
| case OP_UNUSED_E1FF: |
| case OP_UNUSED_E2FF: |
| case OP_UNUSED_E3FF: |
| case OP_UNUSED_E4FF: |
| case OP_UNUSED_E5FF: |
| case OP_UNUSED_E6FF: |
| case OP_UNUSED_E7FF: |
| case OP_UNUSED_E8FF: |
| case OP_UNUSED_E9FF: |
| case OP_UNUSED_EAFF: |
| case OP_UNUSED_EBFF: |
| case OP_UNUSED_ECFF: |
| case OP_UNUSED_EDFF: |
| case OP_UNUSED_EEFF: |
| case OP_UNUSED_EFFF: |
| case OP_UNUSED_F0FF: |
| case OP_UNUSED_F1FF: |
| return false; |
| } |
| |
| return true; |
| } |
| |
| /* |
| * This is a dexDecodeDebugInfo callback, used by markDebugLocals(). |
| */ |
| static void markLocalsCb(void* ctxt, u2 reg, u4 startAddress, u4 endAddress, |
| const char* name, const char* descriptor, const char* signature) |
| { |
| VerifierData* vdata = (VerifierData*) ctxt; |
| bool verbose = dvmWantVerboseVerification(vdata->method); |
| |
| if (verbose) { |
| LOGI("%04x-%04x %2d (%s %s)\n", |
| startAddress, endAddress, reg, name, descriptor); |
| } |
| |
| bool wide = (descriptor[0] == 'D' || descriptor[0] == 'J'); |
| assert(reg <= vdata->insnRegCount + (wide ? 1 : 0)); |
| |
| /* |
| * Set the bit in all GC point instructions in the range |
| * [startAddress, endAddress). |
| */ |
| unsigned int idx; |
| for (idx = startAddress; idx < endAddress; idx++) { |
| BitVector* liveRegs = vdata->registerLines[idx].liveRegs; |
| if (liveRegs != NULL) { |
| if (wide) { |
| GENW(liveRegs, reg); |
| } else { |
| GEN(liveRegs, reg); |
| } |
| } |
| } |
| } |
| |
| /* |
| * Mark all debugger-visible locals as live. |
| * |
| * The "locals" table describes the positions of the various locals in the |
| * stack frame based on the current execution address. If the debugger |
| * wants to display one, it issues a request by "slot number". We need |
| * to ensure that references in stack slots that might be queried by the |
| * debugger aren't GCed. |
| * |
| * (If the GC had some way to mark the slot as invalid we wouldn't have |
| * to do this. We could also have the debugger interface check the |
| * register map and simply refuse to return a "dead" value, but that's |
| * potentially confusing since the referred-to object might actually be |
| * alive, and being able to see it without having to hunt around for a |
| * "live" stack frame is useful.) |
| */ |
| static bool markDebugLocals(VerifierData* vdata) |
| { |
| const Method* meth = vdata->method; |
| |
| dexDecodeDebugInfo(meth->clazz->pDvmDex->pDexFile, dvmGetMethodCode(meth), |
| meth->clazz->descriptor, meth->prototype.protoIdx, meth->accessFlags, |
| NULL, markLocalsCb, vdata); |
| |
| return true; |
| } |
| |
| |
| /* |
| * Dump the liveness bits to the log. |
| * |
| * "curIdx" is for display only. |
| */ |
| static void dumpLiveState(const VerifierData* vdata, u4 curIdx, |
| const BitVector* workBits) |
| { |
| u4 insnRegCount = vdata->insnRegCount; |
| size_t regCharSize = insnRegCount + (insnRegCount-1)/4 + 2 +1; |
| char regChars[regCharSize +1]; |
| unsigned int idx; |
| |
| memset(regChars, ' ', regCharSize); |
| regChars[0] = '['; |
| if (insnRegCount == 0) |
| regChars[1] = ']'; |
| else |
| regChars[1 + (insnRegCount-1) + (insnRegCount-1)/4 +1] = ']'; |
| regChars[regCharSize] = '\0'; |
| |
| for (idx = 0; idx < insnRegCount; idx++) { |
| char ch = dvmIsBitSet(workBits, idx) ? '+' : '-'; |
| regChars[1 + idx + (idx/4)] = ch; |
| } |
| |
| LOGI("0x%04x %s\n", curIdx, regChars); |
| } |
