Home | History | Annotate | Download | only in compiler 
      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 namespace {
     18 
     19 size_t HashCode(Node* node) {
     20   size_t h = base::hash_combine(node->op()->HashCode(), node->InputCount());
     21   for (Node* input : node->inputs()) {
     22     h = base::hash_combine(h, input->id());
     23   }
     24   return h;
     25 }
     26 
     27 
     28 bool Equals(Node* a, Node* b) {
     29   DCHECK_NOT_NULL(a);
     30   DCHECK_NOT_NULL(b);
     31   DCHECK_NOT_NULL(a->op());
     32   DCHECK_NOT_NULL(b->op());
     33   if (!a->op()->Equals(b->op())) return false;
     34   if (a->InputCount() != b->InputCount()) return false;
     35   Node::Inputs aInputs = a->inputs();
     36   Node::Inputs bInputs = b->inputs();
     37 
     38   auto aIt = aInputs.begin();
     39   auto bIt = bInputs.begin();
     40   auto aEnd = aInputs.end();
     41 
     42   for (; aIt != aEnd; ++aIt, ++bIt) {
     43     DCHECK_NOT_NULL(*aIt);
     44     DCHECK_NOT_NULL(*bIt);
     45     if ((*aIt)->id() != (*bIt)->id()) return false;
     46   }
     47   return true;
     48 }
     49 
     50 }  // namespace
     51 
     52 ValueNumberingReducer::ValueNumberingReducer(Zone* temp_zone, Zone* graph_zone)
     53     : entries_(nullptr),
     54       capacity_(0),
     55       size_(0),
     56       temp_zone_(temp_zone),
     57       graph_zone_(graph_zone) {}
     58 
     59 ValueNumberingReducer::~ValueNumberingReducer() {}
     60 
     61 
     62 Reduction ValueNumberingReducer::Reduce(Node* node) {
     63   if (!node->op()->HasProperty(Operator::kIdempotent)) return NoChange();
     64 
     65   const size_t hash = HashCode(node);
     66   if (!entries_) {
     67     DCHECK(size_ == 0);
     68     DCHECK(capacity_ == 0);
     69     // Allocate the initial entries and insert the first entry.
     70     capacity_ = kInitialCapacity;
     71     entries_ = temp_zone()->NewArray<Node*>(kInitialCapacity);
     72     memset(entries_, 0, sizeof(*entries_) * kInitialCapacity);
     73     entries_[hash & (kInitialCapacity - 1)] = node;
     74     size_ = 1;
     75     return NoChange();
     76   }
     77 
     78   DCHECK(size_ < capacity_);
     79   DCHECK(size_ + size_ / 4 < capacity_);
     80 
     81   const size_t mask = capacity_ - 1;
     82   size_t dead = capacity_;
     83 
     84   for (size_t i = hash & mask;; i = (i + 1) & mask) {
     85     Node* entry = entries_[i];
     86     if (!entry) {
     87       if (dead != capacity_) {
     88         // Reuse dead entry that we discovered on the way.
     89         entries_[dead] = node;
     90       } else {
     91         // Have to insert a new entry.
     92         entries_[i] = node;
     93         size_++;
     94 
     95         // Resize to keep load factor below 80%
     96         if (size_ + size_ / 4 >= capacity_) Grow();
     97       }
     98       DCHECK(size_ + size_ / 4 < capacity_);
     99       return NoChange();
    100     }
    101 
    102     if (entry == node) {
    103       // We need to check for a certain class of collisions here. Imagine the
    104       // following scenario:
    105       //
    106       //  1. We insert node1 with op1 and certain inputs at index i.
    107       //  2. We insert node2 with op2 and certain inputs at index i+1.
    108       //  3. Some other reducer changes node1 to op2 and the inputs from node2.
    109       //
    110       // Now we are called again to reduce node1, and we would return NoChange
    111       // in this case because we find node1 first, but what we should actually
    112       // do is return Replace(node2) instead.
    113       for (size_t j = (i + 1) & mask;; j = (j + 1) & mask) {
    114         Node* entry = entries_[j];
    115         if (!entry) {
    116           // No collision, {node} is fine.
    117           return NoChange();
    118         }
    119         if (entry->IsDead()) {
    120           continue;
    121         }
    122         if (entry == node) {
    123           // Collision with ourselves, doesn't count as a real collision.
    124           // Opportunistically clean-up the duplicate entry if we're at the end
    125           // of a bucket.
    126           if (!entries_[(j + 1) & mask]) {
    127             entries_[j] = nullptr;
    128             size_--;
    129             return NoChange();
    130           }
    131           // Otherwise, keep searching for another collision.
    132           continue;
    133         }
    134         if (Equals(entry, node)) {
    135           Reduction reduction = ReplaceIfTypesMatch(node, entry);
    136           if (reduction.Changed()) {
    137             // Overwrite the colliding entry with the actual entry.
    138             entries_[i] = entry;
    139             // Opportunistically clean-up the duplicate entry if we're at the
    140             // end of a bucket.
    141             if (!entries_[(j + 1) & mask]) {
    142               entries_[j] = nullptr;
    143               size_--;
    144             }
    145           }
    146           return reduction;
    147         }
    148       }
    149     }
    150 
    151     // Skip dead entries, but remember their indices so we can reuse them.
    152     if (entry->IsDead()) {
    153       dead = i;
    154       continue;
    155     }
    156     if (Equals(entry, node)) {
    157       return ReplaceIfTypesMatch(node, entry);
    158     }
    159   }
    160 }
    161 
    162 Reduction ValueNumberingReducer::ReplaceIfTypesMatch(Node* node,
    163                                                      Node* replacement) {
    164   // Make sure the replacement has at least as good type as the original node.
    165   if (NodeProperties::IsTyped(replacement) && NodeProperties::IsTyped(node)) {
    166     Type* replacement_type = NodeProperties::GetType(replacement);
    167     Type* node_type = NodeProperties::GetType(node);
    168     if (!replacement_type->Is(node_type)) {
    169       // Ideally, we would set an intersection of {replacement_type} and
    170       // {node_type} here. However, typing of NumberConstants assigns different
    171       // types to constants with the same value (it creates a fresh heap
    172       // number), which would make the intersection empty. To be safe, we use
    173       // the smaller type if the types are comparable.
    174       if (node_type->Is(replacement_type)) {
    175         NodeProperties::SetType(replacement, node_type);
    176       } else {
    177         // Types are not comparable => do not replace.
    178         return NoChange();
    179       }
    180     }
    181   }
    182   return Replace(replacement);
    183 }
    184 
    185 
    186 void ValueNumberingReducer::Grow() {
    187   // Allocate a new block of entries double the previous capacity.
    188   Node** const old_entries = entries_;
    189   size_t const old_capacity = capacity_;
    190   capacity_ *= 2;
    191   entries_ = temp_zone()->NewArray<Node*>(capacity_);
    192   memset(entries_, 0, sizeof(*entries_) * capacity_);
    193   size_ = 0;
    194   size_t const mask = capacity_ - 1;
    195 
    196   // Insert the old entries into the new block (skipping dead nodes).
    197   for (size_t i = 0; i < old_capacity; ++i) {
    198     Node* const old_entry = old_entries[i];
    199     if (!old_entry || old_entry->IsDead()) continue;
    200     for (size_t j = HashCode(old_entry) & mask;; j = (j + 1) & mask) {
    201       Node* const entry = entries_[j];
    202       if (entry == old_entry) {
    203         // Skip duplicate of the old entry.
    204         break;
    205       }
    206       if (!entry) {
    207         entries_[j] = old_entry;
    208         size_++;
    209         break;
    210       }
    211     }
    212   }
    213 }
    214 
    215 }  // namespace compiler
    216 }  // namespace internal
    217 }  // namespace v8
    218