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