#include <hydrogen-environment-liveness.h>

Inheritance diagram for v8::internal::HEnvironmentLivenessAnalysisPhase:

Collaboration diagram for v8::internal::HEnvironmentLivenessAnalysisPhase:

Public Member Functions
	HEnvironmentLivenessAnalysisPhase (HGraph *graph)

void	Run ()

Public Member Functions inherited from v8::internal::HPhase
	HPhase (const char name, HGraph graph)

	~HPhase ()

Private Member Functions
void	ZapEnvironmentSlot (int index, HSimulate *simulate)

void	ZapEnvironmentSlotsInSuccessors (HBasicBlock block, BitVector live)

void	ZapEnvironmentSlotsForInstruction (HEnvironmentMarker *marker)

void	UpdateLivenessAtBlockEnd (HBasicBlock block, BitVector live)

void	UpdateLivenessAtInstruction (HInstruction instr, BitVector live)

	DISALLOW_COPY_AND_ASSIGN (HEnvironmentLivenessAnalysisPhase)

Private Attributes
int	block_count_

int	maximum_environment_size_

ZoneList< BitVector * >	live_at_block_start_

ZoneList< HSimulate * >	first_simulate_

ZoneList< BitVector * >	first_simulate_invalid_for_index_

ZoneList< HEnvironmentMarker * >	markers_

bool	collect_markers_

HSimulate *	last_simulate_

BitVector	went_live_since_last_simulate_

Additional Inherited Members
Protected Member Functions inherited from v8::internal::HPhase
HGraph *	graph () const

Detailed Description

Definition at line 23 of file hydrogen-environment-liveness.h.

Constructor & Destructor Documentation

◆ HEnvironmentLivenessAnalysisPhase()

v8::internal::HEnvironmentLivenessAnalysisPhase::HEnvironmentLivenessAnalysisPhase ( HGraph * graph )

explicit

Definition at line 13 of file hydrogen-environment-liveness.cc.

     : HPhase("H_Environment liveness analysis", graph),
       block_count_(graph->blocks()->length()),
       maximum_environment_size_(graph->maximum_environment_size()),
       live_at_block_start_(block_count_, zone()),
       first_simulate_(block_count_, zone()),
       first_simulate_invalid_for_index_(block_count_, zone()),
       markers_(maximum_environment_size_, zone()),
       collect_markers_(true),
       last_simulate_(NULL),
       went_live_since_last_simulate_(maximum_environment_size_, zone()) {
   DCHECK(maximum_environment_size_ > 0);
   for (int i = 0; i < block_count_; ++i) {
     live_at_block_start_.Add(
         new(zone()) BitVector(maximum_environment_size_, zone()), zone());
     first_simulate_.Add(NULL, zone());
     first_simulate_invalid_for_index_.Add(
         new(zone()) BitVector(maximum_environment_size_, zone()), zone());
   }
 }

References v8::internal::List< T, AllocationPolicy >::Add(), block_count_, DCHECK, first_simulate_, first_simulate_invalid_for_index_, live_at_block_start_, maximum_environment_size_, and NULL.

Here is the call graph for this function:

Member Function Documentation

◆ DISALLOW_COPY_AND_ASSIGN()

v8::internal::HEnvironmentLivenessAnalysisPhase::DISALLOW_COPY_AND_ASSIGN ( HEnvironmentLivenessAnalysisPhase )

private

◆ Run()

void v8::internal::HEnvironmentLivenessAnalysisPhase::Run ( )

