From 76f8279e441144844f8c00d92e4a8bcec5814385 Mon Sep 17 00:00:00 2001 From: Tobias Grosser Date: Fri, 26 Aug 2016 10:43:28 +0000 Subject: [PATCH] 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 Differential Revision: https://reviews.llvm.org/D23910 llvm-svn: 279813 --- polly/include/polly/Support/GICHelper.h | 28 ++++++++++ polly/lib/Support/GICHelper.cpp | 21 ++++++-- polly/unittests/Isl/IslTest.cpp | 91 +++++++++++++++++++++++++++++++-- 3 files changed, 133 insertions(+), 7 deletions(-) diff --git a/polly/include/polly/Support/GICHelper.h b/polly/include/polly/Support/GICHelper.h index 0b50954..4686b6c 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 572904d..48b6013 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 + 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 493a9e0..6b3fc03 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); -- 2.7.4