[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..c219ff6f33cd610e27a48c40d3d33a3fc3f14246
--- /dev/null
+++ b/src/compiler/liveness-analyzer.cc
@@ -0,0 +1,190 @@
+// 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"
+
+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(FrameStateRelaxer* relaxer) {
+  // Put all blocks into the queue.
+  DCHECK(queue_.empty());
+  for (auto block : blocks_) {
+    Queue(block);
+  }
+
+  // Compute the fix-point.
+  ZoneVector<bool> working_area(local_count_, false, 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, relaxer);
+  }
+}
+
+
+void LivenessAnalyzerBlock::Process(ZoneVector<bool>* result,
+                                    FrameStateRelaxer* relaxer) {
+  queued_ = false;
+
+  // Copy the bitvector to the target bit vector.
+  *result = live_;
+
+  for (auto i = entries_.rbegin(); i != entries_.rend(); i++) {
+    auto entry = *i;
+    switch (entry.kind()) {
+      case Entry::kLookup:
+        (*result)[entry.var()] = true;
+        break;
+      case Entry::kBind:
+        (*result)[entry.var()] = false;
+        break;
+      case Entry::kCheckpoint:
+        if (relaxer != nullptr) {
+          relaxer->RelaxFrameState(entry.node(), result);
+        }
+        break;
+    }
+  }
+}
+
+
+bool LivenessAnalyzerBlock::UpdateLive(ZoneVector<bool>* working_area) {
+  bool changed = false;
+  for (size_t i = 0; i < working_area->size(); i++) {
+    if ((*working_area)[i] && !live_[i]) {
+      // We can only make variables live during propagation.
+      live_[i] = true;
+      changed = true;
+    }
+  }
+  return changed;
+}
+
+
+void FrameStateRelaxer::RelaxFrameState(Node* frame_state,
+                                        ZoneVector<bool>* liveness) {
+  DCHECK_EQ(frame_state->opcode(), IrOpcode::kFrameState);
+  Node* locals_state = frame_state->InputAt(1);
+  DCHECK_EQ(locals_state->opcode(), IrOpcode::kStateValues);
+  int count = locals_state->InputCount();
+  DCHECK_EQ(count, static_cast<int>(liveness->size()));
+  for (int i = 0; i < count; i++) {
+    bool live = (*liveness)[i] || blacklist_[i];
+    if (!live || locals_state->InputAt(i) != replacement_node_) {
+      Node* new_values = RelaxStateValues(locals_state, liveness);
+      frame_state->ReplaceInput(1, new_values);
+      break;
+    }
+  }
+}
+
+
+Node* FrameStateRelaxer::RelaxStateValues(Node* values,
+                                          ZoneVector<bool>* liveness) {
+  int count = values->InputCount();
+  ZoneVector<Node*> inputs(count, nullptr, local_zone());
+  for (int i = 0; i < count; i++) {
+    bool live = (*liveness)[i] || blacklist_[i];
+    inputs[i] = live ? values->InputAt(i) : replacement_node_;
+  }
+  const Operator* op = js_graph()->common()->StateValues(count);
+  return js_graph()->graph()->NewNode(op, count,
+                                      count == 0 ? nullptr : &(inputs.front()));
+}
+
+
+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_.size() > 0) {
+    os << "    Live set: ";
+    for (bool live : live_) {
+      os << (live ? "L" : ".");
+    }
+    os << std::endl;
+  }
+}
+
+}  // namespace compiler
+}  // namespace internal
+}  // namespace v8