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