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

src/compiler/graph.h

 // Copyright 2013 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_GRAPH_H_
 #define V8_COMPILER_GRAPH_H_
 
 #include <map>
 #include <set>
 
 #include "src/compiler/generic-algorithm.h"
 #include "src/compiler/node.h"
 #include "src/compiler/node-aux-data.h"
 #include "src/compiler/source-position.h"
 
 namespace v8 {
 namespace internal {
 namespace compiler {
 
 class GraphDecorator;
 
+template <typename LocalState>

[Michael Starzinger, 2014/11/28 11:27:27]

nit: Can we use s/LocalState/State/ here for readability?

+class GraphTraversal : public ZoneObject {

[Michael Starzinger, 2014/11/28 11:27:27]

As discussed offline: Since this is not really a "traversal" but just the "state
for a traversal", how about calling it NodeState? This would also warrant moving
it into the node.h file.

+ public:
+  LocalState GetState(Node* node) {
+    TraversalState state = node->traversal_state();
+    if (state < traversal_state_min_) {
+      state = traversal_state_min_;
+      node->set_traversal_state(traversal_state_min_);
+    }
+    DCHECK_LT(state, traversal_state_max_);
+    return static_cast<LocalState>(state - traversal_state_min_);
+  }
+
+  void SetState(Node* node, LocalState state) {
+    TraversalState local = static_cast<TraversalState>(state);
+    DCHECK(local >= 0 && local < (traversal_state_max_ - traversal_state_min_));
+    DCHECK_LT(node->traversal_state(), traversal_state_max_);
+    node->set_traversal_state(local + traversal_state_min_);
+  }
+
+ private:
+  GraphTraversal(TraversalState min, TraversalState max)
+      : traversal_state_min_(min), traversal_state_max_(max) {}
+
+  TraversalState traversal_state_min_;
+  TraversalState traversal_state_max_;
+
+  friend class Graph;
+};
 
 class Graph : public GenericGraph<Node> {
  public:
   explicit Graph(Zone* zone);
 
   // Base implementation used by all factory methods.
   Node* NewNode(const Operator* op, int input_count, Node** inputs,
                 bool incomplete = false);
 
   // Factories for nodes with static input counts.
@@ skipping 44 matching lines @@
     decorators_.push_back(decorator);
   }
 
   void RemoveDecorator(GraphDecorator* decorator) {
     ZoneVector<GraphDecorator*>::iterator it =
         std::find(decorators_.begin(), decorators_.end(), decorator);
     DCHECK(it != decorators_.end());
     decorators_.erase(it, it + 1);
   }
 
+  template <typename LocalState>

[Michael Starzinger, 2014/11/28 11:27:27]

nit: Can we use s/LocalState/State/ here for readability?

+  GraphTraversal<LocalState>* NewTraversal(Zone* local_zone,
+                                           uint32_t num_states) {
+    TraversalState min = traversal_state_max_;
+    TraversalState max = (traversal_state_max_ += num_states);
+    return new (local_zone) GraphTraversal<LocalState>(min, max);
+  }
+
  private:
+  TraversalState traversal_state_max_;
   ZoneVector<GraphDecorator*> decorators_;
 };
 
 
 class GraphDecorator : public ZoneObject {
  public:
   virtual ~GraphDecorator() {}
   virtual void Decorate(Node* node) = 0;
 };
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8
 
 #endif  // V8_COMPILER_GRAPH_H_