diff --git a/llvm/include/llvm/ADT/APInt.h b/llvm/include/llvm/ADT/APInt.h --- a/llvm/include/llvm/ADT/APInt.h +++ b/llvm/include/llvm/ADT/APInt.h @@ -2220,6 +2220,12 @@ /// coefficients. Optional SolveQuadraticEquationWrap(APInt A, APInt B, APInt C, unsigned RangeWidth); + +/// Compare two values, and if they are different, return the position of the +/// most significant bit that is different in the values. +Optional GetPositionOfMostSignificantDifferentBit(const APInt &A, + const APInt &B); + } // End of APIntOps namespace // See friend declaration above. This additional declaration is required in diff --git a/llvm/lib/Support/APInt.cpp b/llvm/lib/Support/APInt.cpp --- a/llvm/lib/Support/APInt.cpp +++ b/llvm/lib/Support/APInt.cpp @@ -3027,6 +3027,15 @@ return X; } +Optional +llvm::APIntOps::GetPositionOfMostSignificantDifferentBit(const APInt &A, + const APInt &B) { + assert(A.getBitWidth() == B.getBitWidth() && "Must have the same bitwidth"); + if (A == B) + return llvm::None; + return A.getBitWidth() - ((A ^ B).countLeadingZeros() + 1); +} + /// StoreIntToMemory - Fills the StoreBytes bytes of memory starting from Dst /// with the integer held in IntVal. void llvm::StoreIntToMemory(const APInt &IntVal, uint8_t *Dst, diff --git a/llvm/unittests/ADT/APIntTest.cpp b/llvm/unittests/ADT/APIntTest.cpp --- a/llvm/unittests/ADT/APIntTest.cpp +++ b/llvm/unittests/ADT/APIntTest.cpp @@ -2723,4 +2723,65 @@ } } +TEST(APIntTest, GetPositionOfMostSignificantDifferentBit) { + EXPECT_EQ(APIntOps::GetPositionOfMostSignificantDifferentBit(APInt(8, 0), + APInt(8, 0)), + llvm::None); + EXPECT_EQ(APIntOps::GetPositionOfMostSignificantDifferentBit(APInt(8, 42), + APInt(8, 42)), + llvm::None); + EXPECT_EQ(*APIntOps::GetPositionOfMostSignificantDifferentBit(APInt(8, 0), + APInt(8, 1)), + 0u); + EXPECT_EQ(*APIntOps::GetPositionOfMostSignificantDifferentBit(APInt(8, 0), + APInt(8, 2)), + 1u); + EXPECT_EQ(*APIntOps::GetPositionOfMostSignificantDifferentBit(APInt(8, 0), + APInt(8, 3)), + 1u); + EXPECT_EQ(*APIntOps::GetPositionOfMostSignificantDifferentBit(APInt(8, 1), + APInt(8, 0)), + 0u); + EXPECT_EQ(APIntOps::GetPositionOfMostSignificantDifferentBit(APInt(8, 1), + APInt(8, 1)), + llvm::None); + EXPECT_EQ(*APIntOps::GetPositionOfMostSignificantDifferentBit(APInt(8, 1), + APInt(8, 2)), + 1u); + EXPECT_EQ(*APIntOps::GetPositionOfMostSignificantDifferentBit(APInt(8, 1), + APInt(8, 3)), + 1u); + EXPECT_EQ(*APIntOps::GetPositionOfMostSignificantDifferentBit(APInt(8, 42), + APInt(8, 112)), + 6u); +} + +TEST(APIntTest, GetPositionOfMostSignificantDifferentBitExaustive) { + auto GetHighestDifferentBitBruteforce = + [](const APInt &V0, const APInt &V1) -> llvm::Optional { + 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); + + EXPECT_EQ(APIntOps::GetPositionOfMostSignificantDifferentBit(A, B), + GetHighestDifferentBitBruteforce(A, B)); + } + } + } +} + } // end anonymous namespace