[turbofan] Track multiple maps for LoadElimination.

src/zone/zone-handle-set.h

+// Copyright 2016 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.
+
+#ifndef V8_ZONE_ZONE_HANDLE_SET_H_
+#define V8_ZONE_ZONE_HANDLE_SET_H_
+
+#include "src/handles.h"
+#include "src/zone/zone.h"
+
+namespace v8 {
+namespace internal {
+
+template <typename T>
+class ZoneHandleSet final {
+ public:
+  ZoneHandleSet() : data_(kEmptyTag) {}
+  explicit ZoneHandleSet(Handle<T> handle)
+      : data_(bit_cast<intptr_t>(handle.address()) | kSingletonTag) {
+    DCHECK(IsAligned(bit_cast<intptr_t>(handle.address()), kPointerAlignment));
+  }
+
+  bool is_empty() const { return data_ == kEmptyTag; }
+
+  size_t size() const {
+    if ((data_ & kTagMask) == kEmptyTag) return 0;
+    if ((data_ & kTagMask) == kSingletonTag) return 1;
+    return list()->length();
+  }
+
+  Handle<T> at(size_t i) const {
+    DCHECK_NE(kEmptyTag, data_ & kTagMask);
+    if ((data_ & kTagMask) == kSingletonTag) {
+      DCHECK_EQ(0u, i);
+      return Handle<T>(singleton());
+    }
+    return Handle<T>(list()->at(static_cast<int>(i)));
+  }
+
+  Handle<T> operator[](size_t i) const { return at(i); }
+
+  void insert(Handle<T> handle, Zone* zone) {
+    T** const value = bit_cast<T**>(handle.address());
+    DCHECK(IsAligned(bit_cast<intptr_t>(value), kPointerAlignment));
+    if ((data_ & kTagMask) == kEmptyTag) {
+      data_ = bit_cast<intptr_t>(value) | kSingletonTag;
+    } else if ((data_ & kTagMask) == kSingletonTag) {
+      if (singleton() == value) return;
+      List* list = new (zone) List(2, zone);
+      if (singleton() < value) {
+        list->Add(singleton(), zone);
+        list->Add(value, zone);
+      } else {
+        list->Add(value, zone);
+        list->Add(singleton(), zone);
+      }
+      DCHECK(IsAligned(bit_cast<intptr_t>(list), kPointerAlignment));
+      data_ = bit_cast<intptr_t>(list) | kListTag;
+    } else {
+      DCHECK_EQ(kListTag, data_ & kTagMask);
+      List const* const old_list = list();
+      for (int i = 0; i < old_list->length(); ++i) {
+        if (old_list->at(i) == value) return;
+        if (old_list->at(i) > value) break;
+      }
+      List* new_list = new (zone) List(old_list->length() + 1, zone);
+      int i = 0;
+      for (; i < old_list->length(); ++i) {
+        if (old_list->at(i) > value) break;
+        new_list->Add(old_list->at(i), zone);
+      }
+      new_list->Add(value, zone);
+      for (; i < old_list->length(); ++i) {
+        new_list->Add(old_list->at(i), zone);
+      }
+      DCHECK_EQ(old_list->length() + 1, new_list->length());
+      DCHECK(IsAligned(bit_cast<intptr_t>(new_list), kPointerAlignment));
+      data_ = bit_cast<intptr_t>(new_list) | kListTag;
+    }
+  }
+
+  bool contains(ZoneHandleSet<T> const& other) const {
+    if (data_ == other.data_) return true;
+    if (data_ == kEmptyTag) return false;
+    if (other.data_ == kEmptyTag) return true;
+    if ((data_ & kTagMask) == kSingletonTag) return false;
+    DCHECK_EQ(kListTag, data_ & kTagMask);
+    if ((other.data_ & kTagMask) == kSingletonTag) {
+      return list()->Contains(other.singleton());
+    }
+    DCHECK_EQ(kListTag, other.data_ & kTagMask);
+    // TODO(bmeurer): Optimize this case.
+    for (int i = 0; i < other.list()->length(); ++i) {
+      if (!list()->Contains(other.list()->at(i))) return false;
+    }
+    return true;
+  }
+
+  void remove(Handle<T> handle, Zone* zone) {
+    // TODO(bmeurer): Optimize this case.
+    ZoneHandleSet<T> that;
+    for (size_t i = 0; i < size(); ++i) {
+      Handle<T> value = at(i);
+      if (value.address() != handle.address()) {
+        that.insert(value, zone);
+      }
+    }
+    std::swap(*this, that);
+  }
+
+  friend bool operator==(ZoneHandleSet<T> const& lhs,
+                         ZoneHandleSet<T> const& rhs) {
+    if (lhs.data_ == rhs.data_) return true;
+    if ((lhs.data_ & kTagMask) == kListTag &&
+        (rhs.data_ & kTagMask) == kListTag) {
+      List const* const lhs_list = lhs.list();
+      List const* const rhs_list = rhs.list();
+      if (lhs_list->length() == rhs_list->length()) {
+        for (int i = 0; i < lhs_list->length(); ++i) {
+          if (lhs_list->at(i) != rhs_list->at(i)) return false;
+        }
+        return true;
+      }
+    }
+    return false;
+  }
+
+  friend bool operator!=(ZoneHandleSet<T> const& lhs,
+                         ZoneHandleSet<T> const& rhs) {
+    return !(lhs == rhs);
+  }
+
+  friend size_t hash_value(ZoneHandleSet<T> const& set) {
+    return static_cast<size_t>(set.data_);
+  }
+
+ private:
+  typedef ZoneList<T**> List;
+
+  List const* list() const {
+    DCHECK_EQ(kListTag, data_ & kTagMask);
+    return bit_cast<List const*>(data_ - kListTag);
+  }
+
+  T** singleton() const {
+    DCHECK_EQ(kSingletonTag, data_ & kTagMask);
+    return bit_cast<T**>(data_ - kSingletonTag);
+  }
+
+  enum Tag : intptr_t {
+    kSingletonTag = 0,
+    kEmptyTag = 1,
+    kListTag = 2,
+    kTagMask = 3
+  };
+
+  STATIC_ASSERT(kTagMask < kPointerAlignment);
+
+  intptr_t data_;
+};
+
+}  // namespace internal
+}  // namespace v8
+
+#endif  // V8_ZONE_ZONE_HANDLE_SET_H_