| 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 | 5 |
| 6 #include "src/hydrogen-environment-liveness.h" | 6 #include "src/hydrogen-environment-liveness.h" |
| 7 | 7 |
| 8 | 8 |
| 9 namespace v8 { | 9 namespace v8 { |
| 10 namespace internal { | 10 namespace internal { |
| 11 | 11 |
| 12 | 12 |
| 13 HEnvironmentLivenessAnalysisPhase::HEnvironmentLivenessAnalysisPhase( | 13 HEnvironmentLivenessAnalysisPhase::HEnvironmentLivenessAnalysisPhase( |
| 14 HGraph* graph) | 14 HGraph* graph) |
| 15 : HPhase("H_Environment liveness analysis", graph), | 15 : HPhase("H_Environment liveness analysis", graph), |
| 16 block_count_(graph->blocks()->length()), | 16 block_count_(graph->blocks()->length()), |
| 17 maximum_environment_size_(graph->maximum_environment_size()), | 17 maximum_environment_size_(graph->maximum_environment_size()), |
| 18 live_at_block_start_(block_count_, zone()), | 18 live_at_block_start_(block_count_, zone()), |
| 19 first_simulate_(block_count_, zone()), | 19 first_simulate_(block_count_, zone()), |
| 20 first_simulate_invalid_for_index_(block_count_, zone()), | 20 first_simulate_invalid_for_index_(block_count_, zone()), |
| 21 markers_(maximum_environment_size_, zone()), | 21 markers_(maximum_environment_size_, zone()), |
| 22 collect_markers_(true), | 22 collect_markers_(true), |
| 23 last_simulate_(NULL), | 23 last_simulate_(NULL), |
| 24 went_live_since_last_simulate_(maximum_environment_size_, zone()) { | 24 went_live_since_last_simulate_(maximum_environment_size_, zone()) { |
| 25 ASSERT(maximum_environment_size_ > 0); | 25 DCHECK(maximum_environment_size_ > 0); |
| 26 for (int i = 0; i < block_count_; ++i) { | 26 for (int i = 0; i < block_count_; ++i) { |
| 27 live_at_block_start_.Add( | 27 live_at_block_start_.Add( |
| 28 new(zone()) BitVector(maximum_environment_size_, zone()), zone()); | 28 new(zone()) BitVector(maximum_environment_size_, zone()), zone()); |
| 29 first_simulate_.Add(NULL, zone()); | 29 first_simulate_.Add(NULL, zone()); |
| 30 first_simulate_invalid_for_index_.Add( | 30 first_simulate_invalid_for_index_.Add( |
| 31 new(zone()) BitVector(maximum_environment_size_, zone()), zone()); | 31 new(zone()) BitVector(maximum_environment_size_, zone()), zone()); |
| 32 } | 32 } |
| 33 } | 33 } |
| 34 | 34 |
| 35 | 35 |
| (...skipping 18 matching lines...) Expand all Loading... |
| 54 BitVector* live_in_successor = live_at_block_start_[successor_id]; | 54 BitVector* live_in_successor = live_at_block_start_[successor_id]; |
| 55 if (live_in_successor->Equals(*live)) continue; | 55 if (live_in_successor->Equals(*live)) continue; |
| 56 for (int i = 0; i < live->length(); ++i) { | 56 for (int i = 0; i < live->length(); ++i) { |
| 57 if (!live->Contains(i)) continue; | 57 if (!live->Contains(i)) continue; |
| 58 if (live_in_successor->Contains(i)) continue; | 58 if (live_in_successor->Contains(i)) continue; |
| 59 if (first_simulate_invalid_for_index_.at(successor_id)->Contains(i)) { | 59 if (first_simulate_invalid_for_index_.at(successor_id)->Contains(i)) { |
| 60 continue; | 60 continue; |
| 61 } | 61 } |
| 62 HSimulate* simulate = first_simulate_.at(successor_id); | 62 HSimulate* simulate = first_simulate_.at(successor_id); |
| 63 if (simulate == NULL) continue; | 63 if (simulate == NULL) continue; |
| 64 ASSERT(VerifyClosures(simulate->closure(), | 64 DCHECK(VerifyClosures(simulate->closure(), |
| 65 block->last_environment()->closure())); | 65 block->last_environment()->closure())); |
| 66 ZapEnvironmentSlot(i, simulate); | 66 ZapEnvironmentSlot(i, simulate); |
| 67 } | 67 } |
| 68 } | 68 } |
| 69 } | 69 } |
| 70 | 70 |
| 71 | 71 |
| 72 void HEnvironmentLivenessAnalysisPhase::ZapEnvironmentSlotsForInstruction( | 72 void HEnvironmentLivenessAnalysisPhase::ZapEnvironmentSlotsForInstruction( |
| 73 HEnvironmentMarker* marker) { | 73 HEnvironmentMarker* marker) { |
| 74 if (!marker->CheckFlag(HValue::kEndsLiveRange)) return; | 74 if (!marker->CheckFlag(HValue::kEndsLiveRange)) return; |
| 75 HSimulate* simulate = marker->next_simulate(); | 75 HSimulate* simulate = marker->next_simulate(); |
| 76 if (simulate != NULL) { | 76 if (simulate != NULL) { |
| 77 ASSERT(VerifyClosures(simulate->closure(), marker->closure())); | 77 DCHECK(VerifyClosures(simulate->closure(), marker->closure())); |
| 78 ZapEnvironmentSlot(marker->index(), simulate); | 78 ZapEnvironmentSlot(marker->index(), simulate); |
| 79 } | 79 } |
| 80 } | 80 } |
| 81 | 81 |
| 82 | 82 |
| 83 void HEnvironmentLivenessAnalysisPhase::UpdateLivenessAtBlockEnd( | 83 void HEnvironmentLivenessAnalysisPhase::UpdateLivenessAtBlockEnd( |
| 84 HBasicBlock* block, | 84 HBasicBlock* block, |
| 85 BitVector* live) { | 85 BitVector* live) { |
| 86 // Liveness at the end of each block: union of liveness in successors. | 86 // Liveness at the end of each block: union of liveness in successors. |
| 87 live->Clear(); | 87 live->Clear(); |
| (...skipping 14 matching lines...) Expand all Loading... |
| 102 marker->SetFlag(HValue::kEndsLiveRange); | 102 marker->SetFlag(HValue::kEndsLiveRange); |
| 103 } else { | 103 } else { |
| 104 marker->ClearFlag(HValue::kEndsLiveRange); | 104 marker->ClearFlag(HValue::kEndsLiveRange); |
| 105 } | 105 } |
| 106 if (!went_live_since_last_simulate_.Contains(index)) { | 106 if (!went_live_since_last_simulate_.Contains(index)) { |
| 107 marker->set_next_simulate(last_simulate_); | 107 marker->set_next_simulate(last_simulate_); |
| 108 } | 108 } |
| 109 if (marker->kind() == HEnvironmentMarker::LOOKUP) { | 109 if (marker->kind() == HEnvironmentMarker::LOOKUP) { |
| 110 live->Add(index); | 110 live->Add(index); |
| 111 } else { | 111 } else { |
| 112 ASSERT(marker->kind() == HEnvironmentMarker::BIND); | 112 DCHECK(marker->kind() == HEnvironmentMarker::BIND); |
| 113 live->Remove(index); | 113 live->Remove(index); |
| 114 went_live_since_last_simulate_.Add(index); | 114 went_live_since_last_simulate_.Add(index); |
| 115 } | 115 } |
| 116 if (collect_markers_) { | 116 if (collect_markers_) { |
| 117 // Populate |markers_| list during the first pass. | 117 // Populate |markers_| list during the first pass. |
| 118 markers_.Add(marker, zone()); | 118 markers_.Add(marker, zone()); |
| 119 } | 119 } |
| 120 break; | 120 break; |
| 121 } | 121 } |
| 122 case HValue::kLeaveInlined: | 122 case HValue::kLeaveInlined: |
| 123 // No environment values are live at the end of an inlined section. | 123 // No environment values are live at the end of an inlined section. |
| 124 live->Clear(); | 124 live->Clear(); |
| 125 last_simulate_ = NULL; | 125 last_simulate_ = NULL; |
| 126 | 126 |
| 127 // The following ASSERTs guard the assumption used in case | 127 // The following DCHECKs guard the assumption used in case |
| 128 // kEnterInlined below: | 128 // kEnterInlined below: |
| 129 ASSERT(instr->next()->IsSimulate()); | 129 DCHECK(instr->next()->IsSimulate()); |
| 130 ASSERT(instr->next()->next()->IsGoto()); | 130 DCHECK(instr->next()->next()->IsGoto()); |
| 131 | 131 |
| 132 break; | 132 break; |
| 133 case HValue::kEnterInlined: { | 133 case HValue::kEnterInlined: { |
| 134 // Those environment values are live that are live at any return | 134 // Those environment values are live that are live at any return |
| 135 // target block. Here we make use of the fact that the end of an | 135 // target block. Here we make use of the fact that the end of an |
| 136 // inline sequence always looks like this: HLeaveInlined, HSimulate, | 136 // inline sequence always looks like this: HLeaveInlined, HSimulate, |
| 137 // HGoto (to return_target block), with no environment lookups in | 137 // HGoto (to return_target block), with no environment lookups in |
| 138 // between (see ASSERTs above). | 138 // between (see DCHECKs above). |
| 139 HEnterInlined* enter = HEnterInlined::cast(instr); | 139 HEnterInlined* enter = HEnterInlined::cast(instr); |
| 140 live->Clear(); | 140 live->Clear(); |
| 141 for (int i = 0; i < enter->return_targets()->length(); ++i) { | 141 for (int i = 0; i < enter->return_targets()->length(); ++i) { |
| 142 int return_id = enter->return_targets()->at(i)->block_id(); | 142 int return_id = enter->return_targets()->at(i)->block_id(); |
| 143 live->Union(*live_at_block_start_[return_id]); | 143 live->Union(*live_at_block_start_[return_id]); |
| 144 } | 144 } |
| 145 last_simulate_ = NULL; | 145 last_simulate_ = NULL; |
| 146 break; | 146 break; |
| 147 } | 147 } |
| 148 case HValue::kSimulate: | 148 case HValue::kSimulate: |
| 149 last_simulate_ = HSimulate::cast(instr); | 149 last_simulate_ = HSimulate::cast(instr); |
| 150 went_live_since_last_simulate_.Clear(); | 150 went_live_since_last_simulate_.Clear(); |
| 151 break; | 151 break; |
| 152 default: | 152 default: |
| 153 break; | 153 break; |
| 154 } | 154 } |
| 155 } | 155 } |
| 156 | 156 |
| 157 | 157 |
| 158 void HEnvironmentLivenessAnalysisPhase::Run() { | 158 void HEnvironmentLivenessAnalysisPhase::Run() { |
| 159 ASSERT(maximum_environment_size_ > 0); | 159 DCHECK(maximum_environment_size_ > 0); |
| 160 | 160 |
| 161 // Main iteration. Compute liveness of environment slots, and store it | 161 // Main iteration. Compute liveness of environment slots, and store it |
| 162 // for each block until it doesn't change any more. For efficiency, visit | 162 // for each block until it doesn't change any more. For efficiency, visit |
| 163 // blocks in reverse order and walk backwards through each block. We | 163 // blocks in reverse order and walk backwards through each block. We |
| 164 // need several iterations to propagate liveness through nested loops. | 164 // need several iterations to propagate liveness through nested loops. |
| 165 BitVector live(maximum_environment_size_, zone()); | 165 BitVector live(maximum_environment_size_, zone()); |
| 166 BitVector worklist(block_count_, zone()); | 166 BitVector worklist(block_count_, zone()); |
| 167 for (int i = 0; i < block_count_; ++i) { | 167 for (int i = 0; i < block_count_; ++i) { |
| 168 worklist.Add(i); | 168 worklist.Add(i); |
| 169 } | 169 } |
| (...skipping 52 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 222 #ifdef DEBUG | 222 #ifdef DEBUG |
| 223 bool HEnvironmentLivenessAnalysisPhase::VerifyClosures( | 223 bool HEnvironmentLivenessAnalysisPhase::VerifyClosures( |
| 224 Handle<JSFunction> a, Handle<JSFunction> b) { | 224 Handle<JSFunction> a, Handle<JSFunction> b) { |
| 225 Heap::RelocationLock for_heap_access(isolate()->heap()); | 225 Heap::RelocationLock for_heap_access(isolate()->heap()); |
| 226 AllowHandleDereference for_verification; | 226 AllowHandleDereference for_verification; |
| 227 return a.is_identical_to(b); | 227 return a.is_identical_to(b); |
| 228 } | 228 } |
| 229 #endif | 229 #endif |
| 230 | 230 |
| 231 } } // namespace v8::internal | 231 } } // namespace v8::internal |
| OLD | NEW |