/*
 * 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 "compiler_internals.h"
#include "dataflow.h"
#include "bb_opt.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 oat_data_flow_attributes[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,

  // 112 MIR_CHECKPART2
  0,

  // 113 MIR_SELECT
  DF_DA | DF_UB,
};

/* Return the base virtual register for a SSA name */
int SRegToVReg(const CompilationUnit* cu, int ssa_reg)
{
  DCHECK_LT(ssa_reg, static_cast<int>(cu->ssa_base_vregs->num_used));
  return GET_ELEM_N(cu->ssa_base_vregs, int, ssa_reg);
}

int SRegToSubscript(const CompilationUnit* cu, int ssa_reg)
{
  DCHECK(ssa_reg < static_cast<int>(cu->ssa_subscripts->num_used));
  return GET_ELEM_N(cu->ssa_subscripts, int, ssa_reg);
}

static int GetSSAUseCount(CompilationUnit* cu, int s_reg)
{
  DCHECK(s_reg < static_cast<int>(cu->raw_use_counts.num_used));
  return cu->raw_use_counts.elem_list[s_reg];
}

static std::string GetSSAName(const CompilationUnit* cu, int ssa_reg)
{
  return StringPrintf("v%d_%d", SRegToVReg(cu, ssa_reg), SRegToSubscript(cu, ssa_reg));
}

// Similar to GetSSAName, but if ssa name represents an immediate show that as well.
static std::string GetSSANameWithConst(const CompilationUnit* cu, int ssa_reg, bool singles_only)
{
  if (cu->reg_location == NULL) {
    // Pre-SSA - just use the standard name
    return GetSSAName(cu, ssa_reg);
  }
  if (IsConst(cu, cu->reg_location[ssa_reg])) {
    if (!singles_only && cu->reg_location[ssa_reg].wide) {
      return StringPrintf("v%d_%d#0x%llx", SRegToVReg(cu, ssa_reg),
                          SRegToSubscript(cu, ssa_reg),
                          ConstantValueWide(cu, cu->reg_location[ssa_reg]));
    } else {
      return StringPrintf("v%d_%d#0x%x", SRegToVReg(cu, ssa_reg),
                          SRegToSubscript(cu, ssa_reg),
                          ConstantValue(cu, cu->reg_location[ssa_reg]));
    }
  } else {
    return StringPrintf("v%d_%d", SRegToVReg(cu, ssa_reg), SRegToSubscript(cu, ssa_reg));
  }
}


char* GetDalvikDisassembly(CompilationUnit* cu, const MIR* mir)
{
  DecodedInstruction insn = mir->dalvikInsn;
  std::string str;
  int flags = 0;
  int opcode = insn.opcode;
  char* ret;
  bool nop = false;
  SSARepresentation* ssa_rep = mir->ssa_rep;
  Instruction::Format dalvik_format = Instruction::k10x;  // Default to no-operand format
  int defs = (ssa_rep != NULL) ? ssa_rep->num_defs : 0;
  int uses = (ssa_rep != NULL) ? ssa_rep->num_uses : 0;

  // Handle special cases.
  if ((opcode == kMirOpCheck) || (opcode == kMirOpCheckPart2)) {
    str.append(extended_mir_op_names[opcode - kMirOpFirst]);
    str.append(": ");
    // Recover the original Dex instruction
    insn = mir->meta.throw_insn->dalvikInsn;
    ssa_rep = mir->meta.throw_insn->ssa_rep;
    defs = ssa_rep->num_defs;
    uses = ssa_rep->num_uses;
    opcode = insn.opcode;
  } else if (opcode == kMirOpNop) {
    str.append("[");
    insn.opcode = mir->meta.original_opcode;
    opcode = mir->meta.original_opcode;
    nop = true;
  }

  if (opcode >= kMirOpFirst) {
    str.append(extended_mir_op_names[opcode - kMirOpFirst]);
  } else {
    dalvik_format = Instruction::FormatOf(insn.opcode);
    flags = Instruction::FlagsOf(insn.opcode);
    str.append(Instruction::Name(insn.opcode));
  }

  if (opcode == kMirOpPhi) {
    int* incoming = reinterpret_cast<int*>(insn.vB);
    str.append(StringPrintf(" %s = (%s",
               GetSSANameWithConst(cu, ssa_rep->defs[0], true).c_str(),
               GetSSANameWithConst(cu, ssa_rep->uses[0], true).c_str()));
    str.append(StringPrintf(":%d",incoming[0]));
    int i;
    for (i = 1; i < uses; i++) {
      str.append(StringPrintf(", %s:%d",
                              GetSSANameWithConst(cu, ssa_rep->uses[i], true).c_str(),
                              incoming[i]));
    }
    str.append(")");
  } else if (flags & Instruction::kBranch) {
    // For branches, decode the instructions to print out the branch targets.
    int offset = 0;
    switch (dalvik_format) {
      case Instruction::k21t:
        str.append(StringPrintf(" %s,", GetSSANameWithConst(cu, ssa_rep->uses[0], false).c_str()));
        offset = insn.vB;
        break;
      case Instruction::k22t:
        str.append(StringPrintf(" %s, %s,", GetSSANameWithConst(cu, ssa_rep->uses[0], false).c_str(),
                   GetSSANameWithConst(cu, ssa_rep->uses[1], false).c_str()));
        offset = insn.vC;
        break;
      case Instruction::k10t:
      case Instruction::k20t:
      case Instruction::k30t:
        offset = insn.vA;
        break;
      default:
        LOG(FATAL) << "Unexpected branch format " << dalvik_format << " from " << insn.opcode;
    }
    str.append(StringPrintf(" 0x%x (%c%x)", mir->offset + offset,
                            offset > 0 ? '+' : '-', offset > 0 ? offset : -offset));
  } else {
    // For invokes-style formats, treat wide regs as a pair of singles
    bool show_singles = ((dalvik_format == Instruction::k35c) ||
                         (dalvik_format == Instruction::k3rc));
    if (defs != 0) {
      str.append(StringPrintf(" %s", GetSSANameWithConst(cu, ssa_rep->defs[0], false).c_str()));
      if (uses != 0) {
        str.append(", ");
      }
    }
    for (int i = 0; i < uses; i++) {
      str.append(
          StringPrintf(" %s", GetSSANameWithConst(cu, ssa_rep->uses[i], show_singles).c_str()));
      if (!show_singles && (cu->reg_location != NULL) && cu->reg_location[i].wide) {
        // For the listing, skip the high sreg.
        i++;
      }
      if (i != (uses -1)) {
        str.append(",");
      }
    }
    switch (dalvik_format) {
      case Instruction::k11n: // Add one immediate from vB
      case Instruction::k21s:
      case Instruction::k31i:
      case Instruction::k21h:
        str.append(StringPrintf(", #%d", insn.vB));
        break;
      case Instruction::k51l: // Add one wide immediate
        str.append(StringPrintf(", #%lld", insn.vB_wide));
        break;
      case Instruction::k21c: // One register, one string/type/method index
      case Instruction::k31c:
        str.append(StringPrintf(", index #%d", insn.vB));
        break;
      case Instruction::k22c: // Two registers, one string/type/method index
        str.append(StringPrintf(", index #%d", insn.vC));
        break;
      case Instruction::k22s: // Add one immediate from vC
      case Instruction::k22b:
        str.append(StringPrintf(", #%d", insn.vC));
        break;
      default:
        ; // Nothing left to print
      }
  }
  if (nop) {
    str.append("]--optimized away");
  }
  int length = str.length() + 1;
  ret = static_cast<char*>(NewMem(cu, length, false, kAllocDFInfo));
  strncpy(ret, str.c_str(), length);
  return ret;
}

/* Any register that is used before being defined is considered live-in */
static void HandleLiveInUse(CompilationUnit* cu, ArenaBitVector* use_v, ArenaBitVector* def_v,
                            ArenaBitVector* live_in_v, int dalvik_reg_id)
{
  SetBit(cu, use_v, dalvik_reg_id);
  if (!IsBitSet(def_v, dalvik_reg_id)) {
    SetBit(cu, live_in_v, dalvik_reg_id);
  }
}

/* Mark a reg as being defined */
static void HandleDef(CompilationUnit* cu, ArenaBitVector* def_v, int dalvik_reg_id)
{
  SetBit(cu, def_v, dalvik_reg_id);
}

