1 /* 2 * Copyright (C) 2012 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 "local_value_numbering.h" 18 19 namespace art { 20 21 22 uint16_t LocalValueNumbering::GetValueNumber(MIR* mir) { 23 uint16_t res = NO_VALUE; 24 uint16_t opcode = mir->dalvikInsn.opcode; 25 switch (opcode) { 26 case Instruction::NOP: 27 case Instruction::RETURN_VOID: 28 case Instruction::RETURN: 29 case Instruction::RETURN_OBJECT: 30 case Instruction::RETURN_WIDE: 31 case Instruction::MONITOR_ENTER: 32 case Instruction::MONITOR_EXIT: 33 case Instruction::GOTO: 34 case Instruction::GOTO_16: 35 case Instruction::GOTO_32: 36 case Instruction::CHECK_CAST: 37 case Instruction::THROW: 38 case Instruction::FILL_ARRAY_DATA: 39 case Instruction::FILLED_NEW_ARRAY: 40 case Instruction::FILLED_NEW_ARRAY_RANGE: 41 case Instruction::PACKED_SWITCH: 42 case Instruction::SPARSE_SWITCH: 43 case Instruction::IF_EQ: 44 case Instruction::IF_NE: 45 case Instruction::IF_LT: 46 case Instruction::IF_GE: 47 case Instruction::IF_GT: 48 case Instruction::IF_LE: 49 case Instruction::IF_EQZ: 50 case Instruction::IF_NEZ: 51 case Instruction::IF_LTZ: 52 case Instruction::IF_GEZ: 53 case Instruction::IF_GTZ: 54 case Instruction::IF_LEZ: 55 case Instruction::INVOKE_STATIC_RANGE: 56 case Instruction::INVOKE_STATIC: 57 case Instruction::INVOKE_DIRECT: 58 case Instruction::INVOKE_DIRECT_RANGE: 59 case Instruction::INVOKE_VIRTUAL: 60 case Instruction::INVOKE_VIRTUAL_RANGE: 61 case Instruction::INVOKE_SUPER: 62 case Instruction::INVOKE_SUPER_RANGE: 63 case Instruction::INVOKE_INTERFACE: 64 case Instruction::INVOKE_INTERFACE_RANGE: 65 case kMirOpFusedCmplFloat: 66 case kMirOpFusedCmpgFloat: 67 case kMirOpFusedCmplDouble: 68 case kMirOpFusedCmpgDouble: 69 case kMirOpFusedCmpLong: 70 // Nothing defined - take no action. 71 break; 72 73 case Instruction::MOVE_EXCEPTION: 74 case Instruction::MOVE_RESULT: 75 case Instruction::MOVE_RESULT_OBJECT: 76 case Instruction::INSTANCE_OF: 77 case Instruction::NEW_INSTANCE: 78 case Instruction::CONST_STRING: 79 case Instruction::CONST_STRING_JUMBO: 80 case Instruction::CONST_CLASS: 81 case Instruction::NEW_ARRAY: { 82 // 1 result, treat as unique each time, use result s_reg - will be unique. 83 uint16_t res = GetOperandValue(mir->ssa_rep->defs[0]); 84 SetOperandValue(mir->ssa_rep->defs[0], res); 85 } 86 break; 87 case Instruction::MOVE_RESULT_WIDE: { 88 // 1 wide result, treat as unique each time, use result s_reg - will be unique. 89 uint16_t res = GetOperandValueWide(mir->ssa_rep->defs[0]); 90 SetOperandValueWide(mir->ssa_rep->defs[0], res); 91 } 92 break; 93 94 case kMirOpPhi: 95 /* 96 * Because we'll only see phi nodes at the beginning of an extended basic block, 97 * we can ignore them. Revisit if we shift to global value numbering. 98 */ 99 break; 100 101 case Instruction::MOVE: 102 case Instruction::MOVE_OBJECT: 103 case Instruction::MOVE_16: 104 case Instruction::MOVE_OBJECT_16: 105 case Instruction::MOVE_FROM16: 106 case Instruction::MOVE_OBJECT_FROM16: 107 case kMirOpCopy: { 108 // Just copy value number of source to value number of resulit. 109 uint16_t res = GetOperandValue(mir->ssa_rep->uses[0]); 110 SetOperandValue(mir->ssa_rep->defs[0], res); 111 } 112 break; 113 114 case Instruction::MOVE_WIDE: 115 case Instruction::MOVE_WIDE_16: 116 case Instruction::MOVE_WIDE_FROM16: { 117 // Just copy value number of source to value number of result. 118 uint16_t res = GetOperandValueWide(mir->ssa_rep->uses[0]); 119 SetOperandValueWide(mir->ssa_rep->defs[0], res); 120 } 121 break; 122 123 case Instruction::CONST: 124 case Instruction::CONST_4: 125 case Instruction::CONST_16: { 126 uint16_t res = LookupValue(Instruction::CONST, Low16Bits(mir->dalvikInsn.vB), 127 High16Bits(mir->dalvikInsn.vB >> 16), 0); 128 SetOperandValue(mir->ssa_rep->defs[0], res); 129 } 130 break; 131 132 case Instruction::CONST_HIGH16: { 133 uint16_t res = LookupValue(Instruction::CONST, 0, mir->dalvikInsn.vB, 0); 134 SetOperandValue(mir->ssa_rep->defs[0], res); 135 } 136 break; 137 138 case Instruction::CONST_WIDE_16: 139 case Instruction::CONST_WIDE_32: { 140 uint16_t low_res = LookupValue(Instruction::CONST, Low16Bits(mir->dalvikInsn.vB), 141 High16Bits(mir->dalvikInsn.vB >> 16), 1); 142 uint16_t high_res; 143 if (mir->dalvikInsn.vB & 0x80000000) { 144 high_res = LookupValue(Instruction::CONST, 0xffff, 0xffff, 2); 145 } else { 146 high_res = LookupValue(Instruction::CONST, 0, 0, 2); 147 } 148 uint16_t res = LookupValue(Instruction::CONST, low_res, high_res, 3); 149 SetOperandValue(mir->ssa_rep->defs[0], res); 150 } 151 break; 152 153 case Instruction::CONST_WIDE: { 154 uint32_t low_word = Low32Bits(mir->dalvikInsn.vB_wide); 155 uint32_t high_word = High32Bits(mir->dalvikInsn.vB_wide); 156 uint16_t low_res = LookupValue(Instruction::CONST, Low16Bits(low_word), 157 High16Bits(low_word), 1); 158 uint16_t high_res = LookupValue(Instruction::CONST, Low16Bits(high_word), 159 High16Bits(high_word), 2); 160 uint16_t res = LookupValue(Instruction::CONST, low_res, high_res, 3); 161 SetOperandValueWide(mir->ssa_rep->defs[0], res); 162 } 163 break; 164 165 case Instruction::CONST_WIDE_HIGH16: { 166 uint16_t low_res = LookupValue(Instruction::CONST, 0, 0, 1); 167 uint16_t high_res = LookupValue(Instruction::CONST, 0, Low16Bits(mir->dalvikInsn.vB), 2); 168 uint16_t res = LookupValue(Instruction::CONST, low_res, high_res, 3); 169 SetOperandValueWide(mir->ssa_rep->defs[0], res); 170 } 171 break; 172 173 case Instruction::ARRAY_LENGTH: 174 case Instruction::NEG_INT: 175 case Instruction::NOT_INT: 176 case Instruction::NEG_FLOAT: 177 case Instruction::INT_TO_BYTE: 178 case Instruction::INT_TO_SHORT: 179 case Instruction::INT_TO_CHAR: 180 case Instruction::INT_TO_FLOAT: 181 case Instruction::FLOAT_TO_INT: { 182 // res = op + 1 operand 183 uint16_t operand1 = GetOperandValue(mir->ssa_rep->uses[0]); 184 uint16_t res = LookupValue(opcode, operand1, NO_VALUE, NO_VALUE); 185 SetOperandValue(mir->ssa_rep->defs[0], res); 186 } 187 break; 188 189 case Instruction::LONG_TO_FLOAT: 190 case Instruction::LONG_TO_INT: 191 case Instruction::DOUBLE_TO_FLOAT: 192 case Instruction::DOUBLE_TO_INT: { 193 // res = op + 1 wide operand 194 uint16_t operand1 = GetOperandValue(mir->ssa_rep->uses[0]); 195 uint16_t res = LookupValue(opcode, operand1, NO_VALUE, NO_VALUE); 196 SetOperandValue(mir->ssa_rep->defs[0], res); 197 } 198 break; 199 200 201 case Instruction::DOUBLE_TO_LONG: 202 case Instruction::LONG_TO_DOUBLE: 203 case Instruction::NEG_LONG: 204 case Instruction::NOT_LONG: 205 case Instruction::NEG_DOUBLE: { 206 // wide res = op + 1 wide operand 207 uint16_t operand1 = GetOperandValueWide(mir->ssa_rep->uses[0]); 208 uint16_t res = LookupValue(opcode, operand1, NO_VALUE, NO_VALUE); 209 SetOperandValueWide(mir->ssa_rep->defs[0], res); 210 } 211 break; 212 213 case Instruction::FLOAT_TO_DOUBLE: 214 case Instruction::FLOAT_TO_LONG: 215 case Instruction::INT_TO_DOUBLE: 216 case Instruction::INT_TO_LONG: { 217 // wide res = op + 1 operand 218 uint16_t operand1 = GetOperandValueWide(mir->ssa_rep->uses[0]); 219 uint16_t res = LookupValue(opcode, operand1, NO_VALUE, NO_VALUE); 220 SetOperandValueWide(mir->ssa_rep->defs[0], res); 221 } 222 break; 223 224 case Instruction::CMPL_DOUBLE: 225 case Instruction::CMPG_DOUBLE: 226 case Instruction::CMP_LONG: { 227 // res = op + 2 wide operands 228 uint16_t operand1 = GetOperandValueWide(mir->ssa_rep->uses[0]); 229 uint16_t operand2 = GetOperandValueWide(mir->ssa_rep->uses[2]); 230 uint16_t res = LookupValue(opcode, operand1, operand2, NO_VALUE); 231 SetOperandValue(mir->ssa_rep->defs[0], res); 232 } 233 break; 234 235 case Instruction::CMPG_FLOAT: 236 case Instruction::CMPL_FLOAT: 237 case Instruction::ADD_INT: 238 case Instruction::ADD_INT_2ADDR: 239 case Instruction::MUL_INT: 240 case Instruction::MUL_INT_2ADDR: 241 case Instruction::AND_INT: 242 case Instruction::AND_INT_2ADDR: 243 case Instruction::OR_INT: 244 case Instruction::OR_INT_2ADDR: 245 case Instruction::XOR_INT: 246 case Instruction::XOR_INT_2ADDR: 247 case Instruction::SUB_INT: 248 case Instruction::SUB_INT_2ADDR: 249 case Instruction::DIV_INT: 250 case Instruction::DIV_INT_2ADDR: 251 case Instruction::REM_INT: 252 case Instruction::REM_INT_2ADDR: 253 case Instruction::SHL_INT: 254 case Instruction::SHL_INT_2ADDR: 255 case Instruction::SHR_INT: 256 case Instruction::SHR_INT_2ADDR: 257 case Instruction::USHR_INT: 258 case Instruction::USHR_INT_2ADDR: { 259 // res = op + 2 operands 260 uint16_t operand1 = GetOperandValue(mir->ssa_rep->uses[0]); 261 uint16_t operand2 = GetOperandValue(mir->ssa_rep->uses[1]); 262 uint16_t res = LookupValue(opcode, operand1, operand2, NO_VALUE); 263 SetOperandValue(mir->ssa_rep->defs[0], res); 264 } 265 break; 266 267 case Instruction::ADD_LONG: 268 case Instruction::SUB_LONG: 269 case Instruction::MUL_LONG: 270 case Instruction::DIV_LONG: 271 case Instruction::REM_LONG: 272 case Instruction::AND_LONG: 273 case Instruction::OR_LONG: 274 case Instruction::XOR_LONG: 275 case Instruction::ADD_LONG_2ADDR: 276 case Instruction::SUB_LONG_2ADDR: 277 case Instruction::MUL_LONG_2ADDR: 278 case Instruction::DIV_LONG_2ADDR: 279 case Instruction::REM_LONG_2ADDR: 280 case Instruction::AND_LONG_2ADDR: 281 case Instruction::OR_LONG_2ADDR: 282 case Instruction::XOR_LONG_2ADDR: 283 case Instruction::ADD_DOUBLE: 284 case Instruction::SUB_DOUBLE: 285 case Instruction::MUL_DOUBLE: 286 case Instruction::DIV_DOUBLE: 287 case Instruction::REM_DOUBLE: 288 case Instruction::ADD_DOUBLE_2ADDR: 289 case Instruction::SUB_DOUBLE_2ADDR: 290 case Instruction::MUL_DOUBLE_2ADDR: 291 case Instruction::DIV_DOUBLE_2ADDR: 292 case Instruction::REM_DOUBLE_2ADDR: { 293 // wide res = op + 2 wide operands 294 uint16_t operand1 = GetOperandValueWide(mir->ssa_rep->uses[0]); 295 uint16_t operand2 = GetOperandValueWide(mir->ssa_rep->uses[2]); 296 uint16_t res = LookupValue(opcode, operand1, operand2, NO_VALUE); 297 SetOperandValueWide(mir->ssa_rep->defs[0], res); 298 } 299 break; 300 301 case Instruction::SHL_LONG: 302 case Instruction::SHR_LONG: 303 case Instruction::USHR_LONG: 304 case Instruction::SHL_LONG_2ADDR: 305 case Instruction::SHR_LONG_2ADDR: 306 case Instruction::USHR_LONG_2ADDR: { 307 // wide res = op + 1 wide operand + 1 operand 308 uint16_t operand1 = GetOperandValueWide(mir->ssa_rep->uses[0]); 309 uint16_t operand2 = GetOperandValueWide(mir->ssa_rep->uses[2]); 310 uint16_t res = LookupValue(opcode, operand1, operand2, NO_VALUE); 311 SetOperandValueWide(mir->ssa_rep->defs[0], res); 312 } 313 break; 314 315 case Instruction::ADD_FLOAT: 316 case Instruction::SUB_FLOAT: 317 case Instruction::MUL_FLOAT: 318 case Instruction::DIV_FLOAT: 319 case Instruction::REM_FLOAT: 320 case Instruction::ADD_FLOAT_2ADDR: 321 case Instruction::SUB_FLOAT_2ADDR: 322 case Instruction::MUL_FLOAT_2ADDR: 323 case Instruction::DIV_FLOAT_2ADDR: 324 case Instruction::REM_FLOAT_2ADDR: { 325 // res = op + 2 operands 326 uint16_t operand1 = GetOperandValue(mir->ssa_rep->uses[0]); 327 uint16_t operand2 = GetOperandValue(mir->ssa_rep->uses[1]); 328 uint16_t res = LookupValue(opcode, operand1, operand2, NO_VALUE); 329 SetOperandValue(mir->ssa_rep->defs[0], res); 330 } 331 break; 332 333 case Instruction::RSUB_INT: 334 case Instruction::ADD_INT_LIT16: 335 case Instruction::MUL_INT_LIT16: 336 case Instruction::DIV_INT_LIT16: 337 case Instruction::REM_INT_LIT16: 338 case Instruction::AND_INT_LIT16: 339 case Instruction::OR_INT_LIT16: 340 case Instruction::XOR_INT_LIT16: 341 case Instruction::ADD_INT_LIT8: 342 case Instruction::RSUB_INT_LIT8: 343 case Instruction::MUL_INT_LIT8: 344 case Instruction::DIV_INT_LIT8: 345 case Instruction::REM_INT_LIT8: 346 case Instruction::AND_INT_LIT8: 347 case Instruction::OR_INT_LIT8: 348 case Instruction::XOR_INT_LIT8: 349 case Instruction::SHL_INT_LIT8: 350 case Instruction::SHR_INT_LIT8: 351 case Instruction::USHR_INT_LIT8: { 352 // Same as res = op + 2 operands, except use vB as operand 2 353 uint16_t operand1 = GetOperandValue(mir->ssa_rep->uses[0]); 354 uint16_t operand2 = LookupValue(Instruction::CONST, mir->dalvikInsn.vB, 0, 0); 355 uint16_t res = LookupValue(opcode, operand1, operand2, NO_VALUE); 356 SetOperandValue(mir->ssa_rep->defs[0], res); 357 } 358 break; 359 360 case Instruction::AGET_WIDE: 361 case Instruction::AGET: 362 case Instruction::AGET_OBJECT: 363 case Instruction::AGET_BOOLEAN: 364 case Instruction::AGET_BYTE: 365 case Instruction::AGET_CHAR: 366 case Instruction::AGET_SHORT: { 367 uint16_t array = GetOperandValue(mir->ssa_rep->uses[0]); 368 if (null_checked_.find(array) != null_checked_.end()) { 369 if (cu_->verbose) { 370 LOG(INFO) << "Removing null check for 0x" << std::hex << mir->offset; 371 } 372 mir->optimization_flags |= MIR_IGNORE_NULL_CHECK; 373 } else { 374 null_checked_.insert(array); 375 } 376 uint16_t index = GetOperandValue(mir->ssa_rep->uses[1]); 377 if (ValueExists(ARRAY_REF, array, index, NO_VALUE)) { 378 if (cu_->verbose) { 379 LOG(INFO) << "Removing range check for 0x" << std::hex << mir->offset; 380 } 381 mir->optimization_flags |= MIR_IGNORE_RANGE_CHECK; 382 } 383 mir->meta.throw_insn->optimization_flags |= mir->optimization_flags; 384 // Use side effect to note range check completed. 385 (void)LookupValue(ARRAY_REF, array, index, NO_VALUE); 386 // Establish value number for loaded register. Note use of memory version. 387 uint16_t memory_version = GetMemoryVersion(array, NO_VALUE); 388 uint16_t res = LookupValue(ARRAY_REF, array, index, memory_version); 389 if (opcode == Instruction::AGET_WIDE) { 390 SetOperandValueWide(mir->ssa_rep->defs[0], res); 391 } else { 392 SetOperandValue(mir->ssa_rep->defs[0], res); 393 } 394 } 395 break; 396 397 case Instruction::APUT_WIDE: 398 case Instruction::APUT: 399 case Instruction::APUT_OBJECT: 400 case Instruction::APUT_SHORT: 401 case Instruction::APUT_CHAR: 402 case Instruction::APUT_BYTE: 403 case Instruction::APUT_BOOLEAN: { 404 int array_idx = (opcode == Instruction::APUT_WIDE) ? 2 : 1; 405 int index_idx = array_idx + 1; 406 uint16_t array = GetOperandValue(mir->ssa_rep->uses[array_idx]); 407 if (null_checked_.find(array) != null_checked_.end()) { 408 if (cu_->verbose) { 409 LOG(INFO) << "Removing range check for 0x" << std::hex << mir->offset; 410 } 411 mir->optimization_flags |= MIR_IGNORE_NULL_CHECK; 412 } else { 413 null_checked_.insert(array); 414 } 415 uint16_t index = GetOperandValue(mir->ssa_rep->uses[index_idx]); 416 if (ValueExists(ARRAY_REF, array, index, NO_VALUE)) { 417 if (cu_->verbose) { 418 LOG(INFO) << "Removing range check for 0x" << std::hex << mir->offset; 419 } 420 mir->optimization_flags |= MIR_IGNORE_RANGE_CHECK; 421 } 422 mir->meta.throw_insn->optimization_flags |= mir->optimization_flags; 423 // Use side effect to note range check completed. 424 (void)LookupValue(ARRAY_REF, array, index, NO_VALUE); 425 // Rev the memory version 426 AdvanceMemoryVersion(array, NO_VALUE); 427 } 428 break; 429 430 case Instruction::IGET_OBJECT: 431 case Instruction::IGET_WIDE: 432 case Instruction::IGET: 433 case Instruction::IGET_CHAR: 434 case Instruction::IGET_SHORT: 435 case Instruction::IGET_BOOLEAN: 436 case Instruction::IGET_BYTE: { 437 uint16_t base = GetOperandValue(mir->ssa_rep->uses[0]); 438 if (null_checked_.find(base) != null_checked_.end()) { 439 if (cu_->verbose) { 440 LOG(INFO) << "Removing null check for 0x" << std::hex << mir->offset; 441 } 442 mir->optimization_flags |= MIR_IGNORE_NULL_CHECK; 443 } else { 444 null_checked_.insert(base); 445 } 446 mir->meta.throw_insn->optimization_flags |= mir->optimization_flags; 447 uint16_t field_ref = mir->dalvikInsn.vC; 448 uint16_t memory_version = GetMemoryVersion(base, field_ref); 449 if (opcode == Instruction::IGET_WIDE) { 450 uint16_t res = LookupValue(Instruction::IGET_WIDE, base, field_ref, memory_version); 451 SetOperandValueWide(mir->ssa_rep->defs[0], res); 452 } else { 453 uint16_t res = LookupValue(Instruction::IGET, base, field_ref, memory_version); 454 SetOperandValue(mir->ssa_rep->defs[0], res); 455 } 456 } 457 break; 458 459 case Instruction::IPUT_WIDE: 460 case Instruction::IPUT_OBJECT: 461 case Instruction::IPUT: 462 case Instruction::IPUT_BOOLEAN: 463 case Instruction::IPUT_BYTE: 464 case Instruction::IPUT_CHAR: 465 case Instruction::IPUT_SHORT: { 466 int base_reg = (opcode == Instruction::IPUT_WIDE) ? 2 : 1; 467 uint16_t base = GetOperandValue(mir->ssa_rep->uses[base_reg]); 468 if (null_checked_.find(base) != null_checked_.end()) { 469 if (cu_->verbose) { 470 LOG(INFO) << "Removing null check for 0x" << std::hex << mir->offset; 471 } 472 mir->optimization_flags |= MIR_IGNORE_NULL_CHECK; 473 } else { 474 null_checked_.insert(base); 475 } 476 mir->meta.throw_insn->optimization_flags |= mir->optimization_flags; 477 uint16_t field_ref = mir->dalvikInsn.vC; 478 AdvanceMemoryVersion(base, field_ref); 479 } 480 break; 481 482 case Instruction::SGET_OBJECT: 483 case Instruction::SGET: 484 case Instruction::SGET_BOOLEAN: 485 case Instruction::SGET_BYTE: 486 case Instruction::SGET_CHAR: 487 case Instruction::SGET_SHORT: 488 case Instruction::SGET_WIDE: { 489 uint16_t field_ref = mir->dalvikInsn.vB; 490 uint16_t memory_version = GetMemoryVersion(NO_VALUE, field_ref); 491 if (opcode == Instruction::SGET_WIDE) { 492 uint16_t res = LookupValue(Instruction::SGET_WIDE, NO_VALUE, field_ref, memory_version); 493 SetOperandValueWide(mir->ssa_rep->defs[0], res); 494 } else { 495 uint16_t res = LookupValue(Instruction::SGET, NO_VALUE, field_ref, memory_version); 496 SetOperandValue(mir->ssa_rep->defs[0], res); 497 } 498 } 499 break; 500 501 case Instruction::SPUT_OBJECT: 502 case Instruction::SPUT: 503 case Instruction::SPUT_BOOLEAN: 504 case Instruction::SPUT_BYTE: 505 case Instruction::SPUT_CHAR: 506 case Instruction::SPUT_SHORT: 507 case Instruction::SPUT_WIDE: { 508 uint16_t field_ref = mir->dalvikInsn.vB; 509 AdvanceMemoryVersion(NO_VALUE, field_ref); 510 } 511 break; 512 } 513 return res; 514 } 515 516 } // namespace art 517