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 0 : Node::OutOfLineInputs* Node::OutOfLineInputs::New(Zone* zone, int capacity) {
12 : size_t size =
13 13653785 : sizeof(OutOfLineInputs) + capacity * (sizeof(Node*) + sizeof(Use));
14 13653785 : intptr_t raw_buffer = reinterpret_cast<intptr_t>(zone->New(size));
15 : Node::OutOfLineInputs* outline =
16 13653793 : reinterpret_cast<OutOfLineInputs*>(raw_buffer + capacity * sizeof(Use));
17 13653793 : outline->capacity_ = capacity;
18 13653793 : outline->count_ = 0;
19 0 : return outline;
20 : }
21 :
22 :
23 13622539 : 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 13622539 : Use* new_use_ptr = reinterpret_cast<Use*>(this) - 1;
28 : Node** new_input_ptr = inputs();
29 101667035 : for (int current = 0; current < count; current++) {
30 : new_use_ptr->bit_field_ =
31 88044496 : 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 44022248 : Node* old_to = *old_input_ptr;
35 44022248 : if (old_to) {
36 44022248 : *old_input_ptr = nullptr;
37 : old_to->RemoveUse(old_use_ptr);
38 44022248 : *new_input_ptr = old_to;
39 : old_to->AppendUse(new_use_ptr);
40 : } else {
41 0 : *new_input_ptr = nullptr;
42 : }
43 44022248 : old_input_ptr++;
44 44022248 : new_input_ptr++;
45 44022248 : old_use_ptr--;
46 44022248 : new_use_ptr--;
47 : }
48 13622539 : this->count_ = count;
49 13622539 : }
50 :
51 :
52 150948162 : 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 150948162 : if (input_count > kMaxInlineCapacity) {
70 : // Allocate out-of-line inputs.
71 : int capacity =
72 31281 : has_extensible_inputs ? input_count + kMaxInlineCapacity : input_count;
73 : OutOfLineInputs* outline = OutOfLineInputs::New(zone, capacity);
74 :
75 : // Allocate node, with space for OutOfLineInputs pointer.
76 31281 : void* node_buffer = zone->New(sizeof(Node) + sizeof(OutOfLineInputs*));
77 : node = new (node_buffer) Node(id, op, kOutlineMarker, 0);
78 : node->set_outline_inputs(outline);
79 :
80 40686 : outline->node_ = node;
81 40686 : outline->count_ = input_count;
82 :
83 : input_ptr = outline->inputs();
84 : use_ptr = reinterpret_cast<Use*>(outline);
85 : is_inline = false;
86 : } else {
87 : // Allocate node with inline inputs. Capacity must be at least 1 so that
88 : // an OutOfLineInputs pointer can be stored when inputs are added later.
89 301833762 : int capacity = std::max(1, input_count);
90 150916881 : if (has_extensible_inputs) {
91 1225198 : const int max = kMaxInlineCapacity;
92 2450396 : capacity = std::min(input_count + 3, max);
93 : }
94 :
95 150916881 : size_t size = sizeof(Node) + capacity * (sizeof(Node*) + sizeof(Use));
96 150916881 : intptr_t raw_buffer = reinterpret_cast<intptr_t>(zone->New(size));
97 : void* node_buffer =
98 150914643 : reinterpret_cast<void*>(raw_buffer + capacity * sizeof(Use));
99 :
100 : node = new (node_buffer) Node(id, op, input_count, capacity);
101 : input_ptr = node->inline_inputs();
102 : use_ptr = reinterpret_cast<Use*>(node);
103 : is_inline = true;
104 : }
105 :
106 : // Initialize the input pointers and the uses.
107 689393735 : for (int current = 0; current < input_count; ++current) {
108 269219203 : Node* to = *inputs++;
109 269219203 : input_ptr[current] = to;
110 269219203 : Use* use = use_ptr - 1 - current;
111 538438406 : use->bit_field_ = Use::InputIndexField::encode(current) |
112 269219203 : Use::InlineField::encode(is_inline);
113 : to->AppendUse(use);
114 : }
115 : node->Verify();
116 150955329 : return node;
117 : }
118 :
119 :
120 2405684 : Node* Node::Clone(Zone* zone, NodeId id, const Node* node) {
121 : int const input_count = node->InputCount();
122 : Node* const* const inputs = node->has_inline_inputs()
123 : ? node->inline_inputs()
124 2405684 : : node->outline_inputs()->inputs();
125 2405684 : Node* const clone = New(zone, id, node->op(), input_count, inputs, false);
126 : clone->set_type(node->type());
127 2405680 : return clone;
128 : }
129 :
130 :
131 12179877 : void Node::Kill() {
132 : DCHECK_NOT_NULL(op());
133 12179877 : NullAllInputs();
134 : DCHECK(uses().empty());
135 12180403 : }
136 :
137 :
138 27121755 : void Node::AppendInput(Zone* zone, Node* new_to) {
139 : DCHECK_NOT_NULL(zone);
140 : DCHECK_NOT_NULL(new_to);
141 :
142 54243510 : int inline_count = InlineCountField::decode(bit_field_);
143 27121755 : int inline_capacity = InlineCapacityField::decode(bit_field_);
144 27121755 : if (inline_count < inline_capacity) {
145 : // Append inline input.
146 2813188 : bit_field_ = InlineCountField::update(bit_field_, inline_count + 1);
147 1406594 : *GetInputPtr(inline_count) = new_to;
148 : Use* use = GetUsePtr(inline_count);
149 1406594 : use->bit_field_ = Use::InputIndexField::encode(inline_count) |
150 1406594 : Use::InlineField::encode(true);
151 : new_to->AppendUse(use);
152 : } else {
153 : // Append out-of-line input.
154 : int input_count = InputCount();
155 : OutOfLineInputs* outline = nullptr;
156 25715161 : if (inline_count != kOutlineMarker) {
157 : // switch to out of line inputs.
158 13473347 : outline = OutOfLineInputs::New(zone, input_count * 2 + 3);
159 13473355 : outline->node_ = this;
160 13473355 : outline->ExtractFrom(GetUsePtr(0), GetInputPtr(0), input_count);
161 26946756 : bit_field_ = InlineCountField::update(bit_field_, kOutlineMarker);
162 : set_outline_inputs(outline);
163 : } else {
164 : // use current out of line inputs.
165 : outline = outline_inputs();
166 12241814 : if (input_count >= outline->capacity_) {
167 : // out of space in out-of-line inputs.
168 149157 : outline = OutOfLineInputs::New(zone, input_count * 2 + 3);
169 149157 : outline->node_ = this;
170 149157 : outline->ExtractFrom(GetUsePtr(0), GetInputPtr(0), input_count);
171 : set_outline_inputs(outline);
172 : }
173 : }
174 25715192 : outline->count_++;
175 25715192 : *GetInputPtr(input_count) = new_to;
176 : Use* use = GetUsePtr(input_count);
177 25715192 : use->bit_field_ = Use::InputIndexField::encode(input_count) |
178 25715192 : Use::InlineField::encode(false);
179 : new_to->AppendUse(use);
180 : }
181 : Verify();
182 27121786 : }
183 :
184 :
185 15105100 : void Node::InsertInput(Zone* zone, int index, Node* new_to) {
186 : DCHECK_NOT_NULL(zone);
187 : DCHECK_LE(0, index);
188 : DCHECK_LT(index, InputCount());
189 30210200 : AppendInput(zone, InputAt(InputCount() - 1));
190 72794473 : for (int i = InputCount() - 1; i > index; --i) {
191 115378812 : ReplaceInput(i, InputAt(i - 1));
192 : }
193 15105067 : ReplaceInput(index, new_to);
194 : Verify();
195 15105094 : }
196 :
197 493 : void Node::InsertInputs(Zone* zone, int index, int count) {
198 : DCHECK_NOT_NULL(zone);
199 : DCHECK_LE(0, index);
200 : DCHECK_LT(0, count);
201 : DCHECK_LT(index, InputCount());
202 2475 : for (int i = 0; i < count; i++) {
203 1982 : AppendInput(zone, InputAt(Max(InputCount() - count, 0)));
204 : }
205 4630 : for (int i = InputCount() - count - 1; i >= Max(index, count); --i) {
206 3644 : ReplaceInput(i, InputAt(i - count));
207 : }
208 2475 : for (int i = 0; i < count; i++) {
209 991 : ReplaceInput(index + i, nullptr);
210 : }
211 : Verify();
212 493 : }
213 :
214 600352 : void Node::RemoveInput(int index) {
215 : DCHECK_LE(0, index);
216 : DCHECK_LT(index, InputCount());
217 1115658 : for (; index < InputCount() - 1; ++index) {
218 515306 : ReplaceInput(index, InputAt(index + 1));
219 : }
220 600352 : TrimInputCount(InputCount() - 1);
221 : Verify();
222 600352 : }
223 :
224 :
225 15193491 : void Node::ClearInputs(int start, int count) {
226 : Node** input_ptr = GetInputPtr(start);
227 : Use* use_ptr = GetUsePtr(start);
228 73510555 : while (count-- > 0) {
229 : DCHECK_EQ(input_ptr, use_ptr->input_ptr());
230 29158532 : Node* input = *input_ptr;
231 29158532 : *input_ptr = nullptr;
232 29158532 : if (input) input->RemoveUse(use_ptr);
233 29158532 : input_ptr++;
234 29158532 : use_ptr--;
235 : }
236 : Verify();
237 15193491 : }
238 :
239 :
240 26973578 : void Node::NullAllInputs() { ClearInputs(0, InputCount()); }
241 :
242 :
243 1803135 : void Node::TrimInputCount(int new_input_count) {
244 : int current_count = InputCount();
245 : DCHECK_LE(new_input_count, current_count);
246 1803135 : if (new_input_count == current_count) return; // Nothing to do.
247 1706568 : ClearInputs(new_input_count, current_count - new_input_count);
248 1706587 : if (has_inline_inputs()) {
249 2007306 : bit_field_ = InlineCountField::update(bit_field_, new_input_count);
250 : } else {
251 702934 : outline_inputs()->count_ = new_input_count;
252 : }
253 : }
254 :
255 :
256 97218 : int Node::UseCount() const {
257 : int use_count = 0;
258 106659 : for (const Use* use = first_use_; use; use = use->next) {
259 9441 : ++use_count;
260 : }
261 97218 : return use_count;
262 : }
263 :
264 :
265 6704985 : void Node::ReplaceUses(Node* that) {
266 : DCHECK(this->first_use_ == nullptr || this->first_use_->prev == nullptr);
267 : DCHECK(that->first_use_ == nullptr || that->first_use_->prev == nullptr);
268 :
269 : // Update the pointers to {this} to point to {that}.
270 : Use* last_use = nullptr;
271 16307598 : for (Use* use = this->first_use_; use; use = use->next) {
272 9602613 : *use->input_ptr() = that;
273 : last_use = use;
274 : }
275 6704985 : if (last_use) {
276 : // Concat the use list of {this} and {that}.
277 5229547 : last_use->next = that->first_use_;
278 5229547 : if (that->first_use_) that->first_use_->prev = last_use;
279 5229547 : that->first_use_ = this->first_use_;
280 : }
281 6704985 : first_use_ = nullptr;
282 6704985 : }
283 :
284 :
285 77010 : bool Node::OwnedBy(Node const* owner1, Node const* owner2) const {
286 : unsigned mask = 0;
287 224953 : for (Use* use = first_use_; use; use = use->next) {
288 : Node* from = use->from();
289 216098 : if (from == owner1) {
290 74531 : mask |= 1;
291 141567 : } else if (from == owner2) {
292 73412 : mask |= 2;
293 : } else {
294 : return false;
295 : }
296 : }
297 8855 : return mask == 3;
298 : }
299 :
300 0 : void Node::Print() const {
301 0 : StdoutStream os;
302 0 : Print(os);
303 0 : }
304 :
305 0 : void Node::Print(std::ostream& os) const {
306 0 : os << *this << std::endl;
307 0 : for (Node* input : this->inputs()) {
308 0 : os << " " << *input << std::endl;
309 : }
310 0 : }
311 :
312 410 : std::ostream& operator<<(std::ostream& os, const Node& n) {
313 410 : os << n.id() << ": " << *n.op();
314 410 : if (n.InputCount() > 0) {
315 282 : os << "(";
316 1514 : for (int i = 0; i < n.InputCount(); ++i) {
317 616 : if (i != 0) os << ", ";
318 616 : if (n.InputAt(i)) {
319 : os << n.InputAt(i)->id();
320 : } else {
321 0 : os << "null";
322 : }
323 : }
324 282 : os << ")";
325 : }
326 410 : return os;
327 : }
328 :
329 0 : Node::Node(NodeId id, const Operator* op, int inline_count, int inline_capacity)
330 : : op_(op),
331 : mark_(0),
332 150955329 : bit_field_(IdField::encode(id) | InlineCountField::encode(inline_count) |
333 150914643 : InlineCapacityField::encode(inline_capacity)),
334 452865987 : first_use_(nullptr) {
335 : // Inputs must either be out of line or within the inline capacity.
336 : DCHECK_GE(kMaxInlineCapacity, inline_capacity);
337 : DCHECK(inline_count == kOutlineMarker || inline_count <= inline_capacity);
338 0 : }
339 :
340 :
341 82650921 : void Node::AppendUse(Use* use) {
342 : DCHECK(first_use_ == nullptr || first_use_->prev == nullptr);
343 : DCHECK_EQ(this, *use->input_ptr());
344 479829768 : use->next = first_use_;
345 479829768 : use->prev = nullptr;
346 479829768 : if (first_use_) first_use_->prev = use;
347 479829768 : first_use_ = use;
348 82650921 : }
349 :
350 :
351 125380112 : void Node::RemoveUse(Use* use) {
352 : DCHECK(first_use_ == nullptr || first_use_->prev == nullptr);
353 254963935 : if (use->prev) {
354 : DCHECK_NE(first_use_, use);
355 164713077 : use->prev->next = use->next;
356 : } else {
357 : DCHECK_EQ(first_use_, use);
358 90250858 : first_use_ = use->next;
359 : }
360 254963935 : if (use->next) {
361 158692605 : use->next->prev = use->prev;
362 : }
363 125380112 : }
364 :
365 :
366 : #if DEBUG
367 : void Node::Verify() {
368 : // Check basic sanity of input data structures.
369 : fflush(stdout);
370 : int count = this->InputCount();
371 : // Avoid quadratic explosion for mega nodes; only verify if the input
372 : // count is less than 200 or is a round number of 100s.
373 : if (count > 200 && count % 100) return;
374 :
375 : for (int i = 0; i < count; i++) {
376 : DCHECK_EQ(i, this->GetUsePtr(i)->input_index());
377 : DCHECK_EQ(this->GetInputPtr(i), this->GetUsePtr(i)->input_ptr());
378 : DCHECK_EQ(count, this->InputCount());
379 : }
380 : { // Direct input iteration.
381 : int index = 0;
382 : for (Node* input : this->inputs()) {
383 : DCHECK_EQ(this->InputAt(index), input);
384 : index++;
385 : }
386 : DCHECK_EQ(count, index);
387 : DCHECK_EQ(this->InputCount(), index);
388 : }
389 : { // Input edge iteration.
390 : int index = 0;
391 : for (Edge edge : this->input_edges()) {
392 : DCHECK_EQ(edge.from(), this);
393 : DCHECK_EQ(index, edge.index());
394 : DCHECK_EQ(this->InputAt(index), edge.to());
395 : index++;
396 : }
397 : DCHECK_EQ(count, index);
398 : DCHECK_EQ(this->InputCount(), index);
399 : }
400 : }
401 : #endif
402 :
403 0 : Node::InputEdges::iterator Node::InputEdges::iterator::operator++(int n) {
404 0 : iterator result(*this);
405 : ++(*this);
406 0 : return result;
407 : }
408 :
409 :
410 0 : Node::Inputs::const_iterator Node::Inputs::const_iterator::operator++(int n) {
411 0 : const_iterator result(*this);
412 : ++(*this);
413 0 : return result;
414 : }
415 :
416 :
417 0 : Node::UseEdges::iterator Node::UseEdges::iterator::operator++(int n) {
418 0 : iterator result(*this);
419 : ++(*this);
420 0 : return result;
421 : }
422 :
423 :
424 37598 : bool Node::UseEdges::empty() const { return begin() == end(); }
425 :
426 :
427 182072 : Node::Uses::const_iterator Node::Uses::const_iterator::operator++(int n) {
428 182072 : const_iterator result(*this);
429 : ++(*this);
430 182072 : return result;
431 : }
432 :
433 :
434 2428266 : bool Node::Uses::empty() const { return begin() == end(); }
435 :
436 : } // namespace compiler
437 : } // namespace internal
438 121996 : } // namespace v8
|
