OLD | NEW |
1 // Copyright 2014 the V8 project authors. All rights reserved. | 1 // Copyright 2014 the V8 project authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #include "src/compiler/common-operator.h" | 5 #include "src/compiler/common-operator.h" |
6 #include "src/compiler/control-reducer.h" | 6 #include "src/compiler/control-reducer.h" |
7 #include "src/compiler/graph.h" | 7 #include "src/compiler/graph.h" |
8 #include "src/compiler/js-graph.h" | 8 #include "src/compiler/js-graph.h" |
9 #include "src/compiler/node-matchers.h" | 9 #include "src/compiler/node-matchers.h" |
10 #include "src/compiler/node-properties-inl.h" | 10 #include "src/compiler/node-properties-inl.h" |
(...skipping 89 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
100 AddNodesReachableFromEnd(marked, nodes); | 100 AddNodesReachableFromEnd(marked, nodes); |
101 | 101 |
102 // Walk forward through control nodes, looking for back edges to nodes | 102 // Walk forward through control nodes, looking for back edges to nodes |
103 // that are not connected to end. Those are non-terminating loops (NTLs). | 103 // that are not connected to end. Those are non-terminating loops (NTLs). |
104 Node* start = graph()->start(); | 104 Node* start = graph()->start(); |
105 marked.Push(start); | 105 marked.Push(start); |
106 marked.SetReachableFromStart(start); | 106 marked.SetReachableFromStart(start); |
107 | 107 |
108 // We use a stack of (Node, UseIter) pairs to avoid O(n^2) traversal. | 108 // We use a stack of (Node, UseIter) pairs to avoid O(n^2) traversal. |
109 typedef std::pair<Node*, UseIter> FwIter; | 109 typedef std::pair<Node*, UseIter> FwIter; |
110 ZoneVector<FwIter> fw_stack(zone_); | 110 ZoneDeque<FwIter> fw_stack(zone_); |
111 fw_stack.push_back(FwIter(start, start->uses().begin())); | 111 fw_stack.push_back(FwIter(start, start->uses().begin())); |
112 | 112 |
113 while (!fw_stack.empty()) { | 113 while (!fw_stack.empty()) { |
114 Node* node = fw_stack.back().first; | 114 Node* node = fw_stack.back().first; |
115 TRACE(("ControlFw: #%d:%s\n", node->id(), node->op()->mnemonic())); | 115 TRACE(("ControlFw: #%d:%s\n", node->id(), node->op()->mnemonic())); |
116 bool pop = true; | 116 bool pop = true; |
117 while (fw_stack.back().second != node->uses().end()) { | 117 while (fw_stack.back().second != node->uses().end()) { |
118 Node* succ = *(fw_stack.back().second); | 118 Node* succ = *(fw_stack.back().second); |
119 if (marked.IsOnStack(succ) && !marked.IsReachableFromEnd(succ)) { | 119 if (marked.IsOnStack(succ) && !marked.IsReachableFromEnd(succ)) { |
120 // {succ} is on stack and not reachable from end. | 120 // {succ} is on stack and not reachable from end. |
121 Node* added = ConnectNTL(succ); | 121 Node* added = ConnectNTL(succ); |
122 nodes.push_back(added); | 122 nodes.push_back(added); |
123 marked.SetReachableFromEnd(added); | 123 marked.SetReachableFromEnd(added); |
124 AddBackwardsReachableNodes(marked, nodes, nodes.size() - 1); | 124 AddBackwardsReachableNodes(marked, nodes, nodes.size() - 1); |
125 | 125 |
126 // Reset the use iterators for the entire stack. | 126 // The use list of {succ} might have changed. |
127 for (size_t i = 0; i < fw_stack.size(); i++) { | 127 fw_stack[fw_stack.size() - 1] = FwIter(succ, succ->uses().begin()); |
128 FwIter& iter = fw_stack[i]; | |
129 fw_stack[i] = FwIter(iter.first, iter.first->uses().begin()); | |
130 } | |
131 pop = false; // restart traversing successors of this node. | 128 pop = false; // restart traversing successors of this node. |
132 break; | 129 break; |
133 } | 130 } |
134 if (IrOpcode::IsControlOpcode(succ->opcode()) && | 131 if (IrOpcode::IsControlOpcode(succ->opcode()) && |
135 !marked.IsReachableFromStart(succ)) { | 132 !marked.IsReachableFromStart(succ)) { |
136 // {succ} is a control node and not yet reached from start. | 133 // {succ} is a control node and not yet reached from start. |
137 marked.Push(succ); | 134 marked.Push(succ); |
138 marked.SetReachableFromStart(succ); | 135 marked.SetReachableFromStart(succ); |
139 fw_stack.push_back(FwIter(succ, succ->uses().begin())); | 136 fw_stack.push_back(FwIter(succ, succ->uses().begin())); |
140 pop = false; // "recurse" into successor control node. | 137 pop = false; // "recurse" into successor control node. |
(...skipping 428 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
569 Node* ControlReducer::ReduceBranchForTesting(JSGraph* jsgraph, | 566 Node* ControlReducer::ReduceBranchForTesting(JSGraph* jsgraph, |
570 CommonOperatorBuilder* common, | 567 CommonOperatorBuilder* common, |
571 Node* node) { | 568 Node* node) { |
572 Zone zone(jsgraph->graph()->zone()->isolate()); | 569 Zone zone(jsgraph->graph()->zone()->isolate()); |
573 ControlReducerImpl impl(&zone, jsgraph, common); | 570 ControlReducerImpl impl(&zone, jsgraph, common); |
574 return impl.ReduceBranch(node); | 571 return impl.ReduceBranch(node); |
575 } | 572 } |
576 } | 573 } |
577 } | 574 } |
578 } // namespace v8::internal::compiler | 575 } // namespace v8::internal::compiler |
OLD | NEW |