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 KnownMulHS(KnownAnd);
117 KnownBits KnownMulHU(KnownAnd);
118 KnownBits KnownUDiv(KnownAnd);
119 KnownBits KnownURem(KnownAnd);
120 KnownBits KnownSRem(KnownAnd);
121 KnownBits KnownShl(KnownAnd);
122 KnownBits KnownLShr(KnownAnd);
123 KnownBits KnownAShr(KnownAnd);
124
125 ForeachNumInKnownBits(Known1, [&](const APInt &N1) {
126 ForeachNumInKnownBits(Known2, [&](const APInt &N2) {
127 APInt Res;
128
129 Res = N1 & N2;
130 KnownAnd.One &= Res;
131 KnownAnd.Zero &= ~Res;
132
133 Res = N1 | N2;
134 KnownOr.One &= Res;
135 KnownOr.Zero &= ~Res;
136
137 Res = N1 ^ N2;
138 KnownXor.One &= Res;
139 KnownXor.Zero &= ~Res;
140
141 Res = APIntOps::umax(N1, N2);
142 KnownUMax.One &= Res;
143 KnownUMax.Zero &= ~Res;
144
145 Res = APIntOps::umin(N1, N2);
146 KnownUMin.One &= Res;
147 KnownUMin.Zero &= ~Res;
148
149 Res = APIntOps::smax(N1, N2);
150 KnownSMax.One &= Res;
151 KnownSMax.Zero &= ~Res;
152
153 Res = APIntOps::smin(N1, N2);
154 KnownSMin.One &= Res;
155 KnownSMin.Zero &= ~Res;
156
157 Res = N1 * N2;
158 KnownMul.One &= Res;
159 KnownMul.Zero &= ~Res;
160
161 Res = (N1.sext(2 * Bits) * N2.sext(2 * Bits)).extractBits(Bits, Bits);
162 KnownMulHS.One &= Res;
163 KnownMulHS.Zero &= ~Res;
164
165 Res = (N1.zext(2 * Bits) * N2.zext(2 * Bits)).extractBits(Bits, Bits);
166 KnownMulHU.One &= Res;
167 KnownMulHU.Zero &= ~Res;
168
169 if (!N2.isNullValue()) {
170 Res = N1.udiv(N2);
171 KnownUDiv.One &= Res;
172 KnownUDiv.Zero &= ~Res;
173
174 Res = N1.urem(N2);
175 KnownURem.One &= Res;
176 KnownURem.Zero &= ~Res;
177
178 Res = N1.srem(N2);
179 KnownSRem.One &= Res;
180 KnownSRem.Zero &= ~Res;
181 }
182
183 if (N2.ult(1ULL << N1.getBitWidth())) {
184 Res = N1.shl(N2);
185 KnownShl.One &= Res;
186 KnownShl.Zero &= ~Res;
187
188 Res = N1.lshr(N2);
189 KnownLShr.One &= Res;
190 KnownLShr.Zero &= ~Res;
191
192 Res = N1.ashr(N2);
193 KnownAShr.One &= Res;
194 KnownAShr.Zero &= ~Res;
195 } else {
196 KnownShl.resetAll();
197 KnownLShr.resetAll();
198 KnownAShr.resetAll();
199 }
200 });
201 });
202
203 KnownBits ComputedAnd = Known1 & Known2;
204 EXPECT_EQ(KnownAnd.Zero, ComputedAnd.Zero);
205 EXPECT_EQ(KnownAnd.One, ComputedAnd.One);
206
207 KnownBits ComputedOr = Known1 | Known2;
208 EXPECT_EQ(KnownOr.Zero, ComputedOr.Zero);
209 EXPECT_EQ(KnownOr.One, ComputedOr.One);
210
211 KnownBits ComputedXor = Known1 ^ Known2;
212 EXPECT_EQ(KnownXor.Zero, ComputedXor.Zero);
213 EXPECT_EQ(KnownXor.One, ComputedXor.One);
214
215 KnownBits ComputedUMax = KnownBits::umax(Known1, Known2);
216 EXPECT_EQ(KnownUMax.Zero, ComputedUMax.Zero);
217 EXPECT_EQ(KnownUMax.One, ComputedUMax.One);
218
219 KnownBits ComputedUMin = KnownBits::umin(Known1, Known2);
220 EXPECT_EQ(KnownUMin.Zero, ComputedUMin.Zero);
221 EXPECT_EQ(KnownUMin.One, ComputedUMin.One);
222
223 KnownBits ComputedSMax = KnownBits::smax(Known1, Known2);
224 EXPECT_EQ(KnownSMax.Zero, ComputedSMax.Zero);
225 EXPECT_EQ(KnownSMax.One, ComputedSMax.One);
226
227 KnownBits ComputedSMin = KnownBits::smin(Known1, Known2);
228 EXPECT_EQ(KnownSMin.Zero, ComputedSMin.Zero);
229 EXPECT_EQ(KnownSMin.One, ComputedSMin.One);
230
231 // The following are conservatively correct, but not guaranteed to be
232 // precise.
233 KnownBits ComputedMul = KnownBits::mul(Known1, Known2);
234 EXPECT_TRUE(ComputedMul.Zero.isSubsetOf(KnownMul.Zero));
235 EXPECT_TRUE(ComputedMul.One.isSubsetOf(KnownMul.One));
236
237 KnownBits ComputedMulHS = KnownBits::mulhs(Known1, Known2);
238 EXPECT_TRUE(ComputedMulHS.Zero.isSubsetOf(KnownMulHS.Zero));
239 EXPECT_TRUE(ComputedMulHS.One.isSubsetOf(KnownMulHS.One));
240
241 KnownBits ComputedMulHU = KnownBits::mulhu(Known1, Known2);
242 EXPECT_TRUE(ComputedMulHU.Zero.isSubsetOf(KnownMulHU.Zero));
243 EXPECT_TRUE(ComputedMulHU.One.isSubsetOf(KnownMulHU.One));
244
245 KnownBits ComputedUDiv = KnownBits::udiv(Known1, Known2);
246 EXPECT_TRUE(ComputedUDiv.Zero.isSubsetOf(KnownUDiv.Zero));
247 EXPECT_TRUE(ComputedUDiv.One.isSubsetOf(KnownUDiv.One));
248
249 KnownBits ComputedURem = KnownBits::urem(Known1, Known2);
250 EXPECT_TRUE(ComputedURem.Zero.isSubsetOf(KnownURem.Zero));
251 EXPECT_TRUE(ComputedURem.One.isSubsetOf(KnownURem.One));
252
253 KnownBits ComputedSRem = KnownBits::srem(Known1, Known2);
254 EXPECT_TRUE(ComputedSRem.Zero.isSubsetOf(KnownSRem.Zero));
255 EXPECT_TRUE(ComputedSRem.One.isSubsetOf(KnownSRem.One));
256
257 KnownBits ComputedShl = KnownBits::shl(Known1, Known2);
258 EXPECT_TRUE(ComputedShl.Zero.isSubsetOf(KnownShl.Zero));
259 EXPECT_TRUE(ComputedShl.One.isSubsetOf(KnownShl.One));
260
261 KnownBits ComputedLShr = KnownBits::lshr(Known1, Known2);
262 EXPECT_TRUE(ComputedLShr.Zero.isSubsetOf(KnownLShr.Zero));
263 EXPECT_TRUE(ComputedLShr.One.isSubsetOf(KnownLShr.One));
264
265 KnownBits ComputedAShr = KnownBits::ashr(Known1, Known2);
266 EXPECT_TRUE(ComputedAShr.Zero.isSubsetOf(KnownAShr.Zero));
267 EXPECT_TRUE(ComputedAShr.One.isSubsetOf(KnownAShr.One));
268 });
269 });
270 }
271
TEST(KnownBitsTest,UnaryExhaustive)272 TEST(KnownBitsTest, UnaryExhaustive) {
273 unsigned Bits = 4;
274 ForeachKnownBits(Bits, [&](const KnownBits &Known) {
275 KnownBits KnownAbs(Bits);
276 KnownAbs.Zero.setAllBits();
277 KnownAbs.One.setAllBits();
278 KnownBits KnownAbsPoison(KnownAbs);
279
280 ForeachNumInKnownBits(Known, [&](const APInt &N) {
281 APInt Res = N.abs();
282 KnownAbs.One &= Res;
283 KnownAbs.Zero &= ~Res;
284
285 if (!N.isMinSignedValue()) {
286 KnownAbsPoison.One &= Res;
287 KnownAbsPoison.Zero &= ~Res;
288 }
289 });
290
291 // abs() is conservatively correct, but not guaranteed to be precise.
292 KnownBits ComputedAbs = Known.abs();
293 EXPECT_TRUE(ComputedAbs.Zero.isSubsetOf(KnownAbs.Zero));
294 EXPECT_TRUE(ComputedAbs.One.isSubsetOf(KnownAbs.One));
295
296 KnownBits ComputedAbsPoison = Known.abs(true);
297 EXPECT_TRUE(ComputedAbsPoison.Zero.isSubsetOf(KnownAbsPoison.Zero));
298 EXPECT_TRUE(ComputedAbsPoison.One.isSubsetOf(KnownAbsPoison.One));
299 });
300 }
301
TEST(KnownBitsTest,ICmpExhaustive)302 TEST(KnownBitsTest, ICmpExhaustive) {
303 unsigned Bits = 4;
304 ForeachKnownBits(Bits, [&](const KnownBits &Known1) {
305 ForeachKnownBits(Bits, [&](const KnownBits &Known2) {
306 bool AllEQ = true, NoneEQ = true;
307 bool AllNE = true, NoneNE = true;
308 bool AllUGT = true, NoneUGT = true;
309 bool AllUGE = true, NoneUGE = true;
310 bool AllULT = true, NoneULT = true;
311 bool AllULE = true, NoneULE = true;
312 bool AllSGT = true, NoneSGT = true;
313 bool AllSGE = true, NoneSGE = true;
314 bool AllSLT = true, NoneSLT = true;
315 bool AllSLE = true, NoneSLE = true;
316
317 ForeachNumInKnownBits(Known1, [&](const APInt &N1) {
318 ForeachNumInKnownBits(Known2, [&](const APInt &N2) {
319 AllEQ &= N1.eq(N2);
320 AllNE &= N1.ne(N2);
321 AllUGT &= N1.ugt(N2);
322 AllUGE &= N1.uge(N2);
323 AllULT &= N1.ult(N2);
324 AllULE &= N1.ule(N2);
325 AllSGT &= N1.sgt(N2);
326 AllSGE &= N1.sge(N2);
327 AllSLT &= N1.slt(N2);
328 AllSLE &= N1.sle(N2);
329 NoneEQ &= !N1.eq(N2);
330 NoneNE &= !N1.ne(N2);
331 NoneUGT &= !N1.ugt(N2);
332 NoneUGE &= !N1.uge(N2);
333 NoneULT &= !N1.ult(N2);
334 NoneULE &= !N1.ule(N2);
335 NoneSGT &= !N1.sgt(N2);
336 NoneSGE &= !N1.sge(N2);
337 NoneSLT &= !N1.slt(N2);
338 NoneSLE &= !N1.sle(N2);
339 });
340 });
341
342 Optional<bool> KnownEQ = KnownBits::eq(Known1, Known2);
343 Optional<bool> KnownNE = KnownBits::ne(Known1, Known2);
344 Optional<bool> KnownUGT = KnownBits::ugt(Known1, Known2);
345 Optional<bool> KnownUGE = KnownBits::uge(Known1, Known2);
346 Optional<bool> KnownULT = KnownBits::ult(Known1, Known2);
347 Optional<bool> KnownULE = KnownBits::ule(Known1, Known2);
348 Optional<bool> KnownSGT = KnownBits::sgt(Known1, Known2);
349 Optional<bool> KnownSGE = KnownBits::sge(Known1, Known2);
350 Optional<bool> KnownSLT = KnownBits::slt(Known1, Known2);
351 Optional<bool> KnownSLE = KnownBits::sle(Known1, Known2);
352
353 EXPECT_EQ(AllEQ || NoneEQ, KnownEQ.hasValue());
354 EXPECT_EQ(AllNE || NoneNE, KnownNE.hasValue());
355 EXPECT_EQ(AllUGT || NoneUGT, KnownUGT.hasValue());
356 EXPECT_EQ(AllUGE || NoneUGE, KnownUGE.hasValue());
357 EXPECT_EQ(AllULT || NoneULT, KnownULT.hasValue());
358 EXPECT_EQ(AllULE || NoneULE, KnownULE.hasValue());
359 EXPECT_EQ(AllSGT || NoneSGT, KnownSGT.hasValue());
360 EXPECT_EQ(AllSGE || NoneSGE, KnownSGE.hasValue());
361 EXPECT_EQ(AllSLT || NoneSLT, KnownSLT.hasValue());
362 EXPECT_EQ(AllSLE || NoneSLE, KnownSLE.hasValue());
363
364 EXPECT_EQ(AllEQ, KnownEQ.hasValue() && KnownEQ.getValue());
365 EXPECT_EQ(AllNE, KnownNE.hasValue() && KnownNE.getValue());
366 EXPECT_EQ(AllUGT, KnownUGT.hasValue() && KnownUGT.getValue());
367 EXPECT_EQ(AllUGE, KnownUGE.hasValue() && KnownUGE.getValue());
368 EXPECT_EQ(AllULT, KnownULT.hasValue() && KnownULT.getValue());
369 EXPECT_EQ(AllULE, KnownULE.hasValue() && KnownULE.getValue());
370 EXPECT_EQ(AllSGT, KnownSGT.hasValue() && KnownSGT.getValue());
371 EXPECT_EQ(AllSGE, KnownSGE.hasValue() && KnownSGE.getValue());
372 EXPECT_EQ(AllSLT, KnownSLT.hasValue() && KnownSLT.getValue());
373 EXPECT_EQ(AllSLE, KnownSLE.hasValue() && KnownSLE.getValue());
374
375 EXPECT_EQ(NoneEQ, KnownEQ.hasValue() && !KnownEQ.getValue());
376 EXPECT_EQ(NoneNE, KnownNE.hasValue() && !KnownNE.getValue());
377 EXPECT_EQ(NoneUGT, KnownUGT.hasValue() && !KnownUGT.getValue());
378 EXPECT_EQ(NoneUGE, KnownUGE.hasValue() && !KnownUGE.getValue());
379 EXPECT_EQ(NoneULT, KnownULT.hasValue() && !KnownULT.getValue());
380 EXPECT_EQ(NoneULE, KnownULE.hasValue() && !KnownULE.getValue());
381 EXPECT_EQ(NoneSGT, KnownSGT.hasValue() && !KnownSGT.getValue());
382 EXPECT_EQ(NoneSGE, KnownSGE.hasValue() && !KnownSGE.getValue());
383 EXPECT_EQ(NoneSLT, KnownSLT.hasValue() && !KnownSLT.getValue());
384 EXPECT_EQ(NoneSLE, KnownSLE.hasValue() && !KnownSLE.getValue());
385 });
386 });
387 }
388
TEST(KnownBitsTest,GetMinMaxVal)389 TEST(KnownBitsTest, GetMinMaxVal) {
390 unsigned Bits = 4;
391 ForeachKnownBits(Bits, [&](const KnownBits &Known) {
392 APInt Min = APInt::getMaxValue(Bits);
393 APInt Max = APInt::getMinValue(Bits);
394 ForeachNumInKnownBits(Known, [&](const APInt &N) {
395 Min = APIntOps::umin(Min, N);
396 Max = APIntOps::umax(Max, N);
397 });
398 EXPECT_EQ(Min, Known.getMinValue());
399 EXPECT_EQ(Max, Known.getMaxValue());
400 });
401 }
402
TEST(KnownBitsTest,GetSignedMinMaxVal)403 TEST(KnownBitsTest, GetSignedMinMaxVal) {
404 unsigned Bits = 4;
405 ForeachKnownBits(Bits, [&](const KnownBits &Known) {
406 APInt Min = APInt::getSignedMaxValue(Bits);
407 APInt Max = APInt::getSignedMinValue(Bits);
408 ForeachNumInKnownBits(Known, [&](const APInt &N) {
409 Min = APIntOps::smin(Min, N);
410 Max = APIntOps::smax(Max, N);
411 });
412 EXPECT_EQ(Min, Known.getSignedMinValue());
413 EXPECT_EQ(Max, Known.getSignedMaxValue());
414 });
415 }
416
TEST(KnownBitsTest,SExtOrTrunc)417 TEST(KnownBitsTest, SExtOrTrunc) {
418 const unsigned NarrowerSize = 4;
419 const unsigned BaseSize = 6;
420 const unsigned WiderSize = 8;
421 APInt NegativeFitsNarrower(BaseSize, -4, /*isSigned*/ true);
422 APInt NegativeDoesntFitNarrower(BaseSize, -28, /*isSigned*/ true);
423 APInt PositiveFitsNarrower(BaseSize, 14);
424 APInt PositiveDoesntFitNarrower(BaseSize, 36);
425 auto InitKnownBits = [&](KnownBits &Res, const APInt &Input) {
426 Res = KnownBits(Input.getBitWidth());
427 Res.One = Input;
428 Res.Zero = ~Input;
429 };
430
431 for (unsigned Size : {NarrowerSize, BaseSize, WiderSize}) {
432 for (const APInt &Input :
433 {NegativeFitsNarrower, NegativeDoesntFitNarrower, PositiveFitsNarrower,
434 PositiveDoesntFitNarrower}) {
435 KnownBits Test;
436 InitKnownBits(Test, Input);
437 KnownBits Baseline;
438 InitKnownBits(Baseline, Input.sextOrTrunc(Size));
439 Test = Test.sextOrTrunc(Size);
440 EXPECT_EQ(Test.One, Baseline.One);
441 EXPECT_EQ(Test.Zero, Baseline.Zero);
442 }
443 }
444 }
445
TEST(KnownBitsTest,SExtInReg)446 TEST(KnownBitsTest, SExtInReg) {
447 unsigned Bits = 4;
448 for (unsigned FromBits = 1; FromBits <= Bits; ++FromBits) {
449 ForeachKnownBits(Bits, [&](const KnownBits &Known) {
450 APInt CommonOne = APInt::getAllOnesValue(Bits);
451 APInt CommonZero = APInt::getAllOnesValue(Bits);
452 unsigned ExtBits = Bits - FromBits;
453 ForeachNumInKnownBits(Known, [&](const APInt &N) {
454 APInt Ext = N << ExtBits;
455 Ext.ashrInPlace(ExtBits);
456 CommonOne &= Ext;
457 CommonZero &= ~Ext;
458 });
459 KnownBits KnownSExtInReg = Known.sextInReg(FromBits);
460 EXPECT_EQ(CommonOne, KnownSExtInReg.One);
461 EXPECT_EQ(CommonZero, KnownSExtInReg.Zero);
462 });
463 }
464 }
465
TEST(KnownBitsTest,CommonBitsSet)466 TEST(KnownBitsTest, CommonBitsSet) {
467 unsigned Bits = 4;
468 ForeachKnownBits(Bits, [&](const KnownBits &Known1) {
469 ForeachKnownBits(Bits, [&](const KnownBits &Known2) {
470 bool HasCommonBitsSet = false;
471 ForeachNumInKnownBits(Known1, [&](const APInt &N1) {
472 ForeachNumInKnownBits(Known2, [&](const APInt &N2) {
473 HasCommonBitsSet |= N1.intersects(N2);
474 });
475 });
476 EXPECT_EQ(!HasCommonBitsSet,
477 KnownBits::haveNoCommonBitsSet(Known1, Known2));
478 });
479 });
480 }
481
482 } // end anonymous namespace
483