LCOV - code coverage report
Current view: top level - src/compiler - node.cc (source / functions) Hit Total Coverage
Test: app.info Lines: 167 184 90.8 %
Date: 2017-04-26 Functions: 22 27 81.5 %

          Line data    Source code
       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     6278820 : Node::OutOfLineInputs* Node::OutOfLineInputs::New(Zone* zone, int capacity) {
      12             :   size_t size =
      13     6278820 :       sizeof(OutOfLineInputs) + capacity * (sizeof(Node*) + sizeof(Use));
      14     6278820 :   intptr_t raw_buffer = reinterpret_cast<intptr_t>(zone->New(size));
      15             :   Node::OutOfLineInputs* outline =
      16     6278826 :       reinterpret_cast<OutOfLineInputs*>(raw_buffer + capacity * sizeof(Use));
      17     6278826 :   outline->capacity_ = capacity;
      18     6278826 :   outline->count_ = 0;
      19     6278826 :   return outline;
      20             : }
      21             : 
      22             : 
      23     6245752 : 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     6245752 :   Use* new_use_ptr = reinterpret_cast<Use*>(this) - 1;
      28     6245752 :   Node** new_input_ptr = inputs_;
      29    34828525 :   for (int current = 0; current < count; current++) {
      30             :     new_use_ptr->bit_field_ =
      31    57165546 :         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    28582773 :     Node* old_to = *old_input_ptr;
      35    28582773 :     if (old_to) {
      36    28582773 :       *old_input_ptr = nullptr;
      37             :       old_to->RemoveUse(old_use_ptr);
      38    28582773 :       *new_input_ptr = old_to;
      39             :       old_to->AppendUse(new_use_ptr);
      40             :     } else {
      41           0 :       *new_input_ptr = nullptr;
      42             :     }
      43    28582773 :     old_input_ptr++;
      44    28582773 :     new_input_ptr++;
      45    28582773 :     old_use_ptr--;
      46    28582773 :     new_use_ptr--;
      47             :   }
      48     6245752 :   this->count_ = count;
      49     6245752 : }
      50             : 
      51             : 
      52   112379313 : 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   112379313 :   if (input_count > kMaxInlineCapacity) {
      70             :     // Allocate out-of-line inputs.
      71             :     int capacity =
      72       33072 :         has_extensible_inputs ? input_count + kMaxInlineCapacity : input_count;
      73       33072 :     OutOfLineInputs* outline = OutOfLineInputs::New(zone, capacity);
      74             : 
      75             :     // Allocate node.
      76       33072 :     void* node_buffer = zone->New(sizeof(Node));
      77             :     node = new (node_buffer) Node(id, op, kOutlineMarker, 0);
      78       34750 :     node->inputs_.outline_ = outline;
      79             : 
      80       34750 :     outline->node_ = node;
      81       34750 :     outline->count_ = input_count;
      82             : 
      83       34750 :     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   112346241 :     if (has_extensible_inputs) {
      90     3124847 :       const int max = kMaxInlineCapacity;
      91     6249694 :       capacity = std::min(input_count + 3, max);
      92             :     }
      93             : 
      94   112346241 :     size_t size = sizeof(Node) + capacity * (sizeof(Node*) + sizeof(Use));
      95   112346241 :     intptr_t raw_buffer = reinterpret_cast<intptr_t>(zone->New(size));
      96             :     void* node_buffer =
      97   112342565 :         reinterpret_cast<void*>(raw_buffer + capacity * sizeof(Use));
      98             : 
      99             :     node = new (node_buffer) Node(id, op, input_count, capacity);
     100   112342565 :     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   307821236 :   for (int current = 0; current < input_count; ++current) {
     107   195443921 :     Node* to = *inputs++;
     108   195443921 :     input_ptr[current] = to;
     109   195443921 :     Use* use = use_ptr - 1 - current;
     110   390887842 :     use->bit_field_ = Use::InputIndexField::encode(current) |
     111   195443921 :                       Use::InlineField::encode(is_inline);
     112             :     to->AppendUse(use);
     113             :   }
     114             :   node->Verify();
     115   112377315 :   return node;
     116             : }
     117             : 
     118             : 
     119     8165705 : 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     2721903 :                                   : node->inputs_.outline_->inputs_;
     124     2721903 :   Node* const clone = New(zone, id, node->op(), input_count, inputs, false);
     125             :   clone->set_type(node->type());
     126     2721899 :   return clone;
     127             : }
     128             : 
     129             : 
     130    11179373 : void Node::Kill() {
     131             :   DCHECK_NOT_NULL(op());
     132    11179373 :   NullAllInputs();
     133             :   DCHECK(uses().empty());
     134    11179438 : }
     135             : 
     136             : 
     137    17749179 : void Node::AppendInput(Zone* zone, Node* new_to) {
     138             :   DCHECK_NOT_NULL(zone);
     139             :   DCHECK_NOT_NULL(new_to);
     140             : 
     141    35498358 :   int inline_count = InlineCountField::decode(bit_field_);
     142    17749179 :   int inline_capacity = InlineCapacityField::decode(bit_field_);
     143    17749179 :   if (inline_count < inline_capacity) {
     144             :     // Append inline input.
     145     4664144 :     bit_field_ = InlineCountField::update(bit_field_, inline_count + 1);
     146     2332072 :     *GetInputPtr(inline_count) = new_to;
     147             :     Use* use = GetUsePtr(inline_count);
     148     2332072 :     use->bit_field_ = Use::InputIndexField::encode(inline_count) |
     149     2332072 :                       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    15417107 :     if (inline_count != kOutlineMarker) {
     156             :       // switch to out of line inputs.
     157     5994914 :       outline = OutOfLineInputs::New(zone, input_count * 2 + 3);
     158     5994895 :       outline->node_ = this;
     159     5994895 :       outline->ExtractFrom(GetUsePtr(0), GetInputPtr(0), input_count);
     160    11989834 :       bit_field_ = InlineCountField::update(bit_field_, kOutlineMarker);
     161     5994917 :       inputs_.outline_ = outline;
     162             :     } else {
     163             :       // use current out of line inputs.
     164     9422193 :       outline = inputs_.outline_;
     165     9422193 :       if (input_count >= outline->capacity_) {
     166             :         // out of space in out-of-line inputs.
     167      250840 :         outline = OutOfLineInputs::New(zone, input_count * 2 + 3);
     168      250840 :         outline->node_ = this;
     169      250840 :         outline->ExtractFrom(GetUsePtr(0), GetInputPtr(0), input_count);
     170      250839 :         inputs_.outline_ = outline;
     171             :       }
     172             :     }
     173    15417109 :     outline->count_++;
     174    15417109 :     *GetInputPtr(input_count) = new_to;
     175             :     Use* use = GetUsePtr(input_count);
     176    15417109 :     use->bit_field_ = Use::InputIndexField::encode(input_count) |
     177    15417109 :                       Use::InlineField::encode(false);
     178             :     new_to->AppendUse(use);
     179             :   }
     180             :   Verify();
     181    17749181 : }
     182             : 
     183             : 
     184    14883840 : 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    29767680 :   AppendInput(zone, InputAt(InputCount() - 1));
     189    83171262 :   for (int i = InputCount() - 1; i > index; --i) {
     190   106807524 :     ReplaceInput(i, InputAt(i - 1));
     191             :   }
     192    14883774 :   ReplaceInput(index, new_to);
     193             :   Verify();
     194    14883737 : }
     195             : 
     196       44153 : 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      132466 :   for (int i = 0; i < count; i++) {
     202      176626 :     AppendInput(zone, InputAt(Max(InputCount() - count, 0)));
     203             :   }
     204      441110 :   for (int i = InputCount() - count - 1; i >= Max(index, count); --i) {
     205      352804 :     ReplaceInput(i, InputAt(i - count));
     206             :   }
     207       88313 :   for (int i = 0; i < count; i++) {
     208       88313 :     ReplaceInput(index + i, nullptr);
     209             :   }
     210             :   Verify();
     211       44153 : }
     212             : 
     213      234265 : void Node::RemoveInput(int index) {
     214             :   DCHECK_LE(0, index);
     215             :   DCHECK_LT(index, InputCount());
     216      780688 :   for (; index < InputCount() - 1; ++index) {
     217      624314 :     ReplaceInput(index, InputAt(index + 1));
     218             :   }
     219      234266 :   TrimInputCount(InputCount() - 1);
     220             :   Verify();
     221      234266 : }
     222             : 
     223             : 
     224    13412837 : void Node::ClearInputs(int start, int count) {
     225             :   Node** input_ptr = GetInputPtr(start);
     226             :   Use* use_ptr = GetUsePtr(start);
     227    58937359 :   while (count-- > 0) {
     228             :     DCHECK_EQ(input_ptr, use_ptr->input_ptr());
     229    32111685 :     Node* input = *input_ptr;
     230    32111685 :     *input_ptr = nullptr;
     231    32111685 :     if (input) input->RemoveUse(use_ptr);
     232    32111685 :     input_ptr++;
     233    32111685 :     use_ptr--;
     234             :   }
     235             :   Verify();
     236    13412837 : }
     237             : 
     238             : 
     239    23053682 : void Node::NullAllInputs() { ClearInputs(0, InputCount()); }
     240             : 
     241             : 
     242     3774724 : void Node::TrimInputCount(int new_input_count) {
     243             :   int current_count = InputCount();
     244             :   DCHECK_LE(new_input_count, current_count);
     245     3777043 :   if (new_input_count == current_count) return;  // Nothing to do.
     246     1886201 :   ClearInputs(new_input_count, current_count - new_input_count);
     247     1886204 :   if (has_inline_inputs()) {
     248     2994214 :     bit_field_ = InlineCountField::update(bit_field_, new_input_count);
     249             :   } else {
     250      389097 :     inputs_.outline_->count_ = new_input_count;
     251             :   }
     252             : }
     253             : 
     254             : 
     255      166339 : int Node::UseCount() const {
     256             :   int use_count = 0;
     257      219575 :   for (const Use* use = first_use_; use; use = use->next) {
     258       53236 :     ++use_count;
     259             :   }
     260      166339 :   return use_count;
     261             : }
     262             : 
     263             : 
     264     2357788 : 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     5047224 :   for (Use* use = this->first_use_; use; use = use->next) {
     271     2689436 :     *use->input_ptr() = that;
     272             :     last_use = use;
     273             :   }
     274     2357788 :   if (last_use) {
     275             :     // Concat the use list of {this} and {that}.
     276     2278071 :     last_use->next = that->first_use_;
     277     2278071 :     if (that->first_use_) that->first_use_->prev = last_use;
     278     2278071 :     that->first_use_ = this->first_use_;
     279             :   }
     280     2357788 :   first_use_ = nullptr;
     281     2357788 : }
     282             : 
     283             : 
     284       52063 : bool Node::OwnedBy(Node const* owner1, Node const* owner2) const {
     285             :   unsigned mask = 0;
     286      141383 :   for (Use* use = first_use_; use; use = use->next) {
     287             :     Node* from = use->from();
     288      133517 :     if (from == owner1) {
     289       47259 :       mask |= 1;
     290       86258 :     } else if (from == owner2) {
     291       42061 :       mask |= 2;
     292             :     } else {
     293             :       return false;
     294             :     }
     295             :   }
     296        7866 :   return mask == 3;
     297             : }
     298             : 
     299      680037 : bool Node::OwnedByAddressingOperand() const {
     300     1638363 :   for (Use* use = first_use_; use; use = use->next) {
     301     1100877 :     Node* from = use->from();
     302     1610510 :     if (from->opcode() != IrOpcode::kLoad &&
     303             :         // If {from} is store, make sure it does not use {this} as value
     304      172532 :         (from->opcode() != IrOpcode::kStore || from->InputAt(2) == this) &&
     305     1444702 :         from->opcode() != IrOpcode::kInt32Add &&
     306             :         from->opcode() != IrOpcode::kInt64Add) {
     307             :       return false;
     308             :     }
     309             :   }
     310             :   return true;
     311             : }
     312             : 
     313           0 : void Node::Print() const {
     314           0 :   OFStream os(stdout);
     315           0 :   os << *this << std::endl;
     316           0 :   for (Node* input : this->inputs()) {
     317           0 :     os << "  " << *input << std::endl;
     318           0 :   }
     319           0 : }
     320             : 
     321          84 : std::ostream& operator<<(std::ostream& os, const Node& n) {
     322          84 :   os << n.id() << ": " << *n.op();
     323          84 :   if (n.InputCount() > 0) {
     324          56 :     os << "(";
     325         294 :     for (int i = 0; i < n.InputCount(); ++i) {
     326          91 :       if (i != 0) os << ", ";
     327          91 :       if (n.InputAt(i)) {
     328          91 :         os << n.InputAt(i)->id();
     329             :       } else {
     330           0 :         os << "null";
     331             :       }
     332             :     }
     333          56 :     os << ")";
     334             :   }
     335          84 :   return os;
     336             : }
     337             : 
     338           0 : Node::Node(NodeId id, const Operator* op, int inline_count, int inline_capacity)
     339             :     : op_(op),
     340             :       type_(nullptr),
     341             :       mark_(0),
     342   337062445 :       bit_field_(IdField::encode(id) | InlineCountField::encode(inline_count) |
     343   112342565 :                  InlineCapacityField::encode(inline_capacity)),
     344   224754630 :       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           0 : }
     349             : 
     350             : 
     351    70500027 : void Node::AppendUse(Use* use) {
     352             :   DCHECK(first_use_ == nullptr || first_use_->prev == nullptr);
     353             :   DCHECK_EQ(this, *use->input_ptr());
     354   365280920 :   use->next = first_use_;
     355   365280920 :   use->prev = nullptr;
     356   365280920 :   if (first_use_) first_use_->prev = use;
     357   365280920 :   first_use_ = use;
     358    70500027 : }
     359             : 
     360             : 
     361   108479619 : void Node::RemoveUse(Use* use) {
     362             :   DCHECK(first_use_ == nullptr || first_use_->prev == nullptr);
     363   221626457 :   if (use->prev) {
     364             :     DCHECK_NE(first_use_, use);
     365   146853847 :     use->prev->next = use->next;
     366             :   } else {
     367             :     DCHECK_EQ(first_use_, use);
     368    74772610 :     first_use_ = use->next;
     369             :   }
     370   221626457 :   if (use->next) {
     371   138647699 :     use->next->prev = use->prev;
     372             :   }
     373   108479619 : }
     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           0 : Node::InputEdges::iterator Node::InputEdges::iterator::operator++(int n) {
     414             :   iterator result(*this);
     415             :   ++(*this);
     416           0 :   return result;
     417             : }
     418             : 
     419             : 
     420           0 : Node::Inputs::const_iterator Node::Inputs::const_iterator::operator++(int n) {
     421             :   const_iterator result(*this);
     422             :   ++(*this);
     423           0 :   return result;
     424             : }
     425             : 
     426             : 
     427           0 : Node::UseEdges::iterator Node::UseEdges::iterator::operator++(int n) {
     428             :   iterator result(*this);
     429             :   ++(*this);
     430           0 :   return result;
     431             : }
     432             : 
     433             : 
     434       11828 : bool Node::UseEdges::empty() const { return begin() == end(); }
     435             : 
     436             : 
     437      247580 : Node::Uses::const_iterator Node::Uses::const_iterator::operator++(int n) {
     438             :   const_iterator result(*this);
     439             :   ++(*this);
     440      247580 :   return result;
     441             : }
     442             : 
     443             : 
     444     3501130 : bool Node::Uses::empty() const { return begin() == end(); }
     445             : 
     446             : }  // namespace compiler
     447             : }  // namespace internal
     448             : }  // namespace v8

Generated by: LCOV version 1.10