src/hydrogen-escape-analysis.cc - platform/external/chromium_org/v8 - Git at Google

 // 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/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(
       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) {
   HValue* replacement = load_value;
   Representation representation = load->representation();
   if (representation.IsSmiOrInteger32() || representation.IsDouble()) {
     Zone* zone = graph()->zone();
     HInstruction* new_instr =
         HForceRepresentation::New(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;
     PerformScalarReplacement();
     captured_.Rewind(0);
   }
 }


 } }  // namespace v8::internal
	// 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/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(
	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) {
	HValue* replacement = load_value;
	Representation representation = load->representation();
	if (representation.IsSmiOrInteger32() \|\| representation.IsDouble()) {
	Zone* zone = graph()->zone();
	HInstruction* new_instr =
	HForceRepresentation::New(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;
	PerformScalarReplacement();
	captured_.Rewind(0);
	}
	}


	} } // namespace v8::internal