local_value_numbering.cc revision 55fff044d3a4f7196098e25bab1dad106d9b54a2
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 "global_value_numbering.h" 20#include "mir_field_info.h" 21#include "mir_graph.h" 22 23namespace art { 24 25namespace { // anonymous namespace 26 27// Operations used for value map keys instead of actual opcode. 28static constexpr uint16_t kInvokeMemoryVersionBumpOp = Instruction::INVOKE_VIRTUAL; 29static constexpr uint16_t kUnresolvedSFieldOp = Instruction::SGET; 30static constexpr uint16_t kResolvedSFieldOp = Instruction::SGET_WIDE; 31static constexpr uint16_t kUnresolvedIFieldOp = Instruction::IGET; 32static constexpr uint16_t kNonAliasingIFieldLocOp = Instruction::IGET_WIDE; 33static constexpr uint16_t kNonAliasingIFieldInitialOp = Instruction::IGET_OBJECT; 34static constexpr uint16_t kAliasingIFieldOp = Instruction::IGET_BOOLEAN; 35static constexpr uint16_t kAliasingIFieldStartVersionOp = Instruction::IGET_BYTE; 36static constexpr uint16_t kAliasingIFieldBumpVersionOp = Instruction::IGET_CHAR; 37static constexpr uint16_t kNonAliasingArrayOp = Instruction::AGET; 38static constexpr uint16_t kNonAliasingArrayStartVersionOp = Instruction::AGET_WIDE; 39static constexpr uint16_t kNonAliasingArrayBumpVersionOp = Instruction::AGET_OBJECT; 40static constexpr uint16_t kAliasingArrayOp = Instruction::AGET_BOOLEAN; 41static constexpr uint16_t kAliasingArrayStartVersionOp = Instruction::AGET_BYTE; 42static constexpr uint16_t kAliasingArrayBumpVersionOp = Instruction::AGET_CHAR; 43static constexpr uint16_t kMergeBlockMemoryVersionBumpOp = Instruction::INVOKE_VIRTUAL_RANGE; 44static constexpr uint16_t kMergeBlockAliasingIFieldVersionBumpOp = Instruction::IPUT; 45static constexpr uint16_t kMergeBlockAliasingIFieldMergeLocationOp = Instruction::IPUT_WIDE; 46static constexpr uint16_t kMergeBlockNonAliasingArrayVersionBumpOp = Instruction::APUT; 47static constexpr uint16_t kMergeBlockNonAliasingArrayMergeLocationOp = Instruction::APUT_WIDE; 48static constexpr uint16_t kMergeBlockAliasingArrayVersionBumpOp = Instruction::APUT_OBJECT; 49static constexpr uint16_t kMergeBlockAliasingArrayMergeLocationOp = Instruction::APUT_BOOLEAN; 50static constexpr uint16_t kMergeBlockNonAliasingIFieldVersionBumpOp = Instruction::APUT_BYTE; 51static constexpr uint16_t kMergeBlockSFieldVersionBumpOp = Instruction::APUT_CHAR; 52 53} // anonymous namespace 54 55class LocalValueNumbering::AliasingIFieldVersions { 56 public: 57 static uint16_t StartMemoryVersion(GlobalValueNumbering* gvn, const LocalValueNumbering* lvn, 58 uint16_t field_id) { 59 uint16_t type = gvn->GetFieldType(field_id); 60 return gvn->LookupValue(kAliasingIFieldStartVersionOp, field_id, 61 lvn->global_memory_version_, lvn->unresolved_ifield_version_[type]); 62 } 63 64 static uint16_t BumpMemoryVersion(GlobalValueNumbering* gvn, uint16_t old_version, 65 uint16_t store_ref_set_id, uint16_t stored_value) { 66 return gvn->LookupValue(kAliasingIFieldBumpVersionOp, old_version, 67 store_ref_set_id, stored_value); 68 } 69 70 static uint16_t LookupGlobalValue(GlobalValueNumbering* gvn, 71 uint16_t field_id, uint16_t base, uint16_t memory_version) { 72 return gvn->LookupValue(kAliasingIFieldOp, field_id, base, memory_version); 73 } 74 75 static uint16_t LookupMergeValue(GlobalValueNumbering* gvn, const LocalValueNumbering* lvn, 76 uint16_t field_id, uint16_t base) { 77 // If the base/field_id is non-aliasing in lvn, use the non-aliasing value. 78 uint16_t type = gvn->GetFieldType(field_id); 79 if (lvn->IsNonAliasingIField(base, field_id, type)) { 80 uint16_t loc = gvn->LookupValue(kNonAliasingIFieldLocOp, base, field_id, type); 81 auto lb = lvn->non_aliasing_ifield_value_map_.find(loc); 82 return (lb != lvn->non_aliasing_ifield_value_map_.end()) 83 ? lb->second 84 : gvn->LookupValue(kNonAliasingIFieldInitialOp, loc, kNoValue, kNoValue); 85 } 86 return AliasingValuesMergeGet<AliasingIFieldVersions>( 87 gvn, lvn, &lvn->aliasing_ifield_value_map_, field_id, base); 88 } 89 90 static bool HasNewBaseVersion(GlobalValueNumbering* gvn, const LocalValueNumbering* lvn, 91 uint16_t field_id) { 92 uint16_t type = gvn->GetFieldType(field_id); 93 return lvn->unresolved_ifield_version_[type] == lvn->merge_new_memory_version_ || 94 lvn->global_memory_version_ == lvn->merge_new_memory_version_; 95 } 96 97 static uint16_t LookupMergeBlockValue(GlobalValueNumbering* gvn, uint16_t lvn_id, 98 uint16_t field_id) { 99 return gvn->LookupValue(kMergeBlockAliasingIFieldVersionBumpOp, field_id, kNoValue, lvn_id); 100 } 101 102 static uint16_t LookupMergeLocationValue(GlobalValueNumbering* gvn, uint16_t lvn_id, 103 uint16_t field_id, uint16_t base) { 104 return gvn->LookupValue(kMergeBlockAliasingIFieldMergeLocationOp, field_id, base, lvn_id); 105 } 106}; 107 108class LocalValueNumbering::NonAliasingArrayVersions { 109 public: 110 static uint16_t StartMemoryVersion(GlobalValueNumbering* gvn, const LocalValueNumbering* lvn, 111 uint16_t array) { 112 return gvn->LookupValue(kNonAliasingArrayStartVersionOp, array, kNoValue, kNoValue); 113 } 114 115 static uint16_t BumpMemoryVersion(GlobalValueNumbering* gvn, uint16_t old_version, 116 uint16_t store_ref_set_id, uint16_t stored_value) { 117 return gvn->LookupValue(kNonAliasingArrayBumpVersionOp, old_version, 118 store_ref_set_id, stored_value); 119 } 120 121 static uint16_t LookupGlobalValue(GlobalValueNumbering* gvn, 122 uint16_t array, uint16_t index, uint16_t memory_version) { 123 return gvn->LookupValue(kNonAliasingArrayOp, array, index, memory_version); 124 } 125 126 static uint16_t LookupMergeValue(GlobalValueNumbering* gvn, const LocalValueNumbering* lvn, 127 uint16_t array, uint16_t index) { 128 return AliasingValuesMergeGet<NonAliasingArrayVersions>( 129 gvn, lvn, &lvn->non_aliasing_array_value_map_, array, index); 130 } 131 132 static bool HasNewBaseVersion(GlobalValueNumbering* gvn, const LocalValueNumbering* lvn, 133 uint16_t array) { 134 return false; // Not affected by global_memory_version_. 135 } 136 137 static uint16_t LookupMergeBlockValue(GlobalValueNumbering* gvn, uint16_t lvn_id, 138 uint16_t array) { 139 return gvn->LookupValue(kMergeBlockNonAliasingArrayVersionBumpOp, array, kNoValue, lvn_id); 140 } 141 142 static uint16_t LookupMergeLocationValue(GlobalValueNumbering* gvn, uint16_t lvn_id, 143 uint16_t array, uint16_t index) { 144 return gvn->LookupValue(kMergeBlockNonAliasingArrayMergeLocationOp, array, index, lvn_id); 145 } 146}; 147 148class LocalValueNumbering::AliasingArrayVersions { 149 public: 150 static uint16_t StartMemoryVersion(GlobalValueNumbering* gvn, const LocalValueNumbering* lvn, 151 uint16_t type) { 152 return gvn->LookupValue(kAliasingArrayStartVersionOp, type, lvn->global_memory_version_, 153 kNoValue); 154 } 155 156 static uint16_t BumpMemoryVersion(GlobalValueNumbering* gvn, uint16_t old_version, 157 uint16_t store_ref_set_id, uint16_t stored_value) { 158 return gvn->LookupValue(kAliasingArrayBumpVersionOp, old_version, 159 store_ref_set_id, stored_value); 160 } 161 162 static uint16_t LookupGlobalValue(GlobalValueNumbering* gvn, 163 uint16_t type, uint16_t location, uint16_t memory_version) { 164 return gvn->LookupValue(kAliasingArrayOp, type, location, memory_version); 165 } 166 167 static uint16_t LookupMergeValue(GlobalValueNumbering* gvn, const LocalValueNumbering* lvn, 168 uint16_t type, uint16_t location) { 169 // If the location is non-aliasing in lvn, use the non-aliasing value. 170 uint16_t array = gvn->GetArrayLocationBase(location); 171 if (lvn->IsNonAliasingArray(array, type)) { 172 uint16_t index = gvn->GetArrayLocationIndex(location); 173 return NonAliasingArrayVersions::LookupMergeValue(gvn, lvn, array, index); 174 } 175 return AliasingValuesMergeGet<AliasingArrayVersions>( 176 gvn, lvn, &lvn->aliasing_array_value_map_, type, location); 177 } 178 179 static bool HasNewBaseVersion(GlobalValueNumbering* gvn, const LocalValueNumbering* lvn, 180 uint16_t type) { 181 return lvn->global_memory_version_ == lvn->merge_new_memory_version_; 182 } 183 184 static uint16_t LookupMergeBlockValue(GlobalValueNumbering* gvn, uint16_t lvn_id, 185 uint16_t type) { 186 return gvn->LookupValue(kMergeBlockAliasingArrayVersionBumpOp, type, kNoValue, lvn_id); 187 } 188 189 static uint16_t LookupMergeLocationValue(GlobalValueNumbering* gvn, uint16_t lvn_id, 190 uint16_t type, uint16_t location) { 191 return gvn->LookupValue(kMergeBlockAliasingArrayMergeLocationOp, type, location, lvn_id); 192 } 193}; 194 195template <typename Map> 196LocalValueNumbering::AliasingValues* LocalValueNumbering::GetAliasingValues( 197 Map* map, const typename Map::key_type& key) { 198 auto lb = map->lower_bound(key); 199 if (lb == map->end() || map->key_comp()(key, lb->first)) { 200 map->PutBefore(lb, key, AliasingValues(gvn_->allocator_)); 201 // The new entry was inserted before lb. 202 DCHECK(lb != map->begin()); 203 --lb; 204 DCHECK(!map->key_comp()(lb->first, key) && !map->key_comp()(key, lb->first)); 205 } 206 return &lb->second; 207} 208 209template <typename Versions, typename KeyType> 210void LocalValueNumbering::UpdateAliasingValuesLoadVersion(const KeyType& key, 211 AliasingValues* values) { 212 if (values->last_load_memory_version == kNoValue) { 213 // Get the start version that accounts for aliasing with unresolved fields of the same 214 // type and make it unique for the field by including the field_id. 215 uint16_t memory_version = values->memory_version_before_stores; 216 if (memory_version == kNoValue) { 217 memory_version = Versions::StartMemoryVersion(gvn_, this, key); 218 } 219 if (!values->store_loc_set.empty()) { 220 uint16_t ref_set_id = gvn_->GetRefSetId(values->store_loc_set); 221 memory_version = Versions::BumpMemoryVersion(gvn_, memory_version, ref_set_id, 222 values->last_stored_value); 223 } 224 values->last_load_memory_version = memory_version; 225 } 226} 227 228template <typename Versions, typename Map> 229uint16_t LocalValueNumbering::AliasingValuesMergeGet(GlobalValueNumbering* gvn, 230 const LocalValueNumbering* lvn, 231 Map* map, const typename Map::key_type& key, 232 uint16_t location) { 233 // Retrieve the value name that we would get from 234 // const_cast<LocalValueNumbering*>(lvn)->HandleAliasingValueGet(map. key, location) 235 // but don't modify the map. 236 uint16_t value_name; 237 auto it = map->find(key); 238 if (it == map->end()) { 239 uint16_t start_version = Versions::StartMemoryVersion(gvn, lvn, key); 240 value_name = Versions::LookupGlobalValue(gvn, key, location, start_version); 241 } else if (it->second.store_loc_set.count(location) != 0u) { 242 value_name = it->second.last_stored_value; 243 } else { 244 auto load_it = it->second.load_value_map.find(location); 245 if (load_it != it->second.load_value_map.end()) { 246 value_name = load_it->second; 247 } else { 248 value_name = Versions::LookupGlobalValue(gvn, key, location, it->second.last_load_memory_version); 249 } 250 } 251 return value_name; 252} 253 254template <typename Versions, typename Map> 255uint16_t LocalValueNumbering::HandleAliasingValuesGet(Map* map, const typename Map::key_type& key, 256 uint16_t location) { 257 // Retrieve the value name for IGET/SGET/AGET, update the map with new value if any. 258 uint16_t res; 259 AliasingValues* values = GetAliasingValues(map, key); 260 if (values->store_loc_set.count(location) != 0u) { 261 res = values->last_stored_value; 262 } else { 263 UpdateAliasingValuesLoadVersion<Versions>(key, values); 264 auto lb = values->load_value_map.lower_bound(location); 265 if (lb != values->load_value_map.end() && lb->first == location) { 266 res = lb->second; 267 } else { 268 res = Versions::LookupGlobalValue(gvn_, key, location, values->last_load_memory_version); 269 values->load_value_map.PutBefore(lb, location, res); 270 } 271 } 272 return res; 273} 274 275template <typename Versions, typename Map> 276bool LocalValueNumbering::HandleAliasingValuesPut(Map* map, const typename Map::key_type& key, 277 uint16_t location, uint16_t value) { 278 AliasingValues* values = GetAliasingValues(map, key); 279 auto load_values_it = values->load_value_map.find(location); 280 if (load_values_it != values->load_value_map.end() && load_values_it->second == value) { 281 // This insn can be eliminated, it stores the same value that's already in the field. 282 return false; 283 } 284 if (value == values->last_stored_value) { 285 auto store_loc_lb = values->store_loc_set.lower_bound(location); 286 if (store_loc_lb != values->store_loc_set.end() && *store_loc_lb == location) { 287 // This insn can be eliminated, it stores the same value that's already in the field. 288 return false; 289 } 290 values->store_loc_set.emplace_hint(store_loc_lb, location); 291 } else { 292 UpdateAliasingValuesLoadVersion<Versions>(key, values); 293 values->memory_version_before_stores = values->last_load_memory_version; 294 values->last_stored_value = value; 295 values->store_loc_set.clear(); 296 values->store_loc_set.insert(location); 297 } 298 // Clear the last load memory version and remove all potentially overwritten values. 299 values->last_load_memory_version = kNoValue; 300 auto it = values->load_value_map.begin(), end = values->load_value_map.end(); 301 while (it != end) { 302 if (it->second == value) { 303 ++it; 304 } else { 305 it = values->load_value_map.erase(it); 306 } 307 } 308 return true; 309} 310 311LocalValueNumbering::LocalValueNumbering(GlobalValueNumbering* gvn, uint16_t id) 312 : gvn_(gvn), 313 id_(id), 314 sreg_value_map_(std::less<uint16_t>(), gvn->Allocator()->Adapter()), 315 sreg_wide_value_map_(std::less<uint16_t>(), gvn->Allocator()->Adapter()), 316 sfield_value_map_(std::less<uint16_t>(), gvn->Allocator()->Adapter()), 317 non_aliasing_ifield_value_map_(std::less<uint16_t>(), gvn->Allocator()->Adapter()), 318 aliasing_ifield_value_map_(std::less<uint16_t>(), gvn->Allocator()->Adapter()), 319 non_aliasing_array_value_map_(std::less<uint16_t>(), gvn->Allocator()->Adapter()), 320 aliasing_array_value_map_(std::less<uint16_t>(), gvn->Allocator()->Adapter()), 321 global_memory_version_(0u), 322 non_aliasing_refs_(std::less<uint16_t>(), gvn->Allocator()->Adapter()), 323 escaped_refs_(std::less<uint16_t>(), gvn->Allocator()->Adapter()), 324 escaped_ifield_clobber_set_(EscapedIFieldClobberKeyComparator(), gvn->Allocator()->Adapter()), 325 escaped_array_clobber_set_(EscapedArrayClobberKeyComparator(), gvn->Allocator()->Adapter()), 326 range_checked_(RangeCheckKeyComparator() , gvn->Allocator()->Adapter()), 327 null_checked_(std::less<uint16_t>(), gvn->Allocator()->Adapter()), 328 merge_names_(gvn->Allocator()->Adapter()), 329 merge_map_(std::less<ScopedArenaVector<BasicBlockId>>(), gvn->Allocator()->Adapter()), 330 merge_new_memory_version_(kNoValue) { 331 std::fill_n(unresolved_sfield_version_, kFieldTypeCount, 0u); 332 std::fill_n(unresolved_ifield_version_, kFieldTypeCount, 0u); 333} 334 335bool LocalValueNumbering::Equals(const LocalValueNumbering& other) const { 336 DCHECK(gvn_ == other.gvn_); 337 // Compare the maps/sets and memory versions. 338 return sreg_value_map_ == other.sreg_value_map_ && 339 sreg_wide_value_map_ == other.sreg_wide_value_map_ && 340 sfield_value_map_ == other.sfield_value_map_ && 341 non_aliasing_ifield_value_map_ == other.non_aliasing_ifield_value_map_ && 342 aliasing_ifield_value_map_ == other.aliasing_ifield_value_map_ && 343 non_aliasing_array_value_map_ == other.non_aliasing_array_value_map_ && 344 aliasing_array_value_map_ == other.aliasing_array_value_map_ && 345 SameMemoryVersion(other) && 346 non_aliasing_refs_ == other.non_aliasing_refs_ && 347 escaped_refs_ == other.escaped_refs_ && 348 escaped_ifield_clobber_set_ == other.escaped_ifield_clobber_set_ && 349 escaped_array_clobber_set_ == other.escaped_array_clobber_set_ && 350 range_checked_ == other.range_checked_ && 351 null_checked_ == other.null_checked_; 352} 353 354void LocalValueNumbering::MergeOne(const LocalValueNumbering& other, MergeType merge_type) { 355 sreg_value_map_ = other.sreg_value_map_; 356 sreg_wide_value_map_ = other.sreg_wide_value_map_; 357 358 if (merge_type == kReturnMerge) { 359 // RETURN or PHI+RETURN. We need only sreg value maps. 360 return; 361 } 362 363 non_aliasing_ifield_value_map_ = other.non_aliasing_ifield_value_map_; 364 non_aliasing_array_value_map_ = other.non_aliasing_array_value_map_; 365 non_aliasing_refs_ = other.non_aliasing_refs_; 366 range_checked_ = other.range_checked_; 367 null_checked_ = other.null_checked_; 368 369 if (merge_type == kCatchMerge) { 370 // Memory is clobbered. Use new memory version and don't merge aliasing locations. 371 global_memory_version_ = NewMemoryVersion(&merge_new_memory_version_); 372 std::fill_n(unresolved_sfield_version_, kFieldTypeCount, global_memory_version_); 373 std::fill_n(unresolved_ifield_version_, kFieldTypeCount, global_memory_version_); 374 PruneNonAliasingRefsForCatch(); 375 return; 376 } 377 378 DCHECK(merge_type == kNormalMerge); 379 global_memory_version_ = other.global_memory_version_; 380 std::copy_n(other.unresolved_ifield_version_, kFieldTypeCount, unresolved_ifield_version_); 381 std::copy_n(other.unresolved_sfield_version_, kFieldTypeCount, unresolved_sfield_version_); 382 sfield_value_map_ = other.sfield_value_map_; 383 aliasing_ifield_value_map_ = other.aliasing_ifield_value_map_; 384 aliasing_array_value_map_ = other.aliasing_array_value_map_; 385 escaped_refs_ = other.escaped_refs_; 386 escaped_ifield_clobber_set_ = other.escaped_ifield_clobber_set_; 387 escaped_array_clobber_set_ = other.escaped_array_clobber_set_; 388} 389 390bool LocalValueNumbering::SameMemoryVersion(const LocalValueNumbering& other) const { 391 return 392 global_memory_version_ == other.global_memory_version_ && 393 std::equal(unresolved_ifield_version_, unresolved_ifield_version_ + kFieldTypeCount, 394 other.unresolved_ifield_version_) && 395 std::equal(unresolved_sfield_version_, unresolved_sfield_version_ + kFieldTypeCount, 396 other.unresolved_sfield_version_); 397} 398 399uint16_t LocalValueNumbering::NewMemoryVersion(uint16_t* new_version) { 400 if (*new_version == kNoValue) { 401 *new_version = gvn_->LookupValue(kMergeBlockMemoryVersionBumpOp, 0u, 0u, id_); 402 } 403 return *new_version; 404} 405 406void LocalValueNumbering::MergeMemoryVersions(bool clobbered_catch) { 407 DCHECK_GE(gvn_->merge_lvns_.size(), 2u); 408 const LocalValueNumbering* cmp = gvn_->merge_lvns_[0]; 409 // Check if the global version has changed. 410 bool new_global_version = clobbered_catch; 411 if (!new_global_version) { 412 for (const LocalValueNumbering* lvn : gvn_->merge_lvns_) { 413 if (lvn->global_memory_version_ != cmp->global_memory_version_) { 414 // Use a new version for everything. 415 new_global_version = true; 416 break; 417 } 418 } 419 } 420 if (new_global_version) { 421 global_memory_version_ = NewMemoryVersion(&merge_new_memory_version_); 422 std::fill_n(unresolved_sfield_version_, kFieldTypeCount, merge_new_memory_version_); 423 std::fill_n(unresolved_ifield_version_, kFieldTypeCount, merge_new_memory_version_); 424 } else { 425 // Initialize with a copy of memory versions from the comparison LVN. 426 global_memory_version_ = cmp->global_memory_version_; 427 std::copy_n(cmp->unresolved_ifield_version_, kFieldTypeCount, unresolved_ifield_version_); 428 std::copy_n(cmp->unresolved_sfield_version_, kFieldTypeCount, unresolved_sfield_version_); 429 for (const LocalValueNumbering* lvn : gvn_->merge_lvns_) { 430 if (lvn == cmp) { 431 continue; 432 } 433 for (size_t i = 0; i != kFieldTypeCount; ++i) { 434 if (lvn->unresolved_ifield_version_[i] != cmp->unresolved_ifield_version_[i]) { 435 unresolved_ifield_version_[i] = NewMemoryVersion(&merge_new_memory_version_); 436 } 437 if (lvn->unresolved_sfield_version_[i] != cmp->unresolved_sfield_version_[i]) { 438 unresolved_sfield_version_[i] = NewMemoryVersion(&merge_new_memory_version_); 439 } 440 } 441 } 442 } 443} 444 445void LocalValueNumbering::PruneNonAliasingRefsForCatch() { 446 for (const LocalValueNumbering* lvn : gvn_->merge_lvns_) { 447 const BasicBlock* bb = gvn_->GetBasicBlock(lvn->Id()); 448 if (UNLIKELY(bb->taken == id_) || UNLIKELY(bb->fall_through == id_)) { 449 // Non-exceptional path to a catch handler means that the catch block was actually 450 // empty and all exceptional paths lead to the shared path after that empty block. 451 continue; 452 } 453 DCHECK_EQ(bb->taken, kNullBlock); 454 DCHECK_NE(bb->fall_through, kNullBlock); 455 const BasicBlock* fall_through_bb = gvn_->GetBasicBlock(bb->fall_through); 456 const MIR* mir = fall_through_bb->first_mir_insn; 457 DCHECK(mir != nullptr); 458 // Only INVOKEs can leak and clobber non-aliasing references if they throw. 459 if ((Instruction::FlagsOf(mir->dalvikInsn.opcode) & Instruction::kInvoke) != 0) { 460 for (uint16_t i = 0u; i != mir->ssa_rep->num_uses; ++i) { 461 uint16_t value_name = lvn->GetOperandValue(mir->ssa_rep->uses[i]); 462 non_aliasing_refs_.erase(value_name); 463 } 464 } 465 } 466} 467 468 469template <typename Set, Set LocalValueNumbering::* set_ptr> 470void LocalValueNumbering::IntersectSets() { 471 DCHECK_GE(gvn_->merge_lvns_.size(), 2u); 472 473 // Find the LVN with the least entries in the set. 474 const LocalValueNumbering* least_entries_lvn = gvn_->merge_lvns_[0]; 475 for (const LocalValueNumbering* lvn : gvn_->merge_lvns_) { 476 if ((lvn->*set_ptr).size() < (least_entries_lvn->*set_ptr).size()) { 477 least_entries_lvn = lvn; 478 } 479 } 480 481 // For each key check if it's in all the LVNs. 482 for (const auto& key : least_entries_lvn->*set_ptr) { 483 bool checked = true; 484 for (const LocalValueNumbering* lvn : gvn_->merge_lvns_) { 485 if (lvn != least_entries_lvn && (lvn->*set_ptr).count(key) == 0u) { 486 checked = false; 487 break; 488 } 489 } 490 if (checked) { 491 (this->*set_ptr).emplace_hint((this->*set_ptr).end(), key); 492 } 493 } 494} 495 496template <typename Map, Map LocalValueNumbering::* map_ptr> 497void LocalValueNumbering::IntersectMaps() { 498 DCHECK_GE(gvn_->merge_lvns_.size(), 2u); 499 500 // Find the LVN with the least entries in the set. 501 const LocalValueNumbering* least_entries_lvn = gvn_->merge_lvns_[0]; 502 for (const LocalValueNumbering* lvn : gvn_->merge_lvns_) { 503 if ((lvn->*map_ptr).size() < (least_entries_lvn->*map_ptr).size()) { 504 least_entries_lvn = lvn; 505 } 506 } 507 508 // For each key check if it's in all the LVNs. 509 for (const auto& entry : least_entries_lvn->*map_ptr) { 510 bool checked = true; 511 for (const LocalValueNumbering* lvn : gvn_->merge_lvns_) { 512 if (lvn != least_entries_lvn) { 513 auto it = (lvn->*map_ptr).find(entry.first); 514 if (it == (lvn->*map_ptr).end() || !(it->second == entry.second)) { 515 checked = false; 516 break; 517 } 518 } 519 } 520 if (checked) { 521 (this->*map_ptr).PutBefore((this->*map_ptr).end(), entry.first, entry.second); 522 } 523 } 524} 525 526// Intersect maps as sets. The value type must be equality-comparable. 527template <typename Map> 528void LocalValueNumbering::InPlaceIntersectMaps(Map* work_map, const Map& other_map) { 529 auto work_it = work_map->begin(), work_end = work_map->end(); 530 auto cmp = work_map->value_comp(); 531 for (const auto& entry : other_map) { 532 while (work_it != work_end && 533 (cmp(*work_it, entry) || 534 (!cmp(entry, *work_it) && !(work_it->second == entry.second)))) { 535 work_it = work_map->erase(work_it); 536 } 537 if (work_it == work_end) { 538 return; 539 } 540 ++work_it; 541 } 542} 543 544template <typename Set, Set LocalValueNumbering::*set_ptr, void (LocalValueNumbering::*MergeFn)( 545 const typename Set::value_type& entry, typename Set::iterator hint)> 546void LocalValueNumbering::MergeSets() { 547 auto cmp = (this->*set_ptr).value_comp(); 548 for (const LocalValueNumbering* lvn : gvn_->merge_lvns_) { 549 auto my_it = (this->*set_ptr).begin(), my_end = (this->*set_ptr).end(); 550 for (const auto& entry : lvn->*set_ptr) { 551 while (my_it != my_end && cmp(*my_it, entry)) { 552 ++my_it; 553 } 554 if (my_it != my_end && !cmp(entry, *my_it)) { 555 // Already handled. 556 ++my_it; 557 } else { 558 // Merge values for this field_id. 559 (this->*MergeFn)(entry, my_it); // my_it remains valid across inserts to std::set/SafeMap. 560 } 561 } 562 } 563} 564 565void LocalValueNumbering::IntersectAliasingValueLocations(AliasingValues* work_values, 566 const AliasingValues* values) { 567 auto cmp = work_values->load_value_map.key_comp(); 568 auto work_it = work_values->load_value_map.begin(), work_end = work_values->load_value_map.end(); 569 auto store_it = values->store_loc_set.begin(), store_end = values->store_loc_set.end(); 570 auto load_it = values->load_value_map.begin(), load_end = values->load_value_map.end(); 571 while (store_it != store_end || load_it != load_end) { 572 uint16_t loc; 573 if (store_it != store_end && (load_it == load_end || *store_it < load_it->first)) { 574 loc = *store_it; 575 ++store_it; 576 } else { 577 loc = load_it->first; 578 ++load_it; 579 DCHECK(store_it == store_end || cmp(loc, *store_it)); 580 } 581 while (work_it != work_end && cmp(work_it->first, loc)) { 582 work_it = work_values->load_value_map.erase(work_it); 583 } 584 if (work_it != work_end && !cmp(loc, work_it->first)) { 585 // The location matches, keep it. 586 ++work_it; 587 } 588 } 589 while (work_it != work_end) { 590 work_it = work_values->load_value_map.erase(work_it); 591 } 592} 593 594void LocalValueNumbering::MergeEscapedRefs(const ValueNameSet::value_type& entry, 595 ValueNameSet::iterator hint) { 596 // See if the ref is either escaped or non-aliasing in each predecessor. 597 bool is_escaped = true; 598 for (const LocalValueNumbering* lvn : gvn_->merge_lvns_) { 599 if (lvn->non_aliasing_refs_.count(entry) == 0u && 600 lvn->escaped_refs_.count(entry) == 0u) { 601 is_escaped = false; 602 break; 603 } 604 } 605 if (is_escaped) { 606 escaped_refs_.emplace_hint(hint, entry); 607 } 608} 609 610void LocalValueNumbering::MergeEscapedIFieldTypeClobberSets( 611 const EscapedIFieldClobberSet::value_type& entry, EscapedIFieldClobberSet::iterator hint) { 612 // Insert only type-clobber entries (field_id == kNoValue) of escaped refs. 613 if (entry.field_id == kNoValue && escaped_refs_.count(entry.base) != 0u) { 614 escaped_ifield_clobber_set_.emplace_hint(hint, entry); 615 } 616} 617 618void LocalValueNumbering::MergeEscapedIFieldClobberSets( 619 const EscapedIFieldClobberSet::value_type& entry, EscapedIFieldClobberSet::iterator hint) { 620 // Insert only those entries of escaped refs that are not overridden by a type clobber. 621 if (!(hint == escaped_ifield_clobber_set_.end() && 622 hint->base == entry.base && hint->type == entry.type) && 623 escaped_refs_.count(entry.base) != 0u) { 624 escaped_ifield_clobber_set_.emplace_hint(hint, entry); 625 } 626} 627 628void LocalValueNumbering::MergeEscapedArrayClobberSets( 629 const EscapedArrayClobberSet::value_type& entry, EscapedArrayClobberSet::iterator hint) { 630 if (escaped_refs_.count(entry.base) != 0u) { 631 escaped_array_clobber_set_.emplace_hint(hint, entry); 632 } 633} 634 635void LocalValueNumbering::MergeNullChecked(const ValueNameSet::value_type& entry, 636 ValueNameSet::iterator hint) { 637 // Merge null_checked_ for this ref. 638 merge_names_.clear(); 639 merge_names_.resize(gvn_->merge_lvns_.size(), entry); 640 if (gvn_->NullCheckedInAllPredecessors(merge_names_)) { 641 null_checked_.insert(hint, entry); 642 } 643} 644 645void LocalValueNumbering::MergeSFieldValues(const SFieldToValueMap::value_type& entry, 646 SFieldToValueMap::iterator hint) { 647 uint16_t field_id = entry.first; 648 merge_names_.clear(); 649 uint16_t value_name = kNoValue; 650 bool same_values = true; 651 for (const LocalValueNumbering* lvn : gvn_->merge_lvns_) { 652 // Get the value name as in HandleSGet() but don't modify *lvn. 653 auto it = lvn->sfield_value_map_.find(field_id); 654 if (it != lvn->sfield_value_map_.end()) { 655 value_name = it->second; 656 } else { 657 uint16_t type = gvn_->GetFieldType(field_id); 658 value_name = gvn_->LookupValue(kResolvedSFieldOp, field_id, 659 lvn->unresolved_sfield_version_[type], 660 lvn->global_memory_version_); 661 } 662 663 same_values = same_values && (merge_names_.empty() || value_name == merge_names_.back()); 664 merge_names_.push_back(value_name); 665 } 666 if (same_values) { 667 // value_name already contains the result. 668 } else { 669 auto lb = merge_map_.lower_bound(merge_names_); 670 if (lb != merge_map_.end() && !merge_map_.key_comp()(merge_names_, lb->first)) { 671 value_name = lb->second; 672 } else { 673 value_name = gvn_->LookupValue(kMergeBlockSFieldVersionBumpOp, field_id, id_, kNoValue); 674 merge_map_.PutBefore(lb, merge_names_, value_name); 675 if (gvn_->NullCheckedInAllPredecessors(merge_names_)) { 676 null_checked_.insert(value_name); 677 } 678 } 679 } 680 sfield_value_map_.PutBefore(hint, field_id, value_name); 681} 682 683void LocalValueNumbering::MergeNonAliasingIFieldValues(const IFieldLocToValueMap::value_type& entry, 684 IFieldLocToValueMap::iterator hint) { 685 uint16_t field_loc = entry.first; 686 merge_names_.clear(); 687 uint16_t value_name = kNoValue; 688 bool same_values = true; 689 for (const LocalValueNumbering* lvn : gvn_->merge_lvns_) { 690 // Get the value name as in HandleIGet() but don't modify *lvn. 691 auto it = lvn->non_aliasing_ifield_value_map_.find(field_loc); 692 if (it != lvn->non_aliasing_ifield_value_map_.end()) { 693 value_name = it->second; 694 } else { 695 value_name = gvn_->LookupValue(kNonAliasingIFieldInitialOp, field_loc, kNoValue, kNoValue); 696 } 697 698 same_values = same_values && (merge_names_.empty() || value_name == merge_names_.back()); 699 merge_names_.push_back(value_name); 700 } 701 if (same_values) { 702 // value_name already contains the result. 703 } else { 704 auto lb = merge_map_.lower_bound(merge_names_); 705 if (lb != merge_map_.end() && !merge_map_.key_comp()(merge_names_, lb->first)) { 706 value_name = lb->second; 707 } else { 708 value_name = gvn_->LookupValue(kMergeBlockNonAliasingIFieldVersionBumpOp, field_loc, 709 id_, kNoValue); 710 merge_map_.PutBefore(lb, merge_names_, value_name); 711 if (gvn_->NullCheckedInAllPredecessors(merge_names_)) { 712 null_checked_.insert(value_name); 713 } 714 } 715 } 716 non_aliasing_ifield_value_map_.PutBefore(hint, field_loc, value_name); 717} 718 719template <typename Map, Map LocalValueNumbering::*map_ptr, typename Versions> 720void LocalValueNumbering::MergeAliasingValues(const typename Map::value_type& entry, 721 typename Map::iterator hint) { 722 const typename Map::key_type& key = entry.first; 723 724 (this->*map_ptr).PutBefore(hint, key, AliasingValues(gvn_->allocator_)); 725 DCHECK(hint != (this->*map_ptr).begin()); 726 AliasingIFieldValuesMap::iterator it = hint; 727 --it; 728 DCHECK_EQ(it->first, key); 729 AliasingValues* my_values = &it->second; 730 731 const AliasingValues* cmp_values = nullptr; 732 bool same_version = !Versions::HasNewBaseVersion(gvn_, this, key); 733 uint16_t load_memory_version_for_same_version = kNoValue; 734 if (same_version) { 735 // Find the first non-null values. 736 for (const LocalValueNumbering* lvn : gvn_->merge_lvns_) { 737 auto it = (lvn->*map_ptr).find(key); 738 if (it != (lvn->*map_ptr).end()) { 739 cmp_values = &it->second; 740 break; 741 } 742 } 743 DCHECK(cmp_values != nullptr); // There must be at least one non-null values. 744 745 // Check if we have identical memory versions, i.e. the global memory version, unresolved 746 // field version and the values' memory_version_before_stores, last_stored_value 747 // and store_loc_set are identical. 748 for (const LocalValueNumbering* lvn : gvn_->merge_lvns_) { 749 auto it = (lvn->*map_ptr).find(key); 750 if (it == (lvn->*map_ptr).end()) { 751 if (cmp_values->memory_version_before_stores != kNoValue) { 752 same_version = false; 753 break; 754 } 755 } else if (cmp_values->last_stored_value != it->second.last_stored_value || 756 cmp_values->memory_version_before_stores != it->second.memory_version_before_stores || 757 cmp_values->store_loc_set != it->second.store_loc_set) { 758 same_version = false; 759 break; 760 } else if (it->second.last_load_memory_version != kNoValue) { 761 DCHECK(load_memory_version_for_same_version == kNoValue || 762 load_memory_version_for_same_version == it->second.last_load_memory_version); 763 load_memory_version_for_same_version = it->second.last_load_memory_version; 764 } 765 } 766 } 767 768 if (same_version) { 769 // Copy the identical values. 770 my_values->memory_version_before_stores = cmp_values->memory_version_before_stores; 771 my_values->last_stored_value = cmp_values->last_stored_value; 772 my_values->store_loc_set = cmp_values->store_loc_set; 773 my_values->last_load_memory_version = load_memory_version_for_same_version; 774 // Merge load values seen in all incoming arcs (i.e. an intersection). 775 if (!cmp_values->load_value_map.empty()) { 776 my_values->load_value_map = cmp_values->load_value_map; 777 for (const LocalValueNumbering* lvn : gvn_->merge_lvns_) { 778 auto it = (lvn->*map_ptr).find(key); 779 if (it == (lvn->*map_ptr).end() || it->second.load_value_map.empty()) { 780 my_values->load_value_map.clear(); 781 break; 782 } 783 InPlaceIntersectMaps(&my_values->load_value_map, it->second.load_value_map); 784 if (my_values->load_value_map.empty()) { 785 break; 786 } 787 } 788 } 789 } else { 790 // Bump version number for the merge. 791 my_values->memory_version_before_stores = my_values->last_load_memory_version = 792 Versions::LookupMergeBlockValue(gvn_, id_, key); 793 794 // Calculate the locations that have been either read from or written to in each incoming LVN. 795 bool first_lvn = true; 796 for (const LocalValueNumbering* lvn : gvn_->merge_lvns_) { 797 auto it = (lvn->*map_ptr).find(key); 798 if (it == (lvn->*map_ptr).end()) { 799 my_values->load_value_map.clear(); 800 break; 801 } 802 if (first_lvn) { 803 first_lvn = false; 804 // Copy the first LVN's locations. Values will be overwritten later. 805 my_values->load_value_map = it->second.load_value_map; 806 for (uint16_t location : it->second.store_loc_set) { 807 my_values->load_value_map.Put(location, 0u); 808 } 809 } else { 810 IntersectAliasingValueLocations(my_values, &it->second); 811 } 812 } 813 // Calculate merged values for the intersection. 814 for (auto& load_value_entry : my_values->load_value_map) { 815 uint16_t location = load_value_entry.first; 816 bool same_values = true; 817 uint16_t value_name = kNoValue; 818 merge_names_.clear(); 819 for (const LocalValueNumbering* lvn : gvn_->merge_lvns_) { 820 value_name = Versions::LookupMergeValue(gvn_, lvn, key, location); 821 same_values = same_values && (merge_names_.empty() || value_name == merge_names_.back()); 822 merge_names_.push_back(value_name); 823 } 824 if (same_values) { 825 // value_name already contains the result. 826 } else { 827 auto lb = merge_map_.lower_bound(merge_names_); 828 if (lb != merge_map_.end() && !merge_map_.key_comp()(merge_names_, lb->first)) { 829 value_name = lb->second; 830 } else { 831 // NOTE: In addition to the key and id_ which don't change on an LVN recalculation 832 // during GVN, we also add location which can actually change on recalculation, so the 833 // value_name below may change. This could lead to an infinite loop if the location 834 // value name always changed when the refereced value name changes. However, given that 835 // we assign unique value names for other merges, such as Phis, such a dependency is 836 // not possible in a well-formed SSA graph. 837 value_name = Versions::LookupMergeLocationValue(gvn_, id_, key, location); 838 merge_map_.PutBefore(lb, merge_names_, value_name); 839 if (gvn_->NullCheckedInAllPredecessors(merge_names_)) { 840 null_checked_.insert(value_name); 841 } 842 } 843 } 844 load_value_entry.second = value_name; 845 } 846 } 847} 848 849void LocalValueNumbering::Merge(MergeType merge_type) { 850 DCHECK_GE(gvn_->merge_lvns_.size(), 2u); 851 852 IntersectMaps<SregValueMap, &LocalValueNumbering::sreg_value_map_>(); 853 IntersectMaps<SregValueMap, &LocalValueNumbering::sreg_wide_value_map_>(); 854 if (merge_type == kReturnMerge) { 855 // RETURN or PHI+RETURN. We need only sreg value maps. 856 return; 857 } 858 859 MergeMemoryVersions(merge_type == kCatchMerge); 860 861 // Merge non-aliasing maps/sets. 862 IntersectSets<ValueNameSet, &LocalValueNumbering::non_aliasing_refs_>(); 863 if (!non_aliasing_refs_.empty() && merge_type == kCatchMerge) { 864 PruneNonAliasingRefsForCatch(); 865 } 866 if (!non_aliasing_refs_.empty()) { 867 MergeSets<IFieldLocToValueMap, &LocalValueNumbering::non_aliasing_ifield_value_map_, 868 &LocalValueNumbering::MergeNonAliasingIFieldValues>(); 869 MergeSets<NonAliasingArrayValuesMap, &LocalValueNumbering::non_aliasing_array_value_map_, 870 &LocalValueNumbering::MergeAliasingValues< 871 NonAliasingArrayValuesMap, &LocalValueNumbering::non_aliasing_array_value_map_, 872 NonAliasingArrayVersions>>(); 873 } 874 875 // We won't do anything complicated for range checks, just calculate the intersection. 876 IntersectSets<RangeCheckSet, &LocalValueNumbering::range_checked_>(); 877 878 // Merge null_checked_. We may later insert more, such as merged object field values. 879 MergeSets<ValueNameSet, &LocalValueNumbering::null_checked_, 880 &LocalValueNumbering::MergeNullChecked>(); 881 882 if (merge_type == kCatchMerge) { 883 // Memory is clobbered. New memory version already created, don't merge aliasing locations. 884 return; 885 } 886 887 DCHECK(merge_type == kNormalMerge); 888 889 // Merge escaped refs and clobber sets. 890 MergeSets<ValueNameSet, &LocalValueNumbering::escaped_refs_, 891 &LocalValueNumbering::MergeEscapedRefs>(); 892 if (!escaped_refs_.empty()) { 893 MergeSets<EscapedIFieldClobberSet, &LocalValueNumbering::escaped_ifield_clobber_set_, 894 &LocalValueNumbering::MergeEscapedIFieldTypeClobberSets>(); 895 MergeSets<EscapedIFieldClobberSet, &LocalValueNumbering::escaped_ifield_clobber_set_, 896 &LocalValueNumbering::MergeEscapedIFieldClobberSets>(); 897 MergeSets<EscapedArrayClobberSet, &LocalValueNumbering::escaped_array_clobber_set_, 898 &LocalValueNumbering::MergeEscapedArrayClobberSets>(); 899 } 900 901 MergeSets<SFieldToValueMap, &LocalValueNumbering::sfield_value_map_, 902 &LocalValueNumbering::MergeSFieldValues>(); 903 MergeSets<AliasingIFieldValuesMap, &LocalValueNumbering::aliasing_ifield_value_map_, 904 &LocalValueNumbering::MergeAliasingValues< 905 AliasingIFieldValuesMap, &LocalValueNumbering::aliasing_ifield_value_map_, 906 AliasingIFieldVersions>>(); 907 MergeSets<AliasingArrayValuesMap, &LocalValueNumbering::aliasing_array_value_map_, 908 &LocalValueNumbering::MergeAliasingValues< 909 AliasingArrayValuesMap, &LocalValueNumbering::aliasing_array_value_map_, 910 AliasingArrayVersions>>(); 911} 912 913uint16_t LocalValueNumbering::MarkNonAliasingNonNull(MIR* mir) { 914 uint16_t res = GetOperandValue(mir->ssa_rep->defs[0]); 915 DCHECK(null_checked_.find(res) == null_checked_.end()); 916 null_checked_.insert(res); 917 non_aliasing_refs_.insert(res); 918 return res; 919} 920 921bool LocalValueNumbering::IsNonAliasing(uint16_t reg) const { 922 return non_aliasing_refs_.find(reg) != non_aliasing_refs_.end(); 923} 924 925bool LocalValueNumbering::IsNonAliasingIField(uint16_t reg, uint16_t field_id, 926 uint16_t type) const { 927 if (IsNonAliasing(reg)) { 928 return true; 929 } 930 if (escaped_refs_.find(reg) == escaped_refs_.end()) { 931 return false; 932 } 933 // Check for IPUTs to unresolved fields. 934 EscapedIFieldClobberKey key1 = { reg, type, kNoValue }; 935 if (escaped_ifield_clobber_set_.find(key1) != escaped_ifield_clobber_set_.end()) { 936 return false; 937 } 938 // Check for aliased IPUTs to the same field. 939 EscapedIFieldClobberKey key2 = { reg, type, field_id }; 940 return escaped_ifield_clobber_set_.find(key2) == escaped_ifield_clobber_set_.end(); 941} 942 943bool LocalValueNumbering::IsNonAliasingArray(uint16_t reg, uint16_t type) const { 944 if (IsNonAliasing(reg)) { 945 return true; 946 } 947 if (escaped_refs_.count(reg) == 0u) { 948 return false; 949 } 950 // Check for aliased APUTs. 951 EscapedArrayClobberKey key = { reg, type }; 952 return escaped_array_clobber_set_.find(key) == escaped_array_clobber_set_.end(); 953} 954 955void LocalValueNumbering::HandleNullCheck(MIR* mir, uint16_t reg) { 956 auto lb = null_checked_.lower_bound(reg); 957 if (lb != null_checked_.end() && *lb == reg) { 958 if (LIKELY(gvn_->CanModify())) { 959 if (gvn_->GetCompilationUnit()->verbose) { 960 LOG(INFO) << "Removing null check for 0x" << std::hex << mir->offset; 961 } 962 mir->optimization_flags |= MIR_IGNORE_NULL_CHECK; 963 } 964 } else { 965 null_checked_.insert(lb, reg); 966 } 967} 968 969void LocalValueNumbering::HandleRangeCheck(MIR* mir, uint16_t array, uint16_t index) { 970 RangeCheckKey key = { array, index }; 971 auto lb = range_checked_.lower_bound(key); 972 if (lb != range_checked_.end() && !RangeCheckKeyComparator()(key, *lb)) { 973 if (LIKELY(gvn_->CanModify())) { 974 if (gvn_->GetCompilationUnit()->verbose) { 975 LOG(INFO) << "Removing range check for 0x" << std::hex << mir->offset; 976 } 977 mir->optimization_flags |= MIR_IGNORE_RANGE_CHECK; 978 } 979 } else { 980 // Mark range check completed. 981 range_checked_.insert(lb, key); 982 } 983} 984 985void LocalValueNumbering::HandlePutObject(MIR* mir) { 986 // If we're storing a non-aliasing reference, stop tracking it as non-aliasing now. 987 uint16_t base = GetOperandValue(mir->ssa_rep->uses[0]); 988 HandleEscapingRef(base); 989} 990 991void LocalValueNumbering::HandleEscapingRef(uint16_t base) { 992 auto it = non_aliasing_refs_.find(base); 993 if (it != non_aliasing_refs_.end()) { 994 non_aliasing_refs_.erase(it); 995 escaped_refs_.insert(base); 996 } 997} 998 999uint16_t LocalValueNumbering::HandlePhi(MIR* mir) { 1000 if (gvn_->merge_lvns_.empty()) { 1001 // Running LVN without a full GVN? 1002 return kNoValue; 1003 } 1004 int16_t num_uses = mir->ssa_rep->num_uses; 1005 int32_t* uses = mir->ssa_rep->uses; 1006 // Try to find out if this is merging wide regs. 1007 if (mir->ssa_rep->defs[0] != 0 && 1008 sreg_wide_value_map_.count(mir->ssa_rep->defs[0] - 1) != 0u) { 1009 // This is the high part of a wide reg. Ignore the Phi. 1010 return kNoValue; 1011 } 1012 bool wide = false; 1013 for (int16_t i = 0; i != num_uses; ++i) { 1014 if (sreg_wide_value_map_.count(uses[i]) != 0u) { 1015 wide = true; 1016 break; 1017 } 1018 } 1019 // Iterate over *merge_lvns_ and skip incoming sregs for BBs without associated LVN. 1020 uint16_t value_name = kNoValue; 1021 merge_names_.clear(); 1022 BasicBlockId* incoming = mir->meta.phi_incoming; 1023 int16_t pos = 0; 1024 bool same_values = true; 1025 for (const LocalValueNumbering* lvn : gvn_->merge_lvns_) { 1026 DCHECK_LT(pos, mir->ssa_rep->num_uses); 1027 while (incoming[pos] != lvn->Id()) { 1028 ++pos; 1029 DCHECK_LT(pos, mir->ssa_rep->num_uses); 1030 } 1031 int s_reg = uses[pos]; 1032 ++pos; 1033 value_name = wide ? lvn->GetOperandValueWide(s_reg) : lvn->GetOperandValue(s_reg); 1034 1035 same_values = same_values && (merge_names_.empty() || value_name == merge_names_.back()); 1036 merge_names_.push_back(value_name); 1037 } 1038 if (same_values) { 1039 // value_name already contains the result. 1040 } else { 1041 auto lb = merge_map_.lower_bound(merge_names_); 1042 if (lb != merge_map_.end() && !merge_map_.key_comp()(merge_names_, lb->first)) { 1043 value_name = lb->second; 1044 } else { 1045 value_name = gvn_->LookupValue(kNoValue, mir->ssa_rep->defs[0], kNoValue, kNoValue); 1046 merge_map_.PutBefore(lb, merge_names_, value_name); 1047 if (!wide && gvn_->NullCheckedInAllPredecessors(merge_names_)) { 1048 null_checked_.insert(value_name); 1049 } 1050 } 1051 } 1052 if (wide) { 1053 SetOperandValueWide(mir->ssa_rep->defs[0], value_name); 1054 } else { 1055 SetOperandValue(mir->ssa_rep->defs[0], value_name); 1056 } 1057 return value_name; 1058} 1059 1060uint16_t LocalValueNumbering::HandleAGet(MIR* mir, uint16_t opcode) { 1061 // uint16_t type = opcode - Instruction::AGET; 1062 uint16_t array = GetOperandValue(mir->ssa_rep->uses[0]); 1063 HandleNullCheck(mir, array); 1064 uint16_t index = GetOperandValue(mir->ssa_rep->uses[1]); 1065 HandleRangeCheck(mir, array, index); 1066 uint16_t type = opcode - Instruction::AGET; 1067 // Establish value number for loaded register. 1068 uint16_t res; 1069 if (IsNonAliasingArray(array, type)) { 1070 res = HandleAliasingValuesGet<NonAliasingArrayVersions>(&non_aliasing_array_value_map_, 1071 array, index); 1072 } else { 1073 uint16_t location = gvn_->GetArrayLocation(array, index); 1074 res = HandleAliasingValuesGet<AliasingArrayVersions>(&aliasing_array_value_map_, 1075 type, location); 1076 } 1077 if (opcode == Instruction::AGET_WIDE) { 1078 SetOperandValueWide(mir->ssa_rep->defs[0], res); 1079 } else { 1080 SetOperandValue(mir->ssa_rep->defs[0], res); 1081 } 1082 return res; 1083} 1084 1085void LocalValueNumbering::HandleAPut(MIR* mir, uint16_t opcode) { 1086 int array_idx = (opcode == Instruction::APUT_WIDE) ? 2 : 1; 1087 int index_idx = array_idx + 1; 1088 uint16_t array = GetOperandValue(mir->ssa_rep->uses[array_idx]); 1089 HandleNullCheck(mir, array); 1090 uint16_t index = GetOperandValue(mir->ssa_rep->uses[index_idx]); 1091 HandleRangeCheck(mir, array, index); 1092 1093 uint16_t type = opcode - Instruction::APUT; 1094 uint16_t value = (opcode == Instruction::APUT_WIDE) 1095 ? GetOperandValueWide(mir->ssa_rep->uses[0]) 1096 : GetOperandValue(mir->ssa_rep->uses[0]); 1097 if (IsNonAliasing(array)) { 1098 bool put_is_live = HandleAliasingValuesPut<NonAliasingArrayVersions>( 1099 &non_aliasing_array_value_map_, array, index, value); 1100 if (!put_is_live) { 1101 // This APUT can be eliminated, it stores the same value that's already in the field. 1102 // TODO: Eliminate the APUT. 1103 return; 1104 } 1105 } else { 1106 uint16_t location = gvn_->GetArrayLocation(array, index); 1107 bool put_is_live = HandleAliasingValuesPut<AliasingArrayVersions>( 1108 &aliasing_array_value_map_, type, location, value); 1109 if (!put_is_live) { 1110 // This APUT can be eliminated, it stores the same value that's already in the field. 1111 // TODO: Eliminate the APUT. 1112 return; 1113 } 1114 1115 // Clobber all escaped array refs for this type. 1116 for (uint16_t escaped_array : escaped_refs_) { 1117 EscapedArrayClobberKey clobber_key = { escaped_array, type }; 1118 escaped_array_clobber_set_.insert(clobber_key); 1119 } 1120 } 1121} 1122 1123uint16_t LocalValueNumbering::HandleIGet(MIR* mir, uint16_t opcode) { 1124 uint16_t base = GetOperandValue(mir->ssa_rep->uses[0]); 1125 HandleNullCheck(mir, base); 1126 const MirFieldInfo& field_info = gvn_->GetMirGraph()->GetIFieldLoweringInfo(mir); 1127 uint16_t res; 1128 if (!field_info.IsResolved() || field_info.IsVolatile()) { 1129 // Volatile fields always get a new memory version; field id is irrelevant. 1130 // Unresolved fields may be volatile, so handle them as such to be safe. 1131 // Use result s_reg - will be unique. 1132 res = gvn_->LookupValue(kNoValue, mir->ssa_rep->defs[0], kNoValue, kNoValue); 1133 } else { 1134 uint16_t type = opcode - Instruction::IGET; 1135 uint16_t field_id = gvn_->GetFieldId(field_info, type); 1136 if (IsNonAliasingIField(base, field_id, type)) { 1137 uint16_t loc = gvn_->LookupValue(kNonAliasingIFieldLocOp, base, field_id, type); 1138 auto lb = non_aliasing_ifield_value_map_.lower_bound(loc); 1139 if (lb != non_aliasing_ifield_value_map_.end() && lb->first == loc) { 1140 res = lb->second; 1141 } else { 1142 res = gvn_->LookupValue(kNonAliasingIFieldInitialOp, loc, kNoValue, kNoValue); 1143 non_aliasing_ifield_value_map_.PutBefore(lb, loc, res); 1144 } 1145 } else { 1146 res = HandleAliasingValuesGet<AliasingIFieldVersions>(&aliasing_ifield_value_map_, 1147 field_id, base); 1148 } 1149 } 1150 if (opcode == Instruction::IGET_WIDE) { 1151 SetOperandValueWide(mir->ssa_rep->defs[0], res); 1152 } else { 1153 SetOperandValue(mir->ssa_rep->defs[0], res); 1154 } 1155 return res; 1156} 1157 1158void LocalValueNumbering::HandleIPut(MIR* mir, uint16_t opcode) { 1159 uint16_t type = opcode - Instruction::IPUT; 1160 int base_reg = (opcode == Instruction::IPUT_WIDE) ? 2 : 1; 1161 uint16_t base = GetOperandValue(mir->ssa_rep->uses[base_reg]); 1162 HandleNullCheck(mir, base); 1163 const MirFieldInfo& field_info = gvn_->GetMirGraph()->GetIFieldLoweringInfo(mir); 1164 if (!field_info.IsResolved()) { 1165 // Unresolved fields always alias with everything of the same type. 1166 // Use mir->offset as modifier; without elaborate inlining, it will be unique. 1167 unresolved_ifield_version_[type] = 1168 gvn_->LookupValue(kUnresolvedIFieldOp, kNoValue, kNoValue, mir->offset); 1169 1170 // For simplicity, treat base as escaped now. 1171 HandleEscapingRef(base); 1172 1173 // Clobber all fields of escaped references of the same type. 1174 for (uint16_t escaped_ref : escaped_refs_) { 1175 EscapedIFieldClobberKey clobber_key = { escaped_ref, type, kNoValue }; 1176 escaped_ifield_clobber_set_.insert(clobber_key); 1177 } 1178 1179 // Aliasing fields of the same type may have been overwritten. 1180 auto it = aliasing_ifield_value_map_.begin(), end = aliasing_ifield_value_map_.end(); 1181 while (it != end) { 1182 if (gvn_->GetFieldType(it->first) != type) { 1183 ++it; 1184 } else { 1185 it = aliasing_ifield_value_map_.erase(it); 1186 } 1187 } 1188 } else if (field_info.IsVolatile()) { 1189 // Nothing to do, resolved volatile fields always get a new memory version anyway and 1190 // can't alias with resolved non-volatile fields. 1191 } else { 1192 uint16_t field_id = gvn_->GetFieldId(field_info, type); 1193 uint16_t value = (opcode == Instruction::IPUT_WIDE) 1194 ? GetOperandValueWide(mir->ssa_rep->uses[0]) 1195 : GetOperandValue(mir->ssa_rep->uses[0]); 1196 if (IsNonAliasing(base)) { 1197 uint16_t loc = gvn_->LookupValue(kNonAliasingIFieldLocOp, base, field_id, type); 1198 auto lb = non_aliasing_ifield_value_map_.lower_bound(loc); 1199 if (lb != non_aliasing_ifield_value_map_.end() && lb->first == loc) { 1200 if (lb->second == value) { 1201 // This IPUT can be eliminated, it stores the same value that's already in the field. 1202 // TODO: Eliminate the IPUT. 1203 return; 1204 } 1205 lb->second = value; // Overwrite. 1206 } else { 1207 non_aliasing_ifield_value_map_.PutBefore(lb, loc, value); 1208 } 1209 } else { 1210 bool put_is_live = HandleAliasingValuesPut<AliasingIFieldVersions>( 1211 &aliasing_ifield_value_map_, field_id, base, value); 1212 if (!put_is_live) { 1213 // This IPUT can be eliminated, it stores the same value that's already in the field. 1214 // TODO: Eliminate the IPUT. 1215 return; 1216 } 1217 1218 // Clobber all fields of escaped references for this field. 1219 for (uint16_t escaped_ref : escaped_refs_) { 1220 EscapedIFieldClobberKey clobber_key = { escaped_ref, type, field_id }; 1221 escaped_ifield_clobber_set_.insert(clobber_key); 1222 } 1223 } 1224 } 1225} 1226 1227uint16_t LocalValueNumbering::HandleSGet(MIR* mir, uint16_t opcode) { 1228 const MirSFieldLoweringInfo& field_info = gvn_->GetMirGraph()->GetSFieldLoweringInfo(mir); 1229 if (!field_info.IsInitialized() && (mir->optimization_flags & MIR_IGNORE_CLINIT_CHECK) == 0) { 1230 // Class initialization can call arbitrary functions, we need to wipe aliasing values. 1231 HandleInvokeOrClInit(mir); 1232 } 1233 uint16_t res; 1234 if (!field_info.IsResolved() || field_info.IsVolatile()) { 1235 // Volatile fields always get a new memory version; field id is irrelevant. 1236 // Unresolved fields may be volatile, so handle them as such to be safe. 1237 // Use result s_reg - will be unique. 1238 res = gvn_->LookupValue(kNoValue, mir->ssa_rep->defs[0], kNoValue, kNoValue); 1239 } else { 1240 uint16_t type = opcode - Instruction::SGET; 1241 uint16_t field_id = gvn_->GetFieldId(field_info, type); 1242 auto lb = sfield_value_map_.lower_bound(field_id); 1243 if (lb != sfield_value_map_.end() && lb->first == field_id) { 1244 res = lb->second; 1245 } else { 1246 // Resolved non-volatile static fields can alias with non-resolved fields of the same type, 1247 // so we need to use unresolved_sfield_version_[type] in addition to global_memory_version_ 1248 // to determine the version of the field. 1249 res = gvn_->LookupValue(kResolvedSFieldOp, field_id, 1250 unresolved_sfield_version_[type], global_memory_version_); 1251 sfield_value_map_.PutBefore(lb, field_id, res); 1252 } 1253 } 1254 if (opcode == Instruction::SGET_WIDE) { 1255 SetOperandValueWide(mir->ssa_rep->defs[0], res); 1256 } else { 1257 SetOperandValue(mir->ssa_rep->defs[0], res); 1258 } 1259 return res; 1260} 1261 1262void LocalValueNumbering::HandleSPut(MIR* mir, uint16_t opcode) { 1263 const MirSFieldLoweringInfo& field_info = gvn_->GetMirGraph()->GetSFieldLoweringInfo(mir); 1264 if (!field_info.IsInitialized() && (mir->optimization_flags & MIR_IGNORE_CLINIT_CHECK) == 0) { 1265 // Class initialization can call arbitrary functions, we need to wipe aliasing values. 1266 HandleInvokeOrClInit(mir); 1267 } 1268 uint16_t type = opcode - Instruction::SPUT; 1269 if (!field_info.IsResolved()) { 1270 // Unresolved fields always alias with everything of the same type. 1271 // Use mir->offset as modifier; without elaborate inlining, it will be unique. 1272 unresolved_sfield_version_[type] = 1273 gvn_->LookupValue(kUnresolvedSFieldOp, kNoValue, kNoValue, mir->offset); 1274 RemoveSFieldsForType(type); 1275 } else if (field_info.IsVolatile()) { 1276 // Nothing to do, resolved volatile fields always get a new memory version anyway and 1277 // can't alias with resolved non-volatile fields. 1278 } else { 1279 uint16_t field_id = gvn_->GetFieldId(field_info, type); 1280 uint16_t value = (opcode == Instruction::SPUT_WIDE) 1281 ? GetOperandValueWide(mir->ssa_rep->uses[0]) 1282 : GetOperandValue(mir->ssa_rep->uses[0]); 1283 // Resolved non-volatile static fields can alias with non-resolved fields of the same type, 1284 // so we need to use unresolved_sfield_version_[type] in addition to global_memory_version_ 1285 // to determine the version of the field. 1286 auto lb = sfield_value_map_.lower_bound(field_id); 1287 if (lb != sfield_value_map_.end() && lb->first == field_id) { 1288 if (lb->second == value) { 1289 // This SPUT can be eliminated, it stores the same value that's already in the field. 1290 // TODO: Eliminate the SPUT. 1291 return; 1292 } 1293 lb->second = value; // Overwrite. 1294 } else { 1295 sfield_value_map_.PutBefore(lb, field_id, value); 1296 } 1297 } 1298} 1299 1300void LocalValueNumbering::RemoveSFieldsForType(uint16_t type) { 1301 // Erase all static fields of this type from the sfield_value_map_. 1302 for (auto it = sfield_value_map_.begin(), end = sfield_value_map_.end(); it != end; ) { 1303 if (gvn_->GetFieldType(it->first) == type) { 1304 it = sfield_value_map_.erase(it); 1305 } else { 1306 ++it; 1307 } 1308 } 1309} 1310 1311void LocalValueNumbering::HandleInvokeOrClInit(MIR* mir) { 1312 // Use mir->offset as modifier; without elaborate inlining, it will be unique. 1313 global_memory_version_ = 1314 gvn_->LookupValue(kInvokeMemoryVersionBumpOp, 0u, 0u, mir->offset); 1315 // All static fields and instance fields and array elements of aliasing references, 1316 // including escaped references, may have been modified. 1317 sfield_value_map_.clear(); 1318 aliasing_ifield_value_map_.clear(); 1319 aliasing_array_value_map_.clear(); 1320 escaped_refs_.clear(); 1321 escaped_ifield_clobber_set_.clear(); 1322 escaped_array_clobber_set_.clear(); 1323} 1324 1325uint16_t LocalValueNumbering::GetValueNumber(MIR* mir) { 1326 uint16_t res = kNoValue; 1327 uint16_t opcode = mir->dalvikInsn.opcode; 1328 switch (opcode) { 1329 case Instruction::NOP: 1330 case Instruction::RETURN_VOID: 1331 case Instruction::RETURN: 1332 case Instruction::RETURN_OBJECT: 1333 case Instruction::RETURN_WIDE: 1334 case Instruction::GOTO: 1335 case Instruction::GOTO_16: 1336 case Instruction::GOTO_32: 1337 case Instruction::CHECK_CAST: 1338 case Instruction::THROW: 1339 case Instruction::FILL_ARRAY_DATA: 1340 case Instruction::PACKED_SWITCH: 1341 case Instruction::SPARSE_SWITCH: 1342 case Instruction::IF_EQ: 1343 case Instruction::IF_NE: 1344 case Instruction::IF_LT: 1345 case Instruction::IF_GE: 1346 case Instruction::IF_GT: 1347 case Instruction::IF_LE: 1348 case Instruction::IF_EQZ: 1349 case Instruction::IF_NEZ: 1350 case Instruction::IF_LTZ: 1351 case Instruction::IF_GEZ: 1352 case Instruction::IF_GTZ: 1353 case Instruction::IF_LEZ: 1354 case kMirOpFusedCmplFloat: 1355 case kMirOpFusedCmpgFloat: 1356 case kMirOpFusedCmplDouble: 1357 case kMirOpFusedCmpgDouble: 1358 case kMirOpFusedCmpLong: 1359 // Nothing defined - take no action. 1360 break; 1361 1362 case Instruction::MONITOR_ENTER: 1363 HandleNullCheck(mir, GetOperandValue(mir->ssa_rep->uses[0])); 1364 // NOTE: Keeping all aliasing values intact. Programs that rely on loads/stores of the 1365 // same non-volatile locations outside and inside a synchronized block being different 1366 // contain races that we cannot fix. 1367 break; 1368 1369 case Instruction::MONITOR_EXIT: 1370 HandleNullCheck(mir, GetOperandValue(mir->ssa_rep->uses[0])); 1371 // If we're running GVN and CanModify(), uneliminated null check indicates bytecode error. 1372 if ((gvn_->GetCompilationUnit()->disable_opt & (1u << kGlobalValueNumbering)) == 0u && 1373 gvn_->CanModify() && (mir->optimization_flags & MIR_IGNORE_NULL_CHECK) == 0) { 1374 LOG(WARNING) << "Bytecode error: MONITOR_EXIT is still null checked at 0x" << std::hex 1375 << mir->offset << " in " << PrettyMethod(gvn_->cu_->method_idx, *gvn_->cu_->dex_file); 1376 } 1377 break; 1378 1379 case Instruction::FILLED_NEW_ARRAY: 1380 case Instruction::FILLED_NEW_ARRAY_RANGE: 1381 // Nothing defined but the result will be unique and non-null. 1382 if (mir->next != nullptr && mir->next->dalvikInsn.opcode == Instruction::MOVE_RESULT_OBJECT) { 1383 uint16_t array = MarkNonAliasingNonNull(mir->next); 1384 // Do not SetOperandValue(), we'll do that when we process the MOVE_RESULT_OBJECT. 1385 if (kLocalValueNumberingEnableFilledNewArrayTracking && mir->ssa_rep->num_uses != 0u) { 1386 AliasingValues* values = GetAliasingValues(&non_aliasing_array_value_map_, array); 1387 // Clear the value if we got a merged version in a loop. 1388 *values = AliasingValues(gvn_->allocator_); 1389 for (size_t i = 0u, count = mir->ssa_rep->num_uses; i != count; ++i) { 1390 DCHECK_EQ(High16Bits(i), 0u); 1391 uint16_t index = gvn_->LookupValue(Instruction::CONST, i, 0u, 0); 1392 uint16_t value = GetOperandValue(mir->ssa_rep->uses[i]); 1393 values->load_value_map.Put(index, value); 1394 RangeCheckKey key = { array, index }; 1395 range_checked_.insert(key); 1396 } 1397 } 1398 // The MOVE_RESULT_OBJECT will be processed next and we'll return the value name then. 1399 } 1400 // All args escaped (if references). 1401 for (size_t i = 0u, count = mir->ssa_rep->num_uses; i != count; ++i) { 1402 uint16_t reg = GetOperandValue(mir->ssa_rep->uses[i]); 1403 HandleEscapingRef(reg); 1404 } 1405 break; 1406 1407 case Instruction::INVOKE_DIRECT: 1408 case Instruction::INVOKE_DIRECT_RANGE: 1409 case Instruction::INVOKE_VIRTUAL: 1410 case Instruction::INVOKE_VIRTUAL_RANGE: 1411 case Instruction::INVOKE_SUPER: 1412 case Instruction::INVOKE_SUPER_RANGE: 1413 case Instruction::INVOKE_INTERFACE: 1414 case Instruction::INVOKE_INTERFACE_RANGE: { 1415 // Nothing defined but handle the null check. 1416 uint16_t reg = GetOperandValue(mir->ssa_rep->uses[0]); 1417 HandleNullCheck(mir, reg); 1418 } 1419 // Intentional fall-through. 1420 case Instruction::INVOKE_STATIC: 1421 case Instruction::INVOKE_STATIC_RANGE: 1422 if ((mir->optimization_flags & MIR_INLINED) == 0) { 1423 // Make ref args aliasing. 1424 for (size_t i = 0u, count = mir->ssa_rep->num_uses; i != count; ++i) { 1425 uint16_t reg = GetOperandValue(mir->ssa_rep->uses[i]); 1426 non_aliasing_refs_.erase(reg); 1427 } 1428 HandleInvokeOrClInit(mir); 1429 } 1430 break; 1431 1432 case Instruction::MOVE_RESULT: 1433 case Instruction::MOVE_RESULT_OBJECT: 1434 case Instruction::INSTANCE_OF: 1435 // 1 result, treat as unique each time, use result s_reg - will be unique. 1436 res = GetOperandValue(mir->ssa_rep->defs[0]); 1437 SetOperandValue(mir->ssa_rep->defs[0], res); 1438 break; 1439 case Instruction::MOVE_EXCEPTION: 1440 case Instruction::NEW_INSTANCE: 1441 case Instruction::CONST_CLASS: 1442 case Instruction::NEW_ARRAY: 1443 // 1 result, treat as unique each time, use result s_reg - will be unique. 1444 res = MarkNonAliasingNonNull(mir); 1445 SetOperandValue(mir->ssa_rep->defs[0], res); 1446 break; 1447 case Instruction::CONST_STRING: 1448 case Instruction::CONST_STRING_JUMBO: 1449 // These strings are internalized, so assign value based on the string pool index. 1450 res = gvn_->LookupValue(Instruction::CONST_STRING, Low16Bits(mir->dalvikInsn.vB), 1451 High16Bits(mir->dalvikInsn.vB), 0); 1452 SetOperandValue(mir->ssa_rep->defs[0], res); 1453 null_checked_.insert(res); // May already be there. 1454 // NOTE: Hacking the contents of an internalized string via reflection is possible 1455 // but the behavior is undefined. Therefore, we consider the string constant and 1456 // the reference non-aliasing. 1457 // TUNING: We could keep this property even if the reference "escapes". 1458 non_aliasing_refs_.insert(res); // May already be there. 1459 break; 1460 case Instruction::MOVE_RESULT_WIDE: 1461 // 1 wide result, treat as unique each time, use result s_reg - will be unique. 1462 res = GetOperandValueWide(mir->ssa_rep->defs[0]); 1463 SetOperandValueWide(mir->ssa_rep->defs[0], res); 1464 break; 1465 1466 case kMirOpPhi: 1467 res = HandlePhi(mir); 1468 break; 1469 1470 case Instruction::MOVE: 1471 case Instruction::MOVE_OBJECT: 1472 case Instruction::MOVE_16: 1473 case Instruction::MOVE_OBJECT_16: 1474 case Instruction::MOVE_FROM16: 1475 case Instruction::MOVE_OBJECT_FROM16: 1476 case kMirOpCopy: 1477 // Just copy value number of source to value number of result. 1478 res = GetOperandValue(mir->ssa_rep->uses[0]); 1479 SetOperandValue(mir->ssa_rep->defs[0], res); 1480 break; 1481 1482 case Instruction::MOVE_WIDE: 1483 case Instruction::MOVE_WIDE_16: 1484 case Instruction::MOVE_WIDE_FROM16: 1485 // Just copy value number of source to value number of result. 1486 res = GetOperandValueWide(mir->ssa_rep->uses[0]); 1487 SetOperandValueWide(mir->ssa_rep->defs[0], res); 1488 break; 1489 1490 case Instruction::CONST: 1491 case Instruction::CONST_4: 1492 case Instruction::CONST_16: 1493 res = gvn_->LookupValue(Instruction::CONST, Low16Bits(mir->dalvikInsn.vB), 1494 High16Bits(mir->dalvikInsn.vB), 0); 1495 SetOperandValue(mir->ssa_rep->defs[0], res); 1496 break; 1497 1498 case Instruction::CONST_HIGH16: 1499 res = gvn_->LookupValue(Instruction::CONST, 0, mir->dalvikInsn.vB, 0); 1500 SetOperandValue(mir->ssa_rep->defs[0], res); 1501 break; 1502 1503 case Instruction::CONST_WIDE_16: 1504 case Instruction::CONST_WIDE_32: { 1505 uint16_t low_res = gvn_->LookupValue(Instruction::CONST, Low16Bits(mir->dalvikInsn.vB), 1506 High16Bits(mir->dalvikInsn.vB >> 16), 1); 1507 uint16_t high_res; 1508 if (mir->dalvikInsn.vB & 0x80000000) { 1509 high_res = gvn_->LookupValue(Instruction::CONST, 0xffff, 0xffff, 2); 1510 } else { 1511 high_res = gvn_->LookupValue(Instruction::CONST, 0, 0, 2); 1512 } 1513 res = gvn_->LookupValue(Instruction::CONST, low_res, high_res, 3); 1514 SetOperandValueWide(mir->ssa_rep->defs[0], res); 1515 } 1516 break; 1517 1518 case Instruction::CONST_WIDE: { 1519 uint32_t low_word = Low32Bits(mir->dalvikInsn.vB_wide); 1520 uint32_t high_word = High32Bits(mir->dalvikInsn.vB_wide); 1521 uint16_t low_res = gvn_->LookupValue(Instruction::CONST, Low16Bits(low_word), 1522 High16Bits(low_word), 1); 1523 uint16_t high_res = gvn_->LookupValue(Instruction::CONST, Low16Bits(high_word), 1524 High16Bits(high_word), 2); 1525 res = gvn_->LookupValue(Instruction::CONST, low_res, high_res, 3); 1526 SetOperandValueWide(mir->ssa_rep->defs[0], res); 1527 } 1528 break; 1529 1530 case Instruction::CONST_WIDE_HIGH16: { 1531 uint16_t low_res = gvn_->LookupValue(Instruction::CONST, 0, 0, 1); 1532 uint16_t high_res = gvn_->LookupValue(Instruction::CONST, 0, 1533 Low16Bits(mir->dalvikInsn.vB), 2); 1534 res = gvn_->LookupValue(Instruction::CONST, low_res, high_res, 3); 1535 SetOperandValueWide(mir->ssa_rep->defs[0], res); 1536 } 1537 break; 1538 1539 case Instruction::ARRAY_LENGTH: { 1540 // Handle the null check. 1541 uint16_t reg = GetOperandValue(mir->ssa_rep->uses[0]); 1542 HandleNullCheck(mir, reg); 1543 } 1544 // Intentional fall-through. 1545 case Instruction::NEG_INT: 1546 case Instruction::NOT_INT: 1547 case Instruction::NEG_FLOAT: 1548 case Instruction::INT_TO_BYTE: 1549 case Instruction::INT_TO_SHORT: 1550 case Instruction::INT_TO_CHAR: 1551 case Instruction::INT_TO_FLOAT: 1552 case Instruction::FLOAT_TO_INT: { 1553 // res = op + 1 operand 1554 uint16_t operand1 = GetOperandValue(mir->ssa_rep->uses[0]); 1555 res = gvn_->LookupValue(opcode, operand1, kNoValue, kNoValue); 1556 SetOperandValue(mir->ssa_rep->defs[0], res); 1557 } 1558 break; 1559 1560 case Instruction::LONG_TO_FLOAT: 1561 case Instruction::LONG_TO_INT: 1562 case Instruction::DOUBLE_TO_FLOAT: 1563 case Instruction::DOUBLE_TO_INT: { 1564 // res = op + 1 wide operand 1565 uint16_t operand1 = GetOperandValueWide(mir->ssa_rep->uses[0]); 1566 res = gvn_->LookupValue(opcode, operand1, kNoValue, kNoValue); 1567 SetOperandValue(mir->ssa_rep->defs[0], res); 1568 } 1569 break; 1570 1571 1572 case Instruction::DOUBLE_TO_LONG: 1573 case Instruction::LONG_TO_DOUBLE: 1574 case Instruction::NEG_LONG: 1575 case Instruction::NOT_LONG: 1576 case Instruction::NEG_DOUBLE: { 1577 // wide res = op + 1 wide operand 1578 uint16_t operand1 = GetOperandValueWide(mir->ssa_rep->uses[0]); 1579 res = gvn_->LookupValue(opcode, operand1, kNoValue, kNoValue); 1580 SetOperandValueWide(mir->ssa_rep->defs[0], res); 1581 } 1582 break; 1583 1584 case Instruction::FLOAT_TO_DOUBLE: 1585 case Instruction::FLOAT_TO_LONG: 1586 case Instruction::INT_TO_DOUBLE: 1587 case Instruction::INT_TO_LONG: { 1588 // wide res = op + 1 operand 1589 uint16_t operand1 = GetOperandValue(mir->ssa_rep->uses[0]); 1590 res = gvn_->LookupValue(opcode, operand1, kNoValue, kNoValue); 1591 SetOperandValueWide(mir->ssa_rep->defs[0], res); 1592 } 1593 break; 1594 1595 case Instruction::CMPL_DOUBLE: 1596 case Instruction::CMPG_DOUBLE: 1597 case Instruction::CMP_LONG: { 1598 // res = op + 2 wide operands 1599 uint16_t operand1 = GetOperandValueWide(mir->ssa_rep->uses[0]); 1600 uint16_t operand2 = GetOperandValueWide(mir->ssa_rep->uses[2]); 1601 res = gvn_->LookupValue(opcode, operand1, operand2, kNoValue); 1602 SetOperandValue(mir->ssa_rep->defs[0], res); 1603 } 1604 break; 1605 1606 case Instruction::CMPG_FLOAT: 1607 case Instruction::CMPL_FLOAT: 1608 case Instruction::ADD_INT: 1609 case Instruction::ADD_INT_2ADDR: 1610 case Instruction::MUL_INT: 1611 case Instruction::MUL_INT_2ADDR: 1612 case Instruction::AND_INT: 1613 case Instruction::AND_INT_2ADDR: 1614 case Instruction::OR_INT: 1615 case Instruction::OR_INT_2ADDR: 1616 case Instruction::XOR_INT: 1617 case Instruction::XOR_INT_2ADDR: 1618 case Instruction::SUB_INT: 1619 case Instruction::SUB_INT_2ADDR: 1620 case Instruction::DIV_INT: 1621 case Instruction::DIV_INT_2ADDR: 1622 case Instruction::REM_INT: 1623 case Instruction::REM_INT_2ADDR: 1624 case Instruction::SHL_INT: 1625 case Instruction::SHL_INT_2ADDR: 1626 case Instruction::SHR_INT: 1627 case Instruction::SHR_INT_2ADDR: 1628 case Instruction::USHR_INT: 1629 case Instruction::USHR_INT_2ADDR: { 1630 // res = op + 2 operands 1631 uint16_t operand1 = GetOperandValue(mir->ssa_rep->uses[0]); 1632 uint16_t operand2 = GetOperandValue(mir->ssa_rep->uses[1]); 1633 res = gvn_->LookupValue(opcode, operand1, operand2, kNoValue); 1634 SetOperandValue(mir->ssa_rep->defs[0], res); 1635 } 1636 break; 1637 1638 case Instruction::ADD_LONG: 1639 case Instruction::SUB_LONG: 1640 case Instruction::MUL_LONG: 1641 case Instruction::DIV_LONG: 1642 case Instruction::REM_LONG: 1643 case Instruction::AND_LONG: 1644 case Instruction::OR_LONG: 1645 case Instruction::XOR_LONG: 1646 case Instruction::ADD_LONG_2ADDR: 1647 case Instruction::SUB_LONG_2ADDR: 1648 case Instruction::MUL_LONG_2ADDR: 1649 case Instruction::DIV_LONG_2ADDR: 1650 case Instruction::REM_LONG_2ADDR: 1651 case Instruction::AND_LONG_2ADDR: 1652 case Instruction::OR_LONG_2ADDR: 1653 case Instruction::XOR_LONG_2ADDR: 1654 case Instruction::ADD_DOUBLE: 1655 case Instruction::SUB_DOUBLE: 1656 case Instruction::MUL_DOUBLE: 1657 case Instruction::DIV_DOUBLE: 1658 case Instruction::REM_DOUBLE: 1659 case Instruction::ADD_DOUBLE_2ADDR: 1660 case Instruction::SUB_DOUBLE_2ADDR: 1661 case Instruction::MUL_DOUBLE_2ADDR: 1662 case Instruction::DIV_DOUBLE_2ADDR: 1663 case Instruction::REM_DOUBLE_2ADDR: { 1664 // wide res = op + 2 wide operands 1665 uint16_t operand1 = GetOperandValueWide(mir->ssa_rep->uses[0]); 1666 uint16_t operand2 = GetOperandValueWide(mir->ssa_rep->uses[2]); 1667 res = gvn_->LookupValue(opcode, operand1, operand2, kNoValue); 1668 SetOperandValueWide(mir->ssa_rep->defs[0], res); 1669 } 1670 break; 1671 1672 case Instruction::SHL_LONG: 1673 case Instruction::SHR_LONG: 1674 case Instruction::USHR_LONG: 1675 case Instruction::SHL_LONG_2ADDR: 1676 case Instruction::SHR_LONG_2ADDR: 1677 case Instruction::USHR_LONG_2ADDR: { 1678 // wide res = op + 1 wide operand + 1 operand 1679 uint16_t operand1 = GetOperandValueWide(mir->ssa_rep->uses[0]); 1680 uint16_t operand2 = GetOperandValue(mir->ssa_rep->uses[2]); 1681 res = gvn_->LookupValue(opcode, operand1, operand2, kNoValue); 1682 SetOperandValueWide(mir->ssa_rep->defs[0], res); 1683 } 1684 break; 1685 1686 case Instruction::ADD_FLOAT: 1687 case Instruction::SUB_FLOAT: 1688 case Instruction::MUL_FLOAT: 1689 case Instruction::DIV_FLOAT: 1690 case Instruction::REM_FLOAT: 1691 case Instruction::ADD_FLOAT_2ADDR: 1692 case Instruction::SUB_FLOAT_2ADDR: 1693 case Instruction::MUL_FLOAT_2ADDR: 1694 case Instruction::DIV_FLOAT_2ADDR: 1695 case Instruction::REM_FLOAT_2ADDR: { 1696 // res = op + 2 operands 1697 uint16_t operand1 = GetOperandValue(mir->ssa_rep->uses[0]); 1698 uint16_t operand2 = GetOperandValue(mir->ssa_rep->uses[1]); 1699 res = gvn_->LookupValue(opcode, operand1, operand2, kNoValue); 1700 SetOperandValue(mir->ssa_rep->defs[0], res); 1701 } 1702 break; 1703 1704 case Instruction::RSUB_INT: 1705 case Instruction::ADD_INT_LIT16: 1706 case Instruction::MUL_INT_LIT16: 1707 case Instruction::DIV_INT_LIT16: 1708 case Instruction::REM_INT_LIT16: 1709 case Instruction::AND_INT_LIT16: 1710 case Instruction::OR_INT_LIT16: 1711 case Instruction::XOR_INT_LIT16: 1712 case Instruction::ADD_INT_LIT8: 1713 case Instruction::RSUB_INT_LIT8: 1714 case Instruction::MUL_INT_LIT8: 1715 case Instruction::DIV_INT_LIT8: 1716 case Instruction::REM_INT_LIT8: 1717 case Instruction::AND_INT_LIT8: 1718 case Instruction::OR_INT_LIT8: 1719 case Instruction::XOR_INT_LIT8: 1720 case Instruction::SHL_INT_LIT8: 1721 case Instruction::SHR_INT_LIT8: 1722 case Instruction::USHR_INT_LIT8: { 1723 // Same as res = op + 2 operands, except use vC as operand 2 1724 uint16_t operand1 = GetOperandValue(mir->ssa_rep->uses[0]); 1725 uint16_t operand2 = gvn_->LookupValue(Instruction::CONST, mir->dalvikInsn.vC, 0, 0); 1726 res = gvn_->LookupValue(opcode, operand1, operand2, kNoValue); 1727 SetOperandValue(mir->ssa_rep->defs[0], res); 1728 } 1729 break; 1730 1731 case Instruction::AGET_OBJECT: 1732 case Instruction::AGET: 1733 case Instruction::AGET_WIDE: 1734 case Instruction::AGET_BOOLEAN: 1735 case Instruction::AGET_BYTE: 1736 case Instruction::AGET_CHAR: 1737 case Instruction::AGET_SHORT: 1738 res = HandleAGet(mir, opcode); 1739 break; 1740 1741 case Instruction::APUT_OBJECT: 1742 HandlePutObject(mir); 1743 // Intentional fall-through. 1744 case Instruction::APUT: 1745 case Instruction::APUT_WIDE: 1746 case Instruction::APUT_BYTE: 1747 case Instruction::APUT_BOOLEAN: 1748 case Instruction::APUT_SHORT: 1749 case Instruction::APUT_CHAR: 1750 HandleAPut(mir, opcode); 1751 break; 1752 1753 case Instruction::IGET_OBJECT: 1754 case Instruction::IGET: 1755 case Instruction::IGET_WIDE: 1756 case Instruction::IGET_BOOLEAN: 1757 case Instruction::IGET_BYTE: 1758 case Instruction::IGET_CHAR: 1759 case Instruction::IGET_SHORT: 1760 res = HandleIGet(mir, opcode); 1761 break; 1762 1763 case Instruction::IPUT_OBJECT: 1764 HandlePutObject(mir); 1765 // Intentional fall-through. 1766 case Instruction::IPUT: 1767 case Instruction::IPUT_WIDE: 1768 case Instruction::IPUT_BOOLEAN: 1769 case Instruction::IPUT_BYTE: 1770 case Instruction::IPUT_CHAR: 1771 case Instruction::IPUT_SHORT: 1772 HandleIPut(mir, opcode); 1773 break; 1774 1775 case Instruction::SGET_OBJECT: 1776 case Instruction::SGET: 1777 case Instruction::SGET_WIDE: 1778 case Instruction::SGET_BOOLEAN: 1779 case Instruction::SGET_BYTE: 1780 case Instruction::SGET_CHAR: 1781 case Instruction::SGET_SHORT: 1782 res = HandleSGet(mir, opcode); 1783 break; 1784 1785 case Instruction::SPUT_OBJECT: 1786 HandlePutObject(mir); 1787 // Intentional fall-through. 1788 case Instruction::SPUT: 1789 case Instruction::SPUT_WIDE: 1790 case Instruction::SPUT_BOOLEAN: 1791 case Instruction::SPUT_BYTE: 1792 case Instruction::SPUT_CHAR: 1793 case Instruction::SPUT_SHORT: 1794 HandleSPut(mir, opcode); 1795 break; 1796 } 1797 return res; 1798} 1799 1800} // namespace art 1801