Introduce a new data structure, the SparseMultiSet, and changes to the MI scheduler to use it.

A SparseMultiSet adds multiset behavior to SparseSet, while retaining SparseSet's desirable properties. Essentially, SparseMultiSet provides multiset behavior by storing its dense data in doubly linked lists that are inlined into the dense vector. This allows it to provide good data locality as well as vector-like constant-time clear() and fast constant time find(), insert(), and erase(). It also allows SparseMultiSet to have a builtin recycler rather than keeping SparseSet's behavior of always swapping upon removal, which allows it to preserve more iterators. It's often a better alternative to a SparseSet of a growable container or vector-of-vector.

llvm-svn: 173064

1 files changed, 235 insertions, 0 deletions

diff --git a/llvm/unittests/ADT/SparseMultiSetTest.cpp b/llvm/unittests/ADT/SparseMultiSetTest.cpp
new file mode 100644
index 00000000000..4ac03880633
--- /dev/null
+++ b/llvm/unittests/ADT/SparseMultiSetTest.cpp
@@ -0,0 +1,235 @@
+//===------ ADT/SparseSetTest.cpp - SparseSet unit tests -  -----*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/SparseMultiSet.h"
+#include "gtest/gtest.h"
+
+using namespace llvm;
+
+namespace {
+
+typedef SparseMultiSet<unsigned> USet;
+
+// Empty set tests.
+TEST(SparseMultiSetTest, EmptySet) {
+  USet Set;
+  EXPECT_TRUE(Set.empty());
+  EXPECT_EQ(0u, Set.size());
+
+  Set.setUniverse(10);
+
+  // Lookups on empty set.
+  EXPECT_TRUE(Set.find(0) == Set.end());
+  EXPECT_TRUE(Set.find(9) == Set.end());
+
+  // Same thing on a const reference.
+  const USet &CSet = Set;
+  EXPECT_TRUE(CSet.empty());
+  EXPECT_EQ(0u, CSet.size());
+  EXPECT_TRUE(CSet.find(0) == CSet.end());
+  USet::const_iterator I = CSet.find(5);
+  EXPECT_TRUE(I == CSet.end());
+}
+
+// Single entry set tests.
+TEST(SparseMultiSetTest, SingleEntrySet) {
+  USet Set;
+  Set.setUniverse(10);
+  USet::iterator I = Set.insert(5);
+  EXPECT_TRUE(I != Set.end());
+  EXPECT_TRUE(*I == 5);
+
+  EXPECT_FALSE(Set.empty());
+  EXPECT_EQ(1u, Set.size());
+
+  EXPECT_TRUE(Set.find(0) == Set.end());
+  EXPECT_TRUE(Set.find(9) == Set.end());
+
+  EXPECT_FALSE(Set.contains(0));
+  EXPECT_TRUE(Set.contains(5));
+
+  // Extra insert.
+  I = Set.insert(5);
+  EXPECT_TRUE(I != Set.end());
+  EXPECT_TRUE(I == ++Set.find(5));
+  I--;
+  EXPECT_TRUE(I == Set.find(5));
+
+  // Erase non-existent element.
+  I = Set.find(1);
+  EXPECT_TRUE(I == Set.end());
+  EXPECT_EQ(2u, Set.size());
+  EXPECT_EQ(5u, *Set.find(5));
+
+  // Erase iterator.
+  I = Set.find(5);
+  EXPECT_TRUE(I != Set.end());
+  I = Set.erase(I);
+  EXPECT_TRUE(I != Set.end());
+  I = Set.erase(I);
+  EXPECT_TRUE(I == Set.end());
+  EXPECT_TRUE(Set.empty());
+}
+
+// Multiple entry set tests.
+TEST(SparseMultiSetTest, MultipleEntrySet) {
+  USet Set;
+  Set.setUniverse(10);
+
+  Set.insert(5);
+  Set.insert(5);
+  Set.insert(5);
+  Set.insert(3);
+  Set.insert(2);
+  Set.insert(1);
+  Set.insert(4);
+  EXPECT_EQ(7u, Set.size());
+
+  // Erase last element by key.
+  EXPECT_TRUE(Set.erase(Set.find(4)) == Set.end());
+  EXPECT_EQ(6u, Set.size());
+  EXPECT_FALSE(Set.contains(4));
+  EXPECT_TRUE(Set.find(4) == Set.end());
+
+  // Erase first element by key.
+  EXPECT_EQ(3u, Set.count(5));
+  EXPECT_TRUE(Set.find(5) != Set.end());
+  EXPECT_TRUE(Set.erase(Set.find(5)) != Set.end());
+  EXPECT_EQ(5u, Set.size());
+  EXPECT_EQ(2u, Set.count(5));
+
+  Set.insert(6);
+  Set.insert(7);
+  EXPECT_EQ(7u, Set.size());
+
+  // Erase tail by iterator.
+  EXPECT_TRUE(Set.getTail(6) == Set.getHead(6));
+  USet::iterator I = Set.erase(Set.find(6));
+  EXPECT_TRUE(I == Set.end());
+  EXPECT_EQ(6u, Set.size());
+
+  // Erase tails by iterator.
+  EXPECT_EQ(2u, Set.count(5));
+  I = Set.getTail(5);
+  I = Set.erase(I);
+  EXPECT_TRUE(I == Set.end());
+  --I;
+  EXPECT_EQ(1u, Set.count(5));
+  EXPECT_EQ(5u, *I);
+  I = Set.erase(I);
+  EXPECT_TRUE(I == Set.end());
+  EXPECT_EQ(0u, Set.count(5));
+
+  Set.insert(8);
+  Set.insert(8);
+  Set.insert(8);
+  Set.insert(8);
+  Set.insert(8);
+
+  // Erase all the 8s
+  EXPECT_EQ(5u, std::distance(Set.getHead(8), Set.end()));
+  Set.eraseAll(8);
+  EXPECT_EQ(0u, std::distance(Set.getHead(8), Set.end()));
+
+  // Clear and resize the universe.
+  Set.clear();
+  EXPECT_EQ(0u, Set.size());
+  EXPECT_FALSE(Set.contains(3));
+  Set.setUniverse(1000);
+
+  // Add more than 256 elements.
+  for (unsigned i = 100; i != 800; ++i)
+    Set.insert(i);
+
+  for (unsigned i = 0; i != 10; ++i)
+    Set.eraseAll(i);
+
+  for (unsigned i = 100; i != 800; ++i)
+    EXPECT_EQ(1u, Set.count(i));
+
+  EXPECT_FALSE(Set.contains(99));
+  EXPECT_FALSE(Set.contains(800));
+  EXPECT_EQ(700u, Set.size());
+}
+
+// Test out iterators
+TEST(SparseMultiSetTest, Iterators) {
+  USet Set;
+  Set.setUniverse(100);
+
+  Set.insert(0);
+  Set.insert(1);
+  Set.insert(2);
+  Set.insert(0);
+  Set.insert(1);
+  Set.insert(0);
+
+  USet::RangePair RangePair = Set.equal_range(0);
+  USet::iterator B = RangePair.first;
+  USet::iterator E = RangePair.second;
+
+  // Move the iterators around, going to end and coming back.
+  EXPECT_EQ(3u, std::distance(B, E));
+  EXPECT_EQ(B, --(--(--E)));
+  EXPECT_EQ(++(++(++E)), Set.end());
+  EXPECT_EQ(B, --(--(--E)));
+  EXPECT_EQ(++(++(++E)), Set.end());
+
+  // Insert into the tail, and move around again
+  Set.insert(0);
+  EXPECT_EQ(B, --(--(--(--E))));
+  EXPECT_EQ(++(++(++(++E))), Set.end());
+  EXPECT_EQ(B, --(--(--(--E))));
+  EXPECT_EQ(++(++(++(++E))), Set.end());
+
+  // Erase a tail, and move around again
+  USet::iterator Erased = Set.erase(Set.getTail(0));
+  EXPECT_EQ(Erased, E);
+  EXPECT_EQ(B, --(--(--E)));
+
+  USet Set2;
+  Set2.setUniverse(11);
+  Set2.insert(3);
+  EXPECT_TRUE(!Set2.contains(0));
+  EXPECT_TRUE(!Set.contains(3));
+
+  EXPECT_EQ(Set2.getHead(3), Set2.getTail(3));
+  EXPECT_EQ(Set2.getHead(0), Set2.getTail(0));
+  B = Set2.find(3);
+  EXPECT_EQ(Set2.find(3), --(++B));
+}
+
+struct Alt {
+  unsigned Value;
+  explicit Alt(unsigned x) : Value(x) {}
+  unsigned getSparseSetIndex() const { return Value - 1000; }
+};
+
+TEST(SparseMultiSetTest, AltStructSet) {
+  typedef SparseMultiSet<Alt> ASet;
+  ASet Set;
+  Set.setUniverse(10);
+  Set.insert(Alt(1005));
+
+  ASet::iterator I = Set.find(5);
+  ASSERT_TRUE(I != Set.end());
+  EXPECT_EQ(1005u, I->Value);
+
+  Set.insert(Alt(1006));
+  Set.insert(Alt(1006));
+  I = Set.erase(Set.find(6));
+  ASSERT_TRUE(I != Set.end());
+  EXPECT_EQ(1006u, I->Value);
+  I = Set.erase(Set.find(6));
+  ASSERT_TRUE(I == Set.end());
+
+  EXPECT_TRUE(Set.contains(5));
+  EXPECT_FALSE(Set.contains(6));
+}
+} // namespace