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      464165 : 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      928332 :       zone_(zone) {}
      26             : 
      27             : 
      28      464159 : void ControlFlowOptimizer::Optimize() {
      29      464159 :   Enqueue(graph()->start());
      30    19684997 :   while (!queue_.empty()) {
      31    19220828 :     Node* node = queue_.front();
      32             :     queue_.pop();
      33    19221076 :     if (node->IsDead()) continue;
      34    19221076 :     switch (node->opcode()) {
      35             :       case IrOpcode::kBranch:
      36     1868217 :         VisitBranch(node);
      37     1868215 :         break;
      38             :       default:
      39    17352859 :         VisitNode(node);
      40    17352781 :         break;
      41             :     }
      42             :   }
      43      464169 : }
      44             : 
      45             : 
      46    21355723 : void ControlFlowOptimizer::Enqueue(Node* node) {
      47             :   DCHECK_NOT_NULL(node);
      48    64067148 :   if (node->IsDead() || queued_.Get(node)) return;
      49             :   queued_.Set(node, true);
      50             :   queue_.push(node);
      51             : }
      52             : 
      53             : 
      54    19219072 : void ControlFlowOptimizer::VisitNode(Node* node) {
      55   123773151 :   for (Edge edge : node->use_edges()) {
      56    52277440 :     if (NodeProperties::IsControlEdge(edge)) {
      57    20878925 :       Enqueue(edge.from());
      58             :     }
      59             :   }
      60    19218271 : }
      61             : 
      62             : 
      63     1868219 : void ControlFlowOptimizer::VisitBranch(Node* node) {
      64             :   DCHECK_EQ(IrOpcode::kBranch, node->opcode());
      65     1868219 :   if (TryBuildSwitch(node)) return;
      66     1865642 :   VisitNode(node);
      67             : }
      68             : 
      69             : 
      70     1868219 : bool ControlFlowOptimizer::TryBuildSwitch(Node* node) {
      71             :   DCHECK_EQ(IrOpcode::kBranch, node->opcode());
      72             : 
      73             :   Node* branch = node;
      74     1868219 :   if (BranchHintOf(branch->op()) != BranchHint::kNone) return false;
      75      958339 :   Node* cond = NodeProperties::GetValueInput(branch, 0);
      76      958336 :   if (cond->opcode() != IrOpcode::kWord32Equal) return false;
      77      177669 :   Int32BinopMatcher m(cond);
      78             :   Node* index = m.left().node();
      79      177669 :   if (!m.right().HasValue()) return false;
      80      175091 :   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        7466 :   while (true) {
      88      182557 :     BranchMatcher matcher(branch);
      89             :     DCHECK(matcher.Matched());
      90             : 
      91             :     if_true = matcher.IfTrue();
      92             :     if_false = matcher.IfFalse();
      93             : 
      94      182557 :     auto it = if_false->uses().begin();
      95      182557 :     if (it == if_false->uses().end()) break;
      96      365114 :     Node* branch1 = *it++;
      97      182557 :     if (branch1->opcode() != IrOpcode::kBranch) break;
      98       11214 :     if (BranchHintOf(branch1->op()) != BranchHint::kNone) break;
      99        8587 :     if (it != if_false->uses().end()) break;
     100             :     Node* cond1 = branch1->InputAt(0);
     101        8445 :     if (cond1->opcode() != IrOpcode::kWord32Equal) break;
     102        7980 :     Int32BinopMatcher m1(cond1);
     103        7980 :     if (m1.left().node() != index) break;
     104        7896 :     if (!m1.right().HasValue()) break;
     105        7896 :     int32_t value1 = m1.right().Value();
     106        7896 :     if (values.find(value1) != values.end()) break;
     107             :     DCHECK_NE(value, value1);
     108             : 
     109        7466 :     if (branch != node) {
     110        4892 :       branch->NullAllInputs();
     111        4892 :       if_true->ReplaceInput(0, node);
     112             :     }
     113        7466 :     NodeProperties::ChangeOp(if_true, common()->IfValue(value, order++));
     114        7466 :     if_false->NullAllInputs();
     115        7466 :     Enqueue(if_true);
     116             : 
     117             :     branch = branch1;
     118        7466 :     value = value1;
     119             :     values.insert(value);
     120             :   }
     121             : 
     122             :   DCHECK_EQ(IrOpcode::kBranch, node->opcode());
     123             :   DCHECK_EQ(IrOpcode::kBranch, branch->opcode());
     124      175091 :   if (branch == node) {
     125             :     DCHECK_EQ(1u, values.size());
     126             :     return false;
     127             :   }
     128             :   DCHECK_LT(1u, values.size());
     129        2574 :   node->ReplaceInput(0, index);
     130        2574 :   NodeProperties::ChangeOp(node, common()->Switch(values.size() + 1));
     131        2574 :   if_true->ReplaceInput(0, node);
     132        2574 :   NodeProperties::ChangeOp(if_true, common()->IfValue(value, order++));
     133        2574 :   Enqueue(if_true);
     134        2574 :   if_false->ReplaceInput(0, node);
     135        2574 :   NodeProperties::ChangeOp(if_false, common()->IfDefault());
     136        2574 :   Enqueue(if_false);
     137        2574 :   branch->NullAllInputs();
     138        2574 :   return true;
     139             : }
     140             : 
     141             : }  // namespace compiler
     142             : }  // namespace internal
     143      122004 : }  // namespace v8