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