[turbofan] Initial support for Switch.

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"
@@ skipping 200 matching lines @@
 // Phase 1: Build control-flow graph.
 
 
 // Internal class to build a control flow graph (i.e the basic blocks and edges
 // 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 ZoneObject {
  public:
   CFGBuilder(Zone* zone, Scheduler* scheduler)
-      : scheduler_(scheduler),
+      : zone_(zone),
+        scheduler_(scheduler),
         schedule_(scheduler->schedule_),
         queued_(scheduler->graph_, 2),
         queue_(zone),
         control_(zone),
         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
@@ skipping 77 matching lines @@
         FixNode(schedule_->end(), node);
         break;
       case IrOpcode::kStart:
         FixNode(schedule_->start(), node);
         break;
       case IrOpcode::kLoop:
       case IrOpcode::kMerge:
         BuildBlockForNode(node);
         break;
       case IrOpcode::kBranch:
-        BuildBlocksForSuccessors(node, IrOpcode::kIfTrue, IrOpcode::kIfFalse);
+      case IrOpcode::kSwitch:
+        BuildBlocksForSuccessors(node);
         break;
       default:
         break;
     }
   }
 
   void ConnectBlocks(Node* node) {
     switch (node->opcode()) {
       case IrOpcode::kLoop:
       case IrOpcode::kMerge:
         ConnectMerge(node);
         break;
       case IrOpcode::kBranch:
         scheduler_->UpdatePlacement(node, Scheduler::kFixed);
         ConnectBranch(node);
         break;
+      case IrOpcode::kSwitch:
+        scheduler_->UpdatePlacement(node, Scheduler::kFixed);
+        ConnectSwitch(node);
+        break;
       case IrOpcode::kReturn:
         scheduler_->UpdatePlacement(node, Scheduler::kFixed);
         ConnectReturn(node);
         break;
       case IrOpcode::kThrow:
         scheduler_->UpdatePlacement(node, Scheduler::kFixed);
         ConnectThrow(node);
         break;
       default:
         break;
     }
   }
 
   BasicBlock* BuildBlockForNode(Node* node) {
     BasicBlock* block = schedule_->block(node);
     if (block == NULL) {
       block = schedule_->NewBasicBlock();
       Trace("Create block B%d for #%d:%s\n", block->id().ToInt(), node->id(),
             node->op()->mnemonic());
       FixNode(block, node);
     }
     return block;
   }
 