Definition at line 158 of file hydrogen-environment-liveness.cc.

                                             {
   DCHECK(maximum_environment_size_ > 0);
  
   // Main iteration. Compute liveness of environment slots, and store it
   // for each block until it doesn't change any more. For efficiency, visit
   // blocks in reverse order and walk backwards through each block. We
   // need several iterations to propagate liveness through nested loops.
   BitVector live(maximum_environment_size_, zone());
   BitVector worklist(block_count_, zone());
   for (int i = 0; i < block_count_; ++i) {
     worklist.Add(i);
   }
   while (!worklist.IsEmpty()) {
     for (int block_id = block_count_ - 1; block_id >= 0; --block_id) {
       if (!worklist.Contains(block_id)) {
         continue;
       }
       worklist.Remove(block_id);
       last_simulate_ = NULL;
  
       HBasicBlock* block = graph()->blocks()->at(block_id);
       UpdateLivenessAtBlockEnd(block, &live);
  
       for (HInstruction* instr = block->end(); instr != NULL;
            instr = instr->previous()) {
         UpdateLivenessAtInstruction(instr, &live);
       }
  
       // Reached the start of the block, do necessary bookkeeping:
       // store computed information for this block and add predecessors
       // to the work list as necessary.
       first_simulate_.Set(block_id, last_simulate_);
       first_simulate_invalid_for_index_[block_id]->CopyFrom(
           went_live_since_last_simulate_);
       if (live_at_block_start_[block_id]->UnionIsChanged(live)) {
         for (int i = 0; i < block->predecessors()->length(); ++i) {
           worklist.Add(block->predecessors()->at(i)->block_id());
         }
         if (block->IsInlineReturnTarget()) {
           worklist.Add(block->inlined_entry_block()->block_id());
         }
       }
     }
     // Only collect bind/lookup instructions during the first pass.
     collect_markers_ = false;
   }
  
   // Analysis finished. Zap dead environment slots.
   for (int i = 0; i < markers_.length(); ++i) {
     ZapEnvironmentSlotsForInstruction(markers_[i]);
   }
   for (int block_id = block_count_ - 1; block_id >= 0; --block_id) {
     HBasicBlock* block = graph()->blocks()->at(block_id);
     UpdateLivenessAtBlockEnd(block, &live);
     ZapEnvironmentSlotsInSuccessors(block, &live);
   }
  
   // Finally, remove the HEnvironment{Bind,Lookup} markers.
   for (int i = 0; i < markers_.length(); ++i) {
     markers_[i]->DeleteAndReplaceWith(NULL);
   }
 }

References v8::internal::BitVector::Add(), block_count_, collect_markers_, v8::internal::BitVector::Contains(), DCHECK, first_simulate_, first_simulate_invalid_for_index_, v8::internal::HPhase::graph(), v8::internal::BitVector::IsEmpty(), last_simulate_, live_at_block_start_, markers_, maximum_environment_size_, NULL, v8::internal::BitVector::Remove(), v8::internal::List< T, AllocationPolicy >::Set(), UpdateLivenessAtBlockEnd(), UpdateLivenessAtInstruction(), went_live_since_last_simulate_, ZapEnvironmentSlotsForInstruction(), and ZapEnvironmentSlotsInSuccessors().

Here is the call graph for this function:

◆ UpdateLivenessAtBlockEnd()

void v8::internal::HEnvironmentLivenessAnalysisPhase::UpdateLivenessAtBlockEnd	(	HBasicBlock *	block,
		BitVector *	live
	)

private

Definition at line 83 of file hydrogen-environment-liveness.cc.

                      {
   // Liveness at the end of each block: union of liveness in successors.
   live->Clear();
   for (HSuccessorIterator it(block->end()); !it.Done(); it.Advance()) {
     live->Union(*live_at_block_start_[it.Current()->block_id()]);
   }
 }

References v8::internal::BitVector::Clear(), live_at_block_start_, and v8::internal::BitVector::Union().

Referenced by Run().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ UpdateLivenessAtInstruction()

void v8::internal::HEnvironmentLivenessAnalysisPhase::UpdateLivenessAtInstruction	(	HInstruction *	instr,
		BitVector *	live
	)

private

