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