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 int 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, 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, 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, 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, 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, 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, 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, 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, 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, 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, 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, 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, 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, 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, 278 279 // 52 IGET vA, vB, field@CCCC 280 DF_DA | DF_UB | DF_NULL_CHK_0 | DF_REF_B, 281 282 // 53 IGET_WIDE vA, vB, field@CCCC 283 DF_DA | DF_A_WIDE | DF_UB | DF_NULL_CHK_0 | DF_REF_B, 284 285 // 54 IGET_OBJECT vA, vB, field@CCCC 286 DF_DA | DF_UB | DF_NULL_CHK_0 | DF_REF_A | DF_REF_B, 287 288 // 55 IGET_BOOLEAN vA, vB, field@CCCC 289 DF_DA | DF_UB | DF_NULL_CHK_0 | DF_REF_B, 290 291 // 56 IGET_BYTE vA, vB, field@CCCC 292 DF_DA | DF_UB | DF_NULL_CHK_0 | DF_REF_B, 293 294 // 57 IGET_CHAR vA, vB, field@CCCC 295 DF_DA | DF_UB | DF_NULL_CHK_0 | DF_REF_B, 296 297 // 58 IGET_SHORT vA, vB, field@CCCC 298 DF_DA | DF_UB | DF_NULL_CHK_0 | DF_REF_B, 299 300 // 59 IPUT vA, vB, field@CCCC 301 DF_UA | DF_UB | DF_NULL_CHK_1 | DF_REF_B, 302 303 // 5A IPUT_WIDE vA, vB, field@CCCC 304 DF_UA | DF_A_WIDE | DF_UB | DF_NULL_CHK_2 | DF_REF_B, 305 306 // 5B IPUT_OBJECT vA, vB, field@CCCC 307 DF_UA | DF_UB | DF_NULL_CHK_1 | DF_REF_A | DF_REF_B, 308 309 // 5C IPUT_BOOLEAN vA, vB, field@CCCC 310 DF_UA | DF_UB | DF_NULL_CHK_1 | DF_REF_B, 311 312 // 5D IPUT_BYTE vA, vB, field@CCCC 313 DF_UA | DF_UB | DF_NULL_CHK_1 | DF_REF_B, 314 315 // 5E IPUT_CHAR vA, vB, field@CCCC 316 DF_UA | DF_UB | DF_NULL_CHK_1 | DF_REF_B, 317 318 // 5F IPUT_SHORT vA, vB, field@CCCC 319 DF_UA | DF_UB | DF_NULL_CHK_1 | DF_REF_B, 320 321 // 60 SGET vAA, field@BBBB 322 DF_DA | DF_UMS, 323 324 // 61 SGET_WIDE vAA, field@BBBB 325 DF_DA | DF_A_WIDE | DF_UMS, 326 327 // 62 SGET_OBJECT vAA, field@BBBB 328 DF_DA | DF_REF_A | DF_UMS, 329 330 // 63 SGET_BOOLEAN vAA, field@BBBB 331 DF_DA | DF_UMS, 332 333 // 64 SGET_BYTE vAA, field@BBBB 334 DF_DA | DF_UMS, 335 336 // 65 SGET_CHAR vAA, field@BBBB 337 DF_DA | DF_UMS, 338 339 // 66 SGET_SHORT vAA, field@BBBB 340 DF_DA | DF_UMS, 341 342 // 67 SPUT vAA, field@BBBB 343 DF_UA | DF_UMS, 344 345 // 68 SPUT_WIDE vAA, field@BBBB 346 DF_UA | DF_A_WIDE | DF_UMS, 347 348 // 69 SPUT_OBJECT vAA, field@BBBB 349 DF_UA | DF_REF_A | DF_UMS, 350 351 // 6A SPUT_BOOLEAN vAA, field@BBBB 352 DF_UA | DF_UMS, 353 354 // 6B SPUT_BYTE vAA, field@BBBB 355 DF_UA | DF_UMS, 356 357 // 6C SPUT_CHAR vAA, field@BBBB 358 DF_UA | DF_UMS, 359 360 // 6D SPUT_SHORT vAA, field@BBBB 361 DF_UA | 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, 716 717 // E4 IPUT_VOLATILE 718 DF_UA | DF_UB | DF_NULL_CHK_1 | DF_REF_B, 719 720 // E5 SGET_VOLATILE 721 DF_DA | DF_UMS, 722 723 // E6 SPUT_VOLATILE 724 DF_UA | DF_UMS, 725 726 // E7 IGET_OBJECT_VOLATILE 727 DF_DA | DF_UB | DF_NULL_CHK_0 | DF_REF_A | DF_REF_B, 728 729 // E8 IGET_WIDE_VOLATILE 730 DF_DA | DF_A_WIDE | DF_UB | DF_NULL_CHK_0 | DF_REF_B, 731 732 // E9 IPUT_WIDE_VOLATILE 733 DF_UA | DF_A_WIDE | DF_UB | DF_NULL_CHK_2 | DF_REF_B, 734 735 // EA SGET_WIDE_VOLATILE 736 DF_DA | DF_A_WIDE | DF_UMS, 737 738 // EB SPUT_WIDE_VOLATILE 739 DF_UA | DF_A_WIDE | 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, 761 762 // F3 IGET_WIDE_QUICK 763 DF_DA | DF_A_WIDE | DF_UB | DF_NULL_CHK_0, 764 765 // F4 IGET_OBJECT_QUICK 766 DF_DA | DF_UB | DF_NULL_CHK_0, 767 768 // F5 IPUT_QUICK 769 DF_UA | DF_UB | DF_NULL_CHK_1, 770 771 // F6 IPUT_WIDE_QUICK 772 DF_UA | DF_A_WIDE | DF_UB | DF_NULL_CHK_2, 773 774 // F7 IPUT_OBJECT_QUICK 775 DF_UA | DF_UB | DF_NULL_CHK_1, 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, 791 792 // FD SGET_OBJECT_VOLATILE 793 DF_DA | DF_REF_A | DF_UMS, 794 795 // FE SPUT_OBJECT_VOLATILE 796 DF_UA | DF_REF_A | 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 845 /* Return the base virtual register for a SSA name */ 846 int MIRGraph::SRegToVReg(int ssa_reg) const { 847 return ssa_base_vregs_->Get(ssa_reg); 848 } 849 850 /* Any register that is used before being defined is considered live-in */ 851 void MIRGraph::HandleLiveInUse(ArenaBitVector* use_v, ArenaBitVector* def_v, 852 ArenaBitVector* live_in_v, int dalvik_reg_id) { 853 use_v->SetBit(dalvik_reg_id); 854 if (!def_v->IsBitSet(dalvik_reg_id)) { 855 live_in_v->SetBit(dalvik_reg_id); 856 } 857 } 858 859 /* Mark a reg as being defined */ 860 void MIRGraph::HandleDef(ArenaBitVector* def_v, int dalvik_reg_id) { 861 def_v->SetBit(dalvik_reg_id); 862 } 863 864 /* 865 * Find out live-in variables for natural loops. Variables that are live-in in 866 * the main loop body are considered to be defined in the entry block. 867 */ 868 bool MIRGraph::FindLocalLiveIn(BasicBlock* bb) { 869 MIR* mir; 870 ArenaBitVector *use_v, *def_v, *live_in_v; 871 872 if (bb->data_flow_info == NULL) return false; 873 874 use_v = bb->data_flow_info->use_v = 875 new (arena_) ArenaBitVector(arena_, cu_->num_dalvik_registers, false, kBitMapUse); 876 def_v = bb->data_flow_info->def_v = 877 new (arena_) ArenaBitVector(arena_, cu_->num_dalvik_registers, false, kBitMapDef); 878 live_in_v = bb->data_flow_info->live_in_v = 879 new (arena_) ArenaBitVector(arena_, cu_->num_dalvik_registers, false, kBitMapLiveIn); 880 881 for (mir = bb->first_mir_insn; mir != NULL; mir = mir->next) { 882 int df_attributes = oat_data_flow_attributes_[mir->dalvikInsn.opcode]; 883 DecodedInstruction *d_insn = &mir->dalvikInsn; 884 885 if (df_attributes & DF_HAS_USES) { 886 if (df_attributes & DF_UA) { 887 HandleLiveInUse(use_v, def_v, live_in_v, d_insn->vA); 888 if (df_attributes & DF_A_WIDE) { 889 HandleLiveInUse(use_v, def_v, live_in_v, d_insn->vA+1); 890 } 891 } 892 if (df_attributes & DF_UB) { 893 HandleLiveInUse(use_v, def_v, live_in_v, d_insn->vB); 894 if (df_attributes & DF_B_WIDE) { 895 HandleLiveInUse(use_v, def_v, live_in_v, d_insn->vB+1); 896 } 897 } 898 if (df_attributes & DF_UC) { 899 HandleLiveInUse(use_v, def_v, live_in_v, d_insn->vC); 900 if (df_attributes & DF_C_WIDE) { 901 HandleLiveInUse(use_v, def_v, live_in_v, d_insn->vC+1); 902 } 903 } 904 } 905 if (df_attributes & DF_FORMAT_35C) { 906 for (unsigned int i = 0; i < d_insn->vA; i++) { 907 HandleLiveInUse(use_v, def_v, live_in_v, d_insn->arg[i]); 908 } 909 } 910 if (df_attributes & DF_FORMAT_3RC) { 911 for (unsigned int i = 0; i < d_insn->vA; i++) { 912 HandleLiveInUse(use_v, def_v, live_in_v, d_insn->vC+i); 913 } 914 } 915 if (df_attributes & DF_HAS_DEFS) { 916 HandleDef(def_v, d_insn->vA); 917 if (df_attributes & DF_A_WIDE) { 918 HandleDef(def_v, d_insn->vA+1); 919 } 920 } 921 } 922 return true; 923 } 924 925 int MIRGraph::AddNewSReg(int v_reg) { 926 // Compiler temps always have a subscript of 0 927 int subscript = (v_reg < 0) ? 0 : ++ssa_last_defs_[v_reg]; 928 int ssa_reg = GetNumSSARegs(); 929 SetNumSSARegs(ssa_reg + 1); 930 ssa_base_vregs_->Insert(v_reg); 931 ssa_subscripts_->Insert(subscript); 932 DCHECK_EQ(ssa_base_vregs_->Size(), ssa_subscripts_->Size()); 933 return ssa_reg; 934 } 935 936 /* Find out the latest SSA register for a given Dalvik register */ 937 void MIRGraph::HandleSSAUse(int* uses, int dalvik_reg, int reg_index) { 938 DCHECK((dalvik_reg >= 0) && (dalvik_reg < cu_->num_dalvik_registers)); 939 uses[reg_index] = vreg_to_ssa_map_[dalvik_reg]; 940 } 941 942 /* Setup a new SSA register for a given Dalvik register */ 943 void MIRGraph::HandleSSADef(int* defs, int dalvik_reg, int reg_index) { 944 DCHECK((dalvik_reg >= 0) && (dalvik_reg < cu_->num_dalvik_registers)); 945 int ssa_reg = AddNewSReg(dalvik_reg); 946 vreg_to_ssa_map_[dalvik_reg] = ssa_reg; 947 defs[reg_index] = ssa_reg; 948 } 949 950 /* Look up new SSA names for format_35c instructions */ 951 void MIRGraph::DataFlowSSAFormat35C(MIR* mir) { 952 DecodedInstruction *d_insn = &mir->dalvikInsn; 953 int num_uses = d_insn->vA; 954 int i; 955 956 mir->ssa_rep->num_uses = num_uses; 957 mir->ssa_rep->uses = static_cast<int*>(arena_->Alloc(sizeof(int) * num_uses, 958 ArenaAllocator::kAllocDFInfo)); 959 // NOTE: will be filled in during type & size inference pass 960 mir->ssa_rep->fp_use = static_cast<bool*>(arena_->Alloc(sizeof(bool) * num_uses, 961 ArenaAllocator::kAllocDFInfo)); 962 963 for (i = 0; i < num_uses; i++) { 964 HandleSSAUse(mir->ssa_rep->uses, d_insn->arg[i], i); 965 } 966 } 967 968 /* Look up new SSA names for format_3rc instructions */ 969 void MIRGraph::DataFlowSSAFormat3RC(MIR* mir) { 970 DecodedInstruction *d_insn = &mir->dalvikInsn; 971 int num_uses = d_insn->vA; 972 int i; 973 974 mir->ssa_rep->num_uses = num_uses; 975 mir->ssa_rep->uses = static_cast<int*>(arena_->Alloc(sizeof(int) * num_uses, 976 ArenaAllocator::kAllocDFInfo)); 977 // NOTE: will be filled in during type & size inference pass 978 mir->ssa_rep->fp_use = static_cast<bool*>(arena_->Alloc(sizeof(bool) * num_uses, 979 ArenaAllocator::kAllocDFInfo)); 980 981 for (i = 0; i < num_uses; i++) { 982 HandleSSAUse(mir->ssa_rep->uses, d_insn->vC+i, i); 983 } 984 } 985 986 /* Entry function to convert a block into SSA representation */ 987 bool MIRGraph::DoSSAConversion(BasicBlock* bb) { 988 MIR* mir; 989 990 if (bb->data_flow_info == NULL) return false; 991 992 for (mir = bb->first_mir_insn; mir != NULL; mir = mir->next) { 993 mir->ssa_rep = 994 static_cast<struct SSARepresentation *>(arena_->Alloc(sizeof(SSARepresentation), 995 ArenaAllocator::kAllocDFInfo)); 996 997 int df_attributes = oat_data_flow_attributes_[mir->dalvikInsn.opcode]; 998 999 // If not a pseudo-op, note non-leaf or can throw 1000 if (static_cast<int>(mir->dalvikInsn.opcode) < 1001 static_cast<int>(kNumPackedOpcodes)) { 1002 int flags = Instruction::FlagsOf(mir->dalvikInsn.opcode); 1003 1004 if (flags & Instruction::kInvoke) { 1005 attributes_ &= ~METHOD_IS_LEAF; 1006 } 1007 } 1008 1009 int num_uses = 0; 1010 1011 if (df_attributes & DF_FORMAT_35C) { 1012 DataFlowSSAFormat35C(mir); 1013 continue; 1014 } 1015 1016 if (df_attributes & DF_FORMAT_3RC) { 1017 DataFlowSSAFormat3RC(mir); 1018 continue; 1019 } 1020 1021 if (df_attributes & DF_HAS_USES) { 1022 if (df_attributes & DF_UA) { 1023 num_uses++; 1024 if (df_attributes & DF_A_WIDE) { 1025 num_uses++; 1026 } 1027 } 1028 if (df_attributes & DF_UB) { 1029 num_uses++; 1030 if (df_attributes & DF_B_WIDE) { 1031 num_uses++; 1032 } 1033 } 1034 if (df_attributes & DF_UC) { 1035 num_uses++; 1036 if (df_attributes & DF_C_WIDE) { 1037 num_uses++; 1038 } 1039 } 1040 } 1041 1042 if (num_uses) { 1043 mir->ssa_rep->num_uses = num_uses; 1044 mir->ssa_rep->uses = static_cast<int*>(arena_->Alloc(sizeof(int) * num_uses, 1045 ArenaAllocator::kAllocDFInfo)); 1046 mir->ssa_rep->fp_use = static_cast<bool*>(arena_->Alloc(sizeof(bool) * num_uses, 1047 ArenaAllocator::kAllocDFInfo)); 1048 } 1049 1050 int num_defs = 0; 1051 1052 if (df_attributes & DF_HAS_DEFS) { 1053 num_defs++; 1054 if (df_attributes & DF_A_WIDE) { 1055 num_defs++; 1056 } 1057 } 1058 1059 if (num_defs) { 1060 mir->ssa_rep->num_defs = num_defs; 1061 mir->ssa_rep->defs = static_cast<int*>(arena_->Alloc(sizeof(int) * num_defs, 1062 ArenaAllocator::kAllocDFInfo)); 1063 mir->ssa_rep->fp_def = static_cast<bool*>(arena_->Alloc(sizeof(bool) * num_defs, 1064 ArenaAllocator::kAllocDFInfo)); 1065 } 1066 1067 DecodedInstruction *d_insn = &mir->dalvikInsn; 1068 1069 if (df_attributes & DF_HAS_USES) { 1070 num_uses = 0; 1071 if (df_attributes & DF_UA) { 1072 mir->ssa_rep->fp_use[num_uses] = df_attributes & DF_FP_A; 1073 HandleSSAUse(mir->ssa_rep->uses, d_insn->vA, num_uses++); 1074 if (df_attributes & DF_A_WIDE) { 1075 mir->ssa_rep->fp_use[num_uses] = df_attributes & DF_FP_A; 1076 HandleSSAUse(mir->ssa_rep->uses, d_insn->vA+1, num_uses++); 1077 } 1078 } 1079 if (df_attributes & DF_UB) { 1080 mir->ssa_rep->fp_use[num_uses] = df_attributes & DF_FP_B; 1081 HandleSSAUse(mir->ssa_rep->uses, d_insn->vB, num_uses++); 1082 if (df_attributes & DF_B_WIDE) { 1083 mir->ssa_rep->fp_use[num_uses] = df_attributes & DF_FP_B; 1084 HandleSSAUse(mir->ssa_rep->uses, d_insn->vB+1, num_uses++); 1085 } 1086 } 1087 if (df_attributes & DF_UC) { 1088 mir->ssa_rep->fp_use[num_uses] = df_attributes & DF_FP_C; 1089 HandleSSAUse(mir->ssa_rep->uses, d_insn->vC, num_uses++); 1090 if (df_attributes & DF_C_WIDE) { 1091 mir->ssa_rep->fp_use[num_uses] = df_attributes & DF_FP_C; 1092 HandleSSAUse(mir->ssa_rep->uses, d_insn->vC+1, num_uses++); 1093 } 1094 } 1095 } 1096 if (df_attributes & DF_HAS_DEFS) { 1097 mir->ssa_rep->fp_def[0] = df_attributes & DF_FP_A; 1098 HandleSSADef(mir->ssa_rep->defs, d_insn->vA, 0); 1099 if (df_attributes & DF_A_WIDE) { 1100 mir->ssa_rep->fp_def[1] = df_attributes & DF_FP_A; 1101 HandleSSADef(mir->ssa_rep->defs, d_insn->vA+1, 1); 1102 } 1103 } 1104 } 1105 1106 /* 1107 * Take a snapshot of Dalvik->SSA mapping at the end of each block. The 1108 * input to PHI nodes can be derived from the snapshot of all 1109 * predecessor blocks. 1110 */ 1111 bb->data_flow_info->vreg_to_ssa_map = 1112 static_cast<int*>(arena_->Alloc(sizeof(int) * cu_->num_dalvik_registers, 1113 ArenaAllocator::kAllocDFInfo)); 1114 1115 memcpy(bb->data_flow_info->vreg_to_ssa_map, vreg_to_ssa_map_, 1116 sizeof(int) * cu_->num_dalvik_registers); 1117 return true; 1118 } 1119 1120 /* Setup the basic data structures for SSA conversion */ 1121 void MIRGraph::CompilerInitializeSSAConversion() { 1122 size_t num_dalvik_reg = cu_->num_dalvik_registers; 1123 1124 ssa_base_vregs_ = new (arena_) GrowableArray<int>(arena_, num_dalvik_reg + GetDefCount() + 128, 1125 kGrowableArraySSAtoDalvikMap); 1126 ssa_subscripts_ = new (arena_) GrowableArray<int>(arena_, num_dalvik_reg + GetDefCount() + 128, 1127 kGrowableArraySSAtoDalvikMap); 1128 /* 1129 * Initial number of SSA registers is equal to the number of Dalvik 1130 * registers. 1131 */ 1132 SetNumSSARegs(num_dalvik_reg); 1133 1134 /* 1135 * Initialize the SSA2Dalvik map list. For the first num_dalvik_reg elements, 1136 * the subscript is 0 so we use the ENCODE_REG_SUB macro to encode the value 1137 * into "(0 << 16) | i" 1138 */ 1139 for (unsigned int i = 0; i < num_dalvik_reg; i++) { 1140 ssa_base_vregs_->Insert(i); 1141 ssa_subscripts_->Insert(0); 1142 } 1143 1144 /* 1145 * Initialize the DalvikToSSAMap map. There is one entry for each 1146 * Dalvik register, and the SSA names for those are the same. 1147 */ 1148 vreg_to_ssa_map_ = 1149 static_cast<int*>(arena_->Alloc(sizeof(int) * num_dalvik_reg, 1150 ArenaAllocator::kAllocDFInfo)); 1151 /* Keep track of the higest def for each dalvik reg */ 1152 ssa_last_defs_ = 1153 static_cast<int*>(arena_->Alloc(sizeof(int) * num_dalvik_reg, 1154 ArenaAllocator::kAllocDFInfo)); 1155 1156 for (unsigned int i = 0; i < num_dalvik_reg; i++) { 1157 vreg_to_ssa_map_[i] = i; 1158 ssa_last_defs_[i] = 0; 1159 } 1160 1161 /* Add ssa reg for Method* */ 1162 method_sreg_ = AddNewSReg(SSA_METHOD_BASEREG); 1163 1164 /* 1165 * Allocate the BasicBlockDataFlow structure for the entry and code blocks 1166 */ 1167 GrowableArray<BasicBlock*>::Iterator iterator(&block_list_); 1168 1169 while (true) { 1170 BasicBlock* bb = iterator.Next(); 1171 if (bb == NULL) break; 1172 if (bb->hidden == true) continue; 1173 if (bb->block_type == kDalvikByteCode || 1174 bb->block_type == kEntryBlock || 1175 bb->block_type == kExitBlock) { 1176 bb->data_flow_info = 1177 static_cast<BasicBlockDataFlow*>(arena_->Alloc(sizeof(BasicBlockDataFlow), 1178 ArenaAllocator::kAllocDFInfo)); 1179 } 1180 } 1181 } 1182 1183 /* 1184 * This function will make a best guess at whether the invoke will 1185 * end up using Method*. It isn't critical to get it exactly right, 1186 * and attempting to do would involve more complexity than it's 1187 * worth. 1188 */ 1189 bool MIRGraph::InvokeUsesMethodStar(MIR* mir) { 1190 InvokeType type; 1191 Instruction::Code opcode = mir->dalvikInsn.opcode; 1192 switch (opcode) { 1193 case Instruction::INVOKE_STATIC: 1194 case Instruction::INVOKE_STATIC_RANGE: 1195 type = kStatic; 1196 break; 1197 case Instruction::INVOKE_DIRECT: 1198 case Instruction::INVOKE_DIRECT_RANGE: 1199 type = kDirect; 1200 break; 1201 case Instruction::INVOKE_VIRTUAL: 1202 case Instruction::INVOKE_VIRTUAL_RANGE: 1203 type = kVirtual; 1204 break; 1205 case Instruction::INVOKE_INTERFACE: 1206 case Instruction::INVOKE_INTERFACE_RANGE: 1207 return false; 1208 case Instruction::INVOKE_SUPER_RANGE: 1209 case Instruction::INVOKE_SUPER: 1210 type = kSuper; 1211 break; 1212 default: 1213 LOG(WARNING) << "Unexpected invoke op: " << opcode; 1214 return false; 1215 } 1216 DexCompilationUnit m_unit(cu_); 1217 MethodReference target_method(cu_->dex_file, mir->dalvikInsn.vB); 1218 int vtable_idx; 1219 uintptr_t direct_code; 1220 uintptr_t direct_method; 1221 uint32_t current_offset = static_cast<uint32_t>(current_offset_); 1222 bool fast_path = 1223 cu_->compiler_driver->ComputeInvokeInfo(&m_unit, current_offset, 1224 type, target_method, 1225 vtable_idx, 1226 direct_code, direct_method, 1227 false) && 1228 !(cu_->enable_debug & (1 << kDebugSlowInvokePath)); 1229 return (((type == kDirect) || (type == kStatic)) && 1230 fast_path && ((direct_code == 0) || (direct_method == 0))); 1231 } 1232 1233 /* 1234 * Count uses, weighting by loop nesting depth. This code only 1235 * counts explicitly used s_regs. A later phase will add implicit 1236 * counts for things such as Method*, null-checked references, etc. 1237 */ 1238 bool MIRGraph::CountUses(struct BasicBlock* bb) { 1239 if (bb->block_type != kDalvikByteCode) { 1240 return false; 1241 } 1242 for (MIR* mir = bb->first_mir_insn; (mir != NULL); mir = mir->next) { 1243 if (mir->ssa_rep == NULL) { 1244 continue; 1245 } 1246 uint32_t weight = std::min(16U, static_cast<uint32_t>(bb->nesting_depth)); 1247 for (int i = 0; i < mir->ssa_rep->num_uses; i++) { 1248 int s_reg = mir->ssa_rep->uses[i]; 1249 raw_use_counts_.Increment(s_reg); 1250 use_counts_.Put(s_reg, use_counts_.Get(s_reg) + (1 << weight)); 1251 } 1252 if (!(cu_->disable_opt & (1 << kPromoteCompilerTemps))) { 1253 int df_attributes = oat_data_flow_attributes_[mir->dalvikInsn.opcode]; 1254 // Implicit use of Method* ? */ 1255 if (df_attributes & DF_UMS) { 1256 /* 1257 * Some invokes will not use Method* - need to perform test similar 1258 * to that found in GenInvoke() to decide whether to count refs 1259 * for Method* on invoke-class opcodes. 1260 * TODO: refactor for common test here, save results for GenInvoke 1261 */ 1262 int uses_method_star = true; 1263 if ((df_attributes & (DF_FORMAT_35C | DF_FORMAT_3RC)) && 1264 !(df_attributes & DF_NON_NULL_RET)) { 1265 uses_method_star &= InvokeUsesMethodStar(mir); 1266 } 1267 if (uses_method_star) { 1268 raw_use_counts_.Increment(method_sreg_); 1269 use_counts_.Put(method_sreg_, use_counts_.Get(method_sreg_) + (1 << weight)); 1270 } 1271 } 1272 } 1273 } 1274 return false; 1275 } 1276 1277 void MIRGraph::MethodUseCount() { 1278 // Now that we know, resize the lists. 1279 int num_ssa_regs = GetNumSSARegs(); 1280 use_counts_.Resize(num_ssa_regs + 32); 1281 raw_use_counts_.Resize(num_ssa_regs + 32); 1282 // Initialize list 1283 for (int i = 0; i < num_ssa_regs; i++) { 1284 use_counts_.Insert(0); 1285 raw_use_counts_.Insert(0); 1286 } 1287 if (cu_->disable_opt & (1 << kPromoteRegs)) { 1288 return; 1289 } 1290 AllNodesIterator iter(this, false /* not iterative */); 1291 for (BasicBlock* bb = iter.Next(); bb != NULL; bb = iter.Next()) { 1292 CountUses(bb); 1293 } 1294 } 1295 1296 /* Verify if all the successor is connected with all the claimed predecessors */ 1297 bool MIRGraph::VerifyPredInfo(BasicBlock* bb) { 1298 GrowableArray<BasicBlock*>::Iterator iter(bb->predecessors); 1299 1300 while (true) { 1301 BasicBlock *pred_bb = iter.Next(); 1302 if (!pred_bb) break; 1303 bool found = false; 1304 if (pred_bb->taken == bb) { 1305 found = true; 1306 } else if (pred_bb->fall_through == bb) { 1307 found = true; 1308 } else if (pred_bb->successor_block_list.block_list_type != kNotUsed) { 1309 GrowableArray<SuccessorBlockInfo*>::Iterator iterator(pred_bb->successor_block_list.blocks); 1310 while (true) { 1311 SuccessorBlockInfo *successor_block_info = iterator.Next(); 1312 if (successor_block_info == NULL) break; 1313 BasicBlock *succ_bb = successor_block_info->block; 1314 if (succ_bb == bb) { 1315 found = true; 1316 break; 1317 } 1318 } 1319 } 1320 if (found == false) { 1321 char block_name1[BLOCK_NAME_LEN], block_name2[BLOCK_NAME_LEN]; 1322 GetBlockName(bb, block_name1); 1323 GetBlockName(pred_bb, block_name2); 1324 DumpCFG("/sdcard/cfg/", false); 1325 LOG(FATAL) << "Successor " << block_name1 << "not found from " 1326 << block_name2; 1327 } 1328 } 1329 return true; 1330 } 1331 1332 void MIRGraph::VerifyDataflow() { 1333 /* Verify if all blocks are connected as claimed */ 1334 AllNodesIterator iter(this, false /* not iterative */); 1335 for (BasicBlock* bb = iter.Next(); bb != NULL; bb = iter.Next()) { 1336 VerifyPredInfo(bb); 1337 } 1338 } 1339 1340 } // namespace art 1341
