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-marker.h" | 9 #include "src/compiler/node-marker.h" |
10 #include "src/compiler/node-matchers.h" | 10 #include "src/compiler/node-matchers.h" |
(...skipping 88 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
99 ReachabilityMarker marked(graph()); | 99 ReachabilityMarker marked(graph()); |
100 NodeVector nodes(zone_); | 100 NodeVector nodes(zone_); |
101 AddNodesReachableFromEnd(marked, nodes); | 101 AddNodesReachableFromEnd(marked, nodes); |
102 | 102 |
103 // Walk forward through control nodes, looking for back edges to nodes | 103 // Walk forward through control nodes, looking for back edges to nodes |
104 // that are not connected to end. Those are non-terminating loops (NTLs). | 104 // that are not connected to end. Those are non-terminating loops (NTLs). |
105 Node* start = graph()->start(); | 105 Node* start = graph()->start(); |
106 marked.Push(start); | 106 marked.Push(start); |
107 marked.SetReachableFromStart(start); | 107 marked.SetReachableFromStart(start); |
108 | 108 |
109 // We use a stack of (Node, UseIter) pairs to avoid O(n^2) traversal. | 109 // We use a stack of (Node, Node::Uses::const_iterator) pairs to avoid |
110 typedef std::pair<Node*, UseIter> FwIter; | 110 // O(n^2) traversal. |
| 111 typedef std::pair<Node*, Node::Uses::const_iterator> FwIter; |
111 ZoneVector<FwIter> fw_stack(zone_); | 112 ZoneVector<FwIter> fw_stack(zone_); |
112 fw_stack.push_back(FwIter(start, start->uses().begin())); | 113 fw_stack.push_back(FwIter(start, start->uses().begin())); |
113 | 114 |
114 while (!fw_stack.empty()) { | 115 while (!fw_stack.empty()) { |
115 Node* node = fw_stack.back().first; | 116 Node* node = fw_stack.back().first; |
116 TRACE(("ControlFw: #%d:%s\n", node->id(), node->op()->mnemonic())); | 117 TRACE(("ControlFw: #%d:%s\n", node->id(), node->op()->mnemonic())); |
117 bool pop = true; | 118 bool pop = true; |
118 while (fw_stack.back().second != node->uses().end()) { | 119 while (fw_stack.back().second != node->uses().end()) { |
119 Node* succ = *(fw_stack.back().second); | 120 Node* succ = *(fw_stack.back().second); |
120 if (marked.IsOnStack(succ) && !marked.IsReachableFromEnd(succ)) { | 121 if (marked.IsOnStack(succ) && !marked.IsReachableFromEnd(succ)) { |
(...skipping 292 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
413 | 414 |
414 // Never remove an effect phi from a (potentially non-terminating) loop. | 415 // Never remove an effect phi from a (potentially non-terminating) loop. |
415 // Otherwise, we might end up eliminating effect nodes, such as calls, | 416 // Otherwise, we might end up eliminating effect nodes, such as calls, |
416 // before the loop. | 417 // before the loop. |
417 if (node->opcode() == IrOpcode::kEffectPhi && | 418 if (node->opcode() == IrOpcode::kEffectPhi && |
418 NodeProperties::GetControlInput(node)->opcode() == IrOpcode::kLoop) { | 419 NodeProperties::GetControlInput(node)->opcode() == IrOpcode::kLoop) { |
419 return node; | 420 return node; |
420 } | 421 } |
421 | 422 |
422 Node* replacement = NULL; | 423 Node* replacement = NULL; |
423 Node::Inputs inputs = node->inputs(); | 424 auto const inputs = node->inputs(); |
424 for (InputIter it = inputs.begin(); n > 1; --n, ++it) { | 425 for (auto it = inputs.begin(); n > 1; --n, ++it) { |
425 Node* input = *it; | 426 Node* input = *it; |
426 if (input->opcode() == IrOpcode::kDead) continue; // ignore dead inputs. | 427 if (input->opcode() == IrOpcode::kDead) continue; // ignore dead inputs. |
427 if (input != node && input != replacement) { // non-redundant input. | 428 if (input != node && input != replacement) { // non-redundant input. |
428 if (replacement != NULL) return node; | 429 if (replacement != NULL) return node; |
429 replacement = input; | 430 replacement = input; |
430 } | 431 } |
431 } | 432 } |
432 return replacement == NULL ? dead() : replacement; | 433 return replacement == NULL ? dead() : replacement; |
433 } | 434 } |
434 | 435 |
(...skipping 152 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
587 Node* ControlReducer::ReduceBranchForTesting(JSGraph* jsgraph, | 588 Node* ControlReducer::ReduceBranchForTesting(JSGraph* jsgraph, |
588 CommonOperatorBuilder* common, | 589 CommonOperatorBuilder* common, |
589 Node* node) { | 590 Node* node) { |
590 Zone zone(jsgraph->graph()->zone()->isolate()); | 591 Zone zone(jsgraph->graph()->zone()->isolate()); |
591 ControlReducerImpl impl(&zone, jsgraph, common); | 592 ControlReducerImpl impl(&zone, jsgraph, common); |
592 return impl.ReduceBranch(node); | 593 return impl.ReduceBranch(node); |
593 } | 594 } |
594 } | 595 } |
595 } | 596 } |
596 } // namespace v8::internal::compiler | 597 } // namespace v8::internal::compiler |
OLD | NEW |