value-numbering-reducer.cc 5.87 KB
Newer Older
1 2 3 4
// Copyright 2014 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

5 6
#include "src/compiler/value-numbering-reducer.h"

7 8
#include <cstring>

9
#include "src/base/functional.h"
10
#include "src/compiler/node-properties.h"
11 12 13 14 15 16
#include "src/compiler/node.h"

namespace v8 {
namespace internal {
namespace compiler {

17 18 19 20 21 22
ValueNumberingReducer::ValueNumberingReducer(Zone* temp_zone, Zone* graph_zone)
    : entries_(nullptr),
      capacity_(0),
      size_(0),
      temp_zone_(temp_zone),
      graph_zone_(graph_zone) {}
23

24
ValueNumberingReducer::~ValueNumberingReducer() {}
25 26


27
Reduction ValueNumberingReducer::Reduce(Node* node) {
28
  if (!node->op()->HasProperty(Operator::kIdempotent)) return NoChange();
29

30
  const size_t hash = NodeProperties::HashCode(node);
31
  if (!entries_) {
32 33
    DCHECK_EQ(0, size_);
    DCHECK_EQ(0, capacity_);
34 35
    // Allocate the initial entries and insert the first entry.
    capacity_ = kInitialCapacity;
36
    entries_ = temp_zone()->NewArray<Node*>(kInitialCapacity);
37 38 39 40
    memset(entries_, 0, sizeof(*entries_) * kInitialCapacity);
    entries_[hash & (kInitialCapacity - 1)] = node;
    size_ = 1;
    return NoChange();
41 42
  }

43
  DCHECK(size_ < capacity_);
44
  DCHECK(size_ + size_ / 4 < capacity_);
45 46 47 48 49 50 51 52 53 54 55 56 57 58 59

  const size_t mask = capacity_ - 1;
  size_t dead = capacity_;

  for (size_t i = hash & mask;; i = (i + 1) & mask) {
    Node* entry = entries_[i];
    if (!entry) {
      if (dead != capacity_) {
        // Reuse dead entry that we discovered on the way.
        entries_[dead] = node;
      } else {
        // Have to insert a new entry.
        entries_[i] = node;
        size_++;

60 61
        // Resize to keep load factor below 80%
        if (size_ + size_ / 4 >= capacity_) Grow();
62
      }
63
      DCHECK(size_ + size_ / 4 < capacity_);
64 65
      return NoChange();
    }
66

67
    if (entry == node) {
68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86
      // We need to check for a certain class of collisions here. Imagine the
      // following scenario:
      //
      //  1. We insert node1 with op1 and certain inputs at index i.
      //  2. We insert node2 with op2 and certain inputs at index i+1.
      //  3. Some other reducer changes node1 to op2 and the inputs from node2.
      //
      // Now we are called again to reduce node1, and we would return NoChange
      // in this case because we find node1 first, but what we should actually
      // do is return Replace(node2) instead.
      for (size_t j = (i + 1) & mask;; j = (j + 1) & mask) {
        Node* entry = entries_[j];
        if (!entry) {
          // No collision, {node} is fine.
          return NoChange();
        }
        if (entry->IsDead()) {
          continue;
        }
87 88 89 90 91 92 93 94 95 96 97 98
        if (entry == node) {
          // Collision with ourselves, doesn't count as a real collision.
          // Opportunistically clean-up the duplicate entry if we're at the end
          // of a bucket.
          if (!entries_[(j + 1) & mask]) {
            entries_[j] = nullptr;
            size_--;
            return NoChange();
          }
          // Otherwise, keep searching for another collision.
          continue;
        }
99
        if (NodeProperties::Equals(entry, node)) {
100 101 102 103 104 105 106 107 108 109 110 111
          Reduction reduction = ReplaceIfTypesMatch(node, entry);
          if (reduction.Changed()) {
            // Overwrite the colliding entry with the actual entry.
            entries_[i] = entry;
            // Opportunistically clean-up the duplicate entry if we're at the
            // end of a bucket.
            if (!entries_[(j + 1) & mask]) {
              entries_[j] = nullptr;
              size_--;
            }
          }
          return reduction;
112 113
        }
      }
114
    }
115

116 117 118 119 120
    // Skip dead entries, but remember their indices so we can reuse them.
    if (entry->IsDead()) {
      dead = i;
      continue;
    }
121
    if (NodeProperties::Equals(entry, node)) {
122 123 124 125 126 127 128 129 130
      return ReplaceIfTypesMatch(node, entry);
    }
  }
}

Reduction ValueNumberingReducer::ReplaceIfTypesMatch(Node* node,
                                                     Node* replacement) {
  // Make sure the replacement has at least as good type as the original node.
  if (NodeProperties::IsTyped(replacement) && NodeProperties::IsTyped(node)) {
131 132
    Type replacement_type = NodeProperties::GetType(replacement);
    Type node_type = NodeProperties::GetType(node);
133
    if (!replacement_type.Is(node_type)) {
134 135 136 137 138
      // Ideally, we would set an intersection of {replacement_type} and
      // {node_type} here. However, typing of NumberConstants assigns different
      // types to constants with the same value (it creates a fresh heap
      // number), which would make the intersection empty. To be safe, we use
      // the smaller type if the types are comparable.
139
      if (node_type.Is(replacement_type)) {
140 141 142 143
        NodeProperties::SetType(replacement, node_type);
      } else {
        // Types are not comparable => do not replace.
        return NoChange();
144
      }
145 146
    }
  }
147
  return Replace(replacement);
148
}
149 150


151
void ValueNumberingReducer::Grow() {
152
  // Allocate a new block of entries double the previous capacity.
153 154
  Node** const old_entries = entries_;
  size_t const old_capacity = capacity_;
155
  capacity_ *= 2;
156
  entries_ = temp_zone()->NewArray<Node*>(capacity_);
157 158 159 160 161 162 163 164
  memset(entries_, 0, sizeof(*entries_) * capacity_);
  size_ = 0;
  size_t const mask = capacity_ - 1;

  // Insert the old entries into the new block (skipping dead nodes).
  for (size_t i = 0; i < old_capacity; ++i) {
    Node* const old_entry = old_entries[i];
    if (!old_entry || old_entry->IsDead()) continue;
165 166
    for (size_t j = NodeProperties::HashCode(old_entry) & mask;;
         j = (j + 1) & mask) {
167 168 169 170 171 172 173 174 175 176
      Node* const entry = entries_[j];
      if (entry == old_entry) {
        // Skip duplicate of the old entry.
        break;
      }
      if (!entry) {
        entries_[j] = old_entry;
        size_++;
        break;
      }
177 178 179 180 181 182 183
    }
  }
}

}  // namespace compiler
}  // namespace internal
}  // namespace v8