[turbofan] NodeMarker 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"
 #include "src/zone-containers.h"
 
 namespace v8 {
 namespace internal {
 namespace compiler {
 
 enum VisitState { kUnvisited = 0, kOnStack = 1, kRevisit = 2, kVisited = 3 };
-enum Reachability { kFromStart = 8 };
 enum Decision { kFalse, kUnknown, kTrue };
 
+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 };
+};
+
+
 #define TRACE(x) \
   if (FLAG_trace_turbo_reduction) PrintF x
 
 class ControlReducerImpl {
  public:
   ControlReducerImpl(Zone* zone, JSGraph* jsgraph,
                      CommonOperatorBuilder* common)
       : zone_(zone),
         jsgraph_(jsgraph),
         common_(common),
@@ skipping 34 matching lines @@
     return false;
   }
 
   // Repair the graph after the possible creation of non-terminating or dead
   // loops. Removing dead loops can produce more opportunities for reduction.
   bool RepairAndRemoveLoops() {
     // TODO(turbofan): we can skip this if the graph has no loops, but
     // we have to be careful about proper loop detection during reduction.
 
     // Gather all nodes backwards-reachable from end (through inputs).
-    state_.assign(graph()->NodeCount(), kUnvisited);
+    ReachabilityMarker marked(graph());
     NodeVector nodes(zone_);
-    AddNodesReachableFromEnd(nodes);
+    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();
-    ZoneVector<byte> fw_reachability(graph()->NodeCount(), 0, zone_);
-    fw_reachability[start->id()] = kFromStart | kOnStack;
+    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_);
     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);
-        byte reach = fw_reachability[succ->id()];
-        if ((reach & kOnStack) != 0 && state_[succ->id()] != kVisited) {
+        if (marked.IsOnStack(succ) && !marked.IsReachableFromEnd(succ)) {
           // {succ} is on stack and not reachable from end.
-          ConnectNTL(nodes, succ);
-          fw_reachability.resize(graph()->NodeCount(), 0);
+          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());
           pop = false;  // restart traversing successors of this node.
           break;
         }
