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