LCOV - code coverage report
Current view: top level - src/compiler - value-numbering-reducer.cc (source / functions) Hit Total Coverage
Test: app.info Lines: 66 67 98.5 %
Date: 2019-04-17 Functions: 5 5 100.0 %

          Line data    Source code
       1             : // Copyright 2014 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/value-numbering-reducer.h"
       6             : 
       7             : #include <cstring>
       8             : 
       9             : #include "src/base/functional.h"
      10             : #include "src/compiler/node-properties.h"
      11             : #include "src/compiler/node.h"
      12             : 
      13             : namespace v8 {
      14             : namespace internal {
      15             : namespace compiler {
      16             : 
      17     2474047 : ValueNumberingReducer::ValueNumberingReducer(Zone* temp_zone, Zone* graph_zone)
      18             :     : entries_(nullptr),
      19             :       capacity_(0),
      20             :       size_(0),
      21             :       temp_zone_(temp_zone),
      22     2474047 :       graph_zone_(graph_zone) {}
      23             : 
      24             : ValueNumberingReducer::~ValueNumberingReducer() = default;
      25             : 
      26             : 
      27   185457033 : Reduction ValueNumberingReducer::Reduce(Node* node) {
      28   185457033 :   if (!node->op()->HasProperty(Operator::kIdempotent)) return NoChange();
      29             : 
      30    96819806 :   const size_t hash = NodeProperties::HashCode(node);
      31    96829181 :   if (!entries_) {
      32             :     DCHECK_EQ(0, size_);
      33             :     DCHECK_EQ(0, capacity_);
      34             :     // Allocate the initial entries and insert the first entry.
      35     2474235 :     capacity_ = kInitialCapacity;
      36     2473557 :     entries_ = temp_zone()->NewArray<Node*>(kInitialCapacity);
      37             :     memset(entries_, 0, sizeof(*entries_) * kInitialCapacity);
      38     2473557 :     entries_[hash & (kInitialCapacity - 1)] = node;
      39     2473557 :     size_ = 1;
      40             :     return NoChange();
      41             :   }
      42             : 
      43             :   DCHECK(size_ < capacity_);
      44             :   DCHECK(size_ + size_ / 4 < capacity_);
      45             : 
      46    94354946 :   const size_t mask = capacity_ - 1;
      47             :   size_t dead = capacity_;
      48             : 
      49   173388654 :   for (size_t i = hash & mask;; i = (i + 1) & mask) {
      50   173388654 :     Node* entry = entries_[i];
      51   173388654 :     if (!entry) {
      52    89445512 :       if (dead != capacity_) {
      53             :         // Reuse dead entry that we discovered on the way.
      54       17060 :         entries_[dead] = node;
      55             :       } else {
      56             :         // Have to insert a new entry.
      57    89428452 :         entries_[i] = node;
      58    89428452 :         size_++;
      59             : 
      60             :         // Resize to keep load factor below 80%
      61    89428452 :         if (size_ + size_ / 4 >= capacity_) Grow();
      62             :       }
      63             :       DCHECK(size_ + size_ / 4 < capacity_);
      64             :       return NoChange();
      65             :     }
      66             : 
      67    83943142 :     if (entry == node) {
      68             :       // We need to check for a certain class of collisions here. Imagine the
      69             :       // following scenario:
      70             :       //
      71             :       //  1. We insert node1 with op1 and certain inputs at index i.
      72             :       //  2. We insert node2 with op2 and certain inputs at index i+1.
      73             :       //  3. Some other reducer changes node1 to op2 and the inputs from node2.
      74             :       //
      75             :       // Now we are called again to reduce node1, and we would return NoChange
      76             :       // in this case because we find node1 first, but what we should actually
      77             :       // do is return Replace(node2) instead.
      78     8632335 :       for (size_t j = (i + 1) & mask;; j = (j + 1) & mask) {
      79     8632335 :         Node* entry = entries_[j];
      80     8632335 :         if (!entry) {
      81             :           // No collision, {node} is fine.
      82             :           return NoChange();
      83             :         }
      84     6317496 :         if (entry->IsDead()) {
      85             :           continue;
      86             :         }
      87     6310443 :         if (entry == node) {
      88             :           // Collision with ourselves, doesn't count as a real collision.
      89             :           // Opportunistically clean-up the duplicate entry if we're at the end
      90             :           // of a bucket.
      91          25 :           if (!entries_[(j + 1) & mask]) {
      92          14 :             entries_[j] = nullptr;
      93          14 :             size_--;
      94             :             return NoChange();
      95             :           }
      96             :           // Otherwise, keep searching for another collision.
      97             :           continue;
      98             :         }
      99     6310418 :         if (NodeProperties::Equals(entry, node)) {
     100         277 :           Reduction reduction = ReplaceIfTypesMatch(node, entry);
     101         277 :           if (reduction.Changed()) {
     102             :             // Overwrite the colliding entry with the actual entry.
     103         277 :             entries_[i] = entry;
     104             :             // Opportunistically clean-up the duplicate entry if we're at the
     105             :             // end of a bucket.
     106         277 :             if (!entries_[(j + 1) & mask]) {
     107         105 :               entries_[j] = nullptr;
     108         105 :               size_--;
     109             :             }
     110             :           }
     111         277 :           return reduction;
     112             :         }
     113             :       }
     114             :     }
     115             : 
     116             :     // Skip dead entries, but remember their indices so we can reuse them.
     117    81627988 :     if (entry->IsDead()) {
     118             :       dead = i;
     119             :       continue;
     120             :     }
     121    81606383 :     if (NodeProperties::Equals(entry, node)) {
     122     2593605 :       return ReplaceIfTypesMatch(node, entry);
     123             :     }
     124             :   }
     125             : }
     126             : 
     127     2593877 : Reduction ValueNumberingReducer::ReplaceIfTypesMatch(Node* node,
     128             :                                                      Node* replacement) {
     129             :   // Make sure the replacement has at least as good type as the original node.
     130     2593877 :   if (NodeProperties::IsTyped(replacement) && NodeProperties::IsTyped(node)) {
     131      723151 :     Type replacement_type = NodeProperties::GetType(replacement);
     132      723151 :     Type node_type = NodeProperties::GetType(node);
     133      723151 :     if (!replacement_type.Is(node_type)) {
     134             :       // Ideally, we would set an intersection of {replacement_type} and
     135             :       // {node_type} here. However, typing of NumberConstants assigns different
     136             :       // types to constants with the same value (it creates a fresh heap
     137             :       // number), which would make the intersection empty. To be safe, we use
     138             :       // the smaller type if the types are comparable.
     139         768 :       if (node_type.Is(replacement_type)) {
     140             :         NodeProperties::SetType(replacement, node_type);
     141             :       } else {
     142             :         // Types are not comparable => do not replace.
     143           0 :         return NoChange();
     144             :       }
     145             :     }
     146             :   }
     147             :   return Replace(replacement);
     148             : }
     149             : 
     150             : 
     151       69898 : void ValueNumberingReducer::Grow() {
     152             :   // Allocate a new block of entries double the previous capacity.
     153       69898 :   Node** const old_entries = entries_;
     154       69898 :   size_t const old_capacity = capacity_;
     155       69898 :   capacity_ *= 2;
     156       70603 :   entries_ = temp_zone()->NewArray<Node*>(capacity_);
     157       70603 :   memset(entries_, 0, sizeof(*entries_) * capacity_);
     158       70603 :   size_ = 0;
     159       70603 :   size_t const mask = capacity_ - 1;
     160             : 
     161             :   // Insert the old entries into the new block (skipping dead nodes).
     162    67147583 :   for (size_t i = 0; i < old_capacity; ++i) {
     163    33539195 :     Node* const old_entry = old_entries[i];
     164    60389259 :     if (!old_entry || old_entry->IsDead()) continue;
     165    35671286 :     for (size_t j = NodeProperties::HashCode(old_entry) & mask;;
     166     8828788 :          j = (j + 1) & mask) {
     167    35670581 :       Node* const entry = entries_[j];
     168    35670581 :       if (entry == old_entry) {
     169             :         // Skip duplicate of the old entry.
     170             :         break;
     171             :       }
     172    35637547 :       if (!entry) {
     173    26808759 :         entries_[j] = old_entry;
     174    26808759 :         size_++;
     175    26808759 :         break;
     176             :       }
     177             :     }
     178             :   }
     179       69898 : }
     180             : 
     181             : }  // namespace compiler
     182             : }  // namespace internal
     183      122004 : }  // namespace v8

Generated by: LCOV version 1.10