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 void Node::InsertInputs(Zone* zone, int index, int count) {
    197   DCHECK_NOT_NULL(zone);
    198   DCHECK_LE(0, index);
    199   DCHECK_LT(0, count);
    200   DCHECK_LT(index, InputCount());
    201   for (int i = 0; i < count; i++) {
    202     AppendInput(zone, InputAt(Max(InputCount() - count, 0)));
    203   }
    204   for (int i = InputCount() - count - 1; i >= Max(index, count); --i) {
    205     ReplaceInput(i, InputAt(i - count));
    206   }
    207   for (int i = 0; i < count; i++) {
    208     ReplaceInput(index + i, nullptr);
    209   }
    210   Verify();
    211 }
    212 
    213 void Node::RemoveInput(int index) {
    214   DCHECK_LE(0, index);
    215   DCHECK_LT(index, InputCount());
    216   for (; index < InputCount() - 1; ++index) {
    217     ReplaceInput(index, InputAt(index + 1));
    218   }
    219   TrimInputCount(InputCount() - 1);
    220   Verify();
    221 }
    222 
    223 
    224 void Node::ClearInputs(int start, int count) {
    225   Node** input_ptr = GetInputPtr(start);
    226   Use* use_ptr = GetUsePtr(start);
    227   while (count-- > 0) {
    228     DCHECK_EQ(input_ptr, use_ptr->input_ptr());
    229     Node* input = *input_ptr;
    230     *input_ptr = nullptr;
    231     if (input) input->RemoveUse(use_ptr);
    232     input_ptr++;
    233     use_ptr--;
    234   }
    235   Verify();
    236 }
    237 
    238 
    239 void Node::NullAllInputs() { ClearInputs(0, InputCount()); }
    240 
    241 
    242 void Node::TrimInputCount(int new_input_count) {
    243   int current_count = InputCount();
    244   DCHECK_LE(new_input_count, current_count);
    245   if (new_input_count == current_count) return;  // Nothing to do.
    246   ClearInputs(new_input_count, current_count - new_input_count);
    247   if (has_inline_inputs()) {
    248     bit_field_ = InlineCountField::update(bit_field_, new_input_count);
    249   } else {
    250     inputs_.outline_->count_ = new_input_count;
    251   }
    252 }
    253 
    254 
    255 int Node::UseCount() const {
    256   int use_count = 0;
    257   for (const Use* use = first_use_; use; use = use->next) {
    258     ++use_count;
    259   }
    260   return use_count;
    261 }
    262 
    263 
    264 void Node::ReplaceUses(Node* that) {
    265   DCHECK(this->first_use_ == nullptr || this->first_use_->prev == nullptr);
    266   DCHECK(that->first_use_ == nullptr || that->first_use_->prev == nullptr);
    267 
    268   // Update the pointers to {this} to point to {that}.
    269   Use* last_use = nullptr;
    270   for (Use* use = this->first_use_; use; use = use->next) {
    271     *use->input_ptr() = that;
    272     last_use = use;
    273   }
    274   if (last_use) {
    275     // Concat the use list of {this} and {that}.
    276     last_use->next = that->first_use_;
    277     if (that->first_use_) that->first_use_->prev = last_use;
    278     that->first_use_ = this->first_use_;
    279   }
    280   first_use_ = nullptr;
    281 }
    282 
    283 
    284 bool Node::OwnedBy(Node const* owner1, Node const* owner2) const {
    285   unsigned mask = 0;
    286   for (Use* use = first_use_; use; use = use->next) {
    287     Node* from = use->from();
    288     if (from == owner1) {
    289       mask |= 1;
    290     } else if (from == owner2) {
    291       mask |= 2;
    292     } else {
    293       return false;
    294     }
    295   }
    296   return mask == 3;
    297 }
    298 
    299 bool Node::OwnedByAddressingOperand() const {
    300   for (Use* use = first_use_; use; use = use->next) {
    301     Node* from = use->from();
    302     if (from->opcode() != IrOpcode::kLoad &&
    303         // If {from} is store, make sure it does not use {this} as value
    304         (from->opcode() != IrOpcode::kStore || from->InputAt(2) == this) &&
    305         from->opcode() != IrOpcode::kInt32Add &&
    306         from->opcode() != IrOpcode::kInt64Add) {
    307       return false;
    308     }
    309   }
    310   return true;
    311 }
    312 
    313 void Node::Print() const {
    314   OFStream os(stdout);
    315   os << *this << std::endl;
    316   for (Node* input : this->inputs()) {
    317     os << "  " << *input << std::endl;
    318   }
    319 }
    320 
    321 std::ostream& operator<<(std::ostream& os, const Node& n) {
    322   os << n.id() << ": " << *n.op();
    323   if (n.InputCount() > 0) {
    324     os << "(";
    325     for (int i = 0; i < n.InputCount(); ++i) {
    326       if (i != 0) os << ", ";
    327       if (n.InputAt(i)) {
    328         os << n.InputAt(i)->id();
    329       } else {
    330         os << "null";
    331       }
    332     }
    333     os << ")";
    334   }
    335   return os;
    336 }
    337 
    338 Node::Node(NodeId id, const Operator* op, int inline_count, int inline_capacity)
    339     : op_(op),
    340       type_(nullptr),
    341       mark_(0),
    342       bit_field_(IdField::encode(id) | InlineCountField::encode(inline_count) |
    343                  InlineCapacityField::encode(inline_capacity)),
    344       first_use_(nullptr) {
    345   // Inputs must either be out of line or within the inline capacity.
    346   DCHECK(inline_capacity <= kMaxInlineCapacity);
    347   DCHECK(inline_count == kOutlineMarker || inline_count <= inline_capacity);
    348 }
    349 
    350 
    351 void Node::AppendUse(Use* use) {
    352   DCHECK(first_use_ == nullptr || first_use_->prev == nullptr);
    353   DCHECK_EQ(this, *use->input_ptr());
    354   use->next = first_use_;
    355   use->prev = nullptr;
    356   if (first_use_) first_use_->prev = use;
    357   first_use_ = use;
    358 }
    359 
    360 
    361 void Node::RemoveUse(Use* use) {
    362   DCHECK(first_use_ == nullptr || first_use_->prev == nullptr);
    363   if (use->prev) {
    364     DCHECK_NE(first_use_, use);
    365     use->prev->next = use->next;
    366   } else {
    367     DCHECK_EQ(first_use_, use);
    368     first_use_ = use->next;
    369   }
    370   if (use->next) {
    371     use->next->prev = use->prev;
    372   }
    373 }
    374 
    375 
    376 #if DEBUG
    377 void Node::Verify() {
    378   // Check basic sanity of input data structures.
    379   fflush(stdout);
    380   int count = this->InputCount();
    381   // Avoid quadratic explosion for mega nodes; only verify if the input
    382   // count is less than 200 or is a round number of 100s.
    383   if (count > 200 && count % 100) return;
    384 
    385   for (int i = 0; i < count; i++) {
    386     CHECK_EQ(i, this->GetUsePtr(i)->input_index());
    387     CHECK_EQ(this->GetInputPtr(i), this->GetUsePtr(i)->input_ptr());
    388     CHECK_EQ(count, this->InputCount());
    389   }
    390   {  // Direct input iteration.
    391     int index = 0;
    392     for (Node* input : this->inputs()) {
    393       CHECK_EQ(this->InputAt(index), input);
    394       index++;
    395     }
    396     CHECK_EQ(count, index);
    397     CHECK_EQ(this->InputCount(), index);
    398   }
    399   {  // Input edge iteration.
    400     int index = 0;
    401     for (Edge edge : this->input_edges()) {
    402       CHECK_EQ(edge.from(), this);
    403       CHECK_EQ(index, edge.index());
    404       CHECK_EQ(this->InputAt(index), edge.to());
    405       index++;
    406     }
    407     CHECK_EQ(count, index);
    408     CHECK_EQ(this->InputCount(), index);
    409   }
    410 }
    411 #endif
    412 
    413 Node::InputEdges::iterator Node::InputEdges::iterator::operator++(int n) {
    414   iterator result(*this);
    415   ++(*this);
    416   return result;
    417 }
    418 
    419 
    420 Node::Inputs::const_iterator Node::Inputs::const_iterator::operator++(int n) {
    421   const_iterator result(*this);
    422   ++(*this);
    423   return result;
    424 }
    425 
    426 
    427 Node::UseEdges::iterator Node::UseEdges::iterator::operator++(int n) {
    428   iterator result(*this);
    429   ++(*this);
    430   return result;
    431 }
    432 
    433 
    434 bool Node::UseEdges::empty() const { return begin() == end(); }
    435 
    436 
    437 Node::Uses::const_iterator Node::Uses::const_iterator::operator++(int n) {
    438   const_iterator result(*this);
    439   ++(*this);
    440   return result;
    441 }
    442 
    443 
    444 bool Node::Uses::empty() const { return begin() == end(); }
    445 
    446 }  // namespace compiler
    447 }  // namespace internal
    448 }  // namespace v8
    449