Liveness analysis for environment slots in Hydrogen

src/hydrogen-environment-liveness.cc

Index: src/hydrogen-environment-liveness.cc
diff --git a/src/hydrogen-environment-liveness.cc b/src/hydrogen-environment-liveness.cc
new file mode 100644
index 0000000000000000000000000000000000000000..79d8d3402f807f8f66a5e1866337ba0883e33ad9
--- /dev/null
+++ b/src/hydrogen-environment-liveness.cc
@@ -0,0 +1,238 @@
+// 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 {
+
+
+void EnvironmentSlotLivenessAnalysis::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 EnvironmentSlotLivenessAnalysis::ZapEnvironmentSlotsInSuccessors(
+    HBasicBlock* block) {
+  // 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 EnvironmentSlotLivenessAnalysis::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 EnvironmentSlotLivenessAnalysis::UpdateLivenessAtBlockEnd(
+    HBasicBlock* block) {

[titzer, 2013/05/29 16:58:05]

E.g. here, it would be more clear to pass in the temporary live_ bitvector, so
that it's clear the caller expects the method to modify it.

[Jakob Kummerow, 2013/06/03 17:50:38]

Done.

+  // 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 EnvironmentSlotLivenessAnalysis::UpdateLivenessAtInstruction(
+    HInstruction* instr) {
+  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_) {

[titzer, 2013/05/29 16:58:05]

This is a little tricky; maybe a comment that we only collect markers the first
time through the graph.

[Jakob Kummerow, 2013/06/03 17:50:38]

Done.

+        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: {

[titzer, 2013/05/29 16:58:05]

What about kSoftDeoptimize?

[Jakob Kummerow, 2013/06/03 17:50:38]

Usage is different.
HSoftDeoptimize instructions do not affect live ranges in any way, so they don't
need any special handling here.
There are uses of HDeoptimize however that assume that the entire environment is
available. I'm hoping that this will change eventually, but that's a different
issue.

+      // 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;
+  }
+}
+
+
+// Values in the environment are kept alive by every subsequent LInstruction

[titzer, 2013/05/29 16:58:05]

Some reordering of the sentences might make this paragraph clearer. E.g. first
sentence should probably be something to the effect of "Trim live ranges of
environment slots by doing explicit liveness analysis". And then why this is
necessary (stuff is live too long because of environments, and then maybe any
relevant details.

[Jakob Kummerow, 2013/06/03 17:50:38]

Done, and moved to the class, where this comment really makes more sense now.

+// that is assigned an LEnvironment. This creates register pressure and
+// unnecessary spill slot moves. Therefore it is beneficial to trim the
+// live ranges of environment slots by zapping them with a constant after
+// the last lookup that refers to them. This is similar but not identical
+// to live range analysis for HValues, so we perform an explicit liveness
+// analysis on environment slots (identified by their index).
+// This only affects slots whitelisted by
+// HOptimizedGraphBuilder::IsEligibleForEnvironmentLivenessAnalysis().
+void EnvironmentSlotLivenessAnalysis::AnalyzeAndPrune() {
+  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* 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);
+
+      for (HInstruction* instr = block->last(); instr != NULL;
+           instr = instr->previous()) {
+        UpdateLivenessAtInstruction(instr);
+      }
+
+      // Reached the start of the block, do necessary bookkeeping.

[titzer, 2013/05/29 16:58:05]

Explain bookkeeping steps. E.g. "propagate liveness to predecessors" would do.

[Jakob Kummerow, 2013/06/03 17:50:38]

Done.

+      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);
+    ZapEnvironmentSlotsInSuccessors(block);
+  }
+
+  // Finally, remove the HEnvironment{Bind,Lookup} markers.
+  for (int i = 0; i < markers_->length(); ++i) {
+    markers_->at(i)->DeleteAndReplaceWith(NULL);
+  }
+}
+
+} }  // namespace v8::internal