/*
 * 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 FindLocalLiveIn(CompilationUnit* cu, BasicBlock* bb)
{
  MIR* mir;
  ArenaBitVector *use_v, *def_v, *live_in_v;

  if (bb->data_flow_info == NULL) return false;

  use_v = bb->data_flow_info->use_v =
      AllocBitVector(cu, cu->num_dalvik_registers, false, kBitMapUse);
  def_v = bb->data_flow_info->def_v =
      AllocBitVector(cu, cu->num_dalvik_registers, false, kBitMapDef);
  live_in_v = bb->data_flow_info->live_in_v =
      AllocBitVector(cu, cu->num_dalvik_registers, false,
                        kBitMapLiveIn);

  for (mir = bb->first_mir_insn; mir != NULL; mir = mir->next) {
    int df_attributes = oat_data_flow_attributes[mir->dalvikInsn.opcode];
    DecodedInstruction *d_insn = &mir->dalvikInsn;

    if (df_attributes & DF_HAS_USES) {
      if (df_attributes & DF_UA) {
        HandleLiveInUse(cu, use_v, def_v, live_in_v, d_insn->vA);
        if (df_attributes & DF_A_WIDE) {
          HandleLiveInUse(cu, use_v, def_v, live_in_v, d_insn->vA+1);
        }
      }
      if (df_attributes & DF_UB) {
        HandleLiveInUse(cu, use_v, def_v, live_in_v, d_insn->vB);
        if (df_attributes & DF_B_WIDE) {
          HandleLiveInUse(cu, use_v, def_v, live_in_v, d_insn->vB+1);
        }
      }
      if (df_attributes & DF_UC) {
        HandleLiveInUse(cu, use_v, def_v, live_in_v, d_insn->vC);
        if (df_attributes & DF_C_WIDE) {
          HandleLiveInUse(cu, use_v, def_v, live_in_v, d_insn->vC+1);
        }
      }
    }
    if (df_attributes & DF_FORMAT_35C) {
      for (unsigned int i = 0; i < d_insn->vA; i++) {
        HandleLiveInUse(cu, use_v, def_v, live_in_v, d_insn->arg[i]);
      }
    }
    if (df_attributes & DF_FORMAT_3RC) {
      for (unsigned int i = 0; i < d_insn->vA; i++) {
        HandleLiveInUse(cu, use_v, def_v, live_in_v, d_insn->vC+i);
      }
    }
    if (df_attributes & DF_HAS_DEFS) {
      HandleDef(cu, def_v, d_insn->vA);
      if (df_attributes & DF_A_WIDE) {
        HandleDef(cu, def_v, d_insn->vA+1);
      }
    }
  }
  return true;
}

static int AddNewSReg(CompilationUnit* cu, int v_reg)
{
  // Compiler temps always have a subscript of 0
  int subscript = (v_reg < 0) ? 0 : ++cu->ssa_last_defs[v_reg];
  int ssa_reg = cu->num_ssa_regs++;
  InsertGrowableList(cu, cu->ssa_base_vregs, v_reg);
  InsertGrowableList(cu, cu->ssa_subscripts, subscript);
  std::string ssa_name = GetSSAName(cu, ssa_reg);
  char* name = static_cast<char*>(NewMem(cu, ssa_name.length() + 1, false, kAllocDFInfo));
  strncpy(name, ssa_name.c_str(), ssa_name.length() + 1);
  InsertGrowableList(cu, cu->ssa_strings, reinterpret_cast<uintptr_t>(name));
  DCHECK_EQ(cu->ssa_base_vregs->num_used, cu->ssa_subscripts->num_used);
  return ssa_reg;
}

/* Find out the latest SSA register for a given Dalvik register */
static void HandleSSAUse(CompilationUnit* cu, int* uses, int dalvik_reg, int reg_index)
{
  DCHECK((dalvik_reg >= 0) && (dalvik_reg < cu->num_dalvik_registers));
  uses[reg_index] = cu->vreg_to_ssa_map[dalvik_reg];
}

/* Setup a new SSA register for a given Dalvik register */
static void HandleSSADef(CompilationUnit* cu, int* defs, int dalvik_reg, int reg_index)
{
  DCHECK((dalvik_reg >= 0) && (dalvik_reg < cu->num_dalvik_registers));
  int ssa_reg = AddNewSReg(cu, dalvik_reg);
  cu->vreg_to_ssa_map[dalvik_reg] = ssa_reg;
  defs[reg_index] = ssa_reg;
}

/* Look up new SSA names for format_35c instructions */
static void DataFlowSSAFormat35C(CompilationUnit* cu, MIR* mir)
{
  DecodedInstruction *d_insn = &mir->dalvikInsn;
  int num_uses = d_insn->vA;
  int i;

  mir->ssa_rep->num_uses = num_uses;
  mir->ssa_rep->uses = static_cast<int*>(NewMem(cu, sizeof(int) * num_uses, true, kAllocDFInfo));
  // NOTE: will be filled in during type & size inference pass
  mir->ssa_rep->fp_use = static_cast<bool*>(NewMem(cu, sizeof(bool) * num_uses, true,
                                                 kAllocDFInfo));

  for (i = 0; i < num_uses; i++) {
    HandleSSAUse(cu, mir->ssa_rep->uses, d_insn->arg[i], i);
  }
}

/* Look up new SSA names for format_3rc instructions */
static void DataFlowSSAFormat3RC(CompilationUnit* cu, MIR* mir)
{
  DecodedInstruction *d_insn = &mir->dalvikInsn;
  int num_uses = d_insn->vA;
  int i;

  mir->ssa_rep->num_uses = num_uses;
  mir->ssa_rep->uses = static_cast<int*>(NewMem(cu, sizeof(int) * num_uses, true, kAllocDFInfo));
  // NOTE: will be filled in during type & size inference pass
  mir->ssa_rep->fp_use = static_cast<bool*>(NewMem(cu, sizeof(bool) * num_uses, true,
                                                 kAllocDFInfo));

  for (i = 0; i < num_uses; i++) {
    HandleSSAUse(cu, mir->ssa_rep->uses, d_insn->vC+i, i);
  }
}

