[WIP] Node splitting in Scheduler.

src/compiler/scheduler.cc

 // Copyright 2013 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/scheduler.h"
 
 #include "src/bit-vector.h"
 #include "src/compiler/common-operator.h"
 #include "src/compiler/control-equivalence.h"
 #include "src/compiler/graph.h"
 #include "src/compiler/node.h"
 #include "src/compiler/node-marker.h"
 #include "src/compiler/node-properties.h"
 #include "src/zone-containers.h"
 
 namespace v8 {
 namespace internal {
 namespace compiler {
 
 static inline void Trace(const char* msg, ...) {
   if (FLAG_trace_turbo_scheduler) {
     va_list arguments;
     va_start(arguments, msg);
     base::OS::VPrint(msg, arguments);
     va_end(arguments);
   }
 }
 
 
-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();
   scheduler.GenerateImmediateDominatorTree();
 
   scheduler.PrepareUses();
   scheduler.ScheduleEarly();
   scheduler.ScheduleLate();
 
   scheduler.SealFinalSchedule();
@@ skipping 1165 matching lines @@
 }
 
 
 // -----------------------------------------------------------------------------
 // Phase 5: Schedule nodes late.
 
 
 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) {
     for (Node* const root : *roots) {
       ProcessQueue(root);
     }
   }
 
  private:
   void ProcessQueue(Node* root) {
     ZoneQueue<Node*>* queue = &(scheduler_->schedule_queue_);
     for (Node* node : root->inputs()) {
       // Don't schedule coupled nodes on their own.
       if (scheduler_->GetPlacement(node) == Scheduler::kCoupled) {
         node = NodeProperties::GetControlInput(node);
       }
 
       // Test schedulability condition by looking at unscheduled use count.
       if (scheduler_->GetData(node)->unscheduled_count_ != 0) continue;
 
       queue->push(node);
       while (!queue->empty()) {
-        VisitNode(queue->front());
+        Node* const node = queue->front();
         queue->pop();
+        VisitNode(node);
       }
     }
   }
 
   // Visits one node from the queue of schedulable nodes and determines its
   // schedule late position. Also hoists nodes out of loops to find a more
   // optimal scheduling position.
   void VisitNode(Node* node) {
     DCHECK_EQ(0, scheduler_->GetData(node)->unscheduled_count_);
 
@@ skipping 11 matching lines @@
     BasicBlock* min_block = scheduler_->GetData(node)->minimum_block_;
     DCHECK_EQ(min_block, BasicBlock::GetCommonDominator(block, min_block));
     Trace("Schedule late of #%d:%s is B%d at loop depth %d, minimum = B%d\n",
           node->id(), node->op()->mnemonic(), block->id().ToInt(),
           block->loop_depth(), min_block->id().ToInt());
 
     // Hoist nodes out of loops if possible. Nodes can be hoisted iteratively
     // 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.
     if (NodeProperties::IsControl(node)) {
       ScheduleFloatingControl(block, node);
     } else {
       ScheduleNode(block, node);
     }
   }
 
+  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();
     } else if (block->loop_header() != NULL) {
       return block->loop_header()->dominator();
     } else {
       return NULL;
     }
   }
 
   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
                                               ? block
                                               : BasicBlock::GetCommonDominator(
                                                     block, use_block);
     }
     return block;
   }
 
@@ skipping 30 matching lines @@
   void ScheduleFloatingControl(BasicBlock* block, Node* node) {
     scheduler_->FuseFloatingControl(block, node);
   }
 
   void ScheduleNode(BasicBlock* block, Node* node) {
     schedule_->PlanNode(block, node);
     scheduler_->scheduled_nodes_[block->id().ToSize()].push_back(node);
     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_;
 };
 
 
 void Scheduler::ScheduleLate() {
   Trace("--- SCHEDULE LATE ------------------------------------------\n");
   if (FLAG_trace_turbo_scheduler) {
     Trace("roots: ");
     for (Node* node : schedule_root_nodes_) {
       Trace("#%d:%s ", node->id(), node->op()->mnemonic());
     }
@@ skipping 90 matching lines @@
   for (Node* const node : *nodes) {
     schedule_->SetBlockForNode(to, node);
     scheduled_nodes_[to->id().ToSize()].push_back(node);
   }
   nodes->clear();
 }
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8