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 "gtest/gtest.h"
15
16 using namespace llvm;
17
18 namespace {
19
20 template<typename FnTy>
ForeachKnownBits(unsigned Bits,FnTy Fn)21 void ForeachKnownBits(unsigned Bits, FnTy Fn) {
22 unsigned Max = 1 << Bits;
23 KnownBits Known(Bits);
24 for (unsigned Zero = 0; Zero < Max; ++Zero) {
25 for (unsigned One = 0; One < Max; ++One) {
26 Known.Zero = Zero;
27 Known.One = One;
28 if (Known.hasConflict())
29 continue;
30
31 Fn(Known);
32 }
33 }
34 }
35
36 template<typename FnTy>
ForeachNumInKnownBits(const KnownBits & Known,FnTy Fn)37 void ForeachNumInKnownBits(const KnownBits &Known, FnTy Fn) {
38 unsigned Bits = Known.getBitWidth();
39 unsigned Max = 1 << Bits;
40 for (unsigned N = 0; N < Max; ++N) {
41 APInt Num(Bits, N);
42 if ((Num & Known.Zero) != 0 || (~Num & Known.One) != 0)
43 continue;
44
45 Fn(Num);
46 }
47 }
48
TEST(KnownBitsTest,AddCarryExhaustive)49 TEST(KnownBitsTest, AddCarryExhaustive) {
50 unsigned Bits = 4;
51 ForeachKnownBits(Bits, [&](const KnownBits &Known1) {
52 ForeachKnownBits(Bits, [&](const KnownBits &Known2) {
53 ForeachKnownBits(1, [&](const KnownBits &KnownCarry) {
54 // Explicitly compute known bits of the addition by trying all
55 // possibilities.
56 KnownBits Known(Bits);
57 Known.Zero.setAllBits();
58 Known.One.setAllBits();
59 ForeachNumInKnownBits(Known1, [&](const APInt &N1) {
60 ForeachNumInKnownBits(Known2, [&](const APInt &N2) {
61 ForeachNumInKnownBits(KnownCarry, [&](const APInt &Carry) {
62 APInt Add = N1 + N2;
63 if (Carry.getBoolValue())
64 ++Add;
65
66 Known.One &= Add;
67 Known.Zero &= ~Add;
68 });
69 });
70 });
71
72 KnownBits KnownComputed = KnownBits::computeForAddCarry(
73 Known1, Known2, KnownCarry);
74 EXPECT_EQ(Known.Zero, KnownComputed.Zero);
75 EXPECT_EQ(Known.One, KnownComputed.One);
76 });
77 });
78 });
79 }
80
TestAddSubExhaustive(bool IsAdd)81 static void TestAddSubExhaustive(bool IsAdd) {
82 unsigned Bits = 4;
83 ForeachKnownBits(Bits, [&](const KnownBits &Known1) {
84 ForeachKnownBits(Bits, [&](const KnownBits &Known2) {
85 KnownBits Known(Bits), KnownNSW(Bits);
86 Known.Zero.setAllBits();
87 Known.One.setAllBits();
88 KnownNSW.Zero.setAllBits();
89 KnownNSW.One.setAllBits();
90
91 ForeachNumInKnownBits(Known1, [&](const APInt &N1) {
92 ForeachNumInKnownBits(Known2, [&](const APInt &N2) {
93 bool Overflow;
94 APInt Res;
95 if (IsAdd)
96 Res = N1.sadd_ov(N2, Overflow);
97 else
98 Res = N1.ssub_ov(N2, Overflow);
99
100 Known.One &= Res;
101 Known.Zero &= ~Res;
102
103 if (!Overflow) {
104 KnownNSW.One &= Res;
105 KnownNSW.Zero &= ~Res;
106 }
107 });
108 });
109
110 KnownBits KnownComputed = KnownBits::computeForAddSub(
111 IsAdd, /*NSW*/false, Known1, Known2);
112 EXPECT_EQ(Known.Zero, KnownComputed.Zero);
113 EXPECT_EQ(Known.One, KnownComputed.One);
114
115 // The NSW calculation is not precise, only check that it's
116 // conservatively correct.
117 KnownBits KnownNSWComputed = KnownBits::computeForAddSub(
118 IsAdd, /*NSW*/true, Known1, Known2);
119 EXPECT_TRUE(KnownNSWComputed.Zero.isSubsetOf(KnownNSW.Zero));
120 EXPECT_TRUE(KnownNSWComputed.One.isSubsetOf(KnownNSW.One));
121 });
122 });
123 }
124
TEST(KnownBitsTest,AddSubExhaustive)125 TEST(KnownBitsTest, AddSubExhaustive) {
126 TestAddSubExhaustive(true);
127 TestAddSubExhaustive(false);
128 }
129
TEST(KnownBitsTest,GetMinMaxVal)130 TEST(KnownBitsTest, GetMinMaxVal) {
131 unsigned Bits = 4;
132 ForeachKnownBits(Bits, [&](const KnownBits &Known) {
133 APInt Min = APInt::getMaxValue(Bits);
134 APInt Max = APInt::getMinValue(Bits);
135 ForeachNumInKnownBits(Known, [&](const APInt &N) {
136 Min = APIntOps::umin(Min, N);
137 Max = APIntOps::umax(Max, N);
138 });
139 EXPECT_EQ(Min, Known.getMinValue());
140 EXPECT_EQ(Max, Known.getMaxValue());
141 });
142 }
143
144 } // end anonymous namespace
145