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 = 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 
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 
97 TEST(KnownBitsTest, AddSubExhaustive) {
98   TestAddSubExhaustive(true);
99   TestAddSubExhaustive(false);
100 }
101 
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 
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 
284 TEST(KnownBitsTest, ICmpExhaustive) {
285   unsigned Bits = 4;
286   ForeachKnownBits(Bits, [&](const KnownBits &Known1) {
287     ForeachKnownBits(Bits, [&](const KnownBits &Known2) {
288       bool AllEQ = true, NoneEQ = true;
289       bool AllNE = true, NoneNE = true;
290       bool AllUGT = true, NoneUGT = true;
291       bool AllUGE = true, NoneUGE = true;
292       bool AllULT = true, NoneULT = true;
293       bool AllULE = true, NoneULE = true;
294       bool AllSGT = true, NoneSGT = true;
295       bool AllSGE = true, NoneSGE = true;
296       bool AllSLT = true, NoneSLT = true;
297       bool AllSLE = true, NoneSLE = true;
298 
299       ForeachNumInKnownBits(Known1, [&](const APInt &N1) {
300         ForeachNumInKnownBits(Known2, [&](const APInt &N2) {
301           AllEQ &= N1.eq(N2);
302           AllNE &= N1.ne(N2);
303           AllUGT &= N1.ugt(N2);
304           AllUGE &= N1.uge(N2);
305           AllULT &= N1.ult(N2);
306           AllULE &= N1.ule(N2);
307           AllSGT &= N1.sgt(N2);
308           AllSGE &= N1.sge(N2);
309           AllSLT &= N1.slt(N2);
310           AllSLE &= N1.sle(N2);
311           NoneEQ &= !N1.eq(N2);
312           NoneNE &= !N1.ne(N2);
313           NoneUGT &= !N1.ugt(N2);
314           NoneUGE &= !N1.uge(N2);
315           NoneULT &= !N1.ult(N2);
316           NoneULE &= !N1.ule(N2);
317           NoneSGT &= !N1.sgt(N2);
318           NoneSGE &= !N1.sge(N2);
319           NoneSLT &= !N1.slt(N2);
320           NoneSLE &= !N1.sle(N2);
321         });
322       });
323 
324       Optional<bool> KnownEQ = KnownBits::eq(Known1, Known2);
325       Optional<bool> KnownNE = KnownBits::ne(Known1, Known2);
326       Optional<bool> KnownUGT = KnownBits::ugt(Known1, Known2);
327       Optional<bool> KnownUGE = KnownBits::uge(Known1, Known2);
328       Optional<bool> KnownULT = KnownBits::ult(Known1, Known2);
329       Optional<bool> KnownULE = KnownBits::ule(Known1, Known2);
330       Optional<bool> KnownSGT = KnownBits::sgt(Known1, Known2);
331       Optional<bool> KnownSGE = KnownBits::sge(Known1, Known2);
332       Optional<bool> KnownSLT = KnownBits::slt(Known1, Known2);
333       Optional<bool> KnownSLE = KnownBits::sle(Known1, Known2);
334 
335       EXPECT_EQ(AllEQ || NoneEQ, KnownEQ.hasValue());
336       EXPECT_EQ(AllNE || NoneNE, KnownNE.hasValue());
337       EXPECT_EQ(AllUGT || NoneUGT, KnownUGT.hasValue());
338       EXPECT_EQ(AllUGE || NoneUGE, KnownUGE.hasValue());
339       EXPECT_EQ(AllULT || NoneULT, KnownULT.hasValue());
340       EXPECT_EQ(AllULE || NoneULE, KnownULE.hasValue());
341       EXPECT_EQ(AllSGT || NoneSGT, KnownSGT.hasValue());
342       EXPECT_EQ(AllSGE || NoneSGE, KnownSGE.hasValue());
343       EXPECT_EQ(AllSLT || NoneSLT, KnownSLT.hasValue());
344       EXPECT_EQ(AllSLE || NoneSLE, KnownSLE.hasValue());
345 
346       EXPECT_EQ(AllEQ, KnownEQ.hasValue() && KnownEQ.getValue());
347       EXPECT_EQ(AllNE, KnownNE.hasValue() && KnownNE.getValue());
348       EXPECT_EQ(AllUGT, KnownUGT.hasValue() && KnownUGT.getValue());
349       EXPECT_EQ(AllUGE, KnownUGE.hasValue() && KnownUGE.getValue());
350       EXPECT_EQ(AllULT, KnownULT.hasValue() && KnownULT.getValue());
351       EXPECT_EQ(AllULE, KnownULE.hasValue() && KnownULE.getValue());
352       EXPECT_EQ(AllSGT, KnownSGT.hasValue() && KnownSGT.getValue());
353       EXPECT_EQ(AllSGE, KnownSGE.hasValue() && KnownSGE.getValue());
354       EXPECT_EQ(AllSLT, KnownSLT.hasValue() && KnownSLT.getValue());
355       EXPECT_EQ(AllSLE, KnownSLE.hasValue() && KnownSLE.getValue());
356 
357       EXPECT_EQ(NoneEQ, KnownEQ.hasValue() && !KnownEQ.getValue());
358       EXPECT_EQ(NoneNE, KnownNE.hasValue() && !KnownNE.getValue());
359       EXPECT_EQ(NoneUGT, KnownUGT.hasValue() && !KnownUGT.getValue());
360       EXPECT_EQ(NoneUGE, KnownUGE.hasValue() && !KnownUGE.getValue());
361       EXPECT_EQ(NoneULT, KnownULT.hasValue() && !KnownULT.getValue());
362       EXPECT_EQ(NoneULE, KnownULE.hasValue() && !KnownULE.getValue());
363       EXPECT_EQ(NoneSGT, KnownSGT.hasValue() && !KnownSGT.getValue());
364       EXPECT_EQ(NoneSGE, KnownSGE.hasValue() && !KnownSGE.getValue());
365       EXPECT_EQ(NoneSLT, KnownSLT.hasValue() && !KnownSLT.getValue());
366       EXPECT_EQ(NoneSLE, KnownSLE.hasValue() && !KnownSLE.getValue());
367     });
368   });
369 }
370 
371 TEST(KnownBitsTest, GetMinMaxVal) {
372   unsigned Bits = 4;
373   ForeachKnownBits(Bits, [&](const KnownBits &Known) {
374     APInt Min = APInt::getMaxValue(Bits);
375     APInt Max = APInt::getMinValue(Bits);
376     ForeachNumInKnownBits(Known, [&](const APInt &N) {
377       Min = APIntOps::umin(Min, N);
378       Max = APIntOps::umax(Max, N);
379     });
380     EXPECT_EQ(Min, Known.getMinValue());
381     EXPECT_EQ(Max, Known.getMaxValue());
382   });
383 }
384 
385 TEST(KnownBitsTest, GetSignedMinMaxVal) {
386   unsigned Bits = 4;
387   ForeachKnownBits(Bits, [&](const KnownBits &Known) {
388     APInt Min = APInt::getSignedMaxValue(Bits);
389     APInt Max = APInt::getSignedMinValue(Bits);
390     ForeachNumInKnownBits(Known, [&](const APInt &N) {
391       Min = APIntOps::smin(Min, N);
392       Max = APIntOps::smax(Max, N);
393     });
394     EXPECT_EQ(Min, Known.getSignedMinValue());
395     EXPECT_EQ(Max, Known.getSignedMaxValue());
396   });
397 }
398 
399 TEST(KnownBitsTest, SExtOrTrunc) {
400   const unsigned NarrowerSize = 4;
401   const unsigned BaseSize = 6;
402   const unsigned WiderSize = 8;
403   APInt NegativeFitsNarrower(BaseSize, -4, /*isSigned*/ true);
404   APInt NegativeDoesntFitNarrower(BaseSize, -28, /*isSigned*/ true);
405   APInt PositiveFitsNarrower(BaseSize, 14);
406   APInt PositiveDoesntFitNarrower(BaseSize, 36);
407   auto InitKnownBits = [&](KnownBits &Res, const APInt &Input) {
408     Res = KnownBits(Input.getBitWidth());
409     Res.One = Input;
410     Res.Zero = ~Input;
411   };
412 
413   for (unsigned Size : {NarrowerSize, BaseSize, WiderSize}) {
414     for (const APInt &Input :
415          {NegativeFitsNarrower, NegativeDoesntFitNarrower, PositiveFitsNarrower,
416           PositiveDoesntFitNarrower}) {
417       KnownBits Test;
418       InitKnownBits(Test, Input);
419       KnownBits Baseline;
420       InitKnownBits(Baseline, Input.sextOrTrunc(Size));
421       Test = Test.sextOrTrunc(Size);
422       EXPECT_EQ(Test.One, Baseline.One);
423       EXPECT_EQ(Test.Zero, Baseline.Zero);
424     }
425   }
426 }
427 
428 TEST(KnownBitsTest, SExtInReg) {
429   unsigned Bits = 4;
430   for (unsigned FromBits = 1; FromBits <= Bits; ++FromBits) {
431     ForeachKnownBits(Bits, [&](const KnownBits &Known) {
432       APInt CommonOne = APInt::getAllOnesValue(Bits);
433       APInt CommonZero = APInt::getAllOnesValue(Bits);
434       unsigned ExtBits = Bits - FromBits;
435       ForeachNumInKnownBits(Known, [&](const APInt &N) {
436         APInt Ext = N << ExtBits;
437         Ext.ashrInPlace(ExtBits);
438         CommonOne &= Ext;
439         CommonZero &= ~Ext;
440       });
441       KnownBits KnownSExtInReg = Known.sextInReg(FromBits);
442       EXPECT_EQ(CommonOne, KnownSExtInReg.One);
443       EXPECT_EQ(CommonZero, KnownSExtInReg.Zero);
444     });
445   }
446 }
447 
448 } // end anonymous namespace
449