Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(34)

Side by Side Diff: src/compiler/control-reducer.cc

Issue 785233003: Revert "[turbofan] Fix control reducer bug with NTLs." (Closed) Base URL: https://chromium.googlesource.com/v8/v8.git@master
Patch Set: Created 6 years ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
« no previous file with comments | « no previous file | test/mjsunit/regress-ntl.js » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
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
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
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
OLDNEW
« no previous file with comments | « no previous file | test/mjsunit/regress-ntl.js » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698