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 */
createBackwardWidthTable(VerifierData * vdata)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 */
dvmComputeLiveness(VerifierData * vdata)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 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
274 bail:
275 free(backwardWidth);
276 return result;
277 }
278
279
280 /*
281 * Add a register to the LIVE set.
282 */
GEN(BitVector * workBits,u4 regIndex)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 */
GENW(BitVector * workBits,u4 regIndex)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 */
KILL(BitVector * workBits,u4 regIndex)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 */
KILLW(BitVector * workBits,u4 regIndex)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 */
processInstruction(VerifierData * vdata,u4 insnIdx,BitVector * workBits)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_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 */
markLocalsCb(void * ctxt,u2 reg,u4 startAddress,u4 endAddress,const char * name,const char * descriptor,const char * signature)993 static 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 */
markDebugLocals(VerifierData * vdata)1040 static 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 */
dumpLiveState(const VerifierData * vdata,u4 curIdx,const BitVector * workBits)1057 static 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