| OLD | NEW |
| 1 // Copyright 2013 the V8 project authors. All rights reserved. | 1 // Copyright 2013 the V8 project authors. All rights reserved. |
| 2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
| 3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
| 4 | 4 |
| 5 #include "src/hydrogen.h" | 5 #include "src/hydrogen.h" |
| 6 #include "src/hydrogen-gvn.h" | 6 #include "src/hydrogen-gvn.h" |
| 7 #include "src/v8.h" | 7 #include "src/v8.h" |
| 8 | 8 |
| 9 namespace v8 { | 9 namespace v8 { |
| 10 namespace internal { | 10 namespace internal { |
| (...skipping 65 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 76 explicit HSideEffectMap(HSideEffectMap* other); | 76 explicit HSideEffectMap(HSideEffectMap* other); |
| 77 HSideEffectMap& operator= (const HSideEffectMap& other); | 77 HSideEffectMap& operator= (const HSideEffectMap& other); |
| 78 | 78 |
| 79 void Kill(SideEffects side_effects); | 79 void Kill(SideEffects side_effects); |
| 80 | 80 |
| 81 void Store(SideEffects side_effects, HInstruction* instr); | 81 void Store(SideEffects side_effects, HInstruction* instr); |
| 82 | 82 |
| 83 bool IsEmpty() const { return count_ == 0; } | 83 bool IsEmpty() const { return count_ == 0; } |
| 84 | 84 |
| 85 inline HInstruction* operator[](int i) const { | 85 inline HInstruction* operator[](int i) const { |
| 86 ASSERT(0 <= i); | 86 DCHECK(0 <= i); |
| 87 ASSERT(i < kNumberOfTrackedSideEffects); | 87 DCHECK(i < kNumberOfTrackedSideEffects); |
| 88 return data_[i]; | 88 return data_[i]; |
| 89 } | 89 } |
| 90 inline HInstruction* at(int i) const { return operator[](i); } | 90 inline HInstruction* at(int i) const { return operator[](i); } |
| 91 | 91 |
| 92 private: | 92 private: |
| 93 int count_; | 93 int count_; |
| 94 HInstruction* data_[kNumberOfTrackedSideEffects]; | 94 HInstruction* data_[kNumberOfTrackedSideEffects]; |
| 95 }; | 95 }; |
| 96 | 96 |
| 97 | 97 |
| (...skipping 107 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 205 while (next != kNil) { | 205 while (next != kNil) { |
| 206 if (lists_[next].instr->Equals(instr)) return lists_[next].instr; | 206 if (lists_[next].instr->Equals(instr)) return lists_[next].instr; |
| 207 next = lists_[next].next; | 207 next = lists_[next].next; |
| 208 } | 208 } |
| 209 } | 209 } |
| 210 return NULL; | 210 return NULL; |
| 211 } | 211 } |
| 212 | 212 |
| 213 | 213 |
| 214 void HInstructionMap::Resize(int new_size, Zone* zone) { | 214 void HInstructionMap::Resize(int new_size, Zone* zone) { |
| 215 ASSERT(new_size > count_); | 215 DCHECK(new_size > count_); |
| 216 // Hashing the values into the new array has no more collisions than in the | 216 // Hashing the values into the new array has no more collisions than in the |
| 217 // old hash map, so we can use the existing lists_ array, if we are careful. | 217 // old hash map, so we can use the existing lists_ array, if we are careful. |
| 218 | 218 |
| 219 // Make sure we have at least one free element. | 219 // Make sure we have at least one free element. |
| 220 if (free_list_head_ == kNil) { | 220 if (free_list_head_ == kNil) { |
| 221 ResizeLists(lists_size_ << 1, zone); | 221 ResizeLists(lists_size_ << 1, zone); |
| 222 } | 222 } |
| 223 | 223 |
| 224 HInstructionMapListElement* new_array = | 224 HInstructionMapListElement* new_array = |
| 225 zone->NewArray<HInstructionMapListElement>(new_size); | 225 zone->NewArray<HInstructionMapListElement>(new_size); |
| (...skipping 19 matching lines...) Expand all Loading... |
| 245 lists_[current].next = free_list_head_; | 245 lists_[current].next = free_list_head_; |
| 246 free_list_head_ = current; | 246 free_list_head_ = current; |
| 247 current = next; | 247 current = next; |
| 248 } | 248 } |
| 249 // Rehash the directly stored instruction. | 249 // Rehash the directly stored instruction. |
| 250 Insert(old_array[i].instr, zone); | 250 Insert(old_array[i].instr, zone); |
| 251 } | 251 } |
| 252 } | 252 } |
| 253 } | 253 } |
| 254 USE(old_count); | 254 USE(old_count); |
| 255 ASSERT(count_ == old_count); | 255 DCHECK(count_ == old_count); |
| 256 } | 256 } |
| 257 | 257 |
| 258 | 258 |
| 259 void HInstructionMap::ResizeLists(int new_size, Zone* zone) { | 259 void HInstructionMap::ResizeLists(int new_size, Zone* zone) { |
| 260 ASSERT(new_size > lists_size_); | 260 DCHECK(new_size > lists_size_); |
| 261 | 261 |
| 262 HInstructionMapListElement* new_lists = | 262 HInstructionMapListElement* new_lists = |
| 263 zone->NewArray<HInstructionMapListElement>(new_size); | 263 zone->NewArray<HInstructionMapListElement>(new_size); |
| 264 memset(new_lists, 0, sizeof(HInstructionMapListElement) * new_size); | 264 memset(new_lists, 0, sizeof(HInstructionMapListElement) * new_size); |
| 265 | 265 |
| 266 HInstructionMapListElement* old_lists = lists_; | 266 HInstructionMapListElement* old_lists = lists_; |
| 267 int old_size = lists_size_; | 267 int old_size = lists_size_; |
| 268 | 268 |
| 269 lists_size_ = new_size; | 269 lists_size_ = new_size; |
| 270 lists_ = new_lists; | 270 lists_ = new_lists; |
| 271 | 271 |
| 272 if (old_lists != NULL) { | 272 if (old_lists != NULL) { |
| 273 MemCopy(lists_, old_lists, old_size * sizeof(HInstructionMapListElement)); | 273 MemCopy(lists_, old_lists, old_size * sizeof(HInstructionMapListElement)); |
| 274 } | 274 } |
| 275 for (int i = old_size; i < lists_size_; ++i) { | 275 for (int i = old_size; i < lists_size_; ++i) { |
| 276 lists_[i].next = free_list_head_; | 276 lists_[i].next = free_list_head_; |
| 277 free_list_head_ = i; | 277 free_list_head_ = i; |
| 278 } | 278 } |
| 279 } | 279 } |
| 280 | 280 |
| 281 | 281 |
| 282 void HInstructionMap::Insert(HInstruction* instr, Zone* zone) { | 282 void HInstructionMap::Insert(HInstruction* instr, Zone* zone) { |
| 283 ASSERT(instr != NULL); | 283 DCHECK(instr != NULL); |
| 284 // Resizing when half of the hashtable is filled up. | 284 // Resizing when half of the hashtable is filled up. |
| 285 if (count_ >= array_size_ >> 1) Resize(array_size_ << 1, zone); | 285 if (count_ >= array_size_ >> 1) Resize(array_size_ << 1, zone); |
| 286 ASSERT(count_ < array_size_); | 286 DCHECK(count_ < array_size_); |
| 287 count_++; | 287 count_++; |
| 288 uint32_t pos = Bound(static_cast<uint32_t>(instr->Hashcode())); | 288 uint32_t pos = Bound(static_cast<uint32_t>(instr->Hashcode())); |
| 289 if (array_[pos].instr == NULL) { | 289 if (array_[pos].instr == NULL) { |
| 290 array_[pos].instr = instr; | 290 array_[pos].instr = instr; |
| 291 array_[pos].next = kNil; | 291 array_[pos].next = kNil; |
| 292 } else { | 292 } else { |
| 293 if (free_list_head_ == kNil) { | 293 if (free_list_head_ == kNil) { |
| 294 ResizeLists(lists_size_ << 1, zone); | 294 ResizeLists(lists_size_ << 1, zone); |
| 295 } | 295 } |
| 296 int new_element_pos = free_list_head_; | 296 int new_element_pos = free_list_head_; |
| 297 ASSERT(new_element_pos != kNil); | 297 DCHECK(new_element_pos != kNil); |
| 298 free_list_head_ = lists_[free_list_head_].next; | 298 free_list_head_ = lists_[free_list_head_].next; |
| 299 lists_[new_element_pos].instr = instr; | 299 lists_[new_element_pos].instr = instr; |
| 300 lists_[new_element_pos].next = array_[pos].next; | 300 lists_[new_element_pos].next = array_[pos].next; |
| 301 ASSERT(array_[pos].next == kNil || lists_[array_[pos].next].instr != NULL); | 301 DCHECK(array_[pos].next == kNil || lists_[array_[pos].next].instr != NULL); |
| 302 array_[pos].next = new_element_pos; | 302 array_[pos].next = new_element_pos; |
| 303 } | 303 } |
| 304 } | 304 } |
| 305 | 305 |
| 306 | 306 |
| 307 HSideEffectMap::HSideEffectMap() : count_(0) { | 307 HSideEffectMap::HSideEffectMap() : count_(0) { |
| 308 memset(data_, 0, kNumberOfTrackedSideEffects * kPointerSize); | 308 memset(data_, 0, kNumberOfTrackedSideEffects * kPointerSize); |
| 309 } | 309 } |
| 310 | 310 |
| 311 | 311 |
| (...skipping 169 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 481 return false; | 481 return false; |
| 482 } | 482 } |
| 483 | 483 |
| 484 | 484 |
| 485 HGlobalValueNumberingPhase::HGlobalValueNumberingPhase(HGraph* graph) | 485 HGlobalValueNumberingPhase::HGlobalValueNumberingPhase(HGraph* graph) |
| 486 : HPhase("H_Global value numbering", graph), | 486 : HPhase("H_Global value numbering", graph), |
| 487 removed_side_effects_(false), | 487 removed_side_effects_(false), |
| 488 block_side_effects_(graph->blocks()->length(), zone()), | 488 block_side_effects_(graph->blocks()->length(), zone()), |
| 489 loop_side_effects_(graph->blocks()->length(), zone()), | 489 loop_side_effects_(graph->blocks()->length(), zone()), |
| 490 visited_on_paths_(graph->blocks()->length(), zone()) { | 490 visited_on_paths_(graph->blocks()->length(), zone()) { |
| 491 ASSERT(!AllowHandleAllocation::IsAllowed()); | 491 DCHECK(!AllowHandleAllocation::IsAllowed()); |
| 492 block_side_effects_.AddBlock( | 492 block_side_effects_.AddBlock( |
| 493 SideEffects(), graph->blocks()->length(), zone()); | 493 SideEffects(), graph->blocks()->length(), zone()); |
| 494 loop_side_effects_.AddBlock( | 494 loop_side_effects_.AddBlock( |
| 495 SideEffects(), graph->blocks()->length(), zone()); | 495 SideEffects(), graph->blocks()->length(), zone()); |
| 496 } | 496 } |
| 497 | 497 |
| 498 | 498 |
| 499 void HGlobalValueNumberingPhase::Run() { | 499 void HGlobalValueNumberingPhase::Run() { |
| 500 ASSERT(!removed_side_effects_); | 500 DCHECK(!removed_side_effects_); |
| 501 for (int i = FLAG_gvn_iterations; i > 0; --i) { | 501 for (int i = FLAG_gvn_iterations; i > 0; --i) { |
| 502 // Compute the side effects. | 502 // Compute the side effects. |
| 503 ComputeBlockSideEffects(); | 503 ComputeBlockSideEffects(); |
| 504 | 504 |
| 505 // Perform loop invariant code motion if requested. | 505 // Perform loop invariant code motion if requested. |
| 506 if (FLAG_loop_invariant_code_motion) LoopInvariantCodeMotion(); | 506 if (FLAG_loop_invariant_code_motion) LoopInvariantCodeMotion(); |
| 507 | 507 |
| 508 // Perform the actual value numbering. | 508 // Perform the actual value numbering. |
| 509 AnalyzeGraph(); | 509 AnalyzeGraph(); |
| 510 | 510 |
| 511 // Continue GVN if we removed any side effects. | 511 // Continue GVN if we removed any side effects. |
| 512 if (!removed_side_effects_) break; | 512 if (!removed_side_effects_) break; |
| 513 removed_side_effects_ = false; | 513 removed_side_effects_ = false; |
| 514 | 514 |
| 515 // Clear all side effects. | 515 // Clear all side effects. |
| 516 ASSERT_EQ(block_side_effects_.length(), graph()->blocks()->length()); | 516 DCHECK_EQ(block_side_effects_.length(), graph()->blocks()->length()); |
| 517 ASSERT_EQ(loop_side_effects_.length(), graph()->blocks()->length()); | 517 DCHECK_EQ(loop_side_effects_.length(), graph()->blocks()->length()); |
| 518 for (int i = 0; i < graph()->blocks()->length(); ++i) { | 518 for (int i = 0; i < graph()->blocks()->length(); ++i) { |
| 519 block_side_effects_[i].RemoveAll(); | 519 block_side_effects_[i].RemoveAll(); |
| 520 loop_side_effects_[i].RemoveAll(); | 520 loop_side_effects_[i].RemoveAll(); |
| 521 } | 521 } |
| 522 visited_on_paths_.Clear(); | 522 visited_on_paths_.Clear(); |
| 523 } | 523 } |
| 524 } | 524 } |
| 525 | 525 |
| 526 | 526 |
| 527 void HGlobalValueNumberingPhase::ComputeBlockSideEffects() { | 527 void HGlobalValueNumberingPhase::ComputeBlockSideEffects() { |
| (...skipping 306 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 834 map->Kill(changes); | 834 map->Kill(changes); |
| 835 dominators->Store(changes, instr); | 835 dominators->Store(changes, instr); |
| 836 if (FLAG_trace_gvn) { | 836 if (FLAG_trace_gvn) { |
| 837 OFStream os(stdout); | 837 OFStream os(stdout); |
| 838 os << "Instruction i" << instr->id() << " changes " << Print(changes) | 838 os << "Instruction i" << instr->id() << " changes " << Print(changes) |
| 839 << endl; | 839 << endl; |
| 840 } | 840 } |
| 841 } | 841 } |
| 842 if (instr->CheckFlag(HValue::kUseGVN) && | 842 if (instr->CheckFlag(HValue::kUseGVN) && |
| 843 !instr->CheckFlag(HValue::kCantBeReplaced)) { | 843 !instr->CheckFlag(HValue::kCantBeReplaced)) { |
| 844 ASSERT(!instr->HasObservableSideEffects()); | 844 DCHECK(!instr->HasObservableSideEffects()); |
| 845 HInstruction* other = map->Lookup(instr); | 845 HInstruction* other = map->Lookup(instr); |
| 846 if (other != NULL) { | 846 if (other != NULL) { |
| 847 ASSERT(instr->Equals(other) && other->Equals(instr)); | 847 DCHECK(instr->Equals(other) && other->Equals(instr)); |
| 848 TRACE_GVN_4("Replacing instruction i%d (%s) with i%d (%s)\n", | 848 TRACE_GVN_4("Replacing instruction i%d (%s) with i%d (%s)\n", |
| 849 instr->id(), | 849 instr->id(), |
| 850 instr->Mnemonic(), | 850 instr->Mnemonic(), |
| 851 other->id(), | 851 other->id(), |
| 852 other->Mnemonic()); | 852 other->Mnemonic()); |
| 853 if (instr->HasSideEffects()) removed_side_effects_ = true; | 853 if (instr->HasSideEffects()) removed_side_effects_ = true; |
| 854 instr->DeleteAndReplaceWith(other); | 854 instr->DeleteAndReplaceWith(other); |
| 855 } else { | 855 } else { |
| 856 map->Add(instr, zone()); | 856 map->Add(instr, zone()); |
| 857 } | 857 } |
| (...skipping 23 matching lines...) Expand all Loading... |
| 881 dominated); | 881 dominated); |
| 882 successor_map->Kill(side_effects_on_all_paths); | 882 successor_map->Kill(side_effects_on_all_paths); |
| 883 successor_dominators->Kill(side_effects_on_all_paths); | 883 successor_dominators->Kill(side_effects_on_all_paths); |
| 884 } | 884 } |
| 885 } | 885 } |
| 886 current = next; | 886 current = next; |
| 887 } | 887 } |
| 888 } | 888 } |
| 889 | 889 |
| 890 } } // namespace v8::internal | 890 } } // namespace v8::internal |
| OLD | NEW |