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