1 /* 2 * Copyright (C) 2011 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 "compiler_internals.h" 18 #include "local_value_numbering.h" 19 #include "dataflow_iterator-inl.h" 20 21 namespace art { 22 23 /* 24 * Main table containing data flow attributes for each bytecode. The 25 * first kNumPackedOpcodes entries are for Dalvik bytecode 26 * instructions, where extended opcode at the MIR level are appended 27 * afterwards. 28 * 29 * TODO - many optimization flags are incomplete - they will only limit the 30 * scope of optimizations but will not cause mis-optimizations. 31 */ 32 const uint64_t MIRGraph::oat_data_flow_attributes_[kMirOpLast] = { 33 // 00 NOP 34 DF_NOP, 35 36 // 01 MOVE vA, vB 37 DF_DA | DF_UB | DF_IS_MOVE, 38 39 // 02 MOVE_FROM16 vAA, vBBBB 40 DF_DA | DF_UB | DF_IS_MOVE, 41 42 // 03 MOVE_16 vAAAA, vBBBB 43 DF_DA | DF_UB | DF_IS_MOVE, 44 45 // 04 MOVE_WIDE vA, vB 46 DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_IS_MOVE, 47 48 // 05 MOVE_WIDE_FROM16 vAA, vBBBB 49 DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_IS_MOVE, 50 51 // 06 MOVE_WIDE_16 vAAAA, vBBBB 52 DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_IS_MOVE, 53 54 // 07 MOVE_OBJECT vA, vB 55 DF_DA | DF_UB | DF_NULL_TRANSFER_0 | DF_IS_MOVE | DF_REF_A | DF_REF_B, 56 57 // 08 MOVE_OBJECT_FROM16 vAA, vBBBB 58 DF_DA | DF_UB | DF_NULL_TRANSFER_0 | DF_IS_MOVE | DF_REF_A | DF_REF_B, 59 60 // 09 MOVE_OBJECT_16 vAAAA, vBBBB 61 DF_DA | DF_UB | DF_NULL_TRANSFER_0 | DF_IS_MOVE | DF_REF_A | DF_REF_B, 62 63 // 0A MOVE_RESULT vAA 64 DF_DA, 65 66 // 0B MOVE_RESULT_WIDE vAA 67 DF_DA | DF_A_WIDE, 68 69 // 0C MOVE_RESULT_OBJECT vAA 70 DF_DA | DF_REF_A, 71 72 // 0D MOVE_EXCEPTION vAA 73 DF_DA | DF_REF_A | DF_NON_NULL_DST, 74 75 // 0E RETURN_VOID 76 DF_NOP, 77 78 // 0F RETURN vAA 79 DF_UA, 80 81 // 10 RETURN_WIDE vAA 82 DF_UA | DF_A_WIDE, 83 84 // 11 RETURN_OBJECT vAA 85 DF_UA | DF_REF_A, 86 87 // 12 CONST_4 vA, #+B 88 DF_DA | DF_SETS_CONST, 89 90 // 13 CONST_16 vAA, #+BBBB 91 DF_DA | DF_SETS_CONST, 92 93 // 14 CONST vAA, #+BBBBBBBB 94 DF_DA | DF_SETS_CONST, 95 96 // 15 CONST_HIGH16 VAA, #+BBBB0000 97 DF_DA | DF_SETS_CONST, 98 99 // 16 CONST_WIDE_16 vAA, #+BBBB 100 DF_DA | DF_A_WIDE | DF_SETS_CONST, 101 102 // 17 CONST_WIDE_32 vAA, #+BBBBBBBB 103 DF_DA | DF_A_WIDE | DF_SETS_CONST, 104 105 // 18 CONST_WIDE vAA, #+BBBBBBBBBBBBBBBB 106 DF_DA | DF_A_WIDE | DF_SETS_CONST, 107 108 // 19 CONST_WIDE_HIGH16 vAA, #+BBBB000000000000 109 DF_DA | DF_A_WIDE | DF_SETS_CONST, 110 111 // 1A CONST_STRING vAA, string@BBBB 112 DF_DA | DF_REF_A | DF_NON_NULL_DST, 113 114 // 1B CONST_STRING_JUMBO vAA, string@BBBBBBBB 115 DF_DA | DF_REF_A | DF_NON_NULL_DST, 116 117 // 1C CONST_CLASS vAA, type@BBBB 118 DF_DA | DF_REF_A | DF_NON_NULL_DST, 119 120 // 1D MONITOR_ENTER vAA 121 DF_UA | DF_NULL_CHK_0 | DF_REF_A, 122 123 // 1E MONITOR_EXIT vAA 124 DF_UA | DF_NULL_CHK_0 | DF_REF_A, 125 126 // 1F CHK_CAST vAA, type@BBBB 127 DF_UA | DF_REF_A | DF_UMS, 128 129 // 20 INSTANCE_OF vA, vB, type@CCCC 130 DF_DA | DF_UB | DF_CORE_A | DF_REF_B | DF_UMS, 131 132 // 21 ARRAY_LENGTH vA, vB 133 DF_DA | DF_UB | DF_NULL_CHK_0 | DF_CORE_A | DF_REF_B, 134 135 // 22 NEW_INSTANCE vAA, type@BBBB 136 DF_DA | DF_NON_NULL_DST | DF_REF_A | DF_UMS, 137 138 // 23 NEW_ARRAY vA, vB, type@CCCC 139 DF_DA | DF_UB | DF_NON_NULL_DST | DF_REF_A | DF_CORE_B | DF_UMS, 140 141 // 24 FILLED_NEW_ARRAY {vD, vE, vF, vG, vA} 142 DF_FORMAT_35C | DF_NON_NULL_RET | DF_UMS, 143 144 // 25 FILLED_NEW_ARRAY_RANGE {vCCCC .. vNNNN}, type@BBBB 145 DF_FORMAT_3RC | DF_NON_NULL_RET | DF_UMS, 146 147 // 26 FILL_ARRAY_DATA vAA, +BBBBBBBB 148 DF_UA | DF_REF_A | DF_UMS, 149 150 // 27 THROW vAA 151 DF_UA | DF_REF_A | DF_UMS, 152 153 // 28 GOTO 154 DF_NOP, 155 156 // 29 GOTO_16 157 DF_NOP, 158 159 // 2A GOTO_32 160 DF_NOP, 161 162 // 2B PACKED_SWITCH vAA, +BBBBBBBB 163 DF_UA, 164 165 // 2C SPARSE_SWITCH vAA, +BBBBBBBB 166 DF_UA, 167 168 // 2D CMPL_FLOAT vAA, vBB, vCC 169 DF_DA | DF_UB | DF_UC | DF_FP_B | DF_FP_C | DF_CORE_A, 170 171 // 2E CMPG_FLOAT vAA, vBB, vCC 172 DF_DA | DF_UB | DF_UC | DF_FP_B | DF_FP_C | DF_CORE_A, 173 174 // 2F CMPL_DOUBLE vAA, vBB, vCC 175 DF_DA | DF_UB | DF_B_WIDE | DF_UC | DF_C_WIDE | DF_FP_B | DF_FP_C | DF_CORE_A, 176 177 // 30 CMPG_DOUBLE vAA, vBB, vCC 178 DF_DA | DF_UB | DF_B_WIDE | DF_UC | DF_C_WIDE | DF_FP_B | DF_FP_C | DF_CORE_A, 179 180 // 31 CMP_LONG vAA, vBB, vCC 181 DF_DA | DF_UB | DF_B_WIDE | DF_UC | DF_C_WIDE | DF_CORE_A | DF_CORE_B | DF_CORE_C, 182 183 // 32 IF_EQ vA, vB, +CCCC 184 DF_UA | DF_UB, 185 186 // 33 IF_NE vA, vB, +CCCC 187 DF_UA | DF_UB, 188 189 // 34 IF_LT vA, vB, +CCCC 190 DF_UA | DF_UB, 191 192 // 35 IF_GE vA, vB, +CCCC 193 DF_UA | DF_UB, 194 195 // 36 IF_GT vA, vB, +CCCC 196 DF_UA | DF_UB, 197 198 // 37 IF_LE vA, vB, +CCCC 199 DF_UA | DF_UB, 200 201 // 38 IF_EQZ vAA, +BBBB 202 DF_UA, 203 204 // 39 IF_NEZ vAA, +BBBB 205 DF_UA, 206 207 // 3A IF_LTZ vAA, +BBBB 208 DF_UA, 209 210 // 3B IF_GEZ vAA, +BBBB 211 DF_UA, 212 213 // 3C IF_GTZ vAA, +BBBB 214 DF_UA, 215 216 // 3D IF_LEZ vAA, +BBBB 217 DF_UA, 218 219 // 3E UNUSED_3E 220 DF_NOP, 221 222 // 3F UNUSED_3F 223 DF_NOP, 224 225 // 40 UNUSED_40 226 DF_NOP, 227 228 // 41 UNUSED_41 229 DF_NOP, 230 231 // 42 UNUSED_42 232 DF_NOP, 233 234 // 43 UNUSED_43 235 DF_NOP, 236 237 // 44 AGET vAA, vBB, vCC 238 DF_DA | DF_UB | DF_UC | DF_NULL_CHK_0 | DF_RANGE_CHK_1 | DF_REF_B | DF_CORE_C | DF_LVN, 239 240 // 45 AGET_WIDE vAA, vBB, vCC 241 DF_DA | DF_A_WIDE | DF_UB | DF_UC | DF_NULL_CHK_0 | DF_RANGE_CHK_1 | DF_REF_B | DF_CORE_C | DF_LVN, 242 243 // 46 AGET_OBJECT vAA, vBB, vCC 244 DF_DA | DF_UB | DF_UC | DF_NULL_CHK_0 | DF_RANGE_CHK_1 | DF_REF_A | DF_REF_B | DF_CORE_C | DF_LVN, 245 246 // 47 AGET_BOOLEAN vAA, vBB, vCC 247 DF_DA | DF_UB | DF_UC | DF_NULL_CHK_0 | DF_RANGE_CHK_1 | DF_REF_B | DF_CORE_C | DF_LVN, 248 249 // 48 AGET_BYTE vAA, vBB, vCC 250 DF_DA | DF_UB | DF_UC | DF_NULL_CHK_0 | DF_RANGE_CHK_1 | DF_REF_B | DF_CORE_C | DF_LVN, 251 252 // 49 AGET_CHAR vAA, vBB, vCC 253 DF_DA | DF_UB | DF_UC | DF_NULL_CHK_0 | DF_RANGE_CHK_1 | DF_REF_B | DF_CORE_C | DF_LVN, 254 255 // 4A AGET_SHORT vAA, vBB, vCC 256 DF_DA | DF_UB | DF_UC | DF_NULL_CHK_0 | DF_RANGE_CHK_1 | DF_REF_B | DF_CORE_C | DF_LVN, 257 258 // 4B APUT vAA, vBB, vCC 259 DF_UA | DF_UB | DF_UC | DF_NULL_CHK_1 | DF_RANGE_CHK_2 | DF_REF_B | DF_CORE_C | DF_LVN, 260 261 // 4C APUT_WIDE vAA, vBB, vCC 262 DF_UA | DF_A_WIDE | DF_UB | DF_UC | DF_NULL_CHK_2 | DF_RANGE_CHK_3 | DF_REF_B | DF_CORE_C | DF_LVN, 263 264 // 4D APUT_OBJECT vAA, vBB, vCC 265 DF_UA | DF_UB | DF_UC | DF_NULL_CHK_1 | DF_RANGE_CHK_2 | DF_REF_A | DF_REF_B | DF_CORE_C | DF_LVN, 266 267 // 4E APUT_BOOLEAN vAA, vBB, vCC 268 DF_UA | DF_UB | DF_UC | DF_NULL_CHK_1 | DF_RANGE_CHK_2 | DF_REF_B | DF_CORE_C | DF_LVN, 269 270 // 4F APUT_BYTE vAA, vBB, vCC 271 DF_UA | DF_UB | DF_UC | DF_NULL_CHK_1 | DF_RANGE_CHK_2 | DF_REF_B | DF_CORE_C | DF_LVN, 272 273 // 50 APUT_CHAR vAA, vBB, vCC 274 DF_UA | DF_UB | DF_UC | DF_NULL_CHK_1 | DF_RANGE_CHK_2 | DF_REF_B | DF_CORE_C | DF_LVN, 275 276 // 51 APUT_SHORT vAA, vBB, vCC 277 DF_UA | DF_UB | DF_UC | DF_NULL_CHK_1 | DF_RANGE_CHK_2 | DF_REF_B | DF_CORE_C | DF_LVN, 278 279 // 52 IGET vA, vB, field@CCCC 280 DF_DA | DF_UB | DF_NULL_CHK_0 | DF_REF_B | DF_IFIELD | DF_LVN, 281 282 // 53 IGET_WIDE vA, vB, field@CCCC 283 DF_DA | DF_A_WIDE | DF_UB | DF_NULL_CHK_0 | DF_REF_B | DF_IFIELD | DF_LVN, 284 285 // 54 IGET_OBJECT vA, vB, field@CCCC 286 DF_DA | DF_UB | DF_NULL_CHK_0 | DF_REF_A | DF_REF_B | DF_IFIELD | DF_LVN, 287 288 // 55 IGET_BOOLEAN vA, vB, field@CCCC 289 DF_DA | DF_UB | DF_NULL_CHK_0 | DF_REF_B | DF_IFIELD | DF_LVN, 290 291 // 56 IGET_BYTE vA, vB, field@CCCC 292 DF_DA | DF_UB | DF_NULL_CHK_0 | DF_REF_B | DF_IFIELD | DF_LVN, 293 294 // 57 IGET_CHAR vA, vB, field@CCCC 295 DF_DA | DF_UB | DF_NULL_CHK_0 | DF_REF_B | DF_IFIELD | DF_LVN, 296 297 // 58 IGET_SHORT vA, vB, field@CCCC 298 DF_DA | DF_UB | DF_NULL_CHK_0 | DF_REF_B | DF_IFIELD | DF_LVN, 299 300 // 59 IPUT vA, vB, field@CCCC 301 DF_UA | DF_UB | DF_NULL_CHK_1 | DF_REF_B | DF_IFIELD | DF_LVN, 302 303 // 5A IPUT_WIDE vA, vB, field@CCCC 304 DF_UA | DF_A_WIDE | DF_UB | DF_NULL_CHK_2 | DF_REF_B | DF_IFIELD | DF_LVN, 305 306 // 5B IPUT_OBJECT vA, vB, field@CCCC 307 DF_UA | DF_UB | DF_NULL_CHK_1 | DF_REF_A | DF_REF_B | DF_IFIELD | DF_LVN, 308 309 // 5C IPUT_BOOLEAN vA, vB, field@CCCC 310 DF_UA | DF_UB | DF_NULL_CHK_1 | DF_REF_B | DF_IFIELD | DF_LVN, 311 312 // 5D IPUT_BYTE vA, vB, field@CCCC 313 DF_UA | DF_UB | DF_NULL_CHK_1 | DF_REF_B | DF_IFIELD | DF_LVN, 314 315 // 5E IPUT_CHAR vA, vB, field@CCCC 316 DF_UA | DF_UB | DF_NULL_CHK_1 | DF_REF_B | DF_IFIELD | DF_LVN, 317 318 // 5F IPUT_SHORT vA, vB, field@CCCC 319 DF_UA | DF_UB | DF_NULL_CHK_1 | DF_REF_B | DF_IFIELD | DF_LVN, 320 321 // 60 SGET vAA, field@BBBB 322 DF_DA | DF_SFIELD | DF_UMS, 323 324 // 61 SGET_WIDE vAA, field@BBBB 325 DF_DA | DF_A_WIDE | DF_SFIELD | DF_UMS, 326 327 // 62 SGET_OBJECT vAA, field@BBBB 328 DF_DA | DF_REF_A | DF_SFIELD | DF_UMS, 329 330 // 63 SGET_BOOLEAN vAA, field@BBBB 331 DF_DA | DF_SFIELD | DF_UMS, 332 333 // 64 SGET_BYTE vAA, field@BBBB 334 DF_DA | DF_SFIELD | DF_UMS, 335 336 // 65 SGET_CHAR vAA, field@BBBB 337 DF_DA | DF_SFIELD | DF_UMS, 338 339 // 66 SGET_SHORT vAA, field@BBBB 340 DF_DA | DF_SFIELD | DF_UMS, 341 342 // 67 SPUT vAA, field@BBBB 343 DF_UA | DF_SFIELD | DF_UMS, 344 345 // 68 SPUT_WIDE vAA, field@BBBB 346 DF_UA | DF_A_WIDE | DF_SFIELD | DF_UMS, 347 348 // 69 SPUT_OBJECT vAA, field@BBBB 349 DF_UA | DF_REF_A | DF_SFIELD | DF_UMS, 350 351 // 6A SPUT_BOOLEAN vAA, field@BBBB 352 DF_UA | DF_SFIELD | DF_UMS, 353 354 // 6B SPUT_BYTE vAA, field@BBBB 355 DF_UA | DF_SFIELD | DF_UMS, 356 357 // 6C SPUT_CHAR vAA, field@BBBB 358 DF_UA | DF_SFIELD | DF_UMS, 359 360 // 6D SPUT_SHORT vAA, field@BBBB 361 DF_UA | DF_SFIELD | DF_UMS, 362 363 // 6E INVOKE_VIRTUAL {vD, vE, vF, vG, vA} 364 DF_FORMAT_35C | DF_NULL_CHK_OUT0 | DF_UMS, 365 366 // 6F INVOKE_SUPER {vD, vE, vF, vG, vA} 367 DF_FORMAT_35C | DF_NULL_CHK_OUT0 | DF_UMS, 368 369 // 70 INVOKE_DIRECT {vD, vE, vF, vG, vA} 370 DF_FORMAT_35C | DF_NULL_CHK_OUT0 | DF_UMS, 371 372 // 71 INVOKE_STATIC {vD, vE, vF, vG, vA} 373 DF_FORMAT_35C | DF_UMS, 374 375 // 72 INVOKE_INTERFACE {vD, vE, vF, vG, vA} 376 DF_FORMAT_35C | DF_NULL_CHK_OUT0 | DF_UMS, 377 378 // 73 UNUSED_73 379 DF_NOP, 380 381 // 74 INVOKE_VIRTUAL_RANGE {vCCCC .. vNNNN} 382 DF_FORMAT_3RC | DF_NULL_CHK_OUT0 | DF_UMS, 383 384 // 75 INVOKE_SUPER_RANGE {vCCCC .. vNNNN} 385 DF_FORMAT_3RC | DF_NULL_CHK_OUT0 | DF_UMS, 386 387 // 76 INVOKE_DIRECT_RANGE {vCCCC .. vNNNN} 388 DF_FORMAT_3RC | DF_NULL_CHK_OUT0 | DF_UMS, 389 390 // 77 INVOKE_STATIC_RANGE {vCCCC .. vNNNN} 391 DF_FORMAT_3RC | DF_UMS, 392 393 // 78 INVOKE_INTERFACE_RANGE {vCCCC .. vNNNN} 394 DF_FORMAT_3RC | DF_NULL_CHK_OUT0 | DF_UMS, 395 396 // 79 UNUSED_79 397 DF_NOP, 398 399 // 7A UNUSED_7A 400 DF_NOP, 401 402 // 7B NEG_INT vA, vB 403 DF_DA | DF_UB | DF_CORE_A | DF_CORE_B, 404 405 // 7C NOT_INT vA, vB 406 DF_DA | DF_UB | DF_CORE_A | DF_CORE_B, 407 408 // 7D NEG_LONG vA, vB 409 DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_CORE_A | DF_CORE_B, 410 411 // 7E NOT_LONG vA, vB 412 DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_CORE_A | DF_CORE_B, 413 414 // 7F NEG_FLOAT vA, vB 415 DF_DA | DF_UB | DF_FP_A | DF_FP_B, 416 417 // 80 NEG_DOUBLE vA, vB 418 DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_FP_A | DF_FP_B, 419 420 // 81 INT_TO_LONG vA, vB 421 DF_DA | DF_A_WIDE | DF_UB | DF_CORE_A | DF_CORE_B, 422 423 // 82 INT_TO_FLOAT vA, vB 424 DF_DA | DF_UB | DF_FP_A | DF_CORE_B, 425 426 // 83 INT_TO_DOUBLE vA, vB 427 DF_DA | DF_A_WIDE | DF_UB | DF_FP_A | DF_CORE_B, 428 429 // 84 LONG_TO_INT vA, vB 430 DF_DA | DF_UB | DF_B_WIDE | DF_CORE_A | DF_CORE_B, 431 432 // 85 LONG_TO_FLOAT vA, vB 433 DF_DA | DF_UB | DF_B_WIDE | DF_FP_A | DF_CORE_B, 434 435 // 86 LONG_TO_DOUBLE vA, vB 436 DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_FP_A | DF_CORE_B, 437 438 // 87 FLOAT_TO_INT vA, vB 439 DF_DA | DF_UB | DF_FP_B | DF_CORE_A, 440 441 // 88 FLOAT_TO_LONG vA, vB 442 DF_DA | DF_A_WIDE | DF_UB | DF_FP_B | DF_CORE_A, 443 444 // 89 FLOAT_TO_DOUBLE vA, vB 445 DF_DA | DF_A_WIDE | DF_UB | DF_FP_A | DF_FP_B, 446 447 // 8A DOUBLE_TO_INT vA, vB 448 DF_DA | DF_UB | DF_B_WIDE | DF_FP_B | DF_CORE_A, 449 450 // 8B DOUBLE_TO_LONG vA, vB 451 DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_FP_B | DF_CORE_A, 452 453 // 8C DOUBLE_TO_FLOAT vA, vB 454 DF_DA | DF_UB | DF_B_WIDE | DF_FP_A | DF_FP_B, 455 456 // 8D INT_TO_BYTE vA, vB 457 DF_DA | DF_UB | DF_CORE_A | DF_CORE_B, 458 459 // 8E INT_TO_CHAR vA, vB 460 DF_DA | DF_UB | DF_CORE_A | DF_CORE_B, 461 462 // 8F INT_TO_SHORT vA, vB 463 DF_DA | DF_UB | DF_CORE_A | DF_CORE_B, 464 465 // 90 ADD_INT vAA, vBB, vCC 466 DF_DA | DF_UB | DF_UC | DF_CORE_A | DF_CORE_B | DF_CORE_C, 467 468 // 91 SUB_INT vAA, vBB, vCC 469 DF_DA | DF_UB | DF_UC | DF_CORE_A | DF_CORE_B | DF_CORE_C, 470 471 // 92 MUL_INT vAA, vBB, vCC 472 DF_DA | DF_UB | DF_UC | DF_CORE_A | DF_CORE_B | DF_CORE_C, 473 474 // 93 DIV_INT vAA, vBB, vCC 475 DF_DA | DF_UB | DF_UC | DF_CORE_A | DF_CORE_B | DF_CORE_C, 476 477 // 94 REM_INT vAA, vBB, vCC 478 DF_DA | DF_UB | DF_UC | DF_CORE_A | DF_CORE_B | DF_CORE_C, 479 480 // 95 AND_INT vAA, vBB, vCC 481 DF_DA | DF_UB | DF_UC | DF_CORE_A | DF_CORE_B | DF_CORE_C, 482 483 // 96 OR_INT vAA, vBB, vCC 484 DF_DA | DF_UB | DF_UC | DF_CORE_A | DF_CORE_B | DF_CORE_C, 485 486 // 97 XOR_INT vAA, vBB, vCC 487 DF_DA | DF_UB | DF_UC | DF_CORE_A | DF_CORE_B | DF_CORE_C, 488 489 // 98 SHL_INT vAA, vBB, vCC 490 DF_DA | DF_UB | DF_UC | DF_CORE_A | DF_CORE_B | DF_CORE_C, 491 492 // 99 SHR_INT vAA, vBB, vCC 493 DF_DA | DF_UB | DF_UC | DF_CORE_A | DF_CORE_B | DF_CORE_C, 494 495 // 9A USHR_INT vAA, vBB, vCC 496 DF_DA | DF_UB | DF_UC | DF_CORE_A | DF_CORE_B | DF_CORE_C, 497 498 // 9B ADD_LONG vAA, vBB, vCC 499 DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_UC | DF_C_WIDE | DF_CORE_A | DF_CORE_B | DF_CORE_C, 500 501 // 9C SUB_LONG vAA, vBB, vCC 502 DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_UC | DF_C_WIDE | DF_CORE_A | DF_CORE_B | DF_CORE_C, 503 504 // 9D MUL_LONG vAA, vBB, vCC 505 DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_UC | DF_C_WIDE | DF_CORE_A | DF_CORE_B | DF_CORE_C, 506 507 // 9E DIV_LONG vAA, vBB, vCC 508 DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_UC | DF_C_WIDE | DF_CORE_A | DF_CORE_B | DF_CORE_C, 509 510 // 9F REM_LONG vAA, vBB, vCC 511 DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_UC | DF_C_WIDE | DF_CORE_A | DF_CORE_B | DF_CORE_C, 512 513 // A0 AND_LONG vAA, vBB, vCC 514 DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_UC | DF_C_WIDE | DF_CORE_A | DF_CORE_B | DF_CORE_C, 515 516 // A1 OR_LONG vAA, vBB, vCC 517 DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_UC | DF_C_WIDE | DF_CORE_A | DF_CORE_B | DF_CORE_C, 518 519 // A2 XOR_LONG vAA, vBB, vCC 520 DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_UC | DF_C_WIDE | DF_CORE_A | DF_CORE_B | DF_CORE_C, 521 522 // A3 SHL_LONG vAA, vBB, vCC 523 DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_UC | DF_CORE_A | DF_CORE_B | DF_CORE_C, 524 525 // A4 SHR_LONG vAA, vBB, vCC 526 DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_UC | DF_CORE_A | DF_CORE_B | DF_CORE_C, 527 528 // A5 USHR_LONG vAA, vBB, vCC 529 DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_UC | DF_CORE_A | DF_CORE_B | DF_CORE_C, 530 531 // A6 ADD_FLOAT vAA, vBB, vCC 532 DF_DA | DF_UB | DF_UC | DF_FP_A | DF_FP_B | DF_FP_C, 533 534 // A7 SUB_FLOAT vAA, vBB, vCC 535 DF_DA | DF_UB | DF_UC | DF_FP_A | DF_FP_B | DF_FP_C, 536 537 // A8 MUL_FLOAT vAA, vBB, vCC 538 DF_DA | DF_UB | DF_UC | DF_FP_A | DF_FP_B | DF_FP_C, 539 540 // A9 DIV_FLOAT vAA, vBB, vCC 541 DF_DA | DF_UB | DF_UC | DF_FP_A | DF_FP_B | DF_FP_C, 542 543 // AA REM_FLOAT vAA, vBB, vCC 544 DF_DA | DF_UB | DF_UC | DF_FP_A | DF_FP_B | DF_FP_C, 545 546 // AB ADD_DOUBLE vAA, vBB, vCC 547 DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_UC | DF_C_WIDE | DF_FP_A | DF_FP_B | DF_FP_C, 548 549 // AC SUB_DOUBLE vAA, vBB, vCC 550 DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_UC | DF_C_WIDE | DF_FP_A | DF_FP_B | DF_FP_C, 551 552 // AD MUL_DOUBLE vAA, vBB, vCC 553 DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_UC | DF_C_WIDE | DF_FP_A | DF_FP_B | DF_FP_C, 554 555 // AE DIV_DOUBLE vAA, vBB, vCC 556 DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_UC | DF_C_WIDE | DF_FP_A | DF_FP_B | DF_FP_C, 557 558 // AF REM_DOUBLE vAA, vBB, vCC 559 DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_UC | DF_C_WIDE | DF_FP_A | DF_FP_B | DF_FP_C, 560 561 // B0 ADD_INT_2ADDR vA, vB 562 DF_DA | DF_UA | DF_UB | DF_CORE_A | DF_CORE_B, 563 564 // B1 SUB_INT_2ADDR vA, vB 565 DF_DA | DF_UA | DF_UB | DF_CORE_A | DF_CORE_B, 566 567 // B2 MUL_INT_2ADDR vA, vB 568 DF_DA | DF_UA | DF_UB | DF_CORE_A | DF_CORE_B, 569 570 // B3 DIV_INT_2ADDR vA, vB 571 DF_DA | DF_UA | DF_UB | DF_CORE_A | DF_CORE_B, 572 573 // B4 REM_INT_2ADDR vA, vB 574 DF_DA | DF_UA | DF_UB | DF_CORE_A | DF_CORE_B, 575 576 // B5 AND_INT_2ADDR vA, vB 577 DF_DA | DF_UA | DF_UB | DF_CORE_A | DF_CORE_B, 578 579 // B6 OR_INT_2ADDR vA, vB 580 DF_DA | DF_UA | DF_UB | DF_CORE_A | DF_CORE_B, 581 582 // B7 XOR_INT_2ADDR vA, vB 583 DF_DA | DF_UA | DF_UB | DF_CORE_A | DF_CORE_B, 584 585 // B8 SHL_INT_2ADDR vA, vB 586 DF_DA | DF_UA | DF_UB | DF_CORE_A | DF_CORE_B, 587 588 // B9 SHR_INT_2ADDR vA, vB 589 DF_DA | DF_UA | DF_UB | DF_CORE_A | DF_CORE_B, 590 591 // BA USHR_INT_2ADDR vA, vB 592 DF_DA | DF_UA | DF_UB | DF_CORE_A | DF_CORE_B, 593 594 // BB ADD_LONG_2ADDR vA, vB 595 DF_DA | DF_A_WIDE | DF_UA | DF_UB | DF_B_WIDE | DF_CORE_A | DF_CORE_B, 596 597 // BC SUB_LONG_2ADDR vA, vB 598 DF_DA | DF_A_WIDE | DF_UA | DF_UB | DF_B_WIDE | DF_CORE_A | DF_CORE_B, 599 600 // BD MUL_LONG_2ADDR vA, vB 601 DF_DA | DF_A_WIDE | DF_UA | DF_UB | DF_B_WIDE | DF_CORE_A | DF_CORE_B, 602 603 // BE DIV_LONG_2ADDR vA, vB 604 DF_DA | DF_A_WIDE | DF_UA | DF_UB | DF_B_WIDE | DF_CORE_A | DF_CORE_B, 605 606 // BF REM_LONG_2ADDR vA, vB 607 DF_DA | DF_A_WIDE | DF_UA | DF_UB | DF_B_WIDE | DF_CORE_A | DF_CORE_B, 608 609 // C0 AND_LONG_2ADDR vA, vB 610 DF_DA | DF_A_WIDE | DF_UA | DF_UB | DF_B_WIDE | DF_CORE_A | DF_CORE_B, 611 612 // C1 OR_LONG_2ADDR vA, vB 613 DF_DA | DF_A_WIDE | DF_UA | DF_UB | DF_B_WIDE | DF_CORE_A | DF_CORE_B, 614 615 // C2 XOR_LONG_2ADDR vA, vB 616 DF_DA | DF_A_WIDE | DF_UA | DF_UB | DF_B_WIDE | DF_CORE_A | DF_CORE_B, 617 618 // C3 SHL_LONG_2ADDR vA, vB 619 DF_DA | DF_A_WIDE | DF_UA | DF_UB | DF_CORE_A | DF_CORE_B, 620 621 // C4 SHR_LONG_2ADDR vA, vB 622 DF_DA | DF_A_WIDE | DF_UA | DF_UB | DF_CORE_A | DF_CORE_B, 623 624 // C5 USHR_LONG_2ADDR vA, vB 625 DF_DA | DF_A_WIDE | DF_UA | DF_UB | DF_CORE_A | DF_CORE_B, 626 627 // C6 ADD_FLOAT_2ADDR vA, vB 628 DF_DA | DF_UA | DF_UB | DF_FP_A | DF_FP_B, 629 630 // C7 SUB_FLOAT_2ADDR vA, vB 631 DF_DA | DF_UA | DF_UB | DF_FP_A | DF_FP_B, 632 633 // C8 MUL_FLOAT_2ADDR vA, vB 634 DF_DA | DF_UA | DF_UB | DF_FP_A | DF_FP_B, 635 636 // C9 DIV_FLOAT_2ADDR vA, vB 637 DF_DA | DF_UA | DF_UB | DF_FP_A | DF_FP_B, 638 639 // CA REM_FLOAT_2ADDR vA, vB 640 DF_DA | DF_UA | DF_UB | DF_FP_A | DF_FP_B, 641 642 // CB ADD_DOUBLE_2ADDR vA, vB 643 DF_DA | DF_A_WIDE | DF_UA | DF_UB | DF_B_WIDE | DF_FP_A | DF_FP_B, 644 645 // CC SUB_DOUBLE_2ADDR vA, vB 646 DF_DA | DF_A_WIDE | DF_UA | DF_UB | DF_B_WIDE | DF_FP_A | DF_FP_B, 647 648 // CD MUL_DOUBLE_2ADDR vA, vB 649 DF_DA | DF_A_WIDE | DF_UA | DF_UB | DF_B_WIDE | DF_FP_A | DF_FP_B, 650 651 // CE DIV_DOUBLE_2ADDR vA, vB 652 DF_DA | DF_A_WIDE | DF_UA | DF_UB | DF_B_WIDE | DF_FP_A | DF_FP_B, 653 654 // CF REM_DOUBLE_2ADDR vA, vB 655 DF_DA | DF_A_WIDE | DF_UA | DF_UB | DF_B_WIDE | DF_FP_A | DF_FP_B, 656 657 // D0 ADD_INT_LIT16 vA, vB, #+CCCC 658 DF_DA | DF_UB | DF_CORE_A | DF_CORE_B, 659 660 // D1 RSUB_INT vA, vB, #+CCCC 661 DF_DA | DF_UB | DF_CORE_A | DF_CORE_B, 662 663 // D2 MUL_INT_LIT16 vA, vB, #+CCCC 664 DF_DA | DF_UB | DF_CORE_A | DF_CORE_B, 665 666 // D3 DIV_INT_LIT16 vA, vB, #+CCCC 667 DF_DA | DF_UB | DF_CORE_A | DF_CORE_B, 668 669 // D4 REM_INT_LIT16 vA, vB, #+CCCC 670 DF_DA | DF_UB | DF_CORE_A | DF_CORE_B, 671 672 // D5 AND_INT_LIT16 vA, vB, #+CCCC 673 DF_DA | DF_UB | DF_CORE_A | DF_CORE_B, 674 675 // D6 OR_INT_LIT16 vA, vB, #+CCCC 676 DF_DA | DF_UB | DF_CORE_A | DF_CORE_B, 677 678 // D7 XOR_INT_LIT16 vA, vB, #+CCCC 679 DF_DA | DF_UB | DF_CORE_A | DF_CORE_B, 680 681 // D8 ADD_INT_LIT8 vAA, vBB, #+CC 682 DF_DA | DF_UB | DF_CORE_A | DF_CORE_B, 683 684 // D9 RSUB_INT_LIT8 vAA, vBB, #+CC 685 DF_DA | DF_UB | DF_CORE_A | DF_CORE_B, 686 687 // DA MUL_INT_LIT8 vAA, vBB, #+CC 688 DF_DA | DF_UB | DF_CORE_A | DF_CORE_B, 689 690 // DB DIV_INT_LIT8 vAA, vBB, #+CC 691 DF_DA | DF_UB | DF_CORE_A | DF_CORE_B, 692 693 // DC REM_INT_LIT8 vAA, vBB, #+CC 694 DF_DA | DF_UB | DF_CORE_A | DF_CORE_B, 695 696 // DD AND_INT_LIT8 vAA, vBB, #+CC 697 DF_DA | DF_UB | DF_CORE_A | DF_CORE_B, 698 699 // DE OR_INT_LIT8 vAA, vBB, #+CC 700 DF_DA | DF_UB | DF_CORE_A | DF_CORE_B, 701 702 // DF XOR_INT_LIT8 vAA, vBB, #+CC 703 DF_DA | DF_UB | DF_CORE_A | DF_CORE_B, 704 705 // E0 SHL_INT_LIT8 vAA, vBB, #+CC 706 DF_DA | DF_UB | DF_CORE_A | DF_CORE_B, 707 708 // E1 SHR_INT_LIT8 vAA, vBB, #+CC 709 DF_DA | DF_UB | DF_CORE_A | DF_CORE_B, 710 711 // E2 USHR_INT_LIT8 vAA, vBB, #+CC 712 DF_DA | DF_UB | DF_CORE_A | DF_CORE_B, 713 714 // E3 IGET_VOLATILE 715 DF_DA | DF_UB | DF_NULL_CHK_0 | DF_REF_B | DF_IFIELD | DF_LVN, 716 717 // E4 IPUT_VOLATILE 718 DF_UA | DF_UB | DF_NULL_CHK_1 | DF_REF_B | DF_IFIELD | DF_LVN, 719 720 // E5 SGET_VOLATILE 721 DF_DA | DF_SFIELD | DF_UMS, 722 723 // E6 SPUT_VOLATILE 724 DF_UA | DF_SFIELD | DF_UMS, 725 726 // E7 IGET_OBJECT_VOLATILE 727 DF_DA | DF_UB | DF_NULL_CHK_0 | DF_REF_A | DF_REF_B | DF_IFIELD | DF_LVN, 728 729 // E8 IGET_WIDE_VOLATILE 730 DF_DA | DF_A_WIDE | DF_UB | DF_NULL_CHK_0 | DF_REF_B | DF_IFIELD | DF_LVN, 731 732 // E9 IPUT_WIDE_VOLATILE 733 DF_UA | DF_A_WIDE | DF_UB | DF_NULL_CHK_2 | DF_REF_B | DF_IFIELD | DF_LVN, 734 735 // EA SGET_WIDE_VOLATILE 736 DF_DA | DF_A_WIDE | DF_SFIELD | DF_UMS, 737 738 // EB SPUT_WIDE_VOLATILE 739 DF_UA | DF_A_WIDE | DF_SFIELD | DF_UMS, 740 741 // EC BREAKPOINT 742 DF_NOP, 743 744 // ED THROW_VERIFICATION_ERROR 745 DF_NOP | DF_UMS, 746 747 // EE EXECUTE_INLINE 748 DF_FORMAT_35C, 749 750 // EF EXECUTE_INLINE_RANGE 751 DF_FORMAT_3RC, 752 753 // F0 INVOKE_OBJECT_INIT_RANGE 754 DF_NOP | DF_NULL_CHK_0, 755 756 // F1 RETURN_VOID_BARRIER 757 DF_NOP, 758 759 // F2 IGET_QUICK 760 DF_DA | DF_UB | DF_NULL_CHK_0 | DF_IFIELD | DF_LVN, 761 762 // F3 IGET_WIDE_QUICK 763 DF_DA | DF_A_WIDE | DF_UB | DF_NULL_CHK_0 | DF_IFIELD | DF_LVN, 764 765 // F4 IGET_OBJECT_QUICK 766 DF_DA | DF_UB | DF_NULL_CHK_0 | DF_IFIELD | DF_LVN, 767 768 // F5 IPUT_QUICK 769 DF_UA | DF_UB | DF_NULL_CHK_1 | DF_IFIELD | DF_LVN, 770 771 // F6 IPUT_WIDE_QUICK 772 DF_UA | DF_A_WIDE | DF_UB | DF_NULL_CHK_2 | DF_IFIELD | DF_LVN, 773 774 // F7 IPUT_OBJECT_QUICK 775 DF_UA | DF_UB | DF_NULL_CHK_1 | DF_IFIELD | DF_LVN, 776 777 // F8 INVOKE_VIRTUAL_QUICK 778 DF_FORMAT_35C | DF_NULL_CHK_OUT0 | DF_UMS, 779 780 // F9 INVOKE_VIRTUAL_QUICK_RANGE 781 DF_FORMAT_3RC | DF_NULL_CHK_OUT0 | DF_UMS, 782 783 // FA INVOKE_SUPER_QUICK 784 DF_FORMAT_35C | DF_NULL_CHK_OUT0 | DF_UMS, 785 786 // FB INVOKE_SUPER_QUICK_RANGE 787 DF_FORMAT_3RC | DF_NULL_CHK_OUT0 | DF_UMS, 788 789 // FC IPUT_OBJECT_VOLATILE 790 DF_UA | DF_UB | DF_NULL_CHK_1 | DF_REF_A | DF_REF_B | DF_IFIELD | DF_LVN, 791 792 // FD SGET_OBJECT_VOLATILE 793 DF_DA | DF_REF_A | DF_SFIELD | DF_UMS, 794 795 // FE SPUT_OBJECT_VOLATILE 796 DF_UA | DF_REF_A | DF_SFIELD | DF_UMS, 797 798 // FF UNUSED_FF 799 DF_NOP, 800 801 // Beginning of extended MIR opcodes 802 // 100 MIR_PHI 803 DF_DA | DF_NULL_TRANSFER_N, 804 805 // 101 MIR_COPY 806 DF_DA | DF_UB | DF_IS_MOVE, 807 808 // 102 MIR_FUSED_CMPL_FLOAT 809 DF_UA | DF_UB | DF_FP_A | DF_FP_B, 810 811 // 103 MIR_FUSED_CMPG_FLOAT 812 DF_UA | DF_UB | DF_FP_A | DF_FP_B, 813 814 // 104 MIR_FUSED_CMPL_DOUBLE 815 DF_UA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_FP_A | DF_FP_B, 816 817 // 105 MIR_FUSED_CMPG_DOUBLE 818 DF_UA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_FP_A | DF_FP_B, 819 820 // 106 MIR_FUSED_CMP_LONG 821 DF_UA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_CORE_A | DF_CORE_B, 822 823 // 107 MIR_NOP 824 DF_NOP, 825 826 // 108 MIR_NULL_CHECK 827 0, 828 829 // 109 MIR_RANGE_CHECK 830 0, 831 832 // 110 MIR_DIV_ZERO_CHECK 833 0, 834 835 // 111 MIR_CHECK 836 0, 837 838 // 112 MIR_CHECKPART2 839 0, 840 841 // 113 MIR_SELECT 842 DF_DA | DF_UB, 843 844 // 114 MirOpConstVector 845 DF_DA, 846 847 // 115 MirOpMoveVector 848 0, 849 850 // 116 MirOpPackedMultiply 851 0, 852 853 // 117 MirOpPackedAddition 854 0, 855 856 // 118 MirOpPackedSubtract 857 0, 858 859 // 119 MirOpPackedShiftLeft 860 0, 861 862 // 120 MirOpPackedSignedShiftRight 863 0, 864 865 // 121 MirOpPackedUnsignedShiftRight 866 0, 867 868 // 122 MirOpPackedAnd 869 0, 870 871 // 123 MirOpPackedOr 872 0, 873 874 // 124 MirOpPackedXor 875 0, 876 877 // 125 MirOpPackedAddReduce 878 DF_DA | DF_UA, 879 880 // 126 MirOpPackedReduce 881 DF_DA, 882 883 // 127 MirOpPackedSet 884 DF_UB, 885 886 // 128 MirOpReserveVectorRegisters 887 0, 888 889 // 129 MirOpReturnVectorRegisters 890 0, 891 }; 892 893 /* Return the base virtual register for a SSA name */ SRegToVReg(int ssa_reg) const894 int MIRGraph::SRegToVReg(int ssa_reg) const { 895 return ssa_base_vregs_->Get(ssa_reg); 896 } 897 898 /* Any register that is used before being defined is considered live-in */ HandleLiveInUse(ArenaBitVector * use_v,ArenaBitVector * def_v,ArenaBitVector * live_in_v,int dalvik_reg_id)899 void MIRGraph::HandleLiveInUse(ArenaBitVector* use_v, ArenaBitVector* def_v, 900 ArenaBitVector* live_in_v, int dalvik_reg_id) { 901 use_v->SetBit(dalvik_reg_id); 902 if (!def_v->IsBitSet(dalvik_reg_id)) { 903 live_in_v->SetBit(dalvik_reg_id); 904 } 905 } 906 907 /* Mark a reg as being defined */ HandleDef(ArenaBitVector * def_v,int dalvik_reg_id)908 void MIRGraph::HandleDef(ArenaBitVector* def_v, int dalvik_reg_id) { 909 def_v->SetBit(dalvik_reg_id); 910 } 911 HandleExtended(ArenaBitVector * use_v,ArenaBitVector * def_v,ArenaBitVector * live_in_v,const MIR::DecodedInstruction & d_insn)912 void MIRGraph::HandleExtended(ArenaBitVector* use_v, ArenaBitVector* def_v, 913 ArenaBitVector* live_in_v, 914 const MIR::DecodedInstruction& d_insn) { 915 switch (static_cast<int>(d_insn.opcode)) { 916 default: 917 LOG(ERROR) << "Unexpected Extended Opcode " << d_insn.opcode; 918 break; 919 } 920 } 921 922 /* 923 * Find out live-in variables for natural loops. Variables that are live-in in 924 * the main loop body are considered to be defined in the entry block. 925 */ FindLocalLiveIn(BasicBlock * bb)926 bool MIRGraph::FindLocalLiveIn(BasicBlock* bb) { 927 MIR* mir; 928 ArenaBitVector *use_v, *def_v, *live_in_v; 929 930 if (bb->data_flow_info == NULL) return false; 931 932 use_v = bb->data_flow_info->use_v = 933 new (arena_) ArenaBitVector(arena_, cu_->num_dalvik_registers, false, kBitMapUse); 934 def_v = bb->data_flow_info->def_v = 935 new (arena_) ArenaBitVector(arena_, cu_->num_dalvik_registers, false, kBitMapDef); 936 live_in_v = bb->data_flow_info->live_in_v = 937 new (arena_) ArenaBitVector(arena_, cu_->num_dalvik_registers, false, kBitMapLiveIn); 938 939 for (mir = bb->first_mir_insn; mir != NULL; mir = mir->next) { 940 uint64_t df_attributes = GetDataFlowAttributes(mir); 941 MIR::DecodedInstruction* d_insn = &mir->dalvikInsn; 942 943 if (df_attributes & DF_HAS_USES) { 944 if (df_attributes & DF_UA) { 945 HandleLiveInUse(use_v, def_v, live_in_v, d_insn->vA); 946 if (df_attributes & DF_A_WIDE) { 947 HandleLiveInUse(use_v, def_v, live_in_v, d_insn->vA+1); 948 } 949 } 950 if (df_attributes & DF_UB) { 951 HandleLiveInUse(use_v, def_v, live_in_v, d_insn->vB); 952 if (df_attributes & DF_B_WIDE) { 953 HandleLiveInUse(use_v, def_v, live_in_v, d_insn->vB+1); 954 } 955 } 956 if (df_attributes & DF_UC) { 957 HandleLiveInUse(use_v, def_v, live_in_v, d_insn->vC); 958 if (df_attributes & DF_C_WIDE) { 959 HandleLiveInUse(use_v, def_v, live_in_v, d_insn->vC+1); 960 } 961 } 962 } 963 if (df_attributes & DF_FORMAT_35C) { 964 for (unsigned int i = 0; i < d_insn->vA; i++) { 965 HandleLiveInUse(use_v, def_v, live_in_v, d_insn->arg[i]); 966 } 967 } 968 if (df_attributes & DF_FORMAT_3RC) { 969 for (unsigned int i = 0; i < d_insn->vA; i++) { 970 HandleLiveInUse(use_v, def_v, live_in_v, d_insn->vC+i); 971 } 972 } 973 if (df_attributes & DF_HAS_DEFS) { 974 HandleDef(def_v, d_insn->vA); 975 if (df_attributes & DF_A_WIDE) { 976 HandleDef(def_v, d_insn->vA+1); 977 } 978 } 979 if (df_attributes & DF_FORMAT_EXTENDED) { 980 HandleExtended(use_v, def_v, live_in_v, mir->dalvikInsn); 981 } 982 } 983 return true; 984 } 985 AddNewSReg(int v_reg)986 int MIRGraph::AddNewSReg(int v_reg) { 987 // Compiler temps always have a subscript of 0 988 int subscript = (v_reg < 0) ? 0 : ++ssa_last_defs_[v_reg]; 989 uint32_t ssa_reg = GetNumSSARegs(); 990 SetNumSSARegs(ssa_reg + 1); 991 ssa_base_vregs_->Insert(v_reg); 992 ssa_subscripts_->Insert(subscript); 993 DCHECK_EQ(ssa_base_vregs_->Size(), ssa_subscripts_->Size()); 994 // If we are expanding very late, update use counts too. 995 if (ssa_reg > 0 && use_counts_.Size() == ssa_reg) { 996 // Need to expand the counts. 997 use_counts_.Insert(0); 998 raw_use_counts_.Insert(0); 999 } 1000 return ssa_reg; 1001 } 1002 1003 /* Find out the latest SSA register for a given Dalvik register */ HandleSSAUse(int * uses,int dalvik_reg,int reg_index)1004 void MIRGraph::HandleSSAUse(int* uses, int dalvik_reg, int reg_index) { 1005 DCHECK((dalvik_reg >= 0) && (dalvik_reg < cu_->num_dalvik_registers)); 1006 uses[reg_index] = vreg_to_ssa_map_[dalvik_reg]; 1007 } 1008 1009 /* Setup a new SSA register for a given Dalvik register */ HandleSSADef(int * defs,int dalvik_reg,int reg_index)1010 void MIRGraph::HandleSSADef(int* defs, int dalvik_reg, int reg_index) { 1011 DCHECK((dalvik_reg >= 0) && (dalvik_reg < cu_->num_dalvik_registers)); 1012 int ssa_reg = AddNewSReg(dalvik_reg); 1013 vreg_to_ssa_map_[dalvik_reg] = ssa_reg; 1014 defs[reg_index] = ssa_reg; 1015 } 1016 AllocateSSAUseData(MIR * mir,int num_uses)1017 void MIRGraph::AllocateSSAUseData(MIR *mir, int num_uses) { 1018 mir->ssa_rep->num_uses = num_uses; 1019 1020 if (mir->ssa_rep->num_uses_allocated < num_uses) { 1021 mir->ssa_rep->uses = static_cast<int*>(arena_->Alloc(sizeof(int) * num_uses, kArenaAllocDFInfo)); 1022 // NOTE: will be filled in during type & size inference pass 1023 mir->ssa_rep->fp_use = static_cast<bool*>(arena_->Alloc(sizeof(bool) * num_uses, kArenaAllocDFInfo)); 1024 } 1025 } 1026 AllocateSSADefData(MIR * mir,int num_defs)1027 void MIRGraph::AllocateSSADefData(MIR *mir, int num_defs) { 1028 mir->ssa_rep->num_defs = num_defs; 1029 1030 if (mir->ssa_rep->num_defs_allocated < num_defs) { 1031 mir->ssa_rep->defs = static_cast<int*>(arena_->Alloc(sizeof(int) * num_defs, 1032 kArenaAllocDFInfo)); 1033 mir->ssa_rep->fp_def = static_cast<bool*>(arena_->Alloc(sizeof(bool) * num_defs, 1034 kArenaAllocDFInfo)); 1035 } 1036 } 1037 1038 /* Look up new SSA names for format_35c instructions */ DataFlowSSAFormat35C(MIR * mir)1039 void MIRGraph::DataFlowSSAFormat35C(MIR* mir) { 1040 MIR::DecodedInstruction* d_insn = &mir->dalvikInsn; 1041 int num_uses = d_insn->vA; 1042 int i; 1043 1044 AllocateSSAUseData(mir, num_uses); 1045 1046 for (i = 0; i < num_uses; i++) { 1047 HandleSSAUse(mir->ssa_rep->uses, d_insn->arg[i], i); 1048 } 1049 } 1050 1051 /* Look up new SSA names for format_3rc instructions */ DataFlowSSAFormat3RC(MIR * mir)1052 void MIRGraph::DataFlowSSAFormat3RC(MIR* mir) { 1053 MIR::DecodedInstruction* d_insn = &mir->dalvikInsn; 1054 int num_uses = d_insn->vA; 1055 int i; 1056 1057 AllocateSSAUseData(mir, num_uses); 1058 1059 for (i = 0; i < num_uses; i++) { 1060 HandleSSAUse(mir->ssa_rep->uses, d_insn->vC+i, i); 1061 } 1062 } 1063 DataFlowSSAFormatExtended(MIR * mir)1064 void MIRGraph::DataFlowSSAFormatExtended(MIR* mir) { 1065 switch (static_cast<int>(mir->dalvikInsn.opcode)) { 1066 default: 1067 LOG(ERROR) << "Missing case for extended MIR: " << mir->dalvikInsn.opcode; 1068 break; 1069 } 1070 } 1071 1072 /* Entry function to convert a block into SSA representation */ DoSSAConversion(BasicBlock * bb)1073 bool MIRGraph::DoSSAConversion(BasicBlock* bb) { 1074 MIR* mir; 1075 1076 if (bb->data_flow_info == NULL) return false; 1077 1078 for (mir = bb->first_mir_insn; mir != NULL; mir = mir->next) { 1079 mir->ssa_rep = 1080 static_cast<struct SSARepresentation *>(arena_->Alloc(sizeof(SSARepresentation), 1081 kArenaAllocDFInfo)); 1082 memset(mir->ssa_rep, 0, sizeof(*mir->ssa_rep)); 1083 1084 uint64_t df_attributes = GetDataFlowAttributes(mir); 1085 1086 // If not a pseudo-op, note non-leaf or can throw 1087 if (!MIR::DecodedInstruction::IsPseudoMirOp(mir->dalvikInsn.opcode)) { 1088 int flags = Instruction::FlagsOf(mir->dalvikInsn.opcode); 1089 1090 if ((flags & Instruction::kInvoke) != 0 && (mir->optimization_flags & MIR_INLINED) == 0) { 1091 attributes_ &= ~METHOD_IS_LEAF; 1092 } 1093 } 1094 1095 int num_uses = 0; 1096 1097 if (df_attributes & DF_FORMAT_35C) { 1098 DataFlowSSAFormat35C(mir); 1099 continue; 1100 } 1101 1102 if (df_attributes & DF_FORMAT_3RC) { 1103 DataFlowSSAFormat3RC(mir); 1104 continue; 1105 } 1106 1107 if (df_attributes & DF_FORMAT_EXTENDED) { 1108 DataFlowSSAFormatExtended(mir); 1109 continue; 1110 } 1111 1112 if (df_attributes & DF_HAS_USES) { 1113 if (df_attributes & DF_UA) { 1114 num_uses++; 1115 if (df_attributes & DF_A_WIDE) { 1116 num_uses++; 1117 } 1118 } 1119 if (df_attributes & DF_UB) { 1120 num_uses++; 1121 if (df_attributes & DF_B_WIDE) { 1122 num_uses++; 1123 } 1124 } 1125 if (df_attributes & DF_UC) { 1126 num_uses++; 1127 if (df_attributes & DF_C_WIDE) { 1128 num_uses++; 1129 } 1130 } 1131 } 1132 1133 AllocateSSAUseData(mir, num_uses); 1134 1135 int num_defs = 0; 1136 1137 if (df_attributes & DF_HAS_DEFS) { 1138 num_defs++; 1139 if (df_attributes & DF_A_WIDE) { 1140 num_defs++; 1141 } 1142 } 1143 1144 AllocateSSADefData(mir, num_defs); 1145 1146 MIR::DecodedInstruction* d_insn = &mir->dalvikInsn; 1147 1148 if (df_attributes & DF_HAS_USES) { 1149 num_uses = 0; 1150 if (df_attributes & DF_UA) { 1151 mir->ssa_rep->fp_use[num_uses] = df_attributes & DF_FP_A; 1152 HandleSSAUse(mir->ssa_rep->uses, d_insn->vA, num_uses++); 1153 if (df_attributes & DF_A_WIDE) { 1154 mir->ssa_rep->fp_use[num_uses] = df_attributes & DF_FP_A; 1155 HandleSSAUse(mir->ssa_rep->uses, d_insn->vA+1, num_uses++); 1156 } 1157 } 1158 if (df_attributes & DF_UB) { 1159 mir->ssa_rep->fp_use[num_uses] = df_attributes & DF_FP_B; 1160 HandleSSAUse(mir->ssa_rep->uses, d_insn->vB, num_uses++); 1161 if (df_attributes & DF_B_WIDE) { 1162 mir->ssa_rep->fp_use[num_uses] = df_attributes & DF_FP_B; 1163 HandleSSAUse(mir->ssa_rep->uses, d_insn->vB+1, num_uses++); 1164 } 1165 } 1166 if (df_attributes & DF_UC) { 1167 mir->ssa_rep->fp_use[num_uses] = df_attributes & DF_FP_C; 1168 HandleSSAUse(mir->ssa_rep->uses, d_insn->vC, num_uses++); 1169 if (df_attributes & DF_C_WIDE) { 1170 mir->ssa_rep->fp_use[num_uses] = df_attributes & DF_FP_C; 1171 HandleSSAUse(mir->ssa_rep->uses, d_insn->vC+1, num_uses++); 1172 } 1173 } 1174 } 1175 if (df_attributes & DF_HAS_DEFS) { 1176 mir->ssa_rep->fp_def[0] = df_attributes & DF_FP_A; 1177 HandleSSADef(mir->ssa_rep->defs, d_insn->vA, 0); 1178 if (df_attributes & DF_A_WIDE) { 1179 mir->ssa_rep->fp_def[1] = df_attributes & DF_FP_A; 1180 HandleSSADef(mir->ssa_rep->defs, d_insn->vA+1, 1); 1181 } 1182 } 1183 } 1184 1185 /* 1186 * Take a snapshot of Dalvik->SSA mapping at the end of each block. The 1187 * input to PHI nodes can be derived from the snapshot of all 1188 * predecessor blocks. 1189 */ 1190 bb->data_flow_info->vreg_to_ssa_map_exit = 1191 static_cast<int*>(arena_->Alloc(sizeof(int) * cu_->num_dalvik_registers, 1192 kArenaAllocDFInfo)); 1193 1194 memcpy(bb->data_flow_info->vreg_to_ssa_map_exit, vreg_to_ssa_map_, 1195 sizeof(int) * cu_->num_dalvik_registers); 1196 return true; 1197 } 1198 1199 /* Setup the basic data structures for SSA conversion */ CompilerInitializeSSAConversion()1200 void MIRGraph::CompilerInitializeSSAConversion() { 1201 size_t num_dalvik_reg = cu_->num_dalvik_registers; 1202 1203 ssa_base_vregs_ = new (arena_) GrowableArray<int>(arena_, num_dalvik_reg + GetDefCount() + 128, 1204 kGrowableArraySSAtoDalvikMap); 1205 ssa_subscripts_ = new (arena_) GrowableArray<int>(arena_, num_dalvik_reg + GetDefCount() + 128, 1206 kGrowableArraySSAtoDalvikMap); 1207 /* 1208 * Initial number of SSA registers is equal to the number of Dalvik 1209 * registers. 1210 */ 1211 SetNumSSARegs(num_dalvik_reg); 1212 1213 /* 1214 * Initialize the SSA2Dalvik map list. For the first num_dalvik_reg elements, 1215 * the subscript is 0 so we use the ENCODE_REG_SUB macro to encode the value 1216 * into "(0 << 16) | i" 1217 */ 1218 for (unsigned int i = 0; i < num_dalvik_reg; i++) { 1219 ssa_base_vregs_->Insert(i); 1220 ssa_subscripts_->Insert(0); 1221 } 1222 1223 /* 1224 * Initialize the DalvikToSSAMap map. There is one entry for each 1225 * Dalvik register, and the SSA names for those are the same. 1226 */ 1227 vreg_to_ssa_map_ = 1228 static_cast<int*>(arena_->Alloc(sizeof(int) * num_dalvik_reg, 1229 kArenaAllocDFInfo)); 1230 /* Keep track of the higest def for each dalvik reg */ 1231 ssa_last_defs_ = 1232 static_cast<int*>(arena_->Alloc(sizeof(int) * num_dalvik_reg, 1233 kArenaAllocDFInfo)); 1234 1235 for (unsigned int i = 0; i < num_dalvik_reg; i++) { 1236 vreg_to_ssa_map_[i] = i; 1237 ssa_last_defs_[i] = 0; 1238 } 1239 1240 // Create a compiler temporary for Method*. This is done after SSA initialization. 1241 GetNewCompilerTemp(kCompilerTempSpecialMethodPtr, false); 1242 1243 /* 1244 * Allocate the BasicBlockDataFlow structure for the entry and code blocks 1245 */ 1246 GrowableArray<BasicBlock*>::Iterator iterator(&block_list_); 1247 1248 while (true) { 1249 BasicBlock* bb = iterator.Next(); 1250 if (bb == NULL) break; 1251 if (bb->hidden == true) continue; 1252 if (bb->block_type == kDalvikByteCode || 1253 bb->block_type == kEntryBlock || 1254 bb->block_type == kExitBlock) { 1255 bb->data_flow_info = 1256 static_cast<BasicBlockDataFlow*>(arena_->Alloc(sizeof(BasicBlockDataFlow), 1257 kArenaAllocDFInfo)); 1258 } 1259 } 1260 } 1261 1262 /* 1263 * This function will make a best guess at whether the invoke will 1264 * end up using Method*. It isn't critical to get it exactly right, 1265 * and attempting to do would involve more complexity than it's 1266 * worth. 1267 */ InvokeUsesMethodStar(MIR * mir)1268 bool MIRGraph::InvokeUsesMethodStar(MIR* mir) { 1269 InvokeType type; 1270 Instruction::Code opcode = mir->dalvikInsn.opcode; 1271 switch (opcode) { 1272 case Instruction::INVOKE_STATIC: 1273 case Instruction::INVOKE_STATIC_RANGE: 1274 type = kStatic; 1275 break; 1276 case Instruction::INVOKE_DIRECT: 1277 case Instruction::INVOKE_DIRECT_RANGE: 1278 type = kDirect; 1279 break; 1280 case Instruction::INVOKE_VIRTUAL: 1281 case Instruction::INVOKE_VIRTUAL_RANGE: 1282 type = kVirtual; 1283 break; 1284 case Instruction::INVOKE_INTERFACE: 1285 case Instruction::INVOKE_INTERFACE_RANGE: 1286 return false; 1287 case Instruction::INVOKE_SUPER_RANGE: 1288 case Instruction::INVOKE_SUPER: 1289 type = kSuper; 1290 break; 1291 default: 1292 LOG(WARNING) << "Unexpected invoke op: " << opcode; 1293 return false; 1294 } 1295 DexCompilationUnit m_unit(cu_); 1296 MethodReference target_method(cu_->dex_file, mir->dalvikInsn.vB); 1297 int vtable_idx; 1298 uintptr_t direct_code; 1299 uintptr_t direct_method; 1300 uint32_t current_offset = static_cast<uint32_t>(current_offset_); 1301 bool fast_path = 1302 cu_->compiler_driver->ComputeInvokeInfo(&m_unit, current_offset, 1303 false, true, 1304 &type, &target_method, 1305 &vtable_idx, 1306 &direct_code, &direct_method) && 1307 !(cu_->enable_debug & (1 << kDebugSlowInvokePath)); 1308 return (((type == kDirect) || (type == kStatic)) && 1309 fast_path && ((direct_code == 0) || (direct_method == 0))); 1310 } 1311 1312 /* 1313 * Count uses, weighting by loop nesting depth. This code only 1314 * counts explicitly used s_regs. A later phase will add implicit 1315 * counts for things such as Method*, null-checked references, etc. 1316 */ CountUses(struct BasicBlock * bb)1317 void MIRGraph::CountUses(struct BasicBlock* bb) { 1318 if (bb->block_type != kDalvikByteCode) { 1319 return; 1320 } 1321 // Each level of nesting adds *100 to count, up to 3 levels deep. 1322 uint32_t depth = std::min(3U, static_cast<uint32_t>(bb->nesting_depth)); 1323 uint32_t weight = std::max(1U, depth * 100); 1324 for (MIR* mir = bb->first_mir_insn; (mir != NULL); mir = mir->next) { 1325 if (mir->ssa_rep == NULL) { 1326 continue; 1327 } 1328 for (int i = 0; i < mir->ssa_rep->num_uses; i++) { 1329 int s_reg = mir->ssa_rep->uses[i]; 1330 raw_use_counts_.Increment(s_reg); 1331 use_counts_.Put(s_reg, use_counts_.Get(s_reg) + weight); 1332 } 1333 if (!(cu_->disable_opt & (1 << kPromoteCompilerTemps))) { 1334 uint64_t df_attributes = GetDataFlowAttributes(mir); 1335 // Implicit use of Method* ? */ 1336 if (df_attributes & DF_UMS) { 1337 /* 1338 * Some invokes will not use Method* - need to perform test similar 1339 * to that found in GenInvoke() to decide whether to count refs 1340 * for Method* on invoke-class opcodes. This is a relatively expensive 1341 * operation, so should only be done once. 1342 * TODO: refactor InvokeUsesMethodStar() to perform check at parse time, 1343 * and save results for both here and GenInvoke. For now, go ahead 1344 * and assume all invokes use method*. 1345 */ 1346 raw_use_counts_.Increment(method_sreg_); 1347 use_counts_.Put(method_sreg_, use_counts_.Get(method_sreg_) + weight); 1348 } 1349 } 1350 } 1351 } 1352 1353 /* Verify if all the successor is connected with all the claimed predecessors */ VerifyPredInfo(BasicBlock * bb)1354 bool MIRGraph::VerifyPredInfo(BasicBlock* bb) { 1355 GrowableArray<BasicBlockId>::Iterator iter(bb->predecessors); 1356 1357 while (true) { 1358 BasicBlock* pred_bb = GetBasicBlock(iter.Next()); 1359 if (!pred_bb) break; 1360 bool found = false; 1361 if (pred_bb->taken == bb->id) { 1362 found = true; 1363 } else if (pred_bb->fall_through == bb->id) { 1364 found = true; 1365 } else if (pred_bb->successor_block_list_type != kNotUsed) { 1366 GrowableArray<SuccessorBlockInfo*>::Iterator iterator(pred_bb->successor_blocks); 1367 while (true) { 1368 SuccessorBlockInfo *successor_block_info = iterator.Next(); 1369 if (successor_block_info == NULL) break; 1370 BasicBlockId succ_bb = successor_block_info->block; 1371 if (succ_bb == bb->id) { 1372 found = true; 1373 break; 1374 } 1375 } 1376 } 1377 if (found == false) { 1378 char block_name1[BLOCK_NAME_LEN], block_name2[BLOCK_NAME_LEN]; 1379 GetBlockName(bb, block_name1); 1380 GetBlockName(pred_bb, block_name2); 1381 DumpCFG("/sdcard/cfg/", false); 1382 LOG(FATAL) << "Successor " << block_name1 << "not found from " 1383 << block_name2; 1384 } 1385 } 1386 return true; 1387 } 1388 VerifyDataflow()1389 void MIRGraph::VerifyDataflow() { 1390 /* Verify if all blocks are connected as claimed */ 1391 AllNodesIterator iter(this); 1392 for (BasicBlock* bb = iter.Next(); bb != NULL; bb = iter.Next()) { 1393 VerifyPredInfo(bb); 1394 } 1395 } 1396 1397 } // namespace art 1398