blob: ab3bff2edcd37a36c1407c44354b990d70a04f69 [file] [log] [blame]
// 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