| // Copyright 2013 the V8 project authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| |
| #include "src/crankshaft/hydrogen-escape-analysis.h" |
| |
| namespace v8 { |
| namespace internal { |
| |
| |
| bool HEscapeAnalysisPhase::HasNoEscapingUses(HValue* value, int size) { |
| for (HUseIterator it(value->uses()); !it.Done(); it.Advance()) { |
| HValue* use = it.value(); |
| if (use->HasEscapingOperandAt(it.index())) { |
| if (FLAG_trace_escape_analysis) { |
| PrintF("#%d (%s) escapes through #%d (%s) @%d\n", value->id(), |
| value->Mnemonic(), use->id(), use->Mnemonic(), it.index()); |
| } |
| return false; |
| } |
| if (use->HasOutOfBoundsAccess(size)) { |
| if (FLAG_trace_escape_analysis) { |
| PrintF("#%d (%s) out of bounds at #%d (%s) @%d\n", value->id(), |
| value->Mnemonic(), use->id(), use->Mnemonic(), it.index()); |
| } |
| return false; |
| } |
| int redefined_index = use->RedefinedOperandIndex(); |
| if (redefined_index == it.index() && !HasNoEscapingUses(use, size)) { |
| if (FLAG_trace_escape_analysis) { |
| PrintF("#%d (%s) escapes redefinition #%d (%s) @%d\n", value->id(), |
| value->Mnemonic(), use->id(), use->Mnemonic(), it.index()); |
| } |
| return false; |
| } |
| } |
| return true; |
| } |
| |
| |
| void HEscapeAnalysisPhase::CollectCapturedValues() { |
| int block_count = graph()->blocks()->length(); |
| for (int i = 0; i < block_count; ++i) { |
| HBasicBlock* block = graph()->blocks()->at(i); |
| for (HInstructionIterator it(block); !it.Done(); it.Advance()) { |
| HInstruction* instr = it.Current(); |
| if (!instr->IsAllocate()) continue; |
| HAllocate* allocate = HAllocate::cast(instr); |
| if (!allocate->size()->IsInteger32Constant()) continue; |
| int size_in_bytes = allocate->size()->GetInteger32Constant(); |
| if (HasNoEscapingUses(instr, size_in_bytes)) { |
| if (FLAG_trace_escape_analysis) { |
| PrintF("#%d (%s) is being captured\n", instr->id(), |
| instr->Mnemonic()); |
| } |
| captured_.Add(instr, zone()); |
| } |
| } |
| } |
| } |
| |
| |
| HCapturedObject* HEscapeAnalysisPhase::NewState(HInstruction* previous) { |
| Zone* zone = graph()->zone(); |
| HCapturedObject* state = |
| new(zone) HCapturedObject(number_of_values_, number_of_objects_, zone); |
| state->InsertAfter(previous); |
| return state; |
| } |
| |
| |
| // Create a new state for replacing HAllocate instructions. |
| HCapturedObject* HEscapeAnalysisPhase::NewStateForAllocation( |
| HInstruction* previous) { |
| HConstant* undefined = graph()->GetConstantUndefined(); |
| HCapturedObject* state = NewState(previous); |
| for (int index = 0; index < number_of_values_; index++) { |
| state->SetOperandAt(index, undefined); |
| } |
| return state; |
| } |
| |
| |
| // Create a new state full of phis for loop header entries. |
| HCapturedObject* HEscapeAnalysisPhase::NewStateForLoopHeader( |
| HInstruction* previous, |
| HCapturedObject* old_state) { |
| HBasicBlock* block = previous->block(); |
| HCapturedObject* state = NewState(previous); |
| for (int index = 0; index < number_of_values_; index++) { |
| HValue* operand = old_state->OperandAt(index); |
| HPhi* phi = NewPhiAndInsert(block, operand, index); |
| state->SetOperandAt(index, phi); |
| } |
| return state; |
| } |
| |
| |
| // Create a new state by copying an existing one. |
| HCapturedObject* HEscapeAnalysisPhase::NewStateCopy( |
| HInstruction* previous, |
| HCapturedObject* old_state) { |
| HCapturedObject* state = NewState(previous); |
| for (int index = 0; index < number_of_values_; index++) { |
| HValue* operand = old_state->OperandAt(index); |
| state->SetOperandAt(index, operand); |
| } |
| return state; |
| } |
| |
| |
| // Insert a newly created phi into the given block and fill all incoming |
| // edges with the given value. |
| HPhi* HEscapeAnalysisPhase::NewPhiAndInsert(HBasicBlock* block, |
| HValue* incoming_value, |
| int index) { |
| Zone* zone = graph()->zone(); |
| HPhi* phi = new(zone) HPhi(HPhi::kInvalidMergedIndex, zone); |
| for (int i = 0; i < block->predecessors()->length(); i++) { |
| phi->AddInput(incoming_value); |
| } |
| block->AddPhi(phi); |
| return phi; |
| } |
| |
| |
| // Insert a newly created value check as a replacement for map checks. |
| HValue* HEscapeAnalysisPhase::NewMapCheckAndInsert(HCapturedObject* state, |
| HCheckMaps* mapcheck) { |
| Zone* zone = graph()->zone(); |
| HValue* value = state->map_value(); |
| // TODO(mstarzinger): This will narrow a map check against a set of maps |
| // down to the first element in the set. Revisit and fix this. |
| HCheckValue* check = HCheckValue::New(graph()->isolate(), zone, NULL, value, |
| mapcheck->maps()->at(0), false); |
| check->InsertBefore(mapcheck); |
| return check; |
| } |
| |
| |
| // Replace a field load with a given value, forcing Smi representation if |
| // necessary. |
| HValue* HEscapeAnalysisPhase::NewLoadReplacement( |
| HLoadNamedField* load, HValue* load_value) { |
| isolate()->counters()->crankshaft_escape_loads_replaced()->Increment(); |
| HValue* replacement = load_value; |
| Representation representation = load->representation(); |
| if (representation.IsSmiOrInteger32() || representation.IsDouble()) { |
| Zone* zone = graph()->zone(); |
| HInstruction* new_instr = HForceRepresentation::New( |
| graph()->isolate(), zone, NULL, load_value, representation); |
| new_instr->InsertAfter(load); |
| replacement = new_instr; |
| } |
| return replacement; |
| } |
| |
| |
| // Performs a forward data-flow analysis of all loads and stores on the |
| // given captured allocation. This uses a reverse post-order iteration |
| // over affected basic blocks. All non-escaping instructions are handled |
| // and replaced during the analysis. |
| void HEscapeAnalysisPhase::AnalyzeDataFlow(HInstruction* allocate) { |
| HBasicBlock* allocate_block = allocate->block(); |
| block_states_.AddBlock(NULL, graph()->blocks()->length(), zone()); |
| |
| // Iterate all blocks starting with the allocation block, since the |
| // allocation cannot dominate blocks that come before. |
| int start = allocate_block->block_id(); |
| for (int i = start; i < graph()->blocks()->length(); i++) { |
| HBasicBlock* block = graph()->blocks()->at(i); |
| HCapturedObject* state = StateAt(block); |
| |
| // Skip blocks that are not dominated by the captured allocation. |
| if (!allocate_block->Dominates(block) && allocate_block != block) continue; |
| if (FLAG_trace_escape_analysis) { |
| PrintF("Analyzing data-flow in B%d\n", block->block_id()); |
| } |
| |
| // Go through all instructions of the current block. |
| for (HInstructionIterator it(block); !it.Done(); it.Advance()) { |
| HInstruction* instr = it.Current(); |
| switch (instr->opcode()) { |
| case HValue::kAllocate: { |
| if (instr != allocate) continue; |
| state = NewStateForAllocation(allocate); |
| break; |
| } |
| case HValue::kLoadNamedField: { |
| HLoadNamedField* load = HLoadNamedField::cast(instr); |
| int index = load->access().offset() / kPointerSize; |
| if (load->object() != allocate) continue; |
| DCHECK(load->access().IsInobject()); |
| HValue* replacement = |
| NewLoadReplacement(load, state->OperandAt(index)); |
| load->DeleteAndReplaceWith(replacement); |
| if (FLAG_trace_escape_analysis) { |
| PrintF("Replacing load #%d with #%d (%s)\n", load->id(), |
| replacement->id(), replacement->Mnemonic()); |
| } |
| break; |
| } |
| case HValue::kStoreNamedField: { |
| HStoreNamedField* store = HStoreNamedField::cast(instr); |
| int index = store->access().offset() / kPointerSize; |
| if (store->object() != allocate) continue; |
| DCHECK(store->access().IsInobject()); |
| state = NewStateCopy(store->previous(), state); |
| state->SetOperandAt(index, store->value()); |
| if (store->has_transition()) { |
| state->SetOperandAt(0, store->transition()); |
| } |
| if (store->HasObservableSideEffects()) { |
| state->ReuseSideEffectsFromStore(store); |
| } |
| store->DeleteAndReplaceWith(store->ActualValue()); |
| if (FLAG_trace_escape_analysis) { |
| PrintF("Replacing store #%d%s\n", instr->id(), |
| store->has_transition() ? " (with transition)" : ""); |
| } |
| break; |
| } |
| case HValue::kArgumentsObject: |
| case HValue::kCapturedObject: |
| case HValue::kSimulate: { |
| for (int i = 0; i < instr->OperandCount(); i++) { |
| if (instr->OperandAt(i) != allocate) continue; |
| instr->SetOperandAt(i, state); |
| } |
| break; |
| } |
| case HValue::kCheckHeapObject: { |
| HCheckHeapObject* check = HCheckHeapObject::cast(instr); |
| if (check->value() != allocate) continue; |
| check->DeleteAndReplaceWith(check->ActualValue()); |
| break; |
| } |
| case HValue::kCheckMaps: { |
| HCheckMaps* mapcheck = HCheckMaps::cast(instr); |
| if (mapcheck->value() != allocate) continue; |
| NewMapCheckAndInsert(state, mapcheck); |
| mapcheck->DeleteAndReplaceWith(mapcheck->ActualValue()); |
| break; |
| } |
| default: |
| // Nothing to see here, move along ... |
| break; |
| } |
| } |
| |
| // Propagate the block state forward to all successor blocks. |
| for (int i = 0; i < block->end()->SuccessorCount(); i++) { |
| HBasicBlock* succ = block->end()->SuccessorAt(i); |
| if (!allocate_block->Dominates(succ)) continue; |
| if (succ->predecessors()->length() == 1) { |
| // Case 1: This is the only predecessor, just reuse state. |
| SetStateAt(succ, state); |
| } else if (StateAt(succ) == NULL && succ->IsLoopHeader()) { |
| // Case 2: This is a state that enters a loop header, be |
| // pessimistic about loop headers, add phis for all values. |
| SetStateAt(succ, NewStateForLoopHeader(succ->first(), state)); |
| } else if (StateAt(succ) == NULL) { |
| // Case 3: This is the first state propagated forward to the |
| // successor, leave a copy of the current state. |
| SetStateAt(succ, NewStateCopy(succ->first(), state)); |
| } else { |
| // Case 4: This is a state that needs merging with previously |
| // propagated states, potentially introducing new phis lazily or |
| // adding values to existing phis. |
| HCapturedObject* succ_state = StateAt(succ); |
| for (int index = 0; index < number_of_values_; index++) { |
| HValue* operand = state->OperandAt(index); |
| HValue* succ_operand = succ_state->OperandAt(index); |
| if (succ_operand->IsPhi() && succ_operand->block() == succ) { |
| // Phi already exists, add operand. |
| HPhi* phi = HPhi::cast(succ_operand); |
| phi->SetOperandAt(succ->PredecessorIndexOf(block), operand); |
| } else if (succ_operand != operand) { |
| // Phi does not exist, introduce one. |
| HPhi* phi = NewPhiAndInsert(succ, succ_operand, index); |
| phi->SetOperandAt(succ->PredecessorIndexOf(block), operand); |
| succ_state->SetOperandAt(index, phi); |
| } |
| } |
| } |
| } |
| } |
| |
| // All uses have been handled. |
| DCHECK(allocate->HasNoUses()); |
| allocate->DeleteAndReplaceWith(NULL); |
| } |
| |
| |
| void HEscapeAnalysisPhase::PerformScalarReplacement() { |
| for (int i = 0; i < captured_.length(); i++) { |
| HAllocate* allocate = HAllocate::cast(captured_.at(i)); |
| |
| // Compute number of scalar values and start with clean slate. |
| int size_in_bytes = allocate->size()->GetInteger32Constant(); |
| number_of_values_ = size_in_bytes / kPointerSize; |
| number_of_objects_++; |
| block_states_.Rewind(0); |
| |
| // Perform actual analysis step. |
| AnalyzeDataFlow(allocate); |
| |
| cumulative_values_ += number_of_values_; |
| DCHECK(allocate->HasNoUses()); |
| DCHECK(!allocate->IsLinked()); |
| } |
| } |
| |
| |
| void HEscapeAnalysisPhase::Run() { |
| // TODO(mstarzinger): We disable escape analysis with OSR for now, because |
| // spill slots might be uninitialized. Needs investigation. |
| if (graph()->has_osr()) return; |
| int max_fixpoint_iteration_count = FLAG_escape_analysis_iterations; |
| for (int i = 0; i < max_fixpoint_iteration_count; i++) { |
| CollectCapturedValues(); |
| if (captured_.is_empty()) break; |
| isolate()->counters()->crankshaft_escape_allocs_replaced()->Increment( |
| captured_.length()); |
| PerformScalarReplacement(); |
| captured_.Rewind(0); |
| } |
| } |
| |
| |
| } // namespace internal |
| } // namespace v8 |