Mercurial > hg > CbC > CbC_llvm

comparison unittests/ADT/APIntTest.cpp @ 148:63bd29f05246

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
merged
author Shinji KONO <kono@ie.u-ryukyu.ac.jp>
date Wed, 14 Aug 2019 19:46:37 +0900
parents c2174574ed3a
children
comparison
equal deleted inserted replaced
146:3fc4d5c3e21e 148:63bd29f05246
1 //===- llvm/unittest/ADT/APInt.cpp - APInt unit tests ---------------------===// 1 //===- llvm/unittest/ADT/APInt.cpp - APInt unit tests ---------------------===//
2 // 2 //
3 // The LLVM Compiler Infrastructure 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // 4 // See https://llvm.org/LICENSE.txt for license information.
5 // This file is distributed under the University of Illinois Open Source 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 // License. See LICENSE.TXT for details.
7 // 6 //
8 //===----------------------------------------------------------------------===// 7 //===----------------------------------------------------------------------===//
9 8
10 #include "llvm/ADT/APInt.h" 9 #include "llvm/ADT/APInt.h"
11 #include "llvm/ADT/ArrayRef.h" 10 #include "llvm/ADT/ArrayRef.h"
12 #include "llvm/ADT/SmallString.h" 11 #include "llvm/ADT/SmallString.h"
12 #include "llvm/ADT/Twine.h"
13 #include "gtest/gtest.h" 13 #include "gtest/gtest.h"
14 #include <array> 14 #include <array>
15 15
16 using namespace llvm; 16 using namespace llvm;
17 17
1058 testDiv(APInt{1024, 19}.shl(811), 1058 testDiv(APInt{1024, 19}.shl(811),
1059 4356013, // one word 1059 4356013, // one word
1060 APInt{1024, 1}); 1060 APInt{1024, 1});
1061 } 1061 }
1062 1062
1063 TEST(APIntTest, divrem_simple) {
1064 // Test simple cases.
1065 APInt A(65, 2), B(65, 2);
1066 APInt Q, R;
1067
1068 // X / X
1069 APInt::sdivrem(A, B, Q, R);
1070 EXPECT_EQ(Q, APInt(65, 1));
1071 EXPECT_EQ(R, APInt(65, 0));
1072 APInt::udivrem(A, B, Q, R);
1073 EXPECT_EQ(Q, APInt(65, 1));
1074 EXPECT_EQ(R, APInt(65, 0));
1075
1076 // 0 / X
1077 APInt O(65, 0);
1078 APInt::sdivrem(O, B, Q, R);
1079 EXPECT_EQ(Q, APInt(65, 0));
1080 EXPECT_EQ(R, APInt(65, 0));
1081 APInt::udivrem(O, B, Q, R);
1082 EXPECT_EQ(Q, APInt(65, 0));
1083 EXPECT_EQ(R, APInt(65, 0));
1084
1085 // X / 1
1086 APInt I(65, 1);
1087 APInt::sdivrem(A, I, Q, R);
1088 EXPECT_EQ(Q, A);
1089 EXPECT_EQ(R, APInt(65, 0));
1090 APInt::udivrem(A, I, Q, R);
1091 EXPECT_EQ(Q, A);
1092 EXPECT_EQ(R, APInt(65, 0));
1093 }
1094
1063 TEST(APIntTest, fromString) { 1095 TEST(APIntTest, fromString) {
1064 EXPECT_EQ(APInt(32, 0), APInt(32, "0", 2)); 1096 EXPECT_EQ(APInt(32, 0), APInt(32, "0", 2));
1065 EXPECT_EQ(APInt(32, 1), APInt(32, "1", 2)); 1097 EXPECT_EQ(APInt(32, 1), APInt(32, "1", 2));
1066 EXPECT_EQ(APInt(32, 2), APInt(32, "10", 2)); 1098 EXPECT_EQ(APInt(32, 2), APInt(32, "10", 2));
1067 EXPECT_EQ(APInt(32, 3), APInt(32, "11", 2)); 1099 EXPECT_EQ(APInt(32, 3), APInt(32, "11", 2));
1139 EXPECT_EQ(APInt(32, uint64_t(-1LL)), APInt(32, "-1", 36)); 1171 EXPECT_EQ(APInt(32, uint64_t(-1LL)), APInt(32, "-1", 36));
1140 EXPECT_EQ(APInt(32, uint64_t(-35LL)), APInt(32, "-Z", 36)); 1172 EXPECT_EQ(APInt(32, uint64_t(-35LL)), APInt(32, "-Z", 36));
1141 EXPECT_EQ(APInt(32, uint64_t(-36LL)), APInt(32, "-10", 36)); 1173 EXPECT_EQ(APInt(32, uint64_t(-36LL)), APInt(32, "-10", 36));
1142 EXPECT_EQ(APInt(32, uint64_t(-71LL)), APInt(32, "-1Z", 36)); 1174 EXPECT_EQ(APInt(32, uint64_t(-71LL)), APInt(32, "-1Z", 36));
1143 EXPECT_EQ(APInt(32, uint64_t(-72LL)), APInt(32, "-20", 36)); 1175 EXPECT_EQ(APInt(32, uint64_t(-72LL)), APInt(32, "-20", 36));
1176 }
1177
1178 TEST(APIntTest, SaturatingMath) {
1179 APInt AP_10 = APInt(8, 10);
1180 APInt AP_100 = APInt(8, 100);
1181 APInt AP_200 = APInt(8, 200);
1182
1183 EXPECT_EQ(APInt(8, 200), AP_100.uadd_sat(AP_100));
1184 EXPECT_EQ(APInt(8, 255), AP_100.uadd_sat(AP_200));
1185 EXPECT_EQ(APInt(8, 255), APInt(8, 255).uadd_sat(APInt(8, 255)));
1186
1187 EXPECT_EQ(APInt(8, 110), AP_10.sadd_sat(AP_100));
1188 EXPECT_EQ(APInt(8, 127), AP_100.sadd_sat(AP_100));
1189 EXPECT_EQ(APInt(8, -128), (-AP_100).sadd_sat(-AP_100));
1190 EXPECT_EQ(APInt(8, -128), APInt(8, -128).sadd_sat(APInt(8, -128)));
1191
1192 EXPECT_EQ(APInt(8, 90), AP_100.usub_sat(AP_10));
1193 EXPECT_EQ(APInt(8, 0), AP_100.usub_sat(AP_200));
1194 EXPECT_EQ(APInt(8, 0), APInt(8, 0).usub_sat(APInt(8, 255)));
1195
1196 EXPECT_EQ(APInt(8, -90), AP_10.ssub_sat(AP_100));
1197 EXPECT_EQ(APInt(8, 127), AP_100.ssub_sat(-AP_100));
1198 EXPECT_EQ(APInt(8, -128), (-AP_100).ssub_sat(AP_100));
1199 EXPECT_EQ(APInt(8, -128), APInt(8, -128).ssub_sat(APInt(8, 127)));
1144 } 1200 }
1145 1201
1146 TEST(APIntTest, FromArray) { 1202 TEST(APIntTest, FromArray) {
1147 EXPECT_EQ(APInt(32, uint64_t(1)), APInt(32, ArrayRef<uint64_t>(1))); 1203 EXPECT_EQ(APInt(32, uint64_t(1)), APInt(32, ArrayRef<uint64_t>(1)));
1148 } 1204 }
1204 EXPECT_EQ(2U, APInt::getBitsNeeded( "-0", 10)); 1260 EXPECT_EQ(2U, APInt::getBitsNeeded( "-0", 10));
1205 EXPECT_EQ(5U, APInt::getBitsNeeded( "-9", 10)); 1261 EXPECT_EQ(5U, APInt::getBitsNeeded( "-9", 10));
1206 EXPECT_EQ(5U, APInt::getBitsNeeded("-10", 10)); 1262 EXPECT_EQ(5U, APInt::getBitsNeeded("-10", 10));
1207 EXPECT_EQ(6U, APInt::getBitsNeeded("-19", 10)); 1263 EXPECT_EQ(6U, APInt::getBitsNeeded("-19", 10));
1208 EXPECT_EQ(6U, APInt::getBitsNeeded("-20", 10)); 1264 EXPECT_EQ(6U, APInt::getBitsNeeded("-20", 10));
1265
1266 EXPECT_EQ(1U, APInt::getBitsNeeded("-1", 10));
1267 EXPECT_EQ(2U, APInt::getBitsNeeded("-2", 10));
1268 EXPECT_EQ(3U, APInt::getBitsNeeded("-4", 10));
1269 EXPECT_EQ(4U, APInt::getBitsNeeded("-8", 10));
1270 EXPECT_EQ(5U, APInt::getBitsNeeded("-16", 10));
1271 EXPECT_EQ(6U, APInt::getBitsNeeded("-23", 10));
1272 EXPECT_EQ(6U, APInt::getBitsNeeded("-32", 10));
1273 EXPECT_EQ(7U, APInt::getBitsNeeded("-64", 10));
1274 EXPECT_EQ(8U, APInt::getBitsNeeded("-127", 10));
1275 EXPECT_EQ(8U, APInt::getBitsNeeded("-128", 10));
1276 EXPECT_EQ(9U, APInt::getBitsNeeded("-255", 10));
1277 EXPECT_EQ(9U, APInt::getBitsNeeded("-256", 10));
1278 EXPECT_EQ(10U, APInt::getBitsNeeded("-512", 10));
1279 EXPECT_EQ(11U, APInt::getBitsNeeded("-1024", 10));
1280 EXPECT_EQ(12U, APInt::getBitsNeeded("-1025", 10));
1209 } 1281 }
1210 1282
1211 TEST(APIntTest, StringBitsNeeded16) { 1283 TEST(APIntTest, StringBitsNeeded16) {
1212 EXPECT_EQ(4U, APInt::getBitsNeeded( "0", 16)); 1284 EXPECT_EQ(4U, APInt::getBitsNeeded( "0", 16));
1213 EXPECT_EQ(4U, APInt::getBitsNeeded( "F", 16)); 1285 EXPECT_EQ(4U, APInt::getBitsNeeded( "F", 16));
1316 } 1388 }
1317 1389
1318 #ifdef GTEST_HAS_DEATH_TEST 1390 #ifdef GTEST_HAS_DEATH_TEST
1319 #ifndef NDEBUG 1391 #ifndef NDEBUG
1320 TEST(APIntTest, StringDeath) { 1392 TEST(APIntTest, StringDeath) {
1321 EXPECT_DEATH(APInt(0, "", 0), "Bitwidth too small"); 1393 EXPECT_DEATH((void)APInt(0, "", 0), "Bitwidth too small");
1322 EXPECT_DEATH(APInt(32, "", 0), "Invalid string length"); 1394 EXPECT_DEATH((void)APInt(32, "", 0), "Invalid string length");
1323 EXPECT_DEATH(APInt(32, "0", 0), "Radix should be 2, 8, 10, 16, or 36!"); 1395 EXPECT_DEATH((void)APInt(32, "0", 0), "Radix should be 2, 8, 10, 16, or 36!");
1324 EXPECT_DEATH(APInt(32, "", 10), "Invalid string length"); 1396 EXPECT_DEATH((void)APInt(32, "", 10), "Invalid string length");
1325 EXPECT_DEATH(APInt(32, "-", 10), "String is only a sign, needs a value."); 1397 EXPECT_DEATH((void)APInt(32, "-", 10), "String is only a sign, needs a value.");
1326 EXPECT_DEATH(APInt(1, "1234", 10), "Insufficient bit width"); 1398 EXPECT_DEATH((void)APInt(1, "1234", 10), "Insufficient bit width");
1327 EXPECT_DEATH(APInt(32, "\0", 10), "Invalid string length"); 1399 EXPECT_DEATH((void)APInt(32, "\0", 10), "Invalid string length");
1328 EXPECT_DEATH(APInt(32, StringRef("1\02", 3), 10), "Invalid character in digit string"); 1400 EXPECT_DEATH((void)APInt(32, StringRef("1\02", 3), 10), "Invalid character in digit string");
1329 EXPECT_DEATH(APInt(32, "1L", 10), "Invalid character in digit string"); 1401 EXPECT_DEATH((void)APInt(32, "1L", 10), "Invalid character in digit string");
1330 } 1402 }
1331 #endif 1403 #endif
1332 #endif 1404 #endif
1333 1405
1334 TEST(APIntTest, mul_clear) { 1406 TEST(APIntTest, mul_clear) {
1657 EXPECT_TRUE(MaskVal.isShiftedMask()); 1729 EXPECT_TRUE(MaskVal.isShiftedMask());
1658 } 1730 }
1659 } 1731 }
1660 } 1732 }
1661 1733
1734 // Test that self-move works, but only when we're using MSVC.
1735 #if defined(_MSC_VER)
1736 #if defined(__clang__)
1737 // Disable the pragma warning from versions of Clang without -Wself-move
1738 #pragma clang diagnostic push
1739 #pragma clang diagnostic ignored "-Wunknown-pragmas"
1740 // Disable the warning that triggers on exactly what is being tested.
1741 #pragma clang diagnostic push
1742 #pragma clang diagnostic ignored "-Wself-move"
1743 #endif
1744 TEST(APIntTest, SelfMoveAssignment) {
1745 APInt X(32, 0xdeadbeef);
1746 X = std::move(X);
1747 EXPECT_EQ(32u, X.getBitWidth());
1748 EXPECT_EQ(0xdeadbeefULL, X.getLimitedValue());
1749
1750 uint64_t Bits[] = {0xdeadbeefdeadbeefULL, 0xdeadbeefdeadbeefULL};
1751 APInt Y(128, Bits);
1752 Y = std::move(Y);
1753 EXPECT_EQ(128u, Y.getBitWidth());
1754 EXPECT_EQ(~0ULL, Y.getLimitedValue());
1755 const uint64_t *Raw = Y.getRawData();
1756 EXPECT_EQ(2u, Y.getNumWords());
1757 EXPECT_EQ(0xdeadbeefdeadbeefULL, Raw[0]);
1758 EXPECT_EQ(0xdeadbeefdeadbeefULL, Raw[1]);
1759 }
1760 #if defined(__clang__)
1761 #pragma clang diagnostic pop
1762 #pragma clang diagnostic pop
1763 #endif
1764 #endif // _MSC_VER
1765
1662 TEST(APIntTest, reverseBits) { 1766 TEST(APIntTest, reverseBits) {
1663 EXPECT_EQ(1, APInt(1, 1).reverseBits()); 1767 EXPECT_EQ(1, APInt(1, 1).reverseBits());
1664 EXPECT_EQ(0, APInt(1, 0).reverseBits()); 1768 EXPECT_EQ(0, APInt(1, 0).reverseBits());
1665 1769
1666 EXPECT_EQ(3, APInt(2, 3).reverseBits()); 1770 EXPECT_EQ(3, APInt(2, 3).reverseBits());
2011 APInt i128(128, 0xfa); 2115 APInt i128(128, 0xfa);
2012 i128.setHighBits(2); 2116 i128.setHighBits(2);
2013 EXPECT_EQ(0xc, i128.getHiBits(4)); 2117 EXPECT_EQ(0xc, i128.getHiBits(4));
2014 } 2118 }
2015 2119
2120 TEST(APIntTest, clearLowBits) {
2121 APInt i64hi32 = APInt::getAllOnesValue(64);
2122 i64hi32.clearLowBits(32);
2123 EXPECT_EQ(32u, i64hi32.countLeadingOnes());
2124 EXPECT_EQ(0u, i64hi32.countLeadingZeros());
2125 EXPECT_EQ(64u, i64hi32.getActiveBits());
2126 EXPECT_EQ(32u, i64hi32.countTrailingZeros());
2127 EXPECT_EQ(0u, i64hi32.countTrailingOnes());
2128 EXPECT_EQ(32u, i64hi32.countPopulation());
2129
2130 APInt i128hi64 = APInt::getAllOnesValue(128);
2131 i128hi64.clearLowBits(64);
2132 EXPECT_EQ(64u, i128hi64.countLeadingOnes());
2133 EXPECT_EQ(0u, i128hi64.countLeadingZeros());
2134 EXPECT_EQ(128u, i128hi64.getActiveBits());
2135 EXPECT_EQ(64u, i128hi64.countTrailingZeros());
2136 EXPECT_EQ(0u, i128hi64.countTrailingOnes());
2137 EXPECT_EQ(64u, i128hi64.countPopulation());
2138
2139 APInt i128hi24 = APInt::getAllOnesValue(128);
2140 i128hi24.clearLowBits(104);
2141 EXPECT_EQ(24u, i128hi24.countLeadingOnes());
2142 EXPECT_EQ(0u, i128hi24.countLeadingZeros());
2143 EXPECT_EQ(128u, i128hi24.getActiveBits());
2144 EXPECT_EQ(104u, i128hi24.countTrailingZeros());
2145 EXPECT_EQ(0u, i128hi24.countTrailingOnes());
2146 EXPECT_EQ(24u, i128hi24.countPopulation());
2147
2148 APInt i128hi104 = APInt::getAllOnesValue(128);
2149 i128hi104.clearLowBits(24);
2150 EXPECT_EQ(104u, i128hi104.countLeadingOnes());
2151 EXPECT_EQ(0u, i128hi104.countLeadingZeros());
2152 EXPECT_EQ(128u, i128hi104.getActiveBits());
2153 EXPECT_EQ(24u, i128hi104.countTrailingZeros());
2154 EXPECT_EQ(0u, i128hi104.countTrailingOnes());
2155 EXPECT_EQ(104u, i128hi104.countPopulation());
2156
2157 APInt i128hi0 = APInt::getAllOnesValue(128);
2158 i128hi0.clearLowBits(128);
2159 EXPECT_EQ(0u, i128hi0.countLeadingOnes());
2160 EXPECT_EQ(128u, i128hi0.countLeadingZeros());
2161 EXPECT_EQ(0u, i128hi0.getActiveBits());
2162 EXPECT_EQ(128u, i128hi0.countTrailingZeros());
2163 EXPECT_EQ(0u, i128hi0.countTrailingOnes());
2164 EXPECT_EQ(0u, i128hi0.countPopulation());
2165
2166 APInt i80hi1 = APInt::getAllOnesValue(80);
2167 i80hi1.clearLowBits(79);
2168 EXPECT_EQ(1u, i80hi1.countLeadingOnes());
2169 EXPECT_EQ(0u, i80hi1.countLeadingZeros());
2170 EXPECT_EQ(80u, i80hi1.getActiveBits());
2171 EXPECT_EQ(79u, i80hi1.countTrailingZeros());
2172 EXPECT_EQ(0u, i80hi1.countTrailingOnes());
2173 EXPECT_EQ(1u, i80hi1.countPopulation());
2174
2175 APInt i32hi16 = APInt::getAllOnesValue(32);
2176 i32hi16.clearLowBits(16);
2177 EXPECT_EQ(16u, i32hi16.countLeadingOnes());
2178 EXPECT_EQ(0u, i32hi16.countLeadingZeros());
2179 EXPECT_EQ(32u, i32hi16.getActiveBits());
2180 EXPECT_EQ(16u, i32hi16.countTrailingZeros());
2181 EXPECT_EQ(0u, i32hi16.countTrailingOnes());
2182 EXPECT_EQ(16u, i32hi16.countPopulation());
2183 }
2184
2016 TEST(APIntTest, GCD) { 2185 TEST(APIntTest, GCD) {
2017 using APIntOps::GreatestCommonDivisor; 2186 using APIntOps::GreatestCommonDivisor;
2018 2187
2019 for (unsigned Bits : {1, 2, 32, 63, 64, 65}) { 2188 for (unsigned Bits : {1, 2, 32, 63, 64, 65}) {
2020 // Test some corner cases near zero. 2189 // Test some corner cases near zero.
2224 EXPECT_EQ(32U, i96.countLeadingOnes()); 2393 EXPECT_EQ(32U, i96.countLeadingOnes());
2225 EXPECT_EQ(32U, i96.countPopulation()); 2394 EXPECT_EQ(32U, i96.countPopulation());
2226 EXPECT_EQ(64U, i96.countTrailingZeros()); 2395 EXPECT_EQ(64U, i96.countTrailingZeros());
2227 } 2396 }
2228 2397
2398 TEST(APIntTest, RoundingUDiv) {
2399 for (uint64_t Ai = 1; Ai <= 255; Ai++) {
2400 APInt A(8, Ai);
2401 APInt Zero(8, 0);
2402 EXPECT_EQ(0, APIntOps::RoundingUDiv(Zero, A, APInt::Rounding::UP));
2403 EXPECT_EQ(0, APIntOps::RoundingUDiv(Zero, A, APInt::Rounding::DOWN));
2404 EXPECT_EQ(0, APIntOps::RoundingUDiv(Zero, A, APInt::Rounding::TOWARD_ZERO));
2405
2406 for (uint64_t Bi = 1; Bi <= 255; Bi++) {
2407 APInt B(8, Bi);
2408 {
2409 APInt Quo = APIntOps::RoundingUDiv(A, B, APInt::Rounding::UP);
2410 auto Prod = Quo.zext(16) * B.zext(16);
2411 EXPECT_TRUE(Prod.uge(Ai));
2412 if (Prod.ugt(Ai)) {
2413 EXPECT_TRUE(((Quo - 1).zext(16) * B.zext(16)).ult(Ai));
2414 }
2415 }
2416 {
2417 APInt Quo = A.udiv(B);
2418 EXPECT_EQ(Quo, APIntOps::RoundingUDiv(A, B, APInt::Rounding::TOWARD_ZERO));
2419 EXPECT_EQ(Quo, APIntOps::RoundingUDiv(A, B, APInt::Rounding::DOWN));
2420 }
2421 }
2422 }
2423 }
2424
2425 TEST(APIntTest, RoundingSDiv) {
2426 for (int64_t Ai = -128; Ai <= 127; Ai++) {
2427 APInt A(8, Ai);
2428
2429 if (Ai != 0) {
2430 APInt Zero(8, 0);
2431 EXPECT_EQ(0, APIntOps::RoundingSDiv(Zero, A, APInt::Rounding::UP));
2432 EXPECT_EQ(0, APIntOps::RoundingSDiv(Zero, A, APInt::Rounding::DOWN));
2433 EXPECT_EQ(0, APIntOps::RoundingSDiv(Zero, A, APInt::Rounding::TOWARD_ZERO));
2434 }
2435
2436 for (uint64_t Bi = -128; Bi <= 127; Bi++) {
2437 if (Bi == 0)
2438 continue;
2439
2440 APInt B(8, Bi);
2441 {
2442 APInt Quo = APIntOps::RoundingSDiv(A, B, APInt::Rounding::UP);
2443 auto Prod = Quo.sext(16) * B.sext(16);
2444 EXPECT_TRUE(Prod.uge(A));
2445 if (Prod.ugt(A)) {
2446 EXPECT_TRUE(((Quo - 1).sext(16) * B.sext(16)).ult(A));
2447 }
2448 }
2449 {
2450 APInt Quo = APIntOps::RoundingSDiv(A, B, APInt::Rounding::DOWN);
2451 auto Prod = Quo.sext(16) * B.sext(16);
2452 EXPECT_TRUE(Prod.ule(A));
2453 if (Prod.ult(A)) {
2454 EXPECT_TRUE(((Quo + 1).sext(16) * B.sext(16)).ugt(A));
2455 }
2456 }
2457 {
2458 APInt Quo = A.sdiv(B);
2459 EXPECT_EQ(Quo, APIntOps::RoundingSDiv(A, B, APInt::Rounding::TOWARD_ZERO));
2460 }
2461 }
2462 }
2463 }
2464
2465 TEST(APIntTest, umul_ov) {
2466 const std::pair<uint64_t, uint64_t> Overflows[] = {
2467 {0x8000000000000000, 2},
2468 {0x5555555555555556, 3},
2469 {4294967296, 4294967296},
2470 {4294967295, 4294967298},
2471 };
2472 const std::pair<uint64_t, uint64_t> NonOverflows[] = {
2473 {0x7fffffffffffffff, 2},
2474 {0x5555555555555555, 3},
2475 {4294967295, 4294967297},
2476 };
2477
2478 bool Overflow;
2479 for (auto &X : Overflows) {
2480 APInt A(64, X.first);
2481 APInt B(64, X.second);
2482 (void)A.umul_ov(B, Overflow);
2483 EXPECT_TRUE(Overflow);
2484 }
2485 for (auto &X : NonOverflows) {
2486 APInt A(64, X.first);
2487 APInt B(64, X.second);
2488 (void)A.umul_ov(B, Overflow);
2489 EXPECT_FALSE(Overflow);
2490 }
2491
2492 for (unsigned Bits = 1; Bits <= 5; ++Bits)
2493 for (unsigned A = 0; A != 1u << Bits; ++A)
2494 for (unsigned B = 0; B != 1u << Bits; ++B) {
2495 APInt C = APInt(Bits, A).umul_ov(APInt(Bits, B), Overflow);
2496 APInt D = APInt(2 * Bits, A) * APInt(2 * Bits, B);
2497 EXPECT_TRUE(D.getHiBits(Bits).isNullValue() != Overflow);
2498 }
2499 }
2500
2501 TEST(APIntTest, SolveQuadraticEquationWrap) {
2502 // Verify that "Solution" is the first non-negative integer that solves
2503 // Ax^2 + Bx + C = "0 or overflow", i.e. that it is a correct solution
2504 // as calculated by SolveQuadraticEquationWrap.
2505 auto Validate = [] (int A, int B, int C, unsigned Width, int Solution) {
2506 int Mask = (1 << Width) - 1;
2507
2508 // Solution should be non-negative.
2509 EXPECT_GE(Solution, 0);
2510
2511 auto OverflowBits = [] (int64_t V, unsigned W) {
2512 return V & -(1 << W);
2513 };
2514
2515 int64_t Over0 = OverflowBits(C, Width);
2516
2517 auto IsZeroOrOverflow = [&] (int X) {
2518 int64_t ValueAtX = A*X*X + B*X + C;
2519 int64_t OverX = OverflowBits(ValueAtX, Width);
2520 return (ValueAtX & Mask) == 0 || OverX != Over0;
2521 };
2522
2523 auto EquationToString = [&] (const char *X_str) {
2524 return (Twine(A) + Twine(X_str) + Twine("^2 + ") + Twine(B) +
2525 Twine(X_str) + Twine(" + ") + Twine(C) + Twine(", bitwidth: ") +
2526 Twine(Width)).str();
2527 };
2528
2529 auto IsSolution = [&] (const char *X_str, int X) {
2530 if (IsZeroOrOverflow(X))
2531 return ::testing::AssertionSuccess()
2532 << X << " is a solution of " << EquationToString(X_str);
2533 return ::testing::AssertionFailure()
2534 << X << " is not an expected solution of "
2535 << EquationToString(X_str);
2536 };
2537
2538 auto IsNotSolution = [&] (const char *X_str, int X) {
2539 if (!IsZeroOrOverflow(X))
2540 return ::testing::AssertionSuccess()
2541 << X << " is not a solution of " << EquationToString(X_str);
2542 return ::testing::AssertionFailure()
2543 << X << " is an unexpected solution of "
2544 << EquationToString(X_str);
2545 };
2546
2547 // This is the important part: make sure that there is no solution that
2548 // is less than the calculated one.
2549 if (Solution > 0) {
2550 for (int X = 1; X < Solution-1; ++X)
2551 EXPECT_PRED_FORMAT1(IsNotSolution, X);
2552 }
2553
2554 // Verify that the calculated solution is indeed a solution.
2555 EXPECT_PRED_FORMAT1(IsSolution, Solution);
2556 };
2557
2558 // Generate all possible quadratic equations with Width-bit wide integer
2559 // coefficients, get the solution from SolveQuadraticEquationWrap, and
2560 // verify that the solution is correct.
2561 auto Iterate = [&] (unsigned Width) {
2562 assert(1 < Width && Width < 32);
2563 int Low = -(1 << (Width-1));
2564 int High = (1 << (Width-1));
2565
2566 for (int A = Low; A != High; ++A) {
2567 if (A == 0)
2568 continue;
2569 for (int B = Low; B != High; ++B) {
2570 for (int C = Low; C != High; ++C) {
2571 Optional<APInt> S = APIntOps::SolveQuadraticEquationWrap(
2572 APInt(Width, A), APInt(Width, B),
2573 APInt(Width, C), Width);
2574 if (S.hasValue())
2575 Validate(A, B, C, Width, S->getSExtValue());
2576 }
2577 }
2578 }
2579 };
2580
2581 // Test all widths in [2..6].
2582 for (unsigned i = 2; i <= 6; ++i)
2583 Iterate(i);
2584 }
2585
2586 TEST(APIntTest, MultiplicativeInverseExaustive) {
2587 for (unsigned BitWidth = 1; BitWidth <= 16; ++BitWidth) {
2588 for (unsigned Value = 0; Value < (1u << BitWidth); ++Value) {
2589 APInt V = APInt(BitWidth, Value);
2590 APInt MulInv =
2591 V.zext(BitWidth + 1)
2592 .multiplicativeInverse(APInt::getSignedMinValue(BitWidth + 1))
2593 .trunc(BitWidth);
2594 APInt One = V * MulInv;
2595 if (!V.isNullValue() && V.countTrailingZeros() == 0) {
2596 // Multiplicative inverse exists for all odd numbers.
2597 EXPECT_TRUE(One.isOneValue());
2598 } else {
2599 // Multiplicative inverse does not exist for even numbers (and 0).
2600 EXPECT_TRUE(MulInv.isNullValue());
2601 }
2602 }
2603 }
2604 }
2605
2229 } // end anonymous namespace 2606 } // end anonymous namespace