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

src/compiler/node.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_NODE_H_
 #define V8_COMPILER_NODE_H_
 
 #include <deque>
 #include <set>
 #include <vector>
 
 #include "src/compiler/generic-algorithm.h"
 #include "src/compiler/generic-node.h"
 #include "src/compiler/opcodes.h"
 #include "src/compiler/operator.h"
 #include "src/types.h"
 #include "src/zone.h"
 #include "src/zone-allocator.h"
 
 namespace v8 {
 namespace internal {
 namespace compiler {
 
+// Marks are used during traversal of the graph to distinguish states of nodes.
+// Each node has a mark which is a monotonically increasing integer, and a
+// {NodeMarker} has a range of values that indicate states of a node.
+typedef uint32_t Mark;
+
 class NodeData {
  public:
   const Operator* op() const { return op_; }
   void set_op(const Operator* op) { op_ = op; }
 
   IrOpcode::Value opcode() const {
     DCHECK(op_->opcode() <= IrOpcode::kLast);
     return static_cast<IrOpcode::Value>(op_->opcode());
   }
 
  protected:
   const Operator* op_;
   Bounds bounds_;
+  Mark mark_;
   explicit NodeData(Zone* zone) {}
 
   friend class NodeProperties;
+  template <typename State>
+  friend class NodeMarker;
+
   Bounds bounds() { return bounds_; }
   void set_bounds(Bounds b) { bounds_ = b; }
+
+  // Only NodeMarkers should manipulate the marks on nodes.
+  Mark mark() { return mark_; }
+  void set_mark(Mark mark) { mark_ = mark; }
 };
 
 // A Node is the basic primitive of an IR graph. In addition to the members
 // inherited from Vector, Nodes only contain a mutable Operator that may change
 // during compilation, e.g. during lowering passes.  Other information that
 // needs to be associated with Nodes during compilation must be stored
 // out-of-line indexed by the Node's id.
 class Node FINAL : public GenericNode<NodeData, Node> {
  public:
   Node(GenericGraphBase* graph, int input_count, int reserve_input_count)
       : GenericNode<NodeData, Node>(graph, input_count, reserve_input_count) {}
 
-  void Initialize(const Operator* op) { set_op(op); }
+  void Initialize(const Operator* op) {
+    set_op(op);
+    set_mark(0);
+  }
 
   bool IsDead() const { return InputCount() > 0 && InputAt(0) == NULL; }
   void Kill();
 
   void CollectProjections(ZoneVector<Node*>* projections);
   Node* FindProjection(size_t projection_index);
 };
 
 std::ostream& operator<<(std::ostream& os, const Node& n);
 
@@ skipping 21 matching lines @@
 template <typename T>
 static inline const T& OpParameter(const Node* node) {
   return OpParameter<T>(node->op());
 }
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8
 
 #endif  // V8_COMPILER_NODE_H_