Prevent redundant node revisit in ControlEquivalence.

src/compiler/control-equivalence.h

 // 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.
 
 #ifndef V8_COMPILER_CONTROL_EQUIVALENCE_H_
 #define V8_COMPILER_CONTROL_EQUIVALENCE_H_
 
 #include "src/v8.h"
 
 #include "src/compiler/graph.h"
@@ skipping 69 matching lines @@
     Node* parent_node;                 // Parent node of entry during DFS walk.
     Node* node;                        // Node that this stack entry belongs to.
   };
 
   // The stack is used during the undirected DFS walk.
   typedef ZoneStack<DFSStackEntry> DFSStack;
 
   struct NodeData {
     size_t class_number;  // Equivalence class number assigned to node.
     size_t dfs_number;    // Pre-order DFS number assigned to node.
+    bool visited;         // Indicates node has already been visited.
     bool on_stack;        // Indicates node is on DFS stack during walk.
     bool participates;    // Indicates node participates in DFS walk.
     BracketList blist;    // List of brackets per node.
   };
 
   // The per-node data computed during the DFS walk.
   typedef ZoneVector<NodeData> Data;
 
   // Called at pre-visit during DFS walk.
   void VisitPre(Node* node) {
     Trace("CEQ: Pre-visit of #%d:%s\n", node->id(), node->op()->mnemonic());
 
     // Dispense a new pre-order number.
     SetNumber(node, NewDFSNumber());
     Trace("  Assigned DFS number is %d\n", GetNumber(node));
   }
 
   // Called at mid-visit during DFS walk.
   void VisitMid(Node* node, DFSDirection direction) {
     Trace("CEQ: Mid-visit of #%d:%s\n", node->id(), node->op()->mnemonic());
     BracketList& blist = GetBracketList(node);
 
     // Remove brackets pointing to this node [line:19].
     BracketListDelete(blist, node, direction);
 
     // Potentially introduce artificial dependency from start to end.
     if (blist.empty()) {
-      DCHECK_EQ(graph_->start(), node);
       DCHECK_EQ(kInputDirection, direction);
-      VisitBackedge(graph_->start(), graph_->end(), kInputDirection);
+      VisitBackedge(node, graph_->end(), kInputDirection);
     }
 
     // Potentially start a new equivalence class [line:37].
     BracketListTrace(blist);
     Bracket* recent = &blist.back();
     if (recent->recent_size != blist.size()) {
       recent->recent_size = blist.size();
       recent->recent_class = NewClassNumber();
     }
 
@@ skipping 52 matching lines @@
 
       if (entry.direction == kInputDirection) {
         if (entry.input != node->input_edges().end()) {
           Edge edge = *entry.input;
           Node* input = edge.to();
           ++(entry.input);
           if (NodeProperties::IsControlEdge(edge) &&
               NodeProperties::IsControl(input)) {
             // Visit next control input.
             if (!GetData(input)->participates) continue;
+            if (GetData(input)->visited) continue;
             if (GetData(input)->on_stack) {
               // Found backedge if input is on stack.
               if (input != entry.parent_node) {
                 VisitBackedge(node, input, kInputDirection);
               }
             } else {
               // Push input onto stack.
               DFSPush(stack, input, node, kInputDirection);
               VisitPre(input);
             }
@@ skipping 10 matching lines @@
 
       if (entry.direction == kUseDirection) {
         if (entry.use != node->use_edges().end()) {
           Edge edge = *entry.use;
           Node* use = edge.from();
           ++(entry.use);
           if (NodeProperties::IsControlEdge(edge) &&
               NodeProperties::IsControl(use)) {
             // Visit next control use.
             if (!GetData(use)->participates) continue;
+            if (GetData(use)->visited) continue;
             if (GetData(use)->on_stack) {
               // Found backedge if use is on stack.
               if (use != entry.parent_node) {
                 VisitBackedge(node, use, kUseDirection);
               }
             } else {
               // Push use onto stack.
               DFSPush(stack, use, node, kUseDirection);
               VisitPre(use);
             }
@@ skipping 36 matching lines @@
     }
   }
 
  private:
   NodeData* GetData(Node* node) { return &node_data_[node->id()]; }
   int NewClassNumber() { return class_number_++; }
   int NewDFSNumber() { return dfs_number_++; }
 
   // Template used to initialize per-node data.
   NodeData EmptyData() {
-    return {kInvalidClass, 0, false, false, BracketList(zone_)};
+    return {kInvalidClass, 0, false, false, false, BracketList(zone_)};
   }
 
   // Accessors for the DFS number stored within the per-node data.
   size_t GetNumber(Node* node) { return GetData(node)->dfs_number; }
   void SetNumber(Node* node, size_t number) {
     GetData(node)->dfs_number = number;
   }
 
   // Accessors for the equivalence class stored within the per-node data.
   size_t GetClass(Node* node) { return GetData(node)->class_number; }
   void SetClass(Node* node, size_t number) {
     GetData(node)->class_number = number;
   }
 
   // Accessors for the bracket list stored within the per-node data.
   BracketList& GetBracketList(Node* node) { return GetData(node)->blist; }
   void SetBracketList(Node* node, BracketList& list) {
     GetData(node)->blist = list;
   }
 
   // Mutates the DFS stack by pushing an entry.
   void DFSPush(DFSStack& stack, Node* node, Node* from, DFSDirection dir) {
     DCHECK(GetData(node)->participates);
+    DCHECK(!GetData(node)->visited);
     GetData(node)->on_stack = true;
     Node::InputEdges::iterator input = node->input_edges().begin();
     Node::UseEdges::iterator use = node->use_edges().begin();
     stack.push({dir, input, use, from, node});
   }
 
   // Mutates the DFS stack by popping an entry.
   void DFSPop(DFSStack& stack, Node* node) {
     DCHECK_EQ(stack.top().node, node);
     GetData(node)->on_stack = false;
-    GetData(node)->participates = false;
+    GetData(node)->visited = true;
     stack.pop();
   }
 
   // TODO(mstarzinger): Optimize this to avoid linear search.
   void BracketListDelete(BracketList& blist, Node* to, DFSDirection direction) {
     for (BracketList::iterator i = blist.begin(); i != blist.end(); /*nop*/) {
       if (i->to == to && i->direction != direction) {
         Trace("  BList erased: {%d->%d}\n", i->from->id(), i->to->id());
         i = blist.erase(i);
       } else {
@@ skipping 26 matching lines @@
   int dfs_number_;    // Generates new DFS pre-order numbers on demand.
   int class_number_;  // Generates new equivalence class numbers on demand.
   Data node_data_;    // Per-node data stored as a side-table.
 };
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8
 
 #endif  // V8_COMPILER_CONTROL_EQUIVALENCE_H_