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 
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 =
45             KnownBits::computeForAddCarry(Known1, Known2, KnownCarry);
46         EXPECT_EQ(Known, KnownComputed);
47       });
48     });
49   });
50 }
51 
52 static void TestAddSubExhaustive(bool IsAdd) {
53   unsigned Bits = 4;
54   ForeachKnownBits(Bits, [&](const KnownBits &Known1) {
55     ForeachKnownBits(Bits, [&](const KnownBits &Known2) {
56       KnownBits Known(Bits), KnownNSW(Bits);
57       Known.Zero.setAllBits();
58       Known.One.setAllBits();
59       KnownNSW.Zero.setAllBits();
60       KnownNSW.One.setAllBits();
61 
62       ForeachNumInKnownBits(Known1, [&](const APInt &N1) {
63         ForeachNumInKnownBits(Known2, [&](const APInt &N2) {
64           bool Overflow;
65           APInt Res;
66           if (IsAdd)
67             Res = N1.sadd_ov(N2, Overflow);
68           else
69             Res = N1.ssub_ov(N2, Overflow);
70 
71           Known.One &= Res;
72           Known.Zero &= ~Res;
73 
74           if (!Overflow) {
75             KnownNSW.One &= Res;
76             KnownNSW.Zero &= ~Res;
77           }
78         });
79       });
80 
81       KnownBits KnownComputed =
82           KnownBits::computeForAddSub(IsAdd, /*NSW*/ false, Known1, Known2);
83       EXPECT_EQ(Known, KnownComputed);
84 
85       // The NSW calculation is not precise, only check that it's
86       // conservatively correct.
87       KnownBits KnownNSWComputed = KnownBits::computeForAddSub(
88           IsAdd, /*NSW*/true, Known1, Known2);
89       EXPECT_TRUE(KnownNSWComputed.Zero.isSubsetOf(KnownNSW.Zero));
90       EXPECT_TRUE(KnownNSWComputed.One.isSubsetOf(KnownNSW.One));
91     });
92   });
93 }
94 
95 TEST(KnownBitsTest, AddSubExhaustive) {
96   TestAddSubExhaustive(true);
97   TestAddSubExhaustive(false);
98 }
99 
100 TEST(KnownBitsTest, BinaryExhaustive) {
101   unsigned Bits = 4;
102   ForeachKnownBits(Bits, [&](const KnownBits &Known1) {
103     ForeachKnownBits(Bits, [&](const KnownBits &Known2) {
104       KnownBits KnownAnd(Bits);
105       KnownAnd.Zero.setAllBits();
106       KnownAnd.One.setAllBits();
107       KnownBits KnownOr(KnownAnd);
108       KnownBits KnownXor(KnownAnd);
109       KnownBits KnownUMax(KnownAnd);
110       KnownBits KnownUMin(KnownAnd);
111       KnownBits KnownSMax(KnownAnd);
112       KnownBits KnownSMin(KnownAnd);
113       KnownBits KnownMul(KnownAnd);
114       KnownBits KnownMulHS(KnownAnd);
115       KnownBits KnownMulHU(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           Res = (N1.sext(2 * Bits) * N2.sext(2 * Bits)).extractBits(Bits, Bits);
160           KnownMulHS.One &= Res;
161           KnownMulHS.Zero &= ~Res;
162 
163           Res = (N1.zext(2 * Bits) * N2.zext(2 * Bits)).extractBits(Bits, Bits);
164           KnownMulHU.One &= Res;
165           KnownMulHU.Zero &= ~Res;
166 
167           if (!N2.isZero()) {
168             Res = N1.udiv(N2);
169             KnownUDiv.One &= Res;
170             KnownUDiv.Zero &= ~Res;
171 
172             Res = N1.urem(N2);
173             KnownURem.One &= Res;
174             KnownURem.Zero &= ~Res;
175 
176             Res = N1.srem(N2);
177             KnownSRem.One &= Res;
178             KnownSRem.Zero &= ~Res;
179           }
180 
181           if (N2.ult(1ULL << N1.getBitWidth())) {
182             Res = N1.shl(N2);
183             KnownShl.One &= Res;
184             KnownShl.Zero &= ~Res;
185 
186             Res = N1.lshr(N2);
187             KnownLShr.One &= Res;
188             KnownLShr.Zero &= ~Res;
189 
190             Res = N1.ashr(N2);
191             KnownAShr.One &= Res;
192             KnownAShr.Zero &= ~Res;
193           } else {
194             KnownShl.resetAll();
195             KnownLShr.resetAll();
196             KnownAShr.resetAll();
197           }
198         });
199       });
200 
201       KnownBits ComputedAnd = Known1 & Known2;
202       EXPECT_EQ(KnownAnd, ComputedAnd);
203 
204       KnownBits ComputedOr = Known1 | Known2;
205       EXPECT_EQ(KnownOr, ComputedOr);
206 
207       KnownBits ComputedXor = Known1 ^ Known2;
208       EXPECT_EQ(KnownXor, ComputedXor);
209 
210       KnownBits ComputedUMax = KnownBits::umax(Known1, Known2);
211       EXPECT_EQ(KnownUMax, ComputedUMax);
212 
213       KnownBits ComputedUMin = KnownBits::umin(Known1, Known2);
214       EXPECT_EQ(KnownUMin, ComputedUMin);
215 
216       KnownBits ComputedSMax = KnownBits::smax(Known1, Known2);
217       EXPECT_EQ(KnownSMax, ComputedSMax);
218 
219       KnownBits ComputedSMin = KnownBits::smin(Known1, Known2);
220       EXPECT_EQ(KnownSMin, ComputedSMin);
221 
222       // The following are conservatively correct, but not guaranteed to be
223       // precise.
224       KnownBits ComputedMul = KnownBits::mul(Known1, Known2);
225       EXPECT_TRUE(ComputedMul.Zero.isSubsetOf(KnownMul.Zero));
226       EXPECT_TRUE(ComputedMul.One.isSubsetOf(KnownMul.One));
227 
228       KnownBits ComputedMulHS = KnownBits::mulhs(Known1, Known2);
229       EXPECT_TRUE(ComputedMulHS.Zero.isSubsetOf(KnownMulHS.Zero));
230       EXPECT_TRUE(ComputedMulHS.One.isSubsetOf(KnownMulHS.One));
231 
232       KnownBits ComputedMulHU = KnownBits::mulhu(Known1, Known2);
233       EXPECT_TRUE(ComputedMulHU.Zero.isSubsetOf(KnownMulHU.Zero));
234       EXPECT_TRUE(ComputedMulHU.One.isSubsetOf(KnownMulHU.One));
235 
236       KnownBits ComputedUDiv = KnownBits::udiv(Known1, Known2);
237       EXPECT_TRUE(ComputedUDiv.Zero.isSubsetOf(KnownUDiv.Zero));
238       EXPECT_TRUE(ComputedUDiv.One.isSubsetOf(KnownUDiv.One));
239 
240       KnownBits ComputedURem = KnownBits::urem(Known1, Known2);
241       EXPECT_TRUE(ComputedURem.Zero.isSubsetOf(KnownURem.Zero));
242       EXPECT_TRUE(ComputedURem.One.isSubsetOf(KnownURem.One));
243 
244       KnownBits ComputedSRem = KnownBits::srem(Known1, Known2);
245       EXPECT_TRUE(ComputedSRem.Zero.isSubsetOf(KnownSRem.Zero));
246       EXPECT_TRUE(ComputedSRem.One.isSubsetOf(KnownSRem.One));
247 
248       KnownBits ComputedShl = KnownBits::shl(Known1, Known2);
249       EXPECT_TRUE(ComputedShl.Zero.isSubsetOf(KnownShl.Zero));
250       EXPECT_TRUE(ComputedShl.One.isSubsetOf(KnownShl.One));
251 
252       KnownBits ComputedLShr = KnownBits::lshr(Known1, Known2);
253       EXPECT_TRUE(ComputedLShr.Zero.isSubsetOf(KnownLShr.Zero));
254       EXPECT_TRUE(ComputedLShr.One.isSubsetOf(KnownLShr.One));
255 
256       KnownBits ComputedAShr = KnownBits::ashr(Known1, Known2);
257       EXPECT_TRUE(ComputedAShr.Zero.isSubsetOf(KnownAShr.Zero));
258       EXPECT_TRUE(ComputedAShr.One.isSubsetOf(KnownAShr.One));
259     });
260   });
261 
262   // Also test 'unary' binary cases where the same argument is repeated.
263   ForeachKnownBits(Bits, [&](const KnownBits &Known) {
264     KnownBits KnownMul(Bits);
265     KnownMul.Zero.setAllBits();
266     KnownMul.One.setAllBits();
267 
268     ForeachNumInKnownBits(Known, [&](const APInt &N) {
269       APInt Res = N * N;
270       KnownMul.One &= Res;
271       KnownMul.Zero &= ~Res;
272     });
273 
274     KnownBits ComputedMul = KnownBits::mul(Known, Known, /*SelfMultiply*/ true);
275     EXPECT_TRUE(ComputedMul.Zero.isSubsetOf(KnownMul.Zero));
276     EXPECT_TRUE(ComputedMul.One.isSubsetOf(KnownMul.One));
277   });
278 }
279 
280 TEST(KnownBitsTest, UnaryExhaustive) {
281   unsigned Bits = 4;
282   ForeachKnownBits(Bits, [&](const KnownBits &Known) {
283     KnownBits KnownAbs(Bits);
284     KnownAbs.Zero.setAllBits();
285     KnownAbs.One.setAllBits();
286     KnownBits KnownAbsPoison(KnownAbs);
287 
288     ForeachNumInKnownBits(Known, [&](const APInt &N) {
289       APInt Res = N.abs();
290       KnownAbs.One &= Res;
291       KnownAbs.Zero &= ~Res;
292 
293       if (!N.isMinSignedValue()) {
294         KnownAbsPoison.One &= Res;
295         KnownAbsPoison.Zero &= ~Res;
296       }
297     });
298 
299     // abs() is conservatively correct, but not guaranteed to be precise.
300     KnownBits ComputedAbs = Known.abs();
301     EXPECT_TRUE(ComputedAbs.Zero.isSubsetOf(KnownAbs.Zero));
302     EXPECT_TRUE(ComputedAbs.One.isSubsetOf(KnownAbs.One));
303 
304     KnownBits ComputedAbsPoison = Known.abs(true);
305     EXPECT_TRUE(ComputedAbsPoison.Zero.isSubsetOf(KnownAbsPoison.Zero));
306     EXPECT_TRUE(ComputedAbsPoison.One.isSubsetOf(KnownAbsPoison.One));
307   });
308 }
309 
310 TEST(KnownBitsTest, ICmpExhaustive) {
311   unsigned Bits = 4;
312   ForeachKnownBits(Bits, [&](const KnownBits &Known1) {
313     ForeachKnownBits(Bits, [&](const KnownBits &Known2) {
314       bool AllEQ = true, NoneEQ = true;
315       bool AllNE = true, NoneNE = true;
316       bool AllUGT = true, NoneUGT = true;
317       bool AllUGE = true, NoneUGE = true;
318       bool AllULT = true, NoneULT = true;
319       bool AllULE = true, NoneULE = true;
320       bool AllSGT = true, NoneSGT = true;
321       bool AllSGE = true, NoneSGE = true;
322       bool AllSLT = true, NoneSLT = true;
323       bool AllSLE = true, NoneSLE = true;
324 
325       ForeachNumInKnownBits(Known1, [&](const APInt &N1) {
326         ForeachNumInKnownBits(Known2, [&](const APInt &N2) {
327           AllEQ &= N1.eq(N2);
328           AllNE &= N1.ne(N2);
329           AllUGT &= N1.ugt(N2);
330           AllUGE &= N1.uge(N2);
331           AllULT &= N1.ult(N2);
332           AllULE &= N1.ule(N2);
333           AllSGT &= N1.sgt(N2);
334           AllSGE &= N1.sge(N2);
335           AllSLT &= N1.slt(N2);
336           AllSLE &= N1.sle(N2);
337           NoneEQ &= !N1.eq(N2);
338           NoneNE &= !N1.ne(N2);
339           NoneUGT &= !N1.ugt(N2);
340           NoneUGE &= !N1.uge(N2);
341           NoneULT &= !N1.ult(N2);
342           NoneULE &= !N1.ule(N2);
343           NoneSGT &= !N1.sgt(N2);
344           NoneSGE &= !N1.sge(N2);
345           NoneSLT &= !N1.slt(N2);
346           NoneSLE &= !N1.sle(N2);
347         });
348       });
349 
350       Optional<bool> KnownEQ = KnownBits::eq(Known1, Known2);
351       Optional<bool> KnownNE = KnownBits::ne(Known1, Known2);
352       Optional<bool> KnownUGT = KnownBits::ugt(Known1, Known2);
353       Optional<bool> KnownUGE = KnownBits::uge(Known1, Known2);
354       Optional<bool> KnownULT = KnownBits::ult(Known1, Known2);
355       Optional<bool> KnownULE = KnownBits::ule(Known1, Known2);
356       Optional<bool> KnownSGT = KnownBits::sgt(Known1, Known2);
357       Optional<bool> KnownSGE = KnownBits::sge(Known1, Known2);
358       Optional<bool> KnownSLT = KnownBits::slt(Known1, Known2);
359       Optional<bool> KnownSLE = KnownBits::sle(Known1, Known2);
360 
361       EXPECT_EQ(AllEQ || NoneEQ, KnownEQ.has_value());
362       EXPECT_EQ(AllNE || NoneNE, KnownNE.has_value());
363       EXPECT_EQ(AllUGT || NoneUGT, KnownUGT.has_value());
364       EXPECT_EQ(AllUGE || NoneUGE, KnownUGE.has_value());
365       EXPECT_EQ(AllULT || NoneULT, KnownULT.has_value());
366       EXPECT_EQ(AllULE || NoneULE, KnownULE.has_value());
367       EXPECT_EQ(AllSGT || NoneSGT, KnownSGT.has_value());
368       EXPECT_EQ(AllSGE || NoneSGE, KnownSGE.has_value());
369       EXPECT_EQ(AllSLT || NoneSLT, KnownSLT.has_value());
370       EXPECT_EQ(AllSLE || NoneSLE, KnownSLE.has_value());
371 
372       EXPECT_EQ(AllEQ, KnownEQ.has_value() && KnownEQ.value());
373       EXPECT_EQ(AllNE, KnownNE.has_value() && KnownNE.value());
374       EXPECT_EQ(AllUGT, KnownUGT.has_value() && KnownUGT.value());
375       EXPECT_EQ(AllUGE, KnownUGE.has_value() && KnownUGE.value());
376       EXPECT_EQ(AllULT, KnownULT.has_value() && KnownULT.value());
377       EXPECT_EQ(AllULE, KnownULE.has_value() && KnownULE.value());
378       EXPECT_EQ(AllSGT, KnownSGT.has_value() && KnownSGT.value());
379       EXPECT_EQ(AllSGE, KnownSGE.has_value() && KnownSGE.value());
380       EXPECT_EQ(AllSLT, KnownSLT.has_value() && KnownSLT.value());
381       EXPECT_EQ(AllSLE, KnownSLE.has_value() && KnownSLE.value());
382 
383       EXPECT_EQ(NoneEQ, KnownEQ.has_value() && !KnownEQ.value());
384       EXPECT_EQ(NoneNE, KnownNE.has_value() && !KnownNE.value());
385       EXPECT_EQ(NoneUGT, KnownUGT.has_value() && !KnownUGT.value());
386       EXPECT_EQ(NoneUGE, KnownUGE.has_value() && !KnownUGE.value());
387       EXPECT_EQ(NoneULT, KnownULT.has_value() && !KnownULT.value());
388       EXPECT_EQ(NoneULE, KnownULE.has_value() && !KnownULE.value());
389       EXPECT_EQ(NoneSGT, KnownSGT.has_value() && !KnownSGT.value());
390       EXPECT_EQ(NoneSGE, KnownSGE.has_value() && !KnownSGE.value());
391       EXPECT_EQ(NoneSLT, KnownSLT.has_value() && !KnownSLT.value());
392       EXPECT_EQ(NoneSLE, KnownSLE.has_value() && !KnownSLE.value());
393     });
394   });
395 }
396 
397 TEST(KnownBitsTest, GetMinMaxVal) {
398   unsigned Bits = 4;
399   ForeachKnownBits(Bits, [&](const KnownBits &Known) {
400     APInt Min = APInt::getMaxValue(Bits);
401     APInt Max = APInt::getMinValue(Bits);
402     ForeachNumInKnownBits(Known, [&](const APInt &N) {
403       Min = APIntOps::umin(Min, N);
404       Max = APIntOps::umax(Max, N);
405     });
406     EXPECT_EQ(Min, Known.getMinValue());
407     EXPECT_EQ(Max, Known.getMaxValue());
408   });
409 }
410 
411 TEST(KnownBitsTest, GetSignedMinMaxVal) {
412   unsigned Bits = 4;
413   ForeachKnownBits(Bits, [&](const KnownBits &Known) {
414     APInt Min = APInt::getSignedMaxValue(Bits);
415     APInt Max = APInt::getSignedMinValue(Bits);
416     ForeachNumInKnownBits(Known, [&](const APInt &N) {
417       Min = APIntOps::smin(Min, N);
418       Max = APIntOps::smax(Max, N);
419     });
420     EXPECT_EQ(Min, Known.getSignedMinValue());
421     EXPECT_EQ(Max, Known.getSignedMaxValue());
422   });
423 }
424 
425 TEST(KnownBitsTest, CountMaxActiveBits) {
426   unsigned Bits = 4;
427   ForeachKnownBits(Bits, [&](const KnownBits &Known) {
428     unsigned Expected = 0;
429     ForeachNumInKnownBits(Known, [&](const APInt &N) {
430       Expected = std::max(Expected, N.getActiveBits());
431     });
432     EXPECT_EQ(Expected, Known.countMaxActiveBits());
433   });
434 }
435 
436 TEST(KnownBitsTest, CountMaxSignificantBits) {
437   unsigned Bits = 4;
438   ForeachKnownBits(Bits, [&](const KnownBits &Known) {
439     unsigned Expected = 0;
440     ForeachNumInKnownBits(Known, [&](const APInt &N) {
441       Expected = std::max(Expected, N.getSignificantBits());
442     });
443     EXPECT_EQ(Expected, Known.countMaxSignificantBits());
444   });
445 }
446 
447 TEST(KnownBitsTest, SExtOrTrunc) {
448   const unsigned NarrowerSize = 4;
449   const unsigned BaseSize = 6;
450   const unsigned WiderSize = 8;
451   APInt NegativeFitsNarrower(BaseSize, -4, /*isSigned*/ true);
452   APInt NegativeDoesntFitNarrower(BaseSize, -28, /*isSigned*/ true);
453   APInt PositiveFitsNarrower(BaseSize, 14);
454   APInt PositiveDoesntFitNarrower(BaseSize, 36);
455   auto InitKnownBits = [&](KnownBits &Res, const APInt &Input) {
456     Res = KnownBits(Input.getBitWidth());
457     Res.One = Input;
458     Res.Zero = ~Input;
459   };
460 
461   for (unsigned Size : {NarrowerSize, BaseSize, WiderSize}) {
462     for (const APInt &Input :
463          {NegativeFitsNarrower, NegativeDoesntFitNarrower, PositiveFitsNarrower,
464           PositiveDoesntFitNarrower}) {
465       KnownBits Test;
466       InitKnownBits(Test, Input);
467       KnownBits Baseline;
468       InitKnownBits(Baseline, Input.sextOrTrunc(Size));
469       Test = Test.sextOrTrunc(Size);
470       EXPECT_EQ(Test, Baseline);
471     }
472   }
473 }
474 
475 TEST(KnownBitsTest, SExtInReg) {
476   unsigned Bits = 4;
477   for (unsigned FromBits = 1; FromBits <= Bits; ++FromBits) {
478     ForeachKnownBits(Bits, [&](const KnownBits &Known) {
479       APInt CommonOne = APInt::getAllOnes(Bits);
480       APInt CommonZero = APInt::getAllOnes(Bits);
481       unsigned ExtBits = Bits - FromBits;
482       ForeachNumInKnownBits(Known, [&](const APInt &N) {
483         APInt Ext = N << ExtBits;
484         Ext.ashrInPlace(ExtBits);
485         CommonOne &= Ext;
486         CommonZero &= ~Ext;
487       });
488       KnownBits KnownSExtInReg = Known.sextInReg(FromBits);
489       EXPECT_EQ(CommonOne, KnownSExtInReg.One);
490       EXPECT_EQ(CommonZero, KnownSExtInReg.Zero);
491     });
492   }
493 }
494 
495 TEST(KnownBitsTest, CommonBitsSet) {
496   unsigned Bits = 4;
497   ForeachKnownBits(Bits, [&](const KnownBits &Known1) {
498     ForeachKnownBits(Bits, [&](const KnownBits &Known2) {
499       bool HasCommonBitsSet = false;
500       ForeachNumInKnownBits(Known1, [&](const APInt &N1) {
501         ForeachNumInKnownBits(Known2, [&](const APInt &N2) {
502           HasCommonBitsSet |= N1.intersects(N2);
503         });
504       });
505       EXPECT_EQ(!HasCommonBitsSet,
506                 KnownBits::haveNoCommonBitsSet(Known1, Known2));
507     });
508   });
509 }
510 
511 } // end anonymous namespace
512