-        if ((reach & kFromStart) == 0 &&
-            IrOpcode::IsControlOpcode(succ->opcode())) {
+        if (IrOpcode::IsControlOpcode(succ->opcode()) &&
+            !marked.IsReachableFromStart(succ)) {
           // {succ} is a control node and not yet reached from start.
-          fw_reachability[succ->id()] |= kFromStart | kOnStack;
+          marked.Push(succ);
+          marked.SetReachableFromStart(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;
+        marked.Pop(node);
         fw_stack.pop_back();
       }
     }
 
     // Trim references from dead nodes to live nodes first.
     jsgraph_->GetCachedNodes(&nodes);
-    TrimNodes(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];
-      byte reach = fw_reachability[node->id()];
-      if ((reach & kFromStart) == 0 &&
-          IrOpcode::IsControlOpcode(node->opcode())) {
+      if (IrOpcode::IsControlOpcode(node->opcode()) &&
+          !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.
-  void ConnectNTL(NodeVector& nodes, Node* loop) {
+  Node* ConnectNTL(Node* loop) {
     TRACE(("ConnectNTL: #%d:%s\n", loop->id(), loop->op()->mnemonic()));
 
     if (loop->opcode() != IrOpcode::kTerminate) {
       // Insert a {Terminate} node if the loop has effects.
       ZoneDeque<Node*> effects(zone_);
       for (Node* const use : loop->uses()) {
         if (use->opcode() == IrOpcode::kEffectPhi) effects.push_back(use);
       }
       int count = static_cast<int>(effects.size());
       if (count > 0) {
@@ skipping 16 matching lines @@
     } else if (merge->opcode() != IrOpcode::kMerge) {
       // Introduce a final merge node for {end->InputAt(0)} and {loop}.
       merge = graph()->NewNode(common_->Merge(2), merge, loop);
       end->ReplaceInput(0, merge);
       to_add = merge;
     } else {
       // Append a new input to the final merge at the end.
       merge->AppendInput(graph()->zone(), loop);
       merge->set_op(common_->Merge(merge->InputCount()));
     }
-    nodes.push_back(to_add);
-    state_.resize(graph()->NodeCount(), kUnvisited);
-    state_[to_add->id()] = kVisited;
-    AddBackwardsReachableNodes(nodes, nodes.size() - 1);
+    return to_add;
   }
 
-  void AddNodesReachableFromEnd(NodeVector& nodes) {
+  void AddNodesReachableFromEnd(ReachabilityMarker& marked, NodeVector& nodes) {
     Node* end = graph()->end();
-    state_[end->id()] = kVisited;
+    marked.SetReachableFromEnd(end);
     if (!end->IsDead()) {
       nodes.push_back(end);
-      AddBackwardsReachableNodes(nodes, nodes.size() - 1);
+      AddBackwardsReachableNodes(marked, nodes, nodes.size() - 1);
     }
   }
 
-  void AddBackwardsReachableNodes(NodeVector& nodes, size_t cursor) {
+  void AddBackwardsReachableNodes(ReachabilityMarker& marked, NodeVector& nodes,
+                                  size_t cursor) {
     while (cursor < nodes.size()) {
       Node* node = nodes[cursor++];
       for (Node* const input : node->inputs()) {
-        if (state_[input->id()] != kVisited) {
-          state_[input->id()] = kVisited;
+        if (!marked.SetReachableFromEnd(input)) {
           nodes.push_back(input);
         }
       }
     }
   }
 
   void Trim() {
     // Gather all nodes backwards-reachable from end through inputs.
-    state_.assign(graph()->NodeCount(), kUnvisited);
+    ReachabilityMarker marked(graph());
     NodeVector nodes(zone_);
-    AddNodesReachableFromEnd(nodes);
+    AddNodesReachableFromEnd(marked, nodes);
 
     // Process cached nodes in the JSGraph too.
     jsgraph_->GetCachedNodes(&nodes);
-    TrimNodes(nodes);
+    TrimNodes(marked, nodes);
   }
 
-  void TrimNodes(NodeVector& nodes) {
+  void TrimNodes(ReachabilityMarker& marked, NodeVector& nodes) {
     // Remove dead->live edges.
     for (size_t j = 0; j < nodes.size(); j++) {
       Node* node = nodes[j];
       for (UseIter i = node->uses().begin(); i != node->uses().end();) {
-        size_t id = static_cast<size_t>((*i)->id());
-        if (state_[id] != kVisited) {
+        if (!marked.IsReachableFromEnd(*i)) {
           TRACE(("DeadLink: #%d:%s(%d) -> #%d:%s\n", (*i)->id(),
                  (*i)->op()->mnemonic(), i.index(), node->id(),
                  node->op()->mnemonic()));
           i.UpdateToAndIncrement(NULL);
         } else {
           ++i;
         }
       }
     }
 #if DEBUG
     // Verify that no inputs to live nodes are NULL.
     for (size_t j = 0; j < nodes.size(); j++) {
       Node* node = nodes[j];
       for (Node* const input : node->inputs()) {
         CHECK_NE(NULL, input);
       }
       for (Node* const use : node->uses()) {
-        size_t id = static_cast<size_t>(use->id());
-        CHECK_EQ(kVisited, state_[id]);
+        CHECK(marked.IsReachableFromEnd(use));
       }
     }
 #endif
   }
 
   // Reduce the node on the top of the stack.
   // If an input {i} is not yet visited or needs to be revisited, push {i} onto
   // the stack and return. Otherwise, all inputs are visited, so apply
   // reductions for {node} and pop it off the stack.
   void ReduceTop() {
@@ skipping 262 matching lines @@
   }
 
   Graph* graph() { return jsgraph_->graph(); }
 };
 
 
 void ControlReducer::ReduceGraph(Zone* zone, JSGraph* jsgraph,
                                  CommonOperatorBuilder* common) {
   ControlReducerImpl impl(zone, jsgraph, common);
   impl.Reduce();
-  impl.Trim();
 }
 
 
 void ControlReducer::TrimGraph(Zone* zone, JSGraph* jsgraph) {
   ControlReducerImpl impl(zone, jsgraph, NULL);
   impl.Trim();
 }
 
 
 Node* ControlReducer::ReducePhiForTesting(JSGraph* jsgraph,
@@ skipping 17 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