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 void HEscapeAnalysisPhase::CollectIfNoEscapingUses(HInstruction* instr) { 35 for (HUseIterator it(instr->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", instr->id(), 40 instr->Mnemonic(), use->id(), use->Mnemonic(), it.index()); 41 } 42 return; 43 } 44 } 45 if (FLAG_trace_escape_analysis) { 46 PrintF("#%d (%s) is being captured\n", instr->id(), instr->Mnemonic()); 47 } 48 captured_.Add(instr, zone()); 49 } 50 51 52 void HEscapeAnalysisPhase::CollectCapturedValues() { 53 int block_count = graph()->blocks()->length(); 54 for (int i = 0; i < block_count; ++i) { 55 HBasicBlock* block = graph()->blocks()->at(i); 56 for (HInstructionIterator it(block); !it.Done(); it.Advance()) { 57 HInstruction* instr = it.Current(); 58 if (instr->IsAllocate()) { 59 CollectIfNoEscapingUses(instr); 60 } 61 } 62 } 63 } 64 65 66 HCapturedObject* HEscapeAnalysisPhase::NewState(HInstruction* previous) { 67 Zone* zone = graph()->zone(); 68 HCapturedObject* state = new(zone) HCapturedObject(number_of_values_, zone); 69 state->InsertAfter(previous); 70 return state; 71 } 72 73 74 // Create a new state for replacing HAllocate instructions. 75 HCapturedObject* HEscapeAnalysisPhase::NewStateForAllocation( 76 HInstruction* previous) { 77 HConstant* undefined = graph()->GetConstantUndefined(); 78 HCapturedObject* state = NewState(previous); 79 for (int index = 0; index < number_of_values_; index++) { 80 state->SetOperandAt(index, undefined); 81 } 82 return state; 83 } 84 85 86 // Create a new state full of phis for loop header entries. 87 HCapturedObject* HEscapeAnalysisPhase::NewStateForLoopHeader( 88 HInstruction* previous, 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, 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( 115 HBasicBlock* block, HValue* incoming_value, int index) { 116 Zone* zone = graph()->zone(); 117 HPhi* phi = new(zone) HPhi(HPhi::kInvalidMergedIndex, zone); 118 for (int i = 0; i < block->predecessors()->length(); i++) { 119 phi->AddInput(incoming_value); 120 } 121 block->AddPhi(phi); 122 return phi; 123 } 124 125 126 // Performs a forward data-flow analysis of all loads and stores on the 127 // given captured allocation. This uses a reverse post-order iteration 128 // over affected basic blocks. All non-escaping instructions are handled 129 // and replaced during the analysis. 130 void HEscapeAnalysisPhase::AnalyzeDataFlow(HInstruction* allocate) { 131 HBasicBlock* allocate_block = allocate->block(); 132 block_states_.AddBlock(NULL, graph()->blocks()->length(), zone()); 133 134 // Iterate all blocks starting with the allocation block, since the 135 // allocation cannot dominate blocks that come before. 136 int start = allocate_block->block_id(); 137 for (int i = start; i < graph()->blocks()->length(); i++) { 138 HBasicBlock* block = graph()->blocks()->at(i); 139 HCapturedObject* state = StateAt(block); 140 141 // Skip blocks that are not dominated by the captured allocation. 142 if (!allocate_block->Dominates(block) && allocate_block != block) continue; 143 if (FLAG_trace_escape_analysis) { 144 PrintF("Analyzing data-flow in B%d\n", block->block_id()); 145 } 146 147 // Go through all instructions of the current block. 148 for (HInstructionIterator it(block); !it.Done(); it.Advance()) { 149 HInstruction* instr = it.Current(); 150 switch (instr->opcode()) { 151 case HValue::kAllocate: { 152 if (instr != allocate) continue; 153 state = NewStateForAllocation(allocate); 154 break; 155 } 156 case HValue::kLoadNamedField: { 157 HLoadNamedField* load = HLoadNamedField::cast(instr); 158 int index = load->access().offset() / kPointerSize; 159 if (load->object() != allocate) continue; 160 ASSERT(load->access().IsInobject()); 161 HValue* replacement = state->OperandAt(index); 162 load->DeleteAndReplaceWith(replacement); 163 if (FLAG_trace_escape_analysis) { 164 PrintF("Replacing load #%d with #%d (%s)\n", instr->id(), 165 replacement->id(), replacement->Mnemonic()); 166 } 167 break; 168 } 169 case HValue::kStoreNamedField: { 170 HStoreNamedField* store = HStoreNamedField::cast(instr); 171 int index = store->access().offset() / kPointerSize; 172 if (store->object() != allocate) continue; 173 ASSERT(store->access().IsInobject()); 174 state = NewStateCopy(store, state); 175 state->SetOperandAt(index, store->value()); 176 if (store->has_transition()) { 177 state->SetOperandAt(0, store->transition()); 178 } 179 store->DeleteAndReplaceWith(NULL); 180 if (FLAG_trace_escape_analysis) { 181 PrintF("Replacing store #%d%s\n", instr->id(), 182 store->has_transition() ? " (with transition)" : ""); 183 } 184 break; 185 } 186 case HValue::kSimulate: { 187 HSimulate* simulate = HSimulate::cast(instr); 188 // TODO(mstarzinger): This doesn't track deltas for values on the 189 // operand stack yet. Find a repro test case and fix this. 190 for (int i = 0; i < simulate->OperandCount(); i++) { 191 if (simulate->OperandAt(i) != allocate) continue; 192 simulate->SetOperandAt(i, state); 193 } 194 break; 195 } 196 case HValue::kArgumentsObject: 197 case HValue::kCapturedObject: { 198 for (int i = 0; i < instr->OperandCount(); i++) { 199 if (instr->OperandAt(i) != allocate) continue; 200 instr->SetOperandAt(i, state); 201 } 202 break; 203 } 204 case HValue::kCheckHeapObject: { 205 HCheckHeapObject* check = HCheckHeapObject::cast(instr); 206 if (check->value() != allocate) continue; 207 check->DeleteAndReplaceWith(NULL); 208 break; 209 } 210 case HValue::kCheckMaps: { 211 HCheckMaps* mapcheck = HCheckMaps::cast(instr); 212 if (mapcheck->value() != allocate) continue; 213 // TODO(mstarzinger): This approach breaks if the tracked map value 214 // is not a HConstant. Find a repro test case and fix this. 215 for (HUseIterator it(mapcheck->uses()); !it.Done(); it.Advance()) { 216 if (!it.value()->IsLoadNamedField()) continue; 217 HLoadNamedField* load = HLoadNamedField::cast(it.value()); 218 ASSERT(load->typecheck() == mapcheck); 219 load->ClearTypeCheck(); 220 } 221 ASSERT(mapcheck->HasNoUses()); 222 223 mapcheck->DeleteAndReplaceWith(NULL); 224 break; 225 } 226 default: 227 // Nothing to see here, move along ... 228 break; 229 } 230 } 231 232 // Propagate the block state forward to all successor blocks. 233 for (int i = 0; i < block->end()->SuccessorCount(); i++) { 234 HBasicBlock* succ = block->end()->SuccessorAt(i); 235 if (!allocate_block->Dominates(succ)) continue; 236 if (succ->predecessors()->length() == 1) { 237 // Case 1: This is the only predecessor, just reuse state. 238 SetStateAt(succ, state); 239 } else if (StateAt(succ) == NULL && succ->IsLoopHeader()) { 240 // Case 2: This is a state that enters a loop header, be 241 // pessimistic about loop headers, add phis for all values. 242 SetStateAt(succ, NewStateForLoopHeader(succ->first(), state)); 243 } else if (StateAt(succ) == NULL) { 244 // Case 3: This is the first state propagated forward to the 245 // successor, leave a copy of the current state. 246 SetStateAt(succ, NewStateCopy(succ->first(), state)); 247 } else { 248 // Case 4: This is a state that needs merging with previously 249 // propagated states, potentially introducing new phis lazily or 250 // adding values to existing phis. 251 HCapturedObject* succ_state = StateAt(succ); 252 for (int index = 0; index < number_of_values_; index++) { 253 HValue* operand = state->OperandAt(index); 254 HValue* succ_operand = succ_state->OperandAt(index); 255 if (succ_operand->IsPhi() && succ_operand->block() == succ) { 256 // Phi already exists, add operand. 257 HPhi* phi = HPhi::cast(succ_operand); 258 phi->SetOperandAt(succ->PredecessorIndexOf(block), operand); 259 } else if (succ_operand != operand) { 260 // Phi does not exist, introduce one. 261 HPhi* phi = NewPhiAndInsert(succ, succ_operand, index); 262 phi->SetOperandAt(succ->PredecessorIndexOf(block), operand); 263 succ_state->SetOperandAt(index, phi); 264 } 265 } 266 } 267 } 268 } 269 270 // All uses have been handled. 271 ASSERT(allocate->HasNoUses()); 272 allocate->DeleteAndReplaceWith(NULL); 273 } 274 275 276 void HEscapeAnalysisPhase::PerformScalarReplacement() { 277 for (int i = 0; i < captured_.length(); i++) { 278 HAllocate* allocate = HAllocate::cast(captured_.at(i)); 279 280 // Compute number of scalar values and start with clean slate. 281 if (!allocate->size()->IsInteger32Constant()) continue; 282 int size_in_bytes = allocate->size()->GetInteger32Constant(); 283 number_of_values_ = size_in_bytes / kPointerSize; 284 block_states_.Clear(); 285 286 // Perform actual analysis steps. 287 AnalyzeDataFlow(allocate); 288 289 cumulative_values_ += number_of_values_; 290 ASSERT(allocate->HasNoUses()); 291 ASSERT(!allocate->IsLinked()); 292 } 293 } 294 295 296 } } // namespace v8::internal 297
