local_value_numbering.cc revision ffddfdf6fec0b9d98a692e27242eecb15af5ead2
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#include "mir_field_info.h" 20#include "mir_graph.h" 21 22namespace art { 23 24namespace { // anonymous namespace 25 26// Operations used for value map keys instead of actual opcode. 27static constexpr uint16_t kInvokeMemoryVersionBumpOp = Instruction::INVOKE_DIRECT; 28static constexpr uint16_t kUnresolvedSFieldOp = Instruction::SPUT; 29static constexpr uint16_t kResolvedSFieldOp = Instruction::SGET; 30static constexpr uint16_t kUnresolvedIFieldOp = Instruction::IPUT; 31static constexpr uint16_t kNonAliasingIFieldOp = Instruction::IGET; 32static constexpr uint16_t kAliasingIFieldOp = Instruction::IGET_WIDE; 33static constexpr uint16_t kAliasingIFieldStartVersionOp = Instruction::IGET_WIDE; 34static constexpr uint16_t kAliasingIFieldBumpVersionOp = Instruction::IGET_OBJECT; 35static constexpr uint16_t kArrayAccessLocOp = Instruction::APUT; 36static constexpr uint16_t kNonAliasingArrayOp = Instruction::AGET; 37static constexpr uint16_t kNonAliasingArrayStartVersionOp = Instruction::AGET_WIDE; 38static constexpr uint16_t kAliasingArrayOp = Instruction::AGET_OBJECT; 39static constexpr uint16_t kAliasingArrayMemoryVersionOp = Instruction::AGET_BOOLEAN; 40static constexpr uint16_t kAliasingArrayBumpVersionOp = Instruction::AGET_BYTE; 41 42} // anonymous namespace 43 44LocalValueNumbering::LocalValueNumbering(CompilationUnit* cu, ScopedArenaAllocator* allocator) 45 : cu_(cu), 46 last_value_(0u), 47 sreg_value_map_(std::less<uint16_t>(), allocator->Adapter()), 48 sreg_wide_value_map_(std::less<uint16_t>(), allocator->Adapter()), 49 value_map_(std::less<uint64_t>(), allocator->Adapter()), 50 global_memory_version_(0u), 51 aliasing_ifield_version_map_(std::less<uint16_t>(), allocator->Adapter()), 52 non_aliasing_array_version_map_(std::less<uint16_t>(), allocator->Adapter()), 53 field_index_map_(FieldReferenceComparator(), allocator->Adapter()), 54 non_aliasing_refs_(std::less<uint16_t>(), allocator->Adapter()), 55 non_aliasing_ifields_(NonAliasingIFieldKeyComparator(), allocator->Adapter()), 56 escaped_array_refs_(EscapedArrayKeyComparator(), allocator->Adapter()), 57 range_checked_(RangeCheckKeyComparator() , allocator->Adapter()), 58 null_checked_(std::less<uint16_t>(), allocator->Adapter()) { 59 std::fill_n(unresolved_sfield_version_, kFieldTypeCount, 0u); 60 std::fill_n(unresolved_ifield_version_, kFieldTypeCount, 0u); 61 std::fill_n(aliasing_array_version_, kFieldTypeCount, 0u); 62} 63 64uint16_t LocalValueNumbering::GetFieldId(const MirFieldInfo& field_info) { 65 FieldReference key = { field_info.DeclaringDexFile(), field_info.DeclaringFieldIndex() }; 66 auto it = field_index_map_.find(key); 67 if (it != field_index_map_.end()) { 68 return it->second; 69 } 70 uint16_t id = field_index_map_.size(); 71 field_index_map_.Put(key, id); 72 return id; 73} 74 75uint16_t LocalValueNumbering::MarkNonAliasingNonNull(MIR* mir) { 76 uint16_t res = GetOperandValue(mir->ssa_rep->defs[0]); 77 SetOperandValue(mir->ssa_rep->defs[0], res); 78 DCHECK(null_checked_.find(res) == null_checked_.end()); 79 null_checked_.insert(res); 80 non_aliasing_refs_.insert(res); 81 return res; 82} 83 84bool LocalValueNumbering::IsNonAliasing(uint16_t reg) { 85 return non_aliasing_refs_.find(reg) != non_aliasing_refs_.end(); 86} 87 88bool LocalValueNumbering::IsNonAliasingIField(uint16_t reg, uint16_t field_id, uint16_t type) { 89 if (IsNonAliasing(reg)) { 90 return true; 91 } 92 NonAliasingIFieldKey key = { reg, field_id, type }; 93 return non_aliasing_ifields_.count(key) != 0u; 94} 95 96bool LocalValueNumbering::IsNonAliasingArray(uint16_t reg, uint16_t type) { 97 if (IsNonAliasing(reg)) { 98 return true; 99 } 100 EscapedArrayKey key = { reg, type }; 101 return escaped_array_refs_.count(key) != 0u; 102} 103 104 105void LocalValueNumbering::HandleNullCheck(MIR* mir, uint16_t reg) { 106 auto lb = null_checked_.lower_bound(reg); 107 if (lb != null_checked_.end() && *lb == reg) { 108 if (LIKELY(Good())) { 109 if (cu_->verbose) { 110 LOG(INFO) << "Removing null check for 0x" << std::hex << mir->offset; 111 } 112 mir->optimization_flags |= MIR_IGNORE_NULL_CHECK; 113 } 114 } else { 115 null_checked_.insert(lb, reg); 116 } 117} 118 119void LocalValueNumbering::HandleRangeCheck(MIR* mir, uint16_t array, uint16_t index) { 120 RangeCheckKey key = { array, index }; 121 auto lb = range_checked_.lower_bound(key); 122 if (lb != range_checked_.end() && !RangeCheckKeyComparator()(key, *lb)) { 123 if (LIKELY(Good())) { 124 if (cu_->verbose) { 125 LOG(INFO) << "Removing range check for 0x" << std::hex << mir->offset; 126 } 127 mir->optimization_flags |= MIR_IGNORE_RANGE_CHECK; 128 } 129 } else { 130 // Mark range check completed. 131 range_checked_.insert(lb, key); 132 } 133} 134 135void LocalValueNumbering::HandlePutObject(MIR* mir) { 136 // If we're storing a non-aliasing reference, stop tracking it as non-aliasing now. 137 uint16_t base = GetOperandValue(mir->ssa_rep->uses[0]); 138 HandleEscapingRef(base); 139} 140 141void LocalValueNumbering::HandleEscapingRef(uint16_t base) { 142 auto it = non_aliasing_refs_.find(base); 143 if (it != non_aliasing_refs_.end()) { 144 uint64_t iget_key = BuildKey(Instruction::IGET, base, 0u, 0u); 145 for (auto iget_it = value_map_.lower_bound(iget_key), iget_end = value_map_.end(); 146 iget_it != iget_end && EqualOpAndOperand1(iget_it->first, iget_key); ++iget_it) { 147 uint16_t field_id = ExtractOperand2(iget_it->first); 148 uint16_t type = ExtractModifier(iget_it->first); 149 NonAliasingIFieldKey key = { base, field_id, type }; 150 non_aliasing_ifields_.insert(key); 151 } 152 uint64_t aget_key = BuildKey(kNonAliasingArrayStartVersionOp, base, 0u, 0u); 153 auto aget_it = value_map_.lower_bound(aget_key); 154 if (aget_it != value_map_.end() && EqualOpAndOperand1(aget_key, aget_it->first)) { 155 DCHECK_EQ(ExtractOperand2(aget_it->first), kNoValue); 156 uint16_t type = ExtractModifier(aget_it->first); 157 EscapedArrayKey key = { base, type }; 158 escaped_array_refs_.insert(key); 159 } 160 non_aliasing_refs_.erase(it); 161 } 162} 163 164uint16_t LocalValueNumbering::HandleAGet(MIR* mir, uint16_t opcode) { 165 // uint16_t type = opcode - Instruction::AGET; 166 uint16_t array = GetOperandValue(mir->ssa_rep->uses[0]); 167 HandleNullCheck(mir, array); 168 uint16_t index = GetOperandValue(mir->ssa_rep->uses[1]); 169 HandleRangeCheck(mir, array, index); 170 uint16_t type = opcode - Instruction::AGET; 171 // Establish value number for loaded register. 172 uint16_t res; 173 if (IsNonAliasingArray(array, type)) { 174 // Get the start version that accounts for aliasing within the array (different index names). 175 uint16_t start_version = LookupValue(kNonAliasingArrayStartVersionOp, array, kNoValue, type); 176 // Find the current version from the non_aliasing_array_version_map_. 177 uint16_t memory_version = start_version; 178 auto it = non_aliasing_array_version_map_.find(start_version); 179 if (it != non_aliasing_array_version_map_.end()) { 180 memory_version = it->second; 181 } else { 182 // Just use the start_version. 183 } 184 res = LookupValue(kNonAliasingArrayOp, array, index, memory_version); 185 } else { 186 // Get the memory version of aliased array accesses of this type. 187 uint16_t memory_version = LookupValue(kAliasingArrayMemoryVersionOp, global_memory_version_, 188 aliasing_array_version_[type], kNoValue); 189 res = LookupValue(kAliasingArrayOp, array, index, memory_version); 190 } 191 if (opcode == Instruction::AGET_WIDE) { 192 SetOperandValueWide(mir->ssa_rep->defs[0], res); 193 } else { 194 SetOperandValue(mir->ssa_rep->defs[0], res); 195 } 196 return res; 197} 198 199void LocalValueNumbering::HandleAPut(MIR* mir, uint16_t opcode) { 200 int array_idx = (opcode == Instruction::APUT_WIDE) ? 2 : 1; 201 int index_idx = array_idx + 1; 202 uint16_t array = GetOperandValue(mir->ssa_rep->uses[array_idx]); 203 HandleNullCheck(mir, array); 204 uint16_t index = GetOperandValue(mir->ssa_rep->uses[index_idx]); 205 HandleRangeCheck(mir, array, index); 206 207 uint16_t type = opcode - Instruction::APUT; 208 uint16_t value = (opcode == Instruction::APUT_WIDE) 209 ? GetOperandValueWide(mir->ssa_rep->uses[0]) 210 : GetOperandValue(mir->ssa_rep->uses[0]); 211 if (IsNonAliasing(array)) { 212 // Get the start version that accounts for aliasing within the array (different index values). 213 uint16_t start_version = LookupValue(kNonAliasingArrayStartVersionOp, array, kNoValue, type); 214 auto it = non_aliasing_array_version_map_.find(start_version); 215 uint16_t memory_version = start_version; 216 if (it != non_aliasing_array_version_map_.end()) { 217 memory_version = it->second; 218 } 219 // We need to take 4 values (array, index, memory_version, value) into account for bumping 220 // the memory version but the key can take only 3. Merge array and index into a location. 221 uint16_t array_access_location = LookupValue(kArrayAccessLocOp, array, index, kNoValue); 222 // Bump the version, adding to the chain. 223 memory_version = LookupValue(kAliasingArrayBumpVersionOp, memory_version, 224 array_access_location, value); 225 non_aliasing_array_version_map_.Overwrite(start_version, memory_version); 226 StoreValue(kNonAliasingArrayOp, array, index, memory_version, value); 227 } else { 228 // Get the memory version based on global_memory_version_ and aliasing_array_version_[type]. 229 uint16_t memory_version = LookupValue(kAliasingArrayMemoryVersionOp, global_memory_version_, 230 aliasing_array_version_[type], kNoValue); 231 if (HasValue(kAliasingArrayOp, array, index, memory_version, value)) { 232 // This APUT can be eliminated, it stores the same value that's already in the field. 233 // TODO: Eliminate the APUT. 234 return; 235 } 236 // We need to take 4 values (array, index, memory_version, value) into account for bumping 237 // the memory version but the key can take only 3. Merge array and index into a location. 238 uint16_t array_access_location = LookupValue(kArrayAccessLocOp, array, index, kNoValue); 239 // Bump the version, adding to the chain. 240 uint16_t bumped_version = LookupValue(kAliasingArrayBumpVersionOp, memory_version, 241 array_access_location, value); 242 aliasing_array_version_[type] = bumped_version; 243 memory_version = LookupValue(kAliasingArrayMemoryVersionOp, global_memory_version_, 244 bumped_version, kNoValue); 245 StoreValue(kAliasingArrayOp, array, index, memory_version, value); 246 247 // Clear escaped array refs for this type. 248 EscapedArrayKey array_key = { type, 0u }; 249 auto it = escaped_array_refs_.lower_bound(array_key), end = escaped_array_refs_.end(); 250 while (it != end && it->type == type) { 251 it = escaped_array_refs_.erase(it); 252 } 253 } 254} 255 256uint16_t LocalValueNumbering::HandleIGet(MIR* mir, uint16_t opcode) { 257 uint16_t base = GetOperandValue(mir->ssa_rep->uses[0]); 258 HandleNullCheck(mir, base); 259 const MirFieldInfo& field_info = cu_->mir_graph->GetIFieldLoweringInfo(mir); 260 uint16_t res; 261 if (!field_info.IsResolved() || field_info.IsVolatile()) { 262 // Volatile fields always get a new memory version; field id is irrelevant. 263 // Unresolved fields may be volatile, so handle them as such to be safe. 264 // Use result s_reg - will be unique. 265 res = LookupValue(kNoValue, mir->ssa_rep->defs[0], kNoValue, kNoValue); 266 } else { 267 uint16_t type = opcode - Instruction::IGET; 268 uint16_t field_id = GetFieldId(field_info); 269 if (IsNonAliasingIField(base, field_id, type)) { 270 res = LookupValue(kNonAliasingIFieldOp, base, field_id, type); 271 } else { 272 // Get the start version that accounts for aliasing with unresolved fields of the same type 273 // and make it unique for the field by including the field_id. 274 uint16_t start_version = LookupValue(kAliasingIFieldStartVersionOp, global_memory_version_, 275 unresolved_ifield_version_[type], field_id); 276 // Find the current version from the aliasing_ifield_version_map_. 277 uint16_t memory_version = start_version; 278 auto version_it = aliasing_ifield_version_map_.find(start_version); 279 if (version_it != aliasing_ifield_version_map_.end()) { 280 memory_version = version_it->second; 281 } else { 282 // Just use the start_version. 283 } 284 res = LookupValue(kAliasingIFieldOp, base, field_id, memory_version); 285 } 286 } 287 if (opcode == Instruction::IGET_WIDE) { 288 SetOperandValueWide(mir->ssa_rep->defs[0], res); 289 } else { 290 SetOperandValue(mir->ssa_rep->defs[0], res); 291 } 292 return res; 293} 294 295void LocalValueNumbering::HandleIPut(MIR* mir, uint16_t opcode) { 296 uint16_t type = opcode - Instruction::IPUT; 297 int base_reg = (opcode == Instruction::IPUT_WIDE) ? 2 : 1; 298 uint16_t base = GetOperandValue(mir->ssa_rep->uses[base_reg]); 299 HandleNullCheck(mir, base); 300 const MirFieldInfo& field_info = cu_->mir_graph->GetIFieldLoweringInfo(mir); 301 if (!field_info.IsResolved()) { 302 // Unresolved fields always alias with everything of the same type. 303 // Use mir->offset as modifier; without elaborate inlining, it will be unique. 304 unresolved_ifield_version_[type] = 305 LookupValue(kUnresolvedIFieldOp, kNoValue, kNoValue, mir->offset); 306 307 // Treat fields of escaped references of the same type as potentially modified. 308 NonAliasingIFieldKey key = { type, 0u, 0u }; // lowest possible key of this type. 309 auto it = non_aliasing_ifields_.lower_bound(key), end = non_aliasing_ifields_.end(); 310 while (it != end && it->type == type) { 311 it = non_aliasing_ifields_.erase(it); 312 } 313 } else if (field_info.IsVolatile()) { 314 // Nothing to do, resolved volatile fields always get a new memory version anyway and 315 // can't alias with resolved non-volatile fields. 316 } else { 317 uint16_t field_id = GetFieldId(field_info); 318 uint16_t value = (opcode == Instruction::IPUT_WIDE) 319 ? GetOperandValueWide(mir->ssa_rep->uses[0]) 320 : GetOperandValue(mir->ssa_rep->uses[0]); 321 if (IsNonAliasing(base)) { 322 StoreValue(kNonAliasingIFieldOp, base, field_id, type, value); 323 } else { 324 // Get the start version that accounts for aliasing with unresolved fields of the same type 325 // and make it unique for the field by including the field_id. 326 uint16_t start_version = LookupValue(kAliasingIFieldStartVersionOp, global_memory_version_, 327 unresolved_ifield_version_[type], field_id); 328 // Find the old version from the aliasing_ifield_version_map_. 329 uint16_t old_version = start_version; 330 auto version_it = aliasing_ifield_version_map_.find(start_version); 331 if (version_it != aliasing_ifield_version_map_.end()) { 332 old_version = version_it->second; 333 } 334 // Check if the field currently contains the value, making this a NOP. 335 if (HasValue(kAliasingIFieldOp, base, field_id, old_version, value)) { 336 // This IPUT can be eliminated, it stores the same value that's already in the field. 337 // TODO: Eliminate the IPUT. 338 return; 339 } 340 // Bump the version, adding to the chain started by start_version. 341 uint16_t memory_version = LookupValue(kAliasingIFieldBumpVersionOp, old_version, base, value); 342 // Update the aliasing_ifield_version_map_ so that HandleIGet() can get the memory_version 343 // without knowing the values used to build the chain. 344 aliasing_ifield_version_map_.Overwrite(start_version, memory_version); 345 StoreValue(kAliasingIFieldOp, base, field_id, memory_version, value); 346 347 // Clear non-aliasing fields for this field_id. 348 NonAliasingIFieldKey field_key = { type, field_id, 0u }; 349 auto it = non_aliasing_ifields_.lower_bound(field_key), end = non_aliasing_ifields_.end(); 350 while (it != end && it->field_id == field_id) { 351 DCHECK_EQ(type, it->type); 352 it = non_aliasing_ifields_.erase(it); 353 } 354 } 355 } 356} 357 358uint16_t LocalValueNumbering::HandleSGet(MIR* mir, uint16_t opcode) { 359 const MirFieldInfo& field_info = cu_->mir_graph->GetSFieldLoweringInfo(mir); 360 uint16_t res; 361 if (!field_info.IsResolved() || field_info.IsVolatile()) { 362 // Volatile fields always get a new memory version; field id is irrelevant. 363 // Unresolved fields may be volatile, so handle them as such to be safe. 364 // Use result s_reg - will be unique. 365 res = LookupValue(kNoValue, mir->ssa_rep->defs[0], kNoValue, kNoValue); 366 } else { 367 uint16_t field_id = GetFieldId(field_info); 368 // Resolved non-volatile static fields can alias with non-resolved fields of the same type, 369 // so we need to use unresolved_sfield_version_[type] in addition to global_memory_version_ 370 // to determine the version of the field. 371 uint16_t type = opcode - Instruction::SGET; 372 res = LookupValue(kResolvedSFieldOp, field_id, 373 unresolved_sfield_version_[type], global_memory_version_); 374 } 375 if (opcode == Instruction::SGET_WIDE) { 376 SetOperandValueWide(mir->ssa_rep->defs[0], res); 377 } else { 378 SetOperandValue(mir->ssa_rep->defs[0], res); 379 } 380 return res; 381} 382 383void LocalValueNumbering::HandleSPut(MIR* mir, uint16_t opcode) { 384 uint16_t type = opcode - Instruction::SPUT; 385 const MirFieldInfo& field_info = cu_->mir_graph->GetSFieldLoweringInfo(mir); 386 if (!field_info.IsResolved()) { 387 // Unresolved fields always alias with everything of the same type. 388 // Use mir->offset as modifier; without elaborate inlining, it will be unique. 389 unresolved_sfield_version_[type] = 390 LookupValue(kUnresolvedSFieldOp, kNoValue, kNoValue, mir->offset); 391 } else if (field_info.IsVolatile()) { 392 // Nothing to do, resolved volatile fields always get a new memory version anyway and 393 // can't alias with resolved non-volatile fields. 394 } else { 395 uint16_t field_id = GetFieldId(field_info); 396 uint16_t value = (opcode == Instruction::SPUT_WIDE) 397 ? GetOperandValueWide(mir->ssa_rep->uses[0]) 398 : GetOperandValue(mir->ssa_rep->uses[0]); 399 // Resolved non-volatile static fields can alias with non-resolved fields of the same type, 400 // so we need to use unresolved_sfield_version_[type] in addition to global_memory_version_ 401 // to determine the version of the field. 402 uint16_t type = opcode - Instruction::SGET; 403 StoreValue(kResolvedSFieldOp, field_id, 404 unresolved_sfield_version_[type], global_memory_version_, value); 405 } 406} 407 408uint16_t LocalValueNumbering::GetValueNumber(MIR* mir) { 409 uint16_t res = kNoValue; 410 uint16_t opcode = mir->dalvikInsn.opcode; 411 switch (opcode) { 412 case Instruction::NOP: 413 case Instruction::RETURN_VOID: 414 case Instruction::RETURN: 415 case Instruction::RETURN_OBJECT: 416 case Instruction::RETURN_WIDE: 417 case Instruction::MONITOR_ENTER: 418 case Instruction::MONITOR_EXIT: 419 case Instruction::GOTO: 420 case Instruction::GOTO_16: 421 case Instruction::GOTO_32: 422 case Instruction::CHECK_CAST: 423 case Instruction::THROW: 424 case Instruction::FILL_ARRAY_DATA: 425 case Instruction::PACKED_SWITCH: 426 case Instruction::SPARSE_SWITCH: 427 case Instruction::IF_EQ: 428 case Instruction::IF_NE: 429 case Instruction::IF_LT: 430 case Instruction::IF_GE: 431 case Instruction::IF_GT: 432 case Instruction::IF_LE: 433 case Instruction::IF_EQZ: 434 case Instruction::IF_NEZ: 435 case Instruction::IF_LTZ: 436 case Instruction::IF_GEZ: 437 case Instruction::IF_GTZ: 438 case Instruction::IF_LEZ: 439 case kMirOpFusedCmplFloat: 440 case kMirOpFusedCmpgFloat: 441 case kMirOpFusedCmplDouble: 442 case kMirOpFusedCmpgDouble: 443 case kMirOpFusedCmpLong: 444 // Nothing defined - take no action. 445 break; 446 447 case Instruction::FILLED_NEW_ARRAY: 448 case Instruction::FILLED_NEW_ARRAY_RANGE: 449 // Nothing defined but the result will be unique and non-null. 450 if (mir->next != nullptr && mir->next->dalvikInsn.opcode == Instruction::MOVE_RESULT_OBJECT) { 451 MarkNonAliasingNonNull(mir->next); 452 // TUNING: We could track value names stored in the array. 453 // The MOVE_RESULT_OBJECT will be processed next and we'll return the value name then. 454 } 455 // All args escaped (if references). 456 for (size_t i = 0u, count = mir->ssa_rep->num_uses; i != count; ++i) { 457 uint16_t reg = GetOperandValue(mir->ssa_rep->uses[i]); 458 HandleEscapingRef(reg); 459 } 460 break; 461 462 case Instruction::INVOKE_DIRECT: 463 case Instruction::INVOKE_DIRECT_RANGE: 464 case Instruction::INVOKE_VIRTUAL: 465 case Instruction::INVOKE_VIRTUAL_RANGE: 466 case Instruction::INVOKE_SUPER: 467 case Instruction::INVOKE_SUPER_RANGE: 468 case Instruction::INVOKE_INTERFACE: 469 case Instruction::INVOKE_INTERFACE_RANGE: { 470 // Nothing defined but handle the null check. 471 uint16_t reg = GetOperandValue(mir->ssa_rep->uses[0]); 472 HandleNullCheck(mir, reg); 473 } 474 // Intentional fall-through. 475 case Instruction::INVOKE_STATIC: 476 case Instruction::INVOKE_STATIC_RANGE: 477 if ((mir->optimization_flags & MIR_INLINED) == 0) { 478 // Use mir->offset as modifier; without elaborate inlining, it will be unique. 479 global_memory_version_ = LookupValue(kInvokeMemoryVersionBumpOp, 0u, 0u, mir->offset); 480 // Make ref args aliasing. 481 for (size_t i = 0u, count = mir->ssa_rep->num_uses; i != count; ++i) { 482 uint16_t reg = GetOperandValue(mir->ssa_rep->uses[i]); 483 non_aliasing_refs_.erase(reg); 484 } 485 // All fields of escaped references need to be treated as potentially modified. 486 non_aliasing_ifields_.clear(); 487 // Array elements may also have been modified via escaped array refs. 488 escaped_array_refs_.clear(); 489 } 490 break; 491 492 case Instruction::MOVE_RESULT: 493 case Instruction::MOVE_RESULT_OBJECT: 494 case Instruction::INSTANCE_OF: 495 // 1 result, treat as unique each time, use result s_reg - will be unique. 496 res = GetOperandValue(mir->ssa_rep->defs[0]); 497 SetOperandValue(mir->ssa_rep->defs[0], res); 498 break; 499 case Instruction::MOVE_EXCEPTION: 500 case Instruction::NEW_INSTANCE: 501 case Instruction::CONST_CLASS: 502 case Instruction::NEW_ARRAY: 503 // 1 result, treat as unique each time, use result s_reg - will be unique. 504 res = MarkNonAliasingNonNull(mir); 505 break; 506 case Instruction::CONST_STRING: 507 case Instruction::CONST_STRING_JUMBO: 508 // These strings are internalized, so assign value based on the string pool index. 509 res = LookupValue(Instruction::CONST_STRING, Low16Bits(mir->dalvikInsn.vB), 510 High16Bits(mir->dalvikInsn.vB), 0); 511 SetOperandValue(mir->ssa_rep->defs[0], res); 512 null_checked_.insert(res); // May already be there. 513 // NOTE: Hacking the contents of an internalized string via reflection is possible 514 // but the behavior is undefined. Therefore, we consider the string constant and 515 // the reference non-aliasing. 516 // TUNING: We could keep this property even if the reference "escapes". 517 non_aliasing_refs_.insert(res); // May already be there. 518 break; 519 case Instruction::MOVE_RESULT_WIDE: 520 // 1 wide result, treat as unique each time, use result s_reg - will be unique. 521 res = GetOperandValueWide(mir->ssa_rep->defs[0]); 522 SetOperandValueWide(mir->ssa_rep->defs[0], res); 523 break; 524 525 case kMirOpPhi: 526 /* 527 * Because we'll only see phi nodes at the beginning of an extended basic block, 528 * we can ignore them. Revisit if we shift to global value numbering. 529 */ 530 break; 531 532 case Instruction::MOVE: 533 case Instruction::MOVE_OBJECT: 534 case Instruction::MOVE_16: 535 case Instruction::MOVE_OBJECT_16: 536 case Instruction::MOVE_FROM16: 537 case Instruction::MOVE_OBJECT_FROM16: 538 case kMirOpCopy: 539 // Just copy value number of source to value number of result. 540 res = GetOperandValue(mir->ssa_rep->uses[0]); 541 SetOperandValue(mir->ssa_rep->defs[0], res); 542 break; 543 544 case Instruction::MOVE_WIDE: 545 case Instruction::MOVE_WIDE_16: 546 case Instruction::MOVE_WIDE_FROM16: 547 // Just copy value number of source to value number of result. 548 res = GetOperandValueWide(mir->ssa_rep->uses[0]); 549 SetOperandValueWide(mir->ssa_rep->defs[0], res); 550 break; 551 552 case Instruction::CONST: 553 case Instruction::CONST_4: 554 case Instruction::CONST_16: 555 res = LookupValue(Instruction::CONST, Low16Bits(mir->dalvikInsn.vB), 556 High16Bits(mir->dalvikInsn.vB), 0); 557 SetOperandValue(mir->ssa_rep->defs[0], res); 558 break; 559 560 case Instruction::CONST_HIGH16: 561 res = LookupValue(Instruction::CONST, 0, mir->dalvikInsn.vB, 0); 562 SetOperandValue(mir->ssa_rep->defs[0], res); 563 break; 564 565 case Instruction::CONST_WIDE_16: 566 case Instruction::CONST_WIDE_32: { 567 uint16_t low_res = LookupValue(Instruction::CONST, Low16Bits(mir->dalvikInsn.vB), 568 High16Bits(mir->dalvikInsn.vB >> 16), 1); 569 uint16_t high_res; 570 if (mir->dalvikInsn.vB & 0x80000000) { 571 high_res = LookupValue(Instruction::CONST, 0xffff, 0xffff, 2); 572 } else { 573 high_res = LookupValue(Instruction::CONST, 0, 0, 2); 574 } 575 res = LookupValue(Instruction::CONST, low_res, high_res, 3); 576 SetOperandValueWide(mir->ssa_rep->defs[0], res); 577 } 578 break; 579 580 case Instruction::CONST_WIDE: { 581 uint32_t low_word = Low32Bits(mir->dalvikInsn.vB_wide); 582 uint32_t high_word = High32Bits(mir->dalvikInsn.vB_wide); 583 uint16_t low_res = LookupValue(Instruction::CONST, Low16Bits(low_word), 584 High16Bits(low_word), 1); 585 uint16_t high_res = LookupValue(Instruction::CONST, Low16Bits(high_word), 586 High16Bits(high_word), 2); 587 res = LookupValue(Instruction::CONST, low_res, high_res, 3); 588 SetOperandValueWide(mir->ssa_rep->defs[0], res); 589 } 590 break; 591 592 case Instruction::CONST_WIDE_HIGH16: { 593 uint16_t low_res = LookupValue(Instruction::CONST, 0, 0, 1); 594 uint16_t high_res = LookupValue(Instruction::CONST, 0, Low16Bits(mir->dalvikInsn.vB), 2); 595 res = LookupValue(Instruction::CONST, low_res, high_res, 3); 596 SetOperandValueWide(mir->ssa_rep->defs[0], res); 597 } 598 break; 599 600 case Instruction::ARRAY_LENGTH: 601 case Instruction::NEG_INT: 602 case Instruction::NOT_INT: 603 case Instruction::NEG_FLOAT: 604 case Instruction::INT_TO_BYTE: 605 case Instruction::INT_TO_SHORT: 606 case Instruction::INT_TO_CHAR: 607 case Instruction::INT_TO_FLOAT: 608 case Instruction::FLOAT_TO_INT: { 609 // res = op + 1 operand 610 uint16_t operand1 = GetOperandValue(mir->ssa_rep->uses[0]); 611 res = LookupValue(opcode, operand1, kNoValue, kNoValue); 612 SetOperandValue(mir->ssa_rep->defs[0], res); 613 } 614 break; 615 616 case Instruction::LONG_TO_FLOAT: 617 case Instruction::LONG_TO_INT: 618 case Instruction::DOUBLE_TO_FLOAT: 619 case Instruction::DOUBLE_TO_INT: { 620 // res = op + 1 wide operand 621 uint16_t operand1 = GetOperandValueWide(mir->ssa_rep->uses[0]); 622 res = LookupValue(opcode, operand1, kNoValue, kNoValue); 623 SetOperandValue(mir->ssa_rep->defs[0], res); 624 } 625 break; 626 627 628 case Instruction::DOUBLE_TO_LONG: 629 case Instruction::LONG_TO_DOUBLE: 630 case Instruction::NEG_LONG: 631 case Instruction::NOT_LONG: 632 case Instruction::NEG_DOUBLE: { 633 // wide res = op + 1 wide operand 634 uint16_t operand1 = GetOperandValueWide(mir->ssa_rep->uses[0]); 635 res = LookupValue(opcode, operand1, kNoValue, kNoValue); 636 SetOperandValueWide(mir->ssa_rep->defs[0], res); 637 } 638 break; 639 640 case Instruction::FLOAT_TO_DOUBLE: 641 case Instruction::FLOAT_TO_LONG: 642 case Instruction::INT_TO_DOUBLE: 643 case Instruction::INT_TO_LONG: { 644 // wide res = op + 1 operand 645 uint16_t operand1 = GetOperandValue(mir->ssa_rep->uses[0]); 646 res = LookupValue(opcode, operand1, kNoValue, kNoValue); 647 SetOperandValueWide(mir->ssa_rep->defs[0], res); 648 } 649 break; 650 651 case Instruction::CMPL_DOUBLE: 652 case Instruction::CMPG_DOUBLE: 653 case Instruction::CMP_LONG: { 654 // res = op + 2 wide operands 655 uint16_t operand1 = GetOperandValueWide(mir->ssa_rep->uses[0]); 656 uint16_t operand2 = GetOperandValueWide(mir->ssa_rep->uses[2]); 657 res = LookupValue(opcode, operand1, operand2, kNoValue); 658 SetOperandValue(mir->ssa_rep->defs[0], res); 659 } 660 break; 661 662 case Instruction::CMPG_FLOAT: 663 case Instruction::CMPL_FLOAT: 664 case Instruction::ADD_INT: 665 case Instruction::ADD_INT_2ADDR: 666 case Instruction::MUL_INT: 667 case Instruction::MUL_INT_2ADDR: 668 case Instruction::AND_INT: 669 case Instruction::AND_INT_2ADDR: 670 case Instruction::OR_INT: 671 case Instruction::OR_INT_2ADDR: 672 case Instruction::XOR_INT: 673 case Instruction::XOR_INT_2ADDR: 674 case Instruction::SUB_INT: 675 case Instruction::SUB_INT_2ADDR: 676 case Instruction::DIV_INT: 677 case Instruction::DIV_INT_2ADDR: 678 case Instruction::REM_INT: 679 case Instruction::REM_INT_2ADDR: 680 case Instruction::SHL_INT: 681 case Instruction::SHL_INT_2ADDR: 682 case Instruction::SHR_INT: 683 case Instruction::SHR_INT_2ADDR: 684 case Instruction::USHR_INT: 685 case Instruction::USHR_INT_2ADDR: { 686 // res = op + 2 operands 687 uint16_t operand1 = GetOperandValue(mir->ssa_rep->uses[0]); 688 uint16_t operand2 = GetOperandValue(mir->ssa_rep->uses[1]); 689 res = LookupValue(opcode, operand1, operand2, kNoValue); 690 SetOperandValue(mir->ssa_rep->defs[0], res); 691 } 692 break; 693 694 case Instruction::ADD_LONG: 695 case Instruction::SUB_LONG: 696 case Instruction::MUL_LONG: 697 case Instruction::DIV_LONG: 698 case Instruction::REM_LONG: 699 case Instruction::AND_LONG: 700 case Instruction::OR_LONG: 701 case Instruction::XOR_LONG: 702 case Instruction::ADD_LONG_2ADDR: 703 case Instruction::SUB_LONG_2ADDR: 704 case Instruction::MUL_LONG_2ADDR: 705 case Instruction::DIV_LONG_2ADDR: 706 case Instruction::REM_LONG_2ADDR: 707 case Instruction::AND_LONG_2ADDR: 708 case Instruction::OR_LONG_2ADDR: 709 case Instruction::XOR_LONG_2ADDR: 710 case Instruction::ADD_DOUBLE: 711 case Instruction::SUB_DOUBLE: 712 case Instruction::MUL_DOUBLE: 713 case Instruction::DIV_DOUBLE: 714 case Instruction::REM_DOUBLE: 715 case Instruction::ADD_DOUBLE_2ADDR: 716 case Instruction::SUB_DOUBLE_2ADDR: 717 case Instruction::MUL_DOUBLE_2ADDR: 718 case Instruction::DIV_DOUBLE_2ADDR: 719 case Instruction::REM_DOUBLE_2ADDR: { 720 // wide res = op + 2 wide operands 721 uint16_t operand1 = GetOperandValueWide(mir->ssa_rep->uses[0]); 722 uint16_t operand2 = GetOperandValueWide(mir->ssa_rep->uses[2]); 723 res = LookupValue(opcode, operand1, operand2, kNoValue); 724 SetOperandValueWide(mir->ssa_rep->defs[0], res); 725 } 726 break; 727 728 case Instruction::SHL_LONG: 729 case Instruction::SHR_LONG: 730 case Instruction::USHR_LONG: 731 case Instruction::SHL_LONG_2ADDR: 732 case Instruction::SHR_LONG_2ADDR: 733 case Instruction::USHR_LONG_2ADDR: { 734 // wide res = op + 1 wide operand + 1 operand 735 uint16_t operand1 = GetOperandValueWide(mir->ssa_rep->uses[0]); 736 uint16_t operand2 = GetOperandValue(mir->ssa_rep->uses[2]); 737 res = LookupValue(opcode, operand1, operand2, kNoValue); 738 SetOperandValueWide(mir->ssa_rep->defs[0], res); 739 } 740 break; 741 742 case Instruction::ADD_FLOAT: 743 case Instruction::SUB_FLOAT: 744 case Instruction::MUL_FLOAT: 745 case Instruction::DIV_FLOAT: 746 case Instruction::REM_FLOAT: 747 case Instruction::ADD_FLOAT_2ADDR: 748 case Instruction::SUB_FLOAT_2ADDR: 749 case Instruction::MUL_FLOAT_2ADDR: 750 case Instruction::DIV_FLOAT_2ADDR: 751 case Instruction::REM_FLOAT_2ADDR: { 752 // res = op + 2 operands 753 uint16_t operand1 = GetOperandValue(mir->ssa_rep->uses[0]); 754 uint16_t operand2 = GetOperandValue(mir->ssa_rep->uses[1]); 755 res = LookupValue(opcode, operand1, operand2, kNoValue); 756 SetOperandValue(mir->ssa_rep->defs[0], res); 757 } 758 break; 759 760 case Instruction::RSUB_INT: 761 case Instruction::ADD_INT_LIT16: 762 case Instruction::MUL_INT_LIT16: 763 case Instruction::DIV_INT_LIT16: 764 case Instruction::REM_INT_LIT16: 765 case Instruction::AND_INT_LIT16: 766 case Instruction::OR_INT_LIT16: 767 case Instruction::XOR_INT_LIT16: 768 case Instruction::ADD_INT_LIT8: 769 case Instruction::RSUB_INT_LIT8: 770 case Instruction::MUL_INT_LIT8: 771 case Instruction::DIV_INT_LIT8: 772 case Instruction::REM_INT_LIT8: 773 case Instruction::AND_INT_LIT8: 774 case Instruction::OR_INT_LIT8: 775 case Instruction::XOR_INT_LIT8: 776 case Instruction::SHL_INT_LIT8: 777 case Instruction::SHR_INT_LIT8: 778 case Instruction::USHR_INT_LIT8: { 779 // Same as res = op + 2 operands, except use vC as operand 2 780 uint16_t operand1 = GetOperandValue(mir->ssa_rep->uses[0]); 781 uint16_t operand2 = LookupValue(Instruction::CONST, mir->dalvikInsn.vC, 0, 0); 782 res = LookupValue(opcode, operand1, operand2, kNoValue); 783 SetOperandValue(mir->ssa_rep->defs[0], res); 784 } 785 break; 786 787 case Instruction::AGET_OBJECT: 788 case Instruction::AGET: 789 case Instruction::AGET_WIDE: 790 case Instruction::AGET_BOOLEAN: 791 case Instruction::AGET_BYTE: 792 case Instruction::AGET_CHAR: 793 case Instruction::AGET_SHORT: 794 res = HandleAGet(mir, opcode); 795 break; 796 797 case Instruction::APUT_OBJECT: 798 HandlePutObject(mir); 799 // Intentional fall-through. 800 case Instruction::APUT: 801 case Instruction::APUT_WIDE: 802 case Instruction::APUT_BYTE: 803 case Instruction::APUT_BOOLEAN: 804 case Instruction::APUT_SHORT: 805 case Instruction::APUT_CHAR: 806 HandleAPut(mir, opcode); 807 break; 808 809 case Instruction::IGET_OBJECT: 810 case Instruction::IGET: 811 case Instruction::IGET_WIDE: 812 case Instruction::IGET_BOOLEAN: 813 case Instruction::IGET_BYTE: 814 case Instruction::IGET_CHAR: 815 case Instruction::IGET_SHORT: 816 res = HandleIGet(mir, opcode); 817 break; 818 819 case Instruction::IPUT_OBJECT: 820 HandlePutObject(mir); 821 // Intentional fall-through. 822 case Instruction::IPUT: 823 case Instruction::IPUT_WIDE: 824 case Instruction::IPUT_BOOLEAN: 825 case Instruction::IPUT_BYTE: 826 case Instruction::IPUT_CHAR: 827 case Instruction::IPUT_SHORT: 828 HandleIPut(mir, opcode); 829 break; 830 831 case Instruction::SGET_OBJECT: 832 case Instruction::SGET: 833 case Instruction::SGET_WIDE: 834 case Instruction::SGET_BOOLEAN: 835 case Instruction::SGET_BYTE: 836 case Instruction::SGET_CHAR: 837 case Instruction::SGET_SHORT: 838 res = HandleSGet(mir, opcode); 839 break; 840 841 case Instruction::SPUT_OBJECT: 842 HandlePutObject(mir); 843 // Intentional fall-through. 844 case Instruction::SPUT: 845 case Instruction::SPUT_WIDE: 846 case Instruction::SPUT_BOOLEAN: 847 case Instruction::SPUT_BYTE: 848 case Instruction::SPUT_CHAR: 849 case Instruction::SPUT_SHORT: 850 HandleSPut(mir, opcode); 851 break; 852 } 853 return res; 854} 855 856} // namespace art 857