Restrict floating control to minimal control-connected component.

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 <deque>
 #include <queue>
 
 #include "src/compiler/scheduler.h"
 
 #include "src/bit-vector.h"
+#include "src/compiler/control-equivalence.h"
 #include "src/compiler/graph.h"
 #include "src/compiler/graph-inl.h"
 #include "src/compiler/node.h"
 #include "src/compiler/node-properties.h"
 #include "src/compiler/node-properties-inl.h"
 
 namespace v8 {
 namespace internal {
 namespace compiler {
 
@@ skipping 30 matching lines @@
   scheduler.ScheduleEarly();
   scheduler.ScheduleLate();
 
   scheduler.SealFinalSchedule();
 
   return schedule;
 }
 
 
 Scheduler::SchedulerData Scheduler::DefaultSchedulerData() {
-  SchedulerData def = {schedule_->start(), 0, false, false, kUnknown};
+  SchedulerData def = {schedule_->start(), 0, false, kUnknown};
   return def;
 }
 
 
 Scheduler::SchedulerData* Scheduler::GetData(Node* node) {
   DCHECK(node->id() < static_cast<int>(node_data_.size()));
   return &node_data_[node->id()];
 }
 
 
 Scheduler::Placement Scheduler::GetPlacement(Node* node) {
   SchedulerData* data = GetData(node);
   if (data->placement_ == kUnknown) {  // Compute placement, once, on demand.
     switch (node->opcode()) {
       case IrOpcode::kParameter:
         // Parameters are always fixed to the start node.
         data->placement_ = kFixed;
         break;
       case IrOpcode::kPhi:
       case IrOpcode::kEffectPhi: {
         // Phis and effect phis are fixed if their control inputs are, whereas
         // otherwise they are coupled to a floating control node.
         Placement p = GetPlacement(NodeProperties::GetControlInput(node));
         data->placement_ = (p == kFixed ? kFixed : kCoupled);
         break;
       }
-#define DEFINE_FLOATING_CONTROL_CASE(V) case IrOpcode::k##V:
-      CONTROL_OP_LIST(DEFINE_FLOATING_CONTROL_CASE)
-#undef DEFINE_FLOATING_CONTROL_CASE
+#define DEFINE_CONTROL_CASE(V) case IrOpcode::k##V:
+      CONTROL_OP_LIST(DEFINE_CONTROL_CASE)
+#undef DEFINE_CONTROL_CASE
       {
         // Control nodes that were not control-reachable from end may float.
         data->placement_ = kSchedulable;
-        if (!data->is_connected_control_) {
-          data->is_floating_control_ = true;
-          Trace("Floating control found: #%d:%s\n", node->id(),
-                node->op()->mnemonic());
-        }
         break;
       }
       default:
         data->placement_ = kSchedulable;
         break;
     }
   }
   return data->placement_;
 }
 
 
 void Scheduler::UpdatePlacement(Node* node, Placement placement) {
   SchedulerData* data = GetData(node);
   if (data->placement_ != kUnknown) {  // Trap on mutation, not initialization.
     switch (node->opcode()) {
       case IrOpcode::kParameter:
         // Parameters are fixed once and for all.
         UNREACHABLE();
         break;
       case IrOpcode::kPhi:
       case IrOpcode::kEffectPhi: {
         // Phis and effect phis are coupled to their respective blocks.
         DCHECK_EQ(Scheduler::kCoupled, data->placement_);
         DCHECK_EQ(Scheduler::kFixed, placement);
         Node* control = NodeProperties::GetControlInput(node);
         BasicBlock* block = schedule_->block(control);
         schedule_->AddNode(block, node);
         break;
       }
-#define DEFINE_FLOATING_CONTROL_CASE(V) case IrOpcode::k##V:
-      CONTROL_OP_LIST(DEFINE_FLOATING_CONTROL_CASE)
-#undef DEFINE_FLOATING_CONTROL_CASE
+#define DEFINE_CONTROL_CASE(V) case IrOpcode::k##V:
+      CONTROL_OP_LIST(DEFINE_CONTROL_CASE)
+#undef DEFINE_CONTROL_CASE
       {
         // Control nodes force coupled uses to be placed.
         Node::Uses uses = node->uses();
         for (Node::Uses::iterator i = uses.begin(); i != uses.end(); ++i) {
           if (GetPlacement(*i) == Scheduler::kCoupled) {
             DCHECK_EQ(node, NodeProperties::GetControlInput(*i));
             UpdatePlacement(*i, placement);
           }
         }
         break;
@@ skipping 93 matching lines @@
 // between them within a Schedule) from the node graph. Visits control edges of
 // the graph backwards from an end node in order to find the connected control
 // subgraph, needed for scheduling.
 class CFGBuilder {
  public:
   CFGBuilder(Zone* zone, Scheduler* scheduler)
       : scheduler_(scheduler),
         schedule_(scheduler->schedule_),
         queue_(zone),
         control_(zone),
-        component_head_(NULL),
+        component_entry_(NULL),
         component_start_(NULL),
         component_end_(NULL) {}
 
   // Run the control flow graph construction algorithm by walking the graph
   // backwards from end through control edges, building and connecting the
   // basic blocks for control nodes.
   void Run() {
     Queue(scheduler_->graph_->end());
 
+    // TODO(mstarzinger): This is just for testing, remove again.
+    scheduler_->equivalence_->Run(scheduler_->graph_->end());
+
     while (!queue_.empty()) {  // Breadth-first backwards traversal.
       Node* node = queue_.front();
       queue_.pop();
       int max = NodeProperties::PastControlIndex(node);
       for (int i = NodeProperties::FirstControlIndex(node); i < max; i++) {
         Queue(node->InputAt(i));
       }
     }
 
     for (NodeVector::iterator i = control_.begin(); i != control_.end(); ++i) {
       ConnectBlocks(*i);  // Connect block to its predecessor/successors.
     }
   }
 
   // Run the control flow graph construction for a minimal control-connected
-  // component ending in {node} and merge that component into an existing
+  // component ending in {exit} and merge that component into an existing
   // control flow graph at the bottom of {block}.
-  void Run(BasicBlock* block, Node* node) {
-    Queue(node);
+  void Run(BasicBlock* block, Node* exit) {
+    Queue(exit);
 
     component_start_ = block;
-    component_end_ = schedule_->block(node);
+    component_end_ = schedule_->block(exit);
+    scheduler_->equivalence_->Run(exit);
     while (!queue_.empty()) {  // Breadth-first backwards traversal.
       Node* node = queue_.front();
       queue_.pop();
-      bool is_dom = true;
+
+      // Use control dependence equivalence to find a canonical single-entry
+      // single-exit region that makes up a minimal component to be scheduled.
+      if (IsSingleEntrySingleExitRegion(node, exit)) {
+        Trace("Found SESE at #%d:%s\n", node->id(), node->op()->mnemonic());
+        DCHECK_EQ(NULL, component_entry_);
+        component_entry_ = node;
+        continue;
+      }
+
       int max = NodeProperties::PastControlIndex(node);
       for (int i = NodeProperties::FirstControlIndex(node); i < max; i++) {
-        is_dom = is_dom &&
-            !scheduler_->GetData(node->InputAt(i))->is_floating_control_;
         Queue(node->InputAt(i));
       }
-      // TODO(mstarzinger): This is a hacky way to find component dominator.
-      if (is_dom) component_head_ = node;
     }
-    DCHECK_NOT_NULL(component_head_);
+    DCHECK_NE(NULL, component_entry_);
 
     for (NodeVector::iterator i = control_.begin(); i != control_.end(); ++i) {
-      scheduler_->GetData(*i)->is_floating_control_ = false;
       ConnectBlocks(*i);  // Connect block to its predecessor/successors.
     }
   }
 
  private:
   // TODO(mstarzinger): Only for Scheduler::FuseFloatingControl.
   friend class Scheduler;
 
   void FixNode(BasicBlock* block, Node* node) {
     schedule_->AddNode(block, node);
     scheduler_->UpdatePlacement(node, Scheduler::kFixed);
   }
 
   void Queue(Node* node) {
     // Mark the connected control nodes as they are queued.
     Scheduler::SchedulerData* data = scheduler_->GetData(node);
     if (!data->is_connected_control_) {
       data->is_connected_control_ = true;
       BuildBlocks(node);
       queue_.push(node);
       control_.push_back(node);
     }
   }
 
-
   void BuildBlocks(Node* node) {
     switch (node->opcode()) {
       case IrOpcode::kEnd:
         FixNode(schedule_->end(), node);
         break;
       case IrOpcode::kStart:
         FixNode(schedule_->start(), node);
         break;
       case IrOpcode::kLoop:
       case IrOpcode::kMerge:
@@ skipping 53 matching lines @@
   }
 
   // Collect the branch-related projections from a node, such as IfTrue,
   // IfFalse.
   // TODO(titzer): consider moving this to node.h
   void CollectSuccessorProjections(Node* node, Node** buffer,
                                    IrOpcode::Value true_opcode,
                                    IrOpcode::Value false_opcode) {
     buffer[0] = NULL;
     buffer[1] = NULL;
-    for (UseIter i = node->uses().begin(); i != node->uses().end(); ++i) {
-      if ((*i)->opcode() == true_opcode) {
+    for (Node* use : node->uses()) {
+      if (use->opcode() == true_opcode) {
         DCHECK_EQ(NULL, buffer[0]);
-        buffer[0] = *i;
+        buffer[0] = use;
       }
-      if ((*i)->opcode() == false_opcode) {
+      if (use->opcode() == false_opcode) {
         DCHECK_EQ(NULL, buffer[1]);
-        buffer[1] = *i;
+        buffer[1] = use;
       }
     }
     DCHECK_NE(NULL, buffer[0]);
     DCHECK_NE(NULL, buffer[1]);
   }
 
   void CollectSuccessorBlocks(Node* node, BasicBlock** buffer,
                               IrOpcode::Value true_opcode,
                               IrOpcode::Value false_opcode) {
     Node* successors[2];
@@ skipping 12 matching lines @@
       case BranchHint::kNone:
         break;
       case BranchHint::kTrue:
         successor_blocks[1]->set_deferred(true);
         break;
       case BranchHint::kFalse:
         successor_blocks[0]->set_deferred(true);
         break;
     }
 
-    if (branch == component_head_) {
+    if (branch == component_entry_) {
       TraceConnect(branch, component_start_, successor_blocks[0]);
       TraceConnect(branch, component_start_, successor_blocks[1]);
       schedule_->InsertBranch(component_start_, component_end_, branch,
                               successor_blocks[0], successor_blocks[1]);
     } else {
       Node* branch_block_node = NodeProperties::GetControlInput(branch);
       BasicBlock* branch_block = schedule_->block(branch_block_node);
       DCHECK(branch_block != NULL);
 
       TraceConnect(branch, branch_block, successor_blocks[0]);
       TraceConnect(branch, branch_block, successor_blocks[1]);
       schedule_->AddBranch(branch_block, branch, successor_blocks[0],
                            successor_blocks[1]);
     }
   }
 
   void ConnectMerge(Node* merge) {
     // Don't connect the special merge at the end to its predecessors.
     if (IsFinalMerge(merge)) return;
 
     BasicBlock* block = schedule_->block(merge);
     DCHECK(block != NULL);
     // For all of the merge's control inputs, add a goto at the end to the
     // merge's basic block.
-    for (InputIter j = merge->inputs().begin(); j != merge->inputs().end();
-         ++j) {
-      BasicBlock* predecessor_block = schedule_->block(*j);
+    for (Node* input : merge->inputs()) {
+      BasicBlock* predecessor_block = schedule_->block(input);
       TraceConnect(merge, predecessor_block, block);
       schedule_->AddGoto(predecessor_block, block);
     }
   }
 
   void ConnectReturn(Node* ret) {
     Node* return_block_node = NodeProperties::GetControlInput(ret);
     BasicBlock* return_block = schedule_->block(return_block_node);
     TraceConnect(ret, return_block, NULL);
     schedule_->AddReturn(return_block, ret);
   }
 
   void TraceConnect(Node* node, BasicBlock* block, BasicBlock* succ) {
     DCHECK_NE(NULL, block);
     if (succ == NULL) {
       Trace("Connect #%d:%s, B%d -> end\n", node->id(), node->op()->mnemonic(),
             block->id().ToInt());
     } else {
       Trace("Connect #%d:%s, B%d -> B%d\n", node->id(), node->op()->mnemonic(),
             block->id().ToInt(), succ->id().ToInt());
     }
   }
 
   bool IsFinalMerge(Node* node) {
     return (node->opcode() == IrOpcode::kMerge &&
             node == scheduler_->graph_->end()->InputAt(0));
   }
 
+  bool IsSingleEntrySingleExitRegion(Node* entry, Node* exit) const {
+    size_t entry_class = scheduler_->equivalence_->ClassOf(entry);
+    size_t exit_class = scheduler_->equivalence_->ClassOf(exit);
+    return entry != exit && entry_class == exit_class;
+  }
+
   Scheduler* scheduler_;
   Schedule* schedule_;
   ZoneQueue<Node*> queue_;
   NodeVector control_;
-  Node* component_head_;
+  Node* component_entry_;
   BasicBlock* component_start_;
   BasicBlock* component_end_;
 };
 
 
 void Scheduler::BuildCFG() {
   Trace("--- CREATING CFG -------------------------------------------\n");
 
+  // Instantiate a new control equivalence algorithm for the graph.
+  equivalence_ = new (zone_) ControlEquivalence(zone_, graph_);
+
   // Build a control-flow graph for the main control-connected component that
   // is being spanned by the graph's start and end nodes.
   CFGBuilder cfg_builder(zone_, this);
   cfg_builder.Run();
 
   // Initialize per-block data.
   scheduled_nodes_.resize(schedule_->BasicBlockCount(), NodeVector(zone_));
 }
 
 
@@ skipping 866 matching lines @@
       }
     }
     BasicBlock* result = schedule_->block(use);
     if (result == NULL) return NULL;
     Trace("  must dominate use #%d:%s in B%d\n", use->id(),
           use->op()->mnemonic(), result->id().ToInt());
     return result;
   }
 
   void ScheduleFloatingControl(BasicBlock* block, Node* node) {
-    DCHECK(scheduler_->GetData(node)->is_floating_control_);
     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);
   }
 
   Scheduler* scheduler_;
@@ skipping 106 matching lines @@
   for (NodeVectorIter i = nodes->begin(); i != nodes->end(); ++i) {
     schedule_->SetBlockForNode(to, *i);
     scheduled_nodes_[to->id().ToSize()].push_back(*i);
   }
   nodes->clear();
 }
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8