2 * Copyright (C) 2009 The Android Open Source Project
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
22 * Main table containing data flow attributes for each bytecode. The first
23 * 256 entries are for Dalvik bytecode instructions, where extended opcode at
24 * the MIR level are appended afterwards.
26 * TODO - many optimization flags are incomplete - they will only limit the
27 * scope of optimizations but will not cause mis-optimizations.
29 int dvmCompilerDataFlowAttributes[MIR_OP_LAST] = {
34 DF_DA | DF_UB | DF_IS_MOVE,
36 // 02 OP_MOVE_FROM16 vAA, vBBBB
37 DF_DA | DF_UB | DF_IS_MOVE,
39 // 03 OP_MOVE_16 vAAAA, vBBBB
40 DF_DA | DF_UB | DF_IS_MOVE,
42 // 04 OP_MOVE_WIDE vA, vB
43 DF_DA_WIDE | DF_UB_WIDE | DF_IS_MOVE,
45 // 05 OP_MOVE_WIDE_FROM16 vAA, vBBBB
46 DF_DA_WIDE | DF_UB_WIDE | DF_IS_MOVE,
48 // 06 OP_MOVE_WIDE_16 vAAAA, vBBBB
49 DF_DA_WIDE | DF_UB_WIDE | DF_IS_MOVE,
51 // 07 OP_MOVE_OBJECT vA, vB
52 DF_DA | DF_UB | DF_IS_MOVE,
54 // 08 OP_MOVE_OBJECT_FROM16 vAA, vBBBB
55 DF_DA | DF_UB | DF_IS_MOVE,
57 // 09 OP_MOVE_OBJECT_16 vAAAA, vBBBB
58 DF_DA | DF_UB | DF_IS_MOVE,
60 // 0A OP_MOVE_RESULT vAA
63 // 0B OP_MOVE_RESULT_WIDE vAA
66 // 0C OP_MOVE_RESULT_OBJECT vAA
69 // 0D OP_MOVE_EXCEPTION vAA
78 // 10 OP_RETURN_WIDE vAA
81 // 11 OP_RETURN_OBJECT vAA
84 // 12 OP_CONST_4 vA, #+B
85 DF_DA | DF_SETS_CONST,
87 // 13 OP_CONST_16 vAA, #+BBBB
88 DF_DA | DF_SETS_CONST,
90 // 14 OP_CONST vAA, #+BBBBBBBB
91 DF_DA | DF_SETS_CONST,
93 // 15 OP_CONST_HIGH16 VAA, #+BBBB0000
94 DF_DA | DF_SETS_CONST,
96 // 16 OP_CONST_WIDE_16 vAA, #+BBBB
97 DF_DA_WIDE | DF_SETS_CONST,
99 // 17 OP_CONST_WIDE_32 vAA, #+BBBBBBBB
100 DF_DA_WIDE | DF_SETS_CONST,
102 // 18 OP_CONST_WIDE vAA, #+BBBBBBBBBBBBBBBB
103 DF_DA_WIDE | DF_SETS_CONST,
105 // 19 OP_CONST_WIDE_HIGH16 vAA, #+BBBB000000000000
106 DF_DA_WIDE | DF_SETS_CONST,
108 // 1A OP_CONST_STRING vAA, string@BBBB
111 // 1B OP_CONST_STRING_JUMBO vAA, string@BBBBBBBB
114 // 1C OP_CONST_CLASS vAA, type@BBBB
117 // 1D OP_MONITOR_ENTER vAA
120 // 1E OP_MONITOR_EXIT vAA
123 // 1F OP_CHECK_CAST vAA, type@BBBB
126 // 20 OP_INSTANCE_OF vA, vB, type@CCCC
129 // 21 OP_ARRAY_LENGTH vA, vB
132 // 22 OP_NEW_INSTANCE vAA, type@BBBB
135 // 23 OP_NEW_ARRAY vA, vB, type@CCCC
138 // 24 OP_FILLED_NEW_ARRAY {vD, vE, vF, vG, vA}
141 // 25 OP_FILLED_NEW_ARRAY_RANGE {vCCCC .. vNNNN}, type@BBBB
144 // 26 OP_FILL_ARRAY_DATA vAA, +BBBBBBBB
159 // 2B OP_PACKED_SWITCH vAA, +BBBBBBBB
162 // 2C OP_SPARSE_SWITCH vAA, +BBBBBBBB
165 // 2D OP_CMPL_FLOAT vAA, vBB, vCC
166 DF_DA | DF_UB | DF_UC,
168 // 2E OP_CMPG_FLOAT vAA, vBB, vCC
169 DF_DA | DF_UB | DF_UC,
171 // 2F OP_CMPL_DOUBLE vAA, vBB, vCC
172 DF_DA_WIDE | DF_UB_WIDE | DF_UC_WIDE,
174 // 30 OP_CMPG_DOUBLE vAA, vBB, vCC
175 DF_DA_WIDE | DF_UB_WIDE | DF_UC_WIDE,
177 // 31 OP_CMP_LONG vAA, vBB, vCC
178 DF_DA_WIDE | DF_UB_WIDE | DF_UC_WIDE,
180 // 32 OP_IF_EQ vA, vB, +CCCC
183 // 33 OP_IF_NE vA, vB, +CCCC
186 // 34 OP_IF_LT vA, vB, +CCCC
189 // 35 OP_IF_GE vA, vB, +CCCC
192 // 36 OP_IF_GT vA, vB, +CCCC
195 // 37 OP_IF_LE vA, vB, +CCCC
199 // 38 OP_IF_EQZ vAA, +BBBB
202 // 39 OP_IF_NEZ vAA, +BBBB
205 // 3A OP_IF_LTZ vAA, +BBBB
208 // 3B OP_IF_GEZ vAA, +BBBB
211 // 3C OP_IF_GTZ vAA, +BBBB
214 // 3D OP_IF_LEZ vAA, +BBBB
235 // 44 OP_AGET vAA, vBB, vCC
236 DF_DA | DF_UB | DF_UC | DF_NULL_N_RANGE_CHECK_0,
238 // 45 OP_AGET_WIDE vAA, vBB, vCC
239 DF_DA_WIDE | DF_UB | DF_UC | DF_NULL_N_RANGE_CHECK_0,
241 // 46 OP_AGET_OBJECT vAA, vBB, vCC
242 DF_DA | DF_UB | DF_UC | DF_NULL_N_RANGE_CHECK_0,
244 // 47 OP_AGET_BOOLEAN vAA, vBB, vCC
245 DF_DA | DF_UB | DF_UC | DF_NULL_N_RANGE_CHECK_0,
247 // 48 OP_AGET_BYTE vAA, vBB, vCC
248 DF_DA | DF_UB | DF_UC | DF_NULL_N_RANGE_CHECK_0,
250 // 49 OP_AGET_CHAR vAA, vBB, vCC
251 DF_DA | DF_UB | DF_UC | DF_NULL_N_RANGE_CHECK_0,
253 // 4A OP_AGET_SHORT vAA, vBB, vCC
254 DF_DA | DF_UB | DF_UC | DF_NULL_N_RANGE_CHECK_0,
256 // 4B OP_APUT vAA, vBB, vCC
257 DF_UA | DF_UB | DF_UC | DF_NULL_N_RANGE_CHECK_1,
259 // 4C OP_APUT_WIDE vAA, vBB, vCC
260 DF_UA_WIDE | DF_UB | DF_UC | DF_NULL_N_RANGE_CHECK_2,
262 // 4D OP_APUT_OBJECT vAA, vBB, vCC
263 DF_UA | DF_UB | DF_UC | DF_NULL_N_RANGE_CHECK_1,
265 // 4E OP_APUT_BOOLEAN vAA, vBB, vCC
266 DF_UA | DF_UB | DF_UC | DF_NULL_N_RANGE_CHECK_1,
268 // 4F OP_APUT_BYTE vAA, vBB, vCC
269 DF_UA | DF_UB | DF_UC | DF_NULL_N_RANGE_CHECK_1,
271 // 50 OP_APUT_CHAR vAA, vBB, vCC
272 DF_UA | DF_UB | DF_UC | DF_NULL_N_RANGE_CHECK_1,
274 // 51 OP_APUT_SHORT vAA, vBB, vCC
275 DF_UA | DF_UB | DF_UC | DF_NULL_N_RANGE_CHECK_1,
277 // 52 OP_IGET vA, vB, field@CCCC
280 // 53 OP_IGET_WIDE vA, vB, field@CCCC
283 // 54 OP_IGET_OBJECT vA, vB, field@CCCC
286 // 55 OP_IGET_BOOLEAN vA, vB, field@CCCC
289 // 56 OP_IGET_BYTE vA, vB, field@CCCC
292 // 57 OP_IGET_CHAR vA, vB, field@CCCC
295 // 58 OP_IGET_SHORT vA, vB, field@CCCC
298 // 59 OP_IPUT vA, vB, field@CCCC
301 // 5A OP_IPUT_WIDE vA, vB, field@CCCC
304 // 5B OP_IPUT_OBJECT vA, vB, field@CCCC
307 // 5C OP_IPUT_BOOLEAN vA, vB, field@CCCC
310 // 5D OP_IPUT_BYTE vA, vB, field@CCCC
313 // 5E OP_IPUT_CHAR vA, vB, field@CCCC
316 // 5F OP_IPUT_SHORT vA, vB, field@CCCC
319 // 60 OP_SGET vAA, field@BBBB
322 // 61 OP_SGET_WIDE vAA, field@BBBB
325 // 62 OP_SGET_OBJECT vAA, field@BBBB
328 // 63 OP_SGET_BOOLEAN vAA, field@BBBB
331 // 64 OP_SGET_BYTE vAA, field@BBBB
334 // 65 OP_SGET_CHAR vAA, field@BBBB
337 // 66 OP_SGET_SHORT vAA, field@BBBB
340 // 67 OP_SPUT vAA, field@BBBB
343 // 68 OP_SPUT_WIDE vAA, field@BBBB
346 // 69 OP_SPUT_OBJECT vAA, field@BBBB
349 // 6A OP_SPUT_BOOLEAN vAA, field@BBBB
352 // 6B OP_SPUT_BYTE vAA, field@BBBB
355 // 6C OP_SPUT_CHAR vAA, field@BBBB
358 // 6D OP_SPUT_SHORT vAA, field@BBBB
361 // 6E OP_INVOKE_VIRTUAL {vD, vE, vF, vG, vA}
364 // 6F OP_INVOKE_SUPER {vD, vE, vF, vG, vA}
367 // 70 OP_INVOKE_DIRECT {vD, vE, vF, vG, vA}
370 // 71 OP_INVOKE_STATIC {vD, vE, vF, vG, vA}
373 // 72 OP_INVOKE_INTERFACE {vD, vE, vF, vG, vA}
379 // 74 OP_INVOKE_VIRTUAL_RANGE {vCCCC .. vNNNN}
382 // 75 OP_INVOKE_SUPER_RANGE {vCCCC .. vNNNN}
385 // 76 OP_INVOKE_DIRECT_RANGE {vCCCC .. vNNNN}
388 // 77 OP_INVOKE_STATIC_RANGE {vCCCC .. vNNNN}
391 // 78 OP_INVOKE_INTERFACE_RANGE {vCCCC .. vNNNN}
400 // 7B OP_NEG_INT vA, vB
403 // 7C OP_NOT_INT vA, vB
406 // 7D OP_NEG_LONG vA, vB
407 DF_DA_WIDE | DF_UB_WIDE,
409 // 7E OP_NOT_LONG vA, vB
410 DF_DA_WIDE | DF_UB_WIDE,
412 // 7F OP_NEG_FLOAT vA, vB
415 // 80 OP_NEG_DOUBLE vA, vB
416 DF_DA_WIDE | DF_UB_WIDE,
418 // 81 OP_INT_TO_LONG vA, vB
421 // 82 OP_INT_TO_FLOAT vA, vB
424 // 83 OP_INT_TO_DOUBLE vA, vB
427 // 84 OP_LONG_TO_INT vA, vB
430 // 85 OP_LONG_TO_FLOAT vA, vB
433 // 86 OP_LONG_TO_DOUBLE vA, vB
434 DF_DA_WIDE | DF_UB_WIDE,
436 // 87 OP_FLOAT_TO_INT vA, vB
439 // 88 OP_FLOAT_TO_LONG vA, vB
442 // 89 OP_FLOAT_TO_DOUBLE vA, vB
445 // 8A OP_DOUBLE_TO_INT vA, vB
448 // 8B OP_DOUBLE_TO_LONG vA, vB
449 DF_DA_WIDE | DF_UB_WIDE,
451 // 8C OP_DOUBLE_TO_FLOAT vA, vB
454 // 8D OP_INT_TO_BYTE vA, vB
457 // 8E OP_INT_TO_CHAR vA, vB
460 // 8F OP_INT_TO_SHORT vA, vB
463 // 90 OP_ADD_INT vAA, vBB, vCC
464 DF_DA | DF_UB | DF_UC | DF_IS_LINEAR,
466 // 91 OP_SUB_INT vAA, vBB, vCC
467 DF_DA | DF_UB | DF_UC | DF_IS_LINEAR,
469 // 92 OP_MUL_INT vAA, vBB, vCC
470 DF_DA | DF_UB | DF_UC,
472 // 93 OP_DIV_INT vAA, vBB, vCC
473 DF_DA | DF_UB | DF_UC,
475 // 94 OP_REM_INT vAA, vBB, vCC
476 DF_DA | DF_UB | DF_UC,
478 // 95 OP_AND_INT vAA, vBB, vCC
479 DF_DA | DF_UB | DF_UC,
481 // 96 OP_OR_INT vAA, vBB, vCC
482 DF_DA | DF_UB | DF_UC,
484 // 97 OP_XOR_INT vAA, vBB, vCC
485 DF_DA | DF_UB | DF_UC,
487 // 98 OP_SHL_INT vAA, vBB, vCC
488 DF_DA | DF_UB | DF_UC,
490 // 99 OP_SHR_INT vAA, vBB, vCC
491 DF_DA | DF_UB | DF_UC,
493 // 9A OP_USHR_INT vAA, vBB, vCC
494 DF_DA | DF_UB | DF_UC,
496 // 9B OP_ADD_LONG vAA, vBB, vCC
497 DF_DA_WIDE | DF_UB_WIDE | DF_UC_WIDE,
499 // 9C OP_SUB_LONG vAA, vBB, vCC
500 DF_DA_WIDE | DF_UB_WIDE | DF_UC_WIDE,
502 // 9D OP_MUL_LONG vAA, vBB, vCC
503 DF_DA_WIDE | DF_UB_WIDE | DF_UC_WIDE,
505 // 9E OP_DIV_LONG vAA, vBB, vCC
506 DF_DA_WIDE | DF_UB_WIDE | DF_UC_WIDE,
508 // 9F OP_REM_LONG vAA, vBB, vCC
509 DF_DA_WIDE | DF_UB_WIDE | DF_UC_WIDE,
511 // A0 OP_AND_LONG vAA, vBB, vCC
512 DF_DA_WIDE | DF_UB_WIDE | DF_UC_WIDE,
514 // A1 OP_OR_LONG vAA, vBB, vCC
515 DF_DA_WIDE | DF_UB_WIDE | DF_UC_WIDE,
517 // A2 OP_XOR_LONG vAA, vBB, vCC
518 DF_DA_WIDE | DF_UB_WIDE | DF_UC_WIDE,
520 // A3 OP_SHL_LONG vAA, vBB, vCC
521 DF_DA_WIDE | DF_UB_WIDE | DF_UC_WIDE,
523 // A4 OP_SHR_LONG vAA, vBB, vCC
524 DF_DA_WIDE | DF_UB_WIDE | DF_UC_WIDE,
526 // A5 OP_USHR_LONG vAA, vBB, vCC
527 DF_DA_WIDE | DF_UB_WIDE | DF_UC_WIDE,
529 // A6 OP_ADD_FLOAT vAA, vBB, vCC
530 DF_DA | DF_UB | DF_UC,
532 // A7 OP_SUB_FLOAT vAA, vBB, vCC
533 DF_DA | DF_UB | DF_UC,
535 // A8 OP_MUL_FLOAT vAA, vBB, vCC
536 DF_DA | DF_UB | DF_UC,
538 // A9 OP_DIV_FLOAT vAA, vBB, vCC
539 DF_DA | DF_UB | DF_UC,
541 // AA OP_REM_FLOAT vAA, vBB, vCC
542 DF_DA | DF_UB | DF_UC,
544 // AB OP_ADD_DOUBLE vAA, vBB, vCC
545 DF_DA_WIDE | DF_UB_WIDE | DF_UC_WIDE,
547 // AC OP_SUB_DOUBLE vAA, vBB, vCC
548 DF_DA_WIDE | DF_UB_WIDE | DF_UC_WIDE,
550 // AD OP_MUL_DOUBLE vAA, vBB, vCC
551 DF_DA_WIDE | DF_UB_WIDE | DF_UC_WIDE,
553 // AE OP_DIV_DOUBLE vAA, vBB, vCC
554 DF_DA_WIDE | DF_UB_WIDE | DF_UC_WIDE,
556 // AF OP_REM_DOUBLE vAA, vBB, vCC
557 DF_DA_WIDE | DF_UB_WIDE | DF_UC_WIDE,
559 // B0 OP_ADD_INT_2ADDR vA, vB
560 DF_DA | DF_UA | DF_UB,
562 // B1 OP_SUB_INT_2ADDR vA, vB
563 DF_DA | DF_UA | DF_UB,
565 // B2 OP_MUL_INT_2ADDR vA, vB
566 DF_DA | DF_UA | DF_UB,
568 // B3 OP_DIV_INT_2ADDR vA, vB
569 DF_DA | DF_UA | DF_UB,
571 // B4 OP_REM_INT_2ADDR vA, vB
572 DF_DA | DF_UA | DF_UB,
574 // B5 OP_AND_INT_2ADDR vA, vB
575 DF_DA | DF_UA | DF_UB,
577 // B6 OP_OR_INT_2ADDR vA, vB
578 DF_DA | DF_UA | DF_UB,
580 // B7 OP_XOR_INT_2ADDR vA, vB
581 DF_DA | DF_UA | DF_UB,
583 // B8 OP_SHL_INT_2ADDR vA, vB
584 DF_DA | DF_UA | DF_UB,
586 // B9 OP_SHR_INT_2ADDR vA, vB
587 DF_DA | DF_UA | DF_UB,
589 // BA OP_USHR_INT_2ADDR vA, vB
590 DF_DA | DF_UA | DF_UB,
592 // BB OP_ADD_LONG_2ADDR vA, vB
593 DF_DA_WIDE | DF_UA_WIDE | DF_UB_WIDE,
595 // BC OP_SUB_LONG_2ADDR vA, vB
596 DF_DA_WIDE | DF_UA_WIDE | DF_UB_WIDE,
598 // BD OP_MUL_LONG_2ADDR vA, vB
599 DF_DA_WIDE | DF_UA_WIDE | DF_UB_WIDE,
601 // BE OP_DIV_LONG_2ADDR vA, vB
602 DF_DA_WIDE | DF_UA_WIDE | DF_UB_WIDE,
604 // BF OP_REM_LONG_2ADDR vA, vB
605 DF_DA_WIDE | DF_UA_WIDE | DF_UB_WIDE,
607 // C0 OP_AND_LONG_2ADDR vA, vB
608 DF_DA_WIDE | DF_UA_WIDE | DF_UB_WIDE,
610 // C1 OP_OR_LONG_2ADDR vA, vB
611 DF_DA_WIDE | DF_UA_WIDE | DF_UB_WIDE,
613 // C2 OP_XOR_LONG_2ADDR vA, vB
614 DF_DA_WIDE | DF_UA_WIDE | DF_UB_WIDE,
616 // C3 OP_SHL_LONG_2ADDR vA, vB
617 DF_DA_WIDE | DF_UA_WIDE | DF_UB_WIDE,
619 // C4 OP_SHR_LONG_2ADDR vA, vB
620 DF_DA_WIDE | DF_UA_WIDE | DF_UB_WIDE,
622 // C5 OP_USHR_LONG_2ADDR vA, vB
623 DF_DA_WIDE | DF_UA_WIDE | DF_UB_WIDE,
625 // C6 OP_ADD_FLOAT_2ADDR vA, vB
626 DF_DA | DF_UA | DF_UB,
628 // C7 OP_SUB_FLOAT_2ADDR vA, vB
629 DF_DA | DF_UA | DF_UB,
631 // C8 OP_MUL_FLOAT_2ADDR vA, vB
632 DF_DA | DF_UA | DF_UB,
634 // C9 OP_DIV_FLOAT_2ADDR vA, vB
635 DF_DA | DF_UA | DF_UB,
637 // CA OP_REM_FLOAT_2ADDR vA, vB
638 DF_DA | DF_UA | DF_UB,
640 // CB OP_ADD_DOUBLE_2ADDR vA, vB
641 DF_DA_WIDE | DF_UA_WIDE | DF_UB_WIDE,
643 // CC OP_SUB_DOUBLE_2ADDR vA, vB
644 DF_DA_WIDE | DF_UA_WIDE | DF_UB_WIDE,
646 // CD OP_MUL_DOUBLE_2ADDR vA, vB
647 DF_DA_WIDE | DF_UA_WIDE | DF_UB_WIDE,
649 // CE OP_DIV_DOUBLE_2ADDR vA, vB
650 DF_DA_WIDE | DF_UA_WIDE | DF_UB_WIDE,
652 // CF OP_REM_DOUBLE_2ADDR vA, vB
653 DF_DA_WIDE | DF_UA_WIDE | DF_UB_WIDE,
655 // D0 OP_ADD_INT_LIT16 vA, vB, #+CCCC
658 // D1 OP_RSUB_INT vA, vB, #+CCCC
661 // D2 OP_MUL_INT_LIT16 vA, vB, #+CCCC
664 // D3 OP_DIV_INT_LIT16 vA, vB, #+CCCC
667 // D4 OP_REM_INT_LIT16 vA, vB, #+CCCC
670 // D5 OP_AND_INT_LIT16 vA, vB, #+CCCC
673 // D6 OP_OR_INT_LIT16 vA, vB, #+CCCC
676 // D7 OP_XOR_INT_LIT16 vA, vB, #+CCCC
679 // D8 OP_ADD_INT_LIT8 vAA, vBB, #+CC
680 DF_DA | DF_UB | DF_IS_LINEAR,
682 // D9 OP_RSUB_INT_LIT8 vAA, vBB, #+CC
685 // DA OP_MUL_INT_LIT8 vAA, vBB, #+CC
688 // DB OP_DIV_INT_LIT8 vAA, vBB, #+CC
691 // DC OP_REM_INT_LIT8 vAA, vBB, #+CC
694 // DD OP_AND_INT_LIT8 vAA, vBB, #+CC
697 // DE OP_OR_INT_LIT8 vAA, vBB, #+CC
700 // DF OP_XOR_INT_LIT8 vAA, vBB, #+CC
703 // E0 OP_SHL_INT_LIT8 vAA, vBB, #+CC
706 // E1 OP_SHR_INT_LIT8 vAA, vBB, #+CC
709 // E2 OP_USHR_INT_LIT8 vAA, vBB, #+CC
742 // ED OP_THROW_VERIFICATION_ERROR
745 // EE OP_EXECUTE_INLINE
751 // F0 OP_INVOKE_DIRECT_EMPTY
760 // F3 OP_IGET_WIDE_QUICK
763 // F4 OP_IGET_OBJECT_QUICK
769 // F6 OP_IPUT_WIDE_QUICK
772 // F7 OP_IPUT_OBJECT_QUICK
775 // F8 OP_INVOKE_VIRTUAL_QUICK
778 // F9 OP_INVOKE_VIRTUAL_QUICK_RANGE
781 // FA OP_INVOKE_SUPER_QUICK
784 // FB OP_INVOKE_SUPER_QUICK_RANGE
799 // Beginning of extended MIR opcodes
804 * For extended MIR inserted at the MIR2LIR stage, it is okay to have
805 * undefined values here.
809 /* Return the Dalvik register/subscript pair of a given SSA register */
810 int dvmConvertSSARegToDalvik(CompilationUnit *cUnit, int ssaReg)
812 return GET_ELEM_N(cUnit->ssaToDalvikMap, int, ssaReg);
816 * Utility function to convert encoded SSA register value into Dalvik register
817 * and subscript pair. Each SSA register can be used to index the
818 * ssaToDalvikMap list to get the subscript[31..16]/dalvik_reg[15..0] mapping.
820 char *dvmCompilerGetSSAString(CompilationUnit *cUnit, SSARepresentation *ssaRep)
827 for (i = 0; i < ssaRep->numDefs; i++) {
828 int ssa2DalvikValue = dvmConvertSSARegToDalvik(cUnit, ssaRep->defs[i]);
830 sprintf(buffer + strlen(buffer), "s%d(v%d_%d) ",
831 ssaRep->defs[i], DECODE_REG(ssa2DalvikValue),
832 DECODE_SUB(ssa2DalvikValue));
835 if (ssaRep->numDefs) {
836 strcat(buffer, "<- ");
839 for (i = 0; i < ssaRep->numUses; i++) {
840 int ssa2DalvikValue = dvmConvertSSARegToDalvik(cUnit, ssaRep->uses[i]);
841 int len = strlen(buffer);
843 if (snprintf(buffer + len, 250 - len, "s%d(v%d_%d) ",
844 ssaRep->uses[i], DECODE_REG(ssa2DalvikValue),
845 DECODE_SUB(ssa2DalvikValue)) >= (250 - len)) {
846 strcat(buffer, "...");
851 int length = strlen(buffer) + 1;
852 ret = dvmCompilerNew(length, false);
853 memcpy(ret, buffer, length);
857 /* Any register that is used before being defined is considered live-in */
858 static inline void handleLiveInUse(BitVector *useV, BitVector *defV,
859 BitVector *liveInV, int dalvikRegId)
861 dvmCompilerSetBit(useV, dalvikRegId);
862 if (!dvmIsBitSet(defV, dalvikRegId)) {
863 dvmCompilerSetBit(liveInV, dalvikRegId);
867 /* Mark a reg as being defined */
868 static inline void handleLiveInDef(BitVector *defV, int dalvikRegId)
870 dvmCompilerSetBit(defV, dalvikRegId);
874 * Find out live-in variables for natural loops. Variables that are live-in in
875 * the main loop body are considered to be defined in the entry block.
877 void dvmCompilerFindLiveIn(CompilationUnit *cUnit, BasicBlock *bb)
880 BitVector *useV, *defV, *liveInV;
882 if (bb->blockType != DALVIK_BYTECODE &&
883 bb->blockType != ENTRY_BLOCK) {
887 useV = bb->dataFlowInfo->useV =
888 dvmCompilerAllocBitVector(cUnit->method->registersSize, false);
889 defV = bb->dataFlowInfo->defV =
890 dvmCompilerAllocBitVector(cUnit->method->registersSize, false);
891 liveInV = bb->dataFlowInfo->liveInV =
892 dvmCompilerAllocBitVector(cUnit->method->registersSize, false);
894 for (mir = bb->firstMIRInsn; mir; mir = mir->next) {
896 dvmCompilerDataFlowAttributes[mir->dalvikInsn.opCode];
897 DecodedInstruction *dInsn = &mir->dalvikInsn;
899 if (dfAttributes & DF_HAS_USES) {
900 if (dfAttributes & DF_UA) {
901 handleLiveInUse(useV, defV, liveInV, dInsn->vA);
902 } else if (dfAttributes & DF_UA_WIDE) {
903 handleLiveInUse(useV, defV, liveInV, dInsn->vA);
904 handleLiveInUse(useV, defV, liveInV, dInsn->vA+1);
906 if (dfAttributes & DF_UB) {
907 handleLiveInUse(useV, defV, liveInV, dInsn->vB);
908 } else if (dfAttributes & DF_UB_WIDE) {
909 handleLiveInUse(useV, defV, liveInV, dInsn->vB);
910 handleLiveInUse(useV, defV, liveInV, dInsn->vB+1);
912 if (dfAttributes & DF_UC) {
913 handleLiveInUse(useV, defV, liveInV, dInsn->vC);
914 } else if (dfAttributes & DF_UC_WIDE) {
915 handleLiveInUse(useV, defV, liveInV, dInsn->vC);
916 handleLiveInUse(useV, defV, liveInV, dInsn->vC+1);
919 if (dfAttributes & DF_HAS_DEFS) {
920 handleLiveInDef(defV, dInsn->vA);
921 if (dfAttributes & DF_DA_WIDE) {
922 handleLiveInDef(defV, dInsn->vA+1);
928 /* Find out the latest SSA register for a given Dalvik register */
929 static void handleSSAUse(CompilationUnit *cUnit, int *uses, int dalvikReg,
932 int encodedValue = cUnit->dalvikToSSAMap[dalvikReg];
933 int ssaReg = DECODE_REG(encodedValue);
934 uses[regIndex] = ssaReg;
937 /* Setup a new SSA register for a given Dalvik register */
938 static void handleSSADef(CompilationUnit *cUnit, int *defs, int dalvikReg,
941 int encodedValue = cUnit->dalvikToSSAMap[dalvikReg];
942 int ssaReg = cUnit->numSSARegs++;
943 /* Bump up the subscript */
944 int dalvikSub = DECODE_SUB(encodedValue) + 1;
945 int newD2SMapping = ENCODE_REG_SUB(ssaReg, dalvikSub);
947 cUnit->dalvikToSSAMap[dalvikReg] = newD2SMapping;
949 int newS2DMapping = ENCODE_REG_SUB(dalvikReg, dalvikSub);
950 dvmInsertGrowableList(cUnit->ssaToDalvikMap, (void *) newS2DMapping);
952 defs[regIndex] = ssaReg;
955 /* Loop up new SSA names for format_35c instructions */
956 static void dataFlowSSAFormat35C(CompilationUnit *cUnit, MIR *mir)
958 DecodedInstruction *dInsn = &mir->dalvikInsn;
959 int numUses = dInsn->vA;
962 mir->ssaRep->numUses = numUses;
963 mir->ssaRep->uses = dvmCompilerNew(sizeof(int) * numUses, false);
965 for (i = 0; i < numUses; i++) {
966 handleSSAUse(cUnit, mir->ssaRep->uses, dInsn->arg[i], i);
970 /* Loop up new SSA names for format_3rc instructions */
971 static void dataFlowSSAFormat3RC(CompilationUnit *cUnit, MIR *mir)
973 DecodedInstruction *dInsn = &mir->dalvikInsn;
974 int numUses = dInsn->vA;
977 mir->ssaRep->numUses = numUses;
978 mir->ssaRep->uses = dvmCompilerNew(sizeof(int) * numUses, false);
980 for (i = 0; i < numUses; i++) {
981 handleSSAUse(cUnit, mir->ssaRep->uses, dInsn->vC+i, i);
985 /* Entry function to convert a block into SSA representation */
986 void dvmCompilerDoSSAConversion(CompilationUnit *cUnit, BasicBlock *bb)
990 if (bb->blockType != DALVIK_BYTECODE && bb->blockType != ENTRY_BLOCK) {
994 for (mir = bb->firstMIRInsn; mir; mir = mir->next) {
995 mir->ssaRep = dvmCompilerNew(sizeof(SSARepresentation), true);
998 dvmCompilerDataFlowAttributes[mir->dalvikInsn.opCode];
1002 if (dfAttributes & DF_FORMAT_35C) {
1003 dataFlowSSAFormat35C(cUnit, mir);
1007 if (dfAttributes & DF_FORMAT_3RC) {
1008 dataFlowSSAFormat3RC(cUnit, mir);
1012 if (dfAttributes & DF_HAS_USES) {
1013 if (dfAttributes & DF_UA) {
1015 } else if (dfAttributes & DF_UA_WIDE) {
1018 if (dfAttributes & DF_UB) {
1020 } else if (dfAttributes & DF_UB_WIDE) {
1023 if (dfAttributes & DF_UC) {
1025 } else if (dfAttributes & DF_UC_WIDE) {
1031 mir->ssaRep->numUses = numUses;
1032 mir->ssaRep->uses = dvmCompilerNew(sizeof(int) * numUses, false);
1037 if (dfAttributes & DF_HAS_DEFS) {
1039 if (dfAttributes & DF_DA_WIDE) {
1045 mir->ssaRep->numDefs = numDefs;
1046 mir->ssaRep->defs = dvmCompilerNew(sizeof(int) * numDefs, false);
1049 DecodedInstruction *dInsn = &mir->dalvikInsn;
1051 if (dfAttributes & DF_HAS_USES) {
1053 if (dfAttributes & DF_UA) {
1054 handleSSAUse(cUnit, mir->ssaRep->uses, dInsn->vA, numUses++);
1055 } else if (dfAttributes & DF_UA_WIDE) {
1056 handleSSAUse(cUnit, mir->ssaRep->uses, dInsn->vA, numUses++);
1057 handleSSAUse(cUnit, mir->ssaRep->uses, dInsn->vA+1, numUses++);
1059 if (dfAttributes & DF_UB) {
1060 handleSSAUse(cUnit, mir->ssaRep->uses, dInsn->vB, numUses++);
1061 } else if (dfAttributes & DF_UB_WIDE) {
1062 handleSSAUse(cUnit, mir->ssaRep->uses, dInsn->vB, numUses++);
1063 handleSSAUse(cUnit, mir->ssaRep->uses, dInsn->vB+1, numUses++);
1065 if (dfAttributes & DF_UC) {
1066 handleSSAUse(cUnit, mir->ssaRep->uses, dInsn->vC, numUses++);
1067 } else if (dfAttributes & DF_UC_WIDE) {
1068 handleSSAUse(cUnit, mir->ssaRep->uses, dInsn->vC, numUses++);
1069 handleSSAUse(cUnit, mir->ssaRep->uses, dInsn->vC+1, numUses++);
1072 if (dfAttributes & DF_HAS_DEFS) {
1073 handleSSADef(cUnit, mir->ssaRep->defs, dInsn->vA, 0);
1074 if (dfAttributes & DF_DA_WIDE) {
1075 handleSSADef(cUnit, mir->ssaRep->defs, dInsn->vA+1, 1);
1080 bb->dataFlowInfo->dalvikToSSAMap =
1081 dvmCompilerNew(sizeof(int) * cUnit->method->registersSize, false);
1083 /* Take a snapshot of Dalvik->SSA mapping at the end of each block */
1084 memcpy(bb->dataFlowInfo->dalvikToSSAMap, cUnit->dalvikToSSAMap,
1085 sizeof(int) * cUnit->method->registersSize);
1088 /* Setup a constant value for opcodes thare have the DF_SETS_CONST attribute */
1089 static void setConstant(CompilationUnit *cUnit, int ssaReg, int value)
1091 dvmSetBit(cUnit->isConstantV, ssaReg);
1092 cUnit->constantValues[ssaReg] = value;
1095 void dvmCompilerDoConstantPropagation(CompilationUnit *cUnit, BasicBlock *bb)
1098 BitVector *isConstantV = cUnit->isConstantV;
1100 for (mir = bb->firstMIRInsn; mir; mir = mir->next) {
1102 dvmCompilerDataFlowAttributes[mir->dalvikInsn.opCode];
1106 DecodedInstruction *dInsn = &mir->dalvikInsn;
1108 if (!(dfAttributes & DF_HAS_DEFS)) continue;
1110 /* Handle instructions that set up constants directly */
1111 if (dfAttributes & DF_SETS_CONST) {
1112 if (dfAttributes & DF_DA) {
1113 switch (dInsn->opCode) {
1117 setConstant(cUnit, mir->ssaRep->defs[0], dInsn->vB);
1119 case OP_CONST_HIGH16:
1120 setConstant(cUnit, mir->ssaRep->defs[0],
1126 } else if (dfAttributes & DF_DA_WIDE) {
1127 switch (dInsn->opCode) {
1128 case OP_CONST_WIDE_16:
1129 case OP_CONST_WIDE_32:
1130 setConstant(cUnit, mir->ssaRep->defs[0], dInsn->vB);
1131 setConstant(cUnit, mir->ssaRep->defs[1], 0);
1134 setConstant(cUnit, mir->ssaRep->defs[0],
1135 (int) dInsn->vB_wide);
1136 setConstant(cUnit, mir->ssaRep->defs[1],
1137 (int) (dInsn->vB_wide >> 32));
1139 case OP_CONST_WIDE_HIGH16:
1140 setConstant(cUnit, mir->ssaRep->defs[0], 0);
1141 setConstant(cUnit, mir->ssaRep->defs[1],
1148 /* Handle instructions that set up constants directly */
1149 } else if (dfAttributes & DF_IS_MOVE) {
1152 for (i = 0; i < mir->ssaRep->numUses; i++) {
1153 if (!dvmIsBitSet(isConstantV, mir->ssaRep->uses[i])) break;
1155 /* Move a register holding a constant to another register */
1156 if (i == mir->ssaRep->numUses) {
1157 setConstant(cUnit, mir->ssaRep->defs[0],
1158 cUnit->constantValues[mir->ssaRep->uses[0]]);
1159 if (dfAttributes & DF_DA_WIDE) {
1160 setConstant(cUnit, mir->ssaRep->defs[1],
1161 cUnit->constantValues[mir->ssaRep->uses[1]]);
1166 /* TODO: implement code to handle arithmetic operations */
1169 void dvmCompilerFindInductionVariables(struct CompilationUnit *cUnit,
1170 struct BasicBlock *bb)
1172 BitVector *isIndVarV = cUnit->loopAnalysis->isIndVarV;
1173 BitVector *isConstantV = cUnit->isConstantV;
1174 GrowableList *ivList = cUnit->loopAnalysis->ivList;
1177 if (bb->blockType != DALVIK_BYTECODE &&
1178 bb->blockType != ENTRY_BLOCK) {
1182 /* If the bb doesn't have a phi it cannot contain an induction variable */
1183 if (bb->firstMIRInsn == NULL ||
1184 bb->firstMIRInsn->dalvikInsn.opCode != MIR_OP_PHI) {
1188 /* Find basic induction variable first */
1189 for (mir = bb->firstMIRInsn; mir; mir = mir->next) {
1191 dvmCompilerDataFlowAttributes[mir->dalvikInsn.opCode];
1193 if (!(dfAttributes & DF_IS_LINEAR)) continue;
1196 * For a basic induction variable:
1197 * 1) use[0] should belong to the output of a phi node
1198 * 2) def[0] should belong to the input of the same phi node
1199 * 3) the value added/subtracted is a constant
1202 for (phi = bb->firstMIRInsn; phi; phi = phi->next) {
1203 if (phi->dalvikInsn.opCode != MIR_OP_PHI) break;
1205 if (phi->ssaRep->defs[0] == mir->ssaRep->uses[0] &&
1206 phi->ssaRep->uses[1] == mir->ssaRep->defs[0]) {
1207 bool deltaIsConstant = false;
1210 switch (mir->dalvikInsn.opCode) {
1212 if (dvmIsBitSet(isConstantV,
1213 mir->ssaRep->uses[1])) {
1215 cUnit->constantValues[mir->ssaRep->uses[1]];
1216 deltaIsConstant = true;
1220 if (dvmIsBitSet(isConstantV,
1221 mir->ssaRep->uses[1])) {
1223 -cUnit->constantValues[mir->ssaRep->uses[1]];
1224 deltaIsConstant = true;
1227 case OP_ADD_INT_LIT8:
1228 deltaValue = mir->dalvikInsn.vC;
1229 deltaIsConstant = true;
1234 if (deltaIsConstant) {
1235 dvmSetBit(isIndVarV, mir->ssaRep->uses[0]);
1236 InductionVariableInfo *ivInfo =
1237 dvmCompilerNew(sizeof(InductionVariableInfo),
1240 ivInfo->ssaReg = mir->ssaRep->uses[0];
1241 ivInfo->basicSSAReg = mir->ssaRep->uses[0];
1242 ivInfo->m = 1; // always 1 to basic iv
1243 ivInfo->c = 0; // N/A to basic iv
1244 ivInfo->inc = deltaValue;
1245 dvmInsertGrowableList(ivList, (void *) ivInfo);
1246 cUnit->loopAnalysis->numBasicIV++;
1253 /* Find dependent induction variable now */
1254 for (mir = bb->firstMIRInsn; mir; mir = mir->next) {
1256 dvmCompilerDataFlowAttributes[mir->dalvikInsn.opCode];
1258 if (!(dfAttributes & DF_IS_LINEAR)) continue;
1260 /* Skip already identified induction variables */
1261 if (dvmIsBitSet(isIndVarV, mir->ssaRep->defs[0])) continue;
1264 * For a dependent induction variable:
1265 * 1) use[0] should be an induction variable (basic/dependent)
1266 * 2) operand2 should be a constant
1268 if (dvmIsBitSet(isIndVarV, mir->ssaRep->uses[0])) {
1269 int srcDalvikReg = dvmConvertSSARegToDalvik(cUnit,
1270 mir->ssaRep->uses[0]);
1271 int dstDalvikReg = dvmConvertSSARegToDalvik(cUnit,
1272 mir->ssaRep->defs[0]);
1274 bool cIsConstant = false;
1277 switch (mir->dalvikInsn.opCode) {
1279 if (dvmIsBitSet(isConstantV,
1280 mir->ssaRep->uses[1])) {
1281 c = cUnit->constantValues[mir->ssaRep->uses[1]];
1286 if (dvmIsBitSet(isConstantV,
1287 mir->ssaRep->uses[1])) {
1288 c = -cUnit->constantValues[mir->ssaRep->uses[1]];
1292 case OP_ADD_INT_LIT8:
1293 c = mir->dalvikInsn.vC;
1300 /* Ignore the update to the basic induction variable itself */
1301 if (DECODE_REG(srcDalvikReg) == DECODE_REG(dstDalvikReg)) {
1302 cUnit->loopAnalysis->ssaBIV = mir->ssaRep->defs[0];
1303 cIsConstant = false;
1308 dvmSetBit(isIndVarV, mir->ssaRep->defs[0]);
1309 InductionVariableInfo *ivInfo =
1310 dvmCompilerNew(sizeof(InductionVariableInfo),
1312 InductionVariableInfo *ivInfoOld = NULL ;
1314 for (i = 0; i < ivList->numUsed; i++) {
1315 ivInfoOld = ivList->elemList[i];
1316 if (ivInfoOld->ssaReg == mir->ssaRep->uses[0]) break;
1319 /* Guaranteed to find an element */
1320 assert(i < ivList->numUsed);
1322 ivInfo->ssaReg = mir->ssaRep->defs[0];
1323 ivInfo->basicSSAReg = ivInfoOld->basicSSAReg;
1324 ivInfo->m = ivInfoOld->m;
1325 ivInfo->c = c + ivInfoOld->c;
1326 ivInfo->inc = ivInfoOld->inc;
1327 dvmInsertGrowableList(ivList, (void *) ivInfo);
1333 /* Setup the basic data structures for SSA conversion */
1334 void dvmInitializeSSAConversion(CompilationUnit *cUnit)
1337 int numDalvikReg = cUnit->method->registersSize;
1339 cUnit->ssaToDalvikMap = dvmCompilerNew(sizeof(GrowableList), false);
1340 dvmInitGrowableList(cUnit->ssaToDalvikMap, numDalvikReg);
1343 * Initial number of SSA registers is equal to the number of Dalvik
1346 cUnit->numSSARegs = numDalvikReg;
1349 * Initialize the SSA2Dalvik map list. For the first numDalvikReg elements,
1350 * the subscript is 0 so we use the ENCODE_REG_SUB macro to encode the value
1351 * into "(0 << 16) | i"
1353 for (i = 0; i < numDalvikReg; i++) {
1354 dvmInsertGrowableList(cUnit->ssaToDalvikMap,
1355 (void *) ENCODE_REG_SUB(i, 0));
1359 * Initialize the DalvikToSSAMap map. The low 16 bit is the SSA register id,
1360 * while the high 16 bit is the current subscript. The original Dalvik
1361 * register N is mapped to SSA register N with subscript 0.
1363 cUnit->dalvikToSSAMap = dvmCompilerNew(sizeof(int) * numDalvikReg, false);
1364 for (i = 0; i < numDalvikReg; i++) {
1365 cUnit->dalvikToSSAMap[i] = i;
1369 * Allocate the BasicBlockDataFlow structure for the entry and code blocks
1371 for (i = 0; i < cUnit->numBlocks; i++) {
1372 BasicBlock *bb = cUnit->blockList[i];
1373 if (bb->blockType == DALVIK_BYTECODE ||
1374 bb->blockType == ENTRY_BLOCK) {
1375 bb->dataFlowInfo = dvmCompilerNew(sizeof(BasicBlockDataFlow), true);
1380 void dvmCompilerDataFlowAnalysisDispatcher(CompilationUnit *cUnit,
1381 void (*func)(CompilationUnit *, BasicBlock *))
1384 for (i = 0; i < cUnit->numBlocks; i++) {
1385 BasicBlock *bb = cUnit->blockList[i];
1390 /* Main entry point to do SSA conversion for non-loop traces */
1391 void dvmCompilerNonLoopAnalysis(CompilationUnit *cUnit)
1393 dvmCompilerDataFlowAnalysisDispatcher(cUnit, dvmCompilerDoSSAConversion);