Home | History | Annotate | Download | only in compiler 
      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 namespace v8 {
      8 namespace internal {
      9 namespace compiler {
     10 
     11 Node::OutOfLineInputs* Node::OutOfLineInputs::New(Zone* zone, int capacity) {
     12   size_t size =
     13       sizeof(OutOfLineInputs) + capacity * (sizeof(Node*) + sizeof(Use));
     14   intptr_t raw_buffer = reinterpret_cast<intptr_t>(zone->New(size));
     15   Node::OutOfLineInputs* outline =
     16       reinterpret_cast<OutOfLineInputs*>(raw_buffer + capacity * sizeof(Use));
     17   outline->capacity_ = capacity;
     18   outline->count_ = 0;
     19   return outline;
     20 }
     21 
     22 
     23 void Node::OutOfLineInputs::ExtractFrom(Use* old_use_ptr, Node** old_input_ptr,
     24                                         int count) {
     25   // Extract the inputs from the old use and input pointers and copy them
     26   // to this out-of-line-storage.
     27   Use* new_use_ptr = reinterpret_cast<Use*>(this) - 1;
     28   Node** new_input_ptr = inputs_;
     29   for (int current = 0; current < count; current++) {
     30     new_use_ptr->bit_field_ =
     31         Use::InputIndexField::encode(current) | Use::InlineField::encode(false);
     32     DCHECK_EQ(old_input_ptr, old_use_ptr->input_ptr());
     33     DCHECK_EQ(new_input_ptr, new_use_ptr->input_ptr());
     34     Node* old_to = *old_input_ptr;
     35     if (old_to) {
     36       *old_input_ptr = nullptr;
     37       old_to->RemoveUse(old_use_ptr);
     38       *new_input_ptr = old_to;
     39       old_to->AppendUse(new_use_ptr);
     40     } else {
     41       *new_input_ptr = nullptr;
     42     }
     43     old_input_ptr++;
     44     new_input_ptr++;
     45     old_use_ptr--;
     46     new_use_ptr--;
     47   }
     48   this->count_ = count;
     49 }
     50 
     51 
     52 Node* Node::New(Zone* zone, NodeId id, const Operator* op, int input_count,
     53                 Node* const* inputs, bool has_extensible_inputs) {
     54   Node** input_ptr;
     55   Use* use_ptr;
     56   Node* node;
     57   bool is_inline;
     58 
     59 #if DEBUG
     60   // Verify that none of the inputs are {nullptr}.
     61   for (int i = 0; i < input_count; i++) {
     62     if (inputs[i] == nullptr) {
     63       V8_Fatal(__FILE__, __LINE__, "Node::New() Error: #%d:%s[%d] is nullptr",
     64                static_cast<int>(id), op->mnemonic(), i);
     65     }
     66   }
     67 #endif
     68 
     69   if (input_count > kMaxInlineCapacity) {
     70     // Allocate out-of-line inputs.
     71     int capacity =
     72         has_extensible_inputs ? input_count + kMaxInlineCapacity : input_count;
     73     OutOfLineInputs* outline = OutOfLineInputs::New(zone, capacity);
     74 
     75     // Allocate node.
     76     void* node_buffer = zone->New(sizeof(Node));
     77     node = new (node_buffer) Node(id, op, kOutlineMarker, 0);
     78     node->inputs_.outline_ = outline;
     79 
     80     outline->node_ = node;
     81     outline->count_ = input_count;
     82 
     83     input_ptr = outline->inputs_;
     84     use_ptr = reinterpret_cast<Use*>(outline);
     85     is_inline = false;
     86   } else {
     87     // Allocate node with inline inputs.
     88     int capacity = input_count;
     89     if (has_extensible_inputs) {
     90       const int max = kMaxInlineCapacity;
     91       capacity = std::min(input_count + 3, max);
     92     }
     93 
     94     size_t size = sizeof(Node) + capacity * (sizeof(Node*) + sizeof(Use));
     95     intptr_t raw_buffer = reinterpret_cast<intptr_t>(zone->New(size));
     96     void* node_buffer =
     97         reinterpret_cast<void*>(raw_buffer + capacity * sizeof(Use));
     98 
     99     node = new (node_buffer) Node(id, op, input_count, capacity);
    100     input_ptr = node->inputs_.inline_;
    101     use_ptr = reinterpret_cast<Use*>(node);
    102     is_inline = true;
    103   }
    104 
    105   // Initialize the input pointers and the uses.
    106   for (int current = 0; current < input_count; ++current) {
    107     Node* to = *inputs++;
    108     input_ptr[current] = to;
    109     Use* use = use_ptr - 1 - current;
    110     use->bit_field_ = Use::InputIndexField::encode(current) |
    111                       Use::InlineField::encode(is_inline);
    112     to->AppendUse(use);
    113   }
    114   node->Verify();
    115   return node;
    116 }
    117 
    118 
    119 Node* Node::Clone(Zone* zone, NodeId id, const Node* node) {
    120   int const input_count = node->InputCount();
    121   Node* const* const inputs = node->has_inline_inputs()
    122                                   ? node->inputs_.inline_
    123                                   : node->inputs_.outline_->inputs_;
    124   Node* const clone = New(zone, id, node->op(), input_count, inputs, false);
    125   clone->set_type(node->type());
    126   return clone;
    127 }
    128 
    129 
    130 void Node::Kill() {
    131   DCHECK_NOT_NULL(op());
    132   NullAllInputs();
    133   DCHECK(uses().empty());
    134 }
    135 
    136 
    137 void Node::AppendInput(Zone* zone, Node* new_to) {
    138   DCHECK_NOT_NULL(zone);
    139   DCHECK_NOT_NULL(new_to);
    140 
    141   int inline_count = InlineCountField::decode(bit_field_);
    142   int inline_capacity = InlineCapacityField::decode(bit_field_);
    143   if (inline_count < inline_capacity) {
    144     // Append inline input.
    145     bit_field_ = InlineCountField::update(bit_field_, inline_count + 1);
    146     *GetInputPtr(inline_count) = new_to;
    147     Use* use = GetUsePtr(inline_count);
    148     use->bit_field_ = Use::InputIndexField::encode(inline_count) |
    149                       Use::InlineField::encode(true);
    150     new_to->AppendUse(use);
    151   } else {
    152     // Append out-of-line input.
    153     int input_count = InputCount();
    154     OutOfLineInputs* outline = nullptr;
    155     if (inline_count != kOutlineMarker) {
    156       // switch to out of line inputs.
    157       outline = OutOfLineInputs::New(zone, input_count * 2 + 3);
    158       outline->node_ = this;
    159       outline->ExtractFrom(GetUsePtr(0), GetInputPtr(0), input_count);
    160       bit_field_ = InlineCountField::update(bit_field_, kOutlineMarker);
    161       inputs_.outline_ = outline;
    162     } else {
    163       // use current out of line inputs.
    164       outline = inputs_.outline_;
    165       if (input_count >= outline->capacity_) {
    166         // out of space in out-of-line inputs.
    167         outline = OutOfLineInputs::New(zone, input_count * 2 + 3);
    168         outline->node_ = this;
    169         outline->ExtractFrom(GetUsePtr(0), GetInputPtr(0), input_count);
    170         inputs_.outline_ = outline;
    171       }
    172     }
    173     outline->count_++;
    174     *GetInputPtr(input_count) = new_to;
    175     Use* use = GetUsePtr(input_count);
    176     use->bit_field_ = Use::InputIndexField::encode(input_count) |
    177                       Use::InlineField::encode(false);
    178     new_to->AppendUse(use);
    179   }
    180   Verify();
    181 }
    182 
    183 
    184 void Node::InsertInput(Zone* zone, int index, Node* new_to) {
    185   DCHECK_NOT_NULL(zone);
    186   DCHECK_LE(0, index);
    187   DCHECK_LT(index, InputCount());
    188   AppendInput(zone, InputAt(InputCount() - 1));
    189   for (int i = InputCount() - 1; i > index; --i) {
    190     ReplaceInput(i, InputAt(i - 1));
    191   }
    192   ReplaceInput(index, new_to);
    193   Verify();
    194 }
    195 
    196 
    197 void Node::RemoveInput(int index) {
    198   DCHECK_LE(0, index);
    199   DCHECK_LT(index, InputCount());
    200   for (; index < InputCount() - 1; ++index) {
    201     ReplaceInput(index, InputAt(index + 1));
    202   }
    203   TrimInputCount(InputCount() - 1);
    204   Verify();
    205 }
    206 
    207 
    208 void Node::ClearInputs(int start, int count) {
    209   Node** input_ptr = GetInputPtr(start);
    210   Use* use_ptr = GetUsePtr(start);
    211   while (count-- > 0) {
    212     DCHECK_EQ(input_ptr, use_ptr->input_ptr());
    213     Node* input = *input_ptr;
    214     *input_ptr = nullptr;
    215     if (input) input->RemoveUse(use_ptr);
    216     input_ptr++;
    217     use_ptr--;
    218   }
    219   Verify();
    220 }
    221 
    222 
    223 void Node::NullAllInputs() { ClearInputs(0, InputCount()); }
    224 
    225 
    226 void Node::TrimInputCount(int new_input_count) {
    227   int current_count = InputCount();
    228   DCHECK_LE(new_input_count, current_count);
    229   if (new_input_count == current_count) return;  // Nothing to do.
    230   ClearInputs(new_input_count, current_count - new_input_count);
    231   if (has_inline_inputs()) {
    232     bit_field_ = InlineCountField::update(bit_field_, new_input_count);
    233   } else {
    234     inputs_.outline_->count_ = new_input_count;
    235   }
    236 }
    237 
    238 
    239 int Node::UseCount() const {
    240   int use_count = 0;
    241   for (const Use* use = first_use_; use; use = use->next) {
    242     ++use_count;
    243   }
    244   return use_count;
    245 }
    246 
    247 
    248 void Node::ReplaceUses(Node* that) {
    249   DCHECK(this->first_use_ == nullptr || this->first_use_->prev == nullptr);
    250   DCHECK(that->first_use_ == nullptr || that->first_use_->prev == nullptr);
    251 
    252   // Update the pointers to {this} to point to {that}.
    253   Use* last_use = nullptr;
    254   for (Use* use = this->first_use_; use; use = use->next) {
    255     *use->input_ptr() = that;
    256     last_use = use;
    257   }
    258   if (last_use) {
    259     // Concat the use list of {this} and {that}.
    260     last_use->next = that->first_use_;
    261     if (that->first_use_) that->first_use_->prev = last_use;
    262     that->first_use_ = this->first_use_;
    263   }
    264   first_use_ = nullptr;
    265 }
    266 
    267 
    268 bool Node::OwnedBy(Node const* owner1, Node const* owner2) const {
    269   unsigned mask = 0;
    270   for (Use* use = first_use_; use; use = use->next) {
    271     Node* from = use->from();
    272     if (from == owner1) {
    273       mask |= 1;
    274     } else if (from == owner2) {
    275       mask |= 2;
    276     } else {
    277       return false;
    278     }
    279   }
    280   return mask == 3;
    281 }
    282 
    283 
    284 void Node::Print() const {
    285   OFStream os(stdout);
    286   os << *this << std::endl;
    287 }
    288 
    289 
    290 Node::Node(NodeId id, const Operator* op, int inline_count, int inline_capacity)
    291     : op_(op),
    292       type_(nullptr),
    293       mark_(0),
    294       bit_field_(IdField::encode(id) | InlineCountField::encode(inline_count) |
    295                  InlineCapacityField::encode(inline_capacity)),
    296       first_use_(nullptr) {
    297   // Inputs must either be out of line or within the inline capacity.
    298   DCHECK(inline_capacity <= kMaxInlineCapacity);
    299   DCHECK(inline_count == kOutlineMarker || inline_count <= inline_capacity);
    300 }
    301 
    302 
    303 void Node::AppendUse(Use* use) {
    304   DCHECK(first_use_ == nullptr || first_use_->prev == nullptr);
    305   DCHECK_EQ(this, *use->input_ptr());
    306   use->next = first_use_;
    307   use->prev = nullptr;
    308   if (first_use_) first_use_->prev = use;
    309   first_use_ = use;
    310 }
    311 
    312 
    313 void Node::RemoveUse(Use* use) {
    314   DCHECK(first_use_ == nullptr || first_use_->prev == nullptr);
    315   if (use->prev) {
    316     DCHECK_NE(first_use_, use);
    317     use->prev->next = use->next;
    318   } else {
    319     DCHECK_EQ(first_use_, use);
    320     first_use_ = use->next;
    321   }
    322   if (use->next) {
    323     use->next->prev = use->prev;
    324   }
    325 }
    326 
    327 
    328 #if DEBUG
    329 void Node::Verify() {
    330   // Check basic sanity of input data structures.
    331   fflush(stdout);
    332   int count = this->InputCount();
    333   // Avoid quadratic explosion for mega nodes; only verify if the input
    334   // count is less than 200 or is a round number of 100s.
    335   if (count > 200 && count % 100) return;
    336 
    337   for (int i = 0; i < count; i++) {
    338     CHECK_EQ(i, this->GetUsePtr(i)->input_index());
    339     CHECK_EQ(this->GetInputPtr(i), this->GetUsePtr(i)->input_ptr());
    340     CHECK_EQ(count, this->InputCount());
    341   }
    342   {  // Direct input iteration.
    343     int index = 0;
    344     for (Node* input : this->inputs()) {
    345       CHECK_EQ(this->InputAt(index), input);
    346       index++;
    347     }
    348     CHECK_EQ(count, index);
    349     CHECK_EQ(this->InputCount(), index);
    350   }
    351   {  // Input edge iteration.
    352     int index = 0;
    353     for (Edge edge : this->input_edges()) {
    354       CHECK_EQ(edge.from(), this);
    355       CHECK_EQ(index, edge.index());
    356       CHECK_EQ(this->InputAt(index), edge.to());
    357       index++;
    358     }
    359     CHECK_EQ(count, index);
    360     CHECK_EQ(this->InputCount(), index);
    361   }
    362 }
    363 #endif
    364 
    365 
    366 std::ostream& operator<<(std::ostream& os, const Node& n) {
    367   os << n.id() << ": " << *n.op();
    368   if (n.InputCount() > 0) {
    369     os << "(";
    370     for (int i = 0; i < n.InputCount(); ++i) {
    371       if (i != 0) os << ", ";
    372       os << n.InputAt(i)->id();
    373     }
    374     os << ")";
    375   }
    376   return os;
    377 }
    378 
    379 
    380 Node::InputEdges::iterator Node::InputEdges::iterator::operator++(int n) {
    381   iterator result(*this);
    382   ++(*this);
    383   return result;
    384 }
    385 
    386 
    387 bool Node::InputEdges::empty() const { return begin() == end(); }
    388 
    389 
    390 Node::Inputs::const_iterator Node::Inputs::const_iterator::operator++(int n) {
    391   const_iterator result(*this);
    392   ++(*this);
    393   return result;
    394 }
    395 
    396 
    397 bool Node::Inputs::empty() const { return begin() == end(); }
    398 
    399 
    400 Node::UseEdges::iterator Node::UseEdges::iterator::operator++(int n) {
    401   iterator result(*this);
    402   ++(*this);
    403   return result;
    404 }
    405 
    406 
    407 bool Node::UseEdges::empty() const { return begin() == end(); }
    408 
    409 
    410 Node::Uses::const_iterator Node::Uses::const_iterator::operator++(int n) {
    411   const_iterator result(*this);
    412   ++(*this);
    413   return result;
    414 }
    415 
    416 
    417 bool Node::Uses::empty() const { return begin() == end(); }
    418 
    419 }  // namespace compiler
    420 }  // namespace internal
    421 }  // namespace v8
    422