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.h"
     11 
     12 namespace v8 {
     13 namespace internal {
     14 namespace compiler {
     15 
     16 namespace {
     17 
     18 size_t HashCode(Node* node) {
     19   size_t h = base::hash_combine(node->op()->HashCode(), node->InputCount());
     20   for (int j = 0; j < node->InputCount(); ++j) {
     21     h = base::hash_combine(h, node->InputAt(j)->id());
     22   }
     23   return h;
     24 }
     25 
     26 
     27 bool Equals(Node* a, Node* b) {
     28   DCHECK_NOT_NULL(a);
     29   DCHECK_NOT_NULL(b);
     30   DCHECK_NOT_NULL(a->op());
     31   DCHECK_NOT_NULL(b->op());
     32   if (!a->op()->Equals(b->op())) return false;
     33   if (a->InputCount() != b->InputCount()) return false;
     34   for (int j = 0; j < a->InputCount(); ++j) {
     35     DCHECK_NOT_NULL(a->InputAt(j));
     36     DCHECK_NOT_NULL(b->InputAt(j));
     37     if (a->InputAt(j)->id() != b->InputAt(j)->id()) return false;
     38   }
     39   return true;
     40 }
     41 
     42 }  // namespace
     43 
     44 
     45 ValueNumberingReducer::ValueNumberingReducer(Zone* zone)
     46     : entries_(nullptr), capacity_(0), size_(0), zone_(zone) {}
     47 
     48 
     49 ValueNumberingReducer::~ValueNumberingReducer() {}
     50 
     51 
     52 Reduction ValueNumberingReducer::Reduce(Node* node) {
     53   if (!node->op()->HasProperty(Operator::kIdempotent)) return NoChange();
     54 
     55   const size_t hash = HashCode(node);
     56   if (!entries_) {
     57     DCHECK(size_ == 0);
     58     DCHECK(capacity_ == 0);
     59     // Allocate the initial entries and insert the first entry.
     60     capacity_ = kInitialCapacity;
     61     entries_ = zone()->NewArray<Node*>(kInitialCapacity);
     62     memset(entries_, 0, sizeof(*entries_) * kInitialCapacity);
     63     entries_[hash & (kInitialCapacity - 1)] = node;
     64     size_ = 1;
     65     return NoChange();
     66   }
     67 
     68   DCHECK(size_ < capacity_);
     69   DCHECK(size_ * kCapacityToSizeRatio < capacity_);
     70 
     71   const size_t mask = capacity_ - 1;
     72   size_t dead = capacity_;
     73 
     74   for (size_t i = hash & mask;; i = (i + 1) & mask) {
     75     Node* entry = entries_[i];
     76     if (!entry) {
     77       if (dead != capacity_) {
     78         // Reuse dead entry that we discovered on the way.
     79         entries_[dead] = node;
     80       } else {
     81         // Have to insert a new entry.
     82         entries_[i] = node;
     83         size_++;
     84 
     85         // Resize to keep load factor below 1/kCapacityToSizeRatio.
     86         if (size_ * kCapacityToSizeRatio >= capacity_) Grow();
     87       }
     88       DCHECK(size_ * kCapacityToSizeRatio < capacity_);
     89       return NoChange();
     90     }
     91 
     92     if (entry == node) {
     93       // We need to check for a certain class of collisions here. Imagine the
     94       // following scenario:
     95       //
     96       //  1. We insert node1 with op1 and certain inputs at index i.
     97       //  2. We insert node2 with op2 and certain inputs at index i+1.
     98       //  3. Some other reducer changes node1 to op2 and the inputs from node2.
     99       //
    100       // Now we are called again to reduce node1, and we would return NoChange
    101       // in this case because we find node1 first, but what we should actually
    102       // do is return Replace(node2) instead.
    103       for (size_t j = (i + 1) & mask;; j = (j + 1) & mask) {
    104         Node* entry = entries_[j];
    105         if (!entry) {
    106           // No collision, {node} is fine.
    107           return NoChange();
    108         }
    109         if (entry->IsDead()) {
    110           continue;
    111         }
    112         if (Equals(entry, node)) {
    113           // Overwrite the colliding entry with the actual entry.
    114           entries_[i] = entry;
    115           return Replace(entry);
    116         }
    117       }
    118     }
    119 
    120     // Skip dead entries, but remember their indices so we can reuse them.
    121     if (entry->IsDead()) {
    122       dead = i;
    123       continue;
    124     }
    125     if (Equals(entry, node)) {
    126       return Replace(entry);
    127     }
    128   }
    129 }
    130 
    131 
    132 void ValueNumberingReducer::Grow() {
    133   // Allocate a new block of entries kCapacityToSizeRatio times the previous
    134   // capacity.
    135   Node** const old_entries = entries_;
    136   size_t const old_capacity = capacity_;
    137   capacity_ *= kCapacityToSizeRatio;
    138   entries_ = zone()->NewArray<Node*>(capacity_);
    139   memset(entries_, 0, sizeof(*entries_) * capacity_);
    140   size_ = 0;
    141   size_t const mask = capacity_ - 1;
    142 
    143   // Insert the old entries into the new block (skipping dead nodes).
    144   for (size_t i = 0; i < old_capacity; ++i) {
    145     Node* const old_entry = old_entries[i];
    146     if (!old_entry || old_entry->IsDead()) continue;
    147     for (size_t j = HashCode(old_entry) & mask;; j = (j + 1) & mask) {
    148       Node* const entry = entries_[j];
    149       if (entry == old_entry) {
    150         // Skip duplicate of the old entry.
    151         break;
    152       }
    153       if (!entry) {
    154         entries_[j] = old_entry;
    155         size_++;
    156         break;
    157       }
    158     }
    159   }
    160 }
    161 
    162 }  // namespace compiler
    163 }  // namespace internal
    164 }  // namespace v8
    165