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
7namespace v8 {
8namespace internal {
9namespace compiler {
10
11Node::OutOfLineInputs* Node::OutOfLineInputs::New(Zone* zone, int capacity) {
12  size_t size =
13      sizeof(OutOfLineInputs) + capacity * (sizeof(Node*) + sizeof(Use));
14  intptr_t raw_buffer = reinterpret_cast<intptr_t>(zone->New(size));
15  Node::OutOfLineInputs* outline =
16      reinterpret_cast<OutOfLineInputs*>(raw_buffer + capacity * sizeof(Use));
17  outline->capacity_ = capacity;
18  outline->count_ = 0;
19  return outline;
20}
21
22
23void 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  Use* new_use_ptr = reinterpret_cast<Use*>(this) - 1;
28  Node** new_input_ptr = inputs_;
29  for (int current = 0; current < count; current++) {
30    new_use_ptr->bit_field_ =
31        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    Node* old_to = *old_input_ptr;
35    if (old_to) {
36      *old_input_ptr = nullptr;
37      old_to->RemoveUse(old_use_ptr);
38      *new_input_ptr = old_to;
39      old_to->AppendUse(new_use_ptr);
40    } else {
41      *new_input_ptr = nullptr;
42    }
43    old_input_ptr++;
44    new_input_ptr++;
45    old_use_ptr--;
46    new_use_ptr--;
47  }
48  this->count_ = count;
49}
50
51
52Node* 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  if (input_count > kMaxInlineCapacity) {
70    // Allocate out-of-line inputs.
71    int capacity =
72        has_extensible_inputs ? input_count + kMaxInlineCapacity : input_count;
73    OutOfLineInputs* outline = OutOfLineInputs::New(zone, capacity);
74
75    // Allocate node.
76    void* node_buffer = zone->New(sizeof(Node));
77    node = new (node_buffer) Node(id, op, kOutlineMarker, 0);
78    node->inputs_.outline_ = outline;
79
80    outline->node_ = node;
81    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.
88    int capacity = input_count;
89    if (has_extensible_inputs) {
90      const int max = kMaxInlineCapacity;
91      capacity = std::min(input_count + 3, max);
92    }
93
94    size_t size = sizeof(Node) + capacity * (sizeof(Node*) + sizeof(Use));
95    intptr_t raw_buffer = reinterpret_cast<intptr_t>(zone->New(size));
96    void* node_buffer =
97        reinterpret_cast<void*>(raw_buffer + capacity * sizeof(Use));
98
99    node = new (node_buffer) Node(id, op, input_count, capacity);
100    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  for (int current = 0; current < input_count; ++current) {
107    Node* to = *inputs++;
108    input_ptr[current] = to;
109    Use* use = use_ptr - 1 - current;
110    use->bit_field_ = Use::InputIndexField::encode(current) |
111                      Use::InlineField::encode(is_inline);
112    to->AppendUse(use);
113  }
114  node->Verify();
115  return node;
116}
117
118
119Node* 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                                  : node->inputs_.outline_->inputs_;
124  Node* const clone = New(zone, id, node->op(), input_count, inputs, false);
125  clone->set_type(node->type());
126  return clone;
127}
128
129
130void Node::Kill() {
131  DCHECK_NOT_NULL(op());
132  NullAllInputs();
133  DCHECK(uses().empty());
134}
135
136
137void Node::AppendInput(Zone* zone, Node* new_to) {
138  DCHECK_NOT_NULL(zone);
139  DCHECK_NOT_NULL(new_to);
140
141  int inline_count = InlineCountField::decode(bit_field_);
142  int inline_capacity = InlineCapacityField::decode(bit_field_);
143  if (inline_count < inline_capacity) {
144    // Append inline input.
145    bit_field_ = InlineCountField::update(bit_field_, inline_count + 1);
146    *GetInputPtr(inline_count) = new_to;
147    Use* use = GetUsePtr(inline_count);
148    use->bit_field_ = Use::InputIndexField::encode(inline_count) |
149                      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    if (inline_count != kOutlineMarker) {
156      // switch to out of line inputs.
157      outline = OutOfLineInputs::New(zone, input_count * 2 + 3);
158      outline->node_ = this;
159      outline->ExtractFrom(GetUsePtr(0), GetInputPtr(0), input_count);
160      bit_field_ = InlineCountField::update(bit_field_, kOutlineMarker);
161      inputs_.outline_ = outline;
162    } else {
163      // use current out of line inputs.
164      outline = inputs_.outline_;
165      if (input_count >= outline->capacity_) {
166        // out of space in out-of-line inputs.
167        outline = OutOfLineInputs::New(zone, input_count * 2 + 3);
168        outline->node_ = this;
169        outline->ExtractFrom(GetUsePtr(0), GetInputPtr(0), input_count);
170        inputs_.outline_ = outline;
171      }
172    }
173    outline->count_++;
174    *GetInputPtr(input_count) = new_to;
175    Use* use = GetUsePtr(input_count);
176    use->bit_field_ = Use::InputIndexField::encode(input_count) |
177                      Use::InlineField::encode(false);
178    new_to->AppendUse(use);
179  }
180  Verify();
181}
182
183
184void 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  AppendInput(zone, InputAt(InputCount() - 1));
189  for (int i = InputCount() - 1; i > index; --i) {
190    ReplaceInput(i, InputAt(i - 1));
191  }
192  ReplaceInput(index, new_to);
193  Verify();
194}
195
196void 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  for (int i = 0; i < count; i++) {
202    AppendInput(zone, InputAt(Max(InputCount() - count, 0)));
203  }
204  for (int i = InputCount() - count - 1; i >= Max(index, count); --i) {
205    ReplaceInput(i, InputAt(i - count));
206  }
207  for (int i = 0; i < count; i++) {
208    ReplaceInput(index + i, nullptr);
209  }
210  Verify();
211}
212
213void Node::RemoveInput(int index) {
214  DCHECK_LE(0, index);
215  DCHECK_LT(index, InputCount());
216  for (; index < InputCount() - 1; ++index) {
217    ReplaceInput(index, InputAt(index + 1));
218  }
219  TrimInputCount(InputCount() - 1);
220  Verify();
221}
222
223
224void Node::ClearInputs(int start, int count) {
225  Node** input_ptr = GetInputPtr(start);
226  Use* use_ptr = GetUsePtr(start);
227  while (count-- > 0) {
228    DCHECK_EQ(input_ptr, use_ptr->input_ptr());
229    Node* input = *input_ptr;
230    *input_ptr = nullptr;
231    if (input) input->RemoveUse(use_ptr);
232    input_ptr++;
233    use_ptr--;
234  }
235  Verify();
236}
237
238
239void Node::NullAllInputs() { ClearInputs(0, InputCount()); }
240
241
242void Node::TrimInputCount(int new_input_count) {
243  int current_count = InputCount();
244  DCHECK_LE(new_input_count, current_count);
245  if (new_input_count == current_count) return;  // Nothing to do.
246  ClearInputs(new_input_count, current_count - new_input_count);
247  if (has_inline_inputs()) {
248    bit_field_ = InlineCountField::update(bit_field_, new_input_count);
249  } else {
250    inputs_.outline_->count_ = new_input_count;
251  }
252}
253
254
255int Node::UseCount() const {
256  int use_count = 0;
257  for (const Use* use = first_use_; use; use = use->next) {
258    ++use_count;
259  }
260  return use_count;
261}
262
263
264void 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  for (Use* use = this->first_use_; use; use = use->next) {
271    *use->input_ptr() = that;
272    last_use = use;
273  }
274  if (last_use) {
275    // Concat the use list of {this} and {that}.
276    last_use->next = that->first_use_;
277    if (that->first_use_) that->first_use_->prev = last_use;
278    that->first_use_ = this->first_use_;
279  }
280  first_use_ = nullptr;
281}
282
283
284bool Node::OwnedBy(Node const* owner1, Node const* owner2) const {
285  unsigned mask = 0;
286  for (Use* use = first_use_; use; use = use->next) {
287    Node* from = use->from();
288    if (from == owner1) {
289      mask |= 1;
290    } else if (from == owner2) {
291      mask |= 2;
292    } else {
293      return false;
294    }
295  }
296  return mask == 3;
297}
298
299bool Node::OwnedByAddressingOperand() const {
300  for (Use* use = first_use_; use; use = use->next) {
301    Node* from = use->from();
302    if (from->opcode() != IrOpcode::kLoad &&
303        // If {from} is store, make sure it does not use {this} as value
304        (from->opcode() != IrOpcode::kStore || from->InputAt(2) == this) &&
305        from->opcode() != IrOpcode::kInt32Add &&
306        from->opcode() != IrOpcode::kInt64Add) {
307      return false;
308    }
309  }
310  return true;
311}
312
313void Node::Print() const {
314  OFStream os(stdout);
315  os << *this << std::endl;
316  for (Node* input : this->inputs()) {
317    os << "  " << *input << std::endl;
318  }
319}
320
321std::ostream& operator<<(std::ostream& os, const Node& n) {
322  os << n.id() << ": " << *n.op();
323  if (n.InputCount() > 0) {
324    os << "(";
325    for (int i = 0; i < n.InputCount(); ++i) {
326      if (i != 0) os << ", ";
327      if (n.InputAt(i)) {
328        os << n.InputAt(i)->id();
329      } else {
330        os << "null";
331      }
332    }
333    os << ")";
334  }
335  return os;
336}
337
338Node::Node(NodeId id, const Operator* op, int inline_count, int inline_capacity)
339    : op_(op),
340      type_(nullptr),
341      mark_(0),
342      bit_field_(IdField::encode(id) | InlineCountField::encode(inline_count) |
343                 InlineCapacityField::encode(inline_capacity)),
344      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}
349
350
351void Node::AppendUse(Use* use) {
352  DCHECK(first_use_ == nullptr || first_use_->prev == nullptr);
353  DCHECK_EQ(this, *use->input_ptr());
354  use->next = first_use_;
355  use->prev = nullptr;
356  if (first_use_) first_use_->prev = use;
357  first_use_ = use;
358}
359
360
361void Node::RemoveUse(Use* use) {
362  DCHECK(first_use_ == nullptr || first_use_->prev == nullptr);
363  if (use->prev) {
364    DCHECK_NE(first_use_, use);
365    use->prev->next = use->next;
366  } else {
367    DCHECK_EQ(first_use_, use);
368    first_use_ = use->next;
369  }
370  if (use->next) {
371    use->next->prev = use->prev;
372  }
373}
374
375
376#if DEBUG
377void 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
413Node::InputEdges::iterator Node::InputEdges::iterator::operator++(int n) {
414  iterator result(*this);
415  ++(*this);
416  return result;
417}
418
419
420Node::Inputs::const_iterator Node::Inputs::const_iterator::operator++(int n) {
421  const_iterator result(*this);
422  ++(*this);
423  return result;
424}
425
426
427Node::UseEdges::iterator Node::UseEdges::iterator::operator++(int n) {
428  iterator result(*this);
429  ++(*this);
430  return result;
431}
432
433
434bool Node::UseEdges::empty() const { return begin() == end(); }
435
436
437Node::Uses::const_iterator Node::Uses::const_iterator::operator++(int n) {
438  const_iterator result(*this);
439  ++(*this);
440  return result;
441}
442
443
444bool Node::Uses::empty() const { return begin() == end(); }
445
446}  // namespace compiler
447}  // namespace internal
448}  // namespace v8
449