| 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 |