/* Entry function to convert a block into SSA representation */
bool DoSSAConversion(CompilationUnit* cu, BasicBlock* bb)
{
  MIR* mir;

  if (bb->data_flow_info == NULL) return false;

  for (mir = bb->first_mir_insn; mir != NULL; mir = mir->next) {
    mir->ssa_rep = static_cast<struct SSARepresentation *>(NewMem(cu, sizeof(SSARepresentation),
                                                                 true, kAllocDFInfo));

    int df_attributes = oat_data_flow_attributes[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) {
        cu->attrs &= ~METHOD_IS_THROW_FREE;
      }

      if (flags & Instruction::kInvoke) {
        cu->attrs &= ~METHOD_IS_LEAF;
      }
    }

    int num_uses = 0;

    if (df_attributes & DF_FORMAT_35C) {
      DataFlowSSAFormat35C(cu, mir);
      continue;
    }

    if (df_attributes & DF_FORMAT_3RC) {
      DataFlowSSAFormat3RC(cu, mir);
      continue;
    }

    if (df_attributes & DF_HAS_USES) {
      if (df_attributes & DF_UA) {
        num_uses++;
        if (df_attributes & DF_A_WIDE) {
          num_uses ++;
        }
      }
      if (df_attributes & DF_UB) {
        num_uses++;
        if (df_attributes & DF_B_WIDE) {
          num_uses ++;
        }
      }
      if (df_attributes & DF_UC) {
        num_uses++;
        if (df_attributes & DF_C_WIDE) {
          num_uses ++;
        }
      }
    }

    if (num_uses) {
      mir->ssa_rep->num_uses = num_uses;
      mir->ssa_rep->uses = static_cast<int*>(NewMem(cu, sizeof(int) * num_uses, false,
                                                   kAllocDFInfo));
      mir->ssa_rep->fp_use = static_cast<bool*>(NewMem(cu, sizeof(bool) * num_uses, false,
                                                     kAllocDFInfo));
    }

    int num_defs = 0;

    if (df_attributes & DF_HAS_DEFS) {
      num_defs++;
      if (df_attributes & DF_A_WIDE) {
        num_defs++;
      }
    }

    if (num_defs) {
      mir->ssa_rep->num_defs = num_defs;
      mir->ssa_rep->defs = static_cast<int*>(NewMem(cu, sizeof(int) * num_defs, false,
                                                   kAllocDFInfo));
      mir->ssa_rep->fp_def = static_cast<bool*>(NewMem(cu, sizeof(bool) * num_defs, false,
                                                     kAllocDFInfo));
    }

    DecodedInstruction *d_insn = &mir->dalvikInsn;

    if (df_attributes & DF_HAS_USES) {
      num_uses = 0;
      if (df_attributes & DF_UA) {
        mir->ssa_rep->fp_use[num_uses] = df_attributes & DF_FP_A;
        HandleSSAUse(cu, mir->ssa_rep->uses, d_insn->vA, num_uses++);
        if (df_attributes & DF_A_WIDE) {
          mir->ssa_rep->fp_use[num_uses] = df_attributes & DF_FP_A;
          HandleSSAUse(cu, mir->ssa_rep->uses, d_insn->vA+1, num_uses++);
        }
      }
      if (df_attributes & DF_UB) {
        mir->ssa_rep->fp_use[num_uses] = df_attributes & DF_FP_B;
        HandleSSAUse(cu, mir->ssa_rep->uses, d_insn->vB, num_uses++);
        if (df_attributes & DF_B_WIDE) {
          mir->ssa_rep->fp_use[num_uses] = df_attributes & DF_FP_B;
          HandleSSAUse(cu, mir->ssa_rep->uses, d_insn->vB+1, num_uses++);
        }
      }
      if (df_attributes & DF_UC) {
        mir->ssa_rep->fp_use[num_uses] = df_attributes & DF_FP_C;
        HandleSSAUse(cu, mir->ssa_rep->uses, d_insn->vC, num_uses++);
        if (df_attributes & DF_C_WIDE) {
          mir->ssa_rep->fp_use[num_uses] = df_attributes & DF_FP_C;
          HandleSSAUse(cu, mir->ssa_rep->uses, d_insn->vC+1, num_uses++);
        }
      }
    }
    if (df_attributes & DF_HAS_DEFS) {
      mir->ssa_rep->fp_def[0] = df_attributes & DF_FP_A;
      HandleSSADef(cu, mir->ssa_rep->defs, d_insn->vA, 0);
      if (df_attributes & DF_A_WIDE) {
        mir->ssa_rep->fp_def[1] = df_attributes & DF_FP_A;
        HandleSSADef(cu, mir->ssa_rep->defs, d_insn->vA+1, 1);
      }
    }
  }

  if (!cu->disable_dataflow) {
    /*
     * 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->data_flow_info->vreg_to_ssa_map =
        static_cast<int*>(NewMem(cu, sizeof(int) * cu->num_dalvik_registers, false,
                                 kAllocDFInfo));

    memcpy(bb->data_flow_info->vreg_to_ssa_map, cu->vreg_to_ssa_map,
           sizeof(int) * cu->num_dalvik_registers);
  }
  return true;
}

/* Setup a constant value for opcodes thare have the DF_SETS_CONST attribute */
static void SetConstant(CompilationUnit* cu, int32_t ssa_reg, int value)
{
  SetBit(cu, cu->is_constant_v, ssa_reg);
  cu->constant_values[ssa_reg] = value;
}

static void SetConstantWide(CompilationUnit* cu, int ssa_reg, int64_t value)
{
  SetBit(cu, cu->is_constant_v, ssa_reg);
  cu->constant_values[ssa_reg] = Low32Bits(value);
  cu->constant_values[ssa_reg + 1] = High32Bits(value);
}

bool DoConstantPropogation(CompilationUnit* cu, BasicBlock* bb)
{
  MIR* mir;
  ArenaBitVector *is_constant_v = cu->is_constant_v;

  for (mir = bb->first_mir_insn; mir != NULL; mir = mir->next) {
    int df_attributes = oat_data_flow_attributes[mir->dalvikInsn.opcode];

    DecodedInstruction *d_insn = &mir->dalvikInsn;

    if (!(df_attributes & DF_HAS_DEFS)) continue;

    /* Handle instructions that set up constants directly */
    if (df_attributes & DF_SETS_CONST) {
      if (df_attributes & DF_DA) {
        int32_t vB = static_cast<int32_t>(d_insn->vB);
        switch (d_insn->opcode) {
          case Instruction::CONST_4:
          case Instruction::CONST_16:
          case Instruction::CONST:
            SetConstant(cu, mir->ssa_rep->defs[0], vB);
            break;
          case Instruction::CONST_HIGH16:
            SetConstant(cu, mir->ssa_rep->defs[0], vB << 16);
            break;
          case Instruction::CONST_WIDE_16:
          case Instruction::CONST_WIDE_32:
            SetConstantWide(cu, mir->ssa_rep->defs[0], static_cast<int64_t>(vB));
            break;
          case Instruction::CONST_WIDE:
            SetConstantWide(cu, mir->ssa_rep->defs[0],d_insn->vB_wide);
            break;
          case Instruction::CONST_WIDE_HIGH16:
            SetConstantWide(cu, mir->ssa_rep->defs[0], static_cast<int64_t>(vB) << 48);
            break;
          default:
            break;
        }
      }
      /* Handle instructions that set up constants directly */
    } else if (df_attributes & DF_IS_MOVE) {
      int i;

      for (i = 0; i < mir->ssa_rep->num_uses; i++) {
        if (!IsBitSet(is_constant_v, mir->ssa_rep->uses[i])) break;
      }
      /* Move a register holding a constant to another register */
      if (i == mir->ssa_rep->num_uses) {
        SetConstant(cu, mir->ssa_rep->defs[0],
                    cu->constant_values[mir->ssa_rep->uses[0]]);
        if (df_attributes & DF_A_WIDE) {
          SetConstant(cu, mir->ssa_rep->defs[1],
                      cu->constant_values[mir->ssa_rep->uses[1]]);
        }
      }
    } else if (df_attributes & DF_NULL_TRANSFER_N) {
      /*
       * Mark const sregs that appear in merges.  Need to flush those to home location.
       * TUNING: instead of flushing on def, we could insert a flush on the appropriate
       * edge[s].
       */
      DCHECK_EQ(static_cast<int32_t>(d_insn->opcode), kMirOpPhi);
      for (int i = 0; i < mir->ssa_rep->num_uses; i++) {
        if (IsConst(cu, mir->ssa_rep->uses[i])) {
          SetBit(cu, cu->must_flush_constant_v, mir->ssa_rep->uses[i]);
        }
      }
    }
  }
  /* TODO: implement code to handle arithmetic operations */
  return true;
}

/* Setup the basic data structures for SSA conversion */
void CompilerInitializeSSAConversion(CompilationUnit* cu)
{
  int i;
  int num_dalvik_reg = cu->num_dalvik_registers;

  cu->ssa_base_vregs =
      static_cast<GrowableList*>(NewMem(cu, sizeof(GrowableList), false, kAllocDFInfo));
  cu->ssa_subscripts =
      static_cast<GrowableList*>(NewMem(cu, sizeof(GrowableList), false, kAllocDFInfo));
  cu->ssa_strings =
      static_cast<GrowableList*>(NewMem(cu, sizeof(GrowableList), false, kAllocDFInfo));
  // Create the ssa mappings, estimating the max size
  CompilerInitGrowableList(cu, cu->ssa_base_vregs,
                      num_dalvik_reg + cu->def_count + 128,
                      kListSSAtoDalvikMap);
  CompilerInitGrowableList(cu, cu->ssa_subscripts,
                      num_dalvik_reg + cu->def_count + 128,
                      kListSSAtoDalvikMap);
  CompilerInitGrowableList(cu, cu->ssa_strings,
                      num_dalvik_reg + cu->def_count + 128,
                      kListSSAtoDalvikMap);
  /*
   * Initial number of SSA registers is equal to the number of Dalvik
   * registers.
   */
  cu->num_ssa_regs = num_dalvik_reg;

  /*
   * Initialize the SSA2Dalvik map list. For the first num_dalvik_reg 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 < num_dalvik_reg; i++) {
    InsertGrowableList(cu, cu->ssa_base_vregs, i);
    InsertGrowableList(cu, cu->ssa_subscripts, 0);
    std::string ssa_name = GetSSAName(cu, i);
    char* name = static_cast<char*>(NewMem(cu, ssa_name.length() + 1, true, kAllocDFInfo));
    strncpy(name, ssa_name.c_str(), ssa_name.length() + 1);
    InsertGrowableList(cu, cu->ssa_strings, reinterpret_cast<uintptr_t>(name));
  }

  /*
   * Initialize the DalvikToSSAMap map. There is one entry for each
   * Dalvik register, and the SSA names for those are the same.
   */
  cu->vreg_to_ssa_map =
      static_cast<int*>(NewMem(cu, sizeof(int) * num_dalvik_reg, false, kAllocDFInfo));
  /* Keep track of the higest def for each dalvik reg */
  cu->ssa_last_defs =
      static_cast<int*>(NewMem(cu, sizeof(int) * num_dalvik_reg, false, kAllocDFInfo));

  for (i = 0; i < num_dalvik_reg; i++) {
    cu->vreg_to_ssa_map[i] = i;
    cu->ssa_last_defs[i] = 0;
  }

  /* Add ssa reg for Method* */
  cu->method_sreg = AddNewSReg(cu, SSA_METHOD_BASEREG);

  /*
   * Allocate the BasicBlockDataFlow structure for the entry and code blocks
   */
  GrowableListIterator iterator;

  GrowableListIteratorInit(&cu->block_list, &iterator);

  while (true) {
    BasicBlock* bb = reinterpret_cast<BasicBlock*>(GrowableListIteratorNext(&iterator));
    if (bb == NULL) break;
    if (bb->hidden == true) continue;
    if (bb->block_type == kDalvikByteCode ||
      bb->block_type == kEntryBlock ||
      bb->block_type == kExitBlock) {
      bb->data_flow_info = static_cast<BasicBlockDataFlow*>(NewMem(cu, sizeof(BasicBlockDataFlow),
                                                                 true, kAllocDFInfo));
      }
  }
}

/* Clear the visited flag for each BB */
bool ClearVisitedFlag(struct CompilationUnit* cu, struct BasicBlock* bb)
{
  bb->visited = false;
  return true;
}

void DataFlowAnalysisDispatcher(CompilationUnit* cu,
                                   bool (*func)(CompilationUnit*, BasicBlock*),
                                   DataFlowAnalysisMode dfa_mode,
                                   bool is_iterative)
{
  bool change = true;

  while (change) {
    change = false;

    switch (dfa_mode) {
      /* Scan all blocks and perform the operations specified in func */
      case kAllNodes:
        {
          GrowableListIterator iterator;
          GrowableListIteratorInit(&cu->block_list, &iterator);
          while (true) {
            BasicBlock* bb = reinterpret_cast<BasicBlock*>(GrowableListIteratorNext(&iterator));
            if (bb == NULL) break;
            if (bb->hidden == true) continue;
              change |= (*func)(cu, bb);
          }
        }
        break;
      /* Scan reachable blocks and perform the ops specified in func. */
      case kReachableNodes:
        {
          int num_reachable_blocks = cu->num_reachable_blocks;
          int idx;
          const GrowableList *block_list = &cu->block_list;

          for (idx = 0; idx < num_reachable_blocks; idx++) {
            int block_idx = cu->dfs_order.elem_list[idx];
            BasicBlock* bb =
                reinterpret_cast<BasicBlock*>( GrowableListGetElement(block_list, block_idx));
            change |= (*func)(cu, bb);
          }
        }
        break;

      /* Scan reachable blocks by pre-order dfs and invoke func on each. */
      case kPreOrderDFSTraversal:
        {
          int num_reachable_blocks = cu->num_reachable_blocks;
          int idx;
          const GrowableList *block_list = &cu->block_list;

          for (idx = 0; idx < num_reachable_blocks; idx++) {
            int dfs_idx = cu->dfs_order.elem_list[idx];
            BasicBlock* bb =
                reinterpret_cast<BasicBlock*>(GrowableListGetElement(block_list, dfs_idx));
            change |= (*func)(cu, bb);
            }
        }
        break;
      /* Scan reachable blocks post-order dfs and invoke func on each. */
      case kPostOrderDFSTraversal:
        {
          int num_reachable_blocks = cu->num_reachable_blocks;
          int idx;
          const GrowableList *block_list = &cu->block_list;

          for (idx = num_reachable_blocks - 1; idx >= 0; idx--) {
            int dfs_idx = cu->dfs_order.elem_list[idx];
            BasicBlock* bb =
                reinterpret_cast<BasicBlock *>( GrowableListGetElement(block_list, dfs_idx));
            change |= (*func)(cu, bb);
            }
        }
        break;
      /* Scan reachable post-order dom tree and invoke func on each. */
      case kPostOrderDOMTraversal:
        {
          int num_reachable_blocks = cu->num_reachable_blocks;
          int idx;
          const GrowableList *block_list = &cu->block_list;

          for (idx = 0; idx < num_reachable_blocks; idx++) {
            int dom_idx = cu->dom_post_order_traversal.elem_list[idx];
            BasicBlock* bb =
                reinterpret_cast<BasicBlock*>( GrowableListGetElement(block_list, dom_idx));
            change |= (*func)(cu, bb);
          }
        }
        break;
      /* Scan reachable blocks reverse post-order dfs, invoke func on each */
      case kReversePostOrderTraversal:
        {
          int num_reachable_blocks = cu->num_reachable_blocks;
          int idx;
          const GrowableList *block_list = &cu->block_list;

          for (idx = num_reachable_blocks - 1; idx >= 0; idx--) {
            int rev_idx = cu->dfs_post_order.elem_list[idx];
            BasicBlock* bb =
                reinterpret_cast<BasicBlock*>(GrowableListGetElement(block_list, rev_idx));
            change |= (*func)(cu, bb);
            }
        }
        break;
      default:
        LOG(FATAL) << "Unknown traversal mode: " << dfa_mode;
    }
    /* If is_iterative is false, exit the loop after the first iteration */
    change &= is_iterative;
  }
}

/* Advance to next strictly dominated MIR node in an extended basic block */
static MIR* AdvanceMIR(CompilationUnit* cu, BasicBlock** p_bb, MIR* mir)
{
  BasicBlock* bb = *p_bb;
  if (mir != NULL) {
    mir = mir->next;
    if (mir == NULL) {
      bb = bb->fall_through;
      if ((bb == NULL) || Predecessors(bb) != 1) {
        mir = NULL;
      } else {
      *p_bb = bb;
      mir = bb->first_mir_insn;
      }
    }
  }
  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* FindMoveResult(CompilationUnit* cu, BasicBlock* bb, MIR* mir)
{
  BasicBlock* tbb = bb;
  mir = AdvanceMIR(cu, &tbb, mir);
  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(cu, &tbb, mir);
    }
  }
  return mir;
}

