[APInt] Fix getBitsNeeded for INT_MIN values

[Quolyk]

Summary

This patch fixes behaviour of APInt::getBitsNeeded for INT_MIN 10 bits values.

[grandinj]

lib/Support/APInt.cpp

488

this seems inefficient? we're calling logbase2 and exactlogbase2? Perhaps just call isPowerOf2() directly since exactlogbase2 is

int32_t exactLogBase2() const {

  if (!isPowerOf2())
    return -1;
  return logBase2();
}

?

Just a suggestion

[RKSimon]

unittests/ADT/APIntTest.cpp

1269

Please can you add a few other INT_MIN cases - regular and irregular sizes (e.g. i1, i23, i32, i64)

[Quolyk]

Update

[RKSimon]

LGTM - thanks!

lib/Support/APInt.cpp

unsigned APInt::getBitsNeeded(StringRef str, uint8_t radix) {
   unsigned sufficient
     = radix == 10? (slen == 1 ? 4 : slen * 64/18)
                  : (slen == 1 ? 7 : slen * 16/3);
 
   // Convert to the actual binary value.
   APInt tmp(sufficient, StringRef(p, slen), radix);
 
   // Compute how many bits are required. If the log is infinite, assume we need
-  // just bit.
+  // just bit. If the log is exact and value is negative, then the value is
+  // MinSignedValue with (log + 1) bits.
   unsigned log = tmp.logBase2();
   if (log == (unsigned)-1) {
     return isNegative + 1;
+  } else if (isNegative && tmp.isPowerOf2()) {
+    return isNegative + log;
   } else {
     return isNegative + log + 1;
   }
 }
 
 hash_code llvm::hash_value(const APInt &Arg) {
   if (Arg.isSingleWord())
     return hash_combine(Arg.U.VAL);

unittests/ADT/APIntTest.cpp

TEST(APIntTest, StringBitsNeeded10) {
   EXPECT_EQ(5U, APInt::getBitsNeeded("+20", 10));
 
   EXPECT_EQ(2U, APInt::getBitsNeeded( "-0", 10));
   EXPECT_EQ(5U, APInt::getBitsNeeded( "-9", 10));
   EXPECT_EQ(5U, APInt::getBitsNeeded("-10", 10));
   EXPECT_EQ(6U, APInt::getBitsNeeded("-19", 10));
   EXPECT_EQ(6U, APInt::getBitsNeeded("-20", 10));
 
-  // TODO: INT_MIN cases need 1 less bit (PR40897)
-  EXPECT_EQ(9U, APInt::getBitsNeeded("-128", 10));
+  EXPECT_EQ(1U, APInt::getBitsNeeded("-1", 10));
+  EXPECT_EQ(2U, APInt::getBitsNeeded("-2", 10));
+  EXPECT_EQ(3U, APInt::getBitsNeeded("-4", 10));
+  EXPECT_EQ(4U, APInt::getBitsNeeded("-8", 10));
+  EXPECT_EQ(5U, APInt::getBitsNeeded("-16", 10));
+  EXPECT_EQ(6U, APInt::getBitsNeeded("-23", 10));
+  EXPECT_EQ(6U, APInt::getBitsNeeded("-32", 10));
+  EXPECT_EQ(7U, APInt::getBitsNeeded("-64", 10));
+  EXPECT_EQ(8U, APInt::getBitsNeeded("-127", 10));
+  EXPECT_EQ(8U, APInt::getBitsNeeded("-128", 10));
+  EXPECT_EQ(9U, APInt::getBitsNeeded("-255", 10));
+  EXPECT_EQ(9U, APInt::getBitsNeeded("-256", 10));
+  EXPECT_EQ(10U, APInt::getBitsNeeded("-512", 10));
+  EXPECT_EQ(11U, APInt::getBitsNeeded("-1024", 10));
+  EXPECT_EQ(12U, APInt::getBitsNeeded("-1025", 10));
 }
 
 TEST(APIntTest, StringBitsNeeded16) {
   EXPECT_EQ(4U, APInt::getBitsNeeded( "0", 16));
   EXPECT_EQ(4U, APInt::getBitsNeeded( "F", 16));
   EXPECT_EQ(8U, APInt::getBitsNeeded("10", 16));
   EXPECT_EQ(8U, APInt::getBitsNeeded("1F", 16));
   EXPECT_EQ(8U, APInt::getBitsNeeded("20", 16));