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