Reland "[turbofan] Fix control reducer bug with NTLs."

src/compiler/control-reducer.cc

 // Copyright 2014 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "src/compiler/common-operator.h"
 #include "src/compiler/control-reducer.h"
 #include "src/compiler/graph.h"
 #include "src/compiler/js-graph.h"
 #include "src/compiler/node-matchers.h"
 #include "src/compiler/node-properties-inl.h"
@@ skipping 89 matching lines @@
     AddNodesReachableFromEnd(marked, nodes);
 
     // Walk forward through control nodes, looking for back edges to nodes
     // that are not connected to end. Those are non-terminating loops (NTLs).
     Node* start = graph()->start();
     marked.Push(start);
     marked.SetReachableFromStart(start);
 
     // We use a stack of (Node, UseIter) pairs to avoid O(n^2) traversal.
     typedef std::pair<Node*, UseIter> FwIter;
-    ZoneDeque<FwIter> fw_stack(zone_);
+    ZoneVector<FwIter> fw_stack(zone_);
     fw_stack.push_back(FwIter(start, start->uses().begin()));
 
     while (!fw_stack.empty()) {
       Node* node = fw_stack.back().first;
       TRACE(("ControlFw: #%d:%s\n", node->id(), node->op()->mnemonic()));
       bool pop = true;
       while (fw_stack.back().second != node->uses().end()) {
         Node* succ = *(fw_stack.back().second);
         if (marked.IsOnStack(succ) && !marked.IsReachableFromEnd(succ)) {
           // {succ} is on stack and not reachable from end.
           Node* added = ConnectNTL(succ);
           nodes.push_back(added);
           marked.SetReachableFromEnd(added);
           AddBackwardsReachableNodes(marked, nodes, nodes.size() - 1);
 
-          // The use list of {succ} might have changed.
-          fw_stack[fw_stack.size() - 1] = FwIter(succ, succ->uses().begin());
+          // Reset the use iterators for the entire stack.
+          for (size_t i = 0; i < fw_stack.size(); i++) {
+            FwIter& iter = fw_stack[i];
+            fw_stack[i] = FwIter(iter.first, iter.first->uses().begin());
+          }
           pop = false;  // restart traversing successors of this node.
           break;
         }
         if (IrOpcode::IsControlOpcode(succ->opcode()) &&
             !marked.IsReachableFromStart(succ)) {
           // {succ} is a control node and not yet reached from start.
           marked.Push(succ);
           marked.SetReachableFromStart(succ);
           fw_stack.push_back(FwIter(succ, succ->uses().begin()));
           pop = false;  // "recurse" into successor control node.
@@ skipping 428 matching lines @@
 Node* ControlReducer::ReduceBranchForTesting(JSGraph* jsgraph,
                                              CommonOperatorBuilder* common,
                                              Node* node) {
   Zone zone(jsgraph->graph()->zone()->isolate());
   ControlReducerImpl impl(&zone, jsgraph, common);
   return impl.ReduceBranch(node);
 }
 }
 }
 }  // namespace v8::internal::compiler