static BasicBlock* NextDominatedBlock(CompilationUnit* cu, BasicBlock* bb)
{
  if (bb->block_type == kDead) {
    return NULL;
  }
  DCHECK((bb->block_type == kEntryBlock) || (bb->block_type == kDalvikByteCode)
      || (bb->block_type == kExitBlock));
  bb = bb->fall_through;
  if (bb == NULL || (Predecessors(bb) != 1)) {
    return NULL;
  }
  DCHECK((bb->block_type == kDalvikByteCode) || (bb->block_type == kExitBlock));
  return bb;
}

static MIR* FindPhi(CompilationUnit* cu, BasicBlock* bb, int ssa_name)
{
  for (MIR* mir = bb->first_mir_insn; mir != NULL; mir = mir->next) {
    if (static_cast<int>(mir->dalvikInsn.opcode) == kMirOpPhi) {
      for (int i = 0; i < mir->ssa_rep->num_uses; i++) {
        if (mir->ssa_rep->uses[i] == ssa_name) {
          return mir;
        }
      }
    }
  }
  return NULL;
}

static SelectInstructionKind SelectKind(MIR* mir)
{
  switch (mir->dalvikInsn.opcode) {
    case Instruction::MOVE:
    case Instruction::MOVE_OBJECT:
    case Instruction::MOVE_16:
    case Instruction::MOVE_OBJECT_16:
    case Instruction::MOVE_FROM16:
    case Instruction::MOVE_OBJECT_FROM16:
      return kSelectMove;
   case Instruction::CONST:
   case Instruction::CONST_4:
   case Instruction::CONST_16:
      return kSelectConst;
   case Instruction::GOTO:
   case Instruction::GOTO_16:
   case Instruction::GOTO_32:
      return kSelectGoto;
   default:;
  }
  return kSelectNone;
}

