src/v8/src/hydrogen-environment-liveness.cc

   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 "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   ASSERT(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       ASSERT(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     ASSERT(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         ASSERT(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 ASSERTs guard the assumption used in case
 128       // kEnterInlined below:
 129       ASSERT(instr->next()->IsSimulate());
 130       ASSERT(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 ASSERTs 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   ASSERT(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 v8::internal