[turbofan] Optimize certain chains of Branch into a Switch.

src/compiler/instruction-selector.cc

 // Copyright 2014 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/instruction-selector.h"
 
+#include <limits>
+
 #include "src/compiler/instruction-selector-impl.h"
 #include "src/compiler/node-matchers.h"
 #include "src/compiler/node-properties.h"
 #include "src/compiler/pipeline.h"
 
 namespace v8 {
 namespace internal {
 namespace compiler {
 
 InstructionSelector::InstructionSelector(Zone* zone, size_t node_count,
@@ skipping 495 matching lines @@
       CheckNoPhis(tbranch);
       CheckNoPhis(fbranch);
       if (tbranch == fbranch) return VisitGoto(tbranch);
       // Treat special Branch(Always, IfTrue, IfFalse) as Goto(IfTrue).
       Node* const condition = input->InputAt(0);
       if (condition->opcode() == IrOpcode::kAlways) return VisitGoto(tbranch);
       return VisitBranch(input, tbranch, fbranch);
     }
     case BasicBlock::kSwitch: {
       DCHECK_EQ(IrOpcode::kSwitch, input->opcode());
-      BasicBlock** const branches = &block->successors().front();
-      size_t const branch_count = block->SuccessorCount();
-      DCHECK_LE(2u, branch_count);
+      // Last successor must be Default.
+      BasicBlock* default_branch = block->successors().back();
+      DCHECK_EQ(IrOpcode::kIfDefault, default_branch->front()->opcode());
       // SSA deconstruction requires targets of branches not to have phis.
       // Edge split form guarantees this property, but is more strict.
-      for (size_t index = 0; index < branch_count; ++index) {
-        CheckNoPhis(branches[index]);
+      CheckNoPhis(default_branch);
+      // All other successors must be cases.
+      size_t case_count = block->SuccessorCount() - 1;
+      DCHECK_LE(1u, case_count);
+      BasicBlock** case_branches = &block->successors().front();
+      // Determine case values and their min/max.
+      int32_t* case_values = zone()->NewArray<int32_t>(case_count);
+      int32_t min_value = std::numeric_limits<int32_t>::max();
+      int32_t max_value = std::numeric_limits<int32_t>::min();
+      for (size_t index = 0; index < case_count; ++index) {
+        BasicBlock* branch = case_branches[index];
+        int32_t value = OpParameter<int32_t>(branch->front()->op());
+        case_values[index] = value;
+        if (min_value > value) min_value = value;
+        if (max_value < value) max_value = value;
+        // SSA deconstruction requires targets of branches not to have phis.
+        // Edge split form guarantees this property, but is more strict.
+        CheckNoPhis(branch);
       }
-      return VisitSwitch(input, branches, branch_count);
+      DCHECK_LE(min_value, max_value);
+      return VisitSwitch(input, default_branch, case_branches, case_values,
+                         case_count, min_value, max_value);
     }
     case BasicBlock::kReturn: {
       // If the result itself is a return, return its input.
       Node* value = (input != NULL && input->opcode() == IrOpcode::kReturn)
                         ? input->InputAt(0)
                         : input;
       return VisitReturn(value);
     }
     case BasicBlock::kThrow:
       DCHECK_EQ(IrOpcode::kThrow, input->opcode());
@@ skipping 13 matching lines @@
 MachineType InstructionSelector::GetMachineType(Node* node) {
   DCHECK_NOT_NULL(schedule()->block(node));  // should only use scheduled nodes.
   switch (node->opcode()) {
     case IrOpcode::kStart:
     case IrOpcode::kLoop:
     case IrOpcode::kEnd:
     case IrOpcode::kBranch:
     case IrOpcode::kIfTrue:
     case IrOpcode::kIfFalse:
     case IrOpcode::kSwitch:
-    case IrOpcode::kCase:
+    case IrOpcode::kIfValue:
+    case IrOpcode::kIfDefault:
     case IrOpcode::kEffectPhi:
     case IrOpcode::kEffectSet:
     case IrOpcode::kMerge:
       // No code needed for these graph artifacts.
       return kMachNone;
     case IrOpcode::kFinish:
       return kMachAnyTagged;
     case IrOpcode::kParameter:
       return linkage()->GetParameterType(OpParameter<int>(node));
     case IrOpcode::kOsrValue:
@@ skipping 119 matching lines @@
     }
   }
   switch (node->opcode()) {
     case IrOpcode::kStart:
     case IrOpcode::kLoop:
     case IrOpcode::kEnd:
     case IrOpcode::kBranch:
     case IrOpcode::kIfTrue:
     case IrOpcode::kIfFalse:
     case IrOpcode::kSwitch:
-    case IrOpcode::kCase:
+    case IrOpcode::kIfValue:
+    case IrOpcode::kIfDefault:
     case IrOpcode::kEffectPhi:
     case IrOpcode::kMerge:
       // No code needed for these graph artifacts.
       return;
     case IrOpcode::kFinish:
       return MarkAsReference(node), VisitFinish(node);
     case IrOpcode::kParameter: {
       MachineType type = linkage()->GetParameterType(OpParameter<int>(node));
       MarkAsRepresentation(type, node);
       return VisitParameter(node);
@@ skipping 336 matching lines @@
 }
 
 
 void InstructionSelector::VisitGoto(BasicBlock* target) {
   // jump to the next block.
   OperandGenerator g(this);
   Emit(kArchJmp, g.NoOutput(), g.Label(target))->MarkAsControl();
 }
 
 
-void InstructionSelector::VisitSwitch(Node* node, BasicBlock** branches,
-                                      size_t branch_count) {
-  OperandGenerator g(this);
-  Node* const value = node->InputAt(0);
-  size_t const input_count = branch_count + 1;
-  InstructionOperand* const inputs =
-      zone()->NewArray<InstructionOperand>(input_count);
-  inputs[0] = g.UseRegister(value);
-  for (size_t index = 0; index < branch_count; ++index) {
-    inputs[index + 1] = g.Label(branches[index]);
-  }
-  Emit(kArchSwitch, 0, nullptr, input_count, inputs, 0, nullptr)
-      ->MarkAsControl();
-}
-
-
 void InstructionSelector::VisitReturn(Node* value) {
   OperandGenerator g(this);
   if (value != NULL) {
     Emit(kArchRet, g.NoOutput(),
          g.UseLocation(value, linkage()->GetReturnLocation(),
                        linkage()->GetReturnType()));
   } else {
     Emit(kArchRet, g.NoOutput());
   }
 }
@@ skipping 125 matching lines @@
 MachineOperatorBuilder::Flags
 InstructionSelector::SupportedMachineOperatorFlags() {
   return MachineOperatorBuilder::Flag::kNoFlags;
 }
 
 #endif  // !V8_TURBOFAN_BACKEND
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8