/* Do some MIR-level extended basic block optimizations */
static bool BasicBlockOpt(CompilationUnit* cu, BasicBlock* bb)
{
  if (bb->block_type == kDead) {
    return true;
  }
  int num_temps = 0;
  BBOpt bb_opt(cu);
  while (bb != NULL) {
    for (MIR* mir = bb->first_mir_insn; mir != NULL; mir = mir->next) {
      // TUNING: use the returned value number for CSE.
      bb_opt.GetValueNumber(mir);
      // Look for interesting opcodes, skip otherwise
      Instruction::Code opcode = mir->dalvikInsn.opcode;
      switch (opcode) {
        case Instruction::CMPL_FLOAT:
        case Instruction::CMPL_DOUBLE:
        case Instruction::CMPG_FLOAT:
        case Instruction::CMPG_DOUBLE:
        case Instruction::CMP_LONG:
          if (cu->gen_bitcode) {
            // Bitcode doesn't allow this optimization.
            break;
          }
          if (mir->next != NULL) {
            MIR* mir_next = mir->next;
            Instruction::Code br_opcode = mir_next->dalvikInsn.opcode;
            ConditionCode ccode = kCondNv;
            switch(br_opcode) {
              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->ssa_rep->defs[0] == mir_next->ssa_rep->uses[0]) &&
                (GetSSAUseCount(cu, mir->ssa_rep->defs[0]) == 1)) {
              mir_next->dalvikInsn.arg[0] = ccode;
              switch(opcode) {
                case Instruction::CMPL_FLOAT:
                  mir_next->dalvikInsn.opcode =
                      static_cast<Instruction::Code>(kMirOpFusedCmplFloat);
                  break;
                case Instruction::CMPL_DOUBLE:
                  mir_next->dalvikInsn.opcode =
                      static_cast<Instruction::Code>(kMirOpFusedCmplDouble);
                  break;
                case Instruction::CMPG_FLOAT:
                  mir_next->dalvikInsn.opcode =
                      static_cast<Instruction::Code>(kMirOpFusedCmpgFloat);
                  break;
                case Instruction::CMPG_DOUBLE:
                  mir_next->dalvikInsn.opcode =
                      static_cast<Instruction::Code>(kMirOpFusedCmpgDouble);
                  break;
                case Instruction::CMP_LONG:
                  mir_next->dalvikInsn.opcode =
                      static_cast<Instruction::Code>(kMirOpFusedCmpLong);
                  break;
                default: LOG(ERROR) << "Unexpected opcode: " << opcode;
              }
              mir->dalvikInsn.opcode = static_cast<Instruction::Code>(kMirOpNop);
              mir_next->ssa_rep->num_uses = mir->ssa_rep->num_uses;
              mir_next->ssa_rep->uses = mir->ssa_rep->uses;
              mir_next->ssa_rep->fp_use = mir->ssa_rep->fp_use;
              mir_next->ssa_rep->num_defs = 0;
              mir->ssa_rep->num_uses = 0;
              mir->ssa_rep->num_defs = 0;
            }
          }
          break;
        case Instruction::GOTO:
        case Instruction::GOTO_16:
        case Instruction::GOTO_32:
        case Instruction::IF_EQ:
        case Instruction::IF_NE:
        case Instruction::IF_LT:
        case Instruction::IF_GE:
        case Instruction::IF_GT:
        case Instruction::IF_LE:
        case Instruction::IF_EQZ:
        case Instruction::IF_NEZ:
        case Instruction::IF_LTZ:
        case Instruction::IF_GEZ:
        case Instruction::IF_GTZ:
        case Instruction::IF_LEZ:
          if (bb->taken->dominates_return) {
            mir->optimization_flags |= MIR_IGNORE_SUSPEND_CHECK;
            if (cu->verbose) {
              LOG(INFO) << "Suppressed suspend check on branch to return at 0x" << std::hex << mir->offset;
            }
          }
          break;
        default:
          break;
      }
      // Is this the select pattern?
      // TODO: flesh out support for Mips and X86.  NOTE: llvm's select op doesn't quite work here.
      // TUNING: expand to support IF_xx compare & branches
      if (!cu->gen_bitcode && (cu->instruction_set == kThumb2) &&
          ((mir->dalvikInsn.opcode == Instruction::IF_EQZ) ||
          (mir->dalvikInsn.opcode == Instruction::IF_NEZ))) {
        BasicBlock* ft = bb->fall_through;
        DCHECK(ft != NULL);
        BasicBlock* ft_ft = ft->fall_through;
        BasicBlock* ft_tk = ft->taken;

        BasicBlock* tk = bb->taken;
        DCHECK(tk != NULL);
        BasicBlock* tk_ft = tk->fall_through;
        BasicBlock* tk_tk = tk->taken;

        /*
         * In the select pattern, the taken edge goes to a block that unconditionally
         * transfers to the rejoin block and the fall_though edge goes to a block that
         * unconditionally falls through to the rejoin block.
         */
        if ((tk_ft == NULL) && (ft_tk == NULL) && (tk_tk == ft_ft) &&
            (Predecessors(tk) == 1) && (Predecessors(ft) == 1)) {
          /*
           * Okay - we have the basic diamond shape.  At the very least, we can eliminate the
           * suspend check on the taken-taken branch back to the join point.
           */
          if (SelectKind(tk->last_mir_insn) == kSelectGoto) {
              tk->last_mir_insn->optimization_flags |= (MIR_IGNORE_SUSPEND_CHECK);
          }
          // Are the block bodies something we can handle?
          if ((ft->first_mir_insn == ft->last_mir_insn) &&
              (tk->first_mir_insn != tk->last_mir_insn) &&
              (tk->first_mir_insn->next == tk->last_mir_insn) &&
              ((SelectKind(ft->first_mir_insn) == kSelectMove) ||
              (SelectKind(ft->first_mir_insn) == kSelectConst)) &&
              (SelectKind(ft->first_mir_insn) == SelectKind(tk->first_mir_insn)) &&
              (SelectKind(tk->last_mir_insn) == kSelectGoto)) {
            // Almost there.  Are the instructions targeting the same vreg?
            MIR* if_true = tk->first_mir_insn;
            MIR* if_false = ft->first_mir_insn;
            // It's possible that the target of the select isn't used - skip those (rare) cases.
            MIR* phi = FindPhi(cu, tk_tk, if_true->ssa_rep->defs[0]);
            if ((phi != NULL) && (if_true->dalvikInsn.vA == if_false->dalvikInsn.vA)) {
              /*
               * We'll convert the IF_EQZ/IF_NEZ to a SELECT.  We need to find the
               * Phi node in the merge block and delete it (while using the SSA name
               * of the merge as the target of the SELECT.  Delete both taken and
               * fallthrough blocks, and set fallthrough to merge block.
               * NOTE: not updating other dataflow info (no longer used at this point).
               * If this changes, need to update i_dom, etc. here (and in CombineBlocks).
               */
              if (opcode == Instruction::IF_NEZ) {
                // Normalize.
                MIR* tmp_mir = if_true;
                if_true = if_false;
                if_false = tmp_mir;
              }
              mir->dalvikInsn.opcode = static_cast<Instruction::Code>(kMirOpSelect);
              bool const_form = (SelectKind(if_true) == kSelectConst);
              if ((SelectKind(if_true) == kSelectMove)) {
                if (IsConst(cu, if_true->ssa_rep->uses[0]) &&
                    IsConst(cu, if_false->ssa_rep->uses[0])) {
                    const_form = true;
                    if_true->dalvikInsn.vB = ConstantValue(cu, if_true->ssa_rep->uses[0]);
                    if_false->dalvikInsn.vB = ConstantValue(cu, if_false->ssa_rep->uses[0]);
                }
              }
              if (const_form) {
                // "true" set val in vB
                mir->dalvikInsn.vB = if_true->dalvikInsn.vB;
                // "false" set val in vC
                mir->dalvikInsn.vC = if_false->dalvikInsn.vB;
              } else {
                DCHECK_EQ(SelectKind(if_true), kSelectMove);
                DCHECK_EQ(SelectKind(if_false), kSelectMove);
                int* src_ssa = static_cast<int*>(NewMem(cu, sizeof(int) * 3, false,
                                                 kAllocDFInfo));
                src_ssa[0] = mir->ssa_rep->uses[0];
                src_ssa[1] = if_true->ssa_rep->uses[0];
                src_ssa[2] = if_false->ssa_rep->uses[0];
                mir->ssa_rep->uses = src_ssa;
                mir->ssa_rep->num_uses = 3;
              }
              mir->ssa_rep->num_defs = 1;
              mir->ssa_rep->defs = static_cast<int*>(NewMem(cu, sizeof(int) * 1, false,
                                                     kAllocDFInfo));
              mir->ssa_rep->fp_def = static_cast<bool*>(NewMem(cu, sizeof(bool) * 1, false,
                                                     kAllocDFInfo));
              mir->ssa_rep->fp_def[0] = if_true->ssa_rep->fp_def[0];
              /*
               * There is usually a Phi node in the join block for our two cases.  If the
               * Phi node only contains our two cases as input, we will use the result
               * SSA name of the Phi node as our select result and delete the Phi.  If
               * the Phi node has more than two operands, we will arbitrarily use the SSA
               * name of the "true" path, delete the SSA name of the "false" path from the
               * Phi node (and fix up the incoming arc list).
               */
              if (phi->ssa_rep->num_uses == 2) {
                mir->ssa_rep->defs[0] = phi->ssa_rep->defs[0];
                phi->dalvikInsn.opcode = static_cast<Instruction::Code>(kMirOpNop);
              } else {
                int dead_def = if_false->ssa_rep->defs[0];
                int live_def = if_true->ssa_rep->defs[0];
                mir->ssa_rep->defs[0] = live_def;
                int* incoming = reinterpret_cast<int*>(phi->dalvikInsn.vB);
                for (int i = 0; i < phi->ssa_rep->num_uses; i++) {
                  if (phi->ssa_rep->uses[i] == live_def) {
                    incoming[i] = bb->id;
                  }
                }
                for (int i = 0; i < phi->ssa_rep->num_uses; i++) {
                  if (phi->ssa_rep->uses[i] == dead_def) {
                    int last_slot = phi->ssa_rep->num_uses - 1;
                    phi->ssa_rep->uses[i] = phi->ssa_rep->uses[last_slot];
                    incoming[i] = incoming[last_slot];
                  }
                }
              }
              phi->ssa_rep->num_uses--;
              bb->taken = NULL;
              tk->block_type = kDead;
              for (MIR* tmir = ft->first_mir_insn; tmir != NULL; tmir = tmir->next) {
                tmir->dalvikInsn.opcode = static_cast<Instruction::Code>(kMirOpNop);
              }
            }
          }
        }
      }
    }
    bb = NextDominatedBlock(cu, bb);
  }

  if (num_temps > cu->num_compiler_temps) {
    cu->num_compiler_temps = num_temps;
  }
  return true;
}

