Improve documentation and testing of APIntFromVal

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.

Reviewed-by: Michael Kruse <llvm@meinersbur.de>
Differential Revision: https://reviews.llvm.org/D23910

llvm-svn: 279813

3 files changed, 133 insertions, 7 deletions

diff --git a/polly/include/polly/Support/GICHelper.h b/polly/include/polly/Support/GICHelper.h
index 0b50954df70..4686b6c51cf 100644
--- a/polly/include/polly/Support/GICHelper.h
+++ b/polly/include/polly/Support/GICHelper.h
@@ -39,6 +39,34 @@ class Value;
 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.
diff --git a/polly/lib/Support/GICHelper.cpp b/polly/lib/Support/GICHelper.cpp
index 572904d7fa8..48b601334d1 100644
--- a/polly/lib/Support/GICHelper.cpp
+++ b/polly/lib/Support/GICHelper.cpp
@@ -21,6 +21,8 @@
 #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,
@@ -47,18 +49,29 @@ __isl_give isl_val *polly::isl_valFromAPInt(isl_ctx *Ctx, const APInt Int,
 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));
+  assert(isl_val_is_int(Val) && "Only integers can be converted to APInt");
 
-  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);
+  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());
 
diff --git a/polly/unittests/Isl/IslTest.cpp b/polly/unittests/Isl/IslTest.cpp
index 493a9e044b9..6b3fc03c96b 100644
--- a/polly/unittests/Isl/IslTest.cpp
+++ b/polly/unittests/Isl/IslTest.cpp
@@ -65,34 +65,119 @@ TEST(Isl, IslValToAPInt) {
   {
     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);