| 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 |