static bool NullCheckEliminationInit(struct CompilationUnit* cu, struct BasicBlock* bb)
{
  if (bb->data_flow_info == NULL) return false;
  bb->data_flow_info->ending_null_check_v =
      AllocBitVector(cu, cu->num_ssa_regs, false, kBitMapNullCheck);
  ClearAllBits(bb->data_flow_info->ending_null_check_v);
  return true;
}

/* Collect stats on number of checks removed */
static bool CountChecks( struct CompilationUnit* cu, struct BasicBlock* bb)
{
  if (bb->data_flow_info == NULL) return false;
  for (MIR* mir = bb->first_mir_insn; mir != NULL; mir = mir->next) {
    if (mir->ssa_rep == NULL) {
      continue;
    }
    int df_attributes = oat_data_flow_attributes[mir->dalvikInsn.opcode];
    if (df_attributes & DF_HAS_NULL_CHKS) {
      cu->checkstats->null_checks++;
      if (mir->optimization_flags & MIR_IGNORE_NULL_CHECK) {
        cu->checkstats->null_checks_eliminated++;
      }
    }
    if (df_attributes & DF_HAS_RANGE_CHKS) {
      cu->checkstats->range_checks++;
      if (mir->optimization_flags & MIR_IGNORE_RANGE_CHECK) {
        cu->checkstats->range_checks_eliminated++;
      }
    }
  }
  return false;
}

/* Try to make common case the fallthrough path */
static bool LayoutBlocks(struct CompilationUnit* cu, struct BasicBlock* bb)
{
  // TODO: For now, just looking for direct throws.  Consider generalizing for profile feedback
  if (!bb->explicit_throw) {
    return false;
  }
  BasicBlock* walker = bb;
  while (true) {
    // Check termination conditions
    if ((walker->block_type == kEntryBlock) || (Predecessors(walker) != 1)) {
      break;
    }
    BasicBlock* prev = GET_ELEM_N(walker->predecessors, BasicBlock*, 0);
    if (prev->conditional_branch) {
      if (prev->fall_through == walker) {
        // Already done - return
        break;
      }
      DCHECK_EQ(walker, prev->taken);
      // Got one.  Flip it and exit
      Instruction::Code opcode = prev->last_mir_insn->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 " << opcode;
      }
      prev->last_mir_insn->dalvikInsn.opcode = opcode;
      BasicBlock* t_bb = prev->taken;
      prev->taken = prev->fall_through;
      prev->fall_through = t_bb;
      break;
    }
    walker = prev;
  }
  return false;
}

/* Combine any basic blocks terminated by instructions that we now know can't throw */
static bool CombineBlocks(struct CompilationUnit* cu, struct BasicBlock* bb)
{
  // Loop here to allow combining a sequence of blocks
  while (true) {
    // Check termination conditions
    if ((bb->first_mir_insn == NULL)
        || (bb->data_flow_info == NULL)
        || (bb->block_type == kExceptionHandling)
        || (bb->block_type == kExitBlock)
        || (bb->block_type == kDead)
        || ((bb->taken == NULL) || (bb->taken->block_type != kExceptionHandling))
        || (bb->successor_block_list.block_list_type != kNotUsed)
        || (static_cast<int>(bb->last_mir_insn->dalvikInsn.opcode) != kMirOpCheck)) {
      break;
    }

    // Test the kMirOpCheck instruction
    MIR* mir = bb->last_mir_insn;
    // Grab the attributes from the paired opcode
    MIR* throw_insn = mir->meta.throw_insn;
    int df_attributes = oat_data_flow_attributes[throw_insn->dalvikInsn.opcode];
    bool can_combine = true;
    if (df_attributes & DF_HAS_NULL_CHKS) {
      can_combine &= ((throw_insn->optimization_flags & MIR_IGNORE_NULL_CHECK) != 0);
    }
    if (df_attributes & DF_HAS_RANGE_CHKS) {
      can_combine &= ((throw_insn->optimization_flags & MIR_IGNORE_RANGE_CHECK) != 0);
    }
    if (!can_combine) {
      break;
    }
    // OK - got one.  Combine
    BasicBlock* bb_next = bb->fall_through;
    DCHECK(!bb_next->catch_entry);
    DCHECK_EQ(Predecessors(bb_next), 1U);
    MIR* t_mir = bb->last_mir_insn->prev;
    // Overwrite the kOpCheck insn with the paired opcode
    DCHECK_EQ(bb_next->first_mir_insn, throw_insn);
    *bb->last_mir_insn = *throw_insn;
    bb->last_mir_insn->prev = t_mir;
    // Use the successor info from the next block
    bb->successor_block_list = bb_next->successor_block_list;
    // Use the ending block linkage from the next block
    bb->fall_through = bb_next->fall_through;
    bb->taken->block_type = kDead;  // Kill the unused exception block
    bb->taken = bb_next->taken;
    // Include the rest of the instructions
    bb->last_mir_insn = bb_next->last_mir_insn;
    /*
     * If lower-half of pair of blocks to combine contained a return, move the flag
     * to the newly combined block.
     */
    bb->terminated_by_return = bb_next->terminated_by_return;

    /*
     * NOTE: we aren't updating all dataflow info here.  Should either make sure this pass
     * happens after uses of i_dominated, dom_frontier or update the dataflow info here.
     */

    // Kill bb_next and remap now-dead id to parent
    bb_next->block_type = kDead;
    cu->block_id_map.Overwrite(bb_next->id, bb->id);

    // Now, loop back and see if we can keep going
  }
  return false;
}

