1//===- llvm/unittest/Support/KnownBitsTest.cpp - KnownBits 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// This file implements unit tests for KnownBits functions.
10//
11//===----------------------------------------------------------------------===//
12
13#include "llvm/Support/KnownBits.h"
14#include "KnownBitsTest.h"
15#include "llvm/ADT/ArrayRef.h"
16#include "llvm/ADT/StringRef.h"
17#include "llvm/ADT/Twine.h"
18#include "gtest/gtest.h"
19
20using namespace llvm;
21
22using UnaryBitsFn = llvm::function_ref<KnownBits(const KnownBits &)>;
23using UnaryIntFn = llvm::function_ref<std::optional<APInt>(const APInt &)>;
24
25using BinaryBitsFn =
26 llvm::function_ref<KnownBits(const KnownBits &, const KnownBits &)>;
27using BinaryIntFn =
28 llvm::function_ref<std::optional<APInt>(const APInt &, const APInt &)>;
29
30static testing::AssertionResult checkResult(Twine Name, const KnownBits &Exact,
31 const KnownBits &Computed,
32 ArrayRef<KnownBits> Inputs,
33 bool CheckOptimality) {
34 if (CheckOptimality) {
35 // We generally don't want to return conflicting known bits, even if it is
36 // legal for always poison results.
37 if (Exact.hasConflict() || Computed == Exact)
38 return testing::AssertionSuccess();
39 } else {
40 if (Computed.Zero.isSubsetOf(RHS: Exact.Zero) &&
41 Computed.One.isSubsetOf(RHS: Exact.One))
42 return testing::AssertionSuccess();
43 }
44
45 testing::AssertionResult Result = testing::AssertionFailure();
46 Result << Name << ": ";
47 Result << "Inputs = ";
48 for (const KnownBits &Input : Inputs)
49 Result << Input << ", ";
50 Result << "Computed = " << Computed << ", Exact = " << Exact;
51 return Result;
52}
53
54static void testUnaryOpExhaustive(StringRef Name, UnaryBitsFn BitsFn,
55 UnaryIntFn IntFn,
56 bool CheckOptimality = true) {
57 for (unsigned Bits : {1, 4}) {
58 ForeachKnownBits(Bits, Fn: [&](const KnownBits &Known) {
59 KnownBits Computed = BitsFn(Known);
60 KnownBits Exact(Bits);
61 Exact.Zero.setAllBits();
62 Exact.One.setAllBits();
63
64 ForeachNumInKnownBits(Known, Fn: [&](const APInt &N) {
65 if (std::optional<APInt> Res = IntFn(N)) {
66 Exact.One &= *Res;
67 Exact.Zero &= ~*Res;
68 }
69 });
70
71 EXPECT_TRUE(!Computed.hasConflict());
72 EXPECT_TRUE(checkResult(Name, Exact, Computed, Known, CheckOptimality));
73 });
74 }
75}
76
77static void testBinaryOpExhaustive(StringRef Name, BinaryBitsFn BitsFn,
78 BinaryIntFn IntFn,
79 bool CheckOptimality = true,
80 bool RefinePoisonToZero = false) {
81 for (unsigned Bits : {1, 4}) {
82 ForeachKnownBits(Bits, Fn: [&](const KnownBits &Known1) {
83 ForeachKnownBits(Bits, Fn: [&](const KnownBits &Known2) {
84 KnownBits Computed = BitsFn(Known1, Known2);
85 KnownBits Exact(Bits);
86 Exact.Zero.setAllBits();
87 Exact.One.setAllBits();
88
89 ForeachNumInKnownBits(Known: Known1, Fn: [&](const APInt &N1) {
90 ForeachNumInKnownBits(Known: Known2, Fn: [&](const APInt &N2) {
91 if (std::optional<APInt> Res = IntFn(N1, N2)) {
92 Exact.One &= *Res;
93 Exact.Zero &= ~*Res;
94 }
95 });
96 });
97
98 EXPECT_TRUE(!Computed.hasConflict());
99 EXPECT_TRUE(checkResult(Name, Exact, Computed, {Known1, Known2},
100 CheckOptimality));
101 // In some cases we choose to return zero if the result is always
102 // poison.
103 if (RefinePoisonToZero && Exact.hasConflict()) {
104 EXPECT_TRUE(Computed.isZero());
105 }
106 });
107 });
108 }
109}
110
111namespace {
112
113TEST(KnownBitsTest, AddCarryExhaustive) {
114 unsigned Bits = 4;
115 ForeachKnownBits(Bits, Fn: [&](const KnownBits &Known1) {
116 ForeachKnownBits(Bits, Fn: [&](const KnownBits &Known2) {
117 ForeachKnownBits(Bits: 1, Fn: [&](const KnownBits &KnownCarry) {
118 // Explicitly compute known bits of the addition by trying all
119 // possibilities.
120 KnownBits Exact(Bits);
121 Exact.Zero.setAllBits();
122 Exact.One.setAllBits();
123 ForeachNumInKnownBits(Known: Known1, Fn: [&](const APInt &N1) {
124 ForeachNumInKnownBits(Known: Known2, Fn: [&](const APInt &N2) {
125 ForeachNumInKnownBits(Known: KnownCarry, Fn: [&](const APInt &Carry) {
126 APInt Add = N1 + N2;
127 if (Carry.getBoolValue())
128 ++Add;
129
130 Exact.One &= Add;
131 Exact.Zero &= ~Add;
132 });
133 });
134 });
135
136 KnownBits Computed =
137 KnownBits::computeForAddCarry(LHS: Known1, RHS: Known2, Carry: KnownCarry);
138 EXPECT_EQ(Exact, Computed);
139 });
140 });
141 });
142}
143
144static void TestAddSubExhaustive(bool IsAdd) {
145 Twine Name = IsAdd ? "add" : "sub";
146 unsigned Bits = 4;
147 ForeachKnownBits(Bits, Fn: [&](const KnownBits &Known1) {
148 ForeachKnownBits(Bits, Fn: [&](const KnownBits &Known2) {
149 KnownBits Exact(Bits), ExactNSW(Bits), ExactNUW(Bits),
150 ExactNSWAndNUW(Bits);
151 Exact.Zero.setAllBits();
152 Exact.One.setAllBits();
153 ExactNSW.Zero.setAllBits();
154 ExactNSW.One.setAllBits();
155 ExactNUW.Zero.setAllBits();
156 ExactNUW.One.setAllBits();
157 ExactNSWAndNUW.Zero.setAllBits();
158 ExactNSWAndNUW.One.setAllBits();
159
160 ForeachNumInKnownBits(Known: Known1, Fn: [&](const APInt &N1) {
161 ForeachNumInKnownBits(Known: Known2, Fn: [&](const APInt &N2) {
162 bool SignedOverflow;
163 bool UnsignedOverflow;
164 APInt Res;
165 if (IsAdd) {
166 Res = N1.uadd_ov(RHS: N2, Overflow&: UnsignedOverflow);
167 Res = N1.sadd_ov(RHS: N2, Overflow&: SignedOverflow);
168 } else {
169 Res = N1.usub_ov(RHS: N2, Overflow&: UnsignedOverflow);
170 Res = N1.ssub_ov(RHS: N2, Overflow&: SignedOverflow);
171 }
172
173 Exact.One &= Res;
174 Exact.Zero &= ~Res;
175
176 if (!SignedOverflow) {
177 ExactNSW.One &= Res;
178 ExactNSW.Zero &= ~Res;
179 }
180
181 if (!UnsignedOverflow) {
182 ExactNUW.One &= Res;
183 ExactNUW.Zero &= ~Res;
184 }
185
186 if (!UnsignedOverflow && !SignedOverflow) {
187 ExactNSWAndNUW.One &= Res;
188 ExactNSWAndNUW.Zero &= ~Res;
189 }
190 });
191 });
192
193 KnownBits Computed = KnownBits::computeForAddSub(
194 Add: IsAdd, /*NSW=*/false, /*NUW=*/false, LHS: Known1, RHS: Known2);
195 EXPECT_TRUE(checkResult(Name, Exact, Computed, {Known1, Known2},
196 /*CheckOptimality=*/true));
197
198 KnownBits ComputedNSW = KnownBits::computeForAddSub(
199 Add: IsAdd, /*NSW=*/true, /*NUW=*/false, LHS: Known1, RHS: Known2);
200 EXPECT_TRUE(checkResult(Name + " nsw", ExactNSW, ComputedNSW,
201 {Known1, Known2},
202 /*CheckOptimality=*/true));
203
204 KnownBits ComputedNUW = KnownBits::computeForAddSub(
205 Add: IsAdd, /*NSW=*/false, /*NUW=*/true, LHS: Known1, RHS: Known2);
206 EXPECT_TRUE(checkResult(Name + " nuw", ExactNUW, ComputedNUW,
207 {Known1, Known2},
208 /*CheckOptimality=*/true));
209
210 KnownBits ComputedNSWAndNUW = KnownBits::computeForAddSub(
211 Add: IsAdd, /*NSW=*/true, /*NUW=*/true, LHS: Known1, RHS: Known2);
212 EXPECT_TRUE(checkResult(Name + " nsw nuw", ExactNSWAndNUW,
213 ComputedNSWAndNUW, {Known1, Known2},
214 /*CheckOptimality=*/true));
215 });
216 });
217}
218
219TEST(KnownBitsTest, AddSubExhaustive) {
220 TestAddSubExhaustive(IsAdd: true);
221 TestAddSubExhaustive(IsAdd: false);
222}
223
224TEST(KnownBitsTest, SubBorrowExhaustive) {
225 unsigned Bits = 4;
226 ForeachKnownBits(Bits, Fn: [&](const KnownBits &Known1) {
227 ForeachKnownBits(Bits, Fn: [&](const KnownBits &Known2) {
228 ForeachKnownBits(Bits: 1, Fn: [&](const KnownBits &KnownBorrow) {
229 // Explicitly compute known bits of the subtraction by trying all
230 // possibilities.
231 KnownBits Exact(Bits);
232 Exact.Zero.setAllBits();
233 Exact.One.setAllBits();
234 ForeachNumInKnownBits(Known: Known1, Fn: [&](const APInt &N1) {
235 ForeachNumInKnownBits(Known: Known2, Fn: [&](const APInt &N2) {
236 ForeachNumInKnownBits(Known: KnownBorrow, Fn: [&](const APInt &Borrow) {
237 APInt Sub = N1 - N2;
238 if (Borrow.getBoolValue())
239 --Sub;
240
241 Exact.One &= Sub;
242 Exact.Zero &= ~Sub;
243 });
244 });
245 });
246
247 KnownBits Computed =
248 KnownBits::computeForSubBorrow(LHS: Known1, RHS: Known2, Borrow: KnownBorrow);
249 EXPECT_EQ(Exact, Computed);
250 });
251 });
252 });
253}
254
255TEST(KnownBitsTest, SignBitUnknown) {
256 KnownBits Known(2);
257 EXPECT_TRUE(Known.isSignUnknown());
258 Known.Zero.setBit(0);
259 EXPECT_TRUE(Known.isSignUnknown());
260 Known.Zero.setBit(1);
261 EXPECT_FALSE(Known.isSignUnknown());
262 Known.Zero.clearBit(BitPosition: 0);
263 EXPECT_FALSE(Known.isSignUnknown());
264 Known.Zero.clearBit(BitPosition: 1);
265 EXPECT_TRUE(Known.isSignUnknown());
266
267 Known.One.setBit(0);
268 EXPECT_TRUE(Known.isSignUnknown());
269 Known.One.setBit(1);
270 EXPECT_FALSE(Known.isSignUnknown());
271 Known.One.clearBit(BitPosition: 0);
272 EXPECT_FALSE(Known.isSignUnknown());
273 Known.One.clearBit(BitPosition: 1);
274 EXPECT_TRUE(Known.isSignUnknown());
275}
276
277TEST(KnownBitsTest, BinaryExhaustive) {
278 testBinaryOpExhaustive(
279 Name: "and",
280 BitsFn: [](const KnownBits &Known1, const KnownBits &Known2) {
281 return Known1 & Known2;
282 },
283 IntFn: [](const APInt &N1, const APInt &N2) { return N1 & N2; });
284 testBinaryOpExhaustive(
285 Name: "or",
286 BitsFn: [](const KnownBits &Known1, const KnownBits &Known2) {
287 return Known1 | Known2;
288 },
289 IntFn: [](const APInt &N1, const APInt &N2) { return N1 | N2; });
290 testBinaryOpExhaustive(
291 Name: "xor",
292 BitsFn: [](const KnownBits &Known1, const KnownBits &Known2) {
293 return Known1 ^ Known2;
294 },
295 IntFn: [](const APInt &N1, const APInt &N2) { return N1 ^ N2; });
296 testBinaryOpExhaustive(Name: "umax", BitsFn: KnownBits::umax, IntFn: APIntOps::umax);
297 testBinaryOpExhaustive(Name: "umin", BitsFn: KnownBits::umin, IntFn: APIntOps::umin);
298 testBinaryOpExhaustive(Name: "smax", BitsFn: KnownBits::smax, IntFn: APIntOps::smax);
299 testBinaryOpExhaustive(Name: "smin", BitsFn: KnownBits::smin, IntFn: APIntOps::smin);
300 testBinaryOpExhaustive(Name: "abdu", BitsFn: KnownBits::abdu, IntFn: APIntOps::abdu);
301 testBinaryOpExhaustive(Name: "abds", BitsFn: KnownBits::abds, IntFn: APIntOps::abds);
302 testBinaryOpExhaustive(
303 Name: "udiv",
304 BitsFn: [](const KnownBits &Known1, const KnownBits &Known2) {
305 return KnownBits::udiv(LHS: Known1, RHS: Known2);
306 },
307 IntFn: [](const APInt &N1, const APInt &N2) -> std::optional<APInt> {
308 if (N2.isZero())
309 return std::nullopt;
310 return N1.udiv(RHS: N2);
311 },
312 /*CheckOptimality=*/false);
313 testBinaryOpExhaustive(
314 Name: "udiv exact",
315 BitsFn: [](const KnownBits &Known1, const KnownBits &Known2) {
316 return KnownBits::udiv(LHS: Known1, RHS: Known2, /*Exact*/ true);
317 },
318 IntFn: [](const APInt &N1, const APInt &N2) -> std::optional<APInt> {
319 if (N2.isZero() || !N1.urem(RHS: N2).isZero())
320 return std::nullopt;
321 return N1.udiv(RHS: N2);
322 },
323 /*CheckOptimality=*/false);
324 testBinaryOpExhaustive(
325 Name: "sdiv",
326 BitsFn: [](const KnownBits &Known1, const KnownBits &Known2) {
327 return KnownBits::sdiv(LHS: Known1, RHS: Known2);
328 },
329 IntFn: [](const APInt &N1, const APInt &N2) -> std::optional<APInt> {
330 if (N2.isZero() || (N1.isMinSignedValue() && N2.isAllOnes()))
331 return std::nullopt;
332 return N1.sdiv(RHS: N2);
333 },
334 /*CheckOptimality=*/false);
335 testBinaryOpExhaustive(
336 Name: "sdiv exact",
337 BitsFn: [](const KnownBits &Known1, const KnownBits &Known2) {
338 return KnownBits::sdiv(LHS: Known1, RHS: Known2, /*Exact*/ true);
339 },
340 IntFn: [](const APInt &N1, const APInt &N2) -> std::optional<APInt> {
341 if (N2.isZero() || (N1.isMinSignedValue() && N2.isAllOnes()) ||
342 !N1.srem(RHS: N2).isZero())
343 return std::nullopt;
344 return N1.sdiv(RHS: N2);
345 },
346 /*CheckOptimality=*/false);
347 testBinaryOpExhaustive(
348 Name: "urem", BitsFn: KnownBits::urem,
349 IntFn: [](const APInt &N1, const APInt &N2) -> std::optional<APInt> {
350 if (N2.isZero())
351 return std::nullopt;
352 return N1.urem(RHS: N2);
353 },
354 /*CheckOptimality=*/false);
355 testBinaryOpExhaustive(
356 Name: "srem", BitsFn: KnownBits::srem,
357 IntFn: [](const APInt &N1, const APInt &N2) -> std::optional<APInt> {
358 if (N2.isZero())
359 return std::nullopt;
360 return N1.srem(RHS: N2);
361 },
362 /*CheckOptimality=*/false);
363 testBinaryOpExhaustive(
364 Name: "sadd_sat", BitsFn: KnownBits::sadd_sat,
365 IntFn: [](const APInt &N1, const APInt &N2) -> std::optional<APInt> {
366 return N1.sadd_sat(RHS: N2);
367 },
368 /*CheckOptimality=*/false);
369 testBinaryOpExhaustive(
370 Name: "uadd_sat", BitsFn: KnownBits::uadd_sat,
371 IntFn: [](const APInt &N1, const APInt &N2) -> std::optional<APInt> {
372 return N1.uadd_sat(RHS: N2);
373 },
374 /*CheckOptimality=*/false);
375 testBinaryOpExhaustive(
376 Name: "ssub_sat", BitsFn: KnownBits::ssub_sat,
377 IntFn: [](const APInt &N1, const APInt &N2) -> std::optional<APInt> {
378 return N1.ssub_sat(RHS: N2);
379 },
380 /*CheckOptimality=*/false);
381 testBinaryOpExhaustive(
382 Name: "usub_sat", BitsFn: KnownBits::usub_sat,
383 IntFn: [](const APInt &N1, const APInt &N2) -> std::optional<APInt> {
384 return N1.usub_sat(RHS: N2);
385 },
386 /*CheckOptimality=*/false);
387 testBinaryOpExhaustive(
388 Name: "shl",
389 BitsFn: [](const KnownBits &Known1, const KnownBits &Known2) {
390 return KnownBits::shl(LHS: Known1, RHS: Known2);
391 },
392 IntFn: [](const APInt &N1, const APInt &N2) -> std::optional<APInt> {
393 if (N2.uge(RHS: N2.getBitWidth()))
394 return std::nullopt;
395 return N1.shl(ShiftAmt: N2);
396 },
397 /*CheckOptimality=*/true, /* RefinePoisonToZero */ true);
398 testBinaryOpExhaustive(
399 Name: "ushl_ov",
400 BitsFn: [](const KnownBits &Known1, const KnownBits &Known2) {
401 return KnownBits::shl(LHS: Known1, RHS: Known2, /* NUW */ true);
402 },
403 IntFn: [](const APInt &N1, const APInt &N2) -> std::optional<APInt> {
404 bool Overflow;
405 APInt Res = N1.ushl_ov(Amt: N2, Overflow);
406 if (Overflow)
407 return std::nullopt;
408 return Res;
409 },
410 /*CheckOptimality=*/true, /* RefinePoisonToZero */ true);
411 testBinaryOpExhaustive(
412 Name: "shl nsw",
413 BitsFn: [](const KnownBits &Known1, const KnownBits &Known2) {
414 return KnownBits::shl(LHS: Known1, RHS: Known2, /* NUW */ false, /* NSW */ true);
415 },
416 IntFn: [](const APInt &N1, const APInt &N2) -> std::optional<APInt> {
417 bool Overflow;
418 APInt Res = N1.sshl_ov(Amt: N2, Overflow);
419 if (Overflow)
420 return std::nullopt;
421 return Res;
422 },
423 /*CheckOptimality=*/true, /* RefinePoisonToZero */ true);
424 testBinaryOpExhaustive(
425 Name: "shl nuw",
426 BitsFn: [](const KnownBits &Known1, const KnownBits &Known2) {
427 return KnownBits::shl(LHS: Known1, RHS: Known2, /* NUW */ true, /* NSW */ true);
428 },
429 IntFn: [](const APInt &N1, const APInt &N2) -> std::optional<APInt> {
430 bool OverflowUnsigned, OverflowSigned;
431 APInt Res = N1.ushl_ov(Amt: N2, Overflow&: OverflowUnsigned);
432 (void)N1.sshl_ov(Amt: N2, Overflow&: OverflowSigned);
433 if (OverflowUnsigned || OverflowSigned)
434 return std::nullopt;
435 return Res;
436 },
437 /*CheckOptimality=*/true, /* RefinePoisonToZero */ true);
438
439 testBinaryOpExhaustive(
440 Name: "lshr",
441 BitsFn: [](const KnownBits &Known1, const KnownBits &Known2) {
442 return KnownBits::lshr(LHS: Known1, RHS: Known2);
443 },
444 IntFn: [](const APInt &N1, const APInt &N2) -> std::optional<APInt> {
445 if (N2.uge(RHS: N2.getBitWidth()))
446 return std::nullopt;
447 return N1.lshr(ShiftAmt: N2);
448 },
449 /*CheckOptimality=*/true, /* RefinePoisonToZero */ true);
450 testBinaryOpExhaustive(
451 Name: "lshr exact",
452 BitsFn: [](const KnownBits &Known1, const KnownBits &Known2) {
453 return KnownBits::lshr(LHS: Known1, RHS: Known2, /*ShAmtNonZero=*/false,
454 /*Exact=*/true);
455 },
456 IntFn: [](const APInt &N1, const APInt &N2) -> std::optional<APInt> {
457 if (N2.uge(RHS: N2.getBitWidth()))
458 return std::nullopt;
459 if (!N1.extractBits(numBits: N2.getZExtValue(), bitPosition: 0).isZero())
460 return std::nullopt;
461 return N1.lshr(ShiftAmt: N2);
462 },
463 /*CheckOptimality=*/true, /* RefinePoisonToZero */ true);
464 testBinaryOpExhaustive(
465 Name: "ashr",
466 BitsFn: [](const KnownBits &Known1, const KnownBits &Known2) {
467 return KnownBits::ashr(LHS: Known1, RHS: Known2);
468 },
469 IntFn: [](const APInt &N1, const APInt &N2) -> std::optional<APInt> {
470 if (N2.uge(RHS: N2.getBitWidth()))
471 return std::nullopt;
472 return N1.ashr(ShiftAmt: N2);
473 },
474 /*CheckOptimality=*/true, /* RefinePoisonToZero */ true);
475 testBinaryOpExhaustive(
476 Name: "ashr exact",
477 BitsFn: [](const KnownBits &Known1, const KnownBits &Known2) {
478 return KnownBits::ashr(LHS: Known1, RHS: Known2, /*ShAmtNonZero=*/false,
479 /*Exact=*/true);
480 },
481 IntFn: [](const APInt &N1, const APInt &N2) -> std::optional<APInt> {
482 if (N2.uge(RHS: N2.getBitWidth()))
483 return std::nullopt;
484 if (!N1.extractBits(numBits: N2.getZExtValue(), bitPosition: 0).isZero())
485 return std::nullopt;
486 return N1.ashr(ShiftAmt: N2);
487 },
488 /*CheckOptimality=*/true, /* RefinePoisonToZero */ true);
489 testBinaryOpExhaustive(
490 Name: "mul",
491 BitsFn: [](const KnownBits &Known1, const KnownBits &Known2) {
492 return KnownBits::mul(LHS: Known1, RHS: Known2);
493 },
494 IntFn: [](const APInt &N1, const APInt &N2) { return N1 * N2; },
495 /*CheckOptimality=*/false);
496 testBinaryOpExhaustive(
497 Name: "mulhs", BitsFn: KnownBits::mulhs,
498 IntFn: [](const APInt &N1, const APInt &N2) { return APIntOps::mulhs(C1: N1, C2: N2); },
499 /*CheckOptimality=*/false);
500 testBinaryOpExhaustive(
501 Name: "mulhu", BitsFn: KnownBits::mulhu,
502 IntFn: [](const APInt &N1, const APInt &N2) { return APIntOps::mulhu(C1: N1, C2: N2); },
503 /*CheckOptimality=*/false);
504}
505
506TEST(KnownBitsTest, UnaryExhaustive) {
507 testUnaryOpExhaustive(
508 Name: "abs", BitsFn: [](const KnownBits &Known) { return Known.abs(); },
509 IntFn: [](const APInt &N) { return N.abs(); });
510
511 testUnaryOpExhaustive(
512 Name: "abs(true)", BitsFn: [](const KnownBits &Known) { return Known.abs(IntMinIsPoison: true); },
513 IntFn: [](const APInt &N) -> std::optional<APInt> {
514 if (N.isMinSignedValue())
515 return std::nullopt;
516 return N.abs();
517 });
518
519 testUnaryOpExhaustive(
520 Name: "blsi", BitsFn: [](const KnownBits &Known) { return Known.blsi(); },
521 IntFn: [](const APInt &N) { return N & -N; });
522 testUnaryOpExhaustive(
523 Name: "blsmsk", BitsFn: [](const KnownBits &Known) { return Known.blsmsk(); },
524 IntFn: [](const APInt &N) { return N ^ (N - 1); });
525
526 testUnaryOpExhaustive(
527 Name: "mul self",
528 BitsFn: [](const KnownBits &Known) {
529 return KnownBits::mul(LHS: Known, RHS: Known, /*SelfMultiply*/ NoUndefSelfMultiply: true);
530 },
531 IntFn: [](const APInt &N) { return N * N; }, /*CheckOptimality=*/false);
532}
533
534TEST(KnownBitsTest, WideShifts) {
535 unsigned BitWidth = 128;
536 KnownBits Unknown(BitWidth);
537 KnownBits AllOnes = KnownBits::makeConstant(C: APInt::getAllOnes(numBits: BitWidth));
538
539 KnownBits ShlResult(BitWidth);
540 ShlResult.makeNegative();
541 EXPECT_EQ(KnownBits::shl(AllOnes, Unknown), ShlResult);
542 KnownBits LShrResult(BitWidth);
543 LShrResult.One.setBit(0);
544 EXPECT_EQ(KnownBits::lshr(AllOnes, Unknown), LShrResult);
545 EXPECT_EQ(KnownBits::ashr(AllOnes, Unknown), AllOnes);
546}
547
548TEST(KnownBitsTest, ICmpExhaustive) {
549 unsigned Bits = 4;
550 ForeachKnownBits(Bits, Fn: [&](const KnownBits &Known1) {
551 ForeachKnownBits(Bits, Fn: [&](const KnownBits &Known2) {
552 bool AllEQ = true, NoneEQ = true;
553 bool AllNE = true, NoneNE = true;
554 bool AllUGT = true, NoneUGT = true;
555 bool AllUGE = true, NoneUGE = true;
556 bool AllULT = true, NoneULT = true;
557 bool AllULE = true, NoneULE = true;
558 bool AllSGT = true, NoneSGT = true;
559 bool AllSGE = true, NoneSGE = true;
560 bool AllSLT = true, NoneSLT = true;
561 bool AllSLE = true, NoneSLE = true;
562
563 ForeachNumInKnownBits(Known: Known1, Fn: [&](const APInt &N1) {
564 ForeachNumInKnownBits(Known: Known2, Fn: [&](const APInt &N2) {
565 AllEQ &= N1.eq(RHS: N2);
566 AllNE &= N1.ne(RHS: N2);
567 AllUGT &= N1.ugt(RHS: N2);
568 AllUGE &= N1.uge(RHS: N2);
569 AllULT &= N1.ult(RHS: N2);
570 AllULE &= N1.ule(RHS: N2);
571 AllSGT &= N1.sgt(RHS: N2);
572 AllSGE &= N1.sge(RHS: N2);
573 AllSLT &= N1.slt(RHS: N2);
574 AllSLE &= N1.sle(RHS: N2);
575 NoneEQ &= !N1.eq(RHS: N2);
576 NoneNE &= !N1.ne(RHS: N2);
577 NoneUGT &= !N1.ugt(RHS: N2);
578 NoneUGE &= !N1.uge(RHS: N2);
579 NoneULT &= !N1.ult(RHS: N2);
580 NoneULE &= !N1.ule(RHS: N2);
581 NoneSGT &= !N1.sgt(RHS: N2);
582 NoneSGE &= !N1.sge(RHS: N2);
583 NoneSLT &= !N1.slt(RHS: N2);
584 NoneSLE &= !N1.sle(RHS: N2);
585 });
586 });
587
588 std::optional<bool> KnownEQ = KnownBits::eq(LHS: Known1, RHS: Known2);
589 std::optional<bool> KnownNE = KnownBits::ne(LHS: Known1, RHS: Known2);
590 std::optional<bool> KnownUGT = KnownBits::ugt(LHS: Known1, RHS: Known2);
591 std::optional<bool> KnownUGE = KnownBits::uge(LHS: Known1, RHS: Known2);
592 std::optional<bool> KnownULT = KnownBits::ult(LHS: Known1, RHS: Known2);
593 std::optional<bool> KnownULE = KnownBits::ule(LHS: Known1, RHS: Known2);
594 std::optional<bool> KnownSGT = KnownBits::sgt(LHS: Known1, RHS: Known2);
595 std::optional<bool> KnownSGE = KnownBits::sge(LHS: Known1, RHS: Known2);
596 std::optional<bool> KnownSLT = KnownBits::slt(LHS: Known1, RHS: Known2);
597 std::optional<bool> KnownSLE = KnownBits::sle(LHS: Known1, RHS: Known2);
598
599 EXPECT_EQ(AllEQ || NoneEQ, KnownEQ.has_value());
600 EXPECT_EQ(AllNE || NoneNE, KnownNE.has_value());
601 EXPECT_EQ(AllUGT || NoneUGT, KnownUGT.has_value());
602 EXPECT_EQ(AllUGE || NoneUGE, KnownUGE.has_value());
603 EXPECT_EQ(AllULT || NoneULT, KnownULT.has_value());
604 EXPECT_EQ(AllULE || NoneULE, KnownULE.has_value());
605 EXPECT_EQ(AllSGT || NoneSGT, KnownSGT.has_value());
606 EXPECT_EQ(AllSGE || NoneSGE, KnownSGE.has_value());
607 EXPECT_EQ(AllSLT || NoneSLT, KnownSLT.has_value());
608 EXPECT_EQ(AllSLE || NoneSLE, KnownSLE.has_value());
609
610 EXPECT_EQ(AllEQ, KnownEQ.has_value() && *KnownEQ);
611 EXPECT_EQ(AllNE, KnownNE.has_value() && *KnownNE);
612 EXPECT_EQ(AllUGT, KnownUGT.has_value() && *KnownUGT);
613 EXPECT_EQ(AllUGE, KnownUGE.has_value() && *KnownUGE);
614 EXPECT_EQ(AllULT, KnownULT.has_value() && *KnownULT);
615 EXPECT_EQ(AllULE, KnownULE.has_value() && *KnownULE);
616 EXPECT_EQ(AllSGT, KnownSGT.has_value() && *KnownSGT);
617 EXPECT_EQ(AllSGE, KnownSGE.has_value() && *KnownSGE);
618 EXPECT_EQ(AllSLT, KnownSLT.has_value() && *KnownSLT);
619 EXPECT_EQ(AllSLE, KnownSLE.has_value() && *KnownSLE);
620
621 EXPECT_EQ(NoneEQ, KnownEQ.has_value() && !*KnownEQ);
622 EXPECT_EQ(NoneNE, KnownNE.has_value() && !*KnownNE);
623 EXPECT_EQ(NoneUGT, KnownUGT.has_value() && !*KnownUGT);
624 EXPECT_EQ(NoneUGE, KnownUGE.has_value() && !*KnownUGE);
625 EXPECT_EQ(NoneULT, KnownULT.has_value() && !*KnownULT);
626 EXPECT_EQ(NoneULE, KnownULE.has_value() && !*KnownULE);
627 EXPECT_EQ(NoneSGT, KnownSGT.has_value() && !*KnownSGT);
628 EXPECT_EQ(NoneSGE, KnownSGE.has_value() && !*KnownSGE);
629 EXPECT_EQ(NoneSLT, KnownSLT.has_value() && !*KnownSLT);
630 EXPECT_EQ(NoneSLE, KnownSLE.has_value() && !*KnownSLE);
631 });
632 });
633}
634
635TEST(KnownBitsTest, GetMinMaxVal) {
636 unsigned Bits = 4;
637 ForeachKnownBits(Bits, Fn: [&](const KnownBits &Known) {
638 APInt Min = APInt::getMaxValue(numBits: Bits);
639 APInt Max = APInt::getMinValue(numBits: Bits);
640 ForeachNumInKnownBits(Known, Fn: [&](const APInt &N) {
641 Min = APIntOps::umin(A: Min, B: N);
642 Max = APIntOps::umax(A: Max, B: N);
643 });
644 EXPECT_EQ(Min, Known.getMinValue());
645 EXPECT_EQ(Max, Known.getMaxValue());
646 });
647}
648
649TEST(KnownBitsTest, GetSignedMinMaxVal) {
650 unsigned Bits = 4;
651 ForeachKnownBits(Bits, Fn: [&](const KnownBits &Known) {
652 APInt Min = APInt::getSignedMaxValue(numBits: Bits);
653 APInt Max = APInt::getSignedMinValue(numBits: Bits);
654 ForeachNumInKnownBits(Known, Fn: [&](const APInt &N) {
655 Min = APIntOps::smin(A: Min, B: N);
656 Max = APIntOps::smax(A: Max, B: N);
657 });
658 EXPECT_EQ(Min, Known.getSignedMinValue());
659 EXPECT_EQ(Max, Known.getSignedMaxValue());
660 });
661}
662
663TEST(KnownBitsTest, CountMaxActiveBits) {
664 unsigned Bits = 4;
665 ForeachKnownBits(Bits, Fn: [&](const KnownBits &Known) {
666 unsigned Expected = 0;
667 ForeachNumInKnownBits(Known, Fn: [&](const APInt &N) {
668 Expected = std::max(a: Expected, b: N.getActiveBits());
669 });
670 EXPECT_EQ(Expected, Known.countMaxActiveBits());
671 });
672}
673
674TEST(KnownBitsTest, CountMaxSignificantBits) {
675 unsigned Bits = 4;
676 ForeachKnownBits(Bits, Fn: [&](const KnownBits &Known) {
677 unsigned Expected = 0;
678 ForeachNumInKnownBits(Known, Fn: [&](const APInt &N) {
679 Expected = std::max(a: Expected, b: N.getSignificantBits());
680 });
681 EXPECT_EQ(Expected, Known.countMaxSignificantBits());
682 });
683}
684
685TEST(KnownBitsTest, SExtOrTrunc) {
686 const unsigned NarrowerSize = 4;
687 const unsigned BaseSize = 6;
688 const unsigned WiderSize = 8;
689 APInt NegativeFitsNarrower(BaseSize, -4, /*isSigned*/ true);
690 APInt NegativeDoesntFitNarrower(BaseSize, -28, /*isSigned*/ true);
691 APInt PositiveFitsNarrower(BaseSize, 14);
692 APInt PositiveDoesntFitNarrower(BaseSize, 36);
693 auto InitKnownBits = [&](KnownBits &Res, const APInt &Input) {
694 Res = KnownBits(Input.getBitWidth());
695 Res.One = Input;
696 Res.Zero = ~Input;
697 };
698
699 for (unsigned Size : {NarrowerSize, BaseSize, WiderSize}) {
700 for (const APInt &Input :
701 {NegativeFitsNarrower, NegativeDoesntFitNarrower, PositiveFitsNarrower,
702 PositiveDoesntFitNarrower}) {
703 KnownBits Test;
704 InitKnownBits(Test, Input);
705 KnownBits Baseline;
706 InitKnownBits(Baseline, Input.sextOrTrunc(width: Size));
707 Test = Test.sextOrTrunc(BitWidth: Size);
708 EXPECT_EQ(Test, Baseline);
709 }
710 }
711}
712
713TEST(KnownBitsTest, SExtInReg) {
714 unsigned Bits = 4;
715 for (unsigned FromBits = 1; FromBits <= Bits; ++FromBits) {
716 ForeachKnownBits(Bits, Fn: [&](const KnownBits &Known) {
717 APInt CommonOne = APInt::getAllOnes(numBits: Bits);
718 APInt CommonZero = APInt::getAllOnes(numBits: Bits);
719 unsigned ExtBits = Bits - FromBits;
720 ForeachNumInKnownBits(Known, Fn: [&](const APInt &N) {
721 APInt Ext = N << ExtBits;
722 Ext.ashrInPlace(ShiftAmt: ExtBits);
723 CommonOne &= Ext;
724 CommonZero &= ~Ext;
725 });
726 KnownBits KnownSExtInReg = Known.sextInReg(SrcBitWidth: FromBits);
727 EXPECT_EQ(CommonOne, KnownSExtInReg.One);
728 EXPECT_EQ(CommonZero, KnownSExtInReg.Zero);
729 });
730 }
731}
732
733TEST(KnownBitsTest, CommonBitsSet) {
734 unsigned Bits = 4;
735 ForeachKnownBits(Bits, Fn: [&](const KnownBits &Known1) {
736 ForeachKnownBits(Bits, Fn: [&](const KnownBits &Known2) {
737 bool HasCommonBitsSet = false;
738 ForeachNumInKnownBits(Known: Known1, Fn: [&](const APInt &N1) {
739 ForeachNumInKnownBits(Known: Known2, Fn: [&](const APInt &N2) {
740 HasCommonBitsSet |= N1.intersects(RHS: N2);
741 });
742 });
743 EXPECT_EQ(!HasCommonBitsSet,
744 KnownBits::haveNoCommonBitsSet(Known1, Known2));
745 });
746 });
747}
748
749TEST(KnownBitsTest, ConcatBits) {
750 unsigned Bits = 4;
751 for (unsigned LoBits = 1; LoBits < Bits; ++LoBits) {
752 unsigned HiBits = Bits - LoBits;
753 ForeachKnownBits(Bits: LoBits, Fn: [&](const KnownBits &KnownLo) {
754 ForeachKnownBits(Bits: HiBits, Fn: [&](const KnownBits &KnownHi) {
755 KnownBits KnownAll = KnownHi.concat(Lo: KnownLo);
756
757 EXPECT_EQ(KnownLo.countMinPopulation() + KnownHi.countMinPopulation(),
758 KnownAll.countMinPopulation());
759 EXPECT_EQ(KnownLo.countMaxPopulation() + KnownHi.countMaxPopulation(),
760 KnownAll.countMaxPopulation());
761
762 KnownBits ExtractLo = KnownAll.extractBits(NumBits: LoBits, BitPosition: 0);
763 KnownBits ExtractHi = KnownAll.extractBits(NumBits: HiBits, BitPosition: LoBits);
764
765 EXPECT_EQ(KnownLo.One.getZExtValue(), ExtractLo.One.getZExtValue());
766 EXPECT_EQ(KnownHi.One.getZExtValue(), ExtractHi.One.getZExtValue());
767 EXPECT_EQ(KnownLo.Zero.getZExtValue(), ExtractLo.Zero.getZExtValue());
768 EXPECT_EQ(KnownHi.Zero.getZExtValue(), ExtractHi.Zero.getZExtValue());
769 });
770 });
771 }
772}
773
774} // end anonymous namespace
775

source code of llvm/unittests/Support/KnownBitsTest.cpp