OLD | NEW |
1 // Copyright 2013 the V8 project authors. All rights reserved. | 1 // Copyright 2013 the V8 project authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #ifndef V8_COMPILER_NODE_H_ | 5 #ifndef V8_COMPILER_NODE_H_ |
6 #define V8_COMPILER_NODE_H_ | 6 #define V8_COMPILER_NODE_H_ |
7 | 7 |
8 #include <deque> | 8 #include <deque> |
9 #include <set> | 9 #include <set> |
10 #include <vector> | 10 #include <vector> |
11 | 11 |
12 #include "src/compiler/generic-algorithm.h" | 12 #include "src/compiler/generic-algorithm.h" |
| 13 #include "src/compiler/generic-node.h" |
13 #include "src/compiler/opcodes.h" | 14 #include "src/compiler/opcodes.h" |
14 #include "src/compiler/operator.h" | 15 #include "src/compiler/operator.h" |
15 #include "src/types.h" | 16 #include "src/types.h" |
16 #include "src/zone.h" | 17 #include "src/zone.h" |
17 #include "src/zone-allocator.h" | 18 #include "src/zone-allocator.h" |
18 #include "src/zone-containers.h" | |
19 | 19 |
20 namespace v8 { | 20 namespace v8 { |
21 namespace internal { | 21 namespace internal { |
22 namespace compiler { | 22 namespace compiler { |
23 | 23 |
24 // A Node is the basic primitive of an IR graph. In addition to the graph | 24 class NodeData { |
25 // book-keeping Nodes only contain a mutable Operator that may change | |
26 // during compilation, e.g. during lowering passes. Other information that | |
27 // needs to be associated with Nodes during compilation must be stored | |
28 // out-of-line indexed by the Node's id. | |
29 class Node FINAL { | |
30 public: | 25 public: |
31 Node(GenericGraphBase* graph, int input_count, int reserve_input_count); | |
32 | |
33 void Initialize(const Operator* op) { set_op(op); } | |
34 | |
35 bool IsDead() const { return InputCount() > 0 && InputAt(0) == NULL; } | |
36 void Kill(); | |
37 | |
38 void CollectProjections(ZoneVector<Node*>* projections); | |
39 Node* FindProjection(size_t projection_index); | |
40 | |
41 const Operator* op() const { return op_; } | 26 const Operator* op() const { return op_; } |
42 void set_op(const Operator* op) { op_ = op; } | 27 void set_op(const Operator* op) { op_ = op; } |
43 | 28 |
44 IrOpcode::Value opcode() const { | 29 IrOpcode::Value opcode() const { |
45 DCHECK(op_->opcode() <= IrOpcode::kLast); | 30 DCHECK(op_->opcode() <= IrOpcode::kLast); |
46 return static_cast<IrOpcode::Value>(op_->opcode()); | 31 return static_cast<IrOpcode::Value>(op_->opcode()); |
47 } | 32 } |
48 | 33 |
49 inline NodeId id() const { return id_; } | 34 protected: |
50 | |
51 int InputCount() const { return input_count_; } | |
52 Node* InputAt(int index) const { | |
53 return static_cast<Node*>(GetInputRecordPtr(index)->to); | |
54 } | |
55 | |
56 void ReplaceInput(int index, Node* new_input); | |
57 void AppendInput(Zone* zone, Node* new_input); | |
58 void InsertInput(Zone* zone, int index, Node* new_input); | |
59 void RemoveInput(int index); | |
60 | |
61 int UseCount() { return use_count_; } | |
62 Node* UseAt(int index) { | |
63 DCHECK(index < use_count_); | |
64 Use* current = first_use_; | |
65 while (index-- != 0) { | |
66 current = current->next; | |
67 } | |
68 return current->from; | |
69 } | |
70 void ReplaceUses(Node* replace_to); | |
71 template <class UnaryPredicate> | |
72 inline void ReplaceUsesIf(UnaryPredicate pred, Node* replace_to); | |
73 void RemoveAllInputs(); | |
74 | |
75 void TrimInputCount(int input_count); | |
76 | |
77 class Inputs { | |
78 public: | |
79 class iterator; | |
80 iterator begin(); | |
81 iterator end(); | |
82 | |
83 explicit Inputs(Node* node) : node_(node) {} | |
84 | |
85 private: | |
86 Node* node_; | |
87 }; | |
88 | |
89 Inputs inputs() { return Inputs(this); } | |
90 | |
91 class Uses { | |
92 public: | |
93 class iterator; | |
94 iterator begin(); | |
95 iterator end(); | |
96 bool empty(); // { return begin() == end(); } | |
97 | |
98 explicit Uses(Node* node) : node_(node) {} | |
99 | |
100 private: | |
101 Node* node_; | |
102 }; | |
103 | |
104 Uses uses() { return Uses(this); } | |
105 | |
106 class Edge; | |
107 | |
108 bool OwnedBy(Node* owner) const; | |
109 | |
110 static Node* New(GenericGraphBase* graph, int input_count, Node** inputs, | |
111 bool has_extensible_inputs); | |
112 | |
113 | |
114 private: | |
115 const Operator* op_; | 35 const Operator* op_; |
116 Bounds bounds_; | 36 Bounds bounds_; |
| 37 explicit NodeData(Zone* zone) {} |
117 | 38 |
118 friend class NodeProperties; | 39 friend class NodeProperties; |
119 Bounds bounds() { return bounds_; } | 40 Bounds bounds() { return bounds_; } |
120 void set_bounds(Bounds b) { bounds_ = b; } | 41 void set_bounds(Bounds b) { bounds_ = b; } |
121 | |
122 friend class GenericGraphBase; | |
123 | |
124 class Use : public ZoneObject { | |
125 public: | |
126 Node* from; | |
127 Use* next; | |
128 Use* prev; | |
129 int input_index; | |
130 }; | |
131 | |
132 class Input { | |
133 public: | |
134 Node* to; | |
135 Use* use; | |
136 | |
137 void Update(Node* new_to); | |
138 }; | |
139 | |
140 void EnsureAppendableInputs(Zone* zone); | |
141 | |
142 Input* GetInputRecordPtr(int index) const { | |
143 if (has_appendable_inputs_) { | |
144 return &((*inputs_.appendable_)[index]); | |
145 } else { | |
146 return inputs_.static_ + index; | |
147 } | |
148 } | |
149 | |
150 void AppendUse(Use* use); | |
151 void RemoveUse(Use* use); | |
152 | |
153 void* operator new(size_t, void* location) { return location; } | |
154 | |
155 void AssignUniqueID(GenericGraphBase* graph); | |
156 | |
157 typedef ZoneDeque<Input> InputDeque; | |
158 | |
159 static const int kReservedInputCountBits = 2; | |
160 static const int kMaxReservedInputs = (1 << kReservedInputCountBits) - 1; | |
161 static const int kDefaultReservedInputs = kMaxReservedInputs; | |
162 | |
163 NodeId id_; | |
164 int input_count_ : 29; | |
165 unsigned int reserve_input_count_ : kReservedInputCountBits; | |
166 bool has_appendable_inputs_ : 1; | |
167 union { | |
168 // When a node is initially allocated, it uses a static buffer to hold its | |
169 // inputs under the assumption that the number of outputs will not increase. | |
170 // When the first input is appended, the static buffer is converted into a | |
171 // deque to allow for space-efficient growing. | |
172 Input* static_; | |
173 InputDeque* appendable_; | |
174 } inputs_; | |
175 int use_count_; | |
176 Use* first_use_; | |
177 Use* last_use_; | |
178 | |
179 DISALLOW_COPY_AND_ASSIGN(Node); | |
180 }; | 42 }; |
181 | 43 |
182 class Node::Edge { | 44 // A Node is the basic primitive of an IR graph. In addition to the members |
| 45 // inherited from Vector, Nodes only contain a mutable Operator that may change |
| 46 // during compilation, e.g. during lowering passes. Other information that |
| 47 // needs to be associated with Nodes during compilation must be stored |
| 48 // out-of-line indexed by the Node's id. |
| 49 class Node FINAL : public GenericNode<NodeData, Node> { |
183 public: | 50 public: |
184 Node* from() const { return input_->use->from; } | 51 Node(GenericGraphBase* graph, int input_count, int reserve_input_count) |
185 Node* to() const { return input_->to; } | 52 : GenericNode<NodeData, Node>(graph, input_count, reserve_input_count) {} |
186 int index() const { | |
187 int index = input_->use->input_index; | |
188 DCHECK(index < input_->use->from->input_count_); | |
189 return index; | |
190 } | |
191 | 53 |
192 private: | 54 void Initialize(const Operator* op) { set_op(op); } |
193 friend class Node::Uses::iterator; | |
194 friend class Node::Inputs::iterator; | |
195 | 55 |
196 explicit Edge(Node::Input* input) : input_(input) {} | 56 bool IsDead() const { return InputCount() > 0 && InputAt(0) == NULL; } |
| 57 void Kill(); |
197 | 58 |
198 Node::Input* input_; | 59 void CollectProjections(ZoneVector<Node*>* projections); |
| 60 Node* FindProjection(size_t projection_index); |
199 }; | 61 }; |
200 | 62 |
201 | |
202 // A forward iterator to visit the nodes which are depended upon by a node | |
203 // in the order of input. | |
204 class Node::Inputs::iterator { | |
205 public: | |
206 iterator(const Node::Inputs::iterator& other) // NOLINT | |
207 : node_(other.node_), | |
208 index_(other.index_) {} | |
209 | |
210 Node* operator*() { return GetInput()->to; } | |
211 Node::Edge edge() { return Node::Edge(GetInput()); } | |
212 bool operator==(const iterator& other) const { | |
213 return other.index_ == index_ && other.node_ == node_; | |
214 } | |
215 bool operator!=(const iterator& other) const { return !(other == *this); } | |
216 iterator& operator++() { | |
217 DCHECK(node_ != NULL); | |
218 DCHECK(index_ < node_->input_count_); | |
219 ++index_; | |
220 return *this; | |
221 } | |
222 iterator& UpdateToAndIncrement(Node* new_to) { | |
223 Node::Input* input = GetInput(); | |
224 input->Update(new_to); | |
225 index_++; | |
226 return *this; | |
227 } | |
228 int index() { return index_; } | |
229 | |
230 private: | |
231 friend class Node; | |
232 | |
233 explicit iterator(Node* node, int index) : node_(node), index_(index) {} | |
234 | |
235 Input* GetInput() const { return node_->GetInputRecordPtr(index_); } | |
236 | |
237 Node* node_; | |
238 int index_; | |
239 }; | |
240 | |
241 // A forward iterator to visit the uses of a node. The uses are returned in | |
242 // the order in which they were added as inputs. | |
243 class Node::Uses::iterator { | |
244 public: | |
245 iterator(const Node::Uses::iterator& other) // NOLINT | |
246 : current_(other.current_), | |
247 index_(other.index_) {} | |
248 | |
249 Node* operator*() { return current_->from; } | |
250 Node::Edge edge() { return Node::Edge(CurrentInput()); } | |
251 | |
252 bool operator==(const iterator& other) { return other.current_ == current_; } | |
253 bool operator!=(const iterator& other) { return other.current_ != current_; } | |
254 iterator& operator++() { | |
255 DCHECK(current_ != NULL); | |
256 index_++; | |
257 current_ = current_->next; | |
258 return *this; | |
259 } | |
260 iterator& UpdateToAndIncrement(Node* new_to) { | |
261 DCHECK(current_ != NULL); | |
262 index_++; | |
263 Node::Input* input = CurrentInput(); | |
264 current_ = current_->next; | |
265 input->Update(new_to); | |
266 return *this; | |
267 } | |
268 int index() const { return index_; } | |
269 | |
270 private: | |
271 friend class Node::Uses; | |
272 | |
273 iterator() : current_(NULL), index_(0) {} | |
274 explicit iterator(Node* node) : current_(node->first_use_), index_(0) {} | |
275 | |
276 Input* CurrentInput() const { | |
277 return current_->from->GetInputRecordPtr(current_->input_index); | |
278 } | |
279 | |
280 Node::Use* current_; | |
281 int index_; | |
282 }; | |
283 | |
284 | |
285 template <class UnaryPredicate> | |
286 inline void Node::ReplaceUsesIf(UnaryPredicate pred, Node* replace_to) { | |
287 for (Use* use = first_use_; use != NULL;) { | |
288 Use* next = use->next; | |
289 if (pred(use->from)) { | |
290 RemoveUse(use); | |
291 replace_to->AppendUse(use); | |
292 use->from->GetInputRecordPtr(use->input_index)->to = replace_to; | |
293 } | |
294 use = next; | |
295 } | |
296 } | |
297 | |
298 std::ostream& operator<<(std::ostream& os, const Node& n); | 63 std::ostream& operator<<(std::ostream& os, const Node& n); |
299 | 64 |
300 typedef GenericGraphVisit::NullNodeVisitor<Node> NullNodeVisitor; | 65 typedef GenericGraphVisit::NullNodeVisitor<NodeData, Node> NullNodeVisitor; |
301 | 66 |
302 typedef std::set<Node*, std::less<Node*>, zone_allocator<Node*> > NodeSet; | 67 typedef std::set<Node*, std::less<Node*>, zone_allocator<Node*> > NodeSet; |
303 typedef NodeSet::iterator NodeSetIter; | 68 typedef NodeSet::iterator NodeSetIter; |
304 typedef NodeSet::reverse_iterator NodeSetRIter; | 69 typedef NodeSet::reverse_iterator NodeSetRIter; |
305 | 70 |
306 typedef ZoneVector<Node*> NodeVector; | 71 typedef ZoneVector<Node*> NodeVector; |
307 typedef NodeVector::iterator NodeVectorIter; | 72 typedef NodeVector::iterator NodeVectorIter; |
308 typedef NodeVector::const_iterator NodeVectorConstIter; | 73 typedef NodeVector::const_iterator NodeVectorConstIter; |
309 typedef NodeVector::reverse_iterator NodeVectorRIter; | 74 typedef NodeVector::reverse_iterator NodeVectorRIter; |
310 | 75 |
311 typedef ZoneVector<NodeVector> NodeVectorVector; | 76 typedef ZoneVector<NodeVector> NodeVectorVector; |
312 typedef NodeVectorVector::iterator NodeVectorVectorIter; | 77 typedef NodeVectorVector::iterator NodeVectorVectorIter; |
313 typedef NodeVectorVector::reverse_iterator NodeVectorVectorRIter; | 78 typedef NodeVectorVector::reverse_iterator NodeVectorVectorRIter; |
314 | 79 |
315 typedef Node::Uses::iterator UseIter; | 80 typedef Node::Uses::iterator UseIter; |
316 typedef Node::Inputs::iterator InputIter; | 81 typedef Node::Inputs::iterator InputIter; |
317 | 82 |
318 // Helper to extract parameters from Operator1<*> nodes. | 83 // Helper to extract parameters from Operator1<*> nodes. |
319 template <typename T> | 84 template <typename T> |
320 static inline const T& OpParameter(const Node* node) { | 85 static inline const T& OpParameter(const Node* node) { |
321 return OpParameter<T>(node->op()); | 86 return OpParameter<T>(node->op()); |
322 } | 87 } |
323 | 88 |
324 } // namespace compiler | 89 } // namespace compiler |
325 } // namespace internal | 90 } // namespace internal |
326 } // namespace v8 | 91 } // namespace v8 |
327 | 92 |
328 #endif // V8_COMPILER_NODE_H_ | 93 #endif // V8_COMPILER_NODE_H_ |
OLD | NEW |