[APInt] Introduce APIntOps::GetMostSignificantDifferentBit()
Summary:
Compare two values, and if they are different, return the position of the
most significant bit that is different in the values.
Needed for D69387.
Reviewers: nikic, spatel, sanjoy, RKSimon
Reviewed By: nikic
Subscribers: xbolva00, hiraditya, dexonsmith, llvm-commits
Tags: #llvm
Differential Revision: https://reviews.llvm.org/D69439
diff --git a/llvm/unittests/ADT/APIntTest.cpp b/llvm/unittests/ADT/APIntTest.cpp
index 5130b94..fe4e742 100644
--- a/llvm/unittests/ADT/APIntTest.cpp
+++ b/llvm/unittests/ADT/APIntTest.cpp
@@ -2723,4 +2723,75 @@
}
}
+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