[APInt] Introduce APIntOps::GetPositionOfMostSignificantDifferentBit()

[lebedev.ri]

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.

[RKSimon]

llvm/unittests/ADT/APIntTest.cpp

2774

Doesn't this only run once for BitWidth = 8 ?

[lebedev.ri]

llvm/unittests/ADT/APIntTest.cpp

2774

Oops, forgot to undo that..

[lebedev.ri]

Improve test, NFC.

[nikic]

LGTM, though I'd suggest a more compact name.

llvm/include/llvm/ADT/APInt.h

2227

The name seems a bit excessive -- I think GetMostSignificantDifferingBit would have the same information content.

[xbolva00]

llvm/include/llvm/ADT/APInt.h

2227

or GetPosOfMostSignificantDifferentBit

[lebedev.ri]

Thank you for the review!
I will go with the most short one,
Also, this needs a bit more tests, will add when committing.

llvm/include/llvm/ADT/APInt.h

 /// an *unsigned* overflow (if the values are treated as unsigned).
 /// To find a solution for a signed overflow, treat it as a problem of
 /// finding an unsigned overflow with a range with of BW-1.
 ///
 /// The returned value may have a different bit width from the input
 /// coefficients.
 Optional<APInt> 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<unsigned> GetPositionOfMostSignificantDifferentBit(const APInt &A,
+                                                            const APInt &B);
+
 } // End of APIntOps namespace
 
 // See friend declaration above. This additional declaration is required in
 // order to compile LLVM with IBM xlC compiler.
 hash_code hash_value(const APInt &Arg);
 
 /// StoreIntToMemory - Fills the StoreBytes bytes of memory starting from Dst
 /// with the integer held in IntVal.

llvm/lib/Support/APInt.cpp

if (!SignChange) {
     return None;
   }
 
   X += 1;
   LLVM_DEBUG(dbgs() << __func__ << ": solution (wrap): " << X << '\n');
   return X;
 }
 
+Optional<unsigned>
+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,
                             unsigned StoreBytes) {
   assert((IntVal.getBitWidth()+7)/8 >= StoreBytes && "Integer too small!");
   const uint8_t *Src = (const uint8_t *)IntVal.getRawData();
 
   if (sys::IsLittleEndianHost) {

llvm/unittests/ADT/APIntTest.cpp

for (unsigned Value = 0; Value < (1u << BitWidth); ++Value) {
       } else {
         // Multiplicative inverse does not exist for even numbers (and 0).
         EXPECT_TRUE(MulInv.isNullValue());
       }
     }
   }
 }
 
+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<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);
+
+        EXPECT_EQ(APIntOps::GetPositionOfMostSignificantDifferentBit(A, B),
+                  GetHighestDifferentBitBruteforce(A, B));
+      }
+    }
+  }
+}
+
 } // end anonymous namespace