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 13namespace v8 { 14namespace internal { 15namespace compiler { 16 17// Forward declarations. 18class Graph; 19class 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. 24typedef uint32_t NodeId; 25 26 27// Represents the result of trying to reduce a node in the graph. 28class Reduction final { 29 public: 30 explicit Reduction(Node* replacement = nullptr) : replacement_(replacement) {} 31 32 Node* replacement() const { return replacement_; } 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. 45class V8_EXPORT_PRIVATE Reducer { 46 public: 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. 58 static Reduction NoChange() { return Reduction(); } 59 static Reduction Replace(Node* node) { return Reduction(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. 66class AdvancedReducer : public Reducer { 67 public: 68 // Observe the actions of this reducer. 69 class Editor { 70 public: 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 84 explicit AdvancedReducer(Editor* editor) : editor_(editor) {} 85 86 protected: 87 // Helper functions for subclasses to produce reductions for a node. 88 static Reduction Replace(Node* node) { return Reducer::Replace(node); } 89 90 // Helper functions for subclasses to edit the graph. 91 void Replace(Node* node, Node* replacement) { 92 DCHECK_NOT_NULL(editor_); 93 editor_->Replace(node, replacement); 94 } 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()}. 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}. 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. 124class V8_EXPORT_PRIVATE GraphReducer 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