OLD | NEW |
| (Empty) |
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 | |
3 // found in the LICENSE file. | |
4 | |
5 #ifndef V8_COMPILER_GENERIC_NODE_H_ | |
6 #define V8_COMPILER_GENERIC_NODE_H_ | |
7 | |
8 #include "src/v8.h" | |
9 | |
10 #include "src/zone-containers.h" | |
11 | |
12 namespace v8 { | |
13 namespace internal { | |
14 namespace compiler { | |
15 | |
16 class GenericGraphBase; | |
17 | |
18 typedef int NodeId; | |
19 | |
20 // A GenericNode<> is the basic primitive of graphs. GenericNode's are | |
21 // chained together by input/use chains but by default otherwise contain only an | |
22 // identifying number which specific applications of graphs and nodes can use | |
23 // to index auxiliary out-of-line data, especially transient data. | |
24 // Specializations of the templatized GenericNode<> class must provide a base | |
25 // class B that contains all of the members to be made available in each | |
26 // specialized Node instance. GenericNode uses a mixin template pattern to | |
27 // ensure that common accessors and methods expect the derived class S type | |
28 // rather than the GenericNode<B, S> type. | |
29 template <class B, class S> | |
30 class GenericNode : public B { | |
31 public: | |
32 typedef B BaseClass; | |
33 typedef S DerivedClass; | |
34 | |
35 inline NodeId id() const { return id_; } | |
36 | |
37 int InputCount() const { return input_count_; } | |
38 S* InputAt(int index) const { | |
39 return static_cast<S*>(GetInputRecordPtr(index)->to); | |
40 } | |
41 inline void ReplaceInput(int index, GenericNode* new_input); | |
42 inline void AppendInput(Zone* zone, GenericNode* new_input); | |
43 inline void InsertInput(Zone* zone, int index, GenericNode* new_input); | |
44 inline void RemoveInput(int index); | |
45 | |
46 int UseCount() { return use_count_; } | |
47 S* UseAt(int index) { | |
48 DCHECK(index < use_count_); | |
49 Use* current = first_use_; | |
50 while (index-- != 0) { | |
51 current = current->next; | |
52 } | |
53 return static_cast<S*>(current->from); | |
54 } | |
55 inline void ReplaceUses(GenericNode* replace_to); | |
56 template <class UnaryPredicate> | |
57 inline void ReplaceUsesIf(UnaryPredicate pred, GenericNode* replace_to); | |
58 inline void RemoveAllInputs(); | |
59 | |
60 inline void TrimInputCount(int input_count); | |
61 | |
62 class Inputs { | |
63 public: | |
64 class iterator; | |
65 iterator begin(); | |
66 iterator end(); | |
67 | |
68 explicit Inputs(GenericNode* node) : node_(node) {} | |
69 | |
70 private: | |
71 GenericNode* node_; | |
72 }; | |
73 | |
74 Inputs inputs() { return Inputs(this); } | |
75 | |
76 class Uses { | |
77 public: | |
78 class iterator; | |
79 iterator begin(); | |
80 iterator end(); | |
81 bool empty() { return begin() == end(); } | |
82 | |
83 explicit Uses(GenericNode* node) : node_(node) {} | |
84 | |
85 private: | |
86 GenericNode* node_; | |
87 }; | |
88 | |
89 Uses uses() { return Uses(this); } | |
90 | |
91 class Edge; | |
92 | |
93 bool OwnedBy(GenericNode* owner) const; | |
94 | |
95 static S* New(GenericGraphBase* graph, int input_count, S** inputs, | |
96 bool has_extensible_inputs); | |
97 | |
98 protected: | |
99 friend class GenericGraphBase; | |
100 | |
101 class Use : public ZoneObject { | |
102 public: | |
103 GenericNode* from; | |
104 Use* next; | |
105 Use* prev; | |
106 int input_index; | |
107 }; | |
108 | |
109 class Input { | |
110 public: | |
111 GenericNode* to; | |
112 Use* use; | |
113 | |
114 void Update(GenericNode* new_to); | |
115 }; | |
116 | |
117 void EnsureAppendableInputs(Zone* zone); | |
118 | |
119 Input* GetInputRecordPtr(int index) const { | |
120 if (has_appendable_inputs_) { | |
121 return &((*inputs_.appendable_)[index]); | |
122 } else { | |
123 return inputs_.static_ + index; | |
124 } | |
125 } | |
126 | |
127 inline void AppendUse(Use* use); | |
128 inline void RemoveUse(Use* use); | |
129 | |
130 void* operator new(size_t, void* location) { return location; } | |
131 | |
132 GenericNode(GenericGraphBase* graph, int input_count, | |
133 int reserved_input_count); | |
134 | |
135 private: | |
136 void AssignUniqueID(GenericGraphBase* graph); | |
137 | |
138 typedef ZoneDeque<Input> InputDeque; | |
139 | |
140 static const int kReservedInputCountBits = 2; | |
141 static const int kMaxReservedInputs = (1 << kReservedInputCountBits) - 1; | |
142 static const int kDefaultReservedInputs = kMaxReservedInputs; | |
143 | |
144 NodeId id_; | |
145 int input_count_ : 29; | |
146 unsigned int reserve_input_count_ : kReservedInputCountBits; | |
147 bool has_appendable_inputs_ : 1; | |
148 union { | |
149 // When a node is initially allocated, it uses a static buffer to hold its | |
150 // inputs under the assumption that the number of outputs will not increase. | |
151 // When the first input is appended, the static buffer is converted into a | |
152 // deque to allow for space-efficient growing. | |
153 Input* static_; | |
154 InputDeque* appendable_; | |
155 } inputs_; | |
156 int use_count_; | |
157 Use* first_use_; | |
158 Use* last_use_; | |
159 | |
160 DISALLOW_COPY_AND_ASSIGN(GenericNode); | |
161 }; | |
162 | |
163 // An encapsulation for information associated with a single use of node as a | |
164 // input from another node, allowing access to both the defining node and | |
165 // the ndoe having the input. | |
166 template <class B, class S> | |
167 class GenericNode<B, S>::Edge { | |
168 public: | |
169 S* from() const { return static_cast<S*>(input_->use->from); } | |
170 S* to() const { return static_cast<S*>(input_->to); } | |
171 int index() const { | |
172 int index = input_->use->input_index; | |
173 DCHECK(index < input_->use->from->input_count_); | |
174 return index; | |
175 } | |
176 | |
177 private: | |
178 friend class GenericNode<B, S>::Uses::iterator; | |
179 friend class GenericNode<B, S>::Inputs::iterator; | |
180 | |
181 explicit Edge(typename GenericNode<B, S>::Input* input) : input_(input) {} | |
182 | |
183 typename GenericNode<B, S>::Input* input_; | |
184 }; | |
185 | |
186 // A forward iterator to visit the nodes which are depended upon by a node | |
187 // in the order of input. | |
188 template <class B, class S> | |
189 class GenericNode<B, S>::Inputs::iterator { | |
190 public: | |
191 iterator(const typename GenericNode<B, S>::Inputs::iterator& other) // NOLINT | |
192 : node_(other.node_), | |
193 index_(other.index_) {} | |
194 | |
195 S* operator*() { return static_cast<S*>(GetInput()->to); } | |
196 typename GenericNode<B, S>::Edge edge() { | |
197 return typename GenericNode::Edge(GetInput()); | |
198 } | |
199 bool operator==(const iterator& other) const { | |
200 return other.index_ == index_ && other.node_ == node_; | |
201 } | |
202 bool operator!=(const iterator& other) const { return !(other == *this); } | |
203 iterator& operator++() { | |
204 DCHECK(node_ != NULL); | |
205 DCHECK(index_ < node_->input_count_); | |
206 ++index_; | |
207 return *this; | |
208 } | |
209 iterator& UpdateToAndIncrement(GenericNode<B, S>* new_to) { | |
210 typename GenericNode<B, S>::Input* input = GetInput(); | |
211 input->Update(new_to); | |
212 index_++; | |
213 return *this; | |
214 } | |
215 int index() { return index_; } | |
216 | |
217 private: | |
218 friend class GenericNode; | |
219 | |
220 explicit iterator(GenericNode* node, int index) | |
221 : node_(node), index_(index) {} | |
222 | |
223 Input* GetInput() const { return node_->GetInputRecordPtr(index_); } | |
224 | |
225 GenericNode* node_; | |
226 int index_; | |
227 }; | |
228 | |
229 // A forward iterator to visit the uses of a node. The uses are returned in | |
230 // the order in which they were added as inputs. | |
231 template <class B, class S> | |
232 class GenericNode<B, S>::Uses::iterator { | |
233 public: | |
234 iterator(const typename GenericNode<B, S>::Uses::iterator& other) // NOLINT | |
235 : current_(other.current_), | |
236 index_(other.index_) {} | |
237 | |
238 S* operator*() { return static_cast<S*>(current_->from); } | |
239 typename GenericNode<B, S>::Edge edge() { | |
240 return typename GenericNode::Edge(CurrentInput()); | |
241 } | |
242 | |
243 bool operator==(const iterator& other) { return other.current_ == current_; } | |
244 bool operator!=(const iterator& other) { return other.current_ != current_; } | |
245 iterator& operator++() { | |
246 DCHECK(current_ != NULL); | |
247 index_++; | |
248 current_ = current_->next; | |
249 return *this; | |
250 } | |
251 iterator& UpdateToAndIncrement(GenericNode<B, S>* new_to) { | |
252 DCHECK(current_ != NULL); | |
253 index_++; | |
254 typename GenericNode<B, S>::Input* input = CurrentInput(); | |
255 current_ = current_->next; | |
256 input->Update(new_to); | |
257 return *this; | |
258 } | |
259 int index() const { return index_; } | |
260 | |
261 private: | |
262 friend class GenericNode<B, S>::Uses; | |
263 | |
264 iterator() : current_(NULL), index_(0) {} | |
265 explicit iterator(GenericNode<B, S>* node) | |
266 : current_(node->first_use_), index_(0) {} | |
267 | |
268 Input* CurrentInput() const { | |
269 return current_->from->GetInputRecordPtr(current_->input_index); | |
270 } | |
271 | |
272 typename GenericNode<B, S>::Use* current_; | |
273 int index_; | |
274 }; | |
275 } | |
276 } | |
277 } // namespace v8::internal::compiler | |
278 | |
279 #endif // V8_COMPILER_GENERIC_NODE_H_ | |
OLD | NEW |