Move constructor for IntervalMap.

[sfuniak]

Summary

IntervalMap has a user-defined destructor but no user-defined copy constructor. The (compiler-generated) implicitly-declared copy constructor is wrong, because it performs a trivial copy, which is problematic when the IntervalMap contains more than N intervals. This copy constructor is invoked in some places that assume that IntervalMap can be copied, or at least moved, e.g. when generating the MLIR PDL bytecode. The solution is to define a move constructor that will be used instead of the implicitly-declared copy constructor.

[sfuniak]

Ran clang-format.

llvm/include/llvm/ADT/IntervalMap.h

 
 public:
   explicit IntervalMap(Allocator &a) : height(0), rootSize(0), allocator(a) {
     assert((uintptr_t(&data) & (alignof(RootLeaf) - 1)) == 0 &&
            "Insufficient alignment");
     new(&rootLeaf()) RootLeaf();
   }
 
+  IntervalMap(IntervalMap &&other)
+    : IntervalMap(other.allocator) {
+    std::swap(data, other.data);
+    std::swap(height, other.height);
+    std::swap(rootSize, other.rootSize);
+  }
+
   ~IntervalMap() {
     clear();
     rootLeaf().~RootLeaf();
   }
 
   /// empty -  Return true when no intervals are mapped.
   bool empty() const {
     return rootSize == 0;

llvm/unittests/ADT/IntervalMapTest.cpp

TEST(IntervalMapTest, OverlapsHalfOpen) {
   EXPECT_TRUE(map.overlaps(35, 36));
   EXPECT_FALSE(map.overlaps(40, 45));
   EXPECT_FALSE(map.overlaps(45, 46));
   EXPECT_FALSE(map.overlaps(60, 61));
   EXPECT_FALSE(map.overlaps(60, 66));
   EXPECT_FALSE(map.overlaps(66, 67));
 }
 
+TEST(IntervalMapTest, MoveEmpty) {
+  UUMap::Allocator allocator;
+  UUMap map(allocator);
+  UUMap map2(std::move(map));
+  EXPECT_TRUE(map2.empty());
+}
+
+TEST(IntervalMapTest, MoveSingleEntry) {
+  UUMap::Allocator allocator;
+  UUMap map(allocator);
+  map.insert(10, 20, 0);
+  UUMap map2(std::move(map));
+
+  UUMap::iterator I = map2.begin();
+  ASSERT_TRUE(I.valid());
+  EXPECT_EQ(10u, I.start());
+  EXPECT_EQ(20u, I.stop());
+  EXPECT_EQ(0u, I.value());
+  ++I;
+  EXPECT_FALSE(I.valid());
+}
+
+TEST(IntervalMapTest, MoveLargeMap) {
+  UUMap::Allocator allocator;
+  UUMap map(allocator);
+  for (unsigned i = 0; i < 500; i += 20) {
+    map.insert(i, i + 10, 0);
+  }
+  UUMap map2(std::move(map));
+
+  UUMap::iterator I = map2.begin();
+  for (unsigned i = 0; i < 500; i += 20) {
+    ASSERT_TRUE(I.valid());
+    EXPECT_EQ(i, I.start());
+    EXPECT_EQ(i + 10, I.stop());
+    EXPECT_EQ(0u, I.value());
+    ++I;
+  }
+
+  EXPECT_FALSE(I.valid());
+}
+
 TEST(IntervalMapOverlapsTest, SmallMaps) {
   typedef IntervalMapOverlaps<UUMap,UUMap> UUOverlaps;
   UUMap::Allocator allocator;
   UUMap mapA(allocator);
   UUMap mapB(allocator);
 
   // empty, empty.
   EXPECT_FALSE(UUOverlaps(mapA, mapB).valid());