[turbofan] Add TraversalState and GraphTraversal and use them in GraphReducer.

src/compiler/graph-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/graph-reducer.h"
 
 #include <functional>
 
 #include "src/compiler/graph-inl.h"
 
 namespace v8 {
 namespace internal {
 namespace compiler {
 
 enum class GraphReducer::State : uint8_t {
   kUnvisited,
   kRevisit,
   kOnStack,
   kVisited
 };
 
 
 GraphReducer::GraphReducer(Graph* graph, Zone* zone)
     : graph_(graph),
+      state_(graph, 4),
       reducers_(zone),
       revisit_(zone),
-      stack_(zone),
-      state_(zone) {}
+      stack_(zone) {}
 
 
 void GraphReducer::AddReducer(Reducer* reducer) {
   reducers_.push_back(reducer);
 }
 
 
 void GraphReducer::ReduceNode(Node* node) {
   DCHECK(stack_.empty());
   DCHECK(revisit_.empty());
-  std::fill(state_.begin(), state_.end(), State::kUnvisited);
   Push(node);
   for (;;) {
-    DCHECK(!stack_.empty() ||
-           std::find(state_.begin(), state_.end(), State::kOnStack) ==
-               state_.end());
     if (!stack_.empty()) {
       // Process the node on the top of the stack, potentially pushing more or
       // popping the node off the stack.
       ReduceTop();
     } else if (!revisit_.empty()) {
       // If the stack becomes empty, revisit any nodes in the revisit queue.
       Node* const node = revisit_.top();
       revisit_.pop();
-      if (state_[node->id()] == State::kRevisit) {
+      if (state_.Get(node) == State::kRevisit) {
         // state can change while in queue.
         Push(node);
       }
     } else {
       break;
     }
   }
-  DCHECK(std::find(state_.begin(), state_.end(), State::kOnStack) ==
-         state_.end());
   DCHECK(revisit_.empty());
   DCHECK(stack_.empty());
 }
 
 
 void GraphReducer::ReduceGraph() { ReduceNode(graph()->end()); }
 
 
 Reduction GraphReducer::Reduce(Node* const node) {
   auto skip = reducers_.end();
@@ skipping 21 matching lines @@
     return Reducer::NoChange();
   }
   // At least one reducer did some in-place reduction.
   return Reducer::Changed(node);
 }
 
 
 void GraphReducer::ReduceTop() {
   NodeState& entry = stack_.top();
   Node* node = entry.node;
-  DCHECK(state_[node->id()] == State::kOnStack);
+  DCHECK(state_.Get(node) == State::kOnStack);
 
   if (node->IsDead()) return Pop();  // Node was killed while on stack.
 
   // Recurse on an input if necessary.
   int start = entry.input_index < node->InputCount() ? entry.input_index : 0;
   for (int i = start; i < node->InputCount(); i++) {
     Node* input = node->InputAt(i);
     entry.input_index = i + 1;
     if (input != node && Recurse(input)) return;
   }
@@ skipping 42 matching lines @@
 
         // If there was a replacement, reduce it after popping {node}.
         Recurse(replacement);
       }
     }
   }
 }
 
 
 void GraphReducer::Pop() {
-  Node* const node = stack_.top().node;
-  state_[node->id()] = State::kVisited;
+  Node* node = stack_.top().node;
+  state_.Set(node, State::kVisited);
   stack_.pop();
 }
 
 
 void GraphReducer::Push(Node* const node) {
-  size_t const id = static_cast<size_t>(node->id());
-  if (id >= state_.size()) state_.resize(id + 1);
-  DCHECK(id < state_.size());
-  DCHECK(state_[id] != State::kOnStack);
-  state_[id] = State::kOnStack;
+  DCHECK(state_.Get(node) != State::kOnStack);
+  state_.Set(node, State::kOnStack);
   stack_.push({node, 0});
 }
 
 
-bool GraphReducer::Recurse(Node* const node) {
-  size_t const id = static_cast<size_t>(node->id());
-  if (id < state_.size() && state_[id] > State::kRevisit) return false;
+bool GraphReducer::Recurse(Node* node) {
+  if (state_.Get(node) > State::kRevisit) return false;
   Push(node);
   return true;
 }
 
 
-void GraphReducer::Revisit(Node* const node) {
-  size_t const id = static_cast<size_t>(node->id());
-  if (id < state_.size() && state_[id] == State::kVisited) {
-    state_[id] = State::kRevisit;
+void GraphReducer::Revisit(Node* node) {
+  if (state_.Get(node) == State::kVisited) {
+    state_.Set(node, State::kRevisit);
     revisit_.push(node);
   }
 }
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8