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 
117       ForeachNumInKnownBits(Known1, [&](const APInt &N1) {
118         ForeachNumInKnownBits(Known2, [&](const APInt &N2) {
119           APInt Res;
120 
121           Res = N1 & N2;
122           KnownAnd.One &= Res;
123           KnownAnd.Zero &= ~Res;
124 
125           Res = N1 | N2;
126           KnownOr.One &= Res;
127           KnownOr.Zero &= ~Res;
128 
129           Res = N1 ^ N2;
130           KnownXor.One &= Res;
131           KnownXor.Zero &= ~Res;
132 
133           Res = APIntOps::umax(N1, N2);
134           KnownUMax.One &= Res;
135           KnownUMax.Zero &= ~Res;
136 
137           Res = APIntOps::umin(N1, N2);
138           KnownUMin.One &= Res;
139           KnownUMin.Zero &= ~Res;
140 
141           Res = APIntOps::smax(N1, N2);
142           KnownSMax.One &= Res;
143           KnownSMax.Zero &= ~Res;
144 
145           Res = APIntOps::smin(N1, N2);
146           KnownSMin.One &= Res;
147           KnownSMin.Zero &= ~Res;
148 
149           Res = N1 * N2;
150           KnownMul.One &= Res;
151           KnownMul.Zero &= ~Res;
152         });
153       });
154 
155       KnownBits ComputedAnd = Known1 & Known2;
156       EXPECT_EQ(KnownAnd.Zero, ComputedAnd.Zero);
157       EXPECT_EQ(KnownAnd.One, ComputedAnd.One);
158 
159       KnownBits ComputedOr = Known1 | Known2;
160       EXPECT_EQ(KnownOr.Zero, ComputedOr.Zero);
161       EXPECT_EQ(KnownOr.One, ComputedOr.One);
162 
163       KnownBits ComputedXor = Known1 ^ Known2;
164       EXPECT_EQ(KnownXor.Zero, ComputedXor.Zero);
165       EXPECT_EQ(KnownXor.One, ComputedXor.One);
166 
167       KnownBits ComputedUMax = KnownBits::umax(Known1, Known2);
168       EXPECT_EQ(KnownUMax.Zero, ComputedUMax.Zero);
169       EXPECT_EQ(KnownUMax.One, ComputedUMax.One);
170 
171       KnownBits ComputedUMin = KnownBits::umin(Known1, Known2);
172       EXPECT_EQ(KnownUMin.Zero, ComputedUMin.Zero);
173       EXPECT_EQ(KnownUMin.One, ComputedUMin.One);
174 
175       KnownBits ComputedSMax = KnownBits::smax(Known1, Known2);
176       EXPECT_EQ(KnownSMax.Zero, ComputedSMax.Zero);
177       EXPECT_EQ(KnownSMax.One, ComputedSMax.One);
178 
179       KnownBits ComputedSMin = KnownBits::smin(Known1, Known2);
180       EXPECT_EQ(KnownSMin.Zero, ComputedSMin.Zero);
181       EXPECT_EQ(KnownSMin.One, ComputedSMin.One);
182 
183       // ComputedMul is conservatively correct, but not guaranteed to be
184       // precise.
185       KnownBits ComputedMul = KnownBits::computeForMul(Known1, Known2);
186       EXPECT_TRUE(ComputedMul.Zero.isSubsetOf(KnownMul.Zero));
187       EXPECT_TRUE(ComputedMul.One.isSubsetOf(KnownMul.One));
188     });
189   });
190 }
191 
192 TEST(KnownBitsTest, GetMinMaxVal) {
193   unsigned Bits = 4;
194   ForeachKnownBits(Bits, [&](const KnownBits &Known) {
195     APInt Min = APInt::getMaxValue(Bits);
196     APInt Max = APInt::getMinValue(Bits);
197     ForeachNumInKnownBits(Known, [&](const APInt &N) {
198       Min = APIntOps::umin(Min, N);
199       Max = APIntOps::umax(Max, N);
200     });
201     EXPECT_EQ(Min, Known.getMinValue());
202     EXPECT_EQ(Max, Known.getMaxValue());
203   });
204 }
205 
206 TEST(KnownBitsTest, SExtOrTrunc) {
207   const unsigned NarrowerSize = 4;
208   const unsigned BaseSize = 6;
209   const unsigned WiderSize = 8;
210   APInt NegativeFitsNarrower(BaseSize, -4, /*isSigned*/ true);
211   APInt NegativeDoesntFitNarrower(BaseSize, -28, /*isSigned*/ true);
212   APInt PositiveFitsNarrower(BaseSize, 14);
213   APInt PositiveDoesntFitNarrower(BaseSize, 36);
214   auto InitKnownBits = [&](KnownBits &Res, const APInt &Input) {
215     Res = KnownBits(Input.getBitWidth());
216     Res.One = Input;
217     Res.Zero = ~Input;
218   };
219 
220   for (unsigned Size : {NarrowerSize, BaseSize, WiderSize}) {
221     for (const APInt &Input :
222          {NegativeFitsNarrower, NegativeDoesntFitNarrower, PositiveFitsNarrower,
223           PositiveDoesntFitNarrower}) {
224       KnownBits Test;
225       InitKnownBits(Test, Input);
226       KnownBits Baseline;
227       InitKnownBits(Baseline, Input.sextOrTrunc(Size));
228       Test = Test.sextOrTrunc(Size);
229       EXPECT_EQ(Test.One, Baseline.One);
230       EXPECT_EQ(Test.Zero, Baseline.Zero);
231     }
232   }
233 }
234 
235 } // end anonymous namespace
236