1b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// Copyright 2013 the V8 project authors. All rights reserved. 2b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// Use of this source code is governed by a BSD-style license that can be 3b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// found in the LICENSE file. 4b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 5b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#ifndef V8_COMPILER_NODE_H_ 6b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#define V8_COMPILER_NODE_H_ 7b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 8b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#include "src/compiler/opcodes.h" 9b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#include "src/compiler/operator.h" 10f3b273f5e6ffd2f6ba1c18a27a17db41dfb113c3Ben Murdoch#include "src/compiler/types.h" 11c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen Murdoch#include "src/globals.h" 12f3b273f5e6ffd2f6ba1c18a27a17db41dfb113c3Ben Murdoch#include "src/zone/zone-containers.h" 13b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 14b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochnamespace v8 { 15b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochnamespace internal { 16b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochnamespace compiler { 17b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 18958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier// Forward declarations. 19958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernierclass Edge; 20958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernierclass Graph; 21958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 22958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 23958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier// Marks are used during traversal of the graph to distinguish states of nodes. 24958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier// Each node has a mark which is a monotonically increasing integer, and a 25958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier// {NodeMarker} has a range of values that indicate states of a node. 26958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Berniertypedef uint32_t Mark; 27958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 28014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 29958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier// NodeIds are identifying numbers for nodes that can be used to index auxiliary 30958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier// out-of-line data associated with each node. 31014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochtypedef uint32_t NodeId; 32014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 33958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 34958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier// A Node is the basic primitive of graphs. Nodes are chained together by 35958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier// input/use chains but by default otherwise contain only an identifying number 36958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier// which specific applications of graphs and nodes can use to index auxiliary 37958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier// out-of-line data, especially transient data. 38958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier// 39958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier// In addition Nodes only contain a mutable Operator that may change during 40958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier// compilation, e.g. during lowering passes. Other information that needs to be 41958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier// associated with Nodes during compilation must be stored out-of-line indexed 42958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier// by the Node's id. 43c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen Murdochclass V8_EXPORT_PRIVATE Node final { 44b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch public: 45014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch static Node* New(Zone* zone, NodeId id, const Operator* op, int input_count, 46014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Node* const* inputs, bool has_extensible_inputs); 47014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch static Node* Clone(Zone* zone, NodeId id, const Node* node); 48958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 4962ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch inline bool IsDead() const; 50958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier void Kill(); 51958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 52b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch const Operator* op() const { return op_; } 53b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 54b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch IrOpcode::Value opcode() const { 55b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(op_->opcode() <= IrOpcode::kLast); 56b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return static_cast<IrOpcode::Value>(op_->opcode()); 57b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 58b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 59014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch NodeId id() const { return IdField::decode(bit_field_); } 60014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 61014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int InputCount() const { 62014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return has_inline_inputs() ? InlineCountField::decode(bit_field_) 63014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch : inputs_.outline_->count_; 64014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 65014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 66014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch#if DEBUG 67014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void Verify(); 68014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch#define BOUNDS_CHECK(index) \ 69014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch do { \ 70014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (index < 0 || index >= InputCount()) { \ 71014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch V8_Fatal(__FILE__, __LINE__, "Node #%d:%s->InputAt(%d) out of bounds", \ 72014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch id(), op()->mnemonic(), index); \ 73014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } \ 74014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } while (false) 75014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch#else 76014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // No bounds checks or verification in release mode. 77014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch inline void Verify() {} 78014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch#define BOUNDS_CHECK(index) \ 79014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch do { \ 80014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } while (false) 81014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch#endif 82014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 83014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Node* InputAt(int index) const { 84014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch BOUNDS_CHECK(index); 85014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return *GetInputPtrConst(index); 86014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 87014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 88014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void ReplaceInput(int index, Node* new_to) { 89014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch BOUNDS_CHECK(index); 90014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Node** input_ptr = GetInputPtr(index); 91014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Node* old_to = *input_ptr; 92014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (old_to != new_to) { 93014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Use* use = GetUsePtr(index); 94014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (old_to) old_to->RemoveUse(use); 95014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch *input_ptr = new_to; 96014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (new_to) new_to->AppendUse(use); 97014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 98014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 99958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 100014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch#undef BOUNDS_CHECK 101958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 102014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void AppendInput(Zone* zone, Node* new_to); 103014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void InsertInput(Zone* zone, int index, Node* new_to); 104f91f0611dbaf29ca0f1d4aecb357ce243a19d2faBen Murdoch void InsertInputs(Zone* zone, int index, int count); 105014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void RemoveInput(int index); 106014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void NullAllInputs(); 107014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void TrimInputCount(int new_input_count); 108958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 109014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int UseCount() const; 110014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void ReplaceUses(Node* replace_to); 111958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 11262ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch class InputEdges; 11362ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch inline InputEdges input_edges(); 114014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 11562ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch class Inputs; 11662ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch inline Inputs inputs() const; 117958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 118014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch class UseEdges final { 119958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier public: 120014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch typedef Edge value_type; 121014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 122958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier class iterator; 123014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch inline iterator begin() const; 124014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch inline iterator end() const; 125014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 126958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier bool empty() const; 127958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 128958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier explicit UseEdges(Node* node) : node_(node) {} 129958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 130958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier private: 131958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier Node* node_; 132958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier }; 133958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 134014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch UseEdges use_edges() { return UseEdges(this); } 135014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 136c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen Murdoch class V8_EXPORT_PRIVATE Uses final { 137958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier public: 138014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch typedef Node* value_type; 139014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 140014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch class const_iterator; 141014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch inline const_iterator begin() const; 142014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch inline const_iterator end() const; 143014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 144958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier bool empty() const; 145958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 146958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier explicit Uses(Node* node) : node_(node) {} 147958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 148958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier private: 149958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier Node* node_; 150958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier }; 151958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 152958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier Uses uses() { return Uses(this); } 153958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 154014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Returns true if {owner} is the user of {this} node. 155014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch bool OwnedBy(Node* owner) const { 156014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return first_use_ && first_use_->from() == owner && !first_use_->next; 157014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 158958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 159014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Returns true if {owner1} and {owner2} are the only users of {this} node. 160014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch bool OwnedBy(Node const* owner1, Node const* owner2) const; 16162ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch 16262ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch // Returns true if addressing related operands (such as load, store, lea) 16362ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch // are the only users of {this} node. 16462ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch bool OwnedByAddressingOperand() const; 165014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void Print() const; 166b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 167014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch private: 168014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch struct Use; 169014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Out of line storage for inputs when the number of inputs overflowed the 170014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // capacity of the inline-allocated space. 171014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch struct OutOfLineInputs { 172014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Node* node_; 173014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int count_; 174014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int capacity_; 175014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Node* inputs_[1]; 176958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 177014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch static OutOfLineInputs* New(Zone* zone, int capacity); 178014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void ExtractFrom(Use* use_ptr, Node** input_ptr, int count); 179014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch }; 180014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 181014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // A link in the use chain for a node. Every input {i} to a node {n} has an 182014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // associated {Use} which is linked into the use chain of the {i} node. 183014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch struct Use { 184958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier Use* next; 185958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier Use* prev; 186014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch uint32_t bit_field_; 187014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 188014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int input_index() const { return InputIndexField::decode(bit_field_); } 189014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch bool is_inline_use() const { return InlineField::decode(bit_field_); } 190014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Node** input_ptr() { 191014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int index = input_index(); 192014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Use* start = this + 1 + index; 193014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Node** inputs = is_inline_use() 194014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch ? reinterpret_cast<Node*>(start)->inputs_.inline_ 195014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch : reinterpret_cast<OutOfLineInputs*>(start)->inputs_; 196014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return &inputs[index]; 197014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 198958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 199014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Node* from() { 200014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Use* start = this + 1 + input_index(); 201014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return is_inline_use() ? reinterpret_cast<Node*>(start) 202014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch : reinterpret_cast<OutOfLineInputs*>(start)->node_; 203014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 204958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 205014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch typedef BitField<bool, 0, 1> InlineField; 206014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch typedef BitField<unsigned, 1, 17> InputIndexField; 207014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Leaving some space in the bitset in case we ever decide to record 208014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // the output index. 209958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier }; 210958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 211014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch //============================================================================ 212014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch //== Memory layout =========================================================== 213014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch //============================================================================ 214014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Saving space for big graphs is important. We use a memory layout trick to 215014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // be able to map {Node} objects to {Use} objects and vice-versa in a 216014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // space-efficient manner. 217014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // 218014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // {Use} links are laid out in memory directly before a {Node}, followed by 219014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // direct pointers to input {Nodes}. 220014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // 221014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // inline case: 222014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // |Use #N |Use #N-1|...|Use #1 |Use #0 |Node xxxx |I#0|I#1|...|I#N-1|I#N| 223014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // ^ ^ ^ 224014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // + Use + Node + Input 225014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // 226014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Since every {Use} instance records its {input_index}, pointer arithmetic 227014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // can compute the {Node}. 228014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // 229014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // out-of-line case: 230014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // |Node xxxx | 231014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // ^ + outline ------------------+ 232014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // +----------------------------------------+ 233014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // | | 234014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // v | node 235014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // |Use #N |Use #N-1|...|Use #1 |Use #0 |OOL xxxxx |I#0|I#1|...|I#N-1|I#N| 236014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // ^ ^ 237014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // + Use + Input 238014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // 239014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Out-of-line storage of input lists is needed if appending an input to 240014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // a node exceeds the maximum inline capacity. 241014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 242014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Node(NodeId id, const Operator* op, int inline_count, int inline_capacity); 243014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 244014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Node* const* GetInputPtrConst(int input_index) const { 245014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return has_inline_inputs() ? &(inputs_.inline_[input_index]) 246014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch : &inputs_.outline_->inputs_[input_index]; 247014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 248014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Node** GetInputPtr(int input_index) { 249014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return has_inline_inputs() ? &(inputs_.inline_[input_index]) 250014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch : &inputs_.outline_->inputs_[input_index]; 251014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 252014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Use* GetUsePtr(int input_index) { 253014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Use* ptr = has_inline_inputs() ? reinterpret_cast<Use*>(this) 254014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch : reinterpret_cast<Use*>(inputs_.outline_); 255014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return &ptr[-1 - input_index]; 256014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 257014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 258014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void AppendUse(Use* use); 259014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void RemoveUse(Use* use); 260958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 261958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier void* operator new(size_t, void* location) { return location; } 262958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 263014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Only NodeProperties should manipulate the op. 264014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void set_op(const Operator* op) { op_ = op; } 265958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 266014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Only NodeProperties should manipulate the type. 267014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Type* type() const { return type_; } 268014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void set_type(Type* type) { type_ = type; } 269958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 270958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier // Only NodeMarkers should manipulate the marks on nodes. 27162ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch Mark mark() const { return mark_; } 272958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier void set_mark(Mark mark) { mark_ = mark; } 273958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 274014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch inline bool has_inline_inputs() const { 275014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return InlineCountField::decode(bit_field_) != kOutlineMarker; 276958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier } 277958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 278014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void ClearInputs(int start, int count); 279958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 280014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch typedef BitField<NodeId, 0, 24> IdField; 281014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch typedef BitField<unsigned, 24, 4> InlineCountField; 282014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch typedef BitField<unsigned, 28, 4> InlineCapacityField; 283014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch static const int kOutlineMarker = InlineCountField::kMax; 284014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch static const int kMaxInlineCount = InlineCountField::kMax - 1; 285014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch static const int kMaxInlineCapacity = InlineCapacityField::kMax - 1; 286958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 287958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier const Operator* op_; 288014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Type* type_; 289958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier Mark mark_; 290014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch uint32_t bit_field_; 291014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Use* first_use_; 292958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier union { 293014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Inline storage for inputs or out-of-line storage. 294014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Node* inline_[1]; 295014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch OutOfLineInputs* outline_; 296958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier } inputs_; 297014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 298014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch friend class Edge; 299014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch friend class NodeMarkerBase; 300014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch friend class NodeProperties; 301958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 302958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier DISALLOW_COPY_AND_ASSIGN(Node); 303b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch}; 304b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 305958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 306014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochstd::ostream& operator<<(std::ostream& os, const Node& n); 307014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 308014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 309014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch// Typedefs to shorten commonly used Node containers. 310014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochtypedef ZoneDeque<Node*> NodeDeque; 311014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochtypedef ZoneSet<Node*> NodeSet; 312014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochtypedef ZoneVector<Node*> NodeVector; 313014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochtypedef ZoneVector<NodeVector> NodeVectorVector; 314014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 315014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 316014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch// Helper to extract parameters from Operator1<*> nodes. 317014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochtemplate <typename T> 318014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochstatic inline const T& OpParameter(const Node* node) { 319014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return OpParameter<T>(node->op()); 320014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch} 321014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 32262ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdochclass Node::InputEdges final { 32362ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch public: 32462ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch typedef Edge value_type; 32562ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch 32662ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch class iterator; 32762ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch inline iterator begin() const; 32862ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch inline iterator end() const; 32962ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch 33062ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch bool empty() const { return count_ == 0; } 33162ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch int count() const { return count_; } 33262ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch 33362ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch inline value_type operator[](int index) const; 33462ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch 33562ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch InputEdges(Node** input_root, Use* use_root, int count) 33662ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch : input_root_(input_root), use_root_(use_root), count_(count) {} 33762ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch 33862ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch private: 33962ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch Node** input_root_; 34062ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch Use* use_root_; 34162ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch int count_; 34262ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch}; 34362ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch 34462ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdochclass V8_EXPORT_PRIVATE Node::Inputs final { 34562ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch public: 34662ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch typedef Node* value_type; 34762ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch 34862ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch class const_iterator; 34962ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch inline const_iterator begin() const; 35062ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch inline const_iterator end() const; 35162ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch 35262ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch bool empty() const { return count_ == 0; } 35362ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch int count() const { return count_; } 35462ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch 35562ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch inline value_type operator[](int index) const; 35662ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch 35762ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch explicit Inputs(Node* const* input_root, int count) 35862ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch : input_root_(input_root), count_(count) {} 35962ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch 36062ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch private: 36162ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch Node* const* input_root_; 36262ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch int count_; 36362ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch}; 364014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 365958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier// An encapsulation for information associated with a single use of node as a 366958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier// input from another node, allowing access to both the defining node and 367958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier// the node having the input. 368014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochclass Edge final { 369b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch public: 370014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Node* from() const { return use_->from(); } 371014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Node* to() const { return *input_ptr_; } 372958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier int index() const { 373014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int const index = use_->input_index(); 374014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DCHECK_LT(index, use_->from()->InputCount()); 375958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier return index; 376958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier } 377b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 378014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch bool operator==(const Edge& other) { return input_ptr_ == other.input_ptr_; } 379958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier bool operator!=(const Edge& other) { return !(*this == other); } 380b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 381014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void UpdateTo(Node* new_to) { 382014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Node* old_to = *input_ptr_; 383014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (old_to != new_to) { 384014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (old_to) old_to->RemoveUse(use_); 385014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch *input_ptr_ = new_to; 386014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (new_to) new_to->AppendUse(use_); 387014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 388014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 389b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 390958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier private: 391958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier friend class Node::UseEdges::iterator; 39262ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch friend class Node::InputEdges; 393958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier friend class Node::InputEdges::iterator; 394958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 395014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Edge(Node::Use* use, Node** input_ptr) : use_(use), input_ptr_(input_ptr) { 396014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DCHECK_NOT_NULL(use); 397014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DCHECK_NOT_NULL(input_ptr); 398014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DCHECK_EQ(input_ptr, use->input_ptr()); 399014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 400958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 401014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Node::Use* use_; 402014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Node** input_ptr_; 403958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier}; 404958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 40562ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdochbool Node::IsDead() const { 40662ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch Node::Inputs inputs = this->inputs(); 40762ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch return inputs.count() > 0 && inputs[0] == nullptr; 40862ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch} 40962ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch 41062ed631aa0ff23db68a47fd423efa9c019ff2c9eBen MurdochNode::InputEdges Node::input_edges() { 41162ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch int inline_count = InlineCountField::decode(bit_field_); 41262ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch if (inline_count != kOutlineMarker) { 41362ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch return InputEdges(inputs_.inline_, reinterpret_cast<Use*>(this) - 1, 41462ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch inline_count); 41562ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch } else { 41662ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch return InputEdges(inputs_.outline_->inputs_, 41762ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch reinterpret_cast<Use*>(inputs_.outline_) - 1, 41862ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch inputs_.outline_->count_); 41962ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch } 42062ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch} 42162ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch 42262ed631aa0ff23db68a47fd423efa9c019ff2c9eBen MurdochNode::Inputs Node::inputs() const { 42362ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch int inline_count = InlineCountField::decode(bit_field_); 42462ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch if (inline_count != kOutlineMarker) { 42562ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch return Inputs(inputs_.inline_, inline_count); 42662ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch } else { 42762ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch return Inputs(inputs_.outline_->inputs_, inputs_.outline_->count_); 42862ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch } 42962ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch} 430958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 431014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch// A forward iterator to visit the edges for the input dependencies of a node. 432014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochclass Node::InputEdges::iterator final { 433958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier public: 434958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier typedef std::forward_iterator_tag iterator_category; 43562ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch typedef std::ptrdiff_t difference_type; 436958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier typedef Edge value_type; 437958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier typedef Edge* pointer; 438958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier typedef Edge& reference; 439958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 440014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch iterator() : use_(nullptr), input_ptr_(nullptr) {} 441014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch iterator(const iterator& other) 442014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch : use_(other.use_), input_ptr_(other.input_ptr_) {} 443014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 444014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Edge operator*() const { return Edge(use_, input_ptr_); } 445014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch bool operator==(const iterator& other) const { 446014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return input_ptr_ == other.input_ptr_; 447014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 448014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch bool operator!=(const iterator& other) const { return !(*this == other); } 449958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier iterator& operator++() { 450014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch input_ptr_++; 451014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch use_--; 452958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier return *this; 453958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier } 454014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch iterator operator++(int); 45562ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch iterator& operator+=(difference_type offset) { 45662ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch input_ptr_ += offset; 45762ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch use_ -= offset; 45862ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch return *this; 45962ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch } 46062ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch iterator operator+(difference_type offset) const { 46162ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch return iterator(use_ - offset, input_ptr_ + offset); 46262ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch } 46362ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch difference_type operator-(const iterator& other) const { 46462ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch return input_ptr_ - other.input_ptr_; 46562ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch } 466958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 467958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier private: 468958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier friend class Node; 469958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 47062ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch explicit iterator(Use* use, Node** input_ptr) 47162ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch : use_(use), input_ptr_(input_ptr) {} 472958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 473014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Use* use_; 474014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Node** input_ptr_; 475958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier}; 476958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 477958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 478014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben MurdochNode::InputEdges::iterator Node::InputEdges::begin() const { 47962ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch return Node::InputEdges::iterator(use_root_, input_root_); 480014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch} 481014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 482014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 483014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben MurdochNode::InputEdges::iterator Node::InputEdges::end() const { 48462ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch return Node::InputEdges::iterator(use_root_ - count_, input_root_ + count_); 485014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch} 486014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 48762ed631aa0ff23db68a47fd423efa9c019ff2c9eBen MurdochEdge Node::InputEdges::operator[](int index) const { 48862ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch return Edge(use_root_ + index, input_root_ + index); 48962ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch} 490014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 491958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier// A forward iterator to visit the inputs of a node. 492014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochclass Node::Inputs::const_iterator final { 493958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier public: 494958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier typedef std::forward_iterator_tag iterator_category; 49562ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch typedef std::ptrdiff_t difference_type; 496958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier typedef Node* value_type; 49762ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch typedef const value_type* pointer; 49862ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch typedef value_type& reference; 499958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 50062ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch const_iterator(const const_iterator& other) : input_ptr_(other.input_ptr_) {} 501958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 50262ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch Node* operator*() const { return *input_ptr_; } 503014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch bool operator==(const const_iterator& other) const { 50462ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch return input_ptr_ == other.input_ptr_; 505014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 506014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch bool operator!=(const const_iterator& other) const { 507014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return !(*this == other); 508014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 509014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch const_iterator& operator++() { 51062ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch ++input_ptr_; 511958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier return *this; 512958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier } 513014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch const_iterator operator++(int); 51462ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch const_iterator& operator+=(difference_type offset) { 51562ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch input_ptr_ += offset; 51662ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch return *this; 51762ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch } 51862ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch const_iterator operator+(difference_type offset) const { 51962ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch return const_iterator(input_ptr_ + offset); 52062ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch } 52162ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch difference_type operator-(const const_iterator& other) const { 52262ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch return input_ptr_ - other.input_ptr_; 52362ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch } 524958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 525958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier private: 526958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier friend class Node::Inputs; 527958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 52862ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch explicit const_iterator(Node* const* input_ptr) : input_ptr_(input_ptr) {} 529958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 53062ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch Node* const* input_ptr_; 531958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier}; 532958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 533958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 534014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben MurdochNode::Inputs::const_iterator Node::Inputs::begin() const { 53562ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch return const_iterator(input_root_); 536014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch} 537958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 538958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 539014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben MurdochNode::Inputs::const_iterator Node::Inputs::end() const { 54062ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch return const_iterator(input_root_ + count_); 541014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch} 542958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 54362ed631aa0ff23db68a47fd423efa9c019ff2c9eBen MurdochNode* Node::Inputs::operator[](int index) const { return input_root_[index]; } 544958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 545014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch// A forward iterator to visit the uses edges of a node. 546014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochclass Node::UseEdges::iterator final { 547958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier public: 548014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch iterator(const iterator& other) 549014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch : current_(other.current_), next_(other.next_) {} 550958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 551014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Edge operator*() const { return Edge(current_, current_->input_ptr()); } 552014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch bool operator==(const iterator& other) const { 553014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return current_ == other.current_; 554014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 555014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch bool operator!=(const iterator& other) const { return !(*this == other); } 556958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier iterator& operator++() { 557014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DCHECK_NOT_NULL(current_); 558014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch current_ = next_; 559014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch next_ = current_ ? current_->next : nullptr; 560958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier return *this; 561958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier } 562014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch iterator operator++(int); 563958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 564958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier private: 565014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch friend class Node::UseEdges; 566958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 567014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch iterator() : current_(nullptr), next_(nullptr) {} 568014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch explicit iterator(Node* node) 569014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch : current_(node->first_use_), 570014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch next_(current_ ? current_->next : nullptr) {} 571958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 572958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier Node::Use* current_; 573014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Node::Use* next_; 574b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch}; 575b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 576b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 577014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben MurdochNode::UseEdges::iterator Node::UseEdges::begin() const { 578958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier return Node::UseEdges::iterator(this->node_); 579958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier} 580958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 581958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 582014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben MurdochNode::UseEdges::iterator Node::UseEdges::end() const { 583014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return Node::UseEdges::iterator(); 584958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier} 585958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 586958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 587014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch// A forward iterator to visit the uses of a node. 588014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochclass Node::Uses::const_iterator final { 589014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch public: 590014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch typedef std::forward_iterator_tag iterator_category; 591014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch typedef int difference_type; 592014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch typedef Node* value_type; 593014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch typedef Node** pointer; 594014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch typedef Node*& reference; 595958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 596014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch const_iterator(const const_iterator& other) : current_(other.current_) {} 597958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 598014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Node* operator*() const { return current_->from(); } 599014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch bool operator==(const const_iterator& other) const { 600014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return other.current_ == current_; 601958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier } 602014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch bool operator!=(const const_iterator& other) const { 603014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return other.current_ != current_; 604958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier } 605014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch const_iterator& operator++() { 606014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DCHECK_NOT_NULL(current_); 607014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch current_ = current_->next; 608014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return *this; 609958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier } 610014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch const_iterator operator++(int); 611958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 612014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch private: 613014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch friend class Node::Uses; 614958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 615014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch const_iterator() : current_(nullptr) {} 616014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch explicit const_iterator(Node* node) : current_(node->first_use_) {} 617958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 618014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Node::Use* current_; 619014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch}; 620958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 621958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 622014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben MurdochNode::Uses::const_iterator Node::Uses::begin() const { 623014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return const_iterator(this->node_); 624958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier} 625958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 626958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 627014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben MurdochNode::Uses::const_iterator Node::Uses::end() const { return const_iterator(); } 628958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 629b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} // namespace compiler 630b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} // namespace internal 631b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} // namespace v8 632b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 633b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#endif // V8_COMPILER_NODE_H_ 634