Definition at line 94 of file hydrogen-environment-liveness.cc.

                      {
   switch (instr->opcode()) {
     case HValue::kEnvironmentMarker: {
       HEnvironmentMarker* marker = HEnvironmentMarker::cast(instr);
       int index = marker->index();
       if (!live->Contains(index)) {
         marker->SetFlag(HValue::kEndsLiveRange);
       } else {
         marker->ClearFlag(HValue::kEndsLiveRange);
       }
       if (!went_live_since_last_simulate_.Contains(index)) {
         marker->set_next_simulate(last_simulate_);
       }
       if (marker->kind() == HEnvironmentMarker::LOOKUP) {
         live->Add(index);
       } else {
         DCHECK(marker->kind() == HEnvironmentMarker::BIND);
         live->Remove(index);
         went_live_since_last_simulate_.Add(index);
       }
       if (collect_markers_) {
         // Populate |markers_| list during the first pass.
         markers_.Add(marker, zone());
       }
       break;
     }
     case HValue::kLeaveInlined:
       // No environment values are live at the end of an inlined section.
       live->Clear();
       last_simulate_ = NULL;
  
       // The following DCHECKs guard the assumption used in case
       // kEnterInlined below:
       DCHECK(instr->next()->IsSimulate());
       DCHECK(instr->next()->next()->IsGoto());
  
       break;
     case HValue::kEnterInlined: {
       // Those environment values are live that are live at any return
       // target block. Here we make use of the fact that the end of an
       // inline sequence always looks like this: HLeaveInlined, HSimulate,
       // HGoto (to return_target block), with no environment lookups in
       // between (see DCHECKs above).
       HEnterInlined* enter = HEnterInlined::cast(instr);
       live->Clear();
       for (int i = 0; i < enter->return_targets()->length(); ++i) {
         int return_id = enter->return_targets()->at(i)->block_id();
         live->Union(*live_at_block_start_[return_id]);
       }
       last_simulate_ = NULL;
       break;
     }
     case HValue::kSimulate:
       last_simulate_ = HSimulate::cast(instr);
       went_live_since_last_simulate_.Clear();
       break;
     default:
       break;
   }
 }

References v8::internal::List< T, AllocationPolicy >::Add(), v8::internal::BitVector::Add(), v8::internal::BitVector::Clear(), collect_markers_, v8::internal::BitVector::Contains(), DCHECK, v8::internal::HValue::kEndsLiveRange, last_simulate_, live_at_block_start_, markers_, v8::internal::HInstruction::next(), NULL, v8::internal::HValue::opcode(), v8::internal::BitVector::Remove(), v8::internal::BitVector::Union(), and went_live_since_last_simulate_.

Referenced by Run().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ ZapEnvironmentSlot()

void v8::internal::HEnvironmentLivenessAnalysisPhase::ZapEnvironmentSlot	(	int	index,
		HSimulate *	simulate
	)

private

Definition at line 36 of file hydrogen-environment-liveness.cc.

                                     {
   int operand_index = simulate->ToOperandIndex(index);
   if (operand_index == -1) {
     simulate->AddAssignedValue(index, graph()->GetConstantUndefined());
   } else {
     simulate->SetOperandAt(operand_index, graph()->GetConstantUndefined());
   }
 }

References v8::internal::HPhase::graph().

Referenced by ZapEnvironmentSlotsForInstruction(), and ZapEnvironmentSlotsInSuccessors().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ ZapEnvironmentSlotsForInstruction()

void v8::internal::HEnvironmentLivenessAnalysisPhase::ZapEnvironmentSlotsForInstruction ( HEnvironmentMarker * marker )

private

Definition at line 72 of file hydrogen-environment-liveness.cc.

                                 {
   if (!marker->CheckFlag(HValue::kEndsLiveRange)) return;
   HSimulate* simulate = marker->next_simulate();
   if (simulate != NULL) {
     DCHECK(VerifyClosures(simulate->closure(), marker->closure()));
     ZapEnvironmentSlot(marker->index(), simulate);
   }
 }

References DCHECK, v8::internal::HValue::kEndsLiveRange, NULL, and ZapEnvironmentSlot().

Referenced by Run().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ ZapEnvironmentSlotsInSuccessors()

void v8::internal::HEnvironmentLivenessAnalysisPhase::ZapEnvironmentSlotsInSuccessors	(	HBasicBlock *	block,
		BitVector *	live
	)

private

Definition at line 47 of file hydrogen-environment-liveness.cc.

                                          {
   // When a value is live in successor A but dead in B, we must
   // explicitly zap it in B.
   for (HSuccessorIterator it(block->end()); !it.Done(); it.Advance()) {
     HBasicBlock* successor = it.Current();
     int successor_id = successor->block_id();
     BitVector* live_in_successor = live_at_block_start_[successor_id];
     if (live_in_successor->Equals(*live)) continue;
     for (int i = 0; i < live->length(); ++i) {
       if (!live->Contains(i)) continue;
       if (live_in_successor->Contains(i)) continue;
       if (first_simulate_invalid_for_index_.at(successor_id)->Contains(i)) {
         continue;
       }
       HSimulate* simulate = first_simulate_.at(successor_id);
       if (simulate == NULL) continue;
       DCHECK(VerifyClosures(simulate->closure(),
           block->last_environment()->closure()));
       ZapEnvironmentSlot(i, simulate);
     }
   }
 }