Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 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_NODE_H_ |
| 6 | #define V8_COMPILER_NODE_H_ |
| 7 | |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 8 | #include "src/compiler/opcodes.h" |
| 9 | #include "src/compiler/operator.h" |
| 10 | #include "src/types.h" |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 11 | #include "src/zone-containers.h" |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 12 | |
| 13 | namespace v8 { |
| 14 | namespace internal { |
| 15 | namespace compiler { |
| 16 | |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 17 | // Forward declarations. |
| 18 | class Edge; |
| 19 | class Graph; |
| 20 | |
| 21 | |
| 22 | // Marks are used during traversal of the graph to distinguish states of nodes. |
| 23 | // Each node has a mark which is a monotonically increasing integer, and a |
| 24 | // {NodeMarker} has a range of values that indicate states of a node. |
| 25 | typedef uint32_t Mark; |
| 26 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 27 | |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 28 | // NodeIds are identifying numbers for nodes that can be used to index auxiliary |
| 29 | // out-of-line data associated with each node. |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 30 | typedef uint32_t NodeId; |
| 31 | |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 32 | |
| 33 | // A Node is the basic primitive of graphs. Nodes are chained together by |
| 34 | // input/use chains but by default otherwise contain only an identifying number |
| 35 | // which specific applications of graphs and nodes can use to index auxiliary |
| 36 | // out-of-line data, especially transient data. |
| 37 | // |
| 38 | // In addition Nodes only contain a mutable Operator that may change during |
| 39 | // compilation, e.g. during lowering passes. Other information that needs to be |
| 40 | // associated with Nodes during compilation must be stored out-of-line indexed |
| 41 | // by the Node's id. |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 42 | class Node final { |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 43 | public: |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 44 | static Node* New(Zone* zone, NodeId id, const Operator* op, int input_count, |
| 45 | Node* const* inputs, bool has_extensible_inputs); |
| 46 | static Node* Clone(Zone* zone, NodeId id, const Node* node); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 47 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 48 | bool IsDead() const { return InputCount() > 0 && !InputAt(0); } |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 49 | void Kill(); |
| 50 | |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 51 | const Operator* op() const { return op_; } |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 52 | |
| 53 | IrOpcode::Value opcode() const { |
| 54 | DCHECK(op_->opcode() <= IrOpcode::kLast); |
| 55 | return static_cast<IrOpcode::Value>(op_->opcode()); |
| 56 | } |
| 57 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 58 | NodeId id() const { return IdField::decode(bit_field_); } |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 59 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 60 | int InputCount() const { |
| 61 | return has_inline_inputs() ? InlineCountField::decode(bit_field_) |
| 62 | : inputs_.outline_->count_; |
| 63 | } |
| 64 | |
| 65 | #if DEBUG |
| 66 | void Verify(); |
| 67 | #define BOUNDS_CHECK(index) \ |
| 68 | do { \ |
| 69 | if (index < 0 || index >= InputCount()) { \ |
| 70 | V8_Fatal(__FILE__, __LINE__, "Node #%d:%s->InputAt(%d) out of bounds", \ |
| 71 | id(), op()->mnemonic(), index); \ |
| 72 | } \ |
| 73 | } while (false) |
| 74 | #else |
| 75 | // No bounds checks or verification in release mode. |
| 76 | inline void Verify() {} |
| 77 | #define BOUNDS_CHECK(index) \ |
| 78 | do { \ |
| 79 | } while (false) |
| 80 | #endif |
| 81 | |
| 82 | Node* InputAt(int index) const { |
| 83 | BOUNDS_CHECK(index); |
| 84 | return *GetInputPtrConst(index); |
| 85 | } |
| 86 | |
| 87 | void ReplaceInput(int index, Node* new_to) { |
| 88 | BOUNDS_CHECK(index); |
| 89 | Node** input_ptr = GetInputPtr(index); |
| 90 | Node* old_to = *input_ptr; |
| 91 | if (old_to != new_to) { |
| 92 | Use* use = GetUsePtr(index); |
| 93 | if (old_to) old_to->RemoveUse(use); |
| 94 | *input_ptr = new_to; |
| 95 | if (new_to) new_to->AppendUse(use); |
| 96 | } |
| 97 | } |
| 98 | |
| 99 | #undef BOUNDS_CHECK |
| 100 | |
| 101 | void AppendInput(Zone* zone, Node* new_to); |
| 102 | void InsertInput(Zone* zone, int index, Node* new_to); |
| 103 | void RemoveInput(int index); |
| 104 | void NullAllInputs(); |
| 105 | void TrimInputCount(int new_input_count); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 106 | |
| 107 | int UseCount() const; |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 108 | void ReplaceUses(Node* replace_to); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 109 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 110 | class InputEdges final { |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 111 | public: |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 112 | typedef Edge value_type; |
| 113 | |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 114 | class iterator; |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 115 | inline iterator begin() const; |
| 116 | inline iterator end() const; |
| 117 | |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 118 | bool empty() const; |
| 119 | |
| 120 | explicit InputEdges(Node* node) : node_(node) {} |
| 121 | |
| 122 | private: |
| 123 | Node* node_; |
| 124 | }; |
| 125 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 126 | InputEdges input_edges() { return InputEdges(this); } |
| 127 | |
| 128 | class Inputs final { |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 129 | public: |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 130 | typedef Node* value_type; |
| 131 | |
| 132 | class const_iterator; |
| 133 | inline const_iterator begin() const; |
| 134 | inline const_iterator end() const; |
| 135 | |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 136 | bool empty() const; |
| 137 | |
| 138 | explicit Inputs(Node* node) : node_(node) {} |
| 139 | |
| 140 | private: |
| 141 | Node* node_; |
| 142 | }; |
| 143 | |
| 144 | Inputs inputs() { return Inputs(this); } |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 145 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 146 | class UseEdges final { |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 147 | public: |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 148 | typedef Edge value_type; |
| 149 | |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 150 | class iterator; |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 151 | inline iterator begin() const; |
| 152 | inline iterator end() const; |
| 153 | |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 154 | bool empty() const; |
| 155 | |
| 156 | explicit UseEdges(Node* node) : node_(node) {} |
| 157 | |
| 158 | private: |
| 159 | Node* node_; |
| 160 | }; |
| 161 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 162 | UseEdges use_edges() { return UseEdges(this); } |
| 163 | |
| 164 | class Uses final { |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 165 | public: |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 166 | typedef Node* value_type; |
| 167 | |
| 168 | class const_iterator; |
| 169 | inline const_iterator begin() const; |
| 170 | inline const_iterator end() const; |
| 171 | |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 172 | bool empty() const; |
| 173 | |
| 174 | explicit Uses(Node* node) : node_(node) {} |
| 175 | |
| 176 | private: |
| 177 | Node* node_; |
| 178 | }; |
| 179 | |
| 180 | Uses uses() { return Uses(this); } |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 181 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 182 | // Returns true if {owner} is the user of {this} node. |
| 183 | bool OwnedBy(Node* owner) const { |
| 184 | return first_use_ && first_use_->from() == owner && !first_use_->next; |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 185 | } |
| 186 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 187 | // Returns true if {owner1} and {owner2} are the only users of {this} node. |
| 188 | bool OwnedBy(Node const* owner1, Node const* owner2) const; |
| 189 | void Print() const; |
| 190 | |
| 191 | private: |
| 192 | struct Use; |
| 193 | // Out of line storage for inputs when the number of inputs overflowed the |
| 194 | // capacity of the inline-allocated space. |
| 195 | struct OutOfLineInputs { |
| 196 | Node* node_; |
| 197 | int count_; |
| 198 | int capacity_; |
| 199 | Node* inputs_[1]; |
| 200 | |
| 201 | static OutOfLineInputs* New(Zone* zone, int capacity); |
| 202 | void ExtractFrom(Use* use_ptr, Node** input_ptr, int count); |
| 203 | }; |
| 204 | |
| 205 | // A link in the use chain for a node. Every input {i} to a node {n} has an |
| 206 | // associated {Use} which is linked into the use chain of the {i} node. |
| 207 | struct Use { |
| 208 | Use* next; |
| 209 | Use* prev; |
| 210 | uint32_t bit_field_; |
| 211 | |
| 212 | int input_index() const { return InputIndexField::decode(bit_field_); } |
| 213 | bool is_inline_use() const { return InlineField::decode(bit_field_); } |
| 214 | Node** input_ptr() { |
| 215 | int index = input_index(); |
| 216 | Use* start = this + 1 + index; |
| 217 | Node** inputs = is_inline_use() |
| 218 | ? reinterpret_cast<Node*>(start)->inputs_.inline_ |
| 219 | : reinterpret_cast<OutOfLineInputs*>(start)->inputs_; |
| 220 | return &inputs[index]; |
| 221 | } |
| 222 | |
| 223 | Node* from() { |
| 224 | Use* start = this + 1 + input_index(); |
| 225 | return is_inline_use() ? reinterpret_cast<Node*>(start) |
| 226 | : reinterpret_cast<OutOfLineInputs*>(start)->node_; |
| 227 | } |
| 228 | |
| 229 | typedef BitField<bool, 0, 1> InlineField; |
| 230 | typedef BitField<unsigned, 1, 17> InputIndexField; |
| 231 | // Leaving some space in the bitset in case we ever decide to record |
| 232 | // the output index. |
| 233 | }; |
| 234 | |
| 235 | //============================================================================ |
| 236 | //== Memory layout =========================================================== |
| 237 | //============================================================================ |
| 238 | // Saving space for big graphs is important. We use a memory layout trick to |
| 239 | // be able to map {Node} objects to {Use} objects and vice-versa in a |
| 240 | // space-efficient manner. |
| 241 | // |
| 242 | // {Use} links are laid out in memory directly before a {Node}, followed by |
| 243 | // direct pointers to input {Nodes}. |
| 244 | // |
| 245 | // inline case: |
| 246 | // |Use #N |Use #N-1|...|Use #1 |Use #0 |Node xxxx |I#0|I#1|...|I#N-1|I#N| |
| 247 | // ^ ^ ^ |
| 248 | // + Use + Node + Input |
| 249 | // |
| 250 | // Since every {Use} instance records its {input_index}, pointer arithmetic |
| 251 | // can compute the {Node}. |
| 252 | // |
| 253 | // out-of-line case: |
| 254 | // |Node xxxx | |
| 255 | // ^ + outline ------------------+ |
| 256 | // +----------------------------------------+ |
| 257 | // | | |
| 258 | // v | node |
| 259 | // |Use #N |Use #N-1|...|Use #1 |Use #0 |OOL xxxxx |I#0|I#1|...|I#N-1|I#N| |
| 260 | // ^ ^ |
| 261 | // + Use + Input |
| 262 | // |
| 263 | // Out-of-line storage of input lists is needed if appending an input to |
| 264 | // a node exceeds the maximum inline capacity. |
| 265 | |
| 266 | Node(NodeId id, const Operator* op, int inline_count, int inline_capacity); |
| 267 | |
| 268 | Node* const* GetInputPtrConst(int input_index) const { |
| 269 | return has_inline_inputs() ? &(inputs_.inline_[input_index]) |
| 270 | : &inputs_.outline_->inputs_[input_index]; |
| 271 | } |
| 272 | Node** GetInputPtr(int input_index) { |
| 273 | return has_inline_inputs() ? &(inputs_.inline_[input_index]) |
| 274 | : &inputs_.outline_->inputs_[input_index]; |
| 275 | } |
| 276 | Use* GetUsePtr(int input_index) { |
| 277 | Use* ptr = has_inline_inputs() ? reinterpret_cast<Use*>(this) |
| 278 | : reinterpret_cast<Use*>(inputs_.outline_); |
| 279 | return &ptr[-1 - input_index]; |
| 280 | } |
| 281 | |
| 282 | void AppendUse(Use* use); |
| 283 | void RemoveUse(Use* use); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 284 | |
| 285 | void* operator new(size_t, void* location) { return location; } |
| 286 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 287 | // Only NodeProperties should manipulate the op. |
| 288 | void set_op(const Operator* op) { op_ = op; } |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 289 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 290 | // Only NodeProperties should manipulate the type. |
| 291 | Type* type() const { return type_; } |
| 292 | void set_type(Type* type) { type_ = type; } |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 293 | |
| 294 | // Only NodeMarkers should manipulate the marks on nodes. |
| 295 | Mark mark() { return mark_; } |
| 296 | void set_mark(Mark mark) { mark_ = mark; } |
| 297 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 298 | inline bool has_inline_inputs() const { |
| 299 | return InlineCountField::decode(bit_field_) != kOutlineMarker; |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 300 | } |
| 301 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 302 | void ClearInputs(int start, int count); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 303 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 304 | typedef BitField<NodeId, 0, 24> IdField; |
| 305 | typedef BitField<unsigned, 24, 4> InlineCountField; |
| 306 | typedef BitField<unsigned, 28, 4> InlineCapacityField; |
| 307 | static const int kOutlineMarker = InlineCountField::kMax; |
| 308 | static const int kMaxInlineCount = InlineCountField::kMax - 1; |
| 309 | static const int kMaxInlineCapacity = InlineCapacityField::kMax - 1; |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 310 | |
| 311 | const Operator* op_; |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 312 | Type* type_; |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 313 | Mark mark_; |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 314 | uint32_t bit_field_; |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 315 | Use* first_use_; |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 316 | union { |
| 317 | // Inline storage for inputs or out-of-line storage. |
| 318 | Node* inline_[1]; |
| 319 | OutOfLineInputs* outline_; |
| 320 | } inputs_; |
| 321 | |
| 322 | friend class Edge; |
| 323 | friend class NodeMarkerBase; |
| 324 | friend class NodeProperties; |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 325 | |
| 326 | DISALLOW_COPY_AND_ASSIGN(Node); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 327 | }; |
| 328 | |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 329 | |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 330 | std::ostream& operator<<(std::ostream& os, const Node& n); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 331 | |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 332 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 333 | // Typedefs to shorten commonly used Node containers. |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 334 | typedef ZoneDeque<Node*> NodeDeque; |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 335 | typedef ZoneSet<Node*> NodeSet; |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 336 | typedef ZoneVector<Node*> NodeVector; |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 337 | typedef ZoneVector<NodeVector> NodeVectorVector; |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 338 | |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 339 | |
| 340 | // Helper to extract parameters from Operator1<*> nodes. |
| 341 | template <typename T> |
| 342 | static inline const T& OpParameter(const Node* node) { |
| 343 | return OpParameter<T>(node->op()); |
| 344 | } |
| 345 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 346 | |
| 347 | // An encapsulation for information associated with a single use of node as a |
| 348 | // input from another node, allowing access to both the defining node and |
| 349 | // the node having the input. |
| 350 | class Edge final { |
| 351 | public: |
| 352 | Node* from() const { return use_->from(); } |
| 353 | Node* to() const { return *input_ptr_; } |
| 354 | int index() const { |
| 355 | int const index = use_->input_index(); |
| 356 | DCHECK_LT(index, use_->from()->InputCount()); |
| 357 | return index; |
| 358 | } |
| 359 | |
| 360 | bool operator==(const Edge& other) { return input_ptr_ == other.input_ptr_; } |
| 361 | bool operator!=(const Edge& other) { return !(*this == other); } |
| 362 | |
| 363 | void UpdateTo(Node* new_to) { |
| 364 | Node* old_to = *input_ptr_; |
| 365 | if (old_to != new_to) { |
| 366 | if (old_to) old_to->RemoveUse(use_); |
| 367 | *input_ptr_ = new_to; |
| 368 | if (new_to) new_to->AppendUse(use_); |
| 369 | } |
| 370 | } |
| 371 | |
| 372 | private: |
| 373 | friend class Node::UseEdges::iterator; |
| 374 | friend class Node::InputEdges::iterator; |
| 375 | |
| 376 | Edge(Node::Use* use, Node** input_ptr) : use_(use), input_ptr_(input_ptr) { |
| 377 | DCHECK_NOT_NULL(use); |
| 378 | DCHECK_NOT_NULL(input_ptr); |
| 379 | DCHECK_EQ(input_ptr, use->input_ptr()); |
| 380 | } |
| 381 | |
| 382 | Node::Use* use_; |
| 383 | Node** input_ptr_; |
| 384 | }; |
| 385 | |
| 386 | |
| 387 | // A forward iterator to visit the edges for the input dependencies of a node. |
| 388 | class Node::InputEdges::iterator final { |
| 389 | public: |
| 390 | typedef std::forward_iterator_tag iterator_category; |
| 391 | typedef int difference_type; |
| 392 | typedef Edge value_type; |
| 393 | typedef Edge* pointer; |
| 394 | typedef Edge& reference; |
| 395 | |
| 396 | iterator() : use_(nullptr), input_ptr_(nullptr) {} |
| 397 | iterator(const iterator& other) |
| 398 | : use_(other.use_), input_ptr_(other.input_ptr_) {} |
| 399 | |
| 400 | Edge operator*() const { return Edge(use_, input_ptr_); } |
| 401 | bool operator==(const iterator& other) const { |
| 402 | return input_ptr_ == other.input_ptr_; |
| 403 | } |
| 404 | bool operator!=(const iterator& other) const { return !(*this == other); } |
| 405 | iterator& operator++() { |
| 406 | input_ptr_++; |
| 407 | use_--; |
| 408 | return *this; |
| 409 | } |
| 410 | iterator operator++(int); |
| 411 | |
| 412 | private: |
| 413 | friend class Node; |
| 414 | |
| 415 | explicit iterator(Node* from, int index = 0) |
| 416 | : use_(from->GetUsePtr(index)), input_ptr_(from->GetInputPtr(index)) {} |
| 417 | |
| 418 | Use* use_; |
| 419 | Node** input_ptr_; |
| 420 | }; |
| 421 | |
| 422 | |
| 423 | Node::InputEdges::iterator Node::InputEdges::begin() const { |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 424 | return Node::InputEdges::iterator(this->node_, 0); |
| 425 | } |
| 426 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 427 | |
| 428 | Node::InputEdges::iterator Node::InputEdges::end() const { |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 429 | return Node::InputEdges::iterator(this->node_, this->node_->InputCount()); |
| 430 | } |
| 431 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 432 | |
| 433 | // A forward iterator to visit the inputs of a node. |
| 434 | class Node::Inputs::const_iterator final { |
| 435 | public: |
| 436 | typedef std::forward_iterator_tag iterator_category; |
| 437 | typedef int difference_type; |
| 438 | typedef Node* value_type; |
| 439 | typedef Node** pointer; |
| 440 | typedef Node*& reference; |
| 441 | |
| 442 | const_iterator(const const_iterator& other) : iter_(other.iter_) {} |
| 443 | |
| 444 | Node* operator*() const { return (*iter_).to(); } |
| 445 | bool operator==(const const_iterator& other) const { |
| 446 | return iter_ == other.iter_; |
| 447 | } |
| 448 | bool operator!=(const const_iterator& other) const { |
| 449 | return !(*this == other); |
| 450 | } |
| 451 | const_iterator& operator++() { |
| 452 | ++iter_; |
| 453 | return *this; |
| 454 | } |
| 455 | const_iterator operator++(int); |
| 456 | |
| 457 | private: |
| 458 | friend class Node::Inputs; |
| 459 | |
| 460 | const_iterator(Node* node, int index) : iter_(node, index) {} |
| 461 | |
| 462 | Node::InputEdges::iterator iter_; |
| 463 | }; |
| 464 | |
| 465 | |
| 466 | Node::Inputs::const_iterator Node::Inputs::begin() const { |
| 467 | return const_iterator(this->node_, 0); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 468 | } |
| 469 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 470 | |
| 471 | Node::Inputs::const_iterator Node::Inputs::end() const { |
| 472 | return const_iterator(this->node_, this->node_->InputCount()); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 473 | } |
| 474 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 475 | |
| 476 | // A forward iterator to visit the uses edges of a node. |
| 477 | class Node::UseEdges::iterator final { |
| 478 | public: |
| 479 | iterator(const iterator& other) |
| 480 | : current_(other.current_), next_(other.next_) {} |
| 481 | |
| 482 | Edge operator*() const { return Edge(current_, current_->input_ptr()); } |
| 483 | bool operator==(const iterator& other) const { |
| 484 | return current_ == other.current_; |
| 485 | } |
| 486 | bool operator!=(const iterator& other) const { return !(*this == other); } |
| 487 | iterator& operator++() { |
| 488 | DCHECK_NOT_NULL(current_); |
| 489 | current_ = next_; |
| 490 | next_ = current_ ? current_->next : nullptr; |
| 491 | return *this; |
| 492 | } |
| 493 | iterator operator++(int); |
| 494 | |
| 495 | private: |
| 496 | friend class Node::UseEdges; |
| 497 | |
| 498 | iterator() : current_(nullptr), next_(nullptr) {} |
| 499 | explicit iterator(Node* node) |
| 500 | : current_(node->first_use_), |
| 501 | next_(current_ ? current_->next : nullptr) {} |
| 502 | |
| 503 | Node::Use* current_; |
| 504 | Node::Use* next_; |
| 505 | }; |
| 506 | |
| 507 | |
| 508 | Node::UseEdges::iterator Node::UseEdges::begin() const { |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 509 | return Node::UseEdges::iterator(this->node_); |
| 510 | } |
| 511 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 512 | |
| 513 | Node::UseEdges::iterator Node::UseEdges::end() const { |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 514 | return Node::UseEdges::iterator(); |
| 515 | } |
| 516 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 517 | |
| 518 | // A forward iterator to visit the uses of a node. |
| 519 | class Node::Uses::const_iterator final { |
| 520 | public: |
| 521 | typedef std::forward_iterator_tag iterator_category; |
| 522 | typedef int difference_type; |
| 523 | typedef Node* value_type; |
| 524 | typedef Node** pointer; |
| 525 | typedef Node*& reference; |
| 526 | |
| 527 | const_iterator(const const_iterator& other) : current_(other.current_) {} |
| 528 | |
| 529 | Node* operator*() const { return current_->from(); } |
| 530 | bool operator==(const const_iterator& other) const { |
| 531 | return other.current_ == current_; |
| 532 | } |
| 533 | bool operator!=(const const_iterator& other) const { |
| 534 | return other.current_ != current_; |
| 535 | } |
| 536 | const_iterator& operator++() { |
| 537 | DCHECK_NOT_NULL(current_); |
| 538 | current_ = current_->next; |
| 539 | return *this; |
| 540 | } |
| 541 | const_iterator operator++(int); |
| 542 | |
| 543 | private: |
| 544 | friend class Node::Uses; |
| 545 | |
| 546 | const_iterator() : current_(nullptr) {} |
| 547 | explicit const_iterator(Node* node) : current_(node->first_use_) {} |
| 548 | |
| 549 | Node::Use* current_; |
| 550 | }; |
| 551 | |
| 552 | |
| 553 | Node::Uses::const_iterator Node::Uses::begin() const { |
| 554 | return const_iterator(this->node_); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 555 | } |
| 556 | |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 557 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 558 | Node::Uses::const_iterator Node::Uses::end() const { return const_iterator(); } |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 559 | |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 560 | } // namespace compiler |
| 561 | } // namespace internal |
| 562 | } // namespace v8 |
| 563 | |
| 564 | #endif // V8_COMPILER_NODE_H_ |