| /* |
| * Copyright (C) 2011 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. |
| */ |
| |
| #include "Dalvik.h" |
| #include "Dataflow.h" |
| |
| namespace art { |
| |
| /* |
| * Main table containing data flow attributes for each bytecode. The |
| * first kNumPackedOpcodes entries are for Dalvik bytecode |
| * instructions, where extended opcode at the MIR level are appended |
| * afterwards. |
| * |
| * TODO - many optimization flags are incomplete - they will only limit the |
| * scope of optimizations but will not cause mis-optimizations. |
| */ |
| const int oatDataFlowAttributes[kMirOpLast] = { |
| // 00 NOP |
| DF_NOP, |
| |
| // 01 MOVE vA, vB |
| DF_DA | DF_UB | DF_IS_MOVE, |
| |
| // 02 MOVE_FROM16 vAA, vBBBB |
| DF_DA | DF_UB | DF_IS_MOVE, |
| |
| // 03 MOVE_16 vAAAA, vBBBB |
| DF_DA | DF_UB | DF_IS_MOVE, |
| |
| // 04 MOVE_WIDE vA, vB |
| DF_DA_WIDE | DF_UB_WIDE | DF_IS_MOVE, |
| |
| // 05 MOVE_WIDE_FROM16 vAA, vBBBB |
| DF_DA_WIDE | DF_UB_WIDE | DF_IS_MOVE, |
| |
| // 06 MOVE_WIDE_16 vAAAA, vBBBB |
| DF_DA_WIDE | DF_UB_WIDE | DF_IS_MOVE, |
| |
| // 07 MOVE_OBJECT vA, vB |
| DF_DA | DF_UB | DF_NULL_TRANSFER_0 | DF_IS_MOVE | DF_CORE_A | DF_CORE_B, |
| |
| // 08 MOVE_OBJECT_FROM16 vAA, vBBBB |
| DF_DA | DF_UB | DF_NULL_TRANSFER_0 | DF_IS_MOVE | DF_CORE_A | DF_CORE_B, |
| |
| // 09 MOVE_OBJECT_16 vAAAA, vBBBB |
| DF_DA | DF_UB | DF_NULL_TRANSFER_0 | DF_IS_MOVE | DF_CORE_A | DF_CORE_B, |
| |
| // 0A MOVE_RESULT vAA |
| DF_DA, |
| |
| // 0B MOVE_RESULT_WIDE vAA |
| DF_DA_WIDE, |
| |
| // 0C MOVE_RESULT_OBJECT vAA |
| DF_DA | DF_CORE_A, |
| |
| // 0D MOVE_EXCEPTION vAA |
| DF_DA | DF_CORE_A, |
| |
| // 0E RETURN_VOID |
| DF_NOP, |
| |
| // 0F RETURN vAA |
| DF_UA, |
| |
| // 10 RETURN_WIDE vAA |
| DF_UA_WIDE, |
| |
| // 11 RETURN_OBJECT vAA |
| DF_UA | DF_CORE_A, |
| |
| // 12 CONST_4 vA, #+B |
| DF_DA | DF_SETS_CONST, |
| |
| // 13 CONST_16 vAA, #+BBBB |
| DF_DA | DF_SETS_CONST, |
| |
| // 14 CONST vAA, #+BBBBBBBB |
| DF_DA | DF_SETS_CONST, |
| |
| // 15 CONST_HIGH16 VAA, #+BBBB0000 |
| DF_DA | DF_SETS_CONST, |
| |
| // 16 CONST_WIDE_16 vAA, #+BBBB |
| DF_DA_WIDE | DF_SETS_CONST, |
| |
| // 17 CONST_WIDE_32 vAA, #+BBBBBBBB |
| DF_DA_WIDE | DF_SETS_CONST, |
| |
| // 18 CONST_WIDE vAA, #+BBBBBBBBBBBBBBBB |
| DF_DA_WIDE | DF_SETS_CONST, |
| |
| // 19 CONST_WIDE_HIGH16 vAA, #+BBBB000000000000 |
| DF_DA_WIDE | DF_SETS_CONST, |
| |
| // 1A CONST_STRING vAA, string@BBBB |
| DF_DA | DF_CORE_A, |
| |
| // 1B CONST_STRING_JUMBO vAA, string@BBBBBBBB |
| DF_DA | DF_CORE_A, |
| |
| // 1C CONST_CLASS vAA, type@BBBB |
| DF_DA | DF_CORE_A, |
| |
| // 1D MONITOR_ENTER vAA |
| DF_UA | DF_NULL_CHK_0 | DF_CORE_A, |
| |
| // 1E MONITOR_EXIT vAA |
| DF_UA | DF_NULL_CHK_0 | DF_CORE_A, |
| |
| // 1F CHK_CAST vAA, type@BBBB |
| DF_UA | DF_CORE_A | DF_UMS, |
| |
| // 20 INSTANCE_OF vA, vB, type@CCCC |
| DF_DA | DF_UB | DF_CORE_A | DF_CORE_B | DF_UMS, |
| |
| // 21 ARRAY_LENGTH vA, vB |
| DF_DA | DF_UB | DF_NULL_CHK_0 | DF_CORE_A | DF_CORE_B, |
| |
| // 22 NEW_INSTANCE vAA, type@BBBB |
| DF_DA | DF_NON_NULL_DST | DF_CORE_A | DF_UMS, |
| |
| // 23 NEW_ARRAY vA, vB, type@CCCC |
| DF_DA | DF_UB | DF_NON_NULL_DST | DF_CORE_A | DF_CORE_B | DF_UMS, |
| |
| // 24 FILLED_NEW_ARRAY {vD, vE, vF, vG, vA} |
| DF_FORMAT_35C | DF_NON_NULL_RET | DF_UMS, |
| |
| // 25 FILLED_NEW_ARRAY_RANGE {vCCCC .. vNNNN}, type@BBBB |
| DF_FORMAT_3RC | DF_NON_NULL_RET | DF_UMS, |
| |
| // 26 FILL_ARRAY_DATA vAA, +BBBBBBBB |
| DF_UA | DF_CORE_A | DF_UMS, |
| |
| // 27 THROW vAA |
| DF_UA | DF_CORE_A | DF_UMS, |
| |
| // 28 GOTO |
| DF_NOP, |
| |
| // 29 GOTO_16 |
| DF_NOP, |
| |
| // 2A GOTO_32 |
| DF_NOP, |
| |
| // 2B PACKED_SWITCH vAA, +BBBBBBBB |
| DF_UA, |
| |
| // 2C SPARSE_SWITCH vAA, +BBBBBBBB |
| DF_UA, |
| |
| // 2D CMPL_FLOAT vAA, vBB, vCC |
| DF_DA | DF_UB | DF_UC | DF_FP_B | DF_FP_C | DF_CORE_A, |
| |
| // 2E CMPG_FLOAT vAA, vBB, vCC |
| DF_DA | DF_UB | DF_UC | DF_FP_B | DF_FP_C | DF_CORE_A, |
| |
| // 2F CMPL_DOUBLE vAA, vBB, vCC |
| DF_DA | DF_UB_WIDE | DF_UC_WIDE | DF_FP_B | DF_FP_C | DF_CORE_A, |
| |
| // 30 CMPG_DOUBLE vAA, vBB, vCC |
| DF_DA | DF_UB_WIDE | DF_UC_WIDE | DF_FP_B | DF_FP_C | DF_CORE_A, |
| |
| // 31 CMP_LONG vAA, vBB, vCC |
| DF_DA | DF_UB_WIDE | DF_UC_WIDE | DF_CORE_A | DF_CORE_B | DF_CORE_C, |
| |
| // 32 IF_EQ vA, vB, +CCCC |
| DF_UA | DF_UB | DF_CORE_A | DF_CORE_B, |
| |
| // 33 IF_NE vA, vB, +CCCC |
| DF_UA | DF_UB | DF_CORE_A | DF_CORE_B, |
| |
| // 34 IF_LT vA, vB, +CCCC |
| DF_UA | DF_UB | DF_CORE_A | DF_CORE_B, |
| |
| // 35 IF_GE vA, vB, +CCCC |
| DF_UA | DF_UB | DF_CORE_A | DF_CORE_B, |
| |
| // 36 IF_GT vA, vB, +CCCC |
| DF_UA | DF_UB | DF_CORE_A | DF_CORE_B, |
| |
| // 37 IF_LE vA, vB, +CCCC |
| DF_UA | DF_UB | DF_CORE_A | DF_CORE_B, |
| |
| |
| // 38 IF_EQZ vAA, +BBBB |
| DF_UA | DF_CORE_A, |
| |
| // 39 IF_NEZ vAA, +BBBB |
| DF_UA | DF_CORE_A, |
| |
| // 3A IF_LTZ vAA, +BBBB |
| DF_UA | DF_CORE_A, |
| |
| // 3B IF_GEZ vAA, +BBBB |
| DF_UA | DF_CORE_A, |
| |
| // 3C IF_GTZ vAA, +BBBB |
| DF_UA | DF_CORE_A, |
| |
| // 3D IF_LEZ vAA, +BBBB |
| DF_UA | DF_CORE_A, |
| |
| // 3E UNUSED_3E |
| DF_NOP, |
| |
| // 3F UNUSED_3F |
| DF_NOP, |
| |
| // 40 UNUSED_40 |
| DF_NOP, |
| |
| // 41 UNUSED_41 |
| DF_NOP, |
| |
| // 42 UNUSED_42 |
| DF_NOP, |
| |
| // 43 UNUSED_43 |
| DF_NOP, |
| |
| // 44 AGET vAA, vBB, vCC |
| DF_DA | DF_UB | DF_UC | DF_NULL_CHK_0 | DF_RANGE_CHK_1 | DF_CORE_B | DF_CORE_C, |
| |
| // 45 AGET_WIDE vAA, vBB, vCC |
| DF_DA_WIDE | DF_UB | DF_UC | DF_NULL_CHK_0 | DF_RANGE_CHK_1 | DF_CORE_B | DF_CORE_C, |
| |
| // 46 AGET_OBJECT vAA, vBB, vCC |
| DF_DA | DF_UB | DF_UC | DF_NULL_CHK_0 | DF_RANGE_CHK_1 | DF_CORE_B | DF_CORE_C, |
| |
| // 47 AGET_BOOLEAN vAA, vBB, vCC |
| DF_DA | DF_UB | DF_UC | DF_NULL_CHK_0 | DF_RANGE_CHK_1 | DF_CORE_B | DF_CORE_C, |
| |
| // 48 AGET_BYTE vAA, vBB, vCC |
| DF_DA | DF_UB | DF_UC | DF_NULL_CHK_0 | DF_RANGE_CHK_1 | DF_CORE_B | DF_CORE_C, |
| |
| // 49 AGET_CHAR vAA, vBB, vCC |
| DF_DA | DF_UB | DF_UC | DF_NULL_CHK_0 | DF_RANGE_CHK_1 | DF_CORE_B | DF_CORE_C, |
| |
| // 4A AGET_SHORT vAA, vBB, vCC |
| DF_DA | DF_UB | DF_UC | DF_NULL_CHK_0 | DF_RANGE_CHK_1 | DF_CORE_B | DF_CORE_C, |
| |
| // 4B APUT vAA, vBB, vCC |
| DF_UA | DF_UB | DF_UC | DF_NULL_CHK_1 | DF_RANGE_CHK_2 | DF_CORE_B | DF_CORE_C, |
| |
| // 4C APUT_WIDE vAA, vBB, vCC |
| DF_UA_WIDE | DF_UB | DF_UC | DF_NULL_CHK_2 | DF_RANGE_CHK_3 | DF_CORE_B | DF_CORE_C, |
| |
| // 4D APUT_OBJECT vAA, vBB, vCC |
| DF_UA | DF_UB | DF_UC | DF_NULL_CHK_1 | DF_RANGE_CHK_2 | DF_CORE_B | DF_CORE_C, |
| |
| // 4E APUT_BOOLEAN vAA, vBB, vCC |
| DF_UA | DF_UB | DF_UC | DF_NULL_CHK_1 | DF_RANGE_CHK_2 | DF_CORE_B | DF_CORE_C, |
| |
| // 4F APUT_BYTE vAA, vBB, vCC |
| DF_UA | DF_UB | DF_UC | DF_NULL_CHK_1 | DF_RANGE_CHK_2 | DF_CORE_B | DF_CORE_C, |
| |
| // 50 APUT_CHAR vAA, vBB, vCC |
| DF_UA | DF_UB | DF_UC | DF_NULL_CHK_1 | DF_RANGE_CHK_2 | DF_CORE_B | DF_CORE_C, |
| |
| // 51 APUT_SHORT vAA, vBB, vCC |
| DF_UA | DF_UB | DF_UC | DF_NULL_CHK_1 | DF_RANGE_CHK_2 | DF_CORE_B | DF_CORE_C, |
| |
| // 52 IGET vA, vB, field@CCCC |
| DF_DA | DF_UB | DF_NULL_CHK_0 | DF_CORE_B, |
| |
| // 53 IGET_WIDE vA, vB, field@CCCC |
| DF_DA_WIDE | DF_UB | DF_NULL_CHK_0 | DF_CORE_B, |
| |
| // 54 IGET_OBJECT vA, vB, field@CCCC |
| DF_DA | DF_UB | DF_NULL_CHK_0 | DF_CORE_B, |
| |
| // 55 IGET_BOOLEAN vA, vB, field@CCCC |
| DF_DA | DF_UB | DF_NULL_CHK_0 | DF_CORE_B, |
| |
| // 56 IGET_BYTE vA, vB, field@CCCC |
| DF_DA | DF_UB | DF_NULL_CHK_0 | DF_CORE_B, |
| |
| // 57 IGET_CHAR vA, vB, field@CCCC |
| DF_DA | DF_UB | DF_NULL_CHK_0 | DF_CORE_B, |
| |
| // 58 IGET_SHORT vA, vB, field@CCCC |
| DF_DA | DF_UB | DF_NULL_CHK_0 | DF_CORE_B, |
| |
| // 59 IPUT vA, vB, field@CCCC |
| DF_UA | DF_UB | DF_NULL_CHK_1 | DF_CORE_B, |
| |
| // 5A IPUT_WIDE vA, vB, field@CCCC |
| DF_UA_WIDE | DF_UB | DF_NULL_CHK_2 | DF_CORE_B, |
| |
| // 5B IPUT_OBJECT vA, vB, field@CCCC |
| DF_UA | DF_UB | DF_NULL_CHK_1 | DF_CORE_B, |
| |
| // 5C IPUT_BOOLEAN vA, vB, field@CCCC |
| DF_UA | DF_UB | DF_NULL_CHK_1 | DF_CORE_B, |
| |
| // 5D IPUT_BYTE vA, vB, field@CCCC |
| DF_UA | DF_UB | DF_NULL_CHK_1 | DF_CORE_B, |
| |
| // 5E IPUT_CHAR vA, vB, field@CCCC |
| DF_UA | DF_UB | DF_NULL_CHK_1 | DF_CORE_B, |
| |
| // 5F IPUT_SHORT vA, vB, field@CCCC |
| DF_UA | DF_UB | DF_NULL_CHK_1 | DF_CORE_B, |
| |
| // 60 SGET vAA, field@BBBB |
| DF_DA | DF_UMS, |
| |
| // 61 SGET_WIDE vAA, field@BBBB |
| DF_DA_WIDE | DF_UMS, |
| |
| // 62 SGET_OBJECT vAA, field@BBBB |
| DF_DA | DF_CORE_A | DF_UMS, |
| |
| // 63 SGET_BOOLEAN vAA, field@BBBB |
| DF_DA | DF_UMS, |
| |
| // 64 SGET_BYTE vAA, field@BBBB |
| DF_DA | DF_UMS, |
| |
| // 65 SGET_CHAR vAA, field@BBBB |
| DF_DA | DF_UMS, |
| |
| // 66 SGET_SHORT vAA, field@BBBB |
| DF_DA | DF_UMS, |
| |
| // 67 SPUT vAA, field@BBBB |
| DF_UA | DF_UMS, |
| |
| // 68 SPUT_WIDE vAA, field@BBBB |
| DF_UA_WIDE | DF_UMS, |
| |
| // 69 SPUT_OBJECT vAA, field@BBBB |
| DF_UA | DF_CORE_A | DF_UMS, |
| |
| // 6A SPUT_BOOLEAN vAA, field@BBBB |
| DF_UA | DF_UMS, |
| |
| // 6B SPUT_BYTE vAA, field@BBBB |
| DF_UA | DF_UMS, |
| |
| // 6C SPUT_CHAR vAA, field@BBBB |
| DF_UA | DF_UMS, |
| |
| // 6D SPUT_SHORT vAA, field@BBBB |
| DF_UA | DF_UMS, |
| |
| // 6E INVOKE_VIRTUAL {vD, vE, vF, vG, vA} |
| DF_FORMAT_35C | DF_NULL_CHK_OUT0 | DF_UMS, |
| |
| // 6F INVOKE_SUPER {vD, vE, vF, vG, vA} |
| DF_FORMAT_35C | DF_NULL_CHK_OUT0 | DF_UMS, |
| |
| // 70 INVOKE_DIRECT {vD, vE, vF, vG, vA} |
| DF_FORMAT_35C | DF_NULL_CHK_OUT0 | DF_UMS, |
| |
| // 71 INVOKE_STATIC {vD, vE, vF, vG, vA} |
| DF_FORMAT_35C | DF_UMS, |
| |
| // 72 INVOKE_INTERFACE {vD, vE, vF, vG, vA} |
| DF_FORMAT_35C | DF_UMS, |
| |
| // 73 UNUSED_73 |
| DF_NOP, |
| |
| // 74 INVOKE_VIRTUAL_RANGE {vCCCC .. vNNNN} |
| DF_FORMAT_3RC | DF_NULL_CHK_OUT0 | DF_UMS, |
| |
| // 75 INVOKE_SUPER_RANGE {vCCCC .. vNNNN} |
| DF_FORMAT_3RC | DF_NULL_CHK_OUT0 | DF_UMS, |
| |
| // 76 INVOKE_DIRECT_RANGE {vCCCC .. vNNNN} |
| DF_FORMAT_3RC | DF_NULL_CHK_OUT0 | DF_UMS, |
| |
| // 77 INVOKE_STATIC_RANGE {vCCCC .. vNNNN} |
| DF_FORMAT_3RC | DF_UMS, |
| |
| // 78 INVOKE_INTERFACE_RANGE {vCCCC .. vNNNN} |
| DF_FORMAT_3RC | DF_UMS, |
| |
| // 79 UNUSED_79 |
| DF_NOP, |
| |
| // 7A UNUSED_7A |
| DF_NOP, |
| |
| // 7B NEG_INT vA, vB |
| DF_DA | DF_UB | DF_CORE_A | DF_CORE_B, |
| |
| // 7C NOT_INT vA, vB |
| DF_DA | DF_UB | DF_CORE_A | DF_CORE_B, |
| |
| // 7D NEG_LONG vA, vB |
| DF_DA_WIDE | DF_UB_WIDE | DF_CORE_A | DF_CORE_B, |
| |
| // 7E NOT_LONG vA, vB |
| DF_DA_WIDE | DF_UB_WIDE | DF_CORE_A | DF_CORE_B, |
| |
| // 7F NEG_FLOAT vA, vB |
| DF_DA | DF_UB | DF_FP_A | DF_FP_B, |
| |
| // 80 NEG_DOUBLE vA, vB |
| DF_DA_WIDE | DF_UB_WIDE | DF_FP_A | DF_FP_B, |
| |
| // 81 INT_TO_LONG vA, vB |
| DF_DA_WIDE | DF_UB | DF_CORE_A | DF_CORE_B, |
| |
| // 82 INT_TO_FLOAT vA, vB |
| DF_DA | DF_UB | DF_FP_A | DF_CORE_B, |
| |
| // 83 INT_TO_DOUBLE vA, vB |
| DF_DA_WIDE | DF_UB | DF_FP_A | DF_CORE_B, |
| |
| // 84 LONG_TO_INT vA, vB |
| DF_DA | DF_UB_WIDE | DF_CORE_A | DF_CORE_B, |
| |
| // 85 LONG_TO_FLOAT vA, vB |
| DF_DA | DF_UB_WIDE | DF_FP_A | DF_CORE_B, |
| |
| // 86 LONG_TO_DOUBLE vA, vB |
| DF_DA_WIDE | DF_UB_WIDE | DF_FP_A | DF_CORE_B, |
| |
| // 87 FLOAT_TO_INT vA, vB |
| DF_DA | DF_UB | DF_FP_B | DF_CORE_A, |
| |
| // 88 FLOAT_TO_LONG vA, vB |
| DF_DA_WIDE | DF_UB | DF_FP_B | DF_CORE_A, |
| |
| // 89 FLOAT_TO_DOUBLE vA, vB |
| DF_DA_WIDE | DF_UB | DF_FP_A | DF_FP_B, |
| |
| // 8A DOUBLE_TO_INT vA, vB |
| DF_DA | DF_UB_WIDE | DF_FP_B | DF_CORE_A, |
| |
| // 8B DOUBLE_TO_LONG vA, vB |
| DF_DA_WIDE | DF_UB_WIDE | DF_FP_B | DF_CORE_A, |
| |
| // 8C DOUBLE_TO_FLOAT vA, vB |
| DF_DA | DF_UB_WIDE | DF_FP_A | DF_FP_B, |
| |
| // 8D INT_TO_BYTE vA, vB |
| DF_DA | DF_UB | DF_CORE_A | DF_CORE_B, |
| |
| // 8E INT_TO_CHAR vA, vB |
| DF_DA | DF_UB | DF_CORE_A | DF_CORE_B, |
| |
| // 8F INT_TO_SHORT vA, vB |
| DF_DA | DF_UB | DF_CORE_A | DF_CORE_B, |
| |
| // 90 ADD_INT vAA, vBB, vCC |
| DF_DA | DF_UB | DF_UC | DF_IS_LINEAR | DF_CORE_A | DF_CORE_B | DF_CORE_C, |
| |
| // 91 SUB_INT vAA, vBB, vCC |
| DF_DA | DF_UB | DF_UC | DF_IS_LINEAR | DF_CORE_A | DF_CORE_B | DF_CORE_C, |
| |
| // 92 MUL_INT vAA, vBB, vCC |
| DF_DA | DF_UB | DF_UC | DF_CORE_A | DF_CORE_B | DF_CORE_C, |
| |
| // 93 DIV_INT vAA, vBB, vCC |
| DF_DA | DF_UB | DF_UC | DF_CORE_A | DF_CORE_B | DF_CORE_C, |
| |
| // 94 REM_INT vAA, vBB, vCC |
| DF_DA | DF_UB | DF_UC | DF_CORE_A | DF_CORE_B | DF_CORE_C, |
| |
| // 95 AND_INT vAA, vBB, vCC |
| DF_DA | DF_UB | DF_UC | DF_CORE_A | DF_CORE_B | DF_CORE_C, |
| |
| // 96 OR_INT vAA, vBB, vCC |
| DF_DA | DF_UB | DF_UC | DF_CORE_A | DF_CORE_B | DF_CORE_C, |
| |
| // 97 XOR_INT vAA, vBB, vCC |
| DF_DA | DF_UB | DF_UC | DF_CORE_A | DF_CORE_B | DF_CORE_C, |
| |
| // 98 SHL_INT vAA, vBB, vCC |
| DF_DA | DF_UB | DF_UC | DF_CORE_A | DF_CORE_B | DF_CORE_C, |
| |
| // 99 SHR_INT vAA, vBB, vCC |
| DF_DA | DF_UB | DF_UC | DF_CORE_A | DF_CORE_B | DF_CORE_C, |
| |
| // 9A USHR_INT vAA, vBB, vCC |
| DF_DA | DF_UB | DF_UC | DF_CORE_A | DF_CORE_B | DF_CORE_C, |
| |
| // 9B ADD_LONG vAA, vBB, vCC |
| DF_DA_WIDE | DF_UB_WIDE | DF_UC_WIDE | DF_CORE_A | DF_CORE_B | DF_CORE_C, |
| |
| // 9C SUB_LONG vAA, vBB, vCC |
| DF_DA_WIDE | DF_UB_WIDE | DF_UC_WIDE | DF_CORE_A | DF_CORE_B | DF_CORE_C, |
| |
| // 9D MUL_LONG vAA, vBB, vCC |
| DF_DA_WIDE | DF_UB_WIDE | DF_UC_WIDE | DF_CORE_A | DF_CORE_B | DF_CORE_C, |
| |
| // 9E DIV_LONG vAA, vBB, vCC |
| DF_DA_WIDE | DF_UB_WIDE | DF_UC_WIDE | DF_CORE_A | DF_CORE_B | DF_CORE_C, |
| |
| // 9F REM_LONG vAA, vBB, vCC |
| DF_DA_WIDE | DF_UB_WIDE | DF_UC_WIDE | DF_CORE_A | DF_CORE_B | DF_CORE_C, |
| |
| // A0 AND_LONG vAA, vBB, vCC |
| DF_DA_WIDE | DF_UB_WIDE | DF_UC_WIDE | DF_CORE_A | DF_CORE_B | DF_CORE_C, |
| |
| // A1 OR_LONG vAA, vBB, vCC |
| DF_DA_WIDE | DF_UB_WIDE | DF_UC_WIDE | DF_CORE_A | DF_CORE_B | DF_CORE_C, |
| |
| // A2 XOR_LONG vAA, vBB, vCC |
| DF_DA_WIDE | DF_UB_WIDE | DF_UC_WIDE | DF_CORE_A | DF_CORE_B | DF_CORE_C, |
| |
| // A3 SHL_LONG vAA, vBB, vCC |
| DF_DA_WIDE | DF_UB_WIDE | DF_UC | DF_CORE_A | DF_CORE_B | DF_CORE_C, |
| |
| // A4 SHR_LONG vAA, vBB, vCC |
| DF_DA_WIDE | DF_UB_WIDE | DF_UC | DF_CORE_A | DF_CORE_B | DF_CORE_C, |
| |
| // A5 USHR_LONG vAA, vBB, vCC |
| DF_DA_WIDE | DF_UB_WIDE | DF_UC | DF_CORE_A | DF_CORE_B | DF_CORE_C, |
| |
| // A6 ADD_FLOAT vAA, vBB, vCC |
| DF_DA | DF_UB | DF_UC | DF_FP_A | DF_FP_B | DF_FP_C, |
| |
| // A7 SUB_FLOAT vAA, vBB, vCC |
| DF_DA | DF_UB | DF_UC | DF_FP_A | DF_FP_B | DF_FP_C, |
| |
| // A8 MUL_FLOAT vAA, vBB, vCC |
| DF_DA | DF_UB | DF_UC | DF_FP_A | DF_FP_B | DF_FP_C, |
| |
| // A9 DIV_FLOAT vAA, vBB, vCC |
| DF_DA | DF_UB | DF_UC | DF_FP_A | DF_FP_B | DF_FP_C, |
| |
| // AA REM_FLOAT vAA, vBB, vCC |
| DF_DA | DF_UB | DF_UC | DF_FP_A | DF_FP_B | DF_FP_C, |
| |
| // AB ADD_DOUBLE vAA, vBB, vCC |
| DF_DA_WIDE | DF_UB_WIDE | DF_UC_WIDE | DF_FP_A | DF_FP_B | DF_FP_C, |
| |
| // AC SUB_DOUBLE vAA, vBB, vCC |
| DF_DA_WIDE | DF_UB_WIDE | DF_UC_WIDE | DF_FP_A | DF_FP_B | DF_FP_C, |
| |
| // AD MUL_DOUBLE vAA, vBB, vCC |
| DF_DA_WIDE | DF_UB_WIDE | DF_UC_WIDE | DF_FP_A | DF_FP_B | DF_FP_C, |
| |
| // AE DIV_DOUBLE vAA, vBB, vCC |
| DF_DA_WIDE | DF_UB_WIDE | DF_UC_WIDE | DF_FP_A | DF_FP_B | DF_FP_C, |
| |
| // AF REM_DOUBLE vAA, vBB, vCC |
| DF_DA_WIDE | DF_UB_WIDE | DF_UC_WIDE | DF_FP_A | DF_FP_B | DF_FP_C, |
| |
| // B0 ADD_INT_2ADDR vA, vB |
| DF_DA | DF_UA | DF_UB | DF_CORE_A | DF_CORE_B, |
| |
| // B1 SUB_INT_2ADDR vA, vB |
| DF_DA | DF_UA | DF_UB | DF_CORE_A | DF_CORE_B, |
| |
| // B2 MUL_INT_2ADDR vA, vB |
| DF_DA | DF_UA | DF_UB | DF_CORE_A | DF_CORE_B, |
| |
| // B3 DIV_INT_2ADDR vA, vB |
| DF_DA | DF_UA | DF_UB | DF_CORE_A | DF_CORE_B, |
| |
| // B4 REM_INT_2ADDR vA, vB |
| DF_DA | DF_UA | DF_UB | DF_CORE_A | DF_CORE_B, |
| |
| // B5 AND_INT_2ADDR vA, vB |
| DF_DA | DF_UA | DF_UB | DF_CORE_A | DF_CORE_B, |
| |
| // B6 OR_INT_2ADDR vA, vB |
| DF_DA | DF_UA | DF_UB | DF_CORE_A | DF_CORE_B, |
| |
| // B7 XOR_INT_2ADDR vA, vB |
| DF_DA | DF_UA | DF_UB | DF_CORE_A | DF_CORE_B, |
| |
| // B8 SHL_INT_2ADDR vA, vB |
| DF_DA | DF_UA | DF_UB | DF_CORE_A | DF_CORE_B, |
| |
| // B9 SHR_INT_2ADDR vA, vB |
| DF_DA | DF_UA | DF_UB | DF_CORE_A | DF_CORE_B, |
| |
| // BA USHR_INT_2ADDR vA, vB |
| DF_DA | DF_UA | DF_UB | DF_CORE_A | DF_CORE_B, |
| |
| // BB ADD_LONG_2ADDR vA, vB |
| DF_DA_WIDE | DF_UA_WIDE | DF_UB_WIDE | DF_CORE_A | DF_CORE_B, |
| |
| // BC SUB_LONG_2ADDR vA, vB |
| DF_DA_WIDE | DF_UA_WIDE | DF_UB_WIDE | DF_CORE_A | DF_CORE_B, |
| |
| // BD MUL_LONG_2ADDR vA, vB |
| DF_DA_WIDE | DF_UA_WIDE | DF_UB_WIDE | DF_CORE_A | DF_CORE_B, |
| |
| // BE DIV_LONG_2ADDR vA, vB |
| DF_DA_WIDE | DF_UA_WIDE | DF_UB_WIDE | DF_CORE_A | DF_CORE_B, |
| |
| // BF REM_LONG_2ADDR vA, vB |
| DF_DA_WIDE | DF_UA_WIDE | DF_UB_WIDE | DF_CORE_A | DF_CORE_B, |
| |
| // C0 AND_LONG_2ADDR vA, vB |
| DF_DA_WIDE | DF_UA_WIDE | DF_UB_WIDE | DF_CORE_A | DF_CORE_B, |
| |
| // C1 OR_LONG_2ADDR vA, vB |
| DF_DA_WIDE | DF_UA_WIDE | DF_UB_WIDE | DF_CORE_A | DF_CORE_B, |
| |
| // C2 XOR_LONG_2ADDR vA, vB |
| DF_DA_WIDE | DF_UA_WIDE | DF_UB_WIDE | DF_CORE_A | DF_CORE_B, |
| |
| // C3 SHL_LONG_2ADDR vA, vB |
| DF_DA_WIDE | DF_UA_WIDE | DF_UB | DF_CORE_A | DF_CORE_B, |
| |
| // C4 SHR_LONG_2ADDR vA, vB |
| DF_DA_WIDE | DF_UA_WIDE | DF_UB | DF_CORE_A | DF_CORE_B, |
| |
| // C5 USHR_LONG_2ADDR vA, vB |
| DF_DA_WIDE | DF_UA_WIDE | DF_UB | DF_CORE_A | DF_CORE_B, |
| |
| // C6 ADD_FLOAT_2ADDR vA, vB |
| DF_DA | DF_UA | DF_UB | DF_FP_A | DF_FP_B, |
| |
| // C7 SUB_FLOAT_2ADDR vA, vB |
| DF_DA | DF_UA | DF_UB | DF_FP_A | DF_FP_B, |
| |
| // C8 MUL_FLOAT_2ADDR vA, vB |
| DF_DA | DF_UA | DF_UB | DF_FP_A | DF_FP_B, |
| |
| // C9 DIV_FLOAT_2ADDR vA, vB |
| DF_DA | DF_UA | DF_UB | DF_FP_A | DF_FP_B, |
| |
| // CA REM_FLOAT_2ADDR vA, vB |
| DF_DA | DF_UA | DF_UB | DF_FP_A | DF_FP_B, |
| |
| // CB ADD_DOUBLE_2ADDR vA, vB |
| DF_DA_WIDE | DF_UA_WIDE | DF_UB_WIDE | DF_FP_A | DF_FP_B, |
| |
| // CC SUB_DOUBLE_2ADDR vA, vB |
| DF_DA_WIDE | DF_UA_WIDE | DF_UB_WIDE | DF_FP_A | DF_FP_B, |
| |
| // CD MUL_DOUBLE_2ADDR vA, vB |
| DF_DA_WIDE | DF_UA_WIDE | DF_UB_WIDE | DF_FP_A | DF_FP_B, |
| |
| // CE DIV_DOUBLE_2ADDR vA, vB |
| DF_DA_WIDE | DF_UA_WIDE | DF_UB_WIDE | DF_FP_A | DF_FP_B, |
| |
| // CF REM_DOUBLE_2ADDR vA, vB |
| DF_DA_WIDE | DF_UA_WIDE | DF_UB_WIDE | DF_FP_A | DF_FP_B, |
| |
| // D0 ADD_INT_LIT16 vA, vB, #+CCCC |
| DF_DA | DF_UB | DF_CORE_A | DF_CORE_B, |
| |
| // D1 RSUB_INT vA, vB, #+CCCC |
| DF_DA | DF_UB | DF_CORE_A | DF_CORE_B, |
| |
| // D2 MUL_INT_LIT16 vA, vB, #+CCCC |
| DF_DA | DF_UB | DF_CORE_A | DF_CORE_B, |
| |
| // D3 DIV_INT_LIT16 vA, vB, #+CCCC |
| DF_DA | DF_UB | DF_CORE_A | DF_CORE_B, |
| |
| // D4 REM_INT_LIT16 vA, vB, #+CCCC |
| DF_DA | DF_UB | DF_CORE_A | DF_CORE_B, |
| |
| // D5 AND_INT_LIT16 vA, vB, #+CCCC |
| DF_DA | DF_UB | DF_CORE_A | DF_CORE_B, |
| |
| // D6 OR_INT_LIT16 vA, vB, #+CCCC |
| DF_DA | DF_UB | DF_CORE_A | DF_CORE_B, |
| |
| // D7 XOR_INT_LIT16 vA, vB, #+CCCC |
| DF_DA | DF_UB | DF_CORE_A | DF_CORE_B, |
| |
| // D8 ADD_INT_LIT8 vAA, vBB, #+CC |
| DF_DA | DF_UB | DF_IS_LINEAR | DF_CORE_A | DF_CORE_B, |
| |
| // D9 RSUB_INT_LIT8 vAA, vBB, #+CC |
| DF_DA | DF_UB | DF_CORE_A | DF_CORE_B, |
| |
| // DA MUL_INT_LIT8 vAA, vBB, #+CC |
| DF_DA | DF_UB | DF_CORE_A | DF_CORE_B, |
| |
| // DB DIV_INT_LIT8 vAA, vBB, #+CC |
| DF_DA | DF_UB | DF_CORE_A | DF_CORE_B, |
| |
| // DC REM_INT_LIT8 vAA, vBB, #+CC |
| DF_DA | DF_UB | DF_CORE_A | DF_CORE_B, |
| |
| // DD AND_INT_LIT8 vAA, vBB, #+CC |
| DF_DA | DF_UB | DF_CORE_A | DF_CORE_B, |
| |
| // DE OR_INT_LIT8 vAA, vBB, #+CC |
| DF_DA | DF_UB | DF_CORE_A | DF_CORE_B, |
| |
| // DF XOR_INT_LIT8 vAA, vBB, #+CC |
| DF_DA | DF_UB | DF_CORE_A | DF_CORE_B, |
| |
| // E0 SHL_INT_LIT8 vAA, vBB, #+CC |
| DF_DA | DF_UB | DF_CORE_A | DF_CORE_B, |
| |
| // E1 SHR_INT_LIT8 vAA, vBB, #+CC |
| DF_DA | DF_UB | DF_CORE_A | DF_CORE_B, |
| |
| // E2 USHR_INT_LIT8 vAA, vBB, #+CC |
| DF_DA | DF_UB | DF_CORE_A | DF_CORE_B, |
| |
| // E3 IGET_VOLATILE |
| DF_DA | DF_UB | DF_NULL_CHK_0 | DF_CORE_B, |
| |
| // E4 IPUT_VOLATILE |
| DF_UA | DF_UB | DF_NULL_CHK_1 | DF_CORE_B, |
| |
| // E5 SGET_VOLATILE |
| DF_DA | DF_UMS, |
| |
| // E6 SPUT_VOLATILE |
| DF_UA | DF_UMS, |
| |
| // E7 IGET_OBJECT_VOLATILE |
| DF_DA | DF_UB | DF_NULL_CHK_0 | DF_CORE_A | DF_CORE_B, |
| |
| // E8 IGET_WIDE_VOLATILE |
| DF_DA_WIDE | DF_UB | DF_NULL_CHK_0 | DF_CORE_B, |
| |
| // E9 IPUT_WIDE_VOLATILE |
| DF_UA_WIDE | DF_UB | DF_NULL_CHK_2 | DF_CORE_B, |
| |
| // EA SGET_WIDE_VOLATILE |
| DF_DA_WIDE | DF_UMS, |
| |
| // EB SPUT_WIDE_VOLATILE |
| DF_UA_WIDE | DF_UMS, |
| |
| // EC BREAKPOINT |
| DF_NOP, |
| |
| // ED THROW_VERIFICATION_ERROR |
| DF_NOP | DF_UMS, |
| |
| // EE EXECUTE_INLINE |
| DF_FORMAT_35C, |
| |
| // EF EXECUTE_INLINE_RANGE |
| DF_FORMAT_3RC, |
| |
| // F0 INVOKE_OBJECT_INIT_RANGE |
| DF_NOP | DF_NULL_CHK_0, |
| |
| // F1 RETURN_VOID_BARRIER |
| DF_NOP, |
| |
| // F2 IGET_QUICK |
| DF_DA | DF_UB | DF_NULL_CHK_0, |
| |
| // F3 IGET_WIDE_QUICK |
| DF_DA_WIDE | DF_UB | DF_NULL_CHK_0, |
| |
| // F4 IGET_OBJECT_QUICK |
| DF_DA | DF_UB | DF_NULL_CHK_0, |
| |
| // F5 IPUT_QUICK |
| DF_UA | DF_UB | DF_NULL_CHK_1, |
| |
| // F6 IPUT_WIDE_QUICK |
| DF_UA_WIDE | DF_UB | DF_NULL_CHK_2, |
| |
| // F7 IPUT_OBJECT_QUICK |
| DF_UA | DF_UB | DF_NULL_CHK_1, |
| |
| // F8 INVOKE_VIRTUAL_QUICK |
| DF_FORMAT_35C | DF_NULL_CHK_OUT0 | DF_UMS, |
| |
| // F9 INVOKE_VIRTUAL_QUICK_RANGE |
| DF_FORMAT_3RC | DF_NULL_CHK_OUT0 | DF_UMS, |
| |
| // FA INVOKE_SUPER_QUICK |
| DF_FORMAT_35C | DF_NULL_CHK_OUT0 | DF_UMS, |
| |
| // FB INVOKE_SUPER_QUICK_RANGE |
| DF_FORMAT_3RC | DF_NULL_CHK_OUT0 | DF_UMS, |
| |
| // FC IPUT_OBJECT_VOLATILE |
| DF_UA | DF_UB | DF_NULL_CHK_1 | DF_CORE_A | DF_CORE_B, |
| |
| // FD SGET_OBJECT_VOLATILE |
| DF_DA | DF_CORE_A | DF_UMS, |
| |
| // FE SPUT_OBJECT_VOLATILE |
| DF_UA | DF_CORE_A | DF_UMS, |
| |
| // FF UNUSED_FF |
| DF_NOP, |
| |
| // Beginning of extended MIR opcodes |
| // 100 MIR_PHI |
| DF_PHI | DF_DA | DF_NULL_TRANSFER_N, |
| |
| // 101 MIR_COPY |
| DF_DA | DF_UB | DF_IS_MOVE, |
| |
| // 102 MIR_FUSED_CMPL_FLOAT |
| DF_UA | DF_UB | DF_FP_A | DF_FP_B, |
| |
| // 103 MIR_FUSED_CMPG_FLOAT |
| DF_UA | DF_UB | DF_FP_A | DF_FP_B, |
| |
| // 104 MIR_FUSED_CMPL_DOUBLE |
| DF_UA_WIDE | DF_UB_WIDE | DF_FP_A | DF_FP_B, |
| |
| // 105 MIR_FUSED_CMPG_DOUBLE |
| DF_UA_WIDE | DF_UB_WIDE | DF_FP_A | DF_FP_B, |
| |
| // 106 MIR_FUSED_CMP_LONG |
| DF_UA_WIDE | DF_UB_WIDE | DF_CORE_A | DF_CORE_B, |
| |
| // 107 MIR_NOP |
| DF_NOP, |
| |
| // 108 MIR_NULL_RANGE_UP_CHECK |
| 0, |
| |
| // 109 MIR_NULL_RANGE_DOWN_CHECK |
| 0, |
| |
| // 110 MIR_LOWER_BOUND |
| 0, |
| }; |
| |
| /* Return the base virtual register for a SSA name */ |
| int SRegToVReg(const CompilationUnit* cUnit, int ssaReg) |
| { |
| DCHECK_LT(ssaReg, (int)cUnit->ssaBaseVRegs->numUsed); |
| return GET_ELEM_N(cUnit->ssaBaseVRegs, int, ssaReg); |
| } |
| |
| int SRegToSubscript(const CompilationUnit* cUnit, int ssaReg) |
| { |
| DCHECK(ssaReg < (int)cUnit->ssaSubscripts->numUsed); |
| return GET_ELEM_N(cUnit->ssaSubscripts, int, ssaReg); |
| } |
| |
| int getSSAUseCount(CompilationUnit* cUnit, int sReg) |
| { |
| DCHECK(sReg < (int)cUnit->rawUseCounts.numUsed); |
| return cUnit->rawUseCounts.elemList[sReg]; |
| } |
| |
| |
| char* oatGetDalvikDisassembly(CompilationUnit* cUnit, |
| const DecodedInstruction& insn, const char* note) |
| { |
| char buffer[256]; |
| Instruction::Code opcode = insn.opcode; |
| int dfAttributes = oatDataFlowAttributes[opcode]; |
| int flags; |
| char* ret; |
| |
| buffer[0] = 0; |
| if ((int)opcode >= (int)kMirOpFirst) { |
| if ((int)opcode == (int)kMirOpPhi) { |
| strcpy(buffer, "PHI"); |
| } else { |
| sprintf(buffer, "Opcode %#x", opcode); |
| } |
| flags = 0; |
| } else { |
| strcpy(buffer, Instruction::Name(opcode)); |
| flags = Instruction::Flags(opcode); |
| } |
| |
| if (note) |
| strcat(buffer, note); |
| |
| /* For branches, decode the instructions to print out the branch targets */ |
| if (flags & Instruction::kBranch) { |
| Instruction::Format dalvikFormat = Instruction::FormatOf(insn.opcode); |
| int offset = 0; |
| switch (dalvikFormat) { |
| case Instruction::k21t: |
| snprintf(buffer + strlen(buffer), 256, " v%d,", insn.vA); |
| offset = (int) insn.vB; |
| break; |
| case Instruction::k22t: |
| snprintf(buffer + strlen(buffer), 256, " v%d, v%d,", insn.vA, insn.vB); |
| offset = (int) insn.vC; |
| break; |
| case Instruction::k10t: |
| case Instruction::k20t: |
| case Instruction::k30t: |
| offset = (int) insn.vA; |
| break; |
| default: |
| LOG(FATAL) << "Unexpected branch format " << (int)dalvikFormat |
| << " / opcode " << (int)opcode; |
| } |
| snprintf(buffer + strlen(buffer), 256, " (%c%x)", |
| offset > 0 ? '+' : '-', |
| offset > 0 ? offset : -offset); |
| } else if (dfAttributes & DF_FORMAT_35C) { |
| unsigned int i; |
| for (i = 0; i < insn.vA; i++) { |
| if (i != 0) strcat(buffer, ","); |
| snprintf(buffer + strlen(buffer), 256, " v%d", insn.arg[i]); |
| } |
| } |
| else if (dfAttributes & DF_FORMAT_3RC) { |
| snprintf(buffer + strlen(buffer), 256, |
| " v%d..v%d", insn.vC, insn.vC + insn.vA - 1); |
| } |
| else { |
| if (dfAttributes & DF_A_IS_REG) { |
| snprintf(buffer + strlen(buffer), 256, " v%d", insn.vA); |
| } |
| if (dfAttributes & DF_B_IS_REG) { |
| snprintf(buffer + strlen(buffer), 256, ", v%d", insn.vB); |
| } |
| else if ((int)opcode < (int)kMirOpFirst) { |
| snprintf(buffer + strlen(buffer), 256, ", (#%d)", insn.vB); |
| } |
| if (dfAttributes & DF_C_IS_REG) { |
| snprintf(buffer + strlen(buffer), 256, ", v%d", insn.vC); |
| } |
| else if ((int)opcode < (int)kMirOpFirst) { |
| snprintf(buffer + strlen(buffer), 256, ", (#%d)", insn.vC); |
| } |
| } |
| int length = strlen(buffer) + 1; |
| ret = (char*)oatNew(cUnit, length, false, kAllocDFInfo); |
| memcpy(ret, buffer, length); |
| return ret; |
| } |
| |
| char* getSSAName(const CompilationUnit* cUnit, int ssaReg, char* name) |
| { |
| sprintf(name, "v%d_%d", SRegToVReg(cUnit, ssaReg), |
| SRegToSubscript(cUnit, ssaReg)); |
| return name; |
| } |
| |
| /* |
| * Dalvik instruction disassembler with optional SSA printing. |
| */ |
| char* oatFullDisassembler(CompilationUnit* cUnit, const MIR* mir) |
| { |
| char buffer[256]; |
| char operand0[32], operand1[32]; |
| const DecodedInstruction* insn = &mir->dalvikInsn; |
| Instruction::Code opcode = insn->opcode; |
| int dfAttributes = oatDataFlowAttributes[opcode]; |
| char* ret; |
| int length; |
| |
| buffer[0] = 0; |
| if (static_cast<int>(opcode) >= static_cast<int>(kMirOpFirst)) { |
| if (static_cast<int>(opcode) == static_cast<int>(kMirOpPhi)) { |
| snprintf(buffer, 256, "PHI %s = (%s", |
| getSSAName(cUnit, mir->ssaRep->defs[0], operand0), |
| getSSAName(cUnit, mir->ssaRep->uses[0], operand1)); |
| int i; |
| for (i = 1; i < mir->ssaRep->numUses; i++) { |
| snprintf(buffer + strlen(buffer), 256, ", %s", |
| getSSAName(cUnit, mir->ssaRep->uses[i], operand0)); |
| } |
| snprintf(buffer + strlen(buffer), 256, ")"); |
| } |
| else { |
| sprintf(buffer, "Opcode %#x", opcode); |
| } |
| goto done; |
| } else { |
| strcpy(buffer, Instruction::Name(opcode)); |
| } |
| |
| /* For branches, decode the instructions to print out the branch targets */ |
| if (Instruction::Flags(insn->opcode) & Instruction::kBranch) { |
| Instruction::Format dalvikFormat = Instruction::FormatOf(insn->opcode); |
| int delta = 0; |
| switch (dalvikFormat) { |
| case Instruction::k21t: |
| snprintf(buffer + strlen(buffer), 256, " %s, ", |
| getSSAName(cUnit, mir->ssaRep->uses[0], operand0)); |
| delta = (int) insn->vB; |
| break; |
| case Instruction::k22t: |
| snprintf(buffer + strlen(buffer), 256, " %s, %s, ", |
| getSSAName(cUnit, mir->ssaRep->uses[0], operand0), |
| getSSAName(cUnit, mir->ssaRep->uses[1], operand1)); |
| delta = (int) insn->vC; |
| break; |
| case Instruction::k10t: |
| case Instruction::k20t: |
| case Instruction::k30t: |
| delta = (int) insn->vA; |
| break; |
| default: |
| LOG(FATAL) << "Unexpected branch format: " << |
| (int)dalvikFormat; |
| } |
| snprintf(buffer + strlen(buffer), 256, " %04x", |
| mir->offset + delta); |
| } else if (dfAttributes & (DF_FORMAT_35C | DF_FORMAT_3RC)) { |
| unsigned int i; |
| for (i = 0; i < insn->vA; i++) { |
| if (i != 0) strcat(buffer, ","); |
| snprintf(buffer + strlen(buffer), 256, " %s", |
| getSSAName(cUnit, mir->ssaRep->uses[i], operand0)); |
| } |
| } else { |
| int udIdx; |
| if (mir->ssaRep->numDefs) { |
| |
| for (udIdx = 0; udIdx < mir->ssaRep->numDefs; udIdx++) { |
| snprintf(buffer + strlen(buffer), 256, " %s", |
| getSSAName(cUnit, mir->ssaRep->defs[udIdx], operand0)); |
| } |
| strcat(buffer, ","); |
| } |
| if (mir->ssaRep->numUses) { |
| /* No leading ',' for the first use */ |
| snprintf(buffer + strlen(buffer), 256, " %s", |
| getSSAName(cUnit, mir->ssaRep->uses[0], operand0)); |
| for (udIdx = 1; udIdx < mir->ssaRep->numUses; udIdx++) { |
| snprintf(buffer + strlen(buffer), 256, ", %s", |
| getSSAName(cUnit, mir->ssaRep->uses[udIdx], operand0)); |
| } |
| } |
| if (static_cast<int>(opcode) < static_cast<int>(kMirOpFirst)) { |
| Instruction::Format dalvikFormat = Instruction::FormatOf(opcode); |
| switch (dalvikFormat) { |
| case Instruction::k11n: // op vA, #+B |
| case Instruction::k21s: // op vAA, #+BBBB |
| case Instruction::k21h: // op vAA, #+BBBB00000[00000000] |
| case Instruction::k31i: // op vAA, #+BBBBBBBB |
| case Instruction::k51l: // op vAA, #+BBBBBBBBBBBBBBBB |
| snprintf(buffer + strlen(buffer), 256, " #%#x", insn->vB); |
| break; |
| case Instruction::k21c: // op vAA, thing@BBBB |
| case Instruction::k31c: // op vAA, thing@BBBBBBBB |
| snprintf(buffer + strlen(buffer), 256, " @%#x", insn->vB); |
| break; |
| case Instruction::k22b: // op vAA, vBB, #+CC |
| case Instruction::k22s: // op vA, vB, #+CCCC |
| snprintf(buffer + strlen(buffer), 256, " #%#x", insn->vC); |
| break; |
| case Instruction::k22c: // op vA, vB, thing@CCCC |
| snprintf(buffer + strlen(buffer), 256, " @%#x", insn->vC); |
| break; |
| /* No need for special printing */ |
| default: |
| break; |
| } |
| } |
| } |
| |
| done: |
| length = strlen(buffer) + 1; |
| ret = (char*) oatNew(cUnit, length, false, kAllocDFInfo); |
| memcpy(ret, buffer, length); |
| return ret; |
| } |
| |
| char* oatGetSSAString(CompilationUnit* cUnit, SSARepresentation* ssaRep) |
| { |
| char buffer[256]; |
| char* ret; |
| int i; |
| |
| buffer[0] = 0; |
| for (i = 0; i < ssaRep->numDefs; i++) { |
| int ssaReg = ssaRep->defs[i]; |
| sprintf(buffer + strlen(buffer), "s%d(v%d_%d) ", ssaReg, |
| SRegToVReg(cUnit, ssaReg), SRegToSubscript(cUnit, ssaReg)); |
| } |
| |
| if (ssaRep->numDefs) { |
| strcat(buffer, "<- "); |
| } |
| |
| for (i = 0; i < ssaRep->numUses; i++) { |
| int len = strlen(buffer); |
| int ssaReg = ssaRep->uses[i]; |
| |
| if (snprintf(buffer + len, 250 - len, "s%d(v%d_%d) ", ssaReg, |
| SRegToVReg(cUnit, ssaReg), |
| SRegToSubscript(cUnit, ssaReg))) { |
| strcat(buffer, "..."); |
| break; |
| } |
| } |
| |
| int length = strlen(buffer) + 1; |
| ret = (char*)oatNew(cUnit, length, false, kAllocDFInfo); |
| memcpy(ret, buffer, length); |
| return ret; |
| } |
| |
| /* Any register that is used before being defined is considered live-in */ |
| inline void handleLiveInUse(CompilationUnit* cUnit, ArenaBitVector* useV, |
| ArenaBitVector* defV, ArenaBitVector* liveInV, |
| int dalvikRegId) |
| { |
| oatSetBit(cUnit, useV, dalvikRegId); |
| if (!oatIsBitSet(defV, dalvikRegId)) { |
| oatSetBit(cUnit, liveInV, dalvikRegId); |
| } |
| } |
| |
| /* Mark a reg as being defined */ |
| inline void handleDef(CompilationUnit* cUnit, ArenaBitVector* defV, |
| int dalvikRegId) |
| { |
| oatSetBit(cUnit, defV, dalvikRegId); |
| } |
| |
| /* |
| * Find out live-in variables for natural loops. Variables that are live-in in |
| * the main loop body are considered to be defined in the entry block. |
| */ |
| bool oatFindLocalLiveIn(CompilationUnit* cUnit, BasicBlock* bb) |
| { |
| MIR* mir; |
| ArenaBitVector *useV, *defV, *liveInV; |
| |
| if (bb->dataFlowInfo == NULL) return false; |
| |
| useV = bb->dataFlowInfo->useV = |
| oatAllocBitVector(cUnit, cUnit->numDalvikRegisters, false, kBitMapUse); |
| defV = bb->dataFlowInfo->defV = |
| oatAllocBitVector(cUnit, cUnit->numDalvikRegisters, false, kBitMapDef); |
| liveInV = bb->dataFlowInfo->liveInV = |
| oatAllocBitVector(cUnit, cUnit->numDalvikRegisters, false, |
| kBitMapLiveIn); |
| |
| for (mir = bb->firstMIRInsn; mir; mir = mir->next) { |
| int dfAttributes = |
| oatDataFlowAttributes[mir->dalvikInsn.opcode]; |
| DecodedInstruction *dInsn = &mir->dalvikInsn; |
| |
| if (dfAttributes & DF_HAS_USES) { |
| if (dfAttributes & DF_UA) { |
| handleLiveInUse(cUnit, useV, defV, liveInV, dInsn->vA); |
| } else if (dfAttributes & DF_UA_WIDE) { |
| handleLiveInUse(cUnit, useV, defV, liveInV, dInsn->vA); |
| handleLiveInUse(cUnit, useV, defV, liveInV, dInsn->vA+1); |
| } |
| if (dfAttributes & DF_UB) { |
| handleLiveInUse(cUnit, useV, defV, liveInV, dInsn->vB); |
| } else if (dfAttributes & DF_UB_WIDE) { |
| handleLiveInUse(cUnit, useV, defV, liveInV, dInsn->vB); |
| handleLiveInUse(cUnit, useV, defV, liveInV, dInsn->vB+1); |
| } |
| if (dfAttributes & DF_UC) { |
| handleLiveInUse(cUnit, useV, defV, liveInV, dInsn->vC); |
| } else if (dfAttributes & DF_UC_WIDE) { |
| handleLiveInUse(cUnit, useV, defV, liveInV, dInsn->vC); |
| handleLiveInUse(cUnit, useV, defV, liveInV, dInsn->vC+1); |
| } |
| } |
| if (dfAttributes & DF_FORMAT_35C) { |
| for (unsigned int i = 0; i < dInsn->vA; i++) { |
| handleLiveInUse(cUnit, useV, defV, liveInV, dInsn->arg[i]); |
| } |
| } |
| if (dfAttributes & DF_FORMAT_3RC) { |
| for (unsigned int i = 0; i < dInsn->vA; i++) { |
| handleLiveInUse(cUnit, useV, defV, liveInV, dInsn->vC+i); |
| } |
| } |
| if (dfAttributes & DF_HAS_DEFS) { |
| handleDef(cUnit, defV, dInsn->vA); |
| if (dfAttributes & DF_DA_WIDE) { |
| handleDef(cUnit, defV, dInsn->vA+1); |
| } |
| } |
| } |
| return true; |
| } |
| |
| int addNewSReg(CompilationUnit* cUnit, int vReg) |
| { |
| // Compiler temps always have a subscript of 0 |
| int subscript = (vReg < 0) ? 0 : ++cUnit->SSALastDefs[vReg]; |
| int ssaReg = cUnit->numSSARegs++; |
| oatInsertGrowableList(cUnit, cUnit->ssaBaseVRegs, vReg); |
| oatInsertGrowableList(cUnit, cUnit->ssaSubscripts, subscript); |
| DCHECK_EQ(cUnit->ssaBaseVRegs->numUsed, cUnit->ssaSubscripts->numUsed); |
| return ssaReg; |
| } |
| |
| /* Find out the latest SSA register for a given Dalvik register */ |
| void handleSSAUse(CompilationUnit* cUnit, int* uses, int dalvikReg, |
| int regIndex) |
| { |
| DCHECK((dalvikReg >= 0) && (dalvikReg < cUnit->numDalvikRegisters)); |
| uses[regIndex] = cUnit->vRegToSSAMap[dalvikReg]; |
| } |
| |
| /* Setup a new SSA register for a given Dalvik register */ |
| void handleSSADef(CompilationUnit* cUnit, int* defs, int dalvikReg, |
| int regIndex) |
| { |
| DCHECK((dalvikReg >= 0) && (dalvikReg < cUnit->numDalvikRegisters)); |
| int ssaReg = addNewSReg(cUnit, dalvikReg); |
| cUnit->vRegToSSAMap[dalvikReg] = ssaReg; |
| defs[regIndex] = ssaReg; |
| } |
| |
| /* Look up new SSA names for format_35c instructions */ |
| void dataFlowSSAFormat35C(CompilationUnit* cUnit, MIR* mir) |
| { |
| DecodedInstruction *dInsn = &mir->dalvikInsn; |
| int numUses = dInsn->vA; |
| int i; |
| |
| mir->ssaRep->numUses = numUses; |
| mir->ssaRep->uses = (int *)oatNew(cUnit, sizeof(int) * numUses, true, |
| kAllocDFInfo); |
| // NOTE: will be filled in during type & size inference pass |
| mir->ssaRep->fpUse = (bool *)oatNew(cUnit, sizeof(bool) * numUses, true, |
| kAllocDFInfo); |
| |
| for (i = 0; i < numUses; i++) { |
| handleSSAUse(cUnit, mir->ssaRep->uses, dInsn->arg[i], i); |
| } |
| } |
| |
| /* Look up new SSA names for format_3rc instructions */ |
| void dataFlowSSAFormat3RC(CompilationUnit* cUnit, MIR* mir) |
| { |
| DecodedInstruction *dInsn = &mir->dalvikInsn; |
| int numUses = dInsn->vA; |
| int i; |
| |
| mir->ssaRep->numUses = numUses; |
| mir->ssaRep->uses = (int *)oatNew(cUnit, sizeof(int) * numUses, true, |
| kAllocDFInfo); |
| // NOTE: will be filled in during type & size inference pass |
| mir->ssaRep->fpUse = (bool *)oatNew(cUnit, sizeof(bool) * numUses, true, |
| kAllocDFInfo); |
| |
| for (i = 0; i < numUses; i++) { |
| handleSSAUse(cUnit, mir->ssaRep->uses, dInsn->vC+i, i); |
| } |
| } |
| |
| /* Entry function to convert a block into SSA representation */ |
| bool oatDoSSAConversion(CompilationUnit* cUnit, BasicBlock* bb) |
| { |
| MIR* mir; |
| |
| if (bb->dataFlowInfo == NULL) return false; |
| |
| for (mir = bb->firstMIRInsn; mir; mir = mir->next) { |
| mir->ssaRep = (struct SSARepresentation *) |
| oatNew(cUnit, sizeof(SSARepresentation), true, kAllocDFInfo); |
| |
| int dfAttributes = |
| oatDataFlowAttributes[mir->dalvikInsn.opcode]; |
| |
| // If not a pseudo-op, note non-leaf or can throw |
| if (static_cast<int>(mir->dalvikInsn.opcode) < static_cast<int>(kNumPackedOpcodes)) { |
| int flags = Instruction::Flags(mir->dalvikInsn.opcode); |
| |
| if (flags & Instruction::kThrow) { |
| cUnit->attrs &= ~METHOD_IS_THROW_FREE; |
| } |
| |
| if (flags & Instruction::kInvoke) { |
| cUnit->attrs &= ~METHOD_IS_LEAF; |
| } |
| } |
| |
| int numUses = 0; |
| |
| if (dfAttributes & DF_FORMAT_35C) { |
| dataFlowSSAFormat35C(cUnit, mir); |
| continue; |
| } |
| |
| if (dfAttributes & DF_FORMAT_3RC) { |
| dataFlowSSAFormat3RC(cUnit, mir); |
| continue; |
| } |
| |
| if (dfAttributes & DF_HAS_USES) { |
| if (dfAttributes & DF_UA) { |
| numUses++; |
| } else if (dfAttributes & DF_UA_WIDE) { |
| numUses += 2; |
| } |
| if (dfAttributes & DF_UB) { |
| numUses++; |
| } else if (dfAttributes & DF_UB_WIDE) { |
| numUses += 2; |
| } |
| if (dfAttributes & DF_UC) { |
| numUses++; |
| } else if (dfAttributes & DF_UC_WIDE) { |
| numUses += 2; |
| } |
| } |
| |
| if (numUses) { |
| mir->ssaRep->numUses = numUses; |
| mir->ssaRep->uses = (int *)oatNew(cUnit, sizeof(int) * numUses, |
| false, kAllocDFInfo); |
| mir->ssaRep->fpUse = (bool *)oatNew(cUnit, sizeof(bool) * numUses, |
| false, kAllocDFInfo); |
| } |
| |
| int numDefs = 0; |
| |
| if (dfAttributes & DF_HAS_DEFS) { |
| numDefs++; |
| if (dfAttributes & DF_DA_WIDE) { |
| numDefs++; |
| } |
| } |
| |
| if (numDefs) { |
| mir->ssaRep->numDefs = numDefs; |
| mir->ssaRep->defs = (int *)oatNew(cUnit, sizeof(int) * numDefs, |
| false, kAllocDFInfo); |
| mir->ssaRep->fpDef = (bool *)oatNew(cUnit, sizeof(bool) * numDefs, |
| false, kAllocDFInfo); |
| } |
| |
| DecodedInstruction *dInsn = &mir->dalvikInsn; |
| |
| if (dfAttributes & DF_HAS_USES) { |
| numUses = 0; |
| if (dfAttributes & DF_UA) { |
| mir->ssaRep->fpUse[numUses] = dfAttributes & DF_FP_A; |
| handleSSAUse(cUnit, mir->ssaRep->uses, dInsn->vA, numUses++); |
| } else if (dfAttributes & DF_UA_WIDE) { |
| mir->ssaRep->fpUse[numUses] = dfAttributes & DF_FP_A; |
| handleSSAUse(cUnit, mir->ssaRep->uses, dInsn->vA, numUses++); |
| mir->ssaRep->fpUse[numUses] = dfAttributes & DF_FP_A; |
| handleSSAUse(cUnit, mir->ssaRep->uses, dInsn->vA+1, numUses++); |
| } |
| if (dfAttributes & DF_UB) { |
| mir->ssaRep->fpUse[numUses] = dfAttributes & DF_FP_B; |
| handleSSAUse(cUnit, mir->ssaRep->uses, dInsn->vB, numUses++); |
| } else if (dfAttributes & DF_UB_WIDE) { |
| mir->ssaRep->fpUse[numUses] = dfAttributes & DF_FP_B; |
| handleSSAUse(cUnit, mir->ssaRep->uses, dInsn->vB, numUses++); |
| mir->ssaRep->fpUse[numUses] = dfAttributes & DF_FP_B; |
| handleSSAUse(cUnit, mir->ssaRep->uses, dInsn->vB+1, numUses++); |
| } |
| if (dfAttributes & DF_UC) { |
| mir->ssaRep->fpUse[numUses] = dfAttributes & DF_FP_C; |
| handleSSAUse(cUnit, mir->ssaRep->uses, dInsn->vC, numUses++); |
| } else if (dfAttributes & DF_UC_WIDE) { |
| mir->ssaRep->fpUse[numUses] = dfAttributes & DF_FP_C; |
| handleSSAUse(cUnit, mir->ssaRep->uses, dInsn->vC, numUses++); |
| mir->ssaRep->fpUse[numUses] = dfAttributes & DF_FP_C; |
| handleSSAUse(cUnit, mir->ssaRep->uses, dInsn->vC+1, numUses++); |
| } |
| } |
| if (dfAttributes & DF_HAS_DEFS) { |
| mir->ssaRep->fpDef[0] = dfAttributes & DF_FP_A; |
| handleSSADef(cUnit, mir->ssaRep->defs, dInsn->vA, 0); |
| if (dfAttributes & DF_DA_WIDE) { |
| mir->ssaRep->fpDef[1] = dfAttributes & DF_FP_A; |
| handleSSADef(cUnit, mir->ssaRep->defs, dInsn->vA+1, 1); |
| } |
| } |
| } |
| |
| if (!cUnit->disableDataflow) { |
| /* |
| * Take a snapshot of Dalvik->SSA mapping at the end of each block. The |
| * input to PHI nodes can be derived from the snapshot of all |
| * predecessor blocks. |
| */ |
| bb->dataFlowInfo->vRegToSSAMap = |
| (int *)oatNew(cUnit, sizeof(int) * cUnit->numDalvikRegisters, false, |
| kAllocDFInfo); |
| |
| memcpy(bb->dataFlowInfo->vRegToSSAMap, cUnit->vRegToSSAMap, |
| sizeof(int) * cUnit->numDalvikRegisters); |
| } |
| return true; |
| } |
| |
| /* Setup a constant value for opcodes thare have the DF_SETS_CONST attribute */ |
| void setConstant(CompilationUnit* cUnit, int ssaReg, int value) |
| { |
| oatSetBit(cUnit, cUnit->isConstantV, ssaReg); |
| cUnit->constantValues[ssaReg] = value; |
| } |
| |
| bool oatDoConstantPropagation(CompilationUnit* cUnit, BasicBlock* bb) |
| { |
| MIR* mir; |
| ArenaBitVector *isConstantV = cUnit->isConstantV; |
| |
| for (mir = bb->firstMIRInsn; mir; mir = mir->next) { |
| int dfAttributes = |
| oatDataFlowAttributes[mir->dalvikInsn.opcode]; |
| |
| DecodedInstruction *dInsn = &mir->dalvikInsn; |
| |
| if (!(dfAttributes & DF_HAS_DEFS)) continue; |
| |
| /* Handle instructions that set up constants directly */ |
| if (dfAttributes & DF_SETS_CONST) { |
| if (dfAttributes & DF_DA) { |
| switch (dInsn->opcode) { |
| case Instruction::CONST_4: |
| case Instruction::CONST_16: |
| case Instruction::CONST: |
| setConstant(cUnit, mir->ssaRep->defs[0], dInsn->vB); |
| break; |
| case Instruction::CONST_HIGH16: |
| setConstant(cUnit, mir->ssaRep->defs[0], |
| dInsn->vB << 16); |
| break; |
| default: |
| break; |
| } |
| } else if (dfAttributes & DF_DA_WIDE) { |
| switch (dInsn->opcode) { |
| case Instruction::CONST_WIDE_16: |
| case Instruction::CONST_WIDE_32: |
| setConstant(cUnit, mir->ssaRep->defs[0], dInsn->vB); |
| setConstant(cUnit, mir->ssaRep->defs[1], 0); |
| break; |
| case Instruction::CONST_WIDE: |
| setConstant(cUnit, mir->ssaRep->defs[0], |
| (int) dInsn->vB_wide); |
| setConstant(cUnit, mir->ssaRep->defs[1], |
| (int) (dInsn->vB_wide >> 32)); |
| break; |
| case Instruction::CONST_WIDE_HIGH16: |
| setConstant(cUnit, mir->ssaRep->defs[0], 0); |
| setConstant(cUnit, mir->ssaRep->defs[1], |
| dInsn->vB << 16); |
| break; |
| default: |
| break; |
| } |
| } |
| /* Handle instructions that set up constants directly */ |
| } else if (dfAttributes & DF_IS_MOVE) { |
| int i; |
| |
| for (i = 0; i < mir->ssaRep->numUses; i++) { |
| if (!oatIsBitSet(isConstantV, mir->ssaRep->uses[i])) break; |
| } |
| /* Move a register holding a constant to another register */ |
| if (i == mir->ssaRep->numUses) { |
| setConstant(cUnit, mir->ssaRep->defs[0], |
| cUnit->constantValues[mir->ssaRep->uses[0]]); |
| if (dfAttributes & DF_DA_WIDE) { |
| setConstant(cUnit, mir->ssaRep->defs[1], |
| cUnit->constantValues[mir->ssaRep->uses[1]]); |
| } |
| } |
| } |
| } |
| /* TODO: implement code to handle arithmetic operations */ |
| return true; |
| } |
| |
| /* Setup the basic data structures for SSA conversion */ |
| void oatInitializeSSAConversion(CompilationUnit* cUnit) |
| { |
| int i; |
| int numDalvikReg = cUnit->numDalvikRegisters; |
| |
| cUnit->ssaBaseVRegs = (GrowableList *)oatNew(cUnit, sizeof(GrowableList), |
| false, kAllocDFInfo); |
| cUnit->ssaSubscripts = (GrowableList *)oatNew(cUnit, sizeof(GrowableList), |
| false, kAllocDFInfo); |
| // Create the ssa mappings, estimating the max size |
| oatInitGrowableList(cUnit, cUnit->ssaBaseVRegs, |
| numDalvikReg + cUnit->defCount + 128, |
| kListSSAtoDalvikMap); |
| oatInitGrowableList(cUnit, cUnit->ssaSubscripts, |
| numDalvikReg + cUnit->defCount + 128, |
| kListSSAtoDalvikMap); |
| /* |
| * Initial number of SSA registers is equal to the number of Dalvik |
| * registers. |
| */ |
| cUnit->numSSARegs = numDalvikReg; |
| |
| /* |
| * Initialize the SSA2Dalvik map list. For the first numDalvikReg elements, |
| * the subscript is 0 so we use the ENCODE_REG_SUB macro to encode the value |
| * into "(0 << 16) | i" |
| */ |
| for (i = 0; i < numDalvikReg; i++) { |
| oatInsertGrowableList(cUnit, cUnit->ssaBaseVRegs, i); |
| oatInsertGrowableList(cUnit, cUnit->ssaSubscripts, 0); |
| } |
| |
| /* |
| * Initialize the DalvikToSSAMap map. There is one entry for each |
| * Dalvik register, and the SSA names for those are the same. |
| */ |
| cUnit->vRegToSSAMap = (int *)oatNew(cUnit, sizeof(int) * numDalvikReg, |
| false, kAllocDFInfo); |
| /* Keep track of the higest def for each dalvik reg */ |
| cUnit->SSALastDefs = (int *)oatNew(cUnit, sizeof(int) * numDalvikReg, |
| false, kAllocDFInfo); |
| |
| for (i = 0; i < numDalvikReg; i++) { |
| cUnit->vRegToSSAMap[i] = i; |
| cUnit->SSALastDefs[i] = 0; |
| } |
| |
| /* Add ssa reg for Method* */ |
| cUnit->methodSReg = addNewSReg(cUnit, SSA_METHOD_BASEREG); |
| |
| /* |
| * Allocate the BasicBlockDataFlow structure for the entry and code blocks |
| */ |
| GrowableListIterator iterator; |
| |
| oatGrowableListIteratorInit(&cUnit->blockList, &iterator); |
| |
| while (true) { |
| BasicBlock* bb = (BasicBlock *) oatGrowableListIteratorNext(&iterator); |
| if (bb == NULL) break; |
| if (bb->hidden == true) continue; |
| if (bb->blockType == kDalvikByteCode || |
| bb->blockType == kEntryBlock || |
| bb->blockType == kExitBlock) { |
| bb->dataFlowInfo = (BasicBlockDataFlow *) |
| oatNew(cUnit, sizeof(BasicBlockDataFlow), |
| true, kAllocDFInfo); |
| } |
| } |
| } |
| |
| /* Clear the visited flag for each BB */ |
| bool oatClearVisitedFlag(struct CompilationUnit* cUnit, struct BasicBlock* bb) |
| { |
| bb->visited = false; |
| return true; |
| } |
| |
| void oatDataFlowAnalysisDispatcher(CompilationUnit* cUnit, |
| bool (*func)(CompilationUnit*, BasicBlock*), |
| DataFlowAnalysisMode dfaMode, |
| bool isIterative) |
| { |
| bool change = true; |
| |
| while (change) { |
| change = false; |
| |
| switch (dfaMode) { |
| /* Scan all blocks and perform the operations specified in func */ |
| case kAllNodes: |
| { |
| GrowableListIterator iterator; |
| oatGrowableListIteratorInit(&cUnit->blockList, &iterator); |
| while (true) { |
| BasicBlock* bb = |
| (BasicBlock *) oatGrowableListIteratorNext(&iterator); |
| if (bb == NULL) break; |
| if (bb->hidden == true) continue; |
| change |= (*func)(cUnit, bb); |
| } |
| } |
| break; |
| /* Scan reachable blocks and perform the ops specified in func. */ |
| case kReachableNodes: |
| { |
| int numReachableBlocks = cUnit->numReachableBlocks; |
| int idx; |
| const GrowableList *blockList = &cUnit->blockList; |
| |
| for (idx = 0; idx < numReachableBlocks; idx++) { |
| int blockIdx = cUnit->dfsOrder.elemList[idx]; |
| BasicBlock* bb = |
| (BasicBlock *) oatGrowableListGetElement(blockList, |
| blockIdx); |
| change |= (*func)(cUnit, bb); |
| } |
| } |
| break; |
| |
| /* Scan reachable blocks by pre-order dfs and invoke func on each. */ |
| case kPreOrderDFSTraversal: |
| { |
| int numReachableBlocks = cUnit->numReachableBlocks; |
| int idx; |
| const GrowableList *blockList = &cUnit->blockList; |
| |
| for (idx = 0; idx < numReachableBlocks; idx++) { |
| int dfsIdx = cUnit->dfsOrder.elemList[idx]; |
| BasicBlock* bb = |
| (BasicBlock *) oatGrowableListGetElement(blockList, |
| dfsIdx); |
| change |= (*func)(cUnit, bb); |
| } |
| } |
| break; |
| /* Scan reachable blocks post-order dfs and invoke func on each. */ |
| case kPostOrderDFSTraversal: |
| { |
| int numReachableBlocks = cUnit->numReachableBlocks; |
| int idx; |
| const GrowableList *blockList = &cUnit->blockList; |
| |
| for (idx = numReachableBlocks - 1; idx >= 0; idx--) { |
| int dfsIdx = cUnit->dfsOrder.elemList[idx]; |
| BasicBlock* bb = |
| (BasicBlock *) oatGrowableListGetElement(blockList, |
| dfsIdx); |
| change |= (*func)(cUnit, bb); |
| } |
| } |
| break; |
| /* Scan reachable post-order dom tree and invoke func on each. */ |
| case kPostOrderDOMTraversal: |
| { |
| int numReachableBlocks = cUnit->numReachableBlocks; |
| int idx; |
| const GrowableList *blockList = &cUnit->blockList; |
| |
| for (idx = 0; idx < numReachableBlocks; idx++) { |
| int domIdx = cUnit->domPostOrderTraversal.elemList[idx]; |
| BasicBlock* bb = |
| (BasicBlock *) oatGrowableListGetElement(blockList, |
| domIdx); |
| change |= (*func)(cUnit, bb); |
| } |
| } |
| break; |
| /* Scan reachable blocks reverse post-order dfs, invoke func on each */ |
| case kReversePostOrderTraversal: |
| { |
| int numReachableBlocks = cUnit->numReachableBlocks; |
| int idx; |
| const GrowableList *blockList = &cUnit->blockList; |
| |
| for (idx = numReachableBlocks - 1; idx >= 0; idx--) { |
| int revIdx = cUnit->dfsPostOrder.elemList[idx]; |
| BasicBlock* bb = |
| (BasicBlock *) oatGrowableListGetElement(blockList, |
| revIdx); |
| change |= (*func)(cUnit, bb); |
| } |
| } |
| break; |
| default: |
| LOG(FATAL) << "Unknown traversal mode " << (int)dfaMode; |
| } |
| /* If isIterative is false, exit the loop after the first iteration */ |
| change &= isIterative; |
| } |
| } |
| |
| /* Advance to next strictly dominated MIR node in an extended basic block */ |
| MIR* advanceMIR(CompilationUnit* cUnit, BasicBlock** pBb, MIR* mir, ArenaBitVector* bv, |
| bool clearMark) { |
| BasicBlock* bb = *pBb; |
| if (mir != NULL) { |
| mir = mir->next; |
| if (mir == NULL) { |
| bb = bb->fallThrough; |
| if ((bb == NULL) || bb->predecessors->numUsed != 1) { |
| mir = NULL; |
| } else { |
| if (bv) { |
| oatSetBit(cUnit, bv, bb->id); |
| } |
| *pBb = bb; |
| mir = bb->firstMIRInsn; |
| } |
| } |
| } |
| if (mir && clearMark) { |
| mir->optimizationFlags &= ~MIR_MARK; |
| } |
| return mir; |
| } |
| |
| /* |
| * To be used at an invoke mir. If the logically next mir node represents |
| * a move-result, return it. Else, return NULL. If a move-result exists, |
| * it is required to immediately follow the invoke with no intervening |
| * opcodes or incoming arcs. However, if the result of the invoke is not |
| * used, a move-result may not be present. |
| */ |
| MIR* oatFindMoveResult(CompilationUnit* cUnit, BasicBlock* bb, MIR* mir, |
| bool wide) |
| { |
| BasicBlock* tbb = bb; |
| mir = advanceMIR(cUnit, &tbb, mir, NULL, false); |
| while (mir != NULL) { |
| if (!wide && mir->dalvikInsn.opcode == Instruction::MOVE_RESULT) { |
| break; |
| } |
| if (wide && mir->dalvikInsn.opcode == Instruction::MOVE_RESULT_WIDE) { |
| break; |
| } |
| // Keep going if pseudo op, otherwise terminate |
| if (mir->dalvikInsn.opcode < static_cast<Instruction::Code>(kNumPackedOpcodes)) { |
| mir = NULL; |
| } else { |
| mir = advanceMIR(cUnit, &tbb, mir, NULL, false); |
| } |
| } |
| return mir; |
| } |
| |
| void squashDupRangeChecks(CompilationUnit* cUnit, BasicBlock** pBp, MIR* mir, |
| int arraySreg, int indexSreg) |
| { |
| while (true) { |
| mir = advanceMIR(cUnit, pBp, mir, NULL, false); |
| if (!mir) { |
| break; |
| } |
| if ((mir->ssaRep == NULL) || |
| (mir->optimizationFlags & MIR_IGNORE_RANGE_CHECK)) { |
| continue; |
| } |
| int checkArray = INVALID_SREG; |
| int checkIndex = INVALID_SREG; |
| switch (mir->dalvikInsn.opcode) { |
| case Instruction::AGET: |
| case Instruction::AGET_OBJECT: |
| case Instruction::AGET_BOOLEAN: |
| case Instruction::AGET_BYTE: |
| case Instruction::AGET_CHAR: |
| case Instruction::AGET_SHORT: |
| case Instruction::AGET_WIDE: |
| checkArray = mir->ssaRep->uses[0]; |
| checkIndex = mir->ssaRep->uses[1]; |
| break; |
| break; |
| case Instruction::APUT: |
| case Instruction::APUT_OBJECT: |
| case Instruction::APUT_SHORT: |
| case Instruction::APUT_CHAR: |
| case Instruction::APUT_BYTE: |
| case Instruction::APUT_BOOLEAN: |
| checkArray = mir->ssaRep->uses[1]; |
| checkIndex = mir->ssaRep->uses[2]; |
| break; |
| case Instruction::APUT_WIDE: |
| checkArray = mir->ssaRep->uses[2]; |
| checkIndex = mir->ssaRep->uses[3]; |
| default: |
| break; |
| } |
| if (checkArray == INVALID_SREG) { |
| continue; |
| } |
| if ((arraySreg == checkArray) && (indexSreg == checkIndex)) { |
| if (cUnit->printMe) { |
| LOG(INFO) << "Squashing range check @ 0x" << std::hex |
| << mir->offset; |
| } |
| mir->optimizationFlags |= MIR_IGNORE_RANGE_CHECK; |
| } |
| } |
| } |
| |
| /* Allocate a compiler temp, return Sreg. Reuse existing if no conflict */ |
| int allocCompilerTempSreg(CompilationUnit* cUnit, ArenaBitVector* bv) |
| { |
| for (int i = 0; i < cUnit->numCompilerTemps; i++) { |
| CompilerTemp* ct = (CompilerTemp*)cUnit->compilerTemps.elemList[i]; |
| ArenaBitVector* tBv = ct->bv; |
| if (!oatTestBitVectors(bv, tBv)) { |
| // Combine live maps and reuse existing temp |
| oatUnifyBitVectors(tBv, tBv, bv); |
| return ct->sReg; |
| } |
| } |
| |
| // Create a new compiler temp & associated live bitmap |
| CompilerTemp* ct = (CompilerTemp*)oatNew(cUnit, sizeof(CompilerTemp), |
| true, kAllocMisc); |
| ArenaBitVector *nBv = oatAllocBitVector(cUnit, cUnit->numBlocks, true, |
| kBitMapMisc); |
| oatCopyBitVector(nBv, bv); |
| ct->bv = nBv; |
| ct->sReg = addNewSReg(cUnit, SSA_CTEMP_BASEREG - cUnit->numCompilerTemps); |
| cUnit->numCompilerTemps++; |
| oatInsertGrowableList(cUnit, &cUnit->compilerTemps, (intptr_t)ct); |
| DCHECK_EQ(cUnit->numCompilerTemps, (int)cUnit->compilerTemps.numUsed); |
| return ct->sReg; |
| } |
| |
| /* Creata a new MIR node for a new pseudo op. */ |
| MIR* rawMIR(CompilationUnit* cUnit, Instruction::Code opcode, int defs, int uses) |
| { |
| MIR* res = (MIR*)oatNew( cUnit, sizeof(MIR), true, kAllocMIR); |
| res->ssaRep =(struct SSARepresentation *) |
| oatNew(cUnit, sizeof(SSARepresentation), true, kAllocDFInfo); |
| if (uses) { |
| res->ssaRep->numUses = uses; |
| res->ssaRep->uses = (int*)oatNew(cUnit, sizeof(int) * uses, false, kAllocDFInfo); |
| } |
| if (defs) { |
| res->ssaRep->numDefs = defs; |
| res->ssaRep->defs = (int*)oatNew(cUnit, sizeof(int) * defs, false, kAllocDFInfo); |
| res->ssaRep->fpDef = (bool*)oatNew(cUnit, sizeof(bool) * defs, true, kAllocDFInfo); |
| } |
| res->dalvikInsn.opcode = opcode; |
| return res; |
| } |
| |
| /* Do some MIR-level basic block optimizations */ |
| bool basicBlockOpt(CompilationUnit* cUnit, BasicBlock* bb) |
| { |
| int numTemps = 0; |
| |
| for (MIR* mir = bb->firstMIRInsn; mir; mir = mir->next) { |
| // Look for interesting opcodes, skip otherwise |
| Instruction::Code opcode = mir->dalvikInsn.opcode; |
| switch (opcode) { |
| case Instruction::AGET: |
| case Instruction::AGET_OBJECT: |
| case Instruction::AGET_BOOLEAN: |
| case Instruction::AGET_BYTE: |
| case Instruction::AGET_CHAR: |
| case Instruction::AGET_SHORT: |
| case Instruction::AGET_WIDE: |
| if (!(mir->optimizationFlags & MIR_IGNORE_RANGE_CHECK)) { |
| int arrSreg = mir->ssaRep->uses[0]; |
| int idxSreg = mir->ssaRep->uses[1]; |
| BasicBlock* tbb = bb; |
| squashDupRangeChecks(cUnit, &tbb, mir, arrSreg, idxSreg); |
| } |
| break; |
| case Instruction::APUT: |
| case Instruction::APUT_OBJECT: |
| case Instruction::APUT_SHORT: |
| case Instruction::APUT_CHAR: |
| case Instruction::APUT_BYTE: |
| case Instruction::APUT_BOOLEAN: |
| case Instruction::APUT_WIDE: |
| if (!(mir->optimizationFlags & MIR_IGNORE_RANGE_CHECK)) { |
| int start = (opcode == Instruction::APUT_WIDE) ? 2 : 1; |
| int arrSreg = mir->ssaRep->uses[start]; |
| int idxSreg = mir->ssaRep->uses[start + 1]; |
| BasicBlock* tbb = bb; |
| squashDupRangeChecks(cUnit, &tbb, mir, arrSreg, idxSreg); |
| } |
| break; |
| case Instruction::CMPL_FLOAT: |
| case Instruction::CMPL_DOUBLE: |
| case Instruction::CMPG_FLOAT: |
| case Instruction::CMPG_DOUBLE: |
| case Instruction::CMP_LONG: |
| if (mir->next != NULL) { |
| MIR* mirNext = mir->next; |
| Instruction::Code brOpcode = mirNext->dalvikInsn.opcode; |
| ConditionCode ccode = kCondNv; |
| switch(brOpcode) { |
| case Instruction::IF_EQZ: |
| ccode = kCondEq; |
| break; |
| case Instruction::IF_NEZ: |
| ccode = kCondNe; |
| break; |
| case Instruction::IF_LTZ: |
| ccode = kCondLt; |
| break; |
| case Instruction::IF_GEZ: |
| ccode = kCondGe; |
| break; |
| case Instruction::IF_GTZ: |
| ccode = kCondGt; |
| break; |
| case Instruction::IF_LEZ: |
| ccode = kCondLe; |
| break; |
| default: |
| break; |
| } |
| // Make sure result of cmp is used by next insn and nowhere else |
| if ((ccode != kCondNv) && |
| (mir->ssaRep->defs[0] == mirNext->ssaRep->uses[0]) && |
| (getSSAUseCount(cUnit, mir->ssaRep->defs[0]) == 1)) { |
| mirNext->dalvikInsn.arg[0] = ccode; |
| switch(opcode) { |
| case Instruction::CMPL_FLOAT: |
| mirNext->dalvikInsn.opcode = |
| static_cast<Instruction::Code>(kMirOpFusedCmplFloat); |
| break; |
| case Instruction::CMPL_DOUBLE: |
| mirNext->dalvikInsn.opcode = |
| static_cast<Instruction::Code>(kMirOpFusedCmplDouble); |
| break; |
| case Instruction::CMPG_FLOAT: |
| mirNext->dalvikInsn.opcode = |
| static_cast<Instruction::Code>(kMirOpFusedCmpgFloat); |
| break; |
| case Instruction::CMPG_DOUBLE: |
| mirNext->dalvikInsn.opcode = |
| static_cast<Instruction::Code>(kMirOpFusedCmpgDouble); |
| break; |
| case Instruction::CMP_LONG: |
| mirNext->dalvikInsn.opcode = |
| static_cast<Instruction::Code>(kMirOpFusedCmpLong); |
| break; |
| default: LOG(ERROR) << "Unexpected opcode: " << (int)opcode; |
| } |
| mir->dalvikInsn.opcode = static_cast<Instruction::Code>(kMirOpNop); |
| mirNext->ssaRep->numUses = mir->ssaRep->numUses; |
| mirNext->ssaRep->uses = mir->ssaRep->uses; |
| mirNext->ssaRep->fpUse = mir->ssaRep->fpUse; |
| mirNext->ssaRep->numDefs = 0; |
| mir->ssaRep->numUses = 0; |
| mir->ssaRep->numDefs = 0; |
| } |
| } |
| break; |
| default: |
| break; |
| } |
| } |
| |
| if (numTemps > cUnit->numCompilerTemps) { |
| cUnit->numCompilerTemps = numTemps; |
| } |
| return true; |
| } |
| |
| bool nullCheckEliminationInit(struct CompilationUnit* cUnit, |
| struct BasicBlock* bb) |
| { |
| if (bb->dataFlowInfo == NULL) return false; |
| bb->dataFlowInfo->endingNullCheckV = |
| oatAllocBitVector(cUnit, cUnit->numSSARegs, false, kBitMapNullCheck); |
| oatClearAllBits(bb->dataFlowInfo->endingNullCheckV); |
| return true; |
| } |
| |
| /* Eliminate unnecessary null checks for a basic block. */ |
| bool eliminateNullChecks( struct CompilationUnit* cUnit, struct BasicBlock* bb) |
| { |
| if (bb->dataFlowInfo == NULL) return false; |
| |
| /* |
| * Set initial state. Be conservative with catch |
| * blocks and start with no assumptions about null check |
| * status (except for "this"). |
| */ |
| if ((bb->blockType == kEntryBlock) | bb->catchEntry) { |
| oatClearAllBits(cUnit->tempSSARegisterV); |
| if ((cUnit->access_flags & kAccStatic) == 0) { |
| // If non-static method, mark "this" as non-null |
| int thisReg = cUnit->numDalvikRegisters - cUnit->numIns; |
| oatSetBit(cUnit, cUnit->tempSSARegisterV, thisReg); |
| } |
| } else { |
| // Starting state is intesection of all incoming arcs |
| GrowableListIterator iter; |
| oatGrowableListIteratorInit(bb->predecessors, &iter); |
| BasicBlock* predBB = (BasicBlock*)oatGrowableListIteratorNext(&iter); |
| DCHECK(predBB != NULL); |
| oatCopyBitVector(cUnit->tempSSARegisterV, |
| predBB->dataFlowInfo->endingNullCheckV); |
| while (true) { |
| predBB = (BasicBlock*)oatGrowableListIteratorNext(&iter); |
| if (!predBB) break; |
| if ((predBB->dataFlowInfo == NULL) || |
| (predBB->dataFlowInfo->endingNullCheckV == NULL)) { |
| continue; |
| } |
| oatIntersectBitVectors(cUnit->tempSSARegisterV, |
| cUnit->tempSSARegisterV, |
| predBB->dataFlowInfo->endingNullCheckV); |
| } |
| } |
| |
| // Walk through the instruction in the block, updating as necessary |
| for (MIR* mir = bb->firstMIRInsn; mir; mir = mir->next) { |
| if (mir->ssaRep == NULL) { |
| continue; |
| } |
| int dfAttributes = |
| oatDataFlowAttributes[mir->dalvikInsn.opcode]; |
| |
| // Mark target of NEW* as non-null |
| if (dfAttributes & DF_NON_NULL_DST) { |
| oatSetBit(cUnit, cUnit->tempSSARegisterV, mir->ssaRep->defs[0]); |
| } |
| |
| // Mark non-null returns from invoke-style NEW* |
| if (dfAttributes & DF_NON_NULL_RET) { |
| MIR* nextMir = mir->next; |
| // Next should be an MOVE_RESULT_OBJECT |
| if (nextMir && nextMir->dalvikInsn.opcode == Instruction::MOVE_RESULT_OBJECT) { |
| // Mark as null checked |
| oatSetBit(cUnit, cUnit->tempSSARegisterV, |
| nextMir->ssaRep->defs[0]); |
| } else { |
| if (nextMir) { |
| LOG(WARNING) << "Unexpected opcode following new: " << |
| (int)nextMir->dalvikInsn.opcode; |
| } else if (bb->fallThrough) { |
| // Look in next basic block |
| struct BasicBlock* nextBB = bb->fallThrough; |
| for (MIR* tmir = nextBB->firstMIRInsn; tmir; |
| tmir =tmir->next) { |
| if ((int)tmir->dalvikInsn.opcode >= (int)kMirOpFirst) { |
| continue; |
| } |
| // First non-pseudo should be MOVE_RESULT_OBJECT |
| if (tmir->dalvikInsn.opcode == Instruction::MOVE_RESULT_OBJECT) { |
| // Mark as null checked |
| oatSetBit(cUnit, cUnit->tempSSARegisterV, |
| tmir->ssaRep->defs[0]); |
| } else { |
| LOG(WARNING) << "Unexpected op after new: " << |
| (int)tmir->dalvikInsn.opcode; |
| } |
| break; |
| } |
| } |
| } |
| } |
| |
| /* |
| * Propagate nullcheck state on register copies (including |
| * Phi pseudo copies. For the latter, nullcheck state is |
| * the "and" of all the Phi's operands. |
| */ |
| if (dfAttributes & (DF_NULL_TRANSFER_0 | DF_NULL_TRANSFER_N)) { |
| int tgtSreg = mir->ssaRep->defs[0]; |
| int operands = (dfAttributes & DF_NULL_TRANSFER_0) ? 1 : |
| mir->ssaRep->numUses; |
| bool nullChecked = true; |
| for (int i = 0; i < operands; i++) { |
| nullChecked &= oatIsBitSet(cUnit->tempSSARegisterV, |
| mir->ssaRep->uses[i]); |
| } |
| if (nullChecked) { |
| oatSetBit(cUnit, cUnit->tempSSARegisterV, tgtSreg); |
| } |
| } |
| |
| // Already nullchecked? |
| if (dfAttributes & DF_HAS_NULL_CHKS) { |
| int srcIdx; |
| if (dfAttributes & DF_NULL_CHK_1) { |
| srcIdx = 1; |
| } else if (dfAttributes & DF_NULL_CHK_2) { |
| srcIdx = 2; |
| } else { |
| srcIdx = 0; |
| } |
| int srcSreg = mir->ssaRep->uses[srcIdx]; |
| if (oatIsBitSet(cUnit->tempSSARegisterV, srcSreg)) { |
| // Eliminate the null check |
| mir->optimizationFlags |= MIR_IGNORE_NULL_CHECK; |
| } else { |
| // Mark sReg as null-checked |
| oatSetBit(cUnit, cUnit->tempSSARegisterV, srcSreg); |
| } |
| } |
| } |
| |
| // Did anything change? |
| bool res = oatCompareBitVectors(bb->dataFlowInfo->endingNullCheckV, |
| cUnit->tempSSARegisterV); |
| if (res) { |
| oatCopyBitVector(bb->dataFlowInfo->endingNullCheckV, |
| cUnit->tempSSARegisterV); |
| } |
| return res; |
| } |
| |
| void oatMethodNullCheckElimination(CompilationUnit *cUnit) |
| { |
| if (!(cUnit->disableOpt & (1 << kNullCheckElimination))) { |
| DCHECK(cUnit->tempSSARegisterV != NULL); |
| oatDataFlowAnalysisDispatcher(cUnit, nullCheckEliminationInit, |
| kAllNodes, |
| false /* isIterative */); |
| oatDataFlowAnalysisDispatcher(cUnit, eliminateNullChecks, |
| kPreOrderDFSTraversal, |
| true /* isIterative */); |
| } |
| } |
| |
| void oatMethodBasicBlockOptimization(CompilationUnit *cUnit) |
| { |
| if (!(cUnit->disableOpt & (1 << kBBOpt))) { |
| oatInitGrowableList(cUnit, &cUnit->compilerTemps, 6, kListMisc); |
| DCHECK_EQ(cUnit->numCompilerTemps, 0); |
| if (!(cUnit->disableOpt & (1 << kBBOpt))) { |
| oatDataFlowAnalysisDispatcher(cUnit, basicBlockOpt, |
| kAllNodes, false /* isIterative */); |
| } |
| } |
| } |
| |
| void addLoopHeader(CompilationUnit* cUnit, BasicBlock* header, |
| BasicBlock* backEdge) |
| { |
| GrowableListIterator iter; |
| oatGrowableListIteratorInit(&cUnit->loopHeaders, &iter); |
| for (LoopInfo* loop = (LoopInfo*)oatGrowableListIteratorNext(&iter); |
| (loop != NULL); loop = (LoopInfo*)oatGrowableListIteratorNext(&iter)) { |
| if (loop->header == header) { |
| oatInsertGrowableList(cUnit, &loop->incomingBackEdges, |
| (intptr_t)backEdge); |
| return; |
| } |
| } |
| LoopInfo* info = (LoopInfo*)oatNew(cUnit, sizeof(LoopInfo), true, |
| kAllocDFInfo); |
| info->header = header; |
| oatInitGrowableList(cUnit, &info->incomingBackEdges, 2, kListMisc); |
| oatInsertGrowableList(cUnit, &info->incomingBackEdges, (intptr_t)backEdge); |
| oatInsertGrowableList(cUnit, &cUnit->loopHeaders, (intptr_t)info); |
| } |
| |
| bool findBackEdges(struct CompilationUnit* cUnit, struct BasicBlock* bb) |
| { |
| if ((bb->dataFlowInfo == NULL) || (bb->lastMIRInsn == NULL)) { |
| return false; |
| } |
| Instruction::Code opcode = bb->lastMIRInsn->dalvikInsn.opcode; |
| if (Instruction::Flags(opcode) & Instruction::kBranch) { |
| if (bb->taken && (bb->taken->startOffset <= bb->startOffset)) { |
| DCHECK(bb->dominators != NULL); |
| if (oatIsBitSet(bb->dominators, bb->taken->id)) { |
| if (cUnit->printMe) { |
| LOG(INFO) << "Loop backedge from 0x" |
| << std::hex << bb->lastMIRInsn->offset |
| << " to 0x" << std::hex << bb->taken->startOffset; |
| } |
| addLoopHeader(cUnit, bb->taken, bb); |
| } |
| } |
| } |
| return false; |
| } |
| |
| void addBlocksToLoop(CompilationUnit* cUnit, ArenaBitVector* blocks, |
| BasicBlock* bb, int headId) |
| { |
| if (!oatIsBitSet(bb->dominators, headId) || |
| oatIsBitSet(blocks, bb->id)) { |
| return; |
| } |
| oatSetBit(cUnit, blocks, bb->id); |
| GrowableListIterator iter; |
| oatGrowableListIteratorInit(bb->predecessors, &iter); |
| BasicBlock* predBB; |
| for (predBB = (BasicBlock*)oatGrowableListIteratorNext(&iter); predBB; |
| predBB = (BasicBlock*)oatGrowableListIteratorNext(&iter)) { |
| addBlocksToLoop(cUnit, blocks, predBB, headId); |
| } |
| } |
| |
| void oatDumpLoops(CompilationUnit *cUnit) |
| { |
| GrowableListIterator iter; |
| oatGrowableListIteratorInit(&cUnit->loopHeaders, &iter); |
| for (LoopInfo* loop = (LoopInfo*)oatGrowableListIteratorNext(&iter); |
| (loop != NULL); loop = (LoopInfo*)oatGrowableListIteratorNext(&iter)) { |
| LOG(INFO) << "Loop head block id " << loop->header->id |
| << ", offset 0x" << std::hex << loop->header->startOffset |
| << ", Depth: " << loop->header->nestingDepth; |
| GrowableListIterator iter; |
| oatGrowableListIteratorInit(&loop->incomingBackEdges, &iter); |
| BasicBlock* edgeBB; |
| for (edgeBB = (BasicBlock*)oatGrowableListIteratorNext(&iter); edgeBB; |
| edgeBB = (BasicBlock*)oatGrowableListIteratorNext(&iter)) { |
| LOG(INFO) << " Backedge block id " << edgeBB->id |
| << ", offset 0x" << std::hex << edgeBB->startOffset; |
| ArenaBitVectorIterator bIter; |
| oatBitVectorIteratorInit(loop->blocks, &bIter); |
| for (int bbId = oatBitVectorIteratorNext(&bIter); bbId != -1; |
| bbId = oatBitVectorIteratorNext(&bIter)) { |
| BasicBlock *bb; |
| bb = (BasicBlock*) |
| oatGrowableListGetElement(&cUnit->blockList, bbId); |
| LOG(INFO) << " (" << bb->id << ", 0x" << std::hex |
| << bb->startOffset << ")"; |
| } |
| } |
| } |
| } |
| |
| void oatMethodLoopDetection(CompilationUnit *cUnit) |
| { |
| if (cUnit->disableOpt & (1 << kPromoteRegs)) { |
| return; |
| } |
| oatInitGrowableList(cUnit, &cUnit->loopHeaders, 6, kListMisc); |
| // Find the loop headers |
| oatDataFlowAnalysisDispatcher(cUnit, findBackEdges, |
| kAllNodes, false /* isIterative */); |
| GrowableListIterator iter; |
| oatGrowableListIteratorInit(&cUnit->loopHeaders, &iter); |
| // Add blocks to each header |
| for (LoopInfo* loop = (LoopInfo*)oatGrowableListIteratorNext(&iter); |
| loop; loop = (LoopInfo*)oatGrowableListIteratorNext(&iter)) { |
| loop->blocks = oatAllocBitVector(cUnit, cUnit->numBlocks, true, |
| kBitMapMisc); |
| oatSetBit(cUnit, loop->blocks, loop->header->id); |
| GrowableListIterator iter; |
| oatGrowableListIteratorInit(&loop->incomingBackEdges, &iter); |
| BasicBlock* edgeBB; |
| for (edgeBB = (BasicBlock*)oatGrowableListIteratorNext(&iter); edgeBB; |
| edgeBB = (BasicBlock*)oatGrowableListIteratorNext(&iter)) { |
| addBlocksToLoop(cUnit, loop->blocks, edgeBB, loop->header->id); |
| } |
| } |
| // Compute the nesting depth of each header |
| oatGrowableListIteratorInit(&cUnit->loopHeaders, &iter); |
| for (LoopInfo* loop = (LoopInfo*)oatGrowableListIteratorNext(&iter); |
| loop; loop = (LoopInfo*)oatGrowableListIteratorNext(&iter)) { |
| GrowableListIterator iter2; |
| oatGrowableListIteratorInit(&cUnit->loopHeaders, &iter2); |
| LoopInfo* loop2; |
| for (loop2 = (LoopInfo*)oatGrowableListIteratorNext(&iter2); |
| loop2; loop2 = (LoopInfo*)oatGrowableListIteratorNext(&iter2)) { |
| if (oatIsBitSet(loop2->blocks, loop->header->id)) { |
| loop->header->nestingDepth++; |
| } |
| } |
| } |
| // Assign nesting depth to each block in all loops |
| oatGrowableListIteratorInit(&cUnit->loopHeaders, &iter); |
| for (LoopInfo* loop = (LoopInfo*)oatGrowableListIteratorNext(&iter); |
| (loop != NULL); loop = (LoopInfo*)oatGrowableListIteratorNext(&iter)) { |
| ArenaBitVectorIterator bIter; |
| oatBitVectorIteratorInit(loop->blocks, &bIter); |
| for (int bbId = oatBitVectorIteratorNext(&bIter); bbId != -1; |
| bbId = oatBitVectorIteratorNext(&bIter)) { |
| BasicBlock *bb; |
| bb = (BasicBlock*) oatGrowableListGetElement(&cUnit->blockList, |
| bbId); |
| bb->nestingDepth = std::max(bb->nestingDepth, |
| loop->header->nestingDepth); |
| } |
| } |
| if (cUnit->printMe) { |
| oatDumpLoops(cUnit); |
| } |
| } |
| |
| /* |
| * This function will make a best guess at whether the invoke will |
| * end up using Method*. It isn't critical to get it exactly right, |
| * and attempting to do would involve more complexity than it's |
| * worth. |
| */ |
| bool invokeUsesMethodStar(CompilationUnit* cUnit, MIR* mir) |
| { |
| InvokeType type; |
| Instruction::Code opcode = mir->dalvikInsn.opcode; |
| switch (opcode) { |
| case Instruction::INVOKE_STATIC: |
| case Instruction::INVOKE_STATIC_RANGE: |
| type = kStatic; |
| break; |
| case Instruction::INVOKE_DIRECT: |
| case Instruction::INVOKE_DIRECT_RANGE: |
| type = kDirect; |
| break; |
| case Instruction::INVOKE_VIRTUAL: |
| case Instruction::INVOKE_VIRTUAL_RANGE: |
| type = kVirtual; |
| break; |
| case Instruction::INVOKE_INTERFACE: |
| case Instruction::INVOKE_INTERFACE_RANGE: |
| return false; |
| case Instruction::INVOKE_SUPER_RANGE: |
| case Instruction::INVOKE_SUPER: |
| type = kSuper; |
| break; |
| default: |
| LOG(WARNING) << "Unexpected invoke op: " << (int)opcode; |
| return false; |
| } |
| OatCompilationUnit mUnit(cUnit->class_loader, cUnit->class_linker, |
| *cUnit->dex_file, *cUnit->dex_cache, |
| cUnit->code_item, cUnit->method_idx, |
| cUnit->access_flags); |
| // TODO: add a flag so we don't counts the stats for this twice |
| uint32_t dexMethodIdx = mir->dalvikInsn.vB; |
| int vtableIdx; |
| uintptr_t directCode; |
| uintptr_t directMethod; |
| bool fastPath = |
| cUnit->compiler->ComputeInvokeInfo(dexMethodIdx, &mUnit, type, |
| vtableIdx, directCode, |
| directMethod) && |
| !SLOW_INVOKE_PATH; |
| return (((type == kDirect) || (type == kStatic)) && |
| fastPath && ((directCode == 0) || (directMethod == 0))); |
| } |
| |
| /* |
| * Count uses, weighting by loop nesting depth. This code only |
| * counts explicitly used sRegs. A later phase will add implicit |
| * counts for things such as Method*, null-checked references, etc. |
| */ |
| bool countUses(struct CompilationUnit* cUnit, struct BasicBlock* bb) |
| { |
| if (bb->blockType != kDalvikByteCode) { |
| return false; |
| } |
| for (MIR* mir = bb->firstMIRInsn; (mir != NULL); mir = mir->next) { |
| if (mir->ssaRep == NULL) { |
| continue; |
| } |
| uint32_t weight = std::min(16U, (uint32_t)bb->nestingDepth); |
| for (int i = 0; i < mir->ssaRep->numUses; i++) { |
| int sReg = mir->ssaRep->uses[i]; |
| DCHECK_LT(sReg, (int)cUnit->useCounts.numUsed); |
| cUnit->rawUseCounts.elemList[sReg]++; |
| cUnit->useCounts.elemList[sReg] += (1 << weight); |
| } |
| if (!(cUnit->disableOpt & (1 << kPromoteCompilerTemps))) { |
| int dfAttributes = oatDataFlowAttributes[mir->dalvikInsn.opcode]; |
| // Implicit use of Method* ? */ |
| if (dfAttributes & DF_UMS) { |
| /* |
| * Some invokes will not use Method* - need to perform test similar |
| * to that found in genInvoke() to decide whether to count refs |
| * for Method* on invoke-class opcodes. |
| * TODO: refactor for common test here, save results for genInvoke |
| */ |
| int usesMethodStar = true; |
| if ((dfAttributes & (DF_FORMAT_35C | DF_FORMAT_3RC)) && |
| !(dfAttributes & DF_NON_NULL_RET)) { |
| usesMethodStar &= invokeUsesMethodStar(cUnit, mir); |
| } |
| if (usesMethodStar) { |
| cUnit->rawUseCounts.elemList[cUnit->methodSReg]++; |
| cUnit->useCounts.elemList[cUnit->methodSReg] += (1 << weight); |
| } |
| } |
| } |
| } |
| return false; |
| } |
| |
| void oatMethodUseCount(CompilationUnit *cUnit) |
| { |
| oatInitGrowableList(cUnit, &cUnit->useCounts, cUnit->numSSARegs + 32, |
| kListMisc); |
| oatInitGrowableList(cUnit, &cUnit->rawUseCounts, cUnit->numSSARegs + 32, |
| kListMisc); |
| // Initialize list |
| for (int i = 0; i < cUnit->numSSARegs; i++) { |
| oatInsertGrowableList(cUnit, &cUnit->useCounts, 0); |
| oatInsertGrowableList(cUnit, &cUnit->rawUseCounts, 0); |
| } |
| if (cUnit->disableOpt & (1 << kPromoteRegs)) { |
| return; |
| } |
| oatDataFlowAnalysisDispatcher(cUnit, countUses, |
| kAllNodes, false /* isIterative */); |
| } |
| |
| } // namespace art |