Home | History | Annotate | Download | only in crankshaft 
      1 // Copyright 2013 the V8 project authors. All rights reserved.
      2 // Use of this source code is governed by a BSD-style license that can be
      3 // found in the LICENSE file.
      4 
      5 
      6 #include "src/crankshaft/hydrogen-environment-liveness.h"
      7 
      8 
      9 namespace v8 {
     10 namespace internal {
     11 
     12 
     13 HEnvironmentLivenessAnalysisPhase::HEnvironmentLivenessAnalysisPhase(
     14     HGraph* graph)
     15     : HPhase("H_Environment liveness analysis", graph),
     16       block_count_(graph->blocks()->length()),
     17       maximum_environment_size_(graph->maximum_environment_size()),
     18       live_at_block_start_(block_count_, zone()),
     19       first_simulate_(block_count_, zone()),
     20       first_simulate_invalid_for_index_(block_count_, zone()),
     21       markers_(maximum_environment_size_, zone()),
     22       collect_markers_(true),
     23       last_simulate_(NULL),
     24       went_live_since_last_simulate_(maximum_environment_size_, zone()) {
     25   DCHECK(maximum_environment_size_ > 0);
     26   for (int i = 0; i < block_count_; ++i) {
     27     live_at_block_start_.Add(
     28         new(zone()) BitVector(maximum_environment_size_, zone()), zone());
     29     first_simulate_.Add(NULL, zone());
     30     first_simulate_invalid_for_index_.Add(
     31         new(zone()) BitVector(maximum_environment_size_, zone()), zone());
     32   }
     33 }
     34 
     35 
     36 void HEnvironmentLivenessAnalysisPhase::ZapEnvironmentSlot(
     37     int index, HSimulate* simulate) {
     38   int operand_index = simulate->ToOperandIndex(index);
     39   if (operand_index == -1) {
     40     simulate->AddAssignedValue(index, graph()->GetConstantUndefined());
     41   } else {
     42     simulate->SetOperandAt(operand_index, graph()->GetConstantUndefined());
     43   }
     44 }
     45 
     46 
     47 void HEnvironmentLivenessAnalysisPhase::ZapEnvironmentSlotsInSuccessors(
     48     HBasicBlock* block, BitVector* live) {
     49   // When a value is live in successor A but dead in B, we must
     50   // explicitly zap it in B.
     51   for (HSuccessorIterator it(block->end()); !it.Done(); it.Advance()) {
     52     HBasicBlock* successor = it.Current();
     53     int successor_id = successor->block_id();
     54     BitVector* live_in_successor = live_at_block_start_[successor_id];
     55     if (live_in_successor->Equals(*live)) continue;
     56     for (int i = 0; i < live->length(); ++i) {
     57       if (!live->Contains(i)) continue;
     58       if (live_in_successor->Contains(i)) continue;
     59       if (first_simulate_invalid_for_index_.at(successor_id)->Contains(i)) {
     60         continue;
     61       }
     62       HSimulate* simulate = first_simulate_.at(successor_id);
     63       if (simulate == NULL) continue;
     64       DCHECK(VerifyClosures(simulate->closure(),
     65           block->last_environment()->closure()));
     66       ZapEnvironmentSlot(i, simulate);
     67     }
     68   }
     69 }
     70 
     71 
     72 void HEnvironmentLivenessAnalysisPhase::ZapEnvironmentSlotsForInstruction(
     73     HEnvironmentMarker* marker) {
     74   if (!marker->CheckFlag(HValue::kEndsLiveRange)) return;
     75   HSimulate* simulate = marker->next_simulate();
     76   if (simulate != NULL) {
     77     DCHECK(VerifyClosures(simulate->closure(), marker->closure()));
     78     ZapEnvironmentSlot(marker->index(), simulate);
     79   }
     80 }
     81 
     82 
     83 void HEnvironmentLivenessAnalysisPhase::UpdateLivenessAtBlockEnd(
     84     HBasicBlock* block,
     85     BitVector* live) {
     86   // Liveness at the end of each block: union of liveness in successors.
     87   live->Clear();
     88   for (HSuccessorIterator it(block->end()); !it.Done(); it.Advance()) {
     89     live->Union(*live_at_block_start_[it.Current()->block_id()]);
     90   }
     91 }
     92 
     93 
     94 void HEnvironmentLivenessAnalysisPhase::UpdateLivenessAtInstruction(
     95     HInstruction* instr,
     96     BitVector* live) {
     97   switch (instr->opcode()) {
     98     case HValue::kEnvironmentMarker: {
     99       HEnvironmentMarker* marker = HEnvironmentMarker::cast(instr);
    100       int index = marker->index();
    101       if (!live->Contains(index)) {
    102         marker->SetFlag(HValue::kEndsLiveRange);
    103       } else {
    104         marker->ClearFlag(HValue::kEndsLiveRange);
    105       }
    106       if (!went_live_since_last_simulate_.Contains(index)) {
    107         marker->set_next_simulate(last_simulate_);
    108       }
    109       if (marker->kind() == HEnvironmentMarker::LOOKUP) {
    110         live->Add(index);
    111       } else {
    112         DCHECK(marker->kind() == HEnvironmentMarker::BIND);
    113         live->Remove(index);
    114         went_live_since_last_simulate_.Add(index);
    115       }
    116       if (collect_markers_) {
    117         // Populate |markers_| list during the first pass.
    118         markers_.Add(marker, zone());
    119       }
    120       break;
    121     }
    122     case HValue::kLeaveInlined:
    123       // No environment values are live at the end of an inlined section.
    124       live->Clear();
    125       last_simulate_ = NULL;
    126 
    127       // The following DCHECKs guard the assumption used in case
    128       // kEnterInlined below:
    129       DCHECK(instr->next()->IsSimulate());
    130       DCHECK(instr->next()->next()->IsGoto());
    131 
    132       break;
    133     case HValue::kEnterInlined: {
    134       // Those environment values are live that are live at any return
    135       // target block. Here we make use of the fact that the end of an
    136       // inline sequence always looks like this: HLeaveInlined, HSimulate,
    137       // HGoto (to return_target block), with no environment lookups in
    138       // between (see DCHECKs above).
    139       HEnterInlined* enter = HEnterInlined::cast(instr);
    140       live->Clear();
    141       for (int i = 0; i < enter->return_targets()->length(); ++i) {
    142         int return_id = enter->return_targets()->at(i)->block_id();
    143         live->Union(*live_at_block_start_[return_id]);
    144       }
    145       last_simulate_ = NULL;
    146       break;
    147     }
    148     case HValue::kSimulate:
    149       last_simulate_ = HSimulate::cast(instr);
    150       went_live_since_last_simulate_.Clear();
    151       break;
    152     default:
    153       break;
    154   }
    155 }
    156 
    157 
    158 void HEnvironmentLivenessAnalysisPhase::Run() {
    159   DCHECK(maximum_environment_size_ > 0);
    160 
    161   // Main iteration. Compute liveness of environment slots, and store it
    162   // for each block until it doesn't change any more. For efficiency, visit
    163   // blocks in reverse order and walk backwards through each block. We
    164   // need several iterations to propagate liveness through nested loops.
    165   BitVector live(maximum_environment_size_, zone());
    166   BitVector worklist(block_count_, zone());
    167   for (int i = 0; i < block_count_; ++i) {
    168     worklist.Add(i);
    169   }
    170   while (!worklist.IsEmpty()) {
    171     for (int block_id = block_count_ - 1; block_id >= 0; --block_id) {
    172       if (!worklist.Contains(block_id)) {
    173         continue;
    174       }
    175       worklist.Remove(block_id);
    176       last_simulate_ = NULL;
    177 
    178       HBasicBlock* block = graph()->blocks()->at(block_id);
    179       UpdateLivenessAtBlockEnd(block, &live);
    180 
    181       for (HInstruction* instr = block->end(); instr != NULL;
    182            instr = instr->previous()) {
    183         UpdateLivenessAtInstruction(instr, &live);
    184       }
    185 
    186       // Reached the start of the block, do necessary bookkeeping:
    187       // store computed information for this block and add predecessors
    188       // to the work list as necessary.
    189       first_simulate_.Set(block_id, last_simulate_);
    190       first_simulate_invalid_for_index_[block_id]->CopyFrom(
    191           went_live_since_last_simulate_);
    192       if (live_at_block_start_[block_id]->UnionIsChanged(live)) {
    193         for (int i = 0; i < block->predecessors()->length(); ++i) {
    194           worklist.Add(block->predecessors()->at(i)->block_id());
    195         }
    196         if (block->IsInlineReturnTarget()) {
    197           worklist.Add(block->inlined_entry_block()->block_id());
    198         }
    199       }
    200     }
    201     // Only collect bind/lookup instructions during the first pass.
    202     collect_markers_ = false;
    203   }
    204 
    205   // Analysis finished. Zap dead environment slots.
    206   for (int i = 0; i < markers_.length(); ++i) {
    207     ZapEnvironmentSlotsForInstruction(markers_[i]);
    208   }
    209   for (int block_id = block_count_ - 1; block_id >= 0; --block_id) {
    210     HBasicBlock* block = graph()->blocks()->at(block_id);
    211     UpdateLivenessAtBlockEnd(block, &live);
    212     ZapEnvironmentSlotsInSuccessors(block, &live);
    213   }
    214 
    215   // Finally, remove the HEnvironment{Bind,Lookup} markers.
    216   for (int i = 0; i < markers_.length(); ++i) {
    217     markers_[i]->DeleteAndReplaceWith(NULL);
    218   }
    219 }
    220 
    221 
    222 #ifdef DEBUG
    223 bool HEnvironmentLivenessAnalysisPhase::VerifyClosures(
    224     Handle<JSFunction> a, Handle<JSFunction> b) {
    225   Heap::RelocationLock for_heap_access(isolate()->heap());
    226   AllowHandleDereference for_verification;
    227   return a.is_identical_to(b);
    228 }
    229 #endif
    230 
    231 }  // namespace internal
    232 }  // namespace v8
    233