deps/v8/src/compiler/node.cc

   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 #include "src/compiler/node.h"
   6
   7 #include <algorithm>
   8
   9 namespace v8 {
  10 namespace internal {
  11 namespace compiler {
  12
  13 Node* Node::New(Zone* zone, NodeId id, const Operator* op, int input_count,
  14                 Node** inputs, bool has_extensible_inputs) {
  15   size_t node_size = sizeof(Node) - sizeof(Input);
  16   int reserve_input_count = has_extensible_inputs ? kDefaultReservedInputs : 0;
  17   size_t inputs_size = std::max<size_t>(
  18       (input_count + reserve_input_count) * sizeof(Input), sizeof(InputDeque*));
  19   size_t uses_size = input_count * sizeof(Use);
  20   int size = static_cast<int>(node_size + inputs_size + uses_size);
  21   void* buffer = zone->New(size);
  22   Node* result = new (buffer) Node(id, op, input_count, reserve_input_count);
  23   Input* input = result->inputs_.static_;
  24   Use* use =
  25       reinterpret_cast<Use*>(reinterpret_cast<char*>(input) + inputs_size);
  26
  27   for (int current = 0; current < input_count; ++current) {
  28     Node* to = *inputs++;
  29     input->to = to;
  30     input->use = use;
  31     use->input_index = current;
  32     use->from = result;
  33     to->AppendUse(use);
  34     ++use;
  35     ++input;
  36   }
  37   return result;
  38 }
  39
  40
  41 void Node::Kill() {
  42   DCHECK_NOT_NULL(op());
  43   RemoveAllInputs();
  44   DCHECK(uses().empty());
  45 }
  46
  47
  48 void Node::AppendInput(Zone* zone, Node* new_to) {
  49   DCHECK_NOT_NULL(zone);
  50   DCHECK_NOT_NULL(new_to);
  51   Use* new_use = new (zone) Use;
  52   Input new_input;
  53   new_input.to = new_to;
  54   new_input.use = new_use;
  55   if (reserved_input_count() > 0) {
  56     DCHECK(!has_appendable_inputs());
  57     set_reserved_input_count(reserved_input_count() - 1);
  58     inputs_.static_[input_count()] = new_input;
  59   } else {
  60     EnsureAppendableInputs(zone);
  61     inputs_.appendable_->push_back(new_input);
  62   }
  63   new_use->input_index = input_count();
  64   new_use->from = this;
  65   new_to->AppendUse(new_use);
  66   set_input_count(input_count() + 1);
  67 }
  68
  69
  70 void Node::InsertInput(Zone* zone, int index, Node* new_to) {
  71   DCHECK_NOT_NULL(zone);
  72   DCHECK_LE(0, index);
  73   DCHECK_LT(index, InputCount());
  74   AppendInput(zone, InputAt(InputCount() - 1));
  75   for (int i = InputCount() - 1; i > index; --i) {
  76     ReplaceInput(i, InputAt(i - 1));
  77   }
  78   ReplaceInput(index, new_to);
  79 }
  80
  81
  82 void Node::RemoveInput(int index) {
  83   DCHECK_LE(0, index);
  84   DCHECK_LT(index, InputCount());
  85   for (; index < InputCount() - 1; ++index) {
  86     ReplaceInput(index, InputAt(index + 1));
  87   }
  88   TrimInputCount(InputCount() - 1);
  89 }
  90
  91
  92 void Node::RemoveAllInputs() {
  93   for (Edge edge : input_edges()) edge.UpdateTo(nullptr);
  94 }
  95
  96
  97 void Node::TrimInputCount(int new_input_count) {
  98   DCHECK_LE(new_input_count, input_count());
  99   if (new_input_count == input_count()) return;  // Nothing to do.
 100   for (int index = new_input_count; index < input_count(); ++index) {
 101     ReplaceInput(index, nullptr);
 102   }
 103   if (!has_appendable_inputs()) {
 104     set_reserved_input_count(std::min<int>(
 105         ReservedInputCountField::kMax,
 106         reserved_input_count() + (input_count() - new_input_count)));
 107   }
 108   set_input_count(new_input_count);
 109 }
 110
 111
 112 int Node::UseCount() const {
 113   int use_count = 0;
 114   for (const Use* use = first_use_; use; use = use->next) {
 115     ++use_count;
 116   }
 117   return use_count;
 118 }
 119
 120
 121 Node* Node::UseAt(int index) const {
 122   DCHECK_LE(0, index);
 123   DCHECK_LT(index, UseCount());
 124   const Use* use = first_use_;
 125   while (index-- != 0) {
 126     use = use->next;
 127   }
 128   return use->from;
 129 }
 130
 131
 132 void Node::ReplaceUses(Node* replace_to) {
 133   for (Use* use = first_use_; use; use = use->next) {
 134     use->from->GetInputRecordPtr(use->input_index)->to = replace_to;
 135   }
 136   if (!replace_to->last_use_) {
 137     DCHECK(!replace_to->first_use_);
 138     replace_to->first_use_ = first_use_;
 139     replace_to->last_use_ = last_use_;
 140   } else if (first_use_) {
 141     DCHECK_NOT_NULL(replace_to->first_use_);
 142     replace_to->last_use_->next = first_use_;
 143     first_use_->prev = replace_to->last_use_;
 144     replace_to->last_use_ = last_use_;
 145   }
 146   first_use_ = nullptr;
 147   last_use_ = nullptr;
 148 }
 149
 150
 151 void Node::Input::Update(Node* new_to) {
 152   Node* old_to = this->to;
 153   if (new_to == old_to) return;  // Nothing to do.
 154   // Snip out the use from where it used to be
 155   if (old_to) {
 156     old_to->RemoveUse(use);
 157   }
 158   to = new_to;
 159   // And put it into the new node's use list.
 160   if (new_to) {
 161     new_to->AppendUse(use);
 162   } else {
 163     use->next = nullptr;
 164     use->prev = nullptr;
 165   }
 166 }
 167
 168
 169 Node::Node(NodeId id, const Operator* op, int input_count,
 170            int reserved_input_count)
 171     : op_(op),
 172       mark_(0),
 173       id_(id),
 174       bit_field_(InputCountField::encode(input_count) |
 175                  ReservedInputCountField::encode(reserved_input_count) |
 176                  HasAppendableInputsField::encode(false)),
 177       first_use_(nullptr),
 178       last_use_(nullptr) {}
 179
 180
 181 void Node::EnsureAppendableInputs(Zone* zone) {
 182   if (!has_appendable_inputs()) {
 183     void* deque_buffer = zone->New(sizeof(InputDeque));
 184     InputDeque* deque = new (deque_buffer) InputDeque(zone);
 185     for (int i = 0; i < input_count(); ++i) {
 186       deque->push_back(inputs_.static_[i]);
 187     }
 188     inputs_.appendable_ = deque;
 189     set_has_appendable_inputs(true);
 190   }
 191 }
 192
 193
 194 void Node::AppendUse(Use* const use) {
 195   use->next = nullptr;
 196   use->prev = last_use_;
 197   if (last_use_) {
 198     last_use_->next = use;
 199   } else {
 200     first_use_ = use;
 201   }
 202   last_use_ = use;
 203 }
 204
 205
 206 void Node::RemoveUse(Use* const use) {
 207   if (use == last_use_) {
 208     last_use_ = use->prev;
 209   }
 210   if (use->prev) {
 211     use->prev->next = use->next;
 212   } else {
 213     first_use_ = use->next;
 214   }
 215   if (use->next) {
 216     use->next->prev = use->prev;
 217   }
 218 }
 219
 220
 221 std::ostream& operator<<(std::ostream& os, const Node& n) {
 222   os << n.id() << ": " << *n.op();
 223   if (n.InputCount() > 0) {
 224     os << "(";
 225     for (int i = 0; i < n.InputCount(); ++i) {
 226       if (i != 0) os << ", ";
 227       os << n.InputAt(i)->id();
 228     }
 229     os << ")";
 230   }
 231   return os;
 232 }
 233
 234
 235 Node::InputEdges::iterator Node::InputEdges::iterator::operator++(int n) {
 236   iterator result(*this);
 237   ++(*this);
 238   return result;
 239 }
 240
 241
 242 bool Node::InputEdges::empty() const { return begin() == end(); }
 243
 244
 245 Node::Inputs::const_iterator Node::Inputs::const_iterator::operator++(int n) {
 246   const_iterator result(*this);
 247   ++(*this);
 248   return result;
 249 }
 250
 251
 252 bool Node::Inputs::empty() const { return begin() == end(); }
 253
 254
 255 Node::UseEdges::iterator Node::UseEdges::iterator::operator++(int n) {
 256   iterator result(*this);
 257   ++(*this);
 258   return result;
 259 }
 260
 261
 262 bool Node::UseEdges::empty() const { return begin() == end(); }
 263
 264
 265 Node::Uses::const_iterator Node::Uses::const_iterator::operator++(int n) {
 266   const_iterator result(*this);
 267   ++(*this);
 268   return result;
 269 }
 270
 271
 272 bool Node::Uses::empty() const { return begin() == end(); }
 273
 274 }  // namespace compiler
 275 }  // namespace internal
 276 }  // namespace v8