[turbofan] Variable liveness analysis for deopt

src/compiler/liveness-analyzer.cc

Index: src/compiler/liveness-analyzer.cc
diff --git a/src/compiler/liveness-analyzer.cc b/src/compiler/liveness-analyzer.cc
new file mode 100644
index 0000000000000000000000000000000000000000..ae476d2697cb9eec84924c4307b41afb68a1b8eb
--- /dev/null
+++ b/src/compiler/liveness-analyzer.cc
@@ -0,0 +1,188 @@
+// Copyright 2014 the V8 project authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "src/compiler/liveness-analyzer.h"
+#include "src/compiler/js-graph.h"
+#include "src/compiler/node.h"
+#include "src/compiler/node-matchers.h"
+#include "src/compiler/state-values-utils.h"
+
+namespace v8 {
+namespace internal {
+namespace compiler {
+
+
+LivenessAnalyzer::LivenessAnalyzer(size_t local_count, Zone* zone)
+    : zone_(zone), blocks_(zone), local_count_(local_count), queue_(zone) {}
+
+
+void LivenessAnalyzer::Print(std::ostream& os) {
+  for (auto block : blocks_) {
+    block->Print(os);
+    os << std::endl;
+  }
+}
+
+
+LivenessAnalyzerBlock* LivenessAnalyzer::New() {
+  LivenessAnalyzerBlock* result =
+      new (zone()) LivenessAnalyzerBlock(blocks_.size(), local_count_, zone());
+  blocks_.push_back(result);
+  return result;
+}
+
+
+LivenessAnalyzerBlock* LivenessAnalyzer::New(
+    LivenessAnalyzerBlock* predecessor) {
+  LivenessAnalyzerBlock* result = New();
+  result->AddPredecessor(predecessor);
+  return result;
+}
+
+
+void LivenessAnalyzer::Queue(LivenessAnalyzerBlock* block) {
+  if (!block->IsQueued()) {
+    block->SetQueued();
+    queue_.push(block);
+  }
+}
+
+
+void LivenessAnalyzer::Run(NonLiveFrameStateSlotReplacer* replacer) {
+  // Put all blocks into the queue.
+  DCHECK(queue_.empty());
+  for (auto block : blocks_) {
+    Queue(block);
+  }
+
+  // Compute the fix-point.
+  BitVector working_area(local_count_ == 0 ? 1 : static_cast<int>(local_count_),

[Benedikt Meurer, 2015/03/17 05:12:03]

Is it worth adding a shortcut of the rest for local_count_ == 0? In that case
you just need to setup the live_ target bit vector unless I'm missing something?

[Jarin, 2015/03/17 09:22:57]

Done.

+                         zone_);
+  while (!queue_.empty()) {
+    LivenessAnalyzerBlock* block = queue_.front();
+    queue_.pop();
+    block->Process(&working_area, nullptr);
+
+    for (auto i = block->pred_begin(); i != block->pred_end(); i++) {
+      if ((*i)->UpdateLive(&working_area)) {
+        Queue(*i);
+      }
+    }
+  }
+
+  // Update the frame states according to the liveness.
+  for (auto block : blocks_) {
+    block->Process(&working_area, replacer);
+  }
+}
+
+
+void LivenessAnalyzerBlock::Process(BitVector* result,
+                                    NonLiveFrameStateSlotReplacer* replacer) {
+  queued_ = false;
+
+  // Copy the bitvector to the target bit vector.
+  result->CopyFrom(live_);
+
+  for (auto i = entries_.rbegin(); i != entries_.rend(); i++) {
+    auto entry = *i;
+    switch (entry.kind()) {
+      case Entry::kLookup:
+        result->Add(entry.var());
+        break;
+      case Entry::kBind:
+        result->Remove(entry.var());
+        break;
+      case Entry::kCheckpoint:
+        if (replacer != nullptr) {
+          replacer->ClearNonLiveFrameStateSlots(entry.node(), result);
+        }
+        break;
+    }
+  }
+}
+
+
+bool LivenessAnalyzerBlock::UpdateLive(BitVector* working_area) {
+  return live_.UnionIsChanged(*working_area);
+}
+
+
+void NonLiveFrameStateSlotReplacer::ClearNonLiveFrameStateSlots(
+    Node* frame_state, BitVector* liveness) {
+  DCHECK_EQ(frame_state->opcode(), IrOpcode::kFrameState);
+  Node* locals_state = frame_state->InputAt(1);
+  DCHECK_EQ(locals_state->opcode(), IrOpcode::kStateValues);
+  int count = static_cast<int>(StateValuesAccess(locals_state).size());
+  DCHECK_EQ(count == 0 ? 1 : count, liveness->length());
+  for (int i = 0; i < count; i++) {
+    bool live = liveness->Contains(i) || permanently_live_.Contains(i);
+    if (!live || locals_state->InputAt(i) != replacement_node_) {
+      Node* new_values = ClearNonLiveStateValues(locals_state, liveness);
+      frame_state->ReplaceInput(1, new_values);
+      break;
+    }
+  }
+}
+
+
+Node* NonLiveFrameStateSlotReplacer::ClearNonLiveStateValues(
+    Node* values, BitVector* liveness) {
+  DCHECK(inputs_buffer_.empty());
+  for (Node* node : StateValuesAccess(values)) {
+    // Index of the next variable is its furure index in the inputs buffer,
+    // i.e., the buffer's size.
+    int var = static_cast<int>(inputs_buffer_.size());
+    bool live = liveness->Contains(var) || permanently_live_.Contains(var);
+    inputs_buffer_.push_back(live ? node : replacement_node_);
+  }
+  Node* result = state_values_cache()->GetNodeForValues(
+      inputs_buffer_.empty() ? nullptr : &(inputs_buffer_.front()),
+      inputs_buffer_.size());
+  inputs_buffer_.clear();
+  return result;
+}
+
+
+void LivenessAnalyzerBlock::Print(std::ostream& os) {
+  os << "Block " << id();
+  bool first = true;
+  for (LivenessAnalyzerBlock* pred : predecessors_) {
+    if (!first) {
+      os << ", ";
+    } else {
+      os << "; predecessors: ";
+      first = false;
+    }
+    os << pred->id();
+  }
+  os << std::endl;
+
+  for (auto entry : entries_) {
+    os << "    ";
+    switch (entry.kind()) {
+      case Entry::kLookup:
+        os << "- Lookup " << entry.var() << std::endl;
+        break;
+      case Entry::kBind:
+        os << "- Bind " << entry.var() << std::endl;
+        break;
+      case Entry::kCheckpoint:
+        os << "- Checkpoint " << entry.node()->id() << std::endl;
+        break;
+    }
+  }
+
+  if (live_.length() > 0) {
+    os << "    Live set: ";
+    for (int i = 0; i < live_.length(); i++) {
+      os << (live_.Contains(i) ? "L" : ".");
+    }
+    os << std::endl;
+  }
+}
+
+}  // namespace compiler
+}  // namespace internal
+}  // namespace v8