OLD | NEW |
(Empty) | |
| 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 // TODO(turbofan): use NodeProperties::CollectSuccessorProjections() here |
| 72 // once available. |
| 73 auto it = branch->uses().begin(); |
| 74 DCHECK(it != branch->uses().end()); |
| 75 if_true = *it++; |
| 76 DCHECK(it != branch->uses().end()); |
| 77 if_false = *it++; |
| 78 DCHECK(it == branch->uses().end()); |
| 79 if (if_true->opcode() != IrOpcode::kIfTrue) std::swap(if_true, if_false); |
| 80 DCHECK_EQ(IrOpcode::kIfTrue, if_true->opcode()); |
| 81 DCHECK_EQ(IrOpcode::kIfFalse, if_false->opcode()); |
| 82 |
| 83 it = if_false->uses().begin(); |
| 84 if (it == if_false->uses().end()) break; |
| 85 Node* branch1 = *it++; |
| 86 if (branch1->opcode() != IrOpcode::kBranch) break; |
| 87 if (it != if_false->uses().end()) break; |
| 88 Node* cond1 = branch1->InputAt(0); |
| 89 if (cond1->opcode() != IrOpcode::kWord32Equal) break; |
| 90 Int32BinopMatcher m1(cond1); |
| 91 if (m1.left().node() != index) break; |
| 92 if (!m1.right().HasValue()) break; |
| 93 int32_t value1 = m1.right().Value(); |
| 94 if (values.find(value1) != values.end()) break; |
| 95 DCHECK_NE(value, value1); |
| 96 |
| 97 if (branch != node) { |
| 98 branch->RemoveAllInputs(); |
| 99 if_true->ReplaceInput(0, node); |
| 100 } |
| 101 if_true->set_op(common()->IfValue(value)); |
| 102 if_false->RemoveAllInputs(); |
| 103 Enqueue(if_true); |
| 104 |
| 105 branch = branch1; |
| 106 value = value1; |
| 107 values.insert(value); |
| 108 } |
| 109 |
| 110 DCHECK_EQ(IrOpcode::kBranch, node->opcode()); |
| 111 DCHECK_EQ(IrOpcode::kBranch, branch->opcode()); |
| 112 DCHECK_EQ(IrOpcode::kIfTrue, if_true->opcode()); |
| 113 DCHECK_EQ(IrOpcode::kIfFalse, if_false->opcode()); |
| 114 if (branch == node) { |
| 115 DCHECK_EQ(1u, values.size()); |
| 116 Enqueue(if_true); |
| 117 Enqueue(if_false); |
| 118 } else { |
| 119 DCHECK_LT(1u, values.size()); |
| 120 node->set_op(common()->Switch(values.size() + 1)); |
| 121 node->ReplaceInput(0, index); |
| 122 if_true->set_op(common()->IfValue(value)); |
| 123 if_true->ReplaceInput(0, node); |
| 124 Enqueue(if_true); |
| 125 if_false->set_op(common()->IfDefault()); |
| 126 if_false->ReplaceInput(0, node); |
| 127 Enqueue(if_false); |
| 128 branch->RemoveAllInputs(); |
| 129 } |
| 130 } |
| 131 |
| 132 |
| 133 CommonOperatorBuilder* ControlFlowOptimizer::common() const { |
| 134 return jsgraph()->common(); |
| 135 } |
| 136 |
| 137 |
| 138 Graph* ControlFlowOptimizer::graph() const { return jsgraph()->graph(); } |
| 139 |
| 140 |
| 141 MachineOperatorBuilder* ControlFlowOptimizer::machine() const { |
| 142 return jsgraph()->machine(); |
| 143 } |
| 144 |
| 145 } // namespace compiler |
| 146 } // namespace internal |
| 147 } // namespace v8 |
OLD | NEW |