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 "gtest/gtest.h"
16
17 using namespace llvm;
18
19 namespace {
20
TEST(KnownBitsTest,AddCarryExhaustive)21 TEST(KnownBitsTest, AddCarryExhaustive) {
22 unsigned Bits = 4;
23 ForeachKnownBits(Bits, [&](const KnownBits &Known1) {
24 ForeachKnownBits(Bits, [&](const KnownBits &Known2) {
25 ForeachKnownBits(1, [&](const KnownBits &KnownCarry) {
26 // Explicitly compute known bits of the addition by trying all
27 // possibilities.
28 KnownBits Known(Bits);
29 Known.Zero.setAllBits();
30 Known.One.setAllBits();
31 ForeachNumInKnownBits(Known1, [&](const APInt &N1) {
32 ForeachNumInKnownBits(Known2, [&](const APInt &N2) {
33 ForeachNumInKnownBits(KnownCarry, [&](const APInt &Carry) {
34 APInt Add = N1 + N2;
35 if (Carry.getBoolValue())
36 ++Add;
37
38 Known.One &= Add;
39 Known.Zero &= ~Add;
40 });
41 });
42 });
43
44 KnownBits KnownComputed = KnownBits::computeForAddCarry(
45 Known1, Known2, KnownCarry);
46 EXPECT_EQ(Known.Zero, KnownComputed.Zero);
47 EXPECT_EQ(Known.One, KnownComputed.One);
48 });
49 });
50 });
51 }
52
TestAddSubExhaustive(bool IsAdd)53 static void TestAddSubExhaustive(bool IsAdd) {
54 unsigned Bits = 4;
55 ForeachKnownBits(Bits, [&](const KnownBits &Known1) {
56 ForeachKnownBits(Bits, [&](const KnownBits &Known2) {
57 KnownBits Known(Bits), KnownNSW(Bits);
58 Known.Zero.setAllBits();
59 Known.One.setAllBits();
60 KnownNSW.Zero.setAllBits();
61 KnownNSW.One.setAllBits();
62
63 ForeachNumInKnownBits(Known1, [&](const APInt &N1) {
64 ForeachNumInKnownBits(Known2, [&](const APInt &N2) {
65 bool Overflow;
66 APInt Res;
67 if (IsAdd)
68 Res = N1.sadd_ov(N2, Overflow);
69 else
70 Res = N1.ssub_ov(N2, Overflow);
71
72 Known.One &= Res;
73 Known.Zero &= ~Res;
74
75 if (!Overflow) {
76 KnownNSW.One &= Res;
77 KnownNSW.Zero &= ~Res;
78 }
79 });
80 });
81
82 KnownBits KnownComputed = KnownBits::computeForAddSub(
83 IsAdd, /*NSW*/false, Known1, Known2);
84 EXPECT_EQ(Known.Zero, KnownComputed.Zero);
85 EXPECT_EQ(Known.One, KnownComputed.One);
86
87 // The NSW calculation is not precise, only check that it's
88 // conservatively correct.
89 KnownBits KnownNSWComputed = KnownBits::computeForAddSub(
90 IsAdd, /*NSW*/true, Known1, Known2);
91 EXPECT_TRUE(KnownNSWComputed.Zero.isSubsetOf(KnownNSW.Zero));
92 EXPECT_TRUE(KnownNSWComputed.One.isSubsetOf(KnownNSW.One));
93 });
94 });
95 }
96
TEST(KnownBitsTest,AddSubExhaustive)97 TEST(KnownBitsTest, AddSubExhaustive) {
98 TestAddSubExhaustive(true);
99 TestAddSubExhaustive(false);
100 }
101
TEST(KnownBitsTest,BinaryExhaustive)102 TEST(KnownBitsTest, BinaryExhaustive) {
103 unsigned Bits = 4;
104 ForeachKnownBits(Bits, [&](const KnownBits &Known1) {
105 ForeachKnownBits(Bits, [&](const KnownBits &Known2) {
106 KnownBits KnownAnd(Bits);
107 KnownAnd.Zero.setAllBits();
108 KnownAnd.One.setAllBits();
109 KnownBits KnownOr(KnownAnd);
110 KnownBits KnownXor(KnownAnd);
111 KnownBits KnownUMax(KnownAnd);
112 KnownBits KnownUMin(KnownAnd);
113 KnownBits KnownSMax(KnownAnd);
114 KnownBits KnownSMin(KnownAnd);
115 KnownBits KnownMul(KnownAnd);
116 KnownBits KnownUDiv(KnownAnd);
117 KnownBits KnownURem(KnownAnd);
118 KnownBits KnownSRem(KnownAnd);
119 KnownBits KnownShl(KnownAnd);
120 KnownBits KnownLShr(KnownAnd);
121 KnownBits KnownAShr(KnownAnd);
122
123 ForeachNumInKnownBits(Known1, [&](const APInt &N1) {
124 ForeachNumInKnownBits(Known2, [&](const APInt &N2) {
125 APInt Res;
126
127 Res = N1 & N2;
128 KnownAnd.One &= Res;
129 KnownAnd.Zero &= ~Res;
130
131 Res = N1 | N2;
132 KnownOr.One &= Res;
133 KnownOr.Zero &= ~Res;
134
135 Res = N1 ^ N2;
136 KnownXor.One &= Res;
137 KnownXor.Zero &= ~Res;
138
139 Res = APIntOps::umax(N1, N2);
140 KnownUMax.One &= Res;
141 KnownUMax.Zero &= ~Res;
142
143 Res = APIntOps::umin(N1, N2);
144 KnownUMin.One &= Res;
145 KnownUMin.Zero &= ~Res;
146
147 Res = APIntOps::smax(N1, N2);
148 KnownSMax.One &= Res;
149 KnownSMax.Zero &= ~Res;
150
151 Res = APIntOps::smin(N1, N2);
152 KnownSMin.One &= Res;
153 KnownSMin.Zero &= ~Res;
154
155 Res = N1 * N2;
156 KnownMul.One &= Res;
157 KnownMul.Zero &= ~Res;
158
159 if (!N2.isNullValue()) {
160 Res = N1.udiv(N2);
161 KnownUDiv.One &= Res;
162 KnownUDiv.Zero &= ~Res;
163
164 Res = N1.urem(N2);
165 KnownURem.One &= Res;
166 KnownURem.Zero &= ~Res;
167
168 Res = N1.srem(N2);
169 KnownSRem.One &= Res;
170 KnownSRem.Zero &= ~Res;
171 }
172
173 if (N2.ult(1ULL << N1.getBitWidth())) {
174 Res = N1.shl(N2);
175 KnownShl.One &= Res;
176 KnownShl.Zero &= ~Res;
177
178 Res = N1.lshr(N2);
179 KnownLShr.One &= Res;
180 KnownLShr.Zero &= ~Res;
181
182 Res = N1.ashr(N2);
183 KnownAShr.One &= Res;
184 KnownAShr.Zero &= ~Res;
185 } else {
186 KnownShl.resetAll();
187 KnownLShr.resetAll();
188 KnownAShr.resetAll();
189 }
190 });
191 });
192
193 KnownBits ComputedAnd = Known1 & Known2;
194 EXPECT_EQ(KnownAnd.Zero, ComputedAnd.Zero);
195 EXPECT_EQ(KnownAnd.One, ComputedAnd.One);
196
197 KnownBits ComputedOr = Known1 | Known2;
198 EXPECT_EQ(KnownOr.Zero, ComputedOr.Zero);
199 EXPECT_EQ(KnownOr.One, ComputedOr.One);
200
201 KnownBits ComputedXor = Known1 ^ Known2;
202 EXPECT_EQ(KnownXor.Zero, ComputedXor.Zero);
203 EXPECT_EQ(KnownXor.One, ComputedXor.One);
204
205 KnownBits ComputedUMax = KnownBits::umax(Known1, Known2);
206 EXPECT_EQ(KnownUMax.Zero, ComputedUMax.Zero);
207 EXPECT_EQ(KnownUMax.One, ComputedUMax.One);
208
209 KnownBits ComputedUMin = KnownBits::umin(Known1, Known2);
210 EXPECT_EQ(KnownUMin.Zero, ComputedUMin.Zero);
211 EXPECT_EQ(KnownUMin.One, ComputedUMin.One);
212
213 KnownBits ComputedSMax = KnownBits::smax(Known1, Known2);
214 EXPECT_EQ(KnownSMax.Zero, ComputedSMax.Zero);
215 EXPECT_EQ(KnownSMax.One, ComputedSMax.One);
216
217 KnownBits ComputedSMin = KnownBits::smin(Known1, Known2);
218 EXPECT_EQ(KnownSMin.Zero, ComputedSMin.Zero);
219 EXPECT_EQ(KnownSMin.One, ComputedSMin.One);
220
221 // ComputedMul is conservatively correct, but not guaranteed to be
222 // precise.
223 KnownBits ComputedMul = KnownBits::computeForMul(Known1, Known2);
224 EXPECT_TRUE(ComputedMul.Zero.isSubsetOf(KnownMul.Zero));
225 EXPECT_TRUE(ComputedMul.One.isSubsetOf(KnownMul.One));
226
227 KnownBits ComputedUDiv = KnownBits::udiv(Known1, Known2);
228 EXPECT_TRUE(ComputedUDiv.Zero.isSubsetOf(KnownUDiv.Zero));
229 EXPECT_TRUE(ComputedUDiv.One.isSubsetOf(KnownUDiv.One));
230
231 KnownBits ComputedURem = KnownBits::urem(Known1, Known2);
232 EXPECT_TRUE(ComputedURem.Zero.isSubsetOf(KnownURem.Zero));
233 EXPECT_TRUE(ComputedURem.One.isSubsetOf(KnownURem.One));
234
235 KnownBits ComputedSRem = KnownBits::srem(Known1, Known2);
236 EXPECT_TRUE(ComputedSRem.Zero.isSubsetOf(KnownSRem.Zero));
237 EXPECT_TRUE(ComputedSRem.One.isSubsetOf(KnownSRem.One));
238
239 KnownBits ComputedShl = KnownBits::shl(Known1, Known2);
240 EXPECT_TRUE(ComputedShl.Zero.isSubsetOf(KnownShl.Zero));
241 EXPECT_TRUE(ComputedShl.One.isSubsetOf(KnownShl.One));
242
243 KnownBits ComputedLShr = KnownBits::lshr(Known1, Known2);
244 EXPECT_TRUE(ComputedLShr.Zero.isSubsetOf(KnownLShr.Zero));
245 EXPECT_TRUE(ComputedLShr.One.isSubsetOf(KnownLShr.One));
246
247 KnownBits ComputedAShr = KnownBits::ashr(Known1, Known2);
248 EXPECT_TRUE(ComputedAShr.Zero.isSubsetOf(KnownAShr.Zero));
249 EXPECT_TRUE(ComputedAShr.One.isSubsetOf(KnownAShr.One));
250 });
251 });
252 }
253
TEST(KnownBitsTest,UnaryExhaustive)254 TEST(KnownBitsTest, UnaryExhaustive) {
255 unsigned Bits = 4;
256 ForeachKnownBits(Bits, [&](const KnownBits &Known) {
257 KnownBits KnownAbs(Bits);
258 KnownAbs.Zero.setAllBits();
259 KnownAbs.One.setAllBits();
260 KnownBits KnownAbsPoison(KnownAbs);
261
262 ForeachNumInKnownBits(Known, [&](const APInt &N) {
263 APInt Res = N.abs();
264 KnownAbs.One &= Res;
265 KnownAbs.Zero &= ~Res;
266
267 if (!N.isMinSignedValue()) {
268 KnownAbsPoison.One &= Res;
269 KnownAbsPoison.Zero &= ~Res;
270 }
271 });
272
273 // abs() is conservatively correct, but not guaranteed to be precise.
274 KnownBits ComputedAbs = Known.abs();
275 EXPECT_TRUE(ComputedAbs.Zero.isSubsetOf(KnownAbs.Zero));
276 EXPECT_TRUE(ComputedAbs.One.isSubsetOf(KnownAbs.One));
277
278 KnownBits ComputedAbsPoison = Known.abs(true);
279 EXPECT_TRUE(ComputedAbsPoison.Zero.isSubsetOf(KnownAbsPoison.Zero));
280 EXPECT_TRUE(ComputedAbsPoison.One.isSubsetOf(KnownAbsPoison.One));
281 });
282 }
283
TEST(KnownBitsTest,GetMinMaxVal)284 TEST(KnownBitsTest, GetMinMaxVal) {
285 unsigned Bits = 4;
286 ForeachKnownBits(Bits, [&](const KnownBits &Known) {
287 APInt Min = APInt::getMaxValue(Bits);
288 APInt Max = APInt::getMinValue(Bits);
289 ForeachNumInKnownBits(Known, [&](const APInt &N) {
290 Min = APIntOps::umin(Min, N);
291 Max = APIntOps::umax(Max, N);
292 });
293 EXPECT_EQ(Min, Known.getMinValue());
294 EXPECT_EQ(Max, Known.getMaxValue());
295 });
296 }
297
TEST(KnownBitsTest,SExtOrTrunc)298 TEST(KnownBitsTest, SExtOrTrunc) {
299 const unsigned NarrowerSize = 4;
300 const unsigned BaseSize = 6;
301 const unsigned WiderSize = 8;
302 APInt NegativeFitsNarrower(BaseSize, -4, /*isSigned*/ true);
303 APInt NegativeDoesntFitNarrower(BaseSize, -28, /*isSigned*/ true);
304 APInt PositiveFitsNarrower(BaseSize, 14);
305 APInt PositiveDoesntFitNarrower(BaseSize, 36);
306 auto InitKnownBits = [&](KnownBits &Res, const APInt &Input) {
307 Res = KnownBits(Input.getBitWidth());
308 Res.One = Input;
309 Res.Zero = ~Input;
310 };
311
312 for (unsigned Size : {NarrowerSize, BaseSize, WiderSize}) {
313 for (const APInt &Input :
314 {NegativeFitsNarrower, NegativeDoesntFitNarrower, PositiveFitsNarrower,
315 PositiveDoesntFitNarrower}) {
316 KnownBits Test;
317 InitKnownBits(Test, Input);
318 KnownBits Baseline;
319 InitKnownBits(Baseline, Input.sextOrTrunc(Size));
320 Test = Test.sextOrTrunc(Size);
321 EXPECT_EQ(Test.One, Baseline.One);
322 EXPECT_EQ(Test.Zero, Baseline.Zero);
323 }
324 }
325 }
326
327 } // end anonymous namespace
328