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_H_
6#define V8_COMPILER_GENERIC_NODE_H_
7
8#include "src/v8.h"
9
10#include "src/zone-containers.h"
11
12namespace v8 {
13namespace internal {
14namespace compiler {
15
16class GenericGraphBase;
17
18typedef int NodeId;
19
20// A GenericNode<> is the basic primitive of graphs. GenericNode's are
21// chained together by input/use chains but by default otherwise contain only an
22// identifying number which specific applications of graphs and nodes can use
23// to index auxiliary out-of-line data, especially transient data.
24// Specializations of the templatized GenericNode<> class must provide a base
25// class B that contains all of the members to be made available in each
26// specialized Node instance. GenericNode uses a mixin template pattern to
27// ensure that common accessors and methods expect the derived class S type
28// rather than the GenericNode<B, S> type.
29template <class B, class S>
30class GenericNode : public B {
31 public:
32  typedef B BaseClass;
33  typedef S DerivedClass;
34
35  inline NodeId id() const { return id_; }
36
37  int InputCount() const { return input_count_; }
38  S* InputAt(int index) const {
39    return static_cast<S*>(GetInputRecordPtr(index)->to);
40  }
41  inline void ReplaceInput(int index, GenericNode* new_input);
42  inline void AppendInput(Zone* zone, GenericNode* new_input);
43  inline void InsertInput(Zone* zone, int index, GenericNode* new_input);
44  inline void RemoveInput(int index);
45
46  int UseCount() { return use_count_; }
47  S* UseAt(int index) {
48    DCHECK(index < use_count_);
49    Use* current = first_use_;
50    while (index-- != 0) {
51      current = current->next;
52    }
53    return static_cast<S*>(current->from);
54  }
55  inline void ReplaceUses(GenericNode* replace_to);
56  template <class UnaryPredicate>
57  inline void ReplaceUsesIf(UnaryPredicate pred, GenericNode* replace_to);
58  inline void RemoveAllInputs();
59
60  inline void TrimInputCount(int input_count);
61
62  class Inputs {
63   public:
64    class iterator;
65    iterator begin();
66    iterator end();
67
68    explicit Inputs(GenericNode* node) : node_(node) {}
69
70   private:
71    GenericNode* node_;
72  };
73
74  Inputs inputs() { return Inputs(this); }
75
76  class Uses {
77   public:
78    class iterator;
79    iterator begin();
80    iterator end();
81    bool empty() { return begin() == end(); }
82
83    explicit Uses(GenericNode* node) : node_(node) {}
84
85   private:
86    GenericNode* node_;
87  };
88
89  Uses uses() { return Uses(this); }
90
91  class Edge;
92
93  bool OwnedBy(GenericNode* owner) const;
94
95  static S* New(GenericGraphBase* graph, int input_count, S** inputs);
96
97 protected:
98  friend class GenericGraphBase;
99
100  class Use : public ZoneObject {
101   public:
102    GenericNode* from;
103    Use* next;
104    Use* prev;
105    int input_index;
106  };
107
108  class Input {
109   public:
110    GenericNode* to;
111    Use* use;
112
113    void Update(GenericNode* new_to);
114  };
115
116  void EnsureAppendableInputs(Zone* zone);
117
118  Input* GetInputRecordPtr(int index) const {
119    if (has_appendable_inputs_) {
120      return &((*inputs_.appendable_)[index]);
121    } else {
122      return inputs_.static_ + index;
123    }
124  }
125
126  inline void AppendUse(Use* use);
127  inline void RemoveUse(Use* use);
128
129  void* operator new(size_t, void* location) { return location; }
130
131  GenericNode(GenericGraphBase* graph, int input_count);
132
133 private:
134  void AssignUniqueID(GenericGraphBase* graph);
135
136  typedef ZoneDeque<Input> InputDeque;
137
138  NodeId id_;
139  int input_count_ : 31;
140  bool has_appendable_inputs_ : 1;
141  union {
142    // When a node is initially allocated, it uses a static buffer to hold its
143    // inputs under the assumption that the number of outputs will not increase.
144    // When the first input is appended, the static buffer is converted into a
145    // deque to allow for space-efficient growing.
146    Input* static_;
147    InputDeque* appendable_;
148  } inputs_;
149  int use_count_;
150  Use* first_use_;
151  Use* last_use_;
152
153  DISALLOW_COPY_AND_ASSIGN(GenericNode);
154};
155
156// An encapsulation for information associated with a single use of node as a
157// input from another node, allowing access to both the defining node and
158// the ndoe having the input.
159template <class B, class S>
160class GenericNode<B, S>::Edge {
161 public:
162  S* from() const { return static_cast<S*>(input_->use->from); }
163  S* to() const { return static_cast<S*>(input_->to); }
164  int index() const {
165    int index = input_->use->input_index;
166    DCHECK(index < input_->use->from->input_count_);
167    return index;
168  }
169
170 private:
171  friend class GenericNode<B, S>::Uses::iterator;
172  friend class GenericNode<B, S>::Inputs::iterator;
173
174  explicit Edge(typename GenericNode<B, S>::Input* input) : input_(input) {}
175
176  typename GenericNode<B, S>::Input* input_;
177};
178
179// A forward iterator to visit the nodes which are depended upon by a node
180// in the order of input.
181template <class B, class S>
182class GenericNode<B, S>::Inputs::iterator {
183 public:
184  iterator(const typename GenericNode<B, S>::Inputs::iterator& other)  // NOLINT
185      : node_(other.node_),
186        index_(other.index_) {}
187
188  S* operator*() { return static_cast<S*>(GetInput()->to); }
189  typename GenericNode<B, S>::Edge edge() {
190    return typename GenericNode::Edge(GetInput());
191  }
192  bool operator==(const iterator& other) const {
193    return other.index_ == index_ && other.node_ == node_;
194  }
195  bool operator!=(const iterator& other) const { return !(other == *this); }
196  iterator& operator++() {
197    DCHECK(node_ != NULL);
198    DCHECK(index_ < node_->input_count_);
199    ++index_;
200    return *this;
201  }
202  iterator& UpdateToAndIncrement(GenericNode<B, S>* new_to) {
203    typename GenericNode<B, S>::Input* input = GetInput();
204    input->Update(new_to);
205    index_++;
206    return *this;
207  }
208  int index() { return index_; }
209
210 private:
211  friend class GenericNode;
212
213  explicit iterator(GenericNode* node, int index)
214      : node_(node), index_(index) {}
215
216  Input* GetInput() const { return node_->GetInputRecordPtr(index_); }
217
218  GenericNode* node_;
219  int index_;
220};
221
222// A forward iterator to visit the uses of a node. The uses are returned in
223// the order in which they were added as inputs.
224template <class B, class S>
225class GenericNode<B, S>::Uses::iterator {
226 public:
227  iterator(const typename GenericNode<B, S>::Uses::iterator& other)  // NOLINT
228      : current_(other.current_),
229        index_(other.index_) {}
230
231  S* operator*() { return static_cast<S*>(current_->from); }
232  typename GenericNode<B, S>::Edge edge() {
233    return typename GenericNode::Edge(CurrentInput());
234  }
235
236  bool operator==(const iterator& other) { return other.current_ == current_; }
237  bool operator!=(const iterator& other) { return other.current_ != current_; }
238  iterator& operator++() {
239    DCHECK(current_ != NULL);
240    index_++;
241    current_ = current_->next;
242    return *this;
243  }
244  iterator& UpdateToAndIncrement(GenericNode<B, S>* new_to) {
245    DCHECK(current_ != NULL);
246    index_++;
247    typename GenericNode<B, S>::Input* input = CurrentInput();
248    current_ = current_->next;
249    input->Update(new_to);
250    return *this;
251  }
252  int index() const { return index_; }
253
254 private:
255  friend class GenericNode<B, S>::Uses;
256
257  iterator() : current_(NULL), index_(0) {}
258  explicit iterator(GenericNode<B, S>* node)
259      : current_(node->first_use_), index_(0) {}
260
261  Input* CurrentInput() const {
262    return current_->from->GetInputRecordPtr(current_->input_index);
263  }
264
265  typename GenericNode<B, S>::Use* current_;
266  int index_;
267};
268}
269}
270}  // namespace v8::internal::compiler
271
272#endif  // V8_COMPILER_GENERIC_NODE_H_
273