[turbofan] Connect loops to end via Terminate during graph building.

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/graph-reducer.h"
 #include "src/compiler/js-graph.h"
 #include "src/compiler/node-marker.h"
@@ skipping 15 matching lines @@
 
 class ReachabilityMarker : public NodeMarker<uint8_t> {
  public:
   explicit ReachabilityMarker(Graph* graph) : NodeMarker<uint8_t>(graph, 8) {}
   bool SetReachableFromEnd(Node* node) {
     uint8_t before = Get(node);
     Set(node, before | kFromEnd);
     return before & kFromEnd;
   }
   bool IsReachableFromEnd(Node* node) { return Get(node) & kFromEnd; }
-  bool SetReachableFromStart(Node* node) {
-    uint8_t before = Get(node);
-    Set(node, before | kFromStart);
-    return before & kFromStart;
-  }
-  bool IsReachableFromStart(Node* node) { return Get(node) & kFromStart; }
   void Push(Node* node) { Set(node, Get(node) | kFwStack); }
   void Pop(Node* node) { Set(node, Get(node) & ~kFwStack); }
   bool IsOnStack(Node* node) { return Get(node) & kFwStack; }
 
  private:
-  enum Bit { kFromEnd = 1, kFromStart = 2, kFwStack = 4 };
+  enum Bit { kFromEnd = 1, kFwStack = 2 };
 };
 
 
 class ControlReducerImpl final : public AdvancedReducer {
  public:
   Zone* zone_;
   JSGraph* jsgraph_;
   int max_phis_for_select_;
 
   ControlReducerImpl(Editor* editor, Zone* zone, JSGraph* jsgraph)
       : AdvancedReducer(editor),
         zone_(zone),
         jsgraph_(jsgraph),
         max_phis_for_select_(0) {}
 
   Graph* graph() { return jsgraph_->graph(); }
   CommonOperatorBuilder* common() { return jsgraph_->common(); }
   Node* dead() { return jsgraph_->DeadControl(); }
 
-  // Finish reducing the graph by trimming nodes and/or connecting NTLs.
+  // Finish reducing the graph by trimming nodes.
   bool Finish() final {
-    bool done = true;
-    // Gather all nodes backwards-reachable from end (through inputs).
-    ReachabilityMarker marked(graph());
-    NodeVector nodes(zone_);
-    AddNodesReachableFromRoots(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::UseEdges::iterator) pairs to avoid
-    // O(n^2) traversal.
-    typedef std::pair<Node*, Node::UseEdges::iterator> FwIter;
-    ZoneVector<FwIter> fw_stack(zone_);
-    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->use_edges().end()) {
-        Edge edge = *(fw_stack.back().second);
-        Node* succ = edge.from();
-        if (NodeProperties::IsControlEdge(edge) &&
-            succ->op()->ControlOutputCount() > 0) {
-          // Only walk control edges to control nodes.
-          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;
-          }
-          if (!marked.IsReachableFromStart(succ)) {
-            // {succ} is not yet reached from start.
-            marked.SetReachableFromStart(succ);
-            if (succ->opcode() != IrOpcode::kOsrLoopEntry) {
-              // Skip OsrLoopEntry; forms a confusing irredducible loop.
-              marked.Push(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.
-    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) &&
-          node->opcode() != IrOpcode::kDead) {
-        TRACE("Dead: #%d:%s\n", node->id(), node->op()->mnemonic());
-        node->ReplaceUses(dead());
-        done = false;
-      }
-    }
-
-    return done;
-  }
-
-  // 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());
-
-    // Collect all loop effects.
-    NodeVector effects(zone_);
-    for (auto edge : loop->use_edges()) {
-      DCHECK_EQ(loop, edge.to());
-      DCHECK(NodeProperties::IsControlEdge(edge));
-      switch (edge.from()->opcode()) {
-        case IrOpcode::kPhi:
-          break;
-        case IrOpcode::kEffectPhi:
-          effects.push_back(edge.from());
-          break;
-        default:
-          break;
-      }
-    }
-
-    // Compute effects for the Return.
-    Node* effect = graph()->start();
-    int const effects_count = static_cast<int>(effects.size());
-    if (effects_count == 1) {
-      effect = effects[0];
-    } else if (effects_count > 1) {
-      effect = graph()->NewNode(common()->EffectSet(effects_count),
-                                effects_count, &effects.front());
-    }
-
-    // Add a terminate to connect the NTL to the end.
-    Node* terminate = graph()->NewNode(common()->Terminate(), effect, loop);
-
-    Node* end = graph()->end();
-    if (end->opcode() == IrOpcode::kDead) {
-      // End is actually the dead node. Make a new end.
-      end = graph()->NewNode(common()->End(1), terminate);
-      graph()->SetEnd(end);
-      return end;
-    }
-    // Append a new input to the end.
-    end->AppendInput(graph()->zone(), terminate);
-    end->set_op(common()->End(end->InputCount()));
-    return terminate;
+    // TODO(bmeurer): Move this to the GraphReducer.
+    Trim();
+    return true;
   }
 
   void AddNodesReachableFromRoots(ReachabilityMarker& marked,
                                   NodeVector& nodes) {
     jsgraph_->GetCachedNodes(&nodes);  // Consider cached nodes roots.
     Node* end = graph()->end();
     marked.SetReachableFromEnd(end);
     if (!end->IsDead()) nodes.push_back(end);  // Consider end to be a root.
     for (Node* node : nodes) marked.SetReachableFromEnd(node);
     AddBackwardsReachableNodes(marked, nodes, 0);
@@ skipping 154 matching lines @@
     if (result == kFalse) return fvalue;
     return node;
   }
 
   // Reduce redundant phis.
   Node* ReducePhi(Node* node) {
     int n = node->InputCount();
     if (n <= 1) return dead();            // No non-control inputs.
     if (n == 2) return node->InputAt(0);  // Only one non-control input.
 
-    // Never remove an effect phi from a (potentially non-terminating) loop.
-    // Otherwise, we might end up eliminating effect nodes, such as calls,
-    // before the loop.
-    if (node->opcode() == IrOpcode::kEffectPhi &&
-        NodeProperties::GetControlInput(node)->opcode() == IrOpcode::kLoop) {
-      return node;
-    }
-
     Node* replacement = NULL;
     auto const inputs = node->inputs();
     for (auto it = inputs.begin(); n > 1; --n, ++it) {
       Node* input = *it;
       if (input->opcode() == IrOpcode::kDead) continue;  // ignore dead inputs.
       if (input != node && input != replacement) {       // non-redundant input.
         if (replacement != NULL) return node;
         replacement = input;
       }
     }
@@ skipping 233 matching lines @@
     case IrOpcode::kIfFalse:
       return impl.ReduceIfProjection(node, kFalse);
     default:
       return node;
   }
 }
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8