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 "gtest/gtest.h"
15 
16 using namespace llvm;
17 
18 namespace {
19 
20 template<typename FnTy>
21 void ForeachKnownBits(unsigned Bits, FnTy Fn) {
22   unsigned Max = 1 << Bits;
23   KnownBits Known(Bits);
24   for (unsigned Zero = 0; Zero < Max; ++Zero) {
25     for (unsigned One = 0; One < Max; ++One) {
26       Known.Zero = Zero;
27       Known.One = One;
28       if (Known.hasConflict())
29         continue;
30 
31       Fn(Known);
32     }
33   }
34 }
35 
36 template<typename FnTy>
37 void ForeachNumInKnownBits(const KnownBits &Known, FnTy Fn) {
38   unsigned Bits = Known.getBitWidth();
39   unsigned Max = 1 << Bits;
40   for (unsigned N = 0; N < Max; ++N) {
41     APInt Num(Bits, N);
42     if ((Num & Known.Zero) != 0 || (~Num & Known.One) != 0)
43       continue;
44 
45     Fn(Num);
46   }
47 }
48 
49 TEST(KnownBitsTest, AddCarryExhaustive) {
50   unsigned Bits = 4;
51   ForeachKnownBits(Bits, [&](const KnownBits &Known1) {
52     ForeachKnownBits(Bits, [&](const KnownBits &Known2) {
53       ForeachKnownBits(1, [&](const KnownBits &KnownCarry) {
54         // Explicitly compute known bits of the addition by trying all
55         // possibilities.
56         KnownBits Known(Bits);
57         Known.Zero.setAllBits();
58         Known.One.setAllBits();
59         ForeachNumInKnownBits(Known1, [&](const APInt &N1) {
60           ForeachNumInKnownBits(Known2, [&](const APInt &N2) {
61             ForeachNumInKnownBits(KnownCarry, [&](const APInt &Carry) {
62               APInt Add = N1 + N2;
63               if (Carry.getBoolValue())
64                 ++Add;
65 
66               Known.One &= Add;
67               Known.Zero &= ~Add;
68             });
69           });
70         });
71 
72         KnownBits KnownComputed = KnownBits::computeForAddCarry(
73             Known1, Known2, KnownCarry);
74         EXPECT_EQ(Known.Zero, KnownComputed.Zero);
75         EXPECT_EQ(Known.One, KnownComputed.One);
76       });
77     });
78   });
79 }
80 
81 static void TestAddSubExhaustive(bool IsAdd) {
82   unsigned Bits = 4;
83   ForeachKnownBits(Bits, [&](const KnownBits &Known1) {
84     ForeachKnownBits(Bits, [&](const KnownBits &Known2) {
85       KnownBits Known(Bits), KnownNSW(Bits);
86       Known.Zero.setAllBits();
87       Known.One.setAllBits();
88       KnownNSW.Zero.setAllBits();
89       KnownNSW.One.setAllBits();
90 
91       ForeachNumInKnownBits(Known1, [&](const APInt &N1) {
92         ForeachNumInKnownBits(Known2, [&](const APInt &N2) {
93           bool Overflow;
94           APInt Res;
95           if (IsAdd)
96             Res = N1.sadd_ov(N2, Overflow);
97           else
98             Res = N1.ssub_ov(N2, Overflow);
99 
100           Known.One &= Res;
101           Known.Zero &= ~Res;
102 
103           if (!Overflow) {
104             KnownNSW.One &= Res;
105             KnownNSW.Zero &= ~Res;
106           }
107         });
108       });
109 
110       KnownBits KnownComputed = KnownBits::computeForAddSub(
111           IsAdd, /*NSW*/false, Known1, Known2);
112       EXPECT_EQ(Known.Zero, KnownComputed.Zero);
113       EXPECT_EQ(Known.One, KnownComputed.One);
114 
115       // The NSW calculation is not precise, only check that it's
116       // conservatively correct.
117       KnownBits KnownNSWComputed = KnownBits::computeForAddSub(
118           IsAdd, /*NSW*/true, Known1, Known2);
119       EXPECT_TRUE(KnownNSWComputed.Zero.isSubsetOf(KnownNSW.Zero));
120       EXPECT_TRUE(KnownNSWComputed.One.isSubsetOf(KnownNSW.One));
121     });
122   });
123 }
124 
125 TEST(KnownBitsTest, AddSubExhaustive) {
126   TestAddSubExhaustive(true);
127   TestAddSubExhaustive(false);
128 }
129 
130 TEST(KnownBitsTest, BinaryExhaustive) {
131   unsigned Bits = 4;
132   ForeachKnownBits(Bits, [&](const KnownBits &Known1) {
133     ForeachKnownBits(Bits, [&](const KnownBits &Known2) {
134       KnownBits KnownAnd(Bits), KnownOr(Bits), KnownXor(Bits);
135       KnownAnd.Zero.setAllBits();
136       KnownAnd.One.setAllBits();
137       KnownOr.Zero.setAllBits();
138       KnownOr.One.setAllBits();
139       KnownXor.Zero.setAllBits();
140       KnownXor.One.setAllBits();
141 
142       ForeachNumInKnownBits(Known1, [&](const APInt &N1) {
143         ForeachNumInKnownBits(Known2, [&](const APInt &N2) {
144           APInt Res;
145 
146           Res = N1 & N2;
147           KnownAnd.One &= Res;
148           KnownAnd.Zero &= ~Res;
149 
150           Res = N1 | N2;
151           KnownOr.One &= Res;
152           KnownOr.Zero &= ~Res;
153 
154           Res = N1 ^ N2;
155           KnownXor.One &= Res;
156           KnownXor.Zero &= ~Res;
157         });
158       });
159 
160       KnownBits ComputedAnd = Known1 & Known2;
161       EXPECT_EQ(KnownAnd.Zero, ComputedAnd.Zero);
162       EXPECT_EQ(KnownAnd.One, ComputedAnd.One);
163 
164       KnownBits ComputedOr = Known1 | Known2;
165       EXPECT_EQ(KnownOr.Zero, ComputedOr.Zero);
166       EXPECT_EQ(KnownOr.One, ComputedOr.One);
167 
168       KnownBits ComputedXor = Known1 ^ Known2;
169       EXPECT_EQ(KnownXor.Zero, ComputedXor.Zero);
170       EXPECT_EQ(KnownXor.One, ComputedXor.One);
171     });
172   });
173 }
174 
175 TEST(KnownBitsTest, GetMinMaxVal) {
176   unsigned Bits = 4;
177   ForeachKnownBits(Bits, [&](const KnownBits &Known) {
178     APInt Min = APInt::getMaxValue(Bits);
179     APInt Max = APInt::getMinValue(Bits);
180     ForeachNumInKnownBits(Known, [&](const APInt &N) {
181       Min = APIntOps::umin(Min, N);
182       Max = APIntOps::umax(Max, N);
183     });
184     EXPECT_EQ(Min, Known.getMinValue());
185     EXPECT_EQ(Max, Known.getMaxValue());
186   });
187 }
188 
189 } // end anonymous namespace
190