[turbofan] Variable liveness analysis for deopt

src/compiler/liveness-analyzer.h

+// Copyright 2015 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.
+
+#ifndef V8_COMPILER_LIVENESS_ANAYZER_H_
+#define V8_COMPILER_LIVENESS_ANAYZER_H_
+
+#include "src/zone-containers.h"
+
+namespace v8 {
+namespace internal {
+namespace compiler {
+
+class LivenessAnalyzerBlock;
+class Node;
+class JSGraph;
+
+
+class FrameStateRelaxer {
+ public:
+  void RelaxFrameState(Node* frame_state, ZoneVector<bool>* liveness);

[titzer, 2015/02/27 21:03:54]

Can we use a BitVector here and in the implementation. The space usage of
ZoneVector<bool> is probably not a big issue, but with BitVector it will
definitely be smaller, and we are already using BitVector in other analyses like
loop assignment analsysis.

[Jarin, 2015/03/16 21:30:12]

Done. (Will BitVector be really smaller? Why?)

+  FrameStateRelaxer(JSGraph* js_graph, Node* replacement, size_t local_count,
+                    Zone* local_zone)
+      : replacement_node_(replacement),
+        js_graph_(js_graph),
+        local_zone_(local_zone),
+        blacklist_(local_count, false, local_zone) {}
+
+  void Blacklist(int var) { blacklist_[var] = true; }
+
+ private:
+  Node* RelaxStateValues(Node* frame_state, ZoneVector<bool>* liveness);
+
+  JSGraph* js_graph() { return js_graph_; }
+  Zone* local_zone() { return local_zone_; }
+
+  // Node that replaces dead values.
+  Node* replacement_node_;
+  // Reference to graph so that we can create new nodes.
+  JSGraph* js_graph_;
+
+  Zone* local_zone_;
+
+  ZoneVector<bool> blacklist_;
+};
+
+
+class LivenessAnalyzer : public ZoneObject {
+ public:
+  LivenessAnalyzer(size_t local_count, Zone* zone);
+
+  LivenessAnalyzerBlock* New();
+  LivenessAnalyzerBlock* New(LivenessAnalyzerBlock* predecessor);
+
+  void Run(FrameStateRelaxer* relaxer);
+
+  Zone* zone() { return zone_; }
+
+  void Print(std::ostream& os);
+
+  size_t local_count() { return local_count_; }
+
+ private:
+  void Queue(LivenessAnalyzerBlock* block);
+
+  Zone* zone_;
+  ZoneDeque<LivenessAnalyzerBlock*> blocks_;
+  size_t local_count_;
+
+  ZoneQueue<LivenessAnalyzerBlock*> queue_;
+};
+
+
+class LivenessAnalyzerBlock : public ZoneObject {
+ public:
+  friend class LivenessAnalyzer;
+
+  void Lookup(int var) { entries_.push_back(Entry(Entry::kLookup, var)); }
+  void Bind(int var) { entries_.push_back(Entry(Entry::kBind, var)); }
+  void Checkpoint(Node* node) { entries_.push_back(Entry(node)); }
+  void AddPredecessor(LivenessAnalyzerBlock* b) { predecessors_.push_back(b); }
+
+ private:
+  class Entry {
+   public:
+    enum Kind { kBind, kLookup, kCheckpoint };
+
+    Kind kind() const { return kind_; }
+    Node* node() const {
+      DCHECK(kind() == kCheckpoint);
+      return node_;
+    }
+    int var() const {
+      DCHECK(kind() != kCheckpoint);
+      return var_;
+    }
+
+    explicit Entry(Node* node) : kind_(kCheckpoint), var_(-1), node_(node) {}
+    Entry(Kind kind, int var) : kind_(kind), var_(var), node_(nullptr) {
+      DCHECK(kind != kCheckpoint);
+    }
+
+   private:
+    Kind kind_;
+    int var_;
+    Node* node_;
+  };
+
+  LivenessAnalyzerBlock(size_t id, size_t local_count, Zone* zone)
+      : entries_(zone),
+        predecessors_(zone),
+        live_(local_count, false, zone),
+        queued_(false),
+        id_(id) {}
+  void Process(ZoneVector<bool>* result, FrameStateRelaxer* relaxer);
+  bool UpdateLive(ZoneVector<bool>* working_area);
+
+  void SetQueued() { queued_ = true; }
+  bool IsQueued() { return queued_; }
+
+  ZoneDeque<LivenessAnalyzerBlock*>::const_iterator pred_begin() {
+    return predecessors_.begin();
+  }
+  ZoneDeque<LivenessAnalyzerBlock*>::const_iterator pred_end() {
+    return predecessors_.end();
+  }
+
+  size_t id() { return id_; }
+  void Print(std::ostream& os);
+
+  ZoneDeque<Entry> entries_;
+  ZoneDeque<LivenessAnalyzerBlock*> predecessors_;
+
+  ZoneVector<bool> live_;
+  bool queued_;
+
+  size_t id_;
+};
+
+
+}  // namespace compiler
+}  // namespace internal
+}  // namespace v8
+
+#endif  // V8_COMPILER_AST_GRAPH_BUILDER_H_