[turbofan] Add support for advanced reducers.

src/compiler/graph-reducer.h

 // 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.
 
 #ifndef V8_COMPILER_GRAPH_REDUCER_H_
 #define V8_COMPILER_GRAPH_REDUCER_H_
 
 #include "src/compiler/node-marker.h"
 #include "src/zone-containers.h"
 
 namespace v8 {
 namespace internal {
 namespace compiler {
 
 // Forward declarations.
 class Graph;
 class Node;
 
 
+// NodeIds are identifying numbers for nodes that can be used to index auxiliary
+// out-of-line data associated with each node.
+typedef int32_t NodeId;
+
+
 // Represents the result of trying to reduce a node in the graph.
 class Reduction final {
  public:
-  explicit Reduction(Node* replacement = NULL) : replacement_(replacement) {}
+  explicit Reduction(Node* replacement = nullptr) : replacement_(replacement) {}
 
   Node* replacement() const { return replacement_; }
-  bool Changed() const { return replacement() != NULL; }
+  bool Changed() const { return replacement() != nullptr; }
 
  private:
   Node* replacement_;
 };
 
 
 // A reducer can reduce or simplify a given node based on its operator and
 // inputs. This class functions as an extension point for the graph reducer for
 // language-specific reductions (e.g. reduction based on types or constant
 // folding of low-level operators) can be integrated into the graph reduction
 // phase.
 class Reducer {
  public:
-  Reducer() {}
+  class Observer {

[titzer, 2015/05/06 08:57:40]

As discussed, if we could move this out of the base reducer and only have it in
the AdvancedReducer, then I'm (grumble) OK with this change.

[Benedikt Meurer, 2015/05/06 09:10:32]

Done as discussed. However I kept the Finish method in the Reducer to avoid
having the GraphReducer to distinguish Reducer and AdvancedReducer instances.
I'll work on readding Terminate and moving the trimming to GraphReducer, so we
can remove that Finish hack really soonish.

+   public:
+    Observer() {}
+    virtual ~Observer() {}
+
+    // Replace {node} with {replacement}.
+    virtual void Replace(Node* node, Node* replacement) = 0;
+    // Revisit the {node} again later.
+    virtual void Revisit(Node* node) = 0;
+
+   private:
+    DISALLOW_COPY_AND_ASSIGN(Observer);
+  };
+
+  Reducer() : observer_(nullptr) {}
   virtual ~Reducer() {}
 
+  // Observe the actions of this reducer.
+  Observer* observer() const { return observer_; }
+  void set_observer(Observer* observer) { observer_ = observer; }
+
   // Try to reduce a node if possible.
   virtual Reduction Reduce(Node* node) = 0;
 
+  // Ask this reducer to finish operation, returns {true} if the reducer is
+  // done, while {false} indicates that the graph might need to be reduced
+  // again.
+  virtual bool Finish();
+
   // Helper functions for subclasses to produce reductions for a node.
   static Reduction NoChange() { return Reduction(); }
   static Reduction Replace(Node* node) { return Reduction(node); }
   static Reduction Changed(Node* node) { return Reduction(node); }
 
+ protected:
+  void Replace(Node* node, Node* replacement) {
+    DCHECK_NOT_NULL(observer_);
+    observer_->Replace(node, replacement);
+  }
+  void Revisit(Node* node) {
+    DCHECK_NOT_NULL(observer_);
+    observer_->Revisit(node);
+  }
+
  private:
+  Observer* observer_;
+
   DISALLOW_COPY_AND_ASSIGN(Reducer);
 };
 
 
 // Performs an iterative reduction of a node graph.
-class GraphReducer final {
+class GraphReducer final : public Reducer::Observer {
  public:
   GraphReducer(Graph* graph, Zone* zone);
+  ~GraphReducer() final;
 
   Graph* graph() const { return graph_; }
 
   void AddReducer(Reducer* reducer);
 
   // Reduce a single node.
   void ReduceNode(Node* const);
   // Reduce the whole graph.
   void ReduceGraph();
 
  private:
   enum class State : uint8_t;
   struct NodeState {
     Node* node;
     int input_index;
   };
 
   // Reduce a single node.
   Reduction Reduce(Node* const);
   // Reduce the node on top of the stack.
   void ReduceTop();
 
+  // Replace {node} with {replacement}.
+  void Replace(Node* node, Node* replacement) final;
+  // Replace {node} during reduction with {replacement}. If the {replacement}
+  // is a node whose id is less than {max_id}, then replace all uses.
+  // Otherwise, only replace edges whose user id is less than {max_id}.
+  void Replace(Node* node, Node* replacement, NodeId max_id);
+
   // Node stack operations.
   void Pop();
   void Push(Node* node);
 
   // Revisit queue operations.
   bool Recurse(Node* node);
-  void Revisit(Node* node);
+  void Revisit(Node* node) final;
 
-  Graph* graph_;
+  // Finish the graph reduction.
+  bool Finish() {
+    for (Reducer* const reducer : reducers_) {
+      if (!reducer->Finish()) return false;
+    }
+    return true;
+  }
+
+  Graph* const graph_;
   NodeMarker<State> state_;
   ZoneVector<Reducer*> reducers_;
   ZoneStack<Node*> revisit_;
   ZoneStack<NodeState> stack_;
 
   DISALLOW_COPY_AND_ASSIGN(GraphReducer);
 };
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8
 
 #endif  // V8_COMPILER_GRAPH_REDUCER_H_