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 
14 namespace v8 {
15 namespace internal {
16 namespace compiler {
17 
18 template <class B, class S>
GenericNode(GenericGraphBase * graph,int input_count)19 GenericNode<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 
29 template <class B, class S>
AssignUniqueID(GenericGraphBase * graph)30 inline void GenericNode<B, S>::AssignUniqueID(GenericGraphBase* graph) {
31   id_ = graph->NextNodeID();
32 }
33 
34 template <class B, class S>
35 inline typename GenericNode<B, S>::Inputs::iterator
begin()36 GenericNode<B, S>::Inputs::begin() {
37   return typename GenericNode<B, S>::Inputs::iterator(this->node_, 0);
38 }
39 
40 template <class B, class S>
41 inline typename GenericNode<B, S>::Inputs::iterator
end()42 GenericNode<B, S>::Inputs::end() {
43   return typename GenericNode<B, S>::Inputs::iterator(
44       this->node_, this->node_->InputCount());
45 }
46 
47 template <class B, class S>
48 inline typename GenericNode<B, S>::Uses::iterator
begin()49 GenericNode<B, S>::Uses::begin() {
50   return typename GenericNode<B, S>::Uses::iterator(this->node_);
51 }
52 
53 template <class B, class S>
54 inline typename GenericNode<B, S>::Uses::iterator
end()55 GenericNode<B, S>::Uses::end() {
56   return typename GenericNode<B, S>::Uses::iterator();
57 }
58 
59 template <class B, class S>
ReplaceUses(GenericNode * replace_to)60 void 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 
80 template <class B, class S>
81 template <class UnaryPredicate>
ReplaceUsesIf(UnaryPredicate pred,GenericNode * replace_to)82 void 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 
95 template <class B, class S>
RemoveAllInputs()96 void 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 
103 template <class B, class S>
TrimInputCount(int new_input_count)104 void 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 
117 template <class B, class S>
ReplaceInput(int index,GenericNode<B,S> * new_to)118 void GenericNode<B, S>::ReplaceInput(int index, GenericNode<B, S>* new_to) {
119   Input* input = GetInputRecordPtr(index);
120   input->Update(new_to);
121 }
122 
123 template <class B, class S>
Update(GenericNode<B,S> * new_to)124 void 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 
141 template <class B, class S>
EnsureAppendableInputs(Zone * zone)142 void 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 
154 template <class B, class S>
AppendInput(Zone * zone,GenericNode<B,S> * to_append)155 void 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 
168 template <class B, class S>
InsertInput(Zone * zone,int index,GenericNode<B,S> * to_insert)169 void 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 
180 template <class B, class S>
RemoveInput(int index)181 void 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 
190 template <class B, class S>
AppendUse(Use * use)191 void 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 
203 template <class B, class S>
RemoveUse(Use * use)204 void 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 
219 template <class B, class S>
OwnedBy(GenericNode * owner)220 inline bool GenericNode<B, S>::OwnedBy(GenericNode* owner) const {
221   return first_use_ != NULL && first_use_->from == owner &&
222          first_use_->next == NULL;
223 }
224 
225 template <class B, class S>
New(GenericGraphBase * graph,int input_count,S ** inputs)226 S* 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