Line data    Source code

       1             : // Copyright 2015 the V8 project authors. All rights reserved.
       2             : // Use of this source code is governed by a BSD-style license that can be
       3             : // found in the LICENSE file.
       4             : 
       5             : #include "src/compiler/control-flow-optimizer.h"
       6             : 
       7             : #include "src/compiler/common-operator.h"
       8             : #include "src/compiler/graph.h"
       9             : #include "src/compiler/node-matchers.h"
      10             : #include "src/compiler/node-properties.h"
      11             : 
      12             : namespace v8 {
      13             : namespace internal {
      14             : namespace compiler {
      15             : 
      16      456115 : ControlFlowOptimizer::ControlFlowOptimizer(Graph* graph,
      17             :                                            CommonOperatorBuilder* common,
      18             :                                            MachineOperatorBuilder* machine,
      19             :                                            Zone* zone)
      20             :     : graph_(graph),
      21             :       common_(common),
      22             :       machine_(machine),
      23             :       queue_(zone),
      24             :       queued_(graph, 2),
      25      912234 :       zone_(zone) {}
      26             : 
      27             : 
      28      456104 : void ControlFlowOptimizer::Optimize() {
      29      456104 :   Enqueue(graph()->start());
      30    18164753 :   while (!queue_.empty()) {
      31    34505235 :     Node* node = queue_.front();
      32             :     queue_.pop();
      33    17252727 :     if (node->IsDead()) continue;
      34    17252692 :     switch (node->opcode()) {
      35             :       case IrOpcode::kBranch:
      36     1800719 :         VisitBranch(node);
      37     1800603 :         break;
      38             :       default:
      39    15451973 :         VisitNode(node);
      40    15451925 :         break;
      41             :     }
      42             :   }
      43      456115 : }
      44             : 
      45             : 
      46    19282890 : void ControlFlowOptimizer::Enqueue(Node* node) {
      47             :   DCHECK_NOT_NULL(node);
      48    77131535 :   if (node->IsDead() || queued_.Get(node)) return;
      49             :   queued_.Set(node, true);
      50             :   queue_.push(node);
      51             : }
      52             : 
      53             : 
      54    17249941 : void ControlFlowOptimizer::VisitNode(Node* node) {
      55   123665961 :   for (Edge edge : node->use_edges()) {
      56    44583083 :     if (NodeProperties::IsControlEdge(edge)) {
      57    18813708 :       Enqueue(edge.from());
      58             :     }
      59             :   }
      60    17249854 : }
      61             : 
      62             : 
      63     1800711 : void ControlFlowOptimizer::VisitBranch(Node* node) {
      64             :   DCHECK_EQ(IrOpcode::kBranch, node->opcode());
      65     3601427 :   if (TryBuildSwitch(node)) return;
      66     1798061 :   VisitNode(node);
      67             : }
      68             : 
      69             : 
      70     1986069 : bool ControlFlowOptimizer::TryBuildSwitch(Node* node) {
      71             :   DCHECK_EQ(IrOpcode::kBranch, node->opcode());
      72             : 
      73     1800701 :   Node* branch = node;
      74     1800701 :   if (BranchHintOf(branch->op()) != BranchHint::kNone) return false;
      75      932943 :   Node* cond = NodeProperties::GetValueInput(branch, 0);
      76      932941 :   if (cond->opcode() != IrOpcode::kWord32Equal) return false;
      77      172208 :   Int32BinopMatcher m(cond);
      78             :   Node* index = m.left().node();
      79      172207 :   if (!m.right().HasValue()) return false;
      80      169625 :   int32_t value = m.right().Value();
      81             :   ZoneSet<int32_t> values(zone());
      82             :   values.insert(value);
      83             : 
      84             :   Node* if_false;
      85             :   Node* if_true;
      86             :   int32_t order = 1;
      87             :   while (true) {
      88      177399 :     BranchMatcher matcher(branch);
      89             :     DCHECK(matcher.Matched());
      90             : 
      91      177399 :     if_true = matcher.IfTrue();
      92      177399 :     if_false = matcher.IfFalse();
      93             : 
      94      177399 :     auto it = if_false->uses().begin();
      95      177399 :     if (it == if_false->uses().end()) break;
      96      354799 :     Node* branch1 = *it++;
      97      177400 :     if (branch1->opcode() != IrOpcode::kBranch) break;
      98       14872 :     if (BranchHintOf(branch1->op()) != BranchHint::kNone) break;
      99       12158 :     if (it != if_false->uses().end()) break;
     100       12002 :     Node* cond1 = branch1->InputAt(0);
     101       12002 :     if (cond1->opcode() != IrOpcode::kWord32Equal) break;
     102       11512 :     Int32BinopMatcher m1(cond1);
     103       11512 :     if (m1.left().node() != index) break;
     104       11435 :     if (!m1.right().HasValue()) break;
     105       11435 :     int32_t value1 = m1.right().Value();
     106       11435 :     if (values.find(value1) != values.end()) break;
     107             :     DCHECK_NE(value, value1);
     108             : 
     109        7775 :     if (branch != node) {
     110        5119 :       branch->NullAllInputs();
     111        5119 :       if_true->ReplaceInput(0, node);
     112             :     }
     113       15550 :     NodeProperties::ChangeOp(if_true, common()->IfValue(value, order++));
     114        7775 :     if_false->NullAllInputs();
     115        7775 :     Enqueue(if_true);
     116             : 
     117             :     branch = branch1;
     118        7775 :     value = value1;
     119             :     values.insert(value);
     120             :   }
     121             : 
     122             :   DCHECK_EQ(IrOpcode::kBranch, node->opcode());
     123             :   DCHECK_EQ(IrOpcode::kBranch, branch->opcode());
     124      169625 :   if (branch == node) {
     125             :     DCHECK_EQ(1u, values.size());
     126             :     return false;
     127             :   }
     128             :   DCHECK_LT(1u, values.size());
     129        2656 :   node->ReplaceInput(0, index);
     130        5312 :   NodeProperties::ChangeOp(node, common()->Switch(values.size() + 1));
     131        2656 :   if_true->ReplaceInput(0, node);
     132        5312 :   NodeProperties::ChangeOp(if_true, common()->IfValue(value, order++));
     133        2656 :   Enqueue(if_true);
     134        2656 :   if_false->ReplaceInput(0, node);
     135        2656 :   NodeProperties::ChangeOp(if_false, common()->IfDefault());
     136        2656 :   Enqueue(if_false);
     137        2656 :   branch->NullAllInputs();
     138        2656 :   return true;
     139             : }
     140             : 
     141             : }  // namespace compiler
     142             : }  // namespace internal
     143      183867 : }  // namespace v8