1 files changed, 71 insertions, 0 deletions
diff --git a/llvm/unittests/ADT/APIntTest.cpp b/llvm/unittests/ADT/APIntTest.cpp
index 5130b9420d6..fe4e7426099 100644
--- a/llvm/unittests/ADT/APIntTest.cpp
+++ b/llvm/unittests/ADT/APIntTest.cpp
@@ -2723,4 +2723,75 @@ TEST(APIntTest, MultiplicativeInverseExaustive) {
   }
 }
 
+TEST(APIntTest, GetMostSignificantDifferentBit) {
+  EXPECT_EQ(APIntOps::GetMostSignificantDifferentBit(APInt(8, 0), APInt(8, 0)),
+            llvm::None);
+  EXPECT_EQ(
+      APIntOps::GetMostSignificantDifferentBit(APInt(8, 42), APInt(8, 42)),
+      llvm::None);
+  EXPECT_EQ(*APIntOps::GetMostSignificantDifferentBit(APInt(8, 0), APInt(8, 1)),
+            0u);
+  EXPECT_EQ(*APIntOps::GetMostSignificantDifferentBit(APInt(8, 0), APInt(8, 2)),
+            1u);
+  EXPECT_EQ(*APIntOps::GetMostSignificantDifferentBit(APInt(8, 0), APInt(8, 3)),
+            1u);
+  EXPECT_EQ(*APIntOps::GetMostSignificantDifferentBit(APInt(8, 1), APInt(8, 0)),
+            0u);
+  EXPECT_EQ(APIntOps::GetMostSignificantDifferentBit(APInt(8, 1), APInt(8, 1)),
+            llvm::None);
+  EXPECT_EQ(*APIntOps::GetMostSignificantDifferentBit(APInt(8, 1), APInt(8, 2)),
+            1u);
+  EXPECT_EQ(*APIntOps::GetMostSignificantDifferentBit(APInt(8, 1), APInt(8, 3)),
+            1u);
+  EXPECT_EQ(
+      *APIntOps::GetMostSignificantDifferentBit(APInt(8, 42), APInt(8, 112)),
+      6u);
+}
+
+TEST(APIntTest, GetMostSignificantDifferentBitExaustive) {
+  auto GetHighestDifferentBitBruteforce =
+      [](const APInt &V0, const APInt &V1) -> llvm::Optional<unsigned> {
+    assert(V0.getBitWidth() == V1.getBitWidth() && "Must have same bitwidth");
+    if (V0 == V1)
+      return llvm::None; // Bitwise identical.
+    // There is a mismatch. Let's find the most significant different bit.
+    for (int Bit = V0.getBitWidth() - 1; Bit >= 0; --Bit) {
+      if (V0[Bit] == V1[Bit])
+        continue;
+      return Bit;
+    }
+    llvm_unreachable("Must have found bit mismatch.");
+  };
+
+  for (unsigned BitWidth = 1; BitWidth <= 8; ++BitWidth) {
+    for (unsigned V0 = 0; V0 < (1u << BitWidth); ++V0) {
+      for (unsigned V1 = 0; V1 < (1u << BitWidth); ++V1) {
+        APInt A = APInt(BitWidth, V0);
+        APInt B = APInt(BitWidth, V1);
+
+        auto Bit = APIntOps::GetMostSignificantDifferentBit(A, B);
+        EXPECT_EQ(Bit, GetHighestDifferentBitBruteforce(A, B));
+
+        if (!Bit.hasValue())
+          EXPECT_EQ(A, B);
+        else {
+          EXPECT_NE(A, B);
+          for (unsigned NumLowBits = 0; NumLowBits <= BitWidth; ++NumLowBits) {
+            APInt Adash = A;
+            Adash.clearLowBits(NumLowBits);
+            APInt Bdash = B;
+            Bdash.clearLowBits(NumLowBits);
+            // Clearing only low bits up to and including *Bit is sufficient
+            // to make values equal.
+            if (NumLowBits >= 1 + *Bit)
+              EXPECT_EQ(Adash, Bdash);
+            else
+              EXPECT_NE(Adash, Bdash);
+          }
+        }
+      }
+    }
+  }
+}
+
 } // end anonymous namespace