/* * 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(opcode) >= static_cast(kMirOpFirst)) { if (static_cast(opcode) == static_cast(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(opcode) < static_cast(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(mir->dalvikInsn.opcode) < static_cast(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(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(kMirOpFusedCmplFloat); break; case Instruction::CMPL_DOUBLE: mirNext->dalvikInsn.opcode = static_cast(kMirOpFusedCmplDouble); break; case Instruction::CMPG_FLOAT: mirNext->dalvikInsn.opcode = static_cast(kMirOpFusedCmpgFloat); break; case Instruction::CMPG_DOUBLE: mirNext->dalvikInsn.opcode = static_cast(kMirOpFusedCmpgDouble); break; case Instruction::CMP_LONG: mirNext->dalvikInsn.opcode = static_cast(kMirOpFusedCmpLong); break; default: LOG(ERROR) << "Unexpected opcode: " << (int)opcode; } mir->dalvikInsn.opcode = static_cast(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