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