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