1 //===-- KnownBits.cpp - Stores known zeros/ones ---------------------------===//
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 contains a class for representing known zeros and ones used by
10 // computeKnownBits.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "llvm/Support/KnownBits.h"
15 #include <cassert>
16 
17 using namespace llvm;
18 
19 static KnownBits computeForAddCarry(
20     const KnownBits &LHS, const KnownBits &RHS,
21     bool CarryZero, bool CarryOne) {
22   assert(!(CarryZero && CarryOne) &&
23          "Carry can't be zero and one at the same time");
24 
25   APInt PossibleSumZero = LHS.getMaxValue() + RHS.getMaxValue() + !CarryZero;
26   APInt PossibleSumOne = LHS.getMinValue() + RHS.getMinValue() + CarryOne;
27 
28   // Compute known bits of the carry.
29   APInt CarryKnownZero = ~(PossibleSumZero ^ LHS.Zero ^ RHS.Zero);
30   APInt CarryKnownOne = PossibleSumOne ^ LHS.One ^ RHS.One;
31 
32   // Compute set of known bits (where all three relevant bits are known).
33   APInt LHSKnownUnion = LHS.Zero | LHS.One;
34   APInt RHSKnownUnion = RHS.Zero | RHS.One;
35   APInt CarryKnownUnion = std::move(CarryKnownZero) | CarryKnownOne;
36   APInt Known = std::move(LHSKnownUnion) & RHSKnownUnion & CarryKnownUnion;
37 
38   assert((PossibleSumZero & Known) == (PossibleSumOne & Known) &&
39          "known bits of sum differ");
40 
41   // Compute known bits of the result.
42   KnownBits KnownOut;
43   KnownOut.Zero = ~std::move(PossibleSumZero) & Known;
44   KnownOut.One = std::move(PossibleSumOne) & Known;
45   return KnownOut;
46 }
47 
48 KnownBits KnownBits::computeForAddCarry(
49     const KnownBits &LHS, const KnownBits &RHS, const KnownBits &Carry) {
50   assert(Carry.getBitWidth() == 1 && "Carry must be 1-bit");
51   return ::computeForAddCarry(
52       LHS, RHS, Carry.Zero.getBoolValue(), Carry.One.getBoolValue());
53 }
54 
55 KnownBits KnownBits::computeForAddSub(bool Add, bool NSW,
56                                       const KnownBits &LHS, KnownBits RHS) {
57   KnownBits KnownOut;
58   if (Add) {
59     // Sum = LHS + RHS + 0
60     KnownOut = ::computeForAddCarry(
61         LHS, RHS, /*CarryZero*/true, /*CarryOne*/false);
62   } else {
63     // Sum = LHS + ~RHS + 1
64     std::swap(RHS.Zero, RHS.One);
65     KnownOut = ::computeForAddCarry(
66         LHS, RHS, /*CarryZero*/false, /*CarryOne*/true);
67   }
68 
69   // Are we still trying to solve for the sign bit?
70   if (!KnownOut.isNegative() && !KnownOut.isNonNegative()) {
71     if (NSW) {
72       // Adding two non-negative numbers, or subtracting a negative number from
73       // a non-negative one, can't wrap into negative.
74       if (LHS.isNonNegative() && RHS.isNonNegative())
75         KnownOut.makeNonNegative();
76       // Adding two negative numbers, or subtracting a non-negative number from
77       // a negative one, can't wrap into non-negative.
78       else if (LHS.isNegative() && RHS.isNegative())
79         KnownOut.makeNegative();
80     }
81   }
82 
83   return KnownOut;
84 }
85 
86 KnownBits KnownBits::makeGE(const APInt &Val) const {
87   // Count the number of leading bit positions where our underlying value is
88   // known to be less than or equal to Val.
89   unsigned N = (Zero | Val).countLeadingOnes();
90 
91   // For each of those bit positions, if Val has a 1 in that bit then our
92   // underlying value must also have a 1.
93   APInt MaskedVal(Val);
94   MaskedVal.clearLowBits(getBitWidth() - N);
95   return KnownBits(Zero, One | MaskedVal);
96 }
97 
98 KnownBits KnownBits::umax(const KnownBits &LHS, const KnownBits &RHS) {
99   // If we can prove that LHS >= RHS then use LHS as the result. Likewise for
100   // RHS. Ideally our caller would already have spotted these cases and
101   // optimized away the umax operation, but we handle them here for
102   // completeness.
103   if (LHS.getMinValue().uge(RHS.getMaxValue()))
104     return LHS;
105   if (RHS.getMinValue().uge(LHS.getMaxValue()))
106     return RHS;
107 
108   // If the result of the umax is LHS then it must be greater than or equal to
109   // the minimum possible value of RHS. Likewise for RHS. Any known bits that
110   // are common to these two values are also known in the result.
111   KnownBits L = LHS.makeGE(RHS.getMinValue());
112   KnownBits R = RHS.makeGE(LHS.getMinValue());
113   return KnownBits(L.Zero & R.Zero, L.One & R.One);
114 }
115 
116 KnownBits KnownBits::umin(const KnownBits &LHS, const KnownBits &RHS) {
117   // Flip the range of values: [0, 0xFFFFFFFF] <-> [0xFFFFFFFF, 0]
118   auto Flip = [](const KnownBits &Val) { return KnownBits(Val.One, Val.Zero); };
119   return Flip(umax(Flip(LHS), Flip(RHS)));
120 }
121 
122 KnownBits KnownBits::smax(const KnownBits &LHS, const KnownBits &RHS) {
123   // Flip the range of values: [-0x80000000, 0x7FFFFFFF] <-> [0, 0xFFFFFFFF]
124   auto Flip = [](const KnownBits &Val) {
125     unsigned SignBitPosition = Val.getBitWidth() - 1;
126     APInt Zero = Val.Zero;
127     APInt One = Val.One;
128     Zero.setBitVal(SignBitPosition, Val.One[SignBitPosition]);
129     One.setBitVal(SignBitPosition, Val.Zero[SignBitPosition]);
130     return KnownBits(Zero, One);
131   };
132   return Flip(umax(Flip(LHS), Flip(RHS)));
133 }
134 
135 KnownBits KnownBits::smin(const KnownBits &LHS, const KnownBits &RHS) {
136   // Flip the range of values: [-0x80000000, 0x7FFFFFFF] <-> [0xFFFFFFFF, 0]
137   auto Flip = [](const KnownBits &Val) {
138     unsigned SignBitPosition = Val.getBitWidth() - 1;
139     APInt Zero = Val.One;
140     APInt One = Val.Zero;
141     Zero.setBitVal(SignBitPosition, Val.Zero[SignBitPosition]);
142     One.setBitVal(SignBitPosition, Val.One[SignBitPosition]);
143     return KnownBits(Zero, One);
144   };
145   return Flip(umax(Flip(LHS), Flip(RHS)));
146 }
147 
148 KnownBits KnownBits::abs() const {
149   // If the source's MSB is zero then we know the rest of the bits already.
150   if (isNonNegative())
151     return *this;
152 
153   // Assume we know nothing.
154   KnownBits KnownAbs(getBitWidth());
155 
156   // We only know that the absolute values's MSB will be zero iff there is
157   // a set bit that isn't the sign bit (otherwise it could be INT_MIN).
158   APInt Val = One;
159   Val.clearSignBit();
160   if (!Val.isNullValue())
161     KnownAbs.Zero.setSignBit();
162 
163   return KnownAbs;
164 }
165 
166 KnownBits KnownBits::computeForMul(const KnownBits &LHS, const KnownBits &RHS) {
167   unsigned BitWidth = LHS.getBitWidth();
168 
169   assert(!LHS.hasConflict() && !RHS.hasConflict());
170   // Compute a conservative estimate for high known-0 bits.
171   unsigned LeadZ =
172       std::max(LHS.countMinLeadingZeros() + RHS.countMinLeadingZeros(),
173                BitWidth) -
174       BitWidth;
175   LeadZ = std::min(LeadZ, BitWidth);
176 
177   // The result of the bottom bits of an integer multiply can be
178   // inferred by looking at the bottom bits of both operands and
179   // multiplying them together.
180   // We can infer at least the minimum number of known trailing bits
181   // of both operands. Depending on number of trailing zeros, we can
182   // infer more bits, because (a*b) <=> ((a/m) * (b/n)) * (m*n) assuming
183   // a and b are divisible by m and n respectively.
184   // We then calculate how many of those bits are inferrable and set
185   // the output. For example, the i8 mul:
186   //  a = XXXX1100 (12)
187   //  b = XXXX1110 (14)
188   // We know the bottom 3 bits are zero since the first can be divided by
189   // 4 and the second by 2, thus having ((12/4) * (14/2)) * (2*4).
190   // Applying the multiplication to the trimmed arguments gets:
191   //    XX11 (3)
192   //    X111 (7)
193   // -------
194   //    XX11
195   //   XX11
196   //  XX11
197   // XX11
198   // -------
199   // XXXXX01
200   // Which allows us to infer the 2 LSBs. Since we're multiplying the result
201   // by 8, the bottom 3 bits will be 0, so we can infer a total of 5 bits.
202   // The proof for this can be described as:
203   // Pre: (C1 >= 0) && (C1 < (1 << C5)) && (C2 >= 0) && (C2 < (1 << C6)) &&
204   //      (C7 == (1 << (umin(countTrailingZeros(C1), C5) +
205   //                    umin(countTrailingZeros(C2), C6) +
206   //                    umin(C5 - umin(countTrailingZeros(C1), C5),
207   //                         C6 - umin(countTrailingZeros(C2), C6)))) - 1)
208   // %aa = shl i8 %a, C5
209   // %bb = shl i8 %b, C6
210   // %aaa = or i8 %aa, C1
211   // %bbb = or i8 %bb, C2
212   // %mul = mul i8 %aaa, %bbb
213   // %mask = and i8 %mul, C7
214   //   =>
215   // %mask = i8 ((C1*C2)&C7)
216   // Where C5, C6 describe the known bits of %a, %b
217   // C1, C2 describe the known bottom bits of %a, %b.
218   // C7 describes the mask of the known bits of the result.
219   APInt Bottom0 = LHS.One;
220   APInt Bottom1 = RHS.One;
221 
222   // How many times we'd be able to divide each argument by 2 (shr by 1).
223   // This gives us the number of trailing zeros on the multiplication result.
224   unsigned TrailBitsKnown0 = (LHS.Zero | LHS.One).countTrailingOnes();
225   unsigned TrailBitsKnown1 = (RHS.Zero | RHS.One).countTrailingOnes();
226   unsigned TrailZero0 = LHS.countMinTrailingZeros();
227   unsigned TrailZero1 = RHS.countMinTrailingZeros();
228   unsigned TrailZ = TrailZero0 + TrailZero1;
229 
230   // Figure out the fewest known-bits operand.
231   unsigned SmallestOperand =
232       std::min(TrailBitsKnown0 - TrailZero0, TrailBitsKnown1 - TrailZero1);
233   unsigned ResultBitsKnown = std::min(SmallestOperand + TrailZ, BitWidth);
234 
235   APInt BottomKnown =
236       Bottom0.getLoBits(TrailBitsKnown0) * Bottom1.getLoBits(TrailBitsKnown1);
237 
238   KnownBits Res(BitWidth);
239   Res.Zero.setHighBits(LeadZ);
240   Res.Zero |= (~BottomKnown).getLoBits(ResultBitsKnown);
241   Res.One = BottomKnown.getLoBits(ResultBitsKnown);
242   return Res;
243 }
244 
245 KnownBits &KnownBits::operator&=(const KnownBits &RHS) {
246   // Result bit is 0 if either operand bit is 0.
247   Zero |= RHS.Zero;
248   // Result bit is 1 if both operand bits are 1.
249   One &= RHS.One;
250   return *this;
251 }
252 
253 KnownBits &KnownBits::operator|=(const KnownBits &RHS) {
254   // Result bit is 0 if both operand bits are 0.
255   Zero &= RHS.Zero;
256   // Result bit is 1 if either operand bit is 1.
257   One |= RHS.One;
258   return *this;
259 }
260 
261 KnownBits &KnownBits::operator^=(const KnownBits &RHS) {
262   // Result bit is 0 if both operand bits are 0 or both are 1.
263   APInt Z = (Zero & RHS.Zero) | (One & RHS.One);
264   // Result bit is 1 if one operand bit is 0 and the other is 1.
265   One = (Zero & RHS.One) | (One & RHS.Zero);
266   Zero = std::move(Z);
267   return *this;
268 }
269