verwaest@chromium.org | d4be0f0 | 2013-06-05 13:39:03 +0000 | [diff] [blame] | 1 | // Copyright 2013 the V8 project authors. All rights reserved. |
| 2 | // Redistribution and use in source and binary forms, with or without |
| 3 | // modification, are permitted provided that the following conditions are |
| 4 | // met: |
| 5 | // |
| 6 | // * Redistributions of source code must retain the above copyright |
| 7 | // notice, this list of conditions and the following disclaimer. |
| 8 | // * Redistributions in binary form must reproduce the above |
| 9 | // copyright notice, this list of conditions and the following |
| 10 | // disclaimer in the documentation and/or other materials provided |
| 11 | // with the distribution. |
| 12 | // * Neither the name of Google Inc. nor the names of its |
| 13 | // contributors may be used to endorse or promote products derived |
| 14 | // from this software without specific prior written permission. |
| 15 | // |
| 16 | // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
| 17 | // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
| 18 | // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
| 19 | // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT |
| 20 | // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
| 21 | // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT |
| 22 | // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
| 23 | // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
| 24 | // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
| 25 | // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
| 26 | // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| 27 | |
| 28 | |
| 29 | #include "hydrogen-environment-liveness.h" |
| 30 | |
| 31 | |
| 32 | namespace v8 { |
| 33 | namespace internal { |
| 34 | |
| 35 | |
mstarzinger@chromium.org | 1510d58 | 2013-06-28 14:00:48 +0000 | [diff] [blame] | 36 | HEnvironmentLivenessAnalysisPhase::HEnvironmentLivenessAnalysisPhase( |
verwaest@chromium.org | d4be0f0 | 2013-06-05 13:39:03 +0000 | [diff] [blame] | 37 | HGraph* graph) |
mstarzinger@chromium.org | 1510d58 | 2013-06-28 14:00:48 +0000 | [diff] [blame] | 38 | : HPhase("H_Environment liveness analysis", graph), |
verwaest@chromium.org | d4be0f0 | 2013-06-05 13:39:03 +0000 | [diff] [blame] | 39 | block_count_(graph->blocks()->length()), |
| 40 | maximum_environment_size_(graph->maximum_environment_size()), |
mstarzinger@chromium.org | 1510d58 | 2013-06-28 14:00:48 +0000 | [diff] [blame] | 41 | live_at_block_start_(block_count_, zone()), |
| 42 | first_simulate_(block_count_, zone()), |
| 43 | first_simulate_invalid_for_index_(block_count_, zone()), |
| 44 | markers_(maximum_environment_size_, zone()), |
verwaest@chromium.org | d4be0f0 | 2013-06-05 13:39:03 +0000 | [diff] [blame] | 45 | collect_markers_(true), |
mstarzinger@chromium.org | 1510d58 | 2013-06-28 14:00:48 +0000 | [diff] [blame] | 46 | last_simulate_(NULL), |
| 47 | went_live_since_last_simulate_(maximum_environment_size_, zone()) { |
| 48 | ASSERT(maximum_environment_size_ > 0); |
verwaest@chromium.org | d4be0f0 | 2013-06-05 13:39:03 +0000 | [diff] [blame] | 49 | for (int i = 0; i < block_count_; ++i) { |
mstarzinger@chromium.org | 1510d58 | 2013-06-28 14:00:48 +0000 | [diff] [blame] | 50 | live_at_block_start_.Add( |
verwaest@chromium.org | d4be0f0 | 2013-06-05 13:39:03 +0000 | [diff] [blame] | 51 | new(zone()) BitVector(maximum_environment_size_, zone()), zone()); |
mstarzinger@chromium.org | 1510d58 | 2013-06-28 14:00:48 +0000 | [diff] [blame] | 52 | first_simulate_.Add(NULL, zone()); |
| 53 | first_simulate_invalid_for_index_.Add( |
verwaest@chromium.org | d4be0f0 | 2013-06-05 13:39:03 +0000 | [diff] [blame] | 54 | new(zone()) BitVector(maximum_environment_size_, zone()), zone()); |
| 55 | } |
| 56 | } |
| 57 | |
| 58 | |
mstarzinger@chromium.org | 1510d58 | 2013-06-28 14:00:48 +0000 | [diff] [blame] | 59 | void HEnvironmentLivenessAnalysisPhase::ZapEnvironmentSlot( |
| 60 | int index, HSimulate* simulate) { |
verwaest@chromium.org | d4be0f0 | 2013-06-05 13:39:03 +0000 | [diff] [blame] | 61 | int operand_index = simulate->ToOperandIndex(index); |
| 62 | if (operand_index == -1) { |
mstarzinger@chromium.org | 1510d58 | 2013-06-28 14:00:48 +0000 | [diff] [blame] | 63 | simulate->AddAssignedValue(index, graph()->GetConstantUndefined()); |
verwaest@chromium.org | d4be0f0 | 2013-06-05 13:39:03 +0000 | [diff] [blame] | 64 | } else { |
mstarzinger@chromium.org | 1510d58 | 2013-06-28 14:00:48 +0000 | [diff] [blame] | 65 | simulate->SetOperandAt(operand_index, graph()->GetConstantUndefined()); |
verwaest@chromium.org | d4be0f0 | 2013-06-05 13:39:03 +0000 | [diff] [blame] | 66 | } |
| 67 | } |
| 68 | |
| 69 | |
mstarzinger@chromium.org | 1510d58 | 2013-06-28 14:00:48 +0000 | [diff] [blame] | 70 | void HEnvironmentLivenessAnalysisPhase::ZapEnvironmentSlotsInSuccessors( |
| 71 | HBasicBlock* block, BitVector* live) { |
verwaest@chromium.org | d4be0f0 | 2013-06-05 13:39:03 +0000 | [diff] [blame] | 72 | // When a value is live in successor A but dead in B, we must |
| 73 | // explicitly zap it in B. |
| 74 | for (HSuccessorIterator it(block->end()); !it.Done(); it.Advance()) { |
| 75 | HBasicBlock* successor = it.Current(); |
| 76 | int successor_id = successor->block_id(); |
mstarzinger@chromium.org | 1510d58 | 2013-06-28 14:00:48 +0000 | [diff] [blame] | 77 | BitVector* live_in_successor = live_at_block_start_[successor_id]; |
verwaest@chromium.org | d4be0f0 | 2013-06-05 13:39:03 +0000 | [diff] [blame] | 78 | if (live_in_successor->Equals(*live)) continue; |
| 79 | for (int i = 0; i < live->length(); ++i) { |
| 80 | if (!live->Contains(i)) continue; |
| 81 | if (live_in_successor->Contains(i)) continue; |
mstarzinger@chromium.org | 1510d58 | 2013-06-28 14:00:48 +0000 | [diff] [blame] | 82 | if (first_simulate_invalid_for_index_.at(successor_id)->Contains(i)) { |
verwaest@chromium.org | d4be0f0 | 2013-06-05 13:39:03 +0000 | [diff] [blame] | 83 | continue; |
| 84 | } |
mstarzinger@chromium.org | 1510d58 | 2013-06-28 14:00:48 +0000 | [diff] [blame] | 85 | HSimulate* simulate = first_simulate_.at(successor_id); |
verwaest@chromium.org | d4be0f0 | 2013-06-05 13:39:03 +0000 | [diff] [blame] | 86 | if (simulate == NULL) continue; |
| 87 | ASSERT(simulate->closure().is_identical_to( |
| 88 | block->last_environment()->closure())); |
| 89 | ZapEnvironmentSlot(i, simulate); |
| 90 | } |
| 91 | } |
| 92 | } |
| 93 | |
| 94 | |
mstarzinger@chromium.org | 1510d58 | 2013-06-28 14:00:48 +0000 | [diff] [blame] | 95 | void HEnvironmentLivenessAnalysisPhase::ZapEnvironmentSlotsForInstruction( |
verwaest@chromium.org | d4be0f0 | 2013-06-05 13:39:03 +0000 | [diff] [blame] | 96 | HEnvironmentMarker* marker) { |
| 97 | if (!marker->CheckFlag(HValue::kEndsLiveRange)) return; |
| 98 | HSimulate* simulate = marker->next_simulate(); |
| 99 | if (simulate != NULL) { |
| 100 | ASSERT(simulate->closure().is_identical_to(marker->closure())); |
| 101 | ZapEnvironmentSlot(marker->index(), simulate); |
| 102 | } |
| 103 | } |
| 104 | |
| 105 | |
mstarzinger@chromium.org | 1510d58 | 2013-06-28 14:00:48 +0000 | [diff] [blame] | 106 | void HEnvironmentLivenessAnalysisPhase::UpdateLivenessAtBlockEnd( |
verwaest@chromium.org | d4be0f0 | 2013-06-05 13:39:03 +0000 | [diff] [blame] | 107 | HBasicBlock* block, |
| 108 | BitVector* live) { |
| 109 | // Liveness at the end of each block: union of liveness in successors. |
| 110 | live->Clear(); |
| 111 | for (HSuccessorIterator it(block->end()); !it.Done(); it.Advance()) { |
mstarzinger@chromium.org | 1510d58 | 2013-06-28 14:00:48 +0000 | [diff] [blame] | 112 | live->Union(*live_at_block_start_[it.Current()->block_id()]); |
verwaest@chromium.org | d4be0f0 | 2013-06-05 13:39:03 +0000 | [diff] [blame] | 113 | } |
| 114 | } |
| 115 | |
| 116 | |
mstarzinger@chromium.org | 1510d58 | 2013-06-28 14:00:48 +0000 | [diff] [blame] | 117 | void HEnvironmentLivenessAnalysisPhase::UpdateLivenessAtInstruction( |
verwaest@chromium.org | d4be0f0 | 2013-06-05 13:39:03 +0000 | [diff] [blame] | 118 | HInstruction* instr, |
| 119 | BitVector* live) { |
| 120 | switch (instr->opcode()) { |
| 121 | case HValue::kEnvironmentMarker: { |
| 122 | HEnvironmentMarker* marker = HEnvironmentMarker::cast(instr); |
| 123 | int index = marker->index(); |
| 124 | if (!live->Contains(index)) { |
| 125 | marker->SetFlag(HValue::kEndsLiveRange); |
| 126 | } else { |
| 127 | marker->ClearFlag(HValue::kEndsLiveRange); |
| 128 | } |
mstarzinger@chromium.org | 1510d58 | 2013-06-28 14:00:48 +0000 | [diff] [blame] | 129 | if (!went_live_since_last_simulate_.Contains(index)) { |
verwaest@chromium.org | d4be0f0 | 2013-06-05 13:39:03 +0000 | [diff] [blame] | 130 | marker->set_next_simulate(last_simulate_); |
| 131 | } |
| 132 | if (marker->kind() == HEnvironmentMarker::LOOKUP) { |
| 133 | live->Add(index); |
| 134 | } else { |
| 135 | ASSERT(marker->kind() == HEnvironmentMarker::BIND); |
| 136 | live->Remove(index); |
mstarzinger@chromium.org | 1510d58 | 2013-06-28 14:00:48 +0000 | [diff] [blame] | 137 | went_live_since_last_simulate_.Add(index); |
verwaest@chromium.org | d4be0f0 | 2013-06-05 13:39:03 +0000 | [diff] [blame] | 138 | } |
| 139 | if (collect_markers_) { |
| 140 | // Populate |markers_| list during the first pass. |
mstarzinger@chromium.org | 1510d58 | 2013-06-28 14:00:48 +0000 | [diff] [blame] | 141 | markers_.Add(marker, zone()); |
verwaest@chromium.org | d4be0f0 | 2013-06-05 13:39:03 +0000 | [diff] [blame] | 142 | } |
| 143 | break; |
| 144 | } |
| 145 | case HValue::kLeaveInlined: |
| 146 | // No environment values are live at the end of an inlined section. |
| 147 | live->Clear(); |
| 148 | last_simulate_ = NULL; |
| 149 | |
| 150 | // The following ASSERTs guard the assumption used in case |
| 151 | // kEnterInlined below: |
| 152 | ASSERT(instr->next()->IsSimulate()); |
| 153 | ASSERT(instr->next()->next()->IsGoto()); |
| 154 | |
| 155 | break; |
| 156 | case HValue::kEnterInlined: { |
| 157 | // Those environment values are live that are live at any return |
| 158 | // target block. Here we make use of the fact that the end of an |
| 159 | // inline sequence always looks like this: HLeaveInlined, HSimulate, |
| 160 | // HGoto (to return_target block), with no environment lookups in |
| 161 | // between (see ASSERTs above). |
| 162 | HEnterInlined* enter = HEnterInlined::cast(instr); |
| 163 | live->Clear(); |
| 164 | for (int i = 0; i < enter->return_targets()->length(); ++i) { |
| 165 | int return_id = enter->return_targets()->at(i)->block_id(); |
mstarzinger@chromium.org | 1f410f9 | 2013-08-29 08:13:16 +0000 | [diff] [blame] | 166 | live->Union(*live_at_block_start_[return_id]); |
verwaest@chromium.org | d4be0f0 | 2013-06-05 13:39:03 +0000 | [diff] [blame] | 167 | } |
| 168 | last_simulate_ = NULL; |
| 169 | break; |
| 170 | } |
verwaest@chromium.org | d4be0f0 | 2013-06-05 13:39:03 +0000 | [diff] [blame] | 171 | case HValue::kSimulate: |
| 172 | last_simulate_ = HSimulate::cast(instr); |
mstarzinger@chromium.org | 1510d58 | 2013-06-28 14:00:48 +0000 | [diff] [blame] | 173 | went_live_since_last_simulate_.Clear(); |
verwaest@chromium.org | d4be0f0 | 2013-06-05 13:39:03 +0000 | [diff] [blame] | 174 | break; |
| 175 | default: |
| 176 | break; |
| 177 | } |
| 178 | } |
| 179 | |
| 180 | |
mstarzinger@chromium.org | 1510d58 | 2013-06-28 14:00:48 +0000 | [diff] [blame] | 181 | void HEnvironmentLivenessAnalysisPhase::Run() { |
| 182 | ASSERT(maximum_environment_size_ > 0); |
verwaest@chromium.org | d4be0f0 | 2013-06-05 13:39:03 +0000 | [diff] [blame] | 183 | |
| 184 | // Main iteration. Compute liveness of environment slots, and store it |
| 185 | // for each block until it doesn't change any more. For efficiency, visit |
| 186 | // blocks in reverse order and walk backwards through each block. We |
| 187 | // need several iterations to propagate liveness through nested loops. |
mstarzinger@chromium.org | 1510d58 | 2013-06-28 14:00:48 +0000 | [diff] [blame] | 188 | BitVector live(maximum_environment_size_, zone()); |
| 189 | BitVector worklist(block_count_, zone()); |
verwaest@chromium.org | d4be0f0 | 2013-06-05 13:39:03 +0000 | [diff] [blame] | 190 | for (int i = 0; i < block_count_; ++i) { |
mstarzinger@chromium.org | 1510d58 | 2013-06-28 14:00:48 +0000 | [diff] [blame] | 191 | worklist.Add(i); |
verwaest@chromium.org | d4be0f0 | 2013-06-05 13:39:03 +0000 | [diff] [blame] | 192 | } |
mstarzinger@chromium.org | 1510d58 | 2013-06-28 14:00:48 +0000 | [diff] [blame] | 193 | while (!worklist.IsEmpty()) { |
verwaest@chromium.org | d4be0f0 | 2013-06-05 13:39:03 +0000 | [diff] [blame] | 194 | for (int block_id = block_count_ - 1; block_id >= 0; --block_id) { |
mstarzinger@chromium.org | 1510d58 | 2013-06-28 14:00:48 +0000 | [diff] [blame] | 195 | if (!worklist.Contains(block_id)) { |
verwaest@chromium.org | d4be0f0 | 2013-06-05 13:39:03 +0000 | [diff] [blame] | 196 | continue; |
| 197 | } |
mstarzinger@chromium.org | 1510d58 | 2013-06-28 14:00:48 +0000 | [diff] [blame] | 198 | worklist.Remove(block_id); |
verwaest@chromium.org | d4be0f0 | 2013-06-05 13:39:03 +0000 | [diff] [blame] | 199 | last_simulate_ = NULL; |
| 200 | |
mstarzinger@chromium.org | 1510d58 | 2013-06-28 14:00:48 +0000 | [diff] [blame] | 201 | HBasicBlock* block = graph()->blocks()->at(block_id); |
| 202 | UpdateLivenessAtBlockEnd(block, &live); |
verwaest@chromium.org | d4be0f0 | 2013-06-05 13:39:03 +0000 | [diff] [blame] | 203 | |
| 204 | for (HInstruction* instr = block->last(); instr != NULL; |
| 205 | instr = instr->previous()) { |
mstarzinger@chromium.org | 1510d58 | 2013-06-28 14:00:48 +0000 | [diff] [blame] | 206 | UpdateLivenessAtInstruction(instr, &live); |
verwaest@chromium.org | d4be0f0 | 2013-06-05 13:39:03 +0000 | [diff] [blame] | 207 | } |
| 208 | |
| 209 | // Reached the start of the block, do necessary bookkeeping: |
| 210 | // store computed information for this block and add predecessors |
| 211 | // to the work list as necessary. |
mstarzinger@chromium.org | 1510d58 | 2013-06-28 14:00:48 +0000 | [diff] [blame] | 212 | first_simulate_.Set(block_id, last_simulate_); |
| 213 | first_simulate_invalid_for_index_[block_id]->CopyFrom( |
| 214 | went_live_since_last_simulate_); |
| 215 | if (live_at_block_start_[block_id]->UnionIsChanged(live)) { |
verwaest@chromium.org | d4be0f0 | 2013-06-05 13:39:03 +0000 | [diff] [blame] | 216 | for (int i = 0; i < block->predecessors()->length(); ++i) { |
mstarzinger@chromium.org | 1510d58 | 2013-06-28 14:00:48 +0000 | [diff] [blame] | 217 | worklist.Add(block->predecessors()->at(i)->block_id()); |
verwaest@chromium.org | d4be0f0 | 2013-06-05 13:39:03 +0000 | [diff] [blame] | 218 | } |
| 219 | if (block->IsInlineReturnTarget()) { |
mstarzinger@chromium.org | 1510d58 | 2013-06-28 14:00:48 +0000 | [diff] [blame] | 220 | worklist.Add(block->inlined_entry_block()->block_id()); |
verwaest@chromium.org | d4be0f0 | 2013-06-05 13:39:03 +0000 | [diff] [blame] | 221 | } |
| 222 | } |
| 223 | } |
| 224 | // Only collect bind/lookup instructions during the first pass. |
| 225 | collect_markers_ = false; |
| 226 | } |
| 227 | |
| 228 | // Analysis finished. Zap dead environment slots. |
mstarzinger@chromium.org | 1510d58 | 2013-06-28 14:00:48 +0000 | [diff] [blame] | 229 | for (int i = 0; i < markers_.length(); ++i) { |
| 230 | ZapEnvironmentSlotsForInstruction(markers_[i]); |
verwaest@chromium.org | d4be0f0 | 2013-06-05 13:39:03 +0000 | [diff] [blame] | 231 | } |
| 232 | for (int block_id = block_count_ - 1; block_id >= 0; --block_id) { |
mstarzinger@chromium.org | 1510d58 | 2013-06-28 14:00:48 +0000 | [diff] [blame] | 233 | HBasicBlock* block = graph()->blocks()->at(block_id); |
| 234 | UpdateLivenessAtBlockEnd(block, &live); |
| 235 | ZapEnvironmentSlotsInSuccessors(block, &live); |
verwaest@chromium.org | d4be0f0 | 2013-06-05 13:39:03 +0000 | [diff] [blame] | 236 | } |
| 237 | |
| 238 | // Finally, remove the HEnvironment{Bind,Lookup} markers. |
mstarzinger@chromium.org | 1510d58 | 2013-06-28 14:00:48 +0000 | [diff] [blame] | 239 | for (int i = 0; i < markers_.length(); ++i) { |
| 240 | markers_[i]->DeleteAndReplaceWith(NULL); |
verwaest@chromium.org | d4be0f0 | 2013-06-05 13:39:03 +0000 | [diff] [blame] | 241 | } |
| 242 | } |
| 243 | |
| 244 | } } // namespace v8::internal |