xref: /llvm-project/llvm/unittests/ADT/APIntTest.cpp (revision c00c901f1cb714ebd053de5c6af564dc81754d3e)
1 //===- llvm/unittest/ADT/APInt.cpp - APInt unit tests ---------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 
9 #include "llvm/ADT/APInt.h"
10 #include "llvm/ADT/ArrayRef.h"
11 #include "llvm/ADT/DenseMap.h"
12 #include "llvm/ADT/SmallString.h"
13 #include "llvm/ADT/Twine.h"
14 #include "llvm/Support/Alignment.h"
15 #include "gtest/gtest.h"
16 #include <array>
17 #include <optional>
18 
19 using namespace llvm;
20 
21 namespace {
22 
23 TEST(APIntTest, ValueInit) {
24   APInt Zero = APInt();
25   EXPECT_TRUE(!Zero);
26   EXPECT_TRUE(!Zero.zext(64));
27   EXPECT_TRUE(!Zero.sext(64));
28 }
29 
30 // Test that APInt shift left works when bitwidth > 64 and shiftamt == 0
31 TEST(APIntTest, ShiftLeftByZero) {
32   APInt One = APInt::getZero(65) + 1;
33   APInt Shl = One.shl(0);
34   EXPECT_TRUE(Shl[0]);
35   EXPECT_FALSE(Shl[1]);
36 }
37 
38 TEST(APIntTest, i64_ArithmeticRightShiftNegative) {
39   const APInt neg_one(64, static_cast<uint64_t>(-1), true);
40   EXPECT_EQ(neg_one, neg_one.ashr(7));
41 }
42 
43 TEST(APIntTest, i128_NegativeCount) {
44   APInt Minus3(128, static_cast<uint64_t>(-3), true);
45   EXPECT_EQ(126u, Minus3.countl_one());
46   EXPECT_EQ(-3, Minus3.getSExtValue());
47 
48   APInt Minus1(128, static_cast<uint64_t>(-1), true);
49   EXPECT_EQ(0u, Minus1.countl_zero());
50   EXPECT_EQ(128u, Minus1.countl_one());
51   EXPECT_EQ(128u, Minus1.getActiveBits());
52   EXPECT_EQ(0u, Minus1.countr_zero());
53   EXPECT_EQ(128u, Minus1.countr_one());
54   EXPECT_EQ(128u, Minus1.popcount());
55   EXPECT_EQ(-1, Minus1.getSExtValue());
56 }
57 
58 TEST(APIntTest, i33_Count) {
59   APInt i33minus2(33, static_cast<uint64_t>(-2), true);
60   EXPECT_EQ(0u, i33minus2.countl_zero());
61   EXPECT_EQ(32u, i33minus2.countl_one());
62   EXPECT_EQ(33u, i33minus2.getActiveBits());
63   EXPECT_EQ(1u, i33minus2.countr_zero());
64   EXPECT_EQ(32u, i33minus2.popcount());
65   EXPECT_EQ(-2, i33minus2.getSExtValue());
66   EXPECT_EQ(((uint64_t)-2)&((1ull<<33) -1), i33minus2.getZExtValue());
67 }
68 
69 TEST(APIntTest, i61_Count) {
70   APInt i61(61, 1 << 15);
71   EXPECT_EQ(45u, i61.countl_zero());
72   EXPECT_EQ(0u, i61.countl_one());
73   EXPECT_EQ(16u, i61.getActiveBits());
74   EXPECT_EQ(15u, i61.countr_zero());
75   EXPECT_EQ(1u, i61.popcount());
76   EXPECT_EQ(static_cast<int64_t>(1 << 15), i61.getSExtValue());
77   EXPECT_EQ(static_cast<uint64_t>(1 << 15), i61.getZExtValue());
78 
79   i61.setBits(8, 19);
80   EXPECT_EQ(42u, i61.countl_zero());
81   EXPECT_EQ(0u, i61.countl_one());
82   EXPECT_EQ(19u, i61.getActiveBits());
83   EXPECT_EQ(8u, i61.countr_zero());
84   EXPECT_EQ(11u, i61.popcount());
85   EXPECT_EQ(static_cast<int64_t>((1 << 19) - (1 << 8)), i61.getSExtValue());
86   EXPECT_EQ(static_cast<uint64_t>((1 << 19) - (1 << 8)), i61.getZExtValue());
87 }
88 
89 TEST(APIntTest, i65_Count) {
90   APInt i65(65, 0, true);
91   EXPECT_EQ(65u, i65.countl_zero());
92   EXPECT_EQ(0u, i65.countl_one());
93   EXPECT_EQ(0u, i65.getActiveBits());
94   EXPECT_EQ(1u, i65.getActiveWords());
95   EXPECT_EQ(65u, i65.countr_zero());
96   EXPECT_EQ(0u, i65.popcount());
97 
98   APInt i65minus(65, 0, true);
99   i65minus.setBit(64);
100   EXPECT_EQ(0u, i65minus.countl_zero());
101   EXPECT_EQ(1u, i65minus.countl_one());
102   EXPECT_EQ(65u, i65minus.getActiveBits());
103   EXPECT_EQ(64u, i65minus.countr_zero());
104   EXPECT_EQ(1u, i65minus.popcount());
105 }
106 
107 TEST(APIntTest, i128_PositiveCount) {
108   APInt u128max = APInt::getAllOnes(128);
109   EXPECT_EQ(128u, u128max.countl_one());
110   EXPECT_EQ(0u, u128max.countl_zero());
111   EXPECT_EQ(128u, u128max.getActiveBits());
112   EXPECT_EQ(0u, u128max.countr_zero());
113   EXPECT_EQ(128u, u128max.countr_one());
114   EXPECT_EQ(128u, u128max.popcount());
115 
116   APInt u64max(128, static_cast<uint64_t>(-1), false);
117   EXPECT_EQ(64u, u64max.countl_zero());
118   EXPECT_EQ(0u, u64max.countl_one());
119   EXPECT_EQ(64u, u64max.getActiveBits());
120   EXPECT_EQ(0u, u64max.countr_zero());
121   EXPECT_EQ(64u, u64max.countr_one());
122   EXPECT_EQ(64u, u64max.popcount());
123   EXPECT_EQ((uint64_t)~0ull, u64max.getZExtValue());
124 
125   APInt zero(128, 0, true);
126   EXPECT_EQ(128u, zero.countl_zero());
127   EXPECT_EQ(0u, zero.countl_one());
128   EXPECT_EQ(0u, zero.getActiveBits());
129   EXPECT_EQ(128u, zero.countr_zero());
130   EXPECT_EQ(0u, zero.countr_one());
131   EXPECT_EQ(0u, zero.popcount());
132   EXPECT_EQ(0u, zero.getSExtValue());
133   EXPECT_EQ(0u, zero.getZExtValue());
134 
135   APInt one(128, 1, true);
136   EXPECT_EQ(127u, one.countl_zero());
137   EXPECT_EQ(0u, one.countl_one());
138   EXPECT_EQ(1u, one.getActiveBits());
139   EXPECT_EQ(0u, one.countr_zero());
140   EXPECT_EQ(1u, one.countr_one());
141   EXPECT_EQ(1u, one.popcount());
142   EXPECT_EQ(1, one.getSExtValue());
143   EXPECT_EQ(1u, one.getZExtValue());
144 
145   APInt s128(128, 2, true);
146   EXPECT_EQ(126u, s128.countl_zero());
147   EXPECT_EQ(0u, s128.countl_one());
148   EXPECT_EQ(2u, s128.getActiveBits());
149   EXPECT_EQ(1u, s128.countr_zero());
150   EXPECT_EQ(0u, s128.countr_one());
151   EXPECT_EQ(1u, s128.popcount());
152   EXPECT_EQ(2, s128.getSExtValue());
153   EXPECT_EQ(2u, s128.getZExtValue());
154 
155   // NOP Test
156   s128.setBits(42, 42);
157   EXPECT_EQ(126u, s128.countl_zero());
158   EXPECT_EQ(0u, s128.countl_one());
159   EXPECT_EQ(2u, s128.getActiveBits());
160   EXPECT_EQ(1u, s128.countr_zero());
161   EXPECT_EQ(0u, s128.countr_one());
162   EXPECT_EQ(1u, s128.popcount());
163   EXPECT_EQ(2, s128.getSExtValue());
164   EXPECT_EQ(2u, s128.getZExtValue());
165 
166   s128.setBits(3, 32);
167   EXPECT_EQ(96u, s128.countl_zero());
168   EXPECT_EQ(0u, s128.countl_one());
169   EXPECT_EQ(32u, s128.getActiveBits());
170   EXPECT_EQ(33u, s128.getSignificantBits());
171   EXPECT_EQ(1u, s128.countr_zero());
172   EXPECT_EQ(0u, s128.countr_one());
173   EXPECT_EQ(30u, s128.popcount());
174   EXPECT_EQ(static_cast<uint32_t>((~0u << 3) | 2), s128.getZExtValue());
175 
176   s128.setBits(62, 128);
177   EXPECT_EQ(0u, s128.countl_zero());
178   EXPECT_EQ(66u, s128.countl_one());
179   EXPECT_EQ(128u, s128.getActiveBits());
180   EXPECT_EQ(63u, s128.getSignificantBits());
181   EXPECT_EQ(1u, s128.countr_zero());
182   EXPECT_EQ(0u, s128.countr_one());
183   EXPECT_EQ(96u, s128.popcount());
184   EXPECT_EQ(static_cast<int64_t>((3ull << 62) |
185                                  static_cast<uint32_t>((~0u << 3) | 2)),
186             s128.getSExtValue());
187 }
188 
189 TEST(APIntTest, i256) {
190   APInt s256(256, 15, true);
191   EXPECT_EQ(252u, s256.countl_zero());
192   EXPECT_EQ(0u, s256.countl_one());
193   EXPECT_EQ(4u, s256.getActiveBits());
194   EXPECT_EQ(0u, s256.countr_zero());
195   EXPECT_EQ(4u, s256.countr_one());
196   EXPECT_EQ(4u, s256.popcount());
197   EXPECT_EQ(15, s256.getSExtValue());
198   EXPECT_EQ(15u, s256.getZExtValue());
199 
200   s256.setBits(62, 66);
201   EXPECT_EQ(190u, s256.countl_zero());
202   EXPECT_EQ(0u, s256.countl_one());
203   EXPECT_EQ(66u, s256.getActiveBits());
204   EXPECT_EQ(67u, s256.getSignificantBits());
205   EXPECT_EQ(0u, s256.countr_zero());
206   EXPECT_EQ(4u, s256.countr_one());
207   EXPECT_EQ(8u, s256.popcount());
208 
209   s256.setBits(60, 256);
210   EXPECT_EQ(0u, s256.countl_zero());
211   EXPECT_EQ(196u, s256.countl_one());
212   EXPECT_EQ(256u, s256.getActiveBits());
213   EXPECT_EQ(61u, s256.getSignificantBits());
214   EXPECT_EQ(0u, s256.countr_zero());
215   EXPECT_EQ(4u, s256.countr_one());
216   EXPECT_EQ(200u, s256.popcount());
217   EXPECT_EQ(static_cast<int64_t>((~0ull << 60) | 15), s256.getSExtValue());
218 }
219 
220 TEST(APIntTest, i1) {
221   const APInt neg_two(1, static_cast<uint64_t>(-2), true);
222   const APInt neg_one(1, static_cast<uint64_t>(-1), true);
223   const APInt zero(1, 0);
224   const APInt one(1, 1);
225   const APInt two(1, 2);
226 
227   EXPECT_EQ(0, neg_two.getSExtValue());
228   EXPECT_EQ(-1, neg_one.getSExtValue());
229   EXPECT_EQ(1u, neg_one.getZExtValue());
230   EXPECT_EQ(0u, zero.getZExtValue());
231   EXPECT_EQ(-1, one.getSExtValue());
232   EXPECT_EQ(1u, one.getZExtValue());
233   EXPECT_EQ(0u, two.getZExtValue());
234   EXPECT_EQ(0, two.getSExtValue());
235 
236   // Basic equalities for 1-bit values.
237   EXPECT_EQ(zero, two);
238   EXPECT_EQ(zero, neg_two);
239   EXPECT_EQ(one, neg_one);
240   EXPECT_EQ(two, neg_two);
241 
242   // Min/max signed values.
243   EXPECT_TRUE(zero.isMaxSignedValue());
244   EXPECT_FALSE(one.isMaxSignedValue());
245   EXPECT_FALSE(zero.isMinSignedValue());
246   EXPECT_TRUE(one.isMinSignedValue());
247 
248   // Additions.
249   EXPECT_EQ(two, one + one);
250   EXPECT_EQ(zero, neg_one + one);
251   EXPECT_EQ(neg_two, neg_one + neg_one);
252 
253   // Subtractions.
254   EXPECT_EQ(neg_two, neg_one - one);
255   EXPECT_EQ(two, one - neg_one);
256   EXPECT_EQ(zero, one - one);
257 
258   // And
259   EXPECT_EQ(zero, zero & zero);
260   EXPECT_EQ(zero, one & zero);
261   EXPECT_EQ(zero, zero & one);
262   EXPECT_EQ(one, one & one);
263   EXPECT_EQ(zero, zero & zero);
264   EXPECT_EQ(zero, neg_one & zero);
265   EXPECT_EQ(zero, zero & neg_one);
266   EXPECT_EQ(neg_one, neg_one & neg_one);
267 
268   // Or
269   EXPECT_EQ(zero, zero | zero);
270   EXPECT_EQ(one, one | zero);
271   EXPECT_EQ(one, zero | one);
272   EXPECT_EQ(one, one | one);
273   EXPECT_EQ(zero, zero | zero);
274   EXPECT_EQ(neg_one, neg_one | zero);
275   EXPECT_EQ(neg_one, zero | neg_one);
276   EXPECT_EQ(neg_one, neg_one | neg_one);
277 
278   // Xor
279   EXPECT_EQ(zero, zero ^ zero);
280   EXPECT_EQ(one, one ^ zero);
281   EXPECT_EQ(one, zero ^ one);
282   EXPECT_EQ(zero, one ^ one);
283   EXPECT_EQ(zero, zero ^ zero);
284   EXPECT_EQ(neg_one, neg_one ^ zero);
285   EXPECT_EQ(neg_one, zero ^ neg_one);
286   EXPECT_EQ(zero, neg_one ^ neg_one);
287 
288   // Shifts.
289   EXPECT_EQ(zero, one << one);
290   EXPECT_EQ(one, one << zero);
291   EXPECT_EQ(zero, one.shl(1));
292   EXPECT_EQ(one, one.shl(0));
293   EXPECT_EQ(zero, one.lshr(1));
294   EXPECT_EQ(one, one.ashr(1));
295 
296   // Rotates.
297   EXPECT_EQ(one, one.rotl(0));
298   EXPECT_EQ(one, one.rotl(1));
299   EXPECT_EQ(one, one.rotr(0));
300   EXPECT_EQ(one, one.rotr(1));
301 
302   // Multiplies.
303   EXPECT_EQ(neg_one, neg_one * one);
304   EXPECT_EQ(neg_one, one * neg_one);
305   EXPECT_EQ(one, neg_one * neg_one);
306   EXPECT_EQ(one, one * one);
307 
308   // Divides.
309   EXPECT_EQ(neg_one, one.sdiv(neg_one));
310   EXPECT_EQ(neg_one, neg_one.sdiv(one));
311   EXPECT_EQ(one, neg_one.sdiv(neg_one));
312   EXPECT_EQ(one, one.sdiv(one));
313 
314   EXPECT_EQ(neg_one, one.udiv(neg_one));
315   EXPECT_EQ(neg_one, neg_one.udiv(one));
316   EXPECT_EQ(one, neg_one.udiv(neg_one));
317   EXPECT_EQ(one, one.udiv(one));
318 
319   // Remainders.
320   EXPECT_EQ(zero, neg_one.srem(one));
321   EXPECT_EQ(zero, neg_one.urem(one));
322   EXPECT_EQ(zero, one.srem(neg_one));
323 
324   // sdivrem
325   {
326   APInt q(8, 0);
327   APInt r(8, 0);
328   APInt one(8, 1);
329   APInt two(8, 2);
330   APInt nine(8, 9);
331   APInt four(8, 4);
332 
333   EXPECT_EQ(nine.srem(two), one);
334   EXPECT_EQ(nine.srem(-two), one);
335   EXPECT_EQ((-nine).srem(two), -one);
336   EXPECT_EQ((-nine).srem(-two), -one);
337 
338   APInt::sdivrem(nine, two, q, r);
339   EXPECT_EQ(four, q);
340   EXPECT_EQ(one, r);
341   APInt::sdivrem(-nine, two, q, r);
342   EXPECT_EQ(-four, q);
343   EXPECT_EQ(-one, r);
344   APInt::sdivrem(nine, -two, q, r);
345   EXPECT_EQ(-four, q);
346   EXPECT_EQ(one, r);
347   APInt::sdivrem(-nine, -two, q, r);
348   EXPECT_EQ(four, q);
349   EXPECT_EQ(-one, r);
350   }
351 }
352 
353 TEST(APIntTest, compare) {
354   std::array<APInt, 5> testVals{{
355     APInt{16, 2},
356     APInt{16, 1},
357     APInt{16, 0},
358     APInt{16, (uint64_t)-1, true},
359     APInt{16, (uint64_t)-2, true},
360   }};
361 
362   for (auto &arg1 : testVals)
363     for (auto &arg2 : testVals) {
364       auto uv1 = arg1.getZExtValue();
365       auto uv2 = arg2.getZExtValue();
366       auto sv1 = arg1.getSExtValue();
367       auto sv2 = arg2.getSExtValue();
368 
369       EXPECT_EQ(uv1 <  uv2, arg1.ult(arg2));
370       EXPECT_EQ(uv1 <= uv2, arg1.ule(arg2));
371       EXPECT_EQ(uv1 >  uv2, arg1.ugt(arg2));
372       EXPECT_EQ(uv1 >= uv2, arg1.uge(arg2));
373 
374       EXPECT_EQ(sv1 <  sv2, arg1.slt(arg2));
375       EXPECT_EQ(sv1 <= sv2, arg1.sle(arg2));
376       EXPECT_EQ(sv1 >  sv2, arg1.sgt(arg2));
377       EXPECT_EQ(sv1 >= sv2, arg1.sge(arg2));
378 
379       EXPECT_EQ(uv1 <  uv2, arg1.ult(uv2));
380       EXPECT_EQ(uv1 <= uv2, arg1.ule(uv2));
381       EXPECT_EQ(uv1 >  uv2, arg1.ugt(uv2));
382       EXPECT_EQ(uv1 >= uv2, arg1.uge(uv2));
383 
384       EXPECT_EQ(sv1 <  sv2, arg1.slt(sv2));
385       EXPECT_EQ(sv1 <= sv2, arg1.sle(sv2));
386       EXPECT_EQ(sv1 >  sv2, arg1.sgt(sv2));
387       EXPECT_EQ(sv1 >= sv2, arg1.sge(sv2));
388     }
389 }
390 
391 TEST(APIntTest, compareWithRawIntegers) {
392   EXPECT_TRUE(!APInt(8, 1).uge(256));
393   EXPECT_TRUE(!APInt(8, 1).ugt(256));
394   EXPECT_TRUE( APInt(8, 1).ule(256));
395   EXPECT_TRUE( APInt(8, 1).ult(256));
396   EXPECT_TRUE(!APInt(8, 1).sge(256));
397   EXPECT_TRUE(!APInt(8, 1).sgt(256));
398   EXPECT_TRUE( APInt(8, 1).sle(256));
399   EXPECT_TRUE( APInt(8, 1).slt(256));
400   EXPECT_TRUE(!(APInt(8, 0) == 256));
401   EXPECT_TRUE(  APInt(8, 0) != 256);
402   EXPECT_TRUE(!(APInt(8, 1) == 256));
403   EXPECT_TRUE(  APInt(8, 1) != 256);
404 
405   auto uint64max = UINT64_MAX;
406   auto int64max  = INT64_MAX;
407   auto int64min  = INT64_MIN;
408 
409   auto u64 = APInt{128, uint64max};
410   auto s64 = APInt{128, static_cast<uint64_t>(int64max), true};
411   auto big = u64 + 1;
412 
413   EXPECT_TRUE( u64.uge(uint64max));
414   EXPECT_TRUE(!u64.ugt(uint64max));
415   EXPECT_TRUE( u64.ule(uint64max));
416   EXPECT_TRUE(!u64.ult(uint64max));
417   EXPECT_TRUE( u64.sge(int64max));
418   EXPECT_TRUE( u64.sgt(int64max));
419   EXPECT_TRUE(!u64.sle(int64max));
420   EXPECT_TRUE(!u64.slt(int64max));
421   EXPECT_TRUE( u64.sge(int64min));
422   EXPECT_TRUE( u64.sgt(int64min));
423   EXPECT_TRUE(!u64.sle(int64min));
424   EXPECT_TRUE(!u64.slt(int64min));
425 
426   EXPECT_TRUE(u64 == uint64max);
427   EXPECT_TRUE(u64 != int64max);
428   EXPECT_TRUE(u64 != int64min);
429 
430   EXPECT_TRUE(!s64.uge(uint64max));
431   EXPECT_TRUE(!s64.ugt(uint64max));
432   EXPECT_TRUE( s64.ule(uint64max));
433   EXPECT_TRUE( s64.ult(uint64max));
434   EXPECT_TRUE( s64.sge(int64max));
435   EXPECT_TRUE(!s64.sgt(int64max));
436   EXPECT_TRUE( s64.sle(int64max));
437   EXPECT_TRUE(!s64.slt(int64max));
438   EXPECT_TRUE( s64.sge(int64min));
439   EXPECT_TRUE( s64.sgt(int64min));
440   EXPECT_TRUE(!s64.sle(int64min));
441   EXPECT_TRUE(!s64.slt(int64min));
442 
443   EXPECT_TRUE(s64 != uint64max);
444   EXPECT_TRUE(s64 == int64max);
445   EXPECT_TRUE(s64 != int64min);
446 
447   EXPECT_TRUE( big.uge(uint64max));
448   EXPECT_TRUE( big.ugt(uint64max));
449   EXPECT_TRUE(!big.ule(uint64max));
450   EXPECT_TRUE(!big.ult(uint64max));
451   EXPECT_TRUE( big.sge(int64max));
452   EXPECT_TRUE( big.sgt(int64max));
453   EXPECT_TRUE(!big.sle(int64max));
454   EXPECT_TRUE(!big.slt(int64max));
455   EXPECT_TRUE( big.sge(int64min));
456   EXPECT_TRUE( big.sgt(int64min));
457   EXPECT_TRUE(!big.sle(int64min));
458   EXPECT_TRUE(!big.slt(int64min));
459 
460   EXPECT_TRUE(big != uint64max);
461   EXPECT_TRUE(big != int64max);
462   EXPECT_TRUE(big != int64min);
463 }
464 
465 TEST(APIntTest, compareWithInt64Min) {
466   int64_t edge = INT64_MIN;
467   int64_t edgeP1 = edge + 1;
468   int64_t edgeM1 = INT64_MAX;
469   auto a = APInt{64, static_cast<uint64_t>(edge), true};
470 
471   EXPECT_TRUE(!a.slt(edge));
472   EXPECT_TRUE( a.sle(edge));
473   EXPECT_TRUE(!a.sgt(edge));
474   EXPECT_TRUE( a.sge(edge));
475   EXPECT_TRUE( a.slt(edgeP1));
476   EXPECT_TRUE( a.sle(edgeP1));
477   EXPECT_TRUE(!a.sgt(edgeP1));
478   EXPECT_TRUE(!a.sge(edgeP1));
479   EXPECT_TRUE( a.slt(edgeM1));
480   EXPECT_TRUE( a.sle(edgeM1));
481   EXPECT_TRUE(!a.sgt(edgeM1));
482   EXPECT_TRUE(!a.sge(edgeM1));
483 }
484 
485 TEST(APIntTest, compareWithHalfInt64Max) {
486   uint64_t edge = 0x4000000000000000;
487   uint64_t edgeP1 = edge + 1;
488   uint64_t edgeM1 = edge - 1;
489   auto a = APInt{64, edge};
490 
491   EXPECT_TRUE(!a.ult(edge));
492   EXPECT_TRUE( a.ule(edge));
493   EXPECT_TRUE(!a.ugt(edge));
494   EXPECT_TRUE( a.uge(edge));
495   EXPECT_TRUE( a.ult(edgeP1));
496   EXPECT_TRUE( a.ule(edgeP1));
497   EXPECT_TRUE(!a.ugt(edgeP1));
498   EXPECT_TRUE(!a.uge(edgeP1));
499   EXPECT_TRUE(!a.ult(edgeM1));
500   EXPECT_TRUE(!a.ule(edgeM1));
501   EXPECT_TRUE( a.ugt(edgeM1));
502   EXPECT_TRUE( a.uge(edgeM1));
503 
504   EXPECT_TRUE(!a.slt(edge));
505   EXPECT_TRUE( a.sle(edge));
506   EXPECT_TRUE(!a.sgt(edge));
507   EXPECT_TRUE( a.sge(edge));
508   EXPECT_TRUE( a.slt(edgeP1));
509   EXPECT_TRUE( a.sle(edgeP1));
510   EXPECT_TRUE(!a.sgt(edgeP1));
511   EXPECT_TRUE(!a.sge(edgeP1));
512   EXPECT_TRUE(!a.slt(edgeM1));
513   EXPECT_TRUE(!a.sle(edgeM1));
514   EXPECT_TRUE( a.sgt(edgeM1));
515   EXPECT_TRUE( a.sge(edgeM1));
516 }
517 
518 TEST(APIntTest, compareLargeIntegers) {
519   // Make sure all the combinations of signed comparisons work with big ints.
520   auto One = APInt{128, static_cast<uint64_t>(1), true};
521   auto Two = APInt{128, static_cast<uint64_t>(2), true};
522   auto MinusOne = APInt{128, static_cast<uint64_t>(-1), true};
523   auto MinusTwo = APInt{128, static_cast<uint64_t>(-2), true};
524 
525   EXPECT_TRUE(!One.slt(One));
526   EXPECT_TRUE(!Two.slt(One));
527   EXPECT_TRUE(MinusOne.slt(One));
528   EXPECT_TRUE(MinusTwo.slt(One));
529 
530   EXPECT_TRUE(One.slt(Two));
531   EXPECT_TRUE(!Two.slt(Two));
532   EXPECT_TRUE(MinusOne.slt(Two));
533   EXPECT_TRUE(MinusTwo.slt(Two));
534 
535   EXPECT_TRUE(!One.slt(MinusOne));
536   EXPECT_TRUE(!Two.slt(MinusOne));
537   EXPECT_TRUE(!MinusOne.slt(MinusOne));
538   EXPECT_TRUE(MinusTwo.slt(MinusOne));
539 
540   EXPECT_TRUE(!One.slt(MinusTwo));
541   EXPECT_TRUE(!Two.slt(MinusTwo));
542   EXPECT_TRUE(!MinusOne.slt(MinusTwo));
543   EXPECT_TRUE(!MinusTwo.slt(MinusTwo));
544 }
545 
546 TEST(APIntTest, binaryOpsWithRawIntegers) {
547   // Single word check.
548   uint64_t E1 = 0x2CA7F46BF6569915ULL;
549   APInt A1(64, E1);
550 
551   EXPECT_EQ(A1 & E1, E1);
552   EXPECT_EQ(A1 & 0, 0);
553   EXPECT_EQ(A1 & 1, 1);
554   EXPECT_EQ(A1 & 5, 5);
555   EXPECT_EQ(A1 & UINT64_MAX, E1);
556 
557   EXPECT_EQ(A1 | E1, E1);
558   EXPECT_EQ(A1 | 0, E1);
559   EXPECT_EQ(A1 | 1, E1);
560   EXPECT_EQ(A1 | 2, E1 | 2);
561   EXPECT_EQ(A1 | UINT64_MAX, UINT64_MAX);
562 
563   EXPECT_EQ(A1 ^ E1, 0);
564   EXPECT_EQ(A1 ^ 0, E1);
565   EXPECT_EQ(A1 ^ 1, E1 ^ 1);
566   EXPECT_EQ(A1 ^ 7, E1 ^ 7);
567   EXPECT_EQ(A1 ^ UINT64_MAX, ~E1);
568 
569   // Multiword check.
570   uint64_t N = 0xEB6EB136591CBA21ULL;
571   APInt::WordType E2[4] = {
572     N,
573     0x7B9358BD6A33F10AULL,
574     0x7E7FFA5EADD8846ULL,
575     0x305F341CA00B613DULL
576   };
577   APInt A2(APInt::APINT_BITS_PER_WORD*4, E2);
578 
579   EXPECT_EQ(A2 & N, N);
580   EXPECT_EQ(A2 & 0, 0);
581   EXPECT_EQ(A2 & 1, 1);
582   EXPECT_EQ(A2 & 5, 1);
583   EXPECT_EQ(A2 & UINT64_MAX, N);
584 
585   EXPECT_EQ(A2 | N, A2);
586   EXPECT_EQ(A2 | 0, A2);
587   EXPECT_EQ(A2 | 1, A2);
588   EXPECT_EQ(A2 | 2, A2 + 2);
589   EXPECT_EQ(A2 | UINT64_MAX, A2 - N + UINT64_MAX);
590 
591   EXPECT_EQ(A2 ^ N, A2 - N);
592   EXPECT_EQ(A2 ^ 0, A2);
593   EXPECT_EQ(A2 ^ 1, A2 - 1);
594   EXPECT_EQ(A2 ^ 7, A2 + 5);
595   EXPECT_EQ(A2 ^ UINT64_MAX, A2 - N + ~N);
596 }
597 
598 TEST(APIntTest, rvalue_arithmetic) {
599   // Test all combinations of lvalue/rvalue lhs/rhs of add/sub
600 
601   // Lamdba to return an APInt by value, but also provide the raw value of the
602   // allocated data.
603   auto getRValue = [](const char *HexString, uint64_t const *&RawData) {
604     APInt V(129, HexString, 16);
605     RawData = V.getRawData();
606     return V;
607   };
608 
609   APInt One(129, "1", 16);
610   APInt Two(129, "2", 16);
611   APInt Three(129, "3", 16);
612   APInt MinusOne = -One;
613 
614   const uint64_t *RawDataL = nullptr;
615   const uint64_t *RawDataR = nullptr;
616 
617   {
618     // 1 + 1 = 2
619     APInt AddLL = One + One;
620     EXPECT_EQ(AddLL, Two);
621 
622     APInt AddLR = One + getRValue("1", RawDataR);
623     EXPECT_EQ(AddLR, Two);
624     EXPECT_EQ(AddLR.getRawData(), RawDataR);
625 
626     APInt AddRL = getRValue("1", RawDataL) + One;
627     EXPECT_EQ(AddRL, Two);
628     EXPECT_EQ(AddRL.getRawData(), RawDataL);
629 
630     APInt AddRR = getRValue("1", RawDataL) + getRValue("1", RawDataR);
631     EXPECT_EQ(AddRR, Two);
632     EXPECT_EQ(AddRR.getRawData(), RawDataR);
633 
634     // LValue's and constants
635     APInt AddLK = One + 1;
636     EXPECT_EQ(AddLK, Two);
637 
638     APInt AddKL = 1 + One;
639     EXPECT_EQ(AddKL, Two);
640 
641     // RValue's and constants
642     APInt AddRK = getRValue("1", RawDataL) + 1;
643     EXPECT_EQ(AddRK, Two);
644     EXPECT_EQ(AddRK.getRawData(), RawDataL);
645 
646     APInt AddKR = 1 + getRValue("1", RawDataR);
647     EXPECT_EQ(AddKR, Two);
648     EXPECT_EQ(AddKR.getRawData(), RawDataR);
649   }
650 
651   {
652     // 0x0,FFFF...FFFF + 0x2 = 0x100...0001
653     APInt AllOnes(129, "0FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", 16);
654     APInt HighOneLowOne(129, "100000000000000000000000000000001", 16);
655 
656     APInt AddLL = AllOnes + Two;
657     EXPECT_EQ(AddLL, HighOneLowOne);
658 
659     APInt AddLR = AllOnes + getRValue("2", RawDataR);
660     EXPECT_EQ(AddLR, HighOneLowOne);
661     EXPECT_EQ(AddLR.getRawData(), RawDataR);
662 
663     APInt AddRL = getRValue("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", RawDataL) + Two;
664     EXPECT_EQ(AddRL, HighOneLowOne);
665     EXPECT_EQ(AddRL.getRawData(), RawDataL);
666 
667     APInt AddRR = getRValue("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", RawDataL) +
668                   getRValue("2", RawDataR);
669     EXPECT_EQ(AddRR, HighOneLowOne);
670     EXPECT_EQ(AddRR.getRawData(), RawDataR);
671 
672     // LValue's and constants
673     APInt AddLK = AllOnes + 2;
674     EXPECT_EQ(AddLK, HighOneLowOne);
675 
676     APInt AddKL = 2 + AllOnes;
677     EXPECT_EQ(AddKL, HighOneLowOne);
678 
679     // RValue's and constants
680     APInt AddRK = getRValue("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", RawDataL) + 2;
681     EXPECT_EQ(AddRK, HighOneLowOne);
682     EXPECT_EQ(AddRK.getRawData(), RawDataL);
683 
684     APInt AddKR = 2 + getRValue("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", RawDataR);
685     EXPECT_EQ(AddKR, HighOneLowOne);
686     EXPECT_EQ(AddKR.getRawData(), RawDataR);
687   }
688 
689   {
690     // 2 - 1 = 1
691     APInt SubLL = Two - One;
692     EXPECT_EQ(SubLL, One);
693 
694     APInt SubLR = Two - getRValue("1", RawDataR);
695     EXPECT_EQ(SubLR, One);
696     EXPECT_EQ(SubLR.getRawData(), RawDataR);
697 
698     APInt SubRL = getRValue("2", RawDataL) - One;
699     EXPECT_EQ(SubRL, One);
700     EXPECT_EQ(SubRL.getRawData(), RawDataL);
701 
702     APInt SubRR = getRValue("2", RawDataL) - getRValue("1", RawDataR);
703     EXPECT_EQ(SubRR, One);
704     EXPECT_EQ(SubRR.getRawData(), RawDataR);
705 
706     // LValue's and constants
707     APInt SubLK = Two - 1;
708     EXPECT_EQ(SubLK, One);
709 
710     APInt SubKL = 2 - One;
711     EXPECT_EQ(SubKL, One);
712 
713     // RValue's and constants
714     APInt SubRK = getRValue("2", RawDataL) - 1;
715     EXPECT_EQ(SubRK, One);
716     EXPECT_EQ(SubRK.getRawData(), RawDataL);
717 
718     APInt SubKR = 2 - getRValue("1", RawDataR);
719     EXPECT_EQ(SubKR, One);
720     EXPECT_EQ(SubKR.getRawData(), RawDataR);
721   }
722 
723   {
724     // 0x100...0001 - 0x0,FFFF...FFFF = 0x2
725     APInt AllOnes(129, "0FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", 16);
726     APInt HighOneLowOne(129, "100000000000000000000000000000001", 16);
727 
728     APInt SubLL = HighOneLowOne - AllOnes;
729     EXPECT_EQ(SubLL, Two);
730 
731     APInt SubLR = HighOneLowOne -
732                   getRValue("0FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", RawDataR);
733     EXPECT_EQ(SubLR, Two);
734     EXPECT_EQ(SubLR.getRawData(), RawDataR);
735 
736     APInt SubRL = getRValue("100000000000000000000000000000001", RawDataL) -
737                   AllOnes;
738     EXPECT_EQ(SubRL, Two);
739     EXPECT_EQ(SubRL.getRawData(), RawDataL);
740 
741     APInt SubRR = getRValue("100000000000000000000000000000001", RawDataL) -
742                   getRValue("0FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", RawDataR);
743     EXPECT_EQ(SubRR, Two);
744     EXPECT_EQ(SubRR.getRawData(), RawDataR);
745 
746     // LValue's and constants
747     // 0x100...0001 - 0x2 = 0x0,FFFF...FFFF
748     APInt SubLK = HighOneLowOne - 2;
749     EXPECT_EQ(SubLK, AllOnes);
750 
751     // 2 - (-1) = 3
752     APInt SubKL = 2 - MinusOne;
753     EXPECT_EQ(SubKL, Three);
754 
755     // RValue's and constants
756     // 0x100...0001 - 0x2 = 0x0,FFFF...FFFF
757     APInt SubRK = getRValue("100000000000000000000000000000001", RawDataL) - 2;
758     EXPECT_EQ(SubRK, AllOnes);
759     EXPECT_EQ(SubRK.getRawData(), RawDataL);
760 
761     APInt SubKR = 2 - getRValue("1FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", RawDataR);
762     EXPECT_EQ(SubKR, Three);
763     EXPECT_EQ(SubKR.getRawData(), RawDataR);
764   }
765 }
766 
767 TEST(APIntTest, rvalue_bitwise) {
768   // Test all combinations of lvalue/rvalue lhs/rhs of and/or/xor
769 
770   // Lamdba to return an APInt by value, but also provide the raw value of the
771   // allocated data.
772   auto getRValue = [](const char *HexString, uint64_t const *&RawData) {
773     APInt V(129, HexString, 16);
774     RawData = V.getRawData();
775     return V;
776   };
777 
778   APInt Ten(129, "A", 16);
779   APInt Twelve(129, "C", 16);
780 
781   const uint64_t *RawDataL = nullptr;
782   const uint64_t *RawDataR = nullptr;
783 
784   {
785     // 12 & 10 = 8
786     APInt AndLL = Ten & Twelve;
787     EXPECT_EQ(AndLL, 0x8);
788 
789     APInt AndLR = Ten & getRValue("C", RawDataR);
790     EXPECT_EQ(AndLR, 0x8);
791     EXPECT_EQ(AndLR.getRawData(), RawDataR);
792 
793     APInt AndRL = getRValue("A", RawDataL) & Twelve;
794     EXPECT_EQ(AndRL, 0x8);
795     EXPECT_EQ(AndRL.getRawData(), RawDataL);
796 
797     APInt AndRR = getRValue("A", RawDataL) & getRValue("C", RawDataR);
798     EXPECT_EQ(AndRR, 0x8);
799     EXPECT_EQ(AndRR.getRawData(), RawDataR);
800 
801     // LValue's and constants
802     APInt AndLK = Ten & 0xc;
803     EXPECT_EQ(AndLK, 0x8);
804 
805     APInt AndKL = 0xa & Twelve;
806     EXPECT_EQ(AndKL, 0x8);
807 
808     // RValue's and constants
809     APInt AndRK = getRValue("A", RawDataL) & 0xc;
810     EXPECT_EQ(AndRK, 0x8);
811     EXPECT_EQ(AndRK.getRawData(), RawDataL);
812 
813     APInt AndKR = 0xa & getRValue("C", RawDataR);
814     EXPECT_EQ(AndKR, 0x8);
815     EXPECT_EQ(AndKR.getRawData(), RawDataR);
816   }
817 
818   {
819     // 12 | 10 = 14
820     APInt OrLL = Ten | Twelve;
821     EXPECT_EQ(OrLL, 0xe);
822 
823     APInt OrLR = Ten | getRValue("C", RawDataR);
824     EXPECT_EQ(OrLR, 0xe);
825     EXPECT_EQ(OrLR.getRawData(), RawDataR);
826 
827     APInt OrRL = getRValue("A", RawDataL) | Twelve;
828     EXPECT_EQ(OrRL, 0xe);
829     EXPECT_EQ(OrRL.getRawData(), RawDataL);
830 
831     APInt OrRR = getRValue("A", RawDataL) | getRValue("C", RawDataR);
832     EXPECT_EQ(OrRR, 0xe);
833     EXPECT_EQ(OrRR.getRawData(), RawDataR);
834 
835     // LValue's and constants
836     APInt OrLK = Ten | 0xc;
837     EXPECT_EQ(OrLK, 0xe);
838 
839     APInt OrKL = 0xa | Twelve;
840     EXPECT_EQ(OrKL, 0xe);
841 
842     // RValue's and constants
843     APInt OrRK = getRValue("A", RawDataL) | 0xc;
844     EXPECT_EQ(OrRK, 0xe);
845     EXPECT_EQ(OrRK.getRawData(), RawDataL);
846 
847     APInt OrKR = 0xa | getRValue("C", RawDataR);
848     EXPECT_EQ(OrKR, 0xe);
849     EXPECT_EQ(OrKR.getRawData(), RawDataR);
850   }
851 
852   {
853     // 12 ^ 10 = 6
854     APInt XorLL = Ten ^ Twelve;
855     EXPECT_EQ(XorLL, 0x6);
856 
857     APInt XorLR = Ten ^ getRValue("C", RawDataR);
858     EXPECT_EQ(XorLR, 0x6);
859     EXPECT_EQ(XorLR.getRawData(), RawDataR);
860 
861     APInt XorRL = getRValue("A", RawDataL) ^ Twelve;
862     EXPECT_EQ(XorRL, 0x6);
863     EXPECT_EQ(XorRL.getRawData(), RawDataL);
864 
865     APInt XorRR = getRValue("A", RawDataL) ^ getRValue("C", RawDataR);
866     EXPECT_EQ(XorRR, 0x6);
867     EXPECT_EQ(XorRR.getRawData(), RawDataR);
868 
869     // LValue's and constants
870     APInt XorLK = Ten ^ 0xc;
871     EXPECT_EQ(XorLK, 0x6);
872 
873     APInt XorKL = 0xa ^ Twelve;
874     EXPECT_EQ(XorKL, 0x6);
875 
876     // RValue's and constants
877     APInt XorRK = getRValue("A", RawDataL) ^ 0xc;
878     EXPECT_EQ(XorRK, 0x6);
879     EXPECT_EQ(XorRK.getRawData(), RawDataL);
880 
881     APInt XorKR = 0xa ^ getRValue("C", RawDataR);
882     EXPECT_EQ(XorKR, 0x6);
883     EXPECT_EQ(XorKR.getRawData(), RawDataR);
884   }
885 }
886 
887 TEST(APIntTest, rvalue_invert) {
888   // Lamdba to return an APInt by value, but also provide the raw value of the
889   // allocated data.
890   auto getRValue = [](const char *HexString, uint64_t const *&RawData) {
891     APInt V(129, HexString, 16);
892     RawData = V.getRawData();
893     return V;
894   };
895 
896   APInt One(129, 1);
897   APInt NegativeTwo(129, -2ULL, true);
898 
899   const uint64_t *RawData = nullptr;
900 
901   {
902     // ~1 = -2
903     APInt NegL = ~One;
904     EXPECT_EQ(NegL, NegativeTwo);
905 
906     APInt NegR = ~getRValue("1", RawData);
907     EXPECT_EQ(NegR, NegativeTwo);
908     EXPECT_EQ(NegR.getRawData(), RawData);
909   }
910 }
911 
912 // Tests different div/rem varaints using scheme (a * b + c) / a
913 void testDiv(APInt a, APInt b, APInt c) {
914   ASSERT_TRUE(a.uge(b)); // Must: a >= b
915   ASSERT_TRUE(a.ugt(c)); // Must: a > c
916 
917   auto p = a * b + c;
918 
919   auto q = p.udiv(a);
920   auto r = p.urem(a);
921   EXPECT_EQ(b, q);
922   EXPECT_EQ(c, r);
923   APInt::udivrem(p, a, q, r);
924   EXPECT_EQ(b, q);
925   EXPECT_EQ(c, r);
926   q = p.sdiv(a);
927   r = p.srem(a);
928   EXPECT_EQ(b, q);
929   EXPECT_EQ(c, r);
930   APInt::sdivrem(p, a, q, r);
931   EXPECT_EQ(b, q);
932   EXPECT_EQ(c, r);
933 
934   if (b.ugt(c)) { // Test also symmetric case
935     q = p.udiv(b);
936     r = p.urem(b);
937     EXPECT_EQ(a, q);
938     EXPECT_EQ(c, r);
939     APInt::udivrem(p, b, q, r);
940     EXPECT_EQ(a, q);
941     EXPECT_EQ(c, r);
942     q = p.sdiv(b);
943     r = p.srem(b);
944     EXPECT_EQ(a, q);
945     EXPECT_EQ(c, r);
946     APInt::sdivrem(p, b, q, r);
947     EXPECT_EQ(a, q);
948     EXPECT_EQ(c, r);
949   }
950 }
951 
952 TEST(APIntTest, divrem_big1) {
953   // Tests KnuthDiv rare step D6
954   testDiv({256, "1ffffffffffffffff", 16},
955           {256, "1ffffffffffffffff", 16},
956           {256, 0});
957 }
958 
959 TEST(APIntTest, divrem_big2) {
960   // Tests KnuthDiv rare step D6
961   testDiv({1024,                       "112233ceff"
962                  "cecece000000ffffffffffffffffffff"
963                  "ffffffffffffffffffffffffffffffff"
964                  "ffffffffffffffffffffffffffffffff"
965                  "ffffffffffffffffffffffffffffff33", 16},
966           {1024,           "111111ffffffffffffffff"
967                  "ffffffffffffffffffffffffffffffff"
968                  "fffffffffffffffffffffffffffffccf"
969                  "ffffffffffffffffffffffffffffff00", 16},
970           {1024, 7919});
971 }
972 
973 TEST(APIntTest, divrem_big3) {
974   // Tests KnuthDiv case without shift
975   testDiv({256, "80000001ffffffffffffffff", 16},
976           {256, "ffffffffffffff0000000", 16},
977           {256, 4219});
978 }
979 
980 TEST(APIntTest, divrem_big4) {
981   // Tests heap allocation in divide() enfoced by huge numbers
982   testDiv(APInt{4096, 5}.shl(2001),
983           APInt{4096, 1}.shl(2000),
984           APInt{4096, 4219*13});
985 }
986 
987 TEST(APIntTest, divrem_big5) {
988   // Tests one word divisor case of divide()
989   testDiv(APInt{1024, 19}.shl(811),
990           APInt{1024, 4356013}, // one word
991           APInt{1024, 1});
992 }
993 
994 TEST(APIntTest, divrem_big6) {
995   // Tests some rare "borrow" cases in D4 step
996   testDiv(APInt{512, "ffffffffffffffff00000000000000000000000001", 16},
997           APInt{512, "10000000000000001000000000000001", 16},
998           APInt{512, "10000000000000000000000000000000", 16});
999 }
1000 
1001 TEST(APIntTest, divrem_big7) {
1002   // Yet another test for KnuthDiv rare step D6.
1003   testDiv({224, "800000008000000200000005", 16},
1004           {224, "fffffffd", 16},
1005           {224, "80000000800000010000000f", 16});
1006 }
1007 
1008 void testDiv(APInt a, uint64_t b, APInt c) {
1009   auto p = a * b + c;
1010 
1011   APInt q;
1012   uint64_t r;
1013   // Unsigned division will only work if our original number wasn't negative.
1014   if (!a.isNegative()) {
1015     q = p.udiv(b);
1016     r = p.urem(b);
1017     EXPECT_EQ(a, q);
1018     EXPECT_EQ(c, r);
1019     APInt::udivrem(p, b, q, r);
1020     EXPECT_EQ(a, q);
1021     EXPECT_EQ(c, r);
1022   }
1023   q = p.sdiv(b);
1024   r = p.srem(b);
1025   EXPECT_EQ(a, q);
1026   if (c.isNegative())
1027     EXPECT_EQ(-c, -r); // Need to negate so the uint64_t compare will work.
1028   else
1029     EXPECT_EQ(c, r);
1030   int64_t sr;
1031   APInt::sdivrem(p, b, q, sr);
1032   EXPECT_EQ(a, q);
1033   if (c.isNegative())
1034     EXPECT_EQ(-c, -sr); // Need to negate so the uint64_t compare will work.
1035   else
1036     EXPECT_EQ(c, sr);
1037 }
1038 
1039 TEST(APIntTest, divremuint) {
1040   // Single word APInt
1041   testDiv(APInt{64, 9},
1042           2,
1043           APInt{64, 1});
1044 
1045   // Single word negative APInt
1046   testDiv(-APInt{64, 9},
1047           2,
1048           -APInt{64, 1});
1049 
1050   // Multiword dividend with only one significant word.
1051   testDiv(APInt{256, 9},
1052           2,
1053           APInt{256, 1});
1054 
1055   // Negative dividend.
1056   testDiv(-APInt{256, 9},
1057           2,
1058           -APInt{256, 1});
1059 
1060   // Multiword dividend
1061   testDiv(APInt{1024, 19}.shl(811),
1062           4356013, // one word
1063           APInt{1024, 1});
1064 }
1065 
1066 TEST(APIntTest, divrem_simple) {
1067   // Test simple cases.
1068   APInt A(65, 2), B(65, 2);
1069   APInt Q, R;
1070 
1071   // X / X
1072   APInt::sdivrem(A, B, Q, R);
1073   EXPECT_EQ(Q, APInt(65, 1));
1074   EXPECT_EQ(R, APInt(65, 0));
1075   APInt::udivrem(A, B, Q, R);
1076   EXPECT_EQ(Q, APInt(65, 1));
1077   EXPECT_EQ(R, APInt(65, 0));
1078 
1079   // 0 / X
1080   APInt O(65, 0);
1081   APInt::sdivrem(O, B, Q, R);
1082   EXPECT_EQ(Q, APInt(65, 0));
1083   EXPECT_EQ(R, APInt(65, 0));
1084   APInt::udivrem(O, B, Q, R);
1085   EXPECT_EQ(Q, APInt(65, 0));
1086   EXPECT_EQ(R, APInt(65, 0));
1087 
1088   // X / 1
1089   APInt I(65, 1);
1090   APInt::sdivrem(A, I, Q, R);
1091   EXPECT_EQ(Q, A);
1092   EXPECT_EQ(R, APInt(65, 0));
1093   APInt::udivrem(A, I, Q, R);
1094   EXPECT_EQ(Q, A);
1095   EXPECT_EQ(R, APInt(65, 0));
1096 }
1097 
1098 TEST(APIntTest, fromString) {
1099   EXPECT_EQ(APInt(32, 0), APInt(32,   "0", 2));
1100   EXPECT_EQ(APInt(32, 1), APInt(32,   "1", 2));
1101   EXPECT_EQ(APInt(32, 2), APInt(32,  "10", 2));
1102   EXPECT_EQ(APInt(32, 3), APInt(32,  "11", 2));
1103   EXPECT_EQ(APInt(32, 4), APInt(32, "100", 2));
1104 
1105   EXPECT_EQ(APInt(32, 0), APInt(32,   "+0", 2));
1106   EXPECT_EQ(APInt(32, 1), APInt(32,   "+1", 2));
1107   EXPECT_EQ(APInt(32, 2), APInt(32,  "+10", 2));
1108   EXPECT_EQ(APInt(32, 3), APInt(32,  "+11", 2));
1109   EXPECT_EQ(APInt(32, 4), APInt(32, "+100", 2));
1110 
1111   EXPECT_EQ(APInt(32, uint64_t(-0LL)), APInt(32,   "-0", 2));
1112   EXPECT_EQ(APInt(32, uint64_t(-1LL)), APInt(32,   "-1", 2));
1113   EXPECT_EQ(APInt(32, uint64_t(-2LL)), APInt(32,  "-10", 2));
1114   EXPECT_EQ(APInt(32, uint64_t(-3LL)), APInt(32,  "-11", 2));
1115   EXPECT_EQ(APInt(32, uint64_t(-4LL)), APInt(32, "-100", 2));
1116 
1117   EXPECT_EQ(APInt(32,  0), APInt(32,  "0",  8));
1118   EXPECT_EQ(APInt(32,  1), APInt(32,  "1",  8));
1119   EXPECT_EQ(APInt(32,  7), APInt(32,  "7",  8));
1120   EXPECT_EQ(APInt(32,  8), APInt(32,  "10", 8));
1121   EXPECT_EQ(APInt(32, 15), APInt(32,  "17", 8));
1122   EXPECT_EQ(APInt(32, 16), APInt(32,  "20", 8));
1123 
1124   EXPECT_EQ(APInt(32,  +0), APInt(32,  "+0",  8));
1125   EXPECT_EQ(APInt(32,  +1), APInt(32,  "+1",  8));
1126   EXPECT_EQ(APInt(32,  +7), APInt(32,  "+7",  8));
1127   EXPECT_EQ(APInt(32,  +8), APInt(32,  "+10", 8));
1128   EXPECT_EQ(APInt(32, +15), APInt(32,  "+17", 8));
1129   EXPECT_EQ(APInt(32, +16), APInt(32,  "+20", 8));
1130 
1131   EXPECT_EQ(APInt(32,  uint64_t(-0LL)), APInt(32,  "-0",  8));
1132   EXPECT_EQ(APInt(32,  uint64_t(-1LL)), APInt(32,  "-1",  8));
1133   EXPECT_EQ(APInt(32,  uint64_t(-7LL)), APInt(32,  "-7",  8));
1134   EXPECT_EQ(APInt(32,  uint64_t(-8LL)), APInt(32,  "-10", 8));
1135   EXPECT_EQ(APInt(32, uint64_t(-15LL)), APInt(32,  "-17", 8));
1136   EXPECT_EQ(APInt(32, uint64_t(-16LL)), APInt(32,  "-20", 8));
1137 
1138   EXPECT_EQ(APInt(32,  0), APInt(32,  "0", 10));
1139   EXPECT_EQ(APInt(32,  1), APInt(32,  "1", 10));
1140   EXPECT_EQ(APInt(32,  9), APInt(32,  "9", 10));
1141   EXPECT_EQ(APInt(32, 10), APInt(32, "10", 10));
1142   EXPECT_EQ(APInt(32, 19), APInt(32, "19", 10));
1143   EXPECT_EQ(APInt(32, 20), APInt(32, "20", 10));
1144 
1145   EXPECT_EQ(APInt(32,  uint64_t(-0LL)), APInt(32,  "-0", 10));
1146   EXPECT_EQ(APInt(32,  uint64_t(-1LL)), APInt(32,  "-1", 10));
1147   EXPECT_EQ(APInt(32,  uint64_t(-9LL)), APInt(32,  "-9", 10));
1148   EXPECT_EQ(APInt(32, uint64_t(-10LL)), APInt(32, "-10", 10));
1149   EXPECT_EQ(APInt(32, uint64_t(-19LL)), APInt(32, "-19", 10));
1150   EXPECT_EQ(APInt(32, uint64_t(-20LL)), APInt(32, "-20", 10));
1151 
1152   EXPECT_EQ(APInt(32,  0), APInt(32,  "0", 16));
1153   EXPECT_EQ(APInt(32,  1), APInt(32,  "1", 16));
1154   EXPECT_EQ(APInt(32, 15), APInt(32,  "F", 16));
1155   EXPECT_EQ(APInt(32, 16), APInt(32, "10", 16));
1156   EXPECT_EQ(APInt(32, 31), APInt(32, "1F", 16));
1157   EXPECT_EQ(APInt(32, 32), APInt(32, "20", 16));
1158 
1159   EXPECT_EQ(APInt(32,  uint64_t(-0LL)), APInt(32,  "-0", 16));
1160   EXPECT_EQ(APInt(32,  uint64_t(-1LL)), APInt(32,  "-1", 16));
1161   EXPECT_EQ(APInt(32, uint64_t(-15LL)), APInt(32,  "-F", 16));
1162   EXPECT_EQ(APInt(32, uint64_t(-16LL)), APInt(32, "-10", 16));
1163   EXPECT_EQ(APInt(32, uint64_t(-31LL)), APInt(32, "-1F", 16));
1164   EXPECT_EQ(APInt(32, uint64_t(-32LL)), APInt(32, "-20", 16));
1165 
1166   EXPECT_EQ(APInt(32,  0), APInt(32,  "0", 36));
1167   EXPECT_EQ(APInt(32,  1), APInt(32,  "1", 36));
1168   EXPECT_EQ(APInt(32, 35), APInt(32,  "Z", 36));
1169   EXPECT_EQ(APInt(32, 36), APInt(32, "10", 36));
1170   EXPECT_EQ(APInt(32, 71), APInt(32, "1Z", 36));
1171   EXPECT_EQ(APInt(32, 72), APInt(32, "20", 36));
1172 
1173   EXPECT_EQ(APInt(32,  uint64_t(-0LL)), APInt(32,  "-0", 36));
1174   EXPECT_EQ(APInt(32,  uint64_t(-1LL)), APInt(32,  "-1", 36));
1175   EXPECT_EQ(APInt(32, uint64_t(-35LL)), APInt(32,  "-Z", 36));
1176   EXPECT_EQ(APInt(32, uint64_t(-36LL)), APInt(32, "-10", 36));
1177   EXPECT_EQ(APInt(32, uint64_t(-71LL)), APInt(32, "-1Z", 36));
1178   EXPECT_EQ(APInt(32, uint64_t(-72LL)), APInt(32, "-20", 36));
1179 }
1180 
1181 TEST(APIntTest, SaturatingMath) {
1182   APInt AP_10 = APInt(8, 10);
1183   APInt AP_42 = APInt(8, 42);
1184   APInt AP_100 = APInt(8, 100);
1185   APInt AP_200 = APInt(8, 200);
1186 
1187   EXPECT_EQ(APInt(8, 100), AP_100.truncUSat(8));
1188   EXPECT_EQ(APInt(7, 100), AP_100.truncUSat(7));
1189   EXPECT_EQ(APInt(6, 63), AP_100.truncUSat(6));
1190   EXPECT_EQ(APInt(5, 31), AP_100.truncUSat(5));
1191 
1192   EXPECT_EQ(APInt(8, 200), AP_200.truncUSat(8));
1193   EXPECT_EQ(APInt(7, 127), AP_200.truncUSat(7));
1194   EXPECT_EQ(APInt(6, 63), AP_200.truncUSat(6));
1195   EXPECT_EQ(APInt(5, 31), AP_200.truncUSat(5));
1196 
1197   EXPECT_EQ(APInt(8, 42), AP_42.truncSSat(8));
1198   EXPECT_EQ(APInt(7, 42), AP_42.truncSSat(7));
1199   EXPECT_EQ(APInt(6, 31), AP_42.truncSSat(6));
1200   EXPECT_EQ(APInt(5, 15), AP_42.truncSSat(5));
1201 
1202   EXPECT_EQ(APInt(8, -56), AP_200.truncSSat(8));
1203   EXPECT_EQ(APInt(7, -56), AP_200.truncSSat(7));
1204   EXPECT_EQ(APInt(6, -32), AP_200.truncSSat(6));
1205   EXPECT_EQ(APInt(5, -16), AP_200.truncSSat(5));
1206 
1207   EXPECT_EQ(APInt(8, 200), AP_100.uadd_sat(AP_100));
1208   EXPECT_EQ(APInt(8, 255), AP_100.uadd_sat(AP_200));
1209   EXPECT_EQ(APInt(8, 255), APInt(8, 255).uadd_sat(APInt(8, 255)));
1210 
1211   EXPECT_EQ(APInt(8, 110), AP_10.sadd_sat(AP_100));
1212   EXPECT_EQ(APInt(8, 127), AP_100.sadd_sat(AP_100));
1213   EXPECT_EQ(APInt(8, -128), (-AP_100).sadd_sat(-AP_100));
1214   EXPECT_EQ(APInt(8, -128), APInt(8, -128).sadd_sat(APInt(8, -128)));
1215 
1216   EXPECT_EQ(APInt(8, 90), AP_100.usub_sat(AP_10));
1217   EXPECT_EQ(APInt(8, 0), AP_100.usub_sat(AP_200));
1218   EXPECT_EQ(APInt(8, 0), APInt(8, 0).usub_sat(APInt(8, 255)));
1219 
1220   EXPECT_EQ(APInt(8, -90), AP_10.ssub_sat(AP_100));
1221   EXPECT_EQ(APInt(8, 127), AP_100.ssub_sat(-AP_100));
1222   EXPECT_EQ(APInt(8, -128), (-AP_100).ssub_sat(AP_100));
1223   EXPECT_EQ(APInt(8, -128), APInt(8, -128).ssub_sat(APInt(8, 127)));
1224 
1225   EXPECT_EQ(APInt(8, 250), APInt(8, 50).umul_sat(APInt(8, 5)));
1226   EXPECT_EQ(APInt(8, 255), APInt(8, 50).umul_sat(APInt(8, 6)));
1227   EXPECT_EQ(APInt(8, 255), APInt(8, -128).umul_sat(APInt(8, 3)));
1228   EXPECT_EQ(APInt(8, 255), APInt(8, 3).umul_sat(APInt(8, -128)));
1229   EXPECT_EQ(APInt(8, 255), APInt(8, -128).umul_sat(APInt(8, -128)));
1230 
1231   EXPECT_EQ(APInt(8, 125), APInt(8, 25).smul_sat(APInt(8, 5)));
1232   EXPECT_EQ(APInt(8, 127), APInt(8, 25).smul_sat(APInt(8, 6)));
1233   EXPECT_EQ(APInt(8, 127), APInt(8, 127).smul_sat(APInt(8, 127)));
1234   EXPECT_EQ(APInt(8, -125), APInt(8, -25).smul_sat(APInt(8, 5)));
1235   EXPECT_EQ(APInt(8, -125), APInt(8, 25).smul_sat(APInt(8, -5)));
1236   EXPECT_EQ(APInt(8, 125), APInt(8, -25).smul_sat(APInt(8, -5)));
1237   EXPECT_EQ(APInt(8, 125), APInt(8, 25).smul_sat(APInt(8, 5)));
1238   EXPECT_EQ(APInt(8, -128), APInt(8, -25).smul_sat(APInt(8, 6)));
1239   EXPECT_EQ(APInt(8, -128), APInt(8, 25).smul_sat(APInt(8, -6)));
1240   EXPECT_EQ(APInt(8, 127), APInt(8, -25).smul_sat(APInt(8, -6)));
1241   EXPECT_EQ(APInt(8, 127), APInt(8, 25).smul_sat(APInt(8, 6)));
1242 
1243   EXPECT_EQ(APInt(8, 128), APInt(8, 4).ushl_sat(APInt(8, 5)));
1244   EXPECT_EQ(APInt(8, 255), APInt(8, 4).ushl_sat(APInt(8, 6)));
1245   EXPECT_EQ(APInt(8, 128), APInt(8, 1).ushl_sat(APInt(8, 7)));
1246   EXPECT_EQ(APInt(8, 255), APInt(8, 1).ushl_sat(APInt(8, 8)));
1247   EXPECT_EQ(APInt(8, 255), APInt(8, -128).ushl_sat(APInt(8, 2)));
1248   EXPECT_EQ(APInt(8, 255), APInt(8, 64).ushl_sat(APInt(8, 2)));
1249   EXPECT_EQ(APInt(8, 255), APInt(8, 64).ushl_sat(APInt(8, -2)));
1250 
1251   EXPECT_EQ(APInt(8, 64), APInt(8, 4).sshl_sat(APInt(8, 4)));
1252   EXPECT_EQ(APInt(8, 127), APInt(8, 4).sshl_sat(APInt(8, 5)));
1253   EXPECT_EQ(APInt(8, 127), APInt(8, 1).sshl_sat(APInt(8, 8)));
1254   EXPECT_EQ(APInt(8, -64), APInt(8, -4).sshl_sat(APInt(8, 4)));
1255   EXPECT_EQ(APInt(8, -128), APInt(8, -4).sshl_sat(APInt(8, 5)));
1256   EXPECT_EQ(APInt(8, -128), APInt(8, -4).sshl_sat(APInt(8, 6)));
1257   EXPECT_EQ(APInt(8, -128), APInt(8, -1).sshl_sat(APInt(8, 7)));
1258   EXPECT_EQ(APInt(8, -128), APInt(8, -1).sshl_sat(APInt(8, 8)));
1259 }
1260 
1261 TEST(APIntTest, FromArray) {
1262   EXPECT_EQ(APInt(32, uint64_t(1)), APInt(32, ArrayRef<uint64_t>(1)));
1263 }
1264 
1265 TEST(APIntTest, StringBitsNeeded2) {
1266   EXPECT_EQ(1U, APInt::getBitsNeeded(  "0", 2));
1267   EXPECT_EQ(1U, APInt::getBitsNeeded(  "1", 2));
1268   EXPECT_EQ(2U, APInt::getBitsNeeded( "10", 2));
1269   EXPECT_EQ(2U, APInt::getBitsNeeded( "11", 2));
1270   EXPECT_EQ(3U, APInt::getBitsNeeded("100", 2));
1271 
1272   EXPECT_EQ(1U, APInt::getBitsNeeded(  "+0", 2));
1273   EXPECT_EQ(1U, APInt::getBitsNeeded(  "+1", 2));
1274   EXPECT_EQ(2U, APInt::getBitsNeeded( "+10", 2));
1275   EXPECT_EQ(2U, APInt::getBitsNeeded( "+11", 2));
1276   EXPECT_EQ(3U, APInt::getBitsNeeded("+100", 2));
1277 
1278   EXPECT_EQ(2U, APInt::getBitsNeeded(  "-0", 2));
1279   EXPECT_EQ(2U, APInt::getBitsNeeded(  "-1", 2));
1280   EXPECT_EQ(3U, APInt::getBitsNeeded( "-10", 2));
1281   EXPECT_EQ(3U, APInt::getBitsNeeded( "-11", 2));
1282   EXPECT_EQ(4U, APInt::getBitsNeeded("-100", 2));
1283 }
1284 
1285 TEST(APIntTest, StringBitsNeeded8) {
1286   EXPECT_EQ(3U, APInt::getBitsNeeded( "0", 8));
1287   EXPECT_EQ(3U, APInt::getBitsNeeded( "7", 8));
1288   EXPECT_EQ(6U, APInt::getBitsNeeded("10", 8));
1289   EXPECT_EQ(6U, APInt::getBitsNeeded("17", 8));
1290   EXPECT_EQ(6U, APInt::getBitsNeeded("20", 8));
1291 
1292   EXPECT_EQ(3U, APInt::getBitsNeeded( "+0", 8));
1293   EXPECT_EQ(3U, APInt::getBitsNeeded( "+7", 8));
1294   EXPECT_EQ(6U, APInt::getBitsNeeded("+10", 8));
1295   EXPECT_EQ(6U, APInt::getBitsNeeded("+17", 8));
1296   EXPECT_EQ(6U, APInt::getBitsNeeded("+20", 8));
1297 
1298   EXPECT_EQ(4U, APInt::getBitsNeeded( "-0", 8));
1299   EXPECT_EQ(4U, APInt::getBitsNeeded( "-7", 8));
1300   EXPECT_EQ(7U, APInt::getBitsNeeded("-10", 8));
1301   EXPECT_EQ(7U, APInt::getBitsNeeded("-17", 8));
1302   EXPECT_EQ(7U, APInt::getBitsNeeded("-20", 8));
1303 }
1304 
1305 TEST(APIntTest, StringBitsNeeded10) {
1306   EXPECT_EQ(1U, APInt::getBitsNeeded( "0", 10));
1307   EXPECT_EQ(2U, APInt::getBitsNeeded( "3", 10));
1308   EXPECT_EQ(4U, APInt::getBitsNeeded( "9", 10));
1309   EXPECT_EQ(4U, APInt::getBitsNeeded("10", 10));
1310   EXPECT_EQ(5U, APInt::getBitsNeeded("19", 10));
1311   EXPECT_EQ(5U, APInt::getBitsNeeded("20", 10));
1312 
1313   EXPECT_EQ(1U, APInt::getBitsNeeded( "+0", 10));
1314   EXPECT_EQ(4U, APInt::getBitsNeeded( "+9", 10));
1315   EXPECT_EQ(4U, APInt::getBitsNeeded("+10", 10));
1316   EXPECT_EQ(5U, APInt::getBitsNeeded("+19", 10));
1317   EXPECT_EQ(5U, APInt::getBitsNeeded("+20", 10));
1318 
1319   EXPECT_EQ(2U, APInt::getBitsNeeded( "-0", 10));
1320   EXPECT_EQ(5U, APInt::getBitsNeeded( "-9", 10));
1321   EXPECT_EQ(5U, APInt::getBitsNeeded("-10", 10));
1322   EXPECT_EQ(6U, APInt::getBitsNeeded("-19", 10));
1323   EXPECT_EQ(6U, APInt::getBitsNeeded("-20", 10));
1324 
1325   EXPECT_EQ(1U, APInt::getBitsNeeded("-1", 10));
1326   EXPECT_EQ(2U, APInt::getBitsNeeded("-2", 10));
1327   EXPECT_EQ(3U, APInt::getBitsNeeded("-4", 10));
1328   EXPECT_EQ(4U, APInt::getBitsNeeded("-8", 10));
1329   EXPECT_EQ(5U, APInt::getBitsNeeded("-16", 10));
1330   EXPECT_EQ(6U, APInt::getBitsNeeded("-23", 10));
1331   EXPECT_EQ(6U, APInt::getBitsNeeded("-32", 10));
1332   EXPECT_EQ(7U, APInt::getBitsNeeded("-64", 10));
1333   EXPECT_EQ(8U, APInt::getBitsNeeded("-127", 10));
1334   EXPECT_EQ(8U, APInt::getBitsNeeded("-128", 10));
1335   EXPECT_EQ(9U, APInt::getBitsNeeded("-255", 10));
1336   EXPECT_EQ(9U, APInt::getBitsNeeded("-256", 10));
1337   EXPECT_EQ(10U, APInt::getBitsNeeded("-512", 10));
1338   EXPECT_EQ(11U, APInt::getBitsNeeded("-1024", 10));
1339   EXPECT_EQ(12U, APInt::getBitsNeeded("-1025", 10));
1340 }
1341 
1342 TEST(APIntTest, StringBitsNeeded16) {
1343   EXPECT_EQ(4U, APInt::getBitsNeeded( "0", 16));
1344   EXPECT_EQ(4U, APInt::getBitsNeeded( "F", 16));
1345   EXPECT_EQ(8U, APInt::getBitsNeeded("10", 16));
1346   EXPECT_EQ(8U, APInt::getBitsNeeded("1F", 16));
1347   EXPECT_EQ(8U, APInt::getBitsNeeded("20", 16));
1348 
1349   EXPECT_EQ(4U, APInt::getBitsNeeded( "+0", 16));
1350   EXPECT_EQ(4U, APInt::getBitsNeeded( "+F", 16));
1351   EXPECT_EQ(8U, APInt::getBitsNeeded("+10", 16));
1352   EXPECT_EQ(8U, APInt::getBitsNeeded("+1F", 16));
1353   EXPECT_EQ(8U, APInt::getBitsNeeded("+20", 16));
1354 
1355   EXPECT_EQ(5U, APInt::getBitsNeeded( "-0", 16));
1356   EXPECT_EQ(5U, APInt::getBitsNeeded( "-F", 16));
1357   EXPECT_EQ(9U, APInt::getBitsNeeded("-10", 16));
1358   EXPECT_EQ(9U, APInt::getBitsNeeded("-1F", 16));
1359   EXPECT_EQ(9U, APInt::getBitsNeeded("-20", 16));
1360 }
1361 
1362 TEST(APIntTest, toString) {
1363   SmallString<16> S;
1364   bool isSigned;
1365 
1366   APInt(8, 0).toString(S, 2, true, true);
1367   EXPECT_EQ(std::string(S), "0b0");
1368   S.clear();
1369   APInt(8, 0).toString(S, 8, true, true);
1370   EXPECT_EQ(std::string(S), "00");
1371   S.clear();
1372   APInt(8, 0).toString(S, 10, true, true);
1373   EXPECT_EQ(std::string(S), "0");
1374   S.clear();
1375   APInt(8, 0).toString(S, 16, true, true);
1376   EXPECT_EQ(std::string(S), "0x0");
1377   S.clear();
1378   APInt(8, 0).toString(S, 36, true, false);
1379   EXPECT_EQ(std::string(S), "0");
1380   S.clear();
1381 
1382   // with separators
1383   APInt(64, 140).toString(S, 2, false, true, false, true);
1384   EXPECT_EQ(std::string(S), "0b1000'1100");
1385   S.clear();
1386   APInt(64, 1024).toString(S, 8, false, true, false, true);
1387   EXPECT_EQ(std::string(S), "02'000");
1388   S.clear();
1389   APInt(64, 1000000).toString(S, 10, false, true, false, true);
1390   EXPECT_EQ(std::string(S), "1'000'000");
1391   S.clear();
1392   APInt(64, 1000000).toString(S, 16, false, true, true, true);
1393   EXPECT_EQ(std::string(S), "0xF'4240");
1394   S.clear();
1395   APInt(64, 1'000'000'000).toString(S, 36, false, false, false, true);
1396   EXPECT_EQ(std::string(S), "gj'dgxs");
1397   S.clear();
1398 
1399   isSigned = false;
1400   APInt(8, 255, isSigned).toString(S, 2, isSigned, true);
1401   EXPECT_EQ(std::string(S), "0b11111111");
1402   S.clear();
1403   APInt(8, 255, isSigned).toString(S, 8, isSigned, true);
1404   EXPECT_EQ(std::string(S), "0377");
1405   S.clear();
1406   APInt(8, 255, isSigned).toString(S, 10, isSigned, true);
1407   EXPECT_EQ(std::string(S), "255");
1408   S.clear();
1409   APInt(8, 255, isSigned).toString(S, 16, isSigned, true, /*UpperCase=*/false);
1410   EXPECT_EQ(std::string(S), "0xff");
1411   S.clear();
1412   APInt(8, 255, isSigned).toString(S, 16, isSigned, true);
1413   EXPECT_EQ(std::string(S), "0xFF");
1414   S.clear();
1415   APInt(8, 255, isSigned).toString(S, 36, isSigned, false);
1416   EXPECT_EQ(std::string(S), "73");
1417   S.clear();
1418 
1419   isSigned = true;
1420   APInt(8, 255, isSigned).toString(S, 2, isSigned, true);
1421   EXPECT_EQ(std::string(S), "-0b1");
1422   S.clear();
1423   APInt(8, 255, isSigned).toString(S, 8, isSigned, true);
1424   EXPECT_EQ(std::string(S), "-01");
1425   S.clear();
1426   APInt(8, 255, isSigned).toString(S, 10, isSigned, true);
1427   EXPECT_EQ(std::string(S), "-1");
1428   S.clear();
1429   APInt(8, 255, isSigned).toString(S, 16, isSigned, true);
1430   EXPECT_EQ(std::string(S), "-0x1");
1431   S.clear();
1432   APInt(8, 255, isSigned).toString(S, 36, isSigned, false);
1433   EXPECT_EQ(std::string(S), "-1");
1434   S.clear();
1435 
1436   // negative with separators
1437   APInt(64, -140, isSigned).toString(S, 2, isSigned, true, false, true);
1438   EXPECT_EQ(std::string(S), "-0b1000'1100");
1439   S.clear();
1440   APInt(64, -1024, isSigned).toString(S, 8, isSigned, true, false, true);
1441   EXPECT_EQ(std::string(S), "-02'000");
1442   S.clear();
1443   APInt(64, -1000000, isSigned).toString(S, 10, isSigned, true, false, true);
1444   EXPECT_EQ(std::string(S), "-1'000'000");
1445   S.clear();
1446   APInt(64, -1000000, isSigned).toString(S, 16, isSigned, true, true, true);
1447   EXPECT_EQ(std::string(S), "-0xF'4240");
1448   S.clear();
1449   APInt(64, -1'000'000'000, isSigned)
1450       .toString(S, 36, isSigned, false, false, true);
1451   EXPECT_EQ(std::string(S), "-gj'dgxs");
1452   S.clear();
1453 }
1454 
1455 TEST(APIntTest, Log2) {
1456   EXPECT_EQ(APInt(15, 7).logBase2(), 2U);
1457   EXPECT_EQ(APInt(15, 7).ceilLogBase2(), 3U);
1458   EXPECT_EQ(APInt(15, 7).exactLogBase2(), -1);
1459   EXPECT_EQ(APInt(15, 8).logBase2(), 3U);
1460   EXPECT_EQ(APInt(15, 8).ceilLogBase2(), 3U);
1461   EXPECT_EQ(APInt(15, 8).exactLogBase2(), 3);
1462   EXPECT_EQ(APInt(15, 9).logBase2(), 3U);
1463   EXPECT_EQ(APInt(15, 9).ceilLogBase2(), 4U);
1464   EXPECT_EQ(APInt(15, 9).exactLogBase2(), -1);
1465 }
1466 
1467 #ifdef GTEST_HAS_DEATH_TEST
1468 #ifndef NDEBUG
1469 TEST(APIntTest, StringDeath) {
1470   EXPECT_DEATH((void)APInt(32, "", 0), "Invalid string length");
1471   EXPECT_DEATH((void)APInt(32, "0", 0), "Radix should be 2, 8, 10, 16, or 36!");
1472   EXPECT_DEATH((void)APInt(32, "", 10), "Invalid string length");
1473   EXPECT_DEATH((void)APInt(32, "-", 10), "String is only a sign, needs a value.");
1474   EXPECT_DEATH((void)APInt(1, "1234", 10), "Insufficient bit width");
1475   EXPECT_DEATH((void)APInt(32, "\0", 10), "Invalid string length");
1476   EXPECT_DEATH((void)APInt(32, StringRef("1\02", 3), 10), "Invalid character in digit string");
1477   EXPECT_DEATH((void)APInt(32, "1L", 10), "Invalid character in digit string");
1478 }
1479 #endif
1480 #endif
1481 
1482 TEST(APIntTest, mul_clear) {
1483   APInt ValA(65, -1ULL);
1484   APInt ValB(65, 4);
1485   APInt ValC(65, 0);
1486   ValC = ValA * ValB;
1487   ValA *= ValB;
1488   SmallString<16> StrA, StrC;
1489   ValA.toString(StrA, 10, false);
1490   ValC.toString(StrC, 10, false);
1491   EXPECT_EQ(std::string(StrA), std::string(StrC));
1492 }
1493 
1494 TEST(APIntTest, Rotate) {
1495   EXPECT_EQ(APInt(8, 1),  APInt(8, 1).rotl(0));
1496   EXPECT_EQ(APInt(8, 2),  APInt(8, 1).rotl(1));
1497   EXPECT_EQ(APInt(8, 4),  APInt(8, 1).rotl(2));
1498   EXPECT_EQ(APInt(8, 16), APInt(8, 1).rotl(4));
1499   EXPECT_EQ(APInt(8, 1),  APInt(8, 1).rotl(8));
1500 
1501   EXPECT_EQ(APInt(8, 16), APInt(8, 16).rotl(0));
1502   EXPECT_EQ(APInt(8, 32), APInt(8, 16).rotl(1));
1503   EXPECT_EQ(APInt(8, 64), APInt(8, 16).rotl(2));
1504   EXPECT_EQ(APInt(8, 1),  APInt(8, 16).rotl(4));
1505   EXPECT_EQ(APInt(8, 16), APInt(8, 16).rotl(8));
1506 
1507   EXPECT_EQ(APInt(32, 2), APInt(32, 1).rotl(33));
1508   EXPECT_EQ(APInt(32, 2), APInt(32, 1).rotl(APInt(32, 33)));
1509 
1510   EXPECT_EQ(APInt(32, 2), APInt(32, 1).rotl(33));
1511   EXPECT_EQ(APInt(32, 2), APInt(32, 1).rotl(APInt(32, 33)));
1512   EXPECT_EQ(APInt(32, 2), APInt(32, 1).rotl(APInt(33, 33)));
1513   EXPECT_EQ(APInt(32, (1 << 8)), APInt(32, 1).rotl(APInt(32, 40)));
1514   EXPECT_EQ(APInt(32, (1 << 30)), APInt(32, 1).rotl(APInt(31, 30)));
1515   EXPECT_EQ(APInt(32, (1 << 31)), APInt(32, 1).rotl(APInt(31, 31)));
1516 
1517   EXPECT_EQ(APInt(32, 1), APInt(32, 1).rotl(APInt(1, 0)));
1518   EXPECT_EQ(APInt(32, 2), APInt(32, 1).rotl(APInt(1, 1)));
1519 
1520   EXPECT_EQ(APInt(32, 16), APInt(32, 1).rotl(APInt(3, 4)));
1521 
1522   EXPECT_EQ(APInt(32, 1), APInt(32, 1).rotl(APInt(64, 64)));
1523   EXPECT_EQ(APInt(32, 2), APInt(32, 1).rotl(APInt(64, 65)));
1524 
1525   EXPECT_EQ(APInt(7, 24), APInt(7, 3).rotl(APInt(7, 3)));
1526   EXPECT_EQ(APInt(7, 24), APInt(7, 3).rotl(APInt(7, 10)));
1527   EXPECT_EQ(APInt(7, 24), APInt(7, 3).rotl(APInt(5, 10)));
1528   EXPECT_EQ(APInt(7, 6), APInt(7, 3).rotl(APInt(12, 120)));
1529 
1530   EXPECT_EQ(APInt(8, 16), APInt(8, 16).rotr(0));
1531   EXPECT_EQ(APInt(8, 8),  APInt(8, 16).rotr(1));
1532   EXPECT_EQ(APInt(8, 4),  APInt(8, 16).rotr(2));
1533   EXPECT_EQ(APInt(8, 1),  APInt(8, 16).rotr(4));
1534   EXPECT_EQ(APInt(8, 16), APInt(8, 16).rotr(8));
1535 
1536   EXPECT_EQ(APInt(8, 1),   APInt(8, 1).rotr(0));
1537   EXPECT_EQ(APInt(8, 128), APInt(8, 1).rotr(1));
1538   EXPECT_EQ(APInt(8, 64),  APInt(8, 1).rotr(2));
1539   EXPECT_EQ(APInt(8, 16),  APInt(8, 1).rotr(4));
1540   EXPECT_EQ(APInt(8, 1),   APInt(8, 1).rotr(8));
1541 
1542   EXPECT_EQ(APInt(32, (1 << 31)), APInt(32, 1).rotr(33));
1543   EXPECT_EQ(APInt(32, (1 << 31)), APInt(32, 1).rotr(APInt(32, 33)));
1544 
1545   EXPECT_EQ(APInt(32, (1 << 31)), APInt(32, 1).rotr(33));
1546   EXPECT_EQ(APInt(32, (1 << 31)), APInt(32, 1).rotr(APInt(32, 33)));
1547   EXPECT_EQ(APInt(32, (1 << 31)), APInt(32, 1).rotr(APInt(33, 33)));
1548   EXPECT_EQ(APInt(32, (1 << 24)), APInt(32, 1).rotr(APInt(32, 40)));
1549 
1550   EXPECT_EQ(APInt(32, (1 << 2)), APInt(32, 1).rotr(APInt(31, 30)));
1551   EXPECT_EQ(APInt(32, (1 << 1)), APInt(32, 1).rotr(APInt(31, 31)));
1552 
1553   EXPECT_EQ(APInt(32, 1), APInt(32, 1).rotr(APInt(1, 0)));
1554   EXPECT_EQ(APInt(32, (1 << 31)), APInt(32, 1).rotr(APInt(1, 1)));
1555 
1556   EXPECT_EQ(APInt(32, (1 << 28)), APInt(32, 1).rotr(APInt(3, 4)));
1557 
1558   EXPECT_EQ(APInt(32, 1), APInt(32, 1).rotr(APInt(64, 64)));
1559   EXPECT_EQ(APInt(32, (1 << 31)), APInt(32, 1).rotr(APInt(64, 65)));
1560 
1561   EXPECT_EQ(APInt(7, 48), APInt(7, 3).rotr(APInt(7, 3)));
1562   EXPECT_EQ(APInt(7, 48), APInt(7, 3).rotr(APInt(7, 10)));
1563   EXPECT_EQ(APInt(7, 48), APInt(7, 3).rotr(APInt(5, 10)));
1564   EXPECT_EQ(APInt(7, 65), APInt(7, 3).rotr(APInt(12, 120)));
1565 
1566   APInt Big(256, "00004000800000000000000000003fff8000000000000003", 16);
1567   APInt Rot(256, "3fff80000000000000030000000000000000000040008000", 16);
1568   EXPECT_EQ(Rot, Big.rotr(144));
1569 
1570   EXPECT_EQ(APInt(32, 8), APInt(32, 1).rotl(Big));
1571   EXPECT_EQ(APInt(32, (1 << 29)), APInt(32, 1).rotr(Big));
1572 }
1573 
1574 TEST(APIntTest, Splat) {
1575   APInt ValA(8, 0x01);
1576   EXPECT_EQ(ValA, APInt::getSplat(8, ValA));
1577   EXPECT_EQ(APInt(64, 0x0101010101010101ULL), APInt::getSplat(64, ValA));
1578 
1579   APInt ValB(3, 5);
1580   EXPECT_EQ(APInt(4, 0xD), APInt::getSplat(4, ValB));
1581   EXPECT_EQ(APInt(15, 0xDB6D), APInt::getSplat(15, ValB));
1582 }
1583 
1584 TEST(APIntTest, tcDecrement) {
1585   // Test single word decrement.
1586 
1587   // No out borrow.
1588   {
1589     APInt::WordType singleWord = ~APInt::WordType(0) << (APInt::APINT_BITS_PER_WORD - 1);
1590     APInt::WordType carry = APInt::tcDecrement(&singleWord, 1);
1591     EXPECT_EQ(carry, APInt::WordType(0));
1592     EXPECT_EQ(singleWord, ~APInt::WordType(0) >> 1);
1593   }
1594 
1595   // With out borrow.
1596   {
1597     APInt::WordType singleWord = 0;
1598     APInt::WordType carry = APInt::tcDecrement(&singleWord, 1);
1599     EXPECT_EQ(carry, APInt::WordType(1));
1600     EXPECT_EQ(singleWord, ~APInt::WordType(0));
1601   }
1602 
1603   // Test multiword decrement.
1604 
1605   // No across word borrow, no out borrow.
1606   {
1607     APInt::WordType test[4] = {0x1, 0x1, 0x1, 0x1};
1608     APInt::WordType expected[4] = {0x0, 0x1, 0x1, 0x1};
1609     APInt::tcDecrement(test, 4);
1610     EXPECT_EQ(APInt::tcCompare(test, expected, 4), 0);
1611   }
1612 
1613   // 1 across word borrow, no out borrow.
1614   {
1615     APInt::WordType test[4] = {0x0, 0xF, 0x1, 0x1};
1616     APInt::WordType expected[4] = {~APInt::WordType(0), 0xE, 0x1, 0x1};
1617     APInt::WordType carry = APInt::tcDecrement(test, 4);
1618     EXPECT_EQ(carry, APInt::WordType(0));
1619     EXPECT_EQ(APInt::tcCompare(test, expected, 4), 0);
1620   }
1621 
1622   // 2 across word borrow, no out borrow.
1623   {
1624     APInt::WordType test[4] = {0x0, 0x0, 0xC, 0x1};
1625     APInt::WordType expected[4] = {~APInt::WordType(0), ~APInt::WordType(0), 0xB, 0x1};
1626     APInt::WordType carry = APInt::tcDecrement(test, 4);
1627     EXPECT_EQ(carry, APInt::WordType(0));
1628     EXPECT_EQ(APInt::tcCompare(test, expected, 4), 0);
1629   }
1630 
1631   // 3 across word borrow, no out borrow.
1632   {
1633     APInt::WordType test[4] = {0x0, 0x0, 0x0, 0x1};
1634     APInt::WordType expected[4] = {~APInt::WordType(0), ~APInt::WordType(0), ~APInt::WordType(0), 0x0};
1635     APInt::WordType carry = APInt::tcDecrement(test, 4);
1636     EXPECT_EQ(carry, APInt::WordType(0));
1637     EXPECT_EQ(APInt::tcCompare(test, expected, 4), 0);
1638   }
1639 
1640   // 3 across word borrow, with out borrow.
1641   {
1642     APInt::WordType test[4] = {0x0, 0x0, 0x0, 0x0};
1643     APInt::WordType expected[4] = {~APInt::WordType(0), ~APInt::WordType(0), ~APInt::WordType(0), ~APInt::WordType(0)};
1644     APInt::WordType carry = APInt::tcDecrement(test, 4);
1645     EXPECT_EQ(carry, APInt::WordType(1));
1646     EXPECT_EQ(APInt::tcCompare(test, expected, 4), 0);
1647   }
1648 }
1649 
1650 TEST(APIntTest, arrayAccess) {
1651   // Single word check.
1652   uint64_t E1 = 0x2CA7F46BF6569915ULL;
1653   APInt A1(64, E1);
1654   for (unsigned i = 0, e = 64; i < e; ++i) {
1655     EXPECT_EQ(bool(E1 & (1ULL << i)),
1656               A1[i]);
1657   }
1658 
1659   // Multiword check.
1660   APInt::WordType E2[4] = {
1661     0xEB6EB136591CBA21ULL,
1662     0x7B9358BD6A33F10AULL,
1663     0x7E7FFA5EADD8846ULL,
1664     0x305F341CA00B613DULL
1665   };
1666   APInt A2(APInt::APINT_BITS_PER_WORD*4, E2);
1667   for (unsigned i = 0; i < 4; ++i) {
1668     for (unsigned j = 0; j < APInt::APINT_BITS_PER_WORD; ++j) {
1669       EXPECT_EQ(bool(E2[i] & (1ULL << j)),
1670                 A2[i*APInt::APINT_BITS_PER_WORD + j]);
1671     }
1672   }
1673 }
1674 
1675 TEST(APIntTest, LargeAPIntConstruction) {
1676   // Check that we can properly construct very large APInt. It is very
1677   // unlikely that people will ever do this, but it is a legal input,
1678   // so we should not crash on it.
1679   APInt A9(UINT32_MAX, 0);
1680   EXPECT_FALSE(A9.getBoolValue());
1681 }
1682 
1683 TEST(APIntTest, nearestLogBase2) {
1684   // Single word check.
1685 
1686   // Test round up.
1687   uint64_t I1 = 0x1800001;
1688   APInt A1(64, I1);
1689   EXPECT_EQ(A1.nearestLogBase2(), A1.ceilLogBase2());
1690 
1691   // Test round down.
1692   uint64_t I2 = 0x1000011;
1693   APInt A2(64, I2);
1694   EXPECT_EQ(A2.nearestLogBase2(), A2.logBase2());
1695 
1696   // Test ties round up.
1697   uint64_t I3 = 0x1800000;
1698   APInt A3(64, I3);
1699   EXPECT_EQ(A3.nearestLogBase2(), A3.ceilLogBase2());
1700 
1701   // Multiple word check.
1702 
1703   // Test round up.
1704   APInt::WordType I4[4] = {0x0, 0xF, 0x18, 0x0};
1705   APInt A4(APInt::APINT_BITS_PER_WORD*4, I4);
1706   EXPECT_EQ(A4.nearestLogBase2(), A4.ceilLogBase2());
1707 
1708   // Test round down.
1709   APInt::WordType I5[4] = {0x0, 0xF, 0x10, 0x0};
1710   APInt A5(APInt::APINT_BITS_PER_WORD*4, I5);
1711   EXPECT_EQ(A5.nearestLogBase2(), A5.logBase2());
1712 
1713   // Test ties round up.
1714   uint64_t I6[4] = {0x0, 0x0, 0x0, 0x18};
1715   APInt A6(APInt::APINT_BITS_PER_WORD*4, I6);
1716   EXPECT_EQ(A6.nearestLogBase2(), A6.ceilLogBase2());
1717 
1718   // Test BitWidth == 1 special cases.
1719   APInt A7(1, 1);
1720   EXPECT_EQ(A7.nearestLogBase2(), 0ULL);
1721   APInt A8(1, 0);
1722   EXPECT_EQ(A8.nearestLogBase2(), UINT32_MAX);
1723 
1724   // Test the zero case when we have a bit width large enough such
1725   // that the bit width is larger than UINT32_MAX-1.
1726   APInt A9(UINT32_MAX, 0);
1727   EXPECT_EQ(A9.nearestLogBase2(), UINT32_MAX);
1728 }
1729 
1730 TEST(APIntTest, IsSplat) {
1731   APInt A(32, 0x01010101);
1732   EXPECT_FALSE(A.isSplat(1));
1733   EXPECT_FALSE(A.isSplat(2));
1734   EXPECT_FALSE(A.isSplat(4));
1735   EXPECT_TRUE(A.isSplat(8));
1736   EXPECT_TRUE(A.isSplat(16));
1737   EXPECT_TRUE(A.isSplat(32));
1738 
1739   APInt B(24, 0xAAAAAA);
1740   EXPECT_FALSE(B.isSplat(1));
1741   EXPECT_TRUE(B.isSplat(2));
1742   EXPECT_TRUE(B.isSplat(4));
1743   EXPECT_TRUE(B.isSplat(8));
1744   EXPECT_TRUE(B.isSplat(24));
1745 
1746   APInt C(24, 0xABAAAB);
1747   EXPECT_FALSE(C.isSplat(1));
1748   EXPECT_FALSE(C.isSplat(2));
1749   EXPECT_FALSE(C.isSplat(4));
1750   EXPECT_FALSE(C.isSplat(8));
1751   EXPECT_TRUE(C.isSplat(24));
1752 
1753   APInt D(32, 0xABBAABBA);
1754   EXPECT_FALSE(D.isSplat(1));
1755   EXPECT_FALSE(D.isSplat(2));
1756   EXPECT_FALSE(D.isSplat(4));
1757   EXPECT_FALSE(D.isSplat(8));
1758   EXPECT_TRUE(D.isSplat(16));
1759   EXPECT_TRUE(D.isSplat(32));
1760 
1761   APInt E(32, 0);
1762   EXPECT_TRUE(E.isSplat(1));
1763   EXPECT_TRUE(E.isSplat(2));
1764   EXPECT_TRUE(E.isSplat(4));
1765   EXPECT_TRUE(E.isSplat(8));
1766   EXPECT_TRUE(E.isSplat(16));
1767   EXPECT_TRUE(E.isSplat(32));
1768 }
1769 
1770 TEST(APIntTest, isMask) {
1771   EXPECT_FALSE(APInt(32, 0x01010101).isMask());
1772   EXPECT_FALSE(APInt(32, 0xf0000000).isMask());
1773   EXPECT_FALSE(APInt(32, 0xffff0000).isMask());
1774   EXPECT_FALSE(APInt(32, 0xff << 1).isMask());
1775 
1776   for (int N : { 1, 2, 3, 4, 7, 8, 16, 32, 64, 127, 128, 129, 256 }) {
1777     EXPECT_FALSE(APInt(N, 0).isMask());
1778 
1779     APInt One(N, 1);
1780     for (int I = 1; I <= N; ++I) {
1781       APInt MaskVal = One.shl(I) - 1;
1782       EXPECT_TRUE(MaskVal.isMask());
1783       EXPECT_TRUE(MaskVal.isMask(I));
1784     }
1785   }
1786 }
1787 
1788 TEST(APIntTest, isShiftedMask) {
1789   EXPECT_FALSE(APInt(32, 0x01010101).isShiftedMask());
1790   EXPECT_TRUE(APInt(32, 0xf0000000).isShiftedMask());
1791   EXPECT_TRUE(APInt(32, 0xffff0000).isShiftedMask());
1792   EXPECT_TRUE(APInt(32, 0xff << 1).isShiftedMask());
1793 
1794   unsigned MaskIdx, MaskLen;
1795   EXPECT_FALSE(APInt(32, 0x01010101).isShiftedMask(MaskIdx, MaskLen));
1796   EXPECT_TRUE(APInt(32, 0xf0000000).isShiftedMask(MaskIdx, MaskLen));
1797   EXPECT_EQ(28, (int)MaskIdx);
1798   EXPECT_EQ(4, (int)MaskLen);
1799   EXPECT_TRUE(APInt(32, 0xffff0000).isShiftedMask(MaskIdx, MaskLen));
1800   EXPECT_EQ(16, (int)MaskIdx);
1801   EXPECT_EQ(16, (int)MaskLen);
1802   EXPECT_TRUE(APInt(32, 0xff << 1).isShiftedMask(MaskIdx, MaskLen));
1803   EXPECT_EQ(1, (int)MaskIdx);
1804   EXPECT_EQ(8, (int)MaskLen);
1805 
1806   for (int N : { 1, 2, 3, 4, 7, 8, 16, 32, 64, 127, 128, 129, 256 }) {
1807     EXPECT_FALSE(APInt(N, 0).isShiftedMask());
1808     EXPECT_FALSE(APInt(N, 0).isShiftedMask(MaskIdx, MaskLen));
1809 
1810     APInt One(N, 1);
1811     for (int I = 1; I < N; ++I) {
1812       APInt MaskVal = One.shl(I) - 1;
1813       EXPECT_TRUE(MaskVal.isShiftedMask());
1814       EXPECT_TRUE(MaskVal.isShiftedMask(MaskIdx, MaskLen));
1815       EXPECT_EQ(0, (int)MaskIdx);
1816       EXPECT_EQ(I, (int)MaskLen);
1817     }
1818     for (int I = 1; I < N - 1; ++I) {
1819       APInt MaskVal = One.shl(I);
1820       EXPECT_TRUE(MaskVal.isShiftedMask());
1821       EXPECT_TRUE(MaskVal.isShiftedMask(MaskIdx, MaskLen));
1822       EXPECT_EQ(I, (int)MaskIdx);
1823       EXPECT_EQ(1, (int)MaskLen);
1824     }
1825     for (int I = 1; I < N; ++I) {
1826       APInt MaskVal = APInt::getHighBitsSet(N, I);
1827       EXPECT_TRUE(MaskVal.isShiftedMask());
1828       EXPECT_TRUE(MaskVal.isShiftedMask(MaskIdx, MaskLen));
1829       EXPECT_EQ(N - I, (int)MaskIdx);
1830       EXPECT_EQ(I, (int)MaskLen);
1831     }
1832   }
1833 }
1834 
1835 TEST(APIntTest, isOneBitSet) {
1836   EXPECT_FALSE(APInt(5, 0x00).isOneBitSet(0));
1837   EXPECT_FALSE(APInt(5, 0x02).isOneBitSet(0));
1838   EXPECT_FALSE(APInt(5, 0x03).isOneBitSet(0));
1839   EXPECT_TRUE(APInt(5, 0x02).isOneBitSet(1));
1840   EXPECT_TRUE(APInt(32, (unsigned)(0xffu << 31)).isOneBitSet(31));
1841 
1842   EXPECT_TRUE(APInt::getOneBitSet(255, 13).isOneBitSet(13));
1843 }
1844 
1845 TEST(APIntTest, isPowerOf2) {
1846   EXPECT_FALSE(APInt(5, 0x00).isPowerOf2());
1847   EXPECT_FALSE(APInt(32, 0x11).isPowerOf2());
1848   EXPECT_TRUE(APInt(17, 0x01).isPowerOf2());
1849   EXPECT_TRUE(APInt(32, (unsigned)(0xffu << 31)).isPowerOf2());
1850 
1851   for (int N : {1, 2, 3, 4, 7, 8, 16, 32, 64, 127, 128, 129, 256}) {
1852     EXPECT_FALSE(APInt(N, 0).isPowerOf2());
1853     EXPECT_TRUE(APInt::getSignedMinValue(N).isPowerOf2());
1854 
1855     APInt One(N, 1);
1856     for (int I = 1; I < N - 1; ++I) {
1857       EXPECT_TRUE(APInt::getOneBitSet(N, I).isPowerOf2());
1858 
1859       APInt MaskVal = One.shl(I);
1860       EXPECT_TRUE(MaskVal.isPowerOf2());
1861     }
1862   }
1863 }
1864 
1865 TEST(APIntTest, isNegatedPowerOf2) {
1866   EXPECT_FALSE(APInt(5, 0x00).isNegatedPowerOf2());
1867   EXPECT_TRUE(APInt(15, 0x7ffe).isNegatedPowerOf2());
1868   EXPECT_TRUE(APInt(16, 0xfffc).isNegatedPowerOf2());
1869   EXPECT_TRUE(APInt(32, 0xffffffff).isNegatedPowerOf2());
1870 
1871   for (int N : {1, 2, 3, 4, 7, 8, 16, 32, 64, 127, 128, 129, 256}) {
1872     EXPECT_FALSE(APInt(N, 0).isNegatedPowerOf2());
1873     EXPECT_TRUE(APInt::getAllOnes(N).isNegatedPowerOf2());
1874     EXPECT_TRUE(APInt::getSignedMinValue(N).isNegatedPowerOf2());
1875     EXPECT_TRUE((-APInt::getSignedMinValue(N)).isNegatedPowerOf2());
1876 
1877     APInt One(N, 1);
1878     for (int I = 1; I < N - 1; ++I) {
1879       EXPECT_FALSE(APInt::getOneBitSet(N, I).isNegatedPowerOf2());
1880       EXPECT_TRUE((-APInt::getOneBitSet(N, I)).isNegatedPowerOf2());
1881 
1882       APInt MaskVal = One.shl(I);
1883       EXPECT_TRUE((-MaskVal).isNegatedPowerOf2());
1884 
1885       APInt ShiftMaskVal = One.getHighBitsSet(N, I);
1886       EXPECT_TRUE(ShiftMaskVal.isNegatedPowerOf2());
1887     }
1888   }
1889 }
1890 
1891 TEST(APIntTest, isAligned) {
1892   struct {
1893     uint64_t alignment;
1894     uint64_t offset;
1895     bool isAligned;
1896   } Tests[] = {
1897       {1, 0, true},  {1, 1, true},  {1, 5, true},  {2, 0, true},
1898       {2, 1, false}, {2, 2, true},  {2, 7, false}, {2, 16, true},
1899       {4, 0, true},  {4, 1, false}, {4, 4, true},  {4, 6, false},
1900   };
1901   for (const auto &T : Tests)
1902     EXPECT_EQ(APInt(32, T.offset).isAligned(Align(T.alignment)), T.isAligned);
1903   // Tests for APInt that can't represent the alignment.
1904   // Here APInt(4, I) can represent values from 0 to 15.
1905   EXPECT_TRUE(APInt(4, 0).isAligned(Align(32))); // zero is always aligned.
1906   for (int I = 1; I < 16; ++I)
1907     EXPECT_FALSE(APInt(4, I).isAligned(Align(32)));
1908 }
1909 
1910 // Test that self-move works with EXPENSIVE_CHECKS. It calls std::shuffle which
1911 // does self-move on some platforms.
1912 #ifdef EXPENSIVE_CHECKS
1913 #if defined(__clang__)
1914 // Disable the pragma warning from versions of Clang without -Wself-move
1915 #pragma clang diagnostic push
1916 #pragma clang diagnostic ignored "-Wunknown-pragmas"
1917 // Disable the warning that triggers on exactly what is being tested.
1918 #pragma clang diagnostic push
1919 #pragma clang diagnostic ignored "-Wself-move"
1920 #endif
1921 TEST(APIntTest, SelfMoveAssignment) {
1922   APInt X(32, 0xdeadbeef);
1923   X = std::move(X);
1924   EXPECT_EQ(32u, X.getBitWidth());
1925   EXPECT_EQ(0xdeadbeefULL, X.getLimitedValue());
1926 
1927   uint64_t Bits[] = {0xdeadbeefdeadbeefULL, 0xdeadbeefdeadbeefULL};
1928   APInt Y(128, Bits);
1929   Y = std::move(Y);
1930   EXPECT_EQ(128u, Y.getBitWidth());
1931   EXPECT_EQ(~0ULL, Y.getLimitedValue());
1932   const uint64_t *Raw = Y.getRawData();
1933   EXPECT_EQ(2u, Y.getNumWords());
1934   EXPECT_EQ(0xdeadbeefdeadbeefULL, Raw[0]);
1935   EXPECT_EQ(0xdeadbeefdeadbeefULL, Raw[1]);
1936 }
1937 #if defined(__clang__)
1938 #pragma clang diagnostic pop
1939 #pragma clang diagnostic pop
1940 #endif
1941 #endif // EXPENSIVE_CHECKS
1942 
1943 TEST(APIntTest, byteSwap) {
1944   EXPECT_EQ(0x00000000, APInt(16, 0x0000).byteSwap());
1945   EXPECT_EQ(0x0000010f, APInt(16, 0x0f01).byteSwap());
1946   EXPECT_EQ(0x00ff8000, APInt(24, 0x0080ff).byteSwap());
1947   EXPECT_EQ(0x117700ff, APInt(32, 0xff007711).byteSwap());
1948   EXPECT_EQ(0x228811aaffULL, APInt(40, 0xffaa118822ULL).byteSwap());
1949   EXPECT_EQ(0x050403020100ULL, APInt(48, 0x000102030405ULL).byteSwap());
1950   EXPECT_EQ(0xff050403020100ULL, APInt(56, 0x000102030405ffULL).byteSwap());
1951   EXPECT_EQ(0xff050403020100aaULL, APInt(64, 0xaa000102030405ffULL).byteSwap());
1952 
1953   for (unsigned N : {16, 24, 32, 48, 56, 64, 72, 80, 96, 112, 128, 248, 256,
1954                      1024, 1032, 1040}) {
1955     for (unsigned I = 0; I < N; I += 8) {
1956       APInt X = APInt::getBitsSet(N, I, I + 8);
1957       APInt Y = APInt::getBitsSet(N, N - I - 8, N - I);
1958       EXPECT_EQ(Y, X.byteSwap());
1959       EXPECT_EQ(X, Y.byteSwap());
1960     }
1961   }
1962 }
1963 
1964 TEST(APIntTest, reverseBits) {
1965   EXPECT_EQ(1, APInt(1, 1).reverseBits());
1966   EXPECT_EQ(0, APInt(1, 0).reverseBits());
1967 
1968   EXPECT_EQ(3, APInt(2, 3).reverseBits());
1969   EXPECT_EQ(3, APInt(2, 3).reverseBits());
1970 
1971   EXPECT_EQ(0xb, APInt(4, 0xd).reverseBits());
1972   EXPECT_EQ(0xd, APInt(4, 0xb).reverseBits());
1973   EXPECT_EQ(0xf, APInt(4, 0xf).reverseBits());
1974 
1975   EXPECT_EQ(0x30, APInt(7, 0x6).reverseBits());
1976   EXPECT_EQ(0x5a, APInt(7, 0x2d).reverseBits());
1977 
1978   EXPECT_EQ(0x0f, APInt(8, 0xf0).reverseBits());
1979   EXPECT_EQ(0xf0, APInt(8, 0x0f).reverseBits());
1980 
1981   EXPECT_EQ(0x0f0f, APInt(16, 0xf0f0).reverseBits());
1982   EXPECT_EQ(0xf0f0, APInt(16, 0x0f0f).reverseBits());
1983 
1984   EXPECT_EQ(0x0f0f0f0f, APInt(32, 0xf0f0f0f0).reverseBits());
1985   EXPECT_EQ(0xf0f0f0f0, APInt(32, 0x0f0f0f0f).reverseBits());
1986 
1987   EXPECT_EQ(0x402880a0 >> 1, APInt(31, 0x05011402).reverseBits());
1988 
1989   EXPECT_EQ(0x0f0f0f0f, APInt(32, 0xf0f0f0f0).reverseBits());
1990   EXPECT_EQ(0xf0f0f0f0, APInt(32, 0x0f0f0f0f).reverseBits());
1991 
1992   EXPECT_EQ(0x0f0f0f0f0f0f0f0f, APInt(64, 0xf0f0f0f0f0f0f0f0).reverseBits());
1993   EXPECT_EQ(0xf0f0f0f0f0f0f0f0, APInt(64, 0x0f0f0f0f0f0f0f0f).reverseBits());
1994 
1995   for (unsigned N : { 1, 8, 16, 24, 31, 32, 33,
1996                       63, 64, 65, 127, 128, 257, 1024 }) {
1997     for (unsigned I = 0; I < N; ++I) {
1998       APInt X = APInt::getOneBitSet(N, I);
1999       APInt Y = APInt::getOneBitSet(N, N - (I + 1));
2000       EXPECT_EQ(Y, X.reverseBits());
2001       EXPECT_EQ(X, Y.reverseBits());
2002     }
2003   }
2004 }
2005 
2006 TEST(APIntTest, insertBits) {
2007   APInt iSrc(31, 0x00123456);
2008 
2009   // Direct copy.
2010   APInt i31(31, 0x76543210ull);
2011   i31.insertBits(iSrc, 0);
2012   EXPECT_EQ(static_cast<int64_t>(0x00123456ull), i31.getSExtValue());
2013 
2014   // Single word src/dst insertion.
2015   APInt i63(63, 0x01234567FFFFFFFFull);
2016   i63.insertBits(iSrc, 4);
2017   EXPECT_EQ(static_cast<int64_t>(0x012345600123456Full), i63.getSExtValue());
2018 
2019   // Zero width insert is a noop.
2020   i31.insertBits(APInt::getZeroWidth(), 1);
2021   EXPECT_EQ(static_cast<int64_t>(0x00123456ull), i31.getSExtValue());
2022 
2023   // Insert single word src into one word of dst.
2024   APInt i120(120, UINT64_MAX, true);
2025   i120.insertBits(iSrc, 8);
2026   EXPECT_EQ(static_cast<int64_t>(0xFFFFFF80123456FFull), i120.getSExtValue());
2027 
2028   // Insert single word src into two words of dst.
2029   APInt i127(127, UINT64_MAX, true);
2030   i127.insertBits(iSrc, 48);
2031   EXPECT_EQ(i127.extractBits(64, 0).getZExtValue(), 0x3456FFFFFFFFFFFFull);
2032   EXPECT_EQ(i127.extractBits(63, 64).getZExtValue(), 0x7FFFFFFFFFFF8012ull);
2033 
2034   // Insert on word boundaries.
2035   APInt i128(128, 0);
2036   i128.insertBits(APInt(64, UINT64_MAX, true), 0);
2037   i128.insertBits(APInt(64, UINT64_MAX, true), 64);
2038   EXPECT_EQ(-1, i128.getSExtValue());
2039 
2040   APInt i256(256, UINT64_MAX, true);
2041   i256.insertBits(APInt(65, 0), 0);
2042   i256.insertBits(APInt(69, 0), 64);
2043   i256.insertBits(APInt(128, 0), 128);
2044   EXPECT_EQ(0u, i256.getSExtValue());
2045 
2046   APInt i257(257, 0);
2047   i257.insertBits(APInt(96, UINT64_MAX, true), 64);
2048   EXPECT_EQ(i257.extractBits(64, 0).getZExtValue(), 0x0000000000000000ull);
2049   EXPECT_EQ(i257.extractBits(64, 64).getZExtValue(), 0xFFFFFFFFFFFFFFFFull);
2050   EXPECT_EQ(i257.extractBits(64, 128).getZExtValue(), 0x00000000FFFFFFFFull);
2051   EXPECT_EQ(i257.extractBits(65, 192).getZExtValue(), 0x0000000000000000ull);
2052 
2053   // General insertion.
2054   APInt i260(260, UINT64_MAX, true);
2055   i260.insertBits(APInt(129, 1ull << 48), 15);
2056   EXPECT_EQ(i260.extractBits(64, 0).getZExtValue(), 0x8000000000007FFFull);
2057   EXPECT_EQ(i260.extractBits(64, 64).getZExtValue(), 0x0000000000000000ull);
2058   EXPECT_EQ(i260.extractBits(64, 128).getZExtValue(), 0xFFFFFFFFFFFF0000ull);
2059   EXPECT_EQ(i260.extractBits(64, 192).getZExtValue(), 0xFFFFFFFFFFFFFFFFull);
2060   EXPECT_EQ(i260.extractBits(4, 256).getZExtValue(), 0x000000000000000Full);
2061 }
2062 
2063 TEST(APIntTest, insertBitsUInt64) {
2064   // Tests cloned from insertBits but adapted to the numBits <= 64 constraint
2065   uint64_t iSrc = 0x00123456;
2066 
2067   // Direct copy.
2068   APInt i31(31, 0x76543210ull);
2069   i31.insertBits(iSrc, 0, 31);
2070   EXPECT_EQ(static_cast<int64_t>(0x00123456ull), i31.getSExtValue());
2071 
2072   // Single word src/dst insertion.
2073   APInt i63(63, 0x01234567FFFFFFFFull);
2074   i63.insertBits(iSrc, 4, 31);
2075   EXPECT_EQ(static_cast<int64_t>(0x012345600123456Full), i63.getSExtValue());
2076 
2077   // Insert single word src into one word of dst.
2078   APInt i120(120, UINT64_MAX, true);
2079   i120.insertBits(iSrc, 8, 31);
2080   EXPECT_EQ(static_cast<int64_t>(0xFFFFFF80123456FFull), i120.getSExtValue());
2081 
2082   // Insert single word src into two words of dst.
2083   APInt i127(127, UINT64_MAX, true);
2084   i127.insertBits(iSrc, 48, 31);
2085   EXPECT_EQ(i127.extractBits(64, 0).getZExtValue(), 0x3456FFFFFFFFFFFFull);
2086   EXPECT_EQ(i127.extractBits(63, 64).getZExtValue(), 0x7FFFFFFFFFFF8012ull);
2087 
2088   // Insert on word boundaries.
2089   APInt i128(128, 0);
2090   i128.insertBits(UINT64_MAX, 0, 64);
2091   i128.insertBits(UINT64_MAX, 64, 64);
2092   EXPECT_EQ(-1, i128.getSExtValue());
2093 
2094   APInt i256(256, UINT64_MAX, true);
2095   i256.insertBits(0, 0, 64);
2096   i256.insertBits(0, 64, 1);
2097   i256.insertBits(0, 64, 64);
2098   i256.insertBits(0, 128, 5);
2099   i256.insertBits(0, 128, 64);
2100   i256.insertBits(0, 192, 64);
2101   EXPECT_EQ(0u, i256.getSExtValue());
2102 
2103   APInt i257(257, 0);
2104   i257.insertBits(APInt(96, UINT64_MAX, true), 64);
2105   EXPECT_EQ(i257.extractBitsAsZExtValue(64, 0), 0x0000000000000000ull);
2106   EXPECT_EQ(i257.extractBitsAsZExtValue(64, 64), 0xFFFFFFFFFFFFFFFFull);
2107   EXPECT_EQ(i257.extractBitsAsZExtValue(64, 128), 0x00000000FFFFFFFFull);
2108   EXPECT_EQ(i257.extractBitsAsZExtValue(64, 192), 0x0000000000000000ull);
2109   EXPECT_EQ(i257.extractBitsAsZExtValue(1, 256), 0x0000000000000000ull);
2110 
2111   // General insertion.
2112   APInt i260(260, UINT64_MAX, true);
2113   i260.insertBits(APInt(129, 1ull << 48), 15);
2114   EXPECT_EQ(i260.extractBitsAsZExtValue(64, 0), 0x8000000000007FFFull);
2115   EXPECT_EQ(i260.extractBitsAsZExtValue(64, 64), 0x0000000000000000ull);
2116   EXPECT_EQ(i260.extractBitsAsZExtValue(64, 128), 0xFFFFFFFFFFFF0000ull);
2117   EXPECT_EQ(i260.extractBitsAsZExtValue(64, 192), 0xFFFFFFFFFFFFFFFFull);
2118   EXPECT_EQ(i260.extractBitsAsZExtValue(4, 256), 0x000000000000000Full);
2119 }
2120 
2121 TEST(APIntTest, extractBits) {
2122   APInt i32(32, 0x1234567);
2123   EXPECT_EQ(0x3456, i32.extractBits(16, 4));
2124 
2125   APInt i64(64, 0x01234567FFFFFFFFull);
2126   EXPECT_EQ(0xFFFFFFFF, i64.extractBits(32, 0));
2127   EXPECT_EQ(0xFFFFFFFF, i64.trunc(32));
2128   EXPECT_EQ(0x01234567, i64.extractBits(32, 32));
2129   EXPECT_EQ(0x01234567, i64.lshr(32).trunc(32));
2130 
2131   APInt i257(257, 0xFFFFFFFFFF0000FFull, true);
2132   EXPECT_EQ(0xFFu, i257.extractBits(16, 0));
2133   EXPECT_EQ(0xFFu, i257.lshr(0).trunc(16));
2134   EXPECT_EQ((0xFFu >> 1), i257.extractBits(16, 1));
2135   EXPECT_EQ((0xFFu >> 1), i257.lshr(1).trunc(16));
2136   EXPECT_EQ(-1, i257.extractBits(32, 64).getSExtValue());
2137   EXPECT_EQ(-1, i257.lshr(64).trunc(32).getSExtValue());
2138   EXPECT_EQ(-1, i257.extractBits(128, 128).getSExtValue());
2139   EXPECT_EQ(-1, i257.lshr(128).trunc(128).getSExtValue());
2140   EXPECT_EQ(-1, i257.extractBits(66, 191).getSExtValue());
2141   EXPECT_EQ(-1, i257.lshr(191).trunc(66).getSExtValue());
2142   EXPECT_EQ(static_cast<int64_t>(0xFFFFFFFFFF80007Full),
2143             i257.extractBits(128, 1).getSExtValue());
2144   EXPECT_EQ(static_cast<int64_t>(0xFFFFFFFFFF80007Full),
2145             i257.lshr(1).trunc(128).getSExtValue());
2146   EXPECT_EQ(static_cast<int64_t>(0xFFFFFFFFFF80007Full),
2147             i257.extractBits(129, 1).getSExtValue());
2148   EXPECT_EQ(static_cast<int64_t>(0xFFFFFFFFFF80007Full),
2149             i257.lshr(1).trunc(129).getSExtValue());
2150 
2151   EXPECT_EQ(APInt(48, 0),
2152             APInt(144, "281474976710655", 10).extractBits(48, 48));
2153   EXPECT_EQ(APInt(48, 0),
2154             APInt(144, "281474976710655", 10).lshr(48).trunc(48));
2155   EXPECT_EQ(APInt(48, 0x0000ffffffffffffull),
2156             APInt(144, "281474976710655", 10).extractBits(48, 0));
2157   EXPECT_EQ(APInt(48, 0x0000ffffffffffffull),
2158             APInt(144, "281474976710655", 10).lshr(0).trunc(48));
2159   EXPECT_EQ(APInt(48, 0x00007fffffffffffull),
2160             APInt(144, "281474976710655", 10).extractBits(48, 1));
2161   EXPECT_EQ(APInt(48, 0x00007fffffffffffull),
2162             APInt(144, "281474976710655", 10).lshr(1).trunc(48));
2163 }
2164 
2165 TEST(APIntTest, extractBitsAsZExtValue) {
2166   // Tests based on extractBits
2167   APInt i32(32, 0x1234567);
2168   EXPECT_EQ(0x3456u, i32.extractBitsAsZExtValue(16, 4));
2169 
2170   APInt i257(257, 0xFFFFFFFFFF0000FFull, true);
2171   EXPECT_EQ(0xFFu, i257.extractBitsAsZExtValue(16, 0));
2172   EXPECT_EQ((0xFFu >> 1), i257.extractBitsAsZExtValue(16, 1));
2173   EXPECT_EQ(0xFFFFFFFFull, i257.extractBitsAsZExtValue(32, 64));
2174   EXPECT_EQ(0xFFFFFFFFFFFFFFFFull, i257.extractBitsAsZExtValue(64, 128));
2175   EXPECT_EQ(0xFFFFFFFFFFFFFFFFull, i257.extractBitsAsZExtValue(64, 192));
2176   EXPECT_EQ(0xFFFFFFFFFFFFFFFFull, i257.extractBitsAsZExtValue(64, 191));
2177   EXPECT_EQ(0x3u, i257.extractBitsAsZExtValue(2, 255));
2178   EXPECT_EQ(0xFFFFFFFFFF80007Full, i257.extractBitsAsZExtValue(64, 1));
2179   EXPECT_EQ(0xFFFFFFFFFFFFFFFFull, i257.extractBitsAsZExtValue(64, 65));
2180   EXPECT_EQ(0xFFFFFFFFFF80007Full, i257.extractBitsAsZExtValue(64, 1));
2181   EXPECT_EQ(0xFFFFFFFFFFFFFFFFull, i257.extractBitsAsZExtValue(64, 65));
2182   EXPECT_EQ(0x1ull, i257.extractBitsAsZExtValue(1, 129));
2183 
2184   EXPECT_EQ(APInt(48, 0),
2185             APInt(144, "281474976710655", 10).extractBitsAsZExtValue(48, 48));
2186   EXPECT_EQ(APInt(48, 0x0000ffffffffffffull),
2187             APInt(144, "281474976710655", 10).extractBitsAsZExtValue(48, 0));
2188   EXPECT_EQ(APInt(48, 0x00007fffffffffffull),
2189             APInt(144, "281474976710655", 10).extractBitsAsZExtValue(48, 1));
2190 }
2191 
2192 TEST(APIntTest, getLowBitsSet) {
2193   APInt i128lo64 = APInt::getLowBitsSet(128, 64);
2194   EXPECT_EQ(0u, i128lo64.countl_one());
2195   EXPECT_EQ(64u, i128lo64.countl_zero());
2196   EXPECT_EQ(64u, i128lo64.getActiveBits());
2197   EXPECT_EQ(0u, i128lo64.countr_zero());
2198   EXPECT_EQ(64u, i128lo64.countr_one());
2199   EXPECT_EQ(64u, i128lo64.popcount());
2200 }
2201 
2202 TEST(APIntTest, getBitsSet) {
2203   APInt i64hi1lo1 = APInt::getBitsSet(64, 1, 63);
2204   EXPECT_EQ(0u, i64hi1lo1.countl_one());
2205   EXPECT_EQ(1u, i64hi1lo1.countl_zero());
2206   EXPECT_EQ(63u, i64hi1lo1.getActiveBits());
2207   EXPECT_EQ(1u, i64hi1lo1.countr_zero());
2208   EXPECT_EQ(0u, i64hi1lo1.countr_one());
2209   EXPECT_EQ(62u, i64hi1lo1.popcount());
2210 
2211   APInt i127hi1lo1 = APInt::getBitsSet(127, 1, 126);
2212   EXPECT_EQ(0u, i127hi1lo1.countl_one());
2213   EXPECT_EQ(1u, i127hi1lo1.countl_zero());
2214   EXPECT_EQ(126u, i127hi1lo1.getActiveBits());
2215   EXPECT_EQ(1u, i127hi1lo1.countr_zero());
2216   EXPECT_EQ(0u, i127hi1lo1.countr_one());
2217   EXPECT_EQ(125u, i127hi1lo1.popcount());
2218 }
2219 
2220 TEST(APIntTest, getBitsSetWithWrap) {
2221   APInt i64hi1lo1 = APInt::getBitsSetWithWrap(64, 1, 63);
2222   EXPECT_EQ(0u, i64hi1lo1.countl_one());
2223   EXPECT_EQ(1u, i64hi1lo1.countl_zero());
2224   EXPECT_EQ(63u, i64hi1lo1.getActiveBits());
2225   EXPECT_EQ(1u, i64hi1lo1.countr_zero());
2226   EXPECT_EQ(0u, i64hi1lo1.countr_one());
2227   EXPECT_EQ(62u, i64hi1lo1.popcount());
2228 
2229   APInt i127hi1lo1 = APInt::getBitsSetWithWrap(127, 1, 126);
2230   EXPECT_EQ(0u, i127hi1lo1.countl_one());
2231   EXPECT_EQ(1u, i127hi1lo1.countl_zero());
2232   EXPECT_EQ(126u, i127hi1lo1.getActiveBits());
2233   EXPECT_EQ(1u, i127hi1lo1.countr_zero());
2234   EXPECT_EQ(0u, i127hi1lo1.countr_one());
2235   EXPECT_EQ(125u, i127hi1lo1.popcount());
2236 
2237   APInt i64hi1lo1wrap = APInt::getBitsSetWithWrap(64, 63, 1);
2238   EXPECT_EQ(1u, i64hi1lo1wrap.countl_one());
2239   EXPECT_EQ(0u, i64hi1lo1wrap.countl_zero());
2240   EXPECT_EQ(64u, i64hi1lo1wrap.getActiveBits());
2241   EXPECT_EQ(0u, i64hi1lo1wrap.countr_zero());
2242   EXPECT_EQ(1u, i64hi1lo1wrap.countr_one());
2243   EXPECT_EQ(2u, i64hi1lo1wrap.popcount());
2244 
2245   APInt i127hi1lo1wrap = APInt::getBitsSetWithWrap(127, 126, 1);
2246   EXPECT_EQ(1u, i127hi1lo1wrap.countl_one());
2247   EXPECT_EQ(0u, i127hi1lo1wrap.countl_zero());
2248   EXPECT_EQ(127u, i127hi1lo1wrap.getActiveBits());
2249   EXPECT_EQ(0u, i127hi1lo1wrap.countr_zero());
2250   EXPECT_EQ(1u, i127hi1lo1wrap.countr_one());
2251   EXPECT_EQ(2u, i127hi1lo1wrap.popcount());
2252 
2253   APInt i32hiequallowrap = APInt::getBitsSetWithWrap(32, 10, 10);
2254   EXPECT_EQ(32u, i32hiequallowrap.countl_one());
2255   EXPECT_EQ(0u, i32hiequallowrap.countl_zero());
2256   EXPECT_EQ(32u, i32hiequallowrap.getActiveBits());
2257   EXPECT_EQ(0u, i32hiequallowrap.countr_zero());
2258   EXPECT_EQ(32u, i32hiequallowrap.countr_one());
2259   EXPECT_EQ(32u, i32hiequallowrap.popcount());
2260 }
2261 
2262 TEST(APIntTest, getHighBitsSet) {
2263   APInt i64hi32 = APInt::getHighBitsSet(64, 32);
2264   EXPECT_EQ(32u, i64hi32.countl_one());
2265   EXPECT_EQ(0u, i64hi32.countl_zero());
2266   EXPECT_EQ(64u, i64hi32.getActiveBits());
2267   EXPECT_EQ(32u, i64hi32.countr_zero());
2268   EXPECT_EQ(0u, i64hi32.countr_one());
2269   EXPECT_EQ(32u, i64hi32.popcount());
2270 }
2271 
2272 TEST(APIntTest, getBitsSetFrom) {
2273   APInt i64hi31 = APInt::getBitsSetFrom(64, 33);
2274   EXPECT_EQ(31u, i64hi31.countl_one());
2275   EXPECT_EQ(0u, i64hi31.countl_zero());
2276   EXPECT_EQ(64u, i64hi31.getActiveBits());
2277   EXPECT_EQ(33u, i64hi31.countr_zero());
2278   EXPECT_EQ(0u, i64hi31.countr_one());
2279   EXPECT_EQ(31u, i64hi31.popcount());
2280 }
2281 
2282 TEST(APIntTest, setLowBits) {
2283   APInt i64lo32(64, 0);
2284   i64lo32.setLowBits(32);
2285   EXPECT_EQ(0u, i64lo32.countl_one());
2286   EXPECT_EQ(32u, i64lo32.countl_zero());
2287   EXPECT_EQ(32u, i64lo32.getActiveBits());
2288   EXPECT_EQ(0u, i64lo32.countr_zero());
2289   EXPECT_EQ(32u, i64lo32.countr_one());
2290   EXPECT_EQ(32u, i64lo32.popcount());
2291 
2292   APInt i128lo64(128, 0);
2293   i128lo64.setLowBits(64);
2294   EXPECT_EQ(0u, i128lo64.countl_one());
2295   EXPECT_EQ(64u, i128lo64.countl_zero());
2296   EXPECT_EQ(64u, i128lo64.getActiveBits());
2297   EXPECT_EQ(0u, i128lo64.countr_zero());
2298   EXPECT_EQ(64u, i128lo64.countr_one());
2299   EXPECT_EQ(64u, i128lo64.popcount());
2300 
2301   APInt i128lo24(128, 0);
2302   i128lo24.setLowBits(24);
2303   EXPECT_EQ(0u, i128lo24.countl_one());
2304   EXPECT_EQ(104u, i128lo24.countl_zero());
2305   EXPECT_EQ(24u, i128lo24.getActiveBits());
2306   EXPECT_EQ(0u, i128lo24.countr_zero());
2307   EXPECT_EQ(24u, i128lo24.countr_one());
2308   EXPECT_EQ(24u, i128lo24.popcount());
2309 
2310   APInt i128lo104(128, 0);
2311   i128lo104.setLowBits(104);
2312   EXPECT_EQ(0u, i128lo104.countl_one());
2313   EXPECT_EQ(24u, i128lo104.countl_zero());
2314   EXPECT_EQ(104u, i128lo104.getActiveBits());
2315   EXPECT_EQ(0u, i128lo104.countr_zero());
2316   EXPECT_EQ(104u, i128lo104.countr_one());
2317   EXPECT_EQ(104u, i128lo104.popcount());
2318 
2319   APInt i128lo0(128, 0);
2320   i128lo0.setLowBits(0);
2321   EXPECT_EQ(0u, i128lo0.countl_one());
2322   EXPECT_EQ(128u, i128lo0.countl_zero());
2323   EXPECT_EQ(0u, i128lo0.getActiveBits());
2324   EXPECT_EQ(128u, i128lo0.countr_zero());
2325   EXPECT_EQ(0u, i128lo0.countr_one());
2326   EXPECT_EQ(0u, i128lo0.popcount());
2327 
2328   APInt i80lo79(80, 0);
2329   i80lo79.setLowBits(79);
2330   EXPECT_EQ(0u, i80lo79.countl_one());
2331   EXPECT_EQ(1u, i80lo79.countl_zero());
2332   EXPECT_EQ(79u, i80lo79.getActiveBits());
2333   EXPECT_EQ(0u, i80lo79.countr_zero());
2334   EXPECT_EQ(79u, i80lo79.countr_one());
2335   EXPECT_EQ(79u, i80lo79.popcount());
2336 }
2337 
2338 TEST(APIntTest, setHighBits) {
2339   APInt i64hi32(64, 0);
2340   i64hi32.setHighBits(32);
2341   EXPECT_EQ(32u, i64hi32.countl_one());
2342   EXPECT_EQ(0u, i64hi32.countl_zero());
2343   EXPECT_EQ(64u, i64hi32.getActiveBits());
2344   EXPECT_EQ(32u, i64hi32.countr_zero());
2345   EXPECT_EQ(0u, i64hi32.countr_one());
2346   EXPECT_EQ(32u, i64hi32.popcount());
2347 
2348   APInt i128hi64(128, 0);
2349   i128hi64.setHighBits(64);
2350   EXPECT_EQ(64u, i128hi64.countl_one());
2351   EXPECT_EQ(0u, i128hi64.countl_zero());
2352   EXPECT_EQ(128u, i128hi64.getActiveBits());
2353   EXPECT_EQ(64u, i128hi64.countr_zero());
2354   EXPECT_EQ(0u, i128hi64.countr_one());
2355   EXPECT_EQ(64u, i128hi64.popcount());
2356 
2357   APInt i128hi24(128, 0);
2358   i128hi24.setHighBits(24);
2359   EXPECT_EQ(24u, i128hi24.countl_one());
2360   EXPECT_EQ(0u, i128hi24.countl_zero());
2361   EXPECT_EQ(128u, i128hi24.getActiveBits());
2362   EXPECT_EQ(104u, i128hi24.countr_zero());
2363   EXPECT_EQ(0u, i128hi24.countr_one());
2364   EXPECT_EQ(24u, i128hi24.popcount());
2365 
2366   APInt i128hi104(128, 0);
2367   i128hi104.setHighBits(104);
2368   EXPECT_EQ(104u, i128hi104.countl_one());
2369   EXPECT_EQ(0u, i128hi104.countl_zero());
2370   EXPECT_EQ(128u, i128hi104.getActiveBits());
2371   EXPECT_EQ(24u, i128hi104.countr_zero());
2372   EXPECT_EQ(0u, i128hi104.countr_one());
2373   EXPECT_EQ(104u, i128hi104.popcount());
2374 
2375   APInt i128hi0(128, 0);
2376   i128hi0.setHighBits(0);
2377   EXPECT_EQ(0u, i128hi0.countl_one());
2378   EXPECT_EQ(128u, i128hi0.countl_zero());
2379   EXPECT_EQ(0u, i128hi0.getActiveBits());
2380   EXPECT_EQ(128u, i128hi0.countr_zero());
2381   EXPECT_EQ(0u, i128hi0.countr_one());
2382   EXPECT_EQ(0u, i128hi0.popcount());
2383 
2384   APInt i80hi1(80, 0);
2385   i80hi1.setHighBits(1);
2386   EXPECT_EQ(1u, i80hi1.countl_one());
2387   EXPECT_EQ(0u, i80hi1.countl_zero());
2388   EXPECT_EQ(80u, i80hi1.getActiveBits());
2389   EXPECT_EQ(79u, i80hi1.countr_zero());
2390   EXPECT_EQ(0u, i80hi1.countr_one());
2391   EXPECT_EQ(1u, i80hi1.popcount());
2392 
2393   APInt i32hi16(32, 0);
2394   i32hi16.setHighBits(16);
2395   EXPECT_EQ(16u, i32hi16.countl_one());
2396   EXPECT_EQ(0u, i32hi16.countl_zero());
2397   EXPECT_EQ(32u, i32hi16.getActiveBits());
2398   EXPECT_EQ(16u, i32hi16.countr_zero());
2399   EXPECT_EQ(0u, i32hi16.countr_one());
2400   EXPECT_EQ(16u, i32hi16.popcount());
2401 }
2402 
2403 TEST(APIntTest, setBitsFrom) {
2404   APInt i64from63(64, 0);
2405   i64from63.setBitsFrom(63);
2406   EXPECT_EQ(1u, i64from63.countl_one());
2407   EXPECT_EQ(0u, i64from63.countl_zero());
2408   EXPECT_EQ(64u, i64from63.getActiveBits());
2409   EXPECT_EQ(63u, i64from63.countr_zero());
2410   EXPECT_EQ(0u, i64from63.countr_one());
2411   EXPECT_EQ(1u, i64from63.popcount());
2412 }
2413 
2414 TEST(APIntTest, setAllBits) {
2415   APInt i32(32, 0);
2416   i32.setAllBits();
2417   EXPECT_EQ(32u, i32.countl_one());
2418   EXPECT_EQ(0u, i32.countl_zero());
2419   EXPECT_EQ(32u, i32.getActiveBits());
2420   EXPECT_EQ(0u, i32.countr_zero());
2421   EXPECT_EQ(32u, i32.countr_one());
2422   EXPECT_EQ(32u, i32.popcount());
2423 
2424   APInt i64(64, 0);
2425   i64.setAllBits();
2426   EXPECT_EQ(64u, i64.countl_one());
2427   EXPECT_EQ(0u, i64.countl_zero());
2428   EXPECT_EQ(64u, i64.getActiveBits());
2429   EXPECT_EQ(0u, i64.countr_zero());
2430   EXPECT_EQ(64u, i64.countr_one());
2431   EXPECT_EQ(64u, i64.popcount());
2432 
2433   APInt i96(96, 0);
2434   i96.setAllBits();
2435   EXPECT_EQ(96u, i96.countl_one());
2436   EXPECT_EQ(0u, i96.countl_zero());
2437   EXPECT_EQ(96u, i96.getActiveBits());
2438   EXPECT_EQ(0u, i96.countr_zero());
2439   EXPECT_EQ(96u, i96.countr_one());
2440   EXPECT_EQ(96u, i96.popcount());
2441 
2442   APInt i128(128, 0);
2443   i128.setAllBits();
2444   EXPECT_EQ(128u, i128.countl_one());
2445   EXPECT_EQ(0u, i128.countl_zero());
2446   EXPECT_EQ(128u, i128.getActiveBits());
2447   EXPECT_EQ(0u, i128.countr_zero());
2448   EXPECT_EQ(128u, i128.countr_one());
2449   EXPECT_EQ(128u, i128.popcount());
2450 }
2451 
2452 TEST(APIntTest, getLoBits) {
2453   APInt i32(32, 0xfa);
2454   i32.setHighBits(1);
2455   EXPECT_EQ(0xa, i32.getLoBits(4));
2456   APInt i128(128, 0xfa);
2457   i128.setHighBits(1);
2458   EXPECT_EQ(0xa, i128.getLoBits(4));
2459 }
2460 
2461 TEST(APIntTest, getHiBits) {
2462   APInt i32(32, 0xfa);
2463   i32.setHighBits(2);
2464   EXPECT_EQ(0xc, i32.getHiBits(4));
2465   APInt i128(128, 0xfa);
2466   i128.setHighBits(2);
2467   EXPECT_EQ(0xc, i128.getHiBits(4));
2468 }
2469 
2470 TEST(APIntTest, clearLowBits) {
2471   APInt i64hi32 = APInt::getAllOnes(64);
2472   i64hi32.clearLowBits(32);
2473   EXPECT_EQ(32u, i64hi32.countl_one());
2474   EXPECT_EQ(0u, i64hi32.countl_zero());
2475   EXPECT_EQ(64u, i64hi32.getActiveBits());
2476   EXPECT_EQ(32u, i64hi32.countr_zero());
2477   EXPECT_EQ(0u, i64hi32.countr_one());
2478   EXPECT_EQ(32u, i64hi32.popcount());
2479 
2480   APInt i128hi64 = APInt::getAllOnes(128);
2481   i128hi64.clearLowBits(64);
2482   EXPECT_EQ(64u, i128hi64.countl_one());
2483   EXPECT_EQ(0u, i128hi64.countl_zero());
2484   EXPECT_EQ(128u, i128hi64.getActiveBits());
2485   EXPECT_EQ(64u, i128hi64.countr_zero());
2486   EXPECT_EQ(0u, i128hi64.countr_one());
2487   EXPECT_EQ(64u, i128hi64.popcount());
2488 
2489   APInt i128hi24 = APInt::getAllOnes(128);
2490   i128hi24.clearLowBits(104);
2491   EXPECT_EQ(24u, i128hi24.countl_one());
2492   EXPECT_EQ(0u, i128hi24.countl_zero());
2493   EXPECT_EQ(128u, i128hi24.getActiveBits());
2494   EXPECT_EQ(104u, i128hi24.countr_zero());
2495   EXPECT_EQ(0u, i128hi24.countr_one());
2496   EXPECT_EQ(24u, i128hi24.popcount());
2497 
2498   APInt i128hi104 = APInt::getAllOnes(128);
2499   i128hi104.clearLowBits(24);
2500   EXPECT_EQ(104u, i128hi104.countl_one());
2501   EXPECT_EQ(0u, i128hi104.countl_zero());
2502   EXPECT_EQ(128u, i128hi104.getActiveBits());
2503   EXPECT_EQ(24u, i128hi104.countr_zero());
2504   EXPECT_EQ(0u, i128hi104.countr_one());
2505   EXPECT_EQ(104u, i128hi104.popcount());
2506 
2507   APInt i128hi0 = APInt::getAllOnes(128);
2508   i128hi0.clearLowBits(128);
2509   EXPECT_EQ(0u, i128hi0.countl_one());
2510   EXPECT_EQ(128u, i128hi0.countl_zero());
2511   EXPECT_EQ(0u, i128hi0.getActiveBits());
2512   EXPECT_EQ(128u, i128hi0.countr_zero());
2513   EXPECT_EQ(0u, i128hi0.countr_one());
2514   EXPECT_EQ(0u, i128hi0.popcount());
2515 
2516   APInt i80hi1 = APInt::getAllOnes(80);
2517   i80hi1.clearLowBits(79);
2518   EXPECT_EQ(1u, i80hi1.countl_one());
2519   EXPECT_EQ(0u, i80hi1.countl_zero());
2520   EXPECT_EQ(80u, i80hi1.getActiveBits());
2521   EXPECT_EQ(79u, i80hi1.countr_zero());
2522   EXPECT_EQ(0u, i80hi1.countr_one());
2523   EXPECT_EQ(1u, i80hi1.popcount());
2524 
2525   APInt i32hi16 = APInt::getAllOnes(32);
2526   i32hi16.clearLowBits(16);
2527   EXPECT_EQ(16u, i32hi16.countl_one());
2528   EXPECT_EQ(0u, i32hi16.countl_zero());
2529   EXPECT_EQ(32u, i32hi16.getActiveBits());
2530   EXPECT_EQ(16u, i32hi16.countr_zero());
2531   EXPECT_EQ(0u, i32hi16.countr_one());
2532   EXPECT_EQ(16u, i32hi16.popcount());
2533 }
2534 
2535 TEST(APIntTest, AbsDiff) {
2536   using APIntOps::absdiff;
2537 
2538   APInt MaxU1(1, 1, false);
2539   APInt MinU1(1, 0, false);
2540   EXPECT_EQ(1u, absdiff(MaxU1, MinU1).getZExtValue());
2541   EXPECT_EQ(1u, absdiff(MinU1, MaxU1).getZExtValue());
2542 
2543   APInt MaxU4(4, 15, false);
2544   APInt MinU4(4, 0, false);
2545   EXPECT_EQ(15u, absdiff(MaxU4, MinU4).getZExtValue());
2546   EXPECT_EQ(15u, absdiff(MinU4, MaxU4).getZExtValue());
2547 
2548   APInt MaxS8(8, 127, true);
2549   APInt MinS8(8, -128, true);
2550   EXPECT_EQ(1u, absdiff(MaxS8, MinS8).getZExtValue());
2551   EXPECT_EQ(1u, absdiff(MinS8, MaxS8).getZExtValue());
2552 
2553   APInt MaxU16(16, 65535, false);
2554   APInt MinU16(16, 0, false);
2555   EXPECT_EQ(65535u, absdiff(MaxU16, MinU16).getZExtValue());
2556   EXPECT_EQ(65535u, absdiff(MinU16, MaxU16).getZExtValue());
2557 
2558   APInt MaxS16(16, 32767, true);
2559   APInt MinS16(16, -32768, true);
2560   APInt ZeroS16(16, 0, true);
2561   EXPECT_EQ(1u, absdiff(MaxS16, MinS16).getZExtValue());
2562   EXPECT_EQ(1u, absdiff(MinS16, MaxS16).getZExtValue());
2563   EXPECT_EQ(32768u, absdiff(ZeroS16, MinS16));
2564   EXPECT_EQ(32768u, absdiff(MinS16, ZeroS16));
2565   EXPECT_EQ(32767u, absdiff(ZeroS16, MaxS16));
2566   EXPECT_EQ(32767u, absdiff(MaxS16, ZeroS16));
2567 }
2568 
2569 TEST(APIntTest, GCD) {
2570   using APIntOps::GreatestCommonDivisor;
2571 
2572   for (unsigned Bits : {1, 2, 32, 63, 64, 65}) {
2573     // Test some corner cases near zero.
2574     APInt Zero(Bits, 0), One(Bits, 1);
2575     EXPECT_EQ(GreatestCommonDivisor(Zero, Zero), Zero);
2576     EXPECT_EQ(GreatestCommonDivisor(Zero, One), One);
2577     EXPECT_EQ(GreatestCommonDivisor(One, Zero), One);
2578     EXPECT_EQ(GreatestCommonDivisor(One, One), One);
2579 
2580     if (Bits > 1) {
2581       APInt Two(Bits, 2);
2582       EXPECT_EQ(GreatestCommonDivisor(Zero, Two), Two);
2583       EXPECT_EQ(GreatestCommonDivisor(One, Two), One);
2584       EXPECT_EQ(GreatestCommonDivisor(Two, Two), Two);
2585 
2586       // Test some corner cases near the highest representable value.
2587       APInt Max(Bits, 0);
2588       Max.setAllBits();
2589       EXPECT_EQ(GreatestCommonDivisor(Zero, Max), Max);
2590       EXPECT_EQ(GreatestCommonDivisor(One, Max), One);
2591       EXPECT_EQ(GreatestCommonDivisor(Two, Max), One);
2592       EXPECT_EQ(GreatestCommonDivisor(Max, Max), Max);
2593 
2594       APInt MaxOver2 = Max.udiv(Two);
2595       EXPECT_EQ(GreatestCommonDivisor(MaxOver2, Max), One);
2596       // Max - 1 == Max / 2 * 2, because Max is odd.
2597       EXPECT_EQ(GreatestCommonDivisor(MaxOver2, Max - 1), MaxOver2);
2598     }
2599   }
2600 
2601   // Compute the 20th Mersenne prime.
2602   const unsigned BitWidth = 4450;
2603   APInt HugePrime = APInt::getLowBitsSet(BitWidth, 4423);
2604 
2605   // 9931 and 123456 are coprime.
2606   APInt A = HugePrime * APInt(BitWidth, 9931);
2607   APInt B = HugePrime * APInt(BitWidth, 123456);
2608   APInt C = GreatestCommonDivisor(A, B);
2609   EXPECT_EQ(C, HugePrime);
2610 }
2611 
2612 TEST(APIntTest, LogicalRightShift) {
2613   APInt i256(APInt::getHighBitsSet(256, 2));
2614 
2615   i256.lshrInPlace(1);
2616   EXPECT_EQ(1U, i256.countl_zero());
2617   EXPECT_EQ(253U, i256.countr_zero());
2618   EXPECT_EQ(2U, i256.popcount());
2619 
2620   i256.lshrInPlace(62);
2621   EXPECT_EQ(63U, i256.countl_zero());
2622   EXPECT_EQ(191U, i256.countr_zero());
2623   EXPECT_EQ(2U, i256.popcount());
2624 
2625   i256.lshrInPlace(65);
2626   EXPECT_EQ(128U, i256.countl_zero());
2627   EXPECT_EQ(126U, i256.countr_zero());
2628   EXPECT_EQ(2U, i256.popcount());
2629 
2630   i256.lshrInPlace(64);
2631   EXPECT_EQ(192U, i256.countl_zero());
2632   EXPECT_EQ(62U, i256.countr_zero());
2633   EXPECT_EQ(2U, i256.popcount());
2634 
2635   i256.lshrInPlace(63);
2636   EXPECT_EQ(255U, i256.countl_zero());
2637   EXPECT_EQ(0U, i256.countr_zero());
2638   EXPECT_EQ(1U, i256.popcount());
2639 
2640   // Ensure we handle large shifts of multi-word.
2641   const APInt neg_one(128, static_cast<uint64_t>(-1), true);
2642   EXPECT_EQ(0, neg_one.lshr(128));
2643 }
2644 
2645 TEST(APIntTest, ArithmeticRightShift) {
2646   APInt i72(APInt::getHighBitsSet(72, 1));
2647   i72.ashrInPlace(46);
2648   EXPECT_EQ(47U, i72.countl_one());
2649   EXPECT_EQ(25U, i72.countr_zero());
2650   EXPECT_EQ(47U, i72.popcount());
2651 
2652   i72 = APInt::getHighBitsSet(72, 1);
2653   i72.ashrInPlace(64);
2654   EXPECT_EQ(65U, i72.countl_one());
2655   EXPECT_EQ(7U, i72.countr_zero());
2656   EXPECT_EQ(65U, i72.popcount());
2657 
2658   APInt i128(APInt::getHighBitsSet(128, 1));
2659   i128.ashrInPlace(64);
2660   EXPECT_EQ(65U, i128.countl_one());
2661   EXPECT_EQ(63U, i128.countr_zero());
2662   EXPECT_EQ(65U, i128.popcount());
2663 
2664   // Ensure we handle large shifts of multi-word.
2665   const APInt signmin32(APInt::getSignedMinValue(32));
2666   EXPECT_TRUE(signmin32.ashr(32).isAllOnes());
2667 
2668   // Ensure we handle large shifts of multi-word.
2669   const APInt umax32(APInt::getSignedMaxValue(32));
2670   EXPECT_EQ(0, umax32.ashr(32));
2671 
2672   // Ensure we handle large shifts of multi-word.
2673   const APInt signmin128(APInt::getSignedMinValue(128));
2674   EXPECT_TRUE(signmin128.ashr(128).isAllOnes());
2675 
2676   // Ensure we handle large shifts of multi-word.
2677   const APInt umax128(APInt::getSignedMaxValue(128));
2678   EXPECT_EQ(0, umax128.ashr(128));
2679 }
2680 
2681 TEST(APIntTest, LeftShift) {
2682   APInt i256(APInt::getLowBitsSet(256, 2));
2683 
2684   i256 <<= 1;
2685   EXPECT_EQ(253U, i256.countl_zero());
2686   EXPECT_EQ(1U, i256.countr_zero());
2687   EXPECT_EQ(2U, i256.popcount());
2688 
2689   i256 <<= 62;
2690   EXPECT_EQ(191U, i256.countl_zero());
2691   EXPECT_EQ(63U, i256.countr_zero());
2692   EXPECT_EQ(2U, i256.popcount());
2693 
2694   i256 <<= 65;
2695   EXPECT_EQ(126U, i256.countl_zero());
2696   EXPECT_EQ(128U, i256.countr_zero());
2697   EXPECT_EQ(2U, i256.popcount());
2698 
2699   i256 <<= 64;
2700   EXPECT_EQ(62U, i256.countl_zero());
2701   EXPECT_EQ(192U, i256.countr_zero());
2702   EXPECT_EQ(2U, i256.popcount());
2703 
2704   i256 <<= 63;
2705   EXPECT_EQ(0U, i256.countl_zero());
2706   EXPECT_EQ(255U, i256.countr_zero());
2707   EXPECT_EQ(1U, i256.popcount());
2708 
2709   // Ensure we handle large shifts of multi-word.
2710   const APInt neg_one(128, static_cast<uint64_t>(-1), true);
2711   EXPECT_EQ(0, neg_one.shl(128));
2712 }
2713 
2714 TEST(APIntTest, isSubsetOf) {
2715   APInt i32_1(32, 1);
2716   APInt i32_2(32, 2);
2717   APInt i32_3(32, 3);
2718   EXPECT_FALSE(i32_3.isSubsetOf(i32_1));
2719   EXPECT_TRUE(i32_1.isSubsetOf(i32_3));
2720   EXPECT_FALSE(i32_2.isSubsetOf(i32_1));
2721   EXPECT_FALSE(i32_1.isSubsetOf(i32_2));
2722   EXPECT_TRUE(i32_3.isSubsetOf(i32_3));
2723 
2724   APInt i128_1(128, 1);
2725   APInt i128_2(128, 2);
2726   APInt i128_3(128, 3);
2727   EXPECT_FALSE(i128_3.isSubsetOf(i128_1));
2728   EXPECT_TRUE(i128_1.isSubsetOf(i128_3));
2729   EXPECT_FALSE(i128_2.isSubsetOf(i128_1));
2730   EXPECT_FALSE(i128_1.isSubsetOf(i128_2));
2731   EXPECT_TRUE(i128_3.isSubsetOf(i128_3));
2732 
2733   i128_1 <<= 64;
2734   i128_2 <<= 64;
2735   i128_3 <<= 64;
2736   EXPECT_FALSE(i128_3.isSubsetOf(i128_1));
2737   EXPECT_TRUE(i128_1.isSubsetOf(i128_3));
2738   EXPECT_FALSE(i128_2.isSubsetOf(i128_1));
2739   EXPECT_FALSE(i128_1.isSubsetOf(i128_2));
2740   EXPECT_TRUE(i128_3.isSubsetOf(i128_3));
2741 }
2742 
2743 TEST(APIntTest, sext) {
2744   EXPECT_EQ(0, APInt(1, 0).sext(64));
2745   EXPECT_EQ(~uint64_t(0), APInt(1, 1).sext(64));
2746 
2747   APInt i32_max(APInt::getSignedMaxValue(32).sext(63));
2748   EXPECT_EQ(i32_max, i32_max.sext(63));
2749   EXPECT_EQ(32U, i32_max.countl_zero());
2750   EXPECT_EQ(0U, i32_max.countr_zero());
2751   EXPECT_EQ(31U, i32_max.popcount());
2752 
2753   APInt i32_min(APInt::getSignedMinValue(32).sext(63));
2754   EXPECT_EQ(i32_min, i32_min.sext(63));
2755   EXPECT_EQ(32U, i32_min.countl_one());
2756   EXPECT_EQ(31U, i32_min.countr_zero());
2757   EXPECT_EQ(32U, i32_min.popcount());
2758 
2759   APInt i32_neg1(APInt(32, ~uint64_t(0)).sext(63));
2760   EXPECT_EQ(i32_neg1, i32_neg1.sext(63));
2761   EXPECT_EQ(63U, i32_neg1.countl_one());
2762   EXPECT_EQ(0U, i32_neg1.countr_zero());
2763   EXPECT_EQ(63U, i32_neg1.popcount());
2764 }
2765 
2766 TEST(APIntTest, trunc) {
2767   APInt val(32, 0xFFFFFFFF);
2768   EXPECT_EQ(0xFFFF, val.trunc(16));
2769   EXPECT_EQ(0xFFFFFFFF, val.trunc(32));
2770 }
2771 
2772 TEST(APIntTest, concat) {
2773   APInt Int1(4, 0x1ULL);
2774   APInt Int3(4, 0x3ULL);
2775 
2776   EXPECT_EQ(0x31, Int3.concat(Int1));
2777   EXPECT_EQ(APInt(12, 0x313), Int3.concat(Int1).concat(Int3));
2778   EXPECT_EQ(APInt(16, 0x3313), Int3.concat(Int3).concat(Int1).concat(Int3));
2779 
2780   APInt I64(64, 0x3ULL);
2781   EXPECT_EQ(I64, I64.concat(I64).lshr(64).trunc(64));
2782 
2783   APInt I65(65, 0x3ULL);
2784   APInt I0 = APInt::getZeroWidth();
2785   EXPECT_EQ(I65, I65.concat(I0));
2786   EXPECT_EQ(I65, I0.concat(I65));
2787 }
2788 
2789 TEST(APIntTest, multiply) {
2790   APInt i64(64, 1234);
2791 
2792   EXPECT_EQ(7006652, i64 * 5678);
2793   EXPECT_EQ(7006652, 5678 * i64);
2794 
2795   APInt i128 = APInt::getOneBitSet(128, 64);
2796   APInt i128_1234(128, 1234);
2797   i128_1234 <<= 64;
2798   EXPECT_EQ(i128_1234, i128 * 1234);
2799   EXPECT_EQ(i128_1234, 1234 * i128);
2800 
2801   APInt i96 = APInt::getOneBitSet(96, 64);
2802   i96 *= ~0ULL;
2803   EXPECT_EQ(32U, i96.countl_one());
2804   EXPECT_EQ(32U, i96.popcount());
2805   EXPECT_EQ(64U, i96.countr_zero());
2806 }
2807 
2808 TEST(APIntTest, RoundingUDiv) {
2809   for (uint64_t Ai = 1; Ai <= 255; Ai++) {
2810     APInt A(8, Ai);
2811     APInt Zero(8, 0);
2812     EXPECT_EQ(0, APIntOps::RoundingUDiv(Zero, A, APInt::Rounding::UP));
2813     EXPECT_EQ(0, APIntOps::RoundingUDiv(Zero, A, APInt::Rounding::DOWN));
2814     EXPECT_EQ(0, APIntOps::RoundingUDiv(Zero, A, APInt::Rounding::TOWARD_ZERO));
2815 
2816     for (uint64_t Bi = 1; Bi <= 255; Bi++) {
2817       APInt B(8, Bi);
2818       {
2819         APInt Quo = APIntOps::RoundingUDiv(A, B, APInt::Rounding::UP);
2820         auto Prod = Quo.zext(16) * B.zext(16);
2821         EXPECT_TRUE(Prod.uge(Ai));
2822         if (Prod.ugt(Ai)) {
2823           EXPECT_TRUE(((Quo - 1).zext(16) * B.zext(16)).ult(Ai));
2824         }
2825       }
2826       {
2827         APInt Quo = A.udiv(B);
2828         EXPECT_EQ(Quo, APIntOps::RoundingUDiv(A, B, APInt::Rounding::TOWARD_ZERO));
2829         EXPECT_EQ(Quo, APIntOps::RoundingUDiv(A, B, APInt::Rounding::DOWN));
2830       }
2831     }
2832   }
2833 }
2834 
2835 TEST(APIntTest, RoundingSDiv) {
2836   for (int64_t Ai = -128; Ai <= 127; Ai++) {
2837     APInt A(8, Ai);
2838 
2839     if (Ai != 0) {
2840       APInt Zero(8, 0);
2841       EXPECT_EQ(0, APIntOps::RoundingSDiv(Zero, A, APInt::Rounding::UP));
2842       EXPECT_EQ(0, APIntOps::RoundingSDiv(Zero, A, APInt::Rounding::DOWN));
2843       EXPECT_EQ(0, APIntOps::RoundingSDiv(Zero, A, APInt::Rounding::TOWARD_ZERO));
2844     }
2845 
2846     for (int64_t Bi = -128; Bi <= 127; Bi++) {
2847       if (Bi == 0)
2848         continue;
2849 
2850       APInt B(8, Bi);
2851       APInt QuoTowardZero = A.sdiv(B);
2852       {
2853         APInt Quo = APIntOps::RoundingSDiv(A, B, APInt::Rounding::UP);
2854         if (A.srem(B).isZero()) {
2855           EXPECT_EQ(QuoTowardZero, Quo);
2856         } else if (A.isNegative() !=
2857                    B.isNegative()) { // if the math quotient is negative.
2858           EXPECT_EQ(QuoTowardZero, Quo);
2859         } else {
2860           EXPECT_EQ(QuoTowardZero + 1, Quo);
2861         }
2862       }
2863       {
2864         APInt Quo = APIntOps::RoundingSDiv(A, B, APInt::Rounding::DOWN);
2865         if (A.srem(B).isZero()) {
2866           EXPECT_EQ(QuoTowardZero, Quo);
2867         } else if (A.isNegative() !=
2868                    B.isNegative()) { // if the math quotient is negative.
2869           EXPECT_EQ(QuoTowardZero - 1, Quo);
2870         } else {
2871           EXPECT_EQ(QuoTowardZero, Quo);
2872         }
2873       }
2874       EXPECT_EQ(QuoTowardZero,
2875                 APIntOps::RoundingSDiv(A, B, APInt::Rounding::TOWARD_ZERO));
2876     }
2877   }
2878 }
2879 
2880 TEST(APIntTest, umul_ov) {
2881   const std::pair<uint64_t, uint64_t> Overflows[] = {
2882       {0x8000000000000000, 2},
2883       {0x5555555555555556, 3},
2884       {4294967296, 4294967296},
2885       {4294967295, 4294967298},
2886   };
2887   const std::pair<uint64_t, uint64_t> NonOverflows[] = {
2888       {0x7fffffffffffffff, 2},
2889       {0x5555555555555555, 3},
2890       {4294967295, 4294967297},
2891   };
2892 
2893   bool Overflow;
2894   for (auto &X : Overflows) {
2895     APInt A(64, X.first);
2896     APInt B(64, X.second);
2897     (void)A.umul_ov(B, Overflow);
2898     EXPECT_TRUE(Overflow);
2899   }
2900   for (auto &X : NonOverflows) {
2901     APInt A(64, X.first);
2902     APInt B(64, X.second);
2903     (void)A.umul_ov(B, Overflow);
2904     EXPECT_FALSE(Overflow);
2905   }
2906 
2907   for (unsigned Bits = 1; Bits <= 5; ++Bits)
2908     for (unsigned A = 0; A != 1u << Bits; ++A)
2909       for (unsigned B = 0; B != 1u << Bits; ++B) {
2910         APInt N1 = APInt(Bits, A), N2 = APInt(Bits, B);
2911         APInt Narrow = N1.umul_ov(N2, Overflow);
2912         APInt Wide = N1.zext(2 * Bits) * N2.zext(2 * Bits);
2913         EXPECT_EQ(Wide.trunc(Bits), Narrow);
2914         EXPECT_EQ(Narrow.zext(2 * Bits) != Wide, Overflow);
2915       }
2916 }
2917 
2918 TEST(APIntTest, smul_ov) {
2919   for (unsigned Bits = 1; Bits <= 5; ++Bits)
2920     for (unsigned A = 0; A != 1u << Bits; ++A)
2921       for (unsigned B = 0; B != 1u << Bits; ++B) {
2922         bool Overflow;
2923         APInt N1 = APInt(Bits, A), N2 = APInt(Bits, B);
2924         APInt Narrow = N1.smul_ov(N2, Overflow);
2925         APInt Wide = N1.sext(2 * Bits) * N2.sext(2 * Bits);
2926         EXPECT_EQ(Wide.trunc(Bits), Narrow);
2927         EXPECT_EQ(Narrow.sext(2 * Bits) != Wide, Overflow);
2928       }
2929 }
2930 
2931 TEST(APIntTest, SolveQuadraticEquationWrap) {
2932   // Verify that "Solution" is the first non-negative integer that solves
2933   // Ax^2 + Bx + C = "0 or overflow", i.e. that it is a correct solution
2934   // as calculated by SolveQuadraticEquationWrap.
2935   auto Validate = [] (int A, int B, int C, unsigned Width, int Solution) {
2936     int Mask = (1 << Width) - 1;
2937 
2938     // Solution should be non-negative.
2939     EXPECT_GE(Solution, 0);
2940 
2941     auto OverflowBits = [] (int64_t V, unsigned W) {
2942       return V & -(1 << W);
2943     };
2944 
2945     int64_t Over0 = OverflowBits(C, Width);
2946 
2947     auto IsZeroOrOverflow = [&] (int X) {
2948       int64_t ValueAtX = A*X*X + B*X + C;
2949       int64_t OverX = OverflowBits(ValueAtX, Width);
2950       return (ValueAtX & Mask) == 0 || OverX != Over0;
2951     };
2952 
2953     auto EquationToString = [&] (const char *X_str) {
2954       return (Twine(A) + Twine(X_str) + Twine("^2 + ") + Twine(B) +
2955               Twine(X_str) + Twine(" + ") + Twine(C) + Twine(", bitwidth: ") +
2956               Twine(Width)).str();
2957     };
2958 
2959     auto IsSolution = [&] (const char *X_str, int X) {
2960       if (IsZeroOrOverflow(X))
2961         return ::testing::AssertionSuccess()
2962                   << X << " is a solution of " << EquationToString(X_str);
2963       return ::testing::AssertionFailure()
2964                 << X << " is not an expected solution of "
2965                 << EquationToString(X_str);
2966     };
2967 
2968     auto IsNotSolution = [&] (const char *X_str, int X) {
2969       if (!IsZeroOrOverflow(X))
2970         return ::testing::AssertionSuccess()
2971                   << X << " is not a solution of " << EquationToString(X_str);
2972       return ::testing::AssertionFailure()
2973                 << X << " is an unexpected solution of "
2974                 << EquationToString(X_str);
2975     };
2976 
2977     // This is the important part: make sure that there is no solution that
2978     // is less than the calculated one.
2979     if (Solution > 0) {
2980       for (int X = 1; X < Solution-1; ++X)
2981         EXPECT_PRED_FORMAT1(IsNotSolution, X);
2982     }
2983 
2984     // Verify that the calculated solution is indeed a solution.
2985     EXPECT_PRED_FORMAT1(IsSolution, Solution);
2986   };
2987 
2988   // Generate all possible quadratic equations with Width-bit wide integer
2989   // coefficients, get the solution from SolveQuadraticEquationWrap, and
2990   // verify that the solution is correct.
2991   auto Iterate = [&] (unsigned Width) {
2992     assert(1 < Width && Width < 32);
2993     int Low = -(1 << (Width-1));
2994     int High = (1 << (Width-1));
2995 
2996     for (int A = Low; A != High; ++A) {
2997       if (A == 0)
2998         continue;
2999       for (int B = Low; B != High; ++B) {
3000         for (int C = Low; C != High; ++C) {
3001           std::optional<APInt> S = APIntOps::SolveQuadraticEquationWrap(
3002               APInt(Width, A), APInt(Width, B), APInt(Width, C), Width);
3003           if (S)
3004             Validate(A, B, C, Width, S->getSExtValue());
3005         }
3006       }
3007     }
3008   };
3009 
3010   // Test all widths in [2..6].
3011   for (unsigned i = 2; i <= 6; ++i)
3012     Iterate(i);
3013 }
3014 
3015 TEST(APIntTest, MultiplicativeInverseExaustive) {
3016   for (unsigned BitWidth = 1; BitWidth <= 16; ++BitWidth) {
3017     for (unsigned Value = 0; Value < (1u << BitWidth); ++Value) {
3018       APInt V = APInt(BitWidth, Value);
3019       APInt MulInv =
3020           V.zext(BitWidth + 1)
3021               .multiplicativeInverse(APInt::getSignedMinValue(BitWidth + 1))
3022               .trunc(BitWidth);
3023       APInt One = V * MulInv;
3024       if (!V.isZero() && V.countr_zero() == 0) {
3025         // Multiplicative inverse exists for all odd numbers.
3026         EXPECT_TRUE(One.isOne());
3027       } else {
3028         // Multiplicative inverse does not exist for even numbers (and 0).
3029         EXPECT_TRUE(MulInv.isZero());
3030       }
3031     }
3032   }
3033 }
3034 
3035 TEST(APIntTest, GetMostSignificantDifferentBit) {
3036   EXPECT_EQ(APIntOps::GetMostSignificantDifferentBit(APInt(8, 0), APInt(8, 0)),
3037             std::nullopt);
3038   EXPECT_EQ(
3039       APIntOps::GetMostSignificantDifferentBit(APInt(8, 42), APInt(8, 42)),
3040       std::nullopt);
3041   EXPECT_EQ(*APIntOps::GetMostSignificantDifferentBit(APInt(8, 0), APInt(8, 1)),
3042             0u);
3043   EXPECT_EQ(*APIntOps::GetMostSignificantDifferentBit(APInt(8, 0), APInt(8, 2)),
3044             1u);
3045   EXPECT_EQ(*APIntOps::GetMostSignificantDifferentBit(APInt(8, 0), APInt(8, 3)),
3046             1u);
3047   EXPECT_EQ(*APIntOps::GetMostSignificantDifferentBit(APInt(8, 1), APInt(8, 0)),
3048             0u);
3049   EXPECT_EQ(APIntOps::GetMostSignificantDifferentBit(APInt(8, 1), APInt(8, 1)),
3050             std::nullopt);
3051   EXPECT_EQ(*APIntOps::GetMostSignificantDifferentBit(APInt(8, 1), APInt(8, 2)),
3052             1u);
3053   EXPECT_EQ(*APIntOps::GetMostSignificantDifferentBit(APInt(8, 1), APInt(8, 3)),
3054             1u);
3055   EXPECT_EQ(
3056       *APIntOps::GetMostSignificantDifferentBit(APInt(8, 42), APInt(8, 112)),
3057       6u);
3058 }
3059 
3060 TEST(APIntTest, GetMostSignificantDifferentBitExaustive) {
3061   auto GetHighestDifferentBitBruteforce =
3062       [](const APInt &V0, const APInt &V1) -> std::optional<unsigned> {
3063     assert(V0.getBitWidth() == V1.getBitWidth() && "Must have same bitwidth");
3064     if (V0 == V1)
3065       return std::nullopt; // Bitwise identical.
3066     // There is a mismatch. Let's find the most significant different bit.
3067     for (int Bit = V0.getBitWidth() - 1; Bit >= 0; --Bit) {
3068       if (V0[Bit] == V1[Bit])
3069         continue;
3070       return Bit;
3071     }
3072     llvm_unreachable("Must have found bit mismatch.");
3073   };
3074 
3075   for (unsigned BitWidth = 1; BitWidth <= 8; ++BitWidth) {
3076     for (unsigned V0 = 0; V0 < (1u << BitWidth); ++V0) {
3077       for (unsigned V1 = 0; V1 < (1u << BitWidth); ++V1) {
3078         APInt A = APInt(BitWidth, V0);
3079         APInt B = APInt(BitWidth, V1);
3080 
3081         auto Bit = APIntOps::GetMostSignificantDifferentBit(A, B);
3082         EXPECT_EQ(Bit, GetHighestDifferentBitBruteforce(A, B));
3083 
3084         if (!Bit)
3085           EXPECT_EQ(A, B);
3086         else {
3087           EXPECT_NE(A, B);
3088           for (unsigned NumLowBits = 0; NumLowBits <= BitWidth; ++NumLowBits) {
3089             APInt Adash = A;
3090             Adash.clearLowBits(NumLowBits);
3091             APInt Bdash = B;
3092             Bdash.clearLowBits(NumLowBits);
3093             // Clearing only low bits up to and including *Bit is sufficient
3094             // to make values equal.
3095             if (NumLowBits >= 1 + *Bit)
3096               EXPECT_EQ(Adash, Bdash);
3097             else
3098               EXPECT_NE(Adash, Bdash);
3099           }
3100         }
3101       }
3102     }
3103   }
3104 }
3105 
3106 TEST(APIntTest, SignbitZeroChecks) {
3107   EXPECT_TRUE(APInt(8, -1).isNegative());
3108   EXPECT_FALSE(APInt(8, -1).isNonNegative());
3109   EXPECT_FALSE(APInt(8, -1).isStrictlyPositive());
3110   EXPECT_TRUE(APInt(8, -1).isNonPositive());
3111 
3112   EXPECT_FALSE(APInt(8, 0).isNegative());
3113   EXPECT_TRUE(APInt(8, 0).isNonNegative());
3114   EXPECT_FALSE(APInt(8, 0).isStrictlyPositive());
3115   EXPECT_TRUE(APInt(8, 0).isNonPositive());
3116 
3117   EXPECT_FALSE(APInt(8, 1).isNegative());
3118   EXPECT_TRUE(APInt(8, 1).isNonNegative());
3119   EXPECT_TRUE(APInt(8, 1).isStrictlyPositive());
3120   EXPECT_FALSE(APInt(8, 1).isNonPositive());
3121 }
3122 
3123 TEST(APIntTest, ZeroWidth) {
3124   // Zero width Constructors.
3125   auto ZW = APInt::getZeroWidth();
3126   EXPECT_EQ(0U, ZW.getBitWidth());
3127   EXPECT_EQ(0U, APInt(0, ArrayRef<uint64_t>({0, 1, 2})).getBitWidth());
3128   EXPECT_EQ(0U, APInt(0, "0", 10).getBitWidth());
3129 
3130   // Default constructor is single bit wide.
3131   EXPECT_EQ(1U, APInt().getBitWidth());
3132 
3133   // Copy ctor (move is down below).
3134   APInt ZW2(ZW);
3135   EXPECT_EQ(0U, ZW2.getBitWidth());
3136   // Assignment
3137   ZW = ZW2;
3138   EXPECT_EQ(0U, ZW.getBitWidth());
3139 
3140   // Methods like getLowBitsSet work with zero bits.
3141   EXPECT_EQ(0U, APInt::getLowBitsSet(0, 0).getBitWidth());
3142   EXPECT_EQ(0U, APInt::getSplat(0, ZW).getBitWidth());
3143   EXPECT_EQ(0U, APInt(4, 10).extractBits(0, 2).getBitWidth());
3144   EXPECT_EQ(0U, APInt(4, 10).extractBitsAsZExtValue(0, 2));
3145 
3146   // Logical operators.
3147   ZW |= ZW2;
3148   ZW &= ZW2;
3149   ZW ^= ZW2;
3150   ZW |= 42; // These ignore high bits of the literal.
3151   ZW &= 42;
3152   ZW ^= 42;
3153   EXPECT_EQ(1, ZW.isIntN(0));
3154 
3155   // Modulo Arithmetic.  Divide/Rem aren't defined on division by zero, so they
3156   // aren't supported.
3157   ZW += ZW2;
3158   ZW -= ZW2;
3159   ZW *= ZW2;
3160 
3161   // Logical Shifts and rotates, the amount must be <= bitwidth.
3162   ZW <<= 0;
3163   ZW.lshrInPlace(0);
3164   (void)ZW.rotl(0);
3165   (void)ZW.rotr(0);
3166 
3167   // Comparisons.
3168   EXPECT_EQ(1, ZW == ZW);
3169   EXPECT_EQ(0, ZW != ZW);
3170   EXPECT_EQ(0, ZW.ult(ZW));
3171 
3172   // Mutations.
3173   ZW.setBitsWithWrap(0, 0);
3174   ZW.setBits(0, 0);
3175   ZW.clearAllBits();
3176   ZW.flipAllBits();
3177 
3178   // Leading, trailing, ctpop, etc
3179   EXPECT_EQ(0U, ZW.countl_zero());
3180   EXPECT_EQ(0U, ZW.countl_one());
3181   EXPECT_EQ(0U, ZW.popcount());
3182   EXPECT_EQ(0U, ZW.reverseBits().getBitWidth());
3183   EXPECT_EQ(0U, ZW.getHiBits(0).getBitWidth());
3184   EXPECT_EQ(0U, ZW.getLoBits(0).getBitWidth());
3185   EXPECT_EQ(0, ZW.zext(4));
3186   EXPECT_EQ(0U, APInt(4, 3).trunc(0).getBitWidth());
3187   EXPECT_TRUE(ZW.isAllOnes());
3188 
3189   // Zero extension.
3190   EXPECT_EQ(0U, ZW.getZExtValue());
3191 
3192   SmallString<42> STR;
3193   ZW.toStringUnsigned(STR);
3194   EXPECT_EQ("0", STR);
3195 
3196   // Move ctor (keep at the end of the method since moves are destructive).
3197   APInt MZW1(std::move(ZW));
3198   EXPECT_EQ(0U, MZW1.getBitWidth());
3199   // Move Assignment
3200   MZW1 = std::move(ZW2);
3201   EXPECT_EQ(0U, MZW1.getBitWidth());
3202 }
3203 
3204 TEST(APIntTest, ScaleBitMask) {
3205   EXPECT_EQ(APIntOps::ScaleBitMask(APInt(2, 0x00), 8), APInt(8, 0x00));
3206   EXPECT_EQ(APIntOps::ScaleBitMask(APInt(2, 0x01), 8), APInt(8, 0x0F));
3207   EXPECT_EQ(APIntOps::ScaleBitMask(APInt(2, 0x02), 8), APInt(8, 0xF0));
3208   EXPECT_EQ(APIntOps::ScaleBitMask(APInt(2, 0x03), 8), APInt(8, 0xFF));
3209 
3210   EXPECT_EQ(APIntOps::ScaleBitMask(APInt(8, 0x00), 4), APInt(4, 0x00));
3211   EXPECT_EQ(APIntOps::ScaleBitMask(APInt(8, 0xFF), 4), APInt(4, 0x0F));
3212   EXPECT_EQ(APIntOps::ScaleBitMask(APInt(8, 0xE4), 4), APInt(4, 0x0E));
3213 
3214   EXPECT_EQ(APIntOps::ScaleBitMask(APInt(8, 0x00), 8), APInt(8, 0x00));
3215 
3216   EXPECT_EQ(APIntOps::ScaleBitMask(APInt::getZero(1024), 4096),
3217             APInt::getZero(4096));
3218   EXPECT_EQ(APIntOps::ScaleBitMask(APInt::getAllOnes(4096), 256),
3219             APInt::getAllOnes(256));
3220   EXPECT_EQ(APIntOps::ScaleBitMask(APInt::getOneBitSet(4096, 32), 256),
3221             APInt::getOneBitSet(256, 2));
3222 
3223   EXPECT_EQ(APIntOps::ScaleBitMask(APInt(2, 0x00), 8, true), APInt(8, 0x00));
3224   EXPECT_EQ(APIntOps::ScaleBitMask(APInt(2, 0x01), 8, true), APInt(8, 0x0F));
3225   EXPECT_EQ(APIntOps::ScaleBitMask(APInt(2, 0x02), 8, true), APInt(8, 0xF0));
3226   EXPECT_EQ(APIntOps::ScaleBitMask(APInt(2, 0x03), 8, true), APInt(8, 0xFF));
3227 
3228   EXPECT_EQ(APIntOps::ScaleBitMask(APInt(8, 0x00), 4, true), APInt(4, 0x00));
3229   EXPECT_EQ(APIntOps::ScaleBitMask(APInt(8, 0xFF), 4, true), APInt(4, 0x0F));
3230   EXPECT_EQ(APIntOps::ScaleBitMask(APInt(8, 0xE4), 4, true), APInt(4, 0x08));
3231 }
3232 
3233 TEST(APIntTest, DenseMap) {
3234   DenseMap<APInt, int> Map;
3235   APInt ZeroWidthInt(0, 0, false);
3236   Map.insert({ZeroWidthInt, 0});
3237   Map.find(ZeroWidthInt);
3238 }
3239 
3240 TEST(APIntTest, TryExt) {
3241   APInt small(32, 42);
3242   APInt large(128, {0xffff, 0xffff});
3243   ASSERT_TRUE(small.tryZExtValue().has_value());
3244   ASSERT_TRUE(small.trySExtValue().has_value());
3245   ASSERT_FALSE(large.tryZExtValue().has_value());
3246   ASSERT_FALSE(large.trySExtValue().has_value());
3247   ASSERT_EQ(small.trySExtValue().value_or(41), 42);
3248   ASSERT_EQ(large.trySExtValue().value_or(41), 41);
3249 
3250   APInt negOne32(32, 0);
3251   negOne32.setAllBits();
3252   ASSERT_EQ(negOne32.trySExtValue().value_or(42), -1);
3253   APInt negOne64(64, 0);
3254   negOne64.setAllBits();
3255   ASSERT_EQ(negOne64.trySExtValue().value_or(42), -1);
3256   APInt negOne128(128, 0);
3257   negOne128.setAllBits();
3258   ASSERT_EQ(negOne128.trySExtValue().value_or(42), -1);
3259   ASSERT_EQ(42, APInt(128, -1).trySExtValue().value_or(42));
3260 }
3261 
3262 } // end anonymous namespace
3263