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