[turbofan] Fix control reducer bug with walking non-control edges during ConnectNTL phase.

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-marker.h"
 #include "src/compiler/node-matchers.h"
@@ skipping 88 matching lines @@
     ReachabilityMarker marked(graph());
     NodeVector nodes(zone_);
     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, Node::Uses::const_iterator) pairs to avoid
+    // We use a stack of (Node, Node::UseEdges::iterator) pairs to avoid
     // O(n^2) traversal.
-    typedef std::pair<Node*, Node::Uses::const_iterator> FwIter;
+    typedef std::pair<Node*, Node::UseEdges::iterator> FwIter;
     ZoneVector<FwIter> fw_stack(zone_);
-    fw_stack.push_back(FwIter(start, start->uses().begin()));
+    fw_stack.push_back(FwIter(start, start->use_edges().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);
+      while (fw_stack.back().second != node->use_edges().end()) {
+        Edge edge = *(fw_stack.back().second);
+        if (NodeProperties::IsControlEdge(edge) &&
+            edge.from()->op()->ControlOutputCount() > 0) {
+          // Only walk control edges to control nodes.
+          Node* succ = edge.from();
 
-          // 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());
+          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);
+
+            // 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->use_edges().begin());
+            }
+            pop = false;  // restart traversing successors of this node.
+            break;
           }
-          pop = false;  // restart traversing successors of this node.
-          break;
-        }
-        if (succ->op()->ControlOutputCount() > 0 &&
-            !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.
-          break;
+          if (!marked.IsReachableFromStart(succ)) {
+            // {succ} is not yet reached from start.
+            marked.Push(succ);
+            marked.SetReachableFromStart(succ);
+            fw_stack.push_back(FwIter(succ, succ->use_edges().begin()));
+            pop = false;  // "recurse" into successor control node.
+            break;
+          }
         }
         ++fw_stack.back().second;
       }
       if (pop) {
         marked.Pop(node);
         fw_stack.pop_back();
       }
     }
 
     // Trim references from dead nodes to live nodes first.
     jsgraph_->GetCachedNodes(&nodes);
     TrimNodes(marked, nodes);
 
     // Any control nodes not reachable from start are dead, even loops.
     for (size_t i = 0; i < nodes.size(); i++) {
       Node* node = nodes[i];
       if (node->op()->ControlOutputCount() > 0 &&
           !marked.IsReachableFromStart(node)) {
         ReplaceNode(node, dead());  // uses will be added to revisit queue.
       }
     }
     return TryRevisit();  // try to push a node onto the stack.
   }
 
   // Connect {loop}, the header of a non-terminating loop, to the end node.
   Node* ConnectNTL(Node* loop) {
     TRACE("ConnectNTL: #%d:%s\n", loop->id(), loop->op()->mnemonic());
+    DCHECK_EQ(IrOpcode::kLoop, loop->opcode());
 
     Node* always = graph()->NewNode(common_->Always());
     // Mark the node as visited so that we can revisit later.
     MarkAsVisited(always);
 
     Node* branch = graph()->NewNode(common_->Branch(), always, loop);
     // Mark the node as visited so that we can revisit later.
     MarkAsVisited(branch);
 
     Node* if_true = graph()->NewNode(common_->IfTrue(), branch);
@@ skipping 321 matching lines @@
     int index = 0;
     int live_index = 0;
     for (Node* const input : node->inputs()) {
       if (input->opcode() != IrOpcode::kDead) {
         live++;
         live_index = index;
       }
       index++;
     }
 
-    TRACE("ReduceMerge: #%d:%s (%d live)\n", node->id(), node->op()->mnemonic(),
-          live);
+    TRACE("ReduceMerge: #%d:%s (%d of %d live)\n", node->id(),
+          node->op()->mnemonic(), live, index);
 
     if (live == 0) return dead();  // no remaining inputs.
 
     // Gather phis and effect phis to be edited.
     ZoneVector<Node*> phis(zone_);
     for (Node* const use : node->uses()) {
       if (NodeProperties::IsPhi(use)) phis.push_back(use);
     }
 
     if (live == 1) {
@@ skipping 46 matching lines @@
     return node;
   }
 
   // Reduce branches if they have constant inputs.
   Node* ReduceIfTrue(Node* node) {
     Node* branch = node->InputAt(0);
     DCHECK_EQ(IrOpcode::kBranch, branch->opcode());
     Decision result = DecideCondition(branch->InputAt(0));
     if (result == kTrue) {
       // fold a true branch by replacing IfTrue with the branch control.
-      TRACE("BranchReduce: #%d:%s => #%d:%s\n", branch->id(),
+      TRACE("  BranchReduce: #%d:%s => #%d:%s\n", branch->id(),
             branch->op()->mnemonic(), node->id(), node->op()->mnemonic());
       return branch->InputAt(1);
     }
     return result == kUnknown ? node : dead();
   }
 
   // Reduce branches if they have constant inputs.
   Node* ReduceIfFalse(Node* node) {
     Node* branch = node->InputAt(0);
     DCHECK_EQ(IrOpcode::kBranch, branch->opcode());
     Decision result = DecideCondition(branch->InputAt(0));
     if (result == kFalse) {
       // fold a false branch by replacing IfFalse with the branch control.
-      TRACE("BranchReduce: #%d:%s => #%d:%s\n", branch->id(),
+      TRACE("  BranchReduce: #%d:%s => #%d:%s\n", branch->id(),
             branch->op()->mnemonic(), node->id(), node->op()->mnemonic());
       return branch->InputAt(1);
     }
     return result == kUnknown ? node : dead();
   }
 
   // Remove inputs to {node} corresponding to the dead inputs to {merge}
   // and compact the remaining inputs, updating the operator.
   void RemoveDeadInputs(Node* merge, Node* node) {
     int live = 0;
@@ skipping 73 matching lines @@
       return impl.ReduceIfTrue(node);
     case IrOpcode::kIfFalse:
       return impl.ReduceIfFalse(node);
     default:
       return node;
   }
 }
 }
 }
 }  // namespace v8::internal::compiler