Improve documentation and testing of APIntFromVal

[grosser]

Summary

The recent unit tests we gained made clear that the semantics of APIntFromVal
are not clear, due to missing documentation. In this change we document both
the calling interface as well as the implementation of APIntFromVal. We also
make the implementation easier to read by removing the use of magic numbers.
Finally, we add tests to check the bitwidth of the created values as well as
the correct modeling of very large numbers.

[Meinersbur]

Thank you for the extensive documentation and adding more test cases.

include/polly/Support/GICHelper.h

46 ↗

(On Diff #69323)

assert() is not a guaranteed behavior. Better mention that the function can only be called on integer isl_vals.

55–64 ↗

(On Diff #69323)

Cool! More than I hoped for.

I'd remove the Unsigned column. It gives the impression that an unsigned interpretation would make sense. But maybe add a bitwidth column?

lib/Support/GICHelper.cpp

65 ↗

(On Diff #69323)

Can you mention 'negate'=='two's complement'?

unittests/Isl/IslTest.cpp

68 ↗

(On Diff #69323)

Suggestion:
"Compare with the two's complement of -1 in a 1-bit integer"

69–70 ↗

(On Diff #69323)

Remove fixme

150 ↗

(On Diff #69323)

Wow! Truly large integers.

[grosser]

Address Michael's comments.

[grosser]

Thanks for the helpful remarks. I tried to address all of them.

[Meinersbur]

LGTM

unittests/Isl/IslTest.cpp

68 ↗

(On Diff #69337)

I had replacing the comment " APInt has no sign bit, so never equals to a negative number", but of course it is still a valid statement.

69 ↗

(On Diff #69337)

Nitpick: Dot at the end of the sentence.

[grosser]

Thank you. I addressed the last two comments and committed.

polly/trunk/include/polly/Support/GICHelper.h

 
 namespace llvm {
 class Value;
 } // namespace llvm
 
 namespace polly {
 __isl_give isl_val *isl_valFromAPInt(isl_ctx *Ctx, const llvm::APInt Int,
                                      bool IsSigned);
+
+/// @brief Translate isl_val to llvm::APInt.
+///
+/// This function can only be called on isl_val values which are integers.
+/// Calling this function with a non-integral rational, NaN or infinity value
+/// is not allowed.
+///
+/// As the input isl_val may be negative, the APInt that this function returns
+/// must always be interpreted as signed two's complement value. The bitwidth of
+/// the generated APInt is always the minimal bitwidth necessary to model the
+/// provided integer when interpreting the bitpattern as signed value.
+///
+/// Some example conversions are:
+///
+///   Input      Bits    Signed  Bitwidth
+///       0 ->      0         0         1
+///      -1 ->      1        -1         1
+///       1 ->     01         1         2
+///      -2 ->     10        -2         2
+///       2 ->    010         2         3
+///      -3 ->    101        -3         3
+///       3 ->    011         3         3
+///      -4 ->    100        -4         3
+///       4 ->   0100         4         4
+///
+/// @param Val The isl val to translate.
+///
+/// @return The APInt value corresponding to @p Val.
 llvm::APInt APIntFromVal(__isl_take isl_val *Val);
 
 /// @brief Get c++ string from Isl objects.
 //@{
 std::string stringFromIslObj(__isl_keep isl_map *map);
 std::string stringFromIslObj(__isl_keep isl_union_map *umap);
 std::string stringFromIslObj(__isl_keep isl_set *set);
 std::string stringFromIslObj(__isl_keep isl_union_set *uset);

polly/trunk/lib/Support/GICHelper.cpp

 #include "isl/map.h"
 #include "isl/schedule.h"
 #include "isl/set.h"
 #include "isl/space.h"
 #include "isl/union_map.h"
 #include "isl/union_set.h"
 #include "isl/val.h"
 
+#include <climits>
+
 using namespace llvm;
 
 __isl_give isl_val *polly::isl_valFromAPInt(isl_ctx *Ctx, const APInt Int,
                                             bool IsSigned) {
   APInt Abs;
   isl_val *v;
 
   if (IsSigned)
if (IsSigned && Int.isNegative())
     v = isl_val_neg(v);
 
   return v;
 }
 
 APInt polly::APIntFromVal(__isl_take isl_val *Val) {
   uint64_t *Data;
   int NumChunks;
+  const static int ChunkSize = sizeof(uint64_t);
 
-  NumChunks = isl_val_n_abs_num_chunks(Val, sizeof(uint64_t));
-
-  Data = (uint64_t *)malloc(NumChunks * sizeof(uint64_t));
-  isl_val_get_abs_num_chunks(Val, sizeof(uint64_t), Data);
-  APInt A(8 * sizeof(uint64_t) * NumChunks, NumChunks, Data);
+  assert(isl_val_is_int(Val) && "Only integers can be converted to APInt");
 
+  NumChunks = isl_val_n_abs_num_chunks(Val, ChunkSize);
+  Data = (uint64_t *)malloc(NumChunks * ChunkSize);
+  isl_val_get_abs_num_chunks(Val, ChunkSize, Data);
+  int NumBits = CHAR_BIT * ChunkSize * NumChunks;
+  APInt A(NumBits, NumChunks, Data);
+
+  // As isl provides only an interface to obtain data that describes the
+  // absolute value of an isl_val, A at this point always contains a positive
+  // number. In case Val was originally negative, we expand the size of A by
+  // one and negate the value (in two's complement representation). As a result,
+  // the new value in A corresponds now with Val.
   if (isl_val_is_neg(Val)) {
     A = A.zext(A.getBitWidth() + 1);
     A = -A;
   }
 
+  // isl may represent small numbers with more than the minimal number of bits.
+  // We truncate the APInt to the minimal number of bits needed to represent the
+  // signed value it contains, to ensure that the bitwidth is always minimal.
   if (A.getMinSignedBits() < A.getBitWidth())
     A = A.trunc(A.getMinSignedBits());
 
   free(Data);
   isl_val_free(Val);
   return A;
 }
 

polly/trunk/unittests/Isl/IslTest.cpp

 }
 
 TEST(Isl, IslValToAPInt) {
   isl_ctx *IslCtx = isl_ctx_alloc();
 
   {
     auto *IslNOne = isl_val_int_from_si(IslCtx, -1);
     auto APNOne = APIntFromVal(IslNOne);
-    // APInt has no sign bit, so never equals to a negative number.
-    // FIXME: The canonical representation of a negative APInt is two's
-    // complement.
+    // Compare with the two's complement of -1 in a 1-bit integer.
     EXPECT_EQ(APNOne, 1);
+    EXPECT_EQ(APNOne.getBitWidth(), 1u);
+  }
+
+  {
+    auto *IslNTwo = isl_val_int_from_si(IslCtx, -2);
+    auto APNTwo = APIntFromVal(IslNTwo);
+    // Compare with the two's complement of -2 in a 2-bit integer.
+    EXPECT_EQ(APNTwo, 2);
+    EXPECT_EQ(APNTwo.getBitWidth(), 2u);
+  }
+
+  {
+    auto *IslNThree = isl_val_int_from_si(IslCtx, -3);
+    auto APNThree = APIntFromVal(IslNThree);
+    // Compare with the two's complement of -3 in a 3-bit integer.
+    EXPECT_EQ(APNThree, 5);
+    EXPECT_EQ(APNThree.getBitWidth(), 3u);
+  }
+
+  {
+    auto *IslNFour = isl_val_int_from_si(IslCtx, -4);
+    auto APNFour = APIntFromVal(IslNFour);
+    // Compare with the two's complement of -4 in a 3-bit integer.
+    EXPECT_EQ(APNFour, 4);
+    EXPECT_EQ(APNFour.getBitWidth(), 3u);
   }
 
   {
     auto *IslZero = isl_val_int_from_ui(IslCtx, 0);
     auto APZero = APIntFromVal(IslZero);
     EXPECT_EQ(APZero, 0);
+    EXPECT_EQ(APZero.getBitWidth(), 1u);
   }
 
   {
     auto *IslOne = isl_val_int_from_ui(IslCtx, 1);
     auto APOne = APIntFromVal(IslOne);
     EXPECT_EQ(APOne, 1);
+    EXPECT_EQ(APOne.getBitWidth(), 2u);
   }
 
   {
     auto *IslTwo = isl_val_int_from_ui(IslCtx, 2);
     auto APTwo = APIntFromVal(IslTwo);
     EXPECT_EQ(APTwo, 2);
+    EXPECT_EQ(APTwo.getBitWidth(), 3u);
+  }
+
+  {
+    auto *IslThree = isl_val_int_from_ui(IslCtx, 3);
+    auto APThree = APIntFromVal(IslThree);
+    EXPECT_EQ(APThree, 3);
+
+    EXPECT_EQ(APThree.getBitWidth(), 3u);
+  }
+
+  {
+    auto *IslFour = isl_val_int_from_ui(IslCtx, 4);
+    auto APFour = APIntFromVal(IslFour);
+    EXPECT_EQ(APFour, 4);
+    EXPECT_EQ(APFour.getBitWidth(), 4u);
   }
 
   {
     auto *IslNOne = isl_val_int_from_ui(IslCtx, (1ull << 32) - 1);
     auto APNOne = APIntFromVal(IslNOne);
     EXPECT_EQ(APNOne, (1ull << 32) - 1);
+    EXPECT_EQ(APNOne.getBitWidth(), 33u);
+  }
+
+  {
+    auto *IslLargeNum = isl_val_int_from_ui(IslCtx, (1ull << 60) - 1);
+    auto APLargeNum = APIntFromVal(IslLargeNum);
+    EXPECT_EQ(APLargeNum, (1ull << 60) - 1);
+    EXPECT_EQ(APLargeNum.getBitWidth(), 61u);
+  }
+
+  {
+    auto *IslExp = isl_val_int_from_ui(IslCtx, 500);
+    auto *IslLargePow2 = isl_val_2exp(IslExp);
+    auto APLargePow2 = APIntFromVal(IslLargePow2);
+    EXPECT_TRUE(APLargePow2.isPowerOf2());
+    EXPECT_EQ(APLargePow2.getBitWidth(), 502u);
+    EXPECT_EQ(APLargePow2.getMinSignedBits(), 502u);
+  }
+
+  {
+    auto *IslExp = isl_val_int_from_ui(IslCtx, 500);
+    auto *IslLargeNPow2 = isl_val_neg(isl_val_2exp(IslExp));
+    auto APLargeNPow2 = APIntFromVal(IslLargeNPow2);
+    EXPECT_EQ(APLargeNPow2.getBitWidth(), 501u);
+    EXPECT_EQ(APLargeNPow2.getMinSignedBits(), 501u);
+    EXPECT_EQ((-APLargeNPow2).exactLogBase2(), 500);
+  }
+
+  {
+    auto *IslExp = isl_val_int_from_ui(IslCtx, 512);
+    auto *IslLargePow2 = isl_val_2exp(IslExp);
+    auto APLargePow2 = APIntFromVal(IslLargePow2);
+    EXPECT_TRUE(APLargePow2.isPowerOf2());
+    EXPECT_EQ(APLargePow2.getBitWidth(), 514u);
+    EXPECT_EQ(APLargePow2.getMinSignedBits(), 514u);
+  }
+
+  {
+    auto *IslExp = isl_val_int_from_ui(IslCtx, 512);
+    auto *IslLargeNPow2 = isl_val_neg(isl_val_2exp(IslExp));
+    auto APLargeNPow2 = APIntFromVal(IslLargeNPow2);
+    EXPECT_EQ(APLargeNPow2.getBitWidth(), 513u);
+    EXPECT_EQ(APLargeNPow2.getMinSignedBits(), 513u);
+    EXPECT_EQ((-APLargeNPow2).exactLogBase2(), 512);
   }
 
   isl_ctx_free(IslCtx);
 }
 
 } // anonymous namespace