Liveness.cpp revision 6f3c21fb026d9489e5046416bcd5a84fa8e4615b
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 24static bool processInstruction(VerifierData* vdata, u4 curIdx, 25 BitVector* workBits); 26static bool markDebugLocals(VerifierData* vdata); 27static 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 */ 38static 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 */ 60bool 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 LOGI("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 LOGI("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 LOGI("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 274bail: 275 free(backwardWidth); 276 return result; 277} 278 279 280/* 281 * Add a register to the LIVE set. 282 */ 283static 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 */ 291static 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 */ 300static 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 */ 308static 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 */ 319static 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_CHECK_CAST_JUMBO: 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_JUMBO: 360 case OP_SPUT_BOOLEAN: 361 case OP_SPUT_BOOLEAN_JUMBO: 362 case OP_SPUT_BYTE: 363 case OP_SPUT_BYTE_JUMBO: 364 case OP_SPUT_CHAR: 365 case OP_SPUT_CHAR_JUMBO: 366 case OP_SPUT_SHORT: 367 case OP_SPUT_SHORT_JUMBO: 368 case OP_SPUT_OBJECT: 369 case OP_SPUT_OBJECT_JUMBO: 370 /* action <- vA */ 371 GEN(workBits, decInsn.vA); 372 break; 373 374 case OP_RETURN_WIDE: 375 case OP_SPUT_WIDE: 376 case OP_SPUT_WIDE_JUMBO: 377 /* action <- vA(wide) */ 378 GENW(workBits, decInsn.vA); 379 break; 380 381 case OP_IF_EQ: 382 case OP_IF_NE: 383 case OP_IF_LT: 384 case OP_IF_GE: 385 case OP_IF_GT: 386 case OP_IF_LE: 387 case OP_IPUT: 388 case OP_IPUT_JUMBO: 389 case OP_IPUT_BOOLEAN: 390 case OP_IPUT_BOOLEAN_JUMBO: 391 case OP_IPUT_BYTE: 392 case OP_IPUT_BYTE_JUMBO: 393 case OP_IPUT_CHAR: 394 case OP_IPUT_CHAR_JUMBO: 395 case OP_IPUT_SHORT: 396 case OP_IPUT_SHORT_JUMBO: 397 case OP_IPUT_OBJECT: 398 case OP_IPUT_OBJECT_JUMBO: 399 /* action <- vA, vB */ 400 GEN(workBits, decInsn.vA); 401 GEN(workBits, decInsn.vB); 402 break; 403 404 case OP_IPUT_WIDE: 405 case OP_IPUT_WIDE_JUMBO: 406 /* action <- vA(wide), vB */ 407 GENW(workBits, decInsn.vA); 408 GEN(workBits, decInsn.vB); 409 break; 410 411 case OP_APUT: 412 case OP_APUT_BOOLEAN: 413 case OP_APUT_BYTE: 414 case OP_APUT_CHAR: 415 case OP_APUT_SHORT: 416 case OP_APUT_OBJECT: 417 /* action <- vA, vB, vC */ 418 GEN(workBits, decInsn.vA); 419 GEN(workBits, decInsn.vB); 420 GEN(workBits, decInsn.vC); 421 break; 422 423 case OP_APUT_WIDE: 424 /* action <- vA(wide), vB, vC */ 425 GENW(workBits, decInsn.vA); 426 GEN(workBits, decInsn.vB); 427 GEN(workBits, decInsn.vC); 428 break; 429 430 case OP_FILLED_NEW_ARRAY: 431 case OP_INVOKE_VIRTUAL: 432 case OP_INVOKE_SUPER: 433 case OP_INVOKE_DIRECT: 434 case OP_INVOKE_STATIC: 435 case OP_INVOKE_INTERFACE: 436 /* action <- vararg */ 437 { 438 unsigned int idx; 439 for (idx = 0; idx < decInsn.vA; idx++) { 440 GEN(workBits, decInsn.arg[idx]); 441 } 442 } 443 break; 444 445 case OP_FILLED_NEW_ARRAY_RANGE: 446 case OP_FILLED_NEW_ARRAY_JUMBO: 447 case OP_INVOKE_VIRTUAL_RANGE: 448 case OP_INVOKE_VIRTUAL_JUMBO: 449 case OP_INVOKE_SUPER_RANGE: 450 case OP_INVOKE_SUPER_JUMBO: 451 case OP_INVOKE_DIRECT_RANGE: 452 case OP_INVOKE_DIRECT_JUMBO: 453 case OP_INVOKE_STATIC_RANGE: 454 case OP_INVOKE_STATIC_JUMBO: 455 case OP_INVOKE_INTERFACE_RANGE: 456 case OP_INVOKE_INTERFACE_JUMBO: 457 /* action <- vararg/range */ 458 { 459 unsigned int idx; 460 for (idx = 0; idx < decInsn.vA; idx++) { 461 GEN(workBits, decInsn.vC + idx); 462 } 463 } 464 break; 465 466 case OP_MOVE_RESULT: 467 case OP_MOVE_RESULT_WIDE: 468 case OP_MOVE_RESULT_OBJECT: 469 case OP_MOVE_EXCEPTION: 470 case OP_CONST_4: 471 case OP_CONST_16: 472 case OP_CONST: 473 case OP_CONST_HIGH16: 474 case OP_CONST_STRING: 475 case OP_CONST_STRING_JUMBO: 476 case OP_CONST_CLASS: 477 case OP_CONST_CLASS_JUMBO: 478 case OP_NEW_INSTANCE: 479 case OP_NEW_INSTANCE_JUMBO: 480 case OP_SGET: 481 case OP_SGET_JUMBO: 482 case OP_SGET_BOOLEAN: 483 case OP_SGET_BOOLEAN_JUMBO: 484 case OP_SGET_BYTE: 485 case OP_SGET_BYTE_JUMBO: 486 case OP_SGET_CHAR: 487 case OP_SGET_CHAR_JUMBO: 488 case OP_SGET_SHORT: 489 case OP_SGET_SHORT_JUMBO: 490 case OP_SGET_OBJECT: 491 case OP_SGET_OBJECT_JUMBO: 492 /* vA <- value */ 493 KILL(workBits, decInsn.vA); 494 break; 495 496 case OP_CONST_WIDE_16: 497 case OP_CONST_WIDE_32: 498 case OP_CONST_WIDE: 499 case OP_CONST_WIDE_HIGH16: 500 case OP_SGET_WIDE: 501 case OP_SGET_WIDE_JUMBO: 502 /* vA(wide) <- value */ 503 KILLW(workBits, decInsn.vA); 504 break; 505 506 case OP_MOVE: 507 case OP_MOVE_FROM16: 508 case OP_MOVE_16: 509 case OP_MOVE_OBJECT: 510 case OP_MOVE_OBJECT_FROM16: 511 case OP_MOVE_OBJECT_16: 512 case OP_INSTANCE_OF: 513 case OP_INSTANCE_OF_JUMBO: 514 case OP_ARRAY_LENGTH: 515 case OP_NEW_ARRAY: 516 case OP_NEW_ARRAY_JUMBO: 517 case OP_IGET: 518 case OP_IGET_JUMBO: 519 case OP_IGET_BOOLEAN: 520 case OP_IGET_BOOLEAN_JUMBO: 521 case OP_IGET_BYTE: 522 case OP_IGET_BYTE_JUMBO: 523 case OP_IGET_CHAR: 524 case OP_IGET_CHAR_JUMBO: 525 case OP_IGET_SHORT: 526 case OP_IGET_SHORT_JUMBO: 527 case OP_IGET_OBJECT: 528 case OP_IGET_OBJECT_JUMBO: 529 case OP_NEG_INT: 530 case OP_NOT_INT: 531 case OP_NEG_FLOAT: 532 case OP_INT_TO_FLOAT: 533 case OP_FLOAT_TO_INT: 534 case OP_INT_TO_BYTE: 535 case OP_INT_TO_CHAR: 536 case OP_INT_TO_SHORT: 537 case OP_ADD_INT_LIT16: 538 case OP_RSUB_INT: 539 case OP_MUL_INT_LIT16: 540 case OP_DIV_INT_LIT16: 541 case OP_REM_INT_LIT16: 542 case OP_AND_INT_LIT16: 543 case OP_OR_INT_LIT16: 544 case OP_XOR_INT_LIT16: 545 case OP_ADD_INT_LIT8: 546 case OP_RSUB_INT_LIT8: 547 case OP_MUL_INT_LIT8: 548 case OP_DIV_INT_LIT8: 549 case OP_REM_INT_LIT8: 550 case OP_SHL_INT_LIT8: 551 case OP_SHR_INT_LIT8: 552 case OP_USHR_INT_LIT8: 553 case OP_AND_INT_LIT8: 554 case OP_OR_INT_LIT8: 555 case OP_XOR_INT_LIT8: 556 /* vA <- vB */ 557 KILL(workBits, decInsn.vA); 558 GEN(workBits, decInsn.vB); 559 break; 560 561 case OP_IGET_WIDE: 562 case OP_IGET_WIDE_JUMBO: 563 case OP_INT_TO_LONG: 564 case OP_INT_TO_DOUBLE: 565 case OP_FLOAT_TO_LONG: 566 case OP_FLOAT_TO_DOUBLE: 567 /* vA(wide) <- vB */ 568 KILLW(workBits, decInsn.vA); 569 GEN(workBits, decInsn.vB); 570 break; 571 572 case OP_LONG_TO_INT: 573 case OP_LONG_TO_FLOAT: 574 case OP_DOUBLE_TO_INT: 575 case OP_DOUBLE_TO_FLOAT: 576 /* vA <- vB(wide) */ 577 KILL(workBits, decInsn.vA); 578 GENW(workBits, decInsn.vB); 579 break; 580 581 case OP_MOVE_WIDE: 582 case OP_MOVE_WIDE_FROM16: 583 case OP_MOVE_WIDE_16: 584 case OP_NEG_LONG: 585 case OP_NOT_LONG: 586 case OP_NEG_DOUBLE: 587 case OP_LONG_TO_DOUBLE: 588 case OP_DOUBLE_TO_LONG: 589 /* vA(wide) <- vB(wide) */ 590 KILLW(workBits, decInsn.vA); 591 GENW(workBits, decInsn.vB); 592 break; 593 594 case OP_CMPL_FLOAT: 595 case OP_CMPG_FLOAT: 596 case OP_AGET: 597 case OP_AGET_BOOLEAN: 598 case OP_AGET_BYTE: 599 case OP_AGET_CHAR: 600 case OP_AGET_SHORT: 601 case OP_AGET_OBJECT: 602 case OP_ADD_INT: 603 case OP_SUB_INT: 604 case OP_MUL_INT: 605 case OP_REM_INT: 606 case OP_DIV_INT: 607 case OP_AND_INT: 608 case OP_OR_INT: 609 case OP_XOR_INT: 610 case OP_SHL_INT: 611 case OP_SHR_INT: 612 case OP_USHR_INT: 613 case OP_ADD_FLOAT: 614 case OP_SUB_FLOAT: 615 case OP_MUL_FLOAT: 616 case OP_DIV_FLOAT: 617 case OP_REM_FLOAT: 618 /* vA <- vB, vC */ 619 KILL(workBits, decInsn.vA); 620 GEN(workBits, decInsn.vB); 621 GEN(workBits, decInsn.vC); 622 break; 623 624 case OP_AGET_WIDE: 625 /* vA(wide) <- vB, vC */ 626 KILLW(workBits, decInsn.vA); 627 GEN(workBits, decInsn.vB); 628 GEN(workBits, decInsn.vC); 629 break; 630 631 case OP_CMPL_DOUBLE: 632 case OP_CMPG_DOUBLE: 633 case OP_CMP_LONG: 634 /* vA <- vB(wide), vC(wide) */ 635 KILL(workBits, decInsn.vA); 636 GENW(workBits, decInsn.vB); 637 GENW(workBits, decInsn.vC); 638 break; 639 640 case OP_SHL_LONG: 641 case OP_SHR_LONG: 642 case OP_USHR_LONG: 643 /* vA(wide) <- vB(wide), vC */ 644 KILLW(workBits, decInsn.vA); 645 GENW(workBits, decInsn.vB); 646 GEN(workBits, decInsn.vC); 647 break; 648 649 case OP_ADD_LONG: 650 case OP_SUB_LONG: 651 case OP_MUL_LONG: 652 case OP_DIV_LONG: 653 case OP_REM_LONG: 654 case OP_AND_LONG: 655 case OP_OR_LONG: 656 case OP_XOR_LONG: 657 case OP_ADD_DOUBLE: 658 case OP_SUB_DOUBLE: 659 case OP_MUL_DOUBLE: 660 case OP_DIV_DOUBLE: 661 case OP_REM_DOUBLE: 662 /* vA(wide) <- vB(wide), vC(wide) */ 663 KILLW(workBits, decInsn.vA); 664 GENW(workBits, decInsn.vB); 665 GENW(workBits, decInsn.vC); 666 break; 667 668 case OP_ADD_INT_2ADDR: 669 case OP_SUB_INT_2ADDR: 670 case OP_MUL_INT_2ADDR: 671 case OP_REM_INT_2ADDR: 672 case OP_SHL_INT_2ADDR: 673 case OP_SHR_INT_2ADDR: 674 case OP_USHR_INT_2ADDR: 675 case OP_AND_INT_2ADDR: 676 case OP_OR_INT_2ADDR: 677 case OP_XOR_INT_2ADDR: 678 case OP_DIV_INT_2ADDR: 679 /* vA <- vA, vB */ 680 /* KILL(workBits, decInsn.vA); */ 681 GEN(workBits, decInsn.vA); 682 GEN(workBits, decInsn.vB); 683 break; 684 685 case OP_SHL_LONG_2ADDR: 686 case OP_SHR_LONG_2ADDR: 687 case OP_USHR_LONG_2ADDR: 688 /* vA(wide) <- vA(wide), vB */ 689 /* KILLW(workBits, decInsn.vA); */ 690 GENW(workBits, decInsn.vA); 691 GEN(workBits, decInsn.vB); 692 break; 693 694 case OP_ADD_LONG_2ADDR: 695 case OP_SUB_LONG_2ADDR: 696 case OP_MUL_LONG_2ADDR: 697 case OP_DIV_LONG_2ADDR: 698 case OP_REM_LONG_2ADDR: 699 case OP_AND_LONG_2ADDR: 700 case OP_OR_LONG_2ADDR: 701 case OP_XOR_LONG_2ADDR: 702 case OP_ADD_FLOAT_2ADDR: 703 case OP_SUB_FLOAT_2ADDR: 704 case OP_MUL_FLOAT_2ADDR: 705 case OP_DIV_FLOAT_2ADDR: 706 case OP_REM_FLOAT_2ADDR: 707 case OP_ADD_DOUBLE_2ADDR: 708 case OP_SUB_DOUBLE_2ADDR: 709 case OP_MUL_DOUBLE_2ADDR: 710 case OP_DIV_DOUBLE_2ADDR: 711 case OP_REM_DOUBLE_2ADDR: 712 /* vA(wide) <- vA(wide), vB(wide) */ 713 /* KILLW(workBits, decInsn.vA); */ 714 GENW(workBits, decInsn.vA); 715 GENW(workBits, decInsn.vB); 716 break; 717 718 /* we will only see this if liveness analysis is done after general vfy */ 719 case OP_THROW_VERIFICATION_ERROR: 720 case OP_THROW_VERIFICATION_ERROR_JUMBO: 721 /* no registers used */ 722 break; 723 724 /* quickened instructions, not expected to appear */ 725 case OP_EXECUTE_INLINE: 726 case OP_EXECUTE_INLINE_RANGE: 727 case OP_IGET_QUICK: 728 case OP_IGET_WIDE_QUICK: 729 case OP_IGET_OBJECT_QUICK: 730 case OP_IPUT_QUICK: 731 case OP_IPUT_WIDE_QUICK: 732 case OP_IPUT_OBJECT_QUICK: 733 case OP_INVOKE_VIRTUAL_QUICK: 734 case OP_INVOKE_VIRTUAL_QUICK_RANGE: 735 case OP_INVOKE_SUPER_QUICK: 736 case OP_INVOKE_SUPER_QUICK_RANGE: 737 /* fall through to failure */ 738 739 /* correctness fixes, not expected to appear */ 740 case OP_INVOKE_OBJECT_INIT_RANGE: 741 case OP_INVOKE_OBJECT_INIT_JUMBO: 742 case OP_RETURN_VOID_BARRIER: 743 case OP_SPUT_VOLATILE: 744 case OP_SPUT_VOLATILE_JUMBO: 745 case OP_SPUT_OBJECT_VOLATILE: 746 case OP_SPUT_OBJECT_VOLATILE_JUMBO: 747 case OP_SPUT_WIDE_VOLATILE: 748 case OP_SPUT_WIDE_VOLATILE_JUMBO: 749 case OP_IPUT_VOLATILE: 750 case OP_IPUT_VOLATILE_JUMBO: 751 case OP_IPUT_OBJECT_VOLATILE: 752 case OP_IPUT_OBJECT_VOLATILE_JUMBO: 753 case OP_IPUT_WIDE_VOLATILE: 754 case OP_IPUT_WIDE_VOLATILE_JUMBO: 755 case OP_SGET_VOLATILE: 756 case OP_SGET_VOLATILE_JUMBO: 757 case OP_SGET_OBJECT_VOLATILE: 758 case OP_SGET_OBJECT_VOLATILE_JUMBO: 759 case OP_SGET_WIDE_VOLATILE: 760 case OP_SGET_WIDE_VOLATILE_JUMBO: 761 case OP_IGET_VOLATILE: 762 case OP_IGET_VOLATILE_JUMBO: 763 case OP_IGET_OBJECT_VOLATILE: 764 case OP_IGET_OBJECT_VOLATILE_JUMBO: 765 case OP_IGET_WIDE_VOLATILE: 766 case OP_IGET_WIDE_VOLATILE_JUMBO: 767 /* fall through to failure */ 768 769 /* these should never appear during verification */ 770 case OP_UNUSED_3E: 771 case OP_UNUSED_3F: 772 case OP_UNUSED_40: 773 case OP_UNUSED_41: 774 case OP_UNUSED_42: 775 case OP_UNUSED_43: 776 case OP_UNUSED_73: 777 case OP_UNUSED_79: 778 case OP_UNUSED_7A: 779 case OP_BREAKPOINT: 780 case OP_DISPATCH_FF: 781 case OP_UNUSED_27FF: 782 case OP_UNUSED_28FF: 783 case OP_UNUSED_29FF: 784 case OP_UNUSED_2AFF: 785 case OP_UNUSED_2BFF: 786 case OP_UNUSED_2CFF: 787 case OP_UNUSED_2DFF: 788 case OP_UNUSED_2EFF: 789 case OP_UNUSED_2FFF: 790 case OP_UNUSED_30FF: 791 case OP_UNUSED_31FF: 792 case OP_UNUSED_32FF: 793 case OP_UNUSED_33FF: 794 case OP_UNUSED_34FF: 795 case OP_UNUSED_35FF: 796 case OP_UNUSED_36FF: 797 case OP_UNUSED_37FF: 798 case OP_UNUSED_38FF: 799 case OP_UNUSED_39FF: 800 case OP_UNUSED_3AFF: 801 case OP_UNUSED_3BFF: 802 case OP_UNUSED_3CFF: 803 case OP_UNUSED_3DFF: 804 case OP_UNUSED_3EFF: 805 case OP_UNUSED_3FFF: 806 case OP_UNUSED_40FF: 807 case OP_UNUSED_41FF: 808 case OP_UNUSED_42FF: 809 case OP_UNUSED_43FF: 810 case OP_UNUSED_44FF: 811 case OP_UNUSED_45FF: 812 case OP_UNUSED_46FF: 813 case OP_UNUSED_47FF: 814 case OP_UNUSED_48FF: 815 case OP_UNUSED_49FF: 816 case OP_UNUSED_4AFF: 817 case OP_UNUSED_4BFF: 818 case OP_UNUSED_4CFF: 819 case OP_UNUSED_4DFF: 820 case OP_UNUSED_4EFF: 821 case OP_UNUSED_4FFF: 822 case OP_UNUSED_50FF: 823 case OP_UNUSED_51FF: 824 case OP_UNUSED_52FF: 825 case OP_UNUSED_53FF: 826 case OP_UNUSED_54FF: 827 case OP_UNUSED_55FF: 828 case OP_UNUSED_56FF: 829 case OP_UNUSED_57FF: 830 case OP_UNUSED_58FF: 831 case OP_UNUSED_59FF: 832 case OP_UNUSED_5AFF: 833 case OP_UNUSED_5BFF: 834 case OP_UNUSED_5CFF: 835 case OP_UNUSED_5DFF: 836 case OP_UNUSED_5EFF: 837 case OP_UNUSED_5FFF: 838 case OP_UNUSED_60FF: 839 case OP_UNUSED_61FF: 840 case OP_UNUSED_62FF: 841 case OP_UNUSED_63FF: 842 case OP_UNUSED_64FF: 843 case OP_UNUSED_65FF: 844 case OP_UNUSED_66FF: 845 case OP_UNUSED_67FF: 846 case OP_UNUSED_68FF: 847 case OP_UNUSED_69FF: 848 case OP_UNUSED_6AFF: 849 case OP_UNUSED_6BFF: 850 case OP_UNUSED_6CFF: 851 case OP_UNUSED_6DFF: 852 case OP_UNUSED_6EFF: 853 case OP_UNUSED_6FFF: 854 case OP_UNUSED_70FF: 855 case OP_UNUSED_71FF: 856 case OP_UNUSED_72FF: 857 case OP_UNUSED_73FF: 858 case OP_UNUSED_74FF: 859 case OP_UNUSED_75FF: 860 case OP_UNUSED_76FF: 861 case OP_UNUSED_77FF: 862 case OP_UNUSED_78FF: 863 case OP_UNUSED_79FF: 864 case OP_UNUSED_7AFF: 865 case OP_UNUSED_7BFF: 866 case OP_UNUSED_7CFF: 867 case OP_UNUSED_7DFF: 868 case OP_UNUSED_7EFF: 869 case OP_UNUSED_7FFF: 870 case OP_UNUSED_80FF: 871 case OP_UNUSED_81FF: 872 case OP_UNUSED_82FF: 873 case OP_UNUSED_83FF: 874 case OP_UNUSED_84FF: 875 case OP_UNUSED_85FF: 876 case OP_UNUSED_86FF: 877 case OP_UNUSED_87FF: 878 case OP_UNUSED_88FF: 879 case OP_UNUSED_89FF: 880 case OP_UNUSED_8AFF: 881 case OP_UNUSED_8BFF: 882 case OP_UNUSED_8CFF: 883 case OP_UNUSED_8DFF: 884 case OP_UNUSED_8EFF: 885 case OP_UNUSED_8FFF: 886 case OP_UNUSED_90FF: 887 case OP_UNUSED_91FF: 888 case OP_UNUSED_92FF: 889 case OP_UNUSED_93FF: 890 case OP_UNUSED_94FF: 891 case OP_UNUSED_95FF: 892 case OP_UNUSED_96FF: 893 case OP_UNUSED_97FF: 894 case OP_UNUSED_98FF: 895 case OP_UNUSED_99FF: 896 case OP_UNUSED_9AFF: 897 case OP_UNUSED_9BFF: 898 case OP_UNUSED_9CFF: 899 case OP_UNUSED_9DFF: 900 case OP_UNUSED_9EFF: 901 case OP_UNUSED_9FFF: 902 case OP_UNUSED_A0FF: 903 case OP_UNUSED_A1FF: 904 case OP_UNUSED_A2FF: 905 case OP_UNUSED_A3FF: 906 case OP_UNUSED_A4FF: 907 case OP_UNUSED_A5FF: 908 case OP_UNUSED_A6FF: 909 case OP_UNUSED_A7FF: 910 case OP_UNUSED_A8FF: 911 case OP_UNUSED_A9FF: 912 case OP_UNUSED_AAFF: 913 case OP_UNUSED_ABFF: 914 case OP_UNUSED_ACFF: 915 case OP_UNUSED_ADFF: 916 case OP_UNUSED_AEFF: 917 case OP_UNUSED_AFFF: 918 case OP_UNUSED_B0FF: 919 case OP_UNUSED_B1FF: 920 case OP_UNUSED_B2FF: 921 case OP_UNUSED_B3FF: 922 case OP_UNUSED_B4FF: 923 case OP_UNUSED_B5FF: 924 case OP_UNUSED_B6FF: 925 case OP_UNUSED_B7FF: 926 case OP_UNUSED_B8FF: 927 case OP_UNUSED_B9FF: 928 case OP_UNUSED_BAFF: 929 case OP_UNUSED_BBFF: 930 case OP_UNUSED_BCFF: 931 case OP_UNUSED_BDFF: 932 case OP_UNUSED_BEFF: 933 case OP_UNUSED_BFFF: 934 case OP_UNUSED_C0FF: 935 case OP_UNUSED_C1FF: 936 case OP_UNUSED_C2FF: 937 case OP_UNUSED_C3FF: 938 case OP_UNUSED_C4FF: 939 case OP_UNUSED_C5FF: 940 case OP_UNUSED_C6FF: 941 case OP_UNUSED_C7FF: 942 case OP_UNUSED_C8FF: 943 case OP_UNUSED_C9FF: 944 case OP_UNUSED_CAFF: 945 case OP_UNUSED_CBFF: 946 case OP_UNUSED_CCFF: 947 case OP_UNUSED_CDFF: 948 case OP_UNUSED_CEFF: 949 case OP_UNUSED_CFFF: 950 case OP_UNUSED_D0FF: 951 case OP_UNUSED_D1FF: 952 case OP_UNUSED_D2FF: 953 case OP_UNUSED_D3FF: 954 case OP_UNUSED_D4FF: 955 case OP_UNUSED_D5FF: 956 case OP_UNUSED_D6FF: 957 case OP_UNUSED_D7FF: 958 case OP_UNUSED_D8FF: 959 case OP_UNUSED_D9FF: 960 case OP_UNUSED_DAFF: 961 case OP_UNUSED_DBFF: 962 case OP_UNUSED_DCFF: 963 case OP_UNUSED_DDFF: 964 case OP_UNUSED_DEFF: 965 case OP_UNUSED_DFFF: 966 case OP_UNUSED_E0FF: 967 case OP_UNUSED_E1FF: 968 case OP_UNUSED_E2FF: 969 case OP_UNUSED_E3FF: 970 case OP_UNUSED_E4FF: 971 case OP_UNUSED_E5FF: 972 case OP_UNUSED_E6FF: 973 case OP_UNUSED_E7FF: 974 case OP_UNUSED_E8FF: 975 case OP_UNUSED_E9FF: 976 case OP_UNUSED_EAFF: 977 case OP_UNUSED_EBFF: 978 case OP_UNUSED_ECFF: 979 case OP_UNUSED_EDFF: 980 case OP_UNUSED_EEFF: 981 case OP_UNUSED_EFFF: 982 case OP_UNUSED_F0FF: 983 case OP_UNUSED_F1FF: 984 return false; 985 } 986 987 return true; 988} 989 990/* 991 * This is a dexDecodeDebugInfo callback, used by markDebugLocals(). 992 */ 993static void markLocalsCb(void* ctxt, u2 reg, u4 startAddress, u4 endAddress, 994 const char* name, const char* descriptor, const char* signature) 995{ 996 VerifierData* vdata = (VerifierData*) ctxt; 997 bool verbose = dvmWantVerboseVerification(vdata->method); 998 999 if (verbose) { 1000 LOGI("%04x-%04x %2d (%s %s)", 1001 startAddress, endAddress, reg, name, descriptor); 1002 } 1003 1004 bool wide = (descriptor[0] == 'D' || descriptor[0] == 'J'); 1005 assert(reg <= vdata->insnRegCount + (wide ? 1 : 0)); 1006 1007 /* 1008 * Set the bit in all GC point instructions in the range 1009 * [startAddress, endAddress). 1010 */ 1011 unsigned int idx; 1012 for (idx = startAddress; idx < endAddress; idx++) { 1013 BitVector* liveRegs = vdata->registerLines[idx].liveRegs; 1014 if (liveRegs != NULL) { 1015 if (wide) { 1016 GENW(liveRegs, reg); 1017 } else { 1018 GEN(liveRegs, reg); 1019 } 1020 } 1021 } 1022} 1023 1024/* 1025 * Mark all debugger-visible locals as live. 1026 * 1027 * The "locals" table describes the positions of the various locals in the 1028 * stack frame based on the current execution address. If the debugger 1029 * wants to display one, it issues a request by "slot number". We need 1030 * to ensure that references in stack slots that might be queried by the 1031 * debugger aren't GCed. 1032 * 1033 * (If the GC had some way to mark the slot as invalid we wouldn't have 1034 * to do this. We could also have the debugger interface check the 1035 * register map and simply refuse to return a "dead" value, but that's 1036 * potentially confusing since the referred-to object might actually be 1037 * alive, and being able to see it without having to hunt around for a 1038 * "live" stack frame is useful.) 1039 */ 1040static bool markDebugLocals(VerifierData* vdata) 1041{ 1042 const Method* meth = vdata->method; 1043 1044 dexDecodeDebugInfo(meth->clazz->pDvmDex->pDexFile, dvmGetMethodCode(meth), 1045 meth->clazz->descriptor, meth->prototype.protoIdx, meth->accessFlags, 1046 NULL, markLocalsCb, vdata); 1047 1048 return true; 1049} 1050 1051 1052/* 1053 * Dump the liveness bits to the log. 1054 * 1055 * "curIdx" is for display only. 1056 */ 1057static void dumpLiveState(const VerifierData* vdata, u4 curIdx, 1058 const BitVector* workBits) 1059{ 1060 u4 insnRegCount = vdata->insnRegCount; 1061 size_t regCharSize = insnRegCount + (insnRegCount-1)/4 + 2 +1; 1062 char regChars[regCharSize +1]; 1063 unsigned int idx; 1064 1065 memset(regChars, ' ', regCharSize); 1066 regChars[0] = '['; 1067 if (insnRegCount == 0) 1068 regChars[1] = ']'; 1069 else 1070 regChars[1 + (insnRegCount-1) + (insnRegCount-1)/4 +1] = ']'; 1071 regChars[regCharSize] = '\0'; 1072 1073 for (idx = 0; idx < insnRegCount; idx++) { 1074 char ch = dvmIsBitSet(workBits, idx) ? '+' : '-'; 1075 regChars[1 + idx + (idx/4)] = ch; 1076 } 1077 1078 LOGI("0x%04x %s", curIdx, regChars); 1079} 1080