1// Copyright 2014 the V8 project authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#ifndef V8_COMPILER_GRAPH_REDUCER_H_
6#define V8_COMPILER_GRAPH_REDUCER_H_
7
8#include "src/base/compiler-specific.h"
9#include "src/common/globals.h"
10#include "src/compiler/node-marker.h"
11#include "src/zone/zone-containers.h"
12
13namespace v8 {
14namespace internal {
15
16class TickCounter;
17
18namespace compiler {
19
20class Graph;
21class JSHeapBroker;
22class Node;
23class ObserveNodeManager;
24
25// NodeIds are identifying numbers for nodes that can be used to index auxiliary
26// out-of-line data associated with each node.
27using NodeId = uint32_t;
28
29// Possible outcomes for decisions.
30enum class Decision : uint8_t { kUnknown, kTrue, kFalse };
31
32// Represents the result of trying to reduce a node in the graph.
33class Reduction final {
34 public:
35  explicit Reduction(Node* replacement = nullptr) : replacement_(replacement) {}
36
37  Node* replacement() const { return replacement_; }
38  bool Changed() const { return replacement() != nullptr; }
39  Reduction FollowedBy(Reduction next) const {
40    if (next.Changed()) return next;
41    return *this;
42  }
43
44 private:
45  Node* replacement_;
46};
47
48
49// A reducer can reduce or simplify a given node based on its operator and
50// inputs. This class functions as an extension point for the graph reducer for
51// language-specific reductions (e.g. reduction based on types or constant
52// folding of low-level operators) can be integrated into the graph reduction
53// phase.
54class V8_EXPORT_PRIVATE Reducer {
55 public:
56  virtual ~Reducer() = default;
57
58  // Only used for tracing, when using the --trace_turbo_reduction flag.
59  virtual const char* reducer_name() const = 0;
60
61  // Try to reduce a node if possible.
62  Reduction Reduce(Node* node, ObserveNodeManager* observe_node_manager);
63
64  // Invoked by the {GraphReducer} when all nodes are done.  Can be used to
65  // do additional reductions at the end, which in turn can cause a new round
66  // of reductions.
67  virtual void Finalize();
68
69  // Helper functions for subclasses to produce reductions for a node.
70  static Reduction NoChange() { return Reduction(); }
71  static Reduction Replace(Node* node) { return Reduction(node); }
72  static Reduction Changed(Node* node) { return Reduction(node); }
73
74 private:
75  virtual Reduction Reduce(Node* node) = 0;
76};
77
78
79// An advanced reducer can also edit the graphs by changing and replacing nodes
80// other than the one currently being reduced.
81class AdvancedReducer : public Reducer {
82 public:
83  // Observe the actions of this reducer.
84  class Editor {
85   public:
86    virtual ~Editor() = default;
87
88    // Replace {node} with {replacement}.
89    virtual void Replace(Node* node, Node* replacement) = 0;
90    // Revisit the {node} again later.
91    virtual void Revisit(Node* node) = 0;
92    // Replace value uses of {node} with {value} and effect uses of {node} with
93    // {effect}. If {effect == nullptr}, then use the effect input to {node}.
94    // All control uses will be relaxed assuming {node} cannot throw.
95    virtual void ReplaceWithValue(Node* node, Node* value, Node* effect,
96                                  Node* control) = 0;
97  };
98
99  explicit AdvancedReducer(Editor* editor) : editor_(editor) {}
100
101 protected:
102  // Helper functions for subclasses to produce reductions for a node.
103  static Reduction Replace(Node* node) { return Reducer::Replace(node); }
104
105  // Helper functions for subclasses to edit the graph.
106  void Replace(Node* node, Node* replacement) {
107    DCHECK_NOT_NULL(editor_);
108    editor_->Replace(node, replacement);
109  }
110  void Revisit(Node* node) {
111    DCHECK_NOT_NULL(editor_);
112    editor_->Revisit(node);
113  }
114  void ReplaceWithValue(Node* node, Node* value, Node* effect = nullptr,
115                        Node* control = nullptr) {
116    DCHECK_NOT_NULL(editor_);
117    editor_->ReplaceWithValue(node, value, effect, control);
118  }
119
120  // Relax the effects of {node} by immediately replacing effect and control
121  // uses of {node} with the effect and control input to {node}.
122  // TODO(turbofan): replace the effect input to {node} with {graph->start()}.
123  void RelaxEffectsAndControls(Node* node) {
124    ReplaceWithValue(node, node, nullptr, nullptr);
125  }
126
127  // Relax the control uses of {node} by immediately replacing them with the
128  // control input to {node}.
129  void RelaxControls(Node* node) {
130    ReplaceWithValue(node, node, node, nullptr);
131  }
132
133 private:
134  Editor* const editor_;
135};
136
137
138// Performs an iterative reduction of a node graph.
139class V8_EXPORT_PRIVATE GraphReducer
140    : public NON_EXPORTED_BASE(AdvancedReducer::Editor) {
141 public:
142  GraphReducer(Zone* zone, Graph* graph, TickCounter* tick_counter,
143               JSHeapBroker* broker, Node* dead = nullptr,
144               ObserveNodeManager* observe_node_manager = nullptr);
145  ~GraphReducer() override;
146
147  GraphReducer(const GraphReducer&) = delete;
148  GraphReducer& operator=(const GraphReducer&) = delete;
149
150  Graph* graph() const { return graph_; }
151
152  void AddReducer(Reducer* reducer);
153
154  // Reduce a single node.
155  void ReduceNode(Node* const);
156  // Reduce the whole graph.
157  void ReduceGraph();
158
159 private:
160  enum class State : uint8_t;
161  struct NodeState {
162    Node* node;
163    int input_index;
164  };
165
166  // Reduce a single node.
167  Reduction Reduce(Node* const);
168  // Reduce the node on top of the stack.
169  void ReduceTop();
170
171  // Replace {node} with {replacement}.
172  void Replace(Node* node, Node* replacement) final;
173
174  // Replace value uses of {node} with {value} and effect uses of {node} with
175  // {effect}. If {effect == nullptr}, then use the effect input to {node}. All
176  // control uses will be relaxed assuming {node} cannot throw.
177  void ReplaceWithValue(Node* node, Node* value, Node* effect,
178                        Node* control) final;
179
180  // Replace all uses of {node} with {replacement} if the id of {replacement} is
181  // less than or equal to {max_id}. Otherwise, replace all uses of {node} whose
182  // id is less than or equal to {max_id} with the {replacement}.
183  void Replace(Node* node, Node* replacement, NodeId max_id);
184
185  // Node stack operations.
186  void Pop();
187  void Push(Node* node);
188
189  // Revisit queue operations.
190  bool Recurse(Node* node);
191  void Revisit(Node* node) final;
192
193  Graph* const graph_;
194  Node* const dead_;
195  NodeMarker<State> state_;
196  ZoneVector<Reducer*> reducers_;
197  ZoneQueue<Node*> revisit_;
198  ZoneStack<NodeState> stack_;
199  TickCounter* const tick_counter_;
200  JSHeapBroker* const broker_;
201  ObserveNodeManager* const observe_node_manager_;
202};
203
204}  // namespace compiler
205}  // namespace internal
206}  // namespace v8
207
208#endif  // V8_COMPILER_GRAPH_REDUCER_H_
209