-  void BuildBlocksForSuccessors(Node* node, IrOpcode::Value a,
-                                IrOpcode::Value b) {
-    Node* successors[2];
-    CollectSuccessorProjections(node, successors, a, b);
-    BuildBlockForNode(successors[0]);
-    BuildBlockForNode(successors[1]);
+  void BuildBlocksForSuccessors(Node* node) {
+    size_t const successor_count = node->op()->ControlOutputCount();
+    Node** successors =
+        zone_->NewArray<Node*>(static_cast<int>(successor_count));
+    CollectSuccessorProjections(node, successors, successor_count);
+    for (size_t index = 0; index < successor_count; ++index) {
+      BuildBlockForNode(successors[index]);
+    }
   }
 
   // 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 (Node* use : node->uses()) {
-      if (use->opcode() == true_opcode) {
-        DCHECK(!buffer[0]);
-        buffer[0] = use;
+  // IfFalse, and Case.
+  void CollectSuccessorProjections(Node* node, Node** successors,
+                                   size_t successor_count) {
+#ifdef DEBUG
+    DCHECK_EQ(static_cast<int>(successor_count), node->UseCount());
+    std::memset(successors, 0, sizeof(*successors) * successor_count);
+#endif
+    for (Node* const use : node->uses()) {
+      size_t index;
+      switch (use->opcode()) {
+        default:
+          UNREACHABLE();
+        // Fall through.
+        case IrOpcode::kIfTrue:
+          DCHECK_EQ(IrOpcode::kBranch, node->opcode());
+          index = 0;
+          break;
+        case IrOpcode::kIfFalse:
+          DCHECK_EQ(IrOpcode::kBranch, node->opcode());
+          index = 1;
+          break;
+        case IrOpcode::kCase:
+          DCHECK_EQ(IrOpcode::kSwitch, node->opcode());
+          index = CaseIndexOf(use->op());
+          break;
       }
-      if (use->opcode() == false_opcode) {
-        DCHECK(!buffer[1]);
-        buffer[1] = use;
-      }
+      DCHECK_LT(index, successor_count);
+      DCHECK(successors[index] == nullptr);
+      successors[index] = use;
     }
-    DCHECK(buffer[0]);
-    DCHECK(buffer[1]);
+#ifdef DEBUG
+    for (size_t index = 0; index < successor_count; ++index) {
+      DCHECK_NOT_NULL(successors[index]);
+    }
+#endif
   }
 
-  void CollectSuccessorBlocks(Node* node, BasicBlock** buffer,
-                              IrOpcode::Value true_opcode,
-                              IrOpcode::Value false_opcode) {
-    Node* successors[2];
-    CollectSuccessorProjections(node, successors, true_opcode, false_opcode);
-    buffer[0] = schedule_->block(successors[0]);
-    buffer[1] = schedule_->block(successors[1]);
+  void CollectSuccessorBlocks(Node* node, BasicBlock** successor_blocks,
+                              size_t successor_count) {
+    Node** successors = reinterpret_cast<Node**>(successor_blocks);
+    CollectSuccessorProjections(node, successors, successor_count);
+    for (size_t index = 0; index < successor_count; ++index) {
+      successor_blocks[index] = schedule_->block(successors[index]);
+    }
   }
 
   void ConnectBranch(Node* branch) {
     BasicBlock* successor_blocks[2];
-    CollectSuccessorBlocks(branch, successor_blocks, IrOpcode::kIfTrue,
-                           IrOpcode::kIfFalse);
+    CollectSuccessorBlocks(branch, successor_blocks,
+                           arraysize(successor_blocks));
 
     // Consider branch hints.
     switch (BranchHintOf(branch->op())) {
       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_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);
+      DCHECK_NOT_NULL(branch_block);
 
       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 ConnectSwitch(Node* sw) {
+    size_t const successor_count = sw->op()->ControlOutputCount();
+    BasicBlock** successor_blocks =
+        zone_->NewArray<BasicBlock*>(static_cast<int>(successor_count));
+    CollectSuccessorBlocks(sw, successor_blocks, successor_count);
+
+    if (sw == component_entry_) {
+      for (size_t index = 0; index < successor_count; ++index) {
+        TraceConnect(sw, component_start_, successor_blocks[index]);
+      }
+      schedule_->InsertSwitch(component_start_, component_end_, sw,
+                              successor_blocks, successor_count);
+    } else {
+      Node* sw_block_node = NodeProperties::GetControlInput(sw);
+      BasicBlock* sw_block = schedule_->block(sw_block_node);
+      DCHECK_NOT_NULL(sw_block);
+
+      for (size_t index = 0; index < successor_count; ++index) {
+        TraceConnect(sw, sw_block, successor_blocks[index]);
+      }
+      schedule_->AddSwitch(sw_block, sw, successor_blocks, successor_count);
+    }
+  }
+
   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);
+    DCHECK_NOT_NULL(block);
     // For all of the merge's control inputs, add a goto at the end to the
     // merge's basic block.
     for (Node* const 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 ConnectThrow(Node* thr) {
     Node* throw_block_node = NodeProperties::GetControlInput(thr);
     BasicBlock* throw_block = schedule_->block(throw_block_node);
     TraceConnect(thr, throw_block, NULL);
     schedule_->AddThrow(throw_block, thr);
   }
 
   void TraceConnect(Node* node, BasicBlock* block, BasicBlock* succ) {
-    DCHECK(block);
+    DCHECK_NOT_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;
   }
 
   void ResetDataStructures() {
     control_.clear();
     DCHECK(queue_.empty());
     DCHECK(control_.empty());
   }
 
+  Zone* zone_;
   Scheduler* scheduler_;
   Schedule* schedule_;
   NodeMarker<bool> queued_;      // Mark indicating whether node is queued.
   ZoneQueue<Node*> queue_;       // Queue used for breadth-first traversal.
   NodeVector control_;           // List of encountered control nodes.
   Node* component_entry_;        // Component single-entry node.
   BasicBlock* component_start_;  // Component single-entry block.
   BasicBlock* component_end_;    // Component single-exit block.
 };
 
@@ skipping 1100 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