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( 135 zone, NULL, value, 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 = 150 HForceRepresentation::New(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 ASSERT(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 ASSERT(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 ASSERT(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 ASSERT(allocate->HasNoUses()); 309 ASSERT(!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 v8::internal 329
