[WIP] Node splitting in Scheduler.

src/compiler/scheduler.cc

Index: src/compiler/scheduler.cc
diff --git a/src/compiler/scheduler.cc b/src/compiler/scheduler.cc
index 6281371abacc6b737045d38ac1f5de4ef32c4bcb..5bf9a839b47eb422e55d443fd362c9565b68c90b 100644
--- a/src/compiler/scheduler.cc
+++ b/src/compiler/scheduler.cc
@@ -27,20 +27,21 @@ static inline void Trace(const char* msg, ...) {
 }
 
 
-Scheduler::Scheduler(Zone* zone, Graph* graph, Schedule* schedule)
+Scheduler::Scheduler(Zone* zone, Graph* graph, Schedule* schedule, Flags flags)
     : zone_(zone),
       graph_(graph),
       schedule_(schedule),
+      flags_(flags),
       scheduled_nodes_(zone),
       schedule_root_nodes_(zone),
       schedule_queue_(zone),
       node_data_(graph_->NodeCount(), DefaultSchedulerData(), zone) {}
 
 
-Schedule* Scheduler::ComputeSchedule(Zone* zone, Graph* graph) {
+Schedule* Scheduler::ComputeSchedule(Zone* zone, Graph* graph, Flags flags) {
   Schedule* schedule = new (graph->zone())
       Schedule(graph->zone(), static_cast<size_t>(graph->NodeCount()));
-  Scheduler scheduler(zone, graph, schedule);
+  Scheduler scheduler(zone, graph, schedule, flags);
 
   scheduler.BuildCFG();
   scheduler.ComputeSpecialRPONumbering();
@@ -1226,7 +1227,10 @@ void Scheduler::ScheduleEarly() {
 class ScheduleLateNodeVisitor {
  public:
   ScheduleLateNodeVisitor(Zone* zone, Scheduler* scheduler)
-      : scheduler_(scheduler), schedule_(scheduler_->schedule_) {}
+      : scheduler_(scheduler),
+        schedule_(scheduler_->schedule_),
+        visited_(scheduler->zone_),
+        stack_(scheduler->zone_) {}
 
   // Run the schedule late algorithm on a set of fixed root nodes.
   void Run(NodeVector* roots) {
@@ -1249,8 +1253,9 @@ class ScheduleLateNodeVisitor {
 
       queue->push(node);
       while (!queue->empty()) {
-        VisitNode(queue->front());
+        Node* const node = queue->front();
         queue->pop();
+        VisitNode(node);
       }
     }
   }
@@ -1282,13 +1287,21 @@ class ScheduleLateNodeVisitor {
     // into enclosing loop pre-headers until they would preceed their schedule
     // early position.
     BasicBlock* hoist_block = GetPreHeader(block);
-    while (hoist_block != NULL &&
-           hoist_block->dominator_depth() >= min_block->dominator_depth()) {
-      Trace("  hoisting #%d:%s to block B%d\n", node->id(),
-            node->op()->mnemonic(), hoist_block->id().ToInt());
-      DCHECK_LT(hoist_block->loop_depth(), block->loop_depth());
-      block = hoist_block;
-      hoist_block = GetPreHeader(hoist_block);
+    if (hoist_block &&
+        hoist_block->dominator_depth() >= min_block->dominator_depth()) {
+      do {
+        Trace("  hoisting #%d:%s to block B%d\n", node->id(),
+              node->op()->mnemonic(), hoist_block->id().ToInt());
+        DCHECK_LT(hoist_block->loop_depth(), block->loop_depth());
+        block = hoist_block;
+        hoist_block = GetPreHeader(hoist_block);
+      } while (hoist_block &&
+               hoist_block->dominator_depth() >= min_block->dominator_depth());
+    } else if (scheduler_->flags_ & Scheduler::kSplitNodes &&
+               block->SuccessorCount() >= 2 &&
+               node->op()->HasProperty(Operator::kPure)) {
+      // Split the {node} if beneficial and return the new {block} for it.
+      if (SplitNode(block, node)) return;
     }
 
     // Schedule the node or a floating control structure.
@@ -1299,6 +1312,86 @@ class ScheduleLateNodeVisitor {
     }
   }
 
+  bool SplitNode(BasicBlock* block, Node* node) {
+    std::fill(visited_.begin(), visited_.end(), false);
+    visited_.resize(schedule_->BasicBlockCount() + 1, false);
+    stack_.clear();
+
+    // Check if the {node} has uses in {block}.
+    for (Edge edge : node->use_edges()) {
+      BasicBlock* use_block = GetBlockForUse(edge);
+      if (use_block == block) {
+        Trace("  not splitting #%d:%s, it is used in B%d\n", node->id(),
+              node->op()->mnemonic(), block->id().ToInt());
+        return false;
+      }
+      if (use_block) {
+        visited_[use_block->id().ToSize()] = true;
+        for (BasicBlock* predecessor : use_block->predecessors()) {
+          stack_.push_back(predecessor);
+        }
+      }
+    }
+
+    while (!stack_.empty()) {
+      BasicBlock* block = stack_.back();
+      stack_.pop_back();
+      bool visited = visited_[block->id().ToSize()];
+      if (visited) continue;
+      visited = true;
+      for (BasicBlock* successor : block->successors()) {
+        if (!visited_[successor->id().ToSize()]) {
+          visited = false;
+          break;
+        }
+      }
+      if (visited) {
+        visited_[block->id().ToSize()] = true;
+        for (BasicBlock* predecessor : block->predecessors()) {
+          stack_.push_back(predecessor);
+        }
+      }
+    }
+
+    if (visited_[block->id().ToSize()]) {
+      return false;
+    }
+
+    std::map<BasicBlock*, Node*> dominators;
+    for (Edge edge : node->use_edges()) {
+      BasicBlock* use_block = GetBlockForUse(edge);
+      if (!use_block) continue;
+      BasicBlock* dominator = use_block;
+      DCHECK(visited_[dominator->id().ToSize()]);
+      while (visited_[dominator->dominator()->id().ToSize()]) {
+        dominator = dominator->dominator();
+      }
+      if (dominators.find(dominator) == dominators.end()) {
+        if (dominators.size() == 0) {
+          dominators.insert(std::make_pair(dominator, node));
+          scheduler_->schedule_queue_.push(node);
+        } else {
+          Node* copy = CloneNode(node);
+          dominators.insert(std::make_pair(dominator, copy));
+          scheduler_->schedule_queue_.push(copy);
+        }
+      }
+    }
+
+    for (Edge edge : node->use_edges()) {
+      BasicBlock* use_block = GetBlockForUse(edge);
+      if (!use_block) continue;
+      for (;; use_block = use_block->dominator()) {
+        DCHECK(visited_[use_block->id().ToSize()]);
+        if (Node* node = dominators[use_block]) {
+          edge.UpdateTo(node);
+          break;
+        }
+      }
+    }
+    return true;
+  }
+
   BasicBlock* GetPreHeader(BasicBlock* block) {
     if (block->IsLoopHeader()) {
       return block->dominator();
@@ -1310,7 +1403,7 @@ class ScheduleLateNodeVisitor {
   }
 
   BasicBlock* GetCommonDominatorOfUses(Node* node) {
-    BasicBlock* block = NULL;
+    BasicBlock* block = nullptr;
     for (Edge edge : node->use_edges()) {
       BasicBlock* use_block = GetBlockForUse(edge);
       block = block == NULL ? use_block : use_block == NULL
@@ -1361,8 +1454,25 @@ class ScheduleLateNodeVisitor {
     scheduler_->UpdatePlacement(node, Scheduler::kScheduled);
   }
 
+  Node* CloneNode(Node* node) {
+    int const input_count = node->InputCount();
+    Node** const inputs = scheduler_->zone_->NewArray<Node*>(input_count);
+    for (int index = 0; index < input_count; ++index) {
+      Node* const input = node->InputAt(index);
+      scheduler_->IncrementUnscheduledUseCount(input, index, node);
+      inputs[index] = input;
+    }
+    Node* copy = scheduler_->graph_->NewNode(node->op(), input_count, inputs);
+    scheduler_->node_data_.resize(copy->id() + 1,
+                                  scheduler_->DefaultSchedulerData());
+    scheduler_->node_data_[copy->id()] = scheduler_->node_data_[node->id()];
+    return copy;
+  }
+
   Scheduler* scheduler_;
   Schedule* schedule_;
+  BoolVector visited_;
+  BasicBlockVector stack_;
 };