| OLD | NEW |
|---|
| (Empty) |
| 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 | |
| 3 // found in the LICENSE file. | |
| 4 | |
| 5 #include "src/hydrogen-escape-analysis.h" | |
| 6 | |
| 7 namespace v8 { | |
| 8 namespace internal { | |
| 9 | |
| 10 | |
| 11 bool HEscapeAnalysisPhase::HasNoEscapingUses(HValue* value, int size) { | |
| 12 for (HUseIterator it(value->uses()); !it.Done(); it.Advance()) { | |
| 13 HValue* use = it.value(); | |
| 14 if (use->HasEscapingOperandAt(it.index())) { | |
| 15 if (FLAG_trace_escape_analysis) { | |
| 16 PrintF("#%d (%s) escapes through #%d (%s) @%d\n", value->id(), | |
| 17 value->Mnemonic(), use->id(), use->Mnemonic(), it.index()); | |
| 18 } | |
| 19 return false; | |
| 20 } | |
| 21 if (use->HasOutOfBoundsAccess(size)) { | |
| 22 if (FLAG_trace_escape_analysis) { | |
| 23 PrintF("#%d (%s) out of bounds at #%d (%s) @%d\n", value->id(), | |
| 24 value->Mnemonic(), use->id(), use->Mnemonic(), it.index()); | |
| 25 } | |
| 26 return false; | |
| 27 } | |
| 28 int redefined_index = use->RedefinedOperandIndex(); | |
| 29 if (redefined_index == it.index() && !HasNoEscapingUses(use, size)) { | |
| 30 if (FLAG_trace_escape_analysis) { | |
| 31 PrintF("#%d (%s) escapes redefinition #%d (%s) @%d\n", value->id(), | |
| 32 value->Mnemonic(), use->id(), use->Mnemonic(), it.index()); | |
| 33 } | |
| 34 return false; | |
| 35 } | |
| 36 } | |
| 37 return true; | |
| 38 } | |
| 39 | |
| 40 | |
| 41 void HEscapeAnalysisPhase::CollectCapturedValues() { | |
| 42 int block_count = graph()->blocks()->length(); | |
| 43 for (int i = 0; i < block_count; ++i) { | |
| 44 HBasicBlock* block = graph()->blocks()->at(i); | |
| 45 for (HInstructionIterator it(block); !it.Done(); it.Advance()) { | |
| 46 HInstruction* instr = it.Current(); | |
| 47 if (!instr->IsAllocate()) continue; | |
| 48 HAllocate* allocate = HAllocate::cast(instr); | |
| 49 if (!allocate->size()->IsInteger32Constant()) continue; | |
| 50 int size_in_bytes = allocate->size()->GetInteger32Constant(); | |
| 51 if (HasNoEscapingUses(instr, size_in_bytes)) { | |
| 52 if (FLAG_trace_escape_analysis) { | |
| 53 PrintF("#%d (%s) is being captured\n", instr->id(), | |
| 54 instr->Mnemonic()); | |
| 55 } | |
| 56 captured_.Add(instr, zone()); | |
| 57 } | |
| 58 } | |
| 59 } | |
| 60 } | |
| 61 | |
| 62 | |
| 63 HCapturedObject* HEscapeAnalysisPhase::NewState(HInstruction* previous) { | |
| 64 Zone* zone = graph()->zone(); | |
| 65 HCapturedObject* state = | |
| 66 new(zone) HCapturedObject(number_of_values_, number_of_objects_, zone); | |
| 67 state->InsertAfter(previous); | |
| 68 return state; | |
| 69 } | |
| 70 | |
| 71 | |
| 72 // Create a new state for replacing HAllocate instructions. | |
| 73 HCapturedObject* HEscapeAnalysisPhase::NewStateForAllocation( | |
| 74 HInstruction* previous) { | |
| 75 HConstant* undefined = graph()->GetConstantUndefined(); | |
| 76 HCapturedObject* state = NewState(previous); | |
| 77 for (int index = 0; index < number_of_values_; index++) { | |
| 78 state->SetOperandAt(index, undefined); | |
| 79 } | |
| 80 return state; | |
| 81 } | |
| 82 | |
| 83 | |
| 84 // Create a new state full of phis for loop header entries. | |
| 85 HCapturedObject* HEscapeAnalysisPhase::NewStateForLoopHeader( | |
| 86 HInstruction* previous, | |
| 87 HCapturedObject* old_state) { | |
| 88 HBasicBlock* block = previous->block(); | |
| 89 HCapturedObject* state = NewState(previous); | |
| 90 for (int index = 0; index < number_of_values_; index++) { | |
| 91 HValue* operand = old_state->OperandAt(index); | |
| 92 HPhi* phi = NewPhiAndInsert(block, operand, index); | |
| 93 state->SetOperandAt(index, phi); | |
| 94 } | |
| 95 return state; | |
| 96 } | |
| 97 | |
| 98 | |
| 99 // Create a new state by copying an existing one. | |
| 100 HCapturedObject* HEscapeAnalysisPhase::NewStateCopy( | |
| 101 HInstruction* previous, | |
| 102 HCapturedObject* old_state) { | |
| 103 HCapturedObject* state = NewState(previous); | |
| 104 for (int index = 0; index < number_of_values_; index++) { | |
| 105 HValue* operand = old_state->OperandAt(index); | |
| 106 state->SetOperandAt(index, operand); | |
| 107 } | |
| 108 return state; | |
| 109 } | |
| 110 | |
| 111 | |
| 112 // Insert a newly created phi into the given block and fill all incoming | |
| 113 // edges with the given value. | |
| 114 HPhi* HEscapeAnalysisPhase::NewPhiAndInsert(HBasicBlock* block, | |
| 115 HValue* incoming_value, | |
| 116 int index) { | |
| 117 Zone* zone = graph()->zone(); | |
| 118 HPhi* phi = new(zone) HPhi(HPhi::kInvalidMergedIndex, zone); | |
| 119 for (int i = 0; i < block->predecessors()->length(); i++) { | |
| 120 phi->AddInput(incoming_value); | |
| 121 } | |
| 122 block->AddPhi(phi); | |
| 123 return phi; | |
| 124 } | |
| 125 | |
| 126 | |
| 127 // Insert a newly created value check as a replacement for map checks. | |
| 128 HValue* HEscapeAnalysisPhase::NewMapCheckAndInsert(HCapturedObject* state, | |
| 129 HCheckMaps* mapcheck) { | |
| 130 Zone* zone = graph()->zone(); | |
| 131 HValue* value = state->map_value(); | |
| 132 // TODO(mstarzinger): This will narrow a map check against a set of maps | |
| 133 // down to the first element in the set. Revisit and fix this. | |
| 134 HCheckValue* check = HCheckValue::New(graph()->isolate(), zone, NULL, value, | |
| 135 mapcheck->maps()->at(0), false); | |
| 136 check->InsertBefore(mapcheck); | |
| 137 return check; | |
| 138 } | |
| 139 | |
| 140 | |
| 141 // Replace a field load with a given value, forcing Smi representation if | |
| 142 // necessary. | |
| 143 HValue* HEscapeAnalysisPhase::NewLoadReplacement( | |
| 144 HLoadNamedField* load, HValue* load_value) { | |
| 145 HValue* replacement = load_value; | |
| 146 Representation representation = load->representation(); | |
| 147 if (representation.IsSmiOrInteger32() || representation.IsDouble()) { | |
| 148 Zone* zone = graph()->zone(); | |
| 149 HInstruction* new_instr = HForceRepresentation::New( | |
| 150 graph()->isolate(), zone, NULL, load_value, representation); | |
| 151 new_instr->InsertAfter(load); | |
| 152 replacement = new_instr; | |
| 153 } | |
| 154 return replacement; | |
| 155 } | |
| 156 | |
| 157 | |
| 158 // Performs a forward data-flow analysis of all loads and stores on the | |
| 159 // given captured allocation. This uses a reverse post-order iteration | |
| 160 // over affected basic blocks. All non-escaping instructions are handled | |
| 161 // and replaced during the analysis. | |
| 162 void HEscapeAnalysisPhase::AnalyzeDataFlow(HInstruction* allocate) { | |
| 163 HBasicBlock* allocate_block = allocate->block(); | |
| 164 block_states_.AddBlock(NULL, graph()->blocks()->length(), zone()); | |
| 165 | |
| 166 // Iterate all blocks starting with the allocation block, since the | |
| 167 // allocation cannot dominate blocks that come before. | |
| 168 int start = allocate_block->block_id(); | |
| 169 for (int i = start; i < graph()->blocks()->length(); i++) { | |
| 170 HBasicBlock* block = graph()->blocks()->at(i); | |
| 171 HCapturedObject* state = StateAt(block); | |
| 172 | |
| 173 // Skip blocks that are not dominated by the captured allocation. | |
| 174 if (!allocate_block->Dominates(block) && allocate_block != block) continue; | |
| 175 if (FLAG_trace_escape_analysis) { | |
| 176 PrintF("Analyzing data-flow in B%d\n", block->block_id()); | |
| 177 } | |
| 178 | |
| 179 // Go through all instructions of the current block. | |
| 180 for (HInstructionIterator it(block); !it.Done(); it.Advance()) { | |
| 181 HInstruction* instr = it.Current(); | |
| 182 switch (instr->opcode()) { | |
| 183 case HValue::kAllocate: { | |
| 184 if (instr != allocate) continue; | |
| 185 state = NewStateForAllocation(allocate); | |
| 186 break; | |
| 187 } | |
| 188 case HValue::kLoadNamedField: { | |
| 189 HLoadNamedField* load = HLoadNamedField::cast(instr); | |
| 190 int index = load->access().offset() / kPointerSize; | |
| 191 if (load->object() != allocate) continue; | |
| 192 DCHECK(load->access().IsInobject()); | |
| 193 HValue* replacement = | |
| 194 NewLoadReplacement(load, state->OperandAt(index)); | |
| 195 load->DeleteAndReplaceWith(replacement); | |
| 196 if (FLAG_trace_escape_analysis) { | |
| 197 PrintF("Replacing load #%d with #%d (%s)\n", load->id(), | |
| 198 replacement->id(), replacement->Mnemonic()); | |
| 199 } | |
| 200 break; | |
| 201 } | |
| 202 case HValue::kStoreNamedField: { | |
| 203 HStoreNamedField* store = HStoreNamedField::cast(instr); | |
| 204 int index = store->access().offset() / kPointerSize; | |
| 205 if (store->object() != allocate) continue; | |
| 206 DCHECK(store->access().IsInobject()); | |
| 207 state = NewStateCopy(store->previous(), state); | |
| 208 state->SetOperandAt(index, store->value()); | |
| 209 if (store->has_transition()) { | |
| 210 state->SetOperandAt(0, store->transition()); | |
| 211 } | |
| 212 if (store->HasObservableSideEffects()) { | |
| 213 state->ReuseSideEffectsFromStore(store); | |
| 214 } | |
| 215 store->DeleteAndReplaceWith(store->ActualValue()); | |
| 216 if (FLAG_trace_escape_analysis) { | |
| 217 PrintF("Replacing store #%d%s\n", instr->id(), | |
| 218 store->has_transition() ? " (with transition)" : ""); | |
| 219 } | |
| 220 break; | |
| 221 } | |
| 222 case HValue::kArgumentsObject: | |
| 223 case HValue::kCapturedObject: | |
| 224 case HValue::kSimulate: { | |
| 225 for (int i = 0; i < instr->OperandCount(); i++) { | |
| 226 if (instr->OperandAt(i) != allocate) continue; | |
| 227 instr->SetOperandAt(i, state); | |
| 228 } | |
| 229 break; | |
| 230 } | |
| 231 case HValue::kCheckHeapObject: { | |
| 232 HCheckHeapObject* check = HCheckHeapObject::cast(instr); | |
| 233 if (check->value() != allocate) continue; | |
| 234 check->DeleteAndReplaceWith(check->ActualValue()); | |
| 235 break; | |
| 236 } | |
| 237 case HValue::kCheckMaps: { | |
| 238 HCheckMaps* mapcheck = HCheckMaps::cast(instr); | |
| 239 if (mapcheck->value() != allocate) continue; | |
| 240 NewMapCheckAndInsert(state, mapcheck); | |
| 241 mapcheck->DeleteAndReplaceWith(mapcheck->ActualValue()); | |
| 242 break; | |
| 243 } | |
| 244 default: | |
| 245 // Nothing to see here, move along ... | |
| 246 break; | |
| 247 } | |
| 248 } | |
| 249 | |
| 250 // Propagate the block state forward to all successor blocks. | |
| 251 for (int i = 0; i < block->end()->SuccessorCount(); i++) { | |
| 252 HBasicBlock* succ = block->end()->SuccessorAt(i); | |
| 253 if (!allocate_block->Dominates(succ)) continue; | |
| 254 if (succ->predecessors()->length() == 1) { | |
| 255 // Case 1: This is the only predecessor, just reuse state. | |
| 256 SetStateAt(succ, state); | |
| 257 } else if (StateAt(succ) == NULL && succ->IsLoopHeader()) { | |
| 258 // Case 2: This is a state that enters a loop header, be | |
| 259 // pessimistic about loop headers, add phis for all values. | |
| 260 SetStateAt(succ, NewStateForLoopHeader(succ->first(), state)); | |
| 261 } else if (StateAt(succ) == NULL) { | |
| 262 // Case 3: This is the first state propagated forward to the | |
| 263 // successor, leave a copy of the current state. | |
| 264 SetStateAt(succ, NewStateCopy(succ->first(), state)); | |
| 265 } else { | |
| 266 // Case 4: This is a state that needs merging with previously | |
| 267 // propagated states, potentially introducing new phis lazily or | |
| 268 // adding values to existing phis. | |
| 269 HCapturedObject* succ_state = StateAt(succ); | |
| 270 for (int index = 0; index < number_of_values_; index++) { | |
| 271 HValue* operand = state->OperandAt(index); | |
| 272 HValue* succ_operand = succ_state->OperandAt(index); | |
| 273 if (succ_operand->IsPhi() && succ_operand->block() == succ) { | |
| 274 // Phi already exists, add operand. | |
| 275 HPhi* phi = HPhi::cast(succ_operand); | |
| 276 phi->SetOperandAt(succ->PredecessorIndexOf(block), operand); | |
| 277 } else if (succ_operand != operand) { | |
| 278 // Phi does not exist, introduce one. | |
| 279 HPhi* phi = NewPhiAndInsert(succ, succ_operand, index); | |
| 280 phi->SetOperandAt(succ->PredecessorIndexOf(block), operand); | |
| 281 succ_state->SetOperandAt(index, phi); | |
| 282 } | |
| 283 } | |
| 284 } | |
| 285 } | |
| 286 } | |
| 287 | |
| 288 // All uses have been handled. | |
| 289 DCHECK(allocate->HasNoUses()); | |
| 290 allocate->DeleteAndReplaceWith(NULL); | |
| 291 } | |
| 292 | |
| 293 | |
| 294 void HEscapeAnalysisPhase::PerformScalarReplacement() { | |
| 295 for (int i = 0; i < captured_.length(); i++) { | |
| 296 HAllocate* allocate = HAllocate::cast(captured_.at(i)); | |
| 297 | |
| 298 // Compute number of scalar values and start with clean slate. | |
| 299 int size_in_bytes = allocate->size()->GetInteger32Constant(); | |
| 300 number_of_values_ = size_in_bytes / kPointerSize; | |
| 301 number_of_objects_++; | |
| 302 block_states_.Rewind(0); | |
| 303 | |
| 304 // Perform actual analysis step. | |
| 305 AnalyzeDataFlow(allocate); | |
| 306 | |
| 307 cumulative_values_ += number_of_values_; | |
| 308 DCHECK(allocate->HasNoUses()); | |
| 309 DCHECK(!allocate->IsLinked()); | |
| 310 } | |
| 311 } | |
| 312 | |
| 313 | |
| 314 void HEscapeAnalysisPhase::Run() { | |
| 315 // TODO(mstarzinger): We disable escape analysis with OSR for now, because | |
| 316 // spill slots might be uninitialized. Needs investigation. | |
| 317 if (graph()->has_osr()) return; | |
| 318 int max_fixpoint_iteration_count = FLAG_escape_analysis_iterations; | |
| 319 for (int i = 0; i < max_fixpoint_iteration_count; i++) { | |
| 320 CollectCapturedValues(); | |
| 321 if (captured_.is_empty()) break; | |
| 322 PerformScalarReplacement(); | |
| 323 captured_.Rewind(0); | |
| 324 } | |
| 325 } | |
| 326 | |
| 327 | |
| 328 } // namespace internal | |
| 329 } // namespace v8 | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 1405363003:
Move Hydrogen and Lithium to src/crankshaft/ (Closed)
Base URL: https://chromium.googlesource.com/v8/v8.git@master