/* Eliminate unnecessary null checks for a basic block. */
static bool EliminateNullChecks( struct CompilationUnit* cu, struct BasicBlock* bb)
{
  if (bb->data_flow_info == 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->block_type == kEntryBlock) | bb->catch_entry) {
    ClearAllBits(cu->temp_ssa_register_v);
    if ((cu->access_flags & kAccStatic) == 0) {
      // If non-static method, mark "this" as non-null
      int this_reg = cu->num_dalvik_registers - cu->num_ins;
      SetBit(cu, cu->temp_ssa_register_v, this_reg);
    }
  } else {
    // Starting state is intesection of all incoming arcs
    GrowableListIterator iter;
    GrowableListIteratorInit(bb->predecessors, &iter);
    BasicBlock* pred_bb = reinterpret_cast<BasicBlock*>(GrowableListIteratorNext(&iter));
    DCHECK(pred_bb != NULL);
    CopyBitVector(cu->temp_ssa_register_v,
                     pred_bb->data_flow_info->ending_null_check_v);
    while (true) {
      pred_bb = reinterpret_cast<BasicBlock*>(GrowableListIteratorNext(&iter));
      if (!pred_bb) break;
      if ((pred_bb->data_flow_info == NULL) ||
          (pred_bb->data_flow_info->ending_null_check_v == NULL)) {
        continue;
      }
      IntersectBitVectors(cu->temp_ssa_register_v,
                             cu->temp_ssa_register_v,
                             pred_bb->data_flow_info->ending_null_check_v);
    }
  }

  // Walk through the instruction in the block, updating as necessary
  for (MIR* mir = bb->first_mir_insn; mir != NULL; mir = mir->next) {
    if (mir->ssa_rep == NULL) {
        continue;
    }
    int df_attributes = oat_data_flow_attributes[mir->dalvikInsn.opcode];

    // Mark target of NEW* as non-null
    if (df_attributes & DF_NON_NULL_DST) {
      SetBit(cu, cu->temp_ssa_register_v, mir->ssa_rep->defs[0]);
    }

    // Mark non-null returns from invoke-style NEW*
    if (df_attributes & DF_NON_NULL_RET) {
      MIR* next_mir = mir->next;
      // Next should be an MOVE_RESULT_OBJECT
      if (next_mir &&
          next_mir->dalvikInsn.opcode == Instruction::MOVE_RESULT_OBJECT) {
        // Mark as null checked
        SetBit(cu, cu->temp_ssa_register_v, next_mir->ssa_rep->defs[0]);
      } else {
        if (next_mir) {
          LOG(WARNING) << "Unexpected opcode following new: " << next_mir->dalvikInsn.opcode;
        } else if (bb->fall_through) {
          // Look in next basic block
          struct BasicBlock* next_bb = bb->fall_through;
          for (MIR* tmir = next_bb->first_mir_insn; tmir != NULL;
            tmir =tmir->next) {
            if (static_cast<int>(tmir->dalvikInsn.opcode) >= static_cast<int>(kMirOpFirst)) {
              continue;
            }
            // First non-pseudo should be MOVE_RESULT_OBJECT
            if (tmir->dalvikInsn.opcode == Instruction::MOVE_RESULT_OBJECT) {
              // Mark as null checked
              SetBit(cu, cu->temp_ssa_register_v, tmir->ssa_rep->defs[0]);
            } else {
              LOG(WARNING) << "Unexpected op after new: " << 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 (df_attributes & (DF_NULL_TRANSFER_0 | DF_NULL_TRANSFER_N)) {
      int tgt_sreg = mir->ssa_rep->defs[0];
      int operands = (df_attributes & DF_NULL_TRANSFER_0) ? 1 :
          mir->ssa_rep->num_uses;
      bool null_checked = true;
      for (int i = 0; i < operands; i++) {
        null_checked &= IsBitSet(cu->temp_ssa_register_v,
        mir->ssa_rep->uses[i]);
      }
      if (null_checked) {
        SetBit(cu, cu->temp_ssa_register_v, tgt_sreg);
      }
    }

    // Already nullchecked?
    if ((df_attributes & DF_HAS_NULL_CHKS) && !(mir->optimization_flags & MIR_IGNORE_NULL_CHECK)) {
      int src_idx;
      if (df_attributes & DF_NULL_CHK_1) {
        src_idx = 1;
      } else if (df_attributes & DF_NULL_CHK_2) {
        src_idx = 2;
      } else {
        src_idx = 0;
      }
      int src_sreg = mir->ssa_rep->uses[src_idx];
        if (IsBitSet(cu->temp_ssa_register_v, src_sreg)) {
          // Eliminate the null check
          mir->optimization_flags |= MIR_IGNORE_NULL_CHECK;
        } else {
          // Mark s_reg as null-checked
          SetBit(cu, cu->temp_ssa_register_v, src_sreg);
        }
     }
  }

  // Did anything change?
  bool res = CompareBitVectors(bb->data_flow_info->ending_null_check_v,
                                  cu->temp_ssa_register_v);
  if (res) {
    CopyBitVector(bb->data_flow_info->ending_null_check_v,
                     cu->temp_ssa_register_v);
  }
  return res;
}

void NullCheckElimination(CompilationUnit *cu)
{
  if (!(cu->disable_opt & (1 << kNullCheckElimination))) {
    DCHECK(cu->temp_ssa_register_v != NULL);
    DataFlowAnalysisDispatcher(cu, NullCheckEliminationInit, kAllNodes,
                                  false /* is_iterative */);
    DataFlowAnalysisDispatcher(cu, EliminateNullChecks,
                                  kPreOrderDFSTraversal,
                                  true /* is_iterative */);
  }
}

void BasicBlockCombine(CompilationUnit* cu)
{
  DataFlowAnalysisDispatcher(cu, CombineBlocks, kPreOrderDFSTraversal, false);
}

void CodeLayout(CompilationUnit* cu)
{
  DataFlowAnalysisDispatcher(cu, LayoutBlocks, kAllNodes, false);
}

void DumpCheckStats(CompilationUnit *cu)
{
  Checkstats* stats =
      static_cast<Checkstats*>(NewMem(cu, sizeof(Checkstats), true, kAllocDFInfo));
  cu->checkstats = stats;
  DataFlowAnalysisDispatcher(cu, CountChecks, kAllNodes, false /* is_iterative */);
  if (stats->null_checks > 0) {
    float eliminated = static_cast<float>(stats->null_checks_eliminated);
    float checks = static_cast<float>(stats->null_checks);
    LOG(INFO) << "Null Checks: " << PrettyMethod(cu->method_idx, *cu->dex_file) << " "
              << stats->null_checks_eliminated << " of " << stats->null_checks << " -> "
              << (eliminated/checks) * 100.0 << "%";
    }
  if (stats->range_checks > 0) {
    float eliminated = static_cast<float>(stats->range_checks_eliminated);
    float checks = static_cast<float>(stats->range_checks);
    LOG(INFO) << "Range Checks: " << PrettyMethod(cu->method_idx, *cu->dex_file) << " "
              << stats->range_checks_eliminated << " of " << stats->range_checks << " -> "
              << (eliminated/checks) * 100.0 << "%";
  }
}

bool BuildExtendedBBList(struct CompilationUnit* cu, struct BasicBlock* bb)
{
  if (bb->visited) return false;
  if (!((bb->block_type == kEntryBlock) || (bb->block_type == kDalvikByteCode)
      || (bb->block_type == kExitBlock))) {
    // Ignore special blocks
    bb->visited = true;
    return false;
  }
  // Must be head of extended basic block.
  BasicBlock* start_bb = bb;
  cu->extended_basic_blocks.push_back(bb);
  bool terminated_by_return = false;
  // Visit blocks strictly dominated by this head.
  while (bb != NULL) {
    bb->visited = true;
    terminated_by_return |= bb->terminated_by_return;
    bb = NextDominatedBlock(cu, bb);
  }
  if (terminated_by_return) {
    // This extended basic block contains a return, so mark all members.
    bb = start_bb;
    while (bb != NULL) {
      bb->dominates_return = true;
      bb = NextDominatedBlock(cu, bb);
    }
  }
  return false; // Not iterative - return value will be ignored
}

void BasicBlockOptimization(CompilationUnit *cu)
{
  if (!(cu->disable_opt & (1 << kBBOpt))) {
    CompilerInitGrowableList(cu, &cu->compiler_temps, 6, kListMisc);
    DCHECK_EQ(cu->num_compiler_temps, 0);
    // Mark all blocks as not visited
    DataFlowAnalysisDispatcher(cu, ClearVisitedFlag,
                                  kAllNodes, false /* is_iterative */);
    DataFlowAnalysisDispatcher(cu, BuildExtendedBBList,
                                  kPreOrderDFSTraversal,
                                  false /* is_iterative */);
    // Perform extended basic block optimizations.
    for (unsigned int i = 0; i < cu->extended_basic_blocks.size(); i++) {
      BasicBlockOpt(cu, cu->extended_basic_blocks[i]);
    }
  }
}

static void AddLoopHeader(CompilationUnit* cu, BasicBlock* header,
                          BasicBlock* back_edge)
{
  GrowableListIterator iter;
  GrowableListIteratorInit(&cu->loop_headers, &iter);
  for (LoopInfo* loop = reinterpret_cast<LoopInfo*>(GrowableListIteratorNext(&iter));
      (loop != NULL); loop = reinterpret_cast<LoopInfo*>(GrowableListIteratorNext(&iter))) {
    if (loop->header == header) {
      InsertGrowableList(cu, &loop->incoming_back_edges,
                            reinterpret_cast<uintptr_t>(back_edge));
      return;
    }
  }
  LoopInfo* info = static_cast<LoopInfo*>(NewMem(cu, sizeof(LoopInfo), true, kAllocDFInfo));
  info->header = header;
  CompilerInitGrowableList(cu, &info->incoming_back_edges, 2, kListMisc);
  InsertGrowableList(cu, &info->incoming_back_edges, reinterpret_cast<uintptr_t>(back_edge));
  InsertGrowableList(cu, &cu->loop_headers, reinterpret_cast<uintptr_t>(info));
}

static bool FindBackEdges(struct CompilationUnit* cu, struct BasicBlock* bb)
{
  if ((bb->data_flow_info == NULL) || (bb->last_mir_insn == NULL)) {
    return false;
  }
  Instruction::Code opcode = bb->last_mir_insn->dalvikInsn.opcode;
  if (Instruction::FlagsOf(opcode) & Instruction::kBranch) {
    if (bb->taken && (bb->taken->start_offset <= bb->start_offset)) {
      DCHECK(bb->dominators != NULL);
      if (IsBitSet(bb->dominators, bb->taken->id)) {
        if (cu->verbose) {
          LOG(INFO) << "Loop backedge from 0x"
                    << std::hex << bb->last_mir_insn->offset
                    << " to 0x" << std::hex << bb->taken->start_offset;
        }
        AddLoopHeader(cu, bb->taken, bb);
      }
    }
  }
  return false;
}

static void AddBlocksToLoop(CompilationUnit* cu, ArenaBitVector* blocks,
                            BasicBlock* bb, int head_id)
{
  if (!IsBitSet(bb->dominators, head_id) ||
    IsBitSet(blocks, bb->id)) {
    return;
  }
  SetBit(cu, blocks, bb->id);
  GrowableListIterator iter;
  GrowableListIteratorInit(bb->predecessors, &iter);
  BasicBlock* pred_bb;
  for (pred_bb = reinterpret_cast<BasicBlock*>(GrowableListIteratorNext(&iter)); pred_bb != NULL;
       pred_bb = reinterpret_cast<BasicBlock*>(GrowableListIteratorNext(&iter))) {
    AddBlocksToLoop(cu, blocks, pred_bb, head_id);
  }
}

static void DumpLoops(CompilationUnit *cu)
{
  GrowableListIterator iter;
  GrowableListIteratorInit(&cu->loop_headers, &iter);
  for (LoopInfo* loop = reinterpret_cast<LoopInfo*>(GrowableListIteratorNext(&iter));
      (loop != NULL); loop = reinterpret_cast<LoopInfo*>(GrowableListIteratorNext(&iter))) {
    LOG(INFO) << "Loop head block id " << loop->header->id
              << ", offset 0x" << std::hex << loop->header->start_offset
              << ", Depth: " << loop->header->nesting_depth;
    GrowableListIterator iter;
    GrowableListIteratorInit(&loop->incoming_back_edges, &iter);
    BasicBlock* edge_bb;
    for (edge_bb = reinterpret_cast<BasicBlock*>(GrowableListIteratorNext(&iter)); edge_bb != NULL;
         edge_bb = reinterpret_cast<BasicBlock*>(GrowableListIteratorNext(&iter))) {
      LOG(INFO) << "    Backedge block id " << edge_bb->id
                << ", offset 0x" << std::hex << edge_bb->start_offset;
      ArenaBitVectorIterator b_iter;
      BitVectorIteratorInit(loop->blocks, &b_iter);
      for (int bb_id = BitVectorIteratorNext(&b_iter); bb_id != -1;
           bb_id = BitVectorIteratorNext(&b_iter)) {
        BasicBlock *bb;
        bb = reinterpret_cast<BasicBlock*>(GrowableListGetElement(&cu->block_list, bb_id));
        LOG(INFO) << "        (" << bb->id << ", 0x" << std::hex
                  << bb->start_offset << ")";
      }
    }
  }
}

void LoopDetection(CompilationUnit *cu)
{
  if (cu->disable_opt & (1 << kPromoteRegs)) {
    return;
  }
  CompilerInitGrowableList(cu, &cu->loop_headers, 6, kListMisc);
  // Find the loop headers
  DataFlowAnalysisDispatcher(cu, FindBackEdges, kAllNodes, false /* is_iterative */);
  GrowableListIterator iter;
  GrowableListIteratorInit(&cu->loop_headers, &iter);
  // Add blocks to each header
  for (LoopInfo* loop = reinterpret_cast<LoopInfo*>(GrowableListIteratorNext(&iter));
       loop != NULL; loop = reinterpret_cast<LoopInfo*>(GrowableListIteratorNext(&iter))) {
    loop->blocks = AllocBitVector(cu, cu->num_blocks, true,
                                     kBitMapMisc);
    SetBit(cu, loop->blocks, loop->header->id);
    GrowableListIterator iter;
    GrowableListIteratorInit(&loop->incoming_back_edges, &iter);
    BasicBlock* edge_bb;
    for (edge_bb = reinterpret_cast<BasicBlock*>(GrowableListIteratorNext(&iter)); edge_bb != NULL;
         edge_bb = reinterpret_cast<BasicBlock*>(GrowableListIteratorNext(&iter))) {
      AddBlocksToLoop(cu, loop->blocks, edge_bb, loop->header->id);
    }
  }
  // Compute the nesting depth of each header
  GrowableListIteratorInit(&cu->loop_headers, &iter);
  for (LoopInfo* loop = reinterpret_cast<LoopInfo*>(GrowableListIteratorNext(&iter));
       loop != NULL; loop = reinterpret_cast<LoopInfo*>(GrowableListIteratorNext(&iter))) {
    GrowableListIterator iter2;
    GrowableListIteratorInit(&cu->loop_headers, &iter2);
    LoopInfo* loop2;
    for (loop2 = reinterpret_cast<LoopInfo*>(GrowableListIteratorNext(&iter2));
         loop2 != NULL; loop2 = reinterpret_cast<LoopInfo*>(GrowableListIteratorNext(&iter2))) {
      if (IsBitSet(loop2->blocks, loop->header->id)) {
         loop->header->nesting_depth++;
      }
    }
  }
  // Assign nesting depth to each block in all loops
  GrowableListIteratorInit(&cu->loop_headers, &iter);
  for (LoopInfo* loop = reinterpret_cast<LoopInfo*>(GrowableListIteratorNext(&iter));
       (loop != NULL); loop = reinterpret_cast<LoopInfo*>(GrowableListIteratorNext(&iter))) {
    ArenaBitVectorIterator b_iter;
    BitVectorIteratorInit(loop->blocks, &b_iter);
    for (int bb_id = BitVectorIteratorNext(&b_iter); bb_id != -1;
        bb_id = BitVectorIteratorNext(&b_iter)) {
      BasicBlock *bb;
      bb = reinterpret_cast<BasicBlock*>(GrowableListGetElement(&cu->block_list, bb_id));
      bb->nesting_depth = std::max(bb->nesting_depth,
                                  loop->header->nesting_depth);
    }
  }
  if (cu->verbose) {
    DumpLoops(cu);
  }
}

/*
 * 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.
 */
static bool InvokeUsesMethodStar(CompilationUnit* cu, 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: " << opcode;
      return false;
  }
  OatCompilationUnit m_unit(cu->class_loader, cu->class_linker,
                            *cu->dex_file, cu->code_item,
                            cu->class_def_idx, cu->method_idx,
                            cu->access_flags);
  // TODO: add a flag so we don't counts the stats for this twice
  uint32_t dex_method_idx = mir->dalvikInsn.vB;
  int vtable_idx;
  uintptr_t direct_code;
  uintptr_t direct_method;
  bool fast_path =
      cu->compiler->ComputeInvokeInfo(dex_method_idx, &m_unit, type,
                                         vtable_idx, direct_code,
                                         direct_method) &&
      !SLOW_INVOKE_PATH;
  return (((type == kDirect) || (type == kStatic)) &&
          fast_path && ((direct_code == 0) || (direct_method == 0)));
}

/*
 * Count uses, weighting by loop nesting depth.  This code only
 * counts explicitly used s_regs.  A later phase will add implicit
 * counts for things such as Method*, null-checked references, etc.
 */
static bool CountUses(struct CompilationUnit* cu, struct BasicBlock* bb)
{
  if (bb->block_type != kDalvikByteCode) {
    return false;
  }
  for (MIR* mir = bb->first_mir_insn; (mir != NULL); mir = mir->next) {
    if (mir->ssa_rep == NULL) {
      continue;
    }
    uint32_t weight = std::min(16U, static_cast<uint32_t>(bb->nesting_depth));
    for (int i = 0; i < mir->ssa_rep->num_uses; i++) {
      int s_reg = mir->ssa_rep->uses[i];
      DCHECK_LT(s_reg, static_cast<int>(cu->use_counts.num_used));
      cu->raw_use_counts.elem_list[s_reg]++;
      cu->use_counts.elem_list[s_reg] += (1 << weight);
    }
    if (!(cu->disable_opt & (1 << kPromoteCompilerTemps))) {
      int df_attributes = oat_data_flow_attributes[mir->dalvikInsn.opcode];
      // Implicit use of Method* ? */
      if (df_attributes & 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 uses_method_star = true;
        if ((df_attributes & (DF_FORMAT_35C | DF_FORMAT_3RC)) &&
            !(df_attributes & DF_NON_NULL_RET)) {
          uses_method_star &= InvokeUsesMethodStar(cu, mir);
        }
        if (uses_method_star) {
          cu->raw_use_counts.elem_list[cu->method_sreg]++;
          cu->use_counts.elem_list[cu->method_sreg] += (1 << weight);
        }
      }
    }
  }
  return false;
}

void MethodUseCount(CompilationUnit *cu)
{
  CompilerInitGrowableList(cu, &cu->use_counts, cu->num_ssa_regs + 32, kListMisc);
  CompilerInitGrowableList(cu, &cu->raw_use_counts, cu->num_ssa_regs + 32, kListMisc);
  // Initialize list
  for (int i = 0; i < cu->num_ssa_regs; i++) {
    InsertGrowableList(cu, &cu->use_counts, 0);
    InsertGrowableList(cu, &cu->raw_use_counts, 0);
  }
  if (cu->disable_opt & (1 << kPromoteRegs)) {
    return;
  }
  DataFlowAnalysisDispatcher(cu, CountUses,
                                kAllNodes, false /* is_iterative */);
}

}  // namespace art