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      395302 : 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      790606 :       zone_(zone) {}
      26             : 
      27             : 
      28      395304 : void ControlFlowOptimizer::Optimize() {
      29      395304 :   Enqueue(graph()->start());
      30    18508858 :   while (!queue_.empty()) {
      31    35436577 :     Node* node = queue_.front();
      32             :     queue_.pop();
      33    17718393 :     if (node->IsDead()) continue;
      34    17718329 :     switch (node->opcode()) {
      35             :       case IrOpcode::kBranch:
      36     1970177 :         VisitBranch(node);
      37     1970073 :         break;
      38             :       default:
      39    15748152 :         VisitNode(node);
      40    15748107 :         break;
      41             :     }
      42             :   }
      43      395303 : }
      44             : 
      45             : 
      46    19984883 : void ControlFlowOptimizer::Enqueue(Node* node) {
      47             :   DCHECK_NOT_NULL(node);
      48    79939470 :   if (node->IsDead() || queued_.Get(node)) return;
      49             :   queued_.Set(node, true);
      50             :   queue_.push(node);
      51             : }
      52             : 
      53             : 
      54    17707560 : void ControlFlowOptimizer::VisitNode(Node* node) {
      55   107398422 :   for (Edge edge : node->use_edges()) {
      56    44845431 :     if (NodeProperties::IsControlEdge(edge)) {
      57    19544765 :       Enqueue(edge.from());
      58             :     }
      59             :   }
      60    17707560 : }
      61             : 
      62             : 
      63     1970176 : void ControlFlowOptimizer::VisitBranch(Node* node) {
      64             :   DCHECK_EQ(IrOpcode::kBranch, node->opcode());
      65     3940348 :   if (TryBuildSwitch(node)) return;
      66     1959556 :   VisitNode(node);
      67             : }
      68             : 
      69             : 
      70     2249600 : bool ControlFlowOptimizer::TryBuildSwitch(Node* node) {
      71             :   DCHECK_EQ(IrOpcode::kBranch, node->opcode());
      72             : 
      73     1970178 :   Node* branch = node;
      74     1970178 :   if (BranchHintOf(branch->op()) != BranchHint::kNone) return false;
      75     1164956 :   Node* cond = NodeProperties::GetValueInput(branch, 0);
      76     1164956 :   if (cond->opcode() != IrOpcode::kWord32Equal) return false;
      77      227898 :   Int32BinopMatcher m(cond);
      78             :   Node* index = m.left().node();
      79      227898 :   if (!m.right().HasValue()) return false;
      80      224089 :   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             :   while (true) {
      87      247580 :     BranchMatcher matcher(branch);
      88             :     DCHECK(matcher.Matched());
      89             : 
      90      247580 :     if_true = matcher.IfTrue();
      91      247580 :     if_false = matcher.IfFalse();
      92             : 
      93             :     auto it = if_false->uses().begin();
      94      247580 :     if (it == if_false->uses().end()) break;
      95      495160 :     Node* branch1 = *it++;
      96      247580 :     if (branch1->opcode() != IrOpcode::kBranch) break;
      97       25439 :     if (BranchHintOf(branch1->op()) != BranchHint::kNone) break;
      98       25164 :     if (it != if_false->uses().end()) break;
      99       24665 :     Node* cond1 = branch1->InputAt(0);
     100       24665 :     if (cond1->opcode() != IrOpcode::kWord32Equal) break;
     101       23590 :     Int32BinopMatcher m1(cond1);
     102       23590 :     if (m1.left().node() != index) break;
     103       23495 :     if (!m1.right().HasValue()) break;
     104       23493 :     int32_t value1 = m1.right().Value();
     105       23493 :     if (values.find(value1) != values.end()) break;
     106             :     DCHECK_NE(value, value1);
     107             : 
     108       23491 :     if (branch != node) {
     109       12877 :       branch->NullAllInputs();
     110       12877 :       if_true->ReplaceInput(0, node);
     111             :     }
     112       46982 :     NodeProperties::ChangeOp(if_true, common()->IfValue(value));
     113       23491 :     if_false->NullAllInputs();
     114       23491 :     Enqueue(if_true);
     115             : 
     116             :     branch = branch1;
     117       23491 :     value = value1;
     118             :     values.insert(value);
     119             :   }
     120             : 
     121             :   DCHECK_EQ(IrOpcode::kBranch, node->opcode());
     122             :   DCHECK_EQ(IrOpcode::kBranch, branch->opcode());
     123      224089 :   if (branch == node) {
     124             :     DCHECK_EQ(1u, values.size());
     125             :     return false;
     126             :   }
     127             :   DCHECK_LT(1u, values.size());
     128       10614 :   node->ReplaceInput(0, index);
     129       21228 :   NodeProperties::ChangeOp(node, common()->Switch(values.size() + 1));
     130       10614 :   if_true->ReplaceInput(0, node);
     131       21228 :   NodeProperties::ChangeOp(if_true, common()->IfValue(value));
     132       10614 :   Enqueue(if_true);
     133       10614 :   if_false->ReplaceInput(0, node);
     134       10614 :   NodeProperties::ChangeOp(if_false, common()->IfDefault());
     135       10614 :   Enqueue(if_false);
     136       10614 :   branch->NullAllInputs();
     137       10614 :   return true;
     138             : }
     139             : 
     140             : }  // namespace compiler
     141             : }  // namespace internal
     142             : }  // namespace v8