deps/v8/src/compiler/control-flow-optimizer.cc

   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/js-graph.h"
   8 #include "src/compiler/node-matchers.h"
   9 #include "src/compiler/node-properties.h"
  10
  11 namespace v8 {
  12 namespace internal {
  13 namespace compiler {
  14
  15 ControlFlowOptimizer::ControlFlowOptimizer(JSGraph* jsgraph, Zone* zone)
  16     : jsgraph_(jsgraph),
  17       queue_(zone),
  18       queued_(jsgraph->graph(), 2),
  19       zone_(zone) {}
  20
  21
  22 void ControlFlowOptimizer::Optimize() {
  23   Enqueue(graph()->start());
  24   while (!queue_.empty()) {
  25     Node* node = queue_.front();
  26     queue_.pop();
  27     if (node->IsDead()) continue;
  28     switch (node->opcode()) {
  29       case IrOpcode::kBranch:
  30         VisitBranch(node);
  31         break;
  32       default:
  33         VisitNode(node);
  34         break;
  35     }
  36   }
  37 }
  38
  39
  40 void ControlFlowOptimizer::Enqueue(Node* node) {
  41   DCHECK_NOT_NULL(node);
  42   if (node->IsDead() || queued_.Get(node)) return;
  43   queued_.Set(node, true);
  44   queue_.push(node);
  45 }
  46
  47
  48 void ControlFlowOptimizer::VisitNode(Node* node) {
  49   for (Node* use : node->uses()) {
  50     if (NodeProperties::IsControl(use)) Enqueue(use);
  51   }
  52 }
  53
  54
  55 void ControlFlowOptimizer::VisitBranch(Node* node) {
  56   DCHECK_EQ(IrOpcode::kBranch, node->opcode());
  57
  58   Node* branch = node;
  59   Node* cond = NodeProperties::GetValueInput(branch, 0);
  60   if (cond->opcode() != IrOpcode::kWord32Equal) return VisitNode(node);
  61   Int32BinopMatcher m(cond);
  62   Node* index = m.left().node();
  63   if (!m.right().HasValue()) return VisitNode(node);
  64   int32_t value = m.right().Value();
  65   ZoneSet<int32_t> values(zone());
  66   values.insert(value);
  67
  68   Node* if_false;
  69   Node* if_true;
  70   while (true) {
  71     Node* control_projections[2];
  72     NodeProperties::CollectControlProjections(branch, control_projections, 2);
  73     if_true = control_projections[0];
  74     if_false = control_projections[1];
  75     DCHECK_EQ(IrOpcode::kIfTrue, if_true->opcode());
  76     DCHECK_EQ(IrOpcode::kIfFalse, if_false->opcode());
  77
  78     auto it = if_false->uses().begin();
  79     if (it == if_false->uses().end()) break;
  80     Node* branch1 = *it++;
  81     if (branch1->opcode() != IrOpcode::kBranch) break;
  82     if (it != if_false->uses().end()) break;
  83     Node* cond1 = branch1->InputAt(0);
  84     if (cond1->opcode() != IrOpcode::kWord32Equal) break;
  85     Int32BinopMatcher m1(cond1);
  86     if (m1.left().node() != index) break;
  87     if (!m1.right().HasValue()) break;
  88     int32_t value1 = m1.right().Value();
  89     if (values.find(value1) != values.end()) break;
  90     DCHECK_NE(value, value1);
  91
  92     if (branch != node) {
  93       branch->RemoveAllInputs();
  94       if_true->ReplaceInput(0, node);
  95     }
  96     if_true->set_op(common()->IfValue(value));
  97     if_false->RemoveAllInputs();
  98     Enqueue(if_true);
  99
 100     branch = branch1;
 101     value = value1;
 102     values.insert(value);
 103   }
 104
 105   DCHECK_EQ(IrOpcode::kBranch, node->opcode());
 106   DCHECK_EQ(IrOpcode::kBranch, branch->opcode());
 107   DCHECK_EQ(IrOpcode::kIfTrue, if_true->opcode());
 108   DCHECK_EQ(IrOpcode::kIfFalse, if_false->opcode());
 109   if (branch == node) {
 110     DCHECK_EQ(1u, values.size());
 111     Enqueue(if_true);
 112     Enqueue(if_false);
 113   } else {
 114     DCHECK_LT(1u, values.size());
 115     node->set_op(common()->Switch(values.size() + 1));
 116     node->ReplaceInput(0, index);
 117     if_true->set_op(common()->IfValue(value));
 118     if_true->ReplaceInput(0, node);
 119     Enqueue(if_true);
 120     if_false->set_op(common()->IfDefault());
 121     if_false->ReplaceInput(0, node);
 122     Enqueue(if_false);
 123     branch->RemoveAllInputs();
 124   }
 125 }
 126
 127
 128 CommonOperatorBuilder* ControlFlowOptimizer::common() const {
 129   return jsgraph()->common();
 130 }
 131
 132
 133 Graph* ControlFlowOptimizer::graph() const { return jsgraph()->graph(); }
 134
 135
 136 MachineOperatorBuilder* ControlFlowOptimizer::machine() const {
 137   return jsgraph()->machine();
 138 }
 139
 140 }  // namespace compiler
 141 }  // namespace internal
 142 }  // namespace v8