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      463893 : 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      927794 :       zone_(zone) {}
      26             : 
      27             : 
      28      463895 : void ControlFlowOptimizer::Optimize() {
      29      463895 :   Enqueue(graph()->start());
      30    19677238 :   while (!queue_.empty()) {
      31    19213338 :     Node* node = queue_.front();
      32             :     queue_.pop();
      33    19213494 :     if (node->IsDead()) continue;
      34    19213494 :     switch (node->opcode()) {
      35             :       case IrOpcode::kBranch:
      36     1869801 :         VisitBranch(node);
      37     1869794 :         break;
      38             :       default:
      39    17343693 :         VisitNode(node);
      40    17343634 :         break;
      41             :     }
      42             :   }
      43      463900 : }
      44             : 
      45             : 
      46    21345797 : void ControlFlowOptimizer::Enqueue(Node* node) {
      47             :   DCHECK_NOT_NULL(node);
      48    64037333 :   if (node->IsDead() || queued_.Get(node)) return;
      49             :   queued_.Set(node, true);
      50             :   queue_.push(node);
      51             : }
      52             : 
      53             : 
      54    19211234 : void ControlFlowOptimizer::VisitNode(Node* node) {
      55   123704736 :   for (Edge edge : node->use_edges()) {
      56    52246986 :     if (NodeProperties::IsControlEdge(edge)) {
      57    20869403 :       Enqueue(edge.from());
      58             :     }
      59             :   }
      60    19210764 : }
      61             : 
      62             : 
      63     1869797 : void ControlFlowOptimizer::VisitBranch(Node* node) {
      64             :   DCHECK_EQ(IrOpcode::kBranch, node->opcode());
      65     1869797 :   if (TryBuildSwitch(node)) return;
      66     1867253 :   VisitNode(node);
      67             : }
      68             : 
      69             : 
      70     1869799 : bool ControlFlowOptimizer::TryBuildSwitch(Node* node) {
      71             :   DCHECK_EQ(IrOpcode::kBranch, node->opcode());
      72             : 
      73             :   Node* branch = node;
      74     1869799 :   if (BranchHintOf(branch->op()) != BranchHint::kNone) return false;
      75      961591 :   Node* cond = NodeProperties::GetValueInput(branch, 0);
      76      961587 :   if (cond->opcode() != IrOpcode::kWord32Equal) return false;
      77      181103 :   Int32BinopMatcher m(cond);
      78             :   Node* index = m.left().node();
      79      181103 :   if (!m.right().HasValue()) return false;
      80      178537 :   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        7369 :   while (true) {
      88      185906 :     BranchMatcher matcher(branch);
      89             :     DCHECK(matcher.Matched());
      90             : 
      91             :     if_true = matcher.IfTrue();
      92             :     if_false = matcher.IfFalse();
      93             : 
      94      185906 :     auto it = if_false->uses().begin();
      95      185906 :     if (it == if_false->uses().end()) break;
      96      371812 :     Node* branch1 = *it++;
      97      185906 :     if (branch1->opcode() != IrOpcode::kBranch) break;
      98       11073 :     if (BranchHintOf(branch1->op()) != BranchHint::kNone) break;
      99        8476 :     if (it != if_false->uses().end()) break;
     100             :     Node* cond1 = branch1->InputAt(0);
     101        8334 :     if (cond1->opcode() != IrOpcode::kWord32Equal) break;
     102        7873 :     Int32BinopMatcher m1(cond1);
     103        7873 :     if (m1.left().node() != index) break;
     104        7797 :     if (!m1.right().HasValue()) break;
     105        7797 :     int32_t value1 = m1.right().Value();
     106        7797 :     if (values.find(value1) != values.end()) break;
     107             :     DCHECK_NE(value, value1);
     108             : 
     109        7369 :     if (branch != node) {
     110        4826 :       branch->NullAllInputs();
     111        4826 :       if_true->ReplaceInput(0, node);
     112             :     }
     113        7369 :     NodeProperties::ChangeOp(if_true, common()->IfValue(value, order++));
     114        7369 :     if_false->NullAllInputs();
     115        7369 :     Enqueue(if_true);
     116             : 
     117             :     branch = branch1;
     118        7369 :     value = value1;
     119             :     values.insert(value);
     120             :   }
     121             : 
     122             :   DCHECK_EQ(IrOpcode::kBranch, node->opcode());
     123             :   DCHECK_EQ(IrOpcode::kBranch, branch->opcode());
     124      178537 :   if (branch == node) {
     125             :     DCHECK_EQ(1u, values.size());
     126             :     return false;
     127             :   }
     128             :   DCHECK_LT(1u, values.size());
     129        2543 :   node->ReplaceInput(0, index);
     130        2543 :   NodeProperties::ChangeOp(node, common()->Switch(values.size() + 1));
     131        2543 :   if_true->ReplaceInput(0, node);
     132        2543 :   NodeProperties::ChangeOp(if_true, common()->IfValue(value, order++));
     133        2543 :   Enqueue(if_true);
     134        2543 :   if_false->ReplaceInput(0, node);
     135        2543 :   NodeProperties::ChangeOp(if_false, common()->IfDefault());
     136        2543 :   Enqueue(if_false);
     137        2543 :   branch->NullAllInputs();
     138        2543 :   return true;
     139             : }
     140             : 
     141             : }  // namespace compiler
     142             : }  // namespace internal
     143      122036 : }  // namespace v8