[Interpreter] Local flow control in the bytecode graph builder.

src/compiler/bytecode-basic-block-analysis.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_BYTECODE_BASIC_BLOCK_ANALYSIS_H_
+#define V8_COMPILER_BYTECODE_BASIC_BLOCK_ANALYSIS_H_
+
+#include "src/bit-vector.h"
+#include "src/compiler.h"
+#include "src/zone-containers.h"
+
+namespace v8 {
+namespace internal {
+namespace compiler {
+
+class BytecodeBasicBlock;
+
+class BytecodeBasicBlockAnalysis {
+ public:
+  BytecodeBasicBlockAnalysis(Zone* zone, Handle<BytecodeArray> bytecode_array);
+  const ZoneVector<BytecodeBasicBlock*>* Analyze();
+
+ private:
+  void CreateBasicBlock(int start, int end);
+  void SplitBasicBlock(int offset);
+  void CreateBasicBlocks();
+  void LinkBasicBlocks();
+  void AssignRpoOrder();
+  void FindDominators();
+  void FindDependencyOrder();
+  void Dump();
+
+  Zone* zone() const { return zone_; }
+  BytecodeBasicBlock* start() { return block_map_[0]; }
+  BytecodeBasicBlock* exit() { return block_map_[bytecode_array_->length()]; }
+
+  Zone* zone_;
+  ZoneMap<int, BytecodeBasicBlock*> block_map_;
+  ZoneVector<BytecodeBasicBlock*> rpo_order_;
+  ZoneVector<BytecodeBasicBlock*> dependency_order_;
+  Handle<BytecodeArray> bytecode_array_;
+
+  DISALLOW_COPY_AND_ASSIGN(BytecodeBasicBlockAnalysis);
+};
+
+class BytecodeBasicBlock final : public ZoneObject {
+ public:
+  const int kInvalidOffset = -1;
+  static const int kUnassignedId = -1;
+
+  BytecodeBasicBlock(Zone* zone, int start, int end)
+      : start_(start),
+        end_(end),
+        last_bytecode_offset_(kInvalidOffset),
+        if_true_(nullptr),
+        if_false_(nullptr),
+        incoming_(zone),
+        rpo_id_(kUnassignedId),
+        dominator_rpo_ids_(nullptr) {}
+
+  int rpo_id() const { return rpo_id_; }
+  int start() const { return start_; }
+  int end() const { return end_; }
+  int last_bytecode_offset() const { return last_bytecode_offset_; }
+  BytecodeBasicBlock* if_true() const { return if_true_; }
+  BytecodeBasicBlock* if_false() const { return if_false_; }
+
+  bool ends_with_conditional_jump() const {
+    return if_true_ != nullptr && if_false_ != nullptr;
+  }
+
+  bool is_exit() const { return if_true_ == nullptr && if_false_ == nullptr; }
+
+  bool is_dominated_by(const BytecodeBasicBlock* block) const {
+    return dominator_rpo_ids_->Contains(block->rpo_id());
+  }
+
+  const BytecodeBasicBlock* incoming(size_t index) const {
+    return incoming_[index];
+  }
+  const size_t incoming_count() const { return incoming_.size(); }

[rmcilroy, 2015/12/08 13:25:07]

nit - newline above

[oth, 2015/12/09 11:26:45]

Done.

+
+ private:
+  ZoneVector<BytecodeBasicBlock*>* incoming() { return &incoming_; }
+  void add_incoming(BytecodeBasicBlock* incoming) {

[rmcilroy, 2015/12/08 13:25:07]

nit - newlines between all these functions down to end_with_block

[oth, 2015/12/09 11:26:45]

Done.

+    incoming_.push_back(incoming);
+  }
+  void set_end(int end) {
+    DCHECK_GT(end, start_);
+    DCHECK_LE(end, end_);
+    end_ = end;
+  }
+  void set_last_bytecode_offset(int offset) { last_bytecode_offset_ = offset; }
+  void end_with_conditional_jump(BytecodeBasicBlock* if_true,
+                                 BytecodeBasicBlock* if_false) {
+    DCHECK_NOT_NULL(if_true);
+    DCHECK_NULL(if_true_);
+    DCHECK_NOT_NULL(if_false);
+    DCHECK_NULL(if_false_);
+    if_true_ = if_true;
+    if_false_ = if_false;
+    if_true->add_incoming(this);
+    if_false->add_incoming(this);
+  }
+  void end_with_block(BytecodeBasicBlock* if_true) {
+    DCHECK_NOT_NULL(if_true);
+    DCHECK_NULL(if_true_);
+    DCHECK_NULL(if_false_);
+    if_true_ = if_true;
+    if_true->add_incoming(this);
+  }
+
+  void set_rpo_id(int rpo_id) { rpo_id_ = rpo_id; }
+  BitVector* dominator_rpo_ids() { return dominator_rpo_ids_; }
+  void set_dominator_rpo_ids(BitVector* ids) { dominator_rpo_ids_ = ids; }
+
+  int start_;
+  int end_;
+  int last_bytecode_offset_;
+  BytecodeBasicBlock* if_true_;
+  BytecodeBasicBlock* if_false_;
+  ZoneVector<BytecodeBasicBlock*> incoming_;
+  int rpo_id_;
+  BitVector* dominator_rpo_ids_;
+
+  friend class BytecodeBasicBlockAnalysis;
+};
+
+}  // namespace compiler
+}  // namespace internal
+}  // namespace v8
+
+#endif  // V8_COMPILER_BYTECODE_BASIC_BLOCK_ANALYSIS_H_