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