Liveness analysis for environment slots in Hydrogen

src/hydrogen-environment-liveness.cc

+// Copyright 2013 the V8 project authors. All rights reserved.
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are
+// met:
+//
+//     * Redistributions of source code must retain the above copyright
+//       notice, this list of conditions and the following disclaimer.
+//     * Redistributions in binary form must reproduce the above
+//       copyright notice, this list of conditions and the following
+//       disclaimer in the documentation and/or other materials provided
+//       with the distribution.
+//     * Neither the name of Google Inc. nor the names of its
+//       contributors may be used to endorse or promote products derived
+//       from this software without specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+
+#include "hydrogen-environment-liveness.h"
+
+
+namespace v8 {
+namespace internal {
+
+
+EnvironmentSlotLivenessAnalyzer::EnvironmentSlotLivenessAnalyzer(
+    HGraph* graph)
+    : graph_(graph),
+      zone_(graph->isolate()),
+      zone_scope_(&zone_, DELETE_ON_EXIT),
+      block_count_(graph->blocks()->length()),
+      maximum_environment_size_(graph->maximum_environment_size()),
+      collect_markers_(true),
+      last_simulate_(NULL) {
+  if (maximum_environment_size_ == 0) return;
+
+  live_at_block_start_ =
+      new(zone()) ZoneList<BitVector*>(block_count_, zone());
+  first_simulate_ = new(zone()) ZoneList<HSimulate*>(block_count_, zone());
+  first_simulate_invalid_for_index_ =
+      new(zone()) ZoneList<BitVector*>(block_count_, zone());
+  markers_ = new(zone())
+      ZoneList<HEnvironmentMarker*>(maximum_environment_size_, zone());
+  went_live_since_last_simulate_ =
+      new(zone()) BitVector(maximum_environment_size_, zone());
+
+  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());
+  }
+}
+
+
+void EnvironmentSlotLivenessAnalyzer::ZapEnvironmentSlot(int index,
+                                                         HSimulate* simulate) {
+  int operand_index = simulate->ToOperandIndex(index);
+  if (operand_index == -1) {
+    simulate->AddAssignedValue(index, graph_->GetConstantUndefined());
+  } else {
+    simulate->SetOperandAt(operand_index, graph_->GetConstantUndefined());
+  }
+}
+
+
+void EnvironmentSlotLivenessAnalyzer::ZapEnvironmentSlotsInSuccessors(
+    HBasicBlock* block,
+    BitVector* live) {
+  // 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_->at(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;
+      ASSERT(simulate->closure().is_identical_to(
+                 block->last_environment()->closure()));
+      ZapEnvironmentSlot(i, simulate);
+    }
+  }
+}
+
+
+void EnvironmentSlotLivenessAnalyzer::ZapEnvironmentSlotsForInstruction(
+    HEnvironmentMarker* marker) {
+  if (!marker->CheckFlag(HValue::kEndsLiveRange)) return;
+  HSimulate* simulate = marker->next_simulate();
+  if (simulate != NULL) {
+    ASSERT(simulate->closure().is_identical_to(marker->closure()));
+    ZapEnvironmentSlot(marker->index(), simulate);
+  }
+}
+
+
+void EnvironmentSlotLivenessAnalyzer::UpdateLivenessAtBlockEnd(
+    HBasicBlock* block,
+    BitVector* live) {
+  // 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_->at(it.Current()->block_id()));
+  }
+}
+
+
+void EnvironmentSlotLivenessAnalyzer::UpdateLivenessAtInstruction(
+    HInstruction* instr,
+    BitVector* live) {
+  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 {
+        ASSERT(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 ASSERTs guard the assumption used in case
+      // kEnterInlined below:
+      ASSERT(instr->next()->IsSimulate());
+      ASSERT(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 ASSERTs 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();
+        // When an AbnormalExit is involved, it can happen that the return
+        // target block doesn't actually exist.
+        if (return_id < live_at_block_start_->length()) {
+          live->Union(*live_at_block_start_->at(return_id));
+        }
+      }
+      last_simulate_ = NULL;
+      break;
+    }
+    case HValue::kDeoptimize: {
+      // Keep all environment slots alive.
+      HDeoptimize* deopt = HDeoptimize::cast(instr);
+      for (int i = deopt->first_local_index();
+           i < deopt->first_expression_index(); ++i) {
+        live->Add(i);
+      }
+      break;
+    }
+    case HValue::kSimulate:
+      last_simulate_ = HSimulate::cast(instr);
+      went_live_since_last_simulate_->Clear();
+      break;
+    default:
+      break;
+  }
+}
+
+
+void EnvironmentSlotLivenessAnalyzer::AnalyzeAndTrim() {
+  HPhase phase("H_EnvironmentLivenessAnalysis", graph_);
+  if (maximum_environment_size_ == 0) return;
+
+  // 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 = new(zone()) BitVector(maximum_environment_size_, zone());
+  BitVector* worklist = new(zone()) BitVector(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->last(); 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_->at(block_id)->CopyFrom(
+          *went_live_since_last_simulate_);
+      if (live_at_block_start_->at(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_->at(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_->at(i)->DeleteAndReplaceWith(NULL);
+  }
+}
+
+} }  // namespace v8::internal