Quick compiler source reorganizatio - part 1
A step towards cleanup of the quick compiler source. In this
CL we rename all files to Art standards, combine some of the
old target-specific files that may have made sense in the
JIT, but no longer do. Also removed some codegen/<target>/
subdirectories, combined and deleted some existing files.
Still quite a bit of work to do in cleaning up header files,
getting some better consistency in what codegen functions
go where. That will happen in later CLs.
No logic changes in this CL - just renaming and moving stuff around
Change-Id: Ic172cd3b76d4c670f8e4d5fdd4a3e967db3f4c1e
diff --git a/src/compiler/dataflow.cc b/src/compiler/dataflow.cc
new file mode 100644
index 0000000..a20a428
--- /dev/null
+++ b/src/compiler/dataflow.cc
@@ -0,0 +1,2530 @@
+/*
+ * 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 | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_IS_MOVE,
+
+ // 05 MOVE_WIDE_FROM16 vAA, vBBBB
+ DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_IS_MOVE,
+
+ // 06 MOVE_WIDE_16 vAAAA, vBBBB
+ DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_IS_MOVE,
+
+ // 07 MOVE_OBJECT vA, vB
+ DF_DA | DF_UB | DF_NULL_TRANSFER_0 | DF_IS_MOVE | DF_REF_A | DF_REF_B,
+
+ // 08 MOVE_OBJECT_FROM16 vAA, vBBBB
+ DF_DA | DF_UB | DF_NULL_TRANSFER_0 | DF_IS_MOVE | DF_REF_A | DF_REF_B,
+
+ // 09 MOVE_OBJECT_16 vAAAA, vBBBB
+ DF_DA | DF_UB | DF_NULL_TRANSFER_0 | DF_IS_MOVE | DF_REF_A | DF_REF_B,
+
+ // 0A MOVE_RESULT vAA
+ DF_DA,
+
+ // 0B MOVE_RESULT_WIDE vAA
+ DF_DA | DF_A_WIDE,
+
+ // 0C MOVE_RESULT_OBJECT vAA
+ DF_DA | DF_REF_A,
+
+ // 0D MOVE_EXCEPTION vAA
+ DF_DA | DF_REF_A,
+
+ // 0E RETURN_VOID
+ DF_NOP,
+
+ // 0F RETURN vAA
+ DF_UA,
+
+ // 10 RETURN_WIDE vAA
+ DF_UA | DF_A_WIDE,
+
+ // 11 RETURN_OBJECT vAA
+ DF_UA | DF_REF_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 | DF_A_WIDE | DF_SETS_CONST,
+
+ // 17 CONST_WIDE_32 vAA, #+BBBBBBBB
+ DF_DA | DF_A_WIDE | DF_SETS_CONST,
+
+ // 18 CONST_WIDE vAA, #+BBBBBBBBBBBBBBBB
+ DF_DA | DF_A_WIDE | DF_SETS_CONST,
+
+ // 19 CONST_WIDE_HIGH16 vAA, #+BBBB000000000000
+ DF_DA | DF_A_WIDE | DF_SETS_CONST,
+
+ // 1A CONST_STRING vAA, string@BBBB
+ DF_DA | DF_REF_A,
+
+ // 1B CONST_STRING_JUMBO vAA, string@BBBBBBBB
+ DF_DA | DF_REF_A,
+
+ // 1C CONST_CLASS vAA, type@BBBB
+ DF_DA | DF_REF_A,
+
+ // 1D MONITOR_ENTER vAA
+ DF_UA | DF_NULL_CHK_0 | DF_REF_A,
+
+ // 1E MONITOR_EXIT vAA
+ DF_UA | DF_NULL_CHK_0 | DF_REF_A,
+
+ // 1F CHK_CAST vAA, type@BBBB
+ DF_UA | DF_REF_A | DF_UMS,
+
+ // 20 INSTANCE_OF vA, vB, type@CCCC
+ DF_DA | DF_UB | DF_CORE_A | DF_REF_B | DF_UMS,
+
+ // 21 ARRAY_LENGTH vA, vB
+ DF_DA | DF_UB | DF_NULL_CHK_0 | DF_CORE_A | DF_REF_B,
+
+ // 22 NEW_INSTANCE vAA, type@BBBB
+ DF_DA | DF_NON_NULL_DST | DF_REF_A | DF_UMS,
+
+ // 23 NEW_ARRAY vA, vB, type@CCCC
+ DF_DA | DF_UB | DF_NON_NULL_DST | DF_REF_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_REF_A | DF_UMS,
+
+ // 27 THROW vAA
+ DF_UA | DF_REF_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 | DF_B_WIDE | DF_UC | DF_C_WIDE | DF_FP_B | DF_FP_C | DF_CORE_A,
+
+ // 30 CMPG_DOUBLE vAA, vBB, vCC
+ DF_DA | DF_UB | DF_B_WIDE | DF_UC | DF_C_WIDE | DF_FP_B | DF_FP_C | DF_CORE_A,
+
+ // 31 CMP_LONG vAA, vBB, vCC
+ DF_DA | DF_UB | DF_B_WIDE | DF_UC | DF_C_WIDE | DF_CORE_A | DF_CORE_B | DF_CORE_C,
+
+ // 32 IF_EQ vA, vB, +CCCC
+ DF_UA | DF_UB,
+
+ // 33 IF_NE vA, vB, +CCCC
+ DF_UA | DF_UB,
+
+ // 34 IF_LT vA, vB, +CCCC
+ DF_UA | DF_UB,
+
+ // 35 IF_GE vA, vB, +CCCC
+ DF_UA | DF_UB,
+
+ // 36 IF_GT vA, vB, +CCCC
+ DF_UA | DF_UB,
+
+ // 37 IF_LE vA, vB, +CCCC
+ DF_UA | DF_UB,
+
+ // 38 IF_EQZ vAA, +BBBB
+ DF_UA,
+
+ // 39 IF_NEZ vAA, +BBBB
+ DF_UA,
+
+ // 3A IF_LTZ vAA, +BBBB
+ DF_UA,
+
+ // 3B IF_GEZ vAA, +BBBB
+ DF_UA,
+
+ // 3C IF_GTZ vAA, +BBBB
+ DF_UA,
+
+ // 3D IF_LEZ vAA, +BBBB
+ DF_UA,
+
+ // 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_REF_B | DF_CORE_C,
+
+ // 45 AGET_WIDE vAA, vBB, vCC
+ DF_DA | DF_A_WIDE | DF_UB | DF_UC | DF_NULL_CHK_0 | DF_RANGE_CHK_1 | DF_REF_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_REF_A | DF_REF_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_REF_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_REF_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_REF_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_REF_B | DF_CORE_C,
+
+ // 4B APUT vAA, vBB, vCC
+ DF_UA | DF_UB | DF_UC | DF_NULL_CHK_1 | DF_RANGE_CHK_2 | DF_REF_B | DF_CORE_C,
+
+ // 4C APUT_WIDE vAA, vBB, vCC
+ DF_UA | DF_A_WIDE | DF_UB | DF_UC | DF_NULL_CHK_2 | DF_RANGE_CHK_3 | DF_REF_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_REF_A | DF_REF_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_REF_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_REF_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_REF_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_REF_B | DF_CORE_C,
+
+ // 52 IGET vA, vB, field@CCCC
+ DF_DA | DF_UB | DF_NULL_CHK_0 | DF_REF_B,
+
+ // 53 IGET_WIDE vA, vB, field@CCCC
+ DF_DA | DF_A_WIDE | DF_UB | DF_NULL_CHK_0 | DF_REF_B,
+
+ // 54 IGET_OBJECT vA, vB, field@CCCC
+ DF_DA | DF_UB | DF_NULL_CHK_0 | DF_REF_A | DF_REF_B,
+
+ // 55 IGET_BOOLEAN vA, vB, field@CCCC
+ DF_DA | DF_UB | DF_NULL_CHK_0 | DF_REF_B,
+
+ // 56 IGET_BYTE vA, vB, field@CCCC
+ DF_DA | DF_UB | DF_NULL_CHK_0 | DF_REF_B,
+
+ // 57 IGET_CHAR vA, vB, field@CCCC
+ DF_DA | DF_UB | DF_NULL_CHK_0 | DF_REF_B,
+
+ // 58 IGET_SHORT vA, vB, field@CCCC
+ DF_DA | DF_UB | DF_NULL_CHK_0 | DF_REF_B,
+
+ // 59 IPUT vA, vB, field@CCCC
+ DF_UA | DF_UB | DF_NULL_CHK_1 | DF_REF_B,
+
+ // 5A IPUT_WIDE vA, vB, field@CCCC
+ DF_UA | DF_A_WIDE | DF_UB | DF_NULL_CHK_2 | DF_REF_B,
+
+ // 5B IPUT_OBJECT vA, vB, field@CCCC
+ DF_UA | DF_UB | DF_NULL_CHK_1 | DF_REF_A | DF_REF_B,
+
+ // 5C IPUT_BOOLEAN vA, vB, field@CCCC
+ DF_UA | DF_UB | DF_NULL_CHK_1 | DF_REF_B,
+
+ // 5D IPUT_BYTE vA, vB, field@CCCC
+ DF_UA | DF_UB | DF_NULL_CHK_1 | DF_REF_B,
+
+ // 5E IPUT_CHAR vA, vB, field@CCCC
+ DF_UA | DF_UB | DF_NULL_CHK_1 | DF_REF_B,
+
+ // 5F IPUT_SHORT vA, vB, field@CCCC
+ DF_UA | DF_UB | DF_NULL_CHK_1 | DF_REF_B,
+
+ // 60 SGET vAA, field@BBBB
+ DF_DA | DF_UMS,
+
+ // 61 SGET_WIDE vAA, field@BBBB
+ DF_DA | DF_A_WIDE | DF_UMS,
+
+ // 62 SGET_OBJECT vAA, field@BBBB
+ DF_DA | DF_REF_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 | DF_A_WIDE | DF_UMS,
+
+ // 69 SPUT_OBJECT vAA, field@BBBB
+ DF_UA | DF_REF_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 | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_CORE_A | DF_CORE_B,
+
+ // 7E NOT_LONG vA, vB
+ DF_DA | DF_A_WIDE | DF_UB | DF_B_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 | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_FP_A | DF_FP_B,
+
+ // 81 INT_TO_LONG vA, vB
+ DF_DA | DF_A_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 | DF_A_WIDE | DF_UB | DF_FP_A | DF_CORE_B,
+
+ // 84 LONG_TO_INT vA, vB
+ DF_DA | DF_UB | DF_B_WIDE | DF_CORE_A | DF_CORE_B,
+
+ // 85 LONG_TO_FLOAT vA, vB
+ DF_DA | DF_UB | DF_B_WIDE | DF_FP_A | DF_CORE_B,
+
+ // 86 LONG_TO_DOUBLE vA, vB
+ DF_DA | DF_A_WIDE | DF_UB | DF_B_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 | DF_A_WIDE | DF_UB | DF_FP_B | DF_CORE_A,
+
+ // 89 FLOAT_TO_DOUBLE vA, vB
+ DF_DA | DF_A_WIDE | DF_UB | DF_FP_A | DF_FP_B,
+
+ // 8A DOUBLE_TO_INT vA, vB
+ DF_DA | DF_UB | DF_B_WIDE | DF_FP_B | DF_CORE_A,
+
+ // 8B DOUBLE_TO_LONG vA, vB
+ DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_FP_B | DF_CORE_A,
+
+ // 8C DOUBLE_TO_FLOAT vA, vB
+ DF_DA | DF_UB | DF_B_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_CORE_A | DF_CORE_B | DF_CORE_C,
+
+ // 91 SUB_INT vAA, vBB, vCC
+ DF_DA | DF_UB | DF_UC | 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 | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_UC | DF_C_WIDE | DF_CORE_A | DF_CORE_B | DF_CORE_C,
+
+ // 9C SUB_LONG vAA, vBB, vCC
+ DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_UC | DF_C_WIDE | DF_CORE_A | DF_CORE_B | DF_CORE_C,
+
+ // 9D MUL_LONG vAA, vBB, vCC
+ DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_UC | DF_C_WIDE | DF_CORE_A | DF_CORE_B | DF_CORE_C,
+
+ // 9E DIV_LONG vAA, vBB, vCC
+ DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_UC | DF_C_WIDE | DF_CORE_A | DF_CORE_B | DF_CORE_C,
+
+ // 9F REM_LONG vAA, vBB, vCC
+ DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_UC | DF_C_WIDE | DF_CORE_A | DF_CORE_B | DF_CORE_C,
+
+ // A0 AND_LONG vAA, vBB, vCC
+ DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_UC | DF_C_WIDE | DF_CORE_A | DF_CORE_B | DF_CORE_C,
+
+ // A1 OR_LONG vAA, vBB, vCC
+ DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_UC | DF_C_WIDE | DF_CORE_A | DF_CORE_B | DF_CORE_C,
+
+ // A2 XOR_LONG vAA, vBB, vCC
+ DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_UC | DF_C_WIDE | DF_CORE_A | DF_CORE_B | DF_CORE_C,
+
+ // A3 SHL_LONG vAA, vBB, vCC
+ DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_UC | DF_CORE_A | DF_CORE_B | DF_CORE_C,
+
+ // A4 SHR_LONG vAA, vBB, vCC
+ DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_UC | DF_CORE_A | DF_CORE_B | DF_CORE_C,
+
+ // A5 USHR_LONG vAA, vBB, vCC
+ DF_DA | DF_A_WIDE | DF_UB | DF_B_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 | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_UC | DF_C_WIDE | DF_FP_A | DF_FP_B | DF_FP_C,
+
+ // AC SUB_DOUBLE vAA, vBB, vCC
+ DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_UC | DF_C_WIDE | DF_FP_A | DF_FP_B | DF_FP_C,
+
+ // AD MUL_DOUBLE vAA, vBB, vCC
+ DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_UC | DF_C_WIDE | DF_FP_A | DF_FP_B | DF_FP_C,
+
+ // AE DIV_DOUBLE vAA, vBB, vCC
+ DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_UC | DF_C_WIDE | DF_FP_A | DF_FP_B | DF_FP_C,
+
+ // AF REM_DOUBLE vAA, vBB, vCC
+ DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_UC | DF_C_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 | DF_A_WIDE | DF_UA | DF_UB | DF_B_WIDE | DF_CORE_A | DF_CORE_B,
+
+ // BC SUB_LONG_2ADDR vA, vB
+ DF_DA | DF_A_WIDE | DF_UA | DF_UB | DF_B_WIDE | DF_CORE_A | DF_CORE_B,
+
+ // BD MUL_LONG_2ADDR vA, vB
+ DF_DA | DF_A_WIDE | DF_UA | DF_UB | DF_B_WIDE | DF_CORE_A | DF_CORE_B,
+
+ // BE DIV_LONG_2ADDR vA, vB
+ DF_DA | DF_A_WIDE | DF_UA | DF_UB | DF_B_WIDE | DF_CORE_A | DF_CORE_B,
+
+ // BF REM_LONG_2ADDR vA, vB
+ DF_DA | DF_A_WIDE | DF_UA | DF_UB | DF_B_WIDE | DF_CORE_A | DF_CORE_B,
+
+ // C0 AND_LONG_2ADDR vA, vB
+ DF_DA | DF_A_WIDE | DF_UA | DF_UB | DF_B_WIDE | DF_CORE_A | DF_CORE_B,
+
+ // C1 OR_LONG_2ADDR vA, vB
+ DF_DA | DF_A_WIDE | DF_UA | DF_UB | DF_B_WIDE | DF_CORE_A | DF_CORE_B,
+
+ // C2 XOR_LONG_2ADDR vA, vB
+ DF_DA | DF_A_WIDE | DF_UA | DF_UB | DF_B_WIDE | DF_CORE_A | DF_CORE_B,
+
+ // C3 SHL_LONG_2ADDR vA, vB
+ DF_DA | DF_A_WIDE | DF_UA | DF_UB | DF_CORE_A | DF_CORE_B,
+
+ // C4 SHR_LONG_2ADDR vA, vB
+ DF_DA | DF_A_WIDE | DF_UA | DF_UB | DF_CORE_A | DF_CORE_B,
+
+ // C5 USHR_LONG_2ADDR vA, vB
+ DF_DA | DF_A_WIDE | DF_UA | 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 | DF_A_WIDE | DF_UA | DF_UB | DF_B_WIDE | DF_FP_A | DF_FP_B,
+
+ // CC SUB_DOUBLE_2ADDR vA, vB
+ DF_DA | DF_A_WIDE | DF_UA | DF_UB | DF_B_WIDE | DF_FP_A | DF_FP_B,
+
+ // CD MUL_DOUBLE_2ADDR vA, vB
+ DF_DA | DF_A_WIDE | DF_UA | DF_UB | DF_B_WIDE | DF_FP_A | DF_FP_B,
+
+ // CE DIV_DOUBLE_2ADDR vA, vB
+ DF_DA | DF_A_WIDE | DF_UA | DF_UB | DF_B_WIDE | DF_FP_A | DF_FP_B,
+
+ // CF REM_DOUBLE_2ADDR vA, vB
+ DF_DA | DF_A_WIDE | DF_UA | DF_UB | DF_B_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_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_REF_B,
+
+ // E4 IPUT_VOLATILE
+ DF_UA | DF_UB | DF_NULL_CHK_1 | DF_REF_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_REF_A | DF_REF_B,
+
+ // E8 IGET_WIDE_VOLATILE
+ DF_DA | DF_A_WIDE | DF_UB | DF_NULL_CHK_0 | DF_REF_B,
+
+ // E9 IPUT_WIDE_VOLATILE
+ DF_UA | DF_A_WIDE | DF_UB | DF_NULL_CHK_2 | DF_REF_B,
+
+ // EA SGET_WIDE_VOLATILE
+ DF_DA | DF_A_WIDE | DF_UMS,
+
+ // EB SPUT_WIDE_VOLATILE
+ DF_UA | DF_A_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 | DF_A_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 | DF_A_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_REF_A | DF_REF_B,
+
+ // FD SGET_OBJECT_VOLATILE
+ DF_DA | DF_REF_A | DF_UMS,
+
+ // FE SPUT_OBJECT_VOLATILE
+ DF_UA | DF_REF_A | DF_UMS,
+
+ // FF UNUSED_FF
+ DF_NOP,
+
+ // Beginning of extended MIR opcodes
+ // 100 MIR_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 | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_FP_A | DF_FP_B,
+
+ // 105 MIR_FUSED_CMPG_DOUBLE
+ DF_UA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_FP_A | DF_FP_B,
+
+ // 106 MIR_FUSED_CMP_LONG
+ DF_UA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_CORE_A | DF_CORE_B,
+
+ // 107 MIR_NOP
+ DF_NOP,
+
+ // 108 MIR_NULL_CHECK
+ 0,
+
+ // 109 MIR_RANGE_CHECK
+ 0,
+
+ // 110 MIR_DIV_ZERO_CHECK
+ 0,
+
+ // 111 MIR_CHECK
+ 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)
+{
+ std::string str;
+ int opcode = insn.opcode;
+ int dfAttributes = oatDataFlowAttributes[opcode];
+ int flags;
+ char* ret;
+
+ if (opcode >= kMirOpFirst) {
+ if (opcode == kMirOpPhi) {
+ str.append("PHI");
+ } else if (opcode == kMirOpCheck) {
+ str.append("Check");
+ } else {
+ str.append(StringPrintf("Opcode %#x", opcode));
+ }
+ flags = 0;
+ } else {
+ str.append(Instruction::Name(insn.opcode));
+ flags = Instruction::FlagsOf(insn.opcode);
+ }
+
+ if (note) {
+ str.append(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:
+ str.append(StringPrintf(" v%d,", insn.vA));
+ offset = (int) insn.vB;
+ break;
+ case Instruction::k22t:
+ str.append(StringPrintf(" 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;
+ }
+ str.append(StringPrintf(" (%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) str.append(",");
+ str.append(StringPrintf(" v%d", insn.arg[i]));
+ }
+ }
+ else if (dfAttributes & DF_FORMAT_3RC) {
+ str.append(StringPrintf(" v%d..v%d", insn.vC, insn.vC + insn.vA - 1));
+ } else {
+ if (dfAttributes & DF_A_IS_REG) {
+ str.append(StringPrintf(" v%d", insn.vA));
+ }
+ if (dfAttributes & DF_B_IS_REG) {
+ str.append(StringPrintf(", v%d", insn.vB));
+ } else if ((int)opcode < (int)kMirOpFirst) {
+ str.append(StringPrintf(", (#%d)", insn.vB));
+ }
+ if (dfAttributes & DF_C_IS_REG) {
+ str.append(StringPrintf(", v%d", insn.vC));
+ } else if ((int)opcode < (int)kMirOpFirst) {
+ str.append(StringPrintf(", (#%d)", insn.vC));
+ }
+ }
+ int length = str.length() + 1;
+ ret = (char*)oatNew(cUnit, length, false, kAllocDFInfo);
+ strncpy(ret, str.c_str(), length);
+ return ret;
+}
+
+std::string getSSAName(const CompilationUnit* cUnit, int ssaReg)
+{
+ return StringPrintf("v%d_%d", SRegToVReg(cUnit, ssaReg),
+ SRegToSubscript(cUnit, ssaReg));
+}
+
+/*
+ * Dalvik instruction disassembler with optional SSA printing.
+ */
+char* oatFullDisassembler(CompilationUnit* cUnit, const MIR* mir)
+{
+ std::string str;
+ const DecodedInstruction* insn = &mir->dalvikInsn;
+ int opcode = insn->opcode;
+ int dfAttributes = oatDataFlowAttributes[opcode];
+ char* ret;
+ int length;
+
+ if (opcode >= kMirOpFirst) {
+ if (opcode == kMirOpPhi) {
+ int* incoming = (int*)mir->dalvikInsn.vB;
+ str.append(StringPrintf("PHI %s = (%s",
+ getSSAName(cUnit, mir->ssaRep->defs[0]).c_str(),
+ getSSAName(cUnit, mir->ssaRep->uses[0]).c_str()));
+ str.append(StringPrintf(":%d",incoming[0]));
+ int i;
+ for (i = 1; i < mir->ssaRep->numUses; i++) {
+ str.append(StringPrintf(", %s:%d",
+ getSSAName(cUnit, mir->ssaRep->uses[i]).c_str(),
+ incoming[i]));
+ }
+ str.append(")");
+ } else if (opcode == kMirOpCheck) {
+ str.append("Check ");
+ str.append(Instruction::Name(mir->meta.throwInsn->dalvikInsn.opcode));
+ } else if (opcode == kMirOpNop) {
+ str.append("MirNop");
+ } else {
+ str.append(StringPrintf("Opcode %#x", opcode));
+ }
+ goto done;
+ } else {
+ str.append(Instruction::Name(insn->opcode));
+ }
+
+ /* For branches, decode the instructions to print out the branch targets */
+ if (Instruction::FlagsOf(insn->opcode) & Instruction::kBranch) {
+ Instruction::Format dalvikFormat = Instruction::FormatOf(insn->opcode);
+ int delta = 0;
+ switch (dalvikFormat) {
+ case Instruction::k21t:
+ str.append(StringPrintf(" %s, ",
+ getSSAName(cUnit, mir->ssaRep->uses[0]).c_str()));
+ delta = (int) insn->vB;
+ break;
+ case Instruction::k22t:
+ str.append(StringPrintf(" %s, %s, ",
+ getSSAName(cUnit, mir->ssaRep->uses[0]).c_str(),
+ getSSAName(cUnit, mir->ssaRep->uses[1]).c_str()));
+ 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;
+ }
+ str.append(StringPrintf(" %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) str.append(",");
+ str.append(" ");
+ str.append(getSSAName(cUnit, mir->ssaRep->uses[i]));
+ }
+ } else {
+ int udIdx;
+ if (mir->ssaRep->numDefs) {
+
+ for (udIdx = 0; udIdx < mir->ssaRep->numDefs; udIdx++) {
+ str.append(" ");
+ str.append(getSSAName(cUnit, mir->ssaRep->defs[udIdx]));
+ }
+ str.append(",");
+ }
+ if (mir->ssaRep->numUses) {
+ /* No leading ',' for the first use */
+ str.append(" ");
+ str.append(getSSAName(cUnit, mir->ssaRep->uses[0]));
+ for (udIdx = 1; udIdx < mir->ssaRep->numUses; udIdx++) {
+ str.append(", ");
+ str.append(getSSAName(cUnit, mir->ssaRep->uses[udIdx]));
+ }
+ }
+ if (static_cast<int>(opcode) < static_cast<int>(kMirOpFirst)) {
+ Instruction::Format dalvikFormat = Instruction::FormatOf(insn->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
+ str.append(StringPrintf(" #%#x", insn->vB));
+ break;
+ case Instruction::k21c: // op vAA, thing@BBBB
+ case Instruction::k31c: // op vAA, thing@BBBBBBBB
+ str.append(StringPrintf(" @%#x", insn->vB));
+ break;
+ case Instruction::k22b: // op vAA, vBB, #+CC
+ case Instruction::k22s: // op vA, vB, #+CCCC
+ str.append(StringPrintf(" #%#x", insn->vC));
+ break;
+ case Instruction::k22c: // op vA, vB, thing@CCCC
+ str.append(StringPrintf(" @%#x", insn->vC));
+ break;
+ /* No need for special printing */
+ default:
+ break;
+ }
+ }
+ }
+
+done:
+ length = str.length() + 1;
+ ret = (char*) oatNew(cUnit, length, false, kAllocDFInfo);
+ strncpy(ret, str.c_str(), length);
+ return ret;
+}
+
+char* oatGetSSAString(CompilationUnit* cUnit, SSARepresentation* ssaRep)
+{
+ std::string str;
+ char* ret;
+ int i;
+
+ for (i = 0; i < ssaRep->numDefs; i++) {
+ int ssaReg = ssaRep->defs[i];
+ str.append(StringPrintf("s%d(v%d_%d) ", ssaReg,
+ SRegToVReg(cUnit, ssaReg),
+ SRegToSubscript(cUnit, ssaReg)));
+ }
+
+ if (ssaRep->numDefs) {
+ str.append("<- ");
+ }
+
+ for (i = 0; i < ssaRep->numUses; i++) {
+ int ssaReg = ssaRep->uses[i];
+ str.append(StringPrintf("s%d(v%d_%d) ", ssaReg, SRegToVReg(cUnit, ssaReg),
+ SRegToSubscript(cUnit, ssaReg)));
+ }
+
+ int length = str.length() + 1;
+ ret = (char*)oatNew(cUnit, length, false, kAllocDFInfo);
+ strncpy(ret, str.c_str(), 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);
+ if (dfAttributes & DF_A_WIDE) {
+ handleLiveInUse(cUnit, useV, defV, liveInV, dInsn->vA+1);
+ }
+ }
+ if (dfAttributes & DF_UB) {
+ handleLiveInUse(cUnit, useV, defV, liveInV, dInsn->vB);
+ if (dfAttributes & DF_B_WIDE) {
+ handleLiveInUse(cUnit, useV, defV, liveInV, dInsn->vB+1);
+ }
+ }
+ if (dfAttributes & DF_UC) {
+ handleLiveInUse(cUnit, useV, defV, liveInV, dInsn->vC);
+ if (dfAttributes & DF_C_WIDE) {
+ 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_A_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);
+ std::string ssaName = getSSAName(cUnit, ssaReg);
+ char* name = (char*)oatNew(cUnit, ssaName.length() + 1, false, kAllocDFInfo);
+ strncpy(name, ssaName.c_str(), ssaName.length() + 1);
+ oatInsertGrowableList(cUnit, cUnit->ssaStrings, (intptr_t)name);
+ 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::FlagsOf(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++;
+ if (dfAttributes & DF_A_WIDE) {
+ numUses ++;
+ }
+ }
+ if (dfAttributes & DF_UB) {
+ numUses++;
+ if (dfAttributes & DF_B_WIDE) {
+ numUses ++;
+ }
+ }
+ if (dfAttributes & DF_UC) {
+ numUses++;
+ if (dfAttributes & DF_C_WIDE) {
+ numUses ++;
+ }
+ }
+ }
+
+ 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_A_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++);
+ if (dfAttributes & DF_A_WIDE) {
+ 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++);
+ if (dfAttributes & DF_B_WIDE) {
+ 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++);
+ if (dfAttributes & DF_C_WIDE) {
+ 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_A_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;
+ 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_A_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);
+ cUnit->ssaStrings = (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);
+ oatInitGrowableList(cUnit, cUnit->ssaStrings,
+ 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);
+ std::string ssaName = getSSAName(cUnit, i);
+ char* name = (char*)oatNew(cUnit, ssaName.length() + 1, true, kAllocDFInfo);
+ strncpy(name, ssaName.c_str(), ssaName.length() + 1);
+ oatInsertGrowableList(cUnit, cUnit->ssaStrings, (intptr_t)name);
+ }
+
+ /*
+ * 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)
+{
+ BasicBlock* tbb = bb;
+ mir = advanceMIR(cUnit, &tbb, mir, NULL, false);
+ while (mir != NULL) {
+ int opcode = mir->dalvikInsn.opcode;
+ if ((mir->dalvikInsn.opcode == Instruction::MOVE_RESULT) ||
+ (mir->dalvikInsn.opcode == Instruction::MOVE_RESULT_OBJECT) ||
+ (mir->dalvikInsn.opcode == Instruction::MOVE_RESULT_WIDE)) {
+ break;
+ }
+ // Keep going if pseudo op, otherwise terminate
+ if (opcode < 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;
+ 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 (cUnit->genBitcode) {
+ // Bitcode doesn't allow this optimization.
+ break;
+ }
+ 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;
+}
+
+/* Collect stats on number of checks removed */
+bool countChecks( struct CompilationUnit* cUnit, struct BasicBlock* bb)
+{
+ if (bb->dataFlowInfo == NULL) return false;
+ for (MIR* mir = bb->firstMIRInsn; mir; mir = mir->next) {
+ if (mir->ssaRep == NULL) {
+ continue;
+ }
+ int dfAttributes = oatDataFlowAttributes[mir->dalvikInsn.opcode];
+ if (dfAttributes & DF_HAS_NULL_CHKS) {
+ cUnit->checkstats->nullChecks++;
+ if (mir->optimizationFlags & MIR_IGNORE_NULL_CHECK) {
+ cUnit->checkstats->nullChecksEliminated++;
+ }
+ }
+ if (dfAttributes & DF_HAS_RANGE_CHKS) {
+ cUnit->checkstats->rangeChecks++;
+ if (mir->optimizationFlags & MIR_IGNORE_RANGE_CHECK) {
+ cUnit->checkstats->rangeChecksEliminated++;
+ }
+ }
+ }
+ return false;
+}
+
+/* Try to make common case the fallthrough path */
+bool layoutBlocks(struct CompilationUnit* cUnit, struct BasicBlock* bb)
+{
+ // TODO: For now, just looking for direct throws. Consider generalizing for profile feedback
+ if (!bb->explicitThrow) {
+ return false;
+ }
+ BasicBlock* walker = bb;
+ while (true) {
+ // Check termination conditions
+ if ((walker->blockType == kEntryBlock) || (walker->predecessors->numUsed != 1)) {
+ break;
+ }
+ BasicBlock* prev = GET_ELEM_N(walker->predecessors, BasicBlock*, 0);
+ if (prev->conditionalBranch) {
+ if (prev->fallThrough == walker) {
+ // Already done - return
+ break;
+ }
+ DCHECK_EQ(walker, prev->taken);
+ // Got one. Flip it and exit
+ Instruction::Code opcode = prev->lastMIRInsn->dalvikInsn.opcode;
+ switch (opcode) {
+ case Instruction::IF_EQ: opcode = Instruction::IF_NE; break;
+ case Instruction::IF_NE: opcode = Instruction::IF_EQ; break;
+ case Instruction::IF_LT: opcode = Instruction::IF_GE; break;
+ case Instruction::IF_GE: opcode = Instruction::IF_LT; break;
+ case Instruction::IF_GT: opcode = Instruction::IF_LE; break;
+ case Instruction::IF_LE: opcode = Instruction::IF_GT; break;
+ case Instruction::IF_EQZ: opcode = Instruction::IF_NEZ; break;
+ case Instruction::IF_NEZ: opcode = Instruction::IF_EQZ; break;
+ case Instruction::IF_LTZ: opcode = Instruction::IF_GEZ; break;
+ case Instruction::IF_GEZ: opcode = Instruction::IF_LTZ; break;
+ case Instruction::IF_GTZ: opcode = Instruction::IF_LEZ; break;
+ case Instruction::IF_LEZ: opcode = Instruction::IF_GTZ; break;
+ default: LOG(FATAL) << "Unexpected opcode 0x" << std::hex << (int)opcode;
+ }
+ prev->lastMIRInsn->dalvikInsn.opcode = opcode;
+ BasicBlock* tBB = prev->taken;
+ prev->taken = prev->fallThrough;
+ prev->fallThrough = tBB;
+ break;
+ }
+ walker = prev;
+ }
+ return false;
+}
+
+/* Combine any basic blocks terminated by instructions that we now know can't throw */
+bool combineBlocks(struct CompilationUnit* cUnit, struct BasicBlock* bb)
+{
+ // Loop here to allow combining a sequence of blocks
+ while (true) {
+ // Check termination conditions
+ if ((bb->firstMIRInsn == NULL)
+ || (bb->dataFlowInfo == NULL)
+ || (bb->blockType == kExceptionHandling)
+ || (bb->blockType == kExitBlock)
+ || (bb->blockType == kDead)
+ || ((bb->taken == NULL) || (bb->taken->blockType != kExceptionHandling))
+ || (bb->successorBlockList.blockListType != kNotUsed)
+ || ((int)bb->lastMIRInsn->dalvikInsn.opcode != kMirOpCheck)) {
+ break;
+ }
+
+ // Test the kMirOpCheck instruction
+ MIR* mir = bb->lastMIRInsn;
+ // Grab the attributes from the paired opcode
+ MIR* throwInsn = mir->meta.throwInsn;
+ int dfAttributes = oatDataFlowAttributes[throwInsn->dalvikInsn.opcode];
+ bool canCombine = true;
+ if (dfAttributes & DF_HAS_NULL_CHKS) {
+ canCombine &= ((throwInsn->optimizationFlags & MIR_IGNORE_NULL_CHECK) != 0);
+ }
+ if (dfAttributes & DF_HAS_RANGE_CHKS) {
+ canCombine &= ((throwInsn->optimizationFlags & MIR_IGNORE_RANGE_CHECK) != 0);
+ }
+ if (!canCombine) {
+ break;
+ }
+ // OK - got one. Combine
+ BasicBlock* bbNext = bb->fallThrough;
+ DCHECK(!bbNext->catchEntry);
+ DCHECK_EQ(bbNext->predecessors->numUsed, 1U);
+ MIR* tMir = bb->lastMIRInsn->prev;
+ // Overwrite the kOpCheck insn with the paired opcode
+ DCHECK_EQ(bbNext->firstMIRInsn, throwInsn);
+ *bb->lastMIRInsn = *throwInsn;
+ bb->lastMIRInsn->prev = tMir;
+ // Use the successor info from the next block
+ bb->successorBlockList = bbNext->successorBlockList;
+ // Use the ending block linkage from the next block
+ bb->fallThrough = bbNext->fallThrough;
+ bb->taken->blockType = kDead; // Kill the unused exception block
+ bb->taken = bbNext->taken;
+ // Include the rest of the instructions
+ bb->lastMIRInsn = bbNext->lastMIRInsn;
+
+ /*
+ * NOTE: we aren't updating all dataflow info here. Should either make sure this pass
+ * happens after uses of iDominated, domFrontier or update the dataflow info here.
+ */
+
+ // Kill bbNext and remap now-dead id to parent
+ bbNext->blockType = kDead;
+ cUnit->blockIdMap.Overwrite(bbNext->id, bb->id);
+
+ // Now, loop back and see if we can keep going
+ }
+ return false;
+}
+
+/* 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) && !(mir->optimizationFlags & MIR_IGNORE_NULL_CHECK)) {
+ 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 oatMethodBasicBlockCombine(CompilationUnit* cUnit)
+{
+ oatDataFlowAnalysisDispatcher(cUnit, combineBlocks, kPreOrderDFSTraversal, false);
+}
+
+void oatMethodCodeLayout(CompilationUnit* cUnit)
+{
+ oatDataFlowAnalysisDispatcher(cUnit, layoutBlocks, kAllNodes, false);
+}
+
+void oatDumpCheckStats(CompilationUnit *cUnit)
+{
+ Checkstats* stats = (Checkstats*)oatNew(cUnit, sizeof(Checkstats), true, kAllocDFInfo);
+ cUnit->checkstats = stats;
+ oatDataFlowAnalysisDispatcher(cUnit, countChecks, kAllNodes, false /* isIterative */);
+ if (stats->nullChecks > 0) {
+ LOG(INFO) << "Null Checks: " << PrettyMethod(cUnit->method_idx, *cUnit->dex_file) << " "
+ << stats->nullChecksEliminated << " of " << stats->nullChecks << " -> "
+ << ((float)stats->nullChecksEliminated/(float)stats->nullChecks) * 100.0 << "%";
+ }
+ if (stats->rangeChecks > 0) {
+ LOG(INFO) << "Range Checks: " << PrettyMethod(cUnit->method_idx, *cUnit->dex_file) << " "
+ << stats->rangeChecksEliminated << " of " << stats->rangeChecks << " -> "
+ << ((float)stats->rangeChecksEliminated/(float)stats->rangeChecks) * 100.0 << "%";
+ }
+}
+
+void oatMethodBasicBlockOptimization(CompilationUnit *cUnit)
+{
+ if (!(cUnit->disableOpt & (1 << kBBOpt))) {
+ oatInitGrowableList(cUnit, &cUnit->compilerTemps, 6, kListMisc);
+ DCHECK_EQ(cUnit->numCompilerTemps, 0);
+ 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::FlagsOf(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->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