Line data Source code
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 : #include "src/compiler/node.h"
6 :
7 : namespace v8 {
8 : namespace internal {
9 : namespace compiler {
10 :
11 11757732 : Node::OutOfLineInputs* Node::OutOfLineInputs::New(Zone* zone, int capacity) {
12 : size_t size =
13 11757732 : sizeof(OutOfLineInputs) + capacity * (sizeof(Node*) + sizeof(Use));
14 11757732 : intptr_t raw_buffer = reinterpret_cast<intptr_t>(zone->New(size));
15 : Node::OutOfLineInputs* outline =
16 11757753 : reinterpret_cast<OutOfLineInputs*>(raw_buffer + capacity * sizeof(Use));
17 11757753 : outline->capacity_ = capacity;
18 11757753 : outline->count_ = 0;
19 11757753 : return outline;
20 : }
21 :
22 :
23 11721383 : void Node::OutOfLineInputs::ExtractFrom(Use* old_use_ptr, Node** old_input_ptr,
24 : int count) {
25 : // Extract the inputs from the old use and input pointers and copy them
26 : // to this out-of-line-storage.
27 11721383 : Use* new_use_ptr = reinterpret_cast<Use*>(this) - 1;
28 11721383 : Node** new_input_ptr = inputs_;
29 49143105 : for (int current = 0; current < count; current++) {
30 : new_use_ptr->bit_field_ =
31 74843444 : Use::InputIndexField::encode(current) | Use::InlineField::encode(false);
32 : DCHECK_EQ(old_input_ptr, old_use_ptr->input_ptr());
33 : DCHECK_EQ(new_input_ptr, new_use_ptr->input_ptr());
34 37421722 : Node* old_to = *old_input_ptr;
35 37421722 : if (old_to) {
36 37421722 : *old_input_ptr = nullptr;
37 : old_to->RemoveUse(old_use_ptr);
38 37421722 : *new_input_ptr = old_to;
39 : old_to->AppendUse(new_use_ptr);
40 : } else {
41 0 : *new_input_ptr = nullptr;
42 : }
43 37421722 : old_input_ptr++;
44 37421722 : new_input_ptr++;
45 37421722 : old_use_ptr--;
46 37421722 : new_use_ptr--;
47 : }
48 11721383 : this->count_ = count;
49 11721383 : }
50 :
51 :
52 150035723 : Node* Node::New(Zone* zone, NodeId id, const Operator* op, int input_count,
53 : Node* const* inputs, bool has_extensible_inputs) {
54 : Node** input_ptr;
55 : Use* use_ptr;
56 : Node* node;
57 : bool is_inline;
58 :
59 : #if DEBUG
60 : // Verify that none of the inputs are {nullptr}.
61 : for (int i = 0; i < input_count; i++) {
62 : if (inputs[i] == nullptr) {
63 : FATAL("Node::New() Error: #%d:%s[%d] is nullptr", static_cast<int>(id),
64 : op->mnemonic(), i);
65 : }
66 : }
67 : #endif
68 :
69 150035723 : if (input_count > kMaxInlineCapacity) {
70 : // Allocate out-of-line inputs.
71 : int capacity =
72 36359 : has_extensible_inputs ? input_count + kMaxInlineCapacity : input_count;
73 36359 : OutOfLineInputs* outline = OutOfLineInputs::New(zone, capacity);
74 :
75 : // Allocate node.
76 36359 : void* node_buffer = zone->New(sizeof(Node));
77 : node = new (node_buffer) Node(id, op, kOutlineMarker, 0);
78 44754 : node->inputs_.outline_ = outline;
79 :
80 44754 : outline->node_ = node;
81 44754 : outline->count_ = input_count;
82 :
83 44754 : input_ptr = outline->inputs_;
84 : use_ptr = reinterpret_cast<Use*>(outline);
85 : is_inline = false;
86 : } else {
87 : // Allocate node with inline inputs.
88 : int capacity = input_count;
89 149999364 : if (has_extensible_inputs) {
90 1232665 : const int max = kMaxInlineCapacity;
91 2465330 : capacity = std::min(input_count + 3, max);
92 : }
93 :
94 149999364 : size_t size = sizeof(Node) + capacity * (sizeof(Node*) + sizeof(Use));
95 149999364 : intptr_t raw_buffer = reinterpret_cast<intptr_t>(zone->New(size));
96 : void* node_buffer =
97 149994662 : reinterpret_cast<void*>(raw_buffer + capacity * sizeof(Use));
98 :
99 : node = new (node_buffer) Node(id, op, input_count, capacity);
100 149994662 : input_ptr = node->inputs_.inline_;
101 : use_ptr = reinterpret_cast<Use*>(node);
102 : is_inline = true;
103 : }
104 :
105 : // Initialize the input pointers and the uses.
106 416436004 : for (int current = 0; current < input_count; ++current) {
107 266396588 : Node* to = *inputs++;
108 266396588 : input_ptr[current] = to;
109 266396588 : Use* use = use_ptr - 1 - current;
110 532793176 : use->bit_field_ = Use::InputIndexField::encode(current) |
111 266396588 : Use::InlineField::encode(is_inline);
112 : to->AppendUse(use);
113 : }
114 : node->Verify();
115 150039416 : return node;
116 : }
117 :
118 :
119 4746998 : Node* Node::Clone(Zone* zone, NodeId id, const Node* node) {
120 : int const input_count = node->InputCount();
121 : Node* const* const inputs = node->has_inline_inputs()
122 : ? node->inputs_.inline_
123 2373499 : : node->inputs_.outline_->inputs_;
124 2373499 : Node* const clone = New(zone, id, node->op(), input_count, inputs, false);
125 : clone->set_type(node->type());
126 2373496 : return clone;
127 : }
128 :
129 :
130 12817964 : void Node::Kill() {
131 : DCHECK_NOT_NULL(op());
132 12817964 : NullAllInputs();
133 : DCHECK(uses().empty());
134 12818182 : }
135 :
136 :
137 24361189 : void Node::AppendInput(Zone* zone, Node* new_to) {
138 : DCHECK_NOT_NULL(zone);
139 : DCHECK_NOT_NULL(new_to);
140 :
141 48722378 : int inline_count = InlineCountField::decode(bit_field_);
142 24361189 : int inline_capacity = InlineCapacityField::decode(bit_field_);
143 24361189 : if (inline_count < inline_capacity) {
144 : // Append inline input.
145 2236014 : bit_field_ = InlineCountField::update(bit_field_, inline_count + 1);
146 1118007 : *GetInputPtr(inline_count) = new_to;
147 : Use* use = GetUsePtr(inline_count);
148 1118007 : use->bit_field_ = Use::InputIndexField::encode(inline_count) |
149 1118007 : Use::InlineField::encode(true);
150 : new_to->AppendUse(use);
151 : } else {
152 : // Append out-of-line input.
153 : int input_count = InputCount();
154 : OutOfLineInputs* outline = nullptr;
155 23243182 : if (inline_count != kOutlineMarker) {
156 : // switch to out of line inputs.
157 11573441 : outline = OutOfLineInputs::New(zone, input_count * 2 + 3);
158 11573443 : outline->node_ = this;
159 11573443 : outline->ExtractFrom(GetUsePtr(0), GetInputPtr(0), input_count);
160 23146906 : bit_field_ = InlineCountField::update(bit_field_, kOutlineMarker);
161 11573453 : inputs_.outline_ = outline;
162 : } else {
163 : // use current out of line inputs.
164 11669741 : outline = inputs_.outline_;
165 11669741 : if (input_count >= outline->capacity_) {
166 : // out of space in out-of-line inputs.
167 147931 : outline = OutOfLineInputs::New(zone, input_count * 2 + 3);
168 147931 : outline->node_ = this;
169 147931 : outline->ExtractFrom(GetUsePtr(0), GetInputPtr(0), input_count);
170 147931 : inputs_.outline_ = outline;
171 : }
172 : }
173 23243194 : outline->count_++;
174 23243194 : *GetInputPtr(input_count) = new_to;
175 : Use* use = GetUsePtr(input_count);
176 23243194 : use->bit_field_ = Use::InputIndexField::encode(input_count) |
177 23243194 : Use::InlineField::encode(false);
178 : new_to->AppendUse(use);
179 : }
180 : Verify();
181 24361201 : }
182 :
183 :
184 12960046 : void Node::InsertInput(Zone* zone, int index, Node* new_to) {
185 : DCHECK_NOT_NULL(zone);
186 : DCHECK_LE(0, index);
187 : DCHECK_LT(index, InputCount());
188 25920092 : AppendInput(zone, InputAt(InputCount() - 1));
189 76447561 : for (int i = InputCount() - 1; i > index; --i) {
190 101054962 : ReplaceInput(i, InputAt(i - 1));
191 : }
192 12960060 : ReplaceInput(index, new_to);
193 : Verify();
194 12960064 : }
195 :
196 496 : void Node::InsertInputs(Zone* zone, int index, int count) {
197 : DCHECK_NOT_NULL(zone);
198 : DCHECK_LE(0, index);
199 : DCHECK_LT(0, count);
200 : DCHECK_LT(index, InputCount());
201 1493 : for (int i = 0; i < count; i++) {
202 1994 : AppendInput(zone, InputAt(Max(InputCount() - count, 0)));
203 : }
204 4660 : for (int i = InputCount() - count - 1; i >= Max(index, count); --i) {
205 3668 : ReplaceInput(i, InputAt(i - count));
206 : }
207 997 : for (int i = 0; i < count; i++) {
208 997 : ReplaceInput(index + i, nullptr);
209 : }
210 : Verify();
211 496 : }
212 :
213 581434 : void Node::RemoveInput(int index) {
214 : DCHECK_LE(0, index);
215 : DCHECK_LT(index, InputCount());
216 1442593 : for (; index < InputCount() - 1; ++index) {
217 559442 : ReplaceInput(index, InputAt(index + 1));
218 : }
219 581438 : TrimInputCount(InputCount() - 1);
220 : Verify();
221 581438 : }
222 :
223 :
224 15947573 : void Node::ClearInputs(int start, int count) {
225 : Node** input_ptr = GetInputPtr(start);
226 : Use* use_ptr = GetUsePtr(start);
227 64452399 : while (count-- > 0) {
228 : DCHECK_EQ(input_ptr, use_ptr->input_ptr());
229 32557253 : Node* input = *input_ptr;
230 32557253 : *input_ptr = nullptr;
231 32557253 : if (input) input->RemoveUse(use_ptr);
232 32557253 : input_ptr++;
233 32557253 : use_ptr--;
234 : }
235 : Verify();
236 15947573 : }
237 :
238 :
239 28503054 : void Node::NullAllInputs() { ClearInputs(0, InputCount()); }
240 :
241 :
242 3481602 : void Node::TrimInputCount(int new_input_count) {
243 : int current_count = InputCount();
244 : DCHECK_LE(new_input_count, current_count);
245 3570974 : if (new_input_count == current_count) return; // Nothing to do.
246 1696109 : ClearInputs(new_input_count, current_count - new_input_count);
247 1696121 : if (has_inline_inputs()) {
248 1996110 : bit_field_ = InlineCountField::update(bit_field_, new_input_count);
249 : } else {
250 698066 : inputs_.outline_->count_ = new_input_count;
251 : }
252 : }
253 :
254 :
255 87142 : int Node::UseCount() const {
256 : int use_count = 0;
257 96253 : for (const Use* use = first_use_; use; use = use->next) {
258 9111 : ++use_count;
259 : }
260 87142 : return use_count;
261 : }
262 :
263 :
264 6254687 : void Node::ReplaceUses(Node* that) {
265 : DCHECK(this->first_use_ == nullptr || this->first_use_->prev == nullptr);
266 : DCHECK(that->first_use_ == nullptr || that->first_use_->prev == nullptr);
267 :
268 : // Update the pointers to {this} to point to {that}.
269 : Use* last_use = nullptr;
270 15078260 : for (Use* use = this->first_use_; use; use = use->next) {
271 8823573 : *use->input_ptr() = that;
272 : last_use = use;
273 : }
274 6254687 : if (last_use) {
275 : // Concat the use list of {this} and {that}.
276 4695281 : last_use->next = that->first_use_;
277 4695281 : if (that->first_use_) that->first_use_->prev = last_use;
278 4695281 : that->first_use_ = this->first_use_;
279 : }
280 6254687 : first_use_ = nullptr;
281 6254687 : }
282 :
283 :
284 82489 : bool Node::OwnedBy(Node const* owner1, Node const* owner2) const {
285 : unsigned mask = 0;
286 241356 : for (Use* use = first_use_; use; use = use->next) {
287 : Node* from = use->from();
288 226071 : if (from == owner1) {
289 80020 : mask |= 1;
290 146051 : } else if (from == owner2) {
291 78847 : mask |= 2;
292 : } else {
293 : return false;
294 : }
295 : }
296 15285 : return mask == 3;
297 : }
298 :
299 0 : void Node::Print() const {
300 0 : StdoutStream os;
301 0 : Print(os);
302 0 : }
303 :
304 0 : void Node::Print(std::ostream& os) const {
305 0 : os << *this << std::endl;
306 0 : for (Node* input : this->inputs()) {
307 0 : os << " " << *input << std::endl;
308 : }
309 0 : }
310 :
311 394 : std::ostream& operator<<(std::ostream& os, const Node& n) {
312 394 : os << n.id() << ": " << *n.op();
313 394 : if (n.InputCount() > 0) {
314 296 : os << "(";
315 1926 : for (int i = 0; i < n.InputCount(); ++i) {
316 667 : if (i != 0) os << ", ";
317 667 : if (n.InputAt(i)) {
318 667 : os << n.InputAt(i)->id();
319 : } else {
320 0 : os << "null";
321 : }
322 : }
323 296 : os << ")";
324 : }
325 394 : return os;
326 : }
327 :
328 0 : Node::Node(NodeId id, const Operator* op, int inline_count, int inline_capacity)
329 : : op_(op),
330 : mark_(0),
331 450028740 : bit_field_(IdField::encode(id) | InlineCountField::encode(inline_count) |
332 149994662 : InlineCapacityField::encode(inline_capacity)),
333 450118248 : first_use_(nullptr) {
334 : // Inputs must either be out of line or within the inline capacity.
335 : DCHECK_GE(kMaxInlineCapacity, inline_capacity);
336 : DCHECK(inline_count == kOutlineMarker || inline_count <= inline_capacity);
337 0 : }
338 :
339 :
340 78900793 : void Node::AppendUse(Use* use) {
341 : DCHECK(first_use_ == nullptr || first_use_->prev == nullptr);
342 : DCHECK_EQ(this, *use->input_ptr());
343 456693183 : use->next = first_use_;
344 456693183 : use->prev = nullptr;
345 456693183 : if (first_use_) first_use_->prev = use;
346 456693183 : first_use_ = use;
347 78900793 : }
348 :
349 :
350 124538734 : void Node::RemoveUse(Use* use) {
351 : DCHECK(first_use_ == nullptr || first_use_->prev == nullptr);
352 243641814 : if (use->prev) {
353 : DCHECK_NE(first_use_, use);
354 155507031 : use->prev->next = use->next;
355 : } else {
356 : DCHECK_EQ(first_use_, use);
357 88134783 : first_use_ = use->next;
358 : }
359 243641814 : if (use->next) {
360 150526053 : use->next->prev = use->prev;
361 : }
362 124538734 : }
363 :
364 :
365 : #if DEBUG
366 : void Node::Verify() {
367 : // Check basic sanity of input data structures.
368 : fflush(stdout);
369 : int count = this->InputCount();
370 : // Avoid quadratic explosion for mega nodes; only verify if the input
371 : // count is less than 200 or is a round number of 100s.
372 : if (count > 200 && count % 100) return;
373 :
374 : for (int i = 0; i < count; i++) {
375 : DCHECK_EQ(i, this->GetUsePtr(i)->input_index());
376 : DCHECK_EQ(this->GetInputPtr(i), this->GetUsePtr(i)->input_ptr());
377 : DCHECK_EQ(count, this->InputCount());
378 : }
379 : { // Direct input iteration.
380 : int index = 0;
381 : for (Node* input : this->inputs()) {
382 : DCHECK_EQ(this->InputAt(index), input);
383 : index++;
384 : }
385 : DCHECK_EQ(count, index);
386 : DCHECK_EQ(this->InputCount(), index);
387 : }
388 : { // Input edge iteration.
389 : int index = 0;
390 : for (Edge edge : this->input_edges()) {
391 : DCHECK_EQ(edge.from(), this);
392 : DCHECK_EQ(index, edge.index());
393 : DCHECK_EQ(this->InputAt(index), edge.to());
394 : index++;
395 : }
396 : DCHECK_EQ(count, index);
397 : DCHECK_EQ(this->InputCount(), index);
398 : }
399 : }
400 : #endif
401 :
402 0 : Node::InputEdges::iterator Node::InputEdges::iterator::operator++(int n) {
403 0 : iterator result(*this);
404 : ++(*this);
405 0 : return result;
406 : }
407 :
408 :
409 0 : Node::Inputs::const_iterator Node::Inputs::const_iterator::operator++(int n) {
410 0 : const_iterator result(*this);
411 : ++(*this);
412 0 : return result;
413 : }
414 :
415 :
416 0 : Node::UseEdges::iterator Node::UseEdges::iterator::operator++(int n) {
417 0 : iterator result(*this);
418 : ++(*this);
419 0 : return result;
420 : }
421 :
422 :
423 37576 : bool Node::UseEdges::empty() const { return begin() == end(); }
424 :
425 :
426 177399 : Node::Uses::const_iterator Node::Uses::const_iterator::operator++(int n) {
427 177399 : const_iterator result(*this);
428 : ++(*this);
429 177399 : return result;
430 : }
431 :
432 :
433 2915856 : bool Node::Uses::empty() const { return begin() == end(); }
434 :
435 : } // namespace compiler
436 : } // namespace internal
437 183867 : } // namespace v8
|
