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_GENERIC_NODE_INL_H_ |
| 6 #define V8_COMPILER_GENERIC_NODE_INL_H_ |
| 7 |
5 #include "src/v8.h" | 8 #include "src/v8.h" |
6 | 9 |
7 #include "src/compiler/node.h" | 10 #include "src/compiler/generic-graph.h" |
| 11 #include "src/compiler/generic-node.h" |
| 12 #include "src/zone.h" |
8 | 13 |
9 namespace v8 { | 14 namespace v8 { |
10 namespace internal { | 15 namespace internal { |
11 namespace compiler { | 16 namespace compiler { |
12 | 17 |
13 void Node::Kill() { | 18 template <class B, class S> |
14 DCHECK_NOT_NULL(op()); | 19 GenericNode<B, S>::GenericNode(GenericGraphBase* graph, int input_count, |
15 RemoveAllInputs(); | 20 int reserve_input_count) |
16 DCHECK(uses().empty()); | 21 : BaseClass(graph->zone()), |
17 } | 22 input_count_(input_count), |
18 | |
19 | |
20 Node::Node(GenericGraphBase* graph, int input_count, int reserve_input_count) | |
21 : input_count_(input_count), | |
22 reserve_input_count_(reserve_input_count), | 23 reserve_input_count_(reserve_input_count), |
23 has_appendable_inputs_(false), | 24 has_appendable_inputs_(false), |
24 use_count_(0), | 25 use_count_(0), |
25 first_use_(NULL), | 26 first_use_(NULL), |
26 last_use_(NULL) { | 27 last_use_(NULL) { |
27 DCHECK(reserve_input_count <= kMaxReservedInputs); | 28 DCHECK(reserve_input_count <= kMaxReservedInputs); |
28 inputs_.static_ = reinterpret_cast<Input*>(this + 1); | 29 inputs_.static_ = reinterpret_cast<Input*>(this + 1); |
29 AssignUniqueID(graph); | 30 AssignUniqueID(graph); |
30 } | 31 } |
31 | 32 |
32 | 33 template <class B, class S> |
33 void Node::CollectProjections(NodeVector* projections) { | 34 inline void GenericNode<B, S>::AssignUniqueID(GenericGraphBase* graph) { |
34 for (size_t i = 0; i < projections->size(); i++) { | |
35 (*projections)[i] = NULL; | |
36 } | |
37 for (UseIter i = uses().begin(); i != uses().end(); ++i) { | |
38 if ((*i)->opcode() != IrOpcode::kProjection) continue; | |
39 size_t index = OpParameter<size_t>(*i); | |
40 DCHECK_LT(index, projections->size()); | |
41 DCHECK_EQ(NULL, (*projections)[index]); | |
42 (*projections)[index] = *i; | |
43 } | |
44 } | |
45 | |
46 | |
47 Node* Node::FindProjection(size_t projection_index) { | |
48 for (UseIter i = uses().begin(); i != uses().end(); ++i) { | |
49 if ((*i)->opcode() == IrOpcode::kProjection && | |
50 OpParameter<size_t>(*i) == projection_index) { | |
51 return *i; | |
52 } | |
53 } | |
54 return NULL; | |
55 } | |
56 | |
57 | |
58 void Node::AssignUniqueID(GenericGraphBase* graph) { | |
59 id_ = graph->NextNodeID(); | 35 id_ = graph->NextNodeID(); |
60 } | 36 } |
61 | 37 |
62 | 38 template <class B, class S> |
63 Node::Inputs::iterator Node::Inputs::begin() { | 39 inline typename GenericNode<B, S>::Inputs::iterator |
64 return Node::Inputs::iterator(this->node_, 0); | 40 GenericNode<B, S>::Inputs::begin() { |
| 41 return typename GenericNode<B, S>::Inputs::iterator(this->node_, 0); |
65 } | 42 } |
66 | 43 |
67 | 44 template <class B, class S> |
68 Node::Inputs::iterator Node::Inputs::end() { | 45 inline typename GenericNode<B, S>::Inputs::iterator |
69 return Node::Inputs::iterator(this->node_, this->node_->InputCount()); | 46 GenericNode<B, S>::Inputs::end() { |
| 47 return typename GenericNode<B, S>::Inputs::iterator( |
| 48 this->node_, this->node_->InputCount()); |
70 } | 49 } |
71 | 50 |
72 | 51 template <class B, class S> |
73 Node::Uses::iterator Node::Uses::begin() { | 52 inline typename GenericNode<B, S>::Uses::iterator |
74 return Node::Uses::iterator(this->node_); | 53 GenericNode<B, S>::Uses::begin() { |
| 54 return typename GenericNode<B, S>::Uses::iterator(this->node_); |
75 } | 55 } |
76 | 56 |
| 57 template <class B, class S> |
| 58 inline typename GenericNode<B, S>::Uses::iterator |
| 59 GenericNode<B, S>::Uses::end() { |
| 60 return typename GenericNode<B, S>::Uses::iterator(); |
| 61 } |
77 | 62 |
78 Node::Uses::iterator Node::Uses::end() { return Node::Uses::iterator(); } | 63 template <class B, class S> |
79 | 64 void GenericNode<B, S>::ReplaceUses(GenericNode* replace_to) { |
80 | |
81 void Node::ReplaceUses(Node* replace_to) { | |
82 for (Use* use = first_use_; use != NULL; use = use->next) { | 65 for (Use* use = first_use_; use != NULL; use = use->next) { |
83 use->from->GetInputRecordPtr(use->input_index)->to = replace_to; | 66 use->from->GetInputRecordPtr(use->input_index)->to = replace_to; |
84 } | 67 } |
85 if (replace_to->last_use_ == NULL) { | 68 if (replace_to->last_use_ == NULL) { |
86 DCHECK_EQ(NULL, replace_to->first_use_); | 69 DCHECK_EQ(NULL, replace_to->first_use_); |
87 replace_to->first_use_ = first_use_; | 70 replace_to->first_use_ = first_use_; |
88 replace_to->last_use_ = last_use_; | 71 replace_to->last_use_ = last_use_; |
89 } else if (first_use_ != NULL) { | 72 } else if (first_use_ != NULL) { |
90 DCHECK_NE(NULL, replace_to->first_use_); | 73 DCHECK_NE(NULL, replace_to->first_use_); |
91 replace_to->last_use_->next = first_use_; | 74 replace_to->last_use_->next = first_use_; |
92 first_use_->prev = replace_to->last_use_; | 75 first_use_->prev = replace_to->last_use_; |
93 replace_to->last_use_ = last_use_; | 76 replace_to->last_use_ = last_use_; |
94 } | 77 } |
95 replace_to->use_count_ += use_count_; | 78 replace_to->use_count_ += use_count_; |
96 use_count_ = 0; | 79 use_count_ = 0; |
97 first_use_ = NULL; | 80 first_use_ = NULL; |
98 last_use_ = NULL; | 81 last_use_ = NULL; |
99 } | 82 } |
100 | 83 |
| 84 template <class B, class S> |
| 85 template <class UnaryPredicate> |
| 86 void GenericNode<B, S>::ReplaceUsesIf(UnaryPredicate pred, |
| 87 GenericNode* replace_to) { |
| 88 for (Use* use = first_use_; use != NULL;) { |
| 89 Use* next = use->next; |
| 90 if (pred(static_cast<S*>(use->from))) { |
| 91 RemoveUse(use); |
| 92 replace_to->AppendUse(use); |
| 93 use->from->GetInputRecordPtr(use->input_index)->to = replace_to; |
| 94 } |
| 95 use = next; |
| 96 } |
| 97 } |
101 | 98 |
102 void Node::RemoveAllInputs() { | 99 template <class B, class S> |
103 for (Inputs::iterator iter(inputs().begin()); iter != inputs().end(); | 100 void GenericNode<B, S>::RemoveAllInputs() { |
| 101 for (typename Inputs::iterator iter(inputs().begin()); iter != inputs().end(); |
104 ++iter) { | 102 ++iter) { |
105 iter.GetInput()->Update(NULL); | 103 iter.GetInput()->Update(NULL); |
106 } | 104 } |
107 } | 105 } |
108 | 106 |
109 | 107 template <class B, class S> |
110 void Node::TrimInputCount(int new_input_count) { | 108 void GenericNode<B, S>::TrimInputCount(int new_input_count) { |
111 if (new_input_count == input_count_) return; // Nothing to do. | 109 if (new_input_count == input_count_) return; // Nothing to do. |
112 | 110 |
113 DCHECK(new_input_count < input_count_); | 111 DCHECK(new_input_count < input_count_); |
114 | 112 |
115 // Update inline inputs. | 113 // Update inline inputs. |
116 for (int i = new_input_count; i < input_count_; i++) { | 114 for (int i = new_input_count; i < input_count_; i++) { |
117 Node::Input* input = GetInputRecordPtr(i); | 115 typename GenericNode<B, S>::Input* input = GetInputRecordPtr(i); |
118 input->Update(NULL); | 116 input->Update(NULL); |
119 } | 117 } |
120 input_count_ = new_input_count; | 118 input_count_ = new_input_count; |
121 } | 119 } |
122 | 120 |
123 | 121 template <class B, class S> |
124 void Node::ReplaceInput(int index, Node* new_to) { | 122 void GenericNode<B, S>::ReplaceInput(int index, GenericNode<B, S>* new_to) { |
125 Input* input = GetInputRecordPtr(index); | 123 Input* input = GetInputRecordPtr(index); |
126 input->Update(new_to); | 124 input->Update(new_to); |
127 } | 125 } |
128 | 126 |
129 | 127 template <class B, class S> |
130 void Node::Input::Update(Node* new_to) { | 128 void GenericNode<B, S>::Input::Update(GenericNode<B, S>* new_to) { |
131 Node* old_to = this->to; | 129 GenericNode* old_to = this->to; |
132 if (new_to == old_to) return; // Nothing to do. | 130 if (new_to == old_to) return; // Nothing to do. |
133 // Snip out the use from where it used to be | 131 // Snip out the use from where it used to be |
134 if (old_to != NULL) { | 132 if (old_to != NULL) { |
135 old_to->RemoveUse(use); | 133 old_to->RemoveUse(use); |
136 } | 134 } |
137 to = new_to; | 135 to = new_to; |
138 // And put it into the new node's use list. | 136 // And put it into the new node's use list. |
139 if (new_to != NULL) { | 137 if (new_to != NULL) { |
140 new_to->AppendUse(use); | 138 new_to->AppendUse(use); |
141 } else { | 139 } else { |
142 use->next = NULL; | 140 use->next = NULL; |
143 use->prev = NULL; | 141 use->prev = NULL; |
144 } | 142 } |
145 } | 143 } |
146 | 144 |
147 | 145 template <class B, class S> |
148 void Node::EnsureAppendableInputs(Zone* zone) { | 146 void GenericNode<B, S>::EnsureAppendableInputs(Zone* zone) { |
149 if (!has_appendable_inputs_) { | 147 if (!has_appendable_inputs_) { |
150 void* deque_buffer = zone->New(sizeof(InputDeque)); | 148 void* deque_buffer = zone->New(sizeof(InputDeque)); |
151 InputDeque* deque = new (deque_buffer) InputDeque(zone); | 149 InputDeque* deque = new (deque_buffer) InputDeque(zone); |
152 for (int i = 0; i < input_count_; ++i) { | 150 for (int i = 0; i < input_count_; ++i) { |
153 deque->push_back(inputs_.static_[i]); | 151 deque->push_back(inputs_.static_[i]); |
154 } | 152 } |
155 inputs_.appendable_ = deque; | 153 inputs_.appendable_ = deque; |
156 has_appendable_inputs_ = true; | 154 has_appendable_inputs_ = true; |
157 } | 155 } |
158 } | 156 } |
159 | 157 |
160 | 158 template <class B, class S> |
161 void Node::AppendInput(Zone* zone, Node* to_append) { | 159 void GenericNode<B, S>::AppendInput(Zone* zone, GenericNode<B, S>* to_append) { |
162 Use* new_use = new (zone) Use; | 160 Use* new_use = new (zone) Use; |
163 Input new_input; | 161 Input new_input; |
164 new_input.to = to_append; | 162 new_input.to = to_append; |
165 new_input.use = new_use; | 163 new_input.use = new_use; |
166 if (reserve_input_count_ > 0) { | 164 if (reserve_input_count_ > 0) { |
167 DCHECK(!has_appendable_inputs_); | 165 DCHECK(!has_appendable_inputs_); |
168 reserve_input_count_--; | 166 reserve_input_count_--; |
169 inputs_.static_[input_count_] = new_input; | 167 inputs_.static_[input_count_] = new_input; |
170 } else { | 168 } else { |
171 EnsureAppendableInputs(zone); | 169 EnsureAppendableInputs(zone); |
172 inputs_.appendable_->push_back(new_input); | 170 inputs_.appendable_->push_back(new_input); |
173 } | 171 } |
174 new_use->input_index = input_count_; | 172 new_use->input_index = input_count_; |
175 new_use->from = this; | 173 new_use->from = this; |
176 to_append->AppendUse(new_use); | 174 to_append->AppendUse(new_use); |
177 input_count_++; | 175 input_count_++; |
178 } | 176 } |
179 | 177 |
180 | 178 template <class B, class S> |
181 void Node::InsertInput(Zone* zone, int index, Node* to_insert) { | 179 void GenericNode<B, S>::InsertInput(Zone* zone, int index, |
| 180 GenericNode<B, S>* to_insert) { |
182 DCHECK(index >= 0 && index < InputCount()); | 181 DCHECK(index >= 0 && index < InputCount()); |
183 // TODO(turbofan): Optimize this implementation! | 182 // TODO(turbofan): Optimize this implementation! |
184 AppendInput(zone, InputAt(InputCount() - 1)); | 183 AppendInput(zone, InputAt(InputCount() - 1)); |
185 for (int i = InputCount() - 1; i > index; --i) { | 184 for (int i = InputCount() - 1; i > index; --i) { |
186 ReplaceInput(i, InputAt(i - 1)); | 185 ReplaceInput(i, InputAt(i - 1)); |
187 } | 186 } |
188 ReplaceInput(index, to_insert); | 187 ReplaceInput(index, to_insert); |
189 } | 188 } |
190 | 189 |
191 | 190 template <class B, class S> |
192 void Node::RemoveInput(int index) { | 191 void GenericNode<B, S>::RemoveInput(int index) { |
193 DCHECK(index >= 0 && index < InputCount()); | 192 DCHECK(index >= 0 && index < InputCount()); |
194 // TODO(turbofan): Optimize this implementation! | 193 // TODO(turbofan): Optimize this implementation! |
195 for (; index < InputCount() - 1; ++index) { | 194 for (; index < InputCount() - 1; ++index) { |
196 ReplaceInput(index, InputAt(index + 1)); | 195 ReplaceInput(index, InputAt(index + 1)); |
197 } | 196 } |
198 TrimInputCount(InputCount() - 1); | 197 TrimInputCount(InputCount() - 1); |
199 } | 198 } |
200 | 199 |
201 | 200 template <class B, class S> |
202 void Node::AppendUse(Use* use) { | 201 void GenericNode<B, S>::AppendUse(Use* use) { |
203 use->next = NULL; | 202 use->next = NULL; |
204 use->prev = last_use_; | 203 use->prev = last_use_; |
205 if (last_use_ == NULL) { | 204 if (last_use_ == NULL) { |
206 first_use_ = use; | 205 first_use_ = use; |
207 } else { | 206 } else { |
208 last_use_->next = use; | 207 last_use_->next = use; |
209 } | 208 } |
210 last_use_ = use; | 209 last_use_ = use; |
211 ++use_count_; | 210 ++use_count_; |
212 } | 211 } |
213 | 212 |
214 | 213 template <class B, class S> |
215 void Node::RemoveUse(Use* use) { | 214 void GenericNode<B, S>::RemoveUse(Use* use) { |
216 if (last_use_ == use) { | 215 if (last_use_ == use) { |
217 last_use_ = use->prev; | 216 last_use_ = use->prev; |
218 } | 217 } |
219 if (use->prev != NULL) { | 218 if (use->prev != NULL) { |
220 use->prev->next = use->next; | 219 use->prev->next = use->next; |
221 } else { | 220 } else { |
222 first_use_ = use->next; | 221 first_use_ = use->next; |
223 } | 222 } |
224 if (use->next != NULL) { | 223 if (use->next != NULL) { |
225 use->next->prev = use->prev; | 224 use->next->prev = use->prev; |
226 } | 225 } |
227 --use_count_; | 226 --use_count_; |
228 } | 227 } |
229 | 228 |
230 | 229 template <class B, class S> |
231 bool Node::OwnedBy(Node* owner) const { | 230 inline bool GenericNode<B, S>::OwnedBy(GenericNode* owner) const { |
232 return first_use_ != NULL && first_use_->from == owner && | 231 return first_use_ != NULL && first_use_->from == owner && |
233 first_use_->next == NULL; | 232 first_use_->next == NULL; |
234 } | 233 } |
235 | 234 |
236 | 235 template <class B, class S> |
237 Node* Node::New(GenericGraphBase* graph, int input_count, Node** inputs, | 236 S* GenericNode<B, S>::New(GenericGraphBase* graph, int input_count, S** inputs, |
238 bool has_extensible_inputs) { | 237 bool has_extensible_inputs) { |
239 size_t node_size = sizeof(Node); | 238 size_t node_size = sizeof(GenericNode); |
240 int reserve_input_count = has_extensible_inputs ? kDefaultReservedInputs : 0; | 239 int reserve_input_count = has_extensible_inputs ? kDefaultReservedInputs : 0; |
241 size_t inputs_size = (input_count + reserve_input_count) * sizeof(Input); | 240 size_t inputs_size = (input_count + reserve_input_count) * sizeof(Input); |
242 size_t uses_size = input_count * sizeof(Use); | 241 size_t uses_size = input_count * sizeof(Use); |
243 int size = static_cast<int>(node_size + inputs_size + uses_size); | 242 int size = static_cast<int>(node_size + inputs_size + uses_size); |
244 Zone* zone = graph->zone(); | 243 Zone* zone = graph->zone(); |
245 void* buffer = zone->New(size); | 244 void* buffer = zone->New(size); |
246 Node* result = new (buffer) Node(graph, input_count, reserve_input_count); | 245 S* result = new (buffer) S(graph, input_count, reserve_input_count); |
247 Input* input = | 246 Input* input = |
248 reinterpret_cast<Input*>(reinterpret_cast<char*>(buffer) + node_size); | 247 reinterpret_cast<Input*>(reinterpret_cast<char*>(buffer) + node_size); |
249 Use* use = | 248 Use* use = |
250 reinterpret_cast<Use*>(reinterpret_cast<char*>(input) + inputs_size); | 249 reinterpret_cast<Use*>(reinterpret_cast<char*>(input) + inputs_size); |
251 | 250 |
252 for (int current = 0; current < input_count; ++current) { | 251 for (int current = 0; current < input_count; ++current) { |
253 Node* to = *inputs++; | 252 GenericNode* to = *inputs++; |
254 input->to = to; | 253 input->to = to; |
255 input->use = use; | 254 input->use = use; |
256 use->input_index = current; | 255 use->input_index = current; |
257 use->from = result; | 256 use->from = result; |
258 to->AppendUse(use); | 257 to->AppendUse(use); |
259 ++use; | 258 ++use; |
260 ++input; | 259 ++input; |
261 } | 260 } |
262 return result; | 261 return result; |
263 } | 262 } |
| 263 } |
| 264 } |
| 265 } // namespace v8::internal::compiler |
264 | 266 |
265 | 267 #endif // V8_COMPILER_GENERIC_NODE_INL_H_ |
266 bool Node::Uses::empty() { return begin() == end(); } | |
267 | |
268 | |
269 std::ostream& operator<<(std::ostream& os, const Node& n) { | |
270 os << n.id() << ": " << *n.op(); | |
271 if (n.op()->InputCount() != 0) { | |
272 os << "("; | |
273 for (int i = 0; i < n.op()->InputCount(); ++i) { | |
274 if (i != 0) os << ", "; | |
275 os << n.InputAt(i)->id(); | |
276 } | |
277 os << ")"; | |
278 } | |
279 return os; | |
280 } | |
281 | |
282 } // namespace compiler | |
283 } // namespace internal | |
284 } // namespace v8 | |
OLD | NEW |