LCOV - code coverage report
Current view: top level - src/compiler - value-numbering-reducer.cc (source / functions) Hit Total Coverage
Test: app.info Lines: 64 67 95.5 %
Date: 2019-04-18 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     2473220 : ValueNumberingReducer::ValueNumberingReducer(Zone* temp_zone, Zone* graph_zone)
      18             :     : entries_(nullptr),
      19             :       capacity_(0),
      20             :       size_(0),
      21             :       temp_zone_(temp_zone),
      22     2473220 :       graph_zone_(graph_zone) {}
      23             : 
      24             : ValueNumberingReducer::~ValueNumberingReducer() = default;
      25             : 
      26             : 
      27   185377632 : Reduction ValueNumberingReducer::Reduce(Node* node) {
      28   185377632 :   if (!node->op()->HasProperty(Operator::kIdempotent)) return NoChange();
      29             : 
      30    96757378 :   const size_t hash = NodeProperties::HashCode(node);
      31    96767754 :   if (!entries_) {
      32             :     DCHECK_EQ(0, size_);
      33             :     DCHECK_EQ(0, capacity_);
      34             :     // Allocate the initial entries and insert the first entry.
      35     2471329 :     capacity_ = kInitialCapacity;
      36     2470167 :     entries_ = temp_zone()->NewArray<Node*>(kInitialCapacity);
      37             :     memset(entries_, 0, sizeof(*entries_) * kInitialCapacity);
      38     2470167 :     entries_[hash & (kInitialCapacity - 1)] = node;
      39     2470167 :     size_ = 1;
      40             :     return NoChange();
      41             :   }
      42             : 
      43             :   DCHECK(size_ < capacity_);
      44             :   DCHECK(size_ + size_ / 4 < capacity_);
      45             : 
      46    94296425 :   const size_t mask = capacity_ - 1;
      47             :   size_t dead = capacity_;
      48             : 
      49   172159705 :   for (size_t i = hash & mask;; i = (i + 1) & mask) {
      50   172159705 :     Node* entry = entries_[i];
      51   172159705 :     if (!entry) {
      52    89401259 :       if (dead != capacity_) {
      53             :         // Reuse dead entry that we discovered on the way.
      54       17010 :         entries_[dead] = node;
      55             :       } else {
      56             :         // Have to insert a new entry.
      57    89384249 :         entries_[i] = node;
      58    89384249 :         size_++;
      59             : 
      60             :         // Resize to keep load factor below 80%
      61    89384249 :         if (size_ + size_ / 4 >= capacity_) Grow();
      62             :       }
      63             :       DCHECK(size_ + size_ / 4 < capacity_);
      64             :       return NoChange();
      65             :     }
      66             : 
      67    82758446 :     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     8468965 :       for (size_t j = (i + 1) & mask;; j = (j + 1) & mask) {
      79     8468965 :         Node* entry = entries_[j];
      80     8468965 :         if (!entry) {
      81             :           // No collision, {node} is fine.
      82             :           return NoChange();
      83             :         }
      84     6165669 :         if (entry->IsDead()) {
      85             :           continue;
      86             :         }
      87     6158809 :         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           9 :           if (!entries_[(j + 1) & mask]) {
      92           0 :             entries_[j] = nullptr;
      93           0 :             size_--;
      94             :             return NoChange();
      95             :           }
      96             :           // Otherwise, keep searching for another collision.
      97             :           continue;
      98             :         }
      99     6158800 :         if (NodeProperties::Equals(entry, node)) {
     100         276 :           Reduction reduction = ReplaceIfTypesMatch(node, entry);
     101         276 :           if (reduction.Changed()) {
     102             :             // Overwrite the colliding entry with the actual entry.
     103         276 :             entries_[i] = entry;
     104             :             // Opportunistically clean-up the duplicate entry if we're at the
     105             :             // end of a bucket.
     106         276 :             if (!entries_[(j + 1) & mask]) {
     107          90 :               entries_[j] = nullptr;
     108          90 :               size_--;
     109             :             }
     110             :           }
     111         276 :           return reduction;
     112             :         }
     113             :       }
     114             :     }
     115             : 
     116             :     // Skip dead entries, but remember their indices so we can reuse them.
     117    80454859 :     if (entry->IsDead()) {
     118             :       dead = i;
     119             :       continue;
     120             :     }
     121    80429448 :     if (NodeProperties::Equals(entry, node)) {
     122     2590946 :       return ReplaceIfTypesMatch(node, entry);
     123             :     }
     124             :   }
     125             : }
     126             : 
     127     2591267 : Reduction ValueNumberingReducer::ReplaceIfTypesMatch(Node* node,
     128             :                                                      Node* replacement) {
     129             :   // Make sure the replacement has at least as good type as the original node.
     130     2591267 :   if (NodeProperties::IsTyped(replacement) && NodeProperties::IsTyped(node)) {
     131      720290 :     Type replacement_type = NodeProperties::GetType(replacement);
     132      720290 :     Type node_type = NodeProperties::GetType(node);
     133      720290 :     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         775 :       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       69942 : void ValueNumberingReducer::Grow() {
     152             :   // Allocate a new block of entries double the previous capacity.
     153       69942 :   Node** const old_entries = entries_;
     154       69942 :   size_t const old_capacity = capacity_;
     155       69942 :   capacity_ *= 2;
     156       70439 :   entries_ = temp_zone()->NewArray<Node*>(capacity_);
     157       70439 :   memset(entries_, 0, sizeof(*entries_) * capacity_);
     158       70439 :   size_ = 0;
     159       70439 :   size_t const mask = capacity_ - 1;
     160             : 
     161             :   // Insert the old entries into the new block (skipping dead nodes).
     162    67157877 :   for (size_t i = 0; i < old_capacity; ++i) {
     163    33544216 :     Node* const old_entry = old_entries[i];
     164    60398411 :     if (!old_entry || old_entry->IsDead()) continue;
     165    35651582 :     for (size_t j = NodeProperties::HashCode(old_entry) & mask;;
     166     8805067 :          j = (j + 1) & mask) {
     167    35651085 :       Node* const entry = entries_[j];
     168    35651085 :       if (entry == old_entry) {
     169             :         // Skip duplicate of the old entry.
     170             :         break;
     171             :       }
     172    35617903 :       if (!entry) {
     173    26812836 :         entries_[j] = old_entry;
     174    26812836 :         size_++;
     175    26812836 :         break;
     176             :       }
     177             :     }
     178             :   }
     179       69942 : }
     180             : 
     181             : }  // namespace compiler
     182             : }  // namespace internal
     183      122028 : }  // namespace v8

Generated by: LCOV version 1.10