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