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 6278820 : Node::OutOfLineInputs* Node::OutOfLineInputs::New(Zone* zone, int capacity) {
12 : size_t size =
13 6278820 : sizeof(OutOfLineInputs) + capacity * (sizeof(Node*) + sizeof(Use));
14 6278820 : intptr_t raw_buffer = reinterpret_cast<intptr_t>(zone->New(size));
15 : Node::OutOfLineInputs* outline =
16 6278826 : reinterpret_cast<OutOfLineInputs*>(raw_buffer + capacity * sizeof(Use));
17 6278826 : outline->capacity_ = capacity;
18 6278826 : outline->count_ = 0;
19 6278826 : return outline;
20 : }
21 :
22 :
23 6245752 : 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 6245752 : Use* new_use_ptr = reinterpret_cast<Use*>(this) - 1;
28 6245752 : Node** new_input_ptr = inputs_;
29 34828525 : for (int current = 0; current < count; current++) {
30 : new_use_ptr->bit_field_ =
31 57165546 : 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 28582773 : Node* old_to = *old_input_ptr;
35 28582773 : if (old_to) {
36 28582773 : *old_input_ptr = nullptr;
37 : old_to->RemoveUse(old_use_ptr);
38 28582773 : *new_input_ptr = old_to;
39 : old_to->AppendUse(new_use_ptr);
40 : } else {
41 0 : *new_input_ptr = nullptr;
42 : }
43 28582773 : old_input_ptr++;
44 28582773 : new_input_ptr++;
45 28582773 : old_use_ptr--;
46 28582773 : new_use_ptr--;
47 : }
48 6245752 : this->count_ = count;
49 6245752 : }
50 :
51 :
52 112379313 : 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 : V8_Fatal(__FILE__, __LINE__, "Node::New() Error: #%d:%s[%d] is nullptr",
64 : static_cast<int>(id), op->mnemonic(), i);
65 : }
66 : }
67 : #endif
68 :
69 112379313 : if (input_count > kMaxInlineCapacity) {
70 : // Allocate out-of-line inputs.
71 : int capacity =
72 33072 : has_extensible_inputs ? input_count + kMaxInlineCapacity : input_count;
73 33072 : OutOfLineInputs* outline = OutOfLineInputs::New(zone, capacity);
74 :
75 : // Allocate node.
76 33072 : void* node_buffer = zone->New(sizeof(Node));
77 : node = new (node_buffer) Node(id, op, kOutlineMarker, 0);
78 34750 : node->inputs_.outline_ = outline;
79 :
80 34750 : outline->node_ = node;
81 34750 : outline->count_ = input_count;
82 :
83 34750 : 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 112346241 : if (has_extensible_inputs) {
90 3124847 : const int max = kMaxInlineCapacity;
91 6249694 : capacity = std::min(input_count + 3, max);
92 : }
93 :
94 112346241 : size_t size = sizeof(Node) + capacity * (sizeof(Node*) + sizeof(Use));
95 112346241 : intptr_t raw_buffer = reinterpret_cast<intptr_t>(zone->New(size));
96 : void* node_buffer =
97 112342565 : reinterpret_cast<void*>(raw_buffer + capacity * sizeof(Use));
98 :
99 : node = new (node_buffer) Node(id, op, input_count, capacity);
100 112342565 : 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 307821236 : for (int current = 0; current < input_count; ++current) {
107 195443921 : Node* to = *inputs++;
108 195443921 : input_ptr[current] = to;
109 195443921 : Use* use = use_ptr - 1 - current;
110 390887842 : use->bit_field_ = Use::InputIndexField::encode(current) |
111 195443921 : Use::InlineField::encode(is_inline);
112 : to->AppendUse(use);
113 : }
114 : node->Verify();
115 112377315 : return node;
116 : }
117 :
118 :
119 8165705 : 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 2721903 : : node->inputs_.outline_->inputs_;
124 2721903 : Node* const clone = New(zone, id, node->op(), input_count, inputs, false);
125 : clone->set_type(node->type());
126 2721899 : return clone;
127 : }
128 :
129 :
130 11179373 : void Node::Kill() {
131 : DCHECK_NOT_NULL(op());
132 11179373 : NullAllInputs();
133 : DCHECK(uses().empty());
134 11179438 : }
135 :
136 :
137 17749179 : void Node::AppendInput(Zone* zone, Node* new_to) {
138 : DCHECK_NOT_NULL(zone);
139 : DCHECK_NOT_NULL(new_to);
140 :
141 35498358 : int inline_count = InlineCountField::decode(bit_field_);
142 17749179 : int inline_capacity = InlineCapacityField::decode(bit_field_);
143 17749179 : if (inline_count < inline_capacity) {
144 : // Append inline input.
145 4664144 : bit_field_ = InlineCountField::update(bit_field_, inline_count + 1);
146 2332072 : *GetInputPtr(inline_count) = new_to;
147 : Use* use = GetUsePtr(inline_count);
148 2332072 : use->bit_field_ = Use::InputIndexField::encode(inline_count) |
149 2332072 : 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 15417107 : if (inline_count != kOutlineMarker) {
156 : // switch to out of line inputs.
157 5994914 : outline = OutOfLineInputs::New(zone, input_count * 2 + 3);
158 5994895 : outline->node_ = this;
159 5994895 : outline->ExtractFrom(GetUsePtr(0), GetInputPtr(0), input_count);
160 11989834 : bit_field_ = InlineCountField::update(bit_field_, kOutlineMarker);
161 5994917 : inputs_.outline_ = outline;
162 : } else {
163 : // use current out of line inputs.
164 9422193 : outline = inputs_.outline_;
165 9422193 : if (input_count >= outline->capacity_) {
166 : // out of space in out-of-line inputs.
167 250840 : outline = OutOfLineInputs::New(zone, input_count * 2 + 3);
168 250840 : outline->node_ = this;
169 250840 : outline->ExtractFrom(GetUsePtr(0), GetInputPtr(0), input_count);
170 250839 : inputs_.outline_ = outline;
171 : }
172 : }
173 15417109 : outline->count_++;
174 15417109 : *GetInputPtr(input_count) = new_to;
175 : Use* use = GetUsePtr(input_count);
176 15417109 : use->bit_field_ = Use::InputIndexField::encode(input_count) |
177 15417109 : Use::InlineField::encode(false);
178 : new_to->AppendUse(use);
179 : }
180 : Verify();
181 17749181 : }
182 :
183 :
184 14883840 : 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 29767680 : AppendInput(zone, InputAt(InputCount() - 1));
189 83171262 : for (int i = InputCount() - 1; i > index; --i) {
190 106807524 : ReplaceInput(i, InputAt(i - 1));
191 : }
192 14883774 : ReplaceInput(index, new_to);
193 : Verify();
194 14883737 : }
195 :
196 44153 : 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 132466 : for (int i = 0; i < count; i++) {
202 176626 : AppendInput(zone, InputAt(Max(InputCount() - count, 0)));
203 : }
204 441110 : for (int i = InputCount() - count - 1; i >= Max(index, count); --i) {
205 352804 : ReplaceInput(i, InputAt(i - count));
206 : }
207 88313 : for (int i = 0; i < count; i++) {
208 88313 : ReplaceInput(index + i, nullptr);
209 : }
210 : Verify();
211 44153 : }
212 :
213 234265 : void Node::RemoveInput(int index) {
214 : DCHECK_LE(0, index);
215 : DCHECK_LT(index, InputCount());
216 780688 : for (; index < InputCount() - 1; ++index) {
217 624314 : ReplaceInput(index, InputAt(index + 1));
218 : }
219 234266 : TrimInputCount(InputCount() - 1);
220 : Verify();
221 234266 : }
222 :
223 :
224 13412837 : void Node::ClearInputs(int start, int count) {
225 : Node** input_ptr = GetInputPtr(start);
226 : Use* use_ptr = GetUsePtr(start);
227 58937359 : while (count-- > 0) {
228 : DCHECK_EQ(input_ptr, use_ptr->input_ptr());
229 32111685 : Node* input = *input_ptr;
230 32111685 : *input_ptr = nullptr;
231 32111685 : if (input) input->RemoveUse(use_ptr);
232 32111685 : input_ptr++;
233 32111685 : use_ptr--;
234 : }
235 : Verify();
236 13412837 : }
237 :
238 :
239 23053682 : void Node::NullAllInputs() { ClearInputs(0, InputCount()); }
240 :
241 :
242 3774724 : void Node::TrimInputCount(int new_input_count) {
243 : int current_count = InputCount();
244 : DCHECK_LE(new_input_count, current_count);
245 3777043 : if (new_input_count == current_count) return; // Nothing to do.
246 1886201 : ClearInputs(new_input_count, current_count - new_input_count);
247 1886204 : if (has_inline_inputs()) {
248 2994214 : bit_field_ = InlineCountField::update(bit_field_, new_input_count);
249 : } else {
250 389097 : inputs_.outline_->count_ = new_input_count;
251 : }
252 : }
253 :
254 :
255 166339 : int Node::UseCount() const {
256 : int use_count = 0;
257 219575 : for (const Use* use = first_use_; use; use = use->next) {
258 53236 : ++use_count;
259 : }
260 166339 : return use_count;
261 : }
262 :
263 :
264 2357788 : 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 5047224 : for (Use* use = this->first_use_; use; use = use->next) {
271 2689436 : *use->input_ptr() = that;
272 : last_use = use;
273 : }
274 2357788 : if (last_use) {
275 : // Concat the use list of {this} and {that}.
276 2278071 : last_use->next = that->first_use_;
277 2278071 : if (that->first_use_) that->first_use_->prev = last_use;
278 2278071 : that->first_use_ = this->first_use_;
279 : }
280 2357788 : first_use_ = nullptr;
281 2357788 : }
282 :
283 :
284 52063 : bool Node::OwnedBy(Node const* owner1, Node const* owner2) const {
285 : unsigned mask = 0;
286 141383 : for (Use* use = first_use_; use; use = use->next) {
287 : Node* from = use->from();
288 133517 : if (from == owner1) {
289 47259 : mask |= 1;
290 86258 : } else if (from == owner2) {
291 42061 : mask |= 2;
292 : } else {
293 : return false;
294 : }
295 : }
296 7866 : return mask == 3;
297 : }
298 :
299 680037 : bool Node::OwnedByAddressingOperand() const {
300 1638363 : for (Use* use = first_use_; use; use = use->next) {
301 1100877 : Node* from = use->from();
302 1610510 : if (from->opcode() != IrOpcode::kLoad &&
303 : // If {from} is store, make sure it does not use {this} as value
304 172532 : (from->opcode() != IrOpcode::kStore || from->InputAt(2) == this) &&
305 1444702 : from->opcode() != IrOpcode::kInt32Add &&
306 : from->opcode() != IrOpcode::kInt64Add) {
307 : return false;
308 : }
309 : }
310 : return true;
311 : }
312 :
313 0 : void Node::Print() const {
314 0 : OFStream os(stdout);
315 0 : os << *this << std::endl;
316 0 : for (Node* input : this->inputs()) {
317 0 : os << " " << *input << std::endl;
318 0 : }
319 0 : }
320 :
321 84 : std::ostream& operator<<(std::ostream& os, const Node& n) {
322 84 : os << n.id() << ": " << *n.op();
323 84 : if (n.InputCount() > 0) {
324 56 : os << "(";
325 294 : for (int i = 0; i < n.InputCount(); ++i) {
326 91 : if (i != 0) os << ", ";
327 91 : if (n.InputAt(i)) {
328 91 : os << n.InputAt(i)->id();
329 : } else {
330 0 : os << "null";
331 : }
332 : }
333 56 : os << ")";
334 : }
335 84 : return os;
336 : }
337 :
338 0 : Node::Node(NodeId id, const Operator* op, int inline_count, int inline_capacity)
339 : : op_(op),
340 : type_(nullptr),
341 : mark_(0),
342 337062445 : bit_field_(IdField::encode(id) | InlineCountField::encode(inline_count) |
343 112342565 : InlineCapacityField::encode(inline_capacity)),
344 224754630 : first_use_(nullptr) {
345 : // Inputs must either be out of line or within the inline capacity.
346 : DCHECK(inline_capacity <= kMaxInlineCapacity);
347 : DCHECK(inline_count == kOutlineMarker || inline_count <= inline_capacity);
348 0 : }
349 :
350 :
351 70500027 : void Node::AppendUse(Use* use) {
352 : DCHECK(first_use_ == nullptr || first_use_->prev == nullptr);
353 : DCHECK_EQ(this, *use->input_ptr());
354 365280920 : use->next = first_use_;
355 365280920 : use->prev = nullptr;
356 365280920 : if (first_use_) first_use_->prev = use;
357 365280920 : first_use_ = use;
358 70500027 : }
359 :
360 :
361 108479619 : void Node::RemoveUse(Use* use) {
362 : DCHECK(first_use_ == nullptr || first_use_->prev == nullptr);
363 221626457 : if (use->prev) {
364 : DCHECK_NE(first_use_, use);
365 146853847 : use->prev->next = use->next;
366 : } else {
367 : DCHECK_EQ(first_use_, use);
368 74772610 : first_use_ = use->next;
369 : }
370 221626457 : if (use->next) {
371 138647699 : use->next->prev = use->prev;
372 : }
373 108479619 : }
374 :
375 :
376 : #if DEBUG
377 : void Node::Verify() {
378 : // Check basic sanity of input data structures.
379 : fflush(stdout);
380 : int count = this->InputCount();
381 : // Avoid quadratic explosion for mega nodes; only verify if the input
382 : // count is less than 200 or is a round number of 100s.
383 : if (count > 200 && count % 100) return;
384 :
385 : for (int i = 0; i < count; i++) {
386 : CHECK_EQ(i, this->GetUsePtr(i)->input_index());
387 : CHECK_EQ(this->GetInputPtr(i), this->GetUsePtr(i)->input_ptr());
388 : CHECK_EQ(count, this->InputCount());
389 : }
390 : { // Direct input iteration.
391 : int index = 0;
392 : for (Node* input : this->inputs()) {
393 : CHECK_EQ(this->InputAt(index), input);
394 : index++;
395 : }
396 : CHECK_EQ(count, index);
397 : CHECK_EQ(this->InputCount(), index);
398 : }
399 : { // Input edge iteration.
400 : int index = 0;
401 : for (Edge edge : this->input_edges()) {
402 : CHECK_EQ(edge.from(), this);
403 : CHECK_EQ(index, edge.index());
404 : CHECK_EQ(this->InputAt(index), edge.to());
405 : index++;
406 : }
407 : CHECK_EQ(count, index);
408 : CHECK_EQ(this->InputCount(), index);
409 : }
410 : }
411 : #endif
412 :
413 0 : Node::InputEdges::iterator Node::InputEdges::iterator::operator++(int n) {
414 : iterator result(*this);
415 : ++(*this);
416 0 : return result;
417 : }
418 :
419 :
420 0 : Node::Inputs::const_iterator Node::Inputs::const_iterator::operator++(int n) {
421 : const_iterator result(*this);
422 : ++(*this);
423 0 : return result;
424 : }
425 :
426 :
427 0 : Node::UseEdges::iterator Node::UseEdges::iterator::operator++(int n) {
428 : iterator result(*this);
429 : ++(*this);
430 0 : return result;
431 : }
432 :
433 :
434 11828 : bool Node::UseEdges::empty() const { return begin() == end(); }
435 :
436 :
437 247580 : Node::Uses::const_iterator Node::Uses::const_iterator::operator++(int n) {
438 : const_iterator result(*this);
439 : ++(*this);
440 247580 : return result;
441 : }
442 :
443 :
444 3501130 : bool Node::Uses::empty() const { return begin() == end(); }
445 :
446 : } // namespace compiler
447 : } // namespace internal
448 : } // namespace v8
|
