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 "llvm/ADT/ArrayRef.h" |
16 | #include "llvm/ADT/StringRef.h" |
17 | #include "llvm/ADT/Twine.h" |
18 | #include "gtest/gtest.h" |
19 | |
20 | using namespace llvm; |
21 | |
22 | using UnaryBitsFn = llvm::function_ref<KnownBits(const KnownBits &)>; |
23 | using UnaryIntFn = llvm::function_ref<std::optional<APInt>(const APInt &)>; |
24 | |
25 | using BinaryBitsFn = |
26 | llvm::function_ref<KnownBits(const KnownBits &, const KnownBits &)>; |
27 | using BinaryIntFn = |
28 | llvm::function_ref<std::optional<APInt>(const APInt &, const APInt &)>; |
29 | |
30 | static testing::AssertionResult checkResult(Twine Name, const KnownBits &Exact, |
31 | const KnownBits &Computed, |
32 | ArrayRef<KnownBits> Inputs, |
33 | bool CheckOptimality) { |
34 | if (CheckOptimality) { |
35 | // We generally don't want to return conflicting known bits, even if it is |
36 | // legal for always poison results. |
37 | if (Exact.hasConflict() || Computed == Exact) |
38 | return testing::AssertionSuccess(); |
39 | } else { |
40 | if (Computed.Zero.isSubsetOf(RHS: Exact.Zero) && |
41 | Computed.One.isSubsetOf(RHS: Exact.One)) |
42 | return testing::AssertionSuccess(); |
43 | } |
44 | |
45 | testing::AssertionResult Result = testing::AssertionFailure(); |
46 | Result << Name << ": " ; |
47 | Result << "Inputs = " ; |
48 | for (const KnownBits &Input : Inputs) |
49 | Result << Input << ", " ; |
50 | Result << "Computed = " << Computed << ", Exact = " << Exact; |
51 | return Result; |
52 | } |
53 | |
54 | static void testUnaryOpExhaustive(StringRef Name, UnaryBitsFn BitsFn, |
55 | UnaryIntFn IntFn, |
56 | bool CheckOptimality = true) { |
57 | for (unsigned Bits : {1, 4}) { |
58 | ForeachKnownBits(Bits, Fn: [&](const KnownBits &Known) { |
59 | KnownBits Computed = BitsFn(Known); |
60 | KnownBits Exact(Bits); |
61 | Exact.Zero.setAllBits(); |
62 | Exact.One.setAllBits(); |
63 | |
64 | ForeachNumInKnownBits(Known, Fn: [&](const APInt &N) { |
65 | if (std::optional<APInt> Res = IntFn(N)) { |
66 | Exact.One &= *Res; |
67 | Exact.Zero &= ~*Res; |
68 | } |
69 | }); |
70 | |
71 | EXPECT_TRUE(!Computed.hasConflict()); |
72 | EXPECT_TRUE(checkResult(Name, Exact, Computed, Known, CheckOptimality)); |
73 | }); |
74 | } |
75 | } |
76 | |
77 | static void testBinaryOpExhaustive(StringRef Name, BinaryBitsFn BitsFn, |
78 | BinaryIntFn IntFn, |
79 | bool CheckOptimality = true, |
80 | bool RefinePoisonToZero = false) { |
81 | for (unsigned Bits : {1, 4}) { |
82 | ForeachKnownBits(Bits, Fn: [&](const KnownBits &Known1) { |
83 | ForeachKnownBits(Bits, Fn: [&](const KnownBits &Known2) { |
84 | KnownBits Computed = BitsFn(Known1, Known2); |
85 | KnownBits Exact(Bits); |
86 | Exact.Zero.setAllBits(); |
87 | Exact.One.setAllBits(); |
88 | |
89 | ForeachNumInKnownBits(Known: Known1, Fn: [&](const APInt &N1) { |
90 | ForeachNumInKnownBits(Known: Known2, Fn: [&](const APInt &N2) { |
91 | if (std::optional<APInt> Res = IntFn(N1, N2)) { |
92 | Exact.One &= *Res; |
93 | Exact.Zero &= ~*Res; |
94 | } |
95 | }); |
96 | }); |
97 | |
98 | EXPECT_TRUE(!Computed.hasConflict()); |
99 | EXPECT_TRUE(checkResult(Name, Exact, Computed, {Known1, Known2}, |
100 | CheckOptimality)); |
101 | // In some cases we choose to return zero if the result is always |
102 | // poison. |
103 | if (RefinePoisonToZero && Exact.hasConflict()) { |
104 | EXPECT_TRUE(Computed.isZero()); |
105 | } |
106 | }); |
107 | }); |
108 | } |
109 | } |
110 | |
111 | namespace { |
112 | |
113 | TEST(KnownBitsTest, AddCarryExhaustive) { |
114 | unsigned Bits = 4; |
115 | ForeachKnownBits(Bits, Fn: [&](const KnownBits &Known1) { |
116 | ForeachKnownBits(Bits, Fn: [&](const KnownBits &Known2) { |
117 | ForeachKnownBits(Bits: 1, Fn: [&](const KnownBits &KnownCarry) { |
118 | // Explicitly compute known bits of the addition by trying all |
119 | // possibilities. |
120 | KnownBits Exact(Bits); |
121 | Exact.Zero.setAllBits(); |
122 | Exact.One.setAllBits(); |
123 | ForeachNumInKnownBits(Known: Known1, Fn: [&](const APInt &N1) { |
124 | ForeachNumInKnownBits(Known: Known2, Fn: [&](const APInt &N2) { |
125 | ForeachNumInKnownBits(Known: KnownCarry, Fn: [&](const APInt &Carry) { |
126 | APInt Add = N1 + N2; |
127 | if (Carry.getBoolValue()) |
128 | ++Add; |
129 | |
130 | Exact.One &= Add; |
131 | Exact.Zero &= ~Add; |
132 | }); |
133 | }); |
134 | }); |
135 | |
136 | KnownBits Computed = |
137 | KnownBits::computeForAddCarry(LHS: Known1, RHS: Known2, Carry: KnownCarry); |
138 | EXPECT_EQ(Exact, Computed); |
139 | }); |
140 | }); |
141 | }); |
142 | } |
143 | |
144 | static void TestAddSubExhaustive(bool IsAdd) { |
145 | Twine Name = IsAdd ? "add" : "sub" ; |
146 | unsigned Bits = 4; |
147 | ForeachKnownBits(Bits, Fn: [&](const KnownBits &Known1) { |
148 | ForeachKnownBits(Bits, Fn: [&](const KnownBits &Known2) { |
149 | KnownBits Exact(Bits), ExactNSW(Bits), ExactNUW(Bits), |
150 | ExactNSWAndNUW(Bits); |
151 | Exact.Zero.setAllBits(); |
152 | Exact.One.setAllBits(); |
153 | ExactNSW.Zero.setAllBits(); |
154 | ExactNSW.One.setAllBits(); |
155 | ExactNUW.Zero.setAllBits(); |
156 | ExactNUW.One.setAllBits(); |
157 | ExactNSWAndNUW.Zero.setAllBits(); |
158 | ExactNSWAndNUW.One.setAllBits(); |
159 | |
160 | ForeachNumInKnownBits(Known: Known1, Fn: [&](const APInt &N1) { |
161 | ForeachNumInKnownBits(Known: Known2, Fn: [&](const APInt &N2) { |
162 | bool SignedOverflow; |
163 | bool UnsignedOverflow; |
164 | APInt Res; |
165 | if (IsAdd) { |
166 | Res = N1.uadd_ov(RHS: N2, Overflow&: UnsignedOverflow); |
167 | Res = N1.sadd_ov(RHS: N2, Overflow&: SignedOverflow); |
168 | } else { |
169 | Res = N1.usub_ov(RHS: N2, Overflow&: UnsignedOverflow); |
170 | Res = N1.ssub_ov(RHS: N2, Overflow&: SignedOverflow); |
171 | } |
172 | |
173 | Exact.One &= Res; |
174 | Exact.Zero &= ~Res; |
175 | |
176 | if (!SignedOverflow) { |
177 | ExactNSW.One &= Res; |
178 | ExactNSW.Zero &= ~Res; |
179 | } |
180 | |
181 | if (!UnsignedOverflow) { |
182 | ExactNUW.One &= Res; |
183 | ExactNUW.Zero &= ~Res; |
184 | } |
185 | |
186 | if (!UnsignedOverflow && !SignedOverflow) { |
187 | ExactNSWAndNUW.One &= Res; |
188 | ExactNSWAndNUW.Zero &= ~Res; |
189 | } |
190 | }); |
191 | }); |
192 | |
193 | KnownBits Computed = KnownBits::computeForAddSub( |
194 | Add: IsAdd, /*NSW=*/false, /*NUW=*/false, LHS: Known1, RHS: Known2); |
195 | EXPECT_TRUE(checkResult(Name, Exact, Computed, {Known1, Known2}, |
196 | /*CheckOptimality=*/true)); |
197 | |
198 | KnownBits ComputedNSW = KnownBits::computeForAddSub( |
199 | Add: IsAdd, /*NSW=*/true, /*NUW=*/false, LHS: Known1, RHS: Known2); |
200 | EXPECT_TRUE(checkResult(Name + " nsw" , ExactNSW, ComputedNSW, |
201 | {Known1, Known2}, |
202 | /*CheckOptimality=*/true)); |
203 | |
204 | KnownBits ComputedNUW = KnownBits::computeForAddSub( |
205 | Add: IsAdd, /*NSW=*/false, /*NUW=*/true, LHS: Known1, RHS: Known2); |
206 | EXPECT_TRUE(checkResult(Name + " nuw" , ExactNUW, ComputedNUW, |
207 | {Known1, Known2}, |
208 | /*CheckOptimality=*/true)); |
209 | |
210 | KnownBits ComputedNSWAndNUW = KnownBits::computeForAddSub( |
211 | Add: IsAdd, /*NSW=*/true, /*NUW=*/true, LHS: Known1, RHS: Known2); |
212 | EXPECT_TRUE(checkResult(Name + " nsw nuw" , ExactNSWAndNUW, |
213 | ComputedNSWAndNUW, {Known1, Known2}, |
214 | /*CheckOptimality=*/true)); |
215 | }); |
216 | }); |
217 | } |
218 | |
219 | TEST(KnownBitsTest, AddSubExhaustive) { |
220 | TestAddSubExhaustive(IsAdd: true); |
221 | TestAddSubExhaustive(IsAdd: false); |
222 | } |
223 | |
224 | TEST(KnownBitsTest, SubBorrowExhaustive) { |
225 | unsigned Bits = 4; |
226 | ForeachKnownBits(Bits, Fn: [&](const KnownBits &Known1) { |
227 | ForeachKnownBits(Bits, Fn: [&](const KnownBits &Known2) { |
228 | ForeachKnownBits(Bits: 1, Fn: [&](const KnownBits &KnownBorrow) { |
229 | // Explicitly compute known bits of the subtraction by trying all |
230 | // possibilities. |
231 | KnownBits Exact(Bits); |
232 | Exact.Zero.setAllBits(); |
233 | Exact.One.setAllBits(); |
234 | ForeachNumInKnownBits(Known: Known1, Fn: [&](const APInt &N1) { |
235 | ForeachNumInKnownBits(Known: Known2, Fn: [&](const APInt &N2) { |
236 | ForeachNumInKnownBits(Known: KnownBorrow, Fn: [&](const APInt &Borrow) { |
237 | APInt Sub = N1 - N2; |
238 | if (Borrow.getBoolValue()) |
239 | --Sub; |
240 | |
241 | Exact.One &= Sub; |
242 | Exact.Zero &= ~Sub; |
243 | }); |
244 | }); |
245 | }); |
246 | |
247 | KnownBits Computed = |
248 | KnownBits::computeForSubBorrow(LHS: Known1, RHS: Known2, Borrow: KnownBorrow); |
249 | EXPECT_EQ(Exact, Computed); |
250 | }); |
251 | }); |
252 | }); |
253 | } |
254 | |
255 | TEST(KnownBitsTest, SignBitUnknown) { |
256 | KnownBits Known(2); |
257 | EXPECT_TRUE(Known.isSignUnknown()); |
258 | Known.Zero.setBit(0); |
259 | EXPECT_TRUE(Known.isSignUnknown()); |
260 | Known.Zero.setBit(1); |
261 | EXPECT_FALSE(Known.isSignUnknown()); |
262 | Known.Zero.clearBit(BitPosition: 0); |
263 | EXPECT_FALSE(Known.isSignUnknown()); |
264 | Known.Zero.clearBit(BitPosition: 1); |
265 | EXPECT_TRUE(Known.isSignUnknown()); |
266 | |
267 | Known.One.setBit(0); |
268 | EXPECT_TRUE(Known.isSignUnknown()); |
269 | Known.One.setBit(1); |
270 | EXPECT_FALSE(Known.isSignUnknown()); |
271 | Known.One.clearBit(BitPosition: 0); |
272 | EXPECT_FALSE(Known.isSignUnknown()); |
273 | Known.One.clearBit(BitPosition: 1); |
274 | EXPECT_TRUE(Known.isSignUnknown()); |
275 | } |
276 | |
277 | TEST(KnownBitsTest, BinaryExhaustive) { |
278 | testBinaryOpExhaustive( |
279 | Name: "and" , |
280 | BitsFn: [](const KnownBits &Known1, const KnownBits &Known2) { |
281 | return Known1 & Known2; |
282 | }, |
283 | IntFn: [](const APInt &N1, const APInt &N2) { return N1 & N2; }); |
284 | testBinaryOpExhaustive( |
285 | Name: "or" , |
286 | BitsFn: [](const KnownBits &Known1, const KnownBits &Known2) { |
287 | return Known1 | Known2; |
288 | }, |
289 | IntFn: [](const APInt &N1, const APInt &N2) { return N1 | N2; }); |
290 | testBinaryOpExhaustive( |
291 | Name: "xor" , |
292 | BitsFn: [](const KnownBits &Known1, const KnownBits &Known2) { |
293 | return Known1 ^ Known2; |
294 | }, |
295 | IntFn: [](const APInt &N1, const APInt &N2) { return N1 ^ N2; }); |
296 | testBinaryOpExhaustive(Name: "umax" , BitsFn: KnownBits::umax, IntFn: APIntOps::umax); |
297 | testBinaryOpExhaustive(Name: "umin" , BitsFn: KnownBits::umin, IntFn: APIntOps::umin); |
298 | testBinaryOpExhaustive(Name: "smax" , BitsFn: KnownBits::smax, IntFn: APIntOps::smax); |
299 | testBinaryOpExhaustive(Name: "smin" , BitsFn: KnownBits::smin, IntFn: APIntOps::smin); |
300 | testBinaryOpExhaustive(Name: "abdu" , BitsFn: KnownBits::abdu, IntFn: APIntOps::abdu); |
301 | testBinaryOpExhaustive(Name: "abds" , BitsFn: KnownBits::abds, IntFn: APIntOps::abds); |
302 | testBinaryOpExhaustive( |
303 | Name: "udiv" , |
304 | BitsFn: [](const KnownBits &Known1, const KnownBits &Known2) { |
305 | return KnownBits::udiv(LHS: Known1, RHS: Known2); |
306 | }, |
307 | IntFn: [](const APInt &N1, const APInt &N2) -> std::optional<APInt> { |
308 | if (N2.isZero()) |
309 | return std::nullopt; |
310 | return N1.udiv(RHS: N2); |
311 | }, |
312 | /*CheckOptimality=*/false); |
313 | testBinaryOpExhaustive( |
314 | Name: "udiv exact" , |
315 | BitsFn: [](const KnownBits &Known1, const KnownBits &Known2) { |
316 | return KnownBits::udiv(LHS: Known1, RHS: Known2, /*Exact*/ true); |
317 | }, |
318 | IntFn: [](const APInt &N1, const APInt &N2) -> std::optional<APInt> { |
319 | if (N2.isZero() || !N1.urem(RHS: N2).isZero()) |
320 | return std::nullopt; |
321 | return N1.udiv(RHS: N2); |
322 | }, |
323 | /*CheckOptimality=*/false); |
324 | testBinaryOpExhaustive( |
325 | Name: "sdiv" , |
326 | BitsFn: [](const KnownBits &Known1, const KnownBits &Known2) { |
327 | return KnownBits::sdiv(LHS: Known1, RHS: Known2); |
328 | }, |
329 | IntFn: [](const APInt &N1, const APInt &N2) -> std::optional<APInt> { |
330 | if (N2.isZero() || (N1.isMinSignedValue() && N2.isAllOnes())) |
331 | return std::nullopt; |
332 | return N1.sdiv(RHS: N2); |
333 | }, |
334 | /*CheckOptimality=*/false); |
335 | testBinaryOpExhaustive( |
336 | Name: "sdiv exact" , |
337 | BitsFn: [](const KnownBits &Known1, const KnownBits &Known2) { |
338 | return KnownBits::sdiv(LHS: Known1, RHS: Known2, /*Exact*/ true); |
339 | }, |
340 | IntFn: [](const APInt &N1, const APInt &N2) -> std::optional<APInt> { |
341 | if (N2.isZero() || (N1.isMinSignedValue() && N2.isAllOnes()) || |
342 | !N1.srem(RHS: N2).isZero()) |
343 | return std::nullopt; |
344 | return N1.sdiv(RHS: N2); |
345 | }, |
346 | /*CheckOptimality=*/false); |
347 | testBinaryOpExhaustive( |
348 | Name: "urem" , BitsFn: KnownBits::urem, |
349 | IntFn: [](const APInt &N1, const APInt &N2) -> std::optional<APInt> { |
350 | if (N2.isZero()) |
351 | return std::nullopt; |
352 | return N1.urem(RHS: N2); |
353 | }, |
354 | /*CheckOptimality=*/false); |
355 | testBinaryOpExhaustive( |
356 | Name: "srem" , BitsFn: KnownBits::srem, |
357 | IntFn: [](const APInt &N1, const APInt &N2) -> std::optional<APInt> { |
358 | if (N2.isZero()) |
359 | return std::nullopt; |
360 | return N1.srem(RHS: N2); |
361 | }, |
362 | /*CheckOptimality=*/false); |
363 | testBinaryOpExhaustive( |
364 | Name: "sadd_sat" , BitsFn: KnownBits::sadd_sat, |
365 | IntFn: [](const APInt &N1, const APInt &N2) -> std::optional<APInt> { |
366 | return N1.sadd_sat(RHS: N2); |
367 | }, |
368 | /*CheckOptimality=*/false); |
369 | testBinaryOpExhaustive( |
370 | Name: "uadd_sat" , BitsFn: KnownBits::uadd_sat, |
371 | IntFn: [](const APInt &N1, const APInt &N2) -> std::optional<APInt> { |
372 | return N1.uadd_sat(RHS: N2); |
373 | }, |
374 | /*CheckOptimality=*/false); |
375 | testBinaryOpExhaustive( |
376 | Name: "ssub_sat" , BitsFn: KnownBits::ssub_sat, |
377 | IntFn: [](const APInt &N1, const APInt &N2) -> std::optional<APInt> { |
378 | return N1.ssub_sat(RHS: N2); |
379 | }, |
380 | /*CheckOptimality=*/false); |
381 | testBinaryOpExhaustive( |
382 | Name: "usub_sat" , BitsFn: KnownBits::usub_sat, |
383 | IntFn: [](const APInt &N1, const APInt &N2) -> std::optional<APInt> { |
384 | return N1.usub_sat(RHS: N2); |
385 | }, |
386 | /*CheckOptimality=*/false); |
387 | testBinaryOpExhaustive( |
388 | Name: "shl" , |
389 | BitsFn: [](const KnownBits &Known1, const KnownBits &Known2) { |
390 | return KnownBits::shl(LHS: Known1, RHS: Known2); |
391 | }, |
392 | IntFn: [](const APInt &N1, const APInt &N2) -> std::optional<APInt> { |
393 | if (N2.uge(RHS: N2.getBitWidth())) |
394 | return std::nullopt; |
395 | return N1.shl(ShiftAmt: N2); |
396 | }, |
397 | /*CheckOptimality=*/true, /* RefinePoisonToZero */ true); |
398 | testBinaryOpExhaustive( |
399 | Name: "ushl_ov" , |
400 | BitsFn: [](const KnownBits &Known1, const KnownBits &Known2) { |
401 | return KnownBits::shl(LHS: Known1, RHS: Known2, /* NUW */ true); |
402 | }, |
403 | IntFn: [](const APInt &N1, const APInt &N2) -> std::optional<APInt> { |
404 | bool Overflow; |
405 | APInt Res = N1.ushl_ov(Amt: N2, Overflow); |
406 | if (Overflow) |
407 | return std::nullopt; |
408 | return Res; |
409 | }, |
410 | /*CheckOptimality=*/true, /* RefinePoisonToZero */ true); |
411 | testBinaryOpExhaustive( |
412 | Name: "shl nsw" , |
413 | BitsFn: [](const KnownBits &Known1, const KnownBits &Known2) { |
414 | return KnownBits::shl(LHS: Known1, RHS: Known2, /* NUW */ false, /* NSW */ true); |
415 | }, |
416 | IntFn: [](const APInt &N1, const APInt &N2) -> std::optional<APInt> { |
417 | bool Overflow; |
418 | APInt Res = N1.sshl_ov(Amt: N2, Overflow); |
419 | if (Overflow) |
420 | return std::nullopt; |
421 | return Res; |
422 | }, |
423 | /*CheckOptimality=*/true, /* RefinePoisonToZero */ true); |
424 | testBinaryOpExhaustive( |
425 | Name: "shl nuw" , |
426 | BitsFn: [](const KnownBits &Known1, const KnownBits &Known2) { |
427 | return KnownBits::shl(LHS: Known1, RHS: Known2, /* NUW */ true, /* NSW */ true); |
428 | }, |
429 | IntFn: [](const APInt &N1, const APInt &N2) -> std::optional<APInt> { |
430 | bool OverflowUnsigned, OverflowSigned; |
431 | APInt Res = N1.ushl_ov(Amt: N2, Overflow&: OverflowUnsigned); |
432 | (void)N1.sshl_ov(Amt: N2, Overflow&: OverflowSigned); |
433 | if (OverflowUnsigned || OverflowSigned) |
434 | return std::nullopt; |
435 | return Res; |
436 | }, |
437 | /*CheckOptimality=*/true, /* RefinePoisonToZero */ true); |
438 | |
439 | testBinaryOpExhaustive( |
440 | Name: "lshr" , |
441 | BitsFn: [](const KnownBits &Known1, const KnownBits &Known2) { |
442 | return KnownBits::lshr(LHS: Known1, RHS: Known2); |
443 | }, |
444 | IntFn: [](const APInt &N1, const APInt &N2) -> std::optional<APInt> { |
445 | if (N2.uge(RHS: N2.getBitWidth())) |
446 | return std::nullopt; |
447 | return N1.lshr(ShiftAmt: N2); |
448 | }, |
449 | /*CheckOptimality=*/true, /* RefinePoisonToZero */ true); |
450 | testBinaryOpExhaustive( |
451 | Name: "lshr exact" , |
452 | BitsFn: [](const KnownBits &Known1, const KnownBits &Known2) { |
453 | return KnownBits::lshr(LHS: Known1, RHS: Known2, /*ShAmtNonZero=*/false, |
454 | /*Exact=*/true); |
455 | }, |
456 | IntFn: [](const APInt &N1, const APInt &N2) -> std::optional<APInt> { |
457 | if (N2.uge(RHS: N2.getBitWidth())) |
458 | return std::nullopt; |
459 | if (!N1.extractBits(numBits: N2.getZExtValue(), bitPosition: 0).isZero()) |
460 | return std::nullopt; |
461 | return N1.lshr(ShiftAmt: N2); |
462 | }, |
463 | /*CheckOptimality=*/true, /* RefinePoisonToZero */ true); |
464 | testBinaryOpExhaustive( |
465 | Name: "ashr" , |
466 | BitsFn: [](const KnownBits &Known1, const KnownBits &Known2) { |
467 | return KnownBits::ashr(LHS: Known1, RHS: Known2); |
468 | }, |
469 | IntFn: [](const APInt &N1, const APInt &N2) -> std::optional<APInt> { |
470 | if (N2.uge(RHS: N2.getBitWidth())) |
471 | return std::nullopt; |
472 | return N1.ashr(ShiftAmt: N2); |
473 | }, |
474 | /*CheckOptimality=*/true, /* RefinePoisonToZero */ true); |
475 | testBinaryOpExhaustive( |
476 | Name: "ashr exact" , |
477 | BitsFn: [](const KnownBits &Known1, const KnownBits &Known2) { |
478 | return KnownBits::ashr(LHS: Known1, RHS: Known2, /*ShAmtNonZero=*/false, |
479 | /*Exact=*/true); |
480 | }, |
481 | IntFn: [](const APInt &N1, const APInt &N2) -> std::optional<APInt> { |
482 | if (N2.uge(RHS: N2.getBitWidth())) |
483 | return std::nullopt; |
484 | if (!N1.extractBits(numBits: N2.getZExtValue(), bitPosition: 0).isZero()) |
485 | return std::nullopt; |
486 | return N1.ashr(ShiftAmt: N2); |
487 | }, |
488 | /*CheckOptimality=*/true, /* RefinePoisonToZero */ true); |
489 | testBinaryOpExhaustive( |
490 | Name: "mul" , |
491 | BitsFn: [](const KnownBits &Known1, const KnownBits &Known2) { |
492 | return KnownBits::mul(LHS: Known1, RHS: Known2); |
493 | }, |
494 | IntFn: [](const APInt &N1, const APInt &N2) { return N1 * N2; }, |
495 | /*CheckOptimality=*/false); |
496 | testBinaryOpExhaustive( |
497 | Name: "mulhs" , BitsFn: KnownBits::mulhs, |
498 | IntFn: [](const APInt &N1, const APInt &N2) { return APIntOps::mulhs(C1: N1, C2: N2); }, |
499 | /*CheckOptimality=*/false); |
500 | testBinaryOpExhaustive( |
501 | Name: "mulhu" , BitsFn: KnownBits::mulhu, |
502 | IntFn: [](const APInt &N1, const APInt &N2) { return APIntOps::mulhu(C1: N1, C2: N2); }, |
503 | /*CheckOptimality=*/false); |
504 | } |
505 | |
506 | TEST(KnownBitsTest, UnaryExhaustive) { |
507 | testUnaryOpExhaustive( |
508 | Name: "abs" , BitsFn: [](const KnownBits &Known) { return Known.abs(); }, |
509 | IntFn: [](const APInt &N) { return N.abs(); }); |
510 | |
511 | testUnaryOpExhaustive( |
512 | Name: "abs(true)" , BitsFn: [](const KnownBits &Known) { return Known.abs(IntMinIsPoison: true); }, |
513 | IntFn: [](const APInt &N) -> std::optional<APInt> { |
514 | if (N.isMinSignedValue()) |
515 | return std::nullopt; |
516 | return N.abs(); |
517 | }); |
518 | |
519 | testUnaryOpExhaustive( |
520 | Name: "blsi" , BitsFn: [](const KnownBits &Known) { return Known.blsi(); }, |
521 | IntFn: [](const APInt &N) { return N & -N; }); |
522 | testUnaryOpExhaustive( |
523 | Name: "blsmsk" , BitsFn: [](const KnownBits &Known) { return Known.blsmsk(); }, |
524 | IntFn: [](const APInt &N) { return N ^ (N - 1); }); |
525 | |
526 | testUnaryOpExhaustive( |
527 | Name: "mul self" , |
528 | BitsFn: [](const KnownBits &Known) { |
529 | return KnownBits::mul(LHS: Known, RHS: Known, /*SelfMultiply*/ NoUndefSelfMultiply: true); |
530 | }, |
531 | IntFn: [](const APInt &N) { return N * N; }, /*CheckOptimality=*/false); |
532 | } |
533 | |
534 | TEST(KnownBitsTest, WideShifts) { |
535 | unsigned BitWidth = 128; |
536 | KnownBits Unknown(BitWidth); |
537 | KnownBits AllOnes = KnownBits::makeConstant(C: APInt::getAllOnes(numBits: BitWidth)); |
538 | |
539 | KnownBits ShlResult(BitWidth); |
540 | ShlResult.makeNegative(); |
541 | EXPECT_EQ(KnownBits::shl(AllOnes, Unknown), ShlResult); |
542 | KnownBits LShrResult(BitWidth); |
543 | LShrResult.One.setBit(0); |
544 | EXPECT_EQ(KnownBits::lshr(AllOnes, Unknown), LShrResult); |
545 | EXPECT_EQ(KnownBits::ashr(AllOnes, Unknown), AllOnes); |
546 | } |
547 | |
548 | TEST(KnownBitsTest, ICmpExhaustive) { |
549 | unsigned Bits = 4; |
550 | ForeachKnownBits(Bits, Fn: [&](const KnownBits &Known1) { |
551 | ForeachKnownBits(Bits, Fn: [&](const KnownBits &Known2) { |
552 | bool AllEQ = true, NoneEQ = true; |
553 | bool AllNE = true, NoneNE = true; |
554 | bool AllUGT = true, NoneUGT = true; |
555 | bool AllUGE = true, NoneUGE = true; |
556 | bool AllULT = true, NoneULT = true; |
557 | bool AllULE = true, NoneULE = true; |
558 | bool AllSGT = true, NoneSGT = true; |
559 | bool AllSGE = true, NoneSGE = true; |
560 | bool AllSLT = true, NoneSLT = true; |
561 | bool AllSLE = true, NoneSLE = true; |
562 | |
563 | ForeachNumInKnownBits(Known: Known1, Fn: [&](const APInt &N1) { |
564 | ForeachNumInKnownBits(Known: Known2, Fn: [&](const APInt &N2) { |
565 | AllEQ &= N1.eq(RHS: N2); |
566 | AllNE &= N1.ne(RHS: N2); |
567 | AllUGT &= N1.ugt(RHS: N2); |
568 | AllUGE &= N1.uge(RHS: N2); |
569 | AllULT &= N1.ult(RHS: N2); |
570 | AllULE &= N1.ule(RHS: N2); |
571 | AllSGT &= N1.sgt(RHS: N2); |
572 | AllSGE &= N1.sge(RHS: N2); |
573 | AllSLT &= N1.slt(RHS: N2); |
574 | AllSLE &= N1.sle(RHS: N2); |
575 | NoneEQ &= !N1.eq(RHS: N2); |
576 | NoneNE &= !N1.ne(RHS: N2); |
577 | NoneUGT &= !N1.ugt(RHS: N2); |
578 | NoneUGE &= !N1.uge(RHS: N2); |
579 | NoneULT &= !N1.ult(RHS: N2); |
580 | NoneULE &= !N1.ule(RHS: N2); |
581 | NoneSGT &= !N1.sgt(RHS: N2); |
582 | NoneSGE &= !N1.sge(RHS: N2); |
583 | NoneSLT &= !N1.slt(RHS: N2); |
584 | NoneSLE &= !N1.sle(RHS: N2); |
585 | }); |
586 | }); |
587 | |
588 | std::optional<bool> KnownEQ = KnownBits::eq(LHS: Known1, RHS: Known2); |
589 | std::optional<bool> KnownNE = KnownBits::ne(LHS: Known1, RHS: Known2); |
590 | std::optional<bool> KnownUGT = KnownBits::ugt(LHS: Known1, RHS: Known2); |
591 | std::optional<bool> KnownUGE = KnownBits::uge(LHS: Known1, RHS: Known2); |
592 | std::optional<bool> KnownULT = KnownBits::ult(LHS: Known1, RHS: Known2); |
593 | std::optional<bool> KnownULE = KnownBits::ule(LHS: Known1, RHS: Known2); |
594 | std::optional<bool> KnownSGT = KnownBits::sgt(LHS: Known1, RHS: Known2); |
595 | std::optional<bool> KnownSGE = KnownBits::sge(LHS: Known1, RHS: Known2); |
596 | std::optional<bool> KnownSLT = KnownBits::slt(LHS: Known1, RHS: Known2); |
597 | std::optional<bool> KnownSLE = KnownBits::sle(LHS: Known1, RHS: Known2); |
598 | |
599 | EXPECT_EQ(AllEQ || NoneEQ, KnownEQ.has_value()); |
600 | EXPECT_EQ(AllNE || NoneNE, KnownNE.has_value()); |
601 | EXPECT_EQ(AllUGT || NoneUGT, KnownUGT.has_value()); |
602 | EXPECT_EQ(AllUGE || NoneUGE, KnownUGE.has_value()); |
603 | EXPECT_EQ(AllULT || NoneULT, KnownULT.has_value()); |
604 | EXPECT_EQ(AllULE || NoneULE, KnownULE.has_value()); |
605 | EXPECT_EQ(AllSGT || NoneSGT, KnownSGT.has_value()); |
606 | EXPECT_EQ(AllSGE || NoneSGE, KnownSGE.has_value()); |
607 | EXPECT_EQ(AllSLT || NoneSLT, KnownSLT.has_value()); |
608 | EXPECT_EQ(AllSLE || NoneSLE, KnownSLE.has_value()); |
609 | |
610 | EXPECT_EQ(AllEQ, KnownEQ.has_value() && *KnownEQ); |
611 | EXPECT_EQ(AllNE, KnownNE.has_value() && *KnownNE); |
612 | EXPECT_EQ(AllUGT, KnownUGT.has_value() && *KnownUGT); |
613 | EXPECT_EQ(AllUGE, KnownUGE.has_value() && *KnownUGE); |
614 | EXPECT_EQ(AllULT, KnownULT.has_value() && *KnownULT); |
615 | EXPECT_EQ(AllULE, KnownULE.has_value() && *KnownULE); |
616 | EXPECT_EQ(AllSGT, KnownSGT.has_value() && *KnownSGT); |
617 | EXPECT_EQ(AllSGE, KnownSGE.has_value() && *KnownSGE); |
618 | EXPECT_EQ(AllSLT, KnownSLT.has_value() && *KnownSLT); |
619 | EXPECT_EQ(AllSLE, KnownSLE.has_value() && *KnownSLE); |
620 | |
621 | EXPECT_EQ(NoneEQ, KnownEQ.has_value() && !*KnownEQ); |
622 | EXPECT_EQ(NoneNE, KnownNE.has_value() && !*KnownNE); |
623 | EXPECT_EQ(NoneUGT, KnownUGT.has_value() && !*KnownUGT); |
624 | EXPECT_EQ(NoneUGE, KnownUGE.has_value() && !*KnownUGE); |
625 | EXPECT_EQ(NoneULT, KnownULT.has_value() && !*KnownULT); |
626 | EXPECT_EQ(NoneULE, KnownULE.has_value() && !*KnownULE); |
627 | EXPECT_EQ(NoneSGT, KnownSGT.has_value() && !*KnownSGT); |
628 | EXPECT_EQ(NoneSGE, KnownSGE.has_value() && !*KnownSGE); |
629 | EXPECT_EQ(NoneSLT, KnownSLT.has_value() && !*KnownSLT); |
630 | EXPECT_EQ(NoneSLE, KnownSLE.has_value() && !*KnownSLE); |
631 | }); |
632 | }); |
633 | } |
634 | |
635 | TEST(KnownBitsTest, GetMinMaxVal) { |
636 | unsigned Bits = 4; |
637 | ForeachKnownBits(Bits, Fn: [&](const KnownBits &Known) { |
638 | APInt Min = APInt::getMaxValue(numBits: Bits); |
639 | APInt Max = APInt::getMinValue(numBits: Bits); |
640 | ForeachNumInKnownBits(Known, Fn: [&](const APInt &N) { |
641 | Min = APIntOps::umin(A: Min, B: N); |
642 | Max = APIntOps::umax(A: Max, B: N); |
643 | }); |
644 | EXPECT_EQ(Min, Known.getMinValue()); |
645 | EXPECT_EQ(Max, Known.getMaxValue()); |
646 | }); |
647 | } |
648 | |
649 | TEST(KnownBitsTest, GetSignedMinMaxVal) { |
650 | unsigned Bits = 4; |
651 | ForeachKnownBits(Bits, Fn: [&](const KnownBits &Known) { |
652 | APInt Min = APInt::getSignedMaxValue(numBits: Bits); |
653 | APInt Max = APInt::getSignedMinValue(numBits: Bits); |
654 | ForeachNumInKnownBits(Known, Fn: [&](const APInt &N) { |
655 | Min = APIntOps::smin(A: Min, B: N); |
656 | Max = APIntOps::smax(A: Max, B: N); |
657 | }); |
658 | EXPECT_EQ(Min, Known.getSignedMinValue()); |
659 | EXPECT_EQ(Max, Known.getSignedMaxValue()); |
660 | }); |
661 | } |
662 | |
663 | TEST(KnownBitsTest, CountMaxActiveBits) { |
664 | unsigned Bits = 4; |
665 | ForeachKnownBits(Bits, Fn: [&](const KnownBits &Known) { |
666 | unsigned Expected = 0; |
667 | ForeachNumInKnownBits(Known, Fn: [&](const APInt &N) { |
668 | Expected = std::max(a: Expected, b: N.getActiveBits()); |
669 | }); |
670 | EXPECT_EQ(Expected, Known.countMaxActiveBits()); |
671 | }); |
672 | } |
673 | |
674 | TEST(KnownBitsTest, CountMaxSignificantBits) { |
675 | unsigned Bits = 4; |
676 | ForeachKnownBits(Bits, Fn: [&](const KnownBits &Known) { |
677 | unsigned Expected = 0; |
678 | ForeachNumInKnownBits(Known, Fn: [&](const APInt &N) { |
679 | Expected = std::max(a: Expected, b: N.getSignificantBits()); |
680 | }); |
681 | EXPECT_EQ(Expected, Known.countMaxSignificantBits()); |
682 | }); |
683 | } |
684 | |
685 | TEST(KnownBitsTest, SExtOrTrunc) { |
686 | const unsigned NarrowerSize = 4; |
687 | const unsigned BaseSize = 6; |
688 | const unsigned WiderSize = 8; |
689 | APInt NegativeFitsNarrower(BaseSize, -4, /*isSigned*/ true); |
690 | APInt NegativeDoesntFitNarrower(BaseSize, -28, /*isSigned*/ true); |
691 | APInt PositiveFitsNarrower(BaseSize, 14); |
692 | APInt PositiveDoesntFitNarrower(BaseSize, 36); |
693 | auto InitKnownBits = [&](KnownBits &Res, const APInt &Input) { |
694 | Res = KnownBits(Input.getBitWidth()); |
695 | Res.One = Input; |
696 | Res.Zero = ~Input; |
697 | }; |
698 | |
699 | for (unsigned Size : {NarrowerSize, BaseSize, WiderSize}) { |
700 | for (const APInt &Input : |
701 | {NegativeFitsNarrower, NegativeDoesntFitNarrower, PositiveFitsNarrower, |
702 | PositiveDoesntFitNarrower}) { |
703 | KnownBits Test; |
704 | InitKnownBits(Test, Input); |
705 | KnownBits Baseline; |
706 | InitKnownBits(Baseline, Input.sextOrTrunc(width: Size)); |
707 | Test = Test.sextOrTrunc(BitWidth: Size); |
708 | EXPECT_EQ(Test, Baseline); |
709 | } |
710 | } |
711 | } |
712 | |
713 | TEST(KnownBitsTest, SExtInReg) { |
714 | unsigned Bits = 4; |
715 | for (unsigned FromBits = 1; FromBits <= Bits; ++FromBits) { |
716 | ForeachKnownBits(Bits, Fn: [&](const KnownBits &Known) { |
717 | APInt CommonOne = APInt::getAllOnes(numBits: Bits); |
718 | APInt CommonZero = APInt::getAllOnes(numBits: Bits); |
719 | unsigned ExtBits = Bits - FromBits; |
720 | ForeachNumInKnownBits(Known, Fn: [&](const APInt &N) { |
721 | APInt Ext = N << ExtBits; |
722 | Ext.ashrInPlace(ShiftAmt: ExtBits); |
723 | CommonOne &= Ext; |
724 | CommonZero &= ~Ext; |
725 | }); |
726 | KnownBits KnownSExtInReg = Known.sextInReg(SrcBitWidth: FromBits); |
727 | EXPECT_EQ(CommonOne, KnownSExtInReg.One); |
728 | EXPECT_EQ(CommonZero, KnownSExtInReg.Zero); |
729 | }); |
730 | } |
731 | } |
732 | |
733 | TEST(KnownBitsTest, CommonBitsSet) { |
734 | unsigned Bits = 4; |
735 | ForeachKnownBits(Bits, Fn: [&](const KnownBits &Known1) { |
736 | ForeachKnownBits(Bits, Fn: [&](const KnownBits &Known2) { |
737 | bool HasCommonBitsSet = false; |
738 | ForeachNumInKnownBits(Known: Known1, Fn: [&](const APInt &N1) { |
739 | ForeachNumInKnownBits(Known: Known2, Fn: [&](const APInt &N2) { |
740 | HasCommonBitsSet |= N1.intersects(RHS: N2); |
741 | }); |
742 | }); |
743 | EXPECT_EQ(!HasCommonBitsSet, |
744 | KnownBits::haveNoCommonBitsSet(Known1, Known2)); |
745 | }); |
746 | }); |
747 | } |
748 | |
749 | TEST(KnownBitsTest, ConcatBits) { |
750 | unsigned Bits = 4; |
751 | for (unsigned LoBits = 1; LoBits < Bits; ++LoBits) { |
752 | unsigned HiBits = Bits - LoBits; |
753 | ForeachKnownBits(Bits: LoBits, Fn: [&](const KnownBits &KnownLo) { |
754 | ForeachKnownBits(Bits: HiBits, Fn: [&](const KnownBits &KnownHi) { |
755 | KnownBits KnownAll = KnownHi.concat(Lo: KnownLo); |
756 | |
757 | EXPECT_EQ(KnownLo.countMinPopulation() + KnownHi.countMinPopulation(), |
758 | KnownAll.countMinPopulation()); |
759 | EXPECT_EQ(KnownLo.countMaxPopulation() + KnownHi.countMaxPopulation(), |
760 | KnownAll.countMaxPopulation()); |
761 | |
762 | KnownBits = KnownAll.extractBits(NumBits: LoBits, BitPosition: 0); |
763 | KnownBits = KnownAll.extractBits(NumBits: HiBits, BitPosition: LoBits); |
764 | |
765 | EXPECT_EQ(KnownLo.One.getZExtValue(), ExtractLo.One.getZExtValue()); |
766 | EXPECT_EQ(KnownHi.One.getZExtValue(), ExtractHi.One.getZExtValue()); |
767 | EXPECT_EQ(KnownLo.Zero.getZExtValue(), ExtractLo.Zero.getZExtValue()); |
768 | EXPECT_EQ(KnownHi.Zero.getZExtValue(), ExtractHi.Zero.getZExtValue()); |
769 | }); |
770 | }); |
771 | } |
772 | } |
773 | |
774 | } // end anonymous namespace |
775 | |