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