193a47f4837f2137c8d8349250fd8e91da3108126jkummerow@chromium.org// Copyright 2013 the V8 project authors. All rights reserved. 23484964a86451e86dcf04be9bd8c0d76ee04f081rossberg@chromium.org// Use of this source code is governed by a BSD-style license that can be 33484964a86451e86dcf04be9bd8c0d76ee04f081rossberg@chromium.org// found in the LICENSE file. 493a47f4837f2137c8d8349250fd8e91da3108126jkummerow@chromium.org 5196eb601290dc49c3754da728dc58700dff2de1bmachenbach@chromium.org#include "src/hydrogen-escape-analysis.h" 693a47f4837f2137c8d8349250fd8e91da3108126jkummerow@chromium.org 793a47f4837f2137c8d8349250fd8e91da3108126jkummerow@chromium.orgnamespace v8 { 893a47f4837f2137c8d8349250fd8e91da3108126jkummerow@chromium.orgnamespace internal { 993a47f4837f2137c8d8349250fd8e91da3108126jkummerow@chromium.org 1093a47f4837f2137c8d8349250fd8e91da3108126jkummerow@chromium.org 11639bac0c5319f96e1bbe3399fb7f7f37344928bddslomov@chromium.orgbool HEscapeAnalysisPhase::HasNoEscapingUses(HValue* value, int size) { 12dc94e19484d1700cb0ec22365444223e49a3ac1ejkummerow@chromium.org for (HUseIterator it(value->uses()); !it.Done(); it.Advance()) { 1393a47f4837f2137c8d8349250fd8e91da3108126jkummerow@chromium.org HValue* use = it.value(); 1493a47f4837f2137c8d8349250fd8e91da3108126jkummerow@chromium.org if (use->HasEscapingOperandAt(it.index())) { 1593a47f4837f2137c8d8349250fd8e91da3108126jkummerow@chromium.org if (FLAG_trace_escape_analysis) { 16dc94e19484d1700cb0ec22365444223e49a3ac1ejkummerow@chromium.org PrintF("#%d (%s) escapes through #%d (%s) @%d\n", value->id(), 17dc94e19484d1700cb0ec22365444223e49a3ac1ejkummerow@chromium.org value->Mnemonic(), use->id(), use->Mnemonic(), it.index()); 1893a47f4837f2137c8d8349250fd8e91da3108126jkummerow@chromium.org } 19dc94e19484d1700cb0ec22365444223e49a3ac1ejkummerow@chromium.org return false; 20dc94e19484d1700cb0ec22365444223e49a3ac1ejkummerow@chromium.org } 21639bac0c5319f96e1bbe3399fb7f7f37344928bddslomov@chromium.org if (use->HasOutOfBoundsAccess(size)) { 22639bac0c5319f96e1bbe3399fb7f7f37344928bddslomov@chromium.org if (FLAG_trace_escape_analysis) { 23639bac0c5319f96e1bbe3399fb7f7f37344928bddslomov@chromium.org PrintF("#%d (%s) out of bounds at #%d (%s) @%d\n", value->id(), 24639bac0c5319f96e1bbe3399fb7f7f37344928bddslomov@chromium.org value->Mnemonic(), use->id(), use->Mnemonic(), it.index()); 25639bac0c5319f96e1bbe3399fb7f7f37344928bddslomov@chromium.org } 26639bac0c5319f96e1bbe3399fb7f7f37344928bddslomov@chromium.org return false; 27639bac0c5319f96e1bbe3399fb7f7f37344928bddslomov@chromium.org } 28639bac0c5319f96e1bbe3399fb7f7f37344928bddslomov@chromium.org int redefined_index = use->RedefinedOperandIndex(); 29639bac0c5319f96e1bbe3399fb7f7f37344928bddslomov@chromium.org if (redefined_index == it.index() && !HasNoEscapingUses(use, size)) { 30dc94e19484d1700cb0ec22365444223e49a3ac1ejkummerow@chromium.org if (FLAG_trace_escape_analysis) { 31dc94e19484d1700cb0ec22365444223e49a3ac1ejkummerow@chromium.org PrintF("#%d (%s) escapes redefinition #%d (%s) @%d\n", value->id(), 32dc94e19484d1700cb0ec22365444223e49a3ac1ejkummerow@chromium.org value->Mnemonic(), use->id(), use->Mnemonic(), it.index()); 33dc94e19484d1700cb0ec22365444223e49a3ac1ejkummerow@chromium.org } 34dc94e19484d1700cb0ec22365444223e49a3ac1ejkummerow@chromium.org return false; 3593a47f4837f2137c8d8349250fd8e91da3108126jkummerow@chromium.org } 3693a47f4837f2137c8d8349250fd8e91da3108126jkummerow@chromium.org } 37dc94e19484d1700cb0ec22365444223e49a3ac1ejkummerow@chromium.org return true; 3893a47f4837f2137c8d8349250fd8e91da3108126jkummerow@chromium.org} 3993a47f4837f2137c8d8349250fd8e91da3108126jkummerow@chromium.org 4093a47f4837f2137c8d8349250fd8e91da3108126jkummerow@chromium.org 4193a47f4837f2137c8d8349250fd8e91da3108126jkummerow@chromium.orgvoid HEscapeAnalysisPhase::CollectCapturedValues() { 4293a47f4837f2137c8d8349250fd8e91da3108126jkummerow@chromium.org int block_count = graph()->blocks()->length(); 4393a47f4837f2137c8d8349250fd8e91da3108126jkummerow@chromium.org for (int i = 0; i < block_count; ++i) { 4493a47f4837f2137c8d8349250fd8e91da3108126jkummerow@chromium.org HBasicBlock* block = graph()->blocks()->at(i); 4593a47f4837f2137c8d8349250fd8e91da3108126jkummerow@chromium.org for (HInstructionIterator it(block); !it.Done(); it.Advance()) { 4693a47f4837f2137c8d8349250fd8e91da3108126jkummerow@chromium.org HInstruction* instr = it.Current(); 47639bac0c5319f96e1bbe3399fb7f7f37344928bddslomov@chromium.org if (!instr->IsAllocate()) continue; 48639bac0c5319f96e1bbe3399fb7f7f37344928bddslomov@chromium.org HAllocate* allocate = HAllocate::cast(instr); 49639bac0c5319f96e1bbe3399fb7f7f37344928bddslomov@chromium.org if (!allocate->size()->IsInteger32Constant()) continue; 50639bac0c5319f96e1bbe3399fb7f7f37344928bddslomov@chromium.org int size_in_bytes = allocate->size()->GetInteger32Constant(); 51639bac0c5319f96e1bbe3399fb7f7f37344928bddslomov@chromium.org if (HasNoEscapingUses(instr, size_in_bytes)) { 52dc94e19484d1700cb0ec22365444223e49a3ac1ejkummerow@chromium.org if (FLAG_trace_escape_analysis) { 53dc94e19484d1700cb0ec22365444223e49a3ac1ejkummerow@chromium.org PrintF("#%d (%s) is being captured\n", instr->id(), 54dc94e19484d1700cb0ec22365444223e49a3ac1ejkummerow@chromium.org instr->Mnemonic()); 55dc94e19484d1700cb0ec22365444223e49a3ac1ejkummerow@chromium.org } 56dc94e19484d1700cb0ec22365444223e49a3ac1ejkummerow@chromium.org captured_.Add(instr, zone()); 5793a47f4837f2137c8d8349250fd8e91da3108126jkummerow@chromium.org } 5893a47f4837f2137c8d8349250fd8e91da3108126jkummerow@chromium.org } 5993a47f4837f2137c8d8349250fd8e91da3108126jkummerow@chromium.org } 6093a47f4837f2137c8d8349250fd8e91da3108126jkummerow@chromium.org} 6193a47f4837f2137c8d8349250fd8e91da3108126jkummerow@chromium.org 6293a47f4837f2137c8d8349250fd8e91da3108126jkummerow@chromium.org 63594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.orgHCapturedObject* HEscapeAnalysisPhase::NewState(HInstruction* previous) { 64594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org Zone* zone = graph()->zone(); 651e8da746019f818a22dfdc6f691dbc0447048cadjkummerow@chromium.org HCapturedObject* state = 661e8da746019f818a22dfdc6f691dbc0447048cadjkummerow@chromium.org new(zone) HCapturedObject(number_of_values_, number_of_objects_, zone); 67594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org state->InsertAfter(previous); 68594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org return state; 69594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org} 70594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 71594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 72594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org// Create a new state for replacing HAllocate instructions. 73594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.orgHCapturedObject* HEscapeAnalysisPhase::NewStateForAllocation( 74594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org HInstruction* previous) { 75594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org HConstant* undefined = graph()->GetConstantUndefined(); 76594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org HCapturedObject* state = NewState(previous); 77594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org for (int index = 0; index < number_of_values_; index++) { 78594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org state->SetOperandAt(index, undefined); 79594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org } 80594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org return state; 81594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org} 82594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 83594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 84594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org// Create a new state full of phis for loop header entries. 85594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.orgHCapturedObject* HEscapeAnalysisPhase::NewStateForLoopHeader( 861f410f9a9c4fbd4270749af64b477df87b753158mstarzinger@chromium.org HInstruction* previous, 871f410f9a9c4fbd4270749af64b477df87b753158mstarzinger@chromium.org HCapturedObject* old_state) { 88594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org HBasicBlock* block = previous->block(); 89594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org HCapturedObject* state = NewState(previous); 90594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org for (int index = 0; index < number_of_values_; index++) { 91594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org HValue* operand = old_state->OperandAt(index); 92594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org HPhi* phi = NewPhiAndInsert(block, operand, index); 93594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org state->SetOperandAt(index, phi); 94594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org } 95594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org return state; 96594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org} 97594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 98594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 99594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org// Create a new state by copying an existing one. 100594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.orgHCapturedObject* HEscapeAnalysisPhase::NewStateCopy( 1011f410f9a9c4fbd4270749af64b477df87b753158mstarzinger@chromium.org HInstruction* previous, 1021f410f9a9c4fbd4270749af64b477df87b753158mstarzinger@chromium.org HCapturedObject* old_state) { 103594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org HCapturedObject* state = NewState(previous); 104594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org for (int index = 0; index < number_of_values_; index++) { 105594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org HValue* operand = old_state->OperandAt(index); 106594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org state->SetOperandAt(index, operand); 107594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org } 108594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org return state; 109594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org} 110594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 111594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 112594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org// Insert a newly created phi into the given block and fill all incoming 113594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org// edges with the given value. 1141f410f9a9c4fbd4270749af64b477df87b753158mstarzinger@chromium.orgHPhi* HEscapeAnalysisPhase::NewPhiAndInsert(HBasicBlock* block, 1151f410f9a9c4fbd4270749af64b477df87b753158mstarzinger@chromium.org HValue* incoming_value, 1161f410f9a9c4fbd4270749af64b477df87b753158mstarzinger@chromium.org int index) { 117594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org Zone* zone = graph()->zone(); 118594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org HPhi* phi = new(zone) HPhi(HPhi::kInvalidMergedIndex, zone); 119594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org for (int i = 0; i < block->predecessors()->length(); i++) { 120594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org phi->AddInput(incoming_value); 121594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org } 122594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org block->AddPhi(phi); 123594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org return phi; 124594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org} 125594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 126594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 1271f410f9a9c4fbd4270749af64b477df87b753158mstarzinger@chromium.org// Insert a newly created value check as a replacement for map checks. 1281f410f9a9c4fbd4270749af64b477df87b753158mstarzinger@chromium.orgHValue* HEscapeAnalysisPhase::NewMapCheckAndInsert(HCapturedObject* state, 1291f410f9a9c4fbd4270749af64b477df87b753158mstarzinger@chromium.org HCheckMaps* mapcheck) { 1301f410f9a9c4fbd4270749af64b477df87b753158mstarzinger@chromium.org Zone* zone = graph()->zone(); 1311f410f9a9c4fbd4270749af64b477df87b753158mstarzinger@chromium.org HValue* value = state->map_value(); 1321f410f9a9c4fbd4270749af64b477df87b753158mstarzinger@chromium.org // TODO(mstarzinger): This will narrow a map check against a set of maps 1331f410f9a9c4fbd4270749af64b477df87b753158mstarzinger@chromium.org // down to the first element in the set. Revisit and fix this. 134528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org HCheckValue* check = HCheckValue::New( 135af6f699b0be532b73bc2f6c9e1cf40a57fa7e234machenbach@chromium.org zone, NULL, value, mapcheck->maps()->at(0), false); 1361f410f9a9c4fbd4270749af64b477df87b753158mstarzinger@chromium.org check->InsertBefore(mapcheck); 1371f410f9a9c4fbd4270749af64b477df87b753158mstarzinger@chromium.org return check; 1381f410f9a9c4fbd4270749af64b477df87b753158mstarzinger@chromium.org} 1391f410f9a9c4fbd4270749af64b477df87b753158mstarzinger@chromium.org 1401f410f9a9c4fbd4270749af64b477df87b753158mstarzinger@chromium.org 141865f51ff8c94f86f4c97636d70addc0f29e79674machenbach@chromium.org// Replace a field load with a given value, forcing Smi representation if 142865f51ff8c94f86f4c97636d70addc0f29e79674machenbach@chromium.org// necessary. 143865f51ff8c94f86f4c97636d70addc0f29e79674machenbach@chromium.orgHValue* HEscapeAnalysisPhase::NewLoadReplacement( 144865f51ff8c94f86f4c97636d70addc0f29e79674machenbach@chromium.org HLoadNamedField* load, HValue* load_value) { 145865f51ff8c94f86f4c97636d70addc0f29e79674machenbach@chromium.org HValue* replacement = load_value; 146865f51ff8c94f86f4c97636d70addc0f29e79674machenbach@chromium.org Representation representation = load->representation(); 147a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org if (representation.IsSmiOrInteger32() || representation.IsDouble()) { 148865f51ff8c94f86f4c97636d70addc0f29e79674machenbach@chromium.org Zone* zone = graph()->zone(); 149865f51ff8c94f86f4c97636d70addc0f29e79674machenbach@chromium.org HInstruction* new_instr = 150865f51ff8c94f86f4c97636d70addc0f29e79674machenbach@chromium.org HForceRepresentation::New(zone, NULL, load_value, representation); 151865f51ff8c94f86f4c97636d70addc0f29e79674machenbach@chromium.org new_instr->InsertAfter(load); 152865f51ff8c94f86f4c97636d70addc0f29e79674machenbach@chromium.org replacement = new_instr; 153865f51ff8c94f86f4c97636d70addc0f29e79674machenbach@chromium.org } 154865f51ff8c94f86f4c97636d70addc0f29e79674machenbach@chromium.org return replacement; 155865f51ff8c94f86f4c97636d70addc0f29e79674machenbach@chromium.org} 156865f51ff8c94f86f4c97636d70addc0f29e79674machenbach@chromium.org 157865f51ff8c94f86f4c97636d70addc0f29e79674machenbach@chromium.org 158594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org// Performs a forward data-flow analysis of all loads and stores on the 159594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org// given captured allocation. This uses a reverse post-order iteration 160594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org// over affected basic blocks. All non-escaping instructions are handled 161594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org// and replaced during the analysis. 162594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.orgvoid HEscapeAnalysisPhase::AnalyzeDataFlow(HInstruction* allocate) { 163594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org HBasicBlock* allocate_block = allocate->block(); 164594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org block_states_.AddBlock(NULL, graph()->blocks()->length(), zone()); 165594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 166594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org // Iterate all blocks starting with the allocation block, since the 167594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org // allocation cannot dominate blocks that come before. 168594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org int start = allocate_block->block_id(); 169594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org for (int i = start; i < graph()->blocks()->length(); i++) { 170594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org HBasicBlock* block = graph()->blocks()->at(i); 171594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org HCapturedObject* state = StateAt(block); 172594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 173594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org // Skip blocks that are not dominated by the captured allocation. 174594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org if (!allocate_block->Dominates(block) && allocate_block != block) continue; 175594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org if (FLAG_trace_escape_analysis) { 176594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org PrintF("Analyzing data-flow in B%d\n", block->block_id()); 177594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org } 178594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 179594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org // Go through all instructions of the current block. 180594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org for (HInstructionIterator it(block); !it.Done(); it.Advance()) { 181594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org HInstruction* instr = it.Current(); 182594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org switch (instr->opcode()) { 183594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org case HValue::kAllocate: { 184594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org if (instr != allocate) continue; 185594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org state = NewStateForAllocation(allocate); 186594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org break; 187594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org } 188594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org case HValue::kLoadNamedField: { 189594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org HLoadNamedField* load = HLoadNamedField::cast(instr); 190594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org int index = load->access().offset() / kPointerSize; 191594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org if (load->object() != allocate) continue; 192594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org ASSERT(load->access().IsInobject()); 193865f51ff8c94f86f4c97636d70addc0f29e79674machenbach@chromium.org HValue* replacement = 194865f51ff8c94f86f4c97636d70addc0f29e79674machenbach@chromium.org NewLoadReplacement(load, state->OperandAt(index)); 195594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org load->DeleteAndReplaceWith(replacement); 196594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org if (FLAG_trace_escape_analysis) { 197865f51ff8c94f86f4c97636d70addc0f29e79674machenbach@chromium.org PrintF("Replacing load #%d with #%d (%s)\n", load->id(), 198594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org replacement->id(), replacement->Mnemonic()); 199594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org } 200594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org break; 201594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org } 202594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org case HValue::kStoreNamedField: { 203594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org HStoreNamedField* store = HStoreNamedField::cast(instr); 204594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org int index = store->access().offset() / kPointerSize; 205594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org if (store->object() != allocate) continue; 206594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org ASSERT(store->access().IsInobject()); 2071f410f9a9c4fbd4270749af64b477df87b753158mstarzinger@chromium.org state = NewStateCopy(store->previous(), state); 208594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org state->SetOperandAt(index, store->value()); 209594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org if (store->has_transition()) { 210594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org state->SetOperandAt(0, store->transition()); 211594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org } 2121f410f9a9c4fbd4270749af64b477df87b753158mstarzinger@chromium.org if (store->HasObservableSideEffects()) { 2131f410f9a9c4fbd4270749af64b477df87b753158mstarzinger@chromium.org state->ReuseSideEffectsFromStore(store); 2141f410f9a9c4fbd4270749af64b477df87b753158mstarzinger@chromium.org } 2151f410f9a9c4fbd4270749af64b477df87b753158mstarzinger@chromium.org store->DeleteAndReplaceWith(store->ActualValue()); 216594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org if (FLAG_trace_escape_analysis) { 217594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org PrintF("Replacing store #%d%s\n", instr->id(), 218594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org store->has_transition() ? " (with transition)" : ""); 219594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org } 220594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org break; 221594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org } 222594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org case HValue::kArgumentsObject: 2231e8da746019f818a22dfdc6f691dbc0447048cadjkummerow@chromium.org case HValue::kCapturedObject: 2241e8da746019f818a22dfdc6f691dbc0447048cadjkummerow@chromium.org case HValue::kSimulate: { 225594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org for (int i = 0; i < instr->OperandCount(); i++) { 226594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org if (instr->OperandAt(i) != allocate) continue; 227594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org instr->SetOperandAt(i, state); 228594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org } 229594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org break; 230594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org } 231594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org case HValue::kCheckHeapObject: { 232594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org HCheckHeapObject* check = HCheckHeapObject::cast(instr); 233594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org if (check->value() != allocate) continue; 2341f410f9a9c4fbd4270749af64b477df87b753158mstarzinger@chromium.org check->DeleteAndReplaceWith(check->ActualValue()); 235594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org break; 236594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org } 237594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org case HValue::kCheckMaps: { 238594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org HCheckMaps* mapcheck = HCheckMaps::cast(instr); 239594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org if (mapcheck->value() != allocate) continue; 2401f410f9a9c4fbd4270749af64b477df87b753158mstarzinger@chromium.org NewMapCheckAndInsert(state, mapcheck); 2411e8da746019f818a22dfdc6f691dbc0447048cadjkummerow@chromium.org mapcheck->DeleteAndReplaceWith(mapcheck->ActualValue()); 242594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org break; 243594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org } 244594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org default: 245594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org // Nothing to see here, move along ... 246594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org break; 247594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org } 248594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org } 249594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 250594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org // Propagate the block state forward to all successor blocks. 251594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org for (int i = 0; i < block->end()->SuccessorCount(); i++) { 252594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org HBasicBlock* succ = block->end()->SuccessorAt(i); 253594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org if (!allocate_block->Dominates(succ)) continue; 254594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org if (succ->predecessors()->length() == 1) { 255594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org // Case 1: This is the only predecessor, just reuse state. 256594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org SetStateAt(succ, state); 257594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org } else if (StateAt(succ) == NULL && succ->IsLoopHeader()) { 258594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org // Case 2: This is a state that enters a loop header, be 259594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org // pessimistic about loop headers, add phis for all values. 260594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org SetStateAt(succ, NewStateForLoopHeader(succ->first(), state)); 261594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org } else if (StateAt(succ) == NULL) { 262594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org // Case 3: This is the first state propagated forward to the 263594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org // successor, leave a copy of the current state. 264594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org SetStateAt(succ, NewStateCopy(succ->first(), state)); 265594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org } else { 266594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org // Case 4: This is a state that needs merging with previously 267594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org // propagated states, potentially introducing new phis lazily or 268594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org // adding values to existing phis. 269594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org HCapturedObject* succ_state = StateAt(succ); 270594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org for (int index = 0; index < number_of_values_; index++) { 271594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org HValue* operand = state->OperandAt(index); 272594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org HValue* succ_operand = succ_state->OperandAt(index); 273594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org if (succ_operand->IsPhi() && succ_operand->block() == succ) { 274594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org // Phi already exists, add operand. 275594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org HPhi* phi = HPhi::cast(succ_operand); 276594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org phi->SetOperandAt(succ->PredecessorIndexOf(block), operand); 277594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org } else if (succ_operand != operand) { 278594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org // Phi does not exist, introduce one. 279594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org HPhi* phi = NewPhiAndInsert(succ, succ_operand, index); 280594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org phi->SetOperandAt(succ->PredecessorIndexOf(block), operand); 281594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org succ_state->SetOperandAt(index, phi); 282594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org } 283594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org } 284594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org } 285594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org } 286594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org } 287594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 288594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org // All uses have been handled. 289594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org ASSERT(allocate->HasNoUses()); 290594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org allocate->DeleteAndReplaceWith(NULL); 291594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org} 292594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 293594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 294594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.orgvoid HEscapeAnalysisPhase::PerformScalarReplacement() { 295594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org for (int i = 0; i < captured_.length(); i++) { 296594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org HAllocate* allocate = HAllocate::cast(captured_.at(i)); 297594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 298594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org // Compute number of scalar values and start with clean slate. 299594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org int size_in_bytes = allocate->size()->GetInteger32Constant(); 300594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org number_of_values_ = size_in_bytes / kPointerSize; 3011e8da746019f818a22dfdc6f691dbc0447048cadjkummerow@chromium.org number_of_objects_++; 302e31b63e9608909e17e35a3330b0075140af2fe91machenbach@chromium.org block_states_.Rewind(0); 303594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 3042ed0d029906d9c6f0ae06fe8eb7f1180077ae2b0mstarzinger@chromium.org // Perform actual analysis step. 305594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org AnalyzeDataFlow(allocate); 306594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 307594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org cumulative_values_ += number_of_values_; 308594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org ASSERT(allocate->HasNoUses()); 309594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org ASSERT(!allocate->IsLinked()); 310594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org } 311594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org} 312594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 313594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 314e900018c7a2a695fde788911564da37535c7e736mstarzinger@chromium.orgvoid HEscapeAnalysisPhase::Run() { 315e900018c7a2a695fde788911564da37535c7e736mstarzinger@chromium.org // TODO(mstarzinger): We disable escape analysis with OSR for now, because 316e900018c7a2a695fde788911564da37535c7e736mstarzinger@chromium.org // spill slots might be uninitialized. Needs investigation. 317e900018c7a2a695fde788911564da37535c7e736mstarzinger@chromium.org if (graph()->has_osr()) return; 3182ed0d029906d9c6f0ae06fe8eb7f1180077ae2b0mstarzinger@chromium.org int max_fixpoint_iteration_count = FLAG_escape_analysis_iterations; 3192ed0d029906d9c6f0ae06fe8eb7f1180077ae2b0mstarzinger@chromium.org for (int i = 0; i < max_fixpoint_iteration_count; i++) { 3202ed0d029906d9c6f0ae06fe8eb7f1180077ae2b0mstarzinger@chromium.org CollectCapturedValues(); 3212ed0d029906d9c6f0ae06fe8eb7f1180077ae2b0mstarzinger@chromium.org if (captured_.is_empty()) break; 3222ed0d029906d9c6f0ae06fe8eb7f1180077ae2b0mstarzinger@chromium.org PerformScalarReplacement(); 323e31b63e9608909e17e35a3330b0075140af2fe91machenbach@chromium.org captured_.Rewind(0); 3242ed0d029906d9c6f0ae06fe8eb7f1180077ae2b0mstarzinger@chromium.org } 325e900018c7a2a695fde788911564da37535c7e736mstarzinger@chromium.org} 326e900018c7a2a695fde788911564da37535c7e736mstarzinger@chromium.org 327e900018c7a2a695fde788911564da37535c7e736mstarzinger@chromium.org 32893a47f4837f2137c8d8349250fd8e91da3108126jkummerow@chromium.org} } // namespace v8::internal 329