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

src/compiler/graph-reducer.cc

Index: src/compiler/graph-reducer.cc
diff --git a/src/compiler/graph-reducer.cc b/src/compiler/graph-reducer.cc
index 26163bf41613ddbaaf6d07eb7437af315b14ef9e..1f56b302edce5a180599b2b925b178034c11f98a 100644
--- a/src/compiler/graph-reducer.cc
+++ b/src/compiler/graph-reducer.cc
@@ -22,10 +22,10 @@ enum class GraphReducer::State : uint8_t {
 
 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) {
@@ -36,12 +36,8 @@ void GraphReducer::AddReducer(Reducer* 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.
@@ -50,7 +46,7 @@ void GraphReducer::ReduceNode(Node* node) {
       // 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);
       }
@@ -58,8 +54,6 @@ void GraphReducer::ReduceNode(Node* node) {
       break;
     }
   }
-  DCHECK(std::find(state_.begin(), state_.end(), State::kOnStack) ==
-         state_.end());
   DCHECK(revisit_.empty());
   DCHECK(stack_.empty());
 }
@@ -101,7 +95,7 @@ Reduction GraphReducer::Reduce(Node* const 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.
 
@@ -164,34 +158,29 @@ void GraphReducer::ReduceTop() {
 
 
 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);
   }
 }