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