src/v8/src/compiler/value-numbering-reducer.cc

   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::kEliminatable)) 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     if (entry == node) {
  92       return NoChange();
  93     }
  94
  95     // Skip dead entries, but remember their indices so we can reuse them.
  96     if (entry->IsDead()) {
  97       dead = i;
  98       continue;
  99     }
 100     if (Equals(entry, node)) {
 101       return Replace(entry);
 102     }
 103   }
 104 }
 105
 106
 107 void ValueNumberingReducer::Grow() {
 108   // Allocate a new block of entries kCapacityToSizeRatio times the previous
 109   // capacity.
 110   Node** const old_entries = entries_;
 111   size_t const old_capacity = capacity_;
 112   capacity_ *= kCapacityToSizeRatio;
 113   entries_ = zone()->NewArray<Node*>(static_cast<int>(capacity_));
 114   memset(entries_, 0, sizeof(*entries_) * capacity_);
 115   size_ = 0;
 116   size_t const mask = capacity_ - 1;
 117
 118   // Insert the old entries into the new block (skipping dead nodes).
 119   for (size_t i = 0; i < old_capacity; ++i) {
 120     Node* const old_entry = old_entries[i];
 121     if (!old_entry || old_entry->IsDead()) continue;
 122     for (size_t j = HashCode(old_entry) & mask;; j = (j + 1) & mask) {
 123       Node* const entry = entries_[j];
 124       if (entry == old_entry) {
 125         // Skip duplicate of the old entry.
 126         break;
 127       }
 128       if (!entry) {
 129         entries_[j] = old_entry;
 130         size_++;
 131         break;
 132       }
 133     }
 134   }
 135 }
 136
 137 }  // namespace compiler
 138 }  // namespace internal
 139 }  // namespace v8