Fix O(n^2) successor traversal in ControlReducer.

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 62 matching lines @@
     // Gather all nodes backwards-reachable from end (through inputs).
     state_.assign(graph()->NodeCount(), kUnvisited);
     NodeVector nodes(zone_);
     AddNodesReachableFromEnd(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();
     ZoneVector<byte> fw_reachability(graph()->NodeCount(), 0, zone_);
     fw_reachability[start->id()] = kFromStart | kOnStack;
-    stack_.push_back(start);
 
-    while (!stack_.empty()) {
-      Node* node = stack_.back();
+    // 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_);
+    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;
-      for (Node* const succ : node->uses()) {
+      while (fw_stack.back().second != node->uses().end()) {
+        Node* succ = *(fw_stack.back().second);
         byte reach = fw_reachability[succ->id()];
         if ((reach & kOnStack) != 0 && state_[succ->id()] != kVisited) {
           // {succ} is on stack and not reachable from end.
           ConnectNTL(nodes, succ);
           fw_reachability.resize(graph()->NodeCount(), 0);
-          pop = false;  // continue traversing inputs to this node.
+          // The use list of {succ} might have changed.
+          fw_stack[fw_stack.size() - 1] = FwIter(succ, succ->uses().begin());
+          pop = false;  // restart traversing successors of this node.
           break;
         }
         if ((reach & kFromStart) == 0 &&
             IrOpcode::IsControlOpcode(succ->opcode())) {
           // {succ} is a control node and not yet reached from start.
           fw_reachability[succ->id()] |= kFromStart | kOnStack;
-          stack_.push_back(succ);
+          fw_stack.push_back(FwIter(succ, succ->uses().begin()));
           pop = false;  // "recurse" into successor control node.
           break;
         }
+        ++fw_stack.back().second;
       }
       if (pop) {
         fw_reachability[node->id()] &= ~kOnStack;
-        stack_.pop_back();
+        fw_stack.pop_back();
       }
     }
 
     // Trim references from dead nodes to live nodes first.
     jsgraph_->GetCachedNodes(&nodes);
     TrimNodes(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];
@@ skipping 437 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