Home | History | Annotate | Download | only in compiler
      1 /*
      2  * Copyright (C) 2009 The Android Open Source Project
      3  *
      4  * Licensed under the Apache License, Version 2.0 (the "License");
      5  * you may not use this file except in compliance with the License.
      6  * You may obtain a copy of the License at
      7  *
      8  *      http://www.apache.org/licenses/LICENSE-2.0
      9  *
     10  * Unless required by applicable law or agreed to in writing, software
     11  * distributed under the License is distributed on an "AS IS" BASIS,
     12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     13  * See the License for the specific language governing permissions and
     14  * limitations under the License.
     15  */
     16 
     17 #include "Dalvik.h"
     18 #include "Dataflow.h"
     19 #include "Loop.h"
     20 #include "libdex/OpCodeNames.h"
     21 
     22 /*
     23  * Main table containing data flow attributes for each bytecode. The first
     24  * 256 entries are for Dalvik bytecode instructions, where extended opcode at
     25  * the MIR level are appended afterwards.
     26  *
     27  * TODO - many optimization flags are incomplete - they will only limit the
     28  * scope of optimizations but will not cause mis-optimizations.
     29  */
     30 int dvmCompilerDataFlowAttributes[kMirOpLast] = {
     31     // 00 OP_NOP
     32     DF_NOP,
     33 
     34     // 01 OP_MOVE vA, vB
     35     DF_DA | DF_UB | DF_IS_MOVE,
     36 
     37     // 02 OP_MOVE_FROM16 vAA, vBBBB
     38     DF_DA | DF_UB | DF_IS_MOVE,
     39 
     40     // 03 OP_MOVE_16 vAAAA, vBBBB
     41     DF_DA | DF_UB | DF_IS_MOVE,
     42 
     43     // 04 OP_MOVE_WIDE vA, vB
     44     DF_DA_WIDE | DF_UB_WIDE | DF_IS_MOVE,
     45 
     46     // 05 OP_MOVE_WIDE_FROM16 vAA, vBBBB
     47     DF_DA_WIDE | DF_UB_WIDE | DF_IS_MOVE,
     48 
     49     // 06 OP_MOVE_WIDE_16 vAAAA, vBBBB
     50     DF_DA_WIDE | DF_UB_WIDE | DF_IS_MOVE,
     51 
     52     // 07 OP_MOVE_OBJECT vA, vB
     53     DF_DA | DF_UB | DF_IS_MOVE,
     54 
     55     // 08 OP_MOVE_OBJECT_FROM16 vAA, vBBBB
     56     DF_DA | DF_UB | DF_IS_MOVE,
     57 
     58     // 09 OP_MOVE_OBJECT_16 vAAAA, vBBBB
     59     DF_DA | DF_UB | DF_IS_MOVE,
     60 
     61     // 0A OP_MOVE_RESULT vAA
     62     DF_DA,
     63 
     64     // 0B OP_MOVE_RESULT_WIDE vAA
     65     DF_DA_WIDE,
     66 
     67     // 0C OP_MOVE_RESULT_OBJECT vAA
     68     DF_DA,
     69 
     70     // 0D OP_MOVE_EXCEPTION vAA
     71     DF_DA,
     72 
     73     // 0E OP_RETURN_VOID
     74     DF_NOP,
     75 
     76     // 0F OP_RETURN vAA
     77     DF_UA,
     78 
     79     // 10 OP_RETURN_WIDE vAA
     80     DF_UA_WIDE,
     81 
     82     // 11 OP_RETURN_OBJECT vAA
     83     DF_UA,
     84 
     85     // 12 OP_CONST_4 vA, #+B
     86     DF_DA | DF_SETS_CONST,
     87 
     88     // 13 OP_CONST_16 vAA, #+BBBB
     89     DF_DA | DF_SETS_CONST,
     90 
     91     // 14 OP_CONST vAA, #+BBBBBBBB
     92     DF_DA | DF_SETS_CONST,
     93 
     94     // 15 OP_CONST_HIGH16 VAA, #+BBBB0000
     95     DF_DA | DF_SETS_CONST,
     96 
     97     // 16 OP_CONST_WIDE_16 vAA, #+BBBB
     98     DF_DA_WIDE | DF_SETS_CONST,
     99 
    100     // 17 OP_CONST_WIDE_32 vAA, #+BBBBBBBB
    101     DF_DA_WIDE | DF_SETS_CONST,
    102 
    103     // 18 OP_CONST_WIDE vAA, #+BBBBBBBBBBBBBBBB
    104     DF_DA_WIDE | DF_SETS_CONST,
    105 
    106     // 19 OP_CONST_WIDE_HIGH16 vAA, #+BBBB000000000000
    107     DF_DA_WIDE | DF_SETS_CONST,
    108 
    109     // 1A OP_CONST_STRING vAA, string@BBBB
    110     DF_DA,
    111 
    112     // 1B OP_CONST_STRING_JUMBO vAA, string@BBBBBBBB
    113     DF_DA,
    114 
    115     // 1C OP_CONST_CLASS vAA, type@BBBB
    116     DF_DA,
    117 
    118     // 1D OP_MONITOR_ENTER vAA
    119     DF_UA,
    120 
    121     // 1E OP_MONITOR_EXIT vAA
    122     DF_UA,
    123 
    124     // 1F OP_CHECK_CAST vAA, type@BBBB
    125     DF_UA,
    126 
    127     // 20 OP_INSTANCE_OF vA, vB, type@CCCC
    128     DF_DA | DF_UB,
    129 
    130     // 21 OP_ARRAY_LENGTH vA, vB
    131     DF_DA | DF_UB,
    132 
    133     // 22 OP_NEW_INSTANCE vAA, type@BBBB
    134     DF_DA,
    135 
    136     // 23 OP_NEW_ARRAY vA, vB, type@CCCC
    137     DF_DA | DF_UB,
    138 
    139     // 24 OP_FILLED_NEW_ARRAY {vD, vE, vF, vG, vA}
    140     DF_FORMAT_35C,
    141 
    142     // 25 OP_FILLED_NEW_ARRAY_RANGE {vCCCC .. vNNNN}, type@BBBB
    143     DF_FORMAT_3RC,
    144 
    145     // 26 OP_FILL_ARRAY_DATA vAA, +BBBBBBBB
    146     DF_UA,
    147 
    148     // 27 OP_THROW vAA
    149     DF_UA,
    150 
    151     // 28 OP_GOTO
    152     DF_NOP,
    153 
    154     // 29 OP_GOTO_16
    155     DF_NOP,
    156 
    157     // 2A OP_GOTO_32
    158     DF_NOP,
    159 
    160     // 2B OP_PACKED_SWITCH vAA, +BBBBBBBB
    161     DF_UA,
    162 
    163     // 2C OP_SPARSE_SWITCH vAA, +BBBBBBBB
    164     DF_UA,
    165 
    166     // 2D OP_CMPL_FLOAT vAA, vBB, vCC
    167     DF_DA | DF_UB | DF_UC | DF_FP_B | DF_FP_C,
    168 
    169     // 2E OP_CMPG_FLOAT vAA, vBB, vCC
    170     DF_DA | DF_UB | DF_UC | DF_FP_B | DF_FP_C,
    171 
    172     // 2F OP_CMPL_DOUBLE vAA, vBB, vCC
    173     DF_DA | DF_UB_WIDE | DF_UC_WIDE | DF_FP_B | DF_FP_C,
    174 
    175     // 30 OP_CMPG_DOUBLE vAA, vBB, vCC
    176     DF_DA | DF_UB_WIDE | DF_UC_WIDE | DF_FP_B | DF_FP_C,
    177 
    178     // 31 OP_CMP_LONG vAA, vBB, vCC
    179     DF_DA | DF_UB_WIDE | DF_UC_WIDE,
    180 
    181     // 32 OP_IF_EQ vA, vB, +CCCC
    182     DF_UA | DF_UB,
    183 
    184     // 33 OP_IF_NE vA, vB, +CCCC
    185     DF_UA | DF_UB,
    186 
    187     // 34 OP_IF_LT vA, vB, +CCCC
    188     DF_UA | DF_UB,
    189 
    190     // 35 OP_IF_GE vA, vB, +CCCC
    191     DF_UA | DF_UB,
    192 
    193     // 36 OP_IF_GT vA, vB, +CCCC
    194     DF_UA | DF_UB,
    195 
    196     // 37 OP_IF_LE vA, vB, +CCCC
    197     DF_UA | DF_UB,
    198 
    199 
    200     // 38 OP_IF_EQZ vAA, +BBBB
    201     DF_UA,
    202 
    203     // 39 OP_IF_NEZ vAA, +BBBB
    204     DF_UA,
    205 
    206     // 3A OP_IF_LTZ vAA, +BBBB
    207     DF_UA,
    208 
    209     // 3B OP_IF_GEZ vAA, +BBBB
    210     DF_UA,
    211 
    212     // 3C OP_IF_GTZ vAA, +BBBB
    213     DF_UA,
    214 
    215     // 3D OP_IF_LEZ vAA, +BBBB
    216     DF_UA,
    217 
    218     // 3E OP_UNUSED_3E
    219     DF_NOP,
    220 
    221     // 3F OP_UNUSED_3F
    222     DF_NOP,
    223 
    224     // 40 OP_UNUSED_40
    225     DF_NOP,
    226 
    227     // 41 OP_UNUSED_41
    228     DF_NOP,
    229 
    230     // 42 OP_UNUSED_42
    231     DF_NOP,
    232 
    233     // 43 OP_UNUSED_43
    234     DF_NOP,
    235 
    236     // 44 OP_AGET vAA, vBB, vCC
    237     DF_DA | DF_UB | DF_UC | DF_NULL_N_RANGE_CHECK_0 | DF_IS_GETTER,
    238 
    239     // 45 OP_AGET_WIDE vAA, vBB, vCC
    240     DF_DA_WIDE | DF_UB | DF_UC | DF_NULL_N_RANGE_CHECK_0 | DF_IS_GETTER,
    241 
    242     // 46 OP_AGET_OBJECT vAA, vBB, vCC
    243     DF_DA | DF_UB | DF_UC | DF_NULL_N_RANGE_CHECK_0 | DF_IS_GETTER,
    244 
    245     // 47 OP_AGET_BOOLEAN vAA, vBB, vCC
    246     DF_DA | DF_UB | DF_UC | DF_NULL_N_RANGE_CHECK_0 | DF_IS_GETTER,
    247 
    248     // 48 OP_AGET_BYTE vAA, vBB, vCC
    249     DF_DA | DF_UB | DF_UC | DF_NULL_N_RANGE_CHECK_0 | DF_IS_GETTER,
    250 
    251     // 49 OP_AGET_CHAR vAA, vBB, vCC
    252     DF_DA | DF_UB | DF_UC | DF_NULL_N_RANGE_CHECK_0 | DF_IS_GETTER,
    253 
    254     // 4A OP_AGET_SHORT vAA, vBB, vCC
    255     DF_DA | DF_UB | DF_UC | DF_NULL_N_RANGE_CHECK_0 | DF_IS_GETTER,
    256 
    257     // 4B OP_APUT vAA, vBB, vCC
    258     DF_UA | DF_UB | DF_UC | DF_NULL_N_RANGE_CHECK_1 | DF_IS_SETTER,
    259 
    260     // 4C OP_APUT_WIDE vAA, vBB, vCC
    261     DF_UA_WIDE | DF_UB | DF_UC | DF_NULL_N_RANGE_CHECK_2 | DF_IS_SETTER,
    262 
    263     // 4D OP_APUT_OBJECT vAA, vBB, vCC
    264     DF_UA | DF_UB | DF_UC | DF_NULL_N_RANGE_CHECK_1 | DF_IS_SETTER,
    265 
    266     // 4E OP_APUT_BOOLEAN vAA, vBB, vCC
    267     DF_UA | DF_UB | DF_UC | DF_NULL_N_RANGE_CHECK_1 | DF_IS_SETTER,
    268 
    269     // 4F OP_APUT_BYTE vAA, vBB, vCC
    270     DF_UA | DF_UB | DF_UC | DF_NULL_N_RANGE_CHECK_1 | DF_IS_SETTER,
    271 
    272     // 50 OP_APUT_CHAR vAA, vBB, vCC
    273     DF_UA | DF_UB | DF_UC | DF_NULL_N_RANGE_CHECK_1 | DF_IS_SETTER,
    274 
    275     // 51 OP_APUT_SHORT vAA, vBB, vCC
    276     DF_UA | DF_UB | DF_UC | DF_NULL_N_RANGE_CHECK_1 | DF_IS_SETTER,
    277 
    278     // 52 OP_IGET vA, vB, field@CCCC
    279     DF_DA | DF_UB | DF_IS_GETTER,
    280 
    281     // 53 OP_IGET_WIDE vA, vB, field@CCCC
    282     DF_DA_WIDE | DF_UB | DF_IS_GETTER,
    283 
    284     // 54 OP_IGET_OBJECT vA, vB, field@CCCC
    285     DF_DA | DF_UB | DF_IS_GETTER,
    286 
    287     // 55 OP_IGET_BOOLEAN vA, vB, field@CCCC
    288     DF_DA | DF_UB | DF_IS_GETTER,
    289 
    290     // 56 OP_IGET_BYTE vA, vB, field@CCCC
    291     DF_DA | DF_UB | DF_IS_GETTER,
    292 
    293     // 57 OP_IGET_CHAR vA, vB, field@CCCC
    294     DF_DA | DF_UB | DF_IS_GETTER,
    295 
    296     // 58 OP_IGET_SHORT vA, vB, field@CCCC
    297     DF_DA | DF_UB | DF_IS_GETTER,
    298 
    299     // 59 OP_IPUT vA, vB, field@CCCC
    300     DF_UA | DF_UB | DF_IS_SETTER,
    301 
    302     // 5A OP_IPUT_WIDE vA, vB, field@CCCC
    303     DF_UA_WIDE | DF_UB | DF_IS_SETTER,
    304 
    305     // 5B OP_IPUT_OBJECT vA, vB, field@CCCC
    306     DF_UA | DF_UB | DF_IS_SETTER,
    307 
    308     // 5C OP_IPUT_BOOLEAN vA, vB, field@CCCC
    309     DF_UA | DF_UB | DF_IS_SETTER,
    310 
    311     // 5D OP_IPUT_BYTE vA, vB, field@CCCC
    312     DF_UA | DF_UB | DF_IS_SETTER,
    313 
    314     // 5E OP_IPUT_CHAR vA, vB, field@CCCC
    315     DF_UA | DF_UB | DF_IS_SETTER,
    316 
    317     // 5F OP_IPUT_SHORT vA, vB, field@CCCC
    318     DF_UA | DF_UB | DF_IS_SETTER,
    319 
    320     // 60 OP_SGET vAA, field@BBBB
    321     DF_DA | DF_IS_GETTER,
    322 
    323     // 61 OP_SGET_WIDE vAA, field@BBBB
    324     DF_DA_WIDE | DF_IS_GETTER,
    325 
    326     // 62 OP_SGET_OBJECT vAA, field@BBBB
    327     DF_DA | DF_IS_GETTER,
    328 
    329     // 63 OP_SGET_BOOLEAN vAA, field@BBBB
    330     DF_DA | DF_IS_GETTER,
    331 
    332     // 64 OP_SGET_BYTE vAA, field@BBBB
    333     DF_DA | DF_IS_GETTER,
    334 
    335     // 65 OP_SGET_CHAR vAA, field@BBBB
    336     DF_DA | DF_IS_GETTER,
    337 
    338     // 66 OP_SGET_SHORT vAA, field@BBBB
    339     DF_DA | DF_IS_GETTER,
    340 
    341     // 67 OP_SPUT vAA, field@BBBB
    342     DF_UA | DF_IS_SETTER,
    343 
    344     // 68 OP_SPUT_WIDE vAA, field@BBBB
    345     DF_UA_WIDE | DF_IS_SETTER,
    346 
    347     // 69 OP_SPUT_OBJECT vAA, field@BBBB
    348     DF_UA | DF_IS_SETTER,
    349 
    350     // 6A OP_SPUT_BOOLEAN vAA, field@BBBB
    351     DF_UA | DF_IS_SETTER,
    352 
    353     // 6B OP_SPUT_BYTE vAA, field@BBBB
    354     DF_UA | DF_IS_SETTER,
    355 
    356     // 6C OP_SPUT_CHAR vAA, field@BBBB
    357     DF_UA | DF_IS_SETTER,
    358 
    359     // 6D OP_SPUT_SHORT vAA, field@BBBB
    360     DF_UA | DF_IS_SETTER,
    361 
    362     // 6E OP_INVOKE_VIRTUAL {vD, vE, vF, vG, vA}
    363     DF_FORMAT_35C,
    364 
    365     // 6F OP_INVOKE_SUPER {vD, vE, vF, vG, vA}
    366     DF_FORMAT_35C,
    367 
    368     // 70 OP_INVOKE_DIRECT {vD, vE, vF, vG, vA}
    369     DF_FORMAT_35C,
    370 
    371     // 71 OP_INVOKE_STATIC {vD, vE, vF, vG, vA}
    372     DF_FORMAT_35C,
    373 
    374     // 72 OP_INVOKE_INTERFACE {vD, vE, vF, vG, vA}
    375     DF_FORMAT_35C,
    376 
    377     // 73 OP_UNUSED_73
    378     DF_NOP,
    379 
    380     // 74 OP_INVOKE_VIRTUAL_RANGE {vCCCC .. vNNNN}
    381     DF_FORMAT_3RC,
    382 
    383     // 75 OP_INVOKE_SUPER_RANGE {vCCCC .. vNNNN}
    384     DF_FORMAT_3RC,
    385 
    386     // 76 OP_INVOKE_DIRECT_RANGE {vCCCC .. vNNNN}
    387     DF_FORMAT_3RC,
    388 
    389     // 77 OP_INVOKE_STATIC_RANGE {vCCCC .. vNNNN}
    390     DF_FORMAT_3RC,
    391 
    392     // 78 OP_INVOKE_INTERFACE_RANGE {vCCCC .. vNNNN}
    393     DF_FORMAT_3RC,
    394 
    395     // 79 OP_UNUSED_79
    396     DF_NOP,
    397 
    398     // 7A OP_UNUSED_7A
    399     DF_NOP,
    400 
    401     // 7B OP_NEG_INT vA, vB
    402     DF_DA | DF_UB,
    403 
    404     // 7C OP_NOT_INT vA, vB
    405     DF_DA | DF_UB,
    406 
    407     // 7D OP_NEG_LONG vA, vB
    408     DF_DA_WIDE | DF_UB_WIDE,
    409 
    410     // 7E OP_NOT_LONG vA, vB
    411     DF_DA_WIDE | DF_UB_WIDE,
    412 
    413     // 7F OP_NEG_FLOAT vA, vB
    414     DF_DA | DF_UB | DF_FP_A | DF_FP_B,
    415 
    416     // 80 OP_NEG_DOUBLE vA, vB
    417     DF_DA_WIDE | DF_UB_WIDE | DF_FP_A | DF_FP_B,
    418 
    419     // 81 OP_INT_TO_LONG vA, vB
    420     DF_DA_WIDE | DF_UB,
    421 
    422     // 82 OP_INT_TO_FLOAT vA, vB
    423     DF_DA | DF_UB | DF_FP_A,
    424 
    425     // 83 OP_INT_TO_DOUBLE vA, vB
    426     DF_DA_WIDE | DF_UB | DF_FP_A,
    427 
    428     // 84 OP_LONG_TO_INT vA, vB
    429     DF_DA | DF_UB_WIDE,
    430 
    431     // 85 OP_LONG_TO_FLOAT vA, vB
    432     DF_DA | DF_UB_WIDE | DF_FP_A,
    433 
    434     // 86 OP_LONG_TO_DOUBLE vA, vB
    435     DF_DA_WIDE | DF_UB_WIDE | DF_FP_A,
    436 
    437     // 87 OP_FLOAT_TO_INT vA, vB
    438     DF_DA | DF_UB | DF_FP_B,
    439 
    440     // 88 OP_FLOAT_TO_LONG vA, vB
    441     DF_DA_WIDE | DF_UB | DF_FP_B,
    442 
    443     // 89 OP_FLOAT_TO_DOUBLE vA, vB
    444     DF_DA_WIDE | DF_UB | DF_FP_A | DF_FP_B,
    445 
    446     // 8A OP_DOUBLE_TO_INT vA, vB
    447     DF_DA | DF_UB_WIDE | DF_FP_B,
    448 
    449     // 8B OP_DOUBLE_TO_LONG vA, vB
    450     DF_DA_WIDE | DF_UB_WIDE | DF_FP_B,
    451 
    452     // 8C OP_DOUBLE_TO_FLOAT vA, vB
    453     DF_DA | DF_UB_WIDE | DF_FP_A | DF_FP_B,
    454 
    455     // 8D OP_INT_TO_BYTE vA, vB
    456     DF_DA | DF_UB,
    457 
    458     // 8E OP_INT_TO_CHAR vA, vB
    459     DF_DA | DF_UB,
    460 
    461     // 8F OP_INT_TO_SHORT vA, vB
    462     DF_DA | DF_UB,
    463 
    464     // 90 OP_ADD_INT vAA, vBB, vCC
    465     DF_DA | DF_UB | DF_UC | DF_IS_LINEAR,
    466 
    467     // 91 OP_SUB_INT vAA, vBB, vCC
    468     DF_DA | DF_UB | DF_UC | DF_IS_LINEAR,
    469 
    470     // 92 OP_MUL_INT vAA, vBB, vCC
    471     DF_DA | DF_UB | DF_UC,
    472 
    473     // 93 OP_DIV_INT vAA, vBB, vCC
    474     DF_DA | DF_UB | DF_UC,
    475 
    476     // 94 OP_REM_INT vAA, vBB, vCC
    477     DF_DA | DF_UB | DF_UC,
    478 
    479     // 95 OP_AND_INT vAA, vBB, vCC
    480     DF_DA | DF_UB | DF_UC,
    481 
    482     // 96 OP_OR_INT vAA, vBB, vCC
    483     DF_DA | DF_UB | DF_UC,
    484 
    485     // 97 OP_XOR_INT vAA, vBB, vCC
    486     DF_DA | DF_UB | DF_UC,
    487 
    488     // 98 OP_SHL_INT vAA, vBB, vCC
    489     DF_DA | DF_UB | DF_UC,
    490 
    491     // 99 OP_SHR_INT vAA, vBB, vCC
    492     DF_DA | DF_UB | DF_UC,
    493 
    494     // 9A OP_USHR_INT vAA, vBB, vCC
    495     DF_DA | DF_UB | DF_UC,
    496 
    497     // 9B OP_ADD_LONG vAA, vBB, vCC
    498     DF_DA_WIDE | DF_UB_WIDE | DF_UC_WIDE,
    499 
    500     // 9C OP_SUB_LONG vAA, vBB, vCC
    501     DF_DA_WIDE | DF_UB_WIDE | DF_UC_WIDE,
    502 
    503     // 9D OP_MUL_LONG vAA, vBB, vCC
    504     DF_DA_WIDE | DF_UB_WIDE | DF_UC_WIDE,
    505 
    506     // 9E OP_DIV_LONG vAA, vBB, vCC
    507     DF_DA_WIDE | DF_UB_WIDE | DF_UC_WIDE,
    508 
    509     // 9F OP_REM_LONG vAA, vBB, vCC
    510     DF_DA_WIDE | DF_UB_WIDE | DF_UC_WIDE,
    511 
    512     // A0 OP_AND_LONG vAA, vBB, vCC
    513     DF_DA_WIDE | DF_UB_WIDE | DF_UC_WIDE,
    514 
    515     // A1 OP_OR_LONG vAA, vBB, vCC
    516     DF_DA_WIDE | DF_UB_WIDE | DF_UC_WIDE,
    517 
    518     // A2 OP_XOR_LONG vAA, vBB, vCC
    519     DF_DA_WIDE | DF_UB_WIDE | DF_UC_WIDE,
    520 
    521     // A3 OP_SHL_LONG vAA, vBB, vCC
    522     DF_DA_WIDE | DF_UB_WIDE | DF_UC,
    523 
    524     // A4 OP_SHR_LONG vAA, vBB, vCC
    525     DF_DA_WIDE | DF_UB_WIDE | DF_UC,
    526 
    527     // A5 OP_USHR_LONG vAA, vBB, vCC
    528     DF_DA_WIDE | DF_UB_WIDE | DF_UC,
    529 
    530     // A6 OP_ADD_FLOAT vAA, vBB, vCC
    531     DF_DA | DF_UB | DF_UC | DF_FP_A | DF_FP_B | DF_FP_C,
    532 
    533     // A7 OP_SUB_FLOAT vAA, vBB, vCC
    534     DF_DA | DF_UB | DF_UC | DF_FP_A | DF_FP_B | DF_FP_C,
    535 
    536     // A8 OP_MUL_FLOAT vAA, vBB, vCC
    537     DF_DA | DF_UB | DF_UC | DF_FP_A | DF_FP_B | DF_FP_C,
    538 
    539     // A9 OP_DIV_FLOAT vAA, vBB, vCC
    540     DF_DA | DF_UB | DF_UC | DF_FP_A | DF_FP_B | DF_FP_C,
    541 
    542     // AA OP_REM_FLOAT vAA, vBB, vCC
    543     DF_DA | DF_UB | DF_UC | DF_FP_A | DF_FP_B | DF_FP_C,
    544 
    545     // AB OP_ADD_DOUBLE vAA, vBB, vCC
    546     DF_DA_WIDE | DF_UB_WIDE | DF_UC_WIDE | DF_FP_A | DF_FP_B | DF_FP_C,
    547 
    548     // AC OP_SUB_DOUBLE vAA, vBB, vCC
    549     DF_DA_WIDE | DF_UB_WIDE | DF_UC_WIDE | DF_FP_A | DF_FP_B | DF_FP_C,
    550 
    551     // AD OP_MUL_DOUBLE vAA, vBB, vCC
    552     DF_DA_WIDE | DF_UB_WIDE | DF_UC_WIDE | DF_FP_A | DF_FP_B | DF_FP_C,
    553 
    554     // AE OP_DIV_DOUBLE vAA, vBB, vCC
    555     DF_DA_WIDE | DF_UB_WIDE | DF_UC_WIDE | DF_FP_A | DF_FP_B | DF_FP_C,
    556 
    557     // AF OP_REM_DOUBLE vAA, vBB, vCC
    558     DF_DA_WIDE | DF_UB_WIDE | DF_UC_WIDE | DF_FP_A | DF_FP_B | DF_FP_C,
    559 
    560     // B0 OP_ADD_INT_2ADDR vA, vB
    561     DF_DA | DF_UA | DF_UB,
    562 
    563     // B1 OP_SUB_INT_2ADDR vA, vB
    564     DF_DA | DF_UA | DF_UB,
    565 
    566     // B2 OP_MUL_INT_2ADDR vA, vB
    567     DF_DA | DF_UA | DF_UB,
    568 
    569     // B3 OP_DIV_INT_2ADDR vA, vB
    570     DF_DA | DF_UA | DF_UB,
    571 
    572     // B4 OP_REM_INT_2ADDR vA, vB
    573     DF_DA | DF_UA | DF_UB,
    574 
    575     // B5 OP_AND_INT_2ADDR vA, vB
    576     DF_DA | DF_UA | DF_UB,
    577 
    578     // B6 OP_OR_INT_2ADDR vA, vB
    579     DF_DA | DF_UA | DF_UB,
    580 
    581     // B7 OP_XOR_INT_2ADDR vA, vB
    582     DF_DA | DF_UA | DF_UB,
    583 
    584     // B8 OP_SHL_INT_2ADDR vA, vB
    585     DF_DA | DF_UA | DF_UB,
    586 
    587     // B9 OP_SHR_INT_2ADDR vA, vB
    588     DF_DA | DF_UA | DF_UB,
    589 
    590     // BA OP_USHR_INT_2ADDR vA, vB
    591     DF_DA | DF_UA | DF_UB,
    592 
    593     // BB OP_ADD_LONG_2ADDR vA, vB
    594     DF_DA_WIDE | DF_UA_WIDE | DF_UB_WIDE,
    595 
    596     // BC OP_SUB_LONG_2ADDR vA, vB
    597     DF_DA_WIDE | DF_UA_WIDE | DF_UB_WIDE,
    598 
    599     // BD OP_MUL_LONG_2ADDR vA, vB
    600     DF_DA_WIDE | DF_UA_WIDE | DF_UB_WIDE,
    601 
    602     // BE OP_DIV_LONG_2ADDR vA, vB
    603     DF_DA_WIDE | DF_UA_WIDE | DF_UB_WIDE,
    604 
    605     // BF OP_REM_LONG_2ADDR vA, vB
    606     DF_DA_WIDE | DF_UA_WIDE | DF_UB_WIDE,
    607 
    608     // C0 OP_AND_LONG_2ADDR vA, vB
    609     DF_DA_WIDE | DF_UA_WIDE | DF_UB_WIDE,
    610 
    611     // C1 OP_OR_LONG_2ADDR vA, vB
    612     DF_DA_WIDE | DF_UA_WIDE | DF_UB_WIDE,
    613 
    614     // C2 OP_XOR_LONG_2ADDR vA, vB
    615     DF_DA_WIDE | DF_UA_WIDE | DF_UB_WIDE,
    616 
    617     // C3 OP_SHL_LONG_2ADDR vA, vB
    618     DF_DA_WIDE | DF_UA_WIDE | DF_UB,
    619 
    620     // C4 OP_SHR_LONG_2ADDR vA, vB
    621     DF_DA_WIDE | DF_UA_WIDE | DF_UB,
    622 
    623     // C5 OP_USHR_LONG_2ADDR vA, vB
    624     DF_DA_WIDE | DF_UA_WIDE | DF_UB,
    625 
    626     // C6 OP_ADD_FLOAT_2ADDR vA, vB
    627     DF_DA | DF_UA | DF_UB | DF_FP_A | DF_FP_B,
    628 
    629     // C7 OP_SUB_FLOAT_2ADDR vA, vB
    630     DF_DA | DF_UA | DF_UB | DF_FP_A | DF_FP_B,
    631 
    632     // C8 OP_MUL_FLOAT_2ADDR vA, vB
    633     DF_DA | DF_UA | DF_UB | DF_FP_A | DF_FP_B,
    634 
    635     // C9 OP_DIV_FLOAT_2ADDR vA, vB
    636     DF_DA | DF_UA | DF_UB | DF_FP_A | DF_FP_B,
    637 
    638     // CA OP_REM_FLOAT_2ADDR vA, vB
    639     DF_DA | DF_UA | DF_UB | DF_FP_A | DF_FP_B,
    640 
    641     // CB OP_ADD_DOUBLE_2ADDR vA, vB
    642     DF_DA_WIDE | DF_UA_WIDE | DF_UB_WIDE | DF_FP_A | DF_FP_B,
    643 
    644     // CC OP_SUB_DOUBLE_2ADDR vA, vB
    645     DF_DA_WIDE | DF_UA_WIDE | DF_UB_WIDE | DF_FP_A | DF_FP_B,
    646 
    647     // CD OP_MUL_DOUBLE_2ADDR vA, vB
    648     DF_DA_WIDE | DF_UA_WIDE | DF_UB_WIDE | DF_FP_A | DF_FP_B,
    649 
    650     // CE OP_DIV_DOUBLE_2ADDR vA, vB
    651     DF_DA_WIDE | DF_UA_WIDE | DF_UB_WIDE | DF_FP_A | DF_FP_B,
    652 
    653     // CF OP_REM_DOUBLE_2ADDR vA, vB
    654     DF_DA_WIDE | DF_UA_WIDE | DF_UB_WIDE | DF_FP_A | DF_FP_B,
    655 
    656     // D0 OP_ADD_INT_LIT16 vA, vB, #+CCCC
    657     DF_DA | DF_UB,
    658 
    659     // D1 OP_RSUB_INT vA, vB, #+CCCC
    660     DF_DA | DF_UB,
    661 
    662     // D2 OP_MUL_INT_LIT16 vA, vB, #+CCCC
    663     DF_DA | DF_UB,
    664 
    665     // D3 OP_DIV_INT_LIT16 vA, vB, #+CCCC
    666     DF_DA | DF_UB,
    667 
    668     // D4 OP_REM_INT_LIT16 vA, vB, #+CCCC
    669     DF_DA | DF_UB,
    670 
    671     // D5 OP_AND_INT_LIT16 vA, vB, #+CCCC
    672     DF_DA | DF_UB,
    673 
    674     // D6 OP_OR_INT_LIT16 vA, vB, #+CCCC
    675     DF_DA | DF_UB,
    676 
    677     // D7 OP_XOR_INT_LIT16 vA, vB, #+CCCC
    678     DF_DA | DF_UB,
    679 
    680     // D8 OP_ADD_INT_LIT8 vAA, vBB, #+CC
    681     DF_DA | DF_UB | DF_IS_LINEAR,
    682 
    683     // D9 OP_RSUB_INT_LIT8 vAA, vBB, #+CC
    684     DF_DA | DF_UB,
    685 
    686     // DA OP_MUL_INT_LIT8 vAA, vBB, #+CC
    687     DF_DA | DF_UB,
    688 
    689     // DB OP_DIV_INT_LIT8 vAA, vBB, #+CC
    690     DF_DA | DF_UB,
    691 
    692     // DC OP_REM_INT_LIT8 vAA, vBB, #+CC
    693     DF_DA | DF_UB,
    694 
    695     // DD OP_AND_INT_LIT8 vAA, vBB, #+CC
    696     DF_DA | DF_UB,
    697 
    698     // DE OP_OR_INT_LIT8 vAA, vBB, #+CC
    699     DF_DA | DF_UB,
    700 
    701     // DF OP_XOR_INT_LIT8 vAA, vBB, #+CC
    702     DF_DA | DF_UB,
    703 
    704     // E0 OP_SHL_INT_LIT8 vAA, vBB, #+CC
    705     DF_DA | DF_UB,
    706 
    707     // E1 OP_SHR_INT_LIT8 vAA, vBB, #+CC
    708     DF_DA | DF_UB,
    709 
    710     // E2 OP_USHR_INT_LIT8 vAA, vBB, #+CC
    711     DF_DA | DF_UB,
    712 
    713     // E3 OP_IGET_VOLATILE
    714     DF_DA | DF_UB,
    715 
    716     // E4 OP_IPUT_VOLATILE
    717     DF_UA | DF_UB,
    718 
    719     // E5 OP_SGET_VOLATILE
    720     DF_DA,
    721 
    722     // E6 OP_SPUT_VOLATILE
    723     DF_UA,
    724 
    725     // E7 OP_IGET_OBJECT_VOLATILE
    726     DF_DA | DF_UB,
    727 
    728     // E8 OP_IGET_WIDE_VOLATILE
    729     DF_DA_WIDE | DF_UB,
    730 
    731     // E9 OP_IPUT_WIDE_VOLATILE
    732     DF_UA_WIDE | DF_UB,
    733 
    734     // EA OP_SGET_WIDE_VOLATILE
    735     DF_DA_WIDE,
    736 
    737     // EB OP_SPUT_WIDE_VOLATILE
    738     DF_UA_WIDE,
    739 
    740     // EC OP_BREAKPOINT
    741     DF_NOP,
    742 
    743     // ED OP_THROW_VERIFICATION_ERROR
    744     DF_NOP,
    745 
    746     // EE OP_EXECUTE_INLINE
    747     DF_FORMAT_35C,
    748 
    749     // EF OP_EXECUTE_INLINE_RANGE
    750     DF_FORMAT_3RC,
    751 
    752     // F0 OP_INVOKE_DIRECT_EMPTY
    753     DF_NOP,
    754 
    755     // F1 OP_UNUSED_F1
    756     DF_NOP,
    757 
    758     // F2 OP_IGET_QUICK
    759     DF_DA | DF_UB | DF_IS_GETTER,
    760 
    761     // F3 OP_IGET_WIDE_QUICK
    762     DF_DA_WIDE | DF_UB | DF_IS_GETTER,
    763 
    764     // F4 OP_IGET_OBJECT_QUICK
    765     DF_DA | DF_UB | DF_IS_GETTER,
    766 
    767     // F5 OP_IPUT_QUICK
    768     DF_UA | DF_UB | DF_IS_SETTER,
    769 
    770     // F6 OP_IPUT_WIDE_QUICK
    771     DF_UA_WIDE | DF_UB | DF_IS_SETTER,
    772 
    773     // F7 OP_IPUT_OBJECT_QUICK
    774     DF_UA | DF_UB | DF_IS_SETTER,
    775 
    776     // F8 OP_INVOKE_VIRTUAL_QUICK
    777     DF_FORMAT_35C,
    778 
    779     // F9 OP_INVOKE_VIRTUAL_QUICK_RANGE
    780     DF_FORMAT_3RC,
    781 
    782     // FA OP_INVOKE_SUPER_QUICK
    783     DF_FORMAT_35C,
    784 
    785     // FB OP_INVOKE_SUPER_QUICK_RANGE
    786     DF_FORMAT_3RC,
    787 
    788     // FC OP_IPUT_OBJECT_VOLATILE
    789     DF_UA | DF_UB,
    790 
    791     // FD OP_SGET_OBJECT_VOLATILE
    792     DF_DA,
    793 
    794     // FE OP_SPUT_OBJECT_VOLATILE
    795     DF_UA,
    796 
    797     // FF OP_UNUSED_FF
    798     DF_NOP,
    799 
    800     // Beginning of extended MIR opcodes
    801     // 100 OP_MIR_PHI
    802     DF_PHI | DF_DA,
    803 
    804     /*
    805      * For extended MIR inserted at the MIR2LIR stage, it is okay to have
    806      * undefined values here.
    807      */
    808 };
    809 
    810 /* Return the Dalvik register/subscript pair of a given SSA register */
    811 int dvmConvertSSARegToDalvik(CompilationUnit *cUnit, int ssaReg)
    812 {
    813       return GET_ELEM_N(cUnit->ssaToDalvikMap, int, ssaReg);
    814 }
    815 
    816 /*
    817  * Utility function to convert encoded SSA register value into Dalvik register
    818  * and subscript pair. Each SSA register can be used to index the
    819  * ssaToDalvikMap list to get the subscript[31..16]/dalvik_reg[15..0] mapping.
    820  */
    821 char *dvmCompilerGetDalvikDisassembly(DecodedInstruction *insn,
    822                                       char *note)
    823 {
    824     char buffer[256];
    825     int opcode = insn->opCode;
    826     int dfAttributes = dvmCompilerDataFlowAttributes[opcode];
    827     char *ret;
    828 
    829     buffer[0] = 0;
    830     strcpy(buffer, dexGetOpcodeName(opcode));
    831 
    832     if (note)
    833         strcat(buffer, note);
    834 
    835     if (dfAttributes & DF_FORMAT_35C) {
    836         unsigned int i;
    837         for (i = 0; i < insn->vA; i++) {
    838             if (i != 0) strcat(buffer, ",");
    839             snprintf(buffer + strlen(buffer), 256, " v%d", insn->arg[i]);
    840         }
    841     }
    842     else if (dfAttributes & DF_FORMAT_3RC) {
    843         snprintf(buffer + strlen(buffer), 256,
    844                  " v%d..v%d", insn->vC, insn->vC + insn->vA - 1);
    845     }
    846     else {
    847         if (dfAttributes & DF_A_IS_REG) {
    848             snprintf(buffer + strlen(buffer), 256, " v%d", insn->vA);
    849         }
    850         if (dfAttributes & DF_B_IS_REG) {
    851             snprintf(buffer + strlen(buffer), 256, ", v%d", insn->vB);
    852         }
    853         else {
    854             snprintf(buffer + strlen(buffer), 256, ", (#%d)", insn->vB);
    855         }
    856         if (dfAttributes & DF_C_IS_REG) {
    857             snprintf(buffer + strlen(buffer), 256, ", v%d", insn->vC);
    858         }
    859         else {
    860             snprintf(buffer + strlen(buffer), 256, ", (#%d)", insn->vC);
    861         }
    862     }
    863     int length = strlen(buffer) + 1;
    864     ret = dvmCompilerNew(length, false);
    865     memcpy(ret, buffer, length);
    866     return ret;
    867 }
    868 
    869 /*
    870  * Utility function to convert encoded SSA register value into Dalvik register
    871  * and subscript pair. Each SSA register can be used to index the
    872  * ssaToDalvikMap list to get the subscript[31..16]/dalvik_reg[15..0] mapping.
    873  */
    874 char *dvmCompilerGetSSAString(CompilationUnit *cUnit, SSARepresentation *ssaRep)
    875 {
    876     char buffer[256];
    877     char *ret;
    878     int i;
    879 
    880     buffer[0] = 0;
    881     for (i = 0; i < ssaRep->numDefs; i++) {
    882         int ssa2DalvikValue = dvmConvertSSARegToDalvik(cUnit, ssaRep->defs[i]);
    883 
    884         sprintf(buffer + strlen(buffer), "s%d(v%d_%d) ",
    885                 ssaRep->defs[i], DECODE_REG(ssa2DalvikValue),
    886                 DECODE_SUB(ssa2DalvikValue));
    887     }
    888 
    889     if (ssaRep->numDefs) {
    890         strcat(buffer, "<- ");
    891     }
    892 
    893     for (i = 0; i < ssaRep->numUses; i++) {
    894         int ssa2DalvikValue = dvmConvertSSARegToDalvik(cUnit, ssaRep->uses[i]);
    895         int len = strlen(buffer);
    896 
    897         if (snprintf(buffer + len, 250 - len, "s%d(v%d_%d) ",
    898                      ssaRep->uses[i], DECODE_REG(ssa2DalvikValue),
    899                      DECODE_SUB(ssa2DalvikValue)) >= (250 - len)) {
    900             strcat(buffer, "...");
    901             break;
    902         }
    903     }
    904 
    905     int length = strlen(buffer) + 1;
    906     ret = dvmCompilerNew(length, false);
    907     memcpy(ret, buffer, length);
    908     return ret;
    909 }
    910 
    911 /* Any register that is used before being defined is considered live-in */
    912 static inline void handleLiveInUse(BitVector *useV, BitVector *defV,
    913                                    BitVector *liveInV, int dalvikRegId)
    914 {
    915     dvmCompilerSetBit(useV, dalvikRegId);
    916     if (!dvmIsBitSet(defV, dalvikRegId)) {
    917         dvmCompilerSetBit(liveInV, dalvikRegId);
    918     }
    919 }
    920 
    921 /* Mark a reg as being defined */
    922 static inline void handleLiveInDef(BitVector *defV, int dalvikRegId)
    923 {
    924     dvmCompilerSetBit(defV, dalvikRegId);
    925 }
    926 
    927 /*
    928  * Find out live-in variables for natural loops. Variables that are live-in in
    929  * the main loop body are considered to be defined in the entry block.
    930  */
    931 void dvmCompilerFindLiveIn(CompilationUnit *cUnit, BasicBlock *bb)
    932 {
    933     MIR *mir;
    934     BitVector *useV, *defV, *liveInV;
    935 
    936     if (bb->blockType != kDalvikByteCode &&
    937         bb->blockType != kTraceEntryBlock) {
    938         return;
    939     }
    940 
    941     useV = bb->dataFlowInfo->useV =
    942         dvmCompilerAllocBitVector(cUnit->method->registersSize, false);
    943     defV = bb->dataFlowInfo->defV =
    944         dvmCompilerAllocBitVector(cUnit->method->registersSize, false);
    945     liveInV = bb->dataFlowInfo->liveInV =
    946         dvmCompilerAllocBitVector(cUnit->method->registersSize, false);
    947 
    948     for (mir = bb->firstMIRInsn; mir; mir = mir->next) {
    949         int dfAttributes =
    950             dvmCompilerDataFlowAttributes[mir->dalvikInsn.opCode];
    951         DecodedInstruction *dInsn = &mir->dalvikInsn;
    952 
    953         if (dfAttributes & DF_HAS_USES) {
    954             if (dfAttributes & DF_UA) {
    955                 handleLiveInUse(useV, defV, liveInV, dInsn->vA);
    956             } else if (dfAttributes & DF_UA_WIDE) {
    957                 handleLiveInUse(useV, defV, liveInV, dInsn->vA);
    958                 handleLiveInUse(useV, defV, liveInV, dInsn->vA+1);
    959             }
    960             if (dfAttributes & DF_UB) {
    961                 handleLiveInUse(useV, defV, liveInV, dInsn->vB);
    962             } else if (dfAttributes & DF_UB_WIDE) {
    963                 handleLiveInUse(useV, defV, liveInV, dInsn->vB);
    964                 handleLiveInUse(useV, defV, liveInV, dInsn->vB+1);
    965             }
    966             if (dfAttributes & DF_UC) {
    967                 handleLiveInUse(useV, defV, liveInV, dInsn->vC);
    968             } else if (dfAttributes & DF_UC_WIDE) {
    969                 handleLiveInUse(useV, defV, liveInV, dInsn->vC);
    970                 handleLiveInUse(useV, defV, liveInV, dInsn->vC+1);
    971             }
    972         }
    973         if (dfAttributes & DF_HAS_DEFS) {
    974             handleLiveInDef(defV, dInsn->vA);
    975             if (dfAttributes & DF_DA_WIDE) {
    976                 handleLiveInDef(defV, dInsn->vA+1);
    977             }
    978         }
    979     }
    980 }
    981 
    982 /* Find out the latest SSA register for a given Dalvik register */
    983 static void handleSSAUse(CompilationUnit *cUnit, int *uses, int dalvikReg,
    984                          int regIndex)
    985 {
    986     int encodedValue = cUnit->dalvikToSSAMap[dalvikReg];
    987     int ssaReg = DECODE_REG(encodedValue);
    988     uses[regIndex] = ssaReg;
    989 }
    990 
    991 /* Setup a new SSA register for a given Dalvik register */
    992 static void handleSSADef(CompilationUnit *cUnit, int *defs, int dalvikReg,
    993                          int regIndex)
    994 {
    995     int encodedValue = cUnit->dalvikToSSAMap[dalvikReg];
    996     int ssaReg = cUnit->numSSARegs++;
    997     /* Bump up the subscript */
    998     int dalvikSub = DECODE_SUB(encodedValue) + 1;
    999     int newD2SMapping = ENCODE_REG_SUB(ssaReg, dalvikSub);
   1000 
   1001     cUnit->dalvikToSSAMap[dalvikReg] = newD2SMapping;
   1002 
   1003     int newS2DMapping = ENCODE_REG_SUB(dalvikReg, dalvikSub);
   1004     dvmInsertGrowableList(cUnit->ssaToDalvikMap, (void *) newS2DMapping);
   1005 
   1006     defs[regIndex] = ssaReg;
   1007 }
   1008 
   1009 /* Loop up new SSA names for format_35c instructions */
   1010 static void dataFlowSSAFormat35C(CompilationUnit *cUnit, MIR *mir)
   1011 {
   1012     DecodedInstruction *dInsn = &mir->dalvikInsn;
   1013     int numUses = dInsn->vA;
   1014     int i;
   1015 
   1016     mir->ssaRep->numUses = numUses;
   1017     mir->ssaRep->uses = dvmCompilerNew(sizeof(int) * numUses, false);
   1018 
   1019     for (i = 0; i < numUses; i++) {
   1020         handleSSAUse(cUnit, mir->ssaRep->uses, dInsn->arg[i], i);
   1021     }
   1022 }
   1023 
   1024 /* Loop up new SSA names for format_3rc instructions */
   1025 static void dataFlowSSAFormat3RC(CompilationUnit *cUnit, MIR *mir)
   1026 {
   1027     DecodedInstruction *dInsn = &mir->dalvikInsn;
   1028     int numUses = dInsn->vA;
   1029     int i;
   1030 
   1031     mir->ssaRep->numUses = numUses;
   1032     mir->ssaRep->uses = dvmCompilerNew(sizeof(int) * numUses, false);
   1033 
   1034     for (i = 0; i < numUses; i++) {
   1035         handleSSAUse(cUnit, mir->ssaRep->uses, dInsn->vC+i, i);
   1036     }
   1037 }
   1038 
   1039 /* Entry function to convert a block into SSA representation */
   1040 void dvmCompilerDoSSAConversion(CompilationUnit *cUnit, BasicBlock *bb)
   1041 {
   1042     MIR *mir;
   1043 
   1044     if (bb->blockType != kDalvikByteCode && bb->blockType != kTraceEntryBlock) {
   1045         return;
   1046     }
   1047 
   1048     for (mir = bb->firstMIRInsn; mir; mir = mir->next) {
   1049         mir->ssaRep = dvmCompilerNew(sizeof(SSARepresentation), true);
   1050 
   1051         int dfAttributes =
   1052             dvmCompilerDataFlowAttributes[mir->dalvikInsn.opCode];
   1053 
   1054         int numUses = 0;
   1055 
   1056         if (dfAttributes & DF_FORMAT_35C) {
   1057             dataFlowSSAFormat35C(cUnit, mir);
   1058             continue;
   1059         }
   1060 
   1061         if (dfAttributes & DF_FORMAT_3RC) {
   1062             dataFlowSSAFormat3RC(cUnit, mir);
   1063             continue;
   1064         }
   1065 
   1066         if (dfAttributes & DF_HAS_USES) {
   1067             if (dfAttributes & DF_UA) {
   1068                 numUses++;
   1069             } else if (dfAttributes & DF_UA_WIDE) {
   1070                 numUses += 2;
   1071             }
   1072             if (dfAttributes & DF_UB) {
   1073                 numUses++;
   1074             } else if (dfAttributes & DF_UB_WIDE) {
   1075                 numUses += 2;
   1076             }
   1077             if (dfAttributes & DF_UC) {
   1078                 numUses++;
   1079             } else if (dfAttributes & DF_UC_WIDE) {
   1080                 numUses += 2;
   1081             }
   1082         }
   1083 
   1084         if (numUses) {
   1085             mir->ssaRep->numUses = numUses;
   1086             mir->ssaRep->uses = dvmCompilerNew(sizeof(int) * numUses, false);
   1087             mir->ssaRep->fpUse = dvmCompilerNew(sizeof(bool) * numUses, false);
   1088         }
   1089 
   1090         int numDefs = 0;
   1091 
   1092         if (dfAttributes & DF_HAS_DEFS) {
   1093             numDefs++;
   1094             if (dfAttributes & DF_DA_WIDE) {
   1095                 numDefs++;
   1096             }
   1097         }
   1098 
   1099         if (numDefs) {
   1100             mir->ssaRep->numDefs = numDefs;
   1101             mir->ssaRep->defs = dvmCompilerNew(sizeof(int) * numDefs, false);
   1102             mir->ssaRep->fpDef = dvmCompilerNew(sizeof(bool) * numDefs, false);
   1103         }
   1104 
   1105         DecodedInstruction *dInsn = &mir->dalvikInsn;
   1106 
   1107         if (dfAttributes & DF_HAS_USES) {
   1108             numUses = 0;
   1109             if (dfAttributes & DF_UA) {
   1110                 mir->ssaRep->fpUse[numUses] = dfAttributes & DF_FP_A;
   1111                 handleSSAUse(cUnit, mir->ssaRep->uses, dInsn->vA, numUses++);
   1112             } else if (dfAttributes & DF_UA_WIDE) {
   1113                 mir->ssaRep->fpUse[numUses] = dfAttributes & DF_FP_A;
   1114                 handleSSAUse(cUnit, mir->ssaRep->uses, dInsn->vA, numUses++);
   1115                 mir->ssaRep->fpUse[numUses] = dfAttributes & DF_FP_A;
   1116                 handleSSAUse(cUnit, mir->ssaRep->uses, dInsn->vA+1, numUses++);
   1117             }
   1118             if (dfAttributes & DF_UB) {
   1119                 mir->ssaRep->fpUse[numUses] = dfAttributes & DF_FP_B;
   1120                 handleSSAUse(cUnit, mir->ssaRep->uses, dInsn->vB, numUses++);
   1121             } else if (dfAttributes & DF_UB_WIDE) {
   1122                 mir->ssaRep->fpUse[numUses] = dfAttributes & DF_FP_B;
   1123                 handleSSAUse(cUnit, mir->ssaRep->uses, dInsn->vB, numUses++);
   1124                 mir->ssaRep->fpUse[numUses] = dfAttributes & DF_FP_B;
   1125                 handleSSAUse(cUnit, mir->ssaRep->uses, dInsn->vB+1, numUses++);
   1126             }
   1127             if (dfAttributes & DF_UC) {
   1128                 mir->ssaRep->fpUse[numUses] = dfAttributes & DF_FP_C;
   1129                 handleSSAUse(cUnit, mir->ssaRep->uses, dInsn->vC, numUses++);
   1130             } else if (dfAttributes & DF_UC_WIDE) {
   1131                 mir->ssaRep->fpUse[numUses] = dfAttributes & DF_FP_C;
   1132                 handleSSAUse(cUnit, mir->ssaRep->uses, dInsn->vC, numUses++);
   1133                 mir->ssaRep->fpUse[numUses] = dfAttributes & DF_FP_C;
   1134                 handleSSAUse(cUnit, mir->ssaRep->uses, dInsn->vC+1, numUses++);
   1135             }
   1136         }
   1137         if (dfAttributes & DF_HAS_DEFS) {
   1138             mir->ssaRep->fpDef[0] = dfAttributes & DF_FP_A;
   1139             handleSSADef(cUnit, mir->ssaRep->defs, dInsn->vA, 0);
   1140             if (dfAttributes & DF_DA_WIDE) {
   1141                 mir->ssaRep->fpDef[1] = dfAttributes & DF_FP_A;
   1142                 handleSSADef(cUnit, mir->ssaRep->defs, dInsn->vA+1, 1);
   1143             }
   1144         }
   1145     }
   1146 
   1147     bb->dataFlowInfo->dalvikToSSAMap =
   1148         dvmCompilerNew(sizeof(int) * cUnit->method->registersSize, false);
   1149 
   1150     /* Take a snapshot of Dalvik->SSA mapping at the end of each block */
   1151     memcpy(bb->dataFlowInfo->dalvikToSSAMap, cUnit->dalvikToSSAMap,
   1152            sizeof(int) * cUnit->method->registersSize);
   1153 }
   1154 
   1155 /* Setup a constant value for opcodes thare have the DF_SETS_CONST attribute */
   1156 static void setConstant(CompilationUnit *cUnit, int ssaReg, int value)
   1157 {
   1158     dvmSetBit(cUnit->isConstantV, ssaReg);
   1159     cUnit->constantValues[ssaReg] = value;
   1160 }
   1161 
   1162 void dvmCompilerDoConstantPropagation(CompilationUnit *cUnit, BasicBlock *bb)
   1163 {
   1164     MIR *mir;
   1165     BitVector *isConstantV = cUnit->isConstantV;
   1166 
   1167     for (mir = bb->firstMIRInsn; mir; mir = mir->next) {
   1168         int dfAttributes =
   1169             dvmCompilerDataFlowAttributes[mir->dalvikInsn.opCode];
   1170 
   1171         DecodedInstruction *dInsn = &mir->dalvikInsn;
   1172 
   1173         if (!(dfAttributes & DF_HAS_DEFS)) continue;
   1174 
   1175         /* Handle instructions that set up constants directly */
   1176         if (dfAttributes & DF_SETS_CONST) {
   1177             if (dfAttributes & DF_DA) {
   1178                 switch (dInsn->opCode) {
   1179                     case OP_CONST_4:
   1180                     case OP_CONST_16:
   1181                     case OP_CONST:
   1182                         setConstant(cUnit, mir->ssaRep->defs[0], dInsn->vB);
   1183                         break;
   1184                     case OP_CONST_HIGH16:
   1185                         setConstant(cUnit, mir->ssaRep->defs[0],
   1186                                     dInsn->vB << 16);
   1187                         break;
   1188                     default:
   1189                         break;
   1190                 }
   1191             } else if (dfAttributes & DF_DA_WIDE) {
   1192                 switch (dInsn->opCode) {
   1193                     case OP_CONST_WIDE_16:
   1194                     case OP_CONST_WIDE_32:
   1195                         setConstant(cUnit, mir->ssaRep->defs[0], dInsn->vB);
   1196                         setConstant(cUnit, mir->ssaRep->defs[1], 0);
   1197                         break;
   1198                     case OP_CONST_WIDE:
   1199                         setConstant(cUnit, mir->ssaRep->defs[0],
   1200                                     (int) dInsn->vB_wide);
   1201                         setConstant(cUnit, mir->ssaRep->defs[1],
   1202                                     (int) (dInsn->vB_wide >> 32));
   1203                         break;
   1204                     case OP_CONST_WIDE_HIGH16:
   1205                         setConstant(cUnit, mir->ssaRep->defs[0], 0);
   1206                         setConstant(cUnit, mir->ssaRep->defs[1],
   1207                                     dInsn->vB << 16);
   1208                         break;
   1209                     default:
   1210                         break;
   1211                 }
   1212             }
   1213         /* Handle instructions that set up constants directly */
   1214         } else if (dfAttributes & DF_IS_MOVE) {
   1215             int i;
   1216 
   1217             for (i = 0; i < mir->ssaRep->numUses; i++) {
   1218                 if (!dvmIsBitSet(isConstantV, mir->ssaRep->uses[i])) break;
   1219             }
   1220             /* Move a register holding a constant to another register */
   1221             if (i == mir->ssaRep->numUses) {
   1222                 setConstant(cUnit, mir->ssaRep->defs[0],
   1223                             cUnit->constantValues[mir->ssaRep->uses[0]]);
   1224                 if (dfAttributes & DF_DA_WIDE) {
   1225                     setConstant(cUnit, mir->ssaRep->defs[1],
   1226                                 cUnit->constantValues[mir->ssaRep->uses[1]]);
   1227                 }
   1228             }
   1229         }
   1230     }
   1231     /* TODO: implement code to handle arithmetic operations */
   1232 }
   1233 
   1234 void dvmCompilerFindInductionVariables(struct CompilationUnit *cUnit,
   1235                                        struct BasicBlock *bb)
   1236 {
   1237     BitVector *isIndVarV = cUnit->loopAnalysis->isIndVarV;
   1238     BitVector *isConstantV = cUnit->isConstantV;
   1239     GrowableList *ivList = cUnit->loopAnalysis->ivList;
   1240     MIR *mir;
   1241 
   1242     if (bb->blockType != kDalvikByteCode &&
   1243         bb->blockType != kTraceEntryBlock) {
   1244         return;
   1245     }
   1246 
   1247     /* If the bb doesn't have a phi it cannot contain an induction variable */
   1248     if (bb->firstMIRInsn == NULL ||
   1249         bb->firstMIRInsn->dalvikInsn.opCode != kMirOpPhi) {
   1250         return;
   1251     }
   1252 
   1253     /* Find basic induction variable first */
   1254     for (mir = bb->firstMIRInsn; mir; mir = mir->next) {
   1255         int dfAttributes =
   1256             dvmCompilerDataFlowAttributes[mir->dalvikInsn.opCode];
   1257 
   1258         if (!(dfAttributes & DF_IS_LINEAR)) continue;
   1259 
   1260         /*
   1261          * For a basic induction variable:
   1262          *   1) use[0] should belong to the output of a phi node
   1263          *   2) def[0] should belong to the input of the same phi node
   1264          *   3) the value added/subtracted is a constant
   1265          */
   1266         MIR *phi;
   1267         for (phi = bb->firstMIRInsn; phi; phi = phi->next) {
   1268             if (phi->dalvikInsn.opCode != kMirOpPhi) break;
   1269 
   1270             if (phi->ssaRep->defs[0] == mir->ssaRep->uses[0] &&
   1271                 phi->ssaRep->uses[1] == mir->ssaRep->defs[0]) {
   1272                 bool deltaIsConstant = false;
   1273                 int deltaValue;
   1274 
   1275                 switch (mir->dalvikInsn.opCode) {
   1276                     case OP_ADD_INT:
   1277                         if (dvmIsBitSet(isConstantV,
   1278                                         mir->ssaRep->uses[1])) {
   1279                             deltaValue =
   1280                                 cUnit->constantValues[mir->ssaRep->uses[1]];
   1281                             deltaIsConstant = true;
   1282                         }
   1283                         break;
   1284                     case OP_SUB_INT:
   1285                         if (dvmIsBitSet(isConstantV,
   1286                                         mir->ssaRep->uses[1])) {
   1287                             deltaValue =
   1288                                 -cUnit->constantValues[mir->ssaRep->uses[1]];
   1289                             deltaIsConstant = true;
   1290                         }
   1291                         break;
   1292                     case OP_ADD_INT_LIT8:
   1293                         deltaValue = mir->dalvikInsn.vC;
   1294                         deltaIsConstant = true;
   1295                         break;
   1296                     default:
   1297                         break;
   1298                 }
   1299                 if (deltaIsConstant) {
   1300                     dvmSetBit(isIndVarV, mir->ssaRep->uses[0]);
   1301                     InductionVariableInfo *ivInfo =
   1302                         dvmCompilerNew(sizeof(InductionVariableInfo),
   1303                                        false);
   1304 
   1305                     ivInfo->ssaReg = mir->ssaRep->uses[0];
   1306                     ivInfo->basicSSAReg = mir->ssaRep->uses[0];
   1307                     ivInfo->m = 1;         // always 1 to basic iv
   1308                     ivInfo->c = 0;         // N/A to basic iv
   1309                     ivInfo->inc = deltaValue;
   1310                     dvmInsertGrowableList(ivList, (void *) ivInfo);
   1311                     cUnit->loopAnalysis->numBasicIV++;
   1312                     break;
   1313                 }
   1314             }
   1315         }
   1316     }
   1317 
   1318     /* Find dependent induction variable now */
   1319     for (mir = bb->firstMIRInsn; mir; mir = mir->next) {
   1320         int dfAttributes =
   1321             dvmCompilerDataFlowAttributes[mir->dalvikInsn.opCode];
   1322 
   1323         if (!(dfAttributes & DF_IS_LINEAR)) continue;
   1324 
   1325         /* Skip already identified induction variables */
   1326         if (dvmIsBitSet(isIndVarV, mir->ssaRep->defs[0])) continue;
   1327 
   1328         /*
   1329          * For a dependent induction variable:
   1330          *  1) use[0] should be an induction variable (basic/dependent)
   1331          *  2) operand2 should be a constant
   1332          */
   1333         if (dvmIsBitSet(isIndVarV, mir->ssaRep->uses[0])) {
   1334             int srcDalvikReg = dvmConvertSSARegToDalvik(cUnit,
   1335                                                         mir->ssaRep->uses[0]);
   1336             int dstDalvikReg = dvmConvertSSARegToDalvik(cUnit,
   1337                                                         mir->ssaRep->defs[0]);
   1338 
   1339             bool cIsConstant = false;
   1340             int c = 0;
   1341 
   1342             switch (mir->dalvikInsn.opCode) {
   1343                 case OP_ADD_INT:
   1344                     if (dvmIsBitSet(isConstantV,
   1345                                     mir->ssaRep->uses[1])) {
   1346                         c = cUnit->constantValues[mir->ssaRep->uses[1]];
   1347                         cIsConstant = true;
   1348                     }
   1349                     break;
   1350                 case OP_SUB_INT:
   1351                     if (dvmIsBitSet(isConstantV,
   1352                                     mir->ssaRep->uses[1])) {
   1353                         c = -cUnit->constantValues[mir->ssaRep->uses[1]];
   1354                         cIsConstant = true;
   1355                     }
   1356                     break;
   1357                 case OP_ADD_INT_LIT8:
   1358                     c = mir->dalvikInsn.vC;
   1359                     cIsConstant = true;
   1360                     break;
   1361                 default:
   1362                     break;
   1363             }
   1364 
   1365             /* Ignore the update to the basic induction variable itself */
   1366             if (DECODE_REG(srcDalvikReg) == DECODE_REG(dstDalvikReg))  {
   1367                 cUnit->loopAnalysis->ssaBIV = mir->ssaRep->defs[0];
   1368                 cIsConstant = false;
   1369             }
   1370 
   1371             if (cIsConstant) {
   1372                 unsigned int i;
   1373                 dvmSetBit(isIndVarV, mir->ssaRep->defs[0]);
   1374                 InductionVariableInfo *ivInfo =
   1375                     dvmCompilerNew(sizeof(InductionVariableInfo),
   1376                                    false);
   1377                 InductionVariableInfo *ivInfoOld = NULL ;
   1378 
   1379                 for (i = 0; i < ivList->numUsed; i++) {
   1380                     ivInfoOld = ivList->elemList[i];
   1381                     if (ivInfoOld->ssaReg == mir->ssaRep->uses[0]) break;
   1382                 }
   1383 
   1384                 /* Guaranteed to find an element */
   1385                 assert(i < ivList->numUsed);
   1386 
   1387                 ivInfo->ssaReg = mir->ssaRep->defs[0];
   1388                 ivInfo->basicSSAReg = ivInfoOld->basicSSAReg;
   1389                 ivInfo->m = ivInfoOld->m;
   1390                 ivInfo->c = c + ivInfoOld->c;
   1391                 ivInfo->inc = ivInfoOld->inc;
   1392                 dvmInsertGrowableList(ivList, (void *) ivInfo);
   1393             }
   1394         }
   1395     }
   1396 }
   1397 
   1398 /* Setup the basic data structures for SSA conversion */
   1399 void dvmInitializeSSAConversion(CompilationUnit *cUnit)
   1400 {
   1401     int i;
   1402     int numDalvikReg = cUnit->method->registersSize;
   1403 
   1404     cUnit->ssaToDalvikMap = dvmCompilerNew(sizeof(GrowableList), false);
   1405     dvmInitGrowableList(cUnit->ssaToDalvikMap, numDalvikReg);
   1406 
   1407     /*
   1408      * Initial number of SSA registers is equal to the number of Dalvik
   1409      * registers.
   1410      */
   1411     cUnit->numSSARegs = numDalvikReg;
   1412 
   1413     /*
   1414      * Initialize the SSA2Dalvik map list. For the first numDalvikReg elements,
   1415      * the subscript is 0 so we use the ENCODE_REG_SUB macro to encode the value
   1416      * into "(0 << 16) | i"
   1417      */
   1418     for (i = 0; i < numDalvikReg; i++) {
   1419         dvmInsertGrowableList(cUnit->ssaToDalvikMap,
   1420                               (void *) ENCODE_REG_SUB(i, 0));
   1421     }
   1422 
   1423     /*
   1424      * Initialize the DalvikToSSAMap map. The low 16 bit is the SSA register id,
   1425      * while the high 16 bit is the current subscript. The original Dalvik
   1426      * register N is mapped to SSA register N with subscript 0.
   1427      */
   1428     cUnit->dalvikToSSAMap = dvmCompilerNew(sizeof(int) * numDalvikReg, false);
   1429     for (i = 0; i < numDalvikReg; i++) {
   1430         cUnit->dalvikToSSAMap[i] = i;
   1431     }
   1432 
   1433     /*
   1434      * Allocate the BasicBlockDataFlow structure for the entry and code blocks
   1435      */
   1436     for (i = 0; i < cUnit->numBlocks; i++) {
   1437         BasicBlock *bb = cUnit->blockList[i];
   1438         if (bb->blockType == kDalvikByteCode ||
   1439             bb->blockType == kTraceEntryBlock) {
   1440             bb->dataFlowInfo = dvmCompilerNew(sizeof(BasicBlockDataFlow), true);
   1441         }
   1442     }
   1443 }
   1444 
   1445 void dvmCompilerDataFlowAnalysisDispatcher(CompilationUnit *cUnit,
   1446                 void (*func)(CompilationUnit *, BasicBlock *))
   1447 {
   1448     int i;
   1449     for (i = 0; i < cUnit->numBlocks; i++) {
   1450         BasicBlock *bb = cUnit->blockList[i];
   1451         (*func)(cUnit, bb);
   1452     }
   1453 }
   1454 
   1455 /* Main entry point to do SSA conversion for non-loop traces */
   1456 void dvmCompilerNonLoopAnalysis(CompilationUnit *cUnit)
   1457 {
   1458     dvmCompilerDataFlowAnalysisDispatcher(cUnit, dvmCompilerDoSSAConversion);
   1459 }
   1460