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 32namespace v8 { 33namespace internal { 34 35 36HEnvironmentLivenessAnalysisPhase::HEnvironmentLivenessAnalysisPhase( 37 HGraph* graph) 38 : HPhase("H_Environment liveness analysis", graph), 39 block_count_(graph->blocks()->length()), 40 maximum_environment_size_(graph->maximum_environment_size()), 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()), 45 collect_markers_(true), 46 last_simulate_(NULL), 47 went_live_since_last_simulate_(maximum_environment_size_, zone()) { 48 ASSERT(maximum_environment_size_ > 0); 49 for (int i = 0; i < block_count_; ++i) { 50 live_at_block_start_.Add( 51 new(zone()) BitVector(maximum_environment_size_, zone()), zone()); 52 first_simulate_.Add(NULL, zone()); 53 first_simulate_invalid_for_index_.Add( 54 new(zone()) BitVector(maximum_environment_size_, zone()), zone()); 55 } 56} 57 58 59void HEnvironmentLivenessAnalysisPhase::ZapEnvironmentSlot( 60 int index, HSimulate* simulate) { 61 int operand_index = simulate->ToOperandIndex(index); 62 if (operand_index == -1) { 63 simulate->AddAssignedValue(index, graph()->GetConstantUndefined()); 64 } else { 65 simulate->SetOperandAt(operand_index, graph()->GetConstantUndefined()); 66 } 67} 68 69 70void HEnvironmentLivenessAnalysisPhase::ZapEnvironmentSlotsInSuccessors( 71 HBasicBlock* block, BitVector* live) { 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(); 77 BitVector* live_in_successor = live_at_block_start_[successor_id]; 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; 82 if (first_simulate_invalid_for_index_.at(successor_id)->Contains(i)) { 83 continue; 84 } 85 HSimulate* simulate = first_simulate_.at(successor_id); 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 95void HEnvironmentLivenessAnalysisPhase::ZapEnvironmentSlotsForInstruction( 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 106void HEnvironmentLivenessAnalysisPhase::UpdateLivenessAtBlockEnd( 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()) { 112 live->Union(*live_at_block_start_[it.Current()->block_id()]); 113 } 114} 115 116 117void HEnvironmentLivenessAnalysisPhase::UpdateLivenessAtInstruction( 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 } 129 if (!went_live_since_last_simulate_.Contains(index)) { 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); 137 went_live_since_last_simulate_.Add(index); 138 } 139 if (collect_markers_) { 140 // Populate |markers_| list during the first pass. 141 markers_.Add(marker, zone()); 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(); 166 live->Union(*live_at_block_start_[return_id]); 167 } 168 last_simulate_ = NULL; 169 break; 170 } 171 case HValue::kSimulate: 172 last_simulate_ = HSimulate::cast(instr); 173 went_live_since_last_simulate_.Clear(); 174 break; 175 default: 176 break; 177 } 178} 179 180 181void HEnvironmentLivenessAnalysisPhase::Run() { 182 ASSERT(maximum_environment_size_ > 0); 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. 188 BitVector live(maximum_environment_size_, zone()); 189 BitVector worklist(block_count_, zone()); 190 for (int i = 0; i < block_count_; ++i) { 191 worklist.Add(i); 192 } 193 while (!worklist.IsEmpty()) { 194 for (int block_id = block_count_ - 1; block_id >= 0; --block_id) { 195 if (!worklist.Contains(block_id)) { 196 continue; 197 } 198 worklist.Remove(block_id); 199 last_simulate_ = NULL; 200 201 HBasicBlock* block = graph()->blocks()->at(block_id); 202 UpdateLivenessAtBlockEnd(block, &live); 203 204 for (HInstruction* instr = block->end(); instr != NULL; 205 instr = instr->previous()) { 206 UpdateLivenessAtInstruction(instr, &live); 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. 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)) { 216 for (int i = 0; i < block->predecessors()->length(); ++i) { 217 worklist.Add(block->predecessors()->at(i)->block_id()); 218 } 219 if (block->IsInlineReturnTarget()) { 220 worklist.Add(block->inlined_entry_block()->block_id()); 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. 229 for (int i = 0; i < markers_.length(); ++i) { 230 ZapEnvironmentSlotsForInstruction(markers_[i]); 231 } 232 for (int block_id = block_count_ - 1; block_id >= 0; --block_id) { 233 HBasicBlock* block = graph()->blocks()->at(block_id); 234 UpdateLivenessAtBlockEnd(block, &live); 235 ZapEnvironmentSlotsInSuccessors(block, &live); 236 } 237 238 // Finally, remove the HEnvironment{Bind,Lookup} markers. 239 for (int i = 0; i < markers_.length(); ++i) { 240 markers_[i]->DeleteAndReplaceWith(NULL); 241 } 242} 243 244} } // namespace v8::internal 245