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 |