OLD | NEW |
(Empty) | |
| 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 |
| 12 namespace v8 { |
| 13 namespace internal { |
| 14 namespace compiler { |
| 15 |
| 16 class GenericGraphBase; |
| 17 |
| 18 typedef 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. |
| 29 template <class B, class S> |
| 30 class 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 bool has_extensible_inputs); |
| 97 |
| 98 protected: |
| 99 friend class GenericGraphBase; |
| 100 |
| 101 class Use : public ZoneObject { |
| 102 public: |
| 103 GenericNode* from; |
| 104 Use* next; |
| 105 Use* prev; |
| 106 int input_index; |
| 107 }; |
| 108 |
| 109 class Input { |
| 110 public: |
| 111 GenericNode* to; |
| 112 Use* use; |
| 113 |
| 114 void Update(GenericNode* new_to); |
| 115 }; |
| 116 |
| 117 void EnsureAppendableInputs(Zone* zone); |
| 118 |
| 119 Input* GetInputRecordPtr(int index) const { |
| 120 if (has_appendable_inputs_) { |
| 121 return &((*inputs_.appendable_)[index]); |
| 122 } else { |
| 123 return inputs_.static_ + index; |
| 124 } |
| 125 } |
| 126 |
| 127 inline void AppendUse(Use* use); |
| 128 inline void RemoveUse(Use* use); |
| 129 |
| 130 void* operator new(size_t, void* location) { return location; } |
| 131 |
| 132 GenericNode(GenericGraphBase* graph, int input_count, |
| 133 int reserved_input_count); |
| 134 |
| 135 private: |
| 136 void AssignUniqueID(GenericGraphBase* graph); |
| 137 |
| 138 typedef ZoneDeque<Input> InputDeque; |
| 139 |
| 140 static const int kReservedInputCountBits = 2; |
| 141 static const int kMaxReservedInputs = (1 << kReservedInputCountBits) - 1; |
| 142 static const int kDefaultReservedInputs = kMaxReservedInputs; |
| 143 |
| 144 NodeId id_; |
| 145 int input_count_ : 29; |
| 146 unsigned int reserve_input_count_ : kReservedInputCountBits; |
| 147 bool has_appendable_inputs_ : 1; |
| 148 union { |
| 149 // When a node is initially allocated, it uses a static buffer to hold its |
| 150 // inputs under the assumption that the number of outputs will not increase. |
| 151 // When the first input is appended, the static buffer is converted into a |
| 152 // deque to allow for space-efficient growing. |
| 153 Input* static_; |
| 154 InputDeque* appendable_; |
| 155 } inputs_; |
| 156 int use_count_; |
| 157 Use* first_use_; |
| 158 Use* last_use_; |
| 159 |
| 160 DISALLOW_COPY_AND_ASSIGN(GenericNode); |
| 161 }; |
| 162 |
| 163 // An encapsulation for information associated with a single use of node as a |
| 164 // input from another node, allowing access to both the defining node and |
| 165 // the ndoe having the input. |
| 166 template <class B, class S> |
| 167 class GenericNode<B, S>::Edge { |
| 168 public: |
| 169 S* from() const { return static_cast<S*>(input_->use->from); } |
| 170 S* to() const { return static_cast<S*>(input_->to); } |
| 171 int index() const { |
| 172 int index = input_->use->input_index; |
| 173 DCHECK(index < input_->use->from->input_count_); |
| 174 return index; |
| 175 } |
| 176 |
| 177 private: |
| 178 friend class GenericNode<B, S>::Uses::iterator; |
| 179 friend class GenericNode<B, S>::Inputs::iterator; |
| 180 |
| 181 explicit Edge(typename GenericNode<B, S>::Input* input) : input_(input) {} |
| 182 |
| 183 typename GenericNode<B, S>::Input* input_; |
| 184 }; |
| 185 |
| 186 // A forward iterator to visit the nodes which are depended upon by a node |
| 187 // in the order of input. |
| 188 template <class B, class S> |
| 189 class GenericNode<B, S>::Inputs::iterator { |
| 190 public: |
| 191 iterator(const typename GenericNode<B, S>::Inputs::iterator& other) // NOLINT |
| 192 : node_(other.node_), |
| 193 index_(other.index_) {} |
| 194 |
| 195 S* operator*() { return static_cast<S*>(GetInput()->to); } |
| 196 typename GenericNode<B, S>::Edge edge() { |
| 197 return typename GenericNode::Edge(GetInput()); |
| 198 } |
| 199 bool operator==(const iterator& other) const { |
| 200 return other.index_ == index_ && other.node_ == node_; |
| 201 } |
| 202 bool operator!=(const iterator& other) const { return !(other == *this); } |
| 203 iterator& operator++() { |
| 204 DCHECK(node_ != NULL); |
| 205 DCHECK(index_ < node_->input_count_); |
| 206 ++index_; |
| 207 return *this; |
| 208 } |
| 209 iterator& UpdateToAndIncrement(GenericNode<B, S>* new_to) { |
| 210 typename GenericNode<B, S>::Input* input = GetInput(); |
| 211 input->Update(new_to); |
| 212 index_++; |
| 213 return *this; |
| 214 } |
| 215 int index() { return index_; } |
| 216 |
| 217 private: |
| 218 friend class GenericNode; |
| 219 |
| 220 explicit iterator(GenericNode* node, int index) |
| 221 : node_(node), index_(index) {} |
| 222 |
| 223 Input* GetInput() const { return node_->GetInputRecordPtr(index_); } |
| 224 |
| 225 GenericNode* node_; |
| 226 int index_; |
| 227 }; |
| 228 |
| 229 // A forward iterator to visit the uses of a node. The uses are returned in |
| 230 // the order in which they were added as inputs. |
| 231 template <class B, class S> |
| 232 class GenericNode<B, S>::Uses::iterator { |
| 233 public: |
| 234 iterator(const typename GenericNode<B, S>::Uses::iterator& other) // NOLINT |
| 235 : current_(other.current_), |
| 236 index_(other.index_) {} |
| 237 |
| 238 S* operator*() { return static_cast<S*>(current_->from); } |
| 239 typename GenericNode<B, S>::Edge edge() { |
| 240 return typename GenericNode::Edge(CurrentInput()); |
| 241 } |
| 242 |
| 243 bool operator==(const iterator& other) { return other.current_ == current_; } |
| 244 bool operator!=(const iterator& other) { return other.current_ != current_; } |
| 245 iterator& operator++() { |
| 246 DCHECK(current_ != NULL); |
| 247 index_++; |
| 248 current_ = current_->next; |
| 249 return *this; |
| 250 } |
| 251 iterator& UpdateToAndIncrement(GenericNode<B, S>* new_to) { |
| 252 DCHECK(current_ != NULL); |
| 253 index_++; |
| 254 typename GenericNode<B, S>::Input* input = CurrentInput(); |
| 255 current_ = current_->next; |
| 256 input->Update(new_to); |
| 257 return *this; |
| 258 } |
| 259 int index() const { return index_; } |
| 260 |
| 261 private: |
| 262 friend class GenericNode<B, S>::Uses; |
| 263 |
| 264 iterator() : current_(NULL), index_(0) {} |
| 265 explicit iterator(GenericNode<B, S>* node) |
| 266 : current_(node->first_use_), index_(0) {} |
| 267 |
| 268 Input* CurrentInput() const { |
| 269 return current_->from->GetInputRecordPtr(current_->input_index); |
| 270 } |
| 271 |
| 272 typename GenericNode<B, S>::Use* current_; |
| 273 int index_; |
| 274 }; |
| 275 } |
| 276 } |
| 277 } // namespace v8::internal::compiler |
| 278 |
| 279 #endif // V8_COMPILER_GENERIC_NODE_H_ |
OLD | NEW |